Internet DRAFT - draft-zhang-barm-congestion

draft-zhang-barm-congestion



Internet Engineering Task Force                               Bing Zhang
INTERNET-DRAFT                                                Zengji Liu
draft-zhang-barm-congestion-02.txt                          Xidian Univ.
                                                        January 22, 2006
                                                  Expires: July 22, 2006


      Binomial Congestion Control At Receivers for Multicast (BARM)



Status of this Document

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

Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups.  Note that other groups
may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time.  It is inappropriate to use Internet- Drafts as reference material
or to cite them other than as "work in progress."

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

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.



                               Abstract

This document specifies Binomial congestion control At Receivers for
Multicast (BARM). BARM is a single rate multicast congestion control
protocol for streaming media applications in the best effort Internet
environment. Combining aspects of window-based and rate-based congestion
control, the protocol shifts most of the congestion control mechanisms
to multicast receivers. A congestion window is maintained and updated
by each receiver independently according to TCP-friendly binomial
algorithm, and is converted to the expected sending rate which is then
fed back to the sender if permitted. To suppress feedback implosion, a
representative receiver is selected among receivers and a distributed
suppression mechanism is used. BARM has good TCP-friendliness,
smoothness, scalability, and acceptable responsiveness.







Zhang/Liu                                                       [Page 1]

                       Expires: July 22, 2006           January 22, 2006

                           Table of Contents

     1. Introduction . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1. Terminology  . . . . . . . . . . . . . . . . . . . . . . .   4
     1.2. Related Documents  . . . . . . . . . . . . . . . . . . . .   4
     2. Protocol Overview  . . . . . . . . . . . . . . . . . . . . .   4
     2.1. Binomial Algorithm . . . . . . . . . . . . . . . . . . . .   5
     2.2. Packet Contents  . . . . . . . . . . . . . . . . . . . . .   5
     2.2.1. Sender Packets . . . . . . . . . . . . . . . . . . . . .   5
     2.2.2. Feedback Packets . . . . . . . . . . . . . . . . . . . .   6
     3. Data Sender Protocol . . . . . . . . . . . . . . . . . . . .   7
     3.1. Sender Initialization  . . . . . . . . . . . . . . . . . .   7
     3.2. Selecting Representative and Adjusting Sending Rate  . . .   8
     3.3. Assisting Receiver-side RTT Measurement  . . . . . . . . .   8
     3.4. Suppressing Feedbacks from Non-representative Receivers  .   9
     3.5. Determining Maximum RTT  . . . . . . . . . . . . . . . . .  10
     4. Data Receiver Protocol   . . . . . . . . . . . . . . . . . .  10
     4.1. State Diagram at Receivers   . . . . . . . . . . . . . . .  10
     4.2. Adopting Window Round Mechanism to Detect Congestion   . .  12
     4.3. RTT Measurement  . . . . . . . . . . . . . . . . . . . . .  12
     4.4. Calculating the Expected Sending Rate  . . . . . . . . . .  13
     4.5. Feedback and Feedback Suppression  . . . . . . . . . . . .  14
     4.6. Joining and Leaving Multicast Session  . . . . . . . . . .  15
     5. Security Considerations  . . . . . . . . . . . . . . . . . .  15
     6. IANA Considerations  . . . . . . . . . . . . . . . . . . . .  16
     7. Authors' Addresses . . . . . . . . . . . . . . . . . . . . .  16
     8. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . .  16
     9. References . . . . . . . . . . . . . . . . . . . . . . . . .  16
     10. Copyright Notice  . . . . . . . . . . . . . . . . . . . . .  17






















Zhang/Liu                                                       [Page 2]

                       Expires: July 22, 2006           January 22, 2006


1.  Introduction

The document specifies Binomial congestion control At Receivers for
Multicast (BARM) [1]. BARM is a receiver-driven single rate multicast
congestion control protocol. It has good TCP-friendliness, smoothness,
scalability and acceptable responsiveness, which makes BARM suitable for
congestion control of streaming media multicast applications. It can
scales to receivers sets on the order of several thousand receivers.

BARM is a building block as defined in RFC3048.  Instead of specifying
a complete protocol, this document simply specifies a congestion control
mechanism that could be used in a transport protocol such as RTP [2], in
an application incorporating end-to-end congestion control at the
application level. This document does not discuss packet formats,
reliability, or implementation-related issues.

