System for and method of recovering temporal alignment of digitally encoded audio data transmitted over digital data networks

• US 6,744,764 B1
• Filed: 12/16/1999
• Issued: 06/01/2004
• Est. Priority Date: 12/16/1999
• Status: Expired due to Fees

• Current Assignee: Mapletree Networks, Inc. (Ribbon Communications, Inc.)
• Original Assignee: Mapletree Networks, Inc. (Ribbon Communications, Inc.)
• Inventors: Davies, Graham, Matias, John P., Smith, Steve B., Bigdeliazari, Ali
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US09/464,421
• Time in Patent Office: 1,629 Days
• Field of Search: 370/394, 370/270, 370/384, 370/493, 370/522, 370/351, 370/379, 370/352, 370/516, 370/389, 370/509, 709/231, 709/214, 704/503
• US Class Current: 370/394
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 2012/6481 Speech, voice
• CPC Class Codes: H04L 2012/6489 Buffer Management, Threshold setting, Scheduling, Shaping

Abstract

A system for receiving and re-sequencing a plurality of digital data chunks after transmission across a digital data network, so as to recover the natural temporal order of the data chunks as defined at the transmitter, including a chunk sorter for storing the, digital data chunks in a data buffer. The system thereafter sequentially transfers, at a chunk transfer rate compatible with the system playout rate, the digital data chunks to a playout destination according to the natural temporal order. The system further includes a chunk sequence analyzer for measuring the average time that the digital data chunks remain in the data buffer. The chunk sequence analyzer adjusts the playout rate so as to balance an increase in the average time, with an amount of data chunks lost due to arriving late and missing a playout deadline.

Claims

1. For a plurality of digital data chunks sequentially generated by a data transmitter according to a natural temporal order and a natural time alignment, and thereupon transmitted across a digital data network to a receiver, such that said digital data chunks arrive at said receiver in a received temporal order substantially independent of said natural temporal order and in a received time alignment substantially independent of said natural time alignment, a system for re-sequencing said plurality of digital data chunks at said receiver so as to transform said received temporal order into said natural temporal order, comprising:

a chunk sorter for storing said digital data chunks in a data buffer and thereafter sequentially transferring, in said natural temporal order and at a chunk transfer rate compatible with a playout rate, said digital data chunks to a playout destination according to said natural temporal order, wherein said chunk sorter further includes;

(i) a packet unassembly buffer for receiving a plurality of packets of said digital data chunks;

(ii) a jitter buffer having a plurality of storage slots for storing said data chunks, wherein said chunk sorter zero-fills said storage slots so as to accommodate data chunks having a data width less than a width of said storage slots; and

,

(iii) a digital signal processor for receiving said data chunks from said jitter buffer and sequentially playing out said data chunks in said natural temporal order at said playout rate; and

a chunk sequence analyzer for measuring an average time that said digital data chunks remain in said data buffer prior to playout, and for adjusting said playout rate so as to balance (a) an increase in said average time, with (b) an amount of data chunks lost due to arriving late and missing a playout deadline.

2. For a plurality of digital data chunks sequentially generated by a data transmitter according to a natural temporal order and a natural time alignment, and thereupon transmitted across a digital data network to a receiver, such that said digital data chunks arrive at said receiver in a received temporal order substantially independent of said natural temporal order and in a received time alignment substantially independent of said natural time alignment, a system for re-sequencing said plurality of digital data chunks at said receiver so as to transform said received temporal order into said natural temporal order, comprising:

a chunk sorter for storing said digital data chunks in a data buffer and thereafter sequentially transferring at a chunk transfer rate compatible with a playout rate, said digital data chunks to a playout destination according to said natural temporal order, and,

a chunk sequence analyzer for measuring an average time that said digital data chunks remain in said data buffer prior to playout, and for adjusting said playout rate so as to balance (a) an increase in said average time, with (b) an amount of data chunks lost due to arriving late and missing a playout deadline, wherein said chunk sequence analyzer further includes

