Little’s Law

Average number of jobs in a system equals the average arrival rate times the average time in system. Holds for any stable system regardless of arrival process, service distribution, or topology.

From ECE459 L32

Source: [HB13], [Sig09].

Open systems

$E[N]=\lambda E[T]$

• $E[N]$: expected jobs in system.
• $\lambda$: average arrival rate.
• $E[T]$: mean time in system.

University example: 5 000 students/year × 4 years = 20 000 students on campus.

Intuition, fast food vs sit-down: low $E[T]$ ⇒ low seating ($E[N]$); high $E[T]$ ⇒ lots of seats. Restaurants rent seats, not food.

FCFS derivation: arriving customer sees $E[N]$ ahead; each takes $1/\lambda$ on average, so $E[T]\approx E[N]/\lambda$.

Closed systems

Ergodic system with multiprogramming level $N$: $N=X\cdot E[T]$

• $X$: throughput.
• Assumes zero think time.

Terminal-driven (with think time)

$E[R]=\frac{N}{X}-E[Z]$

• $E[R]$: response time.
• $E[Z]$: mean think time.

Related

• Queueing Theory
• Ergodicity
• 1