可重排无阻塞网络课件

二、交换网络二、交换网络1二、交换网络11.交换网络的构成和分类交换网络的构成和分类2.交换单元交换单元q交换单元的基本概念交换单元的基本概念q开关阵列与空间交换单元开关阵列与空间交换单元q共享存储器型的交换单元共享存储器型的交换单元时间交换单元时间交换单元q共享总线型的交换单元共享总线型的交换单元数字交换单元数字交换单元3.交换网络交换网络qCLOS网络网络qTST网络网络qDSN网络网络qBANYAN网络网络主要内容主要内容2交换网络的构成和分类主要内容2 交换交换的基本功能是在任意的入线和出线之间的基本功能是在任意的入线和出线之间建立连接。建立连接。在交换系统中完成这一基本功能的部件就是在交换系统中完成这一基本功能的部件就是交换网络交换网络，它是交换系统的核心。交换网络是由，它是交换系统的核心。交换网络是由若干个交换单元按照一定的若干个交换单元按照一定的拓扑结构拓扑结构和和控制方式控制方式构成的。构成的。交换单元交换单元是构成交换网络的最基本的部件。是构成交换网络的最基本的部件。交换网络有：交换网络有：空分、时分空分、时分 数字、模拟数字、模拟1、交换网络的构成和分类、交换网络的构成和分类3 交换的基本功能是在任意的入线和出线之间建立连接。1、q交换单元的基本概念交换单元的基本概念q开关阵列与空间交换单元开关阵列与空间交换单元q共享存储器型的交换单元共享存储器型的交换单元时间交换单元时间交换单元q共享总线型的交换单元共享总线型的交换单元数字交换单元数字交换单元2、交换单元、交换单元4交换单元的基本概念2、交换单元42.1 交换单元的基本概念交换单元的基本概念入线入线出线出线控制端控制端 状态端状态端M X N的交换单元的交换单元00 11M-1N-152.1 交换单元的基本概念入线出线控制端状态端M入线入线出线出线00 11442323同步时分复用信号的交换同步时分复用信号的交换两种信号的交换两种信号的交换6入线出线00 11442323同步时分复用信号的交换两种信号入线入线出线出线001221异步时分复用信号的交换异步时分复用信号的交换0210001222两种信号的交换两种信号的交换7入线出线00 1221异步时分复用信号的交换02100012交换单元按使用需要的不同可分为交换单元按使用需要的不同可分为：入线入线0M-1出线出线0 N-1入线入线0M-1出线出线0 N-1出线出线0 N-1入线入线0M-1集中型（集中型（MN）扩散型（扩散型（MN）连接型（连接型（M=N）8交换单元按使用需要的不同可分为：入线0M-1出线0 N-1入交换单元按信息流向分为：交换单元按信息流向分为：q有向交换单元：当信息经过交换单元时只能从入线有向交换单元：当信息经过交换单元时只能从入线 进出线出，具有唯一确定的方向。进出线出，具有唯一确定的方向。q无向交换单元：交换单元的每条线即可入也可出，无向交换单元：交换单元的每条线即可入也可出，其入线数必等于出线数。其入线数必等于出线数。出线0 N-1入线0M-1M X N有向交换单元入线/出线0N-1N无向交换单元.9交换单元按信息流向分为：有向交换单元：当信息经过交换单元时只 交换单元的连接特性交换单元的连接特性 连接特性是交换单元的基本特性，它反映了交换单元连接特性是交换单元的基本特性，它反映了交换单元入线到出线的连接能力，通常我们用入线到出线的连接能力，通常我们用连接集合连接集合和和连接函数连接函数来描述交换单元的连接特性来描述交换单元的连接特性q 连接集合：连接集合：入线集合：入线集合：T=0,1,2,M-1T=0,1,2,M-1 出线集合：出线集合：R=0,1,2,N-1R=0,1,2,N-1 定义：定义：tTtT，即即t t是是T T的一个元的一个元 rRtrRt，RtRt是是R R的一个子集，的一个子集，r r是是RtRt的一个元的一个元 则集合则集合 c=t,Rt c=t,Rt 为一个连接。为一个连接。10 交换单元的连接特性 连接特性是交换单元的基本特性若若rRtrRt，RtRt中只含有一个元，则称该连接为点到点中只含有一个元，则称该连接为点到点连接。连接。若若rRtrRt，RtRt中含有多个元，则称该连接为一点到多中含有多个元，则称该连接为一点到多点连接。点连接。若一个交换单元可以提供点到多点的功能，但若一个交换单元可以提供点到多点的功能，但RtRRtR，则称其具有同发功能；若则称其具有同发功能；若Rt=RRt=R，则该交换单元具有则该交换单元具有广播功能。广播功能。交换单元的连接特性交换单元的连接特性11若rRt，Rt中只含有一个元，则称该连接为点到点连接。交 交换单元的连接特性交换单元的连接特性 一个交换单元的连接同时可有多个，这就构成了交一个交换单元的连接同时可有多个，这就构成了交换单元的连接集合：换单元的连接集合：C=c0,c1,c2,其中：起点集其中：起点集 Tc=t;t ci,ci C 终点集终点集 Rc=r;r Rt,Rt ci,ci C q 连接和连接集合是对应于某一时刻的连接和连接集合是对应于某一时刻的q 连接集合的数目越多，连接能力就越强连接集合的数目越多，连接能力就越强12 交换单元的连接特性 一个交换单元的连接同时可有多个，q 连接函数连接函数 一个连接函数对应一种连接，连接函数表示相互一个连接函数对应一种连接，连接函数表示相互连接的入线编号和出线编号之间的一一对应关系，即存连接的入线编号和出线编号之间的一一对应关系，即存在连接函数在连接函数f，入线入线x与出线与出线f(x)相连接，相连接，0 xM-1，0f(x)N-1。连接函数实际上也反映了入线编号构成的数组和出连接函数实际上也反映了入线编号构成的数组和出线编号构成的数组之间的置换关系或排列关系，故连接线编号构成的数组之间的置换关系或排列关系，故连接函数也被称作函数也被称作置换函数置换函数或或排列函数排列函数。交换单元的连接特性交换单元的连接特性13 连接函数 交换单元的连接特性13q 函数表示形式函数表示形式 x x表示入线编号（二进制表示），表示入线编号（二进制表示），f(x)f(x)表表示连接函数。示连接函数。q 排列表示形式排列表示形式 即输入输出对应表示形式即输入输出对应表示形式 t0，t1，t n-1 r0，r1，r n-1q 图形表示形式图形表示形式连接函数的表示形式连接函数的表示形式14 函数表示形式连接函数的表示形式14直线连接：直线连接：函数表示：函数表示：I(xn-1xn-2x1x0)=xn-1xn-2 x1x0 排列表示（排列表示（N=4）：0，1，2，3 0，1，2，3 图形表示（图形表示（N=4）：）：0 00 01 12 23 31 12 23 3 交换单元常用的连接函数交换单元常用的连接函数15直线连接：00123123 交换单元常用的连接函数15交叉连接：交叉连接：函数表示：函数表示：E(xn-1xn-2x1x0)=xn-1xn-2 x1x0 排列表示（排列表示（N=4）：0，1，2，3 1，0，3，2 图形表示（图形表示（N=4）：）：0 00 01 12 23 31 12 23 3 交换单元的连接特性交换单元的连接特性16交叉连接：00123123 交换单元的连接特性16间隔交叉连接：间隔交叉连接：Ck(xn-1xn-2xk x1x0)=xn-1xn-2 xk x1x00 00 01 12 23 31 12 23 30 00 01 12 23 31 12 23 3N=4 k=1N=4 k=1N=4 k=0N=4 k=0 交换单元的连接特性交换单元的连接特性17间隔交叉连接：0012312300123123N=4 k=1均匀洗牌连接：均匀洗牌连接：(xn-1xn-2xk x1x0)=xn-2 xk x1x0 xn-1 0 01 12 23 3N=8N=84 45 56 67 730 01 12 23 34 45 56 67 7 交换单元的连接特性交换单元的连接特性18均匀洗牌连接：0123N=84567301234567 交换蝶式连接：蝶式连接：(xn-1 xn-2xk x1 x0)=x0 xn-2 xk x1 xn-1 0 01 12 23 3N=8N=84 45 56 67 70 01 12 23 34 45 56 67 7 交换单元的连接特性交换单元的连接特性19蝶式连接：0123N=8456701234567 交换单元的交换单元的性能交换单元的性能q 容量：容量：交换单元所有入线可以同时送入的总的信息量交换单元所有入线可以同时送入的总的信息量q 接口：接口：交换单元需要规定自己的信号接口标准，即信号形式、交换单元需要规定自己的信号接口标准，即信号形式、速率及信息流方向速率及信息流方向q 功能：功能：点到点、同发、广播点到点、同发、广播q 质量：质量：完成交换动作的速度、任何情况下是否能完成指定连完成交换动作的速度、任何情况下是否能完成指定连接、信息经过交换单元是否有损伤（时间、语义）接、信息经过交换单元是否有损伤（时间、语义）20交换单元的性能 容量：202.2 开关阵列与空间交换单元开关阵列与空间交换单元开关阵列开关阵列在交换单元内部，要建立任意入线和任意出在交换单元内部，要建立任意入线和任意出线之间的连接，就在每条入线和每条出线之间都线之间的连接，就在每条入线和每条出线之间都各自接上一个开关，所有开关就构成了交换单元各自接上一个开关，所有开关就构成了交换单元内部的内部的开关阵列开关阵列。212.2 开关阵列与空间交换单元开关阵列在交换单元内部，M X N有向交换单元有向交换单元01N-101M-1入线出线M X N有向矩形开关阵列有向矩形开关阵列开关阵列的工作原理开关阵列的工作原理出线0 N-1入线0M-1.22M X N有向交换单元01N-101M-1入线出线M X NN无向方形开关阵列无向方形开关阵列入线入线0 0N-1N-1N无向交换单元无向交换单元0 01 1N-1N-10 01 1N-1N-1入线入线出线出线开关阵列的工作原理开关阵列的工作原理23N无向方形开关阵列入线0N-1N无向交换单元01N-101N入线入线/出线出线0 0N-1N-1N无向交换单元无向交换单元无向交换单元开关阵列的实现（补充）无向交换单元开关阵列的实现（补充）若在一个N X N的交换单元中的连接总是对称的，即如果入端i连接到出端j，则入端j一定连接到出端i，那么相同编号的入端和出端可以看作一个同时具有发送和接收信息能力的信息端，既具有N个双向通信的信息端，并且每个信息端都可以和任何其它的信息端相连，这样的交换单元称作N个信息端的无向交换单元，简称N无向交换单元。24入线/出线0N-1N无向交换单元无向交换单元开关阵列的实现（N无向交换单元的开关阵列无向交换单元的开关阵列（用双向开关）（用双向开关）入线入线/出线出线0 0N-1N-1N无向交换单元无向交换单元0 0 1 1N-2N-21 1N-1N-1无向交换单元开关阵列的实现（补充）无向交换单元开关阵列的实现（补充）2 2N-2N-22 225N无向交换单元的开关阵列入线/出线0N-1N无向交换单元010 0 1 10 01 1N-1N-1N-1N-1无向交换单元开关阵列的实现（补充）无向交换单元开关阵列的实现（补充）入线入线/出线出线0 0N-1N-1N无向交换单元无向交换单元N无向交换单元的开关阵列无向交换单元的开关阵列（用单向开关）（用单向开关）260101N-1N-1无向交换单元开关阵列的实现（补充）入线/无向交换单元开关阵列的实现（补充）无向交换单元开关阵列的实现（补充）若N无向交换单元的N个信息端可以分为两组，分别为K和L个信息端。属于其中一组的信息端都可以和另一组的任何信息端相连接，但是不能和本组中的其它信息端相连，则称其为一个K x L的无向交换单元。入线/出线0 0K-1K-1K x L无向交换单元无向交换单元0 0 L-1L-1入线/出线（信息端）（信息端）27无向交换单元开关阵列的实现（补充）若N无向交换单K X L无向矩形开关阵列无向矩形开关阵列0 01 1L-1L-10 01 1K-1K-1K(K=L)无向方形开关阵列无向方形开关阵列0 01 1K-1K-10 01 1K-1K-1入线/出线0 0K-1K-1K x L无向交换单元无向交换单元0 0 L-1L-1入线/出线（信息端）（信息端）无向交换单元开关阵列的实现（补充）无向交换单元开关阵列的实现（补充）28K X L无向矩形开关阵列01L-101K-1K(K=L)无K X L无向矩形开关阵列无向矩形开关阵列（用双向开关）（用双向开关）0 01 1L-1L-10 01 1K-1K-1无向交换单元开关阵列的实现（补充）无向交换单元开关阵列的实现（补充）(K+L)X(K+L)有向开关阵列有向开关阵列（用单向开关）（用单向开关）0 01 10 01 1K-1K-1K+0K+0K+L-1K+L-1K+0K+0 K+1K+1K+L-1K+L-1K-1K-1K+1K+129K X L无向矩形开关阵列01L-101K-1无向交换单元开K 无向方形开关阵列无向方形开关阵列（用双向开关）（用双向开关）0 01 1K-1K-10 01 1K-1K-1无向交换单元开关阵列的实现（补充）无向交换单元开关阵列的实现（补充）2K X 2K有向开关阵列有向开关阵列（用单向开关）（用单向开关）0 01 10 01 1K-1K-1K+0K+0K+K-1K+K-1K+0K+0 K+1K+1K+K-1K+K-1K-1K-1K+1K+130K 无向方形开关阵列01K-101K-1无向交换单元开关阵列全连接交换单元和部分连接交换单元全连接交换单元和部分连接交换单元0 01 1N-1N-10 01 1N-1N-1入线入线出线出线0 01 1N-1N-10 01 1N-1N-1入线入线出线出线31全连接交换单元和部分连接交换单元01N-101N-1入线出线01M-1入线入线出线出线入线入线0M-1出线出线入线入线0N-1出线出线0 01 1N-1N-1入线入线出线出线多路选择器多路选择器3201M-1入线出线入线0M-1出线入线0N-1出线01N-1开关阵列的特性开关阵列的特性q开关控制简单，从入线到出线具有均匀的单位延迟时开关控制简单，从入线到出线具有均匀的单位延迟时间。间。q开关阵列适合于构成较小的交换单元（开关数反映了开关阵列适合于构成较小的交换单元（开关数反映了实现的复杂度和成本的高低）。实现的复杂度和成本的高低）。q交换单元的性能依赖于所使用的开关。交换单元的性能依赖于所使用的开关。q控制信号简单控制信号简单q容易实现同发和广播功能容易实现同发和广播功能33开关阵列的特性开关控制简单，从入线到出线具有均匀的单位延迟时继电器：其构成的交换单元是无向的，可交换模拟和数字信息，继电器：其构成的交换单元是无向的，可交换模拟和数字信息，干扰和噪声大干扰和噪声大、动作慢（动作慢（msms级）、体积大（级）、体积大（cmcm级）。级）。模拟电子开关：一般利用半导体材料制成。模拟电子开关：一般利用半导体材料制成。如：如：MC142100MC142100、MC145100MC145100（4 x 44 x 4开关阵列）开关阵列）只能单向传送，且衰耗和时延较大。只能单向传送，且衰耗和时延较大。数字电子开关：由简单的由逻辑门构成，用于数字信号的交数字电子开关：由简单的由逻辑门构成，用于数字信号的交 换，开关动作极快且无信号损失。换，开关动作极快且无信号损失。实际的开关阵列实际的开关阵列34继电器：其构成的交换单元是无向的，可交换模拟和数字信息，干扰q通断开关通断开关交叉点可看成是一个具有通/断功能的开关。其具体实现比较复杂，包括FIFO缓冲器和相应的控制逻辑。q多路选择器多路选择器开关阵列交叉点的实现（开关阵列交叉点的实现（1）35通断开关开关阵列交叉点的实现（1）35qCrossbar交叉点是一个2 x 2的传送门，它有两个状态：bar状态和cross状态。Bar状态是指横向输入连到纵向输出，纵向输入连到横向输出；cross状态是指横向输入连到横向输出，纵向输入连到纵向输出。交换矩阵在初始状态时，所有交叉点均处于cross状态，即任何入线与任何出线间均不连通。如果要使入线i与出线j连通，则应使处于交叉点（i,j）上的传送门处于bar状态，而在i行和j列的所有其它的传送门仍处于cross状态。开关阵列交叉点的实现（开关阵列交叉点的实现（2）36Crossbar开关阵列交叉点的实现（2）36横向输入纵向输入纵向输出横向输出bar状态cross状态开关阵列交叉点的实现（开关阵列交叉点的实现（3）37横向输入纵向输入纵向输出横向输出bar状态cross状态开关1234123412341234crossbar通/断开关开关阵列交叉点的实现（开关阵列交叉点的实现（4）381234123412341234crossbar通/断开关开 空间交换单元也称为空间交换单元也称为空间接线器空间接线器（Space Space SwitchSwitch），），简称为简称为S S单元单元或或S S接线器接线器，用来实现，用来实现多个输入复用线与多个输出复用线之间的空间多个输入复用线与多个输出复用线之间的空间交换，而不改变其时隙位置。交换，而不改变其时隙位置。2.3 开关阵列与空间交换单元开关阵列与空间交换单元空间交换单元空间交换单元39 空间交换单元也称为空间接线器（SpaceS S接线器的构成：接线器的构成：交叉点矩阵交叉点矩阵、控制存储器控制存储器交叉点矩阵交叉点矩阵：开关阵列：开关阵列控制存储器控制存储器（CM-Control MemoryCM-Control Memory）：）：q S S接线器所含接线器所含CMCM数量等于入（出）线数数量等于入（出）线数q 每个每个CMCM的所含有的存储单元个数等于入（出）的所含有的存储单元个数等于入（出）线上的复用时隙数线上的复用时隙数q 每个存储单元为每个存储单元为n n位位bit,bit,且满足且满足N2N2n n,其中其中N N 为入（出）线上数为入（出）线上数 空间交换单元的基本结构空间交换单元的基本结构40S接线器的构成：交叉点矩阵、控制存储器空间交换单元的基本结构空间交换单元的控制方式空间交换单元的控制方式0 1 20 1 20 1 2TS12 TS8TS12 TS808121272TS8TS8输入控制方式输入控制方式1TS12TS122041空间交换单元的控制方式0 1 20 1 20空间交换单元的控制方式空间交换单元的控制方式0 1 20 1 20 1 2TS12 TS8TS12 TS808122TS8TS8输出控制方式输出控制方式0TS12TS122012742空间交换单元的控制方式0 1 20 1 20空间交换单元的工作原理空间交换单元的工作原理43空间交换单元的工作原理432.3、共享存储器型的交换单元、共享存储器型的交换单元时间交换单元时间交换单元01N-1输入信号输出信号共享存储器型交换单元的一般结构工作方式：入线缓冲、出线缓冲442.3、共享存储器型的交换单元时间交换单元01N-1输入 时间交换单元也称为时间交换单元也称为时间接线器时间接线器（Time Time SwitchSwitch），），简称为简称为T T单元单元或或T T接线器接线器，用来实现，用来实现时隙交换功能。所谓时隙交换是指入线上各个时隙交换功能。所谓时隙交换是指入线上各个时隙的内容要按照交换连接的需要，分别在出时隙的内容要按照交换连接的需要，分别在出线上的不同时隙位置输出。线上的不同时隙位置输出。时间交换单元时间交换单元45 时间交换单元也称为时间接线器（Time Switch），简T T接线器主要由接线器主要由话音存储器话音存储器（SM:Speech SM:Speech MemoryMemory）和和控制存储器控制存储器(CM:Control memory)CM:Control memory)构成。构成。SMSM用来暂存话音的数字编码信息，故每个单用来暂存话音的数字编码信息，故每个单元至少应为元至少应为8 8比特。比特。SMSM的容量等于输入复用线上每的容量等于输入复用线上每帧的时隙数。帧的时隙数。CMCM的容量等于的容量等于SMSM的容量；设的容量；设CMCM每个单元的比每个单元的比特数为特数为n n，SMSM的单元数为的单元数为N N，则有则有2 2n n=N=N，N N也就是复也就是复用线上的时隙数。用线上的时隙数。时间交换单元的基本结构时间交换单元的基本结构46T接线器主要由话音存储器（SM:Speech Memory）时间交换单元的控制方式时间交换单元的控制方式47时间交换单元的控制方式472.4、共享总线型交换单元、共享总线型交换单元数字交换单元数字交换单元482.4、共享总线型交换单元数字交换单元48入线控制部件的功能入线控制部件的功能：接收入线信号，进行相应的格式变换，放在缓冲存接收入线信号，进行相应的格式变换，放在缓冲存储器中，并在分配给该部件的时隙上把收到的信息送到储器中，并在分配给该部件的时隙上把收到的信息送到总线上。总线上。出线控制部件的功能出线控制部件的功能：检测总线上的信号，并把属于自己的信息读入一个检测总线上的信号，并把属于自己的信息读入一个缓冲存储器中，进行格式变换，放在缓冲存储器中，由缓冲存储器中，进行格式变换，放在缓冲存储器中，由出线送出，形成出线信号。出线送出，形成出线信号。共享总线型交换单元共享总线型交换单元49入线控制部件的功能：共享总线型交换单元49总线总线：一般包括多条数据线和控制线。数据线用于在入线一般包括多条数据线和控制线。数据线用于在入线控制部件和出线控制部件传送信号；控制线用于控制各控制部件和出线控制部件传送信号；控制线用于控制各入线控制部件获得时隙和发送信息，以及出线控制部件入线控制部件获得时隙和发送信息，以及出线控制部件读取属于自己的信息。读取属于自己的信息。总线按时隙轮流分配给各个入线控制部件和出线控总线按时隙轮流分配给各个入线控制部件和出线控制部件使用，其时隙的分配有一定的规则。制部件使用，其时隙的分配有一定的规则。共享总线型交换单元共享总线型交换单元50总线：共享总线型交换单元50数字交换单元（数字交换单元（DSE）51数字交换单元（DSE）51数字交换单元（数字交换单元（DSE）的工作原理的工作原理STS18STS12端口RAM话路RAM数据RAM00031D3131P C121218818S52数字交换单元（DSE）的工作原理STS18STS12端口RA3、交换网络、交换网络交换网络交换网络是由若干个交换单元按照一定的拓是由若干个交换单元按照一定的拓扑结构和控制方式构成的网络。扑结构和控制方式构成的网络。交换网络的三个基本要素是：交换网络的三个基本要素是：交换单元交换单元、不、不同交换单元间的同交换单元间的拓扑连接拓扑连接和和控制方式控制方式。533、交换网络交换网络是由若干个交换单元按照一定的拓扑结构和控交换网络的一般结构交换网络的一般结构控制单元出线入线交换单元交换单元交换单元交换单元交换网络54交换网络的一般结构控制单元出线入线交换单元交换单元交单级交换网络和多级交换网络单级交换网络和多级交换网络交换网络按拓扑连接方式可分为：单级交换网络交换网络按拓扑连接方式可分为：单级交换网络 多级交换网络多级交换网络出线出线0 N-1入线入线0M-1单级交换网络单级交换网络交换交换单元单元55单级交换网络和多级交换网络交换网络按拓扑连接方式可分为：单级单级交换网络和多级交换网络单级交换网络和多级交换网络 如果一个交换网络中的交换单元可以分为如果一个交换网络中的交换单元可以分为N级，顺序命级，顺序命名为第名为第1,2,N级，并且满足：级，并且满足：所有入线都只与第所有入线都只与第1级交换单元连接；级交换单元连接；所有第所有第1级交换单元都只与入线和第级交换单元都只与入线和第2级交换单元连接；级交换单元连接；所有第所有第2级交换单元都只与第级交换单元都只与第1级和第级和第3级交换单元连接；级交换单元连接；依此类推，所有第依此类推，所有第N级交换单元都只与第级交换单元都只与第N-1级和出线级和出线连接；连接；则称这样的交换网络为则称这样的交换网络为多级交换网络多级交换网络，或，或N级交换网络级交换网络。56单级交换网络和多级交换网络 如果一个交换网络中的多级交换网络的拓扑结构可用三个参数来说明：多级交换网络的拓扑结构可用三个参数来说明：每个交换单元的容量每个交换单元的容量 交换单元的级数交换单元的级数 交换单元间的连接通路（链路）交换单元间的连接通路（链路）单级交换网络和多级交换网络单级交换网络和多级交换网络57多级交换网络的拓扑结构可用三个参数来说明：单级交换网络和多级多级交换网络多级交换网络(nm x nm两级交换网络两级交换网络)O1n-1O1n-1O1n-1O1m-1O1m-1O1m-1OO11m-1n-1 1级级2级级58多级交换网络(nm x nm两级交换网络)O1n-多级交换网络的内部阻塞多级交换网络的内部阻塞 若出、入线空闲，但因交换网络级间链路被占用而若出、入线空闲，但因交换网络级间链路被占用而无法接通的现象，称为多级交换网络的内部阻塞。无法接通的现象，称为多级交换网络的内部阻塞。严格无阻塞网络严格无阻塞网络：不管网络处于何种状态，任何时刻都可以在交换网不管网络处于何种状态，任何时刻都可以在交换网络中建立一个连接，只要这个连接的起点、终点是空闲络中建立一个连接，只要这个连接的起点、终点是空闲的，而不会影响网络中已建立起来的连接。的，而不会影响网络中已建立起来的连接。59多级交换网络的内部阻塞 若出、入线空闲，但因交换网可重排无阻塞网络可重排无阻塞网络：不管网络处于何种状态，任何时刻都可以在交换网络不管网络处于何种状态，任何时刻都可以在交换网络中直接或对已有的连接重选路由来建立一个连接，只要这中直接或对已有的连接重选路由来建立一个连接，只要这个连接的起点、终点是空闲的，而不会影响网络中已建立个连接的起点、终点是空闲的，而不会影响网络中已建立起来的连接。起来的连接。广义无阻塞网络广义无阻塞网络：指一个给定的网络存在着固有的阻塞可能，但又可能指一个给定的网络存在着固有的阻塞可能，但又可能存在着一种精巧的选路方法，使得所有的阻塞均可避免，存在着一种精巧的选路方法，使得所有的阻塞均可避免，而不必重新安排网络中已建立起来的连接。而不必重新安排网络中已建立起来的连接。多级交换网络的内部阻塞多级交换网络的内部阻塞60可重排无阻塞网络：多级交换网络的内部阻塞601 13 34 42 21 13 34 42 2C1C1C2C21，2，3，44，2，1，3 可重排无阻塞网络可重排无阻塞网络6113421342C1C1C2C21，2，3，4可重排无阻塞网1 13 34 42 21 13 34 42 2C1C1cc2cc2可重排无阻塞网络可重排无阻塞网络6213421342C1C1cc2cc2可重排无阻塞网络623.1 CLOS网络网络 为了减少交叉点总数而同时具有严格的无阻塞特性，为了减少交叉点总数而同时具有严格的无阻塞特性，CLOS C.很早就提出一种多级结构，推出了严格无阻塞的很早就提出一种多级结构，推出了严格无阻塞的条件，这就是著名的条件，这就是著名的CLOS网络。网络。1 1n n1 1n n1 1n n1 1n n1 11 1m m 1 1r r1 11 1 r rm mm mm mm m1 11 11 11 11 11 11 11 1r rr rr rr r3级级CLOS网络网络633.1 CLOS网络 为了减少交叉点总数而同时具在最坏情况下，中间级会有（在最坏情况下，中间级会有（n-1）X 2个交换单元被个交换单元被占用，因此中间级至少要有（占用，因此中间级至少要有（n-1）X 2+1=2n-1个交换个交换单元，即单元，即m2n-1时，可确保无阻塞（严格无阻塞）。时，可确保无阻塞（严格无阻塞）。CLOS网络网络64在最坏情况下，中间级会有（n-1）X 2个交换单元被占用，因3.2 TST网络网络TST网络是在电路交换系统中经常使用的一种交换网网络是在电路交换系统中经常使用的一种交换网络，它是三级交换网络，两侧为络，它是三级交换网络，两侧为T接线器，中间一级为接线器，中间一级为S接线器，接线器，S级的出入线数决定于两侧级的出入线数决定于两侧T接线器的数量。接线器的数量。第第1级级T接线器：负责输入母线的时隙交换。接线器：负责输入母线的时隙交换。S接线器：负责母线之间的空间交换。接线器：负责母线之间的空间交换。第第2级级T接线器：负责输出母线的时隙交换。接线器：负责输出母线的时隙交换。653.2 TST网络TST网络是在电路交换系统中经常使用的一1 2 31 2 31 2 3TS2TS310723313TS2TS31S(输入控制输入控制)TS7TS231031272031312323 2231731CMACMASMASMASMBSMBCMBCMBTS23TS7T(输出控制输出控制)T(输入控制输入控制)ABAB661 2 31 2 为减少选路次数，简化控制，可使两个方向的内部时为减少选路次数，简化控制，可使两个方向的内部时隙具有一定的对应关系，通常可相差半帧，俗称隙具有一定的对应关系，通常可相差半帧，俗称反相法反相法，即：即：设：设：Nf=一帧的时隙数一帧的时隙数 Na=A到到B方向的内部时隙数方向的内部时隙数 Nb=B到到A方向的内部时隙数方向的内部时隙数则：则：Nb=Na+Nf/2TST网络完全无阻塞的条件：网络完全无阻塞的条件：m（内部时隙数）内部时隙数）=2n（输入时隙数）输入时隙数）3.2 TST网络网络67为减少选路次数，简化控制，可使两个方向的内部时隙具有一定的对关于关于T-S组合网络组合网络T-S(n)-TT-S-T网络：网络：AXE10，FETEX-150，E10B，5ESS等等T-S-S-T网络：网络：NEAX61T-S-S-S-T网络：网络：EWSDT-S-S-S-S-T网络：网络：4ESS(长途长途)S-T(n)-S68关于T-S组合网络T-S(n)-T683.3 BANYAN 网络网络qBanyan 网络的基本结构网络的基本结构qBanyan 网络的基本特性网络的基本特性qBATCHER-BANYAN网络网络q基于基于banyan的多通路结构的多通路结构qBenes网络网络693.3 BANYAN 网络Banyan 网络的基本结构69banyan网络可分为一些子类，L级banyan是其中的一类，其特征是只有相邻级之间才有链路相连，即任何输入到任何输出之间的通路都经过L级。L级banyan网络又可分为规则banyan和不规则banyan。规则banyan是指构成banyan网络的各个交换单元都是等同的，而不规则banyan则不然。如果规则banyan中的各个交换单元不仅是等同的，而且每个交换单元的入线数等于出线数，则称此规则banyan为矩形banyan。1、Banyan 网络的基本结构网络的基本结构70banyan网络可分为一些子类，L级banyan是其中的一类 通常将由2 X 2的交换单元构成的单通路网络称为banyan网络。banyan网络是基于树型的拓扑结构，但每一个交换单元却是基于crossbar的结构。2 X 2的交换单元也具有bar和cross两种状态。1、Banyan 网络的基本结构网络的基本结构71 通常将由2 X 2的交换单元构成的单通路网络称为banya01234567012345678 x 8的的3级级banyan网络网络72012345670124678 x 8的3级banyan网络树型结构特性树型结构特性：从banyan的任一输入端口引出的一组通路形成了2分支树，级数越多，分支越多，级数k=2N，N=总入线数/出线数，即2k=N。单通路特性单通路特性：banyan的任一入端到任一出端之间，具有1条且仅有一条通路。自选路由特性自选路由特性：自选路由，即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应于出端号的二进制码的选路标签来自动选路。2、Banyan 网络的基本特性网络的基本特性73树型结构特性：2、Banyan 网络的基本特性7301234567012(010)3(011)4(100)5(101)678 x 8的3级banyan网络10110(011)(010)(100)(101)Banyan网络的自选路由特性网络的自选路由特性7401234567012(010)4(100)678 x 8的可扩展性可扩展性：banyan的构成具有一定的规律，可以采用有规则的扩展方法将较小容量的banyan扩展成较大规模。已有N X N的BANYAN网络，需构成2N X 2N的BANYAN网络，则可用2组N X N，再加上一组N个2X2交换单元构成。第一组的N X N的N条出线分别与N个2X2交换单元的某一入线相连，第二组的N X N的N条出线分别与N个2X2交换单元的另一入线相连。内部竟争性内部竟争性：banyan是具有内部竞争的有阻塞网络。2、Banyan 网络的基本特性网络的基本特性75可扩展性：2、Banyan 网络的基本特性7516X16BANYAN交换网络的构成Banyan网络的可扩展性网络的可扩展性7616X16BANYAN交换网络的构成Banyan网络的可扩展16X16BANYAN交换网络的构成Banyan网络的可扩展性网络的可扩展性7716X16BANYAN交换网络的构成Banyan网络的可扩展1）内部阻塞是在2X2交换单元的两条入线要向同一个出线上发送信元时产生的，最坏情况下概率为50%，若减少入线上的信息量，就可减少阻塞的概率，故可通过适当限制入线上的信息量或加大缓冲存储器来减少内部阻塞。2）可以通过增加多级交换网络的级数来消除内部阻塞。已有证明，若要完全消除N X N的banyan网络的内部阻塞，至少需要22N-1级。3）可以增加banyan网的平面树，构成多通道交换网络。4）使用排序-banyan网络。解决内部阻塞的方法解决内部阻塞的方法781）内部阻塞是在2X2交换单元的两条入线要向同一个出线上发送 该网络也简称为B-B网，是由BATCHER排序网和BANYAN网组成，它成功地避免了BANYAN网络的内部阻塞，这是目前ATM交换机使用较多的一种网络。BATCHER排序网是由2X2的比较器（BATCHER比较器）构成的。xymin(x,y)max(x,y)xymin(x,y)max(x,y)3、BATCHER-BANYAN网络网络79 该网络也简称为B-B网，是由BATCHER排序BATCHER-BANYAN网络011111010100011010100111111100010011BATCHER-BANYAN网络网络01111111101101111101010010001080BATCHER-BANYAN网络01111101010001 为了减少或消除banyan的内部阻塞，提高吞吐率，除了构成B-B网络之外，还可以构成基于banyan的的各种多通路网络。（1）增长型banyan 增长型banyan就是前面加上分配级，以扩大每个入端的选择范围，从而形成多通路网络。每增加1级，每个入端与每个出端之间的通路数就增加1倍。前置分配级还可以使业务流均衡地进入banyan的入端，减少banyan对流入的业务流模型的敏感性。4、基于、基于BANYAN的多通路结构的多通路结构81 为了减少或消除banyan的内部阻塞，提高吞0123456701234567增长型banyan增长型增长型BANYAN8201234567012467增长型banyan增长型BANY（2）扩展型banyan 考察banyan中的交换单元，对应于每个交换单元输出地址有1条链路，如果使每个输出地址有d条链路，也就是可以任意选择d条中的1条，就称为扩展型banyan。在扩展型banyan网中，22的交换单元变成了2d2d的交换单元。但输出地址并非2d个，而仍然是2个，只要用1个比特来区别。于是在任何时刻，最多可有d个信息单元传送到交换单元的每个输出；如果对应于同一输出地址同时有多于d个的信元到达，只能传送其中的d个。4、基于、基于BANYAN的多通路结构的多通路结构83（2）扩展型banyan4、基于BANYAN的多通路结构830123456701234567扩展型banyan扩展型扩展型BANYAN8401246701234567扩展型banyan扩展型BANY（3）膨胀型banyan 膨胀型banyan是膨胀度d在各级可以变化的扩展型banyan。（4）复份型banyan 复份型banyan是将若干个相同的banyan并接在一起，形成多平面的网络结构。从复份型banyan的每个输入端进入的信息单元，可以随机地选择某个平面，也可以按负荷均分原则分配到各个平面，还可以广播到所有的平面。4、基于、基于BANYAN的多通路结构的多通路结构85（3）膨胀型banyan4、基于BANYAN的多通路结构850123456701234567膨胀型banyand=2d=3d=4膨胀型膨胀型BANYAN8601246701234567膨胀型banyand=2d=3dBanyan 1Banyan 2Banyan r12n12n复份型banyan复份型复份型BANYAN87Banyan 1Banyan 2Banyan r benes网络是著名的多通路网络，具有再配置无阻塞的特点。可 以 看 出，Benes网 络 实 际 上 相 当 于 两 个banyan（banyan与反转banyan）的背对背相连，并将中间相邻两级合并为1级。由于每个banyan有log2 N级，因此Benes网络共有2log2 N-1级。benes网络的构成也有一定的规律。使用2X2交换单元的N X N benes网络的构成方法为：两侧各有N/2个2X2交换单元，中间为两个N/2 X N/2的子网络，每个交换单元以一条链路连到每个子网络；再将中间子网络按上述方法继续分解，直到中间子网络就是2X2交换单元为止。4、BENES网络网络88 benes网络是著名的多通路网络，具有再配置无01234567012345678 X 8 benes网络8 X8 BENES 网络网络89012345670124678 X 8 benes网络8 X0123456701234567benes网络构成方法N/2 X N/2N/2 X N/2BENES 网络构成方法网络构成方法9001234567012467benes网络构成方法N/2 X本章小结本章小结 描述交换单元连接特性的方法 交换单元的外部特性描述的描述指标 三种典型的交换单元的结构、特性及工作原理 无阻塞网络的概念，构成无阻塞网络的方法 TST、CLOS、BANYAN网络的结构及特性91本章小结 描述交换单元连接特性的方法91