分布式队列服务算法在无线网状网包调度中的应用

李精华,嵇建波

(桂林航天工业高等专科学校 电子工程系, 广西 桂林541004)

1 引 言

无线网状网作为下一代的无线网络技术,必然要求它能够传输高速的多种数据业务,支持这些业务关键就是要保证业务的QoS 要求[1],与QoS 密切相关的技术就是如何为网络设计合适的包调度算法。包调度算法就是通过对数据包进行缓存,控制数据包的发送时间和发送次序。

目前的无线包调度算法主要集中在保障网络各连接的QoS 前提下,追求系统吞吐量极大化,是基于数据包所属的“类”或“流”来进行调度的,在进行调度时,调度器首先会把应用业务分成不同的“类”或“流”,并给这些业务流赋予不同的优先级,然后调度器根据这个优先级来对数据包进行调度,比如EDF调度算法就属于这种。这样的调度策略有一个典型的缺点,就是当网络增加一类新的服务时就需要对调度器进行相应的配置,使它能支持相应的服务,因此传统调度算法的可扩展性是一个不容忽视的问题。另外,传统调度器对应用业务的分类不细,从而会导致一些低优先级的包长时间得不到服务。

基于以上算法的弱点,本文提出一种分布式队列服务算法(DQS),能根据数据包所经过端到端的变化情况进行动态的调度。DQS 算法为网络提供更为细化的应用业务,在保证实时用户的QoS 需求的前提下,充分考虑用户的公平性,实现最大化系统的吞吐量。

2 分布式队列服务算法(DQS)描述

差分队列服务算法[2]目的是为了在有线网络中为各类数据业务提供更加细化的QoS,主要优点是能够根据资源的利用情况给业务应用提供更加细化的端到端QoS 服务。其算法的基本原理是:设一个网路由n 个节点组成,数据包的传输路径是固定不变的,在不考虑传播延时,当一个数据包到达节点i时,该数据包端到端的剩余延时为

其中,T 为数据包的最大的端到端延时, τi为数据包经过i 所花费的实际延时。这样,数据包在某个节点所允许最大有效延时δi为

如果上游的节点都按固定的算法限制了每个数据包的延时,那么就可以得:

其中,yi为数据包到达某个节点的时间;xi为数据包离开某个节点最近的时间,这个时间被用来作为包在缓存中排队顺序的依据。

由式(1)～(3)可以看出,差分队列服务算法对数据包进行调度的依据是端到端的延时而不是根据数据包所属的数据流或类。通过这种方式,差分队列服务算法可以为应用业务提供更加细化的QoS 支持。在无线网格网中利用差分队列服务算法为应用业务提供端到端QoS 的支持是很有益处的,但公式(2)中节点i 是利用δj(j >i)来推导公式(3)中的xi,这在无线网络中是很困难的,因为δj只能在将来的某个时刻得到,而不可能在数据包到达本节点时计算出来。因此实现DQS 算法一个很重要的问题就是如何在节点i 去估计δj的值,也就是说如何去估计数据包在剩余路径的延时情况。

分布式贝尔曼-福特算法[3]是在贝尔曼-福特算法基础上演进出来的可预测表驱动路由算法,也就是说每一个节点都会维护一个路由表,每一个节点都会初始化一个到它相邻节点的距离矢量表。比如有一条链路,它由6 个节点组成,节点1 在某个时刻t 1发送出去一个探测包,在时刻t 2节点2 收到这个探测包,则节点1 到节点2 的单步延时为t1-t2,此时为节点2 创建一个时延表,这个表用来记录经过节点2 的所有数据包的延时情况。同时,为了让节点2 能够知道其他节点间的延时情况,必须要求每个节点在发送探测包的同时把自己的时延表也发送出去。这样经过一段时间后节点2 就能够知道这条链路中任意两个节点之间的延时了,这个时延表如表1 所示。

表1 节点2 中的时延表Table 1 Delay table at node 2

根据表1 所示的时延表,当一个数据包到达节点时DQS 调度器可以通过查询表1 所示的延时表来知道数据包在剩余路径的延时情况,然后通过公式(2)计算出数据包在本节点的最迟离开时间,DQS调度器会根据离开时间的大小对数据包进行排队。离开时间越小表示数据包需要越早得到服务,反之说明数据包可以在节点里停留相对较长的时间,因此可以把它放在队列的后面。

