Method for bandwidth sharing in a multiple access system for communications networks
First Claim
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.
7 Assignments
0 Petitions
Accused Products
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.
-
Citations
48 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith packet of class k.
-
-
6. The method of claim 4, wherein said service tag values are calculated according to the formula:
-
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith 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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith packet of class k.
-
-
16. The method of claim 14, wherein said service tag values are calculated according to the formula:
-
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith 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. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30)
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith packet of class k.
-
-
26. The method of claim 24, wherein said head-of-line service tag values are calculated according to the formula:
-
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith 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. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40)
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith packet of class k.
-
-
36. The method of claim 34, wherein said head-of-line service tag values are calculated according to the formula:
-
wherein û
(t) is the service tag of the packet in service at time t, Fik is the service tag for the ith packet from class k with Fok=0 for all k, Lik is the length of the ith packet of class k, rk is the relative weight assigned to class k, and aik is the arrival time of the ith 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.
-
Specification