(i) a chunk holding time calculator for determining a chunk holding time for each of said data chunks in said data buffer;

(ii) a mean holding time calculator for receiving said chunk holding time corresponding to each of said data chunks, and averaging a predetermined number of said chunk holding times, so as to produce a mean holding time corresponding to a set of data chunks in said data buffer;

(iii) a smoothed mean holding time calculator for receiving said mean holding time corresponding to each of said sets of data chunks in said data buffer, and averaging a predetermined number of said mean holding times within a time window, so as to produce a smoothed mean holding time.

3. A system according to claim 2, wherein said holding time calculator calculates a total holding time T_N for N data chunks in said data buffer at a time that an N^th data chunk is stored in said data buffer, said total holding time T_N including a sum of a next preceding total holding time T_N−

1, an aging term E_N, and a chunk holding term C_N.

4. A system according to claim 2, wherein said mean holding time calculator calculates a mean holding time H_N for N data chunks in said data buffer at a time that an N^th data chunk is stored in said data buffer, said mean holding time H_N including a product of said total holding time T_N and 1/N.

5. A system according to claim 4, wherein said chunk sorter initiates a transfer of said data chunks in said data buffer to said playout destination when said mean holding time H_N equals or exceeds a predetermined holding time goal.

6. A system according to claim 2, wherein said chunk sequence analyzer further associates an arrival time with each of said data chunks according to a playout clock associated with said playout destination.

7. A system according to claim 2, wherein upon playout of said data chunks, said holding time calculator calculates, for each of said data chunks, a chunk holding time being a difference between a head playout time and an arrival time of said data chunk.

8. A system according to claim 7, wherein said mean holding time calculator calculates, for a set of K data chunks, a mean holding time being a product of (a) a sum of K chunk holding times corresponding to said set of K data chunks, and (b) 1/K.

9. A system according to claim 8, wherein said sum of K chunk holding times includes K consecutive chunk holding times.

10. A system according to claim 8, wherein said smoothed mean holding time, calculator calculates, for a set of J mean holding times, a smoothed mean holding time being a product of (a) a sum of J mean holding times and (b) 1/J.

11. A system according to claim 10, wherein said sum of J mean holding times includes J consecutive mean holding times.

12. A system according to claim 2, further including a playout adjustment selector for receiving said mean holding time, said smoothed mean holding time and a holding time goal, and providing a playout adjustment signal to said playout destination for adjusting said playout rate, said playout adjustment signal being a predetermined function of said mean holding time, said smoothed mean holding time and said holding time goal.

13. A system according to claim 12, wherein said predetermined function includes comparing said mean holding time to said holding time goal, providing an advance playout command via said adjustment signal if said mean holding time is larger than said holding time goal, and providing a retard playout command via said adjustment signal if said mean holding time is smaller than said holding time goal.

14. A system according to claim 12, wherein said predetermined function includes comparing said smoothed mean holding time to said holding time goal, providing an advance playout command via said adjustment signal if said smoothed mean holding time is larger than said holding time goal, and providing a retard playout command via said adjustment signal if said smoothed mean holding time is smaller than said holding time goal.

15. A system according to claim 12, wherein said predetermined function includes comparing said mean holding time to said holding time goal so as to produce a comparison value, and providing said adjustment signal such that an adjustment magnitude corresponds to said comparison value.

16. A system according to claim 2, said chunk sequence analyzer further including a holding time goal adapter for adjusting a chunk holding time goal, wherein said holding time goal adapter:

(i) determines, for each data chunk, an arrival margin by which said data chunk either (a) achieves storage in said data buffer prior to playout, or (b) does not achieve storage in said data buffer due to missing said playout deadline;

(ii) sorts said arrival margins into a predetermined set of arrival margin bins; and

,

(iii) adjusts said chunk holding time goal as a predetermined function of said sorted arrival margins.

