path: root/3rdparty/openpgm-svn-r1085/doc/draft-ietf-rmt-bb-pgmcc-03.txt

Internet Engineering Task Force 				  RMT WG
INTERNET-DRAFT					     Luigi Rizzo/U. Pisa
draft-ietf-rmt-bb-pgmcc-03.txt		       Gianluca Iannaccone/Intel
						  Lorenzo Vicisano/Cisco
							Mark Handley/UCL
							    12 July 2004
						   Expires: January 2005


	    PGMCC single rate multicast congestion control:
			 Protocol Specification



Status of this Document

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 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 a "work in progress".

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt

To view the list Internet-Draft Shadow Directories, see
http://www.ietf.org/shadow.html.

This document is a product of the IETF RMT WG.	Comments should be
addressed to the authors, or the WG's mailing list at rmt@lbl.gov.


				Abstract


     This document describes PGMCC, a single rate multicast
     congestion control scheme which is TCP-friendly and achieves
     scalability, stability and fast response to variations in
     network conditions.  PGMCC is suitable for both non-reliable



Rizzo/Iannaccone/Vicisano/Handley				[Page 1]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


     and reliable data transfers.  It is mainly designed for NAK-
     based multicast protocols, and uses a window-based, TCP-like
     control loop using positive ACKs between one representative of
     the receiver group (the ACKER) and the sender.  The ACKER is
     selected dynamically and may change over time.

     PGMCC is made of two components: a window-based control loop,
     which closely mimics TCP behavior, and a fast and low-overhead
     procedure to select (and track changes of) the ACKER.  The
     scheme is robust to measurement errors, and supports fast
     response to changes in the receiver set and/or network
     conditions.







































Rizzo/Iannaccone/Vicisano/Handley				[Page 2]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


			   Table of Contents


     1. Introduction. . . . . . . . . . . . . . . . . . . . . .   4
      1.1. Terminology. . . . . . . . . . . . . . . . . . . . .   4
     2. Protocol Overview . . . . . . . . . . . . . . . . . . .   4
      2.1. Packet Contents. . . . . . . . . . . . . . . . . . .   6
       2.1.1. Data Packets. . . . . . . . . . . . . . . . . . .   6
       2.1.2. Feedback Packets. . . . . . . . . . . . . . . . .   7
       2.1.3. Field sizes and formats . . . . . . . . . . . . .   8
      2.2. Window-based controller. . . . . . . . . . . . . . .   9
      2.3. Acker Selection. . . . . . . . . . . . . . . . . . .  11
       2.3.1. Initial Acker election. . . . . . . . . . . . . .  11
       2.3.2. Acker dropouts. . . . . . . . . . . . . . . . . .  12
      2.4. TCP Throughput Equation. . . . . . . . . . . . . . .  12
      2.5. RTT measurement. . . . . . . . . . . . . . . . . . .  13
       2.5.1. Explicit Timestamp. . . . . . . . . . . . . . . .  13
       2.5.2. Implicit timestamp. . . . . . . . . . . . . . . .  13
       2.5.3. Sequence numbers. . . . . . . . . . . . . . . . .  14
       2.5.4. Recommendations . . . . . . . . . . . . . . . . .  15
      2.6. Loss rate measurement. . . . . . . . . . . . . . . .  15
      2.7. Timeouts . . . . . . . . . . . . . . . . . . . . . .  16
      2.8. Interaction with feedback suppression
      schemes . . . . . . . . . . . . . . . . . . . . . . . . .  16
      2.9. Interaction with ECN . . . . . . . . . . . . . . . .  17
     3. Procedures - Sender . . . . . . . . . . . . . . . . . .  17
     4. Procedures -- Receiver. . . . . . . . . . . . . . . . .  18
     5. Security Considerations . . . . . . . . . . . . . . . .  19
     6. Authors' Addresses. . . . . . . . . . . . . . . . . . .  20
     7. Acknowledgments . . . . . . . . . . . . . . . . . . . .  20
     8. Full Copyright Statement. . . . . . . . . . . . . . . .  21




















Rizzo/Iannaccone/Vicisano/Handley				[Page 3]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


1.  Introduction

This document describes PGMCC, a single rate multicast congestion
control scheme which is TCP-friendly and achieves scalability, stability
and fast response to variations in network conditions.

PGMCC is designed for multicast sessions with one sender and one or more
receivers, and is a good match for transport protocols using negative
acknowledgements (NAKs) to collect feedback from the receivers.  The
congestion control scheme implemented by PGMCC closely mimics the
congestion-control behavior of TCP, as it uses a window-based control
loop which is run between the sender and a selected receiver called the
ACKER. The role of the ACKER is to provide timely feedback in the same
way as a TCP receiver; additionally, the ACKER is selected dynamically
among the receivers as the one which would experience the lowest
throughput if separate TCP sessions were run between the sender and each
of the receivers.

