Patent Publication Number: US-6912224-B1

Title: Adaptive playout buffer and method for improved data communication

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The invention relates to data communications and, more particularly, to improvements in the management of playout buffers (POB) in packet-based communications networks. 
   2. Description of Prior Art 
   In order to transport constant bit rate (CBR) traffic, such as telephone conversations or real time video transmissions, modern high-speed, packet-based telecommunications networks, such as those based on Asynchronous Transfer Mode (ATM) technology, make use of playout buffers in receiving nodes at the edge of the network to smooth out differences in the queuing delays that each packet in a data stream experiences as it passes through the network. 
   The playout buffer is generally arranged to operate as a first-in/first-out (FIFO) buffer in which data is placed when it arrives at the node. Data is then dequeued from the playout buffer uniformly so as to preserve the constant bit rate of the data stream being transmitted. Packet sequence numbers can be used to ensure the data is played out in the correct order and to detect packet loss. 
   The use of a playout buffer inevitably introduces an overall end-to-end delay in the data stream being transmitted. For real time applications, it can be vitally important to minimize this delay. For example, for voice traffic in a telephone application, an end-to-end delay of more than about 200 milliseconds will be perceivable by the parties in a call. This is clearly undesirable for users and may require the use of echo cancellation techniques or the like. 
   A variety of techniques have been proposed for the management of playout buffers. Typically, these techniques involve estimating the maximum variation in the transmission delay expected for each packet as it passes through the network, the variation being a parameter also known as the maximum jitter or maximum cell delay variation (CDV). In ATM networks the CDV parameter is estimated by the routing mechanisms at call set-up time. The size of the playout buffer is chosen such that variations in cell arrival time of this order can be smoothed. The end-to-end delay introduced using this approach is then approximately equal to the maximum jitter estimated for the packet data stream. Special techniques are generally provided to handle the relatively rare cases when the playout buffer is either full when a packet arrives, which is referred to as an overrun, or empty when a packet is due to be played out, which is referred to as an underrun. 
   U.S. Pat. No. 5,450,410 issued Sep. 12, 1995, describes such management of a playout buffer and accompanying conventional underrun and overrun processing. In the system described in the &#39;410 patent, if the number of packets in the buffer is greater than a threshold L when a packet arrives, the arriving packet is dropped; and if the number of packets in the buffer falls below a threshold K, a dummy packet is enqueued in the buffer to avoid an underrun. 
   PCT application published under number WO 95/14337 proposes a system in which arriving packets are time stamped before being placed in a playout buffer. An adaptive algorithm periodically measures the longest waiting times of packets in the playout buffer and adjusts the packet playout times so that the expected longest waiting time will be equal to the expected maximum jitter. 
   Techniques are also required to deal with possible slight differences in clock speeds at each end of a CBR link. This can lead to a drift in the average filling level of the playout buffer which, if not corrected, can lead to excessive overruns or underruns. 
   One standard method to adjust the filling level in the Play Out Buffer (POB) for asynchronous communication is called Adaptive Clock Recovery (ACR), described in International Telecommunication Union (ITU) recommendation I.363.1. The average waiting time in the POB is monitored. When the waiting time is too great or tends to increase with time, the frequency of the service clock between an edge node or IWF and a Private Branch Exchange (PBX) is increased to cause the POB to drain more quickly. When the average waiting time is too small, the service clock is decreased to cause the POB to drain less quickly. Adaptive Clock Recovery is appropriate for an asynchronous situation where the input service clock frequency must be recovered at the output IWF. However, it is not suitable for a synchronous situation where the service clock frequency is constant. 
   The problem with the above described conventional POB management techniques is that the methods used to estimate the maximum jitter are somewhat imprecise. Commonly, the maximum end-to-end delay for a particular connection is calculated based on the assumption that the maximum delay is bounded by the sum of the maximum delays in each link in the network path allocated to the connection. Moreover, the maximum delay per link is often computed as the maximum buffer size at the link divided by the line speed. In consequence, the resulting estimate of the maximum jitter is generally extremely pessimistic. The inventors have found that, under realistic network conditions, the estimated maximum jitter is often more than 10 times greater than the actual jitter experienced over a long period of time. 
   Furthermore, the jitter experienced on any particular connection within the network can change rapidly over time due to changing network conditions, such as other connections being set up and removed. 
   SUMMARY OF THE INVENTION 
   An object of the present invention to provide a simple technique for managing a playout buffer in a communication network in order to reduce end-to-end communication delay introduced therein and to adjust the POB filling level in the event of clock speed differences. 
   Another object is an apparatus and method for improving performance of a playout buffer in a communications network. 
   Another object is an apparatus and method including control logic arranged to alter the filling level of a playout buffer occurring to a threshold. 
   Another object is an apparatus and method of reducing average packet waiting time and gradual drifts in a playout buffer in a communication network due to clock signal speed differences. 
   Another object is an adaptive playout buffer reducing average packet waiting time and gradual drifts in a communication network due to clock signal speed differences which are automatically corrected. 
   In brief, this object is achieved by data receiver apparatus for use in an edge node of a packet based data communications network. The apparatus includes a playout buffer for controlling the rate at which data arriving at the apparatus is processed. A mechanism is provided for monitoring the minimum filling level of the playout buffer over a time period and the average filling level of the playout buffer is reduced according to the minimum filling level of the playout buffer over the time period. 
   In a preferred embodiment, the monitoring mechanism comprises means arranged to repeatedly compare the filling level of the playout buffer with a threshold and control logic is arranged to reduce the average filling level of the playout buffer if the filling level of the playout buffer has remained above the threshold over the time period. 
   Suitably, the apparatus can be arranged to reduce the average filling level of the playout buffer at the end of the time period by removing data, preferably a predefined number of bytes, from the playout buffer. Existing slip mechanisms for handling overruns can thereby be employed. 
   With this arrangement, the average waiting time in the POB is reduced and gradual drifts in the POB filling level due to clock speed differences are automatically corrected. In addition, the data loss caused by the slips is distributed over time thereby reducing the impact on the quality of the connection. 
   The playout buffer can have a fixed size for each data connection, the fixed size being established when the connection is set up. This enables rapid variations in the jitter in the network to be accommodated without excessive overruns or underruns. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the appended drawings, in which: 
       FIG. 1  shows data communications apparatus; 
       FIG. 2  shows an edge node in the apparatus of  FIG. 1  incorporating the principles of the present invention; 
       FIG. 3  is a flow diagram illustrating a playout buffer management algorithm in the apparatus of  FIG. 2 ; and 
       FIG. 4  shows examples of the effects of the algorithm of  FIG. 3  in the apparatus of FIG.  2 . 
   

   DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS OF THE INVENTION 
     FIG. 1  is a schematic diagram showing a data communications system in which two Private Branch Exchanges (PBX)  100  are interconnected via a CBR connection within an ATM data communications network  120 . PBXs  100  are connected to the network at edge nodes  110 . Edge nodes  110  provide an interworking function (IWF) to convert the Constant Bit Rate (CBR) traffic from the PBX into ATM cells for transmission over network  120 . 
   While this embodiment has been developed for use in ATM networks, it will be appreciated that the techniques to be described would be equally applicable to other types of packet-based networks, such as those based on Frame Relay or the Internet Protocol (IP). 
   As shown in  FIG. 2 , edge nodes  110  comprise an interface  200  for interfacing with the PBX nodes  100 , Playout Buffer (POB)  230  and associated control logic  240 . Node  110  includes packetizer  201  which places data to be transmitted from PBX  1000  into data packets which are then sent over ATM network  120  over link  210 . Packets received from network  120  arrive over link  220 . The packet headers are removed by depacketizer  202  and the packet payload data are placed in playout buffer  230 . The payload data is then removed from playout buffer  230  in a controlled manner so as to preserve the constant bit rate nature of the traffic. The data is passed to the PBX via interface  200 . 
   The general operation of such a communications system is conventional and, as such, will be well understood by those skilled in the art. 
   The playout buffer  230  is managed by control logic  240  so as to minimize the queuing delay and the number of overruns and underruns on the basis that the maximum jitter can be experienced only when the network is highly congested with a large number of low speed connections at the highest priority. In most other configurations, the jitter experienced is much smaller. 
   Conventional processes, known as slips, are provided to handle underruns and overruns. The standard process for handling an underrun consists of adding a predefined number of bytes to the POB. This kind of slip increases the waiting time for each packet inside the POB. In the case of an overrun, the standard process consists of suppressing a predefined number of bytes to adjust the length of the data inside the POB. 
   Again, as is conventional, the size of the POB is set for each connection at call set-up time in accordance with the maximum jitter (JMAX) expected for that connection. The size of the POB for each connection remains fixed. 
   In addition to these conventional processes and in order to minimize the waiting time in the POB, the algorithm employed by control logic  240  is such that if the minimum waiting time in the POB is greater than a threshold during a defined period of time, a slip is performed at the end of the period to remove a quantity N-bytes of data from the POB. 
     FIG. 3  is a flow chart illustrating this aspect of the playout buffer management algorithm. 
   The process is as follows. A timer is started in step  300 . Each time a packet is received from the network the current POB level is checked against a threshold in step  310 . If the current POB level is less than or equal to the threshold then a flag B is set to  1  in step  320 . The POB level is then augmented by the number of bytes in the received packet in step  330 . Of course, each time a packet is removed from the POB, the POB level will be reduced by the number of bytes in the packets which is removed. This aspect is not shown in  FIG. 3 , but is conventional. 
   A check is made in step  340  to see whether the timer has expired. If not, the system waits to receive another packet from the network, which is processed in the same way. If the timer has expired, it is determined whether the flag B has been set to  1  in step  350 . If it has, then B is set to zero, the timer set to zero and the process repeated. If B has not been set to one, i.e., POB level has remained greater than the threshold throughout the timer period, then in this case, N-bytes of data are removed from the POB in step  360  before the process is repeated. 
   In practical embodiments the timer period can be of the order of one minute. During this time a very large number of packets will normally have been received and processed via the POB. 
   The effect of this algorithm is illustrated in the following examples. In  FIG. 4  graphs A, B and C the filling level of the POB is represented schematically on the Y axis and time on the X axis. The timer periods are represented as T 1 , T 2  and T 3 . The filling level of the POB is shown as being oscillatory for the purposes of illustration, although it will of course be understood that the variation of the POB is in reality somewhat random depending upon the arrival times of packets over the network. 
   Referring to graph A of  FIG. 4 , the jitter in this example is small and clocks are synchronized. The minimum waiting time remains fairly constant, and smaller than the threshold which has been chosen at JMAX/ 10 . The algorithm does not trigger any adjustment since the minimum waiting time is sufficiently low. 
   Referring to graph B of  FIG. 4 , the network experiences a large jitter during a limited period of time  400 . 
   The jitter increases the average waiting time in the POB. When the jitter in the network decreases, the minimum waiting time in the POB becomes higher than the threshold throughout period T 3 , and the algorithm performs an adjustment, indicated at  410 , at the end of period T 3  to decrease the minimum waiting time. 
   Referring to graph C of  FIG. 4 , the PBX clock on the transmit side has a slightly higher frequency than the PBX clock of the receive side. The waiting time in the POB increases and the minimum waiting time remains greater than the threshold during period T 1 . The algorithm performs an adjustment, indicated at  420 , at the end of the period to decrease the minimum waiting time before the occurrence of any overruns. The buffer is never overloaded, and the waiting time in the POB is reduced. 
   It can be seen that, using the above described algorithm, the average waiting time in the POB is reduced and gradual drifts in the POB filling level due to clock speed differences are automatically corrected. However, since the POB size is unchanged, rapid variations in the jitter in the network can be accommodated without excessive overruns or underruns. Moreover, data loss caused by the slips is distributed over time thereby reducing the impact on the quality of the connection. 
   While the invention has been described in terms of preferred embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.