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

平衡分布式/并行计算机系统上的工作负载是提高其整体性能（例如，平均响应时间）的最重要问题之一。这里的负载平衡是一种作业调度策略，它将一个作业作为一个整体，并将其分配给单个主机/处理器。通常，分布式/并行计算机系统中的作业可以分为不同的类。例如，数据、语音和视频包之间可能存在自然的区别。我们可以通过延迟函数来区分不同类别的工作。在该项目中，我们处理分布式/并行计算机系统中此类多类作业的负载平衡问题，该系统由异构主机/处理器（节点）组成，通过一般配置的通信/互连网络相互连接。我们得到了一些简单直观的关于优化问题解的理论结果。在此基础上，我们提出了一种有效的负载均衡算法，该算法可以在整个分布式/并行系统中实现负载均衡。该算法具有两个吸引人的特点。一是该算法可以以去中心化的方式实现。为了确定最优的负载均衡，每个节点仅根据自身的本地信息、通过相邻链路的流量以及通过相邻链路连接的相邻节点的负载，依次更新其负载均衡策略。另一个特点是结构非常简单直接。我们比较了我们提出的算法和其他著名算法的性能。数值实验表明，该算法在计算时间上比其他算法收敛速度快得多。此外，我们将负载平衡原则作为一般原则之一，并将其应用于以下相关问题的研究：(a)研究并行联机事务处理（parallel OLTP）系统的性能。为了提高并行OLTP系统的性能，我们提出了高效的调度和并发控制算法。(b)研究个人通信业务（PCS）网络中的小区分配。针对PCS网络中的小区分配问题，提出了一种平衡算法。除了从性能的角度，我们还从可靠性的角度对系统进行了研究。具体地说，我们研究了磁盘阵列系统中重要的可靠性问题，提出了新的建模分析方法，以便更准确地显示磁盘阵列系统的可靠性行为。少

项目成果

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: "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 系统仿真。

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。

Jiahong Wang, Jie Li, and Hisao Ka-meda: "High Performance Parallel Transa-ction Processing" Proc.of International Conference on Parallel and Disterbuted Computing a-nd Networks,Singapore. 27-30 (1997)

Jiahong Wang、Jie Li 和 Hisao Ka-meda：新加坡并行和分布式计算与网络国际会议的“高性能并行事务处理”会议记录。