一种面向IPv6的定制化路由备份机制

曾荣飞， 张德永， 王兴伟， 黄 敏

(1. 东北大学 软件学院, 辽宁 沈阳 110169； 2. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169；3. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819)

随着互联网规模的快速增长和网络应用的不断多样化，用户希望能够根据特定的需求和经济承受能力选择合适的服务等级，构建符合需求的网络环境.同时，ISP(Internet service provider)希望用最少的资源获取最大的利润，在分配最少网络资源的情况下满足所有网络用户对网络性能的需求.如何使路由具备定制化能力成为需要解决的问题.

可靠性是计算机网络的另一个研究重点.随着网络规模的不断增大，网络保障流量在故障发生时仍能按照一定约束有效传输是至关重要的.可靠性研究集中在连通性上，路由备份加速了网络故障的恢复时间.

本文将定制化理念与可靠路由相结合，基于IPv6数据平面设计了一种定制化路由备份机制，为网络用户提供差异化的可靠路由保证.

1 相关工作

近年来，服务定制化和多态路由的思想被广泛提出，一些研究者已进行了相关研究并取得成果，进一步增加了网络的智能性[1-2].同时，国内外学者纷纷开展对于服务选择与组合等方面的研究，试图设计更有效的网络架构[3]，然而，较少将定制化思想与网络可靠问题相结合.在网络可靠性上，存在大量有关将最优化方法和QoS相结合的研究工作，旨在提高当前网络的可靠性[4-7].然而，相关工作并未与定制化思想结合，不能在提高可靠性的同时考虑用户和网络服务提供商的效用问题.

IPv6崭新的包头格式和巨大的编址空间为下一代网络的创新和研究提供了有利条件.近年来，许多科学家利用IPv6展开对网络安全与可靠的各方面研究[8-9]，大多集中在IPv6下的QoS(quality of service)问题，如何利用IPv6进行路由备份有待进一步研究.

2 架构设计

面向IPv6的定制化路由备份机制整体架构如图1所示.架构分为服务定制层和数据转发层.服务定制层获取用户需求，对用户需求属性进行分析，计算用户和网络提供商效用，然后定制路由服务策略.

数据转发层包含路由备份模块，从节点备份和路径备份两个方面保证路由的可靠性.节点备份基于IPv6数据平面以路由器优先级为基础，结合路由器发现过程和邻居不可达检测完成.路径备份根据节点相关性和路径相关性计算备份路径.

3 路由定制模块设计

3.1 获取用户需求

系统采集不同类型客户的通讯需求.由于不同情况下用户对QoS的要求存在较大差异，用户可以根据实际需求请求不同的QoS参数并将其存储为用户文档.

3.2 用户需求属性分析

网络对用户的通信需求进行分析，依据不同的通信特征实现对用户请求的分类.定义支持的服务为s，对每一种服务s对应的属性予以定义，并基于服务属性将服务s划分成l种服务等级，如表1所示.

表1 服务等级划分

3.3 效用计算

网络不能只关注用户单方喜好，需要均衡用户和ISP双方的利益，因此对用户和ISP的效用进行计算，在满足用户需求与ISP服务成本和利润之间达到平衡时，制定满足双方利益的最佳路由服务定制策略.

3.3.1 用户效用计算

将用户效用定义为用户对ISP提供服务的满意度.满意度越大，表明用户对网络资源配置更加认可，其效用也就越大.

定义隶属函数:假设应用的QoS需求区间为[BwL,BwH]，[DlL,DlH]，[JtL,JtH]和[LsL,LsH]，某服务能提供的实际QoS参数为bw，dl，jt和ls.

网络带宽越大用户体验越佳，大到一定程度后影响趋于平缓.用户需求的带宽隶属函数为

(1)

式中:BwL和BwH代表用户需要的最小和最大带宽请求；kbw为0到1之间的一个常数，本文设为1；Cbw为隶属函数中横坐标为BwH时的函数值.

