（计算机应用技术专业论文）6pe的设计研究.pdf

贵州大学硕j ：论文 摘要 6 p e 技术是实现i p v 4 向i p v 6 过渡的一种技术，目的是连接i p v 6 孤岛。它实现了纯i p v 6 信息跨越i p v 4m p l s 骨干网。v 6c e 传送i p v 6 数据至p e ，p e 支持双栈，可同时处理v 4 n 6 业务。然后，6 p e 路由器采用两层m p l s 标签，封装i p v 6 流量。顶层标签通过l d p 分配， 使用口v 4 路由信息将数据包传送至目的6 p e 。第二层标签通过n i p b g p 与目的i p v 6 地址 关联，传递i p v 6 可达性信息。 6 p e 技术可以向m p l s 骨干网平滑的注入i p v 6 业务，在不影响m p l s 本身提供业务的同 时，又避免减少i p v 4 创收的风险。这种策略保留了当前的i p v 4m p l s 功能。例如： m p l s n p n m p l s q o s 。m p l s t e ，a t m + i ps w i t c h i n g ，l 2s e r v i c e s ( a t o m ，e o m p l s ) 。 同时，能够为企业用户提供本地i p v 6 服务。而且，该方式主要优点在于无需升级p 路由器。 6 p e 对i p v 4 和i p v 6 提供了具有相同能力，弹性和扩展性的m p l s 骨干网。但是，它不适用 于大量的i p v 6 请求服务，也不支持i p v 4 与i p v 6 的互操作。 本文提出的6 p e 设计方案，完成三方面的工作： ( 1 ) 提出i p v 6 路由算法。依据b ! ! b ：竖盟：b 勉：d 丛提供的路由信息，设计算法 的数据结构，具有稳定性和灵活性。而且，分析对比各种路由查找技术并得出 结论：二分查找法是面向i p v 6 的路由查找技术中性能最好的方法。 ( 2 ) 详细论证i n g r e s s6 p e 和e g r e s s6 p e 对话中，m p b g p 的应用过程。这是理论 和实际相结合的一个案例。 ( 3 )代码描述本案例中 i p l s 骨干网内部数据转发的全过程。用代码说明问题，比较 深刻，清晰。另外。深刻阐述了相关技术的理论基础。 i p v 6 是网络应用发展的一个必然结果。目前，i p v 6 网络用户比2 亿多1 p v 4 网络用户 少得多也没有典型的应用。所以，两种网络在一段时期内并存是不可避免的。因此t 如何 从i p v 4 过渡到i p v 6 的许多技术就应运而生了。经过对多种过渡技术的比较和探讨，本文 选择6 p e 技术为研究对象，它具有极大的发展前景，如：6 v p e ，本地i p v 6 服务，业务量 管理，网络扩展性等等。 关键词：v 4 v 6 过渡机制，双栈，隧道，d n si p v 6 正向解析，i p v 6 路由算法，m p b 6 p ， l d p 3 6 p e 的设计研究 a b s t r a c t 6 p ew a sat r a n s i t i o nt e c h n o l o g yf r o mi p v 4t oi p v 6i no r d e rt oc o n n e c ti p v 6i s l a n d s i tc a l l m a k ei p v 6o v e rm p l s i p v 4 d u r i n gt h et r i p ，i p v 6d a t aw a st r a n s f e r r e db yv 6c et op ew h i c h r a nt h ed u a ls t a c kw h i l ev 4 n 6w a si d e n t i f i e d a n dt h e n ，i p v 6s t t e a mw a se n c a p s u l a t e du s i n gt w o l a y e r so fl a b e l sb y6 p er o u t e r t h ef i r s tl a b e lw a sa s s i g n e db yl d p t h a tt h ev 6d a t aw a sc a r r i e dt o l o o k u pi p v 4r o u t i n g t h es e c o n dl a b e li n f o r m e dt h es y s t e mh o wt oc o n f i g u r ei p v 6a d d r e s sa t g a t e w a yr o u t e r m p - b g pa c l l i e v e dt h em a i ng o a l m p l sh a dn o tb e e ni n f l u e n c e do ni t s e l fi n c l u d i n gi t sv a r i o u ss e r v i c e s a tt h es a m et i m e ，t h e i n v e s t e dc a p i t a lw a sa sl o wa sp o s s i b l ew h e ni p v 6w a so v e rm p l s i p v 4 s ot h es t r a t e g yw o u l d s u p p l yt h ei p v 4m p l s f u n c t i o n s f o re x a m p l em p l s v p n ，m p l s q o s ，m p l s t e ，a t m + i p s w i t c h i n g ，l 2s e r v i c e s ( a t e m ，e o m p l s ) i na d d i t i o n 。c l i e n t sc a l ls h a r ei p v 6s e r v i c e s o n t h eo t h e rh a n d ，pr o u t e rd i dn o tn e e dt ob eu p d a t e dt os u p p o r ti p v 6 t h u s ，a sf o ri p v 6a n di p v 4 ， 6 p ep r o v i d e dt h es a m ea b i l i t y , f l e x i b i l i t y , e x p a n s i b i l i t yo fm p l s h o w e v e r , t h eh u g en u m b e ro f i p v 6c o m m i r e ds e r v i c e sw b e y o n d6 p ep e r f o r m a n c e w h a ti sm o l e ，t h e r ew a sn o t i n t e r o p e r a t i o nb e t w e e ni p v 4a n di p v 6 t h ep a p e rs o l v e dt h e s ec d f i c a lq u e s t i o n sa sf o l l o w e d ： f i r s t l y ：b a s e do ni p v 6a g g r e g a t a b l eg l o b a lu n i c a s ta d d r e s s ，r o u t i n ga l g o r i t h mf o ri p v 6w a s r e p r e s e n t e d a c c o r d i n gt or o u t i n gi n f o r m a t i o nf r o mh t t p ：w w w 6 h n n e n e t , t h es t e a d ya n df l e x i b l e d a t as t r u c t u r ew a sd e s i g n e di nt h i sp a p e r s e c o n d l y ：s e s s i o no fi n g r e s s6 p ea n de g r e s s6 p eb ym p - b g p w a sp r o v e d i tb r o u g h tt h et h e o r y i n t ot h ep m c t i c e f i n a l l y ：p r o g r a m e dm p l sl d pe x p l a i n e dh o wt ow o r k i ti sc l e a ra n dp r o f o u n di nt h i sw a y o n t h eo t h e rh a n d , t h er e l a t i v et e c h n o l o g i e sw a sa l s oe x p l a i n e d i p v 6n e t w o r kw i l lb eam a i n s t r e a mi nt h ef u t u r e n o w a d a y s ，c o m p a r e d 埘t hi p v 4l l s e r s ( 2 0 0 m i l l i o n ) i p v 6u a r ef a rl e s sa n dn ou n i q u ea p p l i c a t i o n t h e r e f o r e ，i ti su n a v o i d a b l et h a ti p v 4 a n di p v 6c o e x i s tf o ral o n gt i m e t h er e l a t i v et e c h n o l o g i e sa b o u th o wt ot r a n s f e r r e di p v 4t oi p v 6 i sp r e s e n t e d b yd e s c r i b i n t ga n da n a l y s i n gk i n d so ft r a n s i t i o nt e c h n o l o g i e s ，6 p ei sc h o s e da n d s t u d i e di nt h i sp a p e rf o ri th a sb r i 出f u t u r e ，s u c ha s6 v p e ，i p v 6s e r v i c e s ，1 e k e y w o r d s ：v 4 v 6w a n s i t i o nm e c h a n i s m s ，d u a ls t a c k ，t u n n e l i n g ，d n sr e s o l v e di p v 6a d d r e s s ，i p v 6 r o u t i n ga l g o r i t h m , m p b o p , l d p 4 蚩州人学预i ：论文 前言 6 p e 技术是实现i p v 4 向i p v 6 过渡的一种技术。它实现了纯i p v 6 信息跨越i p v 4m p l s 骨干网。v 6 c e 传送i p v 6 数据至p e ，p e 支持双栈，可同时处理v 4 n 6 业务。然后，在i p v 4 m p l s 骨干网中为不同的i p v 6 网络之间建立l s p 隧道，并通过m p - b g p 传递i p v 6 可达性 信息。 6 p e 发展现状“5 ”3 “1 ：一些国内外著名的通信设备制造商和软硬件生产商都已经在 他们的路由器产品和操作系统当中实现了对i p v 6 的支持一些著名的开放系统平台如 f r e e b s d l i n u x 等也加入支持i p v 6 的软件包。各国还建立了若干针对i p v 6 的试验网络如 6 b o n e ，6 i n i t ，中国也建立了试验网络6 t n e t ，并在实施全新的i p v 6 网络c n g i 的建设。i p v 6 地址已经开始分配，一些国外网络运营商，如日本的i i j 和k d d i 等，开始提供商用的i p v 6 接入服务。 c i s c 0 7 5 0 0r o u t e r s ，c i s c o l 2 0 0 0r o u t e r s 支持6 p e 。 z x r o s 实现了6 p e 过渡机制。 中国电信核心网络设备以硬件支持i p v 6 转发为主，双栈和6 p e 并举。i p v 6 处理能力在 网络中逐步启用。 中兴通讯的双栈路由器在中科院组织的i p v 6 试验中，成功地实现了与国际上其他主流 厂商i p v 6 设备的互通和应用。 烽火网络的模块化路由操作系统软件平台m r 0 s 全面支持i p v 4 i p v 6 双栈和各种过渡策 略。 到2 0 0 3 年底，全球已分配的i p v 6 地址块数为4 9 9 块，其中美国居全球第一位，共7 3 块，占全球总数的1 5 ，美国，日本，德国，荷兰，英国5 个国家所分配到的地址总数占 全球总数的近半数( 4 8 ) 。我国申请到的i p v 6 地址块数只有9 块，占总数的2 弱。事实 上，目前我国申请到的i p v 6 地址块都是默认的申请大小3 2 。 虽然在m p l s 骨干网络上建置i p v 6 服务会比较单纯，然而就现有的教育学术网络及i s p 业者所拥有的骨干网络来看，国内大半的服务网络都没有建置m p l s 骨干。高端路由器厂商 c i s e n 。j u n i p e r 等都推出了自己的m p l s 产品。 c i s c o 于2 0 0 1 年下半年制定的6 p e 方案符合i e t f 组织就”采用b g p 而连接跨越多个 i p v 4 云的i p v 6 域1i p v 6 - b g p 颁布的最新版本的标准草案。 m p l s 对多协议的支持，适应于承载多种网络，促进了网络的互连和融合，在路由平台 上m p l s 提供了高可用性。 对于正在使用的路由器可能会因为扩展能力等问题而无法升级1 0 s 版本，同时又不愿意 硬件投资，从而阻碍m p l s 业务的开展和应用。那么软体扩展是一种可选择方法。 6 p e 技术可以向m p l s 骨干网平滑的注入i p v 6 业务，不影响m p l s 本身提供的业务同时， 又避免减少i p v 4 创收的风险。6 p e 对i p v 4 和i p v 6 提供了具有相同能力，弹性和扩展性的 m p l s 骨干网。 当使用m p l sl 3v p n 技术作为核心网络方案时，边缘网络作为三层c e 接入到核心网络 上，核心网络需要支持6 p e 技术。 6 p e 的设计研究 第一章基于m p l s 的i p v 6 过渡技术 i e t f 于1 9 9 7 年开始制定m p l s ( m u l t i - p r o t o c o ll a b e ls w i t c h i n g ) 。m p l s 技术是一种将 第三层路由和第二层交换结合在一起的i p 交换技术。它的体系结构是基于网络入口无连接， 网路内部面向连接的结构。 m p l s 技术与其它技术相比具有三个特点： ( 1 )r ；i p l s 中的分组转发技术与当前的无连接网络环境完全不同。前者是基于显示 的路由交换( e x p l i c i t m u t i n g ) 和原地址路由方式。后者是基于目标的逐跳单播 路由选择方式( h o p - b y - h o pd e s t i n a t i o n - b a s e d n a i c a s t m u t i n g ) 。 ( 2 )m p l s 中所使用的标签没有固定格式，随下层媒体的变化而变化。例如：a t m 的v c i v p i ，f r 的d l c i ，x 2 5 的l c n 。 ( 3 ) m p l s 支持拓扑驱动和请求驱动。f e c l s p 机制更容易满足t e 或q o s 的要求。 1 9 8 1 年正t f 制定的i p v 4 协议既带来了第一代互联网的巨大成功又随着互联网商业化 不断深入发展，面临许多挑战。例如：移动i p v 4 ，家庭网络( h a n s ：h o m em n e t w o r k s ) ， 在线游戏p 2 p ，p d a s ( p e r s o n a ld i g i t a la s s i s t a n t s ) 于是，i e t f 于1 9 9 3 年着手制定i p n g 的标准它的主要需求是：大的地址空间，迁移 和部署，安全，服务质量，移动性；拓扑结构。网络管理维护等。1 9 9 8 年公布i p v 6 标准 r f c 2 4 6 0 。7 从应用角度来看，不需要区别什么是i p v 4 应用什么是i p v 6 应用i p v 6 是网络应用 发展的一个必然结果0 9 j 1 删。按照因特网中r o b e r tm e t c a l f e 准则：一个网络的价值与它的节 点数目的平方成正比。一个不成熟，不完善的网络不能吸引运营商和用户。因此，这种网络 也不能普及。目前，i p v 6 网络用户比2 亿多 p v 4 网络用户少得多。也没有典型的应用。所 以，两种网络在一段时期内并存是不可避免的 部署i p v 6 的大致过程如下： 首先，i p v 6 孤岛跨越i p v 4 云，彼此连接 其次，形成骨干i p v 6 网，增加i p v 6 规模应用并且，i p v 6 和i p v 4 互通。 最后，i p v 4 骨干网逐步萎缩成局部的孤岛而i p v 6 占据了主导地位，具各全球范围内 的连通性。 r f c 2 8 9 3 中提出从i p v 4 过渡到i p v 6 的5 种工具： ( 1 ) d u a ls t a c k ( 2 ) c o n f i g u r e d t u n n e l i n g ( 3 )i p v 4c o m p a t i b l ei p v 6a d d r e s s e s ( 4 )a u t o m a t i ct u n n e l i n g ( 5 ) p r o t o c o lt r a n s l a t i o n 6 贵州大学硕士论文 1 1 两种关键的过渡技术一一双栈与隧道 1 1 1 基于双栈的过渡技术 网络中的路由设备同时支持i p v 4 和i p v 6 两套协议。逻辑上，相当于两个独立的路由 器。如图示： a p u c a = r i o n 1 c p 鼬毽p i p v 4礤v 6 d r i 、，e r 图1 - 1 双栈结构示意图 应用程序根据d n s 地址解析所返回的地址类型，决定使用那种协议。而且，还要选择 并配置内部网关路由协议( i g p ) 。如：i s i s ，或用于i p v 4 的o s p f v 2 和用于i p v 6 的o s p f v 3 。 这样的路由设备有能力同时转发i p v 4 和i p v 6 数据包。但是，它要求全面升级网络中所有 的路由设备，支持双栈。并且，需要配置足够的内存容纳i p v 4 和i p v 6 路由表等。技术复 杂，投资风险大。 1 1 2 基于隧道的过渡技术 隧道就是在一种协议中承载另一晕中协议，实现跨越不同域的互通 3 1 1 如下圈所示：i p v 6 的寻址信息封装到i p v 4 中： ii 。d a t a 。 _ - - - - - - 一- + 图1 - 2 - - - - - - - - - _ i i p v 4 i l h e a d e r i - ii i i p v 6 i i h e a d e r i _ ：，。_ it r a n s p o r tl = - i l a y e r i f h e a d e r i ii - jl d a t a 1 。 ii _ - 一一- _ e n c a p s u l a t i n gi p v 6i ni p v 4 7 一一 6 p e 的设计研究 在i p v 4 隧道上部署i p v 6 ，主要实现隔离i p v 6 站点之间的通信。或通过i p v 4 骨干网 与i p v 6 网络连接。并且，不必升级它们之间存在的i p v 4 基础框架。通过i p v 4 隧道传送i p v 6 ， 需要配置隧道接口的本地i p v 6 地址和隧道两端的i p v 4 地址。隧道的端点要以双栈模式运 行。 各种隧道机制 ( 1 ) 手工配置隧道 手工配置隧道适用于网络组成不太复杂。常规通信连接的稳定而安全的链路。要求i s p 注册i p v 6 地址。这种技术在6 b o n e 上已得到验证。 ( 2 ) 通用路由封装g r e ( g e n e t i cr o u t i n ge n c a p s u l a t i o n ) 隧道 g r e 是唯一支持传送i s - i s 的隧道协议。但是，在主机上实施的较少。 ( 3 ) 隧道断路( t u n n e lb r o k e r ) 由b r o k e r 处理隧道请求，并将相应配置转发到相应的路由器。它主要用于独立且隔离 的i p v 6 终端系统的通信。但是，存在安全问题。 ( 4 ) 自动6 t “隧道 6 t 0 4 的目标是通过i p v 4 - o n l yi s p 连接i p v 6 。这种技术无需申请正式i p v 6 地址，就可 以部署i p v 6 网络并接入到i p v 6 骨干网中。但是，由于网络使用的i p v 6 地址限制为特殊的 6 t 0 4 地址，它不适用于在大型i p v 6 骨干网络中使用。 1 63 21 66 4 图1 - 36 t 0 4 地址结构 6 t 0 4 隧道是由6 t 0 4 路由器向站点分配6 t 0 4 前缀i p v 6 地址。由6 t 0 4 路由器完成隧道封 装。它只需要一个全球唯一的i p v 4 地址可使整个站点获得i p v 6 的连接。因此，使用者不 会因为所在i p v 4 的环境限制存取i p v 6 资源。6 t 0 4 如果没有通过i p s e c 的保护，有潜在的 安全问题。如：s p o o f i n gr i s k s ，d o sa t t a c k s 采用隧道方式存在的主要问题有： ( 1 ) 由于在i p v 6 数据包前面插入2 0 b y t e 的i p v 4 头，可能会造成分段，从而影 响性能。 ( 2 ) i c m p v 4 错误消息，只返回i p v 4 报头外的8 b y t e 。这样i p v 6 源站点无法得 知i p v 6 地址信息。 ( 3 ) r f c 2 8 9 3 中分配给i p v 6 封装在i p v 4 中的协议号是4 1 ，表示i p v 4 包里面的 上层协议数据是i p v 6 数据包。协议号4 1 有可能被防火墙滤掉。 ( 4 ) i p v 6 i n i p v 4 隧道无法穿越一个启用动态端口转换的n a t 。 ( 5 ) 启动穿隧服务的设备，大多数无法承担较大的i p v 6 流量。 贵州大学硕1 ：论文 1 2 基于m p l s 的i p v 6 过渡技术 1 2 1c e 隧道传送i p v 6 在m p l s 网络上采用c e 隧道传送i p v 6 ，是一种最简单的方法。不需要重新配置p 雨l p e 。 在c e 路由器上配置隧道并且支持双栈。c e 路由器封装l p v 6 数据在i p w 中，通过 m p l s 传送到对端的c e 路由器。也就是说，c e 与p e 通信的是i p v 4 业务对m p l s 域来 说也仍然是i p v 4 。但是，因为i s p 无法从其地址空间中指定i p v 6 前缀，由于它根本看不到 i p v 6 流量，因此，从其业务组台中取消了i p v 6 业务的附加值。 1 2 2m p l s 电路传送i p v 6 过渡技术 许多服务提供商已经设计了用于数据服务的w a n 或m a n 。通过连到i s p w a n 或m a n 的路由器，可以配置使用与现有互联网i p v 4 相同的第二层基础设施。运行纯i p v 6 协议。 底层的机制对i p v 6 完全透明。 在m p l s 网络中，i p v 6 数据包可以通过a t o m ( a n y t r a n s p o r t o v e r m p l s ) 或e o m p l s ( e t h e m e to v e rm p l s ) 来传递。由于i p v 4 和i p v 6 流量不混合。所以，如果i p v 6 链路发 生故障，就可以减少对i p v 4 网络的影响。 1 2 36 p e ( ip ，6p r o v i d e re d g er o u t e ro v e rm p l s ) 过渡技术 目前，m p l s 技术和i p v 6 技术相结合的主要应用是6 p e 和6 v p e 在c e 端口配置并转发i p v 4 流量或纯i p v 6 业务。6 p e 支持双栈。6 p e 技术允许纯的i p v 6 或i p v 6 和i p v 4 穿过i p v 4m p l s 骨干网p ”。 6 p e 路由器采用两层m p l s 标签，封装i p v 6 流量。顶层标签通过l d p 分配，使用i p v 4 路由信息将数据包传送至目的6 p e 。第二层标签通过n i p b g p 与目的i p v 6 地址关联。相当 于l 3v p n 。该方式主要优点在于不需升级p 路由器。 这种策略保留了当前的i p v 4 m p l s 功能。例如：m p l s v p n 。m p t 旦q o s m p l s t e ， a t m + i ps w i t c h i n g ，i _ 2s e r v i c e s ( a t o m ，e o m p l s ) 。同时，能够为企业用户提供本地i p v 6 服务。 1 2 46 v p e ( i p 6v p np r o v i d e re d g er o tt e r so v e rm p l s ) 下一代网络的三层x r p n 将以b g pm p l sv p n 为主导。6 v p e 作为一种v p n 技术，v p n 中多个i p v 6 站点可以分属于不同的v p n ，i p v 4 v p n 工作原理十分相似。并且，这种技术 可使得i p v 6v p n 和p v 4v p n 同时存在。 c e 通过一个单独的物理，逻辑端口向p e 发送v p n i p v 6 路由信息。p e 学习这些路由信 息，为每个v p n 用户分别维护一张虚拟路由转发表( v r f ) ，用来处理v p n i p v 6 路由，是 9 6 p e 的设计研究 v p n 功能的主要实现者。 入口6 v p e 接到c e 的i p v 6 信息，查找v r f 表。通过b g p 和出口的6 v p e ，用m p l s 标签绑定( p e e r i n gr e l a t i o n s ) 。 6 p e 和6 v p e 的区别：6 p e 是一种过渡技术，目的是连接i p v 6 孤岛。6 p e 中多个i p v 6 站点属于同一个v p n ( i p v 6 ) 公网。地址空间不能重叠。而6 v p e 是一种i p v 6 v p n 技术， 其中，多个i p v 6 站点完全可以同i p v 4 v p n 一样，分属丁i 不同的v p n 1 2 5n a t i v oi p v 6 所有设备全部升级到i p v 6 ，支持i p v 6 路由。如果需要提供i p v 4 i p v 6 共存服务：则需 要双栈控制平面的支持或i p v 4o v e ri p v 6 隧道技术。， 0 贵州大学硕l ：论文 第二章路由查找技术的分析 2 1 d n s 解析l p v 6 地址 d n s ( d o m a i nn a m es y s t e m ) 域名系统是存储和维护主机名称与i p 地址对应列表的分 布式机制。使刚域名既方便记忆同时也防止i p 地址变动引起使用不便的问题。在协议执行 时，使用的不是域名而是i p 地址。也就是说，域名是无法在封包传递过程中使用的。为将 域名“翻译”成i p 地址或进行相反的操作，可以利用域名系统d n s 的功能。d n s 不仅提 供这种变换的服务，还对域名进行层次化的处理。 2 1 i 域名查询 在d n s 客户端配置简单的d n s 解析器( r e s o l v e d 。一般由 e t c h o s t s c o n f ，r c s m v c o n f ，h o s t s 三个配置文件组成。只有当本机域名查询失败时，才转交给 d n s 服务器。i p v 6 i p v 4d n s 都是采用树型结构的域名空间。在查询的过程中，基本上是 按照域名树层层搜索”j 。如图示：d n s 域名查询的处理过程。 l i n u x 默认名称解析顺序 ( 定义在，e t c ，h o s t c o n f 文件里) 查询，。c 。文件里定义 查询e 。r 。n f 文件里定卫 啡脚陋了器一曲。 图2 - 1d n s 域名查询的处理过程 2 i 2i p v 6 正向解析 在d n s 区域声明文件里，a 资源记录用来指定域名对应的一个m v 4 地址。a a a a 和 a 6 记录域名和i p v 6 地址的对应关系。其中，a a a a 资源记录不支持地址的层次性，而a 6 资源记录符合i p v 6 地址的层次结构，从而支持地址的聚集。因此，本文中，i p v 6 正向解析 采用a 6 资源记录。 以i p v 6 可聚类全局单播地址为例，a 6 记录根据t l a ，n l a 和s l a 按层次把1 2 8 位 的i p v 6 地址分解为若干的地址前缀和地址后缀。形成一条地址链。每个地址前缀和地址后 缀都是地址链上的一环，一个完整的地址链构成一个i p v 6 地址。 6 p e 的设计研究 a 6 记录的r d a t a 格式如幽示： 前缀长度 地址后缀前缀名字 ( 1 字竹) ( 0 1 6 子节)( 0 - 2 5 5 个字符) 图2 2a 6 记录格式 前缀长度：1 个字节的无符号编码，取值范围0 - 1 2 8 。 地址后缀：该字段必须能够表示1 2 8 位的前缀长度，其中可以包括o 7 位填充位，以使字段 具有完整的字：肖数。如果有填充位，当装载区域文件时必须置为0 。并且在接收时不处理。 前缀名字：编码为域名，根据 d n s i s 规则，该名字不能被压缩。 当前缀为0 ，域名部分不出现，如果前缀长度为1 2 8 ，地址后缀部分不出现。 g e t a d d r i n f o 函数 g e t a d d r i n f o o 的功能是执行d n s 查询，完成主机名字到m 地址以及服务到端口号的转 换。 该函数的定义如一f ： # i n c l u d e i n tg e t a d d r i n f o ( c o n s tc h a r * h o s t n a m e ，c o n s tc h a r * s e r v i c e ，c o n s ts t m c ta d d r l , f f o h i n t s ，s t u c t a d d r i n f o * * r e s u l t ) ；，返回值：成功返回0 ：出错返回非零 其中：h o s t n a m e 是主机名或地址串。 s e w i c c 是服务名或十进制数的端口号字符串。 h i n t s 是一个空指针或指向一个a d d r i n f o 结构的指针，由调用者填写关于它想返 回的信息类型的线索。 s t r u c ta d d r i n f o i n tm _ f l a g s ；a ip a s s i v e 或a i _ c a n o n n a m e i n ta i 地址协议簇family； i n ta i _ s o c k t y p e ；套接口类型 i n ta ip r o t o c o l ；，套接口协议 s i z eta ia d d r l e n ；ma d d r 的长度 c h a r * a ic o n n e ；，指向主机名字的指针 s t r u c ts o c k a d d ra ia d d r ；，指向套接口地址结构的指针 s t r u c ta d d r i n f oa in e x t ；，指向链表中下一个地址结构的指针 如果函数返回成功，r e s u l t 参数通过a in e x t 指针连接a d d r i n f o 结构链表。 2 2 无类域问路由c i d r ( c i a s s i e s si n t e r - d o m a i nr o u t i n g ) 在i n t e r n e t 的发展初期，i p v 4 地址采用基于类的地址结构。由于其简单性而得到广泛 的应用。但是，随着网络的不断发展，使用这种地址结构产生三个方面的不足：( 1 ) 不同类的 i p 地址不能切合实际地反映需求，因此，浪费大量的地址。( 2 ) 子网化技术导致站地址减少， 同时，也增加了路由选择的复杂性。( 3 ) 主干路由器需要跟踪每一类网络，使得路由表的规模 增大。 为了能够降低路由表规模的增长速度以及提高地址空间的利用率，i e t f 提山了一种称 2 贵州大学颂士论文 之为无类域问路由c i d r ( c l a s s l e s s n t e r d o m a i nr o u t i n g ) 的地址结构。它的几个关键特 性改变分类地址的低效性”。：( 1 ) 无类地址。c i d r 引入任意长度的网络前缀，根据3 2 b i t i p 地址和3 2 h i t 掩码做出选路决策。( 2 ) 强化路由汇聚。( 3 ) 超网化。 c i d r 技术采用分层次的路由选择和分地区的路由选择l 。通常是，通过区域分组网络。 在一个给定的区域内，所有网络号能共享相同的前缀，并能以单个路由表项出现在其他区域 的路由表中。这意味着，主干网路由器只需要存储一个路由表项，该表项提供了到许多底层网 络的可达性。但是，由于现在的目的地址中没有便于搜索的白包含信息，对所有目标路由器只 能在最长前缀( 3 2 ) 的基础上进行。如果地址没有找到，就搜索下一个前缀( 3 1 ) 的路由。依 此类推。 前纽蚝度为3 2 的路由 前缀长度为3 l 的路由 前缀长度为3 0 的路由 前缀长度为2 的踏由 前缀长度为i 的路由 图2 - 3 在无分类编址中搜索的数据结构 另外，由一些路由协议引入的分层路由，要求地址分配能影响实际的网路拓扑布局。所以， 制定地址分配计划之前，预见未来的拓扑结构非常重要。 最后，由i s p 为用户重新分配地址，更换i s p 要求给网络设备重新编号。这将制约地址分 配的可伸缩性。 2 3 二分法路由查找技术 最长前缀匹配l p m ( l o n g e s tp r e f i xm a t c h i n g ) 是把i p 地址映射到尽可能小的前缀汇聚 的集合里。对于给定的i p 分组，从路由表中查找匹配其目的地址的最长前缀，然后查找该表 项中下一跳路由端口号，并复制该分组到相应的输出端口。 若把一条长度较短的地址前缀展开成多条地址长度较长的前缀集合，称为前缀扩展。它 能减少不同长度前缀的数目。并且，这个前缀覆盖范围越小，则相应的端口具有越高的优先 权。 2 3 1 地址区间的二分查找法 k 位i p 地址前缀p 表示成二进制形式p 。p 2 。令k = p r p r o 0 和p n = p ，p 2 r1 1 。 p 。与h 是在p 的末尾添加了m k 位0 和1 。前缀p 能唯一确定地址区间 p l ，蹦。给定i p 地 址丑j r ，f 、 ，当且仅当p 是x 的前缀。地址区间的长度l ( p ) = p 一p l + i = 2 ”。因为m 为常数， 意味着越欧的i p 地址前缀对应更窄的地址区间。这些地址区间的关系可能是互斥，包含但不 可能相交。 路由表中如果有两个或更多的i p 地址前缀是地址x 的前缀。也就是说，地址x 属丁两个 6 p e 的设计研究 或更多的地址区间。既然i p 地址查找问题是找到地址的最i 丈匹配前缀p 。那么查找过程等 价于发现包含j 的最窄地址区间 p l ，p i 。 区间二二分法最初由b u t l e rl a m p s o n 提出。算法的核心思想依据上述性质。： 作过程： 首先，把路由表中所有地址前缀转换成地址区间。然后排序区间端点值并计算与这些值相应 的最长前缀。数据预处理的时间复杂度为o ( n ) ，n 为地址前缀个数。最后，给定地址五对一 组有序的p l 和p 进行二分查找。查找时间复杂度为o ( 1 0 9 ：“) 。 由于目前路由表的数目非常大，若单纯地使用简单的二二分查找法，查找速度很慢。然而， 如果利用前缀扩展降低前缀数目并对长度相等的前缀集合再使用区间二分查找法，使得查找 性能得到改善。 另一种优化策略是基于网络流量的聚合特性。有流量发生的地址段和自治域在概率分布 上呈现出相当的聚合度，即约2 0 的地址段和自治域承载了绝大多数的数据通信量。由此，建 议把高频使用的地址段作为查找的起点，并建立缓存机制提高转发效率。 2 3 2 基于前缀长度的二分查找法 在二分查找中，关键字与给定值之间的关系是：”大于”，”等于”，或“小于”- 基 于前缀长度的二分查找法意味着前缀长度”更短”或”更长”。举例说明其工作过程。 设有四个地址前缀p i = 0 ， 1 木。 田曰圜 图2 - 4 基于前缀长度的地址空间 首先从中问结点开始查找前缀长度为2 的哈希表。0 0 1 与0 0 前两位匹配，但并不是最 佳匹配。因此，继续查找前缀为3 的哈希表匹配成功但存在一个问题，例如查找1 1 1 。 在前缀长度为2 的哈希表中查找失败，返回至前缀长度为1 的哈希表中查找，没有找到。为了 解决这个问题。添加路由项，称为m a r k e r 。如图2 5 所示： 图2 5 添加的m a r k e r 但是，还可能存在回溯问题。例如，设p i = 1 ，p 2 = 0 0 ，p 3 = 1 1 1 ，m a r k e r = l l * ，查找1 1 0 。 4 ：塞型查兰堡主堡塞 图2 - 6 误导的m a r k e r 为了避免回溯，引入一个变量b m p 。当更长前缀部分匹配米败时，取出b m p 的值，不必回溯 因为变量b m p 记录了到目前为止最好的匹配前缀。 2 4 基于树型结构的路由查找技术 2 4 1 二叉t r i e 树( b i n a r yt r i et r e e ) 二叉t r i e 树是一棵每个结点都只有一个0 分支和( 或) 一个1 分支的树。常用来表示地 址前缀。结点的数据结构如图2 - 7 所示。 图2 7 二叉t r i e 树的结点结构 采用二叉t r i e 树，进行i p 地址最长匹配的晟有名的例子是b s d 内核。它的算法称为 r a d i xt r i e 。首先把整个转发表组织为二叉树的结构。结点代表转发表中的一条记录。在搜 索时，沿着匹配的路径逐渐从树根出发走向树叶。同时，记住最新经过的结点，直到路径走不 下去为止。从根到晟新的结点就是最长的地址前缀。 基于树型结构的路由查找容易受到前缀长度的影响。如果3 2 比特的i p 地址用一棵二叉 。i e 树存储，那么树的深度为3 2 最坏的情况下要查3 2 次。为了减少查询的时间，必须减小 树的深度。 2 4 2 路径压缩的t r i m 枷j ( p a t h - c o m p r e s s e dt r i et r e e ) 路径压缩的t r i e 树是对树的层次进行压缩，来减小树的深度。由于某些结点被删除，查 提过程中不是逐位对比，而是维护一个位变量指示下一个需要检查的比特位。为了恢复原有 信息，路径压缩t r i e 树需要保存地址前缀的比特串。结点数据结构如图2 - 8 所示。 5 6 p e 的设计研究 篆叫n e x 删t - h o p - p 廿 b i t - p o s i t i o n l e f l - p t rr i g h t - p t r 图2 - 8 路径压缩的t i r e 树的结点结构 2 4 3 多叉t r i e 树( m u i t i - b i tt r i et r e e ) 查找会引起一系列的访问存储器的操作。除了降低寻址深度还需考虑减少访问存储器的 次数。可以增加每次访问存储器所获取结点的信息数。 多叉t r i e 树是二叉t r i e 树一种最简单的变形。在多叉t r i e 树中二进制结点被替换成 k 一维的结点，k 为查找步宽。即每次查找需要检查的比特数。举例，如图2 - 9 所示。 oooo 图2 - 9 步宽为2 的多叉t r i e 树 显而易见，与二叉t r i e 树相比，同一层次上，