路由选择协议教学讲义

1、第十章 路由选择协议10-1 基本概念度量（Metric） 就是给通过网络所指派的代价。 一个特定路由的总度量等于组成该路由的所有网络的度量之和。 给每一个网络指派的度量取决于协议的类型。路由选择协议 路由选择协议是一些规则和过程的组合。使得在互联网中的各路由器能够彼此互相通知这些变化，使得路由器能够共享它们知道的互联网的情况或邻站的情况。2流行的路由选择协议流行的路由选择协议内部的外部的RIPOSPFBGP3内部和外部路由选择每一个自治系统可以选择一种内部路由选择协议处理自治系统内部的路由选择，但是，处理自治系统之间的路由选择通常只能使用一种路由选择协议。内部路由外部路由在一个自治系统内部的

2、路由选择在自治系统之间的路由选择内部路由AS1AS2自治系统：是在一个单一的管理机构管辖下的一组网络和路由器。4自治系统R1R2R3R4Autonomous systemAutonomous systemAutonomous systemAutonomous system510-2 路由选择信息协议（RIP）RIP 是一个内部路由选择协议，它使用在一个自治系统内部。 它是基于距离向量路由选择的非常简单的协议。 它使用 Bellman-Ford 算法 计算路由表。 RIP在熟知端口520使用UDP的服务。6距离向量路由选择在距离向量路由选择中，每一个路由器周期性地与其邻站共享有关整个互联网的信息

3、。要点：共享有关整个自治系统的信息。 在开始时，一个路由器的信息可能很少，但是，它知道多少是不重要的，它将它所知道的发送出去。仅与邻站共享。 每一个路由器仅向其邻站发送它的信息。它将其拥有的信息通过它的所有接口发送出去。按固定时间间隔共享。 每一个路由器按照固定的时间间隔将其信息发送给它的邻站。7一个距离向量路由表DestinationHop CountNext HopOther Information163.5.0.07172.6.23.4197.5.13.05176.3.6.17189.45.0.04200.5.1.6115.0.0.06131.4.7.19到达目的网络的最短距离（以跳数计

4、）8RIP 更新算法在收到RIP响应报文时，路由表就进行更新。对每一个被通知的目的网络的跳数加1。对每一个被通知的目的网络，重复以下步骤：If (目的网络不在路由表中)将通知的信息加到路由表中。ElseIf (下一跳 字段是同样的)将路由表中的项目替换为通知的项目。Else If (通知的跳数小于路由表中的跳数)将它加到路由表中。 Else 什么也不做。Return9更新路由表的例子Net24 Net38 Net64 Net83 Net95从C来的RIP报文Net25 Net39 Net65 Net84 Net96增加以后从C来的RIP报文Net17A Net22C Net68F Net84E

5、 Net94F 旧路由表Updating algorithmNet17A Net25C Net39C Net65C Net84E Net94F 新路由表10对路由表进行初始化Net 14Net 78Net 23Net 08Net 66Net 92Net 5514 1 - 55 1 -14 1 - 23 1 - 78 1 -78 1 - 92 1 -ABCDEF08 1 - 23 1 -08 1 - 66 1 -55 1 - 66 1 -当路由器加到网络上时，它要用其配置文件将路由表进行初始化。这个表中只有直接相连的网络。11前一个图中的路由表的最后状态Net 14Net 78Net 23Net

6、 08Net 66Net 92Net 55ABCDEF08 2 E 14 1 - 23 1 -55 2 B 66 3 E 78 1 - 92 2 F08 3 A 14 1 - 23 2 A 55 1 - 66 2 C 78 2 A 92 3 A08 1 - 14 3 E 23 2 E 55 2 C 66 1 - 78 3 E 92 4 E14 1 - 55 1 -14 1 - 23 1 - 78 1 -08 1 - 66 1 -12RIP 的报文格式网络地址全0命令版本保留系列全0全0距离Repeated13对各字段的说明： 命令：是一个8比特字段。说明了报文的类型：请求（1）或响应（2）。

7、版本：是一个8比特字段。定义版本。 系列：是一个8比特字段。定义所使用的协议系列。对于TCP/IP这个值是2。 地址：定义目的网络的地址。RIP已分配了14个字节给这个字段，可用于任何协议。但是现在IP只使用4字节，其余部分应填入0。 距离：是一个32比特字段。定义从发通知的路由器到目的网络的跳数。注意：报文中的一部分对每一个网络都是重复的，将这部分称为项目。14请求报文当路由器刚刚接到网络上，或路由器有一些超时的项目，它就发送请求报文。网络地址全0命令：1版本保留系列全0全0全0Repeateda.对某个项目的请求全0全0命令:1版本保留系列全0全0全0Repeatedb.对所有项目的请求1

