VisualGMQ的博客

计算机网络-5-网络层-路由选择算法

 2322  5 分钟  

《计算机网络：自顶向下方法》的学习笔记。

这一节记录了路由选择算法，主要是对关联向量算法的解释。

简介

路由器在接收到分组之后，需要找到最快传递到目的地的路径。确定这种路径的算法就是路由选择算法。

现在实现路由选择算法有两种方式：

  • 每路由器控制：指每个路由器运行一种路由算法的情况，每台路由器都有分组转发和路由选择功能。这种主要是将计算负担放在路由器本身。
  • 逻辑集中式控制：指只有一台机器运算路由选择算法，路由器想要找到路径的时候需要向此机器请求路径。这种主要是将计算负担单独放在一台机器上。一般来说，每个路由器都有一个控制代理（CA)，每当要得到路径的时候，需要CA向逻辑集中式路由选择控制器发送请求，得到路径后传给路由器。CA之间不能互相交流，也不能参与路由选择运算。

路由选择算法的分类

有三种分类方法

  • 集中式还是分散式：
    • 集中式路由选择算法：用完整的，全局性的网络信息计算出从源到目的地的最低开销路径。也就是说每个路由器（或者集中式路由选择控制器）需要知道整个网络线路的信息。我们这里会介绍其典型算法链路状态算法。
    • 分散式路由选择算法：路由器以迭代的，分布式的方式进行计算。没有节点拥有整个网路的信息，其每个路由只需要与其相邻的路由的信息就可以开始工作。这里会详细说明其典型算法距离向量算法。
  • 静态的还是动态的：
    • 静态路由选择算法：路由随之间的变化非常缓慢，通常是人工进行调整
    • 动态路由选择算法：路由器自己可以随着网络哦流量负载和拓扑发送变化，但是会受到选择循环和路由振荡之类的情况影响
  • 负载敏感的还是迟钝的
    • 负载敏感算法：链路开销会动态的变化以反映出底层链路的拥塞水平，如果拥塞过高会趋向于绕开该链路来选择路由。
    • 负载迟钝算法：某条链路的开销不能反映拥塞水平。

链路状态路由选择算法和距离向量算法

链路状态路由选择算法

这个算法是集中式的算法，每个路由器都会知道整个网路的情况。具体怎么知道的是用链路状态广播算法来完成的，也就是将当前路由器的状态广播给所有路由器。所以每个节点可以并行地计算出下一跳目的地。

具体的算法有很多种，因为这个问题是完全的图论问题，只需要将路由器当做节点，路由器之间的路径当做边，并且测量出边的开销（分组通过此边的开销）即可。所以你可以使用任何的最短路径算法来解决。比较常用的是Prim和Dijkstra算法。这两种算法数据结构中详细说过，我就不再说明了。

距离向量算法

这个算法是分布式的，迭代的，异步的和自我终止的。

  • 分布式的：此算法需要路由器将自己的信息发送给其相邻路由器。
  • 迭代的：这个过程要持续到相邻路由器之间没有更多信号交换位置
  • 异步的：不要求所有路由器同时运行此算法
  • 自我终止的：没有计算应该停止的信号，它会自我停止。

首先我们定义：

邻居：最接近当前路由器的其他路由器为当前路由器的邻居，即当前路由器可直达的路由器为其邻居。

开销：分组经过一跳所耗费的时间。从x路由器到y路由器的开销记为$c(x,y)$

然后我们还得知道一个重要公式：：Bellman-Ford公式：

令$d_x(y)$为路由器x到y的最低开销路径的开销，那么Bellman-Ford公式为： $$ d_x(y) = min_v{c(x,y) + d_v(y)} $$ 其中$v$为x的所有邻居

Bellman-Ford公式说明了：在图中，从x到y的最短路径是集合${x到y的距离+x相邻节点到y的最短路径}$中的最小值。

这也很好理解：如果对于x的任意邻居v，存在v到目的地y的最短路径，那么显然从x到y的最短路径就是 从x到v再从v到y的最短路径值的最小值。

有了Bellman-Ford公式，任意一个分组从x到y的算法就可以如此描述：

  1. 通过公式找到最短路径上的下一跳路由$v^*$
  2. 将分组转发给$v^*$
  3. 再在$v*$上应用公式得到$v*$的下一跳地址，以此类推，直到分组到达目的地。

为了实现这个算法，需要定义距离向量：

距离向量$D_x=[(D_x(y): y\in 不包括x的路由器集合)]$是x到除了自己的所有路由器的开销估计。

所以现在，每个路由器x需要维护三个量：

  • 对于每个邻居v，从x到v的开销$c(x,v)$
  • x自己的距离向量$D_x$
  • 它的每个邻居的距离向量$D_v$

每个节点不时地向其邻居发送自己的距离向量，邻居接收到距离向量之后，会按照Bellman-Ford公式重新计算自己的距离向量：

$D_x(v)=min_v{c(x,v)+D_v(y)}$

如果距离向量的值变了，他也会如法炮制，向自己的邻居传递自己的距离向量。

在不停地传递距离向量的情况下，所有路由器的路由表总会更新到最短下一跳。这样就得到了最短路径。

距离向量（DV）算法的缺陷

距离向量算法会遇到选择环路，假定现在有如下路由链路：

a---1---b
 \     /
 4 \ /50
    c

假设我们要从a传送到c，那么这里a的距离向量是$D_a(b)=1,D_a(c)=4$，b的距离向量是$D_b(a)=1,D_b(c)=5$，c的距离向量是$D_c(a)=4,D_c(b)=5$

那么从a传送到c就最短就是4（$D_a(c)=\min{d_a(c)+d_a(a), d_a(b)+D_b(c)}=\min{4+0, 1+50}=5$）。

现在假设a到c的路径变成60了，那么假设a先检测到了路径开销变化，并更新自己到c的距离向量，是$D_a(c)=\min{D_a(a)+D_a(c), D_a(b)+D_b(c)}=\min{0+60, 1+5}=6$，显然是错误的计算结果，但是节点a会认为他是对的。

然后现在a要发送分组给c，它会先将分组发给b。由于b还没有更新距离向量，所以b又会将分组还给c（他认为最短路径是b->a->c），一次往返，形成循环。

这个过程会增加分组传送时间。解决的办法是毒性逆传，意思是当a发现从b来的分组的下一跳还是b的话，就告诉b从a到b的距离是无穷大，这样再将分组传回b之后b就不会再往a传了。

可惜的是毒性逆传并不能解决大于三个顶点的环路情况。这也是DV算法的缺陷。

updatedupdated2023-06-082023-06-08