动态路由协议链路状态

动态路由协议链路状态（精选4篇）

动态路由协议链路状态 篇1

###距离矢量路由协议分享其知道的所有信息，但只对其邻居分享;链路状态路由协议只分享与其直连的连接，但会将此信息共享给路由区域内的所有路由器。距离矢量路由协议容易产生环路和无限循环包，所以采用水平分割、路由毒化、保持时间来避免此类事件发生;链路状态路由协议更容易避免此类情况。更重要的是，距离矢量路由协议是发布路由，如果一条重要链路有所更改，意味着发布许多条路由;链路状态路由协议在遇到链路更改时，仅仅发布链路更改通知，而不是传播所有相关路由。一句话，两者的区别是是否自己独立计算路由。

链路状态路由协议有以下特点：

每个路由器与其邻居建立邻接关系;

每个路由器发送link state advertisement (LSA)，一个LSA从路由器的每个接口发出，表明链路，链路的状态，路由器接口到这个链路的metric和所有可能与这条链路相连的邻居。每个接收到LSA的邻居又将这些LSA转发给他们自己的邻居。

每个路由器将其收到的所有LSA存放在其database中。如果一切正常，所有路由器的数据库应该是相同的。

完成了的topological database 或者叫 link state database，描述了从某个路由器出发到各个网络的一棵树，然后形成路由表。

形成邻居关系，以hello包维持。

使用Router ID表明路由器在网络内的唯一身份。

链路状态泛洪 Link state flooding:

邻接关系建立以后，路由器开始发送LSA泛洪。每一个收到的LSA会直接从其他出口发出给邻居，使得链路状态路由协议收敛非常快。而距离矢量路由协议，对收到的update需要先自己处理，然后在定期发送，所以收敛很慢。在泛洪过程中，最重要的两个过程是sequencing和aging。

Sequence Numbers. 路由器在其发出的LSA中包含顺序号，当路由器收到包含相同路由的LSA时，它会检查顺序号的大小，如果大于其topological database内路由的顺序号，就以大的为准，如果收到的LSA顺序号小于等于database内顺序号，则丢弃。这样防止LSA的无限循环扩散。

sequence number space，分为linear sequence number space (IS-IS)， circular sequence number 和 Lollipop-shaped sequence number space (前两者的结合)，

Aging。当LSA生成时，路由器设定aging为零，LSA发布出去过后，每个路由器都增加age。

MaxAgeDiff。当路由器收到多个拥有相同sequence number不同的aging的同一LSA时，如果aging的差别不超过MaxAgeDiff，则路由器认为这些差别是正常网络延迟产生的，将保留原来的LSA;如果aging超过MaxAgeDiff，则路由器选用最新的LSA，并且将这个LSA分发出去。一个典型的MaxAgeDiff是15分钟(OSPF)。

Maximum age。LSA的age在link state database中是持续增加的，当增加到Maximum age时，此LSA的age设定成Maximum age并分发出去，然后从database内删除。OSPF的maximum age为1小时。

Link state refresh time。必须有一种机制使得LSA在到达Maximum age之前重设，否则所有LSA终究会被删除掉。当Link state refresh time到达时，路由器会分发出新的LSA给所有邻居，使得邻居重设Maximum age。OSPF设定为30分钟。

Link state database 链路状态数据库：

Link state database又叫topological database，用于存储LSA。

sequence number 和 age主要用于管理LSA的分发;路由器ID、与其相连的网段和邻居则是用于最短路径计算。

LSA主要包含两种类型的信息：Router link information 和 Stub network information。 路由链路信息描述了一个路由器的邻居(Router ID，Neighbor ID, cost), 其中cost 是到邻居的链路的cost;末端网络信息描述了一个路由器连接的末端网络(不与邻居相连的网络)(Router ID，Network ID, cost)。

SPF算法先计算出到各个路由器的最短路径，然后再将末端网络添加到这些路由器上。

cost是以路由器出口方向的接口cost为准。

Area 区域：

区域是一组路由器组成的内部网络，使用区域主要基于以下考虑：

跟距离矢量协议比较，路由器需要更大内存;

复杂的算法需要更多CPU处理时间;

动态路由协议链路状态 篇2

贪婪路由源于地理路由的思想, 网络中每个节点接收一个GPS坐标[1,2]。网络节点已知其邻居的坐标才能贪婪路由, 转发传入数据包到距数据包预期目的地更近的邻居, 这样到数据包目的地的距离会减小, 重复应用这个距离减小策略能最终达到目的地[3]。通过在给定几何空间安排虚拟坐标能够重用这种思想, 但该技术中数据包可能会陷入局部最小点 (湖或空洞) 。文献[4]提出的贪婪嵌入, 通过确保坐标以相同方式映射到网络节点来避免这种情况, 局部最小点问题永远不会发生。

克莱因伯格的开创性工作[5]证明了双曲平面上任意连接的有限图贪婪嵌入的存在性。但是文献[5]没有明确讨论最差情况下要求的坐标精度。文献[6]提出了一种双曲平面的贪婪嵌入, 仅使用O (logn) 位进行坐标表示, 其中n是网络中节点的数目, 但是文献中未对提出方案产生的拉伸度进行评估。文献[7, 8]提出了在欧氏空间嵌入图的方法, 文献[7]将图嵌入到欧氏O (logn) 维空间中, 文献[8]将图嵌入到多对数维度的欧氏空间。文献[9]表明因特网图的统计结构与双曲几何的统计结构类似, 该文提出因特网本质上是一个隐藏双曲结构。文献[10]也提出一种双曲隐藏度量空间中的网络增长机制, 其中贪婪转发即使是在动态网络拓扑中也总能成功。

