Subject: [Iccrg] Re: Iccrg Digest, Vol 4, Issue 12
From: [email-masked] (Arjuna Sathiaseelan)
Date: Tue Feb 28 09:36:00 2006

I am not sure if I am making sense here...can we take delay into
consideration when defining congestion? Say for eg a Bandwidth on
Demand return link such as a DVB-RCS system could take different
delays from 300 ms to 1300 ms - making the overall RTT varying (even
though the forward link delay is constant). So this does not
necessarily mean the network is congested, right?

> Fil Dickinson wrote:
>
>> 'Network congestion is a state where there are insufficient resources
>> in a network for a flow that result in excessive delay. This in turn
>> results in the flow failing to meet minimum effective performance.'

Regds,
Arjuna

On 2/28/06, [email-masked] <[email-masked]> wrote:
> Send Iccrg mailing list submissions to
>        [email-masked]
>
> To subscribe or unsubscribe via the World Wide Web, visit
>        http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
> or, via email, send a message with subject or body 'help' to
>        [email-masked]
>
> You can reach the person managing the list at
>        [email-masked]
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Iccrg digest..."
>
>
> Today's Topics:
>
>   1. Definition of Congestion (John Leslie)
>   2. Re: Congestion control definition and requirements of a new
>      protocol (Filipe Abrantes)
>   3. Re: Congestion control definition and requirements of a new
>      protocol (Saverio Mascolo)
>   4. RE: Definition of Congestion (Fil Dickinson)
>   5. Re: Congestion control definition and requirements of a new
>      protocol (Tim Shepard)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 27 Feb 2006 08:08:01 -0500
> From: John Leslie <[email-masked]>
> Subject: [Iccrg] Definition of Congestion
> To: Dado Colussi <[email-masked]>
> Cc: iccrg <[email-masked]>, Fil Dickinson
>        <[email-masked]>
> Message-ID: <20060227130801.GP94025@verdi>
> Content-Type: text/plain; charset=us-ascii
>
> Dado Colussi <[email-masked]> wrote:
> > Fil Dickinson wrote:
> >
> >> 'Network congestion is a state where there are insufficient resources
> >> in a network for a flow that result in excessive delay. This in turn
> >> results in the flow failing to meet minimum effective performance.'
>
>   I read Fil to be saying that "congestion" exists when information
> flow is delayed beyond the requirements for effective use of the network.
>
> > If we consider Keshav's utilities mathematically, we probably see
> > functions u: X -> Y where X is a set of resource bundles and Y is some
> > set with order property. Keshav says that a source experiences
> > congestion if u(x1) > u(x2) where x1 and x2 are user's resource bundles
> > before and after an increase in network load. I find this definition
> > quite elegant and expressive.
>
>   It indeed is true that it is technically possible that an increase
> in network load could _increase_ a user's perceived utility.
>
>   More obviously, it is true that different users will have different
> utility functions, and some will perceive degradation in the same set
> of resource bundles where others do not.
>
> > The insufficient resources you suggest are all those resource bundles
> > that don't result in maximum utility when the utility is sensitive to
> > excessive delay (or throughput, as in your second definiton).
>
>   I assume Dado is referring to:
> ]
> ] 'Network congestion is a state that occurs when a network element in
> ] a path reaches a resource limit. A network is said to be congested
> ] from the perspective of a user if that user's minimum effective
> ] throughput has decreased due to a limit being attained.'
>
> which I read to say that whenever a user's experience is degraded, the
> network is by definition "congested". (This does not strike me as a
> useful definition.)
>
> > However, utility functions differ per application and even per user
> > basis and are not limited to excessive delay only (or throughput only).
>
>   I quite agree.
>
>   (Which is why I prefer to work on things we can measure...)
>
> > Furthermore, the Internet exists for its users and it's more important
> > to adjust it for the users than for mere existence. That's why I think
> > a user-centric approach is well justified.
>
>   I come from the old school, which states that the intelligence
> should be at the edges with the center as simple as possible.
>
>   This is not necessarily at odds with Dado and/or Fil: congestion
> management has traditionally been an edge function; and anything they
> want to try at the edges is fine with me.
>
>   My approach to <iccrg> is that it appears that we may have made
> the "backbone" _too_ simple, and I'd like to work on identifying points
> of overload and seeing if we can "route around them".
>
>   (Also, the "backbone" _will_ need to protect itself against excessive
> loading, possibly by discarding types of traffic which seem to be
> failing to apply appropriate congestion management: there are questions
> worth studying in how to distinguish this.)
>
> > You're right about the problem of measurement. I think it would be
> > essential to discuss u, X and Y. If we knew them, u and X in particular,
> > we would be in a better position to decide what tradeoffs to make in
> > suggesting a framework for measurement. It's not feasible to find
> > utility functions for each application and user but I do think it would
> > be feasible to find a sufficiently expressive classification that would
> > enable us to justify the tradeoffs. I'm not suggesting it would be easy
> > though.
>
>   I do think it's clear that there's no single utility function. It
> may be possible to identify a useful set of functions -- which brings up
> the question of how to tell which function to use...
>
> --
> John Leslie <[email-masked]>
>
>
>
> ------------------------------
>
> Message: 2
> Date: Mon, 27 Feb 2006 13:24:19 +0000
> From: Filipe Abrantes <[email-masked]>
> Subject: Re: [Iccrg] Congestion control definition and requirements of
>        a new   protocol
> To: "S. Keshav" <[email-masked]>
> Cc: [email-masked]
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Hi,
>
> (see below)
>
> S. Keshav wrote:
> > Folks,
> >     Its been quiet on this list for a while. Can I take it as consensus on
> > the following:
> >
> > A. Definition of Congestion:
> >
> > Network congestion is a state of degraded performance from the perspective
> > of a particular user. A network is said to be congested from the perspective
> > of a user if that user's utility has decreased due to an increase in network
> > load.
> >
> > B. Problems with TCP congestion control:
> >
> > 1. In a high bandwidth-delay product environment, high throughputs can only
> > be achieved if the packet loss rate is unrealistically low.
> >
>
> Probably combinable with #3. The "limited range of operation" is a term
> I have already seen before and I think it applies the best.
>
> > 2. TCP has low throughput under lossy environments because it uses loss as
> > an indication of congestion.
> >
> Because most of the wireless media have automatic repeat request (ARQ)
> mechanisms, transmission errors result in doubling (or multiplying for
> some other factor) the delay of that wireless hop in question. So, using
> loss in such media is probably ok, unlike rtt measurements.
>
> > 3. Due to additive increase, it takes a long time for a flow to ramp up to
> > transient increases in available capacity which results in unnecessarily
> > long flow-completion times.
> >
> > 4. Even when the flow is capable of completing within a round-trip time,
> > slow-start makes flows last multiple round-trip times just to find their
> > fair share rate. Many flows complete before they exit slow-start phase.
> >
> > 5. TCP fills up all available buffers at the bottleneck links, which results
> > in long latency.
> Combinable with #7 isn't it?
>
> >
> > 6. TCP  shares bandwidth inversely proportional to flow RTTs
> >
> Agreed.
>
> > 7. TCP builds a standing queue at the point of congestion, which increases
> > the delay.
>
>
> I would like to add:
> 8.
> TCP's resultant throughput is unstable, which is inadequate for some
> applications (media apps).
>
>
> > -------
> >
> > If we agree on this, (and if you do not, this is the time to speak up) I
> > would like to propose that we discuss the requirements of a new congestion
> > control protocol, both theoretically and practically.
> >
> > To start off this debate, I would like to state the following top level
> > requirements.
> >
> > First, given the definition of congestion, I argue that the proposed
> > protocol should allow two things: decoupling and observability.
> >
> >     0 Decoupling means that the traffic from one user should not affect (or
> > minimally affect) other users.
> >     0 Observability means that users should be able to observe the network
> > state in some fashion, so that they can control their input so as to not
> > cause overload and a consequent decrease in utility.
> >
> > Second, in addition to these, the new mechanism should also not suffer from
> > the seven problems with TCP.
> >
> > Comments?
> >
> > thanks
> >
> > keshav
> >
> >
> >
> > _______________________________________________
> > Iccrg mailing list
> > [email-masked]
> > http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
> >
>
> --
> Filipe Lameiro Abrantes
> INESC Porto
> Campus da FEUP
> Rua Dr. Roberto Frias, 378
> 4200-465 Porto
> Portugal
>
> Phone: +351 22 209 4266
> E-mail: [email-masked]
>
>
>
> ------------------------------
>
> Message: 3
> Date: Mon, 27 Feb 2006 19:53:25 +0100
> From: Saverio Mascolo <[email-masked]>
> Subject: Re: [Iccrg] Congestion control definition and requirements of
>        a new   protocol
> To: keshav <[email-masked]>, iccrg <[email-masked]>
> Message-ID: <003301c63bcf$1c83b320$703bccc1@yourf1911fedb6>
> Content-Type: text/plain; charset="iso-8859-1"
>
> hi,
>
> you say: " 1. In a high bandwidth-delay product environment, high throughputs can only
> be achieved if the packet loss rate is unrealistically low."
>
> does anyone know what it is a realistic packet loss rate  not due to congestion in gigabit nets?
>
> Saverio
>
>
>
> On 2/24/06, S. Keshav <[email-masked]> wrote:
>  Folks,
>     Its been quiet on this list for a while. Can I take it as consensus on
>  the following:
>
>  A. Definition of Congestion:
>
>  Network congestion is a state of degraded performance from the perspective
>  of a particular user. A network is said to be congested from the perspective
>  of a user if that user's utility has decreased due to an increase in network
>  load.
>
>  B. Problems with TCP congestion control:
>
>  1. In a high bandwidth-delay product environment, high throughputs can only
>  be achieved if the packet loss rate is unrealistically low.
>
>
>
>  2. TCP has low throughput under lossy environments because it uses loss as
>  an indication of congestion.
>
>  3. Due to additive increase, it takes a long time for a flow to ramp up to
>  transient increases in available capacity which results in unnecessarily
>  long flow-completion times.
>
>  4. Even when the flow is capable of completing within a round-trip time,
>  slow-start makes flows last multiple round-trip times just to find their
>  fair share rate. Many flows complete before they exit slow-start phase.
>
>  5. TCP fills up all available buffers at the bottleneck links, which results
>  in long latency.
>
>  6. TCP  shares bandwidth inversely proportional to flow RTTs
>
>  7. TCP builds a standing queue at the point of congestion, which increases
>  the delay.
>  -------
>
>  If we agree on this, (and if you do not, this is the time to speak up) I
>  would like to propose that we discuss the requirements of a new congestion
>  control protocol, both theoretically and practically.
>
>  To start off this debate, I would like to state the following top level
>  requirements.
>
>  First, given the definition of congestion, I argue that the proposed
>  protocol should allow two things: decoupling and observability.
>
>     0 Decoupling means that the traffic from one user should not affect (or
>  minimally affect) other users.
>     0 Observability means that users should be able to observe the network
>  state in some fashion, so that they can control their input so as to not
>  cause overload and a consequent decrease in utility.
>
>  Second, in addition to these, the new mechanism should also not suffer from
>  the seven problems with TCP.
>
>  Comments?
>
>  thanks
>
>  keshav
>
>
>
>  _______________________________________________
>  Iccrg mailing list
>  [email-masked]
>  http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
>
>
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060227/eb6d8eaf/attachment-0001.html
>
> ------------------------------
>
> Message: 4
> Date: Tue, 28 Feb 2006 09:18:51 +1100
> From: Fil Dickinson <[email-masked]>
> Subject: [Iccrg] RE: Definition of Congestion
> To: John Leslie <[email-masked]>, Dado Colussi <[email-masked]>
> Cc: iccrg <[email-masked]>
> Message-ID:
>        <[email-masked]>
> Content-Type: text/plain; charset=us-ascii
>
> Hi John and Dado. I am responding to both your valued comments in this
> one mail. By the way, I found them very enlightening.
>
>
> >-----Original Message-----
> >From: John Leslie [mailto:[email-masked]]
> >Sent: Tuesday, 28 February 2006 12:08 AM
> >To: Dado Colussi
> >Cc: Fil Dickinson; iccrg
> >Subject: Definition of Congestion
> >
> >Dado Colussi <[email-masked]> wrote:
> >> Fil Dickinson wrote:
> >>
> >>> 'Network congestion is a state where there are insufficient
> resources
> >>> in a network for a flow that result in excessive delay. This in turn
>
> >>>results in the flow failing to meet minimum effective performance.'
> >
> >   I read Fil to be saying that "congestion" exists when information
> flow is delayed beyond the requirements for effective use of the
> network.
>
> Here I was saying that congestion exists when the available resources
> for a flow across a network drop below the minimum required for
> effective use. These resources may be bandwidth, queues, packet buffers,
> processor etc. They may not be reliability, transmission delay, problems
> associated with path diversity, routing, reachabilty etc.
>
> >
> >> If we consider Keshav's utilities mathematically, we probably see
> >> functions u: X -> Y where X is a set of resource bundles and Y is
> some
> >> set with order property. Keshav says that a source experiences
> >> congestion if u(x1) > u(x2) where x1 and x2 are user's resource
> >> bundles before and after an increase in network load. I find this
> >> definition quite elegant and expressive.
> >
>
> This expalination is simple and elegant. I agree with this explaination
> with one exception and that is load. The network load may stay the same
> however the nature of the different flows may change, thus expiring the
> available resources for say a certain packet size and rate. The result
> will be congestion for those flows that are now resource constrained. In
> turn the users will see this as degraded performance.
>
> >   It indeed is true that it is technically possible that an increase
> in network load could _increase_ a user's perceived utility.
> >
> >   More obviously, it is true that different users will have different
> utility functions, and some will perceive degradation in the same set of
> resource bundles where others do not.
>
> I agree.
>
> >
> >> The insufficient resources you suggest are all those resource bundles
>
> >> that don't result in maximum utility when the utility is sensitive to
>
> >> excessive delay (or throughput, as in your second definiton).
>
> Yes, that is a fair understanding in light of Keshev's utilities.
>
> >
> >   I assume Dado is referring to:
> >]
> >] 'Network congestion is a state that occurs when a network element in
> ] a path reaches a resource limit. A network is said to be congested ]
> from the perspective of a user if that user's minimum effective ]
> throughput has decreased due to a limit being attained.'
> >
> >which I read to say that whenever a user's experience is degraded, the
> network is by definition "congested". (This does not strike me as a
> useful definition.)
>
> Sorry to be confusing but that was not my intended meaning. I was trying
> to say that congestion is one of a number of states. There are others
> such as loss and transmission delay that may degrede a users
> performance. I was not saying that any degradation experienced by a user
> is due to congestion.
>
> >
> >> However, utility functions differ per application and even per user
> >> basis and are not limited to excessive delay only (or throughput
> only).
> >
> >   I quite agree.
>
> I also agree. The utilities are limited by a number of factors including
> other states such as reliability/loss and delay variance.
>
> >
> >   (Which is why I prefer to work on things we can measure...)
> >
> >> Furthermore, the Internet exists for its users and it's more
> important
> >> to adjust it for the users than for mere existence. That's why I
> think
> >> a user-centric approach is well justified.
>
> I agree that the Internet is for it's users and think a user centric
> approach is honourable. I see it as the more complex approach however
> and that it will require very tight interpretation of the group "users".
> For example I would not want to contribute to engineering the Internet
> for "users" whose applications are written in such a way as to make poor
> use of the Internet or in fact abuse of the Internet.
>
> >
> >   I come from the old school, which states that the intelligence
> should be at the edges with the center as simple as possible.
>
> I come from the same school [and may have borrowed the same books from
> the library;-)].
>
> >
> >   This is not necessarily at odds with Dado and/or Fil: congestion
> management has traditionally been an edge function; and anything they
> want to try at the edges is fine with me.
> >
> >   My approach to <iccrg> is that it appears that we may have made the
> "backbone" _too_ simple, and I'd like to work on identifying points of
> overload and seeing if we can "route around them".
> >
> >   (Also, the "backbone" _will_ need to protect itself against
> excessive loading, possibly by discarding types of traffic which seem to
> be failing to apply appropriate congestion management: there are
> questions worth studying in how to distinguish this.)
> >
> >> You're right about the problem of measurement. I think it would be
> >> essential to discuss u, X and Y. If we knew them, u and X in
> >> particular, we would be in a better position to decide what tradeoffs
>
> >> to make in suggesting a framework for measurement. It's not feasible
> >> to find utility functions for each application and user but I do
> think
> >> it would be feasible to find a sufficiently expressive classification
>
> >> that would enable us to justify the tradeoffs. I'm not suggesting it
> >> would be easy though.
> >
> >   I do think it's clear that there's no single utility function. It
> may be possible to identify a useful set of functions -- which brings up
> the question of how to tell which function to use...
> >
>
> I agree with you both on your comments above.
>
> >--
> >John Leslie <[email-masked]>
>
>
>
> ------------------------------
>
> Message: 5
> Date: Tue, 28 Feb 2006 00:36:33 -0500
> From: Tim Shepard <[email-masked]>
> Subject: Re: [Iccrg] Congestion control definition and requirements of
>        a new   protocol
> To: John Leslie <[email-masked]>
> Cc: iccrg <[email-masked]>
> Message-ID: <[email-masked]>
>
>
> > > A. Definition of Congestion:
> > >
> > > Network congestion is a state of degraded performance from the
> > > perspective of a particular user.
> >
> >    This really won't do.
> >
> >    We need to define something we can measure.
> >
> >    And unless we measure something appreciably smaller than what a
> > user will notice, there's no hope of controlling congestion very well.
>
> The way I think about it, it is the standing queues.  And those are
> measurable.
>
> I think if we get rid of the standing queues (by controlling
> transmissions into the net, not by dropping packets until the
> standing queue goes away), we will have accomplished the first half
> of what we want to accomplish towards a new and improved congestion
> control scheme.
>
> (One scenario I like to keep in mind is a single TCP transmitting data
>  over a path, with no other significant traffic in the net.  This
>  single TCP will build a standing queue in front of the bottleneck,
>  increasing delay (for itself, which probably does not matter, and for
>  the other "insignificant" traffic, which might matter).)
>
>
> The other half of what we want to accomplish would involve fairness,
> the ability to do traffic engineering, et cetera.
>
>
> > > 5. TCP fills up all available buffers at the bottleneck links, which
> > >    results in long latency.?
> >
> >    Better to say that TCP must inflate latency before generating the
> > packet loss which will signal congestion. (It's not necessarily true
> > that "all available buffers" are filled first.)
>
> [....]
>
> > > 7. TCP builds a standing queue at the point of congestion, which
> > >    increases the delay.
> >
> >    This should be combined with #5. I'm not sure what words we should
> > add to make this point clear.
>
> Yes, with #7, #5 is redundant.  So perhaps we can delete #5 and just
> have #7?
>
>                        -Tim Shepard
>                         [email-masked]
>
>
>
> ------------------------------
>
> _______________________________________________
> Iccrg mailing list
> [email-masked]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
>
>
> End of Iccrg Digest, Vol 4, Issue 12
> ************************************
>

