Why Poissonian traffic models matter more now than ever, part 4

In the course of describing one reason why Poisson traffic is so convenient, I’ll briefly discuss how to make things look Poissonian. It turns out that an arrival or point process $N_t$ with a well-defined rate $q$ can be rescaled to a unit-rate Poisson process. Papangelou, who along with Meyer obtained this result in the early seventies, put it in plain language:

Roughly, moving in $[0, \infty)$ so as to meet expected future points at a rate of one per time unit (given at each instant complete knowledge of the past), we meet them at the times of a Poisson process.

A proof using “elementary” methods is in “The Time-Rescaling Theorem and Its Application to Neural Spike Train Data Analysis” by Brown et al., and their statement of the time rescaling theorem is adapted below:

Let $0 < t_1 < t_2 < ... < t_n < t$ be a finite realization of a point process with a conditional rate function $q(t | \mathcal{F}_t)$ that is nonnegative on $(0, T]$ . Define $\tau(x) := \int_0^x q(s | \mathcal{F}_s) \ ds$ , and assume that $\mathbb{P}(\tau(t) < \infty | 0 < t \le T) = 1.$ Then the family $\{\tau(t_k)\}_{k=1}^n$ is a finite realization of a unit-rate Poisson process.

(Here the notation $\mathcal{F}_s$ just indicates the history of the process up to and including time $s.$ Technically it refers to the natural filtration of the process. More sophisticated treatments of the time rescaling theorem are given in Theorem 7.4.I and Proposition 14.6.III of Daley and Vere-Jones, 2nd. ed.)

Using the time rescaling theorem, goodness-of-fit tests like the Kolmogorov-Smirnov test can then be applied to evaluate a model characterization of a process. (It is left as an exercise for the reader to evaluate network traffic models in this way, since as far as I can tell nobody has done this yet.) A simple large-deviation result I’ll discuss below is in the same spirit, but is more applicable as the basis of an anomaly detection technique for computer network traffic.

The problem in practice with using the time rescaling theorem is that without a model, getting a reasonable estimate of an arrival rate is hard for anything but an inhomogeneous Poisson process with sufficiently slow rate variation. For slowly varying Poisson processes, all you have to do is divide the number of recent arrivals by a corresponding time window. The only subtlety here is the time windowing, and it’s a minor one.

(However, even in the case of a homogeneous Poisson process with a maximum-likelihood rate estimate, the rescaled process can be far from Poissonian when the estimation timescales are short enough or the number of observed arrivals is small enough. Even though the large number of packet or even flow arrivals should mean that this typically wouldn’t be a concern for most network traffic applications, it should still serve to highlight the essential practical difficulty present even in the simplest possible application of the time rescaling theorem. For more details, see Schoenberg’s paper “On Rescaled Poisson Processes and the Brownian Bridge”.)

Another nice thing about Poisson processes is that forming martingales from them is easy, for essentially the same reason: because the rate is well-characterized, the so-called compensator (essentially, the expected value of a random process as a function of time) is simple. Without getting into too much detail, a martingale is a bounded random process whose expected future value is always the same as its current value. Archetypal examples in discrete and continuous time are, respectively, the number of heads minus the number of tails in a series of fair coin flips and Brownian motion. Martingales are very powerful tools in probability theory, and the following result is just one illustration of this fact.

Let $N_t$ be a homogeneous Poisson process with rate $q,$ and let $M_t := N_t - qt$ be the corresponding martingale. By a result called the optional sampling theorem, you can get independent identically distributed (IID) random variables from $M$ by considering the martingale differences at regular intervals: i.e., the differences $\Delta_k := M_{kt} - M_{(k-1)t}$ are IID, with expected value zero. And from this point you can apply large-deviation theory, which details the asymptotic behavior of large sums of IID random variables.

A few standard calculations yield first that

$\Lambda(u) := \log \mathbb{E} \exp u M_t = (e^u - u - 1)qt$

and subsequently that

$\Lambda^*(u) := \sup_{v \in \mathbb{R}} \ (uv - \Lambda(v)) = (u + qt) \cdot \log \left(\frac{u}{qt} + 1\right) - u$

so that after a bit of algebra, a routine application of the Cramér large-deviation theorem results in the asymptotic estimate

$\mathbb{P}(M_{nt} > na) \overset{n \uparrow \infty}{\longrightarrow} \exp(-n\Lambda^*(a)) \equiv (x^{-x}e^{x-1})^y$

