969TCPIP网络原理与应用.ppt

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）,这里的体系结构专指互联网络的构造方式选择的体系结构基于路由器链接起来的方式，对选路的实现方式和路由协议产生影响核心体系结构因特网早期，规模非常小，少量核心路由器构成，路由器含有关于网络的全部信息最终形成两级的层次结构作进一步扩展。非核心路由器仅有部分路由信息，依赖核心路由器完成跨越互联网的传输核心路由器之间使用网关到网关协议（GGP），核心与非核心路由器之间使用外部网关协议（EGP）扩展性不好,TCP/IP网络原理与应用 Lecture 4,路由协议体系结构（2）,自治系统体系结构摆脱了有核心的集中式概念，过渡到一个更加适合于大型的、不断增长的互联网络的分散的体系结构将互联网络看成是一组独立的群组，每个群组称为一个自治系统（Autonomous System）一个AS是由一组路由器和网络构成，它们受控于某个特定的组织或管理实体，AS采用单一的、一致的策略进行内部选路,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,IGP,IGP,IGP,IGP,IGP,EGP,EGP,EGP,内部网关协议IGP（例如，OSPF）,外部网关协议EGP（例如，BGP-4）,IGP,R3,R2,TCP/IP网络原理与应用 Lecture 4,路由协议算法和度量,算法是指协议用来确定任一对网络之间的最佳路由及在路由器之间共享选路信息的方法度量是对用来评估某条特定路由效率的“开销”的一种测度最常见的算法：距离矢量和链路状态,TCP/IP网络原理与应用 Lecture 4,距离矢量,根据网络之间的距离来选择路由一般使用网络之间的跳数或路由器数量作为距离度量路由器把所有已知网络的距离信息维护在一张表中，定期把这张表发送给与它们直接相连的每一台路由器（邻居），然后这些路由器更新自己的表并将表发送给自己的邻居最终，每台路由器都获得有关互联网络上的所有网络的距离信息RIP,TCP/IP网络原理与应用 Lecture 4,链路状态,根据两个网络之间的最短路径的动态评估来选择路由每台路由器维护一张描述互联网络当前拓扑的地图。通过对互联网络不同部分可达性的测试，以及和其他路由器交换链路状态信息，该地图得到定期更新。最佳路由（或最短路径）的确定可以基于多种度量，这些度量显示了在一条特定路由上发送一个数据报的真实开销比距离矢量算法强大得多，可动态适应网络变化；设置更为复杂，使用更多的计算机处理资源OSPF,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,RIP 协议的三个要点,仅和相邻路由器交换信息。交换的信息是当前本路由器所知道的全部信息，即自己的路由表。按固定的时间间隔交换路由信息，例如，每隔 30 秒,TCP/IP网络原理与应用 Lecture 4,1 1 2 1 3 1,F,E,D,C,B,A,5 1 6 1,2 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 A2 2 A3 1 4 1 6 2 C,A 说：“我到网 1 的距离是 1。”因此 B 现在也可以到网 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 A2 2 A3 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 和 C 的路由表,网 3,网 2,网 4,网 6,网 5,网 1,1 2 A2 2 A3 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 A2 2 A3 1 4 1 6 2 C,C 说：“我到网 4 的距离是 1。”但 B 没有必要绕道经过路由器 C再到达网 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 A2 2 A3 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 B5 2 E6 3 B,1 1 2 2 A3 2 A4 3 A5 1 6 2 F,1 2 E2 2 D3 3 C4 2 C5 1 6 1,1 3 B2 3 B3 2 B4 1 5 2 F6 1,网 2,网 6,网 5,网 1,网 3,网 4,1 2 A2 1 3 2 A4 3 A5 1 6 2 F,1 2 A2 2 A3 1 4 1 5 3 C6 2 C,TCP/IP网络原理与应用 Lecture 4,RIP 协议的优缺点,优点RIP 协议最大的优点就是实现简单，开销较小。缺点当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。限制了网络的规模，它能使用的最大距离为 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,TCP/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,R1,正常情况,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网络原理与应用 Lecture 4,OSPF(Open Shortest Path First),OSPF 协议的基本特点“开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。“最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法SPFOSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。是分布式的链路状态协议,TCP/IP网络原理与应用 Lecture 4,要点,向本自治系统中所有路由器发送信息。发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。发送信息使用的方法是洪泛法只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。,TCP/IP网络原理与应用 Lecture 4,链路状态数据库,link-state database由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点。,TCP/IP网络原理与应用 Lecture 4,Dijkstra算法,算法维护两个变量: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网络原理与应用 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)网络传输容易出错 流量管理连接可能中断 资源管理、多媒体服务质量基于电池供电 休眠状态的媒体共享、时钟同步无线广播信道 网络安全性问题移动(Mobility)与固定(Stationary)相对节点定位问题路由寻址问题漫游切换问题,TCP/IP网络原理与应用 Lecture 4,Ad Hoc网络（自组织网络）,Ad hoc网络通常即为Wireless Ad hoc Network突出移动性时也称为 Mobile Ad hoc Network(MANET)Ad Hoc网络由一组带有无线收发装置的移动终端组成的一个多跳的自治系统移动终端具有路由和报文转发功能，可通过无线连接构成任意的网络拓扑网络可以独立工作，也可以接入Internet或蜂窝无线网络（以末端子网的形式接入现有网络）,TCP/IP网络原理与应用 Lecture 4,Ad Hoc网络的特点,每个移动终端兼备路由器和主机两种功能作为主机，终端需要运行面向用户的应用程序作为路由器，终端需要运行相应的路由协议，根据路由策略和路由表参与分组转发和路由维护工作节点间的路由通常由多跳（Hop）组成。由此称为多跳无线网、自组织网络、无固定设施的网络。没有固定的基础设施动态的网络拓扑（移动性）多跳自行组织：寻址，路由，分簇，定位，功率控制能量受限,TCP/IP网络原理与应用 Lecture 4,Ad hoc网络的路由,与传统Internet在路由上的区别Internet路由基于固定的网络，路由协议需要周期性的交换信息来维护路由表或者网络拓扑Internet路由不适用于Ad hoc网络动态变化的网络拓扑结构，节点可以自主加入、离开从而导致链路状态权值的变化无线信道资源有限，限制了周期性的拓扑信息的广播节点能量有限，限制了节点交换路由信息的次数和数量单向的无线传输信道，限制了路由表的计算合并,TCP/IP网络原理与应用 Lecture 4,Ad hoc网络路由的分类,主动式路由协议Proactive protocols也称路由表驱动 Table driven每个节点维持一个到本网络其他节点的路由，路由的维护过程开销比较大选路过程的时延比较小被动式路由协议 Reactive protocols也称按需路由 On-demand每个节点仅仅在需要选路的时候才发起路由过程选路过程的时延比较大混合协议 Hybrid protocols将以上两种进行混合,TCP/IP网络原理与应用 Lecture 4,主动式路由,DSDV目标序列距离矢量协议，Destination-Sequenced Distance-Vector基于Bellman-ford路由选择算法的改进，解决了传统距离矢量路由协议中的无穷环路问题,TCP/IP网络原理与应用 Lecture 4,DSDV路由协议,DSDV Perkins1994每个节点维持一个路由表到每个目的地的下一跳信息到每个目的地的路径的代价一个抵达该目的地的序列号，序列号用来防止环路每个节点周期性的向邻居广播路由表每个节点在转发自己路由表的时候增大序列号，并将序列号连同路由表一起发送,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路由协议,DSDVX做以下操作如果 S(X)S(Y),则X忽略收到的信息如果 S(X)=S(Y),且从Y抵达Z的代价小于从X抵达Z的代价，则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 到102B 广播路由信息到邻居A和C，包括目的序号(destination sequence numbers),1,1,TCP/IP网络原理与应用 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收到信息后更新其路由表.,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网络原理与应用 Lecture 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的时候在报文上添加自己的标识符,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,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后发出 RREP(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中发回当使用 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 Hass1997ZRP 结合主动式和被动式路由表协议的优势主动式协议:主动更新和维护网络的路由信息，不论是否有流量传输的需求被动式协议：仅仅在有流量需求的时候才发起选路的请求,谢谢！,