• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Large deviation theory for queueing systems

Park, Young Wook 14 October 2005 (has links)
Consider a Markov jump process, X(t), with a nonnegative state space as a model for a queueing system. The motivation of this study is about useful estimates of system performance. For example, in a system with finite queues, the probability of the system of queues going from an empty state to a state in which the population of at least one queue reaches a large number before becoming empty again is one and the typical sample trajectory of this event is another. To answer these questions, we establish the large deviation principle (LDP) for an appropriate class of queueing processes. The model of our concern is the Jackson network which has a tree-type topological structure. Under carefully designed conditions, the LDP for a time homogeneous Markov process has been well established by Wentzel. However, mainly due to the nonnegativity constraint, the queue length process, X(t), of our model does not satisfy the assumed conditions. As a detour, we define the “potential process”, Y(t), which allows the negativity in state space in the way that even if a queue is empty, the server in the empty queue is working with a same rate as if the queue is not empty. Therefore, each Y<sub>i</sub>(t) can be expressed as the difference of the accumulated number of customers who came to station i and the accumulated number of services, done in station, i, up to time t. Then the scaled processes, Y<sup>∊</sup>(t) = ∊Y(t/∊), obeys LDP with a certain rate function, I<sub>[0,T]</sub>(x,Φ), i.e. P(Y<sup>∊</sup>(.)∈ B|Y<sup>∊</sup>(0) = x| ≈ exp[-1/∊ inf<sub>Φ∊B</sub> I<sub>[0,T]</sub>(x,Φ)], (UTLE) for some B ⊂ D<sup>r</sup>[0,T] = { right continuous R<sup>r</sup> — valued function which has a left limit at every point on [0,T]}. UTLE stands for ‘up to logarithmic equivalence’. By defining an appropriate Skorohod problem, we obtain a continuous mapping θ from D<sup>r</sup> to D<sup>r</sup><sub>(+)</sub>,) such that θ(Y)(t) is a version of X(t). Then we “push the LDP of potential process through” θ so that LDP of the queue length process can be achieved. The procedure of ‘pushing through’ is another principle of the large deviation theory. It is called “contraction principle” [3]. The contraction principle provides the rate function J<sub>[0,T]</sub> of the LDP for the queue length process and J<sub>[0,T]</sub>(Φ) = inf<sub>ψ|θ(ψ)=Φ</sub> J<sub>[0,T]</sub>(ψ). That is, when X<sup>∊</sup> ≡ ∊X(t/∊), for an appropriate set B ⊂ D<sup>r</sup><sub>(+)</sub>, P(X<sup>∊</sup>(.)∈ B|X<sup>∊</sup>(0) = x| ≈ exp[-1/∊ inf<sub>Φ∊B</sub> I<sub>[0,T]</sub>(x,Φ)], (UTLE) The rate function, J<sub>[0,T]</sub>, is expressed in a closed form. / Ph. D.

Page generated in 0.0855 seconds