交换网络_图文_百度文库

  二、交换网络 北京邮电大学计算机科学与技术学院 卞佳丽 1 主要内容 1. 交换网络的构成和分类 2. 交换单元 ? ? ? ? 交换单元的基本概念 开关阵列与空间交换单元 共享存储器型的交换单元——时间交换单元 共享总线型的交换单元——数字交换单元 3. 交换网络 ? ? ? ? CLOS网络 TST网络 DSN网络 BANYAN网络 2 北京邮电大学计算机科学与技术学院 卞佳丽 1、交换网络的构成和分类 交换的基本功能是在任意的入线和出线之间 建立连接。 在交换系统中完成这一基本功能的部件就是 交换网络,它是交换系统的核心。交换网络是由 若干个交换单元按照一定的拓扑结构和控制方式 构成的。 交换单元是构成交换网络的最基本的部件。 交换网络有:空分、时分 数字、模拟 北京邮电大学计算机科学与技术学院 卞佳丽 3 2、交换单元 ? ? ? ? 交换单元的基本概念 开关阵列与空间交换单元 共享存储器型的交换单元——时间交换单元 共享总线型的交换单元——数字交换单元 北京邮电大学计算机科学与技术学院 卞佳丽 4 2.1 交换单元的基本概念 0 1 …… … … 入线 控制端 状态端 M X N的交换单元 北京邮电大学计算机科学与技术学院 卞佳丽 5 两种信号的交换 入线 出线 同步时分复用信号的交换 北京邮电大学计算机科学与技术学院 卞佳丽 6 两种信号的交换 0 入线 出线 异步时分复用信号的交换 北京邮电大学计算机科学与技术学院 卞佳丽 7 交换单元按使用需要的不同可分为: 0 入线 出线 入线 集中型(MN) 入线 扩散型(MN ) 0 出线 连接型(M=N) 北京邮电大学计算机科学与技术学院 卞佳丽 8 交换单元按信息流向分为: ? 有向交换单元:当信息经过交换单元时只能从入线 进出线出,具有唯一确定的方向。 ? 无向交换单元:交换单元的每条线即可入也可出, 其入线 入线 出线 M X N有向交换单元 入 线 / 出 线 ….. 北京邮电大学计算机科学与技术学院 卞佳丽 ….. 交换单元的连接特性 连接特性是交换单元的基本特性,它反映了交换单元 入线到出线的连接能力,通常我们用连接集合和连接函数 来描述交换单元的连接特性 ? 连接集合: 入线} 出线} 定义:t∈T,即t是T的一个元 r∈Rt,Rt是R的一个子集,r是Rt的一个元 则集合 c={t,Rt} 为一个连接。 10 北京邮电大学计算机科学与技术学院 卞佳丽 交换单元的连接特性 ? ? ? 若r∈Rt,Rt中只含有一个元,则称该连接为点到点 连接。 若r∈Rt,Rt中含有多个元,则称该连接为一点到多 点连接。 若一个交换单元可以提供点到多点的功能,但Rt≠R, 则称其具有同发功能;若Rt=R,则该交换单元具有广 播功能。 北京邮电大学计算机科学与技术学院 卞佳丽 11 交换单元的连接特性 一个交换单元的连接同时可有多个,这就构成了交 换单元的连接集合: C={c0, c1, c2, …} 其中:起点集 终点集 Tc={t; t∈ci, ci?C} Rc={r; r∈Rt, Rt ? ci , ci ? C} ? ? 连接和连接集合是对应于某一时刻的 连接集合的数目越多,连接能力就越强 北京邮电大学计算机科学与技术学院 卞佳丽 12 交换单元的连接特性 ? 连接函数 一个连接函数对应一种连接,连接函数表示相互 连接的入线编号和出线编号之间的一一对应关系,即存 在连接函数f,入线。 连接函数实际上也反映了入线编号构成的数组和出 线编号构成的数组之间的置换关系或排列关系,故连接 函数也被称作置换函数或排列函数。 北京邮电大学计算机科学与技术学院 卞佳丽 13 连接函数的表示形式 ? 函数表示形式 x表示入线编号(二进制表示),f(x)表 示连接函数。 ? 排列表示形式 即输入输出对应表示形式 t0,t1,…,t n-1 r0,r1,…,r n-1 ? 图形表示形式 北京邮电大学计算机科学与技术学院 卞佳丽 14 交换单元常用的连接函数 直线连接: 函数表示:I(xn-1xn-2…x1x0)= xn-1xn-2 … x1x0 排列表示(N=4): 0,1,2,3 0,1,2,3 图形表示(N=4): 0 0 1 2 3 1 2 3 15 北京邮电大学计算机科学与技术学院 卞佳丽 交换单元的连接特性 交叉连接: 函数表示:E(xn-1xn-2…x1x0)= xn-1xn-2 … x1x0 排列表示(N=4): 0,1,2,3 1,0,3,2 图形表示(N=4): 0 0 1 2 3 1 2 3 16 北京邮电大学计算机科学与技术学院 卞佳丽 交换单元的连接特性 间隔交叉连接: Ck(xn-1xn-2…xk … x1x0)= xn-1xn-2 …xk … x1x0 0 1 2 3 N=4 k=1 0 1 2 3 0 1 2 3 N=4 k=0 0 1 2 3 北京邮电大学计算机科学与技术学院 卞佳丽 17 交换单元的连接特性 均匀洗牌连接: σ(xn-1xn-2…xk … x1x0)= xn-2 …xk … x1x0 xn-1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 18 N=8 北京邮电大学计算机科学与技术学院 卞佳丽 交换单元的连接特性 蝶式连接: β(xn-1 xn-2…xk … x1 x0)= x0 xn-2 …xk … x1 xn-1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 19 N=8 北京邮电大学计算机科学与技术学院 卞佳丽 交换单元的性能 ? 容量: 交换单元所有入线可以同时送入的总的信息量 ? 接口: 交换单元需要规定自己的信号接口标准,即信号形式、 速率及信息流方向 ? 功能: 点到点、同发、广播 ? 质量: 完成交换动作的速度、任何情况下是否能完成指定连 接、信息经过交换单元是否有损伤(时间、语义) 北京邮电大学计算机科学与技术学院 卞佳丽 20 2.2 开关阵列与空间交换单元——开关阵列 在交换单元内部,要建立任意入线和任意出 线之间的连接,就在每条入线和每条出线之间都 各自接上一个开关,所有开关就构成了交换单元 内部的开关阵列。 北京邮电大学计算机科学与技术学院 卞佳丽 21 开关阵列的工作原理 出线 入线 ….. ….. M X N有向交换单元 M X N有向矩形开关阵列 北京邮电大学计算机科学与技术学院 卞佳丽 22 开关阵列的工作原理 出线 入线 N无向方形开关阵列 北京邮电大学计算机科学与技术学院 卞佳丽 23 无向交换单元开关阵列的实现(补充) 0 入线/出线 N无向交换单元 若在一个N X N的交换单元中的连接总是对称的,即 如果入端i连接到出端j,则入端j一定连接到出端i,那么 相同编号的入端和出端可以看作一个同时具有发送和接 收信息能力的信息端,既具有N个双向通信的信息端, 并且每个信息端都可以和任何其它的信息端相连,这样 的交换单元称作N个信息端的无向交换单元,简称N无向 交换单元。 北京邮电大学计算机科学与技术学院 卞佳丽 24 无向交换单元开关阵列的实现(补充) 0 入线 N无向交换单元 N无向交换单元的开关阵列 (用双向开关) 北京邮电大学计算机科学与技术学院 卞佳丽 25 无向交换单元开关阵列的实现(补充) 0 1 0 入线 N无向交换单元的开关阵列 (用单向开关) 北京邮电大学计算机科学与技术学院 卞佳丽 26 无向交换单元开关阵列的实现(补充) 0 K-1 入线 入线/出线 (信息端) K x L无向交换单元 若N无向交换单元的N个信息端可以分为两组, 分别为K和L个信息端。属于其中一组的信息端都可 以和另一组的任何信息端相连接,但是不能和本组 中的其它信息端相连,则称其为一个K x L的无向交 换单元。 北京邮电大学计算机科学与技术学院 卞佳丽 27 无向交换单元开关阵列的实现(补充) 0 1 K-1 0 1 L-1 0 1 K-1 K(K=L)无向方形开关阵列 0 1 K-1 K X L无向矩形开关阵列 入线 入线/出线 (信息端) K x L无向交换单元 北京邮电大学计算机科学与技术学院 卞佳丽 28 无向交换单元开关阵列的实现(补充) 0 0 1 K-1 K X L无向矩形开关阵列 (用双向开关) 1 L-1 0 1 K-1 K+0 K+1 K+L-1 0 1 K-1K+0 K+1 K+L-1 (K+L) X (K+L)有向开关阵列 (用单向开关) 北京邮电大学计算机科学与技术学院 卞佳丽 29 无向交换单元开关阵列的实现(补充) 0 0 1 K-1 K 无向方形开关阵列 (用双向开关) 1 K-1 0 1 K-1 K+0 K+1 K+K-1 0 1 K-1K+0 K+1 K+K-1 2K X 2K有向开关阵列 (用单向开关) 北京邮电大学计算机科学与技术学院 卞佳丽 30 全连接交换单元和部分连接交换单元 0 出线 入线 北京邮电大学计算机科学与技术学院 卞佳丽 31 多路选择器 出线 入线 出线 出线 入线 出线 北京邮电大学计算机科学与技术学院 卞佳丽 32 开关阵列的特性 ? 开关控制简单,从入线到出线具有均匀的单位延迟时 间。 ? 开关阵列适合于构成较小的交换单元(开关数反映了 实现的复杂度和成本的高低)。 ? 交换单元的性能依赖于所使用的开关。 ? 控制信号简单 ? 容易实现同发和广播功能 北京邮电大学计算机科学与技术学院 卞佳丽 33 实际的开关阵列 继电器:其构成的交换单元是无向的,可交换模拟和数字信息, 干扰和噪声大、动作慢(ms级)、体积大(cm级)。 模拟电子开关:一般利用半导体材料制成。 如:MC142100、MC145100(4 x 4开关阵列) 只能单向传送,且衰耗和时延较大。 数字电子开关:由简单的由逻辑门构成,用于数字信号的交 换,开关动作极快且无信号损失。 北京邮电大学计算机科学与技术学院 卞佳丽 34 开关阵列交叉点的实现(1) ? 通断开关 交叉点可看成是一个具有通/断功能的开关。其具体 实现比较复杂,包括FIFO缓冲器和相应的控制逻辑。 ? 多路选择器 北京邮电大学计算机科学与技术学院 卞佳丽 35 开关阵列交叉点的实现(2) ? Crossbar 交叉点是一个2 x 2的传送门,它有两个状态:bar状 态和cross状态。Bar状态是指横向输入连到纵向输出,纵 向输入连到横向输出;cross状态是指横向输入连到横向输 出,纵向输入连到纵向输出。 交换矩阵在初始状态时,所有交叉点均处于cross状态, 即任何入线与任何出线间均不连通。如果要使入线i与出线j 连通,则应使处于交叉点(i,j)上的传送门处于bar状态, 而在i行和j列的所有其它的传送门仍处于cross状态。 北京邮电大学计算机科学与技术学院 卞佳丽 36 开关阵列交叉点的实现(3) 纵向输入 横向输入 横向输出 bar状态 纵向输出 cross状态 北京邮电大学计算机科学与技术学院 卞佳丽 37 开关阵列交叉点的实现(4) 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 crossbar 通/断开关 38 北京邮电大学计算机科学与技术学院 卞佳丽 2.3 开关阵列与空间交换单元——空间交换单元 空间交换单元也称为空间接线器(Space Switch),简称为S单元或S接线器,用来实现 多个输入复用线与多个输出复用线之间的空间 交换,而不改变其时隙位置。 北京邮电大学计算机科学与技术学院 卞佳丽 39 空间交换单元的基本结构 S接线器的构成:交叉点矩阵、控制存储器 交叉点矩阵:开关阵列 控制存储器(CM-Control Memory): ? ? S接线器所含CM数量等于入(出)线数 每个CM的所含有的存储单元个数等于入(出) 线上的复用时隙数 ? 每个存储单元为n位bit,且满足N≤2n,其中N 为入(出)线上数 北京邮电大学计算机科学与技术学院 卞佳丽 40 空间交换单元的控制方式 TS12 TS8 0 1 2 TS12 TS8 0 0 8 2 12 2 1 输入控制方式 0 41 TS12 TS8 0 1 1 2 TS12 TS8 2 127 北京邮电大学计算机科学与技术学院 卞佳丽 空间交换单元的控制方式 TS12 TS8 0 TS12 TS8 0 1 TS12 TS8 0 0 8 12 127 北京邮电大学计算机科学与技术学院 卞佳丽 42 1 2 1 2 2 2 0 输出控制方式 1 TS12 TS8 2 空间交换单元的工作原理 北京邮电大学计算机科学与技术学院 卞佳丽 43 2.3、共享存储器型的交换单元——时间交换单元 0 1 输入信号 N-1 输出信号 工作方式:入线缓冲、出线缓冲 共享存储器型交换单元的一般结构 北京邮电大学计算机科学与技术学院 卞佳丽 44 时间交换单元 时间交换单元也称为时间接线器(Time Switch),简称为T单元或T接线器,用来实现 时隙交换功能。所谓时隙交换是指入线上各个 时隙的内容要按照交换连接的需要,分别在出 线上的不同时隙位置输出。 北京邮电大学计算机科学与技术学院 卞佳丽 45 时间交换单元的基本结构 T接线器主要由话音存储器(SM:Speech Memory)和控制存储器(CM:Control memory)构 成。 SM用来暂存话音的数字编码信息,故每个单 元至少应为8比特。SM的容量等于输入复用线上 每帧的时隙数。 CM的容量等于SM的容量;设CM每个单元的比 特数为n,SM的单元数为N,则有2n=N,N也就是复 用线上的时隙数。 北京邮电大学计算机科学与技术学院 卞佳丽 46 时间交换单元的控制方式 北京邮电大学计算机科学与技术学院 卞佳丽 47 2.4、共享总线型交换单元——数字交换单元 北京邮电大学计算机科学与技术学院 卞佳丽 48 共享总线型交换单元 入线控制部件的功能: 接收入线信号,进行相应的格式变换,放在缓冲存 储器中,并在分配给该部件的时隙上把收到的信息送到 总线上。 出线控制部件的功能: 检测总线上的信号,并把属于自己的信息读入一个 缓冲存储器中,进行格式变换,放在缓冲存储器中,由 出线送出,形成出线信号。 北京邮电大学计算机科学与技术学院 卞佳丽 49 共享总线型交换单元 总线: 一般包括多条数据线和控制线。数据线用于在入线 控制部件和出线控制部件传送信号;控制线用于控制各 入线控制部件获得时隙和发送信息,以及出线控制部件 读取属于自己的信息。 总线按时隙轮流分配给各个入线控制部件和出线控 制部件使用,其时隙的分配有一定的规则。 北京邮电大学计算机科学与技术学院 卞佳丽 50 数字交换单元(DSE) 北京邮电大学计算机科学与技术学院 卞佳丽 51 数字交换单元(DSE)的工作原理 D P C 端口 RAM 0 0 线 S TS18 S 31 31 31 北京邮电大学计算机科学与技术学院 卞佳丽 52 3、交换网络 交换网络是由若干个交换单元按照一定的拓 扑结构和控制方式构成的网络。 交换网络的三个基本要素是:交换单元、不 同交换单元间的拓扑连接和控制方式。 北京邮电大学计算机科学与技术学院 卞佳丽 53 交换网络的一般结构 交换 单元 … 入线 … 交换 单元 … … 出线 交换 单元 交换 单元 交换网络 控制单元 北京邮电大学计算机科学与技术学院 卞佳丽 54 单级交换网络和多级交换网络 交换网络按拓扑连接方式可分为:单级交换网络 多级交换网络 入线 出线 单级交换网络 北京邮电大学计算机科学与技术学院 卞佳丽 55 单级交换网络和多级交换网络 如果一个交换网络中的交换单元可以分为N级,顺序 命名为第1,2,…,N级,并且满足: 所有入线级交换单元连接; 所有第1级交换单元都只与入线级交换单元连接; 所有第2级交换单元都只与第1级和第3级交换单元连接; 依此类推,所有第N级交换单元都只与第N-1级和出线 连接; 则称这样的交换网络为多级交换网络,或N级交换网络。 北京邮电大学计算机科学与技术学院 卞佳丽 56 单级交换网络和多级交换网络 多级交换网络的拓扑结构可用三个参数来说明: 每个交换单元的容量 交换单元的级数 交换单元间的连接通路(链路) 北京邮电大学计算机科学与技术学院 卞佳丽 57 多级交换网络(nm x nm两级交换网络) 1级 2级 O O 1 m-1 … … … O 1 n-1 O 1 n-1 O 1 n-1 O … … … 1 … m-1 1 O 1 m-1 O 1 m-1 58 北京邮电大学计算机科学与技术学院 卞佳丽 … … … … … … n-1 … 多级交换网络的内部阻塞 若出、入线空闲,但因交换网络级间链路被占用而 无法接通的现象,称为多级交换网络的内部阻塞。 严格无阻塞网络: 不管网络处于何种状态,任何时刻都可以在交换网 络中建立一个连接,只要这个连接的起点、终点是空闲 的,而不会影响网络中已建立起来的连接。 北京邮电大学计算机科学与技术学院 卞佳丽 59 多级交换网络的内部阻塞 可重排无阻塞网络: 不管网络处于何种状态,任何时刻都可以在交换网 络中直接或对已有的连接重选路由来建立一个连接,只要 这个连接的起点、终点是空闲的,而不会影响网络中已建 立起来的连接。 广义无阻塞网络: 指一个给定的网络存在着固有的阻塞可能,但又可 能存在着一种精巧的选路方法,使得所有的阻塞均可避免, 而不必重新安排网络中已建立起来的连接。 北京邮电大学计算机科学与技术学院 卞佳丽 60 可重排无阻塞网络 1 2 3 4 C2 C1 1 2 3 4 C2 C1 1,2,3,4 4,2,1,3 北京邮电大学计算机科学与技术学院 卞佳丽 61 可重排无阻塞网络 1 2 3 4 C1 cc2 1 2 3 4 cc2 C1 北京邮电大学计算机科学与技术学院 卞佳丽 62 3.1 CLOS网络 为了减少交叉点总数而同时具有严格的无阻塞特性, CLOS C.很早就提出一种多级结构,推出了严格无阻塞的 条件,这就是著名的CLOS网络。 1 n 1 … … 1 1 m 1 r 1 … 1 r 1 r 1 m 1 m 1 … … 1 n … 1 n 1 m 1 r 1 … n r 1 m r 3级CLOS网络 北京邮电大学计算机科学与技术学院 卞佳丽 63 CLOS网络 在最坏情况下,中间级会有(n-1)X 2个交换单元被 占用,因此中间级至少要有(n-1)X 2+1=2n-1个交换 单元,即m≥2n-1时,可确保无阻塞(严格无阻塞)。 北京邮电大学计算机科学与技术学院 卞佳丽 64 3.2 TST网络 TST网络是在电路交换系统中经常使用的一种交换网 络,它是三级交换网络,两侧为T接线器,中间一级为S 接线器,S级的出入线数决定于两侧T接线级T接线器:负责输入母线的时隙交换。 S接线器:负责母线之间的空间交换交换。 第2级T接线器:负责输出母线的时隙交换。 北京邮电大学计算机科学与技术学院 卞佳丽 65 T(输出控制) S(输入控制) CMA 7 2 A TS2 0 2 1 2 B 3 31 SMA TS31 SMA 0 CMB T(输入控制) 23 2 2 TS2 A 1 TS7 TS23 SMB 2 TS23 1 0 7 3 2 3 TS7 CMB 7 31 SMB TS31 B 3 31 31 23 31 CMA 23 1 66 31 北京邮电大学计算机科学与技术学院 卞佳丽 3.2 TST网络 为减少选路次数,简化控制,可使两个方向的内部时 隙具有一定的对应关系,通常可相差半帧,俗称反相法, 即: 设:Nf=一帧的时隙数 Na=A到B方向的内部时隙数 Nb=B到A方向的内部时隙数 则: Nb= Na +Nf/2 TST网络完全无阻塞的条件: m(内部时隙数)=2n(输入时隙数) 北京邮电大学计算机科学与技术学院 卞佳丽 67 关于T-S组合网络 T-S(n)-T T-S-T网络:AXE10,FETEX-150,E10B,5ESS等 T-S-S-T网络:NEAX61 T-S-S-S-T网络:EWSD T-S-S-S-S-T网络:4ESS (长途) S-T(n)-S 北京邮电大学计算机科学与技术学院 卞佳丽 68 3.3 BANYAN 网络 ? ? Banyan 网络的基本结构 Banyan 网络的基本特性 ? ? BATCHER-BANYAN网络 基于banyan的多通路结构 ? Benes网络 北京邮电大学计算机科学与技术学院 卞佳丽 69 1、Banyan 网络的基本结构 banyan网络可分为一些子类,L级banyan是其中的一类, 其特征是只有相邻级之间才有链路相连,即任何输入到任何 输出之间的通路都经过L级。 L级banyan网络又可分为规则banyan和不规则banyan。 规则banyan是指构成banyan网络的各个交换单元都是等同的, 而不规则banyan则不然。 如果规则banyan中的各个交换单元不仅是等同的,而 且每个交换单元的入线数等于出线数,则称此规则banyan为 矩形banyan。 北京邮电大学计算机科学与技术学院 卞佳丽 70 1、Banyan 网络的基本结构 通常将由2 X 2的交换单元构成的单通路网 络称为banyan网络。 banyan网络是基于树型的拓扑结构,但每 一个交换单元却是基于crossbar的结构。 2 X 2 的交换单元也具有bar和cross两种状态。 北京邮电大学计算机科学与技术学院 卞佳丽 71 8 x 8的3级banyan网络 0 1 2 3 4 5 0 1 2 3 4 5 6 7 6 7 北京邮电大学计算机科学与技术学院 卞佳丽 72 2、Banyan 网络的基本特性 树型结构特性: 从banyan的任一输入端口引出的一组通路形成了2 分支树,级数越多,分支越多,级数k=㏒2N,N=总入 线k=N。 单通路特性: banyan的任一入端到任一出端之间,具有1条且仅 有一条通路。 自选路由特性: 自选路由,即是给定出线地址,不用外加控制命令, 就可选到出线。可以使用对应于出端号的二进制码的选 路标签来自动选路。 北京邮电大学计算机科学与技术学院 卞佳丽 73 Banyan网络的自选路由特性 0 1 2 3 4 5 (011) 0 1 2(010) 1 (010) 0 1 0 1 3(011) 4(100) 5(101) 6 7 (101) 6 7 (100) 8 x 8的3级banyan网络 北京邮电大学计算机科学与技术学院 卞佳丽 74 2、Banyan 网络的基本特性 可扩展性: banyan的构成具有一定的规律,可以采用有规则的扩展 方法将较小容量的banyan扩展成较大规模。 已有N X N的BANYAN网络,需构成2N X 2N的BANYAN网 络,则可用2组N X N,再加上一组N个2X2交换单元构成。第 一组的N X N的N条出线交换单元的某一入线相 连,第二组的N X N的N条出线交换单元的另一 入线相连。 内部竟争性: banyan是具有内部竞争的有阻塞网络。 北京邮电大学计算机科学与技术学院 卞佳丽 75 Banyan网络的可扩展性 16 16 X BANYAN 交 换 网 络 的 构 成 76 北京邮电大学计算机科学与技术学院 卞佳丽 Banyan网络的可扩展性 16 16 X BANYAN 交 换 网 络 的 构 成 北京邮电大学计算机科学与技术学院 卞佳丽 77 解决内部阻塞的方法 1)内部阻塞是在2X2交换单元的两条入线要向同一个出线 上发送信元时产生的,最坏情况下概率为50%,若减少 入线上的信息量,就可减少阻塞的概率,故可通过适当 限制入线上的信息量或加大缓冲存储器来减少内部阻塞。 2)可以通过增加多级交换网络的级数来消除内部阻塞。已 有证明,若要完全消除N X N的banyan网络的内部阻塞, 至少需要2㏒2N-1级。 3)可以增加banyan网的平面树,构成多通道交换网络。 4)使用排序-banyan网络。 北京邮电大学计算机科学与技术学院 卞佳丽 78 3、BATCHER-BANYAN网络 该网络也简称为B-B网,是由BATCHER排序网和 BANYAN网组成,它成功地避免了BANYAN网络的内 部阻塞,这是目前ATM交换机使用较多的一种网络。 BATCHER排序网是由2X2的比较器(BATCHER比较器) 构成的。 x y x y min(x,y) max(x,y) max(x,y) min(x,y) 79 北京邮电大学计算机科学与技术学院 卞佳丽 BATCHER-BANYAN网络 011 111 010 011 100 010 011 100 010 100 111 111 BATCHER-BANYAN网络 80 北京邮电大学计算机科学与技术学院 卞佳丽 4、基于BANYAN的多通路结构 为了减少或消除banyan的内部阻塞,提高吞吐率, 除了构成B-B网络之外,还可以构成基于banyan的的各种 多通路网络。 (1)增长型banyan 增长型banyan就是前面加上分配级,以扩大每个入端 的选择范围,从而形成多通路网络。每增加1级,每个入 端与每个出端之间的通路数就增加1倍。前置分配级还可 以使业务流均衡地进入banyan的入端,减少banyan对流入 的业务流模型的敏感性。 北京邮电大学计算机科学与技术学院 卞佳丽 81 增长型BANYAN 0 1 2 3 4 5 0 1 2 3 4 5 6 7 6 7 增长型banyan 北京邮电大学计算机科学与技术学院 卞佳丽 82 4、基于BANYAN的多通路结构 (2)扩展型banyan 考察banyan中的交换单元,对应于每个交换单元输出 地址有1条链路,如果使每个输出地址有d条链路,也就是 可以任意选择d条中的1条,就称为扩展型banyan。 在 扩 展 型 banyan 网 中 ,2×2 的 交 换 单 元 变 成 了 2d×2d的交换单元。但输出地址并非2d个,而仍然是2个, 只要用1个比特来区别。于是在任何时刻,最多可有d个信 息单元传送到交换单元的每个输出;如果对应于同一输出 地址同时有多于d个的信元到达,只能传送其中的d个。 北京邮电大学计算机科学与技术学院 卞佳丽 83 扩展型BANYAN 0 1 2 3 4 5 0 1 2 3 4 5 6 7 6 7 扩展型banyan 北京邮电大学计算机科学与技术学院 卞佳丽 84 4、基于BANYAN的多通路结构 (3)膨胀型banyan 膨胀型 banyan 是膨胀度 d 在各级可以变化的扩展型 banyan。 (4)复份型banyan 复份型 banyan 是将若干个相同的 banyan 并接在一起, 形成多平面的网络结构。 从复份型 banyan 的每个输入端进入的信息单元,可 以随机地选择某个平面,也可以按负荷均分原则分配到各 个平面,还可以广播到所有的平面。 北京邮电大学计算机科学与技术学院 卞佳丽 85 膨胀型BANYAN 0 1 2 3 4 5 d=2 d=3 d=4 0 1 2 3 4 5 6 7 6 7 膨胀型banyan 北京邮电大学计算机科学与技术学院 卞佳丽 86 复份型BANYAN 1 Banyan 1 1 … … 2 Banyan 2 2 … … … … … n Banyan r 复份型banyan 北京邮电大学计算机科学与技术学院 卞佳丽 … … … n 87 4、BENES网络 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交换单元为止。 北京邮电大学计算机科学与技术学院 卞佳丽 88 8 X8 BENES 网络 0 1 2 3 4 5 0 1 2 3 4 5 6 7 6 7 8 X 8 benes网络 北京邮电大学计算机科学与技术学院 卞佳丽 89 BENES 网络构成方法 0 1 2 3 4 5 0 1 2 N/2 X N/2 3 4 N/2 X N/2 5 6 7 6 7 benes网络构成方法 北京邮电大学计算机科学与技术学院 卞佳丽 90 作业(1) 1、有一个T-S-T交换网络,有8条输入母线条输出 目线个TS,其第一级T接线 器为输入控制方式,S接线器为输出控制方式,第 二级T接线器为输出控制方式,请画图表示该网络 将HW6TS8交换到HW2TS23的过程(内部选定的空闲 时隙为TS15 ),并标出各级SM和CM的容量及相关 单元内容,给出CP的时间。 北京邮电大学计算机科学与技术学院 卞佳丽 91 作业(2) 2、构造16*16的交换单元:采用基本开关阵列时,需要 多少个开关?采用K=4的绳路开关阵列时,需要多 少个开关?采用可重排无阻塞网络时,需多少个2*2 交叉单元?采用BANYAN网络时,需多少个2*2交叉 单元?采用共享存贮器结构时,至少需 多少个存储 单元。 3、构造256*256的三级严格无阻塞CLOS网络。要求: 入口级选择8入线的交换单元,出口级选择8出线的 交换单元。画出该网络连接示意图(标出各级交换 单元的个数,入出线)。 北京邮电大学计算机科学与技术学院 卞佳丽 92 本章小结 描述交换单元连接特性的方法 交换单元的外部特性描述的描述指标 三种典型的交换单元的结构、特性及工作原理 无阻塞网络的概念,构成无阻塞网络的方法 TST、CLOS、BANYAN网络的结构及特性 北京邮电大学计算机科学与技术学院 卞佳丽 93