（计算机应用技术专业论文）internet域间路由稳定性研究.pdf

东北大学博士学位论文 i n t e r n e t 域问路由稳定性研究 摘要 i n t e m e t 从诞生到现在已经发生了巨大的变化。整个i n t e m e t 被划分为不同的管 理域，这些管理域称为自治系统。自治系统内部通过内部网关协议交换路由信息， 自治系统间通过外部网关协议交换路由信息。目前，边界网关协议( b g p ) 是运 行于i n t e r n e t 上的事实上的外部网关协议。随着网络规模的扩大，b g p 路由的稳 定性受到了业界的广泛关注，如何解决b g p 路由不稳定问题已经成为i n t e m e t 路 由研究的焦点。 b g p 路由不稳定是指存在于路由表中的路由间断性的消失和再现的现象，也 叫路由振荡。导致b g p 路由不稳定的因素很多，包括i g p 不稳定、硬件故障、软 件故障、路由器c p u 能力不足和存储能力不足、网络拓扑改变、b g p 路由策略冲 突和配置错误等。本文以国家自然科学基金项目“i n t e m e t 域间路由稳定性和可管 理性”为背景，作为研究项目的一部分，对域间路由稳定性进行了深入的研究， 针对导致b g p 路由不稳定的部分原因，给出提高b g p 路由稳定性的方法，取得了 一些重要的研究成果。 路由策略冲突可导致b g p 路由振荡。本文对路由策略冲突引发的路由振荡进 行了深入研究，并通过仿真实验再现了路由振荡现象，给出了一种路由策略冲突 检测和策略冲突引发的路由振荡抑制方法。首先根据b g p 路由模型稳定路径问题， 对b g p 路由振荡进行研究，从理论上深入地分析了b g p 路由振荡的动态行为特征 和振荡条件。给出路由相对优先级的概念，用路由相对优先级来描述到同一目的 的两条路由的优选关系。相邻自治系统通过所选路由的相对优先级比较来发现路 由策略冲突。定义本地路径历史记录参与振荡的路由，并对本地路径历史中的重 复路由加以抑制，消除b g p 路由振荡。该方法能够准确地检测到b g p 路由策略冲 突引发的路由振荡和参与振荡的路由，并能区分策略冲突引发的路由振荡和其它 原因引发的路由振荡。 b g p 路由不稳定源可以通过追踪路由变化事件来确定，为此给出另外一种 b g p 路由不稳定解决方法。每个路由器都对路由变化事件及原因进行记载，a s 间 通过构建路由变化事件链发现路由振荡源。通过仿真实验证实了该方法的有效性。 b g p 路由器对路由表进行管理要消耗大量的c p u 时间和存储空间，b g p 路由 表过大可能造成路由器处理能力和存储能力不足，导致路由器失效和b g p 连接中 东北大学博士学位论文 摘要 断，影响b g p 路由的稳定性。对b g p 路由表的构成进行了定量分析，发现路由表 内包含大量前缀长度大于区域i n t e m e t 注册处所允许的最大前缀长度的路由。提出 了基于过滤机制的减缓路由表增长的方法，与一般过滤方法不同的是，该方法对 地址前缀长度大于区域i n t e m e t 注册处规定的最大长度的路由进行过滤。考虑到客 户对负载均衡和可靠连接的需求，允许前缀长度过长的路由在指定范围内传播， 一旦传播距离超过所规定的范围就对路由加以过滤。利用实际的b o p 路由表进行 实验，发现该方法可以大大减少b g p 路由表内的路由数，对抑制路由表增长效果 明显，同时几乎不对网络的可达性产生影响。 路由配置错误也是导致b g p 路由不稳定的一个原因，路由配置错误会增加路 由器负载，甚至导致网络中断。本文主要研究路由源配置错误和路由输出配置错 误。路由源配置错误主要是指导致通告了无效的地址前缀、无效的a s 号的路由配 置，路由输出配置错误是指违反b g p 路由输出策略的路由配置。提出了一种路由 配置错误检测方法，该方法对输入和输出路由的前缀进行从属关系检测，发现非 授权的地址前缀。自治系统之间根据商业合同形成了客户提供者关系和对等者关 系，自治系统的路由输出策略由a s 关系决定，本文利用a s 关系对路由进行有效 性检测，发现违反输出原则的路由。 针对b g p 路由的收敛问题，分析了b g p 路由收敛陧的原因。b g p 收敛慢主 要是由于收敛过程中大量的路由探测和自治系统间b g p 路由策略冲突所导致，同 时b g p 路由收敛慢与网络拓扑和最小路由通告时间间隔相关。基于竞争有向图对 b g p 收敛时间进行研究，给出了b g p 收敛时间范围，并从理论上加以证明，最后 通过仿真实验证实了所得结论的正确性。 关键词：自治系统，域间路由，边界网关协议，路由振荡，路由策略，收敛时间 b g p 路由表，b g p 路由配置错误 东北大学博士学位论文a b s t r a c t s t u d y o ni n t e r - d o m a i nr o u t i n gs t a b i l i t y a b s 仃a c t i n t e r a c th a su n d e r g o n es i g n i f i c a n tc h a n g e sf r o mi t si n c e p t i o n t h ei n t e r n e th a sb e e n d i v i d e di n t od i f f e r e n ta d m i n i s t r a t i v ed o m a i n sc a l l e da u t o n o m o u ss y s t e m s 阻s e s ) w i t h i nt h ea s ，i n t e r i o rg a t e w a yp r o t o c o l sa r eu s e dt oe x c h a n g er o u t i n gi n f o r m a t i o n e x t e r i o rg a t e w a yp r o t o c o l sa r eu s e dt oe x c h a n g er o u t i n gi n f o r m a t i o nb e t w e e na s e s t h e b o r d e rg a t e w a yp r o t o c o lm g p ) i st h ed ef a c t oe x t e r i o rg a t e w a yp r o t o c o ld e p l o y e do nt h e i n t e r a c t w i t ht h eg r o w t ho ft h ei n t e r n e t ，t h es t a b i l i t yo fb g ph a sg o a e nt h en o t i c e so f e x p e r ta n di n d u s t r yp e o p l e h o wt os o l v et h ei n s t a b i l i t yp r o b l e mo fb g ph a sc u r r e n t l y b e c o m et h ef o c u sc o n c e r n e dw i t ht h er e s e a r c ho f i n t e r n e tr o u t i n g t h er o u t ei n s t a b i l i t yi sr e f e r r e dt oa sr o u t ef l a p p i n gi nw h i c har o u t et h a tp r e v i o u s l y e x i s t e di nt h er o u t i n gt a b l ed i s a p p e a r sa n dr e a p p e a r si n t e r m i t t e n t l y t h er e a s o n sf o rb g p r o u t ei n s t a b i l i t ya r ed i v e r s e ，i n c l u d i n gi n t e r i o rg a t e w a yp r o t o c o li n s t a b i l i t y , h a r d w a r e f a i l u r e s ，s o f t w a r ep r o b l e m s ，c p up o w e ri n s u f f i c i e n t ，m e m o r yi n s u f f i c i e n t ，n e t w o r k t o p o l o g yc h a n g e ，b g pr o u t i n gp o l i c i e sc o n f l i c ta n dr o u t e sc o n f i g u r a t i o ne r r o r s b a s e do n p r o j e c tr e s e a r c ho f i n t e r d o m a i nm u t i n gs t a b i l i t ya n dm a n a g e m e n t ，f r o mn a t i o n a ln a t u r a l s c i e n c ef o u n d m i o no fc h i n a ，t h ed i s s e r t a t i o nd i s s e r t e st h es t a b i l i t yo fi n t e r - d o m a i n r o u t i n g w es t u d ys o m eo f t h er e a s o n sl e a d i n gt ob g pr o u t i n gi n s a b i l i t ya n dg i v em e t h o d s t oe n h a n c eb g pr o u t i n gs t a b i l i t yi nt e r mo ft h e s er e a s o n s s o m ev a l u a b l er e s u l t sa r e y i e l d e d t h ep o l i c yc o n f l i c t so fb g pc a nc a u s er o u t eo s c i l l a t i o n s ，i nt h i sp a p e rw ed e e p l y s t u d yt h er o u t eo s c i l l a t i o nc a u s e db yb g pr o u t i n gp o l i c i e sc o n f l i c t sa n dp r e s e n tt h er o u t e o s c i l l a t i o nt h r o u g hs i m u l a t i o ne x p e r i m e n t am e t h o dt od e t e c tp o l i c i e sc o n f l i c t sa n dr o u t e o s c i l l a t i o nc a u s e db yi n s i s t e n tp o l i c i e si sp r o p o s e d w ef i r s tu s et h es a f ep a t hp r o b l e m st o s t u d y t h eb g pr o u t eo s c i l l a t i o na n dt h e o r e t i c a l l y a n a l y z et h ed y n a m i cb e h a v i o r c h a r a c t e r i s t i c sa n dc o n d i t i o n so fb g pr o u t e so s c i l l a t i o n s w ed e f i n et h ec o n c e p t i o no f r o u t er e l a t i v ep r e f e r e n c et h a ti su s e dt od e s c r i b et h ep r e f e r e n c er e l a t i o n s h i pb e t w e e nt w o d i f f e r e n tr o u t e st ot h es a m ed e s t i n a t i o n c o m p a r i n gt h er e l a t i v ep r e f e r e n c eo fs e l e c t e d r o u t e s ，t w on e i g h b o r i n ga s e sc a nd e t e c tt h er o u t i n gp o l i c i e sc o n f l i c t s w ed e f i n ead a t a s t r u c t u r e ，l o c a lp a t hh i s t o r y , t os t o r er o u t e st a k i n gp a r ti no s c i l l a t i o na n de l i m i n a t er o u t e o s c i l l a t i o nb yd a m p i n gt h er o u t er e a p p e a ri nt h el o c a lp a t hh i s t o r y t h eg i v e nm e t h o dc a r l t v 东北大学博士学位论文 a b s t r a c t a c c u r a t e l yf i n dt h er o u t i n go s e i u a t i o nc a u s e db yp o l i c i e sc o n f l i c t sa n di d e n t i f yt h er o u t e s i n v o l v e d t h i sm e t h o dc a l la l s od i s t i n g u i s ho s c i l l a t i o n sb e t w e e nt h eo n ec a u s e db y p o l i c i e sc o n f l i c t sa n dt h eo n ec a u s eb yo t h e rr e a s o n s t h eo r i g i no fr o u t ei n s t a b i l i t yc a l lb ef o u n db yt r a c i n gt h er o u t ec h a n g ee v e n t s b a s e do nt h i si d e a ，w ea l s op r e s e n ta n o t h e rm e t h o dt os o l v et h ep r o b l e mo fr o u t e i n s t a b i l i t y t h er o u t ec h a n g ee v e n t sa r el o g g e da tl o c a lr o u t e r sa n du s e dt of i n do r i g i no f r o u t eo s c i l l a t i o nb yc o n s t r u c t i n gt h er o u t e se v e n t sl i n kb e t w e e na s e s t h ef e a s i b i l i t yo f t h eg i v e nm e t h o di sp r o v e dt h r o u g he x p e r i m e n t b g pr o u t e rn e e d sm o r ec p ut i m ea n ds t o r a g es p a c et od e a lw i t ht h el a r g eb g p r o u t i n gt a b l e t h el a r g eb g pr o u t i n gt a b l el o a dc a nl e a dt or o u t e rf a i l u r ea n dl i n ki n t e r r u p t ， d u et ot h ei n s u f f i c i e n to fc p up o w e ra n dm e m o r y a sar e s u l tt h es t a b i l i t yo fb g pi s a f f e c t e d w ea n a l y z eb g p r o u t i n gt a b l e sa n do b s e r v e dt h a tt h e r ea r eal o to fr o u t e sw i t h p r e f i xl e n g t hl a r g e rt h a nt h ea d d r e s sa l l o c a t i o ng u i d e l i n e sp u b l i s h e db yt h er e g i o n a l i n t e m e tr e g i s t r i e s ( r i r s ) i nt h eb g pr o u t i n gt a b l e w eg i v eam e t h o dt oc o n t r o lt h e g r o w t ho fb g pr o u t i n gt a b l eb yf i l t r a t i o n t h i sm e t h o di sd i f f e r e n tf r o mn o r m a lf i l t e r i n g m e c h a n i s m s i tf i l t e r sr o u t e sw i t h l a r g e rp r e f i xl e n g t h t h a n p e r m i t t e db yr i r s c o n s i d e r i n gt h er e q u i r e m e n t so fc u s t o m e r sf o rl o a db a l a n c ea n dr e l i a b l ec o n n e c t i o nt o i n t e m e t w ea l l o wt h er o u t e sw i t hl a r g e r p r e f i xl e n g t ht r a v e la ta s p e c i f i e ds c o p e o n c et h e r o u t e sw i t hl a r g e rp r e f i xl e n g t ht r a v e l e dt h es p e c i f i e dd i s t a n c e ，t h e s er o u t e sa r ef i l t e r e d s i m u l a t i o nw i t ht h er e a lb g pr o u t i n gt a b l es h o w st h a tt h i sm e t h o dc a ne f f e c t i v e l y c o n s t r a i nt h es i z eo fb g p r o u t i n gt a b l e sa n dh a r d l ya f f e c tt h er e a c h a b i l i t yo ff i l t e r e d a d d r e s s e s m i s c o n f i g u r a t i o ni sa n o t h e rr e a s o nf o rb g pr o u t ei n s t a b i l i t y m i s c o n f i g u r a t i o n sc a n i n c r e a s et h eu p d a t el o a do nr o u t e r s ，a n de v e nd i s r u p ti n t e m e tc o n n e c t i v i t y i nt h i sp a p e r ， w em a i n l ys t u d yt h e o r i g i nm i s c o n f i g u r a t i o na n de x p o r tm i s c o n 矗g u r a t i o n o r i g i n m i s c o n f i g u r a t i o ni st h eo n et h a tl e a d st ou n i n t e n t i o n a l l ya n n o u n c er o u t e sw i t hi n v a l i d p r e f i x e so ra sn u m b e r st og l o b eb g pt a b l e s e x p o r tm i s c o n f i g u r a t i o ni st h eo n et h a t v i o l a t e st h eb g pr o u t e r se x p o r tp o l i c y am e t h o dt od e t e c tc o n f i g u r a t i o ne r r o r si sg i v e n i nt h i sm e t h o d ，t h ei n b o u n dr o u t e sa n do u t b o u n dr o u t e sa r ed e t e c t e df o ro r i g i ne r r o r s a c c o r d i n gt ot h er e l a t i o n s h i pb e t w e e nt h ep r e f i x e sa n da s e sw h i c ha n n o u n c et h ep r e f i x e s t h er e l a t i o n s h i p sb e t w e e na u t o n o m o u ss y s t e m sa r ec u s t o m e r - p r o v i d e ra n dp e e r - p e e r f o r m e da c c o r d i n gt ot h ec o m m e r c i a la g r e e m e n t e x p o r tp o l i c i e so f a n a sa r i s e sf r o mt h e c o m m e r c i a lr e l a t i o n s h i p sw i t l lo t h e ra s e s i nt h i s p a p e rw er i s e t h ec o m m e r c i a l v 东北大学博士学位论文 a b s t r a c t r e l a t i o n s h i p sb e t w e e na s e st od e t e c tr o u t e sa n df u r t h e r f i n dr o u t e sv i o l a t i n ge x p o r t g u i d e l i n e s f o rt h ep r o b l e mo fb g pc o n v e r g e n c e ，w ea n a l y z et h er e a s o n sf o rb g ps l o w c o n v e r g e n c e t h es l o wc o n v e r g e n c eo fb g pi sm a i n l yd u et ot h ee x p l o r a t i o no fr o u t e s d u r i n gc o n v e r g e n c ea n dt h ep o l i c yc o n f l i c t sb e t w e e na s e s m e a n w h i l et h en e t w o r k t o p o l o g ya n dm i n i m a r o u t ea d v e r t i s e m e n ti n t e r v a l ( m r a i ) a l s oc o n t r i b u t et ot h es l o w c o n v e r g e n c e b a s e do nd i s p u t ed i g r a p h ，t h eb g pc o n v e r g e n c et i m ei ss t u d i e d t h eb g p c o n v e r g e n c et i m er a n g ei sg i v e na n dt h e o r e t i c a l l yp r o v e d s i m u l a t i o ne x p e r i m e n th a s p r o v e dt h ec o r r e c t n e s so f t h ec o n c l u s i o n a b o u tb g pc o n v e r g e n c et i m e k e yw o r d s ：a u t o n o m o u ss y s t e m ，i n t e r - d o m a i nr o u t i n g ，b o r d e rg a t e w a yp r o t o c o l ，r o u t e o s c i l l a t i o n ，r o u t i n gp o l i c i e s ，c o n v e r g e n c et i m e ，b g pr o u t i n gt a b l e ，b g p m i s c o n f i g u r a t i o n - v i 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究 成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果， 也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：工j 彰g 日期：厶dz 2 、27 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规 定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论 文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关 数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名 签字日期 导师签名： 签字日期： 东北大学博士学位论文第一章绪论 第一章绪论 i n t e m e t 作为全球最大的计算机网络系统，把全世界的计算机网络连接在一起， 是一个巨大的数据通信网和信息资源网，在社会信息化的进程中扮演着不可替代 的角色。然而，随着i n t e m e t 规模的不断扩大，其拓扑结构也变得越来越复杂m 】， 同时出现了路由稳定性、可靠性及安全性等多方面的问题，这些问题的研究和解 决对改善和提高i n t e r n e t 整体性能具有重要意义。 1 1 研究背景 1 1 1i n t e r n e t 组成及拓扑结构 i n t e m e t 是一个以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 m e tp r o t o c 0 1 ) 网络协 议连接各个国家、各个地区、各个机构的巨大的计算机网络【3 4 】，由i n t e m e t 服务提 供者共同管理。所谓的i n t e m e t 服务提供者就是为网络用户提供访问i n t e m e t 上信 息资源服务的运营商，它们在多个区域都有称为呈现点( p o i n to f p r e s e n c e ，p o p ) 的连接点，用户网络通过把一些设备放在服务提供者的p o p 处实现与提供者网络 的连接，或者通过接入线与提供者网络相连。p o p 的汇集和p o p 之间的连接路径 形成了服务提供者网络。服务提供者网络可能覆盖一个很大的区域，有些服务提 供者网络甚至跨越国家或地区。服务提供者网络通过网络访问点( n e t w o r ka c c e s s p o i n t ，n a p ) 互连，或直接互连，n a p 是一个高速的交换设备或交换网，连接到n a p 上的网络可以相互交换数据。图1 1 绘出了i n t e m e t 的一般结构。 i n t e r n e t 是一个开放分布式的系统，没有一个核心的管理机构，是一个拥有很 多所有者的“松散的互联网络”，人们把这些网络称为自治系统( a u t o n o m o u s s y s t e m s ，a s s ) 。所谓的自治系统就是具有同一选路策略，在同一技术管理部门下 运行的网络，例如：研究机构、大学、企业和政府网络 6 - s 】。整个i n t e r n e t 被分割成 多个称为自治系统的管理控制域，每个a s 都有一个惟一的1 6 比特编号，这个编 号由i n t e r n e t 授权的管理机构来指定1 9 】。自治系统分属于不同的i s p ，有些i s p 只包 含一个a s ，有些i s p 则拥有多个a s ，且分布在不同的地区。每个a s 都有自己的 路由器和路由策略，a s 通过私有或公共的交换节点与一个或多个远端a s 相连， 公共交换点处在物理上相连的两个a s 不一定进行数据交换。因此，a s 级上的 东北大学博士学位论文第一章绪论 i n t e m e t 连接是一种逻辑连接( 图1 2 ) 。 图1 1 n t e m e t 的一般结构 f i g 1 1t h eg e n e r a la r c h i t e c t u r eo f i n t e r n e t 豳1 2i n t e m e t 拓扑结构 f i g 1 2i n t e m e tt o p o l o g y 随着商业化进程的发展，i n t e m e t 呈爆炸性增长，目前己分配的a s 号达到3 3 0 0 0 多爪【1 0 1 ，i p v 4 地址也将要耗尽。i n t e m e t 用户数的不断增加使得其拓扑结构变得 更为复杂。现在a s 大致可以分为四类，第一层为骨干网，第二层为区域或国家i s p ， 第三层大城市范围的i s p ，第四层小城市范围的i s p 1 , 1 2 1 。a s 间的连接关系并非逐 层相连，一层a s 也可能与三、四层a s 相连。一个a s 可以和多个a s 相连，可以 有多个服务提供者，也可以有多个客户。 1 1 2ln t e r n e t 路由协议 i n t e m e t 路由基础设施由路由器、主机以及他们之间相互连接的链路组成。保 证端到端的数据有效传输是i n t e m e t 路由系统的主要目的。所谓路由就是指把数据 从源通过网络传送到目的的行为和动作，路由器是执行这种行为动作的网络设备。 为了实现数据转发的目的，路由器必须知道如何到达目的网络，即路由器必须有 到达目的网络的路由。路由器可以通过两种方法获得路由：静态的方法和动态方 法。静态的方法获得的路由也称为静态路由，是网络管理员通过命令直接为路由 器配置的路由。动态方法获得的路由称为动态路由，是路由器通过路由协议( 路 东北大学博士学位论文第一章绪论 由器动态交换路由和选择路由的方法) 从其他路由器获得的路由。 i n t e m e t 的拓扑结构决定了i s p 问路由的复杂性，由于a s 分属于不同的实体， 这就决定不同的a s 可能运行不同的路由协议，而a s 之间彼此互连，这又决定了 不同的a s 之间要运行相同的路由协议。根据路由协议在互连网中作用的不同， i n t e m e t 路由协议可以分为两大类：内部网关协议( i g p i n t e r i o r g a t e w a y p r o t o c 0 1 ) 和外部网关协议( e g pe x t e r i o rg a t e w a yp r o t o c 0 1 ) 。内部网关协议( i g p ) 运行于 a s 内部，如：r i p c i 3 1 ( r o u r i n g i n f o r m a t i o n p r o t o c 0 1 ) 、o s p f 1 4 1 ( o d e n s h o r t e s t p a t h f i r s t ) 等。自治系统内部路由器之间通过i g p 相互交换路由信息，选择到目的网络 的最佳路径，每个路由器都包含到目的网络的完整的拓扑信息。 外部网关协议( e g p ) 是运行于a s 之间的路由协议，用于a s 间动态交换选 路信息和实现网络互连，如：b g p 协议( b o r d e rg a t e w a yp r o t o c 0 1 ) 。 1 内部网关协议 基于路由器计算和交换路由信息的方法，路由协议可分为距离矢量路由选择 协议和链路状态路由选择协议。 ( 1 ) 距离矢量路由选择协议 距离矢量路由选择协议利用距离矢量算法( 也称b e l l m a n f o r d 算法) 计算到达 目的网络的最佳路径，路径的优劣是通过一个度量值( 如路由器跳数) 来衡量的， 一般选择度量值最小的路径为到目的端的最佳路径。路由器之间相互协作完成路 由选择任务，每个路由器都把当前所选的最佳路径通知给它的所有邻居，同时它 的邻居也把它们的最佳路径通知给它们各自的邻居。这样，一个路由器在得到其 邻居正采用的路径之后如果发现一条通过某个邻居的更好的路径，路由器就更 新到达目的网络的距离和下一跳，并把自己的新选择通知所有的邻居。在经过多 次这样的迭代之后，路由选择将达到稳定，每个路由器都会找到一个通往目的端 的最佳路径。 距离矢量协议是一个易于配置、维护和使用的非常简单的协议，因此，在有 极少的冗余路径和对网络性能要求不高的非常小的网络中，这个协议表现较好。 距离矢量协议的一个经典实例就是路由信息协议r i p 1 3 , 1 6 - 1 9 ，它的主要优点就是比 较简单。但也有一些缺点，比如收敛比较慢，计数到无穷问题，只有到目的网络 的跳数信息。 运行r i p 协议的路由器每隔3 0 秒广播一次路由信息报文，报文包含的信息来 自路由器的当前路由选择数据库，每个报文都包含网络地址和到达目的网络的距 离( 跳数) 。r i p 所使用的距离度量就是通往目的地所经过的路由器数，取值为1 1 5 之间的整数，值1 6 表示节点不可达。p o p 协议交换路由信息的工作过程是；当 3 东北大学博士学位论文第一章绪论 路由器的某接口上启动r i p 后，接口以多搔的形式向邻居发送路由表信息请求 收到请求的路由器发送整个路由表作为对请求的响应；而后就周期性地广播路由 信息报文，只有当检测到路由变化时，才向邻居发送触发更新，即一旦察觉到路 由变化，就请求节点立即发送路由信息报文，通知邻居路由变化，而不等本轮发 送周期结束。路由表的每个表项通常含有目的地i p 地址、通往目的地的度量值、 下一跳路由器地址、各种定时器和最近更新标志。 ( 2 ) 链路状态路由选择协议 链路状态路由选择协议是另一种应用比较广泛的i g p 协议，与距离矢量协议 所采用的递增的分布式计算不同，链路状态路由选择协议采用了一种冗余分布式 数据库方法，根据链路状态算法计算路由。数据库提供关于每个路由器的局部环 境信息，反映的是整个网络的拓扑结构。一个路由器的链路状态是指它与哪个网 络或路由器相邻，以及到这些网络和路由器的度量。链路状态协议不用通告到达 每个目的端的路径代价，而是通过链路状态更新交换局部的网络链路和状态。这 些链路状态更新被发送给其他所有的路由器。最后的结果是所有的路由器都能获 得相同的由收集到的链路状态更新组成的数据库，这个数据库描述了当前的网络 地图。网络中每条路径的代价设为其各条链路代价之和。根据网络地图，每个路 由器可以运行最短路径算法，生成到达每个目的网络的最短路径( 一般采用d i j k s t r a 算法) 。链路状态协议一般被认为具有较好的收敛特性，当网络发生变化时，寻找 新路由更快速，而且所需的开销较少。因为链路状态协议比距离矢量协议拥有更 多的数据，它可以较容易地计算出具有复杂特征的路径，而距离矢量协议只能计 算出具有最低代价的简单路径。链路状态协议可以计算出针对不同的i p 服务类型 的路径，也可以计算遵从诸多策略限制的路径，或者计算出能保证一定服务质量 的路径。 开放最短路径优先协议o s p f 1 4 , 2 0 - 2 2 是基于链路状态的动态路由选择协议，是 由i n t e m e t 工程任务组i e t f ( i n t e r n e te n g i n e e r i n g t a s kf o r c e ) 推荐的内部网关协 议，且得到软件厂商的支持，也是目前i n t e r n e t 上普遍采用的内部网关协议。 o s p f 协议由三个子协议组成：呼叫( h e l l o ) 协议、交换协议与扩散协议。 其中h e l l o 协议负责检查链路是否可用，并完成选举指派路由器及其备份，选举 完指派路由器后，其他路由器将与指派路由器建立相邻关系，并使他们的数据库 与之同步：交换协议完成“主”、“从”路由器的指定并交换各自的路由数据库信 息；扩散协议完成各路由器中路由数据库的同步维护，当一条链路发生状态变化 时，与该链路相连的路由器就将发布新版本的链路状态更新。 2 外部网关协议 d 东北大学博士学位论文第一章绪论 ( 1 ) e g p 协议 外部网关协议e g p ( e x t e r i o r g a t e w a y p r o t o c 0 1 ) 【2 3 】用于相邻的自治系统之间交 换网络可达信息，运行e g p 协议的路由器称为邻站。 首先，运行e g p 协议的路由器通过发送邻站获取报文和另一个路由器建立e g p 通信。建立了邻站关系的路由器共享网络可达信息，相邻路由器在距离的远近上 没有明显的要求。其次，e g p 路由器周期性地发送h e l l o 报文和轮询报文，并等待 邻站响应，或者利用可达报文的状态字段信息来判断邻站是否存活。第三，e g p 路由器通过发送轮询请求和轮询响应报文得到网络可达信息。 e g p 设计于1 9 8 3 年，是为适合当时的i n t e m e t 拓扑而设计的。当时i n t e m e t 的 拓扑结构很简单，是两层结构，一个核心a s 外加一些与核心相连的a s 。e g p 是 一种距离矢量协议，度量值是一个1 2 5 5 的整数，2 5 5 表示网络不可达。随着网 络规模的不断扩大，e g p 不再适应大规模i n t e r n e t ，首先，e g p 不支持子网的概念， 其次，不支持多个a s 的全连通；最后，不能检测路由循环，不能建立策略路由。 因此，更为先进的边界网关协议b g p 诞生了。 ( 2 ) b g p 协议 边界网关协议b g p 是一种运行于i n t e r n e t 上的域间路由协议，用于自治系统之 间交换选路信息，选择到达目的网络的最佳a s 路径。目前b g p 协议已经成为运 行于i n t e r n e t 上的实质上的域问路由协议，它克服了e g p 协议的缺点，适合于解决 大型互连网的路由选择问题，较e g p 具有更优良的扩展性和更高的效能。 b g p 经历了不同的发展阶段，i e t f 先后为b g p 制定了多个标准【1 1 ”。1 9 9 5 年制定的b g p 一4 ，增加了对无类域间路由的支持，允许通告更小的网络地址空间， 支持路由聚合，以减少发送的路由更新数，同时具有对路由流量的控制能力，可 以设置b g p 路由更新的最小发送时间问隔。 尽管b g p 协议是为自治系统间的路由选择雨设计，但它也可以用于自治系统 内部，这样就有两种类型的b g p 会话连接：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 ) 和i b g p ( i n t e r i o r b o r d e r g a t e w a y p r o t o c 0 1 ) 。e b g p 用于分属于不同自治系统的b g p 路由器之间建立会话连接，进行通信的b g p 路由器通常存在于同一个物理介质和 子网上。i b g p 用于同一个自治系统内的b g p 路由器之间建立会话连接，用于在同 一a s 内边界路由器间交换外部路由信息，建立i b g p 会话的两个b g p 路由器不需 要彼此相邻，只要彼此相通并可以建立t c p 连接。通常运行b g p 协议的路由器称 为b g p 发言者，相互交换路由信息的b g p 发言者称为对等体。 b g p 协议不要求