Routing method for fast packet switching systems

The invention relates to high-speed packet switching telecommunications systems, and more particularly relates to a routing method for a switching network in such a system and the system using the method.

Fast packet switching (also known as label packet switching or asynchronous time division switching) is a technique that has recently been proposed for switching voice, data and video signals. According to this technique, information blocks to which a label characterizing the information is assigned and which arrive asynchronously at the switching devices are switched through exclusively on the basis of the content of this label. Because of the simplicity of the protocol, this technique offers significant improvements in operational performance in terms of information processing speed and flexibility compared to conventional packet switching.

A switching system for a system using this technique generally comprises a switching network which is composed of a plurality of identical elements which are combined to a certain number of successive stages, and a controller, referred to as a control structure. Depending on the network size, the needs of the participants and / or the system administrator, the traffic characteristics, etc. Different traffic distribution modalities as well as different designs of the switching network and the control structure are possible.

In detail:

- The traffic can be distributed at the packet level (ie each packet follows its individual route independently of the other packets relating to the same connection) or at the virtual call level: in this case, each virtual call is allocated a route through the network and thus all packets relating to this call follow the same route;

the switching network can provide a single path or a plurality of alternative paths between an input and an output;

- The controller can either be a centralized controller, in which a single unit controls all the input / output lines of the node and has all the information available which is necessary for the routing of the packets; or can be a distributed control: in this case there are a large number of control units, each of which manages the traffic involved in a certain group of input / output lines.

The present invention is applicable to distributed control networks in which a variety of routes are available between an entrance and an exit and the traffic is distributed in the virtual call plane. In a network of this type, the problem arises for each call to be switched through that is to choose the best connection path between the input and the output, that is to say the path that optimizes certain given parameters.

Special reference is often made to the optimization of a "cost function" of the connection: the expression "cost function" means a parameter which relates to the bandwidth allocation on the connection. This parameter can be defined in various ways, inter alia depending on the characteristics of the coupling elements forming the network.

A solution to this problem is described by M. De Prycker and M. De Somer in the article "Performance of a Service Independent Switching Network with Distributed Control", IEEE Journal on Selected Areas in Communications, Volume SAC-5, No. 8, October 1987th In this method, which is applicable to a network in which an output can be reached from an input via any central stage, a control packet is sent into the network in order to find a connection path between the desired input and output, this path being a can guarantee acceptable operational quality. This path is searched step by step by using a local control function for the load of the step output involved in each step: namely, the load (as a percentage of the occupied bandwidth compared to the available bandwidth) due to the connection currently using this output is stored in each coupling element and it is checked whether the additional load due to the new communication is acceptable by not becoming one too high a probability of queue overflow. When the control packet reaches the network exit, the route found in this way is then used to route all packets of the same virtual connection.

This known method has the disadvantage that, due to the large number of alternative ways of finding a route between an input and an output, within a reasonable time without using extremely complex evaluation algorithms, the route between adjacent stages is optimized, but there is no global network vision so that the path ultimately found is not necessarily the one which optimizes the global "cost function" of the new connection.

In contrast, the invention provides a method in which a global cost function is evaluated without placing an excessive processing burden on the control devices: in this way, the path found is actually the optimal path between the network input and the network output.

The method given by the invention of routing through a switching network of a fast packet switching system, in which the switching network is assigned a decentralized control structure which is composed of a multiplicity of processing units which handle the route search in the level of the virtual call, is characterized in that at least some of these processing units, which are each assigned to a group of inputs / outputs of the switching network, bandwidth occupancy data of intermediate stage connections which can be reached from the inputs of the group and are included between the inputs and a stage at which there is a maximum number of alternative routes, or store the bandwidth occupancy data of the interstage links leading to the group's outlets and trapped between that stage and the group's outlets, which data is updated each time a new call is put through; and that if a virtual call is to be put through, the entrance or processing units associated with the output that is involved in the connection, based on the updated state of bandwidth usage and the bandwidth requirements of the new call, a cost function of the connection for the portion of each possible connection path included between the input and the stage in which there is the maximum number of alternative routes, or for the part of each route that is switched on between this stage and the output, the results of the evaluations carried out by these units being combined with one another in one of these units, which determines a global cost function of the individual connection routes and routes the calls to that route that has the minimum cost function.

