（通信与信息系统专业论文）大规模通信网络的性能分析及优化.pdf

摘要 摘要 本文在对国内外近十年以来有关通信网络流量控制以及资源管理的研究进展 进行回顾与总结的基础上，在国家自然科学基金项目“高速网络中业务流量传输 控制策略的最优化研究”课题组的前期研究的影响下，选取大规模通信网络的性 能分析及优化这一课题进行研究。内容涵盖了信息网络理论、最优化理论、大系 统理论、计算复杂性等计算机科学与通信科学的相关领域。文中重点研究了大规 模通信网络中面临的一些特殊问题，包括巨型综合业务队列呼叫阻塞概率的快速 计算问题、大型网络资源的优化分配问题、高速网络中广泛存在的自相似性业务 流的性能分析问题，提出了相应的解决办法或解决方案，取得了一定的进展。 在对巨型综合业务队列或资源共享系统的呼叫损失概率计算的研究中，以各 业务间几乎独立地按比例分享资源为着手点，提出一种将巨型综合业务队列划分 为多个同构的、含综合业务的子队列，然后运用大数定律和中心极限定理以正态 分布来近似系统总资源占用分布的方法，结合查表技术和插值技术，获得了一种 计算复杂度为0 ( c o ) 的近似算法，大大提高了巨型队列中呼叫损失概率的计算速 度，而由近似计算所产生的误差在实际应用中是很小的。 a t m 因其严格的服务质量保证体系而成为宽带网络的主流技术。本文选取大规 模a t m 网络中虚通路带宽优化分配问题作为重点进行了研究。通过对国内外截至 2 0 0 0 年底有关文献的查阅，仅找到两篇针对大规模a t m 网络虚通路带宽分配问题 研究的论文，它们都是由希腊的l o g o t h e t i s 等人所写，其主要思想是将大系统进 行分割优化。由于其算法上存在的不足，导致分割优化的结果与严格最优解存在 2 0 以上的误差。通过对l o g o t h e t i s 分割优化算法的深入剖析，找到其产生误差 的根源在于没有处理好分割后各子系统间的互相关联问题。为此，本学位论文提 出将大系统分解一协调理论运用于大规模网络带宽分配的分割优化中，使计算误差 大大降低，并使计算的时间及空间复杂度都低于直接求解法。由于所提出的算法 中采用了一种较简单的协调机制，它很容易以分布式计算来实现，从而能充分发 挥网络的多计算机协同计算优势。在此基础上，本学位论文对大型网络中的分布 式资源管理及其优化的一些具体问题即协调信息的传递问题和动态资源分配问题 进行了探讨并提出了解决方法或框架方案。 作为对虚通路带宽分配问题的一个补充，学位论文还对传输链容量的可变性 及其对带宽分配的影响进行了研究。考虑到影响传输链容量的物理因素包括交换 机和传输介质( 如光纤) 等多个因素，若将交换机看成是一种具有一定可控性的 或“主动的( a c t i v e ) ”器件，则传输链容量的有限可变性就有其物理上的合理 第i 页 华南理工大学工学博士学位论文 性。在传输链容量具有有限可变性的假设下，通过几个计算实例，揭示出这种可 变性对于提高网络为突发性业务的服务质量有明显作用。这一结论表明，如果交 换机内部的多处理机具有协作能力，那么在不需增加其它硬件投资的情况下，网 络资源将会发挥更大的效率。 网络业务流的自相似性的发现对通信网络理论和流量工程产生了深刻的影 响。由于它与传统p o i s s o n 过程的显著差别，人们对网络业务流量的建模、网络 性能的分析、网络工程设计都要更新的理论。对自相似业务流下的网络性能分析 具有很大的难度，这使得到目前为止还没有能给出较准确结果的解析分析方法， 甚至连数值计算方法都未见报道。本文在t s y b a k o v 等人的研究基础上，运用m g 1 排队系统理论。导出了一个具有普适意义的等待时间分布的f o u r i e r 变换函数， 在此基础上建立了计算任意缓存下溢出概率及信元丢失概率的数值算法。几个关 于大缓存下的计算实例表明，本文所提出的数值算法给出的结果与t s y b a k o v 给出 的上、下界是相符的。由于此前的关于自相似业务流下缓存溢出概率及信元丢失 概率的所有研究局限予缓存要么趋于0 ( 小缓存) ，要么趋于无穷( 大缓存) ，因 此本文的研究比前人的研究有更广阔的应用范围。 关键词：通信网络，性能分析，优化，分布式计算，自相似性 第i i 页 a b s t r a c t i n t h i sd i s s e r t a t i o n ，t h er e s e a r c ha c h i e v e m e n t si nt h ea r e a so ft r a f f i cc o n t r o la n dr e s o u r c e m a n a g e m e n to fc o m m u n i c a t i o n sn e t w o r k si nt h er e c e n td e c a d ea r er e v i e w e d b a s e do nt h er e v i e w a n di n f l u e n c e db yt h ep r e c e d i n gw o r kb et h er e s e a r c hg r o u pe n g a g e di nt h ep r o j e c tc a l l e d “r e s e a r c ho nt h eo p t i m i z a t i o no fc o n t r o ls t r a t e g yo ft r a n s p o r t a t i o no ft r a f f i ci nh i g h - s p e e d n e t w o r k s ”a n da p p r o v e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n ，t h ep e r f o r m a n c ea n a l y s i s a n do p t i m i z a t i o no fl a r g e s c a l ec o m m u n i c a t i o n sn e t w o r k si ss e l e c t e da st h es u b j e c to ft h ea u t h o r s p h dc a r e e r t h ew o r kc o v e r st h et h e o r yo fi n f o r m a t i o nn e t w o r k s 。t h et h e o r yo fo p t i m i z a t i o n ，t h e t h e o r yo fl a r g e - s c a l es y s t e m sa n dc o m p u t a t i o nc o m p l e x i t i e s i ti sa c r o s s e da r e ac o v e r e db o t hb y c o m p u t e rs c i e n c ea n dc o m m u n i c a t i o ns c i e n c e t h ed i s s e r t a t i o nf o c u s e so nt h es p e c i a lp r o b l e m s p r o v i d e db yl a r g e - s c a l ec o m m u n i c a t i o n sn e t w o r k s t h e s ep r o b l e m si n c l u d ef a s te v a l u a t i o no fc a l l b l o c k i n gp r o b a b i l i t i e so fh u g ei n t e g r a t e ds e r v i c e sn e t w o r k s ，o p t i m a la l l o c a t i o no fr e s o u r c e si n l a r g en e t w o r k s ，p e r f o r m a n c ea n a l y s i so fs e l f - s i m i l a rt r a f f i cw h i c hr e s i d ep r o f o u n d l yi nn e t w o r k s s o m es o l u t i o n so rp o t e n t i a ls o l u t i o n st ot h e s ep r o b l e m sa r es u g g e s t e d ，a n dt h e yc a nb er e g a r d e da s a e h i e v e m e n t s i nt h ew o r ko fe v a l u a t i o no fc a l lb l o c k i n gp r o b a b i l i t i e so fh u g ei n t e g r a t e ds e r v i c e so r r e s o u r c es h a r i n gs y s t e m s ，t h ek e yt h a te a c hs e r v i c ec l a s sa l m o s to c c u p i e sr e s o u r c e si n d e p e n d e n t l y h e l p st h ea u t h o rt od e v e l o pa m e t h o dt oe s t a b l i s ht h eo v e r a l ld i s t r i b u t i o no fo c c u p i e dr e s o u r c e s t h em e t h o di st od i v i d et h eh u g es y s t e mi n t om a n yi d e n t i c a ls u b - s y s t e m se a c ho fw h i c ha l s o s u p p o r ti n t e g r a t e ds e r v i c e s t h e nt h el a wo fl a r g en u m b e r sa n dt h ec e n t r a ll i m i tt h e o r e mc a nb e a p p l i e dt oa p p r o x i m a t et h ed i s t r i b u t i o no fo c c u p i e dr e s o u r c e sa st h en o r m a ld i s t r i b u t i o n c o m b i n e dw i t ht h et e c h n o l o g i e so ft a b l el o o k u pa n di n t e r p o l a t i o n ，a na p p r o x i m a t ea l g o r i t h mw i t h t h ec o m p u t a t i o nc o m p l e x i t yo fo ( c ”) i sp r o p o s e d t h ea l g o r i t h ma c c e l e r a t e st h es p e e do f e v a l u a t i n gt h ec a l lb l o c k i n gp r o b a b i l i t i e so fah u g eq u e u ea p p a r e n t l y , b u tt h ee r r o ri nr e a l a p p l i c a t i o n si sp a l t r y a t m p r e v a i l si nt h et e c h n o l o g i e so fb r o a d b a n dn e t w o r k sb e c a u s eo fi t sg u a r a n t e e dq u a l i t y o fs e r v i c e t h ep r o b l e mo fp a t hb a n d w i d t ha l l o c a t i o nf o rl a r g e - s c a l ea t mn e t w o r k si sc h o s e nt o b et h em a j o rr e s e a r c ho ft h i sd i s s e r t a t i o n a m o n gt h er e l a t e dp a p e r sp u b l i s h e dt i l lt h ee n do f2 0 0 0 ， o n l yt w os p e c i a l i z e do nt h ep r o b l e mo fp a t hb a n d w i d t ha l l o c a t i o nf o rl a r g e - s c a l en e t w o r k s b o t h a r ew r i t t e nb ym i c h a e ll o g o t h e t i s t h es p i r i to fl o g o t h e t i s p a p e ri st od i v i d eal a r g es y s t e mt o s m a l lo n e sa n dt h e nt oo p t i m i z et h e mi n d e p e n d e n t l y b e c a u s eo ft h es h o r t c o m i n g s ，t h e i r d e c e n t r a l i z e da l g o r i t h mg i v e se r r o r sa b o v e2 0 o nt h ea v e r a g e b ys t u d y i n gt h e i ra l g o r i t h m 第i i i 页 一丝童垩三查兰三兰堡圭兰堡篁塞 c a r e f u l l y , t h ea u t h o rr e a l i z e dt h a tl o g o t h e t i sh a dn o tt r e a t e dt h ep h y s i c a lc o n n e c t i o n sb e t w e e n s u b s y s t e m s ”。r y “e l l b a s e do nt h eo b s e r v a t i o n ，t h ed i s s e r t a t i o np r o p o s e sam e t h o do fa p p l y i n g t h ed e c o m p o s i t i o n c o o r d i n a t i o nt h e o r yo fo p t i m i z i n gl a r g e s c a l es y s t e m st ot h ef i e l do fb a n d w i d t h a l l o c a t i o nf o rl a r g e - s c a l en e t w o r k s w h i l et h ee r r o rp r o d u c e db yt h en e wa l g o r i t h mi s a l m o s t n e g l i g i b l e ，b o t ht h et i m ea n dt h es p a t i a lc o m p l e x i t i e sa r el e s st h a nt h a to fd i r e c to p t i m i z a t i o n t h e n e wa l g o r i t h mi m p o s e sas i m p l em e c h a n i s mo fc o o r d i n a t i o n ，t h i si n c r e a s e st h ep o s s i b i l i t yo f c o n v e r t i n gt h ea l g o r i t h mt oad i s t r i b u t e dv e r s i o na n dt a k i n gt h ea d v a n t a g e so fc o o r d i n a t i o no f m a n yc o m p u t e r si nt h en e t w o r k - f u r t h e r m o r e ，t h ed i s s e r t a t i o np r o b e si n t os o m es p e c i f i cp r o b l e m s r e l a t e dt ot h ed i s t r i b u t e dm a n a g e m e n to fl a r g e s c a l en e t w o r k s ，n a m e l yt h ep r o b l e mo ft r a n s f e ro f c o o r d i n a t i o nm e s s a g e sa n dt h a to fd y n a m i cr e s o u r c em a n a g e m e n t s o l u t i o n so rp l a n so fs o l v i n g t h ep r o b l e m sa r ep r o p o s e d a sas u p p l e m e n tt ot h er e s e a r c ho np a t hb a n d w i d t ha l l o c a t i o n ，t h ed i s s e r t a t i o nc o n t a i n ss o m e w o r ko nt h ev a r i a b i l i t yo ft h ec a p a c i t yo ft r a n s m i s s i o nl i n k sw i t hi t si n f l u e n c eo np a t hb a n d w i d t h a l l o c a t i o n b e c a u s et h ec a p a c i t yo fal i n kd e p e n d so nm a n yf a c t o r ss u c ha st h es w i t c ha n dt h e c o n v e y i n gm e d i a ( t h eo p t i c a lf i b e r ) 。i fas w i t c hi st os o m ee x t e n tp r o g r a m m a b l eo r a c t i v e ”，t h e n t h el i m i t e dv a r i a b i l i t yo ft h ec a p a c i t yo fal i n ks o u n d sp h y s i c a l l yr a t i o n a l a s s u m i n gt h ec a p a c i t y o fat r a n s m i s s i o nl i n kb ev a r i a b l e ，s e v e r a le x a m p l e ss h o wt h a tt h ev a r i a b i l i t yt a k e sg r e a tp a r ti n u p g r a d i n gt h eq u a l i t yo fs e r v i c ef o rb u r s tt r a f f i c s t h ec o n c l u s i o nh i n t st h a ti ft h ep r o c e s s o r s w i t h i nas w i t c hc 如c o o p e r a t ew i t he a c ho t h e r , t h e nw ec a l lg e th i g h ”u t i l i t i e so fn e t w o r k r e s o u r c e sw i t h o u ta d d i n gh a r d w a r e t h ed i s c o v e r yo ft h es e l f - s i m i l a rn a t u r eo fn e t w o r kt r a f f i ch a sg r e a ti m p a c t sb o t ho nt h e t h e o r yo fc o m m u n i c a t i o nn e t w o r k sa n do nt r a f f i ce n g i n e e r i n g b e c a u s eo fi t ss t r i k i n gd i f f e r e n c e f r o mt r a d i t i o n a lp o i s s o np r o c e s s e s ip e o p l en e e d su p t o - d a t et h e o r i e sf o rn e t w o r kt r a f f i cm o d e l i n g ， n e t w o r kp e r f o r m a n c ea n a l y s i sa n dn e t w o r kp l a n n i n g t h e r ei sg r e a td i f f i c u l t yi np e r f o r m a n c e a n a l y s i sf o rn e t w o r kw i t hs e l f - s i m i l a rt r a f f i c s of a r , t h e r ei sn oa c c u r a t ea n a l y t i c a lm e t h o di nt h i s a r e a e v e nn on u m e r i c a la l g o r i t h mh a sb e e nr e p o r t e d b a s e du p o nt h ea r d u o u sw o r kb y t s y b a k o v a n db ya p p l y i n gt h em g 1 1q u e u i n gt h e o r y , t h ed i s s e r t a t i o nd e d u c e sag e n e r a lf o r m u l ao ft h e f o u r i e rt r a n s f o r mo ft h ed i s t r i b u t i o no ft h ew a i t i n gt i m eo fa na r r i v i n gc u s t o m e r t h i sf o r m u l a b e c o m e st h eb a s i so fd e v e l o p i n gan u m e r i c a la l g o r i t h mf o re v a l u a t i n gt h eb u f f e ro v e r f l o w p r o b a b i l i t ya n dc e l ll o s sp r o b a b i l i t yi naq u e u ew i t ha r b i t r a r yb u f f e rs i z e s e v e r a ln u m e r i c a l e x a m p l e so fl a r g eb u f f e rs h o wt h a tt h ea l g o r i t h mg i v e sr e s u l t sw i t h i nt h et s y b a k o vl i m i t s a st h e e x i s t i n gp u b l i s h e da n a l y s i so n l ya p p l i e st ob u f f e r st e n d i n gt oz e r o ( s m a l lb u f f e r ) o rt ob u f f e r s t e n d i n gt oi n f i n i t y ( 1 a r g eb u f f e r ) ，t h ea c h i e v e m e n t sh e r ec a r lh a v ea w i d e rs p r e a do fa p p l i c a t i o n k e yw o r d s ：t e l e c o m m u n i c a t i o n sn e t w o r k s ，p e r f o r m a n c ea n a l y s i s ，o p t i m i z a t i o n ，d i s t r i b u t e d c o m p u t i n g ，s e l f - s i m i l a r i t y 第i v 页 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写的成果作品。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本人完全意识到本声明 的法律后果由本人承担。 作者签名：童竺叶 日期：z 。j 年占月z 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书， 本学位论文属于 不保密囱。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 啬波文 ， 一 i v f 秒 扩 日期： 矽哆年占, e j l 多日 日期：沙口) 年6 月c 7 e t 第一章绪论 第一章绪论 1 1t c p 与a t m 中的流量控制 i n t e r n e t 是全球性的计算机网络，其传输控制协议( t r a n s m i s s i o nc o n t r o l p r o t o c o lt c p ) 是很简洁的，并且主要操作是在网络的发、收两端进行的，因此 对提高网络设备的利用率十分有利。然而正是这种简洁，它能导致网络在负荷太 重时发生拥塞。t c p 的核心问题是如何预防拥塞( c o n g e s t i o n ) 及在发生拥塞时通 过降低信源方的发送速率来摆脱拥塞。 早期的t c p 拥塞控制机制主要是基于v a n3 a c o b s o n ”提出的“陵启动( s l o w s t a r t ) ”算法、“拥塞避免( c o n g e s t i o na v o i d a n c e ) ”算法和一个用于估计周转 延时r t t ( r o u n dt r i pt i m e ) 的算法，1 9 9 0 年出现的t c pr e n o ”版本增加了“快 速重传”( f a s tr e t r a n s m i t ) 和“快速恢复( f a s tr e c o v e r y ) ”算法，避免了当 网络拥塞不太严重时采用“慢启动”会造成过大地减小发送窗口尺寸的问题。近 年来，将主动队列管理算法( a c t i v eq u e u em a n a g e m e n t ) “”与显式拥塞通知 ( e x p l i c i tc o n g e s t i o nn o t i f i c a t i o ne c n ) ”“相结合的算法已被i e t f ( i n t e r n e t e n g i n e e r i n gt a s kf o r c e ) 接纳为标准。v a s “i o s 等人“”提出了一种支持e c n 的、 基于加权窗的拥塞控制算法，其权值依赖于业务流的吞吐率性能。 现代电信网络的业务已从过去较单一的种类发展成含语音、图象、文件传输等 多种类型。随着i n t e r n e t 客户的飞速增加和光纤技术的发展，电信网的用户及容 量也快速增加。为了在保证服务质量( q u a l i t yo fs e r v i c e ) 的同时，充分利用 现有网络资源，以便在同一个电信网上支持大量的网络应用，a t m 技术应运而生。 a t m 支持c b r 、r t v b r 、n r t v b r 及a b r 等多种业务”，并通过连接允许控制“7 1 ( c a c ) 建立连接，以保证对c b r 、v b r 业务的服务质量。理论上说，只要对每次 呼叫进行连接允许控制并为其分配达到或超过其峰值速率的带宽，拥塞是可以完 全避免的。但会造成网络利用率急剧下降。由于v b r 业务的信源码流发送速率是 可变的，且这种业务通常允许一定的信元丢失率，因此可以只为其分配一个略高 于其源端发送速率平均值的带宽，将节省下来的带宽用于传送对速率要求不高的 a b r 业务。这种方法虽然可以提高网络的利用率，但留下了拥塞的隐患。因此，对 网络进行流量控制，是保证服务质量以及避免拥塞的必需手段。流量控制的两个 主要问题是：在连接允许控制c a c 中如何根据q o s 进行带宽分配；如何发现拥塞 征兆及采取措施预防拥塞。下面对近十年来拥塞控制方面的一些主要研究成果予 第1 页 华南理工大学工学博士学位论文 以总结，而对带宽分配方面的研究综述留待下一节。 拥塞控制是a t m 网络传输控制与管理的核心问题。a t m 网络经连接许可控制建 立连接后，基于连接的特性和q o s 要求，必须给这个连接分配一定的带宽。由于 a t m 网允许所有连接共享带宽资源，加上各类服务传输速率变化很大，因此，实际 入网的传输流量很有可能超过分配给它的带宽，造成拥塞。这时就需要对传输流 量进行监控，以保证业务流传输过程中的特性与它申请入网时要求的传输特性以 及网络分配给它的带宽相符。 a t m 拥塞控制包括开环预防控制和闭环反馈控制。开环预防控制采用普通信元 速率算法以及对信元的流速进行整形( t r a f f i cs h a p i n g ) 。闭环反馈控制也叫反 馈流量控制。 1 1 1 开环预防控制 1 1 1 1l e a c k yb u c k e t 算法 目前最常用的带宽监控技术是普通信元速率算法，也叫“漏桶”算法“”。这种 算法可将突发业务流转化为平缓业务流。漏桶算法用于确保用户的业务流遵守建 立连接时的规定。其基本思想是：任何一个信元要进入网络，一定要从漏桶中取 得一个令牌；如果此时漏桶为空，则该信元被丢弃：漏桶以网络平均允许速率r 产生，漏桶最多可存放m 个令牌，漏桶满时，新产生的令牌被丢弃。一个改进方 法是在信元到达漏桶前增加一个缓冲区。这样，当漏桶为空时，只要缓冲器没有 满，信元就可以存在缓冲器中面不被丢弃。由于这种改进以增加信元的等待时间 来换取低的信元丢失率，因此选择一个合适的缓冲区大小以达到两者的最优控制 是该方法的关键。漏栖算法也有一些缺点，例如即使在网络负载很低时，漏桶算 法对违约信元仍然采用丢弃或放入缓冲区的方法，由于算法限制，减缓了业务流 速，造成网络资源的浪费。采用标志法可以改善这一缺陷：当信元到达但漏桶为 空或缓冲器已满时，就将该信元打上一个标志，说明是违约信元，然后允许它进 入网络，如果在网络某处遇到拥塞，则丢弃；着一直没有遇到拥塞，则可到达目 的结点。 1 1 1 2 业务流整形( t r a f f i cs h a p i n g ) 在a t b l 网络中，业务流是高度突发的，其传输速率变化很大，根据排队理论， 如果适当地改善业务流进入网络的统计特性，使信元进入网络这一随机过程的统 计特性越平滑，网络服务质量( 延迟、丢失率) 就越好。流量整形就是要避免信 元在网络中突发性传输，达到改善网络q o s 性能的目的“”。漏桶算法注重带宽的 限制，流量整形技术则注重于降低突发度和改进业务流进入网络的分布。流量整 第2 页 第一章绪论 形技术成功的关键在于减少了传输延迟和信元的丢失。 1 1 2 反馈流量控制( f e e d b a c kf l o wc o n t r 0 1 ) 闭环、动态的流量控制需要反馈机制使信源知道拥塞点的信息状态。已被a t m 网络研究的反馈流量控制方案主要有以下几类： 1 1 2 1 基于信用的流量控制( c r e d i tb a s e df l o wc o n t r 0 1 ) 突发业务造成网络超载的最显著的标志是缓冲溢出。基于信用的流量控制 “”“”3 “3 就是直接控制缓冲的分配。在沿着链路向前传送任何信元前，发送 结点首先需要接收来自信宿的信用信息，以确定接收点是否有可接收信息的缓冲 空间。发送结点接收到信用信息后，在接收结点可接收范围内传送一定数量的信 元，从而保证不会发生拥塞。基于信用的流量控制的特点是提高了链路的利用率、 控制质量和公平性。最明显的一个缺点是它的复杂性和缺少灵活性，以致于这种 控制方案没有被a t m 论坛选用。 1 1 2 2 基于速率的流量控制( r a t e - b a s e df l o wc o n t r 0 1 ) 基于速率的流量控制”1 ”“1 ”卟”“8 3 直接控制连接的带宽( 速率) 。在1 9 9 4 年 被a t m 论坛选为可用比特速率业务a b r 的最佳控制方法。基于速率的流量控制方 案采用端一端控制，使用网络反馈信息规定每个虚连接上每个信源能发送的最大 速率。基于速率的流量控制方案包括速率的设置和速率的控制两个阶段。在这种 方案中，分配给一个连接的带宽与两点间的延时无关，因此基于速率的流量控制 在结构上是灵活的。这种方案支持公平带宽分配，且这种方案无需复杂的队列管 理。但是，它也面临着许多有待改进和研究的问题。 1 1 2 3 前向显式拥塞通知( f e c n ：f o r w a r d e x p l i c i t c o n g e s t i o n n o t i f i c a t i o n ) 采用前向显式拥塞指示【 ” a 2 0 1 ( e f c he x p l i c i tf o r w a r dc o n g e s t i o ni n d i c a t i o n ) 机制下，多个连接共享一个中间结点的链路队列，当平均队列长度达到某一给定 临界值时，通过队列的信元就打上一个e f c i 标志，继续传输给目的结点，一旦目 的结点接收到带e f c i 标志的信元，就向信源发送拥塞信息一一r m 信元，信源据 此按线性递增或倍减原则调整信元发送速率。由于速率的调整由网络拥塞状态和 信元瞬时的传送速率共同决定，因此，该方案允许各个连接公平地分享带宽。其 缺点是，拥塞信息传送路径过长，不利于信源对拥塞作出快速反应。 1 1 2 4 反向显式拥塞通知( b e c n b a c k w a r de x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ) 第3 页 华南理工大学工学博士学位论文 该方案”“”直接从拥塞点( 如交换机) 向每一个虚通道信源发送拥塞- - r m 信元，因此，它的显著优点是对拥塞反应速度快。它对速率的控制简单、经济， 因为它仅仅依赖于b e c n 信元来调整速率的变化。它的缺点是：每一个中继结点都 参与了拥塞控制，增加了系统开销。另外，如果交换机由于严重拥塞发不出r m 信 元，那么源方将会错误地增加速率，这会使拥塞更严重。 1 1 2 5 均衡速率控制算法( p r c a ：p r o p o r t i o n a lr a t ec o n t r o la l g o r i t h m ) 源方发送的信元e f c i 不总为o ，只有n 个信元中的第个信元的e f c i 为0 。 目的方收到r m = o 的信元时发回一个蹦信元。源方收到r m 信元时提高发送速率( 加 倍) 。采用这种算法3 1 时，如果信元经过多个交换机，那么发生拥塞的可能性大， 源方发送速率不高。 1 1 2 6 智能拥塞控制( i c c t ：i n t e l l i g e n tc o n g e s t i o nc o n t r o lt e c h n i q u e s ) 又称为增强型p r c a 算法( e p r c a ) ”2 ”“2 5 h “。该算法的描述如下； s t e p l ：源方发送信元时设置e f c i = o 。每发送n 个数据信元后，源方发送一 个r m 信元。这个信元中包括以下信息：当前速率a c r ( c u r r e n ta l l o w e d c e l lr a t e ) 、希望速率e r ( d e s i r e de x p i c i tr a t e ) 、拥塞指示位c i ( c o n g e s t i o ni n d i c a t i o nb i t ) 。n 通常取为3 0 。 s t e p 2 ：源方初始时设置e r 为它的峰值速率p c r ( p e a kc e l lr a t e ) ，c i 位为 o 。 s t e p 3 ：交换机从源方收到r m 信元时，根据a c r 计算平均允许速率m a c r ( m e a n a 1 1 0 w e dc e l lr a t e ) m a c r = ( 1 - d ) m a c r + a c r 其中为比例因 子，通常取为1 1 1 6 。 s t e p 4 ：目的方收到r m 信元时，根据最后一个数据信元中e f c i 位的值设置 雕信元中c i 位的值，并将e r 值设置为自己能够满足的大小，之后将 r m 信元发回源方。 s t e p 5 ：交换机收到目的方发回的r m 信元时，根据自身的拥塞状态设置c i 位的值( 拥塞时置c i 为1 ) 及e r 的值。若当前缓冲队列长度大于某一 个临界值，则e r = m i n ( e r ，b , m a c r ) ，b 为比例因子，通常取7 8 ；否 则e r = m i n ( e r ， l a c r ) 。 s t e p 6 ：源方在收到每个r m 信元时，根据其中c i 位的值调整发送速率。若 c l = o ，贝a c r = m i n ( a c r + a i r ，e r ，p c r ) ；若c i = i ，贝ha c r = m a x ( a c r * r d f ， m c r ) 。其中m c r 为最小发送速率( m i n i m u mc e l lr a t e ) ，a i r 为a d d i t i o n i n c r e a s er a t e ，r d f 为r e d u c t i o nf a c t o r - 另外，在a t m 网络上传送t c p 、u d p 等数据分组时，由于一个数据分组要被分 第4 页 第一章绪论 割成多个a t m 信元来传输，所以如果丢失了一个信元，整个数据分组就要重传。 这样网络拥塞时系统的有效吞吐量会很低。为解决这个问题，人们提出了两个简 单的控制机制：部分分组丢弃( p a r t i a lp a c k e td i s c a r d ) 和早期分组丢弃( e a r l y p a c k e td is c a r d ) 。部分分组丢弃是指当丢弃一个信元时，a t m 交换机根据其后到 来的a t m 信元中p t i 的a u u 值丢弃间一个分组中的其他信元。早期分组丢弃要求 设置一个临界值。当交换机缓冲队列达到这个临界值时，就找到属于下一个分组 的第一个信元，丢弃属于这个数据分组的所有信元。实验表明，早期分组丢弃的 性能要优于部分分组丢弃。 1 2 虚通路带宽优化分配 a t m 已被i t u t 组织挑选为宽带综合业务网( b - i s d n ) 上的传输与复用技术。 它是面向连接的，即在两个用户通信前必须建立一条虚通道( v i r t u a lc h a n n e l ) 。 为减少v c 管理的开销，可利用一条虚通路( v i r t u a lp a t h ) 将共用该v p 的若干 v c 捆绑在一起，以便将它们作为一个组统一管理。有了v p 就可以在物理的a t m 网络上建立一个逻辑上的网络。这样，网络效率能发挥到一个什么程度就依赖于 我们所设立的v p 逻辑网如何适应网络中流量的变化以及可能发生的网络故障。 根据网络流量的变化或故障情况而改变v p 设置的过程称为设置管理。设置 管理涉及到根据新的流量和故障条件，在由物理网络的结构及资源所形成的各种 约束条件下，选取一种最优的或近最优的设置。新设置是由新的基础建设的需要 或流量的明显