Clos交换网络的一种基于矩阵分解的路由指派算法

刘晓锋，吴亚娟

(西华师范大学 计算机学院，四川 南充 637009)

0 引 言

Clos 交换网络［1］发展至今已有60 余年的研究历史，最早是针对电话交换网络，随着IP 网络的快速发展和Clos 网络本身的良好可扩展性及优越的网络性能，它被应用于IP 网络的分组交换中，特别是用于高速、大容量交换机/路由器的设计中，如Juniper T1600/TX -Matrix Plus 系列． 另一方面，随着数据中心网络(data center networks，DCN)［2］的诞生和发展，Clos 交换网络再次成为研究热点．一个DCN 通常由成千上万甚至上百万的服务器和交换机/路由器组成，如何组织如此之多的服务器和交换机才能满足DCN 的高可扩展性、低延迟及低能耗的本质需求是一个极其重要的研究课题．Clos 网络或其扩展结构(如Folded -Clos 结构)作为DCN 的拓扑结构已被广泛研究［3］［4］，但很少涉及底层交换节点的体系结构及路由算法．目前相应于Clos 交换网络的迭代类路由指派算法因在线卡与调度器之间较长的往返时延而不能很好地适用于DCN 环境下的数据交换，另外矩阵分解类路由指派算法又因分解不完全致使该类算法在某些情况下不能正常工作．因此，本文旨在对Clos 交换网络的经典指派算法的研究基础上，给出适合于DCN 环境下的基于矩阵分解的路由指派算法．

1 基本网络结构及条件假设

在宏观上，Internet 由两类硬件设施组成:通信链路(link)及交换节点(node)．通信链路只负责数据分组的传输，不负责分组的转发;交换节点虽然也执行分组的传输，但其主要功能是负责分组的转发，即根据IP地址在整个IP 网络里转发IP 分组．

为了分组的路由与转发，路由器/交换机主要由三部分构成，即路由软件(routing software)、线卡(line card)和交换结构(switch fabric)，如图1 所示［5］．路由软件即路由算法，它控制IP 分组从交换结构的某个输入端口交换到某个合适的输出端口以避免在交换结构里发生阻塞而丢包．这个过程是与特定的交换结构相关，本文讨论的路由指派算法是针对可扩展性好、网络性能优越的Clos 交换结构．因此本节首先讨论Clos 交换结构的网络模型及条件假设．

基本的Clos 交换网络由输入级、中间级和输出级互连而组成，相应于每级的交换模块可以是一个交换规模较低的Crossbar 结构，分别称为输入级交换模块(input switching module，ISM)，中间级交换模块(center switching module，CSM)及输出级交换模块(output switching module，OSM)，如图2 所示．每个ISM 或OSM 是一个n×m 或m×n 的Crossbar 交换模块，CSM 是一个r×r 的Crossbar 交换模块．通常称这样的基本Clos 交换结构为对称Clos 交换网络，记为C(n，m，r)，其交换容量N = n×r．

图1 交换机/路由器结构略图[5]Fig.1 Architecture of a switch/an IP router

图2 基本Clos 交换网络Fig．2 A Clos switching network

Clos 网络是具有阻塞特性的一种交换网络，其阻塞特性可由参数n，m 和r 完全决定，即当m≥2n -1时，它是严格非阻塞(strickly non -blocking，SNB)［1］;当m≥n 时，它是可重排非阻塞(rearrangeable non -blocking，RNB)［6］．由此可见，一个SNB 的Clos 网络较RNB 的Clos 网络有更大的硬件代价，前者需要更多的CSM，至少是后者的(2n-1)/n 倍，因此RNB 的Clos 网络更有吸引力，当然调度算法相对复杂．本文的研究是针对RNB 的Clos 交换网络，而且假设m=n，但其结果同样适用于m ＞n 的情况．

在Clos 交换网络中，到达输入端口的分组都带有自己的目的地址，通常用如公式⑴的请求置换来表示分组的源端口与目的端口之间的对应关系．

公式(1)反映了Clos 网络的输入端口到输出端口的映射，即输入端口i (1≤i≤N)映射到输出端口oi(1≤oi≤N)，表示到达输入端口i 的分组的目的端口为oi．

2 路由指派算法相关研究

