Scheduling mechanisms for use in mobile ad hoc wireless networks for achieving a differentiated services per-hop behavior

• US 20030007453A1
• Filed: 07/06/2001
• Published: 01/09/2003
• Est. Priority Date: 07/06/2001
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Ogier, Richard G., Sastry, Ambatipudi R.
• Granted Patent: US 7,006,437 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04W 72/563 of the wireless resources
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Scheduling mechanisms for attaining a per-hop behavior for a plurality of classes of packet traffic in a multi-hop network are described. The per-hop behavior allocates to each class a nominal departure rate and a minimum percentage of available bandwidth. The scheduling mechanisms define a first condition that affects packet forwarding in accordance with the nominal departure rates allocated to the classes and a second condition that affects packet forwarding in accordance with the minimum percentages of the available bandwidth allocated to the classes. Packet forwarding rates for each of the classes are compared with the first and second conditions to select one of the classes for forwarding packets of that class over the network.

Claims

1. A method for attaining a per-hop behavior for a plurality of classes of packet traffic in a multi-hop network, the per-hop behavior allocating to each class a nominal departure rate and a minimum percentage of available bandwidth, comprising:

defining a first condition that affects packet forwarding in accordance with the nominal departure rates allocated to the classes;

defining a second condition that affects packet forwarding in accordance with the minimum percentages of the available bandwidth allocated to the classes; and

comparing a packet forwarding rate for each of the classes with the first and second conditions to select one of the classes for forwarding packets of that class over the network.

2. The method of claim 1 wherein the first condition is whether the packet forwarding rate of each class is at most the nominal departure rate of that class.

3. The method of claim 1 wherein the second condition is whether the packet forwarding rate of a given class is at most the minimum percentage of the available bandwidth of that class.

4. The method of claim 1 further comprising determining an average packet forwarding rate for each class over a time interval having a predetermined duration.

5. The method of claim 4 wherein the predetermined duration of the time interval is 5 seconds.

6. The method of claim 1 further comprising assigning a scheduling priority to each class based on a criterion.

7. The method of claim 6 wherein the criterion is a delay that each class can tolerate.

8. The method of claim 6 further comprising identifying a plurality of the classes from which to select a class for packet forwarding, and selecting the class with the highest scheduling priority from the identified plurality of classes.

9. The method of claim 1 further comprising assigning a weight to each of the classes that corresponds to the minimum percentage of the available bandwidth allocated to each class.

10. The method of claim 9 further comprising identifying a plurality of the classes from which to select a class for packet forwarding, and selecting one of the identified classes based on an order determined by the weights assigned to the identified classes.

11. The method of claim 10 wherein the order is a weighted round robin order.

13. The method of claim 12 further comprising weighting each of the classes with a weight that corresponds to the minimum percentage allocated to that class, and wherein the predefined criterion is to use a weighted round robin order to select one of the identified classes for forwarding a packet of that class.

14. The method of claim 12 further comprising assigning a scheduling priority to each class, and wherein the predefined criterion is to select a class with the highest scheduling priority of the identified classes for forwarding a packet of that class.

15. The method of claim 12 wherein over the time interval each class with a non-empty queue is receiving more than the minimum percentage of the available bandwidth allocated to that class, and further comprising selecting a class with a non-empty queue that has the highest scheduling priority of those classes that are receiving at most the respective allocated nominal departure rate, for forwarding a packet of the selected class.

16. The method of claim 15 wherein over the time interval each class with a non-empty queue is receiving more than the nominal departure rate allocated to that class, and further comprising selecting a class with a non-empty queue that has the highest scheduling priority.

17. The method of claim 12 wherein over the time interval each class with a non-empty queue is receiving more than the nominal departure rate allocated to that class, and further comprising selecting a class with a non-empty queue that has the highest scheduling priority of those classes that are receiving at most the respective allocated minimum percentage of the available bandwidth, for forwarding a packet of the selected class.

18. The method of claim 12 wherein over the time interval each class with a non-empty queue is receiving more than the nominal departure rate and more than the rate priority percentage allocated to that class, and further comprising selecting a class with a non-empty queue that has the highest scheduling priority, for transmitting a packet of the selected class.

19. The method of claim 12 further comprising assigning a scheduling priority to each of the classes based on a criterion.

12. A method for attaining a per-hop behavior for a plurality of classes of packet traffic in a multi-hop network, the per-hop behavior allocating to each class a nominal departure rate and a minimum percentage of available bandwidth, comprising:

identifying each class with a non-empty queue that over a time interval is receiving less than the nominal departure rate and less than the minimum percentage allocated to that class; and

selecting one of the identified classes according to a predefined criterion, for forwarding a packet of the selected class over the network.

20. An article of manufacture having computer-readable program means embodied thereon for attaining a per-hop behavior for a plurality of classes of packet traffic in a multi-hop network, the per-hop behavior allocating to each class a nominal departure rate and a minimum percentage of available bandwidth, the article comprising:

computer-readable means for defining a first condition that affects packet forwarding in accordance with the nominal departure rates allocated to the classes;

computer-readable means for defining a second condition that affects packet forwarding in accordance with the minimum percentages of the available bandwidth allocated to the classes; and

computer-readable means for comparing a packet forwarding rate for each of the classes with the first and second conditions to select one of the classes for forwarding packets of that class over the network.