RTP Payload Format for Reed Solomon FEC
draft-galanos-fecframe-rtp-reedsolomon-00

Status of this Memo

This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”

The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.

This Internet-Draft will expire on April 15, 2010.

Copyright Notice

Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Abstract

This document defines a new RTP payload format for the Forward Error Correction (FEC) that uses Reed-Solomon codes. The format defined by this document enables the protection of source media encapsulated in RTP with one or more repair flows and is based on the FEC framework (described in [I-D.ietf-fecframe-framework]) and the SDP Elements for FEC Framework (described in [I-D.ietf-fecframe-sdp-elements]). The Reed-Solomon codes used in this document belong to the class of Maximum Distance Separable (MDS) codes which means they offer optimal protection against random and bursty packet losses.

Table of Contents

1.  Introduction
2.  Requirements Notation
3.  Definitions, Notations and Abbreviations
    3.1.  Definitions
    3.2.  Notations
4.  Reed Solomon Codes
5.  Source Block Creation
6.  Packet Formats
    6.1.  Source Packets
    6.2.  Repair Packets
        6.2.1.  RTP header format
        6.2.2.  FEC header format
        6.2.3.  Repair Data Format
7.  Payload Format Parameters
    7.1.  Media Type Registration
        7.1.1.  Registration of audio/reed-solomon-fec
        7.1.2.  Registration of video/reed-solomon-fec
        7.1.3.  Registration of text/reed-solomon-fec
        7.1.4.  Registration of application/reed-solomon-fec
    7.2.  Mapping of SDP Parameters
8.  Protection and Recovery Procedures
    8.1.  Overview
    8.2.  Repair Packet Construction
    8.3.  Source Packet Reconstruction
        8.3.1.  Associating the Source and Repair Packets
        8.3.2.  Recovering the source packet
9.  SDP Examples
10.  Offer/Answer considerations
11.  Security Considerations
12.  IANA Considerations
13.  Acknowledgments
14.  References
    14.1.  Normative References
    14.2.  Informative References
§  Authors' Addresses

1.  Introduction

This document defines new RTP payload formats for the Forward Error Correction (FEC) that is generated by the Reed-Solomon code.

By nature, interactive Real-time applications are extremely sensitive to delay and require very low latency. As a result, retransmission of lost packets and using other closed-loop schemes are not valid options while the use of Forward Error Correction (FEC) is an effective approach.

A primary requirement from FEC for real time applications is the ability to correctly recover from both random and bursty packet losses. The Reed-Solomon FEC codes used in this document belong to the class of Maximum Distance Separable (MDS) codes that are optimal in terms of erasure recovery capability for both situations.

The format defined by this document enables the protection of media source flow with one or more repair flows without adding additional information to the source packets. Such behavior reduces the delay presented by any FEC scheme and maintains backwards compatibility with non FEC-enabled receivers.

Number of previous drafts were composed to draw different FEC schemes suitable for different applications. The scheme defined in this draft is designed to compensate a burst of packet loss over RTP networks with minimum delay, which is needed in interactive IP-based applications such as video conferencing.

The method described in this document is generic to all media types and provides the sender with the flexibility of deciding if FEC protection is required and if so, how many protecting packets and how many source packets to use in a block according to network conditions. Furthermore it allows applying unequal error protection that provides different level of protection to different packets. For example, it can be combined with Scalable Video Coding to protect only the base layer packets of the video flow. At the receiver, both the FEC and original media are received. If no media packets are lost, the FEC packets can be ignored. In the event of a loss, the FEC packets can be combined with other received media to recover all or part of the missing media packets.

The Read-Solomon codes used in this document have already been specified by Luigi Rizzo (see [Rizzo97]). The document is compliant with the Forward Error Correction (FEC) Framework (described in [I-D.ietf-fecframe-framework]) and SDP Elements for FEC Framework (described in [I-D.ietf-fecframe-sdp-elements]). This draft completes [I-D.roca-fecframe-rs] by defining Reed-Solomon usage for RTP transport.

2.  Requirements Notation

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).

3.  Definitions, Notations and Abbreviations

This document uses the following definitions and notations. For further definitions that apply to FEC Framework in general, see [I-D.ietf-fecframe-framework].

3.1.  Definitions