17. A system according to claim 16, wherein said arrival margin is a predetermined function of an associated chunk holding time, an associated smoothed mean holding time, and a previous holding time goal value.

18. A system according to claim 16, wherein said chunk holding time goal is further a predetermined function of a loss tolerance value and a margin value width of said arrival margin bins.

19. For a plurality of digital data chunks sequentially generated by a data transmitter according to a natural temporal order, and thereupon transmitted across a digital data network to a receiver, such that said digital data chunks arrive at said receiver in a received temporal order substantially independent of said natural temporal order, a method of re-sequencing said plurality of digital data chunks at said receiver so as to transform said received temporal order into said natural temporal order, comprising the steps of:

storing said digital data chunks in a data buffer and thereafter sequentially transferring, at a chunk transfer rate compatible with a playout rate, said digital data chunks to a playout destination according to said natural temporal order;

including the steps of;

(i) receiving a plurality of packets of said digital data chunks in a packet unassembly buffer;

(ii) storing said data chunks in a jitter buffer having a plurality of storage slots; and

,

(iii) receiving said data chunks from said jitter buffer and sequentially playing out said data chunks in said natural temporal order at said playout rate;

(iv) zero-filling said storage slots so as to accommodate data chunks having a data width less than a width of said storage slots, and,

measuring an average time that said digital data chunks remain in said data buffer prior to playout, and adjusting said playout rate so as to balance (a) an increase in said average time, with (b) an amount of data chunks lost due to arriving late and missing a playout deadline.

20. For a plurality of digital data chunks sequentially generated by a data transmitter according to a natural temporal order, and thereupon transmitted across a digital data network to a receiver, such that said digital data chunks arrive at said receiver in a received temporal order substantially independent of said natural temporal order, a method of re-sequencing said plurality of digital data chunks at said receiver so as to transform said received temporal order into said natural temporal order, comprising the steps of:

storing said digital data chunks in a data buffer and thereafter sequentially transferring, at a chunk transfer rate compatible with a playout rate, said digital data chunks to a playout destination according to said natural temporal order; and

,

measuring an average time that said digital data chunks remain in said data buffer prior to playout, and adjusting said playout rate so as to balance (a) an increase in said average time, with (b) an amount of data chunks lost due to arriving late and missing a playout deadline, further including the steps of;

(i) determining a chunk holding time for each of said data chunks in said data buffer;

(ii) receiving said chunk holding time corresponding to each of said data chunks, and averaging a predetermined number of said chunk holding times, so as to produce a mean holding time corresponding to a set of data chunks in said data buffer;

(iii) receiving said mean holding time corresponding to each of said sets of data chunks in said data buffer, and averaging a predetermined number of said mean holding times within a time window, so as to produce a smoothed mean holding time.

21. A method according to claim 20, further including the step of calculating a total holding time T_N for N data chunks in said data buffer at a time that an N^th data chunk is stored in said data buffer, said total holding time T_N including a sum of a next preceding total holding time T_N−

1, an aging term E_N, and a chunk holding term C_N.

22. A method according to claim 20, further including the steps of calculating a mean holding time H_N for N data chunks in said data buffer at a time that an N^th data chunk is stored in said data buffer, said mean holding time H_N including a product of said total holding time T_N and 1/N.

23. A method according to claim 22, further including the step of initiating a transfer of said data chunks in said data buffer to said playout destination when said mean holding time H_N equals or exceeds a predetermined holding time goal.

24. A method according to claim 20, further including the step of associating an arrival time with each of said data chunks according to a playout clock associated with said playout destination.

25. A method according to claim 20, further including the step of calculating for each of said data chunks, upon playout of said data chunks, a chunk holding time being a difference between a head playout time and an arrival time of said data chunk.

26. A method according to claim 25, further including the step of calculating, for a set of K data chunks, a mean holding time being a product of (a) a sum of K chunk holding times corresponding to said set of K data chunks, and (b) 1/K.

