Empirical scheduling of network packets using a plurality of test packets

• US 7,876,692 B2
• Filed: 12/17/2008
• Issued: 01/25/2011
• Est. Priority Date: 09/17/2003
• Status: Expired due to Fees

• Current Assignee: Novanta Inc.
• Original Assignee: Nds Imaging Holdings, LLC (Novanta Inc.)
• Inventors: Rogers, Steven A.
• Primary Examiner(s): Jung; Min
• Application Number:
  US12/336,743
• Publication Number:
  US 20090141626A1
• Time in Patent Office: 769 Days
• Field of Search: None
• US Class Current: 370/241
• 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 43/0829 Packet loss
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/115 using a dedicated packet
• CPC Class Codes: H04L 47/127 by using congestion prediction
• 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/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• 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 transmitting a first plurality of test packets during a first plurality of time locations that are coarsely spaced apart in time; determining which of the first plurality of time locations corresponds to favorable network traffic conditions; transmitting a second plurality of test packets over the network during a second plurality of time locations that are finely spaced apart in time, wherein the second plurality of time locations are selected on the basis of favorable network traffic conditions; determining which of the second plurality of time locations corresponds to favorable network traffic conditions; and transmitting data packets over the network using one or more favorable time locations determined by the finely spaced test packets. The method can be used to “zero in” on congested network periods by detecting differences in packet latencies among test packets.

Claims

1. A method of transmitting packets over a network, comprising:

receiving a bandwidth requirement for transmitting packets over a network;

from a first network endpoint, transmitting a first plurality of test packets over a single network path of the network to a second network endpoint during a first plurality of time locations that are spaced apart in time, wherein a transmission rate of the first plurality of test packets is determined based on the received bandwidth requirement;

based on an evaluation of the first plurality of test packets, determining which of the first plurality of time locations corresponds to favorable network traffic conditions over the single network path; and

scheduling data packets for transmission over the single network path of the network during one or more of the time locations corresponding favorable network traffic conditions, wherein the data packets are synchronized to a time reference frame at the first network endpoint.

2. The method of claim 1, further comprising:

prior to scheduling the data packets for transmission, transmitting a second plurality of test packets over the single network path during a second plurality of time locations that are more finely spaced apart in time than the first plurality of time locations, wherein the second plurality of test packets are selected based on the determination of favorable network traffic conditions of the first plurality of time locations; and

wherein the data packets are scheduled for transmission over the single network path of the network during one or more of the second plurality of time locations.

3. The method of claim 2, wherein the first plurality of test packets have a packet size that differs from the packet size of the second plurality of test packets.

4. The method of claim 2, further comprising:

transmitting a third plurality of test packets during a third plurality of time locations that are more finely spaced apart in time the second plurality of time locations, wherein the third plurality of time locations are selected based on an evaluation of the second plurality of test packets;

based on the evaluation of the second plurality of test packets determined which of the third plurality of time locations corresponds to favorable network traffic conditions; and

based on the determination of which of the third plurality of time locations corresponds to favorable network traffic conditions, transmitting the data packets.

5. The method of claim 1, wherein the test packets are transmitted using a lower priority level than is used to transmit the data packets.

6. The method of claim 1, wherein the evaluating comprises evaluating packet latencies associated with the first plurality of test packets.

7. The method of claim 1, wherein the evaluating comprises evaluating a dropped packet rate associated with the first plurality of test packets.

8. The method of claim 1, wherein the evaluating comprises evaluating jitter associated with the first plurality of test packets.

9. The method of claim 1, wherein the evaluation of the first plurality of test packets is preformed by the first network endpoint, said evaluation comprising evaluating one of packet latencies, a dropped packet rate, and jitter associated with each of the first plurality of time locations.

10. The method of claim 1, wherein the evaluation of the first plurality of test packets is preformed by the second network endpoint, said evaluation comprising evaluating at least one of packet latencies, a dropped packet rate, and jitter associated with each of the first plurality of time locations.

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