FEC: Forward Error Correction.

Source Flow: The packet flow to which FEC protection is to be applied.

Repair Flow: The packet flow carrying FEC data.

Source Block: The group of source data packets which are to be FEC protected as a single block.

Source Packets: Packets that are transmitted over a source flow

Repair/FEC Packets: Packets that are transmitted over a repair flow

FEC header: The header information contained in an FEC packet

3.2.  Notations

K: The number of packets in a source block

N-K: The number of repair FEC packets generated from a single source block

4.  Reed Solomon Codes

The detailed operation and theory behind Reed Solomon codes is out of the scope of this document. In general a Reed Solomon code takes a group of K source packets and generates N - K repair packets. A receiver needs to receive any K of the N source or repair packets in order to recover the remaining N-K packets. The algorithm operates over multiple symbols each taken from a single source packet. The symbol size can be different in different implementations. Any symbol size can be used in the format offered by this document. However, it is recommended for simplicity to use symbol size of 8 bits (byte). For more information on Reed Solomon codes, the reader is referred to [Rizzo97].

5.  Source Block Creation

This draft defines the protection of an RTP source flow using one or more FEC repair flows.

A source block for the Reed-Solomon code contains K data blocks. In the scheme presented by this document, each data block contains a single RTP packet and therefore a source block contains exactly K consecutive RTP packets. The Reed-Solomon code generates N-K repair blocks that are transmitted using N-K repair packets. Each repair packet contains a single repair block. Such behavior is most suitable for packet-switched networks where errors are on packet boundaries

To create a source block the steps outlined below should be followed.

1. For each packet protected in this source block create a byte array as follows:

   A.

   In the first two bytes place the unsigned network-ordered 16-bit representation of the RTP packet size in bytes (including RTP header size and payload size)

   B.

   Append the entire RTP packet including its RTP header

   C.

   Add padding (bytes containing binary zeroes) so that the byte array is the size of the largest packet protected by this source block including the two bytes from section A (the largest packet does not contain zero padding).

2. Append all the byte arrays one after the other in the following way:

   A.

   The packets are in an increasing order of the sequence number as it appears in the RTP packet header taking wraparound into account

   B.

   The sequence number of the source packets must be consecutive in a source block.

Figure 1 demonstrates how a source block is created from 4 packets (P1, P2, P3, P4) with different sizes. The largest packet protected in this source block has the size of 5 (L=5) and therefore P1 and P3 are both padded with zeros to this size. The source block contains the RTP packet size before each packet. (Note that this example is not a binary representation of the source block. The Packet size spans over two bytes as stated above)

         P1          P2            P3            P4
         L=3         L=5           L=4           L=5

         +---+       +-----+       +----+      +-----+
         |xxx|       |xxxxx|       |xxxx|      |xxxxx|
         +---+       +-----+       +----+      +-----+

                  |--- Source Block (K=4)-----|

                  +------+------+------+------+
                  |3xxx00|5xxxxx|4xxxx0|5xxxxx|
                  +------+------+------+------+

The FEC Reed-Solomon Scheme gets a source block created from K packets and generates N-K FEC repair packets that protect the entire source block. These packets are then transmitted in the repair flow. Note that source packets padding is done only for FEC packet calculation and the original payloads are transmitted without extra padding.

6.  Packet Formats

This section defines the formats of the source and repair packets

6.1.  Source Packets

The FEC Framework requires that source packets contain information identifying the source block and the position within the source block occupied by the packet. However, in order to maintain backwards compatibility, the scheme defined by this document enables the receiver to get this information without appending additional information to the source packet. Specifically this information is obtained using the combination of sequence number found in the RTP header and information provided in the FEC header of each repair packet. Such behavior enables both non-FEC-capable and FEC-capable receivers to receive and interpret the same source packets sent in a multicast session.

6.2.  Repair Packets

The FEC repair packets contain information that enables the receiver to reconstruct the source block in the remote end. This is done by using the RTP header of the repair packets as well as another header that is placed within the RTP payload. This header, referred to as the FEC header, complies with [FECFRAME-FRAMEWORK] (section 6.4.1), as shown in Figure 2.

             +------------------------------+
             |          IP Header           |
             +------------------------------+
             |       Transport Header       |
             +------------------------------+
             |          RTP Header          |
             +------------------------------+ --_
             |          FEC Header          |    \
             +------------------------------+     > RTP Payload
             |        Repair Data           |   _/
             +------------------------------+ --

