Large deviation and fluid approximations can provide valuable insight to the behaviour of stochastic systems. This paper summarises some of the key ideas and discusses a number of examples, including a probabilistic analysis of the first-fit decreasing bin packing algorithm, and comments on ideas of Whittle relating to risk-sensitive control of Markov processes. In a final example, a large deviations analysis is used to estimate the frequency of overflow when a number of stationary traffic sources are routed through a switch with a finite buffer. we show that the buffer overflow frequency is asymptotically less that a specified amount if an only if the sum of the effective bandwidths for the different traffic sources is less than the bandwidth of the switch and we suggest a simple approximation for these effective bandwidths.
back to list of papers