到达信宿40.0.0.0的路由变化 的路由变化 到达信宿
时间 初始
40.0.0.0
断开
第 1步 第 2步 …
A 2 2 2 4
B 1 1 3 3
C 0 2 2 4
刷新 信宿可达
B C B B C， 1+1=2 ， B， 2+1=3 ， C， 3+1=4 ， A， 3+1=4 ，
这条错误的路由信息在C与 之间不断复制和修改 之间不断复制和修改， 这条错误的路由信息在 与B之间不断复制和修改， 并在网络中传播（殃及A），形成路径传播的环路。 ），形成路径传播的环路 并在网络中传播（殃及 ），形成路径传播的环路。
– 对所有自治系统以外的信宿都采用缺省路径 – 简化路由计算，提高寻径效率，缩短表长 简化路由计算，提高寻径效率，
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
缺省路径举例
Default Rd e0 e0 Rd f0 Default Ra b0 Rb b0 Ra Rc c0 Default Ra c0
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
静态路由的概念
• 由网络管理员设置路由表 • 简单、有效，适于结构简单的网络 简单、有效， • 不适于拓扑结构和传输流量经常改变的 复杂网络
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
• 维护各自的路由表
– 路由器根据邻居发送的距离—向量的动态信息启动算法，更 路由器根据邻居发送的距离 向量的动态信息启动算法， 向量的动态信息启动算法 新路由表
D A B C A
路由表
B
路由表
C
路由表
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
路由技术
• 确定路由算法
– 设计目标 – 选择类型 – 定义最佳路径的度量准则
• 实现路由协议
– 路由传输协议（Routed Protocol） 路由传输协议（ ）
• 网间经路由被传输的协议：IP，OSI，Netware 网间经路由被传输的协议： ， ，
– 路由选择协议（Routing Protocol） 路由选择协议（ ）
1）缺省路径（Default Route） ）缺省路径（ ）
• 什么是缺省路径？ 什么是缺省路径？
– 对那些在路由表中未包含其路由选择信息的 信宿（网络/主机 主机） 信宿（网络/主机）设定的缺省路径 – 在路由表中信宿地址取值 在路由表中信宿地址取值0.0.0.0(Default)
• 缺省路径的作用
网络C 网络 c1 b2 b3 Rb b1 网络B 网络
?
c3 a3 Ra a2
Rc c2
a1 网络A 网络
?
Rb路由表 路由表 网络A Ra b3 网络 网络C Rc b2 网络
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
解决办法： 解决办法：人工修改
• 问题
– 逐站传递更新信息，算法的收敛速度慢 逐站传递更新信息， – 有可能出现各站路由信息不一致
• 后果
– 在站点间构成更新路由的路径环（Routing Loops） 在站点间构成更新路由的路径环 路径环（ ） – 计数至无穷大（Count to Infinity） 计数至无穷大（ ）
• 解决办法
a3 a1 网络A 网络 Ra a2
b2 Rb b1 网络B 网络
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
链路发生故障
Ra路由表 路由表 网络B Rb a2 网络 网络C Rc a3 网络 Rc路由表 路由表 网络B Rb 网络 网络A Ra 网络 c2 c3
20122012-4-21
‹#›
D-V发现链路断开 发现链路断开
A 1 B 1 C
r
40.0.0.0 down
C与B之间的对话： 与 之间的对话 之间的对话： C 我得不到信宿 我得不到信宿40.0.0.0的任何路由信息，你能告诉我如何到达信宿吗？ 的任何路由信息， 的任何路由信息 你能告诉我如何到达信宿吗？ B 我可以到达信宿，距离为 。（传播了一条过时的错误信息） 我可以到达信宿，距离为1。 传播了一条过时的错误信息） C 既然如此，我选择经过你到达信宿的路径，距离为 。 既然如此，我选择经过你到达信宿的路径，距离为2。
20122012-4-21
‹#›
静态路由举例
Rc路由表 路由表 网络B Rb 网络 网络A Ra 网络 Ra路由表 路由表 网络B Rb a2 网络 网络C Rc a3 网络 c2 c3
网络C 网络 c3 Rc c1 c2 b3
Rb路由表 路由表 网络A Ra b3 网络 网络C Rc b2 网络
B 7 A 1 E 2 D
20122012-4-21
1
最小代价D 最小代价 (des,nei)
E的路由表 的路由表
信宿 （D,V） ） 到A 到B 到C 到D 1,A 5, 从 D 0 7 5 3 7 0 1 3 3 3 2 0
8
2
到 C 到 D
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
– 定义路径代价的最大值（Maximum） 定义路径代价的最大值（ ） – 提高收敛速度
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
路径环（ 路径环（Routing Loop）问题 ）
A 1 B 1 C
r
40.0.0.0 down
• • • • •
可靠性 延迟 带宽 负载 通信代价
链路数据传输的可靠性（误码率） 链路数据传输的可靠性（误码率） 数据包从源到宿需要花费的传输时间 链路的最大传输能力以及网络流量 网络资源（例如路由器的CPU）的使用率 网络资源（例如路由器的 ） 占用通信线路的费用
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
2）选择最佳路由的度量参数 ）
• 路径长度
– 由网络管理员定义每条网络链路的代价（cost），从源到宿的 由网络管理员定义每条网络链路的代价（ ），从源到宿的 ）， 代价总和为路径长度。 代价总和为路径长度。 – 以路径中的站点（hop）为单位，从源到宿的站点数之和为路 以路径中的站点（ ）为单位， 径长度。 径长度。
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
距离向量算法的基本概念
• 周期性地相互传递信息
– 每个路由器向与它相邻的站点发送一个包含它到所有其他路 每个路由器向与它相邻的站点 相邻的站点发送一个包含它到所有其他路 由器的距离的向量（最短路径或最小代价） 由器的距离的向量（最短路径或最小代价）
20122012-4-21
‹#›
1）路由算法的设计目标 ）
• • • • 优化： 优化：根据一定的优化准则选择最佳路径的能力 简单：利用最少的物理资源、 简单：利用最少的物理资源、提供最有效的功能 稳定：经受得住各种恶劣环境的考验， 稳定：经受得住各种恶劣环境的考验，故障率低 收敛：跟随路由更新信息变化重新计算， 收敛：跟随路由更新信息变化重新计算，快速取 得全网一致的最佳路由 • 灵活：快速、准确地适应各种网络环境和变化 灵活：快速、
C B, 0+1=1 B A, 1+1=2
如果网络中的最长路径为N，则算法经过 次迭代计算后 如果网络中的最长路径为 ，则算法经过N次迭代计算后 收敛。即第N步之后 步之后， 收敛。即第 步之后，网上的所有路由器都获得到达信宿 40.0.0.0的路由信息。 的路由信息。 的路由信息
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
到达信宿40.0.0.0的路由变化 的路由变化 到达信宿
时间 初始
40.0.0.0 断开
A 2 2
B 1 1
C 0 2
刷新 信宿可达
B C，1+1=2 ，
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
距离向量法的收敛性问题及解决办法
Ra路由表 路由表 ！ 网络 Rc 网络B a3 网络C Rc a3 网络 Rc路由表 路由表 网络B Rb 网络 网络A Ra 网络
不适于网络变化！ 不适于网络变化！
c2 c3
网络C 网络 c1
a3 a1 网络A 网络 Ra a2
c3 Rc
c2 b3
b2 Rb b1 网络B 网络
Rb路由表 路由表 网络A b2 ！ 网络 Rc 网络C Rc b2 网络
‹#›
D-V路由选择算法举例
网络与分布式系统研究室(DisNet Lab of NWU) 网络与分布式系统研究室
20122012-4-21
‹#›
距离向量法的计算举例 距离向量法的计算举例
• 计算从 经相邻站点A、B和D到达信宿 、B、 计算从E经相邻站点 、 和 到达信宿 到达信宿A、 、 经相邻站点 C和D的最小代价 (destination,neighbor) 的最小代价D 和 的最小代价 • 得从 到达信宿的最佳路径（最小代价）路由表 得从E到达信宿的最佳路径 最小代价） 到达信宿的最佳路径（