交换原理笔记

二月 22, 2023

开个坑，期末复习用。
ICT:Information Communication Technology,是IT和CT的融合

chapter0-交换通识概论

停电了电话还能打：电话通过双绞线连到供电局，是由供电局来供电的。

通信网的三要素：

交换设备
传输设备
- 用户与交换机之间的线叫用户线
- 交换机与交换机之间的线叫中继线（Trunk）
(用户)终端设备
无线通信：
手机和基站是无线的，基站和基站之间还是有线的。
PSTN:public switching telephone network

通信网的分层：（从上到下）

应用层
业务层：里面有很多业务网，比如PSTN,ISDN,OSODN,IN,IP,移动通信网（3G,4G等）
传送层
- 接入网：接入的是用户网CPE、CPN，相当于高速匝道，2000年左右“打通最后一公里”
- 骨干传送网：光纤啦啥的，物理层的，相当于高速车道
还有一个支撑网，不属于任何一层，包括信令网，电信管理网，数字同步网，有点像CPU里面的控制部件。

通信网的分层

接入网的ways：
ADSL：亚洲用的多，A是非对称的，下行的速率大，一个小盒子，叫ADSL猫，装完之后就可以同时走电话（300~3400hz）和网络（4k以上，分为上行和下行）。现在换成光纤了，叫光猫。
HDSL:high speed DSL,北美用的多，可以达到1.5M，但不能同时传话音和数据
LAN：局域网，共享的，会分流量。
HTTH：光纤到用户，日本是这么干的，因为日本在2000年的时候有钱&国土小。

无线接入技术：

WWAN是广域网，已经不属于接入网了，3G,4G都属于这个范畴。

业务网：

电话通信网 PSTN
分组交换网 X.25 ，分组交换，支持两种方式，数据报和虚电路，ITU-T国际电信联盟推出的，是全球化的标准。
综合业务数字网 N-ISDN 窄带的
帧中继网 FRN
数字数据网 DDN
IN 智能网
综合业务数字网 B-ISDN，宽带的
下一代网络 NGN
移动互联网
物联网 IOT Internet of things，信息传感器

业务网

Q:电路交换跟分组交换和帧交换的区别？
Q:数据报和虚电路的区别？
Q:电信网和计算机网？
另：业务网ppt的交换方式列电路交换&分组交换应下移一行

通信的基本问题：

用什么信息格式传递给对方？编码
如何找到对方？寻址
信息传递的额外要求：网络结构、带宽、复用、连接方式、security、QoS（巴普特的是连到西直门电话局）

通信的三对基本概念：

信息传送的方式
- 面向连接:连接建立——信息传送——连接释放公交车/专线
- 无连接：边寻址边传递讯息自行车春游
时分复用（另一种复用是频分复用）
- 同步时分复用
  - 固定带宽分配
  - 位置化信道：依据信号在时间轴上的位置来区分每一路信号（逻辑信道），无信息传送时也占用信道。
  - 每帧定长、子信道信息流速率恒定。
- 异步时分复用（统计时分复用）
  - 按需分配，提高了利用率
  - （动态带宽分配）
  - 标志化信道：标志码表示哪路信息。
  - 分组长度可变或不可变，分组头用于定界。
  - 统计复用提高信道利用率。
带宽分配
类比：交通车道
- 固定带宽分配，2G，信道是固定的
- 动态带宽分配，4G，按需分配信道

Word

time slot TS 时隙
PTM
ATM
CTM

chapter1-交换概率

交换方式

CTM PTM 的比较

对信息的损伤方面
- 电路交换——时间透明性好，延迟小
- 分组交换——语义透明性好，错误少
支持多种业务方面
- 分组交换有更大的灵活性，可实现多速率交换，并允许多种业务共享网络资源
交换速率
- 电路交换可达到高速率的交换（硬件）
- 分组交换的交换速率受到了限制（软件要看包头）
设备的复杂性
- 分组交换需要复杂的队列管理机制
- 电路交换需要复杂的路由选择算法

电路交换

电话通信中信息的传送方式：公共交换电话网（Public Switched Telephone Network，PSTN），每一路能提供 64k 速率。（恒定速率）

特点
- 信息传送的最小单位是时隙：每个时隙采样 8bit，采样率 8kHz，每路通信速率 64kbps。
- 面向连接的工作方式（物理连接）
- 同步时分复用（固定带宽分配）
- 无差错控制机制
- 对通信信息不做处理（透明传输）
- 流量控制基于呼叫损失制

