Method and system for packet scheduling

• US 8,503,299 B2
• Filed: 05/12/2006
• Issued: 08/06/2013
• Est. Priority Date: 05/12/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Senarath, Nimal, Coverdale, Paul, Li, Hongyi, Periyalwar, Shalini, Teo, Koon Hoo
• Primary Examiner(s): Rinehart, Mark
• Assistant Examiner(s): Cheng, Peter
• Application Number:
  US11/432,476
• Publication Number:
  US 20070019552A1
• Time in Patent Office: 2,643 Days
• Field of Search: 370/235
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method and system for packet scheduling are provided. The method includes: the step of receiving an incoming packet; extracting packet identification information associated with the incoming packet, and assessing a delay budget for the incoming packet in dependence upon its arrival time and the associated information. The system includes: an input module for receiving an incoming packet, and extracting information associated with the incoming packet, and a module for assessing a delay budget for the incoming packet in dependence upon its arrival time and the associated information.

Claims

1. A method of dynamically allocating a delay budget to a packet transmitting from a source to a destination, comprising:

at a packet analyzer between a source and a destination, receiving at least one incoming packet from the source to the destination, wherein at least one incoming packet is a regular interval packet;

extracting information from the incoming packet, the information associating the incoming packet to at least one previously received incoming packets, wherein the information includes packet identification information associating the incoming regular packet to previously received regular interval packets;

assessing a variable delay caused in a communication path from the source to the packet analyzer, based on an arrival time of the at least one previously received regular interval packets, wherein assessing the variable delay caused in a communication path from the source to the packet analyzer, comprises;

sending a request for an assessment packet;

receiving the assessment packet to assess the variable delay; and

determining a delay budget for a downlink from the packet analyzer, based on the variable delay and an end to end delay requirement between the source and the destination; and

outputting the incoming packet with the delay budget from the packet analyzer to a packet scheduler.

2. The method of claim 1, wherein assessing a variable delay comprises evaluating a relative interval of the regular interval packets.

3. The method of claim 1, wherein assessing a variable delay comprises estimating an arrival time distribution of the previously received incoming packets.

4. The method of claim 1, wherein assessing a variable delay comprises estimating a delay distribution of the previously received incoming packets and wherein the received incoming packets is iteratively updated each time another incoming packet is received.

5. The method of claim 1, wherein assessing a variable delay comprises estimating a delay distribution of the previously received incoming packets, and wherein determining a delay budget comprises determining the delay budget based on the delay distribution of the previously received incoming packets.

6. The method of claim 1, wherein assessing a variable delay comprises calculating an average of arrival times of the previously received incoming packets, and wherein determining a delay budget comprises determining the delay budget based on the average of arrival times of the previously received incoming packets.

7. The method of claim 1, wherein extracting comprises identifying packet identification information associating the incoming packet to at least one of a user, a service, one or more data flows or combinations thereof

8. The method of claim 7, wherein determining a delay budget comprises determining the delay budget using a delay requirement associated with the packet identification information.

9. The method of claim 7, wherein identifying comprises identifying at least two associated data flows.

10. The method of claim 9, wherein determining a delay budget comprises determining the delay budget for each associated data flow so as to synchronize the at least two associated data flows.

11. The method of claim 9, wherein the delay budget is the maximum duration the incoming packet can be delayed in one or more next forwarding nodes and associated links, until it reaches the destination, without impacting the required quality of a service.

12. The method of claim 9, further comprising at least one of the following:

recording the arrival time of the incoming packet;

noting the arrival time of the incoming packet; and

marking the arrival time of the incoming packet.

13. A system for dynamically allocating a delay budget to a packet transmitting from a source to a destination, comprising:

an input module for receiving an incoming packet from a source to a destination wherein at least one incoming packet is a regular interval packet, and extracting information from the incoming packet, the information associating the incoming packet to arrival time data associated with previously received incoming packets, wherein the information includes packet identification information associating the incoming regular packet to previously received regular interval packets;

determining an expected arrival time of the incoming packet based at least in part on the arrival time data associated with the previously received incoming packets;

