线性规划的网络流量流向控制技术

文／杨瑞

摘要：合理控制网络流量流向可更好的服务互联网发展与广大网络用户需求，可显著降低成本、降低链路负载、更好应对流量突发变化。本文结合线性规划对网络流量流向控制技术做了简要分析，在介绍网络流量流向控制与线性规划的基础上，探讨并验证了线性规划优化策略，证实了应用的可行性与优化效果，对于互联网的稳定高效运行有积极意义。

教育期刊网 http://www.jyqkw.com
关键词 ：线性规划；网络流量；流向；控制

1．网络流量流向控制

信息技术和计算机技术的快速发展带来了当前时代互联网的飞跃式发展，激增的网络用户、信息数量和网络资源刺激着网络的不断升级与开拓。呈指数级增长的广大用户、信息与资源数量要求运营服务商提供不断升级的高品质服务，网络带宽与速度升级都迫在眉睫。从整体来看，以上这些目标的实现依赖于基础设施建设的升级，从战略上来看，通过合理控制网络流量流向也可达到高效利用当前基础设施实现升级的目标，更好的保障服务的实现与品质升级[1]。

截止2013年底，我国互联网用户数量已经达到8亿多，几乎相当于美国用户数量的2-3倍，庞大的用户数量以及随之而来庞大的网络应用需求推动着互联网硬件设施和软件设备的升级，网络流量十分庞大，面对这些庞大的网络流量，做好流向控制是关键。我国网络流量流向控制主要面临三大问题的解决，分别是：现有设施的高效开发与利用以满足现阶段网络流量传输需求、通过降低网络链路负载达到节省网络资源的目的、通过平衡网络链路负载从而保障各链路有充足裕量应对网络流量的突发情况[2]。对于网络流量流向控制而言，基础设施的建设、升级与高效利用是基础，链路节余、负载平衡和裕量应对突发情况是关键，三者之间的平衡最终决定了流量流向控制[3]。通过将高负载链路的流量转移可降低局部高负载，实现整体负载水平的提升，有利于全局统筹协调链路资源，保证各链路游刃有余的运行与处理流向问题[4]。想要实现各链路负载的全局性平衡，需要科学的控制策略和定向计算方法。

线性规划作为数学运筹学的重要分支，在多个领域均有深入应用，目前无论是理论还是技术都已发展成熟，线性规划中从全局角度实现统筹最优化的思路为网络流量流向控制提供了解决思路，通过结合控制策略定量化各个要素建立线性规划模型，通过最优化求解方式实现整个网路流量资源的统筹，实现负载均衡目标。下面我们就线性规划在网络流量流向控制中的应用加以分析。

2．线性规划介绍

线性规划（LP）是目前多个已知领域应用较为广泛的优化技术，最早于1947年提出，应用于解决目标函数和约束条件等线性问题，关于线性规划的问题可用以下公式描述。

设X1，X2，X3，……，Xn为各变量，n为变量个数，m为约束条件数，aij(i=1，2……，m；j=1，2……，n)为各种系数，b1，b2，b3，……，bm为常数，C1，C2，C3，……，Cn为目标函数系数，Z为目标值，则线性规划模型如下：

线性规划的一个典型特点就是最优解min(max)通常总发生在可行域的顶点上，从而构成了求解线性规划问题的单纯形法的理论基础。单纯形法基本思路是将所有变量分为基变量和非基变量两部分，令非基变量的值为0，从而得到一组解（即基解），如果基解满足非负的条件就可称为基可行解，从而符合线性规划问题的解题定理，即线性规划问题如有最优解，一定在基可行解中[5]。正是基于这个理论，线性规划最优解的获取需从基可行解中得到，单纯形法也是基于这一原理而呈的有效搜索方法，通过搜索排除直到获得最优解，目前线性规划问题最优解的获得多数都是使用这个方法。不过由于此法较慢，目前多使用阻挡层法，此法的原理为产生一系列可行点，在该法收敛时这些点可满足所有约束条件并且不一定是顶点，这些点可穿过可行域，适用于大型问题的求解，相对单纯形法较快。本次研究中网络流量流向线性规划问题的解决使用单纯形法[6]。

线性规划问题的解决要建立线性规划模型，模型建立步骤为：抽象现实问题－建立模型－求解模型－分析结果与结论，前两个步骤依托线性规划软件IKOG或LINGO可实现，结果的分析与结论必须由专业人士进行，其余可以依托计算机完成。抽象现实问题是，模型建立关键，将具象问题转化为线性函数与方程，为问题解决提供量化计算手段[7]。

3．基于线性规划的网络流量流向控制策略

3.1 控制策略

