（计算机应用技术专业论文）基于路由实验床的bgp路由稳定性研究.pdf

东北走学硕士学位论文 摘要 基于路由实验床的b g p 路由稳定性研究 摘要 i n t e r n e t 从2 0 世纪6 0 年代术的小规模学术实验网络，发展成为今天全球互连的 网络，其规模不断扩大，与此同时出现了i n t e r n e t 的i 叮靠性、稳定性和健壮性等问题 这些问题目前已经成为i n t e r n e t 路d i 研究的焦点问题。 i n t e r n e t 被分割成自治系统以便于管理。自治系统内部路由器之间运行r i p 、0 s p f 等内部网关协议来交换路由信息，i 瓜自治系统之问则通过外部网关协议交换路由信息以 实现互连。目前b g p 协议是事实上的标准域问路由防议，b g p 路由的稳定性直接影响到 端到端网络的性能。b g p 路由的不稳定会导致网络丢包率和数据传输延迟增加、网络收 敛延迟，甚至大范围的网络连接中断。 构建一个低成本、易扩展、易用并且灵活性好的路由实验床平台是进行路由稳定性 研究的前提，本文描述了路由实验床的构建过程。路由实验床提供了进行实验研究的软 硬件平台和仿真工具，在实验床上对因b g p 路由配置错误而导致的路由不稳定进行了深 入的研究，分析了导致路由振荡的本质原因，并针对这些问题提出了相应的解决方案。 i b g p 和e b g p 因为配置不当会引起阵发性和持久性的路出振荡，这些故障直接导 致了大范围的路由不稳定。通过在实验床对故障进行再现、收集路出更新报文进行分析， 找到了引起路由振荡的原因：即特定的更新报文收发次序可以引起相应的路由产生阵发 性振荡。针对故障的成因，提出了解决故障的方案，并通过仿真验证了方案的有效性。 b g p 扩展技术较好的解决了b g p 系统的扩展性问题，但是配罱不当也会引起路由 振荡，本文对联盟和路由反射两种扩展技术的典型配置错误引起的路由振荡实例进行了 深入的分析，提出了避免此类故障的方法。 关键词域问路由协议：边界网关协议：路由稳定性：实验床：路由振荡 东北大学硕士学位论文 a b s t r a c t s t u d yo nb g pr o u t i n gs t a b i l i t y b a s e do n r o u t i n gs t a b i l i t yt e s t b e d a b s t r a c t i n t e r n e th a su n d e r g o n es i g n i f i c a n tc h a n g e sf r o mi t si n c e p t i o ni nt h el a t e1 9 6 0 s s t a r t i n g f r o ma na c a d e m i ce x p e r i m e n tn e t w o r kw 畦hl i t t l es c a l e i th a sg r o w nt oag l o b a l i n t e r c o n n e c t e dn e t w o r k d u r i n gt h ee x p a n s i o no fs c a l e ，t h ei n t e r n e tr o u t i n gh a se n c o u n t e r e d t h ep r o b l e m so fr e l i a b i l i t y , s t a b i l i t ya n dr o b u s to fi n t e r a c t t h e s ep r o b l e m sh a v eb e c o m et h e f o c u s e st h a ta c a d e m i aa n di n d u s t r ya r ew i d e l yc o n c e r n e da b o u t i no r d e rt ob ec o n v e n i e n tf o rm a n a g e m e n t ，i n t e r a c th a sb e e nd i v i d e di n t oag r e a tn u m b e r o fa u t o n o m o u ss y s t e m s ( a s e s ) w i t h i na l la s ，r o u t e r sr u ni n t e r i o rg a t e w a yp r o t o c o l s ( i g p s ) s u c ha so p e ns h o r t e s tp a t hf i r s t ( o s p f ) r o u t i n gp r o t o c o la n dr o u t i n gi n f o r m a t i o np r o t o c o l ( r i p ) t oe x c h a n g et h er o u t i n gi n f o r m a t i o n a n da s e se x c h a n g er o u t i n gi n f o r m a t i o nb e t w e e n e a c ho t h e rt oe n a b l ec o n n e c t i v i t yt h r o u 曲e x t e r i o rg a t e w a yp r o t o c o l ( e g p ) b o r d e rg a t e w a y p r o t o c o l ( b g p ) i st h ed ef a c t os t a n d a r di n t e r - d o m a i nr o u t i n gp r o t o c o l ，t h es t a b i l i t yo fb g p d i r e c t l ya f f e c tt h ee n d t o e n dn e t w o r kp e r f o r m a n c e t h ei n s t a b i l i t yo fb g pr o u t i n gc a nc a u s e t h ei n c r e a s eo fp a c k e tl o s sr a t i oa n dd e l i v e r yl a t e n c y , a n dd e l a yn e t w o r kc o n v e r g e n c et i m e ， a n de v e nd i s r u p tt h en e t w o r kc o n n e c t i v i t ya tal a r g es c o p e a r o u t i n gt e s t b e dw i t hl o wc o s t ，s c a l a b i l i t y , u s a b i l i t ya n da g i l i t yi sn e c e s s a r yt ot h es t u d y o nr o u t i n gs t a b i l i t y t h i sp a p e rd e s c r i b e dt h ec o n s t r u c t i o no ft h er o u t i n gt e s t b e d t h et e s t b e d s u p p l i e st h eh a r d w a r ea n ds o f t w a r ep l a t f o r ma n ds i m u l a t i o nt o o l su s e di n t h es t u d y w e d e e p l ys t u d yt h er o u t i n gi n s t a b i l i t yc a u s e db yi n c o r r e c tc o n f i g u r a t i o n s w ea n a l y z et h e r e a s o n s ，w h i c hc a u s et h ei n s t a b i l i t y , a n dg i v eo u tt h es o l u t i o n s i n c o r r e c tc o n f i g u r a t i o no fi b g pa n de b g pc a nc a u s et h et r a n s i e n ta n dp e r s i s t e n tr o u t e o s c i l l a t i o n s ，w h i c ha r et h em a i nr e a s o n so fi n s t a b i l i t yo ft h el a r g e s c a l en e t w o r k w em a k e u s eo ft h er o u t i n gs t a b i l i t yt e s t b e dt or e p r o d u c et h et y p i c a li n s t a n c e so fi b g pa n de b g p t r a n s i e n tr o u t eo s c i l l a t i o n s ，a n dc o l l e c tt h es e q u e n c eo fa c t i v i t i e so fb g pu p d a t em e s s a g e s e x c h a n g eo fb g pr o u t e r b ya n a l y z i n gt h ed a t ag o tf r o mt h ee x p e r i m e n t ，w eg e tt h e c o n c l u s i o nt h a tt h es p e c i a ls e q u e n c eo fb g p u p d a t em e s s a g e sc a nc a u s et h er o u t eo s c i l l a t i o n s i no r d e rt os o l v ei b g pa n de b g pr o u t eo s c i l l a t i o n s s o l u t i o n sa r eg i v e no u t t h ee x p a n dt e c h n o l o g i e so fb g pc a nc a u s et h ei n s t a b i l i t yb e c a u s e o fi n c o r r e c t c o n f i g u r a t i o n w ea n a l y z et h ei n s t a n c e so fp e r s i s t e n tr o u t eo s c i l l a t i o n s , w h i c ha r ec a u s e db y t o p o l o g yo fi b g ps c a l es t r u c t u r e n a m e l yr o u t er e f l e c t i o na n dc o n f e d e r a t i o n a n dw eo f f e r s o m ea d v i c et oi n h i b i ts u c hr o u t eo s c i l l a t i o n s k e yw o r d si n t e r - d o m a i nr o u t i n gp r o t o c o l ；b o r d e rg a t e w a yp r o t o c o l ；r o u t i n gs t a b i l i t y ； t e s t b e d ；r o u t eo s c i l l a t i o n s 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除 加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人 为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 学位论文作者签名 日 期 ：孙次 伽6 、i 、7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定： 即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、 交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 第一幸绪论 1 1 课题的研究背景 第一章绪论_ 帚一早珀了匕 i n t e r n e t 从诞生到如今已经得到了非常迅猛的发展，这使得人类社会更加全酬的 进入了信息时代。当前，i n t e m e tj f 在逐步深入到我们工作和生活的各个方面，已经成 为各个国家基础设施的一个重要组成部分。 然而i n t e m e t 并不是一个经过详细周密设计而进行整体构建的网络，而是一个逐步 发展，不断壮大的网络。随着i n t e m e t 的规模爆炸性的增长，其拓扑结构也变得极其复 杂，应用需求不断扩展，承载的业务h 趋多样，这引发了许多在i n t e m e t 发展初期未曾 料及的问题，例如：通信带宽短缺，路由交换能力不足，路出选择不稳定，网络安全性 等问题，这些问题f 1 益成为影响i n t e m e t 发展和应用的瓶颈。随着i n t e m e t 应用领域的 不断拓展，特别是近些年来电子商务的蓬勃发展，人们对于i n t e m e t 的稳定性、健壮性、 可靠性以及可管理性提出了更力苛刻的要求，从而使得i n t e r n e t 稳定性成为学术界和应 用领域普遍关注的焦点。 i n t e m e t 特别是主干网络的故障，过去只影响少数从事科研的技术人员，而现在随 着i n t e m e t 应用领域的不断扩大，将会损害成千上万终端用户的利益，会造成数以百万， 甚至数以千万美元的损失。据文献记载，最近在美国的几次大范围的i n t e m e t 路由故障， 不仅造成了难以估量的损失，而且动摇了公众对i n t e m e t 的信心，甚至有人预言i n t e m e t 濒临灭亡【2 1 。虽然这些人的言词未免有些耸人听闻，但是严峻的现实告诉我们解决 i n t e m e t 的稳定性和网络故障已成燃眉之急。影响i n t e m e t 稳定性的因素主要包括： ( 1 )硬件故障。接口故障、系统故障或链路故障都会直接影响i n t e m e t 的稳定性。当 然，系统和链路的冗余会改善由于故障而引起的i n t e m e t 连接中断，从而提高系 统的可靠性。 ( 2 ) 软件问题。软件的问题或“b u g ”可能导致系统的失灵和网络的不稳定。虽然开 发人员在软件发行之前会通过严格的测试手段，以尽力排查可能存在的问题。 但是，要预见所有可能在实际网络环境中发生的每一种隋况几乎是不可能的。 ( 3 )路由器处理能力不足。随着i n t e m e t 的广泛应用，链路传输速率的不断提高，以 及数据流量的不断增加，路由器需要处理的路出更新和建立的路由协议的对等 实体，以及引导的川户数据包都在迅速增加。所有这一切都要求路由器本身具 有更大的处理能力，一旦路由器的处理能力满足不了上述的要求时，就会出现 丢包的现象，从而影响路由协议的正常运行以及用户数据的传输，降低网络的 东北大学硕士学位论丈 第一章绪论 稳定性和可靠性。 ( 4 )路由器存储能力升i 足。路i = = i 器不仅需要存储自身的操作系统，同时还要存储路 山表、各种缓存袭、数掘库干【f 操作需要的其它软件。特别是现在路由表迅速 增长。据统计，在1 9 8 8 年到1 9 9 1 年问，路山表每1 0 个月翻一番。图1 1 说明 了这种增长情况【3 4 1 ，虽然采取了c i d r 技术减缓了路由表的增长，但是到目前 为止，路由表仍然变得十分庞大。一一旦路出器的内存用尽，则会造成路由器停 i e 工作。 ( 5 ) ( 6 ) ( 7 ) h u tr u ，ni i n e m r u0 1 ，ii a 0 lp rz t f h | l 小“。 ， 。， i ，” 。” 岛：“i 。7 墨。，qt ，嚣哼 “” 图1 1 路由表增长情况 f i g 1 1n u m b e ro fr o u t e si ni n t e r n e t 网络升级。网络是动态变化的，特性的改变、站点的合并和分离，以及扩展都 需要改变和调整网络。这些变化包括升级软件和硬件系统、增加更多的链路、 增加更多的带宽或网络结构的重新调整和配置。在网络升级后，经常出现软、 硬件的配置问题，以及升级部分与未升级部分的兼容性问题，而出此产生的网 络不稳定性会在其后的网络运行中不断暴露出来。 人为差错。大多数导致网络不稳定的人为差错是因为管理者忽视了某个管理策 略或者某些变化所产生的影响。如同利用某种计算机语言编写复杂应用系统一 样，在复杂的网络配置中很容易犯错误。例如：可能通告了不应通告的网络， 个服务提供者忘记通告某个客，o 的网络等等。这些错误都有可能导致性能和 连通性的严重下降。 链路超载。业务数据量超过了链路的带宽，从而使链路超载，导致网络出现拥 东北是擘硕士学位论丈 第一章绪论 塞现象。而拥塞则会使得终端剐。之问的连通性受到严重的影 i 向。 ( 8 )路山协议的收敛性。路山器上运行的路l l t m 议其收敛性越好，则网络上的路由 器更加容易在较短的寸问内建立个稳定的路由集，整个网络的稳定性越好， 分组丢失率越低。 上述的这些问题是i n t e m e t 主干网。遍存在的问题，学术界也j 下展开对上述 各类问题的研究6 i ，根据今年c n n i c 的报告l ”i ，全球互联网用广，依然增长势头强劲， 各类基于网络的应用对网络也提出了更高的要求，因此解决这些问题对于i n t e m e t 更加 稳定、可靠的运行具有重大的理论意义和应用价值。 1 2 研究的内容和方法 本课题将焦点集中在b g p 协议【2 8 】上，b g p 协议用于在自治系统a s 之间传递路由 信息，目前使用的是第4 版，也是唯一的一个用于进行域问路由的协议。b g p 协议已 经成为i n t e m e t 路由体系结构的基础，目前人们已经发现许多的路由故障是由于b g p 协议配鼍不当引起的【2 9 ，3 0 i ，因此，在本课题中将主要研究b g p 协议的配置错误。 b g p 协议是高性能路由器的核心软件之一，规模很大，系统也较复杂。由于该协 议是基于策略的路由协议，因此与其它的路出协议如r i p 、o s p f 相比配置复杂得多， 并且该协议在自治系统边界运行，各个自治系统可能会采用不同的内部策略而难以做到 全局协调，这些都可能造成实际的路山故障。因此，对于b g p 协议的配置故障进行研 究包含多个方面的工作。本课题具体包括以下几个方面： ( 1 )对路由技术的发展进行跟踪和探索。 ( 2 ) 建立i n t e m e t 路由实验床。 ( 3 )再现典型配置故障，分析造成故障的原因。 ( 4 )对典型配置故障提出相应的解决方案。 本文将从i n t e m e t 路由体系结构入手，讨论在骨干网上使用的域问路由协议b g p ， 研究典型的b g p 配置故障，讨论引起配置故障的原因，寻找避免错误配置的方法，从 而提高i n t e m e t 自身的稳定性和健壮性。 在研究方法上，我们首先将通过查阅棚关文献对i n t e m e t 路由技术和b g p 协议的细 节和操作进行了深入的理解，跟踪当 j f 对路 稳定性的最新进展和面临的困难。在对稳 定性问题的研究过程中，采用实验研究和理论分析的方法，对每一种典型配置故障都首 先在实验中再现，通过对捕获的路由更新报文进行分析以便抽取出关键特征，据此建立 能够进行理论分析的抽象模型，提出的解决方案也将通过实验和仿真的手段进行有效性 验证。希望通过这样的方法使得我们所提的解决方案具有一定理论价值和实际的应用 意义。 东北大学硕士学位论文 第一章绪论 1 3 论文结构 本论文共分为6 章，各章组织如下： 第一章给出课题研究的概要情况，对课题的研究背景、研究内容和研究方法进行概 括性叙述。 第二章介绍i n t e m e t 网络的路由技术对i n t e r n e t 的起源与发展、结构特点和在 i n t e m e t 网上进行i p 路出的基本原理进行了介绍，本章最后对自治系统和路由协议进行 了细致的叙述。 第三章重点介绍b g p 协议，讨沦了b g p 的特性和基本概念，对b g p 协议的各种 报文格式和b g p 操作进行了详细的介绍，然后给出b g p 的路由过程和路由控制机制， 本章的最后对b g p 的扩展技术联盟技术和路由反射技术等进行探索。 第四章给出i n t e m e t 路由实验床的设计思路和构建过程，并对实验床构建过程中涉 及到的工具进行介绍。 第五章分析b g p 协议配置过程中的一些典型故障，对i b g p 、e b g p 以及b g p 的 联盟和路由反射两种扩展技术中出现的典型配置故障进行研究。通过在实验床上再现故 障，收集各过程中的相关数据并分析，揭示故障产生的本质原因，并给出了相应的解决 方案。 最后在第六章给出研究结论，并对下一步的研究工作进行了展望。 第二章i n t e r a c t 路由技术 第二章i n t e r n e t 路由技术 2 1 i n t e r n e t 的起源与发展 i n t e m e l 起源于美国2 0 世纪6 0 年代后j 目盯始实施的a r p a n e t 计划p ”，其目的是 建立分布式的、存活力极强的全国性信i 息刚络。1 9 6 9 年1 2 月，a r p a n e t 网络通过 5 6 k b p s 的电路连接了4 个节点。这种祈投术在当时被证明是高度可靠的，因而被引入 到两个军事网络( 美国的m i l n e t 和欧洲的m i n e t ) 的建设中，到1 9 7 2 年，已经有 5 0 个大学和研究机构接入a r p a n e t ，并第一次公丌向人们腱示，此后数以千计的主机 和用户将其专用网连接到a p r a n e t 。 到1 9 8 5 年，a r p a n e t 已经超量使用并且出现捌塞，作为对策，美国国家科学基 金会( n s f ) 开始了n s f n e t 第一阶段的川：发，将多个区域网和对等网连接到n s f n e t 的核心主干网上，构成了一种三层的网络结构，即校同和研究机构连接到区域网，区域 网再连接到主干网，随着业务数据量的不断增加，n s f n e t 主干网的链路不断升级，1 9 8 8 年达到t i ( 1 5 4 4 m b p s ) 速率，1 9 9 1 年则达到t 3 ( 4 5 m b p s ) 速率。 盲到2 0 世纪9 0 年代初，n s f n e t 还仅供教育和研究之用但是商业和其他领域要 求聩网的呼声却同盏提高，于是出现了许多i n t e m e t 服务提供者( i s p ) 来满足这种需求。 美国之外的其他网络也不断发展，接入到主干网络中，一起组成国际互联网i n t e m e t ， n s f n e t 则于1 9 9 5 年4 月停用。 随着商用的介入，i n t e r a c t 进入了前所未有的高速发展，接入的主机数量和网络通 信量都呈现爆炸性增长。从主机数量来看，从1 9 8 1 年的2 3 1 台，几乎以指数增长，截 j 1 ：5 02 0 0 5 年1 月已经高达近3 亿2 千万s t ”i 。图2 1 给出了从1 9 9 9 年i 月到2 0 0 5 年1 月的i n t e m e t 主机数量变化情况。 现在i n t e m e t 已经覆盖了全球9 5 以l 的国家和地区，所提供的服务也已经从单 一的文本传输向多样化的多媒体应用转变，从而使得i n t e r a c t 深入到人们的同常工作和 生活中，并成为现代信息社会巾重要的公菇通信基础设施。 生活中，并成为现代信息社会巾重要的公拭通信基础设施。 东北大学硕士学位论文 第= 章i n t e r a c t 路由技术 第二章i n t e r n e t 路由技术 2 1lr i c e r n e t 的起源与发展 i n t e r n e t 起源于美国2 0 世纪6 0 年代后期丌始实施的a r p a n e t 计划【3 “，其目的是 建立分布式的、存活力极强的全国性信息刚络。1 9 6 9 年1 2 月，a r p a n e t 网络通过 5 6 k b p s 的电路连接了4 个节点。这种新技术在当时被证明是高度可靠的，因而被引入 到两个军事网络( 美国的m i l n e t 和欧洲的m i n e t ) 的建设中，到1 9 7 2 年，已经有 5 0 个大学和研究机构接入a r p a n e t ，并第一次公开向人们展示，此后数以千计的主机 和用户将其号用网连接到a p r a n e t 。 到1 9 8 5 年，a r p a n e t 已经超量使用并且出现拥塞，作为对策，美国国家科学基 金会( n s f ) 开始了n s f n e t 第一阶段的开发，将多个区域网和对等网连接到n s f n e t 的核心主干网上，构成了一种三层的网络结构，即校园和研究机构连接到区域网区域 网再连接到主干网，随着业务数据量的不断增加，n s f n e t 主干网的链路不断升级，1 9 8 8 年达到t 1 ( 1 5 4 4 m b p s ) 速率，1 9 9 1 年则达到t 3 ( 4 5 m b p s ) 速率。 直到2 0 世纪9 0 年代初，n s f n e t 还仅供教育和研究之用，但是商业和其他领域要 求联网的呼声却同益提高，于是出现了许多i n t e m e t 服务提供者( i s p ) 来满足这种需求。 美国之外的其他网络也不断发展，接入到主干网络中，一起组成国际互联网i n t e m e t ， n s f n e t 则于1 9 9 5 年4 月停用。 随着商用的介入，i n t e m e t 进入了前所未有的高速发展，接入的主机数量和网络通 信量都呈现爆炸性增长。从主机数量来看，从1 9 8 1 年的2 3 1 台，几乎以指数增长，截 止到2 0 0 5 年1 月已经高达近3 亿2 千万台p ”。图2 1 给出了从1 9 9 9 年1 月到2 0 0 5 年1 月的i n t e m e t 主机数量变化情况。 现在，i n t e r n e t 已经覆盖了全球9 5 以l 的国家和地区，所提供的服务也已经从单 一的文本传输向多样化的多媒体应用转变，从而使得i n t e m e t 深入到人们的r 常工作和 生活中并成为现代信息社会中重要的公共通信基础设施。 东北太学硕士学位论文 第二章i n t e r n c t 路由技术 3 5 0 0 0 0 0 0 0 3 0 0 c o o 0 【) o 2 5 0 0 0 0 ，o o o 2 0 0 ，o o o ，o o o 1 5 0 ，o o o ，o o o 1 0 0 ，0 0 0 ，0 0 0 5 0 。0 0 0 ，0 0 0 o _ | | j 。 ， 一一。 _ r ，_ - 一 一一 i f 一一 r 盘oo ohnnn 时 吲呐 西oooooooooo oooooooooooo h nn nv , jn nn nn 、 、 hh 一 - hp h一-一 oooooooooooo 图2 1i n t e r n e t 主机数量变化情况 f i g 2 1i n t e r n e th o s tc o u n ts u r v e y 2 2ln t e r n e t l 弘 结构特点 从i n t e m e t 的起源与发展可以看出它并不是一个根据完整的设计进行实施的网络， 而是一个逐步改进，逐步发展起来的网络。但是i n t e m e t 在发展过程中遵循着一定的原 则，即端到端的原则、在其它协议之上运行口协议以及一致的标准处理过程，这些已 经成为整个i n t e r a c t 体系结构中的关键部分【3 3 】。 从横向来看，i n t e r a c t 网络由端节点和网络节点构成，如图2 2 所示。其中端节点为 主机( 在图中用h 表示) ，网络节点是进行通信接入和网络交换的设备，在i n t e r a c t 中， 网络节点主要是路由器( 在图中用r 表示) 。 图2 2i n t e r n e t 的横向结构 f i g 2 2h o r i z o n t a la r c h i t e c t u r eo fi n t e r n e t i n t e m e t 主要具有如下特点： ( 1 ) 由国际范围内的、组织松散的、自治的计算机网络构成； ( 2 ) 自治的计算机网络通过智能州络节点( 即路由器) 连接起来 东北大学硕士学位论文 第= 章i n t e m e t 路由技术 ( 3 ) 用户数据封装在m 数据报内，经路由器逐级传递。直到目的主机。 因此，i n t e r n e t 是一个基于路由器的通信网络，所有端节点( 主机) 都必须通过网 络节点( 路由器) 才能与其他端节点进行通信。 从纵向来看，i n t e m e t 采用了分层的结构，它隐减了网络层以下各种不同的具体网 络实现的差异，在各主机之间从网络层以上采用t c p i p 协议族来实现互连。m 数据报 是整个i n t e m e t 数据传输的基本单位【3 4 1 ，所有上层协议( 1 p 层以上的，如t c p 、u d p ) 及应用层协议( 如s m t p 、s n m p ) 都是直接或间接地建立在口协议之上的，路由器根 据接收到的砰数据报的报头信息转发m 数据报。图2 3 说明了i n t c m e t 的纵向结构及 路由器所处的位置。 图2 3i n t e r n e t 的纵向结构 f i g 2 3l o n g i t u d i n a la r c h i t e c t u r eo fi n t e r n e t 2 3i p 路由基本原理 嘲络2 路由( r o u t i n g ) 是i p 协议的重要功能之一，同时也是i n t e r n e t 互联的基础。在i n t e m e t 中，主机之间可能会存在多条不同的物理路径，因此当主机之问要求进行通信时，需要 网络能够选择合适的路径到达远端网络和主机，并通过这些路径进行业务流量( t r a f f i c ) 的传递。 路由器( r o u t e r ) 就是用来完成路由选择和业务流量传递功能的设备。它利用了一 种“中继到中继( h o pb yh o p ) ”的技术【3 5 l ，即通过跟踪“下个中继”( n e x th o p ) 信息使 一个数据包能够经过网络传送，最终找到其目的地。与目的地之间没有直接物理连接的 路由器会检查它的路由表。向前转发数据包到更接近目的地的下个中继的路由器。这个 过程重复进行，直到业务流量通过网络找到并到达最终目的地。 整个路由动作包括了两项基本内容：路i 出( m u t i n g ) 和转发( f o r w a r d i n g ) 。路由是指判 定到达目的地的最佳路径，通过路由选择算法来实现。由于涉及到不同的路由选择协议 ，k 络网 东北是学硕士学位论文笨= 章i n t e m e t 路由技术 和路出选择算法，所以比较复杂。为了判定最佳路径，路由选择算法必须启动并维护包 含路由信息的路山表，其中路由信息依赖f 所刖的路由选择算法而不尽栩同。路由选择 算法将收集到的不同信息填入路山表中，根捌路山表可将e 1 的网络与f 一中继的关系告 诉路由器。路由器之叫通过相互交换信息进行路由更新。路由器利刷路dj 更新信息来维 护路由表，使之正确反映网络的拓扑变化，# 擞掘量度( m e t r i c ) 来决定最佳路径，这 就是路由协议( r o u t i n g p r o t o c 0 1 ) 。 而转发是指沿路由选择所确定好的最佳路径传送信息分组。路由器首先在路由表中 查找，判明是否知道如何将分组发送到下一个站点( 路出器或主机) ，如果路由器不知 道如何发送分组，通常将该分组丢弃；否则根据路由表中的相应表项，将分组发送到下 一个站点，如果目的网络直接与路由器相连，路由器就把分组直接送到相应的端口上。 这就是路由转发协议( f o r w a r d i n g p r o t o c 0 1 ) 。它与路由选择协议是相互配合又相互独立 的概念，路由转发时要使用由路由选择协议维护的路出表，而路由协议要通过路由转发 协议传递路由协议数据分组来获取路由信息，并据此更新路由表。 图2 4 给出了路出器对到达的i p 数据包的处理过程。 剑达数据包发出数据包 图2 4i p 数据包处理过程 f i g 2 4p r o c e s s i n go fi p p a c k e t 到达的数据包首先存储在队列中等待处理一旦处理开始，路由器首先对坤数据 包的报头进行检查，通过校验和( c h e c k s u m ) 可确定该数据包在达到本路由器之前是否 被非法修改。对通过检查的i p 数据包路由器要判断该数据包的心地址是否为本地地 址，如果是，则利用i p 报头的p r o t o c o li d 字段，将数据字段的数据传送给本地的相应 模块，如t c p 、u d p 、i c m p 等作进一步的处理，否则说明该p 数据包需要转发，路 由器根掘i p 数据包报头中的目的i p 地址与本地的路出表进行地址匹配如果匹配成功， 则该路由器就可以计算出下一个接收该t p 数据包的巾继节点，并按照浚节点的地址将 东北戈学硕士学位论丈 第= 章i n t e m e t 路由技术 数圭l l ：包转发出去，如果没有匹配成功则将该数据包转发到缺省路由上去，或者简单地 将其丢弃。 2 4 自治系统 早期的i n t e m e t 的路由体系结构只是一个平面的结构，所有的路由器都采用“网关 一网关协议”( g a t e w a y - g a t e w a yp r o t o c o l ，g g p ) 来共享路山信息。然而，当i n t e m e t 规 模不断扩大时，这种平面结构便带来了众多问题1 3 6 i ，例如：路由表激增、路由负载加重、 收敛速度下降、难于进行维护和故障隔离、网络升级变得更加困难和复杂等等。为了解 决这些问题，人们提出了层次化( h i e r a r c h i c a l ) 路由结构来代替平面路由结构。 在层次化路由结构中，i n t e r n e t 被划分为许多小的单位，即所谓的自治系统 ( a u t o n o m o u ss y s t e m ，a s ) 。如图2 5 所示，一个a s 是一个互连的网络，其最为重要的 特点是它拥有自主权，可以决定在本系统内应采用何种路由协议和路由策略。一个a s 内部的所有网络都隶属于同一个行政单位来管辖，例如：一个公司，一所大学，政府的 一个部门。每个a s 都有一个唯一的编号，这个编号是由i n t e r n e t 授权的管理机构分 配的。 图2 5 基于a s 的两层路由体系结构 f i g 2 5t w o l e v e lr o u t i n gh i e r a r c h yb a s e do na s 因此，路由选择协议也被划分为两大类，即：内部网关协议( i n t e m a lg a t e w a yp r o t o c o l ， i g p ) 或者域内路由协议( i n t r a - d o m a i np r o t o c 0 1 ) 和外部网关协议( e x t e r n a lg a t e w a y p r o t o c o l ，e g p ) 或者域问路由协议( i n t e r - d o m a i np r o t o c 0 1 ) 。i g p 是在一个a s 内部使用 的路由选择协议，它只负责在一个a s 内部路由信息的交换，例如：r i p ( r o u t i n g i n f o r m a t i o np r o t o c 0 1 ) ，o s p f ( o p e ns h o r t e s tp a t hf i r s t ) ，i g r p ( i n t e r i o rg a t e w a yr o u t i n g p r o t o c 0 1 ) 等。而e g p 则是在a s 之间使用的路由选择协议，它负责在a s 之间传递域间 网络可达性信息，目前使用的e g p 协议是边界网关协议( b o r d e rg a t e w a yp r o t o c o l ， 东北大学硕士学位论文 第= 章i n t e r a c t 路由技术 b g p ) a 2 5 路由协议 当业务量传递到某个路由器中时，需要在路由表中找出最佳路由条目来决定转发出 口。可以将路由条目分为三类：静态路山、动态路由和默认路由。 静态路由是指通过手工配置的路由，使用配置命令可以将静态路由加入到路由表 中。这种情况下，网络的可达性不依赖于网络自身的存在和状态，即不管目的网络是否 存在，静态路由都会保存在路由表中，丽相应的m 数据包仍然向目的地转发。使用静 态路由不需要运行任何路由协议，可以减少因路由通告和路由表维护而带来韵资源消 耗。静态路由一般应用在端网( s t u b ) 环境中，所谓端网只是有通信数据的起点和终点 的网络，通信数据不能穿越端网，因此进出端网的路由通常是静态路由，它的出口一般 指向一个事先配置好的路由器。 默认路由是指当在路由表中找不到与目标地址相匹配的路由时，数据包将被转发出 去的默认出口，它也被称为最后求助网关( g a t e w a y o f l a s tr e s o r t ) ，通过配置命令来设定， 因此默认路由也不涉及到任何路由协议。 动态路由是指通过运行路由协议得到的路出，路由协议可以探测网络的存在和状 态，通过网络可达性来决定是否将关于某网络的路由信息加入路由表中。如果某个目标 网络不存在，则关于该网络的路由条目会从路由表中删除，业务量不会向该目的地发送。 动态路由的添加和删除是由路由协议自动完成的，因此具有很好的灵活性，但是运行路 由协议需要占用一定的资源。 当我们提到路由协议的时候，都是指动态路由协议。在前一节中，路由选择协议被 划分为两大类，即：内部网关协议和外部网关协议。还可以根据采用的算法不同，可以 把路由协议分为距离矢量路由协议和链路状态路由协议两类。 2 5 1 距离矢量路由协议 距离矢量路由选择协议利用距离矢量算法( 也称b e l l m a n - f o r d 算法) 计算到达目的网 络的最佳路径，路径的优劣是通过一个度量值( 如路由器跳数) 来衡量的，一般选择度 量值最小的路径为到目的端的最佳路径。路由器之问相互协作完成路由选择任务，每个 路由器都把当前所选的最佳路径通知给它的所有邻居，同时它的邻居也把它们的最佳路 径通知给它们各自的邻居。这样，一个路由器在得到其邻居正采用的路径之后，如果发 现一条通过某个邻居的更好的路径，路由器就更新到达目的网络的距离和下一跳，并把 自己的新选择通知所有的邻居。在经过多次这样的迭代之后，路由选择将达到稳定，每 东北大学硕士学位论文 第= 章i n t e r a c t 路由技术 个路由器都会找到一个通往其目的端的最佳路径。 距离矢量协议是一个易于配置、维护和使用的非常简单的 办议，因此，在有极少的 冗余路径和对网络性能要求不高的非常小的网络中，这个协议表现得相对好。路由选择 信息协议r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 是典型的距离矢量协议1 3 7 】，运行r i p 协议的 路由器每隔3 0 秒广播一次路由信息报文，报文包含的信息来自路由器的当前路由选择 数据库，每个报文都包含网络地址和到达目的网络的距离( 跳数) 。r i p 所使用的距离 度量就是通往目的地所经过的路由器数，取值为1 1 5 之间的整数，值1 6 表示节点不 可达。r i p 协议交换路由信息的工作过程是：当路由器的某接口上启动r i p 后，接口以 多播的形式向邻居发送路由表信息请求：收到请求的路由器发送整个路由表作为对请求 的响应：而后就周期性地广播路由信息报文，只有当检测到路由变化时，才向邻居发送 触发更新，通知邻居路由变化。路由表的每个表目通常含有目的地i p 地址、通往目的 地的度量值、下一跳路由器地址、各种定时器和最近更新标志。r i p 协议的主要优点是 比较简单，但存在收敛比较慢、计数到无穷等问题，适合在小规模网络中使用。 2 5 2 链路状态路由协议 与距离矢量协议所采用的递增的分布式计算不同，链路状态路由协议采用了一种冗 余分布式数据库方法，根据链路状态算法计算路由。数据库提供关于每个路由器的局部 环境信息，反映的是整个网络的拓扑结构。一个路由器的链路状态是指它与哪个网络或 路由器相邻，以及到这些网络和路由器的度量。链路状态协议不用通告到达每个目的端 的路径代价，而是通过链路状态通告交换局部的网络链路和状态。这些链路状态通告被 发送给其他所有的路由器。最后的结果是所有的路由