Air-time fair transmission regulation without explicit traffic specifications for wireless networks

• US 9,215,621 B2
• Filed: 11/16/2005
• Issued: 12/15/2015
• Est. Priority Date: 11/22/2004
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips N.V.
• Inventors: Chen, Yingwei, Chen, Richard, Schmitt, Ruediger, Nandagopalan, Saishankar
• Primary Examiner(s): Jagannathan, Melanie
• Application Number:
  US11/719,774
• Publication Number:
  US 20090147765A1
• Time in Patent Office: 3,681 Days
• Field of Search: 370/412, 370/79, 370/229, 370/329, 370/468, 340/825, 395/200
• US Class Current: 1/1
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04W 28/14 using intermediate storage

Abstract

A system and method are provided for non-transmission specification fair air-time, NT-AirFair, allocation control by tracking the transmission time (308) consumed by each link to detect any increase and enforcing air -time allocation (309) based on the pattern of usage derived therefrom.

Claims

1. An apparatus for non-TSPEC (traffic specification) air-time fair transmission control regulation, comprising:

a memory comprising n queues having corresponding pre-determined scheduling weights q_i,old=q_i,new, i=1, 2, . . . , n, where n is an integer more than 1;

a queue-level scheduler to enqueue a received packet and dequeue for transmission an enqueued packet of at least one flow in a queue of said n queues respectively according to a pre-determined queue allocation scheme and a weighted transmission scheduling scheme using said weights q_i,new, i=1, 2, . . . , n; and

a time monitor module to track at least a per-byte transmission time of at least one of the n queues and to determine for determining if there is an increase in a transmission time per byte T _i,t,j for each queue of said at least one flow enqueued therein and adjusting the corresponding scheduling weights q_i,new, i=1, 2, . . . , n according to a pre-determined weight adjustment scheme if the per-byte transmission time of the at least one of the n queues exceeds a threshold.

2. The apparatus of claim 1, further comprising:

a priority-based MAC;

said queue-level scheduler is contained in one of the components selected from a group consisting of a queuing module of an operating system kernel, a device driver, and a MAC; and

wherein delay-sensitive traffic flows per flow category are enqueued in a separate queue per flow by the queue-level scheduler.

3. The apparatus of claim 1, wherein the time monitor computes T,_i,j as a window-averaged transmission time per byte for a pre-determined window size t.

4. The apparatus of claim 1, wherein said allocation scheme comprises enqueuing each delay-sensitive flow in a separate queue of said n queues.

5. The apparatus of claim 4, wherein the time monitor computes T,_i,j as a window-averaged transmission time per byte for a pre-determined window size t.

6. The apparatus of claim 1, wherein said allocation scheme comprises enqueuing all non-delay-sensitive flows in a single separate queue of said n queues.

7. The apparatus of claim 6, wherein the time monitor computes T,_i,j as a window-averaged transmission time per byte for a pre-determined window size t.

8. The apparatus of claim 1,

wherein said allocation scheme comprises enqueuing each delay-sensitive flow and all non-delay-sensitive flows in a separate queue of said n queues,

wherein the time monitor computes T,_i,j as a window-averaged transmission time per byte for a pre-determined window size t, and

wherein the weighted transmission scheduling scheme is selected from a group consisting of weighted round-robin and weighted fair queuing.

9. The apparatus of claim 8, wherein

T,_i,j=transmission_time_consumed/packet_size, for j=1, 2, . . . , and i=1, . . . , n;

and

the pre-determined weight adjustment scheme obtains a sequence T,_i,j for j=1, . . . k over the window t and, if this sequence increases, on a window-averaged basis by more than a pre-determined threshold, adjusts the queue weight inversely proportionally to the increase.

10. The apparatus of claim 9, wherein the queue weight is adjusted according to the formula:

q_i,new=q_i,old*(T_i,old/T_i,new).

11. The apparatus of claim 9, wherein the pre-determined weight adjustment scheme further comprises an adjustment to the retry limit for the flow and determination of a minimum PHY rate under the adjusted retry limit.

12. The apparatus of claim 11, wherein the pre-determined weight adjustment scheme further comprises setting TXOP to a pre-determined allowed airtime.

