RMT Working Group                                                M. Luby
INTERNET DRAFT                                               L. Vicisano
Expires 8 September                              M.Luby/Digital Fountain
Internet Engineering Task Force                       L.Vicisano/Cisco
INTERNET-DRAFT                                      L.Rizzo/U. of Pisa
draft-ietf-rmt-bb-fec-01.txt                       J.Gemmell/Microsoft
13 July 2000                                        L. Rizzo
                                                              J. Gemmell
                                                            J. Crowcroft                                           J.Crowcroft/UCL
                                                B. Lueckenhoff
                                                            8 March Lueckenhoff/Cadence
Expires 13 January 2000

              Reliable Multicast Transport Building Block:
                     Forward Error Correction Codes
                     <draft-ietf-rmt-bb-fec-00.txt>
                     <draft-ietf-rmt-bb-fec-01.txt>

Status of this Memo

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

   Copyright Notice

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

Abstract

This memo describes the use of Forward Error Correction (FEC) codes
within the context of reliable IP multicast transport and provides an
introduction to some commonly-used FEC codes.

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

1.  Rationale and Overview

There are many ways to provide reliability for transmission proto-
   cols. protocols.
A common method is to use ARQ, automatic request for retransmission.
With ARQ, receivers use a back channel to the sender to send requests
for retransmission of lost packets.  ARQ works well for one-to-one
reliable protocols, as evidenced by the pervasive suc-
   cess success of TCP/IP.
ARQ has also been an effective reliability tool for one-to-many
reliability protocols, and in particular for some reli-
   able reliable IP multicast
protocols.  However, for one-to-very many reliabil-
   ity reliability protocols, ARQ has
limitations, including the feedback implosion problem because many
receivers are transmitting back to the sender, and the need for a back
channel to send these requests from the receiver.  Another limitation is
that receivers may experience dif-
   ferent different loss patterns of packets, and
thus receivers may be delayed by retransmission of packets that other
receivers have lost that but they have already received.  This may also
cause wasteful use of bandwidth used to retransmit packets that have
already been received by many of the receivers.

In environments where ARQ is either costly or impossible because there
is either a very limited capacity back channel or no back chan-
   nel channel at
all, such as satellite transmission, a Data Carousel approach to
reliability is sometimes used [AFZ95].  With a Data Carousel, the sender
partitions the object into equal length pieces of data, which we
hereafter call source symbols, places them into packets, and then
continually cycles through and sends these packets. Receivers
continually receive packets until they have received a copy of each
packet.  Data Carousel has the advantage that it requires no back
channel because there is no data that flows from receivers to the
sender.  However, Data Carousel also has limita-
   tions. limitations. For example, if a
receiver loses a packet in one round of transmission it must wait an
entire round before it has a chance to receive that packet again.  This
may also cause wasteful use of bandwidth, as the sender continually
cycles through and transmits the packets until no receiver is missing a
packet.

FEC codes provide a reliability method that can be used to augment or
replace other reliability methods, especially for one-to-many relia-
   bility
reliability protocols such as reliable IP multicast.  Ideally,  We first briefly
review some of the basic properties and types of FEC codes before
reviewing their uses in the context of reliable IP multicast can be used to encode an object into
   packets in such multicast.  Later, we
provide a way that each received packet is fully useful more detailed description of some of FEC codes.

In the general literature, FEC refers to a
   receiver the ability to reassemble overcome both
erasures (losses) and bit-level corruption. However, in the object regardless case of previous packet
   reception patterns. Thus, if some IP

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

multicast, lower network layers will detect corrupted packets are lost in transit between
   the sender and
discard them. Therefore, an IP multicast protocol need not be concerned
with corruption; the receiver, instead of asking for retransmission focus is solely on erasure codes.  The payloads are
generated and processed using ARQ or waiting till the packets an FEC erasure encoder and objects are resent
reassembled from reception of packets using Data Carousel, the receiver can use any other subsequent corresponding FEC
erasure decoder.

The input to an FEC encoder is some number k of equal length source
symbols.  The FEC encoder generates some number of packets
   that arrive to reassemble the object.  This implies encoding symbols that
are of the same
   packet is fully useful to all receivers to reassemble length as the object,
   even though source symbols.  The chosen length of the receivers may have previously experienced different
   packet loss patterns.  This property
symbols can reduce or even eliminate the
   problems mentioned above associated with ARQ and Data Carousel and
   thereby dramatically increase the scalability vary upon each application of the protocol to ord-
   ers of magnitude more receivers.

   For some reliable IP multicast protocols, FEC codes are used in con-
   junction with ARQ to provide reliability.  For example, in a first
   round all of the source symbols could encoder, or it can be transmitted, and then
   receivers could report back to the sender the number of
fixed.  These encoding symbols they are missing from each block.  Then, the sender could compute the max-
   imum placed into packets for transmission.
The number of missing encoding symbols from placed into each block among all receivers,
   and then transmit that packet can vary on a per
packet basis, or a fixed number of redundant symbols for (often one) can be placed
into each block.
   In this case, even if different receivers are missing different sym-
   bols packet.  Also, in different blocks, transmitted redundant symbols for a given
   block are useful each packet is placed enough information to all receivers missing
identify the particular encoding symbols from that block.

   For others, FEC codes are used carried in a Data Carousel fashion to provide
   reliability, by cycling through and transmitting that packet.  Upon
receipt of packets containing encoding symbols, the receiver feeds these
encoding symbols
   instead of into the source symbols.   For example, suppose an corresponding FEC code is
   applied decoder to the entire object consisting recreate an exact
copy of the k source symbols to gen-
   erate n encoding symbols with the property that symbols.  Ideally, the entire object FEC decoder can
   be reassembled recreate an
exact copy from any k encoding symbols, and the sender cycles
   through and transmits of the n encoding symbols in the same order in
   each round.  Then, symbols.

In a receiver can join the transmission at any point
   in time, and later section, we describe a technique for using FEC codes as long
described above to handle blocks with variable length source symbols.

Block FEC codes work as the receiver receives at least follows.  The input to a block FEC encoder is k encoding
source symbols during the transmission and a number n.  The encoder generates n-k redundant
symbols yielding an encoding block of n encoding symbols then in total
composed of the
   receiver can completely recover k source symbols and the object.  This is true even if n-k redundant symbols.  A block