适合实时的、恒定速率的话音业务

多速率电路交换

讲几个基本信道速率捆绑起来，构成一个速率更高的信道，即确定基本信道速率，按需形成其他速率，且其他速率是基本速率的整数倍

关键问题：

确定基本速率
保证时隙顺序完整性（TSSI）

特点：软件实现，控制软件复杂

分组交换

思想来源于报文交换，本质都是存储——转发
所不同的是分组交换的最小信息单位是分组,而报文交换则是一个个报文。由于以较小的分组为单位进行传输和交换,所以分组交换比报文交换快。报文交换主要应用于公用电报网中。

分组交换的特点

信息传送的最小单位是分组：由分组头、用户信息构成，分组头含有选路和控制信息。
面向连接（虚电路）方式和无连接（数据报）方式。
统计时分复用，动态分配带宽。
有差错控制机制：CRC 校验、重发等（设于第二层和第三层协议中）。
信息传送不具有透明性：对通信信息作处理，如拆分、重组等。
流量控制基于呼叫延迟制。

	虚电路	数据报
分组头	简单（逻辑信道号）	复杂（详细的选路信息）
选路	虚连接表	每个分组独立选路
分组顺序	有序	可能失序
故障敏感性	敏感	可靠性高
应用	连续数据流	询问/响应

分组交换的两种方式

虚电路VC
- 面向连接的OC，先建立（逻辑）连接，再传输
- 虚连接也称为虚电路,即逻辑连接,它不同于电路交换中实际的物理连接,而是通过通信连接上的所有交换节点保存选路结果和路由连接关系来实现连接,因此是逻辑的连接。
- 不会失序，适用于连续的数据流
- 一旦建立的连接出现故障,信息传送就要中断,必须重新建立连接,因此对故障敏感。
数据报DG
- 无连接CL，一边传送一边选路
- 典型应用是IP网络
- 统计时分复用（动态带宽分配）

适用于可靠性要求高、突发（burst）、可变速率的数据业务。

帧中继

ATM交换

特点

传输的最小单位是cell（信元），固定长度是53byte，前5byte是信头（简化的），其余48byte是payload
采用了异步时分复用方式（动态分配带宽）
面向连接的工作方式，逻辑连接，用VPI,VCI来表示信道

交换系统

交换系统的基本结构
交换网络是第二章的核心，又叫交换矩阵。

信息传送子系统：
- 交换网络：完成交换，实现任意出线与入线的互联。
- 各种接口：分为用户接口和中继接口，用途是进行信号转换。
控制子系统：由处理机系统构成，是交换系统的“指挥中心”。

chapter2-交换网络

这一章是考试的重点，期末大概占40%。

交换网络的构成

交换网络是由若干个交换单元按照一定的拓扑结构和控制方式构成的网络。交换网络的三个基本要素是：交换单元、不同交换单元间的拓扑结构和控制方式。
==交换单元是构成交换网络的最基本的部件。==

交换单元

SE :switch element
==交换单元是构成交换网络的最基本的部件。==

$M \times N$:容量，M条入线，N条出线

交换单元的分类

入线和出线信息传送方向
关于K$\times $L ：从K个进入，只能从L个出来；而从L进入，只能从K个出来；并不是全联通的，要与N$\times $N区分开来。
入线和出线的数量关系
时分与空分(按照入线和出线之间是否共享单一通路)
按照交换单元所接收的信号
- 模拟交换单元（现在已经不用了）
- 数字交换单元
全联通与部分联通交换单元

交换单元的基本特性

交换单元的连接特性

交换单元连接特性的描述方式：
- 集合描述方式
- 函数描述方式（排列、图形、二进制函数）
常见的连接方式：
- 直接连接
- 交叉连接
- 蝶式连接
- 均匀洗牌连接
- 间隔交叉连接

交换单元的性能

容量：
交换单元所有入线可以同时送入的总的信息量
接口：
交换单元需要规定自己的信号接口标准，即信号形式、速率及信息流方向
功能：
点到点、点到多点
质量：
完成交换动作的速度、任何情况下是否能完成指定连接、信息经过交换单元是否有损伤(时间、语义)

连接、连接方式

连接

集合描述法
函数描述法

连接方式