8、5响应报文 响应可以是询问的（solicited）或非询问的。 询问的响应仅在回答请求时才发送出去。 非询问的响应则是定期地发送，如每隔30秒，并包括整个路由表中所有的信息。下图的RIP响应报文传送了关于三个网络的信息。16响应报文举例命令:2版本保留141.12.0.0全0系列:2全0全05181.2.0.0全0系列:2全0全0297.0.0.0全0系列:2全0全04141.12.0.0 5181.2.0.0 297.0.0.0 4概念性的报文17RIP中的计时器计时器无用信息收集120 秒截止期180 秒定期25-35 秒控制报文的发送管理路由的有效性通知某个路由出了故障18RIP存在的一

9、些问题Problems缓慢收敛在互联网上某处发生的变化传播到互联网上的其他部分的速率是很慢的。不稳定性运行RIP的互联网可能变为不稳定的。当发生这种情况时，分则可能在回路中从一个路由器到另一个路由器。19缓慢收敛Net 1Net 2Net n+10 seconds15 secondsn15 secondsTotal hop count should be less than 16解决RIP的这个缺点的方法是限制跳数为 15. 这样可以防止分组无休止的在网络中兜圈子，从而阻塞了互联网。因此，数值16被认为是无穷大。20不稳定性Net 1Net 2Net 3Net11-Routing tableN

10、et12ARouting tableNet116-Net13BNet116BNet14ANet116AABI can reach net1 by a route with length 2She can reach net1 ! Great !Hop count changed !将跳数限制为15能够改进稳定性，但不能解决所有的问题。21解决稳定性的一些方法已经提出了一些方法来提高稳定性，但是，没有一种方法是100%有效。触发更新: 当网络中有变化，路由器就立即发送其新的路由表。分离范围: 阻止出现选路环路。毒性逆转: 宣布不可达的路由器。22触发更新若网络中没有变化，则按通常的30秒间隔发送

11、更新信息。但若有变化，路由器则立即发送其新的路由表。每一个路由器在收到有变化的更新信息时就立即发出新的信息，这比平均的15秒要少得多。它不能解决所有的路由选择问题。如路由器出故障的问题。Triggered update23分离范围Net 1Net 2Net 3ABNet21Net32Net11RIP messagesNet12Net21Net31RIP messages如果路由器从一个接口已经收到了路由更新信息，那么这个同样的更新信息一定不能再通过这个接口回送过去。如果一个接口通过了给一个路由器更新的信息，那么这个更新信息一定不能再回送回去。24毒性逆转Net 1Net 2Net 3ABNet

12、21Net32RIP messagesNet116Net216Net316Net11RIP messagesNet216Net31Net116Net21Net316Net12路由器收到的更新信息通过所有的接口发送出去。已经从一个接口来的一个路由表项目在通过同样的接口发送出去时，就要将其度量置为16。25RIP版本2网络地址子网掩码命令版本保留系列路由标记下一跳地址距离RepeatedRIP版本2没有增大每一个项目的报文长度，而是将版本1中对TCP/IP协议填入0的那些字段改为一些新的字段。26练习题:一路由器具有如下的路由表：net1 4 Bnet2 2 Cnet3 1 Fnet4 5 G若该

13、路由器从路由器C收到下面的RIP报文，路由表中的内容将会是怎样的？net1 2net2 1net3 3net4 72710-3 OSPFOSPF Open Shortest Path First 也是在一个自治系统内使用的内部路由选择协议。 一些特殊的路由器，叫做自治系统边界路由器，负责将其他自治系统的信息传送到本系统中。 OSPF 分组被封装成IP 数据报。28区域 是包含在自治系统中的一些网络、主机和路由器的集合。自治系统又可划分为若干个不同的区域。在区域的所有网络必须是互相连接的。 在一个区域内的路由器使用洪泛法传送路由选择信息。 区域边界路由器 将有关本区域的信息概括起来发送给其他区域