BARM is designed to be friendly when competing for bandwidth with TCP
flows.  A BARM flow is defined as TCP-friendly when for each
sender-receiver pair, the multicast flow has the property of being
unicast TCP-friendly, that is, its existence does not reduce the
long-term throughput of any coexistent TCP flow more than another TCP
flow on the same path would under the same network conditions. BARM is
a single rate scheme whose sending rate is adapted to the receiver
experiencing the worst network conditions.

BARM is designed to keep good rate smoothness. Its rate fluctuation is
much smaller than that of TCP when network conditions change. It
achieves this at the cost of a reduced responsiveness to changes in
available bandwidth. Thus BARM should be used for applications which
have requirements for smooth throughput. For applications that simply
need to multicast as much data as possible in as short a time as
possible, PGMCC [3] may be more suitable.

To achieve a good scalability, BARM shifts most of the work to
receivers, and the mechanisms of representative selection and
distributed feedback suppression are used. The sender selects as the
representative the receiver with the lowest feedback rate, and updates
its sending rate according to expected rate of the representative. To
avoid feedback implosion, a feedback round suppression scheme is used
in which only selected receivers are allowed to send feedbacks, thus
decreasing the amount of feedbacks greatly. Compared with TFMCC [4][5],
BARM is easier in implementation and better in scalability, making it
suitable for multicast group with up to several thousands of receivers.

BARM is designed for applications that use a fixed packet size, and
vary their sending rate in packets per second in response to congestion.

BARM is most applicable for sessions that deliver a substantial amount
of data, i.e., in length from hundreds of kilobytes to many gigabytes,
and whose duration is in the order of tens of seconds or more.



Zhang/Liu                                                       [Page 3]

                       Expires: July 22, 2006           January 22, 2006


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 BARM implementations.


1.2.  Related Documents

As described in RFC 3048, BARM is a building block that is intended to
be used, in conjunction with other building blocks, to help specify a
protocol instantiation.  


2.  Protocol Overview

In general, as a single rate multicast congestion control mechanism, 
BARM works as follows:

- Each receiver independently maintains a variable called cwnd
  (congestion window) and measures the round-trip time (RTT) to the
  sender. It also maintains a state diagram similar to TCP. According
  to network congestion condition based on the arrival of the packets,
  receivers adjust their own cwnd separately. In particular, at
  Congestion Avoidance state cwnd is adjusted according to TCP-friendly
  binomial algorithm. In order to detect packet loss at receivers and
  emulate the behavior of TCP, a "window round" mechanism is introduced,
  and cwnd is updated at the end of each window round.

- Based on RTT and cwnd, each receiver calculates its expected sending
  rate, which reflects the network condition from sender to it.
 
- To avoid feedback implosion, most receivers' feedbacks are suppressed
  by means of distributed feedback suppression mechanism in which a
  "feedback round" scheme is introduced. The protocol gives more
  feedback probability to the receivers with lower expected rates.
  Receivers who get the chance to send feedbacks report their expected
  rate to the sender in so-called feedback reports. The feedback reports
  serve two purposes: they inform the sender about their expected
  sending rate, and they allow the receivers to measure their RTT.

- The sender selects as the representative the receiver with the lowest
  feedback rate, and updates its sending rate according to feedback rate
  of the representative. 




Zhang/Liu                                                       [Page 4]

                       Expires: July 22, 2006           January 22, 2006


The design of BARM references some mechanisms of TFMCC protocol (such as
feedback round scheme and RTT measurement). However, BARM is radically
deferent from TFMCC in their main mechanisms. Compared with TFMCC, BARM
[1] is easier in implementation and better in scalability.


2.1 Binomial algorithm

BARM adopts binomial algorithm [6] as the congestion window adjustment
scheme at the state of Congestion Avoidance (see section 4.1). At the
end of a window round (see section 4.1) during which there is no packet
loss, cwnd is increased according to equation (1):

     cwnd += a/sqrt(cwnd)                     (1)

When a receiver detects packet loss during a window round, it
immediately decreases its cwnd to the value given in equation (2):
   
     cwnd -= b*sqrt(cwnd)                     (2)

