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现有的数据搜索计算机与UNM开发的微型克隆系统连接起来。这里提出的工作的动机是（但不限于）实用的，Co-PI（在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.