（计算机科学与技术专业论文）单域bgp路由预测工具的设计与实现.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：型：邋日期： 2 o o ；1 f 关于论文使用授权的说明 本人完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复 制手段保存、汇编学位论文。 本人签名：五i ：耋至日期：丝! 堡兰： 导师签名：堕垒塑日期： t 0 0 u zl。， 北京邮电大学软件学院硕士论文 单域b g p 路由预测工具的设计与实现 摘要 作为一种关注域间流量级别上的网络性能优化技术，域间流量工 程越来越受到i s 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 的域间流量工程。 由于本文设计的工具在计算最佳路由时采用f e a m s t e r 算法，本文 介绍了f e a m s t e r 算法。f e a m s t e r 针对不同场景设计了3 种算法分支。 本文详细介绍了f e a m s t e r 算法的约束条件，各算法分支的应用场景 特点、运行流程和证明过程，分析了各算法分支的性能，并且将 f e a m s t e r 算法与动态模拟b g p 协议的仿真工具比较，指出了 f e a m s t e r 算法更符合域间流量工程预测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 配置。 关键词：边界网关协议路由预测域间流量工程路由器配置 北京邮电大学软件学院硕士论文 t 蠢0 0 。 北京邮电大学软件学院硕士论文 d e s i g na n di m 口l e n 匝_ n t 棚o no f at o o l f o rp r e d i c t i o no fb ( 讦r o u i e s i nas i n g l ea u t o n o m o u ss y s t e m a b s t r a c t a sat e c h n i q u ew h i c hc o n c e r nn e t w o r k sp e r f o r m a n c ei m p r o v e m e n t sa tt h e i n t e r d o m a i nt r a f f i cl e v e l ，i n t e r d o m a i nt r a f f i ce n g i n e e r i n gc a u s e si s p s m o r ea n d m o r ea t t e n t i o n a tt h ep r e s e n t ，b g pi st h eo n l yp o p u l a ri n t e r d o m a i np r o t o c 0 1 b g p r o u t e sa r eu s e dt or o u t ei n t e r d o m a i nt r a f f i ct r a n s i ta c r o s sa u t o n o m o u ss y s t e m s ( a s f o rs h o r t ) t h a ti st os a y , t h es e to f g o o d ”b g pr o u t e si st h ek e yo fi n t e r d o m a i n t r a f f i c b u t ，b g p sc o n f i g u r a t i o ni sf l e x i b l e ，w h i c hg i v en e t w o r ko p e r a t o r st o om a n y c h o i c e s d i f f e r e n tb g pc o n f i g u r a t i o nw o u l dp r o d u c ed i f f e r e n tb g pr o u t e s t h u s ， n e t w o r ko p e r a t o r sc a no n l yg e tt h eb e s tb g pc o n f i g u r a t i o nt h r o u g hm a n yt r ya n d a d j u s t i o n i ti st o od a n g e rt oa d j u s tb g pc o n f i g u r a t i o ni nr e a ln e t w o r k w ep r e s e n t a n dd e s i g nat o o lf o rp r e d i c t i n gb g pr o u t ei nas i n g l ea s 髓et o o lp e r m i tn e t w o r k o p e r a t o r sa s s e s sd i f f e r e n tb g pc o n f i g u r a t i o n s a c c o r d i n gt ot h et o o l sp r e d i c t i o n , n e t w o r ko p r a t o r sc a ni m p r o v ei n t e r d o m a i nt r a f f i c i nt h i sp a p e r , w ei n t r o d u c eb g pa n dt r a f f i ce n g i n e e r i n gb a s e do nb g p a st h et o o lu s ef e a m s t e ra l g o r i t h mw h e nc o m p u t eb e s tb g pr o u t e s ，w ei n t r o d u c e i nd e t a i l st h ea l g o r i t h m sc o n s t a i n t s ，e a c hb r a n c h sn e t w o r kf e a t u r e s ，d e s c r i b t i o na n d p r o v e m e n t w ea l s oa n a l y s i se a c hb r a n c h ；sp e r f o r m a n c e ，c o m p a r et h ea l g o r i t h m w i t hs i m u l a t i o nt o o l sw h i c hc a na l s oo u t p u tb g pr o u t e st h r o u g ha n a l y s i sb g p d y n a m i c , a n dt h u sf i g u r eo u tf e a m s t e ra l g o r i t h mi sb e t t e rf o ri n t e r d o m a i nt r a f f i c s n e e dt op r e d i c tb g pr o u t e s w ep r e s e n ts e v e r a lf a c t o r sw h i c hi m p a c tb g pr o u t e s ，d a f f yt h et o o l ss t u d y o b j e c t s ，d e f i n et h et o o l sf u c t i o n a lr e q u i r e m e n t ，a n dt h e nd e s i g nt h et 0 0 1 g i v e na l l a s sb g pc o n f i g u r a t i o n ，t h et o o lw o u l dp r e d i c ta l lb g pr o u t e r sb e s tr o u t et a b l e g i v e nt h ep a c k e t sp a c k e t sp r e f i xa n di n g r e s sp o i n t ，t h et o o lw o u l dp r e d i c tt h e p a c k t se g r e s sp o i n tw i t ht h ei n f o r m a t i o no fb e s tr o u t et a b l e t h en e t w o r ko p e r a t o r c a l lu s et h et o o l sr e s u l tt oa s s e s sd i f f e r e n tb g p c o n f i g u r a t i o n s ，a n dt h u sc h o s et h e b e s to n e k e yw o r d s ：b g p , p r e d i c tr o u t e ，t r a f f i c e n g i n e e r i n g ，r o u t e r c o n f i g u r a t i o n 北京邮电大学软件学院硕士论文 一1哥p；j 北京邮电大学软件学院硕士论文 目录 第一章绪论1 1 1 项目背景及意义l 1 2 论文工作2 1 3 论文结构2 第二章背景知识3 2 1b g p 协议概述3 2 1 1 基本概念3 2 1 2b g p 工作机制4 2 1 3 路由反射器4 2 1 4b g p 消息类型6 2 1 5b g p 路径属性7 2 1 6b g p 路由选择过程1 4 2 2 基于b g p 的域间流量工程1 7 2 2 1 基本概念1 7 2 2 2 基于b g p 的域间流量特点1 8 2 2 3 基于b g p 的域问流量工程的方法1 9 2 2 4 基于b g p 的域间流量工程技术现状2 2 2 3 本章小结2 2 3 1 约束条件2 4 3 2f e a u s t e rb e s te b g p 算法2 5 3 2 1 算法应用场景2 5 3 2 2 算法描述及证明2 6 3 2 3 算法性能分析2 7 3 3f e 嶙t e rb e s te b g pm e d 算法2 8 3 3 1m e d 引发的问题2 8 3 3 2 算法应用场景3 0 3 3 3 算法描述及证明3 0 3 3 4 算法性能分析3 2 3 4f e a s t e rb e s te b g pr r 算法3 4 3 4 1 路由反射机制引发的问题3 4 3 4 2 算法应用场景3 6 3 4 3 算法描述及证明3 7 3 4 4 算法性能分析3 9 3 5 本章小结4 0 第四章软件需求分析4 1 北京邮电大学软件学院硕士论文 4 1 影响b g p 路由选择的若干因子4 1 4 1 1b g p 入口策略4 2 4 1 2 确定性4 2 4 1 3i b g p 拓扑结构4 3 4 1 4i g pc o s t 4 4 4 2 研究现状4 5 4 3 约束条件4 6 4 4 功能性需求4 7 4 3 1 输入输出4 8 4 3 2 功能分析4 9 4 5 本章小结4 9 第五章软件设计与实现5 0 5 1 软件系统结构5 0 5 1 1 系统流程设计5 0 5 1 2 总体结构和模块划分5 1 5 1 3 数据库设计5 2 5 2 入口策略过滤模块5 5 5 2 1 数据结构定义5 6 5 2 2 关键函数的定义与实现6 0 5 3 最佳路由计算模块6 3 5 5 1 子分支流程6 4 5 5 2 数据结构定义6 8 5 5 3 关键函数的定义与实现7 0 5 4 用户界面7 5 5 5 本章小结7 7 第六章结束语7 8 6 1 论文工作总结7 8 6 2 问题和展望7 8 参考文献8 0 致谢8 1 攻读学位期间发表的学术论文8 2 飞 ， p 北京邮电大学软件学院硕士论文 1 1 项目背景及意义 第一章绪论 近十年来，i n t e r n e t 通信服务业中的竞争越来越激烈，终端用户也不断要求 他们的i s p ( 网络服务提供商) 提供更畅通及时的网络服务。另一方面，i s p 常 常出现网络的某部分发生拥塞，其他部分却有大量链路资源闲置，网络资源利 用率低下。为解决上述问题，很多i s p 通过流量工程技术来实现网络流量均衡。 流量工程关注在流量和资源级别提高网络的性能，研究如何评价口网络的性能 以及优化口网络性能的技术，主要包括如何对i n t e m e t 流量进行测量，识别， 建模以及控制的研究。 i n t e r n e t 的目的是将信息从源节点传输到目标节点。与此相对应的，l n t e r n e t 最重要的一个功能是将数据从入口节点路由到出口节点。i n t e r n e t 流量工程的一 个重要功能是控制，优化路由，以便引导流量以最有效的方式通过网络。本文 主要从路由的角度考虑流量工程。 i n t e m e t 路由分为域内路由和域问路由，相应地，流量工程分为域间流量工 程和域内流量工程。域内流量工程对自治域内的流量进行优化，域间流量工程 则是对自治域间的流量进行性能优化。由于网络管理者可以通过运行域内路由 协议管理域内的所有路由器，因此他们可以完全控制域内路由。例如，网络管 理者可以配置链路权重值控制o s p f ( 域内路由协议的一种) 路由中的最短路 径选择。然而，一个大的m 骨干网所承载的大部分流量要通过多个a s ，这使 得域问流量工程非常重要。 边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，以下简称b g p ) 是目前唯一在自 治域( a u t o n o m o u ss y s t e n l ，简称a s ，又称为域d o m m n ) 间使用的路由协议。 因此如何更好的引导域间流量，避免网络资源配置不平衡，提高网络性能和服 务质量，关键在于合理有效地控制优化b g p 路由。然而，b g p 的配置非常灵 活，参数组合有很多可能性，由此产生的b g p 路由也不同，我们只能通过“反 复实验”的方法，得到参数组合的最佳配置。 通常，网络操作员循环以下步骤选择最佳配置。 ( 1 ) 配置自治域的参数，比如入口策略，网络拓扑等 ( 2 )自治域内的b g p 路由器运行b g p 协议，得出b g p 路由 ( 3 ) 结合网络流量对b g p 路由评估 ( 4 ) 提出优化b g p 路由的配置 在实际网络中“反复实验”存在着巨大的风险。首先，b g p 赋予了网络操作 北京邮电大学软件学院硕士论文 员非常大的自由性，网络操作员如果配置不当，会带来严重后果，诸如网络拥 塞，违反商业关系，路由振荡等。这是i s p 所不愿意看到的。其次，b g p 收敛 速度较慢，网络操作员要知道改变配置信息带来的结果需要等待较长的时间。 因此，需要有一个工具或软件，使得网络管理员可以在其上反复实验，评估并 比较各种配置组合对b g p 路由的影响，以便在实际网络配置中选择正确最佳的 网络配置。 1 2 论文工作 本文设计并实现了单域b g p 路由预测工具。本工具提供了两大功能：根据 给定的单域b g p 配置信息，预测本域内所有b g p 路由器的最佳路由表；根据 给定的业务分组的目的前缀和入口点，预测该业务分组在哪个出口点离开本域。 本工具为网络操作员提供评估各种b g p 配置组合的“零风险”实验平台，网络操 作员可以根据本工具的预测结果更好地优化域间流量。 1 3 论文结构 第一章，简要的介绍了课题的研究背景和意义。 第二章，主要介绍b g p 协议和基于b g p 的域间流量工程。b g p 协议介绍 了基本概念，工作机制，路由反射器，消息类型，路径属性，路由选择过程。 基于b g p 的域间流量介绍了其基本概念，特点，方法以及目前国内外对于该领 域的研究现状。 第三章，介绍了f e a m s t e r 算法。f e a m s t e r 算法根据不同的网络场景，提出 了三种i b g p 消息传递顺序，并因此设计了3 种分支算法。本章分别给出了上 述3 种算法的描述，证明以及性能分析。 第四章，软件需求分析。首先，分析了单域b g p 路由预测工具的必要性， 简略介绍了预测工具的研究对象，使用情形、用户人群。定义了本工具的输入 输出以及应完成的功能。 第五章，软件设计与实现，首先介绍了软件系统结构，包括系统流程设计， 模块划分，数据库设计。然后详细介绍各个模块：入口策略模块，路由选择模 块，路由查找模块。 第六章，总结与展望，总结主要工作内容及本文的研究成果，并提出进一 步的研究工作。 2 北京邮电大学软件学院硕士论文 第二章背景知识 本章第一节将简要介绍b g p 协议的基本概念及其工作过程，详细介绍 b g p 的路径属性和选路过程。本章第二节将简要介绍基于b g p 的域间流量工 程的基本概念，特点，方法以及目前国内外在该领域的研究现状。 2 1b g p 协议概述 2 1 1 基本概念 b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 是一种用于自治系统a s ( a u t o n o m o u s s y s t e m ) 之间的动态路由协议。a s 是拥有同一选路策略，在同一技术管理部门 下运行的一组路由器。与o s p f 和r i p 等在自治区域内部运行的协议对应，b g p 是一类e g p ( e x t e r i o rg a t e w a yp r o t o c 0 1 ) 协议，而o s p f 和r i p 等为i g p ( i n t e r i o r g a t e w a yp r o t o c 0 1 ) 协议。 早期发布的三个版本分别是b g p 1 ( r f c l l 0 5 ) 、b g p 2 ( i 强c 1 1 6 3 ) 和b g p 一3 ( r f c l 2 6 7 ) ，当前使用的版本是b g p - 4 ( r f c l 7 7 1 ) 。b g p 4 作为事实上的 i n t e m e t 外部路由协议标准，被广泛应用于i s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 之间。 下文中若不做特殊说明，所指的b g p 均为b g p - 4 。 发送b g p 消息的路由器称为b g p 发言者( s p e a k e r ) ，它接收或产生新的路由 信息，并发布( a d v e r t i s e ) 路由给其它b g p 发言者。当b g p 发言者收到来自其它 自治系统的新路由时，如果该路由比当前已知路由更优、或者当前还没有该路由， 它就把更新自己的路由表，然后将这条路由发布给自治系统内其它b g p 发言者。 互联网可以视作随意连接的a s 的集合。通过b g p 直接连接的路由器就是b g p 发 言者。b g p 发言者可以在同一a s 内，也可以在不同a s 内。每个a s 的b g p 发言者 互相通信，遵照每个a s 建立的策略，交换网络可达性信息。 相互交换消息的b g p 发言者之间互称对等体( p e e r ) ，若干相关的对等体 可以构成对等体组( p e e rg r o u p ) 。对某b g p 发言者，如果该b g p 发言者的对 等体在不同的a s ，则该b g p 发言者称该对等体为外部对等体，而如果在相同 a s 内，则称为内部对等体。 3 北京邮电大学软件学院硕士论文 2 1 2b g p 工作机制 b g 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 消息保持邻居关系。 2 ) 在b g p 邻居建立时一次性交换全部路由信息。 3 ) 路由发生改变时发送u p d a t e 消息更新路由。 b g p 没有对基础因特网拓扑施加任何限制。它假定自治系统内部的选路已 经通过自治系统内的选路协议( i g p ) 完成。基于在b g p 对等体之间交换的信 息b g p 构造了一个自治系统图。这个导引的图形的环境有时叫做树。从b g p 的角度来看，这个因特网就是一个a s 图，每个a s 用a s 号码来识别。两个 a s 之间的连接形成一个路径，路径信息的汇集形成到达特定目的地的路由。 b g p 使用这些与既定目的地相关的路径信息来确保无循环域间选路。 2 1 3 路由反射器 b g p 在路由器上以下列两种方式运行： 1 ) i b g p ( i n t e r n a lb g p ) 2 ) e b g p ( e x t e r n a lb g p ) 物理链路 一一一 b g p 会话 图2 - 1i b g p 与e b g p 如果两个交换b g p 报文的对等体属于同一个自治系统，那么这两个对等体 就是i b g p 对等体( i n t e r n a lb g p )，如图2 - 1 的b 和d 。 4 北京邮电大学软件学院硕士论文 如果两个交换b g p 报文的对等体属于不同的自治系统，那么这两个对等体 就是e b g p 对等体( e x t e r n a lb g p )，如图2 1 的a 和b 。 虽然b g p 是运行于自治系统之间的路由协议，但是一个a s 的不同边界路 由器之间也要建立b g p 连接，只有这样才能实现路由信息在全网的传递，如b 和d ，为了建立a s l 0 0 和a s 3 0 0 之间的通信，我们要在它们之间建立i b g p 连 接。 i b g p 对等体之间不一定是物理上直连的，但必须保证逻辑上全连接。( t c p 连接能够建立即可) 。 一般的路由器都默认要求e b g p 对等体之间是有物理上的直连链路，同时 他们一般也提供改变这个缺省设置的配置命令。 b g p 发言人从i b g p 获得的路由不向它的i b g p 对等体通告，这是b g p 避 免在a s 内部发生路由循环的方法之一。i b g p 中的环路防止机制迫使所有的 i b g p 的宣告者相互之间建立b g p 会话。换句话说，它们是全互连的，因而所 有的b g p 宣告者可以接收完全的路由选择信息。全互连意味着，每个i b g p 路 由器之间都要全连接。n 个i b g p 路由器之间的i b g p 会话总数是n ( n - 1 ) 2 ， 每一台路由器有( n 1 ) 个会话。所以通常在大规模网络中，如果局部无法实现 a s b r 全连接的话，我们可以利用b g p 路由反射器来解决这样的问题。 路由反射器概念的基本思路是：指定一个集中路由器作为内部b g p 对话的 焦点。多个b g p 路由器可以与一个中心点( 路由反射器) 对等化，然后多个路 由器再进行对等化。路由反射器只对拥有大型的i b g p 闭合网的a s ，才被推荐 使用。在这种新的结构下，i b g p 宣告者被分成3 组： 1 ) 路由反射器( r r ) ； 2 ) 路由反射器客户( 也叫客户或客户对等体) ； 3 ) 常规的i b g p 宣告者( 也叫非客户或非客户对等体) 。 这里的客户和非客户的概念总是处在与路由反射器有关的上下文中，这些 路由反射器为它们服务或不为它们服务。一个r r 客户可以是另一个客户的r r 。 与一个r r 相关的非客户可以是另一个客户的r r 。路由反射器的连接图2 - 2 如 下： 北京邮电大学软件学院硕士论文 图2 - 2 路由反射器连接图 为了避免路由选择信息环路，涉及r r 的前缀通告必须遵循以下的规则： 1 ) r r 只通告或反射它所知道的最佳路径。 2 ) r r 总是向e b g p 对等体通告。 3 ) 如果r r 从外部对等体学到前缀，就向它所有的客户和非客户通告。 4 ) 如果前缀是通过一个非客户i b g p 对等体到达r r ，r r 就向它所有的客 户反射这条路由。 5 ) 如果前缀通过客户到达r r ，r r 就向它所有其他客户和非客户反射这 条路由。 2 1 4b g p 消息类型 b g p 的运行是通过消息驱动的，共有4 种消息类型： 1 ) o p e n 2 ) u p d a t e 3 ) k e e p a l i v e 4 ) n o t i f i c a t i o n b g p 对等体间通过发送o p e n 报文来交换各自的版本、自治系统号、保持 时间、b g p 标识符等信息，进行协商。 u p d a t e 报文携带的是路由更新信息。其中包括撤销路由信息和可达路由 信息及其路径属性。 当b g p 检测到差错( 连接中断、协商出错、报文差错等) 时，发送 n o t i f i c a t i o n 报文，关闭同对等体的连接。 k e e p a l i v e 报文在b g p 对等体间周期地发送，以确保连接保持有效。 o p e n 报文主要用于建立邻居( b g p 对等体) 关系，它是b g p 路由器之间 6 的初始握手消息，应该发生在任何通告消息之前。其他在收到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 ( 通知) 等 消息的交换操作。 2 1 5b g p 路径属性 b g p 路由属性是一套参数，它对特定的路由进行更详细的描述。在配置路由 策略时我们将广泛地使用各种路由属性。 事实上，路由属性被分为以下几类： 1 ) 公认必遵属性：在路由更新数据报文中必须存在的路由属性，这种属性 域在b g p 路由信息中有着不可替代的作用，如果缺少必遵属性，路由 信息就会出错。如a s p a t h 就是必遵属性，b g p 用它来避免路由环路， 没有它路由就可能出问题。 2 ) 公认自决属性：能被所有b g p 工具识别，但不一定存在于路由更新数 据报文中，我们设置它完全是根据需要。如m e d 属性，我们就用它来 控制选路。 3 ) 可选过渡属性：具有a s 间可传递性的属性就是过渡属性，过渡属性的 域值可以被传递到其他a s 中去并继续起作用。如o r i g i n 属性，路由信 息的起源一旦确定，域值会一直存在，无论此路由信息被传到哪个a s 中去。 4 ) 可选非过渡属性：只在本地起作用，出了自治系统，域值就恢复成缺省 值。如l o c a l _ _ p r e f 。 几种常用属性的情况如表2 - 1 所示： 表2 - 1 ：b g p 属性列表 类型代码 属性名必遵可选 过渡非过渡 l o n 9 1 n 必遵过渡 2 a s - p a t h 必遵过渡 3 n e x t - h o p必遵 过渡 4m e d可选 非过渡 5 l o c a l _ p r e f 可选非过渡 8 c 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 通过不同的路由源收到了相同 7 北京邮电大学软件学院硕士论文 信宿地址的路由时，需要进行路由选择。 1 ) o r i g i n 属性 o r i g i n 是一个公认必遵属性，定义了路径信息的起点，是产生路由的自治系 统产生的。b g p 允许三种类型的起源： 表2 - 2 ：o r i g e n 值的意义 值意义 0 i g p 一路由信息为起始a s 内部 1 e g p 一路由信息为起始a s 通过e g p 得来 2 i n c o m p l e t e - - 路由信息通过其它方法得来 b g p 在其路由判断过程中会考虑起点属性来判断多条路由之间的优先级。 具体来说，b g p 针对o r i g i n 属性的优选顺序为：i g p e g p i n c o m p l e t e 。 一般情况下： 1 ) i g p ：对于始发a s 来说是内部的。即b g p 把通过n e t w o r k 命令或通过 聚合通告的网络看成对于a s 是内部的。 2 ) e g p ：通过e g p 得知的网络层可到达性信息。 3 ) i n c o m p l e t e ：通过其他方法得知的网络层可到达信息。即把从其它 i g p 路由协议引入的路由起点类型设置为i n c o m p l e t e 。 2 ) a s - p a t h 属性 a s p a t h 是公认必遵属性，由a s 路径段的序列组成，它包括路由到达一个 目的地所经过的一系列的自治系统号码。a s p a t h 保证i n t e r n e t 的无循环拓扑。 当b g p 发言者通告从别的b g p 发言者u p d a t e 的消息学习到的路由，应该根 据路由发送到的b g p 发言者的位置，修改路i 主t a s - p a t h 的属性。 1 ) 当给定的b g p 发言者通告路由到本a s 的别的b g p 发言者，通告发言者不 应该修改路由的a s p a t h 属性。 2 ) 当给定的b g p 发言者通告路由到邻居a s 的b g p 发言者，通告发言者应该 修改路由的a s p a t h 属性，而且要将自己的a s 号码“列前”到排列表中。 具体的情况如图2 3 所示： 图2 - 3a s p a t h 通告原则 如图2 3 所示，a s 路径属性也在影响路由选择。在其它因素相同的情况下， 选择a s 路径较短的路由。a s 2 0 0 内的网络d 1 8 0 0 0 8 经a s 2 0 0 、a s 3 0 0 、a s 4 0 0 到达a s l 0 0 的路径为d l ( 4 0 03 0 02 0 0 ) ，经a s 2 0 0 、a s 5 0 0 到达a s l o o 的路径为d 2 ( 5 0 02 0 0 ) ，这时b g p 优先选择较短的路径d 2 。 选择较短a s p a t h 路径这一点并不一定精确，因为穿过了的2 个由高速网 络构成的a s 区域的路由，有可能比穿过了1 个低速网络的a s 区域的路由更好， 这种情况要求恰当的配置。如图2 4 所示，可以通过加入伪a s 号来增加路径长 度，从而影响路径选择。例如，我们可以在路由器器a 上配置，使之将路由 1 0 0 0 0 8 发往邻居时，将其a s p a t h 属性再加上两个自治系统号1 2 3 、1 2 3 ，这 样当这条路由被传递到路由器b 时，其a s p a t h 为：d l ( 1 2 31 2 31 2 3 ) 。而从 a s 4 6 2 传来的始发予a 8 1 2 3 的路由的a s p a t h 为d 2 ( 4 5 61 2 3 ) 。这样d 1 的a s p a t h 比d 2 长，所以最终路由器会认为d 2 为较优的路由。 9 北京邮电大学软件学院硕士论文 一一- - 1 3 g p 会话争业务分组的 物理连接 最终路径 图2 - 4 预先规划h s - p a t h 3 ) n e x t - h o p 属性 n e x t - h o p 是一个公认必遵属性。在i g p 中，到达一个路由的下个中继是已 通告了路由的路由器的连接接口的口地址，而在b g p 中，n e x t - h o p 概念略为 复杂，分为以下情况： 1 ) 对于e b g p ，n e x t - h o p 属性是本地b g p 与对端连接的端口地址。如图 2 5 所示，路由器c 向路由器a 通过e b g p 通告路由1 7 0 1 0 0 0 时， n e x t h o p 属性为1 7 0 1 0 2 0 2 ；a 向c 通告1 5 0 1 0 0 0 的路由时，n e x t - h o p 为1 7 0 1 0 2 0 1 。 2 ) 对于i b g p ，本地b g p 将从e b g p 得到的路由的n e x t h o p 属性，直接注 入i b g p 的u p d a t e 路由更新消息。图2 5 中，a 通过i b g p 向b 通告 路由1 7 0 1 0 0 0 时，n e x t - h o p 仍然为e b g p 中的1 7 0 1 0 2 0 2 。对于a s 内部产生的路由，下个路由是宣告了路由的相邻体的p 地址，a 向c 通告1 5 0 1 0 0 0 的路由时，n e x t - h o p 为1 5 0 1 0 3 0 1 。 1 0 叠 j 北京邮电大学软件学院硕士论文 图2 - 5n e x t h o p 属性 4 ) m e d 属性 i v i e d ( m u l t ie x i td i s c r i m i n a t o r ，多出口鉴别) 属性是一个可选非 过渡属性，当某a s 自治区域有多个入口点时，此属性用来帮助选择一个较好 的入口点。即，选择m e d 较小的入口点。 m e d 属性是在a s 之间交换的，但是被一个a s 收到的m e d 属性并不离 开这个a s 。当一个更新进入a s 时，它带有某个m e d 值，此值被a s 内部的 决策处理过程使用。b g p 将这个路由更新转给其他a s 时，m e d 被重置为0 ( 除 非出站m e d 被明确地设置为某个数值) 。 缺省情况下，不允许比较来自不同a s 邻居的路由信息的m e d 值。 图2 - 6m e d 属性 北京邮电大学软件学院硕士论文 如图2 6 ，网络路由1 8 0 1 0 0 0 从c 、d 和b 出发，通过e b g p 通告给a 。 其中c 的m e d 为1 2 0 ，d 的m e d 为2 0 0 ，b 的m e d 为5 0 。缺省情况下，b g p 只比较同一a s 区域发送的m e d ，这是因为不同a s 自治区域的度量m e t r i c 的 方法可能不同，只有相同a s 区域的m e t r i c 才有可比性。因此a 选择m e d 较 小的c 发送的路由，将2 2 2 1 作为路由1 8 0 1 0 0 0 的n e x t - h o p ( b 的m e d 更小) 。 m e d 属性不会通过a s 区域传播，因此，a 发送路由1 8 0 1 0 0 0 时的m e d 设 置为缺省值0 。 5 ) l o c a l _ p r e f 属性 本地优先级( 1 0 c a lp r e f ) 属性是可选属性，本地优先级属性是赋予一条路 由的优先级程度，用以比较到相同目的地的不同路由。本地优先级属性值越大， 路由的优选程度就越高。本地优先级属性只用于a s 内部，只在i b g p 对等体 之间被交换，而不被通告给e b g p 对等体。简单来说，本地优先级属性就是用 来帮助a s 区域内部的路由器选择到a s 区域外部使用较好的出口。即，选择本 地优先级较高的出口点。 需要注意的是：配置本地优先级的属性值仅仅会影响离开该a s 的业务量， 不会影响进入该a s 的业务量。缺省情况下，本地优先级属性值为1 0 0 。 如图2 7 所示，当路由1 7 0 1 0 0 0 通过路由器c 和路由器d 发送到a s 2 5 6 内部时，c 将l o c a lp r e f 设置为1 5 0 ；r t d 将l o c a lp r e f 设置为2 0 0 。这可能是 因为c 连接的a s 区域具有较高的速度或收费较低。因此，a s 2 5 6 内部的路由 器e 选择本地优先级较高的c 作为得到网络1 7 0 1 0 0 0 的n e x t h o p 。 一一 b g p 会话 物理连接 图2 - 7l o c a l p r e f 属性 因为这个属性在a s 内的所有b g p 路由器间传递，所以所有的b g p 路由 1 2 p t k 器 6 ) 体 没 对等体) 。 4 ) i n t e r n e t ：带有这一团体值的路由在收到后，应该被通告给所有的 其他路由器。 除了这些公认的团体属性值之外，私有的团体属性值也可以被定义来用于 特殊用途。这些属性值被一些数字所标示。 一条路由可以具有一个以上的团体属性值，就像一条路由可以在其a s 路 径属性中含有一个以上a s 号码一样。在一条路由中看到多个团体属性值的b g p 路由器可以根据一个、一些或所有这些属性值来采取行动。路由器在将路由传 递给其他对等体之前可以增加或修改团体属性值。 图2 8 给出团体属性的一项简单应用，x n e t 正向y n e t 发送带有 n oe x p o r t 团体属性的路由x 和y 以及无改变路由z 。y n e t 中的b g p 路 由器将仅向z n e t 传送路由z 。路由x 和路由y 将不被传送。因为路由x 和路 由y 有n oe x p o r t 团体属性。在定义选路策略时，团体属性提供了非常大 的灵活性。 r o u t e 罂t 卜二= 。 ，、 y n e t 一一一f r 鳓x n 盯1螨嬲参柚i磷蜀臣如 1l f。 物理连接r o u t ex ( n 0 _ e x p o r t ) 一一一阱p 会话 r o u t e