CLOS网络及其路由算法

杨宜镇 管红光 周炜 吴致远

摘 要：本文首先对CLOS网络进行了简单的介绍，然后结合CLOS网络在路由算法中的应用，详细阐述了CLOS网络的路由算法。

关键词：CLOS 网络 路由 拥塞 交换结构

中图分类号：TN915.07 文献标识码：A 文章编号：1674-098X（2012）12（a）-000-03

1 CLOS网络简介

最初的Cols网络是一种经典的严格无阻塞的多级互连网络。由Charles Clos于1953年提出。是在Benes网络的基础上演变而来，该网络由于在通信网和多处理器计算机系统中被广泛采用，因而受到广泛重视，从CLOS的提出以来，人们对其拓扑结构、连接特性和控制算法进行了较为深入的研究，并取得了不少成果。

1.1 CLOS网络的定义

CLOS网络是由多个集成单元（又称交换单元）组成，每个集成单元包含n个输入端口，m个输出端口（m>1，n>1，如果m=n，即为对称CLOS网络）。任意的前级到任意中央级有且只有一个连接供使用，同样任意的中央级到任意的后级有且只有一个连接。也就是说，从stage1的任意一个集成单元到stage2的任意一个集成单元，有且仅有一条连线（或者说一条路径），同理，对stage2到stage3也是如此。但是我们可以发现，从stage1的任意一个集成单元到stage3中的任意一个集成单元有m条路径。但是，这也并非指这个网络完全没有内部竞争，要使它达到严格无阻塞，必须满足一定的条件，这里的条件在三级COLS网路结构中有更详细的

讨论。

图1 CLOS网络模型图

1.2 CLOS网络的设计

多级交换结构之间的不同取决于各交换单元之间的互连形式， 在多级交换结构中，级数越少，交换延迟也就越小，但交换通路也相应减少，这导致碰撞阻塞的更容易产生，因此多级交换结构拓扑的确定有一个各项性能之间的折中。各项性能包括：交换延时、交换通路数目、碰撞概率、输入级与输出级的规模、集成单元的规格（就是交换单元的输入端n输出端m，一般把m×n 称为集成单元的规格），还有芯片的制造工艺能力限制以及具体使用的网路交换设备具体设计等诸多因素。三级CLOS网络结构是CLOS网络最典型的一种结构，后面出现的5级、7级、9级等结构也是在3级CLOS网络结构的基础上，加以改进而成。比如将3级CLOS网路结构的第二级（stage2）换成一个3级的CLOS结构，就形成了5级CLOS网络结构。

1.2.1 三级CLOS网络结构

Clos网络使用非方形交换单元构，典型的CLOS网络是三级全互连对称网络，三级：stage1、stage2、stage3，对称：入线数目=出线数目，三级对称Clos网络C（m，m，r）的输入级有r个n×m交叉开关，中间级有m个r×r交叉开关，输出级有r个m×n交叉开关，网络共有N=n×r个输入与输出端，每个中间级开关与每个输入和输出开关有且仅有1条链路连接。

图2 三级CLOS网络结构示意图

从直观上看，相邻两列的交换单元为全连接是交换性能最好的一种，但全连接方式成本较为昂贵，相互连线众多，需要更多时间调度相对多的输入端口，影响了处理速度。因此非全连接形交换有着更为经济的应用。CLOS网络是得到广泛研究的一种多级交换结构，它的特点在于可伸缩性、固定交换时延、数据传输的自路由性与有序性。由于自路由性，其数据转发过程非常简单，数据信元能并行通过该结构，但是在信元交换负荷接近网络信元交换负荷的极限时，但如果超过一个信元在同一时刻到达一个交换单元的话，就会产生碰撞冲突。因此，在设计CLOS交换结构时，如何处理好拥塞冲突，是考虑各项性能折中的一个重要因素之一。

在CLOS网络交换结构中，m、n值的选取是决定网络的交换性能2个重要参数。结合上图，做以下分析：⑴当m=n的时候必须要重排才能达到完全无阻塞的目的，完全无阻塞就是指它所有输入输出级的端口都被业务占满的情况，这种结构就是我们后期需要研究的可重排无阻塞网络，它消耗的资源是最小的。⑵m=2n-1的时候不需要任何重排，也就是说只要业务要求的输入输出口空闲，不管它怎样路由都不会出现阻塞，这种结构耗的资源是最多的。⑶n

