北京邮电大学计算机科学与技术学院 卞佳丽二、交换网络二、交换网络北京邮电大学计算机科学与技术学院 卞佳丽1.交交换网网络的构成和分的构成和分类2.交交换单元元3.交交换单元的根本概念元的根本概念4.开关开关阵列与空列与空间交交换单元元5.共享存共享存储器型的交器型的交换单元元时间交交换单元元6.共享共享总线型的交型的交换单元元数字交数字交换单元元7.交交换网网络8.CLOS网网络9.TST网网络10.DSN网网络11.BANYAN网网络主要内容主要内容北京邮电大学计算机科学与技术学院 卞佳丽 交换的根本功能是在恣意的入线和出线之间交换的根本功能是在恣意的入线和出线之间建立衔接。建立衔接。 在交换系统中完成这一根本功能的部件就是在交换系统中完成这一根本功能的部件就是交换网络，它是交换系统的中心。交换网络是由交换网络，它是交换系统的中心。交换网络是由假设干个交换单元按照一定的拓扑构造和控制方假设干个交换单元按照一定的拓扑构造和控制方式构成的。式构成的。 交换单元是构成交换网络的最根本的部件。交换单元是构成交换网络的最根本的部件。 交换网络有：空分、时分交换网络有：空分、时分 数字、模拟数字、模拟1、交换网络的构成和分类、交换网络的构成和分类北京邮电大学计算机科学与技术学院 卞佳丽q交交换单元的根本概念元的根本概念q开关开关阵列与空列与空间交交换单元元q共享存共享存储器型的交器型的交换单元元时间交交换单元元q共享共享总线型的交型的交换单元元数字交数字交换单元元2、交换单元、交换单元北京邮电大学计算机科学与技术学院 卞佳丽2.1 交换单元的根本概念交换单元的根本概念入线入线出线出线控制端控制端 形状端形状端M X N的交换单元的交换单元00 11M-1N-1北京邮电大学计算机科学与技术学院 卞佳丽入线入线出线出线00 11442323同步时分复用信号的交换同步时分复用信号的交换两种信号的交换两种信号的交换北京邮电大学计算机科学与技术学院 卞佳丽入线入线出线出线001221异步时分复用信号的交换异步时分复用信号的交换0210001222两种信号的交换两种信号的交换北京邮电大学计算机科学与技术学院 卞佳丽交换单元按运用需求的不同可分为：交换单元按运用需求的不同可分为：入线入线0M-1出线出线0 N-1入线入线0M-1出线出线0 N-1出线出线0 N-1入线入线0M-1集中型集中型MN分散型分散型MN 衔接型衔接型M=N北京邮电大学计算机科学与技术学院 卞佳丽交换单元按信息流向分为：交换单元按信息流向分为：q有向交换单元：当信息经过交换单元时只能从入线有向交换单元：当信息经过交换单元时只能从入线 q 进出线出，具有独一确定的方进出线出，具有独一确定的方向。向。q无向交换单元：交换单元的每条线即可入也可出，无向交换单元：交换单元的每条线即可入也可出，q 其入线数必等于出现数。其入线数必等于出现数。出线0 N-1入线0M-1M X N有向交换单元入线/出线0N-1N无向交换单元.北京邮电大学计算机科学与技术学院 卞佳丽 交换单元的衔接特性交换单元的衔接特性 衔接特性是交换单元的根本特性，它反映了交换单元入线到出线的衔接才干，通常我们用衔接集合和衔接函数来描画交换单元的衔接特性 衔接集合： 入线集合：T=0,1,2,M-1 出线集合：R=0,1,2,N-1 定义：tT，即t是T的一个元 rRt，Rt是R的一个子集，r是Rt的一个元 那么集合 c=t,Rt 为一个衔接。北京邮电大学计算机科学与技术学院 卞佳丽假假设rRtrRt，RtRt中只含有一个元，那么称中只含有一个元，那么称该衔接接为点点到点到点衔接。接。假假设rRtrRt，RtRt中含有多个元，那么称中含有多个元，那么称该衔接接为一点一点到多点到多点衔接。接。假假设一个交一个交换单元可以提供点到多点的功能，但元可以提供点到多点的功能，但RtRRtR，那么称其具有同，那么称其具有同发功能；假功能；假设Rt=RRt=R，那么，那么该交交换单元具有广播功能。元具有广播功能。 交换单元的衔接特性交换单元的衔接特性北京邮电大学计算机科学与技术学院 卞佳丽 交换单元的衔接特性交换单元的衔接特性 一个交一个交换单元的元的衔接同接同时可有多个，可有多个，这就构成了交就构成了交换单元的元的衔接集合：接集合： C=c0, c1, c2, C=c0, c1, c2, 其中：起点集其中：起点集 Tc=t; tci, ci Tc=t; tci, ciCC 终点集点集 Rc=r; rRt, Rt Rc=r; rRt, Rt ci , ci , ci ci C C 衔接和接和衔接集合是接集合是对应于某一于某一时辰的辰的 衔接集合的数目越多，接集合的数目越多，衔接才干就越接才干就越强北京邮电大学计算机科学与技术学院 卞佳丽q 衔接函数q 一个衔接函数对应一种衔接，衔接函数表示相互衔接的入线编号和出线编号之间的一一对应关系，即存在衔接函数f，入线x与出线f(x)相衔接，0xM-1，0f(x)N-1。q 衔接函数实践上也反映了入线编号构成的数组和出线编号构成的数组之间的置换关系或陈列关系，故衔接函数也被称作置换函数或陈列函数。 交换单元的衔接特性交换单元的衔接特性北京邮电大学计算机科学与技术学院 卞佳丽q 函数表示方式函数表示方式q x x表示入表示入线编号二号二进制表示，制表示，f(x)f(x)表表示示衔接函数。接函数。q 陈列表示方式列表示方式q 即即输入入输出出对应表示方式表示方式q t0 t0，t1t1，t n-1t n-1q r0 r0，r1r1，r n-1r n-1q 图形表示方式形表示方式衔接函数的表示方式衔接函数的表示方式北京邮电大学计算机科学与技术学院 卞佳丽直直线衔接：接： 函数表示：函数表示：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 交换单元常用的衔接函数交换单元常用的衔接函数北京邮电大学计算机科学与技术学院 卞佳丽交叉交叉衔接：接： 函数表示：函数表示：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 交换单元的衔接特性交换单元的衔接特性北京邮电大学计算机科学与技术学院 卞佳丽间隔交叉隔交叉衔接：接： 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 交换单元的衔接特性交换单元的衔接特性北京邮电大学计算机科学与技术学院 卞佳丽均匀洗牌均匀洗牌衔接：接： (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 交换单元的衔接特性交换单元的衔接特性北京邮电大学计算机科学与技术学院 卞佳丽蝶式蝶式衔接：接： (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 交换单元的衔接特性交换单元的衔接特性北京邮电大学计算机科学与技术学院 卞佳丽交换单元的性能交换单元的性能q 容量：容量：q 交换单元一切入线可以同时送入的总的信息量交换单元一切入线可以同时送入的总的信息量q 接口：接口：q 交换单元需求规定本人的信号接口规范，即信号方式、交换单元需求规定本人的信号接口规范，即信号方式、速率及信息流方向速率及信息流方向q 功能：功能：q 点到点、同发、广播点到点、同发、广播q 质量：质量：q 完成交换动作的速度、任何情况下能否能完成指定衔完成交换动作的速度、任何情况下能否能完成指定衔接、信息经过交换单元能否有损伤时间、语义接、信息经过交换单元能否有损伤时间、语义北京邮电大学计算机科学与技术学院 卞佳丽2.2 开关开关阵列与空列与空间交交换单元元开关开关阵列列在交换单元内部，要建立恣意入线和恣意出在交换单元内部，要建立恣意入线和恣意出线之间的衔接，就在每条入线和每条出线之间都线之间的衔接，就在每条入线和每条出线之间都各自接上一个开关，一切开关就构成了交换单元各自接上一个开关，一切开关就构成了交换单元内部的开关阵列。内部的开关阵列。北京邮电大学计算机科学与技术学院 卞佳丽M X N有向交换单元有向交换单元01N-101M-1入线出线M X N有向矩形开关阵列有向矩形开关阵列开关阵列的任务原理开关阵列的任务原理出线0 N-1入线0M-1.北京邮电大学计算机科学与技术学院 卞佳丽N无向方形开关阵列无向方形开关阵列入线入线0 0N-1N-1N无向交换单元无向交换单元0 01 1N-1N-10 01 1N-1N-1入线入线出线出线开关阵列的任务原理开关阵列的任务原理北京邮电大学计算机科学与技术学院 卞佳丽入线入线/ /出线出线0 0N-1N-1N无向交换单元无向交换单元无向交换单元开关阵列的实现补充无向交换单元开关阵列的实现补充 假设在一个N X N的交换单元中的衔接总是对称的，即假设入端i衔接到出端j，那么入端j一定衔接到出端i，那么一样编号的入端和出端可以看作一个同时具有发送和接纳信息才干的信息端，既具有N个双向通讯的信息端，并且每个信息端都可以和任何其它的信息端相连，这样的交换单元称作N个信息端的无向交换单元，简称N无向交换单元。北京邮电大学计算机科学与技术学院 卞佳丽N无向交换单元的开关阵列无向交换单元的开关阵列用双向开关用双向开关入线入线/ /出线出线0 0N-1N-1N无向交换单元无向交换单元0 0 1 1N-2N-21 1N-1N-1无向交换单元开关阵列的实现补充无向交换单元开关阵列的实现补充2 2N-2N-22 2北京邮电大学计算机科学与技术学院 卞佳丽0 0 1 10 01 1N-1N-1N-1N-1无向交换单元开关阵列的实现补充无向交换单元开关阵列的实现补充入线入线/ /出线出线0 0N-1N-1N无向交换单元无向交换单元N无向交换单元的开关阵列无向交换单元的开关阵列用单向开关用单向开关北京邮电大学计算机科学与技术学院 卞佳丽无向交换单元开关阵列的实现补充无向交换单元开关阵列的实现补充 假设N无向交换单元的N个信息端可以分为两组，分别为K和L个信息端。属于其中一组的信息端都可以和另一组的任何信息端相衔接，但是不能和本组中的其它信息端相连，那么称其为一个K x L的无向交换单元。入线/出线0 0K-1K-1K x L无向交换单元无向交换单元0 0 L-1L-1入线/出线信息端信息端北京邮电大学计算机科学与技术学院 卞佳丽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入线/出线信息端信息端无向交换单元开关阵列的实现补充无向交换单元开关阵列的实现补充北京邮电大学计算机科学与技术学院 卞佳丽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+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+1北京邮电大学计算机科学与技术学院 卞佳丽全衔接交换单元和部分衔接交换单元全衔接交换单元和部分衔接交换单元0 01 1N-1N-10 01 1N-1N-1入线入线出线出线0 01 1N-1N-10 01 1N-1N-1入线入线出线出线北京邮电大学计算机科学与技术学院 卞佳丽01M-1入线入线出线出线入线入线0M-1出线出线入线入线0N-1出线出线0 01 1N-1N-1入线入线出线出线多路选择器多路选择器北京邮电大学计算机科学与技术学院 卞佳丽开关阵列的特性开关阵列的特性q开关控制简单，从入线到出线具有均匀的单位延迟时开关控制简单，从入线到出线具有均匀的单位延迟时间。间。q开关阵列适宜于构成较小的交换单元开关数反映了开关阵列适宜于构成较小的交换单元开关数反映了实现的复杂度和本钱的高低。实现的复杂度和本钱的高低。q交换单元的性能依赖于所运用的开关。交换单元的性能依赖于所运用的开关。q控制信号简单控制信号简单q容易实现同发和广播功能容易实现同发和广播功能北京邮电大学计算机科学与技术学院 卞佳丽继电器：其构成的交换单元是无向的，可交换模拟和数字信息，继电器：其构成的交换单元是无向的，可交换模拟和数字信息，干扰和噪声大、动作慢干扰和噪声大、动作慢msms级、体积大级、体积大cmcm级。级。模拟电子开关：普通利用半导体资料制成。模拟电子开关：普通利用半导体资料制成。 如：如：MC142100MC142100、MC145100MC1451004 x 44 x 4开关阵列开关阵列 只能单向传送，且衰耗和时延较大。只能单向传送，且衰耗和时延较大。数字电子开关：由简单的由逻辑门构成，用于数字信号的交数字电子开关：由简单的由逻辑门构成，用于数字信号的交 换，开关动作极快且无信号损失。换，开关动作极快且无信号损失。实践的开关阵列实践的开关阵列北京邮电大学计算机科学与技术学院 卞佳丽q通断开关通断开关q交叉点可看成是一个具有通交叉点可看成是一个具有通/断功能的开断功能的开关。其详细实现比较复杂，包括关。其详细实现比较复杂，包括FIFO缓冲缓冲器和相应的控制逻辑。器和相应的控制逻辑。 q多路选择器多路选择器开关阵列交叉点的实现开关阵列交叉点的实现1北京邮电大学计算机科学与技术学院 卞佳丽qCrossbarq交叉点是一个交叉点是一个2 x 2的传送门，它有两个的传送门，它有两个形状：形状：bar形状和形状和cross形状。形状。Bar形状是指形状是指横向输入连到纵向输出，纵向输入连到横向横向输入连到纵向输出，纵向输入连到横向输出；输出；cross形状是指横向输入连到横向输形状是指横向输入连到横向输出，纵向输入连到纵向输出。出，纵向输入连到纵向输出。q交换矩阵在初始形状时，一切交叉点均交换矩阵在初始形状时，一切交叉点均处于处于cross形状，即任何入线与任何出线间形状，即任何入线与任何出线间均不连通。假设要使入线均不连通。假设要使入线i与出线与出线j连通，那连通，那么应使处于交叉点么应使处于交叉点i,j上的传送门处于上的传送门处于bar形状，而在形状，而在i行和行和j列的一切其它的传送列的一切其它的传送门仍处于门仍处于cross形状。形状。开关阵列交叉点的实现开关阵列交叉点的实现2北京邮电大学计算机科学与技术学院 卞佳丽横向输入纵向输入纵向输出横向输出bar形状cross形状开关阵列交叉点的实现开关阵列交叉点的实现3北京邮电大学计算机科学与技术学院 卞佳丽1234123412341234crossbar通/断开关开关阵列交叉点的实现开关阵列交叉点的实现4北京邮电大学计算机科学与技术学院 卞佳丽 空间交换单元也称为空间接线器空间交换单元也称为空间接线器Space Switch，简称为，简称为S单元或单元或S接线器，用来实现多个输接线器，用来实现多个输入复用线与多个输出复用线之间的空间交换，而不改动入复用线与多个输出复用线之间的空间交换，而不改动其时隙位置。其时隙位置。2.3 开关开关阵列与空列与空间交交换单元元空空间交交换单元元北京邮电大学计算机科学与技术学院 卞佳丽S S接接线线器的构成：交叉点矩器的构成：交叉点矩阵阵、控制存、控制存储储器器交叉点矩交叉点矩阵阵：开关：开关阵阵列列控制存控制存储储器器 CM-Control MemoryCM-Control Memory ： S S接接线线器所含器所含CMCM数量等于入数量等于入 出出 线线数数 每个每个CMCM的所含有的存的所含有的存储单储单元个数等于入元个数等于入 出出 线线上的复用上的复用时时隙数隙数 每个存每个存储单储单元元为为n n位位bit,bit,且且满满足足N2n,N2n,其中其中N N 为为入入 出出 线线上数上数 空间交换单元的根本构造空间交换单元的根本构造北京邮电大学计算机科学与技术学院 卞佳丽空间交换单元的控制方式空间交换单元的控制方式0 1 20 1 20 1 2TS12 TS8TS12 TS808121272TS8TS8输入控制方式输入控制方式1TS12TS1220北京邮电大学计算机科学与技术学院 卞佳丽空间交换单元的控制方式空间交换单元的控制方式0 1 20 1 20 1 2TS12 TS8TS12 TS808122TS8TS8输出控制方式输出控制方式1TS12TS1220127北京邮电大学计算机科学与技术学院 卞佳丽空间交换单元的任务原理空间交换单元的任务原理北京邮电大学计算机科学与技术学院 卞佳丽2.3、共享存、共享存储器型的交器型的交换单元元时间交交换单元元01N-1输入信号输出信号共享存储器型交换单元的普通构造任务方式：入线缓冲、出线缓冲北京邮电大学计算机科学与技术学院 卞佳丽 时间交换单元也称为时间接线器Time Switch，简称为T单元或T接线器，用来实现时隙交换功能。所谓时隙交换是指入线上各个时隙的内容要按照交换衔接的需求，分别在出线上的不同时隙位置输出。时间交换单元时间交换单元北京邮电大学计算机科学与技术学院 卞佳丽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，那么有，那么有2n=N2n=N，N N也就是也就是复用线上的时隙数。复用线上的时隙数。时间交换单元的根本构造时间交换单元的根本构造北京邮电大学计算机科学与技术学院 卞佳丽时间交换单元的控制方式时间交换单元的控制方式北京邮电大学计算机科学与技术学院 卞佳丽2.4、共享、共享总线型交型交换单元元数字交数字交换单元元北京邮电大学计算机科学与技术学院 卞佳丽入线控制部件的功能：入线控制部件的功能： 接纳入线信号，进展相应的格式变换，放在缓冲存接纳入线信号，进展相应的格式变换，放在缓冲存储器中，并在分配给该部件的时隙上把收到的信息送到储器中，并在分配给该部件的时隙上把收到的信息送到总线上。总线上。出线控制部件的功能：出线控制部件的功能： 检测总线上的信号，并把属于本人的信息读入一个检测总线上的信号，并把属于本人的信息读入一个缓冲存储器中，进展格式变换，放在缓冲存储器中，由缓冲存储器中，进展格式变换，放在缓冲存储器中，由出线送出，构成出线信号。出线送出，构成出线信号。共享总线型交换单元共享总线型交换单元北京邮电大学计算机科学与技术学院 卞佳丽总线：总线： 普通包括多条数据线和控制线。数据线用于在入线普通包括多条数据线和控制线。数据线用于在入线控制部件和出线控制部件传送信号；控制线用于控制各控制部件和出线控制部件传送信号；控制线用于控制各入线控制部件获得时隙和发送信息，以及出线控制部件入线控制部件获得时隙和发送信息，以及出线控制部件读取属于本人的信息。读取属于本人的信息。 总线按时隙轮番分配给各个入线控制部件和出线控总线按时隙轮番分配给各个入线控制部件和出线控制部件运用，其时隙的分配有一定的规那么。制部件运用，其时隙的分配有一定的规那么。共享总线型交换单元共享总线型交换单元北京邮电大学计算机科学与技术学院 卞佳丽数字交换单元数字交换单元DSE北京邮电大学计算机科学与技术学院 卞佳丽数字交换单元数字交换单元DSE的任务原理的任务原理STS18STS12端口RAM话路RAM数据RAM00031D3131P C121218818S北京邮电大学计算机科学与技术学院 卞佳丽3、交换网络、交换网络交换网络是由假设干个交换单元按照一定的交换网络是由假设干个交换单元按照一定的拓扑构造和控制方式构成的网络。拓扑构造和控制方式构成的网络。交换网络的三个根本要素是：交换单元、不交换网络的三个根本要素是：交换单元、不同交换单元间的拓扑衔接和控制方式。同交换单元间的拓扑衔接和控制方式。北京邮电大学计算机科学与技术学院 卞佳丽交换网络的普通构造交换网络的普通构造控制单元出线入线交换单元交换单元交换单元交换单元交换网络北京邮电大学计算机科学与技术学院 卞佳丽单级交换网络和多级交换网络单级交换网络和多级交换网络交换网络按拓扑衔接方式可分为：单级交换网络交换网络按拓扑衔接方式可分为：单级交换网络 多级交换网络多级交换网络出线出线0 N-1入线入线0M-1单级交换网络单级交换网络交换交换单元单元北京邮电大学计算机科学与技术学院 卞佳丽单级交换网络和多级交换网络单级交换网络和多级交换网络 假假设一个交一个交换网网络中的交中的交换单元可以分元可以分为N级，顺序命序命名名为第第1,2,N级，并且，并且满足：足： 一切入一切入线都只与第都只与第1级交交换单元元衔接；接； 一切第一切第1级交交换单元都只与入元都只与入线和第和第2级交交换单元元衔接；接； 一切第一切第2级交交换单元都只与第元都只与第1级和第和第3级交交换单元元衔接；接； 依此依此类推，一切第推，一切第N级交交换单元都只与第元都只与第N-1级和出和出线衔接；接； 那么称那么称这样的交的交换网网络为多多级交交换网网络，或，或N级交交换网网络。北京邮电大学计算机科学与技术学院 卞佳丽多级交换网络的拓扑构造可用三个参数来阐明：多级交换网络的拓扑构造可用三个参数来阐明： 每个交换单元的容量每个交换单元的容量 交换单元的级数交换单元的级数 交换单元间的衔接通路链路交换单元间的衔接通路链路单级交换网络和多级交换网络单级交换网络和多级交换网络北京邮电大学计算机科学与技术学院 卞佳丽多级交换网络多级交换网络(nm x nm两级交换网络两级交换网络)O1n-1O1n-1O1n-1O1m-1O1m-1O1m-1OO11m-1n-1 1级级2级级北京邮电大学计算机科学与技术学院 卞佳丽多级交换网络的内部阻塞多级交换网络的内部阻塞 假设出、入线空闲，但因交换网络级间链路被占用而无法接通的景象，称为多级交换网络的内部阻塞。严厉无阻塞网络： 不论网络处于何种形状，任何时辰都可以在交换网络中建立一个衔接，只需这个衔接的起点、终点是空闲的，而不会影响网络中已建立起来的衔接。北京邮电大学计算机科学与技术学院 卞佳丽可重排无阻塞网络：可重排无阻塞网络： 不论网络处于何种形状，任何时辰都可以在交换网络不论网络处于何种形状，任何时辰都可以在交换网络中直接或对已有的衔接重选路由来建立一个衔接，只需这中直接或对已有的衔接重选路由来建立一个衔接，只需这个衔接的起点、终点是空闲的，而不会影响网络中已建立个衔接的起点、终点是空闲的，而不会影响网络中已建立起来的衔接。起来的衔接。广义无阻塞网络：广义无阻塞网络： 指一个给定的网络存在着固有的阻塞能够，但又能够指一个给定的网络存在着固有的阻塞能够，但又能够存在着一种精巧的选路方法，使得一切的阻塞均可防止，存在着一种精巧的选路方法，使得一切的阻塞均可防止，而不用重新安排网络中已建立起来的衔接。而不用重新安排网络中已建立起来的衔接。多级交换网络的内部阻塞多级交换网络的内部阻塞北京邮电大学计算机科学与技术学院 卞佳丽1 13 34 42 21 13 34 42 2C1C1C2C21，2，3，44，2，1，3 可重排无阻塞网络可重排无阻塞网络北京邮电大学计算机科学与技术学院 卞佳丽1 13 34 42 21 13 34 42 2C1C1cc2cc2可重排无阻塞网络可重排无阻塞网络北京邮电大学计算机科学与技术学院 卞佳丽3.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网络网络北京邮电大学计算机科学与技术学院 卞佳丽在最坏情况下，中在最坏情况下，中间级会有会有n-1X 2个交个交换单元被元被占用，因此中占用，因此中间级至少要有至少要有n-1X 2+1=2n-1个交个交换单元，即元，即m2n-1时，可确保无阻塞，可确保无阻塞严厉无阻塞。无阻塞。CLOS网络网络北京邮电大学计算机科学与技术学院 卞佳丽3.2 TST网络网络TST网络是在电路交换系统中经常运用的一种交换网网络是在电路交换系统中经常运用的一种交换网络，它是三级交换网络，两侧为络，它是三级交换网络，两侧为T接线器，中间一级为接线器，中间一级为S接线器，接线器，S级的出入线数决议于两侧级的出入线数决议于两侧T接线器的数量。接线器的数量。第第1级级T接线器：担任输入母线的时隙交换。接线器：担任输入母线的时隙交换。S接线器：担任母线之间的空间交换交换。接线器：担任母线之间的空间交换交换。第第2级级T接线器：担任输出母线的时隙交换。接线器：担任输出母线的时隙交换。北京邮电大学计算机科学与技术学院 卞佳丽1 2 31 2 31 2 3TS2TS310723313TS2TS31S(输入控制输入控制)TS7TS231031272031312323 2231731CMACMASMASMASMBSMBCMBCMBTS23TS7T(输出控制输出控制)T(输入控制输入控制)ABAB北京邮电大学计算机科学与技术学院 卞佳丽为减少选路次数，简化控制，可使两个方向的内部时为减少选路次数，简化控制，可使两个方向的内部时隙具有一定的对应关系，通常可相差半帧，俗称反相法，隙具有一定的对应关系，通常可相差半帧，俗称反相法，即：即：设：设：Nf=一帧的时隙数一帧的时隙数 Na=A到到B方向的内部时隙数方向的内部时隙数 Nb=B到到A方向的内部时隙数方向的内部时隙数那么：那么： Nb= Na +Nf/2TST网络完全无阻塞的条件：网络完全无阻塞的条件： m内部时隙数内部时隙数=2n输入时隙数输入时隙数3.2 TST网络网络北京邮电大学计算机科学与技术学院 卞佳丽关于关于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)-S北京邮电大学计算机科学与技术学院 卞佳丽3.3 BANYAN 网络网络qBanyan 网络的根本构造网络的根本构造qBanyan 网络的根本特性网络的根本特性qBATCHER-BANYAN网络网络q基于基于banyan的多通路构造的多通路构造qBenes网络网络北京邮电大学计算机科学与技术学院 卞佳丽banyan网络可分为一些子类，L级banyan是其中的一类，其特征是只需相邻级之间才有链路相连，即任何输入到任何输出之间的通路都经过L级。L级banyan网络又可分为规那么banyan和不规那么banyan。规那么banyan是指构成banyan网络的各个交换单元都是等同的，而不规那么banyan那么不然。假设规那么banyan中的各个交换单元不仅是等同的，而且每个交换单元的入线数等于出线数，那么称此规那么banyan为矩形banyan。1、Banyan 网络的根本构造网络的根本构造北京邮电大学计算机科学与技术学院 卞佳丽 通常将由2 X 2的交换单元构成的单通路网络称为banyan网络。 banyan网络是基于树型的拓扑构造，但每一个交换单元却是基于crossbar的构造。 2 X 2的交换单元也具有bar和cross两种形状。1、Banyan 网络的根本构造网络的根本构造北京邮电大学计算机科学与技术学院 卞佳丽01234567012345678 x 8的的3级级banyan网络网络北京邮电大学计算机科学与技术学院 卞佳丽树型构造特性：树型构造特性： 从从banyan的任一输入端口引出的一组通路构成了的任一输入端口引出的一组通路构成了2分支树，级数越多，分支越多，级数分支树，级数越多，分支越多，级数k=2N，N=总入总入线数线数/出线数，即出线数，即2k=N。单通路特性：单通路特性： banyan的任一入端到任一出端之间，具有的任一入端到任一出端之间，具有1条且仅条且仅有一条通路。有一条通路。自选路由特性：自选路由特性： 自选路由，即是给定出线地址，不用外加控制命令，自选路由，即是给定出线地址，不用外加控制命令，就可选到出线。可以运用对应于出端号的二进制码的选就可选到出线。可以运用对应于出端号的二进制码的选路标签来自动选路。路标签来自动选路。2、Banyan 网络的根本特性网络的根本特性北京邮电大学计算机科学与技术学院 卞佳丽01234567012(010)3(011)4(100)5(101)678 x 8的3级banyan网络10110(011)(010)(100)(101)Banyan网络的自选路由特性网络的自选路由特性北京邮电大学计算机科学与技术学院 卞佳丽可扩展性：可扩展性： 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 网络的根本特性网络的根本特性北京邮电大学计算机科学与技术学院 卞佳丽16X16BANYAN交换网络的构成Banyan网络的可扩展性网络的可扩展性北京邮电大学计算机科学与技术学院 卞佳丽16X16BANYAN交换网络的构成Banyan网络的可扩展性网络的可扩展性北京邮电大学计算机科学与技术学院 卞佳丽1内部阻塞是在2X2交换单元的两条入线要向同一个出线上发送信元时产生的，最坏情况下概率为50%，假设减少入线上的信息量，就可减少阻塞的概率，故可经过适当限制入线上的信息量或加大缓冲存储器来减少内部阻塞。2可以经过添加多级交换网络的级数来消除内部阻塞。已有证明，假设要完全消除N X N的banyan网络的内部阻塞，至少需求22N-1级。3可以添加banyan网的平面树，构成多通道交换网络。4运用排序-banyan网络。处理内部阻塞的方法处理内部阻塞的方法北京邮电大学计算机科学与技术学院 卞佳丽 该网络也简称为该网络也简称为B-B网，是由网，是由BATCHER排序网排序网和和BANYAN网组成，它胜利地防止了网组成，它胜利地防止了BANYAN网络网络的内部阻塞，这是目前的内部阻塞，这是目前ATM交换机运用较多的一种交换机运用较多的一种网络。网络。 BATCHER排序网是由排序网是由2X2的比较器的比较器BATCHER比较器构成的。比较器构成的。xymin(x,y)max(x,y)xymin(x,y)max(x,y)3、BATCHER-BANYAN网络网络北京邮电大学计算机科学与技术学院 卞佳丽BATCHER-BANYAN网络011111010100011010100111111100010011BATCHER-BANYAN网络网络北京邮电大学计算机科学与技术学院 卞佳丽 为了减少或消除banyan的内部阻塞，提高吞吐率，除了构成B-B网络之外，还可以构成基于banyan的的各种多通路网络。1增长型banyan 增长型banyan就是前面加上分配级，以扩展每个入端的选择范围，从而构成多通路网络。每添加1级，每个入端与每个出端之间的通路数就添加1倍。前置分配级还可以使业务流平衡地进入banyan的入端，减少banyan对流入的业务流模型的敏感性。4、基于、基于BANYAN的多通路构造的多通路构造北京邮电大学计算机科学与技术学院 卞佳丽0123456701234567增长型banyan增长型增长型BANYAN北京邮电大学计算机科学与技术学院 卞佳丽2扩展型banyan 调查banyan中的交换单元，对应于每个交换单元输出地址有1条链路，假设使每个输出地址有d条链路，也就是可以恣意选择d条中的1条，就称为扩展型banyan。 在扩展型banyan网中，22的交换单元变成了2d2d的交换单元。但输出地址并非2d个，而依然是2个，只需用1个比特来区别。于是在任何时辰，最多可有d个信息单元传送到交换单元的每个输出；假设对应于同一输出地址同时有多于d个的信元到达，只能传送其中的d个。4、基于、基于BANYAN的多通路构造的多通路构造北京邮电大学计算机科学与技术学院 卞佳丽0123456701234567扩展型banyan扩展型扩展型BANYAN北京邮电大学计算机科学与技术学院 卞佳丽3膨胀型banyan 膨胀型banyan是膨胀度d在各级可以变化的扩展型banyan。4复份型banyan 复份型banyan是将假设干个一样的banyan并接在一同，构成多平面的网络构造。 从复份型banyan的每个输入端进入的信息单元，可以随机地选择某个平面，也可以按负荷均分原那么分配到各个平面，还可以广播到一切的平面。 4、基于、基于BANYAN的多通路构造的多通路构造北京邮电大学计算机科学与技术学院 卞佳丽0123456701234567膨胀型banyand=2d=3d=4膨胀型膨胀型BANYAN北京邮电大学计算机科学与技术学院 卞佳丽Banyan 1Banyan 2Banyan r12n12n复份型banyan复份型复份型BANYAN北京邮电大学计算机科学与技术学院 卞佳丽 benes网络是著名的多通路网络，具有再配置无阻塞的特点。 可以看出，Benes网络实践上相当于两个banyanbanyan与反转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网络网络北京邮电大学计算机科学与技术学院 卞佳丽01234567012345678 X 8 benes网络8 X8 BENES 网络网络北京邮电大学计算机科学与技术学院 卞佳丽0123456701234567benes网络构成方法N/2 X N/2N/2 X N/2BENES 网络构成方法网络构成方法北京邮电大学计算机科学与技术学院 卞佳丽作业作业11、有一个T-S-T交换网络，有8条输入母线和8条输出目线，每条母线为一帧256个TS，其第一级T接线器为输入控制方式，S接线器为输出控制方式，第二级T接线器为输出控制方式，请画图表示该网络将HW6TS8交换到HW2TS23的过程内部选定的空闲时隙为TS15 ，并标出各级SM和CM的容量及相关单元内容，给出CP的时间。北京邮电大学计算机科学与技术学院 卞佳丽作业作业22、构造16*16的交换单元：采用根本开关阵列时，需求 多少个开关？采用K=4的绳路开关阵列时，需求多少个开关？采用可重排无阻塞网络时，需多少个2*2交叉单元？采用BANYAN网络时，需多少个2*2交叉单元？采用共享存贮器构造时，至少需 多少个存储单元。3、构造256*256的三级严厉无阻塞CLOS网络。要求：入口级选择8入线的交换单元，出口级选择8出线的交换单元。画出该网络衔接表示图标出各级交换单元的个数，入出线。 北京邮电大学计算机科学与技术学院 卞佳丽本章小结本章小结 描画交换单元衔接特性的方法 交换单元的外部特性描画的描画目的 三种典型的交换单元的构造、特性及任务原理 无阻塞网络的概念，构成无阻塞网络的方法 TST、CLOS、BANYAN网络的构造及特性