《969-《TCPIP网络原理与应用》.ppt》由会员分享,可在线阅读,更多相关《969-《TCPIP网络原理与应用》.ppt(66页珍藏版)》请在三一文库上搜索。
1、TCP/IP网络原理与应用,华中科技大学电信系 2011.09,TCP/IP网络原理与应用 Lecture 4,第四章、路由算法与协议,4.1 基本概念 4.2 路由选择协议回顾 4.3 无线路由选择协议 4.3.1 无线和移动对通信网络的挑战 4.3.2 无线自组织网络 4.3.3 主动式路由 4.3.4 被动式路由 4.3.5 混合路由,TCP/IP网络原理与应用 Lecture 4,路由协议体系结构(1),这里的体系结构专指互联网络的构造方式 选择的体系结构基于路由器链接起来的方式,对选路的实现方式和路由协议产生影响 核心体系结构 因特网早期,规模非常小,少量核心路由器构成,路由器含有关
2、于网络的全部信息 最终形成两级的层次结构作进一步扩展。非核心路由器仅有部分路由信息,依赖核心路由器完成跨越互联网的传输 核心路由器之间使用网关到网关协议(GGP),核心与非核心路由器之间使用外部网关协议(EGP) 扩展性不好,TCP/IP网络原理与应用 Lecture 4,路由协议体系结构(2),自治系统体系结构 摆脱了有核心的集中式概念,过渡到一个更加适合于大型的、不断增长的互联网络的分散的体系结构 将互联网络看成是一组独立的群组,每个群组称为一个自治系统(Autonomous System) 一个AS是由一组路由器和网络构成,它们受控于某个特定的组织或管理实体,AS采用单一的、一致的策略进
3、行内部选路,TCP/IP网络原理与应用 Lecture 4,现代路由协议类型,AS之内与AS之间的选路有本质区别 内部选路协议(内部网关协议) 用于在一个AS内的路由器之间交换路由信息 AS之间不使用内部选路协议 每个AS可以使用不同的内部选路协议 外部选路协议(外部网关协议) 在AS之间交换选路信息 某些情况下也可能用于一个AS内部的路由器之间,但主要处理AS之间的信息交换 每个AS必须使用相同的外部选路协议以确保他们能够通信,TCP/IP网络原理与应用 Lecture 4,R1,H1,H2,内部网关协议 IGP (例如,RIP),IGP,IGP,IGP,IGP,IGP,IGP,IGP,IG
4、P,IGP,IGP,IGP,IGP,EGP,EGP,EGP,内部网关协议 IGP (例如,OSPF),外部网关协议 EGP (例如,BGP-4),IGP,R3,R2,TCP/IP网络原理与应用 Lecture 4,路由协议算法和度量,算法是指协议用来确定任一对网络之间的最佳路由及在路由器之间共享选路信息的方法 度量是对用来评估某条特定路由效率的“开销”的一种测度 最常见的算法:距离矢量和链路状态,TCP/IP网络原理与应用 Lecture 4,距离矢量,根据网络之间的距离来选择路由 一般使用网络之间的跳数或路由器数量作为距离度量 路由器把所有已知网络的距离信息维护在一张表中,定期把这张表发送给
5、与它们直接相连的每一台路由器(邻居),然后这些路由器更新自己的表并将表发送给自己的邻居 最终,每台路由器都获得有关互联网络上的所有网络的距离信息 RIP,TCP/IP网络原理与应用 Lecture 4,链路状态,根据两个网络之间的最短路径的动态评估来选择路由 每台路由器维护一张描述互联网络当前拓扑的地图。通过对互联网络不同部分可达性的测试,以及和其他路由器交换链路状态信息,该地图得到定期更新。最佳路由(或最短路径)的确定可以基于多种度量,这些度量显示了在一条特定路由上发送一个数据报的真实开销 比距离矢量算法强大得多,可动态适应网络变化;设置更为复杂,使用更多的计算机处理资源 OSPF,TCP/
6、IP网络原理与应用 Lecture 4,第四章、路由算法与协议,4.1 基本概念 4.2 路由选择协议回顾 4.3 无线路由选择协议 4.3.1 无线和移动对通信网络的挑战 4.3.2 无线自组织网络 4.3.3 主动式路由 4.3.4 被动式路由 4.3.5 混合路由,TCP/IP网络原理与应用 Lecture 4,RIP 协议的三个要点,仅和相邻路由器交换信息。 交换的信息是当前本路由器所知道的全部信息,即自己的路由表。 按固定的时间间隔交换路由信息,例如,每隔 30 秒,TCP/IP网络原理与应用 Lecture 4,1 1 2 1 3 1 ,F,E,D,C,B,A,5 1 6 1 ,2
7、 1 5 1 ,3 1 4 1 ,4 1 6 1 ,1 1 5 1 ,一开始,各路由表只有到相邻路由器的信息,网 3,网 2,网 4,网 6,网 5,网 1,“4”表示“从本路由器到网 4”,“1”表示“距离是 1”,“”表示“直接交付”,TCP/IP网络原理与应用 Lecture 4,F,E,D,C,B,A,5 1 6 1 ,2 1 5 1 ,3 1 4 1 ,1 1 5 1 ,路由器 B 收到相邻路由器 A 和 C 的路由表,网 3,网 2,网 4,网 6,网 5,网 1,1 2 A 2 2 A 3 1 4 1 6 2 C,A 说:“我到网 1 的距离是 1。” 因此 B 现在也可以到网
8、1, 距离是 2,经过 A。”,TCP/IP网络原理与应用 Lecture 4,F,E,D,C,B,A,5 1 6 1 ,2 1 5 1 ,3 1 4 1 ,1 1 5 1 ,路由器 B 收到相邻路由器 A 和 C 的路由表,网 3,网 2,网 4,网 6,网 5,网 1,1 2 A 2 2 A 3 1 4 1 6 2 C,A 说:“我到网 2 的距离是 1。” 因此 B 现在也可以到网 2, 距离是 2,经过 A。”,TCP/IP网络原理与应用 Lecture 4,F,E,D,C,B,A,5 1 6 1 ,2 1 5 1 ,3 1 4 1 ,1 1 5 1 ,路由器 B 收到相邻路由器 A
9、和 C 的路由表,网 3,网 2,网 4,网 6,网 5,网 1,1 2 A 2 2 A 3 1 4 1 6 2 C,A 说:“我到网 3 的距离是 1。” 但 B 没有必要绕道经过路由器 A 再到达网 3,因此这一项目不变。,TCP/IP网络原理与应用 Lecture 4,F,E,D,C,B,A,5 1 6 1 ,2 1 5 1 ,3 1 4 1 ,1 1 5 1 ,路由器 B 收到相邻路由器 A 和 C 的路由表,网 3,网 2,网 4,网 6,网 5,网 1,1 2 A 2 2 A 3 1 4 1 6 2 C,C 说:“我到网 4 的距离是 1。” 但 B 没有必要绕道经过路由器 C 再
10、到达网 4,因此这一项目不变。,TCP/IP网络原理与应用 Lecture 4,F,E,D,C,B,A,5 1 6 1 ,2 1 5 1 ,3 1 4 1 ,1 1 5 1 ,路由器 B 收到相邻路由器 A 和 C 的路由表,网 3,网 2,网 4,网 6,网 5,网 1,1 2 A 2 2 A 3 1 4 1 6 2 C,C 说:“我到网 6 的距离是 1。” 因此 B 现在也可以到网 6, 距离是 2,经过 C。”,TCP/IP网络原理与应用 Lecture 4,最终所有的路由器的路由表都更新了,F,E,D,C,B,A,1 1 2 1 3 1 4 2 B 5 2 E 6 3 B,1 1 2
11、 2 A 3 2 A 4 3 A 5 1 6 2 F,1 2 E 2 2 D 3 3 C 4 2 C 5 1 6 1 ,1 3 B 2 3 B 3 2 B 4 1 5 2 F 6 1 ,网 2,网 6,网 5,网 1,网 3,网 4,1 2 A 2 1 3 2 A 4 3 A 5 1 6 2 F,1 2 A 2 2 A 3 1 4 1 5 3 C 6 2 C,TCP/IP网络原理与应用 Lecture 4,RIP 协议的优缺点,优点 RIP 协议最大的优点就是实现简单,开销较小。 缺点 当网络出现故障时,要经过比较长的时间才能将此信息传送到所有的路由器。 限制了网络的规模,它能使用的最大距离为
12、 15(16 表示不可达)。 路由器之间交换的路由信息是路由器中的完整路由表,因而随着网络规模的扩大,开销也就增加。,TCP/IP网络原理与应用 Lecture 4,R2,R1,正 常 情 况,1 1 ,1 2 R1,R1 说:“我到网 1 的距离是 1,是直接交付。”,“1”表示“从本路由器到网 1”,“1”表示“距离是 1”,“”表示“直接交付”,TCP/IP网络原理与应用 Lecture 4,R2,R1,正 常 情 况,1 1 ,1 2 R1,R2 说:“我到网 1 的距离是 2,是经过 R1。”,“1”表示“从本路由器到网 1”,“2”表示“距离是 2”,“R1”表示 经过 R1,TC
13、P/IP网络原理与应用 Lecture 4,R2,R1,正 常 情 况,1 1 ,1 2 R1,R1 说:“我到网 1 的距离是 16 (表示无法到达), 是直接交付。”,但 R2 在收到 R1 的更新报文之前,还发送原来的报文, 因为这时 R2 并不知道 R1 出了故障。,TCP/IP网络原理与应用 Lecture 4,R2,R1,正 常 情 况,1 1 ,1 2 R1,R1 收到 R2 的更新报文后,误认为可经过 R2 到达网1,于是更新自己的路由表,说:“我到网 1 的距离是 3,下一跳经过 R2”。然后将此更新信息发送给 R2。,TCP/IP网络原理与应用 Lecture 4,R2,R
14、1,正 常 情 况,1 1 ,1 2 R1,R2 以后又更新自己的路由表为“1, 4, R1”,表明 “我到网 1 距离是 4,下一跳经过 R1”。,TCP/IP网络原理与应用 Lecture 4,R2,R1,R2,R1,网 1出了故障,正 常 情 况,1 1 ,1 16 ,1 5 R2,1 2 R1,1 2 R1,这样不断更新下去,直到 R1 和 R2 到网 1 的距离都增大到 16 时,R1 和 R2 才知道网1是不可达的。,这就是好消息传播得快,而坏消息传播得慢。网络出故障的传播时间往往需要较长的时间(例如数分钟)。这是 RIP 的一个主要缺点。,TCP/IP网络原理与应用 Lectur
15、e 4,OSPF(Open Shortest Path First),OSPF 协议的基本特点 “开放”表明 OSPF 协议不是受某一家厂商控制,而是公开发表的。 “最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法SPF OSPF 只是一个协议的名字,它并不表示其他的路由选择协议不是“最短路径优先”。 是分布式的链路状态协议,TCP/IP网络原理与应用 Lecture 4,要点,向本自治系统中所有路由器发送信息。 发送的信息就是与本路由器相邻的所有路由器的链路状态,但这只是路由器所知道的部分信息。 “链路状态”就是说明本路由器都和哪些路由器相邻,以及该链路的“度量”(metri
16、c)。 发送信息使用的方法是洪泛法 只有当链路状态发生变化时,路由器才用洪泛法向所有路由器发送此信息。,TCP/IP网络原理与应用 Lecture 4,链路状态数据库,link-state database 由于各路由器之间频繁地交换链路状态信息,因此所有的路由器最终都能建立一个链路状态数据库。 这个数据库实际上就是全网的拓扑结构图,它在全网范围内是一致的(这称为链路状态数据库的同步)。 OSPF 的链路状态数据库能较快地进行更新,使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点。,TCP/IP网络原理与应用 Lecture 4,Dijkstra算法,算法维护两个变量:
17、 M:到目前为止被算法发现最小费用路径到达的节点的集合 C(n) 从源节点到节点n的路径的费用,TCP/IP网络原理与应用 Lecture 4,Dijkstra算法,初始化:先令M=1,对于不在M中的节点v,若v直接与1相连,c(v)=l(1,v);否则,c(v)=正无穷 寻找一个不在M中的节点w,其c(w)最小。把它加入M中。然后对所有不在M中的节点v,用c(v)和c(w)+l(w,v)的较小值去更新原有的c(v) 重复步骤2,直到所有节点都被包含在M中,TCP/IP网络原理与应用 Lecture 4,一个例子,TCP/IP网络原理与应用 Lecture 4,一个例子,TCP/IP网络原理与
18、应用 Lecture 4,第四章、路由算法与协议,4.1 基本概念 4.2 路由选择协议回顾 4.3 无线路由选择协议 4.3.1 无线和移动对通信网络的挑战 4.3.2 无线自组织网络 4.3.3 主动式路由 4.3.4 被动式路由 4.3.5 混合路由,TCP/IP网络原理与应用 Lecture 4,4.3.1 无线和移动对通信网络的挑战,无线网络的两个主要挑战在于其无线和移动 无线(Wireless) 与有线(Wired)相对 不局限于有基础设施 自组织(Ad hoc)网络 传输容易出错 流量管理 连接可能中断 资源管理、多媒体服务质量 基于电池供电 休眠状态的媒体共享、时钟同步 无线广
19、播信道 网络安全性问题 移动(Mobility) 与固定(Stationary)相对 节点定位问题 路由寻址问题 漫游切换问题,TCP/IP网络原理与应用 Lecture 4,Ad Hoc网络(自组织网络),Ad hoc网络 通常即为Wireless Ad hoc Network 突出移动性时也称为 Mobile Ad hoc Network (MANET) Ad Hoc网络 由一组带有无线收发装置的移动终端组成的一个多跳的自治系统 移动终端具有路由和报文转发功能,可通过无线连接构成任意的网络拓扑 网络可以独立工作,也可以接入Internet或蜂窝无线网络(以末端子网的形式接入现有网络),TC
20、P/IP网络原理与应用 Lecture 4,Ad Hoc网络的特点,每个移动终端兼备路由器和主机两种功能 作为主机,终端需要运行面向用户的应用程序 作为路由器,终端需要运行相应的路由协议,根据路由策略和路由表参与分组转发和路由维护工作 节点间的路由通常由多跳(Hop)组成。由此称为多跳无线网、自组织网络、无固定设施的网络。 没有固定的基础设施 动态的网络拓扑(移动性) 多跳 自行组织:寻址,路由,分簇,定位,功率控制 能量受限,TCP/IP网络原理与应用 Lecture 4,Ad hoc网络的路由,与传统Internet在路由上的区别 Internet路由基于固定的网络,路由协议需要周期性的交
21、换信息来维护路由表或者网络拓扑 Internet路由不适用于Ad hoc网络 动态变化的网络拓扑结构,节点可以自主加入、离开从而导致链路状态权值的变化 无线信道资源有限,限制了周期性的拓扑信息的广播 节点能量有限,限制了节点交换路由信息的次数和数量 单向的无线传输信道,限制了路由表的计算合并,TCP/IP网络原理与应用 Lecture 4,Ad hoc网络路由的分类,主动式路由协议Proactive protocols 也称路由表驱动 Table driven 每个节点维持一个到本网络其他节点的路由,路由的维护过程开销比较大 选路过程的时延比较小 被动式路由协议 Reactive protoc
22、ols 也称按需路由 On-demand 每个节点仅仅在需要选路的时候才发起路由过程 选路过程的时延比较大 混合协议 Hybrid protocols 将以上两种进行混合,TCP/IP网络原理与应用 Lecture 4,主动式路由,DSDV 目标序列距离矢量协议,Destination-Sequenced Distance-Vector 基于Bellman-ford路由选择算法的改进,解决了传统距离矢量路由协议中的无穷环路问题,TCP/IP网络原理与应用 Lecture 4,DSDV路由协议,DSDV Perkins1994 每个节点维持一个路由表 到每个目的地的下一跳信息 到每个目的地的路径
23、的代价 一个抵达该目的地的序列号,序列号用来防止环路 每个节点周期性的向邻居广播路由表 每个节点在转发自己路由表的时候增大序列号,并将序列号连同路由表一起发送,TCP/IP网络原理与应用 Lecture 4,DSDV路由协议,DSDV 假设X从Y收到一个到Z的路由信息 用S(X) 表示存放在X的路由表中的以Z为目的地的序列号,S(Y)表示从Y发送过来的以Z为目的地的序列号,X,Y,Z,TCP/IP网络原理与应用 Lecture 4,DSDV路由协议,DSDV X做以下操作 如果 S(X) S(Y), 则X忽略收到的信息 如果 S(X) = S(Y), 且从Y抵达Z的代价小于从X抵达Z的代价,则
24、X将Y设为到达Z的下一跳 如果 S(X) S(Y), X将Y设为到达Z的下一跳,将S(Y)赋值给S(X),X,Y,Z,TCP/IP网络原理与应用 Lecture 4,DSDV(1),C,B,A,1,2,TCP/IP网络原理与应用 Lecture 4,(A, 1, A-550) (B, 0, B-102) (C, 1, C-588),(A, 1, A-550) (B, 0, B-102) (C, 1, C-588),DSDV(2),C,B,A,B 增加序号从100 到102 B 广播路由信息到邻居A和C,包括目的序号(destination sequence numbers),1,1,TCP/I
25、P网络原理与应用 Lecture 4,(D, 0, D-000),DSDV(3),C,B,A,D,1. D 首次广播,序号D-000,2. 为D增加表项,其序号为D-00,随后立即广播自己的路由表信息,TCP/IP网络原理与应用 Lecture 4,(A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1, D-000),(A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1, D-000),DSDV(4),C,B,A,D, ,3. C增加C其序号为C-592,然后广播更新的路由表信息,4. B收到信息后更新其路由表
26、.,TCP/IP网络原理与应用 Lecture 4,(D, 2, D-100),(D, 2, D-100),DSDV(5),C,B,A,D,1. C检测到链路断开,将序号增加1,2. B的广播信息不影响C(C知道B的信息是过时的,因为它为D维护了一个更大的序号),TCP/IP网络原理与应用 Lecture 4,(D, , D-101),(D, , D-101),DSDV (Immediate Advertisement),C,B,A,D,1. C检测到链路断开,将序号增加1,3. 从B传播到A,引发路由表表项的更新,2. 从C传播到B,引发路由表表项的更新,TCP/IP网络原理与应用 Lect
27、ure 4,被动式路由协议,DSR 动态源路由选择协议,Dynamic Source Routing 在数据报头部携带到达目的地的路由信息 AODV 自组织按需的距离向量路由协议,Ad Hoc On-Demand Distance Vector Routing 路径中间节点建立和维护动态路由表,TCP/IP网络原理与应用 Lecture 4,被动式路由:DSR,DSR 源节点S需要向目的节点D发送数据包但是却不知道到达D的路径,此时S发起路由发现过程 DSR是一种基于源路由的按需路由查找协议 源节点将Route Request (RREQ) 洪泛 每个节点在转发RREQ的时候在报文上添加自己的
28、标识符,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,当源节点S收到RREP(Route Reply)时,它将RREP中的路由信息缓存起来 当源节点S向目的节点D发送数据时,它将完整的多跳路径包含在数据包头内发送(这种由原节点制定完整路由的方式称为源路由) 中间节点通过数据包中携带的源路由来确定数据包的转发对象,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR的路由发现过程,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR的路由发现过程,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR的路由发现过程,B,A,S
29、,E,F,H,J,D,C,G,I,K,Z,Y,M,N,L,S,E,S,C,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR的路由发现过程,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR的路由发现过程,B,A,S,E,F,H,J,D,C,G,I,K,Z,Y,M,节点 J 和 K 都向节点D广播RREQ,N,L,S,C,G,K,S,E,F,J,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR的路由发现过程,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR的路由发现过程 目的节点D收到第一个RREQ后发出 RR
30、EP (Route Reply) RREP 沿着RREQ中携带路径的反向路径发送 RREP 包含RREQ从源端S到目的地D时使用的路径,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR路由回应过程,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR路由回应过程 路由回应只有在双向对称链路的情况下才通过RREQ反向路径发送 可以通过旨在双向对成链路上接收、转发RREQ来保证 当需要支持非对称链路时,RREP的发送需要从D到S重新寻路。 目的节点D已知一条到达S的路径时除外 当目的节点发起寻找S的过程时,RREP可以捎带在这次寻路的RREQ中发回 当使用
31、IEEE 802.11 MAC时,连路必须是双向对称的,因为需要又前述的回应过程,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,DSR路由回应过程,TCP/IP网络原理与应用 Lecture 4,DSR路由协议,优点 只在有通信需求的时候才查找和维护路由 减少了不断维护路由表的开销 Route caching 进一步减少了路由发现的开销 能够得到多条路径,从而支持多径传输 缺点 包头长度随路径长度变化 洪泛的方法可能将报文广播给网络全体节点 邻居节点发出的报文有可能冲突 根据过期cache发出的报文会干扰其它节点的cache,使之也失效,TCP/IP网络原理与应用 Lecture 4,主动式路由 vs. 被动式路由,TCP/IP网络原理与应用 Lecture 4,混合路由协议,ZRP 区域路由协议,Zone Routing Protocol 在区域内使用表驱动路由协议,在区域间使用按需路由协议,TCP/IP网络原理与应用 Lecture 4,混合路由协议: ZRP,ZRP Hass1997 ZRP 结合主动式和被动式路由表协议的优势 主动式协议: 主动更新和维护网络的路由信息,不论是否有流量传输的需求 被动式协议:仅仅在有流量需求的时候才发起选路的请求,谢谢!,
链接地址:https://www.31doc.com/p-3025918.html