智慧协同网络负载均衡流量适配方法研究及测试

潘沭铭,贾 濡,石 秀,赵兴利

(1.中国人民解放军66736部队，北京 100144;2.中国电子科学研究院，北京 100041)

0 引 言

现有的互联网是基于TCP/IP的传统网络架构，为了换取灵活高效的分组转发能力，以IP协议为核心的转发牺牲了包括感知与适配在内的自适应型功能。传统路由器通过查找IP地址单一属性，根据自身转发表做出转发出口的单一适配决策，这使得同一服务数据流的不同分组转发路径存在不确定性，无法进行基于实时网络状态的流量调度及资源适配。随着云计算、移动互联网、数据中心网络等多种应对新兴服务需求的技术与应用发展迅速，流媒体等不对称通信业务量激增，互联网流量在近几年里急剧增长。据Cisco VNI(Visual Networking Index)调查预测，2021年全球IP流量将达到每年3.3 ZB，每月278 EB[1]。互联网流量类型也由P2P逐渐转变为IP视频流量。随着智能终端的发展，互联网的内容发布已经不再单纯由新浪、搜狐等大公司进行，取而代之的是以传感器、手机、监控设备等等多种终端混合产生。多种内容源也使得互联网数据量进一步扩大。

各类通信业务需求不断膨胀，网络的发展从以IP地址为中心向以信息为中心的趋势发展，针对日渐增长的新型业务流量，可以说原始架构设计缺陷已经成为了互联网发展的瓶颈。因此，摒弃“补丁”式的改进，设计面向未来需求的新型网络架构已经成为重要研究方向。未来网络架构的承载网络需要支持对网络状态的实时感知并智慧地进行资源的优化适配，随着网络流量的变化自主地从全局角度规划网络资源，动态提高网络资源利用率。

智慧协同网络(Smart Identifier NETwork / SINET)[2][3]作为一种面向未来需求的全新型网络架构，采用了“控制与数据分离”、“以信息内容为中心”的思想，采用基于标识的路由机制，并引入行为描述信息来实现内嵌于网络架构中的智慧性，使网络能够从根本上支持资源动态适配，实现网络资源优化利用。智慧协同网络核心思想是实现网络资源的优化适配，本论文针对“如何实现负载均衡流量适配”这一问题，展开研究。

本论文在前期智慧协同网络流量预测机制的基础上，根据预测结果实现负载均衡调度。主要内容如下：第二章介绍了传统网络中域间流量适配机制方法以及智慧协同网络当前研究进展；第三章介绍了服务获取过程的流量传输情况，并详细阐述了流量规划数学建模方法，即介绍了负载均衡流量适配实现方法；第四章开展原型系统真实流量模拟；第五章在SINET原型系统中实现并验证了域间流量优化调度的可行性；第六章对本文进行了总结。

1 研究背景

1.1 传统网络中域间流量适配机制方法

众所周知，自治系统之间实际上存在着冗余的连接[4-5]，多连接性问题的研究，不同自治域之间的相互联系经常是冗余的，超过一半的自治域是通过多个物理链路连接的，且相邻的一级自治域之间至少有75%的点对点关系是冗余的[6]。域间流量调度规划逐渐成为网络技术的重要组成部分。过去阶段，大量的研究集中在路由协议方面上[7]。这种现象的主要原因是传统网络中的流量工程通常是基于BGP(边界网关协议)，标准的BGP不支持灵活的路由策略。在过去的几十年里，自治域的数量和自治域中节点数量都迅速增长，BGP路由表急速膨胀[8]，BGP面临着可伸缩性不足的挑战，网络产生难以扩展的问题。超过一半的自治域对是通过多个物理链路连接的，邻域间超过四分之三的点对点关系是冗余的，这种现象更是给网络流量资源适配增加了更多的压力，也导致路由的规模越来越大。传统网络中只有少数中间路由器具有流量工程功能，而未来网络参与网络管理的中间节点可达百万数量级，网络规模的发展也势必会带来路由表条目的增长，产生严重的路由可扩展性问题。

1.2 智慧协同网络当前研究进展

智慧协同网络当前主要研究成果及进展如下:

文献[2][3]详细阐述了为彻底解决TCP/IP传统互联网体系架构资源与位置紧耦合、控制与数据紧耦合、身份与位置紧耦合问题而设计的智慧协同网络“三层两域”体系架构。文献[9] [10]分别针对智慧服务层、网络组件层做进一步详细阐述。文献[11]-[13]提出了智慧协同网络路由机制。[14]则是将研究重点放在网络的“原生智慧性”上，设计了基于状态感知的域内资源适配机制，基于流量感知的域内智慧路径分配方法，以及网络能耗和协作缓存优化方法。

