（计算机科学与技术专业论文）面向区分服务的流控算法的研究.pdf

国防科学技术大学研究生院学位论文 摘要 流量控制就是通过控制网络流量，使数据传输速度与网络的处理能力相匹配。早期 的网络更注重的是连通性，不存在资源竞争的问题。随着网络规模的不断扩大，各种应 用层出不穷，应用对网络资源的需求已 经大大超出了网络所能提供的资源，这就需要对 网络流量进行有效的控制，防止网络的崩溃。近几年出现的i p 服务质量( q o s ) 问 题，也 需要有效的流量控制的支持。 流量控制不仅可以 避免网络拥塞， 还可以通过减小丢包率、 降低端到端延迟、提高吞吐量等支持服务质量，而且还可通过对不同业务实施不同的流 量控制机制来达到区分服务的目 的。 本文对基于网 络处理器的流量控制机制进行了深入的研究，在现有算法的基础上， 提出了一种基于稳定性理论的增强型流量控制算法 e - s a r e d ,通过进行算法模拟，对各 种算法的优缺点进行了较深入的比较分析，模拟结果表明了e - s a r e d 的有效性。 本文在对网络处理器和区分服务两项技术的分析的基础上， 与流量控制机制相结合， 提出了 一种基于网 络处理器的 面向 区分服务的 流量控制方法， 该方法引入了 管道的 概念， 可更高效的管理网络带宽。 本文对基于网络处理器的流量控制相关软件实现技术进行了研究， 在路由 器中实现 了流量工程和多协议标签交换两部分网络处理器软件。 关键词流量控制，主动队列管理，增强型减震吸收随机早期检测，网络处理器，多协 议标签交换，区分服务 国防科学技术大学研究生院学位论文 abs t ract f l o w c o n t r o l i s a w a y t o m a k e t h e n e t w o r k d a t a t r a n s m i s s i o n r a t e m a t c h w i t h i t s c a p a c i t y b y c o n t r o l i n g t h e t r a f f i c . m u c h a t t e n t i o n i s f o c u s e d o n t h e c o n n e c t i v i t y i n e a r l y n e t w o r k f o r t h e r e i s n o c o m p e t i t i o n f o r t h e r e s o u r c e s . wi t h t h e e x p a n s i o n o f t h e n e t w o r k s c a l e ,t h e n e e d o f t h e q u i c k l y i n c r e a s i n g a p p l i c a t i o n f o r t h e r e s o u r c e s h a s o v e rt o p e d t h e n e t w o r k c a p a c it y .t h e n e ff e c t i v e t r a f f ic c o n t r o l i s d e s i r e d t o p r e v e n t t h e c o l l a p s e o f t h e n e t w o r k . t h e n e w l y a r i s e n i p q o s p r o b l e m a l s o n e e d t h e s u p p o r t o f e ff e c t iv e fl o w c o n t r o l . f l o w c o n t r o l n o t o n l y c a n a v o i d t h e n e t w o r k c o n g e s t io n ,a n d s u p p o rt t h e q o s t h r o u g h i m p r o v i n g d r o p p i n g r a t e ,e n d to e n d d e l a y a n d t h r o u g h p u t , b u t a l s o c a n a c h i e v e d i ff e r e n t i a t e d s e r v i c e t h r o u g h e x p o s i n g d i ff e r e n t fl o w c o n t r o l me c h a n i s m o n d i f e r e n t t r a f f i c . t h e p a p e r a d d r e s s e s t h e i m p r o v e m e n t o f t h e e x i s t i n g fl o w c o n t r o l a l g o r i t h m t h r o u g h t h e d e e p r e s e a r c h i n t o t h e fl o w c o n t r o l m e c h a n i s m b a s e d o n n e t w o r k p r o c e s s o t a n e w a l g o r i t h m i s p r o p o s e d w h i c h i s a n e x t e n s i o n o f c u r r e n t a l g o r i t h m .t h e c o m p a r i s o n a n d a n a l y s i s o f d i ff e r e n t a l g o r i t h m t h r o u g h s i m u l a t i o n s h o w t h e e ff i c i e n c e o f e - s a r e d . w e p r o p o s e d a n e t w o r k b a s e d fl o w c o n t r o l m e th o d f o r d i ff e r e n t i a t e d s e r v i c e , w h i c h i n t r o d u c e s t h e c o n c e p t p f p i p e t o m a n a g e b a n d w i d t h a l l o c a t i o n m o r e e ff i c i e n t l y . t h e s o ft w a r e i m p l e m e n t a t i o n t e c h n o lo g y o f fl o w c o n t r o l i s s t u d i e d b a s e d o n p r o c e s s o r .t w o p a rt s o f fl o w c o n t r o l r e l a t e d s o ft w a r e a r e i m p l e m e n t e d i n n e t w o r k p r o c e s s o r b a s e d r o u t e r ,w h i c h a r e t r a f f i c e n g i n e e r a n d mp l s p r o t o c o l . k e y w o r d s fl o w c o n t r o l , e - s a r e d , n e t w o r k p r o c e s s o r , d i ff e r e n t i a t e d s e r v ic e , mp l s 页 独创性声明 本人声明 所呈交的学位论文 是我 本人在导师 指导下进行的 研究工作及取得 的 研究 成果 尽我 所知， 除了 文中 特 别加以 标注和致谢的 地方外， 论文中 不 包含 其 他人已 经 发表和 撰写 过的 研究成 果， 也不 包含为获 得国防 科学 技术大学 或其它 教育机构的学位或证书而使用过的 材料。 与我一同 工作的同志对本研究 所做的 任 何贡献均已 在论文中 作了 明 确的 说明 并表示 谢意. 学 位 论文 题目 : 面向区 分 服务的 流 控算 法的 研究 学位论文作者签名: 和i 一- 日 期 :; 。 ; 年 月 月门日 学位论文版权使用授权书 本人完 全了 解国防 科学技术大学 有关 保留 、 使 用学 位论文的 规 定. 本人授权 国防 科学技术大学可以 保留 并向国 家有关 部门 或机构送交论文的复印 件和电 子 文 档， 允许 论文 被查阅 和 借阅 ; 可以 将学 位论文的 全部或部分内 容编入有关 数据 库进行 检索， 可以 采用影印 、 缩印 或扫描等复制手段 保存、汇 编学位论文. ( 保密 学 位论文在解密 后适用本授权书. ) 学 位 论文 题目 : 面 向区 分 服 务 的 流 拉 算 法 的 研究 学位论文作者签名: 作者指导教师签名: 条 清 元 3 + 日 期 : i v , ; 年 ) ， 月i 丁 日 日 期 : 、 乡 年1 月 1 日 国防科学技术大学研究生院学位论文 图 目 录 再万乃l3l723242525262728292930384l444849505l52 1 . l in te m e t 上 t c p i ip 流 量 控 制. 卜，二 . 1 . 2 慢启动和拥塞避免 ( 不含快速重传和恢复) _ ， . . ， ， ，二 ，. . . 1 . 3 快速重传和恢复二 价. ， ， . _ ， - 一， ， ， ，一 甲 . .， ， ， 一. ， ， ， ， ，. . 2 . 1 丢弃概率与平均队列长度之间的函 数关系. . . . . . . . . . . . . . . ， ， . . 2 . 2 拥塞控制的逻辑模型. ， . . . . . . . . . . . . . ， . . . . . . . . ， ， . . . . . . . . 卜 2 . 3 非线性化的t c p 流量控制模型， ， . . . . . ， ， . ， . . . . . . 卜 二 ， . . . . . . . . . . . . 2 . 4 线 性 化的 流 量 控制 模型. 甲， ，】 一 “ 一 ” ” ” ” ” ” 一“ “ 2 . 5 简化的线性t c p 流量控制模型 . ， 卜 . . . . . . ， . . . . . 卜 卜 二 ， . . 2 . 6 加入主动队列管理机制的流量控制模型. . . . . . . . . . . . . ， . .， . 2了 稳定裕度. 卜 卜 。 . 卜 卜 . ， . ， 二 ， 二 ， ， . 卜 . . 卜 二 卜 . . . ， . 卜 卜 ， 卜 卜. . . . . . 2 . 8模 拟网 络 拓扑 结 构，. . . .， 一 二 . “ “ “ 2 . 9 n = 2 0 时的 三 种算法瞬时队 列长 度变化的 模拟结 果.。 . ，二卜 卜 二 ， ， ， . ， . 二 2 . 1 0 n = 1 5 0 时的三种算法瞬时队列长度变化的 模拟结果. . . . . . . . . . . . . ， . 2 . 1 1 n = 2 0 时的三种算法平均队列长度变化的 模拟结果 价 、. “ “ 、 2 . 1 2 n = 1 5 0 时的 三种算法平均队列长度变化的 模拟结果二 ， . . . . . 3 . 1 网络处理器的结构 ， . . . . . . ， . . . . . ， . . . . . . . . . . ， ， . . ，. ， . ， 3 . 2 常用的分组丢弃策略模型. ， ， ， . . . . . ， ， . . . . . . . ， ， 3 . 3 面向区分服务的流量控制方法 . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ， . . . . . . 一 4 . 1 基于网 络处理器的核心路由 器硬件结构示意图. . . . . . ， ， . . ， . .， 卜 4 . 2 基于网 络处理器的核心路由 器软件结构示意图. . . . ， . . . . . . . ， 4 . 3 n p f的软件模型 ， ， ，. ，. ， ， ， ， 、 . ， 二 ” . ， ， ， . . 、 ， ，- . . ， ， 价 . . 4 . 4 网络处理器软件， ， . . . . . . . . - . ， - ，4一， .， 4 . 5 面向区分服务的流量工程模型. . . . . . ， ， ， ， ， . ， . - 一 ， 4 . 6 流量工程软件结构. ” 二 ， . . ， . . . . ， . . . . . . . . . . . . . . . . . . . . . . . ， . ，. . 5 3 4 . 7 输入传输概率表的数据结构二 ， ， ， ， . . . . . . . ， 卜 ， . . 二， . ， . . 5 5 4 . 8 标签的格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ， . . . ， ， . . . . . 5 7 4 . 9 l s p 的建立. ， ， ， . . . . . . ， . . . ，. ， 二 ， . . . ， ， .， . . . ， 二 . 5 8 4 . 1 0 网络处理器中的m p l s 软件结构卜 ， ， . . . . . . . . . . . ， . . . . . . . . . . . . . . . . 5 8 4 . 1 1 实际硬件环境二 ， . ， . . . . . . . . . . . . . . . . . .卜. ， ， ， . . . - . . . . ， ， . . ， . . . . . . 6 2 4 . 1 2 m p l s 数据帧格式. . . . 二 ， ， . . ， . ， . . . . . . . . . . . . . . . . . . . . . . 二 ， ， ， ， 6 3 图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图 国防科学技术大学研究生院学位论文 表 目 录 表 2 . 1 表 2 . 2 表 3 . 1 表 32 流数量为2 0 时几种流控算法的性能比较 卜 . . . . . . . . . . . . . . . . 3 0 流数量为1 5 0 时几种流控算法的 性能比 较. ， . ” .， 卜 二， . ， ， ，一3 4 带宽分配示例表1 . . ， . ， . ， .， ， ， ， .， . ， . . 卜二 ， 卜 . . . 卜 ， . . . . . 4 3 带宽分配示例表2 . . . . . . . . . . ， ， ， . ， . . . ，. . . ， ， . 4 3 一m 万厂气薪一一一 国防科学技术大学研究生院学位论文 第一章 绪论 夸 l l课题研究背景 早期的网络建设中， 更多的注意力放在网络的连通性上，只要两点之间能够通过网 络 连接通讯， 就达到目的。并且当时的网络带宽只有i o m b p s ， 甚至还是共享的方式。 谈不上 服务质量保证的问题。但是随着 工 n t e r n e t规模的不断增大，各种各样的网络服务也争相 涌现，先进的多媒体系统层出不穷。由于实时业务对网络传输时延、延时抖动等特性较为 敏感，当网络上有突发性高的f t p或者含有图像文件的h t t p等业务时，实时业务就会受 到很大影响;另一方面，多媒体业务占去了大量的带宽，这样，现有网络要保证的关键业 务就难以得到可靠的传输，这就涉及到了网络流量的管理和控制的问题。 解决这些问 题的最简单的办法当 然是增大带宽，比 如从共享i o m b p s 到交换i o m b p s , l o o m b p s , 1 0 0 0 m b p s ， 甚 至i o g b p s以 太网 标 准 也已 经 完 成。但是， 由 手 这 种 方 法 代 价 高 昂， 所以并不十分可行。这就要求网 络管理者对不同的服务区别管理， 对网络流量进行有 效的控制， 而不能对所有的数据包一视同仁。 另一方面， 就是合理高效， 充分的利用带宽。 于是，网络的流量管理和控制也就应运而生。 目 前，在网络规划中存在三种高效的技术有助于网络流量的管理和控制，它们分别是 服务质量 ( q o s )、流控机制和组播技术。拥塞管理和避免机制是最终实现服务质量的手 段。 最简单地说， q o s 能够对数据包进行合理的排队， 对含有内容标识的数据包进行优化， 并对其中 特定的数据包赋以较高的优先级，从而加速传输的进程，并实现实时交互。由于 每种应用系统对网络的要求有所不同，这使得带宽本身并不能解决网络拥塞的问题。 q o s 所追求的传输质量在于:数据包不仅要到达其欲传输的目的地址，而且要保证数据包的顺 序性、完整性和实时性。通过 q o s ，网络可以按照业务量的类型或级别加以区分，并能够 依次对各级别进行处理。优秀的q o s 可以提供创建业务量级别的方法，把应用系统或用户 的邮件分配到某一级别中作系统管理。 传统的i p 只有一种服务类型，即尽力而为的 ( b e s t - e f f o r t ) 服务模型。以 前试图为 经典i p 增加q o s 的努力遇到了很多困 难， 这些困 难既包括技术上的可扩展性， 也有商业 上的不统一性以 及缺乏足够的应用等。 现在，事实己 经很清楚，具有时延和时延抖动约束 的 话音业务量将占 i s p ( i n t e r n e t s e r v i c e p r o v i d e r , i n t e r n e t服务提供商) 所提供业 国防科学技术人学研究生院学位论文 务的重要份额。此外，为了提供各种灵活的业务，i s p 必须能够提供不同的业务级别，并 可根据和用户达成的服务级别约定( s e r v i c e l e v e la g r e e m e n t ，s l a ) 传送具有不同带宽 要求和时延特性的客户数据。 i e t f 已经起草了很多有关保证q o s 的建议并标准化了很多服务模型和机制。以满足 q o s 的需求。其中比较有名的有：综合业务模型( i n t s e r v ) ，区分业务模型( d i f f s e r v ) ， 多协议标记交换( m p l s ) ，流量工程和约束路由。综合业务的特点是资源预留，实时应 用在传输数据前必须首先建立通道和预留资源。r s v p 是用来建立通道和预留资源的协议。 在区别型业务中，把包加以标记，产生不同的级别，每个级别的包得到不同的服务级别。 m p l s 是一种前向转发策略，在进入m p l s 作用域时给包赋予一定的标签，随后包的分类、 转发和服务都将基于标签完成。流量工程是一种安排通信流量如何通过网络的过程。约 束路由在寻径路由时会受到一定的约束，如带宽或时延的要求。 可以说，上述的任何一种方法都离不开流量控制。它通过对传输流进行控制，使其数 据传输速度与网络的处理能力相匹配，以避免网络拥塞。所以说，流量控制的首要目标就 是避免网络发生拥塞。如果将网络看作一个系统，那么流量控制就是根据网络状态的反馈 信息，动态地控制网络节点和通信主机的行为，使网络性能达到最优。随着计算机网络在 过去的十几年中的爆炸式增长，拥塞问题也越来越严重例如由于本地缓存溢出。i n t e r n e t 网关会丢弃约1 0 的数据包。据统计，i n t e r n e t 上9 5 ”1 的数据流使用的是t c p i p 协议。 i n t e r n e t 主要互连协议的t c p i p 的流量控制( c o n g e s t i o nc o n t r 0 1 ) 机制对控制拥塞具 有特别重要的意义。流量控制是确保i n t e r n e t 健壮性( r o b u s t n e s s ) 的关键因素，也是各 种管理控制机制和应用( 如多媒体通信中q o s 控制，区分服务d i f f e r e n t i a t e ds e r v i c e s ) 的基础，可以这样说，没有流量控制就不可能有今天i n t e r n e t 的飞速发展，也就不可能 有上层的各种应用。因此流量控制已经成为当前网络研究的一个热点问题。 1 2研究现状 对网络进行有效的流量控制是网络工程研究的一个基本方面。对网络流量所进行的测 量，建模分析，描述，最终都是为流量控制服务的，它对于提高网络的吞吐率，避免网络 拥塞具有很重要的作用。所谓拥塞就是在一段时间内对网络中某一资源的需求超过了它所 能提供的可用部分，此时，网络的吞吐量将随着输入负荷的增加而下降。拥塞出现的条 件可以表述为如下公式o ”： ( 对资源的需求) 可用资源 拥塞产生的直接原因有以下四点： 2 第页 。 国防科学技术人学研究生院学位论文 ( 1 ) 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个端1 ：3 就会建立排 队。如果没有足够的存储空间存储，数据包就会丢弃。对突发数据流更是如此。增加存储 空间在某种程度上可以缓解这一矛盾，但如果路由器有无限存储量时，拥塞只会变得更坏， 而不是更好，因为在网络旱数据包经过长时间排队完成转发时，它们早已超时，源端认为 它们已经被丢弃，而这些数据包还会继续向下一路由器转发，从而浪费网络资源，加重网 络拥塞。 ( 2 1 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论， 任何信道带宽最大值即信道容量c = b l o g ：( i + s n ) ( n 为信道白噪声的平均功率，s 为信源 的平均功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容量c 。如果r c ， 则在理论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其满 足不了通过它的所有源端带宽要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢也能引起拥塞。如果路由器的c p u 在执行排队缓存， 更新路由表等功能时，处理速度跟不上岛速链路，也会产生拥塞。 ( 4 ) 业务流没有被有效地分配到可用资源上，引起部分网络资源过度使用，而其它部 分却未充分使用。 拥塞一旦发生往往会形成一个不断加重过程。如果路由器没有空余的缓存，它就必须 丢弃新到的数据包。当数据包丢弃时，源端会超时、重传该包。由于没有得到确认，源端 只能保留数掘包，结果缓存会进一步消耗，加重拥塞。 从原理上讲，流量控制的目的就是使拥塞出现等式不再成立，即或增大网络可用资源， 或限制用户需求得以满足的程度。将网络看作一个系统，流量控制就是根据网络状态( 拥 塞情况) 的反馈信息，动态地控制网络节点和通信主机的行为，使网络性能达到最优。它 是一种基于反馈的控制机制。但是网络流量控制不能用传统的线性系统中的控制理论解决 一一因为网络是一个分布、动态、非线性的系统，很难用一个数学公式精确刻划，以求解。 流量控制分为两个层次，早期在i n t e m e t ( i p v 4 ) 实际使用的流量控制基本上是建立在 t c p 的窗口控制基础之上的。i p 层的路由器所起的作用比较小。不过现在在i p 层控制拥 塞的研究逐渐增多，已经形成了一个新的研究热点。图1 1 显示了t c p i p 在i m e m e t 上流 量控制的作用范围。 3 第页 国防科学技术大学研究生院学位论文 图1 i i n t e r n e t 上t c p h p 流量控制 可以看出，流量控制牵涉到网络节点又牵涉到通信主机。 对网络节点( 路由器) 的 流量控制和资源分配策略，主要是考虑排队策略，目的是决定在拥塞发生时，对于排队缓 冲区中的报文，发送哪些、丢弃哪些? 对主机而言，流量控制和资源分配主要解决向网络 发送数据包的速率。t c p i p 的流量控制与网络服务质量q o s 和区分服务区分服务是密切 相关的。q o s 实际上是通过对带宽、缓存等网络资源的管理与调度实现所传输数据流要求 的一系列服务请求，例如保证传输时延、抖动、丢失率和吞吐量等指标。流量控制的目胸 正是要采用合理的算法与机制确保网络不因传入数据流过大耗尽网络资源而导致崩溃 ( c o n g e s t i o nc o l l a p s e ) 。与传统的尽最大努力传输业务( b e s t e f f o r t ) 中遇到网络资源不足 就简单地丢弃数据包相比，q o s 对网络流量控制提出了更高的要求。从综合服务i n t s e r v 发 展来的区分服务区分服务更是离不开流量控制，以确保各服务类型得到应有的服务。 流量控制的主要内容以及需要解决的问题，在路由器方面，采取什么样的排队策略， 保证资源的高效和公平? 在主机方面，如何控制向网络发送数据的速率? 如何将路由器和 主机的流量控制策略综合起来，避免拥塞发生? 现有的流量控制机制分为t c p 流量控制和 i p 流量控制。下面分别介绍。 1 2 1t c p 基于窗口的端到端的流量控制机制 目前在i n t e r n e t ( i p v 4 ) 实际使用的流量控制基本上是建立在t c p 的窗口控制“1 基础之 上的。t c p 资源使用拥塞窗口来避免拥塞。新建t c p 会话时，根据缓慢启动机制将拥塞窗 口初始化为一个段。拥塞窗口指出了发送方在接收到确认前可以通过t c p 会话传输的最大 数据量。 当第一个分组得到确认以后，t c p 源将窗口大小增加到2 ，此时可以发送两个分组。 当掰个分组都得到确认后，窗1 ：3 大小将增加到4 。拥塞窗1 3 的大小按这种方式呈指数级增 长a 然而，窗口大小可能不是准确地按指数级增长，因为t c p 接收方不一定会对每一个分 组都进行确认，它通常使用延迟确认，每接收到两个分组发出一次确认。t c p 源的行为遵 第4酉 国防科学技术人学研究生院学何论文 循缓慢启动算法，缓慢启动算法以接收到对方确认的速率将分组发送到网络，这使得t c p 是白同步的。 在t c p 中，分组丢弃率是拥塞指示计，当t c p 源在预计的重传计时器超时( r t t ) 周 期内没能接收到确认时，它就认为发生了拥塞。在这种情况下，它将拥塞窗口的大小重置 为1 ，并且重新启动缓慢启动算法，同时将缓慢启动阀值( s s t h r e s h ，s l o ws t a r tt h r e s h o l d ) 减少到需要重传时的拥塞窗口大小的一般。t c p 会话建立后，s s t h r e s h 将被设为对方生命 的接收方窗口的大小或者默认值。 r t t 超时后，在窗口大小达到s s t h r e s h 之前，发送方一直遵循缓慢启动算法。然后， 窗口大小敬爱你跟呈线性增大，每收到一个确认，c w n d 增加1 。当窗口大小达到s s t h r e s h 后，窗口将缓慢增大，因为s s t h r e s h 为t c p 连接预计了带宽延迟。图1 2 和图1 3 描述 了t c p 缓慢启动算法的拥塞避免行为。上面所描述的是一个t c p 流量控制的基本过程，实 际上，为了克服其缺点，人们提出了很多t c p 的改进模型，如：t c pv e g a s ，t c pr e n o ， u a m , d c w n d l s s t h r e s h = c w n d l ，2 时间 图1 2 慢启动和拥塞避免( 不含快速重传和恢复) 1 2 2 i p 上的流量控制机制 图1 3 快速重传和恢复 5第页 一 国防科学技术人学研究生院学位论文 循缓慢启动算法，缓慢启动算法以接收到对方确认的速率将分组发送到网络，这使得 t c p 是自同步的。 在 t c p中，分组丢弃率是拥塞指示计，当 t c p源在预计的重传计时器超时 ( r t t )周 期内没能接收到确认时，它就认为发生了拥塞。在这种情况下，它将拥塞窗口的大小重置 为1 ， 并且重新启动缓慢启动算法， 同时 将缓慢启动阀 值( s s t h r e s h , s l o w s t a r t t h r e s h o l d ) 减少到需要重传时的拥塞窗口 大小的一般。t c p 会话建立后，s s t h r e s h 将被设为对方生命 的接收方窗口的大小或者默认值。 r t t 超时后， 在窗口 大小达到s s t h r e s h 之前，发送方一直遵循缓慢启动算法。然后， 窗口大小敬爱你跟呈线性增大， 每收到一个确认， c w n d 增加1 。当窗口大小达到s s t h r e s h 后，窗口 将缓慢增大，因为s s t h r e s h为t c p 连接预计了带宽延迟。图 1 . 2 和图 1 . 3 描述 了t c p 缓慢启动算法的拥塞避免行为。上面所描述的是一个t c p 流量控制的基本过程，实 际上， 为7克服其缺点， 人们提出了 很多t c p的改进模型， 如: t c p v e g a s , t c p r e n o , t c p t a h o e s s c, a c9 等。 z m w c wn dl 超时 超时 s s t l x e s h 二 wn d 1 1 2 拥塞避 贾1 己 时m 图 1 . 2 慢启动和拥塞避免 ( 不含快速重传和恢复) 口v n d 拥 塞 rf 免 和 快 速 熏 a 9 6 一 i产一一一一 国防科学技术大学研究生院学位论文 a q m能够通过确保到来的包几乎总是有可用的队列空间，从而阻止 “ 死锁”行为的发 生。也因为这个原因，a q m 能防止路由器对低带宽高突发的流的偏见。常见的r e d , w r e d , a r e d 等都是属于主动队列管理算法。 1 . 3本文的主要工作 本文以国家8 6 3 计划重点项目“ 新一代互联网技术实验装置”为背景，在作者参与核 心路由器研制的基础上， 对i p 层的流量控制机制进行了深入的研究。 主要完成了以下工作: ( 1 )通过对几种常用的主动队列管理机制进行研究，提出了一种增强型的流量控制算法 e - s a r e d ， 该算法可根据网 络流量 特性对队列占 有率阀 值和最大输出 输入带宽比 两个 重要参数进行动态调整， 通过对其性能进行模拟分析， 表明该算法可有效提高系统性 能。 ( 2 )提出了 一种基于网 络处理器的区分服务流量控制方法， 该方法引入管道概念， 提供支 持区分服务的流量控制，可更高效地管理网络带宽分配。 ( 3 )对基于网 络处理器的 流量控制相关软件技术进行了 研究， 在路由 器中实现了 流量工程 与m p l s 协议两部分网 络处理器软件，并进行了功能测试。 1 .4本文的组织结构 第一章，主要介绍课题的研究背景、研究现状和本文的主要工作。 第二章， 对几种主动队列管理算法进行了分析比较， 提出了一种增强型的流量控制算 法e - s a r e d ， 给出了 分析与 模拟结果。 第三章，提出了一种基于网络处理器的区分服务流控方法，并对其进行了 分析。 第四章， 对基于网络处理器的流量控制相关软件技术进行了 研究，介绍了流量工程与 m p l s 协议两部分网 络处理器软件的实现技术。 第五章， 对本文的工作进行总结，提出下一步的研究内容。 1 . 5本文的研究成果 本文对i p 层的流量控制算法进行了深入的研究和分析， 提出了增强型的流量控制算法 e s a r e d ， 通过模拟， 对各种算法的性能进行了比较; 提出了一种区分服务流量控制方法， 该方法可以高效管理网络带宽; 最后， 对网络处理器中流控相关软件的实现技术进行了 研 究。以 第一作者在 计算机工程发表论文一篇 ( 见附录) 。 国防科学技术大学研究生院学位论文 第二章 基于控制论的流量控制算法研究 2 . 1需求背景 网 络交 换设 备在不断提 升业务 质量 ( q o s ) 等 级的同 时， 还需要 对庞大的 数据 和 流量 类型 进行处理。 为满足q o s 要求， 网络设计人员必须在网络交换设备设计中实 施高级流量控制， 以更好地管理资源并解决流量拥塞问题。 拥塞控制是流量控制的一项基本功能，控制拥塞的最佳途径是使网络工作于最大负载 容量之下。由于这种策略并不现实，通常以芯片形式出现的嵌入式流量控制功能必须对资 源进行管理，并决策何时丢弃数据包， 丢弃哪个数据包，并使这些操作对整个网络的影响 最小。 有效的流量控制包含三个关键要素: 拥塞避免: 为端对端传送的数据流预设路径; 对 流 量 调 整 进 行 公 平 排 序以 确 保 传 送的 延 时 有 界 。 如 果 不 能 实 现 王 述 三 大 功 能 ， 那 么 即 便 能 在 数 据网 络中 实 现q o s ， 也 是异常困 难的。 拥 塞 避 免 非 常 重 要， 因 为网 络的 功 率 ( 定 义为 数 据 流量 与 延时 之比 ) 经 过一 定的 流 量 负 载后将显著下降。由 于难以 拥塞中 恢复过来，因此最好从一开始就避免这种情形。 在t c p 层 上， 存 在 许多 拥塞 控制 反 馈机 制。 早 期随 机 检 测 ( r e d ) 拥 塞 控制 算 法 通 过允 许 路由 器 丢 弃数据包以 避免拥塞，它发挥了重要的作用。 有效的流量控制还要求设计人员 通过网络建立预置路径.如果没有这些预置路径，数 据包将在两个端点之间选择另一条路由，而且除非所有的路由均能满足特定的延时界限， 否则结果将无法得到保障。 一旦预置路径建立成功，则需要公平排序。现已证明，具有最大分段尺寸和平均有界 速率的信号流的公平排队可为有界延时提供保障。公平排队为一个数据流保障了最小带 宽， 其余的带宽则平均分配给其他数据流。因此，公平排队是一个能为每个用户保障承约 速率的高效机制， 其峰值速率根据可利用的额外带宽而得到满足。显然， 如果信号源经过 调整，使其限制在平均传送速率且不进行无限制分段， 那么公平排队将在受控信号流的传 输中实现公平和有界延时。 山以上可以 看出，拥塞避免是流量控制的一个基本方面。 t c p 基于窗口 的 端到端的 流量控制对于i n t e rn e t 的稳定性起到了 关键性作用。 然而， 随着i n t e rn e t 的 迅速发展， 其网络规模越来越庞大，结构日 趋复杂， 仅仅依靠端到端的流 国防科学技术大学研究生院学位论文 量控制是不够的。另外，t c p 流量控制的效率和公平性问 题目 前也受到了 广泛的关注。 1 .效率 网络资源的使用效率是由源端要求的总资源与网络资源的接近程度决定的。如果源端 总资源接近或等于网络所能提供的资源，那么这种算法的效率就是高的。超载或负载不足 都是效率不高的表现。显然，效率只与总资源的利用率有关，而与各个源端之间的资源利 用无关。 2 .公平性 公平性是在发生拥塞时各源端 ( 或同一源端建立的不同t c p 连接或u d p 数据报)能 公平地共享同一网络资源 ( 如带宽、缓存等) .处于相同级别的源端应该得到相同数量的 网络资源。产生公平性的根本原因在于拥塞发生必然导致数据包丢失， 而数据包丢失会导 致各数据流之间为争抢有限的网络资源发生竞争，争抢能力弱的数据流将受到更多损害。 因此， 没有拥塞，也就没有公平性问 题。 t c p 层上的公平性问题表现在两方面: ( 1 ) 面向 连接的t c p 和无连接的u d p 在 拥 塞发生时 对拥塞指示的 不同 反 应和处 理， 导致对网络资源的不公平使用问题。 在拥塞发生时， 有流量控制反应机制的t c p 数据流会 按流量控制步骤进入拥塞避免阶段， 从而主动减小发送入网 络的数据量。 但对无连接的 数 据报u d p ，由于没有端到端的拥塞控制机制，即使网络发出了拥塞指示 ( 如数据包丢失、 收到重复a c k等) ， u d p 也不会像t c p 那样减少向网 络发送的数据量。结果遵守 拥塞控 制的t c p 数据流得到的网络资源越来越少， 没有拥塞控制的u d p 则会得到越来越多的网 络资源，这就导致了网络资源在各源端分配的严重不公平。 网 络资源分配的不公平反过来会加重拥塞，甚至可能导致拥塞崩溃。因此如何判断在 拥塞发生时各个数据流是否严格遵守t c p 拥塞控制， 以及如何“ 惩罚” 不遵守拥塞控制协议 的行为， 成了目 前研究拥塞控制的一个热点。在传输层解决拥塞控制的公平性问题的根本 方法是全面使用端到端的拥塞控制机制。目 前， 判断拥塞时不遵守拥塞控制的数据流的几 种方法如下: 如果数据流遵守t c p 拥塞控制方式， 那么在拥塞发生时，作为响应， 它首先应将 拥塞窗口c w n d 减半， 然后 在每个r t t内 按常 数 速率 增加c w n d 。 给定 包 丢失 率p ,t c p 连 接的 最大传 送速率为t b y t e / s , b 为一 个数据包的 最大字节 数， r 为最小r t t 。 当 某 数 据流 的发送速率大于t时， 则可断定该数据流没有执行拥塞控制。 这一公式主要应用于没有突 发级数据包丢失的情况。 实际使用中以 大于1 .4 5 b / ( r ) 判定数据流没有执行拥塞控制， 以 小 于1 .2 2 b / ( r ) 为解除对该数据流“ 惩罚 ， 的 条件。 一一一 第9页 国防科学技术大学研究生院学位论文 通过判断网络中占据高带宽的数据流是否对拥塞指示进行响应来决定其是否执行 拥塞控制，也就是随着网络包丢失率的增加，其传送速率应相应降低。 如果包丢失率p 增加x ，则源端的发送速率应大致减少。 例如，如果包丢失率增加4 倍， 那么发送速率应减少2 倍。正是根据这一关系，通过检测数据流对包丢失率的反应， 就可以 大致判断该流是否执行了 拥塞控制。 对有o n / o f f 特性的数据源和接收者经常变动 的多点广播 ( m u lt ic as t )方式，由于传送速率本身经常变化，所以 这种判断方法在以上两 种情况下并不理想。 ( 2 ) 一些t c p连接之间也存在公平性问 题。 产生问 题的原因在于一些t c p在拥塞前 使用了大窗口尺寸，或者它们的r t t较小， 或者数据包比其他t c p大，这样它们也会多 占带宽。 总之， 在i n t e rn e t 这样复杂的异构系统中， 不能指望所有用户在i n t e r n e t 应用中兼容这 种端到端的拥塞控制。网络现在必须参与资源的控制工作。 由 于带宽、缓存等资源相对需求日 益缺乏，因此 i n t e rn e t 还会继续拥塞。这种情况导 致了几种解决拥塞的方法: 第一种方法是继续改进已有的端到端拥塞控制，并将其作为 i n t e rn e t 上的主要拥塞控 制机制。 第二种方法是利用价格等经济因素，限制用户对网络资源的需求，阻止拥塞的发生。 因此， 要建立网络收费新模型，用经济学理论分析具有拥塞特性网络资源的计费问 题。 第三种方法是在路由器中采用包调度算法和缓存管理技术，也就是这里要讨论的 i p 拥塞控制策略。 2 .2流量控制算法的研究与分析 2 .2 . 1 尾丢弃 传统上，当队列达到最大长度时， 到达队列的分组将被丢弃，丢弃行为一直持续到队 列由于 分组被传输而减小，这种队 列管理技术叫做尾丢弃( t a i l - d r o p ) . 虽然这个方法在当前工 n t e r n e t 上得到了 广泛的使用，但其存在几个重大缺陷: ( 1 ) 死锁 ( l o c k - o u t )问题: 在某些 情况下， 去尾 算法会让某个流或者少数几个流 独占队列空间，阻止其他流的包进入队列。这种“ 死锁 现象通常是由于同步 ( s y n c h r o n i z a t i o n ) 或其他定时 作 用的 结 果. ( 2 ) 满队列( f u l l q u e u e s ) 问 题: 由 于” 去尾” 算法只有在队列满时 才会发出 拥塞信号， 国防科学技术人学研究生院学位论文 因此会使得队列在相当长时间内处于充满 ( 或几乎充满)的 状态。而队列管理最重要的目 标之一就是降低稳定状态下队列的长度，因为端到端的延迟主要就是由于在队列中排队等 待造成的。 ( 3 ) 全局同步 ( g l o b a l s y n c h r o n i z a t i o n )问题:由于i n