无阻塞：就是指即任何一条输入到任何一条输出都必定能找到一条路由，而不会出现阻塞。

可重排：在超过一个信元同一时刻到达一个交换单元的，产生碰撞冲突的情况下，通过对已有的连接重新选路来建立一个连接，来解决碰撞冲突的方法。

2 CLOS网络结构的路由算法

前面提到过，设计CLOS网络结构，其网络机构的交换性能：包括伸缩性、交换时延、数据传输的自路由性与有序性，还有一个最重要的因素就是如何处理网络交换的碰撞冲突，也称为拥塞。

有的人可能会问，既然有严格无阻塞网络，为什么不直接使用严格无阻塞技术呢？当然，无阻塞网络当然是我们所追求的理想目标。但是，为了增加容量和降低阻塞，必须大量上调m和n的数量，会使实现交换单元的数量和交换网络的技术成本大大增加。我们研究CLOS网络结构，就是要研究使设计CLOS网络结构的代价与网络的交换性能的折中达到最优化设计。所以上面提到的完全无阻塞网络结构不在本文的研究范围。

评价一种路由算法好不好，其实就是看其总体得到的阻塞概率大小，要达到最小阻塞概率，那么它的每一次业务所走路径对后序业务的影响应该尽可能的小，达到这个目的方法会有很多种，下面仅从两个角度分别讲述两种路由的算法思想。

2.1 优先级筛选中间模块法

好的路由算法应该是在随机给定业务的情况下，通过该算法找到的路径给后来的业务留下了最大的可用空间，当我们每次都这样选择路径的时候，也就是最大程度地降低了后来业务发生阻塞的可能性。对于每一个业务可能存在多条路径，也就是有多个中间模块可用，那么我们要做的就是极好地利用clos的结构特点，用优先级方式筛选出最适合的中间模块。

2.1.1 当前业务对后面业务造成的影响

假设当前业务为（ab），a为输入端口，b为输出端口，f为a所在的输入单元编号，g为b所在的输出单元编号，中间可用的交换单元集合为V，V代表的是所有中间模块中恰恰输入口f和输出口g都空闲的单元，那么此业务的路径选择也就是对中间交换单元的选择，也就是选出仅仅对f，g的后序剩余端口有关的业务产生的影响最小的单元。因为每个输入输出级的单元都能与中间模块相连，且对于每个中间单元来说只能连接一次，如果我们选中了V中的一个，那么与f，g单元的后续剩余端口有关的业务将不能再与此中间单元相连，而除f，g以外对后来其它单元上需要经过此中间单元上的业务没有任何影响，那么我们要做的就是找到最合适的中间单元，使f，g的后序剩余端口还能最大可能地连接到每一个输出或输入单元，如图3所示：

图3 三级CLOS网络业务交换模拟图

2.1.2 寻找最适合的中间模块

在分析了当前业务对后续业务造成的影响之后，要解决的问题就是建立一个算法模型，通过该模型的算法来寻找出最适合的中间模块。为了让大家更好的理解该算法的思想，先对描述该算法中用到的符号做一下说明：

ab：代表一条业务流，a为输入单元的输入端口，b为输出单元的输出端口，

f：a所在的输入单元编号

g：b所在的输出单元编号

U：能同时和f，g连通的中间单元的集合（图4中显示的中间2，3单元）

V：所有还能与f单元相连的中间单元的集合（图4中显示的中间前三个单元）

W：所有还能与g单元相连的中间单元的集合（图4中显示的中间后三个单元）

Fout（V）：V内所有单元的空闲输出口集合

Fin（W）：W内所有单元的空闲输入口集合

很显然，，。我们寻找最适合的中间单元的原则就是：从U中选择一个单元，使得除去这个单元后，f，g的后序剩余端口还能最大可能地连接到每一个输出或输入单元，整个过程可以按以下步骤进行：

首先从U中找出所有跟f，g的后序剩余端口业务相关的中间单元V和W：