12. The method of claim 11, wherein the data packets are scheduled for transmission during time locations within a frame that is synchronized to a clock.

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

14. The method of claim 1, wherein the data packets comprise one or more of voice data, video data, and real-time data.

15. The method of claim 1, wherein the test packets are transmitted for each side of a two-way connection between the first network endpoint and the second network endpoint.

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

17. The method of claim 1, further comprising;

prior to transmitting the first plurality of test packets, partitioning a delivery schedule at the first network endpoint, the delivery schedule corresponding to the first plurality of time locations.

18. In a network comprising a plurality of packet switches, a method of transmitting data packets, comprising:

establishing a time reference frame comprising a plurality of time locations during which packets are to be transmitted across the network;

from a first network endpoint, empirically determining which of the plurality of time locations is associated with a reduced rate of packet congestion with respect to an intended recipient second network endpoint by transmitting over a single network path through the network a plurality of test packets that are spaced apart in time, wherein a transmission rate of the plurality of test packets is determined based on a received bandwidth requirement; and

synchronously scheduling for transmission a plurality of data packets over the single network path from the first network endpoint to the second network endpoint during one or more time locations empirically determined to be associated with the reduced rate of packet congestion.

19. The method of claim 18, wherein the test packets are transmitted using a packet priority level lower than a packet priority level used to schedule the plurality of data packets.

20. An apparatus comprising:

a computer; and

a computer-readable medium having stored therein computer-executable instructions that, when executed, perform;

transmitting a first plurality of test packets through a network interface and over a single network path in the network to an intended recipient during a first plurality of time locations that are spaced apart in time, wherein a transmission rate of the first plurality of test packets is determined based on the received bandwidth requirement;

based on an evaluation of the first plurality of test packets, determining which of the first plurality of time locations corresponds to favorable network traffic conditions; and

scheduling data packets for transmission through the network interface and over the single network path during the one or more of the time locations corresponding to favorable network traffic conditions, wherein the data packets are synchronized to a time reference frame.

21. The apparatus of claim 20, wherein the evaluation comprises evaluating at least one of packet latencies, dropped packet rates, and packet jitter with a second apparatus connected to the network.

22. The apparatus of claim 20, wherein the test packets are transmitted using a lower priority level than is used to transmit the data packets.

23. The apparatus of claim 20, wherein the evaluating comprises evaluating packet latencies associated with the first plurality of test packets.

24. The apparatus of claim 20, wherein the evaluating comprises evaluating dropped packet rates associated with the first plurality of test packets.

25. The apparatus of claim 20, wherein the evaluating comprises evaluating packet jitter associated with the first plurality of test packets.

26. The apparatus of claim 20, wherein the data packets are scheduled for transmission during time locations within a frame that is synchronized to a clock.

27. The apparatus of claim 20, wherein the test packets are transmitted at a priority level that is lower than the data packets, but higher than other data packets containing other data transmitted on the network.

28. The apparatus of claim 20, wherein the data packets comprise one or more of voice data, video data, and real-time data.

29. The apparatus of claim 20, wherein the computer-executable instructions further perform transmitting a second plurality of test packets during a second plurality of time locations that are more finely spaced apart in time than the first plurality of test packets, wherein the first plurality of test packets have a packet size that differs from the packet size of the second plurality of test packets.

30. The apparatus of claim 29, wherein the computer-executable instructions further perform:

transmitting a third plurality of test packets during a third plurality of time locations that are more finely spaced apart in time than the second plurality of time locations, wherein the third plurality of time locations are selected based on an evaluation of the second plurality of test packets;

based on the evaluation of the second plurality of test packets, determining which of the third plurality of time locations corresponds to favorable network traffic conditions; and

based on the determination of which of the third plurality of time locations corresponds to favorable network traffic conditions, transmitting the data packets.

