Empirical scheduling of network packets using coarse and fine testing periods

• US 7,468,948 B2
• Filed: 10/28/2004
• Issued: 12/23/2008
• Est. Priority Date: 09/17/2003
• Status: Expired due to Fees

• Current Assignee: Novanta Inc.
• Original Assignee: Rivulet Communications Incorporated (Novanta Inc.)
• Inventors: Rogers, Steven A
• Primary Examiner(s): Jung; Min
• Application Number:
  US10/975,019
• Publication Number:
  US 20050058083A1
• Time in Patent Office: 1,517 Days
• Field of Search: 370445-448, 370458-462, 370/241
• 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 the steps of:

(1) transmitting a first plurality of test packets over the network during a first plurality of time locations that are coarsely spaced apart in time;

(2) on the basis of step (1), determining which of the first plurality of time locations corresponds to favorable network traffic conditions;

(3) 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 determined in step (2); and

(4) on the basis of step (3), determining which of the second plurality of time locations corresponds to favorable network traffic conditions.

2. The method of claim 1, further comprising the step of:

(5) transmitting data packets over the network during one or more favorable time locations determined in step (4).

3. The method of claim 2, wherein steps (1) and (3) comprise the step of transmitting the test packets using a lower priority level than is used to transmit data packets in step (5).

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

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

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

7. The method of claim 2, wherein the data packets comprise voice data.

8. The method of claim 2, further comprising the step of repeating steps (1) through (5) for each side of a two-way connection between two nodes in the network.

9. The method of claim 2, further comprising the steps of, prior to step (5):

(a) transmitting a third plurality of test packets during a third plurality of time locations that are more finely spaced apart in time than those in step (3), wherein the third plurality of time locations are selected on the basis of favorable network traffic conditions determined in step (4);

(b) on the basis of step (a), determining which of the third plurality of time locations corresponds to favorable network traffic conditions; and

(c) using the determined time locations in step (b) as the basis for transmitting data packets in step (5).

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

11. The method of claim 1, wherein step (2) comprises the step of evaluating a dropped packet rate associated with the first plurality of test packets.

12. The method of claim 1, wherein step (3) comprises the step of transmitting the test packets at a data rate corresponding to a required connection bandwidth.

13. The method of claim 1, wherein step (2) comprises the step of a transmitting node evaluating one of packet latencies and a dropped packet rate associated with the first plurality of time locations.

14. The method of claim 1, wherein step (2) comprises the step of a receiving node evaluating one of packet latencies and a dropped packet rate associated with the first plurality of time locations.

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

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

17. The method of claim 1, further comprising the step of detecting differences in latencies among test packets and using the detected differences to identify time periods corresponding to congestion.

18. In an Internet Protocol (IP) network comprising a plurality of packet switches, a method of transmitting data packets, comprising the steps of:

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

(2) empirically determining which of the plurality of time locations is associated with a reduced rate of packet congestion with respect to an intended recipient node; and

(3) transmitting a plurality of data packets from a transmitting node to the intended recipient node during one or more time locations empirically determined to be associated with the reduced rate of packet congestion in step (2), wherein step (2) is performed by transmitting a first plurality of test packets that are coarsely spaced apart in time and then transmitting a second plurality of test packets that are finely spaced apart in time, wherein the second plurality of test packets are transmitted during time locations that are selected to correspond to time periods of relative network non-congestion as determined by the first plurality of test packets.

19. The method of claim 18, wherein step (2) comprises the step of transmitting test packets using a packet priority level lower than a packet priority level used to transmit the plurality of data packets in step (3).

20. The method of claim 18, wherein step (2) comprises the step of transmitting test packets at a data rate sufficient to support a desired bandwidth in step (3).

21. Anapparatus comprising:

a network interface;

a computer coupled to the network interface; and

a computer-readagle medium having stored therein computer-executable instructions that, when executed by the computer, perform the steps of;

(1) transmitting a first plurality of test packets through the network interface and over a network during a first plurality of time locations that are coarsely spaced apart in time;

(2) on the basis of step (1), determining which of the first plurality of time locations corresponds to favorable network traffic conditions;

(3) 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 determined in step (2);

(4) on the basis of step (3), determining which of the second plurality of time locations corresponds to favorable network traffic conditions; and

(5) transmitting data packets over the network using one or more favorable time locations determined in step (4).

22. The apparatus of claim 21, wherein the computer-executable instructions further perform the step of evaluating packet latencies with a second arraratus connected to the network.

