US 7539187 B2
A forward error correction (FEC) encoding system and method optimized for protecting real-time audio-video streams for transmission over packet-switched networks with minimal latency. Embodiments of this invention provide bandwidth-efficient and low-latency FEC for both variable and constant bit-rate MPEG-encoded audio and video streams. To maximize bandwidth-efficiency and playable frame rate for recovered media streams, embodiments of the invention may sort packets by content type and aggregate them into FEC blocks weighted by sensitivity in the recovered stream to packet loss of a particular content type. Embodiments of this invention may use temporal constraints to limit FEC block size and thereby facilitate their use in the transport of VBR streams.
1. A system for low-latency content-sensitive forward error correction comprising:
a first node selected from a group of nodes wherein said first node is coupled with said network and
wherein said first node comprises:
at least one packetizer;
a checksum generator;
a forward error correction module coupled with said checksum generator;
a time clock to time stamp a first packet and a second packet wherein said time clock is coupled with said checksum generator;
a packet multiplexer timestamper module coupled with said at least one packetizer and further coupled with said time clock and further coupled with said checksum generator and further coupled with said forward error correction module;
said packet multiplexer timestamper module configured to filter packets based on a first packet type for processing by said forward error correction module and wherein said packet multiplexer timestamper is configured to transmit checksum packets based on a time obtained from said time clock;
a plurality of second nodes selected from said group of nodes wherein said plurality of second nodes are coupled with said network and wherein said plurality of second nodes comprises:
a receiver timestamper;
a receiver time clock coupled with said receiver timestamper;
a forward error correction processing and recovery module coupled with said timestamper comprising a packet filter coupled with at least one packet queue and at least one checksum queue wherein said forward error correction processing and recovery module further comprises a forward error correction engine coupled with said at least one packet queue and said at least one checksum queue;
said forward error correction engine configured to output received packets in correct order with minimal latency; and,
said first node configured to transmit to said plurality of said second nodes.
2. The system of
3. The system of
4. The system of
5. The system of
6. The system of
7. The system of
8. The system of
9. The system of
10. The system of
11. The system of
12. A method for low-latency content-sensitive forward error correction comprising:
packetizing data into a first packet in a first node selected from a group of nodes wherein said first node is coupled with a network;
packetizing data into a second packet in said first node;
time stamping said first packet in said first node;
time stamping said second packet in said first node;
generating a checksum packet based on said first packet and said second packet based on a packet type of said first packet and said second packet;
transmitting said first packet and said second packet and said checksum packet over said network;
providing software to a plurality of second nodes selected from said group of nodes wherein said plurality of second nodes are coupled with said network and wherein said plurality of second nodes are configured to forward error correct data sent from said first node wherein said software comprises the steps of:
filtering a first received packet and a second received packet into a packet queue and a checksum queue based on a packet type associated with said first received packet and a second packet type associated with said second received packet;
reconstructing a missing packet and placing said missing packet in correct time order in said packet queue; and,
outputting said first received packet, said second received packet and said missing packet in a corrected order with minimal latency.
13. The method of
14. The method of
15. The method of
16. The method of
17. The method of
18. The method of
19. A system for low-latency content-sensitive forward error correction comprising:
means for packetizing data into a first packet in a first node selected from a group of nodes wherein
said first node is coupled with a network;
means for packetizing data into a second packet in said first node;
means for time stamping said first packet in said first node;
means for time stamping said second packet in said first node;
means for generating a checksum packet based on said first packet and said second packet;
means for transmitting said first packet and said second packet and said checksum packet over said network;
means for providing software to a plurality of second nodes selected from said group of nodes wherein said plurality of second nodes are coupled with said network and wherein said plurality of second nodes are configured to forward error correct data sent from said first node wherein said software comprises the steps of:
means for filtering a first received packet and a second received packet into a packet queue and a checksum queue based on a packet type associated with said first received packet and a second packet type associated with said second received packet;
means for reconstructing a missing packet and placing said missing packet in correct time order in said packet queue; and,
means for outputting said first received packet, said second received packet and said missing packet in a corrected order with minimal latency.
20. The system of
This application takes priority from United States application to Fellman entitled “LOW-LATENCY CONTENT-SENSITIVE FORWARD ERROR CORRECTION” filed Aug. 9, 2004, Ser. No. 60/522,063 is hereby incorporated herein by reference. United States application to Fellman entitled “METHOD AND SYSTEM FOR PROVIDING SITE INDEPENDENT REAL-TIME VIDEO TRANSPORT OVER PACKET-SWITCHED NETWORKS” filed Jul. 7, 2004, Ser. No. 60/521,821 is hereby incorporated herein by reference. United States application to Fellman entitled “METHOD AND SYSTEM FOR PROVIDING SITE INDEPENDENT REAL-TIME MULTIMEDIA TRANSPORT OVER PACKET-SWITCHED NETWORKS” filed Jul. 7, 2005, Ser. No. 11/177,507 is hereby incorporated herein by reference. United States Provisional Patent Application to Fellman entitled “METHOD FOR CLOCK SYNCHRONIZATION OVER PACKET-SWITCHED NETWORKS” filed Jul. 19, 2004, Ser. No. 60/521,904 is hereby incorporated herein by reference. United States Provisional Patent Application to Fellman entitled “SYSTEM AND METHOD FOR CLOCK SYNCHRONIZATION OVER PACKET-SWITCHED NETWORKS” filed Jul. 19, 2005, Ser. No. 11/184,486 is hereby incorporated herein by reference.
1. Field of the Invention
Embodiments of this invention relate generally to the implementation of a packet recovery mechanism for the robust transport of live or real-time media streams over packet-switched networks. Such media streams may consist of an audio and a video component or any combination of audio and video or other time-sensitive signals. The packet-switched network may include Internet connections and IP networks in general. More specifically, such embodiments relate to forward error correction (FEC) mechanisms optimized for robust, low-latency, and bandwidth-efficient transport of audio and video streams over packet-switched networks.
2. Description of the Related Art
Random congestion through packet-switched networks, such as the Internet, adds an unpredictable amount of jitter and packet loss to the transport of video and audio packet streams. Furthermore the most efficient video compression, variable bit-rate (VBR) coding, produces large bursts of data that further add to network congestion, compounding potential router overflow and the resulting packet loss. Thus, the number of packets that a network might drop and the instantaneous packet rate may fluctuate greatly from one moment to the next.
In addition to contending with packet delivery problems, maintaining low latency is a critical constraint for video conferencing and other applications having interaction between the viewer and subject. Some examples of applications where low-latency is critical are: security, where an operator may desire to control the pan/tilt/zoom of a remote camera to follow suspicious activity; and telemedicine, to enable a doctor to remotely diagnose a patient.
Forward Error Correction (FEC) potentially provides a low-latency method for correcting packet loss. FEC adds a fixed percentage of additional packets, called checksum packets, to a block of data packets such that the loss of one or more data packets in the block, within some predetermined bound, can be recovered by combining the checksum packets with those data packets that had been successfully received in order to reconstruct the missing data packets.
Various forms of FEC have long been applied to digital audio-video streams, most notably for satellite transmission and most recently for Internet streaming, to help minimize the adverse impact of channel impairments on the audio-video signal. Advantages of FEC over other error correction mechanisms include scalability to large systems because of its inherent multicast compatibility, and the fact that latency and distance between source and destination does not have any intrinsic effect since FEC does not require feedback.
Forward Error Correction
Variable packet loss rates and variable video bit rates, coupled with the need to minimize latency, present challenges to the implementation of FEC techniques for protecting packetized media streams. FEC augments a media stream with redundant data, called checksum packets, to help restore stream integrity based upon anticipated levels of packet loss. FEC groups data packets into an FEC block. The checksum packets generated from a given block are said to cover that block since missing data packets can be restored by combining the remaining checksum and data packets in that block. FEC coverage, the number of missing data packets that FEC can recover within the same block, is limited to the number of checksum packets within that block.
One of the strengths of FEC is that it has the potential to immediately reconstruct lost data upon receipt of the appropriate checksum packets, without the need to wait for retransmissions from the source. Thus for networks with long round-trip travel times, FEC may significantly reduce latency as compared with feedback-based error correction, such as Automatic Repeat reQuest (ARQ).
However without knowledge of the actual packet loss at the receiver, a transmitter implementing FEC may not provide a sufficient number of checksum packets for packet recovery. Since FEC implementations generally transmit a fixed number of checksum packets, often calculated as a constant percentage of the number of data packets regardless of packet content, such FEC implementations would not be able to efficiently handle large instantaneous variations in packet loss rates. In such cases, either FEC bandwidth overhead would be excessive and inefficient, or else the FEC coverage would be inadequate for complete packet recovery.
Furthermore without knowledge of the instantaneous bit rate, FEC processing at a receiver may wait an indeterminate amount of time for of all checksum packets pertaining to a data block to arrive before recovering lost data from that data block. For example, if every 10 data packets generate one checksum packet to form an FEC block, and a network drops one data packet in delivering this block, then the receiver would have to wait for the arrival of the 10th packet, the checksum packet, before it could recover the missing data packet. However under VBR coding of the stream, the time required to receive these 10 packets can vary considerably. Waiting for the checksum packet to arrive delays the stream at the receiver and creates a burst of packets as the receiver accumulates each FEC block for FEC processing. Thus, the burstiness of FEC receiver processing adds jitter, and ultimately latency, to a recovered signal.
FEC also generates burstiness and jitter at a transmitter. As mentioned, standard FEC implementations generate checksum packets as a fixed percentage of the number of outgoing data packets. These implementations wait for all packets in a data block to have been generated before creating and sending the associated checksum packets for the block. As for VBR streams at the receiver, a fixed-percentage FEC checksum generator at the transmitter would also have to wait an indeterminate amount of time for enough data packets to accumulate and fill the FEC block before the checksum packet generator could complete checksum generation for that block.
This variation in FEC processing delay produces jitter in the recovered data stream that must be smoothed out by adding input packet buffering at the receiver. However, such input buffering to recover from VBR FEC-induced jitter adds to the overall stream latency. Thus as a further limitation of fixed-percentage FEC, large variations in stream packet rate as a result of VBR encoding result in long system latency.
Even when the bit rate is constant, as with Constant Bit Rate (CBR) coding, conventional FEC can introduce large amounts of jitter and latency to a real-time audio or video stream. A common FEC technique for protecting against large contiguous burst drops is interleaving. An example of interleaving is found in the Pro-MPEG Forum's Code of Practice #3 standard for FEC for video over IP networks (Ref. #1). One implementation of interleaving writes packets sequentially along rows of a two-dimensional matrix. When a data packet fills the last data row of the matrix, the FEC engine computes a final checksum row, generating one parity packet for each column to fill the checksum row, and then sends the entire checksum row as a burst of parity packets. (Parity packets are computed by calculating the Exclusive-OR across corresponding bits of all packets of a block.)
At a transmitter, interleaving delays the generation of checksum packets until the interleaving matrix has been filled, where it then creates a burst of checksum packets. The receiver inputs an incoming stream as blocks of data packets followed by this burst of checksum packets. At the receiver, interleaving introduces a processing delay equal to the time required to fill the entire receiver's matrix. The receiver waits for the last data and parity packet within a block to arrive before it applies the received parity packets to the received block of data packets to recover any missing packets. (If the last packet in a block was lost, then either a timeout, the appearance of a packet from a following block, or a combination of both may force FEC immediate processing for the current FEC block.) Thus, interleaving introduces processing jitter both at the transmitter and at the receiver as a result of the periodic processing time in waiting to fill the interleave matrix.
Video and Audio Stream Compression
The Motion Picture Experts Group (MPEG), a working group of the International Organization for Standardization (ISO), has defined a set of compression specifications for the efficient coding of audio and video digital streams. The generations of this video compression and encoding standard are known as MPEG-1, MPEG-2, and MPEG-4, with MPEG-4 being the latest member of this family of standards.
MPEG video compression encodes video as a sequence of two main types of frames: key interval snapshots, called I-Frames, and motion difference increments encoded in one of two ways, called B- or P-Frames, depending upon whether they encode motion differences using future and past frames (Bi-directional) or only past frames (Predictive). For efficient compression I-Frames typically occur infrequently, ranging from once every 500 milliseconds for professional broadcast applications to several seconds for Internet video conferencing applications, while a fixed pattern of B- and P-Frames (called Group of Pictures, or GOP) would fill the gap between I-Frames. This succession of I, B, and P video frames occurs at the video frame rate, typically having a constant 33.3 millisecond interval between frames. I-Frames are generally much larger than B- or P-Frames, often by orders of magnitude, as they have to encode all the detail of the basic compressed snapshot picture that the motion B- and P-Frames use as a base. For example, an I-Frame may typically consist of a dozen or more 1,500 byte Internet Protocol (IP) packets, while a typical B or P Frame often resides in a single packet or just a few packets.
The loss of a single packet of an I-Frame may invalidate an entire I-Frame, or at minimum result in severe macro blocking unless some form of error concealment is implemented. The invalidation of an entire I-Frame would be equivalent to the loss of all the packets comprising that I-Frame. Assuming that all packets have the same probability of being lost or corrupted during transport over a congested packet-switched medium, such as the Internet, the larger size of an I-Frame relative to B and P Frames makes I-Frames relatively more susceptible to loss or corruption. Conversely, since B- and P-Frames generally fit within a relatively few number of packets, the probability of losing a B- or P-Frame is substantially less. Even if the I-Frame were not completely invalidated, macro blocking may appear that could persist until the next I-Frame.
Furthermore, loss of a single I-Frame may disrupt a video stream for several seconds, until receipt of the next I-Frame. This occurs because the B- and P-Frames that follow an I-Frame must build upon that last I-Frame. In contrast, the loss of a single B-Frame may result in a disruption as low as a single frame period, about 33 milliseconds, since it may depend only on the P-Frames on either side of it. P-Frames only rely on the preceding I- or P-Frame. These facts further emphasize the importance of protecting I-Frames, relative to recovering lost B or P Frames.
Recent research in video forward error correction has validated the conclusion that I-Frames deserve the most FEC protection. A paper titled, “A Model for MPEG with Forward Error Correction and TCP Friendly Bandwidth,” published by the ACM in the NOSSDAV '03 Conference (Ref. #2), analyzed the effectiveness of varying the Group of Pictures (GOP) MPEG coding parameter and varying the number of FEC packets for each type of frame (I, P, & B) on the playable frame rate for the recovered video stream. They adopted an underlying constraint of an upper limit on throughput to make such video streams friendly to other network usage. Thus in their tests, increasing FEC overhead cut directly into bandwidth allotted for video, and therefore reduced the playable frame rate, just as lost packets would reduce the number of delivered frames and also lower playable frame rate at the receiver. Thus, they were able to compute an optimal level of FEC that maximized the playable received video frame rate under various packet loss levels.
After an exhaustive analysis of all reasonable combinations of GOP parameters and FEC overhead for the 3 frame types, they found that varying GOP had little effect on the playable frame rate. Not surprisingly, they also determined that FEC was most effective when I-Frames had the most FEC coverage, followed by the P-Frames. In their calculations of optimal FEC coverage for maximizing playable video frame rate, they provided no FEC coverage to B-Frames in simulations where the network packet loss rate was 5% and less, and only provided one FEC checksum packet for B-Frames at all higher network loss probabilities. In general, their FEC optimizations provided about half the FEC protection for P-Frames as provided for I-Frames.
Their analysis was not meant to provide, nor did it teach, an FEC implementation for general video streams, but rather to show that FEC can indeed improve the received playable video frame rate under the assumption of limited bandwidth. They only optimized FEC for a single high bit rate of video stream and allocated a fixed pattern of FEC coverage to that stream, based upon the ratio of I, P, and B-Frames of their high-bit-rate model stream. In fact, for video conferencing applications and other applications where a single packet may hold B or P Frames, their allocations would result in wasteful FEC allocations. For example, allocating one FEC packet for each B-Frame would result in 100% FEC overhead for B-Frames, even though, in their own analysis, the loss of B-Frames least affects the playable video rate.
Furthermore, their predetermination of FEC overhead would be extremely inefficient when using variable bit rate (VBR) video compression. As we previously mentioned, VBR produces the most efficient video compression, and is therefore the type of compression that all commercial DVDs use today. In VBR, the size of the various video frames changes significantly throughout the stream. Thus any pre-allocation of FEC for various compression frame types results in very inefficient and widely variable FEC coverage.
Neither this paper, nor any other work with which we are familiar discusses FEC techniques that limit the latency under VBR streams, where the receiver would have to wait for a variable number of packets before it can apply FEC checksum packets to restore a stream. This work also does not address the addition of audio packets to the stream.
Audio uses a completely different encoding mechanism from video. For both video conferencing and video streaming applications, audio is often encoded with a high degree of compression. For speech, compressed bit rates typically range from 8,000 or 11,025 bits per second. Furthermore, audio packetized for IP networks often contain 1,000 to 1,500 bytes of compressed audio signal. At a real-time streaming bit rate of 8,000 bps, the loss of a single audio packet represents a second or more of sound loss. MP3 compression of high-fidelity audio often produces audio streams as low as 56 Kbps. The loss of a single 1,500 byte MP3 audio packet would cause a playout gap of over 200 milliseconds. Thus, at these high compression rates and because of the relatively large amount of sound contained in each packet, even a single dropped audio packet can result in very pronounced audio disruptions at a receiver. Thus in addition to I-Frames, the loss of even a single audio packet could be noticeable, and therefore audio packets also require a high degree of protection.
Embodiments of the invention apply forward error correction methods to audio, video, and other real-time signal streams to enable their robust, low-latency transport over packet-switched networks. To minimize and bound latency and jitter added by FEC, embodiments of the invention may bound the size of an FEC data block to a fixed number of audio and video frames. Because frame rates for audio and video streams are constant, limiting the number of frames places a temporal constraint on FEC-induced jitter and latency. This allows embodiments of the invention to transport both constant bit rate streams (CBR) as well as variable bit rate (VBR) streams.
In some embodiments, the allocation of FEC checksum packets may vary with content to best insure the full playable audio and video frame rates despite network packet loss. Embodiments of the invention may therefore separate packets by content type and place each set of packets of a given content type into its own FEC block for independent FEC coverage.
Embodiments of the invention may use a Galois Field FEC to generate checksum packets. Using a Galois Field FEC allows any subset of K packets from a total FEC block of N packets having N-K checksum packets to recover all the data packets within that FEC block. Because Galois Field FEC protects any N-K data packets, it can also handle a consecutive burst of data packet loss, and may thereby eliminate the need for interleaving data packets within a block.
In one embodiment of the invention as shown in
A packet storage block 14 sorts packets by type and places each set of packets of a given content type into its own queue. In one embodiment as shown in
Embodiments of the invention may use Galois Field FEC to generate checksum packets as part of checksum packet generator 11. Using Galois Field FEC allows any subset of size K packets from a total FEC block of N packets having N-K checksum packets to recover all the data packets within that FEC block. Because Galois Field FEC protects any N-K data packets, it can also handle a consecutive burst of packet loss, and may thereby eliminate the need for interleaving data packets within a block. A paper titled, “Effective Erasure Codes for Reliable Computer Communications Protocols,” by Luigi Rizzo (Ref #4), provides computer code examples and explains in detail how to implement Galois Field forward error correction. For the details on implementation of Galois Field FEC for embodiments of the invention, we refer the reader to this work. However, we also note that another embodiment of the invention may instead use simple parity FEC—taking the parity across all corresponding bits of all packets within a block.
Packet grouping may vary among embodiments. Some content types may be combined in applications where separate and concentrated coverage of a particular content type is not a requirement. The determination of how to group packets of the same frames or content type would depend upon reliability versus efficiency tradeoffs. In one embodiment of the invention as shown in
In general, since degradation in received audio-video signal quality is most affected by losses in audio and I-Frame packets, many embodiments would more heavily weigh FEC protection on these packet types over other packet types. Also, because frame timing for audio is usually separate from video frame timing, embodiments of the invention as shown in
An upper bound on the number of frames each FEC block may hold limits the jitter and latency of FEC processing. A constraint on the number of checksum packets as a percentage of each packet type constrains the FEC overhead, yet different limits for different packet types allows a weighting on the FEC coverage based upon packet type and allows more sensitive content and packet types to be given more robust FEC coverage.
At a receiver, the embodiment of FEC processing and recovery block 3 a of
The actual FEC processing of FEC packet processor and recovery engine 305 performs separate FEC processing and recovery on each of the blocks of packets in queues 301 and 302, and queues 303 and 304. FEC processing of 305 should be compatible with the checksum packet generator 11 in transmitter 1. Thus if checksum generator 11 uses Galois Field FEC checksum packets, so should FEC processor 305. The output of FEC processing and recovery block 3 a is the recovered audio and video packet streams, with missing packets restored to the extent of the ability of the FEC processing 305, and FEC processing jitter removed by output gating from clock 33 on queue 301 and 304.
In the embodiment shown in
The second constraint that keeps I-Frames in the same block takes precedence over the 100-millisecond (third) constraint on latency, so I-Frame FEC blocks only cover a single video frame period. This provides maximum protection for I-Frames. FEC blocks that come after an I-Frame FEC block may contain a mixture of B and P frames up to the 100-millisecond limit. The 100-millisecond rule takes precedence over the overhead rule to allow larger blocks and therefore more robust FEC recovery. To honor the first two constraints on maintaining packet ordering and keeping I-Frames together in an FEC block may sometimes force the flushing of an FEC block and generation of that block's checksum packets before the latency or overhead constraints are met. Thus, the actual FEC checksum overhead may be slightly higher than the number specified as a constraint.
As shown in video queue 101 of
During the next frame time, from 33.3 milliseconds into the stream to time 66.7 milliseconds, the stream contains the two packets for the first B-Frame, B1 (second video frame), and the second audio frame, A1. Because we wish to limit the time span of an FEC block to 100 milliseconds or three frames of data per FEC block, and aggregate audio packets into their own FEC block, separate from FEC blocks containing video packets, we must wait until the third audio frame is sent, after 66.7 milliseconds, before sending out the first audio checksum packet, CA1, as part of the audio FEC block comprising audio packets A1 through A3. Thus at time 66.7 milliseconds through 100 milliseconds, the stream contains the second B-Frame (third video frame), the third audio frame packet, A3, and the first audio checksum packet, signaling the end of the first audio FEC block. Since less than 100 milliseconds have accumulated since transmission of the previous FEC block, the FEC block that includes the B1 and B2 frames is not yet ready, but waits for the next frame before generating checksum packets.
The first P-Frame (fourth video frame) occurs after 100 milliseconds and contains 4 packets, P1 1 through P1 4. At this point in time, video packet queue 101 in FEC generator 14 has accumulated 8 video packets. These three video frames, B1, B2, and P1, represent 100 milliseconds of video data, the time constraint dictates the closing of the current FEC block and the generation of 2 checksum packets, Cv3 and Cv4, for this block of 8 packets with FEC overhead of 25%.
Because audio packets comprise separate FEC blocks from video packet in this embodiment, the next audio FEC block and its corresponding checksum packet CA2 occur after transmission of the sixth audio packet, A6, after 166.7 milliseconds. By the time 200 milliseconds elapses, two new video frames, B3 and B4, comprising 4 packets, have been transmitted—an insufficient number of frames to complete another video FEC block.
After 200 milliseconds the second I-Frame (seventh video frame), I2 comprising 8 packets, enters video queue 101 in FEC generator 1 a. However, since this embodiment of the invention keeps I-Frames together as a single FEC block, the checksum generator 11 flushes the video FEC block comprising B3 and B4 to produce checksum packet Cv5 since to wait any longer would violate the constraints on maintaining packet order and keeping a maximum of 100-milliseconds of latency. Immediately after transmission of the eight packets of I2, checksum generator 11 creates the 2 FEC checksum packets, Cv6 and Cv7, for the I2 FEC block.
The above packet processing helps to preserve the quality of the received media stream, despite the possible introduction of significant network impairments, such as that which is likely to occur over an unconditioned best-effort packet network, such as the Internet. The application of FEC adds to the media stream's throughput requirement. However, because the latency constraint overrides the overhead constraint, the actual additional throughput overhead for FEC varies and may sometimes exceed the specified FEC overhead.
It should be understood that the programs, processes, methods, systems and apparatus described herein are not related or limited to any particular type of computer apparatus (hardware or software), unless indicated otherwise. Various types of general purpose or specialized computer apparatus may be used with or perform operations in accordance with the teachings described herein.
In view of the wide variety of embodiments to which the principles of the invention can be applied, it should be understood that the illustrated embodiments are exemplary only, and should not be taken as limiting the scope of embodiments of the invention. For example, the packet ordering and grouping of the media packet stream flow diagrams of
The claims should not be read as limited to the described order or elements unless stated to that effect. Therefore, all embodiments that come within the scope and spirit of the following claims and equivalents thereto are claimed as the invention.