CIF: Small: Load Balancing for Cloud Networks: Data Locality Issues and Modern Algorithms

CIF:小型:云网络的负载平衡:数据局部性问题和现代算法

基本信息

  • 批准号:
    2113027
  • 负责人:
  • 金额:
    $ 42.32万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2021
  • 资助国家:
    美国
  • 起止时间:
    2021-07-01 至 2024-06-30
  • 项目状态:
    已结题

项目摘要

Distributing incoming tasks among the back-end servers or virtual machines in a balanced way is crucial for the seamless functioning of large-scale service systems, such as data centers and cloud networks. As the bulk of modern applications now tend to come with specialized service requirements, these systems are suffering from stringent task-server compatibility constraints arising due to data locality. In simple terms, it means that the resources to process a particular type of task are available to only a small sub-collection of servers and cannot be accessed by the entire network. This issue of task-server compatibility has made large-scale load balancing ever more challenging. State-of-the-art heuristics are predominantly based on "full-flexibility" models that ignore the compatibility aspect and assume that any task can be processed by any server. Naturally, algorithms implemented from these heuristics cause a major adverse impact on the user-perceived delay performance. The current practice to deal with this problem is to find ad-hoc solutions in specific cases. With the investigator's expertise in the area of stochastic modeling and performance analysis, the project is taking a thorough and structured approach to address this issue. On successful completion, the findings will contribute to designing modern load balancing algorithms.The theoretical research agenda of the project is divided into two thrusts: (1) to identify classes of optimal compatibility constraints for existing algorithms, and (2) to develop novel compatibility-aware distributed algorithms for arbitrary systems. The research community has discovered several breakthrough load balancing algorithms over the last few years. These algorithms have excellent performance guarantees in the full-flexibility setup. The goal of Thrust 1 is to identify classes of compatibility constraints that can still preserve such performance guarantees under such existing algorithms. Employing these findings, a service provider can design compatibility structures that enjoy the performance benefits of a fully flexible system, by carefully placing the resource files across the servers. When designing the compatibility structure is not an option, state-of-the-art algorithms exhibit poor performance. In such cases, Thrust 2 aims to develop novel distributed algorithms with provable performance guarantees, that take the compatibility structure into consideration during task assignment. This part of the project is having direct consequences for the practitioners in implementing new algorithmic heuristics for modern systems. On the methodological side, the investigation requires the development of a theoretical foundation for the analysis of structurally constrained systems driven by stochastic inputs. The project is advancing the area of mean-field analysis, which has been a primary tool in the performance analysis of randomized algorithms for large-scale systems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
在后端服务器或虚拟机之间以平衡的方式分配传入任务对于数据中心和云网络等大规模服务系统的无缝运行至关重要。由于大部分现代应用程序现在往往带有专门的服务要求,这些系统正遭受严格的任务服务器兼容性约束,由于数据的本地性。简单地说,这意味着处理特定类型任务的资源仅可用于服务器的一小部分子集合,而不能被整个网络访问。这个任务服务器兼容性问题使得大规模负载平衡变得更加具有挑战性。最先进的代理主要基于“完全灵活”的模型,该模型忽略了兼容性方面,并假设任何任务都可以由任何服务器处理。当然,从这些算法实现的算法会对用户感知的延迟性能产生重大的不利影响。目前处理这一问题的做法是在具体情况下找到临时解决办法。凭借研究人员在随机建模和性能分析领域的专业知识,该项目正在采取彻底且结构化的方法来解决这个问题。该项目的理论研究议程分为两个重点:(1)为现有算法确定最佳兼容性约束类别,(2)为任意系统开发新的兼容性感知分布式算法。在过去的几年里,研究界已经发现了几种突破性的负载平衡算法。这些算法在全柔性设置中具有优异的性能保证。目标1是确定类的兼容性约束,仍然可以保持这样的性能保证在现有的算法。利用这些发现,服务提供商可以设计兼容性结构,享受一个完全灵活的系统的性能优势,通过仔细放置跨服务器的资源文件。当设计兼容性结构不是一种选择时,最先进的算法表现出较差的性能。在这种情况下,推力2的目标是开发新的分布式算法与可证明的性能保证,考虑到在任务分配的兼容性结构。该项目的这一部分对实践者在现代系统中实现新的算法算法有直接的影响。在方法论方面,调查需要发展的理论基础,结构约束系统的随机输入驱动的分析。该项目正在推进平均场分析领域,该领域一直是大规模系统随机算法性能分析的主要工具。该奖项反映了NSF的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(7)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
网络系统中的可扩展负载平衡:最新进展调查
  • DOI:
    10.1137/20m1323746
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    10.2
  • 作者:
    der Boor, Mark Van;Borst, Sem C.;Van Leeuwaarden, Johan S.;Mukherjee, Debankur
  • 通讯作者:
    Mukherjee, Debankur
Smoothed Online Optimization with Unreliable Predictions
A New Approach to Capacity Scaling Augmented with Unreliable Machine Learning Predictions
通过不可靠的机器学习预测增强容量扩展的新方法
  • DOI:
    10.1287/moor.2023.1364
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    1.7
  • 作者:
    Rutten, Daan;Mukherjee, Debankur
  • 通讯作者:
    Mukherjee, Debankur
