动态路由优化中的最短路径并行计算方法研究进展

1动态路由优化中的最短路径并行计算方法研究进展杨忠明秦勇茂名学院广东茂名525000摘要:本文总结了国内外一些最短路径并行计算算法目前的主要研究结果，并从QoS路由选择目标中的一些方法特点对动态路由优化算法进行改进，使用最短路径并行计算是解决动态路由优化的计算量问题的方法之一，并提出了最短路径并行计算算法优化路由策略的实验方法。关键词:最短路径；并行计算；动态路由优化；QoS路由；Pareto子集；中图分类号：TP391文献标识码：A1引言网络中流量的特点是影响网络路由设计的主要因素，对于路由算法设计则必须基于流量，但对于大多数AS(AutonomousSystem)，基于目前的算法，网络中大部分时间内的流量是相当稳定的，但是通常会存在一些时段，网络中的流量会突然变化，对于现有的路由算法基于性能和复杂度考虑没有进行重新计算或调整。已经许多研究者对AS中高突发流量究，通过这些高突发流量的调查报告发现，导致网络高突发流量的原因有诸如病毒的爆发、ISP路由变动、拒绝服务攻击等原因，另外基于多媒体的UDP流量日益增多，使得突发流量往往影响到网络中的关键业务[1-4]。如果路由算法没有考虑到网络中的突发流量的负载均衡，通常会导致网络链路和路由不必要的过载，延迟加大，丢包率增加，网络的吞吐量降低，甚至威胁路由器安全。传统的路由算法通常是基于数据传输对网络情况的预测[5]。而基于算法性能和复杂度不考虑网络突发流量的实际，算法通常是根据采集到网络流量的部分度量样本，基于采样对网络性能优化，而这些采样并不能反映网络的真实情况[6]。ZhangC.等提及算法考虑多个具有代表性的流量矩阵，然后找到一组优化路由使得代表性的流量矩阵的最差代价达到最小，但是这里的最差代价并非全局仅限于网络流量的采样[7,8]。KandulaS.等提及算法对实际网络上流量进行管理，以响应瞬时流量的需求做出优化[9]。这些动态适应算法的优点在于如果它们能够迅速收敛，则不需要过多的采样或者做出预测。近年来在网络流量领域值得关注的是域内的流量工程与域间的路由和流量间交互作用，研究发现一个AS域内的流量会导致AS出口处流量的变化这种流量变化会触发相邻AS路由的变化，导致网络的不稳定[10,11]。COPE(Common-caseOptimizationwithPenaltyEnvelope)算法被提出来解决这种情况[6]。要应对网络中突发流量，有效的办法就是开发出简单快速的路由算法并进行路由优化。22国内外最短路径并行算法研究概述国外许多专家学者较早对最短路径并行算法的实现方法进行了探讨，建立了串行标号设定算法和标号修正算法的各种不同并行实现方法，并在此基础上对比各种算法的性能及效率。目前，针对各种不同的串行最短路径算法而提出的并行算法大体可以分为两类：一类是不依赖于计算机类型的算法，包括Tseng等提出的算法[12]；另一类是针对特定计算机类型的算法，包括Habbal等提出的算法[13]。在有关最短路径并行算法研究的文献中，大部分都是针对全源最短路径问题，分为以下三种：基于标号设定的并行算法、基于标号修正的并行算法、动态规划方法。(1)标号设定并行算法Habbal等实现了分布式网络上的标号设定最短路径并行算法，并取得了较好的加速比，但同时也承认算法的性能依赖于网络的分割方式[13]。Crauser等提出了一种Dijkstra算法并行化的理论方法，将Dijkstra算法的整个计算过程分成几个阶段来并行执行，这是一种过程分解的方法，此方法具有很好的理论性能，但却需要进一步的研究与实际测试[14]。(2)标号修正并行算法Narayanan讨论了Floyd算法的两种数据并行实现方法，并对这两种方法进行了对比，但却没有测试它们相对于串行算法的加速比[15]。Polymenakos和bertsekas采用拍卖算法来实现并行化，拍卖算法本身的运行速度要比一般的串行单源最短路径算法慢，但他们通过实验指出，拍卖算法非常适合于并行化[16]。此外，Adamson和Tick以及Bertsekas等也给出了在虚拟共享存储机器上标号修正并行算法的实验结果[17,18]；同时Papaefthymiou和Rodrique实现了Bell-Ford-Moore标号修正并行算法，并与串行Bell-Ford-Moore算法进行了比较[19]。(3)动态规划并行算法Ziliaskopoulos等采用共享存储和消息传递的方法设计了基于时间的动态最短路径并行化算法[20]，这种并行算法以Ziliaskopoulos和Mahmassani提出的串行动态最短路径算法为基础，同时还采用了离散时间步长以及Bellman的最优原则理论[21]，但却没有在大规模网络上进行实际测试。Ziliaskopoulos和Kotzinos对此算法作了进一步的研究，并在并行虚拟机(PVM)上实现了基于时间的动态最短路径算法的并行化，实验结果表明，随着时间步数的增加算法的加速比也有所改善，但同时他们也指出需要在实际网络和随机网络上对算法的效率作进一步的测试[22]。目前国内有关最短路径并行算法研究的文献还不多见。谭国真和隋春丽在PC机群环境下3研究了最短路径并行算法，给出了SPMD模式下的最短路径并行算法的简单实现过程，并在非循环图网络模型和强连通随机网络模型上对算法的加速比和并行效率进行了测试[23]。但在网络分割策略中采用静态负载平衡策略，没有考虑动态变化的网络带宽和各个节点机的动态变化情况，不能高效利用各节点机的计算资源，但还需要在各种不同规模的网络中对算法性能作进一步的实际测试。3未来最短路径并行算法的研究热点与工作(1)研究最短路径并行算法在分布式并行集群上的实现方法，并在大规模实际网络中对算法的效率及性能作详细深入的测试。(2)优化在最短路径并行算法中的负载平衡算法，以期能够更加有效的利用分布式并行计算环境的资源，从而也可以进一步提高求解大规模网络上最短路径的速度。(3)研究最短路径并行算法对动态性和实时性要求较高的系统中的实际应用。4并行路由算法的启发在QoS路由的选择目标中,通常希望端到端的延迟最小,丢失率最小,瓶颈带宽最大,所占用的网络资源最少,多个目标的选择中多个目标往往是相互冲突的，不能归一化，如果只强调改善某个目标,其后果会使另一目标或整个网络性能变坏。因此,在多目标规划中,一般不存在所有目标函数共同的极大点，即绝对最优解，多次运行单目标优化过程并逼近Pareto最优解或在它们之间进行折衷和权衡，使各子目标函数都尽可能优化。但是这个过程的计算量非常大，时间复杂度高，且非常容易受到网络状态和路由请求约束的个数和参数的影响，通过并行的约束淘汰和全局的寻优计算，可大幅度地减少路由算法搜索时间，全局的代价评估可提高算法整体的效率性能、算法广播次数少，但数据量大，因此只适用于中小型网路。求解目标的相似性程度越高，并行计算的效率也就越高，并行路由搜索应考虑网络结构是否一致，算法是否一致，处理器处理能力是否一致，通信方式是否一致，代价是否有较大偏离。为有效提高计算效率，可将QoS度量的Pareto子集并行搜索条件设定为执行同样的算法和通信方法，使用相同的处理器每个处理器保持同样的网络图邻接矩阵的副本。可以预期处理器基于各自QoS度量计算路由时，检测和判断将产生差异，比如检测丢包率和误码最为费时，剩余带宽较费时，检测跳数和时延比较省时。影响并行算法效能的主要因素分析：串行计算复杂性仍然很高，计算复杂性主要来自节点个数。为进一步降低Pareto的搜索空间，还基于以下几点考虑：4基于约束集删除不满足约束条件的备选路径减少搜索路径的数量，约束条件的个数也是影响复杂度的重要因素；频繁重新计算路由可以较好平衡负载，但是付出较多的计算代价，减少计算路由可以抑制路由抖动增强网络稳定性，因此可根据路由优化的满意度进行权衡；如果增加备选路径，可以保证在约束条件阻止路由时，网络仍能选择一个路由，由于涉及到主次QoS度量的排序，复杂度就会急剧增长；将网络图分区，各区并行计算路由，有效降低在一次计算时所涉及的节点数，提高计算效率和计算所花费的时间。原多目标优化的Pareto集并不位于相同的QoS度量上，即约束作用并不完全相同，产生这种情况的主要原因是请求服务模式的差异，通过约束和并行的寻优计算，并行计算每个QoS度量的各自Pareto子集，若以相同的请求服务模式和约束条件并行求解Pareto子集，再根据代价定义求解综合性能较优的全局路由，可以获得较低的时间复杂度和较优的总体性能。5动态路由优化算法实验方法基于QoS的路由选择策略有两类应用背景,一类是为流量工程；另一类是为动态请求。而对于动态请求来说，QoS路由是基于每个流计算的，这些请求被显式地表达成对资源的需求,路由计算更加频繁,资源分配的粒度更小。针对第二类应用背景，同时考虑到网络状态的不确定性，为了适当地减少路由计算的频度并提供一定使用范围的路由，我们提出了基于QoS度量并行计算的预计算方法：先对QoS度量分几个区间，计算满足这几个区间路由请求约束可行路径的Pareto子集，然后根据QoS度量综合折衷权衡，在Pareto子集中综合选择合适的转发路由。也就是说,将路由问题分成与实际请求无关的可行路径计算和与实际请求相关的路由优化选择两部分,配置并编程期望在Linux下实现上述算法。动态路由优化的协议支持,开发在Linux下实现开发配置,使之支持MPLS,QoS相关协议,依据MCOP,SSAP,QPAS等算法编程替代Linux原有的路由选择模块。集成调试步骤如下：(1)定制内核以支持基于SMP的IP重组计算；(2)定义分组过滤规则；(3)使用切割调度算法对目的地址集合进行初步静态路由优化；(4)按照MCOP,SSAP,QPAS等算法对动态路由进行优化(5)记录日志;5(6)依据MCOP,SSAP,QPAS等进行迭代优化路由计算;(7)分析日志，评估动态路由优化效果。结束语本文对目前动态路由优化的概况做了简述，通过设计并行计算的方式来实现动态路由优化中的最短路径计算是目前行之有效的方法，概述了国内外一些专家对最短路径并行计算算法的设计方法。本文通过QoS路由的选择目标中的一些方法特点对动态路由优化算法进行改进，以期可应对网络中突发流量，开发简单快速的路由算法并进行路由优化，并提出了最短路径并行计算算法优化路由策略的实验方法。参考文献[1]TeixeiraR.,AgarwalS.,RexfordJ..BGProutingchanges:MergingviewsfromtwoISPs[J].ACMSIGCOMMComputerCommunicationsReview,2005,10:79-82[2]TeixeiraR.,DuffieldN.,RexfordJ.,etal.Trafficmatrixreloaded:Impactofroutingchanges[A].In:ProceedingsofPassiveandActiveMeasurement-6thInternationalWorkshop[C].LectureNotesinComputerScience:2005,(3431):251-264[3]XuK.,ZhangZ.-L.,BhattacharyaS..ProfilingInternetbackbonetraffic:Behaviormodelsandapplications[A].In:ProceedingsofACMSIGCOMM’05[C].hiladelphia,PA:ComputerCommunicationReview,2005,35(4):168-180[4]Zhang-ShenR.,McKeownN..DesigningapredictableInternetbackbone-network[A].In:ProceedingsofThirdWorkshoponHotTopicsinNetworks(HotNets-III)[C].SanDiego,CA:Lecture