• Home
• Research interests
• Publications
• Java applets
• Past activities
• Contact

Dispatching Problem

Basic problem: Tasks/jobs/customers arrive according to (Poisson) process Dispatcher assigns a server to each task upon arrival Each server processes tasks according to some scheduling discipline (e.g., FCFS, LCFS, SRPT) Objective is, e.g., to minimize the mean delay (a.k.a. mean sojourn time and mean response time) Classical results are the optimality of JSQ and Round-robin under certain assumptions Extensions: Heterogeneous servers, e.g., some servers can process certain tasks more efficiently Tasks with hard deadlines Tasks which can be assigned only to specific servers (skills, flexibility) Amount of information, e.g., exact task size information vs. its distribution Switching delays (i.e., server setup delays) and associated (energy) costs

Figure: A sample dispatching system with dedicated inputs.

The dispatching problem, or the task assignment problem, is a commonly encountered dynamic decision problem. Examples include manufacturing sites, batch jobs in supercomputing, web server farms and other distributed server systems. The objective can be the minimization of the mean sojourn time, which is achieved by an appropriate load balancing between the servers. Optimal policy depends on the available information about the new job and the state of the servers. It is often assumed that jobs are processed in the first-come-first-served (FCFS) order, although other service disciplines such as the last-come-first-served (LCFS), shortest-remaining-processing-time (SRPT) and processor sharing (PS), can also be relevant. The grand challenge is to take into account the tasks arriving in future.

I. Size-aware systems

Our work on this interesting research topic is based on queueing theory and Markov decision processes. More precisely, so far we have focused on size-aware problems, which means that the service time or its estimate is available at the dispatcher. Availability of this type of more accurate information is common in many modern applications (cf. file sizes), and the increase in computational resources facilitates its exploitation in the decision making process. In this setting, we have derived new (size-aware) analytical results for M/G/1 queues, then applied the so-called policy iteration, and obtained new efficient and robust dispatching policies that exploit the available information on service times, queues' states and servers' capabilities. One important aspect is energy-aware policies that may switch some servers off. See the pages on SITA and Lookahead for more information.

II. Large-scale distributed computing

Here the starting point has been computing clusters such as (large-scale) server farms located in data centers providing the remarkably fast response times the users of different web services are accustomed to. This includes Google search, Amazon's web shop, Facebook updates, YouTube videos. We have focused on developing appropriate models for performance analysis and optimization of such systems. The scheduling discipline is generally either first-come-first-served (FCFS), ,e.g., in computing clusters, or processor sharing (PS), if the underlying system comprises, e.g., the de facto multitasking time-sharing unix systems. More specifically, we have considered:

• Dispatching jobs based on their value (holding cost), i.e., how to prioritize important jobs in dispatching under PS
• Heterogeneous servers, which could arise, e.g., from the data locality (the performance impact for accessing data remotely can be severe)
• Redundant jobs, a novel approach to kill the tails in latency when jobs consist of multiple smaller tasks processed in parallel (cf. speculative execution)

Additional material

• SITA and FPI briefly
• Dispatching policies illustrated
• Dispatching system in action (simulator)
  • See also the Dispatching simulator written as a Java applet (older)

Our publications:

[1]	K. Gardner, S. Zbarsky, S. Doroudi, M. Harchol-Balter, E. Hyytiä and A. Scheller-Wolf. Reducing Latency via Redundant Requests: Exact Analysis, in ACM SIGMETRICS, 2015, Portland, Oregon, USA.
[2]	S. Doroudi, E. Hyytiä and M. Harchol-Balter. Value Driven Load Balancing, Performance Evaluation, vol. 79, 306-327, 2014 (IFIP Performance'14).
[3]	E. Hyytiä, R. Righter and S. Aalto, Energy-aware Job Assignment in Server Farms with Setup Delays under LCFS and PS, in 26th International Teletraffic Congress (ITC'26), 2014, Karlskrona, Sweden.
[4]	E. Hyytiä, R. Righter and S. Aalto, Task Assignment in a Server Farm with Switching Delays and General Energy-Aware Cost Structure, Performance Evaluation, vol. 75--76, pp. 17-35, 2014.
[5]	E. Hyytiä, Optimal Routing of Fixed Size Jobs to Two Parallel Servers, INFOR: Information Systems and Operational Research, 51(4):215-224, 2013.
[6]	E. Hyytiä and S. Aalto, Round-Robin Routing Policy: Value Functions and Mean Performance with Job- and Server-specific Costs, in ValueTools'13, December 2013, Turin, Italy.
[7]	E. Hyytiä, Lookahead Actions in Dispatching to Parallel Queues, in 31st International Symposium on Computer Performance, Modeling, Measurement and Evaluation (IFIP Performance 2013), September 2013, Vienna, Austria.
[8]	E. Hyytiä and S. Aalto, To Split or not to Split: Selecting the Right Server with Batch Arrivals, Operations Research Letters 4(41), pp. 325-330 July 2013.
[9]	E. Hyytiä, S. Aalto, A. Penttinen and J. Virtamo, On the value function of the M/G/1 FCFS and LCFS queues, Journal of Applied Probability 49 (4), pp. 1052-1071, December 2012.
[10]	E. Hyytiä, S. Aalto and A. Penttinen, Minimizing Slowdown in Heterogeneous Size-Aware Dispatching Systems, in ACM SIGMETRICS/Performance, June 2012, London, UK.
[11]	E. Hyytiä, A. Penttinen and S. Aalto, Size- and State-Aware Dispatching Problem with Queue-Specific Job Sizes, European Journal of Operational Research 217 (2) (2012) 357-370.
[12]	A. Penttinen, E. Hyytiä and S. Aalto, Energy-aware dispatching in parallel queues with on-off energy consumption, in Proc. of 30th IEEE IPCCC, November 2011.
[13]	E. Hyytiä, J. Virtamo, S. Aalto and A. Penttinen, M/M/1-PS Queue and Size-Aware Task Assignment, Performance Evaluation 68 (11) (2011) 1136-1148.
[14]	E. Hyytiä, A. Penttinen, S. Aalto and J. Virtamo, Dispatching problem with fixed size jobs and processor sharing discipline, in ITC 2011, 23rd International Teletraffic Congress, Sept. 2011.