CN1726677A - System and method for detecting packet loss in a streaming application using a ring buffer - Google Patents

Abstract

A ring buffer, ie a chain of buffers forming a ring, is provided for managing packet loss detection in Internet streaming. Using the size of the buffer chain to determine the detection delay can dynamically adapt to network conditions and application requirements. The present invention can achieve reasonable detection accuracy.

Description

System and method for detecting packet loss in a streaming application using a ring buffer

The present invention relates to packet loss detection in Internet streaming. More specifically, the present invention relates to a system and method for detecting packet loss in Internet streaming using a ring buffer implemented by a chain of buffers forming a ring. More particularly, the present invention relates to a system and method for dynamically adapting packet loss detection latency (latency) to network conditions and application requirements, wherein said packet loss detection latency is determined by the size of said chain Certainly, the systems and methods of the present invention can achieve reasonable detection accuracy and are easy to implement.

In Internet streaming applications, when an important packet (such as belonging to an I frame in video or a base layer in scalable coding) is lost, the receiver may ask the sender to retransmit the lost packet. In order to send retransmission requests quickly, the receiver must have means for detecting packet loss in time. Currently, packet loss detection is performed using timers or time windows.

In the Transmission Control (TCP) protocol, for loss detection, timers are used. When a packet is sent, a timer with a timeout value is set by the sender of the packet. If the timer expires before the packet is acknowledged as received, the packet is declared lost and retransmitted by the sender.

In most streaming applications, loss detection is achieved through the use of time windows. A time window (or rather a table) has a fixed number of binary entries. Each entry indicates the status of the packet (0: lost, 1: received). At some point in time, the first entry in this window is associated with a packet identified by a sequence number, such as that of a real-time transport protocol (RTP) packet. Subsequent window entries are associated in sequential order with packets with higher sequence numbers. Therefore, the space of the packet sequence number can be regarded as being divided into blocks, and each block is associated with a window at a certain time point.

Currently, two such time windows associated with two consecutive packet blocks are used for packet loss detection. To start, mark all entries as "0". When a packet is received, the corresponding window entry is marked as "1". When a packet with a sequence number exceeding the first window is received, the corresponding second window entry is marked. As soon as a packet with a sequence number that exceeds even the second window is transmitted, the first window is closed and its entries are checked. Packets associated with entries that remain marked "0" are declared lost. Immediately after the second window, a successive new window is opened and the detection process continues.

The timer method can only be applied to protocols like TCP that can measure packet round trip time in order to set the timer timeout value correctly. In streaming applications, only one-way media streams are generated most of the time. The timer method is not suitable for these cases. Instead, a time window approach can be used. However, the time window method has the following limitations:

• The window size is fixed - there is no built-in mechanism for window size adaptation, which is desirable as network conditions and application requirements (eg, latency) change.

Non-uniform loss detection delay for different losses - the loss detection delay lies in the range T-2T, where T is the average period of the time window, so when associating a loss with the first entry of the window , the detection latency is 2T, which is T if the loss is associated with the last entry of the window.

Thus, there is a need for a loss detection method that allows adaptive loss detection delay as well as uniform loss detection delay. The systems and methods of the present invention include:

· Ring buffer chains with adjustable chain sizes based on network conditions and application requirements, thereby providing adaptive loss detection latency; and

• A ring buffer chain with a fixed chain size, thus providing uniform detection when the chain size is fixed.

Shortening the delay increases the chance of recovering lost packets. Having a uniform delay may imply an equal probability of recovery for all losses. Therefore, having all loss detections with a specific equal delay is desirable for many streaming applications.

The implementation overhead of the ring buffer of the present invention is small and less than that of the time window method.

Figure 1a illustrates a preferred embodiment of the ring buffer structure of the present invention.

Fig. 1b illustrates the structure of each buffer in the ring buffer shown in Fig. 1a.

Figure 2a illustrates a preferred algorithm for implementing the ring buffer structure shown in Figures 1a-1b.

Figure 2b illustrates a flowchart of the algorithm shown in Figure 2a.

Figure 3 illustrates a preferred embodiment of an algorithm for adapting a ring buffer chain structure based on network characteristics.

Referring now to FIG. 1a, buffers 1 to m form a circular linked list of m buffers B _i 10, where i=, . . . , m, the structure 12 of each buffer is shown in FIG. 1b. As shown in Figure 1a, m is the length of the cyclic chain used to determine the loss detection delay, and it can be adapted to network conditions as well as application requirements. P11 is a pointer that flows through the chain ring, pointing to each buffer in turn. Each buffer B _i 10 in the chain comprises two fields, F ₁ 13 and F ₂ 14 . F ₁ 13 stores a pointer to the next buffer. F ₂ 14 stores sequence numbers s of packets that may have been lost.

