Serverless computing is leading the way to a simplified and general purpose programming model for the cloud. A key enabler behind serverless is efficient load balancing, which routes continuous workloads to appropriate backend resources. However, current load balancing algorithms implemented in Kubernetes native serverless platforms are simple heuristics without performance guarantee. Although policies such as Pod or JFIQ yield asymptotically optimal mean response time, the information they depend on are usually unavailable. In addition, dispatching jobs with strict deadlines, fractional workloads, and maximum parallelism bound to limited resources online is difficult because the resource allocation decisions for jobs are intertwined. To design an online load balancing algorithm without assumptions on distributions while maximizing the social welfare, we construct several pseudo-social welfare functions and cost functions, where the latter is to estimate the marginal cost for provisioning services to every newly arrived job based on present resource surplus. The proposed algorithm, named OnSocMax, works by following the solutions of several convex pseudo-social welfare maximization problems. It is proved to be $\alpha$-competitive for some $\alpha$ at least 2. We also validate OnSocMax with simulations and the results show that it distinctly outperforms several handcrafted benchmarks.


翻译:没有服务器的计算正在引导着一个简化和通用的云层编程模式。 没有服务器的一个关键使能因素是高效的负负平衡,它将连续的工作量引导到适当的后端资源。然而,目前在Kubernetes本地没有服务器的平台上实施的负负平衡算法是简单的超常算法,没有绩效保障。虽然Pod或JFIQ等政策产生一个简单的最佳平均反应时间,但是它们所依赖的信息通常没有。此外,在严格的最后期限、分数工作量和与有限在线资源联系在一起的最大平行的情况下,发送工作是困难的,因为资源分配决定是相互交织的。在分配的同时不假设分配,设计在线负平衡算法,同时尽量扩大社会福利,我们建立若干假社会福利功能和成本功能,后者是根据目前的资源盈余估算向新到的每一项工作提供服务的边际成本。提议的算法,称为OnSocMax, 其作用是遵循一些对等式伪社会福利最大化问题的解决方案。事实证明,对于一些工作来说,对于一些美元和半价的计算结果来说,我们还要用不同的模型来验证。

0
下载
关闭预览

相关内容

专知会员服务
17+阅读 · 2020年9月6日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
已删除
将门创投
14+阅读 · 2019年5月29日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
计算机 | ICDE 2020等国际会议信息8条
Call4Papers
3+阅读 · 2019年5月24日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
人工智能 | SCI期刊专刊/国际会议信息7条
Call4Papers
7+阅读 · 2019年3月12日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Arxiv
0+阅读 · 2022年2月11日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
已删除
将门创投
14+阅读 · 2019年5月29日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
计算机 | ICDE 2020等国际会议信息8条
Call4Papers
3+阅读 · 2019年5月24日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
人工智能 | SCI期刊专刊/国际会议信息7条
Call4Papers
7+阅读 · 2019年3月12日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Top
微信扫码咨询专知VIP会员