计算机网络中的分组转发路由选择

网络层的主要功能是将数据包从源机器路由到目标机器。在大多数网络中，数据包需要经过多跳（hop）才能到达目的地。唯一值得指出的例外是广播网络，但即使在广播网络中，如果源机器和目标机器不在同一个网络段中时，路由仍然是一个问题。选择路由的算法以及这些算法所用的数据结构是网络层设计的最主要内容。

路由算法（Routing Algorithm）是网络层软件的一部分，它负责确定一个入境数据包应该被发送到哪一条输出线路上。如果网络内部使用了数据报，那么路由器必须针对每一个到达的数据包重新选择路径，因为自上一次选择了路径之后，最佳路径可能已经发生了改变。如果网络内部使用虚电路，那么只有当建立一条新的虚电路时，才需要作路由决策。此后，数据包只要沿着已经建立的路径向前传递即可。后一种情形有时候也称为会话路由（Session Routing），因为在整个会话过程中（如VPN上的一个终端登录会话），路径必须保持有效。

有时对路由和转发（Forwarding）这两个功能进行区分是非常有用的，路由即对使用哪一条路径作出决策，而转发则是当一个数据包到达时该采取什么动作。可以把路由器想象成内部有两个进程。其中一个进程在每个数据包到达的时候对它进行处理，它在路由表中查找该数据包所对应的出境线路。这个进程即转发进程；另一个进程负责生成和更新路由表，这正是路由算法发挥作用的地方。

无论是针对每个数据包独立选择路由，还是仅在建立新连接时选择路径，路由算法都必须满足某些特性：正确性、简单性、鲁棒（Robust的音译，健壮和强壮之意，是指在异常和危险的情况下系统生存的能力）性、稳定性、公平性和有效性。正确性和简单性不需要多加解释，下面解释一下鲁棒性的要求。一旦某个重要网络投入运行，它有可能需要连续运行数年而不能出现波及系统范围的失败。在此期间，会有各种各样的硬件和软件发生故障。主机、路由器和线路可能会重复失败，网络拓扑结构也可能会多次发生变化。路由算法应该能够处理拓扑结构和流量方面的各种变化，而且不能要求所有主机都停止工作。每次路由器崩溃时都需要网络重新启动的严重后果是可以想象出来的。

稳定性对于路由算法来说也是一个重要目标。有些路由算法无论运行多长时间，都没有收敛到一个固定的路径集合。一个稳定的算法能达到并且保持平衡状态，因此，它应该迅速收敛，在路由算法达到平衡之前，通信可能无法正常进行。

公平性和有效性听起来显然是理所应当的——肯定不会有人反对这两种特性。但是，事实证明，它们往往是两个相互矛盾的目标。

举个简单的例子来说明这种冲突，如图4-4所示，假设在A和A′之间、B和B′之间以及C和C′之间有足够的流量使水平的链路达到饱和。为了使总流量达到最大，X和X′之间的流量应该完全被切断。不幸的是，X和X′可能看不到这一点。很显然，全局效率和单个连接的公平性之间必须有一种折中的处理办法。(www.xing528.com)

图4-4　公平性和效率产生冲突的网络

找到公平性和有效性之间的权衡办法之前，首先必须确定要优化什么性能指标。使数据包的平均延迟达到最小是有效发送流量的一种很明显的选择，但是使网络的总吞吐量最大化也是一种不错的选择，而且这两个目标也是相互冲突的，因为运行任何接近容量的排队系统意味着排队延迟很长。作为一种折中，许多网络企图最小化一个数据包必须经过的跳数或简单降低其经历的跳数。两种选择趋向于减小延迟，同时，减少每个数据包消耗的带宽数量，提高整个网络的吞吐量。

路由算法可以分成两大类：非自适应算法（Nonadaptive Algorithm）和自适应算法（Adaptive Algorithm）。非自适应算法不会根据当前测量或者估计的流量和拓扑结构来调整它们的路由决策；相反，从Ⅰ到J（对所有的I和J）所使用的路由选择是预先在离线情况下计算好，并在网络启动时被下载到路由器中的。这个过程有时候也称为静态路由（Static Routing）。因为它无法响应故障，所以静态路由对于路由选择已经很清楚的场合非常有用。例如，在图4-2中，路由器F应该通过路由器E把数据包发到网络中，根本不管数据包的最终目的地在哪里。

与此相反，自适应算法则会改变它们的路由决策，以便反映出拓扑结构的变化，通常也会反映出流量的变化情况。这些动态路由（Dynamic Ronting）算法在多个方面有所不同：获取信息的来源不同（例如，来自本地、相邻路由器，或者所有的路由器）、改变路径的时间不同（如每当拓扑发生变化时，或者每隔Δt秒随负载变化）以及用于路由优化的度量不同（如距离、跳数或者估计的传输时间）。