路由选择算法——网络层

迈不过友情╰ 2023-05-30 09:03 8阅读 0赞

## 一、路由选择算法（routing algorithm） ##

#### 1、介绍 ####

路由选择算法十分重要，是最重要的 10 个十分重要的网络概念之一。

#### 2、目的 ####

**决定从源到目的地通过网络的”好的路径“**。通常一条好的路径指具有最低开销的路径。

#### 3、各种概念 ####

**（1）图（graph）**  
我们可以用图来描述路由选择问题。  
G = （N，E）  
其中 N 指节点，E指边，G是他们的集合。

选路算法的图论抽象:  
图中的节点是路由器  
图中的边是物理链路

*  链路代价: 时延，费用或拥塞等级

![在这里插入图片描述][20191108185909808.png]

**（2）开销**  
一条边还有一个值表示他的开销  
c（x，y）= n  
其中 x，y 表示两个节点，n 表示开销

**（3）路径**  
图 G = （N，E）中的一条路径（path）是一个节点序列（x1, x2, …, xp）  
开销总和是：c（x1，x2）+ c（x2，x3）+ … + c（xp-1，xp）  
通常节点之间有许多路径，每条路径都有一个开销。

**（4）最低开销路径/最短路径**

*  **最低开销路径（least-cost path）**：这些路径中一条或多条组合的路径开销最低。
 *  **最短路径（shortest path）**：若图中所有边具有相同的开销，则最低开销路径就是最短路径。

#### 4、选路算法分类 ####

**（1）按照分布来划分——最重要**

*  **集中式路由选择算法（centralized routing algorithm）**：**全局的**。每个路由器具有所有路由器具有完全的拓扑、链路开销信息。具有全局状态信息的算法被称作**链路状态算法（Link State，LS）**
 *  **分散式路由选择算法（centralized routing algorithm）**：**分散的**。路由器仅有与其直接相连链路的开销信息，然后通过迭代、分布式的方式与邻节点交换信息，最后计算出最低开销路径。这种也被称为**距离矢量算法（Distance-Vector，DV）**

**（2）按照动/静态来划分**

*  **静态路由选择算法（static routing algorithm）**：路由随时间变化非常缓慢，通常是人工进行调整（如：人工编辑一条链路开销）。
 *  **动态路由选择算法（dynamic routing algorithm）**：随着网络流量负载或拓扑发生变化而改变路由选择路径。

**（3）按照负载来划分**

*  **负载敏感算法（load-sensitive algorithm）**：链路开销会动态的变化反映出底层链路的当前拥塞水平。
 *  **负载迟钝（load-insensitive）**：不能明确反应拥塞水平。目前使用：RIP、OSPF、BGP。

## 二、链路状态路由选择算法 ##

#### 1、基本思想 ####

**（1）所有节点知道网络拓扑、链路费用**

*  经“链路状态广播”完成
 *  所有节点具有相同信息

**（2）从一个节点(源)到所有其他节点计算最低费用路径**

*  给出对这些节点的转发表

**（3）迭代: k次迭代后，得知到k个目的地的最低费用路径**

#### 2、基本概念 ####

**链路状态路由选择算法一般采用 Dijsktra 算法**  
（1）c(x,y)：从节点x到y的链路费用; = ∞ 如果不是直接邻居  
（2）D(v)：从源到目的地v路径费用的当前值  
（3）p(v)：从源到v沿路径的前任节点  
（4）N’：已知在最小费用路径中的节点集合

#### 3、Dijsktra 算法 ####

**（1）步骤**

1	初始化
    2		N' = {
        u} 
    3		对所有节点v: 
    4			if v 临近 u 
    5          		then D(v) = c(u,v) 
    6      		else D(v) = ∞ 
    7 
    8	Loop 循环 
    9		找出w不在N‘中使得D(w)最小 
    10    	将w加入N' 
    11    	对于所有v临近w并不在N’中，更新D(v): 
    12      	D(v) = min( D(v), D(w) + c(w,v) ) 
    13    		/* 到v的新费用或是到v的老费用或到w加上从w到v的已知最短路费用*/ 
    15	until 所有节点在 N‘中

**（2）例子**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

**算法复杂性: n个节点**  
每次迭代: 需要检查所有节点w, 不在N中

*  n(n+1)/2 对比: O(n2)
 *  更有效的实现是可能的: O(nlogn)

## 三、距离向量路由选择算法 ##

#### 1、基本思想 ####

（1）每个节点周期性的发送它自己的距离矢量估计到其邻居  
（2）当节点x接收到来自邻居的新DV估计，它使用B-F方程更新其自己的DV :

*  Dx(y) = minv\{c(x,v) + Dv(y) \} for each node y ∊ N

（3）在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y)

#### 2、基本概念 ####

**距离向量路由选择算法一般采用 Bellman-Ford算法**  
（1）c(x,v)：节点 x 到邻节点 v 的开销  
（2）dv(y)：邻节点 v 到目的地 y 的最小开销  
（3）dx(y)：邻节点 x 到目的地 y 的最小开销

**其中min对x的所有邻居**

#### 3、特点 ####

（1）迭代、异步: 每次本地迭代由下列引起:

*  本地链路费用改变
 *  DV从邻居更新报文

（2）分布式

*  每个节点仅当其DV改变时通知邻居
 *  如果必要，邻居则通知它们的邻居

（3）更新方式  
![在这里插入图片描述][20191108212921228.png]

#### 4、Bellman-Ford 算法 ####

**（1）定义**  
dx(y)：从x到y最低费用路径的费用  
dx(y) = minv\{c(x,v) + dv(y) \}

**（2）例子**  
![在这里插入图片描述][20191108212509699.png]

#### 5、链路故障和毒性逆转 ####

**（1）链路故障——形成环路**  
比如下图的例子  
某时刻 x<–>y 的开销由 4 变为 60，y 需要通知其他节点改变开销，但是 y 要首先改变与 x 的开销就要到达 x，通过算法 y 要经过 z 到达 x，但是 z 没有修改最短路径，告诉 y 到达 x 只需要 5，结果 y 到 z 然后返回 y，距离由 5 变为 6，但是还是小于 60，一直由 5 增长到大于 50 才结束。**需要迭代 44 次。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

**（2）毒性逆转**

*  办法：定义 dz(x) = ∞，y 开始直接会选择 60 到 x，更新后修改完善转发表。
 *  只能解决两个节点之间的问题，一旦节点多了同样不能解决问题。

## 四、LS和DV算法的比较 ##

#### 1、报文复杂性 ####

**（1）LS：对n个节点，E条链路, 发送O(nE) 报文**  
**（2）DV：仅在邻居之间交换**

*  收敛时间变化

#### 2、收敛速度 ####

**（1）LS：O(n2) 算法要求 O(nE)报文**

*  可能具有振荡

**（2）DV：收敛时间变化**

*  可能有选路环路
 *  计数到无穷问题

#### 3、健壮性: 如果路由器异常，将发生什么现象? ####

**（1）LS**

*  节点可能通告不正确的链路费用
 *  每个节点仅计算它自己的表

**（2）DV**

*  DV节点通告不正确的路径费用
 *  每个节点表能由其他人使用
 *  差错通过网络传播

[20191108185909808.png]: https://img-blog.csdnimg.cn/20191108185909808.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191108203645336.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[20191108212921228.png]: https://img-blog.csdnimg.cn/20191108212921228.png
[20191108212509699.png]: https://img-blog.csdnimg.cn/20191108212509699.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191108213455578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70