a module for assessing a delay budget for a downlink from the system in dependence upon an arrival time of the incoming packet and the associated information, including;

a first module for assessing a variable delay caused in a communication path from the source to the system, based on an arrival time of the at least one previously received regular interval packets, the first module sending a request for an assessment packet and receiving the assessment packet to assess the variable delay; and

a second module for determining the delay budget for the downlink, based on the variable delay and an end to end delay requirement between the source and the destination; and

an output module for outputting the incoming packet with the delay budget to a packet scheduler.

14. The system of claim 13, wherein the output module comprises a delay budget first output module for outputting the delay budget, and a received packet second output module for outputting the incoming packet received at the input module.

15. The system of claim 13, wherein the output module comprises a module for attaching the delay budget to the incoming packet received at the input module, and outputting the incoming packet with the delay budget.

16. The system of claim 13, further comprising a repository for storing packet information for the assessment.

17. The system of claim 13, wherein the first module assesses a delay distribution of the previously received incoming packets.

18. The system of claim 17, wherein the first module estimates the delay distribution based on the arrival times of the previously received incoming packets.

19. The system of claim 17, wherein the second module iteratively determines the delay budget each time another incoming packet is received.

20. The system of claim 13, wherein the arrival time data associated with the previously received incoming packets comprises an arrival time distribution of the previously received incoming packets.

21. The system of claim 13, wherein the second module determines the delay budget for an incoming regular interval packet based on arrival times of previously received incoming regular interval packets.

22. The system of claim 13, wherein the first module calculates an average of arrival times of the previously received incoming packets, and wherein the second module determines the delay budget using the average of arrival times of the previously received incoming packets.

23. The system of claim 13, wherein the input module comprises a module for identifying packet identification information that associates the incoming packet to at least one of a user, a service, one or more data flows or combinations thereof.

24. The system of claim 13, wherein the delay budget is a delay for the incoming packet and is allowable in one or more next forwarding nodes and associated links, until it reaches the destination, without impacting the required quality of a service.

25. A non-transitory computer-readable medium storing computer executable instructions for use in the execution of a method of dynamically allocating a delay budget to a packet transmitting from a source to a destination, the method comprising:

receiving at a packet analyzer an incoming packet from a source to a destination, wherein at least one incoming packet is a regular interval packet;

extracting information from the incoming packet, the information associating the incoming packet to arrival time data associated with previously received incoming packets, wherein the information includes packet identification information associating the incoming regular packet to previously received regular interval packets;

assessing a variable delay caused in a communication path from the source to the packet analyzer, based on an arrival time of the at least one previously received regular interval packets, wherein assessing the variable delay caused in a communication path from the source to the packet analyzer, comprises;

sending a request for an assessment packet;

receiving the assessment packet to assess the variable delay;

determining an expected arrival time of the incoming packet based at least in part on the arrival time data associated with the previously received incoming packets;

determining a delay budget for a downlink to the destination, based on the variable delay and an end to end delay requirement between the source and the destination; and

outputting the incoming packet with the delay budget to a packet scheduler.

26. A method of dynamically allocating a delay budget to a packet transmitting from a source to a destination, comprising:

at a packet analyzer between a source and a destination, receiving at least one incoming packet from the source to the destination, wherein at least one incoming packet is a regular interval packet;

extracting information from the incoming packet, the information associating the incoming packet to at least one previously received incoming packets, wherein the information includes packet identification information associating the incoming regular packet to previously received regular interval packets;

assessing a variable delay caused in a communication path from the source to the packet analyzer, based on an arrival time of the at least one previously received regular interval packets, wherein assessing the variable delay caused in a communication path from the source to the packet analyzer, comprises;

sending a request for an assessment packet;

receiving the assessment packet to assess the variable delay; and

evaluating a relative interval of the regular interval packets; and

determining a delay budget for a downlink from the packet analyzer, based on the variable delay and an end to end delay requirement between the source and the destination; and

outputting the incoming packet with the delay budget from the packet analyzer to a packet scheduler.