Scalability in PGMCC comes from the use of negative acknowledgements
(NAKs) for collecting feedback from receivers other than the ACKER.  As
a consequence, the usual techniques for NAK suppression and aggregation
can be used to reduce the amount of feedback to the source and improve
the scalability of the scheme.

PGMCC is designed to completely decouple congestion control from data
integrity. As a consequence, the scheme can work with both reliable data
transfer and unreliable communication protocols such as those used for
video or audio streaming.

While designed with multicast in mind, PGMCC can be equally used as a
replacement for TCP for unicast sessions which require a lower degree of
reliability than what TCP offers.


1.1.  Terminology

In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL",
"SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
"OPTIONAL" are to be interpreted as described in RFC 2119 and indicate
requirement levels for compliant PGMCC implementations.


2.  Protocol Overview

PGMCC is based on two separate but complementary mechanisms:

  o A window-based control loop which closely emulates TCP congestion
    control.



Rizzo/Iannaccone/Vicisano/Handley		    Section 2.	[Page 4]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


    The window-based control loop is simply an adaptation of the TCP
    congestion control scheme to transport protocols where missing
    (because of network errors or congestion) data packets are not
    necessarily retransmitted, and so the congestion control scheme
    cannot rely on cumulative acknowledgements.  In PGMCC, the
    ``congestion window'' is simulated using a token-based scheme which
    permits congestion control to be decoupled from retransmission
    state. One of the receivers in the group operates as the ACKER, i.e.
    the node in charge of sending positive acknowledgements back to the
    source and thus controlling the rate of the transfer.


  o A procedure to select the ACKER.
    The purpose of this procedure is to make sure that, in presence of
    multiple receivers, the ACKER is dynamically selected to be the
    receiver which would have the lowest throughput if separate TCP
    sessions were run between the sender and each receiver.
    For the acker selection mechanism, PGMCC uses a throughput equation
    to determine the expected throughput for a given receiver as a
    function of the loss rate and round-trip time. Unlike other schemes
    [2], the TCP throughput equation is not used to determine the actual
    sending rate, which is completely controlled by the window-based
    control loop.


In principle, PGMCC's congestion control mechanism works as follows:


  o Receivers measure the loss rate and feed this information back to
    the sender, either in ACK or NAK messages.


  o The sender also uses these feedback messages to measure the round-
    trip time (RTT) to each receiver.


  o The loss rate and RTT are then fed into PGMCC's throughput equation,
    to determine the expected throughput to that receiver.


  o The sender then selects as the acker the receiver with the lowest
    expected throughput, as computed by the equation.

The dynamics of the acker selection mechanism are sensitive to how the
measurements are performed and applied. In the rest of this document we
suggest specific mechanisms to perform and apply these measurements.
Other mechanisms are possible, but it is important to understand how the
interactions between mechanisms affect the dynamics of PGMCC.



Rizzo/Iannaccone/Vicisano/Handley		    Section 2.	[Page 5]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


2.1.  Packet Contents

Before specifying the sender and receiver functionality, we describe the
information required by PGMCC to perform its tasks. This information is
carried in the data packets sent by the sender, and in the feedback
packets sent by the receiver.  As PGMCC will be used along with some
transport protocol, the actual data and feedback packets will contain
further information for use by the protocol itself. For this reason, we
do not specify packet formats, as these depend on the details of the
transport protocol used.

Note that the requirements of the transport protocol in terms of packet
generation may differ from those of PGMCC. As an example, most NAK-based
reliable multicast protocols do not use positive acknowledgements, but
PGMCC requires ACKs for clocking out data packets; unreliable transport
protocols might have no interest in generating NAKs for data integrity
purposes, yet PGMCC depends on NAKs reaching the data sender in order to
elect the ACKER.


Implementors may decide to insert PGMCC-related information in already
existing protocol packets whenever possible, but in cases such as the
ones described in the previous paragraph, it might be necessary to
define and generate new packets exclusively for congestion control
purposes. As an example, in a prototype implementation of PGMCC on top
of the PGM protocol [7], some of the information used by PGMCC is
already present in the original protocol packets, and PGMCC-specific
information is carried as PGM options in ODATA and NAK packets. However,
a new packet type has been defined for ACKs, which are generated
according to the rules defined in this document.


2.1.1.	Data Packets

