面向MPEG-4 流的交换机调度算法

徐永华，陈清华

(1.金陵科技学院 信息技术学院，江苏 南京211169;2.江苏省信息分析工程实验室，江苏 南京211169;3.南京理工大学 计算机科学与技术学院，江苏 南京210094)

0 引 言

近年来，流媒体传输在网络传输领域中占据了越来越重要的地位，如何根据流媒体的性质或改进交换机的调度策略［1-2］是提高网络服务质量的有效途径。目 前，VOQ［3］交 换 机 使 用 的 调 度 算 法 有PIM［4］(Parallel Iterative Matching)、RRM［5］(Round-Robin Matching)和iSLIP 算法［6-7］，其中，iSLIP 算法因为其实现简单和并行性得到了广泛的应用，但为保证网络的服务质量(QOS)［8］同时也保证吞吐量。学者们提出了基于输入排队［9］的支持优先级机制的交换机调度算法，即Prioritized iSLIP(P-iSLIP)算法［10］，进行基于优先级的调度，这样才能使重要性高的分组得到更好的服务，但该算法是各个输入队列按照严格优先级来执行的，在实际的传输过程中将会导致普通数据队列的丢失及对增强层造成很大的延时和延时抖动，不能更好地满足网络的服务质量保证及网络吞吐量。

因此，本文提出改进支持严格优先级的交换机调度算法，采用动态优先级算法实现，其中设计了一个动态的线性优先级计算函数，该函数的输入参数是每个队列的优先级和在每一队列中待发送的数据包数，传输的优先级随之动态改变。该算法使交换机能够更好地支持MPEG-4 流的传输，提高MPEG-4 流传输的服务质量。

1 虚拟输出排队VOQ 的交换机逻辑结构

基于VOQ 的系统结构如图1 所示，它主要由输入端口、输出端口、交换结构和调度器［11-12］组成。假设输入和输出端口的数量都是N 且数据传输速率相同。输入端口采用VOQ，共有N ×N =N2个队列。分组在进入交换结构前已被分成定长信元，时间被分成等长的时间片。

图1 VOQ 交换机的系统结构

输入端i 的信元到达是一个离散的随机过程，用Ai(t)表示，1≤i≤N，表示在一个时间片t 内最多有一个信元到达一个输入端口。到达的信元根据目的端口存放相应地输入FIFO 队列Q(i，j)中，队列Q(i，j)的占用率用Li，j(t)表示。各队列的信元到达过程用Ai，j(t)表示，平均到达率为λi，j。到达过程的集合记为

2 基于VOQ 的输入排队匹配调度算法

2.1 基于严格优先级的iSLIP 算法

在MPEG-4 中将层次划分为基本层、增强层1 ～4，由此得出VOQ 队列为基本层、增强层分组和普通数据分组的6 组，各自的重要性不同，在支持L 个优先级的P-iSLIP 算法中，每一个输入端口对每个单独的优先权等级和输出都保持一个单独的FIFO 队列，在每个VOQ 中设置P 个子队列，P 个子队列表示为Ql(i，j)，其中i 表示输入端口;j 表示输出端口，l 表示优先级，则1≤i，j≤N，1≤l≤P，这样每个输入端口保持了FIFO 队列数为P ×N 个。该算法在每个信元时间内规定了严格的优先权。

Ql(i，j)只有在Qm( i，j )，l ＜m≤P 的所有队列被服务完成之后才能接受服务，算法在迭代收敛时或迭代次数达到n 次后停止。其中，迭代收敛是指在新一轮的迭代中没有匹配出任何新连接。每次迭代的3 个步骤分别为请求、授权、接受。

在P-iSLIP 算法中，各个优先级队列是按照严格优先级来执行的，即高优先级的队列中有分组的话，低优先级队列不会被发送，在实际的传输过程中将会导致:①普通数据队列丢失，当基本层和增强层待传输的数据量增加时，普通数据包的阻塞将加大，一旦普通数据包的队列达到满的情况下，就会丢失;②MPEG-4 增强层数据包丢失，因为将MPEG-4 流分成基本层和增强层时，由于MPEG-4 增强层是不能单独解码的，必须和其对应的基本层一起解码，如果在MPEG-4 基本层队列和增强层队列中依然采用严格优先级策略的话，对于MPEG-4 增强层将造成很大的延时和延时抖动，很可能当MPEG-4 增强层传送到解码器时，与其对应的基本层帧已经解码播出了。这样MPEG-4 增强层就错过其播发时间，导致的结果是虽然MPEG-4 增强层传输到了终端，但对于视频质量并没有帮助，相当于MPEG-4 增强层数据包丢失了。因此，在考虑尽量满足MPEG-4 基本层的传输下，适当考虑提高增强层和普通数据包的优先级，使得数据传输更加完整。因此，提出了在面向MPEG-4 流的匹配调度算法设计中，综合考虑实际发送数据队列的情况，改进面向MPEG-4流的调度算法，使之更加适合数据传输。

