基于优先公平调度的网络链路状态测量方法

张敏++邱恭安++张士兵

摘要：在不增加网络开销前提下为实现网络实时状态的测量，利用优先公平调度原理中隐性的网络状态统计功能，提出使用周期性测量的优先队列队长和链路公平速率指标估计下游链路承载状态，实现无开销的链路状态测量。仿真显示优先队列队长和链路公平速率变化曲线能够反映出下游链路的不同负载率变化。

关键词：网络测量 优先公平调度 公平速率

中图分类号：TP393 文献标识码：A 文章编号：1007-9416（2016）12-0052-02

1 引言

网络链路状态是指定信源和信宿间路径承载的数据分组状态，反映了链路和网络负载的流量信息，常作为状态参数用于网络流量控制和拥塞控制。当前，多业务综合承载是网络IP化的应用趋势，不同业务具有不同的特征，需要差异化的服务性能保障[1]，因此，实时获得网络链路状态是差异化保障不同业务服务质量和有效提高网络效率的基础。

目前，网络链路状态测量主要是显式的测量方法，包括主动测量和被动测量两类。主动测量方法针对网络性能参数发送探测分组，通过收到的应答分组分析计算网络状态，但增加了网络额外开销，且具有较大的网络状态测量时延。被动测量通过在网络中设置流量监测点，捕捉网络的流量参数，获取网络承载业务的统计信息，其无需发送测量数据分组，但需要网络节点设备被动地收集数据包，操作相对复杂，网络状态信息存在一定的陈旧性。随着，网络信息安全的提高以及多业务综合承载的扩展，既有网络链路状态测量方法的测量精度和时延受到很大影响[2]，针对该问题，本文利用优先公平调度机制中队长参数和链路公平速率实现隐式的网络联网状态测量，能够为两类不同业务分别提供业务匹配的链路状态。

2 优先公平调度机制原理

分组调度指按照一定的规则决定从等待队列中选择分组进行发送，使得所有输入业务流能够按照预定的方式共享输出链路带宽[3]。优先公平调度包含绝对优先公平调度和相对优先公平调度，其中，绝对优先公平调度以连续方式为目标队列赋予优先级，当调度分组时，如果高优先级队列非空，则其分组优先被选择服务。只有高优先级队列为空时，才会服务次高优先队列。为提高调度机制对链路状态的适应性和业务服务公平性，提出了相对优先公平调度，其为高优先队列预留一定的缓存空间，使得低优先队列能相对公平地得到调度服务，仅当优先队列队长超过一定门限时，才为优先队列提供绝对的优先转发。

当网络业务分为时延敏感和可靠性敏感两类业务时，优先公平队列调度算法在逻辑上维护两个队列，优先队列和普通队列。当有新业务到达时，首先根据业务属性判断出业务类型，若该业务类型属于优先业务，则将该业务分组置于优先队列队尾，若检测到优先队列为空，则将该业务分组插入优先队列队首；若属于普通业务，则将该业务分组置于普通队列队尾，若检测到普通队列为空，则将该分组插入普通队列队首。当业务被调度转发时，若优先队列不为空，则转发优先队列中的业务分组，若优先队列为空，则转发普通队列中的业务分组，若在普通队列分组转发期间，有优先业务分组到达，则待当前普通业务分组发送完成后，再转发优先队列分组，优先队列和普通队列内部采用先到先服务模式。

3 隐式网络链路状态测量方法

在综合业务承载的IP网络中，时延敏感业务一般具有较低且稳定的传输速率，但需要相对持久的传输时间，要求较小的端到端时延，能够容忍一定程度的分组丢失，如VoIP业务。可靠性敏感业务一般是传统弹性网络流，其接入峰值速率为接入线速率，对分组丢失率敏感，但可接受较大的端到端传输时延。因此，若根据业务请求接入峰值速率特征，将网络业务分为两类，则优先調度机制可建模为两队列优先排队模型[4]。其中，优先队列分组具有绝对的优先转发权，优先使用网络资源来满足其请求的服务质量，普通队列分组仅使用优先队列分组剩下的有效资源。当网络节点下游链路资源不足以实时转发优先分组时，优先分组进入缓存进行排队，因此，优先队列的排队等待时间和优先队列分组队长间接反映出下游链路承载状态，隐式地反映出链路中时延敏感业务的负载状态。由于可靠性敏感业务所在的普通队列分组仅使用优先队列分组剩下有效链路资源，当下游链路中资源不足时，普通队列中的分组会得不到及时的服务，网络节点进程中该类业务数量随之增加，因此，链路公平速率间接反映了下游链路普通业务的负载状态。因此，利用优先公平调度机制中优先队列队长和链路公平速率参数能够实现对链路状态的隐式测量。

设网络节点通过在优先队列的入口处设置计数器对优先队列缓存中比特数进行统计，利用该计数器的时间相对变化值估计出优先队列分组排队的总比特数。假设在时刻t1，计数器的数值pb（t1），在时刻t2，计数器的数值为pb（t2），C是链路有效带宽，则优先队列队长priority_load计算公式为。

公平调度机制通常使用最大-最小公平份额算法计算链路的公平速率。设网络节点进程中共同承载M类业务，且各自有独立的峰值速率，记为Rp={R1， R2，…， RM}，且R1

公平速率是一个随进程中业务规模波动而动态变化的值，能够动态反应链路负载状态。

