Ernst Biersack (Institut EURECOM, France) . Powerpoint Slides from Talk .

Title: Modeling of LAS-based scheduling polices in packet switched networks

Abstract: In recent years there has been an increased interest in size-based scheduling policies such as SRPT (Shortest Remaining Processing Time) that was motivated by empirical observations showing that job sizes are heavy-tailed or at least have a coefficient of variation larger than one. In this case, SRPT as compared to FCFS can significantly reduce the response time of short jobs without too much penalizing large jobs. However, SRPT requires the jobs size to be known ahead of time, which is not always the case. For this reason, we have been studying LAS (Least Attained Service) scheduling policies that give service to the job in the system that has so far received the least amount of service. We are interested in using LAS in packet switched networks and develop analytical models to asses its performance. LAS scheduling up to now has been analyzed for jobs that arrive to the server all at once. However, in packet switched networks, LAS is applied to flows; a flow being defined as a sequence of packets that are exchanged between two particular end-points. While a job arrives to the server all at once, the packets of a flow arrive to the router at disparate points of time. We show how to model LAS in packet switched networks and we introduce a family of Two-Class LAS policies, for which the service priority of packets in the regular class (class 1) is computed as under (plain) LAS, while the service priority of packets in the priority class (class 2) is computed using a policy function P(x). We discuss the performance for several of these policy functions and show that a logarithmic policy function greatly improves the mean flow transfer time for priority long flows while providing performance similar to (plain) LAS for regular flows.

Co-authors: Idris Rai, Guillaume Urvoy-Keller, and Mary Vernon

Short bio: Ernst Biersack has received his M.S. and Ph.D. degrees in Computer Science from the Technische Universitaet Muenchen, Munich, Germany and his "Habilitation a diriger la Recherche" from the University of Nice Sophia Antipolis. From 1989 to 1992 he was a Member of Technical Staff of Bell Communications Research in Morristown, US. Since then he has been a Professor in Telecommunications at Institut Eurecom, in Sophia Antipolis, France. His research interest is in the area of design and evaluation of scalable protocols and mechanisms for the Internet. His research covers topics such as Multicast Error and Congestion Control, Caching and Content Distribution Networks, Scalable Video Distribution on the Internet, Peer-to-Peer Systems, Network Tomography, and Scheduling in Edge Routers.

Interest areas in multiserver scheduling: Scheduling policies in packet networks, fairness, load balancing

Papers relevant to talk: Click Here

Ed Coffman (Columbia University, U.S.) .

Title: Combinatorial Service Disciplines in the Multi-Server Queue

Abstract: We consider multi-server queues where optimal customer scheduling solves NP-hard packing and fragmentation problems, and where the infinite server queue models arrivals and departures. Illustrative applications are bandwidth packing, reservation systems, channel re-use in LANs, and dynamic storage allocation. These problems are as well or better known for intriguing open questions, which will be the focus of the talk, than they are for strong results with substantial generality.

Co-authors: ....Far too many to name

Short bio: Professor Coffman rejoined the Columbia University E.E. faculty in the summer of 2000. During most of the period since his first appointment at Columbia, he spent 20 years at Bell Labs in Murray Hill, NJ. He is an IEEE Fellow (and Life Member), an ACM Fellow, and a Distinguished Member of Technical Staff (ret.) at Bell Labs. He is currently an editor for the Journal of Interconnection Networks and the Journal of Algorithms. In the past, he has also served as an editor for the Journal of the ACM, SIAM Journal of Computing, among others. He is one of the five system programmers who built the SDC/ARPA time-sharing system, which became fully operational at the same time (1963) as the CTSS system at MIT. The SDC/ARPA time-sharing system also introduced the first computer network at that time.

Interest areas in multiserver scheduling: Interests are very broad.

Papers relevant to talk: Click Here

Daryl Daley (Australian National University). Slides from talk in pdf and in postscript .

Title: Classical k-server queues revisited: some problems

Abstract: The talk surveys both recent and `classical' studies of k-server queueing systems, and will include reference to some of the following problem areas.

1. EXISTENCE. -- Kiefer and Wolfowitz' (1955) proof of the existence of a stationary regime for the GI/GI/k FCFS system relies on `An Essential Lemma'. In reality it hinges on a strong law of large numbers, of which variants are useful in a range of problems including k-fast servers and the tail behaviour of the work-load vector. It depends on ergodicity and not the independence assumptions of GI/GI/k (cf. Loynes' Lemma and Construction).

