**Properties of the Virtual Queue Marking Algorithm (2001)**

Richard J. Gibbens, Peter B. Key & Stephen R. E. Turner

17th UK Teletraffic Symposium, Institution of Electrical Engineers**Abstract**- This paper explores the virtual queue marking algorithm in the context of distributed congestion control for packet networks. Queueing models and simulation experiments are used to describe the behaviour of the virtual queue marking algorithm under both slowly-varying and sudden changes in traffic demands.
**Download**- PDF (445kb) | Postscript (1.5Mb) | Gzipped Postscript (330kb)

**Large Deviations for Join the Shorter Queue (2000)**

Stephen R. E. Turner

Analysis of Communication Networks: Call Centres, Traffic and Performance, Fields Institute Communications volume 28, ed. D. R. McDonald & S. R. E. Turner, 95-108. AMS.**Abstract**- We consider large deviations results for a network of two
queues in which some customers may join the shorter queue at
arrival time. The queues may be ./
*M*/infinity or ./*M*/1 queues. We consider the case in which the routeable customers join the queue with the shorter expected waiting time, as well as that in which they join the queue with the fewer customers. This paper is partly a survey of existing results, and partly new material. One distinctive feature of our presentation is the phrasing of the results in terms of resource pooling. **Download**- PDF (208kb) | Postscript (212kb) | Gzipped Postscript (81kb)

**Comparing Load Balancing Algorithms for Distributed Queueing Networks (2000)**

David R. McDonald & Stephen R. E. Turner

Analysis of Communication Networks: Call Centres, Traffic and Performance, Fields Institute Communications volume 28, ed. D. R. McDonald & S. R. E. Turner, 109-133. AMS.**Abstract**- We consider a network serving a patchwork of overlapping regions
where jobs from a local region are assigned to a collection of
local servers. Copies of these jobs are simultaneously queued at
all the local servers. When a copy of the job begins service
at one of the servers it is removed from the other queues. The
system is equivalent to one in which the exact service requirement
of each job is known at arrival time, and each job joins the local
queue with the shortest waiting time.
We describe how the amount of work in the network becomes large in the simple case of two servers, with one arrival stream for each server and a third, routeable arrival stream. If the proportion of routeable jobs is large enough then the waiting times at the servers become large in tandem when the total workload becomes large, thus delaying overload as long as possible. The fact that this resource pooling can be attained with a local routing policy not dependent on the state of the network has engineering significance for load sharing among distributed call centres.