Clos 网络是一种多路由路径的交换网络，在任意输入/输出之间均存在多条路由路径，具体的路径数目由CSM 模块数决定，即每个CSM 模块就是一条路由路径，因此路由路径的选择等价于CSM 模块的选择．目前关于CSM 的典型的选择策略有分布式的轮询仲裁策略(round - robin arbitration)、二分图边着色策略(edge coloring)及矩阵分解策略(matrix decomposition)等．

由此可见，采用方法一与有限元的计算的排水量和剩余水头高度的结果都十分接近，而采用方法二的排水量计算结果远大于方法一和有限元的计算结果。说明采用方法一与有限元进行双排水盲沟渗流计算时，可以得到较为合理的结果，其结果具有一定的参考价值。

2．1 轮询仲裁策略

轮询仲裁匹配策略就是在输入端口与输出端口之间进行反复询问，最终形成一个匹配．具体地，每个输入端口根据自己当前时隙分组的传输需求向相应的输出端口发送传输“请求(request)”信号，每个输出端口以某种方式(如周期轮换)送出“授权(grant)”信号以表示接受此请求，输入端口收到输出端口的授权信号后，再以某种方式(如周期轮换)“授受(accept)”某个授权，最后在输入端口与输出端口之间形成一个匹配．为了实现端口之间的匹配，需要在每个端口处设立一个仲裁器(arbitrator)，用于在多个信号中的选择．这个轮询过程如图3 所示．

图3 一个4×4 交换模块的一个迭代周期Fig.3 An iteration cycle of a 4×4 switching module

从上述简单描述中可以看出，轮询仲裁匹配策略存在以下不足之处:第一是输入/输出端口在每个匹配周期都采用请求—授权—接受(request-grant-accetp，RGA)形式．这不仅会增加交换延迟，而且会产生大量需要维护的仲裁信息．第二，一个匹配周期很难得到输入与输出端口之间最大匹配，可能需要多个匹配周期，甚至永远也得不到最大匹配．如图3 中，一个匹配周期只得到了两个成功匹配，其余两个匹配(4→2 和3→4)只能在下一个匹配周期完成．第三，在Clos 网络的每一级都需要进行这样的轮询迭代，那么后一级的轮询匹配可能会阻塞上一级的部分匹配．图4(a)表示请求置换的路由路径的指派情况，因中间级的阻塞导致输入级的四个成功匹配在这一级匹配失败，这就降低了整个交换系统的吞吐率．因此，迭代类算法不适合DCN 环境下的分组交换．

2．2 二分图边着色策略

二分图的匹配是解决交换结构中端口匹配问题的最直接的数学理论，为了提高交换结构的吞吐率，每个时隙都尽可能得到一个二分图的最大匹配，但相应算法的复杂度较高．目前效率最高的匹配算法的时间复杂度也是O(n5/2)［7］，实用性并不强．在Clos 交换结构中，不仅需要解决端口的匹配，还必须解决交换路径的指派．

根据每个时隙分组的到达情况，应用二分图的边着色理论实现交换路径的指派．先将Clos 交换结构转化为一张二分图Gclos=(Vin，Vout，E)，其中Vin={ISMi| 1≤i≤r}，Vout={OSMj| 1≤j≤r}．如果当前时隙ISMi有到OSMj的请求任务，则边e = ＜ISMi，OSMj＞是E 的一个元素．为二分图Gclos中邻接于同一顶点的不同边着上不同的颜色，这不同颜色代表不同的CSM 交换模块．图5 就是针对图4 的Clos 交换结构的二分图边着色情况，其中用不同的线型表示不同的颜色，同时表示经过不同的CSM 交换模块．从图5 可看出，邻接于同一个顶点的不同形式的边(表示不同的颜色)表示经历不同的CSM 到达各自的目的端口，这样可很好地解决阻塞问题．相应的交换路径指派如图4(b)所示．

图4 中间级产生阻塞导致匹配不完全Fig.4 An incomplete matching caused by blocking in the central stage

基于二分图的边着色原理可以很好地解决Clos 交换网络的交换路径的指派问题，但必须先将Clos 交换结构转化成一张二分图，这不仅增加时间复杂度，而且也增加空间复杂度．这对于交换容量不是很大的交换结构而言并非是明智的选择［8］，因此这类指派算法也不能很好地工作于DCN 中．

3 基于矩阵分解的路由指派算法

图5 边着色指派图Fig.5 An assignment graph based on the edge-coloring

