This framework by Kristy Gardner explores dispatching strategies in multi-server systems, including JSQ and SED methods, leveraging server heterogeneity for optimal performance. Discover insights on server speed information utilization and system modeling assumptions."
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A General "Power-of-d" Dispatching Framework for Heterogeneous Systems Kristy Gardner Amherst College Based on joint work with Jazeem Abdul Jaleel, Sherwin Doroudi, and Alexander Wickeham University of Minnesota YEQT Conference June 7, 2021
How to dispatch in multi-server systems? large-scale heterogeneous 4 RANDOM JSQ-4 JSQ-2 3 JSQ-10 ? ? 2 JSQ 1 theoretical lower bound (JSQ, all fast) 00 0.2 0.4 0.6 0.8 1 300 fast servers, rate 1.95 jobs/sec 700 slow servers, rate 0.6 jobs/sec June 7, 2021 Kristy Gardner 5
How to dispatch in multi-server systems? large-scale heterogeneous Dispatcher? . . . . . . Shortest Expected Delay among ? (SED-?) June 7, 2021 Kristy Gardner 6
How to dispatch in multi-server systems? large-scale heterogeneous 4 RANDOM JSQ-4 JSQ-2 SED-4 3 JSQ-10 ? ? 2 JSQ 1 theoretical lower bound (JSQ, all fast) 00 0.2 0.4 0.6 0.8 1 300 fast servers, rate 1.95 jobs/sec 700 slow servers, rate 0.6 jobs/sec June 7, 2021 Kristy Gardner 7
Leveraging Server Heterogeneity There are two points at which the dispatcher can use server speed information QueryingRule Assignment Rule Which ? servers to query? After querying, where to send the job? ? ? June 7, 2021 Kristy Gardner 8
System Model Poisson(??) Modeling Assumptions ? servers, ? server speed classes ??= ??? servers in class ? Dispatcher? Independent service times, distribution ?? with mean 1/?? ?1> ?2> > ?? Poisson arrival process with rate ?? Dispatcher decides immediately to which server to send a job . . . ?1 ?2 ?2 ?? ?? ?? Scheduling: any work-conserving policy ?2 class-2 servers Goal: design dispatching policies to achieve low mean response time Key idea: Dispatching policy = Querying rule + Assignment rule June 7, 2021 Kristy Gardner 9
Querying Rules Notation Dispatcher ? ?: # of servers queried (constant, ?) ??: # of class-? servers queried ? = ?1, ,??: query mix ?1 ?2 ?2 ?2 ?3 ?3 ? = ?:?1+ + ??= ? : set of possible query mixes Two important properties: Symmetric: servers of the same class are treated ex ante identically Static: dispatcher doesn t maintain any history Querying rule: ? :? 0,1 June 7, 2021 Kristy Gardner 10
Querying Rules GEN: any distribution over ? GEN IND: each of the ? queried server classes is chosen independently IND DET IID: each of the ? queried server classes is chosen independently from the same distribution DET: the same query mix is always used (? is deterministic) IID Uniform SFC Balanced Routing SRC: probabilistically chooses one server class, then queries ? servers from that class SRC SFC: always queries ? class-?servers for some fixed class ? June 7, 2021 Kristy Gardner 11
Assignment Rules Notation Dispatcher ? = ?1, ,??: query mix ? ? = ?:?1+ + ??= ? : set of possible query mixes ? ? : information obtained about the ? queried servers ?2 ?2 ? = ? ? :? ? : set of possible query results Two important properties: Symmetric: servers with the same state are treated identically Static: dispatcher doesn t maintain any history Assignment rule: , :? ? 0,1 June 7, 2021 Kristy Gardner 12
Assignment Rules ? ? : # of idle class-? servers in query CLD CLD: can use class and queue-length information CID: can use class and idleness information CID ID LD LD: can use only queue-length information CD ND JIQ JSQ ID: can use only idleness information SED CD: can use only class information June 7, 2021 Kristy Gardner 13
Analyzing GEN,CID : Approach Goal: Find ? ? given querying and assignment rules Assumptions: ? , with ?? fixed States of all servers of the same class evolve stochastically identically All server states are independent Main analytic technique: tag a class-? server and examine what happens whenever a new job arrives in steady-state, via mean-field analysis: Is the tagged server queried? If so, does it get the job? June 7, 2021 Kristy Gardner 14
Analyzing GEN,CID : Preliminaries Observation: tagged class-? server has different arrival rates when idle vs busy When idle: Poisson ? When busy: Poisson ? ? ? ? Observation: once busy, server behaves like an ?/??/1 with arrival rate ? Mean busy period duration: 1 ? ?? = ? ?? ? Fraction of time a server is busy: ? ? ?? ?+ ? ?? ? ??= = ?+ ? ? 1/ ? ?? ? June 7, 2021 Kristy Gardner 15
Analyzing GEN,CID : ? ? Condition on the server s class: Mean response time at a class-??/??/1 with arrival rate ? ? ? ?+ ???? ? ? ? ??1 ?? ? ? ? = ? ?? Any work-conserving scheduling policy! ?=1 ? ?+ ?? ? ? 1 ?? ? = ?? ? ?? ?=1 ? and ? ? All that remains: finding ? June 7, 2021 Kristy Gardner 16
? and ? ? Analyzing GEN,CID : ? Given ?, probability that the tagged server is in the query: ?? ? = ?1, ,??: query mix ?? ?? ?? = Rate at which the tagged server is queried: ? ? ? ? ? ?? ?? ? ? ? ? ?? : prob. job is sent to the tagged server, given ? and tagged server is idle Define ?? ?? : analogous, tagged server is busy ?? ?= ?= ?? ?? ? ? ? ???? ? ? ? ???? ?? ?? ? ? ? ? ?? and ?? ?? All that remains: finding ?? June 7, 2021 Kristy Gardner 17
?? Analyzing GEN,CID : ?? ?? : prob. job is sent to the tagged server, given ? and tagged server is idle ?? Define ??? : probability that all faster queried servers are busy ? 1 ???? ??? = ?=1 Job is then assigned to a class-? server w.p. ???,? ?? ?? 1???? ?? ?? ?? 1 ?? 1 1 ?? ?? = ??? ???,? ?? ??=1 June 7, 2021 Kristy Gardner 18
Conclusion QueryingRule Assignment Rule Which ? servers to query? After querying, where to send the job? ? ? June 7, 2021 Kristy Gardner 21
Two Quick Advertisements Amherst College Computer Science is hiring! I ll be visiting the Netherlands for (some part of) the upcoming academic year! kgardner@amherst.edu June 7, 2021 Kristy Gardner 22