网络动态问题 (如链路/节点故障或贪婪路由中节点添加) 尚无学者明确研究过, 但是, 文献[11]提出一种双曲平面选择嵌入方法, 能增量式嵌入网络节点而不干扰全局嵌入, 但是产生的嵌入不能简单的适用于处理网络节点/链路移除。网络节点移除情况下, 该文建议不改变嵌入, 一旦数据包陷入局部最小点, 使用一种适当的路由算法, 产生的路由称为重力-压力路由。该技术不同于面路由, 它保持通过邻居转发尽可能减小距目的地距离。但是, 为了避免数据包卡陷入死循环, 从检测到局部最小点的时刻起, 就需要维持对每个数据包的路径跟踪, 这会对数据包包头带来很大开销。

针对单链路/多链路故障对贪婪嵌入的影响, 提出了两种恢复方法处理网络动态链路故障。提出的方案不需要重嵌入, 确保给定链路故障覆盖, 可以用作保护方案, 能比现有方案实现更快切换。使用的恢复路径显示出了比现有动态方案 (重力-压力路由) 更好的拉伸度特征。不同于文献[11], 该方法不需要维护数据包访问的节点列表, 因此, 加在数据包包头的开销并不明显。提出的方法还能应用于大型网络, 由于其可扩展性、简单性和低成本, 适合分布式实现。

1 双曲平面贪婪嵌入

双曲平面的一个重要特点是允许使用d-正多边形进行无限多均匀镶嵌, 双重这些镶嵌是由生成镶嵌的多边形的中点形成的d-正则树。因此, 双重对应镶嵌可以映射给定网络的任意生成树到一个足够大的d-正则树的子树, 这是文献[5]构建任意图的嵌入使用的核心属性。使用相对于d选择的莫比乌斯变换可以推导出盘加莱圆盘 (PD) 的d-正多边形。本文简单介绍了嵌入图到双曲平面所需的子任务, 其理论解释和数学证明可参照文献[5]。计算网络节点的虚拟坐标 (嵌入) 所需的子任务如下:

(1) 构建一棵网络生成树;

(2) 确定这棵树的最大度d;

(3) 在双曲平面生成无穷d-正则树, 用这个无穷d-正则树命名生成树的每个节点。

用于确定贪婪嵌入 (坐标) 的生成树确保总是存在距离减少路径 (经由树) , 但是, 基于这种嵌入的贪婪路由不同于产生的树上的路由, 因为还会取捷径 (不在生成树上的边) 。

2 故障恢复策略提出

本文应用第1节中介绍的贪婪嵌入方法分配坐标给双曲平面上的网络节点, 假设贪婪路由必须使用这些虚拟坐标才能继续前进。

使用这种嵌入, 单链路故障可能使贪婪嵌入无效。从第1节中观察贪婪路由基于网络的生成树, 这个生成树确保总是存在距离减少路径 (通过树) , 然而, 如果一个链路/节点故障影响生成树的连接性, 它就会影响贪婪嵌入, 进而影响贪婪路由。图1给出了这个问题的一个简单例子, 图中, 用实线表示生成树的边, 用虚线表示网络中的捷径, 整数ID仅用于表示网络节点, 需要注意的是这些ID不等于双曲平面中节点的虚拟坐标。在这个例子中, 节点1到节点7的贪婪路径在树上 (1→3→7) , 链路 (1→3) 上的故障使节点1成为局部最小点 (依据双曲平面嵌入, 节点2比节点1更靠近节点7) , 因此, 数据包卡在这个节点。

该问题的解决方法是找到另一个使贪婪路由再次生效的嵌入, 但是, 这种解决方法会引起坐标频繁重计算, 这在大型网络中不现实, 过多节点坐标重计算会产生不期望的过长时间中断。为了以一种有效的方式克服链路故障问题而不改变坐标, 本文提出了贪婪路由协议的单链路故障和多链路故障恢复方法。就目前所知, 恢复方法可以是保护方案或修复方案或二者的组合, 保护方案中, 在网络任意故障之前先确定一条备份路径, 这类方法能使网络快速恢复。而修复方案中, 可以动态按需安装备份路径[12]。本文提出的方法是主动模式 (保护) , 但是单链路故障的方法也适用于反应模式 (修复) 。

2.1 单链路故障恢复

本节提出一种用于单链路故障的恢复方法。为了检测网络中的故障, 可以利用一些方法和协议, 比如双向转发检测BFD (Bidirectional Forwarding Detection) [13]。仅当网络中有单链路故障且故障链路属于网络生成树时可以应用本文提出的方法, 仅对树边应用本方法的原因是:使用克莱因伯格的贪婪嵌入时, 如果故障链路是一个捷径 (链路不在生成树上) , 贪婪路由仍能在树边上继续, 仅当树边故障时, 才会有陷入局部最小点的问题。图2显示了故障链路是捷径的场景, 从图中可以看到, 使用树边贪婪路由仍然有效, 从左图可以观察到, 节点4和节点7之间的贪婪路由为 (4→2→7) , 当捷径2-7为故障时, 可以使用树上的贪婪路由 (4→2→1→3→7) 代替。因此, 仅当贪婪路由不再有效时, 也就是故障边在网络生成树上时才使用恢复方法。

提出此方法的基本思想是:一旦树链路故障, 对一个节点打开通道, 使得从那个节点到目的地的贪婪路由一定能工作。下面的小节详细描述了该方法。

2.1.1 上游/下游故障恢复

一旦发生树边故障, 必须有另一条路径, 而寻找这条路径需要区分上游故障和下游故障。上游故障是指需要向上传递故障树边 (越来越接近树根) , 而下游故障则反之。

