首发于 计算机网络笔记
切换模式
网络层 | 路由算法
晒月亮的孩子
Silicon to Software
路由，前向转发的相互作用
路由和转发的结合是在前向转发表。
Graph抽象
Graph抽象：费用（costs）
路由算法分类
全局和分布式选路算法
分布式的算法也叫做距离矢量算法。
静态和动态
链路状态选路算法（LS算法）
Dijkstra's 算法举例
Dijkstra's 算法讨论
距离矢量算法（DV算法）
这是一个迭代的异步的分布式的（局部）算法。
分布式：每一个节点都要从一个或者多个直接相邻的邻居节点那获得信息并将计算结果发回给邻居。
迭代：这个过程要一直重复到邻居之间没有可以交换的信息为止。
异步：不要求所有的节点，同步的交换链路状态信息。
dx(y)是假设存在的最小开销路径，要等算法执行后才能真正确定。
其算法的基本思想如下：
Bellman-Ford等式例子
距离矢量算法演算过程
距离矢量：链路费用变化
当 c(y,x) 变为 60 的时候，Dz(x) = 5，所以更新 Dy(x) 等于6，由于 Dz(x) 是通过 y 到达的 x，所以 Dz(x) 接着 Dy(x) 更新为7， Dy(x) = c(y,z) + Dz(x) = 8，接着反复更新44次，最后停止到 Dy(x) = 51， Dz(x) = 50。
使用该方法可以比较好的解决毒性逆转的问题。
LS 和 DV 算法比较
层次路由
之前的LS算法和DV算法进行分析的时候都是使用的理想化的网络环境
- 所有路由平等
- 网络是扁平的
与真实网络环境有区别。
目前的网络大约有 600 million 的目的网络。路由表不可能存储所有网路，路由交换的信息可能瘫痪网络。
解决这个问题的方法有：
在自治系统内部运行的选路算法成为 intra-AS 选路协议。
自治系统中负责向本AS之外的目的地转发分组的路由器叫做网关路由。
互联的ASes
图中的粗线条表示路由器之间的连接，细线条表示路由器连接的子网。
路由器 1a,1b,1c,1d 运行在 AS1 内部，选用AS1内部选入协议。这四个路由可以实现内部的最优选路。同样的AS2，AS3内部的路由也可以实现内部的最优选路。但AS1，AS2，AS3它们内部的网关协议没有必要是一样的。
其中的 1b, 2a 就属于网关路由。
Inter-AS 任务
网关路由接收到其他的自治系统的分组之后就需要向前转发。
举例：路由器 1d 前向转发表的设置
举例：在多个 AS 中选择
编辑于 2017-12-25 22:42
计算机网络
文章被以下专栏收录
