路由选择机制-计算机网络技术基础

2023-10-22 理论教育版权反馈

【摘要】：路由选择解决分组在各交换节点应如何进行转发，即通过哪条路径将数据从源主机传递到目的主机。图7—5路由选择机制目前在广域网中，路由选择功能一般由节点交换机完成；在互联网各子网之间，路由选择功能一般由路由器完成。二者路由选择的依据均是根据其内部的“路由表”。确定路由选择的策略称为“路由算法”。路由选择是网络中所有转发节点共同协调工作的结果，对于大型广域网，必须使用合适的路由算法。

广域网的关键技术是为转发的分组进行路由选择，路由选择机制如图7—5所示。路由选择解决分组在各交换节点应如何进行转发，即通过哪条路径将数据从源主机传递到目的主机。路径选择算法的好坏在很大程度上决定了整个网络的运行性能，如平均延迟时间、网络吞吐率、资源有效利用率等。路由算法的复杂性直接与通信子网拓扑结构的复杂程度、网络规模、交换方式等因素有关。

pagenumber_ebook=178,pagenumber_book=172

图7—5　路由选择机制

目前在广域网中，路由选择功能一般由节点交换机完成；在互联网各子网之间，路由选择功能一般由路由器完成。二者路由选择的依据均是根据其内部的“路由表”。由于二者工作原理基本相同，这里我们以使用中用到最多的路由器为例分析路由原理。

路由通常由以下两个独立的操作组成。

（1）分组转发。采用“逐跳”（hop—by—hop）转发方式。

（2）路由表的管理。生成和更新路由表。

1.分组转发机制

（1）网络上每个路由器都存储着一个路由表，路由表项内容包含可到达的目的网络地址、去往目标网络的下一跳地址、本路由器的出口。路由表中没有源站地址信息，这是因为路由选择中的下一跳只取决于数据报中的目的站地址，而与源站地址无关。路由器的某一个接口收到数据帧后，首先进行帧的拆封并从中剥离出相应的IP分组，然后利用子网掩码求“与”方法从IP分组中提取出目标网络号，根据其目标网络号查找路由表，与路由表项逐条比对看能否找到匹配，即确定是否存在一条到达目标网络的路径信息。若存在匹配，则将IP分组下交数据链路层，重新封装成输出端口所连网络的帧格式并将其转发出去；若不存在匹配，则将该分组丢弃。

上述查找路由表以获得路径信息的过程被称为路由器的“路由”功能，而将从接收端口进来的数据在输出端口重新转发出去的功能称为路由器的“交换”功能。“路由”与“交换”是路由器的两大基本功能。

（2）路由选择是构造路由表的过程。路由表是根据一定的路由选择算法得到的，而转发表又是根据路由表构造出的。

（3）路由选择协议负责发现分组从某个节点到达目的节点的最佳传输路由，以便构造路由表。分组是通过转发表进行转发的。

路由表应该保证：

①路由完备性——必须包含通往所有目的地的下一站信息；

②路由优化性——所指的路径应该是最优路径。

有了路由表，只要根据它来进行分组转发即可。对于大规模的复杂网络，每个交换节点路由表的建立，必须按照一定的算法来进行，即“路由选择算法”。

2.路由算法要求

通信子网为网络源节点和目的节点提供了多条传输路径的可能性。网络节点在收到一个分组后，如何确定向下一节点转发的路径，这就是“路由选择”。确定路由选择的策略称为“路由算法”。路由选择是网络中所有转发节点共同协调工作的结果，对于大型广域网，必须使用合适的路由算法。一个理想的路由算法应具有以下的一些原则。

（1）正确性。算法必须是正确的和完整的。

（2）简单性。算法在计算上应简单。任何路由算法，都会给交换节点带来一定的处理开销，过于复杂的路由算法会使交换节点负担过重。另外，路由算法不应使交换节点在获得当前网络的状态信息时通信量过大，否则造成对全网过大的额外流量开销。

（3）适应性。算法应能适应当前通信量和网络拓扑的动态变化。

（4）稳定性。算法应具有稳定性，以防止对于网络状态的变化反应过于敏感或者过于迟钝。

（5）公平性。算法对网上所有节点应是公平的。

（6）最优性。算法应是最佳的。

