（计算机科学与技术专业论文）域间路由系统自组织特性及关键问题研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 基于b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 的域问路由系统作为i n t e r n e t 的核心设 施，不但是传递网络可达信息的基本机制、自治系统a s ( a u t o n o m o u ss y s t e m ) 互 连的纽带和i s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 实现策略控制的主要手段，而且对i n t e r n e t 的演化起着关键作用。目前域间路由系统在扩展性、收敛性、稳定性、健壮性和 安全性等方面存在诸多问题，对i n t e r n e t 的性能和安全造成不良影响，并会制约新 一代互联网的健康发展。 已有的研究工作大都基于传统路由系统的严格层次模型，采用静态的基于图 论的方法，没有很好地把握域问路由系统的拓扑规律和动态行为模型，域间路由 系统的许多问题没有得到有效地解决。随着i n t e m e t 规模的扩展和商业化进程的加 速，域间路由系统规模膨胀、结构密集、互联关系复杂、路由策略多样，表现出 显著的开放复杂巨系统特征。 本文基于域间路由系统自组织特性，利用复杂系统理论和i s p 之间交互的自 组织规律，提出改善域问路由系统性能以及实现域间组播部署的新方法和新机制， 为构造安全、可信、可控、可管的新一代互联网，促进新一代网络的持续健康发 展做出贡献。 本文主要从以下五个方面进行了深入研究： 域间路由系统自组织特性分析 域问路由系统和i n t e m e t 一样是一个复杂巨系统，自组织理论是当前对于复杂 系统研究的重要成果，是研究复杂系统的有效工具。本文从自组织特性的角度分 析了域问路由系统的内在规律和外在表现，并且评价了改善域问路由系统的扩展 性、收敛性、稳定性和安全性的各种方法。在对域间路由系统发展趋势进行剖析 的基础上，给出了利用自组织特性解决域问路由系统问题的指导原则和几种可行 的方法。 域问路由系统动态演化过程研究 域问路由系统是以a s 为节点构成的自组织系统。本文研究了i n t e m e t 域间路 由系统中各个a s 在其成长消亡过程中需要考虑的各种影响因素，系统地阐述了 a s 之间商业关系的产生和变化，基于复杂系统理论建立了i n t e m e t 域问路由系统 的动态演化模型_ m v h o t 。通过对模型的研究，分析了多宿主、商业关系等因 素对域间路由系统拓扑及特性的影响。 i n t e m e t 域问路由协议b g p 收敛趋势的预测和分析 路由表的快速增长增加了路由器处理路由信息的时延和路由信息的扩散时 间，网络规模的膨胀加大了路由信息的扩散范围，从而影响b g p 协议的收敛延迟。 第i 页 国防科学技术大学研究生院博士学位论文 深入研究域问路由系统的基本理论，以确定域l 、日j 路由系统扩展性和收敛性的基本 性能约束关系成为当务之急。本文考虑了对收敛时间产生影响的各种因素，给出 了更精确的b g p 收敛时间上界，进而根据域问路由系统的幂律特性和b g p 协议标 准分析了各个因素的变化趋势，在此基础上，对b g p 的收敛时间的变化趋势进行 了预测。理论分析和模拟试验显示b g p 的收敛时间最终会受到c p u 处理效率、 a s 度数以及m r a i ( m i n i m u mr o u t ea d v e r t i s e m e n ti n t e r v a l ) 的影响，而传输路径 长度以及链路延迟反而会使收敛时间越来越小。因此网络规模的扩大和应用负载 的增加带给域间路由系统最重要的影响就是对路由器处理能力的挑战。 b g p 收敛性及其对网络性能影响的定量分析 从i n t e m e t 的结构特征入手，分析了b g p 的收敛特性与域问路由系统的幂律 特性及层次性之间的关系。根据幂律特性以及a s 间商业关系的层次性特点建立了 域问路由系统幂律层次模型，将整个域问路由系统分为核心层、转发层和边缘层， 在此基础上分析了不同层次上的各类收敛事件的收敛参数与网络结构的联系。理 论分析和模拟试验显示核心层的收敛时间小于转发层，而影响的a s 数目和转发路 径的范围却大于转发层，并且网络的幂律特性对b g p 收敛性有很大的影响。利用 这个规律，对b g p 的收敛过程进行了改进，提出“b e s tu p 收敛模式，有效地缩 短了网络的收敛过程。 域间组播的计费问题研究 i p 组播广泛部署的困难在于合理的跨域部署和有效的计费机制，这种困难在 很大程度上源于i s p 之间利益的差异和行为协调的复杂性。本文基于自组织理论， 从i s p 之间的关系和a s 结构着手，探求域间组播的合理的结构模型和r p ( 汇聚 点) 部署的经济学方法。实用的收费机制是域间组播部署的关键。本文将i n t e m e t 看作一个生态系统，采用博弈论的方法，提出了有效的收费机制。从不同参与者 的动机出发，系统地讨论了现有的i p 组播服务模型及其收费机制。针对不同的实 际应用场景，提出i c p u s e r 、i c p i s p 和i c p i s p u s e r 三种模型。对每个模型 的适用环境、解析方法以及算法的复杂性进行了全面讨论。 综上所述，本文的工作针对域问路由系统中亟待解决的关键问题提出了有效 的解决方案，对于推进自组织系统的理论研究和实用化具有一定的理论意义和应 用价值。 主题词： 自组织系统、复杂系统、域问路由系统、动态演化模型、b g p 收敛 性、域间组播、模拟 第i i 页 国防科学技术大学研究生院博十学位论文 a b s t r a c t t h ei n t e r - d o m a i nr o u t i n gs y s t e mb a s e do nt h eb g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) p r o t o c o li sak e r n e le s t a b l i s h m e n ti nt h ei n t e r n e t i ti sn o to n l yt h eb a s i cm e c h a n i s mo f e x c h a n g i n gt h er e a c h a b l ei n f o r m a t i o n ，b u ta l s ot h ek e yw a yt oi n t e r c o n n e c tt h ea s s ( a u t o n o m o u ss y s t e m s ) a n de s t a b l i s ht h ep o l i c yc o n t r o li ni s p s ( i n t e r n e ts e r v i c e p r o v i d e r s ) i ti sv e r yi m p o r t a n ti nt h ei n t e r n e te v o l u t i o np r o c e s s n o w a d a y s ，t h e r ea r ea l o to fp r o b l e m si nt h ee x p a n s i b i l i t y ，c o n v e r g e n c y ，s t a b i l i t y ，r o b u s t n e s sa n ds e c u r i t yo f t h ei n t e r - d o m a i nr o u t i n gs y s t e m ，a n dw h i c hb l i g h tt h ec a p a b i l i t ya n ds e c u r i t yo ft h e w h o l ei n t e m e tg r e a t l ya n dr e s t r a i nt h ed e v e l o p m e n to ft h en e x tg e n e r a t i o ni n t e r a c t 1 1 1 ee x i s t i n gr e s e a r c h ，b a s e do nt h es t r i c th i e r a r c h i c a ls t r u c t u r ei nt h et r a d i t i o n a l n e t w o r k sa n du s i n gt h es t a t i cg r a p ht h e o r y ，c o u l dn o tg r a s pt h et o p o l o g yd i s c i p l i n e sa n d t h ed y n a m i cb e h a v i o ro ft h ei n t e r d o m a i ns y s t e mc o m p r e h e n s i v e l y t h e r e f o r e ，m a n y p r o b l e m sc o u l d n tb es o l v e dp e r f e c t l yb yt h e s em e t h o d s w i t ht h er a p i dd e v e l o p m e n to f t h es i z ea n dc o m m e r c i a lp r o c e s si nt h ei n t e r n e t ，t h ei n t e r - d o m a i nr o u t i n gs y s t e mi s b e c o m i n gm o r ee x p a n d e di nt h es c a l e ，m o r ec o m p l e xi nt h ei n t e r r e l a t i o n ，a n dm u c h d e n s e ri nt h es t r u c t u r e a l lo ft h e s em e a nt h a tt h ei n t e r - d o m a i nr o u t i n gs y s t e mi sa l l o p e nc o m p l e xg i a n ts y s t e m ；t h e i n t e r a c t i o n sb e t w e e ni s p s e x p o s e ag r e a t l y s e l f - o r g a n i z e dp r o p e r t y a n dt h i st r e n di st h eb a s i cr u l eo ft h ei n t e r - d o m a i nr o u t i n g s y s t e m ，w h i c hw o u l db e c o m em o r ea n dm o r eo b v i o u si nt h en e x tg e n e r a t i o nn e t w o r k s t u d y i n ga n dd e s i g n i n gan e wr o u t i n gs y s t e mb a s e do nt h es e l f - o r g a n i z a t i o ns y s t e m t h e o r yi sa ne f f i c i e n tw a yt os o l v ea l lk i n d so ft h ep e r f o r m a n c ea n ds e c u r i t yp r o b l e m si n t h er o u t i n gs y s t e m i nt h i sd i s s e r t a t i o n ，w ep r o v i d es o m en e w t e c h n i q u e sa n dm e c h a n i s m st oi m p r o v e t h ep e r f o r m a n c eo ft h ei n t e r - d o m a i nr o u t i n gs y s t e ma n di m p l e m e n tt h ei n t e r - d o m a i n m u l t i c a s t i n gu s i n gt h ec o m p l e xs y s t e mt h e o r ya n d t h es e l f - o r g a n i z e dr u l e si ni s p sb a s e d o nt h es e l f - o r g a n i z a t i o np r o p e r t yo ft h ei n t e r d o m a i nr o u t i n gs y s t e mi t s e l f o u rg o a li s t od os o m ec o n t r i b u t i o nt ot h ec o n t i n u a n c ea n dh e a l t h yd e v e l o p m e n to ft h en e w g e n e r a t i o nn e t w o r ka n dt h ep r o c e s so fc o n s t r u c t i n gam o r er e l i a b l e ，m o r ef a i t h f u l ，m o r e c o n t r o l l a b l ea n dm o r em a n a g e a b l ei n t e r n e t o u r w o r ke x p a n d st h er e s e a r c hi nf i v ea s p e c t sa sf o l l o w s ： a n a l y s i so nt h es e l f - o r g a n i z a t i o np r o p e r t yo ft h ei n t e r d o m a i nr o u t i n gs y s t e m 1 1 1 ei n t e r - d o m a i nr o u t i n gs y s t e mi sac o m p l e xh u g es y s t e mj u s ta st h ei n t e r n e t t h e s e l f - o r g a n i z a t i o nt h e o r yi sa l le f f i c i e n tt o o lt o d e a lw i t l lt h ec o m p l e xs y s t e m w e a b s t r a c tt h ei n t e r n a lr u l e sa n de x t e r n a lb e h a v i o ro ft h ei n t e r - d o m a i nr o u t i n gs y s t e mf r o m t h ev i e wo ft h es e l f - o r g a n i z a t i o np r o p e r t ya n de v a l u a t et h ep r o m o t i o nm e t h o d sf o rt h e e x p a n s i b i l i t y ，c o n v e r g e n c y ，s t a b i l i t y ，r o b u s t n e s sa n ds e c u r i t yf o rb g p b a s e do nt h e p r e d i c t i o no ft h et r e n do ft h e i n t e r - d o m a i nr o u t i n gs y s t e m ，s e v e r a ls o l u t i o n sa n d 第i i i 页 国防科学技术大学研究生院博十学位论文 g u i d a n c ea r ep r e s e n t e db yu s i n gi t ss e l f - o r g a n i z a t i o np r o p e r t y r e s e a r c ho nt h ed y n a m i ce v o l u t i o np r o c e s so ft h ei n t e r d o m a i nr o u t i n gs y s t e m t h ei n t e r d o m a i nr o u t i n g s y s t e m i sa s e l f - o r g a n i z e ds y s t e m c o n s i s t e do f a u t o n o m o u ss y s t e m s o u rr e s e a r c hs t u d ya l lk i n d so ff a c t o r st h a tt h ea ss h o u l dc o n s i d e r d u r i n gi t sp r o c e s sf r o mi t sg r o w t ht od e a t h ，i n t e g r a l l ye x p l o r et h ec o m m e r c i a lr e l a t i o n s b e t w e e na s s a n df a c t u a l l yb u i l dad y n a m i ce v o l u t i o nm o d e lo ft h ei n t e r - d o m a i n r o u t i n gs y s t e mb a s e do nt h ec o m p l e xs y s t e mt h e o r y n a m e dc m v - h o t t h r o u g ht h e a n a l y s i so ft h ee v o l u t i o nm o d e l t h ei n f l u e n c eo ft h em u l t i h o m i n ga n dc o m m e r c i a l r e l a t i o n st ot h e i n t e r d o m a i nr o u t i n gs y s t e mi ss t u d i e d q u a n t i t a t i v ep r e d i c t i o no ft h eb g pc o n v e r g e n c et i m e t h er a p i di n c r e m e n to ft h er o u t i n gt a b l es i z ec a u s e st h er o u t i n gi n f o r m a t i o n p r o c e s s i n gt i m ea n dp r o p a g a t i n gt i m eo nt h en e t w o r km u c hl o n g e r a n dt h ei n f l a t i n go f t h ei n t e m e tm a k e st h ee x p a n d i n gr a n g ea n d p a t h so f t h er o u t i n gi n f o r m a t i o nl a r g e r s oi t i se m e r g e n tt oc o n f i r mt h eb a s i cr e s t r i c t i o nb e t w e e nt h ee x p a n s i b i l i t yo ft h e i n t e r d o m a i nr o u t i n gs y s t e ma n dt h ep e r f o r m a n c eo ft h eb g p c o n v e r g e n c e w ep r e s e n tan e wb g pc o n v e r g e n c em o d e la n da n a l y z et h ec o n v e r g e n c ed e l a y b o u n d so fb g p t h ed e v e l o p m e n tt r e n d so fa l lf a c t o r si n f l u e n c i n gt h ec o n v e r g e n e et i m e a r ef o r e c a s t e db a s e do nt h ep o w e r l a wo fa s 1 e v e li n t e r n e tt o p o l o g ya n dt h eb g p p r o t o c o ls t a n d a r d s f u r t h e r m o r e ，w ep r e d i c tw h a tt h eb g pc o n v e r g e n c ed e l a yw i l lb e t h er e s u l t ss h o wt h a tb g pc o n v e r g e n c et i m ew i l lb ei n f l u e n c e db yp r o c e s s i n g e f f i c i e n c yo fc p u ，d e g r e eo fa s sa n dv a l u eo fm r a ig r e a t l y ，b u tt h ei n f l u e n c eo fp a t h l e n g t ha n dl i n kd e l a yw i l lb er e d u c e d t h eq u a n t i t a t i v ea n a l y s i so ft h ei n f l u e n c eo fb g pc o n v e r g e n c et ot h en e t w o r k p e r f o r m a n c e t h ep h y s i c a li n t e r n e ti so n eo ft h em o s tc o m m o ne x a m p l e so fc o m p l e xn e t w o r k si n t h er e a l s o c i e t y i t sg r o w i n gs t r u c t u r e i st h er e s u l to fc o m p e t i t i v ea n dc o o p e r a t i v e p r o c e s s e sw i t h o u ta n yc e n t r a l i z e dc o n t r o li nd e t e r m i n i n gt h es e l f - o r g a n i z e de v o l u t i o no f t h e s y s t e m w ea n a l y z e t h er e l a t i o n s h i pb e t w e e nb g pc o n v e r g e n c ea n dt h e c h a r a c t e r i s t i c so ft h ei n t e r n e t t h ei n t e r n e ti sc l a s s i f i e di n t ot h r e eh i e r a r c h i e sb a s e do n t h ep o w e r - l a wa n dc o m m e r c i a lr e l a t i o n so fa u t o n o m o u ss y s t e m s t h er e l a t i o no ft h e n e t w o r kt o p o l o g ya n dt h eb g pc o n v e r g e n c ep e r f o r m a n c ei sp r e s e n t e df o ra l ls o r t so f c o n v e r g e n c ee v e n t si nd i f f e r e n tl a y e r s t h er e s u l ts h o w st h a tt h ep o w e r - l a wn a t u r eo f n e t w o r ki n f l u e n c e st h eb g pc o n v e r g e n c eg r e a t l y s ow ep r e s e n tan e wa p p r o a c ht o i m p r o v eb g pc o n v e r g e n c eb a s e do np o w e r - l a w , c a l l e d “b e s tu p ”，w h i c hb e h a v e s b e u e rt h a nn o r m a lc o n v e r g e n c em o d ei nt h ee x p e r i m e n t s t h er e s e a r c ho nt h ep r i c i n gp r o b l e mo ft h ei n t e r - d o m a i nm u l t i c a s t a p r a c t i c a lp r i c i n gm e c h a n i s mi st h ef o u n d a t i o nf o rt h ed e p l o y i n go fi pm u l t i c a s t i nt h ei n t e r - d o m a i ni n t e r n e t h o w e v e r ，t h ed i f f e r e n tk i n do fp r o f i ta n dt h eb e h a v i o ro f e a c ha sm a k et h i sp r o b l e mc o m p l e x 第i v 页 国防科学技术大学研究生院博士学位论文 t h ei pm u l t i c a s ts e r v i c em o d e la n di t sp r i c i n gm e c h a n i s ma r ed i s c u s s e di n t h i s d i s s e r t a t i o nb yc o n s i d e r i n gt h em o t i v a t i o n so fd i f f e r e n tp a r t n e r si nt h ep r o c e s s t l l r e e m o d e l sa r ep r o p o s e df o ra l la p p l i c a t i o n si nt h er e a le n v i r o n m e n t s t h e ya r ei c p u s e r m o d e l ，i c p i s pm o d e la n di c p i s p u s e rm o d e lr e s p e c t i v e l y i ne a c hm o d e l ，t h e a p p l i e ds c e n a r i o s ，r e s o l v i n gm e t h o da n dt h ec o m p l e x i t yo fa l g o r i t h ma r ei l l u s t r a t e d h e r e t h ei n t e r n e ti sc o n s i d e r e da sa ne c o s y s t e m s ow eg i v eag e n e r a ld i s c u s s i o no nt h e p r a c t i c a lp r i c i n gm e c h a n i s mb a s e do nt h eg a m et h e o r yo ft h ec o m p l e xs y s t e mf o r t h e s t a b i l i t yo ft h ee c o n o m i cd e v e l o p m e n ti nt h ei n t e r n e t i ns u r n r n a r y ，o u rw o r kp r e s e n t ss o l u t i o n st os e v e r a lk e yp r o b l e m so ft h e i n t e r d o m a i nr o u t i n gs y s t e m ，a n dh a sa c a d e m i cv a l u ea n dp r a c t i c a lv a l u ef o ra d v a n c i n g t h es e l f - o r g a n i z e ds y s t e mt h e o r ya n di t sp r a c t i c a b i l i t y k e yw o r d s s e l f - o r g a n i z e ds y s t e m ，c o m p l e xs y s t e m ，i n t e r - d o m a i nr o u t i n gs y s t e m ， d y n a m i ce v o l u t i o nm o d e l ，b g pc o n v e r g e n c e ，i n t e r - d o m a i nm u l t i c a s t ，s i m u l a t i o n 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图2 1i n t e r n e t 节点度分布曲线2 0 图2 2i s p 之间的连接图2 0 图2 32 0 0 4 1 1 - 2 0 0 5 3 3 0 间i n t e m e t 上的节点增长曲线和链路增长曲线2 1 图2 4t r a n s i t s t u b 模型结构2 2 图2 5 当今域问路由系统结构的抽象表示2 2 图3 1 域问路由系统简化三层结构一3 6 图3 2 不同调节参数伐和p 得到的5 0 0 个a s 节点的拓扑图一4 2 图3 3 节点度分布比较4 7 图3 4 节点间跳步数分布概率4 8 图3 5 节点聚集系数累计分布比较4 8 图3 6a s 的影响范围分布4 9 图3 7 节点b c 值与与节点度的关系。5 0 图3 8c m v h o t 模型中的商业关系统计5 0 图3 9c m v h o t 生成的2 0 ，0 0 0 个节点的域间路由系统拓扑图5 2 图3 1 0 多宿主对秩系数的影响5 3 图3 11 多宿主对跳步数概率分布的影响5 4 图3 1 2 多宿主对聚集系数概率分布的影响5 4 图3 1 3 商业关系对秩系数的影响5 5 图3 1 4 商业关系对跳步数概率分布的影响5 6 图3 1 5 商业关系对聚集系数的影响5 6 图4 1 更新报文处理过程6 3 图4 2 更新报文的c p u 处理过程及处理时间6 4 图4 3a sp a t h 的平均长度变化6 8 图4 4a s 数目增长曲线7 0 图4 5r 与h 的变化曲线与线性拟合的误差7 0 图4 6 有效直径随与日的变化曲线7 1 图5 1 域间路由系统结构图。7 4 图5 2 各层中a s 节点数目7 5 图5 3 模型中点与边所属的层次7 6 图5 4 模型中发生在各个层次的收敛事件7 8 图5 5 节点度与节点b c 值之间的关系7 9 图5 6 模拟拓扑图8 4 第v 页 国防科学技术大学研究生院博士学位论文 图5 7 节点度分布8 5 图5 8d o w n 事件在各种层次情况下的收敛参数值比较8 6 图5 9u p 事件在各种层次情况下的收敛参数值比较8 7 图5 10 “b e s tu p ”机制的伪代码实现8 8 图5 1 1 在u p 事件中两种方式下收敛时间比较9 0 图5 1 2 在d o w n 事件中两种方式下收敛时间比较9 0 图6 1 域间组播树结构9 7 图6 2 域内变换9 7 图6 3d e w 算法的“从下往上”过程9 9 图6 4d e w 算法的“从上往下”过程10 0 图6 5 一个d e w 算法的实例1 0 1 图6 6i s p 之间的组播数据流10 2 图6 7a v 机制中的信息流1 0 3 图6 8 代价表的组织结构1 0 3 图6 9a v 机制的从下向上过程1 0 4 图6 1 0i c p i s p u s e r 模型实例1 0 6 第v i 页 国防科学技术大学研究生院博士学位论文 表目录 表3 1 三类a s 的特征比较3 6 表3 2c m v h o t 模型的参数值4 6 表3 3a s 节点度比较4 7 表3 4 几组数据源中聚集系数c 值的比较4 9 表4 1 各种收敛模型分析得出的收敛时间。6 0 表4 2 模型符号定义。6 2 表5 1 各层中连接边的数目7 5 表5 2 各种情况下收敛参数最大最小值8 3 表5 3 发生收敛事件的1 0 种情况8 5 表6 1i c p u s e r 模型的符号定义9 9 第l v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 堡间整直丞缝皂堑堡鳖! 睦丞羞毽间錾盈究 学位论文作者签名：超金d 叁 日期：护7 年争月弓日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阒；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 堡圈整直丕统鱼堑丞挂煌区羞堡闷塑叠壅 学位论文作者签名：耋金韪 日期：力咿7 年年月；日 作者指导教师签名：# 进墼一 日期：岬年k 月3 日 国防科学技术大学研究生院博士学位论文 第一章绪论 基于b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 【l 】的域问路由系统作为i n t e m e t 的核心设 施，不但是传递网络可达信息的基本机制、a s ( a u t o n o m o u ss y s t e m ) 互连的纽带 和i s p ( i n t e m e ts e r v i c ep r o v i d e r ) 实现策略控制的主要手段，而且对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 规模的扩展和商业化进程 的加速，域问路由系统规模膨胀、结构密集化、互联关系复杂化和路由策略多样 性，表现出显著的开放复杂巨系统特征，i s p 策略交互行为表现出非常强的自组织 特性，并将在新一代互联网中得到更加充分的表现，成为域间路由系统演化的基 本规律。研究设计基于完善自组织机制的新型路由系统是解决路由系统诸多性能 和安全问题的有效途径，是推动新一代互联网健康发展的动力。 本文基于域间路由系统自组织特性，利用复杂系统理论和i s p 之间交互的自 组织规律，提出改善域问路由系统性能以及实现域间组播部署的新方法和新机制， 为构造安全、可信、可控、可管的新一代互联网，促进新一代网络的持续健康发 展做出贡献。 1 1 域问路由系统对网络发展的影响 i n t e m e t 的演变与路由系统的发展是相互依存、不可分割的。i n t e r a c t 诞生之初 就有对路由技术的讨论，那时网络结构比较简单。上世纪8 0 年代，路由技术逐渐 进入商业化的应用，大量网络互联的需求增加，促进了路由系统的发展。现在， 路由系统已成为i n t e m e t 的基石，支撑着i n t e r a c t 的飞速扩展。 路由系统是随着i n t e m e t 的发展而逐渐成长起来的。在a r p a n e t 建立初期只 有一个骨干网。后来，为了实现多个网络互连的需要，设置了各种路由器，运行 一种网关网关协议，实现不同网络信息在路由器之间的交换。两个网络之间的通 信至少会经过两个路由器，每个路由器都存储有另一个核心路由器的全部路由信 息。不过，随着互联网规模的增长，再让所有路由器保存整个互联网的全部路由 信息是不明智的，于是路由协议被分为域间路由协议和域内路由协议。域间路由 第1 页 国防科学技术大学研究生院博士学位论文 器作为核心路由器，保存全网的可达信息；域内路由协议只负责本自治系统内部 网络的路由处理，不必直接了解互联网上所有其他路由器的情况，可通过缺省路 由经过域间路由器到达其他网络。 域间路由协议早期采用的是e g p ( e x t e r i o rg a t e w a yp r o t o c 0 1 ) 【2 】协议，到1 9 8 9 年公布了b g p 协议的第一个版本p j 。目前采用的b g p 是1 9 9 5 年制订的第四个版 本( b g p 4 ) 【4 】，后来又做了很多修订，发布了二十多个相关的功能增强与完善规 范。基于i p v 6 的b g p 4 + 【5 】除了传播的路由信息的地址格式外，与b g p - 4 没有协 议机制的差别。b g p 路由协议互联的自治系统由1 9 9 7 年的2 , 0 0 0 个增加到目前的 2 2 9 ，0 0 0 个，传输的网络前缀数目由1 9 9 7 年4 , 0 0