Multiplex communications – Channel assignment techniques – Combining or distributing information via time channels...
Reexamination Certificate
2000-09-07
2004-10-05
Olms, Douglas W. (Department: 2661)
Multiplex communications
Channel assignment techniques
Combining or distributing information via time channels...
C370S442000, C370S252000, C370S902000, C370S902000
Reexamination Certificate
active
06801537
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to digital communication systems, and more particularly to contention resolution within such systems.
BACKGROUND OF THE INVENTION
In a communication system based on dynamic bandwidth allocation and in which multiple users have access to shared transmission resources, such as a transmission channel, contention can arise amongst users attempting to access the shared transmission resources simultaneously. Such communication systems require a robust contention resolution algorithm to resolve contentions between users in order to provide Quality of Service guarantees, to maximize bandwidth utilization, and to provide system stability. If users request access to a shared resource simultaneously, a contention arises and packets from the users will collide. Each user whose transmitted packet collides with other packets must randomly determine a back-off time during which the user will not attempt to re-access the shared resource.
The Data-Over-Cable Service Interface Specification (DOCSIS 1.1), incorporated by reference herein, is a communication protocol designed for high-speed packet-based communications over cable television communication networks, but which can also form the basis of wireless communication systems. At the user end of the communication system a headend is linked to several Customer Premises Equipment units (CPEs) through several communication links. The headend acts as a distribution hub into a wide area network for the CPEs to which it is linked. Each CPE may manage more than one service flow. In a cable television communication network the headend, communication link, and CPE are a Cable Modem Termination System (CMTS), a coaxial cable, and a Cable Modem (CM) respectively. In a wireless communication network the headend, communication link, and CPE are a Base station Transceiver System (BTS), a radio channel, and a mobile unit respectively. In a fixed wireless access communication system the headend, communication link, and CPE are a BTS, a radio channel, and a remote unit respectively.
Under DOCSIS 1.1, the headend transmits Bandwidth Allocation Map (MAP) messages on a regular basis to all CPEs to which it is linked. A MAP message is a Media Access Control management message that the headend uses to announce and allocate transmission opportunities to the CPEs. Each MAP message includes a number of Information Elements (IEs), a Data Backoff Start field, and other fields specified by DOCSIS 1.1. The Data Backoff Start field defines an initial back-off window for use in a contention resolution algorithm. Each IE defines an interval of transmission time and includes an interval usage code that identifies the type of transmission which may be transmitted by a CPE during the interval. One type of IE is a Request IE, which is used by the headend to announce an interval in which CPEs may transmit a request for bandwidth for upstream data transmission. The Request IE may have a Service ID of type unicast, in which case only the CPE managing a service flow specified in the Request IE may transmit a request during the interval, and the request must be for the specified service flow. The Request IE may alternatively have a Service ID of type broadcast, in which case any CPE may transmit a request during the interval, for any service flow. If a CPE receives a broadcast-type Request IE in a MAP message and wishes to transmit a request, the CPE calculates a random offset based on the Data Backoff Start field of the MAP message. After expiry of the random offset the CPE transmits a request for bandwidth for a data-transmission for a service flow. The request indicates the number of bytes remaining in the transmission queue of the service flow. The random offset is necessary to minimize request collisions between different CPEs transmitting requests in response to the same broadcast-type Request IE. When the headend receives the request, the headend attempts to schedule the requested data transmission within the interval between transmission of the next two MAP messages (the next MAP period). If the requested data transmission can be accommodated within the next MAP period, the headend alerts the CPE that the request was granted using a Data Grant IE in the next MAP message. If the request for transmission cannot be accommodated within the next MAP period, the headend alerts the CPE that the request is pending using a zero length Data Grant IE (referred to as a Data Grant Pending IE) in the next MAP message. When the headend receives a request from a CPE, the head unit must send either a Data Grant IE or a Data Grant Pending IE to the CPE in the subsequent MAP message.
If the Request IE is of type broadcast, then any CPE may transmit a request to the headend. If requests from more than one CPE arrive at the headend simultaneously, the requests will collide. All of the requests will be lost, unless the headend is implementing a capture effect in which case all but one request will be lost. The headend does not detect the lost requests, and is therefore unable to send a Data Grant IE or Data Grant Pending IE to a CPE whose request was lost. When a CPE does not receive a Data Grant IE or a Data Grant Pending IE in the MAP message subsequent to the transmission of the request, the CPE realizes that a contention arose and that its request was lost. According to the truncated binary exponential back-off algorithm, which is required-by DOCSIS 1.1, the CPE must increase its back-off window by a factor of two. The CPE calculates a new random offset within the new back-off window, and after a number of contention transmission opportunities (each of which is identified by one broadcast-type Request IE) equal to the random offset has elapsed, the CPE may respond to a new broadcast-type Request IE by re-sending the request for bandwidth for upstream data transmission. The CPE continues this contention resolution method until it receives a Data Grant IE or Data Grant Pending IE, a maximum number of retries have been attempted (at which point the packet of data is discarded), or the CPE receives a unicast-type Request IE (in which case it must use the explicit transmission opportunity offered and defined by the unicast-type Request IE).
Each CPE may manage more than one service flow, and will transmit a request for each service flow which uses contention resolution. Contentions may result in more than one request from a CPE being lost, in which case a contention resolution algorithm must be implemented for each blocked service flow.
The truncated binary exponential back-off algorithm successively increases the range of possible random offsets, and repeated contentions will on average result in successively longer back-off times. If a CPE is managing more than one service flow, then at any time the CPE may have backlogged requests. The load on the shared transmission resources is dynamic, and may decrease enough to accommodate new requests. Bandwidth utilization would be improved if the backlogged requests could take advantage of a low load on the shared transmission resources without unnecessarily awaiting expiry of their back-off times.
SUMMARY OF THE INVENTION
The present invention provides a method of resolving contention between a plurality of requests arriving at a headend from Customer Premises Equipment units (CPEs) in a digital communication system. A Bandwidth Allocation Map (MAP) message is transmitted from the headend to each CPE, the MAP message including acknowledgements and a previous contention period load. Upon arrival of the MAP message at each CPE, the CPEs read the acknowledgements and the previous contention period load. An offset is generated for each request for which an acknowledgement does not exist in the MAP message, using a contention resolution algorithm. If the previous contention period load is below a threshold, the offset for some or all requests for which an offset had previously been generated (backlogged requests) may be reduced. The previous contention period load is an estimate of the rate at which the headend
Nortel Networks Limited
Olms Douglas W.
Wilson Robert W.
LandOfFree
Adaptive contention algorithm based on truncated binary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive contention algorithm based on truncated binary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive contention algorithm based on truncated binary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3268605