首先, 考虑下游故障的场景。需要找到一个节点, 这个节点有到故障链路之下子树的捷径, 这个子树的根在与故障链路相连的上级节点上。在上游故障场景中, 节点有一个可用走出故障链路之下子树的捷径就足够了。知道了上下游中间节点的这些条件之后, 按照如下步骤恢复故障链路:

(1) 从故障检测节点初始化一个广度优先搜索 (BFS) 轮循最接近潜在中间节点 (满足上述提到的上下游条件) 。

(2) 找到潜在中间节点后, 节点发回确认消息给故障检测节点, 表明其坐标。

许多文献提出了执行BFS的分布式算法, 直接或稍加改动就可应用于本场景中[14]。

一旦找到中间节点, 转发程序如下:

(1) 从故障检测节点贪婪路由到中间节点。

(2) 使用中间节点的捷径达到期望的子树。

(3) 继续贪婪路由到生成树上的目的地 (禁用捷径) 。

使用这种方法不需要在另一条路径的节点上设置任何项, 因为该方法首先对中间节点打开了通道, 然后贪婪路由到目的地, 唯一加到数据包包头的开销是中间节点的坐标和一个标志, 这个标志表示应该首先贪婪路由这个数据包到中间节点, 然后继续树上的路由。

这种方法可用于按需寻找故障检测的替代路径或作为一种预先计算中间节点的保护方法 (主动) 。

在主动模式中, 预计算网络节点上对应于每个树边的中间节点, 当故障检测之后, 可以为到给定目的地的数据包本地安装预计算的备份入口, 从而实现快速切换。由于仅网络生成树上的边需要这种恢复方法, 所以它能依树中边的数目扩展。在反应模式中, 网络中的每个节点仅需要计算对应于与那个节点相连的每个树边的中间节点。图3是节点对连接到那个节点的树边执行的控制程序框图。

2.1.2 子树确定

为了找到中间节点绕过故障链路, 必须已知: (i) 树中节点的级别 (距树中树根节点的距离) ; (ii) 节点属于那棵子树。节点的级别首先用于确定上下游故障, 弄清楚应该寻找哪类中间节点;节点级别的第二个用处是确定子树 (节点属于哪棵子树) 。然而从节点的虚拟坐标提取这个信息不太容易, 因此, 网络节点需要另外一种编码系统。出于这个目的, 任何能确定生成树上节点位置的编码都可使用, 本文使用一个非常简单的编码方法, 分配一个整数给每个节点, 可以分布式方式完成分配 (与双曲坐标分配并行) 。已知树的节点度, 每个节点就能确定其父母、其孩子的整数ID及其它在树中的级别。使用一种双通算法确定树的度, 每个节点报告给其父母以它为根的子树的最大度, 然后根计算树的最大度, 广播给每个节点[4]。计算整数ID和节点级别的简单公式如下:在一个k叉树 (每个节点的最大度为k+1) :

S (h) 指的是高度为h的完美k叉树中节点的数目, 使用S (h) 可以确定节点的树级别。对于一个整数ID为i的节点, 需要在下列不等式中找到h:

前两个公式有助于找到节点的直接父母及孩子ID, 为了找出节点在某子树下 (以某节点为根的子树) , 应该计算节点的级别, 因为树中节点的级别决定那个节点到根的距离。例如, 想知道节点A是否在以节点B为根的子树上, 首先应该计算两个节点的级别 (使用S (h) ) , 假设节点A在级别4, 节点B在级别1, 为了查明节点A是否在节点B的子树上, 需要检查节点B是否是节点A的父母/祖先, 通过反复检查节点A的下一个父母ID是否等于B的ID来执行, 因此, 本文的例子中需要对节点A的ID应用父母公式3到4次。

图4和图5显示了上下游故障的两个简单例子, 如图4所示, 节点3故障检测之后, 开始BFS轮询潜在中间节点, 节点6有一条走出故障链路下子树的捷径 (子树根节点为节点3, 这个例子中它由节点3、6、7组成) , 因此, 节点6发送确认消息给故障检测节点。右图给出了使用中间节点的替代路径, 首先贪婪路由数据包到中间节点 (节点6) , 然后取期望子树的捷径 (链路6-5) , 继续对树进行剩余路由 (5→2→1) 。分配整数ID给网络节点基于一棵2叉树 (k=2) , 这些ID仅用于确定树中节点的位置, 贪婪路由仍然依据双曲平面的虚拟坐标。图5中, 以相同方式确定了中间节点 (节点2) , 替代路径如右图所示 (1→2→7) 。

2.1.3 数据包交换

为了对寻找中间节点和这些数据包及算法使用的复杂度而交换的数据包数目有个概述, 本文从数据包交换的角度解释了本方法, 故障检测/受保护节点通过发送有节点整数ID的数据包 (探针) 到故障树边的另一端, 并发送故障的方向 (上游或下游) 到其第一邻居来启动BFS搜索 (如图4和图5中所解释的) 。接收到这样一个数据包之后, 节点可以检查它是否有合适的捷径, 如果没有, 以BFS方式检查下一个节点, 当发现中间节点时, 节点发送确认消息给故障检测/受保护节点, 这个确认消息包含中间节点的双曲坐标。实验评估时, 为了找到网络中对应于树边的中间节点, 观察了所需要的通信消息的数目。

2.2 多链路故障

单链路故障恢复方法不能应用于多链路故障场景, 原因是每个节点需要网络所有故障链路的信息, 这个信息用于寻找潜在中间节点, 这个中间节点不会产生有故障链路的子树。对于大型网络, 为所有网络节点提供这类信息不灵活也不现实。不具有这类信息的问题如图6所示, 基于单链路故障方法, 节点2开始搜索潜在中间节点, 节点4是一个合适的选择 (有故障链路之下子树外的捷径) , 但是如果取快捷方式4-6, 路由就不能在这棵树上继续, 因此, 所需的故障链路列表在节点4, 这样可以避免捷径4-6是合适的捷径, 选择节点5为潜在中间节点。

