一种费用最优令牌缓冲流量调度负载控制方法*

郭小雪 ，梁活民 ，袁 奕

(1.茂名学院 理学院，广东 茂名 525000；2.华南理工大学 计算机科学与工程学院，广东 广州 510641)

网络各种新业务带动Internet迅速发展的同时，也产生了大量流量，给网络造成了极大的压力，这就要求网络管理者必须有效地提高网络资源的利用率以满足日益增长的业务量需求。流量工程就是在这种背景下提出的一种用来监测网络状态，控制网络资源，提高网络性能，满足各种业务需求的网络技术[1]。从定义上它涵括了对网络进行监测、分类、建模和控制的科学原理和工程应用，以及用于实现特定目标的原理和技术。流量工程的实质是对网络性能进行分析和实施优化。从网络管理者的角度，实施流量工程可以保证网络资源的合理利用和网络性能的优化；从用户的角度，实施流量工程可以更好地保证用户的服务质量。因此，实施流量工程对IP网络，尤其是公共Internet骨干网是非常必要的[2]。

流量控制和资源分配技术是互联网QoS保证的重要基础[3]，不同网络环境下的流量控制和资源分配技术有不同的特点。当前互联网采用的很多流量控制方法在效率、系统优化以及公平性保障等方面存在着较大的缺点和不足。而优化流量控制则基于拥塞计费技术，借鉴微观经济学原理，利用价格杆杠的调节作用使系统达到优化状态，并可实现用户之间资源共享的比例公平性，是一种较好的流量控制和资源分配方法[4]。

1相关研究

最近很多研究提出的优化流量控制机制借鉴了微观经济学原理，通过效用函数的形式来表示用户的带宽需求，网络以用户效用函数的总和作为优化的目标函数[5]。网络根据当前的拥塞状况不断向用户反馈拥塞费用，用户在利益的驱动下，根据反馈的费用不断调整用户速率，最后达到系统优化的均衡状态[6]。

[7]把微观经济学方法引入网络资源分配领域，分析了基于微观经济学方法的网络资源分配研究最新进展，介绍了网络资源分配的典型经济模型，研究了各种定价策略，并分析与网络资费相关的若干问题，最后研究基于价格的通信协议实现，为这一领域的研究提出了新思路。参考文献[8]通过改变无向网络流最小费用问题的描述，借助Floyd算法思想，给出了一种求解无向网络流最小费用问题的算法，该算法具有路径标记功能，可以自动生成费用修正回路，并且适用于有向网络流最小费用问题。参考文献[9]基于博弈论方法提出了一种不依赖于端系统用户合作的IP网络流速率控制框架，将网络中的流量源模型化为网络博弈中的局中人，竞争共享网络带宽资源，通过一种有效的带宽使用定价与收费机制，使博弈的Nash均衡解达到全局最优，得到有效与公平的网络带宽分配。

实现技术中常用的令牌缓冲调度方法是固定周期令牌缓冲调度方法[10-11]FCTB(Fixed Cycle Token Buffer)，FCTB根据当前时间与上次添加令牌的时间内使用的令牌总数量往缓冲池内添加令牌，并且是一次性添加完毕，没有分段添加。本文设计了一种多链路共享令牌缓冲池流量调度模型，研究了多链路令牌调度费用计算，基于费用最优研究了令牌缓冲流量调度负载计算方法COTB(Cost Optimization Token Buffer)，并且通过实验与FCTB比较，证明了本文方法有较好的流量调度能力，能有效地控制链路的流量，改善系统负载均衡。

2基于时延反馈的流量拥塞控制模型

2.1多链路共享令牌流量调度模型

多链路共享会牌流量调度模型如图1所示。假设某个系统中包含有N条逻辑链路，系统首先为每个进入系统的链路分配一个队列，各个链路的数据到达系统后，在各自的队列里进行排队整形，经过排队整形后再依次被送到共享令牌缓冲池。缓冲池在某个固定的时间间隔内产生一定的令牌，令牌是一种虚拟的资源，每个令牌代表允许通过一个最大的数据长度。共享令牌缓冲池中的令牌总数量表示当前系统允许通过的最大数据量，数据发送时将消耗令牌，令牌降到一定的数量后要重新申请加入补充令牌，流控实体可以通过控制共享令牌缓冲池令牌数量的存储对流量和系统负载进行控制。

