Optimal Load Balancing in Heterogeneous Distributed Systems with General Network Configurations

具有通用网络配置的异构分布式系统中的最佳负载平衡

• 批准号: 08458061
• 负责人: LI Jie
• 金额: $ 4.67万
• 依托单位: UNIVERSITY OF TSUKUBA
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08458061/
• 关键词: Load balancing; distributed systems; networks; heterogeneous; parallel OLTP; reliability analysis; disk array; performance; システム性能; 一般的なネットワーク構造

Balancing the Workload over a distributed/parallel computer system is one of the most important issues to improve its overall performance (e.g., mean response time). Here the load balancing is a job-scheduling policy which takes a job as a whole and assigns it to a single host computer/processor. Often, jobs in a distributed/parallel computer system can be divided into different classes. For instance, there may be a natural distinction among data, voice, and video packets. We may distinguish different classes of jobs by their delay functions. In the project, we deal with the load balancing problems for such multi-class jobs in a distributed/parallel computer system that consists of heterogeneous host computers/processors (nodes) interconnected by a generally configured communication/interconnection network.We derive a number of simple and intuitive theoretical results on the solution of the optimization problem. On the basis of these results, we propose an effective load balancing algo … More rithm for balancing the load over an entire distributed/parallel system.The proposed algorithm has two attractivei features. One is that the algorithm can be implemented in a decentralized fashion. In order to determine the optimal load balancing, each node successively updates its load balancing policy based only on the local information about itself, the traffic through its adjacent links, and the load of its neighboring nodes connected by its adjacent links. Another feature is very simple and straightforward structure.We compare the performance of our proposed algorithm and other famous algorithms. By using numerical experiments, we show that the proposed algorithm has much faster convergence in terms of computational time than the other algorithms.Furthermore, we consider the load balancing principle as one of general principles and apply it to study the following relative problems :(a) Study the performance of parallel On-Line transaction processing (Parallel OLTP) systems. We proposed the efficient scheduling and concurrency control algorithms to improve the performance of parallel OLTP systems.(b)Study the cell assignment in Personal Communication Service (PCS) networks. We proposed a balanced algoirthm to solve the cell assignment problem in PCS networks.Besides the performance point of view, we also study the systems from reliability point of view. Specifically, we study the important reliability problems in disk array systems and propose new modeling analytic methods to show the reliability behaviors of the disk array systems in exact way. Less

在分布式/并行计算机系统上平衡工作量是提高其整体性能（例如平均响应时间）的最重要问题之一。在这里，负载平衡是一个工作的策略，该策略从整体上完成工作并将其分配给单个主机计算机/处理器。通常，分布式/并行计算机系统中的作业可以分为不同的类。例如，数据，语音和视频数据包之间可能存在自然分布。我们可以通过其延迟功能来区分不同类别的作业。在该项目中，我们处理了通过分布式/并行计算机系统中此类多级作业的负载平衡问题，该系统由通过普遍配置的通信/互连网络相互关联的异质主机计算机/处理器（节点）组成。我们得出了许多简单且直接直接的理论结果，这些结果涉及优化问题解决方案。在这些结果的基础上，我们提出了一个有效的负载平衡算法……更多的RITHM用于平衡整个分布式/并行系统上的负载。该算法具有两个吸引人的功能。一个是该算法可以以分散的方式实施。为了确定最佳负载平衡，每个节点仅根据本地信息，通过其相邻链接的流量以及通过其相邻链接连接的相邻节点的负载成功更新其负载平衡策略。另一个功能是非常简单明了的结构。我们比较了我们提出的算法和其他著名算法的性能。通过使用数值实验，我们表明所提出的算法在计算时间方面的收敛速度要比其他算法更快。furthermore。我们将负载平衡原理视为一般原理之一，并将其​​应用于以下相对问题：（a）研究并行的上线交易处理（并行OLTPALLALE OLTPEL OLTPEL）。我们提出了有效的调度和并发控制算法，以提高平行OLTP系统的性能。（b）研究个人通信服务（PCS）网络中的细胞分配。我们提出了一个平衡的算法，以解决PCS网络中的细胞分配问题，以解决pcs网络中。分析方法以精确的方式显示磁盘阵列系统的可靠性行为。较少的

项目成果

Jiahong Wang, Jie Li, and Hisao Ka-meda: "Parallel Transaction Processing Based on Wait-Depth Priority over an Interconnection Networking Environment" Proc.of the 13th International C-onference on Advanced Science and Technology(ICAST 97),USA. 249-255 (19

Jiahong Wang、Jie Li 和 Hisao Ka-meda：“基于互联网络环境上的等待深度优先级的并行事务处理”第 13 届国际先进科学技术会议 (ICAST 97) 会议记录，美国。

H.Kameda, T.Kozawa, and J.Li: "Anomalous Relations among Various Performance Objectives in Distributed Computer System" IEEE Proc.of World Cong on Systems Simulation. 459-465 (1997)

H.Kameda、T.Kozawa 和 J.Li：“分布式计算机系统中各种性能目标之间的异常关系”IEEE Proc.of World Cong 系统仿真。

Jie Li, Hisao Kameda, and Hideto I-toh.: "Balanced Assignment of Cells in PCS Networks" Proc.of 12th ACM Symposium on Ap-plied Computing(SAC'97),USA. 297-301 (1997)

Jie Li、Hisao Kameda 和 Hideto I-toh.：“PCS 网络中的小区平衡分配”第 12 届 ACM 应用计算研讨会 (SAC97) 会议记录，美国。

Jiahong Wang, Jie Li, and Hisao Ka-meda: "Simulation studies on ConcurrencyControl in Parallel Transaction Process-ing Systems" Parallel Computing. 23・6. 755-775 (1997)

Jiahong Wang、Jie Li 和 Hisao Ka-meda：“并行事务处理系统中的并发控制的模拟研究”并行计算 23・6。

X.Wu, J.Li, and H.Kameda: "Reliablity Analysis of Disk Array Organizations by Considering Uncorrectable Bit Errors" Proc.of IEEE Symp on Reliable Dist Sys. 2-9 (1997)

X.Wu、J.Li 和 H.Kameda：“考虑不可纠正的位错误对磁盘阵列组织进行可靠性分析”Proc.of IEEE Symp on Reliable Dist Sys。