Method and apparatus for adaptive delay management

• US 8,472,322 B2
• Filed: 05/05/2005
• Issued: 06/25/2013
• Est. Priority Date: 05/05/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Black, Peter J., Gurelli, Mehmet I., Yavuz, Mehmet, Bhushan, Naga
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): KAVLESKI, RYAN C
• Application Number:
  US11/123,479
• Publication Number:
  US 20050281278A1
• Time in Patent Office: 2,973 Days
• Field of Search: 370/465, 370/395.4, 370/468, 370/231, 370/235
• US Class Current: 370/235
• 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 at a receiver from a plurality of mobile users, wherein the channel condition indicators correspond to forward link communications;

determining a delay criterion for the plurality of mobile users, wherein the delay criterion for the plurality of mobile users is based on data to be transmitted, the data being either high priority data or non-high priority data, the high priority data being delay sensitive and the non-high priority data being capacity sensitive; and

determining a transmission schedule for a plurality of queues including data associated with the plurality of mobile users, wherein the high priority data is scheduled for transmission before the non-high priority data, the non-high priority data is scheduled based at least in part on the channel condition indicators and an age of the non-high priority data, and the transmission schedule is a function of the delay criterion and a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

2. The method of claim 1, further comprising:

selecting a queue for incorporation into a transmission instance based at least in part on each bit metric associated with each bit pending in the queue.

3. The method of claim 1, wherein the transmission instance is a combination of a transmission format and a particular set of bits from the selected queue that may be carried by a packet of the transmission format.

4. The method of claim 1, wherein each bit metric of the plurality of bit metrics is represented by a polynomial with a plurality of terms, wherein each term of the polynomial includes a coefficient, and wherein only one term of the polynomial is nonzero at any given time.

5. 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, wherein generating the set of candidate transmission instances comprises calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow;

selecting one candidate transmission instance from the set; and

preparing the selected candidate transmission instance for transmission by a transmitter.

6. The method as in claim 5, wherein selecting one candidate transmission instance comprises:

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

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

7. The method as in claim 5, wherein the throughput sensitivity is determined on a per flow per user basis.

8. 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 criterion for the plurality of mobile users, wherein the delay criterion for the plurality of mobile users is based on data to be transmitted, the data being either high priority data or non-high priority data, the high priority data being delay sensitive and the non-high priority data being capacity sensitive; and

means for determining a transmission schedule for a plurality of queues including data associated with the plurality of mobile users, wherein the high priority data is scheduled for transmission before the non-high priority data, the non-high priority data is scheduled based at least in part on the channel condition indicators and an age of the non-high priority data, and the transmission schedule is a function of the delay criterion and a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

9. 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, wherein the means for generating the set of candidate transmission instances comprises means for calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow;

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

preparing the selected candidate transmission instance for transmission.

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

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

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

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

a memory storage unit for storing transmission queues, each queue having an associated delay criterion, wherein the delay criterion is based on data to be transmitted, the data being either high priority data or non-high priority data, the high priority data being delay sensitive and the non-high priority data being capacity sensitive;

a queue select unit for selecting a transmission queue of the stored transmission queues as a function of the delay criterion, wherein queues with high priority data are scheduled for transmission before queues with non-high priority data, and the queues with non-high priority data are scheduled based at least in part on channel condition indicators and an age of the non-high priority data; and

a bit metric calculation unit for calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, and wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

12. The apparatus as in claim 11, wherein the queue select unit selects a transmission queue as a function of the bit metric associated with each transmission queue.

13. 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.

14. The apparatus as in claim 13, 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.

15. The apparatus as in claim 13, 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.

16. The apparatus as in claim 15, wherein the packet metric comprises an accumulation of the bit metrics associated with each transmission queue.

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

PacketMetric=AccumulatedBitMetric/Ng

wherein Ng is the generic span of a candidate transmission instance and the AccumulatedBitMetric is a sum of the bit metrics corresponding to all bits included in the candidate instance.

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

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

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

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

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

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

23. The apparatus as in claim 20, wherein the queue select unit selects a transmission queue as a function of the bit metric associated with the transmission queue.

24. The apparatus as in claim 11, wherein each queue has a fixed delay bound.

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

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

27. The apparatus as in claim 26, 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.

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

29. The apparatus as in claim 11, 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.

30. The apparatus as in claim 29, 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.

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

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

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

34. The apparatus as in claim 11, 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.

35. The apparatus as in claim 11, 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.

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

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

a queue select unit for selecting a transmission queue of the stored transmission queues as a function of the delay criterion and a plurality of bit metrics;

wherein each queue has an associated flow class to identify sensitivity to throughput or sensitivity to delay;

wherein the plurality of bit metrics comprises at least a first bit metric for a throughput sensitive flow calculated as;

37. The apparatus as in claim 36, wherein a first bit stuffing metric for the throughput sensitive flow is calculated as:

38. The apparatus as in claim 37, wherein a second bit stuffing metric for a delay sensitive flow is calculated as:

DS_BSM=AccelerationFactor*CurrentDelay+AccelerationOffset

wherein AccelerationFactor is a factor applied to the delay sensitive flow to normalize the delay bound, and AccelerationOffset is a function of the AccelerationFactor.

39. The apparatus as in claim 38, wherein the plurality of bit metrics comprises at least a second bit metric for the delay sensitive flow calculated as:

DS_BM=DSBitMetricValue

wherein DSBitMetricValue is defined for the delay sensitive flow and used for soft prioritization.

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

a memory storage unit for storing transmission queues, each queue having an associated delay criterion, wherein the delay criterion is based on data to be transmitted, the data being either high priority data or non-high priority data, the high priority data being delay sensitive and the non-high priority data being capacity sensitive; and

