基于路径标识的多路径域间路由的开发与实现

摘要：针对现有网络架构中路由扩展性方面的问题日益严重，目前提出一种基于路径标识的多路径域间路由方案，可提高域间路由可扩展性和可靠性，但该研究只停留在理论阶段。现对基于路径标识的多路径路由协议进行了开发与实现，针对域间路由协议BGP的控制层和基于Linu x内核的转发层进行了具体模块的结构分析和开发，并进行了功能性测试。结果显示，开发系统可以实现路径标识路由和多路径路由的功能。
关键词：多路径；路径标识；BGP；内核协议栈

0 引言
近些年来，互联网得到迅猛的发展，中国网民规模已经突破4．2亿，然而，作为其基础支持的路由系统却面临着极大的挑战。路由条目急剧增加，严重地消耗了路由器的计算资源，同时网络阻塞、拥挤、攻击等也会引起网络的失效或不稳定，它们都在很大程度上影响互联网的性能。
一体化网络网的提出，可以有效地解决上述问题。一体化网络是一种新的基于身份位置分离思想的网络体系架。一体化网络体系模型与理论提出接入标识、交换路由标识及其映射理论，建立广义交换路由的概念与机制，在支持安全和移动的基础上实现网络一体化。
延续一体化网络的设计思想，本文实现了一种基于路径标识的多路径域间路由方案。

1 研究背景
针对核心网域问路由，传统网络主要存在可扩展性和可靠性两方面的问题。路由可扩展性主要关注于转发表(FIB)的大小和路由更新的频率。网络用户的剧增、流量工程、策略路由等技术的应用，导致路由前缀不可聚合，使得路由条目呈非线性增长，是限制路由可扩展性的主要原因；路由可靠性主要关注于网络拓扑改变时，路由协议能否快速收敛，提供持续通信的能力。现有域间路由协议BGP只提供一条最佳路由，在路径失效时，需要等待下次收敛才能继续通信，而且域间路由更新的频率十分高，使得收敛时间长达几分钟至十几分钟，是降低路由可靠性的几点原因。
针对上述两个问题，在一体化网络中采用了域内与域问路由相分离，核心网和接入网路由相分离的多路径域间路由方案。核心网域内采用本地标识进行路由，域间采用自治域号(AS)进行路由，保证路由条目的稳定和缓慢增长，提高了路由可扩展性。同时域问路由引入路径标识(PID)标识多条转发路径，在原先的路径失效时可以快速地切换到其他路径，保证了路由的可靠性。

2 基于路径标识的多路径域间路由方案的设计
多路径路域间路由方案主要分为控制层和转发层两部分，其中控制层基于目前经典的域间路由协议(BGP)，主要实现路由的发现、通告和更新。转发层基于Linux内核协议栈，主要实现通告路由的数据包封装解封和转发以及链路失效时的快速收敛。
2．1 控制层的设计
边界网关路由协议(BGP)是目前主流的域间路由协议，它是一种路径向量协议，在AS之间传递网络可达性，并且可以通过检查AS_PATH属性来避免环路。多路径路由方案在域间采用AS号路由，为了标识多条路径引入了路径标识(PID)和下一跳路径标识(NEXT_PID)，从而可以在AS之间通告多条路径。其中PID为从源AS到目的AS之间顺次经过的所有AS号的哈希值，而N]EXT_PID为此路径下一跳AS到目的AS之间所有AS号的哈希值。
基于图1的拓扑图，分析AS 100和AS 200之间传递的UPDATE包的NRLI信息，其基本通信流程为：

(1)首先AS100和AS200分别计算本地的AS号生成本地路由信息，并且在建立邻居关系以后直接发送给对等体路由器。如AS100就将100，HASH(100)，HASH(100)>发送给AS 200。
(2)AS 100和AS 200在收到AS 300通告的路由后，会在邻居关系建立后，将收到AS 300的路由的PID替换为NEXT_PID，将本地AS号加入路径属性中，重新计算PID，然后传递给对等体路由器。如AS 100将300，HASH(100，300)，HASH(300)>发送给AS200。
(3)在下次通告时，AS100和AS200获得了到达对端路由器的信息，及时地通告给对等体路由器，如AS100将200，HASH(100，300，200)>发送给AS200，这时AS200就知道了两条可以到达AS200的路径，实现了简单的多路径。[p]
2．2 转发层的设计
目前的路由器基本都运行在Linux系统中。因为Linux内核提供了完善的网络功能，本方案也是基于Linux内核协议栈。Linux内核协议栈是指网络中各层协议的总和，从上到下依次为应用层、传输层、网络层和网络接口层。其中网络层负责处理网络中的数据包，包括数据包路径的查找、转发、接收等工作。多路径域问路由方案的数据包头主要由传统数据包头和PID、AS号和Local Identifier组成。其中PID和AS号字段用于域间路由使用，Local Iclentifier用于域内路由使用。
多路径域间路由数据包转发的示意图如图2所示。

