Global fairness of additive-increa and multiplicative-decrea with heterogeneous
round-trip times
Milan V ojnovi´c,Jean-Yves Le Boudec,and Catherine Boutremans
Institute for Computer Communications and Applications
Swiss Federal Institute of Technology at Lausanne(EPFL)
CH-1015Lausanne,Switzerland
Milan.V ojnovic,Jean-Yves.LeBoudec,Catherine.Boutremans@epfl.ch
Abstract—Consider a network with an arbitrary topology and arbitrary communication delays,in which congestion control is bad on additive-increa and multiplicative-decrea.We show that the source rates tend to be distributed in order to maximize an objective function called(“fairness”).We derive this result under the assumption of rate proportion-al negative feedback and for the regime of rare negative feedback.This applies to TCP in moderately loaded networks,and to tho TCP imple-mentations that are designed to interpret multiple packet loss within one RTT as a single congestion indication and d中国警察大学排名
o not rely on re-transmission timeout.This result provides some insight into the distribution of rates, and hence of packet loss ratios,which can be expected in a given network with a number of competing TCP or TCP-friendly sources.We validate ourfindings by analyzing a multiple-bottleneck scenario,and comparing with previous results[1],[2],and an extensive numerical simulation with realistic parameter ttings.We apply fairness to gain a more accurate understanding of the bias of TCP against long round-trip times.
Keywords—Additive-increa,Multiplicative-decrea,Fairness,Best-effort,TCP,TCP-friendly,TCP throughput-loss formula,RTT,Multiple-bottleneck,Stochastic approximation,ODE,Lyapunov.
I.I NTRODUCTION
There is a continuing interest on throughput and fairness is-sues of TCP[3]congestion avoidance.This interest is partic-ularly nourished by the proliferation of real-time“stream”ap-plications over the voice,video)for which it is required to be fairly coexist with already existing TCP applications.
In one of the pioneering works,Chiu and Jain[4]formu-lated a t of basic principles of the additive-increa and multiplicative-decrea congestion avoidance to achieve effi-ciency and fairness,by an
alyzing the simple model of a single bottleneck.
In[5]Kelly,Maulloo,and Tan showed that a large-scale network deploying some specific form of additive-increa and multiplicative-decrea congestion avoidance tends to distribute rates according to proportional fairness.This result is common-ly misinterpreted as being applicable to congestion avoidance in the Internet with TCP.
Recently,Hurley,Le Boudec,and Thiran[6]showed that in a network employing additive-increa and multiplicative-decrea,the source rates tend to be distributed in order to max-imize an objective function called.The authors call this“fairness”.This result is obtained by the limit mean ordinary di-fferential equation(ODE)method,for a network operating in the regime of rare negative feedback.The pivotal assumption of that work is the rate proportional negative feedback,which the authors claim to be more realistic than one which depends ex-clusively on the overall load[5].However,the result is restricted to the homogeneous round-trip time(RTT)ca where the rates are updated synchronously.
In this paper,we extend the modeling of[6]to the heteroge-neous RTT ca.Our result is a generalization of fairness, which we call fairness.It gives the distribution of rates in an arbitrary netwo
rk employing the additive-increa and multi-plicative-decrea method for congestion control,with the as-sumption that negative feedback is rare.We allow the round-trip times to differ from one source to another.The rates tend to maximize an objective function called,who parameters reflect the rate adaptation algorithm.To the best of our know-ledge,this is thefirst general result encompassing many of the relevant system parameters,applicable to an arbitrary network topology with multiple bottlenecks.Our results allows tofind a first order approximation of rate distributions;combined with a loss-throughput formula such as[2],[7],this gives a prediction of the loss rates.The results are bad on limit results in[8];as such they apply only assimptotically to real network scenarios. However,our extensive simulations indicate that our results ap-ply well in realistic cas.
The novelty of our approach is an application of the rece-nt weak convergence results of decentralized asynchronous sto-chastic approximation algorithms[8].Our model esntially di-ffers from[6]in that we do not assume that rate-adaptation is performed synchronously by all sources;in contrast,we u an asynchronous model where every source updates its rate bad on its own round-trip time interval.Unlike the synchronous model in[4],[5]or[6],this allows us to address the ca with different round-trip times.But even in the ca where all round-trip times are equal,this gives a
more accurate model.Indeed, with the synchronous model,rate adjustment is bad on the most recent previous rates.In reality,the feedback received by one source at the end of one round-trip time interval depends on the rates during the previous interval,shifted in time by the de-lay required for feedback to reach the sources.The synchronous model assumes implicitly that feedback reaches sources instan-taneously.We call this assumption“stolen lag”.We show with our modeling that the stolen lag assumption does not affect the distribution of average rates;by simulation,we e however that it affects the amplitude of oscillations.Note that our model ex-
牡丹的画法plicitly considers all communication delays.
We assume in this paper that the negative feedback received by sources is rare,and is proportional to the source rate.The rare negative feedback assumption is valid in a reasonably load-ed network;the proportional assumption should be true with active queue management[9](e.g.RED[10])applied to oth-erwi FIFO queues.In addition,our model assumes a single rate updating per RTT;thisfits with TCP implementations de-signed to cope with multiple packet loss within single RTT, i.e.that treat multiple packet loss within one RTT as a single congestion signal,and avoid re-transmission timeouts.Also,it is assumed that all sources are greedy and long-lived.
Our model does not incorporate the effect of the variation of RTT for one given source from one feedback interval to the oth-er.It is known that,for a network withfixed windows[11],the variation of round-trip times due to queues building up has in itlf a congestion avoidance effect,which is not captured by our modeling.Another limitation is that we assume the rates to be piecewi be adjusted only once per round-trip time.Thus,the effect of burstiness at the timescale of the round-trip time is not taken into account.In contrast,our study captures the effect of the window or rate adaptation mechanism found for example with TCP or ABR.Our results may be ud as a reference fairness measure in performance evaluations of TCP-friendly rate adjustment algorithms.
In the next subction we outline our main results.
A.Summary of the Main Results
We consider a network with multiple bottlenecks and hetero-geneous round-trip times.Then,under the condition that there is no substantial queuing delay variation,and the network is oper-ating in the regime of the rare negative feedback,the collection of rates is distributed such that maximizes the objective function
subject to the constraints,.In the for-mula,is the t of sources,the t of links,the routing matrix(is or),the capacity of link,and is the RTT forflow or source.There is oneflow per source.The rate adaptation parameters are(additive-increa element)and (multiplicative-decrea factor);they may depend on source. The above result is applied to a multiple-bottleneck network topology;we obtain a clod-form for the distribution of rates. This allows us to verify the consistency of our result with ex-isting work and with conducted simulations.Wefind that the results in[1]are an asymptotic ca of fairness for sma-ll additive-increa/multiplicative-decrea ratio relative to con-nection throughput.
We also gain a more accurate understanding of the bias of TCP against long round-trip times.We point out that it is im-portant to make the difference between a bias against long RTTs (perhaps an undesirable feature)and a bias againstflows with many hops(perhaps a desired feature).We e that the bias againstflows with many hops is in the nature of any rate adap-tation algorithm bad on additive-increa and multiplicative-decrea.In contrast,a bias against long RTTs can be
attenuated
Fig.1.An illustration of the defined delays.
with corrections such as mentioned in[1]and[12].Finally,we
also confirm throughput loss formulas,within the limitations of
our modeling.
B.Outline of the Paper
The paper is organized as follows.In Section II,the main results are derived.Following the basic model definitions,feed-
back modeling is described in more detail.Then,asymptotic
convergence results of the decentralized asynchronous stochas-
tic approximation algorithms[8]are sketched.In the rest of the
ction,objective function of the algorithm of concern is derived and analyzed.In Section III,result is applied to a
multiple-bottleneck network topology for which a clod-form
rate distribution is computed,and results are verified through
numerical simulation.In Section IV,the results are discusd
and compared to the related previous work.Implications of the result to the Internet are addresd in Section V.In Section VI,
concluding remarks are given.In Appendix A we give the main
theorem of the underlying theory[8].
II.D ERIVATION OF THE M AIN R ESULTS
A.Model Setup
The notation is developed as follows.Let t contain net-
work links.Then let and be the capacity and delay of link ,respectively.Let t compri sources(flows)that are active on the given network.The routing tting we describe by
routing matrix,such that,if flow travers link,and,otherwi.1
ladybroFurther,we define communication delays.Let denote
delay from source to link,and let be the delay from link to source.Then,t.Defining as the round-trip time of the source,clearly,,for all such that.In Fig.1,a sample network illustrates defined delays.
Let be a non-decreasing-valued quence of rate updating times of source.Then,a number of rate updates of source on the interval is. Let be a-valued stochastic process,where is a rate of source at the-th update.Then,define a continuous time interpolation on real time as,for
.
For define a-algebra of the form
. Finally,let.
We define on which can be extended to to accommodate for instance load sharing,etc.[6]
Fig.2.Feedback modeling for the HOMRTT ca.
An additive-increa and multiplicative-decrea algorithm
has the following form
(1) where and are the additive-increa element and the
multiplicative-decrea factor,respectively.The random -
quence is a negative feedback indication with values
in.We assume that the negative feedback indication
is bad on the feedback received between-th and-th rate updating.Conquently,it turns out that is measurable on -algebra.
Now let us briefly comment on the special ca addresd in
[6],where it is assumed that all round-trip times are equal,and
the rates are updated synchronously.Following the definition of in the full extent,one can e in Fig.2that is a
function of,,and,for all such that ,depending on values of.In the related work [4]-[6],it is commonly assumed that is computed bad on
,for all such that,which is indeed an unrealistic assumption.
Let us assume that allflows traversing link have equal ac-
cess delay to that link.Formally,,for all, such that.Then,it follows that depends on ,for all such that.We refer to this assumption as a HOMRTT assumption.In addition,whenever is ud where it should be we refer to this as a stolen lag.Feedback computation is illustrated in Fig.2.
B.Feedback Modeling
上海结婚First,we introduce a notion of the link cost function
,where.At a given time,the link cost is
a function of the link load
(2)
One can interpret as a probability of marking a single packet at time.We are concerned with negative feedback in-dication,,bad on feedback received within. Let us partition the interval into non-overlapping intervals such that,is constant for
,for all such that.
We define as an amount of negative feedback received by source from link within interval,which is equal to a number of marked packets of theflow by the link within interval.
Let and be conditional probabilities given and,respectively.Analogously,let and
be respective conditional expectations.
Admitting the interpretation of as a probability of mark-ing a single packet,it is easy to e that we do have a binomial conditional probability
(3) where is written in lieu of.Note that
corresponds to a number of packets of flow that are prent on link within. Clearly,the expected amount of negative feedback is
Similarly,let be an amount of negative feedback received within by source from all links such that.It follows
网球的规则and from(3)follows
(4) By definition of we have
(5)
Finally,,if source has received an indication,within ,that at least one packet has been marked,thus
(6) Let us examine(6)for the HOMRTT ca.Here we have a single partition of,hence,from(4)-(6)follows
(7)
where,for all,,and sta-nds for.In the limit ca ,limited development yields
,then replacing this in(7),and neglecting the higher order products,yield
(8)
Therefore,it is shown that,under the rare negative feedback as-sumption,(7)degenerates to the rate proportional feedback as is implicitly assumed in[6].However,note that(8)depends on and not on.
C.Asymptotic Convergence
Traditional theory of the stochastic approximation algorithms [13]-[14]is concerned with an algorithm of the general form where is defined on,,
is a random noi,and a step size.It is assumed that compo-nents,,are updated synchronously,facilitating the association of continuous interpolation to discrete pro-cess on the“natural”common iterate time. However,it follows that for an asynchronous updating one has to work in real time,or at least an appropriately scaled real time [8].In general,for decreasing,in respect to,convergence with probability one can be obtained,while for constant small ,only convergence in probability can be proven(weak convergence).The weak convergence limit is obtained for a small en
ough step size,and obrving interpolation of dis-crete time process of concern on the real time scaled by.In the rest of this ction we briefly sketch results of[8]that are applied in our work.For a complete treatment of the underlying theory the reader is referred to[8].
Let be a random quence of updating intervals of ,.Then denote the(scaled)real updating time of as
(9)
and a continuous interpolation on the iterate time, for.Further,let is a number of updates of before.Formally,
(10)
From the definitions,it turns out that,
,i.e.is inver of.
Then,let,,is a continu-ous interpolation on scaled real time,and
,.From definitions of“time”process(9) and(10)it follows,and. Furthermore,let be a non-negative ran
dom variable reprenting a scaled(multiplied by)communication delay between sources and at the-th rate updating of source. Finally,the decentralized asynchronous algorithm can be written in the form
(11) where denotes projection of the argument on, for the constrained on, and is a reflection term.
Let for all,and be non-decreasing-algebras measuring the past data(including,,and,) available on,and,respectively.Then,with and denote respective conditional probabilities,and analogously and conditional expectations.
Subquently,we have the following conditions.It is assumed that
(12) and,are uniformly integrable.We consider the martingale difference noi[8],for which we have
where are real-valued functions continuous in and, is asymptotically negligible noi,and
.There are real-valued functions that are strictly posi-tive()and are continuous uniformly in and,and non-negative random variables such that
(13) where.There are continuous real-valued functions such that for each
,2
(15) Suppo
(16)
Finally,from the Theorem[8](Appendix A)particularly fol-lows that,for the unconstrained algorithm,the weak conver-gence subquence is the limit t of ODE
Fig.3.A multiple-bottleneck network topology.
where is given by(6).
警示教育宣传片In the limit ca,as,and,we neglect scaled delays,then the probability of negative feedback is
For,for all,the mean vectorfield is
(19)
where.
In our ca the rate is updated at the end of each round-trip time interval,thus,.Then,combining this with(19) the limit mean ODE(17)becomes
有什么无什么(21) where
(22)
and by definition,where is a primi-tive of.
It is easy to e that is strictly concave and conquently has a unique maximum over any bounded region.It turns out that is Lyapunov for ODE and with an unique attractor,for which is maximized.
Along the same lines as in[6],one can neglect the cond term in(22).Then,it follows that the rates are distributed such that maximizes
(23) subject to the constraints
(24)D.1asymptotic limits
Let us write(23)in the following form
(25) Then we develop the cond term to obtain
(26) subject to(24).4Note that we skip thefirst term in(25)that is not relevant for maximization in respect to.In the opposite ca,,for all,by simple manipulation we obtain an objective function
Fraction of capacity given to class 0 sources by F A
fairness S i m u l a t i o n R e s u l t s
Fig.4.HOMRTT with the stolen lag,
s,
,
for
flows.
In the quel,we suppo
(29)
Then,(28)becomes
.
天才眼镜狗
Lemma 1(multiple-bottleneck)–fairness distribution for the multiple-bottleneck scenario with (29)is
(31)
where
for
,otherwi
for
.
Proof:Proof is simple and is same as in [6].
,
(34)
flows.
TABLE I
F RACTION OF CAPACITY GIVEN TO A CLASS
FLOWS ,FOR THE
MULTIPLE -BOTTLENECK ,WITH
FOR ALL
.
Fairness
parameters tup
,
;
,
Proportional
,
TCP-Reno
,
,
Remarks :Row 1–-like result [6]is achieved for homogeneous RTTs,and additive-increa parameters proportional to the RTTs.Row 2–Pro-portional fairness result holds for the HETRTT network and equal values of and for all sources.Row 3–Max-min fairness can be obtained by indicat
ed parameters tting.Row 4–Indicates rate distribution for TCP Reno and the HETRTT network (def.Section III-A),which complies to the other results mentioned in Section III-A.
In [6]it is referred to this ca as
,which is encompasd in
,for and .