6.2.1.  RTP header format

The RTP header is formatted according to [RFC3550] with some further clarifications listed below:

• Marker (M) Bit: This bit is not used for this payload type, and is set to 0.
• Payload Type: The (dynamic) payload type for the repair packets is determined through out-of-band means. Note that this document registers new payload formats for the repair packets (Refer to Section 5 for details). According to [RFC3550], an RTP receiver that cannot recognize a payload type must discard it. This provides for backward compatibility. The FEC mechanisms can then be used in a multicast group with mixed FEC-capable and non-FEC- capable receivers. If a non-FEC-capable receiver receives a repair packet, it will not recognize the payload type, and hence, will discard the repair packet.
• Sequence Number (SN): The sequence number maintains the standard definition. It is one higher than the sequence number in the previously transmitted repair packet. The initial value of the sequence number is random (unpredictable) [RFC3550].
• Timestamp (TS): The timestamp is set to a time corresponding to the repair packet's transmission time. Note that the timestamp value has no use in the actual FEC protection process and is usually useful for jitter calculations. FEC packets that are the result of the same FEC operation will use the same value as their Timestamp.
• Synchronization Source (SSRC): The SSRC value is randomly assigned as suggested by [RFC3550].

6.2.2.  FEC header format

The FEC header includes information that enables the receiver to reconstruct the source block and to identify the repair packets associated with each source block in their correct order.

The format of the FEC header is shown in figure 3.

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    N-K        |       i       |        SN Base                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   	   Num Packets          |	Reserved		|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The FEC header consists of the following general fields:

• N-K - The number of FEC packets used to protect this source block
• i - 0 based packet index in the N-K FEC packets sequence.
• SN Base - the lowest sequence number (taking wraparound into account) of the source packets protected by this repair packet.
• Num Packets - The number of consecutive source packets protected by this repair packet.
• Reserved - for future use.

6.2.3.  Repair Data Format

The repair data follows the FEC header in the RTP repair packet. It includes the result of the Reed-Solomon code over the source block. Note that the first two bytes of the repair data contain the result of the Reed-Solomon code over the packet sizes in the source block and that the size of the repair data equals the size of the largest packet protected by this source block plus 2. Therefore, the size of an FEC packet (FEC header and data) is larger than the longest source packet. This should be taken under consideration when deciding on the Maximum Transmission Unit size used for the source packets.

7.  Payload Format Parameters

According to the FEC framework, when RTP is used as a transport for repair packet flows, the scheme must define an RTP Payload Format for the repair data. This section provides the media subtype registration for the Reed-Solomon FEC. The parameters that are required to configure the FEC encoding and decoding operations are also defined in this section.

7.1.  Media Type Registration

This registration is done using the template defined in [RFC4288] and following the guidance provided in [RFC3555].

7.1.1.  Registration of audio/reed-solomon-fec

Type name: audio

Subtype name: reed-solomon-fec

Required parameters:

• max_N: The upper limit for the sum of source and repair packets that belong to the same FEC block. max_N is a positive integer. The application can change both K and N-K. max_N is the upper limit for N.
• repair-window: The time that spans the source packets and the corresponding repair packets. The size of the repair window is specified in microseconds.
• symbol-size: a non-negative integer indicating the length of each encoding symbol in bits.

Optional parameters: None.

Encoding considerations: This media type is framed and binary, see section 4.8 in [RFC4288]

Security considerations: Please see security consideration in [I-D.ietf-fecframe-framework]

Interoperability considerations: None.

Published specification: TBD

Applications that use this media type: Multimedia applications that want to improve resiliency against packet loss by sending redundant data in addition to the source media.

Additional information: None.

Magic number(s): none defined

File extension(s): none defined

Macintosh file type code(s): none defined

Person & email address to contact for further information: Sarit Galanos, sarit@radvision.com

Intended usage: COMMON

Restrictions on usage: This media type depends on RTP framing, and hence is only defined for transfer via RTP [RFC3550]. Transport within other framing protocols is not defined at this time.

