document: A large deviations analysis of the transient of a queue with many Markov fluid inputs : approximations and fast simulation This article analyzes the transient buffer content distribution of a queue fed by a large number of Markov fluid sources . We characterize the probability of overflow at time t , given the current buffer level and the number of sources in the on-state . After scaling buffer and bandwidth resources by the number of sources n , we can apply large deviations techniques . The transient overflow probability decays exponentially in n . In the case of exponential on/off sources , we derive an expression for the decay rate of the rare event probability under consideration . For general Markov fluid sources , we present a plausible conjecture . We also provide the `` most likely path '' from the initial state to overflow -LRB- at time t -RRB- . Knowledge of the decay rate and the most likely path to overflow leads to -LRB- i -RRB- approximations of the transient overflow probability and -LRB- ii -RRB- efficient simulation methods of the rare event of buffer overflow . The simulation methods , based on importance sampling , give a huge speed-up compared to straightforward simulations . The approximations are of low computational complexity and are accurate , as verified by means of simulation experiments
doc_bio_tags: O B I I O O O O O O O O B I I O B O O O O O O O B I I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O B I I O O O O O B I O O O O O O O O O B I O O O B I O O O O O O O O O O O B O O O B I O O O O O O O O O O O
extractive_keyphrases: large deviations analysis markov fluid inputs transient buffer content distribution bandwidth resources approximations transient overflow probability simulation methods importance sampling computational complexity
abstractive_keyphrases: buffer resources atm multiplexers ip routers queuing theory