Notes on FEC supported congestion control for one to many reliable multicast. Working Draft

A NGEWANDTE M ATHEMATIK UND I NFORMATIK
U NIVERSIT¨AT ZU K¨OLN
Report No.98.334
FEC Supported Congestion Control
in One to Many Reliable Multicast
by
Frank Brockners
August,1998
Center for Parallel Computing(ZPR)
University of Cologne
Weyertal80,D–50923K¨o ln
Keywords:Congestion Control,Forward Error Correction(FEC),Reliable Multicast
FEC Supported Congestion Control in One to Many Reliable Multicast
Frank Brockners
Center for Parallel Computing(ZPR)
University of Cologne
brockners@zpr.uni-koeln.de
Technical Report ZPR-TR98-334
August,1998
Abstract
This paper describes the design of a new FEC fueled rate and congestion controller(RCR)which is targeted primarily at one to many reliable bulk multicast data transfer.The concept of RCR is validated by analytical and simulation results.The heuristic analysis is based on a new extended model forflows, which implement a congestion control algorithm similar to TCP.The main goal was to develop an algorithmwhich is TCP-friendly and competes with the control loop of rge de-lays in the control circuit,scaling issues and high packet loss probabilities are among the major challenges of a reliable mul-ticast rate controller implementing TCP-fair congestion con-trol.The controller presented in this paper shows that layered forward error correction(FEC)redundancy coding not only re-duces the control-and retransmissions in reliable multicast en-vironments using automatic repeat requests(ARQ)to trigger retransmissions but also helps a congestion controller to com-pete with TCP.FEC permits the receivers to tolerate losses in a way that they only need to signalize loss levels which are sig-nificant for them.This high-passfiltering of the loss signal re-verts the disadvantage of reacting slowly to loss into an advan-tage in direct comparison to TCP.The greater responsiveness with respect to rate increment ensures that TCP always receives its share of the total available bandwidth.Simulations and ana-lytical analysis for multicast as well as unicast setups show that already a very moderate level(some%)of redundancy suffices to strengthen a connection suffering from long delays and high loss probabilities.
Keywords:Congestion Control,Forward Error Correction, Reliable Multicast.
1Introduction
Congestion control is vital for the internet and is even more important for reliable multicast setups.Besides fairness and throughput considerations,flow and congestion control has been recognized as a major problem for reliable bulk multicast data transfer.
Existing approaches for congestion control schemes in reliable multicast can be devided into closed-loop and open-loop con-trol schemes.All closed loop control schemes have in common that receivers send some kind of feedback information(either positive or negative acknowledgements)back to the source. The source evaluates the feedback information and accordingly adjusts its emission rate.A great varience of the present re-liable multicast frameworks use closed-loop congestion con-trol.In open-loop scenarios a control path from the receivers to the source does not exist.Open-loop solutions employ a pre-configured rate,high levels of redundancy coding or repeated transmissions.Repeated transmissions denotes the sending of the same information elements multiple times.This may ei-ther be at different times or to different multicast groups.The controller presented in this paper primarily relies on close-loop congestion control but also employs aspects of open-loop con-trol,as it utilizes redundancy coding to increase protocol effi-ciency.
We take a short glance at the different approaches forflow and congestion control for reliable multicast before study-ing our approach which integrates TCP-fairness and TCP-competitiveness.
Sender-initiated approaches forflow control that use posi-tive acknowledgments(ACKs)always face the ACK implo-sion problem while receiver oriented schemes do so too in the absence of an NAK aggregation or suppression scheme.In [1]Towsley et al.demonstrated that receiver-initiated(NAK 1
based)error recovery usually is superior to sender-initiated er-ror recovery.Depending on the way how receiver initiated pro-tocols solve the NAK implosion problem,they can be divided into(1)timer based,(2)deterministic and(3)structure(tree-)based approaches.Examples include SRM[2]for a timer based,DTRM[3]for deterministic and RMTP[4]as well as TMTP[5]for tree based approaches.
In each of these approaches the emission rate is either re-stricted to a small tolerable level or a TCP-like congestion control is implemented in order to prevent or resolve conges-tion.RMP[6]and RMTP serve as examples for TCP-like window controlled congestion control schemes.Both rely on positive ACKs,either to the toke site(RMP)or to the desig-nated receivers(RMTP).NAK based schemes significantly re-duce protocol control traffic but lack a control signal to clock themselves(like ACKs in TCP do).Instead they usually em-ploy some kind of of rate control.Explicit rate adjustment is common for most of the approaches.Be it close-loop con-gestion control(RMTP[4],TMTP[5])or open-loop con-trol with afixed emission rate like yered multicast schemes,including the one based on FEC which transfers the TCP-principles of congestion window increase and decrease to group joins and leaves of the receivers[7]are examples for open-loop congestion control.A problem common to all con-trollers interpreting loss as a congestion signal is,that packet loss is very likely to occur:For a heuristic argument one may think of uncorrelatedflows on disjoint paths in the network, each with a packet loss probability of1%.The overall packet loss probability amounts to as much as40%.Loss rates of this magnitude destroy any kind of TCP-like congestion control[8]–A rate controller would end up with the minimum emission rate permitted.[9]and[10]give an in depth analysis of the loss pattern of the MBone.A possible solution of this problem is to tolerate a certain amount of loss.[11]discusses a monitoring based approach whereas LTRC[12]directly measures the loss rate and adjusts the rate increase-decrease function of the con-troller.
Theflow-and congestion controller RCR presented in this pa-per also uses a TCP-like emission rate control and redundancy (FEC coding)to implement loss tolerance.FEC enables each receiver tofilter the loss signal locally and to react to the oc-curance of loss individually.The active use of redundancy in the control circuit compromises between TCP-friendliness and TCP-competitiveness.
This paper is structured as follows:After a short overview about the distributionmodel,section2focuses on some aspects of reliable congestion control and discusses the fairness aspect. The discussion of the design of the controller in section3is followed by an analytical model of the controller for the later analysis in section5.Section5compares the results obtained
from the model with those of a prototypical implementation within the ns-2[13]network simulation tool.
1.1Overview of the distribution model
We follow our protocol design given in[14]of a one to many distribution model which runs on top of the IP-multicast ser-vice and is tree based.It is reliable in a way that a receiver either receives all data correctly or is able to detect an unre-coverable situation.The protocol achieves reliability by using both-redundancy coding(FEC)and automated repeat requests (ARQ).It follows a complete receiver initiated retransmission scheme and uses the ttl hop count to form local groups.The burden for correct reception of all packets is carried by the re-ceivers.By means of an expanding ring search each receiver finds a so-called leader,who is closer to the source and has the capability to locally retransmit packets with a limited hop count value.This implies that the IP multicast tree has to be symmet-ric.Receiver feedback(e.g.ARQ)is sent to the leader only, who decides whether to forward,take actions,or simply dis-card it.The sender does not keep any state information about the set of receivers.
The controller this paper is about only uses[14]as framework. The tiny and straight forward rate control algorithm described in[14]was completely replaced.Therefore,the results and conclusions of this paper can easily be transferred to other mul-ticast and even unicast scenarios.
2Some design issues
2.1Fairness considerations
Stability and robustness of the internet heavily depend on con-gestion controlledflows.A controller has to interpret packet loss as a congestion signal and back off its emission rate in con-ditions of loss.With a constantly growing internet,end-to-end congestion control becomes a vital factor.In[15]Floyd and Fall show the negative effects offlows which are unrespon-sive to loss and emphasize the need for continuing the use of end-to-end congestion control.Therefore,they propose router mechanisms to restrict the bandwidth of best effortflows to a disproportionate share of the overall available bandwidth.Up to90%of today’s internet W AN traffic uses TCP[16]as trans-port protocol.This motivates new protocols to take TCP as ref-erence and adjust their congestion control to be TCP-friendly.
[15]defines aflow to be TCP-friendly,if the arrival rate of theflow does not exceed the bandwidth of a corresponding TCP connection under the same circumstances.Basically this may be achieved by a control algorithm similar to the method employed by TCP,i.e.by reducing the emission rate to half 2
of the original value in case of congestion and by increasing the emission rate to no more than one additional packet per round trip time(RTT)otherwise.The congestion control al-gorithm of TCP constantly checks the network for additional bandwidth by linearly increasing the congestion window.In case of loss,TCP backs off exponentially by reducing its con-gestion window to half of its original size.The fast response of TCP to losses keeps the competition among large sets of TCP-connections fair.
The nature of reliable multicast as a point to multipoint control scheme may have a significant negative impact on the overall throughput of the network.A reliable multicast protocol run-ning in parallel with TCP primarily faces two facts:(1)TCP re-acts to loss quite rapidly and(2)TCP(New-RENO/SACK)re-covers from a drop(quite)fast.While thefirst one makes TCP (and the overall network)vulnerable to applications which do not implement congestion control the second capability makes TCP a tough competitor for
bandwidth.
Figure1:RM source without FEC support in a setup with
.
In particular tree-based reliable multicast protocols which ag-gregate feedback at the tree nodes introduce further delay into their control circuit.Delay and timers keep them from over-reacting to certain constallations because they virtually have to react to the‘wishes’of thousands of receivers.Therefore they are not in the condition to be highly adaptable to changes. But in order to be TCP-friendly they have to exponentially back off their rate on discovering heavy loss.Additionally,it is de-sirable to restrict the amount of expensive control traffic to a minimum.This results in a very conservative increment of the emission rate of the source after rate back off.One possibility to solve this contradiction between speed and fairness is to im-plement forward error correction.FEC works as a high pass for the loss signal.In case of low,uncorrelated loss the source will not be requested to slow down.With FEC,every receiverfilters
his individually observed loss signal and only reacts if loss ex-ceeds the level which could be tolerated through FEC coding. If such a scheme is run with a couple of TCP connections in parallel,we observe the following:If loss is distributed equally among all active connections,TCP will also discover the loss situation and immediately correspond to it.Immediate means faster than the reliable multicast connection running in paral-lel.Once the high-pass(FEC)filter produces an output signal, a receiver issues a congestion notification packet which is for-warded towards the source leading the source to drop its emis-sion rate to half the current rate.Additionally,the source ad-justs the gradient of the emission rate to half the current value. Figure1shows a RM source with a far slower control circuit than a TCP connection operating in parallel.In the absence of redundancy,the source has to react to every packet loss in the network.TCP recovers much faster from a loss and wins the competition for the bottleneck bandwidth.
2.2Partial decoupling of congestion and re-
transmission control
An environment which uses rate control at the source and re-lies on local repair retransmissions for loss recovery faces a principle problem:If the receive window of receivers,which are elected to do local retransmissions,is not smaller than the transmit window of the sender,sets of receivers may lose track of the transmission,although they have sent negative acknowl-edgements in time.Therefore,retransmission control and con-gestion control has to be decoupled partially.This results from the fact that retransmission control often has only local scope whereas congestion control always has to take into account the whole
group.
Figure2:Network example to explain the necessity of a par-tial decoupling of congestion and retransmission control.The elected protocol control tree and local buffer sizes are shown. Consider a network constellation like infigure2with three re-ceivers(3,4,5)and one source(0).Two receivers are connected to the source through a bottleneck link.The control tree is shown with dashed lines.Node works as leader(this is a
3
receiver,which is elected to aggregate and forward NAKs as well as to do local retransmissions)for nodes and and is re-sponsible for NAK and retransmission control for these nodes. Assuming,that loss will only occur on the bottleneck link,re-ceivers and will force receiver to retransmit lost packets. As receiver cannot notice any loss situation by itself,it does not need to contact its leader which is source in the given ex-ample.Besides,the problem of increasing congestion through the retransmissions of receiver this scenario might lead to a situation where one of the receivers or requests the retrans-mission of a packet which was already removed from the buffer of.This is thefirst time,needs to contact its leader that nei-ther holds the packet in its buffers any longer,as its buffer has the same size as that of receiver.A naive solution for this problem is to ask for very large buffers at the source—buffers that are larger than the buffer of any receiver.This is imprac-tical because the buffer capabilities are usually not known by the sender.The suitable solution for this problem is to partially decouple congestion and retransmission control:Another con-trol message is used to signal congestion to the source.These congestion notification messages(CGN)are also transmitted through the control tree but are always forwarded to the source. In addition,the control tree is used to aggregate the conges-tion notification messages to avoid a CGN implosion problem. Congestion notification messages inform the source about the first packet lost and the amount of loss the receivers observed. 3The design of the rate controller
The rate controller(RCR-a Rate Controller supported by Redundancy)achieves TCP-friendliness and TCP-competitiveness by implementing a TCP-like control process which is supported by redundancy through FEC coding. TCP-friendly rate controllers[17]have been proposed for unicast[18]and also reliable multicast[12]environments. LTRC,as presented in[12]achieves competitiveness by adjusting the reaction of the controller to loss depending on the amount of loss encountered by the receivers.RCR is the first controller to actually implement and analyze the effects of FEC deployment within the controller.FEC can be used to high passfilter the loss signal in a very efficient way to be loss tolerant.In contrast to controllers implementing loss tolerance at the source,FEC focuses loss tolerance on the receivers.This reduces the susceptibility of the controller to delay in the control circuit and the amount of control traffic from the receivers which would otherwise be aggregated(e.g. in tree-based protocols like RMTP[4])or suppressed(e.g.in SRM[2]).In contrast to TCP(which is clocked by ACKs)the RCR is clocked by time as long as the time interval between two packets is smaller than the time-outs for rate increase or rate decrease.Otherwise the packet-scheduler clocks the controller.
Although being designed for a reliable multicast environment (because big latencies in the control process are common for reliable multicast)the concepts of the controller apply to uni-cast environments as well.
Source and receivers participate in the congestion control scheme of RCR.Receivers issue NAKs or congestion notifica-tion messages(CGN).NAKs are sent to the individual leader of a receiver,while CGNs are directed towards the source.Both are unicasted and both follow the control tree formed by the election process.The following sections describe the part of the sender as well as the part of the receiver of the control process in detail.
The following sections describe the rate control at the sender and at the receivers as well as the determination of the para-meter“round trip time”in detail.While congestion control at the sender closely follows the design principles of TCP,FEC usage allows fundamental modifications at the receivers.The resulting controllersuits the need for a controller which is TCP-friendly and TCP-competitive.
3.1Sender
Theflow and congestion control of the sender consists of two parts.During the start phase the sender multiplicatively in-creases the send rate.In the absence of any concrete knowledge of the network or the receivers the sender starts at a given min-imum rate and lowers the inter packet time gap by a constant factor after each timer expiry.After being notified of conges-tion in the network the sender switches to the main phase and henceforth only linearly increases the
rate.
Figure3:Congestion control state diagram of the sender At transmission startup time,the sender initializes the inter packet gap to
emission rate.After a minimum time interval of TMO seconds the inter packet gap is reduced to
(2) with representing a constant factor.We use in our simulations.Thefirst NAK or CGN packet reaching
the sender leads him to switch to the main phase and enter the INCREASE state.Cycle count variable(
)and the addend determining the following rate incre-ment are initialized.The cycle count partially determines the gradient of the rate increment after a significant drop and will be explained and discussed in a forthcoming section.The value of depends on the timeout value TMO for reducing the inter packet gap and the round trip time.The determination of will be discussed in section3.2.
1At this point one may think of varying the direct TCP-analogy.Instead of doubling,it may be multiplied by a loss dependent factor,so that .is to enable the controller to react to different loss rates dif-ferently and therefore be loss tolerant.LTRC[12]basically relies on this mech-anism to achieve loss tolerance.In our simulations we studied the following scenario,inspired by the idea to reduce the emission rate by a factor smaller than if the loss is close to a value a FEC block code(We always use and as the FEC coding constants.An erasure code is capable of re-covering the original data packets from any different packets out of the coded packets.)could cope with:
(4)
with and.denotes a factor which weights the frac-tion.The quantitative loss signal can easily be included in the NAK packets.Our simulations have shown,that determining reasonable values for loss and is a difficult task in complex network setups.The amount of loss and the time of detection are not always correlated.There might be receivers which experience low loss rates and are positioned close to the source whereas other receivers positioned far from the source may experience high loss rates but their NAKs are suppressed because a retransmission is already in progress. Furthermore,bursty losses,which are common with drop-tail routers,make the computation of a mean loss rate,e.g.with a low passfilter like an exponential weighted moving average(which works well for estimating the average queue length of a RED router),very difficult.Although the proposed RCR is able to adjust to different loss rates it does not do so in practice.We therefore chose a constant function for all simulations presented in this paper. The simulation results presented show that it is far better to use FEC to imple-ment loss tolerance than to include the tolerance into the dynamic process of rate adaptation at the sender.This is due to the fact that the sender needs tofind a rate which suits all the receivers needs,whereas FEC gives each receiver a Besides the actual rate drop,the changing to INCREASE state is accompanied by an adaptation of gradient of the emission rate.
(8) On approximating the non continuous progression of the emis-sion rate(which is a staircase function in reality)by a continu-ous function,the emission rate has a constant gradient.
3.2The round trip time
The value used for the packet round trip time has a significant
influence on the overall behavior of the control circuit.It de-termines the gradient of the emission rate and subsumes buffer
effects in the network as well as propagation and processing
times.While the definition of the round trip time is straight for-
ward in the unicast case,things are much more complicated in
the multicast case because there is no unique round trip time.
A close timely relationship between sender and receivers like
in TCP does not exist.
To determine a value analogously to the round trip time in the
unicast case,RCR uses the maximum of the round trip times
noticed by the sender.This re-sults in a robust and TCP conformable control circuit.As with
TCP,it assures that the effects of a rate increase are noticeable by the sender within one round trip time.V alues
have the disadvantage that the sender increases the emission
rate before a response of the last rate increase can reach him.
This leads the sender to overestimate the available bandwidth
and gives rise to large oscillations.By choosing
the RMflow is reduced more than necessary.
already means a discrimination,because is much larger than
the RTT of a TCP connection on the same network path.This
results from the fact that the NAK and CGN packets do not take
the direct route to the sender but follow the control tree.
The computation of follows the principles of the NTP
algorithm[19]and is similar to the one used in[2].Due to
the lack of positive acknowledgments,RCR uses the NAK and CGN packets to transport the timing information.As the fre-quency of occurrence of the NAK and CGN packets cannot be compared to that of TCP-ACK packets,the computed value for contains a significant amount of insecurity.Note that an over-estimation of is less dangerous than an underestimation. This is reflected in the sender’s evaluation of the RTT measures .If is larger than the actual used one,is assigned its value.To respond to network dynamics,smaller measures are also taken into account but will lower significance.Again,an exponential weighted moving average is used in this case.
(9)
One important fact to note when using negative acknowledg-ment packets for the RTT computation is that this setup auto-matically measures the RTT of the connection suffering from congestion.If for example the congested path is close to the source,the sender receives a congestion signal quite fast and therefore computes a small round trip time.NAK-packets from receivers which noticed the loss later than the one close to the source are suppressed and do not influence.
3.3Receiver
Corresponding to the election process at the beginning of each transmission the set of receivers falls into two groups,i.e. nodes that were elected to retransmit(leaders)and nodes that receive only.As retransmissions also may have a severe impact on overall network performance,the leaders also need some kind of rate
control.
Figure4:Congestion control state diagram of a leader.
A state diagram of a leader resembles that of the sender.As shown infigure4a third state named SET is added to the ex-isting states INCREASE and DECREASE.The CGN packet is sender specific and therefore left out.SET couples the re-transmission rate to the packet emission rate of the sender. Each leader permanently evaluates the data packet arrival rate–again as inter packet gap and computes an estimated inter packet gap:
(10) New data packets reaching the leader in correct sequence al-ways force the emission rate of the leader to reflect the incom-ing rate:.The parameter of the cycle count is initialized to.When receiving an NAK packet,the leader re-duces its retransmission rate to half of the current value.As long as no new data packets are received the rate control of the leader totally resembles that of the sender.In the absence of any reasonable definition of round trip time at the receivers a constant value of one second is used.
A receiver has two different options to signalize loss and con-gestion to his leader.Negative acknowledgements(NAK)re-port missing packets to the leader and request their retransmis-sion.NAKs simultaneously act as a congestion signal.A NAK packet may contain reports for more than one missing packet. Their structure resembles that of TCP-SACK packets[20]and draws a detailed picture of the receiver’s receive window.Con-gestion notification packets(CGN)are direct loss signals from a receiver to the sender.A CGN signal decouples congestion 6
notification from the retransmission mechanism,as shown in section2.2.
Receivers detect lost packets through gaps in the packet num-ber sequence space.Each entry in the receive window is ac-companied by an entry in a scoreboard,which keeps state in-formation like timer and status information for that packet.The scoreboard is checked immediately if a new data packet is re-ceived.Otherwise it is consulted in a timely manner.Out of sequence arrival is easily detected by comparing the value of holding the sequence number of the next packet ex-pected to the sequence number of the packet which just arrived.If the scoreboard is checked immediately and the receiver decides whether to react with a CGN/NAK packet or
not.
Figure5:FEC fueledfilter capabilities at the receiver. Leaders that receive an NAK packet consult their scoreboard tofind out whether the requested packet resides in their receive window,an NAK for this packet has already been sent to their leader or timer constraints exist,which refuse a reaction to the ACK.Assuming that no timer restrictions exist,a leader for-wards the ACK to his leader if it does not have the requested packet(s)in memory or in the other case schedules a retrans-mission for the packet(s).Leaders never show any response to a CGN packet.CGN packets are always forwarded towards the sender–or suppressed by timers.The frequently mentioned timers assure that a minimum time interval exists be-tween two retransmissions for the same packet,two CGN,or two NAK packets.
The decision,whether to send an NAK or CGN packet is based on two criteria:age of FEC redundancy:By interpreting packet loss as
a signal FEC may be used as a high passfilter.The para-
meters of the FEC block code determine the over-
all behavior of the controller.If the receiver uses FEC to the full extend for being loss tolerant,it tolerates
lost packets per block without issuing an NAK or CGN
packet.If denotes the number of packets already re-
ceived for block and is the packet sequence num-
ber relative to the start of the block.The formal condition for reads
(11)
Section5shows on the basis of simulations and calcula-
tions that the amount of redundancy has to be chosen very
carefully to achieve TCP friendliness as well as TCP com-petitiveness.A full exploitation of the redundancy is not
always applicable.Figure5gives four examples offil-
ter functions.The-axis shows the number of packets sent by the source,the-axis the number of pack-
ets reaching the receiver.If the number of packet re-
ceived drops below the threshold,the receiver stops tolerating losses and requests retransmissions via an NAK.
The curves shown with bold lines describe the situation
if one resigns to use FEC(curve A)or uses FEC to the maximum(curve D).Possiblefilter functions belong to the gray area.Curves B and C are examples for alternative functions.Functions similar to B are applicable in scenar-ios with a high level of redundancy deployed.
Only part of the redundancy is used for congestion con-trol purposes in order to preserve TCP fairness.A receiver can react in two possible ways:If and
the receiver only issues a CGN packet, otherwise it has to send an NAK packet.
The function types represented by curve C(。