7.1.2.  Registration of video/reed-solomon-fec

Type name: video

Subtype name: reed-solomon-fec

Required parameters:

• max_N: The maximum number summing of source and FEC packets. max_N is a positive integer. The application can change both K and N-K. max_N is the upper limit for N.
• repair-window: The time that spans the source packets and the corresponding repair packets. The size of the repair window is specified in microseconds.
• symbol-size: a non-negative integer indicating the length of each encoding symbol in bits.

Optional parameters: None.

Encoding considerations: This media type is framed and binary, see section 4.8 in [RFC4288]

Security considerations: Please see security consideration in [I-D.ietf-fecframe-framework]

Interoperability considerations: None.

Published specification: TBD

Applications that use this media type: Multimedia applications that want to improve resiliency against packet loss by sending redundant data in addition to the source media.

Additional information: None.

Magic number(s): none defined

File extension(s): none defined

Macintosh file type code(s): none defined

Person & email address to contact for further information: Sarit Galanos, sarit@radvision.com

Intended usage: COMMON

Restrictions on usage: This media type depends on RTP framing, and hence is only defined for transfer via RTP [RFC3550]. Transport within other framing protocols is not defined at this time.

7.1.3.  Registration of text/reed-solomon-fec

Type name: text

Subtype name: reed-solomon-fec

Required parameters:

• max_N: The maximum number summing of source and FEC packets. max_N is a positive integer. The application can change both K and N-K. max_N is the upper limit for N.
• repair-window: The time that spans the source packets and the corresponding repair packets. The size of the repair window is specified in microseconds.
• symbol-size: a non-negative integer indicating the length of each encoding symbol in bits.

Optional parameters: None.

Encoding considerations: This media type is framed and binary, see section 4.8 in [RFC4288]

Security considerations: Please see security consideration in [I-D.ietf-fecframe-framework]

Interoperability considerations: None.

Published specification: TBD

Applications that use this media type: Multimedia applications that want to improve resiliency against packet loss by sending redundant data in addition to the source media.

Additional information: None.

Magic number(s): none defined

File extension(s): none defined

Macintosh file type code(s): none defined

Person & email address to contact for further information: Sarit Galanos, sarit@radvision.com

Intended usage: COMMON

Restrictions on usage: This media type depends on RTP framing, and hence is only defined for transfer via RTP [RFC3550]. Transport within other framing protocols is not defined at this time.

7.1.4.  Registration of application/reed-solomon-fec

Type name: application

Subtype name: reed-solomon-fec

Required parameters:

• max_N: The maximum number summing of source and FEC packets. max_N is a positive integer. The application can change both K and N-K. max_N is the upper limit for N.
• repair-window: The time that spans the source packets and the corresponding repair packets. The size of the repair window is specified in microseconds.
• symbol-size: a non-negative integer indicating the length of each encoding symbol in bits.

Optional parameters: None.

Encoding considerations: This media type is framed and binary, see section 4.8 in [RFC4288]

Security considerations: Please see security consideration in [I-D.ietf-fecframe-framework]

Interoperability considerations: None.

Published specification: TBD

Applications that use this media type: Multimedia applications that want to improve resiliency against packet loss by sending redundant data in addition to the source media.

Additional information: None.

Magic number(s): none defined

File extension(s): none defined

Macintosh file type code(s): none defined

Person & email address to contact for further information: Sarit Galanos, sarit@radvision.com

Intended usage: COMMON

Restrictions on usage: This media type depends on RTP framing, and hence is only defined for transfer via RTP [RFC3550]. Transport within other framing protocols is not defined at this time.

7.2.  Mapping of SDP Parameters

For a proper operation details of the FEC scheme have to be communicated between the sender and the receiver. Specifically, the receiver has to know the relationship between the source and the repair flows, how the sender applied protection to the source flow and how the repair flows can be used to recover the lost data. One way to provide this information is to use the Session Description Protocol (SDP) [RFC4566].

The mapping of the media type specification for "reed-solomon-fec" and their parameters in SDP is as follows:

• The media type (e.g., "application") goes into the "m=" line as the media name.
• The media subtype ("reed-solomon-fec") goes into the "a=rtpmap" line as the encoding name.
• The remaining required payload-format-specific parameters ("max_N", "repair-window") go into the "a=fmtp" line by copying them directly from the media type string as a semicolon-separated list of parameter=value pairs.

