（通信与信息系统专业论文）名空间路由研究和源管理路由算法的分析与建模.pdf

中文摘要 摘要：网络路由一直是网络的关键问题。今天的计算机网络非常庞大、高速， 传载着各种多媒体信息，因此，网络路由面临新的挑战。路由算法层出不穷，目 的都是为了寻找满足要求的路径来传递信息。而目前因特网使用的路由算法，主 要是基于1 9 5 9 年提出的d i j k s t r a 算法和1 9 6 2 年提出的基于b e l l m a n - f o r d 算法等理 论研究成果。这些经典路由算法都是假设在网络拓扑的基础上定义一个度量，在 这个度量的基础上计算每个节点到达其他节点的最短路由，并且为每个子网保持 一个路由表项。它们的特点是全局维护，精确路由指向，最短路径路由。随着网 络规模不断扩大，子网数量急剧增多，目前全局最优的传统路由算法将面临严重 挑战。网络发展趋势引发在理论上重新审视现有路由算法和开拓新路由方案的迫 切需求。 本文在研究了v r r ( v i r t u a l 融n gr o u t i n g ) 和r o f l ( r o u t i n go nf l a tl a b e l s ) 路由 算法的基础上，总结出的名空间路由思想：它是基于拓扑独立的路由法则；具有 非精确路由指向，每个节点只指向有限个其他可达节点，按照路由法则将信息转 发到记录中“最近 指向节点去；非全局路由维护，每个节点只需独立维护各自 指定节点的可达性。 本文研究了把v r r ( v a a u a lr i n gr o u t i n g ) 和r o f l ( r o u f i n go nf l a tl a b e l s ) 应用 到b g p 路由协议的可行性，并把这种方法称为源管理路由方案。有如下发现：节 点命名对路由性能有明显的影响，而在v r r ( v 酬i u n gr o u t i n g ) 和r o f l ( r o u t i n g o nf l a tl a b e l s ) 中命名是随机的；拓扑相关的命名策略并不能提高路由性能；核心 a s 在源管理路由算法中起到重要作用。 探讨了源管理路由方案在基于a s 商业关系的实际网络拓扑中的可行性，发 现：直接把源管理路由方案应用实际a s 商业关系的网络拓扑中，源管理路由方案 得到的路径并不是都符合b g p 路由策略；提出基于分层源管理路由方案建立和维 护多条虚拟邻居路径的方法以提供基于a s 商业关系的完备路由信息，确保完整路 径的有效性。 提出了源管理路由算法的理论模型，该路由算法思想虽然简单，却没有理论 模型来描述它的路由选择问题以及计算任意节点间的路径长度，尤其是从理论上 来评估源管理路由算法的性能。模型中通过利用虚拟环路径这一独特想法来描述 路径选择问题，根据源节点和目的节点名字在标识符数值上的距离，分析在虚拟 环上出现的所有可能路径的概率，计算在虚拟环上路径的平均跳数，最终估算出 实际物理路径的长度。分析影响路由性能的因素，网络中的节点数量，虚拟邻居 路径的长度，源节点目的节点名字在标识符数值上的距离以及网络拓扑都影响着 源管理路由算法路径长度的分布。通过全面深入的分析源管理路由算法，对其路 由效率及可扩展性有了完整的认识，为适应于未来核心网络路由打下坚实的理论 基础。 针对源管理路由方案中核心节点路由表可能会过于庞大的问题，研究了通过 命名来压缩路由表的可能性。提出了一种基于概率的启发性命名算法，通过节点 到达连续地址节点的下一跳尽可能相同( 并将这些地址是连续的节点用间隔来表 示) 达到压缩路由表的目的。仿真表明该算法能够很大程度压缩路由表。 关键词：名空间路由；o v e r l a y 网络路由；网络模型；b g p ；v r r ；命名策略；s t r e t c h 。 分类号：t p 3 9 3 a bs t r a c t a b s i l t a c i ! n e t w o r kr o u t i n gh a sb e e nt h ek e yi s s u ei nt h en e t w o r k ，t o d a y sc o m p u t e rn e t w o r k s a r ev e r yl a r g e ，h i g h s p e e d , m a s sl o a d e dw i t hav a r i e t yo fm u l t i m e d i ai n f o r m a t i o n , t h e r e f o r e ，t h en e t w o r kr o u t i n gi sf a c i n gan e wc h a l l e n g e t h eg o a lo fr o u t i n ga l g o r i t h m i st of i n dt h eo p t i m a lp a t ht ot r a n s m i ti n f o r m a t i o n ；i m p r o v es e r v i c eq u a l i t y a tp r e s e n t , t h ei n t e m e tr o u t i n ga l g o r i t h mi sm a i n l yb a s e do nt h ed i j k s t r aa l g o r i t h mp r o p o s e di n 19 5 9 a n db e l l m a n f o r da l g o r i t h mp r o p o s e di n19 6 2 t h e s er o u t i n ga l g o r i t h m sa s s u m e t h a tt h en e t w o r kt o p o l o g yi sb a s e do nt h ed e f i n i t i o no fam e t r i c ，t h es h o r t e s tr o u t e b e t w e e nt w on o d e si sc a l c u l a t e db a s e do nt h i sm e t r i c ，、) l ，i t l lm a i n t a i n i n gar o u t i n gt a b l e e n t r yf o re a c hs u b n e t w o r k t h e ya r ec h a r a c t e r i z e db yt h eg l o b a lm a i n t e n a n c e ，p r e c i s e r o u t i n g ，s h o r t e s tp a t hr o u t i n g a st h en e t w o r k sa r ee x p a n d i n ga n ds h a r pi n c r e a s i n gi nt h e n u m b e ro fs u b - n e t w o r kc a s e ，t h ec u r r e n tg l o b a lo p t i m a lr o u t i n ga l g o r i t h m sf a c es e r i o u s c h a l l e n g e s i n t e r n e td e v e l o p m e n tt r e n d s l e a dt or e e x a m i n et h e e x i s t i n gr o u t i n g a l g o r i t h m sa n dd e v e l o pn e wr o u t i n ga l g o r i t h m s t h i sp a p e rs u m m a r i z e st h ei d e ao fn a m er o u t i n gb a s e do nr e s e a r c ho nt h ev r r ( v i r t u a li u n gr o u t i n g ) a n dr o f l ( r o u t i n go nf l a tl a b e l s ) n a m er o u t i n gi sb a s e do n r o u t i n gr u l e sw h i c hi st o p o l o g yi n d e p e n d e n t i th a sn o n - p r e c i s i o nr o u t i n g ，e a c hn o d eh a s o n l yaf i n i t en u m b e ro fp o i n t st or e a c h t h eo t h e rn o d e s ，t h ei n f o r m a t i o ni sf o r w a r d e dt o t h en o d ew h or e c o r d st h e ”r e c e n t ”p o i m i n gt ot h en o d ea c c o r d i n gt ot h er o u t i n gr u l e s ； n o n g l o b a lr o u t em a i n t e n a n c e ，e a c hn o d eo n l yn e e d t om a i n t a i nt h er e a c h a b i l i t yo ft h e i r o w nd e s i g n a t e dn o d e s i nt h i sp a p e r , w ea p p l yv r g ( v i r t u a l lr i n gr o u t i n g ) a n dr o f l ( r o u t i n go nf l a t l a b e l s ) t os u p p o r tf o rb g pr o u t i n g ，a n dc a l lt h i sm e t h o da ss o u r c em a n a g e m e n tr o u t i n g s c h e m e t h ef o l l o w i n gw a sf o u n d ：t h en a m i n gs t r a t e g yi m p a c t st h er o u t i n gp e r f o r m a n c e f o rt h es o u r c em a n a g e m e n tr o u t i n gs c h e m e ，a l t h o u g hj u s tn a m i n gr a n d o m l yi nv r ra n d r o f l t h en a m i n gs t r a t e g yd e p e n d i n go nt o p o l o g yc a nn o ti m p r o v et h er o u t i n g p e r f o r m a n c e ；t h e c o r ea s e si nt h es o u r c em a n a g e m e n tr o u t i n gs c h e m ep l a ya n i m p o r t a n tr o l ei nr o u t i n g w ed i s c u s st h ef e a s i b i l i t yo fs o u r c em a n a g e m e n tr o u t i n gs c h e m eb a s e do nt h e a c t u a lt h en e t w o r kt o p o l o g yw i t i la sb u s i n e s sr e l a t i o n s h i p s t h ef o l l o w i n gw a sf o u n d ： f o rd i r e c t l ye m p l o y i n gs o u r c em a n a g e m e n tr o u t i n gs c h e m eo nt h ea c t u a lt h en e t w o r k v t o p o l o g y 谢t l la sb u s i n e s sr e l a t i o n s h i p s ，t h e r ea r es o m er o u t e st h a ta r en o ta l w a y sm e e t t h eb g pp a t hr o u t i n gs t r a t e g y ；s ow ep r o p o s et h eh i e r a r c h i c a lr e s o u r c em a n a g e m e n t r o u t i n gs c h e m et oe s t a b l i s ha n dm a i n t a i nm u l t i p l ev i r t u a ln e i g h b o rp a t h si no r d e rt o p r o v i d et h ec o m p l e t er o u t i n gi n f o r m a t i o nb a s e do nb u s i n e s sr e l a t i o n s h i p s ，t oe n s u r et h e v a l i d i t yo ft h ef u l lp a t h w ep r o p o s eat h e o r e t i c a lm o d e lo ft h es o u r c em a n a g e m e n tr o u t i n ga l g o r i t h mt o d e s c r i b et h er o u t i n gm e c h a n i s ma n dt h ei m p a c t so nt h er o u t i n gp e r f o r m a n c e t h e r o u t i n ga l g o r i t h mi ss i m p l e ，s t i l lt h e r ei sn ot h e o r e t i c a lm o d e l t od e s c r i b eh o wt oc h o o s e t h er o u t ea n dc a l c u l a t et h ep a t hl e n g t hb e t w e e na p a i ro fn o d e s ，e s p e c i a l l yi nt h e o r yt o d i s c u s st h ep e r f o r m a n c eo fs o u r c em a n a g e m e n tr o u t i n ga l g o r i t h m t h eh o pi nv i r t u a l r i n gi st h i su n i q u ei d e at od e s c r i b et h ep a t ho f t h i sr o u t i n ga l g o r i t h m u s i n gt h i sm o d e l ， h o wm a n yh o p si nv i r t u a lr i n gt or e a c had e s t i n a t i o nc a nb ec a l c u l a t e da c c o r d i n gt o n u m e r i c a ld i s t a n c eb e t w e e ni d e n t i f i e r so ft w on o d e s t h ep r o b a b i l i t yo fa l lp o s s i b l e p a t h si nt h ev i r t u a lr i n gi sc a l c u l a t e dt og e tt h ea v e r a g en u m b e ro fh o p si nt h er i n g ，a n d u l t i m a t e l yt oe s t i m a t et h ea c t u a lp h y s i c a lp a t hl e n g t h w ea n a l y s i z et h ef a c t o r st h a t a f f e c tt h er o u t i n gp e r f o r m a n c e ，t h en u m b e ro fn o d e si nt h en e t w o r k ，t h ev i r t u a ln e i g h b o r p a t hl e n g t h ，t h es o u r c en o d e ，d e s t i n a t i o nn o d en a m ea n dt h en e t w o r kt o p o l o g y , a l lo f t h e ma f f e c tt h es o u r c em a n a g e m e n tr o u t i n gp a t hl e n g t hd i s t r i b u t i o n t h r o u g ha c o m p r e h e n s i v ei n d e p t ha n a l y s i so fs o u r c em a n a g e m e n tr o u t i n gs c h e m e ，w ef u l l y u n d e r s t a n di t sr o u t i n ge f f i c i e n c ya n ds c a l a b i l i t y , i no r d e rt oa d a p tt ot h ef u t u r ec o r e n e t w o r ka n dl a yas o l i dt h e o r e t i c a lb a s i s i no r d e rt os o l v et h ep r o b l e mt h a tt h er o u t i n gt a b l e so ft h ec o r en o d e si ns o u r c e m a n a g e m e n tr o u t i n ga l g o r i t h ma r es ob i g ，w ep r o p o s eah e u r i s t i ca d d r e s sa s s i g n m e n t a l g o r i t h mb a s e do np r o b a b i l i t yt or e d u c et h er o u t i n gt a b l es i z e o u ra l g o r i t h mc a n g u a r a n t e et h eh i g hp r o b a b i l i t yt h a te a c hn o d eu s e st h es a l t l en e x th o pt ot h en o d e s a s s i g n e dw i t hc o n s e c u t i v ea d d r e s s e s ，a n dt h e nt h e s ec o n s e c u t i v ea d d r e s s e sc a nb e c o m p r e s s e d t o c o m p a c t t h e r o u t i n g t a b l e s s i m u l a t i o nr e s u l t ss h o wt h a tt h e p r o b a b i l i t y b a s e dh e u r i s t i ca l g o r i t h mc a nc o m p r e s sr o u t i n gt a b l eg r e a t l y k e y w o r d s ：n a m er o u t i n g ；o v e r l a yn e t w o r kr o u t i n g ；n e t w o r km o d e l ；b g p ；v r r ； n a m i n gs t r a t e g y ；s t r e t c h c l a s s n 0 ：t p 3 9 3 致谢 光阴荏苒，不知不觉之间已经度过了博士研究生的第五个年头。在本论文初 稿即成，我在键盘上敲出这些文字的时候，眼前不禁浮现出一张张熟悉的脸庞。 在我攻读博士学位的五年里，正是因为有你们的陪伴、关心和鼓励，帮我面对一 个又一个挑战，克复重重困难，到达胜利的彼岸，完成人生一次重要的飞跃。谨 以下面的文字，表达我对你们的谢意。 首先感谢我的导师陈常嘉教授。在我攻读博士学位期间，他的谆谆教诲无时 无刻不在指导着我学业上的进步；工作之余，他还经常旁征博引，交给我许多人 生的道理，指导我在学习工作当中，特别是走上工作岗位之后，如何与人相处， 如何在这个社会当中摸爬滚打，闯出自己的一片天地。而陈老师本人也以身作则， 他的治学态度认真严谨，考虑问题清晰缜密，观察事物敏锐准确，这些都给我留 下了非常深刻的印象，足以成为我一生前进道路上的典范。 感谢通信工程实验室的所有老师，其中特别要感谢胡师舜老师对我学习和生 活上的帮助和支持。 感谢赵永祥老师、郭宇春老师、宋光农老师、郑宏云老师、李磊老师和李纯 喜老师，与他们经常性的讨论和交流对我论文中很多思想的形成和完善都有重要 的启发意义。 感谢实验室的师兄、师姐、师弟、师妹们，特别是张敏，陈一帅、杨悦、危 婷、林福宏、郑毅、黄丹，邓光青，敖乃翔，对我论文中的研究工作给予了热情 帮助和鼓励，感谢你们在生活上对我的关心照顾，我们好像亲兄弟姐妹一样，虽 然一起度过的日子有长有短，但是那些快乐的时光我将永远记在心里。 最后，也是最重要的，要感谢我的家人，生我养我的父母，你们对我永远都 是无私的奉献，却从不索取任何东西。语言已经无法表达我的谢意，我只有在以 后的生活中，用实际行动来回报你们的养育之恩。 五年的时间漫长而又短暂，有些人在身边只是匆匆而过，却足以改变我的一 生。要感谢的人实在太多，篇幅有限，记忆力有限，难免会有疏漏，在此感谢所 有支持和帮助过我的人，谢谢你们! 缩略语 a s ( a u t o n o m o u ss y s t e m ) 自治系统。 b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 边界网关协议 c a i d a ( c o o p e r a t i v ea s s o c i a t i o nf o ri n t e m e td a t aa n a l y s i s ) 互联网数据 分析协作组织 c i d r ( c l a s s l e s si n t e r - d o m a i nr o u t i n g ) 无类别域问路由 d h t ( d i s t r i b u t e dh a s ht a b l e ) 分布式哈希表 e b g p ( e x t e r i o rb o r d e rg a t e w a yp r o t o c 0 1 ) 夕b 部边界网关协议 e g p ( e x t e r i o rg a t e w a yp r o t o c 0 1 ) 外部网关协议 e i g r p ( e n h a n c e di n t e r i o rg a t e w a yr o u t i n gp r o t o c 0 1 ) 增强的内部网关路由选 择协议 l p ( l o c a lp r e f e r e n c e ) 本地偏好 h l p ( h y b r i dl i n k s t a t ep a t h - v e c t o rr o u t i n gp r o t o c 0 1 ) 链路状态与路径矢量 混合的路由协议 i a b ( i n t e m e t a r c h i t e c t u r a lb o a r d ) i n t e r a c t 体系结构委员会 i b g p ( i n t e r i o rb o r d e rg a t e w a yp r o t o c 0 1 ) l 为部边界网关协议 i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) i n t e m e t 工程任务组 i g p ( i n t e r i o rg a t e w a yp r o t o c 0 1 ) 内部网关协议 i g r p ( i n t e r i o rg a t e w a yr o u t i n gp r o t o c 0 1 ) 内部网关路由协议 i p ( i n t e m e tp r o t o c 0 1 ) 网际层协议 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 服务提供者 m e d ( m u l t i e x i td i s c r i m i n a t o r ) 多出口区别 n g n ( n e x tg e n e r a t i o nn e t w o r k ) 下一代互联网 o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 开放式最短路径优先 r f c ( r e q u e s tf o rc o m m e n t s ) 请求意见文档 r i p ( r o u t ei n f o r m a t i o np r o t o c 0 1 ) 路由信息协议 r o f l ( r o u t i n g o nf l a tl a b e l s ) 扁平编号路由 r o n ( r e s i l i e n to v e r l a yn e t w o r k ) 弹性覆盖网络 s p f ( s h o r t e s tp a t hf i r s t ) 最短优先路径 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 0 1 ) 传输控制协议 v r r ( v i r n l a li u n gr o u t i n g ) 虚拟环路由 图表清单 图2 1c h o r d 中节点路由实例1 2 图2 2p a s t r y 中节点路由实例1 5 图2 3v r r 路由算法1 7 图2 4r o u t i n g0 1 1f l a tl a b e l s 路由方案。2 0 图4 1h l p 路由方案。2 9 图4 2 虚拟环中虚拟邻居关系- 3 0 图4 3 源管理路由方案简单实例。3l 图4 _ 4 源管理路由方案路由表3 1 图4 5 启发性命名算法l 一3 5 图4 6 启发性命名算法2 3 5 图4 7 源管理路由算法路径长度比较3 7 图4 8 源管理路由算法平均s t r e t c h 比较3 7 图4 9 虚拟邻居路径长度比较3 8 图4 1 0 源管理路由算法路由表大小比较3 8 图5 1 自治域之间的商业关系4 4 图5 2v a l l e y 路径与v a l l e yf r e e 路径4 6 图5 3 源管理路由方案中b g p 路由策略对虚拟邻居路径的影响4 9 图5 - 4 源管理路由方案中b g p 路由策略对路径长度的影响4 9 图5 5 源管理路由方案中b g p 路由策略对平均s t r e t c h 的影响5 0 图5 - 6 a sd e g r e e 与路由表大小的关系5 l 图5 7v a l l e yf r e e 与v a l l e y 路径举例分析5 2 图5 8 分层源管理路由方案5 3 图5 - 9 两个虚拟环的融合5 3 图6 1 虚拟环上1 跳的可能路径5 8 图6 2 虚拟环上2 跳的可能路径5 9 图6 3 虚拟环上3 跳的可能路径6 1 图6 4 无抄近路路径6 5 图6 5 同一网络不同的i i d - s i | 对应在虚拟环上的平均跳数7 4 图6 6 在虚拟环上的跳数分布情况7 4 图6 7 虚拟邻居路径长度对仿真和理论结果的影响7 6 图6 8 虚拟邻居路径长度对在虚拟环上跳数的影响7 6 图6 9 路由表大小分布情况对比7 7 图6 1 0 不同节点数量的网络中路由表大小分布情况7 7 图6 1 l 网络中节点数量对在虚拟环上跳数的影响7 8 图6 1 2 不同网络大小情况下在虚拟环上跳数的概率分布情况7 8 图6 1 3 随机网络与b a 网络节点的度分布8 1 图6 1 4 随机网络和b a 网络中在虚拟环跳数与l i d s | | 对应关系8 2 图6 1 5 随机网络和b a 网络虚拟环上跳数的分布情况8 2 图6 1 6 随机网络和b a 网络的实际路径长度与虚拟环路径长度对比8 3 图6 1 7 随机网络和b a 网络的实际路径长度与虚拟环路径长度比值对比8 3 图6 1 8 随机网络和b a 网络虚拟邻居路径长度的分布情况8 4 图6 1 9 随机网络和b a 网络路由表大小的分布情况8 4 图7 15 节点网络的间隔路由9 0 图7 2 基于概率的启发性地址分配算法一9 3 图7 3 到达地址连续的两个节点下一跳相同的累积概率分布9 4 图7 _ 4 路由表大小的累积分布情况9 4 表2 1p a s t r y 节点路由信息表：1 4 表4 1 核心a s 同平均路径长度及平均s t r e t c h 之间的关系4 0 表7 1 完整路由表8 9 表7 2 重新命名后的路由表9 1 表7 3 压缩后的路由表9 2 1 绪论 1 1 论文的研究背景及意义 随着网络技术的发展和计算机应用水平的提高，计算机网络广泛应用于科研、 管理、生产及商业等各个领域。在计算机网络的设计、建设过程中，路由是一个 非常重要但又非常复杂的因素。理想的路由选择策略，不仅能够大大降低传输时 延，从而提高网络的实时性和性价比，而且能有效地优化配置网络资源，提高现 有网络的资源利用率和维护效率。 下一代网络( n e x tg e n e r a t i o nn e t w o r k , n g ，特别是下一代互联网，是近年来 信息领域一个炙手可热的研究课题。对下一代网络基础功能提出挑战的主要需求 是以i p v 6 为代表的地址域扩大问题和用户的移动性问题。目前所采用的以子网为 最小颗粒度路由的路由方式几乎没有办法支持这两个基本需求，它所附加的各种 技术限制将大大的降低地址扩展所可能带来的好处，也将大大限制用户的移动性。 例如，因特网体系结构委员会( i n t e m e ta r c h i t e c t u r eb o a r d ，t a b ) 在2 0 0 4 年公布的 r f c 3 8 6 9 1 3 中指出，目前使用的基础路由算法的极限大致在2 0 0 k 3 0 0 k ，而这种 限制并非硬件限制。当前i p v 4 地址所导致的子网数量已经达到这个数量级，如果 上述估计是正确的，那就几乎不可能明显增加核心网中的子网数目。在采用口v 6 ， 势必会由于子网本身规模恶性膨胀而带来严重的后果。尽管现在已经开始有如何 构建百万主机以太网的研究【4 】。因此，如果没有理念上的突破，仅仅依靠当前网 络的基础认知，也只能通过采用扩大核心网络中子网数量的方法。但就目前的技 术而言，存储技术无法容纳子网指向所需要的极大规模表项，分组转发会遭遇明 显增加的转发查表时间，而路由宣告产生的规模和安全问题以及路由故障所引发 的收敛问题将会非常糟糕。就目前所掌握的网络基础认知，并不知道如何为将来 的用户需求提供最基础的服务，更谈不上如何提高服务质量。因此，这就需要找 寻一种技术上可以实现的无颗粒路由方法，并尽量避免全局性的维护。 网络发展趋势引发在理论上重新审视现有路由算法和开拓新路由方案的迫切 需求。而目前因特网使用的路由算法，主要是基于1 9 5 9 年提出的d i j k s t r a 算法 1 】 和1 9 6 2 年提出的基于b e l l m a n f o r d 算法的距离矢量路由【2 】等理论研究成果。这些 学术成果的协议实现，保证了上世纪末出现的大规模信息网络建设并取得了巨大 的成功。目前这些算法仍在基本良好的状态下，在大致1 5 0 k 2 0 0 k 路由前缀的规 模上，支撑着全球网络的运营。由于目前路由算法还能满足网络性能要求，又有 2 0 多年大规模成功实践的基础，所以有相当多的人认为，路由中只剩下如何设计 高速芯片给以实现的问题，留下的学术研究空间已经不大。我们目前确实遇到了 路由方面的非常基础性的挑战，而且正因为路由问题本身的技术基础性和学术基 础性，所以我们面临的挑战将是严肃和巨大的。没有严肃和深入的研究，它将可 能成为制约我们下面十年甚至是几十年在信息网络方面取得重要进展的严重障 碍。 本文在研究了v r r ( v i r t u a lr i n gr o u t i n g ) 和r o f l ( r o u t i n go nf l a tl a b e l s ) 路由 算法的基础上，总结出的名空间路由思想，它将传统路由中的拓扑优先地位下降 到从属地位，从而实现了路由复杂性和路由质量的多样性选择；能够通过有限甚 至是少量的指向实现无颗粒度的路由；能够通过选择不同的路由拓扑适配策略来 平衡维护的复杂性和路由的长度。名空间路由是基于拓扑独立的路由法则，在名 空间上定义测度，并根据名空间测度规定路由法则。它具有非精确路由指向，每 个节点只指向有限个其他可达节点，按照路由法则将信息转发到记录中“最近” 指向节点去；非全局路由维护，每个节点只需独立维护各自指定节点的可达性。 现行的核心网络路由机制可以看成是名空间路由的一个特例，这个特例中， 路由器所管理主机的目的地址是按目前的子网连续分配的，采用了路由拓扑适配 机制是目前的b g p 对子网地址的通报和选路方式。路由器的转发准则是转发到记 录地址中最接近但不超过的那个指向去。这套方案下的名空间路由，无论在维护 的复杂性，转发的复杂性和路由性能方面均与目前的b g p 路由相同，但作为研究 的视角却是完全不同的，在名空间路由的视角下可以采用非b g p 的路由维护方式， 适当的减少路由器记录的表项数目，可以允许在路由器失去某些子网指向的情况 下向“最近”的子网转发等。而这些在传统的基于d i j k s t r a 和b e l l m a n f o r d 最短路 由的拓扑优先框架下是无法容忍的。所以，必须对目前所采用的路由算法和路由 协议进行一次严肃的审视，并应该努力挖掘能够支持更大规模网络的相应算法和 技术。 因此，本文研究了把v r r ( v i r t u a lm n gr o u t i n g ) 和r o f l ( r o u t i n go i lf l a tl a b e l s ) 应用到b g p 路由协议的可行性( 称这种方法为源管理路由方案) ，源管理路由方 案在b g p 主路由失效时为其找到另一条路径，可以绕过失效节点或链路到达目的 地。它的路由思想是所有a s 根据名字在数值上构成一个虚拟的环形，在虚拟环上 名字最接近的a s 称之为虚拟邻居，它们之间维护一条实际物理路径，这条路径经 过的a s 也要记录这条路径信息，这样每个a s 根据自己的名字只负责少量局部路 由信息，而不像b g p 需要维护全局路由信息。在路由时，只需向数值上距离自己 名字最近的a s 转发消息，而不需要找到路由表中精确指向目的地址的表项，并且 只依靠a s 名字进行路由。源管理路由算法的优点是显而易见的，无需维护全局拓 2 扑使得网络更易扩展，也不需要精确的路由指向，只依靠名字路由。 为了评估源管理路由算法为b g p 提供辅助路由的性能，我们从命名策略出发， 研究a s 虚拟邻居的选择对路由性能的影响，也就是对a s 的命名，它关系到什么 样的a s 可以成为虚拟邻居以及需要维护什么样的虚拟邻居路径，最终决定源管理 路由算法中所维护的路径信息以至影响到路由性能。通过基于真实网络拓扑上的 仿真结果分析，与拓扑无关的随机命名或直接利用a sn u m b e r 命名都可以得到很 好的路由性能。同时我们发现核心a s 在源管理路由算法中起到重要作用，越多的 虚拟邻居路径经过核心a s ，可以极大地缩短路径长度及平均s t r e t c h 。 由于b g p 是基于策略的路由，路由时要考虑a s 间的商业关系，v r r 路由算 法中并没有考虑到节点的商业关系。通过分析我们发现直接把源管理路由方案应 用实际a s 商业关系的网络拓扑中，源管理路由方案得到的路径并不是都符合b g p 路由策略，所以本文提出基于分层源管理路由方案建立和维护多条虚拟邻居路径 的方法以提供基于a s 商业关系的完备路由信息，确保完整路径的有效性。 本文建立了源管理路由算法的理论模型，用于计算到达目的节点的所经过的 跳数。利用在虚拟环上的路径这一独特想法来描述该路由算法的路径选择问题， 根据源节点和目的节点名字在虚拟环上的距离计算所有可能路径的概率，计算节 点间在虚拟环上跳数的平均值，最后估算出实际路径的长度。分析影响路由性能 的因素，网络中的节点数量，虚拟邻居路径的长度，源节点目的节点名字在标识 符数值上的距离以及网络拓扑都影响着源管理路由算法路径长度的分布。通过全 面深入的分析源管理路由算法，对其路由效率及可扩展性有了完整的认识，为适 应于未来核心网络路由打下坚实的理论基础。 针对源管理路由方案中核心节点路由表可能会过于庞大的问题，研究了通过 命名来压缩路由表的可能性。提出了一种基于概率的启发性命名算法，通过节点 到达连续地址节点的下一跳尽可能相同( 并将这些地址是连续的节点用间隔来表 示) 达到压缩路由表的目的。仿真表明该算法能够很大程度压缩路由表。 1 2 网络路由的研究现状 目前因特网使用的路由算法，主要是基于1 9 5 9 年提出的d i j k s t r a 算法 1 】和 1 9 6 2 年提出的基于b e l l m a n f o r d 算法的距离矢量路由 2 】等理论研究成果。这些学 术成果的协议实现，保证了上世纪末出现的大规模信息网络建设并取得了巨大的 成功。目前这些算法仍在基本良好的状态下，在大致1 5 0 k 一2 0 0 k 路由前缀的规模 上，支撑着全球网络的运营。这些传统的路由算法都是基于全局维护，精确路由 指向，最短路径路由的。随着网络规模不断扩大，予网数量急剧增多的情况下， 3 目前全局最优的传统路由算法将面临严重挑战。 近些年来，陆续提出了一些典型的o v e r l a y 网络路由算法。这些路由算法采用 了确定性拓扑结构，d h t ( d i s t r i b u t e dh a s ht a b l e ) 类结构能够自适应节点的动态加 入和退出，有着良好的可扩展性、鲁棒性、节点标识分配的均匀性和自组织能力。 目前比较成熟的o v e r l a y 网络路由算法有c h o r d 4 ，t a p e s t r y 错误! 未找到引用源。， p a s t r y 6 ，c a n l ) 8 等。它们的特点是不需要全局的拓扑维护，也不需要精确的 路由指向；o v e r l a y 网络拓扑与实际物理拓扑是完全无关的，只根据节点的名字路 由，导致节点之间实际