Internet Engineering Task Force                                 RMT WG
INTERNET-DRAFT                                  M.Luby/Digital Fountain
draft-ietf-rmt-bb-fec-03.txt
draft-ietf-rmt-bb-fec-04.txt                            L.Vicisano/Cisco
                                                     J.Gemmell/Microsoft
                                            L.Rizzo/ACIRI and Univ. Pisa
                                                         M.Handley/ACIRI
                                                        J. Crowcroft/UCL
							    19 July
                                                         18 October 2001
                                                     Expires: January April 2002

                 RMT BB Forward Error Correction Codes

This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.

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 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 a "work in progress".

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

To view the list Internet-Draft Shadow Directories, see
http://www.ietf.org/shadow.html.

This document is a product of the IETF RMT WG.  Comments should be
addressed to the authors, or the WG's mailing list at rmt@isi.edu.

                                Abstract

     This memo describes the abstract packet formats and IANA
     registration procedures for use of Forward Error Correction
     (FEC) codes within the context of reliable IP multicast
     transport. This memo should be read in conjunction with and
     uses the terminology of the companion memo [1], which
     describes the use of Forward Error Correction (FEC) codes
     within the context of reliable IP multicast transport and

^L
     provides an introduction to some commonly used FEC codes.

1.  FEC Abstract Packet Fields and Out-of-Band Information

This section specifies the describes FEC information that protocol packets must carry
to implement the various forms of FEC-based reliability.  A session is
defined either to be all the sent out-of-
band or in packets.  The FEC information is associated with a transmission
of data about a particular object by a single sender. object.  There are three classes of packets
that may contain FEC information within a session: information: data packets, session-control packets
and feedback packets.  They generally contain different kinds of FEC
information.  Note that some protocols do may not use session-control or
feedback packets.

Data packets may sometime sometimes serve as session-control packets as well;
both data and session-control packets generally travel downstream (from from
the sender towards receivers) receivers and are addressed sent to a multicast IP address
(sometime they might be addressed channel or to the unicast address of a
specific
receiver). In the following, for simplicity we will refer to both data
and session control packets as downstream-traveling packets, or simply
downstream packets. receiver using unicast.

As a general rule, feedback packets travel upstream (from from receivers to
the sender) and are addressed to the unicast address of the sender. Sometimes, however, they might be addressed sent to a multicast IP address
channel or to the unicast address of a another receiver or also the the unicast address of to some different node (an intermediate node or
neighboring router that provides recovery
services or a neighboring router).

The FEC-related services.

This document specifies the FEC information that can must be present carried in downstream data
packets
can and the other FEC information that must be communicated either
out-of-band or in data packets. This document does not specify out-of-
band methods nor does it specify the way out-of-band FEC information is
associated with FEC information carried in data packets.  These methods
must be specified in a complete protocol instantiation that uses the FEC
building block. FEC information is classified as follows:

 1) FEC Encoding Identifier ID

      Identifies the FEC encoding encoder being used and has the purpose of
      allowing allows receivers to
      select the appropriate FEC decoder. As a
      general rule,  The value of the "FEC FEC Encoding Identifier"
      ID MUST be the same for a
      given session, i.e., for all transmission of data related to a
      particular object, but MAY vary across different transmissions of
      data about different objects in different sessions, objects, even if transmitted using to the same set
      of multicast groups channels and/or using a single upper-layer session.
      The FEC encoding ID is subject to IANA registration.

 2) FEC Encoding Name

      Provides a more specific identification of the FEC encoder being
      used for an Under-Specified FEC scheme.  This value is not used
      for Fully-Specified FEC schemes.  (See Section 1.1 for the
      definition of Under-Specified and Fully-Specified FEC schemes.)
      The FEC encoding name is scoped by the FEC encoding ID, and is
      subject to IANA registration.

 3) FEC payload ID

      Identifies the encoding symbol(s) in the payload of the packet.
      The content
      of this piece of information depends fields in the FEC Payload ID depend on the encoder being used