From: [email-masked] (Mark Handley)
Date: Tue Feb 28 09:21:04 2006
Subject: [Iccrg] Congestion control definition and requirements of a new  protocol
In-Reply-To: <20060225015138.GN94025@verdi>
References: <[email-masked]> <20060225015138.GN94025@verdi>
Message-ID: <[email-masked]>

On 2/25/06, John Leslie <[email-masked]> wrote:
> S. Keshav <[email-masked]> wrote:
> >
> > A. Definition of Congestion:
> >
> > Network congestion is a state of degraded performance from the
> > perspective of a particular user.
>
>    This really won't do.
>
>    We need to define something we can measure.

And this of course is at the core of the problem.  We do need to
define something we can measure to be able to objectively compare two
solutions.  However, unfortunately the ideal solution is one that
maximizes the utility, which is a subjective measure.

Thus I agree it's useful to define something we can measure, but it's
important to always keep in mind that *all* such metrics are only
rough proxies for what we would actually want to measure but can't.

 - Mark

From: [email-masked] (Tim Shepard)
Date: Tue Feb 28 05:41:20 2006
Subject: [Iccrg] Congestion control definition and requirements of a new  protocol
In-Reply-To: Your message of Fri, 24 Feb 2006 20:51:38 -0500. <20060225015138.GN94025@verdi>
Message-ID: <[email-masked]>

> > A. Definition of Congestion:
> > 
> > Network congestion is a state of degraded performance from the
> > perspective of a particular user.
>
>    This really won't do.
> 
>    We need to define something we can measure.
> 
>    And unless we measure something appreciably smaller than what a
> user will notice, there's no hope of controlling congestion very well.

The way I think about it, it is the standing queues.  And those are
measurable.  

I think if we get rid of the standing queues (by controlling
transmissions into the net, not by dropping packets until the
standing queue goes away), we will have accomplished the first half
of what we want to accomplish towards a new and improved congestion
control scheme.

(One scenario I like to keep in mind is a single TCP transmitting data
 over a path, with no other significant traffic in the net.  This
 single TCP will build a standing queue in front of the bottleneck,
 increasing delay (for itself, which probably does not matter, and for
 the other "insignificant" traffic, which might matter).)

The other half of what we want to accomplish would involve fairness,
the ability to do traffic engineering, et cetera.

> > 5. TCP fills up all available buffers at the bottleneck links, which
> >    results in long latency.?
> 
>    Better to say that TCP must inflate latency before generating the
> packet loss which will signal congestion. (It's not necessarily true
> that "all available buffers" are filled first.)

[....]

> > 7. TCP builds a standing queue at the point of congestion, which
> >    increases the delay. 
> 
>    This should be combined with #5. I'm not sure what words we should
> add to make this point clear.

Yes, with #7, #5 is redundant.  So perhaps we can delete #5 and just
have #7?

			-Tim Shepard
			 [email-masked]

From: [email-masked] (Saverio Mascolo)
Date: Mon Feb 27 19:58:56 2006
Subject: [Iccrg] Congestion control definition and requirements of a new  protocol
Message-ID: <003301c63bcf$1c83b320$703bccc1@yourf1911fedb6>

hi,

you say: " 1. In a high bandwidth-delay product environment, high throughputs can only
be achieved if the packet loss rate is unrealistically low."

does anyone know what it is a realistic packet loss rate  not due to congestion in gigabit nets?

Saverio

On 2/24/06, S. Keshav <[email-masked]> wrote: 
  Folks,
     Its been quiet on this list for a while. Can I take it as consensus on
  the following:

  A. Definition of Congestion:

  Network congestion is a state of degraded performance from the perspective
  of a particular user. A network is said to be congested from the perspective
  of a user if that user's utility has decreased due to an increase in network
  load.

  B. Problems with TCP congestion control:

  1. In a high bandwidth-delay product environment, high throughputs can only
  be achieved if the packet loss rate is unrealistically low.

  2. TCP has low throughput under lossy environments because it uses loss as
  an indication of congestion.

  3. Due to additive increase, it takes a long time for a flow to ramp up to
  transient increases in available capacity which results in unnecessarily
  long flow-completion times.

  4. Even when the flow is capable of completing within a round-trip time,
  slow-start makes flows last multiple round-trip times just to find their
  fair share rate. Many flows complete before they exit slow-start phase. 

  5. TCP fills up all available buffers at the bottleneck links, which results
  in long latency.

  6. TCP  shares bandwidth inversely proportional to flow RTTs

  7. TCP builds a standing queue at the point of congestion, which increases
  the delay.
  -------

  If we agree on this, (and if you do not, this is the time to speak up) I
  would like to propose that we discuss the requirements of a new congestion
  control protocol, both theoretically and practically.

  To start off this debate, I would like to state the following top level
  requirements.

  First, given the definition of congestion, I argue that the proposed
  protocol should allow two things: decoupling and observability.

     0 Decoupling means that the traffic from one user should not affect (or
  minimally affect) other users.
     0 Observability means that users should be able to observe the network
  state in some fashion, so that they can control their input so as to not
  cause overload and a consequent decrease in utility.

  Second, in addition to these, the new mechanism should also not suffer from
  the seven problems with TCP.

  Comments?

  thanks

  keshav

  _______________________________________________
  Iccrg mailing list
  [email-masked]
  http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060227/eb6d8eaf/attachment.html
>From [email-masked]  Mon Feb 27 22:19:44 2006
From: [email-masked] (Fil Dickinson)
Date: Mon Feb 27 22:43:12 2006
Subject: [Iccrg] RE: Definition of Congestion
Message-ID: <[email-masked]>

Hi John and Dado. I am responding to both your valued comments in this
one mail. By the way, I found them very enlightening.

>-----Original Message-----
>From: John Leslie [mailto:[email-masked]] 
>Sent: Tuesday, 28 February 2006 12:08 AM
>To: Dado Colussi
>Cc: Fil Dickinson; iccrg
>Subject: Definition of Congestion
>
>Dado Colussi <[email-masked]> wrote:
>> Fil Dickinson wrote:
>> 
>>> 'Network congestion is a state where there are insufficient
resources 
>>> in a network for a flow that result in excessive delay. This in turn

>>>results in the flow failing to meet minimum effective performance.'
>
>   I read Fil to be saying that "congestion" exists when information
flow is delayed beyond the requirements for effective use of the
network.

Here I was saying that congestion exists when the available resources
for a flow across a network drop below the minimum required for
effective use. These resources may be bandwidth, queues, packet buffers,
processor etc. They may not be reliability, transmission delay, problems
associated with path diversity, routing, reachabilty etc.

>
>> If we consider Keshav's utilities mathematically, we probably see 
>> functions u: X -> Y where X is a set of resource bundles and Y is
some 
>> set with order property. Keshav says that a source experiences 
>> congestion if u(x1) > u(x2) where x1 and x2 are user's resource 
>> bundles before and after an increase in network load. I find this 
>> definition quite elegant and expressive.
>

This expalination is simple and elegant. I agree with this explaination
with one exception and that is load. The network load may stay the same
however the nature of the different flows may change, thus expiring the
available resources for say a certain packet size and rate. The result
will be congestion for those flows that are now resource constrained. In
turn the users will see this as degraded performance.

>   It indeed is true that it is technically possible that an increase
in network load could _increase_ a user's perceived utility.
>
>   More obviously, it is true that different users will have different
utility functions, and some will perceive degradation in the same set of
resource bundles where others do not.

I agree.

>
>> The insufficient resources you suggest are all those resource bundles

>> that don't result in maximum utility when the utility is sensitive to

>> excessive delay (or throughput, as in your second definiton).

Yes, that is a fair understanding in light of Keshev's utilities.

>
>   I assume Dado is referring to:
>]
>] 'Network congestion is a state that occurs when a network element in
] a path reaches a resource limit. A network is said to be congested ]
from the perspective of a user if that user's minimum effective ]
throughput has decreased due to a limit being attained.'
>
>which I read to say that whenever a user's experience is degraded, the
network is by definition "congested". (This does not strike me as a
useful definition.)

Sorry to be confusing but that was not my intended meaning. I was trying
to say that congestion is one of a number of states. There are others
such as loss and transmission delay that may degrede a users
performance. I was not saying that any degradation experienced by a user
is due to congestion.

>
>> However, utility functions differ per application and even per user 
>> basis and are not limited to excessive delay only (or throughput
only).
>
>   I quite agree.

I also agree. The utilities are limited by a number of factors including
other states such as reliability/loss and delay variance.

>
>   (Which is why I prefer to work on things we can measure...)
>
>> Furthermore, the Internet exists for its users and it's more
important 
>> to adjust it for the users than for mere existence. That's why I
think 
>> a user-centric approach is well justified.

I agree that the Internet is for it's users and think a user centric
approach is honourable. I see it as the more complex approach however
and that it will require very tight interpretation of the group "users".
For example I would not want to contribute to engineering the Internet
for "users" whose applications are written in such a way as to make poor
use of the Internet or in fact abuse of the Internet.

>
>   I come from the old school, which states that the intelligence
should be at the edges with the center as simple as possible.

I come from the same school [and may have borrowed the same books from
the library;-)].

>
>   This is not necessarily at odds with Dado and/or Fil: congestion
management has traditionally been an edge function; and anything they
want to try at the edges is fine with me.
>
>   My approach to <iccrg> is that it appears that we may have made the
"backbone" _too_ simple, and I'd like to work on identifying points of
overload and seeing if we can "route around them".
>
>   (Also, the "backbone" _will_ need to protect itself against
excessive loading, possibly by discarding types of traffic which seem to
be failing to apply appropriate congestion management: there are
questions worth studying in how to distinguish this.)
>
>> You're right about the problem of measurement. I think it would be 
>> essential to discuss u, X and Y. If we knew them, u and X in 
>> particular, we would be in a better position to decide what tradeoffs

>> to make in suggesting a framework for measurement. It's not feasible 
>> to find utility functions for each application and user but I do
think 
>> it would be feasible to find a sufficiently expressive classification

>> that would enable us to justify the tradeoffs. I'm not suggesting it 
>> would be easy though.
>
>   I do think it's clear that there's no single utility function. It
may be possible to identify a useful set of functions -- which brings up
the question of how to tell which function to use...
>

I agree with you both on your comments above.

>--
>John Leslie <[email-masked]>

From: [email-masked] (Filipe Abrantes)
Date: Mon Feb 27 14:17:36 2006
Subject: [Iccrg] Congestion control definition and requirements of a new  protocol
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <[email-masked]>

Hi,

(see below)

S. Keshav wrote:
> Folks, 
>     Its been quiet on this list for a while. Can I take it as consensus on
> the following:
> 
> A. Definition of Congestion:
> 
> Network congestion is a state of degraded performance from the perspective
> of a particular user. A network is said to be congested from the perspective
> of a user if that user's utility has decreased due to an increase in network
> load. 
> 
> B. Problems with TCP congestion control:
> 
> 1. In a high bandwidth-delay product environment, high throughputs can only
> be achieved if the packet loss rate is unrealistically low.
> 

Probably combinable with #3. The "limited range of operation" is a term 
I have already seen before and I think it applies the best.

> 2. TCP has low throughput under lossy environments because it uses loss as
> an indication of congestion.
> 
Because most of the wireless media have automatic repeat request (ARQ) 
mechanisms, transmission errors result in doubling (or multiplying for 
some other factor) the delay of that wireless hop in question. So, using 
loss in such media is probably ok, unlike rtt measurements.

> 3. Due to additive increase, it takes a long time for a flow to ramp up to
> transient increases in available capacity which results in unnecessarily
> long flow-completion times.
> 
> 4. Even when the flow is capable of completing within a round-trip time,
> slow-start makes flows last multiple round-trip times just to find their
> fair share rate. Many flows complete before they exit slow-start phase.   
> 
> 5. TCP fills up all available buffers at the bottleneck links, which results
> in long latency. 
Combinable with #7 isn't it?

> 
> 6. TCP  shares bandwidth inversely proportional to flow RTTs
> 
Agreed.

> 7. TCP builds a standing queue at the point of congestion, which increases
> the delay. 

I would like to add:
8.
TCP's resultant throughput is unstable, which is inadequate for some 
applications (media apps).

> -------
> 
> If we agree on this, (and if you do not, this is the time to speak up) I
> would like to propose that we discuss the requirements of a new congestion
> control protocol, both theoretically and practically.
> 
> To start off this debate, I would like to state the following top level
> requirements. 
> 
> First, given the definition of congestion, I argue that the proposed
> protocol should allow two things: decoupling and observability.
> 
>     0 Decoupling means that the traffic from one user should not affect (or
> minimally affect) other users.
>     0 Observability means that users should be able to observe the network
> state in some fashion, so that they can control their input so as to not
> cause overload and a consequent decrease in utility.
> 
> Second, in addition to these, the new mechanism should also not suffer from
> the seven problems with TCP.
> 
> Comments?
> 
> thanks
> 
> keshav
> 
> 
> 
> _______________________________________________
> Iccrg mailing list
> [email-masked]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
> 

-- 
Filipe Lameiro Abrantes
INESC Porto
Campus da FEUP
Rua Dr. Roberto Frias, 378
4200-465 Porto
Portugal

Phone: +351 22 209 4266
E-mail: [email-masked]

