[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 RFC 5445

Reliable Multicast Transport                                   M. Watson
Internet-Draft                                          Digital Fountain
Intended status: Standards Track                       February 22, 2007
Expires: August 26, 2007


              Basic Forward Error Correction (FEC) Schemes
             draft-ietf-rmt-bb-fec-basic-schemes-revised-03

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of 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 August 26, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).














Watson                   Expires August 26, 2007                [Page 1]

Internet-Draft              Basic FEC Schemes              February 2007


Abstract

   This document provides FEC Scheme specifications according to the RMT
   FEC Building Block for the Compact No-Code FEC Scheme, the Small
   Block, Large Block and Expandable FEC Scheme, the Small Block
   Systematic FEC Scheme and the Compact FEC Scheme.













































Watson                   Expires August 26, 2007                [Page 2]

Internet-Draft              Basic FEC Schemes              February 2007


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Requirements notation  . . . . . . . . . . . . . . . . . . . .  5
   3.  Compact No-Code FEC Scheme . . . . . . . . . . . . . . . . . .  6
     3.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . .  6
     3.2.  Formats and Codes  . . . . . . . . . . . . . . . . . . . .  6
       3.2.1.  FEC Payload ID(s)  . . . . . . . . . . . . . . . . . .  6
       3.2.2.  FEC Object Transmission Information  . . . . . . . . .  7
     3.3.  Procedures . . . . . . . . . . . . . . . . . . . . . . . .  8
     3.4.  FEC code specification . . . . . . . . . . . . . . . . . .  9
       3.4.1.  Source Block Logistics . . . . . . . . . . . . . . . .  9
       3.4.2.  Sending and Receiving a Source Block . . . . . . . . . 10
   4.  Small Block, Large Block and Expandable FEC Scheme . . . . . . 12
     4.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . 12
     4.2.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . 12
       4.2.1.  FEC Payload ID(s)  . . . . . . . . . . . . . . . . . . 12
       4.2.2.  FEC Object Transmission Information  . . . . . . . . . 12
     4.3.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . 13
     4.4.  FEC Code Specification . . . . . . . . . . . . . . . . . . 14
   5.  Small Block Systematic FEC Scheme  . . . . . . . . . . . . . . 15
     5.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . 15
     5.2.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . 15
       5.2.1.  FEC Payload ID(s)  . . . . . . . . . . . . . . . . . . 15
       5.2.2.  FEC Object Transmission Information  . . . . . . . . . 16
     5.3.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . 17
     5.4.  FEC Code Specification . . . . . . . . . . . . . . . . . . 17
   6.  Compact FEC Scheme . . . . . . . . . . . . . . . . . . . . . . 18
     6.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . 18
     6.2.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . 18
       6.2.1.  FEC Payload ID(s)  . . . . . . . . . . . . . . . . . . 18
       6.2.2.  FEC Object Transmission Information  . . . . . . . . . 18
     6.3.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . 18
     6.4.  FEC code specification . . . . . . . . . . . . . . . . . . 18
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 19
   8.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 20
   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 21
   10. Changes from schemes defined in RFC3452 and RFC3695  . . . . . 22
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 23
     11.2. Informative References . . . . . . . . . . . . . . . . . . 23
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 24
   Intellectual Property and Copyright Statements . . . . . . . . . . 25








Watson                   Expires August 26, 2007                [Page 3]

Internet-Draft              Basic FEC Schemes              February 2007


