《计算机网络教学资料》第7章.ppt

1,7.4 因特网控制报文协议 ICMP,为了提高 IP 数据报交付成功的机会，在网际层使用了因特网控制报文协议 ICMP(Internet Control Message Protocol)。ICMP 允许主机或路由器报告差错情况和提供有关异常情况的报告。ICMP 不是高层协议，而是 IP 层的协议。ICMP 报文作为 IP 层数据报的数据，加上数据报的首部，组成 IP 数据报发送出去。,2,ICMP 报文的格式,首 部,ICMP 报文,0,数 据 部 分,检验和,类型,代码,（这 4 个字节取决于 ICMP 报文的类型）,8,16,31,IP 数据报,前 4 个字节都是一样的,ICMP 的数据部分（长度取决于类型）,3,ICMP 报文,ICMP 报文的种类有两种，即 ICMP 差错报告报文和 ICMP 询问报文。ICMP 报文的前 4 个字节是统一的格式，共有三个字段：即类型、代码和检验和。接着的 4 个字节的内容与 ICMP 的类型有关。,4,ICMP 差错报告报文共有 5 种,终点不可达 源站抑制 时间超过 参数问题 改变路由（重定向）,5,ICMP 差错报告报文的数据字段的内容,首部,IP 数据报,ICMP 的前 8 字节,装入 ICMP 报文的 IP 数据报,IP 数据报首部,ICMP 差错报告报文,8字节,收到的 IP 数据报,IP 数据报首部,8字节,ICMP 差错报告报文,IP 数据报的数据字段,6,不应发送 ICMP 差错报告报文的几种情况,对 ICMP 差错报告报文不再发送 ICMP 差错报告报文。对第一个分片的数据报片的所有后续数据报片都不发送 ICMP 差错报告报文。对具有多播地址的数据报都不发送 ICMP 差错报告报文。对具有特殊地址（如或）的数据报不发送 ICMP 差错报告报文。,7,ICMP 询问报文有四种,回送请求和回答报文时间戳请求和回答报文掩码地址请求和回答报文路由器询问和通告报文,8,PING(Packet InterNet Groper),PING 用来测试两个主机之间的连通性。PING 使用了 ICMP 回送请求与回送回答报文。PING 是应用层直接使用网络层 ICMP 的例子，它没有通过运输层的 TCP 或UDP。,9,7.5 因特网的路由选择协议7.5.1 有关路由选择协议的几个基本概念,1.理想的路由算法算法必须是正确的和完整的。算法在计算上应简单。算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。算法应具有稳定性。算法应是公平的。算法应是最佳的。,10,代价,在研究路由选择时，需要给每一条链路指明一定的代价。这里“代价”并不是指“钱”，而是由一个或几个因素综合决定的一种度量(metric)，如链路长度、数据率、链路容量、是否要保密、传播时延等，甚至还可以是一天中某一个小时内的通信量、结点的缓存被占用的程度、链路差错率等。,11,最佳路由,不存在一种绝对的最佳路由算法。所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。实际的路由选择算法，应尽可能接近于理想的算法。路由选择是个非常复杂的问题它是网络中的所有结点共同协调工作的结果。路由选择的环境往往是不断变化的，而这种变化有时无法事先知道。,12,从路由算法 的自适应性考虑,静态路由选择策略即非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。动态路由选择策略即自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。,13,2.分层次的路由选择协议,因特网采用分层次的路由选择协议。因特网的规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使因特网的通信链路饱和。许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到因特网上。,14,自治系统(autonomous system),因特网将整个互联网划分为许多较小的自治系统 AS。一个自治系统是一个互联网，其最重要的特点就是自治系统有权自主地决定在本系统内应采用何种路由选择协议。一个自治系统内的所有网络都属于一个行政单位(例如，一个公司，一所大学，政府的一个部门，等等)来管辖。一个自治系统的所有路由器在本自治系统内都必须是连通的。,15,因特网有两大类路由选择协议,内部网关协议 IGP(Interior Gateway Protocol)即在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。外部网关协议EGP(External Gateway Protocol)若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议 EGP。在外部网关协议中目前使用最多的是 BGP-4。,16,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,自治系统和内部网关协议、外部网关协议,17,因特网的路由选择协议,内部网关协议 IGP：具体的协议有多种，如 RIP 和 OSPF 等。外部网关协议 EGP：目前使用的协议就是 BGP。,18,7.5.2 内部网关协议 RIP(Routing Information Protocol),1.工作原理路由信息协议 RIP 是内部网关协议 IGP中最先得到广泛使用的协议。RIP 是一种分布式的基于距离向量的路由选择协议。RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。,19,“距离”的定义,从一路由器到直接连接的网络的距离定义为 1。从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。,20,“距离”的定义,RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”。RIP 允许一条路径最多只能包含 15 个路由器。“距离”的最大值为16 时即相当于不可达。可见 RIP 只适用于小型互联网。RIP 不能在两个网络之间同时使用多条路由。RIP 选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。,21,RIP 协议的三个要点,仅和相邻路由器交换信息。交换的信息是当前本路由器所知道的全部信息，即自己的路由表。按固定的时间间隔交换路由信息，例如，每隔 30 秒。,22,路由表的建立,路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。RIP 协议的收敛(convergence)过程较快，即在自治系统中所有的结点都得到正确的路由选择信息的过程。,23,2.距离向量算法,收到相邻路由器（其地址为 X）的一个 RIP 报文：(1)先修改此 RIP 报文中的所有项目：将“下一跳”字段中的地址都改为 X，并将所有的“距离”字段的值加 1。(2)对修改后的 RIP 报文中的每一个项目，重复以下步骤：若项目中的目的网络不在路由表中，则将该项目加到路由表中。否则 若下一跳字段给出的路由器地址是同样的，则将收到的项目替换原路由表中的项目。否则 若收到项目中的距离小于路由表中的距离，则进行更新，否则，什么也不做。(3)若 3 分钟还没有收到相邻路由器的更新路由表，则将此相邻路由器记为不可达的路由器，即将距离置为16（距离为16表示不可达）。(4)返回。,24,路由器之间交换信息,RIP协议让互联网中的所有路由器都和自己的相邻路由器不断交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。,25,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”,“”表示“直接交付”,26,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。”,27,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。”,28,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，因此这一项目不变。,29,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，因此这一项目不变。,30,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。”,31,最终所有的路由器的路由表都更新了,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,32,RIP 协议的优缺点,RIP 存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。RIP 协议最大的优点就是实现简单，开销较小。RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。,33,R2,R1,正常情况,1 1,1 2 R1,R1 说：“我到网 1 的距离是 1，是直接交付。”,“1”表示“从本路由器到网 1”,“1”表示“距离是 1”,“”表示“直接交付”,34,R2,R1,正常情况,1 1,1 2 R1,R2 说：“我到网 1 的距离是 2，是经过 R1。”,“1”表示“从本路由器到网 1”,“2”表示“距离是 2”,“R1”表示经过 R1,35,R2,R1,正常情况,1 1,1 2 R1,R1 说：“我到网 1 的距离是 16（表示无法到达），是直接交付。”,但 R2 在收到 R1 的更新报文之前，还发送原来的报文，因为这时 R2 并不知道 R1 出了故障。,36,R2,R1,正常情况,1 1,1 2 R1,R1 收到 R2 的更新报文后，误认为可经过 R2 到达网1，于是更新自己的路由表，说：“我到网 1 的距离是 3，下一跳经过 R2”。然后将此更新信息发送给 R2。,37,R2,R1,正常情况,1 1,1 2 R1,R2 以后又更新自己的路由表为“1,4,R1”，表明“我到网 1 距离是 4，下一跳经过 R1”。,38,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 的一个主要缺点。,39,1979年，距离-向量算法被链路状态路由算法所代替原因：距离-向量路由算法没有考虑物理线路的带宽存在慢收敛问题：路由器不可能得到有关全网的拓扑结构及状态，算法只是在相邻路由器之间交换的部分路由信息。路由更新消息对每个目的地都有相应的项，该更新消息的大小与网络规模成正比，同时距离向量算法要求所有的节点都参加，交换的信息量是非常巨大的。,7.5.3 内部网关协议 OSPF(Open Shortest Path First),40,7.5.3 内部网关协议 OSPF(Open Shortest Path First),1.OSPF 协议的基本特点“开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。“最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法SPFOSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。是分布式的链路状态协议。,41,三个要点,向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法。发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。,42,链路状态数据库(link-state database),由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点。,43,OSPF 的区域(area),为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫作区域。每一个区域都有一个 32 bit 的区域标识符（用点分十进制表示）。区域也不能太大，在一个区域内的路由器最好不超过 200 个。,44,OSPF 划分为两种不同的区域,区域,区域,主干区域,至其他自治系统,R9,R7,R6,R5,R4,R3,R2,R1,网 8,网 6,网 3,网 2,网 1,网 7,区域,网 4,网 5,R8,45,划分区域,划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。OSPF 使用层次结构的区域划分。在上层的区域叫作主干区域(backbone area)。主干区域的标识符规定为。主干区域的作用是用来连通其他在下层的区域。,46,主干路由器,区域,区域,主干区域,至其他自治系统,R9,R7,R6,R5,R4,R3,R2,R1,网 8,网 6,网 3,网 2,网 1,网 7,区域,网 4,网 5,R8,47,区域边界路由器,区域,区域,主干区域,至其他自治系统,R9,R7,R6,R5,R4,R3,R2,R1,网 8,网 6,网 3,网 2,网 1,网 7,区域,网 4,网 5,R8,48,OSPF 直接用 IP 数据报传送,OSPF 不用 UDP 而是直接用 IP 数据报传送，可见 OSPF 的位置在网络层。OSPF 构成的数据报很短。这样做可减少路由信息的通信量。数据报很短的另一好处是可以不必将长的数据报分片传送。分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。,49,OSPF 的其他特点,OSPF 对不同的链路可根据 IP 分组的不同服务类型 TOS 而设置成不同的代价。因此，OSPF 对于不同类型的业务可计算出不同的路由。如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。这叫作多路径间的负载平衡。支持可变长度的子网划分和无分类编址 CIDR。每一个链路状态都带上一个 32 bit 的序号，序号越大状态就越新。,50,IP 数据报,OSPF 分组,IP数据报首部,OSPF 分组,OSPF 分组首部,类型 1 至类型 5 的 OSPF 分组,24 字节,0,8,16,31,版 本,路 由 器 标 识 符,类 型,分 组 长 度,检 验 和,鉴 别,比特,鉴 别,区 域 标 识 符,鉴 别 类 型,51,2.OSPF 的五种分组类型,类型1，问候(Hello)分组。类型2，数据库描述(Database Description)分组。类型3，链路状态请求(Link State Request)分组。类型4，链路状态更新(Link State Update)分组，用洪泛法对全网更新链路状态。类型5，链路状态确认(Link State Acknowledgment)分组。,52,OSPF的基本操作,确定可达性,53,OSPF 使用的是可靠的洪泛法,t,更新报文,ACK报文,R,R,R,R,t1t2t3t4,54,基本功能：OSPF算法要求每个路由器都有整个网络的拓扑信息每个路由器都要测量所有邻居节点的状态,定期把链路状态信息传播给所有其他路由器,55,链路状态路由选择,基本工作过程发现邻居结点测量到邻居结点的线路开销构造链路-状态报文广播链路-状态报文计算新路由,56,该算法涉及问题:如何保存整个路由器拓扑结构的信息?如何测试与之直接相连的邻居节点状态?测量状态时是否要考虑负载因素?如何进行链路状态信息的分发?,57,发现邻居结点：当某个路由器启动后，它要做的第一件事是要知道它的邻居是谁。这可以通过向其邻居发送问候(hello)报文来实现。路由器通过邻居结点返回的应答报文就可以知道它是谁。测量线路开销：链路状态路由算法要求每个路由器知道它到邻居结点的延迟或延迟的估计值。获得线路延迟的最直接方式就是发送一个要求对方立即响应的特殊的回应(Echo)报文，通过计算来回延迟再除以2，就可以得到一个可靠的延迟估计值。,58,构造链路-状态报文：一旦路由器获取到所有邻居结点的延迟，下一步就是构造链路-状态报文中包含构造该报文的路由器标识以及到每个邻居结点的延迟构造链路-状态报文定期进行当网络出现大的变化时（如线路断开或重新连通、邻居结点故障或恢复等情况）就构造新的链路-状态报文,59,图1：构造链路-状态报文,(a)子网拓扑结构,(b)链路-状态报文,60,广播链路-状态报文：如何可靠地将链路-状态报文广播到网络中的每一个路由器上泛洪式路由算法为了控制重复报文的数量，在每个链路-状态报文中加上一个序号，该序号在每次广播新的链路-状态报文时加1。每个路由器记录它所接收过的链路状态报文中的信息对（源路由器，序号），当路由器接收到一个链路状态报文时，先查看一下该报文是否已收到过。如果路由器已收到过该报文，它就将新接收到的报文的序号与路由器记录的最大序号进行比较。如果前者小于或等于后者，则说明该报文是重复报文，将其丢弃；否则该报文就是新的，应将它扩散到所有的输出线路上（除了接收该报文的线路外）。,61,问题：1）顺序号循环使用，产生冲突；2）路由器崩溃丢失顺序号信息；3）顺序号传送可能出现错误解决：使用32位的顺序号在报文中加上生存时间(age)字段，且每隔1秒钟生存时间字段值减1。当生存时间字段变为0时，所有来自于那个路由器的报文都将被丢弃。这样可保证没有任何报文会无限制地生存下去。改进：路由器接收到链路状态报文后，并不立即将它放入输出队列等待转发，而是首先将它送到一个缓冲区等待一会儿。如果已有来自同一路由器的其它链路-状态报文先行到达，则比较它们的序号。如果序号相等，丢弃任何一个重复报文；否则丢弃老的报文。为了防止路由器之间的线路故障而导致链路-状态报文的丢失，所有的链路状态报文都要进行应答。一旦通信线路空闲，路由器就会循环扫描缓冲区以选择发送一个链路-状态报文或应答报文。,62,每一行对应于一个新到的但未完全处理完毕的链路状态报文该链路状态数据库记录了报文来自何处、报文的序号、生存时间以及数据对应于B的每条输出线路（到A、C和E）各有一个传送标志和应答标志位。传送标志位用于标志链路状态报文必须扩散的线路，应答标志位用于标志必须发送应答报文的线路。,63,计算新路由由于网络上的每个路由器都可以获得所有其它路由器的链路-状态报文，因此每个路由器都可以构造出网络的拓扑结构图。当路由器收到一个链路状态信息时，它便更新它所了解的拓扑图。每次当拓扑有所变化时，路由器可以根据最短路径算法（Dijkstra算法）计算出所有到目的结点的最短路径，并把计算结果填到路由器的表中。这样的过程随着链路-状态报文的更新而周期性地进行。,64,OSPF 的其他特点,OSPF 还规定每隔一段时间，如 30 分钟，要刷新一次数据库中的链路状态。由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF 协议要比距离向量协议 RIP 好得多。OSPF 没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于 100 ms。,