Method for bandwidth sharing in a multiple access system for communications networks

• US 6,327,254 B1
• Filed: 05/22/1998
• Issued: 12/04/2001
• Est. Priority Date: 10/14/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Chuah, Mooi Choo
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/083,675
• Time in Patent Office: 1,292 Days
• Field of Search: 370/328, 370/230-234, 370/322, 370/329, 370/336, 370/337, 370/338, 370/347, 370/348, 370/442-445, 370/461, 370/462, 370/401, 370/351, 370/352, 370/441, 370/321, 370/384
• US Class Current: 370/328
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/286 Time to live
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 52/10 Open loop power control
• CPC Class Codes: H04W 52/50 at the moment of starting communication in a multiple access environment
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/535 based on resource usage policies
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 88/08 Access point devices

Abstract

A method for data transmission in a wireless communication network utilizes an on-demand multiple access method with a fair queuing service discipline for efficient utilization of the limited bandwidth available in the network by sharing bandwidth among the remote hosts. In one embodiment, the base station broadcasts the system virtual time and the assigned shares of service classes to each of the wireless remotes. Each remote host computes its own service tag and reports it to the base station, which assigns transmit permits based on the service tag values and the available data slots. If a packet is lost or in error, the sending remote recomputes the service tag values of all its queued packets, including the packet whose transmission failed. Alternatively, the remote informs the base station of its queue size and the base station computes service tags for each remote based on the service shares of the remote and the available data slots. If a packet is lost or in error, the base station recomputes the service tag values for that remote host based on the current system virtual time. In an alternate embodiment, the AP or wireless node maintains a packet queue and a head-of-line tag. If a packet is lost, only the head-of-line tag needs to be changed. Once the head-of-line packet has been transmitted successfully, the rest of the queued packets will automatically receive the correct tag, the recomputed head-of-line tag plus appropriate increments. For half-duplex, both the uplink and downlink queues at the access points are managed as if there is only one system virtual time. For full-duplex, separate system virtual times for the uplink and the downlink traffic may be used. Remotes may also be divided into one or more separate groups, with each group having a different priority and receiving a different system virtual time. Service tags of all other remotes remain unaffected by the retransmission of a packet from any particular remote, meaning that the QoS experienced by the other remotes does not suffer.

Claims

1. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

broadcasting at least one of said system virtual times from said base station to said plurality of remote hosts;

computing at each of said remote hosts a respective service tag value for each newly arrived one of said data packets intended for transmission from said remote host to said base station, said service tag value being computed from said broadcasted system virtual time;

transmitting the smallest one of said service tag values from each of said remote hosts to said base station;

determining transmit permits at said base station based on said service tag values received from said plurality of remote hosts and the availability of transmission data slots to be assigned; and

recomputing at each of said remote hosts the service tag values of all queued packets at said remote host when the currently transmitted packet from said remote host is lost or in error.

2. The method of claim 1, wherein said step of recomputing said service tag values of all of said queued packets at one of said remote hosts when the currently transmitted packet from said remote host is lost or in error further includes the steps of assigning said lost or in error packet the next one of said service tag values previously assigned to packets from said remote host and recomputing the remaining ones of said service tags from that point.

3. The method of claim 1, further including the step of transmitting an assigned service share from said base station to each of said remote hosts and wherein said step of computing at each of said remote hosts a respective service tag value for each newly arrived one of said data packets utilizes said assigned service share in the computation.

4. The method of claim 2, further including the step of transmitting an assigned service share from said base station to each of said remote hosts and wherein said step of computing at each of said remote hosts a respective service tag value for each newly arrived one of said data packets utilizes said assigned service share in the computation.

5. The method of claim 3, wherein said service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r_k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

6. The method of claim 4, wherein said service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r_k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

7. The method of claim 1, wherein a different system virtual time is used for uplink and downlink transmission.

8. The method of claim 2, wherein a different system virtual time is used for uplink and downlink transmission.

9. The method of claim 1, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and receiving a different system virtual time from said base station for computation of said service tag values.

10. The method of claim 2, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and receiving a different system virtual time from said base station for computation of said service tag values.

11. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

transmitting a packet count from each of said remote hosts to said base station, each packet count being representative of the number of fixed-sized packets or the length of a variable-length packet to be transmitted from said remote host to said base station;

computing at said base station a set of service tag values for each of said remote hosts from one of said system virtual times and said packet count;

determining transmit permits at said base station based on said service tag values computed for said plurality of remote hosts and the availability of transmission data slots to be assigned; and

re-computing for each of said remote hosts the service tag values of all queued packets at said base station when the currently transmitted packet from said remote host is lost or in error.

12. The method of claim 11, wherein said step of recomputing said service tag values of all of said queued packets at one of said remote hosts when the currently transmitted packet from said remote host is lost or in error further includes the steps of assigning said lost or in error packet the next one of said service tag values previously assigned to packets from said remote host and recomputing the remaining ones of said service tags from that point.

