Effect of network latency on load sharing in distributed systems

Distributed computing systems consist of computers interconnected by communications links. In such systems, Load sharing is an important technique used to improve system performance in which jobs are transferred from overloaded nodes to underloaded ones. However, due to the ubiquitous and inescapable presence of network latencies, various pitfalls arise which can adversely affect the beneficial effects of job transfer.In this paper, we present an investigation into the effect of network latency on load sharing. The notions of Transfer Pair, and Load-Sharing Window are rigorously defined. A general expression for the probability distribution function of the Load-Sharing Window is derived. A class of rules, called quantile rules, is introduced and their role in avoiding unproductive job redistribution in spite of network latency, as well as to make multiple job transfers, is explained. The general technique is applied to the specific case of a distributed computing system consisting of M/M/1 queues. For this case, an expression for the mean of the Load-Sharing Window is derived. Numerical computations are presented, and their significance discussed.     

Adaptive load sharing in heterogeneous distributed systems

In this paper, we study the performance characteristics of simple load sharing algorithms for heterogeneous distributed systems. We assume that nonnegligible delays are encountered in transferring jobs from one node to another. We analyze the effects of these delays on the performance of two threshold-based algorithms called Forward and Reverse. We formulate queuing theoretic models for each of the algorithms operating in heterogeneous systems under the assumption that the job arrival process at each node in Poisson and the service times and job transfer times are exponentially distributed. The models are solved using the Matrix-Geometric solution technique. These models are used to study the effects of different parameters and algorithm variations on the mean job response time: e.g., the effects of varying the thresholds, the impact of changing the probe limit, the impact of biasing the probing, and the optimal response times over a large range of loads and delays. Wherever relevant, the results of the models are compared with the M/M/ 1 model, representing no load balancing (hereafter referred to as NLB), and the M/M/K model, which is an achievable lower bound (hereafter referred to as LB).     

A two-class parallel system with general service times of the parallel class

A parallel system with two job classes is analyzed. Type-1 jobs require one server for their execution and have exponentially distributed service times while type-2 jobs need two servers and have general service times. The model consists of a single queue served by two servers that may work either independently or in parallel. It is assumed that all jobs are rigid and share the servers according to pure space sharing. We provide closed-form expressions, exact as well as approximate, for various performance measures of interest. The approximate formula is found to be extremely accurate for various distributions of the service times of type-2 jobs. Furthermore, the maximal occupancy of the servers as well as the maximal throughput are examined. Finally, numerical results to investigate the impact of each parameter on system performance are conducted.     

Competitive Analysis of Network Load Balancing

This paper presents a theoretical analysis of the Load Balancing Problem (LBP) in a network of processing units. The performance objective is to minimize the makespan, i.e., the time spent to finish all jobs in a network of processing units. Because of the communication delay that results from the network topology, it is impossible to have a strategy which obtains the exact optimum under all load distributions. Instead, we measure the information efficiency of a load balancing policy by the worst case ratio of the solution (for each load distribution) of a load balancing policy to the optimal solution (for the same load distribution) assuming that processors have complete information about the load distribution over the network. This ratio is called the competitive ratio of this strategy [17, 24, 34]. In particular, a policy is calledcompetitiveif this ratio is bounded by a constant. As a first step, we discuss the centralized LBP, where all the processors have complete information of the load distribution over a network. Its solution serves as a benchmark to compare with realistic strategies, both in theoretical analysis, and experimental and simulational studies of distributed algorithms. We show that when jobs have different sizes, even with preemptive scheduling, LBP is NP–complete. When the jobs are of the same size, we give a polynomial algorithm, using network–flow techniques, which extends to approximate solutions for jobs of different sizes. We apply this benchmark solution in order to analyze the competitiveness for three network topologies: completely connected graphs, rings, and hierarchical completek-ary trees. The constant competitive ratio results for complete network and hierarchical completek-ary trees are applied to a study on the issues of network designs suitable for the LBP. We further discuss the problem for general networks with jobs of different sizes for slightly weaker results than those for the constant competitive ratio requirement. Finally, we comment on the related issues of job partitioning over parallel/distributed systems.     

On the exact and approximate throughput analysis of closed queuingnetworks with blocking

