首页 chapter5_2

chapter5_2

举报
开通vip

chapter5_2 Broadband Wireless Communications Laboratory, Xidian University 1 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 通信网络理论基础 通信工程学院信息科学研究所 http://pcn.xidian.edu.cn Broadband Wireless Communications Laboratory, Xidian University 2 ...

chapter5_2
Broadband Wireless Communications Laboratory, Xidian University 1 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 通信网络理论基础 通信工程学院信息科学研究所 http://pcn.xidian.edu.cn Broadband Wireless Communications Laboratory, Xidian University 2 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 第五章 路由算法 Broadband Wireless Communications Laboratory, Xidian University 3 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 5.2 常用的路由算法 Broadband Wireless Communications Laboratory, Xidian University 4 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ ƒ不同的应用场合对路由算法有不同的要求 ƒ广域网内的路由主要解决子网内分组的传输路径问 题,它主要包括三种路由算法:广播、最短路由和 最佳路由。 ƒ互连网中则主要采用分层的网络。 ƒ还有一类网络是Ad Hoc网络,它是一种分布式的 PRNET网络,该网络中使用了多种形式的路由算 法。 Broadband Wireless Communications Laboratory, Xidian University 5 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 1.广播(Broadcast) ƒ广播是通信网中最常用的方式,它用来传播公共信 息、拓扑变化信息(包括节点和链路工作变化和故 障等信息)。 ƒ广播分组的接收节点通常是全网所有成员。如果接 收节点仅为一个组或部分网络节点,则称为多播 (Multicast)。 Broadband Wireless Communications Laboratory, Xidian University 6 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 1.广播(Broadcast) ƒ广播时采用的路由算法可以有多种方法:如泛洪 (Flooding)路由、采用生成树(Spanning Tree)的广播方式等。 ƒ也可以逐一地把要广播的分组按照点对点的路由算 法(Unicast)发送给每一个目的节点,但这种方 法可能会浪费大量的网络资源,并且广播节点需要 知道全网所有节点的路由信息。 Broadband Wireless Communications Laboratory, Xidian University 7 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 ƒ泛洪路由的基本想法是源节点(发起广播的 节点)将消息以分组的形式发给其相邻的节 点,相邻的节点再转发给它们的相邻节点, 继续下去,直至分组到达网络中所有的节 点。为了限制分组的传输次数,需要两个附 加规则: –若节点B是从A收到一个广播分组,则B不会将该 广播分组再转发给A; –每个节点仅将相同的广播分组转发给邻节点最多 一次。 Broadband Wireless Communications Laboratory, Xidian University 8 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 ƒ具体的实现方法是: –源节点广播的每一个分组都有一个标识符(ID)和序 号,每发送一个新的分组,序号加1。每个节点在收到一 个广播分组后,要检查该分组的标识符和序号,如果该 分组的序号大于记录中具有相同标识符分组的最大序 号,则中转该分组并记录其标识符和序号,所有小于或 等于记录序号的分组都被丢弃,而不会被中转,分组的 广播过程如图5-4(a)所示。图中箭头上的标号表示该 分组被中转的次数。图中A是广播的发起节点。设L为网 络的链路数,该方法的分组传输次数在L~2L之间。为了 减少广播分组传输的次数,可以采用图5-4(b)的方 法,首先构造一个生成树,在该树上分组仅需传输N-1次 (N为网络的节点数)即可。 Broadband Wireless Communications Laboratory, Xidian University 9 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ Broadband Wireless Communications Laboratory, Xidian University 10 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 2.最短路由(Shortest Path Routing) ƒ许多实际的路由算法如RIP(Routing Information Protocol),OSPF(Open Shortest Path First)等都是基于最短路径这一概 念。分组交换网络的各种路由算法实质上都是建立 在某种形式的最小费用准则的基础上。譬如,我们 把准则定为“最短路径”,那就有所谓的“最短路径 路由算法”;这里所说的“最短路径”并不单纯意味 着一条物理长度最短的通路,它可以是从发送节点 到达接收节点的中转次数最少。 Broadband Wireless Communications Laboratory, Xidian University 11 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 ƒ最短路由的一个关键是如何定义“费用”。 ƒ如果心分组时延,则把“费用”与时延相关联。此时 “费用” 与两个参数有关:链路的物理长度和链路 上的业务强度。前者决定信道的传播时延,后者决 定分组的发送等待时延。因此,如果将两个参数的 值折算为该链路的费用或“长度”值(时延的大 小),则最小费用算法等效为最小时延路由算法。 ƒ长度通常是一个正数,它可以是物理距离的长短、 时延的大小、各个节点队列长度、最小跳数(中转 次数)等等。 ƒ其次,链路的长度随着时间可能是变化的,它取决 于链路拥塞的情况。 Broadband Wireless Communications Laboratory, Xidian University 12 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 3.最佳路由(Optimal Routing) ƒ最短路由关心一个节点对之间的一条路径的 选择和求解,因而有两个方面的缺陷: –为每对节点之间仅提供一条路由,因而限制了网 络的通过量; –适应业务变化的能力受到防止路由振荡的限制。 Broadband Wireless Communications Laboratory, Xidian University 13 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 广域网中的路由算法 3.最佳路由(Optimal Routing) ƒ最佳路由是从全网的范围寻找所有可能的传输路 径,从而使得发送节点到达接收节点的信息流的时 延最小、流量最大,而不是局限于一条所谓的最短 路径。 ƒ采用最佳路由(基于平均时延最佳化)可以克服最 短路径的上述缺陷,它可以将节点对之间的流量分 配在多条路径上,从而可使网络的通过量最大,时 延最小。 Broadband Wireless Communications Laboratory, Xidian University 14 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 互连网中的路由算法 ƒ为了实现网络之间的互连,通常采用三种设 备:网关、网桥和路由器。 –实现广域网(WAN)至广域网(WAN)之间的 互连设备称为网关(Gateway)。它完成相当复 杂的网络层的任务,包括 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 转换、路由功能 等。它通常在网际子层。 –实现局域网(LAN)与局域网(LAN)之间在 MAC层互连的设备称为网桥(Bridge)。 –实现LAN与WAN或LAN与LAN之间互连的设备称 为路由器(Router),它提供高级的路由功能。 Broadband Wireless Communications Laboratory, Xidian University 15 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 互连网中的路由算法 Broadband Wireless Communications Laboratory, Xidian University 16 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 互连网中的路由算法 ƒ可以以两种观点来看待一个互连的网络 –一是将互连的设备看成是一个附加的网络节点, 它与网络中其它节点的地位等同,所有的节点组 成一个更大的网络。网络中的每一个节点都维持 一个到达各个节点的路由表(这个表通常会很 大)。 Broadband Wireless Communications Laboratory, Xidian University 17 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 互连网中的路由算法 –第二种观点是把每个子网看成是一个节点,如图 5-5(b)所示。这样将网络分为两层,高层是由 互连设备和子网组成的网络,低层是各子网的内 部网络。 –在这种分层的方式中,Gateway或Router只维持 到达各个子网的路由表,各个子网仅维持子网内 的路由表。这样路由表的维持和修正的负荷相对 较小和易于操作。 –分层的缺点是所形成的路由对整个网络而言不一 定是最佳的。 Broadband Wireless Communications Laboratory, Xidian University 18 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 互连网中的路由算法 ƒ随着网络的增大,路由表中存储的内容也将 不断的增大。 ƒ增大的路由表不仅占用路由器的内存,而且 需要更多的CPU时间扫描表格,以及需要更 大的链路容量来传送关于路由表的状态报 告。 ƒ为了实现充分利用有限资源的同时,还可以 实现网络扩展,必须进行分级路由选择。 Broadband Wireless Communications Laboratory, Xidian University 19 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 互连网中的路由算法 ƒ所谓分级路由选择是指: –将路由器划分为区域,每个路由器仅知道怎样在 其所属区域内选择路由和知道分组在该区域要到 达的目的端的全部细节,但并不知道其它区域的 内部结构。当不同的网络相连时,很自然的将每 个网络看作为独立的区域,以便让一个网络中的 路由器免于知道其它网络的拓扑结构。从而有效 地减少了每个路由表的存储内容。 Broadband Wireless Communications Laboratory, Xidian University 20 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 互连网中的路由算法 ƒ对于大 型的网 络而 言,通 常需要 分成多 级。 Broadband Wireless Communications Laboratory, Xidian University 21 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ Ad Hoc网络中的路由算法 ƒAd Hoc提出分组无线网络的初衷是用于军事目 的,而Ad Hoc网络技术却扩展到更多的领域。 ƒ传统的路由算法(如距离矢量算法和链路状态法等) 基本上是为有线网络设计的,没有考虑到网络的动 态特性。而且在传统的路由算法中,网络管理的开 销随着网络的规模增大而迅速增长。 ƒ上述这些因素是移动Ad Hoc网络中要关注的重要 因素,而且移动Ad Hoc网络还面临着无线信道的 不可靠性、高速移动环境下链路频繁中断、故障以 及节点的能量有限等情况。 Broadband Wireless Communications Laboratory, Xidian University 22 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ Ad Hoc网络中的路由算法 ƒ传统的路由算法中都存在着一些致命的缺陷,如路 由闭环、收敛速度慢等问题。 ƒ为了适应移动Ad Hoc网络中对路由算法的新要 求,目前MANET(Mobile Ad Hoc Network)已 经在距离矢量算法和链路状态法的基础上,提出了 许多改进型的路由协议。同时,也有许多协议是直 接从有线网络继承改进得到的。 ƒ总的来说,我们可以把目前单播的Ad Hoc路由算 法分为三种: Broadband Wireless Communications Laboratory, Xidian University 23 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ Ad Hoc网络中的路由算法 Ad Hoc路由协议 平面式路由 分层路由 地理位置辅助的路由 Proactive (表驱动 路由) Reactive (按需 路由) DSDV WRP FSR FSLS AODV DSR TORA SSR ZRP HSR CGSR LANMAR GeoCast LAR DREAM GPSR Broadband Wireless Communications Laboratory, Xidian University 24 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ Ad Hoc网络中的路由算法 1. 平面式路由(Flat Routing)算法。 ƒ 网络中的所有节点都处于同一层次上,各节点 在网络中获得的路由信息基本相同。根据其设 计的具体原则可进一步的将平面式路由分为 Proactive Routing算法和Reactive Routing算 法。 Broadband Wireless Communications Laboratory, Xidian University 25 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ Ad Hoc网络中的路由算法 2. 分层路由(Hierarchical Routing)算法。 ƒ 网络按一定的规则分为多个不同的层次,在不 同层次中又可以有不同的路由策略。分层的路 由策略比较容易进行网络规模的扩充。 Broadband Wireless Communications Laboratory, Xidian University 26 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ Ad Hoc网络中的路由算法 3. 地理位置辅助的路由(Geographic position assisted Routing)算法。 ƒ 网络中的节点可以获得节点的地理位置信息, 通过这些信息可以有效的降低路由算法中路由 建立或维护的开销。 通信网络理论基础 第五章��路由算法 5.2 常用的路由算法 广域网中的路由算法 广域网中的路由算法 广域网中的路由算法 广域网中的路由算法 广域网中的路由算法 广域网中的路由算法 广域网中的路由算法 广域网中的路由算法 互连网中的路由算法 互连网中的路由算法 互连网中的路由算法 互连网中的路由算法 互连网中的路由算法 互连网中的路由算法 互连网中的路由算法 Ad Hoc网络中的路由算法 Ad Hoc网络中的路由算法 Ad Hoc网络中的路由算法 Ad Hoc网络中的路由算法 Ad Hoc网络中的路由算法 Ad Hoc网络中的路由算法
本文档为【chapter5_2】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_414650
暂无简介~
格式:pdf
大小:244KB
软件:PDF阅读器
页数:26
分类:互联网
上传时间:2012-05-25
浏览量:12