徐明伟 , 高冰洁
清华大学 计算机科学与技术系, 北京 100084

收稿日期：2017-03-19
作者简介：徐明伟(1971-), 男, 教授。E-mail:xmw@cernet.edu.cn


摘要：流量工程是网络资源优化配置的重要手段，域间流量工程是针对自治系统（autonomous system，AS）间链路的负载均衡及利用率优化。目前，互联网的路由都是按照报文目的地址进行的，这使得基于边界网关协议（border gateway protocol，BGP）的域间流量工程在网络拥塞时的调整能力有限。该文在分析了域间流量工程典型场景和需求的基础上，提出了基于二维路由的域间流量工程模型，并提出了域间二维路由流量工程场景下流量放置问题和源地址块切分问题的启发式算法来求解。仿真结果表明：基于域间二维路由的流量工程能够成功解决流量细分问题，并在吞吐量、路径稳定性等指标上均优于基于BGP的流量工程方案。
关键词：二维路由流量工程域间路由
Two-dimensional routing based inter-domain traffic engineering model
XU Mingwei, GAO Bingjie
Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China


Abstract: Traffic engineering (TE) optimizes the allocation of resources. Inter-domain TE aims to balance the load of inter-autonomous system links and to optimize the utilization of every link. Internet routing is based on the packet destination address which limits BGP-based inter-domain TE when the network is congested. Typical inter-domain TE environments and requirements were analyzed to develop a TE model based on two-dimensional routing, a traffic placement algorithm and a source addresses splitting algorithm. Simulation show that the 2D-based inter-domain TE can successfully solve the fine-grained traffic split problem with better throughput and path stability than the traditional BGP TE.
Key words: two-dimensional routingtraffic engineeringinter-domain routing
互联网流量规模的急剧增长，给互联网体系结构的各个方面都带来了巨大的挑战，其中由于流量分布不均衡导致的网络链路利用率不均衡是一个影响网络服务质量的重要问题^[1]。为了优化互联网的流量配置，研究者们提出了一系列方法来控制特定流量的路由，这些方法统称为流量工程。流量工程按照作用范围分为域内流量工程和域间流量工程。由于目前域间的路由协议是边界网关协议(border gateway protocol，BGP)，研究者们围绕BGP展开了大量的域间流量工程研究。然而由于路由体系结构的固有缺陷，基于BGP的流量工程能够优化和解决的问题都十分有限。除了基于BGP的流量工程外，也出现了基于多协议标签交换(multi-protocol label switching，MPLS)^[2]和软件定义网络(software defined network，SDN)^[3]的域间流量工程方案，然而这些方案在部署、隐私保护、安全等方面还存在较大漏洞。
传统的互联网是根据目的地址与路由表中的目的网络前缀匹配结果来寻路的，因此传统的流量工程中对流量划分都是依赖于其目的地址。在基于BGP的流量工程方案中，为了实现对流量更细粒度的划分，则需要在路由表中添加更精准的目的地址前缀。具体而言，通过BGP公告携带的属性，将进入或离开自治系统(AS)的流量以地址前缀进行区分，根据优化目标分配到不同链路上，从而优化域间链路的利用率和性能^[4]。然而基于BGP的流量工程方案的效果并不理想，一方面，更精准的目的地址前缀会导致路由表膨胀^[5]；另一方面，由于现行路由体系的路由过程仅依赖报文的目的IP地址，因此BGP只能实现较粗粒度的流量工程，无法对流量进行更细粒度的划分^[4]。在一些特殊的域间路由场景下，配置更细粒度的路由也无法解决网络中的部分链路拥塞问题^[6]，例如当目的地址为互联网上的内容服务商、云存储服务商时，这些内容服务商向外提供服务的IPv4地址数量很少，导致通往同一个目的地址的巨大流量只能通过一个AS到达目的AS，无法通过通告更精细的路由来完成流量划分。
本文提出一种域间二维路由体系结构，将报文源地址纳入路由决策。通过扩展BGP选项，在网络信息传递报文中增加源地址信息，使得流量的分割更加的精细化。本文提出了基于域间二维路由的域间流量工程模型，并进一步提出了基于域间二维路由的流量放置和切割算法。在NS-3上的仿真实验表明：本文提出的流量工程方法在吞吐率、路径稳定性等多个性能指标上都优于BGP方案。
1 基于二维路由的流量工程基于目的地址的BGP协议无法通过配置解决流量细分问题，而在互联网上大规模的部署MPLS和SDN又存在安全和可扩展性的问题^[7]，因此需要一种能够在BGP基础上实施细粒度流量工程的方案。在以IP协议为基础的互联网路由中，报文源地址和报文目的地址起到的作用并不对等，许多新型的互联网路由方案都增强了目的地址外的因素对路由的影响，例如SDN能够匹配报文中的多个字段来决定转发策略^[8]。综合考虑可部署性和转发效率等因素，报文源地址是一个理想的转发决策维度。
二维路由^[9]是一种由数据包的源地址和目的地址共同决定路径的互联网路由体系结构。二维路由根据作用范围可以分为域内和域间二维路由。基于域间二维路由的流量工程可以根据报文源地址将流量均摊到各个出口上，实现多路径的域间路由。这种方案无需在边界路由器上配置复杂的MPLS/IP-in-IP隧道，通过引入源地址信息降低了实现细粒度流量工程的配置代价。当上游的AS发生拥塞时，边界路由器向其他宿主通告新的二维路由即可实现多宿主下的流量路径切换，当链路恢复正常负载之后再撤回通告即可恢复。
假设一个AS间的拓扑如图 1所示，网络中存在4个AS，共有50台主机与AS A相连，以50 Mb/s的速率向目的AS发送流量。在仅使用目的地址路由的情况下，所有流量经过AS B流向目的，造成域间链路的利用率不均，如果使用二维路由，AS A可以使用源地址分割流量，此时最优的方案是让来自30个主机的流量经AS B传递，剩余20个主机的流量经AS C传递，最终A、B、C、D四个AS间链路的利用率都是50.0%。

