李锶锶

摘 要：交换网络（Switching Network）被广泛应用在计算器通讯、平行处理、阶层交换及积体电路绕线等领域中。在各领域之间会因为性质及对象的不同，对于交换网络的效能亦会有所不同的要求，为使系统提高效能、增加交换能力以及减少交换的时间，一般采用无阻塞交换网络（Non-Blocking Switching Network），然而，交换能力愈好往往代表其须使用数量较多的交换元（Switch Element）以及采用较复杂的连线架构，此举却会使得交换网络的成本增加。

关键词：任意平面；交换网络；容错设计

中图分类号：TP393 文献标识码：A

分析任意平面交换网络及其组成规则，经此规则所组成的交换网络皆为无阻塞交换网络，（Unrestrained Planar Switching Network）简称为UPSN，对于一个n输入的UPSN，存在有（n-1）种平面交换网络；若将UPSN中的交换元视为比较器，则每个UPSN可作为平面排序网络使用。本论文将针对所组合出的平面交换网络设计自由路（Self-routing）演算法以及适用于所有UPSN的连线建立算法，经由算法可使每个输入埠的封包正确送达其所要求的输出埠。最后，将针对所有UPSN架构设计其相对应的容错设计，此容错设计可容许UPSN中有任意一个交换元损坏，对于一n输入的UPSN，于交换网络中放置备用交换元，最佳只需n-1个，而最差仅需2n-4个备用交换元，则可使得有任何一个交换元损坏时，经由适当的选取算法选取备用交换元后，回复原本无阻塞交换网络的特性并符合UPSN的组成规则。

1 交换网络架构的容错设计

组成各种交换网络的交换元，由于交换网络架构及连线算法的不同，可能造成某些特定交换元使用频率偏高，这些使用频率较高的交换元，其寿命相对较短，交换网络架构设计上皆尽可能精简交换元数目，以求得在硬件花费上的最佳表现，若因些许交换元损坏而丧失交换网络的交换能力与其原本的特性（无阻塞交换网络不在具有无阻塞特性），则会造成交换网络的维护更加困难，成本愈高，是如何设计容错架构的问题。

2 交换网络架构容错设计

以Spanke-BenesNetwork为列，Spanke-BenesNetwork属于平面交换网路，所有平面交换网路皆可以任意平面交换网络UPSN表示。当Spanke-BenesNetwork其中一个交换元损坏时，则会丧失原本具有的无阻塞交换网络的特性，我们提出一种称为FaultTolerantSpanke-BenesNetwork，简称FT-Spanke-Benes，对于一n输入的Spanke-BenesNetwork，只需将n-1个额外的交换元放置到特定位置，即可针对此交换网络中任何一个交换元损坏时，仍维持Spanke-BenesNetwork无阻塞交换的特性。

图1（左）所示为一6输入的Spanke-BenesNetwork，可以UPSN的1，3，5，4，2表示，图1（右）则为其容错设计，红色部分为额外放置的备用交换元。

我们将说明当Spanke-BenesNetwork中有任何一个交换元损坏时，如何选取备用交换元来进行其架构的重组。例如当ROW3有任一交换元损坏（BAD）时，我们将整条ROW3的交换元全部设定为不动作（Straight），即状态0，等同于移除了ROW3所有交换元，此时可以发现，当有任何一个ROW的交换元个数比ROW3小时，则必须将备用交换元取出使用（包括交换元个数为0的ROW5）。而ROW3的交换元个数为4，可知ROW0、ROW1、ROW4及ROW5须将备用交换元取出使用。所以最后的重组结果为（2，4，5，3，1），仍是一无阻塞交换网路。

我们以上述的范例可以发现以下规则：当交换元损坏时，损坏的ROW中有i个交换元时，则需取出i个额外备用交换元使用，才能使其形成符合UPSN组成规则的无阻塞交换网络。

3 容错设计的分析

在一n输入的UPSN中，当有一交换元损坏时，则将此交换元所在的Row所有交换元设为状态0，亦即若有多个交换元损坏时，若其都在同一层Row中，则最大可容许n-1个交换元损坏，最少则为1个。

于容错架构设计中，我们也可知，于不同的UPSN架构中，所需的备用交换元数量皆不相同，对于一个n输入输出的UPSN，其最佳的情况，例如于Triangle-Type架构及Spanke-BenesNetwork架构下，其所需备用交换元个数仅需要n-1个，意即每层Row仅需准备一备用交换元，最差的情况则时交换元个数恰好为最多及第二多，其所需备用交换元个数为2n-4，相当于需为每层Row准备两个备用交换元。

容错设计的备用交换元个数与交换元总数的比率图，蓝色部分为备用交换元个数除以交换元总数的比率，橘色为最佳备用交换元个数除以总数，而灰色则为最差交换元个数除以总数，横轴为交换网络输入数，介于2～1000，纵轴为其比率，由此图可以知道，当一UPSN架构的输入输出数n愈大时，其所需的备用交换元个数愈趋近于最差，然而，其备用交换元个数与交换元总个数1＼2相比，其级数上明显较少。

结语

连线建立算法是以C++程序语言所撰写，目的在于验证此连线算法的正确性，用户可以任意决定UPSN的输入数、交换元放置方式以及目的端所要求的输出端，或者由程序自行乱数产生，程序有两种结束方式，其一为当有输入端经由Right-to-Left连线建力算法建立连线后，其到达的目的地为错误的输出端，此时可以知道此种算法有错误，程序将会结束，其二为所有连线皆建立完毕且所有输入端皆到达正确的输出端，代表此次UPSN，Right-to-Left连线建立算法为正确，程序将会结束。

参考文献

[1]富弘毅，杨学军.大规模并行计算机系统硬件故障容错技术综述[J].计算机工程与科学，2010（10） .

[2]张祖平.规则网络容错路由算法及可靠组播的研究[D].中南大学，2005.