From: [email-masked] (John Leslie)
Date: Mon Feb 27 13:13:36 2006
Subject: [Iccrg] Definition of Congestion
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <20060227130801.GP94025@verdi>

Dado Colussi <[email-masked]> wrote:
> Fil Dickinson wrote:
> 
>> 'Network congestion is a state where there are insufficient resources
>> in a network for a flow that result in excessive delay. This in turn
>> results in the flow failing to meet minimum effective performance.'

   I read Fil to be saying that "congestion" exists when information
flow is delayed beyond the requirements for effective use of the network.

> If we consider Keshav's utilities mathematically, we probably see 
> functions u: X -> Y where X is a set of resource bundles and Y is some 
> set with order property. Keshav says that a source experiences 
> congestion if u(x1) > u(x2) where x1 and x2 are user's resource bundles 
> before and after an increase in network load. I find this definition 
> quite elegant and expressive.

   It indeed is true that it is technically possible that an increase
in network load could _increase_ a user's perceived utility.

   More obviously, it is true that different users will have different
utility functions, and some will perceive degradation in the same set
of resource bundles where others do not.

> The insufficient resources you suggest are all those resource bundles 
> that don't result in maximum utility when the utility is sensitive to 
> excessive delay (or throughput, as in your second definiton).

   I assume Dado is referring to:
] 
] 'Network congestion is a state that occurs when a network element in
] a path reaches a resource limit. A network is said to be congested
] from the perspective of a user if that user's minimum effective
] throughput has decreased due to a limit being attained.'

which I read to say that whenever a user's experience is degraded, the
network is by definition "congested". (This does not strike me as a
useful definition.)

> However, utility functions differ per application and even per user
> basis and are not limited to excessive delay only (or throughput only).

   I quite agree.

   (Which is why I prefer to work on things we can measure...)

> Furthermore, the Internet exists for its users and it's more important
> to adjust it for the users than for mere existence. That's why I think
> a user-centric approach is well justified.

   I come from the old school, which states that the intelligence
should be at the edges with the center as simple as possible.

   This is not necessarily at odds with Dado and/or Fil: congestion
management has traditionally been an edge function; and anything they
want to try at the edges is fine with me.

   My approach to <iccrg> is that it appears that we may have made
the "backbone" _too_ simple, and I'd like to work on identifying points
of overload and seeing if we can "route around them".

   (Also, the "backbone" _will_ need to protect itself against excessive
loading, possibly by discarding types of traffic which seem to be
failing to apply appropriate congestion management: there are questions
worth studying in how to distinguish this.)

> You're right about the problem of measurement. I think it would be 
> essential to discuss u, X and Y. If we knew them, u and X in particular, 
> we would be in a better position to decide what tradeoffs to make in 
> suggesting a framework for measurement. It's not feasible to find 
> utility functions for each application and user but I do think it would 
> be feasible to find a sufficiently expressive classification that would 
> enable us to justify the tradeoffs. I'm not suggesting it would be easy 
> though.

   I do think it's clear that there's no single utility function. It
may be possible to identify a useful set of functions -- which brings up
the question of how to tell which function to use...

--
John Leslie <[email-masked]>

From: [email-masked] (Dado Colussi)
Date: Mon Feb 27 10:57:04 2006
Subject: [Iccrg] RE: Iccrg Digest, Vol 4, Issue 10
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <[email-masked]>

Fil Dickinson wrote:
> 'Network congestion is a state where there are insufficient resources in a network for a flow that result in excessive delay. This in turn results in the flow failing to meet minimum effective performance.'

If we consider Keshav's utilities mathematically, we probably see 
functions u: X -> Y where X is a set of resource bundles and Y is some 
set with order property. Keshav says that a source experiences 
congestion if u(x1) > u(x2) where x1 and x2 are user's resource bundles 
before and after an increase in network load. I find this definition 
quite elegant and expressive.

The insufficient resources you suggest are all those resource bundles 
that don't result in maximum utility when the utility is sensitive to 
excessive delay (or throughput, as in your second definiton). However, 
utility functions differ per application and even per user basis and are 
not limited to excessive delay only (or throughput only). Furthermore, 
the Internet exists for its users and it's more important to adjust it 
for the users than for mere existence. That's why I think a user-centric 
approach is well justified.

You're right about the problem of measurement. I think it would be 
essential to discuss u, X and Y. If we knew them, u and X in particular, 
we would be in a better position to decide what tradeoffs to make in 
suggesting a framework for measurement. It's not feasible to find 
utility functions for each application and user but I do think it would 
be feasible to find a sufficiently expressive classification that would 
enable us to justify the tradeoffs. I'm not suggesting it would be easy 
though.

Dado

From: [email-masked] (louise.burness)
Date: Mon Feb 27 09:21:04 2006
Subject: [Iccrg] Congestion control definition and requirements of a new  protocol
Message-ID: <[email-masked]>

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of John Leslie
> Sent: 25 February 2006 01:52
> To: S. Keshav
> Cc: iccrg
> Subject: Re: [Iccrg] Congestion control definition and 
> requirements of a new protocol
> 
> 
> S. Keshav <[email-masked]> wrote:
> > 
> > A. Definition of Congestion:
> > 
> > Network congestion is a state of degraded performance from the 
> > perspective of a particular user.
> 
>    This really won't do.
> 
>    We need to define something we can measure.
> 
>    And unless we measure something appreciably smaller than 
> what a user will notice, there's no hope of controlling 
> congestion very well.

Bob Briscoe did a definition of congestion of a resource and a path in
A.1 of
http://www.sigcomm.org/sigcomm2005/paper-BriJac.pdf

> 
> > B. Problems with TCP congestion control:
> > 
> > 1. In a high bandwidth-delay product environment, high throughputs
> >    can only be achieved if the packet loss rate is unrealistically 
> > low.
> 
>    Better to place this after #3, or even combine it with #3.
> 
> > 2. TCP has low throughput under lossy environments because it uses
> >    loss as an indication of congestion.
> 
>    The "problem" is that TCP uses packet loss as its only 
> measure of congestion. That TCP fails to fill a pipe in the 
> presence of any other packet loss is a result.
> 
> > 3. Due to additive increase, it takes a long time for a 
> flow to ramp up
> >    to transient increases in available capacity which results in
> >    unnecessarily long flow-completion times.
> 
>    This is correct, but could probably be better worded. The 
> problem is that additive increase prevents filling the pipe 
> when another flow stops. "Flow-completion times" may not give 
> the right connotations.

And we need to think about what we really want - AIMD was chosen (from
memory) because of the way it converged quite quickly to a stable and
fair state without any complex network management (at least compared to
other options), so its only a "problem" in certain circumstances.

