（计算机科学与技术专业论文）bgp4路由振荡问题研究及优化实现.pdf

北京邮电大学硕卜学位论文 b g p 4 路由振荡问题研究及优化实现 摘要 边界网关协议( b g p ) 是i n t e m e t 域问路由的事实标准。本文主要涉及三方 面的内容。一是由于b g p 协议允许自治系统独立配置路由选择和播发策略，这 种局部配置可能导致全局策略配置的冲突和低效，从而引起的域问路由振荡问 题。对该问题，本文给出一种b g p 策略冲突动态检测方法，该方法基于有向竞 争图理论，通过构建竞争弧来发现路由策略冲突的a s 及相关路由。用路由相对 优先级来描述到同一目的两条路由的优选关系。根据竞争弧形成条件，如果相邻 两个a s 到达同一目的的两条路由相对优先级不同，这两个a s 的路由策略就存 在冲突。通过对b g p 协议进行修改，增加一个新的属性，该属性值为所选最佳 路由与先前最佳路出的相对优先级。最后通过s s f n e t 仿真试验证实了该方法 的有效性。二是由于b g p 路由反射器的引入而在自治系统内部产生的永久性路 由振荡和瞬时性路由振荡问题。该问题最早是被c i s c o 公司发现，目前主要有两 种解决办法。一种是针对m e d 值，建议在最佳路由选择过程中取消对m e d 值 的比较，或者对来自所有a s 的路由都进行m e d 值的比较。一种是针对b g p 协 议本身，建议通过对r f c l 7 7 1 协议规定的某些b g p 行为进行修改来避免路由振 荡的产生。本文在介绍最著名的w a l t o ne ta 1 提出的解决方案后，也提出了自己 的解决方案，不仅给出了相关的理论证明，而且还对这两个方案进行了比较，证 明在某些w a l t o ne ta 1 方案无效的情况下，本方案依然有效。最后简要介绍了当 前b g p 最为热门的问题：b g p 在i p v 6 上的扩展和运行。 关键字：b g p 竞争弧域问路由振荡瞬时性路由振荡 北京邮电大学硕士学位论文 o p t i m i z e r o u t eo s c i l l a t i o n si nb g p - 4 a b s t r a c t t h eb o r d e rg a t c w a yp r o t o c o l ( b g p ) h a sb e c o m et h ed e f a c t os t a n d a r df o r i n t e r - d o m a i nr o u t i n gi nt o d a y si n t e r n e t 1 1 1 i sa r t i c l er e f e r st ot h r e ep r o b l e m sw i d l b g p o n ei sr o u t eo s c i l l a t i o n sb e t w e e na s e sj u s tb e c a u s eb g p a l l o w se a c ha st o d e f i n ei t so w n r o u t i n gp o l i c i e si n d e p e n d e n t l y a n du s et h e mt os e l e c tt h eb e s tr o u t e s t h i sa r t i c l ei n t r o d u c e sad y n a m i cm e c h a n i s mb a s i n go nd i s p u t ea r ct h e o r yt od e t e c t a n ds u p p r e s sb g po s c i l l a t i o n st h a ta r i s eb e c a u s eo fp o l i c yc o n f l i c t s t h ei d e ai st o e x t e n db g pt oc a r r ya d d i t i o n a li n f o r m a t i o nc a l l e dr e l a t i v ep r o f e r e n c eo fr o u t e 、访t h e a c hu p d a t e t h er e l a t i v ep r e f e r e n c eo fr o u t ed e s c r i b e st h ep r e f e r e n c eo fr o u t e st ot h e s a n en e t w o r k a c c o r d i n gt h ed i s p u t ea r ct h e o r y 、i ft w o p e e r i n ga s e s r o u t e sw i t h t h e s a m en e t w o r kh a v ed i f f e r e n tr e l a t i v ep r e f e r e n c e ，i tm e a n st h a tp o l i c yc o n f l i c te x i t s b e t w e e nt h et w op e e r i n ga s e s s o 也i sn e wb g pe x t e n d i n ga t t r i b u t ec a nf i n dt h e p o s s i b l er o u t eo s c i l l a t i o n sb e t w e e na s e se f f e c t i v e l y , w h i c h t h en e t w o r ka d m i n i s t r a t o r c a nm o d i f yt h ea s p o l i c ya n dm a k et h eb g pr o u t e f o t i ns t a b l e t h ea u t h o rp r o v et h e i d e ab ys s f n e t s e c o n di sr o u t eo s c i l l a t i o nw i m i na na sb e c a u s eo fb g pr o u t e r e f l e c t i o n i ti sr e p o r t e di naf i e l dn o t i c ef r o mc i s c os y s t e m s t h ep e r s i s t e n tr o u t e o s c i l l a t i o n sm e a n st h a ts o m es u b s e to f t h er o u t e r sw i l i na na s m a ye x c h a n g er o u t i n g i n f o r m a t i o nf o r e v e rw i t h o u tb e i n ga b l et os e t t l eo nas t a b l er o u t i n gc o n f i g u r a t i o n t h e t r m a s i e n tr o u t eo s c i l l a t i o n sm e a n st h a ts o m es u b s e to fr o u t e r sm a yu n d e r g or o u t e o s c i l l a t i o n sd u et oat i m i n gc o i n c i d e n c es u c h 髂m e s s a g ed e l a y so rap a r t i c u l a ro r d e r j nw h i c hr o u t e r ss e n da n dr e c e i v em e s s a g e 。n o wt h e r ea r et w op o s s i b l ea p p r o a c h e s f o rs o l v i n gt h ep r o b l e m t h ef i r s ta p p r o a c hi st oc o n s 订a i nt h eu s eo fm e d s a c c o r d i n g t os o m e g u i d e l i n ei no r d e r t oa v o i do s c i l l a t i o n s 1 1 1 es e c o n d a p p r o a c hi st om o d i f yt h e c o r ep r o t o c o li t s e l fs u c ht h a tr o u t eo s c i l l a t i o n sa r ee l i m i n a t e di nt h em o d i f i e dp r o t o c 0 1 i nt h i sp a o e r t h ea u t h o r s u g g e s t a na l t e r n a t em o d i f i c a t i o nt ob g p p r o t o c 0 1 t h ea u t h o r n o to n l y p r e s e n tag r a p h - t h e o r e t i cm o d e l t op r o v et h ei d e ae f f e c t i v e ，b u ta l s op r o v i d e s o m eo s c i l l a t i o n e x a m p l e s w h e r eo t h e rs o l u t i o n sf a i l st oe l i m i n a t e r o u t i n g o s c i l l a t i o n s b u tt h i ss o l u t i o ni sa b l et oe l i m i n a t et h er o u t i n g1 0 0 p s t h e1 a s tt h i sp a p e r i n t r o d u c es i m p l yt h ec o n d i t i o n so f b g p p r o t o c o lo ni p v 6 k e y w o r d s ：p e r s i s t e n t o s c i l l a t i o nt r a n s i e n to s c i l l a t i o nr e f l e c t i o n 2 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 中请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：鲴盔章 日期：硅巫! 丕1 2 关于论文使用授权的说明 学位论文作者完全了解北京邮屯大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期问沦文工作的知识产权单位槲北京邮电大学。学校有权保 尉并向罔家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：术学位沧文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 凳 梦f 门期：迦。主：量 日期：出监。i ! 垒 北京邮电大学硕：匕学位论文 刖舌 随着互联网的不断扩展，最初仅限于a r p a n e t 及其卫星网的外部网关协议 e g p ( e x t e r i o rg a t e w a yp r o t o c 0 1 ) 已经不能满足用户的要求，用户不仅要求摆脱 e g p 那种核心式的网络拓扑结构，而且希望协议本身能够提供更加灵活的选路 策略，在这种情况下，i e t f 工作组制定出一种新型的协议标准即边界网关协议 b g p ( b o r d e r g a t e w a y p r o t o c 0 1 ) 。 1 9 8 9 年i e t f 公布了b g p 协议版本一( b g p 一1 ) 、1 9 9 0 年公布了版本二 ( b g p 2 ) 、1 9 9 3 年公布了版本三( b g p 3 ) ，目前最新版本为1 9 9 5 年制定的 b g p 4 。 作为一个自包含的自治系统问的路由协议，b g p 非常适合用于当前基于 t c w i p 和采用h o p b y - h o p 路由机制的i n t e r n e t ，并己经成为i n t e m e t 路由体系 的基础。 北京万林克通信技术有限公司近年来自主成功开发出了v l r t 系列路由器 产品，并实现了b g p 的基本功能。随着路由器产品的不断升级，对b g p 的功能 和性能也提出了更多更高的要求。在新的需求背景下，我对b g p 运行时产生的 域间路由振荡、自治系统内部由于b g p 路由反射器的引进而导致的域内路由振 荡以及当前b o p 在i p v 6 网络上的扩展这三方面的问题进行了较为深入的研究和 分析，在参考国内外相关理论的基础上提出了自己的解决方案，并在v l r t 路由 器上进行了有效的努力和尝试。 这篇论文是对我所做工作的一个较为全面的总结。全文共分为五章，内容如 卜| ： 第一章概述了计算机网络的发展历程，并简单介绍了当前i n t e m e t 协议簇中 最常用的一些域内路由协议。 第二章阐述了b g p 路由协议的基本原理、运行机制、路由策略等方面的内 容。 第三章详述了自治系统之间由于b g p 路由策略配置不当导致的域间路由振 荡问题，对当前国际上针对该问题的一些主流解决方案做出了评述，并在此基础 上提出了自己的解决方案。 第四章详述了b g p 路由反射器的原理和运行机制。并对路由反射器产生的 域内路由振荡问题做了详细的分析和说明，同时参照当前国际流行的解决思路， 北京邮电大学硕士学位论文 结合自己在研发过程中的实践经验，提出了切实可行的解决方案，并在数理模型 e 给出了相关证明。 第五章介绍了当前b g p 最热门的问题：b g p 在i p v 6 网络上的运行和扩展。 北京邮电大学硕士学位论文 第一章概述 1 1计算机互联网的发展历史及现状 1 9 6 9 年，为了能在爆发核战争时保障通信联络，美国国防部高级研究计划 署a r p a 资助建立了世界上第个分组交换试验网a r p a n e t ，连接美国四个大 学。a r p a n e t 的建成和不断发展标志着计算机网络发展的新纪元。 7 0 年代末到8 0 年代初，计算机网络蓬勃发展，各种各样的计算机网络应运 而生，如m i l n e t 、u s e n e t 、b i t n e t 、c s n e t 等，在网络的规模和数量上都 得到了很大的发展。一系列网络的建设，产生了不同网络之间互联的需求，并最 终导致了t c p ，i p 协议的诞生。 1 9 8 0 年，t c p i p 协议研制成功。1 9 8 2 年，a r p a n e t 开始采用i p 协议。 1 9 8 6 年美国国家科学基金会n s f 资助建成了基于t c p i p 技术的主干网 n s f n e t ，连接美国的若干超级计算中心、主要大学和研究机构，世界上第一个 互联网产生了，迅速连接到世界各地。9 0 年代，随着w e b 技术和相应的浏览器 的出现，互联网的发展和应用出现了新的飞跃。1 9 9 5 年，n s f n e t 开始商业化 运行。 1 9 9 4 年中国支持建设了c e r n e t 示范网工程，这是中国第一个全国性 t c p i p 互联网。 九十年代中期，随着h a t e m e t 网络规模持续增长，i p v 4 协议在许多方面已经 显得不太适应，难以满足日益增长的主机数量、应用种类以及安全方面的要求。 i n t e r n e t 工程任务组( i e t f ) 进行了下一代i p 网络协议i p n g ( i pn e x t g e n e r a t i o n ) 的研究，提出了新一代i p 网络协议、r 6 。作为向下一代互联网协议过渡的 重要步骤，1 9 9 6 年成立了国际i p v 6 试验网6 b o n e 。现在，6 b o n e 已经扩 展到全球5 0 多个国家和地区，成为i p v 6 研究者、开发者和实践者的主要平台。 2 0 0 4 年1 2 月2 5r ，中国下一代互联网示范工程c n g i 核心网c e r n e t 2 主干网开通暨c e r n e t 建设十周年庆祝大会在北京国际会议中心召开。国家发 展与改革委员会、教育部等八部委联合宣布，中国第一个下一代互联网，中国下 一代互联网示范工程c n g i 核心网c e r n e i 2 主干网正式开通，这是世界上规模 最大的i p v 6 互联网。此举标志着中国下一代互联网建设全面拉开序幕，在世界 下一代互联网发展中取得了先机。 北京邮电大学硕l 学位论文 1 2i n t e r n e t 协议簇中一些常见的域内路由协议 协议是网络的灵魂，而路由协议则日益成为i n t e r n e t 的灵魂。随着网络规模 的不断扩大，结构日趋复杂高效稳定的路由协议成为保障网络性能的重要因素。 在i n t e r n e t 上广泛应用的域内路由协议有r i p 、o s p f 、e i g r p 以及其他组织和 厂商的路由协议。 1 21r 口路由协议介绍 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 s ，路由信息协议) 是使用最广泛的距离向 量协议，它是由施乐( x e r o x ) 在7 0 年代开发的。当时，r i p 是x n s ( x e r o x n e t w o r k s e r v i c e ，施乐网络服务) 协议簇的一部分。r c p i p 版本的r 1 2 是施乐协议的改进 版。r i p 最大的特点是，无论实现原理还是配置方法，都非常简单。 r i p 的度量是基于跳数( h o p sc o u n t ) 的，每经过一台路由器，路径的跳数 加一。如此一来，跳数越多，路径就越长，r i p 算法会优先选择跳数少的路径。 r i p 支持的最大跳数是1 5 ，跳数为1 6 的网络被认为不可达。 r i p 中路由的更新是通过定时广播实现的。缺省情况下，路由器每隔3 0 秒 向与它相连的网络广播自己的路由表，接到广播的路由器将收到的信息添加至自 身的路由表中。每个路由器都如此广播，最终网络上所有的路由器都会得知全部 的路由信息。正常情况下，每3 0 秒路由器就可以收到一次路由信息确认，如果 经过1 8 0 秒，即6 个更新周期，路由项仍没有得到确认，它就会从路由表中删除。 卜豫j 的3 0 秒，1 8 0 秒和2 4 0 秒的延时都是由计时器控制，它 i 分别是更新计时 器( u p d a t et i m e r ) 、无效计时器( i n v a l i d t i m e r ) 和届新计时器( f l u s h t i m e r ) 。 距离向量类的算法容易产生路由循环，r i p 是距离向量算法的一种，所以也 不例外。如果网络上有路由循环，路由信息就会循环传递，永远不能达到目的地。 为了避免这个问题，r i p 等距离向量算法实现了下面四个机制：水平分割( s p l i t h o r i z o n ) 、毒性逆转( p 。i 廷f e v c r r e ) 、触发更蔌( t d g g 豇u p d a t e ) 积掷割定时 ( h o l d o w n t i m e r ) 。但即便采用了这四种方法，路由循环的问题也不能完全解决， 只是得到了最大程度的减少。一旦路由循环真的出现，路由项的度量值就会出现 计数到无穷大的情况。这是因为路由信息被循环传递，每穿过一个路由器，度量 值就加l ，一直加到1 6 ，路径就成为不可达的了。r i p 选择1 6 作为不可达的度 量值是很巧妙的，它既足够的大，保证了多数网络能够正常运行，又足够小，使 得计数到无穷大所花费的时间最短。 有些网络是n b m a ( n o n b r o a d c a s tm u l t i a c c e s s ，非广播多路访问) 的，即 网络上不允许广播传送数据。对于这种网络，r i p 就不能依赖广播传递路由表了。 解决方法有很多，最简单的是指定邻居( n e i g h b o r ) ，即指定将路由表发送给某一 北京邮电大学硕士学位论文 台特定的路由器。 r i p 虽然简单易行，并且久经考验，但是也存在着一些很大的缺陷，主要有 以下儿点： 1 ) 过于简单，以跳数为依据计算度量值，经常得出非最优路由； 2 ) 度量值以1 6 为限，不适合大的网络： 3 ) 安全性差，接受来自任何设备的路由更新； d ) 不支持无类i p 地址和v l s m ( v a r i a b l el e n g t hs u b n e t m a s k ，变长子网 掩码) ； 5 ) 收敛缓慢，时间经常大于5 分钟； 6 ) 消耗带宽很大。 12 2 o s p f 路由协议介绍 o s p f 是一种典型的链路状态路由协议。采用o s p f 的路由器彼此交换并保 存整个网络的链路信息，从而掌握全网的拓扑结构，独立计算路由。因为r i p 路由协议不能服务于大型网络，所以，i e 2 t 的i g p 工作组特别开发出链路状态 协议o s p f 。目前广为使用的是o s p f 第二版，最新标准为r f c 2 3 2 8 。 o s p f 路由器收集其所在网络区域上各路由器的连接状态信息，即链路状态 信息( l i n k s t a t e ) ，生成链路状态数据库( ：l i n k s t a t ed a t a b a s e ) 。路由器掌握了 该区域上所有路由器的链路状态信息，也就等于了解了整个网络的拓扑状况。 o s p f 路由器利用“最短路径优先算法( s b o r t e s t p a t h f i r s t ，s p f ) ”，独立地计算 出到达任意目的地的路由。 o s p f 协议引入“分层路由”的概念，将网络分割成由一个“主干”连接的 组相互独立的部分，这些相互独立的部分被称为“区域”( a r e a ) ，“主干”的 部分称为“主干区域”。每个区域就如同一个独立的网络，该区域的o s p f 路由 器只保存该区域的链路状态信息。每个路由器的链路状态数据库都可以保持合理 的大小，路由计算时间、报文数量都不会过大。 根据路由器所连接的物理网络不同，o s p f 将网络划分为四种类型：广播多 路访问型( b r o a d c a s tm u l t i a c c e s s ) 、非广播多路访问型( n o n eb r o a d c a s t m u l t i a c c e s s ，n b m a ) 、点到点型( p o i n t t o - p o i n t ) 、点到多点型 ( p o i n t t o m u l t i p o i n t ) 。 在多路访问网络上可能存在多个路由器，为了避免路由器之间建立完全相邻 关系而引起的大量开销，o s p f 要求在区域中选举一个d r 。每个路由器都与之 建立完全相邻关系。d r 负责收集所有的链路状态信息，并发布给其它路由器。 选举d r 的同时也选举出一个b d r ，在d r 失效的时候，b d r 担负起d r 的职 北京邮电大学硕士学位论文 贝。 o s p f 协议操作步骤： 1j 建立路由器的邻按关系 2 ) 选举d r b d r ： 3 ) 发现路由器； 4 ) 选择适当的路由器； 5 ) 维护路由信息。 123e l g r p 路由协议介绍 加强型内部网关路由协议( e i g r f ) 是c i s c o 公司开发的距离矢量路由协议， 支持i p 、i p x 等多种网络层协议。由于t c p i p 是当今网络中最常用的协议，故 本文只讨论i p 网络环境中的e i g r p 。 e i g r p 是一个平衡混合型路由协议，既有传统的距离矢量协议的特点：路 由信息依靠邻居路由器通告，遵守路由水平分割和反向毒化规则，路由自动归纳， 配置简单，又有传统的链路状态路由协议的特点：没有路由跳数的限制，当路由 信息发生变化时，采用增量更新的方式，保留对所有可能路由( 网络的拓扑结构) 的了解、支持变长子网掩码、路由手动归纳。该协议同时又有自己独特的特点： 支持非等成本路由上的负载均衡，采用差分更新在确保无路由环路的前提下，收 敛迅速。因而适用于中大型网络。 e i o r p 的一些常用术语和概念： 1 ) 在e i g r p 中，有五种类型的数据包： h e l l o ：以组播的方式发送，用于发现邻居路由器，并维持邻居关系。 u p d a t e ：当路由器收到某个邻居路由器的第一个h e l l o 包时，以单点传送方 式回送一个包含它所知道的路由信息的更新包。当路由信息发生变化时，以组播 的方式发送一个只包含变化信息的更新包。注意，两个更新包的内容不一样。 q u e r y ：当一条链路失效，路由器重新进行路由计算但在拓扑表中没有可行 的后继路由时，路由器就以组播的方式向它的邻居发送一个查询包，以询问它们 是否有一条到目的地的可行后继路由。 r e p l y ：以单点的方式回传给查询方，对查询数据包进行应答。 a c k ：以单点的方式传送，用来确认更新、查询、答复数据包，以确保更新、 查询、答复传输的可靠性。 2 ) 可行距离( f e a s i b l e d i s t a n c e ) ：到达一个目的地的最短路由的度量值。 3 ) 后继( s u c c e s s o r ) ：后继是一个直接连接的邻居路由器，通过它具有到达 目的地的最短路由。通过后继路由器将包转发到目的地。 北京邮电大学领j 二学位论文 4 ) 通告距离( a d v e r t i s ed i a t a n c e ) 达某个月的地的最短路由的度量值。 5 ) 可行后继( f e a s i b l es u c c e s s o r ) 相邻路由器所通告的相邻路由器自己到 可行后继是一个邻居路由器，通过它可 以到达日的地，不使用这个路由器是因为通过它到达目的地的路由的度量值比其 他路由器高，但它的通告距离小于可行距离，因而被保存在拓扑表中，用做备择 路由。 6 ) 可行条件( f e a s i b l ec o n d i t i o n ) ：上述四个术语，构成了可行条件，是e i g r p 路由器更新路由表和拓扑表的依据。可行条件可以有效地阻止路由环路，实现路 由的快速收敛。 7 ) 活跃状态( a c t i v es t a t e ) ：当路由器失去了一条路由的后继而有一个可 行后继，或者再找到一个后继时，该路由进入被动状态，是一条可用路由。 e i g r p 的运行： 初始运行e i g r p 的路由器都要经历发现邻居、了解网络、选择路由的过程， 在这个过程中，同时建立三张独立的表：列有相邻路由器的邻居表、描述网络结 构的拓扑表和路由表，并在运行中网络发生变化时更新这三张表。 1 ) 建立相邻关系 运行e i g r p 的路由器自开始运行起，就不断地用组播地址从参与e i g r p 的 各个接口向外发送h e l l o 包。当路由器收到某个邻居路由器的第一个h e l l o 包时， 以单点传送方式回送一个更新包，在得到对方路由器对更新包的确认后，这时双 方建立起邻居关系。 2 ) 发现网络拓扑，选择最短路由 当路由器动态地发现了一个新邻居时，也获得了来自这个新邻居所通告的路 由信息，路由器将获得的路由更新信息首先与拓扑表中所记录的信息进行比较， 符合町行条件的路由被放入拓扑表，再将拓扑表中通过后继路由器的路由加入路 由表，通过可行后继路由器的路由如果在所配置的非等成本路由负载均衡的范围 内，则也加入路由表，否则，保存在拓扑表中作为备择路由。如果路由器通过不 同的路由协议学到了同一目的地的多余路d j ，则比较路由的管理距离，管理距离 最小的路由为最优路由。 3 ) 路由查询、更新 当路由信息没有变化时，e i g r p 邻居间只是通过发送h e l l o 包来维持邻居关 系，以减少对网络带宽的占用。在发现一个邻居丢失、一条链路不可用时，e i g r p 立即会从拓扑表中寻找可行后继路由器，启用备择路由。如果拓扑表中没有后继 路由器，由于e i g r p 依靠它的邻居来提供路由信息，在将该路由置为活跃状态 后，向所有邻居发送查询数据包。 北京邮电人学硕士学位论文 如果某个邻居有一条到达目的地的路由，那么它将对这个查询进行答复，并 且不再扩散这个查询，否则，它将进一步地向它自己的每个邻居查询，只有所有 查询都得到答复后，e i g r p 才重新计算路由，选择新的后继路由器。 北京邮电大学硕_ 上学位论文 第二章边界网关协议b g p 一4 的简介 边界网关协议b g p “2 1 ( b o r d e rg a t e w a yp r o t o c l ) 是一个外部路由选择协议， 尽管这个概念可以应用于任何互联网，但它是为采用t c p i p 协议簇的互联网的 连接而丌发的。b g p 已经成为因特网的有限选用的外部路由协议。 b g p 的设计目的是为了使在不同的自治系统中的路由器能够互相协作，交 换路由信息。协议的运行以报文为基础，通过t c p 连接传送。 2 1b g p 基本工作原理 b g p 路由器通过建立连接来交换报文，建立连接的两个b g p 路由器互称为 邻居。在不同的自治系统间的b g p 连接，称为外部连接( e b g p ) ；相应的，在 同一自治系统内的b g p 连接称为内部连接( m g p ) 。类似的，b g p 邻居如果在 不同的自治系统内，称为外部邻居，如果在同一自治系统内，则称为内部邻居。 b g p 执行三种路由选择，即自治系统间的系统路由选择、自治系统内的系 统路由选择和通过自治系统的系统路由选择。 自治系统间的系统路由选择发生在不同自治系统的两个或多个b g p 路由器 之间。在这些系统中，相邻路由器使用b g p 维护互联网络拓扑结构的一致性。 在自治系统问通信的相邻b g p 路由器必须驻留在同一物理网络上。互联网络就 是一种使用这种路由选择的例子，因为它由自治系统或可管理的域组成。这些域 代表不同的机构、公司和实体，它们组成了互连网络。在i n t e m e t 中，b g p 被频 繁使用，以提供优化的路由选择路径。 自治系统内的系统路由选择发生在同一自治系统的两个或多个b g p 路由器 之| 日j 。在同一自治系统中，邻居路由器使用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 交换信息。 2 2b g p 运行机制 无论使用何种路由选择协议，都将维护路由表，传输路由选择更新报文，并 在路由选择规则的基础上做出路由选择的决策。b g p 系统的主要功能是其它 b g p 系统交换网络可达性信息，其中包括自治系统路径的列表信息。利用信息 可以构造自治系统的连接图，删除其中的路由循环，并强制实施自治系统级的策 各。 每个b g p 路由器都维护一个路由表，路由表中列出了一个特定网络中所有 可行的路径。然而，这个路由器不更新路畦j 表，因此，从同级路由器接收的路由 信息将一直被保留，直到接收到一个新增加的路由信息。在对数据交换进行初始 化并增加更新信息后，b g p 设备交换路由信息。对一个首次连接网络的路由器 而言，在初始化时，b g p 路由器交换他们全部的路由表。与此类似，当路由表 发生变化时，路由器将路由表变更部分发送出去。b g p 路由器不是定期发送路 由更新报文，而且b g p 路由更新报文只发布去往目的网络的最佳路径。 b g p 使用一个单独的路由选择计量标准，该标准决定了一个已知网络的最 佳路径。b g p 计量值一般由网络管理员指定给每一个连接，它可以是路径通过 的自治系统的数目、稳定性、速度、延迟或开销等。 2 21b g p 路由的分发和存储 路由定义为一个单元，包括路由目标和要到达目标的路径。在b g p 中，是 利用更新报文来发送路由信息。路由目标就是m pr e a c hn l r i 属性中n l r i 域携带的i p 地址等信息，路径则是同一消息中p a t h 域中的信息。 路由存储在路由信息库( r o u t i n gi n f o r m a t i o nb a s e ，r i b ) 内。路由信息库包 括三部分：a ) a d j _ r i b si n ：这个部分存储接收的更新报文携带的路由信息，这里 存储的路由信息是作为b g p 选路决策过程的输入：b ) l o er i b ：依据本地规则 从a a j j t i b j n 中选出的路由：c ) a d j _ r i b s o u t ：路由器选出来发送给b g p 邻居 的路由信息，这些信息在通告给邻居时是用更新报文来携带。 b g p 路由器在发送路由之前，可能会修改路由的p a t h 属性。 如果一条以前通告的路由已经不可用，那有三种撤销路由的方法： a ) 在更新报文的“撤销的路由”域内告知对方撤销路由的i p 地址前缀： b ) 在更新报文中发送一个替代的路由： 北京邮屯大学硕七学位论文 c ) 关闭两个b g p 路由器之间的连接，则路出器互相都把对方发送过来的路 由清除了。 22 2b g p 报文的报头 t c p 只在两个建立了连接的程序之问提供一个“可靠字节流”，而像b g p 这样的路山协议实际交换的是路由信息。这样b g p 协议就得包括一个“定界” 功能，以便在无关的报文集合中分离各种字节流。这很容易实现，只需要在所有 b g p 报文前附加一个包括路由报文长度的定长的“报头”即可。如图2 - 1 所示。 0781 51 6 2 32 4 3 1 标记 长度类型 图2 - 1 ：b g p 报头格式 其中，标记的用途之一是在分段过程中提供一定的“冗余”，在验证安全时 也有一定作用；长度字段指出包括b g p 报头在内的报文的字节数；类型字段则 定义了报文的类型。目前定义的报文类型有以下几种( 见表2 1 ) ： 报文类型符号类型值 打开 o p e n 1 更新 u p d a t e 2 通告 n o t i f i c a t i o n3 存活 k e e p a l i v e 4 表2 - 1 ：b g p 的扳文类型 2 2 3 打开( o p e n ) 报文 一旦b g p 连接建立，双方就各发送一个o p e n 报文去协商连接的参数。如 图22 所示。 北京邮屯大学硕 二学位论文 0781 51 6 2 32 43 1 标记 长度类型版本 自治系统号( a s )持续时间( h o l dt i m e ) b g p 标识符 口 选参数长度 。司选参数 图2 - 2 ：b g p 打开( o p e n ) 报文格式 版本域是b g p 的版本号，当前是4 ；i j 治系统指出发送端的自治系统号码； 持续时问是发送端建议的连接保持时间；b g p 标识符是发送端路由器的标识符； 可选参数由一系列的元组携带，每个元组可以携带一个参数。元组定义为 。 目前定义的参数有： a ) 验证信息参数( 类型为1 ) 验证信息参数的参数值中第一个字节为验证码，其后就是验证数据。验证码 呵以决定验证数据的组成和含义，还可以决定计算报头标记的算法。 b ) b g p 能力参数( 类型为2 ) 这是一个用于b g p 路由器间协商b g p 能力的一个参数。支持协商的b g p 路由器向邻居发送一个打开报文，其中的能力参数包含它所支持的能力代码。如 果对方也支持这些能力代码，那么就建立连接，否则会发送一个通告报文给发送 方，告知能力代码不支持，二者之间的连接终止。 在未出现冲突或版本矛盾的情况下，本地工作站在决定与对方建立连接之前 还要验证对方。在接收到打开请求时，b g p 工作站就检查进来的自治系统是否 “可接受”，标识符是否为有效的地址，以及可选参数是否为有效值。如果这些 条件有一个失败，连接就会终止。 拒绝并关闭一个t c p 连接可以通过发送一个解释出错原因的通报报文来完 成，而接受一个连接则通过发送k e e p a l i v e 报文来完成。 北京邮电大学硕士学位论文 2 2 4 更新( u p d a t e ) 报文 更新报文用来在b g p 邻居之间传递路由信息。使用更新报文中携带的路由 信息，b g p 路由器可以得到描绘不同自治系统之间的关系图。 更新报文用来向邻居通告一条可行的路由，或者用来撤销多条不可行的路 由。消息总是携带个定长的b g p 报头，其它的域如图2 3 所示。 不可达路由长度( 一个字节) 撤销路由( 长度可变) 路径属性长度( 两个字节) 路径属性( 长度可变) 网络层可达信鼠( n l r i ) 图2 - 3 ：b g p 更新报文格式 图2 3 中： 不可达路由长度：指出“撤销路由”域的字节数； 撤销路由：是由一系列元组 组成。长度占用一个字节，指 出地址前缀的比特数。地址前缀包含撤销的i p 地址前缀； 路径属性长度：用两个字节指出“路径属性”域的字节数。 路径属性：由一系列元组 组成。“属性类型” 由两个字节组成。“属性长度”根据属性类型的值可能为一个字节或两个字节， “属性值”则携带的是具体的路径属性。 2 25 存活( k e e p a l i v e ) 报文 b g p 路由器也要不断监视其邻居的可达性。它需要周期性发送存活报文来 实现。存活报文没有内容，仅仅包含1 9 字节的b g p 报头。 然而，只发送定期探测并不能保证链路联系会正常工作。路由器还必须检查 报文能定期从对方发来。在打开交换期间，b g p 工作站已经宣布过一个持续时 间，即对方应该在连续的报文之间等待的最大延时。如果在这个延时内没有接收 到报文，就表明对方已经停止正常工作。 由于传输延时不是一个常量，所以工作站发送报文的周期要短于持续时间所 指示的时间周期。大概在该周期内平均发送3 个报文。 北京邮电大学硕士学位论文 2 2 6 通告( n o t i f i c a t i o n ) 报文 通告报文编码如图2 - 4 ： 图2 - 4 ：b g p 通告报文格式 在通告报文里，紧跟1 9 个字节的报头后的是错误代码、错误子代码以及可 变长度的数据。该长度可以从报文长度推断出来。定义的一些错误代码和子代码 详见表2 2 所示： 错误代码错误代码符号名称错误子代码 子代码符号名称 l 连接不同步 i 报头错误2报文长度不正确 3 报文类型不正确 1 不支持的版本号 2 不匹配的自治系统号 3 b g p 标识符不正确 2 打开搬文错误4 不接受的验证代码 5验证失败 6 不接受的抑止时间 7 不支持的能力参数 l 属性d 表畸形 2 无法识别的已知属性 3丢失熟悉属性 4 属性标志错 5 属性长度错 3 更新报文错误 6无效的源属性 7 自治系统路由循环 8 无效的下一跳属性 9 可选属性错 1 0 无效的网络域 l la sp a t h 错误 4 抑止定时器错误 5 有限状态机错误 6 终止 表2 - 2 ：通告报文的错误代码和错误子代码 北京断电大学硕士学位论文 2 3b g p 路径属性 b g p 路径属性分为4 大类，分别是： 1 ) 公认必选：b g p 的u p d a t e 报文中必须存在的属性。它必须能被所有的 b g p 工具识别。公认必选属性的丢失意味着u p d a t e 报文出错。这是为了保证所 有的b g p 工具统。于一套标准的属性。 2 ) 公认自决：能被所有b g p 识别的属性，但在u p d a t e 报文中可发可不发。 3 ) 可选传递：如果b g p 工具不能识别可选属性，它就去找过渡属性位。如 果此属性是过渡的，b g p 工具就接受此属性，并把它向前传递给其它b g p 路由 器。 4 ) 可选非传递：当可选属性未被识别，且过渡属性也未被置位时，此属性 被忽略，不传递给其它b g p 路由器。 路径属性类型主要有以下几种： o r i g i n ( x y p ec o d e = l ，公认必选属性) 指示此路由起始类型( 如表2 3 所示) ； 值意义 oi g p 一路由信