Longest Path in Networks of Queues in the Steady-State

Due to the importance of longest path analysis in networks of queues, we develop an analytical method for computing the steady-state distribution function of longest path in acyclic networks of queues. We assume the network consists of a number of queuing systems and each one has either one or infinite servers. The distribution function of service time is assumed to be exponential or Erlang. Furthermore, the source node can include an M/G/∞ queuing system. The length of the arcs connecting the nodes of the network is assumed to be independent random variables. In the proposed method, the network of queues is transformed into a relevant stochastic network. Then, we compute the distribution function of longest path from the source node to the sink node in the transformed stochastic network. This is done through solving a system of linear differential equations with non-constant coefficients, which is obtained from a related continuous-time Markov process.

Keywords:

Queuing , Stochastic processes , Graph theory , network , Longest Path