Surrogate-based Approximation of Blocking Probability in Non-hierarchical Overflow Loss Systems


Student thesis: Doctoral Thesis

View graph of relations


  • Yin Chi CHAN

Related Research Unit(s)


Awarding Institution
Award date14 Oct 2016


We consider a model of an overflow loss system in which requests require the service of a single server, but each request has access to only some of the servers in the system, depending on the request type. Such a model is a generalization of the classical grading system model for telephony switching, yet still has many applications today such as cellular networks, video-on-demand, server farms, and emergency healthcare.

A classical method for evaluating blocking probability in an overflow loss system is the Exponential Decomposition (ED), which involves de-coupling the system into a set of zero-buffer queues, each with Poisson and independent input (e.g. M/M/N/N or M/M/1/N–PS). ED stems from the even older Erlang Fixed-Point Approximation for switched networks, for which theoretical results have been proven regarding convergence in several limiting regimes.

On the other hand, ED’s simplifying assumptions of Poisson and independent input are known to generate large errors in certain cases. Recently, an extension to ED, known as the Information Exchange Surrogate Approximation framework (IESA framework), was introduced to address such errors. IESA differs from ED in that decoupling is applied to a surrogate model of the original system. The surrogate is carefully designed to be close in blocking probability to the original system while greatly reducing the errors caused by decoupling. The estimated blocking probability of the surrogate thus forms an estimate for that of the original system.

The contributions of this thesis are as follows. Firstly, the IESA framework is extended by introducing new surrogate models. Secondly, several theorems and conjectures are provided for special cases in which both the offered traffic and routing policy are fully symmetric. Thirdly, the IESA framework is extended using moment-matching techniques, allowing the Poisson traffic assumption to be dropped. Fourthly, the IESA framework is extended to overflow loss systems of processor-sharing (M/M/1/N-PS) queues. Finally, as a case study, the IESA framework is applied to a model of patient referral in an ICU network.

Via extensive numerical results, it is concluded that the IESA framework is the first framework to provide a scalable, accurate, and robust approximation technique for overflow loss systems exhibiting both unbalanced offered traffic and a non-hierarchical overflow structure.