2 负载均衡流量适配方法

2.1 服务获取过程流量传输情况

智慧协同网络具有“智慧性”，能够将原生地支持网络资源的优化适配。如图1所示为跨域的服务获取过程中流量的传输情况。服务请求GET包传递至本域资源管理器(RM/Resource Manager)，RM计算流表并下发至边界转发组件(FN/Forwarding Node)，RM将路径标识PID附在GET包并转发至下一域RM。之后被请求服务DATA包附来时路径返回。为实现域间流量智慧适配，RM及边界FN应协同实现网络流量感知及预测，在服务资源流量返回之前，根据策略(详见3.2)进行优化规划计算，为待返回DATA流量选择路径。

图1 服务获取过程中流量传输情况

为实现域间负载均衡应实时感知链路的负载状况，动态改流量规划策略，这一点在传统的域间负载均衡架构中实行起来十分困难。而智慧协同网络无需额外机制、中间件，能够原生性地支持网络状态感知及路径规划，进而实现智慧性资源适配。

2.2 流量规划数学建模

流量规划算法的设计基于动态规划的思想，负载均衡问题本质上是一种离散规划问题，均衡水平的定义分为松弛均衡、严格均衡两种。松弛均衡是指各链路的利用率处于一个稳定的区间内，这个区间我们成为均衡区间。严格均衡是指所有处于特定域之间的链路，其链路利用率均相等。由于在智慧协同网络架构中，以Get包和Data包为基础进行通信，从调控粒度上难以做到严格均衡，所以调控目标以松弛均衡为准。但是严格均衡在理论层面具有重要意义。所以，本论文将实现松弛均衡的行动组合视为负载均衡问题的可行解，把实现严格均衡的行动组合视为负载均衡问题的最优解。

流量规划算法主要有启动策略、转移策略、选择策略、收益性策略四部分策略(准则)[15]：

(1)启动策略

指负载均衡策略启动条件，包括负载转移的发起者，接收者，触发条件三个方面。常见的分布式启动策略有：发送者启动，即重载节点满足触发条件后，发起负载转移过程；接收者启动，即轻载节点满足触发条件后，发起负载转移过程。混合策略，重负载时，轻载节点发起负载转移。轻负载时，重载节点发起负载转移。当链路总负载过高时，采用接收者启动；当网络负载低的时候，采用发送者启动。该设计原因是：当网络负载高的时候，负载低的链路占少数，网络负载低的时候，负载高的链路为少数，当网络负载低的时候，我们只需保证一些高负载链路的流量不要超过链路容量；最大程度降低负载均衡的请求信息。本论文研究范围中启动策略设置为当网络负载高的时候，采用接受者驱动；当网络负载低的时候，由发送者驱动。RM收到Get包，如果各链路负载处于合适区间内，则不做负载均衡，直接查询SID按照结果转发。

(2) 转移策略

解决如何设置阀值，高于某特定值时为高负载链路，需向其他链路转移流量负载；静态阀值很难满足链路流量变化的动态需求,因此在智慧协同网络负载均衡机制中，阀值可以依据网络整体流量的不同实时改变。定义域间链路流量矩阵TM为Tij，其中第i行j列(i∈[1,+∞]，j∈[1,+∞])的值，代表以i为源点、j为目的点的OD(Origin-Destination / 源和目的节点对)对之间的流量：

(1)

定义域间链路容量矩阵为:

(2)

将矩阵Cij的每一行相加，可得本域其他相邻域之间以域为单位的链路容量：

Ci=[c1，c2，…，ci],i∈[1,+∞]

(3)

定义以域为单位的逻辑链路利用率为：

(4)

定义实际链路利用率为：

(5)

设置最大阀值矩阵：

1≤i≤+∞, 1≤j≤+∞,i∈Z,j∈Z

(6)

其中i为自治域AS号，j为链路号，矩阵中元素表示某一AS所有相邻域间链路的最高阀值。矩阵中的元素例如：max11max11表示本域与编号为1的域之间，编号为1的链路的最大阀值。并规定计算公式为：

1≤i≤+∞, 1≤j≤+∞

(7)

其中，α为最大阀值系数。同理，我们设置最小阀值矩阵：

1≤i≤+∞; 1≤j≤+∞

(8)