cwnd is the congestion window maintained at each receiver, while a and
b are two constants. The values of a and b are set to 0.28 and 0.2
respectively. Binomial algorithm with above parameters is the key to
TCP-friendliness and rate smoothness of BARM.


2.2.  Packet Contents

This section introduces congestion control information contained in the
packets sent by the sender and feedbacks packets sent by the receivers.
Information from the sender can either be sent in separate congestion
control messages or piggybacked onto data packets.

As BARM will be used along with a transport protocol, packet formats are
not specified, since these depend on the details of the transport
protocol used.  


2.2.1.  Sender Packets

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

- A sequence Number i: 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.





Zhang/Liu                                                       [Page 5]

                       Expires: July 22, 2006           January 22, 2006

- A representative receiver ID Rep_r: This value is to inform receivers
  of the current representative receiver. If there is no representative,
  the field should be set to 0 to indicate the difference from all the
  receivers. 

- State of representative receiver St_r: This value is to indicate the
  state of current representative. The state of SS or CA should be
  specified (see section 4.1).

- A current sending rate X_send in bits/s: A new joined receiver uses
  this value to calculate its initial cwnd. 

- A suppression rate X_supp in bits/s.  Only receivers with a calculated
  expected rate lower than the suppression rate are eligible to give
  feedbacks, unless their RTTs are higher than the maximum RTT described
  below in which case they are also eligible to give feedbacks.

- A timestamp ts_i indicating when the packet is sent. This value is to
  measure RTT from sender to a receiver. The resolution of the timestamp
  should typically be milliseconds.

- A receiver ID rcvr and a copy of the timestamp ts_r of that receiver's
  last report, which allows the receiver to measure its RTT.  ts_r which
  is included in the sending packet, needs to be adjusted by the time
  interval between receiving the feedback packet and sending data packet
  (i.e., that time interval has to be added to the timestamp value). The
  receiver ID is described in the next section.  The resolution of the
  timestamp echo should be milliseconds. 

- A feedback round counter fb_nr.  This counter is incremented by the
  sender at the beginning of a new feedback round to notify the
  receivers that all feedbacks for older rounds should be suppressed.

- A maximum RTT value R_max, representing the maximum of the RTTs of all
  receivers. All of the RTTs should be measured in milliseconds.  


2.2.2.  Feedback Packets

Each feedback packet sent by the receiver contains the following
information:

- A unique receiver ID rcvr indicating the receiver who sends this
  feedback packet. The ID should be a positive integer.

- A flag have_RTT indicating whether the receiver has made at least one
  RTT measurement since it joined the session.





Zhang/Liu                                                       [Page 6]

                       Expires: July 22, 2006           January 22, 2006


- A flag receiver_leave indicating that the receiver will leave the
  session.

- A timestamp ts_r indicating when the feedback packet is sent.  The
  representation of the timestamp should be the same as that of the
  timestamp echo in the data packets.

- An echo of the timestamp of the last data packet received.  If the
  last packet received at the receiver has sequence number i, then ts_i
  is included in the feedback.  If there is a delay t_d between
  receiving that last data packet and sending feedback, then ts_i' =
  ts_i + t_d is included in the feedback instead of ts_i. The
  representation of the timestamp echo should be the same as that of the
  timestamp in the data packets.

- A feedback round echo fb_nr, reflecting the highest feedback round
  counter value received so far.  The representation of the feedback
  round echo should be the same as the one used for the feedback round
  counter in the data packets.

- The expected sending rate X_exp.  This is the rate calculated by the
  receiver. The representation of the expected sending rate should be
  the same as that of the suppression rate in the data packets.


3.  Data Sender Protocol

The main tasks that are provided by a BARM sender are: (1) selecting the
representative from feedbacks of receivers; (2) adjustment sending rate
according to the feedbacks of the representative; (3) Determining the
Maximum RTT and assisting receiver-side RTT measurement; (4) suppressing
receivers' feedbacks using feedback suppression scheme.


3.1. Sender Initialization

At initialization of the sender, the maximum RTT is set to a value that
should be larger than the highest RTT to any of the receivers.  It
should not be smaller than 500 milliseconds for operation in the public
Internet.  The sending rate X_send is initialized to 1 packet per
maximum RTT and no_feedback_timer is set to expire after t_f second (12
times Maximum RTT is recommended). 