1.  Introduction

   The document specifies the following FEC Schemes according to the
   specification requirements of the FEC Building Block [2]:

   o  Compact No-Code FEC Scheme

   o  Small Block, Large Block and Expandable FEC Scheme

   o  Small Block Systematic FEC Scheme

   o  Compact FEC Scheme

   This document inherits the context, language, declarations and
   restrictions of the FEC building block [2].  This document also uses
   the terminology of the companion document [4] which describes the use
   of FEC codes within the context of reliable IP multicast transport
   and provides an introduction to some commonly used FEC codes.

   Building blocks are defined in RFC 3048 [9].  This document is a
   product of the IETF RMT WG and follows the general guidelines
   provided in RFC 3269 [5].

   RFC3452 [3] and RFC3695 [10] contained a previous versions of the FEC
   Schemes defined in this specification.  These RFCs were published in
   the "Experimental" category.  It was the stated intent of the RMT
   working group to re-submit these specifications as an IETF Proposed
   Standard in due course.

   This Proposed Standard specification is thus based on and backwards
   compatible with the FEC Schemes defined in RFC3452 [3] and RFC3695
   [10] updated according to accumulated experience and growing protocol
   maturity since their original publication.  Said experience applies
   both to this specification itself and to congestion control
   strategies related to the use of this specification.

   The differences between the FEC Scheme specifications in RFC3452 [3]
   and RFC3695 [10] and this document listed in Section 10













Watson                   Expires August 26, 2007                [Page 4]

Internet-Draft              Basic FEC Schemes              February 2007


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 [1].














































Watson                   Expires August 26, 2007                [Page 5]

Internet-Draft              Basic FEC Schemes              February 2007


3.  Compact No-Code FEC Scheme

3.1.  Introduction

   The Compact No-code FEC Scheme is a Fully-Specified FEC Scheme.  The
   scheme requires no FEC coding and is specified primarily to allow
   simple interoperability testing between different implementations of
   protocol instantiations that use the FEC building block.

3.2.  Formats and Codes

3.2.1.  FEC Payload ID(s)

   The FEC Payload ID for the Compact No-Code FEC Scheme is composed of
   a Source Block Number and an Encoding Symbol ID as shown in Figure 1.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Source Block Number       |      Encoding Symbol ID       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Figure 1: FEC Payload ID format for Compact No-Code FEC Scheme

   The 16-bit Source Block Number is used to identify from which source
   block of the object the encoding symbol in the payload of the packet
   is generated.  There are two possible modes: In the unique SBN mode
   each source block within the object has a unique Source Block Number
   associated with it, and in the non-unique SBN mode the same Source
   Block Number may be used for more than one source block within the
   object.  Which mode is being used for an object is outside the scope
   of this document and MUST be communicated, either explicitly or
   implicitly, out-of-band to receivers.

   If the unique SBN mode is used then successive Source Block Numbers
   are associated with consecutive source blocks of the object starting
   with Source Block Number 0 for the first source block of the object.
   In this case, there are at most 2^^16 source blocks in the object.

   If the non-unique SBN mode is used then the mapping from source
   blocks to Source Block Numbers MUST be communicated out-of-band to
   receivers, and how this is done is outside the scope of this
   document.  This mapping could be implicit, for example determined by
   the transmission order of the source blocks.  In non-unique SBN mode,
   packets for two different source blocks mapped to the same Source
   Block Number SHOULD NOT be sent within an interval of time that is
   shorter than the transport time of a source block.  The transport
   time of a source block includes the amount of time the source block



Watson                   Expires August 26, 2007                [Page 6]

Internet-Draft              Basic FEC Schemes              February 2007


   is processed at the transport layer by the sender, the network
   transit time for packets, and the amount of time the source block is
   processed at the transport layer by a receiver.  This allows the
   receiver to clearly decide which packets belong to which source
   block.

   The 16-bit Encoding Symbol ID identifies which specific encoding
   symbol generated from the source block is carried in the packet
   payload.  The exact details of the correspondence between Encoding
   Symbol IDs and the encoding symbols in the packet payload are
   specified in Section 3.4.

3.2.2.  FEC Object Transmission Information

3.2.2.1.  Mandatory

   The mandatory FEC Object Transmission Information element for the
   Compact No-Code FEC Scheme is:

   o  FEC Encoding ID: zero (0)

3.2.2.2.  Common

   The common FEC Object Transmission Information elements and their
   value ranges for the Compact No-code FEC Scheme are:

   Transfer-Length:  a non-negative integer less than 2^^48.

   Encoding-Symbol-Length:  a non-negative integer less than 2^^16.

   Maximum-Source-Block-Length:  a non-negative integer less than 2^^32.

   Note that the semantics for the above elements are defined in [2] and
   are not duplicated here.

   The encoded Common FEC Object Transmission information is defined in
   Figure 2.