其中，i为AS号，j为链路号，表示某一AS所有相邻域间链路的最小阀值。并规定计算公式为：

1≤i≤+∞, 1≤j≤+∞

(9)

β为最小阀值系数。定义负载均衡力度为：

1≤i≤+∞, 1≤j≤+∞,

(10)

α-β越大，则负载均衡力度越小，越不灵敏；α-β越小，则负载均衡力度越大，越灵敏。

(3) 选择策略

选择策略用来选择负载转移的目标。在智慧协同网络多源路由的特性，选择策略分为两个层次。第一层次为选域，第二层次为选路。具体情况为当某Get消息到达本域RM后，首先查找所请求的SID是否具有多个注册内容源，如果是，则依据以域为单位的逻辑链路利用率Hi，选出域间链路总利用率最低的域，作为服务内容源提供者。

将所选链路利用率记为Hk：

Ηk=min{Η1,Η2,Η3,…,Ηi}， 1≤i≤+∞

(11)

如果没有多个注册内容源，则按照唯一匹配流表转发。够借助网络缓存和智慧协同网络中多源路由的特性，合理的实现域间流量的全局均衡。

接着依据域间实际链路负载大小进行选路操作，优先选择链路负载低于最小负载阀值minij链路；在选择需要转移负载的链路时，优先转移负载高于最大负载阀值maxij的链路。最理想的负载均衡状态，应当是域间实际链路的利用率趋于1且各链路利用率应当相等。我们希望在负载均衡的同时，最大化利用网络的传输资源。首先，我们来证明一个结论。既当网络一逻辑链路趋于负载均衡时，域间的实际链路也是处于均衡状态的。如果我们要实现严格负载均衡，只需要按照链路的传输能力进行流量分配即可。也就是说，我们可以按照链路带宽占总链路带宽的百分比来进行流量的分配。下面我们对以上结论进行简单证明。首先，我们证明域间逻辑链路与实际链路在均衡状态时相等。按照以上方法，在网络处于均衡状态时有：

(12)

对其进行简单变化：

(13)

等式左边表示逻辑链路的利用率，等式右边表示实际链路的利用率。 下面我们来证明各实际链路的利用率相等。

(14)

带入：

(15)

得到：

(16)

故得：

∂ij=Ηi

但是我们知道，实际情况下，很难做到每条链路的利用率都处于完全相等的状态，于是，有以下约束条件：

tij-minij≥0

(17)

maxij-tij≥0

(18)

(4) 收益性策略

收益性策略用来评价负载均衡策略是否有收益。为衡量域间链路负载的不平衡程度，我们引入不平衡因子[15]的概念。定义域间链路个数为：

Ni=[n1,n2,n3,…], 1≤i≤+∞

(19)

定义不平衡因子为：

(20)

平衡因子可由下式得出：

1≤i≤+∞, 1≤j≤+∞

(21)

我们知道，当网络具体情况确定后，其链路容量和链路个数往往是不变的。于是，求最小Uij就变成了常见的动态规划问题。有很多动态规划的算法可以用来求解此类问题，例如：维特比算法。

可以引入平衡收益函数作为负载收益性计算的衡量依据。

B(t)=Uij(ti)-Uij(ti-1)

(22)

综上所述，在智慧协同网络架构下，利用卡尔曼滤波算法得到的流量预测结果[14]可以用来进行负载均衡路由规划，而具体负载均衡过程可采用上述四种策略实现。

3 原型系统真实流量模拟

为了通过实际部署验证我们的域间负载平衡机制，我们构建了一个如图2所示的原型系统。

图2 原型系统拓扑

该原型包括两个自治域和11个功能实体节点，包括1个客户端作为服务请求方、1个文件服务器作为服务提供方、2个资源管理器RM和4个边界转发组件。这两个域由PID1和PID2识别的2条路径连接。

资源管理器与转发组件采用linux 2.6.29.5操作系统，并运行针对智慧协同网络机制改进后的OpenFlow[14]协议，服务请求方Client、服务提供方Server采用linux 2.6.29.5操作系统，基于CLICK[17]软件实现GET、DATA包的发送。

在网络初始化阶段，各自治域中服务提供方向RM完成服务内容SID的注册，边界转发组件的域间路由表与族群路由标识映(PID)射表通告完毕，自治域的所有转发组件的转发流表已由RM下发配置完毕。