A type of blocking is investigated in which, on completion of its service, a job attempts to enter a new station. If, at that moment, the destination station is full, the job is forced to reside in the server of the source station until a place becomes available in the destination station. The server of the source station remains blocked during this period of time. This model is known as a queuing network with transfer blocking. The state space of queuing networks with blocking is reduced by considering finite capacities of the stations. A nonblocking queuing network with the appropriate total number of jobs is derived. The state space of this network is equal to the state space of the blocking queuing network. The transformation of state space is exact for two-station networks and approximate for three-or-more station cases. The approximation has been validated by executing several examples, including stress tests. In all investigated network models, the approximate throughput results deviate, on the average, less than 3% from the simulation results     

Computational algorithms for networks of queues with rejection blocking

Summary Open, closed and mixed queueing networks with reversible routing, multiple job classes and rejection blocking are investigated. In rejection blocking networks blocking event occurs when upon completion of its service of a particular station's server, a job attempts to proceed to its next station. If, at that moment, its destination station is full, the job is rejected. The job goes back to the server of the source station and immediately receives a new service. This is repeated until the next station releases a job and a place becomes available. In the model jobs may change their class membership and general service time distributions depending on the job class are allowed. Two station types are considered: Either the scheduling discipline is symmetric, in which case the service time distributions are allowed to be general and dependent on the job class or the service time distributions at a station are all identical exponential distributions, in which case more general scheduling disciplines are allowed. An exact product form solution for equilibrium state probabilities is presented. Using the exact product form solution of the equilibrium state distribution, algorithms for computation of performance measures, such as mean number of jobs and throughputs, are derived. The complexity of the algorithms is discussed.     

Comparing job allocation schemes where service demand is unknown

In this paper a novel job allocation scheme in distributed systems (TAGS) is modelled using the Markovian process algebra PEPA. This scheme requires no prior knowledge of job size and has been shown to be more efficient than round robin and random allocation when the job size distribution is heavy tailed and the load is not high. In this paper the job size distribution is assumed to be of a phase-type and the queues are bounded. Numerical results are derived and compared with those derived from models employing random allocation and the shortest queue strategy. It is shown that TAGS can perform well for a range of performance metrics. Furthermore, an attempt is made to characterise those scenarios where TAGS is beneficial in terms of the coefficient of variation and load.     

M/M/1-PS queue and size-aware task assignment

We consider a distributed server system in which heterogeneous servers operate under the processor sharing (PS) discipline. Exponentially distributed jobs arrive to a dispatcher, which assigns each task to one of the servers. In the so-called size-aware system, the dispatcher is assumed to know the remaining service requirements of some or all of the existing jobs in each server. The aim is to minimize the mean sojourn time, i.e., the mean response time. To this end, we first analyze an M/M/1-PS queue in the framework of Markov decision processes, and derive the so-called size-aware relative value of state, which sums up the deviation from the average rate at which sojourn times are accumulated in the infinite time horizon. This task turns out to be non-trivial. The exact analysis yields an infinite system of first order differential equations, for which an explicit solution is derived. The relative values are then utilized to develop efficient dispatching policies by means of the first policy iteration (FPI). Numerically, we show that for the exponentially distributed job sizes the myopic approach, ignoring the future arrivals, yields an efficient and robust policy when compared to other heuristics. However, in the case of highly asymmetric service rates, an FPI based policy outperforms it. Additionally, the size-aware relative value of an M/G/1-PS queue is shown to be sensitive with respect to the form of job size distribution, and indeed, the numerical experiments with constant job sizes confirm that the optimal decision depends on the job size distribution.     

A metric of fairness for parallel job schedulers

Fairness is an important aspect in queuing systems. Several fairness measures have been proposed in queuing systems in general and parallel job scheduling in particular. Generally, a scheduler is considered unfair if some jobs are discriminated whereas others are favored. Some of the metrics used to measure fairness for parallel job schedulers can imply unfairness where there is no discrimination (and vice versa). This makes them inappropriate. In this paper, we show how the existing approach misrepresents fairness in practice. We then propose a new approach for measuring fairness for parallel job schedulers. Our approach is based on two principles: (i) as jobs have different resource requirements and find different queue/system states, they need not have the same performance for the scheduler to be fair and (ii) to compare two schedulers for fairness, we make comparisons of how the schedulers favor/discriminate individual jobs. We use performance and discrimination trends to validate our approach. We observe that our approach can deduce discrimination more accurately. This is true even in cases where the most discriminated jobs are not the worst performing jobs. Copyright © 2008 John Wiley & Sons, Ltd.     