This process is terminated as soon as any feedback from one of the
receivers is received. After that, the representative is selected and
the sender sends packets at the rate that matches the representative's





Zhang/Liu                                                       [Page 7]

                       Expires: July 22, 2006           January 22, 2006


expected sending rate. At any time, if the sender does not receive any
feedback report from any of the receivers for some time (after
no-feedback-timer of t_f expires), it cuts its sending rate in half. The
lowest sending rate is limited to 1 packet every 64 seconds.


3.2. Selecting Representative and Adjusting Sending Rate

BARM is a single rate multicast congestion control whose sending rate
depends on the receiver experiencing the worst congestion condition.
Each receiver has an opportunity to send feedback packet reporting its
expected sending rate from the sender. The sender selects the receiver
that reports the lowest rate as representative receiver and adjusts its
sending rate accordingly. 

When a feedback from a receiver arrives at the sender, the sender has to
decide whether to change the representative and adjust its sending rate.
If no representative is present, the sender selects the receiver to
become the representative and adjusts its sending rate to the expected
sending rate of the receiver. If the representative is already present
but the receiver is not the representative, the receiver becomes new
representative only if its expected rate is smaller than current sending
rate. The sending rate is decreased to its expected rate. If the
feedback is from the current representative, the sender sets its current
sending rate to the expected rate in the feedback packet no matter the
expected rate is higher or lower than current sending rate.

If the receiver has not yet measured its RTT (i.e., the have_RTT flag is
set false), the receiver report will include a expected rate that is
based on the maximum RTT rather than the actual RTT to that receiver. In
this case, the sender adjusts the sending rate using its measurement of
the instantaneous RTT R_r to that receiver:

     X_exp' = X_exp * R_max / R_r

X_exp' is then used instead of X_exp to detect whether to switch to a
new representative.

When the representative leaves the multicast group, or if the sender
receives no reports from the representative for a period of time (after
no-representative-feedback-timer expires, 10 times Maximum RTT is
recommended), the sender will cancel the current representative (i.e.,
Rep_r should be set to 0) and start to select a new one.


3.3. Assisting Receiver-side RTT Measurement





Zhang/Liu                                                       [Page 8]

                       Expires: July 22, 2006           January 22, 2006


Each receiver measures its RTT by sending a timestamp with the feedback
packet, which can be echoed in the next data packet (It is necessary to
account for the time that elapses between receiving a report and sending
the next data packet). With the information of the receiver ID and the
echoed timestamp contained in the data packet, the corresponding
receiver measures its RTT. If more than one feedback from different
receivers arrive at the sender during the same packet interval, the
sender's timestamp echoes are prioritized in the following order:

- 1. a new representative (after a change of representative) or a
     representative without any previous RTT measurements

- 2. receivers without any previous RTT measurements in the order of the
     feedback round echo of the corresponding receiver report (i.e.,
     older feedback first)

- 3. non-representative receivers with previous RTT measurements 
     (again, older feedback first)

- 4. the representative.


3.4. Suppressing Feedbacks from Non-representative Receivers

The sender uses feedback round scheme to suppress lots of feedbacks from
non-representative receivers. The sending process is divided into
consecutive feedback rounds with a new round starting after the ending
of last round. Every feedback round is identified by a number fb_nr
which is also included in all packets sent during the current feedback
round. Each feedback round has duration T of Nt times Maximum RTT where
Nt of 8 is recommended. At the beginning of each feedback round, the
sender sets its suppression rate to a maximum possible value that can be
represented. Only if the expected sending rate of a receiver is smaller
than current suppression rate X_supp, or its RTT is larger than current
Maximum RTT can a receiver send its feedback.

When receiving a feedback report from a non-representative, the sender
resets its suppression rate to:

     X_supp = (1-g) * X_exp

Where X_exp is the expected sending rate of the receiver and g of 0.9 is
recommended.

After a time span of T, the current feedback round ends. The feedback
round counter is incremented by one and a new feedback round begins. The
suppression rate X_supp is reset to the highest representable value. 




Zhang/Liu                                                       [Page 9]

                       Expires: July 22, 2006           January 22, 2006


When the sender receives a feedback report from a non-representative
whose expected sending rate is lower than the expected rate of current
representative, the receiver becomes new representative.


3.5. Determining Maximum RTT

