Effect of model uncertainty on some optimal routing problems

We study the effect of model uncertainties on optimal routing in a system of parallel queues. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity, the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using on-line gradient estimation is also included and its performance compared with that of model-based algorithms.This work was supported in part by the National Science Foundation under Grant ECS-88-01912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

Effect of Modeling Uncertainty on Some Routing Problems

In this paper, we consider the routing problem described in Mohanty and Cassandras (Ref. 1). As in Ref. 1, we show that the optimal Bernoulli split to minimize mean time in the system is asymptotically independent of the variance of the service time. We give simple proofs of the results in that paper. We exploit the fact that the optimal split to minimize the mean queueing time is variance independent and the special structure of the Karush–Kuhn–Tucker optimality conditions to derive the optimal solution. Apart from being very straightforward, the proofs also give insight into the reason for the existence of the variance-independent asymptotically optimal routing policy.     

Asymptotic optimality of the Round–Robin policy in multipath routing with resequencing

We consider a model of a multipath routing system where arriving customers are routed to a set of identical, parallel, single server queues according to balancing policies operating without state information. After completion of service, customers are required to leave the system in their order of arrival, thus incurring an additional resequencing delay. We are interested in minimizing the end-to-end delay (including time at the resequencing buffer) experienced by arriving customers. To that end we establish the optimality of the Round–Robin routing assignment in two asymptotic regimes, namely heavy and light traffic: In heavy traffic, the Round–Robin customer assignment is shown to achieve the smallest (in the increasing convex stochastic ordering) end-to-end delay amongst all routing policies operating without queue state information. In light traffic, and for the special case of Poisson arrivals, we show that Round–Robin is again an optimal (in the strong stochastic ordering) routing policy. We illustrate the stochastic comparison results by several simulation examples. The work of the first author was supported through an ARCHIMEDES grant by the Greek Ministry of Education. The work of the second author was prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government.     

Uniqueness of the solution for optimal static routing in open BCMP queueing networks

Optimal static routing problems in open BCMP queueing networks with state-independent arrival and service rates are studied. They include static routing problems in communication networks and optimal static load balancing problems in distributed computer systems. We consider an overall optimal policy that is the routing policy whereby the overall mean response (or sojourn) time of a job is minimized. We obtain the routing decisions of the overall optimal policy and show that they may not be unique, but that the utilization of each service center is uniquely determined by the overall optimal policy. We also consider an individually optimal policy whereby jobs are routed so that each job may feel that its own expected response time is minimized if it knows the mean delay time for each path.     

Asymptotically optimal staffing of service systems with joint QoS constraints

We consider the problem of staffing large-scale service systems with multiple customer classes and multiple dedicated server pools under joint quality-of-service (QoS) constraints. We first analyze the case in which arrival rates are deterministic and the QoS metric is the probability a customer is queued, given by the Erlang-C formula. We use the Janssen–Van Leeuwaarden–Zwart bounds to obtain asymptotically optimal solutions to this problem. The second model considered is one in which the arrival rates are not completely known in advance (before the server staffing levels are chosen), but rather are known via a probability distribution. In this case, we provide asymptotically optimal solutions to the resulting stochastic integer program, leveraging results obtained for the case of deterministic arrivals.     

A simple load balancing problem with decentralized information

The following load balancing problem is investigated in discrete time: A service system consists of two service stations and two controllers, one in front of each station. The service stations provide the same service with identical service time distributions and identical waiting costs. Customers requiring service arrive at a controller's site and are routed to one of the two stations by the controller. The processes describing the two arrival streams are identical. Each controller has perfect knowledge of the workload in its own station and receives information about the other station's workload with one unit of delay. The controllers' routing strategies that minimize the customers' total flowtime are determined for a certain range of the parameters that describe the arrival process and the service distribution. Specifically, we prove that optimal routing strategies are characterized by thresholds that are either precisely specified or take one of two possible values.     

Multi-layered round robin routing for parallel servers

We study a system of several identical servers in parallel, where a routing decision must be made immediately on a job’s arrival. Jobs arrive according to a Poisson process, with their processing times following a discrete distribution with finite support. The processing time of a job is known on arrival and may be used in the routing decision. We propose a policy consisting of multi-layered round robin routing followed by shortest remaining processing time scheduling at the servers. This policy is shown to have a heavy traffic limit that is identical to one in which there is a single queue (no routing) and optimal heavy traffic scheduling. In light traffic, we show that the performance of this policy is worse than round robin routing followed by shortest remaining processing time scheduling. We also quantify the difference between round robin and multi-layered round robin routing, which in turn yields insights on the relative importance of routing versus (local) scheduling in such systems. AMS subject classifications: 68M20 · 60K25 (Work done while both authors were visitors at EURANDOM, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.)     

Improved bounds for queues with delayed arrivals

Improved bounds are developed for a queue where arrivals are delayed by a fixed time. For moderate to heavy traffic, a simple improved upper bound is obtained which only uses the first two moments of the service time distribution. We show that our approach can be extended to obtain bounds for other types of delayed arrival queues. For very light traffic, asymptotically tight bounds can be obtained using more information about the service time distribution. While an improved upper bound can be obtained for light to moderate traffic it is not particularly easy to apply. This revised version was published online in June 2006 with corrections to the Cover Date.     

