（通信与信息系统专业论文）基于linux系统拥塞控制技术的研究与实现.pdf

y5 8 6 3 8 7 北京交通人学硕 学位论文 摘要 随着i n t e rn e t 的飞速发展，多种新业务尤其是实时业务的 推出， 人们对网络的服务质量也提出了更多的要求， 但另外一 方面，i p网络尽力而为的服务方式，以及网络中普遍存在着 的网络拥塞问题，使当前的网络不能很好适应业务发展的需 求。 对于拥塞问题的解决， 由网络节点主动对网络状况实施监 视， 采取某种策略， 减少和避免网络拥塞， 是目前网络技术研 究的一个重要课题，也取得了一些可喜的成果。 本文的研究工作是国家自 然科学基金项目 “ 业务内区分服 务和个性化拥塞控制” 的一小部分， 主要是借助于l i n u x 这个 开放的系统平台， 利用其源代码的公开性以及良好的网络支持 特性， 从协议实现的角度研究该系统在实现网络拥塞控制所采 用的技术， 分析其实现的方式， 并在这些研究的基础上， 增加 一些新的控制机制，验证其性能。 本文通过对l i n u x 系统网络接口的分析和内核队列管理机 制的研究， 分析了其支持的排队规则在内核中的实现方式， 明 确了其对数据包排队操作和调度的基本方法和主要流程。 并在 此基础上，比较深入的对系统缺省的排队规则 p f i f o做了重 点的分析。 未经作 者、 导师同惫 勿全文公布 北京交通大学硕士学位论文 分析研究的目的是为了实现新的算法，本文在对l i n u x 系 统原有排队规则的基础上， 通过编程实现了垃圾桶算法， 同时 改写了原有的客户端调用程序 t c ，使该算法能在内核中与其 他算法一起正常运作，同时对该算法的性能做了尝试性的探 讨， 为搭建实际网络平台， 验证新算法， 做了一个很好的准备。 关键词:服务质量 网络拥塞 队列管理 排队规则 北京交通大学硕士学位论文 ab s t r a c t a s t h e i n t e rn e t f a s t d e v e l o p m e n t a n d m o r e a n d m o r e n e w s e r v i c e s , e s p e c i a l ly s o m e r e a l t i m e s e r v i c e s , a r e w i d e l y u s e d i n i n t e r n e t , p e o p l e a s k f o r g o o d q u a l i t y o f t h e s e n e w n e t w o r k s e r v i c e s . h o w e v e r , t h e b e s t e ff o r t s e r v i c e m o d e l a n d u b i q u i t o u s n e t w o r k c o n g e s t i o n p r o b l e m m a d e it d i ff i c u l t t o m e e t t h e s e n e w s e r v i c e s n e e d . i t i s a n i m p o r t a n t r e s e a r c h d i r e c t i o n t h a t t h e n e t w o r k n o d e i n s p e c t s t h e n e t w o r k a n d r u n s o m e p o l i c y t o d e c r e a s e o r a v o i d n e t w o r k c o n g e s t i o n o n t h i s n e t w o r k p r o b le m a n d s o m e g o o d r e s u l t s h a v e b e e n a c h i e v e d . t h e r e s e a r c h i n t h i s t h e s i s i s a p a r t o f t h e n a t i o n a l n a t u r a l s c i e n c e f o u n d a t i o n p r o j e c t t h e s t u d y o f i 3 i ff e r e n t e d s e r v i c e a n d p e r s o n a l c o n g e s t i o n c o n t r o l t e c h n o l o g y . w e u s e t h e l i n u x o p e r a t i n g s y s t e m , f o r i t s o p e n i n g i n k e rn e l a n d g o o d n e t w o r k p r o p e r t y , s t u d y i t s c o n g e s t i o n c o n t r o l t e c h n o l o g y f r o m t h e v i e w o f p r o t o c o l r e a li z a t i o n . w e a n a l y z e t h e w a y i t w o r k s a n d a t t e m p t t o a d d s o me n e w c o n t r o l me c h a n i s m t o t h e k e rne l b a s e d o n t h e a n a l y s i s a n d t e s t o f i t s p e r f o r ma n c e . t h e n e t w o r k i n t e r f a c e a n d q u e u e m a n a g e m e n t t e c h n o l o g y i n l i n u x k e rn e l a r e i n v e s t ig a t e d . w e a n a l y z e t h e q u e u e d i s c i p l i n e i n t h e k e rn e l a n d u n d e r s t a n d t h e b a s ic m e t h o d a n d p r o c e s s i n p a c k e t q u e u e o p e r a t i o n a n d s c h e d u l i n g o f k e rn e l . b e s i d e s , we m a d e a f u r t h e r s t u d y o n t h e d e f a u l t q u e u e d i s c i p l i n e p f i f o o f t h e s y s t e m . b a s e d o n a b o v e w o r k , w e f i n i s h e d w r i t i n g a n e w a l g o r i t h m , i i i 北京交通大学硕士学位论文 t r a s h a l g o r i t h m , a n d r e w r it e d t h e o l d c l i e n t p r o g r a m m e r t c . i t c a n r u n w e l l i n k e r n e l w i t h o t h e r q u e u e d i s c i p l i n e . w e v e t r i e d t o d i s c u s s t h e n e w q u e u e d i s c i p l i n e p r o p e r ty . a l l o f t h e s e w o r k s m a d e a g o o d p r e p a r a t i o n f o r t h e c o n s t r u c t i o n o f a n a c t u a l n e t w o r k p l a t f o r m a n d r e a l i z a t i o n o f s o m e o t h e r a l g o r i t h m s . k e y w o r d : q u a l i t y o f s e r v i c e , n e t w o r k c o n g e s t i o n , q u e u e ma n a g e m e n t , q u e u e d i s c i p l in e 几 v 北京交通大学硕士学位论文 第 1 章 概 述 1 . 1 i n t e r n e t 的现状和用户需求 i n t e rn e t 从上个世纪8 0 年代以来， 因其分布式的特点和网 络的灵活性， 在短短数十年内， 就得到了飞速的发展， 成为当 今世界覆盖最为广阔的一个网络。以t c p i i p协议栈为基础的 i n t e me t 其最初的设计是用以支持数据分组业务，它对于业务 的突发性， 具有很好的适应能力， 能有效的利用网络资源， 满 足用户的需求。 当前，技术的发展使得计算机网络呈现宽带化趋势，在 i n t e rn e t 迅速发展的 今天， 人们非常关注如何能够高效、高质 量地传输 i n t e rn e t 业务以及实时多媒体业务。传统 i n t e me t 是 一种尽力而为的服务方式， 它越来越不能适应一些新业务( 如 i p电话、视频会议、电子商务等) 的服务质量 ( q u a l i ty o # s e r v i c e s . q o s ) 要 求。因 此， i f , 网 络的q o s 已 成为国 际 上的 研究热点，世界各国的大学和研究机构、标准化组织 i e t f , i t u - t , a n s i 等) 、 互联网 络产品开发商以及网络运营商都纷 纷投入到这一领域的研究和开发。 1 . 2网络服务质量与资源分配 1 . 2 . 1服务质量概念 网络服务质量的概念， 可以从多种角度去理解和看待，对 于i p网络，通常可以理解为端到端的服务质量，它是由业务 流经过的每个域所提供的边缘到边缘的服务质量级联构成。 从 北京交通人学硕士学位论文 根本上讲， 端到端的q o s 是由 给定路由 上的每一跳 ( h o p ) 的 q o s 特性所决定的。 在目前的 i p网络服务中，传统的尽力而为路由器在处理 内部拥塞时， 其采用的处理方式是造成大量不可预见和不可识 别的分组丢失的主要原因。 如果某个特定的输出端口成为了两 个 ( 或更多) 输入端口 业务流汇聚的焦点， 尽力而为的路由器 就将使用先进先出的排队方式， 把分组缓存在相应输出链路的 队列中等待传输。 排队会引入延迟以及潜在的分组丢失， 在队 列溢出时分组丢失必然发生。 因而， 从这一点讲， 在路由器端， 利用某种机制， 合理的对分组的发送和到达实行某种策略进行 控制， 对于不同的业务流实行资源分配， 成为解决现有网络服 务质量的一个切入点。下面就资源分配问题作简单讨论。 1 . 2 . 2 资源分配的几个重要概念 资源分配 资源分配， 是指一个进程， 网络设备通过它来尽量满足应 用程序对网络资源的竞争需求， 这里的资源主要指链路带宽和 路由器或交换机上的缓冲区空间。 当然， 它常常不能满足所有 需求，即一些用户或应用获得的网络资源可能比它们需要的 少，资源分配问题的一部分在于决定何时说不以及对谁说不。 数据流 在资源分配中， 流是个十分重要的抽象概念。 通常所谓流 ( fl o w)是指在源/ 目的主机对之间的一系列的分组，它们走 相同的路由。 但对于路由器而言， 它通过检查每个经过的分组 的头部中的地址， 观测出有相同的源和目的地的分组， 就将这 些分组当作同一个流来对待。 北京交通大学硕士学位论文 排队规则 对于任何一种资源分配机制， 每个路由器都必须应用某种 排队规则来决定如何缓存等待发送的分组。 在分配带宽( 哪些 分组被传送) 和分配缓冲区 ( 哪些分组被丢弃) 时， 就应考虑 排队算法。 它决定了分组等待传输的时间， 从而直接影响着分 组的延迟。 资源分配与拥塞控制 拥塞控制和资源分配是同一事物的两个方面。一方面， 如果网络在资源分配方面采取了积极的措施，就可以避免拥 塞， 从而也就没必要进行拥塞控制。然而，以任意的精度来 分配网络资源是相当困难的，因为我们讨论的资源分布在整 个网络， 需要调度连着一系列路由器的多条链路。 另一方面， 可以允许发送方想发多少就发多少，然后当拥塞发生时将其 恢复。这种方法较容易实现，但它也具有一定的破坏性，因 为在拥塞被控制前可能会丢掉许多分组。同时，在网络发生 拥塞，即资源相对于众多竞争用户对资源分配的急切需求来 说变得日 益稀少时，要采取精确的措施，恢复被拥塞的链路 并合理分配网络资源。 在这里还需要指明一点的是，除了 拥塞控制的概念外， 还有一个重要的 概念是流量 控制 ( f l o w c o n t r o l ) ， 它的 通常 意义是为了使快速的发送方不能超出慢速的接收方而在发送 端控制数据包的发送速率， 但在本文当中，由于 l i n u x系统 设计的时 候， 也引 入了 一个 流量 控制 ( t r a ff i c c o n g t r o l ) 的 概 念，其含义就是通过对数据包的队列调度机制来实现网络拥 塞控制，因而本文当中的流量控制，其含义即在于通过在路 由器接口对输入数据流的控制继而达到实现拥塞控制的目 的，而并非前面的f l o w c o n t r o l . 北京交通人学硕 卜 学位论文 1 . 2 . 3 资源分配机制的分类 资源分配机制千差万别， 进行彻底的分类是很难的。 下面 我们介绍 3 种可将资源分配机制分类的的方法。 ( 1 )路由器为中心和主机为中心 路由器为中心和主机为中心资源分配机制可归为两大类: 一种是将问题定位在网络内部 ( 如在路由器或交换机上) ，另 一种是将问题定位在网络的边缘( 如在主机上， 或许是在传输 层内) 。虽然网络中的路由 器和网 络边缘的主机均参与资源分 配，但真正的问题是哪一个承担主要责任。 在以路由器为中心的设计中， 由每个路由器决定什么时候 转发分组， 哪些分组被丢弃， 同时通知网上正在产生通信量的 主机允许它发送的分组数目。 在以主机为中心的设计中， 端主 机观测网络状况 ( 如成功通过网络的分组数) ，并由此相应调 整它们的行为。 这两类设计并不是相互排斥的。 例如， 把拥塞 管理的负担主要放在路由器上的网络仍然希望主机能支持路 由器发送的建议消息， 而使用端到端拥塞控制的网络中的路由 器也会有一些策略 ( 不论多么简单) ，用于决定当路由器队列 发生溢出时要丢弃哪些分组。 ( 2 )基于预定方式和基于反馈方式 有时资源分配机制也根据使用预定 ( r e s e r v a t i o n ) 还是反 馈 ( f e e d b a c k )来进行分类。在基于预定的系统中，端主机在 建立流时向网络申请一定的容量， 每个路由器会分配足够的资 源 ( 包括一部分缓冲区及链路带宽) 以满足这一请求。 如果某 些路由器由于自 身资源不足而不能满足该请求， 那么该路由器 北京交通大学硕士学位论文 会拒绝这个流。 在基于反 馈的 系统中， 端主机在未预定任何容 量的情况下开始发送数据， 然后根据收到的反馈信息调整发送 速率。 反馈信息可以是明确的 ( 例如， 发生拥塞的路由器向主 机发送 “ 减慢速度”的消息) ，也可以是隐含的 ( 例如，端主 机根据外部可观察到的一些网络行为， 如分组丢失， 调整发送 速率) 。 基于预定的系统意味着采用路由器为中心的资源分配机 制。 因为每个路由器都必须负责了解它当前被预定的容量是多 少， 同时确信每个主机都在预定范围内使用。 如果主机发送数 据速率超过它所预定的容量， 当路由器发生拥塞时， 该主机的 分组将首先被丢弃。 另一方面， 基于反馈的系统意味着既可以 采用路由 器为中心的机制， 也可以 采用主机为中心的机制。 通 常， 如果反馈是明 确的， 那么至少在某种程度上讲， 资源分配 方案是与路由 器有关的; 如果反馈是隐含的， 则几乎所有的负 担都落在主机身上， 而路由器的任务只是在发生拥塞时悄悄把 分组丢掉。 ( 3 )基于窗口方式和基于速率方式 对资源分配机制进行分类的第 3种方法是依据基于窗口 ( w i n d o w b a s e d) 还是基于速率 ( r a t e b a s e d ) . 正如上面提到 的， 这只是其多个领域中的一个， 类似的机制和术语还用于流 控制和拥塞控制中。 流控制和资源分配都需要一种方式来向发 送方传达允许其发送的数据量。传达这一信息通常有两种方 法: 窗口 方式和速率方式。 在第二章将介绍基于窗口的传输协 议 t c p ，其中接收方向发送方通知一个窗口。这个窗口 反映 接收方的 缓冲区大小以及对发送方传输数据量的限制， 即它支 持流控制。 用速率控制发送方的行为也是可能的， 速率是指接收方或 网络每秒能接收的比特数。 北京交通大学硕士学位论文 1 . 3 l i n u x 系统对网络服务质量的支持 l i n u x系统作为一种新型的网络操作系统，对在网络服务 质量方面的支持和资源的管理主要是采用了通信流控制机制。 内核对流量控制包括以下几种方式: s h a p i n g ( 限制) 当流量被限制， 它的传输速率就被控制在某个值以下。限 制值可以大大小于有效带宽， 这样可以平滑突发数据流量， 使 网络更为稳定。s h a p i n g( 限 制)只适用于向 外的流量。 s c h e d u l i n g ( 调 度 ) 通过调度数据包的传输， 可以 在带宽范围内， 按照优先级 分配带宽。 s c h e d u l i n g 调度 ) 也只 适于向 外的流量。 p o l i c i n g ( 策略 ) s h a p i n g用于处理向 外的 流量， 而p o l i c i i n g ( 策略) 用 于处理接收到的数据。 d r o p p i n g ( 丢弃) 如果流量超过某个设定的带宽， 就丢弃数据包， 不管是向 内还是向外。 l in u x 对流量的处理由 三 种对象控制， 它们是: g d i s c ( 排队 规则 ) 、 c l a s s ( 类别) 和f i l t e r ( 过滤器) 。 q d i s c ( 排 队 规 r 9 ) q d i s c ( 排队 规则 ) 是q u e u e in g d is c ip lin e 的 简 写， 它 是 理解 流 量控制( t r a f fi c c o n t r o l ) 的 基础。 无论何时， 内 核如果需要通过 北京交通大学硕士学位论文 某个网络接口发送数据包，它都需要按照为这个接口 配置的 q d i s c 把数据包加入队列。 然后，内 核会尽可能多地从 q d i s c 里面取出数据包，把它们交给网络适配器驱动模块。 最简单 的q d i s c 是p f i f o 它不对进入的 数据包做任何的 处理， 数 据包 采用先进先出的方式通过队列。 不过， 它会保存网络接口一时 无法处理的数据包。 c l a s s ( 类) 某些q d i s c ( 排队规则) 可以包含一 些类别， 不同的类别中可 以 包含 更深入的q d i s c ( 排队 规 则 ) ， 通过这些细分的q d i s c 还可 以为进入的队列的数据包排队。 通过设置各种类别数据包的离 队次序，q d i s c 可以为设置网络数据流量的优先级。 f i l t e r ( 过滤器 ) f i t t e r ( 过滤 器) 用于为数 据 包分 类， 决定 它们按 照何 种q d i s c 进入队列。 无论何时数据包进入一个划分子类的类别中， 都需 要进行分类。分类的方法可以有多种，使用 f i l t e r 就是其中之 一。 使用 f i l t e r 分类时， 内核会调用附属于这个c l a s s 的所有过 滤器。 直到返回一个判决。 如果没有判决返回， 就作进一步的 处理，而处理方式和q d i s c 有关。 根据本文研究的需要， 对于上述三种对象， 仅对其中的排 队规则q d i s c 做研究和分析。 1 . 4本文的研究内容和目 标 本文的研究工作是国家自然科学基金项目“ 业务内区分服 务和个性化拥塞控制”的一小部分，该研究项目总的目标是: 集成业务内区分服务和个性化拥塞控制机制， 为媒体流的网络 应用提供一个全新的技术框架。 北京交通大学硕士学位论文 研究工作表明，目 前的网络控制机制不但不能惩恶，同样 不能扬善， 用户既不会因为滥用资源而得到相应的惩罚， 也不 会因为主动约束自己的行为而得到相应的传输质量方面的改 善， 实质的问题是目 前的网络控制机制缺乏个性化服务的能 力， 它将汇聚用户整体行为的结果 “ 均匀地， 分摊到所有用户 身上， 无论单个用户干坏事或做好事， 后果都要由所有的用户 共同承受。具体地说， 现在的路由 器普遍使用f i f 。 或者r e d 缓存管理机制，当缓存满时后续到达的所有分组都会被丢弃， 而t c p 一旦发现分组丢失就认为是网络拥塞， 从而降低发送窗 口。 克服这个问题的根本出路在于个性化拥塞控制机制。 个性 化拥塞控制机制的定义就是网络在不保持流状态的前提下能 够根据不同用户的行为区别服务质量和发送不同的拥塞信号 ( 如丢弃分组) ， 用户就能够根据网络的行为规则、网络的拥 塞信号、 用户自身对服务质量的要求选择一种最为适合自己的 拥塞反应方式。 在不改变目 前网络格局的条件下大大增加用户 信息传输的灵活性， 在保持网络全局公平的条件下满足不同用 户不同业务的不同q o s 要求。 对于本文， 其主要工作侧重于实现， 即将上述课题的部分 理论算法借助于 l i n u x这个开放的系统平台和对网络良好的 性能支持， 分析其原有用于网络通信流控制的实现机制， 并试 图增加一种新的控制机制， 也就是该自 然科学基金项目 的部分 科研成果一种对非t c p 友好流的惩罚机制“ 垃圾桶算法” 使该算法在一个真正的网络环境中得到实施和验证。 其具体内 容是: 研究l i n u x 系统的网络构架，从代码实现的角度去理解网 络协议层次，为深入的分析和研究工作做准备。 研究l i n u x 内核的通信流控制机制 ( t r a f f i c c o n t r o l ) , 分析其内在的排队规则，也就是各个排队算法在内核中的实 北京交通人学硕士学 位论文_ 现方式。 编程实现垃圾桶算法，使之以与其他算法相似的形式，支 持内核对数据包的控制和管理。 对于垃圾桶算法的正确性在一个实际的网络环境中做初步 的分析和验证。 北京交通大学硕士学位论文 第2 章 网络拥塞与控制 计算机网络在过去的十几年中经历了爆炸式的增长， 随之 而来的是越来越严重的拥塞问题。例如，由于本地缓存溢出， i n t e rne t 网关会丢弃约 1 0 %的数据包。据统计， i n t e rn e t 上 9 5 % a 的数据流使用的是 t c p / i p协议。i n t e rn e t主要互连协议的 t c p / i p 的 拥塞控制 ( c o n g e s t i o n c o n t r o l ) 机制对控制拥塞具 有 特别重要的意义。拥塞控制是确保i n t e r n e t 稳定的关键因素， 也是各种管理控制机制和应用的基础， 因此成为当前网络研究 的一个热点问题。 2 . 1网络拥塞 在开始讨论我们的问题之前，先看一下图2 . 1 这个例子。 在网络当中，通常会发生这样一种情况: 一个给定源可能 在立即输出链路上有足够的容量来发送分组， 但到了网络中间 的某处，它的分组会遇到一条正被许多不同通信源使用的链 路。图2 . 1 描述的就是这种情况:两条高速链路 ( l o m以太网 和1 0 0 m f d d i 网络) 正 通过中间的一台 路由 器流入一条低速链 路 ( 1 . 5 m t l ) 。 尽管分组存在着多条路径的路由， 但从网络的 整体上看， 某个路由器不能被绕过的情况是很普遍的， 图中该 路由器负责把来自 两条高速链路的数据转发给目的地， 而由于 资源的竞争， 在该路由器极易发生网络拥塞而造成大量分组的 丢失。 北京交通大学硕士学位论文 图2 . 1分组网中的网络拥塞 从上面的例子，我们可以 看到，在现有的分组网络当中， 网络资源 ( 包括链路的带宽和路由器或交换机上的缓存) 对于 数据分组而言以共享的形式存在， 所有的分组都将在缓存中排 队等待发送。 分组在路山器中竟争连接的使用权， 每个参与竞 争的分组都被放在队列中等待按序发送。 当有太多的分组竟争 同一条链路时， 该队列就会溢出， 分组将不得不被丢弃。 如果 常常发生丢失分组的情况， 则称为网 络被拥塞 ( c o n g e s t e d ) . 因此，网络产生拥塞的根本原因在于用户 ( 端系统) 给网络提 供的负载大于网络资源容量和处理能力， 表现为数据包时延增 加、 丢弃概率增大、 上层应用系统性能下降等。图2 . 2 显示了 拥塞发生前后数据包的发送情况。 月幼最火 负截能力 成功传话擞 图2 . 2网络拥塞与数据包发送 北京交通大学硕士学位论文 如果具体分析一下，拥塞产生的直接原因有以下3 点: ( 1 )存储空间不足。 如果几个输入数据流共同需要同一个输出端口， 那么在这 个端口就会建立排队。 如果没有足够的存储空间， 数据包则会 被丢弃。 对突发数据流更是如此。 增加存储空间在某种程度上 可以缓解这一矛盾， 但当路由器有无限存储量， 拥塞只会变得 更坏， 而不是更好， 因为在网络里数据包经过长时间排队完成 转发时， 它们早已 超时， 发送端认为它们己经被丢弃， 而这些 数据包还会继续向下一路由器转发， 从而浪费网络资源， 加重 网络拥塞。 ( 2 )带宽容量不足。低速链路对高速数据流的输入也会产生 拥塞 ( 图2 . 1 的例子) 。所有信源发送的速率r 必须小于或等 于信道容量c 。 如果r c ， 在理论上无差错传输则是不可能的。 所以在网络低速链路处就会形成带宽瓶颈， 当其满足不了通过 它的所有发送端带宽的要求时，网络就会发生拥塞。 ( 3 )处理器处理能力弱、速度慢。如果路由 器的 c p u 在执行 排队缓存、更新路由表等功能时，处理速度跟不上高速链路， 也会产生拥塞。 而要避免拥塞的发生， 也需对以上3 点原因综合考虑。 例 如， 低速链路对高速c p u 也会产生拥塞; 提高链路速率而不改 变处理器， 只会转移网络瓶颈， 而不能避免拥塞。因此， 拥塞 往往也是系统各部分不匹配的结果。 拥塞一旦发生， 往往会不 断加重， 形成一个恶性循环。 如果路由器没有空余的缓存， 那 么它就必须丢弃新到的数据包。 当数据包被丢弃时， 发送端会 因超时而重传该包。由于没有得到确认， 发送端只能保留数据 北京交通大学硕士学位论文 包，结果缓存会进一步消耗，并加重拥塞。目前在 i n t e r n e t ( i p v 4 ) 上实际使用的拥塞控制基本上是建立在 t c p 的窗口控制基础之上的，本章第二节对此控制机制做了分析。 2 . 2 t c p 基于窗口的端到端拥塞控制机制 t c p在控制网络拥塞方面的不足最早是由伯克利大学的 v . j a c o b s o n 在1 9 8 8 年指出的， 详见参考文献，并针对网络的 拥塞问题，提出了 “ 慢启动”( s l o w s t a r t ) ,“ 拥塞避免” ( c o n g e s t i o n a v o i d a n c e ) 的 算法。 1 9 9 0 年出 现的t c p r e n o 版 本增加了 “ 快速重传 ”( f a s t r e t r a n s m it ) . “ 快速恢复”( f a s t r e c o v e r y ) 算法， 避免了网 络拥塞不严重时采用“ 慢启动” 算 法而造成过大的减小发送窗口尺寸的现象。这样 t c p的拥塞 控制就由这4 个核心部分组成。 t c p拥塞控制是通过控制一些称为窗口的重要参数而实 现的。这些参数主要有: ( 1 ) 拥塞窗口 ( c w n d ) : 拥塞控制的关键参数，它描述发送端 在拥塞控制情况下一次最多能发送的数据包的数量。 ( 2 ) 通告窗口( a w i n ) : 接收端给发送端预设的发送窗口 大小， 它只在t c p 连接建立的初始阶段发挥作用。 ( 3 ) 发送窗口( w i n ) : 发 送端每次实际 发 送数据的窗口 大小。 ( 4 ) 慢启动闲值 ( s s t h re s h ) : 拥塞控制中 慢启动阶段和拥塞避 免 阶 段的 分界 点。 初 始 值 通 常 设为6 5 5 3 5 6 y te o ( 5 ) 回路响应时间 ( r tt) : 一个t c p数据包从发送端发送到 接收端，发送端收到接收端确认的时间间隔。 ( 6 ) 超时重传计数器 ( r t o ) :描述数据包从发送到失效的时 间间隔，是判断数据包丢失与否及网络是否拥塞的重要参数。 通常设为2 r tt 或 5 r tt 北京交通大学硕士学位论文 ( 7 ) 快速重 传阂 值 ( tc p r e x m t th r e s h ) : 能 触 发快 速重 传的 发送 端 收到重复确认包 a c k的 个数。当 此个数超过 t c p r e x m t t h r e s h 时，网络就进入快速重传阶段。 t c p r e x m t t h re s h 缺省 值为3 e 2 . 2 . 1慢启动算法 t c p发送端通过由接收端提供的发送窗口的大小来控制 发送的数据流的多少， 但是， 发送端在一开始并不知道该向接 收方发送多个报文段，直至收到第一个报文段的确认信息 a c k收方通告的窗口 大小， 发 送端才得以知道;即 便发送端 知道接收方所能接收的窗口大小， 但发送端并不知道网络的负 荷状况， 如果在发送方和接收方之间存在多个路由器和速率较 慢的链路时， 如果在发送的最开始阶段， 就按照接收方提供的 窗口大小或者按照发送端网络接口的大小， 大量发送数据， 必 然会发生问题。 因为一些中间路由器必须缓存分组， 并有可能 耗尽存储器的空间， 也就是发生了 所谓的网络拥塞， 从而严重 降低了t c p 连接的吞吐量的。 t c p 引入了一种被称为“ 慢启 动( s l o w s t a r t) ”的算法。 该 算法通过观察到新分组进入网络的速率应该与另一端返回确 认的速率相同而进行工作。慢启动为发送方的t c p增加了另 一 个窗日 : 拥塞窗口 ( c o n g e s t i o n w in d o w ) ， 记为c w n d 。 当 与 另 一个网络的主机建立t c p 连接时，拥塞窗口 被初始化为1 个 报文段 ( 即另一端通告的报文段大小，一个数据包缺省值为 5 3 6 或5 1 2 b y t e ) 。 每收到一个a c k 拥塞窗口 就增加一个报文 段c w n d以字节为单位， 但是慢启动以报文段大小为单位进 行增加) 。发送方取拥塞窗口 与通告窗口中的最小值作为发 送 上限。发送方开始时发送一个报文段， 然后等待 a c k 。当收 到该a c k时，拥塞窗口 从 1 增加为2 ，即可以发送两个报文 段。当收到这两个报文段的a c k时，拥塞窗口就增加为4 0 北京交通大学硕士学位论文 这是一种指数增加的关系。 这里的口慢” 是与 t c p的最初行为相比较而言的。在慢启 动还没有发明之前， 当建立连接后发送端刚要开始发分组， 它 发送通知窗口允许的分组数， 即使网络有大量的带宽可用， 路 由器也可能处理不了分组突然增多的情况。 它完全依赖于路由 器上可用的缓冲区空间的大小。 因此慢启动被设计用来将分组 隔开， 使分组的突然增多的情况不会发生。 尽管指数增长比线 性增长快，但慢启动比起同时发送整个通知窗口数的数据要 “ 。漫”多t。 2 . 2 . 2拥塞避免算法 上一小节介绍的慢启动算法是在一个连接上发起数据流 的方法， 但有时我们会达到中间路由器的极限， 此时分组将被 丢弃。 拥塞避免算法是一种处理丢失分组的方法。 该算法假定 由于分组受到损坏引起的丢失是非常少的 ( 远小于1%) ，因 此分组丢失就意味着在源主机和目的主机之间的某处网络上 发生了拥塞。 有两种分组丢失的指示: 发生超时和接收到重复 的确认。 拥塞避免算法和慢启动算法是两个目的不同、独立的算 法。 但是当拥塞发生时， 我们希望降低分组进入网络的传输速 率， 于是可以调用慢启动来作到这一点. 在实际中这两个算法 通常在一起实现。 拥塞避免算法和慢启动算法需要对每个连接 维持两个变量:一个拥塞窗口 c w n d和一个慢启动门限 s s t h r e s h 。这样得到的算法的工作过程如下: 1 ) 对一个给定的连接， 初始 化c w n d 为1 个报文段，s s t h r e s h 为6 5 5 3 5 个字节。 2 ) t c p 输出例程的 输出不能超过c w n d 和接收方通告窗口的大 北京交通大学硕士学位论文 小。 拥塞避免是发送方使用的流量控制， 而通告窗口则是接收 方进行的流量控制。前者是发送方感受到的网络拥塞的估计， 而后者则与接收方在该连接上的可用缓存大小有关。 3 ) 当 拥塞发生时 ( 超时 或收到重 复 确认) ， s s t h r e s h被设置为 当前窗口大小的一半 (c w n d和接收方通告窗口大小的最小 值，但最少为2个报文段) 。此外，如果是超时引起了拥塞， 则c w n d 被设置为 1 个报文段 ( 这就是慢启动) 。 4 )当 新的 数据被对方确认时， 就增加c w n d ， 但增加的方法依 赖于我们是否正在进行慢启动或拥塞避免。 如果c w n d 小于或 等于 s s t h r e s h ，则正在进行慢启动，否则正在进行拥塞避免。 慢启动一直持续到我们回到当拥塞发生时所处位置的半时候 刁 停止( 因为我们记录了在步骤2 中给我们制造麻烦的窗口大 小的一半) ，然后转为执行拥塞避免。 慢启动算法初始设置c w n d 为1 个报文段，此后每收到一 个确认就加 1 ，使窗口按指数方式增长:发送 1 个报文段，然 后是2 个， 接着是4 个拥塞避免算法要求每次收到一个确 认时将c w n d 增加 1 / c w n d 。 与慢启动的指数增加比起来， 这是 一 种加 性增长 ( a d d i t i v e i n c r e as e ) 。 我们希望在一个往返时间内 最多为c w n d 增加1 个报文段不管在这个r t t 中收到了多少个 a c k ) ， 然后慢启动将根据这个往返时间中所收到的确认的个 数增加c w n d . 图2 .3是慢启动和拥塞避免的一个可视化描述。我们以段 为单位来显示 c w n d和 s s t h r e s h ，但它们实际上是以字节为单 位进行维护的。 在该图中，假定当c w n d 为3 2 个报文段时就会发生拥塞。 于是设置s s t h r e s h 为1 6 个报文段， 而c w n d 为1 个报文段。 在 时刻0 发送了一个报文段， 并假定在时刻 1 接收到它的a c k , 此时e w n d 增加为2 。接着发送了2 个报文段，并假定在时刻 2 接收到它们的a c k ，于是c w n d 增加为4( 对每个a c k增 北京交通人学硕士学位论文 加 1 次) 。这种指数增加算法一直进行到在时刻3 和4 之间收 到8 个a c k后e w n d 等于s s t h r e s h时才停止，从该时刻起， c w n d以线性方式增加，在每个往返时间内最多增加 1 个报文 段。 7a 76-i 一;一 h 0 i 3 3 456 7 图2 .3慢起动和拥塞避免 2 . 23快速重传和恢复 由 于分组在传输当中， 其路径是不确定的， 因而接收端收 到的报文段也是无序的。接收端在收到一个失序的报文段时， t c p 立即需要产生一个a c k( 一 个重复的a c k 。 这个重复 的a c k不应该被迟延，该重复的a c k其目的在于让对方知 道收到一个失序的报文段，并告诉对方自己希望收到的序号。 由于我们不知道一个重复的a c k是由一个丢失的报文段引起 的， 还是由于仅仅出 现了 几个报文段的重新排序， 因此我们等 待少量重复的a c k到来。 假如这只是一些报文段的重新排序， 则在重新排序的报文段被处理并产生一个新的a c k之前， 只 可能产生1 一 2 个重复的a c k . 如果一连串 收到3 个或3 个以 上的重复 a c k *就非常可能是一个报文段丢失了。于是我们 北京交通大学硕士学位论文 就重传丢失的数据报文段， 而无需等待超时定时器溢出。 这就 是快速重传算法。 接下来执行的不是慢启动算法而是拥塞避免 算法，这就是快速恢复算法。 这个算法通常按如下过程进行实现: 1 )当 收到第3 个重复的a c k时， 将s s t h r e s h 设置为当前拥塞 窗口c w n d 的一半。 重传丢失的报文段。 设置c w n d 为s s t h r e s h 加上 3 倍的报文段大小。 2 ) 每次收到另一个重复的a c k时，c w n d 增加1 个报文段大 小并发送 1 个分组 ( 如果新的c w n d 允许发送) 。 3 ) 当 下一个确认新 数据的a c k 到达时， 设置c w n d 为s s t h r e s h ( 在第 1 步中设置的值) 。这个 a c k应该是在进行重传后的 一个往返时间内对步骤 1 中重传的确认。另外，这个a c k也 应该是对丢失的分组和收到的第1 个重复的a c k之间的所有 中间报文段的确认。 这一步采用的是拥塞避免， 因为当分组丢 失时我们将当前的速率减半。 2 . 3 l i n u x 支持的拥塞控制机制 l i n u x操作系统作为一种新型的网络操作系统，由于其源 代码的公开性， 研究人员可以方便的修改其内核， 添加、 调试 自己的功能模块， 因而在最近的几年得到了飞速的发展。 它对 网络功能的支持也日益完善， 可以在l i n u x 系统下方便的实现 服务器、 工作站的架构， 也同样可以配置成路由器使用， 实现 数据包的路由转发功能。 针对上面提到的网络拥塞和带宽资源的分配问题，l i n u x 也同样提供了 一套完善的q o s 机制， 用户可以根据自 身的需 要， 方便的实现对资源的 管理和分配。 在这一套q o s机制当 中， 起核心作用的是一系列别具特色、 各具优势的数据队列调 度算法， 在本文当中都以 排队规则( q u e u e d i s c i p l i n e ) 来表示。 i 七 京交通大学硕士学位论文 下面我们来看一下内核支持的主要的几个算法. 。 2 . 3 . 1先进先出算法 i f o f i f o( 先进先出) 调度算法， 它的思想很简单:首先到达 路由 器的分组首先被发送。 如图2 .4 a 所示， 有一个 f i f o队 列，最多可容纳 8个分组。假定每个路由器中缓冲区的空间 是有限的， 那么当有分组到达而队列 ( 缓冲区)己满时，路由 器将丢弃这个新到的分组，如图2 .4 b 所示，在图中，所有收 到的数据包都受到同等对待， 不分重要性。由于在f i f o队尾 到达的分组被丢弃，因此有时 称为队尾丢弃 ( d r o p t a i l ) . 到达的分组 各空闲 缓冲区正要传送 厂厂 空闲缓冲区队列， ， 的分组 到达的分组 正要传送 、 b )丢 弃 图2 .4 a ) f i f o排队 法 b ) 在f i f o队列中的 对尾丢弃 北京交通大学硕士学位论文 带队尾丢弃的 f i f o ，是所有排队算法中最简单的，也因 为简单在因特网路由器中， 被广泛地应用。 这种简单的排队方 法将拥塞控制和资源分配的所有责任都推到了网络的边缘。 这 样， 目 前因特网中流行的拥塞控制方式就假定不能从路由器获 得任何信息:由t c p负责检测和处理拥塞。 基本f i f o排队法的一个简单变种是优先排队法。它的思 想是给每个分组一个优先级标志: 这个标志可被承载， 例如可 放在 i p的服务类型 (t o s ) 字段中。 路由器采用多个 f i f o 队列， 每个队列对应一个优先级。 路由器总是先发送完非空的 最高优先级队列中的分组， 然后再发送下一个优先级队列中的 分组。 在每个优先级队列中， 分组都采用 f i f o方式管理。 这 种方式与尽力而为模型有一点不同， 但它还没有优化到对任意 特定的优先级提供特殊保证。 它仅允许高优先级的分组插在队 列的前面。 优先排队法的问 题是高优先级队列可能使其他所有 的队列都 “ 饿死” 。也就是说，只要在高优先级队列中有一个 高优先级分组要传送，低优先级队列就不能获得服务。l i n u x 内 核 缺省的 队 列 管 理 方 法 ( p f if o _ f a s t ) 就是 基于 上 面的 思 想， 在这种队列中有三个所谓的频道 ( b a n d s ) ， 每个频道都采用 f i f o准则。 只要b a n d 0 中有数据等待发送， b a n d i 中的数据就 不会被发送。 b a n d i 和b a n d 2同样也是如此。这种排队规则虽 然极其易于实现，但是排在队尾的数据包会产生很大的延迟。 特别是当较小的数据包排在许多较大的包之后时， 这种延时对 于小的数据包来说特别明显。 在i p 包头中有一个t o s ( t