Tiered contention multiple access (TCMA): a method for priority-based shared channel access

• US 7,095,754 B2
• Filed: 11/02/2001
• Issued: 08/22/2006
• Est. Priority Date: 11/03/2000
• Status: Expired due to Term

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Benveniste, Mathilde
• Primary Examiner(s): Ton, Dang T.
• Application Number:
  US09/985,257
• Publication Number:
  US 20020163933A1
• Time in Patent Office: 1,754 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235, 370/252, 370/254, 370/389, 370/428, 370311-319, 370/442, 370/443, 370/444, 370/445, 370/448, 370/449, 370/461, 370/462, 370/458, 340/825.5
• US Class Current: 370/465
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/6275 based on priority
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/0252 per individual bearer or channel dynamic wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 56/00 Synchronisation arrangements
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 72/569 of the traffic information
• CPC Class Codes: H04W 74/02 Hybrid access
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

Quality of Service (QoS) support is provided by means of a Tiered Contention Multiple Access (TCMA) distributed medium access protocol that schedules transmission of different types of traffic based on their service quality specifications. In one embodiment, a wireless station is supplied with data from a source having a lower QoS priority QoS(A), such as file transfer data. Another wireless station is supplied with data from a source having a higher QoS priority QoS(B), such as voice and video data. Each wireless station can determine the urgency class of its pending packets according to a scheduling algorithm. For example file transfer data is assigned lower urgency class and voice and video data is assigned higher urgency class. There are several urgency classes which indicate the desired ordering. Pending packets in a given urgency class are transmitted before transmitting packets of a lower urgency class by relying on class-differentiated urgency arbitration times (UATs), which are the idle time intervals required before the random backoff counter is decreased. In another embodiment packets are reclassified in real time with a scheduling algorithm that adjusts the class assigned to packets based on observed performance parameters and according to negotiated QoS-based requirements. Further, for packets assigned the same arbitration time, additional differentiation into more urgency classes is achieved in terms of the contention resolution mechanism employed, thus yielding hybrid packet prioritization methods. An Enhanced DCF Parameter Set is contained in a control packet sent by the AP to the associated stations, which contains class differentiated parameter values necessary to support the TCMA. These parameters can be changed based on different algorithms to support call admission and flow control functions and to meet the requirements of service level agreements.

Claims

1. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

transmitting pending packets in a given urgency class before transmitting packets of a lower urgency class;

ordering pending packet transmissions according to their urgency class; and

assigning shorter arbitration times to more urgent packets;

thus restricting contention for a channel to packets that are members of the same urgency class.

2. The method for a distributed medium access protocol of claim 1, which further comprises:

classifying packets with a scheduling algorithm that assigns top urgency classification to packets of real-time traffic, medium urgency classification to isochronous traffic, and least urgency classification to best-effort traffic.

3. The method for a distributed medium access protocol of claim 1, which further comprises:

classifying packets of selected traffic types with a scheduling algorithm that advances packets with short remaining life to a higher urgency class in order to meet QoS requirements.

4. The method for a distributed medium access protocol of claim 1, which further comprises:

classifying packets with a scheduling algorithm that adjusts the class assigned to packets in real time based on observed performance parameters and according to QoS requirements.

5. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

transmitting pending packets in a given urgency class before transmitting packets of a lower urgency class;

partitioning contention between different traffic classes through specification of arbitration time duration that the channel must be sensed idle by a node following a busy period on the shared medium before backoff countdown may start.

6. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

transmitting pending packets in a given urgency class before transmitting packets of a lower urgency class;

performing real-time classification of packets to enable the protocol to be combined with a plurality of QoS-driven scheduling algorithms.

7. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

transmitting pending packets in a given urgency class before transmitting packets of a lower urgency class;

broadcasting with each transmission the number of transmission attempts by a node;

estimating from said number of transmission attempts received from other nodes a current congestion experienced; and

adjusting a backoff counter to current congestion levels to provide a dispersion of packet traffic bursts.

8. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes;

differentiating packets into additional urgency classes for packets assigned the same arbitration time; and

using different contention resolution mechanisms, thus yielding hybrid packet prioritization.

9. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before a backoff counter is decreased;

assigning shorter arbitration times to higher urgency classes;

differentiating packets into additional urgency classes for packets assigned the same arbitration time; and

using different contention resolution mechanisms, thus yielding hybrid packets prioritization.

10. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before a backoff counter is decreased;

assigning shorter arbitration times to higher urgency classes; and

differentiating packets into additional urgency classes using random backoff distribution for packets assigned the same arbitration time.

11. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes In an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes; and

said arbitration times of two different urgency classes being at least equal to an arbitration-time increment necessary for a station to discern that another station has seized a channel.

12. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before a backoff counter is decreased;

assigning shorter arbitration times to higher urgency classes; and

said arbitration times of two different urgency classes being at least equal to an arbitration-time increment necessary for a station to discern that another station has seized a channel.

13. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes; and

adjusting backoff probability functions in real time based on congestion estimates derived from a number of re-transmissions attempted by a node.

14. The method for a distributed medium access protocol of claim 13, which further comprises:

adjusting backoff probability functions in real time based on congestion estimates derived from a number of re-transmissions attempted by each of its neighbor nodes.

16. The method for a distributed medium access protocol of claim 13, which further comprises:

adjusting backoff probability functions in real time based on class-specific congestion estimates derived from a number of re-transmissions attempted by each of its neighbor nodes.

15. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes; and