Dynamic Scheduling of a Multiclass Fluid Model with Transient Overload

We study the optimal dynamic scheduling of different requests of service in a multiclass stochastic fluid model that is motivated by recent and emerging computing paradigms for Internet services and applications. In particular, our focus is on environments with specific performance guarantees for each class under a profit model in which revenues are gained when performance guarantees are satisfied and penalties are incurred otherwise. Within the context of the corresponding fluid model, we investigate the dynamic scheduling of different classes of service under conditions where the workload of certain classes may be overloaded for a transient period of time. Specifically, we consider the case with two fluid classes and a single server whose capacity can be shared arbitrarily among the two classes. We assume that the class 1 arrival rate varies with time and the class 1 fluid can more efficiently reduce the holding cost. Under these assumptions, we characterize the optimal server allocation policy that minimizes the holding cost in the fluid model when the arrival rate function for class 1 is known. Using the insights gained from this deterministic case, we study the stochastic fluid system when the arrival rate function for class 1 is random and develop various policies that are optimal or near optimal under various conditions. In particular, we consider two different types of heavy traffic regimes and prove that our proposed policies are strongly asymptotically optimal. Numerical examples are also provided to demonstrate further that these policies yield good results in terms of minimizing the expected holding cost.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

Stability,monotonicity and invariant quantities in general polling systems

Consider a polling system withK1 queues and a single server that visits the queues in a cyclic order. The polling discipline in each queue is of general gated-type or exhaustive-type. We assume that in each queue the arrival times form a Poisson process, and that the service times, the walking times, as well as the set-up times form sequences of independent and identically distributed random variables. For such a system, we provide a sufficient condition under which the vector of queue lengths is stable. We treat several criteria for stability: the ergodicity of the process, the geometric ergodicity, and the geometric rate of convergence of the first moment. The ergodicity implies the weak convergence of station times, intervisit times and cycle times. Next, we show that the queue lengths, station times, intervisit times and cycle times are stochastically increasing in arrival rates, in service times, in walking times and in setup times. The stability conditions and the stochastic monotonicity results are extended to the polling systems with additional customer routing between the queues, as well as bulk and correlated arrivals. Finally, we prove that the mean cycle time, the mean intervisit time and the mean station times are invariant under general service disciplines and general stationary arrival and service processes.     

Optimal order for two servers in tandem

