课前提问
1.P104 T18
2.P104 T19
3.P104 T20
4.P109 T50
5.P105 T29
第三章 分组交换
3.1 改进与扩展
1,点到点网络的缺点所连接主机数量有限且连接地理范围有限。
2,改进目标使不互相连通的主机之间能够进行通信，使网络规模有更好的可扩展性。
3,主要方案引入某种专用的中间设备，如交换机
4,本章主要内容以相对抽象的方式分析分组交换的各种算法。
3.2 交换与转发
1.交换交换是一种允许互边链路以形成更大规模网络的机制。
2.交换机：
有多个输多个输出的设备，它能由一个输入端口传送分组到一个或多个输出端口,
3.交换机的拥塞现象如果到达交换机的分组需从同一输出口发送，
则会产生竞争；如果缓存存不下，会造成分组丢失；如果分组频繁丢失，称交换机 拥塞。
3.2 交换与转发
4,交换机工作方法：
交换使星型结构加入到点到点链路、环、总线等拓扑中。
5,星型拓扑的优点
1） 尽管单个交换机的输入出端口数有限，但可互连多个交换机，建立更大的网络。
2） 在交换机和主机之间使用点到点的链路，可扩大地理范围。
3） 将主机连到交换机中一般不会降低已连接主机的性能 (要重点理解这句 )。
附：交换机提供星形拓扑结构
3.3 交换网特点
1.交换网中的每一台主机都有一条到交换机的链路，所以许多主机以全带宽的速度传输数据是完全可能的。前提是交换机有足够的总容量。
2.交换网比共享介质网更具扩展性，即具备增加更多结点的能力
3.交换机的主要工作：在它的一条链路上接收输入分组，再把这些分组从其它链路上传出去。
4.交换机可能需要在多个使用不同的协议的链路间交换 /转发分组。
3.3 交换网特点
5,交换机工作假设
1） 网络中的每台主机地址是全局唯一的。
2） 使用给端口编号的方法标识同一交换机上的每个端口。
3）可选端口标识方案,通过输入、输出端口所连接的端点（交换机或主机）的名字来识别端口。
4） 交换机分析每个到达本机的分组,(简单但重要 )
3.4 数据报
1.数据报的思想：
每个分组带有足够的信息，使得任何一个交换机都能决定怎样使它到达目的地。
要决定怎样发送一个分组，交换机要查阅转发表
（也称路由表）。 当网络拓扑很简单时，很容易产生转发表。但当网络很大，很复杂，且结构可变，到目的地有多条路径时，这个问题就变得很困难了。
把路由选择看作是在这种背景下发生的过程，当数据分组到达时，在转发表中能够获得正确信息来转发或交换分组。
0交换机 13
主机 C 2
主机 A
主机 D
1
主机 B
主机 H
主机 G
2
3
1
0交换机 3
主机 E
2交换机 2
3 1
0
主机 F
目标主机 端口
A
B
C
D
E
F
G
H
3
0
3
3
2
1
0
0
交换网拓扑示例交换机 2的转发表
3.4 数据报网络特点
1.主机可随时随地发送分组，即到达交换机的分组能立即转发 (假设存在正确的转发表 )。
2.当主机发送分组时，它并不知道网络是否能转发该分组，或目的主机是否可以接收。
3.各分组的转发是相互独立。
4.某个交换机或一段链路发生故障时，只要能找到一条替换路径，并相应的更换转发表，
则通信不受大的影响。
5.健壮性是数据报方案的最初目的。
3.5 虚电路
1.虚电路技术,
分组交换中更广泛使用的是虚电路交换网络技术 (VC),又称面向连接的模式 ;
所谓连接：是在源主机和目的主机之间的每一个交换机上建立连接状态,使得源主机和目的主机逻辑上
,直接相连,,
2.建立连接的方法,
1) 永久虚电路（ PVC） 由网络管理员配置连接状态，
不删除，就永久存在,。
2) 发信令（ SVC）,主机能够发送消息给网络，建立连接状态,这种虚电路称为 交换的虚电路,
SVC,突出特性是主机可以动态地建立和删除这个虚电路，而不需要网络管理员的参与。
3.5 虚电路
3.虚电路记录项每个连接对应 VC表的一条记录,
每条记录由以下项组成,
1)输入接口,此 VC的分组从该接口到达交换机
2)输入 VCI,虚电路标识符 VCI,包含在每个到达的分组中,
3)输出接口,此 VC 的分组从该接口离开交换机,
4)输出 VCI:用于输出分组,
附,虚电路示例
0
1
2
3
0
1
2
3
0
1
2
3
A到 B虚电路附,虚电路示例
2 5 1 11
(a)
输入端口 输入 VCI 输出端口 输出 VCI交换机 1
交换机 2
交换机 3
3 11 0 7
(b)
输入端口 输入 VCI 输出端口 输出 VCI
0 7 3 4
(c)
输入端口 输入 VCI 输出端口 输出 VCI
3.5 虚电路
4,VCI
1)输入接口和输入 VCI 唯一确定一个虚连接给分组指定的 VCI 是当前交换机未用的值
2)输入和输出的 VCI 一般不相同
3)VCI是非全局的 V,它仅在一个给定的链路上有意义
3.5 虚电路
5.数据传输过程
1) 一旦 VC 表建立则数据传输阶段可进行
2) 对任何想去主机 B的分组,主机给该分组的
VCI 值设置为 5,并发送到交换机 1
3) 交换机 1在接口 2收到任何包,都用接口 VCI
的组合去查 VC,并找到适宜的表项,如上表所示,其出口是 1,VCI=11
4) 以下各站同,直到分组到达主机 B
3.5 虚电路
6 建立一个 PVC
1) 无论何时创建一个新的连接，网管员都要保证给分组分配一个当前未用的
VCI.
2) 对于一个合理大小的真实网络，网络管理员将不堪重负，因此 PVC,也是由网管发信令来完成建立连接的过程。
3.5 虚电路
7.信令过程
1)主机发一建立消息到网络交换机 1消息中主要有主机 B的全部地址,
2)交换机 1接收到这个连接请求,建立自己的 VC,添一条记录,<输入端口，输入 VCI,输出端口，？ >,
并发请求到交换机 2.
3)交换机 2执行与交换机 1同样的操作
4)当建立请求到主机 B,并且主机 B愿意同主机 A建立连接,B 发应答到交换机 3
5)最后交换机 1把应答转递给主机 A,告诉它可用 VC5
作本次连接,
3.5 虚电路
8.释放虚电路当主机 A不想发送数据给主机 B时，它通过给交换机 1发送一个撤销连接的消息来撤销连接,S1
撤销连接，且将撤销消息发给 S2,…… 如果现在 A再向 B发数据，必须重新申请建立 VC,否则分组将被丢弃,
3.5 虚电路
9.虚电路交换的特点存在的问题,
1)主机 A从发出连接请求到发送数据前收到应答,至少需要一个 RTT时延
2)虽然连接请求包含主机很长的全局地址,但后续的每个数据分组却只包含在每个链路上是唯一的很小的 VCI,这减少了开销
3)如果其中一个交换机或链路连接失败,本次连接也告失败,新的需重新建立,老的要删除
4)交换机怎样决定哪条链路?
3.5 虚电路虚电路的优点：
1) 主机在发送数据之前知道许多网络的信息,
2) 建立虚电路的同时,可以进行资源分配,
3.5 源路由选择
1.源路由：
有关在网络上需要交换分组的所有网络拓扑信息由源主机提供。
2.实现源路由：
给交换机的每个输出端口编号,并把它放在分组的头部
3.工作过程：
每个分组带一个交换机端口的有序列表，依次表示各交换机的输出端口号，分组每到一个交换机，交换机根据分组中指出的输出端口转发分组。
3.5 源路由选择主机 A
主机 B
1
2
3
0
1
2
3
2
1
0
3
1
0
2
3
交换机 1
交换机 2
交换机 3
3 0 1 1 3 0
0 1 3
0
3.5 源路由选择
4.存在的问题
1) 主机需要充分了解网络的拓扑结构。
2) 无法预测分组头部的大小。
5.PC实现交换机的性能分析
CPU
主存接口 1
接口 2
接口 3
3.5 源路由选择
1) 适于开发新型的交换机。
2) 受制于总线和内存带宽。
3.6 网桥
1,网桥是一种用于共享介质局域网中转发分组的一类交换机。
2,学习型网桥即利用到达网桥的分组中的,源地址,和 输入端口 信息构建交换表的。
附：网桥结构图网段 1 网段 2
3.6 网桥
3.生成树算法
1）目标生成一棵覆盖全图的树。
2）理由局域网的拓扑图可能存在环。
3）作用树的性质是两点间有且只有一条通路。利用生成的树拓扑进行分组交换时能得到唯一的输入输出转发表。网桥完全可能是被,冗余,了的结点。
3.6 网桥
4）算法序前提：
每个网桥要有唯一的标识基本思想：
用标识最小的结点作为 生成树的根,根可以通过每个端口转发数据，然后每个网段找出一条与根结点 距离最短的路径,并将该路径上的网桥作为 指派网桥,如果有同样短的路径，则取标号最小的。重复此过程，直到每个网段都能连通根结点为止。
附：生成树算法示例
B3
B2
B1
B6
B5
B7
B4
A
C
E
G
I
D
B
K
F
H
J
3.6 网桥
5）算法
初始均以自已为根结点。
发送配置消息（根,到根的距离，指派根）
记录并比较所有端口收发的配置消息，按最优条件进行比较：距离 +标号最小。
竞争失败后将该端口收到的配置消息中的,到根的距离,加 1后转发，并声称自己是指派根。
系统稳定后，除根结点外，其它的网桥必定都只转发根的配置信息，而均不发送自己的配置信息。
附：生成树算法示例
B3
B2
B1
B6
B5
B7
B4
A
C
E
G
I
D
B
K
F
H
J
附：网桥条件下的多播和广播
1,广播与在单一局域网中无区别。每个生成树中的网桥都向每个端口发送数据。
2,多播存在扩展方案，但一般不使用，而采用广播方案。
3.6 网桥
4.网桥的局限性
1） 生成树算法是线型增大,即无层次，且 LAN
较大时耗时很多。
2） 广播容易造成广播风暴（ LAN较小可用）
3） 不支持异种网互连
4） 解决方案,VLAN
附,VLAN示意图
W X
B1 B2
Y Z
VLAN 100 VLAN 100
VLAN 200 VLAN 200
3.7 信元交换
1.信元信元是指固定长度的分组。
2.信元的优点（短分组的优点）
1) 硬件简单高效
分组长度预先知道则交换硬件容易实现
可用许多交换单元并行处理,提高速率
2）时延稳定
输出时延相对稳定
链路空闲时间短
3.7 信元交换
3.信元尺寸的选择它是推进 ATM标准化时的折衷结果：
1） 美国电话公司提出 64 字节适应美国
2） 欧洲电话公司提出 32 字节适应欧洲
3） 最终的结果：（ 64+32） /2=49 = 48
3.7 信元交换
4.信元格式
UNI,用户 — 网络接口
NNI,网络 — 网络接口区别在于,NNI格式给 VPI附加 4b取代 GFC字段
PayloadHEC(CRC-8)CLPTypeVCIVPIGFC
4Bits 8 16 3 1 8
384(48Byte)
3.7 信元交换
5.分段与重组
1）分段的原因：
上层协议的分组大于下层协议的分组大小；某类型网络的数据帧大于将要进入网络的数据帧尺寸。
2）重组的要求：
分段时必须提供足够的信息保证被分段的组在另一端重组。
3） ATM的分段与重组分为 4个 AAL层,1,2,3/4,5
附：分段与重组示意图
AAL
ATM
AAL
ATM
3.7 信元交换
3） ATM的分段与重组（续）
AAL实际上是二层结构，第一层将上层数据进行封装，第二层将第一层封装后的数据进行切割 /合并。
6.其它问题
1） ATM设计的目标是交换网，而不是共享介质的局域网，因此假设不存在介质冲突问题。
2） ATM同样工作在物理层之上。
3） ATM同样需要与传输控制协议配合工作。
附,LANE示意图主机 交换机 主机类以太网接口高层协议
(IP,ARP,.,,)
发信令
+ LANE
AAL5
ATM
PHY
高层协议
(IP,ARP,.,,)
发信令
+ LANE
AAL5
ATM
PHY
ATM
PHY PHY
1.P104 T18
2.P104 T19
3.P104 T20
4.P109 T50
5.P105 T29
第三章 分组交换
3.1 改进与扩展
1,点到点网络的缺点所连接主机数量有限且连接地理范围有限。
2,改进目标使不互相连通的主机之间能够进行通信，使网络规模有更好的可扩展性。
3,主要方案引入某种专用的中间设备，如交换机
4,本章主要内容以相对抽象的方式分析分组交换的各种算法。
3.2 交换与转发
1.交换交换是一种允许互边链路以形成更大规模网络的机制。
2.交换机：
有多个输多个输出的设备，它能由一个输入端口传送分组到一个或多个输出端口,
3.交换机的拥塞现象如果到达交换机的分组需从同一输出口发送，
则会产生竞争；如果缓存存不下，会造成分组丢失；如果分组频繁丢失，称交换机 拥塞。
3.2 交换与转发
4,交换机工作方法：
交换使星型结构加入到点到点链路、环、总线等拓扑中。
5,星型拓扑的优点
1） 尽管单个交换机的输入出端口数有限，但可互连多个交换机，建立更大的网络。
2） 在交换机和主机之间使用点到点的链路，可扩大地理范围。
3） 将主机连到交换机中一般不会降低已连接主机的性能 (要重点理解这句 )。
附：交换机提供星形拓扑结构
3.3 交换网特点
1.交换网中的每一台主机都有一条到交换机的链路，所以许多主机以全带宽的速度传输数据是完全可能的。前提是交换机有足够的总容量。
2.交换网比共享介质网更具扩展性，即具备增加更多结点的能力
3.交换机的主要工作：在它的一条链路上接收输入分组，再把这些分组从其它链路上传出去。
4.交换机可能需要在多个使用不同的协议的链路间交换 /转发分组。
3.3 交换网特点
5,交换机工作假设
1） 网络中的每台主机地址是全局唯一的。
2） 使用给端口编号的方法标识同一交换机上的每个端口。
3）可选端口标识方案,通过输入、输出端口所连接的端点（交换机或主机）的名字来识别端口。
4） 交换机分析每个到达本机的分组,(简单但重要 )
3.4 数据报
1.数据报的思想：
每个分组带有足够的信息，使得任何一个交换机都能决定怎样使它到达目的地。
要决定怎样发送一个分组，交换机要查阅转发表
（也称路由表）。 当网络拓扑很简单时，很容易产生转发表。但当网络很大，很复杂，且结构可变，到目的地有多条路径时，这个问题就变得很困难了。
把路由选择看作是在这种背景下发生的过程，当数据分组到达时，在转发表中能够获得正确信息来转发或交换分组。
0交换机 13
主机 C 2
主机 A
主机 D
1
主机 B
主机 H
主机 G
2
3
1
0交换机 3
主机 E
2交换机 2
3 1
0
主机 F
目标主机 端口
A
B
C
D
E
F
G
H
3
0
3
3
2
1
0
0
交换网拓扑示例交换机 2的转发表
3.4 数据报网络特点
1.主机可随时随地发送分组，即到达交换机的分组能立即转发 (假设存在正确的转发表 )。
2.当主机发送分组时，它并不知道网络是否能转发该分组，或目的主机是否可以接收。
3.各分组的转发是相互独立。
4.某个交换机或一段链路发生故障时，只要能找到一条替换路径，并相应的更换转发表，
则通信不受大的影响。
5.健壮性是数据报方案的最初目的。
3.5 虚电路
1.虚电路技术,
分组交换中更广泛使用的是虚电路交换网络技术 (VC),又称面向连接的模式 ;
所谓连接：是在源主机和目的主机之间的每一个交换机上建立连接状态,使得源主机和目的主机逻辑上
,直接相连,,
2.建立连接的方法,
1) 永久虚电路（ PVC） 由网络管理员配置连接状态，
不删除，就永久存在,。
2) 发信令（ SVC）,主机能够发送消息给网络，建立连接状态,这种虚电路称为 交换的虚电路,
SVC,突出特性是主机可以动态地建立和删除这个虚电路，而不需要网络管理员的参与。
3.5 虚电路
3.虚电路记录项每个连接对应 VC表的一条记录,
每条记录由以下项组成,
1)输入接口,此 VC的分组从该接口到达交换机
2)输入 VCI,虚电路标识符 VCI,包含在每个到达的分组中,
3)输出接口,此 VC 的分组从该接口离开交换机,
4)输出 VCI:用于输出分组,
附,虚电路示例
0
1
2
3
0
1
2
3
0
1
2
3
A到 B虚电路附,虚电路示例
2 5 1 11
(a)
输入端口 输入 VCI 输出端口 输出 VCI交换机 1
交换机 2
交换机 3
3 11 0 7
(b)
输入端口 输入 VCI 输出端口 输出 VCI
0 7 3 4
(c)
输入端口 输入 VCI 输出端口 输出 VCI
3.5 虚电路
4,VCI
1)输入接口和输入 VCI 唯一确定一个虚连接给分组指定的 VCI 是当前交换机未用的值
2)输入和输出的 VCI 一般不相同
3)VCI是非全局的 V,它仅在一个给定的链路上有意义
3.5 虚电路
5.数据传输过程
1) 一旦 VC 表建立则数据传输阶段可进行
2) 对任何想去主机 B的分组,主机给该分组的
VCI 值设置为 5,并发送到交换机 1
3) 交换机 1在接口 2收到任何包,都用接口 VCI
的组合去查 VC,并找到适宜的表项,如上表所示,其出口是 1,VCI=11
4) 以下各站同,直到分组到达主机 B
3.5 虚电路
6 建立一个 PVC
1) 无论何时创建一个新的连接，网管员都要保证给分组分配一个当前未用的
VCI.
2) 对于一个合理大小的真实网络，网络管理员将不堪重负，因此 PVC,也是由网管发信令来完成建立连接的过程。
3.5 虚电路
7.信令过程
1)主机发一建立消息到网络交换机 1消息中主要有主机 B的全部地址,
2)交换机 1接收到这个连接请求,建立自己的 VC,添一条记录,<输入端口，输入 VCI,输出端口，？ >,
并发请求到交换机 2.
3)交换机 2执行与交换机 1同样的操作
4)当建立请求到主机 B,并且主机 B愿意同主机 A建立连接,B 发应答到交换机 3
5)最后交换机 1把应答转递给主机 A,告诉它可用 VC5
作本次连接,
3.5 虚电路
8.释放虚电路当主机 A不想发送数据给主机 B时，它通过给交换机 1发送一个撤销连接的消息来撤销连接,S1
撤销连接，且将撤销消息发给 S2,…… 如果现在 A再向 B发数据，必须重新申请建立 VC,否则分组将被丢弃,
3.5 虚电路
9.虚电路交换的特点存在的问题,
1)主机 A从发出连接请求到发送数据前收到应答,至少需要一个 RTT时延
2)虽然连接请求包含主机很长的全局地址,但后续的每个数据分组却只包含在每个链路上是唯一的很小的 VCI,这减少了开销
3)如果其中一个交换机或链路连接失败,本次连接也告失败,新的需重新建立,老的要删除
4)交换机怎样决定哪条链路?
3.5 虚电路虚电路的优点：
1) 主机在发送数据之前知道许多网络的信息,
2) 建立虚电路的同时,可以进行资源分配,
3.5 源路由选择
1.源路由：
有关在网络上需要交换分组的所有网络拓扑信息由源主机提供。
2.实现源路由：
给交换机的每个输出端口编号,并把它放在分组的头部
3.工作过程：
每个分组带一个交换机端口的有序列表，依次表示各交换机的输出端口号，分组每到一个交换机，交换机根据分组中指出的输出端口转发分组。
3.5 源路由选择主机 A
主机 B
1
2
3
0
1
2
3
2
1
0
3
1
0
2
3
交换机 1
交换机 2
交换机 3
3 0 1 1 3 0
0 1 3
0
3.5 源路由选择
4.存在的问题
1) 主机需要充分了解网络的拓扑结构。
2) 无法预测分组头部的大小。
5.PC实现交换机的性能分析
CPU
主存接口 1
接口 2
接口 3
3.5 源路由选择
1) 适于开发新型的交换机。
2) 受制于总线和内存带宽。
3.6 网桥
1,网桥是一种用于共享介质局域网中转发分组的一类交换机。
2,学习型网桥即利用到达网桥的分组中的,源地址,和 输入端口 信息构建交换表的。
附：网桥结构图网段 1 网段 2
3.6 网桥
3.生成树算法
1）目标生成一棵覆盖全图的树。
2）理由局域网的拓扑图可能存在环。
3）作用树的性质是两点间有且只有一条通路。利用生成的树拓扑进行分组交换时能得到唯一的输入输出转发表。网桥完全可能是被,冗余,了的结点。
3.6 网桥
4）算法序前提：
每个网桥要有唯一的标识基本思想：
用标识最小的结点作为 生成树的根,根可以通过每个端口转发数据，然后每个网段找出一条与根结点 距离最短的路径,并将该路径上的网桥作为 指派网桥,如果有同样短的路径，则取标号最小的。重复此过程，直到每个网段都能连通根结点为止。
附：生成树算法示例
B3
B2
B1
B6
B5
B7
B4
A
C
E
G
I
D
B
K
F
H
J
3.6 网桥
5）算法
初始均以自已为根结点。
发送配置消息（根,到根的距离，指派根）
记录并比较所有端口收发的配置消息，按最优条件进行比较：距离 +标号最小。
竞争失败后将该端口收到的配置消息中的,到根的距离,加 1后转发，并声称自己是指派根。
系统稳定后，除根结点外，其它的网桥必定都只转发根的配置信息，而均不发送自己的配置信息。
附：生成树算法示例
B3
B2
B1
B6
B5
B7
B4
A
C
E
G
I
D
B
K
F
H
J
附：网桥条件下的多播和广播
1,广播与在单一局域网中无区别。每个生成树中的网桥都向每个端口发送数据。
2,多播存在扩展方案，但一般不使用，而采用广播方案。
3.6 网桥
4.网桥的局限性
1） 生成树算法是线型增大,即无层次，且 LAN
较大时耗时很多。
2） 广播容易造成广播风暴（ LAN较小可用）
3） 不支持异种网互连
4） 解决方案,VLAN
附,VLAN示意图
W X
B1 B2
Y Z
VLAN 100 VLAN 100
VLAN 200 VLAN 200
3.7 信元交换
1.信元信元是指固定长度的分组。
2.信元的优点（短分组的优点）
1) 硬件简单高效
分组长度预先知道则交换硬件容易实现
可用许多交换单元并行处理,提高速率
2）时延稳定
输出时延相对稳定
链路空闲时间短
3.7 信元交换
3.信元尺寸的选择它是推进 ATM标准化时的折衷结果：
1） 美国电话公司提出 64 字节适应美国
2） 欧洲电话公司提出 32 字节适应欧洲
3） 最终的结果：（ 64+32） /2=49 = 48
3.7 信元交换
4.信元格式
UNI,用户 — 网络接口
NNI,网络 — 网络接口区别在于,NNI格式给 VPI附加 4b取代 GFC字段
PayloadHEC(CRC-8)CLPTypeVCIVPIGFC
4Bits 8 16 3 1 8
384(48Byte)
3.7 信元交换
5.分段与重组
1）分段的原因：
上层协议的分组大于下层协议的分组大小；某类型网络的数据帧大于将要进入网络的数据帧尺寸。
2）重组的要求：
分段时必须提供足够的信息保证被分段的组在另一端重组。
3） ATM的分段与重组分为 4个 AAL层,1,2,3/4,5
附：分段与重组示意图
AAL
ATM
AAL
ATM
3.7 信元交换
3） ATM的分段与重组（续）
AAL实际上是二层结构，第一层将上层数据进行封装，第二层将第一层封装后的数据进行切割 /合并。
6.其它问题
1） ATM设计的目标是交换网，而不是共享介质的局域网，因此假设不存在介质冲突问题。
2） ATM同样工作在物理层之上。
3） ATM同样需要与传输控制协议配合工作。
附,LANE示意图主机 交换机 主机类以太网接口高层协议
(IP,ARP,.,,)
发信令
+ LANE
AAL5
ATM
PHY
高层协议
(IP,ARP,.,,)
发信令
+ LANE
AAL5
ATM
PHY
ATM
PHY PHY