直线连接
交叉连接（交换置换）
蝶式连接
均匀洗牌置换
间隔交叉连接（方体置换）

开关阵列

在每条入线和每条出线直接都各自接上一个开关，构成开关阵列。

开关的位置：入、出线交叉点
开关的表示：$K_{ij}$（i 为入线，j 为出线）
开关的状态：通、断
开关的种类：单向、双向

实现：全连通交换单元、部分连通交换单元、多路选择器……

开关阵列的特性：
可以很容易的实现点到多点的传输，也就是说容易实现广播功能
开关阵列的时延，从（每路）入线到出线延迟时间均等
控制信加暗淡
交换单元性能依赖于所使用的开关（电子的快，机械的慢）
适用于构成较小的交换单元（开关num反应实现复杂度和成本高低）

实际使用的开关阵列

继电器
模拟电子开关
数字电子开关

空间（空分）交换单元

也叫空间接线器（Space Switch），简称 S 单元或 S 接线器 。用来完成多个输入服用先与多个输出复用线之间的空间交换，而不改变其时隙位置。

每条线都是PCM，开关阵列不一定是PCM，但是S接线器是一定是PCM，也就是每一路上面有很多个时隙（老师举例子是32
路PCM）。专为话音通信设计的。
特别的，S接线器，入线和出线的数目都是相等的，而且每条线的（whatever 入还是出）传输速率都是一样样的。

构成：
- 交叉点矩阵（开关阵列）
- 控制存储器（CM，Control Memory）
功能：输入输出线之间的空间交换
S 接线器所含 CM 数量等于入（出）线数
每个 CM 含有的存储单元个数等于入（出）线上的复用时隙数
每个存储单元为 m 位 bit，且满足$N \le 2^m$，其中 N 为接线器的入（出）线数
CM 具有输入控制方式与输出控制方式。
- 输入控制方式
  关于CM里面记得是什么：
  左侧的0~n-1是时隙的编号，如果按照老师说的是32路PCM，那么这里的n=32
  横着的是0-N-1，表示一共是N条入线（出线）
  因为是输入控制方式，格子里面填写的是出线的序号
  比如[30,3]=8,意思就是第三条入线的第30个时隙应该输出到第八条出线上，至于输出到第八条出线的哪个时隙上，因为S接线器不改变时隙，只改变空间，笔者认为应该是输出到第八条线的第30个时隙。
  ==这里还需要注意是是，CM中一共有N个控制存储器，而对于每个控制存储器，它的存储单元数目=n，而bit数=$\lceil log_2N \rceil$==
- 输出控制方式 ==容易实现多播！==
空间交换单元的基本特点：
- 只完成空间交换，不进行时隙交换
- 空间接线器按时分方式工作
- 输出控制方式易于实现多播

