（计算机软件与理论专业论文）用动态生成树改进无线网状网.pdf

中山大学硕士学位论文用动态生成树改进无线网状网 用动态生成树改进无线网状网 专业：计算机软件与理论 硕士生：赵辉 指导教师：姜云飞教授 摘要 无线网状网是近年来迅速发展起来的一种新技术，它解决了当前无线局域 网覆盖范围小、可靠性差等缺点。无线网状网的无线访问点( a c c e s sp o i n t ) 之 间通过无线方式组成网状结构，提供了很好的链路冗余，提高了可靠性，并且这 些访问点是自组织、自配置、自恢复的。无线网状网组网简单，具有良好的可扩 展性。 无线访问点之间的无线链路叫做t l ( t r a n s i tl i n k ) ，虽然无线访问点之间通 过t l 组成了网状结构，但实际的数据传输只使用了部分t l ，很多“闲置”t l 上并没有实际数据的传输，可是这些“闲置”的t l 也需要分配资源，造成了资 源的浪费和整体性能的降低。本文通过对无线网状网进行“剪枝”“剪”掉 “闲置”的t l 以提高资源的利用率，从而增加其它t l 上的数据吞吐率。通过“剪 枝”，无线网状网变成了“无线树状网”，称之为动态生成树。本文通过对开放的 最短路径优先( o s p f ) 协议进行少量修改来实现“剪枝”，同时对“剪枝”后带 来的新问题进行分析，并给出了解决方法。 最后，对提出的方法进行实验以验证该方法是否可以正确的对无线网状网 进行“剪枝”，以及“剪枝”后是否可以提高资源的利用率。 关键词：无线网状网，传输链路t l ，无线访问点，剪枝 中山大学硕士学位论文用动态生成树改进无线网状网 i m p r o v e w i r e l e s sm e s hn e t w o r k u s i n gd y n a m i cs p a n n i n gt r e e m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z h a oh u i s u p e r v i s o r ：p r o f e s s o rj i a n gy u n f e i a b s t r a c t w i r e l e s sm e s hn e t w o r k ( w m - n ) i san e wt e c h n o l o g yt h a td e v e l o p sr a p i d l yt h e s e y e a r s ；i ts o l v e st h es h o r t a g e so fc u r r e n tw i r e l e s sl o c a la r e an e t w o r k s ( w l a n ) ，s u c h a ss m a l lc o v e r a g ea n dl o wr e l i a b i l i t y t h ea c c e s sp o i n t s ( a p ) o fw i r e l e s sm e s h n e t w o r kf o r mam e s ht o p o l o g yu s i n gw i r e l e s sl i n kw h i c hb r i n g sh i 曲r e d u n d a n c yo f l i n k sa n dh i g hr e l i a b i l i t y t h e s ea c c e s sp o i n t sa r es e l f - o r g a n i z e 、s e l f - c o n f i g u r ea n d s e l f - r e c o v e lw i r e l e s sm e s hn e t w o r ki se a s yt ob u i l da n dh a sw e l le x t e n s i b i l i t y t h ew i r e l e s sl i n kb e t w e e na c c e s sp o i n t si sc a l l e dt r a n s i tl i n k ( t l ) a l t h o u g ha c c e s s p o i n t sm a k eu s eo ft lt of o r mam e s ht o p o l o g y , n o te v e r yt li su s e db yu s e rt r a f f i c ， t h a ti s ，t h e r ea r em a n yi d l et l s r a d i ot i m ea n dc p ut i m eh a v et ob ea s s i g n e dt oi d l e t l sw h i c hl e a d st oaw a s t eo fr e s o u r c e s t h ep a p e rp r u n e si d l et l st oi m p r o v et h e t h r o u g h p u to fn o n i d l et l s b yp u n n i n g ，w i r e l e s sm e s hn e t w o r kc h a n g e st ob e “w i r e l e s st r e en e t w o r k ”，t h en e wg e n e r a t et r e ei sc a l l e dd y n a m i cs p a n n i n gt r e e t h ep a p e ri m p l e m e n t sp u n n i n gv i ad o i n gs o m es m a l lc h a n g e so no p e ns h o r t e s tp a t h f i r s tp r o t o c o l ，i ta l s oa n a l y s i st h es i d ee f f e c to fp r u n i n ga n df i n dt h es o l u t i o nt oa v o i d i t a tl a s t ，t h ep a p e rd o e sa ne x p e r i m e n tt os h o ww h e t h e rt h ep r u n i n gm e t h o dc a l lw o r k a n dw h e t h e rt h ep r u n i n gc a ni m p r o v et h et h r o u g h p u to f n o n i d l et l s k e y w o r d s ：w i r e l e s sm e s hn e t w o r k ，t r a n s i tl i n k ，a c c e s sp o i n t ，p r u n e i i 中山大学硕士学位论文用动态生成树改进无线网状阐 1 1 论文背景 第1 章绪论 近年来，无线局域网( w i r e l e s sl o c a la r e an e t w o r k ，w l a n ) 在宽带无线 接入领域中得到了迅速发展，依其所具有的巨大数据传输率，w l a n 也被认为是 3 g 或3 g 后移动数据通信技术的一个主要竞争对手。 如今，基于i e e e8 0 2 1 1 系列协议的无线局域网技术已经成熟并逐渐普及， 无线网卡已经很便宜，各种新型移动终端( p d a ，笔记本电脑等) 普遍支持8 0 2 1 l 系列规范。通过大规模在城市公共环境中如商场、车站、机场等部署无线局域网 接入点( a c c e s sp o i n t ，a p ) 可以很方便的为用户提供高速i n t e r n e t 接入和移 动办公服务，甚至高质量的语音服务。 但w l a n 也有其不足之处，其中最主要的一个便是无线接入点的覆盖范围较 为有限，若要在一个相对较大的区域提供无线覆盖，就需要在该地区内配置大量 接入点，但每个接入点都要通过线缆接入有线网络，因而增加了建设基于w l a n 的公共宽带接入网的成本。所以当前w l a n 一般都部署在室内，、信号只能覆盖建 筑物内部空间，若要在室外进行大规模的部署面临很大困难，如成本高、布线工 作量大等。 当前w l a n 的缺点还包括冗余度低、可靠性差、不支持移动设备在a p 间的漫 游等。 为了解决w l a n 的上述不足，一种新的宽带无线接入技术无线网状网应 运而生。无线网状网中无线接入点( a c c e s sp o i n t ，a p ) 之间组成了一种动态的 网状结构，并且无线接入点之间使用无线连接，有效的降低了无线接入点对于有 线网的依赖，极大的降低了网络部署的工作量。由于网状结构能够有效增加链路 冗余，显著的提高了整个系统的可靠性。同时无线网状网还具有可扩充性强，无 线接入点之间自组织、自恢复，能够支持移动终端在无线接入点之问的漫游等诸 多优点。 由于无线网状网具有的诸多优点，它已经被业内普遍认为是宽带无线网络接 入技术的重要发展方向，美国 t e l e c o m m u n i c a t i o n s 杂志更是把它评为2 0 0 4 年十大热门通信技术之一。同时众多厂商也陆续推出了基于无线网状网的解决方 案。 本文通过“剪枝”对无线网状网进行改进，在不影响无线网状网功能的前提 下，提高其资源利用率，改善性能。 1 2 无线网状网的基本工作原理 为了引出要解决的问题，这里简要介绍无线网状网的基本原理，第3 章将会 详细介绍。 图1 1 是无线网状网中的一个典型的拓扑结构，图中有两种无线接入点：一 种有一条以太网线接入有线网络的叫n e t w o r ka p ，简称n a p ；一种没有任何有 中山大学硕士学位论文 用动态生成树改进无线网状网 线连接叫s t a n da l o n ea p ，简称s a p 。可以看到，无线网状网中大部分的无线接 入点都是s a p ，n a p 只占很小的一部分。所有的无线接入点都可以为移动终端 ( m o b i l en o d e ，m n ) 提供宽带无线接入服务，既移动终端通过无线接入点接入 有线网络。无线接入点把m n 发上来的所有数据包通过邻居无线接入点转发给 n a p ，最终转发到有线网络。由于到达n a p 的路径上经过了多个空中无线链路， 而空中无线链路是不安全的，很容易被监听，所以为了保证数据安全，每个a p 都会建立一条到有线网的i p s e c 隧道口h ”，a p 把所有移动终端发上来的数据包都 使用i p s e c 隧道发送到有线网，然后再由有线网根据原始数据包的目的地址决定 下一步路由。 无线接入点和m n 之间使用8 0 2 1 l b g 协议建立无线链路，称为a c c e s sl i n k ， 简称a l 。无线接入点之间使用8 0 2 1 1 a 协议建立无线链路，称为t r a n s i tl i n k ， 简称t l 。 在无线网状网中无线接入点之间是自组织，自恢复的。自组织是指无线接入 点之间能够自动的发现“邻居”，并选择合适的邻居建立无线链路，同时确定到 有线网络的最佳路由。自恢复是指当网络中的某个无线接入点或某条无线链路发 生故障时，整个网络可以自动迅速调整路由，重新达到平衡。 所有的a p 都使用开放的最短路径优先协议【4 】( o p e ns h o r t e s tp a t hf i r s t ， o s p f ) 来找到到达有线网络的最佳路由。第2 章会详细介绍o s p f 协议的工作 原理。 一般来说，每个a p 上只有一块无线网卡( r a d i oc a r d ) 来收发t l 的无线信 号，同时由于其它硬件限制，每个a p 只能与有限个邻居各建立一条t r a n s i tl i n k 。 例如后面用到的系统中，每个a p 最多只能有3 个t l 。因为这些t l 共用一套底 层硬件，所以t l 越多，每个t l 上收发数据包的能力就会相应降低。 图1 一l 中山大学硕士学位论文 用动态生成树改进无线网状网 1 3 问题的提出 由于使用了i p s e c 进行加密，a p 上收到的所有移动终端发上来的数据包都会 被打上一个i p s e c 数据包头部，i p s e c 数据包头部的i p 地址是i p s e c 隧道对端的 i p 地址( 无线网关的地址) ，而原始数据包被当作普通数据进行加密，i p s e c 数据 包( 上行) 的结构如图1 2 所示。 图l 一2 o s p f 协议计算出最短路径后，a p 就根据到有线网的最短路径选择下一跳地 址，并将所有的收到的移动终端的原始数据包打包成i p s e c 数据包然后转发给该 地址。我们发现网络中有很多t r a n s i tl i n k 并没有数据包的传输，在网络拓扑结 构稳定的情况下，所有的数据包都走固定的路径到达有线网络，如图l 一3 中红色 实线所示。图中虚线部分虽然有t l 的建立，但是并没有任何数据包的传输，处 于“闲置”状态。但是为了维护这些t l ，a p 上的调度器仍然需要分配时间片( t i m e s l o t ) 给这些t l ，使得其他真正有数据包传输的t l 所分配的时间片减少，造成 了资源的浪费和性能的下降。 中山大学硕士学位论文 用动态生成树改进无线网状网 为了把有限的资源尽量分配给有数据包传输的t l 以提高性能，我们希望将 这些“闲置”的t l “剪”掉。也就是说对无线网状网进行“剪枝”，最后使它变 成“无线树状网”，如图1 - 4 所示。 图1 - 4 对无线网状网进行“剪枝”后，可能会造成新的问题。网状结构具有很好的 链路冗余特性，这也是无线网状网的优势之一，但是树状结构没有这样优良的特 性，任何两点间有且仅有一条通路。我们把它减成“无线树状网”之后，如果某 个a p 或某条t l 失效，将会使部分a p 失去到有线网络的连通性，造成局部服 务中断，这是我们的解决思路不得不考虑的问题。如图1 5 所示，如果某条t l 因为某种原因断开，此时该t l 下面的两个a p 将失去到有线网的通路，造成它 们两个无法为移动终端提供接入服务。在对无线网状网“剪枝”以提高性能的同 时，不能牺牲无线网状网链路冗余度高，可靠性好的优点。所以需要采取某种方 法来解决这个问题。 中山大学硕士学位论文用动态生成树改进无线网状网 1 4 基本解决思路 图1 5 要对无线网状网进行“剪枝”，可以手工对每个a p 进行“剪枝”，即通过命 令行或网管软件对a p 进行“剪枝”操作。但无线网状网具有良好的可扩充性， 它在同一个网络里支持几十个甚至上百个a p ，这时t l 的数目就更多，手工“剪 枝”的工作量极大并且容易出错，更重要的是手工“剪枝”无法适应网络拓扑的 变化，因此必须使用一种自动的方式来实现“剪枝”。上面提到无线网状网的a p 之间是一种动态的网状拓扑结构，并具有良好的可扩展性。所以“剪枝”必须能 够适应这种动态性，必须能够随着网络拓扑结构的变化而变化。 仔细观察图1 4 可以发现，对于每一个n a p 来说，它总是和它下方的一些 s a p 组成一棵树，在图中我们可以看到3 棵树。为了显示的更直观，我们把图 1 - 4 中右边那棵树中的s a p 和t l 进行编号，如图1 - 6 所示。 对于一棵树，它有这样的性质：顶点数= 边数+ 1 。在图1 - 6 的树中，除去 根结点n a p ，恰好每个结点对应一个边，即每个s a p 对应一个t l ，如s a p 5 对 应t l 5 ，s a p 4 对应t l 4 等。所以只要每个s a p 记住与它对应的t l 并通知该 t l 的对端保留该t l ，然后“剪”掉所有其它t l 就可以完成对无线网状网的“剪 枝”。具体来说，对于每个s a p ，它除了以下两种情况的t l 外，“剪”掉所有与 它邻接的t l 。 1 与它对应的t l 。 2 被邻居s a p 通知保留的t l 。 例如，对于图1 6 中的s a p l 来说，它保留与它对应的t l l 以及被s a p 3 通 中山大学硕士学位论文 用动态生成树改进无线网状网 知保留的t l 3 ，然后“剪”掉所有其它与它相邻接的t l ，既s a p i 与s a p 2 之 间的t l 。 仔细观察可以发现，与某个s a p 对应的t l 其实就是由o s p f 协议计算出来 的该s a p 到达有线网络最优路径的下一跳所要经过的t l ，例如对于s a p | 来说， o s p f 协议计算出它到达有线网络的最优路径是经t l l 到达n a p ，而不是先走 到s a p 2 再经t l 2 到达n a p 。 图1 6 为了保持无线网状网的高可靠性，防止“剪”成树状网后，因为某个s a p 或 某条t l 失效后造成部分s a p 失去到有线网的连通性的问题。s a p 在“剪”掉 多余的t l 时要保留该t l 的一些相关信息，以便在需要时快速的重新建立该t l 。 具体来说，每个s a p 都维护一个邻居列表，当该s a p 将某个t l “剪”掉时， 它并不把t l 对端的邻居从表中删除，而是将该邻居的状态置为”睡眠”，如果某 个邻居处于“睡眠”状态，s a p 就不允许自己与该邻居建立t l ，既该邻居暂时 被“隔离”。当s a p ( 通过o s p f ) 检测到某个被隔离的邻居不在自己的路由表 中时，它就“唤醒”该邻居允许该邻居与自己建立t l 。 如图1 7 所示，t l ! 因为某种原因而断开，此时s a p l ，s a p 3 ，s a p 4 ，s a p 5 都失去了到有线网的连通性，造成接入服务中断。s a p l 和s a p 2 之间之前曾经 建立过t l ，但后来被“剪”掉，此时它们彼此在对方的“邻居”列表里，但处 于“睡眠”状态。当t l l 断开后，n a p 和s a p l 立刻检测到这种情况，此时运 行在所有a p 上的o s p f 协议重新计算路由表，之后s a p l 发现s a p 2 已经不在 自己的路由表中，于是它将“邻居”列表中的s a p 2 “唤醒”，同样s a p 2 在重新 计算路由表后也发现s a p l 不在自己的路由表中，于是它将“邻居”列表中的 s a p l “唤醒”。此时，s a p i 和s a p 2 在彼此的邻居列表中都是“唤醒”状态， 它们之间可以快速重新建立起t l ，如图1 8 所示。 中山大学硕士学位论文用动态生成树改进无线网状网 图1 7 1 5 本文的工作 图1 8 本文主要做了如下几方面的工作： 1 介绍了无线网状网的优势，同时分析了其存在的问题一一有一些空闲的 t r a n s i tl i n k 没有用来传输数据包，造成资源浪费。 2 通过对无线网状网中的一些“闲置”的t l 进行“剪枝”，来提高资源利 用率以提高性能。 3 分析了“剪枝”过程中带来的新问题可能造成某些a p 因为其它a p 或t l 失效而失去到有线网的连通性，并给出了问题的解决方法。 4 给出了上述解决方法的软件实现。 5 最后，通过一个实验检查“剪枝”的解决方法是否能够正常工作，以及 “剪枝”后资源利用率是否提高。 1 6 本文的组织 本文的组织如下： 第l 章介绍论文背景，同时引出本文要解决的问题，并给出了解决问题的基 本思路。 第2 章介绍了本文中用到的开放的最短路径优先协议( o s p f ) 。 第3 章介绍无线网状网的基本运行原理 第4 章详细介绍了本文要解决的问题，解决问题的基本方法以及解决方法的 软件实现。在本章最后做了实验来检查解决方法是否能够正常工作。 第5 章是前景与展望。 中山大学硕士学位论文用动态生成树改进无线网状网 第2 章开放的最短路径优先协议 2 。1 协议介绍 o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 是由因特网工程任务组i e l 、f ( i n t e r n e t e n g i n e e r i n gt a s kf o r c e ) 开发用来代替问题多多的r i 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 ) ，用于在单一自治系统( a u t o n o m o u s s y s t e m ，a s ) 内决策路由。 o s p f 是一个链路状态协议，它使用d i j k s t r a 算法，并且它是开放的，不属 于任何的厂商或组织。最新的版本是版本2 ，它在r f c 2 3 2 8 中定义。与r i p 相反， o s p f 是链路状态路由协议，而r i p 是距离向量路由协议。 像所有的链路状态协议一样，o s p f 相对于r i p 的优点是快速收敛，支持更大 规模的网络，对错误路由信息的敏感度低等等。 o s p f 的其它特性如下： 1 引入了区( a r e a ) 的概念。这减少了协议对内存和c p u 的占用，减少了 协议所需交换的数据量，使建立层次性的网络成为可能。 2 完全支持无类( c l a s s l e s s ) 路由。 3 支持任意的链路耗费( c o s t ) 。 4 支持等值路径的负载平衡，提高带宽利用率。 5 使用保留的多播地址，减少对其它非o s p f 网络结点的影响。 6 支持路由器之间的认证。 2 2 基本原理 o s p f 是这样工作的”： 1 运行o s p f 的路由器向所有运行o s p f 协议的接口发送l t e l l o 消息。如果 一个接口收到的h e l l o 消息中所包含的某些参数与自身接口配黄的这些参数 相匹配，它们便成为“邻居”。 2 有些邻居之间会建立邻接关系。邻接关系的建立依赖于路由器的类型和 连接它们的网络的类型。 3 每一个路由器都会向所有与它邻接的路由器发送链路状态通知( l s a ， l i n ks t a t ea d v e r t i s e m e n t ) 。l s a 包含了该路由器所有的接口信息，包括 i p 地址、子网掩码、链路耗费等。 4 每一个收到l s a 的路由器都把该l s a 保存在自己的链路状态数据库中， 并将该l s a 转发到其它所有邻接接口。 5 通过l s a 在整个区的扩散，区内所有路由器的链路状态数据库都会保持 致。 6 当得到整个链路状态数据库后，每个路由器以自己为“根”，使用 d i j k s t r a 算法计算到所有其它结点的最短路径。这就是最短路径树 ( s h o r t e s tp a t ht r e e ，s p f ) 。 中山大学硕士学位论文用动态生成树改进无线网状嘲 7 每一个路由器根据上面计算出的最短路径树来构造路由表。 当所有的链路状态通知都在区内扩散完毕后，各个路由器的链路状态数据库 都已经同步了，这时0 s p f 就是一个安静的协议，h e l l o 消息只在邻居之间用来 k e e p - a l i v e ，而l s a 每3 0 分钟更新一次。只要网络拓扑结构稳定，就不会有更 多的协议消息发送。 0 s p f 是一个动态路由协议，当网络拓扑结构改变时，0 s p f 能够迅速的发送 新的l s a ，进而更新链路状态数据库，之后计算最短路径树，构造路由表，从而 达到新的平衡。 o s p f 的运行原理是很简单的，但实现起来却很复杂，下面几节将介绍本文 中用到的一些概念。 2 3 邻居与邻接 在发送l s a 之前，o s p f 路由器必须先发现它的邻居并建立邻接关系，l s a 只在具有邻接关系的路由器之间发送。每一个o s p f 路由器都维护一个邻居列 表，这个列表主要记录以下几项信息： n e i g h b o r n e i g h b o rn e i g h b o rs t a t e d e a d t i m e n e i g h b o r l i n t e r f a c e l i ! 望j ! ! ! 旦旦堕l 垒! 垒塑! n e i g h b o ri d 为该邻居的路由器i d ，每个路由器都有一个自治域内唯一的路 由器i d 。n e i g h b o rp r i o r i t y 表示邻居的优先级，我们暂时不考虑它。n e t g h b o rs t a t e 表示邻居当前的状态，o s p f 路由器为每个邻居维护一个状态机，我们也暂时不 考虑它。d e a dt i m e 表示多长时间后如果收不到该邻居发来的h e l l o 消息就认为 该邻居“死亡”，每次收到该邻居的h e l l o 消息后就重置该计时器。n e t g h b o r a d d r e s s 表示邻居的i p 地址。i n t e r f a c e 表示与该邻居相连的接口。 并不是所有的邻居都会建立邻接关系，这要根据连接它们的网络类型。o s p f 协议把网络分为5 类： 1 点到点网络。如t l 链路。使用一根线缆将两个路由器直接相连。 2 广播网络。如以太网，令牌环网。 3 非广播多路访问网络。如x - 2 5 。 4 点到多点网络。 5 虚链路。 在此我们只考虑点到点网络，因为我们a p 之间的t r a n s i tl i n k 都是点到点网 络，使用点到点网络连接的邻居都会建立邻接关系。 建立了邻接关系的邻居之间会相互交换l s a ，并转发收到的由其它路由器产 生的l s a 。 建立邻接关系需要一个复杂的链路状态数据库的同步过程，这里就不赘述 了。 中山大学硕士学位论文 用动态生成树改进无线网状网 2 4h e l l o 协议 h e l l o 消息主要起到如下作用： 1 用于发现邻居。 2 它传递一些参数给对方路由器，只有这些参数都匹配，它们才可以成为 邻居。 3 用于在邻居之间k e e p a l i v e 。 4 确保邻居之间双向通信的建立。 5 在广播网络和非广播多路访问网络之间选举指派路由器和备份指派路由 器。 运行o s p f 的路由器周期性从所有运行o s p f 协议的接口向外发送h e l l o 消 息。这个周期叫做h e l l o i n t e r v a l ，该参数是可以配置的。如果路由器在 r o u t e r d e a d i n t e r v a l 时间内没有收到某个邻居的h e l l o 消息，它就认为该邻居“死 亡”，显然r o u t e r d e a d i n t e r v a l 要大于h e l l o i n t e r v a l ，一般是后者的4 倍，它也是 可配置的参数。 h e l l o 消息里主要包括如下信息： 该h e l l o 消息始发路由器的r o u t e ri d 。 该h e l l o 消息始发路由器的a r e ai d 。 该h e l l o 消息始发接口的子网掩码。 该h e l l o 消息始发接口的认证类型和认证附加信息。 该h e l l o 消息始发接口的h e l l o i n t e r v a l 。 该h e l l o 消息始发接口的r o u t e r d e a d i n t e r v a l 。 该h e l l o 消息始发路由器的优先级。 指派路由器( d r ) 和备份指派路由器( b d r ) 。 一些标志位。 该h e l l o 消息始发接口认识的所有邻居的r o u t e r i d 的列表。 认证类型表示该消息始发路由器使用的认证类型。而指派路由器和备份指派 路由器只有在广播网络和非广播多路访问网络才用到。后面的解决方法正是利用 了备份指派路由器这个属性在点到点链路中始终为0 这个特性。 a r e a i d 用于表示一个a r e a ，只有a r e a i d 相同的接口才处于同一个区。 当一个路由器的某接口收到一条h e l l o 消息，它就检查该消息所包含的a r e a i d 、认证类型、子网掩码、h e l l o i n t e r v a l 、r o u t e r d e a d i n t e r v a l 等参数是否与该接 口的同名参数匹配，如果不匹配，就直接把该消息丢弃。否则，就认为该消息是 合法的。 对收到的一个合法的h e l l o 消息，该路由器就检查消息中的始发路由器的路 由器i d 是否已经存在于自己的邻居列表，如果存在就重置它的d e a dt i m e 计时 器。如果不存在，就利用h e l l o 消息中所包含的信息创建新的一条记录并加入邻 居列表。 收到的合法的h e l l o 消息中还包含始发路由器的邻居列表，如果接收路由器 在列表中发现自己的r o u t e ri d ，它就认为双向通信已经建立( 注意，此时对端 邻居不一定认为双向通信已经建立) 。只有建立了双向通信，邻接关系才能被建 中山大学硕士学位论文用动态生成树改进无线网状网 业。 2 5o s p f 的接口 在邻接关系建立之前，甚至在h e l l o 消息发送之前，o s p f 路由器必须了解 它自己的接口信息。 o s p f 路由器为每一个运行o s p f 协议的接口维护一个数据结构，该数据结 构包含如下信息： 该接口的i p 地址和子网掩码。 该接口的a r e a i d 。 整个路由器的r o u t e ri d 。 该接口所连网络的网络类型。 该接口的链路代价。 该接口的当前状态。 该接口的优先级。 指派路由器和备份指派路由器。 h e l l o i n t e r v a l 。 r o u t e r d e a d i n t e r v a l 。 h e l l o t i m e g 。 邻居路由器列表。 认证类型。 的。 在该接口发送的h e l l o 消息就是根据该接口数据结构中的当前参数值构造 2 6a r e a o s p f 协议引入了a r e a 的概念。通过将整个自治系统分割成若干个a r e a ，有 效的降低了o s p f 协议对于内存和c p u 资源的占用，同时减少了协议数据在网 络中的传输。 链路数据库的同步只需要在同一个a r e a 中的各个路由器之间，每一个路由 器只需要在维护它所在a r e a 的链路状态数据库( 不包括边界路由器) 。有一个特 殊的a r e a 叫b a c k b o n e a r e a ，它负责将各个a r e a 的路由信息汇总。跨a r e a 的数 据包必须通过b a c k b o n ea r e a 进行中转。各个a r e a 通过a r e ai d 来区分。 如图2 1 所示，a r e a 0 是b a c k b o n e a r e a ，在它的下面连着两个普通的a r e a ： a r e a1 和a r e a1 0 5 5 3 1 6 。 中山大学硕士学位论文 用动态生成树改进无线网状网 图2 1 根据路由器所连接a r e a 的不同，可以把路由器分为如下几种 1 内部路由器。 2 a r e a 边界路由器( a b r ) 。 3 b a c k b o n e 路由器。 4 自治系统边界路由器( a s b r ) 。 内部路由器是指所有的接口都连接在同一个a r e a 的路由器。 a r e a 边界路由器将一个或多个a r e a 连接到b a c k b o n e a r e a ，它至少由一个接 口连接到b a c k b o n ea r e a ，并且它需要为每一个相连的a r e a 维护一个链路状态数 据库。所以，一般来说a r e a 边界路由器具有比一般路由器更多的内存和更快的 处理器。a r e a 边界路由器负责将它所连接a r e a 的拓扑结构信息汇总给整个 b a c k b o n ea r e a 。 b a c k b o n e 路由器至少有一个接口连接到b a c k b o n e a r e a ，显然a r e a 边界路由 器也是一个b a c k b o n e 路由器，一个内部路由器也可能是一个b a c k b o n e 路由器。 所以，一个路由器可能扮演着多种角色，可以属于多种路由器类型。 自治系统边界路由器至少有一个接口连接到自治系统外界，它可能向自治系 统内部注入一些从其它路由协议学习到的路由信息，如r i p 。 图2 2 显示了各种不同路由器类型在网络中的位置情况。 中山大学硕士学位论文用动态生成树改进无线网状网 2 7 扩散 图2 - 2 整个o s p f 自治系统的拓扑结构可以看作是由邻接关系而不是物理链路相连 的路由器组成。为了使每一个路由器都能构造出正确的路由表，每一个路由器对 整个网络的了解必须是一致的，即它们的链路状态数据库必须是相同的。 每一个路由器都能够通过h e l l o 消息认识到所有与它相连的邻居，并产生出 相应的链路状态通知( l i n ks t a t ea d v e r t i s e m e n t ，l s a ) 。每个路由器都会把它自 己产生的l s a 扩散到整个a r e a ，当a r e a 内所有路由器都完成这种扩散后，所有 路由器的链路状态数据库就同步了。当某个路由器发现网络拓扑结构改变后，它 就产生新的l s a 并扩散到整个a r e a ，来更新所有路由器的链路状态数据库。 扩散是通过以下两种类型的o s p f 数据包来完成：的： 1 l i n ks t a t eu p d a t ep a c k e t 。 2 l i n ks t a t ea c k n o w l e d g e m e n tp a c k e t 。 上面每一种数据包都可以包含多个l s a ( 如图2 3 ) ，虽然l s a 是在整个a r e a 中扩散，但上面两种数据包只能在具有邻接关系的路由器之问传递。 中山大学硕士学位论文用动态生成树改进无线网状网 u p d a t e l s a1 l s a2 - l s a3 ，r l s a4 图2 3 因为各个路由器之间维护相同的链路状态数据库对于o s p f 来说非常重要， 所以这种扩散必须是可靠的。发送l s a 的路由器必须知道这些l s a 是否被成功 接收，接收l s a 的路由器也必须知道收到的l s a 是否正确。 每一个发送的l s a 都必须被确认，确认可以通过显式的或隐式的两种方式 来实现。 显式确认是指接收到l s a 的路由器直接向发送路由器发一个l i n ks t a t e a c k n o w l e d g e m e n t 数据包。 隐式确认则是接收到l s a 的路由器如果有其它l s a 要发送给原路由器的话， 顺便把要确认的l s a 也放进l i n ks t a t eu p d a t e 数据包里发送回去，这样原发送 方就知道自己刚发送的l s a 被确认。 为了区分不同l s a 的新旧关系以确保链路状态数据库中包含l s a 的最新拷 贝，每一个l s a 都携带如下三种属性： 1 序列号。 2 校验和。 3 生存期。 o s p f 使用一个线性的序列号空间来标记每个l s a ，路由器每产生个新的 l s a ，它就把当前序列号加1 然后放迸l s a 中。 o s p f 使用1 6 位无符号整数来表示一个l s a 的生存期，生存期的有效范围 是0 3 6 0 0 ，用秒来表示，也就是说一个l s a 的最大生存期是一小时。l s a 在 经路由器转发以及存储在链路状态数据库的过程中，生存期都会逐渐增加，当达 到最大生存期后就会从数据库中删除。 2 。8l s a 的类型 因为o s p f 定义了多种不同的路由器类型，因此我们也需要定义多种l s a 类 型。例如，a r e a 边界路由器需要汇总一个a r e a 的拓扑信息然后扩散到整个 b a c k b o n ea r e a ，同时它也需要将其它a r e a 发送的汇总信息扩散到与它相连的所 有其它a r e a 。 表2 - 1 列出了所有o s p f 定义的所有l s a 类型。 中山大学硕士学位论文用动态生成树改进无线网状同 类型描述 1r o u t e rl s a 2n e t w o r kl s a 3n e t w o r ks u m m a r yl s a 4 a s b rs u m m a r yl s a 5a se x t e r n a ll s a 6 g r o u pm e m b e r s h i pl s a 7n s s ae x t e m a ll s a 8e x t e m a ja r t r i b u t e sl s a 9 o p a q u el s a ( 1 i n k l o c a ls c o p e ) 1 0 o p a q u el s a ( a r e a l o c a ls c o p e ) 1 1 o p a q u el s a ( a ss c o p e ) 表2 1 这里我们只介绍后面会用到的r o u t e rl s a 和n e t w o r ks u m m a r yl s a 。每个 r o u t e r 都会产生r o u t e rl s a ，这是最基本的l s a 。r o u t e rl s a 描述了始发路由 器的基本链路情况，包括每一条链路的状态、链路的耗费、网络类型、对端路由 器的i p 地址等基本情况。图2 - 4 显示了这种情况： t y p e # l r o u t e ri dt1 9 2 。1 6 8 3 0 。1 0 n u m b e r o f l k l k s 2 3 u n k1d e s c r i p o o n u n k 2 d e s c t 如t i o n l i n k3d a s c t f p t i o n 图2 - 4 图2 5 显示了某一个l s a 所包含的3 条链路的详细信息。 中山大学硕士学位论文用动态生成树改进无线网状网 l l n kc o n n o c t e dt o ：a n o t h e rr o u t e r ( p o i n t t o p o i n t ) ( l i n ki d n e l g h b o r i n gr o u t e r1 0 ：1 9 2 。，6 8 3 0 8 0 i l i n kd a t a ) r o u t e pi n t e r f a c ea d d r e s s ：1 9 2 1 6 8 。1 7 9 n u a b e po tt o sb 姆t r t c s ：o t o s0w e t t i c s ：6 4 i - 耋n kc o n n e c t e d t o ：as t u bn e t w o p k t i n ki n e t w o r k s u b n e t 嘲精b e t ：1 9 2 1 6 8 。i 7 8 “n k 奄基t 馥 n e t w o p km a s k ：2 5 5 2 5 5 2 5 5 2 4 8 n u m b e ro f $ m e tr t c s ：e t o so 懿e t r i c s ：6 4 l i n kc o n n e c t e dt o ：at r a n s i th e t 瑚o r k ( l i n kl o d e s c g n a t e dr o u t e pa d d p e 8 s ：t 9 2 1 6 8 1 7 - 8 ( l i n ko a t 箍 r o u t e pi n t e 时密a o d p e s s ：1 9 2 1 6 8 1 7 。1 7 n u 倒b e p 艚sm e t r i c s ：谚 t o s0t 醣譬f l c s ：j 9 图2 5 n e t w o r ks u m m a r yl s a 是由a r e a 边界路由器产生的，它通知内部路由器该 a r e a 边界路由器所能够到达的网络。另外它还可以通知默认路由。 2 9o s p f 的包类型 如图2 - 6 所示，o s p f 协议运行在i p 协议的上层，它的协议号是8 9 。每一个 o s p f 的数据包都有一个o s p f 包头部，包头中包含o s p f 协议的版本号、包类 型、a r e ai d 、认证类型、校验和等信息。 根据具体的包类型，还有不同的头部信息。o s p f 共有5 种类型的数据包， 如表2 2 所示。 包类型描述 1h e l l o 2d a t a b a s ed e s c r i p t i o n 3l i n ks t a t er e q u e s t 4l i n ks t a t eu p d a t e 5 l i n ks t a t ea c k n o w l e d g e m e n t 表2 2 中山大学硕士学位论文 用动态生成树改进无线网状网 图2 - 6 这里只介绍后面会用到的h e l l o 类型的数据包。如图2 7 所示，h e l l o 数据包 除了标准的o s p f 数据包头外，还有自己特定的头部信息。 32bits 8 i 8 i 8 i 8 v e m i o ni 瑰p e = l 期靠k 时l e 湖_ l l - r o u t e ri d 蠢醒壤i b c | 培德s l 相 l a u t y l 孵 a u t h e n t i e a t l m a u l m n t i t m u o n n e l w o 暾m a s k h e d l ot n t 鳓v a d l 0