Delay analysis of discrete-time priority queue with structured inputs

This paper investigates a discrete-time priority queue with multi-class customers. Applying a delay-cycle analysis, we explicitly derive the probability generating function of the waiting time for an individual class in a geometric batch input queue under preemptive-resume and head-of-the-line priority rules. The conservation law and waiting time characterization for a general class of discrete-time queues are also presented. The results in this paper cover several previous results as special cases.     

Mean delay analysis for a message priority-based polling scheme

We consider a multi-access communication channel such as a centrally-controlled polling system, a distributed token-based ring, or a bus network. A message priority-based polling procedure is used to control the access to the channel. This procedure requires the server to have no advance information concerning the number of messages resident at a station prior to its visit to the station. Messages arriving at each station belong to one of two priority classes: class-1 (high priority) and class-2 (low priority). Class-1 messages are served under an exhaustive service discipline, while class-2 messages are served under a limited service discipline. Class-1 messages have non-preemptive priority over class-2 messages resident at the same station. Using a fully symmetric system model, an exact expression for the sum of the mean waiting times of class-1 and class-2 messages is first derived. Upper and lower bounds for the mean message waiting times for each individual message class are then obtained.This work was supported by NFS Grant No. NCR-8914690, Pacific-Bell and MICRO Grant No. 90-135 and US West Contract No. D890701.     

Stability of a three‐station fluid network

This paper studies the stability of a three‐station fluid network. We show that, unlike the two‐station networks in Dai and Vande Vate [18], the global stability region of our three‐station network is not the intersection of its stability regions under static buffer priority disciplines. Thus, the “worst” or extremal disciplines are not static buffer priority disciplines. We also prove that the global stability region of our three‐station network is not monotone in the service times and so, we may move a service time vector out of the global stability region by reducing the service time for a class. We introduce the monotone global stability region and show that a linear program (LP) related to a piecewise linear Lyapunov function characterizes this largest monotone subset of the global stability region for our three‐station network. We also show that the LP proposed by Bertsimas et al. [1] does not characterize either the global stability region or even the monotone global stability region of our three‐station network. Further, we demonstrate that the LP related to the linear Lyapunov function proposed by Chen and Zhang [11] does not characterize the stability region of our three‐station network under a static buffer priority discipline. This revised version was published online in June 2006 with corrections to the Cover Date.     

An Exact Solution for the State Probabilities of the Multi-Class,Multi-Server Queue with Preemptive Priorities

We consider a multi-class, multi-server queueing system with preemptive priorities. We distinguish two groups of priority classes that consist of multiple customer types, each having their own arrival and service rate. We assume Poisson arrival processes and exponentially distributed service times. We derive an exact method to estimate the steady state probabilities. Because we need iterations to calculate the steady state probabilities, the only error arises from choosing a finite number of matrix iterations. Based on these probabilities, we can derive approximations for a wide range of relevant performance characteristics, such as the moments of the number of customers of a certain type in the system en the expected postponement time for each customer class. We illustrate our method with some numerical examples. Numerical results show that in most cases we need only a moderate number of matrix iterations (∼20) to obtain an error less than 1% when estimating key performance characteristics.This revised version was published online in June 2005 with corrected coverdate     

A discrete-time priority queue with two-class customers and bulk services

This paper studies the behavior of a discrete queueing system which accepts synchronized arrivals and provides synchronized services. The number of arrivals occurring at an arriving point may follow any arbitrary discrete distribution possessing finite first moment and convergent probability generating function in ¦ z ¦ 1 + with > 0. The system is equipped with an infinite buffer and one or more servers operating in synchronous mode. Service discipline may or may not be prioritized. Results such as the probability generating function of queue occupancy, average queue length, system throughput, and delay are derived in this paper. The validity of the results is also verified by computer simulations.The work reported in this paper was supported by the National Science Council of the Republic of China under Grant NSC1981-0404-E002-04.     

Diffusion approximations for multiclass queueing networks under preemptive priority service discipline

We prove a heavy traffic limit theorem to justify diffusion approximations for multiclass queueing networks under preemptive priority service discipline and provide effective stochastic dynamical models for the systems.Such queueing networks appear typically in high-speed integrated services packet networks about telecommunication sys- tem.In the network,there is a number of packet traffic types.Each type needs a number of job classes(stages)of processing and each type of jobs is assigned the same priority rank at every station where it possibly receives service.Moreover,there is no inter-routing among different traffic types throughout the entire network.     

区间数互补判断矩阵排序的一种实用方法

本提出了区间数互补判断矩阵排序的一种基于可能度的简洁实用方法,并进行了算例分析。     

基于最小化平均分组跳的分组交换多跳光网的设计

本文研究了支持分组交换通信的波长路由光网的逻辑拓扑设计问题,并将它表示为混合整数线性规划问题(MILP),其目标函数为最小化平均分组跳数目.在约束条件中同时考虑了分组传输时延和排队时延.我们以6结点的网络为例,对于不同的收发机数目和时延边界,数值结果表明最小化平均分组跳数目等价于最小化网络拥塞.小的平均分组跳数目可以保证网络通信时具有较小的时延.最后,对于不同的通信模式,我们比较分析了网格的优化性能参数,这些结果有助于提出更好的启发式算法.     

一种反馈FDL结构竞争解决丢包率的研究

对反馈FDL结构的光分组交换竞争解决方案建立了数学模型并进行了理论分析,推导出了在反馈FDL输入分组比输入光纤输入分组具有更高输出优先级时的系统丢包率公式,对系统丢包率与负载、输入光纤端口数和FDL数目的关系进行了数值计算和讨论.结果表明：由于FDL缓存分组的概率与输入分组负载的非线性关系导致了反馈FDL结构在低负载时对丢包率的改善非常明显,对高负载的改善却十分有限.随着FDL数目的增加,对系统丢包率的改善不会趋于一个极限值,这是与使用波长转换器进行竞争解决的不同之处,因此使用反馈FDL结构可以降低波长转换器的丢包率极限.     

OPS网络中SOA交换矩阵的串扰研究

通过对光开关和节点流量进行建模,利用新颖的等效串扰系数法,研究了基于XGM效应的SOA开关矩阵在OPS网络中的串扰问题.分析了SOA的各种参量以及节点流量特性对开关隔离度、节点中由串扰造成的误码率以及节点级联能力的影响.提出了优化SOA交换矩阵的具体措施,包括提高SOA的载流子寿命、控制脉冲能量和节点中流量的单播特性,以及降低SOA的饱和能量和有源区长度等.