In streaming applications, it is assumed that packets are sent in sequence number order. In an ideal world with no loss, arriving packets would always have a sequence number higher than the previous sequence number. If packets arrive out of order, or are lost, gaps or gaps may be observed in the sequence numbers of received packets. Whenever a gap is observed (possibly a gap separated by more than one consecutive number), then the gap likely indicates one or more lost packets. However, out-of-order packet delivery is common to the Internet because each packet may take a different path through the network, and earlier numbered packets may take longer to arrive than later numbered packets. An application cannot make a loss claim immediately after a gap is observed in the sequence of arriving packets. The application has to wait and see if this gap is just an event of out-of-order delivery. The ring buffer method provides a way to determine whether a loss assertion can be performed.

Figure 2a illustrates the C programming language code of a preferred embodiment of the algorithm for implementing the method of the present invention. Figure 2b is a flowchart of the algorithm shown in Figure 2a. Said pointer P12 cycles through the chain of buffers B _i 11 , said cycle being driven by the packet received at step 20 . In step 21, the sequence number of the received packet is checked against the current maximum sequence number s received already, and if it is less than the current maximum sequence number received, then it is an out-of-order packet.

If it is not an unordered grouping, then at step 22, a gap in the sequence is checked, and when a gap in the sequence is observed, the following steps are performed:

a. If the buffer that P is pointing to contains unreceived packets (P->F2 is not zero, at step 24), then at step 25, the packet with sequence number P->F2 is declared lost.

b. Then, regardless of whether P once pointed to an unreceived packet, in step 26, the current maximum sequence number is increased by one, and stored in the current buffer, and P is updated to point to the next buffer in turn, that is, P=P->F1.

c. At step 27, decrement the number of buffers falling into gaps by 1, and repeat steps a-c until the number of remaining buffers is zero. Thus, all sequence numbers falling into gaps are stored in a chain of circular buffers, each number occupying one buffer.

When no vacancies are observed, the following steps are performed:

d. At step 28, if the buffer pointed to by P contains an unreceived packet (P->F2 is not zero), then at step 29, the packet with sequence number P->F2 is declared lost and stored in The sequence number in the buffer is set to zero.

e. Regardless of whether P->F2 points to an unreceived packet, at step 30, update P to point to the next buffer in sequence.

When all processing associated with ordered grouping is complete:

f. In step 31, set the current maximum sequence number as the sequence number of the received packet.

If the packet arrived out of order (with an earlier sequence number than the currently received largest sequence number s):

g. The received packet number is then compared with the number stored in said ring buffer and the corresponding record in the buffer is cleared, ie set to zero, step 32 .

Thus, the detection delay can be determined by the size m of the buffer chain, since a loss declaration is only made when the pointer revisits a non-empty buffer, ie when F2 is non-zero.

As shown in Figure 3, the chain size m can be used to determine the detection delay. For example, in a preferred embodiment initially m=4. If the observed false claim rate is above a given threshold, i.e.,

false_rate > TOLERABLE_RATE

Then the length may be too short and the length 36 needs to be extended by inserting new buffers and adjusting m accordingly. The larger the length of the network path, that is, the greater the number of traversing links, the larger the required m is, because the longer the network path traversed by the packet, the greater the possibility of out-of-order delivery. As P cycles through the chain of buffers B _i 11, a larger value of m reduces the probability that pointer P will encounter a delivered but out-of-order packet in the buffer.

The success_rate is initially declared as a predetermined EXPECT_RATE and thereafter adjusted to:

$\mathrm{<span\; class="notranslate">\; Success</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; rate</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; declared</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; loss</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; false</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; declared</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; losses</span>}}{\mathrm{<span\; class="notranslate">\; declared</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; losses</span>}}$

false_rate=1-success_rate

and if the success_rate is too high, i.e., if

success_rate > EXPECT_RATE

Then, the length of the buffer chain would be too long and may need to be shortened by deleting buffers, as shown in Figure 3.

The invention can be used in the implementation of a multimedia player that plays media from networked storage. Alternatively, the present invention may be used by any type of multimedia receiver that wishes to use retransmissions as a means of error recovery and therefore needs to perform packet loss detection. Finally, the invention can be used by a TCP implementation that performs packet loss detection on the receiver side.

