Random medium access methods with backoff adaptation to traffic

• US 7,027,462 B2
• Filed: 01/02/2002
• Issued: 04/11/2006
• Est. Priority Date: 01/02/2001
• Status: Expired due to Fees

• 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:
  US10/032,507
• Publication Number:
  US 20020154653A1
• Time in Patent Office: 1,560 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/447
• CPC Class Codes: H04L 12/4013 Management of data rate on the bus systems modifying transmission characteristics according to link quality H04L1/0001
• CPC Class Codes: H04L 12/4015 by scheduling the transmission of messages at the communication node
• 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/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: H04W 28/0231 based on communication conditions dynamic wireless traffic scheduling definition based on channel quality criteria H04W72/54
• CPC Class Codes: H04W 28/0284 detecting congestion or overload during communication monitoring arrangements H04L43/00
• CPC Class Codes: H04W 56/00 Synchronisation arrangements
• CPC Class Codes: H04W 72/54 based on quality criteria
• CPC Class Codes: H04W 72/569 of the traffic information
• CPC Class Codes: H04W 74/02 Hybrid access
• CPC Class Codes: H04W 74/0841 with collision treatment
• CPC Class Codes: H04W 74/085 collision avoidance
• 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

Using low PF values in conjunction with traffic-adapted contention windows leads to substantial decreases in delay and jitter. In general, adaptation to traffic reduces contention or delay: opening up the contention window in congestion and closing it on relief. Residual backoff adaptation provides for the reduction of the already decremented backoff values of stations that interrupted the backoff countdown process due to a transmission. It is good to adapt both the contention window and the residual backoff in order to avoid jitter. Otherwise, if the contention window is reduced but residual backoffs stay unchanged, new arrivals will enjoy shorter backoff delays than older ones, resulting in greater jitter. Adjusting both preserves the relative ordering of backoff counter values, which implies also some form of age ordering. Different adjustments can be applied to different priority traffic.

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;

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

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

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

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

2. 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;

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

remembering the number of transmission attempts for packets of every urgency class by a node for the last transmission in that class of same node;

estimating from said number of transmission attempts the current congestion experienced by the urgency class of a pending packet; and

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

3. 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;

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

broadcasting with each transmission the number of transmission attempts by a node arid the assigned urgency class;

estimating from said number of transmission attempts received from other nodes the current congestion experienced by the urgency class of the pending packet; and

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

4. 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;

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

broadcasting with each transmission the number of transmission attempts by a node and the assigned urgency class;

estimating from said number of transmission attempts received from other nodes the current congestion experienced by the urgency class of the pending packet; and

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

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;

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

initializing backoff counters with a relatively longer value, and then decreasing the value upon transmission failure and retrial.

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;

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts the current congestion experienced; and

adjusting a persistence probability to current congestion levels to provide a dispersion of packet traffic bursts.

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;

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

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

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

adjusting a persistence probability 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;

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

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

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

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

adjusting a persistence probability to current congestion levels to provide a dispersion of packet traffic bursts.

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;

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

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

remembering the number of transmission attempts for packets of every urgency class by a node for the last transmission in that class of same node;

estimating from said number of transmission attempts the current congestion experienced by the urgency class of a pending packet; and

adjusting a persistence probability for the pending packet to current congestion levels to provide a dispersion of packet traffic bursts.

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;

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

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

broadcasting with each transmission the number of transmission attempts by a node and the assigned urgency class;

estimating from said number of transmission attempts received from other nodes the current congestion experienced by the urgency class of the pending packet; and

adjusting a persistence probability of the pending packet to current congestion levels to provide a dispersion of packet traffic bursts.

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;

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

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

broadcasting with each transmission the number of transmission attempts by a node and the assigned urgency class;

estimating from said number of transmission attempts received from other nodes the current congestion experienced by the urgency class of the pending packet; and

adjusting a persistence probability of the pending packet to current congestion levels to provide a dispersion of packet traffic bursts.

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;

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

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

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

