Method and apparatus for a self-correcting bandwidth request/grant protocol in a wireless communication system

• US 6,785,252 B1
• Filed: 07/11/2000
• Issued: 08/31/2004
• Est. Priority Date: 05/21/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Ensemble Communications
• Inventors: Bourlas, Yair, Stanwood, Kenneth L., Spinar, Brian, Serok, Amir, Zimmerman, Ofer
• Primary Examiner(s): SEFCHECK, GREGORY B
• Application Number:
  US09/613,434
• Time in Patent Office: 1,512 Days
• Field of Search: 370/229-230, 370/235, 370/236, 370/276-278, 370/282, 370/328, 370/329, 370/346, 370/395--39, 370/412, 370/449, 370/464, 370/465, 370/468, 370/477, 370/349, 455/450-452
• US Class Current: 370/337
• CPC Class Codes: H04L 2012/5607 Radio
• CPC Class Codes: H04L 2012/561 Star, e.g. cross-connect, concentrator, subscriber group equipment, remote electronics
• CPC Class Codes: H04L 5/0064 Rate requirement of the data, e.g. scalable bandwidth, data priority
• CPC Class Codes: H04L 5/0092 Indication of how the channel is divided
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04W 28/0268 using specific QoS parameters for wireless networks, e.g. QoS class identifier [QCI] or guaranteed bit rate [GBR] negotiating SLA or negotiating QoS H04W28/24
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 56/0005 synchronizing of arrival of multiple uplinks
• CPC Class Codes: H04W 60/00 Affiliation to network, e.g. registration; Terminating affiliation with the network, e.g. de-registration
• CPC Class Codes: H04W 72/044 based on the type of the allocated resource
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/21 in the uplink direction of a wireless link, i.e. towards the network
• CPC Class Codes: H04W 72/23 in the downlink direction of a wireless link, i.e. towards a terminal
• CPC Class Codes: H04W 72/30 Resource management for broadcast services
• CPC Class Codes: H04W 72/51 based on terminal or device properties
• CPC Class Codes: H04W 72/56 based on priority criteria
• CPC Class Codes: H04W 74/06 using polling
• CPC Class Codes: H04W 76/11 : Allocation or use of connection identifiers
• CPC Class Codes: H04W 8/24 : Transfer of terminal data

Abstract

A method and apparatus for a self-correcting bandwidth request/grant protocol in a broadband wireless communication system is disclosed. The self-correcting bandwidth request/grant protocol utilizes a combination of incremental and aggregate bandwidth requests. In accordance with the present inventive protocol, CPEs primarily transmit incremental bandwidth requests to their associated base stations, followed by periodic transmissions of aggregate bandwidth requests. The use of incremental bandwidth requests reduces risks that a base station erroneously issues duplicate bandwidth allocations to the same CPE for the same connection. Race conditions that may have occurred using only aggregate bandwidth requests are eliminated by requiring the CPEs to request bandwidth in an incremental manner. However, use of periodic aggregate bandwidth requests (that express the current state of their respective connection queues) allows the present bandwidth allocation method and apparatus to be “self-correcting”. The present method is self-correcting because errors that may have been introduced due to lost incremental bandwidth requests are corrected by the base stations when the aggregate bandwidth requests are received and processed. Upon receipt of the aggregate bandwidth requests, the base stations reset their records to correctly reflect the current bandwidth requirements of their associated CPEs. Periodic use of aggregate bandwidth requests provides a self-correcting bandwidth allocation protocol yet without the bandwidth overhead (e.g., bandwidth required to transmit acknowledgements) typically associated with the prior art protocols (such as the guaranteed delivery protocols).

Claims

1. A method for allocating bandwidth in a wireless communication system, wherein the wireless communication system includes a plurality of customer premise equipment (CPE) in communication with associated and corresponding base stations, and wherein the base stations maintain uplink sub-frame maps representative of the bandwidth allocations in the uplink communication path, the method comprising:

(a) determining an incremental bandwidth requirement for a selected CPE;

(b) transmitting incremental bandwidth requests to a base station that is associated with the selected CPE, wherein the incremental bandwidth requests contain information indicative of incremental bandwidth requirements determined as in step (a);

(c) determining an aggregate bandwidth requirement for the selected CPE;

(d) determining

(i) an estimate of aggregate bandwidth requirements for the selected CPE that is based at least in part upon incremental bandwidth requests for the selected CPE that have been received by the associated base station, and

