FCAST: Scalable Object Delivery on top of the ALC Protocol
draft-roca-rmt-newfcast-01.txt

Status of this Memo

By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79.

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 “work in 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.

This Internet-Draft will expire on August 28, 2008.

Abstract

This document introduces the FCAST object (e.g. file) delivery application on top of the ALC reliable multicast protocols. FCAST is a highly scalable application that provides a reliable object delivery service.

Table of Contents

1.  Introduction
2.  Requirements notation
3.  Definitions, Notations and Abbreviations
    3.1.  Definitions
    3.2.  Abbreviations
4.  FCAST Specifications
    4.1.  Meta-Data Associated to Objects
    4.2.  Meta-Data Transmission
    4.3.  Object Transmissions Within a Carousel
5.  Control Information Formats
    5.1.  Object Meta-Data ALC/LCT Header Extension (EXT_OMD) Format
    5.2.  Object Trailer Format
    5.3.  Carousel Instance Object (CIO) Format
6.  Security Considerations
7.  Acknowledgments
8.  Normative References
§  Author's Address
§  Intellectual Property and Copyright Statements

1.  Introduction

This document introduces the FCAST reliable and scalable object (e.g. file) delivery application on top of the ALC reliable multicast protocols.

Since FCAST is built on top of ALC/LCT [draft‑ietf‑rmt‑pi‑alc‑revised] (Luby, M., Watson, M., and L. Vicisano, “Asynchronous Layered Coding (ALC) Protocol Instantiation,” February 2007.) [draft‑ietf‑rmt‑bb‑lct‑revised] (Luby, M., Watson, M., and L. Vicisano, “Layered Coding Transport (LCT) Building Block,” February 2007.), it inherits in particular the concepts of ``PUSH'' and ``ON-DEMAND'' delivery modes and the concept of Transport Object ID (TOI) that uniquely identifies the object(s) being transported in an ALC session.

Depending on the target use case, the delivery service that FCAST defines will be more or less reliable. For instance, when used in ON-DEMAND mode over a time period that largely exceeds the typical download time, the service can be considered as fully reliable. When FCAST is used along with a session control application capable of collecting reception information and taking appropriate corrective measures, then the service can be considered as fully reliable. But if FCAST operates in PUSH mode, for a time period that is close to the typical download time, then the service is usually only partially reliable.

Depending on the target use case, the FCAST scalability will be more or less important. For instance, if used on top of purely unidirectional transport channels, with no feedback information at all, which is the default mode of operation, then the scalability is maximum since neither FCAST, nor ALC/LCT, UDP or IP will generate feedback messages. But if FCAST is used along with a session control application capable of collecting reception information from the receivers, then this session control application (that is kept separate from FCAST) will probably create a limit on the FCAST scalability. This situation can be mitigated by using a hierarchy of feedback message aggregators or servers. How this session control application can be designed is out of the scope of the present document.

A goal of FCAST is to enable the receivers to collect meta-data information sent in-band, along with the objects. The transmission of meta-data is done in two complementary ways. Depending on the target use case, the sender will use one scheme or the other, or both of them. When the client must be able to process the meta-data, or a subset of the meta-data, early in the reception process, and in particular before the object has been completely received and decoded, then meta-data (or a subset) is included in a dedicated ALC/LCT header extension. When it is sufficient for the client to extract the meta-data, or a subset of the meta-data, once the object has been fully received and decoded, then meta-data (or a subset) is appended to the object. Several motivations can lead a sender to use one method or the other, or both. Using a dedicated header extension enables a client to select the objects he is interested in, based on various criteria (like the object size or encoding). In that case the client can decide to receive the following packets, or to drop them if he's not interested by the object, which saves both processing and memory resources. But appending meta-data to the object is also an efficient way to carry the information, in particular with very small objects, for instance when the size of the object and the associated meta-data is less than the maximum payload size. With larger objects, appending the meta-data to the object enables to benefit from the erasure protection that is probably provided by the FEC encoding of the object.

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] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).

3.  Definitions, Notations and Abbreviations

3.1.  Definitions