4 测量方法实验与分析

4.1 仿真实验设置

网络仿真拓扑如图1所示，其中，s0 s1 s2 s3 s4 s5为六个源节点（信源），节点s0和s1设置为TCP Agent，应用层协议为FTP；节点s2 s3 s4和s5设UDP Agent，应用层协议为CBR。r1和r2为网络节点，仿真对其间链路状态进行测量，网络节点使用优先公平调度机制，其它节点均应用尾丢弃策略（DropTail），接纳控制机制配置在链路入口节点处，链路总缓存为Bmax=64 个分组。为实现下游链路处于轻载、重载和过载不同状态，四个发送CBR业务源节点的发送速率设为3Mbps，与网络节点间的接入链路带宽设置为3Mbps，两个发送FTP业务源节点与网络节点间的接入链路带宽设为4 Mbps。网络节点间的链路带宽设为12 Mbps，所有链路时延均为1 ms。设时延敏感业务为语音UDP分组，可靠性敏感业务由TCP业务组成，优先队长和公平速率的测量间隔均为100 ms，仿真统计了目标链路上两类业务参数曲线分别如图2，3所示。

4.2 实验结果与分析

由图2可知，四个CBR信源分别在0.0 s，2.5 s，5.0 s，7.5 s时刻开始发送数据，在10.0 s 11.0 s 12.0 s 12.5 s时刻停止发送。在0.0 s到2.5 s时间范围内，一个CBR信源发送数据，峰值速率为3 Mbps，而网络链路带宽为12 Mbps，此时优先队列队长均值为零，下游链路能够及时转发所有的CBR分組，不需等待调度，优先队列处于轻载状态。在2.5 s到5.0 s时间内，两个CBR信源发送数据，峰值速率为6 Mbps，下游网络链路出现来不及转发已到达优先分组，优先分组需要排队等待调度转发服务，此时优先队长在15个分组到25个分组之间浮动，反映出优先业务负载状态由轻载进入重载情况。在5.0s到7.5s时间内，CBR信源发送速率从6 Mbps增至9 Mbps，理论上下游链路出现重载情况，由于下游链路转发速率低于优先分组到达速率，因此，优先队列中缓存了大量等待转发的优先分组，优先队列队长在25个分组到50个分组之间变化，达到了链路总缓存的50%以上，属于重载情况。在7.5 s到10 s时间内，CBR信源的总发送速率达到峰值，4个CBR信源同时发送，峰值速率达到12 Mbps，链路处于过载状态，此时，优先队列中缓存的分组个数已高达64个，达到了设置的队列长度的最大值，反映网络链路处于过载状态。

由图3可知，两个FTP信源分别在0.0 s和0.5 s处开始发送数据，在12.0 s和12.5 s处结束发送数据。在仿真开始时，一个FTP信源开始发送数据，链路公平速率在短时间内升到8Mbps，反映出下游网络链路分配了充足的有效带宽用于普通业务传输。在2.5s处，5.0s处和7.5秒处公平速率分别出现了明显下降并逐渐稳定的过程，在7.5s之后降到接近0，下游网络链路普通业务的吞吐量降为0，此时，普通业务处于饿死状态，网络处于严重拥塞状态。

综上所述，当网络链路处于轻载状态时，优先业务分组被直接转发，优先队列的平均长度为零，普通业务分组使用优先分组剩余有效带宽，以较高的公平速率进行传输。当链路处于轻微的重载状态时，优先业务分组通过排队使用下游网络链路资源，并使用非抢占型调度，优先分组等待正在发送普通分组完成后才插入队首被调度，因此，优先队列队长随时间增加到一定数值，且链路公平速率开始降低。当链路处于重载状态时，下游网络链路由于来不及转发收到的优先分组，优先分组排队队长增加到总缓存的50%以上，网络链路剩下的有效带宽进一步减小，普通业务的链路公平速率与优先业务负载率成反比例变化，但仍维持着最基本的普通业务吞吐量。当链路处于过载状态时，优先业务使用全部网络链路带宽以满足其请求的服务质量参数，挤占了普通业务需求的网络资源，普通业务的传输被迫中断，链路公平速率降到零。可见，在优先公平调度处理时统计优先队列长度，由最大-最小公平份额算法计算链路公平速率，能够从不同角度估计下游链路的准实时负载状态，实现对网络链路状态的隐式测量。

5 结语

所提隐式网络链路状态测量方法能够准实时的反应网络链路中不同业务的负载状态，相较于主动测量方法，不需要发送探测分组，减少了测量过程对链路本身状态的影响。相较于传统被动测量方法，不需要设置网络流量监测点，不涉及网络业务的隐私安全。所提网络链路状态测量方法通过周期性测量获得链路状态信息，存在一定的时滞性，能够为一般网络监测提供应用参考。

参考文献

[1]尹浩，李峰.互联网性能测量技术发展研究[J].计算机研究与发展，2016，53（1）：3-14.

[2]冯韬，于建江.复杂环境下的网络时延测量方法研究[J].科技信息，2012，（22）：27，29.

[3]林闯，单志广，任丰原.计算机网络的服务质量（QoS）[M].北京：清华大学出版社，2004：170-174.

[4]邱恭安，张顺颐，胡隽.基于模糊流感知的动态优先公平调度算法[J].电子与信息学报，2009，31（2）： 467-471.