路由与转发
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)
网友评论