3 分布式队列服务算法性能分析

这里使用Ad Hoc 网络仿真模型[4],在NS2 仿真平台上进行仿真分析[5]。

3.1 探测包性能

数据包在剩余路径所经历的时延估计主要是通过路由层发送探测包得到的,探测包发送的目的是为了估计当前网络的延时情况,即探测包的延时反映了网络当前的延时情况,探测包的延时小网络则当前的拥塞小,探测包的延时大则网络拥塞也大。一般探测包的数量随着探测周期的变大而减少,探测包的数量可以通过理论公式(4)计算:

式中,N 表示节点数,L 表示仿真的时间长度, T 表示探测包的发送周期, n 表示仿真过程中总共发送多少探测包。

在NS 仿真平台上对7 个节点的探测包数量在不同的发送周期下进行仿真分析,仿真场景采用CBR 流和VBR 流共存的方式,使用线性拓扑结构,路径长度为6,仿真时间为500 s。图1 是7 个节点的探测包的数量在不同发送周期下的曲线变化图。从图1 可以看出,当时延探测包发送周期为1 s时,节点在仿真过程中总共发送出约3 500个探测包;当时延探测包发送周期为12 s时,节点在仿真过程中总共发送出290 个探测包。仿真结果与公式(4)计算出来的结果是相吻合的,从而验证了DQS 调度算法的探测包的延时符合设计需求。

图1 不同探测周期下的探测包数量Fig.1 The number of hello packet in different period

3.2 缓冲区的使用率

在DQS 调度算法中使用了控制包队列和数据包队列两个队列,NS 仿真使用CBR 流和VBR 流,线性拓扑结构,7 个节点数,仿真总时间是500 s,每个队列的最大长度为50 个包,探测包的发送周期每3 s发送一次。对控制包队列和数据包队列在每个节点的使用情况进行统计,计算每个节点队列的平均使用率和最大使用长度。图2 为控制包队列中每个节点在整个仿真周期内的使用情况。从图2(a)可以看出,中间节点队列的使用率最高,这也表明中间节点最可能成为网络的瓶颈节点。图2(b)是每个节点中控制队列的最大使用长度,最大使用长度是指节点在最繁忙时最多需要处理多少个包,图2(b)的中间部分最高,表明需要处理的包数量最多。因此从图2 中可以看出,控制包在中间节点会等待较长的时间,这与实际情况也是吻合的。

图2 控制包队列的统计Fig.2 Statistic of control packet queue

图3 为数据包队列在每个节点的使用情况,其曲线的趋势与控制包队列基本相似。在DQS 调度算法中,由于控制包和数据包的发送速率以及处理优先级是不同的,其中数据包的优先级比控制包的优先级低,因此从图2 和图3 可以看出,数据包队列的平均利用率比较高,但数据包队列要比控制包队列要长。

图3 数据包队列的统计Fig.3 Statistic of data packet queue

从图2 和图3 中可以看出,DQS 算法对缓存的要求不高,这样可以节省更多的缓存空间。

3.3 实际平均吞吐量分析

实际平均吞吐量[6]是指数据发送者成功地传输给接收者的度量标准,即接收端成功接收到的包个数与发送端发送的包个数的一个比值。为了便于仿真分析,在这里接收端只计算那些满足端到端延时的数据包个数。在NS 仿真中采用随机拓扑网络结构,运用恒速比特率(CBR)和变速比特率(VBR)两种数据源,每一个队列的长度是50 个数据包,通过改变数据源的个数和节点的个数来模拟真实网络中的情景。这里以EDF 调度算法作为参照算法与DQS 算法进行对比分析。图4 为DQS 调度算法和EDF 调度算法的平均实际吞吐量曲线图,其中图4(a)使用CBR 流,图4(b)使用VBR 流,这两种数据源的前6 跳EDF 调度性能与DQS 调度性能相差不大,一旦数据包的路径长度大于6 以后,DQS 调度算法平均实际吞吐量下降的程度明显要低于EDF 调度算法。最好的情况是DQS 调度算法的实际平均吞吐量比EDF 调度算法的实际平均吞吐量性能提高了16%。其原因是DQS 调度算法充分考虑了应用业务的端到端情况,它可以根据数据包端到端的变化来对其进行调度;而EDF 只是在每一跳给数据包一个固定的延时,并且是基于这个延时来对数据包进行调度,它并没有把数据包端到端的变化情况考虑进去。所以当数据包路径长度发生变化时,EDF 调度算法的实际平均吞吐量性能比DQS 调度算法的性能下降得快。

