一种基于Clos交换结构的路由算法

杨 琦

(中国电子科技集团公司第二十研究所，陕西 西安 710068)



一种基于Clos交换结构的路由算法

杨 琦

(中国电子科技集团公司第二十研究所，陕西 西安 710068)

随着互联网业务数据的爆炸性增长，网络中的关键节点——交换机的“电子瓶颈”问题成为限制网络吞吐能力的重要原因。设计了一种适用于Clos交换结构的平面间路由算法，按照业务传输路径的特性和业务之间的位置关系，为业务快速选择最合适的传输路径。仿真表明，该算法在减少业务阻塞率、降低时延方面表现出色，有效改善了交换设备的路由性能。

Clos结构；电子瓶颈；业务路径

0 引 言

Clos网络结构于1953年由贝尔实验室的Charles Clos提出[1]。它是由多个较小容量的交换单元构建而成的大容量交叉矩阵，具有良好的可扩展性[2-3]、灵活性、可靠性，可以适应网络规模的快速增长，满足网络传输业务的多样化、综合化，能够适应不同传输设备的要求。这些特性使得Clos网络结构成为目前热门的多级交换结构。

路由算法主要实现业务传输路径的快速分配，提高业务吞吐率，在很大程度上决定了交换设备的性能。本文从Clos结构和业务特性出发提出一种路由算法，在快速下发业务的同时也降低了时延和阻塞率。

1 问题建模

1.1 Clos交换结构业务特性

以一个简单的3级Clos结构为例(如图1所示)，第1级结构是由r个n×m交换单元组成；第2级结构由m个r×r交换单元组成；第3级结构由r个m×n交换单元组成。每个中间级单元与每个输入和输出单元只有一条链路连接，而从输入级任一端口到达输出级任一端口可供选择的链路有m条。3级Clos交换结构的总端口数等于输入模块的端口个数n，乘以输出模块的个数r。输入级模块的输出端口共有m个，因此每个输入级模块都有m条链路可供选择。

在工程应用中，当业务从输入端口到来后，交换设备需要通过路由算法得到每条业务的下发路径，也就是业务要被分配到的中间级模块。

为实现输入端的业务分发到每个平面，采用提前一次统计出到达每个输入端口业务之后，进行分平面路径设置。因为输入/输出对的业务个数是随机数，所以用1个业务矩阵统计输入/输出对的业务个数。为了描述交换结构的业务特性，这里采用业务矩阵的方式，业务矩阵的行代表输入端口，列代表输出端口，业务矩阵的具体取值代表了从某行(输入端口)到某列(输出端口)的业务数量,图2是一个N×N规模的业务矩阵。

矩阵中第0行第2列的“7”代表从0号输入端口到2号输出端口有7条业务需要下发。对基于Clos交换结构的设备，业务路由要解决的就是将业务下发到合适的中间级，虽然每个中间级模块理论上都可以承载业务到对应的输出端口，但每个中间级模块的业务容量上限固定。当大量业务都需要转发的时候，就要尽可能让每条业务选择合适的中间级模块将所有业务最大化下发出去。

传统路由算法根据业务矩阵的规模，逐行逐列进行业务查找，在业务矩阵中找到业务后，只需判断下发到的业务平面中该位置的行、列已有业务是否达到上限。若达到上限，寻找下一个业务平面；若还未达到上限，则插入业务，完成操作。如图3所示。

但这种方法轮询的时候只考虑当前位置业务能否下发，没有考虑对之后该位置同一行、同一列位置处的业务下发是否造成影响。

1.2 加速路由算法

在传统路由算法基础上，提出一种加速路由算法，图4是该算法的业务矩阵轮询示意图。

步骤2：从i=SR，j=SL开始轮询。判断业务矩阵是否还有业务未分配；是否存在还未分配业务的平面。

(1) 若m为0，则不存在未分配业务的平面，则提取所有连接矩阵作为平面的路由设置依据，程序结束。

(2) 若存在未分配业务的平面，但是业务矩阵Hm[i,j]中元素全为零，则提取已分配的连接矩阵作为平面的路由设置依据，程序结束。

