Mean-field Analysis for Load Balancing on Spatial Graphs
Mean-field Analysis for Load Balancing on Spatial Graphs
复制标题
空间图负载均衡的平均场分析
DOI：
10.1145/3578338.3593552
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Mukherjee, Debankur
中科院分区：
文献类型：
--
作者：
Rutten, Daan;Mukherjee, Debankur
分析大规模负载平衡系统背后的一个关键方法工具是平均场分析。高层次的思想是通过聚合量来表示系统状态，并描述随着系统规模的增大而变化的速率。上述方案起作用的一个假设是，合计数量是马尔可夫的，使得其变化率可以表示为其当前状态的函数。在负载均衡系统中，如果服务器是可交换的，那么聚合量确实是马尔可夫的。然而，现代数据中心处理的任务类型的日益异构性最近促使研究界考虑超越可交换性假设的系统。主要原因来自数据局部性，即服务器需要存储资源以在本地处理特定类型的任务，并且存储空间有限。因此，一个新兴的工作领域考虑任务类型和服务器之间的二分图[2，3，5-7]。在此兼容性图中，服务器和任务类型之间的边表示服务器处理这些任务的能力。在实践中，存储容量或地理限制迫使服务器仅处理所有任务类型的一小部分，从而导致稀疏网络拓扑。这激发了对具有适当稀疏二部兼容图的系统中的负载平衡的研究。
A pivotal methodological tool behind the analysis of large-scale load balancing systems is mean-field analysis. The high-level idea is to represent the system state by aggregate quantities and characterize their rate of change as the system size grows large. An assumption for the above scheme to work is that the aggregate quantity is Markovian such that its rate of change can be expressed as a function of its current state. If the aggregate quantity is not Markovian, not only does this technique break down, the mean-field approximation may even turn out to be highly inaccurate.In load balancing systems, if servers are exchangeable, then the aggregate quantity is indeed Markovian. However, the growing heterogeneity in the types of tasks processed by modern data centers has recently motivated the research community to consider systems beyond the exchangeability assumption. The main reason stems from data locality, i.e., the fact that servers need to store resources to process tasks of a particular type locally and have only limited storage space. An emerging line of work thus considers a bipartite graph between task types and servers [2, 3, 5 -7]. In this compatibility graph, an edge between a server and a task type represents the server's ability to process these tasks. In practice, storage capacity or geographical constraints force a server to process only a small subset of all task types, leading to sparse network topologies. This motivates the study of load balancing in systems with suitably sparse bipartite compatibility graphs.
登录
查看更多内容
影响因子：
0.6
作者：
Nitish K. Panigrahy;Thirupathaiah Vasantam;P. Basu;D. Towsley;A. Swami;K. Leung
通讯作者：
K. Leung
论冗余模型的稳定性
DOI：
10.1287/opre.2020.2030
发表时间：
2019
期刊：
Oper. Res.
影响因子：
--
作者：
Elene Anton;U. Ayesta;M. Jonckheere;M. Verloop
通讯作者：
M. Verloop
DOI：
10.1145/3466772.3467047
发表时间：
2021-06
期刊：
Proceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
影响因子：
--
作者：
Tuhinangshu Choudhury;Gauri Joshi;Weina Wang;S. Shakkottai
通讯作者：
Tuhinangshu Choudhury;Gauri Joshi;Weina Wang;S. Shakkottai
DOI：
--
发表时间：
2017
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Debankur Mukherjee;S. Borst;J. V. Leeuwaarden
通讯作者：
J. V. Leeuwaarden
影响因子：
2.2
作者：
Lu, Yi;Xie, Qiaomin;Greenberg, Albert
通讯作者：
Greenberg, Albert