Adaptive contention algorithm based on truncated binary exponential back-off
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
35 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
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. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
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. - View Dependent Claims (31, 32, 33)
-
-
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. - View Dependent Claims (35)
-
Specification