Internet DRAFT - draft-luby-uod-raptorq
draft-luby-uod-raptorq
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]