我们假设有port1，port2，……，portn共n个网络节点，每个节点对应相应网络服务器Sevi，及对应网络节点portj的服务需求Rqtij，其中Sevj的存在是为了满足Rqtij，这个目标的实现需要借助不同网络链路流量Flowij来实现，Sevj满足Rqtij既可通过Flowij实现，也可通过Flowjk借助portk的转发通过Flowki实现。因此，控制策略第一条为Flowij要确保Rqtij和Sevj的实现。Flowki要确保portj与porti之间的信息传递及其他节点之间的信息传递，不过由于Flowki加Flowji不能超过链路的双向带宽，所以控制策略第二条为流向的控制要限制在带宽之内。Flowki越大，意味着控制成本越高，所以，控制策略第三条是要尽可能降低ΣCost（Flowji），Flowji越接近满负荷，意味着链路裕量应对突发流量情况的能力越差，所以在接近满负荷时，要考虑将部分流量转向富余链路，所以控制策略第四条是要尽量避免链路满载或者超负荷。

3.2 控制策略实现

线性规划模型的建立关键在于现实要素向抽象变量的转变，要素之间关系抽象为方程必须满足要求也要抽象为方程，从而完成目标函数的构建，根据这一要求，网络流量流向控制的线性规划问题中Sevi、Rqtij、Flowij都是变量，策略一所描述的三者之间的关系可抽象为现象方程，策略二规定了其必须满足的条件，策略三规定了成本控制条件，策略四规定了综合目标，其都应被抽象为线性函数，从而构成多目标线性规划问题。因为线性规划问题目标函数只能有一个，所以必须由策略三与四系统构成。基于以上分析，线性方程的条件描述情况如下：Sevi、Rqtij、Flowij为基本变量，Sevi、Rqtij值固定可视为常量，说明二者之间的需求关系必须得到满足，Flowij值的变化会根据流量流向策略下Sevi、Rqtij的变化优化调整，PunishKij确定为惩罚变量，Flowij增加会影响PunishKij随之增大，成本则提升；网络中每条链路都对应一个相应的惩罚变量，port1，port2，?，portn则对应Punish1ij，Punish2ij，?Punishnij，网络带宽分段处理中Flowij越接近带宽则成本提升幅度越大，因此必须尽可能的降低ΣCost（PunishKij）才能实现最优目标。基于此设计所得到的线性规划函数最优结果一方面可显著降低成本，另一方面也会降低整体网络的链路平均负载，避免接近满载，促使多余流量被平衡到其他链路，达到最优。

Flowij被限制在带宽内，具体方程细节如下。首先是portn的m服务的流量平衡方程：

如果m ≤ n综合带宽控制方程和以Punishkij为基础的目标函数，则链路流量越大成本越高，因Costmij ≤ Costnij，所以越接近满载则成本越高，这也是寻求最优解时所必须注意的。

3.3 控制策略结果分析

通过1和2中提供的控制策略和实现手段，在网络链路结构确定的情况下可了解到网络需求变化下流量和流向的变化，并且可实现自动化寻求最优结果。假设我们有A0-A9十个关键网络节点，那么根据以上线性规划方程可得到网络关键节点之间的链路带宽矩阵，具体见表1。以上矩阵说明了链路宽带矩阵必须满足网络服务流量需求，同样，成本矩阵、优化链路负载矩阵与优化实际流量矩阵同样都是如此，在几个矩阵基础上，定义特定条件下网络情况，通过线性规划模型求得最优解，获得最优流量配置方案。

综上所述，网络流量流向控制作为当前互联网迅速发展形势下必须解决的难题，控制效果直接关系到全局性网络运行服务的质量，关系到经济发展和社会建设。线性规划的应用可很好的把握网络流量全局与局部的整体统筹和协调，实现流量流向的控制，更好的为社会服务。本文通过应用线性规划方法解决网络流量流向控制问题，取得了不错的效果，证实了应用的可行性与效果，不过在实际应用中还需进一步精细化模型中的各个参数，以获得最优流量配置方案。

教育期刊网 http://www.jyqkw.com
参考文献

[1] 李常兴,胡小飞,冼梨萍,胡月明,唐宪.基于线性规划的县级建设用地结构优化研究[J].广东农业科学.2010(07).

[2] 叶苗,王勇.基于支持向量回归学习机的网络流量预测[J].桂林工学院学报.2007(02).

[3] 隋允康,贾志超.0-1线性规划的连续化及其遗传算法解法[J].数学的实践与认识.2010(06).

[4] 张端,高岩,章苗根,何熊熊,邹涛.线性规划实现动态优化的模型预测控制策略[J].化工学报.2010(08).

[5] 任勇,李一鹏.互联网信息共享的复杂性研究[J].复杂系统与复杂性科学.2010(Z1).

[6] 林荣.网络流量控制相关关键技术研究[J].科技资讯.2010(12).[7] 袁华,常欣,逄焕利,李文辉,胡亮.基于Petri的分布式网络流量优化[J].吉林大学学报(理学版).2010(06).

作者简介：杨瑞，内蒙古集宁师范学院计算机系讲师，硕士，研究方向为计算机软件理论、操作系统。