On-line routing of random calls in networks

 We consider a random sequence of calls between nodes in a complete network with link capacities. Each call first tries the direct link. If that link is saturated, then the `first-fit dynamic alternative routing algorithm' sequentially selects up to d random two-link alternative routes, and assigns the call to the first route with spare capacity on each link, if there is such a route. The `balanced dynamic alternative routing algorithm' simultaneously selects d random two-link alternative routes; and the call is accepted on a route minimising the maximum of the loads on its two links, provided neither of these two links is saturated. We determine the capacities needed for these algorithms to route calls successfully, and find that the second `balanced' algorithm requires a much smaller capacity. Our results strengthen and extend the discrete-time results presented in [10]. Received: 10 January 2002 / Revised version: 7 July 2002 / Published online: 28 March 2003     

The selection and scheduling of telecommunication calls with time windows

We consider the bandwidth scheduling problem that consists of selecting and scheduling calls from a list of available calls to be routed on a bandwidth-capacitated telecommunication network in order to maximize profit. Each accepted call should be routed within a permissible scheduling time window for a required duration. To author's knowledge, this study represents the first work on bandwidth scheduling with time windows. We present an integer programming formulation of the problem. We also propose a solution procedure based on the well-established Lagrangean relaxation technique. The results of extensive computational experiments over a wide range of problem structures indicate that the procedure is both efficient and effective.     

Sharp estimates and a central limit theorem for the invariant law for a large star-shaped loss network

Calls arrive in a Poisson stream on a symmetric network constituted of N links of capacity C. Each call requires one channel on each of L distinct links chosen uniformly at random; if none of these links is full, the call is accepted and holds one channel per link for an exponential duration, else it is lost. The invariant law for the route occupation process has a semi-explicit expression similar to that for a Gibbs measure: it involves a combinatorial normalizing factor, the partition function, which is very difficult to evaluate. We study the large N limit while keeping the arrival rate per link fixed. We use the Laplace asymptotic method. We obtain the sharp asymptotics of the partition function, then the central limit theorem for the empirical measure of the occupancies of the links under the invariant law. We also obtain a sharp version for the large deviation principle proved in Graham and O'Connell (Ann. Appl. Probab. 10 (2000) 104).     

Structural properties and stochastic bounds for a buffer problem in packetized voice transmission

We consider a communication channel which carries packetized voice. A fixed number (K) of calls are being transmitted. Each of these calls generates one packet at everyC timeslots and the channel can transmit at most one packet every timeslot. We consider the nontrivial caseK ≤C. We study the effectsK, C and the arrival process have on the number of packets in the buffer. When the call origination epochs in the firstC timeslots of theK calls are uniformly distributed (i.e. when the arrivals during the firstC timeslots have a multinomial distribution) it is shown that the stationary number of calls waiting in the buffer is stochastically increasing and convex in the number of calls. For a fixed average number of calls per slot, it is shown that increasing the number of slots per frame increases the stationary number of packets in the buffer in the sense of increasing convex ordering. Using this, it is shown that the stationary number of packets in the buffer is bounded from above by the number of packets in a stationary discreteM/D/1 queue with arrival rateK/C and unit service time. This bound is in the sense of the increasing convex order.     

Dial-Up Internet Access: A Two-Provider Cost Model

We present a cost model for splitting Internet dial-up traffic (which varies by time-of-day) between two large modem banks. One of the modem banks charges by the hour, the other charges for the peak number-in-system during the day. To study if the possible savings are enough to make the effort worthwhile, we formulate a clairvoyant (“perfect information”) Integer Program that is equivalent to a network flow problem. This leads us to use a ceiling policy. In the stochastic control case, we use a Modified Offered Load (MOL) approximation to explore the properties of the system, and develop a square-root-type rule to set the ceiling in the homogeneous case. We also use simulation to determine an optimal ceiling when we cannot route individual calls precisely. We propose approximations that may be computed for any call duration distribution, and compare their answers to exact differential-equation procedures for Exponential call durations. AMS subject classification: 60K25, 90B18, 68M20, 90B22, 60K30     

A generalization of the Erlang formula of traffic engineering

Calls arrive at a switch, where they are assigned to any one of the available idle outgoing links. A call is blocked if all the links are busy. A call assigned to an idle link may be immediately lost with a probability which depends on the link. For exponential holding times and an arbitrary arrival process we show that the conditional distribution of the time to reach the blocked state from any state, given the sequence of arrivals, is independent of the policy used to route the calls. Thus the law of overflow traffic is independent of the assignment policy. An explicit formula for the stationary probability that an arriving call sees the node blocked is given for Poisson arrivals. We also give a simple asymptotic formula in this case.Work on this paper was done while the author was at Bellcore and at Berkeley.     

