Subject: Re: [ippm] concatenation of QoS parameters

From: "H.E.Holland" <[email-masked]>
Date: Tue, 17 Sep 2002 23:40:19 +0200

Dear all, 

I found this discussion about concatenating parameters from a while back.
Little is said however about concatenating distributions. For example, I
asume that I can simply add medians of delay samples for adjacent
independently measured links. And the percentiles. Is this correct? The
mail below speaks of one-way delay "averages" being added over various
domains where average signifies "mean", but mean "can't" be calculated
(officially anyway) since losses aren't acounted for. 

Thanks,
Henrik.

At 12:03 14-2-02 -0500, stanislav shalunov wrote:
>This is probably outside of scope of IPPM WG activities (and in the
>realm of a statistics), but: Everything hinges on the assumption of
>independent distribution of the delay variables for different domains.
>On one hand, since the next domain doesn't explicitly know about
>treatment in the previous one you could say that the independence
>assumption should be true.  On the other hand, if there exist global
>congestion oscillation phenomena (and why wouldn't they?) the
>assumption would be incorrect.
>
>Further, you do not specify your metrics.  Averages, for example,
>would be much easier to analyze in this way than medians.
>
>Victor Reijs <[email-masked]> writes:
>
>> . OWD. I assume, I can just add figures in case of concatenation of
>> domains.
>
>Sum is correct for averages regardless of independence.
>
>> . IPDV. This is a difficult one. I would tend to say one can not just
>> added the figures. I once heard a convolution is needed here. What are
>> your ideas?
>
>Sum is correct for variances provided that there is independence.
>
>> . IP Packet Loss.
>
>Loss probability, assuming independence, is, of course, 1-\Pi(1-p_i).
>Accidentally, for small values of p_i the first order approximation of
>this quantity happens to be \Sigma p_i.
>
>> . IP Loss patterns.
>
>No numeric parameter.
>
>> . IP packet reordering:
>
>No defined metric and no defined model.
>
>> The above was for the millisec range, perhaps other ideas are needed
>> in microsec range.
>
>Scale doesn't matter.
>
>-- 
>Stanislav Shalunov		http://www.internet2.edu/~shalunov/
>
>"You wake me up early in the morning to tell me I am right?  Please
>wait until I am wrong."	-- John von Neumann, on being phoned at 10 a.m.
>_______________________________________________
>ippm mailing list
>[email-masked]
>http://mailhost.advanced.org/mailman/listinfo/ippm
>

_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: "Alan Clark" <[email-masked]>
Date: Tue, 17 Sep 2002 21:21:03 -0400

My apologies for restating the obvious, if already stated .. typical traces
of loss and jitter are clearly non-stationary.

Jitter often appears to have a roughly constant "background" level with
superimposed short term delay variations (100mS to several seconds) due to
transient congestion on LAN and access links.

Network packet loss is due to transient congestion, route changes, link
failures and similar events.  Contrary to popular belief, bursts are often
long and sparse - e.g. several seconds of 20% loss - rather than the short
bursts of consecutive loss often described.  For multimedia applications
this is a critical distinction as long bursts of 20-30% loss can be more
objectionable than short dense loss periods.

If you assume that both loss and jitter have some fairly constant background
rate/ level with transient events then it would seem to be necessary to
separately combine the background and transient parameters.

e.g. for packet loss:

(i) compute gap/background loss probability using independence assumption

(ii) compute burst probability, assuming that the probability of bursts
occurring on network segments is independent, and combine burst
density/length stats.

Alan Clark

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On Behalf
Of H.E.Holland
Sent: Tuesday, September 17, 2002 5:40 PM
To: stanislav shalunov; [email-masked]
Cc: IPPM Working Group
Subject: Re: [ippm] concatenation of QoS parameters

Dear all,

Thanks,
Henrik.

---

From: Kave Salamatian <[email-masked]>
Date: Wed, 18 Sep 2002 07:41:06 +0200

I agree with Alan about the structure of losses. Losses can be described by
period of high loss probability followed by period of low loss probability.
This is explained in "Hidden Markov Modeling for network communication
channels, M.R Salamatian, S. Vaton, SIGMETRICS 2001, Cambridge,
Massachusett." (can be downloaded from www-rp.lip6.fr).

For delay we have a similar description. That is under writing.

However I don't agree with Alan about Non stationnarity at all scales.
Globally speaking, stationarity cannot be proven of disproven when you work
with empirical data. Stationarity is only a property of the model that you
decide to use and that is best suited to your application. In fact
stationarity is a bet about the fact that what you have observed into your
observation window will be reproduced (with same statistical parameters) out
of the observation window.

A single observation may be described as well by a stationnary model as  a
non stationnary. If one go for a stationnary model he may have to manage
Long Range dependences that will be necessary to explain mean level
variation. If he go for non stationarity he need to track the change of the
underlying process, but he may use short memory model with memory scale at
the level of his tracking agility. Which one is better depend on the
application !

Meaning that loss and jitter are not non-stationnary by essence, but they
may be subjectively stationnary or not.

Kave Salamatian

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]]De la part
de Alan Clark
Envoye : mercredi 18 septembre 2002 03:21
A : H.E.Holland; stanislav shalunov; [email-masked]
Cc : IPPM Working Group
Objet : RE: [ippm] concatenation of QoS parameters

