Time-sensitive-packet jitter and latency minimization on a shared data link

• US 7,551,603 B1
• Filed: 01/27/2004
• Issued: 06/23/2009
• Est. Priority Date: 07/11/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Khouri, Joseph F., Shaffer, Shmuel, Knappe, Michael E.
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US10/765,421
• Time in Patent Office: 1,974 Days
• Field of Search: 370347-412, 370428-473, 370516-529, 370229-237, 709224-253
• US Class Current: 370/352
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/50 Queue scheduling

Abstract

A system and method are disclosed for interleaving time-critical packets and lower-priority packets onto a common data link. A packet arrival prediction mechanism predicts when a time-critical packet is expected to arrive. When transmission of a waiting lower-priority packet might cause a substantial delay in the expected time-critical packet'"'"'s transmission, the lower-priority packet is parked until it can be transmitted without interfering with a time-critical packet.

Claims

1. A method of interleaving the transmission of time-critical packets with the transmission of lower-priority packets across a common data link, the method comprising:

maintaining time-critical packet arrival statistics;

when a lower-priority packet becomes available for transmission across the data link, estimating a transmit time required for transmission of that packet; and

based on the time-critical packet arrival statistics and the estimated transmit time for the lower-priority packet, predicting whether the lower-priority packet can be selected for transmission across the data link without causing substantial delay to a time-critical packet that is not yet available for transmission across the data link, wherein predicting whether the lower-priority packet can be selected for transmission without causing substantial delay comprises computing time remaining until an expected arrival of the next time-critical packet and comparing the time remaining with an estimated transmit time for the lower-priority packet.

2. The method of claim 1, wherein maintaining time-critical-packet arrival statistics comprises measuring the time of arrival for previously-received time-critical packets, and using the measured time of arrival for those packets to update an estimate of the expected time of arrival for the next time-critical packet.

3. The method of claim 2, wherein updating an estimate comprises updating a filter state using the measured time of arrival.

4. The method of claim 1, wherein when the time-critical packets comprise voice packets, maintaining time-critical-packet arrival statistics comprises measuring a speech pause interval between adjacent voice talkspurts using packet measured time of arrival, and maintaining statistics on the duration of speech pause intervals.

5. The method of claim 1, wherein, during a bi-directional packet voice conference, maintaining time-critical-packet arrival statistics comprises measuring a turnaround interval between the beginning of a silence interval for incoming voice conference packets and the beginning of a talkspurt for outgoing time-critical packets, and maintaining statistics on the duration of the turnaround interval.

6. The method of claim 1, wherein maintaining time-critical-packet arrival statistics further comprises measuring the time between a time-critical packet'"'"'s time of arrival and that same packet'"'"'s end-of-transmission time.

7. The method of claim 1, further comprising placing lower-priority packets in a lower-priority queue in the order received, wherein a lower-priority packet becomes available for transmission when it reaches the head of the queue.

8. The method of claim 1, wherein estimating the transmit time for a lower-priority packet comprises determining the packet'"'"'s length and scaling that length by an estimated data link rate expressed in units of data divided by units of time.

9. The method of claim 1, wherein transmission does not cause substantial delay if the estimated transmit time for the lower-priority packet does not exceed the time remaining until the expected arrival of the next time-critical packet by more than an allowable jitter.

10. The method of claim 1, wherein computing the time remaining until the expected arrival of the next time-critical packet comprises computing a time estimate t_R=t_NP+k_σ

σ

_NP+j_A−

t_C, where t_NP is an expected arrival time estimate for the next time-critical packet, σ

_NP is an arrival time standard deviation for the next time-critical packet, k_σ

is a standard deviation multiplier, j_A is an allowable jitter, and t_C is the current time.

11. The method of claim 1, wherein computing the time remaining until the expected arrival of the next time-critical packet comprises receiving a pre-notification from an encoder that a time-critical packet is being built.

12. The method of claim 1, wherein computing the time remaining until the expected arrival of the next time-critical packet comprises receiving a pre-notification from a voice activity detector when voice activity begins and ceases.

13. The method of claim 1, further comprising, when a time-critical packet becomes available for transmission across the data link, transmitting that packet as soon as the data link is available.

14. An apparatus comprising a computer-readable medium containing computer instructions that, when executed, cause a processor or multiple communicating processors to interleave transmissions of time-critical packets with transmissions of lower-priority packets across a common data link, the interleaving comprising:

maintaining time-critical packet arrival statistics;