Watson                   Expires August 26, 2007                [Page 7]

Internet-Draft              Basic FEC Schemes              February 2007


       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Transfer Length                          |
      +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                               |           Reserved            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Encoding Symbol Length     | Max. Source Block Length (MSB)|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Max. Source Block Length (LSB)|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Figure 2: Encoded Common FEC OTI for Compact No-Code FEC Scheme

   All Encoding Symbols of a transport object MUST have length equal to
   the length specified in the Encoding Symbol Length element, with the
   optional exception of the last source symbol of the last source block
   (so that redundant padding is not mandatory in this last symbol).
   This last source symbol MUST be logically padded out with zeroes when
   another Encoding Symbol is computed based on this source symbol to
   ensure the same interpretation of this Encoding Symbol value by the
   sender and receiver.  However, this padding does not actually need to
   be sent with the data of the last source symbol.

   The "Reserved" field in the Encoded FEC Object Transmission
   Information SHOULD be set to zero by senders and its value SHOULD be
   ignored by receivers.

      Note: this FEC Scheme was first defined in [10] which did not
      require that the Encoding Symbol Length should be the same for
      every source block.  This document introduces a general
      requirement that the Encoding Symbol Length be the same across
      source blocks.  Since no protocols were defined which support
      variation in the Encoding Symbol Length between source blocks this
      can be done without introducing backwards compatibility issues.

3.2.2.3.  Scheme-Specific

   No Scheme-Specific FEC Object Transmission Information elements are
   defined by this FEC Scheme.

3.3.  Procedures

   The algorithm defined in Section 9.1. of [2] MUST be used to
   partition the file into source blocks.






Watson                   Expires August 26, 2007                [Page 8]

Internet-Draft              Basic FEC Schemes              February 2007


3.4.  FEC code specification

   The Compact No-Code FEC scheme does not require FEC encoding or
   decoding.  Instead, each encoding symbol consists of consecutive
   bytes of a source block of the object.

   The following two subsections describe the details of how the Compact
   No-Code FEC scheme operates for each source block of an object.

3.4.1.  Source Block Logistics

   Let X > 0 be the length of a source block in bytes.  Let L > 0 be the
   length of the encoding symbol contained in the payload of each
   packet.  The value of X and L are part of the FEC Object Transmission
   Information, and how this information is communicated to a receiver
   is outside the scope of this document.

   For a given source block X bytes in length with Source Block Number
   I, let N = X/L rounded up to the nearest integer.  The encoding
   symbol carried in the payload of a packet consists of a consecutive
   portion of the source block.  The source block is logically
   partitioned into N encoding symbols, each L bytes in length, and the
   corresponding Encoding Symbol IDs range from 0 through N-1 starting
   at the beginning of the source block and proceeding to the end.
   Thus, the encoding symbol with Encoding Symbol ID Y consists of bytes
   L*Y through L*(Y+1)-1 of the source block, where the bytes of the
   source block are numbered from 0 through X-1.  If X/L is not integral
   then the last encoding symbol with Encoding Symbol ID = N-1 consists
   of bytes L*(N-1) through the last byte X-1 of the source block, and
   the remaining L*N - X bytes of the encoding symbol can by padded out
   with zeroes.

   As an example, suppose that the source block length X = 20,400 and
   encoding symbol length L = 1,000.  The encoding symbol with Encoding
   Symbol ID = 10 contains bytes 10,000 through 10,999 of the source
   block, and the encoding symbol with Encoding Symbol ID = 20 contains
   bytes 20,000 through the last byte 20,399 of the source block and the
   remaining 600 bytes of the encoding symbol can be padded with zeroes.

   There are no restrictions beyond the rules stated above on how a
   sender generates encoding symbols to send from a source block.
   However, it is recommended that an implementor of refer to the
   companion document [3] for general advice.

   In the next subsection a procedure is recommended for sending and
   receiving source blocks.





Watson                   Expires August 26, 2007                [Page 9]

Internet-Draft              Basic FEC Schemes              February 2007