^L
      (e.g. in Block and Expandable FEC codes this may be the
      combination of block
      index number and encoding symbol identifier; in ideal expandable FEC
      codes this may be just a flat encoding symbol identifier).

 3) ID).

 4) FEC Object Transmission Information

      This is information regarding the encoding of a specific object
      needed by the FEC decoder (e.g. for Block and Expandable FEC codes
      this may be the combination of the source block length lengths and the
      object length).  This might also include general specific parameters of
      the FEC encoder. Note that, in
      strict terms, the "FEC

The FEC Encoding Identifier" belongs to this class
      of information, however, for practical purposes, we will consider
      it separately.

     All ID, FEC Encoding Name (for Under-Specified FEC schemes)
and the classes of information above, except 2), FEC Object Transmission Information can either be
transmitted sent to a receiver
within the transport data packet headers, within session (using protocol packet-header
fields) control packets, or by
some other means.  In any case, the means for communicating this to a
receiver is out of band. the scope of this document.  The information described in 2) FEC Payload ID MUST
be
transmitted included in data-packet the data packet header fields, as it provides a
description of the data contained in the packet. In the following we will specify
the content of 1), 2) and 3) regardless of whether these pieces of
information are transmitted in protocol packets or out of band. This
document neither specifies out-of-band methods to transport the
information nor does it specify the way out-of-band information is
associated with packet payloads. This last task is devolved to an upper-
layer protocol.

Within the context of FEC repair schemes, feedback packets are
(optionally) used to request FEC retransmission.  The FEC-related
information present in feedback packets usually contains an FEC Block
Identifier, ID
that defines the block that is being repaired, and the number of Repair
Symbols requested. Although this is the most common case, variants are
possible in which the receivers provide more specific information about
the Repair Symbols requested (e.g. an index range or a list of symbols
accepted). It is also possible to include multiple of these request requests in
a single feedback packet.

This document does not provide any detail about feedback schemes used in
combination with FEC nor the format of FEC information in feedback
packets.  If feedback packets are used in a complete protocol
instantiation, these details must be provided in the protocol
instantiation specification.

1.1.  FEC Encoding Identifier

This ID and FEC Encoding Name

The FEC Encoding ID is a numeric index that identifies a specific FEC

scheme OR a class of encoding schemes that share the same format of "FEC FEC Payload ID" and
"FEC Object Transmission Information".

^L

The ID
format.

An FEC Encoding Identifier identifies scheme is a specific Fully-Specified FEC scheme when if the encoding scheme is
formally and fully specified, in a way that independent implementors can
implement both encoder and decoder from the
specification. a specification that is an IETF
RFC.  The FEC Encoding ID uniquely identifies a Fully-Specified FEC
scheme. Companion documents of this specification may specify
such Fully-
Specified FEC schemes and associate them with "FEC FEC Encoding Identifier" ID values.
These documents MUST also specify a correspondent format for the
"FEC FEC Payload ID" ID and "FEC Object Transmission Information".  Currently
FEC Encoding Identifiers
specify the information in the range 0-127 are reserved for this class
of encoding schemes (fully-specified schemes). FEC Object Transmission Information.

It is possible that a FEC scheme cannot be completely specified or that
such a Fully-Specified FEC scheme,
because a specification is simply not available or also that a party exists
that owns the encoding scheme and it is not willing to disclose its
algorithm. the
algorithm or specification. We refer to these such an FEC encoding schemes as "Under-Specified"
schemes. Under-specified schemes can still be identified as follows:

  o A format of
