Dynamic bandwidth allocation for multiple access communications using buffer urgency factor

• US 6,388,999 B1
• Filed: 06/01/1998
• Issued: 05/14/2002
• Est. Priority Date: 12/17/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Tantivy Communications Incorporated (InterDigital, Inc.)
• Inventors: Proctor, James A., Amalfitano, Carlo, Gorsuch, Thomas E.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US09/088,527
• Time in Patent Office: 1,443 Days
• Field of Search: 370/320, 370/310, 370/335, 370/465, 370/342, 370/431, 370/441, 370/522, 370/468, 370/412, 375/347
• US Class Current: 370/335
• CPC Class Codes: H04B 1/707 using direct sequence modulation
• CPC Class Codes: H04J 13/0077 Multicode, e.g. multiple codes assigned to one user
• CPC Class Codes: H04L 1/165 Variable formats
• CPC Class Codes: H04L 25/14 Channel dividing arrangements , i.e. in which a single bit stream is divided between several baseband channels and reassembled at the receiver
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04Q 11/0428 Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
• CPC Class Codes: H04Q 2213/13098 Mobile subscriber
• CPC Class Codes: H04Q 2213/13202 Network termination [NT]
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 2213/13209 ISDN
• CPC Class Codes: H04Q 2213/13216 Code signals, frame structure
• CPC Class Codes: H04Q 2213/1327 Release and resetting of connection
• CPC Class Codes: H04Q 2213/13298 Local loop systems, access network
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 2213/1336 Synchronisation
• CPC Class Codes: H04Q 2213/13389 LAN, internet
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA
• CPC Class Codes: H04W 72/1221 based on age of data to be sent
• CPC Class Codes: H04W 72/52 : based on load
• CPC Class Codes: H04W 84/14 : WLL [Wireless Local Loop]; RLL [Radio Local Loop]
• CPC Class Codes: H04W 88/08 : Access point devices

Abstract

A technique for providing high speed data service over standard wireless connections via an unique integration of protocols and existing cellular signaling, such as is available with Code Division Multiple Access (CDMA) type systems through more efficient allocation of access to CDMA channels. For example, when more users exist than channels, the invention determines a set of probabilities for which users will require channel access at which times, and dynamically assigns channel resources accordingly. Channel resources are allocated according to a buffer monitoring scheme provided on forward and reverse links between a base station and multiple subscriber units. Each buffer is monitored over time for threshold levels of data to be transmitted in that buffer. For each buffer, a probability is calculated that indicates how often the specific buffer will need to transmit data and how much data will be transmitted. This probability takes into account the arrival rates of data into the buffer, as well as which thresholds within the buffer are exceeded, as well as which resources in the form of channels are already allocated to the subscriber unit.

Claims

1. A system for allocating and deallocating channel resources from a limited number of channel resources used to transmit data over a connection from a transmitter to a receiver, comprising:

a transmitter having an input that receives data to be transmitted to the receiver associated with the transmitter via the respective connection;

a plurality of buffers within the transmitter, each one of the plurality of buffers associated with a particular connection between a respective transmitter and receiver, each one of the plurality of buffers having an associated plurality of thresholds, each threshold associated with a level of data presently stored in the respective one of the plurality of buffers; and

a transmission processor within the transmitter which controls the transmission of data from the buffers to the channel resources, such that a respective buffer may use one or more of a number of channel resources allocated to the respective connection; and

a channel resource assignor which monitors the state of thresholds in the plurality of buffers, each buffer associated with a respective one of the connections, the channel resource assignor computes an urgency factor associated with each buffer, based upon statistical information determined from the threshold level states, the urgency factor representing a relative need for transmission to the respective receiver associated with that buffer and the channel resource assignor comparing the buffer urgency factors for the plurality of buffers to determine how many channel resources are to be allocated to each respective connection.

2. The system in claim 1, wherein the statistical information used to compute the urgency factor associated with a buffer includes statistics based upon threshold levels of data in the buffer, current resources allocated to the receiver associated with that buffer, and data arrival rates of data to that buffer.

3. The system in claim 1, wherein the statistical information used to compute the urgency factor associated with the buffer includes conditional probabilities of how much time has passed since the buffer has had data transmitted from the buffer to its intended receiver, as well as how much time has passed since data has been received at that input of the transmitter associated with that buffer.

4. The system of claim 1, wherein the urgency factor for a given buffer is based upon a sum of weighted conditional probabilities, each conditional probability representing the chance of exceeding a threshold E_L in the buffer, within a time frame T_S which corresponds to a maximum time needed to reallocate a channel resource to another buffer, given that data in the buffer has already exceeded a particular threshold E_i, each conditional probability for each threshold in a buffer given by the formula:

$P_{\mathrm{EL}}<br><br>\left(T_S<br><br>E_i\right)=\frac{P_{\mathrm{EL}}<br><br>\left(E_i\right)·<br><br>P_{\mathrm{EL}}<br><br>\left(T_S\right)}{P_{\mathrm{EL}}<br><br>\left(E_j\right)}$

which is derived from the formula;