initializing a persistence probability with a relatively lower value, and then increasing the value upon transmission failure and retrial.

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;

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

remembering the number of transmission attempts by a node for the last transmission of same node;

estimating from said number of transmission attempts a current congestion experienced;

adjusting a backoff counter to current congestion revels to provide a dispersion of packet traffic bursts; and

establishing criteria for cancellation of transmission of a packet associated with packet delay.

14. A method for a medium access protocol that schedules transmission of packets from a plurality of nodes on a channel, comprising the steps of:

employing a backoff countdown procedure for channel access;

monitoring traffic intensity changes continuously and providing feedback to the MAC sublayer of contending nodes;

adjusting a backoff counter of each of a plurality of contending nodes to current congestion levels in time intervals shorter than required for the completion of a transmission attempt;

adjusting such backoff counter in a way that enables older packets to be transmitted before newer ones with high probability, thus minimizing a latency jitter;

adjusting such backoff counter in a way that their relative ordering is preserved;

determining the magnitude of an adjustment factor that is larger for greater congestion;

adjusting a backoff counter of the pending packet to increased congestion levels by increasing the backoff counter values associated with each of a plurality of contending nodes by scaling up such counter through the addition of an increment that is proportional to the current counter value and increases with the scaling factor; and

adding a random integer number drawn from a range bounded by 0 and said adjustment factor.

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

selecting the magnitude of the adjustment factor at a given congestion level so that it is smaller for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.

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

selecting the magnitude of the adjustment factor at a given congestion level so that it is smaller for nodes subscribing to a higher premium service, thus enabling higher premium packets to be transmitted earlier.

15. A method for a medium access protocol that schedules transmission of packets from a plurality of nodes on a channel, comprising the steps of:

employing a backoff countdown procedure for channel access;

monitoring traffic intensity changes continuously and providing feedback to the MAC sublayer of contending nodes;

adjusting a backoff counter of each of a plurality of contending nodes to current congestion levels in time intervals shorter than required for the completion of a transmission attempt;

adjusting such backoff counter in a way that enables older packets to be transmitted before newer ones with high probability, thus minimizing a latency jitter;

adjusting such backoff counter in a way that their relative ordering is preserved;

determining the magnitude of an adjustment factor that is larger for lower congestion; and

adjusting a backoff counter of the pending packet to decreased congestion levels by decreasing the backoff counter values associated with each of a plurality of contending nodes by scaling down in inverse proportion to said scaling factor.

17. The method for a medium access protocol of claim 15, which further comprises:

selecting the magnitude of the adjustment factor at a given congestion level so that it is greater for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.

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

selecting the magnitude of the adjustment factor at a given congestion level so that it is greater for nodes subscribing to a higher premium service, thus allowing higher premium packets to be transmitted earlier.

20. A method for a medium access protocol that schedules transmission of packets from a plurality of nodes on a channel, comprising the steps of:

employing a backoff countdown procedure for random channel access;

monitoring traffic continuously and providing feedback to the MAC sublayer of contending nodes;

adjusting at least one parameter of a random distribution from which a backoff counter is drawn upon initiation of a transmission attempt for each of a plurality of contending nodes to reflect current congestion levels;

determining the magnitude of an adjustment factor R that is larger for greater contention levels; and

adjusting the backoff distribution parameters to increased contention levels by increasing parameter values associated with each of a plurality of contending nodes by scaling up such parameters through the addition of an increment that is proportional to a current counter value and increases with the scaling factor (1+R).

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

while monitoring the contention levels, performing a scaling adjustment when its magnitude exceeds a specified step size, thus maintaining responsive adjustment with an efficient computation load.

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

selecting the magnitude of the adjustment factor at a given contention level so that it is smaller for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.

21. A method for a medium access protocol that schedules transmission of packets from a plurality of nodes on a channel, comprising the steps of:

employing a backoff countdown procedure for random channel access;

monitoring traffic continuously and providing feedback to the MAC sublayer of contending nodes;

