一种求解网络最大流问题的算法

一种求解网络最大流问题的算法 一 种求解网络最大流问题的算法) 凌永发徐宗本 (西安交通大学理学院西安710049) 计算机科学2006Vo1.33No.6 摘要随着网络应用的不断深入,人们对网络传输容量和服务质量的要求和期望也越来越高, 高性能网络成为 一 项迫切的工作.缓存的配置直接影响网络的时延和丢失率,网络缓存和网络传输容量的合理 匹配,能很好提高网络 性能.文章简述了网络最大流问题的现状,提出了一种求解网络最大流问题的算法.算法基于 MPLS流量X-.程技 术,在实现网络最大流的情况下,同时对M争分支(链路)重新分配流量,达到合理分配网络流 量和利用网络资源的目 的.仿真结果表明算法是有效的. 关键词最大流问题,多标签交换(MPLS),流量工程,算法 AnAlgorithmfortheSolutiontotheMaximum-flowProblemofNetworks LINGYong-FaXUZong-Ben (FacultyofScience,Xi?artJiaotongUniversity,Xi?art710049) AbstractWithexpansionofInternetapplication.people?Sexpectationandrequirementonnetworktransmissioncapaci— tyandservicequalitybecomehigherandhigher.Therefore,itisimperativetOdesignthenetworkwithstrongperform alice,ConfigurationofburfermemorydirectlyinfluencesthedelayandlOSSrateofnetwork.Goodmatchbetweenbuff— ermemoryofnetworkandnetworkcapacitywillimproveperformanceofnetwork.Theconditionofthemaximum-flow problemisproposedsimplyinthisarticle,andpresentsaalgorithmforthesolutiontOthemaximum-flowproblemof networks.ThealgorithmsolutesthemaximumqlowproblemofnetworksbasedonMPItrafficengineeringtechnolo gY,anddistributesflowagaintobalanceloadandusenetworkresourcesreasonable.Thesimulationresultsshowthe givenalgorithmiseffective. KeywordsMaximumflowproblem,Multi—protocolLabelSwitching(MPLS),Trafficengineering,Algorithm 最大流问题是指在一定的条件下,要求流过网络的物流, 能量流,信息流等流量为最大的问题最大流问题已有4O多 年的研究历史,这段时期内,人们建立了最大流问题较为完善 的理论,同时开发了大量的算法.如Ford和Fulkson增截轨 算法,Dinic阻塞流算法,Goldberg推进和重标号算法以及 Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法 及相关技术对网络最大流问题的研究起到了非常重要的推动 作用. 近年来,随着计算机科学技术和网络的快速发展,网络最 大流问题得到了更深入的研究,并极大地推动了最大流问题 的研究进展.然而,研究工作仍未结束:首先,在理论算法研 究方面,人们还没有发现最大流问题算法时间复杂度的精确 下界,更没有任何一个通用算法达到或接近问题的下界;其 次,在算法的实际性能方面,目前算法的实际性能也不能满足 许多应用问题的要求;同时,最大流问题作为特殊的线性规划 问题,它远比一般线性规划问题容易解决,发现应用领域中的 问题和最大流问题的联系可以使应用问题更好地得到解 决. 因此,关于网络最大流问题的研究具有十分重要的理论 意义和实用价值. 1提出问题 在实际的网络中,网络的结点和边都是有容量限制的. 很多情况下我们需要知道在一个有容量限制的网络中,当传 输流量时,如何充分利用整个网络拓扑从源S到汇T传输流 量,而不是只使用路由路径或某个单一链路,实现从S到T 的最大传输流量,这就是要解决的网络最大流问题 传统的基于IP的转发(如最短路径算法SPF)不能 充分利用网络的传输能力,而基于MPLS(Multi-ProtocolLa— belSwitching,简称MPLS)的流量工程(TrafficEngineering, 简称TE)为解决网络最大流问题提供了一条途径J. 流量工程是与可操作网络性能优化相关的Internet网络 工程的一个方面,它包含运用技术和科学的原则去测量,模型 化,特性化Internet流量控制,以及运用这种知识和技能来得 到特定性能目标,包括可靠,快速的网络通信,网络资源的有 效利用,网络容量规划.基于约束的动态路由选择(Con— straint-basedDynamicRouting)是流量工程的重要组成部分, 它利用现有路由协议的扩展协议,从流量需求和网络资源角 度考虑,得出路径需要满足的一系列约束条件和目标函数,计 算出由入口路由器到出口路由器间的多条路径.流量工程的 另一个重要组成部分是流量均衡(Load—balancing),它的作用 在入口路由器到出口路由器之间为已建立好的M条路径按 一 定算法规则重新分配流量.在多条路径间分配流量的好处 是提高了大带宽业务流量的接纳率,并且使网络资源均衡使 用,能够提高网络的吞吐量_4]. MPLS网络采用显式路由技术,能够通过静态配置或动 *)国家自然科学基金(10371097),云南省计算机应用技术重点实验室开放基金资助项目.凌 永发博士后,副教授,主要研究方向为网络算法 和网络控制. ? 39? 态路由方式在入口路由器到出口路由器之间得到一条或多条 显式路径LSP(LabelSwitchingPath),避开瓶颈链路,避免流 量对瓶颈资源的竞争,优化流量到资源的映射,提高网络性 能 算法正是基于MPLS的流量工程技术来解决网络最大 流问题. 2数学模型与仿真算法 最大流问题一般有如下要求]:(1)网络有一个起点(又 称源)和一个终点(又称汇),若有几个起点或终点,则可 以通过增加虚拟节点而转化为一个起点和一个终点;(2)网络 是有向网络,即流有方向性.如果是无向网络或混合网络,则 应转化为有向网络;(3)在网络各条弧上都有一个权,表示允 许流过的最大流量.若以b表示由到口的弧上允许流过 的最大流量.以z表示实际流过该弧的流量,则存在O?xi) ?6(4)网络中,对于除起点和终点之外的任何顶点,流入量 的总和应该等于流出量的总和,即?z一?z,?s,t. 由上述规则,可以归纳出最大流问题的一般数学描述如 下: 优化目标:maxf 约束条件: ff一_厂s .J-Exij一{0iCs,1l flo?z? 采用Goldberg和Rao的二分长度阻塞流经典算法来求 解最大流问题.算法伪代码如下: begin x=0; G(z)=G; F~nV; whileF?1do begin A=min{lF/m1/0l,lF/nZ/.1); f0r(,j)EG(x) ifr/i>3Athenlength(i,j)=0; elselength(t)=1; 计算各结点的精确距离标号 计算所有候选截的剩余容量 if存在候选截[,]使cEsk,7k3<F/Zthen F=cEsk,]; else 将由长度为0的边构成的强连通分量收缩成一个点 在收缩后图中,调用gold和的阻塞流算法,. b, ergTarjan 寻找阻塞流或流量为?的沉计算收缩成点强连通分量中的流 用所得到的流更新流-T并更新G(z) end; end; end. 3算法 Goldberg和Rao算法采用自适应二分长度函数,即一个 剩余边的长度取决于对剩余流量的估计值F.和F相比.剩 余容量相对较大的边的长度定义为0,剩余容量相对较小的 边的长度定义为1.在由这个长度所定义的可容许图(仅包 含可容许边的图)中,算法把长度为0的边所构成的强连通分 量收缩成一个点,这样收缩后的可容许图是一个无环图.这 样利用1990年Goldberg和Tarjan提出的阻塞流算法计算此 无环图中的最大流,然后算法对通过收缩成一个点的强连通 分量内部的流单独计算. 算法在执行过程中保持一个流和一个截,这个截的容量 确定了剩余容量的一个上界.算法同时保持一个参数F,它 ? 40? 是剩余流量的估计值.当算法发现一个剩余容量少于F/2 的截时,用此截的容量更新F的值,重新计算每边的长度 Goldberg和Rao算法需O(1ogU)次迭代,在每次迭代中,占主 要操作时间的是Goldberg和Tarjan算法的阻塞流算法,它需 要O(min{n2/.,/}rnlog(n./m))的时间.于是有:Goldberg 和Rao算法可以在O(rain{n2/.,l/}mlog(n/m)log.r)时间 内计算出最大流. 图1为网络拓扑图,节点A,B,C,D,E,F为标签交换路 由器(LabelSwitchingRoute,简称LSR),有向弧上的数字代 表相应链路的最大容量;图2是网络流量最大时各链路需求 图,它是通过Goldberg和Rao二分长度阻塞流经典算法计算 出的当网络达到最大流量时,每条链路可以达到的链路流量. 括号中.第1个数字为链路的残余容量.第2个数字为网络传 输达到最大流时的该链路应达到的流量. S S 图1网络拓扑图 T 图2网络最大流时链路流量需求图 4算法仿真实验 MPLS的网络体系主要由位于网络边缘的路由器U1R (LabelEdgeRouting)和位于网络核心的LSR(LabelSwitc- hingRouting)两大部分组成.复杂的流量管理与控制功能主 要集中在LER中完成.业务流的QoS(QualityofService)请 求能否得到保证,由接纳控制决定.接纳控制根据控制平面 的接纳策略来决定是否可以满足一个新的LSP的建立请求, 或是否能够实现对LSP属性的修改接纳控制后,LER把业务 流映射到适当的LSP中,并设定LSP的相关属性.然后通过 执行一定的资源预留和控制操作,为LSP中的业务流提供相 应的QoS保证. 流量工程通过建立网络边界结点之间的逻辑连接.在物 理拓扑结构上构造一个虚拟网,通过逻辑连接与物理拓扑之 间的合理映射解决流量工程存在的问题. 通信网中,分支(或称链路)是指从源点到汇点都能保持 同一带宽的一条传输通道.在网络拓扑图上的一条有向弧可 以容纳一条或几条分支.现在虽然知道每条链路可以使用的 流量,但不知道从源点到汇点可以分成多少分支,以及该分支 应该预留的网络带宽,所以还不能建立符合资源预留要求的 LSP.为解决这个问题,首先用数据结构中图的邻接表表示 法表示已经获得的网络拓扑图.在图中,权重表示通过前面 算法计算出的达到最大流时链路上的流量.由分支和预留的 网络带宽值组成的数据结构,称为分支元素,所有分支元素组 成一个新的动态链表,用来记录所有的分支及其网络带宽预 留值,称为结果链表.利用Kruskal算法]可以得到所有分 支及相应的带宽预留值. 在得到每个分支包含的节点和网络带宽预留值后,基于 IS的流量工程技术,就可以扩展资源预留协议RSVPc] (ResourcereSerVationProtoco1)建立各分支的LSPLSP建 立后,就建立了从源点到汇点的多条数据传输通道,当有数据 流从源点到汇点时,就可以将其安排到一条分支上,或采用分 流的方法转发到多条分支上. IsP建立后,为了将其高效地映射到MPLS的物理链路 上,MPLS系统必须选择合适的路由选择策略与机制.路由 选择策略决定系统采用何种算法寻找满足一定QoS要求的 路径,以及采用何种度量衡量路径的优劣.路由选择机制则 决定路由计算的方式,如采用源路由还是分布式路由计算;采 用按需计算还是预计算路由表等.. 基于上述前提和思路,依据网络拓扑结构,采用应用非常 广泛的Waxman模型l_8]生成仿真网络.网络模型图中边(“, )的生成概率由式(1)决定.式中,d是”,之间的欧式距 离,L为图中任意两点间的最大距离. prob(“,)一e_d,O??1,L3>/](1) 对节点对(,),取三个随机数,@,n,c)?[0,1],则 S,t之间的业务流需求由式(2)决定,g为正常数由于(, )由3个随机数相乘决定,因此变化范围可以很宽. (,)一旭DfC0e”“),,O?Q,D,G.?1(2) 30 25 分20 支15 数10 5 0 分支利用率 图3网络流量分布示意图 基于算法数学假设,同时对生成节点数为6o,链路数为 96(即II一60,IEI=96)的仿真网络以及不同的业务量需 求,对最短路径算法SPF和最大流问题算法NGA进行仿真 实验.仿真结果显示,在流量轻载的情况下,SPF算法也能满 足网络业务流量需求.在流量重载的情况下,SPF的性能恶 化得很快.随着网络流量的增加,应用NGA对网络流量分 布实施优化的意义与效果也越为明显,网络业务流的分配得 „——到子裒妊的平衡,因而网络的服务能力大大提高.图3给出 了总业务量需求为3283时,网络中流量分布(各分支利用率) 情况,显示了应用NGA进行网络优化,实施流量均衡的意 义.另外,仿真发现随着网络规模增大,算法的运行时间并没 有显着增加,仍能保持良好的性能 结束语随着Internet业务快速增长,网络不断升级,组 网结构越来越复杂,链接带宽也大小不一.合理利用带宽,减 少拥塞的发生是实现服务质量(QoS)的机制的重要一环.基 于MPIS的流量工程的显着优势使其成为一种易于管理,扩 展性好,性价比高的流量工程解决l_9]. 一 直以来,网络最大流的应用都是一项十分有意义的研 究工作,网络流问题的研究者和具体问题的工程师从不同的 角度充实着这方面的研究.实践表明,对许多实际应用问题, 如果能找到它和最大流问题的联系,就可以使问题得到十分 有效的解决.同时,许多应用问题所对应的最大流问题都有 比较明显的特征,充分利用这些特征,设计面向应用问题的算 法,这也是一项很有意义的工作. 本文提出了一种求解网络最大流问题的优化算法.算法 基于MPLS流量工程技术,在实现网络最大流的情况下,同 时对M条分支(链路)重新分配流量,达到合理分配网络流量 和利用网络资源的目的.仿真结果表明算法是有效的. 参考文献 1GoldbergAV,RaoSBeyondtheflowdecompositionbarrier __J].JAssocComputeMath,1998,45(5):783~797 2张宪超,陈国良,万颖瑜.网络最大流问题研究进展[J].计算机研 究与进展,2003,40(9):1281~1292 3XiaoxP.TrafficengineeringwithMPLSintheInternet[J]_ IEEENetworking,2000,14(2):28~33 4GirishMK,ZhouB,HuJQFormulationofthetrafficengineer— ingproblemsinMPLSbasedIPnetworks[A].TheFifthIEEE— ISCCI-c-1.Antibes,France,2000.214~219 5AhujaRK,MagnantiTL,OrlinJHNetworkFlows:Theory, AlgorithmsandApplications[M].NewJersey;PrenticeHall. 2000.134,151 6WangYF,Wang乙ExplicitroutingalgorithmsforInternettraf— fieengineering[A].IEEEICCCN99I-c-1.Boston,MA,1999. 582,588 7AwduchenRSVP—TE:extensionstoRSVPforLSPtunnel& IETF,InternetDraft.,2001 8WaxraanBMRoutingofmultipointconnectionslJ].IEEE JournalonSelectedAreasinCommunications,1988,6(9):1617, 1622 9LeeY,SeokY,CcholY_Aconstrainedmultipathtrafficengineer— ingschemeforMPLSnetworks[A].ICC02I-c-1.NewYork, 2002.2431,2436 - 41?