Method of managing a queue of digital cells

Details Method of managing a queue of digital cells Method of managing a queue of digital cells

1999-08-12

2003-05-27

Ton, Dang (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395420, C370S428000, C370S389000, C710S054000

Reexamination Certificate

active

06570882

ABSTRACT:

The present invention concerns a method of managing a queue of digital cells.
BACKGROUND OF THE INVENTION
In the field of digital transmission, the objective of a method of the above kind is to determine, for data or cells received from various sources, the order in which the cells are to be forwarded to an external unit.
The order in which the various cells are forwarded can naturally differ from that in which they are received. This operation of classifying the received cells is generally called queue management.
Queue management relies on a priority level of each source, priority level often being a function of the rate at which the sources send successive cells.
French Patent Application No. 2 715 258 proposes a data sorting system for queue management of the above type. The system comprises a down column of chained registers for storing the data, the first register of the column being adapted to receive the data to be classified. It also comprises an up column of chained registers, the last register of this column containing the data to be forwarded. Each register of the up column is also associated with a register of the down column in a one-to-relationship and classification is effected by exchanging data stored in the registers of the down column with data stored in the registers of the up column. Without going into how this register works in detail, it is clear that managing the transfer of data between the interconnected registers represents some degree of complexity because of the stepwise progress of the data in each column.
Transferring each item of data requires a number of transfers corresponding to the number of registers that the data must pass through. It follows that the greater the number of registers in each column, the greater the cost of this operation in terms of the number of transfers.
OBJECTS AND SUMMARY OF THE INVENTION
The aim of the present invention is therefore to provide a queue management method requiring a limited number of operations to classify cells. It is particularly well suited to relatively long queues.
The method of the invention for managing a queue of cells received from a plurality of sources comprises the following steps:
storing the last cell received at a receive address in a buffer, and
establishing for the last cell received a time stamp representing the theoretical time it is to leave the queue,
and the method further comprises the following steps:
inserting the receive address in a programmer at a location identified by the time stamp of the last cell received,
setting an occupancy bit associated with the time stamp to an active state,
determining the first cell(s) to leave the queue from the first active occupancy bit following that of the cell that has just left the queue, the occupancy bits being classified in increasing order of the associated time stamps, and
setting the occupancy bit of the first cell to an inactive state when it leaves the queue.
When the last cell received comes from a source assigned a priority level, the time stamp of that cell depends on the priority level.
For example, the source sends cells at a rate corresponding to an average period, the priority level corresponds to that period, and the time stamp is greater than or equal to that of the preceding cell from the source plus the period.
Moreover, the time stamp is also greater than or equal to the time stamp of the first cell.
In an advantageous implementation of the method, the successive occupancy bits are grouped into words and a flag is established for each of these words which has the value 0 when all the bits of the words are inactive and which has the value 1 otherwise.
Moreover, the flag of the corresponding word is recalculated after setting an occupancy bit.
It is therefore possible to look for the first non-zero flag and then the first non-zero bit associated with that flag to determine the first cell(s) to leave the queue.
However, according to an additional feature, the successive flags are grouped into fields and an index is established for each of these fields which has the value 0 when all the bits of the word are inactive and which has the value 1 otherwise.
In this case, after setting an occupancy bit and recalculating the flag of the corresponding word, the index of the field comprising that flag is recalculated.
Thus, advantageously, the first non-zero index and then the first non-zero flag associated with that index and finally the first non-zero bit associated with that flag are looked for to determine the first cell(s) to leave the queue.
Also, the time stamp is preferably established modulo a predetermined capacity constant.
According to an additional feature, the programmer includes at least two pages and the first cell(s) to leave the queue are determined page by page.
In any event, the invention also covers the situation in which one of the locations of the programmer contains a chained list of addresses.


REFERENCES:
patent: 5748614 (1998-05-01), Wallmeier
patent: 5920568 (1999-07-01), Kurita et al.
patent: 6389031 (2002-05-01), Chao et al.
patent: 0 632 622 (1995-01-01), None
patent: 0 710 046 (1996-05-01), None
patent: 0 782 303 (1997-07-01), None
patent: 2 324 678 (1998-10-01), None
F. Chiussi et al, “Implementing Fair Queueing in ATM Switches—Part 2, The Logarithmic Calendar Queue” IEEE Global Telecommunications Conference, Phoenix, Arizona, Nov. 3-8, 1997, vol. 1, Nov. 3, 1997, pp. 519-525, XP000737586, Institute of Electrical and Electronics Engineers.

Affiliated with

Also associated with

Rating

Method of managing a queue of digital cells does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of managing a queue of digital cells, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of managing a queue of digital cells will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3071246