This document uses the following definitions:

Carousel: this is the object transmission system of an FCAST sender;

Carousel Instance: this is a fixed set of registered objects, that will be sent by the carousel during a certain number of cycles. Whenever objects need to be added or removed, a new Carousel Instance is defined;

Carousel Cycle: within a cycle, all the objects registered in the Carousel Instance are transmitted a certain number of times. By default, objects are transmitted once per cycle, but higher values are possible, that might differ according to the object (e.g. to simulate different levels of priorities);

3.2.  Abbreviations

This document uses the following abbreviations:

CIO: Carousel Instance Object

OMD: Object Meta Data

FEC OTI: FEC Object Transmission Information

FPI: FEC Payload ID

4.  FCAST Specifications

This section gives more details on the key design principles behind FCAST, and their motivations.

4.1.  Meta-Data Associated to Objects

Meta-data are associated to each object sent during a session. The meta-data can be composed of, but are not limited to:

• the name and location (URI) of the object;
• the MIME type of the object;
• the size of the object;
• the (optional) encoding of the object performed by FCAST;
• the size of the object after the (optional) encoding performed by FCAST;
• the timestamp associated to this object;
• the time validity of the object, after which the object is considered as out-of-date;
• the message digest of the object, for instance its SHA-1 sum, in order to check its integrity;
• a digital signature for this object;
• when a file is split into several objects by FCAST, an indication that this is a split of the original object;
• when a file is split into several objects by FCAST, the slice index in $[0 .. Slice_Nb[$, and the total number of slices;
• when a file is split into several objects by FCAST, a counter indicating the offset at which this slice starts within the original object;
• the FEC Object Transmission Information (FEC-OTI) when it is preferable to carry the information as meta-data rather than within the ALC/LCT EXT_FTI header extension;

This list is not limited, and new meta-data information can be added to this list as the need arises. Note also that these items are not all mandatory. The only mandatory meta-data item is the name and location of the object (i.e. ``Content-Location'' attribute).

4.2.  Meta-Data Transmission

FCAST proposes two complementary but optional ways to carry meta-data:

• by appending meta-data to the object being transmitted: this is a very efficient scheme, since meta-data are received along with the object, and benefit from the optional FEC erasure protection of the object. Yet a limit of this scheme is that a client does not know the meta-data of an object before receiving and decoding the object completely;
• by adding a dedicated EXT_OMD (Object Meta-Data) header extension to the ALC/LCT packets for a given object: this header extension contains a subset or all of the meta-data of the associated object. Because this header extension can be retrieved and processed before the object is totally received and decoded, it gives the opportunity to a client to know the object's content and determine whether or not to receive it altogether. There are constraints on the EXT_OMD size (Section 5.1 (Object Meta-Data ALC/LCT Header Extension (EXT_OMD) Format)): the EXT_OMD size cannot exceed 1020 bytes, and the resulting ALC packet, after adding the UDP/IP headers, should remain below the PMTU for higher efficiency.

Depending on the target use case, the sender can choose:

• to send the meta-data in the EXT_OMD header extension of all (or most of) the ALC packets sent. In that case, a client will immediately retrieve the meta-data of the object, no matter when he joins the session, and can then decide whether or not to decode the object;
• to send the meta-data in the EXT_OMD header extension of the first few ALC packets sent. In that case, in PUSH mode, a client having joined the session before transmissions actually start, quickly recovers the meta-data of the object and can decide whether or not to download the object;
• to send the meta-data in the EXT_OMD header extension of ALC packets chosen periodically, for instance once per second, or every 1000 ALC packets. This strategy enables a receiver to be able to recover the meta-data of an object quickly, for instance on average every 0.5 seconds when the EXT_OMD is sent once per second. The client can then decide whether or not to decode the object, and whether or not to keep the already received packets of the object;
• to send the meta-data only in the object, appended to this later. For instance, it makes sense when sending small objects, since the meta-data size can be comparable to that of the object. In that case, receiving the object is probably not a problem to clients, even if they are finally not interested in it;
• to send the meta-data both appended to the object and {in some/in most of/in all/periodically in} ALC packets with the EXT_OMD header extension. In some cases, the information contained in the EXT_OMD can be a subset of the meta-data, for instance containing the information required by the clients to take the decision of downloading the object or discarding the associated packets, but not the pieces of information that are required by the end user to process the object. In some cases, the meta-data appended to the object and the meta-data contained in the EXT_OMD header extension of the ALC packets can complement (without creating duplications) one another; What information should be put in the EXT_OMD header extension versus should be appended to the object is not specified in this document and depends on the target use case. In some cases, the client must be able to select the objects he's interested in after receiving some high level indication on the content, e.g. the file's name and encoding, plus a human readable description of the content. In that case, these pieces of information are included in the EXT_OMD. In other target use cases, the client might decide to drop the objects whose size exceeds a given threshold, because of insufficient memory resources for instance. In that case, the EXT_OMD contains the object's transfer length;

4.3.  Object Transmissions Within a Carousel

The object transmissions are performed within the carousel of an FCAST sender. This carousel sends all the objects that have been scheduled for transmission, for a given number of cycles (i.e. repetitions). In some use-cases (e.g. in PUSH mode), there will be a single cycle, whereas in other use-cases (e.g. in ON-DEMAND mode), transmissions could last several days which can represent a high number of cycles. By default, objects are transmitted once per cycle, but higher values are possible, that might differ according to the object, for instance to simulate different levels of priorities. We call the Carousel Instance a fixed set of registered objects that will be sent by the carousel during a certain number of cycles. Whenever objects need to be added or removed, a new Carousel Instance is defined.

The FCAST application can optionally create a Carousel Instance Object (or CIO), that describes the carousel instance. More specifically, this CIO:

• lists the objects that are part of the current carousel instance. It provides the TOI of the objects that are in the current carousel instance. Implicitly, all objects that are not in this list are considered as not being part of the current carousel instance, even if they were present in the previous carousel instances. However this CIO does not describe the objects themselves and in particular this CIO does not include any meta-data.
• TBD

Using a CIO is not mandatory. If it is not used, then the clients progressively learn what files are part of the carousel by receiving ALC packets with new TOIs. However using a CIO has several benefits:

• the receivers know when they can leave the session, i.e. when they have received all the objects that are part of the delivery session, thanks to a Complete keyword that can be added to the CIO;
• In case of a session with a dynamic set of objects, the sender can easily inform the receivers that some objects have been removed from the carousel by using the CLOSE object mechanism of ALC/LCT, even if no Carousel Instance object is used. However it requires that the clients receive at least one of the ALC packets containing the ALC CLOSE object flag. A client with an intermittent connectivity will not necessarily be informed. It is therefore recommended to use a CIO;

The decision of how often and when the CIO should be sent within an FCAST session is left to the sender and depends on many parameters, including the target use case, and the session dynamics. In case of an FCAST session in PUSH mode, the CIO should be sent before the objects (and with a low frequency after the start to enable late receivers to catch up, if this is desired). In case of a highly dynamic FCAST session, a CIO will probably be sent at the beginning of each new carousel instance, and then periodically. The period depends on the desired maximum latency that could be experienced by late receivers who join the FCAST session in the middle of a carousel instance transmission cycle, and who therefore missed the initial CIO transmission.

At a sender, the following operations take place:

• the user (or another application) selects a set of objects (e.g. files) to deliver and submits them to the FCAST application. The user also specifies how many times each object should be sent in this carousel (said differently, if objects have similar lengths, assigning them a different number of transmissions leads to define different transmission priorities to each of them);
• the user then informs FCAST that all the objects of the set have been submitted. If no new object will be submitted later to FCAST, i.e. if the session's content is now complete, the user also informs FCAST;
• the FCAST application now knows the full list of objects that are part of the carousel instance and defines a transmission schedule of the objects and the associated ALC packets (e.g. by sending them in sequence);
• the FCAST application starts the carousel, for the number of transmissions specified for each object. Deciding whether to use the EXT_OMD and/or appending meta-data to each object is left to the sender. The FCAST application also decides whether or not to create and send a CIO. If FCAST knows that no new object will be submitted and if FCAST creates a CIO, then the sender includes the Complete keyword to inform all clients that no object in addition to the ones specified in this carousel instance will be sent;
• then transmissions take place until:
  • each object has been transmitted the desired number of times, or
  • the user wants to add one or several new objects to the carousel, or on the opposite wants to remove them from the carousel. In that case a new carousel instance must be created, i.e. we continue at step 1 above.

5.  Control Information Formats

5.1.  Object Meta-Data ALC/LCT Header Extension (EXT_OMD) Format

The EXT_OMD header extension format is the following. This is an ALC PI Specific header extension (i.e. HET ≤ 127).

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   HET = XXX   |       HEL     | Format| CENC  |               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+               |
.                                                               .
.                Object Meta Data Content                       .
|                                               +-+-+-+-+-+-+-+-+
|                                               |    Padding    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

In Figure 1 (Object Meta-Data (EXT_OMD) header extension format.), the Format field defines the format of the Object Meta Data Content field (e.g. XML), while the CENC field defines the optional content encoding of the Object Meta Data Content field (e.g. gzip). An optional padding field is used to make the EXT_OMD an integral number of 32 bit words. Because of the HEL semantic, the EXT_OMD size cannot exceed: 255 * 4 = 1020 bytes. Of course, the resulting ALC packet size, after adding the UDP/IP headers, should remain below the PMTU size for higher efficiency. This constraint can lead the sender to use the EXT_OMD extension in separate control ALC packets, containing no data or repair symbol.

5.2.  Object Trailer Format

To each object of an FCAST session, a trailer is appended that might or not include meta-data. The format of the trailer 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
                                                +-+-+-+-+-+-+-+-+
             Object data                        |               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+               |
.                                                               .
.                Object Meta Data Content                       .
.                                                               .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Format| CENC  |       Trailer Length          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

In Figure 2 (Object trailer with meta-data.), the Format and CENC fields have the same meaning as for EXT_OMD. If no object meta data is appended to the object, then these two fields are not present. The Trailer Length field contains the number of bytes used by all the trailer fields, from the Object Meta Data Content field up to and including the Trailer Length field.

 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
                                                +-+-+-+-+-+-+-+-+
             Object data                        |    Trailer... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...Length = 2 |
+-+-+-+-+-+-+-+-+

Figure 2 (Object trailer with meta-data.) shows an object trailer without any meta-data. In that case the Trailer Length value equals 2, which means that the trailer is only composed of the Trailer Length field.

5.3.  Carousel Instance Object (CIO) Format

The Carousel Instance object format is the following. It basically consists of two lists:

• a list of TOIs included in the current carousel instance, specified either as the individual TOIs of each object, or as a TOI span (e.g. 10..100 means that all objects whose TOI is in the range 10 to 100 inclusive are part of the carousel instance), or both. In all cases, a TOI in the list is included unless otherwise specified by the exclude list;
• a list of TOIs to exclude from the current carousel instance, even if they are part of the include list. Here also the TOIs are specified either as the individual TOIs to exclude, or as a TOI span to exclude, or both. In all cases, the priority of the exclude list is higher than the priority of the include list: if a TOI is on both list, then the TOI is considered not being part of the carousel instance.

The TOI 0 is reserved for the Carousel Instance object. The various instances of this object are identified by the Carousel Instance ID.

XXX: format TDB

The Carousel Instance ID identifies the carousel instance. It starts from 0 and is incremented by 1 for each new carousel instance. Wrapping of the Carousel Instance ID can happen. In that case, IDs that wrapped to 0 must be considered higher than the IDs used before the wrapping.

The Expires attribute identifies the validity period of this carousel instance. This validity period is expressed as an NTP time. The validity period should enable the transmission, the reception and processing of all the objects that belong to this carousel instance.

6.  Security Considerations

TBD

7.  Acknowledgments

8. Normative References

Author's Address

Full Copyright Statement

Copyright © The IETF Trust (2008).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an “AS IS” basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.

Intellectual Property

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.