(2) 若选取的列上元素为零或者该列计数器值已超过了上限值，则重复步骤3轮询行i的下一列j=(j+1)mod(N)。

(2) 选取的列上元素为零或者该列计数器值已超过了上限值，则重复步骤4，轮询行i的下一列j1=(j1-1)mod(N)。

步骤5：判断轮询的行i是否等于起始行SR，若等于起始行，则m=m-1，SR=(i+1)mod(N)、SL=(j+1)mod(N)，SL1=(j1-1)mod(N),并回到步骤2；若不等于起始行，则回到步骤3，轮询下一行i，列j=(j+1)mod(N)。

1.3 仿真验证

下面通过VS2010软件，对设计算法的业务处理时延、阻塞率进行验证。假设业务矩阵的规模是512×512，每个输入输出端口到达的业务数最多3 000个，业务平面有100个。每个平面来自每个端口的业务数上限值为30个。

图5是业务负载率从10%～100%多种情形下，2种算法在处理时延方面的对比图。

从图中可看出，当业务负载量小于60%，加速路由算法的处理时延优化效果不明显，主要是因为业务矩阵中的业务较稀疏。加速路由算法在轮询过程中花费在查找的时间不能减少，只是在双向找到有效业务的情况下，处理时间能减少，所以不能够达到业务处理时延减半的效果。

随着业务负载量的增加，加速路由算法在处理大量业务时显示出较好的效果，同时时延曲线的变化不会随着业务负载量的增大有明显的变化。主要是因为这种算法在查找业务时避免输出模块端口计数器过早达到上限，计算业务的时候也加快处理速度。而传统路由算法由于查找业务的方法较单一，在下发前面端口业务的同时没有考虑到对后面端口业务的影响，导致在查找上所花的时间较多，时延随业务负载量的增加曲线变化很明显。

图6是业务负载率从85%～100%多种情形下，2种算法在阻塞率方面的对比图。

在仿真过程中发现，当业务负载率小于80%，下发业务所需的平面个数维持在91～97之间，不存在阻塞率。因此我们截取业务负载率85%～100%

这些情形进行阻塞率对比。

当业务负载率超过85%，加速路由算法逐渐显示出较好的的阻塞率表现，尤其是当业务负载率超过92%以后，2种算法的阻塞率差距逐渐拉大，主要是因为加速路由算法在前期查找合适位置的时候尽量避免计数器过早达到上限，不给后面平面下发业务造成限制,如图7所示。

按照传统路由算法，每行轮询的时候都选择第2列的业务，到第i-1行，该列计数器达到上限，到第i行，该位置的业务也不能够再下发出去，造成业务阻塞。

2 结束语

本文针对Clos交换结构的特性，设计了一种适用于大量业务的快速路由算法，通过计算机软件验证了算法在降低时延、阻塞率方面表现出的良好性能。下一步将考虑在提高业务处理速度等方面改善算法的性能。

[1] 陈浩.Clos网络的绿色交换[D].西安：西安电子科技大学，2014.

[2] 熊庆旭，冯金鑫.基于矩阵分解的光交换机分组调度算法[J].通信学报，2006,27(4)：80-86.

[3] 李挥，王秉睿，黄佳庆.负载均衡自路由交换结构[J].通信学报，2009,30(5)：7-15

A Routing Algorithm Based on Clos Switching Structure

YANG Qi

(The 20 Institute of China Electronic Technology Group Corporation,Xi'an 710068，China)

With the explosive growth of Internet business data,"electronic bottleneck" problem of switcher——the key node of network becomes the significant cause limiting network throughput.This paper designs a routing algorithm among planes for Clos switching structure,which rapidly chooses the most suitable transmission path for the business according to the characteristics of the transmission path and the location relationship between services.The simulation results show that:the proposed algorithm performs well in reducing the traffic blocking rate and reducing the time delay,so effectively improves the routing performance of switching devices.

Clos structure;electronic bottleneck;transmission path

2017-02-26

TP393.04

A

CN32-1413(2017)02-0089-03

10.16426/j.cnki.jcdzdk.2017.02.021