Each data packet sent by the data sender contains the following
information:


  o A SEQUENCE NUMBER. This number is incremented by one for each data
    packet transmitted.  The field must be sufficiently large that it
    does not wrap causing two different packets with the same sequence
    number to be in the receiver's recent packet history at the same
    time.


  o A TIMESTAMP (or equivalent information, see Section 2.5) indicating
    when the packet with this sequence number has been sent.  There is
    no requirement for synchronized clocks between the sender and the



Rizzo/Iannaccone/Vicisano/Handley		Section 2.1.1.	[Page 6]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


    receivers.	The timestamp is used to measure network round-trip
    times, so needs sufficient resolution for this task.  A resolution
    of 1ms would be adequate.


  o The ACKER IDENTITY, i.e. the identity of the receiver in charge of
    sending an acknowledgement for this data packet.  The ACKER is
    elected as a result of the process described in Section 2.3.
    A special value is used to indicate that no ACKER is designated for
    this packet -- this can happen at the beginning of a session or when
    the current ACKER leaves the group.  Receivers interpret this value
    as a request to elect a new acker.


2.1.2.	Feedback Packets

There are two types of feedback packets used by PGMCC: ACK packets and
NAK packets.
ACK packets are generated by the current ACKER, and are used to detect
loss or successful delivery of packets, and to regulate the throughput
accordingly. ACK packets also contain information used to determine the
TCP-equivalent throughput for the ACKER.
NAK packets are sent by any receiver who experiences loss.  They contain
information used to determine the TCP-equivalent throughput for that
receiver. In an actual protocol instantiation (such as PGM [7]), NAK
packets might also be used by the protocol to request the retransmission
of specific packets, and indicate the identity of the packet being
requested.

Both ACK and NAK packets are sent by data receivers, and contain the
following information:


  o The TIMESTAMP (or equivalent information) derived from the most
    recently received data packet according to one of the techniques
    described in Section 2.5.
    This value is used by the sender to measure the RTT to the receiver
    who generated this feedback packet.


  o ``p'', the receiver's current estimate of the LOSS RATE.  The loss
    rate is measured by receivers as described in Section 2.6

In addition to the above, ACK packets (sent by the acker designated in
the corresponding data packets) must also contain the following
information:





Rizzo/Iannaccone/Vicisano/Handley		Section 2.1.2.	[Page 7]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


  o RX_MAX, the highest sequence number among received data packets
    (taking care to deal with sequence number wrapping correctly).

  o ACK_BITMAP, a bitmap indicating the receive status of the latest N
    (typically N=32) data packets with sequence numbers RX_MAX-(N-1) to
    RX_MAX.


This information is used by the sender to record which packets have been
received or lost, and manipulate the transmit window accordingly.  Note
that each ACK packet contains information about multiple packets, and
this increases the robustness of the scheme to loss of ACK packets.
This is necessary because ACKs are not sent reliably (unlike TCP's ACKs,
which are cumulative).


2.1.3.	Field sizes and formats

The following sizes and formats are suggested for the various fields
used by PGMCC and transmitted over the network:


  o SEQUENCE NUMBERS
    32 bit, unsigned, network order.


  o TIMESTAMPS
    32 bit, unsigned, network order.  A resolution of 1ms or better is
    desirable.


  o ACKER IDENTITY
    Same size and format of a network layer address (e.g. 32 bit for
    IPv4).  Note though that using an IP address for the Acker Identify
    will cause problems with NAT traversal.  Transport protocol
    designers might examine the SSRC mechanism used by RTP [6] as an
    alternative form of node identifier that could be used as Acker
    Identity.


  o LOSS RATE (``p'')
    16-bit unsigned integer, in network format, with 0 indicating no
    loss and 2^16-1 indicating 100% loss.


  o ACK BITMAP
    32-bit, in network format, with least significant bit indicating
    receive status of packet RX_MAX.



Rizzo/Iannaccone/Vicisano/Handley		Section 2.1.3.	[Page 8]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


2.2.  Window-based controller

In a window-based congestion control scheme such as TCP, the
``congestion window'' represents, among other things, the maximum amount
of packets in flight at any time, which in turn controls the throughput
of the session. The sender keeps track of the actual number of packets
in flight, basing on its transmissions and the reception of
acknowledgements.

The sender may dynamically change the size of the window, according to
the congestion control scheme being used. In TCP, and PGMCC, an
``Additive Increase Multiplicative Decrease'' (AIMD) scheme is used: in
absence of loss, the window is increased by some fixed amount (typically
one packet) per round trip time (RTT), whereas upon loss the window is
reduced to a fraction of its original value (typically halved) in each
RTT in which a loss event is experienced.