$\frac{\sum <br><br>\left(P_{\mathrm{EL}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{within}<br><br>\text{\hspace{1em}<br><br>}<br><br>T_S<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>E_i\right)/\sum <br><br>\left(E_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>T_S\right)}{\sum <br><br>\left(E_L/E_i\right)}.$

5. The system of claim 4, wherein the conditional probabilities that make up the urgency factor U for a particular buffer are weighted before they are summed, according to the formula:

6. The system of claim 5, wherein the transmitter including at least one buffer is located in a base station operating a Code Division Multiple Access communication protocol and the at least one receiver comprises a plurality of subscriber units, each subscriber unit operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a forward link.

7. The system of claim 5, wherein the transmitter including at least one buffer is located in a subscriber unit operating a Code Division Multiple Access communication protocol and the at least one receiver is located in a base station operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a reverse link.

8. The system of claim 1 wherein the channel resource assignor determines how to allocate the available channels among the buffers by determining if the buffer having the highest urgency factor U exceeds a respective high threshold and if the buffer having the lowest urgency factor U exceeds a respective low threshold, and if so, deallocating one resource channel is from the buffer with the lowest urgency factor and reallocating the one resource channel to the buffer with the highest urgency factor.

9. The system of claim 8, wherein, for a first buffer, if the channel resource assignor determines that there is only one channel resource allocated to the first buffer, the one channel resource may be reallocated to a second buffer if there is no data in the second buffer and if the probability of exceeding the buffer capacity within the time it takes to reassign this initial resource, P_EL(T_S|E_O), is less than the probability of reaching the buffer overflow limit P(E_l).

10. The system of claim 1, wherein the transmitter including at least one buffer is located in a base station operating a Code Division Multiple Access communication protocol and the at least one receiver comprises a plurality of subscriber units, each subscriber unit operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a forward link.

11. The system of claim 1, wherein the transmitter including at least one buffer is located in a base station operating a Code Division Multiple Access communication protocol and the at least one receiver comprises a plurality of subscriber units, each subscriber unit operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a forward link.

12. The system of claim 1, wherein the transmitter including at least one buffer is located in a subscriber unit operating a Code Division Multiple Access communication protocol and the at least one receiver is located in a base station operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a reverse link.

13. The system of claim 1, wherein the transmitter including at least one buffer is located in a subscriber unit operating a Code Division Multiple Access communication protocol and the at least one receiver is located in a base station operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a reverse link.

14. A method for allocating and deallocating channel resources from a limited number of channel resources used to transmit data over a connection from a transmitter to a receiver, the method comprising the steps of:

receiving, at a transmitter, data to be transmitted the receiver associated with the transmitter via the respective connection;

storing the data to be transmitted in a plurality of buffers within the transmitter, each one of the plurality of buffers associated with a particular connection between a respective transmitter and receiver, each of the buffers having a plurality of thresholds, each threshold associated with a level of data presently stored in the respective one of the buffers;

controlling the transmission of data from the buffers to the channel resources at a transmission processor within the transmitter such that a respective buffer may use one or more of a number of channel resources allocated to the respective connection;

monitoring the state of thresholds in the plurality of buffers by a channel resource assignor each buffer associated with a respective one of the connections;

computing an urgency factor associated with each buffer based upon a statistical information determined from the threshold level states, the urgency factor representing a relative need for transmission to the respective receiver associated with that buffer; and

comparing the buffer urgency factors for the plurality of buffers to determine how many channel resources are to be allocated to each respective connection.

15. The method of claim 14, further including the step of basing the statistical information used to compute the urgency factor associated with a buffer on statistics including threshold levels of data in the buffer, current resources allocated to the receiver associated with that buffer, and data arrival rates of data to that buffer.

16. The method of claim 14, further including the step of basing the statistical information used to compute the urgency factor associated with the buffer on conditional probabilities of how much time has passed since the buffer has data transmitted from the buffer to its intended receiver, as well as how much time has passed since data has been received at that input of the transmitter associated with that buffer.

17. The method of claim 14, further including the step of basing the urgency factor for a given buffer upon a sum of weighted conditional probabilities, each conditional probability representing the chance of exceeding a threshold E_L in the buffer, within a time frame T_S which corresponds to a maximum time needed to reallocate a channel resource to another buffer, given that data in the buffer has already exceeded a particular threshold E_i, each conditional probability for each threshold in a buffer given by the formula:

$P_{\mathrm{EL}}<br><br>\left(T_S<br><br>E_i\right)=\frac{P_{\mathrm{EL}}<br><br>\left(E_i\right)·<br><br>P_{\mathrm{EL}}<br><br>\left(T_S\right)}{P_{\mathrm{EL}}<br><br>\left(E_j\right)}$

which is derived from the formula;

$\frac{\sum <br><br>\left(P_{\mathrm{EL}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{within}<br><br>\text{\hspace{1em}<br><br>}<br><br>T_S<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>E_i\right)/\sum <br><br>\left(E_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>T_S\right)}{\sum <br><br>\left(E_L/E_i\right)}.$

18. The method of claim 17, further including the steps of weighting the conditional probabilities that make up the urgency factor U for a particular buffer before they are summed, according to the formula:

19. The method of claim 14 further including the steps of:

determining how to allocate the available channels among the buffers by determining if the buffer having the highest urgency factor U exceeds a respective high threshold and if the buffer having the lowest urgency factor U exceeds a respective low threshold, and if so, deallocating one resource channel is from the buffer with the lowest urgency factor and reallocating the one resource channel to the buffer with the highest urgency factor.

20. The method of claim 19 further comprising the steps of:

for a first buffer, if the channel resource assignor determines that there is only one channel resource allocated to the first buffer, the one channel resource may be reallocated to a second buffer if there is no data in the second buffer and if the probability of exceeding the buffer capacity within the time it takes to reassign this initial resource, P_E^L(T_S|E_O), is less than the probability of reaching the buffer overflow limit P(E_L).

21. The method of claim 14, wherein the transmitter including at least one buffer is located in a base station operating a Code Division Multiple Access communication protocol and the at least one receiver comprises a plurality of subscriber units, each subscriber unit operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a forward link.

22. The method of claim 14, wherein the transmitter including at least one buffer is located in a subscriber unit operating a Code Division Multiple Access communication protocol and the at least one receiver is located in a base station operating the Code Division Multiple Access communication protocol and the transmitter communicates with the receiver using a number of channel resources selected from the limited number of channel resources assigned to a reverse link.