FEC decoder has the
   receiver joins property that any k of the data carousel n encoding symbols in the middle of a round.

   For yet other reliable IP multicast protocols the sole method to
   obtain reliability
encoding block is sufficient to use FEC codes.  For example, reconstruct the sender can
   decide a priori how many encoding symbols it will transmit, use an original k source
symbols.

Expandable FEC code to generate that number of encoding codes work as follows.  An expandable FEC encoder takes
as input k source symbols from the object, and then transmit the generates as many unique encoding symbols to all receivers.  This method
   is for example applicable to streaming protocols,
as requested on demand, where the stream is
   partitioned into objects, amount of time for generating each object
encoding symbol is encoded into the same independent of how many encoding sym-
   bols using an symbols are
generated.  Unlike block FEC code, and then codes, the sets source symbols are not
considered part of the encoding symbols for
   each object are transmitted one after the other using IP multicast.
   The large on demand codes described below have an expandable FEC code.  An
expandable FEC decoder has the property that any k of the
   FEC encoder can generate sequentially as many unique
encoding symbols is sufficient to reconstruct the original k source
symbols.

Along a different dimension, we classify FEC codes loosely as are
   desired on demand.  Thus, reliable IP multicast protocols that use
   large on demand codes generally rely solely on these codes for relia-
   bility.

   In the general literature, being
either small or large.  A small FEC refers to the ability to overcome both
   erasures (losses) and bit-level corruption. However, code is efficient in the case terms of
   IP multicast, lower network layers will detect corrupted packets
processing time requirements for encoding and
   discard them. Therefore, an IP multicast protocol need not be con-
   cerned with corruption; the focus is solely on erasure codes.  The
   payloads are generated decoding for small values

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

of k, and processed using an a large FEC erasure encoder code is efficient for encoding and
   objects are reassembled from reception decoding for
much large values of packets using the
   corresponding FEC erasure decoder.

   The primary purpose k.  There are implementations of using standard block FEC
codes is to ensure that minimal
   number of packets need be received in order for a receiver to
   reassemble an object.   Reception overhead is used to measure how
   close a protocol comes have encoding times proportional to achieving this minimum. Reception overhead
   is n times the aggregate length of packets needed to recover the object
   beyond
k source symbols, and decoding times proportional l times the object length, measured as a percentage length of
the object
   length.  For example, if it takes 15 MB k source symbols, where l is the number of packets in order to
   recover a 10 MB object, then missing source symbols
among the reception overhead is (15  10)/10 k received encoding symbols.  Because of the growth rate of
the encoding and decoding times 100, or 50%.  The minimal reception overhead possible is 0%.

2. as a function of k and n, these are
typically considered to be small block FEC Codes

2.1. Simple codes codes.  There are some very simple close
approximations to block FEC codes that are effective which for repairing
   packet loss under very low loss conditions.  For example, one simple
   way to provide protection from a single loss is to partition the
   object into fixed size source all practical purposes can
generate n encoding symbols and then add a redundant symbol
   that is the parity (XOR) of all can decode the k source symbols.  The size of a
   source symbol is chosen so that it fits perfectly into symbols in time
proportional to the payload length of
   a packet, i.e. if the packet payload is 512 bytes then each source
   symbol is 512 bytes.  The header of each packet contains enough
   information n encoding symbols.  These codes are
considered to identify the payload.  In this case, this includes a
   symbol ID.  The symbol IDs be large block FEC codes.  There are numbered consecutively starting from
   zero independently close approximations
to expandable FEC codes which for the all practical purposes can generate
each encoding symbol in time proportional to its length, and can decode
all k source symbols and for the redundant sym-
   bol.  Thus, in time proportional to their length.  These are
considered to be large expandable FEC codes.

Ideally, FEC codes in the packet header also contains an context of IP multicast can be used to
generate encoding flag symbols that
   indicates whether they symbol are transmitted in the payload is packets in such a source symbol or way
that each received packet is fully useful to a
   redundant symbol, where 1 indicates source symbol and 0 indicates
   redundant symbol.  For example, if receiver to reassemble
the object consists regardless of four source
   symbols that have values a, b, c previous packet reception patterns. Thus, if
some packets are lost in transit between the sender and d, then the value receiver,
instead of asking for specific retransmission of the redun-
   dant symbol is e = a XOR b XOR c XOR d.   Then, the lost packets carrying
   these symbols look like (0, 1: a), (1, 1: b), (2, 1: c), (3, 1: d),
   (0, 0: e).  In this example, or
waiting till the first two fields packets are in resent using Data Carousel, the header receiver
can use any other subsequent equal amount of data contained in packets
that arrive to reassemble the packet, where the first field is object.  These packets can either be
proactively transmitted or they can be explicitly requested by
receivers.  This implies that the symbol ID and data contained in the second
   field same packet is
fully useful to all receivers to reassemble the encoding flag.  The portion of object, even though the
receivers may have previously experienced different packet after loss
patterns.  This property can reduce or even eliminate the
   colon is problems
mentioned above associated with ARQ and Data Carousel and thereby
dramatically increase the payload.  Any single symbol scalability of the object can be
   recovered as the parity protocol to orders of all the other symbols.
magnitude more receivers.

1.1.  Application of FEC codecs

For example, if
   packets (0, 1:  a), (1, 1: b), (3, 1: d), (0, 0: e) some reliable IP multicast protocols, FEC codes are received then
   the symbol value for the missing source symbol used in
conjunction with ID 2 can ARQ to provide reliability.  For example, a large
object could be
   recovered by computing partitioned into a XOR b XOR d XOR e = c.

   When the number of source blocks consisting of
a small number of source symbols each, and in the object is large, a simple
   block code variant first round of
transmission all of the above can be used.  In this case, the
   source symbols are grouped together into source blocks of k
   consecutive symbols each, and then for each block of all the source symbols a
   redundant symbol is added to form encoding blocks of k+1 symbols
   each.  Then, a source block can could
be recovered from any k of transmitted.  Then, receivers could report back to the k+1 sender the
number of source symbols they are missing from the associated encoding each source block.

   Slightly more sophisticated ways  The

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

sender could then compute the maximum number of adding redundant missing source symbols using
   parity can also be used. For example, one can group the k
from each source sym-
   bols in the object into block among all receivers.  Based on this, a p x p square matrix, where p = sqrt(k).
   Then, small
