（计算机应用技术专业论文）ip网分级寻址的研究.pdf

i p 网分级寻址的研究 摘要 i n t e r n e t 已走过了三十余年的历史，随着i n t e r n e t 越来越广泛的应用，作 为i n t e r n e t 基础的t c p i p 协议族，也面临着各种各样的问题。其中一个突出 问题是i p v 4 地址空间耗尽问题。解决i p v 4 地址空间耗尽问题的方法主要有 两种：设计全新的i p 协议，在i p v 4 的基础上打补丁。 为解决i p v 4 地址空间耗尽，路由表爆炸，网络管理，新的应用对i p 网 提出新的服务要求等问题，1 9 9 5 年i e t f 发布了下一代i p 协议规范i p v 6 ， 属于第一类方法。为同样目的，1 9 9 6 年发布的私有i p 地址，1 9 9 3 年发布的 临对分配i p 地址的d h c p ，1 9 9 3 年发布的更有效率地使用i p 地址的c i d r 规范，1 9 9 4 年发布的复用i p 地址的网络地址转换( n a t ) 等新的i p 地址使 用方式属于第二类方法。 由于与i p v 4 的互操作性，i p v 6 还没有像过去预期的那样得到普遍使用， 而前面提到的基于i p v 4 打补丁的方法也难以彻底解决问题，并且n a t 给某 些端到端的应用造成困难。 首先，针对i p v 4 地址空间耗尽和路由表爆炸问题，本文提出了一种i p 网分级寻址模型。该模型的地址空间可以达到与i p v 6 地址空间同样大。该模 型将i p 地址空间划分成树形结构，不同层的结点赋予不同类的i p 地址。这 种层次的区分，使数据包的转发过程不必修改包头的地址信息。结点只需维 护本簇内结点的路由信息，这使路由表的长度大大缩短，有利于解决路由表 爆炸问题。这种寻址方式基本上解决了i p v 4 地址空间耗尽和路由表爆炸两个 问题。本文证明了分级寻址模型的层次路由协议的正确性，分析了其复杂性， 说明了分级寻址模型与i p v 4 的互操作性，用仿真实验评价了分级寻址模型的 性能。在文献中，这是i p 地址扩展模型第一次与层次路由方法相结合。 其次，本文分析了分级寻址性能与分级寻址模型中分簇结构之间的关系， 证明最优分簇结构中，各簇大小相等，i p e a 的路由表长度等于本地簇的大小， 与分簇结构无关。按照各簇间负载平衡的标准，确定了最优分簇结构，和相 应的最优分簇结构高度，证明了最优分簇结构是平衡树。同层簇的流量密度 相等。最后给出一个路由表长度伸展指数与路由路径长度伸展指数关系的关 哈尔滨工j 鼙大学博士学位论文 m l l l l l l 联式，很好地解释了路由表长度伸展指数与路由路径长度伸展指数逆相关的 现象。这一现象从1 9 7 7 年k l e i n r o c k 等人公开发表以来，尚没有解析式的解 释。仿真实验结果表明计算值与实验值拟合很好，证明了本章的分析结果。 第三，本文证明了分级寻址模型的最优分簇结构的簇大小是该网络的基 础图的团数。将最优分簇结构的簇大小与图论中的t r e ed e c o m p o s i t i o n 理论相 关联，应用t r e e w i d t h 近似算法确定输入图的t r e e w i d t h 下界，并以之作为最 优分簇结构的簇大小。提出了一个树分割的初始分割生成算法。实验证明本 文提出的算法性能优于基于顺序和随机初始分割的k e m i g h a l l l i n 算法，与多 层k e m i g h a n l i n 算法性能相当，但分割结果更符合树形结构。 最后，本文利用p e t r in e t s 理论对分级寻址模型中的路由算法加以分析。 建立了分级转发算法的有色p e t r in e t 模型，证明了分级转发算法的有色p e t r i n e t 模型的活性，安全性，循环性，分析了模型的不变量。这些结果证明了分 级转发算法的正确性。其次，建立了分级转发算法和非分级转发算法的时间 和随机p e t r in e t 模型，通过对时间和随机p e t r in e t 模型仿真，得到了分级转 发算法和非分级转发算法的包处理性能数据。性能分析表明分级转发算法优 于非分级转发算法。 关键词：i p 地址空间；层次寻址：层次路由；分簇；图分割；p e t r in e t s i i a b s t r a c t t h ei n t e m e th a ss e e ni t s3 0y e a r s a n da sw i d e ra n dw i d e rt h ei n t e r n e th a s b e e nd e p l o y e d ，t h ef o u n d a t i o no ft h ei n t e r n e t ，t c p i pp r o t o c o ls u i t eh a sb e e n c o n f r o n t i n gw i t hv a r i o u sp r o b l e m s ap r o m i n e n t o n ea m o n gt h e s ep r o b l e m si st h e d e p l e t i o no fi p v 4a d d r e s s t h em e t h o d st oa d d r e s st h i sp r o b l e mf a l li n t ot w o c a t e g o r i e s ：d e s i g nb r a n d - n e wi pp r o t o c o l ，o rp a t c h i n go ni p v 4 t oa d d r e s st h e p r o b l e m s o fi p v 4a d d r e s sd e p l e t i o n ，i p v 4r o u t i n gt a b l e e x p l o s i o n ，n e t w o r km a n a g e m e n t ，a n dn e wd e m a n d sf r o mn e wa p p l i c a t i o n s ，i e t f i n1 9 9 6r e l e a s e dt h en e x tg e n e r a t i o ni pp r o t o c o l i p v 6 f o rt h es i m i l a re n d s ， s p e c i f i c a t i o nf o rp r i v a t ei pa d d r e s sr e l e a s e di n19 9 6 ，t e m p o r a l l ya l l o c a t i n gi p a d d r e s sp r o t o c o l d h c pr e l e a s e di n1 9 9 3 ，s p e c i f i c a t i o nf o rm o r ee f f i c i e n t l yu s e o fi pa d d r e s s c i d rr e l e a s e di n1 9 9 3 ，a n ds p e c i f i c a t i o nf o rm u l t i p l e x i n gi p a d d r e s s n a t ( n e t w o r ka d d r e s st r a n s l a t i o n ) r e l e a s e di n1 9 9 4f a l li n t ot h es e c o n d c a t e g o r y f i r s t ，o na d d r e s s i n gt h ep r o b l e m so fi p v 4a d d r e s sd e p l e t i o na n di p v 4r o u t i n g t a b l ee x p l o s i o n ，w ep r o p o s eam o d e lo fh i e r a r c h i c a la d d r e s s i n gi ni pn e t w o r k s ， i p e a ，t i l i sa d d r e s s i n gm o d e le x t e n d st h ea d d r e s sp l a c et oa sb i ga si p v 6 s i nt h i s m o d e l ，a d d r e s ss p a c ei so r g a n i z e di n t oat r e e ，e a c hl a y e ri nt h et r e ei si d e n t i f i e db y d i f f e r e n tc l a s sa d d r e s s e s ，w h i c hs a v e s ，i nt h ep r o c e s so fp a c k e t sf o r w a r d i n g ，t h e i n t e r m e d i a t er o u t e r sf r o ms w a p p i n gt h ea d d r e s s e si nt h ep a c k e th e a d t h el e n g t h o fr o u t i n gt a b l em a i n t a i n e di ne a c hn o d ei sr e d u c e dt ot h es i z eo ft h el o c a lc l u s t e r , w h i c hh e l p sa d d r e s s i n gt h ep r o b l e mo fi p v 4r o u t i n gt a b l ee x p l o s i o n w ep r o v et h e c o r r e c t n e s sa n da n a l y s et h ec o m p l e x i t yo ft h i s a d d r e s s i n gm o d e l 1 1 1 e c o o p e r a b i t i t yb e t w e e ni p e aa n d i p v 4i si l l u s t r a t e d ，a n dt h es i m u l a t i o nr e s u l t so n p e r f o r m a n c eo fi p e aa r ep r o v i d e d t ot h eb e s to fo u rk n o w l e d g e ，i ti st h ef i r s t t i m et h a ti pa d d r e s se x t e n d i n gm o d e li si n c o p e r a t e dw i t hh i e r a r c h i c a lr o u t i n g m o d e l s e c o n d ，w ea n a l y s et h ep e r f o r m a n c eo fh i e r a r c h i c a la d d r e s s i n gi n i p i i i 哈尔滨二【程大学博士学位论文 n e t w o r k sw i t hr e g a r dt ot h es t r u c t u r eo fn e t w o r kc l u s t e r i n g t oo p t i m i z et h el o a d b a l a n c ea n dm i n i m i z et h es t r e t c hf a c t o ro fr o u t i n gp a t hl e n g t h ，t h eo p t i m a l c l u s t e r i n gs t r u c t u r ei sd e t e r m i n e da sab a l a n c e dt r e e c l u s t e r si nt h es a m el e v e l h a v ei d e n t i c a lt r a f f i cd e n s i t y w eg i v ea ne q u a t i o nt oc o r r e l a t et h er o u t i n gt a b l e l e n g t hs t r e t c hf a c t o ra n dr o u t i n gp a t hl e n g t hs t r e t c hf a c t o r , w h i c he x p l a i n st h e n e g a t i v ec o r r e l a t i o nb e t w e e nt h er o u t i n gt a b l el e n g t hs t r e t c hf a c t o ra n dr o u t i n g p a t hl e n g t hs t r e t c hf a c t o r t h i sp h e n o m e n o nh a sn oo t h e ra n a l y t i c a le x p l a n a t i o n s i n c ek l e i n r o c ka n dk a r m o np u b l i s h e di ti n1 9 7 7 t h i r d w ep r o v et h a t t h eo p t i m a lc l u s t e rs i z ee q u a l st h ec l i q u en u m b e ro ft h e g r a p h w er e l a t e t h eo p t i m a lc l u s t e rs i z et oab r a n c ho fg r a p ht h e o r y , t r e e d e c o m p o s i t i o n ，a n dp r o v et h a tt h eo p t i m a lc l u s t e rs i z eo fac l u s t e r i n gi n h i e r a r c h i c a la d d r e s s i n ge q u a l st h et r e e - w i d t ho ft h en e t w o r k w ep r o p o s ea n a l g o r i t h mf o ri n i t i a lp a r t i t i o no f t h ei n p u tg r a p h t h ep e r f o r m a n c eo f o u ra l g o r i t h m i sb e t t e rt h a nt h a to fk e m i g h a n - l i na l g o r i t h mb a s e do ns e q u e n t i a li n i t i a lp a r t i t i o n o rr a n d o mi n i t i a lp a r t i t i o n ，a n di ss i m i l a rt ot h a to fm u l t i l e v e lk e m i g h a n l i n a l g o r i t h m ，b u tw i t har e s u l t i n gp a r t i t i o nm o r ec o n f o r m i n gt oat r e es t r u c t u r e f o u r t h ，w ea n a l y z et h eh i e r a r c h i c a lf o r w a r d i n ga l g o r i t h mi nc o l o u r e dp e t r i n e t s s p e c i f i c a t i o n w ep r o v e t h et i v e n e s s ( c o n v e r g e n c e ，c o m p l e t e n e s s ) a n d s a f e n e s s ( c l o s e n e s s ) a n dr e c c u r c n c e ( c y c l i c n e s s ) o ft h eh i e r a r c h i c a lf o r w a r d i n g a l g o r i t h m w ee v a l u a t et h ep e r f o r m a n c eo fh i e r a r c h i c a lf o r w a r d i n ga l g o r i t h mi n t i m e da n ds t o c h a s t i cp e t r in e t ss p e c i f i c a t i o n t h er e s u l t ss h o wt h a tt h eh i e r a r c h i c a l f o r w a r d i n ga l g o r i f l u np e r f o r m sm u c hb e t t e rt h a nn o n - h i e r a r c h i c a lf o r w a r d i n g a l g o r i t h m k e yw o r d s ：i pa d d r e s ss p a c e ，h i e r a r c h i c a la d d r e s s i n g ，h i e r a r c h i c a lr o u t i n g ， c l u s t e r i n g ，g r a p hp a r t i t i o n i n g ，p e t r in e t s i v 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指 导下，由作者本人独立完成的。有关观点、方法、数据 和文献的引用己在文中指出，并与参考文献相对应。除 文中已注明引用的内容外，本论文不包含任何其他个人 或集体已经公开发表的作品成果。对本文的研究做出重 要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者( 签- 7 - - ) ：陆堡肇 日期：砌f 年易月，2 日 第1 章绪论 第1 章绪论 1 1 课题的目的与意义 i n t e r n e t 已走过了三十余年的历史，随着i n t e m e t 越来越广泛的应用，作 为i n t e r n e t 基础的t c p i p 协议族” 2 1 1 3 1 ，也面临着各种各样的问题。其中一个 突出问题是i p v 4 地址空间耗尽问题。6 0 年代末，i m e m e t 在美国诞生的时候， 只是作为美国军方的一个研究项目，并未考虑民用或日后将有大量的设备接 入网络。在8 0 年代末，人们估计将来只会有十万个网络接入i n t e m e t 4 1 。i p v 4 i 1 1 定义的i p 地址长度为3 2 位，根据所支持的网络数和主机数的不同，又将地 址分为a ，b ，c 三类。由于对互联网发展的速度估计不足，在互联网的初期， 人们认为地址空间非常充裕，因此往往一个公司或大学就能获得一个a 类或 b 类地址。但是随着互联网的发展，移动上网和信息家电等新应用的出现， 对i p 地址的需求也呈指数级的增长。虽然人们认识到i p v 4 地址资源有可能 不足之后，采取了c l d r f 5 1 1 6 1 1 7 1 ，v l s m ( v a r i a b l e 1 e n g t us u b n e t m a s k s ) 8 1 ，私 用i p 地址 9 1 ，以及网络地址转换( n a t ) 0 0 1 等补救措施，但终究无法根本解 决口v 4 地址匮乏的问题。 根据早期的预测【i ”，网络地址分配数每1 2 个月增加一倍，b 类地址将于 1 9 9 4 年全部分配完。 2 0 0 2 年8 月中国电信的沈军在一篇文章中报告【1 2 i ，根据a p n i c ( a s i a p a c i f i cn e t w o r ki n f o r m a t i o nc e n t r e ) 的统计，亚太地区最近六个月的地址消耗 率为3 4 - 3 个b 类地址月，且这个数字呈逐月上升的趋势。目前全球可用地 址已经不足半数，据专家估计，按现在的消耗速度，预计2 0 0 5 年i p v 4 地址 将全部耗尽。 h u s t o n 在2 0 0 5 年的一个报告中，给出了已分配的，8 地址块( 后2 4 位 可以自由使用的地址块) 数目和全部分配完的日期曲线。8 地址块的分配从 1 9 8 2 年的个累计增加到2 0 0 5 年末的近1 6 0 个，其中从8 8 年到9 5 年间这 八年间累计分配数增长最快，9 7 年因为i n t e m e t 引入c i d r ，私用i p 地址等 技术，分配曲线才稍微变得平缓。报告预测i a n a ( i n t e m e t a s s i g n e d n u m b e r s 哈尔滨工程大学博士学位论文 a u t h o r i t y ) 将在2 0 1 6 年分配完所有的8 地址块。 h a i n 在2 0 0 5 年的一个更悲观的估计【1 4 1 是，i a n a 将在2 0 0 8 年分配完所 有的8 地址块。 从上面几个对i p v 4 地址空间的分配情况的分析与预测，可以看到，由于 9 0 年代中期c i d r ，n a t 等技术的引入，将i p v 4 地址分配曲线放缓了1 0 年。 过去曾经有多次预测i p 地址将在上世纪末或本世纪初分配穷尽，但都没有成 为事实。这是因为，1 ) i n t e r n e t 不断采纳吸收新的技术，2 ) i n t e m e t 本身非常 具有弹性。 但是，无论是悲观或是乐观的预测，i p v 4 地址空间的分配穷尽都是在不 远的将来我们必须面对的一个事实。i p v 4 地址空间的不足已经成为引入新的 i p 协议的最直接原因。 另外，i n t e m e t 还面临着如下主要问题。 路由表膨胀由于i p v 4 的地址分级结构不完善，以及由于地址紧缺而 导致的地址分配机构分配的地址比较分散，使得各级路由器的路由表难以很 好地聚合，路由表的路由条数在不断的增长。现在全球路由表有近2 3 万条【， 比三年前几乎翻了一倍。庞大的路由表使得路由器在寻路时的负载剧增和工 作效率大大降低。从i n t e m e t 主干路由器b g p 转发表( f i b ) 长度变化历史 趋判”】可以看到，转发表长度从1 9 8 9 年的不足1 0 0 0 条，几乎线性地增长到 9 8 年的5 万条，然后急剧地增长到2 0 0 5 年末的2 5 万条。 网络管理变得越来越复杂随着互联网的不断扩张，越来越多的主机 接入互联网，而i p v 4 难以实现结点自动发现和地址自动配置等功能，给网络 管理带来了巨大的压力。 新的应用的出现对i p 网络提出了新的要求由于视频服务，金融服务 等新的应用的出现，客户对互联网的服务质量和安全性等有了更高的要求， 而t p v 4 在7 0 年代末设计的时候不可能预见到所有这些因素。同时i p v 4 对移 动设备访问互联网也没有提供很好的支持。 为了解决这些问题，早在9 0 年代初期，互联网工程任务组( i n t e m e t e n g i n e e r i n gt a s kf o r c e ，i e t f ) 就开始着手下一代互联网协议( i p t h en e x t g e n e r a t i o n 。i p n g ) 的制定工作。i e t f 在r f c l 5 5 0 里进行了征求新的i p 协议 的呼吁，并且公布了新的协议需要实现的主要目标： 2 第1 苹绪论 。支持几乎无限大的地址空间 。减小路由表的大小 。简化协议，使路由器能更快地处理数据包 。提供更好的安全性，实现i p 级的安全 。支持多种服务类型，尤其是实时业务 。支持多目传送，即支持组播 。允许主机不更改地址实现异地漫游 。支持未来协议的演变 。允许新旧协议共存一段时间 。支持未来协议的演变以适应底层网络环境或上层应用环境的变化 。支持自动地址配置 为解决上述问题，i e t f 在1 9 9 5 年发布了i p v 6 1 6 】。由于i p v 6 与i p v 4 的 互操作在多数老的网络设备上还难以实现，i p v 6 尚未获得原来预期的广泛应 用f 1 7 】。 i n t e m e t 的体系结构从1 9 6 9 年i n t e r n e t 的雏形诞生以来，到1 9 8 2 年采用 t c p i p 协议族，直到今天，始终是不断变化，演进的。a c ms i g c o m i v l 等 关于网络研究的会议上每年都有非i p v 6 体系结构的网络方面的文章发表。尽 管已经发布了i p v 6 协议，对i n t e m e t 体系结构改进的其它模型仍然不断被提 出【1 8 】【1 9 1 1 2 0 。 y m l g 在a c ms i g c o m m 0 3 的文章 2 l 】提出一种新的i n t e m e t 路由架构 ( n i r a ) 。n i r a 提供给终端用户选择数据包需要穿越的i s p 网络的能力。 文章探索了，用户如何发现路由，路由的动态状况是否满足他的要求，如何 有效地表示路由等问题。n i r a 使用一种层次的，以提供者为根的寻址方案， 这样，域层次上的路由可以有效地用一对地址表示。在n i r a 中，每个用户 维护提供通行服务的提供者的拓扑信息。源按需检索宿的拓扑信息并与自己 的拓扑信息组合来发现端到端的路由。这个路由发现过程保证每个用户不必 知道n t e m e t 的整个拓扑。 c l a r k 等人在a c ms i g c o m m 0 3 的文掣2 2 1 介绍了一种新的网络架构概 念， f a r a ( f o r w a r d i n gd i r e c t i v e ，a s s o c i a t i o n ，a n dr e n d e z v o u sa r c h i t e c t u r e ) ， 定义了一个非常具有一般性和灵活性的抽象模型，该模型将终端系统的名字 3 哈尔滨工程大学博士学位论文 与网络地址解耦( d e c o u p l i n g ) 。该文探讨了f a r a 的意义，以及能够从f a r a 派生的架构实例的范围。作为例子，文章概述了个派生架构，m f a r a ， 该架构支持一般的移动性和多域( m u l t i p l er e a l m s ) 网络寻址。 c r o w c r o f t 等人在a c ms i g c o m m 0 3 的文章1 2 3 】和p e t e r s o n 等人在2 0 0 5 年的文章【2 4 】说明了未来的i n t e r n e t 应该采用多样化( p l u r a l i s m ) 的协议体系。 现在的i n t e m e t 架构对于未来的情况是不足的已经成为广泛共识，如，地址 空间短缺，移动性和非通用的连接等情况。并且情况会随着无线，a d h o c ， 传感器网络的普及而恶化。c r o w c r o f t 等人提出一种互连网络架构，p l u t a r c h 。 p l u t a r c h 包容现有的i n t e m e t 架构，但让网络异质性( h e t e r o g e n e i t y ) 显式化。 s t o i c a 等人在a c ms i g c o m m 0 2 的文章【2 5 】提出一种基于o v e r l a y 的 i n t e m e t 间接基础架构( i n t e m e ti n d i r e c t i o ni n f r a s t r u c t u r e ) 。在这种架构中，不 是将包直接发送到宿，每个包与一个标识符关联，用这个标识符来传递包。 这种间接发送将发送与接受过程解耦，可以有效地支持广泛的通信服务。 r a m a s u b r a m a n i a n 等人在a c ms i g c o m m 0 4 的文章【2 6 1 指出，因为现有 d n s ( d o m a i n n a m es y s t e m ) 的结构缺陷，名字解析较慢并且易受拒绝服务 攻击，并且不支持快速更新。提出一种新的名字服务，合作式d n s ( c o d n s ) ， 通过主动缓存支持高性能查询，通过自动负载平衡防止拒绝服务攻击，以及 快速更新。 s c h m i d 等人在2 0 0 5 年的文章指出，不断增强的网络自治性是未来互连 网的一个关键要求【2 ”。文章提出一个新的，用于在自治的，异质的网络域间 互操作的架构。该架构基于全局标识空间，不需要寻址或共享的互连网协议。 该架构将动态网络组合的概念与最近的，如将地址与名字解耦等架构概念结 合起来。 r a t n a s a m y 等人在a c ms i g c o m m 0 5 的文章 2 8 1 指出，i n t e m e t 架构需要 改变是一个广泛的共识，指出什么因素使i n t e m e t 可以演化，以及通过微小 的修改就可使现在的i n t e m e t 成为可以演化的。 上述工作说明，即使是在i p v 6 发布十余年后的今天，非i p v 6 体系结构 的i p 网协议研究仍然是活跃的，有价值的。 i p 地址空间扩展模型按其地址长度是否可变分为两类，i p v 6 与i p v 4 都 属于固定长度地址模型。 4 第1 苹绪论 本文主要针对扩展i p v 4 地址空间，缩减路由表长度开展工作。采用可变 长度地址模型将层次路由模型推广到层次寻址模型，来扩展i p v 4 地址空间， 缩减路由表长度，研究层次寻址模型的性质与性能，及与层次寻址优化结构 相关的问题。 尝试解决上述i p v 4 面临的四大类问题中的i p 地址空间短缺，路由表长 度爆炸问题是本文工作的动机，也是本文工作的目的与意义。 1 2 相关方法与技术研究现状 本文工作内容涉及的主要相关领域是：1 ) i p 地址空间扩展模型，2 ) 层次 路由模型，3 ) 通信协议的形式描述与验证。 i p 地址扩展模型是本文工作的直接研究对象，本文主要涉及可变长度地 址扩展模型。层次路由方法是缩减路由表长度的最主要方法。随着更多复杂 协议的出现，使用自然语言已经很难准确地描述协议内容，更无法分析和验 证协议的正确性等最基本的性质，这就导致人们在协议工程领域引入形式方 法建立在数学基础上的系统描述与分析方法。协议的复杂性是协议工程 引入形式方法的直接原因。 下面我们将回顾在这三个领域中已有的主要工作和方法。 1 2 1l p 地址扩展模型 解决i p v 4 地址空间耗尽问题的方法主要有两种：设计全新的i p 协议【2 ”， 在i p v 4 的基础上打补丁1 5 】【6 1 1 7 1 1 9 1 0 】【3 0 1 。 为解决i p v 4 地址空间耗尽，路由表爆炸，网络管理，新的应用对i p 网 提出新的服务要求等问题，1 9 9 5 年i e t f 发布了下一代i p 协议规范 i p v 6 1 6 1 。这属于第一种方法。为同样目的，1 9 9 6 年发布的私有i p 地址规范1 9 ， 1 9 9 3 年发布的临时分配i p 地址d h c p 协议【3 州，1 9 9 3 年发布的更有效率地使 用i p 地址的c i d r 协议【5 1 1 6 1 ”，1 9 9 4 年发布的复用i p 地址的网络地址转换 ( n a t ) 协议【1 0 等新的i p 地址使用方式属于第二类方法。 由于与i p v 4 的互操作性，i p v 6 还没有像过去预期的那样得到普遍使用 1 7 ，而前面提到的基于i p v 4 打补丁的方法也难以彻底解决问题，并且n a t 给某些端到端的应用，如f t p ，w i n s 等，造成困难【3 l 】。 i p v 4 地址扩展模型主要分为两种：一种是熟知的平面型固定长度地址， 如i p v 6 使用1 6 字节地址和t u b a 【3 2 使用2 0 字节地址；另一种是可变长度地 址，如p i p 3 3 3 4 】 3 5 1 ，s i p p 4 4 ，i p n l 36 1 ，i p 4 + 4 3 7 】【3 8 1 ，n i m r o d 3 9 以及层次命 名”l j 等。下面介绍主要的可变长度地址模型。 1 2 1 1p i p 模型 p i p 是p a u lf r a n c i s 在1 9 9 3 年提出的一个i p v 4 替代协议，它与s i p i 4 3 l 合 并形成了s i p p 矧，是i p v 6 的前身之一。p i p 采用6 4 位地址。p i p 模型除了 有将名字( i d ) 与地址分离，和源路由这两个主要特点外，还有如下特点。 o 以p r o v i d e r 为根的层次地址； o 自动域范围的地址前缀分配； o 自动主机地址与i d 分配； o 出口p r o v i d e r 选择： o 多默认路由( 源路由，但可以有多个出口点) ； 。与i p v 4d 类地址等价的组播地址： o a n y c a s t 寻址； o 支持策略路由； o 支持移动主机： o 支持与i p v 4 主机互操作； o 支持与现有应用互操作； p i 口包头分为三部分：i n i t i a lp a r t ，t r a n s i tp a r t ，o p t i o n sp a r t 。i n i t i a lp a r t 是8 个3 2 位字长，t r a n s i t p a r t 是3 个3 2 位字长加可交长度，i n i t i a lp a r t 是可 变长度的。 p i p 在b e l l c o r e 的试验网中的实验运行结果显示p i p 有与i p v 4 相当的性 能。 根据文献 3 3 】【3 4 3 5 的结论，p i p 解决了路由伸展性与地址耗尽双重问 题，并且p i p 的架构有很强的适应性，可以演化容纳新的特性而不牺牲性能。 p i p 最后被吸收进s i p p ，而没有独立发展，其源路由寻址特性融入s i p p 的簇 寻址特性。 第l 幸绪论 1 2 1 2s i p p 模型 s i p p 【4 4 j 提出了扩展的变长寻址概念，移动寻址，多播寻址等功能。这些 都是通过i p v 4 松散源路由( i p v 4l o o s es o u r c er o u t e ) 机制实现。 在s i p p 中，中间结点的地址可以是如下种类地址之一：多播地址，分级 单播地址，以及簇地址。多播地址与分级单播地址与i p v 4 地址类似，但是是 6 4 位长。簇地址用来向一组s i p p 结点发送数据。要使用i p 松散源路由寻址， s i p p 结点需要两个功能：s i p p 结点要能将自己的地址转换成6 4 位长，s i p p 结点要能反转i p 松散源路由用来返回数据包。 实验结果表明，i p v 4 松散源路由能用来实现移动寻址，扩展( 变长) 寻 址，服务商选择( p r o v i d e rs e l e c t i o n ) ，以及基于源( s o u r c e b a s e d ) 和基于核 ( c o r e b a s e d ) 的多播。分析结果表明，采用一种单一的机制来实现路由与寻 址功能，优于采用多种特定的机制来实现各种功能。单一的机制比多个特定 的机制更易于实现，也更有效率，也有利于协议未来的演变。 但是，使用路由序列有一些不好的副作用。例如，因为路由器转发包时， 不一定检查扩展地址的高位段，这可能导致s i p p 进入某种错误状态。 s i p p 地址是6 4 位长的单一结点或结点组的标识。有三类s i p p 地址：单 播，簇和组播地址。单播地址标识单一结点。簇地址标识一组具有共同地址 前缀的结点，发到一个簇的包将会发送到该簇的个成员。组播地址标识一 组结点，发到一个组播地址的包将会发送到该组的所有成员。 另外，s i p p 支持通过路由选项扩展地址空间，地址可以达到1 2 8 位，1 9 2 位甚至更长。 单播地址包括全局层次地址，本地地址，纯i p v 4 地址三类。 全局层次地址的构成如下，最高位是“c ”( 1 位) + “p r o v i d e r i d ”( n l 位) + “s u b s c r i b e r i d ”( n 2 位) + “s u b n e t i d ”( p 位) + “n o d e i d ” ( 6 3 n 1 n 2 p 位) 。最高位称为c 位，标识地址所表示的结点是i p v 4 还是s i p p 结点。 本地地址只在本地子网有效，类似i p v 4 的私用地址，构成如下，最高四 是“0 1 1 0 ”+ “s u b n e t i d ”( 1 2 位) + “n o d e i d ”( 4 8 位) 。“n o d e i d ” 通常使用结点的i e e e 8 0 2 的4 8 位地址。 纯i p v 4 地址用于s i p p 与i p v 4 互操作，构成如下，最高位是“1 ”+ 哈尔滨工程大学博士学位论文 “h i g h e r o r d e rs i p p p r e f i x ”( 3 1 位) + “i p v 4 a d d r e s s ”( 3 2 位) 。 簇地址用来访问一组具有共同地址前缀的结点的最近的边界结点。当簇 地址用作地址序列的一部分时，是用来选择中间网络的。簇地址只能作目的 地址。簇地址构成如下，最高位是“c l u s t e rp r e f i xp r o v i d e ri d ”( n 位) + “0 ”( 6 4 一n 位) 。 组播地址构成如下，最高位是c ( 1 位) + “1 1 1 1 1 1 1 ”( 7 位) + “f l g s ” ( 4 位) + “s c o p ”( 4 位) + “g r o u p i d ”( 4 8 位) 。c 位作用如前所述。f l g s 字段的前三位保留，必须置0 。f l g s 最后一位是0 ，表示该组播地址是由 i n t e r n e t 管理机构永久分配的熟知的组播地址；最后一位是1 ，表示该组播地 址是临时组播地址。s c o p 是一个4 i b n 值用来限定组播的范围，其值的定义 如下， 0r e s e r v e d 1 i n t r a - n o d es c o p e 2i n t r a - l i n ks c o p e 3 ( u n a s s i g n e d ) 4 ( u n a s s i g n e d ) 5i n t r a s i t es c o p e 6 ( u n a s s i g n e d ) 7 ( u n a s s i g n e d ) 8 i n t r a - o r g a n i z a t i o ns c o p e 9 ( u n a s s i g n e d ) 1 0 ( u n a s s i g n e d ) 11 i n t r a - c o m m u n i t ys c o p e 1 2 ( u n a s s i g n e d ) 1 3 ( u n a s s i g n e d ) 1 4 g l o b a ls c o p e 1 5r e s e r v e d s i p p 对移动i p 有较好的支持，易于从i p v 4 升级。s i p p 支持层次地址， 具有可伸缩的地址空间，能够容纳1 9 2 位甚至更长的地址。s i p p 最后被吸收 到i p v 6 ，而没有独立发展，其簇寻址特性被吸收到i p v 6 的源路由机制中。 1 2 1 3i p n l 模型 i p n l ( i p n e x tl a y e r ) 9 6 】，是一个n a t 扩展的i m e m e t 协议架构，用来解 决i p v 4 地址耗尽问题。n a t 扩展的协议架构只需要修改主机与n a t 代理， 而i p v 4 路由器及其支持的协议无需改变。i p n l 试图保存i p v 4 的所有原始特 第1 章绪论 性，特别是地址前缀位置独立性。i p n l 提供子网隔离( 无需重编号) ，并且 允许多址而不会使子网前缀影响默认路由域。 i p n l 的目标是，定义一个适当的i n t e r a c t 架构，该架构保持i p v 4 原有的 特性，同时解决i p v 4 的扩展性与地址耗尽问题。 i p n l 的特点是： 1 ) n a - t - 扩展的架构，最大重用现存的i p v 4 架构； 2 ) 数据包中保存完全限定域名( f q d n s ) 作为端到端主机标识符； 3 ) 本地寻址与全局寻址完全隔离。 i p n l 拓扑结构包括：本地域，中间域，域问路由器。使用私用地址的 域通过n a t 代理与使用全局地址的i n