[Search] [pdf|bibtex] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 rfc3452                               
Internet Engineering Task Force                                   RMT WG
INTERNET-DRAFT                                   M.Luby/Digital Fountain
draft-ietf-rmt-bb-fec-03.txt                            L.Vicisano/Cisco
                                                     J.Gemmell/Microsoft
                                            L.Rizzo/ACIRI and Univ. Pisa
                                                         M.Handley/ACIRI
                                                        J. Crowcroft/UCL
                                                            19 July 2001
                                                   Expires: January 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



Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft                   [Page 1]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


     provides an introduction to some commonly used FEC codes.


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

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

Data packets may sometime serve as session-control packets as well; both
data and session-control packets generally travel downstream (from the
sender towards receivers) and are addressed to a multicast IP address
(sometime they might be addressed 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.

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

The FEC-related information that can be present in downstream packets
can be classified as follows:


 1) FEC Encoding Identifier

      Identifies the FEC encoding being used and has the purpose of
      allowing receivers to select the appropriate FEC decoder. As a
      general rule, the "FEC Encoding Identifier" 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, even if
      transmitted using the same set of multicast groups and/or using a
      single upper-layer session.

 2) FEC payload ID

      Identifies the symbol(s) in the payload of the packet. The content
      of this piece of information depends on the encoder being used



Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft       Section 1.  [Page 2]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


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

 3) FEC Object Transmission Information

      This is information regarding the encoding of a specific object
      needed by the FEC decoder (e.g. for Block FEC codes this may be
      the combination of block length and object length). This might
      also include general parameters of the FEC encoder. Note that, in
      strict terms, the "FEC Encoding Identifier" belongs to this class
      of information, however, for practical purposes, we will consider
      it separately.


     All the classes of information above, except 2), can either be
transmitted within the transport session (using protocol packet-header
fields) or out of band. The information described in 2) MUST be
transmitted in 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, 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 in a single feedback packet.

This document does not provide any detail about the format of FEC
information in feedback packets.


1.1.  FEC Encoding Identifier


This is a numeric index that identifies a specific FEC scheme OR a class
of encoding schemes that share the same format of "FEC Payload ID" and
"FEC Object Transmission Information".




Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft     Section 1.1.  [Page 3]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


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

It is possible that a FEC scheme cannot be completely specified or that
such 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. We refer to these encoding schemes as "Under-Specified"
schemes. Under-specified schemes can still be identified as follows:

  o A format of the fields "FEC Payload ID" and "FEC Object Transmission
    Information" MUST be defined for the encoding scheme.

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

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


An Under-specified FEC scheme is completely identified by the tuple (FEC
Encoding Identifier, 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 FEC scheme identified by the 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.

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




Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft     Section 1.1.  [Page 4]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


This specification reserves the range 0-127 of FEC Encoding Identifiers
for fully-specified encoding schemes and the range 128-255 for under-
specified encoding schemes.


1.2.  FEC Payload ID and FEC Object Transmission Information


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

A packet field definition of FEC Object Transmission Information MUST be
provided despite the fact that a protocol instantiation may decide to
communicate this information out of band.

All packet field definitions (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 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.


2.  Preassigned FEC Encoding Identifiers

This section specifies the FEC Encoding Identifier and the relative
packets field for a number of known schemes that follow under the class
of under-specified FEC schemes. Others may be specified in companion
documents.


2.1.  Small Block, Large Block and Expandable FEC Codes

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

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




Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft     Section 2.1.  [Page 5]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


The FEC Payload ID is composed of an encoding symbol identifier and an
encoding block number 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                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      encoding symbol ID                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


In addition, a one bit FEC Encoding Flag MAY be included, and this flag
indicates whether the encoding symbol(s) in the payload of the packet
are source symbol(s) or redundant symbol(s).

The FEC Object Transmission 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        |     Object Length (MSB)       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Object Length (LSB)                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Source Block Length                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


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

The Object Length, composed of a Most Significant Bytes portion (MSB)
and a Least Significant Bytes portion (LSB), is expressed 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 FEC Encoding Identifier for under specified codes assigned to Small
Block Systematic FEC Codes is 129.

Although these codes can generally be accommodated by the FEC Encoding



Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft     Section 2.2.  [Page 6]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


Identifier described in Section 2.1, a specific Encoding-ID is defined
for systematic codes to allow better 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 and the block length:


 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 length      |       encoding symbol ID      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


The FEC Object Transmission Information, when used, 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 of redundant symbols  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


When variable block-length is used, the number of redundant symbols is
to be interpreted as a maximum value (upper bound). This field is
provided as an indication to allow receives to preallocate a decoder
suitable for all the object blocks.

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


3.  IANA Considerations

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



Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft       Section 3.  [Page 7]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


of FEC Encoding Names. Not all FEC Encoding Identifiers have a
corresponding FEC Encoding Name scope (see below).

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

In any case values of FEC Encoding Identifiers can only be assigned if
the required FEC packet fields corresponding to it (see section 1.2) are
specified in a RFC.

Each FEC Encoding Identifier assigned to an under-specified encoding
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). 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, 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 FEC scheme and ways to obtain it
(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). 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 for his
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.





Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft       Section 5.  [Page 8]


^L
INTERNET-DRAFT            Expires: January 2002                July 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










Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft       Section 6.  [Page 9]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001


7.  Full Copyright Statement

Copyright (C) The Internet Society (2000).  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."


























Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft      Section 7.  [Page 10]


^L
INTERNET-DRAFT            Expires: January 2002                July 2001





















































Luby/Vicisano/Gemmell/Rizzo/Handley/Crowcroft      Section 7.  [Page 11]