Method and apparatus for adaptive delay management

• US 20050281278A1
• Filed: 05/05/2005
• Published: 12/22/2005
• Est. Priority Date: 05/05/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Black, Peter J., Bhushan, Naga, Yavuz, Mehmet, Gurelli, Mehmet I.
• Granted Patent: US 8,472,322 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 1/0002 by adapting the transmission rate
• CPC Class Codes: H04L 1/0017 where the mode-switching is based on Quality of Service requirement
• CPC Class Codes: H04L 1/0018 based on latency requirement
• CPC Class Codes: H04L 1/20 using signal quality detector
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 72/54 based on quality criteria
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS
• CPC Class Codes: H04W 8/20 Transfer of user or subscriber data

Abstract

Adaptive delay management means and method for allocating resources having different Quality of Service (QoS) requirements. A Forward Link (FL) scheduler prepares transmission instances by treating pending data queues according to a priority class, such as Best Effort (BE) and Expedited Forwarding (EF). Data bits from multiple queues are stuffed into a transmission instance. Various metrics are used to generate a set of candidates for transmission and then select and build a next transmission instance from the set of candidates.

Claims

1. A method for scheduling transmission instances in a wireless communication system, comprising:

receiving channel condition indicators from a plurality of mobile users, wherein the channel condition indicators correspond to forward link communications;

determining a delay criteria for the plurality of mobile users; and

determining a transmission schedule for the plurality of mobile users, wherein the transmission schedule is a function of the delay criteria.

2. A method for scheduling transmission instances in a wireless communication system, comprising:

evaluating a plurality of transmission queues to identify delay sensitivity and throughput sensitivity of an application flow associated with each transmission queue;

generating a set of candidate transmission instances from the plurality of transmission queues;

selecting one candidate transmission instance from the set; and

preparing the selected candidate transmission instance for transmission.

3. The method as in claim 2, wherein generating the set of candidate transmission instances comprises:

generating a bit metric for each queue; and

generating a bit stuffing metric for each queue.

4. The method as in claim 3, wherein selecting one candidate transmission instance comprises:

generating a packet metric as a function of the bit metric; and

comparing the packet metrics for candidate transmission instances in the set.

5. The method as in claim 4, wherein the delay criteria is determined on a per flow per user basis.

6. An apparatus for scheduling transmission instances in a wireless communication system, comprising:

means for receiving channel condition indicators from a plurality of mobile users, wherein the channel condition indicators correspond to forward link communications;

means for determining a delay criteria for the plurality of mobile users; and

means for determining a transmission schedule for the plurality of mobile users, wherein the transmission schedule is a function of the delay criteria.

7. An apparatus for scheduling transmission instances in a wireless communication system, comprising:

means for evaluating a plurality of transmission queues to identify delay sensitivity and throughput sensitivity of an application flow associated with each transmission queue;

means for generating a set of candidate transmission instances from the plurality of transmission queues;

means for selecting one candidate transmission instance from the set; and

preparing the selected candidate transmission instance for transmission.

8. The apparatus as in claim 7, wherein the means for generating the set of candidate transmission instances comprises:

means for generating a bit metric for each queue; and

means for generating a bit stuffing metric for each queue.

9. The apparatus as in claim 8, wherein the means for selecting one candidate transmission instance comprises:

means for generating a packet metric as a function of the bit metric; and

means for comparing the packet metrics for candidate transmission instances in the set.

10. An apparatus for scheduling transmission instances in a wireless communication system, comprising:

memory storage unit for storing transmission queues, each queue having an associated delay criteria;

a queue select unit for selecting a transmission queue of the stored transmission queues as a function of the delay criteria.

11. The apparatus as in claim 10, further comprising:

a bit metric calculation unit for calculating a bit metric for each transmission queue,

wherein the queue select unit selects a transmission queue as a function of the bit metrics.

12. The apparatus as in claim 11, further comprising:

a bit stuffing metric calculation unit for calculating a bit stuffing metric for each transmission queue; and

a candidate transmission instance unit for generating a set of candidate transmission instances as a function of the bit stuffing metrics,

wherein each candidate transmission instance in the set is eligible for incorporation into a current transmission instance.

13. The apparatus as in claim 12, wherein a candidate transmission instance is eligible for incorporation into the current transmission instance when the candidate transmission instance may be transmitted in the format of the current transmission instance.

14. The apparatus as in claim 12, further comprising:

a packet metric calculation unit for generating a packet metric for each transmission queue; and

a transmission instance select unit for selecting a transmission instance from the set of candidate transmission instances based on the packet metric values.

15. The apparatus as in claim 14, wherein the packet metric is an accumulation of the bit metrics.

16. The apparatus as in claim 15, wherein the packet metric is calculated as:

17. The apparatus as in claim 15, wherein the packet metric is calculated as:

18. The apparatus as in claim 15, wherein the packet metric is an estimate of instantaneous throughput of the bit metric for transmission of the candidate transmission instance.

19. The apparatus as in claim 10, further comprising:

a queue select unit to select transmission queues for a transmission instance.

