网络和现代通信技术基础 —— 网络层网络和现代通信技术基础 —— 网络层第 5章 网络层本章学习目标
了解广域网的概念及网络层的基本功能
掌握广域网提供的两种类型的服务：数据报
（ Datagram） 和虚电路 （ Virtual Circuit）
掌握路由选择机制,路由选择算法
了解拥塞控制原理及拥塞控制策略网络和现代通信技术基础 —— 网络层第 5章 网络层
5.1 网络层所涉及的有关问题广域网的概念
iMac
iMac
iMac
iMac
iMac
WAN 2
WAN 4
WAN 3WAN 1
网络和现代通信技术基础 —— 网络层上图所示的广域网中,云图中及云图相连的部分称之为通信子网,以外的部分为资源子网 。 通信子网提供的是数据传输服务,
它实现 OSI体系结构中的底三层,即物理层,数据链路层和网络层 。
5.1 网络层所涉及的有关问题网络和现代通信技术基础 —— 网络层网络层提供的服务
无连接的网络服务 — 数据报服务；
面向连接的网络服务 — 虚电路服务 。
1,数据报服务（ Datagram）,主机只要想发送数据就随时可发送，每个分组独立地选择路由。
2,虚电路服务（ Virtual circuit）：通信前主机要先建立一条虚电路，之后数据沿固定路由传送，通信后拆除虚电路。
5.1 网络层所涉及的有关问题网络和现代通信技术基础 —— 网络层
5.1 网络层所涉及的有关问题
（ a）数据报服务 （ b）虚电路服务网络和现代通信技术基础 —— 网络层数据报和虚的电路比较：
项目 数据报 虚电路建立连接 不需要 需要寻址方式 每个分组都有源端和目的端的全地址在连接建立阶段使用目的端地址,
分组使用短的虚电路号路由选择 每个分组独立选择路由 在虚电路建立时进行,之后所有分组均按同一路由结点失败的影响出故障的路由器可能会丢失分组,一些路由可能会发生变化所有经过出故障的路由器的虚电路均不能工作分组的顺序 不一定按发送顺序到达目的站总是按发送顺序到达目的站端到端的差错处理由主机负责 由通信子网负责端到端的流量控制由主机负责 由通信子网负责拥塞控制 难 如果有足够的缓冲区分配给已经建立的每一条虚电路,则容易控制网络和现代通信技术基础 —— 网络层
5.2 路由选择机制节点交换机中的路由表交换机 3
交换机 1
交换机 2
交换机 2
路由表
[2,1] [2,2]
[1,1]
[1,3]
[3,1]
[3,3]
目的站
[1,1] 交换机 1
[1,3 交换机 1
[3,1] 交换机 3
[3,3] 交换机 3
[2,1] 本交换机
[2,2] 本交换机下一站
1 3
2
计算机的编址和网络层节点交换机的路由表网络和现代通信技术基础 —— 网络层目的站 下一站
1 交换机 1
3 交换机 3
2 本交换机路由表的简化
5.2 路由选择机制网络和现代通信技术基础 —— 网络层路由选择的一般原理
1,理想的路由算法,
算法必须是正确的和完整的 。
算法在计算上应简单 。
算法应能适应通信量和网络拓扑的变化 。
算法应具有稳定性 。
算法应是公平的 。
算法应是最佳的 。
5.2 路由选择机制网络和现代通信技术基础 —— 网络层
2,路由算法的分类非自适应路由选择策略自适应路由选择策略
（ 1） 非自适应路由选择,固定路由算法,分散通信量法,洪泛法,随机走动法
（２）自适应路由选择,分布式路由选择策略,集中式路由选择策略,
混合式路由选择策略
5.2 路由选择机制路由选择的一般原理网络和现代通信技术基础 —— 网络层固定路由算法,
Dijkstra算法 --最短距离 (最小代价 )算法,
① 初始化处理,定义数组 N,它只包含源节点 S,N＝ ｛ S｝,并定义距离 D (V)= L(S,V),V为非源节点中的一个,该距离为节点 V到源节点 S的链路长度 。 于是有
D(V) = L(S,V)；若 V与 S直接相邻
D(V) = ∞ ；若 V与 S不直接相邻
② 不断求得 N以外的各节点 F,使距离 D(F)最小,并将节点 F加入原来的数组,对 N以外的各节点,按式,D(V) = min [D(V),D(F)+L(F，
V)] 更新距离 D(V),当 D(F)+L(F,V)<D(V) 时,则以 D(F)+L(F,V)
取代原 D(V),否则维持原值不变 。 这一过程重复至所有节点均包含在数组 N内为止 。
5.2 路由选择机制非自适应路由选择网络和现代通信技术基础 —— 网络层固定路由算法,
Dijkstra算法 --最短距离 (最小代价 )算法,
5.2 路由选择机制非自适应路由选择网络和现代通信技术基础 —— 网络层分散通信量法,
5.2 路由选择机制非自适应路由选择目的站经过概率经过概率经过概率
A M 0.50 L 0.40 N 0.10
B M 0.50 N 0.20 L 0.30
C N 0.65 M 0.25 P 0.10
D N 0.55 P 0.30 M 0.15
E P 0.45 N 0.30 M 0.25
… … … …
A B C
DM N
E
P
G
L
节点 G中的路由表网络和现代通信技术基础 —— 网络层洪泛法,
这种方法是当某个节点收到一个不是发给它的分组时,就向所有与此节点相连的链路转发出去 。
随机走动法,
这种方法又称为随机徘徊,其特点是当分组到达某个节点时就随机地选择一条链路作为转发的路由 。
5.2 路由选择机制非自适应路由选择网络和现代通信技术基础 —— 网络层距离向量算法,
5.2 路由选择机制自适应路由选择距离向量路由选择 ( Distance Vector Routing ) 协议中,所有的 IMP
都定期地将它们的整个路由选择表传送给所有与之直接邻接的 IMP。
这种路由选择表包含：
l 每条路径的目的地 (另一 IMP)
l 路径的代价 (也称距离 )
网络和现代通信技术基础 —— 网络层距离向量算法,
5.2 路由选择机制自适应路由选择
0 24 20 21
12 36 31 28
25 18 19 36
40 27 8 24
14 7 30 22
23 20 19 40
18 31 6 31
17 20 0 19
21 0 14 22
9 11 7 10
24 22 22 0
29 33 9 9
A
B
C
D
E
F
G
H
I
J
K
L
TO A I H K
延迟 延迟 延迟 延迟是 8 是 10 是 12 是 6
从 J的四个邻居收到的向量
8 A
20 A
28 I
20 H
17 I
30 I
18 H
12 H
10 I
0 -
6 K
15 K
新估计的从
J的延时线路
J的新路由表路由器 J从其邻居收到距离向量表后计算自己的向量表网络和现代通信技术基础 —— 网络层链路状态 (Link State)算法,
5.2 路由选择机制自适应路由选择在一个链路状态路由选择协议中,一个 IMP检查所有直接链路的状态,并将所得的状态信息发送给网上所有其他的 IMP。 而不是仅仅送给那些直接相连的节点 。
以这种方式,每个 IMP从网上所有其他的 IMP接收包含直接链路状态的路由选择信息 。
每当链路状态报文到达时,路由节点 (IMP)便使用这些状态信息去更新自己的网络拓扑和状态,视野图,,把各个链路标为,Up”或,Down”。 一旦链路状态发生了变化,IMP对更新了的网络图利用 Dijkstra最短通路搜索算法更新计算路由 。
网络和现代通信技术基础 —— 网络层链路状态 (Link State)算法,
5.2 路由选择机制自适应路由选择链路状态路由选择协议的操作过程：
l 发现它的邻居节点,并知道其网络地址 。
l 测量到各邻居节点的延迟或代价
l 组装一个分组,以通告它刚获悉的信息 。
l 把这个分组发送给所有其他路由器 。
l 计算到其他每个路由器的最短路径 。
网络和现代通信技术基础 —— 网络层
5.2 路由选择机制自适应路由选择集中式路由选择策略集中式路由选择策略的核心是网控中心 NCC。 NCC负责全网状态信息的收集,路由计算以及路由选择的实现 。 集中式路由选择策略也有多种,
这取决于储存在 NCC中的网络信息的类型,路由的计算方法以及路由选择实现的技术 。
网络和现代通信技术基础 —— 网络层
5.2 路由选择机制自适应路由选择混合式路由选择策略为了克服集中式路由选择的缺点,可以同时综合使用几种路由选择策略 。
网络和现代通信技术基础 —— 网络层
5.3.1 拥塞控制的概念当（一部分）通信子网中有太多的分组时，其性能降低。这种情况叫做拥塞。造成拥塞有若干因素。如果突然之间，分组流同时从 3个或 4个输入线到达，并且要求输出到同一线路，
就将建立起队列。如果没有足够的空间来保存这些分组，有些分组就会丢失。处理器速度慢也能导致拥塞。拥塞会导致恶性循环。如果路由器没有空余缓冲区，它必须丢掉新到来的分组。拥塞控制和流量控制既有联系又有差异
5.3 拥塞控制网络和现代通信技术基础 —— 网络层
5.3.2 拥塞控制的基本原理所有解决方案被分为两类,一类是开环,一类是闭环 。 开环控制工具的功能包括决定何时接受新的通信,何时丢弃分组,以及丢弃哪些分组,还包括在网络的不同点作计划表 。 所有这些的共同之处在于,它们在做出决定时并不考虑当前网络的状况 。
与之相比较,闭环的解决方案是建立在反馈环路的概念之上的 。 当用于拥塞控制时,这种方法有 3个部分：
监视系统,检测何时何地发生了拥塞 。
将此信息传送到可能采取行动的地方 。
调整系统操作以更正问题 。
5.3 拥塞控制网络和现代通信技术基础 —— 网络层
5.3.3 拥塞预防策略层 次 策 略传输层?重发策略
乱序缓存策略
确认策略
流量控制策略
超时终止网络层?子网内的虚电路与数据报
分组排队和服务策略
分组丢弃策略
路由选择算法
分组生命期管理数据链路层?重发策略
乱序缓存策略
确认策略
流量控制策略
了解广域网的概念及网络层的基本功能
掌握广域网提供的两种类型的服务：数据报
（ Datagram） 和虚电路 （ Virtual Circuit）
掌握路由选择机制,路由选择算法
了解拥塞控制原理及拥塞控制策略网络和现代通信技术基础 —— 网络层第 5章 网络层
5.1 网络层所涉及的有关问题广域网的概念
iMac
iMac
iMac
iMac
iMac
WAN 2
WAN 4
WAN 3WAN 1
网络和现代通信技术基础 —— 网络层上图所示的广域网中,云图中及云图相连的部分称之为通信子网,以外的部分为资源子网 。 通信子网提供的是数据传输服务,
它实现 OSI体系结构中的底三层,即物理层,数据链路层和网络层 。
5.1 网络层所涉及的有关问题网络和现代通信技术基础 —— 网络层网络层提供的服务
无连接的网络服务 — 数据报服务；
面向连接的网络服务 — 虚电路服务 。
1,数据报服务（ Datagram）,主机只要想发送数据就随时可发送，每个分组独立地选择路由。
2,虚电路服务（ Virtual circuit）：通信前主机要先建立一条虚电路，之后数据沿固定路由传送，通信后拆除虚电路。
5.1 网络层所涉及的有关问题网络和现代通信技术基础 —— 网络层
5.1 网络层所涉及的有关问题
（ a）数据报服务 （ b）虚电路服务网络和现代通信技术基础 —— 网络层数据报和虚的电路比较：
项目 数据报 虚电路建立连接 不需要 需要寻址方式 每个分组都有源端和目的端的全地址在连接建立阶段使用目的端地址,
分组使用短的虚电路号路由选择 每个分组独立选择路由 在虚电路建立时进行,之后所有分组均按同一路由结点失败的影响出故障的路由器可能会丢失分组,一些路由可能会发生变化所有经过出故障的路由器的虚电路均不能工作分组的顺序 不一定按发送顺序到达目的站总是按发送顺序到达目的站端到端的差错处理由主机负责 由通信子网负责端到端的流量控制由主机负责 由通信子网负责拥塞控制 难 如果有足够的缓冲区分配给已经建立的每一条虚电路,则容易控制网络和现代通信技术基础 —— 网络层
5.2 路由选择机制节点交换机中的路由表交换机 3
交换机 1
交换机 2
交换机 2
路由表
[2,1] [2,2]
[1,1]
[1,3]
[3,1]
[3,3]
目的站
[1,1] 交换机 1
[1,3 交换机 1
[3,1] 交换机 3
[3,3] 交换机 3
[2,1] 本交换机
[2,2] 本交换机下一站
1 3
2
计算机的编址和网络层节点交换机的路由表网络和现代通信技术基础 —— 网络层目的站 下一站
1 交换机 1
3 交换机 3
2 本交换机路由表的简化
5.2 路由选择机制网络和现代通信技术基础 —— 网络层路由选择的一般原理
1,理想的路由算法,
算法必须是正确的和完整的 。
算法在计算上应简单 。
算法应能适应通信量和网络拓扑的变化 。
算法应具有稳定性 。
算法应是公平的 。
算法应是最佳的 。
5.2 路由选择机制网络和现代通信技术基础 —— 网络层
2,路由算法的分类非自适应路由选择策略自适应路由选择策略
（ 1） 非自适应路由选择,固定路由算法,分散通信量法,洪泛法,随机走动法
（２）自适应路由选择,分布式路由选择策略,集中式路由选择策略,
混合式路由选择策略
5.2 路由选择机制路由选择的一般原理网络和现代通信技术基础 —— 网络层固定路由算法,
Dijkstra算法 --最短距离 (最小代价 )算法,
① 初始化处理,定义数组 N,它只包含源节点 S,N＝ ｛ S｝,并定义距离 D (V)= L(S,V),V为非源节点中的一个,该距离为节点 V到源节点 S的链路长度 。 于是有
D(V) = L(S,V)；若 V与 S直接相邻
D(V) = ∞ ；若 V与 S不直接相邻
② 不断求得 N以外的各节点 F,使距离 D(F)最小,并将节点 F加入原来的数组,对 N以外的各节点,按式,D(V) = min [D(V),D(F)+L(F，
V)] 更新距离 D(V),当 D(F)+L(F,V)<D(V) 时,则以 D(F)+L(F,V)
取代原 D(V),否则维持原值不变 。 这一过程重复至所有节点均包含在数组 N内为止 。
5.2 路由选择机制非自适应路由选择网络和现代通信技术基础 —— 网络层固定路由算法,
Dijkstra算法 --最短距离 (最小代价 )算法,
5.2 路由选择机制非自适应路由选择网络和现代通信技术基础 —— 网络层分散通信量法,
5.2 路由选择机制非自适应路由选择目的站经过概率经过概率经过概率
A M 0.50 L 0.40 N 0.10
B M 0.50 N 0.20 L 0.30
C N 0.65 M 0.25 P 0.10
D N 0.55 P 0.30 M 0.15
E P 0.45 N 0.30 M 0.25
… … … …
A B C
DM N
E
P
G
L
节点 G中的路由表网络和现代通信技术基础 —— 网络层洪泛法,
这种方法是当某个节点收到一个不是发给它的分组时,就向所有与此节点相连的链路转发出去 。
随机走动法,
这种方法又称为随机徘徊,其特点是当分组到达某个节点时就随机地选择一条链路作为转发的路由 。
5.2 路由选择机制非自适应路由选择网络和现代通信技术基础 —— 网络层距离向量算法,
5.2 路由选择机制自适应路由选择距离向量路由选择 ( Distance Vector Routing ) 协议中,所有的 IMP
都定期地将它们的整个路由选择表传送给所有与之直接邻接的 IMP。
这种路由选择表包含：
l 每条路径的目的地 (另一 IMP)
l 路径的代价 (也称距离 )
网络和现代通信技术基础 —— 网络层距离向量算法,
5.2 路由选择机制自适应路由选择
0 24 20 21
12 36 31 28
25 18 19 36
40 27 8 24
14 7 30 22
23 20 19 40
18 31 6 31
17 20 0 19
21 0 14 22
9 11 7 10
24 22 22 0
29 33 9 9
A
B
C
D
E
F
G
H
I
J
K
L
TO A I H K
延迟 延迟 延迟 延迟是 8 是 10 是 12 是 6
从 J的四个邻居收到的向量
8 A
20 A
28 I
20 H
17 I
30 I
18 H
12 H
10 I
0 -
6 K
15 K
新估计的从
J的延时线路
J的新路由表路由器 J从其邻居收到距离向量表后计算自己的向量表网络和现代通信技术基础 —— 网络层链路状态 (Link State)算法,
5.2 路由选择机制自适应路由选择在一个链路状态路由选择协议中,一个 IMP检查所有直接链路的状态,并将所得的状态信息发送给网上所有其他的 IMP。 而不是仅仅送给那些直接相连的节点 。
以这种方式,每个 IMP从网上所有其他的 IMP接收包含直接链路状态的路由选择信息 。
每当链路状态报文到达时,路由节点 (IMP)便使用这些状态信息去更新自己的网络拓扑和状态,视野图,,把各个链路标为,Up”或,Down”。 一旦链路状态发生了变化,IMP对更新了的网络图利用 Dijkstra最短通路搜索算法更新计算路由 。
网络和现代通信技术基础 —— 网络层链路状态 (Link State)算法,
5.2 路由选择机制自适应路由选择链路状态路由选择协议的操作过程：
l 发现它的邻居节点,并知道其网络地址 。
l 测量到各邻居节点的延迟或代价
l 组装一个分组,以通告它刚获悉的信息 。
l 把这个分组发送给所有其他路由器 。
l 计算到其他每个路由器的最短路径 。
网络和现代通信技术基础 —— 网络层
5.2 路由选择机制自适应路由选择集中式路由选择策略集中式路由选择策略的核心是网控中心 NCC。 NCC负责全网状态信息的收集,路由计算以及路由选择的实现 。 集中式路由选择策略也有多种,
这取决于储存在 NCC中的网络信息的类型,路由的计算方法以及路由选择实现的技术 。
网络和现代通信技术基础 —— 网络层
5.2 路由选择机制自适应路由选择混合式路由选择策略为了克服集中式路由选择的缺点,可以同时综合使用几种路由选择策略 。
网络和现代通信技术基础 —— 网络层
5.3.1 拥塞控制的概念当（一部分）通信子网中有太多的分组时，其性能降低。这种情况叫做拥塞。造成拥塞有若干因素。如果突然之间，分组流同时从 3个或 4个输入线到达，并且要求输出到同一线路，
就将建立起队列。如果没有足够的空间来保存这些分组，有些分组就会丢失。处理器速度慢也能导致拥塞。拥塞会导致恶性循环。如果路由器没有空余缓冲区，它必须丢掉新到来的分组。拥塞控制和流量控制既有联系又有差异
5.3 拥塞控制网络和现代通信技术基础 —— 网络层
5.3.2 拥塞控制的基本原理所有解决方案被分为两类,一类是开环,一类是闭环 。 开环控制工具的功能包括决定何时接受新的通信,何时丢弃分组,以及丢弃哪些分组,还包括在网络的不同点作计划表 。 所有这些的共同之处在于,它们在做出决定时并不考虑当前网络的状况 。
与之相比较,闭环的解决方案是建立在反馈环路的概念之上的 。 当用于拥塞控制时,这种方法有 3个部分：
监视系统,检测何时何地发生了拥塞 。
将此信息传送到可能采取行动的地方 。
调整系统操作以更正问题 。
5.3 拥塞控制网络和现代通信技术基础 —— 网络层
5.3.3 拥塞预防策略层 次 策 略传输层?重发策略
乱序缓存策略
确认策略
流量控制策略
超时终止网络层?子网内的虚电路与数据报
分组排队和服务策略
分组丢弃策略
路由选择算法
分组生命期管理数据链路层?重发策略
乱序缓存策略
确认策略
流量控制策略