We consider two servers (serveri, i=1, 2) in tandem for which the order of servers can be changed. Server 1 has a general service time distribution and server 2 has either its shifted or truncated distribution. This permits that the service times at the two servers are overlapping. An unlimited queue is allowed in front of the first server. For the systems having zero buffer capacity between the servers, we show that the sojourn time of every customer is stochastically minimized under any arrival process if server 2 is first. For the systems with infinite buffer capacity and a Poisson arrivals, we show that this order of servers minimizes mean customer delay when traffic is light. Several numerical examples are presented to demonstrate that this optimal order is invariant under any arrival process (the interarrival times are i.i.d. r.v.'s) and mild traffic condition.Research funded by NEC Corporation C & C Laboratory.     

Dynamic Routing and Admission Control in High-Volume Service Systems: Asymptotic Analysis via Multi-Scale Fluid Limits

Motivated by applications in telephone call centers, we consider a service system model with m customer classes and r server pools. The model is one with doubly stochastic arrivals, which means that the m-vector λ of instantaneous arrival rates is allowed to vary both temporally and stochastically. Two levels of dynamic control are considered: customers may be either blocked or accepted at the time of their arrival, and then accepted customers of each class must be routed, either immediately upon acceptance or after some period of waiting, to a server pool that is qualified to handle that class. Customers who are made to wait before commencement of their service are liable to defect. The objective is to minimize the expected sum of blocking costs, waiting costs and defection costs over a fixed and finite planning horizon. We consider an asymptotic parameter regime in which (i) the arrival rates, service rates and defection rates are uniformly accelerated by a large factor κ, then (ii) arrival rates are increased by an additional factor g(κ), and the number of servers in each pool is increased by g(κ) as well. This produces a separation of time scales, justifying a pointwise stationary stochastic fluid approximation for our original system model. In the stochastic fluid approximation, optimal admission control and routing decisions are determined by a simple linear program that uses the current arrival rate vector λ as data. We explain how to implement the fluid model's optimal control policy in our original service system context, and prove that the proposed implementation is asymptotically optimal in the first-order sense. AMS subject classification: 60K30, 90B15, 90B36     

Asymptotic Analysis of a Loss Model with Trunk Reservation II: Trunks Reserved for Slow Traffic

We consider a model for a single link in a circuit switched network. The link has C circuits, and the input consists of offered calls of two types, that we call primary and secondary traffic. Of the C links R are reserved for primary traffic. We assume that both traffic types arrive as Poisson arrival streams. Assuming that C is large and   R = O (1)  , the arrival rate of secondary traffic is   O ( C )  while that of primary traffic is smaller, of the order     . The holding times of the secondary calls are assumed exponentially distributed with unit mean. Those of the primary calls are exponentially distributed with a large mean, that is     . The loads for both traffic types are thus comparable  ( O ( C ))  and we assume that the system is "critically loaded," i.e., the system's capacity is approximately equal to the total load. We analyze asymptotically the steady state probability that   n ₂  (resp.   n ₁  ) circuits are occupied by primary (resp. secondary) calls. In particular, we obtain two-term asymptotic approximations to the blocking probabilities for both traffic types. This work complements part I, where we assumed that the secondary traffic had an arrival rate that was     and a service rate that was     . Thus in part I the R trunks were reserved for the "fast traffic," whose arrival and service rates were   O ( C )  and   O (1)  .     

Second-order nonlinear least squares estimation

The ordinary least squares estimation is based on minimization of the squared distance of the response variable to its conditional mean given the predictor variable. We extend this method by including in the criterion function the distance of the squared response variable to its second conditional moment. It is shown that this “second-order” least squares estimator is asymptotically more efficient than the ordinary least squares estimator if the third moment of the random error is nonzero, and both estimators have the same asymptotic covariance matrix if the error distribution is symmetric. Simulation studies show that the variance reduction of the new estimator can be as high as 50% for sample sizes lower than 100. As a by-product, the joint asymptotic covariance matrix of the ordinary least squares estimators for the regression parameter and for the random error variance is also derived, which is only available in the literature for very special cases, e.g. that random error has a normal distribution. The results apply to both linear and nonlinear regression models, where the random error distributions are not necessarily known.     

On effects of arrival rate and burstiness in the queueing system: Analysis ofLb/D/1

This paper studies a single-server queueing system with deterministic service time in which arrivals are regulated by the leaky-bucket mechanism. This paper intends to improve quantitative understanding of the effects of arrival rate and burstiness on the average delay of queueing systems. The study is directed toward identifying the worst traffic of arrivals allowed by the leaky-bucket regulation and clarifying the effects of the leaky bucket parameters (which represent the arrival rate and burstiness) on the average queueing delay. The arrival traffic that maximizes the average queueing delay is characterized as the repetition of the following three phases: bulky arrival, greedy arrival for a specified length of interval, and then no arrival till the token bucket is full. The average queueing delay for the worst traffic is expressed as a function the leaky bucket parameters.Research was partially supported by the NSF under grant ECS-8552419. Research was conducted at the Laboratory for Information and Decision Systems of the Massachusetts Institute of Technology and the U.S. Naval Research Laboratory.     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

Optimal Flow Control of a G/G/c Finite Capacity Queue

The optimal flow control of a G/G/c finite capacity queue is investigated by approximating the general (G-type) distributions by a maximum entropy model with known first two moments. The flow-control mechanism maximizing the throughput, under a bounded time-delay criterion, is shown to be of window type (bang-bang control). The optimal input rate and the maximum number of packets in the system (i.e. sliding window size) are derived in terms of the maximum input rate and the second moment of the interinput time, the maximum allowed average time delay, the first two moments of the service times and the number of servers. Moreover, the relationship between the maximum throughput and maximum time delay is determined. Numerical examples provide useful information on how critically the optimal throughput is affected by the distributional form of the input and service patterns and the finite capacity of the queue.     

Convexity properties,moment inequalities and asymptotic exponential approximations for delay distributions in G1/G/1 systems

Pollaczek distributions pervade the class of delay distibutions in G1/G/1 systems with concave service time distributions. When the service time distribution has finite support and the delay distribution is absolutely continuous on (0, ∞), one can find a distribution with a pure exponential tail that satisfies the corresponding Wiener-Hopf integral equation except for values of the argument that belong to the support in question or to a translate thereof. Again for an exponentially decaying delay distribution, one can formulate sufficient moment inequalities which ensure the existence of asymptotic upper and lower bounds derived from M/D/1 and M/M/1 delay distributions which agree with the former in terms of the first two moments.     

Towards an Erlang formula for multiclass networks

Consider a multiclass stochastic network with state-dependent service rates and arrival rates describing bandwidth-sharing mechanisms as well as admission control and/or load balancing schemes. Given Poisson arrival and exponential service requirements, the number of customers in the network evolves as a multi-dimensional birth-and-death process on a finite subset of ℕ ^k . We assume that the death (i.e., service) rates and the birth rates depending on the whole state of the system satisfy a local balance condition. This makes the resulting network a Whittle network, and the stochastic process describing the state of the network is reversible with an explicit stationary distribution that is in fact insensitive to the service time distribution. Given routing constraints, we are interested in the optimal performance of such networks. We first construct bounds for generic performance criteria that can be evaluated using recursive procedures, these bounds being attained in the case of a unique arrival process. We then study the case of several arrival processes, focusing in particular on the instance with admission control only. Building on convexity properties, we characterize the optimal policy, and give criteria on the service rates for which our bounds are again attained.