[e2e] Is a control theoretic approach sound?

[Cannara]

One thing to keep in mind is that current systems, whether routers, load
balancers, firewalls, security gateways, etc., have merchant processors and
largely custom firmware, which varies from one vendor's gear to another, and
even within one vendor's offerings.  This means that queueing behavior can
vary greatly from one box to another, even on the same path.  The folks who
build these devices often start with sample router/bridge code from the chip
vendors and build their own processing, hopefully to the relevant RFCs. 
However, since there's no validation of code, this is more wishful thinking
that anything else.  There are software vendors who provide a number of box
makers with protocol and router/bridge code, such as Level7.  It might be
worthwhile contacting them and surveying how queueing code varies among
products they may have licensed code to.  This would help determine what
reasonable modelling decisions can be made.

Alex

Saverio Mascolo wrote:
> 
> I would say that the queue dynamics is a linear positive systems (i.e. queue
> lengths -and rates- are always greater or equal to zero ). Thus the
> behaviour around zero length is linear!
> 
> The queue behaviour around queue capacity has a saturation, but , since the
> goal of congestion control is to obtain a very low packet loss rate, this
> implies that saturation is hit for short times. During saturation, the
> behaviour can be modeled using a loss input rate, that is , the queue
> dynamics can be modeled,  using the following  integrator:
> 
> queue=integral of (input rate-output rate-loss rate)
> 
> Saverio
> 
> ----- Original Message -----
> From: "John T. Wen" <wen at cat.rpi.edu>
> To: "Saverio Mascolo" <mascolo at poliba.it>; "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 2:37 PM
> 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