Method and apparatus for scheduling a heterogeneous communication flow
View Patent ↗A method and apparatus are provided for scheduling a heterogeneous communication flow. A heterogeneous flow is a flow comprising packets with varying classes or levels of service, which may correspond to different priorities, qualities of service or other service characteristics. When a packet is ready for scheduling, it is queued in order in a flow queue that corresponds to the communication flow. The flow queue then migrates among class queues that correspond to the class or level of service of the packet at the head of the flow queue. Thus, after the head packet is scheduled, the flow queue may be dequeued from its current class queue and requeued at the tail of another class queue. If the subsequent packet has the same classification, it may be requeued at the tail of the class queue or may remain in place for another servicing round.
1. A method of servicing packets according to a class-based scheduler, the method comprising:
enqueuing, in a first class queue corresponding to a first class of service, a flow queue comprising packets of multiple different classes, including a first packet at a head of the flow queue that is of the first class of service;
dequeuing the first packet;
identifying a second class of a second packet now at the head of the flow queue; and
enqueuing the flow queue in a second class queue corresponding to the second class;
wherein:
the first class has a first set of QoS (Quality of Service) parameters and requires preservation of packet ordering; and
the second class has a second set of QoS parameters different from the first set of QoS parameters, and requires preservation of packet ordering.
2. The method of claim 1 , wherein said dequeuing the first packet comprises:
dequeuing the flow queue from the first class queue; and
dequeuing the first packet from the flow queue.
3. The method of claim 1 , wherein:
the flow queue comprises references to packets.
4. The method of claim 3 , wherein:
each of the first class queue and the second class queue is configured to comprise references to flow queues.
5. The method of claim 1 , further comprising:
receiving a new packet; and
enqueuing the new packet within the flow queue.
6. The method of claim 1 , wherein said identifying the second class of the second packet comprises:
classifying the second packet.
7. The method of claim 1 , further comprising:
storing a storage location of the flow queue.
8. The method of claim 7 , wherein:
said enqueuing the flow queue within the first class queue comprises writing to an electronic storage area associated with the first class queue a reference to the storage location of the flow queue.
9. The method of claim 1 , further comprising:
configuring one or more classification rules for classifying each packet of a heterogeneous communication flow to one of multiple classes, including the first class and the second class; and
the flow queue comprises packets of the heterogeneous communication flow.
10. A non-transitory computer-readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of servicing packets according to a class-based scheduler, the method comprising:
enqueuing, in a first class queue corresponding to a first class of service, a flow queue comprising packets of multiple different classes, including a first packet at a head of the flow queue that is of the first class of service;
dequeuing the first packet;
identifying a second class of a second packet now at the head of the flow queue; and
enqueuing the flow queue in a second class queue corresponding to the second class;
wherein:
the first class has a first set of QoS (Quality of Service) parameters and requires preservation of packet ordering; and
the second class has a second set of QoS parameters different from the first set of QoS parameters, and requires preservation of packet ordering.
11. The non-transitory computer-readable medium of claim 10 , wherein said dequeuing the first packet comprises:
dequeuing the flow queue from the first class queue; and
dequeuing the first packet from the flow queue.
12. The non-transitory computer-readable medium of claim 10 , wherein:
the flow queue comprises references to packets.
13. The non-transitory computer-readable medium of claim 12 , wherein:
each of the first class queue and the second class queue is configured to comprise references to flow queues.
14. The non-transitory computer-readable medium of claim 10 , wherein the method further comprises:
receiving a new packet; and
enqueuing the new packet within the flow queue.
15. The non-transitory computer-readable medium of claim 10 , wherein said identifying the second class of the second packet comprises:
classifying the second packet.
16. The non-transitory computer-readable medium of claim 10 , wherein the method further comprises:
storing a storage location of the flow queue;
wherein said enqueuing the flow queue within the first class queue comprises writing to an electronic storage area associated with the first class queue a reference to the storage location of the flow queue.
17. The non-transitory computer-readable medium of claim 10 , further comprising:
configuring one or more classification rules for classifying each packet of a heterogeneous communication flow to one of multiple classes, including the first class and the second class; and
the flow queue comprises packets of the heterogeneous communication flow.