（计算机科学与技术专业论文）面向层叠网构建的网络感知技术研究与实现.pdf

国防科学技术大学研究生院硕十学位论文 摘要 近年来，随着层叠网技术的不断发展，涌现出了越来越多的层叠网应用。这 些应用在给我们提供服务、带来便利的同时，占据了大量的可用带宽，如何提高 层叠网应用效率，节省宝贵的网络带宽资源，成为亟待解决的一个重要问题。 网络感知技术能够感知底层物理网络的状态，根据感知结果指导层叠网的拓 扑构建，优化层叠网应用产生的网络流量，缓减骨干网压力，是解决目前层叠网 带宽浪费问题的一个重要途径。 本文面向层叠网应用的优化问题，提出了面向网络设备控制平面的感知体系 结构。通过网络设备获得真实的拓扑信息，并基于标准的网络感知接口为层叠网 应用程序提供网络感知功能服务，简化了层叠网应用结构，提高了应用感知的准 确性和感知效率。 基于面向网络设备控制平面感知体系结构，本文设计实现了基于b g p 协议路 由信息的a s 网络拓扑感知模块和公共时延感知服务模块。在a s 网络拓扑感知模 块中，针对b g p 协议路由收敛慢的问题，提出了一种故障路径快速感知算法；在 时延感知模块中，根据层叠网应用的特点，构建了时延地址缓冲区，多次测量节 点时延，使感知结果更接近真实状况。 通过试验进行模拟，我们的系统确实能够有效感知底层物理网络状态，对诸 如流媒体分发等应用性能有较大改善。 主题词：层叠网，网络感知，a s 拓扑，时延 第i 页 国防科学技术人学研究生院硕十学位论文 a b s t r a c t i nr e c e n ty e a r s ，i n t e m e te m e r g e so u to fm o r ea n dm o r eo v e r l a yn e t w o r k a p p l i c a t i o nw i t ht h er a p i de x p a n s i o no fn e t w o r ks c a l ea n do v e r l a yn e t w o r kt e c h n o l o g y d e v e l o p m e n t t h e yp r o v i d eu sw i t hs e r v i c e sa n db r i n gc o n v e n i e n c e ，b u ta tt h es a m e t i m eo c c u p yag r e a td e a lo fa v a i l a b l eb a n d w i d t hr e s o u r c e s i m p r o v i n go v e r l a yn e t w o r k a p p l i c a t i o ne f f i c i e n c ya n ds a v i n gv a l u a b l en e t w o r kr e s o u r c e sb e c o m eas e r i o u sp r o b l e m n e t w o r k a w a r et e c h n o l o g yc a ns e n s et h es t a t eo ft h ep h y s i c a ln e t w o r k ，a n d a c c o r d i n gt ot h er e s u l t sg u i d et h ec o n s t r u c t i o no fo v e r l a yn e t w o r k i tc a no p t i m i z et h e n e t w o r kt r a f f i cw h i c hb r i n g si nf r o mo v e r l a yn e t w o r ka p p l i c a t i o n s ，a n dm i t i g a t e b a c k b o n ep r e s s u r e ，w h i c hi sa ni m p o r t a n tw a yt os o l v et h ec u r r e n to v e r l a yn e t w o r k b a n d w i d t hw a s t a g e t h i sp a p e rp r o p o s e dt h en e t w o r kd e v i c ec o n t r o lp l a n en e t w o r k a w a r ea r c h i t e c t u r e f o ro v e r l a yn e t w o r ka p p l i c a t i o n so p t i m i z a t i o n ，i to b t a i n sr e a lt o p o l o g i c a li n f o r m a t i o n t h r o u g ht h en e t w o r kd e v i c e ， a n ds t a n d a r d s - b a s e dn e t w o r k a w a r ei n t e r f a c eo f f e r s n e t w o r k - a w a r ef u n c t i o ns e r v i c ef o ro v e r l a yn e t w o r ka p p l i c a t i o n s ，w h i c hs i m p l i f i e st h e s t r u c t u r e so fo v e r l a yn e t w o r ka p p l i c a t i o n sa n di m p r o v e st h ea c c u r a c yo fa p p l i c a t i o n p e r c e p t i o na n dp e r c e i v e de f f i c i e n c y b a s i n gn e t w o r kd e v i c ec o n t r o lp l a n ea r c h i t e c t u r eo fp e r c e p t i o n ，t h i sp a p e rd e s i g n s a n di m p l e m e m sp u b l i cd e l a y - a w a r es e r v i c em o d u l ea n da sn e t w o r kt o p o l o g y a w a r e m o d u l ew h i c hb a s e so nb g pr o u t i n gi n f o r m a t i o n i nt h ea sn e t w o r kt o p o l o g y - a w a r e m o d u l e ，w ep r o p o s e daf a u l tp a t hf a s tp e r c e p t i o na l g o r i t h mf o rs l o wc o n v e r g e n c e p r o b l e mo fb g pp r o t o c o lr o u t i n g i nt h ed e l a y - a w a r em o d u l e ，a c c o r d i n gt o t h e c h a r a c t e r i s t i c so fo v e r l a yn e t w o r ka p p l i c a t i o n sw eb u i l tt h ed e l a yb u f f e rw h i c hm e a s u r e s t h en o d e sd e l a yf o rm a n yt i m e sf o rp e r c e p t i o nr e s u l t sc l o s e rt ot h ea c t u a ls i t u a t i o n t h r o u g ht h es i m u l a t i o ne x p e r i m e n t s ，o u rs y s t e mi si n d e e da b l et oe f f e c t i v e l y p e r c e i v et h eu n d e r l y i n gp l a y s i c a ln e t w o r ks t a t u sa n di m p r o v ea p p l i c a t i o n sp e r f o r m a n c e o f s u c ha ss t r e a m i n gm e d i ad i s t r i b u t i o n k e yw o r d s ：o v e r l a yn e t w o r k ，n e t w o r k a w a r e ，a st o p o l o g y ，d e l a y 第i i 页 国防科学技术人学研究生院硕十学位论文 表目录 表4 1b g p 路径属性列表2 7 表5 1a s 间最小跳数及转发路径查询4 0 表5 2 平均时延对照表( 单位：m s ) 。4 1 表5 3 加入感知模块前后故障路径感知时间对照表4 3 表5 4 并发性查询开销统计表4 5 第l l i 页 国防科学技术人学研究生院硕十学位论文 图1 1 图1 2 图2 1 图2 2 图2 3 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1l 图5 1 图5 2 图5 3 图5 4 图目录 层叠网拓扑示例2 i d m a p s 拓扑结构5 网络感知层体系结构8 设备控制平面感知模块体系结构1 1 a s 拓扑路径探测图1 2 a s 网络拓扑与初始邻接矩阵表1 5 故障路径快速感知算法描述1 6 故障路径快速感知示意图1 7 故障路径快速感知示例1 7 缓冲区队列操作示意图2 0 时延地址缓冲区节点替换算法2 1 基于q u a g g a 的网络感知系统结构图2 4 网络感知服务接口2 5 网络感知服务接口查询示意图2 6 a sp a t h 属性示意图2 7 网络拓扑感知模块软件结构图2 8 网络拓扑感知模块详细流程图2 9 公用内部通讯报文格式3l a s 跳数查询通讯报文格式3 2 网络时延测量与查询模块结构图3 3 网络时延测量与查询模块详细流程图3 4 网络时延测量与查询通讯报文格式3 6 测试环境网络拓扑图3 8 故障路径快速感知时间测试拓扑图4 2 加入感知模块前后故障路径感知时i 、日j 统计图4 3 并发性查询开销统计图一4 5 第l v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：叠已羔啦日期：9 7 年) z 月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩e f 7 或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 作者指导教师签名： 日期： 沙，7 年72 月7 日 日期：知岬年iz 月7 日 ， 国防科学技术入学研究生院硕十学何论文 第一章绪论 1 1 课题背景 近几年来，现有的i n t e r n e t 传输网络存在着向栅格网络发展的趋势，其中完全 位于应用层的o v e r l a y ( 层叠网络) 系统发展很快。例如：提出了监测路径失效的 弹性o v e r l a y 网络；为现有的i n t e r n e t 提供端对端服务质量保证的服务o v e r l a y 网 络等。 层叠网具有广阔的应用前景，正在被用来部署各种类型的网络服务，比如： 文件共享和网络存储系统n 2 2 3 4 ，c d n 网络乜1 ，路由和多播层叠网。4 t5 1 ，q o s 层叠 网阳1 ，动态目标定位层叠网盯16 3 铂等。但是在传统i p 网络和各种专用网络中如何为 层叠网络提供有效支持，以及层叠网络如何充分利用多种下层网络提供的传输机 制来提高应用性能和抗打击能力，实现网络整体效能的最大化，都是需要解决的 重要问题。可感知网络技术是解决上述问题的一个重要技术途径，因此本文针对 可感知网络技术重点展开研究。 可感知网络技术是指，层叠网络感知下层网络的各种信息，针对感知的物理 网络拓扑对上层应用进行优化的技术。“可感知网络 将网络的部分服务对用户 开放，在端用户拥有更多智能的假设条件下，为用户提供更加灵活的传输服务， 如主动路由控制( 进行显式路由选择) 、主动策略路由、主动路径特性感知( 如 路径m t u 发现，避免网络传输中进行报文分段) 等。典型研究项目有b e r k e l e y 大学的“r o u t i n ga sas e r v i c e ”，允许用户显式地请求网络的路由服务，获取网络 的路由信息，用户再根据自身的决策，主动选择合适的传输路径。 在层叠网体系架构中运用网络感知技术，构建高效的层叠网拓扑，能够提高 层叠网应用的效率，节省网络资源，对层叠网技术的进一步发展有重要意义。 1 1 1 层叠网概述 层叠网是建立在一个或者多个已经存在网络之上的网络，通过增加额外的、间 接的、虚拟的层来改善下层网络部分域中的一些属性，提高网络性能。层叠网是 一种不同于底层物理网络的逻辑网络，层叠网中的跳路由( 从节点a 到节点b ) 可能对应物理网络中的多跳路由。 第1 页 国防科学技术人学研究生院硕十学1 = 7 ：论文 图1 1 层叠网拓扑不例 层叠网有一些好的特性： 第一，扩展性好。一个层叠网络不需要改变已有的网络结构，也不需要整个网 络范围内的网络组件的支持，这一思想的实现将会加快新型网络功能和服务的部 署。当节点被增加到层叠网中时，可以更加精确地控制下层网络数据的路径。 第二，灵活性强。层叠网络所建立的是一个抽象的连接，这些连接可以根据应 用程序的需要进行优化。比如，层叠节点可以以带宽为代价优化时延。 第三，健壮性好。层叠网络比下层的网络设施更加健壮。比如在一个有足够多 节点配置的层叠网络中，可以通过两条彼此完全独立的路径实现任意两个节点的 路由。 第四，标准性强。层叠网络能够在下层网络的最少一般共同特性的网络服务器 上建立起来。比如o v e r c a s t 使用t c p 实现可靠传输，而t c p 是简单的，容易理解 的，网络友好的和标准的。 层叠网的这些良好特性使得越来越多的应用构建在层叠网上，然而层叠网应用 占据了大量的i n t e r n e t 可用带宽，因此研究如何在保证层叠网应用质量的同时节约 带宽资源具有重要的现实意义。 1 1 2 层叠网分类 依据感知技术的运用层叠网可以分为以下几类： 1 ) 传统层叠网技术，即无感知的层叠网技术。它基于逻辑空问的标识符创建 到邻居的连接，比如分布式哈希表算法( d h t ) 中的c h o r d m l 和c a n l 9 i 算法，在逻 辑拓扑空间中每个节点和它的最近邻居节点或者子网建立网络连接，进行消息路 由和资源查找，然而由于没有考虑物理网络的相关信息，逻辑网络和物理网络的 拓扑结构不可避免地出现不匹配。在逻辑网络中相邻的节点，常常在物理网络中 第2 页 国防科学技术人学研究生院硕十学位论文 相距甚远，因此逻辑网络中的次逻辑路由可能会经过物理网络中的多次物理路 由。这种低下的物理路由效率导致了网络中查找的物理路径较长的问题，并增大 了网络的通信代价。 2 ) 基于邻近感知的层叠网技术。由于无感知的层叠网技术路由效率低下，不 适合很多以效率为优选目标的应用，而基于邻近感知的层叠网技术在进行逻辑空 间路由选择时，考虑了底层网络的“距离 因素，因此更加合理，效率更高。在 d h t 网络中，p a s t r y 1 0 】和t a p e s t r y t 】算法即是如此。它们在更新路由表时，会选择 有相同标识符前缀，但“距离 更近的节点。然而，像p a s t r y 这样的基于邻近感 知的层叠网技术，在选择邻近节点更新路由表时，只有标识符前缀相同时才考虑 物理“距离”因素。因此，它们虽然从某种程度上提高了路由效率，但对层叠应 用服务的性能改善很有限。 3 ) 基于网络感知的层叠网技术。这种层叠网技术完全从逻辑空间中分离出 来，基于纯粹的物理节点“距离”来创建层叠网拓扑，本地性【3 8 】成为其基本的路 由策略。这个原则意味着网络流量应该最大限度地留在本地，这是因为本地网络 流量有更高的应用质量，比如更少的路由跳数，时延更小，带宽利用率更高，可 靠性更高等。网络感知技术适合大范围的应用，比如内容分发树的建立，大规模 p 2 p 应用等。 与传统层叠网和基于邻近感知的层叠网技术相比，基于网络感知的层叠网技 术能够全面感知底层物理网络的状态，抽取与应用相关的网络拓扑，减少了网络 探测开销，增强了应用路由能力，极大地提高了各种层叠应用服务的效率。 本文面向层叠网应用，借鉴当前国内外网络感知领域的研究成果，在层叠网 模型中引入网络感知层，实现网络感知功能，优化网络感知算法，提高了网络感 知效率，为层叠网应用提供良好的支持。 1 2网络感知相关技术研究 网络感知技术是近年来网络领域研究的热点之一，a k i h i r on a k a o 等人首先提 出了实现网络感知及其应用的总体框架n 引，成为研究网络感知技术的指导性文章。 文章认为多个层叠应用独立探测网络，获取网络拓扑信息会产生较大开销，因此 提出在物理网络与层叠网络之间增加虚拟的网络感知层，用于获取底层网络信息， 为相似层叠网应用提供服务，这样的方法可以极大地降低探测开销。文章还提出 了实现网络感知的若干服务原语，通过实现这些服务原语，能够很好地感知底层 网络的各种信息，为上层应用服务提供良好的支持。其它研究则主要集中在如何 通过预测底层网络节点问的距离，来更好地感知网络的拓扑结构上。 第3 页 国防科学技术大学研究生院硕十学位论文 1 2 1 网络坐标系统 网络坐标系统是典型的网络感知层叠算法，其基本思想是通过某种网络嵌入 的方式，将整个网络嵌入到一定的几何空间当中，网络中的节点对应所嵌入空间中 的点，空间中节点之间的距离对应网络中节点之问的距离，并以一定的坐标形式计 算节点的网络坐标，v i r t u a ll a n d m a r k 1 3 1 、v i v a l d i t l4 1 、i d e s l l 5 】等都是典型的网络坐 标计算方法。 v i r t u a ll a n d m a r k 是由波士顿大学的t a n g 等人于2 0 0 3 年提出的虚拟地标方法， 采用相对坐标方法计算网络坐标。普通节点首先获得地标节点的距离矩阵信息， 并以距离向量形式表示，向量的维度等于地标节点的数目；其次在基于l i p s c h i z t 3 6 】 嵌入的基础上采用p c a ( p r i n c i p l ec o m p o n e n ta n a l y s i s ) 技术来降低维度以提高计 算效率。 v i v a l d i 是由m i t 的f r a n kd a b e k 等人于2 0 0 4 年提出的，是一个简单的，轻量 级的算法，用来给节点指定网络坐标，并通过测量两个坐标间的距离来精确地预 测节点间的通信时延。v i v a l d i 是完全分布式的，不需要固定的网络结构和地标节 点，它也是高效的：一个新的节点通过测量与邻近节点的时延，可以容易地得出 自己的坐标。由于这种方法仅需要很少的通信量，所以v i v a d l i 能够胜任大规模节 点的层叠网络。在v i v a l d i 坐标空间中，节点通过计算两个节点网络坐标的距离来 预测节点问的时延。因此，如果节点x 得知了节点y 的网络坐标，那么不需要测 量x 到y 的时延，而可以通过网络坐标来精确地预测出它们之间的时延。 宾夕法尼亚大学的y u n 等人于2 0 0 6 年提出了i d e s 方法，该方法通过采用s v d ( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 和n m f ( n o n n e g a t i v em a t r i xf a c t o r i z a t i o n ) 两种 矩阵分解技术来建模子优化和非对称路由策略；为每个节点赋予一个入向量和出 向量，根据出向量和入向量的内积确定网络距离。该方法摆脱了对称性和三角不 等性的约束，然而它假设距离矩阵中存在大量线性相关的向量，即利用分簇性原 理，当出现错误分簇时，i d e s 的测量精度会明显降低。 p e t e rp i e t z u c h 等人提出了一种新的基于负载感知的网络坐标系统n 刀 ( l o a d a w a r en e t w o r kc o o r d i n a t e s ，l a n c ) ，它能兼顾考虑本地感知( 用物理距 离、时延、跳数来衡量) 与链路负载，通过应用层的r t t 来度量，从而构建负载 感知坐标空间，选择最优的内容服务器。经实验证明，此方案较随机选择、最近 选择、本地感知选择等效果有明显提高。 1 2 2 非坐标系统 非坐标系统方法通常是指通过直接测量的方式测量网络中部分节点的距离， 第4 页 国防科学技术大学研究生院硕十学俜论文 然后根掂这些部分测得的距离信息米直接预测所有节点之问的距离信息，并不使 用任何坐标计算的形式来预测。 2 0 0 1 年f r a n c i s 等人提出i d m a p s i 倦j 算法，该方法通过在不同的自治系统附近 部署一些跟踪节点( t r a c e r s ) ，从而形成各t r a c e r s 之间以及a s 与t r a c e r s 之问的 双层结构，其拓扑结构如图1 2 所示。双层结构中的节点互相探测距离，并将探测 的结果存入称为h o p s 的服务器中。主机之间的距离估计采用了三角启发式原理： 主机a 、b 之间的距离为a 到最近的t r a c e r l 的距离、b 到其最近的t r a c e r 2 的距 离以及t r a c e r l 到t r a c e r 2 之间最短路径距离的总和。 o 代表a s 代表t r a c 盯 口代表a s 中的主机 图1 2i d m a p s 拓扑结构 卡内基梅隆大学的w o n g 等人于2 0 0 5 年提出了m e r i d i a n n 叫算法( 一种轻量 级的不支持精确坐标的网络感知算法) ，算法的提出主要是为了解决诸如在分布 式系统中为目标节点寻找最近节点；为节点集合找到延迟最小的节点；在既定延 迟限制的条件下为目标节点找到符合延迟限制的节点集合等问题。它利用基于直 接测量形成的松散结构的同心环，结合g o s s i p 协议来交换节点间的信息，以迭代转 发查询匹配信息方式来定位最优的邻近节点。它首先根据“距离”将所有邻居节 点分配在不同的同心环上，为了给一个非m e r i d i a n 节点( 目标节点) 找到最近邻 居，先由一个初始节点测量它到目标节点的时延，然后初始节点请求相同环上的 所有邻居节点和相邻环上的一半节点测量到目标节点的时延。发起节点选择出到 目标节点最短“距离”的邻居，并将消息发送给它，而后将其作为新的发起节点， 重新进行上面的过程，直到找到目标节点的最近邻居。与网络坐标系统相比， m e r i d i a n 更加简单，丌销更小，能较好地完成对底层物理网络的感知任务，为相应 的应用提供良好的服务。其缺点是每次查询都有较大的测量丌销，并且当节点环 中的成员发生改变时，测量的结果可能不准确。 国内有人采用获取i p 地址瞳叫的方法进行网络感知。i p 地址可以在网络上标识 一台主机或者一个局域网，而i p 地址的分配是国际组织n i c ( n e t w o r ki n f o r m a t i o n 第5 页 国防科学技术大学研究生院硕十学俯论文 c e n t e r ) 根掘不同国家和地区进行的，因此i p 地址和节点的物理位置存在着一定 的映射关系。利用i p 地址的这种特性，可以建立相应的i p 地址查询库，在诸如流 媒体分发等的应用中加以使用，优选那些物理位置与自己更近，链路更短的节点。 这种方案在一定程度上节约了网络带宽，减少了下载时间。 这些研究主要是通过预测节点距离来构建层叠网拓扑，不可避免地与真实的 网络拓扑环境存在差异。我们将感知模块部署在网络设备之上，通过感知a s 间的 跳数、转发路径和时延，基于测量结果构建真实的网络拓扑，并且以服务的形式 提供给层叠网应用，提高层叠网应用的效率。 1 2 3a s 拓扑感知研究 目前，国内外对a s 拓扑感知进行了很多研究，采用的方法分为两类：基于 b g p 信息的方法和基于t r a c e r o u t e 【3 9 1 探测的方法。基于b g p 信息的方法采用分析 b g p 路由表中的路径属性或b g p 更新报文来构造a s 级拓扑图。例如，美国o r e g o n 大学的r o u t ev i e w s 项卧3 5 1 较早开展了i n t e m e ta s 级拓扑研究；hc h a n g 等【2 3 1 基于 b g p 表进行了a s 路径推断的研究。而基于t r a c e r o u t e 探测的方法首先采用 t r a c e r o u t e 探测得到i p 级转发路径，然后通过将i p 地址映射到相应的a s 得到a s 级拓扑。c a i d a 的s k i t t e r 项目以及z m a o 掣2 4 】采用主动探测与b g p 信息结合的 方式构造出较完整的a s 级拓扑图。 本文采用分析b g p 路由表中路径属性的方法来感知a s 拓扑，获得以此a s 为源的树形转发路径。相比拓扑的完整性而言，我们更关注路径的准确性，因此 这种方法适合于我们的研究。 1 3 本文的工作 本文主要面向层叠网应用，基于面向网络设备控制平面感知体系结构，设计 实现了基于b g p 协议路由信息的a s 网络拓扑感知模块和公共时延感知服务模块。 在a s 网络拓扑感知模块中，针对b g p 协议路由收敛慢的问题，提出了一种故障 路径快速感知算法；在时延感知模块中，根据层叠网应用的特点，构建了时延缓 冲区，多次测量节点时延，使感知结果更接近于真实状况；并且构建实验环境， 对a s 级别的感知结果进行模拟分析。结果表明，我们的系统确实达到了减少资源 消耗，节约带宽，提高应用效率的目的。 本文共分为六章。 1 4 本文的组织结构 第6 页 围防科学技术人学研究生院硕十学何论文 第一章，绪论。首先介绍了本文的课题背景，分析了在层叠网络体系结构中 应用网络感知技术的必要性；其次介绍了层叠网的特点，和面向层叠网感知技术 的发展概况；在网络感知技术相关研究中，介绍了近些年来国内外对网络感知技 术的研究成果，提出了采用分析b g p 路由表中路径属性的方法，通过测量实际的 a s 间跳数和时延，构建层叠网拓扑的研究目标；最后介绍了本课题的主要研究内 容和论文的主要结构。 第二章，设备控制平面感知模块体系结构。本章介绍了网络感知层体系结构， 并根据此结构提出了设备控制平面感知模块体系结构，还定义了相应的网络感知 接口原语。 第三章，网络感知关键算法研究。本章就如何得到a s 间最小跳数和转发路径， 路径失效时如何进行快速感知，以及如何准确感知节点时延等问题进行了研究， 提出了相应算法。 第四章，基于q u a g g a 的网络感知模块的设计与实现。介绍了基于q u a g g a 的 网络感知系统实现结构，基于z e b r a 协议的网络感知服务接口的设计与实现，在 q u a g g a 软件上基于b g p 协议设计实现了网络拓扑感知模块，以及网络时延测量与 查询模块。 第五章，性能测试与分析。构建测试环境，进行试验与测试，对试验结果进 行分析，并得出结论。 结束语。总结本文完成的主要工作，存在的不足，并为下一步研究指明方向。 第7 页 国防科学技术大学研究生院硕十学何论文 第二章设备控制平面感知模块体系结构 将网络感知技术运用于层叠网络，可以提高层叠应用服务的效率，然而为了 得到底层物理网络的信息，这些层叠网应用经常使用p i n g 或者t r a c e r o u t e 来进行网 络探测，感知底层物理网络拓扑，获取网络节点问的距离、时延等信息，并基于 这些探测结果来构建层叠网拓扑。上述方法存在明显的不足：当多重层叠网运行 在单一的节点，或者相同的子网上时，这些层叠网应用独立地探测i n t e m e t 会带来 很大的开销，比如，在p l a n e t l a b t 引j 上，通过p i n g 探测i n t e r n e t 产生的流量大约l g b 天，等同于在有1 2 5 个节点的网络上，每个节点每秒都产生一个p i n g 。虽然计算 一个层叠网络能够支持多少个层叠服务，或者p i n g 占据了多少总带宽是困难的， 但是每个层叠服务独立地探测网络是不可行的。 因此在层叠网架构中需要引入网络感知层，网络感知层是建立在物理网络之 上，用于感知网络状态的虚拟层，最初是为简单路由和存储而设计的，现在j 下在 被用于分布式网页缓存，内容分发，流媒体处理等网络感知应用，它能根据不同 的层叠网应用对物理网络进行感知，抽取不同级别的拓扑信息，对网络的节点跳 数、时延、带宽、丢包率等指标进行优化来提高应用的性能，减少层叠网络探测 开销。 2 1 网络感知层体系结构 网络感知层体系结构包括三层，从下至上依次分别为：底层物理网络，网络 感知层，层叠网应用服务层。网络感知层体系结构如图2 1 所示。 层叠网应用服务 网络感知层 底层物理网络 图2 1 网络感知层体系结构 各层实现的功能介绍如下： 第8 页 国防科学技术人学研究生院硕十学何论文 1 ) 底层物理网络，主要指i n t e r a c t ，以及各种内部网络，专用刚络等，是构建 网络感知层的基础。它有以下基本特征： 【1 】相对稳定性。不管是整个i n t e m e t ，还是一个自治域，或是小规模的专 用网络，都具有相对稳定的特性。比如，在i n t e m e t 中，虽然很多节 点在不断变化，但a s 的划分是相对稳定的；相对地，在一个自治域 中，核心路由器也是很少变化的；而那些小规模的专用网络在设计之 初就有了明确的拓扑结构，除非改动设计，否则他们不会变化。 【2 】动态性。对于较大规模的网络来说，网络中的节点又是不断变化的。 比如，i n t e r n e t 几乎没有网络拓扑相同的两个瞬间；即使是小规模的网 络，在不同时段，不同任务的情况下，网络拓扑也是不同的，只不过 变化的频率相对小得多。 底层物理网络的特征提示我们，对物理网络进行探测时，根据所构建网络 拓扑级别的不同，探测的频率应该是不同的，这也就导致了探测开销的不 同。 2 ) 网络感知层，是建立在底层物理网络之上，用来感知网络状态的虚拟层。 它能根据层叠网服务应用的不同需求，从底层网络抽取不同级别的网络拓 扑信息，完成下列基本操作： 【l 】感知网络的连接拓扑( 比如a s 级别，路由器级别) 和范围( 比如 i n t e m e t ，a s 的数量，n 跳能到达的范围半径等) ： 【2 】探测一个包从一个节点到另一个节点的实际路径( 比如经过a s 的顺 序，路由器顺序等) ； 【3 】提供两个节点间指定路径的实际距离( 比如a s 跳数，路由跳数，标准 时延等) 。 以上列举了网络感知层应该完成的一些基本操作，由于底层网络是不断变 化的，因此为了得到最新的网络信息为上层应用提供服务，网络感知层就要不 断地进行探测。 网络感知层的引入有如下好处： 【1 】减少了探测丌销。传统的层叠网技术，应用服务直接探测底层网络， 会带来较大丌销；尤其是具有相似性的多个层叠服务同时运行时，各 自独立地重复探测，更引入了大量不必要的丌销，严重浪费资源。而 网络感知层的引入，使得探测的网络拓扑等信息可以被层叠服务所共 享，减少了资源消耗，提高了应用效率。 【2 】对网络的感知更加及时、准确。网络感知层从层叠应用服务中分离出 来，能够更有效地监测网络状态，当网络产生变化时，能够更加及时、 第9 页 国防科学技术人学研究生院硕十学 奇论文 准确的处理，向1 i 会影响应用的其它部分。 3 】便于模块化、设备化，发挥网络设备平台的固有优势，进一步提高系 统的整体应用效率。 3 ) 层叠网应用服务，是指运行在层叠网之上的诸如会话控制服务，应用组播 服务，应用路由服务等网络应用，网络感知层的引入能为这些应用带来明 显的好处，有效提高应用效率。层叠网应用服务一般具有以下特点： 1 】支持大规模应用服务。层叠网上运行的网络应用很多是大规模的，甚 至是全球性的，比如p l a n e t l a b 全球性的互联网实验平台，就是构 建在i n t e m e t 上的层叠网大型应用。 【2 】对物理网络依赖性大。由于需要底层物理网络来路由信息，分发资源， 优选节点等，所以就需要不断地得到网络的拓扑信息，底层物理网络 的任何变化，都会对应用产生影响。网络感知层的引入增加了对上下 层的接口，分离了部分功能，使得层叠网应用只需要利用接口与网络 感知层交换消息即可，大大简化了其结构复杂性。 【3 】具有良好的健壮性。层叠网应用服务在运行过程中，不会因为某个节 点( 甚至是关键节点) 或者某段链路的故障而瘫痪，它会及时地找到 替代节点和路由重建网络，保证应用的f 常运行。 网络感知层的提出，为网络感知技术的进一步研究发展提供了有利条件， 为我们的研究提供了指导，为进一步提高感知效率打下了良好基础。 2 2 设备控制平面感知模块体系结构 我们借鉴网络感知层体系结构，在路由器设备上构建网络设备感知服务层， 实现a s 级别的网络拓扑感知功能。 设备控制平面感知模块体系结构包括四层，由下至上依次分别为：报文转 发平面、路由器控制平面、网络设备感知服务层及层叠网应用服务层。设备控 制平面感知模块体系结构如图2 2 所示： 第l o 页 国防科学技术人学研究生院硕十学何论文 屋叠网廛用服务 | j 囡。，圆图盼 7 ：j 嘲灭j 内容l | 流媒i j 其，i 舅 l 剿。，l 型烈l 氅ji 服务i 。 网络感知服务接u j 。网络设鍪感知服务层 i j 感知模块li 时模块知il 歹，。一l ，。? 习 路由器控制平面 ? 甲。”；一1 j i 。p。 灞 报文转发平面 j i j 。，。一p ，。， j ? 。i j ，编 豳2 2 设备控制平面感知模块体系结构 各层实现的功能及操作介绍如下： 1 ) 报文转发平面，主要指实现报文转发所需的基础网络环境，是构建网络设 备感知服务层的基础。它为上层提供原始的网络拓扑等信息，并在上层的 控制之下，在各个子网、路由器、节点之间转发报文，实现具体的数据传 输操作。对于较大规模的网络来说，它是不断变化的，因此在进行网络感 知时要不停地监测物理网络的变化，抽取最新的网络拓扑信息。 【1 】基础网络环境，即底层物理网络。指通过实际的网络设备连接而成的 网络实体，及实现报文转发所必需的网络协议等，用来解决网络层以 下的数据传输问题，并通过接口为上层提供感知所需的原始网络信息。 2 】实现上层操作控制。通过接口接收上层控制信息，在物理网络上实现 数据信息可靠传输。 2 ) 路由器控制平面，执行路由协议，在路由节点问交互路由可达信息，形成 域内和域问路由转发表。 3 ) 网络设备感知服务层，建立在路由器控制平面之上，实现了网络感知的具 体功能。它能根据应用服务的不同需求从底层物理网络抽取网络拓扑信 息，找到跳数最小的节点，进行时延探测等，根据这些感知结果来优化网 络应用。主要包括： 【l 】网络拓扑感知模块。网络拓扑感知模块主要实现对底层网络拓扑的感 知，根据应用的不同要求，可以分别感知不同级别的网络拓扑，比如： 第l l 页 国防科学技术人学研究生院硕十学1 _ 7 ：论文 感知a s 级别的网络拓扑，路由器级别的网络拓扑，节点级别的网络 拓扑等。本文主要实现对a s 网络拓扑的感知。 【2 】时延感知模块。节点问时延是指源节点发送数据包到收到目的节点应 答数据包的时间，它可以综合反映节点间距离的远近。我们可以通过 在i p 协议层测量r t t 来感知网络节点问的时延大小，为相关应用提 供支持。 【3 】网络感知服务接口，通过接口实现网络设备感知服务层与层叠网应用 服务层的信息传递，层叠服务首先通过接口向网络设备感知服务层发 送相关请求，根据请求内容，网络设备感知服务层调用相应感知模块， 来实现相关的服务原语，感知底层物理网络相关信息，按照规定格式 发送给层叠服务；同时为了保证网络信息的可用性、一致性，网络设 备感知服务层按照一定的频率不断地感知网络相关路由信息。 4 ) 层叠网应用服务，是指以层叠网为基础的，运行在层叠网之上的诸如网页 缓存，内容分发，流媒体服务等网络应用，网络设备感知服务层能为这些 应用带来明显的好处，有效提高应用效率。 设备控制平面感知模块，在路由器设备上实现了网络感知功能，将虚拟的网 络感知层实体化，不仅继承了网络感知层的优点，而且与设备结合更加紧密，安 全性、稳定性都更好。 2 3 网络感知接口原语定义 在网络设备感知服务层实现的网络感知功能，它们主要通过网络感知服务接 口为上层提供服务，相关功能通过如下原语操作来实现： 1 ) 感知物理网络的a s 拓扑 n t = g e t n e t t o p ( ) n t 为网络感知的拓扑图，n t 图中的每一个点代表一个a s ，每一条边代表 a s 间的对等节点连接。我们构建n t 图的策略是只要在自治域x 、y 之间探测到 任一方向的路径，就在n t 图上增加一条双向的边。 a s 节点 一寻径路线 图2 3a s 拓扑路径探测图 第1 2 页 国防科学技术人学研究生院硕十学位论文 我们通过g e t n e t t o p 操作来获得源a s 的网络拓扑信息，根据拓扑信息町以 得到到目的a s 的最短转发路径，而这样的拓扑信息是相对稳定的，因此只需要较 低的探测频率来维护，为进一步的探测和上层服务应用提供了支持。 2 ) 感知本地a s 到目的a s 的跳数 s i n g l e h o p s = g e t s i n g l e h o p s ( d e s ) s i n g l e h o p s 代表从本地a s 到目的a s 的跳数，通过跳数来估计本地a s 到目 的a s 的距离，为相关应用提供支持。虽然此原语操作仅仅是通过单点跳数来近似 地表示距离，但对于很多应用是合适的，比如，想要最小化路径经过的a s 数量； 或者找到没有共享节点的多条独立路径，进行路径备份，避免应用中的链路瓶颈 与单点失效等问题。在那些需要保证服务质量的应用中，为了更有效地利用资源， 只有那些跳数小于i 的a s 才会被选择【2 5 1 。我们可以使用此原语操作来得到候选 a s 的列表，并将列表中节点排序，使靠前的节点有更小的跳数，用来改进很多层 叠网应用服务。 3 1 通过节点间时延来描述距离 d e l a y = g e t d e l a y ( s r g ，d e s ) 本地节点可以p i n g 目标节点，得到相应的往返时延。其结果能够被缓存，用 来回应之后的查询，这个原语操作对于识别节点的远近是非常有用的。而且通过 时延描述的距离较之跳数表示的距离更加精确，更能反映网络的实际状况，缺点 是p i n g 会造成一定的探测开销，特别是当网络规模较大时会消耗较多资源。 4 ) 事件订阅原语 n o t i f i c a t i o n r e s u l t = g e t r