检索结果-内蒙古大学图书馆

Asymptotically optimal importance sampling for Jackson networks with a tree topology

QUEUEING SYSTEMS 2010年第2期64卷 103-117页

作者： Sezer, Ali Devin Middle E Tech Univ Inst Appl Math TR-06531 Ankara Turkey

This note describes an importance sampling (IS) algorithm to estimate buffer overflows of stable Jackson networks with a tree topology. Three new measures of service capacity and traffic in Jackson networks are introduced and the algorithm is defined in their terms. These measures are effective service rate, effective utilization and effective service-to-arrival ratio of a node. They depend on the nonempty/empty states of the queues of the network. For a node with a nonempty queue, the effective service rate equals the node's nominal service rate. For a node i with an empty queue, it is either a weighted sum of the effective service rates of the nodes receiving traffic directly from node i, or the nominal service rate, whichever smaller. The effective utilization is the ratio of arrival rate to the effective service rate and the effective service-to-arrival ratio is its reciprocal. The rare overflow event of interest is the following: given that initially the network is empty, the system experiences a buffer overflow before returning to the empty state. Two types of buffer structures are considered: (1) a single system-wide buffer shared by all nodes, and (2) each node has its own fixed size buffer. The constructed IS algorithm is asymptotically optimal, i. e., the variance of the associated estimator decays exponentially in the buffer size at the maximum possible rate. This is proved using methods from (Dupuis et al. in Ann. Appl. Probab. 17(4): 1306-1346, 2007), which are based on a limit Hamilton-Jacobi-Bellman equation and its boundary conditions and their smooth subsolutions. Numerical examples involving networks with as many as eight nodes are provided.

关键词： Dynamic importance sampling Rare event simulation Queuing networks Jackson networks overflow probability Large deviations Hamilton-Jacobi-Bellmann equation Optimal control

来源：评论

学校读者我要写书评

暂无评论

A loss network model with overflow for capacity planning of a neonatal unit

引用

ANNALS OF OPERATIONS RESEARCH 2010年第1期178卷 67-76页

作者： Asaduzzaman, Md Chaussalet, Thierry J. Robertson, Nicola J. Univ Westminster Hlth & Social Care Modelling Grp HSCMG Sch Informat London W1W 6UW England UCL UCL Elizabeth Garrett Inst Womens Hlth London W1T 7DN England

The main aim of this paper is to derive a solution to the capacity problem faced by many perinatal networks in the United Kingdom. We propose a queueing model to determine the number of cots at all care units for any desired overflow and rejection probability in a neonatal unit. The model formulation is developed, being motivated by overflow models in telecommunication systems. Exact expressions for the overflow and rejection probabilities are derived. The model is then applied to a neonatal unit of a perinatal network in the UK.

关键词： Neonatal unit overflow probability Rejection probability Queueing network OR in health care

来源：评论

学校读者我要写书评

暂无评论

Importance sampling for a Markov modulated queuing network

引用

STOCHASTIC PROCESSES AND THEIR APPLICATIONS 2009年第2期119卷 491-517页

作者： Sezer, Ali Devin Middle E Tech Univ Inst Appl Math TR-06531 Ankara Turkey

Importance sampling (IS) is a variance reduction method for simulating rare events. A recent paper by Dupuis, Wang and Sezer [Paul Dupuis, Ali Devin Sezer, Hui Wang, Dynamic importance sampling for queueing networks, Annals of Applied probability 17 (4) (2007) 1306-1346] exploits connections between IS and stochastic games and optimal control problems to show how to design and analyze simple and efficient IS algorithms for various overflow events of tandem Jackson Networks. The present paper carries out a program parallel to the paper by Dupuis et al. for a two node tandem network whose arrival and service rates are modulated by in exogenous finite state Markov process. The overflow event we study is the following: the number of customers in the system reaches n without the system ever becoming empty, given that initially the system is empty. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Dynamic importance sampling Rare event simulation Tandem queues Queuing networks Markov modulated Regime switch overflow probability Large deviations Isaacs equation Optimal control

来源：评论

学校读者我要写书评

暂无评论

A Statistical Connection Admission Control Mechanism for Multiservice IEEE 802.16 Network

A Statistical Connection Admission Control Mechanism for Mul...

引用

69th IEEE Vehicular Technology Conference