3.4.2.  Sending and Receiving a Source Block

   The following carousel procedure is RECOMMENDED for a sender to
   generate packets containing FEC Payload IDs and corresponding
   encoding symbols for a source block with Source Block Number I. Set
   the length in bytes of an encoding symbol to a fixed value L which is
   reasonable for a packet payload (e.g., ensure that the total packet
   size does not exceed the MTU) and that is smaller than the source
   block length X, e.g., L = 1,000 for X >= 1,000.  Initialize Y to a
   value randomly chosen in the interval [0..N-1].  Repeat the following
   for each packet of the source block to be sent.

   o  If Y <= N-1 then generate the encoding symbol Y.

   o  Within the FEC Payload ID, set the Source Block Length to X, set
      the Source Block Number = I, set the Encoding Symbol ID = Y, place
      the FEC Payload ID and the encoding symbol into the packet to
      send.

   o  In preparation for the generation of the next packet: if Y < N-1
      then increment Y by one else if Y = N-1 then reset Y to zero.

   The following procedure is RECOMMENDED for a receiver to recover the
   source block based on receiving packets for the source block from a
   sender that is using the carousel procedure described above.  The
   receiver can determine from which source block a received packet was
   generated by the Source Block Number carried in the FEC Payload ID.
   Upon receipt of the first FEC Payload ID for a source block, the
   receiver uses the source block length received out-of-band as part of
   the FEC Object Transmission Information to determine the length X in
   bytes of the source block, and allocates space for the X bytes that
   the source block requires.  The receiver also computes the length L
   of the encoding symbol in the payload of the packet by substracting
   the packet header length from the total length of the received packet
   (and the receiver checks that this length is the same in each
   subsequent received packet from the same source block).  After
   calculating N = X/L rounded up to the nearest integer, the receiver
   allocates a boolean array RECEIVED[0..N-1] with all N entries
   initialized to false to track received encoding symbols.  The
   receiver keeps receiving packets for the source block as long as
   there is at least one entry in RECEIVED still set to false or until
   the application decides to give up on this source block and move on
   to other source blocks.  For each received packet for the source
   block (including the first packet) the steps to be taken to help
   recover the source block are as follows.  Let Y be the value of the
   Encoding Symbol ID within FEC Payload ID of the packet.  If Y <= N-1
   then the receiver copies the encoding symbol into the appropriate
   place within the space reserved for the source block and sets



Watson                   Expires August 26, 2007               [Page 10]

Internet-Draft              Basic FEC Schemes              February 2007


   RECEIVED[Y] = true.  If all N entries of RECEIVED are true then the
   receiver has recovered the entire source block.

















































Watson                   Expires August 26, 2007               [Page 11]

Internet-Draft              Basic FEC Schemes              February 2007


4.  Small Block, Large Block and Expandable FEC Scheme

4.1.  Introduction

   This section defines an Under-Specified FEC Scheme for Small Block
   FEC codes, Large Block FEC codes and Expandable FEC codes as
   described in [4].

4.2.  Formats and Codes

4.2.1.  FEC Payload ID(s)

   The FEC Payload ID is composed of a Source Block Number and an
   Encoding Symbol ID structured as 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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     Source Block Number                       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                      Encoding Symbol ID                       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     Figure 3: FEC Payload ID format for Small Block, Large Block and
                           Expandable FEC Codes

   The Source Block Number identifies from which source block of the
   object the encoding symbol(s) in the payload are generated.  These
   blocks are numbered consecutively from 0 to N-1, where N is the
   number of source blocks in the object.

   The Encoding Symbol ID identifies which specific encoding symbol(s)
   generated from the source block are carried in the packet payload.
   The exact details of the correspondence between Encoding Symbol IDs
   and the encoding symbol(s) in the packet payload are dependent on the
   particular FEC Scheme instance used as identified by the FEC Encoding
   ID and by the FEC Instance ID, and these details may be proprietary.

4.2.2.  FEC Object Transmission Information

4.2.2.1.  Mandatory

   The mandatory FEC Object Transmission Information element for the
   Small Block, Large Block and Expandable FEC Scheme are:

   o  FEC Encoding ID: 128





