第3章-3+ Ad hoc路由协议.ppt

第3章-3+ Ad hoc路由协议 主要内容 ??1. 路由协议概述 ??2. 两类典型自适应路由协议 ??3. Ad hoc网络路由问题及协议分类 ??4. 主动路由协议 ??5. 按需路由协议 ??6. 其它路由协议 1. 路由协议概述 路由协议是执行路由算法的硬件或者软件 路由算法涉及两个基本动作:路径选择和数据转发 路径选择即判定到达目的地的最佳路线，由路由选择算法来实现。 数据转发即沿行径好的最佳路径传送信息分组。 他们分别有各自的协议——路由选择协议(routing protocol)和路由转发协议(routed protocol)。 单播/组播 单播：一点对一点的分组传输方式； 组播：一点对多点的分组传输方式； 1. 路由协议概述（续） 路由的功能在网络层实现。 网络层的主要功能是将分组从信源经选定的路由把信息送到信宿节点。路由算法和它使用的数据结构是网络层设计的一个主要方面。 路由选择算法:负责确定所收到的分组转发到哪一个链路接口。 路由选择算法应尽量满足如下特征： 正确性、简单、稳定性、稳健性、最优性和公平性、高效性 1. 路由协议概述（续） 稳健性是指网络在面临局部故障或者超负荷时依然能够经过其他路由进行分组转发，不造成分组的丢失或者虚电路的中断。 稳健性的设计要考虑到与稳定性的折中问题。 在公平性和最优性之间也存在相互折衷问题。某些旨在提高性能的机制给相邻节点之间的分组交换的优先级别，可能要高于给相距较远的站点之间的分组交换的优先级别。这一策略可以获得最大的平均吞吐量，但对那些主要是与远距离站点通信的站点来说则是不公平的。 1. 路由协议概述（续） 路由协议的性能评估标准 通常路由选择是基于某些性能评估标准的，如跳数、费用、时延、吞吐量等。 路由选择策略 在分组交换网中，已逐渐发展出大量的路由选择策略，主要有如下四种： 1）固定式路由选择：固定式路由选择为网络中的每一个源站和信宿站点选择一条永久的路由。这些路由是固定的，只有在网络结构发生变化时，它们才有可能改变。因此，在设计路由时所使用的链路费用不可能是基于通信量等的动态变量，而是基于预期的通信量或容量。 1. 路由协议概述（续） 2）泛洪算法：泛洪法是一种简单的路由选择技术。这种技术不需要任何网络信息，一个分组由源节点发送到与其相邻的每一个节点。在各个节点上，收到的分组再次被传输到除分组到达时所经过的链路以外的所有输出链路。 泛洪法具有三个属性： A: 在源节点与信宿节点之间所有可能的路由都被尝试过； B：分组中至少有一个副本使用的是最小跳数路由到达信宿； C：所有直接或间接与源节点相连的节点全部被访问到。 特点：高度稳健；用于其它路由协议的建立；路由协议信息发布 1. 路由协议概述（续） 3）随机路由选择：随机路由选择具有泛洪法的简单性和稳健性，并且具有远低于泛洪法的通信量负荷。 使用随机路由选择时，为了重传收到的分组，节点只选择一条输出链路。这条链路是从除了分组到达所经过的那条链路之外的其他链路中随机选中的。如果所有链路被选中的可能性相等，那么节点可以简单地以轮流方式使用输出链路。 改进技术是为每条链路分配一个概率，并根据这个概率来选择链路。 4）自适应路由选择：事实上，在所有的分组交换网中，都使用了某种形式的自适应路由选择 1. 路由协议概述（续） 路由选择算法的分类 路由选择算法可以分为两大类： 1）非自适应算法 非自适应算法不根据实测或估计的网络的当前通信量和拓扑结构来做路由选择，所有路由都是离线计算好的，称为静态路由选择。 2）自适应算法 自适应算法根据网络拓扑结构、通信量的变化等进行路由选择。根据其获取信息方式、路由选择的条件、优化的参数，又可以分为不同的种类。 事实上，在所有的分组交换网中，都使用了某种形式的自适应路由选择。 1. 路由协议概述（续） 影响路由选择判决的主要条件： 1)故障：当一个节点或一条中继线发生故障时，它就不能被用作路由的一部分 2)拥塞：当网络的某部分十分拥塞时，最好让分组绕道而行。 要使自适应路由选择成为可能，就必须在节点和节点之间交换有关网络状态的信息。也就是说，自适应路由的实现是有代价的，如增加了节点的处理负担，增加了网络的额外开销等。 2.两类典型自适应路由协议 TCP