We also compare this `join the shorter actual waiting time' policy (JSAW) with a join the shorter expected waiting time policy and join the shorter queue. For some overflow events, we find that the performance of all three policies is roughly the same in the sense that the probability of an overflow has the same exponential decay rate under any policy. Although the JSAW policy is the best, in these cases its probability of overflow is only the lowest by a subexponential factor. However, for other overflow events we find that the JSAW policy is substantially better.

**Download**- PDF (286kb) | Postscript (383kb) | Gzipped Postscript (128kb)

**A Join the Shorter Queue Model in Heavy Traffic (2000)**

Stephen R. E. Turner

Journal of Applied Probability,**37**, 212-223**Abstract**- We prove a new heavy traffic limit result for a simple queueing network under a "join the shorter queue" policy, with the amount of traffic which has a routeing choice tending to zero as heavy traffic is approached. In this limit, the system considered does not exhibit state space collapse as in previous work by Foschini & Salz, and Reiman, but there is nevertheless some resource pooling gain over a policy of random routeing.

**The Effect of Increasing Routing Choice on Resource Pooling (1998)**

Stephen R. E. Turner

Probability in the Engineering and Informational Sciences,**12**, 109-124**Abstract**- We consider a network of
*N*identical ./*M*/1 or ./*M*/infinity queues. There are two types of arriving customers, those that have no routing choice, and those that first pick*r*queues at random, and are then routed to the least busy of those queues. We derive the limiting distribution of queue lengths as*N*tends to infinity, and investigate how this distribution varies with*r*. We show that even a small amount of routing choice can lead to substantial gains in performance through resource pooling. We corroborate these conclusions by carrying out some simulations of a related model, from which the previous model can be derived by an exchangeable queue simplification. We also observe that the exchangeable queue simplification results in a performance gain for some parameters, in contrast to earlier work.

**Call Routing in Telephone Networks (1997)**

Richard J. Gibbens & Stephen R. E. Turner*PASS Maths*, issue 2**Available on line**- HTML

**Resource Pooling in Stochastic Networks (1996)**

Stephen R. E. Turner

Ph.D. dissertation, University of Cambridge

**Download**- PDF (1.2Mb) | Postscript (2Mb) | Gzipped Postscript (538kb)

**Unwrapping Noisy Phase Maps by Use of a Minimum-Cost-Matching Algorithm (1995)**

Justin R. Buckland, Jon M. Huntley & Stephen R. E. Turner

Applied Optics,**34**, 5100-5108

**Abstract**- An algorithm for unwrapping noisy phase maps by means of branch cuts has been proposed recently. These cuts join discontinuity sources that mark the beginning or end of a 2 pi phase discontinuity. After the placement of branch cuts, the unwrapped phase map is unique and independent of the unwrapping route. We show how a minimum-cost-matching graph-theory method can be used to find the set of cuts that has the global minimum of total cut length, in time approximately proportional to the square of the number of sources. The method enables one to unwrap unfiltered speckle-interferometry phase maps at higher source densities (0.1 sources per pixel) than any previous branch-cut placement algorithm.

**Modelling Interest Rates and Assessing Risk of Derivative Securities (1993)**

Stephen R. E. Turner

Project for the Diploma in Mathematical Statistics, University of Cambridge Statistical Laboratory

**Abstract**- The problem of how to model interest rates is important to financial institutions, but is currently not well understood. In this report, both the term structure of rates at a given time and the evolution of rates over time are examined. An Ornstein-Uhlenbeck model is used for the evolution of rates, and the risk inherent in various securities is assessed.

**Dynamic Routing in Multiparented Networks (1993)**

Frank P. Kelly, Richard J. Gibbens & Stephen R. E. Turner*IEEE/ACM Transactions on Networking*,**1**, 261-270

**Abstract**- In this paper, we investigate some of the consequences for dynamic routing schemes of dual- and multiparented networks, in which a call can enter (or leave) the network at two or more points. In particular, we compare bounds on the performance of optimal dynamic routing strategies which respectively ignore and utilize the multiparented structure, and show that simple schemes, easily implemented and analyzed, are able to achieve most of the additional advantages allowed to dynamic rotuing schemes by multiparenting. Further, we illustrate the robust behaivor of these schemes under traffic mismatches as well as multiple link or node failure events.

**Sticky Random Routing in Dual-Parented Networks (1991)**

Richard J. Gibbens & Stephen R. E. Turner

8th UK Teletraffic Symposium, Institution of Electrical Engineers, pgs. 6/1-6/5**Abstract**- We consider the application of dynamic routing strategies to dual-parented networks. Dual-parented networks consist of a fully connected set of nodes, called parent nodes, together with clusters of local nodes connected in each case to two parent nodes. The number of clusters is the same as the number of parent nodes. Such network architectures resemble the upper tiers of the British Telecom national trunk network. We report on investigations to study simple, decentralized routing strategies which generalize the DAR strategy from the fully connected network to the dual-parented network. We employ both analytical and simulation models of our routing strategies. The analytical models are based on fixed point calculations using the familar independent link blocking approximation. A notable feature of dynamic routing in this network architecture is the degree of robustness that it is possible to achieve against traffic overloads and link failures using a simple, decentralized approach to routing.

Stephen Turner

Email: s.r.e.turner at gmail.com

Page last modified: 17-Oct-08