图 1 二维路由解决流量细分问题

图选项

2 基于二维路由的域间流量工程模型基于二维路由的域间流量工程不仅需要二维路由体系结构的设计与实现，也需要在利用二维路由能够细分流量的特点的基础上，通过细粒度的流量调度，实现优化链路利用率，提升整体吞吐量的目的。
2.1 问题抽象首先描述流量工程的需求模型。根据调研，网络中的流量源目的地址分布呈现出少数AS汇集了多数流量的现象，通过优化这些AS出口处的域间流量，可以起到优化整个网络流量的目的。图 2中，目的地址块D有m个，源地址块S有n个，末端网络连接到K个上游ISP。末端网络通往每个上游ISP的链路容量均相同。在二维路由中，数据包的路径由源地址和目的地址共同决定，因此定义一条从第i个源地址块到达第j个目的地址块的路由r_{i, j}：

图 2 域间流量工程模型示意图

图选项

${r_{i,j}} = {S_i} \to {D_j}.$

其中箭头表示从源前缀S_i到目的前缀D_j的映射。
路由r_{i, j}是否经过上游的ISP_k，需要考虑2部分因素：费用和吞吐率。ISP根据经过的流量收费，每个ISP拥有自己的费用方程^[10]，各个ISP的费用方程都不一定相同，所有方程f_k的集合为F，设路由r_{i, j}经过ISP_k的流量为T_{i, j}，则ISP_k能够收取的总流量费用为

${\rm{Cost}}\left( k \right) = \sum\limits_{i,j \in {G_k}} {{f_k}\left( {{T_{i,j}}} \right)} .$

其中G_k, 经过ISP_k的所有流量的源目的对构成的集合。设w_k为末端网络对ISP_k的偏好因子，I为ISP的集合，T为末端网络各出口链路上的流量分布，则在流量分布为T的情况下末端AS订阅上游ISP所产生的费用总和为

${\rm{Cost}}\left( T \right) = \sum\limits_{k \in I} {{w_k}{\rm{Cost}}\left( k \right)} .$

流量工程中比费用更重要的是流量的吞吐率，一条链路的吞吐率决定于经该链路传输的所有流的吞吐率之和，一个末端AS的吞吐率等于其所有出口链路的吞吐率之和。因此，末端AS经过ISP_k传输的流量的吞吐率为

${\rm{throughput}}\left( k \right) = \sum\limits_{i,j \in {G_k}} {{\rm{throughput}}\left( {{T_{i,j}}} \right)} .$

因此一个末端网络流量工程的优化目标为

${\rm{throughput}}\left( T \right) = \sum\limits_{k \in I} {{\rm{throughput}}\left( k \right)} ,$

约束条件为

${\rm{Cost}}\left( T \right) = \sum\limits_{k \in I} {{w_k}{\rm{Cost}}\left( k \right)} \le W.$