(ii) whether an aggregate bandwidth request should be transmitted to the base station associated with the selected CPE to reduce errors in the aggregate bandwidth estimate determined in step (d)(i), wherein the aggregate bandwidth request contains information indicative of the aggregate bandwidth requirement determined in step (c); and

(e) if an aggregate bandwidth request is determined to be required in step (d)(ii), then transmitting the aggregate bandwidth request to the associated base station and returning to step (a), else returning to step (a) without transmitting an aggregate bandwidth request.

2. The method for allocating bandwidth as defined in claim 1, wherein the incremental bandwidth requirement comprises the change in bandwidth requirements since the selected CPE last requested bandwidth from the associated base station, and the aggregate bandwidth requirement determined in step (c) comprises a total immediate bandwidth requirement for the selected CPE.

3. The method for allocating bandwidth as defined in claim 1, wherein determining an aggregate bandwidth for the selected CPE is omitted when according to step (d)(ii), an aggregate bandwidth request should not be transmitted to the associated base station.

5. The method for allocating bandwidth as defined in claim 1, wherein the step (d) of determining whether an aggregate bandwidth request should be transmitted to the associated base station comprises the steps of:

(a) waiting a pre-determined time interval between transmissions of aggregate bandwidth requests;

(b) indicating that an aggregate bandwidth request is required when the pre-determined time interval has expired, else returning to step (a).

6. The method for allocating bandwidth as defined in claim 1, wherein the aggregate bandwidth request transmitted in step (e) causes the associated base station to reset records representative of the total bandwidth requirements of the selected CPE, thereby allowing the method to be self-correcting.

7. The method for allocating bandwidth as defined in claim 1, wherein the incremental and aggregate bandwidth requests are transmitted by the selected CPE to the associated base station using a piggybacking technique, wherein the selected CPE transmits the bandwidth requests using unused bandwidth in packets of existing bandwidth allocations.

8. The method for allocating bandwidth as defined in claim 1, wherein the incremental and aggregate bandwidth requests are transmitted by the selected CPE to the associated base station using an individual polling technique, wherein the selected CPE is individually polled by the associated base station for its bandwidth requirements.

9. The method for allocating bandwidth as defined in claim 8, wherein the associated base station allocates bandwidth to the selected CPE in an uplink sub-frame map, and wherein the base station determines whether the selected CPE requests polling by examining a poll-me bit associated with the selected CPE.

10. The method for allocating bandwidth as defined in claim 1, wherein bandwidth requests are transmitted to the associated base station using a bandwidth request message.

27. The method of claim 1, wherein step (d)(ii) further includes limiting aggregate bandwidth requests to cause a frequency of incremental bandwidth requests transmitted to the associated base station as in step (a) to exceed a frequency of aggregate bandwidth requests as in step (e).

28. The method of claim 27, further comprising limiting a frequency of incremental bandwidth request transmissions as in step (a).

29. The method of claim 1, wherein step (d)(ii) further comprises limiting incremental bandwidth request transmissions based upon a first timer, and limiting aggregate bandwidth request transmissions based upon a second timer.

30. The method of claim 29, further comprising dynamically changing a duration for the first timer and/or a duration for the second timer, based upon changes in system parameters.

31. The method of claim 1, wherein step (d)(ii) further comprises limiting incremental bandwidth request transmissions based upon a timer, and limiting aggregate bandwidth request transmissions based at least in part upon a count of transmitted bandwidth requests.

32. The method of claim 1, further comprising omitting explicit acknowledgements from the associated base station to the selected CPE in response to bandwidth requests transmitted from the selected CPE to the associated base station.

33. The method of claim 1, further comprising:

(f) receiving a combined request for bandwidth from the selected CPE comprising a plurality of individual connection bandwidth requests, including

(i) receiving a first bandwidth request from the selected CPE for a first connection that is associated with a first quality of service (QoS), and

(ii) receiving a second bandwidth request from the selected CPE for a different second connection having a different second QoS; and

(g) providing a bandwidth allocation to the selected CPE in response to the combined request for bandwidth that is unequal to a total of the individual connection bandwidth requests, without conveying information from the associated base station to the CPE indicating an expected distribution of the allocated bandwidth between the individual connections.

4. A method for allocating bandwidth in a wireless communication system, wherein the wireless communication system includes a plurality of customer premise equipment (CPE) in communication with associated and corresponding base stations, and wherein the base stations maintain uplink and downlink sub-frame maps representative of the bandwidth allocations in the uplink and downlink communication paths, the method comprising the steps of:

