Routing in asymmetrical multiconnection three‐stage Clos networks

Journal Article


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(mf3) to O(f4) 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(f4) 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 O(mK2) to O(m(f2 + K log K)), 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. © 1998 John Wiley & Sons, Inc. Networks 32: 77–83, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.