In PGMCC the window is managed using a token-based mechanism, controlled
by two variables:

  o A ``Window Size'', W, which describes the current window size in
    packets.

  o A ``Token Count'', T, which indicates the number of packets that can
    be transmitted.  T is bounded above by W.  It is decremented every
    time a packet is transmitted, and incremented every time an ACK is
    received, according to the rules below.

Note that these two variables need to hold non-integer data.  Typically
a fixed point representation with at least 16 bits for both integer and
fractional parts would be acceptable for implementation purposes.

The information contained in each ACK is used to determine how many new
packets are acknowledged by that ACK, and whether there are
unacknowledged packets which were not reported in previous ACKs.  The
sender also schedules a timeout to react in case no ACKs are received.

The sender behaves as follows:


  o INITIALIZATION
    At startup, or after a timeout, both W and T are set to 1.


  o ACK RECEPTION, NO LOSS DETECTED
    If the incoming ACK reports new acknowledged packets, and no loss
    (as defined in the next paragraph) is detected, then the window is
    inflated by one packet per RTT.



Rizzo/Iannaccone/Vicisano/Handley		  Section 2.2.	[Page 9]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


    NOTE: during the slow-start phase, TCP opens the window
    exponentially up to the SSTHRESH value, which is computed by TCP
    according to the dynamics of the session and updated upon losses.

    We do recommend that PGMCC uses a similar strategy, but using a
    fixed, small value for SSTHRESH (e.g. 4 packets).  In fact, due to
    the dynamicity of the ACKER, which might change on every single
    packet, it is hard to compute a reliable estimate of the SSTHRESH
    without keeping state for multiple receivers, and the benefits are
    small in any event.

    In summary, the reaction to ACK reception on no loss modifies T and
    W as follows (here, N is the number of new packets acknowledged by
    the incoming ACK):

      if (W < SSTHRESH) then
	  D = min(N, SSTHRESH - W) // use the first D acks for
    exp.opening
	  N = N - D		       // and the remaining ones for
    linear opening
	  T = T + 2*D
	  W = W + D
      endif
      // do linear window opening with the remaining acks
      T = T + N * ( 1 + 1/W )
      W = W + N/W


  o PACKET TRANSMISSION
    One token is consumed for each packet transmitted:

				 T = T - 1


  o ACK RECEPTION, LOSS DETECTED
    If the incoming ACK reports an unacknowledged data packet which is
    followed by at least 3 acknowledged data packets, then the packet is
    assumed to be lost and PGMCC reacts by halving the window, in the
    same way as TCP after 3 duplicate acknowledgements.  This is
    achieved by modifying T and W as follows:

			   T = T - W/2 , W = W/2

    to simulate the multiplicative decrease.
    Additionally, all window manipulation is suspended for the
    subsequent RTT.  This is achieved by recording the current transmit
    sequence number, and canceling any further manipulation of the
    window until feedback is received for the next transmitted packet,



Rizzo/Iannaccone/Vicisano/Handley		 Section 2.2.  [Page 10]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


    or until a timeout occurs.




2.3.  Acker Selection

The ACKER selection process in PGMCC aims at locating the receiver which
would have the lowest throughput if each receiver were using a separate
TCP connection to transfer data.

Because the steady-state throughput of a TCP connection can be
characterized in a reasonably accurate way in terms of its loss rate and
round trip time [3], the throughput for each receiver can be estimated
by using these two parameters.

Whenever an ACK or NAK packet from any of the receivers reaches it, the
sender is able to compute the expected throughput T_i for that receiver
by using the equation shown in Section 2.4, with the round trip time RTT
and loss rate p and measured as described in Sections 2.5 and 2.6,
respectively.  At any given time, the sender stores the expected
throughput for the current ACKER, T_acker. This value is updated every
time an ACK or NAK from the current ACKER is received (note that, after
a new ACKER is selected, the sender will typically receive ACKs from the
old ACKER for one RTT, and the feedback from different ACKERs might be
interleaved if the paths leading to them have different round trip
times).

Whenever an ACK or NAK is received from another node i (a previous ACKER
or some other receiver), the expected throughput T_i for that node is
computed, and compared with T_acker.  Node i is selected as the new
acker if

			   T_i < C * T_acker

where the constant C between 0 and 1 provides some hysteresis and avoids
too frequent oscillations in the choice of the ACKER.  A suggested value
for C is 0.75.

Note that, from an implementation point of view (see Section 2.4), it is
more convenient to compute T_i ^(-2), so the above equation must be
modified accordingly.