block FEC encoder could be used to generate for each row source block a
number of redundant symbol is added that is symbols equal to the parity computed maximum number of
   all the
missing source symbols in from the row.  Similarly, for each column block among all receivers.  In a
   redundant symbol is added that is second
round of transmission, the parity server would then send all of these redundant
symbols for all the source sym-
   bols blocks.  In this example, if there are no losses in the column.  Then, Any row
second round of the matrix can transmission then all receivers will be recovered
   from any p able to recreate
an exact copy of the p+1 each original block.  In this case, even if different
receivers are missing different symbols in the row, and similarly different blocks, transmitted
redundant symbols for any
   column.  Higher dimensional product codes using this technique can
   also be used.  However, one must be wary of using these constructions
   without some thought towards the possible loss patterns of symbols.
   Ideally, the property that one would like a given block are useful to obtain is that if k
   source all receivers missing
symbols from that block in the second round.

For other reliable IP multicast protocols, FEC codes are encoded into used in a Data
Carousel fashion to provide reliability, which we call an FEC Data
Carousel.  For example, an FEC Data Carousel using a large block FEC
code could work as follows.  The large block FEC encoder produces n
encoding symbols (the encoding sym-
   bols consist of the source symbols and the redundant symbols) then considering all the k source symbols can be recovered from any k of an object as
one block. The sender cycles through and transmits the n encoding
   symbols.  Using
symbols in packets in the simple constructions described above does not
   yield codes that come close to obtaining this ideal behavior.

2.2. Small block codes

   Reliable IP multicast protocols may use a block (n, k) same order in each round.  An FEC erasure
   code [BLA84]. A popular example of this types of codes is Data
Carousel can have much better protection against packet loss than a class of
   Reed-Solomon codes. Data
Carousel.  For such codes, example, a receiver can join the transmission at any
point in time, And, as long as the receiver receives at least k source encoding
symbols are encoded into during the transmission of the next n > k encoding symbols, such that any k the
receiver can completely recover the object.  This is true even if the
receiver starts receiving packets in the middle of a pass through the
encoding symbols symbols.  This method can also be used to reassemble when the original k source symbols.  Thus, these
   codes have 0% reception overhead when used to encode the entire object directly.  Block codes are usually systematic, which means
   that the n encoding symbols consist of the k source symbols is
partitioned into blocks and n-k
   redundant symbols generated from these k source symbols, where the
   size of a redundant symbol short block FEC code is the same applied to each
block separately.  In this case, as that for a source symbol.
   For example, the first simple code (XOR) described we explain in the previous
   subsection more detail below, it
is a (k+1, k) code.  In general, the freedom useful to choose n
   larger than k+1 is desirable, as this can provide much better protec-
   tion against losses.   Codes of this sort are often based on alge-
   braic methods using finite fields.  Some of interleave the most popular such
   codes symbols from the different blocks when they
are based on linear block codes.   Implementations transmitted.

Since any number of (n, k) encoding symbols can be generated using an
expandable FEC encoder, reliable IP multicast protocols that use
expandable FEC erasure codes are efficient enough to be used by personal comput-
   ers [RIZ97c, NON97]. generally rely solely on these codes for
reliability.  For example, [Riz97b] describes when an implementa-
   tion where expandable FEC code is used in a FEC
Data Carousel application, the encoding packets never repeat, and decoding speeds decay as C/j, where thus
any k of the
   constant C is on encoding symbols in the order potentially unbounded number of 10
encoding symbols are sufficient to 80 Mbytes/second for Pentium
   class machines of various vintages and j is upper bounded by min(k,
   n-k).

   In practice, recover the values of k and n must be small for these codes as
   large values make encoding and decoding prohibitively expensive.  As
   many objects are longer than original k source
symbols.

For yet other reliable IP multicast protocols the method to obtain
reliability is to generate enough encoding symbols for reasonable values so that each encoding
symbol is transmitted at most once.  For example, the sender can decide
a priori how many encoding symbols it will transmit, use an FEC code to

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

generate that number of k encoding symbols from the object, and then
transmit the symbol length (e.g. larger than 16 KB encoding symbols to all receivers.  This method is for k = 16 using 1 KB sym-
   bols), they are divided
example applicable to streaming protocols, where the stream is
partitioned into m source blocks consisting of k objects, the source symbols each. An erasure code is used to encode for each source block object are encoded
into an encoding block consisting of n encoding symbols.  For a
   receiver to completely recover symbols using an FEC code, and then the object, k distinct sets of encoding sym-
   bols (i.e., with different symbol IDs) must be received
symbols for each of object are transmitted one after the encoding blocks.  For other using IP
multicast.

2.  FEC Codes

2.1.  Simple codes

There are some encoding blocks, more than k encoding
   symbols may be received, in which case any additional encoding sym-
   bols very simple codes that are discarded.  An example encoding structure effective for repairing packet
loss under very low loss conditions.  For example, one simple way to
provide protection from a single loss is shown in Figure
   1.

       |   source symbols      | to partition the object into
fixed size source symbols      |
       | and then add a redundant symbol that is the
parity (XOR) of source block 0   | all the source symbols.  The size of a source block 1   |
                    |                          |
                    v                          v
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
       |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                               |
                             encode
                               |
                               v
   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
   |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                  ^                             ^
                  |                             |
   |  encoding symbols           | encoding symbols            |
   | symbol is
chosen so that it fits perfectly into the payload of encoding block 0        | a packet, i.e. if
the packet payload is 512 bytes then each source symbol is 512 bytes.
The header of encoding block 1         |

   Figure 1. Encoding structure each packet contains enough information to identify the
payload.  In this case, this includes a symbol ID.  The symbol IDs are
numbered consecutively starting from zero independently for object divided into m = 2 the source
   blocks, k = 8
symbols and n = 10

   When using small block codes for objects the redundant symbol.  Thus, the packet header also
contains an encoding flag that are larger than k
   source symbols indicates whether the symbol in length, the
payload is a source symbols in symbol or a redundant symbol, where 1 indicates
source symbol and 0 indicates redundant symbol.  For example, if the
object are
   assigned to blocks. Typically, each k contiguous consists of four source symbols that have values a, b, c and d,
then the value of the object redundant symbol is assigned to e = a block, i.e., block XOR b XOR c consists of XOR d.
Then, the
   range of source packets carrying these symbols [ck, (c+1)k-1]. This ensures that memory
   reference look like

