Unnecessary mathematics: queuing delay for two types of network traffic

This morning I asked myself what I thought was an interesting question:

  • If there are two types of traffic in a network, where one is much less common than the other, will the two types experience different queuing delays?

If you have more common sense than me, you’ve already figured out that the answer is “No.” But it took me about an hour to figure this one out.

I designed a simple model of the scenario: there is a queue of N packets, and one of them is of a different type than the rest. Let’s call the two types A and B.

We can assume that the position in the queue reflects the queuing delay of the packet, so then we only need to be interested in the average position in the queue for each type of traffic: E[P(A)] , and E[P(B)].

We assume that there are N-1 packets of type A, and one packet of type B. We can place the type-B packet at any of the N positions in the queue with equal probabilities:

  • E[P(A)] = \frac{1}{N} \sum_{i=0}^{N-1} \left( \frac{1}{N-1} \left( \left( \sum_{j=0}^{N-1} j\right) - i \right) \right)
  • E[P(B)] = \frac{1}{N} \sum_{i=0}^{N-1} \left( i \right)

The term summed in the formula for E[P(A)] represents the average position of all N-1 type-A packets. In E[P(B)], there is only one packet so the term doesn’t need another sum inside of it.

Well, it turns out that E[P(A)] and E[P(B)] both simplify to \frac{N-1}{2}.

This should be immediately obvious in the formula for E[P(B)], and it takes just a little more work to derive for E[P(A)]. Yep, it couldn’t have been simpler.

If you think about it, this result makes a lot of sense and I shouldn’t have needed to compute it — if I’m at a random position in line, then so is everyone else. So it doesn’t matter whether I’m averaging over a group of N-1 people, or only worrying about myself. We’ll all wait the same amount of time (on average, of course).

Published by

Travis Mick

Travis is the chief architect of systems and software at Zeall.us. A background in network security research has fostered in him a passion for values such as digital privacy, net neutrality, and intellectual freedom. In a world where these causes are increasingly important, he aims to both raise awareness of them and further their goals through technology.

Leave a Reply