Adaptive contention algorithm based on truncated binary exponential back-off

• US 6,801,537 B1
• Filed: 09/07/2000
• Issued: 10/05/2004
• Est. Priority Date: 09/07/2000
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Kubbar, Osama M.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Wilson, Robert W.
• Application Number:
  US09/657,155
• Time in Patent Office: 1,489 Days
• Field of Search: 370/352, 370/252, 370/420, 370/421, 370/486, 370/489, 370/490, 370/493, 370/442, 375/222, 725/111, 725/112, 725/113, 725/109, 725/110, 725/114
• US Class Current: 370/442
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 74/085 collision avoidance

Abstract

A method of adaptively resolving contentions in a digital communication system is provided. A headend, such as a Base station Transceiver System, transmits a Media Access Control message to Customer Premise Equipment units. The Media Access Control message includes information on the current load on shared transmission resources. The Customer Premise Equipment units implement a truncated binary exponential back-off algorithm for requests. However if the current load on the transmission resources is low enough, the Customer Premise Equipment units reduce the back-off times of backlogged requests to allow them to take advantage of the low load. The headend may also maintain a table of service flows and their levels of activity. If the level of activity at shared transmission resources falls below a threshold, the headend determines from the table which service flows are likely to have backlogged requests. The headend transmits a unicast-type signal identifying the service flow, and the Customer Premise Equipment unit managing the identified service flow transmits the backlogged request.

Claims

1. In a digital communication system, a method of resolving contention between a plurality of requests arriving at a headend from at least one Customer Premises Equipment unit (CPE), the method comprising the steps of:

transmitting a Bandwidth Allocation Map (MAP) message from the headend to each CPE, the MAP message including zero or more acknowledgments and a previous contention period load;

reading the acknowledgements and the previous contention period load, upon arrival of the MAP message at each CPE;

generating an offset for each request for which an acknowledgement does not exist in the MAP message, using a contention resolution algorithm; and

if the previous contention period load is below a threshold, reducing an offset for zero or more requests for which an offset had previously been generated.

2. The method of claim 1 wherein the previous contention period load is an estimate of a rate at which the headend is receiving requests.

3. The method of claim 2 wherein the previous contention period load is defined as a number of requests which are received at the headend since a previous MAP message was transmitted, divided by a contention window size of the previous MAP message.

4. The method of claim 1 wherein the contention resolution algorithm is a truncated binary exponential back-off algorithm.

5. The method of claim 4 wherein the digital communication system is a fixed wireless access communication system.

6. The method of claim 4 wherein the digital communication system is a mobile communication system.

7. The method of claim 4 wherein the digital communication system is a cable television communication system.

8. The method of claim 1 wherein the digital communication system is a fixed wireless access communication system.

9. The method of claim 1 wherein the digital communication system is a mobile communication system.

10. The method of claim 1 wherein the digital communication system is a cable television communication system.

11. A headend for a digital communication system, the headend comprising a message creator arranged to create a Bandwidth Allocation Map (MAP) message and means arranged to transmit the MAP message to at least one Customer Premises Equipment unit (CPE), wherein the MAP message includes:

zero or more acknowledgements; and

a previous contention period load.

12. The headend of claim 11 wherein the headend receives at least one request from the at least one CPE, and the previous contention period load is an estimate of a rate at which the headend is receiving requests.

13. The headend of claim 12 wherein the previous contention period load is defined as a number of requests which are received at the headend since a previous MAP message was transmitted, divided by a contention window size of the previous MAP message.

14. The headend of claim 12 wherein the headend is a Base station Transceiver System within a fixed wireless access communication system.

15. The headend of claim 12 wherein the headend is a Base station Transceiver System within a mobile communication system.

16. The headend of claim 12 wherein the headend is a Cable Modem Termination System within a cable television communication system.

17. The headend of claim 11 wherein the headend is a Base station Transceiver System within a fixed wireless access communication system.

18. The headend of claim 11 wherein the headend is a Base station Transceiver System within a mobile communication system.

19. The headend of claim 11 wherein the headend is a Cable Modem Termination System within a cable television communication system.

20. A Customer Premises Equipment (CPE) unit for a digital communication system, the CPE unit including a contention resolution processor and transmitting requests to a headend, the contention resolution processor including instructions for:

reading zero or more acknowledgements and a previous contention period load from a Bandwidth Allocation Map (MAP) message transmitted by the headend;

generating an offset for each request for which an acknowledgement does not exist in the MAP message, using a contention resolution algorithm; and

reducing an offset for zero or more requests for which an offset had previously been generated, in the event that the previous contention period load is below a threshold.

21. The CPE unit of claim 20 wherein the previous contention period load is an estimate of a rate at which the headend is receiving requests from the CPB unit and from zero or more additional CPE units.

22. The CPE unit of claim 21 wherein the previous contention period load is defined as a number of requests from the CPE unit and from zero or more additional CPE units which are received at the headend since a previous MAP message was transmitted, divided by a contention window size of the previous MAP message.

23. The CPE unit of claim 20 wherein the contention resolution algorithm is a truncated binary exponential back-off algorithm.

24. The CPE unit of claim 23 wherein the CPE unit is a remote unit within a fixed wireless access communication system.

25. The CPE unit of claim 23 wherein the CPE unit is a mobile unit within a mobile communication system.

26. The CPE unit of claim 23 wherein the CPE unit is a cable modem within a cable television communication system.

27. The CPE unit of claim 20 wherein the CPE unit is a remote unit within a fixed wireless access communication system.

28. The CPE unit of claim 20 wherein the CPE unit is a mobile unit within a mobile communication system.

29. The CPE unit of claim 20 wherein the CPE unit is a cable modem within a cable television communication system.

30. A contention resolution processor including instructions for:

reading zero or more acknowledgements and a previous contention period load from a Bandwidth Allocation Map (MAP) message;

generating an offset for a request for which an acknowledgement does not exist in the MAP message, using a contention resolution algorithm; and

reducing an offset for zero or more requests for which an offset had previously been generated, in the event that the previous contention period load is below a threshold.

31. The contention resolution processor of claim 30 wherein the previous contention period load is an estimate of a rate at which a headend is receiving requests from at least one Customer Premises Equipment unit (CPE).

32. The contention resolution processor of claim 31 wherein the previous contention period load is defined as a number of requests from at least one CPE unit which are received at the headend since a previous MAP message was transmitted, divided by a contention window size of the previous MAP message.

33. The contention resolution processor of claim 30 wherein the contention resolution algorithm is a truncated binary exponential back-off algorithm.

34. In a digital communication system including at least one Customer Premises Equipment unit (CPE) and a headend, a method of reducing backlogged requests at a CPE comprising the steps of:

maintaining a table at the headend, the table including a reference to at least one service flow and a level of activity of each service flow;

if a level of activity at transmission resources shared by the at least one CPE falls below a threshold, determining from the level of activity of each service flow a selected service flow which is most likely to have a backlogged request;

transmitting a signal to the at least one CPE identifying the selected service flow; and

transmitting the backlogged request.

35. The method of claim 34 wherein the level of activity of a service flow is determined from a field in a packet header received from the service flow, the field indicating how many packets remain to be transmitted.