Self-Learning Threshold-Based Load Balancing
基于自学习阈值的负载平衡
  • DOI:
    10.1287/ijoc.2021.1100
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    2.1
  • 作者:
    Goldsztajn, Diego;Borst, Sem C.;van Leeuwaarden, Johan S.;Mukherjee, Debankur;Whiting, Philip A.
  • 通讯作者:
    Whiting, Philip A.
Load Balancing Under Strict Compatibility Constraints
严格兼容性约束下的负载均衡
  • DOI:
    10.1287/moor.2022.1258
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    1.7
  • 作者:
    Rutten, Daan;Mukherjee, Debankur
  • 通讯作者:
    Mukherjee, Debankur
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Debankur Mukherjee其他文献

Asymptotic Optimality of Power-of-d Load Balancing in Large-Scale Systems
大型系统中 d 次方负载平衡的渐近最优性
  • DOI:
    10.1287/moor.2019.1042
  • 发表时间:
    2016
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Debankur Mukherjee;S. Borst;J. V. Leeuwaarden;P. Whiting
  • 通讯作者:
    P. Whiting
Rates of convergence of the join the shortest queue policy for large-system heavy traffic
大型系统大流量加入最短队列策略的收敛率
  • DOI:
    10.1007/s11134-022-09803-5
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    1.2
  • 作者:
    Debankur Mukherjee
  • 通讯作者:
    Debankur Mukherjee
Best of Both Worlds: Stochastic and Adversarial Convex Function Chasing
两全其美:随机和对抗性凸函数追逐
  • DOI:
    10.48550/arxiv.2311.00181
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Neelkamal Bhuyan;Debankur Mukherjee;Adam Wierman
  • 通讯作者:
    Adam Wierman
Aktueller Stand zur Neurobiologie von COVID-19
COVID-19 神经生物学最新立场
  • DOI:
    10.1055/a-1213-1778
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Daan Rutten;Nicolas H. Christianson;Debankur Mukherjee;A. Wierman
  • 通讯作者:
    A. Wierman
Independent-set reconfiguration thresholds of hereditary graph classes
  • DOI:
    10.1016/j.dam.2018.05.029
  • 发表时间:
    2018-12-11
  • 期刊:
  • 影响因子:
  • 作者:
    Mark de Berg;Bart M.P. Jansen;Debankur Mukherjee
  • 通讯作者:
    Debankur Mukherjee

Debankur Mukherjee的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Debankur Mukherjee', 18)}}的其他基金

CPS: Medium: Collaborative Research: Developing Data-driven Robustness and Safety from Single Agent Settings to Stochastic Dynamic Teams: Theory and Applications
CPS:中:协作研究:从单代理设置到随机动态团队开发数据驱动的鲁棒性和安全性:理论与应用
  • 批准号:
    2240982
  • 财政年份:
    2023
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

CC* INTEGRATION-SMALL: ADIABATIC MICROSERVICE LEVEL LOAD BALANCED FORWARDING ON PISA SWITCH FOR ACCELERATING URGENT PROCESSES IN SCIENCE DATA CENTER NETWORKS
CC* 集成小型:PISA 交换机上的绝热微服务级负载平衡转发,用于加速科学数据中心网络中的紧急进程
  • 批准号:
    2346729
  • 财政年份:
    2024
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Standard Grant
Small load electrodynamic testing machine
小负载电动试验机
  • 批准号:
    537597911
  • 财政年份:
    2024
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Major Research Instrumentation
Severity assessment of small wrinkles in pipelines subject to load cycles
受负载循环影响的管道中小皱纹的严重性评估
  • 批准号:
    493087-2015
  • 财政年份:
    2020
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Collaborative Research and Development Grants
CNS: Core: Small: Energy and Load Management in Data Centers: Online Optimization and Learning
CNS:核心:小型:数据中心的能源和负载管理:在线优化和学习
  • 批准号:
    1908298
  • 财政年份:
    2019
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Standard Grant
CIF: Small: Fundamental Tradeoffs Between Communication Load and Storage Resources in Distributed systems
CIF:小:分布式系统中通信负载和存储资源之间的基本权衡
  • 批准号:
    1910309
  • 财政年份:
    2019
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Standard Grant
Severity assessment of small wrinkles in pipelines subject to load cycles
受负载循环影响的管道中小皱纹的严重性评估
  • 批准号:
    493087-2015
  • 财政年份:
    2019
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Collaborative Research and Development Grants
SHF: Small: Design Methodology for Efficient and Reliable Medium-Power Point-of-Load Converters via In-Field Built-in Self-Calibration
SHF:小型:通过现场内置自校准实现高效、可靠的中功率负载点转换器的设计方法
  • 批准号:
    1910380
  • 财政年份:
    2019
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Standard Grant
CSR: Small: Cross-Layer Design of Power Delivery and Load Balancing for Green Data Centers
CSR:小型:绿色数据中心的电力传输和负载平衡的跨层设计
  • 批准号:
    1837924
  • 财政年份:
    2018
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Standard Grant
Study on embankment of Small Earthfill Dam at Acting Load due to Inflow of Sediment
作用荷载下泥沙流入小型土坝路堤研究
  • 批准号:
    17K15349
  • 财政年份:
    2017
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)
Severity assessment of small wrinkles in pipelines subject to load cycles
受负载循环影响的管道中小皱纹的严重性评估
  • 批准号:
    493087-2015
  • 财政年份:
    2017
  • 资助金额:
    $ 42.32万
  • 项目类别:
    Collaborative Research and Development Grants
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了