第15次课路由选择协议

第5章网络层广域网技术5.2因特网的路由选择协议路由算法1.理想的路由算法①算法必须是正确的和完整的。②算法在计算上应简单。③算法应能适应通信量和网络拓扑的变化。④算法应具有稳定性。⑤算法应是公平的。⑥算法应是最佳的。5.2因特网的路由选择协议路由算法1.理想的路由算法①算法必须是正确的和完整的。既沿着各路由表所指引的路由,分组一定能够到达目的网络或主机。①算法在计算上应简单。②算法应能适应通信量和网络拓扑的变化。③算法应具有稳定性。④算法应是公平的。⑤算法应是最佳的。5.2因特网的路由选择协议路由算法1.理想的路由算法①算法必须是正确的和完整的。②算法在计算上应简单。路由选择的计算不应使通信量增加太多额外的开销。①算法应能适应通信量和网络拓扑的变化。②算法应具有稳定性。③算法应是公平的。④算法应是最佳的。5.2因特网的路由选择协议路由算法1.理想的路由算法①算法必须是正确的和完整的。②算法在计算上应简单。③算法应能适应通信量和网络拓扑的变化。即“自适应性”或“称稳健性”。①算法应具有稳定性。②算法应是公平的。③算法应是最佳的。5.2因特网的路由选择协议路由算法1.理想的路由算法①算法必须是正确的和完整的。②算法在计算上应简单。③算法应能适应通信量和网络拓扑的变化。④算法应具有稳定性。在通信量或网络拓扑相对稳定的情况下，路由算法应收敛于一个可接受的解。①算法应是公平的。②算法应是最佳的。5.2因特网的路由选择协议路由算法1.理想的路由算法①算法必须是正确的和完整的。②算法在计算上应简单。③算法应能适应通信量和网络拓扑的变化。④算法应具有稳定性。⑤算法应是公平的。即算法对所有用户都平等。①算法应是最佳的。5.2因特网的路由选择协议路由算法1.理想的路由算法①算法必须是正确的和完整的。②算法在计算上应简单。③算法应能适应通信量和网络拓扑的变化。④算法应具有稳定性。⑤算法应是公平的。⑥算法应是最佳的。“最佳”就是以最低的代价实现路由算法。而“代价”是由一个或多个因素综合决定的一种度量，如链路长度、数据率、链路容量、传播时延、通信量、缓存等。5.2因特网的路由选择协议路由算法2.两种类型的路由算法按照“从路由算法能否随网络的通信量或拓扑自适应的进行调整变化”来划分，路由算法分为两大类：静态路由选择策略（非自适应的）和动态路由选择策略（自适应的）。静态路由选择策略的特点是简单和开销小，但不能及时适应网络的变化。如最短路径路由。动态路由选择策略的特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。如距离矢量路由。5.2因特网的路由选择协议路由算法3.分层次的路由选择协议因特网采用分层次的路由选择协议，这是由于以下两种原因：因特网的规模巨大，不可能所有的路由器知道所有的网络；许多单位不希望外界了解自己网络的内部布局，但同时又希望连接到因特网上。为此，因特网将整个网络划分成许多小的自治系统（AS）。每个自治系统都有权自主决定在本系统内采用何种路由协议。5.2因特网的路由选择协议路由算法3.分层次的路由选择协议因特网又将路由协议划分为两大类：①内部网关协议IGP。②外部网关协议EGP。5.2因特网的路由选择协议路由算法3.分层次的路由选择协议因特网又将路由协议划分为两大类：①内部网关协议IGP。即在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用得最多，如RIP和OSPF协议。如RIP和OSPF协议。①外部网关协议EGP。5.2因特网的路由选择协议路由算法3.分层次的路由选择协议因特网又将路由协议划分为两大类：①内部网关协议IGP。②外部网关协议EGP。若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议，将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议EGP。如BGP-4。5.2因特网的路由选择协议路由算法自治系统之间的路由选择也称为域间路由选择，而在自治系统内部的路由选择称为域内路由选择。5.2因特网的路由选择协议内部网关协议RIP路由信息协议RIP是内部网关协议IGP中使用得最广泛的一个，是因特网的标准协议，其最大优点就是简单。RIP是一种分布式的基于距离向量的路由选择协议。分布式路由选择协议的特点是每个路由都要不断的和其它路由器交换路由信息。用于维护从它自己到其他每一个目的网络的距离记录。5.2因特网的路由选择协议内部网关协议RIP分布式路由选择协议的要点是：1.仅和相邻路由器交换信息。2.交换的信息是当前本路由器的路由表。3.按固定的时间间隔交换路由表。路由表中最主要的信息是：到某网络的距离，以及经过的下一跳地址。路由表更新的原则是：找出每个目的网络的最短距离。这种算法称为距离向量算法。5.2因特网的路由选择协议内部网关协议RIPRIP协议中“距离”的定义：从一路由器到直接连接的网络的距离定义为1。从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加1。RIP协议中的“距离”也称为“跳数”。RIP认为一个好的路由就是它通过的路由器的数目少，即“距离短”。“距离”的最大值为16时即相当于不可达。可见RIP只适用于小型互联网。5.2因特网的路由选择协议内部网关协议RIP①最短路径路由属于非自适应的算法。就是所有的路由选择都是事先计算好了的，在网络启动时被下载到路由器中，称为静态路由。基本思想是：建立一个子网的拓扑图，找出各对节点之间的最短路径。这里的最短路径指的可能是地理距离、跳数或是时延。5.2因特网的路由选择协议内部网关协议RIP①最短路径路由下图是从A节点开始的路由算法右表是A节点的路由表ABGE2261FCHD3322724(2,A)(4,B)(5,E)(6,E)(8,F)(9,B)(10,H)目的站下一跳距离A-0BB2CB9DB10EB4FB6GB5HB8A站的路由表5.2因特网的路由选择协议内部网关协议RIP②距离矢量路由属于自适应算法。就是每个路由器维护一张表，表中列出当前已知的到每个目标的最佳距离，以及所使用的线路。通过在邻居之间互相交换信息，路由器不断的更新这张表。5.2因特网的路由选择协议内部网关协议RIP②距离矢量路由更新路由表的基本思想是：每个路由器每隔T毫秒向它的邻居发送一个列表其中包含它到每个目标的”距离”；同时，每个路由器也收到邻居发出的类似的列表。每个路由器根据各个邻居发来的列表，重新计算到达各目标节点的最短“距离”和最佳路径，并依此修改自己的路由表。J的新表中新估距离=Min（J到邻居的距离+邻居到其它节点距离）ABCDEFGHIJKL到AIHKA02420218AB1236312820AC2518193628ID402782420HE147302217IF2320194030IG183163118HH172001912HI210142210IJ9117100-K24222206KL29339915K810126J到4个邻居的距离向量新估距离下一站J的新路由表内部网关协议RIPRIP存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。这就是好消息传播得快，而坏消息传播得慢。5.2因特网的路由选择协议R2R1网1网3网2正常情况1112R1R1说：“我到网1的距离是1，是直接交付。”R2说：“我到网1的距离是2，是经过R1。”内部网关协议RIPRIP存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。这就是好消息传播得快，而坏消息传播得慢。5.2因特网的路由选择协议R2R1网1网3网2正常情况1112R1R1说：“我到网1的距离是1，是直接交付。”R2说：“我到网1的距离是2，是经过R1。”网1出了故障11612R1R1说：“我到网1的距离是16（表示无法到达），是直接交付。”R2在收到R1的更新报文之前，还发送原来的报文，因为这时R2并不知道R1出了故障。…13R215R2116R214R1116R1…内部网关协议OSPFOSPF又称为开放最短路径优先协议，其最主要特征是使用分布式的链路状态协议。和RIP相比，不同的有三点：1.使用洪泛法向本自治系统中所有的路由器发送信息。5.2因特网的路由选择协议R发送更新报文ACK报文内部网关协议OSPFOSPF的三个要点：1.使用洪泛法向本自治系统中所有的路由器发送信息。2.发送信息是与本路由器相邻的所有路由器的链路状态。3.只有当链路状态发生变化时，路由器才发此信息。由于各路由器之间频繁的交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库，即全网的拓扑结构图。每个路由器使用该数据库的数据，构造自己的路由表。因而能查出到每个目的网络应该走哪条路径。5.2因特网的路由选择协议自治系统AS5.2因特网的路由选择协议内部网关协议OSPF为了使OSPF能够用于规模很大的网络，OSPF将一个自治系统再划分为若干个更小的范围，叫做区域。区域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划分区域的好处是将利用洪泛法交换链路状态信息的范围局限于每个区域而不是整个自治系统，这就减少了整个网络的通信量。在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。OSPF使用层次结构的区域划分。在上层的区域叫作主干区域(backbonearea)。主干区域的标识符规定为0.0.0.0。主干区域的作用是用来连通其他在下层的区域。自治系统AS5.2因特网的路由选择协议内部网关协议OSPF主干区域中的路由器称为主干路由器，其中区域相连接的又称为区域边界路由器。区域0.0.0.1区域0.0.0.3主干区域0.0.0.0至其他自治系统R9R7R6R5R4R3R2R1网8网6网3网2网1网7区域0.0.0.2网4网5R8R7R6R5R4R35.2因特网的路由选择协议外部网关协议BGPBGP使用的环境与内部网关协议不同。因为：1.因特网的规模太大，使得域间路由选择非常困难。由于各自治系统是运行自己选定的内部路由选择协议，使用自己指明的路径度量，因此，当一条路径通过几个不同的自治系统时，要想对这样的路径计算出有意义的费用是不可能的。要寻找最佳路由是很不现实的。2.域间路由选择必须考虑有关策略。因此，边界网关协议BGP只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由。5.2因特网的路由选择协议外部网关协议BGP在配置BGP时，每个自治系统的管理员要选择至少一个路由器作为该自治系统的“BGP发言人”，它往往又是BGP的边界路由器。自治系统连通图BGP所交换的网络可达性的信息就是要到达某个网络所要经过的一系列AS。当BGP发言人互相交换了网络可达性的信息后，各BGP发言人就根据所采用的策略从收到的路由信息中找出到达各AS的较好路由。BGP构造出的自治区与连通图是树形的，没有回路。BGP发言人交换路径向量主干网（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）N1，N2本地ISP（AS5）N3，N4本地ISP（AS6）N5本地ISP（AS7）N6，N7主干网还可发出通知：“要到达网络N5,N6和N7可沿路径（AS1,AS3）。”5.2因特网的路由选择协议外部网关协议BGPBGP协议的特点：BGP协议交换路由信息的结点数量级是自治系统数的量级，这要比这些自治系统中的网络数少很多。每一个自治系统中BGP发言人（或边界路由器）的数目是很少的。这样就使得自治系统之间