计算机网络网络层03

路由算法

路由与转发

路由算法（协议）确定去往目的网络的最佳路径
转发表确定在本路由器如何转发分组

路由算法确定转发表。

网络抽象-图

G = (N, E)
N = 路由器的集合 = {u, v, w, x, y, z}
E = 链路的集合 = {(u, v), (u, x), (v, x), (v, w), (x, w), (x, y), (w, y), (w, z), (y, z)}

图的抽象在网络领域应用很广泛。

费用/权值/代价/距离 - costs

c(w, z) = 5，有些网络抽象中每段链路的费用可以总是1（跳步数），或者可以用带宽的倒数、拥塞程度甚至金钱等来衡量，越小越好。

路径费用

路径费用=每段链路费用之和。

关键问题：源到目的的最小费用路径是什么？最短路径问题
路由算法就是寻找最小费用路径的算法。，比如导航软件堵车时提供的多条路径。

路由算法分类

静态路由 vs 动态路由

静态路由

手工配置
路由更新慢
优先级高（反映了人类的智慧，一般优先级高）

动态路由

路由更新快
定期更新
及时响应链路费用或者网络拓扑变化

全局信息 vs 分散信息

全局信息

所有路由器掌握完整的网络拓扑（全图）和链路费用信息
链路状态（LS）路由算法

分散（decentralized）信息

路由器只掌握物理相连的邻居以及链路费用
邻居间信息交换、运算的迭代过程
距离向量（DV）路由算法

链路状态路由算法

Dijkstra 算法

所有结点（路由器）掌握网络拓扑和链路费用，即必须知道整个图的信息。

通过链路状态广播/范洪/扩散的方式，让每个结点掌握全图的状态，在这个过程中会采取某些措施防止网络风暴
所有结点拥有相同的信息
计算从一个结点（源）到达所有其他结点的最短路径，经过多次迭代获得该结点的转发表
迭代：k 次迭代后，得到到达 k 个目的结点的最短路径

符号

C(x, y): 结点 x 到结点 y 链路的费用，如果 x 和 y不直接相连，则为 inf
D(v): 从源到目的 v 的当前路径（不一定是最短路径）费用值（各节点费用之和）
p(v): 沿从源到 v 的当前路径，v 的前序结点
N': 已找到最小费用路径的结点集合

算法过程

以 u 结点为例，寻找到各个结点的最短路径过程，前提需要收集全局信息。

# 初始化
N' = {u} # u 到自己
for each node v:
    if v is neighbor u:
        D(v) = c(u, v)
    else:
        D(v) = inf

# Loop
# 找出不在 N' 中的 w，满足 D(w) 最小，将 w 加入 N'
# 更新 w 的所有不在 N' 中的邻居 v 的 D(v):
# D(v) = min(D(v), D(w) + c(w, v))
# 到达 v 的新费用 or 是原先到达 v 的费用，或者是已知的到达 w 的最短路径费用加上 w 到 v 的费用
# 直到 所有 结点 在 N' 中

略

复杂性

n 个结点

每次迭代需要检测所有不在集合 N’ 中的结点 w
n (n+1)/2 次比较：O(n^2)
更高效的实现 O(nlogn)

存在震荡oscillations可能

假设链路费用是该链路承载的通信量

比如，在第二个图中，B 向 A 发送数据报，当数据报到达 D 时，D 的路由路由信息发生变化，
如第三个图所示，会导致数据报 TTL 超时，永远到达不了 A。

距离向量 distance vector 路由算法

Bellman-Ford 方程（动态规划）
令：d(x->y) = 从 x 到 y 最短路径费用（距离）则：d(x->y)=min(c(x, v) + d(v->y))
c(x, v)为 x 到邻居 v 的费用；d(v->y)为从邻居 v 到达目的 y 的费用

略

层次化路由

将任意规模网络抽象为一个图计算路由，过于理想化，需要标识所有路由器，是一种扁平化网络，在实际网络（尤其是大规模网络）中不可行。

聚合路由器为一个区域自治系统 AS （autonomous systems），同一个 AS 内的路由器运行相同的路由协议（算法）。

自治系统内部路由协议（intra-AS routing protocol），不同自治系统内的路由器可以运行不同的 AS 内部路由协议。

网关路由器-gateway router：位于 AS 边缘，通过链路连接其他 AS 的网关路由器。

网络规模

考虑6亿目的结点的网络

路由表几乎无法存储
路由计算过程信息交换量巨大，会淹没链路

管理自治

每个网络的管理可能都期望自主控制其网内的路由
互联网（internet） = 网络之网络（network of networks）

自治系统间路由任务

假设 AS1 内某路由器收到一个目的地址在 AS1 之外的数据报，路由器应该将该数据报转发给哪个网关路由器呢？

AS1 必须学习到哪些目的网络可以通过 AS2 到达，哪些可以通过 AS3 到达，将这些网络可达信息传播给 AS1 内部路由器。

Dying Memory