本节提出另外一种恢复网络多链路故障的方法。

2.2.1 多链路故障恢复

在多链路故障场景中, 提出本地恢复每个故障边的方法, 这意味着如果数据包的下一跳是故障树边, 就会对连接到故障另一端的节点使用备份路径。在故障检测节点, 数据包使用备份路径到达故障链路的另一端, 然后恢复从那个节点到目的地的贪婪路由。当遇到到目的地路径上的另一个树边故障时, 重复同样的过程。使用这种方法, 本地恢复故障边, 不需要区分上游故障和下游故障。提出的方法是主动模式的恢复方法, 主动模式和反应模式的方法之间总是存在速度和资源的权衡, 使用本方法可以获得快速恢复, 但需要更多的资源成本。

由于仅需要对网络中树边进行恢复, 每个节点只需找到连接到那个节点的树边的备份路径。主动模式下, 故障之前会预先计算备份路径, 因此, 为了恢复多链路故障, 需要计算多个不相交路径, 两个节点之间的最大可用不相交路径决定能确保恢复同时故障的最大数目。

提出的方法中, 每个节点应该找到它本身和其邻居之间的最大不相交路径, 如果他们之间的链路在网络的生成树上, 应该找到连接到那个节点的每个树边的这些不相交路径, 但是, 基于网络拓扑, 每个树边可能的不相交路径的数目也许会不同, 因此, 所有树边的所有可能不相交路径之中的最大数目 (网络的最小割) 是使用本方法确保能恢复的同时故障的最大数目。

考虑多个不相交路径时会出现一个问题, 在每条不相交路径的中间节点上存储入口会引起那些节点的大内存开销, 为了避免节点上的这类内存开销, 取贪婪路由的优点。代替沿备份路径设置每个节点的入口, 检查使用贪婪路由是否会经过备份路径, 一旦发现不相交路径, 就开始检查每条路径上的节点, 判断其贪婪路由路径是否等于备份路径。将那个节点当作中心节点 (hub node) , 从中心节点对备份路径上的剩余节点重复这个过程, 这个检查结束时, 找到一些中心节点, 这些中心节点之间的贪婪路由等于备份路径。第2.2.2节中解释了如何使用一些探针消息找到这些中心节点, 每个受保护节点仅需为计算每个树边的各种不相交路径而存储这些中心节点, 没有备份路径上的节点需要为任意经过它们的路径存储入口。图7给出了网络节点考虑一条树边时控制程序的步骤。

如果每个节点到下一跳有最大K条不相交路径且每条不相交路径最多有L个中心, 每个节点的最大度为M, 则每个节点需要的内存最大为M×K×L。因此, 节点所需的内存独立于确保能恢复的故障数目, 也独立于网络生成树的节点度。第3.2.2节将给出所需内存和网络生成树中节点的度分布实验结果。

寻找每个树边的备份路径和对应于他们的中心节点, 并将他们存储在受保护节点, 这是控制程序的步骤。接下来的段落将解释转发程序。类似于BFD[13]的协议可用于测试树边备份路径的活跃度, 由于这是一个K:1保护, 所以不需要激活所有K条备份路径, 一旦数据包的下一跳是故障树边, 则添加那条边的对应于其中一条不相交路径的中心节点到数据包包头, 首先贪婪路由数据包到第一个中心, 然后到第二个中心, 一直持续直到到达故障边另一端的节点, 从那里, 再继续贪婪路由数据包到目的地。第3.2.2节的结果表明, 该方法对数据包包头的开销非常低。图8给出了多树边故障的例子以及恢复后的路径 (使用对应于故障边的备份路径) 。面对故障树边的情况, 使用对应于那条边的备份路径代替, 只要网络中每个树边至少存在一条备份路径, 该方法就能成功。

2.2.2 寻找备份路径中的中心节点

本文将连接到受保护链路的节点称为受保护节点, 在这个节点存储对应于备份路径的中心节点, 使用探针消息可以找到这些中心, 从受保护节点开始探测, 路径上的每个节点都有一个下一跳入口, 但是, 一旦找到中心节点, 就不需要保持这些入口。需要使用两类探针消息, 第一类用于检查路径上的节点的贪婪路由给出的路径是否与备份路径相同 (Grdy-Chk消息) ;第二类消息用于通知路径上的节点对剩余节点启动相同程序 (StartChk消息) 。

受保护节点发送Grdy-Chk消息给路径上第一个节点, 检查贪婪路由是否等于备份路径, 由此开始程序。每次Grdy-Chk到达消息目标域的指定节点后, 那个节点发送确认消息给受保护节点, 这个确认消息包含路径上的下一跳, 受保护节点总是存储送回确认消息的最后一个节点, 并且发送另一个Grdy-Chk到路径的下一个节点作为消息的目的地。程序持续直到贪婪路由和备份路径不相同。检测这个问题的第一个节点发回Not Ack给受保护节点, 这类消息到达后, 受保护节点将先前存储的节点作为第一个中心, 并发送Start-Chk消息到那个中心节点, 这个消息到达中心节点后, 它开发发送Grdy-Chk消息给路径上的剩余节点。中心节点持续检查, 直到接收到Not Ack。在这种情况下, 它发回最后存储的节点给受保护节点, 受保护节点存储第二个中心, 并继续程序, 直到找到所有中心节点。

2.3 与面向树路由算法的比较

本节论述了提出方案与著名的面向树算法之间的差异, 如以太网生成树协议 (STP) 、IEEE 802.1D标准及其变种快速生成树协议 (RSTP) 、IEEE 802.1w。这些协议确保网络中的无环路拓扑结构, RSTP能在拓扑结构变化之后提供明显较快的生成树收敛。

