网络出口流量的多径路由处理机制

周媛媛,陈文龙,赵成安,唐晓岚 ,郭思聪

1(首都师范大学 信息工程学院,北京 100048)2(首都师范大学 管理学院,北京 100048)3(陆军炮兵防空兵学院 士官学校,沈阳 110867)

1 引 言

互联网单径路由传输过多依赖最短路径或最优路径,这种传输模式容易导致负载不均、链路拥塞等问题.多径路由的提出对解决上述问题提供了帮助,但现有多径路由机制在实施灵活性等方面还不够理想.已实际部署的典型多径传输机制中,多协议标签交换技术(MPLS)对报文的再次封装会增加数据负载,且主要适用于运营商自治域网络；策略路由方案因为静态配置导致效率较低,也无法随网络拓扑状态变化动态调整.

本文针对互联网的出口流量进行优化控制,提出网络出口流量的多径路由处理机制(MET).在传统流量传输基础上加入二维路由元素,以此控制网络中外访流量的出口网关及路径的选择.并且,针对网络中发生频率较高的单链路、单节点故障问题,提出MET的改进方案：BMET,即通过预先为重要故障设置备份路径并计算路径切换点,实现备份路径的快速切换.

本文主要贡献包括：1)提出了MET机制,基于二维路由高效控制外访流量的出口网关；MET不增加任何报文负载,并与已有一维转发兼容共存；2)针对网络中发生频率较高的单点故障问题对MET机制进行优化改进,通过预先计算备份路径及最优切换点位置,实现重要故障后的路径快速切换,提升数据传输的可靠性.

本文的结构组织如下：第2部分介绍了相关研究及背景;然后在第3部分描述MET机制的主要思想及实施办法;在第4部分,对MET机制进行改进,实现重要故障后路径的快速切换;第5部分对MET机制进行模拟仿真,并对实验结果进行分析;第6部分总结了全文.

2 相关研究

多宿主方式(Multi-homing)往往被应用于末节网络中来增强其网络连接的可靠性.文献[1]将多宿主简单定义为拥有多个外部链接的网络.文献[2]研究分析了多宿主网络,他们认为多宿主可以显著提高网络性能,并通过大量数据证明了多宿主的可靠性.二维路由可以同时根据源地址与目的地址进行选路,并在实现多宿主技术、多路径路由等方面均具有很大的优势.文献[3]基于二维路由研究域间流量工程,利用二维路由能够细分流量的特点,细粒度的进行流量调度,充分展现了二维路由的优势.文献[4]同样对流量工程问题进行了讨论.

多路径路由(MRP)因其在实现低能量消耗、负载均衡、避免拥塞发生等方面具有的重要作用,长期以来一直是学者们研究的热点话题.网络中使用最多同时也最为普遍的是等价多路径路由(ECMP[5]),ECMP沿着多个相等代价的路径进行流量的传输,虽然多个路径可以对流量进行分担,但其路径选择是静态确定的,不能对变化的网络环境及时的做出反应.文献[6]对数据中心网络流量进行研究,发现使用ECMP算法易将多条大数据流转发至同一链路,导致链路瓶颈.多路径路由在链路或节点故障恢复方面也具有一定的意义,文献[7]提出了多路由机制(MRC),通过预先计算备份路径以确保IP网络中链路或节点故障的快速恢复.从负载均衡角度出发,文献[8]提出了一种具有负载均衡功能的多网关路由协议,由此均衡整个网络的负载,避免拥塞的发生.文献[9]设计并实现一种动态负载均衡策略,并对其性能进行验证.不相交的多路径路由的提出对避免路径之间争用带宽以及提高流量传输安全性产生了很大的作用[10,11],文献[12]对MRC继续深入研究,提出了不相交的多路由机制(D-MRC),使得求出的备份路径互不相交.同样基于多路径路由,文献[13]设计了分级拓扑可信机制,为不同级别的流量提供不同的传输路径,实现数据的可信传输.