e.g. for packet loss:

Alan Clark

-----Original Message-----

Dear all,

Thanks,
Henrik.

---

From: "Alan Clark" <[email-masked]>
Date: Wed, 18 Sep 2002 06:58:36 -0400

Kave

I had some difficulty finding the paper you reference on the lip6 web site -
please verify it's location.  My IPtel 2001 paper describes the use of a 4
state Markov Model for describing burst packet loss distribution and may be
of interest to you

 http://www.iptel.org/2001/pg/final_program/21.pdf

Whilst I have to agree with your philosophical observation concerning
stationarity I think you are agreeing that traces do show transient packet
loss and short term delay changes. The main subject of the posting was to
address the issue of how you would combine QoS parameters from two network
segments - it would be intersting to hear your views on this

Regards

Alan

-----Original Message-----
From: Kave Salamatian [mailto:[email-masked]]
Sent: Wednesday, September 18, 2002 1:41 AM
To: Alan Clark; H.E.Holland; stanislav shalunov; [email-masked]
Cc: IPPM Working Group
Subject: RE: [ippm] concatenation of QoS parameters

Kave Salamatian

-----Message d'origine-----

e.g. for packet loss:

Alan Clark

-----Original Message-----

Dear all,

Thanks,
Henrik.

---

From: Kave Salamatian <[email-masked]>
Date: Wed, 18 Sep 2002 13:38:32 +0200

Sorry for the incomplete url. The complete one is www-rp.lip6.fr/~salamat.

For the question about how combining QoS parameter from two network segments
it is indeed difficult. If you can suppose that the network segment are
independent you may combine the Qos measure. But if they are dependent you
may not combine them easily as the moement of the combinaison of two
dependent Random variable is not straightforwardly a simple combinaison of
the individual moments. Meaning that in a general scenario (without
independence hypothesis) you may not be able to easily combine QoS parameter
from two networks.

Bests

kv

-----Message d'origine-----
De : Alan Clark [mailto:[email-masked]]
Envoye : mercredi 18 septembre 2002 12:59
A : Kave Salamatian; H.E.Holland; stanislav shalunov;
[email-masked]
Cc : IPPM Working Group

Kave

Regards

Alan

-----Original Message-----
From: Kave Salamatian [mailto:[email-masked]]
Sent: Wednesday, September 18, 2002 1:41 AM
To: Alan Clark; H.E.Holland; stanislav shalunov; [email-masked]
Cc: IPPM Working Group
Subject: RE: [ippm] concatenation of QoS parameters

Kave Salamatian

-----Message d'origine-----

e.g. for packet loss:

Alan Clark

-----Original Message-----

Dear all,

Thanks,
Henrik.

---

From: Philip Chimento <[email-masked]>
Date: Wed, 18 Sep 2002 08:05:46 -0400

Once again: means may always be combined (added or in linear combinations) 
whether or not the underlying random variables are independent. As Stanislav 
pointed out, variances must be of independent random variables to be able 
simply to add them. While Stanislav's statement is correct on this point, it 
does not apply to either IPDV or delay in successive segments in a real 
network. While you can build a model based on this assumption, your model will 
at best only approximate the real situation (and you must then work on 
bounds). I would NOT recommend trying to write an SLA based on higher moments 
or distributions of combinations of delay or IPDV.

