Distributed semi-rearrangeable non-blocking algorithm for clos networks

#1. Field of the Invention

#The invention relates to telecommunications networking. More particularly, the invention relates to an algorithm for selecting middle stage switch elements when setting up a connection in a Clos network.

#2. State of the Art

#FIG. 1 is a simplified diagram of a prior art Clos network;

#FIG. 2 is a simplified diagram of a preferred n=m=r Clos network for use with the marching algorithm of the invention;

#FIG. 3 is a flowchart illustrating one embodiment of the methods of the invention;

#The algorithm of the present invention is preferably implemented in a Clos network having an equal number of switch elements at each stage. For example, FIG. 2 illustrates a suitable three stage Clos network where n=m=r. According to the invention, the algorithm is suitable for switching TDM traffic from an input switch element to one or more middle stage switch elements to one or more output stage switch elements. FIG. 2 illustrates a TDM signal with R number of time slots being routed from the first input stage switch element to the first output stage switch element via the first middle stage switch element.

#According to a first embodiment of the invention, suitable for single rate connections, upon a connection request, a marching algorithm is used to select the middle stage switch element which will be used to complete the connection. The marching algorithm maintains a sequence of middle stage switch element identifiers referred to as the “marching sequence”. This sequence, while arbitrary, is the same for all the input switch elements. Using Ohta's notation, an example of a suitable marching sequence is {K1, K2, . . . , Kr}, i.e. the middle stage switch elements from top to bottom in order. Using the marching sequence, the marching algorithm operates as follows:

#Referring now to FIG. 3, on a connection request (I, J) at 100, the middle stage switch element K is selected by an input stage switch element following the marching sequence in the forward direction at 102, i.e. the “forward marching sequence”, until a free timeslot for the connection to the destination switch element is found and the connection is made at 104.