Other Queueing Models

There are many other important queueing models which are useful in networking.

• M/M/k for k > 1. Multiple (k) servers.
  • Good model of a link which is made up of multiple channels, either physically or through multiplexing (e.g. a T1 Carrier is typically time division multiplexed with k = 24).

  • Has worse performance at lower loads than M/M/1 with same total capacity.

• M/M/k/k for k 1. One or more servers, no buffers (except one in each server).
  • Important model in circuit switched networks.

  • Models a trunk line with k circuits available.

  • Any customer (a call) which doesn't get a circuit is blocked (gets a busy signal).

  • Blocking probability is given by the Erlang B (or Erlang Loss) Formula

    

• M/G/1. Arbitrary service (packet length) distribution.
  • Can still compute the mean number in the system via the Pollaczek-Khinchine (P-K) Formula

    

    where is the variance of the service time distribution.

  • Again, variability (randomness) causes delay.

  • Can apply Little's Formula to get the mean delay.

• M/D/1. Deterministic service times (packet length).
  • Special case of M/G/1 with

    

  • Under heavy load (), M/D/1 has half the delay of an M/M/1.

  • This is one motivation for fixed-packet-length systems like ATM.

• Can also model and analyze other queueing systems
  • With priority.

  • With more general arrival processes.

  • With ``vacations."

  • Many others.

• See Schwartz (Ch. 2), Kleinrock (Vol. I & II) or take 35.682/92.682, Queuing (sic) Systems and Applications.