a controller configured to;

calculate a bit metric associated with each of the transmission queues, wherein each of the transmission queues stores an instance of an application flow, wherein the application flow is divided into a plurality of instances;

wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow;

select a packet type for a transmission instance;

determine an estimated throughput;

determine flows supporting the estimated throughput; and

order flows according to the delay criterion and bit metrics, wherein queues with high priority data are scheduled for transmission before queues with non-high priority data, and the queues with non-high priority data are scheduled based at least in part on channel condition indicators and an age of the non-high priority data.

41. The apparatus as in claim 40, wherein the controller is further configured 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.

42. 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 criterion; and

a controller configured to;

estimate throughput for flows stored in the transmission queues;

calculate a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow;

determine a quality of service priority for the flows;

sort according to quality of service priorities and bit metrics;

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

select a flow available for transmission at a highest rate based on the determined order of flows.

43. The apparatus as in claim 42, wherein the controller is further configured to:

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

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

receiving channel condition indicators at a receiver 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 conditions and a lower delay performance target is associated with poor channel conditions; and

determining a transmission schedule for a plurality of queues including data associated with the plurality of subscriber stations as a function of the delay performance targets and a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

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

46. The method of claim 44, wherein the channel condition indicators are proportional to the channel conditions.

47. The method of claim 44, 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.

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

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

50. A machine-readable medium being a non-transitory medium having instructions for execution by a processor for scheduling transmission instances in a wireless communication system, the instructions comprising code for:

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, wherein generating the set of candidate transmission instances comprises calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow;

selecting one candidate transmission instance from the set; and

preparing the selected candidate transmission instance for transmission.

51. A machine-readable medium being a non-transitory medium having instructions for execution by a processor for scheduling transmission instances in a wireless communication system, the instructions comprising code for:

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

determining a delay criterion for the plurality of mobile users, wherein the delay criterion for the plurality of mobile users is based on data to be transmitted, the data being either high priority data or non-high priority data, the high priority data being delay sensitive and the non-high priority data being capacity sensitive; and

determining a transmission schedule for a plurality of queues including data associated with the plurality of mobile users, wherein the high priority data is scheduled for transmission before the non-high priority data, the non-high priority data is scheduled based at least in part on the channel condition indicators and an age of the non-high priority data, and the transmission schedule is a function of the delay criterion and a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

52. A machine-readable medium being a non-transitory medium having instructions for execution by a processor for scheduling transmission instances in a wireless communication system, the instructions comprising code for:

storing transmission queues, each queue having an associated delay criterion;

calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow;

estimating throughput for flows stored in the transmission queues;

determining a quality of service priority for the flows;

sorting according to quality of service priorities;

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

selecting a flow available for transmission at a highest rate based on the determined order of flows and bit metrics.

53. A machine-readable medium being a non-transitory medium having instructions for execution by a processor for scheduling packet transmissions in a communication system, the instructions comprising code for:

receiving 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 conditions and a lower delay performance target is associated with poor channel conditions; and

determining a transmission schedule for a plurality of queues including data associated with the plurality of subscriber stations as a function of the delay performance targets and a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

54. A machine-readable medium being a non-transitory medium having instructions for execution by a processor for scheduling transmission instances in a wireless communication system, the instructions comprising code for:

storing transmission queues, each queue having an associated delay criterion, wherein the delay criterion is based on data to be transmitted, the data being either high priority data or non-high priority data, the high priority data being delay sensitive and the non-high priority data being capacity sensitive; and

selecting a transmission queue from the stored transmission queues as a function of the delay criterion and a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, wherein queues with high priority data are scheduled for transmission before queues with non-high priority data, and the queues with non-high priority data are scheduled based at least in part on channel condition indicators and an age of the non-high priority data;

wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

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

storing transmission queues at a base station, each queue having an associated delay criterion, wherein the delay criterion, is based on data to be transmitted, the data being either high priority data or non-high priority data, the high priority data being delay sensitive and the non-high priority data being capacity sensitive; and

selecting a transmission queue from the stored transmission queues as a function of the delay criterion and a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, wherein queues with high priority data are scheduled for transmission before queues with non-high priority data, and the queues with non-high priority data are scheduled based at least in part on channel condition indicators and an age of the non-high priority data;

wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow.

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

storing transmission queues at a base station, each queue having an associated delay criterion;

calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues;

wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow;

estimating throughput for flows stored in the transmission queues;

determining a quality of service priority for the flows;

sorting according to quality of service priorities;

determining an order of flows based on estimated throughput for each flow and bit metrics; and

selecting a flow available for transmission at a highest rate based on the determined order of flows.

57. An apparatus for scheduling packet transmissions in a communication system, comprising:

a receiver module for receiving channel condition indicators from a plurality of subscriber stations;

a comparator module for comparing the channel condition indicators;

a delay performance module for 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 conditions and a lower delay performance target is associated with poor channel conditions;

a bit metric module for calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, the plurality of queues being associated with the plurality of subscriber stations;

wherein each bit metric is calculated based at least in part on whether the data in the associated queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow; and

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

58. An apparatus for scheduling packet transmissions in a communication system comprising:

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

means for comparing the channel condition indicators;

means for 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 conditions and a lower delay performance target is associated with poor channel conditions;

means for calculating a plurality of bit metrics, wherein a bit metric is calculated for and assigned to each bit pending in each of the plurality of queues, the plurality of queues being associated with the plurality of subscriber stations;

wherein each bit metric is calculated based at least in part on whether the data in the associated transmission queue is delay sensitive or throughput sensitive, wherein bit metrics for throughput sensitive flows are based on an inverse of a difference between an averaged total throughput of the flow and a target throughput of the flow; and

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