for $a > 0$ , where $x = \frac{a}{qt} + 1$ and $y = qtn$ . This gets really small really fast.

Behavior of large deviation probabilities. $10^{-14}$ is pretty small last time I checked.

Here’s the punchline: suppose you had the wrong idea about the nature of a putative homogeneous Poisson process $N$ (e.g., your estimate of the rate was poor or $N$ actually failed to be a homogeneous Poisson process in the first place). Then the resulting putative martingale would not actually be a bona fide martingale, and an otherwise improbable large deviation would detect this fact with high probability and with few false positives. Notice that while this sort of approach uses quite a bit of probability theory, it doesn’t require any actual statistics other than a trivial rate estimate and a threshold to determine what constitutes a large enough deviation. And the fact that network traffic is increasingly Poissonian means that such approaches will be increasingly robust.

In the next post in this series I’ll cover the practical details of this technique.

Appendix

In this appendix I’ll go through the calculations mentioned above. First,

$\mathbb{E} \exp uM_t = \sum_{k = 0}^\infty \mathbb{P}(N_t = k) \exp (u[k - qt])$

$= \exp(-uqt) \sum_{k=0}^\infty \frac{(qt)^k}{k!} \exp(-qt) \exp(uk)$

$= \exp(-[u+1]qt) \sum_{k=0}^\infty \frac{(qt e^u)^k}{k!}$

$= \exp(-[u+1]qt) \exp(qt e^u)$

$= \exp([e^u - u - 1]qt).$

Next, $D_v(uv - \Lambda(v)) = u - \Lambda'(v)$ , and the RHS is zero iff $u = \Lambda'(v) = (e^v - 1)qt$ , or equivalently $v = v_* := \log(\frac{u}{qt} + 1)$ . Now $\Lambda'' \ge 0$ identically by Cauchy-Schwarz, so

$\Lambda^*(u) = (u + qt) \cdot \log \left(\frac{u}{qt} + 1\right) - u.$

Finally, for $a > 0,$

$\exp(-n \Lambda^*(a)) = \exp \left( -n(a + qt) \cdot \log \left(\frac{a}{qt} + 1\right) + na \right)$

$= \left(\left(\frac{a}{qt} + 1\right)^{-(a + qt)} e^a\right)^n$

$\equiv (x^{-x}e^{x-1})^y$

where $x = \frac{a}{qt} + 1$ and $y = qtn.$ Note that for $a, qt, n > 0$ , it happens that $x > 1, y > 0$ and $f(x) := x(1 - \log x) \in (-\infty, 1)$ , with $f(1) = 1$ and $\lim_{x \uparrow \infty} f(x) = -\infty$ . Moreover, $f'(x) = -\log x < 0$ for $x > 1,$ so $(x^{-x}e^{x-1})^y = (e^{x(1-\log x) - 1})^y \in (0, 1)$ , providing a helpful sanity check on the large-deviation asymptotics above.

As an aside, an essentially identical result can be obtained in general via a Chernoff bound. Briefly,

$\mathbb{P}(M_{nt} \ge na) \le \inf_{v > 0} \left( \frac{\mathbb{E} \exp vM_t}{\exp av} \right)^n$

$= \inf_{v > 0} \exp (-n[av - \Lambda(v)])$

$= \exp (-n\sup_{v > 0}[av - \Lambda(v)])$

$= \exp (-n\Lambda^*(a)),$

where the last equality follows by convexity and the assumption that $a > 0.$

Like this:

Be the first to like this post.

This entry was posted on Tuesday, July 28th, 2009 at 00:37 and is filed under Communications security, Equilibrium Networks, Mathematics, Networks, Nonrandom bits. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to Why Poissonian traffic models matter more now than ever, part 4

Why Poissonian traffic models matter more now than ever, part 5 « Equilibrium Networks says:

3 August 2009 at 00:39

[...] matter more now than ever, part 5 To sketch how the large-deviation approach discussed in the last post can actually work, consider a process with conditional rate function 1 for the first arrivals and [...]

Reply
Martingales from finite Markov processes, part 1 « Equilibrium Networks says:

15 February 2010 at 04:02

[...] process (or in principle, at least, more general one-dimensional point processes) was outlined here and [...]

Reply

Equilibrium Networks