一种网络可靠性的多路径路由算法

一种网络可靠性的多路径路由算法胡建军1 ，王学毅2 ，范彬31 ( 兰州文理学院 电子信息工程学院，兰州 730000)2 ( 东北大学 信息科学与工程学院，沈阳 110004)3 ( 沈阳工程学院 计算机基础教学部，沈阳 110136)E-mail: hujj518 163 com摘 要: 可靠性是衡量网络性能优劣的重要参数之一 为了提高网络通信的可靠性，在一个网络的源-终端对之间往往要设计多条路由，以往的路由算法通常选择跳数、延迟、流量等参数作为网络路由的度量准则 然而路径可靠性直接影响着其他度量准 则的选择，因此选择路径可靠性的路由决策更加合理 为此，提出一种改进的基于源-终端对路径可靠性的路由算法，在算法中， 每个节点和邻居节点通过周期性交换链路信息维护着一张全局网络的毗邻矩阵，并且以路径的相关性最小优先为准则选择多 路由 实例验证表明，算法可靠性的误差明显下降，最大误差为 0 0371关 键 词: 网络可靠性; 通信网络; 网络拓扑; 毗邻矩阵; 路径相关度中图分类号: TP393文献标识码: A文 章 编 号: 1000-1220( 2014) 08-1780-04Multi-path outing Algorithm About Network eliabilityHU Jian-jun1 ，WANG Xue-yi2 ，FAN Bin31 ( Engineering College of Electric Information，Lanzhou University of Arts and Science，Lanzhou 730000，China)2 ( College of Information Science and Engineering ，Northeastern University ，Shenyang 110004，China)3 ( Teaching Department of Basic Computer，Shenyang Institute of Engineering ，Shenyang 110136，China)Abstract: eliability is one of the important parameters to measure netw ork performance Generally，for a given source-terminal pair，multiple routes exist in a data netw ork for reliability of communication netw ork，and is selected by a routing algorithm based on net- w ork metrics such as hop-count，delay，traffic，and so on How ever，path reliability directly affect the choice of these metrics，so the routing decision based on reliability w ill be the best possible option Therefore w e propose a distributed routing algorithm based on the source-terminal ( s-t) path reliability in this paper In the proposed routing algorithm，each node generates an adjacency matrix of a netw ork graph by periodically exchanging connection information w ith the adjacent nodes，and selects multiple routes based on mini- mal path dependency prior to other rule An example show s that the reliability of the algorithm error decreases obviously ，the biggest error of 0 0371Key words: netw ork reliability; communication netw ork; netw ork topological; adjacency matrix; path relevance布路由策略提出一种有效的分布式路由算法，此算法把流量作为度量准则 文献7提出一种在网云服务中控制 路 由 的 TP( transit portal) 技术，该技术在客户和互联网服务提供商之 间提供透明连接 文献8提出一种在状态链路网络 中 使 路 径多样性的路由算法，该算法以跳数作为度量准则 文献3 提出基于网络可靠性的多路径路由算法，避免了使用某个单 一准则给网络性能造成的影响 然而，文献3存在以下几点 不足: 不能正确计算重合链路的概率; 由于存在统计独立 的链路，因此使用条件概率计算源-终端对的可靠性会出现概 率大于 1 的情形; 由于存在重合链路，因此使用不大于关键 路径的 1 /2 路由的策略不能确保链路的可靠性是高的针 对文献3的不足，本文利用最小路径的相容和互斥1引 言多路径路由与单路径路由相比具有拥塞低、网络的利用率较高和响应 时 间 短、均衡负载能力强等优 点1，从 而 使 数据流的传输更加稳定和光滑2 然而，建立、维护、拆 除 路 径 的开销以及分发流量的复杂性随着路径数的增加而迅速增 大3，因此多路径路由近年来成为学者们研究的热点文献4提出一种基于数据路径服务的可扩展分布式路 由协议，此协议以成本作为度量准则 文献5使用 DIV ( dis- tributed intermediate variables) 算法提出一种推广分布式路径 计算技术，该技术尽管使用的是节点分配值递减的方法，但实 质是以跳数作为度量准则的 文献6基于本地响应 最 大 分收稿日期: 2013-05-17 收 修 改 稿 日 期: 2013-11-18 基 金 项 目: 国 家 杰 出 青 年 科 学 基 金 项 目 ( 61225012 ) 资 助; 国家自然科学基金项目 ( 61070162，71071028，70931001) 资助; 高等学校博士学科点专项科研基金优先发展领域课题( 20120042130003) 资助; 高等学校博士学科点专项科研基金课题( 20100042110025，201100- 42110024 ) 资 助; 工 信 部 物 联 网 发 展 专 项 资 金 项 目 资 助; 中 央 高 校基本科研业务费专项资金项目 ( N110204003，N120104001) 资助作者简介: 胡建军，男，1971 年生，硕士，副教授，CCF 会员，研究方向为协议工程、网络安全等; 王学毅，男，1979 年生，博士研究生，讲师，研究方向为云计算、网络安全等; 范 彬，女，1979 年生，硕士，讲师，研究方向为移动代理8 期胡建军 等: 一种网络可靠性的多路径路由算法1781概率计算特点，对文献3源-终端对间的可靠性算法进行了改进，提出了一种新的 2 路径路由查找方法，并给出了实现算 法 数值结果和仿真对比表明算法是可行和有效的 利用式( 2) 计算出 M 中每一条 M P( minimal path) 的概率| Bi|= ak ，1 i | M |P( Bi )( 2)k = 12问题描述 为便于后文的处理，按照 P( B ) ( 1i | M | ) 概率从i大到小排序假设最小路径集 B1 ，B2 ，Bn 的概率满足不等式 P( B1 )P( B2 ) P( Bn ) ，则源-终端对可靠性计算公式为式( 3) 2 1 网络模型的假设由于通常以源-终端节点对之间的连接概率来表示网络的可靠性9，因此网络被表示为一个有向图，该有向图由节点集 ( 顶点) 和链路集( 边) 组成 同时对网络模型作如下的假设: 网络链路是易于发生故障的部件，网络节点是无故障运行的 链路故障彼此是统计独立的 链路流量是单向的 通常在相反方向上设计一个平行 信道来支持双向通信 不考虑自流量( 由于节点是无故障的) 对于每条链路，添加链接的成本是相同的2 2 符号定义所用符号及相关描述见表 1表 1 符号及描述 = P( B ) + P( B B ) + + P( B B B=121nn 11n 1P( B ) + P( B ) P( B B ) + + P( B ) P( Bi Bn ) ( 3)1212ni = 13源-终端对可靠性的计算是一个 NP 难问题 通常概率大的路径对源-终端对的可靠性贡献大，因此在不使可靠性明 显降低的前提下，通常用 2 路径的可靠性代替源-终端对所有路径的可靠性 在 2 路径的选择上，有下面的定理定理 1 若 P( B1 ) P( B2 ) P( B3 ) ，| B2 B1 | | B3 B1 | ，| B3 | = | B2 | ，1 = P( B1 )+ P( B2 B1 ) ，2 = P( B1 ) + P( B3 B ) ，则 112证明: 令 | B | = i，| B | = | B | = j，| B B | = a，| B B |1232131= b，则 a b因为 0 r 1，所以 r a r b ，在 r a r b 两边同乘以 r i / r ab ，得 r i a r i b Table 1Symbols and description序号符号描述123VE M节点集边集源-终端对的最小路径集在源-终端对间的第 i 个最小路径( 最小路径是一个边集，该边集 满 足，如 果 该 边 集 中 的 任 意 一 条 边被移除，则余集不再是一条路径)源-终端对的可靠性最小路径的概率 邻接矩阵源-终端对间最小路径的条数，n = | M |集合元素的个数节点对，其中 s 为源节点，t 为终端节点 从 s 到 t 总流量选择传输的路径= r i + r j ( 1 r i a ) ，又因为，= P( B )+ P( B B )112 12 = P( B1 )+ P( B3 B1 )= r + r ( 1 ri ji b)= r j ( r i b r i a )所以， = P( B ) + P( B B )12121Bi40，即 成立证毕12定理 1 表明，与 主 路 由 相 比，在路径链路数相同的情况 下，路径的相关性越低路由的可靠性越高 该定理对于给出了 在路径链路数相同时选择备选路径的方法对于路径链路数不同的情形，确定它们之间的关系比较困难 尽管如此，由于后一项可靠性的贡献相对整个可靠性来 说要小的多，为了使问题简化，仅对相差 1 的两条路径的情形 加以考虑定理 2 假设 | B1 B3 | = 0，| B1 B2 | = 1，| B3 | = | B2 | +56789101112P G n| |( s，t)Q T2 3数学描述利用邻接矩阵表示一个网络 G ，G = gij ，1i，j | V | ，1 ，1 = P( B1 ) + P( B2 B1 ) ，2 = P( B1 ) + P( B3 B1 ) ，则当| B1 | 7，1 2 ; 当 | B1 | 7 时，1 2 证明: 令 | B1 | = i，| B2 | = j，| B3 | = k，则 k = i + 2，j = i + 1其中iji 1因为1 = P( B1 )+ P( B2 B1 ) = r + r ( 1 r) ，0， otherwise1， if an edge existsgij =( 1)+ P( B B ) = r i + r k ( 1 r i ) ，所以， = P( B )21311i + 1i 1i + 1 2 = r( 1 r r + r) 下面根据 i 的不同取值进行讨论在实际的网络中，网络链路的性能是有优劣之分的，但是为了使研究问题简化且与文献3易于对比，采用任 一 链 路 具有相同的可靠性，即每条链路的可靠性为 r = 0 9任一源-终端对的一条路径是一条最小路径 源-终 端 对的最小路径求解算法有 SDP( sum-of-disjoint products) 技术和BDD( binary decision diagram) 技术9，由于 SDP 技术利用逻 辑运算法，计算简介且效率较高，而邻接矩阵网络连通性的表示很容易通过 SDP 技 术 求 出 源-终端对的最小路径，因 此 本 文使用 SDP 技术假设源-终端对的所有最小路径存储在 M 中，则 最 小 路 径概率的计算过程如下:当 i = 7 时，1 r当 i = 6 时，1 ri 1 r + r= 0 00097 0;i + 1i 1 r + r= 0 01219 0;i + 1当 i = 5 时，1 r i 1 r + r i + 1 = 0 02466 0;当 i = 4 时，1 r i 1 r + r i + 1 = 0 03851 0; 当 i = 3 时，1 r i 1 r + r i + 1 = 0 0539 0;当 i = 2 时，1 r i 1 r + r i + 1 = 0 071 0;但当 i8 时，1 r i 1 r + r i + 1 0从而得出，当 | B1 | 7 时，1 2 ; 当 | B1 | 7 时，1 2 证毕1782小 型 微 型计 算 机 系 统2014 年定理 2 说明，在链路数不超过 7 且相交路径最小时( 即为1 时) ，概率大的对可靠性的贡献反而小 在 2 路径的选择中，7 条链路基本上可以满足要求 根据小世界效应( 又称六度分 割理论 ) ，在 互 联 网 中，从 源 到 目 的 间的跳数通常只需 6 跳10 另外，当链路数大于 7 时，备选链路对可靠性的贡献相 对较小 因此，在下面的算法中，把 7 条链路作为判断依据Forw ard Q1 and Q2 on T1 and T2 respectivelyEndif算法的数值比较4为了与文献3对比，采用同文献3相同的网络拓扑结构，如图 1 所示 其中源节点为，剩余节点均为目的节点32 路径选择算法与路由3 1 2 路径选择算法2 路径选择的方法是首先选取概率最大的最小路径为第 一条路径，即主路由，然后计算次大概率的最小路径与第一条 路径的交集，根据定理 1，若交集的重叠链路为空 集，则 该 路 径就是所要选择的第二条路径，否则计算后面与此路径链路 数相同的最小集，或者根据定理 2 计算，从而选择出第二条满 足可靠性的路径 算法如下:Tw o-path-select( T1，T2)T1 = B1 / * B1 is a optimal pathIf | M | 2 thenindex = 2if | B2 B1 | 0 and | B1 | 1j = index + 1图 1 11 个节点的网络结构图Fig 1 Topology structure of 11 node netw ork图 2 图 1 的转化图Fig 2 Conversion of the Fig 1表 2 源节点 1 到其他各终端节点对的实验数据Table 2 Data of the source node 1 to the other terminal node终端节点链路 全路径 文献32 路最小路径集数可靠性径可靠性1213911821710639118215820 96340 9590For all j | M | doIf | B1 Bindex | = 0 thenExitElse/ * find suboptimal path1241312317106330 99510 981 1 2 5 9 6 3 5 if | B1 Bindex | = 1 and | Bj | 8 and| Bindex | = | B1 | + 1 and | Bj | = | B1 | + 2and | B1 Bj | = 1 thenindex = jendif134174123417106342230 9795540 9639 1 2 5 9 6 3 4 6 1251391182526endifT2 = Bindex50 8670 8631 171063911825 9 endif1710613961239612596334460 96370 92663 22 路由算法根据 3 1 选择的路径，将每条路径的第一个节点作为路 7 1 7 1 0 9 0 9 由算法的第一跳，再按照当主路由达到某个阈值时利用比例流量分布的策略实施 2 路由转发比例流量分布的计算见式( 4) 和式( 5) 1258125118139118125911812391183445580 93690 7946e | T2 |( 4)Q1 = Q/ main routinge | T2 | + e | T1 | 1 7 10 6 3 9 11 8 7 e | T1 |1391259123917106392335( 5)Q2 = e | T2 | + e | T1 | Q/ alternative routing90 96930 88292 路由算法如下:Tw o-path-outing( )Call Tw o-path-select( T1，T2)Identify next node for each pathInsert into routing table for same destination If Q = K then / * K denote link threshold Forw ard Q on T1 / * only use main pathElse 10 1 7 10 1 0 81 0 81 125111391112591112391117106391133446110 9520 9266由于图 1 不易观察源-终端对的路径，因此，按 照 深 度 搜8 期胡建军 等: 一种网络可靠性的多路径路由算法1783更加逼近实际值，特别是文献3算法在节点8上背离实际的可靠性，节点 9 离实际的可靠性也较远 尽管节点 6 离实际可靠 性稍远点，误差为 0 0371，但此误差与文献3相同 从图 3 可以 看出，本文 2 路径算法源-目的节点对间的可靠性与所有路径的 可靠性非常接近 这表明，本文提出的算法是正确有效的索的方法，把图 1 转化为图 2( 见上页) 我们取与文献3链路相同的概 率，即任一链路的概率 均为 0 9 下面给出图 2 中源节点 1 到其他各终端节点对的相 关信息，见上页表 2根据 Tw o-path-select( ) 算法，找出表 1 中的可靠性高的 2条最小路径，并计算出可靠性，具体数据见表 3表 3 源节点 1 到其他各终端节点对 2 路径实验数据 Table 3 Data of tw o paths of the source node 1 to the other terminal node5结 论利用相容和互斥概率的特点，对文献3源-终端对间的可靠性算法进行了改进，提出了一种新的 2 路径路由查找方 法，并给出了算法的实现 数值结果和仿真对比表明，该算法 是可行和有效的，具有较好的特性终端节点 最小路径集链路数本文 2 路径可靠性12120 9590 1 3 9 11 8 2 5 eferences:1 Vutukury S，Carcia-Luna-Aceves J J M PATH: a loop-free mul- tipath routing algorithmJ M icroprocessors and M icrosystems，2000，24( 16) : 319-3272 Bertsekas D，Gallager Data netw orksM Englew ood Cliffs，NJ: Prentice-Hall，19923 M ou Dasgupta，Bisw as G P Design of multi-path data routing al- gorithm based on netw ork reliabilityJ Computers and Electrical Engineering，2012，38( 6) : 1433-14434 Huang Xin，Ganapathy Sivakumar，Wolf Tilman A scalable dis- tributed routing protocol for netw orks w ith data-path servicesC In: IEEE International Conference on Netw ork Protocols，ICNP2008: 318-3275 ay Saikat，Gurin ，Kw ong K W，et al Alw ays acyclic distrib- uted path computationJ IEEE / ACM Trans Netw ork，2010，18( 1) : 307-3196 Como Giacomo，Savla K，Acemoglu D，et al obust distributed routing in dynamical flow netw orks-Part I: locally responsive poli- cies and w eak resilienceJ IEEE Transactions on Automatic Con- trol，2013，58( 2) : 317-3327 Valancius V，Feamster N，exford J，et al Wide-ar