（通信与信息系统专业论文）基于多线程机制的分布式交换系统中rip协议的分析和实现.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 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 o l ，路由信息协议) 协议作为简单实用的路由协议， 具有较低的带宽消耗，易于管理和维护等优点，广泛应用于中小型网络中。目前，众 多网络设备供应商基于v x w o r k s 系统对r i p 协议进行了分析和支持，而v x w o r k s 系统 任务之间共享内存和其它资源，容易造成数据的安全性和可靠性面临威胁。同时 v x w o r k s 系统是收费系统，增加了设备供应商和网络运营商的成本。而l i n u x 系统内 存独立，线程间数据共享，可靠性高，而且具有开源性和免费性，因此在l i n u x 平台 上对r i p 路由协议进行开发成为发展趋势。同时，为了提高r i p 协议的可靠性，在分 布式交换系统下实现r i p 协议也势在必行。 本课题在某通信公司的预研项目“r i p 路由协议的多线程分析和实现”基础上开展。 笔者参与该项目研发的整个过程，从总体方案设计、详细设计文档撰写、部分模块代 码编写、系统测试到预研报告撰写。通过项目研发，对r i p 路由协议进行了深入研究， 结合分布式交换系统和多线程机制，完成了r i p 路由协议的设计、实现、测试与分析。 通过分析r i p 路由协议目前的实现方案，阐明了在l i n u x 下采用多线程机制实现r i p 路由协议的优点。同时在分布式交换系统下，给出了一种支持分布式的r i p 路由协议 的多线程实现方案。 本文首先以r f c l 0 5 8 和r f c 2 4 5 3 为基础，对r i p 路由协议进行了分析，介绍了 r i p 路由协议的工作算法、报文格式和运行机制。其次，结合分布式交换系统架构的 特点，研究了协议对分布式的支持，提出了r i p 协议的功能需求，对r i p 协议进行总 体设计和模块划分，并结合多线程技术，给出多线程实现方案和其运行机制。然后， 在总体设计和模块划分的前提下，将r i p 协议分为两大模块进行详细分析，通过流程 图形式予以实现，并给出动态运行的交互信息。最后对设计系统的功能需求进行了理 论分析，并在实际环境中对系统功能进行了测试与验证，同时进行了压力测试。分析 测试结果表明，本论文设计的基于c 语言的分布式交换系统中的r i p 协议多线程实现 方案可以有效的在高端分布式交换机上可靠的动态学习路由和处理外部事件。 关键词：r i p 路由协议；分布式交换系统；多线程机制；高可靠性 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t a sas i m p l ea n dp r a c t i c a lr o u t i n gp r o t o c o l ，r i pp r o t o c o li sw i d e l yu s e di ns m a l la n d m e d i u m - s i z e dn e t w o r k sb e c a u s eo fl o w e rb a n d w i d t hc o n s u m p t i o n ，e a s eo fm a n a g e m e n ta n d m a i n t e n a n c e c u r r e n t l y , r i pr o u t i n gp r o t o c o lh a sb e e na n a l y z e da n ds u p p o r t e db ym a n y n e t w o r ke q u i p m e n tp r o v i d e r sb a s e do nv x w o r k ss y s t e m h o w e v e rt h em e m o r ya n do t h e r r e s o u r c e sa r es h a r e db e t w e e na l lt h et a s k si nv x w o r k ss y s t e m ，c a u s i n gt h et h r e a to fs a f e t y a n dr e l i a b i l i t yo ft h ed a t ae a s i l y m e a n w h i l e ，a sc h a r g es y s t e m ，v x w o r k ss y s t e mi n c r e a s e s t h ec o s to ft h ee q u i p m e n ts u p p l i e r sa n dn e t w o r ko p e r a t o r s s u p p o r t i n gf o ri n d e p e n d e n to f m e m o r ya n ds h a r i n gm e m o r yb e t w e e nt h r e a d s ，l i n u xs y s t e mh a sh i g hr e l i a b i l i t y m o r e i m p o r t a n t l y , l i n u x i s o p e ns o u r c ea n df r e e ， s oi tb e c o m e st h e d e v e l o p m e n tt r e n d t o i m p l e m e n tr i pr o u t i n gp r o t o c o lo nt h el i n u xs y s t e m m e a n w h i l e ，i no r d e rt oi m p r o v et h e r e l i a b i l i t y , i m p l e m e n t a t i o no f t h er i pp r o t o c o li nd i s t r i b u t e ds w i t c h i n gs y s t e mi si m p e r a t i v e t h i sa r t i c l eh a sb e e nc a r r i e do u tb a s i n go nap r e - r e s e a r c hp r o j e c to fs o m e c o m m u n i c a t i o nc o m p a n yw h i c hi sa b o u t a n a l y s i sa n di m p l e m e n t a t i o no fr i pp r o t o c o lb a s e d 0 1m u l t i t h r e a d e dm e c h a n i s m ”t h ea u t h o rp a r t i c i p a t e di nt h ee n t i r ep r o c e s so ft h ep r o je c t d e v e l o p m e n t ，f r o mt h eo v e r a l ld e s i g n ，w r i t i n gd e t a i l e dd e s i g nd o c u m e n t s ，w r i t i n gc o d eo f s o m em o d u l e s ，t e s t i n gt h es y s t e mt ow r i t i n gp r e d i c t a b l er e p o r t t h r o u g ht h ep r o j e c ts t u d y a n dd e v e l o p m e n t ，t h ea u t h o rh a sd e e p l yr e s e a r c h e do nt h er i pp r o t o c o l ，a n dt h e nc o m p l e t e d t h ed e s i g n , i m p l e m e n t a t i o n ，t e s t i n ga n da n a l y s i sc o m b i n i n g 谢ld i s t r i b u t e ds w i t c h i n g s y s t e ma n dm u l t i t h r e a d i n gm e c h a n i s m c o m p a r i n gw i t hc u r r e n ts c h e m eo fi m p l e m e n t a t i o n a b o u tr i pp r o t o c o l ，t h i sa r t i c l ee x p l a i n sc l e a r l yt h eb e n e f i t st oc a l t yo u tr i pp r o t o c o lo nt h e m u l t i t h r e a d e dm e c h a n i s mi nl i n u xs y s t e m t h e na c c o r d i n gt od i s t r i b u t e ds w i t c h i n gs y s t e m ， t h i sa r t i c l eb r i n g sf o r w a r dak i n do fs c h e m eo fi m p l e m e n t i n gr i pp r o t o c o li nd i s t r i b u t e d s w i t c h i n gs y s t e m f i r s t l y , r i pp r o t o c o li sa n a l y z e db a s e do nr f c10 5 8a n dr f c 2 4 5 3 a n dt h e nt h e p r o t o c o la l g o r i t h m ，m e s s a g ef o r m a t ，a n do p e r a t i o nm e c h a n i s ma r ei n 仃o d u c e d s e c o n d l y , s u p p o r t i n gf o rd i s t r i b u t e ds w i t c h i n gs y s t e m ，t h i sa r t i c l ep r o v i d e st h ef u n c t i o n a lr e q u i r e m e n t a n de s t a b l i s h e st h e o v e r a l ld e s i g na n dm o d u l ep a r t i t i o n m e a n w h i l e ，c o m b i n e dw i t ht h e m u l t i t h r e a d i n gt e c h n o l o g y ，i tg i v e st h em u l t i t h r e a ds c h e m ea n di t so p e r m i o nm e c h a n i s m t h e nd i v i d e di n t ot w om o d u l e s ，t h er i pp r o t o c o li sa n a l y z e di nd e t a i lt h r o u g hf l o wc h a r t f o r m ，a n dg i v e dt h ed y n a m i ci n t e r a c t i v ei n f o r m a t i o n f i n a l l y , t h ea r t i c l ec a r r i e so u ta t h e o r e t i c a la n a l y s i so ft h ef u n c t i o n sa n dp e r f o r m a n c eo ft h i sd e s i g n e ds y s t e m ，a n dt h e nt e s t s a n dv e r i f i e st h e mi nt h ea c t u a le n v i r o n m e n t t h ea n a l y s i so ft e s tr e s u l t ss h o wt h a tt h e m u l t i t h r e a d e dd e s i g no fr i pp r o t o c o li nd i s t r i b u t e ds w i t c h i n gs y s t e mb a s e do ncl a n g u a g e 西南交通大学硕士研究生学位论文 第1 i i 页 c a 1b ee f f e c t i v ea n dr e l i a b l et od y n a m i c a l l yl e a r nr o u t i n ga n dd e a lw i t he x t e r n a le v e n t si n h i g h e n dd i s t r i b u t e ds w i t c h e s k e yw o r d s ：r i pp r o t o c o l ；d i s t r i b u t e ds w i t c h i n gs y s t e m ；m u l t i - t h r e a d e dm e c h a n i s m ；h i g h a v a i l a b i l i t y 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 路由协议作为t c p i p ( t r a n s m i s s i o nc o n t r o lp r o t o c o l i n t e r n e tp r o t o c o l ，网络通讯协 议) 协议族中的重要组成部分，其选路的优劣直接影响到整个互联网的性能。在众多 的路由协议中，r i p 协议由于带宽消耗小，易于管理和维护，目前仍在大量使用中。文 章首先介绍了课题的研究背景和意义，然后给出了当前r i p 协议和国内外研究现状， 指出本文中r i p 协议实现的优势，最后对论文的内容和章节安排进行了介绍。 1 1 研究背景和意义 多线程机制可以提高应用程序的并行能力，降低调度过程中过多资源的消耗，充 分利用系统资源，目前已经得到大量运用。同时，为了提高协议的可靠性，保证业务 能够不间断运行，网络协议需要对分布式交换系统进行支持。因此，采用多线程机制， 在分布式交换系统中对r i p 路由协议进行相应的分析和实现具有重要的实际和参考意 义。 1 1 1r i p 协议研究背景 随着计算机网络的快速发展以及三网融合的逐步推进，网络规模和网络通信量正 在爆发性的增长。同时网络环境也日趋复杂，呈现出结构繁多，路径复杂等特点，以 往那种结构简单，管理方式单一的信息网络早已不能满足信息量的要求。 为了在全球范围内对网络进行有效的管理，提高网络的透明性和层次性，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 r n e t 分割为不同的 单一的自治系统【l 】，并在r f c l 9 3 0 中给出其在网络中的应用场景。一个自治系统是在 一个管理技术部门下，使用同一种路由协议选路，进行网络通信的所有的网络设备。 这样，因特网就被划分为很多个单一的自治系统，自治系统之间相互协作，实现了因 特网的互联，同时提高了网络的吞吐量。在一个自治系统内部通信，只需要知道本系 统内部的网络如何选路，使用的是内部网关协议( i n t e r i o rg a t e w a yp r o t o c o l s ，i g p ) ， 如r i p 、o s p f ( o p e ns h o r t e s tp a t hf i r s t ，开放式最短路径优先) 、i s i s ( i n t e r m e d i a t es y s t e m t oi n t e r m e d i a t es y s t e m ，中间系统到中间系统) 等。如果计算机需要与本地自治系统外部的 网络进行通信，则需要使用外部网关协议( e x t e r i 0 1 g a t e w a yp r o t o c o l ，e g p ) ，如b g p ( b o r d e rg a t e w a yp r o t o c o l ，边界网关协议) 。 r i p 路由协议是比较早的内部网关协议，分为r i p 1 和r i p 2 两个版本。1 9 8 8 年 i e t f 组织在r f c1 0 5 8 中提出了r i p 1 标准，给出了r i p 1 报文的格式以及报文接收发 送的机制。由于r i p 1 标准提出的较早，设计的比较简单，伴随着子网的出现，发现 r i p 协议已经不能满足社会需求。i e t f 实时的在r f c l 3 8 8 中推出了r i p 2 版本，并且 西南交通大学硕士研究生学位论文第2 页 在r f c l 7 2 3 和2 4 5 3 中对r i p 路由协议进行了完善，不仅对于子网进行了支持，同时 还提供了认证安全机制，保证协议可靠安全的运行。 伴随着网络规模的不断扩大和网络通信量的急剧增加，o s p f 、i s i s 等i g p 路由 协议相继出现和逐步成熟。o s p f 、i s i s 均为基于链路状态的路由协议，收敛速度快， 不会形成路由环路，尤其适合在大中型网络中使用。与r i p 路由协议相比，o s p f 、i s i s 等i g p 协议更能适应当前复杂的网络环境，然而在中小型网络中，尤其在校园网、小 型企业网中，r i p 路由协议具有较低的带宽消耗，易于管理和维护【2 ，3 】，同时大多数的 网络通信发生在一个内部局限的网络，因此目前r i p 协议在这种结构简单，规模不大 的网络环境中仍是广泛使用的内部网关协议。 1 1 2 分布式交换机研究背景 交换机为网络设备的重要组成部分，其性能的优劣直接影响到整个网络环境的带 宽性能，根据网络设计性能的不同，交换机分为接入层交换机、汇聚层交换机和核心 层交换机，其中核心层交换机和汇聚层交换机一般为三层交换机。 三层交换机工作在网络层，相对于二层交换机，其性能更加强大，处理效率线速 化。能够识别口地址信息，如果接收到的数据报文的目的地址是本地网络，则不处理， 否则将该数据报文转发出去，实现不同网段间数据交换，具有一定的路由功能。因此， 三层交换机既能作为二层交换机使用，又可以作为路由器使用。为了提供可靠性的服 务，三层交换机一般采用分布式架构，即设计为分布式交换机。 分布式交换机是相对于集中式交换机而言的，又称分布式以太网交换机，主要用 于企业网和电信城域网的核心层和汇聚层，具有模块化的架构、高可靠性、高扩展性 以及高速率等特点，是目前设备供应商和电信运行商研究和维护的核心设备。分布式 交换机将主控板上的转发芯片分离出来，承担流量的跨板转发，设备的转发性能提高， 同时也降低了主控板的负担。为了提高了设备的可靠性，往往存在多块主控板、接口 板，当其中某一块板发生故障时，相应的替代板接替故障板的工作，保证业务可靠的 不间断运行，减少了各个板之间的相互制约。用户可以根据自己的实际需求，在不影 响其它业务版正常工作的情况下，实时改变交换机的转发速率、路由学习效率以及板 件接口或槽的扩展。 因此，在高端的路由器和交换机上，r i p 路由协议不仅需要满足路由学习性能的要 求，更需要对分布式交换系统架构进行支持，以保证r i p 路由协议在骨干网中可靠的 运行。 1 1 3 多线程和分布式系统中r i p 协议的研究意义 多线程机制，即通过将静态的程序合理划分为多个模块( 线程) ，使其并行运行时 相互协作，充分利用系统资源，共同完成单一进程流的任务，提高程序的执行效率。 西南交通大学硕士研究生学位论文第3 页 与多线程对应的为多进程机制，即通过多个进程并行执行完成系统功能。由于进程间 内存不能共享，需要通过进程间通信完成消息交互。因此，在多线程和多进程机制下， 采用模块化的思想，将功能相对独立的模块划分为单个进程，与其他模块通过进程间 通信的方式实现交互，完成整个系统的功能。在模块内部，按照一定的原则，将单进 程再划分为多个线程，以线程为调度的最小单位，线程间通过共享内存和资源的方式 减少调度消耗，提高并行执行性。尤其在硬件资源异常丰富的今天，即多核多处理器 的系统上，采用多线程技术，已成为必然要求。 本课题在详细研究r i p 路由协议的基础上，指出当前市场上各大公司现有r i p 协 议的实现方案和国内外文献对于协议的研究，并基于某通信公司r i p 路由协议的开发 项目，在分布式交换系统架构下采用多线程机制设计并实现了r i p 路由协议，从而使 运行r i p 协议在满足性能情况下，更加可靠、经济，这对于整个网络设备的研究和发 展具有重要的参考意义。 1 2 国内外研究现状 r i p 路由协议作为简单实用的应用层协议，距离现在提出已经3 0 多年，然而由于 其带宽消耗小，易于管理和维护，仍然在中小型网络中广泛使用，对于其研究和实现 一直都在继续。 r i p 协议提出时，只是为了完成小型网络中路由的动态学习，减少人工对于网络的 干预。它使用u d p 报文通过定时更新机制进行报文发送，使用的端口号为5 2 0 ，以广 播报文的形式完成动态路由的学习。它使用了一种比较简单的度量方式“跳数 计算 网络成本，取值范围为1 1 5 ，1 6 即表示该网络不可达，这也就决定了r i p 协议的网络 规模不能过大。伴随着网络规模的扩大和子网的出现，r i p 协议不能满足稍微复杂的环 境需求，i e t f 提出了r i p 2 版本，对r i p 协议进行了增强，使之支持不连续子网以及 认证等功能，同时为了尽量降低广播风暴，r i p 2 开始支持组播，只有加入组播组的 r i p 路由器才能进行报文处理。思科公司也提出了r i p 协议的增强版本i g r p ( i n t e r i o r g a t e w a yr o u t i n gp r o t o c 0 1 ) 协议，引入了自治系统的概念，对度量值属性进行了适配性 的修改，扩大了网络的规模，弥补了r i p 协议的缺陷，当时大多数的互联网组织也都 采用了i g r p 协议替代r i p 协议。然而由于该协议为思科公司私有，同时和r i p 协议 性能差距不大，伴随着网络通信量的急剧增加，基本已经没有产品对其进行支持。 目前，众多网络设备供应商在相应的平台上对r i p 协议进行了分析和支持，如思 利的l o s 平台，华为的v r p 5 平台以及j u n i p e r 的j u n o s 平台，但这些平台均是基于 v x w o r k s 系统开发的。v x w o r k s 系统是由风河公司开发的嵌入式操作系统，该操作系 统利用任务间的调度完成协议功能，任务之间共享内存和其它资源，对于开发人员要 求较高，容易造成数据的安全性和可靠性面临威胁，后期维护量大。而且v x w o r k s 系 西南交通大学硕士研究生学位论文第4 页 曼量曼曼! 曼曼! 曼! 皇曼曼曼曼曼曼曼曼! ! 曼詈曼曼曼曼曼曼曼曼曼m li 一 一曼i | 统是收费系统，增加了设备供应商和网络运营商的成本。而l i n u x 系统进程间内存独 立，可靠性高，线程间内存共享，减少通信带来的消耗，支持可抢占，同时具备开源 性和免费性，因此在l i n u x 平台上对r i p 路由协议进行重新设计和实现成为一种发展 趋势h 捌。 近年来，对于r i p 路由协议的研究工作也在继续。文献 6 主要从理论方面对r i p 协议的距离矢量算法进行了研究，虽然提高了协议的安全性和可靠性，但增加了网络 带宽的消耗。同时，也存在相关文献对于r i p 路由协议进行分析和实现，但其并不具 备网络运营商所要求的性能。文献 7 在l i n u xk e r n e l2 4 的基础上主要完成了对r i p 路 由协议的命令行模块的设计，对r i p 协议的基本功能等并没有进行细致的设计。文献 8 采用了z e b r a 开源代码中的r i p 部分实现了在l i n u x 下的r i p 协议，开源代码中采 用伪线程机制对r i p 协议进行了实现。文献 9 】则是利用模块化路由软件协议栈x o r p ( e x t e n s i b l eo p e nr o u t e rp l a t f o i t l l ，可扩展性快放路由平台) ，实现了r i p 协议在c l i c k 软件路由器上的扩展，并未对r i p 协议重新设计。而且文献 7 ，8 ，9 】所实现的r i p 协议并 未对分布式进行支持，实现的r i p 路由器性能一般，不能满足核心路由器的性能要求。 本文在某公司的软件平台进行开发，该平台基于l i n u x 2 6 内核，支持抢占式，同时采 用多线程技术，结合高端分布式交换机，对r i p 协议实现进行重新设计，保证r i p 协 议在分布式架构下高性能可靠运行【l 们，同时设计的模块易于扩展，便于维护。 总体来说，r i p 协议虽然提出的比较早，国内外网络设备供应商在v x w o r k s 系统 上对其提供了比较成熟的支持，但是伴随着l i n u x2 6 内核的发布，网络设备供应商越 来越关注l i n u x 系统，从v x w o r k s 系统移植到l i n u x 系统上成为一种发展趋势【l 。因 此，根据l i n u x 系统架构对r i p 路由协议进行重新设计，实现高性能、高可靠性的r i p 协议成为重要的研究方向。 1 3 论文内容简介及章节安排 1 3 1 论文内容简介 本文基于某公司的开发项目，在分布式交换系统架构下，结合多线程技术实现r i p 路由协议，从而使运行r i p 协议的路由器能够高性能可靠的动态学习路由，同时对于 其他i g p 协议的开发提供了借鉴。 本课题基于i e t f 提出的r f c l 0 5 8 和r f c 2 4 5 3 ，对r i p 协议的两个版本进行了支 持。首先，依据i e t f 提出的r f c ，对r i p 路由协议进行了详细分析。然后对分布式交 换机和多线程技术进行了简要介绍，并基于模块化的对r i p 协议进行了总体设计，提 出主线程和路由维护线程，分别维护系统事件模块和路由维护模块。然后对于每个模 块进行了具体的分析，并通过流程图和时序图的方式进行了实现。最后，对于本论文 的实现结果进行了测试。 西南交通大学硕士研究生学位论文第5 页 论文的主要内容包括： ( 1 ) 结合r f c l 7 0 8 和r f c 2 4 5 3 ，对r i p 路由协议进行详细分析，重点分析了r i p 协议的运行机制。 ( 2 ) 结合分布式系统架构和多线程技术，对r i p 路由协议进行了需求分析，同时 给出了r i p 路由协议的总体设计架构，并划分为两个线程，通过两个模块的交互实现 协议功能。 ( 3 ) 对系统事件处理模块和路由维护模块进行详细的分析，划分为多个子模块， 对每个子模块进行设计和实现，并通过运行时线程间的交互完成协议功能。 ( 4 ) 在分布式交换机上对该协议的实现进行了系统测试，验证了r i p 路由协议的 功能和非功能需求，同时进行了压力测试，达到当前商用系统的性能。 1 3 2 论文章节安排 本文共分为五个章节，内容安排如下： 第1 章，绪论。本章首先对课题的研究背景和意义进行了简单描述，然后介绍了 国内外技术发展现状，尤其是国内外主流平台对于r i p 协议的实现机制，提出了在分 布式下通过多线程技术实现r i p 协议。最后，对论文的内容和章节进行了简单介绍。 第2 章，r i p 路由协议分析。本章首先简要介绍了r i p 路由协议，然后对于该协 议使用的算法进行了描述，并给出了r i p 协议的报文格式。最后给出了r i p 协议运行 的机制，该部分为本章的重点，包括定时更新、触发更新、水平分割和毒性逆转等， 为全文的实现奠定基础。 第3 章，分布式下r i p 路由协议的多线程总体设计。本章首先对分布式交换机和 多线程技术进行了介绍，然后结合r i p 路由协议的基本功能，提出本文的功能需求和 非功能需求，最后给出r i p 路由协议的总体设计，并划分为两个线程，并进行了简要 的协议运行设计。 第4 章，分布式下r i p 路由协议的多线程详细设计和实现。本章在第三章的基础 上，对两大模块进行细分，划分为若干子模块，并通过流程图和时序图对其进行详细 设计和实现。然后列出了主要的数据结构关系和冲突资源的保护，最后对于命令行模 块进行了简单的介绍。 第5 章，系统测试和分析。本章对整个设计实现的r i p 路由协议进行系统测试， 包括功能测试和压力测试。通过搭建测试环境，设计测试方案，得出测试结果，并对 测试结果进行分析，指出满足当前商用的性能。 西南交通大学硕士研究生学位论文第6 页 第2 章r i p 路由协议分析 r i p 是一种较为简单的内部网关协议，由于具有较低的带宽消耗，易于管理和维护， 目前主要用在中小型规模的网络当中，比如校园网、小型企业网以及结构较简单的地 区性网络。而o s p f 、i s i s 等其它i g p 路由协议一般使用在相对比较复杂的大型网络 和环境中。本章首先对r i p 路由协议进行简介，然后对距离矢量算法进行了分析，给 出了协议报文的格式，并对r i p 协议运行机制进行描述，其中对r i p 协议处理流程、 r i p 路由表和路由名词等进行了简单的介绍和分析。 2 1 p 路由协议简介 r i p 路由协议是种使用较早的路由网络协议，基于距离矢量( d i s t a n c e v e c t o r , d v ) 算法，通过u d p ( u s e rd a t a g r a mp r o t o c o l ，用户数据包协议) 报文完成路由信 息的交换，采用的r i p 端口号是5 2 0 。它使用了一种比较简单的度量值取法来计算路由 开销：路由跳数，即从源地址到达目的地址所耗费的“网络成本”，取值为1 到1 5 。在 r i p 网络环境中，和源地址直接相连的网络的度量值被定义为0 ，通过一个路由器可以 到达源地址的度量值为1 ，依次类推计算。同时，每个路由器的度量值可以根据实际网 络环境因素定义为大于1 的整数。为限制r i p 网络的收敛时间，r i p 协议规定度量值 大于或等于1 6 的整数被定义为无穷大，即目的网络或主机不可达。 r i p 路由协议通过与相邻网段的路由器交换路由信息实现路由同步。运行r i p 协 议的路由器每隔一段时间发送当前自己的路由项，与网络中的其它的路由器交换路由 信息，网络中的设备收到r i p 报文更新后，将收到的路由项处理更新自己的路由项。 通过上述机制，网络中的所有路由器同步全网的路由并在本地保存了一份全网同步的 路由表。该路由表中存放了合法的路由项，这些路由项一般是一个网段内的所有网关 或主机的网络地址的汇集信息，表示到达该网段内目的端的路径信息，包括下一跳、 出接口、度量值、路由时间等属性【l 引。 r i p 协议通过定时更新和触发更新实现上述功能。定时更新即为每隔一段时间将路 由器的所有路由项发送出去，而触发更新只是将变化的路由及时发送出去。同时，r i p 协议采用水平分割( s p l i th o r i z o n ) 和毒性逆转( p o i s o nr e v e r s e ) 机制提高网络性能， 减少路由收敛时间，防止路由环路产生。水平分割和毒性逆转机制约定路由从学来的 接口再次发送出去时需要经过特殊处理。 r i p 协议报文分为请求报文和响应报文两大类。请求报文用来请求邻居路由器的路 由项，完成请求端路由器中路由项的更新。响应报文中填充的为发送的路由项，用于 网络间路由的同步。 西南交通大学硕士研究生学位论文第7 页 2 2 距离矢量算法 路由是为了寻找一条从源端到目的端的最优路径，同一网段内的源端和目的端是 不需要进行选路的。不同网段间的源端和目的端，实际是通过源端网段与目的端网段 选路的。如果两个网段没有相连，源端可以通过广播或者组播的方式与同一网段的目 的端进行通信，然后采用同样方式通过多个网段的传递到达目的网段。到达目的网段 后，通过发送广播报文寻找目的端。 r i p 路由协议基于距离矢量算法进行选路，并对距离矢量算法存在的缺陷进行了一 定的补充。距离矢量算法也称b e l l m a n f o r d 算法，采用跳数衡量不同网段之间的“损 耗 。由于距离矢量算法简单易用，但在安全机制和路由环路上存在缺陷，近年来很多 文献对算法进行了详细的分析和改进，而对于一些中小型网络而言，改进的算法增加 了网络间的带宽消耗，使得r i p 协议的优势不再明显【l3 1 。因此，本文仍是基于原始的 距离矢量算法，其公式准则如下： d 仡0 = 仍 所有的f d o , j ) = m i n d ( i , 砂+ d 传脚 不同的k 其中d o , j ! ) 代表源端f 到目的端的最优路径，dc i , j ) 代表与从f 端到与相邻的_ ， 端的度量值，当i 和，不相邻或者f 和，在同一网段时d o , j ) 被定义为无穷大。 在距离矢量算法中，网络中的所有运行同一协议的路由器相互协作，分别计算到 达每个目的网段的最佳路径，即尽量寻找度量值最小的路由项，共同完成分布式计算 任务。在算法的任意一个时间间断里，路由器都会保存一份学习到的到达每个目的网 段的最优路由信息。路由器会通过发送机制将当前路由项信息通知给它的所有直连的 邻居，而后它的邻居也会把它们的最优路由信息发送给它们各自相连的邻居。这样， 某一个路由器在收到其邻居通知过来的最优路由信息之后，发现这条最优路由信息比 当前保存的路由信息更好，路由器就会更新到达某个目的网段的度量值和下一跳，并 把自己的新更新的路由项通知给所有的邻居。这就完成第一轮的迭代运算。在经过多 轮这样的迭代运算之后，路由选择趋于稳定，每个路由器最终都会保存到到达目的网 段的最优路由【h j 。 当网络拓扑关系不发生改变的情况下，该算法可以在有限的时间内使得d “) 得到收敛，即完成路由收敛。而当网络环境发生改变，如网关或者线路发生故障时， 网络中的邻居关系发生了相应的变化，按照公式重新进行最优路由的选取。在理论化 的算法中包含了所有的路由信息，如果拓扑发生改变，在下一次的计算中会反应出来。 而在实际算法中，仅保持了目标的最佳路径。如果链路中断或者网关崩溃，不能通过 链路向邻居发送最新改变的路由，也就无法真正反映实际的网络拓扑环境了。 为了解决上述问题，距离矢量算法采用一定的机制进行预防。不同的协议，预防 所采用的机制和细节有所不同。对于r i p 路由协议而言，路由器会每隔3 0 秒向其所有 西南交通大学硕士研究生学位论文第8 页 的邻居发送周期性的更新。如果邻居在1 8 0 秒内都没有收到该路由器的路由，则协议 规定该路由器或者链路出现问题，该路由器中的路由无效。由于r i p 协议采用的是u d p 不可靠连接，网络中的信息在传输过程中可能偶然会丢失，因为一次传输没有达到就 定义为网关崩溃是不合适的。因此采用每隔3 0 秒就会向邻居发送定时更新，1 8 0 秒作 为网关或链路故障的依据。 采用路径时效机制，保证了距离矢量算法的收敛性，然而却不能保证收敛时间的 有效性，即无法确定在短时间内保证路由收敛【l5 1 。产生这一问题的关键原因在于路由 环路的形成，造成相邻路由器过度依赖，相互学习本已失效的路由，直至度量值变为 1 6 后路由器才更新路由项为无效值，实现路由收敛。为了解决上述问题，加快网络收 敛，需要将无效的路由尽快的向邻居发送，不同协议对其处理细节不同。r i p 路由协议 采用毒性逆转、水平分割和触发更新机制确保问题收敛时间趋于稳定性【l 6 1 。7 1 。 2 3 p 协议报文格式 在t c p i p 网络体系架构中，传输层主要依靠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 o l ， 传输控制协议) 或者u d p 完成传输层功能。u d p 协议提供一种无需面对连接、不可靠 的数据报服务。源主机在传送数据前不需要和目标主机建立安全的连接。u d p 报文发 送时填充u d p 协议报文头字段，如源端口号和目的端口号、报文长度等后，直接发往 目的端主机，每个数据报文的可靠性靠上层协议维护和保证。 r i p 协议基于u d p 报文进行路由信息的接收和发送，并且使用的u d p 端口号为 5 2 0 。下面首先对u d p 报文格式进行介绍，然后再对r i p 报文格式进行具体说明。 2 3 1u d p 报文格式 u d p 为o s i ( o p e l ls y s t e mi n t e r c o n n e c t ，开放式系统互联) 参考模型中一种无连接 的运输层协议，与t c p 相比，其提供的信息传送服务是简单而且不可靠的。u d p 协议 报文格式如表2 1 所示。 表2 1u d p 协议报文格式 ( 1 ) 源、的端口号字段：占两字节，用来标志源端和目的端应用进程，不同的应 用进程使用不同的端口号。 ( 2 ) 长度字段：占两字节，为u d p 协议报文头部和数据段的总长度。 ( 3 ) 校验和：占两个字节，用来对u d p 报文头部和数据段进行检查。 西南交通大学硕士研究生学位论文第9 页 ( 4 ) 数据段：填充的应用进程数据。上层应用需要传输的数据封装在该数据段中。 2 3 2r i p 报文格式 r i p 协议为应用层协议，封装为数据后通过u d p 进行传输，端口号为5 2 0 。r i p 协议对请求报文处理时，一般使用请求报文携带的源端口号作为目的端口号发还给请 求者。 r i p 协议分为r i p 1 和r i p 一2 两个版本，r i p 2 是对r i p 1 的补充完善，在报文格 式上只是对某些字段进行了补充设置 1 8 】。下面首先对r i p 报文整体进行介绍，然后再 分别对r i p 1 和r i p 2 的路由项进行详细介绍。 r i p 协议报文头包含命令字段、版本字段和m b z ( m u s tb ez e r o ，保留字段) 三部 分，r i p 1 和r i p 2 版本在协议报文头上是没有区别的，如下表2 2 所示。 表2 2r i p 协议报文头格式 ( 1 ) 命令字段：占一个字节，指定报文用途，分为请求报文和响应报文。请求报 文用于向邻居请求部分或者能够与全部路由，加速路由收敛；响应报文表明报文中填 充的路由项为接收需要处理的路由项。 ( 2 ) 版本字段：占一个字节。分为版本r i p 一1 和r i p 2 ，版本不同决定了报文中 路由项的填充格式。 ( 3 ) m b z 字段：占一个字节。目前r i p 1 和r i p 2 均没有都该字段进行补充和说 明，仍是填充为o 。 ( 4 ) 路由项：每个路由项占用2 0 个字节，由于u d p 报文长度的限制，路由项最 多携带2 5 个路由表项。 2 3 2 1r i p 1 报文格式 r i p l 是出现的比较早的路由协议，在r f c l 0 5 8 对其进行了介绍。r i p 1 是有类路 由协议( c l a s s f u lr o u t i n gp r o t o c 0 1 ) ，它只支持以广播报文方式发送报文，路由项中不 包含掩码信息，只能识别传统的自然网段类型的路由，也就无法支持不连续子网 ( d i s c o n t i n u o u ss u b n e t ) 。r i p 1 的路由项如表2 3 所示。 ( 1 ) 地址描述符( a f i ，a d d r e s sf a m i l yi d e n t i f i e r ) - 占用两个字节。值为2 时， 表示网络层使用的为i p 协议。 ( 2 ) m b z 字段：占用四个字节，表示该字段填充的为0 。由于r i p 1 当时的网络 西南交通大学硕士研究生学位论文第10 页 环境，定义的报文格式中保留了很多m b z 字段，为以后的扩展和完善提供了方便。 表2 3r i p 1 路由项格式 01 51 63 1 地址描述符m b z 路由项地址 m b z m b z 度量值 ( 3 ) 路由项地址：占用四个字节，携带的路由项的目的地址，可以是自然网段路 由、子网路由和主机路由。由于r p 1 没有携带掩码信息，当该字段为子网路由时， 协议作为主机路由处理。 ( 4 ) 度量值：占用四个字节。用来表示该路由项距离该路由器的成本，在r i p 协 议中，可以简化为跳数。 由于r i p 1 版本出现的较早，当时的网络结构不复杂，设计时并不支持自治系统、 子网以及认证技术等。 2 3 2 2r 口2 报文格式 伴随着子网的出现，i e t f 在r f c l 3 8 8 中推出了r i p 2 版本，并且在r f c l 7 2 3 和 2 4 5 3 中对r i p 路由协议进行了扩充和完善。r i p 一2 路由协议是一种无类路由协议，与 r i p 1 相比，它支持了路由标记、掩码信息和下一跳，同时支持了对报文进行验证。r i p 2 和r i p 1 路由项格式类似，如表2 4 所示。 表2 - 4r i p 2 路由项格式 o1 51 63 1 地