基于遗传算法的域间流量控制

麦振大

【摘要】 针对域间流量特点，提出一种基于前缀的域间流量控制算法。利用遗传算法求解出传输自治系统中不同前缀的出口选择和域内各条链路的OSPF权重的优化解，再利用边界网关协议（BGP）对不同的前缀进行相应的通告来控制域间出流量，使域间流量分布更合理。

【关键词】 域间流量控制 BGP路由选择 负载平衡 AS关系 遗传算法

Internet是由超过19，000个相对独立的自治域组成的，这些自治域称为自治系统（AS）。在一个自治域内部，网络管理者可以管理域内的所有路由器，因而可以完全控制域内路由及域内的流量分布。综述了当前的域间流量工程应用现状后指出：“当前的域间流量工程是一种艺术而不是一种技术”。

一、数学模型

传输AS用图G=（V，E）表示，其中V是域内路由器集合，E是域内路由器之间的链路集合。设边e对应的链路容量为C（e），节点s到节点t之间的预期流量为d（s，t）。d（s，t）将分布到由域内路由协议求得的节点s到节点t所经过路径的各段链路上，因而，链路e上的负载为链路e的利用率为l（e）/C（e）。设函数Фe（l（e））表示链路e的费用，域内各段链路费用总和为： 当传输AS的网络性能最优时，对应F取值最小。费用函数Фe（l（e））是非线性的。链路负载在接近链路容量时网络性能会急剧下降，相应地，链路费用在l（e）接近C（e）时会急剧变大，所以Фe（l（e））为类指数函数。将费用函数Фe（l（e））近似表示成分段线性函数

其中，ai和bi随着l（e）/C（e）处于不同区间而取不同值。将取值区间分为六段：[0，1/3]， [1/3，2/3]， [2/3，9/10]，[9/10，1]， [1，11/10]， [ 11/10，+∞]，ai分别取1、3、10、70、500、5000，相应可求得bi在各区间的值。

如果节点s与节点t为边界路由器，则s与t之间传输的数据除了包括本自治系统内部从s到t的数据外，还包括其他自治系统经过s和t传输的数据。对图G扩展，向图中的边界路由器节点添加边，表示与其它自治系统之间的域间链路。则传输AS域内链路及域间链路费用总和为

式中E表示传输AS的边界路由器与其他自治系统之间的域间链路集。

二、算法设计

2.1 外层遗传算法

外层遗传算法的作用是确定每个前缀所选择的域间链路。在Internet中，大部分流量源自小部分前缀，[5]统计了AT&T中的流量分布，接近70%的数据量出自10%的前缀。实际上，由于每个传输AS可见的前缀数以万计，为每个前缀进行设置是不现实的。

（1）染色体编码：利用L=l1，l2，…ln表示前缀所选择的链路，其中li∈[1，65535]，对应一个链路号。这里的前缀指经传输AS传输IP数据包并且与传输AS之间存在多条链路的自治系统及其客户所包含的前缀。（2）交叉与变异：交叉与变异采用染色体多点交叉与单点随机变异的方式。（3）适值计算：由内层算法给出。在内层算法计算适值之前，由外层算法计算传输AS任意节点之间数据量的大小。（4）选择：采用“杰出人才模型”方式。（5）终止条件：指定终止代数或在特定代数内个体没有进化。

2.2 内层遗传算法

（1）染色体编码：利用W=w1，w2，…，wm表示各条域内链路所对应的OSPF权重值，其中，wi∈[1，65535]表示第i条链路的OSPF权重值。由于在实际网络中OSPF权重值一般不取上限65535，在计算过程中可引入一用户自定义上限MAXWEIGHT。

（2）交叉和变异：采用单点交叉以及单点随机变异的运算方式。

（3）适值计算

取链路费用与配置修改费用之和作为适值函数。在外层遗传算法中确定每个前缀所走的域间链路后，根据前缀之间的预期流量、域内各节点间的预期流量及网络拓朴，可以求出传输AS各路由器之间的预期流量。

（4）选择过程

选择过程采用“杰出人才模型”方式。

（5）终止条件

采用进化到一定的代数后终止或在特定代数内没有更优解出现则终止。

三、实例分析

Abilene网络是Internet2高性能骨干网，连接了参与Internet2的二百多所大学和研究机构，网络骨干节点拓朴如图1所示。通过这些节点Abilene与77个AS相连。Abilene Observatory提供每個骨干路由器上传输流的BGP、TCP、UDP、IP、Router等统计数据.其中，BGP类数据中的Source-Destination-prefix是以前缀-前缀形式表示的路由器的天流量，每条记录包含一天中从源网络向目的网络传输的流、字节、包以及持续时间。

四、结论

本文针对传输AS，提出一种域间流量控制方法。传输AS测量其内部的流量数据，规划域间多链路接入点，调节域内网络参数，使域内及域间流量分布更合理。Abilene网络属于中等规模网络，运算结果表明，利用遗传算法调节中等规模网络间的多链路流量是可行的、有效的。对于顶层的传输AS，由于网络路由器及前缀数量过于庞大，算法将进化缓慢，如何有效地选择前缀及简化计算过程将有待于进一步研究。