> 
> > 4. Even when the flow is capable of completing within a 
> round-trip time,
> >    slow-start makes flows last multiple round-trip times 
> just to find
> >    their fair share rate. Many flows complete before they 
> exit slow-start
> >    phase.? ?
> 
>    I'm not sure any flow _is_ capable of completing within a 
> round-trip time. (There's a separate problem with saying 
> "fair-share rate", since the "stable" rate which flows 
> eventually reach isn't especially stable and is heavily 
> influenced by round-trip time, which many folks wouldn't see 
> as "fair".
> 
>    That many flows complete before finishing slow-start is a 
> real problem, and is well-stated.
> 
> > 5. TCP fills up all available buffers at the bottleneck links, which
> >    results in long latency.?
> 
>    Better to say that TCP must inflate latency before 
> generating the packet loss which will signal congestion. 
> (It's not necessarily true that "all available buffers" are 
> filled first.)
> 
> > 6. TCP  shares bandwidth inversely proportional to flow RTTs
> 
>    Better, I think, to say that TCP punishes long round-trip 
> times, causing users to perceive congestion more often than necessary.

I understood the origional point better

> 
> > 7. TCP builds a standing queue at the point of congestion, which
> >    increases the delay.
> 
>    This should be combined with #5. I'm not sure what words 
> we should add to make this point clear.

TCP deliberatly compromises delay in order to maximise overall
throughput. There are big buffers in the network to allow TCP to do
this. It deliberatly pushes the network to the edge of congestion as
this is the way to achieve maximum throughput (probable proviso on long
lived flows etc). TCP was designed to support long lived, delay
insenstive flows operating on links that had low delay-bandwidth
products and low non-congestive losses in a way that minimised
requirements on networks.

> 
> > -------
> > 
> > If we agree on this, (and if you do not, this is the time 
> to speak up) 
> > I would like to propose that we discuss the requirements of a new 
> > congestion control protocol, both theoretically and practically.
> > 
> > To start off this debate, I would like to state the following top 
> > level requirements.
> > 
> > First, given the definition of congestion, I argue that the 
> proposed 
> > protocol should allow two things: decoupling and observability.
> > 
> > - Decoupling means that the traffic from one user should not affect
> >   (or minimally affect) other users.
> 
>    This is clearly impossible. Perhaps you mean that when one 
> flow ramps up, other flows should not ramp down any more than 
> necessary to accomodate a proportional share of the increase.
> 
That's what TCP tries to do after all!

Decoupling is not impossible,you can do it with circuit switching

> > - Observability means that users should be able to observe 
> the network
> >   state in some fashion, so that they can control their 
> input so as to
> >   not cause overload and a consequent decrease in utility.

Again, you are restating what TCP already tries to do
> 
>    I'm not at all sure I understand. Do you mean that minimal 
> congestion should be reported to applications so that they 
> can choose alternative communication methods and/or paths 
> which are not congested?
> 
> > Second, in addition to these, the new mechanism should also 
> not suffer 
> > from the seven problems with TCP.
> 
>    I think, if we list problems, this should come first. But 
> if we state it this way (including by reference instead of 
> listing again the features to avoid), we need to word this 
> list more carefully. I'd prefer to restate -- I think it will 
> read more smoothly.
> 
> --
> John Leslie <[email-masked]>
> 
> _______________________________________________
> Iccrg mailing list
> [email-masked] http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
> 

From: [email-masked] (Fil Dickinson)
Date: Sun Feb 26 22:04:48 2006
Subject: [Iccrg] RE: Iccrg Digest, Vol 4, Issue 10
Message-ID: <[email-masked]>

Hi,
I do not agree with the definition of congestion, but am glad that people are trying to tackle the issue. Although defing it is a challenge, coming up with a metric for measurement may be even harder.

I consider network congestion to be based on resource limits. That is to say
'Network congestion is a state where there are insufficient resources in a network for a flow that result in excessive delay. This in turn results in the flow failing to meet minimum effective performance.'

Or in the syntax similar to that used

'Network congestion is a state that occurs when a network element in a path reaches a resource limit. A network is said to be congested from the perspective of a user if that user's minimum effective throughput has decreased due to a limit being attained.'

The problem of measurement is much harder and interestingly, I don't specifically put this down to the problems of elastic versus inelastic as some have. To me it is difficult to measure because it is very much perception based and we are trying to describe it according to its impact upon a user. Were it elastic like file transfer the results of congestion are less obvious but perhaps more frustrating. The reason for this is people perceive an acceptable level of performance based on experience and expectation (and to some degree their own level of patience). If a file transfer experiences consistant congestion then the performance will be less than optimal, but the throughput consistant. Therefore they may perceive it slow or fast by comparison to another experience (or based upon their perceived urgency of completion). However, were it inelastic like VoIP, then the impacts of congestion to the end user would be obvious and we may be able to borrow from the work done on MOS in order to come up with a measure here for all flow types.

Fil Dickinson

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Saturday, 25 February 2006 10:56 PM
To: [email-masked]
Subject: Iccrg Digest, Vol 4, Issue 10

Send Iccrg mailing list submissions to
	[email-masked]

To subscribe or unsubscribe via the World Wide Web, visit
	http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
or, via email, send a message with subject or body 'help' to
	[email-masked]

You can reach the person managing the list at
	[email-masked]

When replying, please edit your Subject line so it is more specific than "Re: Contents of Iccrg digest..."

Today's Topics:

   1. Congestion control definition and requirements of a new
      protocol (S. Keshav)
   2. Re: Congestion control definition and requirements of a new
      protocol (John Leslie)

----------------------------------------------------------------------

Message: 1
Date: Fri, 24 Feb 2006 17:34:58 -0500
From: "S. Keshav" <[email-masked]>
Subject: [Iccrg] Congestion control definition and requirements of a
	new	protocol
To: iccrg <[email-masked]>
Message-ID: <[email-masked]>
Content-Type: text/plain; charset="ISO-8859-1"

Folks, 
    Its been quiet on this list for a while. Can I take it as consensus on the following:

A. Definition of Congestion:

Network congestion is a state of degraded performance from the perspective of a particular user. A network is said to be congested from the perspective of a user if that user's utility has decreased due to an increase in network load. 

B. Problems with TCP congestion control:

1. In a high bandwidth-delay product environment, high throughputs can only be achieved if the packet loss rate is unrealistically low.

2. TCP has low throughput under lossy environments because it uses loss as an indication of congestion.

3. Due to additive increase, it takes a long time for a flow to ramp up to transient increases in available capacity which results in unnecessarily long flow-completion times.

4. Even when the flow is capable of completing within a round-trip time, slow-start makes flows last multiple round-trip times just to find their fair share rate. Many flows complete before they exit slow-start phase.? ?

5. TCP fills up all available buffers at the bottleneck links, which results in long latency.?

6. TCP  shares bandwidth inversely proportional to flow RTTs

7. TCP builds a standing queue at the point of congestion, which increases the delay. 
-------

If we agree on this, (and if you do not, this is the time to speak up) I would like to propose that we discuss the requirements of a new congestion control protocol, both theoretically and practically.

To start off this debate, I would like to state the following top level requirements. 

First, given the definition of congestion, I argue that the proposed protocol should allow two things: decoupling and observability.

    0 Decoupling means that the traffic from one user should not affect (or minimally affect) other users.
    0 Observability means that users should be able to observe the network state in some fashion, so that they can control their input so as to not cause overload and a consequent decrease in utility.

Second, in addition to these, the new mechanism should also not suffer from the seven problems with TCP.

Comments?

thanks

keshav

------------------------------

Message: 2
Date: Fri, 24 Feb 2006 20:51:38 -0500
From: John Leslie <[email-masked]>
Subject: Re: [Iccrg] Congestion control definition and requirements of
	a new 	protocol
To: "S. Keshav" <[email-masked]>
Cc: iccrg <[email-masked]>
Message-ID: <20060225015138.GN94025@verdi>
Content-Type: text/plain; charset=us-ascii

S. Keshav <[email-masked]> wrote:
> 
> A. Definition of Congestion:
> 
> Network congestion is a state of degraded performance from the 
> perspective of a particular user.

   This really won't do.

   We need to define something we can measure.

   And unless we measure something appreciably smaller than what a user will notice, there's no hope of controlling congestion very well.

> B. Problems with TCP congestion control:
> 
> 1. In a high bandwidth-delay product environment, high throughputs
>    can only be achieved if the packet loss rate is unrealistically low.

   Better to place this after #3, or even combine it with #3.

> 2. TCP has low throughput under lossy environments because it uses
>    loss as an indication of congestion.

   The "problem" is that TCP uses packet loss as its only measure of congestion. That TCP fails to fill a pipe in the presence of any other packet loss is a result.

> 3. Due to additive increase, it takes a long time for a flow to ramp up
>    to transient increases in available capacity which results in
>    unnecessarily long flow-completion times.

   This is correct, but could probably be better worded. The problem is that additive increase prevents filling the pipe when another flow stops.
"Flow-completion times" may not give the right connotations.

> 4. Even when the flow is capable of completing within a round-trip time,
>    slow-start makes flows last multiple round-trip times just to find
>    their fair share rate. Many flows complete before they exit slow-start
>    phase.? ?

   I'm not sure any flow _is_ capable of completing within a round-trip time. (There's a separate problem with saying "fair-share rate", since the "stable" rate which flows eventually reach isn't especially stable and is heavily influenced by round-trip time, which many folks wouldn't see as "fair".

   That many flows complete before finishing slow-start is a real problem, and is well-stated.

> 5. TCP fills up all available buffers at the bottleneck links, which
>    results in long latency.?

   Better to say that TCP must inflate latency before generating the packet loss which will signal congestion. (It's not necessarily true that "all available buffers" are filled first.)

> 6. TCP  shares bandwidth inversely proportional to flow RTTs

   Better, I think, to say that TCP punishes long round-trip times, causing users to perceive congestion more often than necessary.

> 7. TCP builds a standing queue at the point of congestion, which
>    increases the delay. 

   This should be combined with #5. I'm not sure what words we should add to make this point clear.

> -------
> 
> If we agree on this, (and if you do not, this is the time to speak up) 
> I would like to propose that we discuss the requirements of a new 
> congestion control protocol, both theoretically and practically.
> 
> To start off this debate, I would like to state the following top 
> level requirements.
> 
> First, given the definition of congestion, I argue that the proposed 
> protocol should allow two things: decoupling and observability.
> 
> - Decoupling means that the traffic from one user should not affect
>   (or minimally affect) other users.

   This is clearly impossible. Perhaps you mean that when one flow ramps up, other flows should not ramp down any more than necessary to accomodate a proportional share of the increase.

> - Observability means that users should be able to observe the network
>   state in some fashion, so that they can control their input so as to
>   not cause overload and a consequent decrease in utility.

   I'm not at all sure I understand. Do you mean that minimal congestion should be reported to applications so that they can choose alternative communication methods and/or paths which are not congested?

> Second, in addition to these, the new mechanism should also not suffer 
> from the seven problems with TCP.

   I think, if we list problems, this should come first. But if we state it this way (including by reference instead of listing again the features to avoid), we need to word this list more carefully.
I'd prefer to restate -- I think it will read more smoothly.

--
John Leslie <[email-masked]>

------------------------------

_______________________________________________
Iccrg mailing list
[email-masked]
http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg

End of Iccrg Digest, Vol 4, Issue 10
************************************

From: [email-masked] (John Leslie)
Date: Sat Feb 25 01:57:20 2006
Subject: [Iccrg] Congestion control definition and requirements of a new  protocol
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <20060225015138.GN94025@verdi>

S. Keshav <[email-masked]> wrote:
> 
> A. Definition of Congestion:
> 
> Network congestion is a state of degraded performance from the
> perspective of a particular user.

   This really won't do.

   We need to define something we can measure.

   And unless we measure something appreciably smaller than what a
user will notice, there's no hope of controlling congestion very well.

> B. Problems with TCP congestion control:
> 
> 1. In a high bandwidth-delay product environment, high throughputs
>    can only be achieved if the packet loss rate is unrealistically low.

   Better to place this after #3, or even combine it with #3.

> 2. TCP has low throughput under lossy environments because it uses
>    loss as an indication of congestion.

   The "problem" is that TCP uses packet loss as its only measure of
congestion. That TCP fails to fill a pipe in the presence of any other
packet loss is a result.

> 3. Due to additive increase, it takes a long time for a flow to ramp up
>    to transient increases in available capacity which results in
>    unnecessarily long flow-completion times.

   This is correct, but could probably be better worded. The problem is
that additive increase prevents filling the pipe when another flow stops.
"Flow-completion times" may not give the right connotations.

> 4. Even when the flow is capable of completing within a round-trip time,
>    slow-start makes flows last multiple round-trip times just to find
>    their fair share rate. Many flows complete before they exit slow-start
>    phase.? ?

   I'm not sure any flow _is_ capable of completing within a round-trip
time. (There's a separate problem with saying "fair-share rate", since
the "stable" rate which flows eventually reach isn't especially stable
and is heavily influenced by round-trip time, which many folks wouldn't
see as "fair".

   That many flows complete before finishing slow-start is a real
problem, and is well-stated.

> 5. TCP fills up all available buffers at the bottleneck links, which
>    results in long latency.?

   Better to say that TCP must inflate latency before generating the
packet loss which will signal congestion. (It's not necessarily true
that "all available buffers" are filled first.)

> 6. TCP  shares bandwidth inversely proportional to flow RTTs

   Better, I think, to say that TCP punishes long round-trip times,
causing users to perceive congestion more often than necessary.

> 7. TCP builds a standing queue at the point of congestion, which
>    increases the delay. 

   This should be combined with #5. I'm not sure what words we should
add to make this point clear.

> -------
> 
> If we agree on this, (and if you do not, this is the time to speak up)
> I would like to propose that we discuss the requirements of a new
> congestion control protocol, both theoretically and practically.
> 
> To start off this debate, I would like to state the following top level
> requirements. 
> 
> First, given the definition of congestion, I argue that the proposed
> protocol should allow two things: decoupling and observability.
> 
> - Decoupling means that the traffic from one user should not affect
>   (or minimally affect) other users.

   This is clearly impossible. Perhaps you mean that when one flow
ramps up, other flows should not ramp down any more than necessary
to accomodate a proportional share of the increase.

> - Observability means that users should be able to observe the network
>   state in some fashion, so that they can control their input so as to
>   not cause overload and a consequent decrease in utility.

   I'm not at all sure I understand. Do you mean that minimal congestion
should be reported to applications so that they can choose alternative
communication methods and/or paths which are not congested?

> Second, in addition to these, the new mechanism should also not suffer
> from the seven problems with TCP.

   I think, if we list problems, this should come first. But if we
state it this way (including by reference instead of listing again
the features to avoid), we need to word this list more carefully.
I'd prefer to restate -- I think it will read more smoothly.

--
John Leslie <[email-masked]>

From: [email-masked] (Lars Eggert)
Date: Tue Feb  7 23:30:08 2006
Subject: [Iccrg] What's wrong with TCP Congestion control
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

Hi,

On Feb 7, 2006, at 16:57, Michael Welzl wrote:
> According to the Padhye equation, the throughput of a TCP sender
> is directly related to the packet size - so, a sender with large
> packets would get more throughput than a sender with small packets.

based on Sally's work with the small-packets variant of DCCP TFCR  
(and maybe other work?), it should probably matter whether the  
bottleneck router manages its queue based on packets or bytes. (The  
effects for DCCP TFRC are different, but the queue management  
mechanism is likely to have an impact.)

Lars
-- 
Lars Eggert                                     NEC Network Laboratories

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3686 bytes
Desc: not available
Url : http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060208/9c96aade/smime.bin
>From [email-masked]  Fri Feb 10 21:32:48 2006
From: [email-masked] (Aaron Falk)
Date: Fri Feb 10 21:37:04 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <[email-masked]>

On Feb 4, 2006, at 9:05 AM, S. Keshav wrote:

>     A. What is the commonly agreed definition for congestion. (I  
> will post
> my suggestion later today). If we do not agree on a definition,  
> then indices
> are meaningless.

I would argue that 'congestion' is a characteristic of the network  
(not an individual flow) where the offered load exceeds the network's  
capacity at some point.   Flows are affected by congestion initially  
by delay, marks, and then packet loss as the congestion level  
increases.  (Different types of flows will have different tolerance  
levels for these effects.)

--aaron

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060210/34c64106/PGP.bin
>From [email-masked]  Fri Feb 24 22:34:40 2006
From: [email-masked] (S. Keshav)
Date: Fri Feb 24 22:41:04 2006
Subject: [Iccrg] Congestion control definition and requirements of a new
	protocol
Message-ID: <[email-masked]>

Folks, 
    Its been quiet on this list for a while. Can I take it as consensus on
the following:

A. Definition of Congestion:

Network congestion is a state of degraded performance from the perspective
of a particular user. A network is said to be congested from the perspective
of a user if that user's utility has decreased due to an increase in network
load. 

B. Problems with TCP congestion control:

1. In a high bandwidth-delay product environment, high throughputs can only
be achieved if the packet loss rate is unrealistically low.

2. TCP has low throughput under lossy environments because it uses loss as
an indication of congestion.

3. Due to additive increase, it takes a long time for a flow to ramp up to
transient increases in available capacity which results in unnecessarily
long flow-completion times.

4. Even when the flow is capable of completing within a round-trip time,
slow-start makes flows last multiple round-trip times just to find their
fair share rate. Many flows complete before they exit slow-start phase.? ?

5. TCP fills up all available buffers at the bottleneck links, which results
in long latency.?

6. TCP  shares bandwidth inversely proportional to flow RTTs

7. TCP builds a standing queue at the point of congestion, which increases
the delay. 
-------

If we agree on this, (and if you do not, this is the time to speak up) I
would like to propose that we discuss the requirements of a new congestion
control protocol, both theoretically and practically.

To start off this debate, I would like to state the following top level
requirements. 

First, given the definition of congestion, I argue that the proposed
protocol should allow two things: decoupling and observability.

    0 Decoupling means that the traffic from one user should not affect (or
minimally affect) other users.
    0 Observability means that users should be able to observe the network
state in some fashion, so that they can control their input so as to not
cause overload and a consequent decrease in utility.

Second, in addition to these, the new mechanism should also not suffer from
the seven problems with TCP.

Comments?

thanks

keshav

From: [email-masked] (Michael Welzl)
Date: Tue Feb  7 16:06:24 2006
Subject: [Iccrg] What's wrong with TCP Congestion control
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <[email-masked]>

> 1. Unsustainable large equilibrium window sizes under high bandwidth-delay
> product environments; requires an unrealistically low loss probability.
> (Leads to limited dynamic range)
>  2. Low throughput under lossy environments because of using loss as an
> indication of congestion.
>  3. Slow additive increase: Takes a long time for flow to catch up with
> spare capacity and results in unnecessary long flow-completion times.
>  4. Inefficient Slow-start: Even when the flow is capable of completing
> within a round-trip time, slow-start makes flows last multiple round-trip
> times just to find their fair share rate. Often most flows complete
> before they exit slow-start phase.  
>  5. Large queueing delay: TCP fills up any amount of buffering available at
> the bottleneck links. Results in long latency. 
>  6. Unfair bandwidth sharing: shares bandwidth inversely proportional to
> flow RTTs
> 7. TCP builds a standing queue at the point of congestion, which increases
> the delay. 
> 
> Did I miss anything?

According to the Padhye equation, the throughput of a TCP sender
is directly related to the packet size - so, a sender with large
packets would get more throughput than a sender with small packets.
>From a fairness point of view, that's at least odd.

I can't think of any measurement studies which indicate whether
this is a problem or not right now, but there surely are some
(perhaps somewhere in the papers that were written on TFRC
with variable packet sizes, don't know).

In my previous email, I stated that looking at relatively
"safe" proposals like HighSpeed TCP might give us good hints
about things that are wrong with TCP. Based on this viewpoint,
I would say that the fact that TCP increases its rate at a
fixed value, irrespective of the current network conditions,
is one of the problems with this protocol.

Cheers,
Michael

From: [email-masked] (Radek Krzywania)
Date: Tue Feb  7 15:30:08 2006
Subject: [Iccrg] What's wrong with TCP Congestion control
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <op.s4lzy3gkzxx9ui@edelweiss>

On Tue, 07 Feb 2006 16:08:38 +0100, Phelan, Tom <[email-masked]>  
wrote:

> Hi All,
>
> I'd like to point out that the large buffer requirement is not an
> intrinsic property of window-based congestion control.  It's the result
> of the requirement for reliability, coupled with the large transmit
> window.  If you don't need reliability (as with DCCP and its AIMD
> congestion control), the need for sender buffering is greatly reduced.

Hi,
I fully agree that it is the side effect of large window. But in sense of  
TCP, where reliability is a requirement, we need to allocate large memory  
buffers. So paraphrasing my first point:

"Maybe it is good to say explicitly, that large windows requires large
memory buffers on sender side for reliability purposes."

I am talking about memory, because if we have e.g. grid computing  
machines, which communicates each other with multiple streams over long  
fast links, the so-expensive memory may be wasted on TCP windows, rather  
than computations. Am I very wrong here?

Best regards
Radek

-- 
______________________________________________________________________
Radoslaw Krzywania       Network Research and Development
[email-masked]      Poznan Supercomputing and Networking Center
+48 61 858 20 28         http://www.man.poznan.pl
______________________________________________________________________

From: [email-masked] (Phelan, Tom)
Date: Tue Feb  7 15:28:00 2006
Subject: [Iccrg] What's wrong with TCP Congestion control
Message-ID: <[email-masked]>

Hi All,

I'd like to point out that the large buffer requirement is not an
intrinsic property of window-based congestion control.  It's the result
of the requirement for reliability, coupled with the large transmit
window.  If you don't need reliability (as with DCCP and its AIMD
congestion control), the need for sender buffering is greatly reduced.

Tom Phelan

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
On
> Behalf Of Simon Leinen
> Sent: Tuesday, February 07, 2006 8:43 AM
> To: Radek Krzywania
> Cc: [email-masked]
> Subject: Re: [Iccrg] What's wrong with TCP Congestion control
> 
> Radek Krzywania writes:
> > On Tue, 07 Feb 2006 01:50:29 +0100, S. Keshav <[email-masked]>
> wrote:
> >> Here is a list paraphrased from mail so far:
> >>
> >> 1. Unsustainable large equilibrium window sizes under high
> >> bandwidth-delay
> >> product environments; requires an unrealistically low loss
probability.
> >> (Leads to limited dynamic range)
> 
> > Maybe it is good to say explicitly, that large windows requires
large
> > memory buffers on sender and receiver sides.
> 
> The large buffer requirements are mostly due to the fundamental nature
> of window-based transmission, independent of TCP's congestion control
> algorithm: You need to support a large amount of unacknowledged data
> (the window) to sustain the throughput, and you need the buffers at
> the sender so that you can retransmit.
> 
> (The requirement for equally large buffers at the receiver seems more
> like a constraint of the current prevailing interface to TCP in
> end-systems.)
> 
> The only relation between TCP's congestion control and required buffer
> sizes that I can see is when queueing at the bottleneck starts to
> significantly increase RTT.
> --
> Simon.
> 
> 
> _______________________________________________
> Iccrg mailing list
> [email-masked]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg

From: [email-masked] (Simon Leinen)
Date: Tue Feb  7 13:47:44 2006
Subject: [Iccrg] What's wrong with TCP Congestion control
In-Reply-To: <op.s4lhymsvzxx9ui@edelweiss> (Radek Krzywania's message of "Tue, 07 Feb 2006 10:00:12 +0100")
References: <[email-masked]> <op.s4lhymsvzxx9ui@edelweiss>
Message-ID: <[email-masked]>

Radek Krzywania writes:
> On Tue, 07 Feb 2006 01:50:29 +0100, S. Keshav <[email-masked]> wrote:
>> Here is a list paraphrased from mail so far:
>> 
>> 1. Unsustainable large equilibrium window sizes under high
>> bandwidth-delay
>> product environments; requires an unrealistically low loss probability.
>> (Leads to limited dynamic range)

> Maybe it is good to say explicitly, that large windows requires large
> memory buffers on sender and receiver sides.

The large buffer requirements are mostly due to the fundamental nature
of window-based transmission, independent of TCP's congestion control
algorithm: You need to support a large amount of unacknowledged data
(the window) to sustain the throughput, and you need the buffers at
the sender so that you can retransmit.

(The requirement for equally large buffers at the receiver seems more
like a constraint of the current prevailing interface to TCP in
end-systems.)

The only relation between TCP's congestion control and required buffer
sizes that I can see is when queueing at the bottleneck starts to
significantly increase RTT.
-- 
Simon.

From: [email-masked] (Radek Krzywania)
Date: Tue Feb  7 09:08:16 2006
Subject: [Iccrg] What's wrong with TCP Congestion control
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <op.s4lhymsvzxx9ui@edelweiss>

On Tue, 07 Feb 2006 01:50:29 +0100, S. Keshav <[email-masked]> wrote:

> Here is a list paraphrased from mail so far:
>
> 1. Unsustainable large equilibrium window sizes under high  
> bandwidth-delay
> product environments; requires an unrealistically low loss probability.
> (Leads to limited dynamic range)

Maybe it is good to say explicitly, that large windows requires large
memory buffers on sender and receiver sides.

Best regards
Radek

-- 
______________________________________________________________________
Radoslaw Krzywania       Network Research and Development
[email-masked]      Poznan Supercomputing and Networking Center
+48 61 858 20 28         http://www.man.poznan.pl
______________________________________________________________________

From: [email-masked] (S. Keshav)
Date: Tue Feb  7 00:55:28 2006
Subject: [Iccrg] What's wrong with TCP Congestion control
Message-ID: <[email-masked]>

Here is a list paraphrased from mail so far:

1. Unsustainable large equilibrium window sizes under high bandwidth-delay
product environments; requires an unrealistically low loss probability.
(Leads to limited dynamic range)
?2. Low throughput under lossy environments because of using loss as an
indication of congestion.
?3. Slow additive increase: Takes a long time for flow to catch up with
spare capacity and results in unnecessary long flow-completion times.
?4. Inefficient Slow-start: Even when the flow is capable of completing
within a round-trip time, slow-start makes flows last multiple round-trip
times just to find their fair share rate. Often most flows complete
before?they exit slow-start phase.??
?5. Large queueing delay: TCP fills up any amount of buffering available at
the bottleneck links. Results in long latency.?
?6. Unfair bandwidth sharing: shares bandwidth inversely proportional to
flow RTTs
7. TCP builds a standing queue at the point of congestion, which increases
the delay. 

Did I miss anything?

thanks
keshav

From: [email-masked] (S. Keshav)
Date: Tue Feb  7 00:34:08 2006
Subject: [Iccrg] Comments on definitions of congestion
Message-ID: <[email-masked]>

I am commenting on the mail from the last couple of days on the definition
of congestion. As my previous mail from today shows, I believe it should be
user-centric and using the notion of utility.

keshav
-----

1. Nandita Dukkipati writes:
* A network-centric definition of congestion: Congestion is anything that
deviates significantly from an efficient and fair usage of the network
resources --- mostly network bandwidth and buffers.
* User-centric definition: From an user's view point what really matters is
how quickly does my flow finish, so congestion is long flow-completion
times. Often, it isn't the per-packet latency that users care about, but
just how fast the entire flow completes.
---
I am not sure there a network-centric definition makes any sense! A network
is for its users, not a thing-in-itself. If users are satisfied, then the
network is working, otherwise it is a not-work :-)

A user-centric definition that only takes flow completion times is
meaningless for voice traffic.

----
2. John Leslie writes:
   To me, congestion is the condition where a packet can't be sent
"immediately" (meaning perhaps that it can't be queued as the next
packet to be sent).

   Clearly, many if not most Internet applications are perfectly happy
with some time in the queue; and it is arguable that some "smallish" time
in queue should be called "uncongested".

   I do not agree, however, that a definition of "congestion" should
be based on packets actually being dropped.

--
You seem to imply that congestion happens any time the arrival rate exceeds
the service rate. However, this ignores the ability of buffers to rate-match
and smooth over transients. If a small buffer allows transient overloads and
this happens 'under the radar' from the perspective of a user, why would you
call the network congested?

----
3. Kewin Stoeckigt writes:
I understand congestion
as some sort of "sudden interruption"...that means, at one point,
packets are delayed (higher delay than usual/expected), dropped, etc.
However, if the delay = constant (without packet loss), I wouldn't call
this necessarily congestion.
---
You imply that congestion is associated with a sudden interruption. This is
somewhat imprecise. Do you mean the variance in the interarrival times at
the receiver goes beyond a threshold? If so, what is a universally
agreed-upon threshold?

---
4. Michael Welzl writes:
There is no `official',
universally accepted definition of network congestion; this being said, the
most elaborate attempt was probably made in (Keshav 1991a).
--
Thanks for the reference, Michael! You made my day :-)

----
5. Damon Wischik writes:
...congestion should be measured by (A) drop probability,
which seriously impacts flows that last only one or two packets, by sending
them into timeout; and (B) queueing delay, which hurts real-time traffic;
and (C) correlation of losses, since bursts of loss also hurt real-time
traffic; and (D) inability to accomodate a reasonable volume of very short
non-responsive transactions (I hesitate now to call them "flows" when
they're really just "impulses").
---
I guess this is answering the question: How should we measure congestion?
rather than What is congestion. Please see my thesis excerpt on why I think
this measure the effects of congestion, rather than what is congestion.

----
6. Yong Xia writes:
Congestion happens when demand exceeds capacity.
 
At each link, if the aggregate incoming traffic rate is less than the link
capacity, then there is no congestion on this link (in steady state). In a
network, if there is no congestion on all the links, there is no congestion
in this network. 
---- 
This has the same problem as John Leslie's definition, i.e. it ignores the
effect of buffers.

---
7. Tom Petch writes:
congestion can occur whereever there is a limited resource;
links, yes, but buffers, cache, processor capacity etc

And while queue and loss may occur, so could delay, delay variation,
re-ordering, any kind of impairment.

As to impact, it depends on the nature of the traffic; what matters to VOIP
may
not to file download and v.v.

---
Exactly, and that is why congestion needs to be defined from a user
perspective.

---

From: [email-masked] (S. Keshav)
Date: Tue Feb  7 00:10:40 2006
Subject: [Iccrg] My definition of congestion
Message-ID: <[email-masked]>

Folks,
    Here is an excerpt from my 1991 thesis that answers one of the two
questions I raised: What is congestion? I will attempt to discuss the other
opinions presented in this list in a separate message.

--------------------8<--------------------------------------

Some common definitions of congestion

Since congestion occurs at high network
loads, definitions of congestion focus on some aspect of network behavior
under high load. We first discuss a scenario that leads to network
congestion in reservationless networks, and then motivate some definitions.

Consider a reservationless network, where, due to some reason, the short
term packet arrival rate at some switch exceeds its service rate. (The
service rate is determined by the processing time per packet and the
bandwidth of the output line. Thus, the bottleneck could be either the
switch?s CPU or the outgoing line: in either case, there is congestion.) At
this point, packets are buffered, leading to delays. The additional delay
can cause sources to time out and retransmit, increasing the load on the
bottleneck [101]. This feedback leads to a rapidly deteriorating situation
where retransmissions dominate the traffic, and effective throughput rapidly
diminishes. Further, if there is switch to switch flow control (as
in ARPANET, Tym- net, Datapac, Sirpent, etc.), new packets may not be
allowed to enter the switch, and so packets might be delayed at a
preceding switch as well. This can lead to deadlock, where all traffic comes
to a standstill. 

Note that three things happen simultaneously.

- First,  the queueing delay of the data packets increases.
- Second, there may be packet losses.
- Finally, in the congested state, the traffic is dominated by
retransmissions, so that the effective data rate decreases.

The standard definitions of congestion are thus of the form: ??A network is
congested if, due to overload, condition X occurs??, where X is excessive
queueing delay, packet loss or decrease in effective throughput.

These definitions are not satisfactory for several reasons.

First, delays and losses are indices of performance that are being
improperly used as indices of congestion, since the change in the indices
may be due to symptoms of phenomena other than congestion.

Second, the definitions do not specify the exact point at which the network
can be said 
to be congested (except in a deterministic network, where the knee of the
load-delay curve, and hence congestion, is well defined, but that is the
trivial case). For example, while a network that has mean queueing delays in
each switch of the order of 1 to 10 service times is certainly not
congested, it is not clear whether a network that has a queueing delay of
1000 service times is congested or not. It does not seem possible to come up
with any reasonable threshold value to determine congestion!

Third, a network that is congested from the perspective of one user is not
necessarily cong- ested from the perspective of another. For example, if
user A can tolerate a packet loss rate of 1 in 1000, and user B can tolerate
a packet loss rate of 1 in 100, and the actual loss rate is 1 in 500, then A
will claim that the network is congested, whereas B will not. A network
should be called uncongested only if all the users agree that it is.

A New definition 

>From the discussion above, it is clear that network congestion
depends on a user?s perspective. A user who demands little from the
network can tolerate a loss in performance much better than a more demanding
user. For example, a user who uses a network only to send and receive
electronic mail will be happy with a delivery delay of a day, while this
performance is unacceptable for a user who uses a network for real-time
audio communication. The key point is the notion of the utility that a user
gets from the network, and how this utility degrades with network loading.

The concept of ?utility? used here is borrowed from economic theory. It is
used to refer to a user?s preference for a resource, or a set of resources
(often called a resource bundle). Strictly speaking, the utility of a user
is a number that represents the relative preference of that user for a
resource (or performance) bundle, so that, if a user prefers bundle A to
bundle B, the utility of A is greater than the utility of B. For example, if
A is {end-to-end delay of 1 second, average throughput 200 pkts/second}, and
B is {end-to-end delay of 100 seconds, average throughput 20000
pkts/second}, a user may prefer A to B, and we would assign a utility to A
that is greater than the utility of B, while another user may do the
opposite. 

In classic microeconomic theory, utilities are represented by a
function over the resources. Since utilities express only a preference
ordering, utility functions are insensitive to monotonic translations, and
the utilities of two users cannot be compared; the function can only be used
to relatively rank two resource bundles from the point of view of a single
user. An example of a utility function is ?T ? (1??)RTT, where ? is a
weighting constant, T is the average throughput over some interval, and
RTT is the average round-trip-time delay over the same interval. As the
throughput increases, the utility increases, and as delays increase, the
utility decreases. The choice of ? determines the relative weight a user
gives to throughput and delay. A delay-sensitive user will choose ??0,
whereas a delay-insensitive user?s ??1.

In practice, a utility function may
depend on a threshold. For example, a user may state that he or she is
indifferent to delay, as long as it is less than 0.1 seconds. Thus, if the
user gets a delay of 0.05 seconds during some interval of time, and 0.06
seconds in a later period, as far as the user is concerned, there has been
no loss of utility. However, if some user?s utility does decrease as a
result of an increase in the network load, that user will perceive the
network to be congested. This motivates our definition.

Definition:

A network  is said to be congested from the perspective of user i if the
utility of i decreases due to an increase in network load.

Remarks: 

1. A network can be
congested from the perspective of one user, and uncongested from the
perspective of another.

2. A network can be said to be strictly uncongested
if no user perceives it to be congested.

3. A user?s utility may decrease
due to something other than network load, but the user may not be able to
tell the difference. The onus on the user is to determine the cause of the
loss of utility, and to take appropriate corrective action.

This definition 
is better than existing definitions since it avoids the three problems
raised earlier. First, we make a clear distinction between a performance
index and a congestion index. It is possible for a performance metric to
decrease (for example, for RTT to increase), without a change in the
congestion index (for example, if ? = 1). Second, the definition makes it
clear that congestion occurs from the point of view of each individual user.
Finally, the point of congestion is precisely the one where the user detects
a loss of utility. No further precision is necessary, since, if the users
are not dissatisfied with the available service, then the network
performance, no matter how poor it is in absolute terms, is satisfactory.

Our definition places congestion control in a new light. A network that
controls congestion, by our definition, must be responsive to the utility
function of the users, and must be able to manage its resources so that
there is no loss of utility as the load increases. Thus, the network must be
able to differentiate between conversations, and prioritize conversations
depending on the stringency of their owner?s utility. A naive approach that
ignores the user?s quality-of-service requirements is automatically ruled
out by this definition.

------8<-----------------

The rest of the chapter can be found at:

http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/91/thesis/ch1.pdf

There is some material there also on scope, requirements, and assumptions
that are relevant to this list, and we should probably discuss those later.

thanks

keshav

From: [email-masked] (Saverio Mascolo)
Date: Mon Feb  6 18:35:44 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <1139250597.5311.51.camel@debian>

> I think you are assuming that the queue occupancy for each flow is
> constant over time.  If you relax that assumption, then you no longer
> have the implication.
> 
> There may exist viable control schemes which control the flows (and
> have whatever other desirables properties) while keeping the average
> queue occupancy small.
> 
> Do you agree?

then i agree and is  necessary to decide how to fix the queue dynamics. 

> 
> > i have read somewhere, maybe on s. floud homepage, a note on "why
> > control queue length should not be a target". i am not sure, but i think
> > she had  similar arguments.
> 
> I looked on her web pages at http://www.icir.org/floyd/papers.html
> and  http://www.icir.org/floyd/notes.html  and did not manage to
> identify which note you would be refering to.

i am sure it was a note written by floyd. maybe she can help on this.

saverio

> 
> > in other words, if you control queue at fixed value you would prevent
> > other flows to join.
> 
> I think there must be assumptions in your reasoning that I did not
> mean to imply.
> 
> 			-Tim Shepard
> 			 [email-masked]

From: [email-masked] (Tim Shepard)
Date: Mon Feb  6 17:42:24 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: Your message of Mon, 06 Feb 2006 18:07:33 +0100. <1139245653.5311.39.camel@debian>
Message-ID: <[email-masked]>

> > > > > A better congestion control scheme would control the queue length,
> > > > > with a target of zero (or very few) packets, thereby minimizing the
> > > > > impact on delay.
> > > 
> > > by targetting a queue level of few packets we  have that each flow gets
> > > a constant fraction of the buffer space. In a FIFO queue this translates
> > > in the same fraction of used bandwdith.
> > 
> > Why is that?
> > 
> > I don't think that is necessarily true.  It may be true for some kinds
> > of control schemes, but it is not necessarily true for all kinds of
> > control schemes.
>
> let assume  that you have a buffer of 10 packets and two connections: A
> and B. Let assume that target queue is 6 packets for flow A and  4 for
> flow  B. Then flow A would get 6/10-th of the bandwdith and B 4/10-th.
> 

I think you are assuming that the queue occupancy for each flow is
constant over time.  If you relax that assumption, then you no longer
have the implication.

There may exist viable control schemes which control the flows (and
have whatever other desirables properties) while keeping the average
queue occupancy small.

Do you agree?

> i have read somewhere, maybe on s. floud homepage, a note on "why
> control queue length should not be a target". i am not sure, but i think
> she had  similar arguments.

I looked on her web pages at http://www.icir.org/floyd/papers.html
and  http://www.icir.org/floyd/notes.html  and did not manage to
identify which note you would be refering to.

> in other words, if you control queue at fixed value you would prevent
> other flows to join.

I think there must be assumptions in your reasoning that I did not
mean to imply.

			-Tim Shepard
			 [email-masked]

From: [email-masked] (Saverio Mascolo)
Date: Mon Feb  6 17:12:32 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <1139245653.5311.39.camel@debian>

On Mon, 2006-02-06 at 10:55 -0500, Tim Shepard wrote:
> > On Sat, 2006-02-04 at 15:56 -0500, John Leslie wrote:
> > > Tim Shepard <[email-masked]> wrote:
> > > > To: "S. Keshav" <[email-masked]>
> > > > 
> > > >> What's wrong with TCP's congestion control scheme
> > > > 
> > > > The problem with TCP's congestion control scheme is that it builds a
> > > > standing queue at the point of congestion, which increases the delay.
> > > 
> > >    I'd go farther than than: the fundamental problem with TCP's
> > > congestion control scheme is that it never measures congestion.
> > > 
> > >    That said, I agree with Tim that building a queue (of unknown length)
> > > at the point of congestion is not very smart congestion control.
> > > 
> > > > A better congestion control scheme would control the queue length,
> > > > with a target of zero (or very few) packets, thereby minimizing the
> > > > impact on delay.
> > 
> > by targetting a queue level of few packets we  have that each flow gets
> > a constant fraction of the buffer space. In a FIFO queue this translates
> > in the same fraction of used bandwdith.
> 
> Why is that?
> 
> I don't think that is necessarily true.  It may be true for some kinds
> of control schemes, but it is not necessarily true for all kinds of
> control schemes.

let assume  that you have a buffer of 10 packets and two connections: A
and B. Let assume that target queue is 6 packets for flow A and  4 for
flow  B. Then flow A would get 6/10-th of the bandwdith and B 4/10-th.

i have read somewhere, maybe on s. floud homepage, a note on "why
control queue length should not be a target". i am not sure, but i think
she had  similar arguments.

in other words, if you control queue at fixed value you would prevent
other flows to join.

-s

From: [email-masked] (Tim Shepard)
Date: Mon Feb  6 16:02:08 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: Your message of Mon, 06 Feb 2006 12:56:17 +0100. <1139226977.5311.21.camel@debian>
Message-ID: <[email-masked]>

> On Sat, 2006-02-04 at 15:56 -0500, John Leslie wrote:
> > Tim Shepard <[email-masked]> wrote:
> > > To: "S. Keshav" <[email-masked]>
> > > 
> > >> What's wrong with TCP's congestion control scheme
> > > 
> > > The problem with TCP's congestion control scheme is that it builds a
> > > standing queue at the point of congestion, which increases the delay.
> > 
> >    I'd go farther than than: the fundamental problem with TCP's
> > congestion control scheme is that it never measures congestion.
> > 
> >    That said, I agree with Tim that building a queue (of unknown length)
> > at the point of congestion is not very smart congestion control.
> > 
> > > A better congestion control scheme would control the queue length,
> > > with a target of zero (or very few) packets, thereby minimizing the
> > > impact on delay.
> 
> by targetting a queue level of few packets we  have that each flow gets
> a constant fraction of the buffer space. In a FIFO queue this translates
> in the same fraction of used bandwdith.

Why is that?

I don't think that is necessarily true.  It may be true for some kinds
of control schemes, but it is not necessarily true for all kinds of
control schemes.

			-Tim Shepard
			 [email-masked]

From: [email-masked] (Tom Petch)
Date: Mon Feb  6 17:01:52 2006
Subject: [Iccrg] Proposal for ICCRG operations
References: <[email-masked]>
Message-ID: <02d101c62b36$01a72f40$0601a8c0@pc6>

----- Original Message -----
From: "Yong Xia" <[email-masked]>
To: "S. Keshav" <[email-masked]>; <[email-masked]>
Cc: "Ion Stoica" <[email-masked]>; "Lakshminarayanan Subramanian"
<[email-masked]>; "Yong Xia" <[email-masked]>
Sent: Monday, February 06, 2006 5:19 AM
Subject: Re: [Iccrg] Proposal for ICCRG operations

> Hi Keshav,
>
> My two cents on the questions you raised:
>
> >>  A. What is the commonly agreed definition for congestion. (I will post
> my suggestion later today). If we do not agree on a definition, then indices
> are meaningless.
>
> Congestion happens when demand exceeds capacity. Queue and loss are the
> *outcome* of congestion, but not congestion itself.
>
> Therefore, in steady state, if there is congestion, queue builds and, up to
> a point, loss is resulted. If there is no congestion, there is no queue and
> no loss due to congestion. On the contrary, queue and loss do not
> necessarily mean congestion happens. There are other reasons that might
> cause queue or loss.
>
> At each link, if the aggregate incoming traffic rate is less than the
> link capacity, then there is no congestion on this link (in steady state).
> In a network, if there is no congestion on all the links, there is no
> congestion in this network.
>
Very much what I was going to get around to saying:-)  Going on from there, I
would say that congestion can occur whereever there is a limited resource;
links, yes, but buffers, cache, processor capacity etc

And while queue and loss may occur, so could delay, delay variation,
re-ordering, any kind of impairment.

As to impact, it depends on the nature of the traffic; what matters to VOIP may
not to file download and v.v.

The best scheme I have worked with was proprietary and many years ago now; it
measured the utilisation of the resource, factored in the traffic type and
generated explicit congestion control when appropriate.

I think that schemes that try to infer congestion from its consequences - eg
packet loss - should always be regarded as second best, even if that is all we
can do at the time.

Tom Petch

 <snip>
>
> Best,
> Yong
>
>

From: [email-masked] (Saverio Mascolo)
Date: Mon Feb  6 12:01:04 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <20060204205628.GB99125@verdi>
References: <[email-masked]> <[email-masked]> <[email-masked]> <20060204205628.GB99125@verdi>
Message-ID: <1139226977.5311.21.camel@debian>

On Sat, 2006-02-04 at 15:56 -0500, John Leslie wrote:
> Tim Shepard <[email-masked]> wrote:
> > To: "S. Keshav" <[email-masked]>
> > 
> >> What's wrong with TCP's congestion control scheme
> > 
> > The problem with TCP's congestion control scheme is that it builds a
> > standing queue at the point of congestion, which increases the delay.
> 
>    I'd go farther than than: the fundamental problem with TCP's
> congestion control scheme is that it never measures congestion.
> 
>    That said, I agree with Tim that building a queue (of unknown length)
> at the point of congestion is not very smart congestion control.
> 
> > A better congestion control scheme would control the queue length,
> > with a target of zero (or very few) packets, thereby minimizing the
> > impact on delay.

by targetting a queue level of few packets we  have that each flow gets
a constant fraction of the buffer space. In a FIFO queue this translates
in the same fraction of used bandwdith.

what does happen to statistical multiplexing, i.e. to the need of
reshuffling  bandwidth to allocate new flows

saverio

> 
>    That problem looked hard when TCP was invented; and we settled for
> a kind-of brain-dead mechanism (which has worked far better than I would
> have believed).
> 
>    Ideally, we'd move the queuing all the way back to the sender (unless
> someone along the path from the sender can bypass the congestion point).
> 
> --
> John Leslie <[email-masked]>
> 
> _______________________________________________
> Iccrg mailing list
> [email-masked]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg

From: [email-masked] (Yong Xia)
Date: Mon Feb  6 04:24:32 2006
Subject: [Iccrg] Proposal for ICCRG operations
Message-ID: <[email-masked]>

Hi Keshav,

My two cents on the questions you raised:

>>  A. What is the commonly agreed definition for congestion. (I will post
my suggestion later today). If we do not agree on a definition, then indices
are meaningless.

Congestion happens when demand exceeds capacity. Queue and loss are the
*outcome* of congestion, but not congestion itself.

Therefore, in steady state, if there is congestion, queue builds and, up to
a point, loss is resulted. If there is no congestion, there is no queue and
no loss due to congestion. On the contrary, queue and loss do not
necessarily mean congestion happens. There are other reasons that might
cause queue or loss.

At each link, if the aggregate incoming traffic rate is less than the
link capacity, then there is no congestion on this link (in steady state).
In a network, if there is no congestion on all the links, there is no
congestion in this network.

>> B. What's wrong with TCP's congestion control scheme. Does someone have a
concise summary that they can post here? I am sure this will be a
cut-and-paste job for someone who has written a paper on congestion control
recently :-)

TCP's problems are mainly two: 1) Using loss to detect congestion. Even
though this works in wired networks such as today's Internet, loss is a
too-late (binary) signal --- congestion has already happened when loss is
seen. Non-congestion caused loss is also a common case in wireless networks;
2) The limited *information* about congestion using loss as the indicator
limits the choice of congestion control algorithm. TCP's AIMD has a dynamic
range that does not scale to the future high-speed, long-delay networks.

Best,
Yong
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060206/6dcbc85f/attachment.html
>From [email-masked]  Mon Feb  6 11:52:32 2006
From: [email-masked] (Saverio Mascolo)
Date: Mon Feb  6 11:58:56 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
	<[email-masked]>
Message-ID: <1139226692.5311.15.camel@debian>

see in line...

On Sat, 2006-02-04 at 11:50 -0800, Nandita Dukkipati wrote:
> Here's my take on the questions put forth by Keshav. For now I will
> limit my answers to elastic traffic.
> 
> >  A. What is the commonly agreed definition for congestion. (I will
> > post
> > my suggestion later today). If we do not agree on a definition, then
> > indices
> > are meaningless.
> 
> 
> * A network-centric definition of congestion: Congestion is anything
> that deviates significantly from an efficient and fair usage of the
> network resources --- mostly network bandwidth and buffers.
> * User-centric definition: From an user's view point what really
> matters is how quickly does my flow finish, so congestion is long
> flow-completion times. Often, it isn't the per-packet latency that
> users care about, but just how fast the entire flow completes.
> 
> >     B. What's wrong with TCP's congestion control scheme. Does
> > someone have
> > a concise summary that they can post here? I am sure this will be a
> > cut-and-paste job for someone who has written a paper on congestion
> > control
> > recently :-)
> 
> 
> Here's one list:

>  1. Unsustainable large equilibrium window sizes under high
> bandwidth-delay product environments; requires an unrealistically low
> loss probability.

do we have some numbers here? what is the bit error rate range that we
can assume  realistic in 10Gbps links?

saverio

From: [email-masked] (Damon Wischik)
Date: Sun Feb  5 17:01:52 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

> Here's my take on the questions put forth by Keshav. For now I will limit
> my answers to elastic traffic.
> [...]
> * A network-centric definition of congestion: Congestion is anything that
> deviates significantly from an efficient and fair usage of the network
> resources --- mostly network bandwidth and buffers.
> * User-centric definition: From an user's view point what really matters
> is how quickly does my flow finish, so congestion is long flow-completion
> times. Often, it isn't the per-packet latency that users care about, but
> just how fast the entire flow completes.

Here's a different perspective:

Most flows in the Internet are short-duration, e.g. HTTP requests, retriving
one- or two-packet items from a web page. Increasingly, also, we will want
to use the Internet for real-time traffic, e.g. video. For other uses, e.g.
web browsing, we want the first page of text to arrive fast, but the rest we
don't mind about so much. For web services, it's also often short flows that
go to form a transaction. [These are just plain assertions on my part. I
haven't got good data to hand to back them up.]

Elastic flows (by which I mean flows which are in congestion avoidance, or
maybe I mean flows which can't complete in one RTT) matter, but they're not
a good subset of flows on which to base a notion of congestion.

Instead, a notion of congestion should address the performance perceived by
very short flows. Since these flows have no time to respond to any feedback
about the state of the network, they are basically "open loop". Therefore
the most succinct way to say what performance they will perceive is to
summarize network-centric congestion measures.

(I noticed your paper "Why flow-completion time is the right metric for
congestion control", SIGCOMM/CCR January 2006. You point out that TCP and
XCP can make flows take several RTT to complete, when in fact they should be
able to complete in less than one RTT. Your proposal, RCP, seems like an
excellent way to achieve this, for flows of moderate duration (meaning: more
than one RTT). For flows of very short duration (meaning: capable of being
transferred in less than one RTT), we'd like to be able to transfer the file
without having to wait for any feedback from the network, and surely the
only way to achieve this is to have the network operating at say 95% or less
capacity, leaving 5% of capacity free for these instantaneous transfers.
Your RCP algorithm also seems to achieve something like this, but I am not
clear if this was designed in, or if it is serendipity.)

Therefore, perhaps, congestion should be measured by (A) drop probability,
which seriously impacts flows that last only one or two packets, by sending
them into timeout; and (B) queueing delay, which hurts real-time traffic;
and (C) correlation of losses, since bursts of loss also hurt real-time
traffic; and (D) inability to accomodate a reasonable volume of very short
non-responsive transactions (I hesitate now to call them "flows" when
they're really just "impulses").

Interestingly, however, since the bulk of packets come from long flows, that
is where we should work on getting congestion-control right. I suggest that
a good question might be: "What sort of congestion control for long-lived
flows will lead to the best network-centric congestion measures, i.e. will
lead to the best performance for short-lived open-loop flows?"

Damon.

From: [email-masked] (Michael Welzl)
Date: Sun Feb  5 13:43:28 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <[email-masked]>

> 2. Several of us have already started discussions on congestion control
> indices, and modifications to these indices, and so on. I think this is
> jumping the gun. I think it would be better to focus first on two issues:

Indeed, what my mail clearly showed right away is that it isn't
an easy task to find an index that we can all live with. On the
one hand, such an index is supposed to simplify things, while
on the other, there will always be somebody who thinks that
parameters x and y should be part of it. In accordance with your
very reasonable request, I hope that we can stop (or perhaps
postpone) this discussion; as I mentioned in the original mail,
I didn't really hope that this would lead to some consensus - all
I wanted is to provide "food for thought". It's nice to see that
there is some agreement that such an index would be a good thing
to have, though, so I'd be glad if we could get back to it at
some later stage.

>     A. What is the commonly agreed definition for congestion. (I will post
> my suggestion later today). If we do not agree on a definition, then indices
> are meaningless.

Here's what I decided to write about this issue in my book:

Now that we know the origin and some of the technical implications of
congestion, let us find a way to describe it. There is no `official',
universally accepted definition of network congestion; this being said, the
most elaborate attempt was probably made in (Keshav 1991a). Here is a slightly
simplified form of this definition, which acknowledges that the truly important
aspect of network performance is not some technical parameter but user
experience:

A network is said to be congested from the perspective of a user if the
service quality noticed by the user decreases due to an increase in network
load.

(Keshav 1991a) is your ph.d. thesis, of course.

>     B. What's wrong with TCP's congestion control scheme. Does someone have
> a concise summary that they can post here? I am sure this will be a
> cut-and-paste job for someone who has written a paper on congestion control
> recently :-)

That's a hard one - especially the "concise" part. There are many things that
could be said for and against the way TCP works today - on the one hand, I tend
to agree with what has just been said by others about TCP first creating
congestion in order to undo it afterwards. On the other, the strength about
both TCP and IP is the general applicability of these protocols, so when we say
"this is wrong about TCP", we should immediately ask ourselves "would TCP work
at least as good as today in any (future) environment we can think of if we
were to change this?".

In the light of these requirements, I would at least hesitate to say "yes, we
need it to take delay as a congestion measure" ... perhaps, but maybe not, if
we think of link layer ARQ etc.

By the way, I couldn't come up with a scenario where HighSpeed TCP would NOT
work at least as good as TCP works today... so considering the change that was
done for this protocol might be a starting point.

> Lets see if we can reach consensus on these two issues in a week's time.
> These will also form parts 1 and 2 of the consensus document. I ask for your
> co-operation in keeping the discussion to these two issues.

Okay!

Cheers,
Michael

From: [email-masked] (Kewin Stoeckigt)
Date: Sun Feb  5 02:50:40 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <20060204210328.GC99125@verdi>
References: <[email-masked]> <[email-masked]> <20060204210328.GC99125@verdi>
Message-ID: <[email-masked]>

...
>    I don't believe there is one. :^(

Indeed, this is rather tricky.

> 
>    To me, congestion is the condition where a packet can't be sent
> "immediately" (meaning perhaps that it can't be queued as the next
> packet to be sent).

See, for me this would not be congestion at all. I understand congestion 
as some sort of "sudden interruption"...that means, at one point, 
packets are delayed (higher delay than usual/expected), dropped, etc. 
However, if the delay = constant (without packet loss), I wouldn't call 
this necessarily congestion.

But as you said, it is tricky to find a common definition for congestion.

...
>    It's not quite that bad: if an index of "congestion" doesn't define
> what it's measuring, then that index is meaningless. However, I believe
> we can make use of indices which measure different things.

Maybe we should go away from the single word "congestion" and describe a 
type of congestion, which then could be measured. By this I mean that 
lets say congestion A describes a behavior where packets are just 
delayed, but not dropped, congestion B describes actual packet loss, and 
so forth. Coming up with indices for the different types, A, B, etc., 
could the lead to some sort of measurement index for a certain congestion.

Just my few thoughts on a Sunday afternoon with coffee....

Kewin

> 
> --
> John Leslie <[email-masked]>
> 
> _______________________________________________
> Iccrg mailing list
> [email-masked]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
> 

From: [email-masked] (John Leslie)
Date: Sat Feb  4 21:20:00 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <20060204211436.GE99125@verdi>

Shivkumar Kalyanaraman <[email-masked]> wrote:
> 
> BTW, what are the directions are we really interested in for this group?

   This is a very good question. (I suspect different folks come with
different preferred directions.)

> - long BD products?

   I think we need to tackle the bandwidth-delay problem.

> - loss tolerance in wireless?

   I don't think we can tackle this directly until we decouple
congestion-awareness from packet loss (which I believe we should do).

> - more robustness to variance in underlying links?

   I don't know what the level of interest here is. Personally I'd like
to rate links on bandwidth and latency, with expected variance in each.

> - fairness considerations (max-min/processor sharing vs proportional etc)?

   This one is a bit scary. I'd prefer to defer fairness flamewars until
we've got some actual algorithms in use, being actively measured.

> Is there a priorization of relevant concerns? I only saw a broad wish list
> in the original talks...

   In research, traditional "prioritization" doesn't apply: work of interest
to individuals with time available gets done; other work doesn't.

--
John Leslie <[email-masked]>

From: [email-masked] (John Leslie)
Date: Sat Feb  4 21:07:12 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <20060204210328.GC99125@verdi>

S. Keshav <[email-masked]> wrote:
> 
> What is the commonly agreed definition for congestion

   I don't believe there is one. :^(

   To me, congestion is the condition where a packet can't be sent
"immediately" (meaning perhaps that it can't be queued as the next
packet to be sent).

   Clearly, many if not most Internet applications are perfectly happy
with some time in the queue; and it is arguable that some "smallish" time
in queue should be called "uncongested".

   I do not agree, however, that a definition of "congestion" should
be based on packets actually being dropped.

> If we do not agree on a definition, then indices are meaningless.

   It's not quite that bad: if an index of "congestion" doesn't define
what it's measuring, then that index is meaningless. However, I believe
we can make use of indices which measure different things.

--
John Leslie <[email-masked]>

From: [email-masked] (Nandita Dukkipati)
Date: Sat Feb  4 19:54:40 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <[email-masked]>

Here's my take on the questions put forth by Keshav. For now I will  
limit my answers to elastic traffic.

>  A. What is the commonly agreed definition for congestion. (I will  
> post
> my suggestion later today). If we do not agree on a definition,  
> then indices
> are meaningless.

* A network-centric definition of congestion: Congestion is anything  
that deviates significantly from an efficient and fair usage of the  
network resources --- mostly network bandwidth and buffers.
* User-centric definition: From an user's view point what really  
matters is how quickly does my flow finish, so congestion is long  
flow-completion times. Often, it isn't the per-packet latency that  
users care about, but just how fast the entire flow completes.

>     B. What's wrong with TCP's congestion control scheme. Does  
> someone have
> a concise summary that they can post here? I am sure this will be a
> cut-and-paste job for someone who has written a paper on congestion  
> control
> recently :-)