收到数据包需要按如下步骤进行转发：
(1)检查PID字段是否为空，如果为空，则匹配AS号，根据匹配项填充PID字段，根据查询到的PID进行平面查找内核路由表，并将数据包转发到相应的端口上。
(2)如果PID字段不为空，则用平面查找方式匹配PID，如果有匹配项，路由器根据匹配项转发到对应端口；如果没有匹配的PID，再根据标志位，置位的路由器可以按匹配目的AS号的方法对数据包进行转发，没有置位的则将数据包丢弃。
(3)当数据包跨出本AS域转发到下一个AS域时，PID字段需替换成路由条目中NEXT_PID；当PID为本地AS的哈希值时，表明数据包此时已经到达目的AS，此时需交由域内路由协议用Destination Local Identier进行转发。

3 基于路径标识的多路径域间路由方案的实现
多路径域间路由方案实现模块图如图3所示，其中控制层模块主要实现UPDATE消息的产生、交互和处理，并且提供了一些配置和显示命令。在多路径域间路由方案中只需要修改NLRI模块、UPDATE消息处理模块、平面路由表模块和配置、显示命令模块，其他部分可以沿用BGP的设计。RTM模块主要实现控制层和转发层之间的交互，原始数据包的提交和路由信息的下发。转发层模块实现平面转发表的构建、数据包的封装和解封，以及具体的数据包转发流程。

3．1 NRLI模块
该模块主要实现在AS之间传递路由可达消息。在BGP中被设计成(长度，前缀)二元组，为了兼容多路径域间路由方案，需要修改成长度，前缀，PID，AS>四元组，使之既可以满足多路径域间路由的需要，也可以兼容现有的路由方式。[p]
3．2 UPDATE消息处理模块
该模块主要实现UPDATE消息的发送和接收。在BGP当中用来在对等体之问传递可用路由前缀、撤销路由等，在多路径域间方案中需要修改数据包发送函数和接收函数，使之能够正常地传递新的网络可达性信息，同时需要修改包安全性检查等函数，使之能够不被错误地丢弃。
3．3 平面路由表模块
该模块主要实现在控制层维护核心路由表，并向转发层下发最佳转发信息。BGP的路由表是基于最长前缀匹配的方式查找的，用二又树具体组织。在多路径域间路由方案中需要将其平面化，利用PID和AS号来检索域间路由，利用HASH算法将路由节点信息存储在一个双向链表上面，实行了精确查找。
3．4 配置、显示和调试命令模块
该模块主要实现多路径域间路由协议的配置，并且提供了一些显示核心路由表、对等体状态等的显示命令，还有一些路由器故障时的调试命令。相对于BGP，在多路径域间路由方案中添加了以下的命令：
(1)路由显示命令
通过该命令可以遍历多路径域间路由协议的核心路由表，显示具体路由信息，即到目的AS的具体路由信息，包括PID、NEXT_PID和具体路径显示。
(2)路径选择命令
因为在多路径路由方案中，在控制层可以发现多条路径，通过该命令可以选择控制层向转发层通告的最佳路径，在当前链路失效时选择备份路径下达到转发层，实现链路的快速收敛，最终完成了转发路径的可控。
3．5 RTM模块
该模块主要实现转发层模块和控制层模块之间的消息交互。多路径域间路由协议在控制层拥有自己的核心路由表，但最终对转发其作用的是转发层的内核路由表，但是控制层不能对内核路由表直接起作用，该模块实现了两者之间的信息交互。它们之间的通信是通过套接字NET LINK起作用的，在公共消息格式中添加标识路由所需的PID、AS号和NEXT_PID等信息，满足标识路由在转发层的需要。
3．6 平面转发表模块
该模块主要实现多路径域问路由在转发层核心路由表的维护，当需要出路网络流量的发送和接收时查询该路由表。
Linux内核的转发表是基于网络掩码的HASH表组织的，根据不同的网络掩码长度被组织成不同的HASH表。因为IPv4使用32位地址，所以IPv4中有33个不同的网络掩码长度，可对应于一个IP地址。fib_table数据结构来描述路由表。fib_table结构包含一个由33个指针组成的向量，每个指针对应一个网络掩码并指向一个类型为fn_zone的数据结构。Fn_zone结构将路由组织成HASH表，因此通向目的网络的路由，如果网络掩码长度相同，就被放在同一个HASH表内。每个单独的子网对应一个fib_node实例，用变量fn_key(网络掩码)识别，它的值就表明该子网。在查找函数fn_hash_lookup中，也是通过遍历路由表搜索关键词fn_key，获得最终结果。
多路径路由方案中，转发时需要检查PID，并根据PID进行检索和转发，因此需要修改转发表，使之可以根据关键词PID进行查找。在查找时，只需要根据PID进行精确匹配，而不用计算网络掩码。在修改后的路由节点fib_bgp_node中，添加了PID的信息，使得修改后的路由表fib _bgp_table可以根据PID为关键词索引。路由表结构如图4所示。