(a) determining an incremental bandwidth requirement for a selected CPE;

(b) transmitting an incremental bandwidth request to a base station that is associated with the selected CPE, wherein the incremental bandwidth request contains information indicative of the incremental bandwidth requirement determined in step (a);

(c) determining an aggregate bandwidth requirement for the selected CPE;

(d) determining whether an aggregate bandwidth request should be transmitted to the base station associated with the selected CPE, wherein the aggregate bandwidth request contains information indicative of the aggregate bandwidth requirement determined in step (c), including

(i) counting consecutive transmissions of incremental bandwidth requests;

(ii) comparing the number of consecutive transmissions counted in step (a) to a pre-determined incremental bandwidth request threshold value; and

(iii) indicating that an aggregate bandwidth request is required if the number of consecutive transmissions of incremental bandwidth requests equals the pre-determined threshold, else returning to step (a); and

(e) if the aggregate bandwidth request is determined to be required in step (d), transmitting the aggregate bandwidth request to the associated base station and returning to step (a), else returning to step (a) without transmitting the aggregate bandwidth request.

11. A method for allocating bandwidth in a wireless communication system, wherein the wireless communication system includes a plurality of customer premise equipment (CPE) in communication with associated and corresponding base stations, and wherein the base stations maintain uplink and downlink sub-frame maps representative of the bandwidth allocations in the unlink and downlink communication paths, the method comprising the steps of:

(a) determining an incremental bandwidth requirement for a selected CPE.

(b) transmitting an incremental bandwidth request to a base station that is associated with the selected CPE, wherein the incremental bandwidth request contains information indicative of the incremental bandwidth requirement determined in step (a);

(c) determining an aggregate bandwidth requirement for the selected CPE;

(d) determining whether an aggregate bandwidth request should be transmitted to the base station associated with the selected CPE, wherein the aggregate bandwidth request contains information indicative of the aggregate bandwidth requirement determined in step (c); and

(e) if the aggregate bandwidth request is determined to be required in step (d), transmitting the aggregate bandwidth request to the associated base station and returning to step (a), else returning to step (a) without transmitting the aggregate bandwidth request;

wherein bandwidth requests are transmitted to the associated base station using a bandwidth request message, and the bandwidth request message includes a Message Type ID field, a Connection ID/QoS field, a Request Type field, and an Amount Requested field.

12. The method for allocating bandwidth as defined in claim 11, wherein the Request Type field indicates whether an incremental or an aggregate bandwidth request is being transmitted.

13. The method for allocating bandwidth as defined in claim 11, wherein the Amount Requested field indicates the amount of bandwidth being requested by the selected CPE.

14. The method for allocating bandwidth as defined in claim 13, wherein the amount of bandwidth being requested is expressed in natural units of the wireless communication system.

15. The method for allocating bandwidth as defined in claim 14, wherein the natural units comprise bytes for communication systems using variable length packets, and wherein the natural units comprise packets for communication systems using fixed length packets.

16. The method for allocating bandwidth as defined in claim 11, wherein the Message Type ID field comprises a pre-determined constant value indicating to the communication system that a bandwidth request message is being transmitted.

17. The method for allocating bandwidth as defined in claim 11, wherein the Connection ID/QoS field indicates either an identifier for a connection between the selected CPE and the associated base station, or a quality of service (QoS) associated with the connection between the selected CPE and the associated base station.

18. The method for allocating bandwidth as defined in claim 17, wherein the quality of service (QoS) associated with the connection is assigned at a time when the connection is first established between the CPE and the associated base station.

19. An apparatus for allocating bandwidth in a wireless communication system, wherein the wireless communication system includes a plurality of customer premise equipment (CPE) in communication with associated and corresponding base stations, and wherein the base stations maintain uplink sub-frame maps representative of the bandwidth allocations in the uplink communication paths, comprising:

(a) a bandwidth requirement calculator for calculating an incremental bandwidth requirement and an aggregate bandwidth requirement of a selected CPE;

(b) a transmitter, operatively coupled to the bandwidth requirement calculator, for transmitting an incremental bandwidth request and an aggregate bandwidth request to a base station associated with the selected CPE, wherein the incremental bandwidth request is indicative of the incremental bandwidth requirement of the selected CPE, and wherein the aggregate bandwidth request is indicative of the aggregate bandwidth requirement of the selected CPE; and

