Stability for Multiserver Job Models with Product-form Saturated Systems
Explore the stability of multiserver job models via product-form saturated systems, analyzing throughputs, stationary distributions, and correlated duration and server need classes. Learn about the theoretical analysis and prior work in this area.
Download Presentation
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
Stability for the Multiserver-job Model via Product-form Saturated Systems Isaac Grosof CMU GA Tech UIUC Northwestern Mor Harchol-Balter (CMU) Alan Scheller-Wolf (CMU) MAMA 2023, June 19th 1
Multiserver-job Model Job: (duration, server need) FCFS 1 Expected duration Server need 1 ? 4 Poisson(?) 1 1 4 4 Sampled i.i.d. from joint distribution Idle servers Example distribution: (???( ),1) (???(1),4) 2
MSJ FCFS Stability (Duration, server need): (???( ),1) (???(1),4) FCFS 1 1 ? Poisson(?) 1 1 4 4 Stable if ? 0,? . Q: What is ? ? Upper bound: 100% utilization. ? 1.333 Answer: ? = 0.835 How can we theoretically analyze MSJ FCFS stability? 3
Prior work [Rumyantsev & Morozov 17]: Characterized stability in the Single duration setting: Duration = Exp(?), General server need distribution, Independent duration & server need. Otherwise, stability is open. Highly general technique: Saturated system [Baccelli & Foss 95] 4
Saturated System New arrival! FCFS 1 1 1 1 4 4 Always enough jobs to saturate servers Simplest formulation: Exactly ? jobs present. [Baccelli & Foss 95]: Original ? = throughput of saturated system. Nothing MSJ-specific. Q: Can we analyze MSJ FCFS saturated system? 5
(Duration, server need): (???( ),1) (???(1),4) Demo: Saturated Stability Want to calculate saturated throughput. We characterize steady-state: 1 1 1 1 1 1 1 4 1 1 1 2.61% ?4 1= 2 3.48% ?3 1= 1.5 10.43% ?2 1= 1 41.74% ?1 1= 0.5 41.74% ?1 4= 1 Throughput: 0.835 ? = 0.835 6
Our Result: Product-form Stationary Distributions Product-form: Probability of each state is a product of terms, one term for each job present. Result: Saturated system has product-form stationary distribution in each of 2 MSJ FCFS settings: 1. Single duration: Duration = Exp(?), general server need distribution, independent. New proof of RM 17 result. 2. Two classes: Class 1: (Exp(?1), 1), class 2: (Exp(?2), 2). First stability analysis with correlated duration and server need! 7
Stationary distribution: Departure-average Saturated system has 2 natural stationary distributions: 1. CTMC, time-average distribution. 2. DTMC, departure-average distribution. Easy to convert between distributions. We derive product-form formulas for departure-average distribution, in both single-duration and two-class settings. 8
Single duration result Setting: ???(?) duration, ? prob. of server need . New arrival! FCFS 2 State ?: ordered list of ? jobs. ? = [4,1,3,2,1,1] 1 4 3 1 1 Theorem: The departure-average stationary distribution ? of the single-duration setting is: ??= ??? ? 9
Single duration: Partitioned local balance New arrival! FCFS 2 1 4 3 1 1 ? ? ,? : Probability of transition from ? to ? due to 1 departure and 1 arrival. Balance equation: ?? = ? ?? ? ? ,? ? ? ,? : ? to ? via departure of -server job and 1 arrival. Partitioned local balance: ,?? ? = ? ?? ? ? ,? 10
Single duration: Partitioned local balance New arrival! FCFS State ? = [4,1,3,2,1,1] 2 1 4 3 1 1 Partitioned local balance, = 3. Predecessor states: Remove 4-server job from queue, add 3-server job to service. 11
Single duration: Partitioned local balance New arrival! FCFS State ? = [4,1,3,2,1,1] 2 1 3 1 1 Partitioned local balance, = 3. Predecessor states: Remove 4-server job from queue, add 3-server job to service. 12
Single duration: Partitioned local balance New arrival! 1 FCFS State ? = [4,1,3,2,1,1] 1 1 1 2 2 3 3 3 Partitioned local balance, = 3. Predecessor states: Remove 4-server job from queue, add 3-server job to service. ?1 = [1,3,2,1,1,3] 13
Single duration: Partitioned local balance New arrival! 1 FCFS State ? = [4,1,3,2,1,1] 3 1 2 3 1 Partitioned local balance, = 3. Predecessor states: Remove 4-server job from queue, add 3-server job to service. ?1 ?2 = [1,3,2,1,1,3] = [1,3,2,1,3,1] 14
Single duration: Partitioned local balance New arrival! FCFS State ? = [4,1,3,2,1,1] 3 1 1 2 3 1 Partitioned local balance, = 3. Predecessor states: Remove 4-server job from queue, add 3-server job to service. ?1 ?2 ?3 = [1,3,2,1,1,3] = [1,3,2,1,3,1] = [1,3,2,3,1,1] 15
Single duration: Partitioned local balance New arrival! FCFS State ? = 4,1,3,2,1,1 ?1 ?2 ?3 3 = [1,3,2,1,1,3] = [1,3,2,1,3,1] = [1,3,2,3,1,1] 1 1 2 3 1 Predecessors have ? = 3 jobs in service. ? = 3 predecessor states. ,? =1 3?4= Partitioned local balance: ?? Partitioned local balance verified, product-form holds! 1 ??? ?3?? ? ?? ?? ?= ??? ,?) = ??? ??? ? (?? 16
Results outline Single duration: ??= ???? Two-class: Up next 17
Two-class: New view New arrival! (Duration, server need): ?1: ??? ?1, 1 ?2: (??? ?2, 2) FCFS 10 3 ? = 30 10 10 3 3 10 10 1= 3, 2= 10 3 Old representation: k = 30 jobs, 230 states. New representation: Just enough jobs as necessary. Minimal jobs to reach total server need > ? 1= 27 18
Two-class: New view New arrival! (Duration, server need): ?1: ??? ?1, 1 ?2: (??? ?2, 2) 10 3 ? = 30 10 10 10 1= 3, 2= 10 3 Old representation: 30 jobs, 230 states. New representation: Just enough jobs as necessary. Minimal jobs to reach total server need > ? 1= 27 19
Two-class: New view New arrival! (Duration, server need): ?1: ??? ?1, 1 ?2: (??? ?2, 2) 10 3 State: {1,2,2} ? = 30 10 10 10 1= 3, 2= 10 3 Minimal jobs to reach total server need > ? 1= 27 State descriptor: { ,?,?} ?: # of class 1 jobs in service ?: # of class 2 jobs in service : Class 2 job in queue? 20
Two-class: New view New arrival! (Duration, server need): ?1: ??? ?1, 1 ?2: (??? ?2, 2) 3 3 State: {1,2,2} ? = 30 10 10 1= 3, 2= 10 10 10 Minimal jobs to reach total server need > ? 1= 27 State descriptor: { ,?,?} ?: # of class 1 jobs in service ?: # of class 2 jobs in service : Class 2 job in queue? 21
Two-class: New view New arrival! (Duration, server need): ?1: ??? ?1, 1 ?2: (??? ?2, 2) 3 10 State: {1,1,2} ? = 30 ? = 30 10 10 1= 3, 2= 10 10 Minimal jobs to reach total server need > ? 1= 27 State descriptor: { ,?,?} ?: # of class 1 jobs in service ?: # of class 2 jobs in service : Class 2 job in queue? 22
Two-class: New view New arrival! (Duration, server need): ?1: ??? ?1, 1 ?2: (??? ?2, 2) 10 10 State: [0,0,3] ? = 30 10 1= 3, 2= 10 10 Minimal jobs to reach total server need > ? 1= 27 State descriptor: { ,?,?} ?: # of class 1 jobs in service ?: # of class 2 jobs in service : Class 2 job in queue? 23
New arrival! Two-class: Notation 3 3 10 10 ?1(?): Unique state with ? class-1 jobs in service. ?12 = {1,2,2} ?2? : Unique state with ? class-2 jobs in service and no job in queue. ?22 = {0,3,2} ??( ,?,? ): Probability that next completion is class ?. ??1 ??1+??2, ?2 ,?,? 10 10 New arrival! 3 3 10 3 10 ??2 ?1 ,?,? = = ??1+??2 10 24
?1(?): State with ? class-1 jobs in service. ?2? : State with ? class-2 jobs in service and no job in queue. ??( ,?,? ): Prob. next completion is class ?. Two-class: Result Theorem: The departure-average stationary distribution ? of the two-class setting is: ? ? 1 1 ??2 ?+ ? ,?,?= ?1 ?1?1? ?2?2? ?=1 ?=1 25
Two-class: Proof sketch Balance equation: ?? ?(? ,?) ??= ? Partitioned local balance: ?? ?1? ,? , ?? ?2? ,? ???1= ???2= ? ? Remainder of proof: case bash. Partitioned local balance verified! Product form holds! 26
Two-class: Proof intuition 3 {0,0,3} {1,1,2} {1,2,2} {0,3,2} ?: # class 2 in service {1,4,1} {1,5,1} {0,6,1} 0 {1,7,0} {1,8,0} {1,9,0} {0,10,0} ?: # class 1 in service 10 0 Markov chain near 1D. Strict 1D Product form. 27
Results outline Single duration: ??= ???? 1 1 ? ? ??2 ?+ ?=1 ?=1 Two-class: ? ,?,?= ?1 ?1?1? ?2?2? 28
Future directions Beyond MSJ FCFS: FCFS + general constraint on service. Single duration + 2-class results still hold? Relating MSJ FCFS mean response time to saturated system? Student Research Competition poster & talk! 29
Conclusion Saturated System MSJ Stability New arrival! FCFS FCFS 2 1 1 1 4 3 1 1 1 4 4 1 Product form stationary distributions: Single duration: ??= ???? Two-class: ? ,?,?= ?1 1 1 ? ? ??2 ?+ ?=1 ?=1 ?1?1? ?2?2? 30
