Implementing enhanced distributed coordinating function (EDCF) with a single hardware backoff counter

• US 20030145095A1
• Filed: 01/31/2002
• Published: 07/31/2003
• Est. Priority Date: 01/31/2002
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Shoemake, Matthew B., Liu, Yonghe, Schrum, Sid B.
• Granted Patent: US 7,133,422 B2
• Time in Patent Office: Days
• US Class Current: 709/230
• CPC Class Codes: H04L 12/40143 involving priority mechanisms hybrid switching fabrics H04L12/6402; intermediate storage or scheduling H04L49/90; time-division multiplex systems H04J3/00
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 74/085 collision avoidance
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method for implementing a plurality of backoff counters 230 on a hardware backoff counter 210 for use in implementing a prioritized message transmission network is presented. A message with a smallest backoff time is selected and placed into the hardware backoff counter 210. When the hardware backoff counter 210 expires, the message is transmitted. Whenever the communications medium becomes busy, the backoff time for every message is updated.

Claims

1. A method for contending for access to a communications medium to transmit a message of a first traffic category in a system implementing a plurality of backoff counters using a single hardware backoff counter comprising:

(1) determining if the hardware backoff counter is idle;

(2) initiating a backoff procedure for the message if the hardware backoff counter is idle;

(3) if the hardware backoff counter is busy, then;

generating a backoff time for the first traffic category;

comparing the backoff time for the first traffic category with a backoff time for a second traffic category in the hardware backoff counter; and

determining a backoff procedure based on the results of the comparison.

2. The method of claim 1, wherein each traffic category has a backoff counter, and wherein the method further comprising:

(4) if the communications medium is busy, then

updating the values in each virtual backoff counter;

selecting a message from a traffic category with a smallest backoff counter;

initiating a backoff procedure based on the selected the traffic category with the smallest backoff counter.

3. The method of claim 2, further comprising the step of (5) repeating steps (1)-(4).

4. The method of claim 2, wherein the updating step occurs when the communications medium is busy.

5. The method of claim 1, wherein the second determining step comprising:

if the backoff time for the first traffic category is greater than the backoff time in the hardware backoff timer, then;

waiting until the hardware backoff counter expires; and

initiating a new first backoff procedure for the first traffic category;

if the backoff time for the first traffic category is equal to the backoff time in the hardware backoff timer, then;

waiting until the hardware backoff counter expires; and

initiating an enhanced distributed coordinating function (EDCF) collision procedure;

if the backoff time for the first traffic category is less than the backoff time in the hardware backoff timer, then;

saving the contents of the hardware backoff counter; and

initiating a new second backoff procedure for the first traffic category.

6. The method of claim 5, wherein the step of initiating the new first backoff procedure for the first traffic category comprising:

determining a backoff time for the first traffic category;

loading the backoff time into the hardware backoff counter; and

starting the hardware backoff counter.

7. The method of claim 6, wherein the backoff time is equal to the generated backoff time for the first traffic category minus the waiting time for the hardware backoff counter to expire while second traffic category occupies the hardware backoff counter.

8. The method of claim 5, wherein the step of initiating the new first backoff procedure for the first traffic category comprising:

determining a contention window size for the first traffic category;

loading the contention window size into the hardware backoff counter; and

starting the hardware backoff counter.

9. The method of claim 8, wherein the contention window size is equal to the generated backoff time for the first traffic category minus the waiting time for the hardware backoff counter to expire while second traffic category occupies the hardware backoff counter.

10. The method of claim 5, wherein the EDCF collision procedure comprising:

selecting a traffic category of higher priority from the group comprising the first and the second traffic categories;

allowing the selected traffic category to transmit; and

generating a new backoff procedure for the unselected traffic category with a contention window doubled in size.

11. The method of claim 5, wherein the step of initiating the new second backoff procedure for the first traffic category comprising:

determining a backoff time for the first traffic category;

loading the backoff time into the hardware backoff counter; and

starting the hardware backoff counter.

12. The method of claim 11, wherein the backoff time is equal to generated backoff time for the first traffic category.

13. The method of claim 5, wherein the step of initiating the new first backoff procedure for the first traffic category comprising:

determining a contention window size for the first traffic category;

loading the contention window size into the hardware backoff counter; and

starting the hardware backoff counter.

14. The method of claim 13, wherein the contention window size is equal the backoff time for the second traffic category.

15. The method of claim 5 further comprising the step of selecting a next traffic category to occupy the hardware backoff counter.

16. The method of claim 15, wherein a backoff counter value is stored for each traffic category, and the selecting step comprising:

selecting the traffic category with the backoff counter value that is smallest; and

initiating a backoff procedure for the selected traffic category.

17. The method of claim 16, wherein the step of initiating the backoff procedure comprises loading the hardware counter with a backoff time that is equal to the backoff counter value that is second smallest in size.

18. The method of claim 16, wherein the step of initiating the backoff procedure comprises loading the hardware backoff counter with a contention window of size equal to the backoff counter value that is second smallest in size.

19. The method of claim 18, wherein if the selected traffic category is the only traffic category with a non-zero backoff counter value, then the hardware backoff counter is loaded with contention window of size equal to the backoff counter value of the selected traffic category.

20. The method of claim 5, wherein the step of saving the contents of the hardware backoff counter comprises saving the backoff timer and the messageto a backoff timer for the traffic category corresponding to the message in the hardware backoff timer.

21. The method of claim 5, wherein the backoff times for each traffic category include the arbitration interframe space (AIFS) time associated with each traffic category.