STP和RSTP算法以分布式方式动态计算树, 每个拓扑结构变化时, 网络节点之间交换协议消息并重新收敛树。但是, 本文提出的方案仅计算一棵生成树, 按需或受保护的安装备份, 因为本方法本地化恢复故障, 所以不需要通知变化消息给所有网络节点。

另一个差异是路由本身。STP和RSTP路由仅针对网络的生成树 (树路由) , 但是, 使用虚拟坐标的贪婪路由不等于树路由;另外还使用了捷径, 它使路由更有效。文献[5]比较了贪婪路由和生成树路由在拉伸度上的性能。

3 两种恢复策略的评估

本文的仿真环境基于Python/C++, 使用Networkx库实现基于图的算法, Numpy和Scipy包用于数值算法, 使用C++优化某些代码, 使其允许对大型网络仿真。

实验评估由两组结构组成, 一组与单链路故障恢复方法有关, 另一组与多链路故障恢复方法有关。在路由质量 (拉伸度) 和开销两个方面评估提出的方法。

3.1 单链路故障恢复方法的实验结果

3.1.1 拉伸度评估

本节评估了提出方案的路由质量 (即拉伸度) , 定义拉伸度为贪婪路由方案产生的路径长度与同一源-目的对最短路径长度的比值。本文比较了两种场景下的拉伸度, 第一种情况下, 网络中没有故障链路, 拉伸度表示贪婪路由路径长度与最短路径长度的比值;第二种情况下, 网络中有一条故障树边, 因此, 拉伸度表示恢复方法生成的贪婪路由路径长度与从图中移除故障边后最短路径长度之间的比值。

使用第1节中的方法嵌入每个图到双曲平面中, 为了执行贪婪路由而使用虚拟坐标。对于网络中有单个故障的场景, 本文考虑每条树边来评估拉伸度, 一次一条树边作为故障边, 取所有结果的平均值。对各种B-A网络重复这个程序, 图上的值是对所有样本的平均。

在图9 (a) 中, 给出了有1000个节点的图的拉伸度分布, 从图中可以观察到单链路故障上的拉伸度分布几乎与没有任何链路故障的拉伸度分布相同, 恢复方法没有明显改变拉伸度。图9 (b) 中, 给出了不同尺度下网络在两种场景的平均拉伸度。在这个实验中, 计算了网络中所有可能的源-目的对的拉伸度, 然后求平均。图9 (a) 和图9 (b) 的置信区间都是95%。从图中可以看到, 该方案可随着节点数目的增加进行良好扩展, 因为B-A图的平均拉伸度中变化不明显。观察这种趋势可以外推得到大型拓扑结构的性能。

3.1.2 开销评估

本节从网络节点所需内存和通信消息数目两方面评估了本方法。

正如前面所述, 只有树边上的故障才需要使用提出的方法, 因此, 提出的方法能够依网络生成树上边的数目扩展。在单故障恢复方法中, 每个节点A需要为连接到节点A上的每个树链路存储一个中间节点B, 因此, 网络生成树上每个节点的度等于那个节点所需的内存。本文计算生成树上每个节点的度, 使用盒形图描述百分位, 得到网络节点所需内存/节点度的概况。图10 (a) 给出了各种尺度下网络的结果, 使用盒形图描绘了最小值、较低四分位值、中位值、较高四分位值和最大值。但是, 在产生的图中只能看到两个值, 这种表示的原因是高达75%的节点在树上的节点度为1, 但是存在一些节点具有非常高的度。这可以从B-A图的属性来解释, 在生成的这些图中, 一个节点拥有的连接越多, 它得到新链路的可能性越大, 就会产生一些具有非常高的度的节点。由于本文使用BFS来产生生成树, 且选择有最大度的节点作为树根, 所以, 存在一些具有非常高的度的节点, 也存在许多节点的度为1的其他节点, 图顶部的值是网络所需的平均内存。

下一个实验评估了寻找对应于树边的潜在中间节点所需的通信消息的数目。这些消息包括探针和确认消息, 如2.1.3节中解释的, 节点使用探针消息开始BFS, 找到中间节点时, 它接收一个确认消息。对网络中的每个树边计算这些消息的数目, 他们的百分位如图10 (b) 所示, 图中给出了各种尺度下网络的结果, 节点数目高达1000, 顶端的值代表所需消息的平均数目。在1000个节点的网络中, 对于高达75%的树边, 交换的消息小于200个, 交换的消息的最大数目为732, 所需的平均消息数目为127。

为了得到中间节点和故障检测/受保护节点之间距离的概述, 本文对网络中每条树边计算了这个距离 (跳) , 实验只给出了1000个节点的网络的结果。考虑网络中所有树边, 75%的链路中中间节点位于距故障检测节点仅两跳的位置, 最大距离是4, 所有树边的平均距离是2。

3.2 多链路故障恢复方法的实验结果

3.2.1 拉伸度评估

本节评估了多故障场景下本方法的质量, 与3.1.1节类似, 给出了不同节点数目的网络的拉伸度分布和平均拉伸度, 提出的方法能确保恢复给定数目的故障 (至少等于网络的最小割) , 只要没有破坏保护机制, 该方法就能成功, 这意味着网络中每个树边至少有一条备份路径。