如今,由于互联网的普及,网络已逐渐渗透到人们的工作、生活当中.尤其在电子商务领域中,即使是一个短暂的服务中断,也会造成巨大的经济损失.不幸的是,由于多种原因,网络故障时有发生,即使是在管理良好的网络中.文献[14]对IP主干网故障特征进行研究,发现大约85%的故障为单个链路或路由器故障所致.传统的链路状态路由协议如OSPF通过链路状态广播以及路由表的重计算来应对链路故障,这种反应方式会导致严重的转发中断问题.针对这一情况,文献[15]提出了故障不敏感路由(FIR)这种主动式的域内路由方法,对于任何的单链路故障能够很好的处理,但是一旦遇到由单个节点引起的多条链路同时失效时,则会产生环路.针对这个问题,文献[16]基于FIR,提出了基于快速重路由的故障推理方法(FIFR),不仅可以解决单链路故障,也可以对单节点故障进行有效的处理.为了减少故障反应时间,IETF确定了一个框架,称为IP快速重路由(IPFRR[17]),IPFRR基于本地路由变更和预计算绕行两个准则.文献[18]提出了无环路变更的方法(LFA),LFA简单、易于部署,具有很高的商业价值.但是,大量的数值研究表明[19],LFA只能对75-85%的链路故障以及50-75%的节点故障提供保护.因此,文献[20]中专注于LFA故障覆盖率的分析,提出了提高LFA故障覆盖率的方法,即通过使用贪心算法向拓扑中增加2-4条新的链路,就会达到接近于LFA的完全覆盖.

3 MET机制及实施办法

本文针对多出口网络的外访流量进行优化控制,提出网络出口流量的多径路由处理机制(MET).MET可基于源、目的IP前缀指定外访流量的出口网关.便于分析,本文令特定接入路由器的所有外访流量总是经相同的边界网关路由器进行传输.即对于外访流量,接入路由器会与唯一的出口网关绑定.

图1 外访流量控制示例图Fig.1 Outgoing traffic control example

针对图1进行分析,令M、N为自治域的2个出口网关,有A～F共6个接入路由器.该区域的流量策略是：A、B、D、F通过M向外传输流量；C、E通过N负责向外传输流量.

二维转发的重要优势就是与现有一维转发不冲突.对于网络中最普遍使用的出口网关,服务的流量仍使用现有一维转发完成对外传输,从而减少二维转发的部署,降低各项代价.

定义 1.令自治域中默认出口网关为DEr,自治域的外访流量默认情况基于一维转发传输到DEr.

DEr基于传统域内路由协议在自治域中发布外部IP前缀,无法获得二维转发传输服务的外访流量都经DEr传输.图1中,经出口网关M负责最多的外访流量传输,可设置M为DEr,所以A、B、D、F的外访流量基于一维转发传输.

定义 2.令提供二维转发服务的出口网关为TEr,它可为外访流量提供高性能或特定功能的转发服务(区别于DEr).自治域中,TEr提供服务的流量基于二维转发传输到TEr.

由于不同出口网关提供二维转发传输服务时,相互之间没有任何影响,所以本节分析单个出口网关的二维转发设计,二维转发基于OSPF协议扩展来实施.二维转发机制的主要设计思想如下：首先,TEr配置其服务的二维转发流量,以源、目的IP前缀对描述外访流量；然后,TEr发布二维LSA消息通告自治域内节点,路由节点根据收到二维LSA部署二维转发项,构建二维转发路径.

上述过程中,若沿用现有的洪泛机制发送二维LSA通告,各项代价较大.由于每个二维转发项总是针对特定源IP前缀部署,只需自治域中的部分路由节点对其关注.因此,针对每个二维转发项,可以先计算出自治域内接受服务的特定用户到指定出口网关的最优路径,并沿该最优路径的逆路径进行二维LSA消息的发布.该方法可以在最小范围通告链路状态信息,减少控制层开销,实现二维转发路径的高效建立.而且,每个二维转发项只在部分路由节点存储也可降低数据层的二维转发项存储开销.

令自治域网络表示为G,其中,R为路由器集合,E表示链路集合.令提供二维转发服务的出口网关为TEr,接受服务的接入路由器为ACr,PS是接受该服务的用户IP前缀(源IP)集合,PS对应的子网经接入路由器连入互联网,PD是该转发服务的可达目的IP前缀集合.通过报文源IP和目的IP对目标流量进行描述,该流量集合表示为：

(1)

定义 3.令ACr到TEr最优二维转发路径(最短路径)记为：Path(ACr,TEr)={r1,r2,…,rm},其中r1=ACr,rm=TEr.

由于任意2个节点间的往返路径经过的节点相同,所以,二维LSA消息发布的路径即为ACr到TEr最优二维转发路径的逆路径,即Path-(ACr,TEr)={rm,rm-1,…r1}.其中r1=ACr,rm=TEr.

图2 构建二维转发路径示例拓扑Fig. 2 Example topology of building a two-dimensional forwarding path

