The Supermarket Model with Known and Predicted Service Times
The Supermarket Model with Known and Predicted Service Times
复制标题
DOI：
10.1109/tpds.2022.3146195
复制
发表时间：
2019-05
影响因子：
5.3
通讯作者：
M. Mitzenmacher;Matteo Dell'Amico
中科院分区：
文献类型：
--
作者：
M. Mitzenmacher;Matteo Dell'Amico
超市模型是指具有大量排队的系统，到达的顾客随机选择d个队列，加入顾客最少的队列。超级市场模型展示了负载平衡系统中，与简单地加入随机均匀选择的队列相比，即使是少量选择也具有强大的功能。在这项工作中，我们进行了基于模拟的研究，以考虑预测客户服务时间的变化，就像在现代环境中使用机器学习技术或相关机制一样。我们的主要结论是，在这种情况下，即使使用看似薄弱的服务时间预测，也可以比盲目的先进先出算法带来显著的好处。然而，当使用预测的服务时间信息来选择队列和队列内的服务的顺序元素时，必须要小心;虽然在许多情况下，使用信息进行选择和排序是有益的，但在我们的许多模拟设置中，我们发现，当使用预测的服务时间来排序队列中的作业时，简单地使用作业的数量来选择队列更好。在我们的模拟中，我们评估了合成和真实世界的工作负载-在后者中，服务时间是通过机器学习预测的。我们的研究结果为现实世界系统的设计提供了实际指导;此外，我们为未来的工作留下了许多自然的理论开放问题，验证了它们与现实世界情况的相关性。
The supermarket model refers to a system with a large number of queues, where arriving customers choose d queues at random and join the queue with the fewest customers. The supermarket model demonstrates the power of even small amounts of choice, as compared to simply joining a queue chosen uniformly at random, for load balancing systems. In this work we perform simulation-based studies to consider variations where service times for a customer are predicted, as might be done in modern settings using machine learning techniques or related mechanisms. Our primary takeaway is that using even seemingly weak predictions of service times can yield significant benefits over blind First In First Out queueing in this context. However, some care must be taken when using predicted service time information to both choose a queue and order elements for service within a queue; while in many cases using the information for both choosing and ordering is beneficial, in many of our simulation settings we find that simply using the number of jobs to choose a queue is better when using predicted service times to order jobs in a queue. In our simulations, we evaluate both synthetic and real-world workloads--in the latter, service times are predicted by machine learning. Our results provide practical guidance for the design of real-world systems; moreover, we leave many natural theoretical open questions for future work, validating their relevance to real-world situations.