doc: Add RFC documents

1 files changed, 1011 insertions, 0 deletions

diff --git a/doc/rfc/rfc3453.txt b/doc/rfc/rfc3453.txt
new file mode 100644
index 0000000..93c5dcd
--- /dev/null
+++ b/doc/rfc/rfc3453.txt
@@ -0,0 +1,1011 @@
+
+
+
+
+
+
+Network Working Group                                            M. Luby
+Request for Comments: 3453                              Digital Fountain
+Category: Informational                                      L. Vicisano
+                                                                   Cisco
+                                                              J. Gemmell
+                                                               Microsoft
+                                                                L. Rizzo
+                                                              Univ. Pisa
+                                                              M. Handley
+                                                                    ICIR
+                                                            J. Crowcroft
+                                                         Cambridge Univ.
+                                                           December 2002
+
+
+    The Use of Forward Error Correction (FEC) in Reliable Multicast
+
+Status of this Memo
+
+   This memo provides information for the Internet community.  It does
+   not specify an Internet standard of any kind.  Distribution of this
+   memo is unlimited.
+
+Copyright Notice
+
+   Copyright (C) The Internet Society (2002).  All Rights Reserved.
+
+Abstract
+
+   This memo describes the use of Forward Error Correction (FEC) codes
+   to efficiently provide and/or augment reliability for one-to-many
+   reliable data transport using IP multicast.  One of the key
+   properties of FEC codes in this context is the ability to use the
+   same packets containing FEC data to simultaneously repair different
+   packet loss patterns at multiple receivers.  Different classes of FEC
+   codes and some of their basic properties are described and
+   terminology relevant to implementing FEC in a reliable multicast
+   protocol is introduced.  Examples are provided of possible abstract
+   formats for packets carrying FEC.
+
+
+
+
+
+
+
+
+
+
+
+
+Luby, et. al.                Informational                      [Page 1]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+Table of Contents
+
+   1. Rationale and Overview . . . . . . . . . . . . . . . . . . . .   2
+     1.1. Application of FEC codes . . . . . . . . . . . . . . . . .   5
+   2. FEC Codes. . . . . . . . . . . . . . . . . . . . . . . . . . .   6
+     2.1. Simple codes . . . . . . . . . . . . . . . . . . . . . . .   6
+     2.2. Small block FEC codes. . . . . . . . . . . . . . . . . . .   8
+     2.3. Large block FEC codes. . . . . . . . . . . . . . . . . . .  10
+     2.4. Expandable FEC codes . . . . . . . . . . . . . . . . . . .  11
+     2.5. Source blocks with variable length source symbols. . . . .  13
+   3. Security Considerations. . . . . . . . . . . . . . . . . . . .  14
+   4. Intellectual Property Disclosure . . . . . . . . . . . . . . .  14
+   5. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . .  15
+   6. References . . . . . . . . . . . . . . . . . . . . . . . . . .  15
+   7. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . .  17
+   8. Full Copyright Statement . . . . . . . . . . . . . . . . . . .  18
+
+1.  Rationale and Overview
+
+   There are many ways to provide reliability for transmission
+   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
+   success of TCP/IP.  ARQ has also been an effective reliability tool
+   for one-to-many reliability protocols, and in particular for some
+   reliable IP multicast protocols.  However, for one-to-very-many
+   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
+   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
+   channel at all, such as satellite transmission, a Data Carousel
+   approach to reliability is sometimes used [1].  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 limitations.  For example,
+
+
+
+Luby, et. al.                Informational                      [Page 2]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   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.
+
+   Forward Error Correction (FEC) codes provide a reliability method
+   that can be used to augment or replace other reliability methods,
+   especially for one-to-many reliability protocols such as reliable IP
+   multicast.  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.  Later, we provide a more detailed description
+   of some of FEC codes.
+
+   In the general literature, FEC refers to the ability to overcome both
+   erasures (losses) and bit-level corruption.  However, in the case of
+   an IP multicast protocol, the network layers will detect corrupted
+   packets and discard them or the transport layers can use packet
+   authentication to discard corrupted packets.  Therefore the primary
+   application of FEC codes to IP multicast protocols is as an erasure
+   code.  The payloads are generated and processed using an FEC erasure
+   encoder and objects are reassembled from reception of packets
+   containing the generated encoding using the 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 encoding symbols
+   that are of the same length as the source symbols.  The chosen length
+   of the symbols can vary upon each application of the FEC encoder, or
+   it can be fixed.  These encoding symbols are placed into packets for
+   transmission.  The number of encoding symbols placed into each packet
+   can vary on a per packet basis, or a fixed number of symbols (often
+   one) can be placed into each packet.  Also, in each packet is placed
+   enough information to identify the particular encoding symbols
+   carried in that packet.  Upon receipt of packets containing encoding
+   symbols, the receiver feeds these encoding symbols into the
+   corresponding FEC decoder to recreate an exact copy of the k source
+   symbols.  Ideally, the FEC decoder can recreate an exact copy from
+   any k of the encoding symbols.
+
+   In a later section, we describe a technique for using FEC codes as
+   described above to handle blocks with variable length source symbols.
+
+   Block FEC codes work as follows.  The input to a block FEC encoder is
+   k source symbols and a number n.  The encoder generates a total of n
+   encoding symbols.  The encoder is systematic if it generates n-k
+   redundant symbols yielding an encoding block of n encoding symbols in
+   total composed of the k source symbols and the n-k redundant symbols.
+
+
+
+Luby, et. al.                Informational                      [Page 3]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   A block FEC decoder has the property that any k of the n encoding
+   symbols in the encoding block is sufficient to reconstruct the
+   original k source symbols.
+
+   Expandable FEC codes work as follows.  An expandable FEC encoder
+   takes as input k source symbols and generates as many unique encoding
+   symbols as requested on demand, where the amount of time for
+   generating each encoding symbol is the same independent of how many
+   encoding symbols are generated.  An expandable FEC decoder has the
+   property that any k of the unique encoding symbols is sufficient to
+   reconstruct the original k source symbols.
+
+   The above definitions explain the ideal situation when the reception
+   of any k encoding symbols is sufficient to recover the k source
+   symbols, in which case the reception overhead is 0%.  For some
+   practical FEC codes, slightly more than k encoding symbols are needed
+   to recover the k source symbols.  If k*(1+ep) encoding symbols are
+   needed, we say the reception overhead is ep*100%, e.g., if k*1.05
+   encoding symbols are needed then the reception overhead is 5%.
+
+   Along a different dimension, we classify FEC codes loosely as being
+   either small or large.  A small FEC code is efficient in terms of
+   processing time requirements for encoding and decoding for small
+   values of k, and a large FEC code is efficient for encoding and
+   decoding for much large values of k.  There are implementations of
+   block FEC codes that have encoding times proportional to n-k times
+   the length of the k source symbols, and decoding times proportional
+   to l times the length of the k source symbols, where l is the number
+   of missing source symbols among the k received encoding symbols and l
+   can be as large as k.  Because of the growth rate of the encoding and
+   decoding times as a product of k and n-k, these are typically
+   considered to be small block FEC codes.  There are block FEC codes
+   with a small reception overhead that can generate n encoding symbols
+   and can decode the k source symbols in time proportional to the
+   length of the n encoding symbols.  These codes are considered to be
+   large block FEC codes.  There are expandable FEC codes with a small
+   reception overhead that can generate each encoding symbol in time
+   roughly proportional to its length, and can decode all k source
+   symbols in time roughly proportional to their length.  These are
+   considered to be large expandable FEC codes.  We describe examples of
+   all of these types of codes later.
+
+   Ideally, FEC codes in the context of IP multicast can be used to
+   generate encoding symbols that are transmitted in packets in such a
+   way that each received packet is fully useful to a receiver to
+   reassemble the object regardless of previous packet reception
+   patterns.  Thus, if some packets are lost in transit between the
+   sender and the receiver, instead of asking for specific
+
+
+
+Luby, et. al.                Informational                      [Page 4]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   retransmission of the lost packets or waiting till the packets are
+   resent using Data Carousel, the receiver can use any other subsequent
+   equal number of packets that arrive to reassemble the object.  These
+   packets can either be proactively transmitted or they can be
+   explicitly requested by receivers.  This implies that the same packet
+   is fully useful to all receivers to reassemble the object, even
+   though the receivers may have previously experienced different packet
+   loss patterns.  This property can reduce or even eliminate the
+   problems mentioned above associated with ARQ and Data Carousel and
+   thereby dramatically increase the scalability of the protocol to
+   orders of magnitude more receivers.
+
+1.1.  Application of FEC codes
+
+   For some reliable IP multicast protocols, FEC codes are used in
+   conjunction with ARQ to provide reliability.  For example, a large
+   object could be partitioned into a number of source blocks consisting
+   of a small number of source symbols each, and in a first round of
+   transmission all of the source symbols for all the source blocks
+   could be transmitted.  Then, receivers could report back to the
+   sender the number of source symbols they are missing from each source
+   block.  The sender could then compute the maximum number of missing
+   source symbols from each source block among all receivers.  Based on
+   this, a small block FEC encoder could be used to generate for each
+   source block a number of redundant symbols equal to the computed
+   maximum number of missing source symbols from the block among all
+   receivers, as long as this maximum maximum for each block does not
+   exceed the number of redundant symbols that can be generated
+   efficiently.  In a second round of transmission, the server would
+   then send all of these redundant symbols for all blocks.  In this
+   example, if there are no losses in the second round of transmission
+   then all receivers will be able to recreate an exact copy of each
+   original block.  In this case, even if different receivers are
+   missing different symbols in different blocks, transmitted redundant
+   symbols for a given block are useful to all receivers missing symbols
+   from that block in the second round.
+
+   For other reliable IP multicast protocols, FEC codes are 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 considering all the k source symbols of an object
+   as one block.  The sender cycles through and transmits the n encoding
+   symbols in packets in the same order in each round.  An FEC Data
+   Carousel can have much better protection against packet loss than a
+   Data Carousel.  For example, a receiver can join the transmission at
+   any point in time, and, as long as the receiver receives at least k
+   encoding symbols during the transmission of the next n encoding
+
+
+
+Luby, et. al.                Informational                      [Page 5]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   symbols, 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.  This method can also be used when
+   the object is partitioned into blocks and a short block FEC code is
+   applied to each block separately.  In this case, as we explain in
+   more detail below, it is useful to interleave the symbols from the
+   different blocks when they are transmitted.
+
+   Since any number of encoding symbols can be generated using an
+   expandable FEC encoder, reliable IP multicast protocols that use
+   expandable FEC codes generally rely solely on these codes for
+   reliability.  For example, when an expandable FEC code is used in a
+   FEC Data Carousel application, the encoding packets never repeat, and
+   thus any k of the encoding symbols in the potentially unbounded
+   number of encoding symbols are sufficient to recover the original k
+   source symbols.
+
+   For additional reliable IP multicast protocols, the method to obtain
+   reliability is to generate enough encoding symbols so that each
+   encoding symbol is transmitted only once (at most).  For example, the
+   sender can decide a priori how many encoding symbols it will
+   transmit, use an FEC code to generate that number of encoding symbols
+   from the object, and then transmit the encoding symbols to all
+   receivers.  This method is applicable to streaming protocols, for
+   example, where the stream is partitioned into objects, the source
+   symbols for each object are encoded into encoding symbols using an
+   FEC code, and then the sets of encoding symbols for each object are
+   transmitted one after the other using IP multicast.
+
+2.  FEC Codes
+
+2.1.  Simple codes
+
+   There are some very simple codes that are effective for repairing
+   packet loss under very low loss conditions.  For example, to provide
+   protection from a single loss is to partition the object into fixed
+   size source symbols and then add a redundant symbol that is the
+   parity (XOR) of all the source symbols.  The size of a source symbol
+   is chosen so that it fits perfectly into the payload 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 to
+   identify the payload.  This is an example of encoding symbol ID.  The
+   encoding symbol IDs can consist of two parts in this example.  The
+   first part is an encoding flag that is equal to 1 if the encoding
+   symbol is a source symbol and is equal to 0 if the encoding symbol is
+   a redundant symbol.  The second part of the encoding symbol ID is a
+   source symbol ID if the encoding flag is 1 and a redundant symbol ID
+   if the encoding flag is 0.  The source symbol IDs can be numbered
+
+
+
+Luby, et. al.                Informational                      [Page 6]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   from 0 to k-1 and the redundant symbol ID can be 0.  For example, if
+   the object consists of four source symbols that have values a, b, c
+   and d, then the value of the redundant symbol is e = a XOR b XOR c
+   XOR d.  Then, the packets carrying these symbols look like:
+
+            (1, 0: a), (1, 1: b), (1, 2: c), (1, 3: d), (0, 0: e).
+
+   In this example, the encoding symbol ID consists of the first two
+   values, where the first value is the encoding flag and the second
+   value is either a source symbol ID or the redundant symbol ID.  The
+   portion of the packet after the colon is the value of the encoding
+   symbol.  Any single source symbol of the object can be recovered as
+   the parity of all the other symbols.  For example, if packets
+
+                  (1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e)
+
+   are received then the missing source symbol value with source symbol
+   ID = 2 can be recovered by computing a XOR b XOR d XOR e = c.
+
+   Another way of forming the encoding symbol ID is to let values
+   0,...,k-1 correspond to the k source symbols and value k correspond
+   to the redundant symbol that is the XOR of the k source symbols.
+
+   When the number of source symbols in the object is large, a simple
+   block code variant of the above can be used.  In this case, the
+   source symbols are grouped together into source blocks of some number
+   k of consecutive symbols each, where k may be different for different
+   blocks.  If a block consists of k source symbols then a redundant
+   symbol is added to form an encoding block consisting of k+1 encoding
+   symbols.  Then, a source block consisting of k source symbols can be
+   recovered from any k of the k+1 encoding symbols from the associated
+   encoding block.
+
+   Slightly more sophisticated ways of adding redundant symbols using
+   parity can also be used.  For example, one can group a block
+   consisting of k source symbols in an object into a p x p square
+   matrix, where p = sqrt(k).  Then, for each row a redundant symbol is
+   added that is the parity of all the source symbols in the row.
+   Similarly, for each column a redundant symbol is added that is the
+   parity of all the source symbols in the column.  Then, any row of the
+   matrix can be recovered from any p of the p+1 symbols in the row, and
+   similarly 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 to
+   obtain is that if k source symbols are encoded into n encoding
+   symbols (the encoding symbols consist of the source symbols and the
+   redundant symbols) then the k source symbols can be recovered from
+
+
+
+Luby, et. al.                Informational                      [Page 7]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   any k of the n encoding symbols.  Using the simple constructions
+   described above does not yield codes that come close to obtaining
+   this ideal behavior.
+
+2.2.  Small block FEC codes
+
+   Reliable IP multicast protocols may use a block (n, k) FEC code [2].
+   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.  Thus, these codes have no
+   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 and n-k redundant symbols
+   generated from these k source symbols, where the size of a redundant
+   symbol is the same as that for a source symbol.  For example, the
+   first simple code (XOR) described in the previous subsection is a
+   (k+1, k) code.  In general, the freedom to choose n larger than k+1
+   is desirable, as this can provide much better protection against
+   losses.  A popular example of these types of codes is a class of
+   Reed-Solomon codes, which are based on algebraic methods using finite
+   fields.  Implementations of (n, k) FEC erasure codes are efficient
+   enough to be used by personal computers [16].  For example, [15]
+   describes an implementation where the encoding and decoding speeds
+   decay as C/j, where the constant C is on the order of 10 to 80
+   Mbytes/second for Pentium class machines of various vintages and j is
+   upper bounded by min(k, n-k).
+
+   In practice, the values of k and n must be small (for example below
+   256) for such FEC codes as large values make encoding and decoding
+   prohibitively expensive.  As many objects are longer than k symbols
+   for reasonable values of k and the symbol length (e.g. larger than 16
+   kilobyte for k = 16 using 1 kilobyte symbols), they can be divided
+   into a number of source blocks.  Each source block consists of some
+   number k of source symbols, where k may vary between different source
+   blocks.  The FEC encoder is used to encode a k source symbol source
+   block into a n encoding symbol encoding block, where the number n of
+   encoding symbols in the encoding block may vary for each source
+   block.  For a receiver to completely recover the object, for each
+   source block consisting of k source symbols, k distinct encoding
+   symbols (i.e., with different encoding symbol IDs) must be received
+   from the corresponding encoding block.  For some encoding blocks,
+   more encoding symbols may be received than there are source symbols
+   in the corresponding source block, in which case the excess encoding
+   symbols are discarded.  An example encoding structure is shown in
+   Figure 1.
+
+
+
+
+
+
+Luby, et. al.                Informational                      [Page 8]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+       |   source symbol IDs   |   source symbols IDs  |
+       |   of 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 encoder
+                               |
+                               v
+   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+   |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
+   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+                  ^                             ^
+                  |                             |
+   |  encoding symbol IDs        | encoding symbol IDs         |
+   |  of encoding block 0        | of encoding block 1         |
+
+   Figure 1. The encoding structure for an object divided into two
+   source blocks consisting of 8 source symbols each, and the FEC
+   encoder is used to generate 2 additional redundant symbols (10
+   encoding symbols in total) for each of the two source blocks.
+
+   In many cases, an object is partitioned into equal length source
+   blocks each consisting of k contiguous source symbols of the object,
+   i.e., block c consists of the range of source symbols [ck, (c+1)k-1].
+   This ensures 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 when the receiver reads encoding symbols to decode.  Locality of
+   reference is particularly important when the object is stored on
+   disk, as it reduces the disk seeks required.  The block number and
+   the source symbol ID within that block can be used to uniquely
+   specify a source symbol within the object. If the size of the object
+   is not a multiple of k source symbols, then the last source block
+   will contain less than k symbols.
+
+   The block numbers can be numbered consecutively starting from zero.
+   Encoding symbols within a block can be uniquely identified by an
+   encoding symbol ID.  One way of identifying encoding symbols within a
+   block is to use the combination of an encoding flag that identifies
+   the symbol as either a source symbol or a redundant symbol together
+   with either a source symbol ID or a redundant symbol ID.  For
+   example, an encoding flag value of 1 can indicate that the encoding
+   symbol is a source symbol and 0 can indicate that it is a redundant
+   symbol.  The source symbol IDs can be numbered from 0 to k-1 and the
+   redundant symbol IDs can be numbered from 0 to n-k-1.
+
+
+
+Luby, et. al.                Informational                      [Page 9]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   For example, if the object consists 10 source symbols with values a,
+   b, c, d, e, f, g, h, i, and j, and k = 5 and n = 8, then there are
+   two source blocks consisting of 5 symbols each, and there are two
+   encoding blocks consisting of 8 symbols each.  Let p, q and r be the
+   values of the redundant symbols for the first encoding block, and let
+   x, y and z be the values of the redundant symbols for the second
+   encoding block.  Then the encoding symbols together with their
+   identifiers are
+
+   (0, 1, 0: a), (0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 1, 4: e),
+   (0, 0, 0: p), (0, 0, 1: q), (0, 0, 2: r),
+   (1, 1, 0: f), (1, 1, 1: g), (1, 1, 2: h), (1, 1, 3: i), (1, 1, 4: j),
+   (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z).
+
+   In this example, the first value identifies the block number and the
+   second two values together identify the encoding symbol within the
+   block, i.e, the encoding symbol ID consists of the encoding flag
+   together with either the source symbol ID or the redundant symbol ID
+   depending on the value of the encoding flag.  The value of the
+   encoding symbol is written after the colon.  Each block can be
+   recovered from any 5 of the 8 encoding symbols associated with that
+   block.  For example, reception of
+
+    (0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 0, 0: p), (0, 0, 1: q)
+
+   is sufficient to recover the first source block, and reception of
+
+    (1, 1, 0: f), (1, 1, 1: g), (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z)
+
+   is sufficient to recover the second source block.
+
+   Another way of uniquely identifying encoding symbols within a block
+   is to let the encoding symbol IDs for source symbols be 0,...,k-1 and
+   to let the encoding symbol IDs for redundant symbols be k,...,n-1.
+
+2.3.  Large block FEC codes
+
+   Tornado codes [12], [13], [10], [11], [9] are large block FEC codes
+   that provide an alternative to small block FEC codes.  An (n, k)
+   Tornado code requires slightly more than k out of n encoding symbols
+   to recover k source symbols, i.e., there is a small reception
+   overhead.  The benefit of the small cost of non-zero reception
+   overhead is that the value of k may be on the order of tens of
+   thousands and still the encoding and decoding are efficient.  Because
+   of memory considerations, in practice the value of n is restricted to
+   be a small multiple of k, e.g., n = 2k.  For example, [4] describes
+   an implementation of Tornado codes where the encoding and decoding
+   speeds are tens of megabytes per second for Pentium class machines of
+
+
+
+Luby, et. al.                Informational                     [Page 10]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   various vintages when k is in the tens of thousands and n = 2k.  The
+   reception overhead for such values of k and n is in the 5-10% range.
+   Tornado codes require a large amount of out of band information to be
+   communicated to all senders and receivers for each different object
+   length, and require an amount of memory on the encoder and decoder
+   which is proportional to the object 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
+   packets.  Thus, to ensure that a receiver can reassemble the object
+   with low reception overhead, the packets are permuted into a random
+   order before transmission.
+
+2.4.  Expandable FEC codes
+
+   All of the FEC codes described up to this point are block codes.
+   There is a 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.  Unlike block codes, 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 as many
+   unique encoding symbols as required on demand.
+
+   LT codes [6], [7], [8], [5] are an example of large expandable FEC
+   codes with a small reception overhead.  An LT encoder uses
+   randomization to generate each encoding symbol randomly and
+   independently of all other encoding symbols.  Like Tornado codes, the
+   number of source symbols k may be very large for LT codes, i.e., on
+   the order of tens to hundreds of thousands, and the 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 various vintages when k is in
+   the high tens of thousands.  An LT encoder 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 encoding symbol ID that uniquely describes how the encoding
+   symbol is to be generated from the source symbols. In general, each
+   encoding symbol ID value corresponds to a unique encoding symbol, and
+   thus the space of possible encoding symbols is approximately four
+   billion if for example the encoding symbol ID is 4 bytes.  Thus, the
+   chance that a particular encoding symbol is the same as any other
+   particular encoding symbol is inversely proportional to the number of
+   possible encoding symbol IDs.  An LT decoder has the property that
+   with very high probability the receipt of any set of slightly more
+   than k randomly and independently generated encoding symbols is
+   sufficient to reassemble the k source symbols.  For example, when k
+
+
+
+
+Luby, et. al.                Informational                     [Page 11]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   is on the order of tens to hundreds of thousands the reception
+   overhead is less than 5% with no failures in hundreds of millions of
+   trials under any 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 and received by a receiver and the
+   reception overhead and the decoding time is the same as if though 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 partition the object into
+   many short source symbols and include multiple encoding symbols in
+   each packet.  In this case, a single encoding symbol ID is used to
+   identify the multiple encoding symbols contained in a single packet.
+
+   There are a couple of factors for choosing the appropriate symbol
+   length/ number of source symbols tradeoff. The primary consideration
+   is that there is a fixed overhead per symbol in the overall
+   processing requirements of the encoding and decoding, independent of
+   the number of source 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.  A second much less important consideration
+   is that there is a component of the processing per symbol that
+   depends logarithmically on the number of source symbols, and thus for
+   this reason there is a slight preference towards fewer source
+   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 maximum number of source symbols is 128,000 then any object
+   over 128 megabytes will be partitioned into more than one block.  One
+   can choose the maximum number of source symbols to use, 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 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
+
+
+
+Luby, et. al.                Informational                     [Page 12]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   are both chosen uniformly and randomly from their range when an
+   encoding symbol is to be transmitted.  For example, suppose the
+   number of source symbols is 128,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 value identifies the block
+   number and the second value identifies the encoding symbol within the
+   block.  In this example, the block number b is either 0 or 1, and the
+   encoding symbol ID x might be a 32-bit value.  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 in bytes 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-l_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 it takes x bytes to store an integer
+   with possible values 0,...,lmax, where x is a protocol constant known
+   to both the encoder and the decoder.  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 determine if the block is composed
+   of variable- length source symbols: if the redundant symbol(s) is
+   longer than the source symbols then the source symbols are variable-
+   length.  Note that in a variable-length block the redundant symbols
+   are always longer than the longest source symbol, due to the presence
+   of the prepended symbol- length.  The receiver can determine the
+   value of lmax by subtracting x from the length of a received
+   redundant symbol.  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
+
+
+
+Luby, et. al.                Informational                     [Page 13]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   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.  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 try to inject packets carrying corrupted encoding symbols.  If a
+   receiver accepts one or more corrupted encoding symbol, in place of
+   authentic ones, then such a receiver may reconstruct a corrupted
+   object.
+
+   Application-level transmission object authentication can detect the
+   corrupted transfer, but the receiver must discard the transferred
+   object.  By injecting corrupted encoding symbols, they are accepted
+   as valid encoding symbols by a receiver, which at the very least, is
+   an effective denial of service attack.
+
+   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, transport
+   protocols using FEC may provide mechanisms for robust source
+   authentication of each encoding 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.
+
+   It is recommended that a packet authentication scheme such as TESLA
+   [14] be used in conjunction with FEC codes.  Then, packets that
+   cannot be authenticated can be discarded and the object can be
+   reliably recovered from the received authenticated packets.
+
+4.  Intellectual Property Disclosure
+
+   The IETF has been notified of intellectual property rights claimed in
+   regard to some or all of the specification contained in this
+   document.  For more information consult the online list of claimed
+   rights.
+
+
+
+
+
+
+
+Luby, et. al.                Informational                     [Page 14]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+5.  Acknowledgments
+
+   Thanks to Vincent Roca and Hayder Radha for their detailed comments
+   on this document.
+
+6.  References
+
+   [1]  Acharya, S., Franklin, M. and S. Zdonik, "Dissemination - Based
+        Data Delivery Using Broadcast Disks", IEEE Personal
+        Communications, pp.50-60, Dec 1995.
+
+   [2]  Blahut, R.E., "Theory and Practice of Error Control Codes",
+        Addison Wesley, MA, 1984.
+
+   [3]  Bradner, S., "The Internet Standards Process -- Revision 3", BCP
+        9, RFC 2026, October 1996.
+
+   [4]  Byers, J.W., Luby, M., Mitzenmacher, M. and A. Rege, "A Digital
+        Fountain Approach to Reliable Distribution of Bulk Data",
+        Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998.
+
+   [5]  Haken, A., Luby, M., Horn, G., Hernek, D., Byers, J. and M.
+        Mitzenmacher, "Generating high weight encoding symbols using a
+        basis", U.S. Patent No. 6,411,223, June 25, 2002.
+
+   [6]  Luby, M., "Information Additive Code Generator and Decoder for
+        Communication Systems", U.S. Patent No. 6,307,487, October 23,
+        2001.
+
+   [7]  Luby, M., "Information Additive Group Code Generator and Decoder
+        for Communication Systems", U.S. Patent No. 6,320,520, November
+        20, 2001.
+
+   [8]  Luby, M., "Information Additive Code Generator and Decoder for
+        Communication Systems", U.S. Patent No. 6,373,406, April 16,
+        2002.
+
+   [9]  Luby, M. and M. Mitzenmacher, "Loss resilient code with double
+        heavy tailed series of redundant layers", U.S. Patent No.
+        6,195,777, February 27, 2001.
+
+   [10] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D. and V.
+        Stemann, "Message encoding with irregular graphing", U.S. Patent
+        No. 6,163,870, December 19, 2000.
+
+
+
+
+
+
+
+Luby, et. al.                Informational                     [Page 15]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+   [11] Luby, M., Mitzenmacher, M., Shokrollahi, A. and D. Spielman,
+        "Efficient Erasure Correcting Codes", IEEE Transactions on
+        Information Theory, Special Issue: Codes on Graphs and Iterative
+        Algorithms, pp.  569-584, Vol. 47, No. 2, February 2001.
+
+   [12] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D.
+        Spielman, "Loss resilient decoding technique", U.S. Patent No.
+        6,073,250, June 6, 2000.
+
+   [13] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D.
+        Spielman, "Irregularly graphed encoding technique", U.S. Patent
+        No.  6,081,909, June 27, 2000.
+
+   [14] Perrig, A., Canetti, R., Song, D. and J.D. Tygar, "Efficient and
+        Secure Source Authentication for Multicast", Network and
+        Distributed System Security Symposium, NDSS 2001, pp. 35-46,
+        February 2001.
+
+   [15] Rizzo, L., "Effective Erasure Codes for Reliable Computer
+        Communication Protocols", ACM SIGCOMM Computer Communication
+        Review, Vol.27, No.2, pp.24-36, Apr 1997.
+
+   [16] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech
+        Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Luby, et. al.                Informational                     [Page 16]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+7.  Authors' Addresses
+
+   Michael Luby
+   Digital Fountain
+   39141 Civic Center Drive
+   Suite 300
+   Fremont, CA  94538
+
+   EMail: luby@digitalfountain.com
+
+   Lorenzo Vicisano
+   Cisco Systems, Inc.
+   170 West Tasman Dr.,
+   San Jose, CA, USA, 95134
+
+   EMail: lorenzo@cisco.com
+
+   Jim Gemmell
+   Microsoft Research
+   455 Market St. #1690
+   San Francisco, CA, 94105
+
+   EMail: jgemmell@microsoft.com
+
+   Luigi Rizzo
+   Dip. di Ing. dell'Informazione
+   Universita` di Pisa
+   via Diotisalvi 2, 56126 Pisa, Italy
+
+   EMail:luigi@iet.unipi.it
+
+   Mark Handley
+   ICSI Center for Internet Research
+   1947 Center St.
+   Berkeley CA, USA, 94704
+
+   EMail: mjh@icir.org
+
+   Jon Crowcroft
+   Marconi Professor of Communications Systems
+   University of Cambridge
+   Computer Laboratory
+   William Gates Building
+   J J Thomson Avenue
+   Cambridge
+   CB3 0FD
+
+   EMail: Jon.Crowcroft@cl.cam.ac.uk
+
+
+
+Luby, et. al.                Informational                     [Page 17]
+
+RFC 3453               FEC in Reliable Multicast           December 2002
+
+
+8.  Full Copyright Statement
+
+   Copyright (C) The Internet Society (2002).  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 Standards process must be
+   followed, or as required to translate it into 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.
+
+Acknowledgement
+
+   Funding for the RFC Editor function is currently provided by the
+   Internet Society.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Luby, et. al.                Informational                     [Page 18]
+