延迟、抖动和丢包率越小用户体验越佳.用户需求的延迟、抖动和丢包率的隶属函数可以统一表示为

(2)

式中:PL和PH代表用户需要的延迟、抖动或丢包率的最小值和最大值；kp为0到1之间的一个常数，本文设为1；Cp为隶属函数中横坐标为PH时的函数值.

设延迟、抖动和丢包率的隶属函数分别表示为f(dl),f(jt)和f(ls).根据上述隶属函数构造评价矩阵F=[f(bw)f(dl)f(jt)f(ls)]，同时根据用户需求给出带宽、延迟、抖动和丢包率的权重分别为α,β,γ,λ，并构造权重矩阵W=[αβγλ](0<α,β,γ,λ<1).定义用户定制化服务满意度为S=W·FT，数值越大，表明用户对当前资源配置的满意度越高.根据S划分4个满意度等级，如表2所示.

表2 满意度等级划分

α1,α2,α3根据实际情况设定.用户满意度和用户效用的映射如表3所示，满意等级越高，对应的效用越大.

表3 用户效用与满意度映射

3.3.2 网络服务提供商效用计算

网络服务提供商希望用最少的资源满足用户对网络性能的需求.网络服务提供商效用计算步骤设计如下:

1) 选取与当前节点相连的m个网络服务提供商为候选网络服务提供商.

2) 确定n个评价指标，包括带宽、延迟、抖动和丢包率等.

(3)

4) 计算miny，maxy和midy，分别表示第y个评价指标的极小值、极大值和中间值，如公式(4)～(6)所示.

(4)

(5)

(6)

5) 修正矩阵E:对矩阵E中的每个评价指标值予以标准化处理.对值越大评价越高型指标(如带宽)的标准化处理公式为

(7)

对值越小评价越高型指标(如延迟、抖动和丢包率等)的标准化处理公式为

(8)

6) 计算各评价指标的样本方差，用以反映不同评价指标对综合指标的影响.首先计算每一个候选网络服务提供商对应评价指标y的均值，如式(9)所示.一种评价指标产生的影响要远大于另一种评价指标所造成的影响，则可通过权重系数予以平衡，如式(10)所示.

(9)

(10)

7) 根据各评价指标的样本方差计算出各评价指标所占的权重，所有评价指标的权重总和为1.定义wy为第y个评价指标的权重，计算公式如式(11)与式(12)所示:

(11)

(12)

式中:sy2特指第y个评价指标的样本方差；si2泛指第i个评价指标的样本方差.

8) 对候选网络服务提供商评分:将综合评分转换成相应的得分，并将得分作为候选网络服务提供商的效用，如式(13)所示:

(13)

3.4 路由服务定制策略

网络使用二人博弈，依靠获取的用户需求与链路状态，进行用户与网络服务提供商的供需匹配.博弈对象是用户和网络服务提供商.其中，用户的策略为对当前路径的选择或不选择，网络服务提供商的策略为对当前路径的提供或不提供.构建矩阵如式(14)与式(15)所示.

由于农业生产活动对土地要素具有较强的依赖性，因此多位学者研究表明，应该在C-D生产函数中将耕地投入量引入为解释变量，并且将技术进步看成是时间的函数[3]，新的生产函数为：

(14)

(15)

式中:U为用户效用矩阵；P为网络服务提供商效用矩阵；s0和u0为各自满意的最小值；sk和uk表示用户和网络服务提供商对应的效用.α取大于1的值，当用户没有选择网络服务提供商提供的策略或网络服务提供商没有提供当前的网络服务，则予以惩罚.β取0到1的值，当网络服务提供商没有提供服务但是用户选择，或用户不选择对应网络服务提供商提供的网络服务，则造成损失.若用户没有选择，网络服务提供商也没有提供，则对应的效用为0.在效用矩阵中，如果对应的数值为负，说明用户和网络服务提供商不能达到共赢，不选择该路径.

在效用矩阵U和P中，如果存在最优解(x*,y*)，使得式(16)对应的不等式成立，则认为这样的一种策略是一组Nash均衡解:

