From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc3738.txt | 1795 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1795 insertions(+) create mode 100644 doc/rfc/rfc3738.txt (limited to 'doc/rfc/rfc3738.txt') diff --git a/doc/rfc/rfc3738.txt b/doc/rfc/rfc3738.txt new file mode 100644 index 0000000..7c07f55 --- /dev/null +++ b/doc/rfc/rfc3738.txt @@ -0,0 +1,1795 @@ + + + + + + +Network Working Group M. Luby +Request for Comments: 3738 Digital Fountain +Category: Experimental V. Goyal + M.I.T. + April 2004 + + + Wave and Equation Based Rate Control (WEBRC) Building Block + +Status of this Memo + + This memo defines an Experimental Protocol for the Internet + community. It does not specify an Internet standard of any kind. + Discussion and suggestions for improvement are requested. + Distribution of this memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (2004). All Rights Reserved. + +Abstract + + This document specifies Wave and Equation Based Rate Control (WEBRC), + which provides rate and congestion control for data delivery. WEBRC + is specifically designed to support protocols using IP multicast. It + provides multiple-rate, congestion-controlled delivery to receivers, + i.e., different receivers joined to the same session may be receiving + packets at different rates depending on the bandwidths of their + individual connections to the sender and on competing traffic along + these connections. WEBRC requires no feedback from receivers to the + sender, i.e., it is a completely receiver-driven congestion control + protocol. Thus, it is designed to scale to potentially massive + numbers of receivers attached to a session from a single sender. + Furthermore, because each individual receiver adjusts to the + available bandwidth between the sender and that receiver, there is + the potential to deliver data to each individual receiver at the + fastest possible rate for that receiver, even in a highly + heterogeneous network architecture, using a single sender. + + + + + + + + + + + + + +Luby & Goyal Experimental [Page 1] + +RFC 3738 WEBRC Building Block April 2004 + + +Table of Contents + + 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 3 + 2. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 5 + 3. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 6 + 3.1. Sender Operation . . . . . . . . . . . . . . . . . . . . 9 + 3.1.1. Sender inputs and initialization. . . . . . . . . 9 + 3.1.2. Sending packets to the session. . . . . . . . . . 10 + 3.2. Receiver Operation . . . . . . . . . . . . . . . . . . . 12 + 3.2.1. Receiver inputs and initialization. . . . . . . . 12 + 3.2.2. Receiver measurements and calculations. . . . . . 13 + 3.2.2.1. Average loss probability . . . . . . . . 13 + 3.2.2.2. Average round-trip time. . . . . . . . . 16 + 3.2.2.3. Rate Equation. . . . . . . . . . . . . . 16 + 3.2.2.4. Epochs . . . . . . . . . . . . . . . . . 17 + 3.2.2.5. Average reception rate . . . . . . . . . 17 + 3.2.2.6. Slow start . . . . . . . . . . . . . . . 19 + 3.2.2.7. Target rate. . . . . . . . . . . . . . . 20 + 3.2.3. Receiver events . . . . . . . . . . . . . . . . . 20 + 3.2.3.1. Packet reception . . . . . . . . . . . . 20 + 3.2.3.2. First packet after join. . . . . . . . . 20 + 3.2.3.3. Time slot change . . . . . . . . . . . . 20 + 3.2.3.4. Loss event . . . . . . . . . . . . . . . 21 + 3.2.3.5. Epoch change . . . . . . . . . . . . . . 21 + 3.2.3.6. Join the next higher layer . . . . . . . 21 + 3.2.3.7. Join timeout . . . . . . . . . . . . . . 23 + 3.2.3.8. Exceptional timeouts . . . . . . . . . . 23 + 4. Applicability Statement . . . . . . . . . . . . . . . . . . . 23 + 4.1. Environmental Requirements and Considerations. . . . . . 23 + 5. Packet Header Fields. . . . . . . . . . . . . . . . . . . . . 25 + 5.1. Short Format Congestion Control Information. . . . . . . 26 + 5.2. Long Format Congestion Control Information . . . . . . . 27 + 6. Requirements From Other Building Blocks . . . . . . . . . . . 28 + 7. Security Considerations . . . . . . . . . . . . . . . . . . . 28 + 8. References. . . . . . . . . . . . . . . . . . . . . . . . . . 29 + 8.1. Normative References . . . . . . . . . . . . . . . . . . 29 + 8.2. Informative References . . . . . . . . . . . . . . . . . 30 + 9. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . 31 + 10. Full Copyright Statement. . . . . . . . . . . . . . . . . . . 32 + + + + + + + + + + + + +Luby & Goyal Experimental [Page 2] + +RFC 3738 WEBRC Building Block April 2004 + + +1. Introduction + + This document specifies Wave and Equation Based Rate Control (WEBRC). + WEBRC is a congestion control building block that is designed to be + massively scalable when used with the IP multicast network service. + WEBRC is also suitable as the basis for unicast congestion control, + but this is outside the scope of this document. WEBRC is designed to + compete fairly with TCP and similar congestion-controlled sessions. + WEBRC can be used as a congestion control protocol for any type of + data delivery, including reliable content delivery and streaming + delivery. + + WEBRC is a receiver-driven congestion control protocol in the spirit + of [5] and [18]. This means that all measurements and decisions to + raise or lower the reception rate are made by each individual + receiver, and these decisions are acted upon by sending join and + leave messages for channels to the network. A receiver using WEBRC + adjusts its reception rate without regard for other concerns such as + reliability. This is different from TCP, where the congestion + control protocol and the reliability protocol are intricately + interwoven. + + WEBRC takes the same basic equation-based approach as TFRC [9]. In + particular, each WEBRC receiver measures parameters that are plugged + into a TCP-like equation to compute the receiver target reception + rate and adjusts its reception rate up and down to closely + approximate the target reception rate. The sender sends packets to + multiple channels; one channel is called the base channel and the + remaining channels are called wave channels. Each wave channel + follows the same pattern of packet rate transmission spread out over + equally-spaced intervals of time. The pattern of each wave is that + it starts at a high rate and the rate decreases gradually and + continually over a long period of time. (Picture an infinite + sequence of waves.) The receiver increases its reception rate by + joining the next wave channel earlier in the descent of the wave than + it joined the previous wave channel, and the receiver decreases its + reception rate by joining the next wave channel later in the descent + of the wave than it joined the previous wave channel. + + The wave channels are ordered at each point in time from a lowest + layer to a highest layer. At each point in time, the lowest layer is + the wave channel that among all active wave channels is nearest to + the end of its active period; the highest layer is the wave channel + that is furthest from the end of its active period. Because waves + are dynamically becoming active and quiescent over time, the + designation of which wave channel is at which layer changes + dynamically over time. In addition to being joined to the base + channel, at each point in time a receiver is joined to a consecutive + + + +Luby & Goyal Experimental [Page 3] + +RFC 3738 WEBRC Building Block April 2004 + + + set of layers starting at the lowest layer and proceeding towards the + highest. + + WEBRC introduces a natural notion of a multicast round-trip time + (MRTT). An MRTT is measured individually by each receiver and + averaged as a substitute for conventional unicast round-trip time + (RTT). Because the throughput of a TCP session depends strongly on + RTT, having some measure of RTT is essential in making the WEBRC + equation-based rate control protocol "TCP-friendly". The use of the + MRTT also helps to coordinate and equalize the reception rates of + proximate receivers joined to a session behind a bottleneck link. + This implies that packets for the session that flow through the + bottleneck link are on average sent to almost all downstream + receivers, and thus the efficiencies of multicast are realized. + Furthermore, WEBRC is designed to be massively scalable in the sense + that the sender is insensitive to the number of receivers joined to a + multicast session. + + WEBRC is designed for applications that use a fixed packet size and + vary their packet reception rates in response to congestion. WEBRC + is designed to be reasonably fair when competing for bandwidth with + TCP flows, where a flow is "reasonably fair" if its reception rate is + generally within a factor of two of the reception rate of a TCP flow + under the same conditions. However WEBRC has a much lower variation + of throughput over time compared to TCP, which makes it more suitable + for applications such as telephony or streaming media where a + relatively smooth rate is of importance. The penalty of having + smoother throughput than TCP while competing fairly for bandwidth is + that WEBRC responds more slowly than TCP to changes in available + bandwidth. + + The receiver measures and performs the calculation of congestion + control parameters (e.g., the average loss probability, the average + MRTT) and makes decisions on how to increase or decrease its rate + based on these parameters. The receiver-based approach is well + suited to an application where the sender is handling many concurrent + connections and therefore WEBRC is suitable as a building block for + multicast congestion control. + + The paper [16] and technical report [15] provide much of the + rationale and intuition for the WEBRC design and describe some + preliminary simulations. + + This document describes a building block as defined in RFC 3048 [4]. + This document describes a congestion control building block that + conforms to RFC 2357 [3]. This document is a product of the IETF RMT + WG and follows the general guidelines provided in RFC 3269 [2]. The + key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", + + + +Luby & Goyal Experimental [Page 4] + +RFC 3738 WEBRC Building Block April 2004 + + + "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this + document are to be interpreted as described in BCP 14, RFC 2119 [1]. + +Statement of Intent + + This memo contains part of the definitions necessary to fully specify + a Reliable Multicast Transport protocol in accordance with RFC 2357. + As per RFC 2357, the use of any reliable multicast protocol in the + Internet requires an adequate congestion control scheme. This + document specifies an experimental congestion control scheme. While + waiting for initial deployment and experience to show this scheme to + be effective and scalable, the IETF publishes this scheme in the + "Experimental" category. + + It is the intent of the Reliable Multicast Transport (RMT) Working + Group to re-submit the specification as an IETF Proposed Standard as + soon as the scheme is deemed adequate. + +2. Rationale + + WEBRC provides congestion control for massively scalable protocols + using the IP multicast network service. The congestion control that + WEBRC provides is common to a variety of applications, including + reliable content delivery and streaming applications. + + WEBRC is designed to provide congestion control for all packets that + are sent to a session. A session comprises multiple channels + originating at a single sender that are used for some period of time + to carry packets pertaining to the transmission of one or more + objects that can be of interest to receivers. The logic behind + defining a session as originating from a single sender is that this + is the right granularity to regulate packet traffic via congestion + control. The rationale for providing congestion control that uses + multiple channels within the same session is that this allows the + data on the channels to be layered, which in turn allows each + receiver to control its reception rate by joining and leaving + channels during its participation in the session. There are + advantages to layered data for streaming, where the most important + data can be sent to the lower layers and incrementally valuable data + to the higher layers. For reliable content delivery, as described in + [13], an application can send in packets encoded data generated from + an object in such a way that the arrival of enough packets by a + receiver is sufficient to reliably reconstruct the original object. + A primary advantage of WEBRC is that each receiver controls it + reception rate independent of other receivers. Thus, for example, a + receiver with a slow connection to the sender does not slow down the + receivers with faster connections. + + + + +Luby & Goyal Experimental [Page 5] + +RFC 3738 WEBRC Building Block April 2004 + + + There are coding techniques that provide massively scalable + reliability and asynchronous delivery which are compatible with + WEBRC, e.g., as described in [11]. When combined the result is a + massively scalable, reliable, asynchronous content delivery protocol + that is network friendly. WEBRC also provides congestion control + that is suitable for streaming applications. + + WEBRC avoids using techniques that are not massively scalable. For + example, WEBRC does not provide any mechanisms for sending + information from receivers to senders, although this does not rule + out protocols that both use WEBRC and that send information from + receivers to senders. + + WEBRC provides congestion control that can be tuned for different + applications that may have differing application requirements. For + example, a content delivery protocol may aggressively strive to use + all available bandwidth between receivers and the sender, and thus to + maintain fairness it must drastically reduce its rate when there is + competing traffic. On the other hand, a streaming delivery protocol + may strive to maintain a constant rate instead of trying to use all + available bandwidth, and thus it may not reduce its rate as fast when + there is competing traffic. + + WEBRC does not provide any support beyond congestion control, and + thus WEBRC is to be combined with other building blocks to provide a + complete protocol instantiation. For example, WEBRC does not provide + any means that can be used to identify which session each received + packet belongs to. As another example, WEBRC does not provide + support for identifying which object each packet is carrying + information about. + +3. Functionality + + A WEBRC session comprises a logically related set of channels + originating from a single sender that are used for some period of + time to carry data packets with a header carrying WEBRC Congestion + Control Information. When packets are received, they are first + checked to see that they belong to the appropriate session before + WEBRC is applied. A session label defined by a protocol + instantiation may be carried in each packet to identify to which + session the packet belongs. For example, if LCT [12] is being used + with the session, then the sender IP address together with the + Transport Session Identifier supported by LCT would be used to + determine which session a received packet belongs to. The particular + details of how this filtering is performed is outside the scope of + this document. In the remainder of this document, references to + channels are always within the scope of a single session. + + + + +Luby & Goyal Experimental [Page 6] + +RFC 3738 WEBRC Building Block April 2004 + + + A channel can be uniquely identified at the network layer by a + (sender IP address, multicast group address) pair, and this is the + address to which the receiver sends messages to join and leave the + channel. The channels used by a WEBRC session are mapped uniquely to + consecutive channel numbers. In each packet sent to a channel, the + channel number that corresponds to the channel is carried in the + WEBRC Congestion Control Information. A WEBRC receiver uses the + channel number to determine which channel within a session a packet + is received from. + + At the sender, time is partitioned into time slots, each of duration + TSD seconds. There is a fixed number T of time slot indices + associated with a session. As time progresses, the current time slot + index increases by one modulo T each TSD seconds. The current time + slot index CTSI is carried in the WEBRC Congestion Control + Information. This allows receivers to perform very coarse-grained + synchronization within a session. + + WEBRC congestion control is achieved by having the sender send + packets associated with a given session to several different + channels. Individual receivers dynamically join and leave these + channels according to the network congestion they experience. These + congestion control adjustments are performed at each receiver + independently of all other receivers, without any impact on the + sender. A packet sequence number is carried in the WEBRC Congestion + Control Information. The packet sequence numbers are consecutively + numbered per channel and are used by receivers to measure packet + loss. + + The channels associated with a session consist of one base channel + and T wave channels. The packet rate for each channel varies over + time. For the base channel, packets are sent to the channel at a low + rate BCR_P at the beginning of a time slot and this rate gradually + decreases to P*BCR_P at the end of the time slot, where P < 1 is a + constant defined later. This pattern for the base channel repeats + over each time slot. For each wave channel i, packets are sent to + channel i at a rate that first increases very quickly to a high rate + and then decreases over time by a fixed fraction P per time slot + until a rate of BCR_P is reached at the end of time slot i. Then, + for a period of time called the quiescent period, no packets are sent + to wave channel i, and thereafter the whole cycle repeats itself, + where the duration of the cycle is T*TSD seconds. Thus, the wave + channels are going through the same cyclic pattern of packet rate + transmission spaced out evenly by TSD seconds. + + Before joining a session, the receivers MUST obtain enough of the + session description to start the session. This MUST include the + relevant session parameters needed by a receiver to participate in + + + +Luby & Goyal Experimental [Page 7] + +RFC 3738 WEBRC Building Block April 2004 + + + the session and perform WEBRC congestion control. The session + description is determined by the sender and is typically communicated + to the receivers out of band. How receivers obtain the session + description is outside the scope of this document. + + When a receiver initiates a session, it first joins the base channel. + The packets in the base channel help the receiver orient itself in + terms of what the current time slot index is, which in turn allows + the receiver to know the relative rates on the wave channels. The + receiver remains joined to the base channel for the duration of its + participation in the session. + + At each point in time the active (non-quiescent) wave channels are + ordered into layers, where the lowest layer is the active wave + channel whose wave is nearest to completion and the highest layer is + the active wave channel whose wave is furthest from completion. + (This is almost the same as saying that the lowest layer has the + lowest rate and the highest layer has the highest rate. The possible + deviation from this is due to the optional non-exponential beginnings + of the waves as described in [8].) Each time a wave channel becomes + active, it is the highest layer. At the end of each time slot the + lowest-layer wave channel becomes quiescent, and thus all active wave + channels move down a layer at this point in time. At each point in + time a receiver is joined to the base channel and a consecutive set + of layers starting with the lowest. Each time a receiver joins a + wave channel it joins the lowest layer not yet joined. A receiver + always leaves the lowest layer when it becomes quiescent. + + After joining a session the receiver adjusts its rate upwards by + joining wave channels in sequence, starting with the lowest layer and + moving towards the highest. The rates on the active wave channels + are decreasing with time, so the receiver adjusts its rate downwards + simply by refraining from joining additional wave channels. Since + the layer ordering among the channels changes dynamically over time + depending on the current time slot index, it is important that the + receiver continually monitor the current time slot index contained in + received packets. The reception rate at the receiver is determined + by how early each wave channel is joined by the receiver: the earlier + the receiver joins a channel with respect to when its wave started, + the higher the reception rate. + + Once the receiver is joined to a wave channel, the receiver remains + joined to the wave channel until the channel goes quiescent, at which + point the receiver MUST leave the channel. + + The way the receiver adjusts its reception rate is inspired by TFRC + [9]. The receiver at all points in time maintains a target reception + rate, and the receiver is allowed to join the next wave channel if + + + +Luby & Goyal Experimental [Page 8] + +RFC 3738 WEBRC Building Block April 2004 + + + after joining its anticipated reception rate from all the layers it + is joined to would be at most its target reception rate. The target + rate is continually updated based on a set of measured parameters. + The primary parameters are an estimate LOSSP of the average loss + probability and an estimate ARTT of the average multicast round-trip + time. + + In the remainder of this document, log(X) denotes the natural + logarithm of X, i.e., the logarithm base 2.71828459... of X. + +3.1. Sender Operation + + The sender operation is by design much simpler than the receiver + operation. + +3.1.1. Sender inputs and initialization + + The primary input to the sender for the session is SR_b. SR_b is an + upper bound to the sender transmission rate in bits per second at any + point in time (with some reasonable granularity) in aggregate to all + channels. Naturally, this is then also the maximum rate in bits per + second that any receiver could receive data from the session at any + point in time. It is RECOMMENDED that the sender transmission rate + in aggregate to all channels be made constant as described in [8]. + It is also RECOMMENDED that the session description indicate whether + the aggregate transmission rate is constant, unless there is no + ambiguity. + + The secondary inputs to the sender are listed below. These inputs + are secondary because their values will generally be fixed to default + values that will not change, because they will be derived from SR_b, + or because they are chosen based on non-WEBRC considerations. + + o LENP_B is the length of packets in bytes sent to the session. The + value of LENP_B depends on the complete protocol, but in general + this SHOULD be set to as high a value as possible without + exceeding the MTU size for the network that would cause + fragmentation. + + o BCR_P is the transmission rate on the base channel at the + beginning of a time slot in packets per second. The default value + for BCR_P is 1. + + o TSD is the time slot duration measured in seconds. The + RECOMMENDED value for TSD is 10. + + o QD is the minimum quiescent period duration measured in seconds. + The RECOMMENDED value for QD is 300. + + + +Luby & Goyal Experimental [Page 9] + +RFC 3738 WEBRC Building Block April 2004 + + + o P is the multiplicative drop in every channel rate over each time + slot. The default value for P is 0.75. + + o N is the duration in time slots for each wave. N is also the + number of wave channels active at any time. (A wave channel is + called active when it is not quiescent.) A sender may choose any + value that allows it to produce waves that substantially follow + the required exponential shape described in Section 3.1.2. A + RECOMMENDED mechanism for relating N to SR_b, BCR_P and P is + described in [8]. + + From these inputs the following fixed sender parameters can be + derived as follows. + + o SR_P = SR_b/(8*LENP_B) is the sender transmission rate in packets + per second. + + o BCR_b = 8*LENP_B*BCR_P is the rate of the base channel at the + beginning of a time slot in bits per second. + + o L = ceil(BCR_P*TSD*(P-1)/log(P)) is the number of base channel + packets sent in each time slot. + + o Q = ceil(QD/TSD) is the number of quiescent time slots per cycle + for a wave channel. + + o T = N + Q is the total number of time slots in a cycle. T is also + the total number of wave channels. + + o For the base channel CN = T and for the wave channels CN = + 0,1,...,T-1. The sender has the description of the channels + assigned to the session and the mapping between the channels and + the CNs. + + o C = TSD*T is the total duration of a cycle in seconds. + +3.1.2. Sending packets to the session + + The sender keeps track of the current time slot index CTSI. The + value of CTSI is incremented by 1 modulo T each TSD seconds. The + value of CTSI is placed into each packet in the format described in + Section 5. For each packet sent to the session, the sender also + places the channel number CN of the channel into the packets in the + format described in Section 5. Recall that CN = T for the base + channel and CN = 0,1,...,T-1 for the wave channels. + + + + + + +Luby & Goyal Experimental [Page 10] + +RFC 3738 WEBRC Building Block April 2004 + + + For each packet sent to the session, the sender calculates a packet + sequence number PSN and places it into the packet. The value of PSN + is scoped by CN, and the value of PSN is consecutively increasing + within each channel. Furthermore, for each wave channel, the last + packet sent before the channel becomes quiescent must have the + maximum possible PSN value. When the short format for Congestion + Control Information is used (see Section 5.1), this implies that for + any wave channel the last PSN value sent to the channel just before + the channel becomes quiescent is 2^16-1 = 65,535. Similarly, when + the long format for Congestion Control Information is used (see + Section 5.2), the PSN for the final packet of any wave is 2^32-1 = + 4,294,967,295. The PSN of the initial packet of a wave thus depends + on TSD, P, BCR_P and SR_P. For the base channel, the first packet of + each time slot has a PSN congruent to zero modulo L. Hence, instead + of 2^16 - 1 or 2^32 - 1 being the highest PSN used (depending on the + choice of short format or long format Congestion Control + Information), the highest PSN is one less than the largest multiple + of L that does not exceed 2^16 (short format) or 2^32 (long format). + The format for the PSN within packets is described in Section 5. + + The rate at which packets are sent to the base channel starts at + BCR_P packets per second at the beginning of each time slot and + decreases exponentially to P*BCR_P at the end of that time slot. + + The packet rate for the wave channels is more complicated. Each wave + channel carries a sequence of waves separated by quiescent periods. + On each wave channel each wave is active during N time slots followed + by a quiescent period of Q time slots. The waves on wave channel i + end at the ends of time slots with CTSI i. Therefore wave channel i + is active during time slots i-N+1 modulo T, i-N+2 modulo T, ..., i + and is quiescent for time slots i+1 modulo T, i+2 modulo T, ..., i+Q + modulo T. Wave channel i first becomes active within time slot i-N+1 + modulo T at a point in time that may depend on the value of SR_b. + + Except for at most the first two time slots after a wave becomes + active, the packet rate of the wave MUST decrease exponentially by a + factor of P per TSD seconds, down to a rate of BCR_P at the end of + the last active time slot. At the beginning of each wave, i.e., for + at most the first two time slots when the wave becomes active, the + rate MAY deviate from this exponential form so that the total sending + rate in aggregate to all of the channels is constant. A RECOMMENDED + design for the beginnings of waves to achieve this goal is described + in [8]. + + + + + + + + +Luby & Goyal Experimental [Page 11] + +RFC 3738 WEBRC Building Block April 2004 + + +3.2. Receiver Operation + + The bulk of the complexity in WEBRC is in the receiver operation. + For ease of explanation, suppose for the moment that during the + reception there is no packet loss and packets are arriving at exactly + the rate at which they were sent. The sender transmission rate to + the channels is designed so that the receiver reception rate behaves + as follows. + + Upon entering a session, the receiver immediately joins the base + channel. When the receiver wants to increase its rate, it joins + consecutive layers starting with the lowest and moving towards the + highest. (Recall that the designations of lowest to highest change + as waves become active and quiescent.) When the receiver wants to + maintain its current reception rate and it is already joined to the + lowest NWC layers, if the receiver joins channel i-1+NWC modulo T + sometime during time slot i then the receiver joins channel i+NWC + modulo T TSD seconds later in time slot i+1. When the lowest layer + becomes quiescent the receiver leaves the channel. + + Suppose the receiver wants to decrease its rate till it is joined to + just the base channel. Assume that a receiver is joined to the + lowest NWC < N-2 layers at the beginning of time slot i, i.e., wave + channels i, i+1 modulo T,..., i+NWC-1 modulo T. Then, the aggregate + packet reception rate of the receiver over the next NWC time slots + will behave as follows if the receiver does not join any wave + channels during this time. At the beginning of time slot i the + receiver reception rate is BCR_P*(1 + (1/P) + (1/P)^2 + ... + + (1/P)^NWC). Then the receiver reception rate decreases by a factor + of P over the duration of each time slot, and at the end of each time + slot the reception rate decreases by an additive amount of P*BCR_P. + At the end of time slot i+NWC-1 mod T, the receiver reception rate is + BCR_P*(1+P), and at the beginning of time slot i+NWC mod T the + receiver is joined only to the base channel and its reception rate is + BCR_P. + +3.2.1. Receiver inputs and initialization + + Before joining a session the receiver MUST know the mapping between + the CNs and the channels. Upon joining the session or shortly + thereafter, it SHOULD have the values of LENP_B, BCR_P, TSD, P, N, L, + Q and T. Some of these values may be computed or measured once the + receiver has joined the session. For example, the receiver MAY + obtain LENP_B and T from the first packet received from the base + channel, and the receiver MAY measure BCR_P once it is joined to the + base channel. The values of P, Q and TSD MAY be fixed to default + values built into the receiver that do not change from session to + session, and the value of N MAY be computed as T-Q. The receiver + + + +Luby & Goyal Experimental [Page 12] + +RFC 3738 WEBRC Building Block April 2004 + + + SHOULD know whether the sender is employing a technique to produce + constant aggregate rate as described in [8]. + + When a receiver first joins a session, it MUST first join just the + base channel and start receiving packets to determine the current + time slot index. If during the course of the session the receiver + continually loses a high fraction of the packets from the base + channel even when the receiver is only joined to the base channel, + the receiver SHOULD leave the session. + + The receiver MAY also have other individually set parameters that may + be used to determine its behavior. One such parameter is MRR_b: + + o MRR_b is the maximum receiver reception rate in bits per second. + This may be used to determine the maximum reception rate this + receiver is willing to reach. Thus, the maximum reception rate + that the receiver can possibly achieve in the session is the + minimum of SR_b and MRR_b. A recommended value of MRR_b for a + receiver is the bandwidth capacity of the last link to the + receiver. MRR_P is the maximum receiver reception rate in packets + per second, i.e., MRR_P = MRR_b/(8*LENP_B). + +3.2.2. Receiver measurements and calculations + + As outlined in the introduction, the way a receiver adjusts its + reception rate is inspired by TFRC [9]. The receiver at all points in + time maintains a target reception rate, and the receiver is allowed + to join the next wave channel if joining would increase its reception + rate to at most its target reception rate. The target rate is + continually updated based on a set of measured parameters. + + Two primary parameters are the estimate LOSSP of the average loss + probability and the estimate ARTT of the average MRTT. Both LOSSP + and ARTT are moving averages of measurements based on discrete + events. For many of the other estimates calculated by WEBRC, using + an exponentially weighted moving average (EWMA) with a fixed + averaging fraction is sufficient. However, the calculations of LOSSP + and ARTT require a more general and sophisticated filtering approach. + +3.2.2.1. Average loss probability + + The design of TFRC [9] reflects that, because the average packet loss + probability can vary by orders of magnitude, any estimate of the + average loss probability based on either a fixed number of packets or + on a fixed period of time with a fixed averaging fraction will be + poor. In TFRC the average is estimated from the numbers of packets + between beginnings of loss events, and the number of loss events used + is fixed. + + + +Luby & Goyal Experimental [Page 13] + +RFC 3738 WEBRC Building Block April 2004 + + + The estimate LOSSP of the average loss probability of the receiver is + maintained in a manner somewhat similar to that described in TFRC + [9]. The WEBRC receiver estimates the inverse of the average loss + probability by applying two EWMA filters to the packet reception + measurements, a time-based filter with smoothing constant 0 < Nu < 1 + and a loss-based filter with smoothing constant 0 < Delta < 1. The + recommended values for the smoothing constants are Nu = 0.3 and Delta + = 0.3. The reason for the time-based filter is that the loss events + in WEBRC are bursty; they typically occur just after a new wave has + been joined. To smooth out this burstiness, the time-based filter is + applied to the packet reception measurements at the end of each epoch + to smooth out the bursty loss events over a few time slot durations. + Intuitively, the time-based filter averages packet reception events + such that the events are smoothed out over an interval of time + proportional to TSD/Nu seconds. The loss-based filter, similar to + what is suggested in TFRC, is applied to the output of the time-based + filter to produce the estimate of the inverse of the average loss + probability. Intuitively, the loss-based filter averages loss events + such that each loss event is averaged in with weight Delta. + + As described later, LOSSP is initialized at the end of slow start and + occasionally reset due to other events. Let W and X be counts of + packets, let Y be a count of loss events and let Z be the long-term + estimate of the inverse of the average loss probability. Whenever + the value of LOSSP is initialized or reset, the values of W, X, Y and + Z are also initialized or reset. + + Recall that TSD is the duration of a time slot. The epoch length EL + is the duration of time between decisions to adjust the reception + rate. Generally EL is much smaller than TSD, and the RECOMMENDED + values are EL = 0.5 seconds and TSD = 10 seconds. + + Define G = Nu*EL/TSD as the amount of time-based smoothing to perform + at the end of each epoch. The update rules for W, X, Y, Z, and LOSSP + are the following: + + o At the end of each epoch, adjust X, Y and Z and compute LOSSP as + follows: + + Z = Z*(1-Delta)^(G*Y) + G*X/(G*Y+1)*(1-(1-Delta)^(G*Y+1)) + + X = X*(1-G) + + Y = Y*(1-G) + + Z1 = Z*(1-Delta)^Y + X/(Y+1)*(1-(1-Delta)^(Y+1)) + + Z2 = Z*(1-Delta)^(Y+1) + (X+W+1)/(Y+2)*(1-(1-Delta)^(Y+2)) + + + +Luby & Goyal Experimental [Page 14] + +RFC 3738 WEBRC Building Block April 2004 + + + LOSSP = 1/max{Z1,Z2,1} + + o For each packet event (whether it is a received packet or a lost + packet), W = W + 1 + + o At the beginning of each loss event, update W, X, and Y as + follows: + + X = X + W + + W = 0 + + Y = Y + 1 + + The intuition behind these update rules is the following. If just + loss-filtering were used to update Z, then Z would be decreased by a + multiplicative amount 1 - Delta for each loss event and Z would be + increased by an additive amount Delta for each packet. To smooth out + loss events over more than one time slot, these adjustments are + filtered into Z over time, at the rate of a fraction G at the end of + each epoch. Thus, the variables X and Y are counts of the portions + of the packets and loss events, respectively, that have not yet been + filtered into the long-term memory Z. W is the count of packets + since the last loss event started. This explains why W is increased + by one for each packet and Y is increased by one for each loss event. + At the end of each epoch a fraction G of both X and Y are filtered + into Z according to the loss-filter rule described above, and then + the same fraction G is removed from both X and Y to account for the + fact that this portion has been filtered into Z. The LOSSP + calculation combines the short-term history (X,Y) with the long-term + history Z and also allows the arrivals since the last loss W to have + some influence. The value of Z2 is what Z1 would become were the + next packet to be lost. + + To reset the loss calculation to a value LOSSP = a, the state + variables are set as follows: + + W = 0 + + X = 0 + + Y = 0 + + Z = 1/a + + + + + + + +Luby & Goyal Experimental [Page 15] + +RFC 3738 WEBRC Building Block April 2004 + + +3.2.2.2. Average round-trip time + + The receiver maintains an average round-trip time, ARTT, as a + measurement-based filter of MRTT measurements using a smoothing + constant 0 < Alpha < 1. The RECOMMENDED value for Alpha is 0.25. + + Each time the receiver joins a channel (either the base channel upon + entering a session or wave channels continually), it makes a + measurement of the multicast round-trip time MRTT as follows. Let V + be an auxiliary variable that is used that keep track of the average + of the square of the MRTT measurements. When the receiver sends the + join for the channel it records the current time JoinTime and sets a + Boolean variable JOINING to true. When the first packet is received + from the channel the receiver records the current time FirstTime and + resets the value of JOINING to false. If it is the base channel that + has been joined, ARTT is set to FirstTime-JoinTime and V is set to + ARTT*ARTT. Otherwise, the value of MRTT is set to (FirstTime - + JoinTime) - log(1/P)/2/(1-P)/BCR_P * P^NWC. (Note that this value + can be negative.) Then, ARTT is updated as follows. Let Omega = + Alpha*ARTT*ARTT/V, and at the Kth MRTT measurement let Rho = + Omega/(1-(1-Omega)^(K+1)). (Note that as K grows Rho approaches + Omega.) Then, V is updated to (1-Rho)*V+Rho*MRTT*MRTT and ARTT is + updated to max{P*ARTT,(1-Rho)*ARTT+Rho*MRTT}. + + Usually ARTT is updated to the second term in the max, and in this + case ARTT is the EWMA of the previous value of ARTT and the new MRTT, + with a weighting on the new MRTT that as K grows is proportional to + the square of the previous ARTT divided by the previous average V of + the square of the MRTT. Thus, if there is not much variance in the + previous MRTTs relative to the square of their average then the new + MRTT will be filtered into ARTT with a high weight, whereas if there + is a lot of variance in the previous MRTTs relative to the square of + their average then the new MRTT will be filtered into ARTT with a low + weight. The intuitive rationale for this is that in general the + number of measurements needed to compute a meaningful average for a + random variable is proportional to its variance divided by the square + of its average; see, e.g., [6]. By making the weight factor depend on + previous measurements in this way, the appropriate weight to use to + average the new MRTT into the ARTT self-adjusts automatically to the + variability in the measurements. + +3.2.2.3. Rate Equation + + The receiver calculates the reception rate REQN based on the TCP + equation as follows: REQN = 1/(ARTT*sqrt{LOSSP}(0.816 + + 7.35*LOSSP*(1+32*LOSSP^2))). This equation comes from TFRC [9]. + + + + + +Luby & Goyal Experimental [Page 16] + +RFC 3738 WEBRC Building Block April 2004 + + +3.2.2.4. Epochs + + The receiver makes decisions on whether or not to join another wave + channel at equally-spaced units of time called epochs. The duration + of an epoch in seconds, EL, is set to be a small fraction of TSD, so + that decisions to join a channel can be made at a much finer + granularity than TSD. A standard setting is EL = TSD/20. Thus, with + the recommended setting of TSD = 10, it is RECOMMENDED that EL = 0.5. + +3.2.2.5. Average reception rate + + There are two averaged reception rates maintained by the receiver: + TRR_P, the true reception rate, and ARR_P, the anticipated reception + rate. These are used for different purposes and thus are calculated + quite differently. Recommended values for the filtering weights Beta + and Zeta are provided at the end of this subsection. + + In start-up mode, the true reception rate TRR_P is used to ensure + that the receiver does not increase its reception rate too quickly + above its current reception rate. In the transition from start-up + mode to normal operation and in normal operation, TRR_P is used in + setting the slow start rate. TRR_P is calculated based on the + measurement of RR_P, where RR_P is the receiver reception rate in + packets per second measured at the beginning of an epoch averaged + over the epoch that just ended. TRR_P is initialized to BCR_P + + k*log(P)/TSD when the first base channel packet of the session + arrives, where k is the PSN of the packet reduced modulo L. TRR_P is + updated to (1-Zeta)*TRR_P + Zeta*RR_P at the beginning of each epoch + after RR_P is measured for the previous epoch. + + The anticipated reception rate ARR_P is the receiver's estimate of + the total instantaneous rate of the currently joined channels. It is + used to compare against the target rate to decide whether or not the + receiver should increase its reception rate by joining the next + higher unjoined layer. ARR_P is calculated based on a measurement + IRR_P and on the number of joined wave channels NWC. The ideal + reception rate IRR_P is the reception rate in packets per second + including both received and lost packets; like RR_P, it is measured + at the beginning of the epoch and averaged over the previous epoch. + ARR_P, IRR_P and NWC are updated as follows: + + o NWC is initialized to 0. + + o When the first base channel packet arrives, ARR_P is set to BCR_P + + k*log(P)/TSD, where k is the PSN of the packet reduced modulo L. + + + + + + +Luby & Goyal Experimental [Page 17] + +RFC 3738 WEBRC Building Block April 2004 + + + o At the beginning of each epoch, IRR_P is measured over the + previous epoch and then ARR_P is updated to + P^(EL/TSD)*(1-Beta)*ARR_P + Beta*IRR_P. Then if ARR_P exceeds + ARR_P_max = ((1/P)^(NWC+1)-1)/((1/P)-1)*BCR_P, ARR_P is updated to + ARR_P_max. + + o When a join is made to the next higher unjoined layer, NWC is + updated to NWC+1 and then ARR_P is multiplicatively increased by + the factor ((1/P)^(NWC+1)-1)/((1/P)^NWC-1). (Joins happen at + epoch boundaries; this adjustment is in addition to the adjustment + above.) + + o Each time a next time slot index is detected, ARR_P is additively + increased by (1-P)*BCR_P to account for the change in rate on the + base channel. In addition, the bottom layer in the previous time + slot has just gone quiescent and thus a message to leave this + layer has been sent, ARR_P is additively decreased by BCR_P and + NWC is decremented by 1. Thus, the combination of these effects + on ARR_P is that it is additively decreased by P*BCR_P. + + Consider for the moment what happens if Beta = 0 and ARR_P is an + accurate estimate of the total rate of the joined channels. The + adjustments to ARR_P upon joining and leaving wave channels, with the + passage of epochs, and with the detection of time slot changes will + then cause ARR_P to remain an accurate estimate. In practice, Beta + MUST be positive; allowing an influence of IRR_P prevents ARR_P from + drifting away from being an accurate estimate of the total joined + rate. + + The motivation for separate estimates TRR_P and ARR_P is as follows. + ARR_P is needed for comparison with the TFRC-inspired target rate + because there is no lag before it reflects the potential rate + increase resulting from joining the next higher layer and because it + measures the total possible impact on the network since it also + includes lost packets. TRR_P is needed because it reflects the rate + of data arriving at the receiver and this is used to ensure that + there is not a large gap between the joined rate and the receiving + rate. + + The recommended values for Beta and Zeta depend on whether the + receiver is in start-up mode (SSR_P = infinity). In start-up mode, + it is RECOMMENDED that Beta = (1 - P^(0.25))/2 and Zeta = sqrt(P)/(1 + + sqrt(P)). In normal operation, it is RECOMMENDED that Beta = 1 - + (P/(1+P))^(EL/TSD) and Zeta = 2*EL/(4+TSD). + + + + + + + +Luby & Goyal Experimental [Page 18] + +RFC 3738 WEBRC Building Block April 2004 + + +3.2.2.6. Slow start + + WEBRC uses a slow start mechanism to quickly ramp up its rate at both + the beginning of the session and in the middle of a session when the + rate drops precipitously. To enact this, the receiver maintains the + following parameters: + + o SSMINR_P is the minimum allowed slow start threshold rate in + packets per second. The recommended value for SSMINR_P is + BCR_P*(1+1/P+1/P^2). + + o SSR_P is the slow start threshold rate in packets per second. It + is adjusted at the beginning of loss events as described in + Section 3.2.3.4. SSR_P is initialized to infinity and is first set + to a finite value when the receiver leaves the initial start-up + period as described below. + + At the beginning of a session, the receiver cannot compute a + meaningful target rate from its measurements. Thus, it uses SSR_P = + infinity until one of the following events causes an end to this + start-up mode: + + o A packet loss is detected. In this case the value of SSR_P is + updated to max{SSMINR_P, P*TRR_P} as with the beginning of any + other loss event. + + o A sharp increase in MRTT is detected. While SSR_P = infinity the + receiver MUST compute, in the notation of Section 3.2.2.2, + differences in successive measurements of (FirstTime-JoinTime) + from successive waves and MUST set SSR_P to max{SSMINR_P, P*TRR_P} + when a large increase in (FirstTime-JoinTime) is observed. It is + RECOMMENDED that an increase in (FirstTime-JoinTime) be considered + large if it exceeds (P^(NWC+1)-1)/(P*log(P)) / ARR_P. + + o The maximum reception rate is reached. When SSR_P = infinity, if + (P^(-NWC-2)-1)/(P^(-NWC-1)-1)*ARR_P exceeds MRR_P or SR_P, the + receiver MUST set SSR_P to max{SSMINR_P, TRR_P}. + + o TRR_P is not increasing consistent with the last join of a wave + channel. While SSR_P = infinity, it is RECOMMENDED that the + receiver wait at least one full epoch after the first packet of a + wave is received before joining the next wave. If the TRR_P after + that full epoch is greatly below ARR_P the receiver SHOULD NOT + join and SHOULD then set SSR_P to max{SSMINR_P, TRR_P}. It is + RECOMMENDED that TRR_P be considered greatly below ARR_P if TRR_P + < c * ARR_P - 2/EL, where c = Zeta + (1-Zeta)*(P^(-EL/TSD))*(Zeta + + (1-Zeta)*sqrt(P)*(P^(-EL/TSD)))/g with g = (P^(-NWC-1)-1)/(P^(- + NWC)-1). + + + +Luby & Goyal Experimental [Page 19] + +RFC 3738 WEBRC Building Block April 2004 + + + In any of these four cases, the variables associated with LOSSP are + reset to make REQN, calculated as in Section 3.2.2.3 with the current + value of ARTT, equal TRR_P. + +3.2.2.7. Target rate + + In typical operation, SSR_P has a finite value and the target rate + TRATE is computed as TRATE = min{max{SSR_P, REQN}, MRR_P}. When + SSR_P = infinity, TRATE is computed as TRATE = min{4*TRR_P, MRR_P}. + +3.2.3. Receiver events + + There are various receiver events, some of which are triggered by the + passing of time on the receiver, and others by events such as packet + reception, detection of packet loss, reception of a first packet from + a channel, and exceptional time-outs. + +3.2.3.1. Packet reception + + Most packet reception events require the receiver to merely register + the reception for later calculation of RR_P and IRR_P (see Section + 3.2.2.5) and increment W for later calculation of LOSSP (see Section + 3.2.2.1). + + Additional actions, described in the following three subsections, are + required if the packet is the first packet received in response to a + join operation, the CTSI of the packet indicates a time slot change, + or the CN and PSN of the packet indicate a packet loss. + +3.2.3.2. First packet after join + + When channel i is the most recently joined channel and the Boolean + variable JOINING is true, the reception of a packet with PSN = i is a + special event because it is the first packet received in response to + the most recent join. MRTT is calculated and ARTT and V are updated + as described in Section 3.2.2.2, and JOINING is set to false. The + first received packet of the session furthermore necessitates + initialization of ARR_P and TRR_P as described in Section 3.2.2.5. + +3.2.3.3. Time slot change + + This is an event that is triggered by the reception of a packet with + a CTSI value that is one larger modulo T than the previous CTSI + value. When a packet with a new CTSI = i is received, a leave is + sent for the lowest layer in the previous time slot, i.e., wave + channel i-1 modulo T, NWC is updated to NWC-1, and ARR_P is updated + + + + + +Luby & Goyal Experimental [Page 20] + +RFC 3738 WEBRC Building Block April 2004 + + + to ARR_P - P*BCR_P as described in Section 3.2.2.5. If the channel + for which the leave is sent is also the most recently joined wave + channel and JOINING is true, then JOINING is set to false. + + It is possible due to packet reordering for some packets from the + previous time slot to be received after packets from the current time + slot. It is RECOMMENDED that measures be put into place to handle + this situation appropriately, i.e., to not trigger a time slot change + in this situation. One simple mechanism for this is as follows: + Compute the difference i-j modulo T, where i is the CTSI of the + received packet and j is the current CTSI of the receiver. A + difference of zero is, of course, not a time slot change. In + addition, a very large difference, for example a difference larger + than T-Q/2, should also not trigger a time slot change. + +3.2.3.4. Loss event + + Each time the receiver detects a lost packet (based on the sequence + numbers in the packets scoped by the channel number), the receiver + records the start of a new loss event and sets a Boolean variable + LOSS_EVENT to true that will automatically reset to false after ARTT + seconds. All subsequent packet loss for a period of ARTT seconds is + considered as part of the same loss event. When a start of a loss + event is detected, the value of SSR_P is updated to max{SSMINR_P, + P*TRR_P}. + + It is RECOMMENDED that the receiver account for simple misordering of + packets without inferring a loss. + +3.2.3.5. Epoch change + + This is an event that is triggered by the passage of time at the + receiver, which occurs each EL seconds. When this happens, TRR_P and + ARR_P are computed as described in Section 3.2.2.5. Immediately after + these updates, a decision is made about whether to join the next + higher layer as described in Section 3.2.3.6. + +3.2.3.6. Join the next higher layer + + At the beginning of each epoch, after updating the values of ARR_P + and TRR_P as described in Section 3.2.2.5, the receiver decides + whether or not to join the next higher layer as follows: + + o If the first base channel packet has not yet arrived the receiver + MUST not join. + + o If there is a loss event in progress (LOSS_EVENT = true) the + receiver MUST not join. + + + +Luby & Goyal Experimental [Page 21] + +RFC 3738 WEBRC Building Block April 2004 + + + o If a join of a channel is in progress (JOINING = true) the + receiver MUST not join. + + o If NWC = N the receiver MUST not join. + + o If the receiver is employing the OPTIONAL rule described in + Section 3.2.2.6, SSR_P = infinity, and a full epoch has not passed + since the first packet arrival on the most recently joined wave + channel then the receiver MUST not join. + + o If the receiver is employing the OPTIONAL rule described in + Section 3.2.2.6, SSR_P = infinity, and a full epoch has passed + since the first packet arrival on the most recently joined wave + channel, then the receiver checks if TRR_P is greatly below ARR_P + as described in Section 3.2.2.6. If TRR_P is greatly below ARR_P + the receiver MUST not join. + + o The receiver calculates REQN as described in Section 3.2.2.3. + + o The receiver calculates TRATE as described in Section 3.2.2.7. + + o If the sender is not sending at constant aggregate rate and TRATE + < ARR_P*((1/P)^{NWC+2}-1)/((1/P)^{NWC+1}-1), the receiver MUST not + join. If the sender is sending at constant aggregate rate and + TRATE < ARR_P*((1/P)^{NWC+2}-1)/((1/P)^{NWC+1}-1) and TRATE < + SR_P, the receiver MUST not join. + + o If SSR_P is finite and the sender is not sending at constant + aggregate rate or SSR_P is finite and the sender is sending at + constant aggregate rate and TRATE < SR_P then the receiver MAY + apply one additional OPTIONAL check before deciding to join. + + It is RECOMMENDED that the receiver not join if the value of RR_P + is not sufficiently lower than the maximum value of RR_P observed + since the last join. It is RECOMMENDED that RR_P is sufficiently + low to allow a join if RR_P <= max{RRmax-2/EL,P*RRmax}, where + RRmax is the maximum measured RR_P since the last join. + + If the receiver does not join because RR_P is not sufficiently + small then a value of LOSSP is calculated so as to make the value + of the REQN equation given in Section 3.2.2.3 evaluate to + ARR_P*((1/P)^(NWC+2)-1)/((1/P)^(NWC+1)-1) with respect to the + current value of ARR_P. Then, the variables associated with LOSSP + are reset based on this calculated value of LOSSP as described at + the end of Section 3.2.2.1. + + o Otherwise, the receiver MAY join the next higher layer. + + + + +Luby & Goyal Experimental [Page 22] + +RFC 3738 WEBRC Building Block April 2004 + + + Suppose the receiver has decided to join and CTSI = i. The receiver + joins the next higher wave channel, i.e., the wave channel with CN = + i+NWC modulo T, increments NWC by 1, and then updates ARR_P to + ARR_P*((1/P)^{NWC+1}-1)/((1/P)^NWC-1) as described in Section + 3.2.2.5. The time of the join is recorded for use in updating ARTT + as described in Section 3.2.2.2. + +3.2.3.7. Join timeout + + When no packet arrives in response to the join of channel for a long + period of time, the join times out. The receiver sets JOINING to + false, updates ARR_P to ARR_P*((1/P)^NWC-1)/((1/P)^{NWC+1}-1), and + then decrements NWC by 1. + + The RECOMMENDED threshold for a join timeout is max{2*V/ARTT,10*ARTT} + seconds. + +3.2.3.8. Exceptional timeouts + + These are timeouts when the packet reception behavior is far from + what it should be and these MUST trigger the receiver to leave the + session. Exceptional timeouts include + + o No packets are received for a long period. A RECOMMENDED + threshold is max{10,TSD} seconds. + + o There is no change in time slot index for a long period. A + RECOMMENDED threshold is max{20,2*TSD} seconds. + +4. Applicability Statement + + WEBRC is intended to be a congestion control scheme that can be used + in a complete protocol instantiation that delivers objects and + streams (both reliable content delivery and streaming of multimedia + information). WEBRC is most applicable for delivery of objects or + streams of substantial length, i.e., objects or streams that range in + length from hundreds of kilobytes to many gigabytes, and whose + transfer time is on the order of tens of seconds or more. + +4.1. Environmental Requirements and Considerations + + WEBRC can be used with both multicast and unicast networks. However, + the scope of this document is limited to multicast. WEBRC requires + connectivity between a sender and receivers, but does not require + connectivity from receivers to the sender. + + WEBRC inherently works with all types of networks, including LANs, + WANs, Intranets, the Internet, asymmetric networks, wireless + + + +Luby & Goyal Experimental [Page 23] + +RFC 3738 WEBRC Building Block April 2004 + + + networks, and satellite networks. Thus, the inherent raw scalability + of WEBRC is unlimited. However, in some network environments varying + reception rates to receivers may not be advantageous. For example, + the network may have dedicated a fixed amount of bandwidth to the + session or there may be no effective way for receivers to dynamically + vary the set of channels they are joined to, as in a satellite + network. + + Receivers join and leave channels using the appropriate multicast + join and leave messages. For IPv4 multicast, IGMP messages are used + by receivers to join and leave channels. For IPv6, MLDv2 messages + are used by receivers to join and leave channels. This is the only + dependency of WEBRC on the IP version. + + WEBRC requires receivers to be able to uniquely identify and + demultiplex packets associated with a session in order to effectively + perform congestion control over all packets associated with the + session. How receivers achieve this is outside the scope of this + document. + + WEBRC is presumed to be used with an underlying network or transport + service that is a "best effort" service that does not guarantee + packet reception, packet reception order, and which does not have any + support for flow or congestion control. For example, the Any-Source + Multicast (ASM) model of IP multicast as defined in RFC 1112 [7] is + such a best effort network service. While the basic service provided + by RFC 1112 is largely scalable, providing congestion control or + reliability should be done carefully to avoid severe scalability + limitations, especially in the presence of heterogeneous sets of + receivers. + + There are currently two models of multicast delivery, the Any-Source + Multicast (ASM) model as defined in RFC 1112 [7] and the Source- + Specific Multicast (SSM) model as defined in [10]. WEBRC works with + both multicast models, but in a slightly different way with somewhat + different environmental concerns. When using ASM, a sender S sends + packets to a multicast group G, and the WEBRC channel address + consists of the pair (S,G), where S is the IP address of the sender + and G is a multicast group address. When using SSM, a sender S sends + packets to an SSM channel (S,G), and the WEBRC channel address + coincides with the SSM channel address. + + A sender can locally allocate unique SSM channel addresses, and this + makes allocation of channel addresses easy with SSM. To allocate + channel addresses using ASM, the sender must uniquely chose the ASM + multicast group address across the scope of the group, and this makes + allocation of WEBRC channel addresses more difficult with ASM. This + is an issue for WEBRC because several channels are used per session. + + + +Luby & Goyal Experimental [Page 24] + +RFC 3738 WEBRC Building Block April 2004 + + + WEBRC channels and SSM channels coincide, and thus the receiver will + only receive packets sent to the requested WEBRC channel. With ASM, + the receiver joins a channel by joining a multicast group G, and all + packets sent to G, regardless of the sender, may be received by the + receiver. Thus, SSM has compelling security advantages over ASM for + prevention of denial of service attacks. In either case, receivers + SHOULD use mechanisms to filter out packets from unwanted sources. + + WEBRC assumes that the packet route between the sender and a + particular receiver is the same for all channels associated with a + session. For SSM this assumption is true because the multicast tree + is a shortest path tree from each receiver to the sender and + generally this path changes infrequently. For ASM there are some + issues that if not properly considered may invalidate this + assumption. With ASM, the packet route between the sender and + receivers may initially be through the Rendezvous Point (RP) and then + switch over to the shortest path to the sender as packets start + flowing in a channel. The first issue is that the RP may not be the + same for all channels associated with a session, and thus the first + packets sent to the channels may follow a route that depends on the + RP of the channel. This depends on the RP configuration for the + sender. If the sender registers all channels associated with the + session with the same RP then the assumption is true, but if the + sender registers different channels with different RPs then the + assumption may not be true. Thus, it is RECOMMENDED that the sender + register all channels associated with a session with the same RP. + Another issue is that when the channel switches over from the RP to + the sender-based tree then the route to the receivers may vary within + a channel. Furthermore, this may cause either the receipt of + duplicate packets at receivers or loss of packets depending on the + smoothness of the switchover. Thus, it is RECOMMENDED that the RP be + placed as close as possible to the sender. The best location for the + RP is that it be the first-hop router closest to the sender, in which + case the path to the sender and the path to the RP is the same for + each receiver and the problems mentioned above are eliminated. The + consequences of this assumption not being true are that the receiver + reaction to congestion may not be appropriate. Generally, the WEBRC + receiver will act conservatively and reduce its reception rate too + much if this assumption is not true, but there can be cases where the + receivers will act inappropriately. + +5. Packet Header Fields + + Packets sent to a session using WEBRC MUST include Congestion Control + Information fields as specified in this section. This document + specifies short and long formats for the Congestion Control + Information, and it is RECOMMENDED that protocol instantiations use + one of these two formats. Other formats for the Congestion Control + + + +Luby & Goyal Experimental [Page 25] + +RFC 3738 WEBRC Building Block April 2004 + + + Information fields MAY be used by protocol instantiations, but all + protocol instantiations are REQUIRED to use these fields in a format + that is compatible with the interpretations of these fields. Thus, + if a protocol does use a different format for the fields in the + Congestion Control Information then it MUST specify the lengths and + positions of these fields within the packet header. + + All integer fields are carried in "big-endian" or "network order" + format, that is, most significant byte (octet) first. All constants, + unless otherwise specified, are expressed in base ten. + +5.1. Short Format Congestion Control Information + + The short format for the Congestion Control Information is shown in + Fig. 1. The total length of the short format is 32-bits. + + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | CTSI | Channel Number| Packet Sequence Number | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Fig. 1 - Short format for Congestion Control Information + + The function of each field in the Congestion Control Information is + the following. + + Current Time Slot Index (CTSI): 8 bits + + CTSI indicates the index of the current time slot. This must + be sent in each packet within the session. The Current Time + Slot Index increases by one modulo T each TSD seconds at the + sender, where T is the number of time slots associated with the + session and TSD is the time slot duration. Note that T is also + the number of wave channels associated with the session, and + thus T MUST be at most 255. + + Channel Number (CN): 8 bits + + CN is the channel number that this packet belongs to. CN for + the base channel is T, and the CNs for the wave channels are 0 + through T-1. Thus, T+1 channels in total are used, and thus T + MUST be at most 255. + + Packet Sequence Number (PSN): 16 bits + + The PSN of each packet is scoped by its CN value. The sequence + numbers of consecutive packets sent to the base channel are + + + +Luby & Goyal Experimental [Page 26] + +RFC 3738 WEBRC Building Block April 2004 + + + numbered consecutively modulo 2^16. The same sequence of PSNs + are used for each wave channel in each cycle. The sequence + numbers of consecutive packets sent to a wave channel are + numbered consecutively modulo 2^16 within each cycle, ending + with the last packet sent to the channel before the channel + goes quiescent with PSN = 2^16-1. + +5.2. Long Format Congestion Control Information + + The long format for the Congestion Control Information is shown in + Fig. 2. The total length of the long format is 64-bits. + + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | CTSI | Channel Number | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Packet Sequence Number | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Fig. 2 - Long format for Congestion Control Information + + The meaning of each field for the long format is the same as for the + short format, the only difference is that each field is twice as + long. + + Current Time Slot Index (CTSI): 16 bits + + CTSI indicates the index of the current time slot. This must + be sent in each packet within the session. The Current Time + Slot Index increases by one modulo T each TSD seconds at the + sender, where T is the number of time slots associated with the + session and TSD is the time slot duration. Note that T is also + the number of wave channels associated with the session, and + thus T MUST be at most 65,535. + + Channel Number (CN): 16 bits + + CN is the channel number that this packet belongs to. CN for + the base channel is T, and the CNs for the wave channels are 0 + through T-1. Thus, T+1 channels in total are used, and thus T + MUST be at most 65,535. + + Packet Sequence Number (PSN): 32 bits + + The PSN of each packet is scoped by its CN value. The sequence + numbers of consecutive packets sent to the base channel are + numbered consecutively modulo 2^32. The same sequence of PSNs + + + +Luby & Goyal Experimental [Page 27] + +RFC 3738 WEBRC Building Block April 2004 + + + are used for each wave channel in each cycle. The sequence + numbers of consecutive packets sent to a wave channel are + numbered consecutively modulo 2^32 within each cycle, ending + with the last packet sent to the channel before the channel + goes quiescent with PSN = 2^32-1. + +6. Requirements From Other Building Blocks + + As described in RFC 3048 [4], WEBRC is a building block that is + intended to be used, in conjunction with other building blocks, to + help specify a protocol instantiation. + + WEBRC does not provide higher level session support, e.g., how + receivers obtain the necessary session description and how the + receivers demultiplex received packets based on their session. There + is support provided by other building blocks that can be used in + conjunction with WEBRC to provide some of this support. For example, + LCT [12] can provide some of the higher level in-band session support + that may be needed by receivers, and the WEBRC Congestion Control + Information (CCI) required in each packet can be carried in the CCI + field of the LCT header [12]. + + WEBRC does not provide any type of reliability, and in particular + does not provide support for retransmission of loss packets. + Reliability can be added by independent means, such as by the use of + FEC codes as described in [13] and specified in the FEC building + block [14]. + +7. Security Considerations + + WEBRC can be subject to denial-of-service attacks by attackers that + try to confuse the congestion control mechanism for receivers by + injecting forged packets into the multicast stream. This attack most + adversely affects network elements and receivers downstream of the + attack, and much less significantly the rest of the network and other + receivers. Because of this and because of the potential attacks due + to the use of FEC described above, it is RECOMMENDED that Reverse + Path Forwarding checks be enabled in all network routers and switches + along the path from the sender to receivers to limit the possibility + of a bad agent injecting forged packets into the multicast tree data + path. + + It is also RECOMMENDED that packet authentication be used to + authenticate each packet immediately upon receipt before the receiver + performs any WEBRC actions based upon its receipt. Unfortunately, + there are currently no practical multicast packet authentication + schemes that offer instant packet authentication upon receipt. + However, TESLA [17] can be used to authenticate each packet a few + + + +Luby & Goyal Experimental [Page 28] + +RFC 3738 WEBRC Building Block April 2004 + + + seconds after receipt. Thus, TESLA could be used in conjunction with + WEBRC to authenticate packets and for example terminate the session + upon detection of a forged packet. However, it is RECOMMENDED that + the normal WEBRC receiver responses to received packets occur + immediately -- not delayed by the TESLA authentication process. This + is because the overall WEBRC performance would be greatly degraded if + the receiver delayed its WEBRC response to packet receipt for several + seconds. + + A receiver with an incorrect or corrupted implementation of WEBRC may + affect health of the network in the path between the sender and the + receiver, and may also affect the reception rates of other receivers + joined to the session. It is therefore RECOMMENDED that receivers be + required to identify themselves as legitimate before they receive the + session description needed to join the session. + + Another vulnerability of WEBRC is the potential of receivers + obtaining an incorrect session description for the session. The + consequences of this could be that legitimate receivers with the + wrong session description are unable to correctly receive the session + content, or that receivers inadvertently try to receive at a much + higher rate than they are capable of, thereby disrupting traffic in + portions of the network. To avoid these problems, it is RECOMMENDED + that measures be taken to prevent receivers from accepting incorrect + session descriptions, e.g., by using source authentication to ensure + that receivers only accept legitimate session descriptions from + authorized senders. + +8. References + +8.1. Normative References + + [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement + Levels", BCP 14, RFC 2119, March 1997. + + [2] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable + Multicast Transport (RMT) Building Blocks and Protocol + Instantiation documents", RFC 3269, April 2002. + + [3] Mankin, A., Romanow, A., Bradner, S. and V. Paxson, "IETF + Criteria for Evaluating Reliable Multicast Transport and + Application Protocols", RFC 2357, June 1998. + + [4] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S. + and M. Luby, "Reliable Multicast Transport Building Blocks for + One-to-Many Bulk-Data Transfer", RFC 3048, January 2001. + + + + + +Luby & Goyal Experimental [Page 29] + +RFC 3738 WEBRC Building Block April 2004 + + +8.2. Informative References + + [5] Byers, J., Horn, G., Luby, M., Mitzenmacher, M. and W. Shaver. + "FLID-DL: Congestion control for layered multicast," IEEE J. on + Selected Areas in Communications, Special Issue on Network + Support for Multicast Communication, Vol. 20, No. 8, October + 2002, pp. 1558-1570. + + [6] Dagum, P., Karp, R., Luby, M. and S. Ross, "An optimal algorithm + for Monte Carlo estimation," SIAM J. Comput., 29(5):1484-1496, + April 2000. + + [7] Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC + 1112, August 1989. + + [8] Goyal, V., "On WEBRC Wave Design and Server Implementation", + Digital Fountain Technical Report no. DF2002-09-001, September + 2002, available at http://www.digitalfountain.com/technology/. + + [9] Handley, M., Floyd, S., Padhye, J. and J. Widmer, "TCP Friendly + Rate Control (TFRC): Protocol Specification", RFC 3448, January + 2003. + + [10] Holbrook, H., "A Channel Model for Multicast", Ph.D. + Dissertation, Stanford University, Department of Computer + Science, Stanford, California, August 2001. + + [11] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L. and J. Crowcroft, + "Asynchronous Layered Coding (ALC) Protocol Instantiation", RFC + 3450, December 2002. + + [12] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L., Handley, M. and + J. Crowcroft, "Layered Coding Transport (LCT) Building Block", + RFC 3451, December 2002. + + [13] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and + J. Crowcroft, "The Use of Forward Error Correction (FEC) in + Reliable Multicast", RFC 3453, December 2002. + + [14] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and + J. Crowcroft, "Forward Error Correction (FEC) Building Block", + RFC 3452, December 2002. + + [15] Luby, M. and V. Goyal, "Wave and Equation Based Rate Control + Using Multicast Round Trip Time: Extended Report", Digital + Fountain Technical Report no. DF2002-07-001, September 2002, + available at http://www.digitalfountain.com/technology/. + + + + +Luby & Goyal Experimental [Page 30] + +RFC 3738 WEBRC Building Block April 2004 + + + [16] Luby, M., Goyal, V., Skaria, S. and G. Horn, "Wave and Equation + Based Rate Control Using Multicast Round Trip Time", Proc. ACM + SIGCOMM 2002, Pittsburgh, PA, August 2002, pp. 191-214. + + [17] Perrig, A., Canetti, R., Song, D. and J. Tygar, "Efficient and + Secure Source Authentication for Multicast", Network and + Distributed System Security Symposium, NDSS 2001, pp. 35-46, + February 2001. + + [18] Vicisano, L., Rizzo, L. and J. Crowcroft, "TCP-like Congestion + Control for Layered Multicast Data Transfer", Proc. IEEE Infocom + '98, San Francisco, CA, March-April 1998, pp. 996-1003. + +9. Authors' Addresses + + Michael Luby + Digital Fountain + 39141 Civic Center Drive, Suite 300 + Fremont, CA, USA, 94538 + + EMail: luby@digitalfountain.com + + + Vivek K Goyal + Massachusetts Institute of Technology + Room 36-690 + 77 Massachusetts Avenue + Cambridge, MA, USA, 02139 + + EMail: v.goyal@ieee.org + + + + + + + + + + + + + + + + + + + + + +Luby & Goyal Experimental [Page 31] + +RFC 3738 WEBRC Building Block April 2004 + + +10. Full Copyright Statement + + Copyright (C) The Internet Society (2004). This document is subject + to the rights, licenses and restrictions contained in BCP 78 and + except as set forth therein, the authors retain all their rights. + + This document and the information contained herein are provided on an + "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS + OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET + ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, + INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE + INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED + WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Intellectual Property + + The IETF takes no position regarding the validity or scope of any + Intellectual Property Rights or other rights that might be claimed to + pertain to the implementation or use of the technology described in + this document or the extent to which any license under such rights + might or might not be available; nor does it represent that it has + made any independent effort to identify any such rights. Information + on the procedures with respect to rights in RFC documents can be + found in BCP 78 and BCP 79. + + Copies of IPR disclosures made to the IETF Secretariat and any + assurances of licenses to be made available, or the result of an + attempt made to obtain a general license or permission for the use of + such proprietary rights by implementers or users of this + specification can be obtained from the IETF on-line IPR repository at + http://www.ietf.org/ipr. + + The IETF invites any interested party to bring to its attention any + copyrights, patents or patent applications, or other proprietary + rights that may cover technology that may be required to implement + this standard. Please address the information to the IETF at ietf- + ipr@ietf.org. + +Acknowledgement + + Funding for the RFC Editor function is currently provided by the + Internet Society. + + + + + + + + + +Luby & Goyal Experimental [Page 32] + -- cgit v1.2.3