RMT                                                              M. Luby
Internet-Draft                                     Qualcomm Incorporated
Intended status:  Standards Track                         T. Stockhammer
Expires:  March 10, 2012                                  Nomor Research
                                                       September 7, 2011


                Universal Object Delivery using RaptorQ
                       draft-luby-uod-raptorq-01

Abstract

   This document describes a Fully-Specified FEC scheme, identified by
   the FEC Encoding ID 7 (to be determined (tbd)), for Universal Object
   Delivery using the RaptorQ Forward Error Correction (FEC) Scheme for
   Object Delivery.  This document introduces a new FEC Payload ID,
   called the Universal Object Symbol Identifier (UOSI), and describes
   how to use the UOSI together with RaptorQ FEC Scheme to provide
   simplified and enhanced object delivery capabilities.  In particular,
   flexible and simple support is provided for basic object delivery,
   and support is also provided for unequal error protection (UEP)
   object delivery, for bundled object delivery, and for any combination
   of UEP and bundled object delivery.

Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

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

   This Internet-Draft will expire on March 10, 2012.

Copyright Notice

   Copyright (c) 2011 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents



Luby & Stockhammer       Expires March 10, 2012                 [Page 1]

Internet-Draft          Universal Object Delivery         September 2011


   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  3
   3.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . . .  3
     3.1.  FEC Payload IDs  . . . . . . . . . . . . . . . . . . . . .  3
     3.2.  FEC Object Transmission Information  . . . . . . . . . . .  4
       3.2.1.  General  . . . . . . . . . . . . . . . . . . . . . . .  4
       3.2.2.  Mandatory  . . . . . . . . . . . . . . . . . . . . . .  4
       3.2.3.  Common . . . . . . . . . . . . . . . . . . . . . . . .  4
       3.2.4.  Scheme-Specific  . . . . . . . . . . . . . . . . . . .  5
   4.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . . .  6
     4.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . .  6
     4.2.  Content Delivery Protocol Requirements . . . . . . . . . .  6
     4.3.  Example Parameter Derivation Algorithm . . . . . . . . . .  7
     4.4.  Object Delivery  . . . . . . . . . . . . . . . . . . . . .  7
       4.4.1.  Source block construction  . . . . . . . . . . . . . .  7
       4.4.2.  Encoding packet construction . . . . . . . . . . . . .  7
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . .  9
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  9
   7.  References . . . . . . . . . . . . . . . . . . . . . . . . . .  9
     7.1.  Normative References . . . . . . . . . . . . . . . . . . .  9
     7.2.  Informative References . . . . . . . . . . . . . . . . . .  9
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10


















Luby & Stockhammer       Expires March 10, 2012                 [Page 2]

Internet-Draft          Universal Object Delivery         September 2011


1.  Introduction

   This document describes a Fully-Specified FEC scheme, identified by
   the FEC Encoding ID 7 (to be confirmed (tbc)), for Universal Object
   Delivery using the RaptorQ FEC Scheme specified in
   [I-D.ietf-rmt-bb-fec-raptorq], hereafter referred to as the UOD-
   RaptorQ FEC Scheme.  This document introduces a new FEC Payload ID,
   called the universal object symbol identifier (UOSI), and describes
   how to use the UOSI together with RaptorQ FEC Scheme
   [I-D.ietf-rmt-bb-fec-raptorq] to provide simplified and enhanced
   object delivery capabilities.  In particular, more flexible and
   simpler support is provided for basic object delivery when compared
   to the generic scheme defined in[I-D.ietf-rmt-bb-fec-raptorq], and
   support is also provided for unequal error protection (UEP) object
   delivery (for example as described in [PET]), for bundled object
   delivery, and for any combination of UEP and bundled object delivery.


2.  Requirements Notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].


3.  Formats and Codes

3.1.  FEC Payload IDs

   The FEC Payload ID MUST be a 4-octet field defined 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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |        Universal Object Symbol Identifier (UOSI)              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                      Figure 1: FEC Payload ID format

   o  Universal Object Symbol Identifier (UOSI), (32 bits, unsigned
      integer):  A non-negative integer that, in conjunction with the
      FEC Object Transmission Information (OTI), is used to identify the
      encoding symbols contained within the packet.

   The interpretation of the Universal Object Symbol Identifier is
   defined in Section 4.





Luby & Stockhammer       Expires March 10, 2012                 [Page 3]

Internet-Draft          Universal Object Delivery         September 2011


3.2.  FEC Object Transmission Information

3.2.1.  General

   For the delivery of a single object, or multiple objects, or a single
   object partitioned into parts with different priorities, or any
   combination of these, the FEC OTI is as described in this section.
   It should be noted that for each object delivered, the FEC OTI is
   exactly the same as specified in RaptorQ FEC Scheme
   [I-D.ietf-rmt-bb-fec-raptorq].  Each object described herein may be
   different for parts of the same file, or for different files, or
   combinations thereof.  The relationship between the size of object I,
   F(I), and the size of the encoding symbol to be used for object I,
   T(I), determines the priority of object I in the transmission.

