2.1.1 The Importance of Queuing

In a switch, packets are stored in buffers (queues) while waiting to be processed. Queuing theory allows us to predict:

• How long a packet will wait (Delay).
• The probability that a buffer will overflow (Loss).
• The average number of packets in the system.

2.1.2 Little's Law

One of the most fundamental theorems in queuing theory is Little's Law: L = λW

• L: Average number of items in the system.
• λ: Average arrival rate.
• W: Average time spent in the system.
• Significance: This relationship holds regardless of the arrival distribution or the service discipline.

Study Deep: Applying Little's Law

Little's Law ($L = λW$) is powerful because it is independent of the internal distribution. For example:

• In a Router: If you know the arrival rate (packets/sec) and the average delay, you can calculate exactly how much memory (buffer size) you need on average.
• In a Coffee Shop: If 10 people arrive per hour and each stays 30 mins (0.5h), there are always 5 people in the shop.

2.1.3 The M/M/1 Queuing Model

The M/M/1 model is the simplest "Single-Server" model:

1. M (Arrivals): Poisson process (Markovian).
2. M (Service): Exponential distribution (Markovian).
3. 1 (Server): Only one processing unit.

Key Calculations:

• Utilization (ρ): λ / μ (where μ is the service rate).
• Probability of n packets: $P_n = (1 - ρ)ρ^n$.
• Average packets in queue: $ρ^2 / (1 - ρ)$.
• Critical Threshold: As ρ approaches 1.0 (100% utilization), the queue length and delay grow toward infinity. This is why high-speed networks are usually designed to run at 70-80% utilization.

2.1.4 Multi-Server Models (M/M/m)

In high-speed switches with parallel processing units, we use the M/M/m model.

• Allows for higher aggregate throughput.
• Reduces the probability of a single bottleneck.
• Example: A 10Gbps link might be implemented as four 2.5Gbps parallel "lanes."

2.1.5 Self-Similar Traffic and Fractals

Research in the 1990s (Leland et al.) showed that Ethernet traffic is NOT Poisson; it is Self-Similar or "Fractal."

• What this means: Traffic stays "bursty" no matter what time scale you look at (milliseconds, seconds, or minutes).
• Impact: Queues fill up much faster than predicted by simple M/M/1 models, requiring larger buffers.