(0, 1: a), (1, 1: b), (2, 1: c), (3, 1: d), (0, 0: e).

In this example, the first two fields are local when in the sender reads source symbols to encode, header of the packet,
where the first field is the symbol ID and when the receiver reads second field is the
encoding symbols to decode.Locality flag.  The portion of
   reference the packet after the colon is particularly important when the
payload.  Any single symbol of the object is stored on
   disk, can be recovered as it reduces the disk seeks required.

   The block number and parity
of all the other symbols.  For example, if packets

(0, 1: a), (1, 1: b), (3, 1: d), (0, 0: e)

are received then the symbol value for the missing source symbol with ID within that block
2 can be
   used to uniquely specify recovered by computing a source symbol within the object. If XOR b XOR d XOR e = c.

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

When the
   size number of source symbols in the object is not large, a multiple simple block
code variant of k source symbols, then the
   last above can be used.  In this case, the source block will contain less than symbols
are grouped together into source blocks of some number k symbols.

   Encoding of consecutive
symbols can each, where k may be uniquely identified by block number and
   encoding symbol ID.  The different for different blocks.  If a block numbers can be numbered consecutively
   starting from zero.  One way
consists of identifying encoding k source symbols within then a
   block are to use redundant symbol IDs and an encoding flag that is used added to
   specify whether form an
encoding symbol is block consisting of k+1 encoding symbols.  Then, a source symbol or a redundant
   symbol, where for example 1 indicates block
consisting of k source symbol and 0 indicate
   redundant symbol.  The symbol IDs symbols can be numbered consecutively
   starting recovered from zero for each block independently for any k of the source sym-
   bols and for k+1
encoding symbols from the redundant symbols.  Thus, an associated encoding symbol block.

Slightly more sophisticated ways of adding redundant symbols using
parity can also be
   identified by its block number, the encoding flag, and the symbol ID. used. For example, if the object consists 10 one can group a block consisting
of k source symbols with values a,
   b, c, d, e, f, g, h, i, and j, and k = 5 and n in an object into a p x p square matrix, where p = 8, then there are
   two source blocks consisting
sqrt(k).  Then, for each row a redundant symbol is added that is the
parity of 5 all the source symbols each, and there are two
   encoding blocks consisting in the row.  Similarly, for each column
a redundant symbol is added that is the parity of 8 all the source symbols each.  Let p, q and r be
in the
   values column.  Then, any row of the redundant matrix can be recovered from any p
of the p+1 symbols for in the first encoding block, and let
   x, y row, and z similarly for any column.  Higher
dimensional product codes using this technique can also be the values used.
However, one must be wary of using these constructions without some
thought towards the redundant symbols for possible loss patterns of symbols.  Ideally, the second
   encoding block.  Then the encoding
property that one would like to obtain is that if k source symbols together with their iden-
   tifiers are (0, 0, 1:a), (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d),
   (0, 4, 1: e), (0, 0, 0: p), (0, 1, 0: q), (0, 2, 0: r), (1, 0, 1: f),
   (1, 1, 1: g), (1, 2, 1: h), (1, 3, 1: i), (1, 4, 1: j), (1, 0, 0: x),
   (1, 1, 0: y) and (1, 2, 0: z).  In this example, the first three
   fields identify the
encoded into n encoding symbol, where the first field is the
   block number, the second field is the symbol ID and the third field
   is the symbols (the encoding flag. The value symbols consist of the encoding symbol is written
   after
source symbols and the colon.  Each block redundant symbols) then the k source symbols can
be recovered from any 5 k of the 8 n encoding symbols associated with that block.  For example, reception
   of (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 0, 0: p) and (0, 1,
   0: q) are sufficient to recover the first source block and reception
   of (1, 0, 1: f), (1, 1, 1: g), (1, 0, 0: x), (1, 1, 0: y) and (1, 2,
   0: z) are sufficient to recover symbols.  Using the second source block.

2.3. Large block codes

   Tornado simple
constructions described above does not yield codes [LUB97] are that come close to
obtaining this ideal behavior.

2.2.  Small block FEC erasure codes that provide an
   alternative to small

Reliable IP multicast protocols may use a block codes.  A (n, k) Tornado FEC code requires
   slightly more than k out [BLA84].
A popular example of these types of codes is a class of Reed-Solomon
codes. For such codes, k source symbols are encoded into n > k encoding
symbols, such that any k of the encoding symbols can be used to
reassemble the original k source symbols. However,  Thus, these codes have 0%
reception overhead when used to encode the advantage is entire object directly.
Block codes are usually systematic, which means that the value n encoding
symbols consist of k may be on the
   order of tens of thousands k source symbols and still run efficiently.  Because n-k redundant symbols
generated from these k source symbols, where the size of
   memory considerations, a redundant
symbol is the same as that for a source symbol.  For example, the first
simple code (XOR) described in practice the value of previous subsection is a (k+1, k)
code.  In general, the freedom to choose n larger than k+1 is restricted desirable,
as this can provide much better protection against losses.   Codes of
this sort are often based on algebraic methods using finite fields.
Some of the most popular such codes are based on linear block codes.

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

Implementations of (n, k) FEC erasure codes are efficient enough to be
   a small multiple of k, e.g., n = 2k.
used by personal computers [RIZ97c, NON97]. For example, [BYE98] [RIZ97b]
describes an implementation of Tornado codes where the encoding and decoding speeds are proportional to decay
as C/j, where the constant C is on the order of 10 Mbytes/second to 80 Mbytes/second
for Pentium class machines of various vintages when k and j is in upper bounded by
min(k, n-k).

In practice, the tens of
   thousands and n = 2k.  The reception overhead for such values of k and n is in the 5-10% range.  Tornado must be small (below 256) for such
FEC codes require a as large amount of
   out of band information to be communicated to all senders values make encoding and
   receivers decoding prohibitively
expensive.  As many objects are longer than k symbols for each different object length, and require an amount reasonable
values of
   memory on the encoder k and decoder which is proportional to the object symbol length times 2n/k.

   Tornado codes are designed to have low reception overhead on average
   with respect to reception of a random portion of the encoding pack-
   ets.  Thus, to ensure that a receiver (e.g. larger than 16 kilobyte for k =
16 using 1 kilobyte symbols), they can reassemble the object with
   low reception overhead, the packets are permuted be divided into a random order
   before transmission.