每秒钟抽样8000帧(???//这个哪来的？？？)，每一帧中有32个时隙，所以改变的周期是3.9$\mu s$

时间（时分）交换单元

这个玩意儿，其实只有一条线的输入和输出。
大家说的N路输入输出都是指的PCM，也就是说，本来就一个输入的口和输出的口，只是时隙不同。这一点非常重要，记住这个才可能理解后面的共享存储器和共享总线的工作机制。

时分交换单元的一般构成

分为：共享存储器型交换单元、共享总线型交换单元。

共享存储器型：共 2N 个出入线缓存。

入线缓存控制读出
出线缓存控制写入

共享总线型：总线按照时隙轮流分配给入线控制部件和出线控制部件使用

$kNV=B/T$（N 为入线数、V 为入线速率、B 为每时隙传送比特数、T 为时隙长度，k 为时隙分配因子）

时间接线器的构成

T 接线器：共享存储器型SE
- 话音存储器（SM，Speech Memory）：暂存话音的数字编码信息
  - 存储单元个数等于 PCM 线路每帧时隙数；每单元至少 8bit（一路话音）
- 控制存储器（CM，Control Memory）
  - 存储单元个数等于 SM；每单元至少$log_2n（n 为时隙数）$比特
- 这俩其实是形成了一个映射，假设是输出控制，那么顺序写入的数据被顺序存储到SM话音存储器中去，数组下标与到来顺序存在一一对应，而CM相当于存储了一个对应关系，把构造的一个新的帧的每个时隙都对应了一个输入时隙的下标，这样根据CM里面的信息就可以按照原来的帧构造一个仅时隙顺序不同的新帧然后发送。
- 如果是输入控制，那么输出的顺序就是SM里面的信息，一毛一样的，相当于输入来的时候就在一边接收一边构造输出的新帧了，它是存的时候看着CM里面的信息存，这种CM刚好是上面那个输出控制的CM横纵坐标反过来。

输出控制：顺序写入、控制读出
- 前半周期写入，后半周期读出（SM）
- 前半周期写入，后半周期读出（CM）

缺点：复用级别越高，对控制电路要求越高，无法达成很大规模；时隙转换延迟不定。

输入控制：
- 前半周期读出，后半周期写入（SM）
- 前半周期写入，后半周期读出（CM）

交换网络

Def:交换网络是由（若干个）交换单元按照一定的拓扑结构拓展而成的。

CLOS网络

假设CLOS网络有M条入线和N条出线,如果M=N,称该CLOS网络为对称的CLOS网络,否则为非对称的CLOS网络。对称的CLOS网络使用广泛，下文介绍的CLOS网络除特别说明一般指对称的CLOS网络。

CLOS网络可以是3级的，5级的，7级的。

严格无阻、可重排无阻公式和构造

3 级 CLOS 严格无阻：$m \geq 2n-1$
why？

3 级 CLOS 可重排无阻：$m \geq n$
（？？没太懂，凭什么这样就可重排了）

TST网络

T接线器只交换时隙，入线和出线都是同一条PCM； S接线器只交换物理线路，不改变时隙

阻塞特性
完全无阻塞的条件：m（内部时隙数）=2n（输入时隙数）

BANYAN 网络

特性：单通路、有阻塞（内部竞争）、基于树形结构所以能自选路由。

我们要讨论的是L级的，规则的，（2x2）的矩形的banyan网络

banyan网络的级数跟几乘几是有关系的：
按照规律进行banyan网络的递归构造
构造 $N \times N$ 的 BANYAN 网络，需要 $\log_2N$ 级，每级 $N/2$ 个 $2\times2$ 交换单元，共 $(N/2)\times \log_2N$ 个。拿两个 $n \times n$ 网络，将 $n$ 个 $2\times 2$ 交换单元作为一级通过混洗连接到前部、或者通过反转混洗连接到尾部

特性

树形结构的特性
- 从banyan的任意
自选路由特性
单通路特性
- 从任意入段到任一出端，有且只有一条通道
内部阻塞特性
- banyan网络的任意一条人线到任意一条出线之间都具有惟一的一条通路,但各入线与出线之间的单通路并非是完全分离的,会有公共的内部链路,因此内部竞争是不可避免的。如图所示,在某一时刻,信息要从人线0交换到出线3,同时还有信息要从入线﹖交换到出线2,所以在这一时刻会在第2级与第3级的公共链路上产生竞争,发生阻塞。banyan是有阻塞的网络。
内部阻塞的解决
- 增加网络级数（如 BENES 网络），每增加一级，通路数翻倍。但同时失去唯一路径和自选路特性。
- 使用扩展型或膨胀型 BANYAN 网络。
- BATCHER-BANYAN（排序-BANYAN）网络：严格无阻塞、结构规整、自动选路。
  - banyan 网络存在着内部竞争,研究表明,如果将banyan网络输入的全部信息按交换的出线地址(也就是选路标签)进行单调递增(或递减)排列,那么就可以解决banyan网络的内部阻塞。为了满足banyan网络的无阻塞条件,可以在banyan 网络前加人排序网络—batcher网络,构成batcher-banyan网络(B-B网络)。
- 减少入线的信息量，加大入线缓存。
- 增加平面数，构造多通道交换网络。（几平面就是几倍的交换单元）
  
  多平面banyan 的每个输人端的信息可以随机地选择某个平面,也可以按负荷均分原则分配到各个平面,还可以广播到所有的平面。显然,平面数越多,内部冲突的机会越少。在一定的入线数目(或出线数目)N值下,平面数增加到–定值后可以得到无阻塞网络。多平面ban-yan 网络可显著提高网络的吞吐量,不仅如此,还可提高网络的可靠性,其中一个交换平面出`错后,并不会影响到整个交换网络的连接,其缺点是硬件结构复杂。

BENES网络

benes网络实际上相当于两个banyan类网络背对背相连接,然后将中间两级合并为1级。由于每个banyan类网络有Ib*N级,因此, benes网络共有21bN一1级。