The method and system of the present invention as described above and shown in the accompanying drawings provides a circular buffer for allowing adaptive delay detection time or fixed delay detection time. It will be apparent to those skilled in the art that various modifications and variations can be made in accordance with the methods and system of the present invention without departing from the spirit and scope of the invention. Thus, the present invention includes modifications and variations that come within the scope of the appended claims and their equivalents.

Claims (14)

1. A system for adaptively detecting, by a receiver, a streaming packet loss in a plurality of streaming packets transmitted from a given sender to the receiver over a network, the system comprising:

a circular buffer (10) having a size m > 1 entries (13), each entry (13) having at most one sequence number (15) of streaming packets that have not yet been received and may be lost;

-a packet loss detection module (33) for detecting and storing therein sequence numbers (15) of non-received and possibly lost packets using said circular buffer (10), in order to detect therein sequence numbers (15) of lost packets and to remove therefrom sequence numbers (15) of said lost packets and declare said packets lost, and to remove therefrom sequence numbers (15) of possibly lost packets received from a given sender;

an adaptation module (37) for adapting the system to network conditions, wherein the loss detection latency is determined by the size m of the circular buffer (10) and the loss declaration may be false.

2. The system of claim 1, wherein m is initially set to 4.

3. The system of claim 1, further comprising:

a variable s having an initial value of 1 and used to store the highest sequence number of streaming packets transmitted from a given transmitter via the network and received by the receiver;

a pointer P (12) having an initial position pointing to a predetermined location in a circular chain and for sequentially cycling through m entries of the circular buffer (10) starting from an entry (13) in the next circular buffer (10) sequentially to an entry (13) corresponding to a variable s;

wherein,

for a streaming packet received from a given sender, the packet loss detection module (33) checks the sequence number of the received packet against a variable s and performs one of the following steps:

a. if an absence in the received sequence of packets is observed starting from the point pointed to by the pointer P (12), each entry (13) of the circular buffer (10) in said absence is checked to find the sequence number (15) of a packet that may be lost and declares that the corresponding packet is lost, the total declared loss is incremented, each sequence number in the absence is stored in ascending order in the consecutive entries (13) starting from the point pointed to by the pointer P (12), P (12) is updated to point to the entries (13) in the circular buffer (10) following the absence, and s is set to a sequence number equal to the received pkt,

b. if no holes in the received sequence of packets are observed, the entry (13) pointed to by the pointer P (12) is checked to find the sequence number (15) of a packet that may be lost and declares that the corresponding packet is lost, the total declared loss cleared _ losses is incremented, the entry (13) is cleared, P (12) is updated to point to the next entry (14) in the ring buffer (10), and s is set equal to the sequence number of the received pkt,

c. if out-of-order packets are observed, entries of the circular buffer (10) are searched to find an entry containing a sequence number (15) equal to the sequence number of the received packet, if found, the entry is cleared (13), if not found, the false declaration rate false _ cleared _ losses is as one.

4. The system of claim 3, wherein:

the network condition is at least one of a success RATE (success RATE) and a false declaration RATE (false RATE) of transmission, wherein the success RATE is initially set to a predetermined desired RATE (EXPECT _ RATE); and is

The adaptation module (37) adjusts the size m of the circular buffer (10) according to network conditions as follows:

a. if false _ RATE > TABLE _ RATE, which is a predetermined threshold, then m is incremented and an entry (13) is added to the circular buffer (10), otherwise

b. If it is not

${\mathrm{success}}_{-}\mathrm{rate}=\frac{{\mathrm{declared}}_{-}\mathrm{losses}-{\mathrm{falsely}}_{-}{\mathrm{declared}}_{-}\mathrm{losses}}{{\mathrm{EXPECT}}_{-}\mathrm{RATE}}>{\mathrm{EXPECT}}_{-}\mathrm{RATE}$

Then m is decreased and the entry (13) is removed from the circular buffer (10).

5. The system of claim 4, wherein the ring buffer (10) is a chain of ring buffers (10) of m > 1 buffers Bi, i 1.. said, m, such that each of the plurality of buffers is an entry (13) comprising a pointer to a next buffer (14) in the chain and a value for storing a sequence number (15) of an unreceived buffer, and the pointer P (12) points to a buffer in the chain.

6. A system for adaptively detecting, by a receiver, a streaming packet loss in a plurality of streaming packets transmitted from a given sender to the receiver over a network, the system comprising:

a circular buffer (10) having a size m > 1 entries (13), each entry (13) having at most one sequence number (15) of streaming packets that have not yet been received and that may be lost;

-a packet loss detection module (33) for detecting and storing therein sequence numbers (15) of non-received and possibly lost packets using said circular buffer (10), for detecting and removing therefrom sequence numbers (15) of lost packets and declaring said packet loss, and for removing therefrom sequence numbers (15) of possibly lost packets received from a given transmitter;