客户端和客户端用于生成/处理不同类型SID的GET消息，即以SID标识不同的流。服务提供方向RM注册50,000个SID，请求消息中的SID随机从中选取，GET消息的发送间隔服从泊松分布。当服务器收到GET消息时，根据从中解析的SID返回对应服务内容数据流。为模拟实际网络环境中的流量情况，我们设置50,000个SID标识的服务内容数据流大小服从zipf(齐普夫定律)分布。根据已有研究，我们设置zipf分布中的参数α取值1.2。服务内容大小服从Zipf分布的流量生成函数如下：

//输入 参数α、 N的数值;开始:int zipf(double α,int n){ static int first = TRUE; //静态首次旗帜 static double c = 0; //归一化常数 double z,(0 < z < 1); //均匀随机数 double sum_prob; //概率的总和 double zipf_value; //返回计算出的指数值 int i; //循环计数器,首次调用时计算标准化常数 if (first == TRUE) { for (i=1; i<=n; i++) c = c + (1.0 / pow((double) i, α)); c = 1.0 / c; first=FALSE; } // 产生一均匀随机数 do{ z = rand_val(0); } while ((z == 0) || (z == 1)); //将z映射到该 sum_prob = 0; for (i=1; i<=n; i++) { sum_prob = sum_prob + c / pow((double) i, al-pha); if (sum_prob >= z) { zipf_value = i; break; } } //赋值zipf分布介于1到N之间 assert((zipf_value >=1) && (zipf_value <= n)); return(zipf_value);} END

资源管理器(RM)作为集中控制逻辑，处理GET消息中的服务请求，并根据其中SID查询服务注册信息，选定服务提供方并分配传输路径(PID)，并向数据转发层下发命令配置流表。然后，利用感知机制[14]从转发组件获取流量信息。

4 流量调度系统测试

为了测试流量调度机制的可行性，本节在图2所示SINET原型系统下进行流量调度系统测试。服务提供方向资源管理器注册100种服务资源SID 1，SID 2，… SID100，服务请求方发送GET消息随机请求SID。初始情况下，设置不同SID标识的数据流量从PID1、PID2路径随机选取，PID1标识路径带宽为130M，PID2标识路径带宽为250M，待系统运行稳定后，对PID1、PID2路径上链路的实时流量情况取样如图3所示。在测试60分钟内，PID1、PID2连路上的实时负载流量都在55M至100M变化，由于采用随机选路，流量分配呈现无规律随机性，PID1、PID2链路负载流量几乎相同。但是两条链路实际带宽分别为130M和250M，也就是说在该测试时段内，PID1链路利用率为42%至78%，而PID1链路利用率仅为22%至40%，即网络出现明显的资源利用不合理情况。

图3 PID1及PID2链路流量情况

然后，采取如图4所示机制进行网络流量优化适配。

图4 流量调度过程

转发组件实时感知网络中流量情况，并利用感知获取机制将网络状态信息传递至资源管理器RM；RM根据感知到的流量信息，利用基于卡尔曼滤波的流量预测算法计算出流量预测结果；若流量预测结果低于阈值，则RM不重新规划路径；若流量预测结果大于等于于阈值，则RM根据负载均衡策略重新为待返回的DATA数据流规划路径。本文中，我们设置低带宽链路负载超载阈值为50%，当链路利用率平均值高于50%时，RM判定网络链路处于高负载状态，并启动运行负载均衡机制。

如图5所示为流量优化调度后，对PID1、PID2路径上链路的实时流量取样情况，在该测试时段85分钟内，PID1连路上的实时负载流量在40M至70M变化，PID2连路上的实时负载流量在90M至140M变化，PID1链路负载明显低于PID2链路负载，PID1链路利用率为30%～53%，同时PID2链路利用率仅为36%～56%。

图5 PID1及PID2链路流量情况

图6 PID1及PID2链路利用率情况

图6所示的链路利用率实时变化情况可以看出，当PID1链路利用率高于阈值后，流量调度机制启动，PID1流量负载立即降低同时PID2流量负载升高，当PID2链路利用率超过阈值后，PID2流量负载立即降低而PID1流量负载升高，进而全局网络链路利用率情况达到合理状态。

5 结 语

本文在智慧协同网络架构下，对负载均衡流量适配方法开展研究，首先，通过数学建模提出了负载均衡流量规划启动、策略、选择略、收益性四种策略模型，然后在SINET原型系统中部署验证域间负载平衡机制，构建服从齐普夫分布的模拟真实流量，启动流量调度机制后全局网络链路利用率情况达到合理状态，验证了智慧协同网络架构下流量优化调度的可行性。