Browse Prior Art Database

Distributed Control of Clos Networks

IP.com Disclosure Number: IPCOM000105253D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 91K

Publishing Venue

IBM

Related People

Franaszek, PA: AUTHOR [+2]

Abstract

Disclosed is a method for providing fast, distributed control to Clos-type interconnection networks. This method allows Clos networks[*] to be used in packet switching applications that require fast connection set up times.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Distributed Control of Clos Networks

      Disclosed is a method for providing fast, distributed control
to Clos-type interconnection networks.  This method allows Clos
networks[*] to be used in packet switching applications that require
fast connection set up times.

      Clos networks have been used to provide non-blocking
interconnections in large systems since their hardware complexity is
only of the order of N sup 3/2  (for a 3-stage network), while the
complexity of regular crossbars is of the order of N sup 2  (where N
is the number of input/output network ports).  In its general form,
the first stage of a Clos network consists of &sqrt.N switches of
size n x (2n-1), the intermediate stage consists of 2n-1 switches of
size n x n  and the third stage of &sqrt.N switches of size (2n-1) x
n.  For example, if N=1024, there are 32 first-stage switches of size
32 x 63, 63 intermediate-stage switches of size 32 x 32 and 32
third-stage switches of size 63 x 32.  A connection between an input
and output is established by connecting the first- and third-stage
switches via an available intermediate-stage switch.

      A disadvantage of prior-art Clos networks is that connection
set up is time consuming, as it requires a global knowledge of the
connection state of all paths in the network.  The global status is
typically kept in a centralized controller that performs the
connection set-up in a serial fashion, thus producing queueing
delays.  As a result, prior-art Clos networks have been used
primarily for circuit switching applications, where paths in the
network are established infrequently.

      In the disclosed method, each switching element of the 3-stage
Clos network has its own controller.  Furhermore, all controllers of
the first and third stages are interconnected via a separate control
network, as shown in Fig. 1.  When a packet requesting connection to
a destination port is received at a switch element, the controller
must decide on which intermediate stage element to make the
connection.  To do s...