矩阵分解亦是解决路由指派的一种非常重要的方法．这种方法不必将Clos 交换网络转化成二分图，而是直接分解业务矩阵，可降低时间复杂度与空间复杂度．不幸的是，目前已有的矩阵分解算法存在不完全性，即算法在某些情况下不能正常工作．Jajszczyk 算法［9］是一款很优秀的矩阵分解算法，但Cardot［10］却给出一个它不能正确分解的反例导致其正确性遭到质疑．Ramanujam 算法［11］也是通过矩阵分解来解决Clos 结构的路由问题，它不仅通过系列复杂的变换抽取出输入与输出之间的对应关系，而且Kubale［12］证明此算法也是不完全的．Gordon 等人提出的GS 分解算法［13］虽然是一款非常有效的分解算法，但其正确性也遭到了质疑［14］，而且Lee 等人［8］也给出一个此算法不能正确分解的反例．因此，目前已有的基于矩阵分解的路由指派算法不能应用于DCN 中．

本文给出一种基于逐行分解的矩阵分解算法，它可完全解决其它同类算法的不完全性，而且分解效率不低于这些算法．

3．1 基本概念及条件假设

其中，元素tij表示到达第i 个输入交换模块(ISMi)前往第j 个输出交换模块(OSMj)的分组数．在每个时隙到达每个输入交换模块的分组数不能超过其能接收的理论最大值，每个输出交换模块在每个时隙送出的分组数也不能超过其能送出的理论最大值，所以业务矩阵T 中的元素需满足如下条件:

指派矩阵(assignment matrix)Ai(1≤i≤r)指示出所有到达第i 个输入交换模块(ISMi)的分组的路由路径．Ai是一个n×r 的矩阵(akj)n×r，元素akj是一个示性变量，如果第k 个中间交换模块(CSMk)被分配给请求到第j 个输出交换(OSMj)的分组，则akj等于1，否则等于0．分解业务矩阵T 的第i 行得到指派矩阵Ai，分解T 得到的所有指派矩阵组成的集合称为指派矩阵集，记为A．

在部分和矩阵中，含有元素e 的行或列，称为e-行或e-列，并称此元素为e-元．

3．2 矩阵分解算法

为了实现Clos 交换网络的无阻塞路由，中间级交换模块CSM 的分配必须满足以下两个分配目标:①为来自相同ISM 的请求分配不同的CSM;②为拥有相同OSM 的请求分配不同的CSM．任何路由指派算法只要具备这两个分配目标，就一定可以避免路由阻塞．

为了实现上述CSM 的分配目标，本算法分两个阶段实现业务矩阵的分解，第1 阶段为业务矩阵T 的初级分解，第2 阶段为指派矩阵集A 的调整．

● T 的分解:对T 的第i(1≤i≤r)行(ti1，ti2，…，tir)中每个元素tij(1≤j≤r)执行如下两步:

(1)如果tij≥1，则(0，0，…，1，…，0)作为Ai的一行加入其中;

(2)tij= tij-1，执行⑴．

● A 的调整:初始时，ps(1)= A1，然后重复执行如下步骤r-1 次(2≤i≤r)，直至ps(r)的所示元素均为1．

(1)查找ps(i)中的2 -行，用s 表示，则s 对应于Ai的一个调整行，如果ps(i)中没有2 -元，则执行⑷;

(2)查找ps(i)中2 -列的0 -行，用t 表示，则t 对应于Ai的一个目标行;

(3)交换Ai的调整行与目标行，消除ps(i)中的一个2 -元;

(4)ps(i+1)= ps(i)+Ai+1，执行(1)．

3．3 算法的性能分析

矩阵分解算法分2 个阶段，即业务矩阵的分解阶段和指派矩阵集的调整阶段．在分解阶段，每行的分解操作至多执行n 次，而业务矩阵有r 行，所以总的计算时间为O (nr)．调整阶段的时间效率涉及3 个因素，首先是部分和的计算，这是典型的两个矩阵的求和运算，其复杂度为O (nr)，但需要计算r 次，所以总复杂度为O (nr2)．其次，部分和矩阵中2 -元和0 -元的查找，此操作需要遍历整个部分和矩阵，其时间复杂度为O(nr)，共有r - 1 个部分和矩阵需要检查，所以总时间代价亦为O (nr2)．最后，调整行与目标行的交换．由分解阶段的分解算法决定了在任何时候部分和矩阵里至多有n 个2 -元，这说明指派矩阵在最坏情况下需要调整n-1 次，即整个过程需要调整的次数为O (nr)．综合上述分析，此算法的时间复杂度为O(nr2)．与其它同类算法的计算时间复杂度比较如表1，从中可以看出本文提出的分解算法(表1 的最后一行)的时间复杂度不高于其它同类算法．