adjusting at least one parameter of a random distribution from which a backoff counter is drawn upon initiation of a transmission attempt for each of a plurality of contending nodes to reflect current congestion levels;

determining the magnitude of an adjustment factor D that is larger for lower contention levels; and

adjusting the backoff distribution parameters to decreased contention levels by decreasing such parameters associated with each of a plurality of contending nodes by scaling down in inverse proportion to the scaling factor (1+D).

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

while monitoring the contention levels, performing a scaling adjustment when its magnitude exceeds a specified step size, thus maintaining responsive adjustment with an efficient computation load.

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

selecting the magnitude of the adjustment factor at a given contention level so that it is greater for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.

22. A method for a medium access protocol that schedules transmission of packets from a plurality of nodes on a channel, comprising the steps of:

employing a backoff countdown procedure for random channel access;

monitoring traffic continuously and providing feedback to the MAC sublayer of contending nodes;

adjusting at least one parameter of a random distribution from which a backoff counter is drawn upon initiation of a transmission attempt for each of a plurality of contending nodes to reflect current congestion levels;

adjusting a backoff counter of each of a plurality of backlogged nodes to reflect current contention levels in time intervals shorter than required for the completion of a transmission attempt;

adjusting such backoff counters in a way that enables older packets to be transmitted before newer ones with high probability, thus minimizing the latency jitter; and

adjusting such backoff counter in a way that their relative ordering is preserved.

23. The method for a medium access protocol of claim 22, which further comprises:

determining the magnitude of an integer adjustment factor R that is larger for greater contention levels;

adjusting a backoff counter of the pending packet to increased contention levels by increasing the backoff counter values associated with each of a plurality of backlogged nodes by scaling up such counter through the addition of an increment that is proportional to the current counter value and increases with the scaling factor (1+R); and

adding a random integer number drawn from a range bounded by 0 and said adjustment factor R.

25. The method for a medium access protocol of claim 22, which further comprises:

determining the magnitude of an integer adjustment factor D that is larger for lower contention levels; and

adjusting a backoff counter of the pending packet to decreased contention levels by decreasing the backoff counter values associated with each of a plurality of backlogged nodes by scaling down in inverse proportion to the scaling factor (1+D).

26. The method for a medium access protocol of claim 22, which further comprises:

determining the magnitude of a fractional adjustment factor D that is larger for lower congestion;

adjusting a backoff counter of the pending packet to increased contention levels by increasing the backoff counter values associated with each of a plurality of backlogged nodes by scaling down such counter through a multiplication of the current counter value by a term that increases in inverse proportion to the scaling factor (1+D); and

assigning, through statistical means, an integer value to such counter with expected value equal to a multiplication product resulting from said multiplication.

29. The method for a medium access protocol of claim 23, which further comprises:

while monitoring the contention levels, performing a scaling adjustment when its magnitude exceeds a specified step size, thus maintaining responsive adjustment with an efficient computation load.

32. The method for a medium access protocol of claim 23, which further comprises:

selecting the magnitude of the adjustment factor at a given contention level so that it is smaller for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.

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

selecting the magnitude of the adjustment factor at a given contention level so that it is greater for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.

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

selecting the magnitude of the adjustment factor at a given contention level so that it is greater for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.

24. The method for a medium access protocol of 22, which further comprises:

determining the magnitude of a fractional adjustment factor R that is larger for greater contention levels;

adjusting a backoff counter of the pending packet to increased contention levels by increasing the backoff counter values associated with each of a plurality of backlogged nodes by scaling up such counter through a multiplication of the current counter value by a term that increases with the scaling factor (1+R); and

assigning, through statistical means, an integer value to such counter with expected value equal to a multiplication product resulting from said multiplication.

30. The method for a medium access protocol of claim 24, which further comprises:

while monitoring the contention levels, performing a scaling adjustment when its magnitude exceeds a specified step size, thus maintaining responsive adjustment with an efficient computation load.

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

selecting the magnitude of the adjustment factor at a given contention level so that it is smaller for higher priority nodes, thus allowing higher priority packets to be transmitted earlier.