（信号与信息处理专业论文）基于多速率分层组播网络拥塞控制研究.pdf

摘要 随着i n t e r n e t 的不断发展，组播网络拥塞控制引起了广大的研究 者的重视。组播拥塞控制在避免网络拥塞崩溃和保证公平竞争带宽资 源中是必须的，因此组播网络拥塞控制算法是重要研究点。 本文首先对主要的组播网络拥塞算法进行了研究和分析。现有的 组播拥塞控制算法，在异构网络环境下，缺乏友好和公平性，不利于 网络的扩展和拥塞的解决。因此，针对以上存在的问题，根据不同公 平标准的分析。然后，提出了一种多速率分层组播网络的分组标记公 平算法f a t m ( f a i ra g g r e g a t et r a f f i cm a r k e r ) 。新改进的算法在保持聚 集流之间的公平性和网络吞吐量的基础上，提高聚集流内部单个流之 间的公平性，从而降低了组播网络的拥塞。保证t c p 友好公平，减 少了带宽资源竞争中饥饿现象，提高了网络的利用率，并在算法改进 过程中，利用了自回归模型对组播网络流量进行了预测和分析，为算 法的改进提供了可靠的数据保证。 最后，利用了网络模拟器对改进的算法进行了仿真实验，对实验 结果的数据分析和比较。分组标记公平算法f a t m 能够有效地改进区 分服务网络上的多速率分层多播拥塞控制的。i i i ，具有较快的拥塞响 应速度、较好的稳定性和公平性，并且较好地适应了网络的异构性。 关键字组播，多速率，流量，预测，公平性 a b s t r a c t w i t ht h ed e v e l o p m e n to f i n t e m e t ，m u l t i c a s tn e t w o r kc o n t r 0 1a t t r a c t s l o t so fr e s e a r c h e r si n t e r e s t i n g n e t w o r kp r e d i c t i o na n dp a c k e tm a r k i n g a l g o r i t h mi na r et h em o s ti m p o r t a n tr e s e a r c hp o i n t so fc o n t r o ls y s t e m t h e s et w oa s p e c t sa r ea l s ot h em a i nc o n t e n t so ft h i sd i s s e r t a t i o n f i r s t l y ，t h em a i na l g o r i t h m so fc o n g e s t i o nc o n t r o lo nm u l t i c a s ta r e r e s e a r c h e da n da n a l y s e d t h e s ea l g o r i t h m si nt h eh e t e r o n e t w o r ka r e s h o r to ff a i m e s sa n df r i e n d l i n e s s h o w e v e r , t h ef l e x i b l ea n dc o n g e s t i o ni n n e t w o r ka r es o l v e di n e f f i c i e n t l y an e wp r o m o t i o no fc o n g e s t i o nc o n t r o l a l g o r i t h mw h i c hi sf a t m ( f a i ra g g r e g a t et r a f f i cm a r k e r ) i sp r o v i d e dt o s o l v et h e s ep r o b l e m so nm u l t i c a s t t h em a r k i n ga l g o r i t h mi sr e s e a r c h e d i nd i f f s e r v ( d i f f e r e n ts e r v i c e s ) n e t w o r k ，a n dt h ef a i r n e s sp e r f o r m a n c ei s i m p o r t a n t l ya n a l y z e di nm a r k i n ga l g o r i t h m s t h ef 删c a ni m p r o v et h e f a i m e s sa m o n gt h ei n d i v i d u a lf l o w sw i t h i na na g g r e g a t i o n ，w h i l ek e e p i n g t h ef a i m e s sa m o n gt h e a g g r e g a t e t r a f f i cf l o w sa n dt o t a ln e t w o r k t h r o u g h p u t t h ea u t o r e g r e s s i v ep r e d i c t i o nm o d e li su s e dt oa n a l y z ea n d p r e d i c a t et h et r a 伍co fl a y e r e dm u l t i c a s to fm u l t i r a t ew i t hp r o m o t i o no f t h ea l g o r i t h m ，w h i c h p r o v i d e sr e l i a b l ed a t at os u p p o r tt e s to fr e s e a r c h f i n a l l y , t h en s 2w h i c hi s an e t w o r kt o o li su s e dt o a n a l y z e p e r f o r m a n c ei nm a r k i n ga l g o r i t h m s s i m u l a t i o nr e s u l t ss h o wt h a tf a t i 、僵 a l g o r i t h mi sm o r er e s p o n s i v e ，m o r es t a b l ea n df a i r , a n dc a na d a p tt o n e t w o r kh e t e r o g e n e i t yb e t t e r k e yw o r d sm u l t i c a s t ，m u l t i r a t e t r a f f i c ，p r e d i c t i o n ，f a i m e s s i l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者虢驻嗍赳年上月兰日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 作者签名：瓣导师签名 第一章绪论 随着组播应用在因特网上广泛开发，组播拥塞控制变得越来越重要。基于 i n t e m e t 的多媒体组播应用的迅猛发展对组播捌塞控制提出了要求。分层组播是 适应网络异构性较有效的方案。针对现有分层组播存在的问题，仿真实验表明， 该方案大大改进了分层组播捌塞控制的性能，具有较快的拥塞响应速度、较好的 稳定性和t c p 友好特性。 1 1 组播拥塞控制研究背景 t c p 的搠塞控制是i n t e r n e t 正常运行的基础，围绕着t c p 的拥塞控制一直是 i n t e m e t 研究的一个热点。在i n t e r n e t 发展初期，拥塞控制主要是通过t c p 协议 中端到端基于滑动窗口的流量控制完成的。t c p 的流量算法中也逐步增加了慢启 动、拥塞避免、快速重传和快速恢复等算法，以期对网络流量进行控制。控制网 络流量，减少网络拥塞是一种提高网络性能的有效途径。最早的t c p 拥塞控制 和避免算法是建立在把整个网络作为一个不可控的“黑盒”之上，源端逐渐增加网 络流量，直到网络中出现丢失分组的行为，从而判断拥塞的发生。这种算法具有 较大的端到端延迟和丢失率。这种机制用丢失分组的办法来标识网络中出现拥 塞，对早期的应用来说，这种方法是适当的。但是，随着网络实时应用( 如视频 传输、电视会议、远程医疗等) 发展，要求在传输时尽量降低传输延迟和丢失率， 那么这种机制就不适合了。随着应用需求的丰富和技术的发展，研究者们开始研 究能在源端更早地感知网络中将要出现的拼j 塞情况的算法，在网络发生拥塞前调 整发送速率。就捌塞控制而言，提前通告源端控制发送速率的捌塞控制算法能更 及时，甚至提f j i 准确了解网络的拥塞状态，并依此实施有效的资源管理策略，使 网络能有效地避免拥塞，或尽早从严重的拥塞状态中恢复过来。 组播传输所面临的最主要的问题就是提供一种可扩展性和公平性的控制机 制，既能与t c p 传输相适应，同时能克服网络的异构性，为端到端的网络接收 者进行组播数据传递。多速率组播捌塞控制不仅解决了组播的可扩展性问题，而 且提高了异构网络带宽的利用率，在i n t e m e t 组播应用领域倍受关注。对多速率 分层组播 | j 塞控制的性能进行了评价后，着重研究了与公平性有关的问题和解决 方法。 1 2 组播拥塞存在的原因 当网络中存在过多的报文时，网络的性能会下降，这种现象称为捐j 塞。使用 图1 1 来描述拥塞的发生当负载较小时，吞吐量的增长和负载相比基本呈线性关 系，延迟增长缓慢：在负载超过k n e e 之后，吞吐量增长缓慢，延迟增长较快， 当负载超过c l i f f 之后，吞吐量急剧下降，延迟急剧上升可以看出，负载在k n e e 附近时网络的使用效率最高拥塞控制就是网络节点采取措施来避免拥塞的发生 或者对拥塞的发生作出反应，在图1 1 中就是使负载保持在k n e e 附近。拥塞控 制主要考虑端节点之间的网络环境，目的是使负载不超过网络的传送能力：而流 控制主要考虑接收端，目的是使发送端的发送速率不超过接收端的接收能力。拥 塞控制是“恢复”机制，它用于把网络从拥塞状态中恢复出来：拥塞避免是“预 防”机制，它的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延迟 的状态下。 k n k n e ec l i l f j fe：it t 卜 ，r 一 网 络 吞 吐 且 里 丽缠在按 图1 1 网络捌塞 拥塞产生的直接原因有以下3 点： ( 1 ) 存储空间不足 几个输入数据流共同需要同一个输出端口，在这个端门就会建立排队。如果 没有足够的存储空间存储，数据包就会丢弃。对突发数据流更足如此。增加存 储空间在某种程度上可以缓解这一矛盾， 但如果路由器有无限存储量时，拥塞 只会变得更坏，不是更好，因为在网络里数据包经过长时l 训排队完成转发时，它 们早己超时，源端认为它们已经被丢弃，而这些数据包还会继续向下一路由器转 2 发，从而浪费网络资源，加重网络拥塞。 ( 2 ) 带宽容量不足 低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论，任何信道 带宽最大值即信道容量c = bl 0 9 2 ( 1 + s n ) ( n 为信道白噪声的平均功率，s 为信 源的平均功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容 量c 。如果r c ，则在理论上无差错传输就是不可能的，所以在网络低速链路处 就会形成带宽瓶颈，当其满足不了通过它的所有源端带宽要求时，网络就会发生 拥塞。 ( 3 ) 处理器能力弱和速度慢也能引起拥塞 如果路由器的c p u 在执行排队缓存，更新路由表等功能时，处理速度跟不 上高速链路，也会产生拥塞，低速链路对高速c p u 也会产生拥塞。要避免拥塞 的发生。 对以上3 点原因需综合考虑。例如，提高链路速率而不改变处理器，只会 转移网络瓶颈，而不能避免拥塞。所以拥塞往往也是系统各部分不匹配的结果。 拥塞一旦发生往往会形成一个不断加重的过程。如果路由器没有空余的缓存， 它就必须丢弃新到的数据包。当数据包丢弃时，源端会超时，重传该包。由于没 有得到确认，源端只能保留数据包，结果缓存会进一步消耗，加重拥塞。 拥塞发生的原因是“需求 大于“供给 。网络中有限的资源由多个用户共 享使用。由于没有“接纳控制”算法，网络无法根据资源的情况限制用户的数量， 缺乏中央控制，网络也无法控制用户使用资源的数量。目前，i n t e r n e t 上用户和 应用的数量都在迅速增长，如果不使用某种机制协调资源的使用，必然会导致网 络拥塞。虽然拥塞源于资源短缺，但增加资源并不能避免拥塞的发生，有时甚至 会加重拥塞程度。例如，增加网关缓冲会增大报文通过网关的延迟，如果总延迟 超过端系统重传时钟的值，就会导致报文重传，反而加重了拥塞。拥塞总是发生 在网络中资源“相对 短缺的位置。拥塞发生位置的不均衡反映了i n t e r n e t 的不 均衡性。 1 3 组播网络的拥塞控制的标准 现有的组播拥塞控制方案的性能可以用一系列的标准如公平性，可扩缩性以 及复杂性来进行评价。根据i e t f 的建议，一个组播协议必须具有可扩缩性，公 平性，可靠性，以及异构性等特性。 ( 1 ) 公平性是指同一个组播会话的接收者之间公平的分配带宽，也就是说， 组播协议必须具有内建的机制保证最大限度使用带宽满足所有接收者的最大限 度要求。单速率传输由于不能满足所有接收者接收到合适的速率，所以不能保证 会话内公平性。分层组播和编码变换组播都可以提供会话内公平性。多速率组播 的引入后，当组播网络的接受端竞争带宽资源时，需要有机制保证公平性，以免 产生饥饿的现象，公平竞争对保持传输的稳定性也是关键的。当拥塞发生时，组 播的拥塞控制算法必须具有对t c p 和其它组播的友好性。有许多组播拥塞控制 模仿t c p 的a i m d ，以获得t c p 友好性。 公平性的另外一个研究方向就是公平性的标准。使用的标准不同，在实现拥 塞控制的方案上也有所不同。带宽资源在分配中，使得各个相互竞争的接收者的 最小吞吐变得最大化。如果所有接收者的带宽的增加都不是以剥削与之带宽相等 或者更小的接收者为代价的。有界公平性( b o u n d e df a i r n e s s ) 定义了一种组播的公 平分配，该分配满足不等式a r r t t 鱼 占卜 妒z 蠢a 2 瓮 公式( 3 7 ) 公式( 3 8 ) 其中，乃= ( 删2 ，y 为单个采样周期网络流量实际值，矿为单个采样周 期根据采样所估计的网络流量，切，s ) 为预设的误差水平，网络流量估计误差水平的默认设 置值为 0 1 ，0 1 ) 。 现在具体分析自回归模型中参数的求解，利用公式( 3 3 ) ，在第k 1 个采样 周期预测第k 个周期的s c v 为：盅= 口，5 s ；一， i = l 1 4 根据文献可知，较小的u 预测效果较好( “= 1 ) ，也就是1 阶的自回归模 型。根据文献得出，口? 可以通过v 个历史采样值的最小二乘法求解，v 通常定 义为自回归的内存大小( m e m o r ys i z e ) 。 利用统计学回归模型参数求解的的最小二乘法【2 0 1 ，口j 的具体求解表达式为： k f s 声，+ ； 口；= 气孚一 s ；s ； j = k - i - v 公式( 3 9 ) 所以，关键是要确定公式( 3 9 ) 中y 的大小。 使用表3 1 的数据进行实验，具体分析当v 取不同的值时，比较s c v 和分组 数的预测效果。定义s c v 预测的平均相对误差为： 瞵一s 。 占= 上生一 h s 。 公式( 3 1 0 ) 其中七，k = 1 ，刀，为采样周期，刀为总的采样周期，s 。为第k 个采样周期实 际的s c v ，：为第k 个采样周期预测的s c v 。 如图3 2 所示，v 的取值大于等于5 时，s c v 预测效果较好，但为了减少预 测的时间和内存开销，所以建议v 的取值为5 左右。 另外，如图3 - 4 ( a ) 所示，给出当自回归模型中的v 取不同的值时，a u c k l a n d i i 1 9 9 9 1 2 0 1 1 9 2 5 4 8 0 的s c v 实际值和预测值的比较曲线。 拿 菊唿 嗒。 靛 霹n 8 霸 牛n * o n 住 o n o ( a ) a u c k l a n d i i1 9 9 9 1 2 0 1 - 1 9 2 5 4 8 0( b ) b e l ll a b s i 一2 0 0 2 0 5 1 9 1 0 0 0 0 0 图3 2s c v 的平均相对误差 1 5 嘧 吻 嘴 呲 叫 旧 哺 咄 (一荆苔霄罂霸牛 类似s c v 的分析，进一步可以分析当v 的取值不同时，比较分组数目预测 的平均相对误差。分组数目预测的平均相对误差定义为： 阮一脚。l 占= 三型一 月 m 。厶”t 公式( 3 1 1 ) 其中后，k = 1 ，甩，为采样周期，刀为总的采样周期，m 。为第k 个采样周期实 际的分组数目，帆为第k 个采样周期预测的分组数目。 ( a ) a u c k l a n d - i i1 9 9 9 1 2 0 l 1 9 2 5 4 8 - o( b ) b e l ll a b s i - 2 0 0 2 0 5 1 9 1 0 0 0 0 0 图3 3 分组数的平均相对误差 如图3 3 所示，v 的取值大于等于5 时，分组数目预测效果较好，但为了减 少预测的时间和内存开销，所以建议v 的取值为5 。 同样，如图3 4 ( b ) 所示，也给出当自回归模型中的v 取不同的值时， a u c k l a n d i i1 9 9 9 1 2 0 1 1 9 2 5 4 8 0 的分组数目实际值和预测值的比较曲线。 现在进一步分析当预测s c v 和分组数的自回归模型中的v 取不同的值时， 利用公式( 3 8 ) 的结果进行采样，比较a u c k l a n d i i1 9 9 9 1 2 0 1 1 9 2 5 4 8 0 的实际分组 采样。由图3 5 和图3 - 6 可以看出，v 的取值大于等于5 时，实际平均分组采样 数较少，可以取得较优的分组采样概率。 1 6 1 4 0 0 1 2 0 0 赫 鼎1 0 0 0 鑫e o o 米6 0 0 4 0 0 2 0 0 o 采样周期(单位：30 0s ) ( a ) s c v 采样周期( 单位：3 0 0 s ) ( b ) 分组数 图3 - 4s c v 和分组数实际值和预测值比较 采样周期( 单位：3 0 0 s ) 图3 5 实际分组采样数 1 7 5 o 5 o 5 o 5 o 5 o 5 o 5 o 5 o 5 o 5 0 7 7 5 6 5 5 3 3 2 2 1 1 o o o o o o o o o o o o o o o o o o o o o o o o o o d o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 0 6 2 o 8 8 4 2 o 8 6 4 2 2 2 2 2 2 2 ，1 1， 豢寤求 3 2 2 网络流量分析和估计 图3 _ 6 实际平均分组采样数 最后，根据预测的s c v 和分组数，利用公式( 2 8 ) 的结果进行采样，分析网 络流量估计的效果。图3 7 和表3 2 分别表示在每个采样周期，网络流量估计的 误差，以及各个数据源流量估计实际误差水平。计算各个数据源网络流量实际估 计误差和实际误差水平的公式分别定义为： 善= 引 一m i r 2 。 公式( 3 1 2 ) 公式( 3 1 3 ) 舯一t 为满足l 字l 占的采样月期爪数衲总的采样周期数。 图3 - 7a u c k l a n d 1 i1 9 9 9 1 2 0 7 - 1 2 5 0 1 9 0 网络流量估计误差( w 5 ) 1 8 表 数据源采样周期数 7 7 n i 1 8 80 1 2 7 6 6 0 兀29 30 0 7 5 2 6 9 n 38 30 1 0 8 4 3 4 兀2 0 10 1 0 4 4 7 8 f 】， 2 5 90 0 5 7 9 15 s = 0 1 ) 由图3 7 和表3 2 可以看出，采样结果能较好地保证预设的网络流量估计的 误差水平，可以获得较好的估计精度。 所以，综合考虑两个网络流量参数的预测效果以及它们对确定高效的采用概 率的重要作用，和网络流量估计效果，以及减少预测的时间和内存开销，建议 s c v 和分组数目预测的自回归模型中的v 取5 。 3 3 组播网络流量预测仿真实验 根据文献【1 5 】可知，较小的甜在网络流量预测时预测效果较好，所以本文在 预测时采用1 阶的自回归模型，即u = l 。根据文献【1 刀得出，a i 可以通过，个历史 采样值的最小二乘法求解，v 通常定义为自回归的内存大小( m e m o r ys i z e ) 。 利用统计学回归模型参数求解的的最小二乘法【1 7 1 ，模型a 中a ，的具体求解 表达式为： k - i e s x s p l j = i t j v q2 上i 一 s s j = 七一，一v 公式( 3 1 4 ) 对于模型b 而言，应该将公式( 3 4 ) 中s j 换为甜。 在a ，的计算中，关键是确定预测规模参数v 的大小。使用表3 1 的数据进行 实验，具体分析当1 ，取不同的值时，模型a 和模型b 的网络流量的预测效果。 为了有效评价网络预测的效果，采用相对累计预测误差，即 陬- s 。 s = 鱼蔓一 & 1 9 公式( 3 1 5 ) 其中，k 为采样周期，肛l ，刀，行为总的采样周期数。 图3 8 给出了四组网络流量数据下依据模型a 进行的网络流量预测的相对累 计预测误差情况。从图3 8 可以看出，在四组数据中当1 ，的取值大于等于1 0 时， 网络流量预测效果较好，能很好地保证预设的预测误差水平，但为了减少预测的 时间和内存开销，所以建议_ i ，的取值为l o 左右，而且在实际应用中可以根据当 时预测效果动态调整1 ，的取值。为了更加直观地观察网络流量预测情况，图3 - 9 给出了模型a 中的v 取不同的值时，a u c k l a n d i i1 9 9 9 1 2 0 1 1 9 2 5 4 8 0 的网络流量 实际值和预测值的比较曲线。从图3 - 9 可以看出，当v = 1 0 时，网络的预测值和 网络流量的实际值十分接近。 1 。磊湍”。” 1 。? ，；? 。” ( a ) a u c k l a n d - i i1 9 9 9 1 2 0 1 1 9 2 5 4 8 - 0( b ) a u c k l a n d i i1 9 9 9 1 2 0 7 1 2 5 0 1 9 - 0 脚01 0 卫柚- 恤 o m 口蕾重自1 0 _ 口坩 历史值协历史懂恤 ( c ) a u c k l a n d i i1 9 9 9 11 2 9 1 3 4 2 5 8 0( d ) n z i x - i i 2 0 0 0 0 7 0 5 - 1 5 2 9 0 0 图3 8 网络流量估计的相对累计预测误差( 模型a ) 番锄- 嫩位俩 ( a ) a u c k l a n d 1 11 9 9 9 1 2 0 1 - 1 9 2 5 4 8 - 0( b ) a u c k l a n d 一1 11 9 9 9 1 2 0 7 - 1 2 5 0 1 9 - 0 ( c ) a u c k l a n d - i i1 9 9 9 11 2 9 一1 3 4 2 5 8 加( d ) n z i x i i - 2 0 0 0 0 7 0 5 - 1 5 2 9 0 0 图3 - 9 网络流量估计的相对累计预测误差( 模型b ) 图3 - 9 给出了四组网络流量数据下依据模型b 进行的网络流量预测的相对累 计预测误差情况。从图3 - 9 可以看出，在四组数据中当v 的取值大于等于2 0 时， 网络流量预测效果较好。同时，模型b 如果要取得模型a 同样的预测精度，v 的取值要大得多，这主要是由于在模型b 中预测依据的是采样估计值，本身存 在误差。图3 1 1 给出了模型b 中的1 ，取不同的值时，a u c k l a n d 。i i 1 9 9 9 1 2 0 1 1 9 2 5 4 8 0 的网络流量实际值和预测值的比较曲线。从图3 1 1 可以看出， 当v = 2 0 时，网络的预测值和网络流量的实际值比较接近。 为： 图3 1 0 模型a 网络流量预测图3 1 1 模型b 网络流餐预测 最后，分析各个数据源网络流量预测实际误差水平。误差水平7 7 的计算公式 ，7 ：生 m 公式( 3 1 6 ) 其中m 为满足表达式l 字i 占的采样周期个数，研为总的采样周期数。 表3 - 2 5 俣：鬯a 误寿水半s = 0 1 5 ，v 数据源采样周期数 7 7 兀i 1 8 8 0 0 2 6 5 9 6 几2 9 3o 1 0 0 5 3 8 兀38 3 0 0 6 0 2 41 兀42 0 l0 0 2 6 5 9 6 1 0 ) 表3 - 4 模型b 误差水平( f = 0 1 5 ，v = 2 0 ) 数据源 采样周期数刀 兀 1 8 80 0 5 3 1 9 l 兀29 30 1 2 4 2 1 6 兀38 3 0 1 0 8 4 3 4 兀d2 0 l 0 0 2 9 8 5 l 表3 3 给出了依据模型a 进行预测时的网络流量预测误差水平，从表3 3 可 以看出预测误差小于1 5 的概率一般都大于0 9 ，采用数据源兀时，预测误差小 于1 5 的概率大于o 9 7 。表3 4 给出了依据模型b 进行预测时的网络流量预测误 差水平，从表3 4 可以看出预测误差小于1 5 的概率一般在0 9 左右，采用数据 源i - i 时，预测误差小于1 5 的概率大于o 9 4 。同时，对相同数据源进行预测分 析时，模型a 的误差水平都小于模型b 。 3 4 小结 流量测罱和预测，是网络q o s 管理和流量工程任务的重要基础，尤其是小 时间粒度的网络流量预测能很好地用于这种以秒级为单位的接纳控制、资源预留 等q o s 方法。具体分析了针对小时问粒度网络流量自相似特性，并根据两种不 同的网络采样结果提出了自回归预测模型，分析了具体的自回归预测模型的最小 二乘法参数求解，并通过分析真实网络流量数据，分别比较了两种预测模型的预 测效果和实际误差水平，从而得出了最小二乘法中参数1 ，的取值建议，对于在网 络流量预测中真正应用该模型提供了重要依据。本章的进一步研究工作可以研究 网络流量预测对于接纳控制，资源预留等方法的实际应用价值，更好地保证网络 q o s ，提高网络资源利用效率，减少网络拥塞的概率。 第四章一种多速率分层组播网络的分组标记公平算法 本章提出一种改进r l m 的分组标记公平算法f a t m ( f a i ra g g r e g a t et r a f f i c m a r k e r ) ，较好的解决了在组播网络拥塞控制中，由于r l m 收敛情况下的r t t ( r o u n d t r i pt i m e ) 收敛时间长，可能会导致对t c p 的不公平性和友好行问题。 因此，从而保证了网络流量的公平性，减少了组播网络拥塞。 4 1 一种改进r l m 算法一分组标记公平算法f a t m 一种基于聚集流内部公平性聚集流标记算法( f a i ra g g r e g a t et r a f f i cm a r k e r ， f a 刑) 。f a t m 在保证聚集流之间的公平性基础上，提高了聚集流内部单个流 之间的公平性。 在同一个聚集流中可能包含不同类型的单个流，比如同时存在自适应t c p 流 和非适应u d p 流、不同速率的多媒体u d p 流、采用不同t c p 协议的数据流以及不 同分组大小的数据流，因此即使保证了聚集流之间的公平性仍然无法保证聚集流 内部单个流的公平性，研究如何在保证聚集流之间公平性的基础上提高聚集流内 部单个流之间的公平性是本章的主要工作。 r l m 是在分层组播方端到端的、基于接收端的速率控制算法，能较好地解 决组播异构性。r l m 允许接收端根据它们自己的接收能力选择自己能接收的视 频质量。在r l m 中，首先通过分层编码把视频信号划分成多个层，其中最低层 包含视频信号最基本的信息，接着的每个层都是最低层的视频质量的逐步提高， 接着源端用独立的组播组发送各层，接收端则根据其接收能力的强弱和网络为其 提供的带宽来加入层。每个接收端都试图达到其所能订阅的最优层，订阅的最优 层即接收端在所提供的链路带宽的限制下能加入的最大层。r l m 的基本调节控 制机制如下：当接收端检测到拥塞，则离开新近加入的最高层，而当其发现还有 可用带宽，则加入一个更高层。 r l m 没有考虑t c p 友好性，缺乏公平机制，通过判断丢包来加入或退出一个 层次的机制可能导致当前r l m 各个组播组之间带宽分配的不公平。另外这个算 法也没有考虑接收端之间加入离开的同步机制，在遇到普通瓶颈时，协调接收 端及时加入或离开的步调是非常关键的，如果只有一些接收端离开一个层次而其 他仍处在该层，那么剪枝是不可能的，拥塞状况也不能被减轻。因此共享同一瓶 颈链路的接收端应该在加入或离开某层的步调上保持一致性。另外加入试验的失 败可能增加其他接收端的拥塞。 4 1 1 分组标记算法改进 分组标记算法的核心就是：首先测量聚集流跟服务规格s l a 是否一致，低于 服务规格的聚集流分组将会被标记成低丢弃优先级，在核心将会受到高等级的服 务；高于服务规格的聚集流分组将会被标记成高丢弃优先级，在核心将会受到低 等级的服务。基于测量聚集流跟服务规格是否一致的机制，可以将标记算法分为 两大类：基于令牌桶标记器和基于平均速率估计的标记器。 ( 1 ) 基于令牌桶的分组标记算法基于令牌桶的分组标记算法中，有一个或 者多个令牌桶来测量流的发送速率的。在这种机制中，每个流过标记器的分组都 会消耗一定量的令牌。例如，在一个简单的单令牌桶标记器中，每当有一个分组 达到时，如果在令牌桶中还剩余有令牌的话则这个分组被标记为i n p r o f i l e ，否则 标记成o u t p r o f i l e 。基于令牌桶的标记器就是这样根据令牌桶中是否有剩余的令 牌来确定分组应该怎么样被标记。在对公平性进行研究时，有两种基于令牌桶的 标记算法是值得注意和研究的。他们就是j h e i n a n e n 教授等人提出的单速三色 标记算法【3 7 】和双速三色标记算法【3 8 】，这两种算法的提出正是为了改进响应性流 ( 如t c p 流) 与非响应性流( 例如基于u d p 协议的c b r 流) 之间公平共享带 宽的问题的。他们两者的一个共同点就是：在两种标记器之中，都有两个令牌桶， 分别装着“绿色令牌”和“黄色令牌”；当一个分组到达标记器时，当“绿色令牌”和 “黄色令牌”均有剩余的时候，就把绿色令牌给分组，同时将分组标记为绿色；若 只剩下“黄色令牌”时，则把黄色令牌给分组，并将分组标记为黄色；否则将分组 标记为红色。 ( 2 ) 基于平均速率估计器的分组标记算法基于平均速率估计器的分组标记 算法在测量单流或者聚集流的到达速率的时候用到了一些平均速率估计算法，这 些平均速率估计算法中最常用的就是时间滑动窗口算法【3 6 1 。在这种算法中，到 达速率是根据在给定时间间隔内的到达速率的加权平均值来计算的。 标记算法都只考虑聚集流之间的公平性问题，而忽略了存在导致聚集流内部 单个流之间不公平的许多因素1 4 l 一2 1 ，主要包括： ( 1 ) 适应流和非适应流混合存在 当网络发生拥塞时，适应流( 比如t c p 流) 可能减少本身的发送速率，然而 缺少自动调节机制的非适应流( 比如u d p 流) 速率不变。因此网络拥塞导致适应 流速率下降，但是不影响非适应流速率，从而导致不公平带宽分配。 ( 2 ) 贪婪用户流的存在 传统标记算法基于聚集流到达速率标记分组，所以用户获得的带宽跟其发送 速率成正比。如果贪婪用户增加其发送速率，将会获得更多的带宽，从而导致不 2 4 公平标记。 ( 3 ) 不同t c p 协议的流 不同t c p 协议的流拥有不同水平的竞争带宽资源的能力。对于现有的聚集流 标记算法，t c pn e w r e n o 等强势协议将会获得更多的带宽，从而导致不公平性。 ( 4 ) 分组大小的变化 不同分组大小的流拥有不同水平的吞吐量能力。对于现有的聚集流标记算 法，大分组的流将会获得更多的带宽，从而导致不公平性。 对于这些聚集流内部的不公平因素，尤其是t c p 流之间、多媒体u d p 流之间 以及t c p 和u d p 流之间的公平性问题，已引起了很大的关注。对于p a m ，正如作 者所指出的，算法中的关键参数不容易配置；对于f s a m ，需要在源端估计单个 流的速率，而这个估计值可能跟流到达边缘路由器时的实际速率不一致，从而造 成公平速率，计算的不准确。文献脚】提出了一种标记算法t cp f g ，t cp f g 根 据最大最小公平性原则【4 9 j 对单个流的分组提高或者降低其被标记成i n o u t 的概 率，以保证公平性。当c i r 令牌桶t c 的令牌数t n u mc 超过阀值而c 时，提高被标 记成烈的概率；相反当c i r 令牌桶t c 的令牌数t n u mc 低于阀值死c 或者p i r 令牌 桶t p 的令牌数t n u mp 低于阀值死p 时，提高被标记成o u t 的概率。然而，正如 作者所指出的，死c ，死藏茎些参数不容易配置，而且当提高i n 标记概率时，需 要对单个流的i n 分组数排序，这大大增加了算法的时间复杂度，另外标记算法需 要获得聚集流内部单个流的理想吞吐率，而在现在的d i f f s e r v 网络中不知道单个 流的理想吞吐率。基于t cp f g 标记算法文献【4 5 】提出了一种增强的聚集流标记算 法( e n h a n c e dt r a f f i cm a r k e r ，e t m ) ，在t cp f g 标记算法的基础上为p i r 令牌 桶t p 增加了一个最大剩余令牌数阀值乃尸，进一步增强了算法的灵活性，但进一 步增加了设置参数的复杂性。 4 1 2 分组标记算法的实现 为了在保证聚集流之间公平性的基础上提高聚集流内部单个流之间的公平 性，标记算法f a t m 对不同的流提供不同的标记概率函数，从而达到聚集流内部 单个流之间的公平性。f a t m 算法既利用了聚集流的c i r 信息来保持聚集流之间 的公平性，又利用了在边缘路由器维护单个流的速率信息来提高聚集流内部的公 平性。在f a t m 算法中，聚集流和聚集流单个流的速率估计都是基于t s w 算法。 在f a t m 算法中，当某个聚集流的平均速率低于服务规格c i r 时其数据包将标 记为i n 。而当其高于服务规格c i r 时，f a t m 算法对于那些弱势流将降低它们的 分组被标记成o u t 的概率，而提高那些强势流的分组被标记成o u t 的概率。 当聚集流的平均速率超过服务规格c i r 时，为了消除聚集流内部的不公平性， 如果单个流的速率没有超过c i r 胛，则将其分组标记成i n ；如果单个流的速率大 于c i r n ，而没有超过a v g r a t e n ，则当前分组以聚集流的平均速率超过c i r 的 值与聚集流的平均速率的比率的概率被标记成o u t ；如果单个流的速率大于 a v g r a t e 拧，则将其分组以p o = p 1 + ( p 2 ) m 的概率标记成o u t ( m 1 ) ，其中p l 为 聚集流的平均速率超过c i r 的值与聚集流的平均速率的比率，p 2 为在p 1 的标记概 率下如果当前分组没有被标记成o u t ，那么再以( 1 p 1 ) 乘上当前流的速率超过 聚集流的平均速率的值与当前流的速率的比率。 i f ( a v g - r a t e ：= c i r ) t h ep a c k e ti si n ； e l s e i fs i n g l e - r a t e _ c i r n t h ep a c k e ti si n ； e l s ei fs i n g l e r a t e ， a u g u s t2 0 0 0 【4 3 】a d a s ，d d u t t a ，a h e l m y “f a i rs t a t e l e s sa g g r e g a t em a r k i n gt e c h n i q u e s f o rd i f f e r e n t i a t e ds e r v i c e sn e t w o r k s ”i f i p i e e em 【n s ， 2 0 0 2 2 1 1 - 2 3 3 【4 4 】c h u n g - j uc h a n g ， y u n g h o n gc h e n g ，l i f o n gl i n ”t h e t r a f f i c c o n d i t i o n e rw i t hp r o m o t i o na n df a i r n e s sg u a r a n t e es c h e m e sf o rd i f f s e r vn e t w o r k s ” 3 9 硕士学位论文参考文献 i c c2 0 0 3 i e e ei n t e r n a t i o n a lc o n f e r e n c eo nc o m m u n i c m i o n s ，2 0 0 3 ， 2 6 ( 1 ) ：2 3 8 - 2 4 2 【4 5 】l i f o n gl i n ，n i n g - y o uy a n ，c h u n g j uc h a n g ，r a y g u a n gc h e n g a n e n h a n c e dt r a f f i cm a r k e rf o rd i f f s e r vn e t w o r k s ”i n ：c h e e h ak i m ，e d s i c o i n2 0 0 5 s p f i n g e v v e r l a gg m b h 4 3 2 - - 4 4 2 【4 6 】q i n g h u ax i a o ，l i n g d ip i n g ，x u e z e n gp a n “am o d i f i e df a i ra g g r e g a t e m a r k i n ga l g o r i t h mi nd i f l s e r v ”f i f t hw o r l dc o n g r e s so ni n t e l l i g e n tc o n t r o la n d a u t o m a t i o n ，2 0 0 4 w c i c a2 0 0 4 ，v 0 1 2 ， 1 4 8 4 - 1 4 8 8 【4 7 】c hk e ，c ks h i e h ，w sh w a n g ，az i v i a n i “at w om a r k e r ss y s t e mf o r i m p r o v e dm p e gv i d e od e l i v e r yi nad i f f s e r vn e t w o r k ”i e e ec o m m u n i c a t i o n s l e t t e r s ，2 0 0 5 ， 9 ( 4 ) ：3 8 1 3 8 3 4 8 】n e t w o r ks i m u l a t o r ( n s ) ，n s - 2 2 8 u n i v e r s i t yo fc a l i f o r n i aa tb e r k e l e y ， c a ， 2 0 0 5 a v a i l a b l e ：h t t p ：w w w i s i e d u n s n a m n s 【4 9 】r j a i n t h ea r to fc o m p u t e rs y s t e m sp e r f o r m a n c ea n a l y s i s j o h nw i l e y a n ds o n si n c ，2 0 0 1 5 0 】j a r i c e m a t h e m a t i c a ls t a t i s t i c sa n dd a t aa n a l y s i