Subject: Re: Loss patterns,

From: Darryl Veitch <[email-masked]>
Date: Thu, 12 Aug 1999 20:28:25 +1000 (EST)

Let me try to answer these questions briefly myself.

From: "Mike Borella" <[email-masked]>

**  How do you mean 'independent'?  Uncorrelated? 
I am suggesting a model where they are independent, based on an analysis which looks
at covariances.   Of course they are not truly independent, but the idea is that if
such a simple model can be of use, let's be glad..

**  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)?
If I understand what you mean, yes.  In this model if you isolate either
of the losses or the arrival 'bursts' as discrete time series  L(k) and A(k) 
where L(k) is the # of losses in the kth loss burst, and similarly for A, then
both of these would be iid processes.

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

More work needs to be done here.  What we did was to first attempt to isolate
long segments of traces which appeared stationary.  Although parameters varied,
for such segments the model structure seemed to apply well.  
The values of the parameters 
changes though.  Naturally a parameterl-ess model, 'universal traffic', would
be a lot to ask for.. 
 As for 'parameters of parameters', this is what we do all the time really.

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

That sounds reasonable.  Our 'stationary' hunting would tend to exclude these 
worst excesses, which could be modelled separately, or but adding a pareto tail
of low mass to the loss burst distribution, or perhaps just some mass at a single
large value-  depends what you need to model.

From: Andy Scherrer <[email-masked]>

**  > 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. 
**  
**  But in what proportions?  Of course, that's a question you ask of the
**  data, but in a sequence whose beginning and end are difficult to define,
**  the time scale becomes an issue. And so while loss of one packet may not
**  be dependent on loss of any other packet, there is dependency on time
**  scale, since it will probably matter if you're looking at such proportions
**  in 3 sec bursts vs. 30 sec or 3 min bursts.

I am not sure what you mean by 'proportions'.  When I say alternate I mean that.
In the analysis all proportions were looked at via the cross correlation of the
two burst series, which was very low.

**  > 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. 
**  
**  But note that using a simple univariate exponential distribution for A
**  implies a Poisson distribution. This group has discussed problems with
**  Poisson modelling of these data. That is not to say it shouldn't perhaps
**  be discussed more, perhaps with some thought to heirarchical modeling of
**  the Poisson parameter (lambda) -- that would be one approach for
**  addressing the time issue I mentioned above. 

The overall process I describe is not Poisson, although it is short range 
dependent of course.  (paradoxically, we did see some evidence of LRD, I believe
that it is there sometimes but is of low 'power'  (low mass in tail).

**  > With this underlying model the probability of obtaining patterns such as
**  > 111011, or any others, is easily calculated. 
**  
**  Well, I submit that there are actually a suite of underlying models to
**  consider. A binary outcome such as your example can result from one of
**  many distributions, each of which thinks of the "question" in a different
**  way. 
**  
**  For example, if you think of it as Binomial problem (a series of
**  Bernoulli[0-1] trials), you have a fixed, known number of trials (N), 
**  and model the proportion out of N that are 1 (or 0).
**  
**  However, another way of looking at the _same_ data could be "How many
**  trials (packets) do I see before I observe a 1"? Doing this repeatedly
**  might give a set of data consisting of sequence lengths.
**  
**   ...which is different from "How many trials (packets) do I observe before
**  I can count some number C of 1s?" This can also give data consisting of
**  sequence lengths, but counted differently. 

I believe that the framework I described, ie packet k is missing or not, is in some
sense the 'primitive process' from which all these alternately viewpoints can be
deduced.   The converse however is not always true.

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

I agree that on links with low multiplexing, that extreme events are more likely
and other models would be better.  On the other hand large bursts could be modelled,
perhaps successfully, by adding a new parameter which gives a reasonable mass to 
some large burst size.  Of course this flies in the face of the ethos of scaling 
(fractal) behaviour, god forbid that I should be saying this myself!

Darryl 

+-------------------------------+------------------------------------------+
|      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: Vern Paxson <[email-masked]>
Date: Fri, 13 Aug 1999 00:38:50 PDT

Just a note of something to keep in mind: while studies have generally
found loss patterns independent for packets spaced hundreds of msec or
more apart, on finer time scales losses can be strongly correlated.  E.g.,
in my packet dynamics study the probability that a TCP packet is lost given
that its predecessor was lost was 5-8 times larger than if its predecessor
was not lost.  This will likely change with wide deployment of RED: but
it argues for caution when applying models based on independence of loss.

		Vern

---

From: Darryl Veitch <[email-masked]>
Date: Fri, 13 Aug 1999 18:54:24 +1000 (EST)

Whilst not wishing to imply that the model I suggested, based on UDP observations, is
relevant for TCP,  note that it is Not an iid model, and is rich enough to 
include the conditional probabilities you mention.

Essentially the probability of loss given that one is within an arrival burst is 
governed by the residual life distribution relating to the distribution A, whereas 
if one assumes that the previous packet was lost, then one is within a loss burst by
definition and the residual life of L governs the probability.  They are therefore not
the same in general.    Although the model has a lot of 'independence' in it, it is
far from an iid model, being an alternating renewal process. 

Darryl

**  From [email-masked] Fri Aug 13 18:32 EST 1999
**  To: Darryl Veitch <[email-masked]>
**  Cc: [email-masked], [email-masked], [email-masked]
**  Subject: Re: Loss patterns, 
**  Date: Fri, 13 Aug 1999 00:38:50 PDT
**  From: Vern Paxson <[email-masked]>
**  
**  Just a note of something to keep in mind: while studies have generally
**  found loss patterns independent for packets spaced hundreds of msec or
**  more apart, on finer time scales losses can be strongly correlated.  E.g.,
**  in my packet dynamics study the probability that a TCP packet is lost given
**  that its predecessor was lost was 5-8 times larger than if its predecessor
**  was not lost.  This will likely change with wide deployment of RED: but
**  it argues for caution when applying models based on independence of loss.
**  
**  		Vern
**

---

From: Vern Paxson <[email-masked]>
Date: Fri, 13 Aug 1999 23:20:26 PDT

> Whilst not wishing to imply that the model I suggested, based on UDP
> observations, is relevant for TCP,  note that it is Not an iid model, and
> is rich enough to include the conditional probabilities you mention ...
> ... being an alternating renewal process.

Ah!, got it - that's a model I like, it strikes me as a good approximation.
Note that in my packet dynamics study, the distribution for ON-times for
ack loss periods had a clear Pareto tail with infinite variance - definitely
an important property to keep.

		Vern