A Parallel Route Assignment Algorithm for Fault-Tolerant Clos Networks in OTN Switches

The three-stage fault-tolerant Clos network, where extra switch modules exist in the middle stage in case of switch failures, is widely used in the design of OTN switches. This paper proposes a route assignment algorithm for such Clos networks by solving its counterpart in edge-coloring problem. Bas...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2019-05, Vol.30 (5), p.977-989
Main Authors: Wang, Lingkang, Ye, Tong, Lee, Tony T.
Format: Article
Language:English
Subjects:
Algorithms
Clos network
Color
Coloring
complex coloring
Complexity
Computer simulation
edge coloring
Fault tolerance
Fault tolerant systems
Modules
Optical switches
optical switching
Route assignment
Routing
Run time (computers)
Switches
Switching theory
Time complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The three-stage fault-tolerant Clos network, where extra switch modules exist in the middle stage in case of switch failures, is widely used in the design of OTN switches. This paper proposes a route assignment algorithm for such Clos networks by solving its counterpart in edge-coloring problem. Based on complex coloring, a novel edge coloring method, the proposed algorithm possesses two properties. First, our algorithm can make full use of extra switch modules in the middle stage of Clos network. The extra switch modules provide additional colors for edge coloring, which help to reduce the running time of the coloring process remarkably. Second, our algorithm can be implemented in a parallel manner to further shorten the running time. The proposed routing algorithm achieves a low complexity of O(\frac{\sqrt{N}(m-1)}{m-1+(m-\sqrt{N}){\log }N}{\log }N)O(N(m-1)m-1+(m-N)logNlogN), where NN is the network size and mm is the number of switch modules in the middle stage. The performance of our algorithm has been verified by extensive simulation experiments.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2018.2880782