Fair queuing system with adaptive bandwidth redistribution

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.

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.

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.