Nested weighted round robin queuing

This application claims the benefit of the following U.S. Provisional Patent Applications, each of which is incorporated by reference herein in its entirety:

U.S. App. No. 60/976,730 filed on Oct. 1, 2007;

U.S. App. No. 60/976,735 filed on Oct. 1, 2007;

U.S. App. No. 60/976,740 filed on Oct. 1, 2007;

U.S. App. No. 60/976,744 filed on Oct. 1, 2007;

U.S. App. No. 60/976,747 filed on Oct. 1, 2007; and

U.S. App. No. 60/976,748 filed on Oct. 1, 2007.

This invention was made with support of the United States Government under Contract MDA972-01-9-0022. The United States Government may have certain rights in the invention.

This application relates to queuing data for transmission in a Mobile Ad Hoc Network (MANET), and more particularly to queuing prioritized data according to a weighted nested round robin queue. There remains a need for improved handling of multiple traffic types in a wireless ad hoc network.

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.

In one aspect, there is disclosed herein a method that includes 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. The method may include preemptively selecting data packets from a prioritized queue until the prioritized queue is empty.

In another aspect, a computer program product disclosed herein include 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.

In another aspect, a device disclosed herein includes 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.