无线网络中基于优先级队列延迟限定的研究
2016-10-17卢浩洋陈世平王迅登
卢浩洋，陈世平，2, 王迅登
(1.上海理工大学 光电信息与计算机工程学院，上海 200093；2. 上海理工大学 信息化办公室，上海 200093)
无线网络中基于优先级队列延迟限定的研究
卢浩洋1，陈世平1，2, 王迅登1
(1.上海理工大学 光电信息与计算机工程学院，上海 200093；2. 上海理工大学 信息化办公室，上海 200093)
由于无线网络环境下网络节点的增加，网络延时成为一个亟待解决的问题。为了提高服务质量(QoS)，提高吞吐量，文中提出了一种基于优先级的队列延迟模型，通过将每一个包预设置优先级来区分其重要性和实时性，同时将每一个AP设备中的队列根据优先级划分为3种类型，并将预设优先级的包放入其中进行传输，从而有效减少发送端的队列延迟。通过分析和仿真可以发现，与未划分优先级队列的节点网络相比，这种方案不仅使单个节点的延迟大幅减少，也使整个网络的平均延迟明显降低，网络整体性能显著提高。
无线网络；队列延迟；优先级；预设置；服务质量
随着无线网络的不断发展，无线网路环境中各种业务的多样性对于网络延迟是一种挑战，这种多样性[1]主要体现在具有实时特性的数据包和对实时性要求较低的数据包。对于每个AP(AccessPoint)[2]设备，具有实时特性的数据包，通常对网络的传输时延均有阀值限制要求，还具有数据量大，持续传输等特点；对于实时性要求较低的数据，通常对于时间还是可以容忍的。对于这两大类的数据传输的权衡发送直接关系到网络延时，进而影响到用户体验的时间。
数据包在传输过程中，经过每个AP逗留的延迟通常包括发送延迟和队列延迟。对于发送延迟，无法准确控制，但可通过设计一个有效的队列调度算法减少数据包在队列中逗留的延迟。传统情况下，队列的调度机制一般采用先来先服务(FIFO)[3]。明显，这种调度机制有失实时性和公平性，为克服上述缺陷，本文提出了一种新的队列调度机制：基于优先级的队列延迟调度机制(Delay-basedPriorityQuenueScheduling，DPQS)，进而对每一个优先级队列[4]分配权重值，并分配带宽值，按照优先级的由高到低轮询每一个优先级队列。
1 相关研究
为提供QoS[5]保证的策略，一种好的队列调度机制需要考虑以下几点：(1)在各种数据流的传输过程中，应保证流的公平性；(2)数据流之间减少彼此之间的影响，不能影响流与流之间的带宽分配；(3)若一个流占用的带宽还有盈余，可允许其他流适当占用。
目前，在无线网络中使用最多的队列调度策略是先来先服务(FIFO)。
这种队列实现起来相对较为简单，调度也比较方便；最大时延可通过最大队列的长度来决定，时延的大小与队列的长度成正比。但这种队列调度算法有明显的弊端：(1)没有兼顾实时性高和实时性低的分组公平对待；(2)当遇到拥塞发生时，业务流的平均排队时延均会增加，对于任何一种业务流的影响均一致，但对于实时性要求高的流不利；(3)隔离性不佳，当有一个突发的业务流可能便会占用整个缓存空间，以至于其他的业务流均无法进入。
2 系统建模
本文DPQS建模过程主要包括前期的预设优先级，DPQS模型，后期的丢包处理，以及算法设计的介绍。设定一种减少数据包在AP中逗留延迟的调度方法，通过在外队列中筛选数据包，子队列中根据数据包划分优先级的方法来合理调度数据包的发送，本文不考虑数据包在传输过程中的延迟和在AP端中的发送延迟，而只考虑其在队列中的延迟。
2.1预设值优先级
通过分析IP版本4[6]的分组首部结构可知:服务类型字段(TOS)包含8bit，其中还包括一个3bit的优先权子字段，其取值可为000～111，4bit的TOS子字段和1bit未用位。文中可利用这一个未利用的8位字段，将数据包最多划分为8种优先级，进而能将一个缓冲区中的子队列最多划分8个队列，如图1所示。
图1 TOS字段
当包进入支持型队列中的对应的优先级队列时，同一优先级队列的包再按照FIFO的顺序排列好，等待调度。
2.2DPQS模型
这里DPQS模型主要采用一种划分缓冲区的做法，首先将一个缓冲区等分的划分为3个队列，分别为支持型队列、非支持型队列、尽力而为型队列，当一个数据包来到中继节点时，其会先进入支持型队列，当支持型队列阻塞时，才会调度数据包进入非支持型队列，当非支持型队列阻塞时，会调度数据包进入尽力而为型队列中，若这3个队列都阻塞，则会丢弃优先级最低的数据包，并要求发送端降低发送速率。在此，支持性队列的优先级大于非支持型队列，非支持型队列优先级大于尽力而为型队列，既Priority(Support)>Priority(Unsupport)>Priority(Try)如图2所示。
图2 队列模型
当数据流通过时，整个数据包的调度大多数情况下均是在支持型队列中调度，当支持型队列发送阻塞才会用到后续非支持型队列和尽力而为型队列。整个外围队列的调度机制必须满足条件：(1)要产生尽可能少的非支持型和尽力而为型队列数据包，争取能在支持型队列中全部调度完毕；(2)若支持型队列中的数据包未发送完，就不会调度非支持型；同理，若非支持型队列中的数据包未发送完，便不会发送尽力而为型队列中的数据包。
这3个队列又分别划分几个子队列，这些子队列均按照优先级划分。子队列的个数主要取决于TOS字段中划分的优先级个数。
子队列中根据业务应用类型对接受到的包分类处理，并将其分别划分到对应的优先级队列中，然后根据不同的优先级，为优先级队列分配对应的权重值；并根据各优先级队列分配到的权重值，为各个优先级队列分配相应的带宽。
当发送数据包时，按照优先级的顺序依次轮询各优先级队列，并根据各个队列分配得到的带宽从对应队列中取出相应数量的数据包进行调度。
这样，该调度机制不但能保证高优先级的业务需求可及时地得到满足，还具有一定的公平性。当服务不能及时满足时，可利用降低低优先级带宽和减少低优先级需求来保证实时高优先级的业务的带宽保证,如图3所示。
图3 优先级队列模型
如图3所示，若划分的优先级队列只有3个，队列A中的优先级是最高的，故会最先调度，之后依次调度队列B和队列C中的数据包。外队列的这3种类型均会有这些优先级子队列，但本文希望尽量不要用到非支持型队列和尽力而为型队列。
这种优先级划分还会维持一个延迟阀值。每一个子队列中都会设置一个阀值T(T>0)，当发现该数据包在对应的队列中逗留时间已超过T时，该数据包将失效，且优先级的大小与延迟阀值的设定成反比。
区别于常用的优先级调度算法机制的特点还有就是当数据包进入支持型队列时，该数据包首先会先在TOS字段中查找属于自己的优先级，本应加入对应的优先级K队列，当发现高于K优先级队列中不拥挤或数据包量较少的情况下，可越级进入相应高优先级队列，占用高带宽，发送更快，节约延迟。
这样会产生两种情况，超过队长L或小于队长L。当在高优先级队列中混杂着低优先级数据包时，陆续进来高优先级包，若在所有包长总和小于队长L时，则按照FIFO顺序依次传输。若包长总和大于L时，就将低优先级中的包调度到对应优先级队列中。
若此时包长总和>L时，本该将低优先级包调度对应队列中，但此时低优先级包已传输一部分，在此用传输率P来表示，若P>50%，则将该包继续发送，直至发送完成；若P<50时，直接将该包丢弃。
当支持型队列中的数据包发生阻塞时，会从优先级最低的队列中调度数据包放到非支持型队列中。同理，非支持型队列发送阻塞时，也会调用优先级最低的队列中数据包，将其放入到尽力而为的队列中。图4是数据包通过时，调度的具体流程图。其中，P(k)表示优先级为K的数据包；L(support)代表的是支持型队列中包的长度；RalaxValue是判断当前支持型队列是否空闲的临界值；Q(i 图4 DPQS流程图 2.3丢包处理 本文沿用有线网络中常用的基于RED拥塞避免策略，RED[7]算法常用于路由器的队列管理中，从而控制缓存空间的长度。之所以将其应用到无线网络中，是为了采用拥塞度门限值来进行拥塞调节。通过丢弃分组或通知源节点降低发送速率的方法，保证队列长度不超过对应的门限值，如图5所示。 图5 RED算法丢弃函数 该RED函数横坐标K代表的是平均长度，纵坐标P代表的是分组丢弃概率。该RED算法在计算平均对长K时，采用了类似低通滤波器带权值的方法 K=(1-η)×K+η×q 其中，η为权值，相当于低通滤波器的时间常数；q为采样测量时实际队列的长度。 本文通过引入RED算法门限值，设定了两个关于拥塞程度的门限值K1和K2。当支持型队列接受分组时产生的拥塞度值 模拟仿真实验采用Matlab[8]软件进行，仿真运行平台为Pentium(R)Dual-CoreCPU，内存4GB。通过与FIFO队列的性能进行比较，评估DPQS队列的性能指标。本文着重评估了整个队列系统的吞吐量以及在队列中逗留的延迟性能进行分析比对。 实验1验证两种队列调度模型对吞吐量的影响，对FIFO模型和DPQS两种模型的网络吞吐量进行了研究，所得实验结果如图6所示。 图6 网络吞吐量 实验结果分析：根据图中所示的信息可得出，DPQS模型的吞吐量始终处于一个较高的状态，且趋于稳定，但FIFO模型的吞吐量总体上呈现出递减趋势，且并不稳定。可以看出，DPQS在网络吞吐量上明显占用优势，而总体提高了QoS。 实验2验证两种队列所产生的延迟比较。对FIFO模型和DPQS两种调度模型的队列延迟进行了研究比较，所得到的实验结果如图7所示。 图7 数据包在队列中的延迟 通过图7所示的结果可看出，每个AP节点的延迟时间均有着明显的变化，相对于FIFO队列模型，DPQS模型的队列延迟始终处于一个较低的水平，延 迟改善的主要原因在于对数据流进行了优先级划分，区分了业务类型，有针对性地调度策略，较好的解决了传输次序的合理性。 本文提出了一种较为新颖的基于优先级的队列调度模型，通过预设值优先级的方式区分业务类型，再将整个AP队列缓冲区划分为3种队列模型，在子队列中根据预设优先级划分优先级队列的方式来调度传递过来的数据包。并配置RED丢包处理机制来有效地处理废弃数据包，再通过M1+M2/M/1/L[9]来分析两种模型的合理性，验证DPQS模型的可行性。最后，通过模拟仿真实验来证明该模型具有一定的扩展性，降低了队列时延，提高了网络系统的吞吐量，网络整体性能也得到显著提高。 [1]AshourM,Le-NgocT.End-to-enddelaymarginbalancingapproachforroutinginmulti-classnetworks[J].WirelessNetworks, 2007, 13(3):311-322. [2]徐浩.无线网络传统AP与现代AP性能探讨[J].价值工程,2013(28):238-239. [3]印红云,王志良,王莉.网络中常用的队列管理方法比较[J].微计算机信息,2005(11):3-4. [4]周鹏,郝明,唐政,等.基于QoS的优先级队列调度算法[J].电子科技,2013,26(5):122-124. [5]Charikarm,NaorJ,SchieberB.ResourceoptimizationinQoSmulticastroutingofreal-timemultimedia[J].IEEE/ACMTransactionsonNetworking, 2004, 12(2):340-348 [6]沈庆伟,张霖.基于隧道的IPv4/IPv6过渡技术分析[J].计算机技术与发展,2007,17(5):170-172,176. [7]FloydS,JacobsonV.Randomearlydetectiongatewaysforcongestionavoidance[J].IEEE/ACMTransactionsonNetworking,1993,1(4):397-413. [8]李柏年,吴礼斌.Matlab数据分析方法[M].北京:机械工业出版社,2012. [9]KronerH,HebuterneG,BoyerP,etal.PrioritymanagementinATMswitchingnodes[J].IEEEJournalonSelectedAreasinCommunications, 1991, 9(3):418-427. Research on Wireless Network Transmission Side Defining Priority-based Queuing Delay LUHaoyang1,CHENShiping1,2,WANGXundeng1 (1.SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China;2.InformationOffice,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China) Wirelessnetworkstechnologyhasbroadprospectsintoday'ssociety.Withtheincreaseinwirelessnetworknodes,networklatencyhasbecomeanimportantproblemtobesolved.Inordertoprovidequalityofservice(QoS)andincreasethroughput,weproposeamodelbasedonpriorityqueuingdelayofeachpacketbypre-settingprioritiestodistinguishtheirimportanceandtimeliness,whileeachoftheAPaccordingtothepriorityqueueisdividedintothreetypes,andthedefaultprioritypacketsintowhichtransmission,thuseffectivelyreducingthesenderqueuingdelays.Simulationshowsthatcomparedtonon-prioritizedqueueofnodesinthenetwork,thisprogramgreatlyreducesboththedelayofasinglenodeandtheaveragedelayacrossthenetwork,thusasignificantlyimprovedoverallnetworkperformance. wirelessnetworks;queuingdelay;priority;pre-setting;QoS 2015- 12- 17 国家自然科学基金资助项目(61170277；61472256)；上海市教委科研创新重点基金资助项目(12zz137)；上海市一流学科建设基金资助项目(S1201YLXK)。 卢浩洋(1991-)，男，硕士研究生。研究方向：计算机网络等。陈世平(1964-)，男，教授，博士生导师。研究方向：计算机网络等。王迅登(1990-)，男，硕士研究生。研究方向：计算机网络等。 10.16180/j.cnki.issn1007-7820.2016.09.012 TN929 A 1007-7820(2016)09-041-04
3 仿真实验
4 结束语
