（计算机应用技术专业论文）大规模网络中域间路由连通不完全性的仿真研究.pdf

摘要 摘要 作为i n t e r n e t 网络存在的核心，路由技术必然是网络领域研究的重点。人们 对它的研究也一直没有中断过。针对骨干路由器面临的性能问题，人们提出了基 于硬件的网络交换方案。另外有相当多的研究工作集中在路由测量上面。通过较 大规模的测量，获得了大量的有代表性的数据，从中观察到很多路由现象，比如 延迟收敛、a sp a t h 膨胀等等。 我们注意到在设计和实现新的路由协议之前，确定一个完善的特性集合具有十 分重要的意义。可以说这个特性集的完善程度决定了新路由协议的生命力和实用 性。因此，我们从多个不同的角度重新审视了目前被大家所关注的一些路由协议 特性。本文认为，从路由机制的运行结果i p 路径来看，完善的特性集合应该 还要包含一个重要的元素：对称性和可传递性。这个特性对i n t e r n e t 上的将大量 出现的大规模分布计算系统具有十分重要的价值。 通过本文的实验研究表明，在i n t e r n e t 网络目前的路由机制下，所建立的i p 逻辑连接具有相当程度的连通不完全的病态特征。不对称和不可传递的现象在随 着a s 的网络规模的增加而显著增长。 在获得的所有1 2 组实验数据中，不对称性现象的发生率在2 左右；个别b g p 路由器上出现峰值，平均达到1 0 左右。在所有4 个不同的策略强度下，不对称性 都在随着a s 的网络规模的增加而显著增长。同时，不可传递现象的发生率在1 左右；在个别b g p 路由器上出现峰值，平均达到5 左右。在所有4 个不同的策略 强度下，不可传递现象同样在随着a s 的网络规模的增加而显著增长。 最后指出引入域的划分和独立管理的概念、把i s p 的利益简单的建立在对底层 网络的连通性的争夺上，这样的路由体系很难避免出现这种病态特征。 关键词域问路由连通不完全性b g p 路由策略 a b s t r a c t a b s t r a c t a st h ek e m e lo fi n t e m e t ，t e c h n o l o g yo fr o u t i n gi ss u r e l yt h ee m p h a s i so fs t u d i e si n n e t w o r kf i e l d s t h e r eh a v e b e e nl o t so fm a t e r i a le f f o r t sr e s e a r c h i n gi ni t t oi m p r o v et h e p e r f o r m a n c eo fr o u t e r so nb a c k b o n en e t w o r k s ，t h es c h e m eo fh i g h s p e e dn e t w o r k s w i t c h i n gb a s e do nh a r d w a r eh a sb e e nd e v e l o p e d t h e r ea r eo t h e rg r e a te f f o r t sf o c u s i n g o ne x t e n s i v eb g pr o u t i n gm e a s u r e m e n t ，f r o mw h i c hag r e a td e a lo fv a l u a b l ed a t ah a s b e e no b t a i n e d ，a n dm a n yi m p o r t a n tp h e n o m e n o n s ，s u c ha sd e l a y e dr o u t ec o n v e r g e n c e a n da sp a t hi n f l a t i o n ，a r eo b s e r v e d w ec o n c e mm a tw h a ti st h ec o m p l e t ea t t r i b u t es e to fr o u t i n gi n f r a s t r u c t u r ei s d e c i s i v eb e f o r ei m p l e m e n t i n gn e wr o u t i n gp r o t o c 0 1 h a v i n gs u r v e y e dt h ea t t r i b u t es e to f r o u t i n gp r o t o c o lc o n c e r n e da tp r e s e n t ，w ea d dan e wf a t a la t t r i b u t e ，s y m m e t r ya n d t r a n s f e r ，t ot h es e tm e n t i o n e da b o v e ，w h i c hw i l ls h o wg r e a ti m p a c to nt h ee m e r g e i n g l a r g e s c a l ed i s t r i b u t e dc o m p u t i n gb a s e do ni n t e m e t o u re x p e r i m e n td a t as h o w sc l e a r l yt h a t ，w i t ht h ep o l i c yr o u t i n gm e c h a n i s mo f p r e s e n ti n t e m e t ，t h em o n b i dc h a r a c t e ro fi pi n c o m p l e t ec o n n e c t i v i t yh a sr e a c h e dt oa q u i t ed e g r e e ，i no t h e rw o r d s ，i ti sm u c ha s y m m e t r i ca n dn o n t r a n s f e r a b l e f u r t h e r m o r e ， t h i si r r a t i o n a ls i t u a t i o nb e c o m e sw o r s er e m a r k a b l yw i t he n l a r g e ds c a l eo fi n t e m e t f r o m12g r o u p so fe x p e r i m e n t a ld a t a ，w ec a nf i n dt h a tt h ea v e r a g e p o s s i b i l i t yo f a s y m m e t r i ci pc o n n e c t i v i t yi sa b o u t2 a n dr e a c h i n gm a xo f10 a ts o m er o u t e r s w e a l s og e tac o n s i s t e n tr e s u l tt h a tt h ea v e r a g ep o s s i b i l i t yo fa s y m m e t r i ci pc o n n e c t i v i t y i n c r e a s e sn o t a b l yw i t hn e t w o r ks c a l eu n d e r4d i s t i n c tp o l i c yi n t e n s i t y m e a n w h i l e ，f r o m t h es a m ee x p e r i m e n t a ld a t a ，w ef i n dt h a tt h ea v e r a g ep o s s i b i l i t yo fan o n t r a n s f e r a b l ei p c o n n e c t i v i t yi s1 ， a n dr e a c h i n gm a xo f5 a ts o m er o u t e r s t h e a v e r a g e p o s s i b i l i t yo fn o n t r a n s f e r a b l ei pc o n n e c t i v i t yi n c r e a s e sw i t hn e t w o r ks c a l ec o n s i s t e n t l y u n d e r4d i f f r e n tp o l i c yi n t e n s i t y a tt h ee n do ft h i s d i s c u s s i o n ，w ep o i n t o u tt h a tt h e a s y m m e t r i c a n d n o n t r a n s f e r a b l ep r o p e r t yo fp r e s e n ti n t e r n e tr o u t i n gm e c h a n i s mi sh a r dt o g e tr i d o f ，d u et oi n t r o d u c i n gi d e a lo fa sa n di n d e p e n d e n tm a n a g e m e n t ，a sw e l la se s t a b l i s h i n g t h eb e n e f i to fl s ps i m p l yo nc o m p e t i t i v ei pc o n n e c t i v i t y k e y w o r d s ：i n t e r d o m a i nr o u t i n g ，i pc o n n e c t i v i t yi n c o m p l e t i o n ，b g p ，r o u t i n gp o l i c y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：生垒蒸叁 日期：驴，年，月? 牛日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 1 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：生亟兰耋 导师签名： 日期：j 年，月，毕目 第一章引言 第一章引言 随着信息时代的到来，人们对于通信方式、通信效率的要求也越来越高。计算 机网络已经渗透到了社会的各个方面，包括政府、商业、军事、教育和科研等领 域，逐渐成为企业和个人商业活动以及日常生活中的重要工具。特别是随着商业 化的发展，i n t e r n e t 进入了前所未有的高速发展阶段，无论是主机数量，还是数 据流量都呈现出爆炸性增长n 2 3 们3 。从而使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 s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 而言，必须对不同的用户需求和付费提供不同的服务保证。这就对整个网络体系 结构提出了挑战，特别是处于i n t e r n e t 核心地位的路由器。 因此，作为i n t e r n e t 网络存在的核心，路由技术始终是网络领域研究的热点 和重点。并且针对不同的路由问题，展开了不同方面的具体研究和开发工作。 针对骨干路由器面临的性能问题，提出了基于硬件的网络交换方案。在实际应 用中，从1 9 9 7 年以来，一些公司就开始推出采用硬件专用电路( a s i c ) 进行路由识 别、计算和转发的新型i n t e r n e t 骨干路由器。 另外，有相当多的研究工作集中在路由测量上面。通过较大规模的测量，获得 了大量的有代表性的数据乜m 6 7 1 。从中观察到很多路由现象，l t 女h i n t e r n e t 的拓扑 结构的变迁、b g p 路由表大小的变化过程、i p 地址空间的使用状况、路由协议的收 敛情况等等聃9 儿1 2 1 3 1 。对于纯路径矢量路由协议，由于采用单一的距离作为度 量，己经被证明此类协议是收敛的。而b g p 由于采用了基于策略的路由，因此上述 证明结论并不适用于b g p 。有研究表明对于b g p 而言，b g p 的路由策略有可能导致b g p 路由振荡甚至发散1 1 3 1 4 1n 5 1 1 6 3n 7 。 我们注意到在设计和实现新的路由协议之前，确定一个完善的特性集合具有十 分重要的意义。可以说这个特性集的完善程度决定了新路由协议的生命力和实用 电子科技大学硕士学位论文 性。因此，我们从多个不同的角度重新审视了以下目前被大家所关注的路由协议 特性1 8 m 1 。 ( 1 ) 优化根据一定的网络度量选最好路径； ( 2 ) 简单化和低开销协议功能的高效实现和低资源要求； ( 3 ) 健壮和稳定一一在意外事件中，能保持正常部分的正常工作。这对象 i n t e r n e t 这样的大规模系统来说很重要。 ( 4 ) 快收敛慢收敛可能带来环路路径和网络资源的不必要损耗； ( 5 ) 灵活性对网络的正常变化的快速适应能力。 除了上述特性外，本文认为，从路由机制的运行结果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 路径不对 称和不可传递的状况。主要包括以下几部分： ( 1 ) 广泛、深入的阅读相关协议文本，包括i p v 4 、i p v 6 中与路由相关的若干 协议。 ( 2 ) 密切掌握最近的路由研究动态，特别是i n t e r n e t 域问路由。 ( 3 ) 深入研究n s 2 的协议仿真原理和协议扩展方法。 ( 4 ) 实现b g p 4 在n s 2 中的扩展。 ( 5 ) 设计n s 2 下基于b g p 4 的域间策略路由实验方案，并分析实验数据。 在这几部分工作中，b g p 4 在n s 2 中的扩展和域间策略路由实验设计与分析是本 文的工作重点。 2 第二章域问路由结构 第二章域问路由结构 路由是在i n t e r n e t 中把信息从一个地方送到另一个地方，并且中间至少有一个 转发节点的行为。它由选路和报文交换两部分组成。报文交换是比较简单和直接 的事情，而选路则要复杂得多。选路算法主要负责根据一定的网络度量从到达相 同目的地的多个路径中选出最优路径。根据路由涉及的范围的不同，选路可以分 成域内路由和域问路由两类。在大规模网络中域问路由扮演着确定全局路径的重 要角色。 在大规模网络i n t e r n e t 上，所有的i p 业务的共同基础就是互联网的i p 连通性 ( c o n n e c t i v i t y ) 。这也是互联网服务提供商( i s p ) 所提供的最基本的i p 业务。 这种工p 连通性是通过互联网服务提供商( i s p ) 之间交换路由信息来建立的。而实现 这些路由信息的交换需要一定的基础结构和通信规则。 2 1 自治系统 互联网是由许许多多个独立的管理区或自治系统( a s ) 构成的。自治系统的定义 是“在单一技术管理下、采用同一种内部网关协议和统一度量在a s 内转发数据包、 并采用一种外部网关协议将数据包转发到其他a s 的一组路由器”。每个自治系统 有一个由相关机构分配的识别码，称为自治系统号。 互联网号码分配管理局( i a n a ) 是负责分配自治系统号的最顶层管理机构。自治 系统号是一个1 6 比特的数，其范围从1 到6 5 5 3 5 。r f c1 9 3 0 给出了a s 号的使用指南， 从6 4 5 1 2 至i 6 5 5 3 5 的a s 编号范围是留作私用的。 一个自治系统内运载的大部分流量都是起源或终止于本自治系统的，也就是源 i p 地址或目的i p 地址是本自治系统的一部分，这类流量叫做本地流量。起源和终 点都不在本自治系统的流量叫做中转流量。根据处理中转流量的方式可将自治系 统分为以下三种类型： 单出口a s ：只能通过一个出口到达自治系统以外的网络，单出口a s 只能运载本 地流量。 多宿主a s ：有多个出口到达自治系统以外的网络，但不运载中转流量。多宿主 a s 只通告自己的路由，不转发从其他a s 学到的路由。这就保证了到第三方a s 的流 量不会送到本地a s 来。 中转a s ：有多个出口到达自治系统以外的网络，并且可以运载本地流量和中转 流量。 电子科技大学硕士学位论文 2 2 分层结构 最初的i n t e r n e t 是平面的全互连结构，随着i n t e r n e t 的普及应用和商业化运 营，其结构发生了重要的变化。 从i s c 的测量可以看到畸1 ，在1 9 8 8 年到1 9 9 4 年期间，i n t e r n e t 中b g p 路由表的大 小呈现出指数级的增长态势，明显超过了软件和硬件能力的增长速度。对这个严 峻的问题所作出的反应就是理论上引入层次结构，并允许i s p 提供商合并其用户的 地址块，使原本需要大量的路由表项的地址空间只用一个表项就够了。在实际的 应用方面采用了不区分地址类别的路由协议，其中所用到的目的网络都用可变长 度的网络前缀表示。 1 9 9 4 1 9 9 8 年，b g p 路由表大小开始线性的增长，同时，在小时级的采样中看到 b g p 路由表大小的稳定性无论是从路由信息变化所占的比例来看还是从路由信息 量的绝对值来看，都有很大提高。通常认为这是因为网络的局部不稳定性能被本 地吸收，很少向外扩散。 大量研究表明2 m 5 20 | ，i n t e r n e t 在拓扑结构上体现出明显的基于a s 的层次 性，但也不是完全的层次结构( 如图2 1 ) 。在末端的接入网上的路由器将家庭用 户和小型企业网连接到i s p ，而中间层的i s p 连接若干下层i s p ，从而统辖众多用户 网络。在主干网上的路由器不直接连接端系统，它们用长距离主干网络连接中间 i s p 。 在不同的层次结构上的路由器功能略有差异。对于接入网的路由器它面临的主 要问题是连接使用不同的网络技术的计算机进入i n t e r n e t ，需要提供高速的端口， 丰富的协议支持；而中间i s p 必须易于配置，提供高密度的端口，支持q o s ；主干 网上的路由器则需要尽可能的完成高速路由功能。 图2 1 实际的i n t e r n e t 域间路由拓扑结构 4 第二章域问路由结构 出于各种商业目的或者应用需要，有些平行的p r o v i d e r 之间和用户域之间建立 了直接的连接，这样一来很多流量就不需要由顶层骨干域中转( 如图2 1 中虚线所 示) 。通常为了满足可靠性要求，一个域可以有多个出口与i n t e r n e t 连接( 女h a s 5 和a s 6 ) 。2 0 0 0 年左右的测量数据表明n4 j ，这种情况客观存在。表现在b g p 路由表再 次出现接近指数级的增长速度，以及一个路由表项所包含的平均地址数量呈下降 趋势。相应的平均网络前缀的长度在1 8 左右，也略有增加。这个现象说明理论上 高效的层次结构方法在实际的网络中运用得并不彻底。 2 3 内部网关协议和外部网关协议 基于分层的思想，i n t e r n e t 中i p 报文的路由选择分为两种类型：域内路由 ( i n t r a d o m a i n ) 和域间路由( i n t e r d o m a i n ) 。域内路由以某些度量值( 如时延、 带宽等) 为尺度，选择到达本地自治系统内每个目的地的最佳路径；域问路由，则 采用基于所穿越的自治系统序列的选路策略，选择到达自治系统外每个目的地的 最佳路径。 相应的，互联网的路由选择协议也分为两种类型：内部网关协议( i g p ) 和外部网 关协议( e g p ) 。内部网关协议在自治系统内部交换路由信息的路由选择协议。比 如：路由信息协议( r i p ) 、开放最短路径优先协议( o s p f ) 。外部网关协议是在自治 系统之间进行互连所使用的路由选择协议。边界网关协议( b g p ) 就是e g p 的一个例 子。 电子科技大学硕士学位论文 第三章域问路由算法和路由策略 3 1 域问路由选择算法 3 1 1 路由选择算法 路由协议可以视为由两个方面构成，一个是路由信息的传输，另一个是路由选 择算法。判定到达目的地的最佳路径就是通过路由选择算法来实现的。为此，路 由选择算法必须建立并维护包含路由信息的路由表，其中路由信息随所用的路由 选择算法而不尽相同。 路由器间互通信息进行路由更新，使路由表能正确反映网络的拓扑变化。并由 路由选择算法根据度量来决定最佳路径，将目的网络与下一跳( n e x t h o p ) 的关系 告诉路由器的转发表。例如路由信息协议( r i p ) 、开放式最短路径优先协议( o s p f ) 和边界网关协议( b g p ) 等都是以类似的框架工作的。根据实现思路的不同路由选 择算法可进一步分为链路状态算法和距离矢量算法。 其中距离矢量算法采用的是一种分布式计算的方法，即每个路由器到达目标网 络的“最佳”路径是由各路由器独立计算出来的。随后，这些路由器将其所知的 最佳路径通知给它们的邻接路由器。邻接路由器可能从获得的信息中发现通往目 标网络的新的最佳路径。此时该路由器会更新自己的路由表，同时将自己的这一 新的选择再次通知给相邻的路由器这种交互工作会一直进行下去，直到路由域中 的路由达到稳定为止。 3 1 2 域问路由选择算法 b g p 是为t c p i p 互联网设计的外部网关协议，用于多个自治域之间。它采用的 选路算法既不是基于纯粹的链路状态算法，也不是基于纯粹的距离向量算法。它 的主要功能是与其它自治域的b g p 路由器交换网络可达信息，同时屏蔽自治域内的 路由细节。通常各个自治域运行不同的内部网关协议。b g p 更新信息包括网络前缀、 a s 路径信息等。a s 路径信息包括到达某个特定网络须经过的a s 序列。这些更新信 息通过下层的t c p 连接进行传送，以保证传输的可靠性，也简化b g p 协议本身。 6 第三章域问路由算法和路由策略 3 2 域问路由策略 3 2 1 路由策略 为了灵活的控制和管理数据流量的分布，引入路由策略机制。根据策略实施方 式的不同，路由策略模型可以分为3 类： ( 1 ) 基于策略的路由信息的发布； ( 2 ) 基于策略的数据报文过滤和转发； ( 3 ) 基于策略的网络资源分配。 不同模型是为了满足不同的需求。有时不同模型所满足的需求可能重叠，但通 常这些策略作用在不同的粒度上。基于策略的路由信息的发布一般用于网络级或 自治域级；基于策略的数据报文过滤和转发则用于端系统或者用户级；基于策略 的网络资源分配可用于各种层次。实际上它们可以混合使用。尤其是第一个模型 和第三个模型，它们彼此是正交的。 基于策略的路由信息的发布是本文讨论的主要范畴，它控制哪个使用或不能使 用网络资源，属于较宏观的策略机制。具有便于实施大规模的网络工程、能增强 网络的可伸缩性以及对报文交换的性能影响较小等优点。当然，它不能处理数据 报文的过滤，比如无法应对源路由报文的恶意攻击。 如果i n t e r n e t 的某部分需要实施某些策略，基本的要求就是不能给整个网络带 来较大的性能下降。也应做到在a s 内实施的局部策略不影响全局的网络流量。对 资源相对丰富和利用不够充分的部分需要考虑路由优化，同时所有的优化措施都 应考虑减小对网络和路由的稳定性的影响。 基于策略的路由能提供稳定的和可预测的结果，这一点可以进一步保证网络提 供持续一致的和可以接受的服务。 3 2 2 域间路由策略 在i n t e r n e t 的层次结构中，一个a s 可以有权决定该域内的哪些资源( 通常是内 部子网) 可以被外部访问、允许访问哪些外部的资源( 外部a s 及其子网) 以及愿 意在哪些外部a s 之间提供流量中继。具体地说，有的a s ( 如图2 1 中a s 2 、a s 3 ) 称 为p r o v i d e r ，主要为其它a s 提供i n t e r n e t 接入服务，有的a s ( 如图2 1 中a s 4 、a s 5 、 a s 6 ) 只是在内部子网与i n t e r n e t 之间提供连通性，称为e n d c u s t o m e r 。无论是 电子科技大学硕士学位论文 p r o v i d e r 还是e n d c u s t o m e r ，都可能需要通过在边界路由器实施特定的路由策略 来实现各种流量分布管理。当然，p r o v i d e r 和e n d c u s t o m e r 实施策略的目的通常 是不一样的。p r o v i d e r 可能主要考虑尽可能提高中继资源的有效利用，更多的 c u s t o m e r 接入。e n d c u s t o m e r 则可能侧重于内部资源特别是信息资源的访问控制， 防止外出流量带来的经济，法律和社会问题等。 3 2 3b g p 路由策略 在域问路由中实施策略需要相应协议的支持。边界网关协议 b g p ( b o r d e r g a t e w a y p r o t o c 0 1 ) 是现今唯一应用在i n t e r n e t 上的域间路由协议。它 采用了基于策略的路由选择，即在进行路由选择时，允许使用路由的各种属性作 为路由选择条件，同时可以利用b g p 路由策略来影n 向b c , p 路由属性。并且基于路由 属性的度量可以优先于基于路径距离的度量，从而打破了最短路径的路由选择条 件。有测量数据表明，在i n t e r n e t 中存在实际a s 路径长度超过理想的最短路径长 度的现象。b g p 的基于策略的路由，为自治系统提供了十分灵活而又有效的管理手 段。 b g p 路由器实施路由策略通常有两个方面：p r e f i x 过滤与最优路径选择；选择 性的路由信息转发。一方面，a s 通过实施一些过滤策略可以选择允许访问的 p r e f i x 。到达某p r e f i x 可能存在若干路径，a s 可以根据策略配置，决定哪条路径 为最优路径。这一过程实施的策略称为i m p o r tp o l i c y ，它决定了从该a s 出发的i p 包能到达哪些网络。另一方面，如果a s 愿意为其它a s 之间提供流量中继，可以依 据策略配置，确定是否转发某p r e f i x 的可达信息。这一过程实施的策略称为e x p o r t p o l i c y ，决定了来自外部的i p 包可以通过该a s 到达哪些网络( 如图3 - 1 ) 。 图3 1b g p 协议的策略路由模型 3 2 4in t e r n e t 路由机制的良好特性集 第三章域问路由算法和路由策略 路由机制在i n t e r n e t 的发展过程中始终在不断完善。1 9 9 1 年i a b 注意到 i n t e r n e t 的两个主要的扩展问题：地址空间即将耗尽；域问路由表无限制的增长。 i e t fr o a d 建议淡化前3 类地址隐含的网络主机边界，转而采纳显式的边界设置， 并允许多个地址块合并为一个地址块。为了给目前的网络问题找到长期的解决方 法，i e t f 在1 9 9 4 年成立了i n t e r n e tp r o t o c o ln e x tg e n e r a t i o n ( i p n g ) ，并根据 s i m p l ei n t e r n e tp r o t o c o l 的原则选择下一代协议。其根本特征是对老版本协议 的逐渐的完善，而不是突变。所有这些变化都对路由机制提出了一个又一个挑战， 要求对它进行相应的改善。 在设计和实现新的路由协议之前，确定一个完善的特性集合具有十分重要的意 义。可以说这个特性集的完善程度决定了新路由协议的生命力和实用性。当然， 特性集的丰富和完善有一个过程，目前主要考虑的特性集包括以下五个元素n 引： ( 1 ) 优化根据一定的网络度量选最好路径； ( 2 ) 简单化和低开销协议功能的高效实现和低资源要求； ( 3 ) 健壮和稳定一一在意外事件中，能保持正常部分的正常工作。这对象 i n t e r n e t 这样的大规模系统来说很重要。 ( 4 ) 快收敛慢收敛可能带来环路路径和网络资源的不必要损耗； ( 5 ) 灵活性对网络的正常变化的快速适应能力。 路由机制的根本任务就是为用户提供基本的i p 连通性。在提供这种连通性时， 除了上述特性外，本文认为，从路由机制的运行结果工p 路径看，完善的特性 集合应该还要包含一个重要的元素：对称性和可传递性。在后面的分析中可以看 到，这个特性对i n t e r n e t 上的将大量出现的大规模分布计算系统具有十分重要的 价值。本文的主要工作就是通过仿真的方法调查了解i n t e r n e t 上i p 路径不对称和 不可传递的状况。 在此特别要指出的是，这种连通不完全性主要是由于实施域问路由策略所造成 的。所以本文的讨论集中在域间策略路由上。 电子科技大学硕士学位论文 第四章域问路由的连通不完全性 4 1 基本的数学概念 域问路由问题可以用图来表示。设无向图g = ( v ，e ) ，其中v 是a s 节点集( 不 失一般性把一个a s 抽象为节点) ，e 为a s 之间的连接边集。v = ( 0 ，1 ，2 ，n ) ，对任意的u v ，n e i g h b o r s ( u ) = ( wj ( u ，w ) e ) 。节点0 称为起始节点， 所有其它节点都将试图建立到它的路径。路径p 要么为e ，要么是一个节点序列 ( v 。，v ，v 。) ，k 0 。p 具有方向性，表明从左节点v 。出发可以到达右节点v 。 若p 1 = ( v k ，v ，v i ) ，p 2 = ( v i ，v i _ 1 ，v o ) ，则p i p 2 = ( v k ，v k - 1 ，v i ，v i - l ， v 。) 表示两条路径的连接。ep = p = p 。对左节点为v 的路径p ，若边( u ，v ) e ，则( u ，v ) p 表示一条从u 出发，经过v ，沿p 前进的路径。 对任意节点v v 一( 0 ) ，p ( v ) 表示所有从v 出发到达起始节点0 的路径集。 对p p ( v ) ，p 一( v ，v i ，一，o ) ，称v i 为p 的n e x th o p 。设p a t h = p ( v ) lv v 一( 0 ) ) 。对节点v v 一( 0 ) ，在p ( v ) 上定义返回非负整数值的排队函数入， 满足： 入，( ) = 0 ： 如果入，( p 。) = 入，( p 2 ) 则要么p 。= p 。，要么存在u n e i g h b o r s ( v ) ，p 。= ( v ， u ) p 。，p 2 = ( v ，u ) p 。即对来自同一邻居的不同路径不予区别优先级。 设中= 入，iv v 一( 0 ) ) 。 对节点v 定义策略函数q ，b ，y ，。其中q ，对允许到达的节点0 或其中的 p r e f i x 返回t r u e ，否则返回f a l s e ，用于控制是否允许到达起始节点o 或其中的某 p r e f i x 。b ，返回路径p ，p p p p ( v ) 并且m a x ( 入，( p ) ) ) 。q ，与b ， 结合实现i m p o r tp o l i c y 。y ，对提供流量中转的路径返回t r u e ，否则返回f a l s e ， 实现e x p o r tp o l i c y 。定义q = q ，lv v 一( 0 ) ) ，y = y ，iv v ) 。 对起始节点0 中的任意p r e f i x ，定义从v v 一( 0 ) 出发的有效路径嘲。它 是域间策略路由算法的结果。有效路径，邝的计算满足以下规则： ，0 p ( v ) ； p = ( 0 ) 是有效的； 对p p ( v ) 一 ) ，p = ，0 当且仅当：p = ( v ，u ) p ，p = 。0 y 。 ( p ) 返回t r u e ；q ，( p ) 返回t r u e ；p = b ，。就是说，设存在一条从u 出发的有 1 0 第四章域问路由的连通不完全性 效路径p ，如果u 允许它延伸到v ( 即：y 。( p ) 返回t r u e ) ，v 节点允许访问起 始节点0 中的该p r e f i x ( 即：q 。( ( v ，u ) p ) 返回t r u e ) ，同时经由u 是到达0 的最短路径( 即：( v ，u ) p = b ，) ，那么p = ( v ，u ) p 就延伸了p ，是从v 到达0 的有效路径。 4 2 不对称性 设起始节点m 及其中的p r e f i xa ，另一节点n 及其中的p r e f i xb ，存在从1 3 出发的有效路径。向到达p r e f i xa ，如果还存在以n 为起始节点，从m 出发的有 效路径。到达p r e f i xb ，则称网络p r e f i xa 和p r e f i xb 之间的域间策略路由 是对称的。否则称为不对称。以图4 1 为例。对节点v 1 和2 0 2 1 1 2 5 2 0 ，存 在从v 6 出发的有效路径p 。( v 。，v 。，v 。，v 。) ，同时对v 6 和1 0 1 6 2 2 0 2 2 ，存在 从v l 出发的有效路径p ：( v 。，v ：，v 。，v 。) ，这样2 0 2 1 1 2 5 2 0 和1 0 1 6 2 2 0 2 2 之间的路由就是对称的。 对称性意味着通信可以双向进行，否则是单向的。对分布式应用系统，各个 独立组件之间的通信通常都是双向的。但是在i n t e r n e t 域间策略路由中，对称性 是没有保证的。以图4 一l 为例。p ：从v 6 延伸到v 3 需要经过y 们a 。和入，。的决策。 再从v 3 延伸到v 2 ，需要经过yma ，：和入，。的决策。最后从v 2 延伸到v l 需要经 过y 伽q ，。和入，。的决策。整个延伸过程涉及到四个域，每个域有自己的决策函数 q ，和y ，。事实上，在q 和y 中各个决策函数之间是完全独立的，的元素和y 的 元素之间也未必是一致的。所以p 。的延伸不依赖于p 。 2 0 2 1 1 图4 - 1 域间策略路由的不对称和不可传递性 1 6 2 2 0 1 2 2 电子科技大学硕士学位论文 4 3 不可传递性 设节点m 及其中的p r e f i xa ，中间节点r l 及其p r e f i xb ，另一节点g ，如果 存在从n 出发的有效路径。m 到达p r e f i xa ，以及从g 出发的有效路径g 。到达 p r e f i xb ，则必存在从g 出发的有效路径ag m 到达p r e f i xa ，那么称节点m 是传 递可达的。其中没有a 。m = a 。向a 。的限制。以图4 1 为例。设：对节点v 1 和 2 0 2 1 1 2 5 2 0 ，存在从v 4 出发的有效路径p 。( v 。，v 。) ；对节点v 4 和 1 0 2 1 4 2 2 5 2 0 ，存在从v 6 出发的有效路径p 。( v 。，v 。，v 。) 。因为存在从v 6 出 发到v 1 和2 0 2 1 1 2 5 2 0 的有效路径p 。( v 。，v 。，v 。，v ，) ，所以节点v l 是传递可 达的。 节点m 是传递可达的意味着分布式应用系统可以在中间节点n 上，把来自远 程节点g 的交互请求转移到m 上。以有效的支持动态的分布集成计算。在i n t e r n e t 域间策略路由中，可传递性也是没有保证的。以图4 1 为例。在q 和y 中各个决 策函数之间的独立性，以及q 的元素和y 的元素之间也未必一致，使得p 。并不依 赖于p 。和p 。而存在。 1 2 第五章边界网关协议b g p 的基本原理 第五章边界网关协议b g p 的基本原理 5 1 边界网关协议b g p 的概念 b g p n 8 1 9 1 是在最早的外部网关协议e g p 的应用基础上发展起来的，从1 9 8 9 年的最 早版本b g p 一工，发展到1 9 9 3 年开始开发的最新版本b g p 4 。b g p 4 是目前i n t e r n e t 上应 用最广泛的域问路由协议。b g p 4 能够支持无类别域问路由( c i d r ) ，因为它发布的 路由信息包括i p 前缀及其长度。b g p 4 还支持路由聚合。b g p 没有对互联网的拓扑结 构施加任何限制，并且假定自治系统内部的路由选择己经通过内部网关协议i g p 完 成了。 它的主要作用是允许相邻自治系统的b g p 发言者之间互相交换网络层可达性信 息。被交换的网络层可达性信息包括能够到达的网络前缀和这些信息所经过的自 治系统序列。接收者可以根据这个自治系统序列，也就是a sp a t h 来勾画出自治系 统的连通图。用这种方法可以避免路由环路，并且能够在自治系统层次上实施一 些路由策略。 由于b g p 使用了a sp a t h 的概念，所以常被称为是一种路径向量( p a t hv e c t o r ) 协议，也叫做增强型距离向量协议。 5 2b g p 协议的特点 由于b g p 主要负责本自治系统和外部自治系统间的路由可达信息的交换，因此， 它所关心的拓扑结构是a s 级别的拓扑结构，b g p 通过u p d a t e 消息中路由的a sp a t h 属性来构造a s 的拓扑结构图，进一步通过此结构图来选择路由。 与o s p f ，r i p 等i g p 协议相比，b g p 的拓扑图更宏观一些。i g p 协议获得的是一个 a s 内部的路由器的拓扑结构。i g p 把路由器抽象成节点，把路由器之间的链路抽象 成边，根据链路的状态等参数和其它的度量标准，每条边配以一定的权值，生成 拓扑图。根据此拓扑图选择代价( 两点间经过的边的权值和) 最小的路由。这里有 一个假设，即路由器转发数据包是没有代价的。而在b g p 中，拓扑图的节点是一个 a s ，边是a s 之间的链路。此时，数据包经过一个端点( a s ) 时的代价就不能假设为0 ， 这个代价需要由i g p 来负责计算。这体现了e g p 矛ii g p 是分层的关系。即i g p 负责在 a s 内部选择花费最小的路由，e g p 负责选择a s i n 花费最小的路由。 为了加快路由更新的速度、缩短全网络路由的收敛时间，b g p 采用发送增量路 电子科技大学硕士学位论文 由的方法，完成全部路由信息的通告和维护。这样保证了b g p 对等体之间的最小通 信量。但同时增加了b g p 的复杂程度，因为对于b g p 必须为每个b g p 对等体保存已经 发送的路由信息，以便发送一条新路由前确认其是否真的应该发送。 为了进一步减小路由表的体积和发送路由的通信量，b g p 还支持无类别域间路 由c i d r 。它使用带掩码的路由来表达更丰富的路由信息。如从2 0 2 1 1 2 1 0 2 4 至 j 2 0 2 1 1 2 2 5 4 0 2 4 的所有网络可以使用2 0 2 1 1 2 0 0 1 6 表示，从而减小了路由表 的体积和发送路由信息时的网络流量。 同时，作为a s 自治区域间的路由协议，由于政治的、经济的等原因，b g p 需要 按照路由的属性来控制路由的发送和接受。因此，b g p 有丰富的路由策略控制手段。 5 3b 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 会 话( 如图5 1 ) 。 b g p 发言者本身并不要求一定是边界路由器，也就是说边界路由器可以