在这个实验中, 产生了以10为最小度的B-A图, 考虑网络中每条树边的9条不相交路径, 因此, 该方法能确保恢复的最大故障数目为9。本文在故障多于9个的场景中评估了本方法, 得到在更多故障发生时本方法的性能概述。图11 (a) 给出了有1000个节点的网络在四种场景下的拉伸度分布, 每种场景下, 检查了不同比例的树边故障, 随机选择故障树边 (均匀分布) 。正如预期的那样, 网络中故障越多, 较高拉伸度的节点对增加越多, 但是, 再看图11 (b) 中的结果, 平均拉伸度不超过1.4。为了比较提出方法与现有方法的性能, 本文依据文献[15]可用的伪代码实现了重力-压力算法, 选择这个算法是因为它能应用于双曲平面贪婪嵌入, 不同于其他方法, 它可以无任何限制地应用于每个拓扑结构 (如使用面路由需要平面化) 。这种方法对1000个节点的网络在不同树边故障比例下的平均拉伸度如图11 (b) 所示, 正如文献[15]中解释的, 使用这种方法, 平均拉伸度会随着网络中故障数目的增加而增加, 直到网络稀疏。因此, 某个故障数量之后, 平均拉伸度降低, 因为10%的树边故障不会使网络稀疏, 所以重力-压力不是总能找到最有效路径, 因此, 正如结果所示, 在更多故障下, 平均拉伸度增加到2.6。在图11中, 给出的值的置信区间为95%, 在图11 (b) 中, 提出方案的值的置信区间宽度不超过0.02。

正如前面提到的, 本文的恢复方法一直有效, 除非破坏了保护机制, 即破坏了一些树边的所有备份路径。本文在各种树边故障百分值下评估各种场景, 检查源-目的对断开的数量。考虑有1000个节点的网络中树边随机故障高达50%的各种场景, 在故障高达30%的所有场景下, 本方法仍然有效, 但是, 在有40%和50%故障的一些场景下, 平均断开约2600对, 不到网络所有可能对的1%。

3.2.2 开销评估

本方法仅应用于网络中的树边, 因此, 每个节点所需的内存与树中那个节点的度成比例, 正如2.2.1节解释的, 每个节点需要为对应于连接那个节点的树边的每条不相交路径存储中心节点。本实验中, 每条树边的不相交路径数目为9, 基于B-A网络的生成树上的度分布, 仅有一些节点有非常高的度, 大部分节点的度为1, 考虑到这一点, 网络节点所需的内存如图12 (a) 所示, 最小值是9, 在几乎所有网络中, 75%的值为16, 对于有1000个节点的网络, 最大值高达1470, 这是由于仅有少数节点具有非常高的度, 图的顶部给出了生成树中节点的最大度。

最后一个实验评估了对应于每条树边的不相交路径的中心数目, 本文发现网络中每个树边有9条不相交路径, 计算每条路径的中心数目, 图12 (b) 给出了各种尺度的网络中所有不相交路径的中心数目百分位, 从图中可以观察到, 75%的路径仅有2个中心, 在有1000个节点的网络中最大中心数目为4。备份路径的中心会被添加到数据包包头。因为重力-压力算法也使用每个数据包的路径跟踪, 所以计算算法的压力模型中每个数据包中存储的表的大小, 以便可以与提出的方案进行比较。压力模型中数据包中表大小的百分位如下:25%的数据包中表大小为3, 中位数是9, 而75%的数据包中表大小为28, 有1000个节点10%故障树边的网络中最大值为290, 这个表的平均大小为24。

4 结语

本文提出了贪婪路由协议单链路故障和多链路故障恢复策略, 两种方法都在第一时间避免了湖或空洞, 不需要为了成功传输数据包到目的地而在网络中维护局部最小点列表, 提出的方法不需要重计算坐标, 能确保覆盖给定链路故障, 可当作保护方案来使用, 比现有方法实现了更快速的切换。本方法仅需要本地通信, 两种恢复方法都能随着网络生成树中边的数目扩展。在类似于因特网的图的实验环境中评估了这些方法, 使用的恢复路径给出了比现有动态方法更有趣的拉伸度特性, 其他实验给出了方法开销的概述。基于这些结果, 每个节点所需的内存与节点的度和确保能恢复的故障数目成比例, 添加到数据包包头的开销非常低, 其可扩展性、简单性和有限资源使方案适用于大型网络, 其本地化、有限的路由质量损失和低开销等优点使提出的方案成为一种有前途的恢复策略。

摘要：针对现有的贪婪方法不能有效处理拓扑结构中链路故障的问题, 提出单链路故障和多链路故障本地化恢复策略。首先, 通过利用克莱因伯格的贪婪嵌入给出单链路故障恢复策略;然后, 将其扩展到多链路故障的情况;最后, 在基于Python/C++的仿真环境下对提出的技术进行评估。实验结果表明, 该技术仅需要非常有限的资源, 且造成的路由质量损耗也有限, 可以实现快速切换, 可依网络生成树中链路数目扩展。该技术的可扩展性、简单性和低开销使其适合于大型网络。

动态路由协议链路状态 篇3

配置各个路由器的接口ip和Loopback接口ip，步骤略

======================================================================================

配置OSPF

R1:

(config)#routerospf1

(config-router)#router-id1.1.1.1

(config-router)#network1.1.1.1 0.0.0.0area 0

(config-router)#network10.0.0.0 0.0.0.3 area 0

(config-router)#network40.4.4.0 0.0.0.3 area 0

(config-router)#network192.168.1.0 0.0.0.255 area 0

------------------------------------------------------

R2:

(config)#routerospf1

(config-router)#router-id2.2.2.2

(config-router)#network2.2.2.2 0.0.0.0area 0

(config-router)#network10.0.0.0 0.0.0.3 area 0

(config-router)#network20.2.2.0 0.0.0.3 area 0

(config-router)#network192.168.2.0 0.0.0.255 area 0

------------------------------------------------------

R3:

(config)#routerospf1

(config-router)#router-id3.3.3.3

(config-router)#network3.3.3.3 0.0.0.0area 0