Here's one list:

  1. Unsustainable large equilibrium window sizes under high  
bandwidth-delay product environments; requires an unrealistically low  
loss probability.
  2. Low throughput under lossy environments because of using loss as  
an indication of congestion.
  3. Slow additive increase: Takes a long time for flow to catch up  
with spare capacity and results in unnecessary long flow-completion  
times.
  4. Inefficient Slow-start: Even when the flow is capable of  
completing within a round-trip time, slow-start makes flows last  
multiple round-trip times just to find their fair share rate. Often  
most flows complete before they exit slow-start phase.
  5. Large queueing delay: TCP fills up any amount of buffering  
available at the bottleneck links. Results in long latency.
  6. Unfair bandwidth sharing: shares bandwidth inversely  
proportional to flow RTTs

  -Nandita

>
> Lets see if we can reach consensus on these two issues in a week's  
> time.
> These will also form parts 1 and 2 of the consensus document. I ask  
> for your
> co-operation in keeping the discussion to these two issues.
>
> thanks
>
> kesahv

Nandita Dukkipati
Graduate Student
Computer Systems Lab
Stanford University

webpage: http://yuba.stanford.edu/~nanditad/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060204/d8110abd/attachment.html
>From [email-masked]  Sat Feb  4 20:56:32 2006
From: [email-masked] (John Leslie)
Date: Sat Feb  4 21:00:48 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
	<[email-masked]> <[email-masked]>
