Methods and apparatus for differentiated services over a packet-based network
View Patent ↗Methods and apparatus for the provision of differentiated services in a packet-based network may be provided in a communications device such as a switch or router having input ports and output ports. Each output port is associated with a set of configurable queues that store incoming data packets from one or more input ports. A scheduling mechanism retrieves data packets from individual queues in accord with a specified configuration, providing both pure priority and proportionate de-queuing to achieve a guaranteed QoS over a connectionless network.
1. A communications device for use on a communications network, the device capable of transferring data packets received at an input port to an output port, the device comprising:
an input configured to allow specification of first and second configuration parameters, each of said first and the second configuration parameters indicating a queue mode;
a first configurable queue associated with said first configuration parameter and in communication with said input port and said output port; and
a second configurable queue associated with said second configuration parameter in communication with said input port and said output port,
wherein each of said first and second queues is configurable, by each of said first and second configuration parameters, to independently operate in one of a fairness-based mode, wherein a fairness-based queue is serviced when egress bandwidth is available, and a priority-based mode, wherein a priority-based queue with packets for dequeuing is serviced before a fairness-based queue is serviced when priority-based mode dequeuing constraints are met.
2. The device of claim 1 further comprising:
a dequeuing component in communication with each of said first and second queues and said output port.
3. The device of claim 1 wherein said first queue comprises:
a first credit counter for tracking credits associated with said first queue,
wherein said first queue is ineligible for service unless said first credit counter indicates said first queue has sufficient credits for service.
4. The device of claim 3 wherein said second queue comprises:
a second credit counter for tracking credits associated with said second queue,
wherein said second queue is ineligible for service unless said second credit counter indicates said second queue has sufficient credits for service.
5. The device of claim 3 wherein said first queue further comprises:
a first enable bit specifying the state of said first credit counter; and
a first increment register specifying an incremental value for said first credit counter.
6. The device of claim 4 wherein said second queue further comprises:
a second enable bit specifying the state of said second credit counter; and
a second increment register specifying the incremental value for said second credit counter.
7. The device of claim 5 wherein said first queue further comprises:
a first rate value register specifying the rate at which said first credit counter is incremented.
8. The device of claim 6 wherein said second queue further comprises:
a second rate value register specifying the rate at which said second credit counter is incremented.
9. The device of claim 3 wherein said first queue further comprises:
a first burst size register specifying a maximum value for said first credit counter,
wherein said first credit counter is unable to accumulate credits in excess of said specified maximum value.
10. The device of claim 4 wherein said second queue further comprises:
a second burst size register specifying a maximum value for said second credit counter,
wherein said second credit counter is unable to accumulate credits in excess of said specified maximum value.
11. The device of claim 9 wherein said first queue further comprises:
a first credit allocation register comprising entries indicative of at least one other queue for receiving credits in excess of said first maximum value.
12. The device of claim 10 wherein said second queue further comprises:
a second credit allocation register comprising entries indicative of at least one other queue for receiving credits in excess of said second maximum value.
13. The device of claim 11 wherein said entries in said first credit allocation register proportionately represent said at least one other queue.
14. The device of claim 12 wherein said entries in said second credit allocation register proportionately represent said at least one other queue.
15. The device of claim 11 wherein said first queue further comprises:
a first received donation register comprising entries indicative of said received credits from at least one other queue.
16. The device of claim 12 wherein said second queue further comprises:
a second received donation register comprising entries indicative of said received credits from at least one other queue.
17. The device of claim 1 further comprising:
a priority mask register associated with said output port comprising entries associated with at least one queue, said entries specifying the operation of said at least one queue in either priority-based mode or fairness-based mode.
18. The device of claim 1 further comprising:
a dequeuing vector associated with at least one queue operating in a fairness-based mode, said dequeuing vector comprising entries associated with at least one queue.
19. The device of claim 18 wherein said entries in said dequeuing vector proportionately represent said at least one other queue.
20. The device of claim 1 further comprising:
a vector register comprising a value specifying the maximum amount of data to be provided by a fairness-based queue to its associated output port.
21. A method for routing data packets using a telecommunications device, the method comprising the steps:
configuring a first configurable queue to operate in one of a fairness-based mode and a priority-based mode by specifying a first configuration parameter, the first configurable queue being in communication with an input port and an output port;
configuring a second configurable queue to operate in one of a fairness-based mode and a priority-based mode by specifying a second configuration parameter, the second configurable queue in communication with said input port and said output port;
(b) receiving a packet at said input port;
(c) classifying the packet as subject to one of fairness-based handling and priority-based handling;
(d) assigning said packet to one of said first configurable queue and said second configurable queue operating in a mode corresponding to the handling to which the packet is subject; and
(e) causing the queue to which said packet has been assigned to provide said packet to said output port by servicing said identified queue in one of a fairness-based mode and a priority-based mode, as configured.
22. The method of claim 21 wherein the received packet is classified prior to receipt at said input port as subject to one of fairness-based handling and priority-based handling.
23. The method of claim 21 wherein the received packet is not classified prior to receipt at said input port as subject to one of fairness-based handling and priority-based handling.
24. The method of claim 21 further comprising the steps:
(f) providing a plurality of quality-of-service levels for association with packets; and
(g) associating each of said plurality of quality-of-service levels with one of said first configurable queue and said second configurable queue.
25. The method of claim 21 further comprising the steps:
(f) incrementing a first credit counter associated with said first queue;
(g) comparing the value of said first credit counter to a first predetermined value; and
(h) providing said packet in step (e) if the result of said comparison indicates that the value of said credit counter exceeds said first predetermined value.
26. The method of claim 21 further comprising the steps:
(f) incrementing a first credit counter associated with said first queue;
(g) comparing the value of said first credit counter to a first predetermined value;
(h) decrementing said first incremented credit counter if the result of said comparison indicates that said first incremented credit counter exceeds said first predetermined value; and
(i) incrementing a second credit counter.
27. The method of claim 26 wherein step (i) comprises the step:
incrementing said second credit counter by the excess of said first incremented credit counter over said first predetermined value.
28. The method of claim 26 wherein step (i) comprises the step:
incrementing said second credit counter by the amount used to increment said first credit counter.
29. The method of claim 26 further comprising the steps:
(j) accessing a credit allocation register;
(k) retrieving the next entry in said credit allocation register; and
(l) processing said retrieved entry as said second credit counter.
30. The method of claim 21 further comprising the steps:
(f) referencing a priority mask register associated with said output port;
(g) retrieving an entry in said priority mask register defining the operational state of said first configurable queue as one of a fairness-based mode and a priority-based mode; and
(h) retrieving an entry in said priority mask register defining the operational state of said second configurable queue as one of a fairness-based mode and a priority-based mode.
31. The method of claim 21 wherein step (f) comprises the steps:
(e-1) servicing said identified queue in a priority-based mode;
(e-2) iterating step (e-1) until said identified queue is emptied of packets or a predetermined transmission criteria is satisfied.
32. The method of claim 31 further comprising the steps:
(f) incrementing a first credit counter associated with said first queue;
(g) comparing the value of said first credit counter to a first predetermined value;
(h) decrementing said first incremented credit counter if the result of said comparison indicates that said first incremented credit counter exceeds said first predetermined value; and
(i) incrementing a second credit counter.
33. The method of claim 32 wherein step (i) comprises the step:
incrementing said second credit counter by the excess of said first incremented credit counter over said first predetermined value.
34. The method of claim 32 wherein step (i) comprises the step:
incrementing said second credit counter by the amount used to increment said first credit counter.
35. The method of claim 32 further comprising the steps:
(j) accessing a credit allocation register;
(k) retrieving the next entry in said credit allocation register; and
(l) processing said retrieved entry as said second credit counter.
36. The method of claim 31 further comprising the step:
(e-3) iterating steps (e-1) and (e-2) for all remaining queues configured to operate in a priority-based mode; and
(e-4) servicing a queue configured to operate in a fairness-based mode until a queue configured to operate in a priority-based mode requires servicing.
37. A method for routing data packets using a telecommunications device, the method comprising the steps of:
(a) configuring at least one first queue of a plurality of configurable queues to operate in fairness-based mode by specifying at least one configuration parameter;
(b) configuring at least one second queue of a plurality of configurable queues to operate in priority-based mode by specifying at least one other configuration parameter;
(c) dequeuing a packet from said at least one second queue while said at least one second queue has remaining packets; and
(d) dequeuing a packet from said at least one first queue while said at least one second queue has no remaining packets.