（计算机科学与技术专业论文）bgp路由策略检查工具的设计与实现.pdf

独创性( 或创新性) 声明 i i h i l l l f f l l l i l li i l l l l l l l l l l l l lr i j i f i i j l l l f 舢 y 1 7 6 1 1 0 , l , t 1 2 l l l l l i i 7 i i i i i i l i i i i 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： i 堑至! 蛀 日期： 旌f 里：主：! ! 关于论文使用授权的说明 本人完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在 校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校 可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。 本人签名： 导师签名： 日期：一印p 墨一 。p毫v， ，0 b g p 路由策略检查工具的设计与实现 摘要 边界网关协议( b g p ) 是一个域间路由协议，用来在自治系统 ( a s ) 之间交换路由的可达信息，它允许在不泄露自身拓扑和策略 的条件下自主选择路由并传递路由信息。近期的研究显示，很多个 a s 自主配置本地策略的相互作用，有可能产生b g p 策略的冲突以致 造成路由的路由振荡，路由振荡会明显的降低端到端的网络性能，破 坏网络的正常使用。因此，为了稳定路由，避免这些b g p 策略冲突 是很重要的。 本文分析了i n t e m e t 中a s 间的关系、a s 的策略配置，并讨论了 在路由配置中发生错误配置的种类。通过对比多种网络策略语言，确 定使用现今通用的路由策略描述语言r p s l 来描述b g p 路由策略， 并详细介绍了该语言的使用，及其应用到不同a s 间商业关系的路由 描述方法。 本文具体实现了一种检查b g p 路由策略的工具，该工具首先可 以从文法、语法上检查输入的配置文件语句的正确性，并且综合多个 a s 的配置文件检查配置的策略，发现其中有策略冲突的地方。通过 建立拥有所有有用信息的b g p 级别的网络模型，比较其中的路由信 息，检查出路由配置中典型的两类错误i 更新源配置错误和输出配置 错误。 最后，使用路由模拟软件c b g p 对既定的网络拓扑进行模拟仿 真，同时使用该工具对相同的网络配置进行检测，得到了一致的结果， 对该工具进行了验证。 关键词：边界网关协议策略语言自治系统策略检查 气 警 r 麓 d e s i g na n di m p l e m e n t 口i o no fa t o o lf o r b g ，pr o u t i n gp o u c yd e t e c t i o n a b s t r a c t t h eb o r d e rg a t e w a yp r o t o c o l ( b g p ) a l l o w sa l la u t o n o m o u ss y s t e m ( a s ) t o a p p l y d i v e r s el o c a lp o l i c i e sf o rs e l e c t i n gr o u t e sa n dp r o p a g a t i n gr e a c h a b i l i t y i n f o r m a t i o nt oo t h e rd o m a i n sw i t h o u td i v u l g i n gi t si m e m a lt o p o l o g ya n dt h e i rp o l i c i e s t oo t h e r s r e c e n ts t u d i e sh a v es h o w nt h a tac o l l e c t i o no fa s e sm a yh a v ec o n f l i c t i n g b g pp o l i c i e st h a tl e a dt or o u t ed i v e r g e n c e r o u t ed i v e r g e n c ec a nr e s u l t i nr o u t e o s c i l l a t i o n ，w h i c hc a ns i g n i f i c a n t l yd e g r a d et h e e n d t o e n dp e r f o r m a n c eo ft h e i n t e r n e t a v o i d i n gt h e s ec o n f l i c t i n gb g pp o l i c i e si sc r u c i a l f o rt h es t a b l i l i t yo ft h e i n t e r n e tr o u t i n gi n f r a s t r u c t u r e t h i sp a p e rs u m m a r i z e st h er o u t i n gc o n f i g u r a t i o nb a s e do na sr e l a t i o n s h i pa n d t h ec a t e g o r yo fm i s c o n f i g u r a t i o n n e x t ，as u r v e yo fc u r r e n tn e t w o r kp o l i c yl a n g u a g e s i sp r e s e n t e d t h e n ，t h er p s l ( r o u t i n gp o l i c ys p e c i f i c a t i o nl a n g u a g e ) ，w h i c hi s p o p u l a ru s e d ，i st a k e n a st h el a n g u a g ef o rs p e c i f y i n gt h eb g pr o u t ep o l i c y t h i sp a p e r p r o v i d e sag u i d e o nh o wt ou s et h el a n g u a g eo ns p e c i f y i n gt h ea s e sr e l a t i o n s h i p i nt h i sp a p e r , at o o li sd e v e l o p e dt oa n a l y s et h ec o r r e c t n e s so ft h er o u t i n g c o n f i g u r a t i o ni nr p s la n dt od e t e c tt h ec o n s i s t e n c yo ft h ec o n f i g u r e dp o l i c ya n d a c t u a lr o u t i n g b a s e do nt h ec o m p a r i s o nb e t w e e na l ln e c e s s a r yi n f o r m a t i o n i na n e t w o r km o d e la tt h eb g pl e v e la n da c t u a lb g pr o u t i n g ，t h et o o lc a n d e t e c tt w ok i n d s o fm i s c o n f i g u r a t i o n ，o n ei so r i g i nm i s c o n f i g u r a t i o n s ，t h eo t h e r i st h e e x p o r t m i s c o n f i g u r a t i o n s a tl a s t ，u s i n gab g pd e c i s i o np r o c e s ss i m u l a t o r ( c b g p ) t oe m u l a t eo n eo ft h e n e t w o r kt o p o l o g y , a n dd e t e c ti tu s i n gt h i st o o l ，f i n a l l y , t h er e s u l t sa r ec o n s i s t e n ta s e x p e c t e d k e yw o r d s ：b o r d e rg a t e w a yp r o t o c o l ( b g p ) ，p o l i c yl a n g u a g e ， a u t o n o m o u ss y s t e m ，p o l i c yd e t e c t i o n p i i r ；办 广 目录 第一章绪论1 1 1 背景1 1 2 国内外研究现状1 1 3 主要工作3 1 4 论文组织结构4 第二章课题相关技术综述5 2 1 边界网关协议概述5 2 2b g p 消息格式6 2 2 1o p e n 消息格式7 2 2 2k e e p a l i v e 消息格式8 2 2 3n o t i f i c a t i o n 消息格式8 2 2 4u p d a t e 消息格式9 2 3b g p 路径属性1 0 2 3 1o r i g i n 属性1 1 2 3 2a sp a t h 属性1 2 2 3 3n e x th o p 属性1 2 2 3 4m e d 属性1 2 2 3 5l o c a lp r e f e r e n c e 属性1 3 2 3 6c o m m u n i t y 属性1 4 2 4b g p 状态机及选路1 4 2 4 1b g p 状态机1 4 2 4 2b g p 选路过程1 6 2 5a s 分类及a s 间的关系1 7 2 6 本章小结1 8 第三章路由配置及策略配置检查1 9 3 1 路由配置的错误种类1 9 3 1 1 更新源配置错误1 9 3 1 2 路由路由输出配置错误2 0 3 2 更新源配置错误检查分析2 0 3 3 路由输出配置检查分析2 l 3 3 1a s - s e t 集合向有向树模型的转化2 3 3 3 2 链路关系等价策略的推导2 3 3 3 3a s 间商业关系的判定2 5 3 4 本章小结2 6 第四章路由策略检查工具的系统设计与实现2 7 4 1 需求和总体设计2 7 4 2 策略的r p s l 描述2 9 4 2 1 现有网络路由描述语言2 9 4 2 2r p s l 语言介绍3 l 4 2 3a s 间多种商业关系的r p s l 描述3 2 4 3 文法检查模块的设计与实现3 8 4 3 1l e x 、y a c c 介绍3 8 4 3 2 使用l e x 进行文法分析4 2 4 3 3 使用y a c c 进行语法分析4 6 4 4 策略检查模块的设计与实现4 9 4 4 1 数据库的设计4 9 4 4 2 策略检查实现5 1 4 4 3 错误路径的匹配5 4 4 5 本章小结5 5 第五章检查工具的验证5 6 5 1 检查工具功能性测试5 6 5 1 1 单个a s 配置文件的检查5 6 5 1 2 多个a s 策略的检查5 7 5 2c b g p 仿真5 9 5 2 1c b g p 概述5 9 5 2 2c - b g p 的安装6 0 5 2 3 模拟结果6 1 5 3 本章小结6 2 第六章结束语6 3 6 1 论文工作总结6 3 6 2 问题和展望6 3 ， 北京邮电大学工学硕士论文 1 1 背景 第一章绪论 随着网络业务的蓬勃发展，网络规模不断扩大，为了使全球网络拓扑信息能 快速有效的进行传播，边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，b g p ) 1 1 l 【2 】发挥着巨 大的决策作用。i n t e m e t 网络上各个自治系统之间就是采用b g p 协议来实现域问 路由信息的交互。 i n t e m e t 网络是由不同的自治系统( a u t o n o m o u ss y s t e m ，a s ) 构成，这些a s 可能分别属于不同的i n t e r n e t 服务提供商( i n t e r n e ts e r v i c ep r o v i d e r ，i s p ) 。在a s 内部，路由是通过域内路由协议交互信息，例如有o s p f 、i s i s 、r i p 协议等； 而在a s 之间是通过b g p 协议来实现。b g p 允许使用基于策略的选路，由自治 系统管理员制定策略，并通过配置文件将策略指定给b g p 。当到达目的地有多 条路径可供选择时，可以依据自身的策略从中进行选择，并控制信息的重发送。 选路策略与安全或经济因素有关。在当前的网络研究应用中，有很多评估实际 b g p 路由的工具，例如：p i n g ，t r a c e r o u t e ，b g p t a b l ed u m p 等。当配置的策略有 错误，会发生路由策略冲突，导致路由泄露，严重的会影响网络的性能。因此， 随着网络规模的日益扩大和网络策略的更加复杂，检查网络的策略更是尤为重 要。 路由策略是b g p 中重要的功能，在配置的过程中会有很多配置错误的情况 发生。策略的违反可能会导致连接、安全、经济上的问题。一个众所周知的问题 就是抢占地址空间，一个a s 偶然广播其他a s 所拥有的网络地址前缀，会在网 络上形成“黑洞。另一个策略问题通常和a s 相关的经济关系有关。 本文作者在毕业设计阶段参加了原北京网通的b g p 研究项目，对在a s 域 内的一些不同的配置引起b g p 路由振荡进行了分析和研究，撰写了( ( i b g p 路由 振荡问题分析及解决方案。本文在此基础上，结合原北京网通的b g p 运维要求， 针对b g p 策略配置的正确性检查进行研究，设计和实现了一个系统工具来诊断 定位发现违背策略的a s ，进而能够修改相应配置，避免造成更大的影响。 1 2 国内外研究现状 b g p 协议这种复杂的路由协议，它灵活的自主配置策略机制带来方便的同 时，也不可避免的存在错误的策略配置进而引发路由振荡【3 - 5 】的后果。目前提出 北京邮电大学工学硕士论文 来的基于策略的b g p 路由振荡的解决方法有两种：一种是静态方法，在没有发 生路由振荡的情况下，对路由策略进行分析，发现冲突的路由策略，并加以修改； 另一种是动态方法，引入额外的路由振荡检测机制，在交换路由信息的过程中， 发现并消除路由振荡。 v a r a d h a n 首先提出讨论b g p 持续路由振荡问题并定义了安全性的概念1 6 j 。 他认为，路由振荡的原因并不是单一的a s 策略配置问题，而是由于很多个a s 之间的交互才引发的问题。在没有配置错误的情况下也是有可能发生的，而且由 于a s 更倾向于保持自己a s 域内策略的保密性，所以，它更难于检测和解决。 g o v i n d a nr ，a l a e t t i n o g l uc ，e d d yg 等人提出以路由注册的方式进行全球 合作来避免路由策略冲突的产生【7 】。这个机制主要包含了这样几个部分：一是 r p s l 羽，r p s l 是i e t f 用于描述路由策略的高级语言；二是路由注册器( r o u t i n g r e g i s t r y ) ，a s 管理员会将自己的策略注册到互联网路由注册处( i r r ，i n t e m e t r o u t i n gr e g i s t r y ) 【9 】；三是分析所收集策略的工具，这个工具用来检测连通性和 策略冲突并进行管理。 g a r yn s t o n e 提出一种基于路径的策略描述语言p p l ( p a t h b a s e dp o l i c y l a n g u a g e ) 1 1 0 1 ，这个语言将策略规则转化为描述网络服务以及接入控制信息的形 式化逻辑，再编写编译器来评估网络策略规则的正确性并且返回有冲突策略的信 息，这里的正确性包括策略规则的句法和语义上的正确。 g a o 和r e x f o r d 提出【1 1 】由分级结构、过滤和网络拓扑等限制来确保路由的稳 定，并表明网络经济会自然保障路由的稳定。其基本思想是，利用a s 间的经济 关系形成的互联网层次结构，为达到目的网络的路由设定一个偏序关系，这种基 于a s 图的业务分级结构和与之相匹配的a s 间的多种商业协议足以使b g p 协议 收敛。在这个结构中假设了三种a s 关系( 见2 5 ) ，以及由此，根据商业关系制 定路由策略( 见3 1 2 ) ，g a o 和r e x f o r d 规定不允许存在客户提供者循环( 例 如，不能有a s 经过若干个提供者后，又成为自己的非直接客户) 。 n i c kf e a m s t e r 和h a r ib a l a k r i s h n a n 开发了【1 2 j 用p e r l 语言编写的词法检查器 r o e ( r o u t e rc o n f i g u r a t i o nc h e c k e r ) ，用来检查影响网络可达性的两类错误1 1 3 l ：路由 有效性错误( r o u t ev a l i d i t yf a u l t s ) ：路由器可能学习到一条不可用的路径；路径 可见性错误( p a t hv i s i b i l i t yf a u l t s ) ：路由器可能没有学习到网络中实际存在的路 径。r c c 分为三个模块：1 ) 预处理( p r e p r o c e s s o r ) ：对路由器配置文件进行预处 理，检查路由配置的关键字识别该配置文件是何种类型的路由器的配置，并将该 配置文件翻译为更接近于一般配置句法的文件；2 ) 语法分析器：将由预处理得 到的文件内容转变成形式化表达；3 ) 约束检查器：检查限制条件。 tg r i f f i n ，gw i l f o n g 首先提出了【1 4 】一种安全路径矢量协议s p v p ( s a f ep a t h 2 f 北京邮电大学工学硕士论文 v e c t o rp r o t o c 0 1 ) 。它通过在b g p 路由中增加历史属性( h i s t o r y ) ，使其携带路 由变化的历史信息，并利用这些信息以及相应的检测算法，来判断是否因路由冲 突而产生了路由振荡。tg r i f f i n ，gw i l i n g 又利用稳定路由问题( s t a b l ep a t h s p r o b l e m ，s p p ) 模型形式化地抽象出b g p 协议行为，并为此基础提出了一种分布 式的策略冲突检测算法【1 5 1 1 1 6 1 。使用这个框架，能够为路由收敛提供一个充分条 件，即不存在争执环( d i s p u t ew h e e l ) 。争执环是指在有振荡的网络中引起策略 冲突而发生振荡的节点环，现在，唯一知道的一个方法是需要检查网络中所有的 路由策略是否有争执环，但是，这个方法在实际的网络应用中很不现实。另外， g r i f f i n 证明了即使知道了所有网络的策略，要检查其中是否是稳定路由仍是一个 n p 完全问题1 1 7 j 。 v i l l a m i z a rc ，c h a n d r ar ，g o v i n d a nr 等人提出【1 8 】一种路由振荡衰减机制 ( r o u t ef l a pd a m p e n i n o 。这个机制即是有选择的限制不稳定路由信息的传播。它 的工作机制如下：每一个b g p 发言者维持一个和通告给b g p 邻居的每一个前缀 相联系的路由惩罚值，这个值随着路由状态改变而增长也会随着时间而指数倍的 衰减，也就是事实上，这个惩罚值被用来衡量一条路由的不稳定性。路由器使用 本地配置的极限值来决定禁用这条路由的时间和后来重用这条路由的时间。 综上所述，无论是静态的检测方法还是动态的检查方法，都具有一定的局限 性，并不能很好的路由配置冲突引起的路由振荡问题，所以，还需要进一步的研 究和探索。 1 3 主要工作 本文的主要研究是研究b g p 路由策略配置的正确性，将不同a s 的策略用 r p s l 语言描述，作为工具的输入，通过编写的编译器来检查策略配置语句，并 检查所配置的策略，返回有冲突策略的信息。 r p s l 描述的路由策略主要通过路由过滤来配置的，一个过滤器由匹配标准 和一个动作集组成。b g p 路由更新报文中几乎所有的属性都能被用来描述匹配 标准，可以再用上a s 路径和网络前缀等。当一个路由更新报文满足了某个匹配 标准，那么就会执行相应的动作，这个动作包括允许，禁止或者修改路由。过滤 器能够被用在路由起源、输入和输出过程。使用r p s l 语言描述策略，能够在很 大程度上屏蔽低一级的细节的配置，而在宏观上使人们更容易发现其中的策略违 背的地方。 该检查工具能够在语法和语义上对策略进行验证，并且能静态检测不同a s 间的b g p 策略的关系。本检查工具的开发使用了l e x 、y a c c 工具软件，来帮助 生成检查工具。本检查工具能够检查描述b g p 策略配置的r p s l 描述的正确性， 3 北京邮电大学工学硕士论文 并将识别出的策略存入数据库，通过数据库数据之间的比较发现冲突配置，返回 配置错误的路径。最后，论文还使用了b g p 仿真软件c b g p 模拟验证本工具。 1 4 论文组织结构 本论文对使用r p s l 语言描述的a s 的路由配置以及a s 间策略的配置进行 了检测和研究，并在此基础上实现了一个软件原型，本文的论文组织结构如下： 第一章简要介绍了本软件的需求由来，路由策略冲突检测的重要性，国内外 的研究现状，以及本文所作的主要工作； 第二章介绍了b g p 协议的背景知识，包括其概述、消息格式、路径属性、 选路及a s 分类和关系等； 第三章详细介绍了目前常见的两类路由配置的错误，以及本文实现的工具检 测这两类错误的理论方法； 第四章介绍了本文实现的b g p 路由策略检查工具的需求、系统设计，以及 最终实现过程，并对其中使用的r p s l 语言描述路由策略的方法以及l e x 和y a c c 技术做了详细介绍。 第五章给出了两个网络策略配置实例，使用路由模拟软件c b g p 对本检查 工具检查的结果进行验证； 第六章对论文工作进行总结。 4 北京邮电大学工学硕士论文 第二章课题相关技术综述 边界网关协议b g p 是不同自治系统之间交互信息的路由协议，在现今的网 络中有广泛的应用，本章将简要介绍b g p 协议的基本概念及其工作过程，详细 介绍b g p 的消息格式、路径属性，以及b g p 状态机和它的选路过程，由于本文 设计实现的检查路由策略的工具是a s 级别的，因此在最后一节对a s 的分类、 a s 之间的关系有详细的描述。 2 1 边界网关协议概述 边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，b g p ) 1 9 - 2 1 】是用来连接i n t e r a c t 上 的自治系统的路由选择协议，是互联网的路由协议。它是i n t e m e t 工程任务组所 制定的一个加强的、完善的、可伸缩的协议。b g p 不适用传统域内路由协议的 距离度量，而是一个基于路径、网络策略和规则集来决定路由的协议。从1 9 9 4 年起，b g p 4 即在网络上广泛使用，它的主要改进是b g p 4 支持c i d r 寻址方案， 使用路由聚合减少路由表的尺寸，这个方案增加了i n t e m e t 上的可用i p 地址数量。 b g p 是为取代最初的外部网关协议e g p 设计的。它也被认为是一个路径矢量协 议。 b g p 是一种在自治系统之间动态交换路由信息的路由协议。所谓自治系统， 即是在一个管理机构控制之下的一组路由器，它使用i g p ( i n t e r i o rg a t e w a y p r o t o c 0 1 ) 和普通度量值达到内部的统一，然后向其他自治系统转发报文。自治 系统的特点就是：一个自治系统( a s ) 的管理对于其他自治系统而言是提供一 个统一的内部选路计划，它为那些通过它可以到达的网络提供了一个一致的描 述。b g p 分为e b g p 和i b g p ，e b g p 应用于a s 之间，而i b g p 应用于a s 的内 部。 b g p 使用了传输控制协议( t c p ) ，由t c p 提供差错控制来实现面向连接的 可靠传输。当网络检测到某台主机发出变化时，就会发送新的路由表。 b g p 的基本工作过程如下： 1 ) 两个b g p 实体间建立t c p 连接，通过o p e n 消息协商属性，协商成功 则建立b g p 邻居关系，并周期性发送k e e p a l i v e 消息保持邻居关系； 劲在b g p 邻居建立时一次性交换全部路由信息； 3 ) 路由发生改变时发送u p d a t e 消息更新路由。 b g p 没有对基础因特网拓扑施加任何限制。它假定a s 内部的选路已经通过 5 北京邮电大学工学硕士论文 a s 内的选路协议( i g p ) 完成。基于在b g p 对等体之间交换的信息b g p 构造了 一个a s 图。就b g p 而论，这个因特网就是一个a s 图，每个a s 用a s 号码来 识别。两个a s 之间的连接形成一个路径，路径信息的汇集形成到达特定目的地 的路由。b g p 使用这些与既定目的地相关的路径信息来确保无循环域问选路。 2 2b g p 消息格式 b g p 的运行是通过消息驱动的，共有4 种消息类型【1 l ： 1 ) o p e n 消息，b g p 对等体间通过发送o p e n 报文来交换各自的版本、a s 号、保持时间、b g p 标识符等信息，进行协商。 2 ) u p d a t e 消息，该消息携带的是路由更新信息。其中包括撤销路由信息 和可达路由信息及其路径属性。 3 ) k e e p a l i v e 消息，它在b g p 对等体间周期地发送，以确保连接保持有 效 4 1n o t i f i c a t i o n 消息，当b g p 检测到差错( 连接中断、协商出错、报 文差错等) 时，发送n o t i f i c a t i o n 报文，关闭同对等体的连接。 o p e n 报文主要用于建立邻居( b g p 对等体) 关系，它是b g p 路由器之间 的初始握手消息，应该发生在任何通告消息之前。其他在收到o p e n 消息之后， 即以k e e p a l i v e 消息作为响应。一旦握手成功，则这些b g p 邻居就可以进行 u p d a t e ( 更新) 、k e e p a l i v e ( 保持激活) 以及n o t i f i c a t i o n ( 通知) 等消 息的交换操作。 这些消息具有相同的消息头，b g p 消息的格式是一样的，都是“消息头+ 消 息体”的格式。 1 ) 消息头格式 每一个消息包括一个定长的消息头。消息头后面可以可以不包含数据部分， 这取决于消息类型。如图2 1 ： m a r k e r ( 16b y t e ) l e n g t h ( 2b y t e )t y p e ob y t e ) i 图2 - 1 消息头格式 m a r k e r ( 标记) ：1 6 个字节，鉴别进入的b g p 报文或者检测两个b g p 对等 体间同步的丢失。两种格式：无鉴别信息的标记字段全为1 、否则基于鉴别技术 来计算。 6 北京邮电大学工学硕士论文 l z n g t h ( 长度) ：2 字节无符号整数。指定了消息的全长，包括消息头，以字 节为单位。 t y p e ( 类型) ：1 个字节的无符号整数，指定了消息类型编码。如下定义： 1 0 p e n 2 u p d a n z 3 n o t i f i c p 汀i o n 4 k e e p a i i v e 2 2 1o p e n 消息格式 o p e n 消息是t c p 连接建立后发送的第一个消息，用于建立b g p 对等体之 间的连接关系。 o p e n 消息由消息头加上如下结构构成，消息格式如图2 2 ： v i s i o n ( b y 慵 m y a u t o n o m o u ss y s t e m ( 2b y t e ) 。h o l d l l m e ( 2 b y t e ) b g pi d e n t i f i e r ( 4b y t e ) o p t i o n a lp a r a m e t e r s l e n o t h ( 1b v t e ) o p t i o n a lp a r a m e t e r s 图2 - 2o p e n 消息格式 v e r s i o n ( 版本) ：1 字节无符号整数，指示消息的协议版本号。当前的b g p 版本号是4 。 m ya u t o n o m o u ss y s t e m ( 本a s ) ：2 字节无符号整数，指示发送者a s 号。 通过比较两端的a s 编号，可以确定是i b g p 还是e b g p 连接。 h o l dt i m e ( 保持时间) ：2 字节的无符号整数，发送方提供建议的保持定时 器的设定秒数，它规定了b g p 邻居认为发送方信息有效的时间长度。如果b g p 对等体之前的o p e n 消息中h o l dt i m e 时间不一致，选择较小的h o l dt i m e 。如 果在这个时间内未收到对端发来的k e e p a l i v e 消息或u p d a t e 消息，则认为 b g p 连接中断。 b g pi d e n t i f i e r ( b g p 标识符) ：4 字节无符号整数，指示了b g p 发言者的标 示符。给定的b g p 发言者设置b g p 标示符为i p 地址。该值是在b g p 对等体之 间进行握手操作的过程中确定的，并且在每个本地接口及每个b g p 对等体之间 是保持不变的。 o p t i o n a lp a r a m e t e r sl e n 垂h ( 可选参数长度) ：1 字节无符号整数，指示可选 7 北京邮电大学：1 = 学硕士论文 参数域的字节总长度。如果这个域是o ，说明没有可选参数。 o p t i o n a lp a r a m e t e r s ( 可选参数) ：变长，可选的参数。 2 2 2k e e p a l i v e 消息格式 k e e p a l i v e 消息主要用于对等体路由器间的运行状态以及链路的可用性确 认。合理的最大k e e p a l i v e 消息时间是h o l d 计时器间隔的1 3 。如果协商的 h o l dt i m e 计时间隔是“0 ”，则不发送k e k p a l i v e 消息。缺省情况下，发送 k e e 础山v e 的时间间隔为6 0 秒。 k e e p a l i v e 消息只包含消息头长度是1 9 字节，没有附加其他任何字段， 如图2 3 ： m a r k e r ( 1 6b y t e ) l e n g t h ( 2b y t e )t y p e ob y t e ) | 图2 - 3k e e p a l i v e 消息格式 2 2 3n o i i n c a t i o n 消息格式 n o t i f a c a t i o n 消息在探测到错误情况时发送，b g p 连接发送它之后会立 即关闭。 除了定长b g p 消息头，n o t i f i c a t i o n 消息包括下面的域，如图2 4 所示： 图2 - 4n o t i f i c a t i o n 消息格式 e r r o rc o d e ( 错误码) ：1 字节的无符号整数，指示了n o t i f i c a t i o n 的类 型，表2 - 1 给出了错误类型编码定义： 袁2 - 1 错误类型编码 错误码符号名称 l消息头错误 2o p e n 消息错误 3u p d a i e 消息错误 4h o l d 计时器溢出 5f s m 错误 6终止 8 北京邮电大学工学硕士论文 e r r o rs u b c o d e ( 错误子码) ：1 字节的无符号整数，提供了更多的信息关于 报告的错误的种类。每一个错误可以由一个或者多个错误子码，如果没有特别的 错误子码定义，在错误子码域填充0 。 1 ) m e s s a g eh e a d e re r r o rs u b c o d e s ( 消息头错误子码) ： 1 连接未同步 2 错误消息长度 3 错误消息类型 2 ) o p e nm e s s a g ee r r o rs u b c o d e s ( o p e n 消息错误子码) ： 1 不支持版本号 2 错误对端a s 3 坏的b g p 标识符 4 不支持的选项参数 5 一认证失败 6 不支持的h o l d 时间 3 ) u p d a t em e s s a g ee r r o rs u b c o d e s ( u p d a t e 消息错误子码) t 1 一畸形属性链表 2 一不认识公认属性 3 一缺少公认属性 4 一属性标志错误 5 一属性长度错误 6 一无效o r i g i o n 属性 7 一a s 路由环路 8 一无效的n e x t h o p 属性 9 一可选参数错误 1 0 - 无效网络域 1 1 畸形a sp a t h d a t e ( 数据) ：变长的域，用来诊断n o t i f i q 钉i o n 的原因。数据与内容 依赖于错误码和错误子码。n o t i f i c a t i o n 消息最小的长度是2 1 字节( 包括消 息头) 。 u p d a t e 消息用来发送路由信息到b g p 对端，以下是u p d a t e 消息的通告 原则： 1 一个u p d a t e 消息一次只能通告一条路由，但它可携带多个路由属性。 2 一个u p d a t e 消息一次也可通告多条路由，但它的路由属性必须相同。 9 北京邮电大学工学硕士论文 3 一个u p d a t e 消息可以同时携带多个被撤消的路由。 u p d a t e 消息总是包括定长消息头，同时可选的包括下面的域，消息格式 如图2 5 ： 、u n f e a s i b l er o u t e sl e n g t h 矾穗h d r a w nr o u t e s p a t ha t t r i b u t el e n g t h p a t ha t t r i b u t e n e t w o r kl a y e rr e a c h a b i l i t yi n f o r m a t i o n 图2 - 5u p d a t e 消息格式 u n f e a s i b l er o u t e sl e n g t h ( 不可用路由长度) ：2 字节无符号整数，指示了 撤销路由的字节总长度。若为“0 表示没有撤销路由字段。 w i t h d r a w nr o u t e s ( 撤销的路由) ：可变长路由域。不可达路由列表，包括 一系列的口前缀，说明撤销服务的路由。 t o t a lp a t ha t t r i b u t el e n g t h ( 总的路径属性长度) ：2 字节无符号整数，指示 路径属性域字节总长度。值必须使下文中网络层可达信息域的长度能够被探测 到。本字段取值为0 ，则表示在u p d a t e 消息中没有网络层可达信息域。 p a t ha t t r i b u t e s ( 路径属性) ：在每一个u p d a t e 消息中有变长的路径属性 序列。 n e t w o r kl a y e rr e a c h a b i l i t yi n f o r m a t i o n ( 网络层可达信息) ：这个变长域包 含了i p 地址前缀的清单。包括网络可达信息。 u p d a t e , 消息是b g p 系统中最重要的信息，用于在b g p 对等实体之间交换 路由信息，它最多由三部分构成：不可达路由( u n r e a c h a b l e ) 、路径属性( p a t h a t t r i b u t e s ) 、网络可达性信息( n l r i ，n e t w o r kl a y e rr e a c h a b i l i t yi n f o r m a t i o n ) 。 2 3b g p 路径属性 b g p 路由属性1 1 】是一套参数，它对特定的路由进行更详细的描述。在配置路 由策略时将广泛地使用各种路由属性。 事实上，路由属性被分为以下几类： w e l l k n o w nm a n d a t o r y ( 公认必遵属性) ：在路由更新数据报文中必须存在 的路由属性，这种属性域在b g p 路由信息中有着不可替代的作用，如果缺少必 遵属性，路由信息就会出错。如a s p a t h 就是必遵属性，b g p 用它来避免路由 环路，没有它路由就可能出问题。 1 0 北京邮电大学工学硕士论文 w e l l k n o w nd i s c r e t i o n a r y ( 公认自决属性) ：能被所有b g p 协议实体识别， 但不一定存在于路由更新数据报文中，设置它完全是根据需要。如m e d 属性， 就用它来控制选路。 o p t i o n a lt r a n s i t i v e ( 可选过渡属性) ：具有a s 间可传递性的属性就是过渡 属性，过渡属性的域值可以被传递到其他a s 中去并继续起作用。如o r i g i n 属 性，路由信息的起源一旦确定，域值会一直存在，无论此路由信息被传到哪个 a s 中去。 o p t i o n a ln o n t r a n s i t i v e ( 可选非过渡属性) ：只在本地起作用，出了a s ，域 值就恢复成缺省值。如l o c a lp r e f 。 表2 2 列出几种常用属性的情况： 表2 - 2b g p 常用属性 类型代码属性名必遵可选过渡非过渡 1o r i g i n 必遵过渡 2 a s p a t h 必遵过渡 3 n e x t h o p 必遵 过渡 4 m u l t i e x i t d i s c 可选非过渡 5 l o c a l p r e f 可选非过渡 8c o m m u n i t y可选 过渡 每个属性都有特定的含义并可以灵活的运用，使得b g p 的功能十分强大。 b g p 属性可以扩展到2 5 6 种。 路由是用信宿地址来标识的。路由的属性即u p d a t e 消息中的路由属性部 分，是用来帮助b g p 进行路由选择的。当b g p 通过不同的路由源收到了相同目 的地地址的路由时，需要进行路由选择。 2 3 1o