Message-ID: <20060204205628.GB99125@verdi>

Tim Shepard <[email-masked]> wrote:
> To: "S. Keshav" <[email-masked]>
> 
>> What's wrong with TCP's congestion control scheme
> 
> The problem with TCP's congestion control scheme is that it builds a
> standing queue at the point of congestion, which increases the delay.

   I'd go farther than than: the fundamental problem with TCP's
congestion control scheme is that it never measures congestion.

   That said, I agree with Tim that building a queue (of unknown length)
at the point of congestion is not very smart congestion control.

> A better congestion control scheme would control the queue length,
> with a target of zero (or very few) packets, thereby minimizing the
> impact on delay.

   That problem looked hard when TCP was invented; and we settled for
a kind-of brain-dead mechanism (which has worked far better than I would
have believed).

   Ideally, we'd move the queuing all the way back to the sender (unless
someone along the path from the sender can bypass the congestion point).

--
John Leslie <[email-masked]>

From: [email-masked] (Tim Shepard)
Date: Sat Feb  4 18:16:32 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: Your message of Sat, 04 Feb 2006 12:05:41 -0500. <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

>     B. What's wrong with TCP's congestion control scheme. Does someone have
> a concise summary that they can post here? I am sure this will be a
> cut-and-paste job for someone who has written a paper on congestion control
> recently :-)