31. The apparatus of claim 29, wherein the first plurality of test packets are transmitted during a first time segment spanning a plurality of time locations;

and wherein the second plurality of test packets are transmitted during a subset of the first time segment.

32. The apparatus of claim 20, wherein the computer-executable instructions further perform:

prior to transmitting the first plurality of test packets, partitioning a delivery schedule at the apparatus, the delivery schedule corresponding to the first plurality of time locations.

33. A computer-readable medium comprising computer executable instructions which, when executed, perform:

receiving a bandwidth requirement for transmitting packets over a network;

from a first network endpoint, transmitting a first plurality of test packets to a second network endpoint over a single network path of a network during a first plurality of time locations that are spaced apart in time, wherein a transmission rate of the first plurality of test packets is determined based on the received bandwidth requirement;

based on an evaluation of the first plurality of test packets, determining which of the first plurality of time locations corresponds to favorable network traffic conditions over the single network path; and

scheduling data packets for transmission to the second network endpoint over the single network path of the network during one or more of the time locations corresponding to favorable network traffic conditions, wherein the data packets are synchronized to a time reference frame at the first network endpoint.

34. The computer-readable medium of claim 33, wherein the test packets are transmitted using a lower priority level than is used to transmit the data packets.

35. The computer-readable medium of claim 33, wherein the evaluating comprises evaluating packet latencies associated with the first plurality of test packets.

36. The computer-readable medium of claim 33, wherein the evaluating comprises evaluating a dropped packet rate associated with the first plurality of test packets.

37. The computer-readable medium of claim 33, wherein the evaluating comprises evaluating packet jitter associated with the first plurality of test packets.

38. The computer-readable medium of claim 33, wherein the evaluation of the first plurality of test packets is performed by transmitting node, said evaluation comprising evaluating at least one of packet latencies, a dropped packet rate, and jitter associated with each of the first plurality of time locations.

39. The computer-readable medium of claim 33, wherein the evaluation of the first plurality of test packets is performed by a receiving node, said evaluation comprising evaluating at least one of packet latencies, a dropped packet rate, and jitter associated with each of the first plurality of time locations.

40. The computer-readable medium of claim 33, wherein the test packets and the data packets comprise one of Internet Protocol (IP) and ethernet packets transmitted over a packet-switched network.

41. The computer-readable medium of claim 40, wherein the data packets are scheduled for transmission during time locations within a frame that is synchronized to a clock.

42. The computer-readable medium of claim 33, wherein the test packets are transmitted at a priority level that is lower than the data packets, but higher than other data packets containing other data transmitted on the network.

43. The computer-readable medium of claim 33, wherein the data packets comprise one or more of voice data, video data, and real-time data.

44. The computer-readable medium of claim 33, wherein the test packets are transmitted for each side of a two-way connection between two nodes in the network.

45. The computer-readable medium of claim 33, wherein the network is a packet-switched network comprising packet switches that maintain packet queues.

46. The computer-readable medium of claim 33, wherein the instructions, when executed, further cause a second plurality of test packets to be transmitted over the single network path during a second plurality of time locations, wherein the first plurality of test packets have a packet size that differs from the packet size of the second plurality of test packets.

47. The computer-readable medium of claim 46, wherein the instructions, when executed, further perform:

transmitting a third plurality of test packets during a third plurality of time locations that are more finely spaced apart in time than the second plurality of time locations, wherein the third plurality of time locations are selected based on an evaluation of the second plurality of test packets;

based on the evaluation of the second plurality of test packets, determining which of the third plurality of time locations corresponds to favorable network traffic conditions; and

based on the determination of which of the third plurality of time locations corresponds to favorable network traffic conditions, transmitting the data packets.

48. The computer-readable medium of claim 33, wherein the instructions, when executed, further perform:

prior to transmitting the first plurality of test packets, partitioning a delivery schedule at the first network endpoint, the delivery schedule corresponding to the first plurality of time locations.