An enhanced meta-scheduling system for grid computing that considers the job type and priority

Meta-scheduling systems play a crucial role in scheduling jobs that are submitted for execution and require special attention because an increasing number of jobs are being executed using a limited number of resources. The primary problem of meta-scheduling is selecting the best resources (sites) to use to execute the underlying jobs while still achieving the following objectives: reducing the mean job turnaround time, ensuring site load balance, and considering job priorities. We introduce an enhanced meta-scheduling system, called Job Nature Meta-scheduling over Grid (JNMgrid), that achieves these objectives. JNMgrid consists of three components: (1) Job Analyzer and Monitor, which is responsible for determining the types of jobs in specific ratios; (2) Job Decider, which is responsible for matching the jobs with the appropriate resources; and (3) Job Batcher, which is responsible for determining the best number of jobs for execution. The performance of JNMgrid is compared with similar existing systems, such as Random, Queue Length, File Access Cost, and File Access Cost + Job Queue Access Cost. The simulation results demonstrate that JNMgrid outperforms these systems and can thus be deployed in any grid middleware to improve sharing of limited resources among grid users.     

农村科技信息共享服务系统的设计和实现

随着农村信息化建设的迅速发展,有效的信息共享及信息服务成了急待解决的重要问题。苯文提出了一个新的信息共享服务系统的框架,它通过统一、标准的信息接口、资源描述元数据及共享协议,将分布异构的农村科技信息有效地整合到共享平台下,使各个分散的信息源能够方便、快捷地成为共享服务系统中的一部分。系统通过共享访问模块访问信息源,实现信息共享,快速、准确地提供全方位、多层次的信息服务。     

一种支持服务网格的动态负载平衡系统

为了实现服务网格系统内负载的均衡分布,提高资源利用率和系统的吞吐率,设计并实现了一种基于服务网格环境的动态负载平衡系统。提出了层次式负载平衡调度模式,给出了本系统结构形式,设计并实现了一种综合考虑各局部代理作业数和各个局部代理性能以及当前的负载情况的动态双阈值作业分配算法。实验结果表明,此算法能有效地基于负载分派作业,达到了提高网格内分布资源的利用率和减少作业调度时间的目的。     

The probability of load balancing success in a homogeneous network

The problem of load balancing in distributed systems composed of several homogeneous sites connected by a subnet is examined. The author determines a general formula for the probability that any one site in the system is underloaded while some other site in the system is overloaded. This probability can be used to define the likelihood of load balancing success in a distributed operating system. This probability gives insight into the utilization of the system and is an aid in determining a measure of effectiveness of the system. From this formula one can determine this probability when the workload is composed of processes typical to distributed systems. The influence of variants in the load balancing algorithm on this probability is demonstrated     

异构计算中的负载共享

在基于消息传递的异构并行计算系统中 ,各处理器或计算机具有自制和独立地调度、执行作业的能力 .当一个可划分的作业初始位于一个处理器上时 ,为了提高计算性能 ,该处理器可以请求其他异构处理器负载共享 ,参与协同计算 ,减少作业的完成时间 .该文提出了异构计算负载共享的一种方案 .首先 ,调用负载共享协议 ,收集当前各处理器参与负载共享的许可数据 ,包括共享时间段、计算能力等 .然后 ,构造一个作业量与作业完成时间之间的关系函数 .该函数是选择一组合适的处理器群、优化作业划分、作业完成时间最小的理论基础 .最     

Evaluation of load sharing in HARTS with consideration of itscommunication activities

We rigorously analyze load sharing (LS) in a distributed real-time system, called HARTS (Hexagonal Architecture for Real-Time Systems), while considering LS-related communication activities, such as task transfers and state-change broadcasts. First, we give an overview of the general distributed real-time LS approach described previously, and then adapt it to HARTS by exploiting the topological properties of HARTS. Second, we model task arrival/completion/transfer activities in HARTS as a continuous-time Markov chain from which we derive the distribution of queue length and the rate of generating LS-related traffic-task transfer-out rate and state-region change broadcast rate. Third, we derive the distribution of packet delivery time as a function of LS-related traffic rates by characterizing the hexagonal mesh topology and the virtual cut-through capability of HARTS. Finally, we derive the distribution of task waiting time (the time a task is queued for execution plus the time it would spend if the task is to be transferred), from which the probability of a task failing to complete in time, called the probability of dynamic failure, can be computed. The results obtained from our analytic models are verified through event-driven simulations, and can be used to study the effects of varying various design parameters on the performance of LS while considering the details of LS-related communication activities     

