[e2e] Is a control theoretic approach sound?

Fri Aug 1 08:53:26 PDT 2003

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
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> > >
> >
>
>