（通信与信息系统专业论文）基于打包策略的拥塞及差错控制的研究与实现.pdf

华中科技大学硕士学位论文 = = = = = ；= = = = = = ；= = = = = ；= = = = = = = = = = = = = = = 一 摘要 f 随着i n t e m e t 的迅速发展，网络中不仅流量急剧增加，流量的性质也发生了很大 的变化。许多数据流( 如视频、音频数据等) 不能采用t c p 协议，而采用u d p 协议， 以保证数据的实时传输。这类流量的增加带来了不公平性和新的拥塞崩溃现象。同时， 随着网络技术的不断发展，现代远程教育希望找到一种适合的技术，使教师课件能够 在教学过程中同步的在学生机器上得到展示。实现这一功能最恰当的解决方案就是利 用屏幕共享技术。如何在这样一个带宽受限的环境下实现数据量较大的屏幕共享技 术，是当前研究远程教学系统的关键之一。土一一 本文在国家科技部技术创新基金项目( n o 0 0 c 2 6 2 2 4 2 1 0 6 4 1 ) - - “远程教学协同群 件产品”和国家教育部重点科学技术项目( n o 2 0 0 0 1 7 5 ) - - “现代远程教育关键技术： 交互式实时教学工具软件”的资助下，主要通过分析i p 网络中的u d p 流的特点，研 究了具有不同数据包大小的u d p 流对路由器性能产生的公平性以及效率的影响，提 出了一种基于数据包大小的拥塞及差错控制方案。为适应远程教育的需求，我们还在 编码层面提出了一种高效的屏幕图象压缩算法来实现屏幕共享。 经过对数据传输的研究，本文发现数据包的大小对路由器转发的公平性、发送端 与接收端的传输效率都有着较大的影响。通过对路由器在出现拥塞时的r e d 丢弃算 法中加入对不同大小数据包的区别，有效的提高了不同数据流之间的公平性。同时， 在考虑了不同大小的数据包在网络上传输的不同特性后，本文提出了一种通过更改数 据包大小来进行速率及差错控制的方案。 在压缩算法方面，本文在课题组提出的屏幕图象分块算法的基础上，通过对屏幕 图象进行分块，使用改进的图象块识别算法进行分类，再分别使用无失真压缩算法及 有失真压缩算法进行压缩，得到了比原有单一压缩方法有较大提高的压缩算法。 以上方案在经过研究及实验后，证明该方案比传统的传输算法在数据的到达率上 有了较大的提高。与改进后的压缩算法结合，较好的实现了广域网中的屏幕共享，已 被应用在了一种多媒体教学系统的屏幕共享功能模块中，并取得了较好的效果。 一 关键词：u d p 数据流； 共享，分块压缩，远程教学； a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，i n t e m e tt r a f f i ch a sn o to n l ya u g m e n t e di n v o l u m e ，b u ta l s oc h a n g e di nn a t u r e i no r d e rt oe n s u r et r a n s f e ri nr e a l t i m e ，m a n ys t r e a m s ( s u c ha s v i d e os t r e a m ，a u d i os t r e a me t c ) t r a n s f e ro v e ru d pp r o t o c o li n s t e a do ft c p p r o t o c 0 1 t h e i n c r e a s eo ft h i sk i n do ft r a f f i cc a nr e s u l ti nu n f a i r n e s sa n dd a n g e ro f c o n g e s t i o nc o l l a p s e a n d a tt h es a m et i m e ，w i t ht h ed e v e l o p m e n to f n e tt e c h n o l o g y , m o d e m d i s t a n te d u c a t i o nn e e d st os y n c h r o n i z ed i s p l a yt h ec o u r s e w a r ei nt h es t u d e n t sc o m p u t e r w i t hac o m p a t i b l et e c h n o l o g y ，t h ew a yt os o l v et h i sp r o b l e mi ss c r e e n - s h a r e dt e c h n o l o g y h o wt om a k es c r e e n s h a r e dt e c h n o l o g yi n t or e a l i t yu n d e rt h el i m i t e db a n d w i d t h ，i so n eo f t h ek e y p r o b l e m i nm o d e md i s t a n te d u c a t i o n i nt h i sp a p e r , u n d e rt h es u p p o r f r o mi n n o v a t i o nf o u n d a t i o no fc h i n an a t i o n a lm i n i s t r yo f s c i e n c ea n d t e c h n o l o g y f o rt h e p r o j e c t “c o o p e r a t i o n d i s t a n c e l e a r n i n gg r o u p w a r e ”( n o 0 0 c 2 6 2 2 4 2 1 0 6 4 1 ) a n dk e ys c i e n c ea n dt e c h n o l o g y t e r nf o u n d a t i o no fc h i n an a t i o n a le d u c a t i o n m i n i s t r y f o rt h e p r o j e c t “k e yt e c h n o l o g i e s i nm o d e md i s t a n c e l e a r n i n g ：i n t e r a c t i v e r e a l - t i m e e d u c a t i o ns o f t w a r et o o l s ”( n o 2 0 0 0 1 7 5 ) ，a f t e ra n a l y z e dt h ec h a r a c t e r so fu d ps t r e a m si ni p n e ta n dt h ee f f e c tt h a tt h eu d ps t r e a m so fd i f f e r e n tp a c k e ts i z em a k ei nr o o t e r , ac o n g e s t i o n a n de l i o tc o n t r o ls c h e m eb a s e do nt h ed i f f e r e n ts i z eo fp a c k e ti sp r o p o s e d a n df o rt h e r e q u i r e m e n to f d i s t a n te d u c t i o n ，ah i g he f f i c i e n c ys c r e e ni m a g ec o m p r e s s i o n a l g o r i t h mi s p r o p o s e do n t h ec o d i n g l a y e r b y r e s e a r c ho fd a t at r a n s f o r m ，w ef i n dt h a tt h es i z eo f p a c k e th a sm u c hi n f l u e n c eo n t h ef a i r n e s so fr o o t e ra n dt r a n s f o r me f f i c i e n c yb e t w e e ns e n d e ra n dr e c e i v e r t h ef a i r n e s s a m o n g t h ed i f f e r e n td a t as t r e a m si n c r e a s ea f t e rw ec o n s i d e rt h ep a c k e ts i z ei nt h er e d a l g o r i t h m a f t e rs t u d i e dt h ec h a r a c t e r so f d i f f e r e n tp a c k e ts i z ei nt h en e t w o r k ，w e p r o p o s e d ar a t ea n de r r o rc o n t r o ls c h e m eb y c h a n g et h es i z eo f p a c k e t i i 华中科技大学硕士学位论文 an e wi m a g ec o m p r e s s i o na l g o r i t h mi s p r o p o s e db a s e do nt h es u b - b l o c ka l g o r i t h m p r o p o s e db yt h eg r a d u a t e s s c r e e ni m a g ei sd i v i d e di n t of o u rs o r t so fb l o c k sb yc e r t a i n p r o v i d e d r u l e s f i r s t ，t h e n t h e s eb l o c k sa r e c o m p r e s s e ds e p a r a t e l yd e p e n d e do nt h e i r c h a r a c t e r i s t i cs oa st oe n s u r et h a tt h eq u a l i t yo f r e c o v e r yi m a g ei st h eo v e r a l lb e s ta n dt h e c o m p r e s s i o nr a t i oi st h eh i g h e s t t h er e s u l uo f e x p e r i m e n t ss h o w st h a t0 u ra l g o r i t h mh a si m p r o v e dt h eq u a l i t yo f r e c o v e r yi m a g ea n dh i g h e rf r a m er a t et h a nt r a d i t i o n a la l g o r i t h m n o wt h i ss c h e m eh a s a p p l i e d i nas c r e e ns h a r e dm o d u l eo fam u l t i m e d i a e d u c a t i o n s y s t e m ，a n da c h i e v e d e x c e l l e n tp e r f o r m a n c e k e y w o r d ：u d p s t r e a m ，f a i m e s s ，t r a n s f e r s e f f i c i e n c y , s c r e e ns h a r e d ，s u b b l o c k c o m p r e s s i o n ，d i s t a n te d u c a t i o n i i i 华中科技大学硕士学位论文 1 1 引言 1 绪论 在现代生活中，人们都会经历过交通阻塞的情况，当在十字路口等待绿灯的汽车 排成了长龙，那就是拥塞了。在一定的时间间隔，当对资源的需求超过了可用的资源 时，拥塞就会发生。例如，希望使用某道路的车辆超过了可以在该道路通过的车辆。 对计算机网络来说，当用户提供的负荷接近或超过网络的设计限制，即负载暂时大于 资源时就会发生拥塞。随着计算机网络技术的发展，网络的速度越来越快，网络带宽 的持续增长也许会带来一种错觉，即认为网络拥塞是过去的问题，但实际上恰恰相反， 由于新老技术的混用，低速和高速链路的共存，链路带宽的不匹配加重了拥塞问题， 因此拥塞控制一直是网络技术研究的重要课题之。 我们知道，在计算机通信中数据是以数据包为单位进行传输的，传输过程中所经 过的网络节点必须存储并转发这些数据包，直到目的地，这就是包交换，在这个过程 中，网络拥塞一般发生在哪里? 网络拥塞时会出现什么现象呢? 研究表明，网络拥塞 主要发生在包交换机或路由器处，每个包交换机或路由器都有输入和输出缓冲，若数 据包到达的速率接近或超过包处理和转发的速率，数据包就会在缓冲处堆积而排起队 来，这时包会经历很大的时延。包交换机或路由器出现队列就是出现拥塞，拥塞现象 就是数据包的时延变得很大，特别当队列溢出，即无缓冲可用时，必须丢弃包。对于 有差错控制的可靠传输来说，丢弃就会引起超时重发，重发将使拥塞加剧，于是，可 能导致网络吞吐量突然迅速下降，从而形成“拥塞崩溃”。例如，某两地相距不到4 0 0 米，只经过3 个网络节点，但它们之间的数据吞吐量度从平时的3 2 k b p s 降到4 0 b p s ， 这就是捌塞崩溃。 近年来随着网络用户的急剧增加，互联网变得日益繁忙，通信业务的迅猛增长使 得主干网越来越拥塞。与此同时，各种各样的新型业务对网络服务质量提出了更高的 要求。这时，t c p 拥塞控制在保证互联网的鲁棒性和稳定性方面起着至关重要的作用， 但随着互联网技术的进一步发展，仅靠t c p 一种拥塞控制机制来管理网络业务已经显 得越来越力不从心了。 网络的拥塞控制一般分为开环和闭环控制两种，对互联网网络业务不断变化的复 杂系统，般采用闭环控制。依据控制论的观点，发送方接收反馈信息并从反馈信息 华中科技大学硕士学位论文 i *w = = ；= = - = = = = = = = = = ；= = = = ；= ；= = = = = ；= ； 中推断网络状况，确定控制参数，并依据一定的控制算法调整发送速率完成对网络拥 塞的响应。因此讵确的控制算法和准确及时的控制参数是网络拥塞控制的关键。为此， 网络拥塞控制的研究重点就变成研究控制算法和控制参数。 由于许多新的网络应用( 如多媒体实时传输、组播应用等) 在传输层采用u d p 协议 及与t c p 不同的拥塞控制策略，有时甚至没有任何拥塞控制。为适应这一趋势，有必 要研究新的拥塞控制策略，这策略主要从以下两方面入手： 1 ) 在网络设备( 主要是路由器) 中采取一定的策略来避免和控制网络拥塞。 2 ) 研究新的端到端的拥塞控制算法。 本文介绍了互联网拥塞的原因，分析了造成网络越来越拥塞主要原因是由于许多 新的网络应用采用了与t c p 不同的拥塞控制策略或不采用任何拥塞控制，并提出了一 套结合路由器中采取拥塞控制策略和端到端对多媒体实时流的拥塞控制方法 1 2i n t e r n e t 上拥塞控制的研究与发展 1 2 1t c p 协议中的拥塞避免机制 复杂系统的许多问题，都能从控制论角度观察。网络也不例外。拥塞控制的方法， 不论什么形式都可归为两类：开环和闭环控制。开环控制是在事先设计一个“好的” 网络，确保它不发生拥塞，而网络一旦运行起来，就不再采取措施。显然对网络这样 不断变化的复杂系统，开环控制并不是理想的选择。t c p 的拥塞控制采用的是基于窗 口的端到端的闭环控制方式，图1 1 是对拥塞控制机制的一种描述。 图i 1n 个用户共享一个网络环境下拥塞的闭环控制系统 1 9 8 8 年v a n j a c o b s o n 在文献f ”指出了t c p 在控制网络拥塞方面的不足，并提出了 ? 慢启动”( 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 i t ) 算i 去、“陕速恢复”( f a s t r e c o v e r y ) 华中科技大学硕士学位论文 ：= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 算法，避免了网络拥塞不够严重时采用“慢启动”算法而造成过大地减小发送窗口尺 寸的现象，这样t c p 的拥塞控制就由这4 个核心部分组成，最近几年又出现t c p 的 改进版本如n e w r e n o 2 1s a c k 孔等。t c p 拥塞控制是通过控制一些重要参数的改变实 现的。t c p 用于拥塞控制的参数主要有： ( 1 ) 拥塞窗口( c w n d ) ：是拥塞控制的关键参数。它描述源端在拥塞控制情况下一次最 多能发送数据包的数量。 ( 2 ) 通告窗1 3 ( a w i n ) ：是接收端给源端预设的发送窗口大小，它只在t c p 连接建立 的初始阶段起作用。 ( 3 ) 发送窗口( w i n ) ：是源端每次实际发送数据的窗口大小。 h ) 慢启动阈值( s s t h r e s h ) ：是拥塞控制中慢启动阶段和拥塞避免阶段的分界点。初始 值通常设为6 5 5 3 5 b y t e s j 。 f 5 ) 回路响应时f 司( r t t ) ：- - 个t c p 数据包从源端发送到接收端，源端收到接收端确 认的时间间隔。 ( 6 ) 超时重传计数器( r t 0 ) ：描述数据包从发送到失效的时间间隔，是判断数据包丢 失与否、网络是否拥塞的重要参数。通常设为2 r t t 或5 r t t 。 f 7 ) 快速重传阈值( t c p r e x m t t h 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 r e s h 缺省值为3 。 t c p 拥塞控制可分为四个阶段： ( 1 ) 慢启动阶段。旧的t c p 在启动一个连接时会向网络中发送许多数据包，由于 一些路由器必须对数据包排队，所以这样就有可能耗尽存储空间，从而导致t c p 连接 的吞吐量( t h r o u g h p u t ) 急剧下降。避免这种情况发生的算法就是慢启动。当建立新的 t c p 连接时，拥塞窗口( c w n d ) 初始化为一个数据包大小( 一个数据包缺省为5 3 6 或 5 1 2 b y t e s ) 。源端按c w n d 大小发送数据，每收到一个a c k 确认，c w n d 就增加一个数 据包发送量。很显然，c w n d 的增长将随r t t 呈指数级( e x p o n e n t i a l ) 增长：1 个、2 个、 4 个、8 个。源端向网络中发送的数据量将急剧增加。 ( 2 ) 拥塞避免阶段。当发现超时或收到3 个相同a c k 确认帧时，网络即发生拥塞 ( t c p 这一假定是基于由传输引起的数据包损坏和丢失的概率很小( 小于1 ) ) 。此时就 进入拥塞避免阶段。慢启动阈值( s s t h r e s h ) 被设置为当前c w n d 的半，如果是超时， c w n d 还要被胃1 。如果此时c w n d ! s s t h r e s h ，t c p 就重新进入慢启动过程：如果 c w n d s s t h r e s h ，t c p 就执行拥塞避免算法，c w n d 在每次收到一个a c k 时只增加 1 c w n d 个数据包( 这里将数据包大小s e g s i z e 假定为1 ) ，所以在拥塞避免算法中c w n d 华中科技大学硕士学位论文 一：；= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ； 的增长不是指数的，而是线性的( 1 i n e a t ) 。 f 3 ) 快速重传和恢复阶段。当数据包超时时，c w n d 要被置为1 ，重新进入慢启动， 这会导致过大地减小发送窗口尺寸，降低t c p 连接的吞吐量。所以快速重传和恢复就 是在源端收到3 个或3 个以上重复a c k 时，就断定数据包已经丢失，重传数据包， 同时将s s t h r e s h 置为当前c w n d 的一半，而不必等到r t o 超时。 图1 2 和图1 3 反映了拥塞控制窗口随时间在4 个阶段的变化情况。 t o 蚴正l s s t a r c s h 。 o u 辨矗1 2 时阅 图1 2 慢启动和拥塞避免( 不含快速重传和快速恢复) 对阃 图1 3 快速重传和快速恢复 由以上分析可以看出，t c p 使用的是一种和式增加积式减少( a d d i t i v ei n c r e a s e m u l t i p l i c a t i v ed e - c r e a s e ，a i m d ) 的基于窗口的端到端拥塞控制机制。t c p 源端“发送 速率”由拥塞窗口控制。如果有一个数据包丢失，发送窗口则要减半；否则就简单地增 加一个数据包的发送量。大量的实践证明这种拥塞控制机制对i n t e r n e ：上大批量文件 传输等尽量做好( b e s t - e f f o r t ) 型服务具有较好的适应性。但该拥塞控制在与非t c p 流共 享带宽时，会极大的限制t c p 流对带宽的占用，必须依赖非t c p 流的拥塞控制机制 才可以得到较好的效果。 。 华中科技大学硕士学位论文 一= = 一= = = = = = ；= = = = = = = = = = = = = = = = = = = = = = ；= 2 1 2 2t c p 友好的拥塞避免机制及其q o s 保证机制 近年来，多媒体业务越来越多地被应用到因特网上。由于u d p 协议没有像t c p 那样的重传的机制，可以获得较小的时延，所以这些多媒体业务一般采用u d p 协议 作为传输层协议。但由于u d p 缺少拥塞控制的机制，大量使用u d p 流很可能会造成 网络的过载。同时，如果在因特网中大量使用u d p 流，没有流量控制的u d p 流会过 分抢占t c p 的流量，造成u d p 流和t c p 流之间严重的不公平。因此，需要给u d p 增加流量控制机制。这种流量控制机制应该不仅可以避免网络的过载，还应该与t c p 的流控机制是公平的。这种公平性的具体的含义是指：当t c p 流和具有流控机制的 u d p 流在相同的环回时间和包丢失率的情况下，占有相同的带宽。这种u d p 的流控 机制的特性可以被称为t c p 友好9 j 。 关于t c p 的拥塞控制研究的文献相当丰富，而关于t c p 友好的基于u d p 上的拥 塞控制则相对有限。文献【6 l 提出了将去掉t c p 重传的t c p 变例作为传输i n t e m e t 视频 应用的协议框架，但没有解决t c p 内在的突发行为。文献口l 提出了基于r t p 的端端 拥塞控制算法，但没有证明与t c p 流的公平性，且没有研究与网关队列调度的协作性。 文献【8 】1 9 也只是提出了基于t c p 友好的拥塞控制机制，而没有进一步考虑结合网关支 持可控负载服务。文献【lo j 对路由器的r e d 机制进行加强，对标记的和不标记的( 尽力 传递) 流量进行不同的处理，然后对t c p 的拥塞控制机制进行了相应的修改，从而允 许t c p 协议支持最少带宽保证，但该文没有研究u d p 的端端拥塞控制机制，并且也 不支持r e d 网关的自适应调节i l ”。 u d p 协议主要目的是为了实现低时延，大数据量通信。而这一通信方式的主要代 表就是实时视频。拥塞控制及t c p 友好性的主要目的就是保证通信过程中的服务质 量，也就是q o s 。目前有两种途径可以解决当前i n t e r n e t 网上传输实时视频遇到的q o s 保证问题。一种是面向网络的方法。如综合服务( t n t s e r v ) 模型、区分服务( d i f f - s e r v ) 模型、多协议标记交换( m p l s ) 技术等。这些技术需要对现有的i n t e r n e t 的路由器或交 换机进行改动，使它能够区别对待对时延、时延抖动和丢包的宽容度要求不同的数据 流。从而可以管理带宽，提高带宽使用效率以满足不同应用的要求。这种方法比较彻 底，但是对现有的路由交换设备进行全面升级，需要有个比较长的过程。而且各网 络设备生产商的遵循的标准不尽统一也是一个问题。另种方法是面向终端的方案。 这种方案对网络设备没有要求，它仅通过对终端应用的控制来保证视频流的有效传 递。这种方法无论对现有的还是下一代的i n t e r n e t 都适用。 华中科技大学硕士学位论文 一一= = = = = = ；= = = = = = = = = = = = ；= = = = = ；= = = = 。 1 2 2 1 面向网络的q o s 解决方案 为了解决i n t e r n e t 的q o s 问题，一些新的协议和体系模型被先后提出l l 纠1 1 3 1 0 资源预留协议资源预留协议( r s v p ) 是一种提供预留设置和控制以实现综合服务 ( i n t s e r v ) n 综合协议。它在服务保证、资源分配的粒度和对保证q o s 应用及用户反馈 的细节等方面能提供高级的q o s 服务。r s v p 的特性可以归纳为以下几点：1 ) 在每 一个路由器中的预留是“软”的，这意味着需要由接收者周期地更新。2 ) r s v p 不是 传输而是网络( 控制) 协议，因此它不携带数据，但是和t c p 或u d p 数据流并行工作。 3 ) 应用要求a p i 决定流的初始预留请求，并且接收在经过初始请求和全过程中预留 成功或失败的通知。4 ) 为了能够容纳大量不同的接收者，预留是以接收者为基础的。 5 ) 多播的预留在上行的数据流复制点上被结合。6 ) r s v p 数据流可以通过非r s v p 路由器，这会在q o s 链上产生弱链路，在这些弱链路上没有q o s 保证，那里的服务 仍然是尽力而为型的。 i e t f 的区分服务( d i f f - s e r v ) i 作组开发了另一种保证q o s 的方法一区分业务 ( d i f f - s e r v ) 。区分服务对网络上的数据流进行分类，划分优先级，i s p 或网络管理员 可以根据价格、应用的重要性或其他因素对不同的交通流提供不同水平的服务。区分 服务模型重新利用了i p 数据包头中的服务类型( t o s ) 字段( 改为d s 域) ，这使得对 r s v p 网络控制协议的使用仅局限在用户网络一侧而将骨干传送网从r s v p 中解脱出 来。骨干网中的核心路由器只需检查数据包中的t o s 字段( 或d s 域) 来判断业务的 类别，为不同的业务提供不间的q o s 的保证策略。这种模型并不提供从信源端到信宿 端的全程q o s 保证，而是将q o s 限制在不同的域( d o m a i n ) 范围内加以实现。 多协议标记交换( m p l s ) 在某些方面类似于d i f f - s e r v ( ”】，它也是在网络的进入边 界对交通流加标记，在输出点除去标记。但是不像d i 昏s e r v 是在路由器内用标记来决 定优先级，m p l s 标记主要用来决定下一个路由器的跳转。在应用m p l s 的网络中， 可根据i p 层数据包的优先级类别，将其映射到一些特殊的链路层标签上。对于这些 特殊标记的数据，链路层提供特殊的传输通道以满足这些数据包对时延及带宽的需 求。这样，通过链路层定义的特殊标记实现了网络层上不同的q o s 业务需求。 实际应用中，为得到更高的性能需要同时使用多种q o s 技术来提供网络层次从上 到下、在发送者和接收者之间的端到端q o s 。 华中科技大学硕士学位论、文 12 2 2 面向终端的q o s 解决方案 这种方案主要通过在传输层( u d p 协议) 之上对视频流通过反馈信息来进行速率 控制。现在提出的速率控制方案可分为三种：基于发方的速率控制、基于收方的速率 控制、混合的速率控制”“。 在基于发方的速率控制方案中，视频发送方负责调整视频流的传输率来适应网络 的可用带宽。这种对可用带宽的估测一般需要接受方的反馈信息。探测法通过调整发 方的速率使某些q o s 参数( 丢包率等) 在允许范围之内来逼近可用带宽。如线性增加 倍数减少法( a i m d ) 或倍数增加倍数减少法( m i m d ) 法mj 。模型法则试图通过 反馈信息来计算出当前的可用带宽。单播应用可采用这两种方法的任意一种，而组播 应用则一般采用探测法。 基于收方的速率控制一般被用在组播应用中，它通过收方动态的加入或退出分层 通道来实现流量控制。这种技术可有效的解决组播应用中的异构性问题。它同样可分 为探测法和模型法两种。s 。m c c a n n e 提出的基于收方的分层组播( r e c e i v e rd r i v e n l a y e r e dm u l t i c a s t ) r l m 方案就采用探测法【l 刖，当检测到拥塞时，收方退出当前所接 收的最高一层的视频流，从而降低接收速率：反之，则尝试加入上一层视频流。而模 型法通过定量的计算可用带宽，来控制收方加入和退出的层数 1 9 】。 混合的速率控制的速率控制方案则将上述两种方案结合起来。一种代表性的方案 是s 。y 。c h e u n g 提出的目的设置分类( d e s t i n a t i o n s e tg r o u p ) d s g 协议【2 0 】。在发端， 视频被编码成多个独立的可解码的流，这些流的质量不同因而速率也不同。收方跟据 网络的拥塞状态来加入或退出组播组，发方则根据收方的反馈信息来澜整发送速率。 1 3 论文选题和主要工作 本课题是国家教育部重点科学技术项目( n o 2 0 0 0 1 7 5 ) “现代远程教育关键 技术：交互式实时教学工具软件”和国家科技部技术创新基金项目( n o 0 0 c 2 6 2 2 4 2 1 0 6 4 1 ) “远程教学协同群件产品”的核心技术之，这两个项目的重 点是连续媒体流的实时传输，如何对多媒体流高效地编码并结合网络的情况进行实时 传输将是至关重要的技术难关。 本文的选题主要是针对i n t e m e t 上的u d p 数据( 视频，音频等) 的传输应用。主要 想法是通过打包策略，降低网络传输中的错误率，提高网络的利用程度。 本论文共分六章，主要结构与内容如下： 。 华中科技大学硕士学位论文 第一章为综述，提出问题，介绍了视频压缩编码技术在i n t e m e t 网上的实时传输 技术的发展与现状。 第二章从路由器出发，考虑包的尺寸大小对网络性能的影响。这一点，在使用 r e d 算法的路由器中表现的很明显。研究表明，丢包率与数据包的最大长度有着密切 的关系。因此，本章讨论了如何在尽量不降低效率的情况下，减小数据包的长度，也 是打包策略应加以考虑的问题。 第三章对端到端的网络对端到端的网络拥塞控制进行了研究，并依据打包策略提 出了一种基于调整数据包大小的速率控制算法。同时，针对网络传输中出现的丢包现 象，我们提出了一种与数据包大小相关联的选择重传方案，主要应用对象是m p e g 4 等基于运动补偿的视频压缩方案。 第四章首先介绍了一种基于动态阈值的屏幕图象分块压缩算法，在该压缩算法的 基础上结合打包策略，设计了一套屏幕共享系统方案，该方案可有效的提供计算机之 间的屏幕图象共享功能，并有相当优秀的网络性能。 第五章对我们设计的易学多媒体远程教学系统进行了介绍，该系统中采用了第四 章中提出的屏幕图象共享方案，并且在视频数据的传输中对前节所述的速率控制算法 和重传算法进行了尝试。 最后一章对全文工作进行了总结，并针对下一步的研究工作做出了初步设想 8 华中科技大学硕士学位论文 2 数据包大小对i n t e r _ n e t 路由器拥塞控制算法的影响 2 1 引言 在研究计算机网络的发展时，必须着重介绍分组交换( p a c k e ts w i t c h i n g ) 。分组交 换也称为包交换，它是现代计算机网络的技术基础。 存储转发的概念最初是在1 9 6 4 年8 月由巴兰( b a r a n ) 在美国兰德( r a n d ) “公 司的论分布式通信”的报告中提出的。在1 9 6 2 年1 9 6 5 年，美国国防部远景规划局 d a r p a ( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c ta g e n c y ) 和英国的国家物理实验室n p l 都在对新型的计算机通信网进行研究。1 9 6 6 年6 月，n p l 的戴维斯( d a v i e s ) 首次提 出“分组”( p a c k e t ) 这一名词。1 9 6 9 年1 2 月，美国的分组交换网a r p a n e t ( 当时仅 4 个节点) 投入运行。从此，计算机网络的发展就进入了一个崭新的纪元。1 9 7 3 年英 国的n p l 也开通了分组交换实验网。现在大家都公认a r p a n e t 为分组交换网之父， 并将分组交换网的出现作为现代电信时代的开始。除英美两国外，法国也在1 9 7 3 年 开通其分组交换网c y c l a d e s f 2 训1 2 4 1 , 但是随着网络应用的不断发展，用户对带宽的需求也越来越大，需求的增长超过 了硬件设备的发展速度，使得网络服务的质量受到越来越严重的挑战。为缓和这一矛 盾，又两条途径，- l e e 是提高硬件设备的处理能力及速度，这一方法受到技术与成本 的限制，同时，由于网络用户需求在时域上的不均匀性( 白铁与晚上的网络负载有着 极大的区别) ，一味提高硬件性能往往造成了大量的资源的浪费，引起更多方面的问 题。为此，另一种方法，通过控制算法，来对高峰期的网络负载进行合理分配，允许 一定程度的性能的降低，但避免出现服务崩溃的可能，成为了当前的研究热点，这也 就是对网络的拥塞控制。 由于带宽、缓存等资源相对需求日益缺乏，i n t e m e t 还会继续变得拥塞。这种情 况导致了几种解决拥塞的方法，第一种方法是继续改进已有的端到端拥塞控制并将其 作为i n t e r n e t 上的主要拥塞控制机制1 25 l ：第二种方法是利用价格等经济因素限制用户 对网络资源的需求，减少拥塞的发生。文献忙6 j 提出另外建立网络收费论的方法，但仅 限于理论分析。文献1 27 1 用经济学理论分析了具有拥塞特性网络资源的计费问题。第三 种方法是在路由器中采用排队算法和数据包丢弃策略，也就是这里要讨论的1 p 拥塞 控, j j j a q 题。排队算法通过决定哪些包可以传输来分配带宽，而丢弃策略通过决定哪些 包被丢弃宋分配缓存。这些也直接影响数据包的延时特性。本文在此介绍了一种结合 华中科技大学硕士学位论文 数据包大小及队列变化趋势的早期随机探测( r e d ) 算法的改进，该改进算法有效的 提高了具有不同数据包大小的数据流之间的公平性与流量。 2 2 1 n t e r n e t 上i p 数据包的传输 i p 的数据通信网( 简称i p 网) 有其明显的特点。在i p 网，每一计算机用户发出的 数据信息首先分成许多个“分组( p a c k e t ) ”，每一i p 分组先是标明传送目的地地址 f d e s t i n a t i o na d d r e s s ) ，接着是数据信息主体( i pp a yl o a d ) 。于是，i p 分组经过“分组交 换( p a c k e ts w i t c h i n g ) ”过程，这与传统通信网中的交换制式大不相同。在传统的电话 通信网，采用电路交换( c i r c u i ts w i t c h i n g ) ，对双方用户的互相通话提供一定的电路， 这电路的路由是固定的。在通话进行期间( 不管用户通不通话) ，这电路所需的通信网 频带宽度就为这双方用户占用，不能提供别人通信使用。近年临时增设的数据通信网 也是按照传统电话网同样办理，分配一定的电路供用户数据信息业务使用，电路的带 宽也得到保证。 现在和将来发展的i p 网的交换方式却与传统的大不相同，它不是对传统网稍加 改进，而是采用分组交换，发生根本性变化。i p 网是分组交换网，把i p 分组从发端 传送至收端，经过网内各不同的节点，走最合适和便捷的路由，而不是固定的路由。 如经过某处有障碍，就改用其它路由或经过其它节点绕道前进。而且各节点的设施可 以属于不同的制式，并不强求一律。这样i p 网的分组交换把数据业务从发端传至收 端，没有采用固定连接的路由。因为每一分组在入网之前都已标明目的地的地址，每 一节点收到这分组，首先验明目的地的地址根据它决定下一段路由向前传送。就是说， 在接续的全程中，逐段验明地址才决定路由。通信网不为分组保证固定带宽，也不保 证同一发端至同一收端的两个分组是同样的路由。 为了让发端和收端双方确知每一分组已经顺利经过了i p 网并正确地完成了传送 任务，i p 网配备的“传输控制协议( t c p ) ”起很大作用。t c p 负责处理i p 分组在网内 传送的速率，并在分组收到时发出通告，又保证各分组收到后按原来次序重新组合。 这样的t c p 功能，在邮政网比拟中可以当作发信人和收信人的秘书，互相核对信函或 包裹是否完全送到而且完整无损。 与利用电路交换的传统电话网相比，这样的分组交换i p 网有一些明显的优点：第 一，对于发收双方不是长时通信不停使用的情况，i p 网不需要预留带宽容量，因而对 于同样的通信业务量，可以减少必需的通信网带宽资源，从而降低成本。不过，分组 交换网为了保证提供与电路交换网相似的服务水平，一般需要增加更多的额外工作， 因而并不能使成本节约很多。并且，对于有些数据通信业务，仍是要求i p 网预约一 华中科技大学硕士学位论文 定的带宽容量。第二，由于i p 分组在网内传送每一段线路后就重新确定下一段所走 路由，因此，如遇到网内某处线路发生故障，可以方便地选用其它最好的线路，保证 传送畅通无阻。第三，i p 分组的方式容许各种不周制式的设备都能载荷数据信息。因 此，较大规模的i p 网如有几种不同制式设备的节点，i p 分组总是能够顺利地从发端 传送至收端。这在邮政网比拟中恰像每段邮递可以使用邮车，也可使用火车或轮船等 交通工具，同样把邮件顺利传送。 i p 网的主要网络单元是路由器( r o u t e r ) 和交换机( s w i t c h e r ) 。i p 路由器须完成 三种主要功能：第一，为数据信息业务选择路由。i p 网的每一节点都设置路由器。当 数据信息业务从一段线路到达一节点的路由器时，这路由器就对该数据分组的标头进 行分析，以确知该数据传往收端目的地。于是这路由器核查“选路表( r o u t i n gt a b l e ) ”， 从而确定下一节点以便连往目的地。于是把分组发往下一段线路至下一节点。第二种 功能是建立选路表。大多数i p 网是根据选路的协议，让各节点间互相联络了解网络 组形情况，以便各节点能够确定最好的下一节点连往目的地。第三是路由器适应各种 不同制式装置的设备使用。例如经过路由器可把数据分组从帧中继网连至以太网。这 也可以用邮政网来比拟，路由器好像是一个中间邮局，把从渡轮取下的邮件，装上火 车继续向前运送。 路由器有各种不同类型和规格。小型路由器用作用户室内设备，装在局域网l a n 的接口，线路传输速率2 m b s 。中型路由器作为接入路由器，用于广域网w a n ，可以 有2 0 0 个用户的集合接入，线路传输速率3 4 m b s 。大型路由器则是装在核心网，可以 集合很多用户的数据业务，线路传输速率达1 5 5 m b s 。特大型路由器用于大型i p 网的 核一心网，线路传输速率高至2 。5 g b s ，以致核心网总的交换容量可达6 0 g b s 。不久 的将来可能再加大交换容量至t b s 级。凡是装置一个或多个路由器的地点，往往称 为“存在点( p o p ，p o i n to fp r e s e n c e ) ”。为了使路由器能够顺利地把i p 分组传往目 的地，必须具备选路表。一般规定的选路表在使用时要花费较多时间，而且可能发生 差错。所以，最好让路由器根据“选路协议( r o u t i n gp r o t o c 0 1 ) ”自己建立选路表， 这就称为动念选路。有时遇到网内发生故障，需要另走部份路由，相应地要求路由器 重新建立选路表。有了这样的动态选路，可以减少人工估算，但它需要网络提供小量 的带宽，这也是值得的。选路规约有内部和外部的两种：内部选路规约是针对网络内 部，它能随着变化及时修改：外部选路协议则用来与其它企业运营的网络互相经常交 换选路信息。 华中科技大学硕士学位论文 = 一= = = = = = ；= = = = = = = = = = = ；= = = = = g = = = = = = = = = 一 2 3 路由器拥塞控制方案 2 3 1 拥塞控制算法概述 目前路由器处理拥塞的方法有以下