Optimal Load Balancing in Heterogeneous Distributed Systems with General Network Configurations

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

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