Distributed forward link schedulers for multi-carrier communication systems

• US 8,331,377 B2
• Filed: 02/27/2006
• Issued: 12/11/2012
• Est. Priority Date: 05/05/2004
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Attar, Rashid A., Black, Peter J., Gurelli, Mehmet, Yavuz, Mehmet, Bhushan, Naga
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): CHAU, PETER P
• Application Number:
  US11/364,384
• Publication Number:
  US 20060146721A1
• Time in Patent Office: 2,479 Days
• Field of Search: 370/395.4, 370/310, 370/395.42 415 416 422 428
• US Class Current: 370/395.42
• 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/0021 in which the algorithm uses adaptive thresholds
• CPC Class Codes: H04L 1/20 using signal quality detector
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS
• CPC Class Codes: H04W 72/569 of the traffic information

Abstract

Embodiments disclosed here relate to scheduling packet transmission in a multi-carrier communication system. In an embodiment, a master scheduler having at least one processor and at least one memory operably connected to the at least one processor is adapted to execute instructions stored in the at least one memory, the instructions comprising selecting a packet with a highest packet metric from among candidate packets from one carrier of a plurality of carriers, whereby expedited forwarding flows do not have a higher metric on another carrier.

Claims

1. A forward link scheduler, comprising:

a master scheduler, comprising;

at least one processor, wherein said at least one processor corresponds to at least one sector; and

at least one memory operably connected to said at least one processor, wherein said master scheduler executes instructions stored in said at least one memory, said instructions comprising;

selecting a first carrier of a plurality of carriers for transmission of a plurality of packets of an expedited forwarding flow with multi-carrier assignment, wherein a plurality of candidate packets comprise the plurality of packets of the expedited forwarding flow, wherein a first candidate packet is associated with the first carrier and a second candidate packet is associated with another carrier of the plurality of carriers, wherein at least one of the plurality of packets of the expedited forwarding flow is associated with the first candidate packet and also with the second candidate packet, and wherein the at least one of the plurality of packets of the expedited forwarding flow associated with the first carrier has a highest packet metric of the at least one of the plurality of packets of the expedited forwarding flow selected for the first carrier and any other carrier of the plurality of carriers, wherein a packet metric is calculated as;

2. The forward link scheduler according to claim 1, wherein said instructions further comprise:

buffering the plurality of packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for the other carriers of said plurality of carriers to serve.

3. The forward link scheduler according to claim 1, wherein said instructions further comprise:

updating a queue state for flows served by said first carrier.

4. The forward link scheduler according to claim 1, wherein said selecting the first carrier is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached.

5. The forward link scheduler according to claim 1, wherein said instructions further comprise:

updating a packet metric for candidate packet transmissions for the other carriers of said plurality of carriers.

6. The forward link scheduler according to claim 1, wherein said instructions further comprise:

buffering the plurality of packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for the other carriers of said plurality of carriers to serve;

updating a queue state for flows served by said first carrier, wherein said selecting the first carrier is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached; and

updating a packet metric for candidate packet transmissions for the other carriers of said plurality of carriers.

7. The forward link scheduler according to claim 1, further comprising at least one candidate packet generator coupled to said master scheduler, wherein said at least one candidate packet generator comprises a memory, and wherein said at least one candidate packet generator executes instructions stored in said memory, the instructions executed by the at least one candidate packet generator comprising generating a set of candidate packet transmission instances, selecting one candidate packet among a set, and maximizing a packing efficiency.

8. The forward link scheduler according to claim 7, further comprising a slave scheduler coupled to said master scheduler, wherein said slave scheduler comprises a memory, and wherein said slave scheduler executes instructions stored in said memory of the slave scheduler, the instructions executed by the slave scheduler comprising executing a shadow routine of said master scheduler.

9. The forward link scheduler according to claim 8, further comprising at least one master processor having a memory coupled to said master scheduler, and at least one packet builder having a memory coupled to said master scheduler, wherein said at least one master processor executes instructions stored in said memory of the at least one master processor, the instructions executed by the at lest one master processor comprising sending a packet over an air interface, and wherein said at least one packet builder executes instructions stored in said memory of the at least one packet builder, the instructions executed by the at least one packet builder comprising generating packets based on a packet format provided by said master scheduler.

10. A distributed forward link scheduler, comprising:

a plurality of forward link processors, wherein said plurality of forward link processors correspond to a plurality of sectors;

a master scheduler coupled to said plurality of forward link processors comprising;

at least one memory operably connected to at least one of said plurality of forward link processors, wherein said at least one of said plurality of forward link processors executes instructions stored in said at least one memory, said instructions comprising;