2.3.1.	Initial Acker election

Upon reception of a data packet reporting that no acker is currently
selected, receivers generate a dummy NAK report which is used to elect



Rizzo/Iannaccone/Vicisano/Handley	       Section 2.3.1.  [Page 11]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


the initial acker. The NAK is sent with the usual feedback suppression
mechanism dictated by the transport protocol (possibly with shorter time
constants) to avoid feedback implosion, and the sender will select the
source of the first incoming NAK as the new ACKER.


2.3.2.	Acker dropouts


If the ACKER decides to disconnect from the session, it can cause the
session to stop. To avoid this, it is recommended that an ACKER deciding
to leave the session informs the sender by sending an ACK packet (or a
duplicate) carrying an "ACKER_LEAVING" option.	The reception of this
packet by the sender will in turn trigger an initial acker election
phase.



2.4.  TCP Throughput Equation

Any realistic equation of TCP throughput as a function of loss event
rate and RTT should be suitable for use in PGMCC.  Unlike other schemes
[2] where the throughput equation directly controls the transmit rate,
in PGMCC the equation is used only for acker selection purposes, and the
throughput values are only compared among themselves.  As a consequence,
we can use the following equation, derived from the one presented in [3]
by setting RTO = 4 * RTT (as it is common practice):

	 M = 1/T = RTT_i * sqrt(p) * (1 + 9*p * (1 + 32*(p)^2))


where

    M = 1/T is proportional to the inverse of the throughput for the
    receiver under consideration;

    RTT is the round trip time for the receiver under consideration;

    p is the loss rate for the receiver under consideration, between 0
    and 1.0;

and multiplying constants are omitted.

The above equation is accurate on a wide range of loss rates, and also
covers situations where retransmission timeouts have a significant
impact on the throughput of the protocol.

Note that when p=0, the equation yields 1/T = M = 0. This does not



Rizzo/Iannaccone/Vicisano/Handley		 Section 2.4.  [Page 12]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


constitute a problem as we can still compare the M values computed for
different receivers to determine the acker.  Also note that it is easier
to compute M^2 instead of M, because the former does not require the use
of sqrt().

In future, different throughput equations may be substituted for this
equation.  The requirement is that the throughput equation be a
reasonable approximation of the sending rate of TCP for conformant TCP
congestion control.

The parameters p and RTT need to be measured or calculated by a PGMCC
implementation.  The measurement of RTT is specified in Section 2.5; the
measurement of p is specified in Section 2.6.

2.5.  RTT measurement

In PGMCC, the RTT is measured by the sender making use of the timestamp
(or equivalent information) echoed back by each receiver in feedback
messages. Three procedures are possible to measure the RTT, as follows.
In no case is it required to have clock synchronization between sender
and receivers.


2.5.1.	Explicit Timestamp

This first technique relies on the transmission of a timestamp TS_j with
each data packet j.
The receiver will record the most recently received timestamp, and will
echo it back to the source when generating an ACK or a NAK. If the
feedback is delayed, the time elapsed between the reception of the
timestamp and the generation of the feedback should be added to the
echoed timestamp.
The sender computes the RTT by subtracting the received timestamp from
the current value of the clock.

The resolution of the timestamp value should be good enough for
reasonable precision measurement of typical network round trip times. If
receivers need to apply correction for delayed feedback, it is necessary
that receivers know the resolution of the timestamp clock. A suggested
value is 1ms.


2.5.2.	Implicit timestamp

With this technique, the sender will record a timestamp TS_j for each
transmitted data packet j, but the timestamp will not be transmitted
with the packet itself.
The receiver will record the most recently received sequence number, and



Rizzo/Iannaccone/Vicisano/Handley	       Section 2.5.2.  [Page 13]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


will echo it back to the source when generating an ACK or a NAK.
The sender computes the RTT by looking up the timestamp associated with
the sequence number received in the feedback packet, and subtracting it
from the current clock value.

If the feedback from the receiver is delayed, as it is commonly the case
for NAKs, the receiver can compute, and send back to the source, a
correction term corresponding to the time elapsed between the reception
of the timestamp and the generation of the feedback. The correction term
will then be subtracted by the sender in order to obtain the correct
estimate of the RTT.

This RTT measurement technique is equivalent to the previous one, but it
saves some space in data packets as the timestamp does not need to be
sent explicitly. Feedback packets might become larger if the correction
value is transmitted explicitly; but in many cases, the sequence number
will already be present for other reasons (e.g. ACK packets), and
wherever space is a concern the sequence number and the correction term
can be packed in a single 32-bit word without loss of precision.


