Queues, random graphs, and queues on random graphs

The work presented in this thesis lies on the interface of two key areas in probability theory, namely queueing theory and random graph theory. In addition to the introduction, the thesis is structured in three parts which can be read independently, and each part contains multiple chapters. In Part I we consider the occupation time of a stochastic process. Our main motivation originated from queueing theory, where the occupation time arises naturally as a performance measure in various applications. In Part II random graph models are considered (or ensembles, a term that is often encountered in the statistical mechanics literature). The objects of interest are the canonical and the microcanonical ensembles, two probability measures on the space of graphs. We consider dense graphs where the degree of each vertex scales as the total number of vertices. In Part III we combine queueing theory and random graph theory. The object of interest is a queueing process on a randomly evolving network. We introduce and analyze two models of randomly evolving graphs. In both models the edges appear and disappear dependently of each other.