费用指某动作或某状态所消耗的系统资源。对网络服务的计费要以占用的系统资源为基准，系统资源包括带宽资源、缓冲队列管理资源和CPU时间片资源等多种资源，网络服务通过对各种资源的使用来为用户提供服务质量，当对系统的某种资源出现竞争时，费用计算就必须要考虑多种资源的联合计算问题，这样才能使费用计算成为系统负载控制的有效手段。

2.2费用最优令牌缓冲流量负载计算方法

为了便于分析，首先对数据包在链路中的处理情况定义如下变量：

p1：每次共享令牌缓冲池申请增加令牌的费用。

p2：令牌来到缓冲池后在里面进行排队处理的费用，即每个单位时间每个令牌的储存费用。由定义可知缓冲池内令牌越多其平均储存费用就越大。

p3：当令牌缓冲池为空时，每个单位时间每条链路的等待费用。

n：每单位时间的令牌消耗总量。

Q：申请加入缓冲池的令牌总量。

T：申请令牌加入缓冲池的时间间隔，即申请周期。

q：任意时刻t缓冲池内的令牌的剩余储存量。

申请费用p1、平均储存费用p2及单位时间消耗量n均为已知常数。模型要以总平均费用为目标函数确定申请周期T和申请量Q的最优值。

一般来说，令牌缓冲池存在着两种状态：非空和空。非空表示不允许缓冲池内的令牌个数为0，当令牌个数大于或等于0时就可以申请往缓冲池中增加令牌；可以为空时表示允许缓冲池内的令牌个数等于0，当等于0时系统处于等待状态，不进行流量发送，将产生一定的等待费用。

(1)令牌缓冲池非空情况下的费用计算

由模型假设可以得出，申请周期T、申请量Q与每隔T时刻消耗量n之间满足如下关系：

由式(2)得每T时刻的平均费用为：

因此，制定最优费用令牌调度策略归结为求申请周期T使得 C(T)最小。

图 2 q>=0情况下 q(t)变化规律

利用微分法可以求出T和Q的最优值，分别记作 T′和 Q′：

并且根据式(1)代入求得：

(2)令牌缓冲池为空时的费用计算

当令牌缓冲池内的所有令牌都使用完毕后，令牌的存储数量为0，系统不进行流量发送，并进入等待申请令牌加入的状态，等待时可以把令牌储存量q视作负值，因此，q(t)的变化规律可以用图3表示。

图 3 q＜0情况下 q(t)变化规律

假设令牌在t=T1时刻全部用完，在一段时间内令牌的存储量为0，并且假设这时候令牌的消耗量仍然为n，在t=T时刻下一次令牌申请量q到达系统。于是由图3可以得出：

模型的目标函数仍为每单位时间的平均费用。

把式(7)中的 T1用式(6)代入，可知平均费用是 T和Q的二元函数，记作 P(T，Q)，且：

利用微分法可以求得：

若记：

则可以求得一个申请周期内的最小平均费用为：

当 T′>T时 Q′>Q，即在允许令牌缓冲池为空的情况下申请周期应增大，而申请数量应减少。但当等待费用p3越大时(相当于平均储存费用 p2时)，μ 越小，T′和 Q′就越接近 T和 Q。特别地，当 p3→∞ 时，μ→1，于是有T′→T、Q′→Q， 因为 p3→∞即等待造成的费用无限大相当于不允许令牌缓冲池为空。

3实验与结果分析

3.1实验环境

本文在NS2上实现了费用最优令牌缓冲流量调度负载控制方法，并进行了实验，实验使用的仿真网络拓扑如图4所示。网络拓扑由发送端s1～s3、路由器R1～R5和接收端r1、r2组成，各节点间链路带宽如图4所示，各发送端通过虚拟拨号连接建立一条到接收端的逻辑链路，分别为L1～L3，链路路径如图4虚线所示。本文在R3节点上对所建立的逻辑链路进行共享令牌流量控制。

3.2实验结果对比分析

