计算机网络中的路由选择协议基本概念

1.理想的路由算法

路由选择协议的核心就是路由算法，即需要何种算法来获得路由表中的各项目。一个理想的路由算法应具有如下特点：

（1）算法必须是正确的和完整的。此处，“正确”的含义是：沿着各路由表所指引的路由，分组一定能够最终到达目的网络和目的主机。

（2）算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销（即完成路由算法而增加的网络通信量）。

（3）算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。当网络中的通信量发生变化时，算法能自适应地改变路由以均衡各链路的负载。当某个或某些结点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时地改变路由。有时也称这种自适应性为“稳健性”。

（4）算法应具有稳定性。在网络通信量和网络拓扑相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应使得出的路由不停变化。

（5）算法应是公平的。路由选择算法应对所有用户（除对少数优先级高的用户外）都是平等的。例如，若仅使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显地不符合公平性的要求。

（6）算法应是最佳的。路由选择算法应当能够找出最好的路由，使分组平均时延最小而网络的吞吐量最大。虽然人们希望得到“最佳”的算法，但这并不总是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均时延或最大吞吐量更加重要。因此，所谓“最佳”只是相对于某一种特定要求下得出的较为合理的选择。

一个实际的路由选择算法，应尽可能接近理想的算法。在不同的应用条件下，对以上提出的6个方面也可有不同的侧重。应当指出，首先，路由选择是个非常复杂的问题，因为它是网络中的所有结点共同协调工作的结果。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先知道，例如，网络中出了某些故障。此外，当网络发生拥塞时，就特别需要出现能缓解这种拥塞的路由选择策略，但恰好在这种条件下很难从网络中的各结点获得所需的路由选择信息。

倘若从路由算法能否随网络的通信量或拓扑自适应地进行调整变化来划分，则只有两大类，即静态路由选择策略与动态路由选择策略。静态路由选择也叫作非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。对于很简单的小网络，完全可以采用静态路由选择，用人工配置每一条路由。动态路由选择也叫作自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。因此，动态路由选择适用于较复杂的大网络。

2.分层次的路由选择协议

互联网采用的路由选择协议主要是自适应的（即动态的）、分布式路由选择协议。由于以下两个原因，互联网采用分层次的路由选择协议：

（1）互联网的规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。所有这些路由器之间交换路由信息所需的带宽就会使互联网的通信链路饱和。

（2）许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到互联网上为此，可以把整个互联网划分为许多较小的自治系统（Autonomous System，AS）。AS是在单一技术管理下的一组路由器，而这些路由器使用一种自治系统内部的路由选择协议和共同的度量。一个自治系统对其他自治系统表现出的是一个单一的和一致的路由选择策略［RFC 4271］。

在目前的互联网中，一个大的ISP就是一个自治系统。这样，互联网就把路由选择协议划分为两大类：(www.xing528.com)

（1）内部网关协议（Interior Gateway Protocol，IGP），即在一个自治系统内部使用的路由选择协议，而这与在互联网中的其他自治系统选用什么路由选择协议无关。目前这类路由选择协议使用得最多，如RIP和OSPF协议。

（2）外部网关协议（External Gateway Protocol，EGP）。若源主机和目的主机处在不同的自治系统中（这两个自治系统可能使用不同的内部网关协议），当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议。目前使用最多的外部网关协议是EGP的版本4（EGP-4）。

自治系统之间的路由选择也叫作域间路由选择（Interdomain Routing），而在自治系统内部的路由选择叫作域内路由选择（Intradomain Routing）。

图4-33所示是自治系统和内部网关协议、外部网关协议。每个自治系统自己决定在本自治系统内部运行哪一个内部路由选择协议（可以是RIP，也可以是OSPF）。但每个自治系统都有一个或多个路由器（图4-33中的路由器R1和R2）除运行本系统的内部路由选择协议外，还要运行自治系统间的路由选择协议（EGP-4）。

图4-33　自治系统和内部网关协议、外部网关协议

这里要指出两点：

（1）互联网的早期RFC文档中未使用“路由器”而是使用“网关”这一名词，但是在新的RFC文档中又改用“路由器”这一名词，因此有的书把原来的IGP和EGP分别改为IRP（内部路由器协议）和ERP（外部路由器协议）。为了方便读者查阅RFC文档，本书仍使用RFC原先使用的名字（IGP和EGP）。

（2）RFC采用的名词IGP和EGP是协议类别的名称，但RFC在使用名词EGP时发生了混乱，因为最早的一个外部网关协议的协议名字正好也是EGP［RFC 827］。后来发现该RFC提出的FGP有不少缺点，就设计了一种更好的外部网关协议，叫作边界网关协议（Border Gateway Protocol，BGP），用来取代旧的RFC827外部网关协议（EGP）。实际上，旧协议EGP和新协议BGP都属于外部网关协议EGP这一类别。因此，在遇到名词EGP时，应弄清它是指旧协议EGP（即RFC 827）还是指外部网关协议EGP这个类别。

总之，使用分层次的路由选择方法，可将互联网的路由选择协议划分为：

（1）内部网关协议：具体的协议有多种，如RIP和OSPF等。

（2）外部网关协议：目前使用的协议就是EGP。

对于比较大的自治系统，还可将所有的网络再进行一次划分。例如，可以构筑一个链路速率较高的主干网和许多速率较低的区域网。每个区域网通过路由器连接到主干网。当在某个区域内找不到目的站时，就通过路由器经过主干网到达另一个区域网或者通过外部路由器到别的自治系统中去查找。下面分别介绍这两类协议。