NESTED WEIGHTED ROUND ROBIN QUEUING
In a Mobile Ad Hoc Network (MANET), nested weighted round robin queues are employed to selectively provide channel access for traffic according to a priority or Quality of Service (QoS) for data. By nesting queues within other queues, and applying a weighted round robin technique to serve each queue, relatively arbitrary service metrics may be achieved including nodal QoS for class-based traffic, avoidance of queue starvation, and so forth. Prioritized queues may also be provided for preemptive delivery of high priority traffic.
1 . A method comprising:
storing a plurality of data packets in a plurality of queues for transmission in a number of time slots from a node of a mobile ad hoc network, each one of the plurality of queues having a weight;
selecting a first data packet from the plurality of data packets for transmission in one of the number of time slots according to a first weighted round robin schedule that is weighted to serve a first group of the plurality of queues according to their respective weights; and
selecting a second data packet from the plurality of data packets according to a second weighted round robin schedule that is weighted to serve a second group of the plurality of queues according to their respective weights, wherein the first weighted round robin schedule includes a weight for the second round robin schedule and periodically serves the second weighted round robin schedule according to the weight, thereby selecting the second data packet in the first weighted round robin schedule for transmission in one of the number of time slots.
2 . The method of claim 1 further comprising preemptively selecting data packets from a prioritized queue until the prioritized queue is empty.
3 . The method of claim 2 further comprising:
providing a plurality of prioritized queues, each one of the prioritized queues having a priority; and
preemptively selecting data packets from the plurality of prioritized queues according to the priority until each one of the prioritized queues is empty.
4 . The method of claim 2 further comprising assigning a Quality of Service level to the prioritized queue, whereby data having the corresponding Quality of Service is placed into the prioritized queue and preemptively scheduled for transmission.
5 . The method of claim 1 further comprising assigning a weight to at least one of the plurality of queues according to a Quality of Service level for that queue.
6 . The method of claim 1 wherein at least one of the second group of the plurality of queues has a lowest priority of the plurality of queues.
7 . The method of claim 1 wherein the second group of the plurality of queues includes at least one best-efforts queue for which delivery is not assured.
8 . The method of claim 1 wherein the weight used by the first weighted round robin schedule to serve the second weighted round robin schedule is a lowest one of the weights used by the first weighted round robin schedule.
9 . The method of claim 1 wherein the first weighted round robin schedule serves a plurality of additional weighted round robin schedules.
10 . The method of claim 1 wherein the second weighted round robin schedule serves a third weighted round robin schedule.
11 . The method of claim 1 further comprising adjusting one or more weights for the first weighted round robin schedule according to a queue depth for one or more of the first group of the plurality of queues.
12 . The method of claim 1 further comprising adjusting one or more weights for the second weighted round robin schedule according to a queue depth for one or more weights of the second group of the plurality of queues.
13 . The method of claim 1 further comprising filling at least one of the number of time slots with data from a current one of the queues before moving to a next queue in the weighted round robin schedule.
14 . A computer program product comprising computer executable code that, when executing on one or more computing devices, performs the steps of:
storing a plurality of data packets in a plurality of queues for transmission in a number of time slots from a node of a mobile ad hoc network, each one of the plurality of queues having a weight;
selecting a first data packet from the plurality of data packets for transmission in one of the number of time slots according to a first weighted round robin schedule that is weighted to serve a first group of the plurality of queues according to their respective weights; and
selecting a second data packet from the plurality of data packets according to a second weighted round robin schedule that is weighted to serve a second group of the plurality of queues according to their respective weights, wherein the first weighted round robin schedule includes a weight for the second round robin schedule and periodically serves the second weighted round robin schedule according to the weight, thereby selecting the second data packet in the first weighted round robin schedule for transmission in one of the number of time slots.
15 . The computer program product of claim 14 further comprising computer executable code that performs the step of providing a prioritized queue and preemptively selecting data packets from the prioritized queue until the prioritized queue is empty.
16 . The computer program product of claim 15 further comprising computer executable code that performs the steps of:
providing a plurality of prioritized queues, each one of the prioritized queues having a priority; and
preemptively selecting data packets from the plurality of prioritized queues according to the priority until each one of the prioritized queues is empty.
17 . The computer program product of claim 15 further comprising computer executable code that performs the step of assigning a Quality of Service level to the prioritized queue, whereby data having the corresponding Quality of Service is placed into the prioritized queue and preemptively scheduled for transmission.
18 . The computer program product of claim 14 further comprising computer executable code that performs the step of assigning a weight to at least one of the plurality of queues according to a Quality of Service level for that queue.
19 . The computer program product of claim 14 wherein at least one of the second group of the plurality of queues has a lowest priority of the plurality of queues.
20 . A device comprising:
a data source that provides a plurality of data packets;
a queue that schedules the plurality of data packets for transmission according to a weighted round robin, the weighted round robin including at least one weight for a nested weighted round robin queue, the nested weighted round robin queue served according to its weight in the weighted round robin, thereby providing scheduled packets;
a radio that provides an air interface to a mobile ad hoc network including links to a plurality of neighboring nodes; and
a signal processor that prepares the scheduled packets for transmission over the air interface.