an Under-Specified FEC scheme.  The following holds for an Under-
Specified FEC scheme:

  o The format of the fields "FEC FEC Payload ID" ID and "FEC the specific information in the
    FEC Object Transmission
    Information" Information MUST be defined for the encoding Under-
    Specified FEC scheme.

  o A value of "FEC for the FEC Encoding Identifier" ID MUST be reserved and associated
    to with
    the format definitions above. of the FEC Payload ID and the specific information in the
    FEC Object Transmission Information.  An already reserved "FEC FEC
    Encoding
    Identifier" ID value MUST be reused if it is associated to with the same
    format of "FEC FEC Payload ID" ID and "FEC the same information in the FEC Object
    Transmission Information" Information as the ones needed for the new under-specified Under-
    Specified FEC scheme.

  o A value of "FEC for the FEC Encoding Name" must Name MUST be reserved (see below). reserved.

An Under-specified FEC scheme is completely fully identified by the tuple (FEC
Encoding Identifier, ID, FEC Encoding Name). The tuple MUST identify a single scheme
that has at least one implementation. The party that owns this tuple
MUST be able to provide information on how to obtain the
under-specified Under-Specified
FEC scheme identified by the tuple (e.g. tuple, e.g. a pointer to a publicly
available reference-implementation or the name and contacts of a company
that sells it, either separately or embedded in another
product).

"FEC Encoding Names" are numeric identifiers scoped by a FEC Encoding
Identifier.

The FEC Encoding Name MUST be part of the "FEC Object Transmission
Information" and must be communicated to receivers together with the FEC
Encoding Identifier. product.

Different Under-Specified FEC schemes that share the same FEC Encoding Identifier
ID -- but have different FEC Encoding Names -- also share the same
format of FEC Payload ID and specify the same information in the FEC
Object Transmission Information.

^L

This specification reserves the range 0-127 for the values of FEC

Encoding Identifiers IDs for fully-specified encoding Fully-Specified FEC schemes and the range 128-255 for under-
specified encoding
the values of Under-Specified FEC schemes.

1.2.  FEC Payload ID and FEC Object Transmission Information

     A document that specifies an encoding FEC scheme and reserves a value of FEC
Encoding Identifier ID MUST define a packet-field packet format for the FEC Payload ID and
specify the information in the FEC Object Transmission Information
according to the need needs of the encoding scheme. This also applies to documents
that reserves reserve values of FEC Encoding Identifiers IDs for under-specified encoding schemes.
In this case the both Fully-Specified and
Under-Specified FEC Object Transmission Information must also include a
field to contain the "FEC Encoding Name".

A schemes.

The packet field format definition of for the FEC Object Transmission Information Payload ID MUST be
provided despite specify the fact that a protocol instantiation may decide
meaning and layout of the fields down to
communicate this information out the level of band.

All packet field definitions (FEC specific bits.
The FEC Payload ID and FEC Object Transmission
Information) MUST be fully specified at the level of bit-fields and they
must have a length that is a multiple of a 4-byte word (this is to
facilitate
word.  This requirement facilitates the alignment of packet fields in
protocol instantiations).

Note that the specification of FEC Payload ID MUST allow an
implementation-independent identification of the packet payload even in
the case of Under-Specified encoding schemes. instantiations.

2.  Preassigned FEC Encoding Identifiers IDs

This section specifies the FEC Encoding Identifier ID and the relative
packets field associated FEC
Payload ID format and the specific information in the FEC Object
Transmission Information for a number of known schemes that follow under the class
of under-specified Under-Specified FEC
schemes. Others  Under-specified FEC schemes that use the same FEC Payload ID
format and specific information in the FEC Object Transmission
Information as for one of the FEC Encoding IDs specified in this section
MUST use the corresponding FEC Encoding ID.  Other FEC Encoding IDs may
be specified for other Under-Specified FEC schemes in companion
documents.

2.1.  Small Block, Large Block and Expandable FEC Codes

This section subsection reserves a the FEC Encoding Identifier ID value 128 for the families of
codes described in [1], and specifies the relative packet fields.
Under-specified Under-
Specified FEC schemes described in [1] that belong to this class MUST use this
identifier and packet field definitions.

The FEC Encoding Identifier for under specified codes assigned to are called Small
Block, Block FEC
codes, Large Block, Block FEC codes and Expandable FEC Codes is 128.

