2.4.1 寻找路径

网络层的主要任务就是寻找一条转发数据包的路径，我们称之为路由算法。路由算法分为两类：一类称为链路状态算法，另一类称为距离向量算法。但是无论是何种算法，我们都需要为每一个机器节点指定一个唯一编号，之后各个机器节点交换信息的时候就用这个唯一编号作为对方的标识符。我们以ID作为每个机器节点的编号代称。接下来大致介绍一下这两种类型的算法。

1．链路状态算法

链路状态（LS）算法的思路如下。

1）确认所有物理相连的机器节点：每加入一个机器节点机器，该机器就需要确认所有与其物理相连的机器节点，并获取其唯一编号。具体方法是，向整个网络中的机器节点都发送一个用于探测机器节点的数据包，当机器节点接收到该数据包后，返回一个对应的数据包，其中包含其ID。

2）测量到每个机器节点的时间长度：我们需要测量出当前机器节点到与其相连的机器节点到底需要花多长时间。方法是向对应的机器节点发送一个数据包，接收方回送一个数据包。发送方就可以根据发送和接收响应数据包的时间来确定发送数据消耗的时间。

3）共享信息：各个机器节点会向其他机器节点广播自己的连接信息，这样所有的机器节点都可以逐步构建起整个网络的拓扑结构。

4）根据拓扑结构寻找最短路径：然后我们可以使用最短路径算法，根据机器节点的网络图（每个机器节点是图中的一个节点），使用Dijkstra算法来计算出最短路径。Dijkstra算法大家应该都比较熟悉，这里不过多阐述。

2．距离向量算法

我们可以看到链接状态算法是全局性算法，需要在每个机器节点构建出全局网络并计算路径。但这样会消耗太多的系统资源。与此相对的是局部性的距离向量（DV）算法。

该算法的思路如下。

1）建立路由表：路由表很简单，只记录当前机器节点到达其他各个机器节点的一个权值，权值越大，路径越长。并记录这种情况下应该将数据转发给哪个相邻机器节点。

2）计算与相邻机器节点的链接权值：每个机器节点只计算与自己直接相连的机器节点的路径权值（可以理解为数据的到达时间），计算方法可以采取与LS相同的方法。

3）每隔一段时间将自己的路由表发送到相邻机器节点：每个机器节点每隔一段时间将自己最新的路由表发送给相邻的机器节点，通过各个机器节点局部性地不断传递，各个机器节点逐步修正路由表。

4）在转发消息时，只要选择与目标机器节点权值最小的那个相邻机器节点，并将消息转发出去即可。

我们可以看到，这种方式消耗的资源较少，处理速度也较快。另外我们也可以证明，路由表最后是可以收敛的，对此感兴趣的读者可以自行查阅资料进行研究。