Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
1998-11-25
2004-04-27
Ton, Dang (Department: 2666)
Multiplex communications
Pathfinding or routing
Store and forward
C370S412000
Reexamination Certificate
active
06728256
ABSTRACT:
This invention relates to a shared buffer control device which can be used in a packet or cell switching unit using buffers or in an input or output terminal module of an asynchronous switching network using buffers.
BACKGROUND OF THE INVENTION
Information is increasingly transmitted using digital signals transmitted in the form of asynchronous data made up of packets or cells that are transmitted from their point of origin to their point of arrival via nodes at which a number of lines converge and from which a multiplicity of lines depart. A packet or a cell must be switched from an input line to at least one output line. This switching, which is effected under the control of a routing algorithm, is performed by switching units each of which comprises a plurality of inputs (n
1
inputs) and a plurality of outputs (n
2
outputs).
In some conventional switching units input data is stored in a buffer from which it is subsequently extracted to be transmitted to the output chosen by the routing algorithm.
The simplest version of a switching unit of the above kind includes an individual buffer for each of the n
2
outputs, each item of input data being written into the buffer relating to the output chosen by the routing algorithm. However, to simplify these units it is known to use a single buffer called a “shared buffer”. In this case the switching unit typically includes an input multiplexer and an output demultiplexer and control means for controlling the buffer in particular.
The operation of a unit of the above kind is cyclic. Each cycle corresponds to writing into the shared buffer data received on each of the n
1
inputs and to reading from the shared buffer data to be transmitted to each of the n
2
outputs. Each cycle is conventionally divided into a number of time slots during each of which a data block read operation and/or a data block write operation is/are effected. During a given time slot comprising both types of operation a data block received on a particular input is written and a data block to be transmitted to a given output is read but a read operation and a write operation at the same buffer location must be effected at different times.
The duration of a cycle is conditioned by three parameters, namely the binary bit rate at the inputs and outputs of the switching unit, the number of bits of a data block processed in parallel, and the number of inputs and outputs of the switching unit. Although it is desirable to increase the capacity (n
1
×n
2
) of the switching unit, the duration of a cycle is reduced when the inputs/outputs are at a high bit rate and it is not possible to increase the size of a data block processed in parallel beyond certain limits of complexity.
In broadband applications the need to increase the number of inputs and outputs reduces the duration of the time slots and therefore the time allocated to each operation to write or to read the shared buffer. This can not only lead to prohibitive additional costs but also run up against performance limits of the technology in terms of memory access time.
European Patent Application No. EP 0 700 187 (Mitsubishi) describes a shared buffer control device that includes a plurality of sub-buffers. The shared sub-buffers are controlled so that during at least some time slots writing an input data block and extracting a data block to an output can be effected simultaneously in separate shared sub-buffers, selecting the shared sub-buffers for reading taking priority over selecting the shared sub-buffer for writing.
In this way, for each read operation, as for each write operation, all of the time slot is available whereas with a switching unit of the previous prior art type a time slot has to be shared in order to effect the two types of operation consecutively. The set of shared sub-buffers, all of which have the same capacity and are identical to each other, constitutes a virtual shared buffer equivalent to a single shared buffer of a prior art switching unit.
The prior art control device includes a shared buffer control unit for controlling an input switch and selecting the shared sub-buffer into which a received cell is written. The unit reads a plurality of cells in a plurality of shared sub-buffers during a time cycle corresponding to that of a cell and controls an output switch to transmit each cell read to a selected output. The control device updates a sub-buffer access table having a first dimension representing the number of sub-buffers and a second dimension representing the number of time slots in a time cycle corresponding to that of a cell.
Arbitration between write access and read access to the sub-buffers is controlled in parallel for all access time slots (n
1
wrote access and n
2
read access for a switching unit with n
1
inputs and n
2
outputs) in a time cycle corresponding to that of a cell.
OBJECTS AND SUMMARY OF THE INVENTION
The control device is complex and the aim of the present invention is to propose a simpler control device.
In accordance with the invention, a control device for a shared buffer comprising a plurality of shared sub-buffers, a write selector circuit for writing therein data blocks from inputs, and a read selector circuit for reading said data blocks therein afterwards and directing them to at least one output; said two selector circuits including arbitration means for writing and reading data blocks:
in accordance with periodic cycles, each cycle including time slots during each of which a data block received at an input can be written into one of said shared sub-buffers and during which a data block previously written can be read and sent to a particular output;
simultaneously, at least during some of said time slots, writing a data block from an input and reading a data block to be sent to an output in different shared sub-buffers; selecting a sub-buffer for reading taking priority over selecting the same sub-buffer for writing;
wherein said arbitration means include means for arbitrating a single write access vis a vis a single read access during each time slot.
This control device is simpler to produce because arbitration between sub-buffer write access and read access is managed serially, i.e. successively for each Individual time slot for access to a sub-buffer within a time cycle corresponding to that of a cell. It performs a single logic operation during each time slot to arbitrate a single write access relative to a single read access.
To control a device of the above kind it is necessary to take account of the fact that choosing the shared sub-buffer in which to write is limited not only by the availability of free locations in the various shared sub-buffers but also by the unavailability of access to the shared sub-buffer selected for reading, which takes priority. It is therefore necessary to know the number of the shared sub-buffer in which the data block to be read is stored in order to be able to select another shared sub-buffer in which an incoming data block can be stored; this selection is effected in accordance with the availability of free locations of the sub-buffers, for example.
Control must also allow for the risks of blocking during writing. Compared to a switching unit with a single shared buffer, a switching unit in accordance with the invention has an additional risk of blocking, which can occur when only the shared sub-buffer used for reading has free locations and all the other shared sub-buffers accessible for writing are entirely filled. The risk of blocking is an additional risk in that it does not exist in the conventional case of a single shared buffer (in which case it is always possible to write in the last free location, regardless of which one it is).
The additional possibility of blocking decreases as the number of shared sub-buffers increases. However, as increasing the number of buffers makes control more complex, it is in practice preferable to limit this number to a relatively low value.
In one preferred embodiment, the two selector circuits are such that, for each time slot, the choice of the sub-buffer for w
Alcatel
Ton Dang
Tran Phuc
LandOfFree
Shared buffer control device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shared buffer control device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared buffer control device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3245923