《_45__________因特网的路由选择协议》由会员分享，可在线阅读，更多相关《_45__________因特网的路由选择协议（98页珍藏版）》请在金锄头文库上搜索。
1、q 要实现路由，路由器必须知道要实现路由，路由器必须知道:目的地址目的地址 最佳路由路径最佳路由路径源地址源地址 管理路由信息管理路由信息所有可能的路由路径所有可能的路由路径172.16.1.010.120.2.0什么是路由什么是路由什么是路由什么是路由: :4.5.1 有关路由选择协议的几个基本概念有关路由选择协议的几个基本概念4.5 因特网的路由选择协议因特网的路由选择协议路由协议在网络层工作路由协议在网络层工作routingtableRouting protocolspath selectionRIP, OSPF, BGPIP protocoladdressing conventions
2、datagram formatpacket handling conventionsICMP protocolerror reportingrouter “signaling”Transport layer: TCP, UDPData Link layerPhysical layerNetworklayer理想的路由算法理想的路由算法q算法必须是正确的和完整的。算法必须是正确的和完整的。 q算法在计算上应简单。算法在计算上应简单。 q算算法法应应能能适适应应通通信信量量和和网网络络拓拓扑扑的的变变化化，这就是说，要有自适应性。这就是说，要有自适应性。 q算法应具有稳定性。算法应具有稳定性。 q
3、算法应是公平的。算法应是公平的。 q算法应是最佳的。算法应是最佳的。路由算法分类路由算法分类q 一个实际的路由选择算法，应尽可能接近于理想一个实际的路由选择算法，应尽可能接近于理想的算法，在不同的应用条件下，对前页几个方面的算法，在不同的应用条件下，对前页几个方面也可有不同的侧重。也可有不同的侧重。q 从路由算法能否随网络的通信量或拓扑自适应地从路由算法能否随网络的通信量或拓扑自适应地进行调整变化来划分，分为两大类：进行调整变化来划分，分为两大类：静态路由选择策略静态路由选择策略 (非自适应路由选择非自适应路由选择) 动态路由选择策略动态路由选择策略 (自适应路由选择自适应路由选择)路由算法路
4、由算法静态与动态路由算法静态与动态路由算法q静态路由算法静态路由算法预先计算好路由表，在系统启动时装入路由器，在运行过程中保持不变。不能适应网络拓扑和流量的变化，出现故障时必须人工干预。实现简单，适合于负载稳定、变化不大的环境。q动态路由算法动态路由算法根据当前网络流量和拓扑来选择最佳路径。算法灵活、强壮。某一节点发生故障时，可绕过该节点，平衡负载。算法复杂，实现难度大。各路由器之间定期交换路由信息，增加了网络负担。 静态路由静态路由172.16.2.1SO172.16.1.0B172.16.2.2NetworkA在小型网络中适宜设置静态路由。在小型网络中适宜设置静态路由。BStub Netw
5、ork指定一条可以到达目的网络的路径指定一条可以到达目的网络的路径Router(config)# ip route network mask address | interfacedistance permanent路由器上静态路由的配置路由器上静态路由的配置路由器上静态路由的配置路由器上静态路由的配置network - 目的网络地址目的网络地址mask - 子网掩码子网掩码address - 下一跳地址下一跳地址静态路由的例子静态路由的例子Stub Networkip route 172.16.1.0 255.255.255.0 172.16.2.1172.16.2.1SO172.16.1.
6、0B172.16.2.2NetworkAB分层次的路由选择协议分层次的路由选择协议q 因特网采用的路由选择协议主要是自适应的因特网采用的路由选择协议主要是自适应的(即动态的即动态的)、分布式路由选择协议。分布式路由选择协议。 q方法方法当网络规模很大时，将网络分成一些区域当网络规模很大时，将网络分成一些区域每个区域内的路由器只负责本区域内的分组转发，而每个区域内的路由器只负责本区域内的分组转发，而不管其他区域的情况不管其他区域的情况目的地址不在本区域内的分组全部发给指定的区域路目的地址不在本区域内的分组全部发给指定的区域路由器去处理由器去处理q 特点特点 能较好地适应网络状态的变化，但实现起来
7、较为复能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。杂，开销也比较大。自治系统自治系统(autonomous system, AS) q将整个互联网划分为许多较小的将整个互联网划分为许多较小的自治系统自治系统 (AS)。q一一个个自自治治系系统统是是一一个个互互联联网网，其其最最重重要要的的特特点点就就是是自自治治系系统统内内各各路路由由器器采采用用同同一一个个路路由由选选择择协协议议，一一个个自自治治系系统统有有权权自自主主地地决决定定在在本本系系统统内内应应采采用用何何种种路由选择协议。路由选择协议。 q一一个个自自治治系系统统内内的的所所有有网网络络都都属属于于一一个个行
8、行政政单单位位(例例如如，一一个个公公司司，一一所所大大学学，政政府府的的一一个个部部门门，等等等等)来来管辖管辖。 q一一个个自自治治系系统统的的所所有有路路由由器器在在本本自自治治系系统统内内都都必必须须是是连通连通的。的。 因特网有两大类路由选择协议因特网有两大类路由选择协议 q内内部部网网关关协协议议 IGP (Interior Gateway Protocol) 即即在在一一个个自自治治系系统统内内部部使使用用的的路路由由选选择择协协议议。目目前前这这类类路路由由选选择择协协议议使使用用得得最最多多，如如 RIP 和和 OSPF 协议。协议。q外外部部网网关关协协议议EGP (Ext
9、ernal Gateway Protocol) 若若源源站站和和目目的的站站处处在在不不同同的的自自治治系系统统中中，当当数数据据报报传传到到一一个个自自治治系系统统的的边边界界时时，就就需需要要使使用用一一种种协协议议将将路路由由选选择择信信息息传传递递到到另另一一个个自自治治系系统统中中。这这样样的的协协议议就就是是外外部部网网关关协协议议 EGP。在在外外部部网网关关协议中目前使用最多的是协议中目前使用最多的是 BGP-4。 R1H1H2内部网关协议内部网关协议IGP（例如，（例如，RIP）自治系统自治系统 A自治系统自治系统 B自治系统自治系统 C CIGPIGPIGPIGPIGPIG
10、PIGPIGPIGPIGPIGPIGPEGPEGPEGP内部网关协议内部网关协议IGP（例如，（例如，OSPF）外部网关协议外部网关协议EGP（例如，（例如，BGP-4）IGPR3R2自治系统和内部网关协议、外部网关协议自治系统和内部网关协议、外部网关协议 需注意的两点需注意的两点 q因因特特网网的的早早期期 RFC 文文档档中中未未使使用用“路路由由器器”而而是是使使用用“网网关关”这这一一名名词词。但但是是在在新新的的 RFC 文文档中又使用了档中又使用了“路由器路由器”这一名词。这一名词。qIGP 和和 EGP 是是协协议议类类别别的的名名称称。但但 RFC 在在使使用用 EGP 这这个
11、个名名词词时时出出现现了了一一点点混混乱乱，因因为为最最早早的的一一个个外外部部网网关关协协议议的的协协议议名名字字正正好好也也是是 EGP。因因此此在在遇遇到到名名词词 EGP 时时，应应弄弄清清它它是是指指旧旧的的协协议议 EGP 还是指外部网关协议还是指外部网关协议 EGP 这个类别。这个类别。 因特网的路由选择协议因特网的路由选择协议 q内部网关协议内部网关协议 IGP：具体的协议有多种，：具体的协议有多种，如如 RIP 和和 OSPF 等。等。q外部网关协议外部网关协议 EGP：目前使用的协议就：目前使用的协议就是是 BGP-4。q各路由选择协议使用的两种主要算法：各路由选择协议使用
12、的两种主要算法： 距离矢量路由选择算法距离矢量路由选择算法(RIP采用采用) 链路状态路由选择算法链路状态路由选择算法(OSPF采用采用)(1) 距离矢量路由选择算法距离矢量路由选择算法qDVRDistance Vector Routingq方法方法每隔每隔一段时间，每个节点就向它的所有一段时间，每个节点就向它的所有相邻相邻节节点发送一个点发送一个有关全网的距离列表有关全网的距离列表(即距离矢量即距离矢量)。各节点依据当前相邻节点的情况来各节点依据当前相邻节点的情况来修改更新修改更新自自己的路由表。己的路由表。q距离的计算距离的计算可以为距目的节点的站的可以为距目的节点的站的段数段数(hops
13、)、时间等、时间等距离矢量的路由协议距离矢量的路由协议距离矢量的路由协议距离矢量的路由协议定期将路由表复制给相邻的路由器，并且进行矢量计算、更新路由表C CD DB BA AC CB BA AD DRoutingTableRoutingTableRoutingTableRoutingTableDistance How farVector In which direction各路由器从自己直接相连的网络收集到最原始的源信息A AB BC C10.1.0.010.2.0.010.3.0.010.4.0.0E0S0S0S1S0E0Routing Table10.2.0.010.3.0.0 00S0S
14、1Routing Table10.3.0.0S0010.4.0.0E00Routing Table10.1.0.010.2.0.0 E0S0 00距离矢量距离矢量距离矢量距离矢量源信息的获得源信息的获得源信息的获得源信息的获得路由器从相邻路由器收集到的源信息中选择到达目标地址的最佳路径A AB BC C10.1.0.010.2.0.010.3.0.010.4.0.0E0S0S0S1S0E0Routing Table10.1.0.010.2.0.010.3.0.0Routing Table10.2.0.010.3.0.010.4.0.010.1.0.00011S0S1S1S0Routing Ta
15、ble10.3.0.0S0010.4.0.0E0010.2.0.0S0 1E0S0S0100距离矢量距离矢量距离矢量距离矢量源信息的获得源信息的获得源信息的获得源信息的获得距离矢量距离矢量距离矢量距离矢量源信息的获得源信息的获得源信息的获得源信息的获得路由器继续从相邻路由器收集到的源信息中选择到达目标地址的最佳路径A AB BC C10.1.0.010.2.0.010.3.0.010.4.0.0E0S0S0S1S0E0Routing Table10.1.0.010.2.0.010.3.0.010.4.0.0Routing Table10.2.0.010.3.0.010.4.0.010.1.0.
16、00011S0S1S1S0Routing Table10.3.0.0S0010.4.0.0E0010.2.0.0S010.1.0.0S012E0S0S0S01200一步一步完成的路由表更新过程一步一步完成的路由表更新过程一步一步完成的路由表更新过程一步一步完成的路由表更新过程路由表的更新过程将通过路由器之间一步一步来完成A A更新路由表更新路由表网络结构的网络结构的网络结构的网络结构的改变将导致改变将导致改变将导致改变将导致路由表的路由表的路由表的路由表的更新更新更新更新一步一步完成的路由表更新过程一步一步完成的路由表更新过程一步一步完成的路由表更新过程一步一步完成的路由表更新过程路由表的更新
17、过程将通过路由器之间一步一步来完成A A更新路由表更新路由表在下一个周期后在下一个周期后路由器路由器A发送更新发送更新过的路由表过的路由表网络结构的网络结构的网络结构的网络结构的改变将导致改变将导致改变将导致改变将导致路由表的路由表的路由表的路由表的更新更新更新更新一步一步完成的路由表更新过程一步一步完成的路由表更新过程一步一步完成的路由表更新过程一步一步完成的路由表更新过程路由表的更新过程将通过路由器之间一步一步来完成A AB B更新路由表更新路由表更新路由表更新路由表网络结构的网络结构的网络结构的网络结构的改变将导致改变将导致改变将导致改变将导致路由表的路由表的路由表的路由表的更新更新更新
18、更新在下一个周期后在下一个周期后路由器路由器A发送更新发送更新过的路由表过的路由表DVR的收敛性讨论的收敛性讨论(a)节点启动时节点启动时 (b)A-B的的链路失效链路失效时时图中为各结点到结点图中为各结点到结点A的距离的变化，直至值稳定下来，称为的距离的变化，直至值稳定下来，称为“收敛收敛”X好消息传播得快，坏消息传播得慢好消息传播得快，坏消息传播得慢。经过经过4 4个周期值稳定，收敛个周期值稳定，收敛直至轮番上涨至直至轮番上涨至16()，此时才知此时才知A不可达，收敛不可达，收敛DVRq优点优点实现简单，开销较小实现简单，开销较小q缺点缺点收敛较慢收敛较慢，网络远端的变化只有经过相邻点的多
19、次，网络远端的变化只有经过相邻点的多次传递才能逐渐反映出来传递才能逐渐反映出来好消息传播得快，坏消息传播得慢好消息传播得快，坏消息传播得慢。网络出故障的。网络出故障的传播时间往往需要较长的时间传播时间往往需要较长的时间路由器之间路由器之间交换的路由信息是交换的路由信息是路由器中的路由器中的完整路由完整路由表表，随着网络规模的扩大，随着网络规模的扩大，开销开销也就也就增加增加。一般只用于一般只用于规模不大规模不大的局域网的局域网(2) 链路状态路由选择算法链路状态路由选择算法LSPqLSPLink State Packetq特点特点各结点各结点向全网其它向全网其它节点节点洪泛洪泛发送该节点同发送
20、该节点同相邻相邻节点的节点的链路状态信息链路状态信息q基本思想基本思想通过各个节点之间的通过各个节点之间的洪泛洪泛路由信息交换路由信息交换每个节点可获得每个节点可获得关于关于全网的拓扑信息全网的拓扑信息，得知网中所有，得知网中所有的节点、各节点间的链路连接和各条链路的代价的节点、各节点间的链路连接和各条链路的代价.将这些拓扑信息抽象成一张带权无向图，然后利用将这些拓扑信息抽象成一张带权无向图，然后利用最最短通路路由选择算法短通路路由选择算法计算出计算出到各个目的节点最短通路到各个目的节点最短通路。链路状态协议链路状态协议链路状态协议链路状态协议LSA（link state advertisem
21、ent) 数据包链路状态公告 洪泛传递自己的链路状态信息给其它的路由器SPF运算运算拓扑结构数据拓扑结构数据最佳路由信息最佳路由信息路由表路由表C CA AD DB BLSP使用使用dijkstra算法进行算法进行SPF运算运算LSP 的的步骤步骤q1.了解相邻节点了解相邻节点方法：发送询问分组方法：发送询问分组每个节点启动后，向同它相连的线路上发送一个特殊每个节点启动后，向同它相连的线路上发送一个特殊的询问分组，链路另一端的节点收到该分组后进行响的询问分组，链路另一端的节点收到该分组后进行响应，返回其网络地址。应，返回其网络地址。q2.确定链路代价确定链路代价方法：发送回声分组方法：发送回声
22、分组节点在链路上发送一个特殊的节点在链路上发送一个特殊的ECHO分组分组另一端以最快的速度返回。另一端以最快的速度返回。发送节点将往返时间除以发送节点将往返时间除以2即得到该链路的延迟时间。即得到该链路的延迟时间。可取多次结果的平均值。可取多次结果的平均值。LSP的的步骤（续）步骤（续）q 3. 构造链路状态分组构造链路状态分组链路状态分组包括：源节点的网络地址、分组的序列链路状态分组包括：源节点的网络地址、分组的序列号、寿命、相邻节点的网络地址和去往该节点的链路号、寿命、相邻节点的网络地址和去往该节点的链路代价。代价。(a) 网络拓扑网络拓扑 (b)链路状态分组链路状态分组LSP的的步骤（续
23、）步骤（续）构造该分组的时机构造该分组的时机不能太快，过于增加网络负载；不能太快，过于增加网络负载；不能太慢，不能反映网络拓朴的变化。不能太慢，不能反映网络拓朴的变化。有两种方法有两种方法定期产生链路状态分组，如定期产生链路状态分组，如30秒。秒。在探测到网络连接或链路代价改变之后，才产生。在探测到网络连接或链路代价改变之后，才产生。 q 4. 发送链路状态分组发送链路状态分组采用采用洪泛法洪泛法进行发送，保证网络上所有结点都能收到链进行发送，保证网络上所有结点都能收到链路状态分组。路状态分组。每一结点收到一个链路状态分组后，复制多份，向所有每一结点收到一个链路状态分组后，复制多份，向所有的其
24、他端口发送出去。的其他端口发送出去。LSP的的步骤（续）步骤（续）q5.计算新的路由计算新的路由构造反映网络拓扑的带权图构造反映网络拓扑的带权图使用使用SPF最短通路路由选择算法最短通路路由选择算法(dijkstra)计算路由，然计算路由，然后更新路由表后更新路由表qLSP的优点的优点链路状态数据库更新较快，因而链路状态数据库更新较快，因而收敛快收敛快。能适用于能适用于规模很大的自治系统规模很大的自治系统中中链路状态信息量小链路状态信息量小，可减少路由信息的通信量，可减少路由信息的通信量qLSP的缺点的缺点当网络规模大当网络规模大，链路状态数据库大，链路状态数据库大，需较大的存储空间，计算最需
25、较大的存储空间，计算最佳路由需较长时间。佳路由需较长时间。比距离矢量算法比距离矢量算法复杂复杂4.5.2 内部网关协议内部网关协议 RIP 1. 工作原理工作原理q路由信息协议路由信息协议 RIP 是内部网关协议是内部网关协议 IGP中最中最先得到广泛使用的协议。先得到广泛使用的协议。qRIP 是一种分布式的基于是一种分布式的基于距离向量距离向量的路由选择的路由选择协议。协议。qRIP 协议要求网络中的每一个路由器都要维护协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。从它自己到其他每一个目的网络的距离记录。 RIP - Routing Information Pr
26、otocol“距离距离”的定义的定义 q从一路由器到从一路由器到直接连接直接连接的网络的距离定义为的网络的距离定义为 1。q从从一一个个路路由由器器到到非非直直接接连连接接的的网网络络的的距距离离定定义义为所经过的路由器数加为所经过的路由器数加 1。qRIP 协协议议中中的的“距距离离”也也称称为为“跳跳数数”(hop count)，因为每经过一个路由器，跳数就加，因为每经过一个路由器，跳数就加 1。“距离距离”的定义的定义 qRIP 认认为为一一个个好好的的路路由由就就是是它它通通过过的的路路由由器器的的数目少，即数目少，即“距离短距离短”。qRIP 允许一条路径最多只能包含允许一条路径最多
27、只能包含 15 个路由器。个路由器。q“距距离离”的的最最大大值值为为16 时时即即相相当当于于不不可可达达。可可见见 RIP 只适用于小型互联网。只适用于小型互联网。qRIP 不不能能在在两两个个网网络络之之间间同同时时使使用用多多条条路路由由。RIP 选选择择一一个个具具有有最最少少路路由由器器的的路路由由（即即最最短短路路由由），哪哪怕怕还还存存在在另另一一条条高高速速(低低时时延延)但但路路由器较多的路由。由器较多的路由。 RIP 协议的三个要点协议的三个要点 qQ：和哪些路由器交换信息？：和哪些路由器交换信息？( to Whom) A：仅和相邻路由器交换信息。：仅和相邻路由器交换信息
28、。 qQ：交换什么信息？：交换什么信息？(What) A: 交换的信息是当前本路由器所知道的全部信交换的信息是当前本路由器所知道的全部信 息，即自己的路由表。息，即自己的路由表。 qQ: 在什么时候交换信息？在什么时候交换信息？(When) A：按固定的时间间隔交换路由信息，例如，每：按固定的时间间隔交换路由信息，例如，每 隔隔 30 秒。秒。 路由表的建立路由表的建立 q路路由由器器在在刚刚刚刚开开始始工工作作时时，只只知知道道到到直直接接连连接接的网络的距离（此距离定义为的网络的距离（此距离定义为1）。）。q以以后后，每每一一个个路路由由器器也也只只和和数数目目非非常常有有限限的的相相邻路
29、由器交换并更新路由信息。邻路由器交换并更新路由信息。q经经过过若若干干次次更更新新后后，所所有有的的路路由由器器最最终终都都会会知知道道到到达达本本自自治治系系统统中中任任何何一一个个网网络络的的最最短短距距离离和下一跳路由器的地址。和下一跳路由器的地址。qRIP 协协议议的的收收敛敛(convergence)过过程程较较快快，收收敛敛是是指指在在自自治治系系统统中中所所有有的的结结点点都都得得到到正正确确的的路路由选择信息的过程。由选择信息的过程。 2. RIP中的距离向量算法中的距离向量算法收到相邻路由器（其地址为 X）的一个 RIP 报文：(1) 先修改此 RIP 报文中的所有项目：将“
30、下一跳”字段中的地址都改为 X，并将所有的“距离”字段的值加 1。(2) 对修改后的 RIP 报文中的每一个项目，重复以下步骤： 若项目中的目的网络不在路由表中，则将该项目加到路由表中。 否则 若下一跳字段给出的路由器地址是同样的，则将收到的项目替换原路由表中的项目。 否则 若收到项目中的距离小于路由表中的距离，则进行更新，否则，什么也不做。(3) 若 3 分钟还没有收到相邻路由器的更新路由表，则将此相邻路由器记为不可达的路由器，即将距离置为16（距离为16表示不可达）。(4) 返回。路由器之间交换信息路由器之间交换信息 qRIP协协议议让让互互联联网网中中的的所所有有路路由由器器都都和和自自
31、己己的的相相邻邻路路由由器器不不断断交交换换路路由由信信息息，并并不不断断更更新新其其路路由由表表，使使得得从从每每一一个个路路由由器器到到每每一一个个目目的的网网络的路由都是最短的（即跳数最少）。络的路由都是最短的（即跳数最少）。q虽虽然然所所有有的的路路由由器器最最终终都都拥拥有有了了整整个个自自治治系系统统的的全全局局路路由由信信息息，但但由由于于每每一一个个路路由由器器的的位位置置不同，它们的路由表当然也应当是不同的。不同，它们的路由表当然也应当是不同的。 1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 一开始，各路由
32、表只有到相邻路由器的信息一开始，各路由表只有到相邻路由器的信息网 3网 2网 4网 6网 5网 1“4”表示表示“从本路由从本路由器到网器到网 4”“1”表示表示“距离是距离是 1”“ ”表示表示“直接交直接交付付”更新后1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 A 说：说：“我到网我到网 1 的距离是的距离是 1。”因此因此 B 现在也可以到网现在也可以到网 1，距离
33、是距离是 2，经过，经过 A。”1 2 A2 2 A3 1 4 1 6 2 C1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 更新后A 说：说：“我到网我到网 2 的距离是的距离是 1。”因此因此 B 现在也可以到网现在也可以到网 2，距离是距离是 2，经过，经过 A。”1 2 A2 2 A3 1 4 1 6 2 CA 说：说：“我到网我到网 3 的距离是的距离是 1。”但但
34、 B 没有必要绕道经过路由器没有必要绕道经过路由器 A再到达网再到达网 3，因此这一项目不变。，因此这一项目不变。1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 更新后1 2 A2 2 A3 1 4 1 6 2 CC 说：说：“我到网我到网 4 的距离是的距离是 1。”但但 B 没有必要绕道经过路由器没有必要绕道经过路由器 C再到达网再到达网 4，因此这一项目不变。，因此这一
35、项目不变。1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 更新后1 2 A2 2 A3 1 4 1 6 2 C1 2 A2 2 A3 1 4 1 6 2 CC 说：说：“我到网我到网 6 的距离是的距离是 1。”因此因此 B 现在也可以到网现在也可以到网 6，距离是距离是 2，经过，经过 C。”1 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1
36、 4 1 6 1 1 1 5 1 路由器路由器 B 收到相邻路由器收到相邻路由器 A 和和 C 的路由表的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 更新后最终所有的路由器的路由表都更新了最终所有的路由器的路由表都更新了FEDCBA1 1 2 1 3 1 4 2 B5 2 E6 3 B1 1 2 2 A3 2 A4 3 A5 1 6 2 F1 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网 41 2 A2 1 3 2 A4 3 A5 1 6 2 F1 2 A2 2
37、 A3 1 4 1 5 3 C6 2 C路由表更新过程解析路由表更新过程解析路由表更新过程举例路由表更新过程举例RIP 协议的位置协议的位置 qRIP 协协议议使使用用运运输输层层的的用用户户数数据据报报 UDP进进行行传传送送（使用（使用 UDP 的端口的端口 520）。）。q因因此此 RIP 协协议议的的位位置置应应当当在在应应用用层层。但但转转发发 IP 数据报的过程是在网络层完成的。数据报的过程是在网络层完成的。 qRIP-1协协议议不不支支持持子子网网和和VLSM变变长长子子网网掩掩码码，它只支持它只支持A、B、C类网络即类网络即IP地址分类的协议地址分类的协议。qRIP-2协协议议
38、支支持持明明文文认认证证和和 MD5 密密文文认认证证，还还支支持子网和持子网和VLSM变长子网掩码。变长子网掩码。3. RIP2 协议的报文格式协议的报文格式 4 字节字节RIP 报文报文路由信息路由信息（20 字节字节/路由）路由）可重复出现可重复出现最多最多 25 个个IP 数据报数据报路由标记路由标记网络地址网络地址地址族标识符地址族标识符距离距离 (1-16) IP 首部首部UDP 首部首部首部首部路由部分路由部分必为必为 0 0版本版本命令命令 4 字节字节子网掩码子网掩码下一跳路由器地址下一跳路由器地址UDP 用户数据报用户数据报RIP2 的报文由首部和路由部分组成的报文由首部和
39、路由部分组成qRIP2 报报文文中中的的路路由由部部分分由由若若干干个个路路由由信信息息组组成成。每每个个路路由由信信息息需需要要用用 20 个个字字节节。地地址址族族标标识识符符（又又称称为为地地址址类类别别）字字段段用用来来标标志志所所使使用的地址协议。用的地址协议。q路路由由标标记记填填入入自自治治系系统统的的号号码码，这这是是考考虑虑使使RIP 有有可可能能收收到到本本自自治治系系统统以以外外的的路路由由选选择择信信息息。再再后后面面指指出出某某个个网网络络地地址址、该该网网络络的的子子网网掩码掩码、下一跳路由器地址下一跳路由器地址以及到此网络的以及到此网络的距离距离。 RIP 协议的
40、优缺点协议的优缺点 qRIP 存存在在的的一一个个问问题题是是当当网网络络出出现现故故障障时时，要要经经过过比比较较长长的的时时间间才才能能将将此此信信息息传传送送到到所所有有的的路由器。路由器。q RIP 协议最大的协议最大的优点优点就是就是实现简单，开销较小。实现简单，开销较小。qRIP 限限制制了了网网络络的的规规模模，它它能能使使用用的的最最大大距距离离为为 15（16 表示不可达）。表示不可达）。q路路由由器器之之间间交交换换的的路路由由信信息息是是路路由由器器中中的的完完整整路路由由表表，因因而而随随着着网网络络规规模模的的扩扩大大，开开销销也也就就增加。增加。 R2R1网 1网
41、3网 2正正常常情情况况1 1 1 2 R1R1 说：说：“我到网我到网 1 的距离是的距离是 1，是直接交付。，是直接交付。”“1”表示表示“从本路由器到从本路由器到网网 1”“1”表示表示“距离是距离是 1”“ ”表示表示“直接交付直接交付”R2R1网 1网 3网 2正正常常情情况况1 1 1 2 R1R2 说：说：“我到网我到网 1 的距离是的距离是 2，是经过，是经过 R1。”“1”表示表示“从本路由器到从本路由器到网网 1”“2”表示表示“距离是距离是 2”“R1”表示表示经过经过 R1R2R1网 1网 3网 2R2R1网 1网 3网 2网网 1 1出了故障出了故障正正常常情情况况1
42、 16 1 1 1 2 R11 2 R1R1 说：说：“我到网我到网 1 的距离是的距离是 16 （表示无法到达），（表示无法到达）， 是直接交付。是直接交付。” 但但 R2 在收到在收到 R1 的更新报文之前，还发送原来的报的更新报文之前，还发送原来的报文，因为这时文，因为这时 R2 并不知道并不知道 R1 出了故障。出了故障。R2R1网 1网 3网 2R2R1网 1网 3网 2网网 1 1出了故障出了故障正正常常情情况况1 1 1 16 1 2 R11 2 R1 R1 收收到到 R2 的的更更新新报报文文后后，误误认认为为可可经经过过 R2 到到达达网网1，于于是是更更新新自自己己的的路路
43、由由表表，说说：“我我到到网网 1 的的距距离离是是 3，下一跳经过下一跳经过 R2”。然后将此更新信息发送给。然后将此更新信息发送给 R2。1 3 R2R2R1网 1网 3网 2R2R1网 1网 3网 2网网 1 1出了故障出了故障正正常常情情况况1 1 1 16 1 2 R11 2 R1 R2 以以后后又又更更新新自自己己的的路路由由表表为为“1, 4, R1”，表明表明 “我到网我到网 1 距离是距离是 4，下一跳经过，下一跳经过 R1”。 1 3 R21 4 R1R2R1网 1网 3网 2R2R1网 1网 3网 2网网 1 1出了故障出了故障正正常常情情况况1 1 1 16 1 3 R
44、21 5 R21 16 R21 2 R11 2 R11 4 R11 16 R1 这这样样不不断断更更新新下下去去，直直到到 R1 和和 R2 到到网网 1 的的距距离离都都增增大到大到 16 时，时，R1 和和 R2 才知道网才知道网1是不可达的。是不可达的。 这这就就是是好好消消息息传传播播得得快快，而而坏坏消消息息传传播播得得慢慢。网网络络出出故故障障的的传传播播时时间间往往往往需需要要较较长长的的时时间间( (例例如如数数分分钟钟) )。这这是是 RIP RIP 的一个主要缺点。的一个主要缺点。 RIP“路由环路路由环路”问题的解决方法问题的解决方法分析以上问题产生原因，为防止错误的路由
45、信息传播开，分析以上问题产生原因，为防止错误的路由信息传播开，RIP采用以下措施：采用以下措施： (1) 水平分割（水平分割（Split Horizon）：）：从一个方向学来的路由信息，不能再放入发从一个方向学来的路由信息，不能再放入发回那个方向的路由更新包并且又发回那个方向。回那个方向的路由更新包并且又发回那个方向。(2) 路由下毒（路由下毒（Route Poisoning）：）：当路由器发现自己直连的网段出现故障时，当路由器发现自己直连的网段出现故障时，首先给自己首先给自己“下毒下毒”，标记该路由为，标记该路由为16，即不可达，然后使用路由更新，即不可达，然后使用路由更新包给自己的邻居包给
46、自己的邻居“下毒下毒”，即向自己的邻居路由器通告该路由已失效。，即向自己的邻居路由器通告该路由已失效。(3) 毒性逆转（毒性逆转（Poison Reverse）：）：路由器被路由器被“下毒下毒”之后，会继续向自己的之后，会继续向自己的邻居邻居“下毒下毒”，同时，为了保证所有的邻居都被，同时，为了保证所有的邻居都被下毒下毒，还会向，还会向毒源毒源的方向反向的方向反向下毒下毒。(4) 触发更新（触发更新（Triggered Update）：）：当路由器发现某网段出现故障时，会立当路由器发现某网段出现故障时，会立刻发出路由更新包来通知邻居，而不用等到刻发出路由更新包来通知邻居，而不用等到30秒以后下
47、一次发送路由更秒以后下一次发送路由更新包的时间。新包的时间。(5) 抑制定时器（抑制定时器（Holddown Timers）：）：当路由器学习到某个网段出现故障，当路由器学习到某个网段出现故障，并标记该路由变为并标记该路由变为“可能可能down状态状态”之后，还要保持该状态一段时间。之后，还要保持该状态一段时间。在保持时间里，如果再收到该网段的更新时，若更新具有相等或更差的在保持时间里，如果再收到该网段的更新时，若更新具有相等或更差的度量值，路由器会不听度量值，路由器会不听.4.5.3 内部网关协议内部网关协议 OSPFOSPF - Open Shortest Path First OSPF
48、协议的基本特点协议的基本特点:q“开放开放”表明表明 OSPF 协议不是受某一家厂商控制，而协议不是受某一家厂商控制，而是公开发表的。是公开发表的。q“最短路径优先最短路径优先”是因为使用了是因为使用了 Dijkstra 提出的最提出的最短路径算法短路径算法SPFqOSPF 只是一个协议的名字，它并不表示其他的路由只是一个协议的名字，它并不表示其他的路由选择协议不是选择协议不是“最短路径优先最短路径优先”。q是分布式的是分布式的链路状态协议链路状态协议。 OSPF 协议的三个要点协议的三个要点q Q：和哪些路由器交换信息？：和哪些路由器交换信息？(to Whom) A：用：用洪泛洪泛法向本自治
49、系统中法向本自治系统中所有所有路由器发送信息路由器发送信息q Q：交换什么信息？：交换什么信息？(What) A: 发送的信息是与本路由器发送的信息是与本路由器相邻的相邻的所有路由器的所有路由器的 链路状态，链路状态，即说明本路由器都和哪些路由器相即说明本路由器都和哪些路由器相 邻，以及该链路的邻，以及该链路的“度量度量”(metric)。q Q: 在什么时候交换信息？在什么时候交换信息？(When) A：更新发送时，即只有当链路状态发生：更新发送时，即只有当链路状态发生变化变化时，时， 路由器才用洪泛法向所有路由器发送此信息。路由器才用洪泛法向所有路由器发送此信息。链路状态数据库链路状态数据
50、库 (Link-state database) q 由于各路由器之间频繁地交换链路状态信息，因由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据此所有的路由器最终都能建立一个链路状态数据库。库。q 这个数据库实际上就是全网的拓扑结构图，它在这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的全网范围内是一致的（这称为链路状态数据库的同步）。同步）。q OSPF 的链路状态数据库能较快地进行更新，使的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。各个路由器能及时更新其路由表。OSPF 的更新的更新过程收敛得快是其
51、重要优点过程收敛得快是其重要优点。 OSPF 的区域的区域 (area) q为了使为了使 OSPF 能够用于规模很大的网络，能够用于规模很大的网络， OSPF 将一个自治系统再划分为若干个更小的范围，叫将一个自治系统再划分为若干个更小的范围，叫作作区域区域。q每一个区域都有一个每一个区域都有一个 32 bit 的区域标识符（用点的区域标识符（用点分十进制表示）。分十进制表示）。q区域也不能太大，在一个区域内的路由器最好不区域也不能太大，在一个区域内的路由器最好不超过超过 200 个。个。 OSPF 划分为两种不同的区域划分为两种不同的区域 自治系统 AS区域 0.0.0.1区域 0.0.0.3
52、主干区域 0.0.0.0至其他自治系统至其他自治系统R9R7R6R5R4R3R2R1网 8网 6网 3网 2网 1网 7区域 0.0.0.2网 4网 5R8OSPF 使用使用层次结构的区域层次结构的区域划分。在上层的区域叫作划分。在上层的区域叫作主干区域主干区域(backbone area)。 主干区域的标识符规定为主干区域的标识符规定为0.0.0.0。主干区域的作用是用来连通其他在。主干区域的作用是用来连通其他在下层的区域下层的区域OSPF 路由协议为什么要分区？路由协议为什么要分区？ q洪泛消息只在本区域中发送洪泛消息只在本区域中发送。在每个区域里，路由器不关心其它。在每个区域里，路由器不
53、关心其它区域的链路改变，而只关心本区域的链路改变。一个区域的网络区域的链路改变，而只关心本区域的链路改变。一个区域的网络拓扑变化，只会引起本区域的链路信息的更新和网络收敛操作。拓扑变化，只会引起本区域的链路信息的更新和网络收敛操作。通过划分区域，网络故障和链路变化的影响范围被缩小，整个网通过划分区域，网络故障和链路变化的影响范围被缩小，整个网络不再频繁地进行收敛操作。络不再频繁地进行收敛操作。q当网络中自治系统非常大时当网络中自治系统非常大时，洪泛网络拓扑数据库的内容就很多，洪泛网络拓扑数据库的内容就很多，所以所以如果不分区域如果不分区域的话，的话，一方面容易造成数据库溢出一方面容易造成数据库
54、溢出，另一方面另一方面当网络中某一当网络中某一链路状态发生变化时链路状态发生变化时，会引起整个网络中每个节点会引起整个网络中每个节点都重新计算一遍自己的路由表，既浪费资源与时间，又会影响路都重新计算一遍自己的路由表，既浪费资源与时间，又会影响路由协议的性能由协议的性能（如聚合速度、稳定性、灵活性等）。因此，需要（如聚合速度、稳定性、灵活性等）。因此，需要把自治系统划分为多个区域，每个区域内部维持本区域一张唯一把自治系统划分为多个区域，每个区域内部维持本区域一张唯一的拓扑结构图，且各区域根据自己的拓扑图各自计算路由。的拓扑结构图，且各区域根据自己的拓扑图各自计算路由。主干路由器主干路由器自治系统
55、 AS区域 0.0.0.1区域 0.0.0.3主干区域 0.0.0.0至其他自治系统至其他自治系统R9R7R6R5R4R3R2R1网 8网 6网 3网 2网 1网 7区域 0.0.0.2网 4网 5R8区域内部路由器、区域边界路由器、区域内部路由器、区域边界路由器、主干路由器主干路由器、AS边界路由器边界路由器(R6)主干路由器主干路由器：R3、R4、R5、R6、R7区域边界路由器区域边界路由器 自治系统 AS区域 0.0.0.1区域 0.0.0.3主干区域 0.0.0.0至其他自治系统至其他自治系统R9R7R6R5R4R3R2R1网 8网 6网 3网 2网 1网 7区域 0.0.0.2网 4
56、网 5R8区域内部路由器、区域内部路由器、区域边界路由器区域边界路由器、主干路由器、主干路由器、AS边界路由器边界路由器(R6)区域边界路由器区域边界路由器：R3、R4、R7OSPF 路由协议分区域后的工作原理路由协议分区域后的工作原理q在区域与区域的边界处有区域边界路由器，在区域与区域的边界处有区域边界路由器，区域边界路由器负责学习两区域边界路由器负责学习两个区域的路由。个区域的路由。当发送目的地是其它区域的数据报时，区域内路由器先当发送目的地是其它区域的数据报时，区域内路由器先路由给区域边界路由器，然后由区域边界路由器将数据报路由到其它区路由给区域边界路由器，然后由区域边界路由器将数据报路
57、由到其它区域，而域，而区域内部的路由器不需要学习其它区域的链路结构数据区域内部的路由器不需要学习其它区域的链路结构数据。这样，。这样，相对而言，路由器所维护的路由表体积显著缩小，路由操作效率提高。相对而言，路由器所维护的路由表体积显著缩小，路由操作效率提高。q所有区域之间的网络链路结构情况互不可见，所有区域之间的网络链路结构情况互不可见，区域边界路由器会将其相区域边界路由器会将其相连接区域的内部链路结构数据总结后连接区域的内部链路结构数据总结后通过通过Summary Link广播至区域广播至区域0，也即广播至所有其它区域的边界路由器，也即广播至所有其它区域的边界路由器，这样与区域这样与区域0相
58、连的区域边界相连的区域边界路由器上就有区域路由器上就有区域0及其它所有区域的链路结构总结信息及其它所有区域的链路结构总结信息，通过这些信，通过这些信息，这些息，这些区域边界路由器区域边界路由器能够能够计算出计算出至相应目的地的至相应目的地的路由路由，并，并将这些路将这些路由信息广播至与其相连接的区域内由信息广播至与其相连接的区域内，以便让该区域内部的路由器找到与，以便让该区域内部的路由器找到与区域外部通信的最佳路由。区域外部通信的最佳路由。q当网络中的某条链路状态发生变化时，此链路所在区域中的每个路由器当网络中的某条链路状态发生变化时，此链路所在区域中的每个路由器重新计算本区域路由表，重新计算
59、本区域路由表，而区域边界路由器把区域的内部路由总结后在而区域边界路由器把区域的内部路由总结后在区域间扩散。而其它区域中路由器只需修改其路由表中的相应条目而无区域间扩散。而其它区域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表须重新计算整个路由表，节省了计算路由表的时间。，节省了计算路由表的时间。OSPF 直接用直接用 IP 数据报传送数据报传送 qOSPF 不用不用 UDP 而是而是直接用直接用 IP 数据报传送数据报传送(IP信包中的高层协议信包中的高层协议号号89)，可见，可见 OSPF 的位置在网络层。的位置在网络层。qOSPF 构成的数据报很短。这样做可减少路由信息的通信
60、量。构成的数据报很短。这样做可减少路由信息的通信量。qOSPF由两个互相关联的主要部分组成：由两个互相关联的主要部分组成：“呼叫呼叫”(Hello)协议和协议和“可靠泛洪可靠泛洪”机制。机制。“呼叫呼叫”协议检测邻居并维护邻接关系，协议检测邻居并维护邻接关系，“可靠泛洪可靠泛洪”算法可以确保区域中的所有的算法可以确保区域中的所有的OSPF路由器始终具有一路由器始终具有一致的链路状态数据库。致的链路状态数据库。q每个路由器都维护一个用于跟踪网络每个路由器都维护一个用于跟踪网络链路状态的数据库链路状态的数据库，然后各，然后各路由器的路由选择就是基于链路状态、通过路由器的路由选择就是基于链路状态、通
61、过Dijkastra算法建立起算法建立起来最短路径树来最短路径树，用该树跟踪系统中，用该树跟踪系统中到每个目标的最短路径到每个目标的最短路径。最后。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。与再通过计算域间路由、自治系统外部路由确定完整的路由表。与此同时，此同时，OSPF动态监视网络状态，动态监视网络状态，一旦链路状态发生变化则迅速一旦链路状态发生变化则迅速洪泛扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由洪泛扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由表。表。OSPF 分组格式及封装分组格式及封装 IP 数据报IP数据报首部OSPF 分组OSPF 分组首部类型
62、1 至类型 5 的 OSPF 分组24 字节081631版 本路 由 器 标 识 符类 型分 组 长 度检 验 和鉴 别比特比特鉴 别区 域 标 识 符鉴 别 类 型OSPF 工作过程工作过程1、构造发送、构造发送Hello包、接收包、接收Hello包，得知本地链路状态；包，得知本地链路状态；2、通过一系列的分组交换，全网各路由器达到链路状态数、通过一系列的分组交换，全网各路由器达到链路状态数据库的同步；或链路状态发生变化时用洪泛法向全网更据库的同步；或链路状态发生变化时用洪泛法向全网更新链路状态；新链路状态；3、各路由器根据收集到的链路状态建立链路状态数据库；、各路由器根据收集到的链路状态建
63、立链路状态数据库；4、启动、启动SPF算法，以自己为源点计算算法，以自己为源点计算SPF树；树；5、建立到达所有信宿的路由表（目的网络、下一跳路由器、建立到达所有信宿的路由表（目的网络、下一跳路由器、经由端口、代价）。经由端口、代价）。（1）构造）构造LSP/LSAAEDCBFLSPLSPNet 2Net 1Net 3Net 4Net 5Net 6522331125a0a1A的的LSPNet 1a00Net 2a10Link State PacketLink State Advertisement可靠的洪泛法OSPF 使用的是可靠的洪泛法使用的是可靠的洪泛法 t更新报文ACK报文RRRRt1t
64、2t3t4（2）构造拓扑数据库）构造拓扑数据库LSDBAEDCBF全网具有相同全网具有相同的的L-S逻辑图。逻辑图。AEDCBF（3）各自重新计算）各自重新计算SPF树树223311525AEDCBF（4）生成各自的路由表）生成各自的路由表a0a1路路由由表表路路由由表表路路由由表表路路由由表表路路由由表表22Net 2Net 1Net 3Net 4Net 5Net 6A的路由表的路由表Net 1a00Net 2a10Net 3B2Net 4B4Net 5B5Net 6C5113OSPF 的五种分组类型的五种分组类型 如果所有的路由器启动后通过如果所有的路由器启动后通过Hello分组得知相邻路
65、由器及其链路代价，分组得知相邻路由器及其链路代价，然后组成自己的本地链路状态信包对全网进行洪泛广播，那么各路由器将全部然后组成自己的本地链路状态信包对全网进行洪泛广播，那么各路由器将全部信息综合后就可得出链路状态数据库。但这样做开销太大，实际上，信息综合后就可得出链路状态数据库。但这样做开销太大，实际上，OSPF采采用下法：用下法： q类型类型1，问候，问候(Hello)分组。分组。(相邻路由器每隔相邻路由器每隔10秒交换一次秒交换一次，得知和何路由器，得知和何路由器 相邻以及其间链路的代价，若相邻以及其间链路的代价，若40秒未收到，则标为不可达秒未收到，则标为不可达)q类型类型2，数据库描述
66、，数据库描述(Database Description)分组。分组。(和相邻路由器交换和相邻路由器交换本数据本数据 库的库的摘要摘要信息：有哪些路由器的链路状态信息、及相应序号信息：有哪些路由器的链路状态信息、及相应序号)q类型类型3，链路状态请求，链路状态请求(Link State Request)分组。分组。(向对方请求向对方请求发送自己所发送自己所 缺少的某些链路状态项目缺少的某些链路状态项目的的详细详细信息信息)q类型类型4，链路状态更新，链路状态更新(Link State Update)分组。分组。(对链路状态请求的应答对链路状态请求的应答； 也也可用作可用作链路状态发生变化时链路状
67、态发生变化时用用洪泛洪泛法向全网更新链路状态法向全网更新链路状态)q类型类型5，链路状态确认，链路状态确认(Link State Acknowledgment)分组。分组。 (可靠洪泛法可靠洪泛法: 在在 收到更新收到更新分组分组后后要发送要发送确认确认分组分组)OSPF的基本操作的基本操作 问候问候数据库描述数据库描述数据库描述数据库描述链路状态请求链路状态更新链路状态确认确定可达性达到数据库的同步新情况下的同步OSPF 的其他特点的其他特点 qOSPF对不同的链路可根据不同服务类型的业务设置成不对不同的链路可根据不同服务类型的业务设置成不同的代价，因而可计算出不同的路由，因此对应多个不同同
68、的代价，因而可计算出不同的路由，因此对应多个不同类型业务可以有多个路由表。类型业务可以有多个路由表。q允许到同一个目的网络有多条相同代价的路径。可以将通允许到同一个目的网络有多条相同代价的路径。可以将通信量分配给这几条路径，这叫作多路径间的负载平衡。信量分配给这几条路径，这叫作多路径间的负载平衡。qOSPF支持可变长子网掩码支持可变长子网掩码VLSM和无分类编址和无分类编址CIDR。以。以上上OSPF的特性，的特性，RIP都没有。都没有。q所有在所有在 OSPF 路由器之间交换的分组都具有鉴别的功能。路由器之间交换的分组都具有鉴别的功能。q每一个链路状态信包都带上一个每一个链路状态信包都带上一
69、个 32 bit 的序号，序号越大的序号，序号越大状态就越新，若洪泛中收到相同序号的链路状态包则丢弃。状态就越新，若洪泛中收到相同序号的链路状态包则丢弃。OSPF 的其他特点的其他特点 qOSPF 还规定每隔一段时间，如还规定每隔一段时间，如 30 分钟，要刷分钟，要刷新一次数据库中的链路状态。新一次数据库中的链路状态。 q由于一个路由器的链路状态只涉及到与相邻路由由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，接关系。因此当互联网规模很大时，OSPF 协议协议要比距离向量协议要比距离
70、向量协议 RIP 好得多。好得多。 qOSPF 没有没有“坏消息传播得慢坏消息传播得慢”的问题，据统计，的问题，据统计，其响应网络变化的时间小于其响应网络变化的时间小于 100 ms。 指定路由器指定路由器 (designated router) *qOSPF的设计实现，还要涉及到的设计实现，还要涉及到指定路由器指定路由器、备份备份指定路由器指定路由器的选举、协议包的接收、发送、泛洪的选举、协议包的接收、发送、泛洪机制、路由表计算等一系列问题。机制、路由表计算等一系列问题。qOSPF协议对多点接入的局域网协议对多点接入的局域网 (如多个路由器接如多个路由器接在一个以太网上在一个以太网上) 要采
71、用要采用指定路由器指定路由器，由它代表局由它代表局域网上所有的链路向连接到该网络上的各路由器域网上所有的链路向连接到该网络上的各路由器发送状态信息。发送状态信息。q多点接入的局域网采用了指定路由器的方法，使多点接入的局域网采用了指定路由器的方法，使广播的信息量大大减少。广播的信息量大大减少。OSPF 支持三种网络的连接支持三种网络的连接 *(1) 两个路由器之间的点对点连接两个路由器之间的点对点连接(2) 具有广播功能的局域网具有广播功能的局域网(3) 无广播功能的广域网无广播功能的广域网局域网 ABCABED广域网局域网 L1局域网 L2(a) 网络拓扑(b) 有向图L1L2W1W3W2DB
72、CAIHGFE12422233341312167788810W4W64W56522544333288131212107616ABHGFECDI广域网 W5广域网 W3广域网 W2广域网 W6广域网 W1广域网 W4*有向图L1L2W1W3W2DBCAIHGFE12422233341312167788810W4W64W565L1L2W1W3W2DBAIGFE4331216788W4W6W5654从上图生成下图的以路由器F为根的最短路径树 *4.5.4 外部网关协议外部网关协议 BGPqBGP 是不同自治系统的路由器之间交换路由是不同自治系统的路由器之间交换路由信息的协议。信息的协议。 qBGP
73、的较新版本是的较新版本是 1995 年发表的年发表的 BGP-4（BGP 的第的第 4 个版本）。个版本）。 qBGP采用采用类似类似DVA的算法的算法 - 路径向量路径向量(path vector)路由选择算法路由选择算法 ；q可以将可以将 BGP-4 简写为简写为 BGP。BGP 使用的环境与前面协议不同使用的环境与前面协议不同 q前提前提因特网的因特网的规模规模太大，使得自治系统之间路由选择非常太大，使得自治系统之间路由选择非常困难。困难。 对于自治系统之间的路由选择，要寻找对于自治系统之间的路由选择，要寻找最佳最佳路由是很路由是很不现实的。不现实的。 自治系统之间的路由选择必须考虑有关
74、自治系统之间的路由选择必须考虑有关策略策略。q目标目标边界网关协议边界网关协议 BGP 只能是力求寻找一条能够到达目只能是力求寻找一条能够到达目的网络且的网络且比较好的比较好的路由（不能兜圈子），而并非要寻路由（不能兜圈子），而并非要寻找一条找一条最佳路由最佳路由。BGP 发言人发言人 q每一个自治系统的管理员要选择至少一个路由每一个自治系统的管理员要选择至少一个路由器作为该自治系统的器作为该自治系统的“BGP 发言人发言人” 。q一般说来，两个一般说来，两个 BGP 发言人都是通过一个共发言人都是通过一个共享网络连接在一起的，而享网络连接在一起的，而 BGP 发言人往往就发言人往往就是是 B
75、GP 边界路由器边界路由器，但也可以不是，但也可以不是 BGP 边边界路由器。界路由器。 BGP 交换路由信息交换路由信息q一个一个 BGP 发言人与其他自治系统中的发言人与其他自治系统中的 BGP 发言人要交发言人要交换路由信息，就要先换路由信息，就要先建立建立 TCP 连接连接(端口号端口号179)，然后在，然后在此连接上交换此连接上交换 BGP 报文以建立报文以建立 BGP 会话会话(session)，利用，利用 BGP 会话交换网络可达性信息会话交换网络可达性信息(内容为内容为: 到达某个网络需到达某个网络需要经过哪一系列要经过哪一系列AS)。q使用使用 TCP 连接能提供可靠的服务，
76、也简化了路由选择协连接能提供可靠的服务，也简化了路由选择协议。议。q使用使用 TCP 连接交换路由信息的两个连接交换路由信息的两个 BGP 发言人，彼此发言人，彼此成为对方的成为对方的邻站邻站或对等站。或对等站。BGP 发言人和自治系统发言人和自治系统 AS 的关系的关系 BGP 发言人BGP发言人BGP 发言人BGP 发言人BGP发言人AS1AS3AS2AS5AS4BGP 发言人互相交换网络可达性信息发言人互相交换网络可达性信息q每个每个 AS 的的 BGP 发言人向相邻的发言人向相邻的 BGP 发言人通告对方经由发言人通告对方经由本本AS到本自治系统中的各目的网络的可达性，相邻的到本自治系
77、统中的各目的网络的可达性，相邻的 BGP发言人将到这些目的网络的路径上加上自己所在的发言人将到这些目的网络的路径上加上自己所在的 AS，又又向其相邻的其它向其相邻的其它 BGP 发言人通告，发言人通告，.，这样，这样，BGP 发言发言人之间就互相交换这些到达各个网络的可达性信息：到达某人之间就互相交换这些到达各个网络的可达性信息：到达某个网络需要经过哪一系列个网络需要经过哪一系列 AS 的路径信息。的路径信息。qBGP 发言人互相交发言人互相交 换网络可达性的信息换网络可达性的信息 后，各后，各 BGP 发言人发言人 就可找出到达各自治就可找出到达各自治 系统的比较好的路由。系统的比较好的路由
78、。 AS1AS6AS2AS3AS5AS4AS7AS8BGP 发言人交换路径向量发言人交换路径向量 主干网（AS1）地区 ISP（AS2）地区 ISP（AS3）本地 ISP（AS4）N1， N2本地 ISP（AS5）N3， N4本地 ISP（AS6）N5本地 ISP（AS7）N6， N7 自治系统自治系统 AS2 的的 BGP 发言人通知主干网的发言人通知主干网的 BGP 发言人：发言人：“要到达网络要到达网络 N1, N2, N3 和和 N4 可经过可经过 AS2。” BGP 发言人交换路径向量发言人交换路径向量 主干网（AS1）地区 ISP（AS2）地区 ISP（AS3）本地 ISP（AS4
79、）N1， N2本地 ISP（AS5）N3， N4本地 ISP（AS6）N5本地 ISP（AS7）N6， N7主干网还可发出通知：“要到达网络 N5, N6 和 N7 可沿路径（AS1, AS3）。” BGP 协议的特点协议的特点qBGP 协议交换路由信息的结点数量级是协议交换路由信息的结点数量级是自治自治系统数的量级系统数的量级，这要比这些自治系统中的网络，这要比这些自治系统中的网络数少很多。数少很多。q每一个自治系统中每一个自治系统中 BGP 发言人（或边界路由发言人（或边界路由器）的数目是很少的。这样就使得自治系统之器）的数目是很少的。这样就使得自治系统之间的路由选择不致过分复杂。间的路由
80、选择不致过分复杂。 BGP 协议的特点协议的特点qBGP 支持支持 CIDR，因此，因此 BGP 的路由表的路由表也就应当也就应当包括包括目的网络前缀目的网络前缀、下一跳路由器下一跳路由器，以及，以及到达到达该目的网络所要经过的各个自治系统序列该目的网络所要经过的各个自治系统序列。q在在BGP 刚刚运行时刚刚运行时，BGP 的邻站是交换整个的的邻站是交换整个的 BGP 路由表。路由表。但但以后以后只需要在只需要在发生变化时更新发生变化时更新有变化的部分有变化的部分。这样做对节省网络带宽和减少。这样做对节省网络带宽和减少路由器的处理开销方面都有好处。路由器的处理开销方面都有好处。 qBGP 采用
81、采用 TCP 报文传送。报文传送。 BGP 发言人间交换报文的类型发言人间交换报文的类型* OPEN报文报文 (与相邻与相邻BGP发言人建立关系，使通信初始化发言人建立关系，使通信初始化) KEEPALIVE报文报文 (周期性每隔周期性每隔30秒一次证实邻站的连通性秒一次证实邻站的连通性)UPDATE报文报文 (通告某一路由信息，及列出撤销路由通告某一路由信息，及列出撤销路由)-为核心交换报为核心交换报文文NOTIFICATION报文报文 (发送检测到的差错发送检测到的差错)ROUTE-REFRESH报文报文 (请求对等端重新通告请求对等端重新通告)BGP 报文的格式报文的格式* 4 字节类 型长 度标 记BGP 报文的数据部分可变长度首部长度19 字节该 BGP-4 报文封装在 TCP 报文段中传输。RIP、OSPF、BGP 路由协议比较路由协议比较
