Random Interval Graphs and the Maximum Throughput Rate in the System GI/G/1/0

摘要

An analysis of a random interval graph is presented which is the intersectiongraph of a family of random intervals. Based on a limit result for the expectation of a maximum stable set of the graph, the expectation of the maximum attainable fraction of served customers in the GI/G/1/0 loss system is given, under the assumption of perfect information about the future of the arrival and service processes. An asymptotic heavy traffic result for the fraction is derived, under the assumption of exponentially distributed service time.