(16)

式中:x,y=1或2；axy和bxy分别表示U和P中的取值.如果对应的策略是用户选择该路径，网络服务提供商提供该路径，则该路径为路由服务定制策略得出的路径.如果对应的策略为其他组合，说明路径不是最优解.

在对网络服务分类的基础上，ISP可定义某些服务为可靠性需求高的服务，在保证传输性能的同时进一步在网络连通性上保证这类服务的可靠性.若用户需求为此类服务，则进行节点备份或路径备份，否则结束流程.

4 路由备份模块设计

随着网络技术的飞速发展，网络冗余机制越来越重要.在IPv6新的数据平面上研究网络备份机制具有重要意义.

4.1 节点备份

利用RFC4191在路由器公告报文中添加的Prf(defaut router preference)字段定义路由器优先级，如表4所示.

表4 路由器优先级定义

当优先级高的路由器发生故障时，选择低优先级备份路由器替代.本文设计一种备份节点位置选取方法，见算法1.

算法 1 IPv6备份节点位置选取方法

输入：当前网络环境相关参数，具体包括节点度dv、链路带宽bandwidth、负载load、时延delay、通信代价cost、丢包率loss、候选节点集C,C⊆V

输出:最优备份节点c

BEGIN

1. 将度最大交换机节点cdegree_max加入候选节点 集C

2. 计算交换机节点权重w(v)

3. 根据路由算法求得路径，计算交换机节点到 备份路由器候选位置的传输代价f(v,c)

4. 计算候选位置的平均代价h(c)

5. 选择最小h(c)节点cmeancost_min

6. IF最小h(c)节点数>1

7. 选择度最大交换机节点为最优备份节点c

8. END IF

END

在备份路由器的最优部署决策过程中，有两个因素需要考虑:一个是交换机节点的权重；另外一个是交换机节点到备份路由器候选位置的传输代价.

交换机节点的权重w(v)既体现节点的重要性，又能代表节点流量.使用节点度dv衡量节点的权重，权重w(v)和节点度dv两者之间的函数关系为

(17)

式中，dmax为最大节点度.

f(v,c)为交换机节点到备份路由器的传输代价，在求解过程中，可以通过链路参数进行组合求解.参考用户需求对不同QoS指标的重视程度对指标加权求和并保证权重和为1:

f(v,c)=a·delay+b·bandwidth+c·loss+d·cost+e·load.

(18)

式中:0≤a,b,c,d,e≤1，a+b+c+d+e=1;delay，bandwidth，loss，cost和load表示归一化后的影响因子.

在传输代价f(v,c)的基础上定义数据流请求的平均代价函数:

(19)

式中:n为节点数目；w(v)为节点权重.

计算得出备份路由器在候选位置节点的平均代价.从候选的节点集C中选择平均代价函数最小值的点作为备份路由器的最佳部署节点，若存在多个最优节点，则选择节点度最大的节点部署备份路由器.

4.2 路径备份

路径备份采用多路径路由，备份路径质量qbackup通过链路质量和路径相关性计算.链路质量qlink通过数据传输成功率量化，根据路径相关因子η计算路径的相关性:

qbackup=f×qlink-g×η，

(20)

η=ηnode+ηlink.

(21)

式中:f为链路质量所占比例；g为路径相关因子对应的比例，可以根据需要调整；ηnode为2条路径中相关节点数；ηlink为两条路径中相关链路数.选择备份路径时，根据节点得到的链路信息，计算出所有备份路径被选择的可能性，选择数值最大的路径作为备份路径.使用RSVP协议对备份路径进行资源预留,依据制定的路由策略和路由备份方式在数据转发层进行数据转发.

5 性能评价

5.1 拓扑用例

针对本文提出的一种面向IPv6的定制化路由备份机制，选用CERNET2和INTERNET2两个拓扑进行实验，拓扑结构如图2与图3所示.

5.2 原路由机制

选择原IPv6路由机制作为对比算法.原路由机制指不存在定制化，不均衡用户和ISP效用，无路由备份的原IPv6路由机制.

