（计算机应用技术专业论文）bgp协议模拟技术的优化.pdf

哈尔滨工程大学硕士学位论文 摘要 b g p 是目前i n t e r n e t 上广为采用的a s 间的动态路由协议。模拟是 研究b g p 协议的有效手段之一。随着被模拟的网络的规模成比例的增长， 路由模拟成为了一个关键的问题。 对于目前b g p 协议模拟效率都相对较低的问题，为了提高b g p 协议 模拟的性能，减少b g p 模拟过程中的c p u 负载消耗，本文针对网络模拟 的优化问题，做了以下几个方面工作。 首先对网络协议，特别是b g p 协议进行了概述。然后阐述了网络模 拟技术，尤其对路由模拟进行了较为深入的分析和总结。同时介绍了相 关的网络模拟软件，特别是对b g p 协议的专用模拟器b g p + + 的形成过程 进行了系统的阐述。 对路由模拟技术，从两个方面做了路由策略优化的工作。第一个方 面是对路由查找过程的改进，优化了按需计算的n i x - v e c t o r 策略，在进 行n i x - v e c t o r 计算之前先搜索当前路由器节点的相邻节点集合，如果找 到了目的节点i d 则直接将目的节点i d 作为下一跳路由器地址返回，而 不必再进行n i x - v e c t o r 向量的计算过程；另一个方面是对模拟过程的改 进，首先去除b g p 模拟过程中的t c p 特性，用模拟器中路由节点间的连 接链路代替，即去除b g p 协议模拟过程中对t c p 的依赖性。其次，修改 了b g p 协议通过k e e p a l i v e - n o t i f i c a t i o n 来确定路由动态变化的方式， 改变了b g p 协议模拟过程中，依靠k e e p a l i v e - n o t i f i c a t i o n 发现拓扑信 息变化的策略。 最后，在l i n u x 系统上，以b g p + + 模拟器为基础，进行了真实性比 较实验和模拟性能比较试验。实验结果表明，在不失真实性的前提下， 这些优化技术能够有效的提高对b g p 协议模拟的效率，使模拟事件数大 大减少，模拟时间得到有效降低。 关键词：b g p , 网络模拟；路由算法；b g p + + 哈尔滨工程大学硕士学位论文 a b s t r a c t b g pi st h ed ef a c t oi n t e r - d o m a i n r o u t i n gp r o t o c o l o ft h ei n t e r n c t - s i m u l a t i o ni so n eo f t h em o s te f f i c i e n tm e t h o d sf o rs t u d yb o pp r o t o c 0 1 w i t ht h e d e v e l o p m e n to ft h es c a l eo fs i m u l a t i v en e t w o r k , r o u t es i m u l a f i o nb e c o m e sak e y p r o b l e m m o s to fc u r r e n tb g ps i m u l a t i o nh a sp r e u yl o we f f i c i e n c y i no r d e rt o i m p r o v et h ee f f i c i e n c yo fb o ps i m u l a t i o n , t h i sp a p e rp r e s e n t ss o m eo p t i m i z a t i o n m e t h o d sf o rr e d u c et h ec p ul o a d r o u t ep r o t o c o l so ft h ei n t e r n c ta r ef u s t l y s l , l m m a r i z e d b o r d e rg a t e w a yp r o t o c o li se s p e c i a u ye x p l a i n e d t e c h n o l o g yo f n e t w o r ks i m u l a t i o ni sn a r r a t e d a tt h es a m et i m e ，t h i sp a p e ri n ( t e d u c et h e s o h v a r eo f n e t w o r ks i m u l a t o r , e m p h a s i si sb g p 十tw h i c hi sas i m u l a t o ro f b g p i nt h e f o l l o w i n g ，s o m eo p i t i l n i z e dm e t h o d sf o r r o u t es t i m u l a t i o na 把 p r e s e n t e d o n ei si m p r o v e m e n tf o rt h es e a r c h i n gp r o c e s so f r o u t e m o d i f i c a t i o n i s m a d ef o rt h en i x - v o z t o r t h en e i g h b o r h o o dg a t h e r i n go fc u r r e n tn o d ei sl o o k e d u df o rd e s t i n a t i o nb e f o r ec o m p u t en i x v e c t o r i f t h ed e s t i n a t i o nn o d ew e r ef o u n d , t h i sn o d ei dw o u l dt a k ea st h ea d d r c s so fn e x th o p , t h ep r o c e s so fn i x - v e c t o r c o m p u t a t i o nw o u l dn o tb ee x e c u t e d t h eo t h e ri sb e t t e r m e n tf o rp r o c e s s o f s i m u l a t i o n f i r s t l y , t h ec h a r a c t e r i s t i co ft c pi sg e t t e dr i do fd u r i n gt h eb g p s i m u l a t i o n r e l a t i o n s h i pb e t w e e nb g pa n dt c pi sr e m o v e di nt h es i m u l a t o r s e c o n d l y , t h ek e e p a l i v e - n o t i f i c a t i o nm e c h a n i s mo fb g pi sm o d i f i e dt od e c i d e w h e t h e ral i n ks t a t ec h a n g e so rn o t a tl a s t a l l e x p e r i m e n ti sd e s i g n e d a n dc a r r i e do u tu n d e rt h el i u n x o p e r a t i n gs y s t e m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ee f f i c i e n c yo fb g p s i m u l a t i o nc a nb eg r e a t l yi m p r o v e dw i t ht h e s eo p t h n i z a t i o nm e t h o d s , t h en u m b e r o f e v e n t sg e n e r a t e dd u r i n gt h es i m u l a t i o nr e d u c e dl a r g e l y , a n dt h es i m u l a t i o nt i m e r e d u c e dg r e a t l yc o m p a r e dw i t ht h eo r i g i n a lb g ps i m u l a t i o ni nb g p + + k e yw o r d s ：b g p ：n e t w o r ks i m u l a t i o n ：r o u t i n ga l g o r i t h m ：b g p 抖 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的 指导下，由作者本人独立完成的。有关观点、方法、 数据和文献的引用已在文中指出，并与参考文献相对 应。除文中已注明引用的内容外，本论文不包含任何 其他个人或集体已经公开发表的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律结果由本人 承担。 作者( 签字) ：醢墨童 日期：即6 年，。月 哈尔滨工程大学硕士学位论文 1 。1 引言 第l 耄绪论 i n t e r n e t 由约1 8 ，0 0 0 个相互连接的自治域( a u t o n o m o u ss y s t e m ，a s 独 立的自管瑷网络域) 组成，每个自治域有统一的管理控制，可以怒一个企业嚼 终，一个i s p ，域一个校园嬲络。i n t e r n e t 的路由分为嚣令层次，域内 ( i n t r a - d o m a i n ) 路由和域间( i n t e r - d o m a i n ) 路由，分别由不同滕次的路由协 议实魂。内部圈关谤议( i n t e r i o r g a t e w a yp r o t o c o l ，i g 辨受奏今矗s 蠹都 的路由过程，例如o s p f ，r i p 等；而外部网关协议( e x t e r i o rg a t e w a y p r o t o c o l ，e g p ) 尉负责a s 闯的路由过程，皖如边界黼关协议( b o r d e r g a t e w a y p r o t o c o l ，b g p ) 等。翻翦，b g p 作为事实上的a s 问路由标凇广泛_ 陂用于 i n t e r n e t 上。不同于普通的路由策略，b g p 路由策略是基于不同a s 之间的商 韭蛰定来遂学程关路壶躲，霞嚣b g p 谚议鹣路由谤算移焱逶过糕更热复杂。 而这种复杂性又随着i n t e r n e t 规模的迅猛增长而进一步恶化。因此，b g p 协 议的研究工作得潮了越来越多瓣重褫。 网络协议的研究方法目前主要有三种：测量，分析以及模拟。其中测量 只能用于研究现脊网络，局限性较大。与分析方法相比，模拟其有能够完整 提供块议缨苓帮逑应大嫂模鄹络环境等使点，嚣戴在b g p 秘议辑究工终中应 用十分广泛。 瓣络搂攘技术是一释逶遘建立彤蓦设备耪阙终链路豹统计模型，势模攮 网络流量的传输，拓扑结构的影响等一系列网络特性，从而获取网络在正常 情况下，以及在网络病毒和网络攻击影响下的各种特征的模叛技术。阐络模 拟佟为一静圣亍之蠢效的、对实躲网络进行模拟与分析的方法，具有可馈度高、 使用范围广、应用成本低、可以提供真实和实用系统的可行性和安全性依据 等特点，奁逶售嘲络技术豹磁究孛毒着重要熬意义。 网络模拟技术提供将一个真实的网络放入一台或少数几台独立主机的可 能，从而为网络研究入受带来了继续 羿究的可能。运用网络模拟技术，可馥 哈尔滨工程大学硕士学位论文 通过各种模型和技术，在单机或小范围的与外界隔绝的网络中模拟大规模网 络的各种网络特性，这样，研究人员可以在绝对安全的情况下对网络病毒和 攻击进行实验，获取各种宝贵的数据。 网络模拟不仅可以模拟现已存在的网络环境，研究比较各种改进方案， 还可以构造一个虚拟的网络环境，实验新的网络协议和各种保障网络安全的 算法，以较小的代价对设计方案进行研究。网络模拟能够灵活的改变拓扑结 构，调整节点和连接，详细描述网络各层次的交互行为。因此，网络模拟己 逐渐成为进行计算机网络安全，性能研究、系统分析和实现的主要手段。 1 2 网络模拟技术研究的目的 随着互联网技术的不断发展和信息化进程的日益深入，网络安全问题越 来越突出，并已经成为制约信息化发展的重要因素。特别是2 0 0 0 年以来，全 球互联网上多次出现蠕虫、病毒、黑客攻击等重大安全事件，不仅严重影响 了全球互联网的正常运行，而且对于互联网上承载的各种应用带来巨大冲击， 造成了数以十亿美元计的经济损失。 为应对这些日益严重的网络安全威胁，近几年，本着“谁主管、谁负责， 谁运营、谁负责”的原则，各部门及企事业单位陆续开始着手建设各自的网 络安全保障体系，一定程度上缓解了网络安全所带来的危害。 但由于目前的网络安全研究更多地关注局部的网络安全问题，缺乏对互 联网整体安全态势的深入思索，无法从宏观层面客观地评估互联网的整体安 全状况，对于可能的突发事件及其爆发的方式和规模也无法准确地预测，这 就导致大规模网络的安全防范总是处于一种被动的境地，在发生大规模网络 安全事件时，各种决策也缺乏科学的依据。 对互联网的整体安全状况进行评估不同于传统的漏洞扫描、风险评估、 等级保护等安全性分析技术，一方面上述安全性分析技术的计算模型是针对 小规模网络的，其计算复杂性无法适应大规模互联网的安全评估；另一方面 上述安全性分析技术的应用前提是其基础数据可全部授权获得，基础数据的 完整性和准确性可以保证，而在大规模互联网的条件下，许多基础数据如主 机的信息、网络的拓扑等无法通过测量完整获得，一些关键数据需要进行理 2 哈尔滨工程大学硕士学位论文 论推演，因此互联网整体安全状况评估无法照搬传统的安全性分析技术。 大规模网络安全事件的爆发具有突发性、传播速度快、覆盖范围广和不 断变化等特点： 突发性导致该种事件无法事先准确预测； 覆盖范围广说明这种安全事件一旦发生所涉及网络节点数目庞大，无法 估计； 不断变化的特点使研究人员难以抓住该安全事件的本质，同一个安全事 件发作所产生的影响可能是不同的，这一方面是安全事件本身的行为发生变 化，另一方面网络环境也在不断发生变化。 这使得我们无法用纯理论的方法清晰描述网络的行为、安全事件的行为 属性，以及将有可能爆发的安全事件的发作方式、规模和破坏力。因此对于 互联网整体安全态势的研究必须借助于实验或者模拟手段。但由于网络安全 事件的特殊性，不可能直接使用真实的互联网环境来研究各种网络行为。这 样导致在网络安全研究领域，研究工作常常因为实验平台的规模限制，不能 得到真实的结果。例如一个蠕虫制造者可以把整个互联网当作一个实验平台， 可以向其释放各种蠕虫。但作为研究者这种行为是不允许的，因为一次蠕虫 爆发将带来巨大的损失。而建立科学的网络模拟体系可以对可能发生的安全 危害进行预演，所以依靠模拟的方法对大规模互联网的安全态势进行研究是 一个可行的方向n ，。 另外，网络模拟也可以应用于网络课程教学中m 。使用网络模拟软件构 建网络模拟环境，初学者不需考虑硬件和软件是否正确可用，只要根据实验 要求选择所需的抽象硬件实体、协议及其参数，就能得到正确的网络实验环 境。在该环境里，可以再现网络运行的任何细节，有效地学习网络协议，更 深入理解网络中的复杂行为。在教学中进行网络模拟，有以下优点： 1 ) 经济性。使用模拟软件，可基于现有的计算机，花费极少的资金就能 提供网络课程学习的软件实验环境，能解决受资金限制无法构建大规模网络 实验平台的问题。 2 ) 方便性。基于网络模拟器丰富的构件库，使用者可以在很短时间内模 拟网络常见协议和算法的运作过程。模拟过程中跟踪和监测对象，可以记录 网络系统的状态和事件。模拟结束后，使用相关组件可以将结果转换成易于 3 哈尔滨工程大学硕士学位论文 比较的平面统计图，方便使用者对网络性能进行分析；可以利用模拟得到的 相关文件运行动画，观察数据包传输过程和链路队列管理，同步监测各节点 的状态等。快速、生动地理解抽象的网络协议。 3 ) 针对性。模拟时，使用者通过灵活地设置网络模拟环境中每个实体的 参数，可以只获取自己感兴趣的网络运行细节的相关数据。通过这种设置方 式，使用者就可以有针对性地更改网络模拟环境，从不同的角度获取有用数 据，全面理解网络运行过程 4 ) 可重复性。只要模拟的网络拓扑、网络实体的参数和使用的协议等不 改变，模拟结果就不会发生改变。 1 3 网络模拟技术研究的背景 由于大规模网络安全事件的爆发能够在短时间内通过网络快速传播，。影 响到主机数目可能达到数百万台甚至上千万台。那么在网络模拟环境中就必 须要构建庞大数目的虚拟的主机。很显然单个的模拟器已经无法胜任，所以 分布式模拟器体系结构得到一定的发展m 。由于模拟体系的规模有限，所以 每个模拟器仍然要模拟大量的主机的行为。同时，对主机之间基于松耦合关 系的网格系统模拟器的研究也在开展“，一。而对于内存和c p u 资源都有限的单 个的独立模拟器，要提高其网络模拟的效率可以从两个方面完成：1 ) 采用高 效的机制和算法提高模拟器本身的模拟性能。2 ) 在不影响模拟真实性的前提 下尽可能减少所需要模拟的网络环境和网络行为的空间复杂度和时间复杂 度，科学地缩小模拟的规模。所以要解决网络模拟效率的问题要研究下几个 方面的内容。 1 ) 高效的路由模拟。影响模拟规模和模拟效率的因素有很多，路由策略 是最为关键的因素之一。首先，路由表的存储是模拟器存储资源需求的主要 瓶颈之一，而有限的存储空间正是限制模拟规模的关键所在；其次，在模拟 运行过程中，路由查找需要大量消耗模拟器运算开销，是影响模拟效率的重 要环节。因此，合理的存储管理模式和有效的路由查找算法是高效路由模拟 的主要研究内容。研究的难点在于这两个因素是互相制约、互相矛盾的，则 平衡路由存储空间和查找时间、提高综合效率是我们研究的目标。具体的研 4 哈尔滨工程大学硕士学位论文 究内容包括静态路由模拟策略研究、动态路由模拟策略研究和模拟器体系架 构改进的研究。静态路由模拟策略研究包括单机路由模拟策略，以及并行模 拟中的远程路由技术。动态路由模拟策略研究包括各种动态路由协议( b g p ， o s p f ，r i p 等) 的模拟技术，以支持拓扑动态变化时模拟器的模拟真实性m 。 模拟器体系架构改进的研究：将路由模拟作为模拟器体系架构中的单独一个 层次，模拟平台根据实际需要可选择的使用路由层的应用协议，保证路由模 拟的性能和真实性的全面提高。提高路由模拟的效率正是本文工作的出发点。 2 ) 抽象度分类模型的研究。提高网络模拟性能的另一个途径是减小模拟 的规模。如：对大规模的网络进行合理的切分，形成多个子网，将子网抽象 为一个点，这样以予网为模拟单位，实现用抽象的小规模网络反映实际的大 规模网络。这样实际模拟的规模变小了，模拟效率自然会提高。与此同时， 为了保证被模拟的行为在所关注的局部区域具有尽可能真实的效果，又需要 保证被模拟的事件所发生的核心区域应该是尽量精确的，因此，要研究的内 容包括：建立拓扑抽象度分类模型、流量抽象度分类模型、协议抽象度分类 模型。这就涉及到模拟粒度的问题，在不同粒度下，根据不同的需要来抽象 拓扑结构、流量和协议行为。对事件模拟的敏感中心区的网络采取细粒度的 模拟策略，以该敏感区为中心逐渐向外扩散，使之模拟粒度逐步变粗，从而 既可以达到反映真实情况的目的，又可以达到尽量减少系统开销的效果，使 得在解决模拟的规模问题和效率问题之间取得最佳平衡。其研究的难点在于 如何保证抽象的模型能够保持其原型系统的行为属性。 3 ) 分布式网络模拟性能评估。对于由多个网络模拟器构成的分布式网络 模拟，目前都采用并行离散事件模拟( p a r a l l e ld i s c r e t ee v e n ts i m u l a t i o n ， p d e s ) 机制来实现网络模拟的并行化，那么整个分布式网络模拟的性能也得 到了普遍的关注，为了对并行网络模拟性能有一个估计，并且依此指导如何 提高网络模拟的性能，需要对网络模拟性能有一个分析和估计。研究分布式 网络模拟性能的方法主要分为两种：实验分析以及模型分析。实验分析主要 是通过运行标准实例来分析分布式模拟器的性能以及各种对性能有影响的因 素。模型分析主要是通过建立数学模型，综合各种因素，来实现对模拟性能 的估计和评价。无论是实验分析以及模型分析，都没有综合考虑各种对分布 5 哈尔滨工程大学硕士学位论文 式网络模拟性能有影响的因素，比如运行环境，p d e s 时间推进机制类型，所 模拟的应用，以及模拟任务划分情况，只是简单的研究i ，2 个因素。 研究内容分为两个部分：建立分布式网络模拟性能测试基准和建立分布 式网络模拟性能估计模型。建立分布式网络模拟性能测试基准能够帮助分析 各种对分布式网络模拟性能有影响的因素，并刻画出各种因素对模拟性能的 影响趋势与程度；另一方面可以作为衡量分布式模拟性能的标准。建立分布 式网络模拟性能估计模型就可以定量的估计出分布式网络模拟的性能。依靠 此模型可以研究采用什么样的策略能够获得较高的模拟性能。通过上述两点 的研究，一方面能够对分布式网络模拟性能进行估计，量化模拟的性能指标， 帮助找出提高模拟性能的途径，发现网络模拟存在的缺陷。另一方面能够指 导模拟任务的划分。 从2 0 世纪8 0 年代开始，发达国家就开始了网络模拟研究。早期的网络 模拟主要使用c c + + 或者其他一些通用性程序设计语言，由于网络系统逐渐 变得复杂，网络事件的不确定性又往往很难表征出来，不同的研究人员可能 会采用不同的设计方法和结构，得到的结果不尽相同，缺乏公认的可靠标准。 随着计算机网络技术的快速发展，出现了很多专门的网络模拟软件，并得到 了广泛的使用和推广。 由于我国网络发展时间相对稍晚，加之美国对高端的网络产品的限制等 原因，我国在网络模拟和仿真方面的投入较少，直到2 0 世纪9 0 年代后期才 由各高校和通信研发公司陆续引进和使用o p n e t n ，和n s 一2 m 等软件。对于当前 比较流行的网络模拟器软件主要有以下几种： 1 ) n s - 2 ( n e t w o r k s i m u l a t o r v 2 ) 是一个可扩展的、易配置的、可编程的 离散事件驱动的模拟器。它有丰富的网络模型库，网络模型库包括拓扑模型、 流量模型和协议模型等。为了兼顾效率和运行速度，n s 一2 采用c + + 和 o t c l ( o b j e c tt c l ) 两种编程语言实现。n s - 2 定义了相关的模块用于记录模拟 的结果，可以指定文件名对模拟过程及相关参数进行跟踪。它提供了x g r a p h 用来以图形的方式显示模拟结果，n a m ( n e t w o r ka n i m a t o r ) 用来动态展示模拟 场景的动画效果。n s - 2 将各种网络设备抽象为节点，因此不能对具体设备的 网络处理能力进行模拟。 6 哈尔滨工程大学硕士学位论文 2 ) o p n e t 最早是于1 9 8 6 年美国麻省理工( m i t ) 的两个博士共同创建的， 后来由此成立了o p n e tt e c h n o l o g i e si n c 公司进行开发成为著名的商业网 络模拟软件。m o d e l e r 为o p n e t 中主要的核心模拟组件，它结合了基于包的 分析方法和基于统计的数学建模方法，采用层次性的模拟方式( h i e r a r c h i c a l n e t w o r km o d e l i n g ) ，节点模块建模完全符合o s i 模型，共提供了3 层建模机 制，底层为进程( p r o c e s sl e v e l ) 模型，通过状态机来描述协议对各对象进行 仿真；上层为节点( n o d el e v e l ) 模型，由相应的协议模型构成，反映设备特 性：最上层为网络( n e t w o r kl e v e l ) 模型。其中的各种代码都是完全公开的， 注释也很详尽，使得用户比较容易理解其操作。 3 ) s s f n e t ”是基于j a v a 和c + + 的s s f ( s c a l a b l es i m u l a t i o nf r a m e w o r k ) 的软件框架所组成。作为教育和科学研究用途的s s f n e t 是开放软件，允许用 户按需要进行补充和修改。开放源码提供面向对象的可扩展仿真建模的并行 运算环境，主要支持i p 包级别以上的细粒度模拟，链路层和物理层的协议模 型以独立的组件方式提供。s s f n e t 模型是一种自配置的模拟软件，每一个 s s f n e t 类能通过询问本地的配置数据库或者通过网络进行自主配置。网络配 置文件是用d m l ( d o m a i nm o d e ll a n g u a g e ) 来编写配置的，它被用来描述一 个完整的网络模型。在s s f n e t 软件中，被用作模拟主机和操作系统，特别是 协议的软件框架叫做s s f o s ；被用作模拟网络的连通性，建立主机结点和链 路配置的软件框架叫做s s f n e t 。s s f n e t 提供的协议支持包括： i p ，t c p ，( d p ，s o c k e t ，o s p f ，b g p 4 ，h t t p 等等。s s f n e t 可以支持的操作系统是 w i n d o w s 2 0 0 0 及以上系列，u n i x 操作系统，l i n u x 操作系统等。d m l 语言配置 方便，灵活；可以很好的定义所需的网络拓扑结构。目前s s f n e t 也支持大多 数网络协议，可以实现运行网络模型的功能。s s f n e t 具有灵活的可扩展性， 其配置语言d m l 具有自己的语法结构，用户可以按照需要自己编写d m l 配置 文件，设计网络拓扑结构模型。另外，用户可按照s s f n e t 的a p i 自行定义编 写所需要的新的网络模型或者协议。 目前，在处理大型网络和复杂网络的应用方面，网络模拟技术还不是很 成熟，不少的问题亟需解决，因此该领域还需要投入相当的人力和物力，以 达到更好的应用效果，进一步促进网络通信产业的研究和开发。 7 哈尔滨工程大学硕士学位论文 1 4 论文的组织结构 论文的结构安排如下： 第1 章对网络模拟技术的研究目的和研究背景进行了综述；说明了论文 的组织结构。 第2 章综述了大规模网络的模拟技术，主要针对b g p 协议，对大规模网 络的路由模拟和b g p + + 模拟器做了进一步阐述。 第3 章首先简要介绍n i x v e c t o r 策略；接着讨论了按需计算的 n i x - v e c t o r 策略，提出了对按需计算的n i x - v e c t o r 策略进行优化的思想及 其实现。 第4 章针对b g p 协议模拟过程的改进做了讨论，提出了以路由器节点连 接代替t c p 特性的思想和优化拓扑更新方式的策略。并对两种方法加以讨论， 阐述了实现的过程。 第5 章结合实验，针对前几章提出的优化策略对优化的真实性进行了阐 述，并对优化的效果进行了比较。 3 哈尔滨工程大学硕士学位论文 第2 章大规模网络模拟技术 2 1 引言 我们这里所说的大规模网络是指以自治系统( a s ) 域结构来划分的 i n t e r n e t 网。如何在有限的硬件资源条件下，尽可能的提高模拟规模和效率， 是大规模网络模拟研究工作的基本目标。影响模拟规模和模拟效率的因素有 很多。各a s 域主要是通过b g p 协议来协同工作的。目前的b g p 协议模拟工作 的主要缺点之一是模拟效率低下。由于b g p 协议的路由计算策略十分复杂， 数据信息交换频繁，因此对b g p 协议模拟效率提出了很大的挑战。 2 2b g p 网络协议 目前的t c p i p 网络，全部是通过路由器互连起来的，i n t e r n e t 就是成 千上万个i p 子网通过路由器互连起来的国际性网络。在这种以路由为基础的 网络中，路由器不仅负责对i p 分组的转发，还要负责与别的路由器进行联络， 共同确定网络中的路由选择和维护路由表。这就涉及到网络路由的两个基本 工作：路径选择和数据转发。路径选择即判定到达目的地的最佳路线，由路 由选择算法来实现。数据转发即沿选择好的最佳路径传送信息分组。他们分 别有各自的协议：路由选择协议( r o u t i n gp r o t o c 0 1 ) 和路由转发协议( r o u t e d p r o t o c 0 1 ) 。 路由选择协议：路由选择算法通过将收集到的不同信息填入路由表中， 让路由器根据路由表了解到目的网络与下一站( n e x t h o p ) 的关系。路由表通过 互通信息机制进行路由表的更新维护来正确反映网络的拓扑变化，并由路由 器根据量度来决定最佳路径。像路由信息协议( r i p ) 、开放式最短路径优先协 议( o s p f ) 和边界网关协议( b g p ) 等都是路由选择协议。 路由转发协议：通过查找路由表，路由器根据相应表项将分组发送到下 一站点( 路由器或主机) ，如果遇到不知道如何发送分组，通常路由器会将其 丢弃，在此之前，路由器会对分组进行识别。如果目的网络直接与路由器相 9 哈尔滨工程大学硕七学位论文 连，路由器就直接把分组送到相应的端口上 通常，我们所说的路由协议是指路由选择协议。在路由的工作原理中， 路由选择协议和路由转发协议既是相互配合又是相互独立的。 路由选择协议又分为两个部分：静态路由和动态路由。使用动态路由协 议路由器可以自动的学习到达远端网络的路径信息。而静态路由是网络管理 者手动的将到达目的网络的路径添加到路由表中。通常当一个分组在路由器 中寻找路径时，路由器首先查找静态路由，如果查到则根据相应的静态路由 转发分组，否则再查找动态路由。 2 2 1 动态路由协议 使用动态路由的路由器能自动交换路由信息从而了解整个网络的拓扑信 息，这一过程也就是网络中的路由器之间相互通信，传递路由信息，利用收 到的路由信息更新路由表的过程。动态路由适用于网络规模大、网络拓扑复 杂的网络，能够根据网络拓扑的变化自动更改路由表的信息，避免了人工手 动更改。当然，各种动态路由协议会不同程度地占用网络带宽和c p u 资源。 上一章曾提到，因特网的路由系统是分层的，按照两层进行操作。根据 是否在一个自治域内部使用，分为内部网关协议( i g p ) 和外部网关协议( e g p ) 。 内部网关协议根据路由选择协议的算法又分为连接状态协议( l i n ks t a t e p r o t o c o l s ) 和距离向量协议( d i s t a n c e - v e c t o rp r o t c o l s ) 。 距离向量协议( d i s t a n c e - v e c t o rp r o t o c o l s ) 也称为b e l l m a n - f o r d 协议， 采用距离向量路由选择算法，是最古老也是最简单的一种路由选择协议算法。 路由器定期向相邻的路由器发送它们的整个路由选择表( r o u t i n gt a b l e ) 。相 邻的路由器在接收到的这些信息的基础之上建立自己的路由选择信息表。距 离矢量路由协议有一个严重的缺点，收敛时间缓慢，缓慢的收敛时间过程会 造成路由回路( r o u t i n gl o o p ) 。比较典型的距离向量协议是路由信息协议 ( 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 ) ，内部网关协议( i n t e r i o rg a t e w a 卜 r o u t i n gp r o t o c o l ，i g r p ) 和增强型内部网关协议( e n h a n c e di n t e r i o r g a t e w a yr o u t i n gp r o t o c o l ，e i g r p ) 。i g r p 和e i g r p 是思科( c i s c o ) 公司自 主开发的动态路由协议，仅支持思科公司的网络路由设备“u 。 连接状态协议是一种比距离向量协议更为复杂的路由选择协议，目前最 l o 哈尔滨工程大学硕士学位论文 流行、应用最多的是开放式最短路径优先( o p e ns h o r t e s tp a t hf i r s t ，0 s p f ) 协议。o s p f 路由器利用。最短路径优先算法( s h o r t e s tp a t hf i r s t ，s p f ) ”， 独立地计算出到达任意目的地的路由，路由器之间交换拓扑信息，这样所有 的路由器对本地全网的拓扑都有一个完全的的视图。运行链路状态路由协议 的路由器不会传送路由表内的所有信息，只发送已经改动的路由信息。链路 状态路由器将向它们的邻居发送呼叫消息，这称为链路状态通告( l s a ) 。然后， 邻居将l s a 复制到它们的路由选择表中，并传递那个信息到网络的剩余部分。 这个过程称为泛洪( f l o o d i n g ) 。 对于外部网关协议，b g p - 4 是当前在i n t e r n e t 上广泛使用的事实上的标 准。 2 2 2 边界网关协议- b g p 概述 b g p 是一种不同自治系统的路由器之间进行通信的外部网关协议。b g p 是a i 诤a n e t 所使用的老e g p 的取代品。r f c l 2 6 7 l o u g h e e d a n dr e k h t e r1 9 9 1 对第3 版的b g p 进行了描述。r f c l 2 6 8 r e k h t e r a n dg r o s s l 9 9 1 描述了如何在 i n t e r n e t 中使用b 6 p ，1 9 9 3 年开发了第4 版的b g p ( r f c l 4 6 7 t o p o l c i e1 9 9 3 ) 。 在r f c l 7 7 1 中描述的b g p - 4 是现行的因特网的事实标准。它完成了各自治系 统a s 间的路由选择，可以说b g p 协议是现代i n t e r n e t 网的支架m - 。 为了阐述清楚b g p 协议，先对自治域系统a s 进行相关的介绍。一个自治 系统中的i p 数据报分成本地流量和通过流量。自治系统中的本地流量是指起 始和终止于该自治系统的流量。也就是说，其源i p 地址和目的i p 地址所指 定的主机都位于该自治系统中。其他的流量则称为通过流量。在i n t e r n e t 中使用b 6 p 的一个目的就是减少通过流量。根据流经自治系统的流量，可以 将自治系统分为以下几种类型： 1 ) 残桩自治系统( s t u b a s ) ，它与其他自治系统只有单个连接。s t u b s 只有本地流量，一 一 2 ) 多接口自治系统( m u l t i h o m e d a s ) ，它与其他自治系统有多个连接，但 拒绝传送通过流量。 3 ) 转送自治系统( t r a n s i t a s ) ，它与其他自治系统有多个连接，在一些 策略准则之下，它既传送本地流量也传送通过流量。 哈尔滨工程大学硕士学位论文 这样，可以将i n t e r n e t 的总拓扑结构看成是由一些残桩自治系统、多接 口自治系统以及转送自治系统的任意互连。 前面已经提到，b g p 是用来完成a s 之间的路由选择的，所以对于b g p 来 说，每一个a s 都是一个原子的跳度。建立了b g p 会话连接的路由器被称作对 等体( p e e r s o r n e i g h b o r s ) ，对等体的连接有两种模式：i b g p ( i n t e r n a l b g p ) 和e b g p ( e x t e r n a lb g p ) 。i b g p 是指单个a s 内部的路由器之间的b g p 连接，而e b g p 则是指a s 之间的路由器建立b g p 会话。 由于a s 在b g p 看来是一个整体，所以a s 内部的b g p 路由器都必须将相 同的路由信息发送给边界的e b g p 路由器。路由信息在通过i b g p 链路时不会 发生改变，只有通过e b g p 链路时，路由信息才会发生变化。在a s 内部，通 过i b g p 连接的路由器都有相同的b g p 路由表( b g pr o u t i n gt a b l e ) 用于存 放b 6 p 路由信息，i b g p 于i g p 有所不同，对i g p 路由表，两个表之间的信息 可以通过“再分布”( r e d i s t r i b u t i o n ) 技术进行交换。也就是将e b g p 传送 来的其他a s 的路由“再分布”到i g p 路由器中，然后将其“再分布”到e b g p 传送到其他a s 。而i b g p 的功能是维护a s 内部连通性，是用来在a s 内部完 成b g p 更新信息的交换。虽然这种功能也可以通过i g p “再分布”技术来完 成，但是相比之下，i b g p 提供了更高的扩展性、灵活性和管理的有效性。 b g p 规定，一个i b g p 的路由器不能将来自另一i b g p 路由器的路由发送 给第三方i b g p 路由器。这也可以理解为通常所说的s p l i t - h o r i z o n 规则。当 路由器通过e b g p 接收到更新信息时，它会对这个更新信息进行处理，并发送 到所有的i b g p 及余下的e b g p 对等体；而当路由器从i b g p 接收到更新信息时， 它会对其进行处理并仅通过e b g p 传送，而不会向i b g p 传送。所以，在a s 中，b g p 路由器必须要通过i b g p 会话建立完全连接的网状连接，以此来保持 b g p 的连通性。如果没有在物理上实现全网状( f u l lm e s h e d ) 的连接，就会 出现连通性上的问题。另外，与传统的内部路由协议相比，b g p 还有一个特 性，就是使用b g p 的路由器之间，可以被未使用8 g p 的路由器隔开。这是因 为b g p 在独立的内部路由协议之上工作，所以通过b g p 会话连接的路由器能 被多个运行内部路由协议的路由器分开。 在域一级，目的地址是根据根据子网地址也就是i p 前缀来制定的。现在 整个因特网路由表包括超过1 8 0 ，0 0 0 个这样的i p 前缀。b g p - 4 支持c i d r 1 2 哈尔滨工程大学硕七学位论文 ( c l a s s l e s si n t e r d o m a i n sr o u t i n g ) 和a s 路径聚合( a g g r e g a t i o n ) ，这种 新属性的加入，可以减缓b g p 表中条目的增长速度。为了提供全局的连接， 多个网络也就是各个域之间，要协调进行数据流量的交换，这要通过设置一 个或多个对等点，即对等路由器来实现。域之间( 不同的a s 间) 路由的执行 和控制跟域内路由不同。b g p 允许使用基于策略的选路。由自治系统管理员 制订策略，并通过配置文件将策略指定给b g p 。制订策略并不是协议的一部 分，但制定策略允许b g p 实现在存在多个可选路径时选择路径，并控制信息 的重发送。选路策略与政治、安全或经济因素有关。不同的网络间的流量的 交换是通过商业上的协定来决定的，根据这些协定定出相应的路由策略，由 路由协议执行了这些限定。一般的，两个网络问典型的商业关系包括客户 提供者( c u s t o m e r p r o v i d e r ) 和对等关系( p e e r p e e r ) 。一个用户从一个 i s p 处购买因特网的访问权，也就是，在因特网上通过这个i s p 寻到的所有 到其他终点的路由对这个客户应该是可见的。同样，到客户网络的路由要告 知给因特网的其他部分。在对等关系中，两个网络的操作者是互惠互利的， 相互交换对方的数据。比如，有两个地区的i s p ，我们称之为a 和b ，他们的 用户之间可以直接交换流量，不用把流量传送给他们上一级的提供者。在这 种情况下，a 把从它的客户得到的路由告知给b ，并且，接受b 的客户的路由， 重新告知给自己的客户。然而，a 不把从它的上一级提供者寻到的路由告知 给b 。也不把b 的路由告知给它的提供者。因为这将导致a 给b 提供传送服 务。b g p 允许对路由策略做详细的规定以便来控制路由的优先权，不论这个 路由是否允许使用，是否他们被再告知。 b g p 是一种类似于距离向量( d i s t a n c ev e c t o r ) 的路由协议，称之为路 径向量协议，它的操作与距离向量协议相似，但是比起r i p 等典型的距离矢量 协议，又有很多增强的性能。它在最优的路由上跟它的邻居节点交换信息， 最终汇聚到一个稳定的状态。然后，b g p 路由告知邻居几种衡量路由路径的度 量标准( 称为路由属性) ，来强化路由策略的配置。包括由路由传送的全a s 路径，这个全a s 路径在强化配置路由策略时被路由过滤和选择机制使用，可 以更加准确的判断出最优的路径。在通信时，b g p 使用t c p 作为其传输层协议， 使用端口号1 7 9 ，数据传输的可靠性就由t c p 协议来保证。两个运行b g p 的系统 之间建立一条t c p 连接，然后交换整个b g p 路由表。从这个时候开始，b g p 使用 1 3 哈尔滨工程大学硕士学位论文 “保留信号”( k e e p a l i v e ) 来监视t c p 会话的连接。在路由表发生变化时， b g p 使用增量的、触发性的路由更新，发