基于负载分类的交换式以太网的实时性研究

董海勇，林 奕

（西北工业大学 计算机学院，陕西 西安 710129）

交换式以太网因结构简单，管理方便，可扩展性强，已在商业应用中获得了成功。但负载延迟的不确定性致使交换式以太网不适合直接应用在强实时通信领域。根据对实时要求的不同，通信数据主要分为周期性实时数据、突发性实时数据、有一定实时要求的受控类负载数据和不需要提供实时保障的数据。

目前，新兴的网络演算作为一门能够解决当前网络复杂问题的理论，因其可以方便地计算网络节点之间的延迟和积压上限，逐渐发展成网络通信实时性能分析的最有效的理论工具。GEORGES[1]应用网络演算研究了交换式以太网的时延上限，但没有区分数据类型。F.FRANCES、和张奇智[2]等应用网络演算理论计算了交换式以太网中周期性实时数据、突发性实时数据的实时性，但没有研究受控类负载的实时性。RIDOUARD[3]讨论了在 FIFO（First In First Out，先进先出）和SPQ（Static Priority Queueing，静态优先级队列）两种调度机制下周期性实时数据的延迟上限。

文中应用网络演算理论分析周期性和突发性实时数据的时延上限，并针对如何提高受控类负载实时性的问题进行研究。

1 相关模型及概念

1.1 网络演算基本理论

R.L.Cruz在文献[4-5]在分析不同网络拓扑结构下数据延迟的方法时，定义了固定时延线、接收缓冲区、多路复用器、解多路复用器、（σ，ρ）整形器和先到先出队列等6个基本网络服务元素。随后，C.S.Chang[6]，J.Y.Boudec等人基于最小加代数的数学解释为网络模型提出了网络演算理论。

应用基于极小加代数的网络演算，需要掌握其基本定义[8]。

定义 1（广义增函数）定理广义增函数是指当 s≤t，f（s）≤f（t）时的函数。另记F为在t＜0是取值为0的广义增函数的集合，F0为在t≤0时取值为0的广义增函数的集合。

定义 2（极小卷积）设 f，g∈F，则 f，g 的极小卷积定义为（f⊙g）（t）=inf{f（t-s）+g（s）|0≤s≤t}，且当 t＜0 时，（ f⊙g）（t）=0。

定义3（到达曲线）设广义增函数A，α∈F，如果对于所有s≤t满足 A（t）-A（s）≤α（t-s），则称 A 是被 α 限制的，α 被称为A的到达曲线。

定义4（服务曲线）当网络元素S的输入和输出累积函数分别为A（t）和D（t）时，称服务曲线为β当且仅当β是广义增函数，β（0）=0 且 D＞A⊙β。

1.2 多路复用器中的排队延迟

本节分析输入流编号为i在先进先出多路复用器（FIFO MUX）和静态优先级队列多路复用器（SPQMUX）的时延上限。

1.2.1 先进先出多路复用器

先进先出多路复用器（FIFO MUX）由于不考虑数据流的优先级，所以只有一个输出缓冲区。如图1所示，FIFOMUX将输入流的数据帧按照它们到达的次序传输到输出链路，其中B（t）表示MUX在时刻t的缓冲区积压。

图1 仅有一个缓冲的FIFOMUXFig.1 FIFOMUX with one buffer

当Cout足够大时，任意时刻的积压B（t）至多就是一个在转发的帧。则对于单个帧即可传输完成的长度为L的负载的时延上限为 Dqs=（Lmax+L）/Cout。

对于需要分割成多个帧才能完成传输的负载，若平均长度为Lavg，共被分割成m个数据帧，则该负载的时延上限为Dqm=（m*Lavg+L）/Cout。

当Cout不够大时，任意时刻的积压B（t）就可能不止一个帧。则对于单个帧可传输完成的长度为L的负载的时延上限为 Dqs=（B（t）+L）/Cout。

需要分割成多个帧才能完成传输任务的负载进入缓冲区需要的时间为 Tin=（m*Lavg）/Ci。 在T in的时间内，其他数据链路也可以发送数据到缓冲区，则此时间内共可进入的一些数据，再加上之前的积压B（t），一起以Cout的速率传输出去，则此负载的时延上限为Dqm。

1.2.2 静态优先级队列多路复用器

静态优先级队列多路复用器（SPQ MUX）由于考虑数据流的优先级，所以对应每个优先级提供一个输出缓冲区。如图2所示，SPQMUX将输入流的数据帧按照它们的优先级依次传输到输出链路，对于优先级相同的数据帧，则按它们到达的次序传输到输出链路，其中Bi（t）表示MUX在时刻t的第i个缓冲区的积压。

图2 附有多个缓冲的SPQMUXFig.2 SPQMUX withmany buffers

当Cout足够大时时，负载的延迟上限与FIFOMUX相同。

对于需要分割成多个数据帧才能完成传输任务的负载的时延上限为Dqm。

当输入流过大时，则无法得到该负载的时延上限，尽管时延上限是最悲观的理论分析值。这也符合基于优先级调度的实际情况，即只要高优先级任务一直没有完成，则低优先级的任务便得不到调度。

2 网络模型

2.1 模型设计

为了研究交换式以太网的实时性，本文所建模型是一个基于交换式以太网的两级树形拓扑结构的网络系统，如图3，其中SW表示交换机，SLV代表数据源端；MST代表中央控制器。图中的1个一级交换机连接着6个二级交换机，每个二级交换机又连着10个数据终端。即数据终端的个数为60。存储转发速率均设为常见的C=100 Mb/s，每个设备的连接线长度设为200m，电信号在电缆中的传输速率设为2*108m/s。

