Performance Analysis of Queueing Networks via Robust Optimization
Performance Analysis of Queueing Networks via Robust Optimization
复制标题
通过鲁棒优化对排队网络进行性能分析
DOI：
10.1287/opre.1100.0879
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Alexander Anatoliy Rikun
中科院分区：
文献类型：
--
作者：
D. Bertsimas;D. Gamarnik;Alexander Anatoliy Rikun
嵌入式网络的性能分析是嵌入式理论中最具挑战性的领域之一。除了非常专业的模型，如产品形式的网络，有很少的结果，提供可证明的非渐近的上界和下界的关键性能指标。
本文提出了一种基于鲁棒优化的性能分析方法。我们的方法的基本前提如下：而不是假设一个随机模型的随机原语满足某些概率定律-如i.i.d.。到达间隔和服务时间分布-我们假设基本原语是确定的，并满足这种概率定律的含义。这些影响采取简单的线性约束的形式，即那些由迭代对数律（LIL）的动机。使用这种方法，我们能够获得一些关键的性能指标的性能界限。此外，这些性能界限意味着类似的边界在底层的随机建模。
我们证明了我们的方法对两种类型的路由网络：（a）串联单类路由网络和（B）多类单服务器路由网络。在这两种情况下，使用所提出的鲁棒优化方法，我们能够获得一些稳态性能指标的显式上界。例如，对于TSC系统，我们得到了期望稳态逗留时间的形式为C（1-ρ）-1 ln ln（（1-ρ）-1）的上界，其中C为显式常数，ρ为瓶颈交通强度.这在定性上与该性能测量的正确的重交通缩放一致，直到ln ln（（1-ρ）-1）校正因子。
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.