实验中采用的对比方法为常用的固定周期令牌缓冲调度策略FCTB，主要考察这两种方法在相同出口流量的情况下的系统负载对比。

图5 缓冲池非空时出口流量对比

在令牌缓冲池非空的情况下，通过这两种调度方法造成出口流量差不多维持在同一水平上，大约为平均150 Mb/s，具体结果如图5所示，然后进行系统的负载数据采集，数据采集结果如图6所示。从图6可以看到，FCTB的最高系统负载为60.4%，最低为35.7%，平均系统负载为47.9%；COTB的最高系统负载为44.7%，最低为33.6%，平均系统负载为39.5%。造成FCTB比COTB系统负载高的原因主要是FCTB令牌缓冲池里面的未用到的剩余令牌较多，系统要花费大量的资源去维护整理那些在缓冲区里面的令牌，COTB虽然因为多次申请令牌到缓冲池增加了一定的系统负载，但总的系统平均负载仍然较FCTB低许多。

实验加大出口流量时，由图7可以看出，两种调度方法的出口流量最高达到约 160 Mb/s，约 20 s后，令牌缓冲池内的令牌使用完毕，出口流量迅速降到接近0，再用这两种方法对缓冲池进行令牌补充然后，出口流量得以恢复。由数据采集统计得到，FCTB平均流量为131.3 Mb/s，COTB平均流量为 133.2 Mb/s，两者大致相同。系统负载数据结果如图8所示，FCTB的最高系统负载为66.4%，最低为38.8%，平均系统负载为51.3%；COTB的最高系统负载为52.7%，最低为41.6%，平均系统负载为46.8%。虽然FCTB比COTB在某段时间内的最低系统负载要低，但是平均系统负载仍然比COTB高出约4.5%。由此可见，COTB在平均系统负载、负载峰值、负载均衡等方面都比FCTB要好。

本文讨论了多链路流量调度系统负载优化问题，给出了基于共享令牌调度和流量调度负载均衡体系模型，提出了基于费用最优的令牌缓冲流量调度负载计算方法，并在广东茂名学院校园网上成功地实现了上述方法和体系结构。实验结果表明，增大了网络通过量，降低了平均系统负载，链路在整个网络结构里有良好的时间响应特性，取得较好的应用效果。

下一步主要工作是对更多QoS受限条件下的多链路流量调度问题，对具有不同优先权请求的链路进行区分以及基于处理节点计算能力的负载迁移等问题进行研究。

参考文献

[1]WANG H， XIE H Y， QIU L L.COPE：traffic engineering in dynamic networks[A].In：Proceedings of ACM SIGCOMM[J].Pisa， Italy：ACM ComputerCommunication Review，2006，36(4)：99-110.

[2]刘郁恒，陈广文，胡严，等.一种在接收端实现的 TCPFriendly 拥 塞 控 制 机 制[J].电 子 学 报 ，2005，33(5)：835-841.

[3]张桂英，吴学智.下一代宽带接入网 QoS研究[J].计算机应用，2007，27(6)：174-176.

[4]武航星，慕德俊，潘文平，等.网络拥塞控制算法综述[J].计算机科学，2007，34(2)：51-56.

[5]黄启萍.流量控制与 IP服务质量[J].计算机工程，2006，32(11)：144-146

[6]葛敬国，马宏伟，钱华林.Internet自治系统间负载均衡机制及其性能分析 [J].计算机应用，2005，25(12)：2916-2917.

[7]陈晓梅，卢锡城，王怀民.基于微观经济学方法的网络资源分配研究[J].计算机研究与发展，2001，38(11)：1345-1353.

[8]付彤，郭强.无向网络流的最小费用问题[J].计算机工程与 应 用 ，2005(28)：88-90.

[9]钟伯成，韩江洪.网络速率控制的博弈模型[J].华南理工大学学报(自然科学版)，2007，35(9)：85-89.

[10]涂文伟，张进，张兴明.分级统筹分配令牌参数的流量整形算法[J].计算机应用，2006，26(9)：2175-2177.

[11]雷雯，许都，黄振华.以数据流特性为导向的令牌调度算法[J].电子科技大学学报，2005，34(6)：955-958.