An Approximate Bribe Queueing Model for Bid Advising in Cloud Spot Markets

We consider the scheduling system of a container cloud spot market where the user specifies the requested number of containers and their resource requirements, along with a bid value. Jobs are preemptively ordered based on their bid values as the available capacity, which is excess capacity made available for the spot market, may vary over time. Due to this variation, the number of allocated containers to a job may vary during its lifetime, resulting in users experiencing periods of degraded performance, potentially leading to job slowdown. We want to model and analyze such a scheduling system starting from first principles, inspired by the M/M/1 bribe queue. Thus, we introduce a simple, empirical queueing model which parametrically relates job slowdown to bid values given load and bid distribution. We demonstrate the accuracy of our approximation and parameter estimation through simulation.