图2为构建最优二维转发路径示例拓扑.其中,令s为ACr,d为TEr.则二维转发路径为s-a-e-f-c-d,二维LSA消息发布路径为d-c-f-e-a-s.构建二维转发路径时,d首先发送二维LSA通告到c,c接收到LSA通告后,生成下一跳为d的二维转发项,并且继续向f发布此二维LSA.后续节点同理构建二维转发路径.

4 MET优化

现有互联网中,由于路由器损坏、网络维护、配置错误等多种原因导致的网络故障仍时有发生.文献[14]对于IP骨干网中的故障特征进行研究,发现网络中大约85%的故障为单个链路或路由器故障所致.为此,本文针对最优二维路径中最易发生的单个链路及节点故障问题预先计算备份路径,并研究分析故障发生后两路径间切换的最佳节点.以此达到在尽量少的节点中部署二维转发项,减小控制层开销并提升部署效率.

MET中,一旦网络状态发生变化,如：增加新的节点/链路或删除已有的节点/链路,会由TEr触发二维转发路径的维护.此时,需要注意将路径切换对数据传输的影响降至最低,本文主要分以下2种情况分析：

1)若有更优转发路径出现,可待新路径构建完成后再撤除当前转发路径；

2)若现有转发路径发生故障,则必定导致数据传输出现一段时间的中断.因此,本文设计了针对重要故障的备份路径快速切换机制.

4.1 确定重要节点及链路

现有网络中,单链路故障或单个路由器所引发的故障发生频率极高.通过一段时间对网络的监控观察,可以很容易找出网络中某路径中最易发生故障的链路及节点.由于其对网络影响较大,我们称其为重要链路、重要节点,并将重要链路或重要节点所引发的故障称为重要故障.

定义 4.令二维转发路径Path(ACr,TEr)的链路集合为ETP,路径中最易发生故障的链路为重要链路：Ie,有Ie∈ETP.

定义 5.令二维转发路径Path(ACr,TEr)的节点集合为RTP,路径中最易发生故障的节点为重要节点：Ir,Ir∈RTP.令它的直连链路集合为Eco{Ir}.

4.2 计算备份路径及路径的切换

针对区域中发生可能性较大的单链路故障、单节点故障的问题,我们通过为重要链路、重要节点设置备份路径的方法来解决.

令B-Path(ACr,TEr)为自治域内去除重要链路或重要节点后,ACr到TEr的最优路径,我们称B-Path(ACr,TEr)为二维转发路径Path(ACr,TEr)的备份路径.其中,B-Path(ACr,TEr) ={rb1,rb2,…rbm},rb1=ACr,rbm=TEr.

若为重要链路故障,则更新拓扑表示为：

若为重要节点故障,则更新拓扑表示为：

定义 6.令STr为路径切换负责节点,即二维转发路路径Path(ACr,TEr)以及备份路径B-Path(ACr,TEr)在故障发生时的关键切换点.

图3 备份路径更换拓扑Fig.3 Path switching topology

STr满足2个约束条件：1)它是2条转发路径的公共节点；2)它在2条路径中的转发下一跳不同.

即：(STr=rpi=rbj)∧(rpi+1≠rbj+1).

显然,只要备份路径存在,就必定存在STr.Path(ACr,TEr)中,STr一定出现在ACr到Ir或者Ie的直连节点之前,它可能是ACr,但一定不会是TEr.

图3为备份路径更换拓扑示例,其中,图3(a)、图3(b)为链路(c,e)发生故障时备份路径更新拓扑图.图3(c)、图3(d)为节点e发生故障时的示例图.可以看到,当故障发生时,不是由ACr进行二维转发路径与备份路径之间的切换,而是由距离故障链路或节点更为相近的带阴影节点完成此项操作,这样不仅可以减少数据转发量,更可以很大程度上缩短收敛时间,达到二维转发路径与备份路径之间的快速切换.

4.3 下发针对备份路径的二维转发项

和最优二维转发路径一样,我们同时也针对备份路径上的部分节点下发二维转发项,一旦重要链路或重要节点发生故障,只需STr获知该网络状态发生的变化,即可完成二维转发路径的快速切换.

RTP表示最优二维转发路径上的所有节点的集合,RB-TP表示备份二维路径上所有节点的集合.令集合RB-deploy表示备份路径上需要进行二维转发项部署的节点集,满足：RB-deploy=RB-TP-RTP+{STr}.