27. A method according to claim 26, further including the step of calculating, for a set of J mean holding times, a smoothed mean holding time being a product of (a) a sum of J mean holding times and (b) 1/J.

28. A method according to claim 20, further including the steps of receiving said mean holding time, said smoothed mean holding time and a holding time goal, and providing a playout adjustment signal to said playout destination for adjusting said playout rate, said playout adjustment signal being a predetermined function of said mean holding time, said smoothed mean holding time and said holding time goal.

29. A method according to claim 28, further including the steps of comparing said mean holding time to said holding time goal, providing an advance playout command via said adjustment signal if said mean holding time is larger than said holding time goal, and providing a retard playout command via said adjustment signal if said mean holding time is smaller than said holding time goal.

30. A method according to claim 28, further including the steps of comparing said smoothed mean holding time to said holding time goal, providing an advance playout command via said adjustment signal if said smoothed mean holding time is larger than said holding time goal, and providing a retard playout command via said adjustment signal if said smoothed mean holding time is smaller than said holding time goal.

31. A method according to claim 28, further including the steps of comparing said mean holding time to said holding time goal so as to produce a comparison value, and providing said adjustment signal such that an adjustment magnitude corresponds to said comparison value.

32. A method according to claim 20, further including the steps of adjusting a chunk holding time goal by:

(i) determining, for each data chunk, an arrival margin by which said data chunk either (a) achieves storage in said data buffer prior to playout, or (b) avoids storage in said data buffer due to missing said playout deadline;

(ii) sorting said arrival margins into a predetermined set of arrival margin bins; and

,

(iii) adjusting said chunk holding time goal as a predetermined function of said sorted arrival margins.

33. An apparatus for recovering temporal alignment of digitally encoded speech chunks having a natural temporal order, transmitted over a packet-switched data network providing best-effort connectionless service such that said packets conveyed thereby are subject to transit delay, variation in transit delay from one packet to another, packet loss, packet duplication, and out-of-order packet delivery, the apparatus comprising:

a first software module for (a) storing speech data packets in a data buffer as said packets arrive from a data network and (b) retrieving said data packets from said data buffer in said natural temporal order and at a time at which said speech data packets should be played out to a receiving party; and

a second software module for (a) measuring and (b) adjusting an average time that said speech data packets spend in storage, so as to balance an additional delay with an occurrence of said speech data that arrives from said data network too late for playout, and

wherein the first software module recovers the sequence in which said encoded speech data is played out by storage of said speech chunks in a Jitter Buffer, according to a relative playout time value provided by a packet protocol header, and independent of a packet arrival order, and furthermore said Jitter Buffer is divided into storage partitions into each of which encoded speech data representing a known time interval is stored, and said time interval is configurable according to a speech encoding method in use.

34. An apparatus according to claim 33, wherein said storage partitions are arranged by a software module in a fixed order representing said natural temporal order.

35. An apparatus according to claim 33, wherein each frame received in a packet on the data network is stored in an individual storage partition of the Jitter Buffer.

36. An apparatus according to claim 33, wherein samples received in a packet on said data network are distributed into said storage partitions of the Jitter Buffer such that each partition contains an amount of data representing a selected partition time interval.

37. An apparatus according to claims 36, wherein a selection of storage partitions is made with reference to information about an encoder'"'"'s relative sampling time included in the packet header by the transmitter.

38. An apparatus according to claim 33, wherein said apparatus decoding and playing out speech maintains a playout clock, advancing in step with speech playout, and each said storage partition is labeled with a value of said playout clock when said partition is filled with data, for the purpose of measuring the time the data spends in storage between arrival and playout.

39. An apparatus according to claim 33, wherein the average time spent in storage by encoded speech data is measured by processing the storage time of the data in each successive storage partition with accumulate-and-dump and/or sliding window averaging and smoothing algorithms to reduce fluctuations due to stochastic variations in packet delay.