See section 9 for SDP examples.

8.  Protection and Recovery Procedures

This section provides a complete specification of the protection and recovery procedures.

8.1.  Overview

The FEC packets allow end-systems to recover from a loss of media packets. The following sections specify the steps involved in generating the repair packets and reconstructing the missing source packets from the repair packets.

8.2.  Repair Packet Construction

The RTP header of a repair packet is formed based on the guidelines given in Section 6.2.1. The FEC header is formed based on the guidelines given in Section 6.2.2. The repair data is then appended to the FEC header. The repair data is the direct output of the protection operation calculated on the source block with Reed-Solomon code. Note that the repair data calculated over K source packets will span over N-K packets.

8.3.  Source Packet Reconstruction

Recovery requires two distinct operations. The first determines which packets (media and FEC) must be combined in order to recover the missing packets. Once this is done, the second step is the reconstruction of the missing data.

8.3.1.  Associating the Source and Repair Packets

Association of the Source and Repair packets is done using a combination of the Source packet sequence number and the information found in the RTP header and the FEC header of the repair packets. The first step is to accumulate the N-K repair packets that were generated in the protection operation. For that the application has to follow the steps listed below:

• For each received packet, retrieve the payload type parameter from the RTP header to identify the packet as a repair packet of the reed-solomon scheme.
• Once a repair packet has been identified, retrieve the sequence number from the RTP header and the N-K and i parameters from the FEC header.
• With these parameters, identify the collection of FEC packets generated for the source block. For example, if N-K=4, i=2 and the sequence number is 1003, it means that 4 packets with sequence numbers 1001,1002,1003 and 1004 were generated for a specific source block.

The next step is to use the SN Base and Num Packets parameters from the FEC header to identify the packets that constructed the source block.

8.3.2.  Recovering the source packet

In order to recover the lost packets the application has to rebuild the source block according to the guidelines given in section 5 and append the repair data to it in the correct order. Zero padding will replace the lost packets in the constructed source block. The size of each source block data packet in bytes will be equal to the size of the repair data found in the repair packets. The repair data size is the size of the RTP payload in the repair packet without the FEC header information (see figure 2). The application will then append the repair data taken from each repair packet. This new block is provided to the Reed-Solomon code.

Reconstruction of lost packets (source or repair packets) is possible only if at least any K packets were received (source or repair packets).

The Reed-Solomon code will reconstruct the lost data into the provided source block overriding the zero padded blocks. The application can then recover the lost packets as follows:

• The first two bytes specify the RTP packet size.
• According to the RTP packet size the application can retrieve the RTP packet (RTP header and payload).
• Any extra padding bytes if exist are ignored.

9.  SDP Examples

The following example demonstrates source flow with flow ID of 0 that is protected by a single repair flow R1.

v=0
o=sarit 1122334455 1122334466 IN IP4 fec.example.com
s= Reed Solomon FEC Example
t=0 0
a=group:FEC S1 R1
m=video 30000 RTP/AVP 100
c=IN IP4 224.1.1.1/127
a=rtpmap:100 MP2T/90000
a=fec-source-flow: id=0
a=mid:S1
m=application 30000 RTP/AVP 110
c=IN IP4 224.1.2.1/127
a=rtpmap:110 reed-solomon-fec /90000
a=fmtp:110 max_N:5; repair-window:200000; symbol-size:8
a=mid:R1

10.  Offer/Answer considerations

None.

11.  Security Considerations

See [I-D.ietf-fecframe-framework]

12.  IANA Considerations

New media subtypes are subject to IANA registration. For the registration of the payload formats and their parameters introduced in this document, refer to Section 7.

13.  Acknowledgments

Some parts of this document are borrowed from the following documents: [RFC5109], [draft-ietf-fecframe-1d2d-parity-scheme-01], [draft-roca-fecframe-rs-00], [draft-ietf-avt-reedsolomon-00]. The author would like to thank the editors of these documents. The authors would also like to thank the members of the FP7 3DPresence project consortium for their contribution to this draft writing.

14.  References

14.1. Normative References

14.2. Informative References

Authors' Addresses