需要对RB-deploy中所有节点下发二维转发项.其中,STr只是存储针对RB-TP的二维转发项,并不生效.一旦重要链路/节点发生故障,只需STr获知该网络状态所发生的变化,就可以迅速完成二维转发路径的切换.即,路径切换负责节点STr删除针对RTP的二维转发项,并使RB-TP的二维转发项生效.图3(a)中,针对s到d的二维转发项,c节点生效的下一跳节点为e,当c感知到c-e链路故障,立刻将下一跳切换为m.易知,STr为最后一个同时出现在2个有序集合中的节点.

STr节点的算法如下,即在RTP和RB-TP中,寻找最后一个同时出现在2个有序集合中的节点.

Algorithm1.CalculationofSTr

Node*switch_node(RTP,RB-TP)

{

Get the first node ofRTP：r1;

Get the first node ofRB-TP：r2;

While(r1==r2)

{

STr=r1;

r1=r1->next;

r2=r2->next;

}

returnSTr;

}

5 实验评估

1条二维转发项所占存储空间包括：4字节源IP网段、4字节目的IP网段、4字节下一跳地址、1字节源IP子网掩码长度、1字节目的IP子网掩码长度、2字节出接口号,共计16字节.令自治域中路由节点数：NA=|R|.给定1条二维转发项,需要部署的节点数为：NT,其占用存储空间为16*NT.对于普通MET机制,需进行二维转发项部署的节点数为：NT= |Rp|.对于改进的MET机制(BMET),需进行二维转发项部署的节点数为：NT= |Rbp|.显然,使用优化的MET方法需要进行二维转发项部署的节点数更多.同时,对于不同拓扑中的不同二维转发项,其二维转发路径和备份路径都会有所不同,部署节点数也不同.不过,对于OSPF现有洪泛链路状态机制(Flooding),则会将1条二维转发项在自治域中除出口路由器外的所有路由器节点生成,即：NT=|R|-1.

通过仿真研究MET机制与OSPF现有洪泛链路状态机制下二维转发项部署节点数以及内存消耗情况.假定ACr与TEr所携带的IP前缀数量均为10,并将3个方法应用于四种拓扑：ANS,Abilene,NSFNET,ARPANET[21,22].每个拓扑中选择10个随机样本,不同随机样本具有不同的接入路由器、默认出口路由器以及提供二维转发服务的出口路由器,并假定重要节点及链路.在计算每种方法需部署二维转发项的节点数后,可分析对应的内存消耗情况.

图4 针对重要节点故障部署二维转发项所需存储消耗Fig.4 Storage consumption required to deploy two-dimensional forwarding items for important node failures

图4、图5分别为重要链路故障、重要节点故障情况下,在4个不同拓扑中使用MET、BMET以及OSPF现有洪泛链路状态机制(Flooding)3种方法部署二维转发项所需要的内存消耗情况.OSPF现有洪泛链路状态机制(Flooding)由于需要对二维链路状态信息进行全网洪泛,所以需要部署二维转发项的节点数量最多,所需内存消耗最大.MET方法只需在接入路由器ACr到出口路由器TEr的最优路径上进行二维转发项的部署,需部署节点数最少,因此所需内存消耗最小.改进的MET方法(BMET)除需要在最优路径上部署二维转发项,还需将其部署到备份路径上.相比于MET方法会增加一定的内存消耗.

图5 针对重要链路故障部署二维转发项所需存储消耗Fig.5 Storage consumption required to deploy two-dimensional forwarding items for important link failures

由图4、图5可以看出,4种拓扑中,使用我们提出的MET方法相比于OSPF现有洪泛链路状态机制(Flooding)所需的内存消耗情况有了明显的改善,可以节约更多的内存空间.而改进的MET方法相较于普通的MET方法虽然需要更多内存空间,但当重要故障发生时可以很快的对故障进行反应,切换到备份路径,减少收敛时间.

6 总 结

本文针对互联网的出口流量进行优化控制,提出网络出口流量的多径路由处理机制：MET.即在传统流量传输基础上加入二维路由元素,基于源、目的IP前缀实现更细粒度的外访流量控制.其中,自治域内路由器到指定出口的流量传输基于二维转发实现,因此无需考虑其与自治域内现有一维转发路径的冲突,可提升多径路由的实施灵活性.MET机制的部署代价主要体现在二维LSA消息的传播及二维转发项的部署上,针对此种情况,我们对构建最优二维转发路径进行讨论,并只沿此最优路径传播二维LSA消息及进行二维转发项的部署.

此外,针对网络中发生频率较高的单链路、单节点故障问题,提出MET机制的改进方案：BMET,即通过预先为重要故障设置备份路径并计算路径切换点,实现备份路径的快速切换.后续,我们将对多出口网络的外访流量进行更深入的研究.