2.4. On demand codes

   All number of the FEC erasure codes described up to this point are
source blocks.  Each source block
   codes.  There is a different type consists of some number k of source
symbols, where k may vary between different source blocks.  The FEC erasure code that we call on
   demand codes.  Like block codes, an on demand
encoder operates on an
   object of known size that is partitioned used to encode a k source symbol source block into equal a n
encoding symbol encoding block, where the length n of the encoding block
may vary for each source block.  For a receiver to completely recover
the object, for each source
   symbols.  Unlike block codes, there is no predetermined number consisting of k source symbols, k
distinct encoding symbols that can (i.e., with different symbol IDs) must be generated for on demand codes.
   Instead, an on demand encoder can generate as few or as many encoding
   symbols as required on demand. Also unlike block codes, optimal on
   demand codes have
received from the additional attractive property that corresponding encoding block.  For some encoding
blocks, more encoding symbols for the same object can may be generated and transmitted from
   multiple servers and concurrently received by a receiver and yet than there are source
symbols in the
   receiver incurs a 0% reception overhead.

   LT codes corresponding source block, in which case any additional
encoding symbols are an discarded.  An example encoding structure is shown
in Figure 1.

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

        |   source symbols      |   source symbols      |
        |   of a large on demand source block 0   |   of source block 1   |
                     |                          |
                     v                          v
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                                |
                            FEC code.  An LT encoder
   uses randomization to generate each
                                |
                                v
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                   ^                             ^
                   |                             |
    |  encoding symbol randomly and
   independently symbols           | encoding symbols            |
    |  of all other encoding symbols.  An LT encoder satisfies block 0        | of encoding block 1         |

    Figure  1. Encoding structure for object divided into two source
    blocks consisting of 8 source symbols each, and the on demand property, as it can FEC  encoder
    is  used to generate as few or as many 2 additional redundant symbols (10 encoding
    symbols as required on demand. Let k be the number in total) for each of source symbols
   that the two source blocks.

In many cases, an object is partitioned into.  An LT decoder has the property
   that with very high probability the receipt of any set into equal length source blocks
each consisting of slightly
   more than k encoding contiguous source symbols is sufficient to reassemble the object.
   Like Tornado codes, the value of k may be very large, i.e., on the
   order object, i.e.,
block c consists of tens or hundreds the range of thousands, and source symbols [ck, (c+1)k-1].  This
ensure that the FEC encoder can be optimized to handle a particular
number k of source symbols.  This also ensures that memory references
are local when the sender reads source symbols to encode, and decoder
   run efficiently in software.  For example when the
receiver reads encoding and decoding
   speeds for LT codes are proportional to 3 Mbytes/second symbols to 20
   Mbytes/second for Pentium class machines decode.  Locality of various vintages reference is
particularly important when k the object is in stored on disk, as it reduces
the high tens of thousands. disk seeks required.  The reception overhead for such
   values of k is in block number and the 2-4% range.

   When a new encoding source symbol is to ID
within that block can be generated, it used to uniquely specify a source symbol within
the object. If the size of the object is based on not a key
   that uniquely describes how multiple of k source
symbols, then the last source block will contain less than k symbols.

Encoding symbols can be uniquely identified by block number and encoding
symbol is to ID.  The block numbers can be generated.
   Because numbered consecutively starting
from zero.  One way of identifying encoding symbols within a block are randomly
to use symbol IDs and independently generated, LT
   codes have the property an encoding flag that is used to specify whether
an encoding symbols for the same object symbol is a source symbol or a redundant symbol, where for
example 1 indicates source symbol and 0 indicate redundant symbol.  The

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

symbol IDs can be generated and transmitted numbered consecutively starting from multiple servers and concurrently
   received by a receiver with no more reception overhead than if all
   the encoding symbols were generated by a single sender.

   There is a tradeoff between zero for each
block independently for the number of source symbols and for the
   reception overhead, redundant
symbols.  Thus, an encoding symbol can be identified by its block
number, the encoding flag, and the larger symbol ID.  For example, if the number of
object consists 10 source symbols the
   smaller the reception overhead.  Thus, for shorter objects, it is
   sometimes advantageous to include multiple symbols in each packet.
   Normally, with values a, b, c, d, e, f, g, h, i,
and in the discussion below, there is only one symbol per
   packet.

   Like small block codes, j, and k = 5 and n = 8, then there is a point when the object is large
   enough that it makes sense to partition it into are two source blocks when using LT
   codes.  Generally the object is partitioned into consisting
of 5 symbols each, and there are two encoding blocks whenever the
   number consisting of source 8
symbols times the packet payload length is less than each.  Let p, q and r be the size values of the object.  Thus, if redundant symbols for
the packet payload is 1024 bytes first encoding block, and let x, y and z be the number values of source the
redundant symbols is 64,000 then any object over 64 MB
   will be partitioned into more than one block.  One can choose the
   number of source symbols to partition the object into, depending on
   the desired encoding and decoding speed versus reception overhead
   tradeoff desired.  Encoding symbols can be uniquely identified by a
   block number (when for the object is large enough to be partitioned into
   more than one block) and an second encoding symbol ID.  The block numbers,
   if they are used, are generally numbered consecutively starting from
   zero within block.  Then the object.  The range of possible values for an encoding
   symbol ID is orders of magnitude larger than the number of source
symbols in a block, i.e., on the range of possible values is gen-
   erally in the billions.  The block number and the encoding symbol ID
   are both chosen uniformly and randomly from together with their range when an
   encoding symbol is to be generated and transmitted.    For example,
   suppose the number of source symbols is 64,000 and the number of
   blocks is 2.  Then, each packet generated by the LT encoder could be
   of the form (b, x: y). identifiers are

    (0, 0, 1: a), (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 4, 1: e),
    (0, 0, 0: p), (0, 1, 0: q), (0, 2, 0: r),

    (1, 0, 1: f), (1, 1, 1: g), (1, 2, 1: h), (1, 3, 1: i), (1, 4, 1: j),
    (1, 0, 0: x), (1, 1, 0: y), (1, 2, 0: z).

In this example, the first two three fields iden-
   tify identify the encoding symbol,
where the first field is the block number b
   = 0 or 1 and number, the second field is the randomly chosen encoding
