Random arrivals: the Poisson process
Requests, calls and packets rarely arrive on a neat schedule. Watch 37 requests reach a server at truly random moments, 4 per second on average: the gaps between them are exponential, the count in each second is Poisson, the process has no memory, and chance clumps build a queue even though the server is only 80% busy. Then see why many users look Poisson, and where real internet traffic does not.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01Requests arrive as a Poisson process at λ = 4 per second. What is the average gap between two arrivals?
The gaps are exponential with mean 1/λ. With λ = 4 per second, the average gap is 1/4 = 0.25 s, even though single gaps vary from a few milliseconds to over half a second.
02With λ = 4 per second, how likely is it that exactly 4 requests arrive in a given second?
The count in one second is Poisson with mean 4: P(N = 4) = e^(−4) × 4⁴ / 4! ≈ 0.195, about 20%. The average is the single most likely count, but most seconds have some other number.
03Nothing has arrived for 0.4 s. What can you say about how long until the next arrival?
The exponential gap is memoryless: P(T > s + t | T > s) = P(T > t). Independent users do not know how long it has been quiet, so the past wait tells you nothing about the remaining one.
04A server can handle 5 requests per second and requests arrive at random, 4 per second on average. Why do requests sometimes wait?
The server is busy 80% of the time (ρ = 4 ÷ 5), so on average it keeps up. But random times clump: 8 or more in one second happens about 5% of the time. During a clump a queue forms; with a fixed 0.2 s service the average wait is 0.4 s, while evenly spaced arrivals would never wait.
05What did Leland and colleagues (1994) find about measured Ethernet traffic?
Poisson counts smooth out over long windows (the spread is 50% of the mean per second at λ = 4, but only 5% per 100 s). The Bellcore Ethernet measurements looked equally bursty from milliseconds to minutes, so queues grow longer than a Poisson model predicts. User session arrivals, by contrast, are still well modelled as Poisson (Paxson and Floyd, 1995).
Glossary
- Arrival rate (λ)
- The average number of arrivals per unit of time, such as 4 requests per second. λ is the Greek letter lambda.
- Poisson process
- Arrivals that happen independently at random moments at a steady average rate λ. The count in a window of length t is Poisson with mean λt, and the gaps are exponential.
- Poisson distribution
- The chances of seeing 0, 1, 2, … arrivals in a window: P(N = k) = e^(−λt)(λt)^k / k!. Its mean and its variance are both λt.
- Exponential distribution
- The distribution of the gap between Poisson arrivals: P(gap > t) = e^(−λt), mean 1/λ. Short gaps are the most common.
- Memoryless
- The time still to wait does not depend on how long you have already waited. Among continuous distributions only the exponential has this property.
- Utilisation (ρ)
- The fraction of time a server is busy: arrival rate ÷ service rate, ρ = λ / μ. ρ is the Greek letter rho.
- Self-similar traffic
- Traffic whose bursts look alike at every time scale, so it stays bursty when counted over longer windows. Measured Ethernet and wide-area packet traffic behave this way.
Notes and sources
- The arrival times are one random draw (seeded generator, λ = 4 per second, 37 arrivals in 10 s); another draw gives different times with the same statistics.
- λ = 4 per second and the fixed 0.2 s service time are illustrative; all probabilities follow from them.
- The average wait of 0.4 s is the Pollaczek–Khinchine result for random arrivals and a fixed service time (M/D/1); with random service times (M/M/1) it would be 0.8 s.
- The tray shows at most 7 waiting requests; this sample never has more than 5.
- Self-similar traffic: Leland et al., IEEE/ACM Transactions on Networking 2(1), 1994; Paxson and Floyd, IEEE/ACM ToN 3(3), 1995.
- R. G. Gallager, Discrete Stochastic Processes, ch. 2 Poisson processes (MIT OpenCourseWare 6.262)
- M. Harchol-Balter, Performance Modeling and Design of Computer Systems (Cambridge, 2013), ch. 11
- Leland, Taqqu, Willinger, Wilson: On the self-similar nature of Ethernet traffic (IEEE/ACM ToN, 1994)
- Paxson and Floyd: Wide area traffic: the failure of Poisson modeling (IEEE/ACM ToN, 1995)
- L. Kleinrock, Queueing Systems, Volume 1: Theory (Wiley, 1975)
- ITU-D Teletraffic Engineering Handbook (V. B. Iversen, ed.)
Quiz Unlocks after the last step.