23. The apparatus of claim 21, wherein the computer-executable instructions perform steps (1) and (3) using a lower priority level than is used to transmit data packets in step (5).

24. The apparatus of claim 21, wherein the computer-executable instructions perform step (2) by evaluating packet latencies associated with the first plurality of test packets.

25. The apparatus of claim 21, wherein the computer-executable instructions perform step (2) by evaluating dropped packet rates associated with the first plurality of test packets.

26. The apparatus of claim 21, wherein the computer-executable instructions perform step (3) by transmitting the test packets at a data rate corresponding to a required connection bandwidth.

27. The apparatus of claim 21, wherein the computer-executable instructions perform the step of detecting differences in latencies among test packets and using the detected differences to identify time periods corresponding to congestion.

28. The apparatus of claim 21, wherein the computer-executable instructions schedule packets for transmission during time locations within a frame that is synchronized to a clock.

29. The apparatus of claim 21, wherein the computer-executable instructions transmit test packets at a priority level that is lower than data packets transmitted in step (5), but higher than other data packets containing other data transmitted on the network.

30. The apparatus of claim 21, wherein the computer-executable instructions transmit data packets comprising voice data.

31. The apparatus of claim 21, wherein the computer-executable instructions transmit the first plurality of test packets using a packet size that differs from the packet size of the second plurality of test packets.

32. The apparatus of claim 21, wherein the computer-executable instructions perform the steps of, prior to step (5):

(a) transmitting a third plurality of test packets during a third plurality of time locations that are more finely spaced apart in time than those in step (3), wherein the third plurality of time locations are selected on the basis of favorable network traffic conditions determined in step (4);

(b) on the basis of step (a), determining which of the third plurality of time locations corresponds to favorable network traffic conditions; and

(c) using the determined time locations in step (b) as the basis for transmitting data packets in step (5).

33. The apparatus of claim 21, wherein the computer-executable instructions perform step (1) by transmitting test packets during a first time segment spanning a plurality of time locations;

and wherein the computer-executable instructions perform step (3) by transmitting test packets during a subset of the first time segment.

34. A computer-readable medium comprising computer instructions which, when executed by a computer, perform the steps of:

(1) transmitting a first plurality of test packets over a network during a first plurality of time locations that are coarsely spaced apart in time;

(2) on the basis of step (1), determining which of the first plurality of time locations corresponds to favorable network traffic conditions;

(3) 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 determined in step (2);

(4) on the basis of step (3), determining which of the second plurality of time locations corresponds to favorable network traffic conditions; and

(5) transmitting data packets over the network using one or more favorable time locations determined in step (4).

35. The computer-readable medium of claim 34, wherein steps (1) and (3) comprise the step of transmitting the test packets using a lower priority level than is used to transmit data packets in step (5).

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

37. The computer-readable medium of claim 34, wherein step (2) comprises the step of evaluating a dropped packet rate associated with the first plurality of test packets.

38. The computer-readable medium of claim 34, wherein step (3) comprises the step of transmitting the test packets at a data rate corresponding to a required connection bandwidth.

39. The computer-readable medium of claim 34, wherein step (2) comprises the step of a transmitting node evaluating one of packet latencies and a dropped packet rate associated with the first plurality of time locations.

40. The computer-readable medium of claim 34, wherein step (2) comprises the step of a receiving node evaluating one of packet latencies and a dropped packet rate associated with the first plurality of time locations.

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

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

43. The computer-readable medium of claim 34, wherein the test packets are transmitted at a priority level that is lower than the data packets in step (5), but higher than other data packets containing other data transmitted on the network.

44. The computer-readable medium of claim 34, wherein the data packets comprise voice data.

45. The computer-readable medium of claim 34, further comprising the step of repeating steps (1) through (5) for each side of a two-way connection between two nodes in the network.

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

47. The computer-readable medium of claim 34, wherein the first plurality of test packets have a packet size that differs from the packet size of the second plurality of test packets.

48. The computer-readable medium of claim 34, wherein the instructions, when executed, further perform the steps of, prior to step (5):

(a) transmitting a third plurality of test packets during a third plurality of time locations that are more finely spaced apart in time than those in step (3), wherein the third plurality of time locations are selected on the basis of favorable network traffic conditions determined in step (4);

(b) on the basis of step (a), determining which of the third plurality of time locations corresponds to favorable network traffic conditions; and

(c) using the determined time locations in step (b) as the basis for transmitting data packets in step (5).

49. The computer-readable medium of claim 34, wherein the instructions, when executed, further perform detecting differences in latencies among test packets and using the detected differences to identify time periods corresponding to congestion.