应该说，路由算法同时具有上述原则是有矛盾的，有时只能折中。

3.路由算法分类

根据路由选择算法能否自动适应网络拓扑结构及通信流量的变化，路由选择算法又分为“静态路由算法”和“动态路由算法”两大类。

（1）静态路由算法。

由人工预先设计安排好的固定路由，一般是由网络管理员手工配置的路由表信息，称为“静态路由表项”。配置完成后，各节点路由表的静态路由表项保持不变，除非网络管理员重新配置。因此，静态路由配置不能适应网络拓扑结构和通信流量的动态变化，属于非自适应路由算法。当网络的拓扑结构或链路的状态发生变化需另选路由时，需要网络管理员手工去修改路由表中相关的静态路由信息。

静态路由算法的优点如下。

①简便易行，开销小，不必在路由器之间为生成路由表而交换路由信息，可以减少路由器之间的额外通信流量，这对于带宽较紧张，线路冗余度低的网络尤其适合。另外也可减少路由器CPU的计算工作量。

②网络安全保密性高。动态路由因为需要路由器之间频繁地交换各自的路由信息，若被截获可能暴露网络的拓扑结构和网络地址等信息。所以，网络出于安全方面的考虑时也可以采用静态路由。

静态路由算法的缺点是：灵活性差，无法适应网络中发生的链路或节点失效以及阻塞等故障，不能自动调整路由。

静态路由一般适用于负载稳定，拓扑结构变化不大的简单网络环境，也经常应用于一个末梢网络的唯一出口路由，如图7—6所示。末梢网络中去往外部所有网络的数据包都将通过路由器A，在路由器B设置一条指向路由器A的静态路由表项即可实现，这是静态路由的典型用法之一。

pagenumber_ebook=180,pagenumber_book=174

图7—6　末梢网络设置静态路由(www.chuimin.cn)

（2）动态路由算法。

路由器运行动态路由协议软件，彼此间相互通信交换路由信息，自动生成和更新路由表。因此，这种算法交换结点的路由表能够根据网络当前流量和拓扑结构等状态信息进行自动调整选择最佳路径，这被称为“动态路由选择策略”，属于自适应路由算法。

动态路由是基于某种路由协议实现的。动态路由协议是路由器获取路由信息（网络拓扑和可达性信息）、自动维护和更新路由表的机制。这样当网络中的某些路由器或链路损坏时，路由器可以自动调整路由，使得通信的源宿主机之间始终有一条路由保持连通，提高了路由的可靠性。运行动态路由协议的网络生存性很强。这种动态交换路由信息和路由表的生成、调整过程对用户是透明的。动态路由协议如图7—7所示。

pagenumber_ebook=181,pagenumber_book=175

图7—7　动态路由协议

①动态路由算法的优点如下。

A.灵活。能较好地适应网络流量、拓扑结构的变化，能对网络的通信量进行控制，避免或减缓网络中拥挤和阻塞的发生，从而极大地改善网络的性能，减少管理工作量。

B.强壮。可根据网络当前状态选择最佳路径，当网络出现故障时可绕过故障点继续传输。

②动态路由算法的缺点如下。

A.由于算法复杂，需要占用路由器的内存和CPU处理时间，消耗路由器的资源，对路由器性能要求高，设备开销较大。

B.需要各个路由器之间定期交换路由信息，会占用网络的带宽，从而增加网络负担。

C.自适应算法对网络参数的变化反应太快会引起网络流的振荡，反应太慢则得不到最佳路由。为减少这些风险要经常对算法本身的某些参数进行调整，这又增加了网络管理的难度。

自适应算法尽管存在一些缺点，但是在大型网络中仍然得到广泛的应用，因为这种算法的优点是明显的。

4.动态路由算法分类

动态路由算法主要有两大类：距离矢量路由选择算法（Distance—Vector），简称D—V算法；链路状态路由选择算法（Link—State），简称L—S算法。

（1）距离矢量路由选择算法。

