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

A Route Dispatching Algorithm Based on Matrix Decomposition for Clos-Network Switches

Clos交换网络以其低成本优势和良好的可扩展性成为高速大容量交换系统的主流交换结构;另外,随着数据中心网络(data center network,DCN)诞生与发展,交换节点(路由器/交换机)面临更苛刻的性能需求,但相应的指派算法因各种原因无法很好地服务于数据中心环境下的路由与交换.矩阵分解是解决Clos网络的路由指派的重要途径,但目前已有的大多数分解算法被证明为不完全.因此,基于矩阵分解提出一款针对可重排无阻塞Clos网络的非常有效的路由指派算法.该算法采用逐行分解策略,不仅能有效解决同类算法的不完全性,亦能在串行时间O(nr2)内正确地分解任意的业务矩阵,而且避免在调度器与线卡之间产生较长的往返时间,简单易实现于Clos交换网络.

Clos-network switches are considered as the mainstream switching architecture of high-speed large-capac- ity switches due to their low cost and good scalability. Moreover, with the arising and development of data center networks （DCN） ,switching nodes including routers and switches are confronted with rigorous performance requir- ment, but most corresponding dispatching algorithms are somewhat powerless for various reasons so that they cannot well serve the switching of DCNs. Matrix decomposition is an important method to solve the route assignment prob- lem of Clos-network switches, but most existing decomposition algorithms are proved to be incomplete. Therefore, a new and efficient dispatching algorithm based on matrix decomposition idea is proposed to routing for rearrangeable Clos-network switches in this paper. The proposed algorithm uses a row-wise decomposition manner, which is a to- tally different decomposition method from the existing algortihms, to decompose a traffic matrix for implementing the routing of all requests. Not only can the algorithm effectively solve similar algorithms＇ incompleteness and success- fully deocmpose any traffic matrices in serial time O （ nr^2） , but also it is simple and practical for Clos-network swit- ches and can avoid large round trip times （RTTs） between the scheduler and line cards.