3.2.2.  Mandatory

   The value of the FEC Encoding ID MUST be 7 (tbd), as assigned by IANA
   (see Section 6).

3.2.3.  Common

   The Common FEC Object Transmission Information elements used by this
   FEC Scheme are:

   o  Number of objects (D), (8 bits, unsigned integer):  A positive
      integer that is at most 255.  The number of objects delivered is
      D, i.e., if D = 1 then there is one object (default value).  D=0
      MUST NOT be used.

   o  For I = 1,...,D, the Common FEC OTI elements specific to object I
      are:

      *  Symbol Size (T(I)), (16 bits, unsigned integer):  A positive
         integer that is less than 2^^16.  This is the size of a symbol
         for object I in units of octets.

      *  Transfer Length (F(I)), (40 bits, unsigned integer):  A non-
         negative integer that is at most 2^^40.  This is the transfer
         length of object I in units of octets.

   The encoded Common FEC OTI format is shown in Figure 2 when D=2.









Luby & Stockhammer       Expires March 10, 2012                 [Page 4]

Internet-Draft          Universal Object Delivery         September 2011


        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |Num. obj. (D=2)|   Object 1 Symbol Size (T(1)) |    F(1)       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |             Object 1 Transfer Length (cont.) (F(1))           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Object 2 Symbol Size (T(2)  |Object 2 Transfer Length (F(2))|
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Object 2 Transfer Length (cont.) (F(2))   |    padding    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                 Figure 2: Encoded Common FEC OTI when D=2

3.2.4.  Scheme-Specific

   The following parameters are carried in the Scheme-Specific FEC OTI
   element for this FEC Scheme:

   o  A symbol alignment parameter (Al) (8 bits, unsigned integer)

   o  For I = 1,...,D, the Scheme-Specific FEC Object Transmission
      information elements specific to object I are:

      *  The number of source blocks for object I (Z(I)) (12 bits,
         unsigned integer)

      *  The number of sub-blocks for object I (N(I)) (12 bits, unsigned
         integer)

   These parameters are all positive integers.  The encoded Scheme-
   specific OTI is a (1+3*D)-octet field.  An example for D=2 is shown
   in Figure 3.

          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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |        Al     |          Z(1)         |           N(1)        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |          Z(2)         |           N(2)        |    padding    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            Figure 3: Encoded Scheme-specific FEC OTI when D=2

   The encoded FEC OTI is a (2+10*D)-octet field consisting of the
   concatenation of the encoded Common FEC OTI and the encoded Scheme-
   specific FEC OTI.




Luby & Stockhammer       Expires March 10, 2012                 [Page 5]

Internet-Draft          Universal Object Delivery         September 2011


4.  Procedures

4.1.  Introduction

   All notation used in the document has exactly the same interpretation
   and meaning as in RaptorQ FEC Scheme [I-D.ietf-rmt-bb-fec-raptorq].

4.2.  Content Delivery Protocol Requirements

   This section describes the information exchange between the UOD-
   RaptorQ FEC Scheme and any Content Delivery Protocol (CDP) that makes
   use of the UOD-RaptorQ FEC Scheme for object delivery.

   The UOD-RaptorQ encoder scheme and UOD-RaptorQ decoder scheme for
   object delivery require the following information from the CDP:

   o  The number of objects, D, to be transferred

   o  A symbol alignment parameter, Al

   o  For I = 1,...,D

      *  The transfer length of object I, F(I), in octets

      *  The symbol size to use for object I, T(I), in octets, which
         MUST be a multiple of Al

      *  The number of source blocks for object I, Z(I)

      *  The number of sub-blocks in each source block for object I,
         N(I)

   The UOD-RaptorQ encoder scheme for object delivery additionally
   requires:

   o  For I = 1,...,D, the object I to be encoded consisting of F(I)
      octets

   The UOD-RaptorQ encoder scheme supplies the CDP with the following
   information for each packet to be sent:

   o  Universal Object Symbol Identifier (UOSI)

   o  For I = 1,...,D, the encoding symbol(s) for object I

   The CDP MUST communicate this information to the receiver.





Luby & Stockhammer       Expires March 10, 2012                 [Page 6]

Internet-Draft          Universal Object Delivery         September 2011


4.3.  Example Parameter Derivation Algorithm

   For each object I, it is RECOMMENDED that the example parameter
   derivation algorithm described in Section 4.3 of the RaptorQ FEC
   Scheme [I-D.ietf-rmt-bb-fec-raptorq] be used, applied independently
   to each of the D objects.

   The following are RECOMMENDATIONS:

   o  Al = 4 octets

   o  SS = 8 (which implies that the each sub-symbol will be at least
      SS*Al = 32 octets)

   o  For each I = 1,...,D, the size of the encoding symbol T(I) for
      object I is RECOMMENDED to be least SS*Al octets.  (As stated
      earlier, T(I) MUST be a multiple of Al.)

   o  The payload size of each encoding packet is RECOMMENDED to be of
      size at least T, where T is the sum over I = 1,...,D of T(I).

4.4.  Object Delivery

4.4.1.  Source block construction

   Exactly the same procedures as specified in Section 4.4.1 of the
   RaptorQ FEC Scheme [I-D.ietf-rmt-bb-fec-raptorq] are to be applied
   independently to each of the D objects.

4.4.2.  Encoding packet construction

   Each encoding packet contains the following information:

   o  Universal Object Symbol Identifier (UOSI)

   o  For I = 1,...,D, the encoding symbol(s) for object I

   The following mappings provide the translations between the UOSI
   format used by the UOD-RaptorQ FEC Scheme and the (SBN, ESI) format
   of the FEC Payload ID used by the RaptorQ FEC Scheme
   [I-D.ietf-rmt-bb-fec-raptorq].

   For each object I = 1,...,D, the mapping from a UOSI value C to the
   corresponding (SBN, ESI) values (A,B) for object I is:

   o  B = floor(C/Z(I))





Luby & Stockhammer       Expires March 10, 2012                 [Page 7]

Internet-Draft          Universal Object Delivery         September 2011


   o  A = C - B*Z(I)

   Similarly, for each object I = 1,...,D, the mapping from (SBN, ESI)
   values (A,B) for object I to a corresponding UOSI value C is:

   o  C = A + B*Z(I)

   For each object I = 1,...,D, UOSI values from 0 to Kt(I)-1 identify
   the source symbols of object I in source block interleaved order,
   wherein Kt(I) = ceil(F(I)/T(I)).  UOSI values from Kt(I) onwards
   identify repair symbols generated from the source symbols of object I
   using the RaptorQ encoder.

   Each encoding packet may contain source symbols and repair symbols
   for objects.  For each object I = 1,...,D, a packet may contain
   multiple encoding symbols generated from the same source block of
   object I, which may be a mixture of source and repair symbols.  If
   the last source symbol of a source block includes padding octets
   added for FEC encoding purposes, then these octets MUST be included
   in any packet carrying this source symbol.  Thus, each packet MUST
   contain only full-sized encoding symbols generated from the objects.

   The UOSI, C, carried in each encoding packet is the UOSI of the first
   encoding symbol for each object carried in that packet.  The
   subsequent encoding symbols in the packet for each object have UOSIs,
   C+1 to C+G-1, in sequential order, where G is the number of encoding
   symbols for each object in the packet.

   It is RECOMMENDED that each encoding packet contain exactly one
   encoded symbol for each of the D objects.

   It is RECOMMENDED that encoding packets be generated and sent
   according to the following procedure:

   o  For each UOSI value C = 0, 1, 2, 3, ..., generate and send an
      encoding packet as follows:

      *  Set the value of the FEC Payload ID of the encoding packet to
         the UOSI value C.

      *  For I = 1,...,D,

         +  Determine the (SBN, ESI) values (A(I), B(I)) that correspond
            to UOSI value C.

         +  Generate the encoding symbol E(I) of size T(I) that
            corresponds to (SBN, ESI) values (A(I), B(I)) from object I
            according to the procedures of the RaptorQ FEC Scheme



Luby & Stockhammer       Expires March 10, 2012                 [Page 8]

Internet-Draft          Universal Object Delivery         September 2011


            [I-D.ietf-rmt-bb-fec-raptorq].

         +  Add encoding symbol E(I) to the payload of the encoding
            packet.

      *  Send the encoding packet.

   Note that it is not necessary for the receiver to know the total
   number of encoding packets.


5.  Security Considerations

   Exactly the same as for the RaptorQ FEC Scheme
   [I-D.ietf-rmt-bb-fec-raptorq] apply.


6.  IANA Considerations

   Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
   registration.  For general guidelines on IANA considerations as they
   apply to this document, see [RFC5052].  This document assigns the
   Fully-Specified FEC Encoding ID 7 (tbd) under the ietf:rmt:fec:
   encoding name-space to "UOD-RaptorQ Code".


7.  References

7.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [I-D.ietf-rmt-bb-fec-raptorq]
              Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T.,
              and L. Minder, "RaptorQ Forward Error Correction Scheme
              for Object Delivery", draft-ietf-rmt-bb-fec-raptorq-04
              (work in progress), August 2010.

   [RFC5052]  Watson, M., Luby, M., and L. Vicisano, "Forward Error
              Correction (FEC) Building Block", RFC 5052, August 2007.

7.2.  Informative References

   [PET]      Albanese, Blomer, Edmonds, Luby, and Sudan, "Priority
              Encoding Transmission", November 1996.





Luby & Stockhammer       Expires March 10, 2012                 [Page 9]

Internet-Draft          Universal Object Delivery         September 2011


Authors' Addresses

   Michael Luby
   Qualcomm Incorporated
   3165 Kifer Road
   Santa Clara, CA  95051
   U.S.A.

   Email:  luby@qualcomm.com


   Thomas Stockhammer
   Nomor Research
   Brecherspitzstrasse 8
   Munich  81541
   Germany

   Email:  stockhammer@nomor.de

































Luby & Stockhammer       Expires March 10, 2012                [Page 10]