《基于不相交路径的域内路由保护方案》由会员分享，可在线阅读，更多相关《基于不相交路径的域内路由保护方案（11页珍藏版）》请在金锄头文库上搜索。
1、基于不相交路径的域内路由保护方案 耿海军 刘洁琦 张举 山西大学软件学院 摘 要： 业界提出利用路由保护方法来提高网络的可用性。但是, 目前采用的路由保护方案有下面两个问题 (1) 备份路径和默认路径交叉度比较高。 (2) 为了寻找交叉度较低的两条路径, 默认路径可能不利用最短路径。因此, 本文首先将问题描述为整数规划模型, 接着利用遗传算法计算近似最优解, 最后在大量拓扑结构上对算法进行了模拟。模拟结果表明, 本文的方案大大降低了默认路径和备份路径的交叉度, 从而提高了网络的可靠性, 提升了用户体验。关键词： 默认路径; 备份路径; 网络故障; 整数线性规划; 遗传算法; 作者简介：耿海军
2、(1983-) , 男, 山西太原人, 讲师, 博士, 主要研究方向为网络体系结构和路由算法等 () 。作者简介：刘洁琦 (1995-) , 男, 山西太原人, 本科生, 主要研究方向路由算法 () 。作者简介：张举 (1972-) , 男, 山西太原人, 讲师, 硕士, 主要研究方向为SDN 网络和路由算法等 () 。基金：国家自然科学基金 (61702315) Intra-domain Routing Protection Scheme based on Disjoint PathsHaijun Geng Jieqi Liu Ju Zhang School of Software Engi
3、neering, Shanxi University; Abstract： Academics and industry have proposed to employ reactive routing protection solutions to deal with network failures in the network. However, the existing routing protection algorithms are facing two problems: (1) The disjointness of the default path with respect
4、to the backup path is very low. (2) In order to compute two paths which have high disjointness, some restriction must be put on default path, i.e., the default path is not the shortest path. In this paper, we first introduce the problem of constructing disjoint paths into integer programming problem
5、s, and then propose to use the genetic algorithm to calculate the approximate optimal solution. Finally, the algorithms are carried out in the real, measured and generated networks. The experimental results show that the proposed algorithms can greatly enhance the disjointness of the shortest path a
6、nd the backup path, and improve the network availability.Keyword： default path; backup path; network failure; integer linear programming; genetic algorithm; 0 引言在设计之初互联网主要用于部署一些非实时应用1, 但是目前许多实时应用234也部署在了互联网之上, 实时应用对网络的性能提出更加严格的要求567。很多研究已经表明网络中的故障经常出现8910, 但是目前的路由协议很难应对频繁发生的突发故障。为了解决上述出现的问题, 业界提出了路由
7、保护方案1112, 该方案利用预先计算出的备份路径来应对主路径出现断路的情况。下面介绍一些常见的路由保护方案。多配置路由13 (Multiple Routing Configurations, MRC) 利用多拓扑结构的思想为每条链路存储备份路径, 但是该方案的计算开销过大, 消耗了大量的计算资源。FCP14 (Failure Carrying Packet) 将故障信息存储在报文的头部, 然后利用给信息事先计算相应的备份路由表, 但是该方案对路由协议的改变较大, 无法在互联网中部署。IP 快速重路由15 (IP Fast Re-Route, IPFRR) 是一种较为简单的路由保护方案, 该方
8、案利用无环路规则预先计算备份路由表, 但是该方案的故障覆盖率较低。为了进一步提升 LFA 的故障保护率, 作者在文章16中提出了 U-turn 方案, 该方案可以在节点的邻居的邻居节点中计算 LFA 下一跳。U-turn 虽然明显提高了故障保护率, 但是仍然达不到预期目标。相关作者在文章17中利用红绿树来构造两条不相交路径, 但是该方案限制了默认路由, 即默认路由可能不采用最短路径。作者提出了在 SDN 网络中如何应对网络故障的框架和算法18, 但是该方法只能部署在 SDN 网络中。本文主要包含三个方面的贡献:(1) 首先将本文需要解决的科学问题转化为求解整数线性规划 (Integer Lin
9、ear Programming, ILP) 的问题。(2) 然后利用遗传算法求解上述 ILP 问题。(3) 最后在不同网络拓扑结构中对算法进行了模拟。1 网络模型和问题描述为了清晰的描述本文需要解决的科学问题, 需要在基本网络模型的基础上做一些扩充。下面我们首先描述网络的基本模型, 该模型和目前学术界普遍采用的模型是一致的。网络可以表示为一个无向图 G= (V, E, C) , 在该模型中 V 代表网络中的所有路由器, E 代表网络中的所有链路, C 代表网络中链路权值的集合。对于该网络中的每一条边e= (i, j) E, w (e) , w (i, j) 代表该边对应的权值。在实际网络中边的
10、权值一般具有对称性, 即 w (i, j) =w (j, i) 。P (o, d, G) 代表网络中节点对 (o, d) 的最短路径, D (o, d, G) 代表节点对 (o, d) 的最小代价.然后我们对上述基本模型进行扩展。在网络基本模型 G= (V, E, C) 的基础上, 根据第 2 节描述的方法可以生成其对应的扩展模型 G= (V, E, C) 。本节不介绍基本模型转化为扩展模型的方法, 我们将在第 2 节中详细介绍其具体的方法。在扩展模型中, P (o, d, G) 代表网络中节点对 (o, d) 的备份路径, D (o, d, G) 代表节点对 (o, d) 的最小代价。P (
11、o, d, G) 代表该节点对之间的备份路径, K (o, d, e) 代表链路 e 是否同时在节点对 (o, d) 的最短路径和备份路径上, 可以用下面的数学公式来表示:从该定义可知, 如果链路 e 同时在节点对 (o, d) 的最短路径和备份路径上, 则 K (o, d, e) 则的数值为 1, 否则为 0。L (o, d) 定量的描述了节点对 (o, d) 的最短路径和备份路径同时包括的边的总数量。网络交叉度为网络中全部节点对之间的最短路径和备份路径包括的边的总的数量, 用 R (G, G) 来表示, 即:最后在网络模型和扩展网络模型的基础上描述本文解决的关键科学问题。已知网络拓扑结构
12、G (V, E, C) , 如何在该拓扑结构的基础上生成其对应的扩展拓扑结构 G= (V, E, C) , 使得网络交叉度 R (G, G) 的数值最小。2 算法从第 1 节中描述的关键科学问题可知, 本文需要在已知拓扑结构 G= (V, E, C) 上, 生成其对应的扩展结构 G= (V, E, C) , 从而使得网络交叉度的数值最小。G= (V, E, C) 和 G= (V, E, C) 的唯一区别是链路的权值集合不同, 即本文需要解决如何在 G= (V, E, C) 的基础上调整网络中链路的权值, 从而使得 R (G, G) 的数值最小。下面, 我们定性的描述本文需要解决的问题:已知网络
13、拓扑 G= (V, E, C) , C=w (e) , eE, 如何调整网络中所有边的权值 C=w (e) , eE, 使得 R (G, G) 最小, 其中 G= (V, E, C) 。这个问题能够用 ILP 来表示, 即:上面描述的问题中, 公式 (1) 就是本文需要解决的问题的最终目标。公式 (2) 和公式 (3) 表示网络中节点到自身的最短距离为 0。共式 (4) 和公式 (5) 代表最短路径规则。在公式 (6) 中, x (i, j, d) 代表在网络 G 中, 节点 (i, d) 之间的最短路径是否包含链路 (i, j) , 如果包含则 x (i, j, d) =1, 否则 x (i
14、, j, d) =0。在公式 (7) 中, y (i, j, d) 代表在网络 G中, 节点 (i, d) 之间的最短路径是否包含链路 (i, j) , 如果包含则 y (i, j, d) =1, 否则 y (i, j, d) =0。在公式 (8) 中, 假如 x (i, j, d) =1, 则公式 (8) 和公式 (4) 的表达式是一样的, 相反假如 x (i, j, d) =0, 公式 (8) 的表达式将转化为 w (i, j) +D (i, d, G) -D (j, d, G) 1;在公式 (9) 中, 假如 x (i, j, d) =1, 则公式 (9) 将被转化为 w (i, j)
15、+D (i, d, G) -D (j, d, G) 0, 合并公式 (8) 和公式 (9) , 当 x (i, j, d) =0 时 w (i, j) +D (i, d, G) -D (j, d, G) =0。假如 x (i, j, d) =0, 则公式 (9) 将被转变为 w (i, j) +D (i, d, G) -D (j, d, G) M, M=2*max。在公式 (10) 中, 假如 y (i, j, d) =1, 则公式 (10) 和公式 (5) 的表达式是一样的, 相反假如 y (i, j, d) =0, 公式 (10) 的表达式将转化为 w (i, j) +D (i, d, G
16、) -D (j, d, G) 1;在公式 (11) 中, 假如 y (i, j, d) =1, 则公式 (11) 将被转化为 w (i, j) +D (i, d, G) -D (j, d, G) 0, 合并公式 (10) 和公式 (11) , 当 y (i, j, d) =0 时, w (i, j) +D (i, d, G) -D (j, d, G) =0 假如 y (i, j, d) =0, 公式 (11) 将被转变为 w (i, j) +D (i, d, G) -D (j, d, G) =0, M=2*max。公式 (12) 和公式 (13) 代表链路具有对称性。本文解决的问题可以转化为解决 ILP 的问题。在小拓扑网络中, 我们可以使用cplex 计算器计算出最优结果, 但
