IP拥塞控制

IP拥塞控制（共6篇）

IP拥塞控制 篇1

摘要：由于卫星链路有着不同于地面有线环境和固定应用的一些特点,传统的TCP中使用的拥塞控制算法难以满足要求,因此本文提出了一种开环IP拥塞控制算法,让IP层参与网络的拥塞控制。并在原有IP交换模型的基础上,通过改变IP源和输入处理进程对星上IP拥塞控制进行OPNET仿真。计算机仿真结果表明,该算法可明显地降低星上IP交换的丢失率。

关键词：卫星链路,拥塞控制,RSVP协议,VOQ,资源管理

0 引言

卫星通信网络已经成为全球通信基础设施不可缺少的一部分。卫星链路有着不同于地面有线环境和固定应用的一些特点,如:通信时延长、链路误码率高、带宽资源少、链路连接的间断性等,因此传统的TCP中使用的拥塞控制算法难以满足要求,必须让IP层参与网络的拥塞控制。

拥塞控制算法[1]可分为在端系统上使用的源算法和在网络设备上使用的链路算法两种。源算法中使用最广泛的是TCP协议中的拥塞控制算法。链路算法的研究主要集中于“主动队列管理”AQM(active queue management)算法研究。TCP中使用的拥塞控制算法已经成为保证Internet稳定性的重要因素。

拥塞控制[2]的解决方案一般被分为两类:一类是开环,一类是闭环。闭环方案是通过反馈环路将拥塞信息从检测点传送到可采取行动的地方。星地链路时延大,出现拥塞时再进行反馈的方案不易实现。因此,本文采用开环方案,通过在交换分组之前对资源进行预留来避免拥塞,并将RSVP协议用于星上交换机的拥塞控制。

1 RSVP协议

作为IP网络中实现资源保留与控制的协议,RSVP提供了一套完整的信令机制,该机制可被用于在网络中为数据流建立一条具有足够带宽的单向通道,从而实现对数据流的可预测性传输。RSVP协议包含一个信令的呼叫建立过程。在此呼叫建立过程中,用户提出带宽和Qo S参数的请求。网络中的参与RSVP协议过程的路由器将对于自身是否有足够的资源做出回应。RSVP中从源到目的地所经过的每一台路由器都需要进行这样的处理。当一个中间节点不能满足相应的请求时,它便向接收方发送拒绝信息,拒绝此Qo S请求,中断信令的处理过程。如果网络和用户能够对提出和响应的Qo S参数达成一致,则呼叫被正式建立,为该流分配链路带宽和缓冲区空间,并且把相关的流状态信息装入路由器中;同时,网络中的路由器对呼叫状态信息进行维护。当源站开始向网络发用户数据包时,为了确保流量不超过其达成一致的Qo S流量参数,网络将对其进行监视,路由器查找对应的资源列表,判断它是否被预留了带宽[3]。

RSVP协议在封装时处于传输层的位置,但并不用来传输应用层的数据,类似于ICMP、IGMP及路由协议,也是一种Internet控制协议。对于不支持RSVP的路由器来说,该协议是透明的,即不支持RSVP的路由器可简单地将RSVP分组作尽力传送处理。RSVP共有7种报文:1)路径请求Path;2)预留请求Resv;3)路径错误Path Err;4)预留出错Resv Err;5)路径拆除Path Tear;6)预留清除Resv Tear;7)预留确认[4]。

2 星上IP交换的拥塞控制

星上拥塞控制的基本过程是:地面站点在发送IP数据之前,先向星上IP交换机发送路径请求消息,星上交换机根据星上交换机中缓存区的利用情况决定是否为该数据预留资源,然后为地面站点发送资源预留或拒绝消息,地面站点只有在收到星上交换机的资源预留消息后才能发送IP数据报文,否则等待并定期发送路径请求消息。

Internet上出现的接近40%的IP数据是40字节的不带数据的TCP回应报文。在进行拥塞控制时,如果对于地面站点待发送的每个IP报文都进行路径的请求,那么就会出现大量的路径请求及资源预留消息,对于短报文来说,传输效率较低,且时延更大。因此,本文在进行星上拥塞控制时,对40字节和44字节的短报文并不进行路径请求,由于短报文分组占近40%,采取该策略将减少大量的路径请求及预留消息。

2.1 星上拥塞控制的消息类型及格式

采用RSVP中的路径请求消息Path和预留请求消息Resv来完成,根据原有的消息格式重新设计。RSVP协议中的消息封装在IP数据报文中,通过IP头部中的协议域来指示该报文属于RSVP协议中的消息报文。如下表所示。

在表1通用头部中,Vers域指的是协议版本号;Flags域中是标志比特;Msg Type域指示的是消息类型,路径请求消息该域的值是1,预留请求消息中该域为2;Send_TTL是指发送该消息的IP报文的TTL值;在RSVP Length域中说明了以字节为单位的RSVP消息的总长,包括常见的头部及可变长的对象;另外通用头部中还有一个16比特的校验和域。

如表2所示,Path消息中,主要传送的信息有源、目的IP地址,待发送IP报文的标识号及IP报文的总长度等;Resv消息中除了待发送IP报文的一些信息如目的地址、标识号、报文总长度外,还要有是否接受该请求的标志位信息。

2.2 协议交互过程

采用RSVP协议进行资源预留来避免星上交换机缓存区的拥塞时,地面发送站点及星上交换机需要发送或接收不同的消息来进行资源的预留和数据的交换。对于消息的丢失或错误,地面发送站点和星上交换机都需要采用一定的措施来保证交换的正常进行。

图1是正常情况下,资源预留协议及传输数据的过程,地面的发送站点只有在收到星上IP交换机的接受资源预留请求消息后才能向星上发送IP报文。

图2是当地面发送站点向星上IP交换机发送的路径请求消息出错或丢失时,地面站点和星上交换机传输数据的情况。为减少星地之间的交互,在发送站点和星上交换机采取一定的超时重发策略。地面发送站点直到收到星上IP交换机发出的接收资源预留请求消息才能发送IP报文。

图3是当星上IP交换机发送给地面站点的资源预留消息出错或丢失时,地面站点和星上交换机传输数据的情况。

资源预留消息出错或丢失时也不发送出错消息。地面站点在发送路径请求消息时启动定时器,如果定时器时间到,并没有收到星上交换机的回复消息,或者收到了一个错误的消息,那么该地面站点重新发送路径请求消息,继续启动定时器等待直到收到接收资源预留请求消息。

如果星上交换机根据当前的缓存利用情况接受了地面发送站点的路径请求消息,但是该消息丢失或者出错,如图3(a)所示。星上交换机为该请求已经进行了资源预留,但由于消息丢失或出错,并没有数据到来如图3(b)所示。对于这种情况,星上交换机也有一个定时器,当时间到但还没有收到预约的数据,那么就释放为该数据预约的资源。

(a)接收资源预留请求消息出错或丢失(b)拒绝资源预留请求消息出错或丢失

2.3 星上IP交换机的资源管理

星上IP交换机采用基于输入缓存的Crossbar交换结构,为避免队头阻塞现象,采取了VOQ的技术[5]。在队列组织时,每个输入端口处的N个队列固定划分。之前的仿真结果说明了输入端口处VOQ对拥塞的影响要比输出重组时缓存大。针对这种结构的星上IP交换机进行拥塞设计时,需要分别管理每个VOQ的资源利用情况。

