Routing method for fast packet switching systems

Claim 2

A routing method for an interconnection network of a fast packet switching system, in which the interconnection network comprises a number of consecutive stages such that a number of alternative connection paths between any input and any output of the inter­connection network is available and the interconnection network is associated with a distributed control structure composed of a plur­ality of processing units which manage the routing at the virtual call level, characterized in that at least some of said processing units, associated each with a group of network inputs/outputs, store bandwidth occupancy data of interstage links which can be reached from the inputs of said group and are included between said inputs and a stage where there is a maximum number of alternative paths or respectively bandwidth occupancy data of the interstage links leading to the outputs of said group and included between said stage and the outputs of said group, said data being updated whenever a new call is routed, and in that, when a virtual call is to be routed, the processing units associated with the input or respectively the output involved in the connection evaluate each, on the basis of the updated condition of bandwidth occupancy and of the bandwidth requirements of the new call, a cost function of the connection along the portion of each possible routing path included between the input and the stage where there is the maximum number of alternative paths or respectively for the portion of each routing path included between such stage and the output, the results of the evaluations carried out by said units being combined together in one of said units, which determines a global cost function of the individual connection paths and forwards the calls on the path which presents the minimum cost function.

Claim 3

A method according to claim 1, characterized in that the sum of the inverses of the bandwidth available on each interstage link is calculated as cost function to determine the delay introduced by each routing path, and the call is routed along the path which presents the minimum delay.

Claim 4

A method as claimed in claim 1, characterized in that the sum of the bandwidths available on each interstage link is calculated as cost function and the call is routed on the path which minimizes the residual bandwidth availability.

Claim 5

A fast packet switching communications system, comprising a plurality of switching nodes each comprising an interconnection network composed of switching elements (SE) organized into such a number of stages that a number of alternative paths between each input and each output is available, and a distributed control structure (CD) comprising a plurality of processing units (UC1-1...UC3-16) which manage the routing at the virtual call level, characterized in that at least a group of said processing units (UC1-16, UC3-16), associated each with a group of network inputs/outputs, are apt to memorize and to update at each new routed call, bandwidth occupancy data of interstage links which can be reached from the inputs of the respective group and are included between such inputs and a stage where there is a maximum number of alternative paths, and respectively of the links leading to the outputs of the respective group and included between such stage and the outputs, and in that, when a virtual call is to be routed, the processing units associated respectively with the input and output involved in the call comprise means for evaluating, on the basis of the updated bandwidth occupancy condition and of the bandwidth requirements of the new call, a partial cost function of the connection for the part of each of the possible routing paths included between the input and the stage where there is the maximum number of alternative paths or respectively for the part of each routing path included between such stage and the output, one of said units (UC1-16, UC3-16) receiving from the other unit the partial cost function, combining it with the partial cost function calculated by itself, in order to evaluate a global cost function of the connection, and routing the call on the path presenting the minimum cost function.

Claim 6

A fast packet switching communications system, comprising a plurality of switching nodes each comprising an interconnection network composed of switching elements (SE) organized into such a number of stages that a number of alternative paths between each input and each output is available, and a distributed control structure (CD) comprising a plurality of processing units (UC1-1...UC3-16) which manage the routing at the virtual call level, characterized in that at least a group of said processing units (UC1-16, UC3-16), associated each with a group of network inputs/outputs, are apt to memorize and to update at each new routed call, bandwidth occupancy data of interstage links which can be reached from the inputs of the respective group and are included between such inputs and a stage where there is a maximum number of alternative paths, and respectively of the links leading to the outputs of the respective group and included between such stage and the outputs, and in that, when a virtual call is to be routed, the processing units associated respectively with the input and output involved in the call comprise means for evaluating, on the basis of the updated bandwidth occupancy condition and of the bandwidth requirements of the new call, a partial cost function of the connection for the part of each of the possible routing paths included between the input and the stage where there is the maximum number of alternative paths or respectively for the part of each routing path included between such stage and the output, one of said units (UC1-16, UC3-16) receiving from the other unit the partial cost function, combining it with the partial cost function calculated by itself, in order to evaluate a global cost function of the connection, and routing the call on the path presenting the minimum cost function.

Claim 7

A system as claimed in claim 4, wherein the interconnection network is divided into a number of input/output partitions (PE1...PU8), characterized in that for each partition (PE1...PU8) a processing unit (UC1-16, UC3-16) is provided, which stores said bandwidth occupancy data and evaluates said partial cost function at least for the interstage links included in the respective partition.

Claim 8

A system as claimed in claim 5, characterized in that the processing unit (UC1-16) associated with an input partition (PE) evaluates the partial cost function up to a first stage of the output partition (PU) and receives from the processing unit associated with the latter the partial cost functions relevant to the connection portions included in the output partition.