Fluid flow fair scheduling emulation in wireless shared channel packet communication network

• US 6,728,257 B1
• Filed: 08/28/1998
• Issued: 04/27/2004
• Est. Priority Date: 08/28/1998
• Status: Expired due to Term

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Lu, Songwu, Bharghavan, Vaduvur, Srikant, Rayadurgam
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): TRAN, PHUC H
• Application Number:
  US09/143,302
• Time in Patent Office: 2,069 Days
• Field of Search: 370/230, 370/237, 370/238, 370/332, 370/329, 370/330, 370/337, 370/347, 370/458, 370/459, 370/468, 370/437, 370/230.1, 370/231, 370/232, 370/235, 370/216, 370/217, 370/228, 370/333, 455/436-444
• US Class Current: 370/458
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A wireless shared channel network packet communication method emulates fluid flow fair scheduling. Errors inherent in wireless communication and unaccounted for in fair scheduling for wired networks are accounted for according to the method. Lagging communication flows, typically caused by burst errors in wireless communication systems, make up for their lag by causing leading flows to give up their lead. The method is independent of the pattern of channel error. In a preferred embodiment, lag compensation is accounted for by a service tag which identifies a precedence for contention based upon the previous denial of access for channel error. This precedence allows compensation when channels become error free. A modified preferred embodiment first attempts intraframe compensation by swapping slots when a host predicts an error for its assigned slot and another host assigned a later slot is able to transmit in the slot. Interframe compensation, when needed, is accomplished preferably by a round robin contention among backlogged flows. Errors are predicted by hosts for a subsequent slot when activity is sensed in a current slot but no good packet is received. Preferred packet structures include data and control slots, with data slots partitioned to provide necessary error status and backlog information piggybacked with data so a base has sufficient information to implement compensation in contention resolution.

Claims

1. A base and host wireless shared channel network packet communication method for scheduling communications for one or more base communication channels comprising the steps of:

monitoring, by a plurality of hosts, to analyze a channel error state for a base communication channel;

for the base communication channel analyzed in said step of monitoring, implementing a scheduling algorithm for said plurality of hosts;

communicating information according to a schedule determined by the scheduling algorithm;

repeating said monitoring step;

repeating said implementing step and compensating in the scheduling algorithm for the base communication channel analyzed in said step of monitoring for hosts previously determined by said monitoring step to have an error presence state.

2. The method according to claim 1, wherein each of said plurality of hosts indicates an error presence statement to the base by a NAK and an error free state by an ACK after each slot is received.

3. The method according to claim 2, wherein the base maintains a set of known backlogged flows among hosts and said scheduling algorithm schedules said set of known backlogged flows.

4. The method according to claim 3, wherein the base obtains uplink backlogged queue information from queue length information piggybacked onto data transmissions from hosts.

5. The method according to claim 4, wherein the base station allots slots only to hosts having queue length information indicated possession of packets to transmit.

6. A base and host wireless shared channel network packet communication method comprising the steps of:

monitoring, by a plurality of hosts, to analyze a channel error state for a base communication channel;

implementing a scheduling algorithm for said plurality of hosts;

communicating information according to a schedule determined by the scheduling algorithm;

repeating said monitoring step;

repeating said implementing step and compensating for hosts previously determined by said monitoring step to have an error presence state;

wherein said compensating comprises a swap of slots between a flow having an error presence state for its assigned slot and another flow scheduled for a later slot if a swap of slots is possible.

7. The method according to claim 6, wherein a swap of slots is possible when another flow assigns an error free state, possesses a packet and possesses a later slot.

8. The method according to claim 7, wherein said swap of slots is between flows assigned within a single frame.

9. The method according to claim 8, wherein flows are normally assigned to spread slots in a frame.

10. The method according to claim 8, further comprising a step of assigning values to leading and lagging flows when a swap of slots within a frame fails to compensate for a host previously determined to have an error state or a swap of slots is not possible.

11. The method according to claim 10, wherein leading flows are prevented from transmitting for a number of frames determined by their assigned value and weight if a lagging flow exists and is capable of transmitting in said number of frames.

12. The method according to claim 11, wherein lagging flows compensate for their associated value in a single frame.

13. The method according to claim 12, wherein values assigned to lagging flows are limited to a predetermined maximum.

14. The method according to claim 11, wherein lagging flows compensate for their associated value over a plurality of frames.

15. A base and host wireless shared channel network packet communication method comprising the steps of:

monitoring, by a plurality of hosts, to analyze a channel error state for a base communication channel;

implementing a scheduling algorithm for said plurality of hosts;

communicating information according to a schedule determined by the scheduling algorithm;

repeating said monitoring step;

repeating said implementing step and compensating for hosts previously determined by said monitoring step to have an error presence state;

wherein said step of monitoring conducted by each of said plurality of hosts comprises;

monitoring each base station transmission slot;

predicting an error presence state for a next slot if a current slot contains activity but no good packet;

else

predicting an error free state for said next slot.

16. A base and host wireless shared channel network packet communication method comprising the steps of:

monitoring, by a plurality of hosts, to analyze a channel error state for a base communication channel;

implementing a scheduling algorithm for the base communication channel analyzed in said step of monitoring for said plurality of hosts;

communicating information according to a schedule determined by the scheduling algorithm;

repeating said monitoring step;

repeating said implementing step and compensating in the scheduling algorithm for the base communication channel analyzed in said step of monitoring for hosts previously determined by said monitoring step to have an error presence state;

wherein the base and hosts communicate via a protocol having data slots and control slots.

17. The method according to claim 16, wherein each data slot comprises a control subslot having four minislots, a data subslot and an ACK/NAK subslot.

18. A base and host wireless shared channel network packet communication method comprising the steps of:

separating communication flows into leading and lagging flows, wherein leading flows are flows associated with a host having a queue length less than a queue length of its error free service at a predetermined time and lagging flows are flows associated with a host having a queue length greater than a queue length of its error free service at said predetermined time instant;

reducing the lag of lagging flows in a time after said predetermined time by allocating access to said lagging flows from said leading flows.

19. The method according to claim 18, wherein hosts maintain separate packet and slot queues, priority tags are maintained in said slot queues, and said packet queues discard packets once a predetermined packet backlog is reached to reduce a lag of a lagging flow, while the slot having the highest priority tag is maintained.