刘金生，陈石
（中国联合网络通信有限公司 网络运维部综合监控处，北京 100033）
摘要：在多链路互联的BGP邻居之间实现流量按需负载分担，可以有效提高链路利用率，降低组网成本，但目前常见的实现方法要么对硬件性能要求较高，要么配置复杂，不易在较大网络特别是电信运营商网内灵活部署。利用BGP路由寻址的特点，采用多重递归的方式，实现了按链路带宽的比例分配流量的非等价负载分担。这种方法原理简单，易于操作，具备较好的扩展性。
关键词：边界网关协议；等价多路径；非等价负载分担；递归寻址；选路原则
0引言
数据流量的多链路负载分担技术在互联网界应用广泛，对应不同的网络结构和需求，解决方案不尽相同。本文提供的非等价负载分担方案基于路由寻址算法和BGP“下一跳”的递归属性，与常见的策略路由方式相比，该方案配置更简单，部署更加灵活。
1等价负载分担
Internet是由众多相互联在一起的自治系统（Autonomous System）组成的，为这些自治系统提供路由交换功能的协议就是边界网关协议（BGP）［1］。为了保障BGP协议自身的健壮性和稳定性，BGP协议规定了13条选路原则，所有开启BGP功能的路由器都严格遵守这些选路原则。
根据这13条选路原则，BGP协议默认不支持等价路径，也就是说BGP数据库中到达同一个目的IP只有一条最优的路由会被放入路由表。
基于网络可靠性的考虑，很多企业网在与电信运营商互联时采用了双归、甚至多上联的拓扑结构。为了提高数据传送的效率和可靠性，对于这种多链路互联的BGP邻居，BGP协议在设计之初也保留了一个后门，即“等价多路径”（Equal Cost MultiPath，ECMP）功能，一旦启用了这一功能，对于同一目的IP，BGP协议允许最多可以有6条等价路径被放入路由表中。
如图1所示，自治系统AS100和AS200通过边界路由器R1和R2建立了BGP邻居关系。R1和R2之间有两条直连的物理链路。当AS100内的用户访问AS200内的服务器时，在R1和R2上开启ECMP功能，两个自治系统之间的流量就会按照1∶1的比例加载到两条直连链路上，而不是只选择其中一条链路进行数据流量的传递。
这样看，ECMP解决了多链路流量负载均担问题，在一定程度上提高了网络的可靠性。目前，国内主要电信运营商已把ECMP功能作为BGP接入的备选方案向用户推荐，各主流电信设备供应商如思科、华为、Junior、中兴等也纷纷宣布支持这一功能。
2非等价负载分担的提出
仍以图1为例，R1和R2之间的两条物理链路，第一条是点到点的串行链路，假设带宽为2.5 Gb/s；第二条是广播型的以太网链路，假设为带宽为10 Gb/s。如果在R1和R2上开启ECMP功能，则每条链路最大流量不能超过2.5 Gb/s，否则串行链路就会因流量超过带宽值而丢包，此时的以太网链路尚有10 Gb/s-2.5 Gb/s=7.5 Gb/s的带宽处于闲置状态。
如何既能够让去往同一目的IP的流量承载在不同的链路上，又能够让带宽高的链路能者多劳？就此提出了非等价负载分担的需求。
目前实现非等价负载分担常见方法包括：策略路由、流量工程、MPLSVPN等。这些方法要么对设备的性能要求较高，要么需要BGP邻居之间密切配合，对各种数据流进行分类和打标记，并在路由进行收发双向控制，配置过程复杂，无法根据业务流量和中继链路的变化灵活地部署，扩展性差［2］。
3路由寻址与递归过程
路由寻址算法的本质就是在路由表中实现对目的IP地址前缀的最长匹配［3］。
图2路由寻址的哈希过程如图2所示，目的IP一旦被放入路由表，它的前缀同时就被哈希到特定的桶中，寻址的过程就是从哈希表中的第一个记录开始，对被哈希的关键字与给定值（即掩码值，从32到0）逐个进行比较，当某个哈希的关键字与给定值完全相等时，则查找成功，路由协议会根据所查的记录将包含目的IP数据包送入对应的出接口；否则，若直到最后一个记录，其关键字和给定值比较都不相等，则查找失败，包含目的IP的数据包被送入默认网关（若未设默认网关，则该数据包被丢弃）。
路由寻址哈希算法描述［4］如下：
int Search(int d,int a［］,int n)
/*在数组a［］中查找等于D元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/
int i；
/*从后往前查找*/
for(i=n-1;a!=d;--i)
return i ;
/*如果找不到，则i为0*/
事实上，路由寻址算法还包含了递归的过程，即寻找数据包下一跳的过程路由的三元素包括：目标地址、掩码、下一跳。只有计算出有效的下一跳，IP协议才能逐跳地将数据包送往目的地。
所谓有效的下一跳，对于路由器而言分为两个层面。从转发层面（FIB：转发信息库）看，就是本路由器到达目的IP所经的出接口。从控制层面（RIB：路由信息库）看，就是在路由表中进行最长掩码匹配的哈希算法查找的结果，是一个IP地址，如果这个IP地址对应一个直连出接口，它就是一个有效的下一跳，可以被直接映射到转发表中，参与指导数据包的转发［5］；如果这个IP地址没有对应的直连出接口，则不能称之为有效的下一跳，需要进行递归查找，最终找到对应的直连出接口为止。
如图3所示，在BGP路由表中，R0到达Server的下一跳是R3，到达R3的下一跳是R2，到达R2的下一跳是R1，以此类推。IP协议在查找路由时，如果发现下一跳不是与自己直连的，那么就会将此下一跳地址作为目的IP再次按照上述逻辑查找路由表，直到查到与自己直连的下
一跳或者完全失败为止，这就是路由的递归查找。
递归过程算法描述如下：
CheckNode{
int A;
int B;
Node children［1<<B］;
}
union Node{
Leaf entry;
CheckNode node;
}
由于查找下一跳的次数不是固定的（用A表示），并且经过本次递归查找后下一跳是否有对应的直连接口也不确定（用B表示），因此每一轮递归查找就是一个CheckNode过程。
4案例实现
仍以图1为例，AS100网内的用户希望向AS200网内的文件服务器（IP地址200.0.0.1）传送文件，并且希望在传送过程中根据两条互联链路带宽的比例（2.5 Gb/s∶10 Gb/s=1∶4）分配数据流量。具体配置如表1所示。表1R1和R2的初始配置设备名R1R2Loopback0接口IP地址1.1.1.1/322.2.2.2/32链路带宽链路流量占比
需求（共5份）R1R2Serial5/112.0.0.1/2412.0.0.2/242.5 Gb/s1份R1R2GigabitEthernet1/021.0.0.1/2421.0.0.2/2410 Gb/s4份
本例中R1与R2通过双方的环回口（loopback0）建立EBGP邻居关系，因此对R1而言，到达AS200网内的目的IP200.0.0.1的下一跳地址就是R2的loopback0的地址2.2.2.2。
（1）第一步：指定新的目的IP和下一跳地址
为了通过递归寻址影响BGP的选路，在R1侧，把2.2.2.2/32作为新的目的IP，并分配5个虚拟IP地址作为它的下一跳（之所以选择5个虚拟IP地址，是因为链路带宽比例为1∶4，可以理解为需要把数据流量分成1+4=5份）。
完成配置后，检查到达2.2.2.2/32的路由。如图4所示，每个下一跳均为“traffic share count is 1”，代表这5个下一跳之间是等价的。注意：由于这些虚拟IP地址仅用于本地路由表的递归寻址，并不需要广播到互联网中，因此建议使用私网地址，本例中使用的是192.168.1.1~192.168.1.5。
（2）第二步：将虚拟下一跳引入路由表
根据实际链路的带宽比例（1∶4）为这些下一跳地址分配出接口（本例中串口被分配1次，以太口被分配4次），如图5所示。
虚拟下一跳地址一旦关联了出接口，指向虚拟IP地址的静态路由就变了合法的路由，将被放入路由表中，参与对目的IP的递归寻址过程（查找有效的下一跳）。
（3）第三步：寻址过程分析
从控制层面看（如图6所示），在R1的路由表（RIB）中查找到达目的IP200.0.0.1的路由，首先会查到它的下一跳地址2.2.2.2，但由于没有对应的出接口，需要进行一次递归查找；以2.2.2.2作为目的IP，经过第一次递归查找，发现到达2.2.2.2有5个等价的下一跳地址，分别是192.168.1.1~192.168.1.5，由于这5个下一跳依然没有对应的出接口，因此需要再进行一次递归查找；经过第二次递归查找，5个下一跳都找到了对应的出接口，路由寻址过程结束［6］。
从转发层面看（如图7所示），转发表（FIB）中去往目的IP 200.0.0.1的数据包被等价地分配到5个出口：1份流量由点到点的串口链路（Serial5/1）承载，剩下的4份流量由广播型的以太口链路（Gigabit1/0）承载。
这样就实现了预先设定的需求：在两条链路上实现按1∶4的流量进行转发，即非等价负载分担。
5结论
实际案例证明：在路由寻址中增加一次递归过程，可以比较灵活地实现等价或非等价负载分担。相比常用的策略路由，这种方法不需要对特定的数据流量进行分类标记，在配置上更简单，另外用于递归算法的下一跳使用的是私网地址，不消耗公网资源，部署起来也比较方便。
这里需要强调的是，本例中的EBGP邻居R1和R2并未打开等价多路径（ECMP）功能，对于目的IP200.0.0.1，在R1的BGP数据库中只有2.2.2.2/32这一个下一跳，而不是多个下一跳。也就是说本方法并不是在BGP协议内实现非等价负载分担，而是借用BGP协议中“下一跳”的概念，通过路由表中的多重递归实现流量非等价分担的效果，因此这与BGP的等价多路径选路原则并不矛盾。
另外，本例中介绍的非等价负载分担方法适用于通过环回口建立的EBGP邻居。对于通过直连接口建立的EBGP邻居，可以在双方的直连接口上配置若干个second IP作为到目的IP的下一跳地址，再经过路由递归查找，也能实现非等价负载均衡的效果，具体配置方法本文不再赘述。
参考文献
［1］ STEWART J.BGP4: interdomain routing in the Internet［M］．USA Addison Wesley，1998.
［2］ 萨姆·哈拉比. Internet 路由结构（第2版）［M］.孙剑，孙余强,译.北京：人民邮电出版社，2015.
［3］ 布莱恩特，奥哈拉伦.深入理解计算机系统（第2版）［M］.北京：机械工业出版社，2011.
［4］ 维斯.数据结构与算法分析：C语言描述［M］.冯舜玺，译.北京：机械工业出版社，2004.
［5］ 艾云霄,谭跃生,王静宇，等.MooseFS中chunkserver负载均衡算法研究［J］.微型机与应用,2013,32(5):13.
［6］ SCUDDER J， CHANDRA R.RFC 5492： capabilities advertisement with BGP4［EB/OL］.（200902xx）.http://tools.ietf.org/html/rfc5492.