Adaptive queuing

Methods and systems for dynamically adjusting the length of delay before playback as a function of the amount of transmission jitter is disclosed, whereby a target error rate is received, error rates at different delays are tracked and current delay is adjusted as a function of tracked error rates.

FIELD OF THE INVENTION

The present invention is directed to the field of data transmission, and in particular to the dynamic adjustment of length of delay before playback in response to network and system conditions.

BACKGROUND OF THE INVENTION

Typically in data transmission over a network, a transmitter transmits certain size packets periodically and a receiver receives the transmitted packets and plays them. However, although the receiver transmits at fixed intervals, there is some variation in the time intervals at which transmitted packets are received by the receiver. For example, a transmitter may transmit a packet every 100 ms, so that at time0, packet A is transmitted, at time0+100, packet B is transmitted and at time0+200, packet C is transmitted. The receiver, however, may receive packet A at time0+10, packet B at time0+110 (a 100 ms interval) and packet C at time0+230 (a 120 ms interval).

The variation in the time intervals between which packets are received is called jitter. Jitter causes problems for real-time streaming data applications because proper data reproduction requires consistent playback timing. Streaming data transfer differs from other types of data transfer in that the data transferred has a temporal aspect. Once the receiver begins to reproduce the stream of data at the destination, it must continue to reproduce that data stream continuously according to the temporal structure of that data, or else the reproduction of that data will have lower quality. As an example, without limitation, audio data has this structure. A stream of audio data must be reproduced at the destination with the right temporal structure, or it will not sound correct to the listener. Therefore if a packet arrives late because of jitter, the receiver may not be able to play a continuous stream of data if the packet is not available when required to maintain consistent playback timing. The packet unavailability causes the playback to “break up” and reduces playback quality.

To compensate for playback errors, streaming data applications communicated over packet-based networks typically use a “jitter buffer” to implement a measure of delay before playback on the receiver. As the receiver receives packets, it does not play them back right away, but instead, copies them to a jitter buffer. The data stream is then played from the jitter buffer. If the size of the jitter buffer is larger than the amount of jitter present in the network, then the receiver will be able to play back a smooth and unbroken stream of data, because there will always be data available in the jitter buffer for playback.

The jitter buffer, however, adds latency to the playback. In the context of streaming data transmission and playback, latency is the time between input of data by the sender and rendering of that data by the receiver. The length of the jitter buffer increases latency. If the jitter buffer is 50 milliseconds (ms) in length, there may be up to 50 ms of delay attributable to the size of the jitter buffer in addition to any additional latency attributable to the network and other components of the communications system. Thus it is desirable to have the smallest jitter buffer that provides adequate playback quality.

The size of jitter buffer required to provide adequate playback quality will change as conditions change on the network between the transmitter and receiver. Thus it would be desirable to have a method to automatically adjust the size of the jitter buffer, thus adjusting the length of delay of playback, in response to changing network conditions.

SUMMARY OF THE INVENTION

In accordance with the invention, incoming packets are inserted into a queue (hereinafter referred to as a jitter buffer). The packets are not released to be played until a certain number of packets are received and stored in the jitter buffer. The number of packets that must be received before playback starts is referred to herein as the “high-water mark” which effectively determines the length of delay before playback. A high-water mark appropriate for the current network and host conditions is determined. If there is little or no jitter, the high-water mark can be very low or even zero, whereas where there is significant jitter, the high-water mark should be set correspondingly higher. As jitter changes in response to network and host conditions, the high-water mark and thus the length of delay before playback changes accordingly, to compensate for the jitter.

According to another aspect of the invention, the high-water mark is dependent on the desired quality of playback. As the high-water mark is increased, the number of reproduction errors approaches zero, but latency increases. A target error rate is selected based on the type of application. Gaming applications, for example, generally desire low latency and, hence, exchange low latency for a higher error rate.