Performance analysis of a discrete-time queuing system with a correlated train arrival process

In this paper, we present an exact transient and steady-state discrete-time queuing analysis of a statistical multiplexer with a finite number of input links and whose arrival process is correlated and consists of a train of a fixed number of fixed-length packets. The functional equation describing this queuing model is manipulated and transformed into a mathematical tractable form. This allows us to derive the transient probability generating function (pgf) of the buffer occupancy. From this transient pgf, time-dependent performance measures such as transient probability of empty buffer, transient mean of buffer occupancy and instantaneous packet overflow probabilities are derived. By applying the final-value theorem, the corresponding exact expressions for the steady-state pgf of the queue length and packet arrivals are derived. We also show how the transient analysis provides insights into the derivation of the system's busy period distribution. Closed-form expressions for the mean packet and message delays are also provided. The paper presents significant results on the transient and steady-state analysis of statistical multiplexers with N input links and correlated train arrivals.     

Performance analysis of parallel processing systems

A bulk arrival M/sup x//M/c queuing system is used to model a centralized parallel processing system with job splitting. In such a system, jobs wait in a central queue, which is accessible by all the processors, and are split into independent tasks that can be executed on separate processors. The job response-time consists of three components: queuing delay, service time, and synchronization delay. An expression for the mean job response-time is obtained for this centralized parallel-processing system. Centralized and distributed parallel-processing systems (with and without job-splitting) are considered and their performances compared. Furthermore, the effects of parallelism and overheads due to job-splitting are investigated.<>     

Adaptive hierarchical scheduling policy for enterprise grid computing systems

In an enterprise grid computing environments, users have access to multiple resources that may be distributed geographically. Thus, resource allocation and scheduling is a fundamental issue in achieving high performance on enterprise grid computing. Most of current job scheduling systems for enterprise grid computing provide batch queuing support and focused solely on the allocation of processors to jobs. However, since I/O is also a critical resource for many jobs, the allocation of processor and I/O resources must be coordinated to allow the system to operate most effectively. To this end, we present a hierarchical scheduling policy paying special attention to I/O and service-demands of parallel jobs in homogeneous and heterogeneous systems with background workload. The performance of the proposed scheduling policy is studied under various system and workload parameters through simulation. We also compare performance of the proposed policy with a static space–time sharing policy. The results show that the proposed policy performs substantially better than the static space–time sharing policy.     

Incorporating System Overhead in Queuing Network Models

Multiclass queuing network models of multiprogramming computer systems are frequently used to predict the performance of computing systems as a function of user workload and hardware configuration. This paper examines three different methods for incorporating operating system overhead in multiclass queuing network models. The goal of the resultant model is to provide an accurate account of the processing performance and the system CPU overhead of each of the several different types of jobs (batch, timesharing, transaction processing, etc.) that together make up the multiprogramming workload. The first method introduces an operating sysbtm workload consisting of a fixed number of jobs to represent system CPU overhead processing. The second method extends the jobs' CPU service requests to include explicitly the CPU overhead necessary for system processing. The third method employs a communicating set of user and system job classes so that the CPU overhead can be modeled by switching jobs from user to system class whenever they require system CPU service. The capabilities and accuracy of the three methods are assessed and compared against performance and overhead data measured on a Univac 1110 computer.     

A Queuing Model for Evaluating the Transfer Latency of Peer-to-Peer Systems

This paper presents a queuing model to evaluate the latency associated with file transfers or replications in peer-to-peer (P2P) computer systems. The main contribution of this paper is a modeling framework for the peers that accounts for the file size distribution, the search time, load distribution at peers, and number of concurrent downloads allowed by a peer. We propose a queuing model that models the nodes or peers in such systems as M/G/1/K processor sharing queues. The model is extended to account for peers which alternate between online and offline states. The proposed queuing model for the peers is combined with a single class open queuing network for the routers interconnecting the peers to obtain the overall file transfer latency. We also show that in scenarios with multipart downloads from different peers, a rate proportional allocation strategy minimizes the download times.