[e2e] Is a control theoretic approach sound?

[Steven Low]

This is indeed one item in the list of
open problems in the slides that David
Wei posted, here it is again:
http://netlab.caltech.edu/pub/papers/FASTietf0307.ppt

A few comments:
Fairness can indeed be an issue.  Error
in baseRTT estimation, however, does not
seem to upset stability.  Its effect is
to distort the underlying utility function
that FAST (or Vegas) is implicitly optimizing;
see:
http://netlab.caltech.edu/FAST/papers/vegas.pdf
Shivkumar Kalyanaraman has a clever proposal to
deal with this problem which makes use of
higher prioirty queue in routers.

Finally, even though the fairness problem
can in principle be severe, in our limited
experience with FAST, baseRTT estimation
has not been a major issue, consistent with
Larry Peterson's experience with Vegas.

Steven



lz6 at njit.edu wrote:

> I have one question about FAST TCP. In FAST TCP, the BaseRTT measurement is 
> needed. As pointed out by C. Boutremans and J. Y. Le Boudec in their year 2000 
> paper, later starting vegas flows can have more bandwidth share than those 
> existing vegas flows due to the over-estimation of BaseRTT from later starting 
> vegas flows. I just have the feeling that FAST-TCP might have the similar 
> unfairness problem.
> 
> Thanks 
> 
> Li
> 
> Quoting Steven Low <slow at caltech.edu>:
> 
> 
>>Hi Christian
>>
>>Thanks for your insightful analysis.
>>Tom Kelly's STCP indeed has TimeInterval = O(1),
>>though the constant is inversely proportional
>>to the flow's RTT in your notation (i.e., for
>>STCP: cwnd * loss_probability = constant, and hence
>>throughput * loss_probability = constant/RTT).
>>
>>To your last question, as pointed out by
>>Martin, Nillson and Rhee's paper in ToN,
>>delay can be a poor or untimely predictor
>>of packet loss.  This does *not* mean that
>>it is futile to use delay as a measure of
>>congestion, but rather, that using a
>>delay-based algorithm to predict loss
>>in the hope of helping a loss-based algortihm
>>adjust its window is the wrong approach
>>to address problems at large windows.
>>Instead, a different approach
>>that fully exploits delay as a congestion
>>measure, augmented with loss information,
>>is needed.
>>
>>Roughly, delay as a congestion measure
>>has two advantages.  First, each measurement
>>of loss (whether a packet is lost or not)
>>provides 1 bit of information about
>>congestion for the filtering of noise in
>>loss probability, whereas each measurement
>>of RTT provides multibit information, and
>>hence queueing delay can probably be more
>>accurately estimated than loss probability,
>>especially in networks with large
>>bandwidth-delay product.
>>
>>Second, delay has the right scaling with
>>respect to network capacity, which helps
>>stabilize congestion control as network
>>scales up in capacity.  This scaling
>>property is also, in a sense, what
>>underlies Matt Mathis's idea of large
>>MTU's.
>>
>>Delay-based congestion control has been
>>proposed since the 80s by Raj Jain and
>>many others.  We believe its advantage
>>over loss-based approach is small at
>>low speed, but decisive at high speed.
>>
>>This is not to say that there are no
>>challenges in implementing delay-based
>>approach - there are many.  One of them
>>is that the bottleneck (e.g., at a
>>switch) may happen to have very
>>small buffer (say, <10ms).  In this
>>case, it may be hard to estimate
>>queueing delay accurately and stabilize
>>the control based solely on delay;
>>losses may be unavoidable
>>and therefore a good loss recovery
>>mechanism is essential at large window;
>>etc.  The fun continues.
>>
>>Steven
>>
>>
>>Christian Huitema wrote:
>>
>>
>>>>This is a very interesting example:)  Let me follow this example:
>>>>
>>>>1) if the cart is very small and light, and if every mouse pulls
>>>>
>>very
>>
>>>hard
>>>
>>>
>>>>and brakes very hard to chase the target speed, then the cart goes
>>>>
>>as
>>
>>>what
>>>
>>>
>>>>you described.
>>>>2) if the cart is very heavy, and every mouse pulls slightly, then
>>>>
>>it
>>
>>>>takes
>>>>a long time for the cart to gain the target speed, and the system
>>>>
>>may
>>
>>>>oscillate around the target speed slightly.
>>>>3) If the mice are a little bit cleverer: they consider the speed of
>>>>
>>>>
>>>the
>>>
>>>
>>>>cart. If the speed is far from the target speed, they pull very hard
>>>>
>>>>
>>>or
>>>
>>>
>>>>brake very hard; if the speed of the cart is close to the target
>>>>
>>>>
>>>speed,
>>>
>>>
>>>>they
>>>>pull slightly or brake slightly, or even stop pulling. Then there is
>>>>
>>a
>>
>>>>hope
>>>>to make the system stays around the target speed? :) Actually, even
>>>>
>>50
>>
>>>>elephants come to pull the cart, they have to follow the same rule:
>>>>
>>>>
>>>pull
>>>
>>>
>>>>or brake slightly when the speed is close to the target.
>>>>
>>>>
>>>There is another dimension that we ought to consider, which is the
>>>frequency of corrections. The traditional AIMD congestion control has
>>>
>>a
>>
>>>nasty side effect: the frequency of correction decreases when the
>>>average transmission speed increases. This is linked to the
>>>
>>relation:
>>
>>>	Throughput = O(1/SQRT(LossRate))
>>>Which can also be written
>>>	1/LossRate = O(Throughput^2)
>>>The average number of packets between losses is inversely
>>>
>>proportional
>>
>>>to the loss rate:
>>>	PacketInterval = O(1/LossRate)
>>>The time interval between losses is inversely proportional to the
>>>throughput:
>>>	TimeInterval = PacketInterval*PacketSize/Throughput
>>>We can express that as a function of the throughput:
>>>	TimeInterval = O((1/LossRate)*(1/Throughput))
>>>	TimeInterval = O((Throughput^2)*(1/Throughput))
>>>	TimeInterval = O(Throughput)
>>>In short, the faster you go, the less often you correct the
>>>
>>situation.
>>
>>>>From a control theory point of view, that could only be sustainable
>>>
>>if
>>
>>>high speed networks where somehow much more stable than low speed
>>>networks, for example if the rate of arrival and departure of new
>>>connections somehow diminished when the connection speed increases.
>>>There is no evidence that this is the case.
>>>
>>>So, if we pursue that particular avenue of control theory, we have
>>>
>>two
>>
>>>possible solutions. On possibility is to change the way TCP reacts
>>>
>>to
>>
>>>packet losses, so that for high speed connections we end up with: 
>>>	Throughput = O(1/LossRate) 
>>>	TimeInterval = O(1)
>>>Or we can try to obtain another source of control information than
>>>packet losses, so we can apply more frequent connections. Vegas and
>>>
>>FAST
>>
>>>seem to explore this later avenue, by using the packet transmission
>>>delays as a source of information about the congestion. On one hand,
>>>that is seductive, since we could get some limited amount of
>>>
>>information
>>
>>>in every packet. On the other hand, if we believe a paper in the
>>>
>>last
>>
>>>Transaction on Networking, there is only a weak correlation between
>>>delays and congestion, and I wonder how the designers of FAST deal
>>>
>>with
>>
>>>that.
>>>
>>>-- Christian Huitema
>>>
>>>
>>>
>>>
>>
>>-- 
>>_____________________________________________
>>Steven Low                assoc prof, cs & ee
>>netlab.caltech.edu        tel: (626) 395-6767
>>slow at caltech.edu          fax: (626) 568-3603
>>
>>
>>
>>
> 
> 


-- 
_____________________________________________
Steven Low                assoc prof, cs & ee
netlab.caltech.edu        tel: (626) 395-6767
slow at caltech.edu          fax: (626) 568-3603