在入线处的队列将需要更多的缓冲容量 存在队头阻塞（HOL）



在一个信元周期内，任一条出线都只能为一个信元提 供输出服务，而选择该出线的其他信元必须在输入队 列中等待 若一条入线上的队列的排头信元因竞争失败而阻塞， 该队列中的所有后续信元也被迫阻塞，即使该队列中 的后续信元所选择的出线当前是空闲的。 一个信元周期内，通过交换传输媒体传输的信元数 P 不超过交换单元的入线总数 N，即 P N。
出线
单级交换网络
29
混合式互换网络
0 1 0 1 2 3 4 5 6 7
输 入 端 口
2 3 4 5 6 7
输 出 端 口
反馈回路
30
多级交换网络
多级交换网络的拓扑结构可用三个参数来说明： 每个交换单元的容量 交换单元的级数
交换单元间的连接通路（链路）
31
多级交换网络(nm x nm两级交换网络)

下图是一个交叉点缓冲方式（Crosspoint Buffer），即 缓冲器设置在交叉点中，用在基于crossbar交换网络中。 交叉点缓冲方式不存在HOL阻塞现象，其缓冲性能类 似于输出缓冲方式， 但不存在加速因子，即 对内部处理速度和存储 器存储速率没有加速要 求，但这种方式需要较 多数量的存储器。
缓冲器 交换 单元 输出 控制器 输入 控制器 交换 单元
37
反压控制
第 K-1 级
第K级
ATM交换机构和交换系统
ATM交换机构
时分交换
空分交换
共享总线
环形结构
共享存储器
单级交换网
多级交换网
扩展 交换 矩阵
漏斗 型网 络
混洗 交换 网络
弹出 式交 换网 络
单通 路网 络
多通 路网 络
38
ATM交换系统举例
20

该图表示了一个带缓冲型banyan交换网络（Buffered Banyan），它是在交换单元（SE）内部设置缓冲。缓 冲型banyan缓冲方式与交叉点缓冲方式不同，缓冲型 banyan的缓冲器主要是用来存储在内部竞争中失败的 信元，减少信元丢失率。当然缓冲器即使在交换单元 （SE）内部， 也会有不同的配置方式 （输入方式，输出方式， 输入输出方式），图中就 是一个由采用输入缓冲方 式的SE构成的缓冲型 banyan交换网络。
缓冲型banyan交换网络（输入缓冲方式）
21
邮局中的输入排队模型

一个邮局中有两个服务窗 口

邮票窗口
邮寄窗口
邮局大门相当于一条入线 两个服务窗口相当于两条 出线
邮票


到达邮局的顾客都邮局门 口排在一个队列中

相当于输入队列


队列按照先进先出原则服 务 队头的顾客被阻塞（等待） 会导致队中的其他顾客也 得不到服务


在输入排队模型中，仲裁逻辑是必须的
用于确定可以得到服务的入线
11
Ê È Å ¶ Ö µ ¶ Í ×È £ HOL£ ä ë Ó Ð Ä Ô ·è û ¨ ©
12
输出排队

基本思想

来自入线的信元可以自由通过交换传输媒体传送（交换） 到所需的出线上，在出线上设置缓冲队列解决多信元对出线 的竞争。

ATM交换系统是由话路子系统和控制子系统组成，其 中话路子系统由输入和输出侧接口以及交换网络组成， 该ATM交换系统的交换网络采用了Sunshine交换结构， 如图所示。
交换网络 时延
输入端口 ... 输入端口
IPC ... IPC
邮票 寄信 寄信 邮票
22
邮局中的输出排队模型

到达的顾客都直接进入邮 局，并根据自己的目的选 择排在一个服务窗口的队 列中

邮票窗口
邮寄窗口
顾客的选择相当于交换过 程 窗口队列相当于输出队列
邮票
邮票 邮票
寄信
寄信 寄信
23

服务窗口的利用率得到提 高 顾客排队的等待时间减少 了
VCC k m l a b c
2
信元被交换的同时， 输入信头的值被翻译 成输出信元头的值。
1、交换网络的构成和分类
交换的基本功能是在任意的入线和出线之间 建立连接。 在交换系统中完成这一基本功能的部件就是 交换网络，它是交换系统的核心。交换网络是由 若干个交换单元按照一定的拓扑结构和控制方式 构成的。 交换单元是构成交换网络的最基本的部件。 交换网络有：空分、时分 数字、模拟
N
交换传输媒体

无阻塞的传输网络，信元通过传输媒体时无需仲裁逻辑 信元在出线处排队，采用 FIFO 原则，保证信元的顺序
14