Watson                   Expires August 26, 2007               [Page 12]

Internet-Draft              Basic FEC Schemes              February 2007


4.2.2.2.  Common

   The common FEC Object Transmission Information elements and their
   value ranges for the Small Block, Large Block and Expandable FEC
   Scheme are:

   FEC Instance ID:  a non-negative integer less than 2^^16.

   Transfer-Length:  a non-negative integer less than 2^^48.

   Encoding-Symbol-Length:  a non-negative integer less than 2^^16.

   Maximum-Source-Block-Length:  a non-negative integer less than 2^^32.

   Note that the semantics for the above elements are defined in [2] and
   are not duplicated here.

   The encoded Common FEC Object Transmission information is defined in
   Section 4.2.2.2.

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Transfer Length                          |
      +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                               |         FEC Instance ID       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Encoding Symbol Length     | Max. Source Block Length (MSB)|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Max. Source Block Length (LSB)|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     Figure 4: Encoded Common FEC OTI for Small Block, Large Block and
                           Expandable FEC Scheme

4.2.2.3.  Scheme-Specific

   No Scheme-Specific FEC Object Transmission Information elements are
   defined by this FEC Scheme.

4.3.  Procedures

   The algorithm defined in Section 9.1. of [2] MUST be used to
   partition the file into source blocks.







Watson                   Expires August 26, 2007               [Page 13]

Internet-Draft              Basic FEC Schemes              February 2007


4.4.  FEC Code Specification

   The FEC code specification and the correspondance of Encoding Symbols
   IDs to encoding symbols are defined by specific instances of this
   scheme and so are out of scope of this document.














































Watson                   Expires August 26, 2007               [Page 14]

Internet-Draft              Basic FEC Schemes              February 2007


5.  Small Block Systematic FEC Scheme

5.1.  Introduction

   This section defines an Under-Specified FEC Scheme for Small Block
   Systematic FEC codes as described in [4].  For Small Block Systematic
   FEC codes, each source block is of length at most 65536 source
   symbols.

   Although these codes can generally be accommodated by the FEC
   Encoding ID described in Section 4, a specific FEC Encoding ID is
   defined for Small Block Systematic FEC codes to allow more
   flexibility and to retain header compactness.  The small source block
   length and small expansion factor that often characterize systematic
   codes may require the data source to frequently change the source
   block length.  To allow the dynamic variation of the source block
   length and to communicate it to the receivers with low overhead, the
   block length is included in the FEC Payload ID.

5.2.  Formats and Codes

5.2.1.  FEC Payload ID(s)

   The FEC Payload ID is composed of the Source Block Number, Source
   Block Length and the Encoding Symbol ID structured as shown in
   Figure 5.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     Source Block Number                       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      Source Block Length      |       Encoding Symbol ID      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 5: FEC Payload ID format for Small Block Systematic FEC scheme

   The Source Block Number identifies from which source block of the
   object the encoding symbol(s) in the payload are generated.  These
   blocks are numbered consecutively from 0 to N-1, where N is the
   number of source blocks in the object.

   The Source Block Length is the length in units of source symbols of
   the source block identified by the Source Block Number.

   The Encoding Symbol ID identifies which specific encoding symbol(s)
   generated from the source block are carried in the packet payload.
   Each encoding symbol is either an original source symbol or a



Watson                   Expires August 26, 2007               [Page 15]

Internet-Draft              Basic FEC Schemes              February 2007


   redundant symbol generated by the encoder.  The exact details of the
   correspondence between Encoding Symbol IDs and the encoding symbol(s)
   in the packet payload are dependent on the particular FEC scheme
   instance used as identified by the FEC Instance ID, and these details
   may be proprietary.

5.2.2.  FEC Object Transmission Information

5.2.2.1.  Mandatory

   The mandatory FEC Object Transmission Information element for the
   Small Block Systematic FEC Scheme is:

   o  FEC Encoding ID: 129

