EMPIRICAL SCHEDULING OF NETWORK PACKETS

• US 20090207732A1
• Filed: 04/29/2009
• Published: 08/20/2009
• Est. Priority Date: 09/17/2003
• Status: Active Grant

• Current Assignee: Novanta Inc.
• Original Assignee: Rivulet Communications Incorporated (Novanta Inc.)
• Inventors: Rogers, Steven A.
• Granted Patent: US 7,911,963 B2
• Time in Patent Office: Days
• US Class Current: 370/232
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5628 Testing
• CPC Class Codes: H04L 2012/5671 Support of voice
• CPC Class Codes: H04L 2012/5675 Timeslot assignment, e.g. TDMA
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling

Abstract

A method of transmitting packets over a network includes steps of partitioning a packet delivery schedule into discrete time slots; transmitting a plurality of test packets from a first endpoint on the network to an intended recipient in the network using different time slots; evaluating the reliability of the network to transmit the plurality of test packets in each time slot; and selecting one or more time slots in the delivery schedule according to the evaluation step.

Claims

1. A method of transmitting packets over a packet-switched network, comprising the steps of:

(1) transmitting a plurality of test packets over a single network path of the packet-switched network between a first network endpoint and a second network endpoint during a plurality of different delivery times, each delivery time corresponding to a candidate time within a time reference frame during which a packet can be transmitted from the first network endpoint to the second network endpoint;

(2) empirically determining on the basis of packet statistics of the test packets which of the plurality of different delivery times corresponds to favorable traffic conditions for transmitting packets between the first network endpoint and second network endpoint over the single network path of the packet-switched network; and

(3) scheduling data packets for delivery over the network from the first network endpoint to the second network endpoint during one or more delivery times empirically determined in step (2) to correspond to favorable traffic conditions.

2. The method of claim 1, wherein the test packets have characteristics emulating data packets that will be transmitted between the first network endpoint and the second network endpoint.

3. The method of claim 1, wherein step (2) comprises the step of evaluating packet latencies associated with the test packets.

4. The method of claim 1, wherein step (2) comprises the step of evaluating dropped packet rates associated with the test packets.

5. The method of claim 1, wherein step (1) comprises the step of transmitting the test packets at a data rate corresponding to an expected connection bandwidth between the first network endpoint and the second network endpoint.

6. The method of claim 1, wherein step (2) comprises the step of the first network endpoint performing an evaluation of packet statistics associated with the test packets transmitted over the plurality of different delivery times.

7. The method of claim 1, wherein step (1) comprises the step of transmitting the test packets at a priority level lower than a priority level of existing real-time data traffic on the packet-switched network.

8. The method of claim 1, wherein the test packets and the data packets comprise Internet Protocol (IP) packets transmitted over the packet-switched network.

9. The method of claim 8, wherein the IP packets are scheduled for transmission within a frame that is synchronized to a clock.

10. The method of claim 1, wherein the test packets are transmitted at a priority level that is lower than the data packets in step (3), but higher than other data packets containing other data transmitted on the network.

11. The method of claim 1, wherein the data packets comprise voice data.

12. The method of claim 1, further comprising the step of repeating steps (1) through (3) for each side of a two-way connection between two network endpoints in the network.

13. The method of claim 1, wherein the network is a packet-switched network comprising packet switches that maintain packet queues.

14. The method of claim 13, wherein each packet switch comprises at least two packet queues, a higher-priority queue for transmitting the data packets of step (3) and a lower-priority queue for transmitting the test packets of step (1).

15. The method of claim 1, wherein step (3) comprises the step of synchronously transmitting the plurality of data packets from the first network endpoint to the second network endpoint.

16. The method of claim 1, further comprising establishing the time reference frame by decomposing a time period into a plurality of smaller time periods.

17. An apparatus comprising:

a computer having a network interface and programmed with computer-executable instructions that, when executed, perform the steps of;

(1) transmitting a plurality of test packets over a single network path of a packet-switched network between a first network endpoint and a second network endpoint during a plurality of different delivery times, each delivery time corresponding to a candidate time within a time reference frame during which a packet can be transmitted from the first network endpoint to the second network endpoint;

