宽带网络交换技术

(4) 多级互连网(络)交换(Multistage Interconnection Network Switch)
     多级互连网络(也称MIN)曾经在电路交换网络中被广泛研究过，其目标是通过多级网络互连的形式来减少交叉节点的数目。Banyan网即是其中比较典型的一种，其特征是从输入口到输出口仅存在一条通路。其它类似的网络有baseline网、shuffle-exchange(也叫OMEGA)网以及flip网等。

     MIN：Multistage Interconnection Network
       a. 在电路交换网中采用，
       b. 在计算机紧耦合互连结构中经常使用。

     目标：通过多级互连的形式来减少交叉节点的数目。

     举例与特征：
       a. 由基本交换模块靠一定的拓扑结构组成MIN，
       b. 基本交换模块可以是2×2也可以是32×32→b×b，
       c. 最有代表性的是C.Clos网(Clos是本世纪50年代最著名的学者之一)。

     Delta网是C.Clos网络的代表，它在构成MIN交换机构时有以下特征：
       a. 由若干相同的b×b交换单元构成，
       b. 其规则性和互连模式非常适合大规模的芯片集成，
       c. 具有Self-routing特性，输入到输出需要log_bN比特的routing tag，
       d. 由log_bN级组成，每一级含N/b个基本交换单元。

     下图列举了Delta变形拓扑的几个例子。

     尽管上述网络的模式不同，但其性能是基本相同的，这些性能特点包括：
     •它们由log₂N级(N为交换网络之容量)组成；
     •利用选路地址在交换网络内自选路由；
     •可以由小的交换单元按规则的模块方式构成大的网络；
     •其规则性和互连模式便于VLSI芯片实现。

     但是上述MIN存在内部阻塞，即信元在网络内会因为同时到达一个节点单元的出线而发生冲突。为了减少内部冲突，可采取以下一些措施：
     •提高内部链路上的操作速率；
     •在每个内部交换节点上设置缓冲器；
     •采用多个并行的网络同时工作；
     •增加串联的网络级数；
     •在Banyan网的前面加分配网络以均匀地分配到达负荷；
     •在Banyan网的前面采用Batcher排序网，把输入的信元按目的地址排序。

     Delta网存在内部竞争(Contention in a Delta Network)。
　　原因：竞争内部链路、队列或其它共享资源。如下图所示。

     降低Delta网内部阻塞的措施有以下五条：
       a. 在交换机构中每个基本交换单元内设置缓冲器(队列)，
       b. 提高内部链路的速率(相对于外部而言)，这样可以降低内部链路负荷，使竞争的实际概率为零“0”，
       c. 在交换节点之间采用反压(backpressure)机制以延缓阻塞信元的发送，
       d. 在入线和出线之间使用多个并行网络(多个平面)提供多条通路，
       e. 在交换节点之间提供多条内部链路，这种做法会使信元到达交换机构出线的顺序发生变化，因此需要在交换机构的输出端对信元重新排序。
　