ITR Collaborative Research: Modeling and Mitigation of Communication-Delay Effects on Load Balancing in Large-Scale Distributed Systems

这是新墨西哥大学(UNM)和田纳西-诺克斯维尔大学(UTK)的一项合作提案，旨在对由地理上相距遥远的计算元素(CE)组成的大规模分布式计算系统中的创新负载平衡策略进行建模、优化和测试。智力上的优点：随着使用CE之间共享通信介质的大规模分布式计算系统的出现，需要准确地了解信息传输延迟对这些系统的功能和控制的影响。这样的分布式系统可以包括移动CE、通过互联网连接的CE或分布在不同州或国家(例如代表各种数据库)的CE的网络。在大规模分布式系统中，由于节点之间的物理距离，节点之间的通信和负载转移活动具有明显的随机延迟。这种行为不同于在局部化分布式系统中通常假定的行为，对于这种情况，各组成CE彼此接近，受益于专用的快速通信介质。直觉和我们的蒙特卡罗模拟都明确表明，分布式系统中这种通信和负载转移延迟的存在会导致传统负载平衡算法的失败。因此，任务计算的动态性需要一个包含时延的分析框架，并在这个框架内实现包含时延的负载均衡策略的开发和优化。本项目的目标是开发一个通用的分析框架来建模时延侵扰的分布式系统的随机动态，并利用它来开发负载平衡策略，以缓解通信和负载传输延迟导致的性能下降或失败。该模型建立在一种新颖的基于再生的排队框架内，并将通过统计学习和随机预测来进行负载平衡优化。本计划中开发的负载平衡策略将在具有实际延迟的物理分布式系统环境中进行测试。为此，将开发和部署一个分布式计算试验台，将UTK的现有数据搜索计算机与将在联东综合团开发的微型克隆系统连接起来。布罗德影响：这里提出的工作的动机是(但不限于)联合PIS(UTK)目前对联邦调查局(FBI)国家DNA指数系统(NDIS)及其联合DNA指数系统(CODIS)软件所做工作中出现的实际、紧迫的问题。NDIS数据库及其内容搜索需求的预计增长需要迁移到并行计算平台，并可能迁移到大规模分布式系统，在大型分布式系统中，数据库分布或复制在地理上遥远的中心，这些中心通过带宽有限的共享通信介质连接。该计划的成果不仅将使上述系统受益，还将使广泛的公共、私人和政府数据库系统在分布式站点上执行搜索。拟议的研究还将用于改善大型虚拟实验室的运行。UNM的电气和计算机工程系创造了一种通过因特网远程控制仪器和模拟的有效方法。这一方法既适用于工业教育，也适用于远程教育，目前已投入使用，并可供指定用户使用。然而，该平台尚未在真实的分布式环境中进行大量用户测试。这项研究的方法将用于提高现有教育平台的绩效，并将其扩大到世界各地的大型机构网络。这项活动还将为研究生和本科生提供大量最先进的信息技术培训机会。

This is a collaborative proposal between The University of New Mexico (UNM) and The University of Tennessee-Knoxville (UTK) for modeling, optimization and testing of a innovative load balancing strategies in large-scale, distributed-computing systems consisting of geographically-distant computational elements (CEs).Intellectual Merit: With the emergence of large-scale distributed-computing systems that utilize a shared communication medium between the CEs, there is a need for accurately understanding the effect of delay in information transport on the functionality and control of these systems. Such distributed systems may include networks of mobile CEs, CEs that are connected through the Internet, or CEs that are distributed over different states or countries (representing various data bases, for example). Due to the physical distance between nodes in large-scale distributed systems, communication and load-transfer activity among the nodes is infested with tangible, random delays. This behavior is unlike what is ordinarily assumed in localized distributed systems, for which the constituent CEs are within proximity of each other, benefiting from a dedicated fast communication medium. Both intuition and our Monte-Carlo simulation definitively indicate that the presence of such communication and load-transfer delays in distributed systems can lead to the failure of traditional load balancing algorithms. Thus, a delay-inclusive analytical framework is needed for the dynamics of task computing, and it is within such a framework that the development and optimization of delay-inclusive load-balancing policies can be realized.The objectives of this program are to develop a general analytical framework for modeling the stochastic dynamics of delay-infested distributed systems and utilize it to develop load-balancing strategies that mitigate the performance degradation or failure caused by communication and load-transfer delays. The modeling is developed within a novel, regeneration-based queuing framework, and the load-balancing optimization will be carried out by means of statistical learning and stochastic prediction. The load-balancing strategies developed in this program will be tested in a physical distributed-system environment with realistic delays. To do so, a distributed-computing test-bed will be developed and deployed connecting existing data searching computers at UTK with a miniature clone system to be developed at UNM.Broader Impact: The work proposed here is motivated by (but not limited to) practical, pressing issues arising in the current work done by the Co-PIs (at UTK) on The Federal Bureau of Investigation (FBI) National DNA Index System (NDIS) and its Combined DNA Index System (CODIS) software. The projected growth of this NDIS database and in the demand for searches of its contents necessitates migration to a parallel computing platform, and potentially to large-scale distributed systems, where the database is distributed or duplicated over geographically distant centers which are connected by means of a bandwidth-limited shared communication medium. The outcomes of this program will not only benefit the above systems but also a broad range of public, private and government database systems that perform searches over distributed sites.The proposed research will also be utilized to improve the operation of large-scale virtual laboratories. The Electrical and Computer Engineering Department at UNM has created an efficient way for the remote control of instruments and simulations over the Internet. This approach is applicable to both industry and distance education, and it is currently operational and accessible for designated users. However, this platform has not been tested with a large number of users in a real, distributed environment. The methodology in this research will be applied to enhance the performance of the existing educational platform and scale up its reach to a large network of institutions worldwide. This activity will also provide tremendous training opportunities in state-of-the-art information technology for graduate and undergraduate students.