2. CYCLES. -- Much work on busy period analysis has relied on either regeneration points or weakened versions of them. The prime underlying result again is one of ergodicity and stationarity, and exploits ideas of point processes, albeit subsequent to Khinchin's (1955) monograph.

3. MOMENTS. -- The fact that a sub-minimally stable GI/GI/k system has finite mean delay when E(S^{3/2})< infinity for a generic service-time r.v. S is now better understood. An intermediate result concerns the moment index kappa(X) = sup{k : E(X^k)< infinity } of independent r.v.s X and Y, with kappa(min(X,Y)) > = kappa(X) + kappa(Y). Equality holds if X has a d.f. with a regularly varying tail, but the class is a little larger than this.

4. EXPONENTIAL SYSTEMS. -- Let two identical ./M/1 systems be fed by the same Poisson arrival process: what is their joint stationary distribution, and correlation of the queue sizes? Alan Brown has conjectured the structure of the d.f. sufficient for use with an expression for the stationary bivariate p.g.f.: is there any `routine' approach to circumvent the relative intractability of such simple systems?

5. HEAVY TAILS. -- The same dichotomy between minimally and sub-minimally stable systems as occurs for moment behaviour affects the asymptotic tail-behaviour of the work-load vector when the service-time d.f. is heavy-tailed.

6. SECOND-ORDER PROPERTIES. -- The stationary waiting-time sequence {W_n} in a single-server system has corr(W_0, W_n) monotonic decreasing in n, and its Hurst index is a simple function of the moment index of service times. Does monotonicity hold in GI/GI/k? And what is the Hurst index of corr(W_0,W_n): is it affected by the system being minimally stable or not?

Short bio: Daryl Daley is a Senior Fellow in the Institute of Advanced Studies at the Australian National University where he has been since 1970, now located in the Centre for Mathematics and its Applications. His interests are in applied probability generally, including Point Processes (joint author with David Vere-Jones of An Introduction to the Theory of Point Processes ), Mathematical Epidemic Modelling (joint author with Joe Gani of Epidemic Modelling: An Introduction ), Stochastic Geometry (papers with Dietrich Stoyan and others), and Queueing Theory (including work with Les Servi on telecommunication modelling problems and Tomasz Rolski on light-traffic, and review papers on outputs (1976), mean waiting-times (1992) and work-load vectors (1997)).

Interest areas in multiserver scheduling: queueing problems in general.

Papers relevant to talk: Click Here

Peter Glynn (Stanford University, U.S.) . Slides from Talk in pdf .

Title: Heavy-Traffic Approximations for Many-Server and Multi-Server Systems

Abstract: We will discuss some new heavy-traffic approximations in both the multi-server setting and the many-server setting. In the many-server context, we will describe some formulae for how to optimally split traffic between two servers on the basis of observed job size and on the basis of predicted job size. These results complement recently derived formulae for Poisson arrival streams, and are based on an assumption of "heavy-traffic". We will then turn to discussion of heavy-traffic limit theory in the many-server setting (in which the number of servers is infinite or large as compared to the arrival rate, which is also assumed to be large). We will describe a new extension of the classical Gaussian heavy-traffic limit theory to the setting of non-stationary traffic, and we will further discuss some related modeling implications.

Co-authors: Kavita Ramanan, Yuqing Sun

Short bio: Peter Glynn received his Ph.D in Operations Research from Stanford University in 1982. He then joined the faculty of the University of Wisconsin at Madison,where he held a joint appointment between the Industrial Engineering Department and Mathematics Research Center, and courtesy appointments in Computer Science and Mathematics. In 1987, he returned to Stanford, where he is now the Thomas Ford Professor of Engineering in the Department of Management Science and Engineering. He also has a courtesy appointment in the Department of Electrical Engineering. He is a Fellow of the Institute of Mathematical Statistics and has research interests in computational probability, queueing theory, statistical inference for stochastic processes, and stochastic modeling.

Interest areas in multiserver scheduling: multi-server queues, many-server queues, limit theorems, approximations

Mor Harchol-Balter (CMU, U.S.) . Powerpoint slides from Introduction talk and Powerpoint slides from talk .

Title: New Recursive Dimensionality Reduction Technique applied to the analysis of multiserver scheduling policies including: Cycle Stealing, Priority Queueing, Task Assignment, and Threshold Policies (Part I)

Abstract: We consider common scheduling policies for multiserver systems including cycle stealing policies, priority queuing, task assignment policies, and threshold policies. Even these simple policies are already very difficult to analyze because their underlying Markov chain structure grows infinitely in more than one dimension -- the dimension of the Markov chain is typically equal to the number of servers. We introduce a new analysis technique which we call Recursive Dimensionality Reduction (RDR) which allows us to reduce an n-dimensionally inifinite Markov chain to a 1-dimensionally infinite Markov chain which can then be solved via numerical methods. We apply RDR to analyze the above scheduling policies, leading to new insights about these policies and proposals for improved policies.

Co-authors: Taka Osogami, Alan Scheller-Wolf, Mark Squillante

Short bio: Mor Harchol-Balter received a Ph.D. in Computer Science from the University of California at Berkeley in December 1996 under the direction of Manuel Blum. From 1996-1999, Mor was awarded the NSF Postdoctoral Fellowship in the Mathematical Sciences at M.I.T. In the Fall of 1999, she joined CMU, and in 2001 received the McCandless Chair. Mor is also a recipient of the NSF CAREER award and the Herbert A. Simon Award for Teaching Excellence. Mor is heavily involved in the ACM SIGMETRICS research community. Mor's work focuses on designing new scheduling/resource allocation policies for various distributed computer systems including Web servers, distributed supercomputing servers, networks of workstations, and database systems. Her work spans both analysis and implementation and emphasizes integrating measured workload distributions into the problem solution. She derives often counter-intuitive theorems in the areas of scheduling theory, queueing theory, and heavy-tailed workloads and applies these theorems in building servers with improved performance.

Interest areas in multiserver scheduling: Threshold policies, analysis of scheduling policies in multiserver systems, systems with time-varying load, job scheduling in supercomputing centers, analysis of Web server farms, multi-resource modeling in databases, fairness of scheduling policies.

Papers relevant to talk: Click Here

Helen D. Karatza (Aristotle University of Thessaloniki, Greece) . Slides from talk in pdf .

Title: Performance Analysis of Scheduling Strategies in Distributed Systems

Abstract: Distributed systems pose challenging problems and require proper scheduling in order to efficiently serve users. This presentation summarizes recent research into the performance of scheduling strategies on distributed systems. Topic relating to various aspects of distributed system scheduling are included. The technique used to evaluate the performance of scheduling strategies is experimentation using synthetic workload simulation. Open and closed queueing network models of distributed systems are considered.

In addition to traditional methods of load sharing and temporal job scheduling, two other methods are presented called epoch load sharing and epoch scheduling . Epoch load sharing evenly distributes the load mong distributed processors and performs job migration, but only at the end of predefined intervals. The time interval between successive load sharing events is called an epoch . In epoch scheduling, job priorities in processor queues are recalculated at the end of epochs when queues are rearranged.

Most parallel job scheduling research assumes that parameters such as job inter-arrival times, number of tasks per job and task service demans are defined by specific distributions, but we also consider distributed systems with time varying workloads. We examine scheduling of parallel jobs which consist of independent tasks that can execute at any time on any processor, as well as gang scheduling. Finally, the impact of workload parameterics on performance metrics is examined.

Short bio: Helen D. Karatza is an Associate Professor in the Department of Informatics at the Aristotle University of Thessaloniki, Greece. Her research interests mainly include Performance Evaluation of Parallel and Distributed Systems, Multiprocessor Scheduling, and Simulation. Dr. Karatza is area Editor for computer systems of the Journal of Systems and Software (Elsevier), a member of the Editorial Board of the Simulation Modelling Practice and Theory Journal (Elsevier), a member of the Editorial Board of the International Journal of Simulation: Systems, Science & Technology (the UK Simulation Society), and Associate Editor of the Journal Simulation: Transactions of the Society for Modeling and Simulation International (Applications Section). She has served as a member of Program Committees and Program Chair of many Simulation/Performance/Parallel and Distributed Systems related International Conferences/Symposia. Her email and web address are , and .

Interest areas in multiserver scheduling: Load balancing, load sharing, task assignment and task scheduling policies.

Papers relevant to talk: Click Here

John Lehoczky (Carnegie Mellon University, U.S.) . Powerpoint slides from talk .

Title: Heavy Traffic Limit Theorems for Real-Time Computer Systems

Abstract: Real-time computer and communication systems process tasks (or packets) that have explicit deadlines. One important system design goal is to determine if the deadlines of those tasks can be met under various workload conditions. Real-time scheduling theory is one approach that addresses these problems, but this theory is based on worst case assumptions. If the average case utilization is much less than the worst case utilization, then standard methods will lead to a substantial under-utilization of the system. Real-time queueing theory is a new methodology for studying real-time systems using the moments of the distributions governing the arrival and service processes rather than their worst-case bounds. It utilizes heavy traffic queueing theory to predict the faction of tasks that will miss their deadlines. If the workload process converges weakly to a possibly multi-dimensional Brownian motion process, then the lead-time process of customers (the time until their deadlines elapse) converges to a deterministic form from which the fraction of task lateness can be determined. This talk will focus largely on the single node case with single and multiple traffic flows. Various scheduling policies will be considered including earliest deadline first, FIFO, and generalized processor sharing (or weighted fair queueing) for the multiple flow case. Extensions to feed-forward and acyclic networks will be mentioned.

Co-authors: Bogdan Doytchinov, Lukasz Kruk, Steve Shreve, and Shu-Ngai Yeung

Short bio: John Lehoczky is Thomas Lord Professor of Statistics and Mathematical Science and Dean of the College of Humanities and Social Sciences at Carnegie Mellon. He received his Ph.D. in Statistics from Stanford University in 1969 and joined Carnegie Mellon that year. His current research interests are in real-time queueing theory and its application to computer and communication systems and in computational finance.

Interest areas in multiserver scheduling: Real-time systems, scheduling, heavy traffic queueing

Papers relevant to talk: To be supplied later.

Bill Massey (Princeton University, U.S.) . Powerpoint slides from talk .

Title: An Optimal Design of the M/M/C/K Queue for Call Centers

Abstract: Motivated by the performance analysis of call centers, we develop an optimal design analysis for the M/M/C/K queueing system. The number of servers C corresponds to the number of agents and C+K, where K equals the number of additional waiting spaces, corresponds to the number of telephone lines. Our goal is to find the optimal (C,K) for this multi-server, loss and delay queueing system by holding two key service metrics below their given target values, for a predetermined level of offered load traffic. Using the exact steady state blocking and delay probabilities, we construct a new efficient algorithm for finding the optimal C and K that satisfy a given set of service level metrics. Moreover, we develop a faster approximate algorithm by using a steady state, heavy traffic, asymptotic analysis. The asymptotically derived number of agents and the number of waiting spaces in the buffer are found by iteratively solving a fixed point equation. Moreover, each iteration uses a generic special function which can be precomputed. Numerical examples with parameters found in typical call centers are used to compare both of these methods to each other and to a third ad hoc Erlang algorithm that is widely used in practice. This is joint work with Rodney B. Wallace of IBM and the Department of Engineering Management & Systems Engineering of George Washington University.

Co-authors: Rodney B. Wallace,

Short bio: Professor Massey is the Edwin S. Wilsey Professor in the Department of Operations Research and Financial Engineering, a member of the Applied and Computational Mathematics Program, and an associate member of the Department of Mathematics at Princeton University. From 1981 until 2001, he was a researcher in the Mathematical Sciences Research Center at Bell Laboratories of Lucent Technologies. His research interests include queueing theory, applied probability, as well as performance and pricing models for telecommunication systems. He received his undergraduate degree in Mathematics from Princeton University in 1977 and his Ph.D. in Mathematics from Stanford University in 1981.

Interest areas in multiserver scheduling:

Papers relevant to talk: Click Here

Balaji Prabhakar (Stanford University, U.S.) .

Title: SIFT: a randomized algorithm for determining large flows in the Internet

Abstract: Bandwidth is allocated to a flow in today's Internet due to actions by transport protocols at end-systems and queue management schemes at routers. While the nature of this bandwidth allocation is not yet well understood, to minimize the average flow delay, it would be ideal to allocate bandwidth according to a policy like SRPT (shortest remaining processing time). Given the heavy-tailed nature of Internet flow size distribution, the corresponding reduction in average flow delay would be particularly pronounced. But, this ideal is impractical: to decide which packet to transmit next a router would now need to know the residual data in the flow corresponding to each currently buffered packet. Even a less complex cousin of SRPT, like SFF (Shortest Flow First), is unimplementable since it would require a knowledge of flow sizes at routers. In this talk, we introduce a randomized algorithm called SIFT, for separating the packets of long and short flows. It is based on the simple observation that a randomly sampled arriving packet is much more likely to belong to a large flow, allowing a router to differentially allocate link bandwidth to large and small flows. We analyze the performance of SIFT via simulations and theory, and show that it is feasible to deploy it in Internet routers.

Co-authors: Costas Psounis and Arpita Ghosh

Short bio: Balaji Prabhakar is with the departments of Electrical Engineering, Computer Science and, by courtesy, of Management Science and Engineering at Stanford University. He is interested in network algorithms, in scaleable methods for network performance monitoring and simulation, in wireless (imaging) sensor networks, stochastic network theory and information theory. He has designed algorithms for switching, routing, bandwidth partitioning, load balancing, and web caching.

Alan Scheller-Wolf (CMU, U.S.) . Powerpoint slides from talk .

Title: New Recursive Dimensionality Reduction Technique applied to the analysis of multiserver scheduling policies including: Cycle Stealing, Priority Queueing, Task Assignment, and Threshold Policies (Part II)

Abstract: We consider common scheduling policies for multiserver systems including cycle stealing policies, priority queuing, task assignment policies, and threshold policies. Even these simple policies are already very difficult to analyze because their underlying Markov chain structure grows infinitely in more than one dimension -- the dimension of the Markov chain is typically equal to the number of servers. We introduce a new analysis technique which we call Recursive Dimensionality Reduction (RDR) which allows us to reduce an n-dimensionally inifinite Markov chain to a 1-dimensionally infinite Markov chain which can then be solved via numerical methods. We apply RDR to analyze the above scheduling policies, leading to new insights about these policies and proposals for improved policies.

Co-authors: Mor Harchol-Balter, Taka Osogami, Adam Wierman, Li Zhang.

Short bio: Alan Scheller-Wolf is an associate professor in Operations Management at the Graduate School of Industrial Administration of CMU. He did his doctoral studies in Operations Research at Columbia University, where he earned M.S., M. Phil., and Ph.D. degrees. Dr. Scheller-Wolf's research focuses on stochastic processes, and how they can be used to estimate and improve the performance of manufacturing and service systems. His earliest work dealt with the performance of multi-server queueing systems -- such as computer or telecommunication networks. In addition to his work, Dr. Scheller-Wolf is actively pursuing research on problems dealing with inventory systems and supply chains. He is particularly interested in how systems operate when there are capacity constraints, alternate sourcing or delivery options, perishable inventory, or exchange rate factors present. His work has appeared in Operations Research , Queueing Systems , and EJOR , as well as at Proceedings of ICDCS , SPAA and Sigmetrics. Professor Scheller-Wolf has or is currently working on operations consulting projects Caterpillar, the American Red Cross, John Deere, Intel, and Air Products International, and serves on the editorial boards of Management Science , M&SOM , OR Letters , IIE Transactions , and POMS journals.

Interest areas in multiserver scheduling:

Papers relevant to talk: Click Here

R. Srikant (University of Illinois, Urbana-Champaign, U.S.). Slides from talk in pdf .

Title: Fluid Modeling of BitTorrent-Like Peer-to-Peer Networks

Abstract: In this talk, we will present simple models to study the performance of BitTorrent, a second generation peer-to-peer (P2P) file-sharing application. We will first present a fluid model of BitTorrent and study the scalability, performance and efficiency of file-sharing. We will then consider the built-in mechanism in BitTorrent that is designed to prevent free-riding and study its effect on network performance.

Co-authors: Dongyu Qiu

Short bio: R. Srikant is an Associate Professor in the Department of Electrical and Computer Engineering Engineering and a Research Associate Professor in the Coordinated Science Lab at the University of Illinois. His research interests include communication networks, stochastic processes, queueing theory, information theory, and game theory.

Interest areas in multiserver scheduling: Scheduling, load-balancing, fluid models, diffusion approximations

Mark Squillante (IBM T.J. Watson Research Lab, U.S.) .

Title: Analysis of Parallel-Server Systems with Dynamic Affinity Scheduling and Load Balancing

Abstract: In this study we consider a parallel-server queueing system in which a scheduling policy directs customers to the server where they inherently can be served most efficiently (so-called affinity scheduling) and in which a threshold-based scheduling policy (both sender-initiated and receiver-initiated) manages the fundamental tradeoff between balancing the workload among the servers and serving customers where they can be served most efficiently (so-called load balancing, as well as resource pooling). This queueing system arises in many application areas, such as parallel computing environments, multi-tiered web server environments, and various business applications. We first establish the optimality of our general dynamic threshold-based scheduling policy within the context of fluid and diffusion limits. We then derive a matrix-analytic analysis and fixed-point solution of this parallel-server queueing system under fairly general stochastic processes as input and across all traffic intensities, obtaining explicit results in several cases. This solution is shown to be asymptotically exact (in terms of the number of servers) under certain conditions. The results of this analysis also provide key insights into the fundamental probabilistic behavior of dynamic threshold-based policies in large-scale parallel-server queueing systems. This includes numerically determining the optimal threshold values as a function of the workload, and demonstrating the potential for some unstable behavior under dynamic threshold-based scheduling policies if the thresholds are selected improperly. Lastly, based on this analysis we consider the corresponding stochastic optimization problem of dynamically determining the threshold values that minimize expected sojourn time as a function of time-varying workloads.

Co-authors: Portions of this study represent joint work with Randolph Nelson and Andrew Conn.

Short bio: Mark S. Squillante is a Research Staff Member in the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center, Yorktown Heights, NY. He has been an adjunct faculty member of the Department of Computer Science at Columbia University, New York, NY, from 1991 through 1996, and a Member of the Technical Staff at Bell Telephone Laboratories, Murray Hill, NJ, from 1982 to 1985. He received the Ph.D. degree in computer science from the University of Washington, Seattle, WA, in 1990. His research interests concern the mathematical analysis, modeling and optimization of the design and control of stochastic systems, with applications in the areas of computer, business, call center, finance, manufacturing and communication systems and services. Mark Squillante is a Fellow of IEEE, and a member of ACM, AMS, IFIP W.G. 7.3, INFORMS and SIAM. He currently serves on the editorial boards of Operations Research and Performance Evaluation.

Interest areas in multiserver scheduling: Very broad interests, including all areas related to the workshop.

Ward Whitt (Columbia University, U.S.) . Slides from talk in pdf .

Title: Resource Pooling and Staffing in Call Centers with Skill-Based Routing

Abstract: Call centers constitute an important application of scheduling for multi-server queues. Call centers usually handle several types of calls. To do so effectively, agents are given special training. However, it is often not cost-effective to have every agent be able to handle every type of call. Thus, the agents tend to have different skills, in different combinations. Call centers are equipped with automatic call distributors to assign calls to appropriate agents, i.e., to perform skill-based routing (SBR). However, it is challenging to do skill-based routing well. Moreover, it is challenging to determine the staff requirements in an SBR call center. This talk will discuss recent work addressing these problems. The main idea is to seek simplification through resource pooling, i.e., the notion that with (i) only a limited amount of cross training (e.g., perhaps even when agents have at most two skills)and (ii) a reasonable scheduling policy, the call center performance may be nearly the same as if all agents had all skills (and scheduling was not an issue at all). First, simulation experiments within a particular SBR framework show that resource pooling indeed occurs. Second, resource pooling is exploited to develop an effective algorithm to generate staffing require ments. The classical Erlang model is used to determine an initial estimate for the total staff needed in t he call center. Motivated by heavy-traffic stochastic-process limits, a square-root formula is then applied to dete rmine initial skill requirements within the estimated total staff. Finally, simulations are performed in order to make improvements in the initial assignment, in order to make the total staff requirements as small as possible, while ensuring that all performance requirem ents are met. Simulation experiments show that the overall procedure is remarkably effective: The required staff with limited cross training in a reasonable SBR framework can be nearly the same as if all agents had all skills.

Co-authors: Rodney B. Wallace, IBM,

Short bio: Ward Whitt is a Professor in the Department of Industrial Engineering and Operations Research at Columbia University in the City of New York. Ward joined the faculty at Columbia in 2002, after spending twenty-five years in research at AT&T, first at Bell Labs and then at AT&T Labs. He received an A.B. in mathematics from Dartmouth College in 1964 and a Ph.D. in operations research from Cornell University in 1969. His research has concentrated on probability theory and its application to telecommunication systems, especially involving queueing theory, stochastic processes, simulation and numerical transform inversion. He published the book, Stochastic-Process Limits in 2002. His current talk is based on his recent paper with the same title, co-authored with Rodney B. Wallace, based on Rodney's 2004 Ph.D. thesis, Performance Modeling and Design of Call Centers with Skill-Based Routing , for which Ward was co-advisor with Bill Massey and Thomas Mazzuchi.

Interest areas in multiserver scheduling:

Papers relevant to talk: Click Here

Ruth Williams (University of California, San Diego, U.S.) . Powerpoint slides from talk .

Title: Dynamic Scheduling of a Parallel Server System

Abstract: We consider a parallel server queueing system consisting of a bank of buffers for holding incoming jobs and a bank of flexible servers for processing these jobs. Incoming jobs are classified into one of several different classes (or buffers). Jobs within a class are processed on a first-in-first-out basis, where the processing of a given job may be performed by any server from a given (class-dependent) subset of the bank of servers. The random service time of a job may depend on both its class and the server providing the service. Each job departs the system after receiving service from one server. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs to available servers. We consider a parameter regime in which the system satisfies both a heavy traffic and a complete resource pooling condition. Our cost function is a mean cumulative discounted cost of holding jobs in the system, where the (undiscounted) cost per unit time is a linear function of normalized (with heavy traffic scaling) queue length. Based on an interpretation of the analytic solution to an associated Brownian control problem (formal heavy traffic diffusion approximation), we propose a "continuous review" threshold scheduling policy for use in the parallel server system. We then show that this policy is asymptotically optimal in the heavy traffic limit and that the limiting cost is the same as the optimal cost in the Brownian control problem.

Coauthors: S. L. Bell

Short bio: Ruth Williams is a Professor of Mathematics at the Univeristy of California at San Diego (UCSD). Her research interests are in probability, stochastic processes and their applications. She is a Fellow of the American Association for the Advancement of Science and the Institute of Mathematical Statistics. Ruth Williams has been a U.S. National Science Foundation (NSF) Presidential Young Investigator (1987-93), an Alfred P. Sloan Fellow (1988-92), a Guggenheim Fellow (2001-2002) and was an invited speaker at the International Congress of Mathematicians held in Berlin in 1998.

Interest areas in multiserver scheduling: Load balancing, stability and performance, fluid and diffusion limits, task assignment policies, heavy tails.

Papers relevant to talk: Click Here

Carey Williamson (University of Calgary, Canada) . Powerpoint slides from talk .

Title: Simulation Evaluation of Hybrid SRPT Policies

Abstract: This talk describes trace-driven simulation work that compares and evaluates different Web server scheduling strategies, such as Processor Sharing (PS), Shortest Remaining Processing Time (SRPT), and Fair Sojourn Protocol (FSP). We use a probe-based sampling methodology developed in prior work to study the response time and fairness properties of these scheduling policies. The approach is general purpose: it can be used to determine complete response time distributions for arbitrary arrival processes, scheduling policies, and service time distributions. We use the approach to evaluate two novel scheduling policies called K-SRPT and K-Threshold SRPT. Each is a variant of SRPT. K-SRPT is a multi-threaded version of SRPT that can have up to K jobs in service at a time, namely the K jobs with the least remaining service times. K-Threshold SRPT is a hybrid policy that dynamically switches from PS to SRPT when the number of jobs in the system exceeds K, and back to PS when the load diminishes. Fairness profile plots are used to characterize mean slowdown and variance of slowdown for these policies. The results show that the parameter K defines a family of policies with smooth performance tradeoffs between SRPT and PS. The extension of our results to multi-server systems is also discussed.

Co-authors: Mingwei Gong, University of Calgary

Short bio: Dr. Carey Williamson is an iCORE (Informatics Circle of Research Excellence) Professor in the Department of Computer Science at the University of Calgary, specializing in "Broadband Wireless Networks, Protocols, Applications, and Performance". He also holds an NSERC Industrial Research Chair in "Wireless Internet Traffic Modeling". His educational background includes a B.Sc.(Honours) degree in Computer Science from the University of Saskatchewan in 1985, and a Ph.D. in Computer Science from Stanford University in 1991. Dr. Williamson's research interests include Internet protocols, wireless networks, network traffic measurement, workload characterization, network simulation, and Web server performance.

Interest areas in multiserver scheduling: Load balancing, scheduling policies, fairness, workload modeling, simulation

Papers relevant to talk: Click Here

Back to Workshop home page .