Maximum RTT is the maximum among all RTTs from sender to each receiver.
It is mainly used for suppressing feedbacks from receivers with
different RTTs. When receiving a feedback report from a receiver, the
sender calculates its instantaneous RTT Rs_ins to the receiver as:

     Rs_ins = t_now - ts_i

Where t_now is the arrival time of feedback packet, ts_i is timestamp
contained in the feedback packet. If the instantaneous RTT is larger
than current Maximum RTT, the Maximum RTT is adjusted to a new value as:

     R_max = Rs_ins

If no instantaneous RTT larger than Maximum RTT is received during
current feedback round, Maximum RTT is reduced to:

     R_max = MAX(R_max * 0.9, R_peak)

Where R_peak is the maximum receiver RTT measurement during the feedback
round.


4. Data Receiver Protocol

A congestion window (cwnd) and a state diagram are maintained
independently by each receiver, who adjusts cwnd according to current
state and the data packets received. Meanwhile each receiver measures
its RTT to the sender. Through the information acquired, the expected
sending rate is calculated which reflects the network condition from the
sender to it. In order to avoid feedback implosion caused by feedback
reports from lots of receivers, a feedback round scheme is used where
only selected receivers send their feedbacks.


4.1. State Diagram at Receivers









Zhang/Liu                                                      [Page 10]

                       Expires: July 22, 2006           January 22, 2006


                                         +---------+
                       packet drop       |         |----------  
                    -------------------->|   FR    |           \
                  /                      |         |<-----      |
                 |                       +---------+       \    |
                 |                                          |   |
                 |                                   packet |   |after
                 |                                    drop  |   |a RTT
                 |                                          |   |
            +---------+                  +---------+       /    |
            |         | cwnd >= ssthresh |         |------      |
    ------->|   SS    |----------------->|   CA    |           /
  /         |         |                  |         |<---------
 |          +---------+                  +---------+
 |               |                            |
 |after a RTT    |timeout                     |
 |               |                            |
 |               V                            |
 |          +---------+                       |
  \         |         |        timeout       /
    --------|   TO    |<--------------------
            |         | 
            +---------+ 
                     
                      BARM state diagram at receivers
                               Figure 1

Unlike TCP, BARM maintains a variable called cwnd at each receiver
instead of at the sender and adjusts it based on the arrival of the
packets. It greatly decreases the information that would be maintained
at the sender. For this a state diagram is set up at each receiver. The
states of BARM consist of four states: Slow Start (SS), Congestion
Avoidance (CA), Fast Recovery (FR) and Timeout (TO). Figure 1 shows the
state diagram at BARM receivers. 

Each receiver works as follows: Initially cwnd is set to 1. When the
first data packet is received, the receiver enters SS state, during
which the congestion window increases exponentially as Slow Start of TCP
to explore the network bandwidth available rapidly. This state does not
change until a packet loss is detected (see section 4.2) or the cwnd is
larger than SSthresh (the Slow Start threshold), when the receiver
enters FR or CA respectively. FR state is entered if a packet loss
occurs. At this state, the receiver decreases its cwnd immediately
according to the binomial decrease algorithm (equation 2). Then it waits
for a period of R (i.e., the measured RTT at the receiver, see section
4.3), and all the packets received during this time are ignored. At the
end of the RTT period, it changes to CA state. At CA state, the cwnd




Zhang/Liu                                                      [Page 11]

                       Expires: July 22, 2006           January 22, 2006


increases according to the binomial increase algorithm (equation 1). If
persistent congestion occurs so that a RTO (Receiving Timeout) timer
expires, it changes to TO state. After a period of R, the receiver
changes its state to SS and cwnd is set to 1.

The initial value of SSthresh is recommended to 64. When a packet drop
is detected at the state of SS, SSthresh is cut in half, while at CA
state SSthresh is set to m times current SSthresh. The value of m of
0.8 is recommended.

RTO (Receiving Timeout) is a period of time during which no data packet
is received. The value of RTO of 12 times Maximum RTT is recommended.  


4.2. Adopting Window Round Mechanism to Detect Congestion

