第十四章 矩形波导中的简正波.ppt

第14讲网络层之二
路由选择算法
一. 路由选择概述
Routing table
Network layer switching/routing
C
A
B
D
B的内部结构
B-A
data ink
B-C
data link
B-D
data link
B-A
physical
B-C
physical
B-D
physical
谁确定路由表?
用什么信息确定路由表项?
何时修改路由表项?
何地存放路由信息?
如何控制路由表大小?
为什么路由表能确定一条路径?
关键问题
who
what
when
where
how
why

给定一组路由器及连接路由器的链路,找出一条从源到目标的“好”路径。
非自适应算法
不根据实测或估计的网篮的当前通信量和拓扑结构来作路由选择。
静态路由
自适应算法
根据拓扑结构、通信量的变化来改变其路由选择。
动态路由
自适应路由的前提:节点间交换网络状态信息
路由决策复杂
依赖于状态信息
不能太快和太慢
可提高网络性能
有助于拥塞控制
缺点
优点
加重网络节点的处理负担
加重网络的交通负担

正确性(correctness)
简单性(simplicity)
健壮性(robustness)
稳定性(stability)
最优性(optimality)
公平性(fairness)
有效性(efficiency)
包交换网络中的路由技术元素
性能标准网络信息源网络信息更新时间
跳计数
成本
延迟
吞吐量
None
Local
Adjacent node
All nodes
连续
定期
主负载变化
拓扑变化
决策时间决策地点
包(数据报)
会晤(虚电路)
每个节点(分布)
中心节点(集中)
原始节点(源)

最小跳计数(minimum-hop)标准:
1
2
3
4
5
6
2
2
2
2
1
1
1
1
1
5
8
4
3
6
7
8
5
最短路径:1-3-6
成本:10
成本与数据率有关(数据率越高,成本越低)
成本与当前排队延迟有关
3
3
3
通常为最小成本(least-cost)路由
最小成本路径:1-4-5-6
成本:4;

决策时间
内部数据报
决策地点
分布式路由
为每个包单独作路由决策
当建立虚电路时作路由决策
每个节点都负责为到达的包选择一条输出链路
由某些指定节点(如网络控制中心)负责决策
路由决策实际上由源站点而非网络作出。
内部虚电路
集中式路由
源路由

大多数路由决策要求根据网络拓扑、交通负载和链路成本等知识作出决定。
信息更新时间:这是信息源和路由决策的函数
无信息(扩散法)
其他信息源(邻接节点,全部节点)
局部信息
无更新之说
更新基本上是连续的。
固定策略
自适应策略
从不更新信息
不时更新信息

测量路径长度的方法
最小跳计数
最短距离
信道带宽
传输延迟
平均通信量
子网图:节点代表路由器;
弧线代表两个路由器之间的一条链路;
 Dijkstra算法
找出一个节点到所有其他节点的最短路径.