2.5.3.	Sequence numbers

This technique is the least precise, but it does not rely on the
presence of a high resolution clock on the nodes.
The sender will not compute any timestamp, and just send data packets
with their sequence number j.
The receiver will record the most recently received sequence number, and
will echo it back to the source when generating an ACK or a NAK.
The sender computes the RTT as the difference between the most recently
sent sequence number and the sequence number received from the ACK or
NAK packet.

Note that in this case the RTT is not measured in seconds, but in
"sequence numbers", which are monotonically, but not uniformly,
increasing with time. The two measurements are equivalent if the sender
transmits at a constant rate. When the data rate changes over time (as
it is normally happens, given that PGMCC controls the actual data rate),
then the "measured" RTT values grow with the actual transmit rate. This
can influence the correctness of the results when comparing two
measurement done over different and only partially overlapping time (and
sequence number) intervals where the transmit rate incurs a significant
change.








Rizzo/Iannaccone/Vicisano/Handley	       Section 2.5.3.  [Page 14]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


2.5.4.	Recommendations

Whenever possible, the measurement of the RTT should be carried out
using either explicit or implicit timestamps, and by keeping track of
the "correction term" (the delay between data reception and feedback
generation).

If the receiver does not have a clock with a suitable resolution, the
correction term might not be present (or be inaccurate). In this case
the timestamps received by the sender on NAK packets might be in error,
in the worst case, by as much as the packet interarrival time.	This
error will normally not be present on ACK packets, which are sent
immediately.  A suitable correction should be applied by the sender in
order to avoid systematic errors.

The measurement based on sequence numbers is less accurate, but also
less sensitive to errors due to the lack of the correction term. In
fact, the measurement error induced by the lack of the correction term
can be at most one unit.  This suggests that, when the correction term
is not available, measurements based on sequence numbers should be
favoured.  Simulations have shown that the acker selection mechanism
performs moderately better when the RTT measurement is based on
timestamps, but performance is reasonably good also with measurements
based on sequence numbers.



2.6.  Loss rate measurement


The loss measurement in PGMCC is entirely performed by receivers.  The
measurement results do not directly influence the transmit rate, but are
only used for comparison purposes. As a consequence, the scheme is
reasonably robust to different measurement techniques, as long as they
are not influenced too strongly by single loss events.

The main method suggested for loss measurement is Exponentially Weighted
Moving Average (EWMA), which is formally equivalent to a single-pole
digital low pass filter applied to a binary signal x_i, where x_i = 1 if
packet i is lost, x_i = 0 if packet i is successfully received.

The loss rate p_i upon reception or detection of loss of packet i is
computed as


		 p_i = c_p * p_{i-1} + (1 - c_p ) * p_i
 where the constant c_p between 0 and 1 is related to the bandpass of
the filter. Experiments have shown good performance with c = 500/65536,



Rizzo/Iannaccone/Vicisano/Handley		 Section 2.6.  [Page 15]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


and computations performed with fixed point arithmetic and 16 fractional
digits.

As an alternative to EWMA, the technique used in TFRC [2] can be
adopted. Simulations have shown a moderate improvement in the acker
selection mechanism by measuring loss using the TFRC loss estimator,
which is however slightly more expensive to compute than the EWMA loss
estimator in presence of packet reordering.


2.7.  Timeouts


When a packet is transmitted, the sender schedules a timeout to prevent
stalls upon loss of ACKs or disconnection of the ACKER.  In TCP, which
has a similar problem, the timeout value is computed by accumulating
statistics (SRTT and RTTVAR) on RTT samples, starting from a default
initial value (3s) when no RTT samples are available.

PGMCC can use a similar scheme to compute the timeouts, remembering that
upon ACKER changes (which may be very frequent), the computation of SRTT
and RTTVAR must be restarted from the beginning, unless the sender
decides to keep state for at least a small number of recent ackers.

Because the ACKER can leave the group without notifying the sender,
after a number of successive timeouts the sender MUST force the election
of a new ACKER.  We recommend this new election to be performed after
two successive timeouts.


2.8.  Interaction with feedback suppression schemes


Several schemes are used by NAK-based multicast protocols to reduce the
amount of feedback directed toward the source and make the protocol
scale with large populations of receivers.  Such schemes typically rely
on randomly delaying NAK generation, and suppressing pending NAKs when
an equivalent NAK or a retransmission is heard; or, intermediate nodes
such as routers can implement some form of feedback aggregation and
filtering.