After a target high-water mark is selected, the high-water mark is thereafter dynamically adjusted to approach the target error rate for the given application. Hence, as data segments (which in audio applications are referred to as talkspurts) are processed, the error rate for the data segment or talkspurt is determined. The error rate experienced at the current high-water mark and its associated delay time is compared to the error rate experienced at other delay times and if the target error rate has not been achieved, length of delay may be increased or decreased by increasing or decreasing the high-water mark, in order to make the error rate approach the target error rate.

According to an aspect of the invention, the error rate experienced for each high-water mark is tracked. Results are stored in a data structure such as, but not limited to, an array. The array or other suitable data structure is updated with the error rate of each segment. For example, if the error rate is better (lower) than the error rate required, and the length of delay is not zero, the length of delay may be decreased by the time interval represented by one packet. To determine whether or not the length of delay will be decreased, the disclosed invention checks to see which delay time results in an error rate closer to the target error rate and the high-water mark is set to which ever delay time results in an error rate closer to the target error rate.

The disclosed invention is appropriate for systems that use both variable and fixed length packets.

DETAILED DESCRIPTION OF THE INVENTION

Overview

To compensate for playback error, communications applications over packet-based networks typically use a jitter buffer in which packets of data are stored and from which packets are played back. The consequences of choosing a jitter buffer that is too small will be excessive playback errors. The consequences of choosing a jitter buffer that is too large is excessive latency. Typically the size of a jitter buffer is static, so that even if a ideal jitter buffer size is chosen, network conditions may change, rendering the jitter buffer size no longer ideal. The invention contemplates the use of a dynamically-sized buffer resulting in a dynamically-hanging length of delay.

Illustrative Computer Network Environment

The present invention may be deployed as part of a computer network. In general, the computer network may comprise both server computers and client computers deployed in a network environment.FIG. 1illustrates an exemplary network environment, with a server in communication with client computers via a network, in which the present invention may be employed. As shown inFIG. 1, a number of servers10a,10b, etc., are interconnected via a communications network160(which may be a LAN, WAN, intranet or the Internet) with a number of client computers20a,20b,20c, etc. In a network environment in which the communications network160is the Internet, for example, the servers10can be Web servers with which the clients20communicate via any of a number of known protocols such as hypertext transfer protocol (HTTP). Each client computer20can be equipped with a browser180to gain access to the servers10. In addition to using the network160in a client-server configuration, client computer20a,20b,20cmay communicate directly with each other in a peer-to-peer configuration.

The present invention is preferably deployed in a network environment, particularly where that network is an Internet or Intranet environment. The term “Internet” is an abbreviation for “Internetwork,” and refers commonly to the collection of networks and gateways that utilize the TCP/IP suite of protocols, which are well-known in the art of computer networking. TCP/IP is an acronym for “Transport Control Protocol/Internet Protocol.” The Internet can be described as a system of geographically distributed remote computer networks interconnected by computers executing networking protocols that allow users to interact and share information over the networks. Because of such wide-spread information sharing, remote networks such as the Internet have thus far generally evolved into an “open” system for which developers can design software applications for performing specialized operations or services, essentially without restriction.

Electronic information transmitted by one of the common protocols (e.g., TCP/IP, UDP, etc.) is generally broken into packets. The packets are addressed to one of the other computers20a,20b,20c,10a,10bconnected to network160. The addressed computer receives the packets, strips out the information content of the packets, and reassembles the transmitted electronic information. The electronic information may be audio, video, text and so on.

A transmission of audio data, as in a gaming application, can be sent by a client application program to a server or to another client, depending on the game configuration. If the data is transmitted to a server, the server may transmit this data to another client application program. The client process may be active in a first computer system, and the server process may be active in a second computer system, communicating with one another over a communications medium, thus providing distributed functionality and allowing multiple clients to take advantage of the capabilities of the server.

Thus, the present invention can be utilized in a computer network environment having client computers for accessing and interacting with the network and a server computer for interacting with client computers. However, the systems and methods for providing audio data stream transmission in accordance with the present invention can be implemented with a variety of network-based architectures, and thus should not be limited to the example shown. The present invention will now be described in more detail with reference to a presently illustrative implementation.

Transmission of Audio Data through a Network