Optimal trunk reservation for an overloaded link

We consider a single overloaded link with a large number of circuits which is offered two kinds of calls. The traffic intensity of the primary calls is assumed to be strictly less than 1, and R of the circuits are reserved for these. Rewards are generated when calls are accepted, and it is assumed that the reward for primary calls is greater than that for secondary calls. We determine the trunk reservation parameter R which asymptotically maximizes the long run average reward.     

Optimal static pricing for a tree network

We study the static pricing problem for a network service provider in a loss system with a tree structure. In the network, multiple classes share a common inbound link and then have dedicated outbound links. The motivation is from a company that sells phone cards and needs to price calls to different destinations. We characterize the optimal static prices in order to maximize the steady-state revenue. We report new structural findings as well as alternative proofs for some known results. We compare the optimal static prices versus prices that are asymptotically optimal, and through a set of illustrative numerical examples we show that in certain cases the loss in revenue can be significant. Finally, we show that static prices obtained using the reduced load approximation of the blocking probabilities can be easily obtained and have near-optimal performance, which makes them more attractive for applications.     

Designing a call center with an IVR (Interactive Voice Response)

A call center is a service operation that caters to customer needs via the telephone. Call centers typically consist of agents that serve customers, telephone lines, an Interactive Voice Response (IVR) unit, and a switch that routes calls to agents. In this paper we study a Markovian model for a call center with an IVR. We calculate operational performance measures, such as the probability for a busy signal and the average wait time for an agent. Exact calculations of these measures are cumbersome and they lack insight. We thus approximate the measures in an asymptotic regime known as QED (Quality and Efficiency Driven) or the Halfin–Whitt regime, which accommodates moderate to large call centers. The approximations are both insightful and easy to apply (for up to 1000’s of agents). They yield, as special cases, known and novel approximations for the M/M/N/N (Erlang-B), M/M/S (Erlang-C) and M/M/S/N queue.     

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)  .     

Loss circuit switched communication network-performance analysis and dynamic routing

We investigate a loss circuit switched communication network with state-dependent dynamic routing strategy, wherein the state of the network at the time of call arrival determines whether or not the call is accepted and, if accepted, its route. We develop an approximate approach to the network performance analysis. The approach enhances the Fixed Point Model by treating multiple solutions of the Fixed Point Equations. Assuming that the multiple solutions correspond to the long-living network modes, we develop the aggregated Markov chain that describes the network transitions among these modes. We also propose and discuss a new state-dependent dynamic routing strategy which we call Least-Expected-Blocking strategy (LEB). LEB accepts an incoming call only if this results in a decrease in the expected blocking probability and it chooses a route that yields the maximum decrease. The new strategy outperforms the previously known strategies by the criterion of network steady blocking probability.     

The role of preparedness in ambulance dispatching

Response time in the emergency medical service is an important performance measure and ambulance dispatching is one of the most important factors affecting the response time. The most commonly used dispatching rule is to send the closest available unit to the call site. However, though dispatching the closest unit enables the service to achieve the minimal response time for the current call, the response times for the next incoming calls may increase if the area where the closest ambulance is currently located has a high call rate, that is the area becomes ill-prepared. A dispatching algorithm based on the preparedness concept was recently proposed. Rather than greedily minimizing each current response time, the dispatching algorithm takes account of future calls by a quantitative definition of preparedness. This study investigates the role of preparedness by examining the performance of the preparedness-based dispatching algorithm as well as by evolving the algorithm in several ways in order to magnify the effectiveness of preparedness consideration. As a result of these efforts, it is found that the consideration of preparedness in ambulance dispatching can provide significant benefits in reducing response time but only when appropriately used.     

Coordinated decisions for substitutable products in a common retailer supply chain

This paper studies coordination mechanisms in a supply chain which consists of two suppliers with capacity uncertainties selling differential yet substitutable products through a common retailer who faces price-sensitive random demand of these two products. We develop in a noncompetitive setting three coordination models – revenue sharing, return policy, and combination of revenue sharing and return policy – and contrast them with a basic and uncoordinated model. We are able to establish the ordinal relationship among the retailer’s ordering and pricing decisions and analytically compare the performances between certain models when two suppliers are identical. We find that the retailer’s ordering and pricing decisions in the model with return policy in the case of identical suppliers are independent of demand or supply uncertainty. Our numerical results reveal that the performances of coordination models in the case of nonidentical suppliers resemble those in the case of identical suppliers. We find that the retailer will place a larger order quantity in models where her average cost per unit sold is smaller. We also find that product substitutability and uncertainties have different effects on chain performances.     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Predictive Model for the Police Response Function