22. A method for implementing a plurality of backoff counters using a single hardware backoff counter comprising:

determining a state of the hardware backoff counter;

if the hardware backoff counter is performing a backoff procedure, then;

determining a state of a communications medium;

if the communications medium is idle, then

decrementing a value in the hardware backoff counter;

if the value is equal to zero, then allow transmission to occur;

if the communications medium is busy, then updating a value in each backoff counter;

selecting a backoff counter with a smallest value;

moving the selected backoff counter to the hardware backoff counter; and

initiating a new backoff procedure with the hardware backoff counter.

23. The method of claim 22, wherein the decrementing step comprises decrementing the value in the hardware backoff counter only if the communications medium has been idle a period of time at least equal to an arbitration interframe space (AIFS) and the communications medium has been idle for a network cycle since the last time it was decremented.

24. The method of claim 23, wherein there are a plurality of traffic categories, and wherein each traffic category may have a different value for the AIFS.

25. The method of claim 22, further comprising the step of repeating until stopped.

26. The method of claim 22, wherein the updating step comprises:

determining a period of time between a start of the backoff procedure currently in the hardware backoff counter and a current time; and

subtracting the period of time from each backoff counter.

27. The method of claim 26, wherein the backoff counter is set to zero if the subtraction produces a result that is negative.

28. The method of claim 22, wherein there are a plurality of traffic categories and each traffic category has a backoff counter, and wherein the moving step comprises:

moving a backoff counter value and a message from the hardware backoff counter to a backoff counter for the traffic category of the message in the hardware backoff counter; and

moving a backoff counter value and a message from the selected backoff counter to the hardware backoff counter.

29. The method of claim 28, wherein if the selected backoff counter is the hardware backoff counter, then the moving step does not actually move any counter values and messages.

30. B5. The method of claim 22, wherein the selecting step selects the backoff counter with the smallest backoff counter from all backoff counters, including the hardware backoff counter.

31. The method of claim 22, wherein the initiating step comprises:

determining a backoff time; and

starting the backoff timer.

32. The method of claim 31, wherein the backoff time is equal to the backoff timer value plus an arbitration interframe space of the selected backoff timer.

33. The method of claim 31, wherein the backoff time is specified by a contention window of a size equal to the backoff timer value of a traffic category with a second smallest backoff timer value plus an arbitration interframe space of the selected backoff timer.

34. The method of claim 33, wherein the contention window is provided to the hardware backoff timer and the hardware backoff timer randomly selects a backoff time from within an interval specified by the contention window.

35. A circuit for implementing a plurality of backoff counters on a hardware backoff counter comprising:

a hardware backoff counter containing circuitry to decrement a backoff time once for each idle network cycle;

a memory coupled to the hardware backoff counter, the memory containing storage locations that contain a virtual backoff counter, an arbitration interframe space, and a information queue for each backoff counter; and

a processor coupled to the hardware backoff counter and the memory, the processor containing circuitry to implement a plurality of backoff counters on a hardware backoff counter, the processor comprising;

an initial transmit hardware enqueue unit coupled to the hardware backoff counter, the initial transmit hardware enqueue unit containing circuitry to forward a transmission request to the hardware backoff counter depending on the status of the hardware backoff counter;

a generate new virtual backoff unit coupled to the initital transmit hardware enqueue unit and the memory, the generate new virtual backoff unit containing circuitry to generate virtual backoff times and to place the transmission request forwarded to it by the initial transmit hardware enqueue unit onto a queue;

an adjust virtual backoff counters unit coupled to the memory and the hardware backoff counter, the adjust virtual backoff counters unit containing circuitry to adjust the backoff times in the virtual backoff counters; and

a select and enqueue transmit frame unit coupled to the coupled to the memory and the hardware backoff counter, the select and enqueue frame unit containing circuitry to select a transmission request with the lowest backoff time and to place it in the hardware backoff counter.

36. The circuit of claim 35, wherein the hardware backoff counter permits direct writes to its backoff counter.

37. The circuit of claim 35, wherein the hardware backoff counter permits specification of a contention window size.

38. A network station comprising a circuit for implementing a plurality of backoff counters on a hardware backoff counter, the circuit comprising:

a hardware backoff counter containing circuitry to decrement a backoff time once for each idle network cycle;

a memory coupled to the hardware backoff counter, the memory containing storage locations that contain a virtual backoff counter, an arbitration interframe space, and a information queue for each backoff counter; and

a processor coupled to the hardware backoff counter and the memory, the processor containing circuitry to implement a plurality of backoff counters on a hardware backoff counter, the processor comprising;

an initial transmit hardware enqueue unit coupled to the hardware backoff counter, the initial transmit hardware enqueue unit containing circuitry to forward a transmission request to the hardware backoff counter depending on the status of the hardware backoff counter;

a generate new virtual backoff unit coupled to the initital transmit hardware enqueue unit and the memory, the generate new virtual backoff unit containing circuitry to generate virtual backoff times and to place the transmission request forwarded to it by the initial transmit hardware enqueue unit onto a queue;

an adjust virtual backoff counters unit coupled to the memory and the hardware backoff counter, the adjust virtual backoff counters unit containing circuitry to adjust the backoff times in the virtual backoff counters; and

a select and enqueue transmit frame unit coupled to the coupled to the memory and the hardware backoff counter, the select and enqueue frame unit containing circuitry to select a transmission request with the lowest backoff time and to place it in the hardware backoff counter.

39. The network station of claim 38, wherein the network station is part of a wireless communications network.

40. The network station of claim 38, wherein the network station is part of a hybrid wireless and wired communications network.