The invention also provides a system for fast packet switching communication, which is characterized in that at least some processing units, each associated with a group of inputs / outputs of the switching network, with each new routed call, bandwidth occupancy data relating to interstage connections, from the inputs of this group can be reached from and between these inputs and a level, in which there is a maximum of alternative routes included, or bandwidth occupancy data relating to the connections which lead to the outputs of this group and which are included between this stage and the outputs, can be stored and updated; and that if a virtual call is to be put through, the input or connection involved in the connection Processing units associated with output contain evaluation devices which, based on the updated bandwidth occupancy status and the bandwidth requirements of the new call, evaluate a connection cost function for the part of each possible route which is switched between the input and a stage in which there is the maximum of alternative routes, respectively. for the part of each route that is switched between this stage and the output; one of these units receiving from the other unit the results of the evaluations carried out, combining them with its own results to evaluate a global cost function of the connection, and placing the call on the path that has the minimum cost function.

The routing method according to the invention and the communication system to which it is used offer additional advantages in addition to the advantage that results from the selection of the optimal route based on a global network vision. In particular, processing times are reduced in that the processing units that evaluate the cost function only have to control a part of the connections. In addition, distributing the link bandwidth occupancy memory among a plurality of processing units enables routing operations between inputs / outputs belonging to different groups to be performed simultaneously, which further improves network handling behavior.

For a better understanding, reference is made to the accompanying drawing which shows a fast packet switching switching network applying the invention.

The figure shows an example of a switching network with 64 inputs and 64 outputs, which is composed of 2 × 2 switching elements SE, which are arranged in eight stages. The structure of the coupling elements can be one as described by C. Demichelis, G. Giandonato, S. Giorcelli and R. Melen in the article "Fast packet switchng technique in first generation ISDN", CSELT Technical Reports, Volume XV, No. 4 , June 1987. The network described here has two additional tiers (namely two tiers more than the minimum number necessary to enable a connection between any input and any output) and offers the availability of four alternative routes between a given input and one given output. In addition, the network inputs / outputs are divided into four input departments PE1 ... PE4 and four output departments PU1 ... PU4 groups, each comprising 16 inputs or outputs and containing the elements SE, which form the first four and the last four stages of the network. The elements SE are schematic only for one of the input departments, e.g. B. PE1, and only for one of the output departments, e.g. B. PU3 shown. The connections between the different elements are only shown in PE1 and partly in PU3.

At the network periphery there is a distributed control structure CD with the usual tasks of processing the packets received at the node so that they are passed through the switching network and passed on to the subsequent node. The circuit CD consists, for example, of units whose structure and function corresponds to the structures and functions described in the above-mentioned article. Some units of the control circuit which are connected to inputs of departments PE1 or to outputs of departments PU3 are shown individually. These units are labeled UC1-1 ... UC1-7 ... UC1-16, and UC3-1 ... UC3-7 ... UC3-16. It should be pointed out that, although the control circuit is shown as being divided into two parts, are connected to the outputs of the switching network, a single unit such as UC controls an input and an output of the network, as is clearly shown in Fig. 2 of the above-mentioned article.

A group of the units UC should also search for the optimal routes according to the modalities required by the invention. To this end, they must store the bandwidth occupancy of the connections between the levels that can be occupied by calls involving the entry / exit controlled by these units and are intended to provide a global "cost function" based on the occupancy and bandwidth requirements of the new call "evaluate the connection between the input and the output according to any of the possible alternative routes available on the network. Communication is directed towards the path that minimizes the selected cost function.

The cost function can be evaluated with the aid of the connector assignment or with the help of packet delays etc. The choice of the cost function generally depends on the network structure and the coupling elements that make up the network. Different cost functions can lead to different route selections. The function to be evaluated for a specific network is specified.

