Interconnection-Networks-ch6

Non-Blocking Networks

如果网络可以处理输入和输出排列的所有电路请求，则称该网络为非阻塞网络。即，可以形成从每个输入到其选择的输出的专用路径，而没有任何冲突（共享通道）。相反，如果网络无法处理所有此类电路请求而没有冲突，则它就是阻塞网络.

两种类型的非阻塞网络。strictly non-blocking, rearrangeably non-blocking

首先，如果可以每次一个电路递增地设置任何排列，而无需重新路由（或重新排列）任何已设置的电路，则网络严格不阻塞。如果可以将任何未使用的输入连接到任何未使用的输出，而无需更改任何其他流量所采用的路径，则说明网络完全是无阻塞的。

相反，如果网络可以路由电路进行任意排列，则网络可重新排列为非阻塞（或简单地可重新排列），但是排列的渐进式构造可能需要重新布置一些早期电路，以允许以后建立电路。可重新排列的网络可以将任何未连接的输入连接到任何未连接的输出，但是可能需要重新路由一些不相关的流量才能建立连接。

6.1 Non-Blocking vs. Non-Interfering Networks

分组交换网络中，资源分配好之后就不会互相影响。

实际上无阻塞的网络就是为了实现无干扰的网络。

6.2 Crossbar Networks

一个n×m交叉开关或交叉点开关将n个输入直接连接到m个输出，没有中间级。

m=n,square

m>n||m<n,rectangular

在输入线与输出线交叉的每个点（即，在每个交叉点），开关都可以选择将输入线连接到输出线。为了正确操作，每个输出最多必须连接到一个输入。但是，输入可以连接到多个输出.

今天，大多数交叉开关都是使用数字逻辑实现的，其结构如图所示。 n条输入线中的每条连接到m n：1多路复用器的一个输入。多路复用器的输出驱动m个输出端口。多路复用器可以通过驱动输出线的三态门或线或门实现。

简化图：

纵横开关显然对于单播和多播流量都严格不阻塞。可以通过开关不同开关门。

建造其他无阻塞网络，原因是成本和可伸缩性。

成本都是$N^2$的。

下图显示了如何使用2×2的n×n交叉开关阵列构造2n×2n交叉开关，从小型交叉开关构建大型交叉开关的成本也是二次方。

6.3 Clos Networks

6.3.1 Structure and Properties of Clos Networks

Clos网络是一个三阶段网络，其中每个阶段都由许多纵横开关组成。对称Clos的特征是三元组（m，n，r），其中m是中级开关的数量，n是每个输入（输出）开关上的输入（输出）端口的数量，r是输入和输出开关的数量。此处输入和输出都一样为r和n.对于不一样的网络可以设为$(m,n_0,n_1,r_0,r_1)$

中级交换机，到每个输入和输出交换机都有相应的链路。

在引用Clos网络的输入和输出端口时，我们将交换机s的端口p表示为s.p。

6.3.2 Unicast Routing on Strictly Non-Blocking Clos Networks

定理：A Clos network is strictly non-blocking for unicast traffic iff m ≥ 2n − 1.

要将单播呼叫从a.i路由到b.j，可通过将a不使用的交换机列表与b不使用的交换机列表相交来找到中间级交换机。

如下图，电路从输入1.1（1）路由到输出3.3（9）。其中虚线为已经本占用的线路。最终选择为加粗的线。一个完整的排列{5、7、11、6、12、1、8、10、3、2、9、4}。也就是说，输入1（1.1）路由到输出5（2.2），输入2（1.2）路由到输出7（3.1），依此类推。

假设按{9,6,7,8,3,12,10,5,1,11,2,4}的顺序应用呼叫。

显示了在（5,3,4）Clos网络上路由此呼叫集的过程。该表的每一行对应于路由过程中的一个步骤。该表的每一行对应于路由过程中的一个步骤。前三列显示呼叫来自的输入交换机（进入），呼叫去向的输出交换机（离开）和分配给呼叫的中间交换机（中间）。其余八列给出位向量，显示哪些中间交换机不受每个输入和输出开关的影响。

第一个呼叫为9（3，3），查排列集合，输入交换机为3，输出应该为3，交换机为输出switch1。并且由于第一个调用没有阻塞的路径，因此将其分配给中间交换机1.所以将输入交换机的路径3到中间交换机1忙（输入空闲3 = 01111），从中间交换机1到输出交换机1的路径忙（输出空闲1 = 01111）。