Each receiver adjusts its window in terms of "window round".  The idea
of window round we use comes from TEAR [7]. The arrival of packets is
partitioned into non-overlapping window rounds. A new window round
begins when the current window round ends. If no packet loss occurs, a
window round contains roughly an arrival of the cwnd number of 
packets. If congestion detected, the current window round ends
immediately and after a period of R a new window round begins. At the
end of a window round, the receiver updates its cwnd. Because the
feedback at the end of the previous window round may take effect at the
sender after an R period, the protocol also maintains another variable
named lastCwnd at each receiver. lastCwnd is the value of cwnd at the
end of the previous window round. A window round ends only when
"lastCwnd" number of packets are received if no packet loss occurs in
current window round.

Like TCP, the receivers detect congestion by packet loss (in fact ECN
[8] can also be used to detect congestion). Each data packet has a
sequence number and the packets are transmitted in sequence. The
receivers each maintain a packet history that keeps track of which
packets have arrived and which are missing in the current round. If
congestion occurs resulting in a packet loss, there will be a gap in the
packet history. The loss of a packet is detected by the arrival of at
least three packets with a higher sequence number than the lost packet.
The current window round ends and FR state is entered immediately. If
the receiver gets less than three packets after a packet loss until the
packet with the largest sequence number in the current window round has
arrived, or if no packet is received during a period of time (one RTO),
the current window round also ends and TO state is entered.


4.3. RTT Measurement 




Zhang/Liu                                                      [Page 12]

                       Expires: July 22, 2006           January 22, 2006


A receiver measures RTT to the sender using timestamp contained in the
feedback packet. When a receiver receives a data packet that includes
the receiver's own ID in the rcvr field, the receiver updates its RTT
estimate.

The current RTT sample is given as:

     R_sample = t_now - ts_r

Where t_now is the time when the data packet arrives at the receiver and
ts_r is the receiver report timestamp echoed in the data packet.

Then the smoothed RTT estimate R is updated:

          If no feedback has been received before
              R = R_sample
          Else
              R = q*R + (1-q)*R_sample

A filter parameter q of 0.5 is recommended for non-representative
receivers. As representative receiver performs RTT measurements much
more frequently, a larger filter value should be used. We recommend
using q=0.9.  


4.4. Calculating the Expected Sending Rate

The updated cwnd can't be fed back to the sender directly. The value of
cwnd must be converted to the expected sending rate X_exp. First a rate
sample r is calculated as

     r = cwnd * packet_size / R

Where packet_size is the size of a data packet.

To further decrease the rate fluctuation, the weighted averaging over
rate samples taken over the past several rounds is applied. For this
reason, the expected receiving rate X_exp is given as

     R_tot = 0;
     W_tot = 0;
     for (i = 1 to n) {
       R_tot = R_tot + (r(i) * w(i));
       W_tot = W_tot + w(i);
     }
     X_exp = R_tot/W_tot;





Zhang/Liu                                                      [Page 13]

                       Expires: July 22, 2006           January 22, 2006


Where n the number of expected rate samples, r(i) being the rate sample
calculated in the recent ith window round. The value of n is recommended
to be 8. w(i) is the weight which is given as

     If (i <= n/2)
        w(i) = 1;
     Else
        w(i) = 1 - (i - n/2)/(n/2 + 1);


4.5. Feedback and Feedback Suppression

BARM uses feedback round mechanism to avoid the feedback implosion.
Every data packet arrived at the receiver includes a feedback round
counter value of fb_nr. When the receiver receives a packet with a new
fb_nr, it set a feedback timer. After the timer expires the receiver
sends a feedback report unless the timer is cancelled before the
expiration of the timer.

Feedback suppression mechanism is only used for non-representative. The
representative sends its feedback in each window round and its feedback
is independent from other receivers. The feedback from representative
neither is suppressed by feedbacks from other receivers nor suppresses
other receivers' feedbacks.
  
Let fb_nr be the highest feedback round counter value received by a
receiver.  When a new data packet arrives with a higher feedback round
counter than fb_nr, a new feedback round begins and fb_nr is updated.
Outstanding feedback for the old feedback round is cancelled. 

Non-representative receiver sets a feedback timer at the beginning of a
feedback round. Using an exponentially weighted random timer mechanism,
the feedback timer is set to expire after

     t = max(T * (1 + log(x)/log(N)), 0)

where

     x is a random variable uniformly distributed in (0,1),

     T is the duration of a feedback round (i.e., 8 * R_max),

     N is an estimated upper bound on the number of receivers. A value
of N of 10000 is recommended.