means for adapting the system to network conditions (37), wherein the loss detection latency is determined by the size m of the circular buffer (10) and the loss declaration may be false.

7. The system of claim 6, further comprising:

a variable s having an initial value of 1 and used to store the highest sequence number of streaming packets transmitted from a given transmitter via the network and received by the receiver;

a pointer P (12) having an initial position pointing to a predetermined location in a circular chain and for sequentially cycling through m entries of the circular buffer (10) starting from an entry (13) in the next circular buffer (10) sequentially to an entry (13) corresponding to a variable s; wherein,

for a streaming packet received from a given sender, the packet loss detection module (33) checks the sequence number of the received packet against a variable s and performs one of the following steps:

a. if an absence in the received sequence of packets is observed starting from the point pointed to by the pointer P (12), each entry (13) of the circular buffer (10) in said absence is checked in order to find the sequence number (15) of a packet that may be lost and declare that the corresponding packet is lost, the declared lost clear-losses is incremented, each sequence number in the absence is stored in ascending order in the consecutive entries (13) starting from the point pointed to by the pointer P (12), P (12) is updated in order to point to the entries (13) in the circular buffer (10) following the absence, and s is set to a sequence number equal to the received pk t,

b. if no holes in the received sequence of packets are observed, the entry (13) pointed to by the pointer P (12) is checked to find the sequence number (15) of a packet that may be lost and declares that the corresponding packet is lost, the total declared loss cleared _ losses is incremented, the entry (13) is cleared, P (12) is updated to point to the next entry (14) in the ring buffer (10), and s is set equal to the sequence number of the received pkt,

c. if out-of-order packets are observed, the entries (13) of the circular buffer (10) are searched to find entries containing sequence numbers (15) equal to the sequence numbers of the received packets, and if found, the entries (13) are cleared, and if not found, the false declaration rate false _ cleared _ losses is incremented by one.

8. A method for adaptively detecting, by a receiver, a streaming packet loss in a plurality of streaming packets transmitted from a given sender to the receiver over a network, the method comprising the steps of:

providing a circular buffer (10) of size m > 1 entries, each entry (13) having at most one sequence number (15) of streaming packets that have not yet been received and may be lost;

receiving a streaming packet having a sequence number from a given transmitter;

using the circular buffer (10) and the received packed sequence numbers to perform one of the following steps:

a. detecting and storing in the ring buffer (10) the sequence numbers (15) of packets not received and possibly lost,

b. detecting and removing sequence numbers (15) of lost packets from the circular buffer (10) and declaring said packet loss such that the loss declaration may be false, and

c. removing from the circular buffer (10) sequence numbers (15) of potentially missing packets corresponding to sequence numbers of received packets;

the method is adapted to network conditions such that the size m of the circular buffer (10) is used to determine the loss detection delay.

9. The method of claim 8, further comprising the steps of:

providing a variable s with an initial value of 1;

setting the provided variable to s ═ max (s, sequence number of received streaming packet);

providing a pointer P (12), said pointer P (12) having an initial position pointing to a predetermined location in the ring buffer (10) for sequentially cycling through m entries of the provided ring buffer (10) starting with an entry (13) in the next ring buffer (10) in sequence to an entry (13) corresponding to the variable s;

for a streaming packet received from a given sender, the sequence number of the received packet is checked against a variable s and one of the following steps is performed:

a. if a gap in the received sequence of packets is observed starting from the location pointed to by the pointer P (12), then

a.1 checking each entry (13) of the ring buffer (10) in said vacancy for finding the sequence number (15) of a packet that may be lost and declaring that the corresponding packet is lost,

a.2 if packet loss is declared, adding one to the total declared loss classified _ losses,

a.3 storing each sequence number in the absence in ascending order in successive entries (13) starting from the location pointed to by the pointer P (12),

a.4 updating the pointer P (12) to point to an entry (13) in the ring buffer (10) after the vacancy, and

a.5 setting s equal to the sequence number of the received pkt;

b. if no gaps in the received sequence of packets are observed, then

b.1 checking the entry (13) pointed to by the pointer P (12) to find the sequence number (15) of a packet that may be lost and declaring that the corresponding packet is lost,

b.2 if packet loss is declared, then the total declared loss cleared losses is increased by one,

b.3 clearing the entry (13) pointed to by P (12),

b.4 updating P (12) to point to the next entry (14) in the ring buffer (10), and

b.5 setting s equal to the sequence number of the received pkt;

c. if out-of-order packets are observed, then