图4 平均实际吞吐量Fig.4 Average throughput

3.4 平均端到端延时分析

平均端到端延时是指数据包从原节点到目的节点所经历的平均端到端延时[7]。使用的仿真条件和2.3 节的仿真条件一样, 图5 为DQS 调度算法和EDF 调度算法[8]的端到端延时曲线图。

图5 端到端延时Fig.5 The delay of end-to-end

从图5 可以看出,DQS 调度算法的端到端延时性能比EDF 调度算法的性能好,这主要是由于DQS调度算法会把数据包的端到端延时作为一个调度因素来考虑,所以它具有更好的端到端延时性能。

4 总 结

无线网状网作为下一代无线网络的关键技术,为其设计合适的包调度算法是一项很有挑战性的工作。DQS 包调度算法解决了无线网状网为多个等待接收服务的分组业务流安排合理的服务规则,特别是DQS 包调度算法在缓冲区的使用率、实际平均吞吐量性能和平均端到端延时性能上具有较高的性能。但还存在一些不够完善及有待改进的地方,比如在DQS 调度算法中控制包和业务数据包在网络传输过程中的相互影响,如何在环境变化的无线链路中使探测包的周期控制在一个合适的范围之内,在高速运动情况下的性能情况有何区别等,这些问题还需要深入研究。

[1] 刘俊芳,赵尔敦,刘巍.小无线网络中基于BLUF 的包调度算法[J] .计算机工程与应用,2008,44(16):108-110.

LIU Jun-fang, ZHAO Er-dun, LIU Wei.Wireless packet scheduling algorithm based on BLUF in wireless networks[J] .Computer Engineering and Applications, 2008,44(16):108-110.(in Chinese)

[2] Jiang S M.Granular Differentiated Queueing Services for QoS:Structure and Cost Model[ J] .ACM SIGCOMM Computer Communication Review, 2005, 35(2):13-22.

[3] Bertsekas D, Gallager R.Data Networks[ M] .Englewood Cliffs, NJ:Prentice-Hall,1987.

[4] 钱权.无线Ad Hoc 网络安全[M] .北京:清华大学出版社,2009.

QIAN Quan.Wireless Ad Hoc Network Security[M] .Beijing:Tsinghua University Press,2009.(in Chinese)

[5] 时慧晶, 赵烨.基于NS2 的Ad Hoc 网络路由协议性能研究[C]//全国第21 届计算机技术与应用学术会议(CACIS·2010)暨全国第2 届安全关键技术与应用学术会议论文集.上海:[ s.n.] ,2010:17-131.

SHI Hui-jing, ZHAO Ye.Research on Performance of Ad Hoc Routing Protocol Using NS2[ C]//Proceedings of the 21th National Computer Technology and Application Conference and the National 2nd safety -critical Technology and App lication Conference.Shanghai:[ s.n.] , 2010:17 -131.(in Chinese)

[6] 顾金媛, 章国安, 包志华.认知无线mesh 网中联合路由的分布式信道分配算法[J] .计算机应用研究,2010(9):3476-3479.

GU Jin-yuan,ZHANG Guo-an, BAO Zhi-hua.Distributed joint routing and channel assignment algorithm in cognitive wireless mesh networks[ J] .App lication Research of Computers, 2010(9):3476-3479.(in Chinese)

[ 7] 陈潜,刘云.动态高速环境下Ad Hoc 路由协议研究[J] .中北大学学报(自然科学版),2011(10):579-582.

CHEN Qian,LIU Yun.Research on Ad Hoc Routing Protocol in High Speed Dynamic Environment[ J] .Journal of North University of China(Natural Science Edition), 2011(10):579-582.(in Chinese)

[ 8] Guerin R,Peris V.Quality-of-service in packet networks:Basic mechanisms and directions [ J] .Computer Networks,1999, 31(3):169-189.