第2章 交换单元与交换网络.ppt

1 第2章交换单元与交换网络 2 交换的基本功能是在任意的入线和出线之间建立连接 在交换系统中完成这一基本功能的部件就是交换网络 因此交换网络是任何交换系统的核心 交换网络是由各种交换单元构成的 对于不同的交换系统具体要求不同 可采用的最佳交换网络就不同 相应的可由不同交换单元构成 本章重点讨论交换单元的描述方法 各种主要的交换单元及交换网络 3 2 1概念 要了解交换单元和交换网络 首先应该知道需要交换的信息经过交换单元和交换网络传送时的信号形式 针对不同的信号形式 有相应的交换结构 按照信号的基本形式分为电信号和光信号 电信号又分为模拟信号和数字信号 目前使用的采用时分多路复用技术的数字信号主要有 用于电路交换的同步时分复用信号 用于分组交换和ATM交换的统计时分复用信号 4 1 同步时分复用信号同步时分复用是指将时间划分为基本时间单位 一帧占用一定时长 每帧分成若干个时隙 并按顺序编号 所有帧中编号相同的时隙成为一个子信道 是恒定速率的 一个子信道传递一路信息 根据时隙在时间轴上的位置 可确定其信道 对同步时分复用信号的交换实际是时隙所在位置的交换 即时隙的内容在时间轴上的移动 5 2 统计时分复用信号把需要传送的信息分成很多小段 称为分组 每个分组前附加标志码 标志要去哪个输出端 即路由标记 各个分组在输入时使用不同时隙 虽然使用不同时隙 但标志码相同的分组属于一次接续 所以 把它们所占的信道容量看作一个子信道 这个子信道可以是任何时隙 这样把一个信道划分成了若干子信道 称为标志化信道 6 这时 一个信道中的信息与它在时间轴上的位置 即时隙 没有必然联系 将这样的子信道合成为一个信道用的复用器为统计复用器 统计复用器中必须有一个存储器把接收到的信息按先后顺序分组发送 称为统计复用 所以 对统计时分复用信号的交换实际上就是按照每个分组信息前的路由标记 将其分发到出线 7 图1对两种时分复用信号的比较 8 2 2交换单元 交换单元是构成交换网络的最基本的部件 用若干个交换单元按照一定的拓扑结构和控制方式就可构成交换网络 因此交换单元的功能也就是交换的基本功能 即在任意的入线和出线之间建立连接 9 1 交换单元的数学模型1 交换单元 图2交换单元模型示意图 10 交换单元具有M条入线 N条出线 这是一个M N的交换单元 其中入线可用0 M 1或l M的编号来表示 出线可用0 N 1或1 N编号来表示 若入线数与出线数相等且均为N 则为N N的对称交换单元 交换单元通常还具有完成控制功能的控制端和描述内部状态的状态端 通常还将集中型和扩散型称为矩形交换单元 将分配型称为方形交换单元 11 交换单元按使用需要的不同可分为集中型 分配型和扩散型 1 集中型 入线数大于出线数 M N 可称集中器 2 分配型 入线数与出线数相等 M N 可称连接器 3 扩散型 入线数小于出线数 M N 可称扩展器 12 连接与连接函数首先我们可以把一个交换单元的一组入线和一组各看为一个集合 称为入线集合和出线集合 并记为入线集合 出线集合 定义 即t是T的一个元 即Rt是R的一个子集 r是Rt的一个元 则集合为一个连接 13 交换单元的一个连接就是入线集合T中的一个元t与出线集合R中的一个子集Rt组成的集合 若 Rt中只含有一个元 则称该连接为一点到一点 简称点到点 连接 若 Rt中含有多个元 则称连接为一点到多点连接 若一个交换单元可以提供点到多点连接 但 则称其具有同发功能 14 一个具有一组入线和一组出线的交换单元 上述定义的连接可以同时有多个 这就构成了交换单元的连接集合其中 起点集终点集值得注意的是 我们所说的连接和连接集合应该是对应于某一时刻的 15 每一个交换单元都可用一组连接函数来表示 一个连接函数对应一种连接 连接函数表示相互连接的入线编号和出线编号之间的一一对应关系 即存在连接函数f 在它的作用下 入线x与出线f x 相连接 0 x M 1 0 f x N 1 连接函数实际上也反映了入线编号构成的数组和出线编号构成的数组之间对应的置换关系或排列关系 所以 连接函数也被称为置换函数或排列函数 16 常见的连接函数表示形式有下列三种 1 函数表示形式用x表示入线编号变量 用f x 表示连接函数 通常x用若干位二进制形式来表示 写成 连接函数则表示为 2 排列表示形式排列表示形式也称输入输出对应表示形式 因为交换单元的连接实际上是各入线与各出线编号之间的一种对应关系 17 3 图形表示形式将以十进制数表示的入线编号与出线编号均按顺序排列 左边为入线编号 右边为出线编号 再用直线连接相应的入线与出线 即为连接函数的图形表示形式 18 2 几种连接函数 1 直线连接 恒等置换 对称交换单元相同编号的人线与出线一一对应连接即为直线连接 其函数表示为 19 图3直接连接的图形表示 20 2 交叉连接 交叉置换 交叉连接是实现二进制地址编号中第0位位值不同 0或1 的入线与出线之间的连接 其函数表示为 21 图4交叉连接的图形表示 22 3 间隔交叉连接 方体置换 间隔交叉连接是实现二进制地址编号中第k位位值不同的入线与出线间的连接 其函数表示为 23 图5间接交叉连接的图形表示 24 4 均匀洗牌连接 均匀洗牌置换 均匀泣牌连接是将入线二进制地址编号循环左移1位作为出线地址编号 其函数表示为此外 还可定义子洗牌连接 即将全部入线及相应出线分成若干个子部分 每一个子部分独立完成均匀洗牌连接 其连接函数为 25 逆均匀洗牌连接是均匀洗牌连接的逆函数 从图上可以看出 两者的入线和出线正好互换了位置 即逆洗牌是将入线二进制地址编号循环右移1位作为出线地址编号 函数表示为 26 图6均匀洗牌 子均匀洗牌 逆均匀洗牌连接的图形表示 27 5 蝶式连接 蝶式置换 蝶式连接的名称来源于FFT变换实现时 其图形形状如蝴蝶式样 这种连接是将入线进制地址编号的最高位与最低位互换位置作为出线地址编号 函数表示为同样 可定义子蝶式连接为 28 图7蝶式 子蝶式连接的图形表示 29 3 交换单元的性能指标 1 容量交换单元的容量 最基本的就是交换单元入线和出线的数目 但更一般的还应考虑交换单元每条入线上可以送入的信息量 如模拟信号的带宽和数字信号的速率 这两方面的综合 即为交换单元所有入线可以同时送入的总的信息量 称为交换单元的容量 2 接口如同需要规定线路上传送信号的标准一样 交换单元也需要规定自己的信号接口标准 30 3 功能交换单元的基本功能是在入线和出线之间建立连接并传送信息 具体来说 交换单元可分别或同时具有点到点功能 同发功能和广播功能 4 质量一个交换单元的质量包括它完成交换功能的情况和信息经过交换单元的损伤 前者包括完成交换动作的速度 以及是否在任何情况下都能完成指定的连接 后者包括信号经过交换单元时的时延和其他损伤 如信噪比的降低 31 2 开关阵列1 开关阵列在交换单元内部 要建立任意入线和任意出线之间的连接 最简单最直接的想法就是使用开关 在每条入线和每条出线之间都各自接上一个开关 所有的开关就构成了交换单元内部的开关阵列 32 图8开关阵列的表示 33 特性 因为每条入线和每条出线的组合都对应着一个单独的开关 开关阵列的交叉点数取决于交换单元的入线和出线数 开关阵列很容易地实现了同发和广播功能 交换单元的性能依赖于所使用的开关 开关阵列具有控制端和状态端 34 数字电子开关可以简单地用数字选择器门电路构成 用于数字信号的交换 图9多路选择器构成的M N的交换单元 35 2 S接线器 1 结构空间接线器由电子交叉矩阵和控制存储器 CM 构成 36 图10空间接线器 37 S接线器 输入控制 工作原理 控制存储器 2 2 1 2 2 2 1 1 1 1 3 n n n n n TS1 TS2 TS3 输入 输出 1 2 1 2 3 3 总结 利用S接线器实现母线交换 38 2 工作原理 按输入线配置的称为输入控制方式 见图10 a 按输出线配置的称为输出控制方式 见图10 b 39 3 时分复用交换单元1 共享存储器型交换单元 图11共享存储器型交换单元的一般结构 40 2 T接线器 1 结构时间接线器采用缓冲存储器暂存话音的数字信息 并用控制读出或控制写入的方来实现时隙交换 因此 时间接线器主要由话音存储器 SM 和控制存储器 CM 构成 41 图12时间接线器 42 2 工作原理控制存储器对话音存储器的控制而言 可有两种控制方式 顺序写入 控制读出 简称 输出控制 控制写入 顺序读出 简称 输入控制 43 图13时间接线器工作方式 3 容量与时延T接线器的容量等于话音存储器的容量 2 N v B t经过T接线器的时延包括信号并串变换时延和存储器时延 存储器时延T NW 44 45 a 输出控制T接线器工作原理 顺序写入 顺序读出 话音存储器 控制存储器 控制写入 总结 利用T接线器完成时隙交换 46 2 3交换网络 机构 交换网络是由若干个交换单元按照一定的拓扑结构和控制方式构成的网络 交换网络含有三大要素 即交换单元 不同交换单元间的拓扑连接和控制方式 47 1 单级网络和多级网络将交换单元按一定的拓扑连接起来 可形成单级或多级交换网络 单级交换网络是由一个交换单元或若干个位于同一级的交换单元构成的 需交换的信息在单级交换网络中一次通过 即一次入线到出线的连接 只经过一个交换单元 48 如果一个交换网络中的交换单元可以分为K级 顺序命名为第l 2 K级 而且满足 所有的入线都只与第1级交换单元连接 所有的第1级交换单元都只与入线和第2级交换单元连接 49 所有的第2级交换单元都只与第1级交换单元和第3级交换单元连接 依此类推 所有的第K级交换单元都只与第K 1级交换单元和出线连接 则称这样的交换网络为多级交换网络 或K级交换网络 50 一般而言 交换网络中交叉点越多 成本越高 建立连接的路径亦越多 阻塞的机会也越少 连接能力也就越强 交换网络拓扑设计的总目标 就是在满足一定的连接能力的要求下 尽量最小化交叉点数 容量相同的多级与单级交换网络比较 交叉点数会大大减少 51 2 内部阻塞 1 内部阻塞的基本概念出 入线空闲 但因交换网络级间链路被占用而无法接通的现象称为多级交换网络的内部阻塞 多级交换网络会出现内部阻塞问题 单级交换网络是不存在内部阻塞的 52 2 无阻塞交换网络研究无阻塞交换网络的目的是如何尽量减少 以至最后消除多级交换网络的内部阻塞 下面给出三种无阻塞交换网络的概念 严格无阻塞网络 不管网络处于何种状态 任何时刻都可以在支换网络中建起一个连接 只要这个连接的起点 终点是空闲的 而不会影响网络中已建立起来的连接 53 可重排无阻塞网络 不管网络处于何种状态 任何时刻都可以在一个交换网络中直接或对已有的连接重选路由来建立一个连接 只要这个连接的起点和终点是空闲的 广义无阻塞网络 指一个给定的网络存在着固有的阻塞的可能 但有可能存在着一种精巧的选路方法 使得所有的阻塞均可避免 而不必重新安排网络中已建立起来的连接 因为目前真正实用的广义无阻塞网络非常少见 所以本课程只讨论严格无阻塞网络和可重排无阻塞网络 54 3 CLOS网络 1 CLOS网络的基本概念CLOS首次构造了一类如图所示的N N的无阻塞交换网络 他指出 采用足够多的级数 对于较大的N 能够设计出一种无阻塞网络 其交叉点数增长的速度小于N1 0 1 也就是说 使用CLOS网络 既可以减少交叉点数 又可以做到无阻塞 55 图8三级CLOS网络 56 由图可知 CLOS网络的结构 两边各有r个对称的m n矩形交换单元 中间是m个r r的方形交换单元 每一个交换单元都与下一级的各个交换单元有连接且仅有一条连接 因此任意一条入线与出线之间均存在一条通过中间级交换单元的路径 m n r是整数 决定了交换单元的容量 称为网络参数 并记为C m n r 57 2 三级CLOS网络无阻塞条件参见图 可以看出 在最不利情况下 中间级会有 n 1 2个交换单元被占用 因此中间级至少要有 n 1 2 1 2n 1个交换单元 即m 2n 1时 可确保无阻塞 所以对于C m n r CLOS网络 如果m 2n 1 则此网络是严格无阻塞的 对三级CLOS网络C m n r 如果m n 则此网络是可重排无阻塞的 CLOS网络的论文参见参见IEEECOMMUNICATIONSMAGAZINE2003 10 58 对于V m n1 r1 n2 r2 三级非对称CLOS网络 如果m n1 n2 1 则此网络是严格无阻塞的 如果m max n1 n2 则此网络是可重排无阻塞的 59 4 TST网络TST网络是在电路交换系统中经常使用的一种典型的交换网络 由前面讨论过的共享存储器型交换单元的T接线器和开关结构的S接线器连接而成 60 1 结构TST是三级交换网络 两侧为T接线器 中间一级为S接线器 S级的出 入线数决定于两侧T接线器的数量 设每侧有32个T接线器 T接线器的容量为512 则网络结构如图9所示 输入侧话音存储器用SMA0到SMA31表示 控制存储器用CMA0到CMA31表示 输出侧话音存储器用SMB0到SMB31表示 控制存储器用CMB0到CMB31表示 61 S接线器为32 32矩阵 对应连接到两侧的T接线器 并采用输出控制方式 控制存储器有32个 用CMC0到CMC31表示 输入侧接线器采用顺序写入 控制读出方式 输出侧T接线器则采用控制写入 顺序读出方式 62 2 工作原理下面以实现第0个T接线器的时隙2与第31个T接线器的输出时隙511的交换为例来说明TST网络的工作原理 参见图9 1 通路建立首先 交换机要选择一个内部时隙做交换用 2 双向通路的建立为便于选择和简化控制 可使两个方向的内部时隙具有一定的对应关系 通常采用半相帧法 63 图9TST交换网络 64 5 BANYAN网络BANYAN网络是 种空分交换网络 是由若干个2 2交换单元组成的多级交换网络 它最早使用干并行计算机领域 目前巳在ATM交换机中得到广泛应用 它适用于统计复用信号的交换 即根据信号中携带的出线地址信息 在交换网络中建立通道 是进行信元交换的有效方法之一 65 1 结构2 2交换单元是具有两条入线和两条出线的电子开关元件 如图所示 图102 2交换单元 66 这种电子开关具有两种状态 平行连接和交叉连接 分别完成不同编号的入线与出线间的连接 达到两条入线中的任意入线和两条出线中的任意出线可进行交换的目的 这种交换网络有一个特点 就是它的每一条入线到每一条出线都有一条路径 并且只有一条路径 如果我们使用12个2 2交换单元就可以构成 个8 8的三级交换网络 其第1级和第2级之间的连接为子洗牌连接 第2级和第3级之间的连接为均匀洗牌连接 如图所示 67 图118 8三级BANYAN网络 68 利用递归的方法 可用较小的BANYAN网络构成较大的BANYAN网络 其构成方法如下 假设已有N N的BANYAN网络 需构成2N 2N的BANYAN网络 则可使用2组N N 再加上一组N个2 2交换单元构成 第一组和第二组N N的2N条出线分别与N个2 2的入线用洗牌连接方式相连 对于N N的BANYAN网络 其级数约为M log2N 每一级需要N 2个2 2交换单元 共需要 N 2 log2N个2 2变换单元 69 图12用8 8三级BANYAN网络构造16 16四级BANYAN 70 用2 2变换单元构成BANYAN网络的具体形式可以有多种 如图所示的几种交换网络均为8 8BANYAN类网络 71 图138 8三级BANYAN类网络 72 2 工作原理因为BANYAN网络的构成非常规则 由其结构可以引出 些重要的特点 1 唯一路径在BANYAN网络中 我们已经知道它的每条入线与每条出线之间都有一条路径并且只有这一条路径 这就是BANYAN网络的唯一路径特点 我们假设它对N N的BANYAN网络也成立 那么 对于2N 2N的BANYAN网络来说 因为2N 2N的BANYAN网络是用前述的方法来构成的 显然从N NBAHYAN网络到最后一级2 2交换单元中共有2N条路径 要到其中某一条出线必须经过其中唯一的 条路径 73 BANYAN网络特性 1 惟一路径 每一条入线到每一条出线都有一条路径 并且只有一条路径 可以利用类似于数学归纳法的方法给予证明 Error Error Error 惟一路径 0号入线到3号出线的惟一路径特性演示 74 2 自选路由由BANYAN网络的构成方法可知 一个BANYAN网络的入线数和出线数相等 并且若假设其为N 则必有N 2M M为级数 再设N条入线和N条出线分别顺序编号为十进制数0 1 2 N 1 则必定可用M位二进制数字来区别N入线和N条出线 由BANYAN网络的唯一路径特点可知 从BANYAN网络的任意一条入线到全部N条出线共有N个连接 这N个连接可以用出线的N个不同的编号表示 即其中的每一个连接都可以用M位二进制数字表示 75 一个N N的BANYAN网络共有M级 每一级有N 2个2 2交换单元 如果把每个交换单元的两条入线和两条出线都依照在图上的上下位置分别编号为0和1 考虑一个由入线i到出线j的连接 这个连接是由M个属于不同级的交换单元顺序连接组成的 从第1级开始顺序排列该连接经过的各个交换单元的出线编号 0或1 则恰好组成一个M位二进制数字 这M位值二进制数字正是出线 的编号 我们从任意一条入线开始 逐个读出各级交换单元相应出线的数字 或1 那么 这些数字组合起来就是出线的号码 可以说明 这个数字的 种不同的取值正好表示了从同一条入线出发的N个不同的连接或路径 76 BANYAN网络特性 2 自选路由 从任意一条入线开始 逐个读出各级交换单元相应出线的数字0和1 那么 这些数字组合起来就是出线的号码 i号入线到3号出线的自选路由特性演示 77 3 编号数字置换像任何交换单元及交换网络一样 BANYAN网络的入线和出线可以都编上号码 并用一组数字的排列或称置换来表示它的一种连接方式 虽然任何一个交换单元及交换网络都可以用置换来表示其连接方式 但对BANYAN网络使用置换表示有特别的意义 这是因为 BANYAN网络是按级由2 2交换单元组成的 每一个2 2交换单元都完成两个数字的一次置换 每一级都完成N个数字的一次置换 换句话说 在BANYAN网络中 表示整个交换网络连接方式的置换是由各级及级间逐次置换构成 78 3 BANYAN网络的内部阻塞BANYAN网络不是CLOS网络 它不符合CLOS网络的无阻塞条件 因此BANYAN网络存在内部阻塞 发生阻塞的2 2交换单元在交换网络的最后一级 即交换网络的两条或多条入线同时试图占用同一条出线 这称为出线阻塞 由于出线阻塞不是由于交换网络本身的缺陷造成的 采用诸如输入或输出缓冲排队方法可以很好地解决 所以通常内部阻塞不包括出线阻塞 发生阻塞的2 2交换单元在交换网络的各级 除最后一级之外 例如在图14中 假设在入线0 1 4 6上同时接收到信元 其路由标记分别为3 7 2 4 即此时需要建立 79 连接1 0 3连接2 1 7连接3 4 2连接4 6 4当连接1和连接3同时到达第2级交换单元时 必然会同时选择该交换单元的出线1 于是发生内部阻塞 如果不采取适当措施 就会造成信元丢失 如图中入线4上的信息未送到出线2 应该注意的是 BANYAN网络的内部阻塞发生在2 2交换单元内部 而不是级与级之