The units for this group carry out the tasks mentioned for the partial route that lies within the department to which they are assigned, or generally for the partial route that lies between the entrance and the level at which there is the maximum number of alternative routes, or between this stage and the mains outlet. Since the maximum number of alternative routes is found in accordance with the or a central network stage, there is a good distribution of the load between the two control units involved (provided, of course, that the input and the output are not controlled by the same unit).

The number of units UC that are capable of performing these functions naturally depends on the size of the switching network. In the example shown in the figure, the functions required by the invention are carried out by one of the units per department, this unit being connected to all the inputs / outputs of the department itself. For example, in the drawing the units entrusted with the functions required by the invention are the units UC1-16, UC3-16 and the corresponding units (not shown) of the other departments. To carry out these functions, the units only need a table of the bandwidth occupancy data and an arithmetic unit which can carry out the usual mathematical operations and can recognize the minimum in a certain group of values. For this purpose, the memories and the computing unit of the usual microprocessors, by means of which the usual distributed control units are implemented, can be used.

To better illustrate the invention, consider the case in which a connection is to be established between the input connected to the control unit UC1-7 and the output connected to the control unit UC3-7. Bold lines A, B, C, D in the figure show the four possible alternative routes between the entrance and the exit; A hypothetical bandwidth occupancy situation at the time of the routing request for the new connection is indicated alongside each assignable link between the stages. The bandwidth occupancy values ​​refer to the maximum available bandwidth, which is assumed to be 1. The new connection is assumed to increase the bandwidth allocation by 0.1.

Two possible cost functions of a connection are examined. The first function leads to the choice of the route which introduces the least delay in the queue of the packets to be transmitted through the network, while the second function leads to the choice of the route which allows maximum utilization of the available bandwidth. The first function is given by Σ1 / (1 - Boc), where Boc indicates the occupied bandwidth of a connector between the levels. It should be noted that in a system with queues and a determined maximum bandwidth availability B = 1, the delay can be represented by a curve which has the same behavior as the function 1 / (1 - Boc) when the bandwidth allocation is increased. The second cost function is given by Σ (1-Boc), the minimum of which obviously corresponds to the maximum occupancy. Both summations contain the entire group of intermediate stage connections that are included in a route.

The unit UC1-16 of the department PE1, which comprises the input affected by the call, evaluates a cost function of the connection up to the input of the output department PU3, that is to say the connector between the fourth and fifth stages; the UC3-16 element of the PU3 department evaluates the cost function from the fifth stage exit to the network exit.

Examination of the first cost function shows that the calculation performed by UC1-16 for the part of route A that it controls results in partial costs:

CP1A = [1/1 - 0.3] + [1/1 - 0.6] + [1/1 - 0.9] + [1/1 - 0.5] = 15.93

The calculation performed by UC3-16 regarding the remaining part of route A gives as partial costs:

CP3A = [1/1 - 0.2] + [1/1 - 0.4] + [1/1 - 0.8] = 7.91

in the same way, routes B, C, D result in the following partial costs:

CP1B = 7.09 CP3B = 5.93

CP1C = 6.75 CP3C = 13.33

CP1D = 17.83 CP3D = 6.43

By means of a message that is routed through the switching network in the usual way, the unit UC3-16 communicates the results of its calculations to the unit UC1-16, which adds up the two partial costs relating to the individual routes and thereby the global costs calculated, and then determined the minimum among the found values. In the example, the global costs are CTA1 = 23.84; CTB1 = 13.02; CTC1 = 20.08; and CTD1 = 24.26. As a result, UC1-16 provides unit UC1-7 with the information necessary to route the call over path B.

If the second cost function is selected, the global costs of the different connections are:

CTA2 = 3.3; CTB2 = 3.9; CTC2 = 3.1; CTD2 = 2.8

and the call is routed from UC1 to path D, which has the minimum cost.

It is clear that this description has been given as a non-limiting example and that changes and modifications are possible without departing from the scope of the invention as defined in the appended claims. In particular, the above considerations relate to networks of any size, with coupling elements that have any number of inputs / outputs, as long as only the number of alternative routes between an input and an output of the network remains limited.