It should be understood that although the following illustrative example is described in terms of audio data transmission, the present invention encompasses the storage and playback of other types of data as well, such as video data or any other data having a sequential temporal aspect, as described above.

FIG. 2is a block diagram of an exemplary network environment in which a user204inputs audio data through an audio input device208, such as a microphone, connected to a transmitting device20afor transmission to a receiving device20bthrough a network160. The transmitted audio data received by receiving device20bmay be output to an audio output device232, such as speakers, to user236.

Everything that is sent through a packet-switched network is sent in packets, e.g.,216,217,218,219, etc., typically, although not exclusively, in IP format. Packets216,217,218,219, etc. can be fixed in length or variable in length. Each packet216,217,218,219, etc. typically contains a header216a,217a,218a,219a, etc., payload216b,217b,218b,219b, etc. and trailer216c,217c,218c,219c, etc.

Referring now to packet216as an exemplary packet, header216acontains information needed to direct the packet to its intended destination, (the intended receiver's IP address), the sender's IP address, how many packets are contained in the data stream, the sequence number of this packet, synchronization bits and in some cases, protocol (the type of packet being transmitted, including but not limited to e-mail, Web page, streaming video or audio) and length of packet. Length of packet is required for variable length packets.

Payload216bcontains all or a portion of the actual data stream to be transmitted. If a packet216is a fixed-length packet and the data to be transmitted is less than the fixed length, payload216bis typically padded with blanks. Trailer216ctypically contains data for error checking and a few bits for an end-of-packet indicator.

Once packet216is assembled, packet216is released to a routing system (not shown.) Routers are special-use computers that examine the destination address and determine the best available route at the time the packet is transmitted. Routers examine the destination address, compare it to lookup tables to find out where to send the packet, and ascertain current network conditions to determine the best available route. Once packet216arrives at its destination, header216aand trailer216care stripped off. Payload216bis reassembled into a data stream with the payloads of other packets217,218,219etc. based on the numbered sequence of packets216,217,218,219etc.

Each packet released may travel by a different route and may take a different amount of time to arrive at its destination.FIG. 3depicts the transmission time and arrival times for packets transmitted through a packet-switched network160. For example, if packets216,217,218,219, etc. are 100 millisecond (ms) packets containing audio data, packet216may be transmitted from transmitting device20aat time0316and be received by receiving device20bat time0+10326, packet217may be transmitted at time0+100317and be received at time0+230327, packet218may be transmitted at time0+200318and be received at time0+210328and packet219may be transmitted at time0+300319and be received at time0+310329. Thus the amount of time it took for packet216to arrive at its destination was 10, for packet217was120, for packet218was 10 and for packet219was 10. The variation in the time intervals between which packets216,217,218and219are received by receiving device20bis called jitter.

Jitter causes problems for real-time audio applications because proper audio reproduction requires that the packets216,217,218, etc. must be received by the time receiving device20battempts to play them back. For example, if receiving device20bstarts to play packet216at time0+10, at time0+110 packet217needs to be played back to get a continuous audio stream, but at time0+110 packet217has not arrived. Packet217does not arrive until time0+230. This results in a loss of audio data, reducing sound quality. User236hears the sound “breaking up”.

To compensate for jitter, communications applications deployed on packet-based networks typically use a jitter buffer404as depicted inFIG. 4to store audio data until a certain number of packets216,217,218,219,220are received by receiving device20b. As packets216,217,218,219,220are received, audio data216b,217b,218b,219b,220bfrom packets216,217,218,219,220are copied into jitter buffer404in the sequence in which they are to be played. If the size of jitter buffer404is larger than the amount of jitter present in network160, receiving device20bwill be able to play back a smooth and unbroken stream of audio, because audio packets216,217,218,219and220are available in jitter buffer404at the time the packets are needed for playback.

Referring now to FIG4, if, as shown, a jitter buffer404500 milliseconds long is chosen, at time0+10 packet216is received and stored in jitter buffer404cell one404a, at time0+210 packet218is received and stored in jitter buffer404cell three404c, at time0+230 packet217is received and stored in jitter buffer404cell two404b, at time0+310319packet219is received and stored in jitter buffer404cell four404d, and at time0+410 (not shown inFIG. 3) packet220is received and stored in jitter buffer404cell five,404e. At time0+500, receiving device begins to play and will be able to play a continuous stream of audio because 500 milliseconds worth of audio data is stored in jitter buffer404.

If, however, too small a jitter buffer is chosen for the amount of jitter present in network160, a similar result to that discussed above with respect to a situation where no jitter buffer exists: that is, poor sound quality will result. The ideal size of a jitter buffer may change if conditions on the network change so that a jitter buffer that initially was ideal may become too large or too small. The consequence of choosing a jitter buffer that is larger than required is an increase in latency. If the jitter buffer is 500 milliseconds in length, there may be 500 milliseconds of delay attributable to the jitter buffer in addition to any additional latency attributable to the network and other components of the audio communications system. Thus it is desirable to have the smallest jitter buffer adequate to adjust for the amount of jitter present in the network.

Dynamic Sizing of Jitter Buffer to Adapt to Changing Run Conditions

FIG. 5depicts a jitter buffer504in accordance with the present invention. It should be understood that the particular number of elements in jitter buffer504as depicted inFIG. 5is in all ways an arbitrary one and selected for exemplary purposes only. The scope and spirit of the invention encompasses a jitter buffer of any appropriate size and number of elements. In a preferred embodiment jitter buffer504may be an array but it should be understood that the present invention contemplates the use of any suitable data structure.

In accordance with the present invention, the size of jitter buffer504is automatically adjusted in response to changing network and system run conditions that an audio communications application encounters. Reproduction of packets containing audio data placed in jitter buffer504does not occur until a certain number of packets are received. The number of packets that must be received before playback of the packets begins is called the high-water mark508,509,510,511,512or513. The present invention determines the high-water mark508,509,510,511,512or513that most closely results in a target error rate for the application, given the current conditions of the network and the host systems and dynamically adjusts the current high-water mark to that value.

Reproduction of packets containing audio data placed in the jitter buffer does not occur until a certain number of packets are received. For example, if the high-water mark is three511, then jitter buffer504will not release packets for playback until three packets have been received and stored in jitter buffer504or until a time equivalent to three packets since the first packet of the talkspurt was received has passed. Thus if a talkspurt contains 2 packets, each packet representing 100 ms of play, and the high-water mark is 3, play will commence 300 ms after receiving the first packet. This delays the start of playback by three packets, thereby providing a delay three packets in length, which in the example cited above is 300 ms. Playback errors are tracked and the size of jitter buffer504is modified as a function of how many errors in playback occur.

The present invention determines the high-water mark that most closely results in the target error rate for the application, given the current conditions of the network and the host systems. If there is a great deal of jitter, the high-water mark may be larger. If there is little or no jitter, such as may occur on a local area network with dedicated host machines, the high-water mark can be very small or even zero508. On a wide area network with some congestion and non-dedicated hosts, the high-water mark may be much higher. Conditions within the same network configuration may change over time and therefore the high-water mark that results in the closest approximation to the target error rate for the application may change over time. The present invention automatically adjusts the length of delay to achieve the error rate that most closely approaches the target error rate.

The present invention monitors and tracks the error rate experienced at different high-water marks and dynamically selects the high-water mark that provides the error rate closest to the target error rate selected for the application. This provides the application with the lowest latency (delay) achievable at its target error rate, regardless of the environment in which the application is deployed. No user intervention is required for an application using the present invention in order to adapt to these different circumstances. If conditions change while the application is running, the present invention will change the high-water mark to adapt.

Referring now toFIG. 6, in combination withFIG. 5, at step604, all elements of an array or other suitable data structure in which is stored the error rate experienced at each possible high-water mark508,509,510,511,512or513, are set to equal the target error rate for the application. The target error rate will not be the same for every application because generally the lower the error rate required, the longer the latency will be, which is to say, target error rate is generally inversely proportional to latency. Each application may have a different target tradeoff between latency and error rate. For example, a lecture application where one person does all the speaking and others do all the listening can tolerate a very high latency (perhaps several seconds) and will therefore be able to achieve a very low error rate. An interactive application in which two users are having a two-way conversation (similar to a traditional telephone conversation) will require lower latency, but will still demand a relatively low error rate. A gaming application which implements audio communication may require audio playback with low latency but may be willing to tolerate a higher error rate in order to achieve the desired lower latency.

At step608, the current high-water mark508,509,510,511,512or513, representing the number of packets that must be received before reproduction (such as playback) begins, is set to an application-defined value appropriate for the application. The current high-water mark508,509,510,511,512or513is initially an estimate of the length of delay that is required to achieve the desired error rate. After the application is run for the first time, the ending current high-water mark may be saved and used to initialize the starting high-water mark the next time the application is run.

As previously discussed, the target high-water mark is application-dependent because as the high-water mark is increased, the incidents of errors in the playback stream approach zero. An error occurs when a packet necessary for uninterrupted playback is not available (not in the jitter buffer) when it is supposed to be played. Thus, if a user is willing to wait an infinitely long time for a packet to be delivered, unless the packet has been lost by the network, eventually the packet will arrive and thus the error rate will be zero. However this also means that there will be an infinite latency to the audio playback.

For example, referring concurrently to FIG.3andFIG. 5, suppose transmitting device20asends packet216(a 100 ms packet) at time0, packet217at time0+100 and packet218at time0+200. If a receiving device20breceives packet216at time0+10, packet217at time0+230 and packet218at time0+210 and the high-water mark is 1509, at time0+110 packet216will start to play. At time0+210, packet217is needed to play but since packet217will not arrive until time0+230, packet217is not available for playback at time0+210. The listener hears silence. This is counted as an error. At time0+230, packet217arrives “late,” and is discarded. If the high-water mark had been changed to 2510, it would have allowed enough time for packet217to arrive before it was needed to play (at time0+310), packet217would not have been discarded, no error would have resulted, but latency would have been increased by 100 ms.

At step612, an audio segment such as a talkspurt is received. Audio communications applications on packet-based networks often transmit audio data in audio segments called talkspurts. Talkspurts contain variable numbers of packets containing audio data. When a user begins speaking, the software begins transmitting a series of packets to the destination and when the user stops speaking, the application stops transmitting packets.

At step616, the number of errors in each talkspurt is counted. The number of packets in the talkspurt is counted. The error rate is then calculated in accordance with the following formula:
Error rate=the minimum of ((total number of errors in the talkspurt/number of packets in the talkspurt), 1).

Thus if a given talkspurt contained 4 packets, and there were a total of 4 errors in the talkspurt, the error rate for this talkspurt would be min((4/4), 1) or 1. Likewise if a given talkspurt contained 4 packets, and there was a total of 1 error in the talkspurt, the error rate for the talkspurt would be calculated as min((1/4), 1) or 0.25.

The maximum value for error rate is 1, representing one or more errors for each packet in a talkspurt. Every time data is required for playback but has not arrived, it is counted as an error. Note that this can happen more times than there are packets in a talkspurt, hence the minimum function. For example, if a 100 mns packet arrives 310 ms late, 3 errors are counted, one error for each time the packet was needed but had not yet arrived.

An error rate of 0 represents no errors. Every time a packet arrives late, it is counted as an error. A packet that does not arrive by the time the next talkspurt is played, however, is not defined as an error but as lost. A lost packet is not counted as an error because increasing the high-water mark to adapt to a lost packet will not increase the probability that future packets will be successfully delivered. Hence increasing the high-water mark will not result in a lower error rate.

At step620, talkspurts may be weighted in accordance with the following formula:
Talkspurt weighting=minimum ((constant*number of packets in the talkspurt), 1).
The constant in the formula above represents how much weight is assigned to each packet of audio data, or, in other words, how much effect the error rate of a given talkspurt will have on changing the high-water mark. The constant may be set by the application in step608. If it is anticipated that network conditions will be changing quickly, and it is desired that the high-water mark will change correspondingly rapidly, the constant may be set to a high value. If it is anticipated that network conditions are relatively stable, the constant may be set to a low value so that changes to the high-water mark occur relatively slowly. For example, if network conditions are changing rapidly, the weighting constant may be set to a high number, such as 1. If there are 4 packets in a talkspurt, the resulting talkspurt weighting will be:
Talkspurt weighting=min (4, 1) or 1.
If network conditions are generally stable, the weighting constant may be set to a low value such as 0.1. Given the same 4 packets per talkspurt, the resulting talkspurt weighting will be:
Talkspurt weighting=min (0.4, 1) or 0.4.

Thus, for a weighting constant of 0.4, the difference between the value of talkspurt weighting for an audio talkspurt containing one packet and one containing two packets is twofold:For the audio talkspurt containing one packet:
Talkspurt weighting=minimum ((constant*number of packets in the talkspurt), 1).
Talkspurt weighting=min ((0.4*1), 1)=0.4And for a talkspurt containing two packets:
Talkspurt weighting=min ((0.4*2), 1)=0.8
Of course, where the weighting constant multiplied by the number of packets exceeds one, this proportional relationship will no longer exist. For example, for a talkspurt containing 10 packets:
Talkspurt weighting=min ((0.4*10), 1)=1
In this case increasing from one packet (talkspurt weighting=0.4) to 10 (talkspurt weighting=1) does not result in a proportional (tenfold) increase in talkspurt weighting.

After the talkspurt weighting is determined for the current talkspurt, the error rate for the current high-water mark is calculated at step622, in accordance with the following formula:The element of the array corresponding to the current high-water mark is set to:The error rate of the current high-water mark*(1−talkspurt weighting from step620)+talkspurt error rate from step616*talkspurt weighting.

For example, in the case where:Target error rate=0.2Current high-water mark=3Talkspurt weighting=1Error rate for the present talkspurt=0.4Existing error rate for high-water mark (3) stored in the array=0.25Existing error rate for high-water mark (4) stored in the array=0.2The new error rate for the current high-water mark (3) would be calculated as:
0.25*(1−1)+0.4*1 or 0.4
The error rate for high-water mark (3) (previously 0.25) would be changed to 0.4.

Thus if a talkspurt with a higher (worse) error rate than the current error rate is encountered, the error rate stored in the array for the current high-water mark may be increased. The current high-water mark may be also increased, effectively increasing the delay before playback.

To decide whether or not to increase the size of the high-water mark, the error rate at the current high-water mark is compared to the error rate at the next higher high-water mark. Whichever high-water mark whose corresponding error rate is closer to the target error rate becomes the current high-water mark. Hence, in the example, to determine if the high-water mark should be increased, a comparison is made between the error rate at a high-water mark of 3 (0.4) and the error rate at a high-water mark of 4 (0.2). Since 0.2 is closer to the target error rate of 0.2 than is 0.4, in this case the current high-water mark will be changed from 3 to 4 and the next talkspurt will be processed.

Similarly, if the new value of the error rate for the current high-water mark is lower than the target error rate, the high-water mark may be reduced by one packet.

In accordance with another embodiment of the invention, the new value of the error rate for the current high-water mark may be compared with a given range of allowable variation from the target error rate before the array element is updated. If the new error rate is not within the allowable range, the error rate in the array for that high-water mark is set to the low end value or high end value of the allowable range that is closer to the calculated error rate.

In accordance with another aspect of the invention, the high-water mark is not changed unless the error rate for the current high-water mark differs from the target error rate by a certain given percentage (e.g. 20%) or by a certain absolute amount(e.g. 0.1).

According to another aspect of the invention, the target error rate is not constant for the application, but instead changes depending on latency and error rate. As latency increases, a different tradeoff between latency and error rate may be desired. For example, if the network has low jitter and a selection is being made between a high-water mark of 1 or 2 packets (perhaps translating into a delay of 50 ms versus 100 ms) since either latency is quite low, the target error rate should be very low (approaching zero). If, however, a choice must be made between high-water marks in the 8 to 12 range (perhaps translating into delays between 400 ms and 600 ms), the target error rate should be set higher to keep latency lower. Thus a target error rate may be associated with each high-water mark such that the target error rate for a lower high-water mark may be lower than that for a higher high-water mark.

In accordance with this aspect of the invention, each high-water mark is assigned its own factored target error rate according to the following formula:Constant*2⁢N*ms⁢⁢per⁢⁢packet1000
where N represents the value of the current high-water mark and ms per packet represents the number of milliseconds in a packet. Thus for a packet length of 100 ms, where the constant equals 0.01, the factored target error rate for a high-water mark of 1, (N=1), would be 0.01 times 2 to the power of 0.1 or 0.01071773462536. The factored target error rate for a high-water mark of 10, (N=10), would be 0.01 times 2 or 0.02.

According to another aspect of the invention, the present invention places incoming packets into a jitter buffer, placing packets received out of order back into order in the buffer. For example, suppose that a transmitter transmits a talkspurt containing packet216, packet217and packet218. Although the transmitter transmits the packets in order (first216, then217, then218), the receiver may not receive the packets in that order. Because not every packet will follow the same route through a network, the receiver may receive packet216, then packet218and then packet217. In accordance with the present invention, when packet216is placed in the jitter buffer, it will be placed in the jitter buffer in position one for than talkspurt. When packet218is received, packet218will be placed in the jitter buffer in position three for that talkspurt and when packet217is received, packet217will be placed in the jitter buffer in position two for the talkspurt, hence reordering packets into their proper playback order as the packets are placed into the jitter buffer.

In an alternate embodiment, packets received out of order are discarded. In a further embodiment, packets are placed in the buffer in the order in which the packets are received. According to one aspect of the invention, a lost packets is replaced by an empty packet (in an audio application, the listener would hear silence). In another embodiment of the invention, lost packets are ignored and the next available packet is played.

Once the number of packets of audio data at least equal to the current high-water mark is reached the data is ready for playback. It should be noted, however, that as previously discussed, if the length of a talkspurt is smaller than the length of jitter buffer504as determined by high-water mark508,509,510,511,512or513, the queue will release the talkspurt when an equivalent amount of time has passed since the first packet of the talkspurt was received. Thus, if the length of a received talkspurt is 4 milliseconds, but the length of the jitter buffer is 5 milliseconds, after 5 milliseconds have passed from the beginning of the receipt of the talkspurt, the talkspurt will be released from the jitter buffer.

The described invention is appropriate for a computing system that transmits and receives fixed length packets of audio (for example, each packet contains audio data that will take 1 millisecond to play). In such an embodiment the high-water mark would represent a number of packets (e.g. 5 packets) corresponding to a length of delay before playback begins. Since each packet contains 1 millisecond of playback audio, the 5 packets represent 5 milliseconds of audio playback. Since each packet contains the same length of audio data (measured in time), the present invention tracks the number of packets received and stored sequentially in an array or other suitable data structure before playback begins, resulting in a 5 millisecond length of delay before playback.

The described invention is also appropriate for systems that use variable length packets of audio (that is, each packet does not contain the same amount of audio data). In such an embodiment the high-water mark would represent some number of milliseconds of audio playback (say 5 ms of playback) which may not represent a set number of packets. For example, if packet1contained 1 millisecond of audio data, packet2contained 3 milliseconds of audio data and packet3contained 2 milliseconds of audio playback, the high-water mark would be 5 (representing 5 milliseconds of audio playback) so that in the above described instance, the audio data providing 5 ms of playback is received in three packets. When packet2arrives, 5 milliseconds of audio is not available to play. When packet3arrives, 6 milliseconds of audio is available to play. Because at least 5 milliseconds of playback is now available to play, playback can commence. It should be noted that although a particular number of packets and milliseconds has been described for exemplary purposes, the spirit and scope of the invention includes the use of any suitable number of packets or milliseconds for jitter buffer size.

Exemplary Computing Environment