路由算法（网络层）_汇集树

引言

网络层的主要功能是将数据包从源机器路由到目标机器。在大多数是网络中，数据包需要多跳才能到达目的地。唯一一个值得指出的例外是广播网络，但即使在广播网络中，如果源机器和目标机器不在同一个网络段中时，路由仍然是一个问题。选择路由的算法以及这些算法所用的数据结构是网络层设计的最主要内容。
路由算法是网络层软件的一部分，它负责确定一个入境数据包应该被发送到哪一条输出线路上。如果网络内部使用了数据报，那么路由器必须针对每一个到达的数据包重新选择路径，因为自上一次选择了路径之后，最佳路径可能已经发生了改变。如果网络内部使用虚电路，那么只有当建立一条新的虚电路时，才需要做路由决策；伺候，数据包只要沿着已经建立的路径向前传递即可。后一种情形有时候称为会话路由，他被我在整个会话过程中，路径必须保持有效。
路由与转发的区分。路由即对使用哪一条路径作出决策，而转发是当一个数据包到达时该采取什么操作。可以把路由器想象成内部有两个进程。其中一个进程在每个数据包到达时对它进行处理，它在路由表中查找该数据包所对应的出境线路。这个进程称为转发进程；另一个进程负责生成和更新路由表，这正是路由算法发挥作用的地方。
无论是针对每个数据包独立选择路由，还是仅建立新连接时选择路径，路由算法必须满足某些特性：正确性、简单性、鲁棒性（健壮）、稳定性、公平性和有效性。正确性和简单性无需多加解释，对鲁棒性的要求似乎没有那么显而易见。一旦一个重要网络投入运行，它有可能需要连续运行数年而不能出现波及系统范围的失败。在此期间，将会有各种各样的硬件和软件发生故障。路由算法应该能够处理拓扑结构和流量方面的各种变化，而且不能要求所有主机都停止所有的工作。
稳定性对于路由算法来说也是一个重要目标。有一些路由算法无论运行多长时间从来都没有收到过一个固定路径的集合（收敛是所有路由器在最佳路径上取得一致的过程）。一个稳定算法能到达平衡（能采用最佳路径的选择通常会保持负载均衡），并且保持平衡状态。因此它应该迅速收敛，在路由算法达到平衡之前，通信可能无法进行。
公平性和有效性往往会相互矛盾。如图，假设在A和A次之间、B和B次以及C和C次之间有足够的流量使得水平链路达到饱和。为了使总流量达到最大，X和X次之间的流量应该被完全切断。全局效率和单个连接的公平性之间必须有一种折中的处理办法。

要找到折中办法，必须确定要优化什么性能指标。使数据包的平均延迟达到最小是有效发送流量的一种很明显的选择，但是使网络的总吞吐量最大化也是一个不错的选择。但这两个目标是相互冲突的，因为运行在任何一个接近容量的排队系统意味着排队延迟很长。作为一种折中，许多网络企图最小化一个数据包必须经过的跳数。两种选择趋向于减小延迟，同时减少每个数据包消耗的带宽数量，从而提高吞吐量。
路由算法可以分成两大类：非自适应算法和自适应算法。非自适应算法不会根据当前测量或者估计的流量和拓扑结构，来调整路由决策。相反，从I到J（对所有的I和J）所使用的路由选择是预先在离线情况下计算好，并在网络启动时被下载到路由器中的。这个过程有时也称为静态路由，因为它们无法响应故障，所以静态路由对于路由选择已经很清楚的场合非常有用。自适应算法则会改变它们的路由决策以便反映出拓扑结构的变化，通常也会反映流量的变化情况。这些动态路由算法在多个方面有所不同：获取信息的来源不同（例如来自本地、相邻路由器或者所有的路由器）、改变路径的时间不同（比如拓扑结构发生变化时，或者每隔多少时间随负载变化）以及用于路由算法的度量不同（比如距离、跳数或者估计的传输时间）。
在以后的章节中，将讨论不同的路由算法。算法除了从源端发送数据包到接收方外，还涉及传递模式。有时候路由的目标是把数据包发送到多个地址、全部地址或者一组地址中的一个。在这里描述的所有路由算法都基于拓扑结构进行路由决策；将基于流量水平做路由决策的可能性推迟到拥塞算法一章中讲解。

1、优化原则

在讨论具体算法之前，先不考虑网络拓扑结构和流量情况，而是给出最优路径的一般性描述。最优路径的一般陈述如下：如果路由器 J 在从路由器 I 到 K 的最优路径上，那么 J 到 K 的最优路径也必定遵循同样的路由。作为最优原则的一个直接结果，从所有的源到一个指定目标的路径的集合构成了一棵以目标节点为根的树，这样的树称为汇集树。如图b，图中的距离度量是跳数。所有路由算法的目标是为所有路由找到这样的汇集树，并根据汇集树来转发数据包。

汇集树并不是唯一的；有可能存在具有相同路径长度的其他汇集树。如果允许选择所有可能的路径（前提是遵守优化原则），则树就变成了更一般的结构，称为有向无环图（DAG）。DAG没有环路。由于汇集树没有换，所以每个数据包将在有限的跳数内完成传递。然而实际情况并非如此。在运行过程中，链路和路由器可能会故障，然后又恢复运行。所以，不同的路由器对当前拓扑结构的了解可能有所不同。不管如何，最优原则和汇集树为测量其他路由算法提供了一个基准。

2、最短路径算法

最短路径的一种测量路径长度的方法是跳数，另一种方法是以千米为单位的物理距离。然而，也可以使用平均延迟（最短路径就是最快路径）等方法。最优路径可能包含距离、带宽、平均流量、通信成本、平均延迟等因素，通过改变它们的权重，路由算法就可以根据任何一种标准或多种标准来计算“最短”路径。
一种算法（Dijkstra）是找出网络中的一个源节点到全部目标节点的最短路径。每一个节点都标出了（圆括号内）从源节点沿着已知的最佳路径到达本节点的距离。初始时，所有的路径都不知道，因此所有节点都被标记为无限远。算着算法的进行，陆续找到了最短路径，于是节点的标记发生变化，以便反映出更好的路径。每个标记可能是暂时的，也可能是永久的。初始时，所有的标记都是暂时的，当发现一个标记代表了从源节点到该节点的最短可能路径，该标记就变成永久。（图，从A到D最短路径计算的前6个步骤）