其中W为费用上限，如果W不能满足则方程无解，即考虑在一定的费用限制下有些自治域可能会选择忍受拥塞。如需要找到一组解来避免拥塞，则需要调高W的数值。在一般的网络流和最优化路由的问题求解过程中，需要知道网络拓扑和拓扑中每条链路的带宽容量，而对于末端网络，只知道其直连的每条上游链路的容量，因此末端网络需要通过探测的方式来得到上游路径的状况，采用启发式的方式得到最优解。
2.2 流量放置算法流量放置算法的目的在于将出入末端网络的流量按照当前各出口链路的性能状况进行分配，每个＜源地址块，目的地址块＞为此算法中放置的基本单元，如有进一步划分的需求可以在此二元组的基础上增加维度，如＜源地址块，目的地址块，端口号＞等。算法主要分为初始放置和动态调整2个阶段。
初始放置问题可以抽象为一个背包问题，目标是将多条流量需求放置到末端AS的多个出口链路上，这个算法是根据测量数据离线执行的。本文采用首次适应降序(first fit decreasing，FFD)^[11]算法来解决初始放置的问题。首先将各条流的带宽请求按降序排序，随后将排好序的请求从小到大依次尝试放置在各条出口链路上，若当前链路能够容纳该请求，则放置，否则继续尝试下一条链路。设Requests={R₁, R₂, …, R_n}为初始时刻末端网络中各条流的带宽请求，Bandwidths={B₁, B₂, …, B_m}为末端网络各出口的带宽容量，T为流量放置的结果，算法如图 3所示。

图 3 流量初始放置算法伪代码

图选项

算法1是一个典型的贪心算法，当流的数目为N_F，出口链路数为N_L时，其时间复杂度为O(N_FN_L)。从上述算法中可以看到，初始放置只是找到了一种流量的静态情况下的放置方案，而当网络情况发生变化或者出现拥塞时，就需要调整流量分布。
在动态调整时，首先对末端AS中正在传输的所有流进行排序，找出正在拥塞的所有流。随后，将所有吞吐率低于门限Throughput_th的流按照已知的上游ISP带宽、流量费用和移动次数等约束条件分配到有空余带宽的链路上去。流量移动目标链路的选择顺序是以当前各条链路富余带宽为依据的，性能最差的流量优先选择富余带宽最大的链路。设Flow={flow₁，flow₂，…, flow_m}为当前网络中所有流序号的集合，Link={link₁，link₂，…，link_n}为网络所有出口链路的标号，当前各条链路剩余带宽RemainBW={RB₁, RB₂, …, RB_n}，各条流当前的吞吐率Throughput={T₁, T₂, …, T_m}，每个上游ISP处的流量费用Cost={C₁, C₂, …, C_k}，每条流切换链路的次数Move={Move₁, Move₂, …, Move_m}，T′为调整后的分布，LowPerf为性能低于门限值的流的序号集合，流量放置的动态调整算法如图 4所示。

图 4 流量动态调整算法伪代码

图选项

在动态调整的过程中，复杂度为O(N_CN_L)，其中N_C是发生拥塞的流的数目。对于以上算法有以下几点说明：1)每次试图迁移流之前需要实时地检测当前流的吞吐率是否依然低于门限值，这是由于前面属于LowPerf流的迁移可能会导致当前流的性能上升，不再处于拥塞状态，从而无需迁移；2)由于在移动前即可根据待迁移流量的带宽计算得到迁移后的整体费用值Cost′，因此是否迁移也受到费用的约束；3)为了防止流的频繁迁移导致的重路由从而造成性能下降，需要为每条流设置一个移动迁移次数的计数器，当某条流的迁移次数Move_i超过上限Move_th时不再迁移该条流。
2.3 流量细分算法根据算法2可以得到一个以源、目的地址前缀为唯一标识的流量放置方案，该方案已经在一定程度上缓解了仅根据目的地址进行流量分配所造成的链路利用率不均的状况，但在某些较小的地址块通信流量很大的情况下，无论如何按照源地址块分配流量，网络中还是会产生拥塞，此时就需要更细粒度地对源地址块进行切分。
图 5中，末端网络中有大小为150 Mb/s、源地址前缀为101.5.208.024、目的地址为220.181.111.188(百度)的流量，而此时连接到的上游ISP1、ISP2和ISP3的接入链路带宽已经分别被占用了30、70和20 Mb/s，如果按照BGP选路的原则(假设此处选择ISP2为流量的下一跳AS)，则通往ISP2的链路需要承载220 Mb/s的流量，如图 5中粗链路所示。而由于通往ISP1和ISP3的链路也没有充足的带宽能够单独容纳150 Mb/s的流量，因此需要对流量按照源地址分割为3部分，3个宿主AS分别承担60、20和70 Mb/s的流量，避免了链路利用率不均的情况(图 5中20/100表示链路容量为100 Mb/s，当前占用20 Mb/s；箭头表示了链路利用率的变化前后的情况)。

