（计算机系统结构专业论文）层次交换网络体系结构及其服务质量实现机制研究.pdf

堡竺奎堡塑堑堡墨竺塑墨苎竺! 型曼曼兰墨塑型竺篓二塑兰一 摘要 本文讨论了i n t e m e t 体系结构及其服务质量的实现机制，提出了一种新的i n t e r n e t 体系结构：层次交换网络( h n e t ) 体系结构，并在这个体系结构的基础上讨论了服务 质量的实现机制。 ri n t e m e t 从诞生到成为目前全球最大的数据网络仅经过了数 年的时问。但是随着 i n t e t 规模的爆炸性增长以及它朝着提供多服务，商业化发展的趋势，i n t e m e l 遇到了 许多在设计初期根本无法预料的困难。这些困难主要表现当前i n t e m e t 缺乏持续扩展的 能力和不能提供满意的服务质量，因此不能满足i n t e m e t 进步发展的要求。而目前提 出的许多基于现有i n t e r n e t 的解决方案都只能部分解决问题，而且通常增加了实现的复 杂性。本文的分析表明，唯有对i n t e m e t 进行根本的革新才能解决这些问题并满足i m e m e t 未来发展的要求。 h n e t 是一种基于i p v 6 的地址和包格式的新一代i n t e m e t 体系结构，它采用和层 次地址结构一致的层次拓扑结构。h n e t 利用地址和拓扑的一致性使用地址计算的交 换方式完成选路，从而从根本上取消了路由表和路由协议，不但解决了路由的扩展性 问题，还有效的降低了网络设备设计和实现的复杂性。h n e t 的体系结构的固定路径 和层次拓扑还为服务质量的实现提供了有力的支持，使得多服务，保证的服务质量成 为可能。刁勺一 本文首先讨论了h n e t 的体系结构，包括它的层次地址和树形拓扑结构，本文提 出了用逻辑节点域的方式实现层次树形拓扑的可靠性，并讨论了其路由计算的方法。 我们还分析了逻辑节点域的实现，h n e t 和现有网络的互操作性和部署等问题。 在h n e t 体系结构的基础上，本文着重分析了基于h n e t 体系结构的服务质量实 现机制。本文首先提出了h n e t 服务质量的基本框架模型。l 通过充分利用h n e t 拓扑 结构的优点，同时结合当前i n t e m e t 服务质量实现的一些方法，印、e t 服务质量框架模 型能够支持良好的扩展性和对网络资源的优化利用。具体地说，h n e t 支持三种服务 等级：保证服务，公平共享服务和尽力服务。对于保证服务，我们支持延迟保证服务 和吞吐率保证服务两种类型。公平共享服务的主要目的是实现网络资源的公平利用， 而尽力服务主要是为了兼容现有的i n t e r n e t 服务模型，它不作任何控制。本文详细讨论 了每种服务的具体方法： 1 ) 本文分析了在层次树形结构下实现延迟保证的三种基于汇聚的方法：边界汇聚， 逐层汇聚和任意汇聚。对于边界汇聚，本文主要分析了边界汇聚调度和每流调度的延 迟性能，提出并证明了边界汇聚调度的延迟性能优于每流调度的条件。对于任意汇聚， 本文提出了保证任意汇聚性能的公平汇聚算法：双层抢占式汇聚，并分析了其汇聚性 能。对于任意汇聚本文分析了在一定的网络利用牢条件下任意、【聚的最坏延迟约束， 并提出了基于跳数区分的任意汇聚方法。除j ，阔度方法，本文还讨论了基于汇聚的资 层! 堕堡型竺竺墨竺塑壁坚里墨垦兰壅翌! ! ! ! 竺垄! 塑望 一 一一一 源管理方法。基于汇聚的方法不仅保证了延迟保证的性能，还具有良好的扩展性，本 文提出的三种汇聚方法是在扩展性，性能方法的不同折中，可以应用在h n e t 不同的 服务质量和实现要求下。 2 ) 本文还提出了一种基于边界汇聚每节点整形的算法来实现吞吐率保证，我们证 明了该算法可以在有限的缓冲区下实现吞吐率保证，并分析了实现吞吐率保证的缓冲 区大小约束，以及为了提高扩展性而进行的改进方法。 3 ) 本文提出了应用协作的拥塞控制( a c f c c ) 方法实现公平共享服务。这种方 法基于对流量层次速率编码，通过网络层的层次丢弃控制和应用层的层次标记和流量 控制实现对网络资源的公平共享。本文提出了基于共享速率空间的层次标记算法，基 于最大层次丢弃的缓冲区管理方法和基于层次标记反馈的应用层流量控制算法。并讨 论了用加权的公平共享服务实现v p n 吞吐率保证的问题。 本文提出的服务质量方法在h n e t 拓扑结构的支持下，实现了不同等级的性能保 证，并支持良好的扩展性。其中的一些方法，例如公平共享服务也可以用在现有的i n t e m e t 体系结构中。，广 j 。 关键词：。亘鐾匿，皂垡墅喹系结构，匿兰至厦量，l 麴摩，缓冲区管理，坦塞! ! 型 丘 层次交换网络堡墨竺塑墨苎璺竺璺塑型竺窒! 垒! 竺! 竺! 一 r e s e a r c ho nh i e r a r c h i c a l l ys w i t c h e d i n t e r n e t ：n e t w o r k a r c h i t e c t u r ea n dq u a i i t y o fs e r v i c o y a n gm i n g c h u a n ( c o m p u t e r n e t w o r ka r c h i t e c t u r e ) d i r e c t e db y ：q i a nh u a l i n n l i st h e s i sa d d r e s s e s 山ei n t e m e ta r c h i t e c t u r ea n d i t sq u a l i t yo fs e r v i c e ( q o s ) p r o v i s i o n an e wi n t e m e ta r c h i t e c t u r e ：h i e m r c h i c a l i ys w i t c h e di n t e m e t ( h n e t ) i sp m p o s e d t or e s 0 1 v e t h ep m b l e m so fc u r r e n ti n t e m e ta r c h i t e c t u r e a n dt 1 1 ep r o v i s i o no f t h eq o si nh n e ti s m a i n l yf o c u s e d i nt h i st h e s i s t h ei n t e m c ts p e n d so n l yt e n so f y e a r st 0b et h el a r g e s t 出幢ac o m m u n j c a t i o nn e t w o r k i n t h ew o r l d h o w e v e r ，d u et ob o t l lt h er a p i di n c r e a s i n gi ns i z ea i l d p a c i t y ，a n dt h ec o n t i n u o u s e v o l v i n 2t ob u s i n e s sn e t w o r kw i mm u i t i s e “i c e ，“i sm o r ea i l dm o r ed i 伍c u l tf o ri n t e r n e tt o s a t i s 匆m ef u t u r er e q u i r e m e n t si ns c a l a b i l i t ya n dq u a l i t yo fs e r v i c e a l t h o u g hm a n y m e t h o d s b a s e do nt h ec u r r e n ti n t e m e ta r c h i t e c t u r ea r ep r o p o s e dt oo v e r c o m em e s ed i 街c u l t i e s ，t h e y g e n e r a l i ya d d r e s so l l l yp a n s o f t l l e ma i l do f t e ni m r o d u c es o m ec o m p l e x i t yi ni m p l e m e n t a t i o n s t h ea 1 1 a l y s i so f t h i st h e s i ss u g g e s t st l l a t ：o n l yi f t h eb a s i ca r c h i t e c m r ei sc h a l l g e d ，i ti sp o s s i b l e t or e s o l v et h e s ep r o b l e m sa n ds a t i s f yt h ef u t u r er e q u i r e m e n t s h n e ti san e wi n t e m e ta r c h i t e c t u r eb a s e do nt h eh i e r a r c h i c a la d d r e s sa n dp a c k e t s t r u c t u r eo fi p v 6 i ti st h em o s ti h l p o n a n tc h a r a c t e ro fh n e tt h a tt h eh i e r a r c h i c a l t o p o i o g yo f h n e ti sc o n s i s t e n tw i t ht h eh i e r a r c h i c a la d d r e s ss t r u c t u r e t h ec o n s i s t e n c yb e t w e e nt h e t o p o l o g ya n dt h ea d d r e s ss t m c t u r em a k e s i tp o s s i b l et os w i t c hp a c k e t sb yc o m p u t i n ga d d r e s s ， n o tt or o u t ep a c k e t sb yj o o k i n gu pr o u t e t a b i e s o ，t h ep r o b l e m si n t r o d u c e db yl a r g er o u t e t a b l e ，s u c ha st h ec o m p i e x i t yo fm u t et a b l em a i n t e n a n c ea n dt h ei i m i t a t i o no fm u t e rp a c k e t f o r w a r d i n gc a p a c i t y c a nb er e s o l v e d e a s i i y t h en x e dp a c k e t f o r w a r d i n gp a t ha n dt h e h i e r a r c h i c a lt o p o l o g yi nh n e ta l s ob e n e n t g r e a t l yt ot h eq u a l i t y ，o fs e r v i c es u p p o r t i nt h i s t h e s i s ，t h ea r c h i t e c t u r eo f 玎q e ti s6 r s t l yi n t r o d u c e d ，i n c l u d i n 叠i t sa d d r e s s s 仃u c t u r ea n d t o p o l o g ym o d e l ，r o u t ec o m p u t i n g ，l o g i c a ln o d ed o m a i ni m p l e m e n t a t i o n ，m u l t i h o m es u p p o r t ，t h et r a n s l a t i o nf r o mt h ec u r r e n ti n t e m e tt oh n e t ，a n dt h ec o o p e r a t i o nb e t w e e n t h e m b a s e do nt h ea r c h i t e c t u r eo fh n e t t h eq o sp r o v i s i o no fh n e ti sm a i n l vf o c u s e di n t h i st h e s i s t h ef a m e w o r ko f q o s i nh n e ti sf i r s t l yd e s c r i b e d c o m b i n i n gt h ea d v a n t a g e so f h n e ta r c h i t e c t u r ew i t hs o m em e t h o d e si nt r a d i t i o n a ii n t e m e t0 0 s m o d e l s ，t h i sf r a m e w o r k c a na c h i e v eg o o ds c a l a b i l i t yi nq o s p r o v i s i o n m o r es p e c i f i c a j ly t h ef h m e w o r kd e f i n e st h r e e l l i 层次奎垫翌竺竺墨竺塑些些璺竺垦至兰翌墨! ! 翌窒! 垒! ! ! ! 竺! 一一一 h 一一。一。 s e r v j c ed e g m d e s ： g u a r a l l t e e d s e r v i c e ，f a i r _ s h a r i n g s e r v i c e a n db e s te f f b r ts e r v i c e f o r 业u a r a n t e e ds e r v i c e ， t w ot y p e sa r es u p p o n e d ：d e l a yg u a r 觚t e e d s e r v i c ea n dt | l m u g h p u t g u a r a i l t e e ds e r v i c e t h et a r g e to ff a i r _ s h a r i n gs e r v i c ei st ou t i l i z em e n e t w o r kr e s o u r c e sf a i r l y f o re v e r ya p p l i c a t i o n t h eb e s te 行b r ts e r v i c e ，s a i t l ea st h a ti nt h ec u r r e n ti n t e m e t ，d o e sn o m i n g f o rq o sc o n t r 0 1 t h em a j o rc o n t r i b u t i o n sf o rq o sp r o v i s i o ni nh n e t i nt h i st h e s i sa sf 0 1 l o w ： 1 ) t h r e ep a t h - b a s e da g g r e g a t i o nm e t l l o d sa r ep m p o s e d t oi m p l e m e n td e l a yg u a r a l l t e e d s e r v i c e ：e d g e _ b a s e da g 伊e g a t i o n ，p e r - l a y e ra g 酽e g a t i o n a n df r e ea g g r e g a t i o n i nm ee d g e 。 b a s e d a g g r e g a t i o n m e t h o d ，m ec o n d i t i o n t h a tt 1 1 e d e l a yp e r f o n n a n c e w i t h e d g e _ b a s e d a g g r e g a t i o ni sb e n e r t h a l lt h a tw i t hp e 卜n o wc o n t r o l i sp r o v i d e da n dp r o v e d i nt h ep e 卜l a y e r a g g r e g a t i o nm e t h o d ，i no r d e r t og e td e l a y g u a r a n t e e ，a f a i ra g 伊e g a t i o na l g o r i t h mi sp r o p o s e d i nt h ef 沁ea g g r e g a t i o nm e t h o d ，t t l ed e i a yb o u n di nt h e 、帕r s tc a s ei sd e r i v e du n d e rs o m e “n k u t i l i z a t i o nl i m i t a t i o n 1 h e s ep a t h - b a s e da g g r e g a t i o nm e t h o d sm a k et r a d e o f rb e t w e e nd e l a y g u a r a n t e ep e r f b 1 1 a 1 1 c ea i l ds c a l a b i l i t y t h er e s o u r c em a n a g e m e n t a 1 1 dt h ea d m i s s i o nc o n 仃o l i nt h ec a s eo f a g g r c g a t i o na r ea l s oa d d r e s s e d 2 ) a ne g r c s s - b a s e dp e 卜n o d ea g g r e g a t e ds h a p i n gm e t 上1 0 di sp r o p o s e dt og u a r a n t e e 山e t h m u g h o u tf o re v e r yn o w t h eb u 任h r e q u i r e m e n t so r l i m i t a t i o ni nn o d e sw i t hd i 圩e r e n tl a y e r a r ea l s od e r i v e du n d e rt h i sm e t h o d 3 ) a na p p l i c a t i o n c o o p e r a t e df a i rc o n g e s t i o nc o m m l ( a c f c c ) m e t h o di sp m p o s e di n t h i st h e s i s t h eb a s i ci d e ao fa c f c ci st h ec o o r d i n a t i o nb e t 、v e e nn e t w o r ka n da p p l i c a t i o n t h ec o r em e c h a n i s m sa r eh i e r a r c h i c a lr a t ec o d i n ga n d d r o p p i n ga i g o r i t h mi nn e t w o r ka n dt h e f l o wc o n t m l b ya n a l y z i n gt h ea c k n o w l e d g e dp a c k e t sw i t hr a t ec o d ei n a p p l i c a t i o n w e i n t r o d u c et h eb a s i c a l g o r i t l l r i la n de v a l u a t et l l ep e 响n n a l l c ew i ml o t so fe x p e r i m e n t s t h eq o sp r o v i s i o nm e t h o d sp r o p o s e di n t h et h e s i sc a l l g e tg o o dp e r f o r m a n c ea n d s c a l a b i l i t yi nt h eh n e t m e a n w h i l e ，s o m em e t h o d s ，s u c ha sa c f c cc a na l s ow o r kw e l li n t h ec u r r e n ti n t e m e ta r c h i t e c t u r e k e y w o r d s ：i n t e m e t ，n e t w o r ka r c h i t e c t u r e ，q o s ，p a c k e ts c h e d u l i n g ，b u f f e r m a n a g e m e n t ， c o n g e s t i o nc o n t r o i 7 v 独创性声明 本人声明我所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本 文所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：啼勿e 冉t 、1 日期： 砌2 牛二 关于论文使用授权的说明 中国科学院计算技术研究所有权保留送交论文的复印件，允许论文被 查阅和借阅：并可以公布论文的全部或部分内容，可以采用影印、缩印或 其它复制手段保存该论文。 作者签名：啷移柏“导师签名 编日期：叫2 织2 二 第一章引苦 一 第一章引言 i n t e m e t 从诞生到现在成为全球最大数据通讯网络仅经历了短短的数十年的时旧j 。 在这期间，i n t e m e t 从一个简单的试验性网络演变成为一个巨大的商业网络，它不仅成 为了全球数据通讯的基础，而且从根本上影响了整个人类社会的生活方式。 但是随着i n t e m e t 的进一步发展，i n t e m e t 遇到了许多在设计初期根本无法预料的 困难。这些困难使得1 1 1 t e m e t 变革的要求越来越迫切。本章简要的对i n t e m e t 的发展变 化，i n t e m e t 的缺点和现有的解决方案进行了分析。并指出：唯有对i n t e m e t 进行根本 的革新才能解决这些问题并满足i n t e m e t 未来发展的要求。 1 1 当前i n t e m e t 的新变化 近年来，随着网络技术的进步和i m e m e t 进一步商业化，i n t e m e t 呈现出许多新的 特征，这些特征包括： 一i n t e r n e t 拓扑和规模的变化 1 】：i n t e m e t 不但保持了规模的持续扩大，还呈现出更 为复杂的拓扑连接。规模的扩大主要表现在a s ( 自治系统) 的增加。因为i n t e m e t 从宏观上可以看作是各个相对独立的a s 的松散联合。a s 的数量和它们之 t 日j 的连 接性的变化会对整个i n t e m e t 的结构带来影响。统计表明，在1 9 9 5 年9 月，全球仅 有9 0 9 个a s ，到了1 9 9 8 年1 2 月，a s 的数量达到了4 4 2 7 个。到了2 0 0 0 年底，达 到了6 2 9 8 个。按照这种速度增长，到2 0 0 5 年，1 6 位的a s 号将被耗尽。除了a s 数量的增加，a s 之间的连接性也在增强，1 9 9 5 年9 月，a s 的连接度是2 9 9 ，到 了1 9 9 8 年1 2 月，增加到了4 1 1 8 。这表明，a s 之间呈现密集互连的趋势。这种，趋 势导致i n t e m e t 的拓扑更加复杂。连接性的增强将对i n t e m e t 的路由等产生重大的影 响。 一i n t e r n e t 骨干网络容量的增加：i n t e m e t 容量的增加表现在网络链路带宽的增加和网 络节点处理能力的增强。容量增加主要得益于以光通讯为代表的传输技术的巨大进 步 2 】。目前的高速主干网络普遍采用了d w d m ( 密集波分复用) 技术使得链路带 宽达到了1 0 g ( o c 一1 9 2 ) 以上，而d w d m 技术在2 0 0 0 年已经可以支持在单个光 纤上容纳1 2 8 个波长，每个波长4 0 g 的带宽，传输距离为3 0 二k m 。这样，每根光纤 即可承载t b 级的流量。而且采用d w d m 技术的光纤容量正以6 个月翻一番的速 度增长，则甚至远远高于摩尔定律的增长速度( 1 2 1 8 个月) 。i n t e m e t 骨干网络容 量的增加不仅意味着有了更多的原始带宽，它还对i n t e m e t 的设计产生革命性的影 响：一方面网络( 交换) 节点的压力增加了，为了在t b 级上传输数据，需要更高 性能的路由器。目前已经有支持t b 级的路由器，但是端口速率通常还，j 能达到g b 层次交换网络竺至竺望墨苎壁垒堕苎壅墨! ! 型竺塑 一 一一 绒。另方面容量的增加对整个刚络扩展性的要求增加了，这对在网络中支持服务 质量有了更高的要求。 一传输网络体系结构的改变 3 ，4 】：随着光通讯技术的发展，特别是d w d m 和全光的 交叉连接器( 0 x c ) 等技术的发展，使得i p 的传输网络和协议层次发生了根本的 变化。主要表现为：1 ) 协议层次减少，从1 9 9 3 年的i p a t m s o n e t d w d m f i b e r 五层结构到现在的i po v e rd w d m 【5 】两层结构，协泌层次咎少的原因是原有的层次 提供的功能已经不再需要或者向i p 或光层转移。例如原有的a t m 层提供的多服务 可以由i p 层的q o s 机制实现，原有的s o n e t s d h 提供的快速保护切换也可以由 光层来实现，协议层次的减少不仅降低了实现的复杂性，还提供了更好的灵活性， 例如光通道传输没有协议的依赖性，可以直接在光通路上支持以太网的帧；2 ) 网 络呈平面化发展，即网络的连接越来越呈扁平的互连结构。这主要是由于光网络中 可用光通路( 波长) 的增多，使得网络内部节点的全连接成为可能t 平面化导致在 网络内部传输跳数的减少，同时增加了网络流量工程的必要性；3 ) 全光网络，通 过在中间节点使用全光的光交叉连接器，在访问节点使用全光的上下复用器 ( o a d m ) 避免了光电光( 0 e 0 ) 的转换，全光网络可以进一步提高网络的容量， 降低网络的成本。同时，采用g m p l s 【6 】等基于流量工程的信令技术可以建立不同 层次的光通路。提高了网络的灵活性和可伸缩性。从这些变化可以发现，由于以光 技术为基础的低层传输技术本质上带有电路交换的特征，使得i n t e m e t 在一定程度 上正朝着包交换和电路交换相互融合和互补的方向发展。这无疑将对整个i n t e m e t 的发展产生深远的影响。 - i n t e m e t 流量的超指数增长【5 ：流量的增长一方面得益于主干网络容量的增加，另 一方面得益于接入网络瓶颈的打破。目前大量采用的x d s l ，c a b l em o d e m ，宽带网 络( 局域网接入) 等技术打破了原来的i n t e m e t 拨号上网用户的带宽瓶颈。这样， 每个用户的可用带宽大大增加了，这刺激了每个用户流量的增长，同时网络中用户 的数量也呈指数增加，这些因素导致i n t e r n e t 的流量呈现出超指数增加的趋势。美 国最大的i s p 之一的u u n e t 的统计表明，它的流量增加从以前的每四个月翻一番 到现在的每l o o 天翻一番。网络中多媒体应用和多媒体资源目趋增加也是i n t e r n e t 爆炸性增长的原因。流量的增加为网络节点和网络链路的容量都提出了更高的要 求，因为网络的设计必需考虑到未来流量的变化，即：网络必须是高度可扩展的。 _ 应用类型的增加和应用模式的转变 7 】：随着i n t e m e t 的普及和商业化，出现了大量 新的应用，特别是多媒体应用，包括视频会议，i p 电话，虚拟在线游戏，远程医疗 等等。相应的出现许多新的应用层和传输层协议，如流媒体传输协议r t p ，r t c p 等。应用类型的增加为i n t e m e t 提供服务增加了复杂性，因为不同的应用通常有不 同的要求。在应用类型增加的同时，i n t e m e t 的应用模式也在发生改变。i n t e m e t 的 应用经历了所谓的二：次“浪潮”【8 】：第次以计算的共享为特征，这时f tp t e l n e t e m a i l 等应用足m t e m e t 的主流应用；第一i 次则以客户服务器模式和格式化的语 第一章引言 言为基础，其代表的应用是w w w 应用：目前正在经历第三次浪潮使得i n t e m e t 的 应用模式朝着合作化，对等( p 2 p ) ，交互方向发展。典型的应用包括n a p s t e r ，i m e s h ， k a z a a ，g a m i n 舀v i d e o 等。i n t e m e t 应用模式的变化使得它更需要实时的交互能力和对 网络的变化迅速做出反应。 i n t e m e t 应用模式的转变的另一个表现是i m e m e t 朝商 业化发展。i n t e m e t 的商业化发展也在许多方面为i n t e m e t 提出了新的要求，例如服 务的保证，安全性，可靠性等等。 总之，i n t e m e t 出现的新特征一方面反映了i n t e r n e t 的需求，另一方面为i n t e r n e t 的 进化提供了新的驱动力。这些需求表现在：1 ) 对性能扩展性的要求，要求在网络规模 扩大，流量增加的情况下，保持甚至提高网络传输的性能：2 ) 对灵活性和可靠性的要 求，要求用户可以灵活的接入方式并保持与i m e h 坞t 连接的可靠性，这一点反映在a s 的增多和基于多宿主的连接性的增强；3 ) 对应用的支持的要求，要求i n t e r n e t 应该支 持丰富的应用类型，并提供足够的服务质量保证。尽管目前i n t e r n e t 仍然可以保持高速 的增长，并提供稳定可靠的服务。但是当前的i n t e m e t 不适应在规模和流量上的长期爆 炸性增长，不能满足用户日益提高的对服务质量的需求的问题已经开始逐渐显露出来。 我们需要对i m e m e t 的体系结构进行重新分析以从根本上提出解决i n t e m e l 不适应新发 展的方法。 1 2 当前i n t e m e t 的突出问题 i n t e m e t 的成功得益于它的一些基本建立原则，包括：1 ) 平面网络拓扑结构，i n t e m e t 设计的最初原则是保证极强的可靠性，它要求在网络严重损坏的条件下也能保持网络 的正常工作。因此，i n t c m e t 采用了平面的网络拓扑，尽管后来由于网络规模的扩大， 不得不采用了两层的路由结构，但本质上还是平面的。平面网状结构可以保持很高的 连接性，同时，网络结构有很高的灵活性，便于扩充；2 ) 开放式网络结构，如前所述， i n t e r n e t 可以看作是网络或自治系统的松散联合，他们仅仅依靠共同的地址空问和一个 以自治系统，网络为单位的路由协议来连接，网络本身可以有不同的结构，策略。这种 丌放式异构性的网络组成使得i n t e m e t 有很强的包容性和扩展能力，新的网络的增加十 分方便。所以，i n t e r n c t 在规模扩大了几个数量级之后仍然能保持正常，稳定的工作： 3 ) 无连接包交换特性【9 】，这种方式特别适合数据流量，因为网络对数据的处理非常简 单，复杂的可靠性确认，安全，甚至流量控制都依靠应用层协议由主机来完成。这样 网络设计的复杂性降低了网络的花费降低，升级更加容易。新的应用不需要对网络 低层协议作任何的修改，这是i n t e m e t 应用不断涌现并广为普及的重要原因。同时，d 于应用的可靠实现不依赖于网络的低层支持，应用可以根据自身的特点没汁满足可靠 性的方法。但是随着i n t e m e t 的进步持续爆炸性增长，一些不适应新的要求的征兆已 经出现，具体的说，当前的i n t e m e t 有如下的突出问题： 墨堕! 坠塑竺竺墨堕塑墨茎壁墨垦里茎墨! ! 型竺竺 可扩展性：复杂的路由技术导致i n t e m e t 的可扩展性瓶颈。具体的说，当6 h 的i p 路 由协议包括几个核心技术：a ) 地址分配技术( 划分a ，b ，c 三类地址) ；b ) 两层的 路由体系结构( e g p i g p ) ；c j 基于变长的地址匹配的每包转发。这几个技术是相 互关联的。网络地址类型的划分有助于减少网络的数量，并保持足够多的小型网络 ( c 类网络) ，使得它能够支持网络的数量和灵活性要求。但是，i n t e m e t 的发展远 远超出了设计的预期。目前i n t e m e t 上网络和主机的数量都呈现快速增长的模式， 而且网络的连接性不断增加。因此，一方面i p v 4 的地址开始耗尽，特别是对于发 展中国家( 例如中国) ，他们有众多的用户，但是分配到韵网络地址非常少。另一 方面，网络和连接性的增加导致了路由的复杂性增加，路由表迅速扩大。到2 0 0 0 年，b g p 路由表项已经达到7 0 0 0 0 【1 0 ，1 1 】同时仍有快速增长的趋势。路由表的 扩大不仅增加了网络路由设备的成本，还使得基于路由表查找的包转发更加复杂， 从而影响到了包转发的速度，这对于支持高速网络t b 级的转发要求显然是非常困 难的。第三个方面是路由收敛的问题，由于网络的数量多，连接性高，路由也更复 杂。特别是对于b g p 协议涉及大量的策略和多连接问题，使得b g p 的管理非常复 杂。 交换节点成为瓶颈：随着网络容量的扩大，交换节点的交换能力再次成为制约网络 进一步扩展的瓶颈，当前的网络链路由于采用了d w d m 技术，已经可以在单个光 纤上实现t b 级的带宽，可以支持更高带宽的技术还在不断涌现，凶此，链路可用 带宽几乎是无限的。但是，交换节点的交换能力的增长却有限。尽管在1 9 9 8 年， 市场上已经出现容量达到5 6 t b p s 甚至6 4 t b p s 的路由交换设备，这个数值确实惊 人，因为全中国当前所有电话程控交换机的容量总和，也不及两台这样的设备大。 但这样的设备只说明人们有能力从设备结构上做到了设备容量的可扩展性，把同等 速度的众多电路拼装成一个巨型设备，从对每个i p 报文的处理速度来看，与容量 为数十g b p s 的路由交换设备没有区别，端口速率也不过是2 5 g b p s ，而且还做不 到2 5 g b p s 的线速处理速度。与一对光纤的2 5 t b p s 容量相比，差三个数量级。 _ 服务质量( q u a i 时o fs e r v i c e ：q o s ) 问题：随着当前所有的通讯平台向i p 融合的 趋势，即e v e r y t h i n go v e r i p 以及i n t e m e t 朝商业化发展，使得用户对i n t e r n e t 提供的 服务要求越来越高。因此i p 网络需要对大量多媒体业务，特别是话音和视频，提 供服务保证支持。这是传统的基于b e s t 。e 硒n 的转发方式不能提供的。当前i n t e m e t 体系结构不能有效支持服务质量的因素有几点：1 ) i n t e m e t 本质是无连接的结构， 它仅以b e s te f r o r t 的方式转发包，在网络中不提供任何支持服务质量的功能和函数， 而依靠应用本省的适应性实现传输的可靠性和流量控制，这是当日ii n t e m e t 使用最 广泛的传输层协议t c p 协议的基本思想。但是，有效的服务质量提供要求网络核 心提供一定的支持，应用本身不能很好的支持服务质量，一个明显的例子是依靠应 用本身的流量控制，网络不能杜绝恶意的流过多的占用资源。2 ) i n t e r n e t 是包交换 的机制，尽管相对电路交换而言，包交换可以支持更高的效率和灵活性。但是包交 4 第一章引言 一一 换的结构本质上对服务质量是不利的，这是包交换网络在传送多媒体流量时性能远 低于电路交换网络的根本原因。因为包交换网络以包为单位，在每个节点，即使不 出现队列等待的情况，包的存储转发也需要时间，包越大，这个时间就越长。因此， 为了接近电路交换的性能，必须使用小包( 例如a t m 的信元长度为5 3 字节) ，但 是小包又降低了利用率，因为包头的开销是一定的。另外，每个包需要对包头解析 处理，这制约了扩展性。因此，包交换网络对突发性的数据流量是合适的，但是对 流媒体的服务质量去很难保证。3 ) i n t e m e t 的每包路由方式，每包路由可以支持很 强的可靠性，但是会导致同一个流的不同包转发路径不确定，这对实现基于流的服 务质量保证是一个很大障碍。因为任何基于流的有效的服务质量控制必须依赖于路 径的确定性，否则即无法保证包的按序到达，又无法实现有效的资源的预留和管理。 4 ) i n t e m e t 本质上是由相对独立的网络连接而成的，每个网络有自己的实现和使用 策略，而有效的服务质量提供通常需要端到端的所有节点的协作，这在i n t e m e t 这 种非常松散的结构中是很难实现的。i m e m e t 本身的开放性使得各个网络拥有各个 的实现方法和策略。这种异构性使得端到端的控制非常困难。通常只能依靠网络层 之上的功能来解决。总之，服务质量要求和i m e m e t 最初的设计原则本质上是相背 离的，企图在i n t e m e t 现有的体系结构上解决服务质量问题要求实现起来十分复杂， 要么性能不尽如人意。因此，服务质量问题尽管被研究了许多年，提出了许多方法， 但是都只能是对现有体系结构的修补，在i n t e m e t 中的真正使用还是很有限的。仅 有一些服务质量的算法，如加权公平队列( w f q ) 等得到了普遍的支持。但也未得 到充分的使用。随着i m e m e t 的发展，特别是网络流量的增加，网络应用月趋复杂 化，支持有效的服务质量保证显得更加迫切，同时也更加困难。 一流量工程( t m f f i c e n g i n e e r i n g ) 问题：流量工程的目的是对网络资源的进行优化， 广义的讲，流量工程也属于一种服务质量控制。对于网络服务商而占，流量工程可 以提高资源的利用率，平衡网络中的流量。对于用户而言，有效的流量工程有助于 提高i 网络传输的性能，避开拥塞的链路。随着i n t e m e t 流量的增加，以及i 小e m e t 流 量本质上的突发性特征，流量工程显得日趋重要。但是i n t e m e t 的无连接和最短路 径路由的特性使得i p 层的流量工程的实施很困难，通常需要借助低层的功能来实 现，例如a t m ，m p l s 等。这增加了管理和维护的复杂度。尽管如此，动态的流量 工程仍然难以实现。 1 3 目前的解决方案 针对前面讨论的问题，i n t e m e t 界提出了许多解决方案，我们作简单的分析 无类域问路由( c i d r ) 1 2 】：c i d r 的目的是实现地址的聚合以控制路由表的大小， 即地址分配机构通过将连续的地址合并成地址块，并由统一分配给i s p ，i s p 仅向 层次交换网络竺墨堕塑丝苎堡堑堕兰兰墨塑型竺窒 一一 外宣告这个成块的地址。c i d r 在b g p 4 1 3 ，1 4 中实现并在1 9 9 4 年开始实施。在c i d r 实施的最初阶段，的确取得了很好的效果 1 0 】，b g p 路由表大小从1 9 9 4 年开始放 慢增长，在实施的初期甚至有所下降。随后的四年( 1 9 9 4 - 1 9 9 8 ) b g p 几乎保持7 线性的增长，每年约增加l 0 0 0 0 项，但是从1 9 9 8 起，情况发生了变化，b g p 路由 表重新恢复了指数增长。造成c i d r 失效的原因是网络互连程度的增加，即多宿主 f m u i t i - h o m e ) 小型网络的迅速增加破坏了c i d r 的地址聚合能力，表现在c i d r 地址 聚合项中出现了许多空洞( h o l e ) ，这些空洞是具有特殊路由策略的小型网络添加的， 目的是保持网