Routing in asymmetrical multiconnection three-stage Clos networks

✍ Scribed by Tham, Yiu Kwok

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 84 KB
• Volume: 32
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199809)32:2<77::aid-net1>3.0.co;2-f

✦ Synopsis

The asymmetrical multiconnection three-stage rearrangeable Clos network is considered, where, in general, many-to-many connections are allowed between input and output terminals. The problem of routing the connections over the switches is efficiently solved. The computational complexity is improved from O(mf 3 ) to O( f 4 ) using a network flow model for the routing problem, where f is the number of first-stage switches and m is the number of second-stage switches; the number of third-stage switches is assumed to be of the same order as f. Note that the O( f 4 ) complexity is independent of the number of second-stage switches. Using an appropriate data structure, the computational complexity of an edge-coloring approach to the routing problem is lowered from

where K is the aggregate capacity of the interconnecting links between all first-stage switches and a second-stage switch; the aggregate capacity of the interconnecting links between a second-stage switch and all third-stage switches is assumed to be of the same order as K. This makes the edge-coloring approach competitive for small values of m and K.