（计算机应用技术专业论文）基于bgp的域间流量工程研究.pdf

查些查兰量主兰堡垒圭一一一一坚 基千b o p 的域间流量工程研究 摘要 i n t e r a c t 在过去的几十年中已经演变成为一种非常重要的通讯基础设施，广泛 应用于经济、教育、社会各方面。与此同时，i n t e r n e t 通讯服务中的竞争越来越激 烈，终端用户要求他们的服务提供商提供非常高的服务质量。结果，大规模口网 络尤其是i n t e r a c t 公共骨干网的性能优化，已经成为一个非常重要的问题。现在的 l i l t e m e t 路由由两部分组成：域内路由和域间路由。在一个自治域内部，网络管理 者可以获取路由器拓扑并对路由信息进行控制，因而可以控制域内的流量分布。 而在自治域之间，i n t e r n c t 采用了一种分布式控制路由信息方式，每个自治系统通 过边界网关协议与其他自治系统交换网络可达信息。边界网关协议的关键特征是 允许网络管理者定义自己的路由策略，路由策略允许自治系统向邻居自治系统通 告其全部或部分路由。由于网络管理者没有域间流量和拓扑的详细信息，因而域 间流量工程特别困难。与域内流量工程技术相比，域间流量工程技术还不细致、 不完善。本文以国家自然科学基金“域问路由稳定性与可管理性研究”为背景， 在多个方面对域间流量工程技术进行了研究。 本文概括介绍了域内流量工程与域闾流墨工程的应用现状，域间流量工程的 必要性和现有方法存在的不足。概括介绍了b g p 常用属性和b o p 的决策过程，分 析了域闻流量工程过程模型和基于b g p 的域间流量的特点，综述了域间流量工程 研究现状。 详细分析了i n t e r a c t 自治系统拓扑模型和实际自治系统拓扑的构建。通过分析 i n t e r a c t 演变过程中自治系统的拓扑变化情况，总结出节点连接规律，进而对b a 模型参数进行了修正，并将b a 模型生成的拓扑与i n t c m e t 拓扑进行了对比。分析 了自治系统层次结构特点，着重阐述了顶层自治系统的结构特点和域问路由的路 径特点。利用b g p 路由表包含的路径信息，根据不同层次自治系统结构特点，推 导出了各个自治系统所属的层次。综述了i n t e r a c t 路由器拓扑研究现状与路由嚣检 测实用工具，指出了路由器检测中存在的问题。 分类余绍了自治系统之间存在的商业合同关系，综述了在路由策略、自治系统 关系方面的研究现状，阐述了根据自治系统关系设置路由策略的一般性原则。提 东北大学博士学位论文摘要 出了一种从多个b g p 路由表推导a s 关系的方法，根据t i e r - 1 路由表a s 嘲的 结构特点，利用多个t i e r - 1 路由表相互验证自治系统关系，再由其他属于不同层 次自治系统的b g p 路由表辅助验证。与同类算法相比算法中没有引入经验参数， 结果对比表明算法推导结果具有极高的正确率。 详细介绍了基于b g p 的各种域间出流量和入流量控制技术，包括设置本地优 先值、a sp a t h 伪装、团体属性以及多出口鉴别等，并对各种方法的优缺点进行 了对比。给出了一个利用s s f n e t 仿真软件进行b g p 流量控制的示例，并利用 s s f n e t 仿真对a sp a t h 伪装技术的性能进行了评价。 分析了域问路由稳定性现状和大型自治系统域间流量特点，大流量的“流行前 缀”以及域问路由和流量的相对稳定性是利用b g p 实现域间流量工程的前提条件。 合理选择。流行前缀”，才能在利用b g p 改变前缀路由进行域问流量控制时获得 良好的效果详细介绍了现有的几种动态选择前缀方案并对比了他们各自的优缺 点。传输自治系统与末端自治系统具有不同的域间流量工程目标，根据他们各自 的流量工程目标分别建立相应的数学模型。根据网络测量的实际流量数据，分别 对末端自治系统和传输自治系统进行域问流量规划，实现特定的域间流量工程目 标。由于计算量庞大，使用遗传算法实现规划计算。利用a b i l e n e 网络提供的流量 数据对算法进行了验证。 关键词：域问路由；边界网关协议；域间流量工程；路由策略；网络拓扑；自治系 统关系；遗传算法 查韭查堂堡主兰堡堕查垒曼! ! 坠里 s t u d yo n b g p - b a s e di n t e r d o m a i n t r a f f i ce n g i n e e r i n g a b s t r a c t t h ei n t e r o e th a se v o l v e di n t oav e r yc r i t i c a lc o m m u n i c a t i o n si n f r a s t r u c t u r ei nt h e p a s td o z e n sy e a r s ，a p p l y i n gs i g n i f i c a n ti ne c o n o m i c , e d u c a t i o n a l ，a n ds o c i a la c t i v i t i e s s i m u l t a n e o u s l y , t h ei n t e r o e tc o m m u n i c a t i o n ss e x v i c e sh a v eb e c o m i n gm o l e ：c o m p e t i t i v e a n de n d - u s e r sa r e ：d e m a n d i n gv e r yh i g hq u a l i t ys e r v i c ef r o mt h e i rs e w i e ep r o v i d e r s c o n s e q u e n t l y , p e r f o r m a n c eo p t i m i z a t i o no fl a r g e $ p 麓l e 口n e t w o r k s e s p e c i a l l yp u b l i c i n t e r a c tb a c k b o n e s 。h a v eb e 0 3 , m ea l li m p o r t a n tp r o b l e m i n t e r a c tr o u t i n gs y s t e mt o d a yi s c o m p o s e do ft w op a r t s ：i n t r a d o m a i nr o u t i n ga n di n t c r d o m a i nr o u t i n g i n s i d e a l l a u t o n o m o u sd o m a i n , n e t w o r km a n a g e r sc a ng e tt h er o u t e rt o p o l o g ya n dc o n t r o lt h e r o u t e t h e r e f o r e t h ec o n t r o lo ft h ed i s t r i b u t i o no f 锄ci n s i d ead o m a i ni sp o s s i b l e a t t h ei n t e r d o m a l nl e v e lo ut h eo t h e rh a n d , t h ea p p r o a c hu s e di nt h ei n t e r n e ti st h eo n eo fa d i 蛐u t c dc o n t r o lo ft h er e n t i n gi n f o r m a t i o n e a c ha u t o n o m o u ss y s t e m ( a s ) u s eb o r d e r g a t e w a yp r o t o c o l ( b g p ) t oe x c h a n g er o u t i n gi n f o r m a t i o nw i t ho t h 廿a s e s a k e yf e a t a r e o fb g pi st h a ti ta l l o w se a c hn e t w o r km a n a g e rt od e f i n ei t sr o u t i n gp o l i c i e s a na sm a y a d v e r t i s ea l li t sr o u t e so iaf r a c t i o no fi t sr o u t e st on e i g h b o r i n ga s e s i n t e r d o m a i n 订a f f i c e n g i n e e r i n gi sp m d c u l a f l yd i f f i c u l ts i n c et h en e t w o r ki n a l l a g e rd o e sn o th a v ed e t a i l e d i n f o r m a t i o na b o u ti n t e r d o m a l nt r a f f i ca n dt h et o p o l o g y c o m p a r e d 州t hi n t t a d o m a i n 仃a m ce n g i n e e r i n g , t h et e c h n o l o g yo fi n t e r d o m a l nt r a 岱ce n g i n e e r i n gi sn o tp e r f e c ta n d s u f f i c i e n t b a s e do nt h en s fp r o j e c t “s t u d yo ni n t e r d o m a i nr o u t i n gs t a b i l i t ya n d m a n a g e b i l i t y , t h i sd i s s e r t a t i o n d i s c u s s e ds e v e r a lp r o b l e mo fi n t e r d o m a i n 倘c e n g i n e e r i n g t h i sd i s s e r t a t i o ns u m m a r i z 嚣t h ep r e s e n ts i t u a t i o no ft h ea p p l i c a t i o no fi n t r a d o m a i n t t a f f ee n g i n e e r i n ga n di n t e r d o m a i n a 蚯ce n g i n e e r i n g , i n t r o d u c e st h ei m p o r t a n c eo f i n t e r d o m a l nt r a f f i ce n g i n e e r i n ga n dt h es h o r t a g eo fc u r r e n tt e c h n o l o g i e s ，s i m p l y i n t r o d u c e sb g pc o n n n o na t t r i b u t e sa n db g pp r o c e s s ，a n a l y z e st h em o d e lo f i n t e r d o m a l nt r u l 五ce n g i n e e r i n ga n dt h ec h a r a c t e r i s t i co fi n t e r d o m a l nt r a f f i ce n g i n e e r i n g b a s e do ub g p , a n ds u m m a r i z e st h er e c e n tr e s e a r c h 1 v 墨些苎兰壁主壁垒建查叁墨! 里塑 t h em o d e lo ft h ea st o p o l o g yi nt h ei n t e r a c ta n dt h ec o n s t r u c t i o no fr e a l a s t o p o l o g ya r ea n a l y z e di nd e t a i l e d b ya n a l y z i n gt h ee v o l u t i o no fa st o p o l o g yi nt h e i n t e m c t ，w es u m m a r i z et h er u l eo fn o d ec o n n e c t i v i t y , a m e n dt h ep a r a m e t e ro fb am o d e l ， a n dc o m p a r et h et o p o l o g yg e n e r a t e db yt h eb am o d e lw i t ht h ei n t e r a c tt o p o l o g y t h i s d i s s e r t a t i o na n a l y z e st h ec h a r a c t e r i s t i co fa sh i e r a r c h i c a ls t r u c t u r e ，e m p h a s i z e st h e c h a r a c t e r i s t i co ft h es t r u c t u r eo ft o pt i e ra sa n dt h ep a t ho fi n t e r d o m a i nr o u t e ，a n du s e s t h e p a t h i n f o r m a t i o n i n c l u d e d i n b g p r o u t i n g t a b l e t o j 疵r t h e t i e r o f e a c h a s a c c o r d i n g t ot h es t r u c t u r ec h a m d e f i s f i co fd i 岱e r e n tt i e ra s t h er e c e n tr e s e a r c ho nr o u t e rt o p o l o g y i nt h ei n t e r a c ta n dt h et o o l su s e dt op r o b er o u t e ra r es u m m a r i z e d , a n dt h ee x i s t e n t p r o b l e m si nt h er o u t e rm a d i n ga r ep r e s e n t e d a f t e ri n t r o d u c i n gt h ec o m m e r c i a lr e l a t i o n s h i p sb e t w e e na s e so nc l a s s i f i c a t i o n ， s u m m a r i z i n gt h er e o e n tr e s e a r c ho nr o u t i n gp o l i c i e sa n da sr e l a t i o n s h i p s ，i n t r o d u c i n g t h eg e n e r a lr u l e st os e tm u t i n gp o l i c i e si na c c o r d a n c ew i t ha sr e l a t i o n s h i p s ，a l l a p p r o a c h t o i n f e ra sr e l a t i o n s h i pf r o ms e v e r a lb g pr o u t i n gt a b l e si sp r o p o s e d a c c o r d i n gt ot h ec h a r a c t e r i s t i co fa sp a t hs t r u c t u r ei nat i e r - 1a s sr o u t i n gt a b l e , t h i s d i s s e r t a t i o nu s e ss e v e r a lt i e r - 1a s sr o u t i n gt a b l e st ov e r i f yt h ei n f e r r e da sr e l a t i o n s h i p ， u s e so t h e rr o u t i n gt a b l e st ov e r i f ya s s i s t a n t l y c o m p a r e dw i t ho t h e rs i m i l a ra l g o r i t h m , t h ea l g o r i t h md o e sn o tu s ee x p e r i e n t i a lp a r a m e t e ra n dt h er e s u l th a sh i g h e rc o r r e c tr a t i o d e t a i l e d l ya n a l y z et h et e c h n o l o g i e sw h i c h nb eu s e dt oc o n t r o li n t e r d o m a i n i n c o m i n gu a m ca n do u t c o m i n gu a 饪i ci n c l u d i n gl o c a lp r e f e r e n c e , a sp a t hp r e p e n d i n g , c o m m u n i t ya t t r i b u t ea n dm e d a la n dc o m p a r et h ea d v a n t a g ea n dd i s a d v a n t a g eo fe a c h w a y t h i sd i s s e r t a t i o np r e s e n t sa l le x a m p l eu s i n gs s f n e tt os i m u l a t ef l o wc o n t r o l ， e v a l u a t e st h ee f f e c to f a sp a t hp r e p e n d i n g c o n s i d e r i n gt h es t a b i l i t yo fi n t e r d o m a i nm u t i n ga n dt h ec h a r a c t e r i s t i co fu 8 伍ci n l a r g es c a l ea s e s ，w e 哪ct h a tp o p u l a rp r e f i x e sw i t hl a r g ev o l u m et r a f f i ca n dt h e r e l a t i v es t a b i l i t yo ft r a f f i ca n di n t o r d o m a i nr o u t i n ga t h ep r e c o n d i t i o no fi n t e r d o m a i n t r a f f i ce n g i n e e r i n gb a s e do nb g p o n l yw h e ns e l e c t i n gp o p u l a rp r e f i x e sr e a s o n a b l ei n c o n t r o l l i n gi n t e r d o m a i nt r a 伍cb a s e do i lu s i n gb g p t oc h a n g er o u t e ，ab e t t e re f f e c tc o u l d b eo b t a i n e d s e v e r a ls c h e m e so fd y n a m i cs e l e c t i n gp r e f i xa r ci n t r o d u c e di nd e t a i la n d t h e i ra d v a n t a g ea n dd i s a d v a n t a g ea r ec o m p a r e d t r a n s i ta s e sa n ds t u ba s e sh a v e d i f f e r e n ti 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 go b j e c t s a c c o r d i n gt ot h e s eo b j c c t e s ，t h i s v 东北大学博士学住论文 d i s s e r t a t i o nc o n s t r u c t st w od i f f e r e n tm o d e l e s i no r d e rt oo b t a i nt h ep a r t i c u l a r 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 go b j e c t , r e a lt r a f f i cv o l u m em e a s u r e di nn e t w o r ki su s e d t op l a nt h ei n t e r d o m a i nt r a f f i cf u rt r a n s i ta sa n ds t u ba sr e s p e c t i v e l y b e c a u s eo ft h e h u g eo fc a l c u l a t i o n ，g ai ss e l e c t e dt oc a l c u l a t et h ep l a n n i n g t h et r a 岱cd a t am e a s u r e d i nt h e a b f l e n en e t w o r ki su s e dt ov e r i f yt h ea l g o r i t h m k e yw o r d s ：i n t e r d o m a i nm u t i n g ；b o r d e fg a t e w a yp r o t o c o l ；i n t e r d o m a i nt r a 位c e n g i n e e r i n g ；m u t i n gp o l i c y ；n e t w o r kt o p o l o g y ；a sr e l a t i o n s h i p ；g e n e t i ca l g o r i t h m - 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究 成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果， 也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： 认惫、 日 期：2 、， 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规 定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论 文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关 数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 查些垄兰堡主兰竺垒墨 苎= 主童垒一 第一章绪论 1 1 研究背景 i n t e r n e t 在过去的十几年中迅速演变成一种非常重要的通讯基础，广泛应用 于经济、教育、科学、社会各方面。同时，i n t e r n e t 通讯服务业中的竞争越来越 激烈，终端用户也不断要求他们的服务提供商提供更高的服务质量。结果，大规 模i p 网络尤其是公共i n t e r n e t 骨干网的性能优化，已成为一个很重要的问题。 网络性能要求是复杂的、多样的、有时甚至是矛盾的，这使得流量工程问题富有 挑战性。 i n t e r n e t 流量工程是i n t e r n e t 网络工程的一部分，涉及i p 网络的性能评价、 性能优化问题，包括i n t e r n e t 流量的测量、描述、建模、控制等方面的理论和应 用技术。i n t e r n e t 流量工程的主要目的是在流量和资源级别上提高网络的性能， 促进可靠的网络操作。 网络优化是通过容量管理和流量管理实现的。容量管理包括容量规划、路由 控制、资源( 如链踌带宽、缓存空间、计算资源) 管理等。流量管理包括节点流量 控制( 如队列管理、流量规划) 、通过网络的数据流控制、为不同的包或数据流分 配不同的网络资源等。i n t e r n e t 流量工程的优化目标需要通过不断地、渐进地改 善网络性能才能实现。为了增强网络的性能，流量工程也要求不断地发展新技术 和新方法，而新技术、新需求的出现又会引起优化目标发生变化。不同的网络可 以具有不同的优化目标，优化目标依赖于网络的商业模式、容量以及操作限制。 然而，不管在哪种特殊环境下有什么样的具体优化目标，优化最终都需要通过对 网络进行控制来实现。 i n t e r n e t 的目的是将信息从源节点传输到目地节点，相应地，i n t e r n e t 最重 要的一个功能是将数据从入口节点路由到出口节点。因而，i n t e r n e t 流量工程的 一个最具特色的功能是控制、优化路由，以便引导流量以最有效的方式通过网络。 本文主要从路由角度考虑i n t e r n e t 流量控制。 i n t e r a c t 是由超过1 9 ，0 0 0 多个相对独立的自治域组成的。这些自治域称为自治 系统( a u t o n o m o u ss y s t e m ，a s ) 。自治系统内部的路由器运行域内路由协议( i g p ) 。 东北大学博士学位论文 第一章诸论 每个自治系统可以自主决定采用什么样的域内路由协议，如路由信息协议( r i p ) 、 开放最短路径优先协议( o s p f 3 、中间系统中间系统协议( i s - l s ) 。自治系统之间通 过域间路由协议( e g p ) 交换域间网络可达信息【2 】。当前实际使用的域问路由协议是 边界网关协议c b g p ) 。 i n t c r n e t 路由分为域内路由和域问路由两部分，相应地，i n t e r a c t 流量工程也有 域内流量工程和域间流量工程之分。域内流量工程对一个自治域内部的流量进行 优化，而域间流量工程则是对一个自治域到另一个自治域的域间流量进行性能优 化。 由于网络管理者可以管理域内运行i g p 的所有路由器，因此他们可以完全控 制域内路由例如，网络管理者可以配置链路权重值控制0 s p f 路由中的最短路径 选择 3 1 。多协议标记交换 心l s ) 技术为域内流量工程提供了技术支持。近期大部 分流量工程的研究和标准化工作集中在i g p 方面【】。 然而，一个大的口骨干网所承载的大部分流量要通过多个a s ，这使得域间流 量工程也非常重要例如，在如下的几个方面都需要域间流量工程： ( 1 ) 域间链路拥塞：在i n t e r n e t 中，拥塞通常发生在域问链路。如果检测到某 条域间链路过载，网络管理者可以改变域问路径将部分流量分担到其他负载较轻 的域间链路上。 ( 2 ) 链路容量更新：大的口骨干网经常安装新的高带宽域间链路。使用这些 新加的容量需要修改路由，将原来经其他链路传输的流量转到新链路上来。 ( 3 ) 违反了对等协议：两个自治系统之间的商业协议限制他们之间交换的数据 量。例如，假设协议商定出流量和入流量之比限定在1 5 ，如果超出了这个比例， 自治系统就需要将部分流量转到其他的邻居。 当前，m i l s 对流量工程提供支持只局限在自治域内部【4 1 ，因而，现在唯一可 用的方法是使用边界网关协议进行域间流量控制。然而，b g p 4 没有对流量工程提 供显式的支持，网络管理者只能通过调整b g p 配置来调节域间流量，因而，i e t f 流量工程工作组指出l l 】，“通常是以一种反复实验佃a la n de r r o r ) 的方式应用域间流 量工程”。 流量工程处理过程可分为四个步骤f 1 1 ，如图1 1 所示。 ( 1 ) 定义控制网络的相关控制策略。这些策略可能与很多因素有关，如网络所 采用的主要商业模式、网络的费用结构、操作限制、优化标准等。 东北大学博士学位论文 第一章诸论 图1 1 流量工程过程模型 f i g 1 1t r a f f i ce 丑曲嘲 血gp r o c e s sm o d e l ( 2 ) 获取网络的测量数据。测量对流量工程功能非常重要。只有通过测量才 能确定网络的运行状态，获得流量工程所需的反馈数据，确定网络的服务质量以 及评价流量工程策略的效力。 ( 3 ) 分析网络状态、描述流量大小。性能分析可以预期将来可能出现的潜在问 题，也可以针对现有问题，分析其产生原因，评价各种解决问题的可能方法。 ( 4 ) 网络的性能优化在性能优化阶段，从可行的解决方案中选出最佳方案并 执行。性能优化包括使用适当的技术控制网络提供的流量或控制网络中流量的分 布。优化中可能涉及到添加额外的链路、增大链路容量、使用额外的硬件、系统 调节路由相关的参数( 如i g p 的度量值、b g p 属性) 、调节流量管理参数等。 在流量优化过程中，上述四个步骤可能需要循环进行多次才能获得良好的网 络性能。i n t e r a c t 域问流量工程也应该按照上述四个过程实行，在策略的制定、性 能优化的实施以及网络状态的分析等方面域间流量工程都与b g p 直接相关。 1 2b g p 协议撅述 r i p 中应用的距离向量协议和o s p f 中采用的链路状态协议作为域问路由协议 都不是很有效1 9 j ，b g p 采用了一种称为路径向量路由选择的技术1 2 1 。 在距离向量协议中，每个路由器都向其邻站播发一个向量，其中列出可达的 每个网络，加上到达的距离度量值以及到该网络的路径。每个路由器都根据其邻 站的更新向量建立一个数据库，但并不知道各个特定路径上都有哪些中间路由器 和网络。将它应用于域问路由选择协议时存在两个问题： 1 距离向量协议假定所有的路由器都采用相同的距离度量，并用这个距离度 量来判断路由器的选择顺序。但在不同的自治系统间并不完全这样。如果不同的 路由器对于一个给定的度量赋予不同的含义，那么就不能产生稳定的路由。 2 一个给定的自治系统可能会与其他自治系统有不同的优先级，它也可能会 有一些关于禁止使用某些其他自治系统的路由策略。距离向量协议无法给出沿途 东北大学博士学位论文 第一章诸论 经过的各个自治系统的内部信息。 在链路状态路由选择协议中，每个路由器都要向所有其他的路由器广播其链 路状态度量值，每个路由器建立起配置的完整拓扑映象然后进行路由选择计算。 链路状态路由算法应用于域问路由选择协议也有问题： 1 不同的自治系统会采用不同的度量方案，会有不同的限制。尽管链路状态 协议确实要求路由器建立起完整的拓扑映象，不同自治系统中采用的度量方案可 能不一样，要执行一致的路由选择算法是不可能的。 2 链路状态信息向所有实现外部选路协议的路由器的洪泛发送涉及到多个自 治系统中的路由器，这很可能是无法管理的。 b g p 采用的路径向量方法舍弃了路由度量值并且只是简单地提供哪个网络经 由哪个路由器可达，以及必须经过哪些自治系统路径向量方法与距离向量方法 有两点不同：首先，路径向量方法不包含距离或耗费的计算；其次，每个路由信 息块列出沿着某路由到达目标阿络要经过的所有自治系统。 路径向量中列出了数据包沿着某条路由必须穿过的自治系统，其中包括的信 息使路由器可以按照某种策略选择路由。也就是说，路由器可以根据是否要避开 某个自治系统而决定避开某条特定路径。例如，需要保密的信息可以限制它只能 穿越某些特定自治系统，如果路由器知道互联网上某些部分的性能或质量，它可 以避开某些性能或质量不好的自治系统。 为了在自治系统间交换网络可达信息，b g p 运行在自治系统之间的边界路由 器上。运行b g p 选路处理程序的路由器通常叫做b g p 发言者。两个b g p 发言者 相互间构成交换选路信息的连接。这两个路由器就称为相邻体或对等体对等路 由器交换多种消息以开放并确认连接参数。不同a s 之间的b g p 对等体称为外部 对等体，同一a s 内部的b g p 对等体称为内部对等体。 s l 图1 _ 2 简单互联网示例 f i g 1 2a s i m p l ei n l e t n e t - 4 东北大学博士学位论文 第一章诸论 外部对等体之间运行外部b g p ( f - , b g p ) 。外部b g p 在两个a s 之间传递网络的 可达信息。内部对等体之间运行内部b g p ( i b g p ) 。内部b g p 将从外部b g p 获取 的网络可达信息传递给同一a s 内部的b g p 对等体。图1 2 中的路由器r 1 2 和r 3 1 之间运行的就是e b g p ，r 1 2 和r 1 3 之间运行的为i b g p 。 b g p 把t c p 当作它的传输协议( 端口1 7 9 ) 。这就保证了所有的传送可靠性诸 如再传输可以由t c p 管理，而不需要由b g p 自己来实现，这样就简化了复杂程度， 不必把可靠性设计到协议内部。 从b g p 协议的用途出发，定义一条“路由”包含目的网络和到目的网络的路 径属性。b g p 通过路由通告发送网络可达信息。网络用“前缀”的形式表示，由 网络地址和掩码两部分组成，例如，1 9 2 1 6 8 0 o ，2 4 表示王p 地址为 1 9 2 1 6 8 0 0 - 1 9 2 1 6 8 0 2 5 5 之间的地址块。b g p 路由器在下列两种情况下通告某个 网络的路由：本a s 内部的网络；从另一个a s 接收到该网络的路由通告。 最初，在一系列b g p 发言者之间建立b g p 会话时，所有的候选b g p 路由都 被交换。会话建立并且最初的路由交换完成之后，当网络信息改变时，只发送增 量的更新。就c p u 开销以及带宽分配与其他协议使用的完整的定期更新相比较而 言，增量更新的方法体现了巨大的改进。 路由在一对b g p 发言者之间通过u p d a t e 消息广播。b g p 路由器接收 u p d a t e 消息，对消息运行某些策略或过滤，然后把路由传送给其他b g p 对等体。 在到同一个目的地存在多个路由的情况下，b g p 不是把所有这些路由扩散给其对 等体，而是挑选并发出最好的路由。除了在对等体间传送路由之外，b g p 路由器 还可以产生路由更新，通告给属于其本身自治系统的网络。 u p d a t e 消息中包括一个 数组的列表，它表示通过每个发言者 可到达的目的地的列表。u p d a t e 消息还包括路径属性，诸如某个特定路由的优 先级别的信息，某条路由以及路由经过的a s 列表。如果一个路由变得难以到达， b g p 发言者就会通过撤消无效路由，来告知它的相邻体。撤消的路由是u p d a t e 消息的一部分。它们是不能再供使用的路由。如果路由改变或者对同一个前缀选 择了新的路径，就不需要撤消，只需要通告代替的路由。 b g p 通过如下三种方式告诉对等体先前的路由通告不再使用： ( 1 ) 在u p d a t e 消息中的w i t h d r a w nr o u t e s 域内通告先前广播的路由 目的地口前缀，这样相应的路由被标志不再使用。 ( 2 ) 重新通告到目的网络的路由。 东北大学博士学位论文 第一章诗论 f b g p 发言者发言者的连接被关闭，强制撤消这一对发言者通告的所有路 由。 如果一个b g p 发言者选择路由通告，他可以在通告路由到对等体之前加入和 修改路由的路径属性。因此，自治系统在路由通告中，通过修改路径属性可以加 入自己的控制策略。 b g p 的一个重要的特点就是它的路径属性的思想。这些属性包含在u p d a t e 消息中，与网络前缀一起对外通告。b g p 属性是一套参数，用来标记路由中的特 定信息，如路径信息、路由优先级、路由的下个中继值和聚合信息等。每个u p d a t e 消息都有一个可变长度的路径属性的序列。路径属性由三部分组成，它的形式是 ，长度可变。属性类型是两个字节的字段，包括1 字节属性标记、1 字节属性类型代码。 b g p 的路径属性有公认盛遵、公认自决、可选传递和可选非传递4 种类型， 这4 种类型由路径属性标记字段的前两位表示。 公认必遵属性是b g p 的u p d a t e 数据包中必须存在的属性。它必须能被所有 的b g p 工具识别。如果公认属性丢失，就会出现通知差错。这是为了保证所有的 b g p 工具统一于一套标准属性。公认必遵属性的一个例子是a s 属性。_path 公认自决属性是能被所有的b g p 工具识别的属性，但是在b g p 的u p d a t e 消息中可发可不发。公认自决属性的一个例子是l o c a lp r e f ( 本地优先) 。 除了公认属性以外，一个路径可以有一个或多个可选属性。可选属性并不要 求所有的b g p - r 具支持它，可选属性可以是过渡或非过渡的。 可选过渡的是指如果b g p 工具不能识别可选属性，它就去找过渡标记看它是 否被置为该特定属性如果标记已置位，也就是该属性是过渡的，b g p 工具就应 接受这个属性并把它向前传递给其他b g p 发言者。可选非过渡是指当可选属性未 被识别而且过渡标记未要位时( 属性是非过渡的) ，这个属性应被忽略，不去传递给 其他b g p 对等体。新的过渡可选属性可能被路径的初始者或者路径上的某个a s 附加到路径上。如果他们不是由初始者附加的，那么属性标志八位组中的奇偶校 验位被置1 。附加新的非过渡可选属性的规则随特定属性的性质而有所不同。所有 的可选属性( 过渡和非过渡) 都可以被路径上的a s 更新。 下面列出几个基本的b g p 路径属性： o r i g i n ：公认必遵属性。它定义了路由信息的来源，用一个字节表示。o r i g i n 属性有如下3 种取值： 东北大学博士学位论文 第一章诸论 0 ：1 6 p 表明n l r i 由本地自治系统内部产生的； 1 ：e g l l _ 表明n l r i 是通过外部网关协议得知的； 2 ：d 啪 伸i 捌 b 表明n l r i 是由其他方法得知的； b g p 在进行决策过程中考虑起点属性以便在多个路由中建立优先级别。特别 是，b g p 优选最低起点类型的路径，即i g p 低于e g p ，而e g p 低于i n c o m p i e i e 。 a sp a t h ：公认必遵属性，它包括路由到达一个目的地所经过的一系列的自 治系统号码。在一个自治系统内部，在b o p 发言者中传递的路由的a sp a t h 信 息都是保持原样的，但是，产生路由的a s 在把该路由发送到它的外部b g p 对等 体时，要加上自己的a s 号码。此后，每个接收路由并传送给其他b o p 对等体的 a s 都将把自己的a s 号码加到捧列表的最前面。最后的排列表表示了一个路由经 过的所有a s 号码，产生该路由的a s 的a s 号码捧在排列表的最后。这种a sp a t h 排列表称为a s 序列。 b g p 用a sp a t h 属性作为路由更新的要素以保证因特网的无循环拓朴。在 b g p 对等体间传递的每个路由将承一个该路由已经通过的所有a s 号码的排列表。 如果路由通告给一个a s ，该a s 的号码已经存在于a s 序列之中那么u p d _ k r e 将被忽略。 a sp a t h 信息是b g p 为了确定到一个目的地的最佳路由要考察的属性之一。 在比较两个或两个以上的不同路由时，假如所有其他属性都相等，b g p 总是挑选 最短的a sp a t h 。在二者相等时，就要靠其他属性决定到目的地的最佳路径了。 n e x t _ h o p ：公认必遵属性。在i g p 中，到达个路由的n e x th o p 是已 通告了路由的路由器的连接接口的口地址。在b g p 中n e x th o p 略为复杂，并 取下面三种形式之一： 对于e b g p 对话：n e x th o p 是宣告了路由的相邻体的坤地址。 对于i b g p 对话：对于a s 内部产生的路由，n e x t _ h o p 是宣告了路由的相 邻体的口地址。 对于经e b g p 注入到a s 的路由，从e b g p 得知的下个中继是不变地送到i b g p 中。n e x t _ h o p 是从中得知路由的e b g p 相邻体的口地址。 m u l t i _ e x i t _ d i s c r i m i n a t i o r ( m e d ) ：可选非过渡属性，用在e b g p 之问，它可以提示外部邻居如何优选路径进入一个拥有多个入口的a s 。m e d