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
<draft-ietf-rmt-pi-alc-00.txt>
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]
