（计算机应用技术专业论文）Linux下Anycast路由协议的设计与实现(1).pdf

摘要 a n y c a s t 是i p v 6 中提出的一秘新型的网络服务，它在主机自动配 置、网络负载均衡等方面的应用都非常广泛。对a n y c a s t 路由协议进 行研究是确保a n y c a s t 服务能否实现的关键，a n y c a s t 路由协议的好 坏直接决定了a n y c a s t 服务的可用性和效率。 本文讨论了l i n u x 内核中a n y c a s t 路由协议的设计方案和实现技 术。系统大体上分为内核a n y c a s t 路由数据处理、a n y c a s t 映射表信 息的动态交换与更新、主机a n y c a s t 组成员信息管理三个部分。内核 a n y c a s t 路由数据处理部分的实现包括a n y c a s t 路由软件的设计和 a n v c a s t 路由过程中a n y c a s t 地址映射算法及映射表维护。在该部分， 系统增加了一个核心数据结构一一映射表，完成了a n y c a s t 地址到 u n i c a s t 地址的转换。通过把a n y c a s t 映射表信息交换系统设计成守 护进程，实现了内核映射表信息的动态更新和路由器问映射表信息的 交换。通过a n y c a s t 组成员之间的信息通信和用户介入控制的方式实 现了a n y c a s t 组成员的动态管理。通过采用全i p v 6 地址和兼容i p v 4 的i p v 6 地址两种地址进行了组管理、映射表信息交换和a n y c a s t 路 由以及基于h t t p 应用的服务测试，测试结果表明系统设计合理，可 以有效实现a n y c a s t 数据报的转发。 其次，论文在讨论了s p r 和m p r 路由特点的基础上提出了一种新 的动态的a n y c a s t 路由算法一d a r l b 算法。该算法根据网络拓扑及 链路状态信息，动态使用s p r 或m p r 路由，充分利用链路状态信息实现 路由的最优化。 总之，论文对a n y e a s t 路由及其实现技术进行了深入的研究，为 进一步探讨a n y c a s t 及相关应用提供科学的参考。 关键词软路由器，a n y c a s t 地址，映射表，s p r ，m p r a b s t r a c t a n y c a s ti s an e w 卿eo fn e t w o r ks e r v i c ei n i p v 6 a n y c a s tc a nb e u s e d w i d e l y i n m a n y f i e l d ss u c h a s d h c p ，l o a d - b a l a n c e db e t w e e n d i 觑r e 主1 tl i n l ( s 龇l ds oo n a n y c a s tr o u t i n g i sm ek e yp a r to fa n y c a s t s e r v i c e t h e u s a b i l i 妙a 1 1 de f f i c i e n c y o ft 1 e a n y c a s ts e r v i c el i e o nt 1 1 e q u a l i t yo fa n y c a s tr o u t i n gp r o t o c 0 1 t h i s p a p e r d i s c u s s e s m a i n l y t l l e d e s i g n a i l d i m p l e m e n t a t i o n o f a n y c a s tr o u t m gp r o t o c o l i nl i n u x t h ea 1 1 y c a s tr o u t i n gs y s t e mi n c l u d e s m r e ek e ys e c t i o n sw h i c ht l l e ya r et h es o ri m p l e m e n tt e c l l i l o l o g y o f a n y c a s tr o u t i n gd a t ap r o c e s s m g ，t i l ed y n 吼i cc h a l l 西n ga n du p d a t i n go f a n y c a s tr o u t i n gm 印姆b l e a n dt h e m a i l a g e m e n t o fh o s t a n y c a s t g r o u p _ n l e m b e r _ t h ep a p e rd i s c u s s e sm es o 盘i m p i e m e n tt e c h n o j o g yo f a n y c a s tr o u t i n g d a t a p r o c e s s i n g o nm e d e s i g n o f a n y c a s tr o u t m g s o r w a r ea n dm e m a pa l g o r i t l l mo fa n y c a s ta d d r e s s 踟1 dt 1 1 em a i n t e n a n c e o ft h em a pt a b l ei nt 1 1 ea n y c a s t r o u t i n gp r o c e s s i nm es e c t i o n ，an e w d a t a s 乜u c t u r e 一m a pt a b l ei s a d d e di n 也es y 3 t e m ，w h i c hc a nm a _ pa n v c a s t a d d r e s si n t ou n i c a s ta d d r e s s t h es y s t e mt h a ti m p l e m e m sm ed y n a m i c u p d a t i n go fm a pt a b l ei n f 0 h n a t i o ni nl i n u xk e m e la n dm ee x c h a l l g eo f m a p j a b l e i n f o n n a t i o na m o n gr o u t e r si si m p l e m e m e d b yd e s i g n i n g i ta sa d a e m o n p r o c e s s t o a c c o m p l i s h廿l e 舢l y c a s tg r o u pm a n a g e m ! e n t ， i n f o r m a t i o nc o m n m i c a t i o ni na n y c a s t 掣0 u pa n d o p e r a t i n gc o n f i g u r e f i l e i nu s e rc o n t r 0 1c o n s o l ea r ei m p l e m e m e d t h ed e s i 星皿o fa n y c a s tr o u t i n g p r o t o c o li sp r o v e dt ob en o to n l yr e a s o n a b l eb u ta l s of e a s i b l eb yt e s t i n g t h ea n y c a s t g r o u pm a n a g e m e m ，t 1 1 ee x c h a n g eo fm 印_ t a b l ei n f o m l a t i o n ， a n y c a s tr o u t i n ga 1 1 dt l l es e r v i c eb a s e do nh i m 印p l i c a t i o nw i t l l 恤ep u r e i p v 6a d d r e s sa n dt 1 1 ec o m p a t i b l ei p v 6a d d r e s s t h e n ，m ep a p e rd i s c u s s e s t h ek e y t e c h n o l o g i e so f m e s y s t e m a n di t si m p l e m e n t a tt l l es 锄et i m e ，t 1 1 ep 印e rb r i n g sf b r w a r dar l e wd y n 锄i ca n y c a s t r o u t i n ga l g o r i 妇一d a r i ，ba l g o r i 抛1b a s e do ns p ra r l d 田r t h e d a r l ba l g o r i m mi n t e 础st 1 1 em e r i t so ft 1 1 es p ra n dm p rb vm e i n f b r m a t i o n so fc o m p u t e rn e m o r k t o p o l o 霉r ya 1 1 dl i n k s t a t e i naw o r d ，恤ep 印e rd i s c u s s e sa n y c a s tr o u t i n ga n di t si m p l e m e n t p r o f o u n d l y i tm u s tp m v i d eas c i e n t i f i cr e f e r e n c ef o rt | l e 矗l n l r er e s e a r c h a 1 1 da p p l i c a t i o no f a n y c a s t k 置yw o r d ss o rr o u t e r a n y c a s ta d d r e s s ，m a p t a b l e ，s p r m p r l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的 学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在 论文中作了明确的说明。 作者签名 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学 位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容， 可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部 门规定送交学位论文。 作者签名 硕士学位论文第一章绪论 第一章绪论 i n t e r n e tp r o t o c o lv e r s i o n6 ( i p v 6 ) 是目前信息科学领域的研究热点。i p v 6 是i e t f ( i n t e r n e t 工程任务组) 继i p v 4 ( r f c 7 9 1 ) 后制定的用于取代i p v 4 的 新一代i n t e r n e t 协议”3 。随着网络技术的发展，在网络上出现了大量更高要求的 需求，即主机、应用或用户希望有这样的一种服务：有多个服务器可提供相同的服 务( 至少有一个) ，但它并不关心真正提供服务的是哪一个服务器。a n y c a s t 正是 为满足这种需求而提出的一种新型网络服务( r f c1 5 4 6 ) 。3 。1 9 9 3 年在文献 2 中 首次提出a n y c a s t 服务的概念，并通过客户定位最近服务器的事例阐述了需要 a n y c a s t 地址的主要动机。由于越来越多的应用需要a n y c a s t 服务，因此在i p v 6 中其被定义为一种标准服务模型。 在i p v 6 中定义了一种新的群集地址类型，即a n y c a s t 地址“。，它可以同时 分配给多个网络接口( 通常分布在不同节点上) 。a n y c a s t 地址是a n y c a s t 路由 的基础。a n y c a s t 路由为因特网提供了一个崭新的发展空间，使因特网有着更为 广阔的发展前景。同时，由于组管理协议是针对i p v 4 而提出的，所以a n y c a s t 路由的实现面临挑战，它要求对传统网络技术从底层进行根本性的变革以适应这 一新的发展方向0 3 。基于l i n u x 的a n y c a s t 路由的设计与实现这一课题，就是在 这一背景下提出的。 本章包括a n y c a s t 概述，课题的研究背景及现状，a n y c a s t 路由研究的重要 意义，最后对本文研究的主要内容进行了概述。 1 1 a n y c a s t 概述 随着更多的网络主机相连，网络服务需求己超过了网络的服务容量，并且网 络服务在降质。虽然其不影响一些经典的网络应用，比如电子邮件、文件传输等， 但是其对需要实时服务的应用产生了严重的影响，比如视频点播、i p 电话等。 为了提供足够的网络服务，必须增加些定量或定性的确定性i p 服务。 为了增强服务的可用性和改善网络的流量分布，通常应用的方法是在网络中 复制服务器。例如：在i n t e r n e t 中的w 删镜像服务器、视频点播、股票服务器、 计算服务器和代理服务器。复制服务器技术分为两类：本地复制和分布式复制”“。 本地复制主要采用服务器组群技术，这些服务器都在同一个子网内。分布式复制 是将服务器放置在不同的地理位置，通过i n t e r n e t 连接提供服务。如果客户端 需要定位合适的服务器，就必须扩充和增强客户端功能去完成定位工作。 在i n t e r n e t 上，可以采用一种新的服务模型a n y c a s t 来支持分布式服 硕士学位论文第一章绪论 务器复制。a n y c a s t 服务是指从一台主机向一组目的主机中的任何一台传输数据。 一组目的主机的地址是由一个a n y c a s t 地址表示，提供相同服务的不同服务器拥 有相同的a n y c a s t 地址。例如：多个w w w 镜像服务器可以共享一个a n y c a s t 地址， 为得到所需要的信息( 例如：天气情况、股票数据等) ，用户可以简单地采用 a n y c a s t 地址所对应虚拟主机名访问若干个主机的一个。图卜l 给出了a n y c a s t 服务的示意图，服务器1 、服务器2 、服务器3 具有相同的a n y c a s t 地址，客户 机1 、客户机2 要确定用服务器l 、2 、3 中的哪个服务器提供服务。在该事例中 采用最少跳数的策略，客户机l 选择服务器1 提供服务，而客户机2 选择服务器 2 提供服务”“。 1 9 9 3 年在文献 2 中首次提出a n y c a s t 服务的概念，并通过客户定位最近服 务器的事例阐述了需要a n y c a s t 地址的主要动机。a n y c a s t 是使源结点向一组能 提供相同服务的不同服务器传输数据，提供相同服务的不同服务器拥有相同的 a n y c a s t 地址，但一个a n y c a s t 信息总是被转发到一组服务器中的一个。正如文 献 2 中所描述的：a n y c a s t 报文总被转发至可服务于该a n y c a s t 地址的一组服 务器中的至少一台( 最好是一台) 的尽力而为的无状态服务。在i p v 6 中规定，这被 选择的一台服务器接口应该是按路由协议的距离量度计算的”最近”的一个接口。 由于越来越多的应用需要a n y c a s t 服务，因此在i p v 6 中其被定义为一种标准服 务模型”3 。 图卜l a n y c a s t 服务示意图 a n v c a s t 是一种非常有用的通信服务，在许多应用领域都有着不可替代的作 硕士学位论文第一章绪论 用。使用a n y c a s t 通信可以简化一些应用，比如，a n y c a s t 查询可以用来从一组 可用的服务器中定位台合适的服务器，这比通过m u l t i c a s t 查询极大地提高了 效率“1 。事实上，多个w e b 站点镜像可以共享一个a n y c a s t 地址，用户只需简单地 发送一个请求，就可以获 导相关信息( 如天气信息，证券报价等) 。在m u l t i c a s t 路 由中综合利用s h a r e d t r e e 路由与a n y c a s t 路由技术的优点，可以产生一种稳 定、高效的路由算法“1 。随着网络新应用、新服务的不断涌现，对它的需求会不 断增长。 1 2 课题的研究背景 12 1 研究原因及意义 虽然a n y c a s t 在许多应用领域起着非常重要的作用，但目前对它的研究才刚 刚起步，在许多方面还存在着制约这种服务的实施的问题，这些都需要研究人员 解决“1 。研究a n y c a s t 路由及其实现的主要原因有： ( 1 ) a n y c a s t 服务及相关技术日趋规范，越来越多的操作系统提供了对i p v 6 相关技术的支持。随着网络技术和i n t e r n e t 的迅速发展，i p v 4 暴露出越来越多 的缺点与局限，严重地制约了网络技术的进一步发展。因此，作为下一代因特网协 议的i p v 6 吸引许多网络研究者的目光。近年来，许多基于i p v 6 的研究成果和产 品相继问世i p v 6 已得到越来越多的网络操作系统和厂商的支持。如l i n u x 2 2 + 、w i n d o w s 2 0 0 0 及f r e e b s d 等都开始提供了对i p v 6 的相关实现，路由器生产 厂商如c i s c 0 ，t u n i p e r ，h i t a c h i 等都在自己的产品中增加对i p v 6 的支持“。，i p v 6 的地址为1 2 8 位，可以与i p v 4 地址兼容使用，r f c2 3 7 3 ”。详细介绍了其地址格式。 这些都为研究和应用a n y c a s t 服务奠定了基础。 ( 2 ) 在许多应用领域，a n y c a s t 成为最佳选择。i n t e r n e t 的规模成指数级的 增长，在1 9 e 9 年，每l o s 就有一台新的p c 连接到因特网上去。分布式服务面 临服务器严重超载，带宽浪费和延迟增加的问题。服务器复制和缓存的技术虽然 可以有效地改善服务的性能，但是关键的问题是客户机如何找到性能最好的服务 器? a n y c a s t 是解决此类问题的最好办法：在移动多播( m o b i l em u l t i c a s t ) 服务 中，a n y c a s t 路由技术被用来支持移动结点和外地结点本地结点之间的 m u l t i c a s t 通信，以减少端到端的延迟提高m u l t i c a s t 的效率：a n y c a s t 也被广泛 应用在最优服务器的选择和针对d n s 及类似服务提出的主机自动配置上，从一组 服务器中选择一台”最优”的服务器是a n y c a s t 最基本的功能：在主机的自动配 置上，比较典型的是用在域名服务器的解析，名字服务器不管距离远近，只要能够 完成名字的解析即可，有了a n y c a s t 服务，用户在进行d n s 解析时只要向全球的 硕士学位论文第一章绪论 某个代表d n s 的知名a n y c a s t 地址发送查询请求即可得到地址解析的结果，这样 可以简化客户机的配置，即使主机移动到一个新的网络也不用重新配置本地的 d n s 服务器的地址。a n y c a s t 通信还在提高网络资源的利用率，提供多媒体通信 的端到端q o s 保证上等多方面有其独特作用。另外，在分摊网络不同链路的负载 以及在动态条件下的军事和商业应用等方面都有非常重要的应用。 ( 3 ) 路由问题是a n y c a s t 服务最根本的问题，a n y c a s t 路由协议的好坏直接 决定a n y c a s t 服务的可用性和效率。随着a n y c a s t 在许多领域的广泛应用，研究 一种针对a n y c a s t 的高效的路由算法，尤显得非常重要。 综合上述，随着用户对网络服务要求的提高和网络技术的发展，对a n y c a s t 路由协议及其实现技术的研究，以提高网络的性能有非常重要意义，近年来，针对 于a n y c a s t 相关问题的研究引起学术界的广泛关注，许多文献“6 。8 论述了 a n y c a s t 路由协议，可见，a n y c a s t 及其实现技术是网络研究领域的重要方向之一 具有深入研究的价值。 122 研究现状 自从r f c1 5 4 6 “1 提出a n y c a s t 服务以来，网络研究者对它进行了大量的研究。 在r f c1 8 8 4 。1 中，决定从u n i c a s t 地址空间分配a n y c a s t 地址，a n y c a s t 地址采 用u n i c a s t 地址格式，r f c2 4 6 0 “1 把子网路由器定义为同一子网前缀所有路由器 的一个a n y c a s t 地址。 目前，研究a n y c a s t 服务模型主要从两个方面着手：基于网络层的a n y c a s t 服务和基于应用层的a n y c a s t 服务。在选择”最优”服务器时，如果选择的标 准依赖于网络的拓扑结构，例如路由器最小的跳数，最小的花费( 不同的路由器 可能有不同的花费) ：依赖于路由器路由协议的算法，这就是基于网络层a n y c a s 。 如果选择的标准依赖于服务器或者应用的尺度，如可以获得的容量，可以测量的 响应时间，以及激活连接的数量等就是基于应用层的a n y c a s t 。两者关键的区别 在于网络层a n y c a s t 仅仅依靠网络自身来选择合适的服务器；而应用层a n y c a s t 则依赖于外部的实体来选择连接性能最好的服务器。仅仅依靠网络自身来选择服 务器的问题是客户机不一定能选择到性能最好的服务器，而应用层的a n y c a s t 则 能带来更多的灵活性和可规划性。虽然网络层a n y c a s t 实现简单，但是需要修改 路由器的配置，在选择标准方面缺乏灵活性；丽应用层a n y c a s t 选择的标准灵活， 不需要修改路由器的配置，但是基于应用层的a n y c a s t 需要周期性的收集信息。 文献 9 1 7 探讨了a n y c a s t 在应用层的实现。文献 1 0 提出了一个a n y c a s t 的 可扩展的体系结构g i a 。g i a 定义了一种特殊结构的独立a n y c a s t 地址空间，这种 a n y c a s t 地址不同于i p v 6 的规定，因此，这种结构在i p v 6 中无法使用。文献 1 0 1 6 ，2 3 ，2 7 分别讨论了a n y c a s t 路由算法。文献 1 9 讨论了a n y c a s t 地址与 4 硕士学位论文第一章绪论 u m c a s t 地址之间映射。文献 2 4 ，2 9 讨论了i pa n y c a s t 在负载分配和服务器选 择方面的应用。 如何在i p v 6 中实现上述讨论的a n y c a s t 服务是当今网络研究领域另一大热 点。文献 1 7 提出了一种在应用层实现a n y c a s t 服务的协议。文中提出两种 a n y c a s t 实现最近服务器的方式：一种是利用客户端初始化一个有一定有效范围 的t t l 字段的令牌来查找最近的a n y c a s t 服务器；另一种方法则通过计算从客户 端到服务器的跳数( h o p ) 来决定最近的a n y c a s t 服务器。 实现a n y c a s t 服务的另一个难点是如何实现a n y c a s t 地址到服务器的 u n i c a s t 地址的映射。目前主要的有两种方式：s i o ( s o u r c ei d e n t i f i c a t i o n o p t i o n ) 方式“”及a a m ( a n y c a s ta d d r e s sm a p p e r ) 方式“。s i o 方式使用了一 个新的i p 选项一s o u r c ei d e n t i f i c a t i o no p t i o n ，该选项利用了i p 包扩展头部 的第二目的地址字段。通信双方先通过t c p3 一w a y h a n d s h a k e 方式建立连接，当 i p 包的目的地址为a n y c a s t 地址时，它先获得最近的一个a n y c a s t 服务器的 u n i c a s t 地址，用该u n i c a s t 地址替换原a n y c a s t 目的地址并把i p 包发送出去。 a a m 机制主要利用i c m pe c h or e q u e s t i c m pe c r e p l y 包来实现a n y c a s t 到 u n i c a s t 地址的映射，首先，请求端发送一个i c m pe c h or e q u e s t 至a n y c a s t 地 址m ，当服务器收到这个请求包时，就返回一个源地址为它的u n i c a s t 地址b 的 i c m pe c h 0r e p l y 信息，当请求端收到这个响应包时，就在m 与b 之间建立了一种 映射关系，然后，发送方就用该u n i c a s t 地址与a n y c a s t 服务请求端建立连接并 进行通信。但目前，还没有完整实现a n y c a s t 路由协议的研究成果。本文主要研 究在l i n u x 内核中a n y c a s t 路由协议的实现技术。 1 3 研究内容与本文所做的工作 使i p v 6 网络能够提供a n y c a s t 服务是当今网络研究领域的主要课题，本课题 的主要目标是研究l i n u x 内核中a n y c a s t 路由协议的实现技术及一种动态的 a n y c a s t 路由算法，分析设计a n y c a s t 地址与u n i c a s t 地址的映射技术，a n y c a s t 组管理技术及路由器间a n y c a s t 信息交换技术，同时，研究链路态信息和网络拓 扑结构对a n y c a s t 路由的影响，优化a n y c a s t 路由算法。主要研究内容包括： a n y c a s t 地址映射技术，路由器之间映射表信息的交换技术，a n y c a s t 组成员管 理，动态的a n y c a s t 路由算法等。针对以上研究内容，本文主要在以下几个方面 进行了深入研究： 1 ) a n y c a s t 路由协议的实现过程中，有关a n y c a s t 地址映射技术的研究。 分析了当前两种主要a n y c a s t 地址映射技术一一a a m 和s i o 。a a m 方式增加了路 由器间信息交换的次数，并且存在由于网络错误，使得a n y c a s t 地址转换为u n i c a 硕士学位论文第一章绪论 一s t 地址失败的可能。而s i o 技术增加了一个新的i p 字段，这就要求对系统的原 处理过程作较大的改动。因此，本文提出了一种新的a n y c a s t 地址映射技术，即采 用映射表。这种方法实现简单、方便，对操作系统内核的其它部分不作任何改动， 就可实现a n y c a s t 地址到u n i c a s t 地址转换，实践证明这种方式不仅最大限度地 降低了开发成本、而且减少路由器之间数据包交换的次数，极大地提高了系统的 稳定性和可靠性。 2 ) 路由器之间映射表信息的交换技术的研究。映射表是为实现a n y c a s t 路 由协议而引入的一种新的数据结构，如何在路由之间实现映射表信息的交换，以 确保映射表的正确有效是必须解决的课题。针对路由器和映射表的特点，系统采 用一种类r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 协议的技术来实现映射表的动态 更新和交换，从测试结果可以看出，这种技术能根据a n y c a s t 组成员及网络拓扑 的变化及时地更新和扩散网络映射表的信息。 3 ) a n y c a s t 组成员管理的研究。a n y c a s t 服务可以在具有相同a n y c a s t 地 址的多个a n y c a s t 服务器中选择至少一个( 最好是一个) ，这些a n y c a s t 组成员可 以分布在网络的任何位置。因而，a n y c a s t 组成员的管理不同于m u l t i c a s t 的组 管理。一般地，m u l t i c a s t 的组成员管理一般在内核实现，但在目前的情况下，要 在内核实现a n y c a s t 组成员的管理并不可行，本系统首次提出在用户态实现 a n y c a s t 组成员的管理，使得用户可以方便地对a n y c a s t 组成员进行管理和维护。 测试结果表明该方法较好的解决了a n y c a s t 组成员管理的问题。 4 ) 动态的a n y c a s t 路由算法的研究。由于a n y c a s t 是基于i p v 6 的新的通信 模式，对a n y c a s t 路由算法的研究还处于起步阶段。目前的路由算法大多要么采 用s p r 方式，要么采用m p r 方式，这两种方法均具有各自的优缺点。为充分利用这 种方式的优点，避免其缺点，本文提出了一种基于负载均衡的动态采用这两种方 式的瓶的路由算法一d a r l b 算法。 本文所做的工作主要有： 1 ) l i n u x 下a n y c a s t 路由协议的设计与实现 如前所述，a n y c a s t 是i p v 6 新增的非常有用的服务，在许多领域都发挥着重 要的作用。主要表现在最优服务器的选择、主机自动配置及其它的商业和军事应 用上。随着网络技术的发展，对它的新需求还在不断地涌现。但作为一种全新的 网络服务，对它的研究也还处于起步阶段。因此，如何在网络系统中实现这种高效 的a n y c a s t 服务，显得尤其重要和紧迫。 由于l i n u x 开放源代码，人们可以自己对内核进行配置和重编译，而不必依 赖路由器提供商，因此，l i n u x 成为配置软路由器的的首选操作系统。目前，有 许多基于l i n u x 的商品化的路由器软件，如中科院软件所开发出的基于l i n u x 的 硕j = 学位论文第一章绪论 嵌入式广域网路由器。”和z e b r a 公司开发的z e b r a 路由软件“”等。要在l i n u x 操作系统中实现a n y c a s t 服务，必顽先在l i n u x 操作系统中实现a n y c a s t 路由， 这便是本课题的主要目标。 2 ) 一种动态的a n y c a s t 路由算法一d a r l b 算法 研究出种高效的a n y c a s t 路由算法，可以大大提高a n y c a s t 服务的性能和 效率。因此，在论文的第四部分提出了一种基于负载均衡的动态路由的算法 一一d a r l b 算法。 1 4 论文的组织 论文正文全文共分五章： 第一章绪论。这一章主要介绍a n y c a s t 服务及其特点，研究a n y c a s t 路由的 原因、意义及现状，并阐述了课题研究的主要内容和本文所做的工作。 第二章a n y c a s t 路由系统的总体设计方案。本章首先介绍了l i n u x 内核中 i p 层路由实现机制、l i n u x 内核中与i p 路由相关的主要数据结构及a n y c a s t 协 议的过程描述，接着阐述系统实际采用的设计方案，以及系统的开发与运行环境。 第三章l i n u x 下a n y c a s t 路由协议的设计与实现。这一章首先介绍了当今 两种主要的a n y c a s t 地址映射方法一一a a m 方式和s i o 方式及l i n u x 内核i p 层 路由实现机制，接着论述了目前软路由器的研究现状，通过对a a m 和s i o 的分析， 提出一种新的a n y c a s t 地址映射方法一映射表。然后从内核a n y c a s t 路由数据 处理、a n v c a s t 路由映射表信息的动态交换与更新、主机a n y c a s t 组成员信息管 理等三个部分详细论述了系统的设计与实现。同时，这一章还介绍了系统设计与 实现所采用的一些关键技术及其具体实现。其中包括数据包截获技术、a n y c a s t 地址判另u 技术、a n y c a s t 地址映射技术等关键技术。 第四章一种动态的基于负载均衡的a n y c a s t 路由算法。这一章主要介绍了 一种结合了s p r 和m p r 路由方式的a n y c a s t 路由算法一d a r l b 算法。这种算法 根据链路状态信息在s p r 及m p r 两种路由方式之间进行更换，及时选择一种高效 的路由方式。 第五章结束语。对所做的研究工作进行了总结，并阐述了将来进一步的研 究工作。 硕士学位论文第二章a n y c a s t 软路由器总体设计方案 第二章a n y c a s t 软路由器的总体设计方案 一般来院，路由器都包括四个部分：输入部分、输出部分、交换结构和路由 处理部分，这些功能用软件或硬件实现“。软路由器具有快速、廉价、高效的特 点，灵活性和性能都符合高性能路由器的要求，目前，已得到广泛的应用。许多 大公司，如3 c o m 、6 w i n d 、z e b r a 等都研制了支持i p v 6 的路由器软件，有的已经 实现了m u l t i c a s t 路由和对q o s 的支持。设计一个基于l i n u x 的稳定、高效且支 持a n y c a s t 路由的软路由器是本课题的主要目标之一。本章首先介绍了l i n u x 内核中i p 层路由实现机制；接着阐述了a n y c a s t 路由协议系统的设计方案；最 后介绍了系统的开发与运行环境。 21l in u x 内核中l p 层路由实现机制 211j p 层路由实现过程 在l i n u x 系统中，发送数据包和接收数据包的处理过程是不同的。图2 1 和图2 2 分别给出了l l n u x 系统处理发送数据和接收数据两种不同的处理机制。 接收数据是针对于从系统外部接收到的数据包，在i p 层的处理过程是：通过内核 的i p 6r o u t ei n p u t ( ) 函数的调用，获得路由表的入口，通过该入口所指明的 下跳地址，如果需要将包转发出去则转发；如果是给本机的数据包，则传给上 层相应函数来处理。发送数据是针对于从本机出发的数据包，在i p 层路由时， 通过内核的i p 6 一r o u t e o u t p u t ( ) 函数来查找路由表的入口，获得相应路由信息， 然后将数据包发往相应的主机或路由器。 对应地，在l i n u x 内核中，路由过程由接收路由和发送路由两部分组成。i p 路由函数决定了将预定的有指定i p 地址的i p v 6 包送到哪里。在传送i p v 6 包时， 可能有多种选择。这些路由信息存放在两个数据库中，即f i b ( f o r w a r d i n g i n f o r m a t i o nb a s e ) 和路由缓存表( r t c a c h e ) ，其中最重要的一个是f i b 。它包 含对当前系统当前时间可得到的所有i p 路由。路由缓存则用来快速找到目的i p 的路由。和其它的缓存一样，它只包含常用的路由，它的内容来自f i b 。 f i b 表中有一个f i b z o n e ) 结构，它用来描述每个i p 子网。h a s h 索引指 向这些结构，它来源于i p 子网掩码。所有通向同一子网的路由由f i b n o d e ) 和 f i bi n f o ) 结构来描述。如果通向同一子网有多个路由，则每个路由要使用一 个不同的网关。路由的优劣用【n e t r i c 结构来测量。e t r i c 越大，路由越差。 而路由缓存表中有一个指向r t a b l e 数据结构链的指针。r t a b l e 数据结构中有一 个u s e & e ee o u n t 字段，在每次查找路由时增加，它是r t a b l e 项在h a s h 链中排 硕士学位论文第二章a n y c a s t 软路由器总体设计方案 序和是否将之从h a s h 链中删除的依据畸1 。 系统路由时，先到路由缓存中查找表项，如果能够查找到，那么就直接将对 应的一项取出作为路由的规则；如果不能查找到，那么就到f i b 中根据规则换算 出来，并且在路由缓存中添加项路由信息。 图2 1 接收数据处理 图2 2 发送数据处理 硕士学位论文第二章a n y c a s t 软路由器总体设计方案 2 1 2 与l p 路由相关的主要数据结构 在l i n u x 内核网络部分，可分为硬件层数据链路层、i p 层、i n e ts o c k e t 层和b s ds o c k e t 层四个部分。i p 路由过程就发生在数据包从i n e ts o c k e t 层到 i p 层的过程中，如图2 3 所示，在这里，发送数据时，根据发送数据的目的地址确 定需要使用的网络设备接口和下一个需要传送到的机器地址；接收数据时，则在 i p 层判断该数据包是要发送给上一层协议，还是需要做一个i p 转发，将数据传递 给下一个机器。为了节省时间、提高效率，在l i n u x 内核中，数据的传递是通过 指针移位来实现的，而把数据放入缓存，尽量减少内存到内存的拷贝操作。这个过 程主要是通过数据结构s k _ b u f f 来完成的。结构s k j u f f 组织成为带头结点 的双向循环链表，利用指针可以存取链表中所有的数据，每个结点使用指针 h e a d 、d a t a 、t a i l 、e n d 等实现对内存的访问，如图2 4 所示。 厂 图2 3l i n u x 网络协议栈示意 图2 4s k _ b u f f 链表结构 另外，结构d 钒一e n t r y ( ) 、结构r t a b l e 及结构s 。c k ) 在数据传递和路由 过程中也起着非常重要的作用。 0 硕士学位论文 第二章a n y c a s t 软路由器总体设汁方案 2 2 设计方案 2 21a n v c a s t 路由协议的实现过程描述 开始 r | 0 p ( 娃教l 是苔为l 结束* 一 图2 5a n y c a st 协议处理过程描述 a n y c a s t 路由是指向提供同一服务的所有服务器都能识别的通用地址 ( a n y c a s t 地址) 发送i p 分组，路由系统将该分组送至最近的服务器。例如，利 用a n y c a s t 可以访问离用户最近的d n s 服务器和文件服务器等。a n y c a s t 路由过 程可描述如下： ( 1 ) 客户主机发起a n y c a s t 服务请求，将请求发送给路由器； ( 2 )路由器根据客户主机所请求的a n y c a s t 地址，到映射表中查找与该 a n v c a s t 地址对应的的最少p 数的下一跳路由器地址，这有三种情况： 如果没有找到对应的a n y c a s t 地址，则对数据包的目的地址不作处 理，直接查找路由表： 如果有，则判断h o p 数是否为1 ， 专人一 毫 硕士学位论文 第二章a n y c a s t 软路由器总体殴计方案 若为l ，则用对应于a n y c a s t 地址的服务器地址替换该项 a n y c a s t 地址，执行3 ) 、5 ) 步； 若不为l ，则用下一跳路由器地址替换a n y c a s t 地址，执行( 3 ) 、 ( 4 ) 步； 如果有多条符合条件的路径，则随机选取一条； ( 3 ) 利用替换后的目的地址查找路由表； ( 4 ) 查找路由表以后，再把目的地址更换为原目的地址，即a n y c a s t 地址： 重复第( 2 ) 步，直至找到至目标服务器的最后一个路由器： ( 5 ) 重建数据包的校验和。 该过程描述如图2 5 所示。 222 系统采用的技术方案 综合前匿所述，要实现a n y c a s t 路由，首先就得进行a n y c a s t 地址到u n i c a s t 地址的转换，前面讨论了两种方法，即a a m 和s i o 。这两种方式实际上只是在开始 进行了一次a n y c a s t 地址至u n i c a s t 地址的替换，然后就是利用替换后的 u n i c a s t 地址进行路由。本系统的实现过程中，提出了采用映射表的方法来进行 a n y c a s t 地址至u n i c a s t 地址的转换。因此，为了存储映射记录，在l i n u x 内核 中设计一个数据结构一映射表。为了与l i n u x 路由保持一致，选择在l i n u x 内 核中的i p 层实现映射表的查找，并完成a n y c a s t 路由。 同时，要保证映射表的信息及时、有效，就必须完成映射表信息动态交换，这 个过程类似于r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 协议的处理。因此，在应用 层以守护进程方式实现这个功能。 鉴于a n y c a s t 服务的研究现状，结合当前l i n u