2.2 动态优先级的iSLIP(DP-iSLIP)算法

首先将数据队列分为3 组，如表1 所示。

表1 数据队列分组

因此，每个输入端口的每一个VOQ 设置6 个子队列，分别是MPEG-4 基本层队列、MPEG-4 增强层1 队列、MPEG-4 增强层2 队列、MPEG-4 增强层3 队列、MPEG-4 增强层4 队列和普通的Best Effort 队列。

基于严格的优先级考虑是对于每一组设置一个固定的优先级，不考虑系统的状态和队列中的数据多少。本文提出采用一种动态考虑优先级的办法，即在整个数据传输的过程中，优先级动态改变，设计一个动态的线性优先级计算函数F(i)，该函数的输入参数是每个队列的优先级和在每一队列中的待发送的数据包数，该函数定义为

式中:l(p)是对列p 的优先级，0≤l(p)≤1，本文实验仿真中定义为{0.7，0.4，0.2};r(p)是队列中的待发送的数据比，即待发送的数据包数/队列的长度;w(p)是一个权重因子，在此，定义为{0.6，0.7，0.8}。公式中体现出如果一个数据包具有较高的l(p)，同时队列中的数据也较多则具有较高的优先级，会被首先考虑发送。设置MPEG-4 的基本层队列的优先级l(p)最高，普通数据队列的l(p)最低，而r(p)的值取决于目前队列的状态和队列可利用的长度。如图3 所示，经过优先级函数计算后具有最高取值的队列优先被发送。但是，当一个队列中待发送的数据较多，即r(p)接近于1 时，首先考虑发送该队列中的数据，以免数据被丢失。然而，如果没有一个队列中待发送的数据处于占满队列的情况，l(i)是发送数据优先级的决定因素，也就是队列优先级较高的先被发送。如果f(p)＞1，则取整。

图3 动态优先级结构模型

因为该算法中要支持6 个优先级队列，所以，每个输出端口需要6 个授权指针gjp(j)，1≤j≤6;每个输入端口也需要6 个接受指针aip(i)，1≤i≤6。

改进后的算法同样分为3 个步骤:

(1) 请求。如果任意一个输入端口i 有分组需要发送，那么在输入端口i 的所有非空VOQ 中，每个VOQ 选出发送配额Ck不为0 的，且根据测算出具有最高优先级的分组，判断如果是增强层组，则固定优先级考虑轮转该组的所有队列，并为相应队列发送请求;否则不是增强层组，发送最高优先级的分组队列，在请求中包含该队列的优先级fij(p)信息。如果MPEG-4基本层组队列和增强层组中所有队列均为空，则发送普通队列的请求。

(2) 授权。输出端口j 接收到请求之后，它需要找到这些请求当中具有最高优先级的所有请求f(j)=max fij。然后输出端口就在满足优先级为f(j)的输入端口中选择一个输入端口。输出仲裁器需要对每一个优先级等级保持一个指针gjp。在所有具有最高优先级为f(j)的输入选择过程中，仲裁器使用指针gjp(j)并且选择使用与经典SLIP 算法相同的轮转方案。输出端口要告诉每个输入端口它的请求是否被授权了。当且仅当在第3 步中输入端口i 接受输出端口j 时，指针gjp(j)在授权的输入端口位置之后模N+1。

(3) 接受。假如输入端口i 接收到输出端口来的授权，输入端口i 将确定最高级别的授权，即确定f'(i)=max fij。输入端口在具有优先级为fij=f'(i)的输出端口中选择一个。输入仲裁器对每个优先级保持一个单独的指针aip。在所有具有最高优先级为f'(i)的输出端口中进行选择时，仲裁器就使用指针a'ip(i)按照经典SLIP 算法一样的轮转方案来进行选择。每个输入端口应该对每个输出端口的授权是否被接受做出指示。指针a'ip(i)在被接受的输出端口之后模N +1。输出端口i 在完成匹配后将该端口的VOQij中建立匹配的队列的发送配额Ck－1。