5.2.2.2.  Common

   The common FEC Object Transmission Information elements and their
   value ranges for the Small Block Systematic FEC Scheme are:

   FEC Instance ID:  a non-negative integer less than 2^^16.

   Transfer-Length:  a non-negative integer less than 2^^48.

   Encoding-Symbol-Length:  a non-negative integer less than 2^^16.

   Maximum-Source-Block-Length:  a non-negative integer less than 2^^16.

   Max-Number-of-Encoding-Symbols:  a non-negative integer less than
      2^^16

   Note that the semantics for the above elements are defined in [2] and
   are not duplicated here.

   The encoded Common FEC Object Transmission information is defined in
   Figure 6.















Watson                   Expires August 26, 2007               [Page 16]

Internet-Draft              Basic FEC Schemes              February 2007


       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Transfer Length                          |
      +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                               |         FEC Instance ID       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Encoding Symbol Length     |  Maximum Source Block Length  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Max. Num. of Encoding Symbols |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Figure 6: FEC OTI format for Small Block Systematic FEC Scheme

   All Encoding Symbols of a transport object MUST have length equal to
   the length specified in the Encoding Symbol Length field, with the
   optional exception of the last source symbol of the last source block
   (so that redundant padding is not mandatory in this last symbol).
   This last source symbol MUST be logically padded out with zeroes when
   another Encoding Symbol is computed based on this source symbol to
   ensure the same interpretation of this Encoding Symbol value by the
   sender and receiver.  However, this padding need not be actually sent
   with the data of the last source symbol.

      Note: this FEC Scheme was first defined in [3] which did not
      require that the Encoding Symbol Length should be the same for
      every source block.  However, no protocols have been defined which
      support variation in the Encoding Symbol Length between source
      blocks and thus introduction of a general requirement that the
      Encoding Symbol Length be the same across source blocks (as
      defined here) should not cause backwards compatibility issues and
      will aid interoperability.

5.2.2.3.  Scheme-Specific

   No Scheme-Specific FEC Object Transmission Information elements are
   defined by this FEC Scheme.

5.3.  Procedures

   The algorithm defined in Section 9.1. of [2] MAY be used to partition
   the file into source blocks.

5.4.  FEC Code Specification

   The FEC code specification and the correspondance of Encoding Symbols
   IDs to encoding symbols are defined by specific instances of this
   scheme and so are out of scope of this document.



Watson                   Expires August 26, 2007               [Page 17]

Internet-Draft              Basic FEC Schemes              February 2007


6.  Compact FEC Scheme

6.1.  Introduction

   The Compact FEC Scheme is an Under-Specified FEC scheme.  This FEC
   scheme is similar in spirit to the Compact No-Code FEC scheme, except
   that a non-trivial FEC encoding (that is Under-Specified) may be used
   to generate encoding symbol(s) placed in the payload of each packet
   and a corresponding FEC decoder may be used to produce the source
   block from received packets.

6.2.  Formats and Codes

6.2.1.  FEC Payload ID(s)

   The FEC Payload ID format defined in Section 3.2.1 SHALL be used.

6.2.2.  FEC Object Transmission Information

6.2.2.1.  Mandatory

   The mandatory FEC Object Transmission Information element for the
   Compact No-Code FEC Scheme is:

   o  FEC Encoding ID: 130

6.2.2.2.  Common

   The common FEC Object Transmission Information elements and their
   encoding are the same as defined for the Small Block, Large Block and
   Expandable FEC Scheme in Figure 4.

6.2.2.3.  Scheme-Specific

   No Scheme-Specific FEC Object Transmission Information elements are
   defined by this FEC Scheme.

6.3.  Procedures

   The algorithm defined in Section 9.1. of [2] MUST be used to
   partition the file into source blocks.

6.4.  FEC code specification

   The FEC code specification and the correspondance of Encoding Symbols
   IDs to encoding symbols are defined by specific instances of this
   scheme and so are out of scope of this document.




Watson                   Expires August 26, 2007               [Page 18]

Internet-Draft              Basic FEC Schemes              February 2007


7.  Security Considerations

   This specification does not introduce any further security
   considerations beyond those described in [2].















