When the feedback timer expires, a feedback report is sent unless the
timer is cancelled before. The expected sending rate contained in the




Zhang/Liu                                                      [Page 14]

                       Expires: July 22, 2006           January 22, 2006


feedback packet is the one calculated by the receiver at the end of most
recent "window round". 

If the suppression rate contained in the sending data packet is lower
than the expected rate calculated at the receiver, AND the value of
maximum RTT in the data packet is higher than or equal to RTT (i.e., R)
computed at the receiver, the feedback timer is cancelled. This means
feedback for that feedback round is suppressed. Likewise, a data packet
indicating the beginning of a new feedback round cancels all feedbacks
for older feedback rounds.  


4.6. Joining and Leaving Multicast Session

A receiver may join or leave a BARM session at any time. A late joined
receiver should decide its initial congestion window size and initial
state according to current sending rate and the state of the
representative. Its initial cwnd is given as:

     cwnd = X_send * RTT_max

Where X_send is the sending rate contained in data packet, and RTT_max
being initial maximum value for RTT (500ms is recommended).

After that, the receiver adjusts its cwnd according to state diagram,
calculates expected sending rate and sends feedback report if permitted.

When the first RTT value is measured, the receiver should adjust its
cwnd to avoid abrupt fluctuation of expected rate:
  
     cwnd = X_exp * R

where X_exp is the expected sending rate, R being its measured RTT.
After that, cwnd is not adjusted when the value of R changes.

If a receiver wishes to leave the BARM session within the next feedback
round, it may indicate the pending leave by setting the receiver_leave
flag in its report. If the leaving receiver is the representative, the
receiver_leave flag should be set for all the reports within the
feedback round before the leave takes effect.


5.  Security Considerations

The associated security issues will be identified as further works to go
on. 





Zhang/Liu                                                      [Page 15]

                       Expires: July 22, 2006           January 22, 2006


6.  IANA Considerations

There are no IANA actions required for this document.


7.  Authors' Addresses

     Bing Zhang
     State Key Lab. of Integrated Services Networks
     Xidian University
     Xi'an, Shaanxi, 710071, China
     Zhangbing328@sina.com

     Zengji Liu
     State Key Lab. of Integrated Services Networks
     Xidian University
     Xi'an, Shaanxi, 710071, China
     zjliu@xidian.edu.cn


8.  Acknowledgments

We would like to acknowledge Joerg Widmer and Mark Handley who designed
TFMCC. Some mechanisms of BARM are based on or from TFMCC. For the
purpose for protocol integrity, the authors quote some of them in this
document. We would also like to thank Zhen Li and Yayan Xu who
participated in the implementation of the protocol.


9.  References

[1] B. ZHANG, Z. LIU, Y. XU, Z. LI, S. ZHANG, "Binomial congestion
    control at receivers for multicast", Proc. ITCOM 2004, Philadelphia,
    October 2004.

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

[3] L. Rizzo, "Pgmcc: A TCP-friendly Single-rate Multicast Congestion
    Control Scheme", Proc ACM SIGCOMM, Stockholm, Sweden, 2000.

[4] J. Widmer, M. Handley, "Extending Equation-based Congestion Control
    to Multicast Applications", Proc ACM SIGCOMM, San Diego, 2001.

[5] J. Widmer and M. Handley, "TCP-Friendly Multicast Congestion Control
    (TFMCC): Protocol Specification", Internet Draft




Zhang/Liu                                                      [Page 16]

                       Expires: July 22, 2006           January 22, 2006


    draft-ietf-rmt-bb-tfmcc-03.txt, July 2004, work in progress.

[6] D. Bansal, H. Balakrishnan, "Binomial Congestion Control Algorithm",
    Proc IEEE INFOCOM 2001, Alaska 2001.

[7] Rhee, V. Ozdemir, Y. Yi, "TEAR: TCP Emulation at Receivers - Flow
    Control for Multimedia Streaming", Tech. report., Dept. of Comp. 
    Sci., NCSU, April 2000.

[8] K. Ramakrishnan and S. Floyd, "A Proposal to add Explicit Congestion
    Notification (ECN) to IP", RFC 2481, January 1999.


10.  Copyright Notice

Copyright (C) The Internet Society (2006).  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.

























Zhang/Liu                                                      [Page 17]