symbol ID x. The value y after and the colon third field is the encoding flag. The value of the
encoding sym-
   bol.

3. Passing FEC coding information to receivers

   There are two basic methods for passing FEC coding information to
   receivers in order to decode an object: within the IP multicast
   packet headers or through out of band methods.  A description of the
   variety of out of band methods symbol is outside written after the scope of this document.
   The FEC coding information colon.  Each block can be classified as three types. FEC ses-
   sion information is information needed by recovered
from any 5 of the FEC decoder 8 encoding symbols associated with that may
   remain fixed for the transmission block.  For
example, reception of many objects. FEC object
   transmission information is information particular (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 0,
0: p) and (0, 1, 0: q) are sufficient to recover the object
   transmission session needed by the FEC decoder.  The FEC payload ID
   identifies the symbols in the payload first source block
and reception of (1, 0, 1: f), (1, 1, 1: g), (1, 0, 0: x), (1, 1, 0: y)
and (1, 2, 0: z) are sufficient to recover the ALC packet.

   FEC coding information include the FEC codec type, the second source block.

2.3.  Large block
   length, the symbol length, the object length, the encoding FEC codes

Tornado codes [LUB97] are block
   number, the encoding symbol ID, and FEC codes that provide an alternative to
small block FEC codes.  A (n, k) Tornado code requires slightly more
than k out of n encoding flag indicating
   whether the encoding symbol is a symbols to reassemble k source symbol or a redundant symbol.
   The FEC codec type, symbols.
However, the source block length and advantage is that the symbol length are
   often FEC session information, although they value of k may classified as FEC
   object transmission information for some protocols.  Thus, sometimes
   this information be on the order of
tens of thousands and still run efficiently.  Because of memory
considerations, in practice the value of n is passed restricted to be a small
multiple of k, e.g., n = 2k.  For example, [BYE98] describes an
implementation of Tornado codes where the receiver out encoding and decoding speeds
are tens of band, although they
   can equally well be included megabytes per second range for Pentium class machines of
various vintages when k is in each IP multicast packet header as
   long as the amount tens of space they take within each packet is minimal. thousands and n = 2k.  The object length
reception overhead for such values of k and n is part in the 5-10% range.
Tornado codes require a large amount of FEC out of band information to be
communicated to all senders and receivers for each different object transmission information.
   Depending

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

length, and require an amount of memory on the protocol, encoder and decoder which
is proportional to the object length is passed times 2n/k.

Tornado codes are designed to the
   receiver out have low reception overhead on average
with respect to reception of band or included within each IP multicast packet
   header.  The FEC payload ID consists a random portion of the encoding block number (if
   used), packets.
Thus, to ensure that a receiver can reassemble the encoding symbol ID and object with low
reception overhead, the encoding flag.  The packets are permuted into a random order before
transmission.

2.4.  Expandable FEC payload
   ID must be contained within each IP multicast packet header.

4. Security Considerations

   The use of FEC, in and codes

All of itself, imposes no additional security con-
   siderations versus sending the same information without FEC.  How-
   ever, just like for any transmission system, FEC codes described up to this point are block codes.  There
is a malicious sender may
   intentionally transmit bad different type of FEC codes that we call expandable FEC codes.
Like block codes, an expandable FEC encoder operates on an object of
known size that is partitioned into equal length source symbols. If a receiver accepts one  Unlike
block codes, ideally there is no predetermined number of encoding
symbols that can be generated for expandable FEC codes. Instead, an
expandable FEC encoder can generate as few or more
   bad as many unique encoding
symbols in place of authentic ones then such a receiver will as required on demand. Also unlike block codes, optimal
expandable FEC codes have
   its entire object down-load corrupted by the bad symbol.
   Application-level transmission additional attractive property that
encoding symbols for the same object authentication can detect the
   corrupted transfer, but the be generated and transmitted
from multiple servers and concurrently received by a receiver must then discard and yet
the
   transferred object. Thus, transmitting false symbols is at least an
   effective denial of service attack. At worst, receiver incurs a malicious sender
   could add, delete, or replace arbitrary data within the transmitted
   object.

   In light 0% reception overhead.

LT codes [LUB00] are an example of this possibility, large expandable FEC receivers may screen the source
   address of a received codes.  An LT
encoder uses randomization to generate each encoding symbol against a list randomly and
independently of all other encoding symbols.  Like Tornado codes, the
number of authentic transmitter
   addresses.  Since source addresses symbols k may be spoofed, FEC transport pro-
   tocols may provide mechanisms very large for robust source authentication LT codes, i.e., on the
order of
   each encoded symbol. Multicast routers along tens to hundreds of thousands, and the path encoder and decoder run
efficiently in software. For example the encoding and decoding speeds
for LT codes are in the range 3-20 megabytes per second for Pentium
class machines of a FEC
   transfer may provide various vintages when k is in the capability high tens of discarding multicast packets
   that originated
thousands.  An LT encoder closely approximates the properties of an
ideal expandable FEC encoder, as it can generate as few or as many
encoding symbols as required on demand.  When a new encoding symbol is
to be generated by an LT encoder, it is based on a randomly chosen
32-bit encoding symbol ID that subnet, uniquely describes how the encoding
symbol is to be generated from the input symbols. In general, each
encoding symbol ID value corresponds to a unique encoding symbol, and whose source IP address does not
   correspond with
thus the space of possible encoding symbols is approximately four
billion.  Thus, the chance that subnet.

5. Intellectual Property Disclosure

   Both Tornado codes and a particular encoding symbol is the same
as any other particular encoding symbol is tiny.  An LT codes have patents pending.

6. Acknowledgments

   Thanks to Vincent Roca decoder has the
property that with very high probability the receipt of any set of
slightly more than k randomly and Hayder Radha for their detailed comments independently generated encoding

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

symbols is sufficient to reassemble the k source symbols.  For example,
when k is on this draft.

7. References

   [AFZ95] Acharya, S., Franklin, the order of tens to hundreds of thousands the reception
overhead is less than 5% with no failures in tens of millions of trials
under a variety of loss conditions.

Because encoding symbols are randomly and independently generated by
choosing random encoding symbol IDs, LT codes have the property that
encoding symbols for the same k source symbols can be generated and
transmitted from multiple senders ad than if all the encoding symbols
were generated by a single sender.  The only requirement is that the
senders choose their encoding symbol IDs randomly and independently of
one another.

