路由与转发

image.png

网络抽象：图

图.png

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

图抽象：费用（Costs)

c(x,x') = 链路(x,x')的费用。
例如：c(u,v)=2
费用也可能是其他含义：带宽的倒数、拥塞程度等。
费用通常是越小越好。

关键问题：源到目的最小费用路径？

路由算法分类

• 静态路由
  -- 手工配置、路由更新慢、优先级高
• 动态路由
  -- 路由更新快、定期更新、及时响应链路费用或网络拓扑变化

全局信息 vs 分散信息

• 全局信息：
    所有路由器掌握完整的网络拓扑和链路费用信息
    例如：链路状态路由算法（LS)
• 分散信息：
    路由器只掌握物理相连的网络拓扑和链路费用信息
    例如：距离向量路由算法（DV)