（计算机科学与技术专业论文）互联网域间路由协同配置技术的研究与实现.pdf

国防科学技术大学研究生院硕十学位论文 摘要 路由系统是i n t e r n e t 的核心部分，而作为路由系统的关键基础设施，b o r d e r g a t e w a yp r o t o c o l ( b g p ) 起着举足轻重的作用。但是，b g p 协议本身的局限性同 时也导致了域问路由的安全和性能问题。路由系统由于其自治性和隐私保护，在 配置管理上多a u t o n o m o u ss y s t e m ( a s ) 之间的协同是未来域问路由配置管理的必 然趋势。 本文着重从路由策略管理的角度出发，详细分析了路由配置错误的原因，针 对路由策略配置管理缺陷，提出了路由配置错误的域内静态检查方法和策略冲突 的域间协同监测方法。根据协同管理思想，我们设计并实现了一个域问路由协同 配置检查系统，能够在策略配置管理上进行协同检查和监测。我们主要开展了如 下几方面的工作。 1 、分析当前在路由器配置策略上的错误检查机制的不足，特别针对隐私保护 导致的策略冲突，提出域问路由策略协同思想，在尽可能减少信息泄露的情况下 达到配置策略协同的目的。 2 、分析了当前主要的路由器配置错误类型，针对静态可检查的错误类型，提 出域内检查方法和域间利用隐私隐藏信息共享方法进行协同策略检查；作为对配 置错误检查的补充，针对静态不可检查的错误类型，提出协同监测方法，能够监 测域间路由震荡并确定其性质，同时利用信誉机制防范前缀劫持和确定m o a s 的 源。 3 、针对在协同过程中i s p 之间隐私保护问题，提出了一种隐私隐藏的信息共 享方法，采用信誉评价的方法作为协同的激励机制，能够在协同过程中避免不必 要的信息泄漏。 4 、实现了一个域问路由协同配置系统i s p p o l i c y ，不仅具备单个域内的错误 检查能力，还能够与其他协同者一起进行策略协同检查，能够检查域内路由阻隔、 转发环路、路由不确定和域问策略冲突问题，协同监测域问路由震荡、m u l t i p l e o r i g i na u t o n o m o u ss y s t e m ( m o a s ) ，还能够进行简单的配置辅助生成。 主题词：域问路由，协同，配置检查，路由监测，自动配置生成 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t a st h ed e f a c t os t a n d a r do fi n t e r - d o m a i nr o u t i n gp r o t o c o l s ，b o r d e rg a t e w a y p r o t o c o l ( b g p ) p l a y sa ni m p o r t a n tr o l ei ni n t e m e tr o u t i n gs y s t e m ，w h i c hi st h ek e y i n f f a s t r u c t u r eo fb o t ht h ei n t e r n e ta n dt h eu s e rn e t w o r k s h o w e v e r ，t h el i m i t a t i o n so ft h e p r o t o c o li t s e l fh a v el e a dt om a n ys e c u r i t ya n dp e r f o r m a n c ep r o b l e m s t oc o n q u e r t h e s e b a r r i e r s ，w em a k eas u m m a r yo fr e s e a r c ha b o u tt h et h r e e1 e v e l so nw h i c ht h er o u t i n g s y s t e mw o r k s ，a n dg e tac o n c l u s i o nt h a ti t sa nu r g e n tf o ra st oc o l l a b o r a t eo nt h e r o u t i n gp o l i c ym a n a g e m e n t i nt e r m so fr o u t i n gp o l i c ym a n a g e m e n t ，t oc h e c kt h em i s t a k e si nr o u t i n g c o n f i g u r a t i o n ，w ed e s i g na n db u i l dad i s t r i b u t e dc o l l a b o r a t es y s t e mf o rc o n f i g u r a t i o n m a n a g e m e n t ，a n do u rm a i nc o n t r i b u t i o n sa r ea sf o l l o w s o nt h eb a s i so ft h es t u d yo ns e c u r i t yp r o b l e m so fi n t e r - d o m a i nr o u t i n g ，e s p e c i a l l y t h er o u t i n gs e c u r i t ya c c i d e n t s ，w ea n a l y z et h ed e f e c t so fc u r r e n tm i s t a k ec h e c k i n gi n r o u t i n gc o n f i g u r a t i o n t od e a lw i t ht h ep o l i c yc o n f l i c t i o nc a u s e db yp r i v a c yp r o t e c t i o n ， w eb r i n gu pt h ei d e ao fc o l l a b o r a t i n gi np o l i c yc o n f i g u r a t i o nc h e c k i n g b a s e do nt h ec l a s s i f i c a t i o no fr o u t i n gc o n f i g u r a t i o nm i s t a k e s ，w ep r o p o s e das t a t i c c h e c k i n gm e t h o df o rb o t hi n t r a - a sd o m a i na n di n t e r - a sd o m a i n st oc o n q u e rt h ee r r o r t y p e sc a nb ed e t e c t e ds t a t i c a l l y r e g a r d i n gt h ee r r o rt y p e sc a n t b ed e t e c t e dt h r o u g h s t a t i cm e t h o d s ，w ep r o p o s e dac o l l a b o r a t i n gm o n i t o rm e t h o d ，w h i c hm o n i t o r st h e c o l l i s i o n si ni n t e r - d o m a i nr o u t i n g ，a n du t i l i z e sr e p u t a t i o nm e c h a n i s mt od e f e n da g a i n s t p r e f i xh i ja c k i n ga n dm a k e sc e r t a i nt h es o u r c e so fm o a s t od e a l 、析t hp r i v a c yl e a k i n gi nt h ec o l l a b o r a t i o na m o n gm u l t i - a s w ep r o p o s ea s c h e m eu s i n gt h ep r i v a c yp r e s e r v e di n f o r m a t i o ns h a r i n gm e t h o d ( p p i s m ) t oe x c h a n g e o n l yn e c e s s a r yi n f o r m a t i o n p p i s mi sv e r ye x t e n s i b l ea n dc a nb eu s e df o rm a n yt y p e s o fi n f o r m a t i o ns h a r i n g f i n a l l y ，w eh a v ei m p l e m e n t e das o f t w a r ec a l l e di s p p o l i c y ，w h i c hc a nb eu s e dt o c h e c kt h er o u t i n gp o l i c yo fb o t has i n g l ea sa n dm u l t i - a s i s p p o l i c yc a nd e t e c t r o u t i n gp a r t i t i o n ，f o r w a r d i n gl o o p s ，u n d e t e r m i n e dr o u t i n gi na ni n t r a - a sd o m a i nw h i l e r o u t i n go s c i l l a t i o na n dm o a st h o u g ht h ec o l l a b o r a t i o n 讲t ho t h e ra s ，a n di ti sa l s oo f g r e a th e l pi nt h ec o n f i g u r a t i o np r o c e s s k e yw o r d s ：i n t e r - d o m a i nr o u t i n g ，c o l l a b o r a t i o n ，c o n f i g u r a t i o nc h e c k ，r o u t i n g m o n i t o r ，a u t o m a t i cc o n f i g u r a t i o ng e n e r a t i o n 第i i 页 国防科学技术大学研究生院硕+ 学位论文 表目录 表3 1 域内错误检查类型1 6 表6 1i s p p o l i c y 实现的功能4 7 第l l i 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 路由系统工作平面l 图2 1 路由的处理过程7 图2 2 商业关系示意图1 0 图2 3 商业关系设置问题1 0 图2 4a s 关系设置错误示例1 1 图2 5 “热土豆”路由示意图1 2 图2 6 “冷土豆 路由示意图1 2 图2 7 策略效果抵消示意图1 3 图2 8 域间路由震荡示意图1 5 图2 9 路由阻隔示例图1 7 图2 1 0 域内路由震荡示意图18 图2 1 1 转发环路示意图19 图2 1 2m e d 导致的路由选择不确定1 9 图2 1 3 拓扑导致的路由不确定2 0 图3 1 协同流程图3 0 图4 1 系统总体结构3 l 图4 2 联合路由监测方式3 2 图4 3 协作路由监测示意图3 3 图4 4b g p 配置文件的中间表示形式3 4 图4 5 拓扑视图协作3 5 图4 6 系统工作流程图3 8 图4 7 系统部署图3 9 图5 1 试验网络拓扑图4 0 图5 2 路由器配置文件管理界面4 1 图5 3 网络配置图形化管理界面4 2 图5 4 域内路由阻隔检查4 3 图5 5 服务器1 上的过滤规则冲突协同结果4 4 图5 6 服务器2 上的过滤规则冲突协同结果4 4 图5 7 震荡试验拓扑图4 4 图5 8 路由震荡监测结果4 5 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 亘珐囹邀回整由进圃耍垦曼遮查鲍叠塞生塞理 学位论文作者签名：兰金幽生日期： 删年，文月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 作者指导教师签名： 日期：粕年c 月r 7e 1 日期：扩年卜l 月1 3 日 国防科学技术大学研究生院硕士学位论文 第一章绪论弟一早珀下匕 i n t e m e t 作为当今世界最有影响力的科技成果，在现实生活中挥着举足轻重的作用。 i n t e m e t 运行b o r d e rg a t e w a yp r o t o c o l ( b g p ) 【1 ，2 】作为其域间路由协议，b g p 策略灵活性 使网络间复杂的政治商业得以体现，然而与此同时，b g p 协议本身的局限性和b g p 的配 置管理上的错误和不协调很大程度上影响着域问路由的安全和性能。目前，业界围绕b g p 配置管理展开了一系列理论和实践研究。 1 1 课题背景 路由系统是i n t e m e t 的基础设施和用户网络的关键支撑，i n t e m e t 路由协议包括b g p 域问路由协议和o p e ns h o r t e s tp a t hf i r s t ( o s p f ) 【3 】、i s i s 协谢4 】和r o u t i n gi n f o r m a t i o n p r o t o c o l ( r i p ) 5 】域内路由协议等。作为关键基础设施，b g p 占据着举足轻重的地位，它 允许各个自治系统的管理人员对于本自治系统内部的路由选择和路由信息的传播施加本 地路由策略，同时各个自治系统相互独立，无需向外暴露内部网络信息，在体现政治关系 上具有极大的灵活性。正是这种独立和自主性使得整个i n t e m e t 缺乏一个全局的协调管理 机制。 域问路由的安全和管理问题关乎整个i n t e r n e t 基础设施的稳定运行和健康发展，一直 以来受到网络运营商、设备制造商以及学术界的广泛关注。路由系统主要工作在管理平面、 控制平面、转发平面三个层次上，相关研究分别在这三个层次上展开，它们之间的关系如 图1 1 所示。 配置策略卜 冒埋干皿 。f 和g ，鐾。复 7 l “。”j j | | 一 控制平面 b g p 协议实体b g p 协议实体 上 土 转发平面 口口口报文报文口口口 图1 1 路由系统工作平面 管理平面工作在路由系统的最顶层，其配置策略对整个i n t e m e t 路由系统至关重要。 域问路由的网络流量大、影响范围广，因此保障网络的通畅、可靠也就显得极为重要，除 了要依靠网络设备本身和网络架构的可靠性之外，网络管理是一个关键环节。 管理平面的功能一般包括配置管理、性能管理、安全管理、故障告警管理等，从管理 第1 页 国防科学技术大学研究生院硕士学位论文 的分工上讲可以细分为网络管理系统和网元管理系统两大类，网元管理系统一般由原厂商 提供，各厂商采用专有的管理m i b 库，以实现对厂商设备本身的细致入微的管理，包括可 以显示出厂商设备图形化的面板等，例如c i s c o 公司的c i s c ow o r k s 、港湾网络公司的 h a m m e r v i e w 等；网络管理系统则主要用于掌握全网的状况，作为底层的网管平台来服务 于上层的网元管理系统，当前比较有名的有h po p e n v i e w 、i b mt i v o l i 等。 网络管理发展到今天，从功能上讲已经非常丰富，但在域问路由系统的网络管理中仍 然存在着很多的不足，例如：网络管理缺乏完善的信息作支撑，各i s p 之间的路由策略 都被作为隐私加以保护，造成各i s p 在配置管理时候进行博弈，被迫作出局部最优的决策， 导致整个网络全局范围内效率降低；配置以及管理复杂、使用不够灵活、智能化程度不 高等，尤其对于大型网络的管理，成百上千台的网络设备，网络管理变成了一项非常烦琐 的工作，甚至使得网络管理人员干脆弃之不用；当前网络管理中使用s n m p ，他依赖的 m i b 库中的信息类型相对域间路由需要来说太简单，具有十分明显的局限性。例如互操作 性差，网络开销大，难以适应大众化网络，功能受限，不对路由信息进行专门分析，更无 法进行综合分析。 因此，未来域问路由管理平面功能的发展方向应该是智能化、简单化和协同化。在目 前路由配置管理基础上应用配置生成技术、信息共享机制、自动配置检查技术，将使得路 由策略管理工作变得轻松而高效。 1 2 路由配置相关研究 1 2 1 域问路由配置问题研究 1 9 9 6 年，v a r a d h a n 【6 】首先观察到b g p 的路由振荡问题，引起广大科研人员的关注。路 由振荡不仅出现在域内也出现在域间，既有永久震荡也有瞬时震荡。这一类问题被总结为 s p p 问题【7 1 ，s p p 问题已经被证明为n p 完全问题【8 】，h a x e l l 定义了s p p 问题的简单版本【9 1 ， 并提出了这一类s p p 问题的解决方法。总的来说，路由震荡的应对方法仅限于震荡抑制， 然而这并不能根本上解决震荡。 转发环路指路由数据在转发时形成了环路，在这种情况下路由有效性被破坏，虽然拥 有路由但是实际上数据并不能到达目的地，而这种情况往往比路由震荡更难以发现。转发 环路通常在域内发生，g o b j u k a t l o 】针对域问路由中的转发环路提出一种无环路的配置方法， 能够防止因i b g p 路由反射配置引起的域内的转发环路。 “热土豆”路由是指，i s p 为了使报文传输在自己网络内的路径代价最小，选取最短 路径将报文传出，而这会导致报文在其他网络中的路径代价增大，从而导致整个网络的性 能降低。t e i x e i r a 研究了】“热土豆 路由对b g p 更新报文的影响，发生范围和时间特性， 认为b g p “热土豆 路由是导致b g p 更新报文的重要因素。“热土豆路由会导致转发 第2 页 国防科学技术大学研究生院硕士学位论文 平血的收敛时间增加【l2 | ，改变邻居自治域的流量、特大流量的路由信息更新和i n t e m e t 性 能测定的不准确性【1 3 】。在大规模的a s 中，热土豆路由被网络管理员用来进行流量均衡， 因为虽然基于a sp a t h 属性的i m p o r t 策略提供了足够的灵活性来实施流量工程目标【l 训，但 是它的效率有时候会非常低。 n i c kf e a m s t e r 提出“冷土豆”路由【1 5 】问题并提出一种从邻居节点策略中进行检测的方 法。所谓“冷土豆路由是指i s p 为了流量工程和安全等方面的目的，有选择性地向邻居 公布路由，导致邻居在有低代价路径的情况下被强迫采取高代价路径的情况。 前缀劫持【1 6 1 指被错误配置的或者是恶意的路由器发布其本来不拥有的路由前缀，这将 会导致严重的安全问题，其原因主要是除了s - b g p t l7 1 ，s o b g p 1 引，p s b g p t l 9 】等还没有有效 的手段能够预防和减缓i p 前缀劫持，而上述三种方案没能得到广泛应用主要由于以下两条 原因：它们都需要对b g p 协议进行重大修改，导致部属困难；局部的部署体现出来的优越 性有限，使得初始部署没有动力。 路由毒素指路由系统的非法路由信息的注入【2 0 j ，它是路由系统主要的安全威胁。 ( r o u t ep o i s o n i n g ) 攻击是指利用i n t e m e t 路由系统中的脆弱性，通过向目标路由系统注入特 定的毒素路由来达到扰乱、破坏、控制目标特定流量、关键设备、路由系统与核心网络的 目的。路由毒素的类型根据攻击目标分为3 类：对整个网络和路由系统的打击，对特定网 络和关键节点的打击，对特定流量的操纵；按照攻击意图分为路由系统扰乱、破坏和利用 等3 类；按照战术可分为7 种：网络分割，路由抑制，路由撤销，路由黑洞，流量吸附， 路由劫持，路由伪造；按照注入方式分为4 种：路由节点模式、网络中间人模式、远程控 制模式和路由渗透模式。 1 2 - 2 路由配置问题解决方案研究 g o v i n d a l l 【2 l 】等人提出以路由注册的方式进行全球合作，来避免路由策略冲突的产生， 而且很多工作被用来改进i r r 的效率【2 2 】。然而，这个方法在实施过程中面临着3 个实际 问题：a s 不愿意在如此大的范围内共享它们的路由策略，或者只提供不完整的路由策 略；由于商业竞争导致a s 的路由策略不断变化，而a s 可能不及时更新i r r 的数据， 导致i r r 中的路由策略很多是过时的：即使i r r 中的数据是完整的和最新的，g r i f f i n 和w i l f o n g 【7 j 已经证明要检查各种全局收敛的条件是一个n p 或者是一个n p 完全问题。 v i l l a m i z a t 2 3 j 等人提出一种路由振荡衰减( r o u t ef l a pd a m p e n i n g ) 机制，这种机制存在两个 缺点：路由振荡衰减机制并不能彻底消除由策略引起的振荡，它只是减缓了振荡；该 机制没有给管理人员足够的信息来鉴别路由振荡的根源。g r i f f i n 和w i l f o n g 2 4 】提出的s p v p 只能发现振荡的路由，但仍无法判别是由哪些路由策略产生冲突而引起的路由振荡。 g a o t 2 5 】提出描述a s 之间策略关系的a s 商业关系模型，它是a s 的路由策略的粗粒度 描述，在模型中有p r o v i d e r ，p e e r 和s i b l i n g 三种对象类型，以及他们之间的路由报文转发 第3 页 国防科学技术大学研究生院硕士学位论文 关系。商业关系模型关注于a s 级别以上的删络之间的关系，若视p r o v i d e r 在上c u s t o m e r 在下，则c u s t o m e r 不会在它的两个p r o v i d e r 之间转发数据，称之为“无谷底原则。w a n g f f 2 6 】根据商业模型研究了现实中a s 商业关系和他们的策略关系，发现p e e rt op e e r 之间的 关系经常被违背，a s 经常将其所有的前缀发给其p e e r 。 多个用于路由信息共享的项目被设立，用于解决i s p 在进行路由策略时相互间进行策 略博弈，构建信息共享渠道。主要包括i n t e m e tr o u t i n gr e g i s t r i e s ( i r r ) ，r o u t e v i e w ，l o o k i n g g l a s s 等。i r r 数据库，安全多方计算。i r r 是一个分布式的数据库，它提供了用于b g p 策略细节信息的巨大存储空间，但是它远未能达到其预想的效果，其原因有二：向i r r 进 行策略注册不是一种强制行为，而网络路由策略属于商业合同，一般不公开，公开的路由 策略，要么很快过时，要么与实现的策略不一致；静态分析工具具有指数级时间复杂性。 安全多方计算是指在一个互不信任的多用户网络中，各用户能够通过网络来协同完成可靠 的计算任务，又不暴露任何有关各自秘密输入的信息，由于其计算主要依靠密码学技术， 复杂度比较高，现阶段难以实用化，主要限于理论研究阶段。 自动配置检查技术发展迅速，能够改善以往主要依靠手工配置和“试验回滚”这样容 易繁杂而又容易产生错误的应用方式，它主要采用静态分析技术，对于配置策略进行形式 化的检查验证主要代表有r o u t i n gc o n f i g u r a t i o n c h e c k e r ( r c c ) 2 7 1 主要优点：对于域 内的配置能够比较好的检查，以优化经验为指导。缺点：对于域问路由难以采用集中式部 署方式，a s 之间通常不愿意公布内部策略细节，有的配置错误无法通过静态方式进行检 查。 配置自动生成技术目前主要依靠配置模板技术，同时采用图形化界面，减少网络管理 员在配置路由器时的输入信息量，提供主动的配置帮助提示，主要的工具有c i s c o 的 n e t w o r kc o n f i ga u d i tt o o l 和r o u t e ra u d i tt o o l ，i r r t o o l s 。 网络模拟软件的研究，当前广泛使用的网络仿真软件有n s 2 、s s f n e t ，o p n e t 等，其 中s s f n e t 可以用于b g p 仿真，其内部包含了b g p 的完整实现，可仿真b g p 的通告、撤 销、过滤等过程。在仿真过程中，s s f n e t 用域建模语言( d o m m nm o d e ll a n g u a g e ) 编写 的网络配置、生成网络、主机对象。在各个路由器、主机对象上运行的协议与实际的路由 器、主机等运行的相同。 1 2 3 域问路由配置管理难点 域间路由涉及到复杂的商业、政治利益关系，i n t e m e t 商业化使i s p 之间存在利益竞争， 进而使跨i s p 的路由行为控制很困难。同时，i s p 之间的路由策略的不透明性以及b g p 路 由实现的差异性都使得在域问路由安全问题处理上缺乏信息共享。 b g p 协议本身的局限性，b g p 协议设计之初并没有考虑到类似今天这么复杂的安全状 况，其对于安全性考虑很少，无法对其传递的路由信息提供保护，其本身无法检测永久路 第4 页 国防科学技术大学研究生院硕士学位论文 由震荡、路由黑洞、前缀劫持等问题。 b g p 路由行为的复杂性，其主要体现在路由策略的多样性和策略语义的不精确性。例 如，不一致的路由宣告，专用对等连接，多宿主网络，备份路径等策略都增加了域间路由 问题的隐蔽性和复杂性。 1 3 本文的工作 本文针对i n t e r n e t 网络中b g p 协议的配置问题进行了综合分析，总结了配置错误的类 型、危害，提出对域内和域间两类配置错误进行检查的方法，包括单个a s 的静态配置分 析、i r r 一致性检查，路由震荡、前缀劫持和m o a s 的协同监测，多个a s 间的协同配置， 针对协同中的策略隐私保护问题提出了一种i s p 之间的隐私隐藏的信息共享方法，研究了 配置文件的辅助生成技术。最后，在分析的基础上，我们构建了用于i s p 问协同配置的原 型系统。 。 第一章绪论。主要对当前b g p 安全增强机制的研究领域做了总体概述，介绍了国内 外在b g p 协议安全机制方面所做的工作。介绍了本文的相关研究工作。 第二章从策略管理角度出发，分析策略冲突问题的类型及检测方法，存在的困难和 应对方法。 第三章研究、设计、实现协同管理的框架，隐私隐藏的信息共享方法，协同管理的 协议，基于信誉机制的激励机制。 第四章具体分析协同的机制及方法的具体应用。 第五章对系统进行实验，分析效果和不足。 第六章总结和对未来工作的展望。总结了本文的工作，并对b g p 协议安全的研究工 作提出了相应的展望。 第5 页 国防科学技术大学研究生院硕士学位论文 第二章路由配置错误及策略冲突检查 路由配置错误是影响路由安全的重要因素，它可以导致商业关系违背、路由环路、路 由震荡、“热土豆 路由、不一致路由宣告等问题。本章对路由配置错误进行了系统化的 分析，深入研究了域间和域内两大类路由配置错误的各种表现形式、危害，并探讨了可能 的解决方法；针对单个a s 无法检测的配置错误提出协同检查的方法，针对静态无法检查 的震荡等问题提出协同监测的方法。 2 1 路由策略概述 b g p 路由器进行路由决策、转发路由信息都是根据本地路由策略配置执行，通过它期 望达到一个稳定的全局的连通性。同时，通过路由策略控制b g p 行为是一把双刃剑，它的 灵活性使网络管理员可以通过b g p 实现很大范围的目标，而错误的配置会导致重大的问 题。 路由策略问题是由网络上日益增长的路由器数目，越来越细节化的路由查询，网络的 协调性，和过多的负载引起的服务质量引起的，路由策略的定义为b g p 对等体之间关系的 公共描述，也就是包括，谁是对等体，路由是从那里产生的，要送到什么地方，路由的优 先权是什么，没有路由会怎么样以及什么样的路由可以聚合的问题。 路由策略主要分为如下四类：商业关系策略、流量工程策略、可伸缩性策略和安全性 策略【2 引。可伸缩性策略主要包括限制路由表大小和限制路由变化的频率，安全性策略包括 删除无效路由、保护路由策略的完整性、防止拒绝服务攻击等。这两类策略不存在冲突问 题，而涉及到冲突的主要是商业关系和流量工程策略。 总体来说b g p 具有如下特性：( b g p 路由是一种外部路由协议，与o s p f 、r i p 等的 内部路由协议不同，其着眼点不在于发现和计算路由，而在于控制路由的传播和选择最好 的路由。通过携带a s 路径信息，可以彻底解决路由循环问题。为控制路由的传播和 路由选择，它为路由附带属性信息。使用t c p 作为其传输层协议，提高了协议的可靠性。 支持无类域问路由，c i d r ( c l a s s l e s si n t e r - d o m a i nr o u t i n g ) 。路由更新时，b g p 只发 送增量路由，大大减少b g p 传播路由所占用的带宽，适用在i n t e m e t 上传播大量的路由信 息。出于政治、经济等目的，每个自治系统希望对路由进行过滤、选择和控制，因此， b g p 提供了丰富的路由策略，它使得b g p 便于扩展以支持i n t e m e t 新的发展。 对于一个具体的边界路由器来说，其路由的来源有两种，从对等体接收的路由和从i g p 引入的。对于接收的路由，根据其属性( 如a s 路径、团体属性) 进行过滤，并设置某些 属性( 如本地优先、m e d 值等) ，之后若需要的话，将具体的路由聚合为超网路由。b g p 可能从多个对等体收到目的地相同的路由，根据规则选择最好的路由并加入路由表。对于 第6 页 国防科学技术大学研究生院硕士学位论文 i g p 路由，则要经过引入策略的过滤和设置。b g p 发送优选的b g p 路由和i g p 路由给对 等体。路由器对路由的处理过程如图2 1 所示， 图2 1 路由的处理过程 主要路由属性：o r i g i n 属性，a s p a t h 属性，m u l t i e x i td i s c r i m i n a t o r ( m e d ) 属性，下 一跳属性，本地优先属性，团体属性。 路由决策过程描述如下： ( 1 、) 如果下一跳不可达，忽略此路由； ( 2 ) 选择本地优先级较大的路由，如果相同则选择本地路由器始发的路由； ( 3 ) 选择a s 路径较短的路由； ( 4 ) 依次选择起点类型为i g p 、e g p 、i n c o m p l e t e 类型的路由； ( 5 ) 同一个下一跳a s 的，选择m e d 值较低的路由： ( 6 ) i b g p 的路哟优先于e b g p 的路由； ( 7 ) 到出1 2 1 路由器最低的i g pm e t r i c 值路由； ( 8 ) 最低r o u t e r i d 的路由； 主要的路由策略控制手段有如下几条： ( 1 ) 路由的注入、重发布、聚合； ( 2 ) 通过i m p o r t 和e x p o i r tr o u t em a p 修改m e d 、l o c a lp r e f e r e n c e 等属性； ( 3 ) 访问控制列表、过滤表； ( 4 ) a sp a t h 的添加； ( 5 ) 团体属性； ( 6 ) 下一跳设置； ( 7 ) 路由抖动抑制； ( 8 ) 各种时间设置； 路由策略的正确性度量主要包括路由有效性、可见性、安全性、确定性和信息受控性， 详细描述如下： 第7 页 国防科学技术大学研究生院硕十学位论文 ( 1 ) 有效性：一条路由是有效的，当且仪当沿这条路由对应的路径发送的报文一定能 够到达目标。 ( 2 ) 可见性：如果存在一条在物理上从源到目的的路径，则一定拥有一条相应到达目 的的路由。 ( 3 ) 安全性：给定的路由集合和策略，对于一个目标地址，能够找到一个确定的路由， 使它不会随着其他网络参与者配置的改变而改变。 ( 4 ) 确定性：给定路由集合和策略，路由协议会最终收敛到同样的可以预知的路由集 合上。 ( 5 ) 信息受控性：路由信息能够充分体现应有的策略，同时不能泄露除了为了实现策 略必须的路由信息之外的隐私。 2 1 1i m p o r t 路由策略 i m p o r t 策略影响的是出口流量，网络管理员通过配置i m p o r t 策略影响从相同优等的边 界路由器中选择路由的过程，或者修改i g p 的路径代价，通常用到的策略是“e a r l y e x i t 路由，也即“热土豆 路由。i s p 将流量转发到最近的出口，以此来减少链路上的报文转 发，减少内部网络的拥塞。虽然这样会导致端到端的路径膨胀，i s p 还是经常使用这样的 策略来减少内部代价和拥塞，因为b g p 不支持通过多个i s p 来决定全局最短路径的选项。 另外一个常用的目的是减少到邻居的向外流量的拥塞，这可以通过在多条链路上实行 负载均衡来实现，出口流量可以通过改变本地优先属性来控制。实现精确的负载均衡很困 难，最大的挑战是要选取合适的前缀，并对其属性进行恰当的修改，如果选的过大则会导 致流量变化大以至于使链路过载，同时在路由配置里加入一长串前缀是很令人乏味的工 作，因此，一些i s p 适用正则表达式对a sp a t h 进行匹配来控制前缀，由于这是个手工工 作，很容易导致错误配置，不能实时的修正来适应变化的流量，而且变化的结果很难预测。 2 1 2e x p o r t 路由策略 一个i s p 的内部拥塞很可能由于其邻居而被加剧，这是因为隐私保护的原因，它的邻 居不知道它的流量工程目的、内部拓扑或者内部链路负载。同时这又是一个很有挑战性的 问题，这要求本地i s p 影响远程i s p 的路由决策，而相对的远程i s p 可能希望限制或者完 全忽略本地i s p 的目标。 在两个邻居间的多跳路径上流量切换通常采用修改m e d 值来实现。在多个邻居间切 换流量就更加具有挑战性，通常采用的做法是让a s 追加多个重复的a s 号到a sp a t h 里来 改变a sp a t h 的长度。 常用i s p 的e x p o r t 策略有： e x p o r t i n gt op r o v i d e r ：一个c u s t o m e r 向其p r o v i d e r 公布其他自己的路由，但是不公布 第8 页 国防科学技术大学研究生院硕士学位论文 其从其他p r o v i d e r 或者p e e r 学习到的路由。 e x p o r t i n gt oc u s t o m e r ：个p r o v i d e r 向其c u s t o m e r 公布其自己的路由和从其他 c u s t o m e r 、p r o v i d e r 和p e e r 学习到的路由。 e x p o r t i n gt op e e r ：一个p e e r 向其他p e e r 公布其自己和从c u s t o m e r 学习到的路由，但 是不公布其从p r o v i d e r 和其他p e e r 学习到的路由。 e x p o r t i n g t os i b l i n g ：一个s i b l i n g 向其他s i b l i n g 公布其自己学习到的所有路由。 c u s t o m e r 通常需要通过远程控制通知他的p r o v i d e r 根据他的利益来采取一些行动，最 常用的方法是设置c o m m u n i t y ，当然前提是对等体预先同意接收。c o m m u n i t y 的富于表达 力的天赋也有可能会导致错误配置，例如，两个相邻的i s p 有可能用相同的c o m m u n i t y 表 示不同的事情。i s p 通过仔细的路由器配置，并公布c o m m u n i t y 列表和其触发的操作。 2 1 3 安全性路由策略 一些错误配置会导致过多的路由更新，而过于频繁的更新会降低网络的q o s ，或者会 超出路由器的处理能力或者存储能力，从而导致停机和路由器出错，适当配置的b g p 策略 可以使网络对于上述问题具有弹性适应能力。 保护自己不受其他i s p 的影响的方法包括：过滤过长路由前缀( 如长于2 4 ) ，以此来 激励地址聚合；作为安全检查，路由器维持一个单个会话前缀宣告限制，限制一个邻居能 够宣告的总的路由总数；默认路由，小i s p 通常不需要完整的路由表，而是设置一个默认 路由使大多数目的地可达。 保护其他i s p 的方法通常是通过路由聚合，减少路由前缀公布。这通常需要对邻居的 连通性非常了解，而这并不能从b g p 协议发现，必须让网络管理员用人工发现和确定。 限制路由变化，路由不稳定会增加路由器c p u 负担，延长路由器对重要事件的反应时 间，同样，不同路径之间频繁的流量切换也会导致v o i c e o v e r - i p 等应用协议性能的抖动和 报文丢失，而且会影响到t c p 的应答时间的计算。此类方法中重要的机制是抖动抑制。 2 2 商业关系型策略冲突 a s 之间的商业关系由于商业和政治上的原因非常复杂，为了简单直观描述i s p 与其邻 居之间的关系，a s 商业关系模型被建立。它对a s 的路由策略进行了粗粒度的描述，一般 为各个i s p 之间协商决定。在模型中有p r o v i d e r ，p e e r 和s i b l i n g 三种对象类型，它们之间 的正确路由信息流如图2 2 所示。 商业关系是多方参与的综合结果，在小范围内，即使商业关系的双方有协议并在路由 策略上严格遵守，也有可能出现路由震荡等问题。要检查商业关系是否冲突，需要检查一 下三点：检查商业关系双方是否遵守约定；检查商业关系的配置方法是否正确，即其 配置是否在任何情况下都能使商业关系得到保证；在多方参与的关系中，检查整体关系 第9 页 国防科学技术大学研究生院硕士学位论文 是否协调一致。下面我们对这三个方面进行分析。 4 z u s t o m e r , c u s t o m e r c u s t o m e r c u s t o m e r 图2 2 商业关系不意图 检查商业关系的约定的遵守情况，需要双方公布其路由配置策略，这在当前隐私保护 政策下是不可能完成的。但是在隐私最低泄漏情况下，仅仅对双方的边界路由器商业关系 设置相关配置进行一致性检查也是可行的，这需要进行协同管理。 商业关系的设置，前缀过滤方法比较繁琐且不方便修改，需要检查是否采用采用 a s p a t h 过滤。利用前缀过滤方法设置错误的情况如图2 3 ，为避免在a s 3 和a s 2 之间转 发流量，a s 3 在a s l 的入口方向过滤了2 0 2 2 0 6 1 6 0 2 4 的前缀，这在当前网络状况下是有 效的。但是如果a s 3 和a s 4 的链路断开，a s 2 到1 7 2 1 8 1 9 0 2 4 地址的流量通过a s l 和