城域以太网中基于抖动检测的拥塞控制算法.doc

第1期郝俊瑞等：城域以太网中基于抖动检测的拥塞控制算法127城域以太网中基于抖动检测的拥塞控制算法郝俊瑞1, 余少华1,2（1. 华中科技大学 计算机科学与技术学院，湖北 武汉430074；2. 武汉邮电科学研究院，新一代光纤通信技术和网络国家重点实验室, 湖北 武汉430074）摘 要：提出了一种在城域以太网节点设备中基于抖动检测的拥塞控制算法（JDCC算法）。通过检测和丢弃那些时延抖动值超过用户容忍门限值的数据分组，给正常的数据分组提供了更高的带宽，提高了实时多媒体流在城域以太网中传输的服务质量。实验结果表明JDCC算法可以更有效地降低实时多媒体流的平均时延抖动，且能提高有效吞吐量。关键词：延迟抖动；拥塞控制；城域以太网中图分类号：TP393.11 文献标识码：A 文章编号：1000-436X(2009)01-0121-07Congestion control algorithm based on jitter detection in metro Ethernet networksHAO Jun-rui1, YU Shao-hua1, 2（1.College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;2. Wuhan Research Institute of Posts & Telecommunications, State Key Laboratory of New Optical Communication Technologies and Networks, Wuhan 430074, China）Abstract: A novel congestion control algorithm (JDCC) for multimedia traffics was proposed. JDCC improves the QoS of multimedia stream in metro Ethernet network by detecting and discarding packets that accumulated enough jitter so as to maintain a high bandwidth for packets that stay within the multimedia streams jitter tolerance. Simulation results have shown that the proposed scheme can effectively lower the average received packet jitter than that using traditional congestion control algorithm RED and DropTail. Moreover, the proposed scheme can improve the useful goodput of the received packets when compared to RED and DropTail.Key words: delay jitter; congestion control; metro Ethernet network1 引言收稿日期：2008-03-03；修回日期：2008-07-15基金项目：国家高技术研究发展计划（“863”计划）基金资助项目（2005AA121410）Foundation Item: The National High Technology Research and Development Program of China (863 Program)(2005AA121410)随着IPTV、视频监控、Triple play等新业务的广泛应用，实时视频业务成为当前城域网上增长最快的应用之一。在当前的城域网领域，以太网已成为应用非常广泛的解决方案之一。如何在城域以太网节点设备中更好地承载实时视频分组业务是当前城域以太网急需解决的问题之一。当实时多媒体数据在分组交换网络节点上传送时，一般假定数据分组之间维持着一个恒定的延迟关系，但事实上这一假定是很难实现的。在实际的传输过程中，由于数据业务的突发性，拥塞的发生或者传输延迟的不同造成数据分组在到达目的地时产生了网络延迟的变化，也就是产生了时延抖动，造成这些实时视频数据流的服务质量降低。当实时多媒体数据流穿越网络各节点时，如果产生的时延抖动过大，即使收到这些数据流，对用户来说也没有实际意义。这是因为在用户端很难对一个数据流或多个数据流之间的数据分组再进行时序之间的调整。在一些多媒体系统中1,2，在客户端分配了一个缓冲区来解决该问题。然而，这样的缓冲区仅仅是增加了网络对于时延抖动的容忍，并没有从实质上解决该问题。如果有大量的实时多媒体数据分组在网络传输过程中累计的时延抖动超过了客户的容忍程度，那么这种情况将变得更加糟糕。这种情况下，虽然这些实时多媒体数据对用户来说已经不可用，但是他们仍然占用着网络的带宽，而传输这些无用的数据无疑增加了网络的拥塞程度。这种新的拥塞问题不可能通过传统的队列管理算法，比如随机早期检测（RED）3或者丢尾算法（DropTail）3来解决。本文提出一种在城域以太网中针对实时多媒体业务的拥塞控制算法，称为基于抖动检测的拥塞控制算法。该算法的目的是为了提高像实时视频和音频等多媒体业务在城域以太网节点设备中传输时的服务质量。该算法通过检测实时多媒体数据分组的时延抖动，丢弃那些抖动范围已经超过用户容忍门限范围的分组，这样不仅降低了发生拥塞的可能，节约了带宽，而且还提高了多媒体数据流的服务质量。本文的组织结构如下：第2节介绍了传统的拥塞控制算法和城域以太网中的Q-in-Q技术；在第3节介绍本文提出的基于抖动检测的拥塞控制算法的主要思想和设计过程，并且详细描述算法的工作过程；在第4节，从理论上分析了JDCC（基于抖动检测的拥塞控制）算法的性能和丢弃概率上限；第5节是本文的结束语。2 相关工作2.1 传统的拥塞控制算法传统拥塞控制算法的主要代表是随机早期检测（RED）和丢尾算法（DropTail）3。RED是IETF提出的一种主动队列管理机制。RED的有效性经过了一些实践的验证，但依旧存在一些不足。为了改进和完善RED算法存在的不足和缺陷还产生了大量RED的其他改进算法413。另外还出现了BLUE14、LARED15、REM16、PI17、Adaptive PI18、AVQ19、PIP20等算法。BLUE的主要思想是通过链路空闲和缓冲溢出的状况来调整报文丢失概率。LARED算法自适应链路负载。REM利用网络流量优化理论中“价格”的概念来探测和控制网络的拥塞状态。PI中控制的是队列长度。Adaptive PI通过实时测量链路的报文丢失率获得当前的负载信息，然后动态设置算法中的有关参数。AVQ中控制的是队列的入口速率。文献21提出一种PID控制算法，但其参数整定方法相当复杂。LRED22算法把Loss Ratio 引入到RED的丢弃概率的计算中，但链路利用率考虑不够；VRC23算法对队列长度进行规范，获得了高的链路利用率，但其顽健性欠缺。AOPC24定期地测量分组丢失率，并基于二阶系统最优模型，及时调节比例控制参数，使系统能够在动态变化的网络环境中仍然保持稳定性合较好的响应性。2.2 Q-in-Q技术以太网技术向城域网延伸必然要面临许多棘手的问题，例如突破4 096个VLAN数的限制、透明LAN业务连接、服务质量保证等一系列问题。为了在城域以太网中突破4 096个VLAN的限制和实现透明LAN业务传输，IEEE 802在2005年定义了Q-in-Q的标准IEEE 802.1ad (provider bridge)25。Q-in-Q技术中，外层的VLAN标签称为S-VLAN，而内层的VLAN标签称为C-VLAN。IEEE 802.1ad的Q-in-Q以太网帧格式如图1所示。图1 带有Q-in-Q VLAN Tag的以太帧格式在城域以太网中进行数据帧的转发时，通常只考虑S-VLAN Tag中的优先级设置，而C-VLAN Tag通常不被改变，也不被访问。3 基于抖动检测的拥塞控制算法本文假定通过UDP来传送实时视频分组业务，并和TCP流一起共享网络带宽，同时把TCP流和UDP流分为不同的类（事实上，可以利用IPv4包头的协议字段进行区分）。实时视频分组业务流以恒定的速率发送，而TCP流则以不同的速率发送各种业务，比如FTP等。TCP流采用RED丢弃策略，而UDP流则在进入队列之前采用抖动检测算法。为了讨论简单，交换节点中的队列被假定为先进先出队列，而且假定实时视频分组大小为固定值。在实际网络环境中，实时视频数据流比如MPEG-2 VBR音频流也常常被分成固定大小的数据分组来适应网络环境，而且在多媒体数据流中，丢失某些数据是允许的，并不影响多媒体数据流的解码。基于抖动检测的拥塞控制（JDCC）算法的基本思想是在分组流传送过程中检测和跟踪其时延抖动，如果时延抖动超过了用户的容忍门限，就将该数据分组丢弃，从而减少带宽浪费。为了跟踪时延抖动，需要一个抖动计数器。本文利用Q-in-Q中不被使用的C-VLAN Tag的优先级字段来作为该以太网帧在传输过程中抖动值的计数器。对于多媒体数据流来说，那些抖动值较小的分组应该优先转发，所以对应较高的优先级，而对于那些抖动值已经很大的分组来说，可能对用户已经没有用，在发生拥塞时应该首先丢弃，所以抖动值和优先级之间的对应关系应该是较大的抖动值对应较低的优先级，而较低的抖动值对应较高的优先级。本文规定将抖动值3个比特位的最低位来表示抖动值的正负，0表示抖动正值，1表示抖动负值。根据用户可以容忍的门限将抖动值分为8个不同的等级，正值4个等级，负值4个等级。优先级中的高两位分别表示抖动正值或负值的4个等级，即从等级0到等级3，而最低位用来表示抖动值的正负。由于抖动值越高优先级越低。所以等级0对应的二进制比特为11，等级1对应的二进制比特为10，等级2对应的二进制比特为01，而等级3对应的二进制比特为00。比如：如果抖动值在正的等级0中，那么对应的优先级为：高两位为比特11，最低位为0，即对应的优先级为6。如果抖动值为负的等级0中，那么队应的优先级为7。而如果抖动值较高，落在等级3中，那么对应的优先级为00或者01。从上面的分析可以看出，优先级的值正好为抖动值等级的取反运算。具体的对应关系如图2所示。图2 C-VLAN Tag 优先级与抖动值之间的对应关系如果用户数据在进入运营商网络之前，用户数据的C-VLAN Tag中本身就带了优先级，那么可以将用户C-VLAN Tag中的优先级映射到S-VLAN Tag中。这样C-VLAN Tag中的优先级就可以用来标识抖动域值的等级。如果进入运营商网络之前的用户数据的C-VLAN Tag中没有带优先级，那么采用上述的方法进行优先级的分配。具体的算法实现如图3所示。图3 JDCC算法的实现图3中描述了JDCC算法的伪代码，变量D是以太网数据帧在交换机中经历的时延，B代表输出队列的当前buffer占有率，P代表包长的大小，L表示可用的链路带宽，时延可以通过式（1）来估计D = BP/L(1)数据帧在交换机中经历的平均时延通过每个数据帧时延的指数加权平均来计算，其中Da表示平均时延，如式（2）所示 Da = Da (1 Wd) +DWd(2)通过指数加权平均，短期平均时延的增加可以被有效地平滑掉。以太网数据帧在交换机中经历的本地抖动值Jl则通过式（3）给出Jl = D Da (3)以太网数据帧从源到当前节点经历的总的抖动值Jt是本地的抖动值加上以太网数据帧中携带的C-VLAN Tag中的优先级对应的抖动计数器的值。如果Jt超过了用户的容忍阈值Tu，即Jt Tu/2 or Jt Tu/2(4)则该以太网帧就被丢弃。如果Jt在用户容忍阈值之内，那么则更新抖动计数器，并按照图3中的对应关系将抖动计数器的值转换为C-VLAN Tag中对应的优先级。4 性能界限和丢弃决定分析JDCC算法的性能可以通过测量收到的数据分组的时延抖动值来得到，采用抽样平均时延，使用有限数量的采样分组Ns。通过使用Chebyshev不等式，可以得出丢弃分组的概率上限P(drop)。假定收到分组Di的时延之间是相互独立的，以标准差同分布26。抽样平均时延为(5)Chebyshev不等式可以得到一个松散的上限和丢弃分组的概率P(drop)，也可收到分组的时延Di和平均时延，采用数量Ns和丢弃门限之间的关系。丢弃门限Tu定义为Tu = 2jJmax (6)其中，Jmax是允许的最大时延抖动，j(0,1)。则丢弃概率P(drop)为(7)根据Chebyshev不等式可得(8)式（7）可以写为(9)由式（8）可得，给定用户最大容忍阈值或最大时延抖动值可以得到丢弃概率的上限，从式（8）可以看出，丢弃门限值越高，丢弃概率则越小。同时，式(8)还给出了丢弃概率的性能上限。5 算法复杂度分析在该算法中，主要的计算过程是对每个数据帧计算延迟、平均延迟和时延抖动参数。每次首先根据缓冲的长度计算出数据帧的延迟，这个过程主要是一次乘法和一次除法，算法复杂度为O(1)；然后通过指数加权平均来计算平均延迟，平均延迟的计算过程是两次乘法和一次加法算法复杂度为O(1)；分组的抖动计算是一次减法运算；最后的丢弃决策过程主要是一次判决和移位运算，算法复杂度也是O(1)。由此可以看出，在整个算法过程中，只进行若干次加法、乘法以及移位运算，所以整个算法的运算复杂度为O(1)。因此不会影响分组在交换中的线性转发。算法中假定用UDP来代表视频流，用TCP来代表其他的流，在当前的交换机中，对于这种分类是很容易实现的，而且不会影响分组在交换中的线性转发。6 实验结果与分析本文采用NS2来进行算法的仿真实验，图4给出了仿真实验的拓扑图。在拓扑图中主机通过用户接入交换机（图4中的Customer switch）上连到运营商网络中。从用户主机发出的数据流是不带VLAN Tag的，当数据流进入用户交换机后，在用户交换机上和用户主机相连的端口上会为数据流打上C-VLAN Tag，在这里根据端口来分配C-VLAN。实验中用户主机A1A4的VLAN ID为100400，但不带优先级。在用户交换机的上联端口上配置为VLAN TRUNK模式。这样从用户上联端口出来的数据流就带有C-VLAN Tag了。在进入SP 交换机后，SP交换机按照端口来为数据流分配S-VLAN Tag，用户数据流在进入SP网络之后就变成了Q-in-Q模式。实验中，2个用户交换机相连的SP交换机上的端口的SP VLAN 分别为1 000和2 000。由于本文的JDCC算法是在SP网络中运行的，所以仿真实验涉及的主要是运营商网络部分，即图4中的SP Network部分。图4 仿真实验拓扑每个用户交换机连接的2个用户主机上分别发送TCP（采用FTP的流）和UDP（多媒体的流，比如MPEG-2的视频，比特率为6Mbit/s）的数据流。设定用户交换机到SP交换机的链路容量为10Mbit/s，传输延迟为3ms。MPEG-2视频流的样本采用VBR格式。为了实验的简单在下面的讨论中采用UDP流来代表视频流。在实验中数据帧将穿过一个有3个SP交换节点的链路，然后到达另一端的用户端交换机。SP交换机之间的节点彼此之间通过10Mbit/s的带宽链路互联，它们之间的传播延迟为2ms。这3个SP交换机之间的链路是整个链路上的瓶颈。拥塞控制算法在SP交换节点上实现，分别使用不同的算法（RED、DropTail、BLUE、JDCC）来进行拥塞控制，并给出了实验结果。在实验中设定每个节点上队列中数据帧的限制为150个；实验中测试256byte，512byte，1024byte 3种帧长，测试时间为10s。每个UDP和TCP的流的速率设定为6Mbit/s。JDCC算法的门限设置为0.1s，权重Wd设置为0.02；RED算法中的参数设置为最大门限100个帧，最小为30个帧。在实验中主要从TCP的友好性、时延抖动和多媒体流的有效吞吐量3个方面比较分析了JDCC算法和传统拥塞控制算法RED、DropTail的性能。6.1 TCP流的友好性UDP是一种无连接协议，它没有相应的流量控制机制，不会对丢包做出相应处理。当UDP流和TCP流共享带宽时，UDP流的这种特性会贪婪地占用大量的带宽，从而降低TCP流的吞吐量。因此，本文提出的JDCC算法有确定的TCP友好性是很重要的，它不应该降低TCP流的吞吐量，要能达到和传统的RED、DropTail算法以及BLUE算法相同的友好性。图5中的实验结果给出了TCP流在不同数据帧大小，不同队列管理策略的情况下的平均吞吐量。从实验结果可以看出，相比于传统的拥塞控制算法，JDCC算法能达到和RED、DropTail近似水平的TCP吞吐量。而图6中给出了UDP流在不同数据帧大小的情况下的吞吐量，采用的是和图5中相同的实验。采用JDCC算法UDP的平均吞吐量随着数据帧的增加而减小，同时它是小于DropTail算法和RED算法的。这是因为有些UDP分组积累了大量的时延抖动而被丢弃。算法的TCP友好性是直接与UDP吞吐量和TCP吞吐量的比例相关的。图7给出了在不同帧长下的UDP和TCP 图5 TCP流在不同帧长情况下的吞吐量图6 UDP流在不同帧长情况下的吞吐量图7 在不同帧长情况下的UDP和TCP吞吐量的比例吞吐量之间的比例。从实验中可以看出，JDCC算法和其他成熟的拥塞控制算法相比在TCP友好性方面是相接近的。6.2 时延抖动比较时延抖动对于多媒体业务是非常重要的一个参数指标，保证较小的时延抖动是提高多媒体业务服务质量的一个重要手段。多媒体数据流用RED算法时的时延抖动的定义如下：Ji |DDa|。并且在计算RED、DropTail以及BLUE算法的时延抖动值时，不计算被用户丢弃的包的时延值。图8图10分别给出了4种算法在不同帧长情况下的时延抖动的平均值的比较。从图中可以看出，BLUE算法的时延抖动值要低于RED和DropTail算法，而JDCC图8 平均时延抖动比较（帧长为128字节）图9 平均时延抖动比较（帧长为512字节）图10 平均时延抖动比较（帧长为1024字节）算法在各种帧长的情况下，平均时延抖动值都要明显低于传统的RED、DropTail和BLUE算法。从图中还可以看出4种算法包括DropTail、RED和JDCC算法都有相同的曲线趋势，这种周期性的趋势主要是因为TCP协议本身的流量控制机制所导致的。图中的实验结果表明本文提出的JDCC算法相比于BLUE、DropTail和RED算法可以达到更低的时延抖动。6.3 有效吞吐量的比较多媒体的UDP流对于时延抖动是很敏感的。当分组的时延抖动比用户的容忍阈值大的情况下，分组即使被成功地传送到客户端，实际上对于用户来说已经没有意义。如果没有足够的带宽那么将可能增加发生拥塞的可能，在交换节点上转发这些时延抖动较大的分组将减少传输信道的可用带宽。而且会导致其他的一些数据帧增加时延抖动，致使有更多的数据帧对用户来说也是没有意义的数据。所以在JDCC算法中将超过用户容忍阈值的数据帧丢弃。实际上在数据的传输过程中，对用户来说关心的是对其有用的输出而不单是吞吐量。这里的“有效”意味着多媒体数据帧到达客户端时满足抖动容忍，也就是到达用户端的数据帧要满足jitterTu。“有效”的多媒体数据帧能满足在播放给用户之前到达它的位置。用户容忍阈值在实验中设置在0.030.1s的范围内，给出了用户处的有效吞吐量的比较图以及在第一个交换节点的有效吞吐量的比较图，实验结果如图11和图12所示。由于拥塞实际上是在第一个节点发生的，所以第一个节点的有效吞吐量和用户处的有效吞吐量相差无几，只是JDCC算法在最后一个节点的有效吞吐量略高于第一个节点。实验结果表明BLUE算法的有效吞图11 用户处有效吞吐量的比较（帧长为1024字节）图12 第一个交换节点中的有效吞吐量的比较（帧长为1024字节）吐量略好于RED和DropTail算法，而JDCC算法的有效吞吐量要高于BLUE算法以及RED和DropTail算法。整个的趋势在图11中是可以很清楚地看到的，这说明实验结果和理论分析是一致的。7 结束语本文提出了一种在城域以太网中基于时延抖动的拥塞控制算法（JDCC算法）。JDCC算法检测多媒体数据流在网络节点经历的时延抖动，并利用城域以太网中的Q-in-Q的C-VLAN Tag来作为节点时延抖动的计数器。JDCC算法通过丢弃那些超过用户容忍阈值的数据帧来提高多媒体业务的服务质量。实验结果表明，JDCC算法与RED和DropTail的传统拥塞控制算法相比不但可以保持TCP的友好性，而且可以更有效地降低多媒体流的平均时延抖动，并能提高多媒体业务的有效吞吐量。参考文献：1CHAN S P, KOK C W. Protocol and buffer design for multimedia-on-demand systemA. Proc of IEEE Pacific Rim Conference on MultimediaC. London:Springer-Verlag, 2001. 10101015.2CHAN S P, KOK C W. Bitrate adaptation flow control for multimedia-on-demandA. Proc of IEEE International Conference on CommunicationsC. 2002. 2503-2507.3FLOYD S, JACOBSON V. Random early detection gateways for congestion avoidanceJ. IEEE/ACM Transaction on Networking, 1993,1(4):397413.4FLOYD S. A report on some recent developments in TCP congestion controlJ. IEEE Communication Magazine, 2001,39(4):84-90.5CNODDER S D, ELLOUMI O, PAUWELS K. RED behavior with different packet sizesA. Proc of 5th IEEE Symposiums Computers CommunicationsC. Antibes-Juan les Pins, 2000. 793-799.6PIPPAS J B, VENIERIS I S. A RED variation for delay controlA. Proc of ICCC. New Orleans, 2000. 475-479.7FLOYD S, MAHAJAN R. Controlling High-Bandwidth Flows at the Congested RouterR. Technical Report of ACIRI, 2000.8Cisco system. Distributed weighted random early detectionEB/OL. , 2003.9OTT T J, LAKSHMAN T V, WONG L H. SRED: stabilized REDA. Proc of IEEE INFORCOM99C. New York, 1999. 1346-1355.10FENG W, KANDLUR D, SAHA D, et al. A self-configuring RED gatewayA. Proc of IEEE INFOCOM99C. New York, 1999. 1320-1328.11FLOYD S, GUMMADI R, SHENKER S. Adaptive RED: an algorithm for increasing the robustness of REDs active queue managementEB/OL. /. 2003.12LIN D, MORRIS R. Dynamics of random early detectionA. Proc of the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer CommunicationsC. New York, 1997. 127-138.13ANJUM F, TASSIULAS L. Balanced-RED: an algorithm to achieve fairness in InternetA. Proc of IEEE INFOCOM99C. New York, 1999.14FENG W C, SHIN K G, KANDLUR D, et al. The BLUE active