^L codes.

The FEC Payload ID is composed of an encoding symbol identifier a Source Block Number and an
encoding block number Encoding
Symbol ID structured as follows:

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|		      encoding block number                    Source Block Number                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|		       encoding symbol                     Encoding Symbol ID                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

In addition, a one bit FEC Encoding Flag MAY be included, and this flag
indicates whether

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

The FEC Object Transmission Information has
blocks in the following structure:

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      FEC object.

The Encoding Name	|     Object Length (MSB)	|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|		      Object Length (LSB)			|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|		      Source Block Length			|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Note that this structure limits Symbol ID identifies which specific encoding symbol(s)
generated from the range source block are carried in the packet payload.  The
exact details of possible FEC the correspondence between Encoding Names
to 0-:-65536, despite Symbol IDs and the fact that
encoding symbol(s) in the packet payload are dependent on the particular
encoding algorithm used as identified by the Fec Encoding ID and by the
FEC Encoding Name, and these details may be proprietary.

The FEC Object Transmission Information can also be transmitted out has the following specific
information:

  o The total length of band. the object in bytes.

  o The Object Length, composed number of a Most Significant Bytes portion (MSB)
and a Least Significant Bytes portion (LSB), source blocks that the object is expressed partitioned into, and
    the length of each source block in bytes.

2.2.  Small Block Systematic FEC Codes

The following definitions apply to systematic codes of small length
(total block length < 2^16).

The

This subsection reserves the FEC Encoding Identifier ID value 129 for under specified codes assigned to the Under-
Specified FEC schemes described in [1] that are called Small Block
Systematic FEC Codes codes.  For Small Block Systematic FEC codes, each source
block is 129. of length at most 65536 bytes.

Although these codes can generally be accommodated by the FEC Encoding

^L

Identifier
ID described in Section 2.1, a specific Encoding-ID FEC Encoding ID is defined for systematic
Small Block Systematic FEC codes to allow better more flexibility and to retain
header compactness. The small source block length and small exapansion
factor that often characterize systematic codes may require that the
data source changes frequently 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.

The FEC Payload ID is composed of the encoding block number, the
encoding symbol identifier Source Block Number, Source Block
Length and the block length: Encoding Symbol ID:

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|		     encoding block number                    Source Block Number                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      Source block length Block Length      |	encoding symbol       Encoding Symbol ID      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The Source Block Number idenfities 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.  The
exact details of the correspondence between Encoding Symbol IDs and the
encoding symbol(s) in the packet payload are dependent on the particular
encoding algorithm used as identified by the Fec Encoding ID and by the
FEC Encoding Name, and these details may be proprietary.

The FEC Object Transmission Information, when used, Information has the following
structure:

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      FEC Encoding Name	|  Number specific
information:

  o The total length of redundant symbols	|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

When variable block-length is used, the number object in bytes.

  o The maximum length in bytes of redundant the encoding symbols is
to that can be interpreted as a maximum value (upper bound).
    generated for any source block.  This field is provided as an indication to allow receives
    receivers to preallocate a decoder buffer space that is suitable for all the object blocks.

Note that this structure limits the range of possible FEC Encoding Names decoding
    to 0-:-65536, despite the FEC Object Transmission Information can also
be transmitted out recover any source block.

  o The length in bytes of band. a source symbol.

3.  IANA Considerations

Values of FEC Encoding Identifiers IDs and FEC Encoding Names are subject to IANA
registration. FEC Encoding Identifiers IDs and FEC Encoding Names are hierarchical:
FEC Encoding Identifiers (at the top level) IDs scope ranges

^L of FEC Encoding Names. Not all  Only FEC Encoding Identifiers have

IDs that correspond to Under-Specified FEC schemes scope a corresponding
set of FEC Encoding Name scope (see below).

A Names.

