[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-02.txt                            L.Vicisano/Cisco
                                                     J.Gemmell/Microsoft
                                            L.Rizzo/ACIRI and Univ. Pisa
                                                         M.Handley/ACIRI
                                                        J. Crowcroft/UCL
                                                        17 November 2000
                                                       Expires: May 2001


                 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/Gemmell/Vicisano/Rizzo/Handley/Crowcroft                   [Page 1]


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


     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 the 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 (intermediate node that provides recovery services
or 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.

 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
      (e.g. in Block FEC codes this may be the combination of block



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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


      index and symbol index; in expandable FEC codes this may be just a
      flat 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.


     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 specify the
content of 1), 2) and 3) independent of whether these pieces of
information are transmitted in protocol packets or out of band. This
document does not specify out of band methods to transport the
information.

Within the context of FEC repair schemes, feedback packets are
(optionally) used to request FEC retransmission.  The FEC-related
information present in feedback packets can be classified as follows:

 1) FEC Block Identifier

      This is the identifier of the FEC block for which retransmission
      is requested. This information does not apply to some type of
      decoders.

 2) Number of Repair Symbols

      This is the number of repair symbols requested, needed to recover
      the object.  This is used when there are still an ample supply of
      previously unsent symbols that can be sent, and this specifies the
      number of such additional symbols that should be sent.  This type
      of request is most applicable to both small and large block FEC
      codes and to expandable FEC codes.

 2) Range of Repair Symbols

      This is a range of the symbol indices that are being requested as
      repair symbols.  This is used when there is a specified set of
      repair symbols that will be most useful to reconstruct input
      symbols, and in general the requested symbols will be symbols not
      yet received by the requestor.  This type of request is most
      applicable to both small and large block FEC codes, and less



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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


      applicable to expandable FEC codes.

 2) List of Repair Symbols

      This is a list of the symbol indices that are being requested as
      repair symbols.  This is used when there is a specified set of
      repair symbols that will be most useful to reconstruct input
      symbols, and in general the requested symbols will be symbols not
      yet received by the requestor.  This type of request is most
      applicable to both small and large block FEC codes, and less
      applicable to expandable FEC codes.


1.1.  FEC Encoding Identifier


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

The FEC Encoding Identifier identifies a specific FEC encoding 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 encoding 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.

It is possible that a FEC encoding 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 encoding scheme.

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




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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


An Under-specified FEC scheme is completely identified by the tuple (FEC
Encoding Identifier, FEC Encoding Name). The party that owns this tuple
MUST be able to provide an FEC encoder and decoder that implement the
under-specified FEC encoding scheme identified by the tuple.

"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.

An FEC Encoding Identifier MAY also define a format for the (abstract)
feedback packet fields "FEC Block Identifier", "Number of Repair
Symbols", "Range of Repair Symbols" and "List of Repair Symbols".


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 protocol instantiation may decide to
communicate this information out of band.

The packet field format of "FEC Block Identifier" and "Number of Repair
Symbols" SHOULD be specified for each FEC encoding scheme, even the
scheme is mainly intended for feedback-less protocols.  FEC Block
Identifier may not apply to some encoding schemes.

All packet field definition (FEC Payload ID, FEC Object Transmission
Information, FEC Block Identifier and Number of Repair Symbols) MUST be
fully specified at 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).


2.  Predefined FEC encoders

This section specifies the FEC Encoding Identifier and the relative
packets field for a number of known schemes that follow under the class



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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


of under-specified FEC encoding 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 family of codes
described in Section 2.2, 2.3 and 2.4 and specifies the relative packet
fields.  Under-specified FEC encoding schemes that belong to this class
MUST use this identifier and packet field definitions.

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

The FEC Payload ID is composed of an encoding symbol index 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 SHOULD 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 FEC Object Transmission Information can also
be transmitted out of band.




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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


The Object Length, composed of a Most Significant Bytes portion (MSB)
and a Least Significant Bytes portion (LSB), is expressed in bytes.

There are three different types of feedback packets: number type, range
type, and list type.  The type of feedback packets used by the
application MUST be specified either out of band or within each feedback
packet. Feedback packets MUST contain both an FEC Block Identifier and
one of the following, depending on the type:

 o   number type: The number of repair symbols requested.

 o   range type: The range of symbol indices of the repair symbols
     requested.

 o   list type: The list of symbol indices of the repair symbols
     requested.

The structure of feedback packets is the following:


 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 Block Identifier                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


Number type:


 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                   Number of Repair Symbols                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
















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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


Range type:


 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|              Start Symbol Index of Repair Symbols             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|              End Symbol Index of Repair Symbols               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


List type:


 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 = Number of Symbols in the List               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Repair Symbol Index 0                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Repair Symbol Index 1                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                             ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Repair Symbol Index N-1                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



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
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. Value grater than 127 can be
assigned to under-specified encoding schemes.

In any case values of FEC Encoding Identifiers can only be assigned if
the required FEC packet fields corresponding to it (see section 3.1) are



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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


specified in a RFC.

Each FEC Encoding Identifier assigned to an under-specified encoding
scheme scopes a range of FEC Encoding Names. 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 encoder and a ways to obtain
it. The requestor is responsible for keeping this information up to
date.


4.  References


[1] Luby, M., Vicisano, L., Rizzo, L., Handley, M.,  Gemmell, J.,
Crowcroft, J., "The use of Forward Error Correction in Reliable
Multicast", draft-ietf-rmt-info-fec-00 submited to the IETF RMT working
group, November 2000.


5.  Authors' Addresses

   Michael Luby
   luby@digitalfountain.com
   Digital Fountain
   600 Alabama Street
   San Francisco, CA, USA, 94110

   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



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


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


   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/Gemmell/Vicisano/Rizzo/Handley/Crowcroft      Section 5.  [Page 10]


^L
INTERNET-DRAFT              Expires: May 2001              November 2000


6.  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/Gemmell/Vicisano/Rizzo/Handley/Crowcroft      Section 6.  [Page 11]


^L
INTERNET-DRAFT              Expires: May 2001              November 2000





















































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