There is a weak tradeoff between the number of source symbols and the
reception overhead for LT codes, and the larger the number of source
symbols the smaller the reception overhead.  Thus, for shorter objects,
it is sometimes advantageous to include multiple symbols in each packet.
Normally, and in the discussion below, there is only one symbol per
packet.

There are a couple of factors for choosing the appropriate symbol
length/ number of input symbols tradeoff. The primary consideration is
that there is a fixed overhead per symbol component in the overall
processing requirements of the encoding and decoding, independent of the
number of input symbols.  Thus, using shorter symbols means that this
fixed overhead processing per symbol will be a larger component of the
overall processing requirements, leading to larger overall processing
requirements.  Because of this, it is advisable to use a reasonably
sized fixed symbol length independent of the length of the object, and
thus shorter objects will be partitioned into fewer symbols than larger
objects.  A second much less important consideration is that there is a
component of the processing per symbol that depends logarithmically on
the number of input symbols, and thus for this reason there is a slight
preference towards less input symbols.

Like small block codes, there is a point when the object is large enough
that it makes sense to partition it into blocks when using LT codes.
Generally the object is partitioned into blocks whenever the number of
source symbols times the packet payload length is less than the size of
the object.  Thus, if the packet payload is 1024 bytes and the number of
source symbols is 64,000 then any object over 64 megabytes will be
partitioned into more than one block.  One can choose the number of
source symbols to partition the object into, depending on the desired
encoding and decoding speed versus reception overhead tradeoff desired.
Encoding symbols can be uniquely identified by a block number (when the

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

object is large enough to be partitioned into more than one block) and
an encoding symbol ID.  The block numbers, if they are used, are
generally numbered consecutively starting from zero within the object.
The block number and the encoding symbol ID are both chosen uniformly
and randomly from their range when an encoding symbol is to be generated
and transmitted. For example, suppose the number of source symbols is
64,000 and the number of blocks is 2.  Then, each packet generated by
the LT encoder could be of the form (b, x: y).  In this example, the
first two fields identify the encoding symbol, where the first field is
the block number b = 0 or 1 and the second field is the randomly chosen
encoding symbol ID x. The value y after the colon is the value of the
encoding symbol.

2.5.  Source blocks with variable length source symbols

For all the FEC codes described above, all the source symbols in the
same source block are all of the same length.  In this section, we
describe a general technique to handle the case when it is desirable to
use source symbols of varying lengths in a single source block.  This
technique is applicable to block FEC codes.

Let l_1, l_2, ... , l_k be the lengths of k varying length source
symbols to be considered part of the same source block.  Let lmax be the
maximum over i = 1, ... , k of l_i.  To prepare the source block for the
FEC encoder, pad each source symbol i out to length lmax with a suffix
of lmax-i zeroes, and then prepend to the beginning of this the value
l_i.  Thus, each padded source symbol is of length x+lmax, assuming that
the length of an original symbol takes x bytes to store.  These padded
source symbols, each of length x+lmax, are the input to the encoder,
together with the value n.  The encoder then generates n-k redundant
symbols, each of length x+lmax.

The encoding symbols that are placed into packets consist of the
original k varying length source symbols and n-k redundant symbols, each
of length x+lmax.  >From any k of the received encoding symbols, the FEC
decoder recreates the k original source symbols as follows.  If all k
original source symbols are received, then no decoding is necessary.
Otherwise, at least one redundant symbol is received, from which the
receiver can easily whether the block was composed of variable-length
source symbols: if the redundant symbol(s) has a size different (larger)
from the source symbols then the source symbols are variable-length.
Note that in a variable-length block the redundant symbols are always
larger than the largest source symbol, due to the presence of the
encoded symbol-length.  The receiver can determine the value of lmax by

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

subtracting x from the length of a received redundant symbol. Note that
x MUST be a protocol constant.  For each of the received original source
symbols, the receiver can generate the corresponding padded source
symbol as described above.  Then, the input to the FEC decoder is the
set of received redundant symbols, together with the set of padded
source symbols constructed from the received original symbols.  The FEC
decoder then produces the set of k padded source symbols.  Once the k
padded source symbols have been recovered, the length l_i of original
source symbol i can be recovered from the first x bytes of the ith
padded source symbol, and then original source symbol i is obtained by
taking the next l_i bytes following the x bytes of the length field.

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

This section specify 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

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

       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 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 follow:

 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.

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

 2) Number of Repair Symbols

       This is the number of repair symbols requested, needed to recover
       the object.

3.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).

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

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

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" and "Number of Repair
Symbols".

3.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).

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

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

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

5.  Security Considerations

The use of FEC, in and of itself, imposes no additional security
considerations versus sending the same information without FEC.
However, just like for any transmission system, a malicious sender may
intentionally transmit bad symbols. If a receiver accepts one or more
bad symbols in place of authentic ones then such a receiver will have
its entire object down-load corrupted by the bad symbol.  Application-
level transmission object authentication can detect the corrupted
transfer, but the receiver must then discard the transferred object.
Thus, transmitting false symbols is at least an effective denial of
service attack. At worst, a malicious sender could add, delete, or
replace arbitrary data within the transmitted object.

In light of this possibility, FEC receivers may screen the source
address of a received symbol against a list of authentic transmitter
addresses.  Since source addresses may be spoofed, FEC transport

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

protocols may provide mechanisms for robust source authentication of
each encoded symbol. Multicast routers along the path of a FEC transfer
may provide the capability of discarding multicast packets that
originated on that subnet, and whose source IP address does not
correspond with that subnet.

6.  Intellectual Property Disclosure

Tornado codes [LUB97] have both patents issued and patents pending.  LT
codes [LUB00] have patents pending.

7.  Acknowledgments

Thanks to Vincent Roca and Hayder Radha for their detailed comments on
this draft.

8.  References

[AFZ95] Acharya, S., Franklin, M., and Zdonik, S., ``Dissemination-
Based Data Delivery Using Broadcast Disks'', IEEE Personal
Communications, pp.50-60, Dec 1995.

[BLA94] Blahut, R.E., ``Theory and Practice of Error Control Codes'',
Addison Wesley, MA 1984.

[BYE98] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., ``A
Digital Fountain Approach to Reliable Distribution of Bulk Data'',
Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998.

