（系统工程专业论文）大时滞网络的主动队列管理算法研究.pdf

硕士论文大时滞网络的主动队列管理算法研究 ab s t r a c t a s o n e k in do f su p p 1e m e 111 on th e c o n ge s ti0 ncontro l o f the te rmi n a l sy s te m s ， t h e 从t i v e q u e u c ma nag e me nt( a q m) arg o ri t 11 l1 1 a c t i n g o nthe i nt e rme d i a t en o d e s i s abl et o c o ntro l th eq u eue l e n g t he ffec t i v e l yo nt he b a s i s o f th e址g ht l l r o u g ll p ut o f t h er o u t er s . the re fo r e ， th ea q m a r g o r l t h l nc a nc o n t ro l t h e即d 一 即dd e l aysfor q o s即盯 ant ees ， w h i c h m a d e a q mb e c o m e o n e o f the h o tt e s t fi e l d s i n t h e c o m p 讯 e r n e two r k s . t h e 皿p a c t o n th e p e r fo rman c e c aus e db y la r g e d e la y a lw a y s b e n e g le c te d in t h e e x i st e da l g o r i t l l l l l st o: h eaut hor ， skno w l e d g e . afa c t t l扛 o u gh s i mu l at i o ne x p e r i m e nt si s v e r i fi e d ， wh i c hi s t he q u e ues c o ntro l l e db ys e v e r al t y p i c a l a q m al g o r i t h l 11 s ， i ncl u d i n g r e d ，r e m，p lc o ntr o l l e randp i d c o n tro l l e r ;th ed r am at i co s c i l l at i o n si nl ar g ed e l a y n et wo r k s ar e app e ar e d ， w 11 i c hd e c r e a s e s t h e u t i l i z at i o no f t he b o tt l e n e c kl i nk and l e ads t o th e unav o id ab le d e l盯 j itt e r . t h is p ap e r c o n c e m s th e in flue n c eo nth e p e r fo rmanc e o f a c t i v e q u e u e ma 门 a g e me n t ( a q m) i nn e two rk c a u s e d b y t h e t i me d e l a y s ， a n d mo d e l e s t h e n e t w o r kfr o mthe c o nt rol 一 the o r e t i c p o i nto f v i e w . t h e nt h ee l l l p h a s i s o f res e arc hi nt h e c o n g e s t i o n c o n tr o l tu rns 1 l n 0th e r e s e a r c hi n v e s t i g ai i o no f t h e c 0 n t r o l a l g o r i t b 11 1 s a n d t h e i r p re fe r e n c e s ， whe re t h e c o n trol t he o 汀c anwork ai th e s 翻e ti m e ， s o m e s tr a te g ie s in tim e d e l 盯s y s t e ma r e s ume d u p . the m a in c o n c ern 0 f th e p ap e r is t o r i se a s 而th- p l a lg o rit hln b a s e d o n m o d i fi e d c o m p e n s at o r and ano th e r m o d i fi e d s m i t h 一 p l al g o r i t l l 们 l b a s e d o n h u m an s i mu l atedl n t e l l i g e n t c 0 l l t t o 1 b y the app l y i n g o f s mi t h p re d i c t o r and i nt e l 1 i g enc e c o n t r o l . f in al y ， a s e ts o f s im u lat io n e x p e rim e n ts ar e p ro v id e d to d e m o n st r at e t h e e ffec tiv e n e s s o f th e p r o p o s e d al g o ri lb lll 卜 we c ans e e th atth e s e two n e wa lg o rit 11 i刀 e s re s tr ic t t h e n e g at iv e im p ac t o 几 th e q u e u e s tabilityc aus e d b y th e la rg e d e layand is o b v io u s ly s 叩e r io r to th ato f t h ee x i s t e ds c heme s. k 即wo r d s : l ar g e d e l ay，c o n g e s t i o n c o nt r o l ， a c ti v e q u e u e m ana g e m e nt ， s m i th p r e d i ct o 几 h u m a n s i mu l at e d i n t e l l i g e n t 1 1 1 声明 本学位论文是我在导师的 指导下取得的 研究成果，尽我所知，在 本学位论文中， 除了 加以 标注和致谢的部分外，不包含其他人已 经发 表或公布过的研究成果， 也不包含我为获得任何教育机构的学 位或学 历而使用过的材料。与我一同 工作的同 事对本学位论文做出的贡献均 己 在论文中作了明确的说明。 研究生签名:年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档， 可以 借阅 或上网公布本学位论文的部分或全部内 容，可以向 有关部门或 机构送 交并 授权其保存、借阅或上网公布本学位论文的部分或全部内 容。 对 于保密论文，按保密的 有关规定和 程序处理。 研究生签名:年月日 硕士论文大时濡网络的主动队列管理算法研究 1 绪论 i n t e r n e t 自 从出 现以来就一直以 惊人的速度飞速发展。 近些年来， 许多新兴的网 络服务， 例如v od点播、 pzp 以 及视频会议等大数据传输量业务的出 现， 已 使i nternet 由以 往的单一数据传送网 发展成传送数据、 语音、 视频等多媒体信息的综合业务网。 正是由 于网络数据流量的急剧增加， 使工 nternet 经常发生拥塞( congest ion)现象， 所 导致的后果是出现数据传输延时、抖动等服务质量( quali ty of s e rvi ces ， q os) 性能 指标的下降 和带宽、 缓存 等网 络资 源利用率降 低的 现象11 . 特别是 在主 干网 络， 一旦 发生长时间的网络拥塞， 后果不堪设想， 在极端情况下甚至可能导致网络的崩溃。 同 时， 新业务的出 现也对网 络服务质量提出了 更高的要求。 这些新需求的共同特点是要 求有较低的网络延时和抖动、 较低的数据包丢失率以及较高的访问带宽。 这些严格的 服务质量指标促进了网 络技术的发展， 接纳控制、 流量成形、 队列调度以及拥塞控制 等都得到了 显著的发展， 而这些网 络技术最基本和最核心的 依旧是拥塞控制。因此， 在过去的二十几年中，如何预防和控制拥塞一直是计算机网络界研究的热点。 ， . 1网络拥塞控制概述 1 . 1 . 1网络拥塞的定义以及拥塞产生的原因 计算机网 络中的链路容量、 处理器的处理能力以 及路由 器节点的缓存等都是地理 位置分布于全世界的 用户( 端系统) 所共享的资源。 当 用户提供给网络的负载总和大于 网络资源容量时，网 络的性能会下降，主要体现为数据包的往返时延( r r r ) 加大、丢 包率增加以及上层应用系统性能下降等，这些现象统称为网络拥塞。 统计表明， 网络的性能降低有三成的因素是由于硬件损坏， 七成是由于网络拥塞 造成的阁 。 因此在网 络不存在硬件损坏的前提下，当 主机转储到通信子网中的分组数 量在其传输容量之内 时， 它们将全部送达目 的地。 然而当通信量增大太快时， 路由 器 不再能够应付， 开始丢弃分组， 并会导致情况恶化， 而在通信量高出一定限度的情况 下，网络完全瘫痪， 几乎没有分组能够送达目的端。 由 此 可见， 造 成网 络 拥塞的因 素主 要有以 下三 个方面门 : ( 1)路由 器缓冲区队列溢出。 如果有多个突发分组同时到达，并且输出到同一链 路中， 这时如果没有足够的带宽容量， 就会产生一段瓶颈链路， 并在该段瓶颈链路的 路由 器卜 津守韶队 列。 如果路由 器处再没有足够的缓存来存储这些分组， 有些分组就 绪论硕士论文 会在队列滋出 缓冲区时被丢弃。 在某种程度上增加缓冲区容t会改替这种现象， 但是， 19 84年n agle研 究 发 现 tl61， 如 果 路 由 器 有 无 限 大 的 内 存， 拥 塞 不 但 不 会 变 好， 反 而 会更糟。 因为分组在队 列中 等待处理时，己 经超时， 而且副本已经被重发了， 这些副 本将被尽职的转发到下一个路由 器， 从而增加了到目 的地所有线路的 载荷。 (2 ) 链路传输速度与路由 器c pu处理速度的不匹配。如果路由 器的c pu处理速度 太慢， 以 至于不能执行要求它们做的任务， 那么即使有多余的线路容量， 也可能使队 列饱和。 也就是说， 商速链路对低速c p u 会产生拥塞。 同理， 如果链路带宽容量不足， 满足不了 通过它的所有发送端的带宽要求时， 会在低速链路处产生带宽瓶颈， 即低速 链路对高速c pu也会产生拥塞。 (3 ) 拥塞会导致恶性循环。 如果路由 器的缓冲区队列已 经饱和，那就必须丢掉新 来的分组。 每扔掉一个分组， 发送端就可能因为超时而重传此分组， 并很可能需要多 次重传. 由于发送端路由 器在未收到确认前不能释放在通常情况下已 经释放了的缓冲 区， 如此循环下去， 拥塞的程度始终得不到缓解， 只能越来越重， 最终导致网络崩溃。 1 . 1 . 2网络拥塞控制 网络拥塞控制的基本思想是在共享资源管理的基础上， 按一定的算法， 控制信源 端的业务发送量，合理地使用瓶颈资源。 具体分来， 拥塞控制算法包含拥塞避免和拥塞控制两种机制。 拥塞避免是“ 预防” 机制， 它的目 标是当网 络在正常运作时， 避免网 络进入拥塞 状态。 拥塞控制是“ 恢复” 机制， 它是用于在网 络己 经发生拥塞的 情况下， 把网络从拥塞状态中 恢复出 来。 为了 避免拥塞， 保证网络带宽的高效利用并提供好的服务质量， 任何一种拥塞避免和控制 策略都应该能满足下列要求11;: ( 1) 提前探测并消除拥塞。时刻监视穿越路由 器的数据流量，一旦检测到拥塞发 生的前兆就开始采取预防措施，力图把网络拥塞消除在萌芽 状态。 (2 ) 保证对不同特性的数据具有公平性。对丢包不太敏感的流要有相应的处理机 制:同时对恶意攻击或错误操作的流也应有可靠的防范，建立相应的惩罚机制. (3 ) 在缓冲区排队的分组应尽可能短，并保证对延时敏感的业务优先传送。 (4 ) 尽可能提高吞吐率，高效地利用实际链路。能够容许一定范围内 的突发传输 而不认为是出现了 拥塞。 基于以 上思想， 目 前i nternet 上的 拥塞控制策略主要有两个方面， 一种是以t cp 为核心的基于窗口 技术的端到端( end 一 t 。 一 end)控制。 这种方法主要是以丢包作为拥塞 发生的信号， 当发送端确认已发出的数据包丢失后， 通过减少拥塞窗口的方法来降低 发送速率，以此缓解拥塞。另一种拥塞控制方法是以ip 为核心的基干路由 器端的拥 大时浦网络的主动队列管理算法研究 塞控制， 它利用每条连接的 一些状态信息( 如缓冲区大小和发送速率等 ) 在数据流经过 的网 络节点 上实施拥塞控制， 主要是在路由器 端应用包调度算法和缓存管理技术。 本 文主要研究的主动队 列管理(a 以) 算法就是属于基于路由 器端的拥 塞控制策略。 1 . 1 ， 3网络拥塞控制策 略 . 端到端( t c p ) 拥塞控制 tcp 拥塞控制是一 种基于滑动窗口 的端到端(e n d es t o-的d)控制机制， 它通过改变 一些参数来实现拥塞控 制， 这些参数主要如表 1 . 1 所示: 表 1 . i t c p 拥塞控制的主要参数 拥塞窗口( c 肋d )发送端在 拥塞控制的 情况下一次最多能发送的 数据包的数据 包的数t: 通告窗口( 晰 d ) 接收 端给发送端预设的 发送窗口大小，只在 t c p连接建立的 初期有效: 发送窗口( 而d )发 送端每次 实际发送数 据的窗口大小; 慢启 动阀 值 ( s s t hre 3 h ) 拥塞控制中 慢启动和拥塞避免阶段的分界点; 回 路 响 应 时 间 ( r ti) 一个数据包从发送端发送到接收端， 发送端受到接收端确认 的时间间隔; 超时重传 计数器 (rt 0 ) 数据包从发送到失效的时间间隔; 快 速 重 传 阀 值 ( t c p r e 恤t t hre sh) 能 触发快速重传的 发送端收到重复确认包a c k 的个数。 tcp 拥塞控制的 基础加性 增/ 减性乘 策略， 它的具体过程 可以分为 三个阶段t. : 慢 启动、 拥塞避免、 选择重传和 拥塞 恢复。 其具体过程是:发送端在开始发送数据时， 处于 “ 慢启动” 阶段。此时 拥塞窗口的 值为1 ，即只可以 发送一个t c p 数据包。当发 送端每收到一个来自 接收端的确认帧伪 c k 帧) 后， 拥塞窗口 的值就加 1 ，即在下一时 刻， 可以 一次性发送 两个tcp 数据包。 发送结束以后， 发送端将收到两个来自 接收端 的 舰k帧，拥塞窗口的值加 2 以 此类推，拥塞窗口的值可以 用公式表示为: 酬刀 j 二 2 ” ( n 二 0 、 1 、 2 、3. “ 此时拥塞窗口随r 竹呈指数规律增 长， 可见 “ 慢启动” 其实并不慢。 当 拥塞 窗口的 值等于慢启动阀值时， “ 慢启动” 结束， 进入 “ 拥塞避免” 阶段。 在该阶段每收到一个八 c k 帧， 拥塞窗口的值就增加ljc 冲 刀 d ， 即每个时刻发送的 t c p 数据包增加 1 ，呈 线性增长， 增长速率要保守了 许多。 如果 发现超时或收到 3 个 相同的ack 帧， 网络即 认为 数据丢失， 发生拥塞。 此时， 发送端先将慢启动阀 值改为 3 绪论硕士论文 当 前拥塞窗口 的一半，再将 拥塞窗口 重置为1 ，发 送端重 新进入 “ 慢启动” 阶段。 在 发送新的 数据包之前， 发送端要重传丢失的数 据包， 就是“ 选择重传” 阶段。 而由 于 拥塞窗口已 经减小， 到 达接收 端的数 据包也 会减少， 因此网络的 拥塞状况会逐渐恢复， 也就是 “ 拥塞恢复”阶段。 自1 98 8 年v . j a c o b s on提出了tcp 端到端的 基于滑动窗口 的 拥塞控制算法l1， t cp 的 流量控制算法经历了t ahoe、 r en。 、ne 份 r en。 、 s ack 等多个版本的改进， 不断地完 善。 但由 于在最初的tcp 协议中只有流控制( flocontro1) 而没有拥塞控制， 发送端 仅通过对网 络当 前状态的 探测来调整发 送分组的窗口 大小。 这样的tcp 控制机制将注 意力 全部 集中 到了 终端系 统上， 只考虑了 接收端的接收能力， 而完全没有考虑到网 络 的传输能力， 从而导 致了网 络拥塞的发 生。而 且，由 于 工 nternet 规模的不断扩大， 从网 络节点 发生拥塞( 丢包) 到发 送端降 低流量需 要较长的 周期， 而同时发送端依然以 很高的速率发送数 据， t cp拥塞控制策略来不及反馈到发送端， 会造成更大规模的 拥 塞。因此不能完全依靠发送端来控制拥塞，也需要处于网 络层的 ip路由 器参与控制 策略以 减轻网络的负担。 . 中 间节点( i p)控制策略 在i nternet 这样复杂的异构系统中， 不能指望所 有的 用户在i nternet 应用中 兼 容端到端的t c p 拥塞控制， 而且由于t c p 拥塞控 制策略 有其自 身固有的缺点， 因 此基 于 ip的拥塞控制 策略受到大多数学者的关 注。 在tcp 的端 到端控制系统中， 数据发 送方 和接收 方对网 络的 拥塞程度一无所知， 而网 络传输中的 大部分丢包事件是由于 路 由器结点的 缓冲区 溢出 造成的，因此只有路由 器才对网 络的 拥塞程度有最直接的了 解， 这就要求网关 和路由 器必须参与网 络资 源的 控制工作门 。 而现有 ip 路由 器的主 要功能是进行包转发，不具备对网络的拥塞进行检测和控制 功能。 为此， i etf提出 在路由 器中提供主动队列管理技术( a cti veq ueue枷nagement济 q m ) ， 采用排队算法和 数据包丢弃策略监控路由器缓冲区队列， 提前检测拥塞的出 现井通知数据发送端。 这 样发送端可以 在路由 器溢出 之前调整数据的发送速率， 或者 数据发送端主动地丢弃或 标 记少量 数据包， 以 主动丢包的形式来避免或者缓解 拥塞， 从而降低总的丢包率， 并 避免更严重拥塞的发生。 中间节点针 对拥塞控制的 增强 机制中 主要有以 下两个方 面: 调度和队列管理。 调 度直接管理输出 链路的带宽资 源， 而队 列管理通过控制缓存与 队列的占 用间 接影响带 宽的 分配。 目 前路由 器中使 用最广泛的是简单的 先进先出( fi fo) 包调度算法结合尾丢 弃队 列管 理策 略， 即当 路由 器缓存已 满时，丢弃后 续到达的 数 据包。对fipo 算法的 改 进包括 公平排队算法( f q ) 、加权公平排队算法( 邢动和基于类的排队算法( c b q)等。 而在网络中最 早使用的队 列管理策略就是“ 去尾” 队 列管理 策略， 它的主要 缺点是 会 产生闭塞和满队 列现象， 造成大量数 据包丢失。 通过把 “ 去尾” 策略改为当队 列满时 硕士论文 大时浦网络的主动队列管理算 法研究 “ 去头” 或 “ 随机丢弃”， 可以 避免产生闭 塞 ， 但却无法克服满队 列现象。 由 于以上的策略只有在队列满的时候， 也 就是已 经发生 拥塞的时候才被动地丢弃 数据包， 因 此都是被动的队列管理策略， 无法 很好地起到拥塞控制的作用。 这就促使 专家和学者建议采用 “ 主动队 列管理”( a 明) 策略， 即在队 列满之前就按一定概率丢 弃 或标记少量数据包， 从而端点 在缓存滋出之前就能对拥塞做出响应。 a 姗 的目 标是使路由 器能控制平均排队 长度， 减少数据包 丢弃数。这就要求a q m 解决的问 题应主要包括以下几个方面阂 : ( 1) 探测路由 器可能发生的 拥塞， 通过随机丢弃分组或标记分组来通知源端来采 取措施避免可能发生的 拥塞， 其中对 拥塞程度的判断是至关重要的。 (2 ) 缓冲控制机制应能 容忍某些脆弱流的 短暂突发， 但如果突发度超过一定门限， 则 应开始 对潜在的 缓冲溢出 危险做出反应， 对行为 不良 的 流加以 管制。 当具有侵略性 的高带宽 流变得符合行为规范时， 应能对其及时 解禁。 同 时， 公平地处理包括突发 性、 持久性和 间隙性的 各种业务流。 ( 3 ) 避免多个t c p 连接由 于队列溢出 而造成的全局同步( g l o b a l s y n c hro n i z a t i o n) 现象。 全 局同步 指的 是采用尾丢弃策略， 当 缓冲资源被完全占 用时， 大量的t c p 源同 时降低发 送速率， 在短时间内 造成网络的负载过轻， 降 低了网络资源的利用率; 然后， 所有的tc p 数据源又同 时增加发送速率， 导 致新一 轮拥塞的出现， 这样周而复始地影 响网络的运行效率，造成大量分组的丢失。 (4 ) 队列 长度应 稳定 变化， 最好能 在预定 义的范围内 波动。同时也要维持合适的 队列长度， 在高吞吐量 和低延时之间做出 合理的 平衡。 既要保证较高的 链路利用率， 同时 也不能使队列长度过大从而导 致数据延时 过大。 (5 ) 算法应易于 在实际路由 器中实 现和 部署， 并考虑到能兼容网络中的 其他设备， 同时， 算法维护的状态信息及其自 身占 用的资 源应尽可 能少。 以 这些要求为主旨， 许多新的算法在世界各地被不断提出。 主动队 列管理算法是 一种积 极的管理资源的机制， 它对网 络上可能出 现的拥塞情况进行预判， 然后在情形 恶化之 前采取一定的 机制来通知数 据发送方， 从而可能避免真正 拥塞的发生。 较之于 传统的队 列管理或调度机制， 主动队列管理算法具 有以 下的一些优点门 : ( 1)能 够减少 路由 器的丢包数量. 在分组网 络中， 分组的突发性是不可避免的， 如果路由 器的队 列空间已经“ 忠于” 稳定状 态的数 据流或 者缓存空间不 足， 那么路由 器就没 有能力来缓存 突发数据流。 主动队列 管理通过维持一个小的平均队 列长度， 可 以 提供更大的能力来 吸收自 然出 现的突发 数据流， 而不用丢弃分组。 (2 ) 能够提供低 延时的交互服务。主动队 列管理 通过减小平均队 列长 度可以有效 地减小报文在网络设 备中的排队延迟。 这对于一些 交互的或实时的应用尤 其重要， 这 绪论 硕士论文 些应用对丢包并不是非常敏感， 个别的分组丢失不会对其造成很大的除碍; 但是延迟 的 影响 则是巨 大的，如t elnet 传 输以 及交互的 声讯会议等。 (3 ) 能够避免死锁( l ock 一 out)行为的发生。死锁行为指的是由 于同 步或其他定时 作用的 结果，导致 “ 去 尾”算法让某 些流独占队列空间，阻 止其他流的 包进入队 列。 由 于主动队 列管理算法有 着以上 显著的 优点，自1 9 98年 b . brad即等人在 i e if 提出主 动队列管理( a cti ve queue血nage ment， 胡m ) 的研究动议以 来，作为端到端拥 塞控制技术的补充， a 洲算法得到了不 断地发展和补充。 1 . 1 . 4网 络拥塞控制的现状和研究热点 当 前大多数的网络 拥塞算法 研究 还只是基于理论的。 也 就是说大多数网络拥塞方 面的 研究 是在一 个理想网络环境的基 础上进行算法设计， 而 且只是在纯软件环境下进 行， 完全 不涉及硬件环境， 然后 通过各种仿真软件平台进行 仿真， 再根据经验和实验 调试的方 式进行参数调整以 及算法改 进， 无法在实践中 验证算法的有效 性， 更加无法 在实际的网 络中加以 应用。 因为 仿真只是模拟的实现情况， 难以 对网 络的复杂情况做 出全面的 分析和预测， 所得到的 仿真结果会与实际情况相差很多。 因 此拥塞控制领域 的研究还有很长的一段路要走。 在目 前来看，网 络拥塞控制领域的 研究热点主 要集中于以 下几方面 ” : ( 1)对路由 器主动队列管理( a 卿) 算法的 研究. 作为i etf 推荐的 拥塞控制关键机 制， 主动 队列管 理引起了 广泛的兴 趣。 对它的 研究通常是基于 仿真对现有的算法进行 改进，改进主要集中在参数设置以及有效估计拥塞程度问题上。 (2)对 混 合 流 量 传 输 公 平 性的 研 究 t41 ， 例如t cp流、 ud p 流以 及h 竹 p 流 在同 一 网 络上 传输的公平性问 题。 如何才能 有效地利用网络带宽，以 及如何公平 地分配资源， 而不是 让用户去抢占 网络资 源， 这是传输公平性要解决的主要问 题。 ( 3) 对多媒体 传输控制的研究， 包括传输算法设 计的 研究。 高速网 络的建立和多 媒体业 务流的 应用， 使网络的 传输性能更加复杂， 对性能的要求也更高。 传输要求网 络有尽量小的 波动和时滞。 (4) 对 提高网络负载能力的 研究。 由 于在实际的i nternet 网 络中， 已 经有数以 亿 计的 用户在使用网络资源， 如 此庞大的负载必定给网络性能带 来不可忽 视的影响， 这 就需 要研究如何在不影响网 络性能的同时 提高 用户数目 的 增长能力。 ( 5)基于多 瓶颈链路、 双向 链路以 及突发流量等不同网 络环境的研究 阅。 在实际 网络环 境中， 这些都是普遍存在的现 象， 但是在以 往的 算法 研究中 这些常被作为 特殊 情况进 行理想 化处理，因此， 在近几年， 对这些 “ 特殊” 网络 环境的 研究成为热点。 (6 ) 基于 速率结合基于队列的主 动队 列管理算法研究。当 前的主动队列管理 算法 硕士论文大时海网络的主动队列管理算法研究 通常 要么是基于速率要么是 基于队列长度， 因此， 同时对二者进行研究成为当 前的 热 点之 一。 其中孙金生等提出的r a q 算法就是基于该思想， 结合了 基于 速率与基于队 列 算法的 优点 阎。 (7 ) 基于大时 滞网络的研究。由 于实际网络中普遍时 滞要比仿真时所用到的时滞 大很多， 而在大时滞情况下， 许多基于小 时滞环境的主动队列管理算法性能 显著恶化. 因此，大时 滞系统的控制问题一直是网 络拥塞 控制着力解决的 一个主要问题。同时， 这也是本文所要研究的主要内容。 ， . 2 本 文主要完成的工作 本文的研究课题来源于江苏省自 然科学基金， 主要研究大时 滞网 络的主动队列管 理算 法。 . 本课题的 研究意义 本文 通过研究发现，在早期的 主动队列管理算法的 研究中， 由于当时所研究网络 的范围和规 模都比 较小， 因此， 在进行网 络仿真验证算法性能的时候， 在网 络环境的 设置上， 无一 例外地 认定rtt 往返时延不超过几十毫秒。 而此后的学者， 为了进行算 法性能 的对比方便，也沿用了 几十毫秒的r tt时延. 然而，现在的i nterllet 网络畏 盖了 世界各地，在范围 上和规模上都不可与早期的网络相提并论。 许多跨洲越洋的 t c p 连接， r 竹 时延往往有几百毫 秒， 而已 有的大多数策略和算法都 没有充分考虑往 返时 延对算法性能 的影响。 此后， 本文 运用ns一 2 软柞在网 络仿真条件下证明， 许多 经典 算法， 例如red 、 咫m 、pl 以 及p 功等都出现了队 列振荡和时延 抖动。这些在小 时滞网络环境下适用的 算法不能有效地工作在大时 滞环境 下， 这就要求我们研究出适 合在大时滞网络下工 作的主动队列管理算法 . 本文所做改 进工作 本文着重考虑了 大时滞对胡m 算法稳定 性的影响。 首先本文基于启发式的思想， 在大时滞网络环境下， 通过调整参数的方式改进了r e d 算法， 并进行了 网络仿真验证。 然后设计了 一种基于 改进补偿器结构的5 血t h 一 pl 算法。 经过网 络仿真， 该算法虽然 有效地 补偿了时延， 但是控制性能与鲁棒性能都还不够理想。 因 此， 本文将控制理论 中的智能 控制思想与smi th预估器结合起来， 设计出 一种控制性能以 及鲁棒性能都更 好的基于仿人智能控 制思想的改进腼主 th中1 腼 d 主 f 加 d 一 5 口 主 th p 工 ， 粥pl) 算法。 . 本文的论文 组织结构 下面本文的内 容安排如下: 第二 章分别从基于启发式和基于控制理论 两方面介绍了几种经典的主动队 列管 理算 法， 主要介 绍了re。 算法，以及基于控制理论的几种算法。 7 绪论硕士论文 第三章主要归纳总结了 现有时滞系统的 控制策略， 重点分析介绍了 在后文提出的 改进算法中所涉及到的s mit h预估补偿机制和智能控制. 第四 章本文首先基于启发式思想， 在大时 滞网络环境下对red 算法进行了参数改 进。 然后提出了墓于改进补偿器结构的smith - p l 算法以 及基于仿人智能思想的改进 s m i t b es p l 算法( 物d i f i e ds 口 i t h 一 p l， m s p i ) ， 介绍t创门 的 设计原理和过程。 第五章首先介绍了网络仿真以 及仿真软件， 然后建立在大时滞网络拓扑结构， 并 在该结构下对己 有的主动队列管理算法和本文提出的新算法进行了 仿真， 并将仿真结 果图形化显示，比 较各种算法在大时滞环境下性能上的 优劣，最后给出结论。 ， . 3工作完成的环境 本论文所有的 仿真都是在 叭nd佣sxp 操作系统下， 在利用c y 四in软件安装的 n e torks i mul ato r ( v e r s i o nz ) 网络仿真平台上完成的。c y 沙i n是一个运行于 windos 下免费的u nix 子系统， 它是使用一个动态链接库( d l l)来实现的。 这样， 我们 可以开发出c y 盯in下的u nix 工具， 使用这个d ll运行在w i ndows 下。 也就是说， c y 盯in 可以使我们在w i nd昨5 操作系统下拥有u nix 开发环境， 并且不用切换。由 于ns仿真 软件的开发最初是针对基于u nix 系统下的网 络设计和仿真而进行的，但是我们在应 用时一般在贾 i nd叮5 下开发和调试比较方便， 因此本文就使用c y 罗in软件在w i ndows 下安装和运行ns软件。 硕士论文 大时滞网络的主动队列管理算法研究 2主动队列管 理 (aq 码算法研究 a q m 算法的核心问 题是如何检测拥塞和如何计算包丢失或标记概率。从包丢弃概 率的计算来分， 可以分为启发式的a q m 算法和基于控制理论的a 明算法两大类。 下面本 章首先从包丢弃概率的计算方面来介绍几种基于启发式的经典主动队列管理算法。 2. 1基于启发式的 主动队列管理算法 2 . 1 . 1 咫d ( r a n d om ea 卫 ， l ydetecti on) 算法及其改进算法 随 机早期 检测( r e d ) 算法早 在1 9 93年就被 f l oyd 和j acb s on提出 阂 叫， 作为r p c 2 3 09 在a 叫中推 荐的唯一获 选算法， 它己经作为 可选配置( c isco的 饥 班 d ) 应用到在实际的路 由器中， 并且对网 络拥 塞控制起到了一定的作用。 该算法的基本思想是 通过计算平均 队列长度来检测即将到 来的 拥塞， 并以 丢弃数据包或在数据包的首部设 一标志位的方 式 来 通 告 拥 塞 连 接. r e d 算 法的 实 现 分为 如下 两 步 明 : 第一步: r ed算法用一个 e 饥 认( e xpo n e nti a l l y ， e i g h t e dmov i n gave r sge ) 低通 滤波器计算平均队 列长度，表示为: avg 卜(l 一 粉 口 ) x avs+ w 叮 x 夕.(2 1 ) 其中 ， av g 表 示 平 均 队 列 长 度， q 表示 瞬 时队 列 长 度， w q 是 一 个 加权 系 数， 同 时 也是一 个时间常数。 另外， 考虑队列空闲时 刻， 路由器在这段时间里估计有m 个平均 大小的包可以被传输，计算方法为: m= ( 万 雄 一 q 一 才 加司 / 5(2 . 2 ) 其中t i 职表示当 前时间， 屯t i 砚 表示队列开始为空的时刻，才 表示传输一个平 均大小的包所需的典 型传输时间。 路由 器计算队 列平均长度时， 就认为在这个空闲 期 间收到了m 个分组， 而m也要进入m 瞥的 计算: a v g +- ( 1 一 w 。 ) “ x a v g ( 2 . 3 ) 第二步: 利用得到的平均队列长度计算丢弃概率。 主动队列管理 ( 人q m)算法研究硕士论文 ， =- 丛 一 l ， 酬9 fre e 么 e 一 t i me) p. = 儿 + 呜( 2 . 8 ) 更 新 时 刻， l a s t 一 p d a t e=n 叮， 当链路空闲: i f ( ( no- 1 a s t -up d a t e ) fr e e z 免t i me) p 。 “ p 一 d :(2 . 9) 再 次更新当前时 刻，2 公 才 _ 即由翻 = 其 中fr eez e- t i 配参 数决 定 了 连 续 两 次 更改 值 的 最小 时 间 间 隔 ， 这 使 得凡在 下 一次 更 改 之 前， 上 一 次的 改 动 能 够 生 效 。 其中 风 峨， 风 和峨决 定 了p. 增 加 和减 少的幅 度。在实际算法实现时，可以 将包丢失和链路空闲事件取不同的值。 b i ju e算法基于分组丢弃和链路空闲来管理拥塞，能更好地估计 拥塞程度。因此 其标记分组的比 率比 较稳定， 这又使得其队列长度也相对稳定， 减少了时延抖动。 其 最大的贡献在于， 使用 相对较小的缓 冲区 就能够控制拥塞。 这样就减小了 端到端延迟， 提高了tcp 流的 吞吐最， 也使得路由 器有更多的自由空间来执行其他功能， 从而提高 了路由器的性能。 但是由 于 b l u e 算 法是根 据数据流占 有的网络带宽比 例丢弃数 据报， 它也将导致 不公 平的带宽分配。 而且由于b l u e 只有在包丢失情况下才进行概率 调整， 因此它无 主动队列管理 ( ao m)算法研究硕士论文 法 预 先察 觉 到 拥 塞。 另 外， bl ue算 法 中 的fr ee z e- ti me如 果设 置太 小 ， 会 导 致几变 化 过于 频 繁， 使 得 拥塞 管 理过 于 积 极 . 相 反 ， 如 果 设 置 太 大， 会 导 致几变 化过 于 缓 慢， 使得 拥塞管理过于 保守， 不能适应流量的变化，较难选择一个合适的平衡值。 鉴于b lue 算法的不 足之处， 许多 学者 提出了 在blue算法基础上的 改进算法， 其 中 较有影 响力的有mbl u e ， e b l u e ，fbl u e ( fai rb l u e ) 等。 2 . 1 . 3g k v q 和 人 v q算法 g i b b e n s 和k e l l y 最早提出t 虚拟队列( v i r t u a 1 que u e ) 概念， 并 将它 应用到 主动 队列的管 理中， 产生了gkvq 算法闻。 所谓的虚 拟队列是路由 器维护的实际 上并不 存 在的一种 逻辑队 列， 与其链接的 虚拟链路容量小于实际 链路容量， 而缓 存大小与实 际 队列相同。 当 有分组进入实际队列时， 更新虚 拟队列长度以 反映新分组的 到达。 如果 虚拟队列 溢出， 则标记或者丢弃实际队 列中的 分组。 因为vq 算法采用了 虚拟容量 ， 从理论上 来说， 链路利用率总小于c/c。 为了克 服这 一缺陷， 5 . k unniyu r 和r . s rik ant 提出了自 适应虚拟队列( adaptivev i rtua1 queu e ， a vq) 的主动队列管理 算法， 用简单 的微分方 程在线调整虚拟容量， 借助限 制因子的调整在高链路 利用率 和小队 列长度之 间实现适当的 平衡。具体算法11.j实现如下: 9= a (r c 一 幻表 示 虚 拟 队 列 容 t(2 . 10 ) 其中 c为 虚拟 队 列 容 量， a 为 限 制 因 子 ， 产 为 期 望 的 链 路 利 用 率 ， c 为 实际 的 链 路容量，又 为数据包到 达的速率。 当有数据包到达时，更新虚拟队列大小: 叩 卜功 a x ( 不 心一 c.(t 一 力 ， 0)(2 . 11 ) 其中 叩 为 虚拟 队 列 大 小， t 为当 前 包 到 达 时 间 ， 5 为 上 一 个 包到 达 的 时 间 。 if ( 叩 + b) b ;则标记或丢弃实际队列中的 数据包。 e l s e叩 十 不 叼 + b 其中b 为当 前数据 包中的字节数， b 为缓 冲区 大小。 更新虚拟队列容量: c+- 恤 面( c 护 + 哪 + c (t 一 5 ) ， 0一 a b ， 0)( 2 . 1 2 ) 更新上一次 包到达的时间:5 = t 。 基于虚拟队列的 a 朋 策略与 其他算法最显著的区 别在于它不需要计算分组丢弃 概率， 但 是它需要维护一个虚拟队 列， 对其进行队列长队和 容量的 更新， 这并没有降 低算法的复杂度，也是非常占用计算资源的。 硕士论文大时 海网络的主动队 列管理算法研究 2 . 1 . 4r e m ( ran d 饱 e x 伪n e t i a l场 甘 k i n g)算法 随 机指数标记佃】 ) 算 法由ath u r a l i y a s 最早提出， 该算法是基于流检测的拥塞 控制方 法， 它主要在主动队列管理中引 入了“ 价格” 的概念， 将网 络性能测量和拥塞 侧量分离， 通过分布式运算“ 价格” 对数据包进行标识。 而 l o w 将网 络的用户和链路 视为 分 布 计 算 系 统的 处 理 器 ， 将 系 统 优化问 题 转 化为 对 偶问 题明 ， 提出 了 运用 梯 度 下 降法进行求解。 在这种方法中， 发送端选择发送速率以 最大化其利益， 网络链路动态 调整其带宽代价以 协调源端的决策。 变量pri ce 作为拥塞程度的度量， 决定丢弃概率 的大小， 它的更新基于速率的不匹配( 聚合流的输入速率与端口 输出 速率 之差) 以 及队 列长度的不匹配( 实际队列长度与期望队列长度之差) 。 速率与队长的 关系实际上就类 似于市场经济中 需求与供给的关系， 利用“ 价格” 这个度量衡将它们联系起来。 其中 一种最常见的 价格函 数tlo形式为: pi (t 十 1) = inax 八 (t)十 了 ( 场 俪(t)一 ) + xl (t)一 cj (t )， 0)(2 . 13 ) 其中 y 0和al 0是 小的 常 数; q， (t)是 队 列1 在t 时 刻的 缓 存占 有全 ， 厉 0是目 标队 列 长 度， 场 (t)一 是 度 量 队 列 长 度匹 配 的 情 况; xl (t)是t 时 刻 进 入队 列1 的 总 输 入 童， cl (t)是t 时 刻 队 列1 的 可 用 带宽 。 xl (t)一 cl (t)是 度 量速 率匹 配的 情况 ; 当 进 入 缓冲 区的 分 组速 率 与 离开 缓 冲 区的 分 组 速率 匹 配时， 对列 长度qt (t )=盯， 链路 利 用 xl (t)二 cl ( t) 。 链 路1 的 丢 包 率 码与 价 格pi之 间的 指数 关系 是: 琳 (t)= 1 一 或 ” (t)(2 . 1 4) 其 中尹 是 一 个 大 于1 的 常 数， 那 么 整 个 端 到 端的 丢 包 概 率帆与 经 过 路 径 上 所 有 链 路价格和也成指数关系: 一 艺 几 ( ) 码 (t 少 =1 一尹 二 ( 2 . 1 5 ) 从而源端可以 通过探测丢失 的分组 来判断网络的 拥塞状况， 来采取相应的 速率控 制机制，从而实现对网络拥塞的控制 。 2. 2 启发式主动队列管理算法的不足 通过上文算法的原理分析以 及下文第五章的网络仿真可以 发现，基于启发式的 a 伽算法研究都是基于实验 仿真， 然后根 据专家经验， 采用启发式的思想进行参数的 调整以 及算法的改 进。 这样缺乏有效的 理论指导， 有很大的随机性 和人为因素， 控制 往往达不到预期的 效果， 而且不适合精确分析和进一步的算法改 进。 因此， 就迫切需 主动队列管 理 ( a q m)算法研究硕士论文 要建立一套系统的理论体系来指导八 朋机制的 研究。 而控制理论正是这样一种成热的 理论体系，它有很多策略和方法可以借鉴到拥塞控制中。 2. 3控制理论对网 络拥塞控制发展的影响 近些年来， 系统控制理论和非线 性规划理论被引入到 拥塞控制的研究中 来， 许多 研究者致力于尝试使用严格的数学模型来描述端系统和中间设备( 如路由 器和交换 机) 组成的