（计算机科学与技术专业论文）域间路由优化工具bgp_rom的设计与实现.pdf

国防科学技术大学研究生院学位论文 摘要 传统的b g p 协议是一种基于策略的距离向量协议，只传输了a s 级别的信 息，隐藏了部分路径信息，并且其设计没有考虑流量负载的平衡性，因此存在网 络拥塞、策略碰撞、路由震荡等问题。b g p 协议是不支持域闻流量优化需求的。 商业上提出的一些路由优化技术和工具，它们的体系结构是完全自私的这 些基于动态测量的路由优化技术，仅仅从本域的利益出发进行域问路由优化，因 此路由优化往往不能进行全面的考瘩，会导致更多的不一致性碰撞问题、协议振 荡、配置错误等问题；另一方面，它们都是针对短期的交通流量进行控制，无法 做长时间粒度的优化。 为解决上述问题，本文研究与分析了b g p 协议的基本原理，深入研究了b o p 协议中b g p 路由处理过程以及路由选择算法。在分析b g p 协议路由处理过程和 其他路由优化工具的基础上，提出了域间路由优化工具b g pr o m 的设计方案， 深入研究了b g pr o m 实现的几个关键技术，并实现了原型系统。该工具考虑 了与b g p 协议的结合和流量的影响，在逻辑集中式控制路由体系结构平台上实 现了在线的路由优化。我们在l i n u x 环境下实现了该工具，并对该工具的功能 进行了测试和验证。测试表明，该路由优化工具能够达到设计目标。 主题词：域问路由优化，路由决策过程，域间流量工程，b g p 协议 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t t h et r a d i t i o n a lb g p p r o t o c o li sa k i n do fd i s t a n c e - v e c t o rp r o t o c o l , a n di tc a n o n l yt r a n s f e rn 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 w i t h o u tc o n s i d e r i n gt h el o a do f b a 】撇b g pp r o t o c o lm a yl e a dt os o m ep r o b l e m ss u c h 鹊n e t w o r kc o n g e s t i o n , s 蛔t e g yc o l l i s i o n , r o u t ec o n c u s s i o n 锄d6 0o i lt h e r e f o r e ，b g pp r o t o c o lc 锄n o t s u p p o r t i n t e r - d o m a i nu a f f i ce n o n e e r i n g an u m b e ro fr o u t eo p t h n i z i n gt e c h n o l o g i e sa n dt o o l s 哦r e l e a s e db ym a n y c o m p a n i e s , b u tt h e i ra r c h i t e c u m i ss e l f i s h b a s e d 蛳d y n a m i cl n e a s u l e , t h e s e t e c h n o l o g i e so p t h n i z er o u t e so n l yb yc o n s i d e r i n gt h e m s e l v e s s ot h e y 咖n o t 0 l ，i i m i g l o b a lr o l l t e 3 m a yl e a dt om o r ep r o b l e m ss u c h8 , 9c u s a g r e e m e n t p r o t o c o l s h o c k , c o n f i g u r a t i o ne r r o ra n ds oo i l o nt h eo t h e rh a n d , t h e yo n l yc o n t r o ls h o r t - t e r m t r a m c ，b u tc a n td e a lw i t hl o n g - t e r m0 i i i m i z a l i o n t or e s o l v et h e s ep r o b l e m s , t h i sp a p e rs t u d i e st h eb a s i op r i n c i p l eo f b g pp r o t o c o l ， t h e 印嘲so fr o u t ed e t e r m i n a t i o n , a n dt h er o u t ea l g o r i t h m b a s e do na n a l y s i so f p r o c e s so f r o u t ed e t e r m i n a t i o na n do t h e rr o u t eo p t i m i z et o o l s ，n o to n l yd i dw ed e s i g n 锄i n t e r - d o m a i nr o u t eo p t i m i z ct o o l b o p _ r o m b u ts t u d i e ds e v e r a lk e y t e c h n o l o g i e si ni t si m p l e m e n t a t i o n , f i n a l l yw ei m p l e m e n tt h i st 0 0 1 t h i st o o lc o n s i d e r s t h ei n t e r a c t i o no f b g p p r o t o c o la n d t h ei n f l u e n c eo f t r a f f i c ，i m p l e m e n t sg l o b a lo n - l i n e r o u t eo p t t m i z cb a s e do nr s ps y s t e m w ei m p l e m e n t e db o pr o mo nl i n u x o p e r a t i n gs y s t e ma n dv a l i d a t e si t sb a s i cf u n c t i o i lt h er e s u l to ft e s tr e v e a l e dt h a t b o pc d _rom a c h i e v o u rg o a l k e ) rw o r d s ：i n t e r - d o m a i nr o u t eo p t i m i z a t i o n , p r o c e s so fr o u t ed e t e r m i n a t i o n , i n t e r - d o m a i nt r a f f i ce n g i n e e l i n g , b o pp r o t o c o l 第i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1 优化工具比较 表5 1 域的接口声明 表5 2 域的方法 表5 3 流量矩阵的接口 9 表5 4 流量矩阵的方法3 4 表5 5 带流量的如算法数据结构 表6 1 两种路由结果比较 3 7 第m 页 国防科学技术大学研究生院学位论文 图目录 图2 1 r c p 体系结构 9 1 1 1 3 1 4 图3 1l i s p 体系结构 图3 2 l i s p 与船pr o m 关系 图3 3 a o pr o m 组成部分 图3 5 各模块关系顺序图 图4 1 路由决策过程函数调用关系图 图4 2b g p 结构体 1 6 1 8 1 8 1 9 2 0 图4 3 路由表的结构。 图4 4 路由处理过程流程图 图4 5 最佳路由选择过程 图4 6 路由选择标准 图4 7 交互过程1 图4 8 交互过程2 图4 9 交互过程3 图4 1 0 节点和链路结构 图4 1 l 路由节点结构 图4 1 2 流量矩阵结构 图4 1 3 优化主体类图 2 1 2 2 2 2 2 4 。2 6 图4 1 4 事件调度示意图2 7 图5 1 地址前缀和域路径结构 图5 2 路由信息和路由属性结构。 图5 3 f i en t 流程图 图5 4 主体框架顺序图 图5 5l i s p 与主体框架关系 图5 6 流量处理流程 图6 1 测试环境 图6 2 域内拓扑图及其变化 图6 3i g p 变化后的路由优化 图6 4 引入流量的路由优化 3 7 。3 9 3 9 4 5 4 6 4 7 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：缝闻坠直选焦至县堡壁= ! 型鲍塑盐皇塞塑 学位论文作者签名： 缘绎 日期： 护6 年，f 月哆日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：遗闷竖直优丝王县坚! = ! ! 丛煎遮盐生塞垫 学位论文作者签名： 作者指导教师签名： 日期：少，6 年1 1 月哆日 b 静l 6 年其8 b 国防科学技术大学研究生院学位论文 第一章引言 1 1 课题背景 随着互联网的迅猛发展，网络的服务质量越来越受到人们的关注。互联网必须 在能够提供可靠业务传输能力的前提下针对不同的用户提供不同质量的传输服 务。据调查显示，网络电话服务的质量比不上传统电话质量虽然人人旨知，但是 作为新兴技术的v o l p ，通话质量没有上升，反而出现了下降。b r i x 网络公司旗下 的网站t e s t y o u r v o i p t o m 调查数据显示，v o l p 电话的通话质量在过去1 8 个月内 下降了5 左右。分析指出，v o i p 电话通话质量的下降是因为竞争造成的，语音 电话要在相同的p 网络资源中和其他服务一同工作，比如视频，音乐下载与互动 游戏服务。多服务接入互联网，通信的质量势必会下降。 v o i p 服务只是网络服务的一个例子，那么随着互联网用户的快速增长和用户 需求的不断变化，网络服务对口网络技术提出了更高的要求。 目前在口网络广泛使用的域问路由协议是b o p 协议【l l i z l t 3 4 s 1 ，它是一种基于 策略的距离向量协议，为支持网络的可扩展性，其传输的路由信息只是网络的可 达信息，即只传输了a s 级别的信息，隐藏了部分路径信息，并且其设计没有考虑 流量负载的平衡性，因此存在网络拥塞、策略碰撞、路由震荡等问题。所以说传 统的b o p 协议是不支持域间流量优化需求的 为了解决上述问题，很多i s p 引入流量工程技术 e l 来提高口网络的性能。根据 作用范围的不同，流量工程可分为域内流量工程和域间流量工程两种。域间流量 工程技术主要研究六个关键问题：路由，流量映射，测量，抗毁性，分类支持， 网络控制等。其中最需要考虑的是路由问题。因为路由才是决定网络流量负载均 衡与网络稳定性的基础。 在国内新一代互联网技术的研究中，我国建立了高速互连研究试验网 n s f c n e t 、基于隧道技术的i p v 6 试验网c e r n e t - i p v 6 ( v i at u n n e l i n g ) 以及中日 l p v 6 - c j ( n a t i v el l v 6 ) 。同时，国家9 7 3 项目“新一代互联网路由与交换理论”直接 给予我们域问路由优化技术的研究以支持。 1 2 研究现状 1 2 1 国内的研究现状 当前，国内在域问路由优化技术上的研究还很少，国内公司也还未开发出域 第l 页 国防科学技术大学研究生院学位论文 问路由优化的产品。大部分的产品也是集中于域内流量工程技术的领域。如华为 公司为其路由、交换设备配备的网管软件中有关予实现域内流量工程的一些辅助 工具。还有一些是支持m p l s 技术川旧【9 】的路由器上支持域内流量工程的实现。如 华为【i 川路由器、风云路由器等 从目前国内的研究现状来看，域问路由优化技术的研究才处于起步阶段 1 2 2 国外的研究现状 国外对路由优化模型的研究中具体的体系结构有四类：完全自私的结构、基 于相邻域协商的结构、基于覆盖网络的结构、逻辑集中式控制的结构。 逻辑集中式控制的结构强调控制与转发分离，通过路由控制平面计算出的结 果来控制、调整路由协议的参数，然后再将其调整的结果反映到转发平面上，从 而达到控制调整路由的目的。这种体系结构是为了解决b g p 路由存在的若干问题 而提出的，如b o p 易出现配置错误、收敛性差等，避免了不断增加b g p 的复杂性 和b g p 协议出现的问题越来越多的循环。 这种体系结构的典型代表是伯克利大学加利福利亚分校的s h a r a da g a r w a l 等 提出的o p c a 体系结构i l l 】，m i t n i c k f c a m s t e r 与a t & t 实验室的j e n n i f e r r e x f o r d 博士等提出的r c p 体系结构1 1 2 】【1 3 1 。在理想的情况下，r c p 可以实现域之间的路由 交换，而不是路由器间的路由交换。相比其它结构，这种结构能对实施流量工程 提供较好的架构支撑。逻辑集中式控制的体系结构使我们实现真正全域范围内的 路由优化成为可能。但目前并没有出现这种体系结构为基础的商业路由优化的产 品。 商业上提出了一些路由优化技术和工具，比如f 5 网络公司的b i g - i pl i n k c o n t r o l l e i ，i n t e r n a p 公司的i n t e r n a pf l o wc o n t r o lp l a t f o r m “，r o u t e s c i e n c e 的 产品p a t h c o n m f l 1 6 1 。i n t e r n a p 公司的产品i i i i e r n 印f l o wc o n t r o lp l a t f o r m ，它分 为四个部件，包括f l o w c o l l e c t o r ，f l o w d i r e c t o r ，f l o w v i e w 、f l o w p r e v i e w 等等。 f l o w c o t l e c t o r 被动分析口网络实时流量，根据应用和流量识别网络，通过测量回 路性能和带宽利用率激活目标网络。f l o w c o n t r o l p r o g r a m 3 3 加入了一项新技术， 可以识别路由延迟不敏感的数据，比如在低成本低性能链路上传输电子邮件。这 样可以释放带宽给延迟敏感数据，比如口电话。路由优化使终端用户可以以每分 钟为时闯间隔选择自己的最快和成本最低的路由。还有r o u t e s c i e n c e 的产品 p a t h c o n t r o l ，和f c p 类似的，它通过测置点到点的网络连接之间的延迟来优化路 由。 这些商业产品，它们都是以单个路由器为出发点，作为商业公司，它们首先要 考虑的是成本，当然，在性能上也要让客户基本满意。它们都是以监视路由器的 流量为手段，通过发送p i n g 和l r a c e r o u t e 数据包等方法来探测和发现网络拥塞。这 第2 页 国防科学技术大学研究生院学位论文 些产品并没有考虑其它域的利益，我们说这是自私的，路由优化不可能全面。可 能导致更多的不一致性碰撞问题、协议振荡、配制错误等闻题，这些都是不可预 知的。另一方面，它们都是针对短期的交通流量进行控制，无法做长时间粒度的 优化，而且这种短期的流量控制也可能产生碰撞和协议振荡等问题。 比利时纳穆尔大学的s t e v eu h l i g 等人在t o t e m 项目口5 】中研究了出口方向控 制的域问流量工程1 1 7 - 2 4 , 硐。其主要思想是提出使用多目标的遗传算法来解决基于 b g p 的域问流量工程问题。t o t e m 为研究人员提供了一个集成算法的框架，但它 只是一个模拟工具，不能实施在线优化t o t e m 工具的对于域和流量的建模是值 得借鉴的。 1 3 课题研究内容 为了解决目前商业路由优化技术存在的一些问题，我们在逻辑集中式控制的 体系结构的基础上，考虑与b g p 的结合和流量的影响，设计一个可以实施在线的 路由优化工具b g pr o m 。 本课题以提高鼹绔牲能为目标，主要研究了域问路由优化技术，其主要内容 包括： 研究了b g p 协议的r f c ，深入研究了z e b r a 源代码1 2 6 中的路由处理过 程，分析了核心路由选择算法。 研究了一些路由优化和流量工程工具，分析了这些工具的设计思路和方 法。 在分析b g p 协议路由处理过程和其它路由优化工具设计思路基础上，提 出自己的域问路由优化工具b g p 的设计并实现。_rom 研究和分析了b g pr o m 的关键技术。 搭建了原型系统，用可靠数据对原型系统进行了测试，测试结果表明原型 系统达到了在线路由优化的功能，使疋网络性能得到了提高。 1 4 论文结构 论文的内容是对硕士阶段学习和研究成果的总结和升华，本文的结构如下： 第一部分：引言。简单介绍了课题背景、研究现状、课题研究内容以及本文的 文档结构。 第二部分：相关的研究工作。介绍了b g p 协议的基本原理，路由优化算法的 研究以及一些路由优化工具的研究。 第三部分：b g p的总体设计。详细描述了的总体设计方案。_ r o m b o pr o m 第3 页 国防科学技术大学研究生院学位论文 第四部分：b g p _ r o m 的关键技术。从三个方面分析了b g p _ r o m 的关键技 术。 第五部分：b o p的设计与实现。首先介绍b g p 的详细设计思_ r o m 3 2 1 _ r o m 路以及各模块关系图，然后描述了各模块的详细设计 第六部分：原型系统测试。使用可靠的数据对原型系统测试，结果表明满足要 求，提高了m 网络的性能。 第七部分：总结以及展望。 第4 页 国防科学技术大学研究生院学位论文 第二章相关研究工作 相关研究工作包括b g p 协议研究与分析，路由优化算法的研究，路由优化工 具的研究等，这些为域问路由优化工具b g p _ r o m 的提出提供了坚实的基础 2 1b g p 协议的基本原理 b g p 的版本1 在1 9 8 9 年以r f c l l 0 5 发表，然后在1 9 9 0 。1 9 9 1 和1 9 9 5 年分别 在r f c1 1 6 3 ，r f c1 2 6 7 ，r f c1 7 7 1 1 l 】中发表了版本2 3 ，4 b g p - 4 包含了所有前面版 本的功能，同时支持无类路由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 - 4 运行在t c p 之上，端口 号为1 7 9 。要开始与其它路由器的b g p 会话，一个路由器在建立t c p 连接后，需 要向b g p - 4 端口发送一个o p e n 信息。在o p e n 结束后，两个路由器交换所有的 活动路由( 当然，应用所有可应用的过滤规则) 这个过程的执行需要几分钟， 特别是对于具有大量活动路由的路由器。 做完这个工作，在b g p 会话中由两个主要类型的信息。首先，是检查b g p 会话是否仍在允许的两个方向的k e e p a l i v e 信息。其次是会话的路由修改r o u t e u p d a t e 信息。只有当路由表的表项自上次修改后又有新的更新时才会发送修改信息 ( 或者传输所有的活动路由) 。有两者类型的修改。第一种是已存在路由的修改 或者新路由的通告信息a n n o t m c c m e n t i 另一种是通知接收者指明的路由不再存在 的撤回信息w i t h d r a w a l s ，这一般出现在起通告的路由不再被使用。由于b g p 使 用保证可靠性和顺序性的t c p 协议，除非发生变化否则不需要定期的发送通告。 但是，如果没有收到一个外部邻居的k e e pa l i v e 信息，一个路由器会认为该路 由器不再存在，并将来自它的所有路由信息删除。 与很多i g p 不同，b g p 不会简单地使用最短路径或者延迟来优化路由度量值。 因为它的目标是提供可达信息并保证路由策略，它的通告不会简单的通告类似于 跳数的度量信息。相反，它们使用如下格式： 口前缀：属性 其中：每个p 前缀可通告一个或者多个属性。这些属性在b g p - 4 中是一个实 数的标准属性。在本讲义的后续部分我们会介绍其中的一些细节其实，我们已 经介绍过一个b g p 属性l o c a lp r e f 。它并不是一个在路由通告中发布的属性， 而是在本地使用，用于为一个目的地选择合适路由的属性。 有两种类型的b g p 会话：在不同a s 问的b g p s p e a l d n g 路由器的e b g p 会话， 以及同一个a s 内部b g p 路由器间的i b g p 会话。它们的服务目标不同，但是却 使用相同的协议。 第5 页 国防科学技术大学研究生院学位论文 e b g p 是b g p 使甩的一种“标准馍式，毕竟b g p 协议是为了在l m e m c t 中不 同的a s 间交换网络路由信息而设计的。b g p 路由器执行路由过滤规则，并与其 它a s 中的路由器交换它们路由的子集 m g p 会话维护内部a s 的一致性由于i b g p 路由器要求通过完整的网状结 构连接，这限制了可扩展性。结果是，产生了两种解决该问题的策略，这两者策 略都是基于采用某种层次结构的手工配置。第一种策略使用路由反射器r o u t e r e f l e c t o r ，第二种设置b g p 路由器的联盟。 熟悉b g p 协议的基本原理是为了了解b g p 协议的运行过程，对b o p 协议的 实际应用了然于胸。在此基础上，我们可以再详细的分析其路由处理过程，为路 由优化工具在线功能的设计做好铺垫。 2 2 路由优化算法的研究 国内外研究人员已经作了很多路由优化算法的研究，有很多算法可以拿来直接 应用到路由优化工具中去比如c s p f 算法【嚣】，遗传算法刚，t i e 算法【3 1 1 等等。 本文要研究和设计的路由优化工具提供了一个框架，可以便利的集成各种算法， 为研究人员作优化提供方便。所以分析这些路由优化算法的特点有助于设计出更 好的算法集成框架。 路由优化算法的研究主要是分别从不同的优化日标、不同的约束条件下提出不 同的算法。由于此类路由优化问题是n p 完全问题，因此当前提出的路由优化算法 主要有六类：启发式算法、遗传算法、本地随机搜索算法、激励算法、热土豆改 进算法、基于实际测量的算法。 启发式算法、遗传算法、本地随机搜索算法、激励算法的复杂性比较大，适合 于较长时间的粒度的路由优化和离线优化。而热土豆算法、基于实际测量的算法 则适合于在线优化。 路由优化问题可以用组合优化来解决。组合优化( c o m i f i n a i a i a lo p t i m i z a t i o n ) 解决离散问题的优化问题，是运筹学的分支组合优化通过数学方法的研究去寻 找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、 工业工程、交通运输和通信网络等许多方面。年代以来出现的现代优化方法有 禁忌搜索( t a b us e a r c h ) 、模拟退火( s i m u l a t e da n n e a l i n g ) 、遗传算法( g e n e t i c a l g o r i t h m s ) 、神经网络( n e u r a ln e t w o r k s ) 、蚂蚁算法( a n ta l g o r i t h m ，群体( 群 集) 智能，s w a r mi n t e l l i g e n c e ) 等其它方法。比如蚂蚁算法，基于蚁群寻找食物时 的最优路径选择问题，构造人工蚁群，来解决最优化问题，如t s p 问题。人工蚁 群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信 息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择， 第6 页 国防科学技术大学研究生院学位论文 也就是最终的优化结果。还有遗传算法。遗传算法g a 把问题的解表示成“染色体”， 在算法中也即是以二进制编码的串并且，在执行遗传算法之前，给出一群“染色 体”，也即是假设解然后，把这些假设解置于闯题的“环境”中，并按适者生存的 原则，从中选择出较适应环境的“染色体”进行复翻，再通过交叉，变异过程产生更 适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环 境的一个“染色体”上，它就是问题的最优解。 路由优化算法的研究是为了了解各种算法的原理和特点，然后结合路由优化 问题，把相应的算法做适当的修改，以便集成方便使用 2 3 路由优化工具的研究 国内外有很多路由优化和流量工程工具，如f c p t t 4 l ，p a t h c o n t z o l ! 堋，t o t e m 1 叼 等这里做一些分析和介绍。 1 、i n t e r n a pf l o wc o n t r o lp l a t f o r m f l o w c o n u o l p l a t f o r m 是矾t e r n a p 公司的产品。它主要有以下特点： f c p 被设置为路由器的对等体，有一个扩张端口和路由器连接，这个端口也 用来发送p i n g 探测以及其它的探测来帮助评估性能。f c p 还有一个独立的端口给 c u 和网页界面管理访问点。 f c p 实时监视所有的t c p 流，查找重新传输的数据包和长时间的r t t 时间， 来指示性能问题，如延迟和丢包等等。所有流数据都要通过一个特定的端口，但 是并不成为一个数据传输的节点，这样可以避免节点失效。 另一个优点，f c p 在向一条路径发送探测之前，先用多个t r a c e r o u t e 来确定拥 塞点。一旦拥塞点找到了，f c p 再开始向那个拥塞点发起探测，这使性能分析更 加有效。 对经测试的数据流，f ：p 可以配置以成本为优先考虑的策略。当f c p 监测到 带宽利用率达到一个预设的阀值，f c p 将会把流量引导到另一条相对廉价的路径 上。带宽利用率超过预设的阀值后，i s p 将会为超过部分额外付费。谈到粒度控制， 可以设置几个价格等级，f c p 可以灵活的使价格和性能达到一种平衡。只有在不 会引起大幅度性能下降的情况下，f c p 才会使用最廉价的路径。 f c p 有和思科类似的命令行界面，包括配置和查看命令。大多数的设备配置 和报告生成都可以通过w e b 界面来完成。另外，f c p 的报告选项也很丰富。 2 、p a t h c o n t r o l p a t h c o n t r o l 是r o u t e s c i e n c e 公司的产品。其主要特点如下： 和f c p 类似，p a t h c o n t r o l 也使用了设置自己为b g p 对等体的技术。该设备可 以发送多种探铡来测试性能，也有一个扩张端口，但是它只监视流量等级。 第7 页 国防科学技术大学研究生院学位论文 p a t h c o n t r o l 有另外一种方法来监测流量，它监视t c p 握手连接。这个方法似乎比 f c p 要好，因为f c p 需要监视所有的t c p 流但是p a t h c o n t r o l 的局限在于只能 为w e b 访问服务 和f c p 一样，p a t h c o n t r o l 在优化成本和性能上也很优秀。只有在不会引起大 幅度性能下降的情况下，p a t h c o n t r o l 会使用最廉价的路径。 p a t h c o n t r o l 也有一个i o s 风格的c l i 。但没有w e b 页面的配置方式。性能分 析的报告虽然没有f c p 做的那么详尽，其路由信息的报告也是一大亮点 3 、t ( y i b i 工具 这里介绍t o t e m 流量工程工具，其中有很多可借鉴之处。 t o t e m 全称为t o o l b o xf o rt r a f f i ce n g 蛐gm e t h o d s 。t o t e m2 1t o o l b o x 提供了一个框架，这样研究人员可以集成他们的流量工程算法。这些流量工程算 法可以应用到真实的网络模型中。t o t e m 框架可以让研究人员在自己的网络上试 验那些流量工程算法。其中该工具也实现了一些算法，如c s i f 、i g p w o 、c b g p 3 4 、 d a m o t e 等等。 从设计一个优化工具的角度来讲，在t o t e m 工具中可以学习的地方： 网络模型的建立 d o m a i n ：域的概念 1 h 缳c m a t r i x ：流量矩阵的概念 n e t w o r k c o n t r o l l e r ：网络控制器 统计功能 统计当前网络的状态，网络流量、负载等各种信息，建立各种度量值，形成 一个初步的评估体系。 网络事件机制以及设计模式 模拟网络环境，在模拟环境中执行一系列的网络事件，给出各种算法的优劣， 找出最优方案。 该工具用到了多种设计模式：外观模式，单例模式，工厂方法模式。 当然，t o t e m 也有其不足的地方。首先，t o t e m 只能做离线模拟，不能做 在线优化。所以可以作为网络管理员的辅助工具，不能直接应用到路由优化中， 还需要做一些改进。再者，虽然t o t e m 建立了网络模型，但其在算法集成方面 是不方便的，很多算法是直接编码在工具中的，扩展性不好，这也是有待改进的 地方。 上述三个优化工具各有优缺点，下面分别在设计和功能上从三个方面做一下对 比，如表2 1 所示。 第8 页 国防科学技术大学研究生院学位论文 表2 1 优化工具比较 工具名称建立网络模型算法集成在线优化 f c p 没有没有是 p a t h c o n t m l 没有没有是 t d 聊 有 有，但不够灵活离线模拟 f c p 和p a t h c o n t r o l 都是商业产品，它们都是通过测量手段跟踪路由和流量来 实施在线优化。这两个工具可以详细的跟踪路由和流量信息，生成详细的报告， 为网络性能评估提供详尽可靠的数据，但不能做出性能评估。它们没有建立网络 模型，主要依靠测量优化路由，算法方面也没有集成算法框架，只能用少数的算 法实现它们的商业功能。 t o t e m 是一个离线的模拟工具，可以为网络管理人员提供建议，不能拿到实 际应用中去。它对网络的各种事物和现象进行了抽象，建立了网络模型：同时提 供了算法集成的框架，但可扩展性并不好，有些算法是直接编码在工具中的。 我们分析这些优化工具的是希望能够知道目前正在使用的优化工具都有什么 特点，各有什么优缺点，在分析这些工具的基础上，综合这些工具的优点，设计 出更好的优化工具来。 2 4 路由控制平台r c p 麻省理工学院n i c k f e a m s t e r 与a t & t 实验室的j e n n i f e r r e x f o r d 博士等人提出 了路由控制平台( r c p ) 体系结构【9 ，埘。每个a s 都有一个逻辑上集中控制的路由 控制平台r c p ，r c p 代表整个域与相邻域的r c p 交换路由策略信息，并拥有整个 域的域内拓扑结构和b g p 路由信息，可以代替域内所有路由器作出b g p 路由决策， 如图3 1 所示 图2 1 r c p 体系结构 r c p 体系结构体现的也是一种控制和转发相分离的思想，从根本上对现在的 第9 页 国防科学技术大学研究生院学位论文 b g p 协议存在的问题进行解决，因此它有如下特点：l 、r c p 代替域内所有路由器 进行路由决策，从面防止了i b g p 路由协议的不一致性；2 、可以在一个网络范围 内进行路由决策和策略设置；3 、实现域间交换路由而不是路由器间交换路由，简 化了协议，提高了路由器的性能。 2 5 本章小结 本章介绍了相关的研究工作，包括b g p 协议的摹本原理，路由优化算法的研 究，优化工具的研究，还有路由控制平台r c p 。熟悉b g p 协议的基本原理为路由 优化工具在线功能的设计做好铺垫。分析各类优化算法的特点，为集成算法的设 计打好基础。各类优化工具的研究是我们清楚的了解现有优化工具的功能，让我 们能够结合它们的优点，设计出更好的优化工具r c p 的体系结构是逻辑集中式 的体系结构，适合流量工程的实施我们在r c p 的基础上提出了面向流量工程的 支持路由优化的r s p 结构。 第l o 页 国防科学技术大学研究生院学位论文 第三章b g pr o m 的总体设计 3 1r s p 的研制背景 r i 的体系结构是逻辑集中式的体系结构，适合流量工程的实施。烈：p 结构 将解决焦点集中于一个自治域内b g p 路由决策的一致性、正确性，因此切合我们 的设计目标，易于实现。因此我们在r c p 的基础上提出了面向流量工程的支持路 由优化的r s p 结构网。 为了作出每个路由器在全互联的i b g p 结构中会选择的路由，r s p 必须拥有 i g p 拓扑信息和从每个路由器到目的地的最佳路由，这些路由器从相邻的a s 获得 路由这样，r s p 由三个模块组成：域内拓扑观察器( m ev i e w e r ) ，b g p 引擎g p e n g i n e ) 和中心控制服务器0 7 3 u t ec o n t r o ls e r v e r ，r c s ) 。i g pv i e w e r 与一个或多个 路由器建立邻接，从而使得r s p 可以获得整个自治系统的i g p 拓扑信息。b g p e f l g i n e 从路由器获得b g p 路由并将r c s 计算的路由分发到各个路由器。然后r c s 用i g pv i e w e r 获得的i g p 拓扑信息和从b g pe n g i n e 获得的b g p 路由来为每个路 由器计算出最佳路由。( 见图3 1 ) 图3 1r s p 体系结构 ( 其中细的虚线为i b g p 连接，粗的虚线 为e b g p 连接，实线箭头为i g p 连接) r s p 通过标准的路由协议与一个a s 内的路由器进行交互。假设一个a s 内的 所有路由器r 构成i g p 连通图g = ( r ，e ) ，e 是i g p 拓扑图中的边。虽然一个 a s 内的i g p 拓扑结构通常是一个连通整体，但是链路故障，路由器或者接口都有 可能造成这部分网络的分块。这样，g 包括了一个或多个连通的块，比如g = 第1 l 页 国防科学技术大学研究生院学位论文 p i , f 2 ，p n 。r c s 只为具有其完整i g p 和b g p 信息的p i 计算路由，并且为每 个部分独立地进行路由计算。 r s p 还维持有和优化模块间的接口，以便选择优化模块提供的支持流量工程 的优化算法来取代标准的决策过程进行路由计算 域内拓扑观察器监控i g p 拓扑结构并将其提供给r c s 。域内拓扑观察器通过 建立的i g p 邻接接收i g p 的连接状态通告( 1 i n k - s t a t ea d v e r t i s e m e n t s , l s a s ) 。为 保证不通过域内拓扑观察器发送数据包，路由器和域内拓扑观察器间的连接应该 设置成高的i g p 代价。由于i g p ( 比如o s p f 和i s i s ) 执行可靠的泛洪算法( f l o o d i n g ) 来广播l s a ，不论是连接代价的改变还是设备的增减，域内拓扑观察器都可以拥 有最新的i g p 拓扑结构。使用泛洪来广播l s a 意味着i g p 只要与一个分区中的一 个路由器有邻接就可以从该分区中所有的路由器接收l s a b g p 引擎维持和a s 内的每一个路由器的i b g p 连接。这些i b g p 连接使得 r s p 可以：( 1 ) 获得备选路由；( 2 ) 将其路由决策发送给路由器。因为i b g p 运 行在t c p 之上，b g p 引擎并不需要与每个路由器有物理连接。事实上，b g p 引擎 可以与任何通过i g p 拓扑可达的路由器建立并维持i b g p 连接。b g p 引擎可以通 过网络中其他路由器的“下一跳”地址来广播b g p 路由。一个路由器和b g p 引擎 交互就如它和一个普通的b g p - s p e a k i n g 路由器交互一样，但是b g p 引擎可以为每 个路由器发送不同的路由。 r c s 从域内拓扑观察器获得i g p 拓扑信息，从b g p 引擎获得b g p 路由，然 后为一组路由器计算路由( 计算所依据的是标准的决策过程或者优化模块提供的 优化算法) ，然后将结果路由返回给使用该b g p 弓l 擎的路由器。如果一个路由器 已经选择了比其它备选路由更好的路由( 根据决策过程得到) ，r c s 将不会给该 路由器发送路由。 r s p 路由体系结构达到了以下三个设计目标，降低了域问路由的复杂性，提 高了路由效率和正确性： 1 路由系统的体系结构必须以基于一致路由状态的路由决策为基础。 2 各路由协议接口问的交互最小化。 3 域问路由机制必须直接支持灵活的，易于描述的策略。 3 2b g p _ r o m 与r s p 的关系 在第二章中我们分析了b g p 协议的基本原理，为的是在我们的路由优化工具 的设计中考虑与b g p 协议的结合；分析了路由优化算法的特点，是为了更好的把 各种算法集成到我们的工具中来；分析了路由优化工具的优缺点，是为了综合它 们的优点避免它们出现的问题 第1 2 页 国防科学技术大学研究生院学位论文 商业上的优化工具总是出现这样那样的问题，是因为它们都是从单个路由器 的角度出发来优化路由，没有考虑到其它路由器的利益，这是不全面的，造成很 多更严重的网络拥塞等问题也是显而易见的那么面向流量工程的支持路由优化 的r s p 系统一逻辑集中式路由体系结构的实现，为我们提供了最好的支持。在上 述前提下，我们提出了域间路由优化工具b g p的设计。那么有_romb g p _ r o m 那些优点呢? b g p 协议只是传达了网络路径的可达信息，并不能作路由优化，也不能处理 流量的变化；而流量工程工具t o t e m 只能作离线模拟，不能作在线优化，但其 设计思想有借鉴之处；故我们设计自己的路由优化工具b g p _ r o m , 该工具考虑了 流量的影响，并且与b g p 协议结合起来，让其运行在路由服务器上，就可作全域 的路由优化 与b g p 协议相比，b g pr o m 可以做路由优化，也可以处理流量变化，更好 的为网络提供质量服务；与流量工程工具t o t e m 相比，b g p 可以作在线优_rom 化，使路由优化更加贴近实际应用 在3 1 节中我们提到，r s p 维持有和优化模块间的接口，以便选择优化模块提 供的支持流量工程的优化算法来取代标准的决策过程进行路由计算。这里的优化 模块就是我们的域问路由优化工具b g pr o m 。r s p 系统和优化工具b g p 是紧密联系在一起的，如图3 2 所示。 _ r o m lr s p 系统 l 孽 l b g p _ r o m 图3 2 r s p 与b g p _ r o m 关系 由于i g p ( 比如o s p f 和i s - i s ) 执行可靠的泛洪算法( f l o o d i n g ) 来广播l s a ( 连接状态通告) ，不论是连接代价的改变还是设备的增减，域内拓扑观察器都 可以拥有最新的i g p 拓扑结构。所以b g pr o m 从r s p 系统总是可以得到最新的 域内拓扑信息，可以实时的监测域内拓扑的变化，并将域内拓扑的变化及时反映 给用户。 在r s p 系统收到b g p 的u p d a t e 消息后，由b g p实现的路由优化算法 为系统计算最佳路由，并将路由返回给系统_ 。r 这o m r s p r s p是在域内拓扑不发生变 化的时候的情形。 当域内拓扑发生了变化，r s p 系统的域内拓扑观察器会及时的通知