Subject: Re: Loss patterns, Re: minutes for IPPM WG, 13 July 1999

From: "Mike Borella" <[email-masked]>
Date: Tue, 10 Aug 1999 09:52:58 -0500

How do you mean 'independent'?  Uncorrelated?  Doesn't independent
mean that the arrival and loss burst processes would both be well modeled as
geometrically-distributed (at least in the Bernoulli sense)?

And how do the parameters vary over different times of day, days of week,
time scales and paths?  While the general model of a binary Markov chain
can be used to model this sort of process, if the parameters are all over the
map,
the model may not be very useful in practice.  With any luck the parameter
values can be ranged based on some physical observations.

I performed a simple analysis of UDP loss patterns a couple of years back on
6 months of data across 3 paths.  On all three paths, loss bursts fit a Pareto
better than anything else I tried.  The interesting thing was that bursts of 10
or
less packets lost always had to be modeled differently that bursts of about 15
or
greater.  Given the time scales involved (about 30 ms between packets) it seemed
as if the shorter loss bursts were caused by transient congestion while the
longer
bursts (up to and exceeding 1000's of packets) were cause by a more serious
outage such as downtime or a reboot.

-Mike

Darryl Veitch <[email-masked]> on 08/10/99 02:58:31 AM

Sent by:  Darryl Veitch <[email-masked]>

To:   [email-masked]
cc:    (Mike Borella/MW/US/3Com)
Subject:  Loss patterns,     Re: minutes for IPPM WG, 13 July 1999

Hello all,

In a recent mail from Will Leland on the meeting in Oslo, the following comment
was made:

&&&&&&&&&&&&&&&&&&&&&&&&
"  There was also a discussion about the fact that a burst loss
is considered terminated by a single good packet arrival.
A burst followed by a single good packet and another burst
would seem to be better characterized as one long burst.
Will noted that what is being measured could provide the
raw data for constructing a "less sensitive" metric.
Would some sort of "errored period" be a meaningful thing
to define?  "
&&&&&&&&&&&&&&&&&&&&&&&&

Two students and I did some work last year looking at characterising
the loss process in detail.
One of the issues to clarify was precisely this one of, 'ok losses tend to occur
in small groups, but what about patterns such as  111011 ?
The results we obtained were quite surprising. We found that the structure of
losses
in UDP test packet streams (send out either as Poisson or with constant
separation)
was extremely 'independent', in fact looking like an alternating renewal process
in most cases we observed (~100 experiments over 15 routes in 8 countries).

That is, take two random variables  L (Loss) and A (Arrival).
 To a good approximation the loss process consisted in simply
taking sample values alternately from L and A, in an independent fashion.
This offers the prospect of a simple description of the loss process consisting
of a discrete probability distribution for L (with most of the mass on 1, 2 or 3
losses), and an exponential distribution for A.
With this underlying model the probability of obtaining patterns
such as 111011, or any others, is easily calculated.

I know it is late days as far as the RFC is concerned, but I think that such a
description could be of use.   I will be taking up this work in more detail in
coming months.    Sue Moon presented similar finding at Infocom this year.

The paper appeared in Globecom 98 and can be downloaded from
 http://www.serc.rmit.edu.au/~darryl     (paper at the bottom)

Darryl Veitch

+-------------------------------+------------------------------------------+
|      Dr. Darryl Veitch      | Email:   [email-masked]         |
|      Senior Research Fellow   |                                          |
|      S.E.R.C.                 | Telephone:                               |
|      110 Victoria St          |        Direct-   +61 3 9925 4014         |
|      Carlton 3053             |     Inquiries-   +61 3 9925 4013         |
|      GPO Box 2476V            |                                          |
|      Melbourne                | Fax:             +61 3 9925 4094         |
|      Victoria 3001            |                                          |
|      Australia                | Web: http://www.serc.rmit.edu.au/~darryl |
+-------------------------------+------------------------------------------+

---

From: kavé Salamatian <[email-masked]>
Date: Tue, 10 Aug 1999 18:10:16 +0200

Hello,

about this problem of loss patterns, we had also some measure. It seems that for
paths that are shared between large number of transmission, we can use with good
confidence Markovian model such as Elliot-Gilbert  or simple model as noticed by
Darryl, but for links that have not a such an important number of concurrent we can
see very large burst separated by large period of smaller burst. I think that
the burst pattern has things to do with the statistical multiplexing of concurrent
traffics over the link. This was pointed out in simulation by Bolot & al in a paper
"on the  relevance of long range dependence to packet loss in Internet" (I am not
sure of the title of the paper). Then it is not atonishing that the measure of Mike
gives different result from the measure of Darryl. It should be noticed that the
large deployment of RED based router will more bias the Darryl type of observation.

Another interesting things is that we have tried to modelize loss process by some
Semi Markov process, (for the case of large concurrency over the link it reduce to
Markov process). But in most case the Markov chain reduce to only two states. In
fact adding a third, or fourth state does not give much more to the quality of the
model. We cannot says what we see this state aggregation.

Any Idea.

*-------------------------------------------------------------------------------------------------------

Kave Salamatian                                                  [email-masked]
LRI, URA 410 CNRS
U. Paris SUD
91405 ORSAY
France

---

From: Andy Scherrer <[email-masked]>
Date: Tue, 10 Aug 1999 12:27:53 -0500 (CDT)

> How do you mean 'independent'?  Uncorrelated?  

Good question; I took it to mean that any packet behaves in a way that is
_not_ more predictable based on information you might have about other
packets in the stream, particularly its neighbors. 

> Doesn't independent

No, that's sort of backwards. 
As I suggested in an earlier response, many distributions can be used to
model this system, and they all actually assume that samples elements are
independent. 

I believe the property you're thinking of re: Geometric-distributed (and
exponential) data is that of "memorylessness", which is different than
independence. 

Whether that is apt for a model of this sort of system, I'm not yet
convinced. 

> time scales and paths?  

In other words, the parameters of the distribution themselves have
parameters! There has been some work on this, particularly a paper given
at Interface '98 (I forget the author). Modeling changing parameters of,
say, a Poisson distribution does show promise in being useful. 

> While the general model of a binary Markov chain
> map, the model may not be very useful in practice.  With any luck the
> parameter values can be ranged based on some physical observations.

Please note that elements of a Markov chain are explicitly _not_
independent. In Markov chains, the dependency relationship is merely
restricted, so that, e.g., all the information about the past that is
important to element t is contained in element t-1 (or something that
reduces to that). And so if you know elements t and t-1, you don't gain
anything by considering t-2.

> outage such as downtime or a reboot.

Yes, that _is_ very interesting. How much did you learn about what
qualifies for "short" and "long"? I imagine that depends on many different
factors as well.

Andy Scherrer
Statistician
Matrix Information and Directory Services, Inc.
1106 Clayton Lane, Ste. 501W, Austin, TX 78723
http://www.mids.org/
+1-512-451-7602