Watson                   Expires August 26, 2007               [Page 19]

Internet-Draft              Basic FEC Schemes              February 2007


8.  Acknowledgments

   This document is substantially based on [10] by Michael Luby and
   Lorenzo Vicisano and [3] by Michael Luby, Lorenzo Vicisano, Jim
   Gemmell, Luigi Rizzo, Mark Handley and Jon Crowcroft.














































Watson                   Expires August 26, 2007               [Page 20]

Internet-Draft              Basic FEC Schemes              February 2007


9.  IANA Considerations

   FEC Encoding IDs 0 and 130 were first defined and registered in the
   ietf:rmt:fec:encoding namespace by [10].  This document updates and
   obsoletes the definitions from that specification.

   FEC Encoding IDs 128 and 129 were first defined and registered in the
   ietf:rmt:fec:encoding namespace by [3].  This document updates and
   obsoletes the definitions from that specification.










































Watson                   Expires August 26, 2007               [Page 21]

Internet-Draft              Basic FEC Schemes              February 2007


10.  Changes from schemes defined in RFC3452 and RFC3695

   This section describes the changes between the Exprimental versions
   of these FEC Scheme specifictions contained in RFC3452 [3] and
   RFC3695 [10] and those defined in this specification:

   o  Scheme definitions have been updated to meet the requirements of
      [2].

   o  Complete encoding formats for the FEC Object Trasmission
      Information for each scheme are defined here, instead of within
      content delivery protocol specifications, since th exact format
      depends on the FEC Scheme.

   o  The previous specifications for the Compact No-Code and Small
      Block Systematic FEC Schemes sis not require that all encoding
      symbols of the object should have the same length.  This
      requirement is introduced in this specification.  Since no
      protocols have been defined which support variation of the
      encoding symbol length within an object this should not cause
      backwards compatibility issues.






























Watson                   Expires August 26, 2007               [Page 22]

Internet-Draft              Basic FEC Schemes              February 2007


11.  References

11.1.  Normative References

   [1]   Bradner, S., "Key words for use in RFCs to Indicate Requirement
         Levels", BCP 14, RFC 2119, March 1997.

   [2]   Watson, M., "Forward Error Correction (FEC) Building Block",
         draft-ietf-rmt-fec-bb-revised-04 (work in progress),
         September 2006.

11.2.  Informative References

   [3]   Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M.,
         and J. Crowcroft, "Forward Error Correction (FEC) Building
         Block", RFC 3452, December 2002.

   [4]   Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M.,
         and J. Crowcroft, "The Use of Forward Error Correction (FEC) in
         Reliable Multicast", RFC 3453, December 2002.

   [5]   Kermode, R. and L. Vicisano, "Author Guidelines for Reliable
         Multicast Transport (RMT) Building Blocks and Protocol
         Instantiation documents", RFC 3269, April 2002.

   [6]   Mankin, A., Romanov, A., Bradner, S., and V. Paxson, "IETF
         Criteria for Evaluating Reliable Multicast Transport and
         Application Protocols", RFC 2357, June 1998.

   [7]   Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
         April 1992.

   [8]   Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA
         Considerations Section in RFCs", BCP 26, RFC 2434,
         October 1998.

   [9]   Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S.,
         and M. Luby, "Reliable Multicast Transport Building Blocks for
         One-to-Many Bulk-Data Transfer", RFC 3048, January 2001.

   [10]  Luby, M. and L. Vicisano, "Compact Forward Error Correction
         (FEC) Schemes", RFC 3695, February 2004.









Watson                   Expires August 26, 2007               [Page 23]

Internet-Draft              Basic FEC Schemes              February 2007


Author's Address

   Mark Watson
   Digital Fountain
   39141 Civic Center Drive
   Suite 300
   Fremont, CA  94538
   U.S.A.

   Email: mark@digitalfountain.com









































Watson                   Expires August 26, 2007               [Page 24]

Internet-Draft              Basic FEC Schemes              February 2007


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Watson                   Expires August 26, 2007               [Page 25]


Html markup produced by rfcmarkup 1.108, available from http://tools.ietf.org/tools/rfcmarkup/