[e2e] Is a control theoretic approach sound?

[Christian Huitema]

There are two different points: whether routing should adapt to the
congestion state of the network, and whether congestion control scheme
should be evaluated as to how they react to a routing change, or more
generally to a change in topology. 

The result of the Arpanet experience was indeed that adapting routes to
congestion state is tricky. Pushing packets from a short congested path
to a longer less congested path means that each of the individual
packets will consume more network resource, and thus will contribute
more to network congestion. Also, moving traffic around in reaction to
congestion notifications creates a feedback loop between routing and
congestion, which has a significant potential for creating oscillations.
There is however a limited amount of load balancing going on today, e.g.
OSPF or ISIS load-balancing between equal length paths.

But, on the other hand, the topology can change "under your feet", and
it actually does from time to time. You mention that, on a routing
change, the TCP window will quickly go down to 1. That is a bit
cavalier. Will it actually go down? How long does it take to adapt? What
is the effect of the transients? What if the transition actually results
in higher capacity? The halving of the window on a congestion
notification in VJ's algorithm was precisely designed to quickly react
to such transitions. Some proposed schemes don't have this feature. How
do they compare?

> -----Original Message-----
> From: Shivkumar Kalyanaraman [mailto:shivkuma at ecse.rpi.edu]
> Sent: Friday, August 01, 2003 8:53 AM
> To: Christian Huitema
> Cc: John T. Wen; Saverio Mascolo; end2end-interest at postel.org; John
Wen;
> Murat Arcak
> Subject: RE: [e2e] Is a control theoretic approach sound?
> 
> 
> I have never seen any congestion control simulation in the last 10
years
> which also considers effects of routing as well. After the original
> ARPAnet experience of congestion-sensitive route changes, we have
always
> de-coupled the design/analysis of routing from congestion control.
Routing
> operates at time-scales much larger than CC.
> 
> In any case, if there is a route change, TCP sessions will most likely
> reset their windows to 1, or rapidly detect new congestion and cut
their
> windows down.
> 
> -Shiv
> ===
> Shivkumar Kalyanaraman
> Associate Professor, Dept of ECSE, Rensselaer Polytechnic Institute
(RPI)
> 110, 8th Street, Room JEC 6003, Troy NY 12180-3590
> Ph: 518 276 8979   Fax: 518 276 4403
> WWW: http://www.ecse.rpi.edu/Homepages/shivkuma
> 
> A goal is a dream with a deadline -C. Knight
> 
> 
> On Fri, 1 Aug 2003, Christian Huitema wrote:
> 
> > There is a big problem with a lot of the control approaches: they
ignore
> > the dynamic nature of the network. (The average NS simulation
certainly
> > does.) At any given time, some link somewhere is going to be lost, a
BGP
> > update will reroute a fraction of the traffic on another path, a new
> > network will join the Internet, etc.
> >
> > > -----Original Message-----
> > > From: end2end-interest-admin at postel.org [mailto:end2end-interest-
> > > admin at postel.org] On Behalf Of John T. Wen
> > > Sent: Friday, August 01, 2003 5:37 AM
> > > To: Saverio Mascolo; Shivkumar Kalyanaraman
> > > Cc: end2end-interest at postel.org; John Wen; Murat Arcak
> > > Subject: Re: [e2e] Is a control theoretic approach sound?
> > >
> > > The link capacity constraint is a nonlinear function.  The queue
> > dynamics
> > > at
> > > zero queue length is also nonlinear.   I don't think you can come
up
> > with
> > > a
> > > linear controller to address these issues.   Furthermore, fairness
is
> > > addressed through optimization, and unless the optimization index
is
> > > quadratic, the resulting controller would also be nonlinear.
> > > John
> > >
> > > ----- Original Message -----
> > > From: "Saverio Mascolo" <mascolo at poliba.it>
> > > To: "Shivkumar Kalyanaraman" <shivkuma at ecse.rpi.edu>
> > > Cc: <end2end-interest at postel.org>; "John Wen" <wen at ecse.rpi.edu>;
> > "Murat
> > > Arcak" <arcak at ecse.rpi.edu>
> > > Sent: Friday, August 01, 2003 6:17 AM
> > > Subject: Re: [e2e] Is a control theoretic approach sound?
> > >
> > >
> > > > Shiv,
> > > >
> > > > we all agree with VJ that a network is to a very good
approximation
> > a
> > > linear
> > > > system. Linear system means that it can be modeled by linear
> > > differential
> > > > equations (and the superposition principle holds).
> > > > The only way to get a non linear system from a linear one is to
use
> > a
> > > > nonlinear controller.
> > > > So the question is: why should we use a nonlinear controller?
> > > >
> > > > Saverio
> > > >
> > > > ----- Original Message -----
> > > > From: "Shivkumar Kalyanaraman" <shivkuma at ecse.rpi.edu>
> > > > To: "Saverio Mascolo" <mascolo at poliba.it>
> > > > Cc: <end2end-interest at postel.org>; "John Wen"
<wen at ecse.rpi.edu>;
> > "Murat
> > > > Arcak" <arcak at ecse.rpi.edu>
> > > > Sent: Thursday, July 31, 2003 2:53 PM
> > > > Subject: Re: [e2e] Is a control theoretic approach sound?
> > > >
> > > >
> > > > > Saverio,
> > > > >
> > > > > we seem to be hair-splitting the word "non-linear"... which
means
> > > > > different things to different people.
> > > > >
> > > > > The point is not to model TCP -- but to understand the dynamic
> > > properties
> > > > > of a larger class of de-centralized control systems.
> > > > >
> > > > > you are a controls person, but just for the sake of the
broader
> > > audience,
> > > > > here is a clarification of terms being used more commonly
> > nowadays...:
> > > > >
> > > > > TCP has already been modeled in kelly/low's "non-linear" but
> > "static"
> > > > > opimization framework. Non-linear here refers to the shape of
the
> > > > > objective function (sum of concave utility functions) and the
> > > inequality
> > > > contraints
> > > > > on the problem. The value of this framework (arguably a
> > > > > "control-theoretic viewpoint") has been for a cleaner
"flow-level"
> > > > > "steady-state" understanding of TCP behavior that generalizes
to a
> > > > > broader class of schemes. This is clearly one of the modeling
> > > victories
> > > in
> > > > > the last 5-6 years.
> > > > >
> > > > > Practically, a lot of interesting AQM work as resulted from
this
> > > > > viewpoint (eg: REM from Low, and AVQ from srikant et
> > > > > al). We can use this framework also to design edge-based
methods
> > to
> > > handle
> > > > > non-cooperative/misbehaving flows.
> > > > >
> > > > > Beyond "static" optimizations which describe steady state or
> > converged
> > > > > flow-level throughputs and fairness, we are interested in
> > "dynamics":
> > > > > stability, robustness and performance characteristics. This
could
> > be
> > > > > thought of as "dynamic" optimization, an area deeply studied
in
> > > control
> > > > > theory, but considered hard in a non-linear and decentralized
> > context
> > > like
> > > > > in the case of internet congestion control.
> > > > >
> > > > > Here there is control-theoretic talk of "local-stability",
> > > > > "global-stability" "time-delay robustness" etc. The analysis
> > > techniques
> > > > > can be done in a linearized framework (with a limited and
somewhat
> > > ad-hoc
> > > > > toolkit) or a non-linear framework (that admits a broader and
> > > systematic
> > > > > set of tools).
> > > > >
> > > > > In my prior note, I meant non-linear in this sense of toolkits
> > that
> > > > > aid in the analysis of dynamics at the flow-level.
Understanding
> > and
> > > > > modeling dynamic decentralized control in elegant frameworks
is
> > the
> > > > > next control-theoretic frontier (to step up from static
> > optimization
> > > > > frameworks) and the Wen/Arcak framework is an important step
in
> > that
> > > > > direction.
> > > > >
> > > > > So, i think it makes sense to study these frameworks to take
the
> > > > > congestion control robustness and dynamics discussion above
the
> > level
> > > of
> > > > > handwaving "packet-level" dynamics to rigorous flow-level
models.
> > The
> > > > > contributions of control-theoretic folks to networks in this
area
> > is
> > > > > invaluable.
> > > > >
> > > > > best
> > > > > -Shiv
> > > > >
> > > > > On Thu, 31 Jul 2003, Saverio Mascolo wrote:
> > > > >
> > > > > > Hi,
> > > > > >
> > > > > > why do you think that TCP is a nonlinear system?
> > > > > >
> > > > > > By quoting V. Jacobson cornerstone paper :
> > > > > >
> > > > > > "Network is, to a a very good approximation, a linear
system.
> > That
> > > is,
> > > > it is
> > > > > > composed of elements that behave like linear
> > operator-integrators,
> > > > delays,
> > > > > > gain stages, etc"
> > > > > > - Van Jacobson, "Congestion Avoidance and Control," in
> > Proceedings
> > > of
> > > > ACM
> > > > > > Sigcomm'88.
> > > > > >
> > > > > > I think that modeling the TCP as a nonlinear system not only
> > > introduces
> > > > not
> > > > > > useful complexity but it is  wrong!
> > > > > >
> > > > > > Saverio Mascolo
> > > > > >
> > > > > >
> > > > > >
> > > > > > ----- Original Message -----
> > > > > > From: "Shivkumar Kalyanaraman" <shivkuma at ecse.rpi.edu>
> > > > > > To: <end2end-interest at postel.org>
> > > > > > Cc: "John Wen" <wen at ecse.rpi.edu>; "Murat Arcak"
> > > <arcak at ecse.rpi.edu>
> > > > > > Sent: Thursday, July 31, 2003 2:49 AM
> > > > > > Subject: Re: [e2e] Is a control theoretic approach sound?
> > > > > >
> > > > > >
> > > > > > >
> > > > > > > The issue of considering delay robustness and several
other
> > > > > > > properties directly in a non-linear dynamic control
theoretic
> > > > framework
> > > > > > > has been proposed by my control-theory colleagues John Wen
and
> > > Murat
> > > > Arcak
> > > > > > > in their INFOCOM 2003 paper -- this framework is a
superset of
> > > Kelly
> > > > and
> > > > > > > Low static optimization frameworks and linearized
stability
> > > analyses.
> > > > > > > Since my colleagues do not read this mailing list, please
cc
> > your
> > > > > > > responses directly to them too.
> > > > > > >
> > > > > > > It is becoming clear that basic dynamics and steady state
> > behavior
> > > of
> > > > > > > congestion control schemes are best understood at the
"flow"
> > > > > > > level in optimization frameworks; and "fine-tuning" of
schemes
> > can
> > > be
> > > > done
> > > > > > > at the "packet" level (eg: estimation robustness issues,
> > > > > > > increase/decrease: AIMD etc, slow start, interaction with
> > > timeout/rtt
> > > > > > > estimation etc). This "packet-level" dynamic behavior can
be
> > > validated
> > > > by
> > > > > > > ns-2 simulations or implementation trials.
> > > > > > >
> > > > > > > This is the essence of the approach of Kelly and Low
> > frameworks
> > > and
> > > > the
> > > > > > > other generalized frameworks...
> > > > > > >
> > > > > > > -Shiv
> > > > > > > ===
> > > > > > > Shivkumar Kalyanaraman
> > > > > > > Associate Professor, Dept of ECSE, Rensselaer Polytechnic
> > > Institute
> > > > (RPI)
> > > > > > > 110, 8th Street, Room JEC 6003, Troy NY 12180-3590
> > > > > > > Ph: 518 276 8979   Fax: 518 276 4403
> > > > > > > WWW: http://www.ecse.rpi.edu/Homepages/shivkuma
> > > > > > >
> > > > > > > A goal is a dream with a deadline -C. Knight
> > > > > > >
> > > > > > >
> > > > > > > On Thu, 31 Jul 2003, Panos GEVROS wrote:
> > > > > > >
> > > > > > > >
> > > > > > > > ----- Original Message -----
> > > > > > > > From: "Yunhong Gu" <ygu1 at cs.uic.edu>
> > > > > > > > Subject: Re: [e2e] Is a control theoretic approach
sound?
> > > > > > > >
> > > > > > > > > Well, I think to decide how "aggressive" the AI will
be is
> > not
> > > > that
> > > > > > > > > *simple* a problem :) It is not the more aggressive
the
> > better
> > > > (even
> > > > > > if
> > > > > > > > > the per flow throughput is the only objective), right?
> > > > > > > >
> > > > > > > > agreed but only if you want to address the problem in
its
> > full
> > > > > > generality
> > > > > > > > ... if it is restricted to those areas of the
> > (capacity,traffic)
> > > > space
> > > > > > where
> > > > > > > > the packet loss is in [0...7-8%] range (and AIMD is
indeed
> > > relevant)
> > > > > > since
> > > > > > > > out of this range timeouts start becoming the norm) then
it
> > is
> > > > > > > > *fairly*straightforward* to decide on AIMD parameters
which
> > > provide
> > > > > > specific
> > > > > > > > outcomes (wrt individual connection perfromance -within
> > limits
> > > > > > obviously-
> > > > > > > > and wrt capacity utilisation).
> > > > > > > >
> > > > > > > > > > ..in their case they know pretty much that the links
> > they
> > > are
> > > > using
> > > > > > are
> > > > > > > > in the
> > > > > > > > > > gigabit range and there are not many others using
these
> > > links
> > > at
> > > > the
> > > > > > > > same time.
> > > > > > > > > >
> > > > > > > > >
> > > > > > > > > But what if there are loss, especially continuous loss
> > during
> > > the
> > > > bulk
> > > > > > > > > data transfer? No matter how large the cwnd is
initially,
> > it
> > > can
> > > > > > decrease
> > > > > > > > > to 1 during the transfer, then the problem arise
again.
> > > > > > > >
> > > > > > > > drastic measures (timeout, exponential backoff etc) will
> > always
> > > need
> > > > to
> > > > > > be
> > > > > > > > in place -
> > > > > > > > I 'm saying that (at least in the first attempt)  it
pays
> > being
> > > > > > optimistic
> > > > > > > > (this is the idea underlying slow start anyway..)-  and
in
> > > certain
> > > > > > > > environments indeed more optimistic than the standard
> > prescribes
> > > > since
> > > > > > there
> > > > > > > > is a-priori knowledge of the network path
characteristics
> > and
> > > even
> > > > > > traffic
> > > > > > > > conditions - which is the case when considering OCxx
links
> > > > connecting
> > > > > > > > particle physics laboratories.
> > > > > > > > this approach seems to me a lot simpler and (most
likely)
> > > equally
> > > > > > effective
> > > > > > > > compared to elaborate control schemes which try to do
better
> > > while
> > > > > > trying
> > > > > > > > hard to remain "friendly" at the same time.
> > > > > > > >
> > > > > > > > Panos
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > > >
> > > >
> > >
> >
> >
>