Applications of matching and edge-coloring algorithms to routing in clos networks

Rearrangeable Clos networks have been studied in the literature in connection with telephone switching and communication networks. This paper examines the applicability of matching and edge‐coloring in bipartite graphs to the rearrangement problem in these networks. A survey of various matching and...

Full description

Saved in:
Bibliographic Details
Published in:Networks 1994-09, Vol.24 (6), p.319-326
Main Authors: Carpinelli, John D., Oruc, A. Yavuz
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Teletraffic
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:Rearrangeable Clos networks have been studied in the literature in connection with telephone switching and communication networks. This paper examines the applicability of matching and edge‐coloring in bipartite graphs to the rearrangement problem in these networks. A survey of various matching and edge‐coloring algorithms is given, and these algorithms are evaluated for their suitability and effectiveness. It is shown that no single matching or edge‐coloring algorithm reported in the literature performs well over all Clos networks. It is further shown that the time complexity of the looping algorithm for Beneš networks is at least as good as any routing algorithm that can be obtained from matching or edge‐coloring. © 1994 by John Wiley & Sons, Inc.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.3230240603