作者： Yu, Ke Wang, Xuan Sun, Songlin Zhang, Lin Wu, Xiaofei Beijing Univ Posts & Telecommun Sch Informat & Commun Engn Commun Network Lab Beijing 100088 Peoples R China

ISBN: (纸本)9781424425167

IEEE 802.16 is a promising technology in broadband wireless access area. In multiservice IEEE 802.16 network, connection admission control (CAC) plays a critical role for resource management and QoS guarantee. In this paper, a statistical CAC mechanism is proposed for IEEE 802.16 network. In order to avoid the QoS degradation, the proposed CAC mechanism considers the traffic variability and overflow. Furthermore, a model of traffic and air interface capacity is provided to make the CAC mechanism easy to be implemented. Then, a performance analysis model based on Markov chains is proposed. Numerical and simulation results show that the proposed CAC mechanism can prevent the traffic overflow and achieve a good packet level QoS.

关键词： IEEE 802.16 connection admission control quality of service complete sharing overflow probability

来源：评论

学校读者我要写书评

暂无评论

Statistical connection admission control for mobile WiMAX systems

Statistical connection admission control for mobile WiMAX sy...

引用

IEEE Wireless Communications and Networking Conference

作者： Lee, Ju Yong Kim, Ki Baek Univ Toronto Dept ECE Toronto ON Canada Samsung Elect Co LTD Telecommun Network Business Suwon South Korea

ISBN: (纸本)9781424419968

In this paper, we propose a new connection ad mission control (CAC) algorithm accommodating various classes of traffic, which can easily be implemented in mobile WiMAX system. The proposed CAC algorithm has three characteristics: first, the variation of air capacity is taken into account by measuring the distribution of modulation and coding scheme (MCS) levels offline;second, we estimate the mean and variance of frame occupancy ratio of each QoS How based on declared traffic descriptors;and third, the admission region is determined to satisfy the target overflow probability in the bufferless model. Through numerical analysis, we show that the accuracy of the proposed CAC is satisfactory.

关键词： mobile WiMAX OFDMA connection admission control admissible region overflow probability resource occupancy QoS

来源：评论

学校读者我要写书评

暂无评论

Algorithms for rare event simulation with Markov chains

Algorithms for rare event simulation with Markov chains

引用

5th International Industrial Simulation Conference

作者： Radev, Dimitar Lokshina, Izabella Univ Rousse 8 Studentska St Rousse 7017 Bulgaria SUNY Coll Oneonta Oneonta NY 13820 USA

ISBN: (纸本)9789077381342

An approach to overflow probability estimation in the queuing systems based on rare event simulation with Markov chains is proposed in this paper. Rare event probability that content of the second buffer exceeds some high level L before it becomes empty starting from a given state is considered. The approach is based on Markov additive representation of buffer processes, leading to exponential change of measure used in Importance Sampling (IS) procedure. The considered examples demonstrate that when the first buffer is finite, the relative error is bounded independent on some high level L. When the first buffer is infinite, a natural extension of exponential change of measure for finite buffer case is proposed. The relative error is shown to be bounded (independent on L) only when the second server is a bottleneck. However, when the first server is a bottleneck, experimental results confirm that the relative error is linearly bounded to level L. IS algorithms with cross-entropy are developed and used to speed up the overflow probability simulation. Numerical results are shown.

关键词： rare event simulation overflow probability queuing theory Markov chains

来源：评论

学校读者我要写书评

暂无评论

Fast simulation of overflow probabilities in a queue with Gaussian input

引用

ACM TRANSACTIONS ON MODELING AND COMPUTER SIMULATION 2006年第2期16卷 119-151页

作者： Dieker, A. B. Mandjes, M. CWI NL-1009 AB Amsterdam Netherlands Univ Twente NL-7500 AE Enschede Netherlands

In this article, we study a queue fed by a large number n of independent discrete-time Gaussian processes with stationary increments. We consider the many-sources asymptotic regime, that is, the buffer-exceedance threshold B and the service capacity C are scaled by the number of sources (B = nb and C = nc). We discuss four methods for simulating the steady-state probability that the buffer threshold is exceeded: the single-twist method (suggested by large deviation theory), the cut-and-twist method (simulating timeslot by timeslot), the random-twist method (the twist is sampled from a discrete distribution), and the sequential-twist method (simulating source by source). The asymptotic efficiency of these four methods is analytically investigated for n --> infinity. A necessary and sufficient condition is derived for the efficiency of the single-twist method, indicating that it is nearly always asymptotically inefficient. The other three methods, however, are asymptotically efficient. We numerically evaluate the four methods by performing a detailed simulation study where it is our main objective to compare the three efficient methods in practical situations.

