Optimal Load Balancing in Heterogeneous Distributed Systems with General Network Configurations

在分布式/并行计算机系统上平衡工作负载是提高其整体性能(例如，平均响应时间)的最重要问题之一。在这里，负载平衡是一种作业调度策略，它将作业作为一个整体，并将其分配给单个主机/处理器。通常，分布式/并行计算机系统中的作业可以被分成不同的类别。例如，数据、语音和视频分组之间可能存在自然区别。我们可以通过延迟函数来区分不同类别的作业。在该项目中，我们研究了分布式/并行计算机系统中这类多类别作业的负载平衡问题，该系统由由通常配置的通信/互连网络互连的异类主机/处理器(节点)组成，我们得到了一些关于该优化问题解的简单直观的理论结果。在此基础上，我们提出了一种有效的负载均衡算法…在整个分布式/并行系统上平衡负载的速度更快。该算法具有两个吸引人的特点。其一，该算法可以以去中心化的方式实现。为了确定最优负载均衡，每个节点仅根据关于自身的本地信息、通过其相邻链路的业务量以及通过其相邻链路连接的相邻节点的负载来连续地更新其负载均衡策略。另一个特点是结构简单明了，我们将该算法与其他著名算法的性能进行了比较。通过数值实验表明，该算法在计算时间上比其他算法具有更快的收敛速度。此外，我们将负载平衡原则作为一般原则之一，并将其应用于以下相关问题的研究：(A)研究并行联机事务处理(Parally On-Line Transaction Processing，简称为并行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