对于V内的每个单元，总能找到唯一的一条路径与输入单元f相连，所以我们只看是否能通过它的空闲输出端口连接到任意的输出单元，如图4中显示，记下它的空闲输出端口output[i] ，集合Fout（V）（i为中间模块的端口号，假设其规格为y×y，那么（0≤i≤y）；

对于W内的每个单元，总能找到唯一的一条路径与输出单元g相连，所以我们也只看是否能通过它的空闲输入端口连接到任意的输入单元，记下它的空闲输入端口号input[i]集合Fin（W）；

经过步骤1之后，我们可以发现输入单元f的剩余端口到任意输出单元的所有能成功路由的个数就等于Fout（V）里不同元素的个数（如图4中所示2.3单元的最后一个输出端口都是白色圆圈，那么我们就说他们是相同元素），输出单元g的剩余端口到任意输入单元的所有能成功路由个数等于Fin（W）里不同元素的个数，相同元素就代表了相同的空闲端口，相同元素出现的次数就是空闲次数。

其次寻从U中寻找最适合的中间单元，使得f，g的后序剩余端口还能最大可能地连接到每一个输出或输入单元。假设=，当F内不同元素的个数最多的时候我们取max，这时候，通过该算法找到的路径给后来的业务留下了最大的可用空间。那么我们的目标就是在U里找到一个最好的单元，使得除去这个单元后F=max（）。这就是该模型的最优目标。

图4 寻找中间交换模块示意图

下面结合上图，通过1个例子来说明该模型的决策过程。为了避免图形不至于太混乱，上图中有部分连线没有画出来。

例子说明：由于图4中3～n之间的单元没有画出来，所以我们只对前3个单元进行分析，n个单元的分析思路是一样的。假设output[i]是中间模块V的所有输出端口，Fout（V）是output[i]中空闲端口的集合，也就是图中所有中间单元输出端的白色圆圈，这个集合内的每个元素就是这些白色圆圈的编号，每个中间单元的端口编号都是从0开始，比如说中间模块包含1.2.3单元，1单元的空闲输出端也就是白色圆圈编号为{0.2.4.5}，2单元的为{1.6}，3单元的为{0.1.2.5.6}。那么Fout（V）的所有元素就为{（0.2.4.5），（1.6），（0.1.2.5.6） }，其中0.1.2.5.6都出现了重复， 说明他们有相同的空闲端口，且都出现了2次。说明分别都有2个单元上这些端口是空闲的，4只出现了一次，说明只有一个单元上4端口是空闲的，Fout（V）里不相同的元素为{0.1.2.4.5.6}，说明输入单元f的剩余端口能到达6个输出单元，如果我们令3单元的3号输出端口也空闲，那么我们可以做如下比较：

（1）假设从a->b的业务流选择中间模块的2单元，那么f和g单元剩下的端口业务将再也不能从2这个单元路由，我们在计算F的时候就必须忽略掉跟这个单元有关的所有空闲端口，那么结合上图可以得出：

Fout（V）={（0.2.4.5），（0.1.2.5.6）}，Fout（V）内的不同元素为{0.1.2.4.5.6}；

Fin（W）={（1.2.5），（1.2. 4.5.6）}，Fin（W）内的不同元素为{1.2.3.4.5.6}；

F=max（）={（0.1.2.3.4.5.6）， （1.2.3.4.5.6）}，那么F的最大值就为不同元素个数13，也就是说当选择2单元的时候f单元的剩余端口还能到达7个输出单元，而g单元的剩余端口还能到达6个输入单元。

（2）同理，假设从a->b的业务流选择中间模块的3单元，结合图4可以得出：

Fout（V）={（0.2.4.5），（1.6）}，Fout（V）内的不同元素为{0.1.2.4.5.6}；

Fin（W）={（1.2.5），（1.2.4）}，Fin（W）内的不同元素为{1.2.4.5}；

F=max（）={（0.1.2.4.5.6），（1.2.4.5）}，那么F的最大值就是不同元素的个数10，也就是说当选择3单元的时候f单元的剩余端口还能到达6个输出单元，而g单元的剩余端口还能到达4个输入单元。

通过上面的比较，我们应该选选取F值较大的2单元。