14、。 在自治系统中有一个特殊区域叫做主干，在自治系统中的所有区域必须连接到主干上。 如果由于某些问题，在主干和区域之间的连通性被破坏了，则管理员必须创建路由器间的虚链路，以保持作为一级区域的主干的各种功能的连续性。Area29自治系统中的区域区域边界路由器Autonomous systemArea 1区域边界路由器Area 2Area 0 (主干)主干路由器主干路由器到其他的 ASAS 边界路由器30链路状态路由选择在链路状态路由选择协议中，每一个路由器与在该区域内的每一个路由器共享其邻站的信息。理解关键：共享关于邻站的信息。 每一个路由器向本区域内的每一个其他路由器发送其邻站的状态。与每一个其

15、他路由器共享。 每一个路由器向本区域内的每一个其他路由器发送其邻站的状态。 发送的方法是洪泛法（ flooding）。 最终，每一个路由器（没有例外）都会收到同样信息的一个副本。只要有了变化就共享。 仅当有了变化时每一个路由器才共享其邻站的信息。这使得互联网上的通信量比距离向量路由选择所需的通信量要小。31链路的类型链路的类型残桩链路过渡链路点对点链路虚拟链路两个路由器直接连接连接有若干个路由器的网络只连接到一个路由器的网络当路由器之间的链路断开时创建的32（一）点对点链路点对点链路直接连接两个路由器，而中间没有任何其他的主机或路由器。没有必要给这种类型的链路指派一个网络地址。每一个路由器只有

16、一个邻站在链路的另一端。33（二）过渡链路EthernetABCDE过渡链路ABCDE 不实际的表示ABCDE实际的表示指定路由器 一方面，现在每一个路由器只有一个邻站，即指定路由器（网络），另一方面，这个指定路由器（即网络）有5个邻站。 是一种连接有若干个路由器的网络。数据可以从任何一个路由器进入网络，并从任何一个路由器离开网络。34（三）残桩链路 残桩链路是只连接到一个路由器的网络。 数据分组通过这个单一路由器进入网络，而离开网络也是通过这个路由器。EthernetA残桩链路A表示法指定路由器35链路状态数据库 链路状态数据库是一个区域内的互联网拓扑的表格表示。 它给出了每一个路由器与其邻

17、站的包括度量在内的关系。 在同一个区域内的每一个路由器具有同样的链路状态数据库。BA/6C/2E/1AB/6D/2CB/2F/2G/5DA/2E/2EB/1D/2F/4FC/2E/4G/1GC/5F/1ADBCGEF622214251Network36Dijkstra 算法从本地结点（路由器）开始，本地结点即树的根。将代价0指派给这个结点，并使它成为第一个永久结点。对最后一个永久结点的每一个相邻结点进行检查。给每一个结点指派一个累计代价，并使它成为试验的。在试验结点的清单中：寻找具有最小累计代价的结点，并使它成为永久的。若一个结点从多于一个方向可达，选择具有最短累计代价的方向。重复步骤3至5，

18、直到每一个结点成为永久的。37一个实例ABCDEFN3N5EthernetEthernetEthernetN2N1N4T-1 lineT-3 lineToken ringFDDI上图是一个具有7个网络和6个路由器的小互联网。38上图的图形表示N5N2N3N1N4ABCDEF238857442529539最短路径计算N5N2N3N1N4ABCDEFProblem:Calculate the shortest paths from A40Step 1AStep:Start with A0Node A is the root of the shortest paths tree.41Step 2N1

19、ADStep:Make A permanent, add its neighbors058ANow we have two tentative nodes, N1 and D.42N1Step 3N1BCDStep:Make N1 permanent, add its neighborsA0585543Step 4N1N1BCDStep:Make C permanent, add its neighborsA05855CN2744Step 5N1BDEStep:Make B permanent, add its neighborsA05855N27C9B45Step 6N2N1DEStep:M

20、ake N2 permanentA085CN27B5B9546Step 7N2N3N1DEStep:Make D permanent, add its neighborsA0857595CBBD1047Step 8N2N3N1N4EStep:Make E permanent, add its neighborsA085759510CDB11E1414 1048Step 9N2N3N1N4FStep:Make N3 permanent, add its neighborsA085759510CDB11EN31049Step 10N5N2N3N1N4FStep:Make F permanent,

21、add its neighborsA085759510CDB11E10F1550Step 11Step:Make N4 permanentN5N2N3N1N4FA085759510CDB11E10F15N451Step 12Step:Make N5 permanentN5N2N3N1N4FA085759510CDB11E10F15N4N5Now weve calculated all the shortest paths from A to other routers52路由器A的链路状态路由表NetworkCostNext RouterOther InformationN15 N27CN31