图 5 源地址切分算法效果示意图

图选项

根据源地址切分流量在AS的入站流量工程中也同样适用。例如图 5中，当流量经过多跳到达目的AS时，由于网络中AS复杂的选路方法可能使得流量在接收端汇聚而产生拥塞，如果流量都汇集到ISP6而递交给目的端时，ISP6到目的AS的链路就会产生拥塞，而其他接入链路还有空余带宽。当目的AS检测到这一情况时，可以主动按照源地址切分入境流量。目的AS首先将入境流量的按源地址分为3块，分别向3个ISP发送具有3个源地址块的BGP Update通告，ISP收到通告后会级联地向前传播，最终使得流量经过的整条路径全部分开。
源地址划分算法是依托于算法2的一个补充方案，可用来解决网络中存在大流且通过切分源地址空间就可以缓解这条流造成的拥塞的问题，也可以解决初始放置时可用带宽不足的问题。设网络中的源地址块的集合为S，划分源地址之后的集合为S′，则优化目标为

$\begin{array}{l}\Delta T = \sum\limits_{k \in S'} {{w_k}{\rm{thoughput}}\left( k \right)} - \\\quad \quad \sum\limits_{k \in S} {{w_k}{\rm{thoughput}}\left( k \right).} \end{array}$

作为流动态放置的补充，基于源地址的流量切分能够有效地将大流分割，从而将更多链路上碎片化的带宽资源利用起来。首先，寻找到当前拥塞的流量中占用带宽最大的流量，尝试将其源地址前缀等分。然后采用算法2寻找无拥塞的解决方案。如果依旧找不到解则继续寻找最大流量并拆分。为了保证路由表能够承受前缀划分带来的膨胀，需要设定一个容量上限，如果当前流量属于的源前缀长度超过了门限长度(即掩码的位数)，则停止划分。设当前网络中流的源地址块及对其应流量为D={＜S₁, BW₁＞, ＜S₂, BW₂＞, …, ＜S_n, BW_n＞}，当前各出口链路可用带宽为RemainBW={RB₁, RB₂, …, RB_m}，具体算法按以下步骤如图 6所示。

图 6 源地址分割算法伪代码

图选项

上述算法中排序和建堆部分的复杂度均为O(N_F lb N_F)，随后的堆调整和分配过程的复杂度为O(N_F)。
3 性能评价采用NS-3对算法进行仿真，来比较基于域间二维路由和传统BGP路由的流量工程在各种性能上的差异。在仿真中，所有的链路容量都设为1 Gb/s，每个路由节点都实现了基于BGP扩展的二维路由转发引擎及流量工程算法，仿真的拓扑是一个实际的AS级别的域间拓扑^[12]。该拓扑有43 340个节点，每个节点的平均度数为3.5，其中末端网络的平均度数为2.1。为了防止路由环路，实验中假设所有的边界路由器(iBGP节点)是连接在一个全连接(full-mesh)的拓扑之上的^[13]。实验首先针对优化目标吞吐率，验证了基于二维路由的域间流量工程在提升流量吞吐率方面有良好的表现，同时验证了AS间流量路径的多样性和这些路径的稳定性。流量的分布采用平均分布和幂律分布2种方式产生。流的开始时间构成一个Poisson过程，在1 s内启动的流的平均数目设置为100，流量的大小为1 GB，包的大小是1 kB。本文在每个节点上实现了二维路由协议，在末端的AS节点上实现了算法2和3，分别记为2DTE-w/o-split和2DTE-w/-split。
3.1 吞吐率当给定一个域间网络的流量矩阵时，吞吐率是反映流量工程效果的直观指标，也是算法2和3的优化目标。首先，使用均匀分布产生一个含有一百万条流的流量矩阵，每条流量的源和目的是随机选择的。图 7为网络中各条流吞吐量的累积分布(CDF)。与本文的预期一致，带有源地址分割和不带源地址分割的流量工程在网络容量一定的情况下流量的总吞吐率都高于传统的BGP方案，这是因为当网络中的总带宽容量能够容纳所有流时，基于源目的地址对的放置算法能够使流量被均衡到不同的链路上。在源地址分割方案和不带源地址分割方案的比较中，源地址分割方案明显优于不带源地址分割方案，不带源地址分割的方案只有一半的流超过3 Gb/s的吞吐率，而实现了源地址分割后有60%以上的流的吞吐率能达到3 Gb/s。

图 7 均匀分布下流量吞吐率的CDF

图选项

接下来，使用幂律分布模拟一个AS级别的流量矩阵，因为这样更接近真实互联网的流量分布^[14]。图 8中，基于传统BGP的流量工程中有50%的流量吞吐率不足1 Gb/s，这是因为大量的流量通过有限的路径而造成了拥塞。与此相对应的是，由于可以通过多路径转发，基于源地址分割的方案比基于传统BGP的流量工程在吞吐量上的表现要更好一些，同时也优于不带源地址分割的方案。如果使用带源地址分割的方案，70%的流的吞吐率可以达到5 Gb/s，而其他2种方案中只有50%和17%的流可以达到这一吞吐率。

图 8 幂律分布下流量吞吐率的CDF

图选项

3.2 路径稳定性由于二维路由的流量工程涉及流量的路径切换，而频繁地切换路径不仅会导致路由震荡，也会降低流量的传输效率，因此需要考评路径的稳定性。本文设置的流量迁移和切分的门限次数都是3次，如图 9所示，不到50%的流量只切换过2次，而95%以上的流量切换路径都不超过3次。这说明多数流量的路径切换是处于可控范围内的。

图 9 流量路径切换次数分布

图选项

4 结论域间二维路由是一种新型的域间路由体系结构，它充分利用了报文中的源地址信息划分流量，在实施域间流量工程方面有较好的优势。本文通过实例说明了现有的域间流量工程存在的不足，提出了基于域间二维路由实现细粒度流量工程的方法，进而提出了末端网络利用二维路由的域间流量工程进行流量放置和在线调整的算法。仿真结果表明：本文提出的基于域间二维路由的流量工程及流量放置和调整算法在时延、吞吐量、路径多样性等方面比传统BGP的流量工程都有较大的提升。

参考文献

[1]	Hassidim A, Raz D, Segalov M, et al. Network utilization:The flow view[C]//IEEE International Conference on Computer Communications, INFOCOM 2013 Proceedings IEEE. Atlanta, GA, USA:IEEE, 2013:1429-1437.
[2]	Rosen E, Viswanathan A, Callon R. Multiprotocol Label Switching Architecture[R]. Fremont, CA, USA:Internet Engineering Task Force, 2000.
[3]	Kreutz D, Ramos F M V, Verissimo P E, et al. Software-defined networking:A comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14–76. DOI:10.1109/JPROC.2014.2371999
[4]	Wang N, Ho K, Pavlou G, et al. An overview of routing optimization for internet traffic engineering[J]. IEEE Communications Surveys & Tutorials, 2008, 10(1): 36–56.
[5]	Tangmunarunkit H, Govindan R, Shenker S. Internet path inflation due to policy routing[C]//ITCom 2001:International Symposium on the Convergence of IT and Communications. Denver, CO, USA:International Society for Optics and Photonics, 2001:188-195.
[6]	Nagami K, Uda S, Ogashiwa N, et al. Multi-homing for Small Scale Fixed Network Using Mobile IP and NEMO[R]. Fremont, CA, USA:Internet Engineering Task Force, 2007.
[7]	Zhang R, Vasseur J P. RFC 4216:MPLS Inter-Autonomous System (AS) Traffic Engineering (TE) Requirements[R]. Fremont, CA, USA:Internet Engineering Task Force, 2005.
[8]	McKeown N, Anderson T, Balakrishnan H, et al. OpenFlow:Enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69–74. DOI:10.1145/1355734
[9]	Yang S, Xu M, Wang D, et al. Scalable forwarding tables for supporting flexible policies in enterprise networks[C]//IEEE International Conference on Computer Communications, INFOCOM 2014 Proceedings IEEE. Toronto, Canada:IEEE, 2014:208-216.
[10]	Kist A A, Harris R J. Cost efficient overflow routing for outbound ISP traffic[C]//ISCC 2004. Alexandria, Egypt:IEEE, 2004:876-882.
[11]	Baker B S. A new proof for the first-fit decreasing bin-packing algorithm[J]. Journal of Algorithms, 1985, 6(1): 49–70. DOI:10.1016/0196-6774(85)90018-5
[12]	UCLA IRL. Internet topology collection[Z/OL].[2017-02-21]. http://irl.cs.ucla.edu/topology.
[13]	Bates T, Chandra R, Chen E. BGP Route Reflection-An Alternative to Full Mesh IBGP[R]. Pittsburgh, PA, USA:Internet Engineering Task Force, 2000.
[14]	Adamic L A, Huberman B A. Zipf's law and the Internet[J]. Glottometrics, 2002, 3(1): 143–150.