每个路由器周期性地向其相邻路由器广播自己知道的路由信息，通知相邻路由器自己可以到达的网络以及到达该网络的距离，相邻路由器可以根据收到的路由信息进行叠加刷新，自己的路由表也向外广播，这样路由信息逐渐传播到了全网。更新过程经过一段时间后，所有的路由器都建立起自己完整的路由表。路由表从更新开始到进入稳定状态，网络中的所有路由器都运行着精确的、足以反映当前互联网络拓扑结构的路由信息，称为“收敛”。快速收敛是动态路由选择协议最希望具有的特征。

路由器所知的最初始路由信息是它从直接相连的网络得出的一组初始直连路由，然后利用路由协议，不断通过已知网络逐步获取未知网络的路由信息，如此逐步扩展直到掌握全网的路由信息。当网络状况发生变化时，路由器中的路由表能够自动地重新发布进行更新，从而保证了正确地转发分组。

距离矢量路由协议的典型代表是RIP协议（Routing Information Protocols），即路由信息协议，是为TCP/IP环境开发的第一个动态路由选择协议，其最大优点就是简单。RIP基于跳数作为距离值（也称“代价”）计算路由，通过计算抵达目的地的最少跳数来选取最佳路径，每30s将整个路由数据库广播一次。RIP认为一个好的路由就是它通过的路由器的数目最少，即“距离短”。RIP协议规定的跳数最多为15跳，当大于等于16跳时，RIP协议即认为目的地不可到达，这样就限制了其所应用的网络规模。另外单纯以跳数作为选路的依据不一定能充分描述路径特征（如带宽等其他因素），可能导致所选的路径不是最优的，因此RIP协议只适用于中小型的网络，属于第一代路由协议。其次，由于路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。由于RIP协议开发的较早，几乎所有的路由器都支持RIP协议。

RIP原理如图7—8所示。

pagenumber_ebook=182,pagenumber_book=176

图7—8　RIP原理

（2）链路状态路由选择算法。

链路状态路由选择算法的基本思想是不直接向相邻路由器通告路由信息，而是将自己所连接的链路状态信息发布给其他路由器，这些信息包括：该路由器连接的链路以及连接到该链路上的相邻路由器、接口信息、传输花费（如带宽）等。由于各路由器之间动态地交换链路状态信息，所以所有的路由器最终都能建立一个全局的链路状态数据库，这个数据库实际描述的就是全网的拓扑结构图。这个拓扑结构图在全网范围内是一致的（这称为链路状态数据库的同步）。因此，每一个路由器都知道全网共有多少个路由器，以及哪些路由器是相连的，到其的代价是多少等。每一个路由器再根据这张全网的拓扑结构图（即链路状态数据库中的数据），使用最短路径算法，计算出自己到达各个目标网络的路由（也叫“最小生成树”），构造出自己的路由表。链路状态路由选择算法的过程如图7—9所示。

pagenumber_ebook=183,pagenumber_book=177

图7—9　链路状态路由选择算法

20世纪80年代中期，基于距离矢量路由算法RIP协议的缺点已使其不能适应大规模网络的互联，Internet工程任务组（IETF）为IP网络开发出了“开放最短路径优先协议OSPF”（Open Shortest Path First）。OSPF是一种典型的基于链路状态的路由协议，需要每个路由器向其同一管理域范围内的其他路由器发送链路状态通告（LSA）信息。在OSPF的链路状态通告中包括所有接口信息、所有的链路状态信息和其他一些变量。运行OSPF协议的路由器首先必须从相连路由器收集有关链路状态信息，建立一张完整的网络拓扑图（链路状态数据库），然后根据最短路径算法计算出每个节点的最短路径——即最佳路由。

链路状态路由选择算法的优点如下。

①网络开销小：仅发布周边链路的状态而不是整个路由表，且仅在网络拓扑结构发生变化时，才进行链路状态更新的发布，因而带宽占用率低。

②路由收敛迅速。OSPF协议的链路状态数据库能较快地进行更新，且各个路由器能及时地更新其路由表。OSPF协议的更新过程收敛快是其重要优点。

③支持VLSM（变长的子网掩码），适应当前灵活划分子网的需求。

④无自环。由于OSPF通过对收集到的链路状态用最小生成树算法计算路由，故从算法本身保证了不会生成自环路由。

⑤网络扩展性好。

由于具有这些优点，采用链路状态算法的路由协议可用于大型网络，属于第二代路由协议，目前应用广泛。