在本设计中,收到40和44字节的短报文时,如果资源够用则缓存该IP报文,并更新资源利用情况,否则丢弃。收到地面站点发送来的路径请求消息后,根据资源情况来判断是否为该IP报文预留资源。若资源够用,为该IP报文预留所需资源,同时进行定时。当定时器时间到,但该IP报文还没到达星上交换机时,释放该资源。当缓存的内部信元被交换至交换单元,则释放一个信元大小的资源空间。

当收到的报文大小与提前预约的不同时,需及时对缓存区中的资源利用情况进行更新。当收到的IP报文使用资源比提前预约的要大时,若目前资源够用,则允许缓存该报文,同时更新资源利用情况,但如果交换机出现拥塞时,最先丢弃该报文;若目前资源不够用,则直接丢弃该报文,释放原预留资源。当收到的IP报文使用资源比提前预约少时,缓存该报文,并更新资源利用情况。

3 仿真结果和分析

在原有IP交换模型的基础上,通过改变IP源和输入处理进程对星上IP拥塞控制进行OPNET仿真,验证本文提出的拥塞控制算法是否能降低星上交换机的丢失率,达到拥塞控制的目的。

由于这里的拥塞控制是针对Internet上的IP报文长度分布设计的,因此仿真中数据源产生IP报文的长度服从下面五种分布:40字节-34%,44字节-4%,280字节-42%,576字节-10%,1500字节-10%。仿真时间仍然设定为1.024s,也就是200000个信元时隙。

由于1500字节的报文需要拆分成25个信元,如果VOQ的容量小于25的话,那么所有的1500字节报文都无法得到预留。因此这里对VOQ容量在小于25(24),等于25,大于25(26)时分别进行仿真,比较在同样条件下采用拥塞控制和无拥塞控制的丢失率情况。

图4(a)是当VOQ为25时,两种情况下丢失率的比较。进行拥塞控制时,由于1500字节的报文需要拆分成25个信元,因此如果为1500字节的报文预留了资源,那么不发送预留消息的40和44字节短报文就会由于资源不足被丢弃。但经过拥塞控制后的丢失率明显小于不采用拥塞控制下的丢失率。

当VOQ为24时,两种情况下丢失率的比较如图4(b)所示。在这种情况下,由于VOQ的容量不足以保存一个1500字节的IP报文,那么所有1500字节报文的预留请求消息都会被拒绝,星上缓存足够存储短报文,因此在星上没有出现丢失,但1500字节的报文将无法被交换。因此,设置缓存大小时,VOQ队列应至少足以保存一个IP报文,否则对于长报文来说,将永远无法预留;从该图的仿真结果中也能看出如果不采用拥塞控制的话,IP交换机的丢失率很大,达到了10-1量级。

图4(c)是当VOQ为26时,采用拥塞控制和不采用拥塞控制时丢失率的比较。在这种情况下,即使星上交换机为最长的IP报文预留了资源,不发送预留消息的短报文到达时也有存储空间,这是因为短报文拆分为一个信元,只需占用VOQ中一个信元大小的空间,因此从仿真结果可看出,在这种情况下采用拥塞控制的丢失率为0,明显小于不采用拥塞控制时的丢失率。

4 结论

仿真结果表明,本文提出的算法可明显地降低星上交换机的丢失率。但这种算法地面需要缓存待发送的IP报文,并要定期向星上发送路径请求消息。

下一步,可考虑如何对多个IP报文同时发送资源预留消息、地面站为终端或者网关时不同的星上拥塞控制算法进行研究。

参考文献

[1]秦凯运,杨煜普,谢剑英,面向宽带IP网络的拥塞控制研究进展[J].通信学报,2004,Vol.25,No.11:119-126.

[2]Shin-ichi Kuribayashi;Kenichi Hatakeyama,Proposed con-gestion control method for all-IP networks including NGN[J],10th International Conference on Advanced Communication Technology,2008.(ICACT 2008):1082-1087.

[3]Karsten,M.Collected Experience From Implementing RSVP[J].IEEE/ACM Transactions on Networking,IEEE2006:767-778.