图3 两级树形拓扑的网络模型Fig.3 Networkmodelwith two-level tree topological

每个数据终端发送数据的模式相同，即都发送周期性实时数据、突发性实时数据、受控类负载和其他负载。定义周期性实时数据的优先级为最高的7，突发性实时数据的优先级为次高的6，受控类负载优先级被定义为1到4，其他数据优先级为0。

设每个数据终端10ms发送一个最小以太网帧用以传输周期性数据；同时使用漏桶整形器对突发性实时数据进行整流，使其平均每100 ms发送一个突发性实时数据帧，为了提高突发性实时数据的实时性，允许其连续发送10个突发性实时数据帧，帧的大小同样采取最小以太网的帧格式。

对于受控类负载，设数据终端发出的数据大小分别为1 KB，10 KB，100 KB和1MB 4种。同时假设数据终端在发送完成一个受控类负载的之前，不会发送新的受控类负载，即规定数据终端发送出去的聚合流仅能包含一个受控类负载微数据流。

对于优先级最低的其他负载，则是不受任何限制的随机发送，但系统不为该类负载提供任何实时性保证。

2.2 时延分析

应用文献[3]可知周期性实时数据和突发性实时数据的延迟上限分别为0.700 430 987ms和5.311 312 44ms。

在不对受控类负载进行分类的情况下，只能采取FIFO调度机制，该机制可以保证每个受控类负载不会无限期的等待。数据终端i发出的受控类负载Pa在该系统的延迟上限为DΣ。

发送一个类型为Pa的受控类负载，加上该负载在传输的间隙等，需要传输Pb的数据量。

表1 受控类负载传输信息表Tab.1 Information of controlled data

负载分类策略通过为较小负载分配较高优先级，为较大负载分配较低优先级，并采用SPQ的调度机制进行缓冲区管理，以降低较高优先级受控类负载的时延上限。采用SPQ的调度机制，设每个数据终端i发送优先级是p的受控类负载的速率上限为 Ci-p，在时刻t的速率为Ri-p（t），在交换机中的积压为 Bi-p（t），p的取值范围是 1～4。 数据终端i发出的受控类负载Pa在该系统的延迟上限为DΣ。

对比两种机制所得到的时延上限，根据系统为受控类负载提供有效带宽的大小，得到如下两点：

1）Band充分大的情况下，两种时延上限相同；

2）Band不是充分大时，采用FIFO调度机制可以得到一个非常大的时延上限，但不会出现任务的无限等待；采用负载分类策略则可以使优先级较高的任务得到快速的转发，但可能会导致低优先级的任务无限期的等待。

2.3 模型仿真

为了验证理论分析的结果，本节应用VS2010设计并实现了该模型的仿真系统，该仿真系统是一个时间触发的离散事件动态系统。同时规定各种受控类负载发送的概率相同。

2.4 结果比较

仿真程序在不同的调度策略，不同的负载情况分别运行1 000 s。当一级交换机平均负载为30%时，各类受控类负载在使用负载分类策略前后的统计结果做箱图如图4。

仿真结果表明，无论在何种负载的情况下，FIFO调度机制会给所有受控类负载以公平的调度方式，延迟差异不大；而采用分类负载策略可以明显地降低了较高优先级的传输时延，而低优先级的时延较FIFO虽有提高，但提高比例不大。然而，随着平均负载的不断提高，多个1MB的负载同时出现在一个交换机中的频次增加，导致了最大延迟的急剧增加。

图4 受控类负载时延箱型统计图Fig.4 Box plot of controlled loads delay

应用负载分类策略，对受控类负载采用SPQ调度机制，给较小的负载以较高优先级，给较大的负载以较低的优先级，理论分析和实验共同表明：该策略可以有效的降低高优先级的传输时延，同时对低优先级数据延迟影响较小。

3 结 论

文中应用网络演算分析了交换式以太网中周期性和突发性实时数据时延上限，以满足强实时通信领域应用要求。针对原有对受控类负载调度管理算法的不足，提出了对受控类负载进行负载分类并赋予不同优先级的策略。通过实验仿真，表明该策略可以大幅度降低受控类负载的时延，进而提高了受控类负载的实时性。

[1]Georges J P，Rondeau E，Divoux T.Evaluation of switched ethernet in an industrial context by using the network calculus[C]//Factory Communication Systems，2002.4th IEEE InternationalWorkshop on.IEEE，2002:19-26.

[2]张奇智，张彬，张卫东，等.基于网络演算计算交换式工业以太网中的最大时延[J].控制与决策，2005，20（1）:117-120.ZHANG Qi-zhi，ZHANG Bin，ZHANG Wei-dong，et al.Calculation of maximum delay in switched industrial Ethernet based on network calculus[J].Controland Decision，2005，20（1）:117-120.

[3]Ridouard F，Scharbarg J L，Fraboul C.Probabilistic upper bounds for heterogeneous flows using a static priority queueing on an AFDX network[C]//Emerging Technologies and Factory Automation， 2008.ETFA 2008.IEEE International Conference on.IEEE，2008:1220-1227.

[4]Cruz R.L..A calculus for network delay.I.Network elements in isolation[J].Information Theory， IEEE Transactions on，1991，37（1）:114-131.

[5]Cruz R.L..A calculus of delay Part II:Network analysis[J].IEEE Trans.Inform.Theory，1991，37（1）:132-141.

[6]Chang C S.On deterministic traffic regulation and service guarantees:a systematic approach by filtering[J].Information Theory， IEEE Transactions on，1998，44（3）:1097-1110.