Fair queuing system with adaptive bandwidth redistribution

• US 6,452,933 B1
• Filed: 11/18/1997
• Issued: 09/17/2002
• Est. Priority Date: 02/07/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Lakshman, Tirunell V., Duffield, Nicholas G., Stiliadis, Dimitrios
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US08/972,424
• Time in Patent Office: 1,764 Days
• Field of Search: 370/252, 370/253, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/428, 370/429, 370/465, 370/468, 370/395
• US Class Current: 370/415
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 49/9078 using an external memory or storage device
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Apparatus for routing packets in a communication network comprises a plurality of per-connection queues, each queue established for receiving packets from a respective source and temporarily storing received packets before routing to a particular destination; a weighted fair-queuing scheduler for servicing packets from each of the plurality of per-connection queues at guaranteed pre-allocated rates; a sensing device for sensing a presence or absence of packets in queues, the absence of packets in queues indicating availability of excess bandwidth; and, a state dependent scheduler for redistributing excess bandwidth upon sensing of queues absent packets, the state dependent scheduler servicing those queues in accordance with a state variable corresponding to a performance property of the queues, wherein delay and isolation properties for routing packets of respective queues in weighted fair-queuing is preserved.

Claims

1. Apparatus for routing packets in a communication network comprising:

a plurality of per-connection queues, each queue established for receiving packets from a respective source and temporarily storing received packets before routing to a particular destination;

weighted fair queuing scheduling means servicing packets from each of said plurality of per-connection queues at guaranteed pre-allocated rates;

means for sensing a presence or absence of packets in queues, said absence of packets in queues indicating availability of excess bandwidth; and

,

state dependent scheduling means for redistributing excess bandwidth upon sensing of queues absent said packets, said state dependent scheduling means servicing those queues in accordance with a state variable corresponding to a performance property of said queues,

wherein delay and isolation properties for routing packets of respective queues is preserved.

2. Apparatus for routing packets in a communication network as claimed in claim 1, wherein a said performance property of a queue includes the queue having the greatest amount of packets, said corresponding state variable being longest queue first.

3. Apparatus for routing packets in a communication network as claimed in claim 1, wherein a said performance property of a queue includes that queue having a packet waiting to be serviced in the longest amount of time, said corresponding state variable being longest delay first.

4. Apparatus for routing packets in a communication network as claimed in claim 1, wherein a said performance property of a queue includes the queue most likely to overflow buffer memory containing said queue, said corresponding state variable being most likely to overflow buffer.

5. Apparatus for routing packets in a communication network as claimed in claim 1, wherein a worst case fairness measure for said connections is satisfied.

6. Method for routing packets in a communication network comprising:

establishing a plurality of per-connection queues, each queue for receiving packets from a respective source and temporarily storing received packets before routing to a particular destination;

servicing packets from each of said plurality of per-connection queues at guaranteed pre-allocated rates;

sensing a presence or absence of packets in queues, said absence of packets in queues indicating availability of excess bandwidth; and

,

for redistributing excess bandwidth upon sensing of queues absent said packets, said state dependent scheduling means servicing those queues in accordance with a state variable corresponding to a performance property of said queues, while preserving delay and isolation properties for routing of said packets.

7. Apparatus for routing packets in a communication network comprising:

a plurality of per-connection queues, each queue established for receiving packets from a respective source and temporarily storing received packets before routing to a destination;

a weighted fair queuing (WFQ) server coupled to receive packets from each of said plurality of per-connection queues, and as a WFQ output, schedule packets for delivery;

means for sensing an absence of packets in each of said plurality of per-connection queues;

a state dependent server (SDS) coupled to receive packets from each of said plurality of per-connection queues, and as an SDS output, schedule packets for delivery upon sensing said absence of packets in at least one of said plurality of per-connection queues; and

a multiplexer coupled to receive said WFQ and SDS outputs, to multiplex packets scheduled by said WFQ server with packets scheduled by said SDS, for delivery to said destination.

8. A method for routing packets comprising:

queuing packets in a plurality of per-connection queues, each queue utilized for receiving packets from a respective source and temporarily storing received packets before routing to a destination;

scheduling packets for delivery from a first scheduling server, from among said plurality of per-connection queues, based upon a weighted fair queuing (WFQ) priority;

monitoring each of said plurality of per-connection queues to sense an absence of queued packets in at least one of said plurality of per-connection queues;

scheduling packets for delivery from a second scheduling server, from among said plurality of per-connection queues, based upon any state dependent priority; and

multiplexing packets scheduled from said first scheduling server and said second scheduling server for delivery to said destination.