（通信与信息系统专业论文）覆盖网络的路由发现策略研究.pdf

中山大学硕士学位论文 覆盖网络的路由发现策略研究 专业：通信与信息系统 硕士生：陈长怡 导师：周渊平教授倪江群教授 摘要 在i n t e r n e t 中，从一个用户到另一个用户的数据传输服务常常要穿越多个自 治域。而在“尽力而为”的情况下，许多网络应用难以部署和扩展。覆盖网络正 是在这种情况下诞生的。覆盖网络技术不需要大规模改变现有网络架构就能提供 更为可靠、容错性更好的服务。本文使用弹性覆盖网( r e s i l i e n to v e r l a yn e t w o r k ， r o n ) 作为研究平台。 本文首先对r o n 的系统模型作了一个整体介绍，理清r o n 的各个功能模 块，介绍了路由发现策略，h e l l o 协议，泛洪协议，s p a n d ，讨论了r o n 中的周 期泛洪路由发现策略。r o n 所使用的路由发现探测包引入了不可忽视网络开销， 并限制了r o n 网络规模的扩展，对此本文提出了r o n 的路由发现策略改进， 采取按需随机探测的路由发现策略。并且在r o n 上构建了v o i c eq o s 敏感的 o n e w a y - d e l a y 的路由度量。 本文在o p n e t 上建立了r o n 终端模型和r o n 网络拓扑，在验证了模型功 能的正确性之后，对r o n 的周期泛洪路由发现策略和按需随机探测路由发现策 略进行仿真并比较结果，仿真表明了按需随机探测减少了探测包的网络开销，并 且探测包网络开销的减小改善了数据包的o n e w a y - d e l a y 。 关键词：弹性覆盖网，周期泛洪路由发现，按需随机路由发现，o p n e t 建模 中山大学硕士学位论文 r o u t i n g s c h e m eo ho v e r l a yn e t w o r k s m a j o r - c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m n a m e ：c h e nc h a n g y i s u p e r v i s o r ：p r o f e s s o rz h o uy u a n p i n g p r o f e s s o rn ij i a n g q u n a b s t r a c t ht o d a y si n t e m e t , d a t at r a n s f e r r i n gf r o mo n ec l i e n tt oa n o t h e rc l i e n th a st o t r a v e r s ea c r o s sm a n ya s e s ( a u t o n o m o u ss y s t e m s ) m a n ye n d - t o - e n da p p l i c a t i o n s , s u c hf i t sq o s ，a r eh a r dt od e p l o yl a c ko ft h es u p p o r to ft h ei s p s t h eo v 盯l a y n e t w o r k sc a ns o l v et h e s ep r o b l e m s i nt h i st h e s i s r e s i l i e n to v 盯l a yn e t w o r k ( r o s ) i ss t u d i e d r o nc a nd e t e c tt h e p a t hf a i l u r er a p i d l ya n ds e l e c ta n o t h e rp a t ht ot r a n s f e rt h ed a t a r o nu s ep e r i o d i c f l o o d i n gr o u t i n g s c h e m et op r o b et h ep a t h a g g r e s s i v e l y , b u t t h i si n t r o d u c e s n o n - n e g l i g i b l en e t w o r ko v e r h e a dw h i c hw i l lb e c o m eas i g n i f i c a n tp a r to ft h et o t a l n e t w o r kb a f f i c i nt h i s t h e s i s ，a l lo n - d e m a n dr a n d o m i z e dm u t m gs c h e m ei s p r o p o s e d , a n db u i l dt h er o u t i n gm e t r i c ：o n e - w a y - d e l a y , w h i c hv o i c eq o s s e n s e sm o r e t h e nt h er o nd e f a u l tm e t r i c ：r t t a n dr o nn e t w o r km o d e li sb u i l to n0 n 0 e ，r d o s i m u l a t i o n sf o re a c hm u t i n gs c h e m ea n df i n do u tt h eo n - d e m a n dr a n d o m i z e dm u t i n g s c h e m ei n t r o d u c e sl e s so v e r h e a da n dl e a d st ol e s sd a t a 协m s f e r r i i l go n - w h i d a y k e y w o r d s ：r e s i l i e n to v e r l a yn e t w o r k , p e r i o d i cf l o o d i n gr o u t i n gs c h e m e , o n - d e m a n d r a n d o m i z e dr o u t i n gs c h e m e , o p n e tm o d e l i n g 1 1 i 中山大学硕士学位论文 1 1 研究背景 1 1 1 覆盖网络的出现 第1 章绪论 n t e r n e t 是由很多自治域( a u t o n o m o u ss y s t e m s ，a s ) 组成的。自治域在传 统意义上是指拥有相同的选路策略、处于一个管理机构控制下的路由器和网络的 集合。在这样的架构里，具体的路由信息仅保存在a s 和它所属的网络中而每 个a s 一般由某个网络服务提供商( 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 和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 - 4 ) 动态交换路由 信息。但因路由信息被b g p - 4 严重过滤和高度汇聚，因此网络的高度扩展性是 以端到端通信的可靠性降低为代价的。当今的i n t e r n e t 架构仅支持“尽力而为 ( b e s te f f o r t ) ”型的连接服务，从一个用户到另一个用户的数据传输服务常常要 穿越多个自治域。而在“尽力而为”的情况下，许多网络应用如端到端q o s 、i p 组播等由于无法得到网络服务提供商的大力支持而难以部署和扩展。 覆盖网络正是在这种情况下诞生的。覆盖网络( o v e r l a yn e t w o r k ) 是建立在 现有网络基础上独立的虚拟网络，由一系列分布于i n t e m e t 各自治域内部的覆盖 服务节点以及连接它们的逻辑链路所组成，它能有效地利用i n t e r n e t 给终端用户 提供更为可靠的服务。覆盖网示意图如图1 1 所示。 图1 - 1 覆盖网示意图 第1 章绪论 覆盖节点通常具有路由，数据处理和数据保存等功能，而逻辑链路( 即覆盖 链路) 通常对应底层一条或多条物理路径，对数据进行传输。利用覆盖网络技术， 不需要大规模改变现有网络架构就能提供更为可靠、容错性更好的服务，可以方 便地通过针对特定应用的覆盖网络提供在现有网络层基础结构中难以提供的新 业务，通过采用更好地利用网络资源信息的算法来提高现有i n t e r n e t 已有的业务 性能。有了覆盖网络，即使网络出现错误，应用系统也可以凭借覆盖网络快速找 到替代路由，并且可以根据应用服务的不同服务质量要求寻找相应得最优路径。 1 1 2 覆盖网络的应用 覆盖网络的应用很多，典型应用有：虚拟个人网络( v p n ) 、应用层多播、 p 2 p 文件共享、服务覆盖网( s o n ) 虚拟个人网络( ，n ) 可以帮助远程用户、公司分支机构、商业伙伴及供应 商公司的内部网建立可信的安全连接，并保证数据的安全传输v p n 的技术原 理是在企业内部建立i n t e m e t 接入点、部署内容服务器节点，在这些节点的基础 上组成一个覆盖网络，并利用一种特殊的隧道机制将网站发布的内容数据流转移 到低成本的网络上。 覆盖网技术的提出，使在应用层实现多播成为可能。应用层多播的思想是由 端系统而不是核心路由器实现多播通信的所有功能，其最大的优势在于无须改变 现有的口网络，可灵活部署。 利用覆盖网实现的p 2 p 文件共享机制比存在中央服务器的n a p s t e r ，g n u t e l l a 和p v r 文件共享模型更具优势。非中心化、网络资源分散在所有节点，无需中 间环节和服务器的特点，避免了可能的瓶颈，随之带来其在可扩展性、健壮性等 方面的优势，并且更好地实现了整个网络的负载均衡。 服务覆盖网( s e r v i o eo v e r l a y n e t w o r k ，s o n ) 有效地解决了困扰当今i n t e r n e t 的端到端q o s 问题，同时便于创造和部署增值型i n t e m e t 服务，如m 、v o d 和其它的q o s 敏感型服务。s o n 通过与各个i s p 达成服务水平协议( s e r v i c e l e v e l a g r e e m e n t ，s l a ) 购买一定q o s 保障的带宽，从而在现有的数据传输网络顶层 建立起一条端到端的逻辑服务传输通道。用户通过s l a 直接向s o n 的i s p 申请 2 中山大学硕士学位论文 s o n 增值服务，并交纳服务费用。 1 2 国内外研究现状 1 2 1 覆盖网络通用平台研究 目前，大部分对覆盖网的研究都是针对特定应用的，比如c h o r d 2 1 ，b r o c a d d n 和t a p c s 垆等都是为基于良好定义架构的( w e l l - d e f i n e d - s t r u c t u r e - b a s e d ) 应用而 设计的，它们的主要且标是在一个大的分布式系统中对内容进行迅速的定位，而 文【5 】【6 】则是针对基于覆盖网的应用层组播的研究。这些研究者都提出了基于某 种应用的覆盖架构。随着覆盖网络应用的增多，出现了通用覆盖服务网的概念， 它能对已有的和将来的覆盖应用提供支持。当前对此的研究主要有覆盖服务网络 ( o v e r l a ys e r v i c en e t w o r k ，o s n ) r 7 l ，覆盖应用服务网络( o v e r l a yu t i l i t ys 目v i c e ， o p u s ) 嗍，q o s 保证的覆盖网络( o v e r l a yn e t w o r ko f f e r i n gq o s ，o v e r q o s ) 【9 ，1 0 1 以及s o n l l i j 2 l 等 o s n 可以为各种覆盖服务提供资源分配和协商，路由、拓扑发现等服务支 持，特别适用于对q o s 敏感的覆盖应用服务。o p u s 是一个提供q o s 保证的大范 围覆盖应用服务网络平台，它能同时为多个分布式应用提供必要的服务。o p u s 能同时满足应用的性能和可靠性要求，并且能够扩展到数千个参与节点。 o v 岛q o s 是一个利用覆盖网为i n t e r a c t 提供服务质量保证的架构o v e r q o s 提出 了丢包控制虚拟链路( c o n t r o l l e dl o s sv i r t u a ll i n k ，c l v l ) 的概念，通过在数据流 中加入冗余数据包来实现丢包控制，能提供比传统i n t e r n c t 的“尽力而为”更好 的服务。o v e r q o s 将不同的q o s 要求的服务数据流分类，将相同q o s 要求的服 务数据流汇聚成一“柬”。s o n 主要关注的是在满足q o s 和流量要求的基础上如 何尽量减少带宽花费。 1 2 2 覆盖网络的底层网络支持研究 如果在底层网络中加入一些支持功能，那么由此建立起来的覆盖网将会更为 3 第1 章绪论 高效文献【1 3 】介绍了一种叫p a c k e tr e f l e c t i o n 的网络层支持覆盖网的技术，使 用这种技术可以使内容的发布更为有效，降低网络带宽的消耗。在其支持下，用 户可以给邻近路由器发送请求，把数据的复制转发交给邻近的路由器完成，使得 内容发布占用的带宽最小化这种技术并不需要全部路由器支持，只需要在适当 路由器中加入此技术就可以达到目的，并没有违反避免对底层网路做太大改动的 初衷。即使只有一个路由器支持这个技术，也能马上就能提高带宽利用率，有效 提升响应时间 1 2 3 覆盖网络的安全研究 和传统的i n t e m e t - - 样，覆盖网络也容易受到各种恶意攻击。拒绝服务( d e n i a l o f s e r v i c e , d o s ) 攻击是覆盖网络安全的主要威胁。以前防止d o s 攻击的方法是 被动的，即等有攻击产生了，网络才会启动保护机制，这难以防止使用复杂伪装 技术的攻击。 文献 1 4 】提出了一个安全覆盖服务( s e c u r eo v e r l a ys e r v i c e s ，s o s ) 网络架 构可以主动预防d o s 攻击。s o s 架构采用了安全覆盖隧道、相容哈希和过滤等 技术。它在“边缘”网络使用高强度的过滤保护，将d o s 攻击推向核心网络， 核心网络的高速路由器可以处理大量攻击流量使得攻击难以成功。s o s 还引入了 匿名机制和随机机制，使攻击者难以针对某个特定的目标进行攻击。 1 2 4 覆盖网络的拓扑研究 不同的覆盖网络拓扑结构对覆盖网络的性能有很大的影响。即假定覆盖节点 都已选定，探讨如何在这些节点之间建立覆盖链路( o v e r l a yl i n k s ) ，以更加有 效地支持提供各种覆盖应用。不同的拓扑结构往往被称为不同的覆盖服务网络， 主要有以下几种：弹性覆盖网( r e s i l i e n t o v e r l a y n e t w o r k ，r o n ) ，s o n ，q o s - a w a r e m u t i n gf o ro v e r l a y n e t w o r k ( q r o n ) ，o v e r q o s 等。这些种类各异的拓扑结构往 往是针对不同的特定服务而优化选择的，对于一种服务适合的拓扑结构对另外的 服务就不一定是高效的 2 6 1 。 4 中山大学硕士学位论文 文献【1 5 】把覆盖网的拓扑模型分为两类，一类是不知道或者不利用物理层网 络拓扑的，如全网格( f u l lm e s h ) 、网格树( m e s h t r e e ) 、最小生成树( m i n i m u m s p a n n i n gt r e e ) 等；另外一类是知道物理层网络拓扑的，如邻近连接( a d j a c e n t c o n n e c t i o n ) 和知道物理层拓扑的最小生成树( t o p o l o g y - a w a r em i n i n l t n ns p a n n i n g t r e e ) 等。然后在这些拓扑上利用不同的路由算法进行了仿真实验，通过对错误 修复率、路由耗费等性能指标对比后得出了以下几个结论： ( 1 )网络拓扑对覆盖网的路由服务性能有重大的影响，在一种网络拓扑下表 现最好的路由算法在另外一种拓扑结构下可能最差； ( 2 )网格树模型在覆盖服务网中并不是一个好的选择，因为仿真实验中所有 的路由算法在这个拓扑模型下的性能表现都很差； ( 3 )下层物理网络拓扑信息对构建一个高效率的覆盖网拓扑结构是非常有用 的，因为知道物理层网络拓扑的覆盖网拓扑模型在各种路由算法下性能表现普遍 比其他拓扑模型好。 1 2 5 覆盖网络的路由算法研究 路由研究主要分服务路由研究和数据路由研究，服务路由只是数据路由的更 上一层抽象，本质上是一致的。 文献【7 】是o s n 的路由解决方案，引入了o v c d a yb r o k e r s ( o b s ) 的概念， 每一个自治域都至少包括一个o b s ，o b s 彼此间相互操作为o s n 应用提供服务， 文章提出了q r o n 路由算法，这个算法通过平衡o b s 之间的数据流量和覆盖链 路来寻求一条覆盖路径。q r o n 给出了两种链路代价算法，分别为改进最短路径 ( m o d i f i e ds h o r t e d - d i s t a n c ep a t h ，m s d p ) 算法和成比例的带宽最小路径 ( p r o p o r t i o n a lb 锄d w i d ms h o r t e s tp a t h ，p b s p ) 算法。文献 2 】 1 6 】【1 7 】是对p 2 p 文件共享系统的路由研究。文献0 7 利用相容哈希表来完成文件的查找和路由， 文献 16 】则进一步将数据分类以减少路由查询的消息量，文献0 7 研究了如何利 用路由表中的冗余信息来获得更高的路由效率。 第1 章绪论 1 2 6 路由发现策略研究 路由发现策略是指路由探测和选择的策略不同的路由策略因为实现的机制 不同，开销的大小也不同 s p i n e s 覆盖网络【1 明是由美国霍普金斯大学的c l a u d i ud a n i l o v 和y a i r a m i r 提 出的。s p i n e s 的路由发现策略使用h e l l o 协议。邻居节点之间使用不可靠h e l l o 包 定期发送p i n g 消息，以检查节点之间的连接情况。如果连续累计发送一定数量 的h e l l o 包而没有得到回复，就认为该节点已经断开，不再是邻居节点了。s p i n e s 的h e l l o 协议负责在相邻d a e m o n 之间创建、销毁、监控覆盖虚拟链路和测量链 路的延时特性。如果s p i n e s 通过h e l l o 协议检测到网络失败，就会根据情况调整 路由方案。s p i n e s 提出的逐跳传输协议和实时恢复协议能够很好地改善实时传输 的延时、丢包率和吞吐量等特性。 r o n ( r e s i l i e n to v e r l a yn e t w o r k ，弹性覆盖网) 【i 】是美国麻省理工大学的 d a v i dga n d e r s e n 提出的。r o n 的路由发现策略基于发送探测包去探测网络性 能。r o n 非常主动和强烈地发送探测包去获得用户关心的网络性能参数，能够 快速探测失效路径并且重新选择一条替代路径，提供灵活的路由策略，支持各种 用户自定义的应用，例如视频会议，然后根据应用去匹配相应的路由度量( 系统 默认提供三个路由度量：r o u n d - t r i p - t i m e 延时，丢包率，抖动) 去进行路由。r o n 采用的是周期泛洪探测结合s p a n d t 明机制的路由发现策略泛洪探测回来的得 到的网络性能信息存放在r o n 中的一个性能共享数据库里，这个数据库借助的 是s p a n d 中s h a r e 的思想，泛洪代替了s p a n d 之中被动探测的思想。但当r o n 网络规模逐渐扩大，周期泛洪探测包在网络中的开销会越来越可观，有时甚至影 响数据包的传输，因此r o n 的网络规模限制在两个节点到五十个节点之间。 s p a n d 2 5 1 也是一种路由发现策略，目标是建立一个统一的端到端共享的网 络性能信息仓库，当终端应用要建立路由时可以查找数据库里的信息来获取遥远 的i n t e m e t 终端的信息。s p a n d 的思想是拓扑相近的节点为一簇，同一簇内不需 要每个节点都发出p r o b e s 去探测网络性能，同一簇内的节点共享其中一个节点 探测回来的网络性能状况信息。 测量网络性能最常用的办法就是引入探测包，引入这些探测包的目标就是去 测量两个终端之间的r o u n d - t r i p - t i m e ( r t t ) ，峰值带宽，或者可以公平分享的带 6 中山大学硕士学位论文 宽等文献【1 8 】【1 9 】【2 0 】【2 1 】 2 2 】【2 3 】提出了一些p r o b e sa l g o r i t h m 能够探测 r o u n d - t r i p - t i m e 和峰值带宽的p r o b e s 诸如文献 1 8 1 提出的n e t d y np r o b e s ，文献 1 9 】 提出的p a c k e tp a i r ，文献【2 0 】提出的b p r o b e s 。文献 2 2 1 提出的p a t h c h a r 与文献 2 3 1 t r a c e r o u t e 结合起来可以测量链路带宽和每一跳的延时，文献 2 9 1 提出的 p a c k e tb u n c hm o d e ( p b m ) 在网络中插入各种大小的包群来测量网络性能，这 就允许p b m 可以处理多信道的链路( 例如i s d n 连接，多链路点对点协议( p p p ) 连接，等) ，也同时提高了网络性能测量的准确度。文献 2 0 1 还提出了c p r o b e s ， 测量带宽是否公平共享。文献【2 l 】提出的t r n e o 实质上就是将文献【2 0 】的b p r o b e s 和c p r o b e s 结合，进行瓶颈链路的流量竞争，控制拥塞等。 图1 2 对比了各种网络测量引入的网络开销。 w h a t _ h 目l r f - s 柚诅m 曲r 划l d i l i o u lt r a 如啪n s y s t e m p e r f o r m a n c e i a t r e d u c e d n e t t 噶脚蛔“ 印峨q 曲s 畿篓 s i 俨缸卜1 0 k )c p r o 如u $ l l t o f l o w ! c h e n ts i d e 珥掣n c m 嘲 p a d r e 陆 a v a l h b a z d m d t 卜i 玛a g “珥f 细 c l i e n ts i d e 缸甲_ 嘲 p a t h e k 啤母姊l i n k辅掣嘶吐p i o 酗 鎏。“脚一 c h e a ts i d e b m 凶j 曲l m 嘲r t k _ _ k e t b e n c h 豁黟攀 s 酵吐c 墨t 卜l o 鹭 c l i e n t s i d e m o d e s t r a ma v a 血b l e b 卸出融 s 婚睡口p 1 0 1 d u 搬t c pf l 啊阳c 讳a i 耐s i d e g e s 随m c o l m d 图1 2 各种网络性能估测的网络开销图 如何通过估测网络性能来快速发现路由，又不至于引入可观的网络开销而影 响覆盖网络的扩展，对于覆盖网络的发展非常重要。开销小的有效的路由发现策 略让覆盖网可以更加灵活的实现用户定义的各种应用。 覆盖网络的路由发现策略也是覆盖网络研究的重要分支，也是本文的研究重 点，本文将在以下几章详细介绍。 7 第1 章绪论 1 3 论文工作 1 3 1 论文意义与内容 本文的覆盖网络平台使用弹性覆盖网r o n 。 r o n 网络采用周期泛洪发送探测包的路由发现策略，探测包的开销随着弹 性覆盖网络的规模增大而增大，探测包的通信量已经成为r o n 路由发现的负担， 并且严重限制了r o n 扩展，r o n 网络节点数限制在两个到五十个之间。针对这 个问题，本文采用一种按需随机探测的方法来减小r o n 中探测包的网络开销， 提高r o n 系统工作效率，改善r o n 的扩展性，让r o n 应用更广泛。 由于当今v o i c e 业务的q o s 所敏感的路由度量是o n e - w a y - d e l a 尸1 ，所以本 文为r o n 构建的路由度量为o n e - w a y - d e l a y ，并没有采用r o n 系统默认提供的 r o u n d - t r i p - t i m e ( r t t ) 路由度量。 本文使用o p n e t 作为网络仿真软件，使用p a c k e tf o r m a te d i t o r 设计探测包， 数据包，使用l i n km o d e le d i t o r 设计l i n km o d e l ，并从o p n e t 最底层开始编程， 使用p r o c e s s m o d e le d i t o r 和n o d e e d i t o r 设计r o n 节点及a s 节点的p r o c e s s m o d e l 和n o d em o d e l ，按照文献【l 】的实验拓扑在o p n e t 的p r o j e c te d i t o r 上建立起r o n 的3 6 个节点的大拓扑。在验证设计和程序的正确性之后，构建r o n 周期泛洪探 测仿真场景和改进的按需随机探测仿真场景进行仿真，使用o p n e t 的a n a l y s i s t o o l 对比仿真结果及进行分析 1 3 2 论文结构 本文结构篇章如下： 第一章：介绍了本文的研究背景，覆盖网络的研究现状和论文工作。 第二章：详细介绍了本文所使用的覆盖网平台r o n ，详细介绍了r o n 的各 个模块的设计和实现，包括系统模型，数据转发，虚拟链路管理，实验评价等。 第三章：介绍了各种路由发现策略，详细介绍了r o n 的路由发现策略。并 且提出一种可以减小r o n 探测包带来庞大网络开销的方法：按需随机探测。 第四章：介绍了网络仿真软件，主要介绍了o p n e t 。 第五章：在o p n e t 上设计r o n 终端节点模型，建立r o n 拓扑，实现r o n 中山大学硕士学位论文 平台，验证模型与程序的正确性构建仿真场景，对r o n 的泛洪探测策略和按 需随机探测策略进行仿真，进行各条路径吞吐量的比较，仿真结果表明按需随机 探测有效降低r o n 探测包的开销，改善r o n 的可扩展性；并且降低的网络开 销使数据包o n o - w a y - d e l a y 也降低了。 第六章：结束语。 9 中山大学硕士学位论文 第2 章弹性覆盖网( r e s i ii e n to v e r l a yn e t w o r k ) 2 1 弹性覆盖两r o n 的优势 当今基于b o p 4 的大范围i n t e r a c t 路由系统，并不能很好地处理网络中的失 效。从网络角度看有两种失效，链路失效和路径失效。链路失效指的是路由器或 者连接两个路由器的链路发生失效，可能的原因是软件错误，硬件失效或者链路 断开。另一种失效是路径失效，路径失效的发生可能有许多原因，包括受到了拒 绝服务攻击或者突发的流量导致分组丢失率上升或者延迟增大。从应用的角度 看，也有两种失效。一种是彻底失效，另一种是性能下降彻底失效是指由于链 路失效或者比较严重的路径失效导致大部分应用不能正常运行。性能下降则是指 应用系统发现网络的性能有所降低，但是还在可以容忍的范围之内。b g p 对于 汇聚和失败的反应是很慢的，一般来说，b o p 协议需要花数分钟才能在链路失 效后重新恢复正确的路由。而r o n 的目标则是在2 0 s 之内从链路失效中恢复。 另外，b g p 并不能检测到链路性能的降低，只要链路还是通的，b g p 就认为路 由是正确的这样就导致根据b g p 得到的路由并不能满足应用的需要。r o n 可 以帮助优化路由。 不同应用对网络性能降低的容忍程度是不同的，例如，基于u d p 的应用在 分组丢失率大于1 0 时基本上就不能正常工作了，而基于t c p 的应用则在分组 丢失率达到3 0 时还能够进行正常的分组传输。而r o n 可以允许应用定义失效 和如何对失效进行响应。 目前b g p 还不能针对单个用户或者主机定义路由策略，这样就不能对不同 的端用户提供不同的路径选择。而由于r o n 节点本身就是运行在端系统上，因 此r o n 可以针对终端主机定义灵活的路由策略。 2 2r o n 的模型设计 r o n 的设计理念如图2 1 。节点发送探测包来获得彼此之间的网络状况，然 后根据探测回来的信息进行路由。在图2 1 这个例子中，u t a h 并不是直接发送数 第2 章弹性覆盖网( r e s i l i e n to v e r l a yn e t w o r k ) 据包到c a b l em o d e m ，而是间接经过了m r r 。 图2 - 1 r o n 理念设计图 r o n 节点可以位于i n t e m e t 的任意位置，它们形成了一个应用层的覆盖网络， 并且相互协作完成分组转发。每个r o n 节点都探测它和其他节点之间的i n t e m e t 路径的质量并使用该信息进行路径选择两个r o n 节点之间的i n t e m e t 路径称 为虚拟链路。为了构造整个覆盖网络的拓扑结构并获得拓扑结构中全部虚拟链路 信息，每个r o n 节点都参与一个分布式路由协议来交换各种链路度量信息。 通过r o n 进行通信的应用程序称为r o n 客户程序。r o n 的设计目标主要 就是为一组使用r o n 的客户程序提供更可靠的口分组传输机制。 r o n 体系结构如图2 2 。 r o n 客户端通过c o n d u i t 接口和r o n 交互。在数据转发路径上，通过c o n d u i t 接收分组的第一个r o n 节点( e n t r yn o d e ) 将对分组进行分类以决定分组需要使 用的路径类型( 如低延迟或高吞吐率等) ，路径选择在e n t r yn o d e 中完成，该节 点将从拓扑表中寻找一条路径，用r o n 分组报头封装该分组，对分组进行标记 以简化后续节点的转发过程，然后将分组转发出去。每个后续的r o n 节点只需 要知道目的地址和标记决定下一跳。最后一个r o n 节点( e x i tn o d e ) 将把分组 递交给r o n 客户程序。 中山大学硕士学位论文 d a t a 图2 - 2 r o n 体系结构图 在r o n 中，路径选择在e n t r yn o d e 中完成，这样节省了中间转发的节点的 处理量。当选择的路径失效时，下游的节点不会改变已经选择的路径，而是将失 效信息传播给e n l l yn o d e ，让其再重新选择路径。 2 3 r o n 的引导协议( b o o t s t r a p ) 和同伴管理 一个新加入拓扑的r o n 节点需要通知其他拓扑中的节点，r o n 允许r o n 客户终端使用自定义的节点同伴管理机制，r o n 也提供两种系统同伴管理：一 种是从文件导入的静态同伴管理机制，一种是基于通告的动态的软状态同伴管 理。 当引导一个新节点加入的时候，新节点至少需要知道r o n 网络中一个r o n 节点的d ，新节点通过这个r o n 节点将新节点的存在广播给r o n 中已存在的 节点。为了支持这样一个通告机制，r o n 提供了一个通用的泛洪机制。每个泛 洪包都有一个唯一的6 4 b i ti d ，当泛洪包到达一个f o r w a r d e r 时f o r w a r d e r 就记下 这个d 以免重复接收，增加节点的处理量。 这种动态同伴管理需要在简单和健壮性之间的折中。实际上，这种广播的开 销比起探测包和路由更新的开销来说是很小的，而且实验中r o n 的网络规模不 大。对于离开了r o b 的节点又在回到r o n 中的情况，例如系统或进程重启， 这个节点保存了离开前r o n 中的所有节点名单，重新加入后对这份名单上的节 第2 章弹性覆盖网( r e s i l i e n to v e r l a y n e t w o r k ) 点进行广播，在收到它们的反馈之后把它们加入新的同伴名单。 2 4r o n 的数据转发 r o n 使用u d p ( u s e rd a t a g r a mp r o t o c o l ，用户数据报协议) 来转发数据， 因为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 o l ，传输控制协议) 与r o n 客户终端不匹 配，使用基于口的封装会限制r o n 的特有的应用层转发能力。 r o n 的f o r w a r d e r 提供转发功能。c o n d u i t 相当于用户终端与r o n 之间的网 关，它进行包的封装和分类，这个分类是可以终端定义的，它在包上贴上信息的 标签，这些信息决定了用什么路由度量。r o n 中本身存在三个路由度量： r o u n d - t r i p - t i m e 延时( r t t ) ，丢包率和吞吐量。例如对h 1 1 甲流可以标签为对r t t 延时敏感的，对f t p 流可以标签为对吞吐量敏感的，这些标签决定了r o n 的 f o r w a r d e r 用什么路由度量。 r o n 一般不分割一个包，除非包超过了m a x i m u mt r a n s m i s s i o nu n i t ( m r u ) ， 这时返回i c m p 信息“m u s tf i a g m e n t ”。 r o n 的报头如图2 3 所示： v e r s i o n h o p l i m i tr o u t i n gn a g s r o n $ o u z c ea d l 蛔 l l 0 咐d e s t i n a t i o na d d r e s s s o t h c ep o r td e s tp o r t h o w i d p o l i c yt a g p a c k e tt y p e 图2 - 3 r o n 报头 r o n 报头中的r o u t i n g f l a g 和f l o w i d 是由c o n d u i t 所设置。p a c k e t t y p e 是发 送数据包到合适的接收者( r e c e i v e r ) 的c o n d u i t 的关键。p o f i c yt a g 是路由策略 标签。r o u t i n gf l a g 是路由优先度量标签，f l o wi d 指定下一跳。 一个有n 个节点的r o n 网络，有n - l 条虚拟链路。r o n 采用泛洪探测方 式来得到链路的度量参数。探测得到的样本信息保存在性能数据库( p e r f o r m a n c e d a t a b a s e ) 中，性能数据库借助了s p a n d 的思想 2 5 l 。泛洪探测和s p a n d 的原 1 4 中山大学硕士学位论文 理将在第三章介绍 当一个包到达一个r o n 节点时，f o r w a r d e r 会判断当地是否包的目的地，如 果不是，则进行三级查找，则需要将r o n 报头传递给m u t i n gt a b l e 。转发控制 ( f o r w a r d i n gc o n t r 0 1 ) 如图2 4 所示 图2 _ 4 转发控制图 第一级查找基于策略类型，通过p o l i c yt a g 知道此次的策略路由，然后找到 相应的参考路由表。第二级查找基于路由优先度，根据r o u t i n gf l a g 找到一个与 数据包相一致的路由选择度量( m e d i c ) ，这个m e 舡i c 可以是系统的基本m e t r i c ： 延时，丢包率，吞吐量，也可以是用户自定义的m e t r i c 。第三级查找是基于目的 地址的哈希查找，再由f o r w a r d e r 将数据包送往下一个节点。在r o n 中，这里 用的是基于p e c x - t o - p e c r 的c h o r d 算法。i pf o r w a r d 盯的结构如图2 5 。图2 - 5 是 r o n 客户终端的p 封装过程。数据包通过r o n 的f r e 圯b s d 的套接字进入系统， 经过封装之后进入r o nf o r w a r d e r ，在多层路由表中进行下一跳的三级查找。当 包到达目的地时，c o n d u i t 写进当地的原始套接字，进行解封装 第2 章弹性覆盖网( r e s i l i e n to v e r l a y n e t w o r k ) 图2 - 5r o n 客户端的数据封装图 2 5r o n 的策略路由 r o n 的策略路由允许r o n 客户终端定义数据流的类别来指定特定的网络链 路。例如，r o n 可以定义一个策略叫做“只有麻省理工大学计算机系的学生可 以接入i n t e m e t 2 ”其他r o n 客户终端也希望可以定义不同的策略。r o n 的策 略路由由两部分组成：分类和路由表构成。当数据包进入r o n 时会被分配一个 策略标签，策略标签引导路由查找在相应的路由表中进行。 策略分类器提供了策略标签，c o n d u i t 数据分类器和允许功能。c o n d u i t 数据 分类回答“i s t h i s p a c k e t m y t y p e ? ”；允许功能告诉路由器这个策略能否使用特定 的链路。r o n 设计了两种策略：“e x c l u s i v e c l i q u e s ”( 小圈子策略) 和通用策略。 1 6 中山大学硕士学位论文 在小圈子里产生和目的地是小圈子的数据才可以使用小圈子之间的特定的链路， 其实这就如i n t e m e t 2 里的教育网。在通用策略分类器里，r o n 允许用户创建他 们自己策略的组合。 2 6r o n 的路由发现策略 r o n 采用泛洪探测与s p a n d 结合来作为它的路由发现策略，第三章会对泛 洪和s p a n d 做详细介绍。在一个有n 个节点的r o n 中，每个r o n 节点使用 周期探测来监控它的n - l 条虚拟链路。r o n 中，每个p e e r 都有一个主动探测组 件，这个组件维持着一个n e x t 邮b ct i m e 的域。当这个域的时间到了，探测器 就会发送一个小小的u d p 包到别的p e e r ，每个探测包都有一个随机的6 4 b i t 的 d 。这个过程使用的探测机制如图2 - 6 所示。当一个节点收到p e e r 的探测包后， 它响应1 给p e e r ，然后重置那个p e e r 的p r o b et i m e r 。当发送探测包的节点收到l 响应后，发送2 到响应它的p e e r ，然后即表明双方可到达，r o u n d - h i p - t i m e 的信 息就来自这三个包。 圈2 - 6 砌广r 探测机制图 l p r o b e 的探测周期是p r o b ei n t e r v a l ，允许圭p r o b ei n t e r v a l 的偏 3 。 离。如果探测包在p r o b e时间之内没有返回，则认为探测包t i m e o u t p r o b e r 丢失了并且记录这个丢失事件。为了加快失效检测，当有探测包被认为丢失之后， p r o b e r 会马上再发四个快速探测包。而p r o b e r 是依赖于t i m e r 来完成这些周期动 作的：检查有没有过期的探测信息。选择一个最久以前发过探测包的节点，如果 发现这个时间超过了t i m e r ，那么发送探测包。 1 7 驺 壹 恤 孵黜叫q科鹬 仪l矿 砌叫一 雠 堂 恤 n 钒 耐 扣 酝 m p 、 第2 章弹性覆盖网( r e s i l i e n t o v e r l a y n e t w o r k ) 在默认情况下，p r o b ei n t e r v a l 是1 0 秒，所以p r o t m r 一般每隔1 2 秒发 送探测包p r o b et i m e o u t 默认是3 秒，当p r o b e r 在3 秒内没收到其他系统 的响应，则报告丢包p r o b i n gp r o t o c o l 就会将这些延时和丢包信息写进 口e 墒砌舳d a t a b a s e 由上述参数可以看到，p r o b e r 会在 p r o b e 刷孢r 眦+ 4 咫et i m e o u t 的时间内检测出网络失效，大概2 5 3 。 秒。 r o n 路由组件使用链路状况路由协议在节点之间分发拓扑信息，这些信息 是用来构建路由转发表的。每个r o n 节点都周期性地汇聚从它到其他节点