RMT Working Group M. Luby INTERNET DRAFT J. Gemmell Expires 8 September 2000 L. Vicisano L. Rizzo J. Crowcroft B. Lueckenhoff 8 March 2000 Asynchronous Layered Coding A scalable reliable multicast protocol Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "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. Copyright Notice Copyright (C) The Internet Society (2000). All Rights Reserved. Abstract This document describes Asynchronous Layered Coding, a scalable reli- able multicast protocol, hereafter referred to as ALC. ALC can be used to reliably transmit objects to multiple receivers. An object can be any well-defined piece of data. Examples include any type of file such as a group of pictures in an MPEG stream, a MP3 music file, a JPEG image, and a collection of files that are zipped into one file. In addition, the ALC delivery model is fairly flexible, e.g., on demand or a push delivery. When using ALC, the payload of the Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 1] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 packets that flow from senders to receivers in no way depend on net- work conditions or the reaction of receivers to these conditions, although the rate of flow of the packets in various parts of the net- work does depend on network conditions. Receivers may join or leave an existing packet stream in an asynchronous manner independent of other receivers. Congestion control is achieved by sending several packet streams ordered in a layered fashion and delivering only a subset of these to individual receivers. The number of streams received is dictated by the local bandwidth availability and network conditions. A possible way to achieve this is by using a distinct multicast address for each stream. Receivers join the lowest layer stream they are not currently joined to at coordinated points in time when there is more available bandwidth between those receivers and the sender. Similarly, receivers leave one or more highest layer streams they are currently joined to as soon as they feel congestion (typically as evidenced by packet loss). Another possibility to achieve this form of congestion control is through router-assisted schemes. Reliability is achieved via FEC coding only, i.e. there is no request for feedback for retransmission from receivers that miss packets for whatever reason. 1. Introduction This document describes a scalable reliable protocol using IP multi- cast. IP multicast, while powerful and efficient, is a "best effort" service [DEE88]. It does not guarantee packet reception, or reception order. Many reliable multicast protocols have been built on top of multicast. However, scalability is not a design goal for many reli- able multicast protocols. Even among those that targeted improved scalability, many still fall far short of the scalability of IP mul- ticast itself. Others, while as scalable as IP multicast, require changes to routers or other infrastructure, making their deployment unlikely in the near term. The key difficulty in scaling reliable multicast is dealing with the amount of data that flows from receivers back to the sender. Proto- cols that avoid any such feedback can be massively scalable. The data carousel [AFZ95] approach is a simple protocol that avoids any feed- back from the receivers. The sender simply loops repeatedly through the symbols of the object, places the symbols into packets, and transmits the packets (a symbol is a small fixed size portion of data). If the receiver misses any symbol, it simply waits for the symbol to be sent again in the next loop. However, a receiver has to wait for the full loop to repeat to receive a symbol that is missed if the packet carrying it is lost. Forward error correction (FEC) coding can be used to improve the data carousel approach [RIZ97a, GEM99, VIC98A, BYE98]. Using a FEC codec, i.e., a FEC encoder at the sender to generate packets from an object and the corresponding FEC Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 2] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 decoder at the receivers to process packets in order to recover the object, can dramatically reduce the amount of packets a given receiver needs to receive in order to recover the object. ALC relies exclusively on a FEC codec to achieve reliability, thereby avoiding non-scalable reliability mechanisms that rely on receiver feedback to the sender to trigger retransmission of missing packets. A survey of FEC codes and considerations for their use in reliable IP multicast can be found in [FECBB]. This document utilizes the terminology and concepts introduced in that survey. An attractive feature of a scalable reliable protocol is the ability for different receivers to join and leave the packet stream asynchro- nously without adversely affecting the reception experience of other receivers and without affecting the scalability of the protocol. This is one of the features provided by ALC. ALC congestion control is achieved by using several packet streams and delivering only a subset of these to individual receivers. The streams are ordered in layers from lowest to highest. The number of streams delivered to each receiver is dictated by the local bandwidth availability and network conditions. A possible way to achieve this is by using a distinct multicast address for each stream. Receivers that can receive packets at a rate higher than their current rate are allowed to do this by joining the lowest layer stream(s) they are not currently joined to. Receivers that are receiving packets at a higher rate than they have the capacity for (as evidenced by packet loss) MUST leave one or more of the highest layer streams they are currently joined to immediately. Another possibility to implement this form of congestion control is through a router-assisted scheme where the selection of which streams to forward is performed by routers. In this case all the streams could be transmitted in a sin- gle multicast group. Having routers select which streams to forward allows a smaller granularity in the rate-set and a faster response time. A limitation of this approach is that it potentially requires changes to the hardware router infrastructure. One of the attractions of ALC is that it is multicast routing independent. In particular, ALC works well with the original multi- cast model introduced in [DEE88] as well as with the emerging PIM single source model that is based on [HOL99]. PIM single source is an attractive match for ALC for a few reasons. First, because of the different layers that ALC uses, and because ALC can use different multicast addresses for the transmission of different objects, the fact that address allocation with PIM single source is simple is an advantage. Second, because ALC supports a dynamically changing set of receivers who are dynamically changing the set of multicast streams to which they are joined, the light weight mechanisms used in PIM single source to quickly react to changes in the multicast tree Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 3] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 topology is an advantage. Third, because ALC is scalable to a very large number of receivers joined to a single multicast group that may span the global Internet, the light weight mechanisms that PIM single source uses to cross ISP boundaries is an advantage. Finally, because PIM single source explicitly references the source of the multicast transmission, it has security advantages for denial of ser- vice attacks. 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 RFC 2119 [R2119]. 2. General Architecture An object transmission session comprises all packet streams emanating from all senders that pertain to the transmission of a particular object that could potentially be received by a receiver to recover the object. For example, packets pertaining to a particular object could be transmitted from three different senders, each sending four streams of packets at different rates. A receiver may join and receive packets from all 12 streams concurrently until it has enough packets in total to recover the object. The receivers need to obtain an object transmission session descrip- tion before starting the down-load of an object. The session description must include the relevant session parameters needed by a receiver to enact a down-load of an object from the senders partici- pating in the session. The object transmission session description is determined and agreed upon by the senders and communicated to the receivers out of band, or, in some cases, included or partially included in the header of each packet. The session description could include the object name, the object length, the packet format and length, the FEC codec type, the description of which congestion con- trol algorithms to use, the multicast address(es) of the layered streams, their port number(s), and their transmission bandwidths. The session description could be in a form such as SDP [HAN98]. We assume that there exists an out of band mechanism for receivers to obtain the session description. The session description might be car- ried in a session announcement protocol such as SAP [HAN96], located on a Web page with scheduling information, or conveyed via E-mail or other out of band methods. Discussion of session description format, and distribution of session descriptions is beyond the scope of this document. An FEC encoder is used to generate encoding symbols that are placed in the payload of ALC packets. A survey of FEC codecs can be found in [FECBB], and the current document relies upon and uses the termi- nology of this survey. The FEC coding information is information that Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 4] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 needs to be passed to a receiver in order to decode objects FEC cod- ing information include the FEC codec type, the source block length, the symbol length, the object length, the encoding block number, the encoding symbol ID, and an encoding flag indicating whether the encoding symbol is a source symbol or a redundant symbol for block codes. The FEC protocol ID specifies the FEC codec type and the way it is to be used for the transmission (see delivery modes below). The object length, source block length and the symbol length are part of FEC object transmission information. The encoding block number (if used) and the encoding symbol ID that identify the encoding sym- bol in the payload of an ALC packet constitute the FEC payload ID. All ALC packets pertaining to a particular object transmission ses- sion MUST have the same format. An ALC packet consists of an ALC header and a payload. Together with other information, the ALC header MUST contain congestion control information, an FEC protocol ID, and an FEC payload ID. Receivers use congestion control informa- tion to coordinate the rate at which they receive packets and to measure congestion as indicated by packet loss in order to determine this rate. Other OPTIONAL information that an ALC header may contain is an object transmission label, FEC session information, FEC object transmission information, and authentication information. The object transmission label can be used by receivers to verify that received packets are associated with a particular object transmission session. Therefore, object transmission labels for sessions pertain- ing to different objects should be different. As an example, the object transmission label may be the MD5 hash of the object name, object length and FEC object transmission information described below. ALC packets are sent over the network encapsulated within UDP packets sent with an IP multicast address. 3. Minimizing reception overhead The primary purpose of using FEC codes is to ensure that minimal number of packets need be received in order for a receiver to recon- struct an object. Reception overhead is used to measure this. Reception overhead is the aggregate length of packets needed to recover the object beyond the object length, measured as a percentage of the object length. For example, if it takes 15 MB of packets in order to recover a 10 MB object, then the reception overhead is (15- 10)/10 times 100, or 50%. The minimal reception overhead possible is 0%. Under ideal conditions, reception overhead is 0% using even the Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 5] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 simplest of FEC codes. For example, a simple carousel achieves 0% reception overhead when transmission is over a network with no packet loss using a single multicast stream with receivers that join and stay attached to the stream until they have enough encoding symbols to recover the object. However, under more realistic conditions when transmission uses multiple multicast streams, when there is packet loss, and when receivers join and leave streams during the down-load process, more sophisticated FEC codes are clearly useful to minimize reception overhead. There are three primary contributors to reception overhead, and these guide the design of how to use FEC codes for ALC. These contributors are: (1) duplicate encoding symbol reception due to division into blocks of the object; (2) duplicate encoding symbol reception due to fixed length FEC codes; (3) inherent reception overhead of the FEC code. ALC based on small block codes is prone to (1) and (2), ALC based on large block codes is most prone to (2) and (3), and ALC based on large on demand codes is most prone to (3). 3.1. Division into blocks One concern is the order of encoding symbol transmission from dif- ferent blocks when the object is partitioned into blocks. Suppose the object is partitioned into m blocks of k source symbols each, and any k encoding symbols from a block is sufficient to recover the k source symbols from that block. Ideally, reception of any km encod- ing symbols is sufficient to recover the entire object. Actually, reception of k encoding symbols for each of the m blocks is necessary to recover the entire object. Thus, it is important to schedule the transmission of symbols so that in the face of most patterns of packet loss receivers can recover the object from reception of as close to km encoding symbols as possible. A RECOMMENDED ordering is to interleave encoding symbols from different blocks. This inter- leaving can be described in terms of rounds, where in a round m encoding symbols are transmitted, one from each block. A particular sending order in each round is not specified by ALC. However, it is RECOMMENDED that some randomization be performed to eliminate corre- lation with periodic losses. For example, sending could be performed as follows: In round i, randomly choose a permutation p(i) of the m blocks, and then send the i-th encoding symbol from each of the m blocks in the order determined by p(i). In the following example, the object is split into 3 blocks of 4 source symbols each: +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ + s00 + s01 + s02 + s03 + s10 + s11 + s12 + s13 + s20 + s21 + s22 + s23 + +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ Source block 0 | Source block 1 | Source block 2 Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 6] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 Then the first 4 permutations chosen are p(0) = (1,0,2), p(1) = (0,2,1), p(2) = (2,0,1), p(3) = (0,1,2), and the send order for the first 4 rounds is: +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ + e10 + e00 + e20 + e01 + e21 + e11 + e22 + e02 + e12 + e03 + e13 + e23 + +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ Encoding symbol send order Object division into blocks, and thus application of this scheme, is applicable to all the codes, as the value of k is ultimately limited for all the codes. For example, small block codes use small values of k because of computational limits, and large block codes and large on demand codes use much larger yet still limited values of k because of memory and packet length limitations. This interleaving scheme minimizes the induced reception overhead due to division into blocks for any predefined loss pattern for a given value of k. However, it is likely that the induced reception overhead will be larger and more variable when k is small and when losses are moderate or more. For example, when k = 20 and m = 50, the induced reception overhead with respect to a 10% random packet loss is on average 18%, and will reach over 40% for some receiver among 1,000 receivers. See [BYE98] for a more detailed analysis of this. Thus, the reception overhead will tend to be smaller and less variable when using either large block codes or large on demand codes than when using small block codes. For small block codes and large block codes the limit on the number of encoding symbols n for the codes will limit the number of distinct rounds to n. For large on demand codes, since there is no limit to the number of encoding symbols there can be an unlimited number of rounds. A simple way to choose the permutation in each round is the follow- ing, and this is RECOMMENDED when protecting against arbitrary packet loss patterns. At each round, the permutation p(i) is determined by selecting a first block randomly, and the rest of the ordering is the consecutive blocks following this first block, modulo the number of blocks. For example, if there are m blocks, and block j is selected as the first, the permutation p(i) consists of block j through block m-1, followed by block 0 through block j-1. For more detailed discussion, see [VIC98B,GEM99]. 3.2. Block FEC codes For some FEC codes for a given object consisting of s source symbols there is a limited supply t of encoding symbols that are produced. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 7] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 If the number of encoding symbols to be sent exceeds t then some encoding symbols need to be sent more than once. Thus, it is impor- tant to schedule the order of sending encoding symbols in such a way as to avoid as much as possible reception of the same encoding symbol more than once by the same receiver. This applies to ALC based on block codes as these codes produce a limited number of encoding sym- bols. However, this does not apply to ALC based on large on demand codes, as these codes can produce an essentially unlimited supply of encoding symbols. 3.2.1. A single stream In some simple scenarios, receivers will join a single ongoing multi- cast stream, collect enough encoding symbols to decode the object, and then leave the object transmission session. In this situation, in order to avoid as much as possible duplicate reception of packets by such receivers, it is important to send the encoding symbols the second and subsequent times in the same order that they were sent the first time. Thus, for example, a receiver that joins the session towards the end of the transmission of the encoding symbols for the first time can continue receiving packets from the transmission of the encoding symbols for the second time and be sure to receive dis- tinct encoding symbols. However, it is inevitable that the reception overhead due to reception of duplicate encoding symbols can be large for receivers that join and leave the transmission over intervals of time that span the transmission of more than the total supply of encoding symbols. For example, a receiver may join the session at the beginning of the first transmission of encoding symbols and receive e0, e1, ... , e98, e99, leave the session and then rejoin the session again at the beginning of the second transmission of encoding symbols and receive again e0, e1, ... , e98, e99, thus receiving 100 duplicate encoding symbols that provide no benefit to recovering the object. +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+ + e0 + e1 + ... + e98 + e99 + ... + e0 + e1 + ... + e98 + e99 + +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+ first transmission | second transmission 3.2.2. General streams In more general scenarios, in order to recover an object, receivers will join multiple ongoing multicast streams dynamically. These streams may emanate from more than one server and may be running at different rates. Furthermore, receivers may join a given stream and rejoin the same stream an arbitrary amount of time later (for exam- ple, the next day) to complete the recovery. Finally, for congestion control purposes, receivers dynamically change the set of multicast Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 8] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 streams they are receiving from based on dynamically changing loss conditions. How to schedule the encoding symbols from a block code among the various multicast streams in order to minimize reception overhead under all of these different conditions is a challenge. Let r = t/s be the ratio of the number of encoding symbols to the number of source symbols. The larger the value of r the easier it is to avoid receiver reception of duplicate encoding symbols, and in particular as r goes to infinity then reception overhead due to this problem can go to zero. There are ordering schemes that keep reception overhead minimal for small value of r under certain restrictions. For example, in the previous subsection a scheme is described that minimizes reception overhead under the restriction that there is only one stream and the receiver is able to complete recovery within a time period that encompasses the transmission of t encoding symbols. However, under general conditions the best and simplest scheme for minimizing reception overhead for objects that aren't blocked is the following. For each stream, group the sending of encoding symbols into rounds. In each round, choose independently a random permuta- tion of all t encoding symbols and send the encoding symbols in this order. Using this ordering, it is not hard to show that no matter in which order and at what time a receiver may join and leave streams the induced reception overhead due to reception of duplicate encoding symbols of a receiver is at most on average r*ln(r/r-1)-1. Further- more, there are examples of receiver behavior that achieves these maximum averages. As examples, when r is two then the induced recep- tion overhead is at most 38.6%, when r is five then the reception overhead is at most 11.5%, and when r is ten then the reception over- head is at most 5.4%. Thus, to achieve a reasonable overhead the total length of the encoding must be substantially longer than the length of the object. 3.3. Inherent overhead A (n, k) linear block code has no inherent reception overhead, as any k encoding symbols are sufficient to recover all k source symbols. On the other hand, both the large block codes and large on demand codes described in [FECBB] do have an inherent reception overhead. 4. Delivery modes ALC can operate in several different delivery modes: On demand mode. Receivers may join the ongoing object transmission session at their discretion, obtain the necessary encoding symbols to reproduce the object, and then leave the session. In on demand mode, Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 9] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 senders typically transmit for some given time period selected to long enough to allow all the intended receivers to join the session and recover the object. The time period would typically be much larger than the down-load time for the object to make it convenient to receivers to enact the down-load at their discretion. For example a popular software update might be sent using ALC for several days, even though any particular receiver can enact the down-load in only an hour. Streaming mode. Typically, receivers join and remain joined to a particular set of multicast groups to receive multiple related objects in consecutive object transmission sessions. In streaming mode, senders typically transmit a fixed number of encoding symbols for each object. This number may depend on network conditions that are obtained using out of band methods. For example, if network con- ditions are such that at most 33% of the packets are lost over any 15 MB of transmitted packets, then 15 MB of encoding symbols may be transmitted for a 10 MB object to ensure that receivers are able to reassemble the object under the worst loss conditions. A typical application is a streaming real-time MPEG video, where each object consists of a group of pictures in the stream. For each object, the receiver obtains enough ALC packets to recover the object and then discards all subsequent packets associated with the object until packets start arriving for the next object. Push mode. Push mode combines a number of on demand mode transmis- sions, combined with a streaming mode transmission containing schedule information about the on demand transmissions. Typically, receivers join a particular set of multicast groups to collect ALC packets for multiple unrelated objects they have interest in, and receivers are not joined to the groups when ALC packets are being transmitted for objects they have no interest in. Receivers may automatically join the groups at appropriate times by listening to a multicast group containing schedule information of object transmis- sions. Commonly, the sender controls which receivers are to recover which objects using out of band methods. There are many other delivery modes that ALC can be used for that are not covered above. The description of the many potential applica- tions and the appropriate delivery mode is beyond the scope of this document. With many of these delivery modes, substantial additional mechanisms beyond what is described in this document will be needed to support the mode, i.e. the out of band mechanism for delivering object transmission session information to the receivers. This docu- ment only attempts to describe the minimal common scalable elements to these diverse applications using ALC as the delivery mechanism. 5. Congestion Control Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 10] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 ALC congestion control is specified in a companion document [CCMRBB]. This section only provides a brief description of the possible stra- tegies. ALC performs congestion control using layered streams. Receivers par- ticipating to the session are subject to heterogeneous data rates, obtained by selectively delivering to receiver a subset of all the streams available at the source. Two different techniques can be used to select which streams to forward in a distributed fashion. The first is based on sending each stream on a distinct multicast group and having receivers joining only a subset of groups. The second is based on using a single multicast group and having routers to perform the stream selection. This solution requires special router support. See [CAI99, LUB99] for further details. The solution with multiple multicast groups is based on [VIC98A, VIC98B]. A single sender generates and sends ALC packets to several multicast addresses concurrently, and packets sent to a particular multicast address are considered to be a stream layer. The u layers emanating from a single sender are numbered consecutively from 0 through u-1. Each layer sends ALC packets at a potentially different rate than other layers but at the same rate at all points in time. Receivers join as many layers as possible without experiencing packet loss as described below. To obtain y layers, the receiver MUST sub- scribe to layers 0 through y-1. When network congestion is detected (via packet loss) along the path from a particular sender to the receiver, the receiver MUST immedi- ately leave some number of its highest currently joined layers, as described in the building block [CCMRBB], to reduce the aggregate reception rate. In the case that the last ("base") layer is left, the receiver no longer receives any packets from that sender. When there is only one single sender that sends a single layer, ALC is a simple rate-limited transmission. In this case, the receiver should still detect congestion and be prepared to leave the object transmis- sion session if and when enough loss is detected. Congestion is assumed to have occurred when losses exceed a given threshold. This threshold depends on losses expected in the network. For example, in a wireless network, some loss may be expected even with no congestion. The threshold should be configurable by the receiving application. The default threshold should be zero, i.e., any packet loss should lead to leaving layers. Details of this will be specified in the congestion control multiple rates building block [CCMRBB]. 6. Packet format Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 11] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 The ALC packet header is laid out as follows (see Figure 1). The ALC payload immediately follows the ALC header. All integer fields are carried in "big-endian" or "network order", that is, most significant byte (octet) first. Unless otherwise noted, numeric constants are in decimal (base 10). Bits designated as padding have the value zero. All ALC packets pertaining to an object transmission session MUST be the same size and the same format. o 32-bits: Congestion control information o 3-bits: ALC version number (called "ver" in Figure 1) o 5-bits: Length of the non-fixed portion of the ALC header (called "hdr len" in Figure 1) o 8-bits: FEC protocol ID o 1-bit: FEC encoding flag (called "E" in Figure 1), 1 indicates source symbols in payload, 0 indicates redundant symbols in the payload (see [FECBB]). This is part of the FEC payload ID. o 1-bit: Additional header fields flag (called "A" in Figure 1), 0 indicates there are no additional header fields, and 1 indicates there are additional header fields. o 3-bits: Length of object transmission label (called "LTL" in Figure 1) in units of 32-bit words. LTL = y indicates the object transmis- sion label is y words in length. o 2-bits: Length of FEC object transmission information (called "LTI" in Figure 1) in units of 32-bit words. LTI = y indicates the FEC object transmission information is y words in length. o 1-bit: Length of FEC payload ID (called "F" in Figure 1). F = 0 indicates the FEC payload ID is 32-bits long. F = 1 indicates the FEC payload ID is 64-bits in length. o 4-bits: reserved o 4-bits: Length of source authentication information (called "LSA" in Figure 1) in units of 32-bit words. LSA = y indicates the source authentication information is y words in length. o 0 -- 7 x 32-bits: Object transmission label. LTL = y indicates the object transmission label is y words in length. o 0 -- 3 x 32-bits: FEC object transmission information. LTI = y Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 12] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 indicates the FEC object transmission information is y words in length. o 1 -- 2 x 32-bits: FEC payload ID. If F = 0 then this is 32-bits long. If F = 1 then this is 64-bits long. o 0 -- 15 x 32-bits: Source authentication information. LSA = y indicates the source authentication information is y words in length. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Congestion control information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ver | hdr len | FEC proto ID |E|A| LTL |LTI|F|reservd| LSA | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0-7 32-bit words of object transmission label | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0-3 32-bit words of FEC object transmission information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 32-bit FEC payload ID if F = 0, 64-bit FEC payload ID if F = 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0-15 32-bit words of source authentication information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1 - ALC packet header layout The congestion control information is specified in [CCMRBB]. The initial ALC version number is 0. The length of the non-fixed por- tion of the ALC header is in units of words and doesn't count the first two words of the ALC header (it doesn't count the congestion control information and everything up to and including LSA), but it does include the lengths of all additional headers that are indi- cated by A = 1. Thus, the length of the non-fixed portion of the ALC header can be used to directly find the beginning of the ALC payload. The FEC protocol ID specifies which FEC protocol to use. This includes the specification of the FEC codec and can also include identifying the delivery mode. There are several different FEC codecs available (see [FECBB]). The default FEC protocol ID is 0, which uses the FEC codec based on [RIZ97c]. The interpretation of the ALC packet header format used for the default protocol and for other protocols based on other FEC codecs is described in the appendices. For block codes, the encoding flag is set to 1 if the ALC payload contains source symbols, and is set to 0 if the ALC payload contains redundant symbols. For some FEC codecs, the encoding flag is not used and MUST be set to 0. The A flag is used Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 13] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 to indicate the presence of additional headers beyond those indi- cated by the second word of the ALC header. The length of the object transmission label can be anywhere from 0 (indicating field not present) to 7 words long. A standard setting for the length of the object transmission label is 4 words, i.e., the length of an MD5 hash. The length of the FEC object transmission information can be anywhere from 0 (indicating field not present) to 3 words long. The length of the FEC payload ID is either 32-bits or 64- bits (this is a REQUIRED field for all FEC protocols). The length of the source authentication information can be anywhere from 0 (indicating field not present) to 15 words long. The object transmission label (if used) verifies that the packet is associated with the object transmission session. Generally, the object transmission label is all or part of the MD5 hash of the relevant parameters associated with the session. The exact format and use of the object transmission label is FEC protocol dependent. The FEC object transmission information (if used) contains informa- tion that is used by the FEC codec to decode the object. This is information MUST NOT vary from packet to packet. For example, this could include the length of the object, the source block length, and the symbol length. The exact format and use of the FEC object transmission information is FEC protocol dependent. For some pro- tocols, some or all of the FEC object transmission information is provided to receivers using out of band methods. The FEC payload ID identifies the content of the ALC payload con- tain FEC encoding symbols. The encoding symbol ID must be part of the FEC payload ID. If the object is partitioned into blocks, then the encoding block number is also part of the FEC payload ID. The exact format and use of the FEC payload ID is FEC protocol depen- dent. The source authentication information (if used) contains informa- tion that can be used by a receiver to verify the source of the packet. The exact format and use of the source authentication information is FEC protocol dependent. The minimal required portion of the ALC header can be enough for a simple on demand mode service, where most of the information can be obtained by out of band methods by receivers. As shown in Figure 2, the minimal ALC header is 3 words long, consisting of one word of congestion control information, one word of control information including types, lengths, and flags, and a one word FEC payload ID. In this example, the FEC payload ID consists of a 16-bit encoding block number and a 16-bit encoding symbol ID. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 14] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Congestion control information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 1 | FEC proto ID |E|0| 0 | 0 |0|reservd| 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding block number | encoding symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2 - An example of a minimal ALC packet header For other delivery modes, other information in the ALC header can be useful. For example, consider a push mode service where receivers obtain object transmission session information by listen- ing to a multicast group containing this information for the multi- ple objects. This object transmission session information could include the object transmission label, the length of each object, the source block length and the symbol length used by the FEC codec, and additional information about when ALC packets will be transmitted for the object. In this mode, it may be appropriate for the ALC header to contain an object transmission label and the remaining transmission time for a particular object. The object transmission label allows the receiver to associate received pack- ets with particular objects. The remaining transmission time can be used to allow receivers to predict whether or not they will be able to recover the object from the packets they have already received and from the packets they can expect to receive in the future. An example is shown in Figure 3. In this example, the object transmission label is 2 words long, consisting of the first 64-bits of the MD5 hash of the appropriate object transmission ses- sion parameters. The FEC object transmission information is one word, consisting of a 32-bit remaining transmission time in seconds. The FEC payload ID is one word, consisting of a 16-bit encoding block number and a 16-bit encoding symbol ID. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 15] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Congestion control information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 4 | FEC proto ID |E|0| 2 | 1 |0|reservd| 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 64-bits of MD5 hash of relevant | + + | object transmission session parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | remaining transmission time in seconds | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding block number | encoding symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3 - An example of a push-mode ALC packet header As another example, consider a streaming mode service where receivers remain joined to the multicast group to sequentially recover multiple related objects of different length. In this case, all information to recover the objects may be the same from one object to the next except for the object length. For example, all objects may be encoded using the same FEC encoder and use the same set of streams and rates for the transmission, and use the same source block length and symbol length. Thus, once a receiver obtains all of this information, the only additional information receivers need to obtain to decode each object is its length. In this case, the ALC header could contain the object transmission label, the object length and source authentication information, as shown in Figure 4. In this example, the object transmission label consists of the first 64-bits of the MD5 hash of the relevant object transmission session parameters, the FEC object transmission information consists of the 32-bit object length, the FEC payload ID consists of a 32-bit encoding symbol ID, and the source authen- tication is 3 words in length. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 16] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Congestion control information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 7 | FEC proto ID |E|0| 2 | 1 |0|reservd| 3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 64-bits of MD5 hash of relevant | + + | object transmission session parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | 12 bytes of source authentication information | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4 - An example ALC packet header for streaming mode The predefined fields within the ALC header have been included because it is recognized that many applications will find these fields useful. Some limited number of applications may require additional header fields. For example, in a payment for down-load application, encryption of packets may be useful. To allow for unanticipated or rarely used additional header fields, the ALC header contains an additional header fields flag "A". If "A" is set to 0 then no additional header fields are included within the ALC header beyond the predefined fields. When additional headers beyond the predefined fields are used, the value of "A" within the ALC header MUST be set to 1. The format of additional headers is an 8-bit Additional Header Type (AHT), an 8-bit header Additional Header Length (AHL), followed by the additional header content. AHT determines the type of the additional header. AHL specifies the length of the additional header in 4-byte words, and this includes the length of AHT and AHL. Note that this implies that the length of the additional header content MUST be at least 16 bits and MUST be an odd number of 16-bits words. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 17] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AHT | AHL | current header content ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5 - format of additional headers 7. Sender Operation ALC assumes that one or more senders generate and send encoding sym- bols for a single object to one or more multicast addresses. The encoding symbols sent to a particular multicast address define a mul- ticast stream, and the transmission rate on different streams may differ. Typically, the sender(s) continue to send encoding symbols to all streams until the transmission is complete. The transmission may be considered complete when some time has expired, a certain number of encoding symbols have been sent, or some out of band signal (from a higher level protocol, perhaps) has indicated completion by a sufficient number of receivers. The sender(s) may then proceed to additional object transfers, or terminate. In on demand mode, senders transmit for some given time period selected to allow all the intended receivers to tune in and get the object. This would typi- cally be much larger than the down-load time for the object to make it convenient to receivers to join the object transmission session asynchronously. For example a popular software update might be sent using ALC for several days, even though the down-load itself only takes an hour. All encoding symbols in an ALC transfer MUST be the same size. The sender(s) may determine the symbol size arbitrarily, but must coordi- nate or use a default symbol size to ensure that all encoding symbols are of equal length. Larger packet sizes (which implies larger encod- ing symbols) are generally desirable so that the fraction of bandwidth lost to packet headers is reduced. On the other hand, if the packet size is larger than the network's maximum transmission unit (MTU), packets would be fragmented, and the loss of any fragment would require the entire packet to be lost. Therefore a packet size close to, but not exceeding, the MTU is best, with the symbol size chosen as the MTU less the size of the IP, UDP and ALC headers. How- ever, as some receivers may not be able to contain the object in main memory, it is desirable that a multiple of 512 bytes should be chosen for the symbol size. This makes writing to disk sectors more con- venient (if values below 512 bytes are necessary, they should be chosen to evenly divide 512). Ethernet's MTU is 1500 bytes and PPP's Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 18] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 is at least 576 bytes. For the above reasons we RECOMMEND to use an ALC payload size of either 512 or 1024 bytes. The former can be advantageous when packet loss occurs on a small-MTU modem link; the latter is to be preferred in all other cases, as it reduces packet header overhead and packet handling overhead in routers. 8. Receiver Operation Once receivers have obtained the object transmission session descrip- tion needed to initiate a down-load of an object, the receivers join one or more multicast streams associated with the session and start receiving ALC packets from these streams. In order to perform rate and congestion control, the streams emanating from a single sender are organized into layers. As described in the congestion control section, receivers MUST join and leave these streams to vary their down-load speed in the face of varying bandwidth capacity between the receivers and the sender. The receiver can operate in several possible modes. For example, in on demand mode receivers may join one or more multicast streams asso- ciated with the object transmission session, obtain the necessary encoding symbols to reproduce the object, and then leave all of the multicast streams. As another example, in push mode a receiver may be tuned in to a continuous session announcement multicast stream to determine when objects of interest are scheduled for transmission. Then, at the appropriate time the receiver automatically joins the object transmission session to down-load objects of interest. As another example, in streaming mode a receiver may be continuously joined to a set of multicast groups to down-load all objects. 9. ALC and Generic Router Assist Router filtering of ALC packets to assist in congestion control is described in [LUB99]. The addresses of the multicast layers can be communicated to the routers and they can do filtering of groups based on congestion. This is one of the reasons why it is good to have the sequence number information in a fixed place in the ALC packet header, so that the routers can probe this field if necessary (although it may not be). There are some good strategies for combin- ing router assisted congestion control with receiver congestion con- trol in such a way that ALC will perform well when only receivers are doing congestion control, and will perform even better with router assist. 10. Intellectual Property Issues There are patents pending for large block codes and for large on demand codes. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 19] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 11. Acknowledgments Thanks to Hayder Radha and Vincent Roca for detailed comments on this paper. 12. References [AFZ95] Acharya, S., Franklin, M., and Zdonik, S., "Dissemination-Based Data Delivery Using Broadcast Disks", IEEE Personal Communications, pp.50-60, Dec 1995. [BLA94] Blahut, R.E., "Theory and Practice of Error Control Codes", Addison Wesley, MA 1984. [BYE98] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., "A Digital Fountain Approach to Reliable Distribution of Bulk Data", Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. [CAI99] Cain, B., Speakman, T., and Towsley, D., "Generic Router Assist (GRA) Building Block, Motivation and Architecture", Internet Draft draft-ietf-rmt-gra-arch-00.txt, a work in progress. [CCMRBB] "Congestion Control for multi-rate building block", draft to be written for submission to the IETF. [DEE88] Deering, S., "Host Extensions for IP Multicasting", RFC 1058, Stanford University, Stanford, CA, 1988. [FECBB] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L., Crowcroft, J., Luekenhoff, B., "Reliable Multicast Transport Building Blocks: Forward Error Correction", Internet Draft draft-ietf-rmt-bb-fec-00.txt, a work in progress. [GEM99] Gemmell, J., Schooler, E., and Gray, J., "FCast Scalable Multicast File Distribution: Caching and Parameters Optimizations", Technical Report MSR-TR-99-14, Microsoft Research, Redmond, WA, April, 1999. [HAN98] Handley, M., and Jacobson, V., "SDP: Session Description Protocol", RFC 2327, April 1998. [HAN96] Handley, M., "SAP: Session Announcement Protocol", Internet Draft, IETF MMUSIC Working Group, Nov 1996. [HOL99] Holbrook, H., Cheriton, D., "IP Multicast Channels: Experss Support for Large-scale Single-source Applications", ACM SIGCOMM'99 [LUB99] Luby, M., Vicisano, L., Speakman, T. "Heterogeneous Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 20] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 multicast congestion control based on router packet filtering", presented at RMT meeting in Pisa, March 1999. [R2068] Fielding, R., Gettys, J., Mogul, J. Frystyk, H., Berners-Lee, T., Hypertext Transfer Protocol - HTTP /1.1 (IETF RFC2068) http://www.rfc-editor.org/rfc/rfc2068.txt [R2119] Bradner, S., Key words for use in RFCs to Indicate Requirement Levels (IETF RFC 2119) http://www.rfc-editor.org/rfc/rfc2119.txt [RIZ97a] Rizzo, L, and Vicisano, L., "Reliable Multicast Data Distribution protocol based on software FEC techniques", Proceedings of the Fourth IEEES Workshop on the Architecture and Implementation of High Performance Communication Systems, HPCS'97, Chalkidiki, Greece, June 1997. [RIZ97b] Rizzo, L., and Vicisano, L., "Effective Erasure Codes for Reliable Computer Communication Protocols", ACM SIGCOMM Computer Communication Review, Vol.27, No.2, pp.24-36, Apr 1997. [RIZ97c] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997. [RUB99] Rubenstein, Dan, Kurose, Jim and Towsley, Don, "The Impact of Multicast Layering on Network Fairness", Proceedings of ACM SIGCOMM [VIC98A] L.Vicisano, L.Rizzo, J.Crowcroft, "TCP-like Congestion Control for Layered Multicast Data Transfer", IEEE Infocom [VIC98B] Vicisano, L., "Notes On a Cumulative Layered Organization of Data Packets Across Multiple Streams with Different Rates", University College London Computer Science Research Note RN/98/25, Work in Progress (May 1998). A.1. Default FEC protocol The default FEC protocol is based on the FEC codec described in [RIZ97c]. This FEC codec is a small block small block codes that is described in more detail in [FECBB]. The FEC protocol ID for the default protocol is 0. The encoding flag E is set to 1 for packets that contain source symbols and to 0 for packet that contain redun- dant symbols. The object transmission label may be set arbitrarily. For example, an application may need to use well-known numbers. Alternatively, the transmission label may be the MD5 hash of the relevant object transmission session parameters, and its length in words is LTL. If LTI = 0 then there is no FEC object transmission information Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 21] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 carried in the ALC packet header, and thus the object length, the source block length and the symbol length must be obtained by the receiver out of band. If LTI = 1 then the receiver must obtain the source block length and the source symbol length out of band and the FEC object transmission information contains a 32-bit object length in units of bytes. If LTI = 2 then the FEC object transmission information contains a 40-bit object length in units of bytes, a 12- bit source block length in units of source symbols and a 12-bit sym- bol length in units of bytes. If LTI = 3 then the FEC object transmission information contains a 56-bit object length in units of bytes, a 12-bit source block length in units of source symbols, a 12-bit symbol length in units of bytes and a 16-bit remaining transmission time in seconds for the object. If F = 0 then the FEC payload ID consists of a 20-bit encoding block number and a 12-bit encoding symbol ID. If F = 1 then the FEC pay- load ID consists of a 48-bit encoding block number and a 16-bit encoding symbol ID. Figure 6 shows an example of the ALC header for the default protocol. In this example, LTL = 4, LTI = 3 and F = 1. No additional header fields or source authentication is used in this example. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 22] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Congestion control information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 9 | 0 |E|0| 4 | 3 |1|reservd| 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | 128-bits of MD5 hash of relevant | + + | object transmission session parameters | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object length (cont. | source block length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |SBL(c) | symbol length | remaining transmission time | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding block number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding block number (cont.) | encoding symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6 - Example ALC packet header for default FEC protocol A.2. DF FEC protocol The DF FEC protocol is based on large on demand codes. large on demand codes are described in more detail in [FECBB]. The FEC proto- col ID for the DF FEC protocol is 223. The encoding flag E is not used for the DF FEC protocol, and it MUST be set to 0 for all pack- ets. The object transmission label is the MD5 hash of the relevant object transmission session parameters, and its length in words is LTL. With the DF FEC protocol, the receiver calculates the source block length based on the symbol length and on the object length. If LTI = 0 then there is no FEC object transmission information carried in the ALC packet header, and thus the symbol length and the object length must be obtained by the receiver out of band. If LTI = 1 then the symbol length must be obtained by the receiver out of band and the FEC object transmission information contains a 32-bit object length in units of bytes. If LTI = 2 then the FEC object transmission information contains a 40-bit object length in units of bytes, a 12- bit symbol length and a 12-bit remaining transmission time in seconds Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 23] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 for the object. If LTI = 3 then the FEC object transmission informa- tion contains a 64-bit object length in units of bytes, a 16 bit sym- bol length and a 16-bit remaining transmission time in seconds for the object. If F = 0 then the FEC payload ID consists of a 32-bit encoding symbol ID. If F = 1 then the FEC payload ID consists of a 32-bit encoding block number and a 32-bit encoding symbol ID. Figure 7 shows an example of the ALC header for the default protocol. In this example, LTL = 4, LTI = 3 and F = 1. No additional header fields or source authentication is used in this example. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Congestion control information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 9 | 123 |0|0| 4 | 3 |1|reservd| 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | 128-bits of MD5 hash of relevant | + + | object transmission session parameters | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + 64-bits object length + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | symbol length | remaining transmission time | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding block number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 7 - Example DF FEC protocol packet header A.3. File Transfer using ALC - "Fcast" While ALC can be used to transfer arbitrary objects, file transfer is expected to be a primary application. This appendix describes a stan- dard for file transfer, called "Fcast". Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 24] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 When the object being transmitted is a file, the receiver usually requires "metadata" in addition to the file itself, such as the file name, its creation date, etc. Metadata can be sent a number of ways. For example, it could be part of the object session description or sent as a separate ALC object with a well-known object transmission label. The method described here combines the file with its metadata in a single ALC object. The metadata is logically appended to the end of the file as a trailer and sent as part of the transmission. The file with appended trailer is referred to as the extended file. In order to find the beginning of the trailer, the last 4 bytes in the object indicate the length of the trailer. Including metadata is OPTIONAL, so the length may be zero. Figure 8 shows the layout of the Fcast file transmission. The metadata is appended rather than prepended to the file so that the file length may be corrected by simply truncating the extended file (rather than requiring re-writing). The nature of ALC does not ensure that the start of the file is received before the end, so there is no drawback to using a trailer in terms of latency to get the information. +----------------------------------------------+ | Object | 4-byte checksum | Null padding| +----------------------------------------------+ / \ | ........... | \ | .......... / \ +--------------------------------------+ | File data | Trailer | Trailer Length | +--------------------------------------+ Figure 8 - Fcast file transmission: The ALC object is the file data, followed by the meta-data trailer, followed by the trailer length (in bytes - 4 byte value) The metadata in the file trailer is stored as ASCII text. It carries the same information as HTTP object metainformation header fields, as defined in RFC 2068 [R2068]. As in the RFC, field names should be followed by a colon, followed by the field value, followed by a CR- LF. The header fields that are RECOMMENDED/OPTIONAL to be supported by all receiving clients are listed below and should be interpreted as per RFC 2068. Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 25] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 RECOMMENDED fields: Content-Location (indicates the URI for the file - could be just the file name) Last-modified OPTIONAL fields: Content-Length (indicates the length of the file) Content-Encoding Content-Type Content-Base Content-Language Content-Style-Type Date Expires Any other header field defined in RFC 2068 or subsequent HTTP standards. Example: Content-Length : 1024 Content-Location : http://www.foo.com/myfile.zip Authors' Addresses Michael Luby luby@dfountain.com Digital Fountain 600 Alabama Street San Francisco, CA, USA, 94110 Jim Gemmell jgemmell@microsoft.com Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 26] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 Microsoft Research 301 Howard St., #830 San Francisco, CA, USA, 94105 Lorenzo Vicisano lorenzo@cisco.com cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134 Luigi Rizzo luigi@iet.unipi.it Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy Jon Crowcroft J.Crowcroft@cs.ucl.ac.uk Department of Computer Science University College London Gower Street, London WC1E 6BT, UK Bruce Lueckenhoff brucelu@cadence.com Cadence Design Systems, Inc. 120 Cremona Drive, Suite C Santa Barbara, CA 93117 Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 27] Internet Draft RMT PI, Asynchronous Layered Coding March 2000 Luby, Gemmell, Vicisano, Rizzo, Crowcroft, Lueckenhoff [Page 28]