T-S-T三级交换网络路径搜索算法的研究

1 引 言

光纤通讯技术的飞速发展使得目前高速通讯网络性能的瓶颈集中在高速交换系统，研究、设计和制造高速交换系统对目前高速通讯网络具有极其重要的意义。而且随着电信网和计算机网络的高速发展，高速大容量的交叉连接或交换设备和芯片的性能也在大幅度的提高。同时由于现在的交换机在不停地更新换代，对新的交换算法的需求也在不断增加。

本文的研究工作旨在利用矩阵置换的思想，模拟开发一种基于T(时分)-S(空分)-T(时分)交换网络的调度算法。提出一种新的三级交换的矩阵模型，并在这种模型上设计相应的无阻塞交换算法。利用矩阵作为数学模型，可以利用矩阵的置换操作搜索交换的设置。算法设计和实现的过程中，大量的实验表明，本算法具有良好的特性，而且通过芯片级联可实现。

本算法不同于以往的基于图论的寻径调度算法，力图通过对这个算法的研究，为未来的大型综合数字交换网络奠定理论和实践基础，并为变化多端的网络环境下快速建立有保障的网络服务提供先期的技术研究。

2 T-S-T数字交换网络结构

典型的T-S-T数字交换网络可以用图1的模型描述。

整个交换网络以S接线器为核心组织。对于一个具有N条输入复用线和N条输出复用线的交换网络而言，需要配置2N套T接线器，其中N套在输入侧，为初级T接线器，完成用户的发送时隙到交换网络内部的公共时隙的交换；N套在输出侧，称为次级T接线器，完成将交换网络内部的公共时隙上的住处传送到另一用户的接收时隙上。因此，交换网络内部提供的公共时隙的数量就决定了交换网络中能够形成的话音通路的数量。中间的S接线器主要由一个N×N的交叉接点和具有N个存储器的控制存储器组来组成，用来完成将交换网络内部运载的用户信息从一条输入侧复用线上交换到规定的一条输出复用线上。

3 T-S-T交换网络数学模型的建立

3.1 问题的描述

在建立T-S-T交换网络的数学模型之前，首先给出这样的数学抽象：用1个n×n的输入矩阵inport表示输入数据流，每一行代表1个T-S-T交换网络的输入链路，也就是说每一行代表l根链路HW，每一行内元素的位置代表1个时隙内各个数据帧的次序关系。由于T交换是对同一根链路的不同时隙之间进行的交换，故将其抽象为矩阵的行内置换。因此当输入矩阵inport经过一级T交换后，得到1个中间矩阵after_t1，此矩阵是inport矩阵通过每一行数据的行内变换得到。同理，由于S交换是在不同链路的相同时隙之间进行的交换，类似于对一个矩阵在其同一列内进行列内变换，称其为列内置换。这样当after_tl又经过S交换，得到另外一个中间矩阵after_s，此矩阵是after_tl矩阵通过列内变换得到的。最后，又经过第二级的T交换，产生outport矩阵，类似地，他是after_s矩阵通过行内变换得到。于是，可以将交换算法这样描述：对于初始矩阵inport，怎样能找到一种满足T-S-T三级交换的变换方式，最终得到1个输出矩阵outport。而且对于用户要求的任意outport(此矩阵与inport是单播关系)，都可以通过算法找到其变换方式，即可以找到2个中间矩阵。

3.2 矩阵模型的建立

将T变换对应于矩阵的行内变换，而S变换对应于矩阵的列内变换，这样上面的这一段叙述就可以描述为inport矩阵经过一系列的行内变换得到after_t1矩阵，after_t1矩阵经过一系列的列内变换得到after_s矩阵，after_s矩阵又经过一系列的行内变换得到outport矩阵如图2所示。

4 交换算法的设计思想

从上面论述可以看到，本文已经将具体的路径选择问题，抽象成纯粹的数学问题。接下来，本文将从纯数学的角度来找出一种算法，从而解决这个交换问题。

4.1 问题的数学分析

观察从输入矩阵inport→中间矩阵after_t1→中间矩阵after_s→输出矩阵outport整个的变换过程，输入矩阵先后经过2次时间变换，而只经过1次空间变换。也就是说，当输入矩阵inport中的某个元素，要发生列变换时，他只有1次变换机会，此情况对于inport中的任意一个元素都是适用的。所以，时间变换只起到调整作用，因此本文要重点考察空间变换，试图从空间变换S变换中找出矩阵的特点。

不难发现，中间矩阵after_s(n×m)(一般情况下，本文取m=n，无阻塞的交换网络)有这样的特点：每一列的n个元素，他们的行号包含从1～n的所有行号。如上面的例子可以看到这一点。这样，将after_s矩阵经过1个空间变换，向空间变换的反方向变换的时候，这n个元素就会回到在inport矩阵原来的行上，在经过1个时间变换的反变换就可以变成为输入矩阵inport。

在发现中间矩阵after_s的特点之后，就有了基本的思路。这里的算法只要能够使得outport矩阵经过1个时间变换的反变换后能够变成为满足中间矩阵after_s的特点的矩阵，那么，也就找到一种矩阵的变换方式。解决了这个交换问题。有没有一个从inport到outport的变换的问题，转换成能不能找到一个满足after_s矩阵要求的问题，此after_s矩阵只是outport矩阵经过一个时间变换得到。

这样，对于任意输入矩阵inpott，经过矩阵的行内、列内、行内3次变换可以得到任意输出矩阵outport，从而成功的完成了T-S-T交换。本文为了方便描述inport和T-S-T交换的核心算法，不妨将inport定义为顺序矩阵n×n，就是以行为序，从0～n×n-1，例如n=4，inport被定义为：

而outport将是inport的任意置换矩阵。在这里也不妨将outport假设为：

为了从inport矩阵变换到outport矩阵，必须找到两个中间矩阵after_t1和after_s，从而完成交换路径的接续。因此本文的目标是研究一种算法，根据输入矩阵和输出矩阵产生这两个中间矩阵，从而使处理机可以根据4个矩阵往寄存器阵列中填值，这样就可以实现T-S-T网络交换。为了以后叙述方便，3个寄存器阵列定义为：Tregister1(时分)、Sregister(空分)、Tregister2(时分)。

由于在实际的T-S-T交换中，CPU根据各个控制寄存器中的值来完成交换。由交换的特点可知，每个控制寄存器的值是由输入序列和输出序列决定的。其中Tregisterl的值可以由inport和after_t1决定，同理，Sregister的值由after_t1和after_s决定，Tregister2的值由after_s和outport决定。

4.2 算法思想的设计

算法设计要求：

(1)对于任意给定的输入矩阵和输出矩阵，都能够得到2个中间矩阵；

(2)由输入矩阵到第一个中间矩阵只能经过一系列行内置换；

(3)由第一个中间矩阵到第二个中间矩阵只能经过一系列列内置换；

(4)由第二个中间矩阵到输出矩阵只能经过一系列行内置换。

由行内变换和列内变换的性质可以推断出after_t1(AT)和after_s(AS)矩阵的特点如下：

AT的特点：ATij=INij'(只能在同一行上进行置换)；AS的特点：AS是inport的一个置换矩阵；AS的同一列上不可能出现inport同一行上的元素。

这是由于AT同一列上不可能出现inport同一行上的元素，而AT到AS经过的是列内变换。

来源：《现代电子技术》