20. The apparatus as in claim 19, wherein each queue has an associated quality of service indicator and an associated delay criteria.

21. The apparatus as in claim 20, wherein the quality of service indicator and delay criteria are stored in the memory storage unit with each transmission queue.

22. The apparatus as in claim 19, comprising:

a bit metric calculation unit for each transmission queue,

wherein the queue select unit selects a transmission queue as a function of the bit metrics.

23. The apparatus as in claim 10, wherein each queue has a fixed delay bound.

24. The apparatus as in claim 23, wherein delay is measured as time a queue is stored in the memory storage unit.

25. The apparatus as in claim 24, wherein each delay bound is a function of a fraction of expedited forwarding users.

26. The apparatus as in claim 25, wherein each queue has at least one time stamp, and wherein delay is measured as time elapsed from the one of the at least one time stamp.

27. The apparatus as in claim 26, wherein a timestamp is applied to each octet in a queue.

28. The apparatus as in claim 10, wherein the quality of service indicator identifies a queue as one of:

a best effort flow having a high end-to-end delay tolerance; and

an expedited forwarding flow having low delay tolerance.

29. The apparatus as in claim 28, wherein the quality of service indicator further identifies a queue as one of:

a best effort flow having a high end-to-end delay tolerance;

an expedited forwarding flow having low delay tolerance; and

an assured forwarding flow having a high delay tolerance with a target average throughput.

30. The apparatus as in claim 10, wherein each queue has an associated flow class to identify sensitivity to throughput or sensitivity to delay.

31. The apparatus as in claim 30, wherein a bit metric for a throughput sensitive flow is calculated as:

32. The apparatus as in claim 31, wherein a bit stuffing metric for a throughput sensitive flow is calculated as:

33. The apparatus as in claim 32, wherein a bit metric for a delay sensitive flow is calculated as:

34. The apparatus as in claim 33, wherein a bit stuffing metric for a delay sensitive flow is calculated as:

35. The apparatus as in claim 10, wherein bits from at least one flow are stuffed to format a candidate transmission instance.

36. The apparatus as in claim 35, wherein the bit stuffing metrics are used for bit stuffing in descending order of bit stuffing metrics.

37. The apparatus as in claim 10, wherein if a selected transmission instance is in a single user format, the apparatus converts to the transmission instance to a lower rate available format.

38. The apparatus as in claim 10, wherein the wireless communication system supports multi-user formats, and

Wherein if a selected transmission instance is a multi-user format, the apparatus applies a lower available multi-user format.

39. An apparatus for scheduling transmission instances in a wireless communication system, comprising:

memory storage unit for storing transmission queues, each queue having an associated delay criteria; and

a controller adapted to;

select a packet type for a transmission instance;

determine an estimated throughput;

determine flows supporting the estimated throughput; and

ordering flows according to the delay criteria.

40. The apparatus as in claim 39, wherein the controller is further adapted to:

select a packet type for a transmission instance by;

identifying a number of user bits in a packet for the packet type;

identifying a number of slots for the packet type; and

calculating a ratio of the number of user bits in a packet to the number of slots for the packet type.

41. An apparatus for scheduling transmission instances in a wireless communication system, comprising:

memory storage unit for storing transmission queues, each queue having an associated delay criteria; and

a controller adapted to;

estimate throughput for flows stored in the transmission queues;

determine a quality of service priority for the flows;

sort according to quality of service priorities;

determine an order of flows based on estimated throughput for each flow;

select a flow available for transmission at a highest rate.

42. The apparatus as in claim 41, wherein the controller is further adapted to:

generate a packet available for transmission with a highest number of bits per slot.

43. An apparatus for scheduling transmission instances in a wireless communication system, comprising:

memory storage unit for storing transmission queues, each queue having an associated delay criteria; and

a controller adapted to;

track delay of each queue;

schedule delay sensitive flows according to delay; and

schedule delay insensitive flows according to a ratio of transmission data rate to throughput.

44. The apparatus as in claim 43, wherein delay is measured by a time stamp.

45. A method for scheduling packet transmissions in a communication system, the method comprising:

receiving a channel condition indicators from a plurality of subscriber stations;

comparing the channel condition indicators;

determining delay performance targets for each of the plurality of subscriber stations in response to the comparison, wherein a higher delay performance target is associated with good channel condition and a lower delay performance target is associated with poor channel condition; and

determining a transmission schedule for each the plurality of subscriber stations as a function of the delay performance targets.

46. The method of claim 45, wherein the channel condition indicators correspond to forward link communications to the subscriber stations.

47. The method of claim 45, wherein the channel condition indicator is proportional to channel condition.

48. The method of claim 45, further comprising:

receiving a delay parameter for each of the plurality of subscriber stations;

receiving queue state information for each of the plurality of subscriber stations; and

wherein the transmission schedule is determined as a function of the delay parameter and the queue state information.

49. The method of claim 48, wherein each delay parameter is a function of a quality of service index associated with each subscriber station.

50. The method of claim 48, wherein the queue state information includes age of the data pending in each queue.