Such schemes might prevent NAKs from potential ACKER candidates from
reaching the source. This filtering might impact the speed at which
PGMCC selects the correct ACKER, though initial experience from
simulations seem to suggest that PGMCC behavior is not severely affected
by NAK suppression schemes.





Rizzo/Iannaccone/Vicisano/Handley		 Section 2.8.  [Page 16]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


2.9.  Interaction with ECN


PGMCC can use ECN notifications in much the same way as actual losses,
and use such notifications to control the throughput of the session.

At the receiver, ECN-marked data packets can be considered as lost
packets for the purpose of loss rate computation and ACK/NAK generation.
If the ACKER sends an ACK for ECN-marked packets, that ACK MUST report
that the packet being acknowledged that was ECN marked.  Similarly the
ACKER must indicate in the ACK packet's received packets bitmap that the
packet was ECN-marked, or that the packet was lost.

We note that to support use of the ECN nonce, the ACK packet's received
packets bitmap would require two bits per packet being reported.


3.  Procedures - Sender

The following pseudo-code specifies the complete behavior of the sender
in PGMCC.


initialization:
  T = 1 ; W = 1 ;   /* initialize window and number of tokens */
  RETRY = 0 ;	    /* number of consecutive timeouts so far  */
  < initialize p, RTT for acker to default values >
  ACKER = NO_ACKER; /* no acker is known		      */
  < initialize sequence numbers >
  QUEUED = 0;	    /* packets waiting to be transmitted      */

on transmission request:
  send_packet() ;

on timeout expiration :
  T = 1 ; W = 1 ;   /* initialize window and number of tokens */
  if (RETRY < RETRY_MAX)
    RETRY = RETRY + 1
  else
    ACKER = NO_ACKER ; /* old acker is not valid anymore      */
  send_packet() ;










Rizzo/Iannaccone/Vicisano/Handley		   Section 3.  [Page 17]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


on ACK/NAK reception from receiver I :
  < compute p and RTT for source of this ACK, see Sec. 2.5 and 2.6 >
  RETRY = 0 ;
  if (ACKER == NO_ACKER) { /* select current as acker is no other known */
    ACKER = I ;
    T = T + 1 ;
  }
  if (ACKER != I)
    < select acker according to Sec. 2.3 > ;
  else {
    <update acker statistics (p_ACKER, RTT_ACKER) >
    if (packet_type == ACK) {
      < update_window according to Sec.2.2 >
      send_packet ;
      if (ack_pending)
	update_timeout ;
  }
}

send_packet() {
  if (QUEUED > 0 && T >= 1) {
    < transmit one packet >
    T = T - 1 ;
    QUEUED = QUEUED - 1 ;
  }
  if ( <there are unacked packet> )
    <set a timeout, see Sec.2.7 >
}



4.  Procedures -- Receiver

The following pseudo-code specifies the complete behavior of the
receiver in PGMCC.

A receiver only transmits an ACK packet when it receives a data packet
for which the receiver is designated as the ACKER by the data packet
itself.  A receiver can transmit a NAK packet after it has detected that
a data packet is missing and a suitable delay has passed, as dictated by
the feedback suppression rules of the protocol in use.

The data packet contains acknowledgement status about the most recent 32
sequence numbers known to the receiver.







Rizzo/Iannaccone/Vicisano/Handley		   Section 4.  [Page 18]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


on initialization/session setup:
  < initialize state variables and ACK bitmap >

on DATA packet reception:
  < update p measurement according to Sec.2.6 >
  < record timestamp and packet reception time >
  if (ACKER == this_node) {
    < send an immediate ACK >
  }
  if ( <some data packet is missing and unacknowledged > )
    < schedule a timeout for NAK transmission >

on NAK reception:
  < suppress any pending NAK transmission for the sequence
    number indicated in the NAK >

on timeout:
  if ( < there are missing and unacknowledged packets > ) {
    < send a NAK for one or more of the missing packets >
    < mark such packets as acknowledged >
    if ( <some data packet is missing and unacknowledged > )
      < schedule a timeout for NAK transmission >
  }


5.  Security Considerations

PGMCC is not a transport protocol in its own right, but a congestion
control mechanism that is intended to be used in conjunction with a
transport protocol.  Therefore security primarily needs to be considered
in the context of a specific transport protocol and its authentication
mechanisms.

Congestion control mechanisms can potentially be exploited to create
denial of service.  This may occur through spoofed feedback.  Thus any
transport protocol that uses PGMCC should take care to ensure that
feedback is only accepted from the receiver of the data.  The precise
mechanism to achieve this will however depend on the transport protocol
itself.