(2) empirically determining on the basis of packet statistics of the test packets which of the plurality of different delivery times corresponds to favorable traffic conditions for transmitting packets between the first network endpoint and second network endpoint over the single network path of the packet-switched network; and

(3) scheduling data packets for delivery over the network from the first network endpoint to the second network endpoint during one or more delivery times empirically determined in step (2) to correspond to favorable traffic conditions.

18. The apparatus of claim 17, wherein the test packets have characteristics emulating data packets that will be transmitted between the first network endpoint and the second network endpoint.

19. The apparatus of claim 17, wherein step (2) comprises the step of evaluating packet latencies associated with the test packets.

20. The apparatus of claim 17, wherein step (2) comprises the step of evaluating dropped packet rates associated with the test packets.

21. The apparatus of claim 17, wherein step (1) comprises the step of transmitting the test packets at a data rate corresponding to an expected connection bandwidth between the first network endpoint and the second network endpoint.

22. The apparatus of claim 17, wherein step (2) comprises the step of the first network endpoint performing an evaluation of packet statistics associated with the test packets transmitted over the plurality of different delivery times.

23. The apparatus of claim 17, wherein step (1) comprises the step of transmitting the test packets at a priority level lower than a priority level of existing real-time data traffic on the packet-switched network.

24. The apparatus of claim 17, wherein the test packets and the data packets comprise Internet Protocol (IP) packets transmitted over the packet-switched network.

25. The apparatus of claim 24, wherein the IP packets are scheduled for transmission within a frame that is synchronized to a clock.

26. The apparatus of claim 17, wherein the test packets are transmitted at a priority level that is lower than the data packets in step (3), but higher than other data packets containing other data transmitted on the network.

27. The apparatus of claim 17, wherein the data packets comprise voice data.

28. The apparatus of claim 17, wherein the network is a packet-switched network comprising packet switches that maintain packet queues.

29. The apparatus of claim 28, wherein each packet switch comprises at least two packet queues, a higher-priority queue for transmitting the data packets of step (3) and a lower-priority queue for transmitting the test packets of step (1).

30. The apparatus of claim 17, wherein step (3) comprises the step of synchronously transmitting the plurality of data packets from the first network endpoint to the second network endpoint.

31. The apparatus of claim 17, wherein the instructions when executed further establish the time reference frame by decomposing a time period into a plurality of smaller time periods.

32. A computer-readable storage medium having stored thereon executable instructions that, when executed by a computer, perform:

(1) transmitting a plurality of test packets over a single network path of the packet-switched network between a first network endpoint and a second network endpoint during a plurality of different delivery times, each delivery time corresponding to a candidate time within a time reference frame during which a packet can be transmitted from the first network endpoint to the second network endpoint;

(2) empirically determining on the basis of packet statistics of the test packets which of the plurality of different delivery times corresponds to favorable traffic conditions for transmitting packets between the first network endpoint and second network endpoint over the single network path of the packet-switched network; and

(3) scheduling data packets for delivery over the network from the first network endpoint to the second network endpoint during one or more delivery times empirically determined in step (2) to correspond to favorable traffic conditions.

33. The computer-readable storage medium of claim 32, wherein the test packets have characteristics emulating data packets that will be transmitted between the first network endpoint and the second network endpoint.

34. The computer-readable storage medium of claim 32, wherein step (2) comprises the step of evaluating packet latencies associated with the test packets.

35. The computer-readable storage medium of claim 32, wherein step (2) comprises the step of evaluating dropped packet rates associated with the test packets.

36. The computer-readable storage medium of claim 32, wherein step (1) comprises the step of transmitting the test packets at a data rate corresponding to an expected connection bandwidth between the first network endpoint and the second network endpoint.

37. The computer-readable storage medium of claim 32, wherein step (2) comprises the step of the first network endpoint performing an evaluation of packet statistics associated with the test packets transmitted over the plurality of different delivery times.

38. The computer-readable storage medium of claim 32, wherein step (1) comprises the step of transmitting the test packets at a priority level lower than a priority level of existing real-time data traffic on the packet-switched network.