The Experts below are selected from a list of 19809 Experts worldwide ranked by ideXlab platform
Dimitris Bertsimas - One of the best experts on this subject based on the ideXlab platform.
-
performance analysis of Queueing Networks via robust optimization
Operations Research, 2011Co-Authors: Dimitris Bertsimas, David Gamarnik, Alexander RikunAbstract:Performance analysis of Queueing Networks is one of the most challenging areas of Queueing theory. Barring very specialized models such as product-form type Queueing Networks, there exist very few results that provide provable nonasymptotic upper and lower bounds on key performance measures. In this paper we propose a new performance analysis method, which is based on the robust optimization. The basic premise of our approach is as follows: rather than assuming that the stochastic primitives of a Queueing model satisfy certain probability laws---such as i.i.d. interarrival and service times distributions---we assume that the underlying primitives are deterministic and satisfy the implications of such probability laws. These implications take the form of simple linear constraints, namely, those motivated by the law of the iterated logarithm (LIL). Using this approach we are able to obtain performance bounds on some key performance measures. Furthermore, these performance bounds imply similar bounds in the underlying stochastic Queueing models. We demonstrate our approach on two types of Queueing Networks: (a) tandem single-class Queueing network and (b) multiclass single-server Queueing network. In both cases, using the proposed robust optimization approach, we are able to obtain explicit upper bounds on some steady-state performance measures. For example, for the case of TSC system we obtain a bound of the form C(1-ρ)-1 ln ln((1-ρ)-1) on the expected steady-state sojourn time, where C is an explicit constant and ρ is the bottleneck traffic intensity. This qualitatively agrees with the correct heavy traffic scaling of this performance measure up to the ln ln((1-ρ)-1) correction factor.
-
performance analysis of Queueing Networks via robust optimization
arXiv: Optimization and Control, 2010Co-Authors: Dimitris Bertsimas, David Gamarnik, Alexander RikunAbstract:Performance analysis of Queueing Networks is one of the most challenging areas of Queueing theory. Barring very specialized models such as product-form type Queueing Networks, there exist very few results which provide provable non-asymptotic upper and lower bounds on key performance measures. In this paper we propose a new performance analysis method, which is based on the robust optimization. The basic premise of our approach is as follows: rather than assuming that the stochastic primitives of a Queueing model satisfy certain probability laws, such as, for example, i.i.d. interarrival and service times distributions, we assume that the underlying primitives are deterministic and satisfy the implications of such probability laws. These implications take the form of simple linear constraints, namely, those motivated by the Law of the Iterated Logarithm (LIL). Using this approach we are able to obtain performance bounds on some key performance measures. Furthermore, these performance bounds imply similar bounds in the underlying stochastic Queueing models. We demonstrate our approach on two types of Queueing Networks: a) Tandem Single Class queue- ing network and b) Multiclass Single Server Queueing network. In both cases, using the proposed robust optimization approach, we are able to obtain explicit upper bounds on some steady-state performance measures. For example, for the case of TSC system we obtain a bound of the form $\frac{C}{1-\rho} \ln \ln(1/(1-\rho))$ on the expected steady-state sojourn time, where C is an explicit constant and $\rho$ is the bottleneck traffic intensity. This qualitatively agrees with the correct heavy traffic scaling of this performance measure up to the $ln ln(1/(1-\rho))$ correction factor.
-
performance of multiclass markovian Queueing Networks via piecewise linear lyapunov functions
Annals of Applied Probability, 2001Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:Queueing Networks under a stable policy. We propose a general methodology based on Lyapunov functions for the performance analysis of infinite state Markov chains and apply it specifically to Markovian multiclass Queueing Networks. We establish a deeper connection between stability and performance of such Networks by showing that if there exist linear and piecewise linear Lyapunov functions that show stability, then these Lyapunov functions can be used to establish geometric-type lower and upper bounds on the tail probabilities, and thus bounds on the expectation of the queue lengths. As an example of our results, for a reentrant line Queueing network with two processing stations operating under a work-conserving policy, we
-
Performance analysis of multiclass Queueing Networks
ACM SIGMETRICS Performance Evaluation Review, 1999Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:The subject of this abstract is performance analysis of multiclass Queueing Networks. The objective is to estimate steady-state queue lengths in Queueing Networks, assuming a priori that the scheduling policy implemented brings the system to a steady state, namely is stable. We propose a very general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to multiclass exponential type Queueing Networks. We use, in particular, linear and piece-wise linear Lyapunov function to establish certain geometric type lower and upper bounds on the tail probabilities and bounds on expectation of the queue lengths. The results proposed in this paper are the first that establish geometric type upper and lower bounds on tail probabilities of queue lengths, for Networks of such generality. The previous results on performance analysis can in general achieve only numerical bounds and only on expectation and not the distribution of queue lengths.
-
Stability and performance of multiclass Queueing Networks
1998Co-Authors: David Gamarnik, Dimitris Bertsimas, John N. TsitsiklisAbstract:In the first part of the thesis, we address the question of stability of multiclass Queueing Networks operating under any work-conserving scheduling policy (global stability). It has been established that the stability of Queueing Networks is essentially equivalent to the stability of the underlying fluid model. However, the exact stability conditions for multiclass Queueing Networks are unknown. We propose a new and direct approach for stability analysis based on linear programming. We construct a linear program that provides an upper bound on the duration of the time until the fluid network empties. As a result, linear programs with finite optimal cost correspond to stable Networks. We prove that this criterion for stability is both necessary and sufficient for Networks with two stations. This approach also gives sufficient conditions for stability of Networks with more than two processing stations. We then modify this approach specifically for priority policies in multiclass fluid Queueing Networks. A linear program is constructed which bounds the duration of the time until the fluid network empties under a specific priority policy. In the second part of the thesis we concentrate on the performance analysis of multiclass Queueing Networks. The objective is to estimate steady-state queue lengths in Queueing Networks assuming a priori that the scheduling policy implemented is stable. We propose a very general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to multiclass exponential type Queueing Networks. We show that whenever some piece-wise linear Lyapunov function witnesses global stability of the network, certain finite upper bounds hold on the probability distribution and expectation of the queue lengths. Lower bounds are also constructed by means of a linear Lyapunov function. Specifically we show that whenever some piece-wise linear function witnesses global stability of the network, bounds of the form$$c\sbsp{1}{m}\le {\rm Pr}\{ {\rm total\ number\ of\ customers} \ge m\}\le c\sbsp{2}{m}$$hold for some computable constants $c\sb1We then concentrate on the performance analysis of Queueing Networks operating under some priority policy. Piece-wise linear and linear functions are used to construct upper and lower bounds on steady-state queue lengths. The proposed lower bounds are closed form and are expressed exclusively in terms of traffic intensities of the network. The upper bounds are numerical and are constructed using the solution of linear program which establishes the existence of a piece-wise linear Lyapunov function. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) (Abstract shortened by UMI.)
David Gamarnik - One of the best experts on this subject based on the ideXlab platform.
-
performance analysis of Queueing Networks via robust optimization
Operations Research, 2011Co-Authors: Dimitris Bertsimas, David Gamarnik, Alexander RikunAbstract:Performance analysis of Queueing Networks is one of the most challenging areas of Queueing theory. Barring very specialized models such as product-form type Queueing Networks, there exist very few results that provide provable nonasymptotic upper and lower bounds on key performance measures. In this paper we propose a new performance analysis method, which is based on the robust optimization. The basic premise of our approach is as follows: rather than assuming that the stochastic primitives of a Queueing model satisfy certain probability laws---such as i.i.d. interarrival and service times distributions---we assume that the underlying primitives are deterministic and satisfy the implications of such probability laws. These implications take the form of simple linear constraints, namely, those motivated by the law of the iterated logarithm (LIL). Using this approach we are able to obtain performance bounds on some key performance measures. Furthermore, these performance bounds imply similar bounds in the underlying stochastic Queueing models. We demonstrate our approach on two types of Queueing Networks: (a) tandem single-class Queueing network and (b) multiclass single-server Queueing network. In both cases, using the proposed robust optimization approach, we are able to obtain explicit upper bounds on some steady-state performance measures. For example, for the case of TSC system we obtain a bound of the form C(1-ρ)-1 ln ln((1-ρ)-1) on the expected steady-state sojourn time, where C is an explicit constant and ρ is the bottleneck traffic intensity. This qualitatively agrees with the correct heavy traffic scaling of this performance measure up to the ln ln((1-ρ)-1) correction factor.
-
performance analysis of Queueing Networks via robust optimization
arXiv: Optimization and Control, 2010Co-Authors: Dimitris Bertsimas, David Gamarnik, Alexander RikunAbstract:Performance analysis of Queueing Networks is one of the most challenging areas of Queueing theory. Barring very specialized models such as product-form type Queueing Networks, there exist very few results which provide provable non-asymptotic upper and lower bounds on key performance measures. In this paper we propose a new performance analysis method, which is based on the robust optimization. The basic premise of our approach is as follows: rather than assuming that the stochastic primitives of a Queueing model satisfy certain probability laws, such as, for example, i.i.d. interarrival and service times distributions, we assume that the underlying primitives are deterministic and satisfy the implications of such probability laws. These implications take the form of simple linear constraints, namely, those motivated by the Law of the Iterated Logarithm (LIL). Using this approach we are able to obtain performance bounds on some key performance measures. Furthermore, these performance bounds imply similar bounds in the underlying stochastic Queueing models. We demonstrate our approach on two types of Queueing Networks: a) Tandem Single Class queue- ing network and b) Multiclass Single Server Queueing network. In both cases, using the proposed robust optimization approach, we are able to obtain explicit upper bounds on some steady-state performance measures. For example, for the case of TSC system we obtain a bound of the form $\frac{C}{1-\rho} \ln \ln(1/(1-\rho))$ on the expected steady-state sojourn time, where C is an explicit constant and $\rho$ is the bottleneck traffic intensity. This qualitatively agrees with the correct heavy traffic scaling of this performance measure up to the $ln ln(1/(1-\rho))$ correction factor.
-
performance of multiclass markovian Queueing Networks via piecewise linear lyapunov functions
Annals of Applied Probability, 2001Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:Queueing Networks under a stable policy. We propose a general methodology based on Lyapunov functions for the performance analysis of infinite state Markov chains and apply it specifically to Markovian multiclass Queueing Networks. We establish a deeper connection between stability and performance of such Networks by showing that if there exist linear and piecewise linear Lyapunov functions that show stability, then these Lyapunov functions can be used to establish geometric-type lower and upper bounds on the tail probabilities, and thus bounds on the expectation of the queue lengths. As an example of our results, for a reentrant line Queueing network with two processing stations operating under a work-conserving policy, we
-
Using fluid models to prove stability of adversarial Queueing Networks
IEEE Transactions on Automatic Control, 2000Co-Authors: David GamarnikAbstract:A digital communication network can be modeled as an adversarial Queueing network. An adversarial Queueing network is defined to be stable if the number of packets stags bounded over time. A central question is to determine which adversarial Queueing Networks are stable under every work-conserving packet routing policy. Our main result is that stability of an adversarial Queueing network is implied by stability of an associated fluid Queueing network.
-
Performance analysis of multiclass Queueing Networks
ACM SIGMETRICS Performance Evaluation Review, 1999Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:The subject of this abstract is performance analysis of multiclass Queueing Networks. The objective is to estimate steady-state queue lengths in Queueing Networks, assuming a priori that the scheduling policy implemented brings the system to a steady state, namely is stable. We propose a very general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to multiclass exponential type Queueing Networks. We use, in particular, linear and piece-wise linear Lyapunov function to establish certain geometric type lower and upper bounds on the tail probabilities and bounds on expectation of the queue lengths. The results proposed in this paper are the first that establish geometric type upper and lower bounds on tail probabilities of queue lengths, for Networks of such generality. The previous results on performance analysis can in general achieve only numerical bounds and only on expectation and not the distribution of queue lengths.
John N. Tsitsiklis - One of the best experts on this subject based on the ideXlab platform.
-
performance of multiclass markovian Queueing Networks via piecewise linear lyapunov functions
Annals of Applied Probability, 2001Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:Queueing Networks under a stable policy. We propose a general methodology based on Lyapunov functions for the performance analysis of infinite state Markov chains and apply it specifically to Markovian multiclass Queueing Networks. We establish a deeper connection between stability and performance of such Networks by showing that if there exist linear and piecewise linear Lyapunov functions that show stability, then these Lyapunov functions can be used to establish geometric-type lower and upper bounds on the tail probabilities, and thus bounds on the expectation of the queue lengths. As an example of our results, for a reentrant line Queueing network with two processing stations operating under a work-conserving policy, we
-
Performance analysis of multiclass Queueing Networks
ACM SIGMETRICS Performance Evaluation Review, 1999Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:The subject of this abstract is performance analysis of multiclass Queueing Networks. The objective is to estimate steady-state queue lengths in Queueing Networks, assuming a priori that the scheduling policy implemented brings the system to a steady state, namely is stable. We propose a very general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to multiclass exponential type Queueing Networks. We use, in particular, linear and piece-wise linear Lyapunov function to establish certain geometric type lower and upper bounds on the tail probabilities and bounds on expectation of the queue lengths. The results proposed in this paper are the first that establish geometric type upper and lower bounds on tail probabilities of queue lengths, for Networks of such generality. The previous results on performance analysis can in general achieve only numerical bounds and only on expectation and not the distribution of queue lengths.
-
Stability and performance of multiclass Queueing Networks
1998Co-Authors: David Gamarnik, Dimitris Bertsimas, John N. TsitsiklisAbstract:In the first part of the thesis, we address the question of stability of multiclass Queueing Networks operating under any work-conserving scheduling policy (global stability). It has been established that the stability of Queueing Networks is essentially equivalent to the stability of the underlying fluid model. However, the exact stability conditions for multiclass Queueing Networks are unknown. We propose a new and direct approach for stability analysis based on linear programming. We construct a linear program that provides an upper bound on the duration of the time until the fluid network empties. As a result, linear programs with finite optimal cost correspond to stable Networks. We prove that this criterion for stability is both necessary and sufficient for Networks with two stations. This approach also gives sufficient conditions for stability of Networks with more than two processing stations. We then modify this approach specifically for priority policies in multiclass fluid Queueing Networks. A linear program is constructed which bounds the duration of the time until the fluid network empties under a specific priority policy. In the second part of the thesis we concentrate on the performance analysis of multiclass Queueing Networks. The objective is to estimate steady-state queue lengths in Queueing Networks assuming a priori that the scheduling policy implemented is stable. We propose a very general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to multiclass exponential type Queueing Networks. We show that whenever some piece-wise linear Lyapunov function witnesses global stability of the network, certain finite upper bounds hold on the probability distribution and expectation of the queue lengths. Lower bounds are also constructed by means of a linear Lyapunov function. Specifically we show that whenever some piece-wise linear function witnesses global stability of the network, bounds of the form$$c\sbsp{1}{m}\le {\rm Pr}\{ {\rm total\ number\ of\ customers} \ge m\}\le c\sbsp{2}{m}$$hold for some computable constants $c\sb1We then concentrate on the performance analysis of Queueing Networks operating under some priority policy. Piece-wise linear and linear functions are used to construct upper and lower bounds on steady-state queue lengths. The proposed lower bounds are closed form and are expressed exclusively in terms of traffic intensities of the network. The upper bounds are numerical and are constructed using the solution of linear program which establishes the existence of a piece-wise linear Lyapunov function. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) (Abstract shortened by UMI.)
-
Stability conditions for multiclass fluid Queueing Networks
IEEE Transactions on Automatic Control, 1996Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:We introduce a new method to investigate stability of work-conserving policies in multiclass Queueing Networks. The method decomposes feasible trajectories and uses linear programming to test stability. We show that this linear program is a necessary and sufficient condition for the stability of all work-conserving policies for multiclass fluid Queueing Networks with two stations. Furthermore, we find new sufficient conditions for the stability of multiclass Queueing Networks involving any number of stations and conjecture that these conditions are also necessary. Previous research had identified sufficient conditions through the use of a particular class of (piecewise linear convex) Lyapunov functions. Using linear programming duality, we show that for two-station systems the Lyapunov function approach is equivalent to ours and therefore characterizes stability exactly.
-
Performance of multiclass Markovian Queueing Networks
Proceedings of the 39th IEEE Conference on Decision and Control (Cat. No.00CH37187), 1Co-Authors: Dimitris Bertsimas, David Gamarnik, John N. TsitsiklisAbstract:We study the distribution of steady-state queue lengths in multiclass Queueing Networks under a stable policy. We propose a general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to Markovian multiclass Queueing Networks. We establish a deeper connection between stability and performance of such Networks by showing that if there exist linear and piecewise linear Lyapunov functions that show stability, then these Lyapunov functions can be used to establish geometric type lower and upper bounds on the tail probabilities, and thus bounds on the expectation of the queue lengths. As an example of our results, for a reentrant line Queueing network with two processing stations operating under a work-conserving policy we show that E[L]=O (1/(1-/spl rho/*)2), where L is the total number of customers in the system, and /spl rho/* is the maximal actual or virtual traffic intensity in the network. This extends a recent result by Dai and Vande-Vate, which states that a re-entrant line Queueing network with two stations is globally stable if /spl rho/*
P. R. Kumar - One of the best experts on this subject based on the ideXlab platform.
-
new linear program performance bounds for Queueing Networks
Journal of Optimization Theory and Applications, 1999Co-Authors: James R Morrison, P. R. KumarAbstract:We obtain new linear programs for bounding the performance and proving the stability of Queueing Networks. They exploit the key facts that the transition probabilities of Queueing Networks are shift invariant on the relative interiors of faces and the cost functions of interest are linear in the state. A systematic procedure for choosing different quadratic functions on the relative interiors of faces to serve as surrogates of the differential costs in an inequality relaxation of the average cost function leads to linear program bounds. These bounds are probably better than earlier known bounds. It is also shown how to incorporate additional features, such as the presence of virtual multi-server stations to further improve the bounds. The approach also extends to provide functional bounds valid for all arrival rates.
-
stability of Queueing Networks and scheduling policies
IEEE Transactions on Automatic Control, 1995Co-Authors: P. R. Kumar, Sean P MeynAbstract:We develop a programmatic procedure for establishing the stability of Queueing Networks and scheduling policies. The method uses linear or nonlinear programming to determine what is an appropriate quadratic functional to use as a Lyapunov function. If the underlying system is Markovian, our method establishes not only positive recurrence and the existence of a steady-state probability distribution, but also the geometric convergence of an exponential moment. We illustrate this method on several example problems. >
-
Stability of Queueing Networks and
1995Co-Authors: P. R. KumarAbstract:Usually, the stability of Queueing Networks is es- tablished by explicitly determining the invariant distribution. Outside of the narrow class of Queueing Networks possessing a product form solution, however, such explicit solutions are rare, and consequently little is also known concerning stability. We develop here a programmatic procedure for establishing the stability of Queueing Networks and scheduling policies. The method uses linear or nonlinear programming to determine what is an appropriate quadratic functional to use as a Lyapunov function. If the underlying system is Markovian, our method establishes not only positive recurrence and the existence of a steady-state probability distribution, but also the geometric convergence of an exponential moment. We illustrate this method on several example problems. For an example of an open re-entrant line, we show that all stationary nonidling policies are stable for all load factors less than one. This includes the well-known First Come First Serve (FCFS) policy. We determine a subset of the stability region for the Dai-Wang example, for which they have shown that the Brownian approximation does not hold. In another re-entrant line, we show that the Last Buffer First Serve (LBFS) and First Buffer First Serve (FBFS) policies are stable for all load factors less than one. Finally, for the Rybko-Stolyar example, for which a subset of the instability region has been determined by them under a certain buffer priority policy, we determine a subset of the stability region.
-
performance bounds for Queueing Networks and scheduling policies
IEEE Transactions on Automatic Control, 1994Co-Authors: Sunil Kumar, P. R. KumarAbstract:Except for the class of Queueing Networks and scheduling policies admitting a product form solution for the steady-state distribution, little is known about the performance of such systems. For example, if the priority of a part depends on its class (e.g., the buffer that the part is located in), then there are no existing results on performance, or even stability. In most applications such as manufacturing systems, however, one has to choose a control or scheduling policy, i.e., a priority discipline, that optimizes a performance objective. In this paper the authors introduce a new technique for obtaining upper and lower bounds on the performance of Markovian Queueing Networks and scheduling policies. Assuming stability, and examining the consequence of a steady state for general quadratic forms, the authors obtain a set of linear equality constraints on the mean values of certain random variables that determine the performance of the system. Further, the conservation of time and material gives an augmenting set of linear equality and inequality constraints. Together, these allow the authors to bound the performance, either above or below, by solving a linear program. The authors illustrate this technique on several typical problems of interest in manufacturing systems. For an open re-entrant line modeling a semiconductor plant, the authors plot a bound on the mean delay (called cycle-time) as a function of line loading. It is shown that the last buffer first serve policy is almost optimal in light traffic. For another such line, it is shown that it dominates the first buffer first serve policy. For a set of open Queueing Networks, the authors compare their lower bounds with those obtained by another method of Ou and Wein (1992). For a closed Queueing network, the authors bracket the performance of all buffer priority policies, including the suggested priority policy of Harrison and Wein (1990). The authors also study the asymptotic heavy traffic limits of the lower and upper bounds. For a manufacturing system with machine failures, it is shown how the performance changes with failure and repair rates. For systems with finite buffers, the authors show how to bound the throughput. Finally, the authors illustrate the application of their method to GI/GI/1 queues. The authors obtain analytic bounds which improve upon Kingman's bound (1970) for E/sub 2//M/1 queues. >
-
stability of Queueing Networks and scheduling policies
Conference on Decision and Control, 1993Co-Authors: P. R. Kumar, Sean P MeynAbstract:Usually, the stability of Queueing Networks is established by explicitly determining the invariant distribution. However, except for product form Queueing Networks, such explicit solutions are rare. We develop here a programmatic procedure for establishing the stability of Queueing Networks and scheduling policies. The method uses linear or nonlinear programming to determine what is an appropriate quadratic functional to use as a Lyapunov function. If the underlying system is Markovian, our method establishes not only positive recurrence and the existence of a steady-state probability distribution, but also the geometric convergence of an exponential moment. We illustrate this method on several example problems. For an open re-entrant line, we show that all stationary nonidling policies are stable for all load factors less than one. This includes the well known first-come-first-served (FCFS) policy. We determine a subset of the stability region for the Dai-Wang example (1991), for which they have shown that the Brownian approximation does not hold. In another re-entrant line, we show that the last-buffer-first-served (LBFS) and first-buffer-first-served (FBFS) policies are stable for all load factors less than one. Finally, for the Rybko-Stolyar example (1992), for which a subset of the instability region has been determined by them under a certain buffer priority policy, we determine a subset of the stability region. >
Alexander Rikun - One of the best experts on this subject based on the ideXlab platform.
-
performance analysis of Queueing Networks via robust optimization
Operations Research, 2011Co-Authors: Dimitris Bertsimas, David Gamarnik, Alexander RikunAbstract:Performance analysis of Queueing Networks is one of the most challenging areas of Queueing theory. Barring very specialized models such as product-form type Queueing Networks, there exist very few results that provide provable nonasymptotic upper and lower bounds on key performance measures. In this paper we propose a new performance analysis method, which is based on the robust optimization. The basic premise of our approach is as follows: rather than assuming that the stochastic primitives of a Queueing model satisfy certain probability laws---such as i.i.d. interarrival and service times distributions---we assume that the underlying primitives are deterministic and satisfy the implications of such probability laws. These implications take the form of simple linear constraints, namely, those motivated by the law of the iterated logarithm (LIL). Using this approach we are able to obtain performance bounds on some key performance measures. Furthermore, these performance bounds imply similar bounds in the underlying stochastic Queueing models. We demonstrate our approach on two types of Queueing Networks: (a) tandem single-class Queueing network and (b) multiclass single-server Queueing network. In both cases, using the proposed robust optimization approach, we are able to obtain explicit upper bounds on some steady-state performance measures. For example, for the case of TSC system we obtain a bound of the form C(1-ρ)-1 ln ln((1-ρ)-1) on the expected steady-state sojourn time, where C is an explicit constant and ρ is the bottleneck traffic intensity. This qualitatively agrees with the correct heavy traffic scaling of this performance measure up to the ln ln((1-ρ)-1) correction factor.
-
performance analysis of Queueing Networks via robust optimization
arXiv: Optimization and Control, 2010Co-Authors: Dimitris Bertsimas, David Gamarnik, Alexander RikunAbstract:Performance analysis of Queueing Networks is one of the most challenging areas of Queueing theory. Barring very specialized models such as product-form type Queueing Networks, there exist very few results which provide provable non-asymptotic upper and lower bounds on key performance measures. In this paper we propose a new performance analysis method, which is based on the robust optimization. The basic premise of our approach is as follows: rather than assuming that the stochastic primitives of a Queueing model satisfy certain probability laws, such as, for example, i.i.d. interarrival and service times distributions, we assume that the underlying primitives are deterministic and satisfy the implications of such probability laws. These implications take the form of simple linear constraints, namely, those motivated by the Law of the Iterated Logarithm (LIL). Using this approach we are able to obtain performance bounds on some key performance measures. Furthermore, these performance bounds imply similar bounds in the underlying stochastic Queueing models. We demonstrate our approach on two types of Queueing Networks: a) Tandem Single Class queue- ing network and b) Multiclass Single Server Queueing network. In both cases, using the proposed robust optimization approach, we are able to obtain explicit upper bounds on some steady-state performance measures. For example, for the case of TSC system we obtain a bound of the form $\frac{C}{1-\rho} \ln \ln(1/(1-\rho))$ on the expected steady-state sojourn time, where C is an explicit constant and $\rho$ is the bottleneck traffic intensity. This qualitatively agrees with the correct heavy traffic scaling of this performance measure up to the $ln ln(1/(1-\rho))$ correction factor.
