[e2e] Is a control theoretic approach sound?

[John T. Wen]

Saverio:

I'm quite sure what you mean.  As you said, the queue dynamics is given by

queue dot = (input rate - output rate - loss rate)_(positive projection
based on queue length)

which means that if the queue length > 0, or, queue length=0, input
rate-output rate-loss rate >0, queue dot = input rate - output rate - loss
rate, if the queue length=0 and input rate-output rate-loss rate <=0, queue
dot =0.

Under the latter condition, the behavior is clearly nonlinear.

The saturation I'm referring to is the when output rate > capacity
(bandwidth).  To ensure that the constraint output rate <= capacity is
observed, nonlinear feedback control (e.g., penalty function as in Kelly
primal, feedback of something proportional to the queue length with queue
dynamics given by the nonlinear equation above as in RED) has been used.

John

----- Original Message -----
From: "Saverio Mascolo" <mascolo at deemail.poliba.it>
To: "John T. Wen" <wen at cat.rpi.edu>; "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: Monday, August 04, 2003 10:37 AM
Subject: Re: [e2e] Is a control theoretic approach sound?


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