The problem with TCP's congestion control scheme is that it builds a
standing queue at the point of congestion, which increases the delay.

A better congestion control scheme would control the queue length,
with a target of zero (or very few) packets, thereby minimizing the
impact on delay.

			-Tim Shepard
			 [email-masked]

From: [email-masked] (S. Keshav)
Date: Sat Feb  4 17:10:24 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
Message-ID: <[email-masked]>

A couple of comments:

1. I am glad that the plan of action seems to make sense. I am aware that
the schedule is aggressive. However, we do have 20 years of work to build
on, so getting to consensus in 2 years does not seem overly aggressive to
me!

2. Several of us have already started discussions on congestion control
indices, and modifications to these indices, and so on. I think this is
jumping the gun. I think it would be better to focus first on two issues:

    A. What is the commonly agreed definition for congestion. (I will post
my suggestion later today). If we do not agree on a definition, then indices
are meaningless.

    B. What's wrong with TCP's congestion control scheme. Does someone have
a concise summary that they can post here? I am sure this will be a
cut-and-paste job for someone who has written a paper on congestion control
recently :-)

Lets see if we can reach consensus on these two issues in a week's time.
These will also form parts 1 and 2 of the consensus document. I ask for your
co-operation in keeping the discussion to these two issues.

thanks

kesahv 

From: [email-masked] (Xiaoliang (David) Wei)
Date: Sat Feb  4 17:40:16 2006
Subject: [Iccrg] Proposal for ICCRG operations
References: <[email-masked]> <[email-masked]> <[email-masked]> <[email-masked]> <[email-masked]>
Message-ID: <07e101c629a9$3a4e4e20$f5f2010a@seashadow>

Thanks, all. About the benchmark, I have been thinking about a few questions 
that might be interesting in the process of designing a benchmark:

1. Who is expected to use the benchmark?
    My understanding is that there may be different groups of users that are 
interested in different properties of a congestion control algorithm.
    For example, distributed computation applications would prefer a low 
latency of the worst flow (this is max-min fairness). Data transfer users 
may emphasize on a higher average throughput. Media servers would like to 
have stable delay... As Linux allows users to select their preferred 
congestion control algorithm, network administrator is capable to select 
different algorithms in their private network, based on the major 
applications they have. In this case, I think it make sense to provide a few 
different metrics for different users.
    If the benchmark is to be used to identify a TCP candidate for 
standardization, we probably need to consider even more: incremental 
deployability (interaction with Reno), the impact of the algorithm to the 
network (link loss rate, queue fluctuation) and etc. In this case, we may 
also want to measure the realistic workload in Internet and feed it back to 
the benchmark.

2. Who will perform the benchmark tests, and how?
    As the e2e mailing list talking on some strange behaviors in NCSU's 
performance evaluation due to some buggy implementation, it brings up the 
problem that the same congestion control algorithm may perform very 
different because of a bug in the implementation, or even a hardware defect 
in the testbed.
    I think it will be better if we can have a standard hardware testbed 
that can repeatedly evaluate an implementation of congestion control 
algorithm. So, the protocol designers can iterate the process of 
design->implementation->testing and make sure that their algorithms are 
correctly evaluated. In this issue, I think WAN-in-Lab may help (at least 
partially) as a standard testing platform, if we can build a automatic 
testing system based on it.

just my 2 cents.

-David

Xiaoliang (David) Wei             Graduate Student in CS@Caltech
http://www.davidwei.org
====================================================
----- Original Message ----- 
From: "Lachlan Andrew" <[email-masked]>
To: "Michael Welzl" <[email-masked]>
Cc: "Aaron Falk" <[email-masked]>; "Steven Low" <[email-masked]>; "Lachlan 
Andrew" <[email-masked]>; "iccrg" <[email-masked]>; "Pei Cao" 
<[email-masked]>; "David Wei" <[email-masked]>; 
<[email-masked]>
Sent: Friday, February 03, 2006 3:57 PM
Subject: Re: [Iccrg] Proposal for ICCRG operations

Greetings all,

On 03 Feb 2006 09:32:27 +0100, Michael Welzl <[email-masked]> 
wrote:
> So, the index should contain:
>
> * normalized throughput
> * loss
> * fairness (let's use the Jain Fairness Index)
>
> It could then look something like this:
>
> WI = (T*t + L*l + F*f) / 3
>
> where WI is "Welzl Index" (tm)   ;-)
> T is normalized throughput
> L is normalized loss
> F is the Jain fairness index (which is already a value
> in the 0..1 range)

A good way to summarise throughput and fairness is just to take the
*harmonic* mean of the flows' throughputs instead of the arithmetic
mean (or equivalently, the aggregate througput).  That corresponds to
measuring the mean time to transfer a given number of bytes, which is
the quantity actually observed by an application.

This metric avoids the arbitraryness both of using a sum or product,
with the problem of  selecting weightings, and also of Jain's index.
(If one flow out of many is starved, Jain's index can still report
high "fairness", but the harmonic mean of rates goes to zero
highlighting the problem.)  Similarly, if one flow (or protocol) is
unable to achieve a high rate, Jain's index says it is "unfair" for
another to out-perfom it.  The harmonic mean correctly indicates that
rates  0.5 and 1  are better than rates 0.5 and 0.5 (but less good
than 0.75 and 0.75).

(Trying to maximise the harmonic mean of the rates is just a special
case of "utility maximisation", using  alpha=2 in Mo and Walrand's
alpha-fairness framework.  It could be argued that this utility
function is itself arbitrary, but it seems less so than summing
thoughput and "fairness".)

Combining throughput and fairness of throughput can be done
systematically, since they both just reflect the average rates.  A
bigger challenge is incorporating loss/delay and the other metrics
Wesley Eddy mentioned (stability, convergence time etc).  For file
transfers, it could be argued that these only matter insofar as they
affect the total transfer times.  This applies to both long- and
short-lived flows (but not to real-time flows).  However, there is
still a problem of how to weight the times:  The transfer time of each
short flow should get less weight than a long flow, but weighting them
in proportion to the amount of data may put too little weight on them.

Cheers,
Lachlan

--
Lachlan Andrew  Dept of Computer Science, Caltech
Phone: +1 (626) 395-8820    Fax: +1 (626) 568-3603

From: [email-masked] (Lachlan Andrew)
Date: Sat Feb  4 00:42:40 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]> <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

Greetings all,

On 03 Feb 2006 09:32:27 +0100, Michael Welzl <[email-masked]> wrote:
> So, the index should contain:
>
> * normalized throughput
> * loss
> * fairness (let's use the Jain Fairness Index)
>
> It could then look something like this:
>
> WI = (T*t + L*l + F*f) / 3
>
> where WI is "Welzl Index" (tm)   ;-)
> T is normalized throughput
> L is normalized loss
> F is the Jain fairness index (which is already a value
> in the 0..1 range)

A good way to summarise throughput and fairness is just to take the
*harmonic* mean of the flows' throughputs instead of the arithmetic
mean (or equivalently, the aggregate througput).  That corresponds to
measuring the mean time to transfer a given number of bytes, which is
the quantity actually observed by an application.

This metric avoids the arbitraryness both of using a sum or product,
with the problem of  selecting weightings, and also of Jain's index. 
(If one flow out of many is starved, Jain's index can still report
high "fairness", but the harmonic mean of rates goes to zero
highlighting the problem.)  Similarly, if one flow (or protocol) is
unable to achieve a high rate, Jain's index says it is "unfair" for
another to out-perfom it.  The harmonic mean correctly indicates that
rates  0.5 and 1  are better than rates 0.5 and 0.5 (but less good
than 0.75 and 0.75).

(Trying to maximise the harmonic mean of the rates is just a special
case of "utility maximisation", using  alpha=2 in Mo and Walrand's
alpha-fairness framework.  It could be argued that this utility
function is itself arbitrary, but it seems less so than summing
thoughput and "fairness".)

Combining throughput and fairness of throughput can be done
systematically, since they both just reflect the average rates.  A
bigger challenge is incorporating loss/delay and the other metrics
Wesley Eddy mentioned (stability, convergence time etc).  For file
transfers, it could be argued that these only matter insofar as they
affect the total transfer times.  This applies to both long- and
short-lived flows (but not to real-time flows).  However, there is
still a problem of how to weight the times:  The transfer time of each
short flow should get less weight than a long flow, but weighting them
in proportion to the amount of data may put too little weight on them.

Cheers,
Lachlan

--
Lachlan Andrew  Dept of Computer Science, Caltech
Phone: +1 (626) 395-8820    Fax: +1 (626) 568-3603

From: [email-masked] (Wesley Eddy)
Date: Fri Feb  3 14:30:24 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

On Fri, Feb 03, 2006 at 09:32:27AM +0100, Michael Welzl wrote:
> So, the index should contain:
> 
> * normalized throughput
> * loss
> * fairness (let's use the Jain Fairness Index)
> 
> It could then look something like this:
> 
> WI = (T*t + L*l + F*f) / 3
> 
> where WI is "Welzl Index" (tm)   ;-)
> T is normalized throughput
> L is normalized loss
> F is the Jain fairness index (which is already a value
> in the 0..1 range)
> 
> and t, l, f are weighting factors which decide how
> important the parameters are to us.
>
> ...

It would be nice to have a simple scheme, but I don't think that a simple
summation-based scheme is going to suffice.  In addition to the problems
Michael described with this simple scheme, here are a couple more:

1) no notion of how stability factors in
2) no notion of convergence rate
3) no notion of what happens to a mix of different types of flows
4) ranking is ambiguous in that it gives identical results for very differnt
   inputs

There are ways to cobble in or correct for these, but I don't know how to
meaningfully do it all at once.  In previous work on RED, Mark Allman and
I started with an index based on summation like the one you propose, and
we found problem 4 irritating.  We were only looking at two inputs to the
rating function -- utilization (U) and Jain's index (F), both from 0 to
1.  We decided that an index computed using  U^alpha * F^(1-alpha)
worked much better for our purposes, with alpha used to weight preferences.
This is described in a pretty obscure paper called "A Comparison of RED's
Byte and Packet Modes" from Computer Networks volume 42, issue 2, in June
2003.

-Wes

-- 
Wesley M. Eddy
Verizon Federal Network Systems
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060203/8f702c62/attachment.bin
>From [email-masked]  Fri Feb  3 14:28:16 2006
From: [email-masked] (Shivkumar Kalyanaraman)
Date: Fri Feb  3 14:34:40 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
Message-ID: <[email-masked]>

Folks,

BTW, what are the directions are we really interested in for this group?
- long BD products?
- loss tolerance in wireless?
- more robustness to variance in underlying links?
- fairness considerations (max-min/processor sharing vs proportional etc)?

Is there a priorization of relevant concerns? I only saw a broad wish list
in the original talks...

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

Risk comes from not knowing what you're doing   -W.Buffett

On Thu, 2 Feb 2006, Pei Cao wrote:

>
> > So, the panel isn't for several hours (at PFLDnet 2006) but one thing that
> > has become clear to me so far is that this community has not converged on
> > metrics and scenarios for evaluation.
>
> Precisely.  This actually IS the biggest problem right now...
>
> Pei
>
> _______________________________________________
> Iccrg mailing list
> [email-masked]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
>

From: [email-masked] (Filipe Abrantes)
Date: Fri Feb  3 15:40:48 2006
Subject: [Tmrg-interest] Re: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]> <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

Hi Michael,

before I agree with you, let me disagree for a bit :) .