5.3 应用类型

参考ITU-T标准G.1010，选取多个不同应用类别和相应的QoS指标作为仿真实验中的QoS参数.

5.4 评价指标

选择3个指标对定制化路由备份机制进行性能评价.

1) 路由时间开销:指用户发送建立连接报文到接收失败或成功报文的总时间.

2) 备份路径带宽变化.

3) 恢复响应时间:指主路径失效后，启用备份路由达到路由稳定的时间；在原路由机制中，指主路径失效后重新选路达到路由稳定的时间.

5.5 性能评价

将面向IPv6的定制化路由备份机制分别运行在CERNET2拓扑和INTERNET2拓扑上，得到了下面的对比结果.

1) 路由时间开销:选择2个端点，对每组应用分别运行两种机制各50次，取路由时间开销平均值，观察随服务组数变化两种路由机制的路由时间开销对比.

在CERNET2拓扑下，路由时间开销对比如图4所示，在服务组数较少的情况下，本文提出的路由机制路由时间开销较小.当服务组数多于4组时，随着服务组数的增多，路由时间开销比原路由机制平均多18.8%.在INTERNET2拓扑下展现出同样的趋势，路由时间开销对比如图5所示.在服务组数不大于7的情况下本文机制路由时间开销较小，之后开销相比原路由机制增加，平均多14.7%.

上述实验结果是因为本文设计的面向IPv6的定制化路由备份机制的时间开销主要包括建立连接，为每个应用单独执行路径计算，选择备份路径等，而原路由机制路由时间开销为选路所花费的时间.本机制的路由时间开销随服务组数增多增幅较大，是因为本机制在匹配用户和网络服务提供商后才开始发送数据.总之，本机制的路由时间开销增长在可容忍的范围内.

2) 备份路径带宽:仿真时，选择2个端点，给定带宽约束计算备份路径，先后进行2次实验，观察资源预留与否情况下备份路径带宽资源随时间的变化.

在CERNET2拓扑下，备份路径带宽变化如图6所示，备份路径的带宽资源会随着网络请求的增加逐渐降低，逼近当前服务的带宽约束值.在本机制中，由于使用RSVP预留资源，备份路径带宽资源可以在60 s内100%满足需求，不降到服务的约束值以下.相比之下，原路由机制有11.7%的时间不能满足带宽需求.在INTERNET2拓扑下，备份路径带宽变化如图7所示，备份路径带宽资源同样可以100%满足需求，而原路由机制有36.7%时间不能满足需求.实验证明资源预留对于保证备份路径的有效性起到一定作用.

3) 恢复响应时间:在仿真时，选择2个端点，对每组应用分别运行两种机制各50次，计算恢复响应时间平均值.

在CERNET2拓扑下，恢复响应时间对比如图8所示，两种机制的恢复响应时间变化趋势基本相似.总体上，本文提出的路由机制相比原路由机制恢复响应时间平均短17.2%，这是因为为用户定制了路由备份，加快了路由恢复.在某些情况下本文机制恢复响应时间较长，是因为选择的备份路径已经是其他应用的主路径，带宽资源已被占用，因此在某些情况下可能需要重新选路.在INTERNET2拓扑下，恢复响应时间对比如图9所示，本文提出的路由机制相比原路由机制恢复响应时间平均短35.7%，性能较好.

6 结 论

1) 结合定制化和可靠路由两个问题设计了面向IPv6的定制化路由备份机制，该机制包括路由定制模块和路由备份模块.路由定制模块平衡了用户和网络服务提供商效用，路由备份模块基于IPv6数据平面设计了备份节点选取算法和备份路径计算方法，提高了网络的可靠性.

2) 对设计机制进行了仿真实现，根据实验结果将本机制与IPv6原路由机制进行对比分析.实验验证了本文机制在路由时间开销增加可容忍的前提下，使网络具备了定制化能力，使网络备份在预留带宽和恢复响应时间方面具有一定优势.