7
A
1
B 1C
8
2
E2D
DE(A,D) = c(E,D) +DD(A, w) = 2+3 = 5
DE(A,B)＝14 ？
Cost to destination via
DE() A B D
A 1 14 5 B 785 C 694 D 4 11 2
Байду номын сангаас
2.DV算法
主要数据结构：每个节点维护的距离表(distance table)。 •一个节点能得到的信息
与其直接相连链路的成本 来自邻接节点。
• DV算法 估算的延迟作为性能指标 Bellman-Ford算法的一个版本
Bellman-Ford算法： 已用于BGP、ISO的IDRP、Novell IPX和最早的ARPAnet
Distance Vector (DV) Algorithm. At each node, X:
Cost via DY X Z X 28 Z 91
Cost via DZ X Y X 73 Y 91
Cost via DX Y Z Y 28 Z 37
Cost via DX Y Z Y 24 Z 51
Cost via DX Y Z Y 73 Z 91
3.相关问题
• DV算法：链路成本变化及链路故障
包交换网络中的路由技术元素
性能标准
网络信息源
网络信息更新时间
跳计数 成本 延迟 吞吐量
None Local Adjacent node All nodes
连续 定期 主负载变化 拓扑变化
决策时间
包（数据报） 会晤（虚电路）
决策地点
每个节点（分布） 中心节点（集中） 原始节点（源）
3.性能标准
最小跳计数(minimum-hop)标准：
(, -)
(2,A)
B (4,B)
A
E
G (6,A)
(2,A)
B
(4,B)
A
E
G (5,E)
(9,B)
C
选择当前工作节点B
F (, -) D (, -)
H
标值其他节点到源的距离
(, -)
(9,B)
C
选择当前工作节点E
F (6,E) D (, -)
H
标值其他节点到源的距离
(, -)
(2,A)
B (4,B)
•无信息(扩散法) 无更新之说
•局部信息 更新基本上是连续的。
•其他信息源(邻接节点，全部节点)
固定策略
自适应策略
从不更新信息
不时更新信息
二.静态路由算法
1.最短路由选择
•测量路径长度的方法
最小跳计数 最短距离 信道带宽 传输延迟 平均通信量
子网图：节点代表路由器； 弧线代表两个路由器之间的一条链路;
• Dijkstra算法 找出一个节点到所有其他节点的最短路径.
例：使用Dijkstra算法计算AD的最短路经
B
7
22
A
E2
6
14
G
C
3
3
F
D
22
H
测量每一条链路的长度 初试化
(2,A)
B
(, -)
A
E
(, -)
C
选择当前工作节点A
F (, -) D (, -)
G
H
标值其他节点到源的距离
(6,A)
集中式路由 源路由
为每个包单独作路由决策
当建立虚电路时作路由决策
每个节点都负责为到达 的包选择一条输出链路 由某些指定节点(如网络 控制中心)负责决策 路由决策实际上由源 站点而非网络作出。
5.网络信息源和更新时间
大多数路由决策要求根据网络拓扑、交通负载和链 路成本等知识作出决定。
信息更新时间：这是信息源和路由决策的函数
Y
的
Cost via
Cost via
距 离
DY
X
Z
DY X Z
DY
表X 46
X 16
X
1 4
X
Cost via
XZ
16
Y 1 Z
50
Cost via DY X Z
X 13
Z 的 距
DZ
Cost via
XY
离 表
X
50 5
Cost via DZ X Y X 50 5
C(X, Y)
time
changed
迭代的(iterative)
计算过程循环进行，直到相邻 节点没有可交换的信息为止。
异步的(asynchronous)
并不要求所有节点相互锁步操作。
考虑X经直接邻居Z到达Y。
设：Dx(Y, Z)：为X经邻接节点Z到达y的距离
Dx(Y,Z) = c(X, Z) + minw{Dz(Y, w)}
(1)
其中w为Z的所有直接邻居(包括X)
•自适应路由的前提：节点间交换网络状态信息
•缺点
路由决策复杂 依赖于状态信息 不能太快和太慢
加重网络节点的处理负担 加重网络的交通负担
•优点
可提高网络性能 有助于拥塞控制
2.路由算法的特性
•正确性(correctness) •简单性(simplicity) •健壮性(robustness) •稳定性(stability) •最优性(optimality) •公平性(fairness) •有效性(efficiency)
X 4 X 60 X 60 X 60 51 X 60 51
Cost via
Cost via
Cost via
Cost via
Cost via
DZ X Y DZ X Y DZ X Y DZ X Y DZ X Y
X 50 5 X 50 5 X 50 61 X 50 61 X 50
C(X, Y)
time
changed
t0
t1
t2
t3
t4
水平分裂法的失败情况
1
A
1
C
A通知C到D的距离为；
B
B通知C到D的距离为；
1 当C-D链路失效后，C到D不可达；
1
A选择经过B到D且距离为3；
D
B选择经过A到D且距离为3；
A 、B相互交换最短距离直到无穷大。
四. 链路状态路由
基本思想：
•采用延迟作为性能标准； •每个节点为每条链路维护一个近似的延迟； •节点每10秒计算每条出境链路的平均延迟； •如有重大变化，则采用扩散法通知其他节点； •每当接收到来自其他节点的信息时，用Dijkstra 算法重新计算路由表。
算法的操作是同步进行的，所有节点同时接收来自邻 居的消息，计算新距离表条目；如有变化通知邻居。
• DV算法实例
初始化
Y
最左列为x, y, z初始化后的距离表
2
1
X收到来自y, z的更新信息
后，重新计算距离表
X
7
Z
收到Z的消息后： Dx(y, z) = C(x, z) + minwDz(y, w) = 8
1 Initialization: 2 for all adjacent nodes v: 3 DX(*,v) = 4 DX(v,v) = c(X,v) 5 for all destinations, y 6 send minwD(y,w) to each neighbor
/* w over all X's neighbors */ 7
2
3
6
1
4
5
2
3
1
4
5
6 (c)节点2、3、4、 5在所有出境线路 发送包
三. 距离向量算法(DV, distance vector routing)
1. 基本思想
•DV算法的特点 分布的(distributed)
每个节点接收来自与其直接邻接 节点的信息执行路由计算；将计 算结果回传给直接邻接的节点。
一. 路由选择概述
B的内部结构
C
A
D
B
Routing table
Network layer switching/routing
B-A data ink
B-A physical
B-C data link
B-C physical
B-D data link
B-D physical
关键问题
谁确定路由表？ 用什么信息确定路由表项？ 何时修改路由表项？ 何地存放路由信息？ 如何控制路由表大小？ 为什么路由表能确定一条路径？
15 for all destinations y: DX(y,V) = DX(y,V) + d 16 17 else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its minw DV(Y,w) */ 20 /* call this received new value is "newval" */ 21 for the single destination y: DX(Y,V) = c(X,V) + newval 22 23 if we have a new minw DX(Y,w)for any destination Y 24 send new value of minw DX(Y,w) to all neighbors 25 26 forever
X 4 6 X 60 6 X 60 6 X 60 8 X 60 8