如果上面2中情况得处的F的最大值相等，也就是在选择不同的中间单元之后得到的F值最大的单元不止一个的时候，可以选取内元素个数最多的单元，这样的话，在f，g单元的剩余端口能最大可能地到达输出/输入端的时候，也给予了最多的路径选择。如果出现F的最大值相等，并且内元素个数也相等的情况，可以随机或者按照筛选的先后顺序选取其中的一个单元也是可行的。这种情况，在业务交换负荷很低的情况，是可能出现的。

2.2 最优选路路由算法

2.2.1 传统CLOS网络路由选路算法思想

假设网络是由规格为 n×m的集成单元组成（n代表集成单元输入端口数目，m代表输出端口数）。给定输入端口X（因为整个网络结构对外是一个整体，所以这里的X与网络结构中某个具体集成单元的端口编号是有区别的，如果网络输入/输出端有8个集成单元，那么X可以取 1～n×8之间的任何值，表示业务从X端口进入）；给定输出端口Y（这里的Y，跟前面提到的X相同，表示业务要到达与Y端口相连的设备），路由算法描述如下：

对于给定的输入端口X，由X/n向上取整得到i，将第i个交换单元的输出端口中没有被占用的端口放在一个集合{I}里（已经被占用的端口视为无效端口），此时{I}集合里的端口号表示可以和第一级建立连接的第二级的交换单元编号。

同样，对于给定的输出端口Y，由Y/n向上取整得到p，再将第p个交换单元的输入端口中没有被占用的端口放在集合{P}里，此时集合{P}里出现的端口号表示可以和第三级建立连接的第二级的交换单元。

如果端口号Z同时出现在集合{I}和{P}里，表示第一级和第三级均能和第二级的第Z个交换单元建立连接。

2.2.2 有阻塞网络的最优选路路由算法思想

基于以上情况的考虑，我们对上面的选路算法进行改进，改进后的算法最有利于后续的选路，中间级交换单元的选择也较平衡，这就是最优选路路由算法。

算法思想：在每条连接线路选取中间级单元时，我们计算一下一旦此连接建立，对于后续的连接情况会产生多大的影响，即后续的所有的需要连接的线路中，不能连接成功的所占的比例。此比例越小，表明对后续的影响越小。在每次选择中间级单元时，均选取此比例（影响）最小的单元，这样就能确保每次选路最优了。

最优选路路由算法描述如下：如前所述，如果在建立第n条连接时，中间级有k个交换单元满足通路要求，我们先选取第i（1≤i≤k）个建立连接。此时还剩下N-n个输入和输出，表明还可能有（N-n）×（N-n）条路径需要连接，但有阻塞网络不能保证所有的连接都能成功，接着计算下（N-n）×（N-n）条路径中不能连通的路径所占的比例，定义为组塞概率，f（n，i）。然后我们释放第i个中间交换单元，选取第j（1≤j≤k，j≠i）个，再计算f（n，i）。我们将k个中间级的情况都计算一次组塞概率，最后选取组塞概率最小的那个中间级交换单元，即f（n，z）≤f（n，i），1≤i≤k。这样每次选路，都选取能使后续的可连接数最多的路径，此为最优选路路由算法。

3 结语

CLOS网络是科学家们在20世纪五、六十年代，为了解决电话系统里电路交换的问题，提出的解决方案，其中还包括 Banyan网络、Omega网络、Flip网络和Benes网络等等。其中许多交换网络技术具有超常的前瞻性和强大的生命力，即使经历了50多年的洗礼，其间出现了大规模集成电路、光通信等重大的技术变革，其基本原理依然经久不衰，依然为今人所用，实在是令人叹服。近年来，随着Internet，整个IP网络的流量和规模在急剧膨胀，如何提高网络关键设备—路由器系统的扩展能力是目前需要解决的关键问题，而寻求新的交换技术更是对网络研究人员、科学家们的又一重大挑战。

参考文献

[1] Clos C.A study of nonblocking switching networks[J].Bell Syst Tech J，1953，32（2）：406-424.

[2] Gordon J，Srikanthan S.Novel algorithm for Clos-type networks[J].Electron Lett，1990，26（21）：1772-1774.

[3] 刘亚社，刘增基，胡征.Clos型大规模ATM交换网络的虚连接无阻塞特性研究[J].电子学报，1999，27（10）.