13. The method of claim 11, wherein said step of computing for each of said remote hosts a respective set of service tag values utilizes an assigned service share for said remote host in the computation.

14. The method of claim 12, wherein said step of computing for each of said remote hosts a respective set of service tag values utilizes an assigned service share for said remote host in the computation.

15. The method of claim 13, wherein said service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r_k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

16. The method of claim 14, wherein said service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r^k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

17. The method of claim 11, wherein a different system virtual time is used for uplink and downlink transmission.

18. The method of claim 12, wherein a different system virtual time is used for uplink and downlink transmission.

19. The method of claim 11, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and having a different system virtual time used in computation of said service tag values.

20. The method of claim 12, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and having a different system virtual time used in computation of said service tag values.

21. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

broadcasting at least one of said system virtual times from said base station to said plurality of remote hosts;

computing at each of said remote hosts a respective head-of-line service tag value for the first one of said data packets intended for transmission from said remote host to said base station, said service tag value being computed from said broadcasted system virtual time;

transmitting said respective head-of-line service tag value from each of said remote hosts to said base station;

determining transmit permits at said base station based on said head-of-line service tag values received from said plurality of remote hosts and the availability of transmission data slots to be assigned;

computing a new head-of-line service tag value at each remote host after successful transmission of a packet from said remote host; and

recomputing at each of said remote hosts the head-of-line service tag value for queued packets at said remote host when the currently transmitted packet from said remote host is lost or in error.

22. The method of claim 21, wherein said step of recomputing said head-of-line service tag value for said queued packets at one of said remote hosts when the currently transmitted packet from said remote host is lost or in error includes the step of assigning said lost or in error packet a service tag value equal to the new head-of-line service tag that would have been computed at said remote host had said packet been transmitted successfully.

23. The method of claim 21, further including the step of transmitting an assigned service share from said base station to each of said remote hosts and wherein said step of computing at each of said remote hosts a respective head-of-line service tag value for said data packets utilizes said assigned service share in the computation.

24. The method of claim 22, further including the step of transmitting an assigned service share from said base station to each of said remote hosts and wherein said step of computing at each of said remote hosts a respective head-of-line service tag value for said data packets utilizes said assigned service share in the computation.

25. The method of claim 23, wherein said head-of-line service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r_k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

26. The method of claim 24, wherein said head-of-line service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r_k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

27. The method of claim 21, wherein a different system virtual time is used for uplink and downlink transmission.

28. The method of claim 22, wherein a different system virtual time is used for uplink and downlink transmission.

29. The method of claim 21, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and receiving a different system virtual time from said base station for computation of said head-of-line service tag values.

30. The method of claim 22, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and receiving a different system virtual time from said base station for computation of said head-of-line service tag values.

31. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and a plurality of remote hosts, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

transmitting a packet count from each of said remote hosts to said base station, each packet count being representative of the number of fixed-sized packets or the length of a variable-length packet to be transmitted from said remote host to said base station;

computing at said base station a head-of-line service tag value for each of said remote hosts from one of said system virtual times and said packet count;

determining transmit permits at said base station based on said head-of-line service tag values computed for said plurality of remote hosts and the availability of transmission data slots to be assigned;

computing a new head-of-line service tag for each of said remote hosts after successful transmission of a packet from said remote host; and

re-computing for each of said remote hosts the head-of-line service tag value for queued packets at said base station when the currently transmitted packet from said remote host is lost or in error.

32. The method of claim 31, wherein said step of recomputing said head-of-line service tag value for said queued packets at one of said remote hosts when the currently transmitted packet from said remote host is lost or in error includes the step of assigning said lost or in error packet a service tag value equal to the new head-of-line service tag that would have been computed for said remote host had said packet been transmitted successfully.

33. The method of claim 31, wherein said step of computing for each of said remote hosts a respective head-of-line service tag value utilizes an assigned service share for said remote host in the computation.

34. The method of claim 32, wherein said step of computing for each of said remote hosts a head-of-line service tag value utilizes an assigned service share for said remote host in the computation.

35. The method of claim 33, wherein said head-of-line service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r_k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

36. The method of claim 34, wherein said head-of-line service tag values are calculated according to the formula:

$F_k^i=\frac{L_k^i}{r_k}+\max <br><br>\left(F_k^{i^{-1}},\hat{u}<br><br>\left(a_k^i\right)\right)$

wherein û

(t) is the service tag of the packet in service at time t, Fⁱ_k is the service tag for the i^th packet from class k with F^o_k=0 for all k, Lⁱ_k is the length of the i^th packet of class k, r_k is the relative weight assigned to class k, and aⁱ_k is the arrival time of the i^th packet of class k.

37. The method of claim 31, wherein a different system virtual time is used for uplink and downlink transmission.