adjusting backoff probability functions in real time based on class-specific congestion estimates derived from a number of re-transmissions attempted by a node.

17. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes; and

adjusting backoff probability functions in real time based on congestion estimates derived from a number of re-transmissions attempted by a node.

18. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes; and

adjusting backoff probability functions in real time at a node based on congestion estimates derived from the time spent by packets waiting for transmission.

19. The method for a distributed medium access protocol of claim 18, which further comprises:

adjusting backoff probability functions in real time at a node based on congestion estimates derived from the time spent by packets waiting for transmission at each of its neighbor nodes.

20. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes; and

adjusting backoff probability functions in real time at a node based on class-specific congestion estimates derived from the time spent by packets of different classes waiting for transmission.

21. The method for a distributed medium access protocol of claim 20, which further comprises:

adjusting backoff probability functions in real time at a node based on class-specific congestion estimates derived from the time spent by packets of different classes waiting for transmission at each of its neighbor nodes.

22. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated retrial functions that are used to update parameters of backoff distribution used following transmission failure and subsequent transmission retrial; and

using class-differentiated retrial functions that take the form of lower- and upper-coefficients multiplying the upper and lower bound of a uniform backoff distribution used following transmission failure and subsequent transmission retrial.

23. A system for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising:

a first wireless station supplied with data from a source having a low QoS priority; and

a second wireless station supplied with data from a source having a high QoS priority;

said wireless stations each determining an urgency class of its respective pending packets, the urgency classes indicating a desired ordering of transmission; and

said wireless stations transmitting pending packets in a given urgency class before transmitting packets of a lower urgency class by relying on class-differentiated urgency arbitration times (UATs), which are the idle time intervals required before a random backoff counter is decreased.

24. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising:

determining in a first wireless station a first urgency class of data having a low QoS priority;

assigning a first class-differentiated urgency arbitration time to said data having a lower QoS priority;

determining in a second wireless station a second urgency class of data having a high QoS priority;

assigning a second class-differentiated urgency arbitration time shorter than said first time, to said data having a higher QoS priority;

transmitting from said second wireless station pending packets in said second urgency class before transmitting from said first wireless station pending packets in said first urgency class;

wherein said urgency classes each have a corresponding urgency arbitration time that must expire before starting a random backoff interval for packets assigned to that urgency class; and

differentiating between different urgency class transmissions with class-specific urgency arbitration times.

25. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising:

determining in a first wireless station a first urgency class of data having a low QoS priority;

assigning a first class-differentiated urgency arbitration time to said data having a lower QoS priority;

determining in a second wireless station a second urgency class of data having a high QoS priority;

assigning a second class-differentiated urgency arbitration time shorter than said first time, to said data having a higher QoS priority;

transmitting from said second wireless station pending packets in said second urgency class before transmitting from said first wireless station pending packets in said first urgency class;

wherein said urgency classes each have a corresponding urgency arbitration time that must expire before starting a random backoff interval for packets assigned to that urgency class; and

differentiating between different urgency class transmissions with class-specific packet age limits.

26. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

transmitting pending packets in a given urgency class before transmitting packets of a lower urgency class; and

partitioning contention between different traffic classes through specification of arbitration time duration that the channel must be sensed idle by a node before decreasing a backoff counter by one time slot.

27. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required for the backoff counter to be decreased by one time slot; and

assigning shorter arbitration times to higher urgency classes.

28. The method for a distributed medium access protocol of claim 27, which further comprises:

differentiating packets into additional urgency classes using different age limits that lead to the cancellation of a transmission if the time since arrival at the MAC layer exceeds the threshold value; and

assigning shorter age limits to delay sensitive traffic classes.

29. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes;

differentiating packets into additional urgency classes for packets assigned the same arbitration time; and

using different persistence probabilities as a contention resolution mechanism to distribute packet transmission times.

30. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes;

differentiating packets into additional urgency classes for packets assigned the same arbitration time; and

using different backoff distributions as a contention resolution mechanism to distribute packet transmission times.

31. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes;

differentiating packets into additional urgency classes for packets assigned the same arbitration time; and

using ALOHA protocol as a contention resolution mechanism to distribute packet transmission times.

32. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

determining at a plurality of nodes in an access network, an urgency class of pending packets according to a scheduling algorithm;

using class-differentiated arbitration times, as idle time intervals required before transmission is attempted following a busy period on a medium;

assigning shorter arbitration times to higher urgency classes;

differentiating packets into additional urgency classes for packets assigned the same arbitration time; and

using CSMA/CD protocol as a contention resolution mechanism to distribute packet transmission times.

33. A method for a distributed medium access protocol that schedules transmission of different types of packets on a channel based on a service quality specification for each type of packet, comprising the steps of:

broadcasting a parameter set in a management packet sent from an Access Point to associated stations, the parameter set containing the values of class differentiating parameters, such as urgency arbitration times, contention windows, persistence factors, and packet age limits, necessary to support Tiered Contention Multiple Access; and

adjusting such class-differentiating parameter values under the direction of an algorithm at the Access Paint or at a central controller coordinating several Access Points.

34. The method for a medium access protocol of claim 33, which further comprises:

adjusting such class-differentiating parameters to implement algorithms for flow control.

35. The method for a medium access protocol of claim 33, which further comprises:

adjusting such class-differentiating parameter values for call admission purposes.

36. The method for a medium access protocol of claim 33, which further comprises:

adjusting such class-differentiating parameter values to deliver quality of service as specified by Service Level Agreements.