selecting a first carrier of a plurality of carriers for transmission of a plurality of packets of an expedited forwarding flow with multi-carrier assignment, wherein a plurality of candidate packets comprise the plurality of packets of the expedited forwarding flow, wherein a first candidate packet is associated with the first carrier and a second candidate packet is associated with another carrier of the plurality of carriers, wherein at least one of the plurality of packets of the expedited forwarding flow is associated with the first candidate packet and also with the second candidate packet, and wherein the at least one of the plurality of packets of the expedited forwarding flow associated with the first carrier has a highest packet metric of the at least one of the plurality of packets of the expedited forwarding flow selected for the first carrier and any other carrier of the plurality of carriers, wherein a packet metric is calculated as;

11. The distributed forward link scheduler according to claim 10, wherein said instructions further comprise:

buffering the plurality of packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for the other carriers of said plurality of carriers to serve;

updating a queue state for flows served by said first carrier, wherein said selecting the first carrier is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached; and

updating a packet metric for candidate packet transmissions for the other carriers of said plurality of carriers.

12. The distributed forward link scheduler according to claim 10, further comprising at least one candidate packet generator coupled to said plurality of forward link processors, wherein said at least one candidate packet generator comprises a memory, and wherein said at least one candidate packet generator executes instructions stored in said memory, the instructions executed by the at least one candidate packet generator comprising generating a set of candidate packet transmission instances, selecting one candidate packet among a set, and maximizing a packing efficiency.

13. The distributed forward link scheduler according to claim 12, further comprising a slave scheduler coupled to said plurality of forward link processors, wherein said slave scheduler comprises a memory, and wherein said slave scheduler executes instructions stored in said memory of the slave scheduler, the instructions executed by the slave scheduler comprising executing a shadow routine of said master scheduler.

14. The distributed forward link scheduler according to claim 13, further comprising at least one master processor having a memory coupled to said plurality of forward link processors, and at least one packet builder having a memory coupled to said plurality of forward link processors, wherein said at least one master processor executes instructions stored in said memory of the at least one master processor, the instructions executed by the at least one master processor comprising sending a packet over an air interface, and wherein said at least one packet builder executes instructions stored in said memory of the at least one packet builder, the instructions executed by the at least one packet builder comprising generating packets based on a packet format provided by said master scheduler.

15. A non-transitory, computer-readable medium embodying instructions executable by a processor to:

select a first carrier of a plurality of carriers for transmission of a plurality of packets of an expedited forwarding flow with multi-carrier assignment, wherein a plurality of candidate packets comprise the plurality of packets of the expedited forwarding flow, wherein a first candidate packet is associated with the first carrier and a second candidate packet is associated with another carrier of the plurality of carriers, wherein at least one of the plurality of packets of the expedited forwarding flow is associated with the first candidate packet and also with the second candidate packet, and wherein the at least one of the plurality of packets of the expedited forwarding flow associated with the first carrier has a highest packet metric of the at least one of the plurality of packets of the expedited forwarding flow selected for the first carrier and any other carrier of the plurality of carriers, wherein a packet metric is calculated as;

16. The non-transitory, computer-readable medium of claim 15, further comprising instructions to:

buffer the plurality of packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for the other carriers of said plurality of carriers to serve.

17. The non-transitory, computer-readable medium of claim 15, further comprising instructions to:

update a queue state for flows served by said first carrier.

18. The non-transitory, computer-readable medium of claim 15, wherein said selecting the first carrier is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached.

19. The non-transitory, computer-readable medium of claim 15, further comprising instructions to:

update a packet metric for candidate packet transmissions for the other carriers of said plurality of carriers.

20. The non-transitory, computer-readable medium of claim 15, further comprising instructions to:

buffer the plurality of packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for the other carriers of said plurality of carriers to serve;

update a queue state for flows served by said first carrier, wherein said selecting the first carrier is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached; and

update a packet metric for candidate packet transmissions for the other carriers of said plurality of carriers.

21. A method, implemented in an apparatus, for scheduling packet transmission in a multi-carrier communication system, the method comprising:

selecting a first carrier of a plurality of carriers for transmission of a plurality of packets of an expedited forwarding flow with multi-carrier assignment, wherein a plurality of candidate packets comprise the plurality of packets of the expedited forwarding flow, wherein a first candidate packet is associated with the first carrier and a second candidate packet is associated with another carrier of the plurality of carriers, wherein at least one of the plurality of packets of the expedited forwarding flow is associated with the first candidate packet and also with the second candidate packet, and wherein the at least one of the plurality of packets of the expedited forwarding flow associated with the first carrier has a highest packet metric of the at least one of the plurality of packets of the expedited forwarding flow selected for the first carrier and any other carrier of the plurality of carriers, wherein a packet metric is calculated as;

