Queue management system capable of controlling priority and jitter

• US 6,215,791 B1
• Filed: 04/28/1998
• Issued: 04/10/2001
• Est. Priority Date: 04/30/1997
• Status: Expired due to Fees

• Current Assignee: Dongbu Daewoo Electronics Corporation
• Original Assignee: Daewoo Electronics (Government of South Korea)
• Inventors: Kim, Deog-Nyoun
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): HO, DUC CHI
• Application Number:
  US09/066,952
• Time in Patent Office: 1,078 Days
• Field of Search: 370/516, 370/412, 370/413, 370/414, 370/417, 370/416, 370/389, 370/392, 370/393, 370/394, 370/292, 370/230, 370/252, 370/395, 370/429
• US Class Current: 370/412
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A queue management system for selectively transmitting cells received from a plurality of sources, comprises: a multiplexer for multiplexing the cells from the plurality of sources into one output line; a cell pool for storing the cells received from the multiplexer; an idle-address FIFO for storing addresses of empty sectors of the cell pool; a sequencer, having a plurality of modules therein, each module for determining the cells'"'"' sequence of transmission, for storing information including a cell'"'"'s priority field and its corresponding address in the cell pool, comparing the stored information with information of a new entry cell, and queuing the information on the basis of the priority field, wherein the priority field is composed of a deadline time and an eligible time, the deadline time being defined as a maximum allowable delay bound at a node and the eligible time, referring to a delay bound in which a cell is supposed to be transmitted from the node; and a write controller and a read controller for generating signals for accessing to the multiplexer, the cell pool and the sequencer.

Claims

1. A queue management system for selectively transmitting cells received from a plurality of sources, the system comprising:

a multiplexer for multiplexing the cells from the plurality of sources into one output line;

a cell pool for storing the cells received from the multiplexer;

an idle-address FIFO for storing addresses of empty sectors of the cell pool;

a sequencer, having a plurality of modules therein, each module for determining the cells'"'"' sequence of transmission, for storing information including a cell'"'"'s priority field and its corresponding address in the cell pool, comparing the stored information with information of a new entry cell, and queuing the information on the basis of the priority field, wherein the priority field is composed of a deadline time and an eligible time, the deadline time being defined as a maximum allowable delay bound at a node and the eligible time, referring to a delay bound in which a cell is supposed to be transmitted from the node, being determined by taking into account a jitter; and

a write controller and a read controller for generating signals for accessing to the multiplexer, the cell pool and the sequencer,

wherein the eligible time is represented by;

2. The queue management system of claim 1, wherein the sequencer includes a plurality of modules repeated side by side, the module containing:

a register for storing the information including the priority field and its corresponding address;

a comparator for comparing a real time with the eligible time stored in the register;

a selector for selectively yielding either an output from a selector of the left-hand module or an address of the register according to an output from the comparator; and

a controller for comparing the priority field of a corresponding module with that of the new entry cell and that of a left-hand module, choosing a priority-address pair according to the result of the comparison, and letting the register store the priority-address pair.

3. The queue management system of claim 2, wherein the controller compares the deadline time of the new entry cell with that of the entries stored in the sequencer, and an entry with a smaller value of the deadline time is arranged to be at the right side to an entry with a larger deadline time;

and, further, if values of deadline time of the new entry cell with that of the entries stored in the sequencer are identical to each other, the controller compares the eligible time of the new entry cell with that of the entries stored in the sequencer so as to have an entry with a smaller value of the eligible time located to the right side of an entry with a larger eligible time.

4. The queue management system of claim 2, wherein the number of modules incorporated in the sequencer is equal to the number of cells storable in the cell pool.

5. The queue management system of claim 2, wherein the sequencer is used for a non-work-conserving queue management scheme.

6. The queue management system of claim 5, wherein the queue management system is implemented in a node incorporated in a broadband integrated service digital network.

7. The queue management system of claim 6, wherein the node is an asynchronous transfer mode switch.

8. A queue management method, for use in selectively transmitting cells received from a plurality of sources, for queuing received cells in an order that a cell with a higher priority is arranged to be transmitted first, by using priority information composed of a deadline time and an eligible time, the deadline time being defined as a maximum allowable delay bound at a node and the eligible time referring to a delay bound in which a cell is supposed to be transmitted from a node, being determined by taking into account a jitter,

wherein the eligible time is represented by:

9. The method of claim 8, wherein the method sequencer is applied for a non-work-conserving queue management scheme.

10. The method of claim 9, wherein the queue management system is implemented in a node incorporated in a broadband integrated service digital network.

11. The method of claim 10, wherein the node is an asynchronous transfer mode switch.