Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1996-11-21
2001-07-24
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S230000
Reexamination Certificate
active
06266338
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system for the regulation of information trains for a packet switch.
FIG. 1
shows the schematic diagram of a device for the regulation of information trains within a switch. A device of this kind has chiefly input modules, output modules and a routing module.
To simplify the description, only three input modules and three output modules, respectively referenced E
1
, E
2
, E
3
; S
1
, S
2
, S
3
have been shown in this figure.
In general, these modules are each made in the form of an electronic card with a standard format.
Each input module receives an information train at its input port. This information train, which is at a high bit rate, may or may not be sporadic.
Each module, namely each input card or output card, has two ports, an input port and an output port. The routing module has at least as many input ports and output ports respectively as it has input cards and output cards respectively.
An input link of the switch forms an input port of an input card.
A port consists of a channel that takes several paths forming an interlacing of information trains, it being known that instantaneously there is only one cell on the channel. Information trains enter asynchronously and exit asynchronously.
After going through an input and output module (or card), the order of the packets in each information train must remain the same.
Reference may be made, for a clearer understanding of the description, to the diagram of
FIG. 2
, which shows cases of interlacing of information trains flowing through an input card or through an output card.
Indeed, this diagram illustrates the incoming of three information trains at the input port with the bit rate DE card and the exit of these three information trains at the output port with the bit rate DS of the card.
The digits 1 and 2 mark the order of the cells within one and the same train. It can be seen that the order of the packets in each information train is the same at output as it is at input.
With an information train there is associated a bit rate (this is the number of cells per second) which is also the bit rate of the path on which it is moving.
With a port there is associated a bit rate (the borderline value of the number of cells per second independently of the information trains to which these cells belong). The input bit rate DE of an input card is generally equal to the output bit rate DS of this card. It may also be lower.
It will be recalled that the term “active path” for a card is understood to mean a path for which there are cells in this card (this notion of active path is therefore internal to a switch).
The cells are placed on each output link according to a particular rule by distinguishing the paths to which they belong. This particular rule could be for example:
either in proportion to the bit rates of each pat h,
or by the equitable sharing of the link between the active paths.
Other rules may be envisaged.
It will also be recalled that it is possible for a communication (for information other than data trains) between switches to be set up in order to adjust the bit rate of the paths between switches.
It is then possible for a switch to send an indication to its upline switch instructing it to reduce the bit rates of the paths coming from the output cards of this upline switch.
An output of the upline switch is then associated with an input card of the switch considered.
Reference may be made to the diagram of
FIG. 3
which illustrates this example.
A clearer understanding of the problem posed can be obtained by looking inside a switch. Tijk denotes the information train flowing on the path Tijk coming from the input module i, going towards the output module J, this information train having an index k among the trains having same input modules and same output modules.
The routing module is capable of processing the sum of the incoming bit rates. Its function is to send a data train from a port
i
to a port
j
in following the flow. It is possible that the information trains coming from different input ports will be routed to the same output module.
The constraints of processing time and of storage capacity of the input or output modules are such that the bit rate that a module can accept at input (DE) is limited.
The reference DEe will be applied to the input bit rate of an input module, DEs being that of an output module and DEa that of the routing device.
The reference DSe will be applied to the output bit rate of an input module, DSs to that of an output module and DSa to that of the routing device.
Hereinafter, a distinction shall be made between the case where the routing device is not limited in output bit rate and the case where its output ports and input ports have the same bit rate:
Case A
Even if the routing device were to bear the superimposition of the bit rates of each of the information trains that converge towards the same output port (in having the bit rate of each output port equal to the sum of the bit rates of its input ports: DSa=&Sgr; DEa), the output card is limited by the bit rate DEs that it can accept, DEs<<&Sgr; DEa; a bottleneck thus appears at the input of the output card.
Case B
When the routing card has input and output ports with the same bit rates (DSa=DEa), a buffer of limited size is associated with each output port with the aim of accepting the excess bit rate as compared with DSa, generated by the simultaneity of convergence of sporadic trains.
However, the risk remains that this limited memory capacity will be insufficient to collect the excess of bit rate as compared with DSa, whence the risk of uncontrollable losses in the buffer.
In this case, the problem is shifted from the input of the output card (case A) to the output of the routing device (case B). This is illustrated in the diagram of FIG.
5
.
There is therefore a bottleneck. This bottleneck is set up by the routing device.
2. Description of the Prior Art
Hereinafter, the approaches that have been provided to resolve this problem shall be enumerated.
1) The first approach consists in placing a buffer at output of the routing device. Practically, this amounts to placing a large memory at each output port. The memory size is a function of the number of inputs and of the bit rate so as to buffer the excess bit rate at output of the routing device.
In the case A (defined here above), the memories are placed between the output port of the routing device and the output card as shown in FIG.
6
.
In the case B, these memories are placed in the routing card at the output port as shown in FIG.
5
.
The size of the buffer needed to collect the excess bit rate increases linearly according to the relationship: (n−1)×D×T, with n as the number of inputs of the routing device, D as the bit rate of the input ports of the routing device and of the output port (case B) or of the input of the output card (case A), T the duration during which the simultaneity of convergence occurs.
For eight inputs at 155 M bits per second and 424-bits cells (giving 365 k cells per second) and information trains with a length of 200 cells (the duration of a train being 547 &mgr;s), a buffer size of 1,400 cells is needed to collect the bit rate on the duration of a train (547 &mgr;s), and increases linearly so long as this simultaneity of convergence continues (for example on several trains).
Thus, the memory sizes needed very soon become substantial, and there is no certainty that the memory size chosen will be sufficient to collect the excess bit rate in every possible example.
Now, having uncontrollable losses is intolerable.
Furthermore, in the case B, when the routing card is taken from among those available in the market, there is no possibility of modifying the memory size within the routing device. This routing device is fixed by the manufacturer (for example the Fujitsu MB86680A matrix has buffers at output with a capacity of 75 cells).
2) The second approach consists in placing a buffer at the input of the routing
Berthou Martine
Calvignac Géraldine
Simon Jean Louis
Chin Wellington
France Telecom
Nguyen Steven
Nilles & Nilles SC
LandOfFree
System for the regulation of information trains for packets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for the regulation of information trains for packets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for the regulation of information trains for packets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2558024