when a lower-priority packet becomes available for transmission across the data link, estimating the transmit time required for transmission of that packet; and

based on the time-critical packet arrival statistics and the estimated transmit time for the lower-priority packet, predicting whether the lower-priority packet can be selected for transmission across the data link without causing substantial delay to a time-critical packet that is not yet available for transmission across the data link, wherein predicting whether the lower-priority packet can be selected for transmission without causing substantial delay comprises computing a time remaining until an expected arrival of the next time-critical packet and comparing the time remaining with an estimated transmit time for the lower-priority packet.

15. The apparatus of claim 14, wherein maintaining time-critical-packet arrival statistics comprises measuring the time of arrival for previously-received time-critical packets, and using the measured time of arrival for those packets to update an estimate of the expected time of arrival for the next time-critical packet.

16. The apparatus of claim 15, wherein updating an estimate comprises updating a filter state using the measured time of arrival.

17. The apparatus of claim 14, wherein when the time-critical packets comprise voice packets, maintaining time-critical-packet arrival statistics comprises measuring a speech pause interval between adjacent voice talkspurts using packet measured time of arrival, and maintaining statistics on the duration of speech pause intervals.

18. The apparatus of claim 14, wherein, during a bi-directional packet voice conference, maintaining time-critical-packet arrival statistics comprises measuring a turnaround interval between the beginning of a silence interval for incoming voice conference packets and the beginning of a talkspurt for outgoing time-critical packets, and maintaining statistics on the duration of the turnaround interval.

19. The apparatus of claim 14, further comprising placing lower-priority packets in a lower-priority queue in the order received, wherein a lower-priority packet becomes available for transmission when it reaches the head of the queue.

20. The apparatus of claim 14, wherein transmission does not cause substantial delay if the estimated transmit time for the lower-priority packet does not exceed the time remaining until the expected arrival of the next time-critical packet by more than an allowable jitter.

21. The apparatus of claim 14, wherein computing the time remaining until the expected arrival of the next time-critical packet comprises computing a time estimate t_R=t_NP+k_σ

σ

_NP+j_A−

t_C, where t_NP is an expected arrival time estimate for the next time-critical packet, σ

_NP is an arrival time standard deviation for the next time-critical packet, k_σ

is a standard deviation multiplier, j_A is an allowable jitter, and t_C is the current time.

22. The apparatus of claim 14, wherein computing the time remaining until the expected arrival of the next time-critical packet comprises receiving a pre-notification from an encoder that a time-critical packet is being built.

23. The apparatus of claim 14, wherein computing the time remaining until the expected arrival of the next time-critical packet comprises receiving a pre-notification from a voice activity detector when voice activity begins and ceases.

24. The apparatus of claim 14, further comprising, when a time-critical packet becomes available for transmission across the data link, transmitting that packet as soon as the data link is available.

25. A system comprising:

means for maintaining time-critical packet arrival statistics;

means for estimating a transmit time required for transmission of a lower-priority packet when the lower-priority packet becomes available for transmission across a data link; and

means for predicting whether the lower-priority packet can be selected for transmission across the data link without causing substantial delay to a time-critical packet that is not yet available for transmission across the data link based on the time-critical packet arrival statistics and the estimated transmit time for the lower-priority packet, wherein the means for predicting whether the lower-priority packet can be selected for transmission without causing substantial delay comprises means for computing time remaining until an expected arrival of the next time-critical packet and means for comparing the time remaining with an estimated transmit time for the lower-priority packet.

26. The system of claim 25, wherein transmission does not cause substantial delay if the estimated transmit time for the lower-priority packet does not exceed the time remaining until the expected arrival of the next time-critical packet by more than an allowable jitter.

27. The system of claim 25, wherein the means for computing the time remaining until the expected arrival of the next time-critical packet comprises means for computing a time estimate t_R=t_NP+k_σ

σ

_NP+j_A−

t_C, where t_NP is an expected arrival time estimate for the next time-critical packet, σ

_NP is an arrival time standard deviation for the next time-critical packet, k_σ

is a standard deviation multiplier, j_A is an allowable jitter, and t_C is the current time.

28. The system of claim 25, wherein the means for computing the time remaining until the expected arrival of the next time-critical packet comprises means for receiving a pre-notification from an encoder that a time-critical packet is being built.

29. The system of claim 25, wherein the means for computing the time remaining until the expected arrival of the next time-critical packet comprises means for receiving a pre-notification from a voice activity detector when voice activity begins and ceases.