38. The method of claim 32, wherein a different system virtual time is used for uplink and downlink transmission.

39. The method of claim 31, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and having a different system virtual time used in computation of said head-of-line service tag values.

40. The method of claim 32, wherein said remote hosts are divided into a plurality of classes, each of said classes having a different priority and having a different system virtual time used in computation of said head-of-line service tag values.

41. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

broadcasting at least one of said system virtual times from said base station to at least one remote host;

receiving at said base station a smallest service tag value for at least one remote host, service tag values being computed for each newly arrived one of said data packets intended for transmission from said remote host to said base station, said service tag values being computed from said broadcasted system virtual time, the service tag values of all queued packets at said remote host being recomputed when the most recently transmitted packet from said remote host has been lost or in error; and

granting at least one transmit permit at said base station based on said smallest service tag value received for said at least one remote host.

42. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

receiving at least one of said system virtual times from said base station at least one remote host;

computing a respective service tag value for each newly arrived one of said data packets intended for transmission from said at least one remote host to said base station, said service tag value being computed from said broadcasted system virtual time, the service tag values of all queued packets at said remote host being recomputed when the most recently transmitted packet from said remote host is lost or in error; and

transmitting the smallest one of said service tag values from at least one of said remote hosts to said base station for granting of at least one transmit permit based on said smallest service tag value.

43. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

receiving a packet count at said base station for at least one remote host, said packet count being representative of the number of fixed-sized packets or the length of a variable-length packet to be transmitted from said remote host to said base station;

computing a set of service tag values for said at least one remote host from one of said system virtual times and said packet count, the service tag values of all queued packets at said remote host being recomputed when the most recently transmitted packet from said remote host is lost or in error; and

granting at least one transmit permit at said base station based on said computed service tag values.

44. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

transmitting a packet count for at least one remote host to said base station, said packet count being representative of the number of fixed-sized packets or the length of a variable-length packet to be transmitted from said remote host to said base station, said packet count being used for computing a set of service tag values for said remote host from one of said system virtual times, said computed service tag values being used by said base station for granting of at least one transmit permit; and

transmitting one of said data packets from at least one remote host to said base station after receipt of one of said at least one transmit permit, the service tag values for all queued packets at said remote host being recomputed if the transmitted data packet is lost or in error.

45. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

broadcasting at least one of said system virtual times from said base station to at least one remote host;

receiving at said base station, for at least one of said remote hosts, a head-of-line service tag value for a first one of said data packets intended for transmission from said remote host to said base station, said head-of-line service tag value being computed from said broadcasted system virtual time, a new head-of-line service tag value being computed for a next one of said data packets at said remote host after successful transmission of said first one of said data packets from said remote host, the head-of-line service tag value for queued packets at said remote host being recomputed when the most recently transmitted packet from said remote host is lost or in error; and

granting at least one transmit permit at said base station based on said head-of-line service tag value received for said at least one remote host.

46. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

receiving at least one of said system virtual times from said base station at at least one remote host;

computing, for at least one remote host, a head-of-line service tag value for a first one of said data packets intended for transmission from said remote host to said base station, said head-of-line service tag value being computed from said broadcasted system virtual time, a new head-of-line service tag value being computed for a next one of said data packets at said remote host after successful transmission of said first data packet from said remote host, the head-of-line service tag value for queued packets at said remote host being recomputed when the most recently transmitted packet from said remote host is lost or in error; and

transmitting said head-of-line service tag value from at least one remote host to said base station for granting of at least one transmit permit based on said head-of-line service tag value.

47. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

receiving a packet count at said base station for at least one remote host, said packet count being representative of the number of fixed-sized packets or the length of a variable-length packet to be transmitted from said remote host to said base station;

computing at said base station a head-of-line service tag value for said remote host from one of said system virtual times and said packet count, a new head-of-line service tag being computed for said remote host after successful transmission of a packet from said remote host, the head-of-line service tag value for queued packets at said remote host being recomputed when the most recently transmitted packet from said remote host is lost or in error; and

granting at least one transmit permit at said base station based on said head-of-line service tag value.

48. A method for sharing bandwidth among remote hosts in a wireless communications network, said network having a base station and at least one remote host, said network being configured for transmission and receipt of data packets and maintaining at least one system virtual time, the method comprising the steps, in combination, of:

transmitting a packet count for at least one remote host to said base station, said packet count being representative of the number of fixed-sized packets or the length of a variable-length packet to be transmitted from said remote host to said base station, said packet count being used for computing a head-of-line service tag value for said remote host from one of said system virtual times, said head-of-line service tag value being used for granting at least one transmit permit at said base station; and

transmitting one of said data packets from said at least one remote host to said base station after receipt of one of said at least one transmit permit, a new head-of-line service tag being computed for said remote host after successful transmission of said data packet from said remote host, the head-of-line service tag value for queued packets at said remote host being recomputed if the transmitted data packet is lost or in error.