Server saturation in skewed networks
Proceedings of the ACM on Measurement and Analysis of Computing Systems(2024)
摘要
We consider a model inspired by compatibility constraints that arise between
tasks and servers in data centers, cloud computing systems and content delivery
networks. The constraints are represented by a bipartite graph or network that
interconnects dispatchers with compatible servers. Each dispatcher receives
tasks over time and sends every task to a compatible server with the least
number of tasks, or to a server with the least number of tasks among d
compatible servers selected uniformly at random. We focus on networks where the
neighborhood of at least one server is skewed in a limiting regime. This means
that a diverging number of dispatchers are in the neighborhood which are each
compatible with a uniformly bounded number of servers; thus, the degree of the
central server approaches infinity while the degrees of many neighboring
dispatchers remain bounded. We prove that each server with a skewed
neighborhood saturates, in the sense that the mean number of tasks queueing in
front of it in steady state approaches infinity. Paradoxically, this
pathological behavior can even arise in random networks where nearly all the
servers have at most one task in the limit.
更多查看译文
关键词
coupling,drift analysis,load balancing,networks with skewed degrees
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要