13. The apparatus of claim 11, wherein the adjustment is selected from a group consisting of lowering the retry limit by a pre-determined lowering amount and setting the retry limit to 0.

14. The apparatus of claim 13, wherein the pre-determined weight adjustment scheme further comprises setting TXOP to a pre-determined allowed airtime, and wherein the apparatus is selected from a group consisting of an IEEE 802.11 wireless local area network (LAN) integrated circuit (IC), a wireless personal area network (PAN) IC, a wireless video server, a wireless video receiver, a wireless media adapter, a media personal computer (PC), and a wireless video transmission module.

15. A communications network for non-TSPEC (traffic specification) air-time fair transmission control regulation comprising a plurality of devices each including an apparatus according to claim 14.

16. A method for non-TSPEC (traffic specification) air-time fair transmission control regulation, comprising:

providing n queues each having a corresponding pre-determined scheduling weight qi, old=qi, new, i=1, 2, . . . , n, where n is an integer more than 1;

enqueuing a received packet of at least one flow in a separate queue of said n queues according to a pre-determined queue allocation scheme;

dequeuing for transmission an enqueued packet in accordance with a weighted transmission scheduling scheme using said weights qi, new, i=1, 2, . . . , n;

tracking at least a per-byte transmission time of at least one of the n queues;

determining if there is an increase in a transmission time per byte Tij for each queue;

and

adjusting the corresponding scheduling weights qi, new, i=1, 2, . . . , n according to a predetermined weight adjustment scheme if the per-byte transmission time of the at least one of the n queues exceeds a threshold.

17. The method of claim 16, further comprising:

providing a priority-based MAC; and

the enqueuing further comprises enqueuing delay-sensitive traffic flows per flow category in a separate queue per flow in one of the components selected from a group consisting of a queuing module of an operating system kernel, a device driver, and a MAC.

18. The method of claim 16, wherein the determining further comprises computing T_i,j as a window-averaged transmission time per byte for a pre-determined window size t.

19. The method of claim 16, wherein said queue allocation scheme comprises allocating each delay-sensitive flow to a separate queue of said n queues.

20. The method of claim 19, wherein the determining further comprises computing T_i,j as a window-averaged transmission time per byte for a pre-determined window size t.

21. The method of claim 16, wherein said queue allocation scheme comprises allocating all non-delay-sensitive flows to a single separate queue of said n queues.

22. The method of claim 21, wherein the determining further comprises computing T_i,j as a window-averaged transmission time per byte for a pre-determined window size t.

23. The method of claim 16, wherein said allocation scheme comprises:

allocating each delay-sensitive flow to a separate queue of said n queues; and

allocating all non-delay-sensitive flows to a separate queue of said n queues.

24. The method of claim 23, wherein the determining further comprises computing T_i,jas a window-averaged transmission time per byte for a pre-determined window size t.

25. The method of claim 23, wherein

the weighted transmission scheduling scheme is selected from a group consisting of weighted round-robin and weighted fair queuing, and

T_i,t,j=transmission_time_consumed/packet_size, for j=1, 2, . . . , and i=1, . . . , n;

and

the pre-determined weight adjustment scheme comprises;

i. obtaining a sequence T_i,j for j=1, . . . , k over the window t; and

ii. determining if the obtained sequence increases, on a window-averaged basis by more than a pre-determined threshold; and

iii. when the increase exceeds the threshold, adjusting the queue weight inversely proportionally to the increase.

26. The method of claim 25, wherein the adjusting the queue weight uses the formula:

qi, new=qi, old (Ti, old/Ti, new).

27. The method of claim 25, wherein the pre-determined weight adjustment scheme further comprises:

adjusting the retry limit; and

determining a minimum PHY rate under the adjusted retry limit.

28. The method of claim 27, wherein the pre-determined weight adjustment scheme further comprises setting TXOP to a pre-determined allowed airtime.

29. The method of claim 27, wherein the adjusting the retry limit comprises selecting an adjustment from a group consisting of lowering the retry limit by a pre-determined lowering amount and setting the retry limit to 0.

30. The method of claim 29, wherein the pre-determined weight adjustment scheme further comprises setting TXOP to a pre-determined allowed airtime.