22. The method of claim 21, further comprising:

buffering the plurality of packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for the other carriers of said plurality of carriers to serve.

23. The method of claim 21, further comprising:

updating a queue state for flows served by said first carrier.

24. The method of claim 21, wherein said selecting the first carrier is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached.

25. The method of claim 21, further comprising:

updating a packet metric for candidate packet transmissions for the other carriers of said plurality of carriers.

26. The method of claim 21, further comprising:

buffering the plurality of packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for the other carriers of said plurality of carriers to serve;

updating a queue state for flows served by said first carrier, wherein said selecting the first carrier is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached; and

updating a packet metric for candidate packet transmissions for the other carriers of said plurality of carriers.

27. An apparatus for scheduling packet transmission across a plurality of carriers, comprising:

at least one candidate packet generator configured to select a first candidate packet for transmission over a first carrier of the plurality of carriers and a second candidate packet for transmission over another carrier of the plurality of carriers from a plurality of packets, wherein the first and second candidate packets correspond to an expedited forwarding flow; and

a master scheduler configured to;

identify the first candidate packet corresponding to the expedited forwarding flow, wherein with first candidate packet has a highest packet metric from among the first candidate packet and any other candidate packets corresponding to the expedited forwarding flow, wherein a packet metric is calculated as;

28. The apparatus of claim 27, wherein the master scheduler is further configured to:

buffer packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for a carrier other than the first carrier to serve.

29. The apparatus of claim 27, wherein the master scheduler is further configured to:

update a queue state for flows served by said first carrier.

30. The apparatus of claim 27, wherein the master scheduler is further configured to:

select said first candidate packet with the highest metric, wherein said selecting is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached.

31. The apparatus of claim 27, wherein the master scheduler is further configured to:

update a packet metric for candidate packets corresponding to the expedited forwarding flow selected for carriers other than the first carrier.

32. A method, implemented in an apparatus, for scheduling packet transmission in a multi-carrier communication system, the method comprising:

selecting a first candidate packet for transmission over a first carrier of a plurality of carriers and a second candidate packet for transmission over another carrier of the plurality of carriers from a plurality of packets, wherein the first and second candidate packets correspond to an expedited forwarding flow;

identifying the first candidate packet corresponding to the expedited forwarding flow, wherein with first candidate packet has a highest packet metric from among the first candidate packet and any other candidate packets corresponding to the expedited forwarding flow, wherein a packet metric is calculated as;

33. The method of claim 32, further comprising:

buffering packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for a carrier other than the first carrier to serve.

34. The method of claim 32, further comprising:

updating a queue state for flows served by said first carrier.

35. The method of claim 32, further comprising:

selecting said first candidate packet with the highest metric, wherein said selecting is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached.

36. The method of claim 32, further comprising:

updating a packet metric for candidate packets corresponding to the expedited forwarding flow selected for carriers other than the first carrier.

37. A non-transitory, computer-readable medium embodying instructions executable by a processor to:

select a first candidate packet for transmission over a first carrier of a plurality of carriers and a second candidate packet for transmission over another carrier of the plurality of carriers from a plurality of packets, wherein the first and second candidate packets correspond to an expedited forwarding flow;

identify the first candidate packet corresponding to the expedited forwarding flow, wherein with first candidate packet has a highest packet metric from among the first candidate packet and any other candidate packets corresponding to the expedited forwarding flow, wherein a packet metric is calculated as;

38. The non-transitory, computer-readable medium of claim 37, further embodying instructions executable by a processor to:

buffer packets of said expedited forwarding flow in a queue, whereby there are no packets in said queue for a carrier other than the first carrier to serve.

39. The non-transitory, computer-readable medium of claim 37, further embodying instructions executable by a processor to:

update a queue state for flows served by said first carrier.

40. The non-transitory, computer-readable medium of claim 37, further embodying instructions executable by a processor to:

select said first candidate packet with the highest metric, wherein said selecting is based upon whether a user has sufficient data according to a transmission criteria or said user'"'"'s delay bound is reached.

41. The non-transitory, computer-readable medium of claim 37, further embodying instructions executable by a processor to:

update a packet metric for candidate packets corresponding to the expedited forwarding flow selected for carriers other than the first carrier.