[4]J.Hillston,D.I.Laurenson,H.Wang,Evaluation of RSVP and Mobility-Aware RSVP Using Performance Evaluation Process Algebra[J].IEEE International Conference on Communications,2008.(ICC'08):192-197.

[5]Banovic,D.;Radusinov,I.VOQ Simulator-Software Tool for Performance Analysis of VOQ Switches[J].International Conference on Internet and Web Applications and Services/Advanced International Conference on Telecommunications,2005.

IP拥塞控制 篇2

随着计算机技术和网络技术的快速发展, 常规而又单一的Internet服务已经无法满足目前的需求, 尤其是现阶段发展快速的多媒体通信业务, 必须要求Internet可以保质保量地传输包括音频、 图片以及视频等多媒体信息, 也就是要求网络最基本上可以支持和达到服务质量需求 (QOS), 从而实现综合服务水平。 然而, 随着计算机网络的发展, 其规模和负荷也在不断增加, 计算机网络存在的拥塞现象越来越明显。 互联网所使用的主要数据流协议便是TCP/IP, 而对网络拥塞控制的分析和TCP/IP有着非常紧密的联系。

2 TCP/IP 计算机网络拥塞相关理论

2.1 计算机网络拥塞

拥塞是网络中发生网络链接失败, 或者是线路装置产生严重过负荷之后出现的正反馈现象, 导致接通率大 大降低 ,网络局部甚至会出现整体瘫痪的事故, 甚至会对网络的性能和服务质量产生一定程度的影响。 目前, 对当前Internet的主要体系而言, 拥塞现象的发生几乎成为必然的现象, 由于网络资源中的信息传播如果没有事先的协商和接纳, 当很多的IP分组当同一时刻到达了路由器 , 如果这些IP分组均希望通过某一端口进行转发的概率增大, 而对于路由器来说, 同时对这么多的分组进行处理, 并不是那么容易, 如果要想顺利处理, 需要对它们设置好处理的顺序。 如果缓存空间被消耗殆尽时, 则路由器只能选择丢弃分组。 在拥塞现象发生的情况下, 分组很容易丢失, 而且在端与端之间需要消耗更长的时间, 如果长时间发生拥塞现象还可能导致整个网络的瘫痪。如果网络处于拥塞崩溃状态时, 则微小的负载增量都会使得网络的有效吞吐量不断减少。 如果负载减小时, 则拥塞能够自行恢复。

2.2 TCP/IP 协议

TCP/IP协议是互 联网上使 用最为广 泛的协议 , 所以对TCP/IP的拥塞控制机制进行研究也比较多 。 实际上 , TCP/IP的拥塞控制包括两个部分: 分别是TCP (传输层) 的拥塞控制和PI (网络层) 的拥塞控 制 。 传输控制 协议/网际互连 协议TCP/IP并非一个协议 , 而是一系列的协议 , 它对如何利用国际互联网Internet传输交换进行定义。 根据权威的统计数据显示, TCP/IP协议是目前互联网Internet使用最主要的协议, 因此, 针对TCP/IP协议的拥塞控制机制的研究, 将对于拥塞控制的研究具有非常重要的作用。 甚至假如没有TCP/IP拥塞控制算法的引入, 今天Internet的成功就大打折扣。

3 网络拥塞的原因

网络拥塞是指网络用户使用的网络资源已经超出了网络的承载能力, 使得网络产生过载的现象。 对于互联网 来说 ,在通信子网中存在着很多的分组数量, 在这种情况下就会带来通信性能的降低, 也即是网络拥塞现象的产生。 如果网络对于通信子网的分组数量的传输一般处于一个标准的范围之内, 通信子网的分组数据就会被完整地发送到通信目 的地 。信息数据的发送和送达的数量处于一定的比例之下。 然而会在一些特殊情况下网络传输的数据量提升幅度较大, 导致路由器由于拥塞现象而出现瘫痪, 即分组的丢失, 甚至造成情况持续恶化, 网络传输数据信息量持续提升, 拥塞范围也随之扩张, 导致分组基本上无法送达到目的地。 出现网络拥塞现象主要包括3个原因。

3.1 存储空间限制

存储空间限制所谓是通过对网络信息数据的传输端口进行存储空间大小的设定来达到控制拥塞的目的。 在这种控制机制下, 如果发送到该端口的分组数据突然增多, 则会将超过空间限制的分组数据按照一定的顺序进行编排, 等待信息输出。 如果端口的数据转发速率远远小于数据包, 而且存储空间就会在不断延误的情况下逐渐被填满, 基于该种背景下,后续到达端口的包就会被路由丢弃。 尽管能够利用增加存储空间缓解输出端口的压力的方式, 然而伴随着存储空间的持续增加, 会导致数据流量包在转发时尽管已超时, 然而源端仍会由于数据包在传输时被丢弃而要求传输端重新发送, 这种做法一是可以使得互联网的工作效率极大地下降了; 二是会使得网络在拥塞现象下的状况变得更加糟糕。

3.2 带宽容量的限制

基于香农理论的主要原理, 对网络中数据信息源的发生速率不得大于信息通道的容量, 这种情况下网络才可以保证正常运转。 但是, 如果信息数据发送源端的带宽要大于网络链路的带宽, 就会在网络的数据输入量和容量之间产生矛盾,在这种矛盾之下, 就会造成网络节点中信息数据的不断累计,进而导致网络拥塞现象的发生。

3.3 处理器性能的局限性

处理器性能低也可能会带来网络阻塞现象的发生。 比如,处理器性能达不到高速链路的要求, 也将极大地降低网络工作效率, 继而导致产生网络拥塞; 还有在互联网中, 因为网络结构设置不科学合理, 也有可能导致网络拥塞。 计算机网络拥塞过程如图1所示。

4 拥塞控制及其属性

拥塞控制实际上是利用一定的控制理论, 从而决定注入网络数据的数量及速度, 然而对拥塞控制进行严格定义却尚未有一个定论。 拥塞控制属性应当由以下几点组成:

(1) 稳定性 , 也就是存在而且仅存在一个平衡点 , 拥塞控制必须要收敛于此平衡点。

(2) 高效性 , 拥塞控制的效率实际上可以理解为两个方面: 一个是拥塞控制的算法要确保网络效率, 保证网络不会出现欠载和过载的情况; 二是拥塞控制必须要及时收敛于某一平衡点。

(3) 公平性 , 针对TCP拥塞控制来说 , 主要是对各个连接间的公平性进行综合考虑; 针对非TCP拥塞控制来说, 则需要对两种公平性进行考虑, 包括协议内公平和协议间公平,也就是TCP友好。

(4) 鲁棒性 , 拥塞控制必须要可以抵御恶意用户的行为 ,也就是可以起到隔离恶意用户的作用, 避免因为恶意行为而对其他用户的满意度产生影响。

(5) 可扩展性 , 针对单播来说 , 拥塞控制的可扩展性主要表现在对各种规模网络、 不同链路状况以及不同端用户能力等都是有效的。 针对组播来说, 拥塞控制的可扩展性不仅如此, 还可以对诸多异构接收者的情况进行处理。

以上5种属性是拥塞控制的理论上分析的境界, 大部分拥塞控制仅仅可以满足其中几种要求。

5 TCP/IP 网络拥塞控制

控制网络拥塞是系统而又复杂的工程, 单纯地从某一点对网络拥塞问题进行控制很难达到应有的效果, 如果处理不当, 甚至会将网络拥塞现象的后果变得更加严重。 在针对网络拥塞现象进行处理时, 应该树立正确的观念, 客观对待网络拥塞存在的复杂性、 繁琐性特征。 可以将控制理论深入融合, 以反馈系统的观点看待网络拥塞现象。 在这种反馈系统中, 可以将网络中输入的各类信息数据看做是系统输入, 输出的是端系统对发包速率进行调整, 基于该种理论下, 发包速率将是对网络拥塞情况的最直接反映因素。 而在这种分析下, TCP和IP网络拥塞算法将是两个主要的分析角度。

5.1 TCP 拥塞控制方法

连接、 稳定和面向字节是传输控制协议的主要特征和内容, 其是针对LAN进行设计的, 信息数据可以稳定地在其传输通道上进行传输, 带重传的肯定确认技术运用其中, 这样可以有效保证通信系统的稳定可靠传输。 在基于TCP/IP网络拥塞的问题研究中, TCP拥塞控制方法将是研究的重点之所在。 在常规的TCP网络拥塞控制中, “拥塞避免” 算法是比较基础的理论, 后期很多算法都是以此为基础发展起 来的 ,可以说是对这种算法的升级和改造, 当然, 此类的算法还有估计周转RTT算法或者 “慢启法” 算法等等。

5.2 IP 拥塞控制方法

网络互联协议是针对计算机网络内部进行通信而设计的一种专门的通信协议, 也可以说, 在互联网传输中的IP也即对通信过程中需要遵守的规则进行制定。 可以有效控制网络拥塞现象的IP控制方法主要有以下几种, 例如, FIFO、 FQ、WFQ、 RED以及ECN。 比如先入先出的原则 , 如果信息数据包优先到达了端口, 就将其优先级标注为较高, 而这种方式本身在队列调度管理中就有着广泛深入的应用。 随机检测算法包括两个方面, 监控队列长度和丢弃数据包, 利用对路由器中的数据包队列长度进行实时监控, 在即将发生拥塞前随机地把数据包丢弃, 降低输出端口的数据量; 显示拥塞指示算法, 使在发送端能够获取拥塞通告, 防止出现任何不必要的丢包事件。

5.3 TCP/IP 网络拥塞控制比较

通过对TCP/IP网络拥塞 的仔细分 析看出 , 若想达到 对TCP/IP网络拥塞有效控制的目的 , 必须在端系统和信源两个方面下功夫。 伴随着拥塞现象的发生, 也会出现网络延迟现象, 而有些则是发生在信息数据达到发送源端之后再进行拥塞信息的反馈。 当前很多网络拥塞都表现出暂时性, 而利用IP对网络拥塞现象进行预先感知 , 在此基础上实现采取相应措施对发生拥塞后采取果断措施, 可以有效区分出在不断发送端下的信息数据, 之后按照一定的队列进行排序, 并完成公平的调度。

6 结语

随着互联网的飞速发展, 新型网络应用和用户数量也逐渐增多, 在这种情况下必然会带来网络流量的增加。 而正是由于网络拥塞问题的存在, 网络发展也受到了极大的 影响 ,拥塞有可能导致传输延迟以及网络吞吐量等Qo S性能指标降低, 造成网络性能降低、 网络资源利用效率下降, 甚至无法确保有效的Qo S。 所以有效解决拥塞问题对于促进网络性能的提升具有一定的意义。

摘要：对TCP/IP计算机网络拥塞相关理论进行了总结,分别对计算机网络拥塞、TCP/IP协议进行了简单介绍,对网络拥塞的原因进行了分析,原因包括存储空间限制、带宽容量的限制、处理器性能的局限性,对拥塞控制及其属性进行探讨,对TCP/IP网络拥塞控制进行研究,对于网络性能的提升起到一定的理论指导意义。

主动拥塞控制应用研究 篇3

1. 主动拥塞控制方法

步骤一:路由器的选径功能是形成拥塞的主要原因, 首先通过一个实例来分析它如何形成拥塞的。图的定义:G=, 其中, V={v1, v2, v3, …vm}, vi (i=1, 2, 3, …m) 为节点。E={e1, e2, e3, …en}, ei (i=1, 2, 3, …n) 为边, g是从E到非负实数集合的函数 (权值) 。图1是一张网络的权值图。

V= (A, B, C, D, E, F, G, H) , E= (AB, AG, BE, BC, GE, GH, EF, FC, FH, CD, HD) , g0 (AB) =2, g0 (AG) =6, g0 (BE) =2, g0 (BC) =7, g0 (GE) =1, g0 (GH) =4, g0 (EF) =2, g0 (FC) =3, g0 (FH) =2, g0 (CD) =3, g0 (HD) =2, 每个节点在发送数据时都要利用它的信源树进行寻径, 以期获最小权值路径, 图2是图1各节点的信源树:

步骤二:每个节点都会按照各自的信源树进行数据投放, 假设每个节点等概率进行数据发送, 按以下规则将各点信源树和并为一张多重图 (流量图) 。 (1) :信源树各点集合合并。 (2) :信源树各边累加合并。如图3所示:

由图3可直观地看出, 当各节点增加数据发送量时节点E和F数据收发量最大, 也是最先、最易发生拥塞的节点, 而C, A, G点的流量相对较小, 形成网络流量的不平衡, 易诱导局部拥塞。定义这些最先、最易发生拥塞的节点为热点, 与该节点相邻弧的条数 (该点的度数) 称为该点的热度值。见表1:

节点E, F, B的热度值较高, 节点C, A, G的热度值较低, 且各点热度值相差很大, 即方差很大 (后面将进行比较) 。可以用热度值的方差值来刻画网络数据的平衡度。网络的热度值方差越大它的数据分配就越不平衡, 如果各点数据继续增加, 点E, F, B就会局部拥塞, 而此刻网络总流量还没有达到它的最大物理承载量, 点C, A, G还有增加传输量的潜力, 可把热点的部分数据转移到非热点上去, 缓解热点的压力, 也就是减少热度值方差, 提高网络平衡度。本文采用以下方法平衡网络流量:局部拥塞是由于路由器在投递数据时采用信源树选径造成的, 改变相应弧的权值, 就可以改变相应信源树的结构, 使得在合成后的流量图中, 任意有连接两点的弧的数量基本相同, 使以前的热点“变凉一点”, 解决各点发送数据时热点的拥塞现象。

步骤三:重新确定整个网络的权值图:各点间的拓朴结构不变, 只改变各弧的权值, 令g1 (ei) =g0 (ei) +h (ei) ×c, h (ei) 为ei相邻两节点热度值和, c的取值将影响新产生的网络权值图与原图在上的变化差别, 本文将在后面介绍c在取不同值时热度值方差量的差别。这里c=1/4, 且为了方便计算同时对h (ei) ×c的取整 (这样会影响迭代精确度) , 得到另一张网络权值图, 如图4所示:

运用前述方法可得c=1/4时的网络重图 (流量图) 和热度表, 如图5, 表2所示:

由上述流量图和热度表可直观看出:以前的热点E, F的热度值已经明显下降, 说明以前流经E, F点的某些数据已扩散到其它点, 如点G, C, 降低了E, F的负荷。热度值方差也明显降低, 说明网络数据流趋于平衡。当网络某热点要发生拥塞时, 可向全网各点发送拥塞信息, 并要求更改网络权值图来寻径, 虽然各点利用更改后权值图发出数据的路径并不是最优的, 是次优的, 但这样能有效地遏制拥塞的发生。权衡拥塞等待或丢弃重发时间, 多走路径的时间是可以接受的。如果热点的热度值还没有降下来, 说明热点向周围节点扩散的数据流还不够, 可以继续使用前述步骤一, 二, 三, 在已改变权值图和热度表的基础上再构造一个权值图, 作出它的流量图和热度表, 如图6, 表3所示:

由图6和表3可以看出, 各节点数据流的分配已基本平衡, 虽然热度值方差在第二次迭代后出现回升, 是由于 (1) 本例中的c值相对过大; (2) 对h (ei) ×c取整造成的, 但随着迭代次数的增加, 方差值会沿一值上下波动, 最终达到动态平衡。依次类推, 形成迭代的权值图和信源树。用一个递归公式来形式化这个过程:

其中, Gk表示K次迭代权值图, 表示当c=1/4时施加于Gk-1上的步骤一, 二, 三。称图1为0次迭代权值图, 导出的路由表为0次迭代路由表, 图3为0次迭代流量图, 图4为1次迭代权值图, 导出的路由表为1次迭代路由表, 图5为1次迭代流量图, 图6为2次迭代流量图。迭代次数越高, 形成的迭代流量图的热度值方差就越小, 路径的最优度也越低, 它是牺牲路径的最优度来达到整个网络数据流的高平衡。当迭代到一定次数后, 它的平衡度将稳定到一定值。

控制方法:若网络产生了局部拥塞, 采用1次迭代路由表, 若还拥塞, 启用2次迭代路由表, 若还拥塞, 再启用高次迭代路由表, 直到网络达到平衡, 消除拥塞为止。数据就会像水一样在网络槽中平衡流动。当路由表的迭代次数达到一定值还拥塞, 说明网络的数据流量已超过整个网络的承载量, 从策略上无法解决因物理局限而引发的拥塞。

2. 结论

通过对网络的静态分析和模拟, 可以预测网络动态运行时的一些节点信息, 并进行静态准备, 动态激发。以上算法经过计算模拟, 其拥塞控制效果和能力与期望基本符合, 是行之有效的。总之, 基于不同应用, 不同网络层次的拥塞控制研究还在继续, 它的成果必然对优化网络结构, 增强网络性能, 提高网络服务质量产生深远影响, 并最终将成为继计算机网络体系结构, 网络信息技术, 网络安全技术后计算机网络领域的又一大研究方向和热点。

参考文献

[1]曾家智等.《计算机网络》 (M) .2002年4月

TCP拥塞控制研究 篇4

网络中的拥塞来源于网络资源和流量分布的不均衡性。一旦网络中存在过多的数据包, 就会导致网络性能的下降, 这种现象称为拥塞。拥塞会导致分组丢失率增加, 从而增大端到端的延迟, 累积到一定程度就是整个系统的崩溃。这样的例子在互联网发展史上曾经不止一次的出现过, 当网络处于拥塞崩溃状态时, 微小的负载增量都将使网络的有效吞吐量急剧下降。

网络拥塞发生的原因说起来也很简单, 就是“需求”大于“供给”。网络本身无法根据现有资源的情况限制用户的数量;互联网络又是一个分散控制系统, 无法控制用户使用资源的数量, 不断增长的用户和应用的数量必然会导致网络发生拥塞。

2 TCP拥塞控制

研究拥塞控制的目的不是要完全避免拥塞, 而是研究怎样的拥塞程度是合适的。TCP网络是可靠数据传输, 采用分组交换技术来提高网络链路的利用率, 也就是说, 路由器队列缓存如果是满的, 则网络利用率最高, 但传输延迟大;队列始终是空的或不满, 则网络利用率低, 传输延迟小。所以拥塞控制的目标就是实现网络利用率和传输延迟等综合性能指标达到最优化, 提高网络的总体性能, 保证网络系统长期的稳定性和鲁棒性。

TCP的实现包含四个连续的基本过程, 其实是四个不同的阶段, 分别是:慢启动、拥塞避免、快速重传和快速恢复。

慢启动:当一个新的TCP连接建立时, 发送方发送一个缺省大小为512字节的TCP报文段 (segment) , 称为拥塞窗口 (cwnd) , 该cwnd的值被初始化为一个数据包, 因此每经过一个RTT, cwnd将指数增加。该算法的原理就是将能发送到网络的新数据包的发送速率对应从接受端返回的确认消息的速率。

拥塞避免:拥塞避免的触发条件是当发现接收方的ACK确认包超时到达或者收到了三个相同的ACK确认包时, TCP就认为网络中出现了拥塞, 开始执行拥塞避免算法, 这里的触发条件是有前提条件的, 那就是TCP假设由于线路传输引起的数据包损坏和丢失的概率非常小, Jacobson V在1988年提出的值为小于1%时条件就成立。在这一阶段, 慢启动阈值 (ssthresh) 设置为cwnd的一半, 如果是超时, cwnd则被置1。如果此时cwnd<=ssthresh。TCP就重新进入慢启动, 如果cwnd>ssthresh, TCP进入拥塞避免, 发送方每收到一个ACK, 则cwnd=cwnd+1/cwnd。可见慢启动阶段cwnd的增加是指数的, 而拥塞避免阶段则是线性的。

快速重传和快速恢复:发送方不等到数据包超时, 在收到三个或三个以上的重复ACK时就判断数据包已经丢失, 这样不用等定时器超时后cwnd置1, 就马上重传该数据包, 同时将ssthresh的值置为当前cwnd的一半, 这种算法来保证TCP保持足够的吞吐量。快速恢复的算法是: (1) 当第三个重复的ACK到达, 设置ssthresh=cwnd/2;重传丢失的报文;设置cwnd=ssthresh+3。加3是因为三个重复的ACK表示有三个数据包已经被接受方缓存了。 (2) 每次有一个更多的重复ACK到达, 把cwnd加1并在可能的情况下传输一个报文段。 (3) 当确认新数据的下一个ACK到达时, 设置cwnd=ssthresh, 进入拥塞避免。

3 TCP拥塞控制算法的改进

3.1慢启动的改进

随着Internet应用在互联网络中的占的比例逐步增大, Web数据流占了网络流量的相当部分, 这些TCP连接的数据量一般都很短小, 通过了解TCP拥塞控制原理, 我们知道短TCP流主要工作的阶段是慢启动阶段, 它不具备长TCP流的传输时间, 无法达到拥塞避免阶段, 所以短TCP流的问题是, 如果一个分组丢失, 按照拥塞控制算法, 需要等待定时器超时重传, 这在带宽竞争上就无法和长TCP流竞争, 从而造成网络的拥塞节点处, 长TCP流会挤掉短TCP流, 使贷款分配不均。针对这些问题, 研究者们提出了传统的慢启动存在的两个问题: (1) 数据发送从一个数据包开始, 要经过多个RTT才能达到较大吞吐量, 这不利于流量小但是链路延迟又比较大的TCP流的传输; (2) 采用指数增长的方式发送数据造成了数据突发, 易引起瓶颈链路的拥塞。

针对第一个问题, 大家提出了很多解决方法, 比如采用大的初始窗口, 将初始窗口从1MSS增加到4MSS, (Allman M.et al, 1998) , 这种方法虽然可以改善慢启动的性能, 但是不能适应多变的网络带宽。还有就是将各个TCP连接的信息共享 (Padmanabhan V.et al, 1998;Touch J, 1997;Savage S.et al, 1999) , 后面的连接可以使用具有相同目的地址的连接信息, 从而可以减少慢启动的时延, 但是这样会使连接很快造成网络拥塞, 而短TCP的长度只需要几个RTT就可以传输完毕, 网络拥塞会造成额外的时延。再后来提出了将初始窗口设定为4个分组, 而从以快速重传来减少重传超时造成的传输时延 (Mellia M.et al, 2001) 。

解决第二个问题可以通过使用带宽时延的估计来设定初始慢启动阈值ssthresh (Hoe J, 1996) 。Smoot-start方法 (Marchese M, 2001) 使发送方从慢启动阶段较为平滑的过渡到拥塞避免阶段, 减少了数据包丢失和突发流, 当拥塞窗口到达Smsthresh后, 采用比较平缓的指数方式增长拥塞窗口, 逐渐达到默认值或估算的ssthresh值。

3.2快速重传和快速恢复的改进

有时发送端减少拥塞窗口值并不是因为分组丢失, 而是分组数据传输中顺序错误引起的重复ACK。有限传输机制 (Allman M, Balakrishman H.and Floyd S.2001) 是一种改进方法, 当发送端收到一个或两个重复的ACK后, 如果被允许, 发送端就发送一个新的分组。这种方式对错序的状况有较好的调节作用。还有D-SACK方式, 是一种基于SACK的方式, 通过给TCP发送端一个附加信息, 来判断是否发生了不必要的重传, D-SACK通过接收端受用SACK选项来报告收到了重复的分组序列, D-SACK在容易引起错序的环境下提供更高的效率。

快速恢复的改进机制有SACK (Selective Acknowledgement) , FACK (Forward Acknowledgement) , TCP New-Reno等。SACK方式的接收端通过ACK向发送端通过所有正确的分组, 发送端只需重传真正丢失的分组。FACK是基于SACK的改进, 它们的问题都是增加了TCP的复杂性, 对TCP版本的兼容性较差。TCP New-Reno不需要接收端的特殊支持, 相对实现起来简单, 但是数据传输效率相对不高。RateHalving (Allman M, Dawkins S, Glover D, et al, 2000) 是FACK的一个比较新的版本。在快速恢复阶段, 每收到2个ACK发送一个新的分组, 从而在一个RTT里将拥塞窗口减小到网络能处理的分组数的一半大小, 并保持了TCP的自计时特性。

目前, TCP基于窗口的拥塞控制策略被广泛的应用。各种改进的TCP控制策略在不同侧面解决了一定的问题, 但是也有着局限性, 有的实现起来过于复杂, 有的解决了多个分组丢失的恢复问题, 但对恢复过程中出现的分组丢失却无法得到解决。

4结束语

在实际的应用中, 针对不同特点的TCP网络, 有着适合的改进策略, 这些策略不用做到面面俱到, 只要具有一定的针对性就可以。网络拥塞的改进是十分灵活的, 方法也很非常多, 其原因正式因为不同网络中传输的数据特点不同, 从而选择合适的改进策略是关键。

(上接第153页) [1]Allman M, Hayes C, Ostermann S.An Evaluation of TCP with Larger Initial Windows[J].ACM Computer Communication Review, 1998, 28 (5) 41-52.

[2]邓亚平, 叶凌伟, 陈雁.TCP/IP拥塞控制算法的改进[J].计算机科学, 2001 (4)

110-113.

[3]王彬.TCP/IP网络拥塞控制策略研究[D].浙江大学, 2004

参考文献

[1]Allman M, Hayes C, Ostermann S.An Evaluation of TCP with Larger Initial Windows[J].ACM Computer Communication Review, 1998, 28 (5) :41-52.

[2]邓亚平, 叶凌伟, 陈雁.TCP/IP拥塞控制算法的改进[J].计算机科学, 2001 (4) :110-113.

网络拥塞控制策略的研究 篇5

1 TCP的拥塞控制

为了更好地在运输层进行拥塞控制, 1999年公布的因特网建议标准定义了以下四种算法, 即慢开始、拥塞避免、快重传和快恢复。

1.1 慢开始和拥塞避免

慢开始算法原理:先设cwnd=1, 发送第一个抱文M0, 接收端收到后发回ACK1。发送端收到ACK1后, 将cwnd从1增大到2, 于是发送端每收到一个ACK, 就使发送端的cwnd加1。

其中:ACK-确认号;

C w nd-拥塞窗口, 是来自发送端的流量控制;

R w nd-接受端窗口, 是来自接收端的流量控制;

TCP采用大小可变的滑动窗口进行流量控制, 即:

实际流量=滑动窗口的上限值=min (r w n d, c w n d) 。

慢开始算法使发送端在开始发送时向网络注入的分组数大大减少, 这对防止网络出现拥塞是个非常有力的措施。

由于慢开始算法的“慢”指的是开始时的分组数发送的少, 但发送分组的增长速率并不慢。为了防止拥塞窗口cwnd的增长引起网络拥塞, 还需要另一个状态变量, 即慢开始门限ssthresh。用法如下:

当cwnd

当cwnd>ssthresh时, 改用拥塞避免算法;

当cwnd=ssthresh时, 既可使用慢开始算法, 也可使用拥塞避免算法。

拥塞避免算法是使发送端的cwnd每经过一个往返时延RTT就增加一个MSS的大小 (而不管在时间RTT内收到了几个ACK) 。这样, 拥塞窗口rwnd按线性规律缓慢增长, 比慢开始算法的增长速率慢得多。

“乘法减小”—只要出现一次超时, 就将ssthresh设置为当前拥塞窗口值乘以5.0。

“加法增大”—执行拥塞避免算法后, 当收到所有发出报文的确认就将cwnd增加一个MSS大小。

1.2 快重传和快恢复

快重传:发送端一连收到三个重复的ACK即断定分组丢失, 而不等到计时器超时才重传丢失的报文。

快恢复: (1) 当发送端连续收到三个重复的ACK时, 就按“乘法减小”重置ssthresh。 (2) 与慢开始不同之处是cwnd不是设置为1, 而是设为ssthresh+3*MSS。 (3) 若收到重复的ACK为n个 (n>3) , 则cwnd设为ssthr esh+n*MSS。 (4) 若滑动窗口值还允许发送报文段, 就执行拥塞避免算法。 (5) 若收到了确认新的报文段的ACK, 就将cwnd缩小到sst hres h。

2 IP的拥塞控制

TCP拥塞控制并没有和网络层采取的策略联系起来, 网络层的策略对TCP拥塞控制影响最大的就是路由器的数据报丢弃策略。目前, 常用的IP拥塞控制算法是随机早期检测 (RED) 方法。基本思想是按一定的概率丢弃路由器的数据包。

首先计算平均队列长度:

式中:avg_q为平均队列长度, w为权值, q为采样测量时实际队列长度。

计算丢弃包的概论:

min_th和max_th是二个和队列长度相关的阈值, count是上次丢弃分组后收到的分组个数, 当有包到达路由器时, RED计算出平均队列长avg_q, 若avg_qmax_th时, 所有包都被丢弃。

RED算法的有效性和可靠性取决于选择合适的配置参数, 而且丢包率又是平均队列长度avg_q的静态映射, 因此, 容易引起网络的不稳定, 当业务的突发度较强或流量抖动较大时, 并不能获得满意的吞吐性能。

3 智能拥塞控制算法

AQM作为端到端拥塞控制机制的一个改进, 通过有目的地丢弃路由器间的分组, 可维持较小的排队延迟和较高的吞吐量。主动队列管理算法的研究主要集中在2个方向: (1) 依赖于启发式的直觉思维, 针对局部个别问题的启发式算法设计方法, 典型的如Floyd等提出的随机早期检测RED算法以及RED的派生算法, 除此之外新的启发式AQM算法也不断涌现, 诸如BLUE, REM, GREEN, GKVQ等。 (2) 以随机过程、控制理论等系统理论作为算法分析和设计的依据。最具代表性的如Hollot等利用经典控制理论作为分析和设计的依据, 用频域分析的方法提出的比例积分 (PI) 控制算法, 以及Ren等为了克服PI控制器响应速度慢这一问题, 加入了微分环节, 提出具有快速响应的PID控制器。总结AQM中各种策略与算法的研究不难发现, 启发式的设计方法不免带有盲目性和片面性, 造成最终形成的算法不免存在各种意想不到的缺陷。

基于神经网络补偿器算法是一种通过“拥塞通知” (ECN) 标志TCP的AQM路由器自调节控制法, 该算法TCP和IP层的拥塞控制, 是一种智能控制算法。当队列长度高于上限时, 路由器中ECN置为1, 这样TCP源将缩小发送窗口大小以减小速率。相反, 当队列长度低于下限时, 路由器中的ECN置为0, TCP源扩大窗口大小以增大速率。结果是, 路由器中的队列长度将维持在区间[qmin, qmax]之间。当路由器的队列长度界于区间[qmin, qmax]时, 则关闭ECN标记, 自调节控制器计算丢弃并且丢弃或标志在路由器中的分组, 以使TCP源调节其发送速率, 从而是路由器的队列趋于期望值。

通过修改ECN可使路由器队列长度维持在[qmin, qmax], 从而降低了路由器队列的抖动, 提高了控制系统的瞬变性能。自调节控制器使瞬时队列长度趋向于设定的队长, 进一步增强了稳定性。

4 结语

本文对TCP拥塞控制算法, IP拥塞控制以及结合二者的智能控制算法进行了描述。随着计算机通信网络的理论的不断完善, 计算机网络性能分析和控制理论、神经网络、人工智能、专家系统等技术进一步进行交叉和有机结合将成为拥塞控制的发展趋势和研究的新方向。

摘要：对网络拥塞控制的研究具有重要的理论意义和实际应用价值。人们提出了很多的拥塞控制方法和策略, 慢开始、快重传和快恢复算法等。而这些TCP拥塞控制算法都没有考虑到网络层采取的策略, 于是出现了随机早期丢弃 (RED) IP拥塞控制算法。随着智能控制路论与技术的发展, 也出现了许多智能算法, 取得了不少的进步。

关键词：网络拥塞,拥塞控制

参考文献

[1]谢希仁.计算机网络[M].电子工业出版社.

[2]李之芳.网络拥塞的原因分析及控制策略[J].经营管理者, 2010, 7.

组播拥塞控制的研究(英文) 篇6

关键词：组播,拥塞控制,TCP友好性

I.INTRODUCTION

Multicast provides an effi cient way of delivering a single data stream from one sender to a group of receivers.However,multicast is not a mature technique for large-scale Internet data transmission because of the heterogeneity amongst end systems’computational capabilities and their available network bandwidth.During the past decade,many multicast congestion control schemes are proposed to solve the problem.

Multicast congestion control is responsible for congestion collapse avoidance and co-existence with existing TCP.On one hand,multicast congestion control must ensure multicast receivers’satisfaction and prevent multicast traffic from suffering congestion.Internet Protocol,IP,which underlies multicast transmission layer,offers only best-effort packets delivery.The defi ciency of proper congestion control mechanisms may lead to congestion collapse and eventually endanger the stability of the network.Many multicast congestion control mechanisms have been proposed to address this issue.It is natural to adopt unicast TCP congestion control mechanisms,which have been proved effi cient and practical in currently widely used TCP connections.Though varying in details,these proposed TCP-like mechanisms mimic TCP’s AIMD[1]behavior.Due to the fl uctuation of AIMD,other more advanced congestion control schemes,e.g.equation-based,are proposed to generate more smooth transmission fl ow.Meanwhile,as the multicast session has multiple receivers,which may vary in downward link bandwidth,it is a problem to achieve fairness between receivers.Such a requirement can be satisfied by a layered multicast scheme that allows different receivers to subscribe different numbers of layers to achieve different rates.Layered approach is the current trend in multicast congestion control.However,layered approach also places new challenges to multicast congestion control,e.g.,layer granularity,joinlayer coordination etc.As multicast group size increase,the sender may be overwhelmed by the receivers’feedback information if congestion control is totally left to the sender.TCP-like sender-driven congestion control does not scale up well.Receiver-driven schemes were proposed to provide better scalability.

In this paper,we present a overall survey on existing multicast congestion control schemes by classifi cation to summarize state-of-the-art in this fi eld.

II.OVERVIEW OF MULTICAST CONGESTIONCONTROL

Both unicast and multicast require traffic regulation to avoid and control congestion.Issues related to multicast congestion control include traffi c regulation,multicast group management,data layering and coding router function,of which traffic regulation is the central one.As it’s for unicast congestion control,those issues simply reduce to traffi c regulation.

Congestion control task can be left either to network layer or to transport layer according to ISO-OSI reference model.However,network layer in Internet TCP/IP model is IP layer,which offers only hop-by-hop best-effort data forwarding.To ensure congestion control in IP layer,new components should be added to IP layer.RSVP[2]is such a protocol that enhances router functions and provides QoS guarantee.This is similar to virtual circuit style data transfer.The session makes reservation ahead of time whenever starting data transmission.Pricing mechanism,which mimics financial incentives,also needs router support to implement the principle:pay more and obtain more.Such congestion control schemes are defi ned as router-supported congestion control.Adding Explicit Congestion Notification(ECN)[4]to IP layer can also inform the multicast session of incipient congestion.Thus the session can react to ECN and avoid congestion.In addition,some maintenance mechanisms such as feedback aggregation are required for multicast congestion control.Unfortunately,these router functions have not been deployed widely.Hence,another dominant congestion control mechanism,end-to-end congestion control,is widely used and proved effective.End-to-end congestion control is implemented in transport layer.

A.Traffi c regulation characteristics

We characterize traffic regulation in end-to-end congestion control by four attributes:Regulation parameter(RP),Regulation initiator(RI),Congestion Indicator(CI),and Regulation algorithm(RA).The four attributes are enough to describe the regulation behavior.When suffering from congestion indicated by CI,congestion control mechanism triggers RA at RI side to react to congestion by adjusting RP.

B.Multicast traffi c regulation

In TCP sessions,congestion control tasks reduce to only traffic regulation.TCP traffi c regulation attributes are respectively RP:window,RI:sender,CI:ACK and RA:AIMD.Multicast traffi c regulation can also be defi ned by the four-attribute tuple.For heterogeneity consideration,{RP,RI,CI,RA}should be properly selected.

C.Multicast group management

Multicast group management defines multicast group membership and group communication model.Multicast communication model can be classified into dissemination model(one to many)and collaborative model(many to many).The former can be viewed as a special instance of the latter with only one sender.Group membership in multicast session can be either static or dynamic.In static group membership circumstance,multicast members are permanent throughout the session.Once the session starts,no connected members are allowed to leave and no new members are permitted to join.In dynamic group,any member can join or leave the group regardless of whether the connection starts.From the viewpoint of receivers,the group membership of receiver can be canceled either by the receiver itself or by the session.The non-determinacy of group membership can both complicate and benefit and the design of congestion control schemes.On one hand,dynamic membership poses new problems such as whether a specifi c packet is correctly received by all receivers,and whether the non-responsive receiver has left the group.On the other hand,the session can cancel membership of some receivers to avoid congestion.A straightforward method is to cancel the receiver behind the bottleneck link since its bandwidth is not enough.

D.Data layering and coding

Multicast group heterogeneity is a practical challenge.Different receivers may be distributed behind varying bandwidth link.If the sender transmits data at a single rate,low-capacity regions of the network suffer congestion while high-capacity regions are underutilized.

To accommodate heterogeneity,source data are encoded into a number of layers.These layers can either be dependent or independent.Dependent layers can be incrementally combined to provide progressive refinement.Each layer is sent to a different multicast address and the receivers subscribe to as many layers as their bottleneck bandwidth permits.Furthermore,dependent layers can be cumulative or non-cumulative[6].Cumulative layers scheme imposes an order on the multicast layers and requires clients to subscribe and unsubscribe to layers in sequential order while non-cumulative one is not restricted to sequential order.The granularity of cumulative layers is associated with throughput.The bandwidth each layer consumes may be equal or exponentially distributed.

In independent layers scheme,each layer provides a different rate that results in different quality.These different layers are not cumulative.The receivers only need to subscribe one proper layer that the bandwidth can afford.Nevertheless,independent layers scheme waste some bandwidth in sending the redundancy of basic quality data.Independent layers schemes are a design mistake when trying to enable congestion control.

Layered approaches can enhance the overall transmission effi ciency and avoid congestion in low-capacity link.The receiver-driven layered multicast(RLM)[7]is the first comprehensive instance of a layered approach.RLM is rate-adaptive using cumulative layers scheme.Many subsequent mechanisms adopted methods in RLM.

Besides layering,another approach named transcoding can also ensure heterogeneous receivers achieving optimal rate corresponding to their bandwidth.In transcoding approach,the source transmits at a rate matching the fastest of its receivers.The transmission rates are transcoded at the intermediate nodes to match the capabilities of slower receivers downstream.At every link,the transmission rate of a session is equal to that of the fastest session receiver downstream of the link.

Layered multicast is especially efficient for packetized audio/video transmission.Receivers with different bandwidth can subscribe corresponding amount of layers and get proper QoS.Nevertheless,as for software distribution,all the receivers must get the exactly the same copies.Different rates result in time delay in low-capacity bandwidth receivers.Hence the transmission is not synchronous for all receivers.Bhattacharyya et al[8]proposed new idea to address the problem.The sender use heuristics to determine the rate of each layer and a specifi c data should be sent over which layer.

E.Router function

There are mainly two classes of router functions related to congestion control:queue management and scheduling.Queue management algorithms manage the length of packet queues by dropping packets when necessary or appropriate,while scheduling algorithms determine which packet to send next and are used primarily to manage the allocation of bandwidth among fl ows.

As TCP exemplifies,traditional end-to-end congestion control mainly rely on end systems,while routers only perform drop-tail queue management and FIFO scheduling.As it for multicast,extra functions may be needed to achieve better performance.

RED is currently highly recommended as the active queue management mechanism in routers.RED randomly marks packet queue with a probability to inform the receivers of incipient congestion.Priority drop is also a queue management mechanism.On congestion,packets with low priority are dropped earlier that packets with high priority.Flow isolation is kind of classification mechanism that enable routers isolate different priority queues from one another.

Some schemes require routers enable more complex scheduling mechanism other than FIFO.PLM[9]is feasible on condition that all routers implement Fair scheduler(FS)paradigm,which is a Packet Generalized Processor Sharing scheduler with longest queue drop buffer management.

Besides queue management and scheduling,some multicast protocols assume routers have extra functions related to multicast transmission such as feedback aggregation,hierarchical RTT estimation.Thus,extra overhead is introduced to maintain session information.

If a multicast congestion control scheme requires only droptail queue and FIFO scheduling,we say the scheme is free from additional router functions.

III.CLASSIFICATION

A number of multicast congestion control schemes have been proposed.We can classify congestion control schemes with respect to the above discussed congestion control components{traffic regulation,multicast group management,data layering and coding,router function}.Of all the components,Regulation parameter,Regulation initiator and Data layering and coding,router function are the most signifi cant classifi cation criteria.Advantages and drawbacks of each scheme are also summarized in this section.

Many multicast congestion control schemes were proposed.For brevity and novelty consideration,we analyze several recently proposed typical schemes,namely RLM,Representatives[10],LTRC[11],RLC[12],LVMR[13],RLA[14],MTCP[15],MLDA[16],PLM,pgmcc[17],Rainbow[18],FLID-DL[19],SAMM[20],TFMCC[21],CIFL[22],MCA[23],HALM[24],SMCC[25].

A.Window-based vs.rate-based

The advantage of window-based scheme is that it has a good integration with error control and traffic regulation.Error recovery is selective repeat,i.e.,only packets that are suspected to be lost or corrupted are retransmitted.It’s easy to keep the amount of outstanding unacknowledged packets by keeping a proper window size to perform traffi c regulation.Also,window-based scheme reacts to network changes faster.TCP is a success that uses window as RP.

The advantage of rate-based scheme is that it is a natural control parameter for certain applications,e.g.streaming media,which have intrinsic sending rates.Also rate control generates traffi c into the network smoothly.One of the drawbacks of rate-based scheme is that the complexity to achieve TCP-friendliness.As mentioned in sectionⅡ,equation-based rate control can achieve long-term TCP-friendliness.

Typical window-based multicast congestion control schemes are mostly single-rate considering the extra overhead in keeping multiple windows with multiple rates for each receiver.RLA,MTCP and pgmcc are all window-based single-rate schemes.The only comprehensive multi-rate window-based scheme is Rainbow.

Rate-based schemes include RLM,RLC,LVMR,MLDA,PLM,FLID-DL,SAMM,CIFL,MCA,HALM,and SMCC.Most rate-based schemes are of multi-rate with the exception Representatives,LTRC,TFMCC.

B.Receiver-driven vs.Sender-driven

The sender-driven approach places the responsibility for providing traffi c regulation on the sender,which maintains state information on all receivers to which it is multicasting.Receiver-driven protocols place the responsibility for traffi c regulation on the receivers.The sender continues to transmit new data packets until it receives a NAK from a receiver When this occurs,the sender then retransmits(i.e.,again multicasts)the packet required by that receiver.The role of the receiver is to check for lost packets.If it decides that it has not received a particular packet,it transmits a NAK to the sender.In multi-rate multicast,receiver-driven approaches require the receivers to decide their respective rates.

Sender-driven schemes can suffer performance degradation as the number of receivers increases.This degradation is due to the fact tha the sender must bear much of the complexity associated with traffic regulation(e.g.,maintaining RP for each of the receivers and responding to receivers’CIs).

RLA and Representatives fall into sender-driven category.Generally speaking,receiver-driven schemes are more suitable for multicast congestion control considering scalability purpose.Receiver-driven schemes include RLM,LTRC,RLC,MTCP,PLM,pgmcc,Rainbow FLID-DL,TFMCC,CIFL,and SMCC.LVMR is a hybrid sender and receiver-driven scheme that distributes congestion control tasks amongs sender and receivers.MLDA,SAMM,MCA and,HALM are also senderand receiver-jointly driven scheme.Though effective,sender-and receiverjointly driven schemes need information exchange between sender and receivers,which complicates congestion control mechanism.

C.Single-rate vs.multi-rate

The central role of data layering and coding involves opting for single-rate or multi-rate scheme.In single-rate schemes,data is sent to al receivers at the same rate.This cripples the scalability of the mechanism since all receivers are restricted to the rate that is limited by the bottleneck receiver.Multi-rate transmission of data is often recommended as a solution to the problem of varying bandwidth constraints.Flexible rate adaptation is allowed for heterogeneous receivers.The receivers can tune their rate according to bandwidth limitation.Therefore multi-rate schemes have better scalability.

In the forepart of research in multicast congestion control,most proposed schemes then are single-rate,such as Representatives,RLA LTRC,and MTCP.After layering technology is fi rst introduced in RLM many newly proposed schemes adopt this idea,such as RLC,LVMR MLDA,PLM,Rainbow,FLID-DL,SAMM,CIFL,HALM and SMCC However,there still remains room for single-rate schemes,such as pgmcc TFMCC,MCA.TFMCC and pgmcc are even under IETF standardization.

D.Router-supported vs.end-to-end

Pure end-to-end congestion control requires no additional router functions to support the multicast protocol.Thus,such schemes scale up well since no changes are needed in current underlying network infrastructure.

Router-supported congestion control grants routers responsibilities of congestion detection and fair sharing.To shift some congestion contro functionality to network can balance the overhead of end systems Meanwhile,the additional functions in router can tackle some problems in multicast congestion control such as feedback implosion,subgroup management.Advanced queue management and scheduling mechanisms also perform fl ow classifi cation that is absent in pure end-to-end congestion control.The fatal drawback of router-supported congestion control is tha changes to the currently running routers are necessary.

RLM,LTRC,RLC,RLA,MLDA,FLID-DL,TFMCC,CIFL,MCA HALM,SMCC are all end-to-end schemes,which can be deployed in current Internet.Representatives,LVMR,MTCP,PLM,pgmcc,Rainbow SAMM are all router-supported schemes.

Representatives scheme,LVMR,MTCP need the routers perform multicast tree structure maintenance.PLM is applicable only when al routers deploy Fair Scheduler paradigm.Though the authors argue that FS is a feasible,it is obvious that fundamental changes to router requires time.In pgmcc,feedback aggregation is an optional function by routers If necessary,routers only forward the fi rst NAK for a given data segment and suppress subsequent NAKs.Rainbow relies heavily on additional router intelligence.Routers store all the requests from receivers,and then accumulate multiple requests for the same packet from distinct receivers After forwarding a specifi c packet to the receivers,router will delete the requests for that packet.In SAMM,the sender adapts target bitrate for each layer according to the backward feedback from the receivers.In routersupported SAMM,routers need additional functions:monitoring available bandwidth and calculating each competing fl ow’s share.

IV.CONCLUSION