关键词： algorithms performance asymptotic efficiency Gaussian processes importance sampling large deviations overflow probability queueing theory

来源：评论

学校读者我要写书评

暂无评论

Dimensioning of a dejittering buffer for variable bit rate video streams

Dimensioning of a dejittering buffer for variable bit rate v...

引用

13th International Conference on Analytical and Stochastic Modelling Techniques and Applications

作者： Spaey, Kathleen Blondia, Chris Univ Antwerp IBBT Performance Anal Telecommun Syst Res Grp B-2020 Antwerp Belgium

ISBN: (纸本)0955301807

In this paper a Markov model is developed that, given a simple description of the network delay and the packet interarrival times of a variable bit rate video stream, can be used to dimension the two important parameters of the dejittering process: the capacity Q the dejittering buffer should have and the dejittering delay T-jit the dejittering process should wait before starting the playout of the first packet. The correct setting of these parameters is important to keep both the packet loss due to dejittering buffer overflow and/or underflow and the introduced dejittering delay below some acceptable limits.

关键词： dejittering buffer Markov model underflow probability overflow probability

来源：评论

学校读者我要写书评

暂无评论

Conditional limit theorems for queues with Gaussian input, a weak convergence approach

引用

STOCHASTIC PROCESSES AND THEIR APPLICATIONS 2005年第5期115卷 849-873页

作者： Dieker, AB CWI NL-1090 GB Amsterdam Netherlands Univ Twente Fac Math Sci NL-7500 AE Enschede Netherlands

We consider a buffered queueing system that is fed by a Gaussian source and drained at a constant rate. The fluid offered to the system in a time interval (0, t] is given by a separable continuous Gaussian process Y with stationary increments. The variance function sigma(2) t -> Var Y-t of Y is assumed to be regularly varying with index 2H, for some 0 < H < 1. By proving conditional limit theorems, we investigate how a high buffer level is typically achieved. The underlying large deviation analysis also enables us to establish the logarithmic asymptotics for the probability that the buffer content exceeds u as u -> infinity. In addition, we study how a busy period longer than T typically occurs as T -> infinity, and we find the logarithmic asymptotics for the probability of such a long busy period. The study relies on the weak convergence in an appropriate space of {Y-alpha t/sigma(alpha) : t is an element of R} to a fractional Brownian motion with Hurst parameter H as alpha -> infinity. We prove this weak convergence under a fairly general condition on sigma(2), sharpening recent results of Kozachenko et al. (Queueing Systems Theory Appl. 42 (2002) 113). The core of the proof consists of a new type of uniform convergence theorem for regularly varying functions with positive index. (c) 2004 Elsevier B.V. All rights reserved.

关键词： weak convergence large deviations Gaussian processes overflow probability busy period metric entropy regular variation

来源：评论

学校读者我要写书评

暂无评论

Network decomposition: Theory and practice

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2005年第3期13卷 526-539页

作者： Eun, DY Shroff, NB N Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47905 USA

We show that significant simplicities can be obtained for the analysis of a network when link capacities are large enough to carry many flows. We develop a network decomposition approach in which network analysis can be greatly simplified. We prove that the queue length at the downstream queue converges to that of a single queue obtained by removing the upstream queue, as the capacity and the number of flows at the upstream queue increase. The precise modes of convergence vary depending on the type of input traffic, i.e., from regulated traffic arrivals to point process inputs. Our results thus help simplify network analysis by decomposing the original network into a simplified network in which all the nodes with large capacity have been eliminated. By means of extensive numerical investigation under various network scenarios, we demonstrate different aspects and implications of our network decomposition approach. Some of our findings are that our techniques perform well especially for the cases when: i) many flows are multiplexed as they enter the queue and/or ii) departing flows are routed to different downstream nodes, i.e., no single flow dominates at any node.

关键词： aggregation many-sources-asymptotic network decomposition overflow probability performance analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：