Open Access Open Access  Restricted Access Subscription Access

A Parallel Matrix Decomposition Algorithm for Routing on Rearrangeable Clos-Network Switches

Xiaofeng Liu,
Youjian Zhao,

Abstract


Matrix decomposition is an important routing approach in a rearrangeable three-stage Clos network. However, most existing routing algorithms based on matrix decomposition were proved to be incomplete. In this paper, a new and efficient decomposition algorithm is proposed to route for rearrangeable Clos-network switches. The proposed algorithm uses a row-wise decomposition manner, which is a totally different decomposition method from the existing ones, to decompose a connection matrix for implementing the switching of all requests. Consequently, the algorithm can effectively overcome the incompleteness of similar algorithms and is capable of decomposing any connection matrices in serial time O(nr^2) or parallel time O(nr). Moreover, we prove the correctness of the proposed algorithm by rigorous mathematical proofs and analyse its time complexity in detail.

Keywords


Matrix decomposition; Clos-network; Routing algorithm; Rearrangeable non-blocking

Citation Format:
Xiaofeng Liu, Youjian Zhao, "A Parallel Matrix Decomposition Algorithm for Routing on Rearrangeable Clos-Network Switches," Journal of Internet Technology, vol. 18, no. 2 , pp. 229-236, Mar. 2017.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.





Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Library and Information Center, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd. Shoufeng, Hualien 97401, Taiwan, R.O.C.
Tel: +886-3-931-7017  E-mail: jit.editorial@gmail.com