为了说明标记算法的过程，先看图a中的加权无向图，这里是权值代表了一种度量，比如说距离。我们现在要找出从A到D的最短路径。开始时将节点A标记为永久，然后依次检查每一个与A相邻的节点，并且用它们与A之间的距离重新进行标记。为了可以重构出最终路径，每当一个节点被重新标记时，也要标记出这次探测动作的出发节点（即前一个节点）。在检查了每一个与A相邻的节点之后，我们检查整个图中全部具有暂时性标记的节点，并且使得其中具有最小标记的那个节点称为永久性的，如图b所示，这个节点就变成新的工作节点。下面给出这个算法的程序描述。全部变量n和dist（distance）描述了图，在shortest_path被调用之前对这两个变量进行初始化。这段程序与前面描述的算法之间唯一的区别是，从终结节点 t 开始计算最短路径，而不是从源节点 s 开始。

#define MAX_NODES 1024 /* maximum number of nodes */
#define INFINITY 1000000000 /* a number larger than every maximum path */
int n, dist[MAX_NODES][MAX_NODES]; /* dist[i][j] is the distance from i to j */
void shortest_path(int s, int t, int path[])
{ struct state { /* the path being worked on */
		int predecessor; /* previous node */
		int length; /* length from source to this node */
		enum {permanent, tentative} label; /* label state */
	} state[MAX_NODES];
	int i, k, min;
	struct state *p;
	for (p = &state[0]; p < &state[n]; p++) { /* initialize state */
		p->predecessor = −1;
		p->length = INFINITY;
		p->label = tentative;
	}
	state[t].length = 0; state[t].label = permanent;
	k = t; /* k is the initial working node */
	do { /* Is there a better path from k? */
	for (i = 0; i < n; i++) /* this graph has n nodes */
		if (dist[k][i] != 0 && state[i].label == tentative) {
			if (state[k].length + dist[k][i] < state[i].length) {
				state[i].predecessor = k;
				state[i].length = state[k].length + dist[k][i];
			}
		}
	/* Find the tentatively labeled node with the smallest label. */
	k = 0; min = INFINITY;
	for (i = 0; i < n; i++)
		if (state[i].label == tentative && state[i].length < min) {
			min = state[i].length;
			k = i;
			}
		state[k].label = permanent;
	} while (k != s);
	/* Copy the path into the output array. */
	i = 0; k = s;
	do {path[i++] = k; k = state[k].predecessor; } while (k >= 0);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

之所以选择后向搜索的原因是，每个节点都被标记了它的前任节点而不是它的继任节点。因此，当最终的路径被复制到输出变量path中的时候，该路径也被逆转了过来。两次逆转的效果刚好抵消，因此，结果按正确的顺序产生。

3、泛洪算法

在实现路由算法时，每个路由器必须根据本地只是而不是网络的全貌做决策。一个简单的本地技术是泛洪，这种技术将每一个入境数据包发送到除了源端口的每个其他端口。很显然，泛洪会产生大量重复数据包。事实上，除非采取某些措施来抑制泛洪过程，否则将会产生无限多的数据包。其中一项措施是在每个数据包头中设置一个跳计数器，，每经过一跳计数器减一，当计数器到达0时就丢弃该数据包。理想情况下，跳计数器的初始值应该等于从源端到接收方之间的路径长度，如果发送方不知道路径有多长，它可以将计数器的初始值设置为最坏情况下的长度，即网络的直径。
带有跳计数器的泛洪能够产生随着跳数增大而指数增长的的重复数据包，而且路由器要复制以前已经看到过的数据包。抑制泛洪算法的一种更好的技术是让路由器跟踪已经泛洪过的数据包，从而避免二次转发。实现这个目标的一种方式是让每个源路由器在接收来自主机的数据包时填上一个序号，然后每个路由器为每个源路由器准备一张表，记录已经观察过到的来自源路由器的序号，如果入境数据包在这张表中，它就不能被再泛洪到其他路由器。为了防止该表无限膨胀，每个表应该使用一个计数器k作为参数，它表示直到k的所有序号都已经观察到了。当一个数据包抵达时，很容易检查该数据包是否已经被泛洪过（只需要比较该数据包序号和k）；如果是被泛洪过，则丢弃该数据包，而且，不需要记录k以下的整个列表，因为k本身就是这部分数据的有效概括。
对于发送大多数数据包来说，泛洪算法是不切实际的，但它也有用途。首先，它确保数据包能被传送到网络中的每个节点。如果数据包的目的地只有一个，那么这种发送途径就是一种浪费；但对于广播信息来说，这是一种有效的广播手段。在无线网络中，站发送的全部信息都可以被位于其无线范围内的所有其他站接收，这实际上就是一种形式的泛洪，一些无线路由器算法利用了这个特性。
其次，泛洪途径的鲁棒性非常好。即使大量路由器被出现了故障，泛洪也能找到一跳路径，使该数据包到达目的地。泛洪需要的安装很少，路由器仅仅需要知道自己的邻居即可这意味着，泛洪可用作其他路由算法进行比较的性能度量。因为泛洪算法能并发选择每一条可能的路径，因此总能选出最短的那条路径，没有其他算法能够产生一个更短的延迟（如果忽略泛洪过程本身产生的开销）。

4、距离矢量算法

计算机网络通畅使用动态路由算法。虽然动态路由算法比上述泛洪算法更复杂，但由于这些算法能找到当前网络拓扑结构中的最短路径，因而更加有效。特别的，两个动态算法最为流量，即距离矢量算法和链路状态路由算法。
距离矢量路由算法是这样工作的：每个路由器维护一张表（即一个矢量），表中列出了当前已知的到每个目标的最佳距离，以及所使用的链路。这些表通过邻居之间交换信息而不断更新，最终每个路由器都了解到达每个目的地的最佳链路。
距离矢量路由算法是最初ARPANET使用的路由算法，也曾被用于Internet，相应的协议名称为RIP协议。在距离矢量路由算法中，每个路由器维护一张路由表，它以网络每个路由器为索引并且每个路由器对应一个表项。该表项包含两部分：到达该目标路由器的优选出境线路，以及到达该目标路由器的距离估计值，距离的度量可能是跳数，或者其他因素。假定路由器知道它到每一个邻居的距离，如果所用的度量是跳数，那么该距离就是1跳。如果度量值为传播延迟，则路由器很容易测量出链路的传播延迟。它只要直接发送一个特殊的ECHO数据包给邻居，邻居收到后盖上时间戳，尽可能快地发送回来即可。
举个例子，假设使用延迟作为距离度量，并且路由器知道它到每个邻居的延迟。每隔T毫秒，每隔路由器给它的每个邻居发送一个列表，该表包含了它到每个目标的延迟估计值；同时，它也从每个邻居那里收到一个类似的表。想象一个路由器接收到了来自邻居X的一个表，其中Xi表示邻居X估计的到达路由器 i 所需要的时间。如果该路由器知道它到邻居X的延迟为m毫秒，那么它也能明白在Xi+m毫秒之内经过X可以到达路由器 i 。对每个邻居都执行这样的运算，最终可以发现到达每个目标的估计值，然后在新的路由表中使用这个最佳估计值以及对应的出境线路。
这个更新过程如图。图a是一个网络，图b的前4列显示了J 从邻居路由器接收到的延迟矢量。A声称它到B有12秒延迟，到C有25秒延迟，到D有40秒延迟，等等。假定 J 已经测量和估计了它到邻居A、I、H和K 的延迟分别为8、10、12和6毫秒。

现在考虑 J 如何计算它到路由器 G 的新路径。它知道在8毫秒之内可以到达A，并且A声称可以在18毫秒内到达 G，所以 J 知道如果将那些目标地址为 G的数据包转发给 A的话，需要26秒的延迟。类似的，它计算出经过 I 、H和K到达G的延迟分别为41、18、和37毫秒。在这些计算得出的距离值之中，最好的结果是18，所以在 J 的路由表中，对应于 G的表项中的延迟值为18毫秒，所用的线路是经过H的那条。对于所有其他的目标地址执行同样的计算，最好得到的新路由如图所示。

无穷计算问题

整个网络最佳路径的寻找过程称为收敛。距离矢量路由算法作为一项简单技术很有用，因为路由器可以在所有路径中有选择地计算出一条最短路径。但实际上它有一个严重的缺陷：虽然它总是能够收敛到正确的答案，但速度可能非常慢。尤其是，它对于好消息的反映非常迅速，而对于坏消息的反应异常迟缓。考虑这样一个路由器，它到目标X的最佳路径非常大，如果在下一次交换信息时，邻居A突然报告说它到X有一条延迟很短的路径，那么，该路由器只是将发送给X的流量切换到通向A的线路。经过一次矢量交换，好消息就发挥作用了。
为了看清楚好消息的传播有多快，请考虑图中一个五节点（线型）网络，这里的延迟量为跳数。假定A最初处于停机状态，所有其他的路由都知道了这一点。换句话说，它们到A的延迟记录为无穷大。

当A启动时，其他的路由器通过矢量交换知道了这一点。为了简化起见，我们假定在某个地方有个巨大的锣鼓，它定期敲击来启动所有路由器惊醒矢量交换。在第一次交换时，B知道它左边的邻居到A的延迟为0。于是B在它的路由表中建立一个表项，说明A离它一跳远。所有其他的路由器仍认为A是停机的。这时候，针对A的路由表项如图a中的第二行所示。在接下去的交换中，C知道B有一条路径通向A，并且路径长度为1，所以它更新自己的路由表，指明它到A的路径长度为2，但是D和E要到以后才能听到这个好消息。很显然，好消息扩散的速度是每交换一次往远处走一跳。如果一个网络中最长路径是N跳，那么经过N次交换之后，每个路由器都将知道所恢复的链路和路由器。
现在考虑图b的情形，在这里所有的线路和路由器最初都是正常工作的。路由器B、C、D和E到A的距离分别为1、2、3和4。突然A停机了，或者A和B之间的链路断了。在第一次信息交换时，B没有听到来自A的任何信息。幸运的是，C说“别担心，我有一条通向A的长度为2的路径”，B并不怀疑C的路径经过自身，B能知道的全部只是C可能有10条链路，每条都通向A，且长度为2（作者诙谐）。因此，B认为它可以通过C到达A，路径长度为3，在第一次交换之后，D和E并不更新它们的A表项。在第二次交换时，C注意到它的每一个邻居都声称有一条通向A的长度为3的路径，它随机挑出一条，并且将它到A的距离更新为4，如图b中的第三行。通过后续交换，可以得到图b中的余下记录历史。所以怀消息传播得很慢：没有一个路由器具有一个比它所有邻居的最小值还大于1的值，逐渐地，所有路由器都会趋向无穷大，凡是所需交换的次数依赖于代表无穷大的数值，由于这样的原因，明智的做法是将无穷大设置为最长的路径加1。这个问题称为无穷计数问题，已经有许多试图解决该问题的工作，例如，防止路由器向邻居返回一个从该邻居获得的最佳路径，这个方法称为带有染毒逆向的水平分裂。然而，这些工作实际工作得并不好。问题的核心在于当X告诉Y他有一条通往某个地方的路径，Y无从知道自己是否已经在这条路径上。

5、链路状态路由

1979年以前ARPANET一直使用距离矢量路由算法，而在此之后则改为使用链路状态路由算法。导致距离矢量算法退位的主要原因是当网络拓扑结构发生变化后距离路由算法需要太长时间才能收敛到稳定状态（无穷计数问题引起）。因此，距离矢量路由算法被一个全新的算法所替代，该算法就是链路状态路由算法。今天，链路状态路由算法的变种算法——IS-IS或者OSPF已经成为大型网络或Internet应用最为广泛的路由算法。
链路状态路由算法的设计思想非常简单，可以用五个部分加以描述：（1）发现它的邻居节点，并了解其网络地址。（2）设置到每个邻居节点的距离或者成本度量值（3）构造一个包含所有刚刚获知的链路信息包（4）将这个包发送给其他的路由器，并接收来自所有其他路由的信息包（5）计算出到每个其他路由器的最短路径。实际上，算法将完整的拓扑结构分发给了每一个路由器。然后每个路由器运行Dijkatra算法（最短路径算法之一）就可以找出从本地到每一个其他路由器的最短路径。下面讲述每一个步骤的实现。

发现邻居

当一个路由器启动时，它的第一个任务是找出哪些路由器是它的邻居。为了实现这个目标，它只需在每一条点到点线路上发送一个特殊的HELLO数据包。线路的另一端的路由器应该返回一个应答说明自己是谁。这个名字必须是全局唯一的，因为当一个远程路由器以后听到有三个路由器都能连接到F时，它必须能够确定这三个路由器所提到的F是同一个路由器F。
当两个或多个路由器通过一个广播链路连接（比如一个交换机、环或者经典以太网），情形会稍微复杂一点。图a显示了一个广播LAN直接与三个路由器A、C和F连接的情形，如图所示，每个路由器都连接到一个或多个其他的路由器上。

广播LAN为连接到其上任何一对路由器提供了彼此的连通性然而，把LAN建模成许多个点到点链路会增大拓扑结构，从而导致浪费消息。模拟局域网的一个更好方法是把它看做一个节点，如图b所示。在这里，我们引入了一个新的人造节点N，它与A，C和F连接。LAN上的一个指定路由器被选中替代N运行路由协议。事实上，从LAN上的A到C时可能的，这里用ANC标识这条路径。

设置链路成本

为了寻找最短路径，链路状态路由算法需要每条链路的距离或成本度量。当邻居的成本可自动设置或由网络运营商配置的度量。一种常用的选择是使成本与链路的带宽成反比。例如，1Gbps以太网的成本可能是1，而100Mbps以太网的成本可能是10.这样可以使得高容量的路径成为路由的更好选择。如果网络在地理上分散，链路的延迟可以作为成本的组成部分，这样才能更好地选择较短链路上的路径。确定这种延迟的最直接方法是通过线路给另一边发送一个特殊的ECHO数据包，要求对方发回。通过测量往返时间再除以2，发送路由器可以得到一个合理的延迟估算值。

构造链路状态包

一旦收集到了所需要的交换信息，每个路由器的下一步工作是构建一个包含所有这些信息的数据包。该数据包的内容是首先是发送方的标识符，接着是一个序号和年龄，以及一个邻居列表。对于每个邻居，同时要给出到这个邻居的延迟。图a显示了一个网络实例，每条线路上标出了延迟信息。这6个路由器所对应的链路状态数据包如图b所示。

构造链路状态数据包很容易。难的是确定什么时候构造数据包。一种可能的做法是周期性地创键数据包，也就是说，以一定时间间隔创建链路状态数据包。另一种可能的做法是每当发生某些重要的事情时才创建数据包，比如当一条线路断掉或者一个邻居节点停机时，当它们重新恢复运行时，或者当它们的特性发生了一定变化时。

分发链路状态包

链路状态路由算法最技巧的部分在于分发链路状态数据包。所有路由器必须快速并可靠地获得全部的链路状态数据包。如果不同的数据包使用了不同的版本的拓扑结构那么它们计算出来的路由很可能会不一致，例如出现环路、目标机器不可达以及其他问题。
首先，我们描述最基本的发布算法，然后在对它进行改进。基本思路是使用泛洪法将链路状态数据包分发给所有路由器。为了控制泛洪规模，每个数据包都包含一个序号，序号随着每一个新数据包发出而逐一递增。路由器记录下所有它看到的所有（源路由器、序号）对。当一个新的链路状态数据包到达时，路由器检查这个新来的数据包是否已经出现在上述观察到的列表中。如果这是一个新数据包，则把它转发到除入境线路之外的所有其他线路上，。如果这是一个重复数据包，则将它丢弃。如果数据包的序号小于当前看到的来自源路由器的最大序号，则将它当做过时的数据包而拒接，因为路由器已经有了更新的数据。
发布算法还有几个问题需要处理：第一，如果序号绕回，可能产生混淆，解决方案是使用一个32位的序号，即使每秒钟产生一个链路状态数据包，也需要137年才能绕回。其次，如果一个路由器崩溃，那么它将丢失所有的序号记录表。如果它再从0开始，那么，下一个数据包将作为重复数据包而拒绝；再次，如果一个序号被破坏了，比如发送方发送的序号为4，但是由于产生了1位错误，所以接收方看到的序号是65540，那么序号从5到65540的数据包都将被当做过时数据包而拒接，因为接收方认为当前的序号是65540。
所有这些问题的解决方案都一样：在每个数据包的序号之后包含一个年龄字段，并且每秒钟将年龄减1。当年龄字段被减到0时，来自路由器的该信息将被丢弃。通常情况下，每隔一段时间，比如说10秒，一个新的数据包就会到来；所以，只有当一个路由器停机时（或者6个连续的数据包被丢失，这种情形发生的可能性不大），路由器信息才会超时。在初始泛洪过程中，每个路由器也要递减age字段，这样可以确保没有数据包丢失，也不会无限制生存下去。
对上述算法进行一些改进可以使其更健壮。当一个链路状态数据包被泛洪到一个路由器时，它并没有立即被排入队列等待传输，而是被放到一个保留区中等待一段时间（这个时间间隔应该小于发送新数据包的时间间隔，寒注），如果在这个数据包转发出去之前，另一个来自同一源路由器的链路状态数据包也到来了，那么就比较它们的序号。如果两个数据包序号相等，则丢弃重复数据包。如果两者不相等，则丢弃旧的数据包。为了防止线路产生错误导致丢包和错包，所有的链路状态数据包都要被确认。
在上图图a所示的网络中，路由器B使用的数据结构如下图所示（路由器B的状态包缓冲区）。这里的每一行对应于一个刚刚到达的，但是还没有处理完毕的链路状态数据包。该表记录了数据包的来源、序号和年龄，以及状态数据。而且，针对B的三条线路（分别到A、C和F）还记录了发送和确认标志。发送标志标明该数据包必须在所指示的线路上发送。确认标志表明它必须在这条线路上得到确认。

图中，来自A的链路状态数据包可以直接到达，所以B必须将它发送给C和F（发送标识为1），清切按照标志位的只是向A发送确认（不确认标识为0），类似的，必须把来自F的数据包转发给A和C，并向F返回确认。然而，第三个数据包有所不同。它到达两次，一次经过EAB，另一次经过EFB。因此，它只需要被发送给C，但是要向A和F确认。如果一个重复数据包到来时原来的数据包仍然在缓冲区中，那么标志位必须作相应的改变。例如，如果表中的第四项发出去之前，C的链路状态数据包的一份副本从F到达，那么这六位将被改为100011，以表明该数据包必须向F确认，但是不用转发给F了。

计算新路由

一旦路由器已经积累了全部的链路状态数据包之后，它就可以构造出完整的网络图，因为每条链路都已经表示出来了。事实上，每条链路被表示了两次，每个方向各表示一次。不同方向的链路可能有不同的成本。最短路径计算可找到从A到B和从B到A的路径。
现在可以在路由器本地运行Dijkstra算法，以便构造出从本地出发到所有可能目标的最短路径，这个算法的运行结果告诉路由器到达每个目的地能够走哪条链路。这个信息被安装在路由表中，而且恢复正常操作。
相比距离矢量算法，链路状态路由算法需要更多的内存和计算。对于一个具有n个路由器的网络，每个路由器有k个邻居，那么，用于储存输入数据所要求的内存与kn成正比，这至少与列出全部目的地的路由表一样大（两个路由器，寒注）。二桥，计算时间的增长快过kn，即使采用最有效的数据结构，在大型网络中运行这个算法依然是个问题。不过在许多实际场合，链路状态路由算法工作得很好，因为它没有慢收敛问题。
链路状态路由算法被广泛地应用于实际网络中，所以现在提一下某些使用该算法的例子。许多ISP使用中间系统到中间系统（IS-IS）链路状态协议，它是专门为DECnet而设计的，后来被ISO采纳用于OSI协议；自此以后，它被修改了多次以便能够处理其他协议，例如著名的IP协议。开发最短路径有限（OSPF）是另一个主流链路状态协议。它是在IS-IS之后几年由IETF设计的，而且它吸收了许多IS-IS的创意。这些创意包括：一种泛洪链路状态更新的自稳定方法、LAN上的指定路由器概念以及计算和支持路径分裂和多个度量的方法。因此，IS-IS和OSPF之间的差异非常小。其中一个最重要的差别是IS-IS可同时携带多个网络层协议的信息（比如IP、IPX、AppleTalk），OSPF不具备这个特性。对于大型的多协议环境这一特性是个优势。
下面对路由算法做出一般性评论。连接状态、距离向量和其他路由算法依赖于所有路由器计算路径的处理。硬件或软件，甚至少数路由器的问题都可以肆虐破坏网络。例如一个路由器声称有一条实际上并不存在的链路，或者忘记一条实际上存在的链路而声称没有，由此产生的网络图都是不正确的。如果一个路由器转发数据包失败，或者在转发期间自己发生故障，对于的路由都将无法工作。最后，如果内存不足或者路由计算出错，就会发生不好的事情。随着网络规模的迅速增长，某些路由器偶尔失败的概率变得不可忽视。应对这个困境的诀窍是尽量做好安排，当发生不可避免的错误时把危害降到最低。

1、层次路由

随着网络规模的增长，路由器的路由表也成比例地增长。不断增长的路由表不仅消耗路由器内存，而且还需要更多的CPU时间来扫描路由器表以及更多的带宽来发送有关的状态报告。当网络增长到一定规模时，路由器不太可能再为其他每一个路由器维护一个表项。所以，路由不得不分层进行，就好像电话网络中的做法那样。
在采用了分层路由之后，路由器被划分成区域。每个路由器知道如何将数据包路由到自己所在区域内的目标地址，但是对于其他区域的内部结构毫不知情。当不同的网络被互联在一起，很自然会将每个网络当做一个独立的区域，一个网络中的路由器不必知道其他网络的拓扑结构。
对于大型网络，两级的层次结构可能还不够；可能有必要将区域组织成簇，将簇组织成区，将区组织成群，等等。举一个例子，请考虑如何将一个数据包从加利福利亚的伯克利路由到肯尼亚的马林迪。伯克利的路由器知道加利福利亚的详细拓扑结构，但是可能将其他所有州际的流量发送给洛杉矶的路由器；洛杉矶的路由器能够将流量直接路由器给美国其他国家的路由器，但是它会将国际流量发送到纽约；纽约的路由器直接将所有流量发送至目标国家中负责处理国际流量的路由器，比如肯尼亚的内罗毕。最后，该数据包将沿着肯尼亚国家中的路径树往下传送，一直到达马林迪。
图中给出了一个两级层次的定量分析例子，其中包含了5个区域。路由器1A的完整路由表有17个表项，如图b所示。如果采用分级路由，则路由表如图c所示，所有针对本区域内的路由表项都跟原先一样；但是，所有到其他区域的路由器都将被压缩到了单个路由器中。因此，所有到区域2的流量都要经过1B-2A线路，其余的远程流量都经过1C-3B线路。层次路由使得路由器1A的路由表从17项降低为7项。随着区域数与每个区域中路由器数量之比值的增加，节省下来的表空间也随之增加。

不幸的是，这种空间的节省不是免费得来的，它需要付出代价，其代价形式是增加了路径长度。例如，从1A到5C的最佳路径是经过区域2，但采用了层次路由之后，所有到区域5的流量都要经过区域3，因为对于区域5中的大多数目标来说，这是更好的选择。
当单个网络变得非常大时，应该分多少层？例如，一个具有720个路由器的子网。如果没有分层，每个路由器需要720个表项；如果子网被分成24个区域，每个区域30个路由器，那么，每个路由器只需要30个本地表项，加上23个远程表项，总共53个表项；如果采用三级层次结构，总共8个簇，每个簇包含9个区域，每个簇包含9个区域，每个区域10个路由器，那么每个路由器需要10个表项用于本地记录，8个表项用于到同一簇内其他区域的路由，7个表项用于远程的簇，总共25个表项。Kamoun和Kleinrock发现，对于一个包含N个路由器的网络，最优层数是ln N，每个路由器所需的路由器表项是elnN个，它们还证明了由于分层路由而导致的平均路径长度的实际增长非常小，通常是可以接收的。

2、广播路由

在有些应用中，主机需要给其他多个或者全部主机发送消息。例如，用于发布天气预报、股市行情最新报告或者现场直播节目等服务，它们最佳的工作方式是将消息广播给所有机器，然后让那些感兴趣的机器读取数据。同时给全部目标地址发送一个数据包称为广播。
一种不要求网络具有任何特殊性质的广播方法是让源机器简单地给每一个目标单独发送一个数据包。这种方法不仅浪费带宽，而且还要求源机器拥有所有目标机器的完整地址列表。实际上这种做法不够理想，即使它广泛适用。一种改进方法称为多目标路由，每个数据包包含一组目标地址，或者一个位图，由该位图指定所期望到达的目标。当一个数据包到达一个路由器时，路由器检查数据包携带的所有目标，确定哪些输出线路是必要的（只要一条输出线路是到达至少一个目标的最佳路径，那么就是必要的）。路由器为每一条需要用到的输出线路生成一份该数据包新的副本，在这份副本中只包含了那些使用这条线路的目标地址。实际上，原来的目标集合被分散到这些输出线路上。在经过了足够多的跳数之后，每个数据包将只包含一个目标地址，因此可被当做普通的数据包来对待。多目标路由方法就如单个地址的数据包一样，只不过当多个数据包必须遵循同样的路径时，其中一个数据包承担了全部的费用，而其他的舒筋梢则是免费搭载。因此，网络带宽的利用率更高。然而，这种模式依然要求源端知道全部的目标地址，对于路由器来说，要确定从哪些线路转发多目标数据包的工作量太大，尤其是处理多个不同的数据包时。
泛洪是更好的广播路由技术。当每个源实现了序号，泛洪能有效利用链路，而且路由器要做的决策也很简单。虽然泛洪方法不适合普通的点到点通信，但它被认为值得考虑做广播，而且，事实证明，一旦计算出普通数据包的最短路径，我们可以把广播做得更好。
逆向路径转发思想被认为是一种非常优秀的广播技术。当一个广播数据包到达一个路由器时，路由器检查它到来的那条线路是否正是通常用来给广播源端发送数据包用的那条线路。如果是，说明这是一个极好的机会，该广播数据包是沿着最佳路径被转发过来的，因而是到达当前路由器的第一份副本。如果是这种情况，则路由器将该数据包转发到除了到来的那条线路之外的其他线路上。然而，如果广播数据包时从其他任何一条并非首选的到达广播源的线路入境的话，该数据包被当做一个可能的重复数据包而被丢弃。
例子如图。图a显示了一个网络，图b显示了该网络中路由器 I 的一棵汇集树，图c显示了逆向路径算法是如何工作的。在第一跳，I 发送数据包给F、H、J和N。这些数据包中的每一个都是在通向 I 的首选路径（假定首选路径都沿着汇集树）到来的，这点用字母外面加一个圆圈来表示。在第二跳，共产生了8个数据包，其中，在第一跳接收到数据包的路由器各产生2个数据包。结果，所有这8个数据包都到达了以前没有访问过的路由器，其中5个是沿着首选线路到来的。在第三跳所产生的6个数据包中，只有3个是沿着首选线路（在C、E和K）到来的，其他的都是重复数据包。在经过5跳和24个数据包以后，广播过程终止。相比之下，如果完全沿着汇集树的话，只需要4跳和14个数据包。

逆向路径转发的路径的主要优点是它有效而且易于实现。它只往每个方向上的链路发送一次广播数据包，就像泛洪一样简单，而仅仅要求路由器知道如何到达全部目标；路由器无须记住序号（或使用其他机制来防止泛洪）或者在数据包中列出全部的目标地址。
最后一种算法改进了逆向路径转发行为。它明确使用了以发起广播的路由器为根的汇集树，或者任何其他便利的生成树。生成树是网络的一个子集，它包含所有的路由器，但是没有任何环路。汇集树是生成树的一种。如果每个路由器都知道它的哪些线路属于生成树，那么，它就可以将一个入境广播数据包复制到除了该数据包到来的那条线路之外的所有生成树线路上。这种方法可最佳使用带宽，并且所生成的数据包也绝对是完成这项任务所需要的最少数量。例如，图b的汇集树就被用作生成树，广播数据包的副本最少，只有14个。唯一的问题是每个路由器都必须知道这棵生成树才可以正常工作。有时候这样的信息是可以得到的（比如采用了链路状态路由算法，所有路由器都知道完整的网络拓扑，因而它们计算出一条生成树），但是有时候无法获得这样的信息（比如采用了距离矢量路由算法）。

3、组播路由

有些应用，比如多人游戏或者体育赛事视频直播到几个观看点，这样的应用将数据包发送给多个接收者。除非组的规模很小，否则给每个接收者单独发不同的数据包的代价很昂贵。另一方面，如果在一个由百万节点组成的网络中有一个由1000个机器组成的组，采用广播技术发送数据包显然是一种浪费，因为大多数接收者对广播的消息并不感兴趣。因此需要一种办法能够给明确定义的组发送消息，这些组的成员数量虽然很多，但相比整个网络规模却很小。
给一个组发送消息称为组播，使用的路由算法称为组播路由。所有的组播方案都需要一些方法来创建和撤销特定的组，并确定哪些路由器是组的成员。如何完成这些任务不是路由算法要关注的。现在，假定每个组由一个组播地址标识，并且路由器知道自己属于哪些组。组播方案建立在广播路由方案的基础上，为了将数据包传递给组的成员同时有有效利用带宽，数据包可沿着生成树发送。然而，最佳生成树的使用取决于组的密度分布。密集分布指接收者遍布在网络的大部分区域；洗漱分布指大部分网络都不属于组。
如果组是密集分布的，那么广播是一个良好的开端，因为它能有效地把数据包发送到网络的每个角落。但广播可能将一些不属于该组成员的路由器，因而也是一种浪费。Deering和Cheriton探索出一个方案，就是通过修建广播生成树把不通往组成员的链路从树中删掉。修剪结果得到的是一棵有效的组播生成树。
例子如图，图a其中有两个组：组1和组2。有些路由器连接的主机属于其中的一个组或同时属于两个组。最左边的路由器的一棵生成树如图b。此树可用于广播，对于组播来说则过度了，这从下面显示的两个修剪版本可见一斑。在图c中，所有不通向组1成员的主机链路已被删除，结果是一棵针对最左边路由器发送到组1的生成树。数据包的转发就只能沿着这棵树进行，可见这比广播树有效，因为这里只有7条链路而不是10条链路。如d显示了一棵针对组2修剪后的组播生成树。相比广播树它也更加有效，此时只有5条链路。这个例子表明，不同的组播组有不同的生成树。

生成树的修剪方式有许多种。如果路由器使用了链路状态路由算法，并且每个路由器知道完整的网络拓扑结构，包括了解哪些主机属于哪个组，那么就可以使用一种最简单组播算法。每个路由器针对组内每个发送者构造一棵它自己修剪后生成树，具体做法是先按常规方法构造一棵以发送者为根的汇集树，然后从汇集树节点上删除所有不连接到组成员的链路。MOSPF就是一个以这种方式工作的链路状态协议例子。
如果采用距离矢量路由算法，则要遵循不同的修剪策略。基本算法是逆向路径转发。然而，一旦一个路由器不属于任何一个组，并且没有连接到需要连接该组播消息的其他路由器，那么它要用PRUNE（减少、删除）消息作为接收该组播消息的响应，告诉发送方该消息的邻居不要再给自己发送任何来自该组发送者的消息。如果一个路由器连接的主机没有一个属于该组成员，并且从它以前转发组播消息的所有线路都接收了这样的修剪消息（意味着除源端以为的其他连接处都没有属于该组的成员，寒注），那么它也同样以PURNE消息来响应（它自然也不需要连接源端了，寒注），通过这种递归方式，最终修剪出一棵生成树。距离矢量组播路由协议（DVMRP）就是以一个这样方式工作的组播路由协议的例子。
修剪过程的最后结果得到的是一棵有效的生成树，该树只用到了那些抵达组成员真正需要的链路。这种方法的一个潜在缺点是路由器需要做大量的工作，特别是大型网络。假设一个网络有n组，平均每个组有m个节点。在每个路由器上针对n组，每个组有m棵修剪生成树（因为每个路由器给组中成员发送消息的生成树是不同的），因此总共有mn棵生成树。路由器转发数据包将沿着不同的方向进行，具体方向取决于组内哪个节点是发送者的位置。当存在大量的组，并且组内发送者很多时，需要大量空间来储存所有的树。
另一种设计是采用基于核心树的技术，计算某个组的单棵生成树。采用这种方法时所有路由器都同意某个路由器作为根，这个根称为核心或汇聚点，然后每个成员通过给根发送一个数据包来建立这棵树。树是组播数据包遵循的路径集合。图a显示了一棵组1的核心树。为了把数据包发送到这个组，发送者把数据包发送给核心；当数据包到达核心后，它再被沿着树往下转发。图b显示了网络右侧一个发送者的组播过程。作为性能优化的一种措施，发送该组的数据包并不需要先发送到核心然后再开始组播。一旦数据包到达树，它便沿着树向上转发给根，但同时沿着树转发到其他分支。

对于所有的组播源使用同一棵共享树是无法达到最优的。例如，在图b中，从网络右侧的发送者到达右上角的组成员通过核心要三跳，如果直接发送或许不需要三跳。共享树的低效率取决于核心和发送者的位置，把核心设置在所有发送者的中间往往是一种合理的做法。如果只有一个发送者，比如视频流传输到一个组，那么将发送者作为核心是最优的。另外值得注意的是共享树可以大大节省储存开销、消息发送和计算。每个路由器只要为每个组保存一棵树，而不是m棵树。此外，不属于这棵共享树一部分的路由器根本不需要为组做任何工作。正是出于这个原因，像基于核心树的共享树方法被用于Internet的稀疏组播，成为协议流的一部分，例如协议独立组播。

4、选播路由

在选播方式下，数据包被传递给最近的一个组成员。发现这些路径的方案就是所谓的选播路由。为什么需要选播？有时候，节点提供了诸如报时或者内容分发等服务，这类服务对客户而言最重要的是获取正确的信息而不是与哪个节点取得联系，任何节点都可以，只有它能提供所需的服务。例如，选播就作为域名系统的一部分广泛应用于Internet。
我们不需要为选播指定新的路由方案，因为普通的距离矢量和链路状态路由算法可用来生成选播路由。假设我们要选播数据包到组1的成员，该组成员都将被赋予一个组地址“1”而不是一个个独立的地址。距离矢量路由就像往常一样分发向量，并且节点将只选择到目的地1的最短路径。这将导致数据包被发送到目的地1的最近实例。图a显示了选播路由，此过程之所以能正常工作是因为路由协议并没有意识到目的地多个实例。也就是说，它认为节点1的实例都是同一个节点，如图b所示的拓扑结构。

这个过程也同样适用于链路状态路由协议，虽然要额外考虑这样的情况，路由协议似乎找不到通过节点1的最短路径，这将导致跨越网络空间的跳跃，因为节点1的实例是那些真正位于网络不同部分的节点。然而，链路状态协议已经能够区分路由器和主机。

5、移动主机路由

将使用术语移动主机示意诸如移动过程中使用计算机的这些设备，以便与从不移动的固定主机截然区分。移动主机引入了新的复杂性：路由一个数据包到移动主机，网络首先要找到该主机。我们将考虑的模型世界中，假设所有主机都有一个永久的家乡位置，该位置用于不会改变。每个主机也有一个永久的家乡地址，用来确定其家乡位置。移动主机所在系统的路由目标是使人们有可能利用固定的家乡地址来发送数据包，无论它们在哪里都能有效地把数据包送到。当然，这里的关键是要找到它们。
一种不同的模型是每当移动主机移动，以及拓扑结构发生变化后就重新就算路由。然后我们可以采用前述的路由方案。然而，随着移动主机的数目越来越多，这种模式将很快导致整个网络陷入不断计算新路由的过程。使用家乡地址能大大降低这种负荷。
另一种方法是在网络层之上提供移动，这就是今天笔记本电脑典型的用法。当它们被转移动新的Internet位置，笔记本电脑就获得一个新的网络地址。这里新老地址之间不存在任何关联；网络也不知道他们属于同一台笔记本电脑。在此模型中，一台笔记本电脑可用于浏览网页，但其他主机无法给它发送数据包（例如一个入境呼叫），除非有更高层的位置服务，例如移动之后再登录Skype。此外，主机在移动期间无法保持与网络的连接，而是必须重新启动建立新的连接。网络层的移动性对解决这些问题非常有用。
Internet和蜂窝网络的移动路由采用的基本思想是移动主机把自己在哪里告诉给家乡位置的一台主机。这台主机称为家乡代理，它将以移动主机的名义采取行动，一旦它知道移动主机的当前位置，它就可以将数据包转发给移动主机。

如图。一个在西北部的西雅图的发送者想发送一个数据包给通常设在美国纽约的主机，但是移动主机到来圣地亚哥。在圣地亚哥的移动主机必须获得一个本地网络地址，然后才能使用网络。这是主机获得网络地址通常会发生的情况。本地地址称为转交地址。一旦移动主机有了这个地址，它可以告诉家乡代理它在哪儿。他给家乡代理发送一个带有转交地址的注册消息（第一步），图中用虚线表示，以表明它是一个控制信息而不是一个数据报文。

接下来，发送者使用其永久地址发送一个数据包给移动主机（第二步）。这个数据包被网络路由到主机的家乡位置，因为这是主机家乡地址的所属地。在纽约，家乡代理截获该数据包，然后用一个新的头包裹或者封装该数据包，并在捆绑后的结果发送给转交地址（第三步）。这种机制称为隧道，该机制在Internet上非常重要。当封装后的数据包到达转交地址，移动主机解开它并提取出来自发送者的数据包，然后移动主机直接给发送者发应答数据包（第四步）。这个路由过程称为三角路由，因为如果远程位置离家乡位置很远时，这条路由可能是迂回的。作为第四步的一部分，发送者可借鉴当前的转交地址，把随后的数据包直接发送给移动主机。具体做法是通过隧道发送到转发地址（第5步），完全绕过家乡位置。无论什么原因，在移动主机移动时如果失去了连接，则家乡地址可随时用来寻址到移动主机。
一般来说，当一个主机或路由器得到这种形式的信息“现在开始，请把Z的所有邮件发送给我”时，可能会产生两个问题，我在跟谁谈话，以及这是否是个好主意。安全信息被包含在消息中，因此可以用加密协议检查消息的合法性。
移动路由算法有许多变种。上面描述的方案是IPv6流动模型，这种移动主要形式用在Internet，以及诸如UMTS蜂窝网络中基于IP的那部分。我们发现如果发送方是个固定节点，则情况简单些；但设计方案时必须考虑这两个节点都是移动的情形。另外主机可能是移动网络的一部分，例如在一个平面上的计算机。对基本方案进行扩展就可以支持移动网络，不涉及任何主机部分的工作。
有些方案利用外地（即远程）代理，类似家乡代理但放置在远程位置，或类似于蜂窝网络中的访问位置寄存器（VLR）。然而，最近的研究方案并不需要外地代理；移动主机自己承担外地代理的行为。在这两种情况下，移动主机的临时位置仅限于被少量的主机获得（例如移动主机、家乡代理和发送者），因此大型网络中的许多路由器不需要重新计算路由。

6、自组织网络路由

当主机移动时路由器的工作如前所述，另一种更极端的情形是路由器本身也是移动的。这种可能性主要发生在以下几种情况下：地震现场的紧急救援工作、战场上的军事车辆、海上航行的一队舰队或者一群配备了笔记本电脑的人们聚集在一个没有802.11网络的区域。
在所有这样或那样的情形中，每个节点用无线通信，并且同时承担路由器和主机的双重角色。如果网络中的节点彼此靠近，那么该网络称为自组织（Ad hoc）网络，或者移动自组织网络（MANET）。Ad hoc网络区别于有线网络的原因在于网络拓扑更加复杂。节点可以来来去去，消失一会儿突然又出现在一个新的地方。在有线网络中，如果一台路由器有一条通往某个目标的有效路径，那么该路径将会持续有效（除非故障）。而在Ad hoc网络中，拓扑结构可能每时每刻都在变化，所以路径的可能性和有效性自发地改变着，甚至没有任何警告。毋庸多说，这些情况使得Ad hoc网络的路由比固定网络更具挑战性。
针对Ad hoc目前已经提出了许多种路由算法。然而，由于Ad hoc网络相比移动网络实际很少使用，因此无法确定哪种协议更有效。作为一个学习案例，我们将考察其中一个最流行的路由算法，即Ad hoc按需距离矢量（AODV）路由算法。它是相对的距离矢量算法，适应在移动环境中工作，即节点的带宽有限和电源寿命相对较短。下面是此算法的陈述。

路由发现

在AODV中，到某个目的地的路由是按需发现的，即只有当某个节点要给目标节点发送数据时才去找路径。这种方式可以节省大量不必要的工作，比如在路由使用之前拓扑就发生变化，因而之前的所有路由工作都白费了。在任何时刻，Ad hoc网络都可以用连接节点的图来描述。如果两个节点可以直接通信，则这两个节点是连接的。我们采用了一个简单恰当的模型，即每个节点都可以与位于其覆盖范围内的其他节点通信。实际网络要复杂得多，可能有建筑物、山坡或者其他妨碍通信的障碍物，还可能出现这种情况情况：节点A连接到节点B，但是节点B却无法连接到节点A，因为A有比B更强大的功率。为了简化起见，假设所有的连接都是对称的。
图中是一个Ad hoc网络。假设节点A上的一个进程想要给节点 I 上的一个进程发送数据包。AODV算法在每个节点上维护了一张距离矢量表，以目标节点作为关键字，每个表项给出了有关该目标节点的信息，包括将数据包发送给哪个邻居才可以到达这个目标。首先，A检查自己的表，没有发现针对 I 的表项。因此，它必须去发现一条通向 I 的路径。

为了找到节点 I ，A构造一个ROUTE REQUEST（路由请求）包，并且使用前述的泛洪算法广播它。该包从A被传输到B和D，如图所示。每个节点重新广播，该包继续达到节点F、G和C → 节点H、E和 I 。源端设置的一个序号用来淘汰泛洪算法过程中的重复请求包。例如，D丢弃来自B的传输，因为它已经转发过请求数据包了。
最后请求包到达节点 I ，节点 I 构造一个ROUTE REPLY（路由应答）包。这个包沿着请求包所遵循的路径逆向单播给发送者。这项工作要求每一个中间节点必须记住给它发送请求包的节点。如图b\c\d所示，虚线表示可能的逆向路由，实现表示发现的路由。每个中间节点在转发应答数据包时还要讲跳数递增1，告诉节点到目标节点多远。应答数据包还告诉每个中间节点，使用哪个邻居能到达目标节点。节点G和D在处理应答数据包时把听到的最好的路由填入它们的路由表中。当该应答包到达节点A，一条新路由ADGI就被创建出来。
在一个大型网络中，AODV算法会产生许多广播包，即使对于比较近的目标也是如此。为了减少开销，可以使用IP包的Time to live字段来限制广播范围。该字段由发送者初始化，并且每经过一跳该字段被减1。如果该字段被减到0，则把包丢弃，不再广播。因此，路由发现过程可以作如下修改：为了发现一个目标，发送者广播一个ROUTE REQUSET包，其中TTL字段设置为1。如果在一段合理的时间内没有应答包返回，则再发送一个ROUTE REQUSET包，这次将TTL字段设置为2。以后的每一次尝试分别使用TTL的3、4等值，按照这种方法，搜索过程首先在本地进行，然后扩大到更大的范围。（Windows系统下可以设置，也可以使用pathping和tracert命令跟踪）.

路由维护

因为节点可以移动或关闭，所以网络的拓扑结构也自然会发生变化。路由算法必须能够处理这样的情况。每个节点周期广播一个HELLO消息，并且期望它的邻居做出响应。如果没有响应到来，消息的广播这就知道它的邻居已经离开接收范围或者失效。类似地，如果它试图给一个邻居发送数据包而没有响应，那么它也知道邻居不可用。
这些信息可被用来清除掉那些不再有效的路由。对于每一可能的目标节点，每个节点（比如说N）记录自己的活跃邻居，即那些在最近时间给它发过到达该目标的数据包。当N的邻居变得不可达时，它就检查自己的路由表看哪些通往目标节点的路由使用了刚刚离开的邻居。对于这些路径中的一个，通知相应的活跃邻居，因为它们经过N的路径不再有效，必须从路由表中删除。一般情况下，活跃邻居在告诉它们自己的活跃邻居，如此递归下去，直到所有依赖走掉节点的路由从全部路由表中删除。
在这个阶段，无效的路由器已被清除出网络，发送者可以使用我们描述过的路由发现机制来发现新的有效路由。然而，这里有一点复杂，距离矢量协议可能有慢收敛问题，或者拓扑发生变化后的无穷计数问题，这些问题把新的有效路由和旧的无效路由混淆在一起。为了保证快速收敛，路由包括了一个由目标节点控制的序号。目标序号就像个逻辑时钟。目标节点每次发送一个新的ROUTE REPLY时就递增该序号。发送者请求发现一条新路由时，就在ROUTE REQUEST请求报文中包括它最后使用的那条路由的序号，这个序号要么是刚刚被清除的路由的序号，要么作为初始值被设置为0。该求情报文将被广播直到发现一条具有更高序列的路由。中间节点储存具有更高序号的路由，或者当前序号下具有更少跳的路由。（混乱）
按需协议的精髓在于中间节点只储存正在使用中的路由。在广播期间了解的其他路由信息经过短暂延迟后会超时。相比需要定期广播路由更新信息的标准距离矢量协议，只发现并储存那些要使用的路由有助于节省带宽和电池寿命。到目前为止，我们已经考虑过网络中只有单条路由的情况，即从 A 到 I 。为了进一步节省资源，路由发现和路由维护可被重叠的路由共享。例如，如果B也想给 I 发送数据包，它将执行路由发现。然而，在这种情况下，请求报文首先到达D，而D已经有了一条路由可以通向 I 。因此节点 D 生成一个路由应答报文，告诉B这条路由无需做任何额外工作。
还有许多其他的Ad hoc路由方案。另一个著名的按需路由方案是动态源路由（DSR）。贪婪边界无状态路由（GPSR）则探讨了另一种基于地理位置信息的不同的路由策略。如果所有节点知道它们的地理位置，则数据包的转发无需进行路由计算，只需简单地朝着正确的方向，并绕开任何死角即可。究竟哪个路由协议能胜出将取决于Ad hoc网络的类型，必须时间证明对这种网络是有效的。