Regards, Phil Chimento
-- 
Phil Chimento             Ericsson IPI
Phone: 240-314-3597	  7301 Calhoun Place
[email-masked]   Rockville, Md. 20855
-----------------------------------------------------

---

From: stanislav shalunov <[email-masked]>
Date: 21 Sep 2002 09:30:39 -0400

"H.E.Holland" <[email-masked]> writes:

> independently measured links. And the percentiles.

You *cannot* add medians, etc.  For that, you'll have to do a
convolution (which requires both complete distributions, not just one
or five percentiles).

Sex is the mathematics urge sublimated.                 -- M. C. Reed.
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: "H.E.Holland" <[email-masked]>
Date: Sat, 21 Sep 2002 23:38:46 +0200

Hi Matthew,

So I guess one of the hardest parts is acquiring of "fitting" a complete
distrubution function. How would you do this? Furthermore, maybe a Laplace
transformation to make calculations easier?

Henrik.

At 09:58 18-9-02 -0400, you wrote:
>Hi,
>
>its actually quite tricky. The simplest case is where you know the 
>distribution functions (or can fit simple distribution functions) and 
>then you integrate to do the convolution.
>
>Mathematically, if you are taking the sum X = X_1 + X_2 (where X_1 and 
>X_2 are non-negative), the distribution function of X is
>	F(T) = p(X<=T)
>	     = int_0^T P(X_1 <= S) P(X_2 <= T-S)  dS
>	     = int_0^T F_1(S) F_2(T-S) dS
>where F_1 and F_2 are the distribution functions of X_1 and X_2.
>
>There are neat ways to compute these for some distributions by taking 
>the characteristic functions of the distributions. There are also 
>special cases like the Gaussian distribution where the distribution is 
>completely characterized by the mean and variance so adding independent 
>RVs is easy.
>
>I assume you can do the integral above numerically for empirical 
>distributions, but I don't have any experience doing that, and don't 
>know what the numerical issues are, but you had better have fairly good 
>data before you try something like that.
>
>Matt
>
>H.E.Holland wrote:
>> Matt,
>> 
>> Can you tell me from a practical point of view how I do this? With the
>> normal discrete time convolution sum?
>> 
>> Henrik.
>> 
>> At 21:28 17-9-02 -0400, you wrote:
>> 
>>>No, you can't add medians or other percentiles. You have to convolve the 
>>>distributions.
>>>
>>>Matt
>>>
>>>H.E.Holland wrote:
>>>
>>>
>>>>Dear all, 
>>>>

---

From: Philip Chimento <[email-masked]>
Date: Tue, 24 Sep 2002 08:56:04 -0400

Henrik: 
Fitting distributions is equally tricky. There are many different 
statistical tests to use for fitting distributions, but in general 
it is an art of approximation. Further if you have purely empirical 
distributions, Laplace transforms won't help. If you fit the data to
a known distribution (approximately) and convolve the known distribution
then you will get an approximate answer. But, remember, if the distributions 
are not independent (and they are NOT in this case) you have a more 
complicated convolution integral than the one that Matt gave you. In that
case, you wind up with an integral that looks like (for Z = X+Y, the sum of 
only two random variables)
f(z) = int_0^infinity{f(s, z-s) ds} to get the density (see, Trivedi, 
Probability & Statistics with Reliability, Queueing and Computer Science 
Applications for the derivation). Note that the bivariate function (f(x,y)) 
does not resolve into a product of the marginals because they are not 
independent. Basically, if you don't fit a distribution function, you have to 
compute this numerically.
Regards, Phil Chimento
-- 
Phil Chimento             Ericsson IPI
Phone: 240-314-3597	  7301 Calhoun Place
[email-masked]   Rockville, Md. 20855
-----------------------------------------------------

---

From: Matthew Roughan <[email-masked]>
Date: Tue, 24 Sep 2002 09:29:35 -0400

All good points. Particularly as delay distributions can easily be 
multimodal, and fitting such distributions can be challenging.

Matt