图4 给出了一个算法实例。图中为一个4 ×4 的交换结构。在图4(a)中，设VOQ11的基本层和增强层队列都不空，且Ck＞0，所以VOQ11的基本层队列发送请求，请求优先级为f1，即requset(f1);设VOQ12中，基本层队列不空，但基本层队列的Ck=0，无法发送请求，所以增强层发送请求requset(f2);而VOQ32中基本层和增强层都为空，则普通队列发送请求requset(f3)。由于输出端口1 收到的2 个请求的优先级相同，需要查看授权指针gjp(j)来确定授权哪个输入端口的请求，而gjp(j)所指的输入端口为1，所以输出端口1 授权输入端口1 的请求;输出端口2 收到的2 个请求优先级不同，授权优先级高的请求。在图4(b)中，可以看到授权的结果。如图4(c)所示，输入端口1 收到了2 个授权，但优先级不同，所以输入端口1 接受优先级高的授权，在接受之后，相应的授权和接受指针都进行更新，这样就完成了一次迭代。多重迭代执行算法的步骤(1)～(3)，每次迭代都在以前迭代建立匹配的基础上增加匹配的数目。如果在迭代过程中，当某一VOQ 的子队列中的MPEG-4 基本层和增强层队列的发送配额Ck=0，则将它们的发送配额Ck各自设为初始时的发送配额。通过上述的改进，使得MPEG-4 基本层和增强层有选择的发送，首先保证基本层分组的发送，同时也尽力发送增强层分组。

图4 算法实例

3 实验结果

该发生器的开发采用VC + + 6.0、Matlab 6.5 的开发环境，Windows XP 操作系统。仿真的交换结构采用8 ×8 的crossbar［13-14］交换结构，并且所有链路具有相同的信元传输速率，流量模型采用ON/OFF 模型［15-16］。设定输入端口速率为1 Gb/s，交换结构采用VOQ 存储组织方式，改进后的算法采用4 次迭代，信元长度为64 Byte，延迟时间的单位为时隙(slot)，即传输一个信元用的时间。

3.1 性能评价指标

(1) 包丢失率。设Npli表示第i 时间间隙丢失的包数;Npai表示第i 时间间隙到达的包数;t 为某个时间片，则包丢失率:

(2) 平均延迟。设Tpdi表示第i 时间间隙包的延迟时间;Tpai表示第i 时间间隙包的到达时间;t 为某个时间片，则平均延迟Ad:

3.2 发送配额对延迟的影响

由于在改进的算法中为MPEG-4 基本层队列和4个MPEG-4 增强子层队列分别设置了发送配额Ck。设MPEG-4 基本层队列、MPEG-4 增强层1 队列、MPEG-4 增强层2 队列、MPEG-4 增强层3 队列和MPEG-4 增强层4 队列的发送配额分别为C1，C2，…，C5，令rate = C1∶C2∶C3∶C4∶C5，则rate 值表示MPEG-4 基本层和4 个增强子层队列的发送比，假设rate=2 ∶1 ∶1 ∶1 ∶1，给出增强层的4 个队列同一个发送配额，而每发送2 个MPEG-4 基本层队列就发送1个MPEG-4 增强层组中每一个队列，其中增强层的队列是轮转发送。

如表2 所示，在80%的负载下，不同的流量和不同的rate 值，MPEG-4 基本层和MPEG-4 增强层1 队列、2 队列、3 队列和4 队列的平均延迟大小。rate 值从3 增大到10。

表2 配额对延迟的影响

从表2 中可以看出，基本层的延迟同比增强层的较少，说明首先保证基本层传输，此外，当rate 从3 增大到6 时，MPEG-4 基本层分组的延迟明显减小;rate从6 增大到10 时MPEG-4 基本层的延时略有减小，趋于稳定;rate 从3 增大到7 时，MPEG-4 增强层的延时缓慢增大;当rate 从7 ～10 时，MPEG-4 增强层分组平均延时增大较快。

通过上述分析，可以得到这样的结论:rate 值为7左右时，改进的算法能够获得较好的性能，既能使MPEG-4 基本层的分组平均延迟减少到最低，又能保证MPEG-4 增强层的分组平均延迟不至于过大。故本文将MPEG-4 基本层分组和MPEG-4 增强层分组的Ck值比例设为7 ∶1。

3.3 P-iSLIP 算法和DP-iSLIP 算法的分析比较

普通数据队列的延迟比较如图5 所示。由图可以看出，普通数据队列在负载为10% ～50%时，两种算法下的延迟基本一样，当负载大于50%时，动态优先级下的平均延迟较小，随着负载的加重，平均延迟变化比较平稳。

普通数据队列的包丢失率如图6 所示，由图可以看出，当负载大于50%时，随着负载的加重，两种算法下的包丢失率变化都比较快，其中P-iSLIP 算法下的包丢失率较大;动态优先级下的包丢失率较小。

增强层1 队列的延迟比较和丢包率如图7、8 所示。由图可以看出，与普通队列的基本相似，但是在60% ～70%和80% ～90%之间两种算法有很大的区别。

图5 普通数据队列的延迟

图6 普通数据队列的包丢失率

图7 增强层1 队列的延迟

图8 增强层1 队列的包丢失率

图9 基本层队列的延迟

图10 基本层队列的包丢失率