c.1 searching the entries (13) of the circular buffer (10) for an entry containing a sequence number (15) equal to the sequence number of the received packet,

c.2 if found, clearing the entry (13),

c.3 if not found, add one to the false declaration rate false _ classified _ losses.

10. The method of claim 9, wherein:

the network condition is at least one of a success RATE (success RATE) and a false declaration RATE (false RATE) of transmission, wherein the success RATE is initially set to a predetermined desired RATE (EXPECT _ RATE); and is

The adapting step adjusts the size m of the circular buffer (10) in dependence on network conditions by performing one of the following steps:

d. if false _ RATE > TOLERABLE _ RATE, where TOLERABLE _ RATE is a predetermined threshold, the following steps are performed:

d.1 adding m to 1, and

d.2 adding an entry (13) to the circular buffer (10), otherwise

e. If success _ RATE > EXPECT _ RATE

e.1 reducing m by 1,

e.2 removing the entry (13) from the ring buffer (10).

11. The method of claim 9, wherein m is initially set to 4.

12. A computer program product for use with a processor, adapted for use by a receiver in detecting streaming packet loss in a plurality of streaming packets transmitted from a given sender to the receiver over a network, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a circular buffer (10) of size m > 1 entries (13), each entry (13) having at most one sequence number (15) of streaming packets that have not yet been received and may be lost;

a packet loss detection routine (33) comprising instructions for using the circular buffer (10) to detect and store therein sequence numbers (15) of non-received and potentially lost packets, detecting and removing therefrom sequence numbers (15) of lost packets and declaring said packet loss, and removing therefrom sequence numbers (15) of potentially lost packets received from a given transmitter;

an adaptation routine (37) comprising instructions for adapting the system to network conditions,

wherein the loss detection delay is determined by the size m of the circular buffer (10) and the loss assertion may be false.

13. The computer program product of claim 12, further comprising:

a variable s having an initial value of 1 and used to store the highest sequence number of streaming packets transmitted from a given transmitter via the network and received by the receiver;

a pointer P (12) having an initial position pointing to a predetermined location in the circular chain and for sequentially cycling m entries of the circular buffer (10) starting from an entry (13) in the next circular buffer (10) sequentially to an entry (13) corresponding to a variable s;

wherein,

for streaming packets received from a given sender, instructions of the packet loss detection routine (33) check the sequence number of the received packet against a variable s and perform one of the following steps:

a. if an absence in the received sequence of packets is observed starting from the point pointed to by the pointer P (12), each entry (13) of the circular buffer (10) in said absence is checked in order to find the sequence number (15) of a packet that may be lost and declare that the corresponding packet is lost, the total declared loss is incremented, each sequence number in the absence is stored in ascending order in the consecutive entries (13) starting from the point pointed to by the pointer P (12), P (12) is updated in order to point to the entries (13) in the circular buffer (10) following the absence, and s is set to a sequence number equal to the received pkt,

b. if no holes in the received sequence of packets are observed, the entry (13) pointed to by the pointer P (12) is checked to find the sequence number (15) of a packet that may be lost and declares that the corresponding packet is lost, the total declared loss cleared _ losses is incremented, the entry (13) is cleared, P (12) is updated to point to the next entry (14) in the ring buffer (10), and s is set equal to the sequence number of the received pkt,

c. if out-of-order packets are observed, the entries (13) of the circular buffer (10) are searched to find an entry containing a sequence number (15) equal to the sequence number of the received packet, and if found, the entries (13) are cleared, if not found, the false declaration rate false _ declared _ losses is added together and the total declared loss classes is decremented by one.

14. The computer program product of claim 13, wherein:

the network condition is at least one of a success RATE (success RATE) and a false declaration RATE (false RATE) of transmission, wherein the success RATE is initially set to a predetermined desired RATE (EXPECT _ RATE); and is

The adaptation routine (37) adjusts the size m of the circular buffer (10) according to network conditions as follows:

a. if false _ RATE > TABLE _ RATE, then m is incremented, where

A TABLE _ RATE is a predetermined threshold and an entry (13) is added to the circular buffer (10), otherwise

b. If it is not

${\mathrm{success}}_{-}\mathrm{rate}=\frac{{\mathrm{declared}}_{-}\mathrm{losses}-{\mathrm{falsely}}_{-}{\mathrm{declared}}_{-}\mathrm{losses}}{{\mathrm{EXPECT}}_{-}\mathrm{RATE}}>{\mathrm{EXPECT}}_{-}\mathrm{RATE}$

Then m is decreased and the entry (13) is removed from the circular buffer (10).

Images