CN-路由和转发

[[CN-NotesView]]

路由与转发

路由算法（协议）确定去往目的网络的最佳路径

转发表确定在本路由器如何转发分组

网络抽象：图

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

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

N是peers集合，E是TCP的集合

图抽象：费用（Costs）

c(x,x’)链路(x,x’)的费用

e.g c(w,z) = 5

每段链路的费用可以总是1，描述一个链路或者路径的大小的时候称为段数；或者是，带宽的倒数、拥塞程度等。

路径费用：(x1,x2,x3,,,xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

[!关键问题]
源到目的的最小费用的路径是什么？

路由算法：在网络的抽象图中寻找最小路径的算法

路由算法分类

静态路由 vs 动态路由？

静态路由：

• 手工配置

• 路由更新的速度慢

• 优先级高（在路由信息中同等条件下首选）

动态路由：

• 路由更新快

  • 定期更新

  • 及时响应链路费用或者网络拓扑变化

全局信息 vs 分散信息？

全局信息：所有路由器掌握完整的网络拓扑和链路费用信息

e.g. 链路状态(LS)路由算法

分散信息（decentralized）:

路由器只掌握物理项链的邻居以及链路费用

链路之间信息交换、运算的迭代过程

e.g. 距离向量9(DV)路由算法