基本层队列的延迟和包丢失率比较如图9、10 所示。由图可以看出，基本层队列在负载为10% ～50%时，两种算法下的延迟基本一样，当负载大于50%时，动态优先级下的平均延迟较小，在负载为50% ～60%之间随着负载的加重，平均延迟变化较快，但是丢包率有着明显的改善，较为平稳。

纵观以上结果可以看出，动态优先级算法具有较低的平均延迟和包丢失率，对于MPEG-4 基本层队列、增强层1 队列以及普通数据队列具有很好的分类调度作用，当负载为90%时，MPEG-4 基本层队列的延迟为18 个时隙，增强层1 队列的延迟为340 个时隙，普通数据队列的延迟为2 400 个时隙;MPEG-4 基本层队列的包丢失率为0.019，增强层1 队列的包丢失率为0.21，普通数据队列的包丢失率为0.96，说明首先保证了基本层的通过，而且纵向比较各图，牺牲了较小的基本层的延迟和丢包率，换得了其他各层数据的延迟和丢包率的大幅度减少，即以较小的代价换得了更多的数据通过。综上所述，DP-iSLIP 算法在有限的空间下，尽量考虑了满足MPEG-4 基本层的传输下，适当考虑提高增强层和普通数据包的优先级，使得数据传输更加完整。

4 结 语

本文改进了面向MPEG-4 分级编码流的交换机调度算法，实验首先对算法中rate 参数取值进行了讨论，然后在普通数据队列、基本层队列、增强层1 数据队列中分别采用严格优先级的P-iSLIP 算法和DP-iSLIP 算法完成了不同负载情况下的延迟和丢包率比较。说明在有限的资源下，首先保证基本层数据队列的通过，其次是增强层1 队列，最后是普通数据队列，对于普通数据队列和增强层的队列都在原有的P-iSLIP 算法基础上有了较大的提高，当然是以牺牲了较少的基本层的数据传输为代价的。仿真结果表明，本文提出的面向MPEG-4 流的交换机调度算法能够保证MPEG-4 基本层的优先发送，保证其延时性能，保证其具有较少的丢包率，同时也能将考虑到MPEG-4 增强层和普通数据得到一定的服务，能够为MPEG-4 流的传输提供更好的质量保证。

［1］ 王 晖，沙基昌，孙 晓，等. MPEG-4FGS 视频流量模型的仿真应用研究［J］.计算机仿真，2006，23(12):

［2］ 刘国柱，王洪林.MPEG-4 实时视频传输的拥塞控制算法的改进［J］.微型机与应用，2010，18(5):39-44.

［3］ 徐晓飞，吴建民，龚 诚.VOQ 交换机的输出队列调度算法［J］.哈尔滨工业大学学报，2009，41(7):120-123.

［4］ McKeown N. Scheduling cells in an input-queued switch［J］.Electronics Letters，1993，29(25):2174-2175.

［5］ Anderson T E，Owicki S S，Saxe J B，et al. High speed switch scheduling for local area networks［J］. ACM Transactions on Computer Systems，1993，11(4):319-352.

［6］ Nick McKeown. The iSLIP scheduling algorithm for input-queued switches［J］. IEEE/ACM Transactions on Networking，1999，7(2):188-201.

［7］ 李 秋，戚宇林，杨 凯.输入排队iSLIP 算法的改进与比较［J］.华北电力大学学报(自然科学版)，2009，36(2):106-109.

［8］ Ch Bouras，Gkamas A. Multimedia transmission with adaptive QoS based on real-time protocols ［J］. International Journal of Communication Systems，2003，16(3):225-248.

［9］ 张重洋，申金媛，刘润杰，等.基于输入排队的高速交换调度算法研究［J］.智能系统学报，2008，3(3):265-269.

［10］ Nick McKeown. Scheduling algorithms for input-queued cell switches［D］.Berkeley:Univ California，1995.

［11］ 王俊芳，张思东.通用高速分组交换调度算法［J］.电子科技大学学报，2010，39(1):69-73.

［12］ 申 宁，李 俊，倪 宏. 一种优化指针策略的输入排队调度算法［J］.计算机系统应用，2010，19(12):94-99.

［13］ 马祥杰，兰巨龙，毛军鹏，等.输入排队Crossbar 架构下的流量模型［J］.电子学报，2009，37(1):170-174.

［14］ 高志江，曾华燊，夏 羽.基于CICQ 交换结构的低复杂度调度算法［J］.四川大学学报(工程科学版)，2011，43(5):163-167.

［15］ TAQQU M，LECY J. Dependence in probability and statistics:A survey of recent results［C］//Volume 11 of Progress in Probability and Statistics. Birkhauser，Boston，1986:73-89.

［16］ 饶云华，曹 阳，杨 艳，等. 基于Pareto 分布的IP 骨干节点输入通信量模型［J］.计算机科学，2006，33(3):27-28.