(config-router)#network20.2.2.0 0.0.0.3 area 0

(config-router)#network30.3.3.0 0.0.0.3 area 0

(config-router)#network192.168.3.0 0.0.0.255 area 0

------------------------------------------------------

R4:

(config)#routerospf1

(config-router)#router-id4.4.4.4

(config-router)#network4.4.4.4 0.0.0.0area 0

(config-router)#network30.3.3.0 0.0.0.3 area 0

(config-router)#network40.4.4.0 0.0.0.3 area 0

(config-router)#network192.168.4.0 0.0.0.255 area 0

========================================================================

动态路由协议链路状态 篇4

关键词：移动Adhoc网络,路由控制开销,链路质量,拓扑质量

0 引言

移动Ad hoc网络(Mobile ad hoc network,MANET)是由一组可以自由移动的节点构成的多跳的无线网络。节点的自由移动导致拓扑的动态变化,使得传统的用于有线网络的"表驱动"路由协议无法在移动Ad hoc网络直接使用。文献[1]指出在拓扑不断变化的网络中,维护一个及时的路由表将带来较大路由控制开销,因而需要消耗比较多的网络资源。"按需"路由协议,如AODV、DSR等,无需维护整个网络的拓扑结构,因而能将路由控制开销限制在当路由需要时。然而节点的移动使得路由断开难以避免,因此路由发现时的控制开销不可忽视。文献[2]指出移动Ad hoc网络的控制开销对于整个无线网络来说是一个巨大的负担,这是难以将传统的信息论应用到这种无中心的网络中的三个障碍之一。同时,文献[3]指出路由控制开销是网络拓扑变化率的函数,是衡量路由协议性能的主要指标。因此在为移动Ad hoc网络设计路由协议时必须考虑路由控制开销问题。本文提出了一种综合考虑"链路质量"和"拓扑质量"的路由协议(LQTQ),此协议在路由发现时,综合链路质量和拓扑质量设置转发概率,不仅选取较长生存期的路由,而且减少路由请求包的数量,从而提高了路由性能。

1 相关工作和研究动机

对于移动Ad hoc网络的路由控制开销问题,主要有两种解决办法:a.减少路由发现的次数;b.减少每次路由发现的开销。"最长生命期"路由是一种有效地减少路由发现次数的方法。文献[4]提出了一个全局式的长链路生存期路由算法用于研究长链路生存期路由的统计行为,并提出一个分布式长链路生存期路由算法用于实际的路由设计。文献[5]提出了一个通过限制到下一跳中继节点的距离来提高路由生存时间,进而提高路由性能。文献[6]提出了一种联合物理层和路由层的跨层算法,采用长链路生存期和信道质量作为路由选择度量指标,模拟结果显示该方法能显著提高吞吐量并降低延迟。本文提出的"链路质量"指标就是考虑相邻节点之间的链路生存期,有较长的剩余链路生存期的节点有较大的转发概率。这样使得链路生存期较长的节点有较大的概率被选为路由中继节点,避免了选择了弱链路导致路由很快地断开,从而减少了路由发现次数。

"按需"路由协议的路由发现多采用洪泛方式,中间节点的盲目转发收到的路由请求包会导致"广播风暴"问题。传统的解决此问题的方法多是完全针对广播问题的,并没有从路由发现的角度,针对发现目的节点作优化。如文献[7]提出的基于"邻居覆盖"的"动态概率路由发现",节点根据本地节点密度和被广播覆盖的邻居集合来计算转发概率。文献[8]提出的基于"计数器"的概率方法,每个节点为收到的路由请求包维护一个计数器,然后根据计数器以某个概率转发收到的路由请求包。这两种方法均采用了概率机制,中间节点根据某种概率来转发路由请求包,能有效地减少冗余的路由请求包。然而这些方法没有从路由的角度考虑中间节点是否适合作为路由中继节点,即这些优化措施仍然是全向的,面向整个网络的。路由发现毕竟不同于数据广播,只要能够发现目的节点,路由请求包没有必要扩散到整个网络。因此为了减少路由控制开销,不仅要减少冗余的路由请求包,还要控制路由请求包的传播范围。近些年来,已经有研究开始解决此类问题。文献[9]提出了一种极化的Gossip协议(Polarized Gossip),节点的Gossip概率是由节点自身到目的节点的距离和节点的上一跳节点到目的节点的距离决定的。文献[10]提出一种区域性的Gossip协议(Regional Gossip),这个协议中定义多个以源节点和目的节点为焦点的椭圆,只有在椭圆内的节点执行Gossip协议并转发消息,而不在椭圆内的节点将不参与Gossip协议。本文提出的"拓扑质量"指标便是考虑了中间节点与"源-目的"节点连线的距离,距离"源-目的"节点连线较近的节点有较大的转发概率。这样避免了路由请求包传播到离"源-目的"较远的节点,从而限制了路由请求包的传播范围,减少了路由发现时的控制开销。

综上所述,为了有效地减少路由控制开销,不仅要"减少路由发现的次数",还要"减少每次路由发现的开销"。本文提出的方法正是同时从这两方面入手,能够有效地降低路由发现的频率和路由发现的开销,从而提高网络的分组投递率和端到端延迟。

2 基于链路质量和拓扑质量的路由协议

在本文提出的路由协议中,假设节点知道自己的位置坐标和移动速度。同时为了方便考察链路质量,网络中每个节点维护一个邻居节点的位置和速度的列表。下面介绍链路质量和拓扑质量的计算方法。

2.1 链路质量的计算

节点Ni收到邻居节点Nj的路由请求包后,Ni可以根据自己的位置和速度以及邻居列表中Nj的位置和速度,计算出Ni和Nj之间的链路还能维持多长时间。设节点Ni的当前位置是(xi,yi),速度为(ui,vi),节点Nj的当前位置是(xj,yj),速度为(uj,vj),t秒后各自的位置分别为(xi+uit,yi+vit)和(xj+ujt,yj+vjt),其距离为:

