Method and system for packet scheduling

• US 20070019552A1
• Filed: 05/12/2006
• Published: 01/25/2007
• Est. Priority Date: 05/12/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Periyalwar, Shalini, Senarath, Nimal, Li, Hongyi, Coverdale, Paul, Teo, Koon
• Granted Patent: US 8,503,299 B2
• Time in Patent Office: Days
• 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 packet scheduling, comprising:

receiving an incoming packet;

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

2. A method according to claim 1, wherein the step of assessing includes the step of:

assessing the delay budget for the incoming budget based on a delay distribution associated with the associated information.

3. A method according to claim 1, wherein the step of assessing includes the step of:

estimating an arrival time distribution based on the associated information to assess the delay budget.

4. A method according to claim 2, wherein the step of estimating is iteratively updated each time another incoming packet is received.

5. A method according to claim 1, wherein the step of assessing includes the step of:

evaluating an expected arrival time of the incoming packet based on the associated information to assess the delay budget.

6. A method according to claim 1, wherein the incoming packet is a regular interval packet and the associated information including packet identification information associating the incoming regular packet to previously received regular interval packets, the step of assessing including the step of:

assessing the delay budget for the incoming regular interval packet based on the arrival times of the previously received regular interval packets.

7. A method according to claim 6, wherein the step of assessing includes the step of:

evaluating a relative interval of the regular interval packets.

8. A method according to claim 1, wherein the step of assessing includes the step of:

sending an assessment packet; and

receiving a return packet associated with the assessment packet to assess the delay budget.

9. A method according to claim 2, wherein the associated information includes packet identification information associating the incoming packet to previously received incoming packets, the step of assessing includes the step of:

assessing the delay budget based on the assessed external delay distribution of the previously received incoming packets.

10. A method according to claim 2, wherein the associated information include packet identification information associating the incoming packet to previously received incoming packets, the step of assessing includes the step of:

estimating the delay distribution based on the previously received incoming packets.

11. A method according to claim 1, wherein the associated information including packet identification information associating the incoming packet to previously received incoming packets, the step of assessing includes the step of:

assessing the delay budget based on an average of arrival times of the previously received incoming packets.

12. A method according to claim 1, wherein the associated information includes packet identification information associating the incoming packet to a previously received time-stamped incoming packet, the step of assessing includes the step of:

assessing the delay budget for the incoming packet with a time-stamp using the previously received time-stamped incoming packet.

13. A method according to claim 1, wherein the step of extracting includes the step of:

identifying packet identification information associating the incoming packet to at least one of a user, a service, one or more data flows, one or more previously received incoming packets or combinations thereof.

14. A method according to claim 13, wherein the step of assessing includes the step of:

determining the delay budget using a delay requirement associated with the associated information.

15. A method according to claim 13, wherein the step of identifying includes the step of:

identifying at least two associated data flows.

16. A method according to claim 15, wherein the step of assessing includes the step of:

determining the delay budget for each associated data flow so as to synchronize the at least two associated date flows.

30. A method according to claim 1, 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 a destination, without impacting the required quality of a service.

31. A method according to claim 1, further comprising as least one of the following steps of:

recording the arrival time of the incoming packet;

noting the arrival time of the incoming packet;

marking the arrival time of the incoming packet.

17. A system for packet scheduling, comprising:

an input module for receiving an incoming packet, and extracting information associated with the incoming packet;

a module for assessing a delay budget for the incoming packet in dependence upon its arrival time and the associated information; and

an output module for outputting the delay budget.

18. A system according to claim 17, wherein the output module includes:

a delay budget first output module for outputting the delay budget; and

a received packet second output module for outputting the packet received at the input module.

19. A system according to claim 17, wherein the output module includes:

a module for attaching the delay budget to the packet received at the input module and outputting the packet with the delay budget.

20. A system according to claim 17, further including a repository for storing packet information for the assessment.

21. A system according to claim 17, wherein the assessing module assesses the delay budget for the incoming packet based on a delay distribution associated with the associated information.

22. A system according to claim 17, wherein the assessing module evaluates an expected arrival time of the incoming packet based on an arrival time distribution associated with the associated information.

23. A system according to claim 17, wherein the assessing module assesses the delay budget for an incoming regular interval packet based on arrival times of previously received incoming regular interval packets.

24. A system according to claim 17, wherein the assessing module sends an assessment packet and receives a return packet associated with the assessment packet, and estimates the delay for the assessment packet.

25. A system according to claim 17, wherein the associated information includes packet identification information associating the incoming packet to a previously received time-stamped incoming packet, the assessing module assessing the delay budget for the incoming packet with a time-stamp, using the previously received time-stamped incoming packet.

26. A system according to claim 21, wherein the associated information includes packet identification information associating the incoming packet to one or more previously received incoming packets, the assessing module estimating the delay distribution based on the previously received incoming packets.

27. A system according to claim 17, wherein the associated information includes packet identification information associating the incoming packet to one or more previously received incoming packets, the assessing module assessing the delay budget based on an average of arrival times of the previously received incoming packets.

28. A system according to claim 17, wherein the input module includes:

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, one or more previously received incoming packets or combinations thereof.

29. A system according to claim 21, wherein the assessing module iteratively assesses the delay budget each time another packet is received.

32. A system according to claim 17, 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 a destination, without impacting the required quality of a service.

33. A computer-readable medium having computer-executable instructions for use in the execution of a method of packet scheduling, the method comprising the step of.

receiving an incoming packet;

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