(c) an aggregate bandwidth request limiter, operatively coupled to the transmitter, for determining whether an aggregate bandwidth request should be transmitted to the associated base station and limiting a frequency of aggregate bandwidth requests to be less than a frequency of incremental bandwidth requests, wherein the aggregate bandwidth request limiter causes the transmitter to periodically transmit an aggregate bandwidth request when the aggregate bandwidth request limiter determines that the aggregate bandwidth request should be transmitted to the associated base station.

20. The apparatus for allocating bandwidth in a wireless communication system as defined in claim 19, wherein the aggregate bandwidth request limiter precludes aggregate bandwidth requests until a limiting counter counts a predetermined number of time units and/or incremental bandwidth requests.

21. The apparatus for allocating bandwidth in a wireless communication system as defined in claim 20, wherein the predetermined number set for the limiting counter of the aggregate bandwidth request limiter is dynamically modifiable based upon changes in system parameters.

22. An apparatus for allocating bandwidth in a wireless communication system wherein the wireless communication system includes a plurality of customer premise equipment (CPE) in communication with associated and corresponding base stations, and wherein the base stations maintain uplink and downlink sub-frame maps representative of the bandwidth allocations in the uplink and downlink communication paths, comprising:

(a) bandwidth requirement calculating means for calculating an incremental bandwidth requirement and an aggregate bandwidth requirement of a selected CPE;

(b) transmitting means, operatively coupled to the bandwidth requirement calculating means, for transmitting an incremental bandwidth request and an aggregate bandwidth request to a base station associated with the selected CPE, wherein the incremental bandwidth request is indicative of the incremental bandwidth requirement of the selected CPE, and wherein the aggregate bandwidth request is indicative of the aggregate bandwidth requirement of the selected CPE; and

(c) determining means, operatively coupled to the transmitting means, for determining whether an aggregate bandwidth request should be transmitted to the associated base station, wherein the determining means causes the transmitting means to periodically transmit an aggregate bandwidth request when the determining means determines that the aggregate bandwidth request should be transmitted to the associated base station, the determining means including;

(i) means for counting consecutive transmissions of incremental bandwidth requests;

(ii) means for comparing the number of consecutive transmissions counted by the counting means with a pre-determined incremental bandwidth request threshold value; and

(iii) means for indicating that an aggregate bandwidth request is required whenever the number of consecutive transmissions of incremental bandwidth requests equals the pre-determined threshold.

23. The apparatus for allocating bandwidth in a wireless communication system as defined in claim 22, wherein the means for counting consecutive transmissions of incremental bandwidth requests includes a dynamic timer.

24. The apparatus for allocating bandwidth in a wireless communication system as defined in claim 23, wherein the timer is set to a pre-determined number of frames that the apparatus waits between transmissions of aggregate bandwidth requests, and wherein the timer is decremented each time that an incremental bandwidth request is transmitted.

25. The apparatus for allocating bandwidth in a wireless communication system as defined in claim 24, wherein the a pre-determined number of frames that the apparatus waits between transmissions of aggregate bandwidth requests depends upon a quality of service (QoS) associated with a connection between the selected CPE and the associated base station.

26. A method for allocating bandwidth in a wireless communication system, wherein the wireless communication system includes a plurality of customer premise equipment (CPE) in communication with associated and corresponding base stations, and wherein the base stations maintain uplink and downlink sub-frame maps representative of the bandwidth allocations in the uplink and downlink communication paths, the method comprising the steps of:

(a) awaiting for the arrival of data for which bandwidth has not yet been allocated;

(b) determining whether a first timer has expired, wherein the first timer is initially set to a number of frames that the communication system waits between transmission of aggregate bandwidth requests;

(c) if the first timer is determined not to have expired in step (b), constructing an incremental bandwidth request indicative of an incremental bandwidth requirement of a selected CPE, else constructing an aggregate bandwidth request indicative of an aggregate bandwidth requirement of the selected CPE;

(d) transmitting the bandwidth request constructed in step (c) to a base station that is associated with the selected CPE;

(e) receiving an uplink sub-frame map that contains a bandwidth grant responsive to the bandwidth request transmitted in step (d);

(f) determining whether the bandwidth grant contained in the uplink sub-frame map is appropriate;

(g) if the bandwidth grant is determined to be appropriate in step (f), proceeding to step (h), else determining whether a second timer has expired, and if the second timer has expired, returning to step (e), else returning to step (b);

(h) transmitting data;

(i) determining whether the bandwidth grant received in step (e) fully satisfied the bandwidth request transmitted in step (d); and

(j) if the bandwidth grant is fully satisfied, returning to step (a);

else returning to step (e).