第七章-网络互连-之-路由协议课件

大家好大家好路由协议（RIP，OSPF和BGP）“互联网络”（internet）是路由器连接而成的多个网络的组合体。当数据报从一个源端传送到一个目标端时，可能需要通过很多个路由器才到达与目标网络连接的路由器。路由器的作用是从一个网络中接收数据包（packet，分组），然后将它传送给另一个网络。一个路由器通常与几个网络连接，这样，当它收到一个数据包时，应该将数据包转发给哪个网络呢？路由器是按最佳化原则进行判定：哪个可用的路径是最佳路径？人们用metric来表示通过某个网络时所指定的“成本”（cost，代价）。一个特定路由的总metric，等于包含了该路由的多个网络的metric之和。路由器根据最短（最小）的metric来选择路由。Metric电信专业n.米制的,量度的计算机专业度量，尺度；公制分配给每个网络的metric取决于协议的类型。某些简单的协议，如“路由信息协议”（RIP），将每个网络同等处理，即通过每个网络的cost是一样的，或者说都是一个“跳数”（onehopcount）。所以如果一个数据包通过10个网络才到达目标端，其总cost就是10个“跳数”。其他协议，如“开放最短路径优先协议”（OSPF），则允许管理员根据所需的服务类型，为通过一个网络指定cost。通过某个网络的路由可以具有不同的cost（metric）。例如，如果所需的服务类型是“最大吞吐量”（throughput），一条卫星链路就比一条光纤链路具有更低的metric。另一方面，如果所需的服务类型是“最小延迟”，一条光纤链路就比一条卫星链路具有更低的metric。OSPF允许每个路由器根据所需的服务类型拥有几个路由表。其他协议定义metric的方法则完全不同。在“边缘网关协议”（BGP）中，评定的标准是可以由管理员设置的所谓“策略”（policy）。“策略”定义了应该选择的是哪个路径。不管metric是如何确定的，路由器在准备转发数据包时，都必须使用路由表。路由表应为数据包规定最佳路径。不过，路由表可以是静态的，也可以是动态的。“静态路由表”是那种不经常变化的路由表。“动态路由表”是那种当互联网络中的某处出现变化时能自动更新的路由表。今天，互联网络需要的是动态路由表。这种路由表要求互联网络出现变化时即被尽快更新。例如，当某个路由关闭（down）时，需要进行更新；而当一个更好的路由建立后，也需要进行更新。各种路由协议都是为了动态路由表的需要而制定的。一个路由协议是一组规则和程序的组合，用于使互联网络中的路由器们相互告知有关的变化情况。它使路由器们共享它们所掌握的互联网络或相邻路由器的情况。这种信息的共享使得武汉的某个路由器可以知道上海的网络出现故障了。路由协议还包含了将从其他路由器接收的信息综合起来的处理程序。什么是路由协议内部和外部路由今天，一个互联网络可能很大，以致一个路由协议无法完成为所有路由器更新路由表的任务。为此，需要将一个互联网络分为若干“自治系统”（autonomoussystems，AS）。一个“自治系统”是指由同一个管理员管理的一组网络和路由器。自治系统内部的路由称为“内部路由”，自治系统之间的路由称为“外部路由”。每个自治系统都可以选择一个内部路由协议来处理该自治系统内部的路由。但是，自治系统之间的路由通常只能使用一个外部路由协议来处理。路由器R1，R2和R3使用一个内部路由协议和一个外部路由协议。其他路由器只使用内部路由协议。阴影部分表示使用内部路由协议的各自治系统。细实线表示使用内部路由协议的各路由器间的通信连接。粗实线表示使用外部路由协议的各路由器间的通信连接。现在使用的内部和外部路由协议很多。本章只介绍最常用的几种。下面讨论两个内部路由协议（RIP和OSPF）和一个外部路由协议（BGP）。RIP和OSPF可用于自治系统内部路由表的更新。BGP可用于为连接自治系统的各个路由器进行路由表更新。动态路由动态路由路由算法路由算法：根据网络拓扑计算路由的方法。：根据网络拓扑计算路由的方法。或路由表的生成方法。或路由表的生成方法。两种路由算法：两种路由算法：矢量矢量-距离（距离（V-D V-D）算法）算法 如如RIP（路由信息）（路由信息）链路状态（链路状态（L-SL-S）算法）算法 如如OSPF（开放最短路径优先）（开放最短路径优先）矢量-距离（V-D）算法路由表中列出所有已知的路由启动时路由器对每个与自己直连的网络生成一个表项每个路由器周期地向直接相连的其他路由器发送自己的路由表每个路由器根据其他路由器发来的路由更新消息，相应修改自己的路由表周期性传送的信息包括：（目的网络地址(矢量)V，到达该网络的距离D）这就是矢量-距离算法名称的来源链路状态（链路状态（L-S）算法算法不需要传送路由信息，只需：1）检测所有相邻相邻路由器的状态(相邻：通过同一网络连接的两个路由器相邻：通过同一网络连接的两个路由器)-周期地向相邻路由器发送“Hello”报文，询问其工作状态2）周期地向其他路由器通告自己了解到的链接状态信息-链路类型、链路标识、通告该链路的路由器地址每个路由器根据其他路由器发来的链路状态报文，相应地更新自己的网络拓扑结构数据库最终每个路由器都具有同样的网络拓扑最终每个路由器都具有同样的网络拓扑 结构数据库（即共享一个公共的连接状态数据库），称为收敛结构数据库（即共享一个公共的连接状态数据库），称为收敛路由器使用Dijkstra最短路径算法对网络拓扑图求最短路径计算到达其他网络的最短路径最后用计算出来的最短路径更新自己的路由表D-V和和L-S算法的比较算法的比较D-V通过与邻居的信息交换通过与邻居的信息交换获得网络拓扑知识获得网络拓扑知识路由计算是增加路由器路由计算是增加路由器之间的站点数（之间的站点数（hops）定期刷新路由：收敛慢定期刷新路由：收敛慢向相邻站点传送路由表向相邻站点传送路由表的副本的副本L-S全网获得共同的全局性全网获得共同的全局性网络拓扑知识（网络拓扑知识（L-S图）图）计算到达其他站点的最计算到达其他站点的最短路径（短路径（SPF准则）准则）触发刷新：收敛快触发刷新：收敛快向其他站点发送链路状向其他站点发送链路状态的动态变化态的动态变化RIP（路由信息协议）路由信息协议是一个用于自治系统内部的“内部路由协议”。它是一种非常简单的协议，基于“距离向量路由”技术。距离向量路由在“距离向量路由”中，每个路由器都定期地和其相邻的路由器们共享它们对整个互联网络掌握的情况。理解这一算法的工作原理有三个关键，如下：1、共享整个自治系统的情况每个路由器都和其相邻的路由器们共享它们对整个互联网络掌握的情况。开始时，一个路由器掌握的情况可能是很少的，便是它知道多少并不重要；它发送它所知道的所有情况。2、只和相邻的路由器共享每个路由器只向相邻的路由器发送自己掌握的情况。它通过自己的所有端口发送自己知道的所有情况。3、定期地共享每个路由器都定期地（如每隔30秒）向相邻的路由器发送自己掌握的情况。术语“距离向量”起源于定期信息发送，一个报文包含有成对的列表（V，D），这里的V表示目的地（叫做向量），D是到达那个目的地的距离。注意距离向量是以第一人称报告路由的，即我们把一个路由器送来的通告看成它在说：“我可以到达距离为D的目的地V”。路由表每个路由器都保持一张路由表，表中为路由器知道的每一个目标网络设置一条记录。该记录由目标网络的IP地址、到达目标的最短距离（用“跳数”表示）和下一跳（为了到达最后目标应将数据包转送给它的下一个路由器）三个部分组成。跳数是指数据包到达最后目标所进入的网络数目。路由表中还含有诸如该记录最后更新时间等其他信息。示例如下：距离跳数下一跳其他信息163.5.0.07172.6.23.4197.5.13.05176.3.6.17189.45.0.04200.5.1.6115.0.0.06131.4.7.19RIP更新算法路由表根据收到的RIP响应报文（message）进行更新。以下是RIP所使用的更新算法：接收：一个RIP响应报文1为每个advertised（被发布）的目标增加一个跳数值；2对每个advertised的目标重复以下步骤：IF（目标不在路由表中）将advertised的信息添加到路由表中。ELSEIF（下一跳字段相同）用advertised的记录替换表中的记录ELSEIF（advertised跳数小于表中的跳数）把它加到路由表中(更新）ELSE什么都不做3返回动态路由举例动态路由举例路由信息协议路由信息协议RIP报文由序偶（报文由序偶（IP网络地址，到达该网络的距离）组成网络地址，到达该网络的距离）组成用步跳数表示到达目的网络的距离；用步跳数表示到达目的网络的距离；1-16，1表示直连，表示直连，16表示不可达表示不可达（即只要步跳数大于等于（即只要步跳数大于等于16就认为路径为无穷远）就认为路径为无穷远）路由器收到路由更新报文后应更新自己的路由表路由器收到路由更新报文后应更新自己的路由表 例如，例如，R2从从R1收到的路由更新报文为收到的路由更新报文为(net1,1)、(net2,2)、(net3,1)，则，则R2的路由表更新为的路由表更新为(net1,R1,2)、(net2,R1,3)、(net3,R1,2)RIP协议的时钟协议的时钟路由刷新周期路由刷新周期每个路由器每隔每个路由器每隔30秒刷新和广播自己的路由表。秒刷新和广播自己的路由表。路由失效计时路由失效计时一条路由表项未被更新的时间达一条路由表项未被更新的时间达3分钟（分钟（180秒），秒），则视其为失效信息，将本路由表项的距离置为无穷则视其为失效信息，将本路由表项的距离置为无穷大（毒性逆转）。大（毒性逆转）。路由保持计时路由保持计时发现一条路由失效信息后，立即启动保持计时，发现一条路由失效信息后，立即启动保持计时，60秒之后删除此条目。秒之后删除此条目。RIP的缺点的缺点算法不能明确的检测出循环路由，会产生慢收敛和无限计数问题算法不能明确的检测出循环路由，会产生慢收敛和无限计数问题步跳数不能反映链路的真实开销，例如步跳数为步跳数不能反映链路的真实开销，例如步跳数为4的的LAN路径不一路径不一定比步跳数为定比步跳数为1的的64K DDN链路差。链路差。网络1R1R2R31.R1与网络与网络1直接相连。直接相连。2.通过周期性路由广播，通过周期性路由广播，R1、R2、R3都建立了到网络都建立了到网络1的路由的路由(a)3.某时刻，某时刻，R1到网络到网络1的路由消失的路由消失(b)4.但是但是R2对对R1的路由通告引起了选路的循环的路由通告引起了选路的循环:更新报文会在更新报文会在R1，R2来回传输直到距离值到达来回传输直到距离值到达RIP规定的上限。规定的上限。网络1R1R2R3(a)(b)R1直接与网络1相连，因此在路由表中具有一个到网络1的路由，跳数为0，在它广播后，R2获得到网络1的路由，跳数为0+1=1，最后R3则通过R2的广播得到到网络1的路由，跳数为1+1=2，同时，R1也会收到R2的广播，但是由于在R1中到网络1的跳数为0，比R2的小，因此不会更新。如果网络1到R1的连接故障，则R1把到网络1的跳数设为16，并广播，使其它路由器更新。但是，由于所有路由器都会周期性广播路由信息，因而可能会出现这种情况：在R1广播跳数16之前，先收到了来自R2的广播，计算到网络1的跳数为1+1=2，比16小，因此在还没有广播之前已经被更新了，等到下一个广播周期时，R2的更新为2+1=3。到下一轮广播，R1又是收到R2的广播跳数变为3+1=4，而后又广播给R2，使R2到网络1的跳数更新为4+1=5，如此，不断增加，要经过一个较长的时间（大于14*30秒）之后，才会发现网络1从这里是不可达的，而这段时间内到网络1的流量仍被引导到这个不可能的方向。这就是慢收敛问题(坏消息传得慢)网络1R1R2R3网络1R1R2R3 1 1ACB40.0.0.0 down到达信宿到达信宿40.0.0.0的路由变化的路由变化路径环（路径环（Routing Loop）问题）问题这条错误的路由信息在这条错误的路由信息在C与与B之间不断复制和修改，之间不断复制和修改，并在网络中传播（殃及并在网络中传播（殃及A），形成路径传播的环路。），形成路径传播的环路。1 1ACB40.0.0.0 down到达信宿到达信宿40.0.0.0的路由变化的路由变化严重后果：计数至无穷大严重后果：计数至无穷大 1 1ACB40.0.0.0 down到达信宿到达信宿40.0.0.0的路由变化（定义的路由变化（定义Hop最大值为最大值为16）解决办法：定义距离的最大值解决办法：定义距离的最大值收敛！收敛！解决解决RIP存在的问题的几种方法存在的问题的几种方法v视野分离（水平分割）视野分离（水平分割）Split-Horizon从一个接口收到的路由信息不会再通过该接口送回去从一个接口收到的路由信息不会再通过该接口送回去v毒性逆转毒性逆转 Poison Reverse 从一个接口收到的路由信息可以再通过该接口送回去，但距离为从一个接口收到的路由信息可以再通过该接口送回去，但距离为16v触发更新触发更新 Trigged updates 路由发生变化时，不必等到路由发生变化时，不必等到30秒，可立即将更新报文广播出去秒，可立即将更新报文广播出去v抑制更新抑制更新 Hold-Down timers 收到某网络不可达的信息后，在一段时间内（收到某网络不可达的信息后，在一段时间内（60秒）忽略任何关于秒）忽略任何关于该网络的路由信息该网络的路由信息水平分割方法的思路水平分割方法的思路 1 1ACB40.0.0.0 down分析路径环产生的原因分析路径环产生的原因B向向C提供了一条过时的、错误的路由信息。提供了一条过时的、错误的路由信息。能否避免事件发生？能否避免事件发生？B必须经由必须经由C方可到达网络方可到达网络40.0.0.0，B不可能向不可能向C提供任何有提供任何有价值的路由信息。价值的路由信息。修改修改B对对C提供的路由，禁止提供的路由，禁止B向向C提供关于此信宿的路由信息。提供关于此信宿的路由信息。水平分割法水平分割法（Split Horizons）1 1ACB40.0.0.0 down收敛！收敛！到达信宿到达信宿40.0.0.0的路由变化的路由变化水平分割法利用的是路由报文发送的选择性；一个路由器必须识别不同的水平分割法利用的是路由报文发送的选择性；一个路由器必须识别不同的端口。如果一个路由器已经从某个端口处接收到了路由更新信息，那么这端口。如果一个路由器已经从某个端口处接收到了路由更新信息，那么这同一个更新信息就不能通过此端口再发送回去。如果一个端口已经发送信同一个更新信息就不能通过此端口再发送回去。如果一个端口已经发送信息以帮助某个路由器进行更新，这种更新的信息不得回送；它是已知的，息以帮助某个路由器进行更新，这种更新的信息不得回送；它是已知的，所以是不需要的。所以是不需要的。水平分裂不能解决所有的问题水平分裂不能解决所有的问题l水平分裂虽然广泛使用，但有时候会失败。l如右图。n开始时，A和B到D的距离都为2，C到D的距离为1。n假设CD线路断了，使用水平分裂，A和B都告诉C，它们不能到达D，同时C自己也发现直达D的线路断了，于是C很快认定D不可达了。n但是，A认为B有一条通向D长度为2的路径，通过B经过3个结点可到达D。类似，B也这样认为。于是两个结点每交换一次信息，到达D的距离就增加1，直至加大无穷。1 1ACB40.0.0.0 down此此法法是是水水平平分分割割法法的的一一个个变变种种。在在本本办办法法中中，路路由由器器收收到到的的信信息息被被用用于于更更新新路路由由表表，然然后后转转发发到到所所有有端端口口。但但是是，从从某某个个端端口口传传来来的的路路由由表表记记录录如如果果通通过过同同一一个个端端口口出出去去，它它的的跳跳数数值值被设为被设为16。反向抑制法反向抑制法 (毒性逆转毒性逆转Poison Reverse）1 1ACB40.0.0.0 down当当C发现网络发现网络40.0.0.0发生故障时，不等下一刷新周期发生故障时，不等下一刷新周期到来，立刻更改路由为到来，立刻更改路由为“信宿不可达信宿不可达”引起全网的连锁反映，迅速刷新引起全网的连锁反映，迅速刷新触发刷新法触发刷新法网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达距离向量算法小结距离向量算法小结路径选择采用最短路径准则，计算路径选择采用最短路径准则，计算D信宿信宿(距离，下站距离，下站)；每个站点只知道自己和邻居的局部信息，在自己的刷新每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法；周期到来时，根据邻居的路由变化重新启动算法；算法的收敛速度慢（特别是对网络崩溃）造成全网信息算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；的不一致，导致产生路径环，使计数至无穷大；当路径环产生时，定义距离的最大值可防止算法进入死当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题；循环，解决计数至无穷大问题；各种加速收敛方法的目的在于避免路径环的形成，但不各种加速收敛方法的目的在于避免路径环的形成，但不能从根本上杜绝这一现象的发生；能从根本上杜绝这一现象的发生；在具体的路由协议中，各种加速收敛方法往往综合使用。在具体的路由协议中，各种加速收敛方法往往综合使用。开放最短路径优先（开放最短路径优先（OSPF）协议OSPF协议的基本概念协议的基本概念Open Shortest Path First采用链接状态（采用链接状态（L-S）算法算法由由IETF工作小组研制工作小组研制1990年成为标准（年成为标准（RFC1247）改进改进RIP协议的问题协议的问题计数至无穷大计数至无穷大收敛速度慢收敛速度慢开放最短路径优先（开放最短路径优先（OSPF）协议：使用SPF算法，基于链路状态。(ShortestPathFirst)提供路由服务类型：如可要求低延迟或高吞吐量，路由时不仅依据路由目的，还要依据服务类型要求，OSPF将均分负载给各个路径提供网络的“域”划分能力，一个域对外部是透明的，因而可独立管理，这就提供了灵活的网络扩展能力，易于规模化OSPF规定路由器之间的信息交换需要有授权，提高安全性。RIP中任意路由都可广播路由信息，易被利用。支持指向特定主机、特定子网的路由，当然还有对网络的路由，以满足不同需要。支持子网支持CIDR支持虚链路。.最短路径优先最短路径优先(ShortestPathFirst)算法：该算法利用网络拓扑结构（基于链路状态），作如下抽象：把网络中的每个路由器看成一个节点,若两个路由器之间存在直接的连接,就认为它们之间存在一条边这样整个网络拓扑就可抽象为一个只含有节点和边的图参与SPF算法的路由器执行如下两个任务以获得网络拓扑结构：周期性地测试与相邻路由器的连接状态周期性地把连接状态广播给其他路由器每个路由器在获得整个网络的拓扑结构后，就可以各自独立地使用Dijkstra最短路径算法来计算从本路由到其他路由的最短路。AEDCB212113Dijkatra最短路径算法最短路径算法F3552Dijkatra算法计算结果算法计算结果AEDCB212113源点源点A到所有结点的最短路径到所有结点的最短路径F3552DFEABC11212L-S图图SPF树树每个路由器周期性地收集和发送信息每个路由器周期性地收集和发送信息主动测试其到所有邻居的链接状态（度量值）主动测试其到所有邻居的链接状态（度量值）向所有的路由器发送（广播）自己拥有的状态信息向所有的路由器发送（广播）自己拥有的状态信息得到一个全网的、动态的逻辑链路状态（得到一个全网的、动态的逻辑链路状态（L-S）图图每个路由器刷新自己的路由表每个路由器刷新自己的路由表当当L-S变化时，用最短路径优先变化时，用最短路径优先(SPF)算法重新计算本地路由算法重新计算本地路由DCAB链路状态算法的基本概念链路状态算法的基本概念_路路由由表表SPF算法算法拓扑数据库拓扑数据库（L-S图）图）SPF树树L-S包包OSPF划分编号区域（划分编号区域（Area）国家主干国家主干Area1Area0Area2AreaN地区主干地区主干主干路由器主干路由器域边界路由器域边界路由器域内路由器域内路由器.域内路由器域内路由器只拥有本域的路由信息；只拥有本域的路由信息；具有相同的具有相同的L-S图，采用相同的图，采用相同的SPF算法；算法；采用扩散方式广播自己获得的网络知识采用扩散方式广播自己获得的网络知识（邻居和开销）；（邻居和开销）；根据扩散的信息修改根据扩散的信息修改L-S图，计算到域内图，计算到域内其他路由器的最短路径；其他路由器的最短路径；根据计算机结果维护各自的路由表。根据计算机结果维护各自的路由表。域边界路由器域边界路由器具有域内路由器的功能；具有域内路由器的功能；拥有相邻域的拥有相邻域的L-S信息，并计算到达相邻域的信息，并计算到达相邻域的最短路径；最短路径；域间的分组交换都通过其进行路径选择和数据域间的分组交换都通过其进行路径选择和数据交换。交换。例如：例如：本域的路由器通过域边界路由器把分组送往主干本域的路由器通过域边界路由器把分组送往主干网，经主干网送达目的域边界路由器，再由其通网，经主干网送达目的域边界路由器，再由其通过域内路由送往目的主机。过域内路由送往目的主机。主干路由器主干路由器拥有主干网的拥有主干网的L-S信息，计算到其他主干信息，计算到其他主干路由器的最短路径；路由器的最短路径；从与之相连的下级域边界路由器获取该从与之相连的下级域边界路由器获取该域的路由信息，计算其到每个域的最短域的路由信息，计算其到每个域的最短路径；路径；将主干到每个域的最短路径信息回传给将主干到每个域的最短路径信息回传给域边界路由器。域边界路由器。OSPF报文格式:每个OSPF都有一个如下固定的首部:OSPF直接使用IP，而不用UDP或TCP。OSPFHello报文运行OSPF的机器周期性地向相邻连接的机器发送Hello报文以测试其可达性。报文格式：OSPF数据库描述报文格式:OSPF链接状态请求报文格式:OSPF链接状态更新报文格式:BGP边缘网关协议 BGP(Border Gateway Protocol)是自治系统间的路由协议，适用于大的网际网。