[DEE88] Deering, S., ``Host Extensions for IP Multicasting'', RFC
1058, Stanford University, Stanford, CA, 1988.

[GEM99] Gemmell, J., Schooler, E., and Gray, J., ``ALC Scalable
Multicast File Distribution: Caching and Parameters Optimizations''
Technical Report MSR-TR-99-14, Microsoft Research, Redmond, WA, April,
1999.

[HAN98] Handley, M., and Jacobson, V., ``SDP: Session Description
Protocol'', RFC 2327, April 1998.

[HAN96] Handley, M., ``SAP: Session Announcement Protocol'', Internet
Draft, IETF MMUSIC Working Group, Nov 1996.

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

[LUB97] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D.,
Stemann, V., ``Practical Loss-Resilient Codes'' 29th STOC'97.

[LUB99] Luby, M., Vicisano, L., Speakman, T. ``Heterogeneous multicast
congestion control based on router packet filtering'', presented at
RMT meeting in Pisa, March 1999.

[LUB00] Luby, M., "An overview of LT codes", Digital Fountain white paper,
July 2000.

[R2068] Fielding, R., Gettys, J., Mogul, J. Frystyk, H., Berners-Lee,
T., Hypertext Transfer Protocol  HTTP/1.1 (IETF RFC2068)
http://www.rfc-editor.org/rfc/rfc2068.txt

[R2119] Bradner, S., Key words for use in RFCs to Indicate Requirement
Levels (IETF RFC 2119) http://www.rfc-editor.org/rfc/rfc2119.txt

[RIZ97a]  Rizzo, L, and Vicisano, L., ``Reliable Multicast Data
Distribution protocol based on software FEC techniques'', Proceedings techniques'', Proceedings
of the Fourth IEEE Workshop on the Architecture and Implementation of
High Performance Communication Systems, HPCS-97, Chalkidiki, Greece,
June 1997.

[RIZ97b]  Rizzo, L., and Vicisano, L., ``Effective Erasure Codes for
Reliable Computer Communication Protocols'', ACM SIGCOMM Computer
Communication Review, Vol.27, No.2, pp.24-36, Apr 1997.

[RIZ97c]  Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech
Report, http://www.iet.unipi.it/ luigi/softfec.ps, Jan 1997.

[RUB99] Rubenstein, Dan, Kurose, Jim and Towsley, Don, ``The Impact of
Multicast Layering on Network Fairness'', Proceedings of ACM SIGCOMM'99.

[VIC98A]  L.Vicisano, L.Rizzo, J.Crowcroft, ``TCP-like Congestion
Control for Layered Multicast Data Transfer'', IEEE Infocom '98, San
Francisco, CA, Mar.28-Apr.1 1998.

[VIC98B]  Vicisano, L., ``Notes On a Cumulative Layered Organization
of Data Packets Across Multiple Streams with Different Rates'',
University College London Computer Science Research Note RN/98/25,
Work in Progress (May 1998).

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

A. Predefined FEC encoders

This appendix 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 encoding schemes. Others may be specified in
companion documents.

A.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 Fourth IEEES Workshop on encoding symbol(s) in the Architecture and Implementation payload of
   High Performance Communication Systems, HPCS-97, Chalkidiki, Greece,
   June 1997.

   [RIZ97b]  Rizzo, L., and Vicisano, L., ``Effective Erasure the
packet are source symbol(s) or redundant symbol(s).  The FEC Object
Transmission Information has the following structure:

Draft            RMT BB, Forward Error Correction Codes for
   Reliable Computer Communication Protocols'', ACM SIGCOMM Computer
   Communication Review, Vol.27, No.2, pp.24-36, Apr 1997.

   [RIZ97c]  Rizzo, L., ``On     13 July 2000

     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 Feasibility range of Software FEC'', DEIT Tech
   Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997.

   [RUB99] Rubenstein, Dan, Kurose, Jim and Towsley, Don, ``The Impact possible FEC Encoding Names
to 0-:-65536, despite the FEC Object Transmission Information can also
be transmitted out of
   Multicast Layering on Network Fairness'', Proceedings band.

The Object Length, composed of ACM SIGCOMM'99.

   [VIC98A]  L.Vicisano, L.Rizzo, J.Crowcroft, ``TCP-like Congestion
   Control for Layered Multicast Data Transfer'', IEEE Infocom '98, San
   Francisco, CA, Mar.28-Apr.1 1998.

   [VIC98B]  Vicisano, L., ``Notes On a Cumulative Layered Organization Most Significant Bytes portion (MSB)
and a Least Significant Bytes portion (LSB), is expressed in bytes.

Feedback packet MUST contain both FEC Block Identifier and Number of
Repair Symbols. Their structure 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                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     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 Data Packets Across Multiple Streams with Different Rates'',
   University College London Computer Science Research Note RN/98/25,
   Work in Progress (May 1998).

8. Repair Symbols                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

9.  Authors' Addresses

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

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

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

   Luigi Rizzo
   luigi@iet.unipi.it
   Dip. di Ing. dell'Informazione
   Universita` di Pisa
   via Diotisalvi 2, 56126 Pisa, Italy

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

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

   Bruce Lueckenhoff
   brucelu@cadence.com
   Cadence Design Systems, Inc.
   120 Cremona Drive, Suite C
   Santa Barbara, CA 93117

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

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

Draft            RMT BB, Forward Error Correction Codes     13 July 2000

Table of Contents

1 Rationale and Overview ..........................................    2
1.1 Application of FEC codecs .....................................    4
2 FEC Codes .......................................................    6
2.1 Simple codes ..................................................    6
2.2 Small block FEC codes .........................................    7
2.3 Large block FEC codes .........................................   10
2.4 Expandable FEC codes ..........................................   11
2.5 Source blocks with variable length source symbols .............   13
3 FEC Abstract Packet Fields and Out-of-Band Information ..........   14
3.1 FEC Encoding Identifier .......................................   16
3.2 FEC Payload ID and FEC Object Transmission Information ........   17
4 IANA Considerations .............................................   17
5 Security Considerations .........................................   18
6 Intellectual Property Disclosure ................................   19
7 Acknowledgments .................................................   19
8 References ......................................................   19
 A. Predefined FEC encoders .......................................   21
 A.1. Small Block, Large Block and Expandable FEC Codes ...........   21
9 Authors' Addresses ..............................................   22
10 Full Copyright Statement .......................................   24