Article Preview
Top1. Introduction
Internet Distributed System (IDS) is a collection of independent computers that are especially used to share the computing resources among them (Nishida, & Nguyen, 2013). The participated computer may provide or desire some kind of computing services. In general, these computers are characterized into two basic types, namely clients and servers, where servers are more computational power than clients. They are exchanging information through request and response messages. Moreover, the client initiates a request and the server replies with a response for the desired request. However, a server may act like a client by requesting a service request to other servers. This request-response message between a set of clients and servers is referred as a client-server assignment problem which aims to balance the service requests among the servers (i.e., load balancing) and minimizes the communication cost. The optimal assignment to this problem is NP-hard (Nishida, & Nguyen, 2013; Ba, Nguyen, Bose, & Tran, 2014; Fei, Ammar, & Zegura, 2002).
In IDS, a server may receive huge number of service requests from the clients. These many requests cannot be performed at a time as no server has unlimited resource capacity. In this case, the server may share few loads to other servers in order to fulfill the service requests of all the clients (Li et al., 2012). This load transfer may be occurred in the following two cases. 1) Intra-server load balancing and 2) Inter-server load balancing. In the first case, a server is sharing its loads to another server, i.e., present in its own group or cluster. In the latter case, a server is sharing its loads to another server that is present in other groups. Thus, the client-server problem is also viewed as a clustering problem (Nishida, & Nguyen, 2013).
In this paper, the following load balancing problem in IDS is presented. Given a set C of n clients, a set S of m servers, a data rate matrix R: C → C, an assignment matrix X: C → S and a load matrix L: C → S, the primary objective is to assign all the client requests to the servers so that the loads on the servers are equally distributed. An algorithm called swap-based intra- and inter-server (SIS) load balancing with padding is presented for the solution of this problem. The basic idea of the proposed algorithm can be described as follows. SIS first finds the total loads on the servers and distributes their loads by finding the disjoint sets of loads. Next, it swaps each load of the disjoint sets to balance the loads and finds the standard deviation of the total loads. It finally keeps the load sets which give the minimum standard deviation. Note that if the standard deviation among the server loads is zero, then the loads of the servers are fully balanced. The evaluation of the proposed algorithm is performed using a large set of clients and servers through simulation run. To determine the performance of the proposed algorithm, two metrics, namely the number of load comparisons and load factor are considered in the process of simulation. The simulation results show that the proposed algorithm properly distributes the loads among the servers with minimum number of load comparisons than the existing client-server algorithm (Nishida, & Nguyen, 2013; Bharati, Naidu, Kiran, Khune, & Vyas, 2014).
The major contributions are described as follows.
- •
Development of an intra- and inter-server load balancing algorithm for IDS
- •
Extensive simulation of the proposed algorithm with a large set of clients and servers
- •
Performance evaluation of the proposed load balancing algorithm in terms of the number of load comparisons and load factor
- •
Comparison of simulation results with an existing client-server algorithm to show the adoption of the proposed algorithm