22、0DN411BN515D区域中到达每一个网络的代价53另一个例子ABCF62214233HDEG272(2, A)(4, B)(9, B)(6, E)(5, E)(8, F)(10, H)54链路状态通知 为了共享关于邻站的信息，每一个路由器要发布链路状态通知 (LSA)。 LSA 宣布路由器链路的状态。链路状态通知路由器链路网络链路概括链路到网络概括链路到 AS边界外部链路55（一）路由器链路虚拟至过渡网络点对点至残桩网络向4条链路发通知的路由器 路由器链路定义一个真路由器的链路。 真路由器使用路由器链路通知来宣布关于它的所有链路的信息，以及在链路的另一端情况（邻站）。56 网络链路定义网络

23、的链路。 指定路由器代表一个过渡网络并发布这种类型的LSA分组。 这个分组宣布连接到这个网络上的所有路由器的存在。（二）网络链路指定路由器具有5条链路的网络指定路由器向各链路发通知57（三）概括链路到网络概括链路到网络Area 0区域边界路由器在这个区域进行洪泛Area 1区域边界路由器在这个区域进行洪泛Area 2N1概括链路到网络Autonomous system一个区域边界路由器能够在多于一个区域的范围工作。它接收路由器链路通知和网络链路通知，并为每一个区域创建一个路由表。58（四）概括链路到AS边界概括链路到AS边界路由器Area 0区域边界路由器在这个区域进行洪泛Area 1区域边界

24、路由器在这个区域进行洪泛Area 2Autonomous systemAS 边界路由器概括链路到AS边界路由器提供到自治区域边界路由器的路由信息。59（五）外部链路外部链路帮助一个自治系统内的路由器知道在自治系统外的哪些网络是可用的。AS边界路由器在AS进行洪泛Area 0Area 1Area 2Autonomous systemNetwork外部链路外部路由选择协议60分组的类型OSPF 分组Hello数据库描述链路状态请求链路状态更新链路状态确认路由器链路网络链路概括链路到网络概括链路到AS边界路由器外部链路61OSPF分组的格式源路由器IP地址区域标识符版本类型报文长度检验和鉴别类型鉴别

25、所有的OSPF分组共享同样的公共首部。62字段说明： 版本：是一个8比特字段。定义OSPF协议的版本。目前是版本2。 类型：是一个8比特字段。如前所述，共5种类型，用值1至5来定义这些类型。 报文长度：是一个16比特字段。定义包括首部在内的总的报文长度。 源路由器IP地址：是一个32比特字段。定义发送该分组的路由器的IP地址。 区域标识符：是一个32比特字段。定义发生路由选择的区域。 检验和：是一个16比特字段。对整个分组进行差错检测，但不包括鉴别类型和鉴别数据字段。 鉴别类型：是一个16比特字段。定义在这个区域内使用的鉴别方法。现在定义了两种类型的鉴别：0表示没有鉴别，1表示口令。 鉴别：是

26、一个16比特字段。是鉴别数据真正的值。目前，若鉴别类型是0，则这个字段就填入0；若类型是1，这个字段就携带8个字符的口令。63（一）Hello报文停用间隔指定路由器IP地址Hello间隔全0备份指定路由器IP地址邻站IP地址重复的ET优先级网络掩码公共首部24字节 类型：164字段说明： 网络掩码：是一个32比特字段。定义网络的网络掩码。 Hello间隔：是一个16比特字段。定义在Hello报文之间的秒数。 E标志：是一个1比特字段。当它置1时，表示该区域是残桩区域。 T标志：是一个1比特字段。当它置1时，表示该路由器支持多种度量。 优先级：是一个8比特字段。定义路由器的优先级，用来选择指定路由器。 停用间隔：是一个32比特字段。定义在路由器确认某个邻站是停用的之前的秒数。 指定路由器IP地址：是一个32比特字段。是该报文所发送的网络的指定路由器的IP地址。 备份指定路由器IP地址：是一个32比特字段。是该报文所发送的网络的备份指定路由器的IP地址。 邻站IP地址：是一个重复的32比特字段。定义已经同意成为该发送路由器的邻站。65（二）数据库描述报文报文序号全0全0链路状态首部（20字节）重复的EB全0公共首部24字节 类型：2MM/SI66字段说