如图1所示,节点Ni和Nj各自移动,当Nj到达Ni的传输边界时,即D(t)=R(R为节点的无线信号传播范围)时,Ni和Nj之间的链路即将断开,因此解方程D(t)=R可得Ni和Nj的剩余链路生存期(Residual Link Lifetime,RLL)为:

根据RLL,定义"链路质量"(Link Quality,LQ)如下:

其中Lth为一判断链路强弱的阈值。

2.2 拓扑质量的计算

在一个节点均匀分布的网络中,一个拓扑质量良好的中间节点,应当位于"源-目的"节点连线附近。如图2所示,节点N3所处的拓扑位置最佳,它距离S-D连线最近,故节点N3应该有最大的转发概率。

源节点S在初始路由发现时,对目的节点D一无所知,因此只能采用全向的路由发现。当目的节点返回路由回复包时,附带上自己的位置和速度。源节点在路由重建时,可以计算出目的节点当前的位置。源节点在路由请求包中附带上源节点位置和目的节点位置。中间节点N在收到路由请求包后,其"拓扑质量"(Topology Quality TQ)计算如下:

设为节点Ni和Nj之间的距离,则拓扑质量TQ定义如下:

其中,α为TQ调整因子。

2.3 基于链路质量和拓扑质量的概率转发机制

根据2.1和2.2小节介绍的链路质量LQ和拓扑质量TQ,中间节点的概率转发算法LQTQ如下:

3 性能评测

为了评测本文提出的LQTQ路由协议,本文使用NS2进行了仿真实验,在AODV协议的基础上实现了所提出的路由算法。实验参数如下:Mac层采用IEEE 802.11协议中的分布式协调功能(DCF),无线传播范围是250m,带宽是2Mb/s。在实验中随机选取了12条固定比特率(CBR)的数据流,每个源节点每秒发送4个512字节的CBR分组。网络区域为1000m×1000m,移动模型采用随机位点模型(RWP),节点最大速度为5m/s,暂停时间为0。

实验评测的性能指标有:

(1)标准化路由开销:控制分组的总流量和成功到达目的节点的数据分组的总流量的比值。

(2)分组投递率:成功到达目的节点的分组个数和源节点生成的分组个数的比值。

(3)平均端到端延迟:从源节点成功到达目的节点的分组的平均延迟。

每次实验的模拟时间是100s,节点个数从50个到300个。实验结果中,每个数据点为30次实验的平均值。模拟结果如下:

图3显示了标准化路由控制开销,LQTQ协议利用链路质量避免了弱链路节点转发,并利用拓扑质量限制路由请求包的传播范围,故而降低了路由控制开销。平均情况下,LQTQ协议比AODV减少了38.7%的控制开销,在网络密度较高的情况下效果更明显。

图4显示了在不同网络密度下的分组投递率。LQTQ协议减少了路由控制开销,从而减少了分组冲突,进而减少了因冲突导致的分组丢弃,故而提高了分组投递率。平均情况下,LQTQ比AODV提高了5.6%的分组投递率。图中可以看到,在节点密度较高时提高得更多。

图5显示了目的节点收到的CBR分组的平均端到端延迟。随着节点密度增加,大量冗余的路由请求包占用了信道资源,使得信道竞争更加严重,从而增加了CBR分组的延迟。LQTQ减少了路由请求包,从而减缓了信道竞争,故能降低端到端延迟,平均比AODV减少了24.7%的延迟,在高密度下效果更加明显。

4 结束语

本文提出了一种基于链路质量和拓扑质量的路由协议,此协议通过剩余链路生存期作为链路质量指标,使得选取的路由有较长的生存期,从而避免了频繁的路由发现;同时为了避免路由请求包向全网的传播,根据中间节点与"源-目的"节点连线的距离关系作为拓扑质量指标,从而减少了路由请求包的个数。模拟结果显示,本文提出的LQTQ协议同AODV协议相比,显著地降低了路由控制开销并提高了分组投递率和降低了端到端延迟,进而提高了路由性能。

参考文献

[1]Andrews J,Jindal N,Haenggi M,et al.Rethinking information theory for mobile Ad Hoc networks[J],IEEE Communications Magazine,2008,46(12):94-101.

[2]Wu X,Sadjadpour H R,Garcia-Luna-Aceves J J,Routing overhead as a function of node mobility:modeling framework and implications on proactive routing[C]//Proc.IEEE MASS'07,2007:1-9.

[3]Cheng Z,Heinzelman W B.Discovering long lifetime routes in mobile ad hoc networks[J],Ad Hoc Networks,2008,6(5):661-674.

[4]Wu Y S,Lee D,Jung J.Routing algorithm limiting next hop selection distance in multi hop Ad Hoc networks[C]//Proc.ICC'09,2009:1-4.

[5]Drini M,Saadawi T.Link lifetime based route selection in mobile Ad-Hoc network[J].International Journal of Communication Networks and Information Security,2009,1(3):31-39.

[6]Abdulai J D,Ould-Khaoua M,Mackenzie L M,et al.Neighbour coverage:A dynamic probabilistic route discovery for mobile Ad hoc networks[C]//Proc.SPECTS'08,2008:165-172.

[7]Mohammed A,Ould-Khaoua M,Mackenzie L M,et al.Probabilistic counter-based route discovery for mobile Ad Hoc networks[C]//Proc.IWCMC'09,2009:1335-1339.

[8]Beraldi R.The polarized gossip protocol for path discovery in MANETs[J].Ad Hoc Networks,2008,6(1):79-91.