Joining the shortest or least loaded queue among $d$ randomly selected queues are two fundamental load balancing policies. Under both policies the dispatcher does not maintain any information on the queue length or load of the servers. In this paper we analyze the performance of these policies when the dispatcher has some memory available to store the ids of some of the idle servers. We consider methods where the dispatcher discovers idle servers as well as methods where idle servers inform the dispatcher about their state. We focus on large-scale systems and our analysis uses the cavity method. The main insight provided is that the performance measures obtained via the cavity method for a load balancing policy {\it with} memory reduce to the performance measures for the same policy {\it without} memory provided that the arrival rate is properly scaled. Thus, we can study the performance of load balancers with memory in the same manner as load balancers without memory. In particular this entails closed form solutions for joining the shortest or least loaded queue among $d$ randomly selected queues with memory in case of exponential job sizes. Moreover, we obtain a simple closed form expression for the (scaled) expected waiting time as the system tends towards instability. We present simulation results that support our belief that the approximation obtained by the cavity method becomes exact as the number of servers tends to infinity.


翻译:在随机选择的$d 队列中加入最短或最不全的队列是两个基本的负载平衡政策。 在这两种政策中,调度者不保留关于队列长度或服务器负载的任何信息。 在本文中, 当调度者有一定的内存可以存储一些闲置服务器的代号时, 我们分析这些政策的性能。 我们考虑调度者发现闲置服务器的方法, 以及闲置服务器告知调度者其状态的方法。 我们侧重于大型系统, 我们的分析使用空格方法。 我们提供的主要洞察力是, 通过空格方法为负载平衡政策而获得的性能措施 。 与 内存相比, 将内存减为同一政策 的内存的性能措施 。 在适当缩放率的情况下, 我们分析这些政策的性能。 因此, 我们可以以与无记忆的负载平衡器的相同的方式研究负载器的性能。 特别是要采用封闭的形式解决方案, 加入最短或最小的排队列, 以记忆方式选择的排队列, 以指数大小为单位 。 此外, 我们获得了一个简单的封闭式表达式表达形式, 我们的表达, 我们的状态会成为了模拟的状态,,, 以正变变变变的系统会决定着, 。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
已删除
将门创投
3+阅读 · 2019年4月25日
时序数据异常检测工具/数据集大列表
极市平台
65+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【数据集】新的YELP数据集官方下载
机器学习研究会
16+阅读 · 2017年8月31日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年3月18日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Arxiv
3+阅读 · 2018年10月5日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
已删除
将门创投
3+阅读 · 2019年4月25日
时序数据异常检测工具/数据集大列表
极市平台
65+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【数据集】新的YELP数据集官方下载
机器学习研究会
16+阅读 · 2017年8月31日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员