（通信与信息系统专业论文）自治系统商业关系稳定性分析.pdf

摘要 摘要：互联网路由采用双层架构体系：域内路由选择和域日j 路由选择。域有自 己的路由策略并且作为一个完整的系统进行独立管理，称为自治系统( a s ) 。域 | 日j 路由的选路协议b g p 是基于策略的路由协议，它允许每个管理域问的商业契约关 系对i n t e r n e t 结构和端到端性能起关键作用。因此，明确管理域( a s ) 之间的关系 对理解i n t e r n e t 结构具有重要意义。 目前对互联网中自治系统间商业关系主要基于推断的研究，针对a s 间商业关 系的推断算法验证评价的相关研究较少。本文首先研究了自治系统的输入输出策 略，分析了a s 关系对b g p 路由的制约，详细叙述了a s 关系推断的原理及实现过程， 并分析研究了目前比较权威的a s 关系推断算法。其次，本文从a s 关系的两个固有 属性：a s 关系是变化的网络中相对稳定的元素和a s 之间p r o v i d e r c u s t o m e r 关系无 环的角度出发，提出了对推断a s 关系算法的评价标准。并对c a i d a 推导的连接关系 进行验证。 关键词：a s 关系；路由策略；b g p 分类号：t p 3 9 3 0 2 b 鏖窒迪厶堂亟堂垃监塞垦s 工曼至 a b s t r a c t a b s t r a c t ：t h ei n t e r a c t sr o u t i n ga r c h i t e c t u r ei ss t r u c t u r e da sat w o l e v e lh i e r a r c h y ： i n t r a d o m a i nr o u t i n ga n di n t e r d o m a i n r o u t i n g e a c hr o u t i n g d o m a i ni sas i n g l e a d m i n i s t r a t i v es y s t e m ，o p e r a t e d 谢t h i nau n i f o r ms e to f r o u t i n gp o l i c i e s ，a n di so p e r a t e d i n d e p e n d e n t l yf r o ma n yo t h e rd o m a i n ，w h i c hi s i st e r m e da n “a u t o n o m o u ss y s t e m ( a s ) t h ei n t e r d o m a i nr o u t i n gu s e sb o r d e rg 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 g i n f o r m a t i o na m o n ga s s ，w h i c ha 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 g p o l i c i e s i tm a k e se v e r ya s sc o m m e r i c a lc o n t r a c tt h ek e yo f t h ei n t e r n e t ss t r u c t u r ea n d t h ep e r f o r m a n c eo fp o i n tt op o i n t t h u si ti si m p o r t a n tt oi d e n t i f yt h er e l a t i o n s h i p b e t w e e na s sf o rc o m p r e h e n d i n gt h ei n t e r n e ts t r u c t u r e a tp r e s e n t ，t h e r ea r el o t so fe f f o r t sf o c u so ni n f e r r i n gt h ea s s r e l a t i o n s h i p b u t t h e r ei sal i r l em a t e r i a la b o u tt h ei n f e r e n c e s v a l i d a t i o na n de v a l u a t i o n t h i sp a p e rh a s i n t r o d u c e dt 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 so nc l a s s i f i c a t i o n ，t h eg e n e r a l r u l e st os e tr o 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 ，d e t a i l e d l ya n a l y z e dt h e t h e o r yo fi n f e r r i n gt h er e l a t i o n s h i pa n di t sp r o c e s s ，s u m m a r i z e ds e v e r a la p p r o a c h e st o i n f e ra sr e l a t i o n s h i pf r o mb g p r o u t i n gt a b l e s t h e nt h i sp a p e rg i v e sa ne v a l u a t i o nf o r t h e a c c u r a c yo ft h ea s s r e l a t i o n s h i pi n f e r r i n ga l g o r i t h mf r o mt w op r i n c i p l e s ：1 c o m m e r c i a lr e l a t i o n s h i pb e t w e e na s ss h o u l db ear e l a t i v e l yi n v a r i a b l ee l e m e n t2t h e r e s h o u l dn o th a v ec i r c l e sa m o n gp r o v i d e r - c u s t o m e rr e l a t i o n s h i p ，w h i c hm e a n so n ea s s a n c e s t o rs h o u l d n tb ei t sd e s c e n d a n t t h er e l a t i o n s h i ph a sb e e ni n f e r r e di nc a i d ai s e x p e r i m e n t e d k e y w o r d s ：a sr e l a t i o n s h i p ；r o u t i n gp o l i c y ；b g p c l a s s n o ： t p 3 9 3 0 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数掘库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：髹喜 签字日期：瑚0 7 年应月2 7 日 导师签名： 签字同期： 屠节 ，氟蝴 、胛下 e 立銮堑占堂亟堂僮迨塞丝剑性主明 独创性声明 本人卢明所，交的学 上论文是本人在导师指导r 进行的研究：作羽f 取得的研究成聚，除 了文中特别加咀杯注平致谢之处外，论文中不包古其他人已经发表或撰写过的研究成果，也 不包含为获得北京交通人学或其他教育机构的学位或i 止f ；而使_ l i ；| 过的材料。与我一同i ：作的 同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了酣意。 学位论文作者弛幺余隶 签字日期：2 口萨f ) 月刁日 致谢 本论文的工作是在我的导师郭字春副教授的悉心指导下完成的。在我的论文 选题、课题研究和论文撰写等方面郭老师给予精心指导，倾注了大量的心血。郭 老师渊博的学识、严谨的治学态度、敏锐的学术洞察力以及对科学的不懈追求精 神，一直不断地在鞭策和激励着我，将使我受益终生。 同时，郭老师那种和蔼可亲、平易近人的师者风范也深深地影响着我。在整 个攻读硕士期间，郭老师在学习、工作和生活上给予我的无微不至的关怀将令我 终生难忘。我将不辜负郭老师对我的殷切期望，在今后的学习和工作中更加刻苦 努力，积极进取。 感谢李磊博士在论文写作过程中给予我帮助和指导，并对本文提出许多有价 值的意见和建议，感谢黄祖真同学在本文代码的编写工作上给予我大量帮助和指 导。感谢北京交通大学通信网络实验室给我的研究提供了良好的实验环境和学习 氛围。 感谢我的父母在我读研期间给我的支持和鼓励。 e丞童道厶堂亟堂位丝塞绻诠 1 绪论 1 1 本课题研究的目的 i n t e r n e t 作为人类社会信息化的标志，已经广泛应用到社会生活的各个方面， 其规模高速膨胀，日益复杂。如今i n t e r n e t 的“面貌”与其原型a r p a n e t 已大相径 庭。 i n t e r n e t 将整个路由环境划分为独立管理的自治系统( a s ) ，这些自治系统间 的路由通告和路由传递由域间路由协议边界网关协议( b g p ) 决定。b g p 协议允许每 个自治系统使用自己的策略宣告和接收路由，选择最佳路由。a s 之间商业合同关 系已经成为决定路由策略的最重要因素。由此可见，通过a s 之间的关系可以考察 不同管理部门网络间的连接关系和运营情况，为优化网络结构和网络接入提供依 据：同时a s 的属性信息是重要的网络资源，掌握它对国家的网络管理与网络维护 有深远的意义。 尽管自治系统关系对我们理解i n t e r n e t 结构具有重要作用，但是并没有公共可 用的数据库存储自治系统关系。近几年来，对互联网中自治系统间商业关系的推 断和研究已经成为互联网特征研究领域中的热门之一。这些算法基本都通过对路 由数据的提取、分析，计算出自治系统问相互的商业关系。不同的算法有不同的 局限性。自治系统间的商业关系是商业机密，推断自治系统问关系以后，无法进 行事实验证。这些算法孰优孰劣，孰能真实地反映自治系统的关系，正是一个亟 待解决的问题。 1 2 国内外的研究及现状分析 l x g a o “1 较早地进行了推断a s 之间商业关系的研究，基于a s 规模与其角色之 间的关系、节点度与a s 规模以及与路由表项模式之间关系的假设，给出了3 个递进 推断a s 关系的启发式算法，将a s 拓扑图中的边分为p r o v i d e r - t o c u s t o m e r ( p 2 c ) 或c u s t o m e r t o p r o v i d e r ( c 2 p ) ，p e e r t o p e e r ( p 2 p ) 和s i b li n g t o s i b li n g ( s 2 s ) 等三类。通过采用b g p 团体( c o m m u n i t y ) 属性进行验证，对不同的b g p 路由表， 算法推断的准确率介于9 4 1 一9 9 4 之间“3 。此外，还进一步推断和刻画a s 所采用 的输入、输出路由策略，对输入策略的分析发现，大多数a s 依次优先选择来自 c u s t o m e r ，p e e r 和p r o v i d e r 的路由，这符合a s 商业关系。g e 等人”1 的研究表明，具 e壅室迪厶堂亟堂位垃塞缝诠 有商业关系的a s 级拓扑图( 有向图) 与只表示互连结构的 s 级拓扑图( 无向图) 的某 些拓扑性质，例如图的直径，存在较大差别，这说明了分析a s 之间商业关系的重 要性。 1 和 6 中推断a s 商业关系的方法本质上是基于a s 节点度的方法。 s u b r a m a n i a n 等人“1 基于汇集的b g p 路出表构造出无向a s 级拓扑图后，采用迭代 去除叶节点的算法给图中每个节点赋予一个等级标号，然后根据等级标号而不是 节点度来推断a s 之间的商业连接关系。k x u 等人”1 通过分析i n t e r n e t 上i x p 的地理 分布及a s 互连特点，辅助推断a s 之问的商业关系。对p 2 p 关系的分析表明，i x p 对 a s 拓扑结构以及a s 关系有很大影响。 s u b r a m a n i a n 等人”1 将对无向a s 级拓扑图的边进行定向以反映商业关系的问题 抽象为极大化关系类型( t o r ，t y p e o f r e l a t i o n s h i p ) 问题( m a x t o r ) ，并猜测 m a x t o r 问题为n p 完全问题。很快，e r l e b a c h 等人”1 和b a t t i s t a 等人”1 分别独立地证 明了m a x t o r 问题为n p 完全问题，并各自给出了较好的推断结果。他们还发现m a x t o r 问题不能有效推断p 2 p 关系。 然而，研究表明 9 ， 8 和 3 中只关心最大化有效路径比重的单目标优化的 推断结果包含明显不正确的a s 关系，某些t i e r 一1 层的a s 成为小规模a s 的用户。通 过将推断a s 关系问题扩充为多目标优化问题，采用a s 节点度对最小化无效路径数 量目标函数进行修正，也用2 s a t 子句方式表示路径，但首先根掘w h o i s 信息识别 s i b li n g 关系的边，然后根据a s 节点度大小对边初步定向。通过归约与缩减路径之 后，采用s e m i d e f i n i t ep r o g r a m m i n g ( s d p ) 近似算法推断剩余路径的a s 之问的关 系。实验结果表明，这种基于a s 节点度的多目标优化方法的推断结果更符合实际。 但是，这种方法不能有效地推断p 2 p 关系的算法。 研究a s 关系的工作主要侧重研究准确推断a s 之间商业关系的分析方法。由 于a s 间的商业关系属于企业的商业机密，而查询w h o i s 信息得到的a s 信息往往 有些陈旧，所以a s 推断结果的验证一直是个令人头疼的问题。2 0 0 5 年k c 的研究 团队通过邮件提问的方式向一些a s 所有者确认a s 关系推断结果的正确性，反馈 的结果较好，k c 在 1 0 中有详细说明。自此k c 将c a i o a 1 作为个交流平台，将 每次推断出的a s 关系公布于上，供其他研究者参考。 1 3 本文的主要内容和结构安排 本论文的主要内容是对自治系统间商业关系的研究并对其推断算法的准确性 进行评价。在第二章和第三章中介绍了自治系统间的商业关系，详细分析b g p 路 由协议，尤其是b g p 路由策略和a s 间商业关系的因果关系。 第四章介绍了主流自治系统关系的推断算法，分析其优缺点，提出自治系统 e瘟窑迪厶：兰亟上竺位迨塞绻诠 之| 日j 商业关系的两种基本属性：i s p 之间的商业关系短期稳定性；商业关系的等级 性，即一个a s 的p r o v i d e r 集合不能有其c u s t o m e r 。第五章根据第四章提出a s 的两 个属性构造了推断自治系统关系算法的评价标准，验证c a i d ak c 上的推断结果。 e 壅窑迪厶堂亟= i 三位迨塞自蕴丕堑回的连接 2 自治系统问的连接 2 1 自治系统的定义 i n t e m e t 是一个开放分布式系统，没有个核心的管理机构，是由很多自治系 统( a u t o n o m o u ss y s t e r m ，a s ) 构成的集合。所谓自治系统是在单一技术管理体 系下的多个路由器的集合，例如：研究机构、大学、企业和政府网络。在自治系 统内部使用内部网关协议( i g p ) 和通用参数来决定如何路由数据包，在自治系统 问则使用a s 间路由协议来路出数据包。当前使用b g p v 4 维护域间路由。 在外部世界看来，整个自治系统是一个单一的实体。两个a s 之间的连接形成 一条路径，路径信息的汇集形成到达特定目的地的路由。就b g p 而论，因特网就 是一个a s 图，每个a s 都有一个由互联网授权的管理机构分配的自治系统号( a s n u m b e r ) 。b g p 的基本思想就是希望通过不同的编号来区分不同的自治系统。自治 系统号( a s n ) 由1 6 比特组成，一共具有6 5 ，5 3 6 个可能取值。 2 2 自治系统的互联机制 一个i s p 在管理上可以分为一个或几个a s 。单个a s 体现出i s p 的意志。山于 只有极小一部分i s p 申请多个a s 号在b g p 协议中作为该i s p 部分网络的标示，因 此在实际操作中可以把一个i s p 看作一个a s 。本文对i s p 和a s 将不作区分。 i s p 完全独立决策，并可在所辖a s 内实施路由策略。a s 的互联体现了a s 局 部利益极大化决策的结果。i n t e r n e t 上的i s p 呈现等级关系：- - 4 部分全球传输 i s p ，国家级i s p ，地区级i s p 及本地i s p 。对于有逻辑连接的a s ，等级高的a s 为 等级低的a s 提供接入服务，等级低的a s 向等级高的缴纳费用。由于i n t e r n e t 的 商业运营，各i s p 之间存在竞争，与此同时，各i s p 网络必须与相邻i n t e r n e t 网 络相互合作，才能提供全面连接的传输服务。各i s p 为了利益最大化，尽量缩小 了访问其他网络时跨越的网络个数，并非逐级相连，如同一个国家的两个地区级 i s p 建立直接的连接，这种本地互连将使两个地区级i s p 之间的流量不必经过上级 i s p ，因而不需要为流量为上一级付费。因此相同等级的i s p 根据自身所属信息结 成复杂的商业关系。一级a s 也可能与三、四级a s 相连。减小转发代价是a s 互联 的主要动力。为了提供备用链路以及市场竞争因素，很多i s p 与多个提供者相连， 形成多宿连接。这种非严格的等级模型使现在的a si 日j 的连接变得十分复杂。 4 e 宝窑迪厶堂亟堂位丝塞自渔丕缝回曲迫撞 例2 - 1i n t e r n e t 结构的严格层次模型 f i 9 2 1t h es t r i c t h i e r a r c h y o f t h e i n t e m e ts t r u c t u r e 2 3a s 问的商业关系 a s 之间在利益的驱动下，自动形成四种关系：c u s t o m e r t o p r o v i d e r ( 客户一提 供者) ，p r o v i d e r t o c u s t o m e r ( 提供者一客户) ，p e e r t o - p e e r ( 对等一对等) 或者 s i b l i n g - t o s i b l i n g ( 兄弟一兄弟) 。四种关系中，最多的是客户一提供者关系，客 户向提供者购买传输服务，以便使自己的网络接入i n t e r n e t 。提供者为客户提供 传输服务，但客户通常不为他的两个提供者提供传输服务。在对等关系中，两个 对等体通常是两个较大的i s p ，每个i s p 拥有一定的客户，如果这两个i s p 传输流量 的不少部分是去往其它i s p 的直接相连的客户的，这两个i s p 就可能签订一种对等 协议，两个i s p 之间不用互相付费而各自的用户就可以互相访问，这样就省去了互 相支付费用所需要的管理费用。另外对等协议对i n t e r n e t 的推广和扩展特别有利。 相互传输协议允许两个自治系统互为对方提供至u i n t e r n e t 的连接，互相为对方和 对方客户提供到自己和自己客户的流量通道，这种更加直接的链路可以导致客户 间更好的端一端性能。通过这种协议两个i s p 都获得了更好的连通性。自治系统间 还存在种兄弟关系，两个较小的自治系统由于经费的原因，愿意为对方提供一 个备份通道。这样当一个自治系统到他的提供者之间的连接失效时仍然可以与 i n t e r n e t 相连。 四种关系在相互协商的基础上，为了达到彼此的利益最大化，制定双方都遵守 的规则。这样，在网络经济的驱动下，各个a s 自主合作。自治系统之间的这些商业 合同关系对i n t e r n e t 结构具有重要的影响。 2 4 研究a s 关系的意义 首先a s 的关系代表着i n t e r n e t 结构中最关键的部分。 e 瘟至堑厶堂亟：羔位迨塞臼逾丕统间丝丝缝 ( 1 ) a s l 日j 的物理连接，不意味着可达： 自治系统级拓扑发现和传统的路由器级拓扑发现一个最大区别就在于，a s 间 的选路协议b g p 是基于策略的路由协议，管理域问的商业契约关系对i n t e r n e t 结构 和端到端性能特性起了关键性的作用，如果两个相连接的a s 之j 日j 没有签订商业契 约，那么两者之间没有业务量，就无法互相通信。 例如，三个自治系统a ，b ，c 连接情况如图2 2 ：其中( a ，b ) ，( c ，b ) 均为提供者一客户 关系，我们知道。流量过渡的方向要和付费的方向一致，虽然在拓扑图中a ，b ，c 直接相连，但是b 的本地策略不允许b 在a ，c 之问提供转发服务。所以i s pa 不能通 过i s pc 到达i s pb 。 图2 2 客户和提供者关系图 f i 9 2 - 2p r o v i d e r - c u s t o m e rr e l a t i o ng r a p h ( 2 ) 仅从a s 拓扑连接图上无法得出因特网的结构属性。 即使i s pa 和b 能够通过其他的i s p 相通，其端到端的性能特性也不能从a c | 日j 和 b c 日j 的性能特性推断出来。例如，a b 间的延迟独立于a c 问和b c 间的总延迟。这己 经通过几个测量研究得到证实，因而，互连性( 无论是自治系统层还是路由层) 本 身不能完全表示i n t e m e t 的结构属性。 其次，a s 间的关系是一种重要的网络资源。 ( 1 ) 各个自治系统问连接关系，属于企业内部的私有协定，i s p 不愿意透露其 中的商业秘密，外界很难得到其真实拓扑结构。 ( 2 ) 没有专门的机构来记录a s 之日j 的关系，即使有信息也不完备：同时i s p 之 间结成的商业关系是不断变化的，而w h o i s 库中的信息往往更新速度较慢，不能反 映当前网络状况。 ( 3 ) 自治系统的各种属性信息是一个国家的网络资源，对于网络管理和保持 网络健康发展有重要意义。 再次，在网络服务方面有重要指导意义。 ( 1 ) 设计和优化网络，为管理域的负载平衡，拥塞避免提供参考。 ( 2 ) 研究自治系统关系基础上，可确定自治系统在i n t e r n e t 中的的等级，为 企业或小i s p 提供网络接入的商业协议的依据。 6 立童适厶堂亟竺位迨塞臼筮丕丝回的丝撞 ( 3 ) 比较a s 拓扑图中的逻辑关系和自治系统间的真实关系，发现故障点，减 少误配现象，指导并调试路由器配置文件。 宝銮逢厶堂亟堂篮迨塞煎定s苤丕丝直迭 3 确定a s 关系的方法 3 1 根据w h o i s 库提供的a s 信息进行研究 这是最直接的方法，各机构在申请注册a s 号时，会向注册机构登记一些机构 名称、所在地区、路由输入输出策略等信息。亚太网络信息中心( a n p i c ) 、因特网 号码北美注册处( a r n i ) 和i p 网络欧洲协调中心( r i p e ) 都设立了w h o i s 数据库，允许 个人和组织查询分配的i p 地址和自治号码信息。我们通过w h o i s 查询，就可以得到 关于某个a s 的这些信息。然而w h o i s 数据库中的连接信息都是建立网络申请自治系 统号码时的资料，互联网是动态变化的，单纯使用这种方法来推断a s 间的关系， 很难即时反映网络的实际路由状况。 3 2 根据b g p 路由表的路径属性进行研究 每个自治系统都是根据它与其它自治系统之间的关系来制定输出策略，自治 系统间通过b g p 路由器连接起来，b g p 是一种不同自治系统的路由器之间进行通信 的外部网关协议。所以路由表在某种程度上反映了自治系统的输出策略，基于这 个事实可以从路由表中推导a s 之间的关系。 在本节中，我们在b g p 路由机制和输出策略的基础上，对自治系统关系图描述 及对应的路由表项模式进行研究，给出从路由表推导自治系统关系的算法。 3 2 1b g p 概述及其选路原理 b g p 协议对i n t e r n e t 拓扑没有限制，交换的路由信息包括一个a s 序列，表示可 达信息所经过的自治系统，所以b g p 协议也被称为路径向量协议。通过a s 路径序列 可以有效地构造a s 拓扑、消除路由环路和在a s 上实施策略选路。同时b g p 也是一种 基于策略的协议，每个a s 按照自己的路由度量标准在多个到达目的网络的路由中 选择最佳路由，这个度量由网络管理员来确定，可以基于任何标准，包括路由所 经过的a s 数、链路稳定性、速度、延迟或费用。一个a s 只有在愿意为某个a s 转发 到目的网络的流量时，才向其发送路由信息。 3 2 2b g p 路由及其通告 b g p 使用“递增式”( i n c r e m e n t a i ) 的更新机制，即b g p 会话路由器只有在连接 些毫窑适厶堂亟! ：堂位途塞煎定墨苤丞煎直壁 建立之初j 会交换完整的路由信息，此后，当网络可达信息发生变化时，对等体 之间只交换发生变化的路由更新信息。b g p 协议的消息共有四种类型，分别是打开 ( o p e n ) 消息、更新( u p d a t e ) 消息、保活( k e e p a l i v e ) 消息和通知( n o t i f i c a t o i n ) 消 息。b g p 传输连接成功建立后，对等体之1 日j 通过交换o p e n 消息确认连接参数，通过 u p d a t e 消息交换路由信息，初始交换的数据是整个b g p 路由表。之后，只有当路由 表发生改变时，才发送增量的u p d a t e 消息。b g p 发言者通过周期性发送k e e p a l i v e 消息来保证连接的存在，当有错误或者特别情况发生时就发送n o t i f i c a t l o n 消息 并且关闭连接。b g p 发言者之f b j 通告的目的网络就是u p d a t e 消息的网络层可达性信 息( n e t w o r kl a y e rr e a c h a b l ei n f o r m a t i o n ，n l r i ) 域内的i p 地址，路径属性是 u p d a t e 消息的路径属性域内报告的信息。 b g p 路由定义为含有一个目的地址和到这个目的地址的路径属性的信息单位， 可用二维数组 表示。路由存储在路由信息库r i b ( r o u t i n g i n f o r m a t i o nb a s e ) 内。一个b g p 发言者在把路由发送给对等体之前可以加入或修 改路由的路径属性。 b g p 的路径属性： 每个路径属性以三元组 的形式表示。每个路 径属性由l 字节的属性标志位，l 字节的属性类型，l 或2 字节路径属性长度和路径 属性数据组成。b g p 的路径属性有公认强制、公认自决、可选传递和可选非传递4 种类型。公认属性可以被所有b g p 实现识别。其中公认强制属性是必须遵守的，必 须被包含在每一个更新报文中，公认自决可以选择是否在一个特定的更新报文中 发送。所有的公认属性都必须传递给其他b g p 对等体。除了公认属性之外，每个路 径可以包含一个或多个可选属性。并不要求或期望所有b g p 实现支持可选属性。不 可识别的可选属性的处理通过在属性标记字节设置过渡位来进行。新的可选过渡 属性可以由路径始发者或在路径上的任何其他a s 附加到路径上。所有可选属性可 以被在路径上的a s 更新。 几种基本的b g p 路径属性： 1o r i g i n 属性 公认强制属性，类型码l ，定义了路径信息的来源，o r i g i n 属性由产生路由的 自治系统生成，表示相对于发出它的自治系统的路由更新的起点。b g p 有三种类型 的起点： i g p 一网络层可达性信息对于始发a s 是内部的。 e g p - 网络层可达性信息通过e g p 学到。 i n c o m p l e t e - 网络层可达性信息通过其他方法得知。 2a sp a t h 属性 9 e 立交道厶堂亟! ：堂僮j 金塞煎定羞丕曲直洼 公认强制属性，类型编码2 ，包括路由到达一个目的地所经过的一系列自治系 统号。由一系列a s 路径段组成。每一个a s 路径段表示为三元组 。路径段类型是l 字节长度域，包含a s s e t ； f l a s s e q u e n c e 两种 类型。 a s s e t ：u p d a t e 消息中的路由经过的a s 的无序集 a s s e q u e n c e ：u p d a t e 消息中的路由经过的a s 的有序集 路径段长度是1 字节长度的域，指出了在路径段值域的a s 数。路径段值域包含 了一个或者多个a s 号。 ( 1 ) 当b g p 发言者通告从其它b g p 发言者学到的路由时，应该根据路由接收者 的位置，修改路由的a s p a t h 属性。当给定的b g p 发言者通告路由信息到本地a s 的 其它b g p 发言者时，通告者不应该修改路由的a s p a t h 属性，a s p a t h 信息维持原状 不动。当给定的b g p 发言者通告路由到邻居a s 的b g p 发言者时，通告者应该修改路 出的a s p a t h 属性，把自己的a s 号码列到排列表的最前面，产生路由的a s 的号码在 排列表的最后。 ( 2 ) 当b g p 发言者产生路由时，在发送到邻居a s 自治系统的b g p 发言者的所有 u p d a t e 消息的a s p a t h 属性中，起源发言者应该包括自己的a s 号码。在发送到本地 自治系统的b g p 发言者的所有u p d a t e 消息的a s p a t h 属性中，起源发言者应该包括 一个空的a sp a t h 属性。 3n e x t h o p 属性 公认强制属性，类型码3 ，定义了作为到达u p d a t e 消息中指定的网络层可达地 址所用的下一跳边界路由器的i p 地址。 ( 1 ) 对于e b g p 对话，下个中继是宣布了路由的相邻体的i p 地址。 ( 2 ) 对于i b g p 对话，对于a s 内部产生的路由，下个中继是宣布了路由的相邻 体的i p 地址。 ( 3 ) 对于经e b g p 注入至t j a s 的路由，从e b g p 得知的下个中继是不变地发送到 i b g p 中。下个中继是从中得知路由的e b g p 相邻体的i p 地址。 ( 4 ) 当路由在多路访问媒体( 例如：以太网、帧中继等) 上被发送时，下个中继 通常是连接到媒体、产生该路由的路由器接口的i p 地址。 4m u l t ie x i td i s c 属性 可选非传递属性，类型码4 ，4 字节非负整数。属性值可被b g p 发言者用于决策 过程，提示外部邻居如何优选进入一个拥有多个入口的a s 的路径，在相邻自治系 统中区分多个出口。m u l t i e x i t _ d i s c 属性简称为m e d 属性，具有低m e d 值的路由优 先。 m e d 属性表示一个a s 如何影响另一个a s 的出站业务量。如果m e d 属性通过外部 0 e 立銮堑厶堂亟：主位丝塞煎塞s差丞的直鎏 链路得到，m e d 属性可以通过内部链路通告给同一个a s 内的其他b g p 发言者，但不 能通告给外部b g p 发言者。 5l o c a l p r e f 属性 公认自决属性，类型编码5 ，4 字节非负整数。本地优先属性是给予一个路由的 优先程度，具有较高的本地优先属性值的路由优先。b g p 发言者应该为每一条外部 路由计算本地优先，同时在通告路由到内部对等体的时候包括这个优先级。 l o c a l _ p r e f 属性仅在a s 内部对等体之间交换，b g p 发言者不应该把它发送给外 部对等体，如果b g p 发言者收到的u p d a t e 消息包括了这个属性，并且消息来自a s # b 部对等体，则这个属性应该被忽略。 6a t o m i c _ a g g r e g a t e 属性 公认自决属性，类型编码6 。自动聚合属性用于表示路由信息的丢失，如果一 个系统发送造成路由信息丢失的聚合，那么就需要把该路由附上自动聚合属性。 如果b g p 发言者得到一个对等体的一些重叠的路由，而选择了一条更不具体的路 由，而不是选择一条更具体的路由，那么本地系统在通告该路由到对等体时应该 附加a t o m i c - a g g r e g a t e 属性到路由，( 如果属性没有出现在接收的更不具体的路由 中) 。接收到具有a t o m i c _ a g g r e g a t e 属性路由的b g p 发言者，在把该路由通告给别 的b g p 发言者的时候，不应该从路由中去掉这个属性，并且不能对任何n l r i 内的地 址进行分片。 7a g g r e g a t o r 属性 可选传递属性，类型编码7 ，长度为6 字节。该属性包含了最后形成聚合路由 的a s 号码，后面是形成聚合路出的b g p 发言者的i p 地址。 8c o 删u n i t y 属性 可选传递属性，类型编码8 ，长度可变，此属性包含一系列4 个字节值。一个 团体就是一组具有共同性质的目的地，一个团体不限于一个网络或一个自治系统， 它没有物理边界，提供了一种对路由进行过滤、选择的方法。 取值范围在0 x 0 0 0 0 0 0 0 0 到0 x o 0 0 0 f f f f 以及o x f f f f 0 0 0 0 到0 x f f f f f f f f 之间的团 体是保留的，是公认的，具有全球意义。公认的团体有： ( 1 ) n oe x p o r t ：属性值是o x f f f f f f 0 1 ，具有这一属性值的路由不应被通告给 一个a s 之外的对等体。 ( 2 ) n oa d v e r t i s e ：属性值是o x f f f f f f 0 2 ，具有这一属性值的路由不应被通告 给任何b g p 对等体。 ( 3 ) l o c a la s ：属性值是o x f f f f f f 0 3 ，具有这一属性值的路由不应在同联盟 内的两个私有a s 问交换，更不能通告给外部对等体。 一个路由中可以有一个以上的团体属性，在一个路由中看到多个团体属性的 e 盛窒适厶堂亟堂焦迨塞确定苤丕的友鎏 b g p 发言者可以按照一个，几个或全部属性行动。路由器在传递路由到其他对等体 之前可以选择增加或改变团体属性。 b g p 发言者的路由信息库( r i b ) 包括三个不同部分： ( 1 ) a d j r i b s i n ：a d j r i b s i n 保1 字了从接收到的u p d a t e 消息中学习到的路由 信息，这些路由信息经过输入策略机处理或者过滤后作为决策过程的输入。 ( 2 ) l o c r i b ：l o c r i b 存储b g p 发言者根据本地策略在a d j r i b s _ i n 内选择的本 地使用的路由。 ( 3 ) a d j r i b s o u t ：a d j r i b s o u t 存储本地b g p 发言者通告到对等体的路由。 这些路由消息将在相关的输出策略机操作以后通过u p d a t e 消息发送到对等体。 i a d j r i b - i n i - - - q a m r i l l n n d j - r i b 4 n 卜- q a d j - r i b i n b g pb g p 决策过程决策过程 “自r i b - i n i - + | a 由一r i b i n n 自一r i e t n t - - 一 a d j r i b i n 犏 聚略引军稿出泵陌 j i 擎 图3 1b g p 策略的实现 f i 9 3 1t h ei m p l e m e n t a t i o no f b g pp o l i c i e s a d j r i b - i n 包含了从对等节点广播到本地b g p 发言人的无特权的路由选择信 息：l o c r i b 包含了本地b g p 决策后的路由信息：a d j r i b o u t 依靠本地发言者的更 新信息组织路由，广播到特定的对等节点。 3 2 3b g p 路由选择过程 b g p 路由决策过程对a d j i b s _ i n 内的路由施加本地路由策略，选择出本地使 用的路由，并将所选路由施加输出策略发送给对等体。b g p 的路由选择过程是根据 路由的路径属性值进行的，路由选择过程以路由的属性为参数计算每个路由的优 先级别，选择具有最高优先级的路由为最佳的路由，并根据此路由来引导流量。 e 丞窑堑厶堂亟堂位建塞煎定苤丕的直逵 整个路由决策过程分三个阶段，具体描述如下： 1 计算路由优先级。b g p 发言者通过u p d a t e 消息从外部或内部对等体接收路 由，对一个新路由或替换路由，b g p 发言者应计算该路由的优先级别。如果路由通 过i b g p 得到，b g p 发言者可以直接使用l o c a l _ p r e f 属性值为路由的优先级，或者根 据路出策略重新计算路由优先级别。如果路由从外部对等体得到，b g p 发言者就要 根据路由策略计算路由优先级别。 输入策略机施加操作员配置的进站策略，对路由进行过滤和属性操作。从而 决定从哪些对等体来的路由可接受，以及接受其中哪些路由。过滤可以基于i p 前 缀、a sp a t h 属性和其他b g p 路径属性值。b g p 通过输入策略机作路径属性来干预其 本身的决策过程，因而影响其到达给定目的网络实际使用路由。也就是说，会直 接影响到其到达某一目的地所使用的实际路由。例如，b g p 的输入策略配置中要求 不能通过某对等体到达某个网络，则当从该对等体发来的路由中含有该网络号时， 该路由就会被过滤掉。 2 路由选择过程。b g p 决策过程的基础是属性值，面对多个到相同目的地、前 缀长度相同的路由，b g p 选择最好的路由，将业务量发送到目的地。对经输入策略 机处理的路由经过下面的选择过程后存入l o c r i b 。 ( 1 ) 如果下个中继是不可达的，路由就被忽略。 ( 2 ) 选择具有最大本地优先级的路由。 ( 3 ) 如果没有本地始发路由，而且本地优先相同，选择具有最短a s p a t h 的路 由。 ( 4 ) 如果a s p a t h 长度相同，选择最低初始类型的路由( i g p 低于e g p ，e g p 低于 i n c o m p l e t e ) 。 ( 5 ) 如果初始类型相同，路由从同一a s 接收，则优选最低m e d 值的路由。 ( 6 ) 如果路由有相同的m e d 值，优选e b g p 路由而不是i b g p 路由。 ( 7 ) 如果前面所有情况都相同，优选可以通过最近的i g p 邻居到达的路由，也 就是说，使用a s 内部最短的内部路径到达目的地。 ( 8 ) 如果内部路径相同，b g p 路由器i d 就成为决定因素。优选来自带有最低路 由器i d 值的路由。路由器i d 决定是随厂家而不同的。 由决策过程识别的最好路由放在l o c r i b 中。这些路由可以作为候补通告给其 对等体或者放进i p 路由表中。如果路由没有放入l o c r i b 中，它就不能被放进 a d j r i b _ o u t 中通告给对等体。除了从其它对等体学到的路由，边界路由器还产生 关于自治系统内部网络的更新消息。 3 路由分发。只有当l o cr i b 内的路出发生变化时，路由器才向相邻体发送路 由更新消息。路出器使用的路由以及路由器在本地产生的路由都交给输出策略机 b 立銮适厶堂亟曼堂位迨塞确定 s苤丞曲直鎏 处理，在把路由发送给对等体之前，输出策略机可以对它进行过滤，也可以对某 些路径属性进行修改，例如，a s 路径属性在路由发送出去之前一般都要进行修改， 即加上本自治系统的号码。同时输出策略机也区分内部和外部对等体。如果b g p 发 言者从同- - a s 内的对等体获得路由，该路由不应该再被发送给同- - a s 内的其它b g p 发言者。如果b g p 发言者从外部对等体获得路由，且该路由通过路由选择过程被选 为最佳路由，那么该路由就应该发送给内部对等体或外部对等体。 输入过滤城佳路由选择输入过滤 图3 2b g p 路由选择过程 f i 9 3 2t h ep r o c e s so fb