In addition, congestion control mechanisms may potentially be
manipulated by a greedy receiver that wishes to receive more than its
fair share of network bandwidth.  A receiver might do this by first
reporting inflated loss and RTT samples, in order to get selected as the
ACKER, and then generating ACK at the desired rate (including possibly
claiming to have received packets that in fact were lost due to
congestion).  Possible defenses against such a receiver could be based
on the sender verifying the correctness of the loss and RTT samples



Rizzo/Iannaccone/Vicisano/Handley		   Section 5.  [Page 19]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


supplied by the receiver. A PGMCC sender SHOULD compare the receiver
reports on loss rate and RTT with the information derived directly from
the incoming stream of ACKs.  In case of discrepancy of the reports, a
PGMCC sender SHOULD mark the current acker as ineligible and initiate a
new acker election. The decision on how large that discrepancy should be
before initiating a new acker election is left to the implementation.

Also, the sender MAY include some form of nonce that the receiver must
feed back to the sender to prove receipt. However, the details of such a
nonce would depend on the transport protocol, and in particular on
whether the transport protocol is reliable or unreliable.


6.  Authors' Addresses

   Luigi Rizzo
   luigi@iet.unipi.it
   Dip. Ing. dell'Informazione,
   Univ. di Pisa
   via Diotisalvi 2, 56122 Pisa, Italy

   Gianluca Iannaccone
   gianluca.iannaccone@intel.com
   Intel Research
   15 JJ Thomson Avenue, Cambridge CB3 0FD, UK

   Lorenzo Vicisano
   lorenzo@cisco.com
   cisco Systems, Inc.
   170 West Tasman Dr.,
   San Jose, CA, USA, 95134

   Mark Handley
   m.handley@cs.ucl.ac.uk
   University College London,
   Gower Street, London WC1E 6BT, UK


7.  Acknowledgments

We would like to acknowledge feedback and discussions on equation-based
congestion control with a wide range of people, including members of the
Reliable Multicast Research Group, the Reliable Multicast Transport
Working Group, and the End-to-End Research Group.







Rizzo/Iannaccone/Vicisano/Handley		   Section 7.  [Page 20]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


[1] Bradner, S., Key words for use in RFCs to Indicate Requirement
Levels (IETF RFC 2119) http://www.rfc-editor.org/rfc/rfc2119.txt

[2] Floyd, S., Handley, M., Padhye, J., Widmer, J., "Equation-Based
Congestion Control for Unicast Applications", ACM SIGCOMM 2000,
Stockholm, Aug. 2000

[3] Padhye, J. and  Firoiu, V. and Towsley, D. and Kurose, J., "Modeling
TCP Throughput: A Simple Model and its Empirical Validation", Proc ACM
SIGCOMM 1998.

[4] Mankin, A., Romanow, A., Brander, S., Paxson, V., "IETF Criteria for
Evaluating Reliable Multicast Transport and Application Protocols,"
RFC2357, June 1998.

[5] Rizzo, L., "pgmcc: a TCP-friendly single-rate multicast congestion
control scheme", ACM SIGCOMM 2000, Stockholm, Aug.2000

[6] Schulzrinne, H., Casner, S., Frederick, R., Jacobson, V., "RTP: A
Transport Protocol for Real-Time Applications", RFC 1889, Jan 1996.

[7] Speakman, T., Crowcroft, J., Gemmell, J., Farinacci, D. , Lin, S.,
Leshchiner, D., Luby, M., Montgomery, T. , Rizzo, L., Tweedly, A.,
Bhaskar, N., Edmonstone, R., Sumanasekera, R., Vicisano, L., PGM
Reliable Transport Protocol Specification, RFC 3208, December 2001.
rfc3208.txt also available at ftp://ftp.rfc-editor.org/in-
notes/rfc3208.txt




8.  Full Copyright Statement

Copyright (C) The Internet Society (2000).  All Rights Reserved.

This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it or
assist in its implementation may be prepared, copied, published and
distributed, in whole or in part, without restriction of any kind,
provided that the above copyright notice and this paragraph are included
on all such copies and derivative works. However, this document itself
may not be modified in any way, such as by removing the copyright notice
or references to the Internet Society or other Internet organizations,
except as needed for the purpose of developing Internet standards in
which case the procedures for copyrights defined in the Internet
languages other than English.





Rizzo/Iannaccone/Vicisano/Handley		   Section 8.  [Page 21]

INTERNET-DRAFT		  Expires: January 2005 	       July 2004


The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS
IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK
FORCE DISCLAIMS 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."










































Rizzo/Iannaccone/Vicisano/Handley		   Section 8.  [Page 22]