headers
Sireen Habib Malik | 1 Aug 2005 13:10
Picon
Favicon

Re: RTO Estimation... was "Agility..."

Hi all,

I have been thinking about David's emails and some points raised by 
Detlef in the background discussion. It's a learning process.

So ...there are some questions which I think are important in the 
context of this discussion.

We say that the RTT's distribution is heavy-tailed. However, the 
discussion on heavy-tailed sized files, the resultant LRD in the traffic 
and the sub-exponential queue occupancy distribution, is based upon  the 
"open-loop" queue anaylsis.

However, TCP is a "closed-loop" protocol (David's point).

The first set of questions then is, "what impacts the queue occupancy 
distribution more, the closed loop operation, or the heavy-tailedness of 
E2E distribution?", or, "under what loads/traffic conditions one of them 
is more dominant?" , or, "is there a dependency between them?".

Second point: It is clear that present RTO estimation will work in the 
frame of assumptions under which it is supposed to work. Like Detlef 
says, "nobody will complain that a car does not run if it is out of 
gas", so nobody should complain if RTO estimator does not work when 
traffic parameters do not fall inside the space of the relevant assumptions.

If that is true then one way to resolve this issue is to adjust/shape 
traffic in such a way that RTO should work (I think this is what Detlef 
is saying), or make a "general purpose" RTO estimator that 
reduces/relaxes the set of assumptions - ideally, it should work if IID
(Continue reading)

Permalink | Reply | 1 comment |
headers
Detlef Bosau | 1 Aug 2005 20:07
Picon

Re: RTO Estimation... was "Agility..."

Sireen Habib Malik wrote:

> 
> Second point: It is clear that present RTO estimation will work in the
> frame of assumptions under which it is supposed to work. Like Detlef
> says, "nobody will complain that a car does not run if it is out of
> gas", so nobody should complain if RTO estimator does not work when
> traffic parameters do not fall inside the space of the relevant assumptions.

And we should well consider the consequences, if it´s true that RTO
estimators 
actually don´t work, as Christian suggested. For the particular case of
mobile wireless networks, we would have to reconsider the whole work on
"spurious timeouts", because what´s called "spurious timeout" is perhaps
not the problem, but a symptom. Unduly often spurious timeouts are
nothing else 
than a too high probability for unwanted retransmissions, to remain in
the words chosen e.g. by Edge.

> 
> If that is true then one way to resolve this issue is to adjust/shape
> traffic in such a way that RTO should work (I think this is what Detlef

Exactly. In my post, I focussed solely on the routers. However, any
change in a router´s behaviour directly influences the traffic switched
by this.
Even more difficult: Influencing the traffic on a router will perhaps
not only affect this router, but the behaviour of other routers as well.
So, I´m not quite sure whether we are allowed to consider the router
queues as being decoupled.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Chris Edmondson-Yurkanan | 2 Aug 2005 23:33
Picon

Cerf & Kahn's Turing Lecture: Open to all, 8/22/2005


The Turing Lecture by Vint Cerf and Bob Kahn is OPEN TO ALL!

SIGCOMM 2005 is the host for this year's ACM Turing Lecture, and has  
opened
the Lecture beyond the conference attendees to ALL who are interested.
In addition, SIGCOMM will stream it live over the Internet that Cerf &  
Kahn
helped create.

* You are invited to attend the ACM Turing Lecture in Philadelphia, PA,  
US,
   August 22nd: 6:00-7:30 EDT (and join the reception which begins at  
4:30)
   at the Irvine Auditorium, University of Pennsylvania (free-of-charge)

   (with thanks to Penn's School of Engineering & Applied Science)

* Bring your colleagues, guests, students, advisors... and help Vint &  
Bob
   celebrate the first time that networking researchers have received  
this
   prestigious award, in the 39 years of the ACM Turing Award.

* The Lecture will be a moderated discussion between Vint and Bob, with
   the title:
   Assessing the Internet:
        Lessons Learned, Strategies for Evolution, and Future  
Possibilities
(Continue reading)

Permalink | Reply | 0 comments |
headers
Detlef Bosau | 3 Aug 2005 21:54
Picon

Re: Agility of RTO Estimates, stability, vulneratibilites

Christian Huitema wrote:
> I think we should just look at a simple question. Does the current
> algorithm actually works? 
> 
> I personally did measurements 6 years ago. The measurement of
> tcp-connect times to various web servers clearly showed a power law
> distribution. There is in fact a history of finding power laws in
> measurement of communication systems. In fact, Mandelbrot work on
> fractals started with an analysis of the distribution of errors on a
> modem link! Based on all that, it is quite reasonable to assume that the
> distribution of RTT measurement follows a power law. 
> 

Hm. I believe I remember some newspaper article, where the origin for 
the work on "the fractal geometry of nature" was the question: How long 
is the coast of England?

Shortly afterwards, we typically learn that a butterly in the Himalaya 
may cause a tornado in Europe.

When I attendet lessons in stochastics, I was told: When we think there 
may be a stochastic behaviour, we must consider where the stochastic 
behaviour is supposed to come from. Do we really _expect_ this 
behaviour? And why do we?

It´s the same with the whole thing of chaos theory, self similarity and 
its variations.

1.: What does it describe exactly? (I frequently miss precise definitions.)
2.: Where does chaotic/self-similar/.... behaviour come from? (It´s not
(Continue reading)

Permalink | Reply | 751 comments |
headers
S. Keshav | 3 Aug 2005 22:02
Picon
Picon
Favicon

Re: end2end-interest Digest, Vol 17, Issue 26

> I think of RED strategies, I remember a strategy where there
> are two thresholds a, b, a < b, for a queuelength q. If q < a, packets
> are accepted. If b < q, packets are rejected. If a <= q <= b packets are
> rejected randomly with a probality p which is linear increased from p=0
> if q=a to p=1 if q=b.
> 
> Question: Would it make sense to chose a and b that way, that
> i) q has a constant expectation and
> ii) q has a constand variance
> for certain periods of time?
> 
> 
> However, I expect that someone has discussed this before, it?s just too
> simple.
> 

The easiest way to make the queueing delay constant, or nearly so, is to
introduce wait times where the link is idle even though there are packets in
the queue. This reduces delay jitter in the system and makes the whole
network more circuit-like. By introducing new 'work', the system is what is
called 'non-work-conserving'. Such systems were studied extensively in the
early 90's. For more details, you should look up Hui Zhang's comprehensive
survey on scheduling: "Service disciplines for guaranteed performance
service in packet-switching networks" Proceedings of the IEEE, Volume 83,
Issue 10,  Oct. 1995 Page(s):1374 - 1396.

hope this helps

keshav
(Continue reading)

Permalink | Reply | 4 comments |
headers
Detlef Bosau | 4 Aug 2005 00:20
Picon

Re: end2end-interest Digest, Vol 17, Issue 26

S. Keshav wrote:
> 
> The easiest way to make the queueing delay constant, or nearly so, is to
> introduce wait times where the link is idle even though there are packets in
> the queue. This reduces delay jitter in the system and makes the whole
> network more circuit-like. By introducing new 'work', the system is what is

Exactly. And I´m not quite sure whether it´s that what I want to do.

> called 'non-work-conserving'. Such systems were studied extensively in the
> early 90's. For more details, you should look up Hui Zhang's comprehensive
> survey on scheduling: "Service disciplines for guaranteed performance
> service in packet-switching networks" Proceedings of the IEEE, Volume 83,
> Issue 10,  Oct. 1995 Page(s):1374 - 1396.
> 
> hope this helps

It exactly marks the problem.

The more circuit like a network is, the less are the economical 
advantages for typical "packet switching users".

When we make a delay´s _expectation_ constant for a certain amount of 
time, we can well accept a large variation. Jitter is not the problem. 
So, this could be overkill here. However, I don´t know of a "weaker" way.

In my other post from today (Augst, 3rd) I tried to weaken the problem 
that way, that I only ask for a limited forecast capability. It is not 
necessary to keep a queueing delay constant or makeing it obey a certain 
distribution. It would be sufficient to forecast its expectation, and if
(Continue reading)

Permalink | Reply | 3 comments |
headers
Craig Partridge | 4 Aug 2005 16:09
Picon

Re: Expected latency for a single hop


Is l a physical link, an IPsec or IP-in-IP tunnel, or ...?

Note that if it is a tunnel, the answer is that the expectation and
variance of latency is potentially the same as any random multi-hop
Internet path....

Craig

In message <42F20F14.3000007 <at> web.de>, Detlef Bosau writes:

>I posted this in another context yesterday, but perhaps, I should 
>isolate the problem to state it more clearly.
>
>Consider an arbitrary packet-switching network.
>
>Consider two adjacent nodes n1, n2 with link l in between
>
>n1--------------------------n2
>                l
>
>
>Consider a packet traveling the network, it´s path shall contain n1 and 
>n2 subsequently.
>
>Now, let
>  t1: packet´s arrival time on r1.
>  t2: packet´s arrival time on r2.
>
>Can we forecast expectaition and variance (if only for the _near_
(Continue reading)

Permalink | Reply | 0 comments |
headers
S. Keshav | 4 Aug 2005 16:30
Picon
Picon
Favicon

Re: end2end-interest Digest, Vol 17, Issue 26

Detlef,
    In general, what you are asking for is difficult. Consider the following
scenario. Suppose a router forecasts that the queueing delays at a
particular interface are small at time t and expects this forecast to hold
until t+200ms. Now, suddenly, a burst of packets from multiple input ports
destined to that interface arrive at time t+epsilon. This builds up the
queue, increasing delays. You have two choices:

1. violate the forecast
   or
2. drop packets in order to meet the forecast.

Neither one is a good alternative. If you violate the forecast, then what
use is it? If you drop packets to meet the forecast, that's a waste, because
adequate buffers exist. I do not think that dropping packets in order to
make RTO computations sane is a good tradeoff.

A similar situation holds if traffic is generally high, so that queue
lengths are large, and you forecast a large delay. Now, if the traffic dies
down, you have to either violate the forecast or add new work to the system.
Adding new work delays all subsequent packets, so if you now get a burst,
you are in trouble.

As such, I believe that any sort of forecast is only possible if there is a
way to bound the total incoming traffic, both in terms of rate and
burstiness. 

keshav

>
(Continue reading)

Permalink | Reply | 1 comment |
headers
David P. Reed | 4 Aug 2005 17:19
Picon

Re: Expected latency for a single hop

Detlef - Though it seems simple, your statement is about as complex as a 
problem can be.
This is the kind of problem statement that creates the definitional trap 
I was referring to in earlier discussions.   By construing the "latency" 
as being a propery of the "link" rather than of the network as a whole, 
the statement acquires  a misleading simplicity

The latency only is well defined for real packets that actually arrive 
and traverse the link.   Expectation and variance are properties of 
distributions, not packets.

There is no random process at all on the link itself (at least in the 
common case - there are links where the link itself has a random delay, 
but that usually arises where the link's physical characteristics vary 
faster and larger than the queue management and link pacing 
mechanisms).  The random process is the network environment that 
provides competing packets.  So the latency is everywhere but the link 
itself.

The other issue is that prediction is more reliable over a collection of 
packets, but a sufficient collection cannot happen in an instant.

The first order predictor is the queue size at the entry to the link.   
That's a very reliable predictor of latency for the next event.   But it 
provides very little input about variance (which depends entirely on 
packets arriving from elsewhere at "light speed").

I think there might be a much better (i.e. less complex to state) 
approach in NOT trying to start with the link and go by induction to the 
multilink case.   Instead, perhaps start with an end-to-end flow (over a
(Continue reading)

Permalink | Reply | 5 comments |
headers
Nicolas Christin | 4 Aug 2005 16:59
Picon

Re: end2end-interest Digest, Vol 17, Issue 26

Detlef, 

On Wed Aug 03, 2005, Detlef Bosau <detlef.bosau <at> web.de> wrote:
> 
> Do you think, there´s a way to do so, thereby maintaining the typical 
> "packet-switching best effort" nature of the Internet?
> 
> Perhaps, this is a borderline between "best effort" traffic shaping (if 
> this even exists) and some kind of guaranteed service. I really don´t 
> know yet.

I actually studied a very related problem in the good ol' days of my
Ph.D dissertation. I basically tried to combine buffer management and
packet scheduling to provide service differentiation without admission
control.

The trick is essentially that the bounds that you give to traffic
classes are actually soft, in that they can be violated. (Keshav is
completely right - when traffic is really bursty, it is very difficult
to do any type of intelligent predicition, and you might end up with
something that is not much better than best effort.) 

The good news is that you can do quite a lot if you combine scheduling
with packet dropping, and even more when you start looking at ways to
playing with TCP congestion control to do essentially endpoint admission
control for you.

If you are interested, a summary of my dissertation is in:

N. Christin and J. Liebeherr.
(Continue reading)

Permalink | Reply | 0 comments |

Gmane