The expected response time to a call for service (CFS) for a given configuration of police beats is developed. The effect of downtime calls on the response time to a CFS is determined. Consideration is given to both travel time and waiting time. Travel time and service time distributions are isolated. The model is valid for Poisson arrivals and arbitrary service time distributions. A probabilistic assignment policy is determined for each beat. The fraction of incoming calls arriving in beat k answered by unit l is obtained. Pre-emptive priorities are allowed. Application to the Aurora, Illinois, Police Department is shown.     

Pricing American currency options in an exponential Lévy model

In this article the problem of the American option valuation in a Lévy process setting is analysed. The perpetual case is first considered. Without possible discontinuities (i.e. with negative jumps in the call case), known results concerning the currency option value as well as the exercise boundary are obtained with a martingale approach. With possible discontinuities of the underlying process at the exercise boundary (i.e. with positive jumps in the call case), original results are derived by relying on first passage time and overshoot associated with a Lévy process. For finite life American currency calls, the formula derived by Bates or Zhang, in the context of a negative jump size, is tested. It is basically an extension of the one developed by Mac Millan and extended by Barone‐Adesi and Whaley. It is shown that Bates' model generates pretty good results only when the process is continuous at the exercise boundary.     

A simple heuristic for load balancing in parallel processing networks with highly variable service time distributions

Suppose that customers arrive at a service center (call center, web server, etc.) with two stations in accordance with independent Poisson processes. Service times at either station follow the same general distribution, are independent of each other and are independent of the arrival process. The system is charged station-dependent holding costs at each station per customer per unit time. At any point in time, a decision-maker may decide to move, at a cost, some number of jobs in one queue to the other. The goals of this paper are twofold. First, we are interested in providing insights into this decision-making scenario. We do so, in the important case that the service time distribution is highly variable or simply has a heavy tail. Secondly, we propose that the savvy use of Markov decision processes can lead to easily implementable heuristics when features of the service time distribution can be captured by introducing multiple customer classes. To this end, we consider a two-station proxy for the original system, where the service times are assumed to be exponential, but of one of two classes with different rates. We prove structural results for this proxy and show that these results lead to heuristics that perform well.     

Equitable transit charges for multiadministration telecommunications networks

We study a multi-administration telecommunications network that is an abstraction of an international network. The nodes represent separate telecommunications administrations that are linked such that alternately-routed calls go through one tandem administration. The cost of the group of circuits between a pair of administrations is borne by them; and when a call between the pair is alternately routed through the tandem node, then the two administrations share the call revenue and pay transit fees to the tandem administration. The numbers of circuits between the administrations are selected to yield a least-cost network that provides a desired level of service, in terms of blocking probabilities, over an entire day. We address the problem of determining transit charges for the alternately-routed calls that are equitable for all of the administrations. Our approach is to derive such charges by equating the system-optimal circuit group sizes to certain hypothetical administration-optimal circuit group sizes. This approach may be of use in other system design problems involving cost sharing among several companies.This research was supported in part by Grant AFOSR 84-0367.     

A Stackelberg Network Game with a Large Number of Followers

We consider a hierarchical network game with multiple links, a single service provider, and a large number of users with multiple classes, where different classes of users enter the network and exit it at different nodes. Each user is charged by the service provider a fixed price per unit of bandwidth used on each link in its route, and chooses the level of its flow by maximizing an objective function that shows a tradeoff between the disutility of the payment to the service provider and congestion cost on the link the user uses, and the utility of its flow. The service provider, on the other hand, wishes to maximize the total revenue it collects. We formulate this problem as a leader-follower (Stackelberg) game, with a single leader (the service provider, who sets the price) and a large number of Nash followers (the users, who decide on their flow rates). We show that the game admits a unique equilibrium, and obtain the solution in analytic form. A detailed study of the limiting case where the number of followers is large reveals a number of interesting and intuitive properties of the equilibrium, and answers the question of whether and when the service provider has the incentive to add additional capacity to the network in response to an increase in the number of users on a particular link.     

M/G/1 retrial queueing systems with two types of calls and finite capacity

We consider anM/G/1 priority retrial queueing system with two types of calls which models a telephone switching system and a cellular mobile communication system. In the case that arriving calls are blocked due to the server being busy, type I calls are queued in a priority queue of finite capacityK whereas type II calls enter the retrial group in order to try service again after a random amount of time. In this paper we find the joint generating function of the numbers of calls in the priority queue and the retrial group in closed form. When ₁=0, it is shown that our results are consistent with the known results for a classical retrial queueing system.