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 for?ows, 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 https://www.doczj.com/doc/ef6016924.html,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-ni?cant for them.This high-pass?ltering 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 suf?ces 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,?ow 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-con?gured 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 ef?-ciency.
We take a short glance at the different approaches for?ow and congestion control for reliable multicast before study-ing our approach which integrates TCP-fairness and TCP-competitiveness.
Sender-initiated approaches for?ow 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 signi?cantly re-duce protocol control traf?c 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 a?xed emission rate like https://www.doczj.com/doc/ef6016924.html,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 uncorrelated?ows 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.
The?ow-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 to?lter 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 ?nds 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 controlled?ows.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 of?ows 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 effort?ows to a disproportionate share of the overall available bandwidth.Up to90%of today’s internet W AN traf?c 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]de?nes a?ow to be TCP-friendly,if the arrival rate of the?ow 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 signi?cant 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 the?rst 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 traf?c 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 receiver?lters
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)?lter produces an output signal, a receiver issues a congestion noti?cation 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 in?gure2with 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 the?rst 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 noti?cation 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 noti?cation messages to avoid a CGN implosion problem. Congestion noti?cation messages inform the source about the ?rst 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 ?rst controller to actually implement and analyze the effects of FEC deployment within the controller.FEC can be used to high pass?lter the loss signal in a very ef?cient 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 traf?c 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 noti?ca-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 modi?cations at the receivers.The resulting controllersuits the need for a controller which is TCP-friendly and TCP-competitive.
3.1Sender
The?ow 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 noti?ed 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.The?rst 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 signi?cant 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 dif?cult 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 pass?lter like an exponential weighted moving average(which works well for estimating the average queue length of a RED router),very dif?cult.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 to?nd 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 signi?cant
in?uence 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 de?nition 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 RM?ow 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 signi?cant amount of insecurity.Note that an over-estimation of is less dangerous than an underestimation. This is re?ected 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 signi?cance.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 in?uence.
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 in?gure4a third state named SET is added to the ex-isting states INCREASE and DECREASE.The CGN packet is sender speci?c 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 re?ect 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 de?nition 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 noti?cation packets(CGN)are direct loss signals from a receiver to the sender.A CGN signal decouples congestion 6
noti?cation 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 fueled?lter capabilities at the receiver. Leaders that receive an NAK packet consult their scoreboard to?nd 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:https://www.doczj.com/doc/ef6016924.html,age of FEC redundancy:By interpreting packet loss as
a signal FEC may be used as a high pass?lter.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 of?l-
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).Possible?lter 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(
a static timeout value which takes into account the size of the local receive window.If a receiver has a receive win-dow of size FEC blocks and denotes the mini-mal inter packet gap used by the sender,the minimal time interval is chosen as follows:
(13) This result may be directly mapped to the case discussed here, because RM and TCP connection are following exactly the same algorithm if we apply the simplifying assumptions and no FEC is used.
(14) For equal round trip times the packet loss prob-ability is.
4.2Generalized model
The generalized model introduces FEC redundancy and the cy-cle count to adjust the gradient of the emission rate after each rate drop.We now give up the assumption,that the connections react on every packet loss to investigate the in?uence of FEC on a?ow and congestion controller similar to TCP.The other assuptions made in section4.1still hold.Especially,we still employ poisson distributed losses but change the way we react to losses.
Because of the introduction of the cycle count into the control process,the system is no longer stateless and can no longer be interpreted as a markov process.The markovian property that the present state must be independent of the past states is vio-lated.
Again let be the bandwidth of the bottleneck link in bit/s and the percentage of bandwidth occupied by TCP and the RM connection respectively,when a signi?cant packet drop happens.The th signi?cant packet drop takes place at time.
and are only de?ned for the discrete times.At time we have.A packet drop is said to be signi?cant if either the TCP or the RM connection react to the drop.We use“”to represent the event that the TCP connection registers a signi?cant packet loss and“”to represent the event that the RM connection registers a signi?cant packet loss.Let the prob-abilities for the two events be and:, with.Further,let be the time elapsed between two packet drops.and denote the ex-pected values of and for the steady state,i.e.for. Each(and analogously)is de?ned by a corresponding event vector out of the event space.
.de?nes a function mapping
the event space to the interval.E.g.With a possi-ble event vector could be which means that?rst, the TCP connection registers a packet drop and then the RM connection registers two packet drops in sequence.For
we obtain the event space
.
The corresponding interation formulas for each and ,which are deduced in the next section,are applied ac-cording to the event sequence de?ned by.is ran-domly chosen from the interval.
We obtain the expected value for as
(15)
with denoting the probabilility of event .signi?es the number of signi?cant packet drops the TCP connection registers:.
Figures8and7illustrate the meaning of different variables de-?ned above.Figure7shows the situation,where TCP connec-tion reacts to lost packets two times in a row.In?gure8the RM connection is the?rst one to detect a lost packet.After this the TCP connection reacts to loss and?nally it is the turn of the RM connection again.In contrast to?gure7a cycle count different from zero was chosen():At time the gradi-ent of the emission rate is reduced to half of the original value and is set back to this value at time.denotes the cycle count with.After bisections of the emission rate the initial value of is adopted again.After steps the gradient reaches its minimum
.
Figure7:Example of the rate control of the sender for a reac-tion series TCP,TCP and.
9
Figure8:Example of the rate control of the sender for a reac-tion series RM,TCP,RM and.
Other interesting expected values include the transferred in-clude the amount of data during time.The bandwidth of the TCP connection in steady state results to. The expected values for throughput and duration of the TCP connection are computed with a similar formular,as both are functions of.In steady state we obtain:
(16)
(17)
of the overall bandwidth,whereas the RM connection receives an additional part of.The index of denotes the actual value of the cycle count.
At time the following equation holds for the bandwidth of the congested link:
(20) we obtain the expression determining the iteration step from
to for the condition that the TCP connection drops its rate at
Inserting this result,we obtain for
(22) From this result we can derive the transferred amount of data for the TCP connection during with respect to.
is represented by the gray area in the examples shown in ?gures7and8.
(23) The transferred amount of data for the RM connection is ob-tained analogously
Case B:The RM connection registers a signi?cant packet loss(Event“”)The computations here are completely sim-ilar to the previous case.Here the resulting bandwidth equation is
4.3.1Evaluation of with the assumption
With the assumption of a stateless process()we can
evaluate equation15which de?nes the expected value for.
We will show that in this special case the bandwidth will be dis-tributed according to equation13which was derived in[23]. To compute the expected value we?rst derive an iter-ation formula for as a function of.With a given event vector we denote
the corresponding event vector formed out of the?rst com-
ponents as:.
(25) This iteration de?nes a Banach series
which converges to the?xed point of the function
if;. For we obtain
For the expected value of we obtain with:
In the absence of an interaction free representation for equation
15with we realized the iteration formulas as functional
programs and evaluated them with Mathematica[25].
It is now possible to describe the effects of varying drop prob-
abilities but we still lack a description of the FEC in?uences.
The next section links the actual in?uence of FEC usage to the
model.The derived relationship between and assumes
a complete usage of the redundancy for the purposes of
congestion control–This corresponds to curve D in?gure5.
4.4Relationship between packet loss probabil-
ity and the parameters of the block
code
Let be the total number of losses at the gateway2.Again we
assume a setup like in?gure6with two connections,one TCP
and one RM competing for bandwidth on a congested link.The
total number of losses is divided into the number lost packets
belonging to the TCP connection and those belonging
to the RM connection.It is.For
the packet loss probability of the TCP connection we obtain
and in analogy.
If FEC is used for the?ow control of the RM connection,
,the absolute size of
and is also signi?cant for the process.The absolute size of
determines the amount of data being transferred be-
tween two subsequent packet drops.is represented by
the gray area the example in?gure8.
(31)
The value of is determined by the model chosen and
the RTT of the connections.Figure10shows as a function
of for different cycle counts.Especially the area with rel-
atively small FEC redundancy is very interesting:
Minor changes of the redundancy level result in major changes
12
Figure10:as a function of the coding parameters with .
of the packet drop probability of the TCP connection.The RM connection already becomes less resilient for small values
and reduces TCP throughput signi?cantly.The reason for this behavior can also be derived from the TCP control loop,which has a strong sensitivity to a change of the packet loss proba-bility.Jacobson shows in[8]that for given round trip time, window size the throughput is a function of the packet loss probability:
a simulation time of400seconds.The packet size was chosen to be536bytes for both connections,the gateway used RED queue management with a queuelength of30packets.The cy-cle number was,i.e.the process was stateless.
can be interpreted as a measure for the TCP disconformity.In a setup where both connections receive the same throughput,a small amount of redundancy suf?ces to discriminate the TCP connection.10%-15%redundancy are enough to reduce the throughput of TCP to the half of the original value.The very good responsiveness bears dangers when higher levels of re-dundancy are deployed.The less resilient the RM connection
is,the more prejusticed parallel TCP connections are.There-fore the coding parameters have to be chosen very carefully. Otherwise one may break the control circuit of TCP.If a high level of redundancy is used to minimize control traf?c and re-transmissions,one should not use the full redundancy for the control circuit but deploy a?lter function utilizing only a part of the redundancy(like curve B in?gure5).The larger the FEC blocks are,the more effective is the use of redundancy[26]. This rule also holds for the situation described here as well,as ?gure11shows.If the block length grows while the relative level of redundancy is kept constant,the number of recover-able packets which are crucial for the behavior of the controller grows as well.So the controller becomes even less sensitive to packet loss for growing if is kept constant. In order to prevent this,we suggest choosing relatively small .This is also motivated by the current software codecs based on linear block codes.They perform well for up to ([27],
[28]).
Figure13:Blocking effects under the assumption of poission distributed drops.
Figures11and12indicate that the model developed in the pre-vious section is well suited for a heuristic analysis of the con-troller.A small number of iterations already suf?ces to de-scribe the effects qualitatively and quantitatively.The limita-tions of the model become obvious in?gure13.It shows the throughput of the TCP connection as a function of the
coding Figure14:Measures in which the number of cycles(0,1,2,3) and the FEC parameters were changed. parameters,with and cycle count. varied between and.Measured values are again rep-resented by triangles whereas the solid continuous curve is the result of the analytic model.The measured values are usually slightly bigger than the calculated ones.This is partly due to the assumption of poisson distributed losses.The nature of sta-tistical?uctuation is such that a random pattern of losses usu-ally exhibits some clustering of the losses-some blocks con-tain more than the average number of losses,some blocks con-tain less.So it happens that more than losses fall into one block.This reduces the amount of packets actually trans-ferred between two signi?cant losses.In?gure13we varied the amount of data(with FEC blocks as unit)being transferred between two signi?cant losses.We used multiples of the num-ber of blocks(from equations30and31)as parameter.The results are shown with dashed lines in?gure13.Most of the measured values fall into the region between the curves for and.As we are more interested in the phenomena involved in the process,we will continue to use the plain poisson model in the following calculations.But one has to be aware of the fact,that this choice is a major simpli?cation and is useless for setups of greater complexity[29].
5.2Cycle count
In the previous sections,we have introduced the cycle count for reducing control traf?c.This section discusses advantages and disadvantages of the approach.The cycle count controls the gradient of the emission rate after a drop.Beginning with an increase of one packet per RTT(which equals)the gra-dient of the emission rate is halved after each signi?cant loss until(after steps)it reaches.The next drop resets the gradient to again.
14
Figure15:In?uence of the cycle number and the FEC para-meters on the transmissions
duration.
Figure16:In?uence of the cycle number and the FEC pa-rameters on the mean bandwidth consumed by the RM?ow ().
The cycle compromises between a good adaptation to the present bandwidth situation and the need to reduce control traf-?c.The simulation results in?gure14match the expectations: The bigger the less throughput the TCP connection receives and the more throughput the RM connection receives.Already a small percentage of redundancy is able to compensate for the cycle count effects.Figure15and16again obtained by an evaluation of the formulas developped in section4with Mathe-matica,give insight into the possible bene?ts.Figure15shows the relative prolongation for cycle counts and as a func-tion of the relative redundancy(denotes the expected value for a time interval with a?xed amount of signi?cant losses).Cycle counts reduce the number of signi?cant losses per time interval.As FEC and the cycle count are expected to work hand in hand,the effect of the cycle count is maximized for small.Not surprisingly,this advantage is not for free: Figure16shows up to what percentage the cycle count reduces throughput.Again,the effect is most obvious for small. Transmissions,which are not targeted at the maximum possible speed may choose to use a cycle.The cycle count increases the fairness of the protocol with respect to the other connections operating in parallel but lowers the throughput of the connec-tion per time interval.
5.3A quantitative measure of the TCP-fairness To complete the discussion of the tiny network setup this sec-tion takes a short glance at the quantitative fairness of the RM protocol with TCP.Besides min-max fairness[30],the fairness index with being the re-
source usage of([31],[32])is frequently used[23].It allows a quantitative analysis of fairness and therefore meets our
needs.
Figure17:Fairness index as a function of the packet drop
probability.
Figure18:Fairness index as a function of the relative level of redundancy.
We de?ne the expected value of the mean bandwidth as the resource to be distributed fairly.In the absence of any cycle count or redundancy is maximized for in
15
our simple test setup,with.We obtain the same result for min-max fairness.
To evaluate the effect of redundancy and cycle count quan-titatively?gure17shows as a function of the packet loss probability of the TCP connection for different cycle counts. Depending on the cycle count,is maximized for
.If we include the results of?gure18, which shows as a function of the relative redundancy, we notice that the operating point of the control circuit is usu-ally positioned close to,or right of the maximum(because ).
5.4Simulation of a bigger network
The previous sections focussed on the behavior of the proto-col in a simple unicast environment to distill the central fea-tures.This section puts attention to bigger networks,where an-alytic modeling becomes impossible and simulation is the only means of
evaluation.
Figure19:Automatically generated,medium sized test net-work.Backbone link24-0was traced.Node109was set to be the RM source.Nodes34,41,71,77,86,87,89,90,91,95,96, 97,99,100,104,105,114,117,124,126are RM receivers. We used the topology generation tool tiers[33]to create a sim-ple medium sized test network,shown in?gure19.As the sim-ulation results focus on a single backbone link(the link which connects the‘backbone’nodes0-24),we have chosen no in-ternetwork redundancy at W AN level for the test network.Be-sides the multicast traf?c,which originates at node109and is targeted towards20destinations,we randomly created100 TCP connections connecting100randomly chosen ftp-clients to a set of20randomly chosen‘servers’.This random setup re-sulted in a total number of38?ows on link0-24.The routers use RED queue management with a queue size of just10pack-
ets.
Figure20:FEC in?uence on throughput in medium sized net-works.
Figure20shows the mean bandwidth that each of the38?ows receives for a simulation time of400seconds.Nine different bars for each?ow represent the throughput of the?ow for a dif-ferent level of redundancy used by the server.The leftmost bar shows the situation in the network without any reliable multi-cast data transfer,whereas the rightmost bar re?ects the situa-tion for a multicast data transfer with.The measured values for the RM connection are shown with wider bars in order to emphasize them.The outcome of the simple model with just two connections qualitatively holds true for this larger setup:The higher the level of redundancy,the larger the average throughput of the RM connection.The effect on the TCP connections is no longer easy to quantify.The same is true for the cycle count.
As shown in?gure21the throughput of the RM connection is nearly independent of the value of.As a consequence one can draw the conclusion that the in?uence of the redundancy is much bigger than that of the cycle count–as long as a con-stant gradient(leading to a linear rate increment)is used after each rate drop.This fact justi?es the design decision described earlier.It turns out that it is more suitable to fuel the rate con-troller by FEC than to actually tune the control process by dif-
16
Figure21:In?uence of FEC and cycle number in the medium size test network.Again link24-0was traced.
ferent parameters–either through a loss tolerant adaptation of the rate decrement(by a factor different from)as response to packet loss or a cycle count to modify the increment.
6Conclusion and future work
This paper describes a new TCP conformant congestion con-trol scheme primarily designed for reliable multicast data trans-fers.It is the?rst to integrate TCP-friendliness and TCP-competitiveness.
TCP shows up to be a hard competitor for bandwidth,as re-liable multicast transfers usually suffer from high packet loss probabilities and large delays in their control loop.The use of packet level redundancy(FEC)within the rate controllermakes it TCP-competitive.It reduces the mentioned disadvantages as shown by the simulations and analytical results in this paper. TCP-friendliness is achieved by a TCP conformant rate con-troller interpreting packet loss as a congestion signal. Besides the design of the controller,the primary focus of this paper is the analysis of the FEC introduction to the control loop.Therefore we developed a new,extended model for ?ows with a congestion control scheme simliar to TCP.As shown,already moderate levels of redundancy(up to10% with FEC-block sizes of about30packets)may signi?cantly change the bandwidth distributions among competiting?ows. This raises the question how to detect the level of redundancy that compromises best between TCP-friendliness and TCP-competitiveness.Further more,one may discuss the idea of dynamically adapting the loss?lter function of the receivers as well as the level of redundancy of the sender to the needs of the data transfer and those of the network.The necessary classi?-cation of the controller needs further analysis in complex net-work setups as well as for other reliable(multicast)protocols.References
[1]Towsley D.,Kurose J.,Pingali S.,“A Comparison of
Sender-Initiated and Receiver-Initiated Reliable Multi-cast Protocols,”IEEE Journal on Selected Areas in Com-munication,vol.15,pp.398–406,April1997.
[2]Floyd S.,Jacobson V.,McCanne S.,Liu C.G.,Zhang L.,
“A Reliable Multicast Framework for Light-weight Ses-sions and Application Level Framing,”in Proceedings of the ACM SIGCOMM Conference’95,pp.342–356,Oc-tober1995.
[3]Grossglauser M.,“Optimal Deterministic Timeouts for
Reliable Scalable Multicast,”IEEE Journal on Selected Areas in Communication,vol.15,pp.422–433,April 1997.
[4]Paul S.,Sabnani K.,Lin J.,Bhattacharyya S.,“Reliable
Multicast Protocol(RMTP),”IEEE Journal on Selected Areas in Communication,vol.15,pp.407–421,April 1997.
[5]Yavatkar R.,Grif?oen J.,Sudan M.,“A Reliable Dissem-
ination Protocol for Interactive Collaborative Applica-tions,”in Proceedings of ACM Multimedia’95,pp.333–344,1995.
[6]Whetten B.,Montgomery T.,Kaplan S.,“A High Perfor-
mance Totally Ordered Multicast Protocol.”Theory and Practice in Distributed Systems,Springer V erlag LNCS 938.
[7]Vicisano L.,Crowcroft J.,“One to Many Reliable Bulk-
Data Transfer in the MBone,”in Proceedings of the Thrid International Workshop on High Performance Protocol Architectures HIPP ARCH,Uppsala,Sweden,June1997.
[8]Jacobson V.,“Issues in Gigabit IP-Networking.”Tutorial
presented at INET91,Copenhagen,Denmark,June1991.
[9]Yajnik M.,Kurose J.,Towsley D.,“Packet Loss Correla-
tion in the MBone Multicast Network,”in Proceedings of the IEEE Global Internet Conference,London,Novem-ber1996.
[10]Handley M.,“An Examination of MBone Performance.”
USC/ISI Research Report:ISI/RR-97-450,January 1997.
[11]Sano T.,Shiroshita T.,Takahashi O.,Yamashita M.,
“Monitoring-Based Flow Control for Reliable Multicast Protocols and its evaluation,”in Proceedings of the IEEE International Performance,Computing and Communica-tion Conference(IPCCC’97),February1997.
17
[12]Montgomery T.,“A Loss Tolerant Rate Controller for
Reliable Multicast,”tech.rep.,West Virginia University, NASA-IVV-97-011,August1997.
[13]“UCB/LBNL Network Simulator ns version 2.”
https://www.doczj.com/doc/ef6016924.html,/ns,1997.
[14]Brockners F.,“Bulk multicast data transfer–to-
wards the integration of FEC and ARQ using a lightweight feedback control tree,”tech.rep.,Uni-versity of Cologne,Center for Parallel Computing, TR97-279,July1997.available via http://www.zpr.uni-koeln.de/people/frank/doc/summer.ps.gz.
[15]Floyd S.,Fall K.,“Promoting the Use of End-to-End
Congestion Control in the Internet.”Submitted to IEEE/ACM Transactions on Networking,February 1998.
[16]Jacobson V.,“Congestion Avoidance and Control,”Com-
puter Communication Review,vol.18,pp.314–329,Au-gust1988.
[17]Mahdavi J.,Floyd S.,“TCP-Friendly Unicast Rate-Based
Flow Control.”Technical note sent to the end2end-interest mailing list,January1997.
[18]Rejaie R.,Handley M.,Estrin D.,“RAP:An End-to-end
Rate-based Congestion Control Mechanism for Realtime Streams in the Internet,”in submitted to ICNP98,1998.
[19]Mills D.L.,“Network Time Protocol(V ersion3).”IETF
RFC(Request For Comments)1305,31992.
[20]Mathis M.,Mahdavi J.,Floyd S.,Romanov A.,“TCP Se-
lective Acknowledgment Options.”IETF RFC(Request For Comments)2018,October1996.
[21]Floyd S.,Jacobson V.,“Traf?c phase effects in packet-
switched gateways,”Computer CommunicationsReview, vol.21,pp.26–42,Apr.1991.
[22]Speakman T.,Farinacci D.,Lin S.,Tweedly A.,“PGM
Reliable Transport Protocol Speci?cation.”IETF Internet-Draft draft-speakman-pgm-spec-01.txt,January 1998.
[23]Floyd S.,“Connections with Multiple Congested Gate-
ways in Packet-Switched Networks,Part1:One-way Traf?c,”Computer Communications Review,vol.21, Oct.1991.
[24]Mathis M.,Semke J.,Mahdavi J.,Ott T.,“The Macro-
scopic Behavior of the TCP Congestion Avoidance Algo-rithm,”Computer Communication Review,vol.27,July 1997.[25]Wolfram S.,The Mathematica Book.Cambridge Univer-
sity Press,1996.
[26]Blahut R.E.,Theory and practice of error control codes.
Addison-Wesly Publishing Company Inc.,1983. [27]Rizzo L.,“Effective Erasure Codes for Reliable Com-
puter Communication Protocols,”in Computer Commu-nications Review,April1997.
[28]Rizzo L.,“On the feasibility of software FEC,”Tech.
Rep.LR-970131,DEIT,1997.
[29]Paxson V.,Floyd S.,“Wide-Area Traf?c:The Failure of
Poisson Modeling,”ACM Computer Communication Re-view,vol.24,Oct.1994.SIGCOMM’94Symposium.
[30]Bertsekas D.,Gallager R.,Data Networks.Prentice-Hall
International,Inc.,1992.
[31]Jain R.,Chiu D.,Hawe W.,“A Quantitative Measure
of Fairness and Discrimination for Ressource Allocation in Shared Computer System,”tech.rep.,DEC DEC-TR-301,September1984.
[32]Jain R.,“Fairness:How to Measure Quantiatively?.”
A TM Forum Document94-0881,September1994.
[33]Donar B.D.,“A Better Model for Gernerating Test Net-
works,”in Proceedings of IEEE Global Telecommunica-tions Conference GLOBECOM96,London,November 1996.
18