（计算机应用技术专业论文）多路径传输中乱序与负载均衡研究.pdf

浙江大学硕士学位论文 摘要 摘要 多径传输使用多条连接流分割节点和流汇聚节点的路径进行传输。相对于传 统的单径传输，多径传输具有充分利用网络资源、减少拥塞、提高传输可靠性和 提高网络的安全性等优点，是近几年网络领域的一个研究热点。但是由于每条并 行路径的传输延迟存在差别，因此从流分割节点按序发出的包到达流汇聚节点时 可能是乱序的；此外，在多条并行的路径上传输数据包存在流量在各条路径间的 负载均衡问题；而乱序和路径间的负载不均衡都会给传输速率、服务质量和网络 资源的利用率等带来不利影响，因而对保证包有序和实现负载均衡的流量分割算 法的研究具有重要的意义。 目前多径流量分割算法的研究主要集中在包有序和路径间的负载均衡其中 的一个点上，即使有少量的算法是两者都关注到，并且在保证包有序的基础上实 现了一定程度的负载均衡，但由于流分割的粒度过于粗糙，其负载均衡性不是很 好。本文首先分析了乱序对网络性能带来的不利影响，然后介绍了目前已经提出 的几种多径流量分割算法，并分析了它们的优缺点。在此基础上，本文提出了一 种新的流量分割算法，其在保证包有序的同时，尽可能细粒度地在路径间分割流 从而很好地实现路径间的负载均衡。该算法主要通过构建用作可用路径延迟底线 的游标来实现，游标主要取决于两个参数一当前路径传输延迟和相邻包到达流分 割节点的时间间隔，它作为选取路径的延时基线来保证包到达的有序性；游标会 随着每次选取的路径不同或相邻包到达流分割节点的时间间隔不同而动态地滑 动，通过动态滑动游标使得尽可能多的路径可用来传输当前包，从而很好地实现 负载均衡。通过对目前已经提出的流量分割算法和基于游标的流量分割算法进行 跟踪驱动模拟，仿真结果表明，与已有的保证包有序的流量分割算法相比，本算 法使负载更加均衡。 关键词：多径，乱序，负载均衡，游标 浙江大学硕士学位论文 a b s t r a e t a b s t r a c t m u l t i p a t ht r a n s m i s s i o n ，u s i n gs e v e r a lp a t h sb e t w e e nt h ed i v e r g i n gp o i n ta n dt h e c o n v e r g i n gp o i n t ，i su s e dt ot r a n s m i tp a c k e t c o m p a r et ot h et r a d i t i o n a ls i n g l ep a t h t r a n s m i s s i o n ，m u l t i - p a t ht r a n s m i s s i o nc a nm a k et h eb e s to fn e t w o r kr e s o u r c e s ，r e d u c e t h ec o n g e s t i o n ，i m p r o v et h et r a n s m i s s i o nr e l i a b i l i t ya n ds e c u r i t y , e t c t h e r e f o r e ，i ti sa r e s e a r c hh o t s p o ti nn e t w o r kf i e l d b e c a u s eo ft h ed e l a yd e f e r e n c eb e t w e e nt h ep a r a l l e l p a t h s ，t h ep a c k e t sr e a c h i n gt h ec o n v e r g i n gp o i n tw i l lb eo u to fo r d e rw h i l et h e ya r e s e n to r d e r l ya tt h ed i v e r g i n gp o i n t ；i na d d i t i o n ，m u l t i p a t ht r a n s m i s s i o nw i l lp r e s e n t s o m ep r o b l e m sa b o u tl o a db a l a n c i n ga m o n gt h ep a t h s ；f u r t h e r m o r e ，r e o r d e r i n ga n d u n b a l a n c e dl o a dh a v ea d v e r s ee f f e c t su p o nt r a n s m i s s i o nr a t e ，q u a l i t yo fs e r v i c e ，t h e u t i l i z a t i o nr a t eo fr e s o u r c e s ，e t c s o ，i ti sb eo fg r e a ts i g n i f i c a n c et od os o m er e s e a r c h o nt r a f f i cs p l i t t i n ga l g o r i t h m ，w h i c hc a ng u a r a n t e et h eo r d e ro fp a c k e t sa n dr e a l i z et h e l o a db a l a n c i n g a tp r e s e n t ，t h ei s s u eo fr e s e a r c h i n go nt r a f f i cs p l i u i n ga l g o r i t h mm a i n l yf o c u s e s o no n eo ft h et w op o i n t s ，g u a r a n t e e i n gt h eo r d e ro fp a c k e t sa n dl o a db a l a n c i n g ， a l t h o u g hl i t t l eo ft h e mf o c u so nt h e mt o g e t h e r , t h ep e r f o r m a n c eo fl o a db a l a n c i n gi s n o tv e r yg o o db e c a u s eo ft h ec o a r s eg r a i no ft r a f f i cs p l i t t i n g t h i sp a p e rf i r s ta n a l y z e s t h ea d v e r s ee f f e c t su p o nt h en e t w o r kp e r f o r m a n c er e s u l t e df r o mo u to fo r d e r , a n dt h e n i n t r o d u c e ss e v e r a lt r a f f i cs p l i t t i n ga l g o r i t h m sa n da n a l y z e st h e i rm e r i t sa n df l a w s o n t h i sb a s i s ，t h i sp a p e rp r o p o s e san e wt r a f f i cs p l i t t i n ga l g o r i t h m ，w h i c hc a na c h i e v e g o o dl o a db a l a n c i n gb ys p l i t t i n gt r a f f i ci n t of l o ws l i c e sa sf i n e g r a i n e da sp o s s i b l e t h e n e wa l g o r i t h mi sm a i n l yc a r r i e do u tb yc o n s t r u c t i n gan o n i u sw h i c hc a nb eu s e da sa b a s e l i n eo fp a t hl a t e n c y t h en o n i u s ，w h i c hi su s e dt og u a r a n t e et h eo r d e ro fp a c k e t s ， m a i n l yd e p e n d so nt w op a r a m e t e r s ，t h ep a t hl a t e n c ya n dt h ei n t e r v a lb e t w e e nt w o s u c c e s s i v ep a c k e t s t h en o n i u sc a ns l i d ed y n a m i c a l l yb e c a u s eo fd i f f e r e n tp a t ho rt h e d i f f e r e n ti n t e r v a lb e t w e e nt w os u c c e s s i v ep a c k e t s b ys l i d i n gd y n a m i c a l l y , t h ep a c k e t c a nb et r a n s m i t t e da m o n ga sm a n yp a t h sa sp o s s i b l e ；a sar e s u l t ，t h el o a db a l a n c i n gc a n b ea c h i e v e d t h r o u g ht r a c ed r i v e ns i m u l a t i o no ft h et r a f f i cs p l i t t i n ga l g o r i t h mb a s e do n 浙江大学硕士学位论文 a b s t r a c t n o n i u sa n do t h e re x i s t e dt r a f f i cs p l i t t i n ga l g o r i t h m s ，t h es i m u l a t i o nr e s u l t ss h o wt h a t t h ep r o p o s e da l g o r i t h mg a i n sap r o m i n e n ti m p r o v e m e n ti nl o a d b a l a n c i n go v e r p r e v i o u sa l g o r i t h m s ，w h i l ew i t h o u tr e o r d e r i n gi sg u a r a n t e e d k e y w o r d s ：m u l t i p a t h ，w i t h o u tr e o r d e r i n g ，l o a db a l a n c i n g ，n o n i u s 浙江大学硕士学位论文图目录 图目录 图2 1 多径传输乱序8 图2 2 乱序感知流程1 0 图2 3t c p 拥塞避免算法1 3 图3 1 按包轮循转发18 图3 2 差额轮循选路1 9 图3 3 差额轮循选路算法2 0 图3 4 按目的地址前缀选择路径2 l 图3 5h a s h 值到路径的映射2 3 图3 6 按源宿地址选路流程2 3 图3 7 流信息记录2 5 图3 8 流分片一2 7 图3 9 流分片与路径映射表一2 8 图4 1 流量分割与选路单元3 2 图4 2 路径传输延迟和游标3 3 图4 3 包有序的路径选择3 4 图4 4 流分片一3 5 图4 5 同一流中相邻包的传输3 6 图4 6t s b n 算法处理流程一3 9 图4 7 延迟探测包与应答包一4 l 图4 8 延迟探测应答包交换4 1 图4 9 剩余带宽探测包与应答包一4 3 图4 10 剩余带宽感知4 3 图5 1 实验拓扑结构一4 9 图5 2 实验数据流图5 l 图5 3 流的大小与分片数5 2 图5 4 分片大小占总流量的累积分布函数5 3 图5 5 负载失衡度5 4 i i i 浙江大学硕士学位论文表目录 表目录 表4 1 路径信息表3 7 表4 2 游标表3 8 表4 3 按时间段的期望配额表4 2 表5 1t r a c e 数据信息4 9 表5 2 分片到达速率5 2 i v 浙江大学硕士学位论文第l 章绪论 第1 章绪论 1 1 课题背景 自从1 9 6 9 年作为互联网始祖的a r p a n e t 诞生以来，互联网就一直处于高 速发展的状态。特别是近几年来，随着计算机处理能力的不断增强和新业务的不 断涌现，互联网在新需求的驱动下正在向更快、更可靠和更安全的方向发展，传 输的业务由原来单一的文本和图片传输逐渐发展成为以文本、图片、语音和实时 多媒体为主体的综合业务传输。这些新的业务不但对传输的可靠性和带宽提出了 更高的要求，而且对传输的实时性也提出了不同的需求。 长期以来，人们一直在为提高传输的可靠性和带宽不断地升级网络，但却始 终赶不上新业务需求的增长，并且大大提高了网络复杂度。然而，与不断升级的 网络和不断涌现的新业务相比，早期采用的单条路径传输方法却很少改变，在今 天的互联网中仍然是传输方法中的主流。目前，互联网中使用的路由协议主要有 两类：内部网关协议( i n t e r i o rg a t e w a yp r o t o c o l s ，i g p s ) 和外部网关协议( e x t e r i o r g a t e w a yp r o t o c o l s ，e g p s ) ，内部网关协议用作自治系统内的路由，外部网关协议 用作自治系统间的路由。内部网关协议主要包含i p 的r i p ( r o u t i n gi n f o r m a t i o n p r o t o c 0 1 ) 和o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 、o s i 的i s is ( i n t e r m e d i a t es y s t e mt o i n t e r m e d i a t es y s t e mp r o t o c 0 1 ) ，r i p 采用跳数最少的路径进行传输，o s p f 和i s i s 采用最短路径进行传输，因此都是采用的单条路径传输方式；外部网关协议主要 包含i p 的b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 和o s i 的i d r _ p ( i n t e r - d o m a i nr o u t i n g p r o t o c 0 1 ) ，它们都是依据设定的策略选取多条路径中的一条路径进行传输，因此 也都是采用单径传输方式。这样，一方面人们在为满足带宽需求而不断增加网络 容量，另一方面却由于采用单径传输而浪费了许多带宽。 单径传输由于只采用了一条路径进行传输，当该路径上的节点或链路出现问 题时，传输将被中断，直到新路径建立成功后才能继续传输，因此可靠性较低， 并且会引起服务质量的下降和传输抖动；由于所有数据在同条路径上传输，攻 浙江大学硕士学位论文第l 章绪论 击者比较容易窃取通信双方的所有交互信息，攻击也就比较容易得逞，因此安全 性比较差；单径在构建时总是趋向于选取最短路径或当前拥塞最小的路径，所有 共享两个节点的所有路径都会选取这两个节点问的相同路径段，从而使得很多流 量都流向相同的路径或路径段，最终造成部分路径或路径段拥塞很严重而其他并 行路径或路径段却很空闲，不利于拥塞避免和充分利用网络资源，也不利于提高 服务质量。 相对于单径传输，多径传输将流量分配到多条并行的路径上进行传输，能充 分地利用网络资源和减少拥塞【l l ；当其中一条路径失效时，通过将该路径的流量 份额平滑过渡到其它并行的路径上去，对于用户来说不会出现断网或因路径失效 而产生传输抖动，因此提高了端到端的传输可靠性、降低了网络上的负载波动和 增大了网络吞吐量【2 】；通过将通信数据分配到不同的路径上进行传输，使得网络 攻击者必须截取多条路径上的数据才能取得完整的数据，提高了攻击难度，因此 提高了网络的安全性1 3 j 。 早在1 9 9 9 年，s t e f a ns a v a g e 等人【4 】就通过实验研究表明：在单条路径传输过 程中，有3 0 一8 0 的情况存在比所选路径更优的路径可被用来传输数据；在2 0 0 3 年，r e n a t at e i x e i r a 等人1 5 j 的研究结果表明：9 0 的点对点连接( p o p ) 存在至少4 条并行路径，4 0 的点对点连接存在至少8 条并行路径。从这些研究结果可以看 出，在互联网中大量存在可以用来传输数据的并行路径，这些都为我们研究和应 用多径传输提供了依据和可能。 由于多径传输存在诸多优点并且多径在现实网络中确实是存在的，越来越多 的多径传输应用出现在互联网中，与多径传输技术相关的研究也成为了近期网络 领域中的一个研究热点。在协议研究方面，e c m p ( e q u a l c o s tm u l t i p a t h r o u t i n g ) 6 】【7 】【8 】是一种非常简单的多径路由算法，但由于不能适应多径路由带宽的 动态变化和负载均衡性较差，c u r t i sv i l l a m i z a r 等人【9 】【1 0 】【l l 】提出了 o s p f o m p ( o p l t i m i z e dm u l t i p a t h ) 、i s i s o m p 和m p l s o m p ，通过依据各路径负载 情况动态调整流量在路径间的分配，从而使得多径传输负载更加均衡。在应用方 面，目前比较成熟的m p i 。s ( m u l t i p r o t o c o ll a b e ls w i t c h i n g ) 多径传输技术在m p l s 2 浙江大学硕士学位论文第l 章绪论 流量工程中得到了较多的应用；在虚拟网构建时，需要将多条底层连接两节点的 多条并行链路虚拟成一条需链路，与这个过程相反的是，当在虚链路上传输数据 流时，需要将流量合理分配到各条路径来完成，即底层必需采用多径传输方法来 实现一条虚拟链路上的传输【1 2 1 。 为了改变长期以来通过增强节点处理能力、增大链路传输带宽和使用复杂协 议和网络控制算法来适应不断出现的新需求的状况，文献【1 3 探索了一种面向服 务提供的新型网络技术体系，在该体系中，通过对业务按特性进行聚类来屏蔽各 个具体业务的细节特性，再根据聚类的属性为用户构建一体化逻辑承载网【1 4 】【l5 1 。 在一体化逻辑承载网的构建过程中，首先将业务按其特性进行聚类，然后根据用 户的带宽需求和聚类在物理网络上的源节点和目的节点间构建一个逻辑网络，逻 辑网中采用资源预留方式保证服务质量、采用多条并行的物理路径来实现资源充 分利用和尽可能多的逻辑网能被构建，在逻辑网的接入节点控制其流量从而保证 逻辑网中不会有拥塞出现，因此各条路径的传输延迟比较稳定。 与单径传输不同，在多径传输过程中，包在多条路径上进行传输，包由于在 不同传输延迟的路径上进行传输，因此可能会引起乱序；此外，流在不同路径间 分割也提出了负载均衡问题。 1 2 研究内容 采用多径传输会引起包乱序问题，而乱序会对服务质量和资源利用率带来的 许多不利影响，并且对于不同应用和不同的传输层协议产生的影响又有差别，分 析多径传输过程中乱序产生的原因以及乱序的危害对于多径传输等网络中的并 行处理研究具有重要的指导意义。 存在负荷共享情况就存在负荷均衡方面的问题，在多径传输中也不例外。采 用多径传输的原因之一是提高资源利用率，如果不能很好地均衡路径间的负载， 出现负载集中在少数路径上而其它可用路径却很空闲的情况就违背了采用多径 传输的初衷。本文在参考了多篇文献的基础上，通过对现有的各种多径负载均衡 算法进行分析对比，充分考虑各条路径间传输延迟差与属于同一流的相邻包到达 浙江大学硕士学位论文第l 章绪论 间隔之间的关系，提出了一种在保证包不乱序前提下的多径负载均衡算法，并通 过仿真对该算法的性能进行了分析。 1 3 研究意义 多路径传输具有的能增大吞吐量、提高服务质量、减少拥塞和提高网络安全 性等优点，正好与互联网朝着大流量、高服务质量和高安全性方向发展相一致， 因此对于多径传输的研究具有重要的现实意义。在一体化逻辑承载网的底层网络 中采用的是多径传输，因此对于多径传输的研究对于一体化逻辑承载网的研究具 有重要意义。 深入研究了多径传输中路径传输延迟、流量分割、包选路与包乱序之间的关 系，为防止包乱序提供了理论依据。 通过对乱序的危害进行分析，使得人们对乱序带来的各种问题有了更全面的 认识，这不仅对以后的多径传输研究和应用具有重要的指导意义，而且对多处理 器路由器等可能引起乱序的研究有重要意义。 研究了当前的各种流量分割方法及其负载均衡能力，并且提出了一种新的流 量分割算法，该算法使包在不乱序的前提下尽可能地实现负载均衡，不仅对于以 后的多径传输研究具有重要的参考价值，而且对于一体化逻辑承载网和虚拟网中 的路径问负载均衡具有重要的实践意义。 1 4 论文组织 本文共分为六章。第二章分析了乱序及其危害，主要分析了乱序产生的原因， 乱序的几种感知方法，乱序对于常见的传输层协议t c p 和u d p 性能带来的不利 影响；第三章介绍了现有的几种多径流量分割算法，对按包、按应用特性、 o s p f o m p 、按流、按流片等现有的几种主要多径流量分割算法进行了介绍和分 析，并从实现复杂度、包的有序性和负载均衡能力三方面进行了比对；第四章介 绍了本文提出的一种新的基于游标的流量分割算法，先对算法相关的一些基本概 念进行了解释，再对算法的理论基础进行了分析，并在此基础上对算法的具体实 现和算法的参数获取进行了详细地阐述，此外还对算法的稳定性进行了分析；第 4 浙江大学硕士学位论文第l 章绪论 五章进行了仿真与性能评价，通过采用跟踪驱动模拟方法对基于游标的算法与其 它算法进行了仿真，并对它们的结果进行了比对和分析，仿真结果表明了新的算 法在保证包有序性的前提下能更好地实现路径间的负载均衡；第六章为总结和展 望。 浙江大学硕士学位论文 第2 章乱序及其危害分析 第2 章乱序及其危害分析 2 1 乱序 在t c p 传输过程中，每个数据段的t c p 头部中都包含有一个3 2 位的序列号， 该序列号被用于表示当前数据段中第一个字节在数据流中的位置；然而，在u d p 传输过程中，由于u d p 是一种无连接、不可靠的传输协议，它本身不提供标识 数据段顺序的序列号，采用u d p 协议的应用程序为了唯一标识每一个数据段， 只能由应用程序为每一个应用数据包分配一个序列号。 包乱序【1 6 】【1 7 1 是指序列号大的包先于序列号小的包到达接收端。包乱序是一种 众所周知的现象，并且其数量还在不断上升1 8 】【1 9 1 1 2 0 】；特别在2 0 0 0 年末，j d u f 每2 1 】 的研究表明当网络上的负载比较大时会引起严重的乱序，这也引起了人们对乱序 的极大关注。 将接收到的报文段序列号按照收到的时间顺序排成一个数列，报文序列号的 逆序数称为报文的乱序深度，如：接收到的序列号为别为( 3 ，2 ，4 ，5 ，1 ) ，则序列 号为2 的报文的乱序深度为1 ，而序列号为1 的报文的乱序深度为4 ，其它三个 包的乱序深度为0 。乱序报文按照乱序深度大小分为深乱序报文和浅乱序报文1 2 2 1 。 当接收端收到一个乱序报文时，为了告知发送端自己已经接收到乱序包和期望接 收包的序列号，将立即发送一个重复应答( ad u p l i c a t ea c k ，d u p a c k ) 。在收当三 个重复应答后，t c p 的快速重传算法则认为报文已经丢失，将重传该报文并触发 拥塞控制算法，这种乱序深度大于3 的乱序报文称为深乱序报文，乱序深度小于 等于3 的乱序报文则称为浅乱序报文。 2 2 乱序的原因 引起包乱序的原因很多，根据乱序发生的位置不同可分为在发送端产生乱序 和在网络中产生乱序。 6 浙江大学硕士学位论文第2 章乱序及其危害分析 2 2 1 在发送端产生乱序 发送端重传报文段会引起乱序【2 3 1 。当发送端的发送定时器超时或者在收到多 个重复a c k 之后，发送端会认为该报文段已经在传输过程中丢失，然后重传该 报文段；对于超时重传，该重传报文段到达接收端的时间会比超时期间发送的序 列号更大的报文晚；对于多个重复a c k 引起的重传，在重传之前就已经有序列 号更大的报文到达接收端，当重传报文到达接收端时肯定是乱序的；因此，无论 哪一种情况都会引起该重传报文乱序。 2 2 2 在网络中产生乱序 在互联网中，i p 层提供的是无连接、不可靠的数据包传输服务 2 4 1 1 2 5 1 ，只是尽 力将数据包传送给接收端的i p 层，再由接收端的i p 层向上传递给传输层，整个 过程中没有对包的传输顺序进行处理，并行传输、路由变化、路由器内部的并行 处理都可能引起乱序。 在多条路径上传输数据时，为了使路径间的负载更加均衡，相邻包可能会在 不同的路径上进行传输，而不同路径的传输延迟通常不相等，因此采用多径传输 可能会引起乱序1 2 6 】【2 7 1 。如图2 1 所示，假设路径r s r d 的传输延迟小于路径 r s r 1 一r d 且路径r s r 1 一r d 的传输延迟小于路径r s r 2 r 3 一r d ，当属于同 一个流的三个包( 包l ，包2 ，包3 ) 按序从源节点发出时，由于3 个包所走路径的 传输延迟不一样，它们到达目的节点的顺序变为( 包2 ，包1 ，包3 ) ，包1 发生了 乱序。 采用区分服务等优先调度方法将引起乱序1 2 8 1 2 9 1 ，当执行快速转发时 ( e x p e d i t e df o r w a r d i n g ) ，对于满足预定带宽要求的流优先进行处理，但是当流 量超过预定带宽限制时，对于流量超过的数据包，一种方法是将其丢弃，另一个 方法是不将数据包丢弃而是降低其优先级，这样相邻的包就会被放入不同的队列 进行处理，由于优先级高的队列优先处理，因此先前被降低优先级的包可能比后 到来却进入了高优先级的包更晚被处理，这样就会产生包乱序。 在m a n e t ( m o b i l ea d h o cn e t w o r k ) 网络中，由于网络节点会频繁移动，并且 7 浙江大学硕士学位论文第2 章乱序及其危害分析 网络节点的能量有限，因此其路由会频繁地变化；当两节点间的路径传输延迟由 长变短时，路由变化前发送的包可能会比路由变化后发送的包晚到达目的节点， 即产生了乱序【2 引。 l也i妈 图2 1 多径传输乱序 为了提高路由节点的处理速度，作为路由器核心的网络处理器通常采用单芯 片多处理器的体系结构，其关键部分为多个处理单元( p e ，p r o c e s s i n ge l e m e n t ) ，每 个处理单元都是一个独立的微处理器；在路由器内部，多个线程并行运行，每个 线程处理一个报文，并行处理在提高报文处理速度的同时，也会由于内存请求挂 起等原因致使包转发时间不一致而引起包乱序【2 7 】【3 0 1 【3 l 】，j b e n n e r 等人对 m a e e a s ti s p 交换中心的升级前后分别进行了报文乱序测量，测量结果表明在 系统升后，报文乱序概率由升级前的很低一跃超过9 0 ，这些结果都充分表明了 路由器内部的并行处理会引起包乱序。 2 3 包乱序感知方法 当接收端接收到比以前报文序列号更小的报文时，接收端就感知到了乱序； 然后接收端再发送一个重复a c k 给发送端，当发送端收到一个重复a c k 时，也 感知到了乱序。文献【3 2 】根据序列号的单调增加和t c p 的重复a c k 来感知乱序。 8 浙江大学硕士学位论文第2 章乱序及】危害分析 2 3 1 序号单调增加法 在接收端，如果接收到数据包的序列号是单调增加的，那么数据包是按序到 达的，否则就发生了乱序。基于这个原理，我们可以采用公式( 2 1 ) 所示的方法来 感知乱序包，其中t 表示接收端接收到数据包的时间，s 表示报文段的序列号， p 表示报文段。 死 t j 姐s k s j ( v i ，川 公龆1 ) jp k 乱序 、。 2 3 2 重复a c k 法 在发送端，如果重复收到请求某个报文的a c k ( 重复a c k ) ，那么表示数据包 发生了乱序或者发生了丢包；在t c p 中，三个重复的a c k 被认为数据包已经丢 失，会快速重传该数据包，重复a c k 法用于判断是否触发快速重传算法。基于 这个理论，在接收端可以采用公式( 2 2 ) 所示的方法来感知包乱序。 s ， s j - , i s i s i - 2 且s i s i - 3 ( v i ) 公龆2 ) jp i 乱序 、。 序列号单调增加法的理论基础是乱序的基本概念，它是一种直观、简单的乱 序判断方法，基础适合于接收端使用；此外，不论是深乱序还是浅乱序，序列号 单调增加法都能准确地判断，并且可以用这种方法准确地计算出乱序比例和乱序 密度( i m ，r e o r d e rd e n s i t y ) 2 9 1 。序号单调增加法的处理流程如图2 2 所示。与序列 号单调增加法相比，重复a c k 法由于主要用于t c p 快速重传的判定，不能判别 出浅乱序，也不能准确地计算出乱序密度和乱序比例，适用于类t c p 的包乱序感 知，女口：t c p 矛口s c t p ( s t r e a mc o n t r o lt r a n s m i s s i o np r o t o c 0 1 ) 。 9 浙江大学硕士学位论文 第2 章乱序及其危害分析 图2 2 乱序感知流程 2 4 乱序的危害 t c p i p 协议栈共分为五层，从下至上分别为：物理层，数据链路层，网络层， 传输层和应用层。物理层只负载数据位的传输。数据链路层只负责将每一帧按其 物理地址进行传输。网络层负责在互联的网络中进行选路，将每一个i p 包由源端 送达目的端。传输层提供一种端到端的服务，在发送端的传输层中需要进行拥塞 控制，在目的端的传输层中，面向连接的t c p 协议需要对接收到的包发送应答或 重复应答，并且对包在缓冲区中进行排序，排好序后才能传递给应用层，因此会 受到乱序的影响；虽然u d p 提供的是无连接、不可靠传输层服务，拥塞和乱序 完全由应用层进行控制和处理，但由于现在应用层业务种类很多，并且新的应用 l o 浙江大学硕士学位论文第2 章乱序及其危害分析 层协议也随着新业务的涌现而在不断地制定，因此本文将按照传输层的常用协议 对乱序的危害进行分析。 2 4 1 乱序对t c p 性能的影响 传输控制协议( t r a n s m i s s i o nc o n t r o lp r o t o c o l ，t c p ) 位于t c p i p 协议栈的传 输层，为应用层提供一种可靠的、面向连接的字节流服务。面向连接是指两个t c p 应用程序在进行数据交换前必须要通过三次握手建立连接，数据传输完成后要通 过四次握手来完全断开连接。t c p 在保证传输的可靠性的同时，其保证可靠性的 机制也正好使得其在遇到报文段乱序时更加脆弱，用来保证可靠性的机制【3 3 】及其 受乱序的影响分析如下： 1 应用层传来的数据被分割成一个个小的数据块，数据块的大小是t c p 认 为最适合发送的大小，给数据块加上t c p 头部封装成报文段( s e g m e n t ) 后 再传递给i p 层进行传输。由于应用层数据的分块传输，当各分块走不同 延迟的路径时，数据块到达接收端可能是乱序的。 2 当接收端的t c p 层收到一个报文段时，经过一定延时后会发送一个确认 a c k ，a c k 数据包的t c p 包首部中包含了一个3 2 位的确认序列号，该 确认序列号是接收端期望收到的下一个序号，其值为当前已经完整接收 到报文段的数据字节数加上1 ，并且将t c p 包首部中的a c k 标志位置1 ， 这样发送端就可以知道哪些数据包已经成功送达接收端。由于每收到一 个数据报都要发送一个a c k ，因此当序列号大的包到达接收端而序列号 小的包没有到达时，这样接收端就会发送重复a c k ，重复a c k 用于告 知对方收到一个乱序的报文段，并将自己期望接收的报文序列号告知对 方，重复a c k 不会象正常的a c k 那样需要经过一定延时才发送，它是 在接收到乱序报文时立即发送的。当收到多个重复的a c k 时，发送端会 误认为是丢包引起的并重新发送该确认序列号指定的包，这提供了丢包 的快速重传功能，同时也会引起因乱序而错误重传的问题。 3 由于i p 数据报在传输中可能会乱序到达接收端，而位于传输层的t c p 浙江大学硕士学位论文第2 章乱序及其危害分析 报文段又只能通过l p 数据报进行传输，因此t c p 报文段也有可能是乱 序到达接收端的。t c p 对接收到的数据在缓冲区中进行重新排序，然后 将排好序的数据以正确的顺序提交给应用层。由于在缓冲区中对数据进 行排序，因此当乱序发生时，可能存在除排在第一的包外其余的包都已 经到达的情况，所有的已到达包都只能存在缓冲区中而不能提交给应用 层，当缓冲区占满时，后面的t c p 传输就不能继续进行，这样既影响了 应用程序的性能，也将因t c p 传输不能继续进行而影响到网络资源的利 用率。 4 在发送端和接收端都为t c p 分配了固定大小的缓冲区，为了防止发送端 发送过快而接收端接收过慢致使接收端缓冲区溢出的问题，t c p 提供了 流量控制功能，接收端通过告知发送端其剩余的缓冲区大小，发送端将 其发送的流量限制在该缓冲区大小之内从而防止溢出。 5 为了提高传输速率和降低拥塞，t c p 采用了慢启动和拥塞避免机制来控 制发送速率。慢启动和拥塞避免在每个连接上都维护了两个变量：拥塞 窗1 2 1 ( c o n g e s t i o nw i n d o w , e w n d ) 和慢启动门槛( s l o ws t a r tt h r e s h o l d ， s s t h r e s h ) 。当c w n d 小于等于s s t h r e s h 时，即处于慢启动阶段，每收到一 个a c k 就将c w n d 增加一个包的大小，因此c w n d 呈指数据增长；当c w n d 大于s s t h r e s h 时，即进入拥塞避免阶段，每一个a c k 只将c w n d 增加 1 c w n d ，每个r t t 之内最多增长一个报文的大小。t c p 拥塞避免算法如 图2 3 所示，收到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 的值，即c w n d 置为拥塞之前的一半； 此外，进入拥塞避免阶段，每一个a c k 只将c w n d 增加1 c w n d ，每个 r 1 r t 之内最多增加一个报文的大小，这将大大降低传输速率。因此，如 果发生深乱序时，t c p 传输性能将大大降低。 1 2 浙江大学硕士学位论文第2 章乱序及其危害分析 图2 3 t c p 拥塞避免算法 1 3 浙江大学硕士学位论文第2 章乱序及其危害分析 t c p 采用缓冲区来解决发送过快而接收过慢问题，并且是将数据排好序之后 才传递给应用层，如果有比缓冲区中收到报文序列号更小的报文没有收到，比未 收到报文序列号大的报文段数据只能存放在缓冲区中，不能传递给应用层，基于 这个原因，y ex i a 等人【3 4 】分析了t c p 为将乱序报文重新排序所需要的缓冲区大 小和因此而产生的报文延时情况，分析结果表明乱序报文段的重新排序需要很大 的缓存，对t c p 端系统的缓存容量有较高的要求，这对于资源有限的嵌入式设备 提出了较高的要求；此外，由重新排序引起的报文延时也很显著，并且延时与分 组大小和t c p 连接的吞吐率有密切的关系，在分组较小和吞吐率较高的情况下， 乱序将对应用层的性能产生严重的影响。 文献 2 7 】研究了h s t c p i ”j ，b i c 3 6 】等几种高速网络中包乱序的特性以及包乱 序对高速网中t c p 传输速度的影响，仿真实验通过设置不同的乱序间隔、乱序延 时和乱序块大小三个参数来观察t c p 传输性能的变化，实验结果表明：乱序间 隔越小，吞吐量这越小；当乱序间隔小于o 0 2 秒时，b i c 的吞吐量急剧下降；h s t c p 受乱序的影响大于b i c 的影响；并最终得出了包乱序使得各种高速网络的t c p 传输性能变得很差的结论。文献【3 7 的研究表明乱序会严重降低端到端的传输性 能。由于多次重传，r 1 r t 就不能得到及时采样从而降低r 1 r r 的估计准确度【3 8 】【3 9 j 。 2 4 2 乱序对u d p 性能的影响 与t c p 不同，u d p 是一种简单、面向数据报的传输层协议，不提供重传和 拥塞控制功能，是一种不可靠无连接的协议，传输的可靠性需要由应用层来保障。 u d p 应用进程的一次输出操作只产生一个u d p 数据报，该u d p 数据报再封装成 一个i p 数据报，因此输出操作的u d p 数据报长度会受到i p 数据报的最大长度的 限制，而i p 首部总长度字段为1 6 比特，即i p 数据报的最大长度为6 5 5 3 5 个字节， 去除2 0 个字节的i p 头部和8 个字节的u d p 头部，u d p 应用进程一次输出操作 输出数据的最大长度为6 5 5 0 7 个字节。 由于u d p 不提供拥塞控制，因此用户数据能尽可能快地送达接收端而不考 虑丢包和网络拥塞情况，此外，u d p 也不会在接收端对乱序包进行重新排序，这 1 4 浙江大学硕士学位论文第2 章乱序及其危害分析 正好适用于数据包晚到达等同于丢包的实时应用数据传输。文献 3 8 1 的分析表明 对于象v o l p 这样的u d p 应用，在播放时间点之后到达的乱序包将作为丢包处理， 这使得接收端的声音质量降低，出现声音断断续续的现象，并且浪费了网络接口 卡和处理器等资源。除了对乱序包作丢包处理之外，当前常用的另一种方法是对 于延迟不是太大的乱序包进行缓存，等乱序包在缓存中排好序后再交给解码器等 进程进行处理；但是接收端的缓存将随着乱序程度、范围增大以及应用程序的位 率增加而增加，比如：基于i p 的视频传输就比基于i p 的声音传输需要更大的缓 存空间。接收端缓存地增加将对接收设备提出更高的要求，对于资源有限的嵌入 式设备，由于缓存空间的限制，过多的乱序包只能作为丢包处理，从而使服务质 量大大降低。 现在，u d p 常被用于传输面向流的数据，并且u d p 本身没有给发送端提供 接收到数据包的反馈，总是假设数据能按时按序到达。然而，文献 4 0 1 的研究表 明m p e g 4 这样的采用预测编码技术的数据流总是对数据包的有序性有很高的要 求，乱序将对这些应用的性能带来不利影响，比如：为了改进压缩率，预测编码 技术中在视频数据中引入了对时间的依赖，当发生丢包或乱序时会导致很大的解 码错误。此外，文献 4 0 】用w i n d o w s 媒体播放器作为分析工具，对乱序对视频质 量的影响进行了量化分析，分析结果显示大量乱序将导致缓冲区溢出，最终使得 视频出现视频帧冻结现象。 采用u d p 传输视频等实时流时，如果乱序在应用层不加以处理就交给解码 器处理，将使得解码出来的图像严重失真，文献 4 1 】的测试表明过多的乱序包传 递给解码器会使得解码器死掉。 2 5 本章小结 当到达包的序列号数列出现逆序就表示产生了乱序。乱序产生的原因很多， 当发送端因超时或接收到多个重复a c k 后重传数据包会引起乱序；网路内部的 多径并行传输、路由器内部多处理单元和多线程等并行处理都会引起乱序，路由 变化也会引起包乱序。乱