在overlay网络上的负载平衡多播路由算法.doc

第4期张晓瑜等：在overlay网络上的负载平衡多播路由算法93在overlay网络上的负载平衡多播路由算法张晓瑜，张光昭(中山大学 电子与通信工程系，广州 广东510275)摘 要：针对基于代理服务器的overlay网络的负载平衡多播路由算法被提出。它能均衡利用overlay网络的有限资源，并能满足多播应用的延迟限制需求。首先用具有延迟约束的Steiner树问题对路由问题进行建模；然后采用预计算方法将计算复杂度集中在预备的单点路径计算上，使由这些单点路径所构成的网络更易于构建负载平衡路由树；预计算只计算一次，结果使用多次，因此降低了总体的计算复杂度。仿真实验的结果表明，相对于其他的快速启发式算法，该算法能提供更为优越的性能。整体而言，基于预计算的负载平衡多播路由算法在性能和计算复杂度方面取得了很好的平衡。关键词：overlay网络；多播路由算法；负载平衡；预计算中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2009)04-0086-07Load balance multicast routing algorithms on overlay networkZHANG Xiao-yu, ZHANG Guang-zhao (Department of Electronics and Communication Engineering, Sun Yat-sen University, Guangzhou 510275, China)Abstract: Overlay networks had been recently developed to support multicast framework. Specially, overlay architectures based on proxies and leased lines could provide applications with optimal performance in terms of bandwidth, reliability, delay guarantee, etc. A balanced multicast routing algorithm for these proxy-based overlay architectures was proposed to utilize the network resources efficiently while keeping the delay guarantee for each multicast session. First, the routing problem was modeled as a delay-constraint Steiner tree problem. Then, a balanced solution with the aid of precomputing was proposed. The precomputing performed once with high complexity. However, its outcome was used multiple times in the later low complexity tree forming algorithm. Hence, the overall complexity was lowered. Extensive simulations show that the multicast routing algorithm provides superior performance with respect to other heuristics.Key words: overlay network; multicast routing algorithm; load balance; precomputing1 引言收稿日期：2007-06-04；修回日期：2009-02-11Overlay网络以及应用层多播技术正吸引着愈来愈多的关注，这在于overlay架构可以使人们方便地在现有的因特网上实现群组通信，例如视频会议、视频点播、多人游戏、协同工作等，而不需要改变现有网络的底层结构和协议，如路由器的实现机制、点到点的IP协议等。应用层多播实质上就是在端系统上建立逻辑网络（overlay网络），再在这个逻辑网络上，也就是应用层上，实现多点通信；而在底层仍然采用点到点的通信协议15。在这里，端系统可以指用户的终端系统，也可以指特定的代理服务器。本文讨论的是由特定的代理服务器（称为多播系统节点(MSN，multicast system node)）构成的overlay网络，并且代理服务器之间的连接是采用租用线路（或者是虚拟专用线路）实现的，这样的网络称为虚拟专用overlay网络（VPON, virtual private overlay network）6。VPON具有以下的优点：1）代理服务器是长期稳定地存在网络中，由它们构成的网络可以实现优化的网络配置，以达到高资源利用率、低延迟和高可靠性的网络性能；2）采用租用线路或者是虚拟专用线路可以避免VPON上的数据与因特网上的IP数据流竞争网络带宽资源，从而避免了由于竞争引起的抖动、高延迟、低吞吐率等不可预测的网络破坏性行为。VPON可以为最后的终端用户提供具有一定业务质量要求（QoS, quality of service）的服务，如宽带、实时和可靠传输业务。图1显示了由MSN构成的overlay网络。这里要注意，由于是租用（虚拟）线路，VPON的链路带宽资源都是有限的。图1 由MSN构成的overlay网络对于提供QoS业务的VPON运营商来说，需要考虑以下的问题。1）资源规划问题。即在总资源一定的情况下，如何分配链路资源，使得VPON具有最优的服务能力。2）路由问题。即对于给定资源规划的VPON以及给定的多播业务需求，如何选择路由策略，使得不仅可以满足它们的QoS要求，而且可以最大化VPON的服务能力，即可以满足最多的多播会话数目。本文着重考虑路由问题。假设QoS要求为时延要求（相当多的实时应用的首要需求，尤其是流媒体业务，如视频会议），因此路由问题可以表述为在有限的资源情况下，如何为多播会话设计路由算法，使能满足多播会话的最大时延约束，并且能够容纳最多的多播会话数目。Overlay网络的资源规划问题和路由问题在近几年均有文献涉及。文献7提出了MSN的带宽资源规划和满足端端延迟约束的资源优化路由算法。但是文献中设定overlay网络的租用带宽仅仅是在MSN到骨干网的接入带宽上，而不考虑MSN之间的链路连接带宽，即认为骨干网的带宽是无限大的。本文考虑的VPON是所有链路的租用，即接入带宽和骨干网带宽资源都是有限的，都存在多业务的资源竞争，设计负载平衡的路由算法使实现满足应用需求的全网资源优化。在多播路由算法方面，关于最小代价树（minimum Steiner tree）算法在近10多年里取得了跳跃式的进展。最小代价树的近优似算法的性能达到了1.550(Steiner ratio: 指近似算法性能与最优性能的比值)8,9。也有相当多的文献讨论具有QoS约束的最小代价树算法，例如延迟、延迟抖动、最小带宽约束等。文献10提出的具有最小带宽约束的最小代价树算法近似比率达到3.802。这一类的多播路由算法的特点是它们可以获得近似最优的性能，但是它们的计算复杂度很高，它们的最好结果至少是O(|V|3)（|V|表示节点数）。还有另一类的最小代价树的近似算法，它们具有较低的复杂度，而且它们的性能在一般的情况下可以与上述的算法相比拟。它们的缺点是在最坏情况下，性能会远低于最优性能。这类算法包括最短路径树算法（shortest path tree）11、目的地驱动的多播（DDMC，destination driven MultiCast）算法12。这类算法的特点是采用分布式计算或者是仅仅利用局部信息。DDMC是结合了Dijkstra最短路径算法和Prim最小支撑树算法, DDMC的计算复杂度为O(|E|log|V|)（|E|表示边的数目）。在具有时延约束的多播算法方面，文献13提出了源路由算法。首先原始网络被变换为仅仅由目的节点构成的新网络，新网络的边为相连的2个目的节点之间满足时延约束的最小代价路径。然后，在新网络上构建Prim最小支撑树。最后，这个最小支撑树再扩充回原始网络中。算法的复杂度为O(|V|3)。文献14提出的时延约束最小代价树是从计算最小延迟树开始，在不破坏约束条件下，采用迭代算法用代价较低的边替换树中的边，直到不能替换为止。算法的复杂度为O(k|V|3log|V|)（k表示每次迭代的替换数）。这2种算法均能满足应用的延迟约束，但是过于复杂，使之难以运用到实际的网络协议中，尤其是对于规模较大的网络。本文提出的路由算法采用预计算的方法，对每个节点利用局部信息并采用分布式计算构建满足一定延迟约束的负载平衡路径，再构建负载平衡树。预计算的方法极大地降低了网络多播路由的总体计算开销，从而使算法可实际应用于VPON路由规划。本文的主要贡献在于对原有的预计算方法进行修改，将其用于计算负载平衡的多播路由树，使之具有优越性能的同时，降低计算复杂度。 本文的结构如下：第2节给出路由问题的数学描述，第3节提出满足延迟约束的负载平衡路由算法，第4节是仿真实验结果，第5节是结束语。2 问题描述本文的路由问题可以认为是在VPON上的QoS多播路由问题10。我们希望设计这样的路由算法，既能够充分利用VPON的可用带宽资源，同时保证能够满足应用的QoS要求端端延迟约束。显然，对每一个多播会话，我们希望将它路由至可用带宽较大的路径上，使得总体来说在VPON上不会出现哪条路径资源过于紧张，而导致不能容纳更多的多播会话。也就是说，对于总资源一定的VPON，路由算法应使得多播流量可以均匀地分布在各条链路上。令剩余带宽Res(l) = link capacity （链路容量） bandwidth being used（已用带宽），路由算法在建立多播路由树的时候，其目的是使最小的剩余带宽即min Res(l)最大。这样建立起来的多播路由树称之为平衡树。在某些情况下，VPON服务提供商会提高资源较为紧缺链路的价格，即价格反比于链路的可用带宽。令开销（cost）为剩余带宽的倒数。从而，对于我们的路由算法来说，寻找最大的最小剩余带宽可以转变为寻找最小的开销树，同时它要满足端端延迟限制。路由问题可以描述为如下的形式。给定：一个无向图G = (V, E, w, d)、s和一个非空的集合D。V和E分别是图的节点集合和边集合; s是源节点；D V, 为目标节点集合; w是边的开销函数(反比于边的可用带宽)；d 为边的延迟函数。求：G 上的一棵源为s的路由树TG(s)。满足：1) 连通性，D中的任意2个节点间存在一条路径;2) 总开销在所有可能的路由树中最小;3) 由s到任意u，uD的延迟不超过B(B为延迟约束)。在路由树中不属于D的节点称之为Steiner节点。寻找满足延迟约束的最小开销树实际上为求解具有约束问题的Steiner树。由于Steiner树问题是NP难度问题，它是求解延迟约束Steiner树问题的特殊情况，即当延迟约束为无穷大时的情况。所以，求解具有延迟约束的Steiner树问题也是NP难度问题15，需要采用启发式方法进行求解。3 多播路由算法3.1 预计算前文提过，对于QoS的多播路由问题，其求解方法通常在获得较优解的时候，所带来的代价就是计算复杂度太高。近年来，在求解网络约束路径问题上提出了预计算的方法。预计算是提前计算所有相关的路径并将它们存储在数据库里。它能快速满足大量的在不同时刻到达的具有不同QoS要求的连接请求。它相当于预计算一次，而使用多次，从而从总体上降低了计算复杂度。这种计算所有相关路径的方法可以作为发展其他网络相关问题算法的中间步骤16,17。本文也采用预计算的方法来求解具有约束问题的Steiner树。这里首先简要描述如何预计算约束路径16，然后，将提出我们的算法。对于给定的图G=(V, E, w, d), 一条路径p的开销和延迟可以分别表述如下：用Pt(d)表示所有源为s、目的地为t、延迟不超过d的路径集合。令表示所有路径pPt(d)的最小开销（若，则）。可以证明是分段常数，右连续，非递增的函数；并且如果在d上是跳跃的，则必存在一条路径p*(d)Pt(d)满足也就是说，通过寻找这些跳跃点，就可以找到与它们对应的路径。Siachalou等人16提出了对网络中所有节点寻找不连续点的算法。由于是非递增的函数，显然对应于跳跃点的路径不会出现环路。在无向图中，每一条边相当于具有2个方向。只要同一条边的2个方向不同时使用，那么它的每一个方向都不需要重新定义参数，即假设每一条边不是出边（数据流出节点），就是入边（数据流入节点），其开销函数与原来边的开销函数一致。而算法的特性表明回路或重复路径不会出现在不连续点的路径中，因此同一条边的不同方向一定不会同时使用，即算法也适用于无向图。我们对他们的算法进行修改，以适应无向图的特性。修改后的算法如下。预计算算法输入：图G, 源s和延迟约束B输出：队列D(u), /*初始化 */1) 2) /*初始化结束*/3) 生成(d, C, u, pu)所有可能的后续不连续点(即集合 ) 并将它们添加至P；4) 如果P 是空的，则停止；5) 在P中的所有元素中 (可能的后续不连续点), 寻找并抽出(即从P中删除) 在词序中最小的一个元素，标识这个元素为(d, C, u, pu)；6) 如果，则回到第4)步；7) 否则; 回到第3)步。在算法中，第1)步和第2)步是初始化所有节点的不连续点。表示对应于不连续点(d, C)的路径。在第3)步里，一旦证实了(d, C, u, pu)是一个真实的不连续点，则算法将产生以(d, C, u, pu)为前一跳的所有可能的不连续点，这些不连续点满足路径延迟不超过B，而且路径不存在循环（如果表示v不在该路径上，否则的话将会产生循环，因为节点v在之前就已经经过）。如果不存在可能的不连续点（第4）步），算法停止。在第5)步，在词序上最小的不连续点从P中抽出。词序定义如下：对于(di, Ci), i=1,2, 当且仅当d1d2或者d1=d2且C1=C2，则认为(d2, C2)在词序上大于(d1, C1)。在第6)步，检查它是否是真实的不连续点，如果是，则将它加入相应的集合中，否则回到第4)步。算法最终在找到延迟不超过B的所有不连续点后结束。在这里要注意的是D(u)是用队列实现的，其中的元素(d, C, u, pu)在算法运行过程中是以d的递增或C的递减顺序来存放的。3.2 负载平衡多播路由树首先看一个例子。图2显示了网络G以及对应于各个节点的不连续点集合D(u)=延迟, 开销, 路径。假设s=1，3,4,5是目的节点集合，B=20是延迟限制。将D(u)中的第一个元素抽取出来，可以构造图G*。例如对于节点2，选择第一个不连续点，其对应的路径为1432。采用同样的方法，可以获得以下的路径构造G*：143, 14, 1425。显然，这样构造出来的G*并不是一棵树。由于G*包含了所有延迟不超过B的最小开销路径，因此它必然包含满足延迟约束的树。令T*为G*上以s为源的到达所有目标节点的最小延迟树。从而T*是延迟约束的，并且接近所要求解的具有约束条件的Steiner树。算法仅在这样的条件下会失败，即若存在目标节点，它在D(v)中的第一个元素为，表示不存在满足延迟约束的s至v的路径。算法的最后要注意剪除到达非目标节点的路径。图2 一个例子，图G及其G*可以进一步降低计算复杂度，即直接从预计算的D(u), uV中构建T*。在文献10的引理中，如果v是对应于u的不连续点(d, C, u, pu)中路径pu的前一跳，则v必然有不连续点(d-d(u, v), C-w(u, v), v, pu-u)，并称为前向不连续点。因此，对于目的节点t，对应其D(t)的第一个元素，搜索并标志路径上所有的不连续点。最后，可以构造T*，利用在D(u), uU中做过标志的最小元素。再看看图3的例子，可以计算如下。节点3：p3 = 143节点4：p4 = 14节点5：p5=1425, 它的前一跳是节点 2: p2 = 142, 作为D(2)的最小标志点。图3 采用BRONP算法在图3G上构建树T*组合这些路径，可以获得T*, 算法如下。BRONP：1) 预计算D(u), uV, 延迟约束为B；2) 对于每一个目标节点，对应其D(v)的第一个元素, 搜索它的前向不连续点并标志起来；3) 利用D(u), uU中标志的最小元素信息构造多播树。算法的最终目的是平衡在VPON上的多播流量，称之为基于预计算的覆盖网络平衡路由算法 (BRONP, balance routing on overlay network with precomputing)。3.3 复杂度分析表1算法的计算复杂度比较Steiner树近似优化算法Steiner树启发式算法(DDMC,SPT)具有延迟约束的Steiner树近似优化算法BRONP计算复杂度O(|V|3) 10O(|E|log|V|) 11，12O(|V|3) 13，O(k|V|3log|V|) 14预计算：O(|E|V|log|V|+|E|2)建树：O(|V|log|V|)在BRONP算法中，预计算约束路径在最坏情况下的计算复杂度为O(|E|V|log|V|+|E|2) 17，构造树的复杂度为O(|V|log|V|)。利用预计算的方法，BRONP易于处理多播会话的动态性问题，即多播成员的加入/退出行为（这在overlay多播中是常有的问题）以及对于不同的成员有不同的延迟要求的问题。由于预计算只进行一次，结果使用多次，因此总体复杂度降低了。表1给出了BRONP与其他现有算法的复杂度比较，可以看出，BRONP的预计算部分复杂度较高，但当预计算结束后，以后每次多播路由的计算都与DDMC11和SPT17相仿，即BRONP通过预计算，其总体复杂度降低。另外，可以预计BRONP的性能会低于高复杂度的具有延迟约束的Steiner树近似优化算法13,14。在仿真实验中，验证BRONP可达到无约束启发式算法的性能水平，从而证明BRONP算法的实用性。4 仿真结果4.1 仿真环境的设置采用Waxman的网络拓扑概率模型生成具有100个自治域AS(autonomous system)节点的随机网络拓扑。假设每一个AS节点连接一个MSN。所有的这些MSN和它们之间的链路构成一个overlay网络。任意两点间的时延设置为它们之间的欧氏距离。链路的带宽满足均匀分布。设置多播会话到达过程为泊松过程，会话持续时间满足Pareto分布。会话成员数目（会话容量）满足截断的二项式分布，最大值为50，最小值为2，均值在各个实验中有所不同。假设所有的多播会话的带宽需求相同。评估BRONP的性能，并与DDMC（启发式Steiner树算法）12和SPT（最短路径树）11比较。假设在SPT算法中，如果最大的延迟超出延迟约束，则认为算法失败，该会话被拒绝。评估标准分别从以下几个方面来评估。 拒绝率。多播会话拒绝数目/多播会话申请数目，当算法不能满足延迟约束或网络资源不足，则多播会话被拒绝。拒绝率越高，则表示系统能容纳的多播数目越少。 延迟。包括多播会话的平均延迟和最大延迟。延迟反映多播会话的实时性能。 利用率。网络使用资源总量/网络总资源。它反映网络资源的使用程度。整个仿真程序在Linux平台上采用C语言实现。4.2 结果图4显示了执行3个多播算法（BRONP, DDMC, SPT）的拒绝率和多播会话到达速率的关系。参与多播会话的节点数均值分别是10和20，延迟约束为10。图5显示了在同样设置下网络利用率和多播会话达到速率的关系。正如图5所示，网络利用率随着会话达到速率的增加而增加，这表明overlay网络的流量负载增加，同样，如图4所示，拒绝率曲线也随着会话到达速率的增加而增长。由于SPT算法并不考虑负载均衡，因此它有最高的拒绝率。而DDMC不考虑延迟约束，仅仅考虑链路带宽的开销，即负载均衡，它有最低的拒绝率。BRONP的拒绝率曲线接近DDMC，但在最高的部分分开。这是因为随着越来越多的会话竞争网络资源，BRONP难以在满足延迟约束的同时平均地分配资源。例如，在图4中，当到达速率分别为20、25、30的时候，BRONP和DDMC的拒绝率曲线分离开来，此时，图5显示的资源利用率高达70%。更进一步，可以观察到对于不同的会话容量，结果都相似。它们的差别仅在于给网络施加的负荷不同。图4 拒绝率和会话到达速率的关系图5 利用率和会话到达速率的关系表2比较了3个启发式算法的性能。此时多播会话到达率为15，会话的平均容量为10，BRONP和SPT的延迟约束为10。可以发现DDMC的平均延迟和最大延迟都远大于BRONP和SPT。虽然SPT可以获得最小的延迟，但它有最高的拒绝率，几乎是另外2个算法的2倍。BRONP的性能接近DDMC，这表明它能充分利用网络资源，同时满足延迟约束。表2 算法性能比较(容量为10, B为10, 会话到达速率为15)启发式算法利用率拒绝率平均延迟最大延迟DDMC59.6%13.2%10.638.8SPT54.1%27.8%4.610BRONP65.5%14.3%710图6显示了当延迟约束改变时BRONP的性能变化。可以观察到当延迟限制放松后，拒绝率曲线下降直至平稳。这是由于对一个多播会话来说当限制条件放松后，它更容易找到足够的可用资源分配给多播会话。从仿真实验可以得出结论，即BRONP可以取得接近于DDMC的性能并能同时满足延迟限制。图6 延迟约束改变时BRONP的性能变化5 结束语本文提出了BRONP算法基于预计算的覆盖网络平衡路由算法。BRONP的目标是在资源受限的overlay网络上实现负载均衡，从而在满足应用程序延迟约束的条件下最大化多播会话数目。BRONP算法采用预计算的方法降低总体的计算开销，具有很好的实用意义。仿真实验表明，BRONP算法的性能接近无约束条件的最小开销树算法的性能，并且远优于最短路径树。BRONP算法主要针对资源受限的VPON网络，这类网络通常由具备网络支付能力的公司组织或网络运营商所有。为了使所构建的网络有最大的效用，优化网络资源利用率，通常还要考虑如何配备连接带宽以及代理服务器的个数和位置，使最终的总成本最低。这时，需要设计涵盖该路由算法的带宽分配算法和代理服务器的配置算法。这将是我们进一步的工作。另外，BRONP也可用于非租用带宽网络，即IP网络，此时需要在TCP层进行端到端的可用带宽的测量，获得overlay上两节点间的带宽。参考文献：1CHU Y, RAO S, ZHANG H, Enabling conferencing applications on the internet using an overlay multicast architecture A. Proc of the ACM SIGCOMM C. San Diego, CA, 2001.55-67. 2CHAWATHE Y, Scattercast: an Architecture for Internet Broadcast Distribution As an Infrastructure ServiceD. Berkeley, CA, University of California, Berkeley, 2000.3JANNOTTI J, GIFFORD D K, JOHNSON K L. Overcast: reliable multicasting with an overlay networkA. Proc of the 4th Symposium on Operating Systems Design and ImplementationC. San Diego, CA, 2000.4FRANCIS P. Yoid: extending the Internet multicast architecture EB/OL. /yoid/docs/index.html, 2000.5章淼，徐明伟，吴建平. 应用层多播研究综述J. 电子学报, 2004, 32(12A):22-25.ZHANG M, XU M W, WU J P. Survey on application layer multicastJ. Acta Electronica Sinica, 2004, 32(12A): 22-25.6LOUATI W, ZEGHLACHE D. Network-based virtual personal overlay networks using programmable virtual routersJ. IEEE Comm Magazine, 2005,43(8): 86-94.7SHI S Y, TURNER J. Multicast routing and bandwidth dimensioning in overlay networksJ. IEEE Journal on Selected Areas in Communications(JSAC), 2002, 20(8):1444-1455.8ROBINS G, ZELIKOVSKY A. Improved Steiner tree approximation in graphsA. Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete algorithmsC. 2000. 770-779. 9CHLEBIK M, CHLEBIKOVA J. Approximation hardness of the steiner tree problem on graphsA. Proc 8th S