（通信与信息系统专业论文）自治域路由快速收敛、竞争策略和流量特性建模.pdf

北京交通大学博士学位论文 中文摘要 摘要：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 的持续 健康发展。 本文针对自治域层面的若干问题进行了一系列研究，包括； 1 研究了b g p 路由的快速收敛问题。b g p 在网络发生故障后的收敛速度并不 理想，依靠在路由消息中附加链路状态信息的方法虽然能够达到快速收敛的目的， 但却引入了高昂的存储代价，而采用先将路由树拆除再重新建立的方法也大大降 低了末端a s 的连通性能。本文提出了新的加速b g p 收敛的方法，该方法对路由 消息的发送规则做了新的改进，放弃了向所有邻居广播撤销消息的做法，转而通 过引入适当的探测代价，既避免了不必要的撤销消息的发送，又能保证路径探索 过程快速进行，在仅需要花费少量存储代价及通信代价的前提下，最终实现b g p 快速收敛。 2 研究了自治域间的流量竞争闯题。在i n t e m e t 商业化运作模式下，各自治域 扮演着提供者( p r o v i d e r ) 和用户( c u s t o m e 0 等不同角色，而如何吸纳更多的用户流 量，扩大所承载的用户流量份额，即提高自身相对于其它提供者的竞争能力是摆 在各提供者面前的一个十分现实的问题。本文提出了旨在提高自治域盈利的若干 竞争策略，这些策略以著名的g a o - r e x f o r d 准则为基础，根据与邻居自治域的商业 关系的不同，对宣告给邻居的路由信息中的a s 路径实施不同的修改，在保证 i n t e m e t 路由系统安全的前提下，使自治域的竞争能力得到明显的提高。 3 。对自治域流量特性进行建模分析。域间流量工程对于高效利用网络资源以 及改善用户的端到端性能不可或缺，而对自治域流量进行有效的控制必须以对流 量的产生和变化规律有一定程度的理解为前提。本文利用n e t f l o w 工具对 c h i n a n e t 骨干网的一台核心路由器进行了长达5 0 天的持续流量测量，获得了流 经该核心路由器的所有自治域的流量的实测数据，并根据该实测数据建立了一个 描述a s 流量特性的模型，以主机流量独立同分布和混合激活的假设为基础，依据 所测流量的强度和波动来推测每个自治域的视在尺寸和日常行为，刻画各自治域 对于给定路由器的实际流量产生能力以及流量变化规律，得出较为精确的流量估 计，进而应用到流量工程及异常检测中。 中文摘要 北京交通大学博士学位论文 a b s t r a c t a b s t r a c t ：t h ei n t e m e ti sc o m p o s e do ft e n so ft h o u s a n d so fs e l f - i n t e r e s e t e d d o m a i n sc a l l e da u t o n o m o u ss y s t e m s ( a s e s ) a na si sac o l l e c t i o no f r o u t e r sa n dl i n k s a d m i n i s t e r e db ya ne c o n o m i ce n t i t y , s u c ha si n t e m e ts e r v i c ep r o v i d e r , c o m p a n ya n d u n i v e r s i t i e s b o r d e rg a t e w a yp r o t o c o li st h eo n l yi n t e r - d o m a i nr o u t i n gp r o t o c o la c t u a l l y u s e dt oe x c h a n g en e t w o r kr e a c h a b i l i t yi n f o r m a t i o nb e t w e e nn e i i g h b o m ga s e s a st h e i n t e r n e th a sk e p tg r o w i n gi nt e r m so fb o t ht h es c a l e sa n dt h ea m o u n to fa p p l i c a t i o n s ， m a n yp r o b l e m se m e r g eo na sl e v e l a p p r o p r i a t es o l u t i o n sf o rt h e s ep r o b l e m sm u s tb e p r o p o s e dt oe n s u r et h eh e a l t h ya n dc o n t i n u e dd e v e l o p m e n to f t h ei n t e m e t t h i sd i s s e r t a t i o nc o v e r sas e r i e so f r e s e a r c ho np r o b l e m so f a sl e v e l ，i n c l u d e s ： 1 p r o b l e mo ff a s tb g p c o n v e r g e n c e e m p i r i c a lm e a s u r e m e n t sh a v es h o w nt h a t t h e r ec a nb ec o n s i d e r a b l ed e l a yi nb g p c o n v e r g e n c ea f t e rr o u t i n gc h a n g e s c u r r e n t s o l u t i o n se i t h e ra d de x t r al i n ks t a t ei n f o r m a t i o ni n t or o u t i n gm e s s a g e s , w h i c hi n t r o d u c e s u n a c c e p t a b l es t o r a g ec o s go rd e m o l i s ht h er o u t i n gt r e ea n dt h e nr e b u i l di t , w h i c h d e c r e a s e st h ee n d - t o - e n dc o n n e c t i v i t yp e r f o r m a n c e w ep r o p o s ean e wh e u r i s t i cm e t h o d t o s p e e du pb g pc o n v e r g e n c eb ys l i g h t l ym o d i f y i n gb g pr u l e so fw h e nt os e n d w i t h d r a w a l sa n dw h e nt os e n da n n o u n c e m e n t s m o r e o v e r , i tu s e sm o d e r a t ep r o b ec o s tt o r e p l a c et h ea g g r e s s i v ed i s s e m i n a t i o no fw i t h d r a w a l sa n dc a na c h i e v ef a s tb g p c o n v e r g e n c ew i t hal i t t l em e m o r ya n dc o m m u n i c a t i o no v e r h e d 2 p r o b l e mo ft r a f f i cc o m p e t i t i o n sb e t w e e na s e s i nt o d a y sc o m m e r c i a li u t e r o o t , a na s e sa c t sa se i t h e rap r o v i e ro rac u s t o m e r h o wt oa t t r a c tm o r et r a f f i cf r o mo n e s c u s t o m e r st og e tm o r em a 妇s h a r ea n df i n a n c i a lg a i n si sav e r yp r a c t i c a lp r o b l e mf o r e a c hp r o v i d e sw ee x p l o r ep o s s i b l es t r a t e g i e st oe n h a n c ec o m p e t i t i o ns t r e n g t ho fa s a g a i n s to t h e rr i v a l sb yf o r g i n ga sp a t hi nr o u t e sa d v e r t i s e dt on e i g h b o r s o u rs t r a t e g i e s c a p i t a l i z eo nt h ef a m o u sg a o - r e x f o r dc o n s t r a i n t sa n dh a v eg r e a tp r a c t i c a lv a l u ew i t h o u t v i o l a t i n gi n t e r o e tr o u t i n gs a f e t y 3 p r o b l e mo fa st r a f f i c c h a r a c t e r i z i n ga n dm o d e l i n g i n t e r - d o m a i nt r a f f i c e n g i n e e r i n gi sv i t a l l yi m p o r t a n tf o rh i g he f f i c i e n c yu t i l i z a t i o no f n e t w o r kr e s o u r c ea n d e n h a n c e m e n to fe n d - t o - e n dp e r f o r m a n c eo fh o g si nd i f f e r e n ta s e s t oe f f e c t i v e l y c o n t r o la st r a f f i c ，w em u s tu n d e r s t a n dc e r t a i np r i n c i p l e so fa st r a f f i cg e n e r a t i o na n d c h a n g e w eu s en e t f l o wt o o l st om e a s u r et h et r a f f i co fac o r er o u t e ri nc h i n a n e t b a c k b o n ef o rap e r i o do f 5 0d a y sa n dp r o p o s eam o d e lt od e p i c ta sl e v e li n t e r o e tb a s e d a b s t r a c t o nt h em e a s u r e dd a t a o u rg o a li st oi n f e rt h ev i s u a ls i z ea n dd a i l yb e h a v i o ro f e a e ha s t h r o l l g ht h ei n t e n s i t ya n df l u c t u a t i o no ft h eo b s e r v e d 缸墨f f i c b a s c do nt h e8 s s u m p t i o n t l l a te a c ha sc o n s i s t so fi n d e p e n d e n th o s t sw i t ht h es a m en 谢i i ce m i s s i o nb e h a v i o ra n d f o l l o w sam i x e da c t i v a t i o nm e c h a n i s m ，o u rm o d e if i t st h em e a s u r e dd a t aq u i t ew e l la n d i ss i m p l ee n o u 曲t ob eu s e di nt r a f f i ce n g i n e e r i n ga n dt r a f f i ca n o m a l i e sd e t e c t i o n k e y w o r d s ：a u t o n o m o u ss y s t e m ；b o r d e rg a t e w a yp r o t o c o l ：f a s tr o u t e c o n v e r g e n c e ；c o m p e t i t i o n ：i n t e r - d o m a i nt i _ a f f i ce n g i n e e r i n g ；r o u t ep o l i c y c l a s s n o ：t p l 9 3 北京交通大学博士学位论文 图2 1 图2 2 图2 - 3 图3 1 图3 2 图3 - 3 图3 - 4 图3 - 5 图3 - 6 图3 7 图3 8 图3 - 9 图3 - 1 0 图3 1 l 图3 - 1 2 图3 一1 3 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图5 1 图5 2 图5 - 3 图5 - 4 图5 5 图5 - 6 图5 7 图表清单 b g p 路由器的操作过程1 2 a s 注释图示例1 7 从源s 到目的d 的合理和不合理a s 路径1 8 全连通网络路由收敛过程示意图2 3 b g p - g f 缺点的一个简单示例2 6 瞬时环路构建示意图3 0 标准b g p 、n d p r 和b g p - g f 对于连续宣告消息的处理差异3 2 a l p 在故障中断情况下的示例3 3 故障转移示意图3 5 a l p 在故障转移情况下的示例3 6 a l p 实现的伪代码3 7 尺寸为4 的全连通拓扑故障中断和故障转移情形示例3 9 全连通拓扑故障中断情况下的收敛时间以及消息复杂度4 0 全连通拓扑故障转移情况下的收敛时间以及消息复杂度4 0 b a 拓扑故障中断情况下的收敛时间以及消息复杂度4 1 b a 拓扑故障转移情况下的收敛时间以及消息复杂度4 l 本章使用的一个a s 注释图4 6 网络前缀劫持示例4 8 a s 路径预先计划示例4 9 提供者间的竞争5 0 a s 路径毒化示例5 3 实施网络前缀劫持之前和之后各提供者所服务的o d 对的数量对比5 7 提供者收益增幅的累计分布5 7 预先计划有效a s 的分布5 8 采集点位置示意图6 4 a s 4 8 0 8 、a s 7 4 6 7 和a s 2 9 1 4 持续5 0 天的流量6 5 a s 4 8 0 8 、a s 7 4 6 7 和a s 2 9 1 4 流量的傅氏变换( f f t ) 6 6 a s 4 8 0 8 、a s 7 4 6 7 和a s 2 9 1 4 的m v 图。6 9 a s 流量特性变化轨迹的活动区域7 2 a s 视在尺寸与a s 流量尺寸的相对差异7 6 a s 视在尺寸与a s 宣告尺寸的相对差异。7 6 旦墨塑苎 图5 8 a s 4 8 0 8 的流量均值以及激活参数在一天之内的变化情况7 7 图5 - 9 和p 的极值分布7 8 表4 - 1 a s 类别的分布情况。5 6 表5 - 1 每类a s 的个数和占总流量的百分比7 4 北京变通大学博士学位论文 缩略语 a l p ( a n t i l a m pp r o b i n g ) 破环探测 a s ( a u t o n o m o u ss y s t e m ) 自治域 a s p p ( a sp a t hp r c p e n d i n g ) a s 路径预先计划 b g p ( b o r d e r g a t e w a yp r o t o c 0 1 ) 边界网关协议 c a i d a ( c o o p e r a t i v ea s s o c i a t i o n 蠡”i n t e r a c td a t aa n a l y s i 曲互联网数据分析协作组 织 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 ) 无类别域问路由 c t i ( c o u n t - t o - i n f i n i t y ) 计数至无穷 e b g p ( e x t e r n a lb g p ) 外部边界网关协议 e g p ( e x t e r i o rg a t e w a yp r o t o c 0 1 ) 外部网关协议 l a b ( i n t e r a c t a r c h i t e c t u r a lb o a r d ) i n t e m e t 体系结构委员会 i b g p ( i n t e r n a lb g p ) 内部边界网关协议 i g p 0 n l e r i o rg a t e w a yp r o t o c 0 1 ) 内部网关协议 i g r p ( i 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 0 1 ) 内部网关路由协议 i p ( i n t e m e tp r o t o c 0 1 ) 网际层协议 i p p ( i n t e m e tp e e r i n gp o i n t ) i n t e m e t 对等点 i s p ( n t e m e ts e r v i c ep r o v i d e r ) i n t e m e t 服务提供者 i x p ( i n t e m e te x c h a n g ep o i n t ) i n t e r a c t 交换点 l s p ( l a b e ls w i t c hp a t h ) 标签交换路径 m o a s ( m u l t i p l eo r i g i na s ) 自治域多源 m p l s ( m u l t i - p r o t o c o ll a b e ls w i t c h i n g ) 多协议标签交换 m r a i ( m i nr o u t ea d v e r t i s e m e n ti n t e r v a l ) 最短路由宣告间隔 n a p ( n e t w o r ka c c e s sp o i n t ) 网络接入点 n d p r ( n o n d e l a yp o i s o nr e v e r s e ) 无拖延反向毒化 o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 开放式最短路径优先 p e ( p a t he x p l o r a t i o n ) 路径探索 p h ( p r e f i xh u a c k i n 西网络前缀劫持 p o p ( p o i n to f p r e s e n c e ) 呈现点 p r ( p o i s o nr e v e r s e ) 反向毒化 r c n ( r o o tc a u s en o d e ) 根原因节点， r f d ( r o u t ef l a pd a m p i n g ) 路由抖动阻尼 缩略语 r i p ( r o u t ei n f o r m a t i o np r o t o c 0 1 ) 路由信息协议 r p ( r o u t ep o i s o n i n g ) 路由毒化 s h ( s p l i th o r i z o n ) 水平分割 s p v p ( s i m p l ep a t hv e c t o rp r o t o c 0 1 ) 简单路径矢量协议 t c p ( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 传输控制协议 t e ( t r a f f i ce n g i n e e r i n g ) 流量工程 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：娄、& 签字日期：2 姗1 年j 2 月坫日 撇名：? 售韦誊 签字日期：墙，2 月习自 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：枢签字日期： 2 d 。1 年f 2 月时日 致谢 在这篇学位论文完成之际，首先要向我的恩师陈常嘉教授致以最诚挚的感谢， 是陈老师引领我进入科学研究这块看似枯燥但实际上魅力无限的领域，在我攻读 博士学位期间所进行的各项科研工作都凝聚着陈老师的心血和汗水。本文中的许 多思想都源自我和陈老师富有成果的讨论，陈老师对问题的独到见解不仅扩宽了 我的思路，更加深了我对所作研究课题的理解。陈老师严谨的治学态度、渊博的 学识、敏捷的思维、忘我的工作热情和正直坦荡的人格魅力，都给我留下了深刻 的印象，成为我一生治学、做人的榜样。 感谢通信工程实验室的所有老师，特别要感谢胡师舜老师对我学习和生活上 的帮助和支持。 感谢赵永祥博士、郭宇春博士、张云飞博士、宋光农博士、张立军博士、郑 红云博士和刘紫千博士，与他们经常性的讨论和交流对我论文中很多思想的形成 和完善都有重要的启发意义。 最后，我要深深感谢我的父母，感谢他们多年来对我的养育之恩，对我无私 的爱以及我学习和生活上无微不至的关心和照顾，成为我完成博士阶段学习的强 有力支持。 北京变通大学博士学位论文 1 1 引言 第1 章绪论 在过去短短十几年中，i n t e r n e t 迅速发展成为现代通信架构中至关重要的一部 分。它成功地将诸多异构网络连接起来，因此享有万网之网的美誉【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 1 。而相邻自治域间按照域问路由协议【3 1 交换路由信息， 实现跨域主机间的可达。边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，b g p ) 是唯一正在 使用的域间路由协议，它与自治域一道构成了i n t e r a c t 事实上的筋与骨。 因此，i n t e r a c t 实际上是按照路由器层和自治域层的双层路由体制来进行流量 转发的。在路由器层面上，各路由器按照通力协作、尽力而为1 4 j 的方式完成端到端 的流量传输需求，而当上升到自治域层面时，所完成的工作和面临的问题却要复 杂得多。可以说，域问问题并不是域内问题的简单延拓一方面，自治域之间是 合作的关系，为了提高跨域间主机的端到端连通性能，域问路由快速收敛以及流 量工程等问题必须得到妥善解决；而另一方面，自治域之间又是竞争的关系，作 为彼此相对独立的经济体，经济因素对各自治域的具体行为有着不可忽略的影响， 如何在保证i n t e m e t 路由系统安全的前提下提高自身竞争力也是摆在各自治域面前 的一个十分现实的问题。本文的研究就着眼于这两方面，对相关问题进行深入探 讨，并给出相应的解决方案，为i n t e m e t 的持续健康发展贡献我们的智力。 1 2 本文的主要贡献 本文的主要贡献包括以下三项工作： 1 研究了b g p 路由的快速收敛问题。b g p 在网络发生故障后的收敛速度并不 理想，依靠在路由消息中附加链路状态信息的方法虽然能够达到快速收敛的目的， 但却引入了高昂的存储代价，而采用先将路由树拆除再重新建立的方法也大大降 低了末端a s 的连通性能。本文提出了新的加速b g p 收敛的方法，该方法对路由 消息的发送规则做了新的改进，放弃了向所有邻居广播撤销消息的做法，转而通 第1 章绪论 过弓i 入适当的探测代价，既避免了不必要的撤销消息的发送，又能保证路径探索 过程快速进行，在仅需要花费少量存储代价及通信代价的前提下，最终实现b g p 快速收敛。 2 研究了自治域间的流量竞争问题。在i n t e r a c t 商业化运作模式下，各自治域 扮演着提供者( p r o v i d e r ) 和用户( c u s t o m e r ) 等不同角色，而如何吸纳更多的用户流 量，扩大所承载的用户流量份额，即提高自身相对于其它提供者的竞争能力是摆 在各提供者面前的一个十分现实的问题。本文提出了旨在提高自治域盈利的若干 竞争策略。这些镱略以著名的g a o - r e x f o r d 准则唧为基础，根据与邻居自治域的商 业关系的不同，对宣告给邻居的路由信息中的a s 路径实施不同的修改，在保证 i n t e m e t 路由系统安全的前提下，使自治域的竞争能力得到明显的提高。 3 对自治域流量特性进行建模分析。域间流量工程对于高效利用网络资源以 及改善用户的端到端性能不可或缺，而对自治域流量进行有效的控制必须以对流 量的产生和变化规律有一定程度的理解为前提。本文利用n c t f l o w 工具 6 】对 c h i n a n e t i 。7 1 骨干网的一台核心路由器进行了长达5 0 天的持续流量测量，获得了 流经该核心路由器的所有自治域的流量的实测数据，并根据该实测数据建立了一 个描述a s 流量特性的模型，以主机流量独立同分布和混合激活的假设为基础依 据所测流量的强度和波动来推测每个自治域的视在尺寸和日常行为，刻画各自治 域对于给定路由器的实际流量产生能力以及流量变化规律，得出较为精确的流量 估计，进而应用到流量工程及异常检测中。 1 3 本文的结构安排 论文的余下部分安排如下： 第2 章主要介绍与本文研究工作相关的背景知识。首先从结构和路由两个方 面简要概述了i n t e m c t 的发展及现状。然后，着重介绍了边界网关协议( b g n 的特 点，运作机理、面临的问题和研究热点。随后，介绍了关于自治域拓扑的特征和 构建模型，自治域问商业关系引入之后引发的商业关系推断工作。最后，简单介 绍了b g p 相关测量分析以及仿真工作现状。 第3 章讨论b g p 路由快速收敛问题。酋先探讨b g p 收敛馒的根本原因及对现 有解决方案的分析比较，并给出我们工作的基本思想。然后介绍与本章工作相关 的简单路径矢量协议模型，并给出与b g p 收敛相关的定义。随后提出了利用无拖 延反向毒化及破环探测加速b g p 收敛的方法，讨论了该方法的两个组成部分以及 具体实现。最后给出仿真设置和结果。 北京变通大学博士学位论文 第4 章讨论自治域问的竞争问题首先指出a s 闻存在竞争的事实及其原因。 然后介绍与我们的工作相关的背景知识。随后提出一套既能增强a s 竞争能力又不 会破环i n t e m e t 路由系统安全的竞争策略。最后在一个实际的i n t e m e t 拓扑上对该 套竞争策略的有效性进行评估，分析评估时发现的各种现象。 第5 章讨论自治域流量建模问题。首先阐述了自治域流量特性建模的意义。 然后介绍本章工作的相关的测量平台及测量数据。随后提出刻画a s 流量特性的模 型，并根据测量数据匹配模型中的参数。最后给出实验验证及数字结果。 最后的结论总结全文，指出现有研究工作中存在的问题和不足，以及今后可 能的研究方向和内容。 北京交通大学博士学位论文 第2 章研究背景 本章主要介绍与本文研究工作相关的背景知识。首先从结构和路由两个方面 简要概述了i n t e r a c t 的发展及现状。然后，着重介绍了边界网关协议g p ) 的特点， 运作机理，面临的问题和研究热点。随后，介绍了关于自治域拓扑的特征和构建 模型，自治域间商业关系引入之后引发的商业关系推断工作。最后，简单介绍了 b g p 相关测量分析以及仿真工作现状。 2 1i n t e r n e t 发展与应用现状 2 1 1i n t e m e t 结构 i n t e r a c t 仅用了短短十几年的时间就从根本上改变了世界的信息基础设施，作 为覆盖全球的计算机网络系统，在社会信息化的过程中扮演着不可替代的角色。 随着i n t e m e t 规模的不断扩大，其结构也发生了彻底的改变，由最初的单个分组交 换n ( a r p a n e t ) 发展成为具有多级结构的网络集合体f s j ，由众多以t c p i p 协议框 架为基础但又相互独立，受不同所有者管理的网络组成，形成局域、城域、广域、 国家骨干，跨国等不同层次。i n t e r n e t 商业化以后，以提供i n t e r n e t 接入服务为业 务的i n t e m e t 服务提供者( i n t e m e ts e r v i c ep r o v i d e r , i s p ) 纷纷出现。这些i s p 将其运 营的服务提供者网络( s e r v i c ep r o v i d e rn e t w o r k ) 通过横向和纵向两种方式彼此互 连，并依照相互之间达成的数据交换协定实现i n t e r n e t 的端到端连接。 在横向上，若干规模相当的i s p 通过i n t e r a c t 交换点( i n t e m e te x c h a n g ep o i n t ， i x p ) 将彼此的骨t - n 络直接连接在一起，由高性能的交换设施( 如a t i v l 交换机) 实 现高速数据交换。i x p 又称作网络接入点( n e t w o r ka c c e s sp o i n t , n a p ) 或者i n t e m e t 对等点( i n t e r n e tp e e r i n gp o i n t ，i p p ) 。这三者没有严格统一的界定，但一般来说，n a p 特指i n t e r n e t 商业化之初由4 家美国电信公司分别运营的4 个到n s f n e t 骨干网的 接入点，是最高级别的i n t e m e t 交换点。因此，i x p 较n a p 有更为广阔的外延。 它们的共同点是包含对等( p e e r i n g ) 的思想，这意味着在i x p n a p 上交换流量的双 方是互不收费的。 在纵向上，上级i s p 用呈现点( p o i n to f p r e s e n c e ，lo p ) 的方式向下级i s p ，末端 用户网络( 校园网，企业网) 甚至个人提供i n t e r a c t 的接入服务。用户通过把接入设 第2 章研究背景 备放在i s p 的p o p 处或者直接通过接入线实现与i s p ，继而是整个i n t e m e t 的连接， 并且为这种接入服务支付费用。具体数额由双方协商决定，一般采用接入带宽租 赁或者按照流量( 字节数) 收费。上级i s p 与下级i s p 或末端用户网络进行网间结算 时，控制权掌握在上级i s p 手中 9 1 。 显然，i x p 和p o p 在数据传输成本上存在巨大反差，诸多i s p 在利益的驱使 下竭尽全力寻找适当的合作伙伴( g t 方的数据交换量基本相当) ，建立对等关系。 i n t e m e t 从转入商业化运营的那一天起至今一直承受着巨大的商业压力，这种压力 使得i n t e m e t 逐渐转交成一个在各个级别都丰富直连( r i c hm e s h ) 的网络【1 0 j 。如今， 全世界已经有数百个i x p 【l ”，而且这一数量还在不断增加。对于i n t e r n e t 的结构， 也很难再给出较为细致的描述。 2 1 2i n t e m e t 路由 i n t e m e t 是由众多i p 子网通过路由器互连构成的国际性网络，路由一直是 i n t e r a c t 最重要的支撑，受到网络运营和研发的高度重视。路由的功能包括三个方 面，即路由信息的收集、选择和更新。路由信息的收集和更新是通过各种状态信 息的交换机制实现的，而选路则是使用路由算法实现的。路由协议是对路由信息 的交换和选路法则的规范，路由器按照路由协议与相邻路由器交换路由信息，更 新维护动态路由表使之正确反映网络拓扑结构的变化。 2 1 2 1i n t e r n e t 路由演化 i n t e m e t 路由技术的发展是一个在实践中逐步演化的过程，主要表现在下面两 个方面。 1 ) 从使用动态度量参数到使用静态度量参数 在i n t e m e t 发展的最初阶段( a p r a n e t ) ，路由器节点测量当前链路上的状态参 数( 主要是时延) ，并根据测量结果计算出最短时延路径来确定路由【l2 】。这种方法有 个明显的缺点，网络时延往往与链路负载相关。如果网络中的所有业务分组都使 用负载较轻的链路，这些链路就会因此而变得拥挤，造成时延增加，后续的分组 就可能选择另外的路径，这就形成了路由振荡，导致网络资源利用效率低下。为 了解决这一问题，i n t e r n e t 路由转为使用其它度量参数，主要是静态度量参数，如 “跳数”等【l3 1 。静态参数的使用使得网络流量不至于发生剧烈的振荡，但同样也 导致网络资源利用效率低下的问题。由于静态度量参数无法反映网络负载情况， 6 北京交通大学博士学位论文 所以容易造成网络各部分的负载不均。 2 ) 自治域概念的引入和双层路由体制的确立 i n t e r a c t 的规模和膨胀速度是最初的设计者始料不及的，因此引发了两方面的 问题。一方面，如此庞大的规模对i n t c r n e t 路由的可扩展性提出严峻挑战，让i n t e m e t 的所有路由器都遵循相同的路由协议是不可能的另一方面，i n t e r a c t 是一个松散 的网络联合，每个所有者都有对自己网络的路由进行自治控制的需求。i n t e m e t 因 此产生了自治域( a u t o n o m o u ss y s t e m ，a s ) 的概念。a s 是受同一部门管理，具有同 一路由选择策略的若干网络和路由器的集合。每个a s 由一个双字节编号标识，该 编号由i n t e r n e t 授权的管理机构来指定【1 4 】。网络管理者可以自主设置在自己域内使 用的路由法则，但各个a s 必须共同遵循某一域问路由协议，实现跨域的端到端连 接。i n t e r a c t 双层路由体制因此确立。并沿用至今。 2 1 2 2 路由算法 目前i n t e r a c t 使用的路由算法，主要是基于1 9 5 9 年提出的d i j k s t r a 算法【”1 和 1 9 6 2 年提出的b e l l m a n f o r d 算法l 嘲i l 等理论研究成果。它们都属于最短路径算法， 用于求解网络中两个节点之间的某项指标( 如时延、丢失率、可用带宽等) 的最优路 径。这些学术成果的协议实现使得大规模信息网络建设取得了巨大的成功。d i j k s t r a 算法用于求解以信源为根，到网络中所有其它节点的最短路所组成的最短路径树。 算法的思路是在每次迭代的过程中，都从当前不在树上的节点中选择距离树最近 的节点加入，同时更改其余节点到树的距离，这样逐次进行，直到所有节点都在 树上为止。b e l l m a n f o r d 算法能求出信源到信宿在不同跳数范围内的最短路径。采 用的方法是逐次逼近，第埘次逼近求出跳数在册内的最短路假设网络中共有n 个节点，则进行到第h 1 次时算法停止。 2 1 2 3 路由协议 按照双层路由体制，自治域内由各管理者自行决定采用何种路由协议，而自 治域间需要运行同一路由协议。外部网关协议( e x t e r i o rg a t e w a yp r o t o c o l ，e g p ) 是最 早为自治域问交换路由信息而设计的路由协议，因此，又把运行于自治域内的各 种路由协议统称内部网关协议( i n t e r i o rg a t e w a yp r o t o c o l ，i g p ) 。随着i n t e r n e t 的发 展，e g p 早已退出历史舞台，目前实际使用的域问路由协议是边界网关协议( b o r d e r g a t e w a yp r o t o c o l ，b g p ) ，作为本文的重点，将另开小节予以介绍。因此，本节仅 简要介绍内部网关协议，它可以分为以下两类： 第2 章研究背景 1 ) 距离矢量协议 距离矢量协议利用b e l l m a n f o r d 算法计算到达目的网络的最短路径。路由器 仅与相邻节点交换路由信息，信息仅包含到达目的网络的度量值和下一跳节点。 每次收到来自邻居节点的路由信息后，路由器就重新计算最优路径，如果最优路 径发生改变，则更新路由表，并将新选择通知所有邻居节点。经过有限次这样的 迭代之后，所有路由器都稳定在自己当前的路径选择上，不会再产生新的路由消 息。 距离矢量协议的路由选择完全依赖于从邻居节点获得的信息，这种递增式的 交互方式虽然能够保证路由收敛，但是收敛速度十分缓慢。由于节点问交互的信 息十分简陋，当拓扑发生改变时，节点本身缺乏对错误信息的识别能力。因此对 好消息( 例如节点j a ) 反映迅速，但对坏消息( 例如节点退出) 则反应迟钝，主要表 现为计数至无穷问题( c o u n t - t o - i n f i n i t y ) 。水平分害l j ( s p l i th o r i z o n ) 是针对计数至无穷 问题提出的一个解决方案，它要求路由器不要把当前所选最优路回送给告知这条 路径的邻居路由器。在实际操作中，路由器往往回送给这个邻居路由器一个不可 达信息，这称作反向毒化( p o i s o nr e v e r s e ) 。然而，水平分割和反向毒化并不能完全 解决计数至无穷问题。在某些情况下，该问题依然存在。 路由信息协议( r o u t ei n f o r m a t i o np r o t o c o l ，r 1 p ) 是距离矢量协议的一个经典实 例，它十分简单，易于配置和维护，适合在有极少的冗余路径和对网络性能要求 不高的小型网络中使用。针对计数至无穷问题，r i p 采用跳数1 6 代表节点不可达， 并采用触发更新( t r i g g e r e du p d a t e ) 的方式迅速散播路由更新消息，从而缩短了计数 至无穷所需的时间，但是这也引发了路由消息的泛滥，同时限制了使用r i p 的网 络的规模。 2 ) 链路状态协议 与距离矢量协议的递增分布式计算不同，链路状态协议采用一种冗余分布的 方式交换路南信息。一个路由器的链路状态指的是该路由器有哪些邻居节点，以 及与这些邻居节点棚关的一些度量参数。每个路由器都要将自己的链路状态泛洪 至全网所有节点，因此，每个路由器都能够获得一张关于当前