表1 算法的时间复杂度比较Tab．1 Comparisons of time complexity of decomposition algorithms

4 结 论

Clos 交换网络在构建高速大容量交换系统时具有单级结构无法比拟的成本和可扩展优势，而且随着DCNs 的广泛应用，对交换节点提出更为严格的需求．而目前相应的路由指派算法不能很好地满足如此严格的性能需求，不是延迟较大，就是过于复杂或矩阵分解不完全等．本文提出的基于矩阵分解的路由指派算法，采用与其它同类算法不一样的逐行分解策略，能以串行时间O (nr2)正确分解满足条件⑶的任意请求矩阵，有效解决以前分解算法的不完全性，并且不会在调度器与线卡之间产生较大的往返时间(RTT)，简单易实现于Clos 交换网络的路由指派．

另外，分解算法的分解步骤之间的数据依赖较弱，非常容易并行化，可在线性时间复杂度O(nr)内完成业务矩阵的分解，较其它算法更适用于DCN 中的分组交换．

［1］ CLOS C． A Study of Non-blocking Switching Networks［J］，Bell Systems Technical Journal，1953，32(2):406 -424．

［2］ LIU Y，MUPPALA J K，VEERARAGHAVAN M，et al． Data Center Networks -topologies，Architectures and Fault-tolerance Characteristics［M］． New York:Springer，2013:1 -5．

［3］ AL-FARES M，LOUKISSAS A，VAHDAT A． A Scalable，Commodity Data Center Network Architecture［C］//Proc． of the ACM SIGCOMM，Seattle，USA，2008:63 -74．

［4］ GREENBEG A，HAMILTON J R，JAIN N，et al． VL2:A Scalable and FlexibleData Center Network［J］． Communications of The ACM，2011，54(3):95 -104．

［5］ CHANG C S，LEE D S． Principles，Architectures and Mathematical Theory of High Performance Packet Switches［M］． National Tsinghua University Press，Taiwan，2008:3 -4．

［6］ BENEš V E． On rearrangeable three-stage Connecting Networking［J］． Bell Systems Technical Journal，1962，41(5):1481 -1492．

［7］ HOOPCROFT J E，KARP R M． An n5/2Algorithm for Maximum Matching in Bipartite Graph［J］．SIAM Journal on Computing，1973，2(4):225 -231．

［8］ LEE H Y，HWANG F K，CARPINELI J D． A New Decomposition Algorithms for Rearrangeable Clos Interconnection Networks［J］． IEEE Transactions on Communications，1996，44(11):1572 -1578．

［9］ JAJSZCZYK A． A Simple Algorithm for the Control of Rearrangeable Switching Network［J］． IEEE Transactions on Communications，1985，COM-33(2):169 -171．

［10］ CARDOT C． Comments on“A Simple Algorithm for the Control of Rearrangeable Switching Networks”［J］． IEEE Transactions on Communications，1986，COM-34(4):395．

［11］ RAMANUJAM H R． Decomposition of Permutation Networks［J］． IEEE Transactions on Computers，1973，C-22(7):639 -643．

［12］ KUBALE M． Comments on“Decomposition of Permutation Networks”［J］． IEEE Transactions on Computers，1982，C -31(3):256．

［13］ GORDON J，SRIKANTHAN S． Novel Algorithm for Clos-type Networks［J］． Electronics Letters，1990，26(21):1772 -1774．

［14］ CHIU Y K，SIU W C． Comment“Novel algorithm for Clos-type Networks”［J］． Electronics Letters，1991，27(6):524 -526．［15］ TSAO-WU N T． On neiman's Algorithm for the Control of Rearrangeable Switchicng Networks［J］． IEEE Transactions on Communications，1974，COM-22(6):737 -742．

［16］ HWANG F K． A modification to a Decomposition Algorithm of Gordon and Srikanthan［J］． IEEE Transactions on Computers，1997，46(8):958 -960．