IP网络时延敏感型业务流自适应负载均衡算法
2015年3月Journal on Communications March 2015 第36卷第3期通信学报V ol.36No.3 IP网络时延敏感型业务流自适应负载均衡算法
杨洋1,2,3，杨家海1,2，王会1,2，李晨曦1,2，王于丁1,2
（1. 清华大学网络科学与网络空间研究院，北京100084;
2. 清华信息科学与技术国家实验室（筹），北京100084；
3. 西安通信学院信息管理中心，陕西西安710106）
摘 要：互联网对时延敏感的业务数据流，要求具有较低的端到端时延，但是网络拥塞的发生，将会使服务质量无法保证。基于链路关键度提出了一种新的自适应负载均衡路由算法(LARA，load adaptive routing algorithm)，能最大限度地避开拥塞链路从而减少端到端延迟。该算法通过得到一个优化目标函数，并利用凸优化理论将优化目标函数分解为若干个子函数，最终得到一个简单的分布式协议。利用NS2仿真器在基于CERNET2真实的拓扑结构上进行仿真实验，同时与网络中能普遍部署的等开销多路径（ECMP，equal-cost multi-path）算法相比较，通过测试反馈时延、分组丢失率、流量负载，结果表明LARA具有更好的自适应性和健壮性，性能相比更优。
关键词：网络拥塞；关键链路；链路关键度；多路径路由；负载均衡
中图分类号：TP393.1 文献标识码：A
Towards load adaptive routing based on link critical
degree for delay-sensitive traffic in IP networks
YANG Yang1,2,3, YANG Jia-hai1,2, WANG Hui1,2, LI Chen-xi1,2, WANG Yu-ding1,2
(1. Institute for the Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China;
2. Tsinghua National Laboratory for Information Science and Technology (TNList), Beijing 100084, China;
3. Information Management Center, Xi’an Communication Institute, Xi’an 710106, China )
Abstract: Delay-sensitive traffic requires lower end-to-end delay in IP networks, such as online video, VoIP, video con-ference. Based on the criticality degree of link. A load adaptive routing algorithm (LARA) was presented which could avoid the link to be congested to reduce the end-to-end delay. Firstly, an optimization objective function has been put forward; and then decomposed into several sub-functions by using convex optimization theory; finally, the optimization objective function and sub-functions were transformed into a simple distributed protocol. LARA with ECMP (equal-cost multipath) routing strategy was compared which was widely deployed in the network by using NS2 simulation under CERNET2 topology. By evaluating the feedback delay, packet loss rate and traffic load, the results show that LARA can exhibit good performance and achieve excellent load balance, and meanwhile improve the robustness of the link when using multipath routing technology.
Key words: network congestion; critical link; criticality degree of link; multipath routing; load balance
1引言
伴随着宽带互联网增值业务进入消费者市场，交互式应用程序变得越来越流行，如视频直播、VoIP、多媒体会议、在线游戏等。截止到2013年12月，中国网络视频用户已达4.28亿，网民使用网络视频业务的比例上升至69.3%，在选择网站时，约四成的用户考虑了“播放流畅”因素[1]。在
收稿日期：2014-01-08；修回日期：2014-05-28
基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2012CB315806）；国家自然科学基金资助项目（61170211，61202356, 61161140454）；教育部博士学科专项基金资助项目（20110002110056, 20130002110058）
Foundation Items: The National Basic Research Program of China (973 Program) (2012CB315806); The National Natural Science Foundation of China (61170211, 61202356, 61161140454); Specialized Research Fund for the Doctoral Program of Higher Educa-tion (20110002110056, 20130002110058)
doi:10.11959/j.issn.1000-436x.2015082
通信学报第36卷
全球范围内，思科预计在2018年[2]，互联网视频流量将会占到所有互联网流量的80%到90%，相比2013年增长了66%。随着我国“三网融合”的加快，实时多媒体业务对承载网络的服务质量(QoS)能力提出了更高的要求。在QoS的指标当中，最小化网络时延是针对视频类网络服务的关键度量指标[3]。为了保障视频类应用的互动性以及能够做到实时回放，数据分组交付的低时延是必须要保证的，即使是一个短暂的突发延迟都可能会影响到用户体验。但是目前的互联网设备对这种时延敏感型的数据流传输并没有做到很好的支持，数据流在链路中传输容易遭受瞬时的链路拥塞，造成突发的时延或分组丢失，从而降低视频流的质量。
之前的研究工作，用QoS的方法能够对有延迟和带宽需求的应用程序提供保障[4]，满足某个应用程序在特定的带宽和延迟下数据分组的交付，例如RSVP协议。然而，这种方法需要网络中的资源协调工作，因为它需要沿数据传输路径上的每一个节点为应用程序的请求预约保留资源。此外，还需要使用准入控制，即在数据源端根据端到端的网络特性和所需要保证的QoS对进入网络的流进行分类，如果时延的增加超过某一阈值，那么这些数据源端将不允许发送数据。本文试图找到一个更简单更实用的解决方案，不需要为每流进行资源预订，同时允许用户在他认为需要的时候能够不受限制地传输数据。
目前，由于多路径路由[5~7]技术与传统单路径路由相比，能够提供链路的负载均衡、容错、聚合可用带宽以及提高端主机的吞吐量[8]等优点，使其越来越受到重视。文献[9,10]主要针对路由快速恢复和路由保护，当一条链路发生拥塞或者不可达，多路径路由技术能对数据流进行重路由，从而避开拥塞或者失效链路，提高数据交付的可靠性和健壮性。但是，如果是因为链路的暂时故障，例如路由器断电等因素，等到故障链路恢复后，路由又切换回首选主路由，这样路由的频繁切换，容易引起路由震荡[11]。无论是路由快速恢复或路由保护，都是为主路由选择备份路由，其实质还是单路径路由。并行的多路径路由，例如ECMP[12]算法采用简单的轮询方式将数据分组均匀地分布到多条等代价的路径上，达到负载均衡的目的。并行多路径路由还可以根据应用服务的需求，首先对数据分组进行分类，例如需要低时延的业务、高吞吐量的业务或者安全度高的业务，然后同时在多条路径上并行地传输数据。并行多路径传输机制相比于单路径能够保障低时延业务需求，例如VoIP 的应用[13]，只是对数据分组进行分类将会增加额外的数据平面开销。而本文使用的关键技术也是并行多路径路由，不同的是，为减少数据平面的开销，并不对数据分组进行分类，而是直接对基于链路关键度的开销进行优化，最小化链路总时延。
文献[14~16]为最小化网络传播时延采用的方法，是为每个源节点指定大概有多少流量从该节点离开并进入与该节点连接的链路。虽然文献的研究工作是采用多路径路由并在理论上能达到时延的最优值，但是还存在如下几个问题。首先，文献[14]无法做到在流量发生波动的情况下提供一个合适的步长值使算法收敛，这个问题在文献[15]中得到解决，但是增加了算法的复杂度，如算法需要估计时延二阶导数的下限和上限值；其次，测量开销的问题[16]，算法需要测量链路的传播时延、剩余带宽等信息，无论主动测量还是被动测量都需要增加一定的开销值并对实际流量产生影响，测量造成的误差容易对链路的性能产生误判，影响算法的准确性。相比之下，本文的方法更实用，因为不需对当前的路由协议进行太多的修改，其次充分利用链路状态协议的扩展信息[17]，降低算法复杂度，减轻路由器计算负担。
文献[18]提出了最小干扰路由算法(MIRA, minimum interference routing algorithm)，它的关键思想是在源和目的节点对之间选择一条对未来业务产生最小干扰的路径。MIRA 算法中关键链路的定义是当链路容量减少一个单位时，源目的节点对之间的最大流也减少。该算法的目标是选择包含尽可能少的关键链路的路径，一般可以避免瓶颈效应。在本文中，将重新定义关键链路，并基于链路关键度提出了一种新的算法能最大限度地避开拥塞链路，从而减少端到端延迟。本文优化的目标函数是以链路关键度作为链路流量分配的权值函数，通过将目标函数的优化分解[19]从而获得一个简单的分布式解决方案，同时，将它转换成一个实际的协议，即基于链路关键度的自适应负载均衡路由算法(LARA, load adaptive routing algorithm)，使它能够被网络中的路由器和数据源端很好地执行。算法的设计目标是：1)能最小化网络流量的时延；2)通
第3期杨洋等：IP网络时延敏感型业务流自适应负载均衡算法
过避免拥塞链路，尽可能满足用户对流量传输速率的需求；3)提高网络的健壮性，能够适应网络瞬时的性能下降，降低分组丢失率。算法的设计将确保数据流所选择的路径相对较短且通过拥塞避免能保证链路的最小时延甚至是在链路负载发生变化的时候。最后通过在NS2中进行模拟评估，展示了在真实的网络拓扑和反馈延迟的环境下LARA的性能，证明了该协议更简单、更实用。
综上所述，本文设计的LARA算法协议具备如下特点。
1) 提出基于链路关键度的凸优化问题，将算法分为离线预计算和在线计算2部分，减少数据平面的开销，降低算法复杂度，减轻路由器计算负担。通过对链路权值进行优化，最小化链路时延，保证时延敏感业务端到端的服务质量。
2) 采用并行多路径路由技术，基于反馈路由节点的OSPF扩展域信息，通过凸优化理论求解数据源端最佳的速率分配值，做到自适应调节并行多路径上的速率分配问题，使得链路总时延最小。该协议并不需对当前的路由协议进行太多的修改。
2算法关键技术分析
一个好的路由算法要能适应网络拓扑和流量条件的改变，并且只有在网络发生拥塞时才能充分体现出它的优点。本文提出了基于链路关键度算法，根据最大流?最小割定理，考虑节点对之间最大流流经每条链路的影响，每条链路上可能经过的路由的影响以及链路剩余带宽的影响，使尽可能多的路由均衡地通过网络，并且采用预先计算的方法减少动态路由时的计算复杂度，从而使该算法高效快捷。
2.1关键链路描述
目前的互联网域内路由协议广泛采用的是OSPF、IS-IS等协议，均属于单下一跳路由机制。路由协议仅计算数据源和目的节点之间的最优路径，节点对间的分组信息传输时总是沿最优路径传输，这样会导致网络中不同源目节点对间的最优路径趋于重合。依据这种路由机制所选的最优路径会保持相对的稳定，但是却容易使某些链路被长时间过多占用，形成关键链路。这些关键链路上传输负载过大，导致出现局部网络拥塞。而在这些链路负载过大甚至出现拥塞的同时，其他可用链路却基本闲置。以欧洲的科研教育骨干网Geant[20]为例，其平均链路利用率仅有2%左右，但其网络中关键链路的带宽占用率却高达90%。
在图1所示的简单网络拓扑中，假设节点间链路代价均为1，源目节点对（S1，D1）、（S2，D2）、（S3，D3）根据最短路径优先算法都将选择7-8这段链路，那么7-8链路势必成为关键链路，也越容易发生拥塞。对于节点对（S3，D3），在链路7-8发生拥塞的时候，同样能到达目的的路径5-9-10-6，负载较轻，那么提出的新算法将对这一现象加以改善，通过定义链路的关键度，即关键度高的链路越容易成为关键链路，那么对链路关键度相对较高、剩余容量相对较低的链路提高其惩罚因子，这样使流量能在有效链路之间做到均衡分配。
图1 关键链路
2.2链路关键度定义
设置一个无向连通图G=(V，E)作为网络模型来定义链路关键度。其中V代表网络中所有节点的集合，E代表所有节点之间的链路集合，P表示节点对的集合，图中每个节点都有唯一的标识。s和d 表示图G中的任意两点，其中s, d∈V，(s, d)∈P。
对于给定一个流网络，目标就是最大化网络效用，找出一个具有最大值的流，基于最大流?最小割定理，首先定义链路l的平均期望负载AVE(l)这个概念。定义链路的平均期望负载，即链路的平均每流大小，就是这条链路期望的最大流值，这能反映出一条链路质量的好坏，对于期望值越高的链路，说明链路质量越好，源端都选择这条链路的概率值就大。本文提出的路由协议，由离线预计算和在线计算2个阶段来完成，这样做的好处是减轻路由器的计算开销。对链路关键度的定义是在离线预计算阶段完成。在离线预计算阶段，链路l的平均期望负载AVE(l)就是所有节点对(s, d)之间最大流中通过链路l的流量之和与通过链路l的最大流路径数目m的比值。用公式表示为
(,)
()(,)
l
s d P
AVE l f s d m
∈
=∑(1)
通 信 学 报 第36卷
其中，AVE (l )表示链路l 的平均期望负载，(,)l f s d 表示节点对(s ,d )之间的最大流中通过链路l 的流量，m 表示所有节点对中通过链路l 的最大流路径数目。根据链路的平均期望负载，确定链路的关键度。链路的关键度定义为链路的平均期望负载与链路的容量比值。公式如下
()()l l AVE l C ρ=
(2)
其中，()l ρ表示链路l 的关键度，()C l 表示链路l 的容量。可以看出，链路l 的关键度的值越大，表示链路l 越关键，相应地链路就容易造成堵塞。以图1为例，假设每条链路带宽均为100 Mbit/s ，链路代价均为1，由于源端S 3存在等代价链路，将S 3发送的最大流流量平均分配，经计算，节点对（S 3，D 3）之间所有链路中，链路7-8的关键度值最高83.0)(8-7≈l ρ，其余链路关键度值为0.5，那么链路7-8即为关键链路也是最容易产生拥塞的链路，符合上一节的推断。下面将在算法的在线计算阶段讨论基于链路关键度的链路成本开销计算。 2.3 数据源流量分割
流量分割是指网络中某一个路由节点，对到达相同目的节点的数据分组实现多下一跳链路并行的转发，使网络中各链路的资源利用率趋于均衡，最大程度地降低网络数据传输中的拥塞。采用多路径传输最主要的好处是能够降低端到端延迟并保证更好的传输可靠性。在本文中没有指定数据源是否为边缘路由器或端主机以及新的协议是否只能在域间或者域内进行部署，将分别针对这些不同的场景讨论使用多路径的可行性。
在域内采用多路径路由相对容易完成，因为所有流量的起始节点和目的节点都在一个自治域内，路由器能够计算出K 条最短路径或者通过域内网络管理员在端节点之间设置多隧道。当然，域间的多路径路由也是可以做到的[5,21]，例如在重叠路由中，数据源可以将流量直接路由到某一指定路径上，如果数据源是多宿主的，那么将流量根据业务的不同需求路由到某一上游提供商提供的有效链路上变得更加容易实现。
当源端能够对瞬时低时延链路进行选择的时候，那么针对链路负载的动态流量分割将能提高网络传输性能。另外，这种方式在链路发生故障时，源端可以避免失效链路或由于链路的高关键度而造成拥塞的链路。所以，灵活的流量分割技术能够
在多条不同质量的链路上根据业务需求进行流量配置，很好地做到链路负载均衡。如何在有效的多路径上进行流量分割，将在下一章中重点讨论。
3 核心优化问题定义
目前，将最优化理论应用于网络研究领域已取得了显著的成果。总体上，它在为网络效用最大化
(NUM)[19]，
尤其是对拥塞控制[22]和覆盖网络的优化[23]设计新的分布式协议时发挥了重要作用。本文中，将利用凸优化理论对时延敏感业务流量进行优化。上一节介绍了算法设计的关键技术，本节将确定优化的核心问题，并利用优化分解理论来解决核心优化问题。优化分解技术分为主问题分解和对偶问题分解这2种方法，前者是分解原始的主要问题，而后者利用拉格朗日对偶函数法求解问题，本文将采用后者方法。通过提出优化目标函数以及约束条件，同时能满足是一个凸优化问题，那么其最优解就是数据源端在多路径上的最佳流量分配值，并能够保证端到端路径时延最小化。 3.1 问题的相关定义
上节中已经定义了网络中某一特定的链路l ，以及链路的容量l C 。假设网络能提供多路径路由，并在源目节点对间存在多条有效路径。这里定义路
由矩阵i H ，其中i 代表源目节点对，i
lj H 表示节点对i 选择的路径j 中某条链路l 。如果流量流经链路
l ，则1i lj
H =，否则0i lj H =。路由矩阵H 没有必要代表物理拓扑中所有可能的路径，但是却可以代表
由网络管理员挑选出来的路径。
由于每个源目节点对之间可以将流量在多条有效路径上进行分配，用符号i j r 表示连接源目节点对i 的路径j 上分配速率，用符号()l Hr 表示链路l 的总负载，用i R 表示每个源目节点对i 之间的流量需求。观察到，对于视频流的带宽需求在10~30 s 的间隔内是恒定不变的，所以在本文中假设i R 是恒定比特率，但同时必须认识到在这段时间间隔之间，由于视频压缩速率的变化，带宽的需求还是有变化的，在后面的实验中会反映出这一点。 3.2 核心优化问题
本文的优化目标是最小化端到端的网络延迟。换句话说，需要优化的目标是在网络中保证分配在有效多路径上的所有时延敏感型数据流其端到端的时延最小化，同时也需要数据源需求流量恒定来
第3期 杨洋等：IP 网络时延敏感型业务流自适应负载均衡算法
确保满足优化的一定条件，以及链路的实际负载不能超过链路的带宽容量等约束条件。
在本文第2节中，为了减轻路由器的计算负担，针对路由算法的设计提出了离线预计算和在线计算2个阶段。在离线阶段主要完成链路关键度值的计算。目前的路由协议中，最常用的就是定义链路容量或可用带宽的倒数作为链路的边权值。例如，某一刻，一条链路剩余带宽较大，按照以前定义的倒数权值关系，那么权值相对较小，越容易吸引流量，但是如果这是一条关键度值很高的链路，根据第2节定义AVE 的物理意义，在下一刻这条链路是容易产生拥塞的，给它分配过多的流量并不一定合适。如果将这条链路的关键度值作为剩余带宽倒数的修正因子，权值就不一定小了。所以，为了更好地刻画链路的实时状态，将离线阶段得到的链路关键度值与该链路可用带宽相比，其值能很好地反映出链路的动态特性，提高算法的准确性。在线计算阶段，可以获取链路的可用带宽'
l C 。根据式(1)、式(2)以及链路的可用带宽，定义链路的成本开销为链路的关键度与链路的可用带宽的比值。公式如下
()
()l l cost l C ρ=
′
(3)
其中，cost (l )表示链路l 的开销。式(3)将链路关键
度与该链路可用带宽的比值定义为链路的成本，相当于惩罚因子，那些高关键度、低可用带宽的链路就是本文要进行拥塞避免的链路，可以将一部分流量引导至相对值较低的有效链路上，保证端到端的低时延。根据这个设计思路，最终提出
的优化目标函数为()i i l
j lj i j l l f r r H C ρ=′
∑∑∑，即
Mininize i i
l
j lj
i j l l r H C ρ′
∑∑∑，其中，r 为变量。优化
目标函数的提出将伴随着一定的约束条件，首先链路的负载不能超过链路的承载能力，即()l l Hr C ≤；其次要确保分配在每一个源目节点对i 流量的总和等于用户需求流量，即
i
j i j
r R =∑
，其中i R 应为常量；最后是链路流量分配的非负取值约束，即0r ≥ 。
对于约束条件
i j i j
r R =∑
，这里假设R i 是常量。首先，在前文中提到大部分视频流的带宽需求
在10~30 s 的间隔内是恒定不变的，也符合本文的
假设条件，如果时间间隔外需求流量发生改变，那么算法将重新计算并收敛得到最优解；其次，如果R i 是变量，那么优化问题必将引入流量矩阵，将使算法的复杂度增加，加重路由计算的负担。基于以上原因，本文中定义R i 为常量。 3.3 凸优化证明
为了使本文提出的优化目标函数有唯一解，那么需要证明提出的核心优化问题是凸函数。对于不等式约束条件 (),l l Hr C l ?≤ (4) 因为是线性的，所以是凸函数。同样对于等式约束条件
,i
j
i j r R i =?∑
(5) 是仿射函数，所以只需要证明优化目标函数
i i
l
j lj i j l l r H C ρ′
∑∑∑ (6)
是凸函数即可。由于目标函数是线性函数，根据凸函数性质可以证明式(6)是凸函数。 3.4 优化问题分解
首先将提出的核心优化问题利用拉格朗日对偶法重新定义为
(,,)(()
)()
i i l
j lj i j l l
i l
l
l i i j l
i j L r r H C Hr C R r ρβδβδ=+
′?+?∑∑∑∑∑∑ (7)
式中引入2个新的对偶变量l β和i δ，它们也叫拉格朗日乘子，分别关联着链路的不等式约束条件以及数据源端的等式约束条件。这2个对偶变量的引入可以认为是当流量分配背离约束条件时的惩罚代价。在分布式算法中，这种惩罚性的代价值可以在节点路由器上通过次梯度方法计算得到，并可以将计算得到的代价值反馈给数据流源端。
上一节中已经证明了本文提出的优化问题属于凸优化，且满足利用KKT(karush-kuhn-tucker)条件来找到多路径上最优的流量分配速率，即i j r 的最优解，KKT 条件是拉格朗日乘子法的推广。算法中，假设在t 时刻，源端i 获得来自不同链路的代价值()l t β，根据不同链路的代价相应地分别计算源端各自发送速率的代价值i δ。即在满足KKT 条件下，通过拉格朗日对偶法分解得到链路分配的最优速率*()i j r t 应满足式(8)，即满足式(8)的解为最优解。
通 信 学 报 第36卷
((,,))0i
j L r r βδ?
=? (8)
将式（7）整理如下
(,,)(()
)()
i i
l
j lj
i j l l i l
l
l i i j l
i j L r r H C Hr C R r ρβδβδ=+
′
?+?∑∑∑∑∑∑
{(
)}i i
l
j lj l i l l i i i j l l i l r H C R C ρβδβδ=+??+′
∑∑∑∑∑ 则由初始问题通过拉格朗日变化得到函数(,,)L r βδ，那么其基于变量r 上的对偶目标函数(,)D βδ则可以定义为
(,)inf (,,)r D L r βδβδ=
(9)
可以证明初始目标函数和对偶目标函数对于任意的可行解r 和(,)βδ都满足()(,)f r D βδ≥，那么当原始优化问题在最优解处得到下限值f *的时候，其对偶函数将获得最大值。其对偶形式为 ,max (,)D βδβδ
s.t. 0l β≥ (10)
可知即使初始目标函数不是凸函数，式(10)也
是凸优化问题[19]。将式(9)通过变形得到 (,)inf (,,)r D L r βδβδ=
{(
)}i i
l
j lj l i l l i i i j l l i l r H C R C ρβδβδ=+??+′
∑∑∑∑∑ ()l l i i l i A r C R βδ=?+∑∑
(11)
其中，
()min {()}i i l j
lj
l i i j l l A r r H C ρ
βδ=+?′
∑∑
∑
通过初始问题的对偶形式可以看到，对偶问题的目标函数(,)D βδ被分解为独立的子问题A (r )、
l
l
l
C
β∑和i i i R δ∑。这就表明通过求解对偶问题，
各源端只需要知道局部信息，而不需要知道全局信息，这样就可以通过分布式算法来设计新的协议。
由于式(10)属于凸优化问题，则对偶目标函数(,)D βδ属于凸函数，其导数存在。对代表链路代价的变量求偏导数为
()i i
l l lj j l i j D Hr C H r C β?=?=??∑∑
利用次梯度算法可以得到反馈回来的链路代价更新算法 (1)[()()]i i l l l lj j l t t C H r βββε+
+=??∑
(12)
其中，βε是迭代步长，每一条链路上l β的更新是由链路负载和链路容量之间的差异而决定的。如果源端对链路l 的带宽需求超过了链路的自身的带宽，
例如链路发生拥塞，只有在这种情况下表达式[
]
+
代表正值，相当于提高链路代价；否则就降低链路代价。
同样通过求解变量δ的偏导数，再利用次梯度算法可以得到数据源端的发送代价
(1)[()()]i i i j i j t t r R δδδε++=??∑
(13)
根据式(11)中的A (r )可以获得源端i 在路径j 上的速率表达式，同样在对偶的目标函数中对变量r 求偏导数为
()i l
lj l i l l D H r C ρβδ?=+?′?∑
那么为了选择一个目标函数值下降最快的方
向以利于尽快达到极小值点，利用最速下降法得到源端速率的更新算法为
(1)()[()]i i i l
j j r i lj l l l r t r t H C ρεδβ+=+?+′
∑ (14)
当(
)]i
l
i lj l l l H C ρδβ=+′
∑时，
源端i 在路径j 上的速率则不需要更新。式(12)~式(14)中，βε、δε、r ε分别是在迭代的t 时刻定义的迭代步长。如果逐步减小步长值，例如当t →∞时0ε→，分布式算法的目标函数将收敛于全局目标函数。
4 分布式多路径协议设计
上节中，提出了优化问题的目标函数，并利用拉格朗日对偶函数法求解该优化问题，对偶问题的目标函数(,)D βδ分解为独立的子问题A (r )、
l
l
l
C β∑和i i
i R δ∑。这就表明通过求解对偶问题，
各数据源端只需要知道局部信息，而不需要知道全局信息，这样就可以通过分布式算法来设计新的协议，最终利用最优化理论与数学方法得到式(12)~式(14)。本节将利用上一节得到的可调参数以及数据源端速率的更新算法，同时根据网络实际运行情况对链路负载进行合理地替换，最终转换成一个实际的算法协议，即基于链路关键度的自适应负载均衡路由算法(LARA ，load adaptive routing algorithm)，使其能够收敛于目标函数的最
第3期 杨洋等：IP 网络时延敏感型业务流自适应负载均衡算法
优解，并使LARA 能够在路由器和数据源端部署运行。
路由器在网络中能做到监控与其连接的链路性能，计算链路代价以及将计算的代价反馈回数据源端。路由器更新链路代价是在粒度为T 的时间间隔内迭代更新的，那么在这个时间间隔内到达链路l 的比特数B T 作为该时刻链路的负载并与该链路的
容量进行比较，即式(12)中链路负载i i
lj j l H r ∑由T
B T
替换。
数据源端是根据路由器反馈的链路代价信息进行链路分配速率的调整，值得注意的是源端收到的路由器反馈信息是有延迟的。例如，源端i 收到来自路径j 的代价反馈信息是伴随着往返时间延迟，即一个i j RTT 周期。因此，让源端i 更新所有的路径发送速率是以这些路径中RTT 值最长的作为更新触发时刻，即max(),i i j T RTT j =?。最终结合式(12)~式(14)得到分布式算法协议，如算法1所示。
算法1 LARA
//采样时刻t =1,2,3,….,每条链路
1) 接收网络中经过链路l 的各源端发送速率i j r //,i P j E ∈∈
2) 更新反馈链路代价：
()[()()]i i l l l lj j l t T t C H r βββε+
+=??∑ //βε为
反馈链路代价步长，i i
T
lj
j l B H r T
=∑ 3) 将新的链路代价值传给数据源端
4) 计算数据源端i 的需求代价：
()[()()]i i i i j i j t T t r R δδδε++=??∑ //δε为
源端需求代价步长
5) 数据源端i 在路径j 上分配速率更新计算：
'()()[()]i i i
j i j r i lj l l l l r t T r t H C εδρβ+=+?+∑ //r ε为迭代步长，max()i i j T RTT =
在算法1中，将使βε、δε、r ε步长参数之间相互独立，减少关联性。LARA 中要强调实现步长的递减是不切实际的，因为无论何时一条新的数据流进入网络或者随着一条数据流的离开，步长参数都会增加，所以将选择一个恒定的步长参数来简化协议，但需要寻找到合适的步长值。同时要注意到，如果步长值选取太大，其解决方案可能最终离最优值相差较多，而如果选取太小，则协议的收敛速度
会变得非常缓慢。在下一节仿真实验中将对步长值
的选取做进一步讨论。
5 仿真与评估
仿真实验的目标是能够展示出所设计协议的性能以及它的动态特性。本文利用NS2仿真模拟器在基于真实的网络拓扑上进行仿真。首先，介绍仿真中使用的网络拓扑以及具体NS2参数的设置；其次，将选择设置协议中的步长参数并讨论其设置的合理性；最后，通过与ECMP 比较结果展示LARA 设计的优点。在实验过程中，曾对美国Internet2骨干网Abilene 进行拓扑仿真（共20个主节点，30条链路），因为其拓扑结构较为简单，满足实验条件链路较好遴选，实验结果完全符合预期。同样，还从CAIDA 网站获取真实的AS 拓扑数据生成较为复杂的拓扑（随机选取50个AS 节点，生成100条链路），依然取得较好的实验结果，说明本协议是能适应较大规模网络部署的。因篇幅有限，本文选择更接近实际生活的CERNET2主干网进行实验仿真。
5.1 NS2仿真及拓扑
分布式路由协议的研究需要大规模网络拓扑环境的评估和验证，但是受资源、技术条件和场地等因素限制，往往很难在实际的网络系统中完成LARA 的验证和测试工作。NS2仿真器具有强大的数据处理功能，可扩展性强，执行效率高，且仿真结果的可靠性高，本文将用NS2对提出的LARA 协议进行仿真评估。仿真的拓扑图是基于第二代中国教育和科研计算机网CERNET2骨干网，其覆盖中国几十个主要城市，其拓扑结构包括25个主节点(其中20个城市节点)和28条链路。如图2所示。
图中路由器代表20个城市节点，连接这25个主节点的链路为28条。其中，粗实线代表链路带宽为10 Gbit/s ，细实线为2.5 Gbit/s 。实际模拟中，将整个CERNET2视为一个AS ，遴选PoP (point of presence)的原则是：1)每个PoP 对至少包含一条主干链路，即图2中代表10 Gbit/s 链路的粗实线；2)每个PoP 对之间都有多于一条的备选路径，并具备相同路径开销。基于上述原则，选择4对源目节点对作为PoP ，其主节点分别是沈阳到南京、北京大学到广州、北京邮电大学到重庆、兰州到长沙，其局部拓扑如图3所示。
通信学报第36卷
图3 CERNET2局部网络拓扑
根据实际链路的带宽、时延，以及时延与带宽的反比关系，图中链路上的值即为链路的代价值，例如节点1和2之间链路带宽代表原拓扑图中2.5 Gbit/s链路，节点2和4之间链路带宽代表原拓扑图中10 Gbit/s链路。实际仿真中，首先，设定100 Mbit/s链路容量代表实际10 Gbit/s链路，25 Mbit/s链路容量代表实际2.5 Gbit/s链路，严格满足实际链路的带宽以及开销的比例关系；其次，将在源目节点对之间选择使用TCP与UDP协议混合的传输模式，因为UDP协议通信开销较小，所以目前大部分对时延要求较高，而对可靠性要求不高的应用，例如视频点播等，都采用UDP协议进行通信。
LARA还涉及到链路剩余带宽的信息获取，知道
在一个运行OSPF协议的自治域内，每个路由器都维护有路由信息数据库，路由表中的每一条记录都包含有链路的当前状态，OSPF的所有LSA(链路状态广播)都包含有Option域字节，那么链路剩余带宽信息可以通过对Option域中ToS(type of service)域的扩展[17]得到，并经过周期性的链路通告广播出去。
5.2步长参数选取
LARA中涉及到3个步长参数的选择，即
β
ε、
δ
ε、r
ε分别代表反馈链路代价步长、源端需求代价步长以及源端在路径j上分配速率迭代步长。在前文中提到如果步长值选取太大，其最终解可能离最优值相差较多，而如果选取太小，则协议的收敛速度会变得非常缓慢。利用Matlab仿真工具对步长值进行选取，其好处是能快速的遍历所设置的参数空间，并进行结果
的比对。以反馈链路代价步长
β
ε为例，假定一条链路带宽分别为10 Mbit/s、100 Mbit/s和1 000 Mbit/s，通过实验结果发现链路带宽越小，所需步长值相对与高带宽链路步长值越大，最终可以得到反馈链路代价步
长1
l
C
β
ε≈，即步长值与该链路带宽成反比关系，
用图2 CERNET2网络拓扑
第3期 杨洋等：IP 网络时延敏感型业务流自适应负载均衡算法
同样的方法可以确定源端需求代价步长近似满足0.5i R δε≈的关系。在获取更新后的反馈链路代价以及源端需求速率更新代价值之后，最终需要确定源端在路径j 上分配速率迭代步长r ε。对r ε步长值的选取，假设速率的随机初始值在[0,10] Mbit/s 之间均匀选取10个，选取的每一个迭代步长值的迭代次数值都是10次计算平均的结果。在仿真实验中，考虑到某些初值选取会影响算法的收敛速度，实际操作时如果算法的迭代次数超过200则直接让算法迭代过程终止退出，最后得到510r ε?≈比较合适。至此LARA 所需步长值均得到确认。步长参数值的最终确认是经过对不同的拓扑仿真（Abilene 、CAIDA ），并经过多次实验得到，具有普适性。 5.3 性能比较
由于目前关于多路径路由协议的研究成果大部分都没有实际的部署，为了客观地评估性能，利用NS2仿真模拟器在基于CERNET2真实的网络拓扑上，将LARA 与目前在网络中普遍部署的路由算法ECMP 进行比较。在实际部署ECMP 的网络中，数据源节点通过测量获取到所有能到达目的节点的最短路径，即这些路径的开销值都是相同的，那么数据源端可以将流量平均的分割到这些路径上进行传输，这即是ECMP 的基本原理。
在实验中，将4个节点对流量需求以5 Mbit/s 的迭代步长从5 Mbit/s 增加到70 Mbit/s 来观察目的节点平均产生的时延、分组丢失率以及吞吐量。同时，为了更真实模拟实际场景，通过配置NS2随机数产生器，使每个数据源端在0~1 s 内由产生的随机数决定数据流开始传送的时刻。首先观察LARA 平均传播时延的表现，实验结果如图4所示。发现当源端发送速率在5 Mbit/s 至11 Mbit/s 之间时，ECMP 与LARA 时延表现相当，说明这一阶段网络链路状态良好，无拥塞链路出现。当源端发送速率超过12 Mbit/s 时，ECMP 时延开始增大；当发送速率在35 Mbit/s 到60 Mbit/s 之间，时延产生较大抖动，网络性能开始下降，发送速率在41 Mbit/s 时，延时出现峰值。实验现象符合预期，这是ECMP 本身的设计所不能避免的结果，因为当链路负载增加到一定值，数据分组传输路径上开始出现拥塞链路，由于ECMP 的算法并不能将数据流切换到链路负载较轻，且未发生拥塞的路径上，从而使分组丢失率开始增加，网络性能下降，这样对于视频服务来说已经开始影响
到用户体验，ECMP 路由使数据分组交付时延增大，已不能满足用户对源端提供服务的需求。相比之下，LARA 则能将时延控制在有效范围内，总体平稳无抖动产生，能体现出LARA 的优越性。
图4 时延比较
LARA 分组丢失率的测试是在同一实验环境下进行测量，如图5所示。当源端发送速率低于5 Mbit/s 时，ECMP 和LARA 均无分组丢失产生；当发送速率在5 Mbit/s 至35 Mbit/s 之间时，ECMP 控制分组丢失率总体上优于LARA ，但是当发送速率大于35 Mbit/s 时，LARA 部署下的分组丢失率开始明显下降，而ECMP 部署下的分组丢失率开始增加，并在51 Mbit/s 时刻，分组丢失率达到峰值。在对时延的测试中，当发送速率在35 Mbit/s 到60 Mbit/s 之间，ECMP 部署下的时延产生较大抖动，网络性能开始下降，其原因是随着负载增大，链路出现拥塞时，分组丢失率开始增加，当数据源端进入TCP 拥塞避免时，分组丢失率开始下降，如此反复是造成ECMP 实验结果波动的原因，这也是ECMP 机制所无法避免的。这一现象与本次分组丢失率测试结果相一致，即在网络时延增大的情况下，分组丢失率也相应增大。由此可以得出：LARA 的网络部署在链路高负载的情况下能显示出对ECMP 部署的优越性。
图5 分组丢失率比较
通信学报第36卷
同时，对网络吞吐量进行了比较测试，实验结果如图6所示。当源端发送速率在5 Mbit/s至11 Mbit/s之间时，ECMP与LARA吞吐量表现相当，增长迅速，说明期间并无拥塞链路产生；当发送速率大于12 Mbit/s时，网络开始出现拥塞链路，ECMP 吞吐量回落迅速，LARA则表现较平稳。实验结果表明，当节点路由器使用LARA进行部署时，与使用ECMP部署时相比，网络吞吐量明显增加，进一步验证了LARA的优越性。
图6 吞吐量比较
从以上的实验结果可以得出结论：当网络链路处于低负载、无拥塞产生时，LARA与ECMP性能表现相当，传播时延较低；当链路负载增加并有拥塞产生时，LARA能够使源端动态调整不同链路的发送速率，将部分流量引导至链路负载相对较低、链路质量较好且无拥塞产生的链路上去，保证端到端的时延控制在有效的范围之内，能够很好地进行链路负载均衡。
6结束语
本文的主要目标是针对时延敏感型的业务流，例如在线视频等，为确保基于该业务的端到端时延控制在有效范围之内，而开发一个新的协议将更好满足这些对时延敏感的应用程序的需求。观察到这些应用程序在网络性能瞬时下降时将受益于链路较低的时延以及更好的健壮性，考虑到这些目标，利用优化论设计了一个新的路由算法协议LARA。
LARA利用凸优化理论，通过提出优化目标函数，将流量在多个有效路径上进行分割，确保关键链路不会成为产生拥塞的瓶颈路径。然后用优化分解的方法将优化问题转化为一个具有3个可调参数的分布式算法和实用协议。通过利用NS2仿真器在基于实际的CERNET2网络拓扑上模拟LARA的运行，验证了LARA在低时延和健壮性方面的优越表现。
LARA在低时延和健壮性方面的优越表现是通过与目前在网络中普遍部署的ECMP路由策略进行比较并得出的结论，即在网络的关键路径产生拥塞之前，LARA能够将部分流量引导至链路负载相对较低、链路质量较好且无拥塞产生的链路上，保证了端到端的时延，避免了关键链路拥塞的发生，同时在链路高负载的情况下能保证链路的低分组丢失率，提高网络的吞吐量。
在下一步的工作中针对本文提出的LARA还有2个可能的扩展工作可以做，首先在LARA中假设用户对服务提供商即源端的需求是常量，但是在实际情况下，需求量可能随时都会变化，而不是在一定时间间隔内是恒定的，因而可以进一步改进本文的协议；其次，LARA可以与互联网经济学融合，由于协议中对链路反馈的代价消息十分敏感，对于低开销链路将会吸引更多的流量，尤其对于域间的跨网络部署，因为ISP之间存在市场竞争关系而通告虚假路径信息或者出于安全和隐私保护的目的不通告实际可达路由，那么如何让ISP提供诚实的路径信息以及如何通过激励机制使ISP提供更多的可达路由，都是下一步研究的重点。
参考文献：
[1] Chinese netizens network video application research report in
2013[EB/OL].https://www.wendangku.net/doc/108563053.html,/hlwfzyj/hlwxzbg/spbg/201406/t 20140609_47180.htm.
[2] Cisco visual networking index: forecast and methodology[EB/OL].
https://www.wendangku.net/doc/108563053.html,/c/en/us/solutions/collateral/service-provider/ip-
ngn-ip-next-generation-network/white_paper_c11-481360.html.
[3] VOGEL A, KERHERVE B, et al. Distributed multimedia and QoS: a
survey[J]. IEEE Multi-Media, 1995, 2(2): 10-19.
[4] XIAO X, NI L M. Internet QoS: a big picture[J]. IEEE Network,
1999,13(2):8-18.
[5] HE J, REXFORD J. Towards Internet-wide multipath routing[J]. IEEE
Network Magazine, Special Issue on Internet Scalability, 2008, 22(2): 16-21
[6] KELLY F, VOICE T. Stability of end-to-end algorithms for joint rout-
ing and rate control[J]. ACM SIGCOMM Computer Communication Review, 2005,35(2):5-12.
[7] XU W, REXFORD J. MIRO: Multi-path interdomain routing[J]. ACM
SIGCOMM Computer Communication Review, 2006,36(4):171-182. [8] DAMON W, COSTIN R, ADAM G, et al. Design, implementation and
evaluation of congestion control for multipath TCP[A]. Proc of the 8th USENIX Conference[C]. 2011. 99-112.
第3期杨洋等：IP网络时延敏感型业务流自适应负载均衡算法
[9] SUCHARA M, XU D H, DOVERSPIKE R, et al. Network architec-
ture for joint failure recovery and traffic engineering[J]. ACM SIG-METRICS Performance Evaluation Review, 2011,39(1):97-108. [10] NGUYEN G T K, AGARWAL R, LIU J D, et al. Slick packets[J].
Performance Evaluation Review, 2011,39(1): 205-216.
[11] SUCHARA M, FABRIKANT A, REXFORD J. BGP safety with spu-
rious updates[A]. IEEE INFOCOM[C]. 2011.2966-2974.
[12] HOPPS C. Analysis of an Equal-Cost Multi-Path Algorithm[S]. RFC
2992, 2002.
[13] ZLA TOKRILOV H, LEVY H. Packet dispersion and the quality of voice
over IP applications in IP networks[A]. IEEE INFOCOM[C]. 2004.
1170-1180.
[14] GALLAGER R. A minimum delay routing algorithm using distributed
computation[J]. IEEE Transactions on Communications, 1977,25(1): 73-85.
[15] BERTSEKAS D, GAFNI E, GALLAGER R. Second derivative algo-
rithms for minimum delay distributed routing in networks[J]. IEEE Transaction Communications, 1984,32(8):911-919.
[16] JA VED U, SUCHARA M, HE J Y,et al. Multipath protocol for de-
lay-sensitive traffic[A]. Proc of the First International Conference of Communication Systems and Networks[C].2009.
[17] APOSTOLOPOULOS G，WILLIAMS D. QoS Routing Mechanism
and OSPF Extensions[S]. RFC 2676, 1999.
[18] KODIALAM M, LAKSHMAN T V. Minimum interference routing
with applications to MPLS traffic engineering[A]. IEEE INFO-COM[C]. 2000.884-893.
[19] PALOMAR D, CHIANG M. A tutorial on decomposition methods for
network utility maximization[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(8):1439-1451.
[20] UHLIG S, QUOITIN B, LEPROPRE J, et al. providing public intra-
domain traffic matrices to the research community[J]. ACM SIG-COMM Computer Communication Review, 2006, 36(1):83-86. [21] HE J, SUCHARA M, BRESLER M. Rethinking Internet traffic man-
agement: from multiple decompositions to a practical protocol[A].
Proc of the ACM CoNEXT[C]. 2007.17.
[22] WEI X D, CHENG J, LOW H S, et al. FAST TCP: motivation, archi-
tecture, algorithms, performance[J]. Networking, IEEE/ACM Transac-tions on, 2006,14(6):1246-1259.
[23] KURIAN J, SARAC K. A survey on the design, applications, and
enhancements of application-layer overlay networks[J]. ACM Com-puting Surveys, 2010, 43(1):5. 作者简介：
杨洋（1980-），男，江苏无锡人，清
华大学博士生、主要研究方向为计算机网
络、路由协议、流量工程等。
王于丁（1984-），男，河北石家庄人，
清华大学博士生，主要研究方向为计算机
网络、云计算等。
李晨曦（1991-），男，湖北武汉人，
清华大学博士生，主要研究方向为网络安
全、异常检测等。
王会（1977-），女，河南南阳人，博
士，清华大学副研究员，主要研究方向为
互联网路由、流量工程等。
杨家海（1966-），男，浙江云和人，
清华大学网络运行与管理技术研究室主
任、教授、博士生导师，主要研究方向为
计算机网络、网络管理与测量、网络安全、
云计算与大数据等。
网络流算法
网络流算法 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 ［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 一、基本概念及相关定理 1)网络与网络流 定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点， 对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 2)可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： 定义2 满足下列条件 (1)容量约束：0≤fij≤cij，(vi,vj)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 3)可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
网络最大流问题概论
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从 到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。 可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。 注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧； 收点是指只有弧指向，而没有从它的发出去的弧。
从一道题目的解法试谈网络流的构造与算法Word版
从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。
2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例
网络流模型总结
网络流模型总结 福州一中肖汉骏【引言】： “许多问题可以先转化为网络流问题，再运用最大流算法加以解决。而发现问题本质，根据最大流算法的特点，设计与之相配的数学模型是运用最大流算法解决问题的重要步骤。” “网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。” 注：本文大部分出自江涛老师讲稿及网络资料
图1.1 【理论部分】： 一、引入 如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。 一个实例：运输网络 参看下图，给定一个有向图G=(V ,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s 和汇点t ，现在假设在s 处有一个水源，t 处有一个蓄水池，问从s 到t 的最大水流量是多少，类似于这类的问题都可归结为网络流问题。 在流网络中，每条有向边可以被看导管。每根导管有一个固定的容量，代表物质流经这个导管的最大速率，例如一个管道每小时最多能流过200加仑液体或者一根电线最多能承载20安培的电流。流网络中的顶点可以看作是导管的连接处。除了源点和汇点之外，物质流进每个点的速率必须等于流出这个点的速率。如果我们把研究的物质特化为电流，这种“流的保持”属性就好像电路中的基尔霍夫电流定律一样。
二、网络流相关定义1 网络定义： 一个有向图 G=(V ，E)； 有两个特别的点：源点s 、汇点t ； 图中每条边(u,v)∈E ，有一个非负值的容量C(u,v) 记为 G=(V ，E ，C)，网络三要素：点、边、容量 可行流定义： 是网络G 上的一个“流”，即每条边上有个“流量”P(u,v)，要满足下面两个条件： 流的容量限制——弧： ),(),(0v u C v u P ≤≤ 对任意弧(u,v)---有向边 流的平衡限制——点： 除源点和汇点，对任意中间点有：流入u 的“流量”与流出u 的“流量”相等。即： {,}(,)(,)0x V x V u V s t P x u P u x ∈∈?∈--=∑∑有 网络的割： 一个s-t 割是这样一个边的集合，把这些边从网络中删除之后，s 到t 就不可达了。或者，正式的说，一个割把顶点集合分成A,B 两个集合，其中s 在A 中,t 在B 中，而割中的边就是所有从A 出发，到达B 的所有边。 割的容量就是割中所有边的容量的和。正式的说，就是所有从A 到B 的边的容量的和。 网络的流量： 源点的净流出“流量” 或 汇点的净流入“流量”。即： ∑∑∑∑∈∈∈∈-=-V x V x V x V x x t P t x P s x P x s P ),(),(),(),( 注意，我们这里说的流量是一种速率，而不是指总量。联系上面所说的实例，下面是一个流量为1的可行流：
网络流算法讲座材料
网络流常用算法： 1.Fort_Fulkerson算法. 2.Edmonds_Karp算法(最短增广路算法).-------------------O( n*m^2 ) 3.SAP算法(使用距离标号的最短增广路算法).--------------O( n^2*m ) 4.Dinic算法.------------------------------------------O( n^2*m ) 5.Push_Relabel算法(预流推进算法).---------------------O( n^2*m ) 6.FIFO Preflow_Push算法.-------------------------------O( n^2*m) 7.Relabel_to_Front算法.--------------------------------O( n^3 ) 8.Highest Label Preflow_push算法.----------------------O( n^2*m^1/2) 网络流算法讲座材料 1 概念与性质 网络N是指具有以下结构的有向图D，D中有两个称为源和汇的不同顶点s, t，在D的弧集E上定义了非负整数值函数c。 网络N的流是定义在弧集E上的整数值函数，满足对任意边a， 0<=f(a)<=c(a)，且对任意顶点，入流量等于出流量。 性质1：任何st-流都具有如下性质：从s的出流量等于到t的入流量。 性质2：任何st-流都有一个最大流，它可以表示为从s到t，至多E条有向路径集合上的流。 图的切割是将顶点分成两个独立的集合，交叉边是一条连通两个集合中顶点的边，交叉边的集合叫做切割集合。 网络N的st-切割是这样的一个切割，它将源s放到一个集合，将汇t放到另一个集合。与st-切割对应的每条交叉边或者是st-边(从集合s指向集合t)，或者是ts-边(从集合t指向集合s)，st-切割的容量是st-边的容量之和，st-切割的流量等于st-边上的流量和与ts-边上的流量和之差。 性质3：网络中所有st-流的最大值等于所有st-切割的最小容量。 残余网络 边费用是定义在边集E上的整数值函数h。流的费用是该流的所有边的流值与边费用乘积的总和。 最小费用最大流是费用最小的最大流。 性质4：当且仅当残余网络不包含负开销的有向环时，最大流才是一个最小费用流。 2 最大流应用 2.1 一般网络的最大流 描述：给定一个含多个源和多个汇的网络，找出其中的最大流。 解法：在原网络的基础上，增加一个虚源s和一个虚汇t。若原网络有p个源s1, s2, …, sp和q个汇t1, t2, …, tq，则在原网络中增加p条以s为起
网络流题目集锦
(2010-02-07 18:00:40) 转载 分类：ACM 标签： 杂谈 最大流 POJ 1273 Drainage Ditches POJ 1274 The Perfect Stall (二分图匹配) POJ 1698 Alice's Chance POJ 1459 Power Network POJ 2112 Optimal Milking (二分) POJ 2455 Secret Milking Machine (二分) POJ 3189 Steady Cow Assignment (枚举) POJ 1637 Sightseeing tour (混合图欧拉回路) POJ 3498 March of the Penguins (枚举汇点) POJ 1087 A Plug for UNIX POJ 1149 Pigs (构图题) ZOJ 2760 How Many Shortest Path (边不相交最短路的条数) POJ 2391 Ombrophobic Bovines (必须拆点，否则有BUG) WHU 1124 Football Coach (构图题) SGU 326 Perspective (构图题，类似于 WHU 1124) UVa 563 Crimewave UVa 820 Internet Bandwidth POJ 3281 Dining (构图题) POJ 3436 ACM Computer Factory POJ 2289 Jamie's Contact Groups (二分) SGU 438 The Glorious Karlutka River =) (按时间拆点) SGU 242 Student's Morning (输出一组解) SGU 185 Two shortest (Dijkstra 预处理，两次增广，必须用邻接阵实现，否则 MLE) HOJ 2816 Power Line POJ 2699 The Maximum Number of Strong Kings (枚举+构图)
浅谈网络流算法与几种模型转换
浅谈网络流算法与几种流模型 吴迪1314010425 摘要：最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。s-t的最大流等于s-t的最小割，最大流最小割定理。网络流在计算机程序设计上有着重要的地位。 关键词：网络流Edmonds-Karp 最大流 dinic 最大流最小割网络流模型最小费用最大流 正文： 图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C），其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1 表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。 最大流理论是由福特和富尔克森于 1956 年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。 先来看一个实例。 现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下： 每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？ 这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。 若有向图G=(V,E)满足下列条件： 1、有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。 2、有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。 3、每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。 则称之为网络流图，记为G = (V, E, C) 介绍完最大流问题后，下面介绍求解最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。 三个基本的性质: 如果C代表每条边的容量F代表每条边的流量 一个显然的实事是F小于等于C 不然水管子就爆了 这就是网络流的第一条性质容量限制(Ca pacity Constraints):F
网络最大流问题算法研究【开题报告】
开题报告 数学与应用数学 网络最大流问题算法研究 一、综述本课题国内外研究动态, 说明选题的依据和意义 最大流问题是指在一定的条件下, 要求流过网络的物流、能量流、信息流等流量为最大的问题[2]. 最大流问题已有50多年的研究历史, 这段时期内, 人们建立了最大流问题较 为完善的理论, 同时开发了大量优秀的算法. 如Ford 和Fulkerson 增截轨算法 [3]、Dinic 阻塞流算法、Goldberg 推进和重标号算法[6]以及Goldberg 和Rao 的二分长度阻塞流算法等等, 这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用. 近年来, 随着计算机科学技术和网络的快速发展, 网络最大流问题得到了更深入的研究, 并极大地推动了最大流问题的研究进展. 然而, 研究工作仍未结束: 首先, 在理论算法研究方面, 人们还没有发现最大流问题算法时间复杂度的精确下界, 更没有任何一个通用算法达到或接近问题的下界; 其次, 在算法的实际性能方面, 目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决, 发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决. 因此, 关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig 提出的网络单纯刑法和Ford 和Fulkerson 的增载轨算法, 他们都是伪多项式时间算法, 分别由Dinic, Edmonds 和Karp 等提出. 1973年Dinic 首次获得了时间复杂度的核心因子为nm 算法. 以后的几十年中, 最大流算法获得了很大的进展. 在最大流问题中, ()nm O 时间界是一个自然的障碍. 如果我们把一个流沿从源到汇的各个路径进行分解, 根据流分解定理, 这些包含流的路径的总长度为()nm Θ.因此, 对每次利用一条曾接轨的算法, ()nm O 时间是这类算法的下界. 尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的, 但在很长一段时间内, ()nm O 的
网络最大流问题算法研究【文献综述】
文献综述 数学与应用数学 网络最大流问题算法研究 最大流问题是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题[2].最大流问题已有50多年的研究历史,这段时期内,人们建立了最大流问题较为完善的理论,同时开发了大量的算法.如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法[6]以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用.近年来,随着计算机科学技术和网络的快速发展,网络最大流问题得到了更深入的研究,并极大地推动了最大流问题的研究进展.然而,研究工作仍未结束:首先,在理论算法研究方面,人们还没有发现最大流问题算法时间复杂度的精确下界,更没有任何一个通用算法达到或接近问题的下界; 其次,在算法的实际性能方面,目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决,发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决.因此,关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig[6]提出的网络单纯刑法和Ford和Fulkerson的增载轨算法, 他们都是伪多项式时间算法,分别由Dinic、Edmonds和Karp等提出.1973年Dinic首 次获得了时间复杂度的核心因子为nm算法.以后的几十年中,最大流算法获得了很 大的进展. 本文主要介绍的是网络最大流的几种主要算法,其中重点介绍了标号算法的详细 过程,其后给出了其在实际中的应用实例,后面介绍了现有的几种主要算法,虽然没 有给出具体的程序,但本文目的主要是了解最大流问题的解决思想,读者对网络流算 法有更深刻的认识,读者要想了解更多关于最大流问题的研究,详细可以参照Goldberg等人的研究成果, 这些程序在网上都可以轻松得到. 在这里就不再详细讲述. 下面简要介绍一下增载轨算法. 增载轨算法[5]: 沿剩余网络中从源到汇的有向路径推进流. 增载轨算法包括Ford
网络流详解(C++版)
网络流基本概念 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 1.问题描述如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 图5-1 图5-2 2.网络与网络流 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。所谓网络上的流，是指
定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 3.可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： (1)容量约束：0≤f ij≤c ij，(v i,v j)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量v s(f)=汇点的净流入量（-v t(f)） 的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 4.可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件： (1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤f ij 网络流专题研究 福州一中肖汉骏 预备知识(参见Amber论文) 网络和流 残留网络和增广路径 最大流和最小割 主要算法 最大流 增广路方法Ford-Fulkerson method 一般增广路算法Labeling algorithm 连续增广路算法 由陈启峰提出，竞赛中相当实用，近于O(m) 容量缩放增广路算法Capacity scaling algorithm 最短增广路算法Edmonds-Karp algorithm 连续最短增广路算法Successive shortest augmenting path algorithm (Dinic augorithm) 预流推进方法Preflow-push method 一般预流推进算法Generic preflow-push algorithm 先进先出预流推进算法FIFO preflow-push algorithm 最高标号预流推进算法Highest-label preflow-push algorithm (Relabel-to-Front algorithm) 最小费用流 最小费用路方法 一般最小费用路算法(SPFA找增广路，复杂度近于O(mf)，竞赛中实用) 注意：初始流的费用必须保证是在所有同流量流中最小的。 原始-对偶算法 消圈方法 一般消圈算法 网络单纯形法 常见变形 多源多汇问题 可通过增添超级源和超级汇解决。 点有容量或费用 可以尝试拆一个点为一入点一出点，将点的限制转移到入点到出点的边上。 重边、无向边和自环的处理 对于使用边链表存储的图，重边一般不需要特殊处理。但当重边的数量太多以至于显著影响算法效率时，可以考虑将相同起点终点的边的容量相加。 而无向边则可以看做是在两个方向上都只要求Flow小于Capa即可。 而最小费用流问题中的重边却反而成为一种处理复杂权函数的手段。根据题目要求或者问题性质，可以为重边列出一个费用随流量变化的函数。如果将这个函数的离散点顺次相连，得到的是若干斜率不断增大的折线段，则可为每段折线段建立一条边，根据最小费用流的性质，重边选择的必然是连续的一段。 给定流值的情况 可以增设一个源，向原来的源连一条容量为给定流值的边。 或者在每次增广的时候，直接将源的可改进量设为到给定流值的差。 或在回溯增广的时候，将路径的增广量同到给定流值的差比较后取小。 有上下界的流问题 注意到下界必须被满足，可以将所有必要弧抽取，经过新建的源和汇。但这时必须为原来的汇到源增添一条容量为无穷大的边，使之成为满足流量平衡条件的普通节点(注意，汇到源的流量实际上就是原网络的流值)。再运行最大流算法得到一个可行流。 另一方面，可以先满足下界，此时有一些点不满足流量平衡条件。而这可以用多源多汇问题解决。 若求的是最大流，则可以在可行流的基础上进行增广。 如果求的是最小可行流，则可以通过交换源汇，去除新增的点和边后运行最大流，将多余的流抵消。也可以通过二分汇到源的容量，运行可行流。 最大费用流 将费用取负，运行最小费用流算法。 或将SPFA的大于号反向。 可行最小费用流 从T向S连边，在这基础上找负权圈增广。网络流构图总结
- 网络流算法介绍与分析 ppt课件
- 网络流算法介绍
- 9.王欣上《浅谈基于分层思想的网络流算法》
- 网络流算法介绍与分析共91页
- 图论和网络分析算法及Matlab实现(Graph_and_Network_Analysis)
- 从一道题目的解法试谈网络流的构造与算法
- 网络流最大流算法ppt
- 图论-浅谈网络流算法的应用-流算法
- 朱睿大牛：图论基础与网络流习题集锦
- 算法合集之《从一道题目的解法试谈网络流的构造与算法》
- 算法合集之《浅谈网络流算法的应用》
- 网络流：最小费用最大流(最简单的算法)(优选.)
- 算法合集之《浅谈基于分层思想的网络流算法》
- 网络流算法(Ford-Fulkerson算法)
- 算法思想之8网络流与匹配
- 浅谈网络流算法的应用
- 网络流算法专题共52页文档
- 北京大学ACM暑期课讲义-网络流
- 网络流匹配汇总
- 网络流算法(Ford-Fulkerson算法)