  We present the first class of perfect sampling (also known as exact
simulation) algorithms for the steady-state distribution of non-Markovian loss
networks. We use a variation of Dominated Coupling From The Past for which we
simulate a stationary infinite server queue backwards in time and analyze the
running time in heavy traffic. In particular, we are able to simulate
stationary renewal marked point processes in unbounded regions. We use the
infinite server queue as an upper bound process to simulate loss systems. The
running time analysis of our perfect sampling algorithm for loss systems is
performed in the Quality-Driven (QD) and the Quality-and-Efficiency-Driven
regimes. In both cases, we show that our algorithm achieves sub-exponential
complexity as both the number of servers and the arrival rate increase.
Moreover, in the QD regime, our algorithm achieves a nearly optimal rate of
convergence.