Michael Welzl wrote:
> [cc'ing TMRG]
> 
> 
> Hi all,
> 
> I'm very happy to see some movement here. Clearly, many of us
> would want something concrete to come out of ICCRG, but how to
> reach agreement is the tricky bit.
> 
> 
> 
>>>I think a TCP benchmarking suite will be a very helpful tool to
>>>guide us in this process.  It will be useful especially in your
>>>Phase 3 to evaluate various proposals, but just thinking through
>>>the design and implementation of a good benchmark lends clarity
>>>to issues of Internet congestion control and metrics to optimize
>>>against.
>>>
>>>Aaron Falk is chairing a panel at a conference to discuss this
>>>very issue.  Hopefully, we wll hear from the participants soon
>>>on their thoughts.
>>
>>So, the panel isn't for several hours (at PFLDnet 2006) but one thing  
>>that has become clear to me so far is that this community has not  
>>converged on metrics and scenarios for evaluation.  The TMRG work is  
>>really needed to make progress.
> 
> 
> I have an overly simplistic proposal ... this is something I had
> in my mind for a long time, but I kept dismissing it again and
> again because it probably isn't feasible. Nevertheless, I'm now
> bringing it up as food for thought rather than a concrete
> suggestion:
> 
> Wouldn't it be great if we had a single "congestion control
> performance index" ? (or wait, before anybody agrees with me,
> let me call it "Welzl index" instead   :)   )
> 
> After all, it's not that much that we demand from a
> congestion control mechanism: it must avoid congestion
> while efficiently and fairly utilizing the available
> bandwidth, right? Congestion means that queues grow, leading
> to increased delay and eventually loss beyond a certain
> length (or depending on some AQM function); should the
> index then contain loss _AND_ delay? For simplicity, I'd
> suggest to ignore delay. Let's say we only have loss
> in the index, and someone comes up with a result that
> shows how good a mechanism is doing in a certain scenario,
> while in fact queues are growing - well, then it's a
> matter of changing the scenario just a little bit (more
> flows and/or shorter queues), and we have a case of
> "inadequate performance evaluation" (which we can always
> have).
> 

I have thought for a while why do we talk about "congestion control" 
when what all these mechanisms are responsible for, is a bit more than 
solely avoid congestion. Rate control would be a bit more accurate from 
my point of view. That said, I just wanted to disagree about leaving 
delay out of the metric. I didn't quite understood your explanation, but 
certainly a mechanisms that maintains a lower queue is better than one 
that maintains an higher queue (and note that there are mechanisms that 
maintain stable queues avoiding most of the packet drops).

Other than that I agree with you about the need of nice little index for 
uniform performance measurement.

br

-filipe

> So, the index should contain:
> 
> * normalized throughput
> * loss
> * fairness (let's use the Jain Fairness Index)
> 
> It could then look something like this:
> 
> WI = (T*t + L*l + F*f) / 3
> 
> where WI is "Welzl Index" (tm)   ;-)
> T is normalized throughput
> L is normalized loss
> F is the Jain fairness index (which is already a value
> in the 0..1 range)
> 
> and t, l, f are weighting factors which decide how
> important the parameters are to us.
> 
> Now the question would be how to appropriately set these
> factors... we'd have to decide on fixed values, I
> guess, or otherwise the simplification obtained with the
> index isn't really a simplification after all. Should
> t, l and f all be 1?
> 
> While I don't seriously believe that we can all just
> agree on the Welzl index, I believe that thinking in
> this direction of simplifying performance evaluations
> is worthwhile.
> 
> Just imagine what congestion control papers could look
> like if we had such an index... any comparisons could be
> more focused. Sure, all the usual scenarios would still
> have to be checked (dumbbell and beyond  :-)  ), but
> we'd reduce the problem space by one dimension - instead
> of showing loss, throughput, fairness etc., the Welzl index
> would be enough.
> 
> Cheers,
> Michael
> 
> _______________________________________________
> Tmrg-interest mailing list
> [email-masked]
> http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/tmrg-interest
> 

-- 
Filipe Lameiro Abrantes
INESC Porto
Campus da FEUP
Rua Dr. Roberto Frias, 378
4200-465 Porto
Portugal

Phone: +351 22 209 4266
E-mail: [email-masked]

From: [email-masked] (Radek Krzywania)
Date: Fri Feb  3 08:51:12 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <op.s4d2wnxlzxx9ui@edelweiss>

Hi all,
I am very glad that I can see any mails on that list, especially that they  
contain detailed work plan. I wish I could be on PFLDnet this year - it is  
going an interesting discussion out there. Anyway, I agree that the  
proposed work plan is quite aggressive, and it may be very difficult to  
fit into time schedule. Especially phase 2 and 3 will take more time that  
it is assumed in Keshav proposal. But we still have some current results  
with metrics, test proposals, test cases, etc. We need just to compile  
them carefully. But it will still take more time than assumed, I guess.

Best regards
Radek

On Fri, 03 Feb 2006 00:38:08 +0100, Steven Low <[email-masked]> wrote:

> Hi Keshav
>
> Your proposed steps make a lot of sense.  It seems a little too
> aggressive - great if we can make it.  In particular, Phases 2
> and 3 on developing a solutions will likely take more time if
> the goal is not just to sort out what proposals are available
> today and understand their tradeoffs, but to come up with something
> that is significantly better than the various proposals available
> today (each of which has limitations in some scenarios).
>
> I think a TCP benchmarking suite will be a very helpful tool to
> guide us in this process.  It will be useful especially in your
> Phase 3 to evaluate various proposals, but just thinking through
> the design and implementation of a good benchmark lends clarity
> to issues of Internet congestion control and metrics to optimize
> against.
>
> Aaron Falk is chairing a panel at a conference to discuss this
> very issue.  Hopefully, we wll hear from the participants soon
> on their thoughts.
>
> Steven
>

-- 
______________________________________________________________________
Radoslaw Krzywania       Network Research and Development
[email-masked]      Poznan Supercomputing and Networking Center
+48 61 858 20 28         http://www.man.poznan.pl
______________________________________________________________________

From: [email-masked] (Pei Cao)
Date: Fri Feb  3 14:11:12 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

> So, the panel isn't for several hours (at PFLDnet 2006) but one thing that 
> has become clear to me so far is that this community has not converged on 
> metrics and scenarios for evaluation.

Precisely.  This actually IS the biggest problem right now...

Pei

From: [email-masked] (Douglas Leith)
Date: Fri Feb  3 02:46:24 2006
Subject: [Iccrg] Proposal for ICCRG operations
References: <[email-masked]> <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

>So, the panel isn't for several hours (at PFLDnet 2006) but one thing  
>that has become clear to me so far is that this community has not  
>converged on metrics and scenarios for evaluation.  The TMRG work is  
>really needed to make progress.

Lets see what the panel outcome is, but maybe you're a little too pessimistic here.  

My impression is that there actually is really quite a good consensus of the broad framework for testing.  Tests by ourselves and the north carolina folks have converged to very similar setups and metrics.  There is even a common subset of tests that we have both been using and that also seem to have a wider ground-swell of support.  Fertile ground for TMRG acitivity.

Doug
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060203/aebed4ab/attachment.html
>From [email-masked]  Fri Feb  3 08:32:00 2006
From: [email-masked] (Michael Welzl)
Date: Fri Feb  3 08:36:16 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
	<[email-masked]>
	<[email-masked]>
Message-ID: <[email-masked]>

[cc'ing TMRG]

Hi all,

I'm very happy to see some movement here. Clearly, many of us
would want something concrete to come out of ICCRG, but how to
reach agreement is the tricky bit.

> > I think a TCP benchmarking suite will be a very helpful tool to
> > guide us in this process.  It will be useful especially in your
> > Phase 3 to evaluate various proposals, but just thinking through
> > the design and implementation of a good benchmark lends clarity
> > to issues of Internet congestion control and metrics to optimize
> > against.
> >
> > Aaron Falk is chairing a panel at a conference to discuss this
> > very issue.  Hopefully, we wll hear from the participants soon
> > on their thoughts.
> 
> So, the panel isn't for several hours (at PFLDnet 2006) but one thing  
> that has become clear to me so far is that this community has not  
> converged on metrics and scenarios for evaluation.  The TMRG work is  
> really needed to make progress.

I have an overly simplistic proposal ... this is something I had
in my mind for a long time, but I kept dismissing it again and
again because it probably isn't feasible. Nevertheless, I'm now
bringing it up as food for thought rather than a concrete
suggestion:

Wouldn't it be great if we had a single "congestion control
performance index" ? (or wait, before anybody agrees with me,
let me call it "Welzl index" instead   :)   )

After all, it's not that much that we demand from a
congestion control mechanism: it must avoid congestion
while efficiently and fairly utilizing the available
bandwidth, right? Congestion means that queues grow, leading
to increased delay and eventually loss beyond a certain
length (or depending on some AQM function); should the
index then contain loss _AND_ delay? For simplicity, I'd
suggest to ignore delay. Let's say we only have loss
in the index, and someone comes up with a result that
shows how good a mechanism is doing in a certain scenario,
while in fact queues are growing - well, then it's a
matter of changing the scenario just a little bit (more
flows and/or shorter queues), and we have a case of
"inadequate performance evaluation" (which we can always
have).

So, the index should contain:

* normalized throughput
* loss
* fairness (let's use the Jain Fairness Index)

It could then look something like this:

WI = (T*t + L*l + F*f) / 3

where WI is "Welzl Index" (tm)   ;-)
T is normalized throughput
L is normalized loss
F is the Jain fairness index (which is already a value
in the 0..1 range)

and t, l, f are weighting factors which decide how
important the parameters are to us.

Now the question would be how to appropriately set these
factors... we'd have to decide on fixed values, I
guess, or otherwise the simplification obtained with the
index isn't really a simplification after all. Should
t, l and f all be 1?

While I don't seriously believe that we can all just
agree on the Welzl index, I believe that thinking in
this direction of simplifying performance evaluations
is worthwhile.

Just imagine what congestion control papers could look
like if we had such an index... any comparisons could be
more focused. Sure, all the usual scenarios would still
have to be checked (dumbbell and beyond  :-)  ), but
we'd reduce the problem space by one dimension - instead
of showing loss, throughput, fairness etc., the Welzl index
would be enough.

Cheers,
Michael

From: [email-masked] (Aaron Falk)
Date: Fri Feb  3 00:00:00 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]> <[email-masked]>
Message-ID: <[email-masked]>

Hi Steven, Keshav-

On Feb 3, 2006, at 8:38 AM, Steven Low wrote:

> Your proposed steps make a lot of sense.  It seems a little too
> aggressive - great if we can make it.

I agree.  At this point, I'd say it is more important to focus on the  
steps than the schedule, though.

> In particular, Phases 2
> and 3 on developing a solutions will likely take more time if
> the goal is not just to sort out what proposals are available
> today and understand their tradeoffs, but to come up with something
> that is significantly better than the various proposals available
> today (each of which has limitations in some scenarios).
>
> I think a TCP benchmarking suite will be a very helpful tool to
> guide us in this process.  It will be useful especially in your
> Phase 3 to evaluate various proposals, but just thinking through
> the design and implementation of a good benchmark lends clarity
> to issues of Internet congestion control and metrics to optimize
> against.
>
> Aaron Falk is chairing a panel at a conference to discuss this
> very issue.  Hopefully, we wll hear from the participants soon
> on their thoughts.

So, the panel isn't for several hours (at PFLDnet 2006) but one thing  
that has become clear to me so far is that this community has not  
converged on metrics and scenarios for evaluation.  The TMRG work is  
really needed to make progress.

--aaron

From: [email-masked] (Steven Low)
Date: Thu Feb  2 23:45:04 2006
Subject: [Iccrg] Proposal for ICCRG operations
In-Reply-To: <[email-masked]>
References: <[email-masked]>
Message-ID: <[email-masked]>

Hi Keshav

Your proposed steps make a lot of sense.  It seems a little too
aggressive - great if we can make it.  In particular, Phases 2
and 3 on developing a solutions will likely take more time if
the goal is not just to sort out what proposals are available
today and understand their tradeoffs, but to come up with something
that is significantly better than the various proposals available
today (each of which has limitations in some scenarios).

I think a TCP benchmarking suite will be a very helpful tool to
guide us in this process.  It will be useful especially in your
Phase 3 to evaluate various proposals, but just thinking through
the design and implementation of a good benchmark lends clarity
to issues of Internet congestion control and metrics to optimize
against.

Aaron Falk is chairing a panel at a conference to discuss this
very issue.  Hopefully, we wll hear from the participants soon
on their thoughts.

Steven

S. Keshav wrote:

> A Proposal for ICCRG Operations
> ---------------------------------------------
> 
> The ICCRG Charter Document states (lightly paraphrased): "The key goal of
> ICCRG is to move towards consensus on which technologies are viable
> long-term solutions for the Internet congestion control architecture and
> what constitutes an appropriate cost/benefit tradeoff. ... Unfortunately, it
> is unclear at this stage whether any single solution is viable, or whether
> there needs to be a synthesis of ideas from many places."
> 
> To achieve the requisite clarity I propose the following phases.
> 
> Phase 1: Challenge document
> Target date: Preferably by end of Feb, but no later than March 20th (IETF
> Dallas date)
> 
> This document will outline the challenges faced by current TCP congestion
> control, and the requirements of any long-term solution for Internet
> congestion control.
> 
> Exit criterion: Consensus in this list that the document covers the bases.
> 
> Phase 2: Solution proposals
> Target date: By Fall IETF
> 
> We will broadcast a call to all contenders to submit a congestion control
> proposal. To make this reasonably efficient, the format of the submission
> will need to be agreed to and specified by this community.
> 
> Exit criterion: A document that surveys all contenders and presents them in
> standard format
> 
> Phase 3: Discussion
> Target date: Spring IETF 2007
>   
> The goal is to identify common themes and best practices in the proposed
> solutions as well as holes in coverage. Perhaps, we can use these to run a
> competition or bakeoff for the top spot, (which may require teams to
> collaborate or synthesize ideas).
> 
> Exit criterion:  A document that identifies the form of the best solution.
> 
> Phase 4: Consensus formation
> Target date: Fall IETF 2007
> 
> We will use this phase to clean up the preliminary solution and handle any
> issues than may come up in the previous phase.
> 
> Exit criterion: Creation of a document that recommends a 'best known
> solution'
> 
> I hope that this approach will result in a solution that is not only widely
> accepted by the community but has also been critically evaluated.
> 
> 
> Comments on this proposal are very welcome.
> 
> thanks
> 
> keshav
> 
> 
> 
> _______________________________________________
> Iccrg mailing list
> [email-masked]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
> 

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

From: [email-masked] (Douglas Leith)
Date: Thu Feb  2 14:26:08 2006
Subject: [Iccrg] status
Message-ID: <[email-masked]>

Mark,

Can I ask what the status of the congestion control research group is - what's the next step to move things on ?

Doug  

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://oakham.cs.ucl.ac.uk/pipermail/iccrg/attachments/20060202/63bb14be/attachment.html
>From [email-masked]  Thu Feb  2 22:51:44 2006
From: [email-masked] (S. Keshav)
Date: Thu Feb  2 22:58:08 2006
Subject: [Iccrg] Proposal for ICCRG operations
Message-ID: <[email-masked]>

A Proposal for ICCRG Operations
---------------------------------------------

The ICCRG Charter Document states (lightly paraphrased): "The key goal of
ICCRG is to move towards consensus on which technologies are viable
long-term solutions for the Internet congestion control architecture and
what constitutes an appropriate cost/benefit tradeoff. ... Unfortunately, it
is unclear at this stage whether any single solution is viable, or whether
there needs to be a synthesis of ideas from many places."

To achieve the requisite clarity I propose the following phases.

Phase 1: Challenge document
Target date: Preferably by end of Feb, but no later than March 20th (IETF
Dallas date)

This document will outline the challenges faced by current TCP congestion
control, and the requirements of any long-term solution for Internet
congestion control.

Exit criterion: Consensus in this list that the document covers the bases.

Phase 2: Solution proposals
Target date: By Fall IETF

We will broadcast a call to all contenders to submit a congestion control
proposal. To make this reasonably efficient, the format of the submission
will need to be agreed to and specified by this community.

Exit criterion: A document that surveys all contenders and presents them in
standard format

Phase 3: Discussion
Target date: Spring IETF 2007
  
The goal is to identify common themes and best practices in the proposed
solutions as well as holes in coverage. Perhaps, we can use these to run a
competition or bakeoff for the top spot, (which may require teams to
collaborate or synthesize ideas).

Exit criterion:  A document that identifies the form of the best solution.

Phase 4: Consensus formation
Target date: Fall IETF 2007

We will use this phase to clean up the preliminary solution and handle any
issues than may come up in the previous phase.

Exit criterion: Creation of a document that recommends a 'best known
solution'

I hope that this approach will result in a solution that is not only widely
accepted by the community but has also been critically evaluated.

Comments on this proposal are very welcome.

thanks

keshav