The FEC Encoding Identifier ID is a numeric non-negative index. Value In this document,
the range of values for FEC Encoding IDs is 0 and 255.  Values from 0 to
127 are reserved for Fully-Specified FEC encoders that are fully specified, schemes, as described in section 3.1. more
detail in Section 1.1. The assignment of a FEC Encoding Identifier ID in this range
can only be granted if the requestor can provide such a specification
published as an IETF RFC. RFC, as described in more detail in Section 1.1.
Values greater than 127 can be
assigned from 128 to under-specified encoding schemes. Note: this 255 are reserved for Under-Specified FEC schemes, as
described in more detail in Section 1.1. This specification already
assigns the values 128 and 129.

In any case values 129, as described in Section 2.

Values of FEC Encoding Identifiers IDs can only be assigned if the required format
for the FEC packet fields corresponding to it (see section 1.2) Payload ID and the specific information in the FEC Object
Transmission Information are specified in a an IETF RFC.

Each FEC Encoding Identifier ID assigned to an under-specified encoding Under-Specified FEC scheme scopes an
independent range of FEC Encoding Names (i.e. the same value of FEC
Encoding Name can be reused for different FEC Encoding
Identifiers). IDs). An FEC
Encoding Name is a numeric non-negative index. The
document that reserves a FEC Encoding Identifier MAY also specify a
range for the subordinate FEC Encoding Names.

Under the scope of a FEC Encoding Identifier, ID, FEC Encoding Names are assigned on
a First Come First Served base to requestors that are able to provide
point of contact information and a pointer to publicly accessible
documentation describing the Under-Specified FEC scheme and ways to
obtain it (e.g. a pointer to a publicly available reference-implementation reference-
implementation or the name and contacts of a company that sells it,
either separately or embedded in another product). The requestor is
responsible for keeping this information up to date.

4.  Acknowledgments

Brian Adamson contributed to this document by shaping Section 2.2 and
providing general feedback. We also wish to thank Vincent Roca and
Justin Chapweske for his their comments.

5.  References

[1] Luby, M., Vicisano, Gemmell, J., L., Rizzo, L., Handley, M.,
Crowcroft, J., "The use of Forward Error Correction in Reliable
Multicast", Internet draft draft-ietf-rmt-info-fec-00.txt, November
2000.

^L draft-ietf-rmt-info-fec-01.txt, October 2001.

6.  Authors' Addresses

   Michael Luby
   luby@digitalfountain.com
   Digital Fountain, Inc.
   39141 Civic Center Drive
   Suite 300
   Fremont, CA  94538

   Lorenzo Vicisano
   lorenzo@cisco.com
   cisco Systems, Inc.
   170 West Tasman Dr.,
   San Jose, CA, USA, 95134

   Jim Gemmell
   jgemmell@microsoft.com
   Microsoft Research
   301 Howard St., #830
   San Francisco, CA, USA, 94105

   Luigi Rizzo
   luigi@iet.unipi.it
   ACIRI, 1947 Center St., Berkeley CA 94704
   and
   Dip. di Ing. dell'Informazione
   Universita` di Pisa
   via Diotisalvi 2, 56126 Pisa, Italy

   Mark Handley
   mjh@aciri.org
   ACIRI
   1947 Center St.
   Berkeley CA, USA, 94704

   Jon Crowcroft
   J.Crowcroft@cs.ucl.ac.uk
   Department of Computer Science
   University College London
   Gower Street,
   London WC1E 6BT, UK

^L

7.  Full Copyright Statement

Copyright (C) The Internet Society (2000). (2001).  All Rights Reserved.

This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it or
assist in its implementation may be prepared, copied, published and
distributed, in whole or in part, without restriction of any kind,
provided that the above copyright notice and this paragraph are included
on all such copies and derivative works. However, this document itself
may not be modified in any way, such as by removing the copyright notice
or references to the Internet Society or other Internet organizations,
except as needed for the purpose of developing Internet standards in
which case the procedures for copyrights defined in the Internet
languages other than English.

The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS
IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK
FORCE DISCLAIMS 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."

^L