3．7 数据包封装解封模块
该模块主要实现数据包中标识的转换，Linux内核中采用IP地址进行路由，而在多路径域间路由方案中，在域间有需要才用AS号路由，因此需要在发送数据包时，添加PID、目的AS号和源AS号等信息，但为了兼容现有的网络架构，方便现有网络其他服务的处理，在数据包进入网络层前，去除PID、目的AS号、源AS号等扩展选项。只是在数据包离开网络层后，才增减以上扩展选项。修改后的数据包头如图5所示。
3．8 数据包转发处理模块
该模块主要实现基于PID的数据包转发，同时维护一个PID、AS号和NEXT_PID一一对应的查询表，实现到目的AS路径标识PID的填充。Lin ux内核是基于IP地址前缀路由的，而在多路径域间路由方案中是基于AS号，在查询平面转发表要使用PID，如果数据包是终端第一次经过路由器时，不存在PID等信息，需要根据目的AS号添加PID等信息，还有域内路由时根据设计要使用Local Identiner，只有在数据包进入Linux内核网络层前，进行了该模块处理，才能完成标识路由的功能。

4 基于路径标识的多路径域间路由方案的功能验证
多路径域间路由方案的功能验证，主要包括控制层基于路径标识的多路径路由发现和转发层基于路径标识的数据包正常转发。[p]
4．1 测试平台及拓扑
全部系统采用普通的x86系列的PC；测试环境的核心网路由器配置至少两个以上的网卡，无线或有线均可；所有充当路由器都应该安装Linux操作系统，内核版本为2．6．28；测试的拓扑如图6所示，对各个功能实体进行地址和路由配置，在所有路由器都需要安装文中提到的修改后的BGP路由软件和相应的内核软件。

4．2 控制层基于路径标识的多路径路由发现
AR1为AS号为100的一台路由器，AR2，AR3分别为AS号为200，300的路由器，其中AR1的BGP配置如图7所示。
其他路由器配置与AR1类似，通过配置使得AR1，AR2，AR3之间建立了EBGP关系对等体关系，通过show ip bgp命令查看AR1的路由表，内容如图8所示。

AR1学习到了到达3个AS域的路由信息，学习到了到本地AS域100的路由，其中PID和NEXT_PID一致，并且默认权重为32 768；到达AS域300的路径则有两条，分别为“300i”和“200 300i”，表明到达AS域300的路径可以是直接到达AS域300，PID为f78aac78，NEXT_PID为809d3a9 0，也可以是通过AS域200到达AS域300，PID为7a5flfe8，NEXT_PID为33f960c4，可见PID和NEXT_PID均不一致，可以通过PID和NEXT_PID区分不同的路径，通过测试，可以看出本方案在控制层可以正确地发现基于路径标识的多条路径。
4．3 转发层基于路径标识的数据包正常转发
基于路径标识的数据包转发是多路径域间路由的重要功能，首先用AR1向AR2发送ping包，也就是AS域100向AS域200发送ping包，在AS 200的内核编写打印语句，打印出数据包添加的PID，NEXT_PID和AS号，结果如图9所示。

可见，在ping包已经正确地添加了域间路由所需的PID，NEXT_PID和AS号等信息。利用wireshark抓包工具进行测试，可以成功地获取icmp包，证明两个AS域之间可以实现基于路径标识的数据包转发。

5 结语
在实际搭建的拓扑中，实现了基于路径标识的多路径路由方案，并且进行了功能验证。结果表明，可以正确地发现多路径路由，并且可以实现基于路径标识PID的数据包转发。本文实现了基于路径标识的多路径域问路由方案，快速实现链路失效时的重新收敛，将成为下一步研究的重点。