每出线配置一个缓冲队列

输出排队的优缺点





设置在出线上的队列所需的缓冲空间较小 去往同一条出线的多个信元可以在同一个信元 周期内交换到出线上，不存在队头阻塞 不需要仲裁逻辑 为保证没有信元丢失，在传输交换媒体中信元 的传输交换的速率必须 N 倍于入线的速率 输出排队策略对缓冲器的访问速度要求很高

在一个信元周期内需要对队列缓冲器进行 N 次信元写操作 和一次信元读操作。Biblioteka 15中央排队
基本思想

为了减少整个交换单元所需的总缓冲容量，在基本交换 单元中设置一个共享的队列缓冲器，被所有的入线和出线 所公用。

实现方法


在基本交换单元的中央设置一个队列缓冲器，被所 有的入线和出线所共享 来自所有入线上的全部信元都直接存入中央队列 各出线从中央队列中查找目的地为其自身的信元， 依照先进先出的原则取出并发送
35
可重排无阻塞网络
1 2
3 4
C1
cc2
1 2 3 4
cc2
C1
36
采用反压机制的无阻塞 MIN

各交换单元的输入具有缓冲器，存储竞争失败的信元 内部控制机制监视缓冲器的充满程度，当缓冲器快充满时，向上游交换单 元发送反压控制，防止队列溢出 内部链路速率需高于外部，保证在入线处无信元丢失

19
三种排队策略的性能分析

衡量排队策略性能的参数

信元丢失率 信元的排队时延 所需队列缓冲器的容量（实现参数）


研究性能的方法
在交换单元的输入线上，给定一种特定的业务类型和业务 量负荷，来研究不同排队策略的性能。

进行排队策略的性能的手段

直观的分析 建立数学模型 计算机仿真的

智能服务员在服务窗口空 闲时，从队列中找出下一 个需要被服务的顾客

服务员的功能对应于一个 复杂的控制逻辑
邮票 寄信 服务员 寄信 邮票
24
三种排队策略的直观分析

平均等待时间

对相同的外部业务负荷，输入排队的平均等 待时间比其他两种排队策略更长
输入排队需要最大 中央排队需要最少 在队列缓冲容量相同的情况下，输入排队信 元丢失率明显高于输出排队和中央排队
25

队列缓冲器需求


信元丢失率

三种策略的实现参数的比较
输出排队 输入排队 中央排队 存贮器速度 控制逻辑 缓冲器大小 性能 支持组播 高 FIFO 大 高 容易 低 FIFO 很大 低 困难 高 复杂 小 高 困难
26
3、交换网络
交换网络是由若干个交换单元按照一定的拓 扑结构和控制方式构成的网络。
可重排无阻塞网络：
不管网络处于何种状态，任何时刻都可以在交换网 络中直接或对已有的连接重选路由来建立一个连接，只要 这个连接的起点、终点是空闲的，而不会影响网络中已建 立起来的连接。
广义无阻塞网络： 指一个给定的网络存在着固有的阻塞可能，但又可 能存在着一种精巧的选路方法，使得所有的阻塞均可避免， 而不必重新安排网络中已建立起来的连接。
9

实现方式



输入排队模型
输入队列
1 2 1 2
入 线
N

仲 裁 逻 辑

传输 交换 媒体 仲裁逻辑

出 线
N
每条入线一个缓冲队列 信元在入线排队

交换传输媒体

决定可以得到服务的入线 仲裁策略

是一个无阻塞的传输网络
轮流服务、具有优先级（固 定优先级或队列长度优先等）
10
输入排队的缺点

基本交换模块的容量

规模：从 2x2 到 16x16 信息速率： 从 155Mbit/s、622Mbit/s 到 2.5Gbit/s 基本交换模块的容量（规模和信息速率）决定于：
采用的技术工艺、设计的集成化程度

基本交换模块的基本功能 —— 排队功能

基本交换模块是一个统计复用器 在基本交换模块内部会出现竞争
交换网络
1
ATM 交换的基本原理
z y x x
I1 I2
数据
Queue Queue
O1 O2
k l
k b
a a
输入
s
数据
s
信元头
y x
输出
In
Queue
Oq
m
c
c
信元
信元头
信头 翻译表

信元头翻译

输入链路 I1 : : In
VCC x y z x y s
输出链路 O1 Oq O2 O1 O2 Oq

实现方法



在一个信元周期内，所有信元都可无需仲裁地从入 线到达所需的出线 每条出线配置一个队列，以便缓冲同时到达的竞争 该出线的多个信元 一个信元周期内，一条出线只能为一个信元服务， 未服务的信元将暂存在该出线的输出队列中