Mirroring

CS 495P MAIN PROJECT REPORT

Mirroring and Load Balancing Submitted in Partial Fulfillment of the Degree of

Bachelor of Technology

By

Denzil Thomas (Y2.092) Elvin P. Abraham (Y2.060)

Under the guidance of

Mr. Vinod P

Department Of Computer Engineering

NATIONAL INSTITUTE OF TECHNOLOGY CALICUT

Kerala, India April 2006

National Institute Of Technology, Calicut Department Of Computer Science Engineering

Certified That This Main Project Report Entitled

Mirroring and Load Balancing Is a bonafide report of the work done by

Denzil Thomas Y2.092 Elvin P. Abraham Y2.060 In partial fulfillment of the

Bachelor of Technology Degree

Mr. Vinod Pathari Lecturer Dept. of Computer Engineering

Dr. M. P. Sebastian Professor and Head Dept. of Computer Engineering

Acknowledgment We would like to express our profound gratitude to Mr. Vinod Pathari, Lecturer, Department of Computer Science and Engineering, NIT Calicut for his guidance and cooperation. We also acknowledge the advice and help given to us by our friends, especially Deepak Lukose and Haynes, for their valuable suggestions and interest in our work. We would like to extend our gratitude to the entire faculty and staff of the CSED NITC, who stood by us in all pits and falls we had to face during the development phase of this project. Denzil Thomas, Y2092 Elvin P Abraham, Y2060

Abstract Downloading files from various mirror sites is a very common process nowadays. The project attempts to install a mirror for any distribution and also to propose a dynamic centralized load balancing algorithm to balance the requests between the mirrors.

Contents 1. Introduction 1.1 Problem Specification………………………………………………. 1.2 Literature Survey……………………………….…………………… 1.3 Motivation………………………………………………….………..

3 3 3 3

2. Design 4 2.1 Mirroring Techniques ………………………………………………. 4 2.1.1 RSYNC...................................................................................... 4 2.1.2 Push and Pull mirroring..............................................................5 2.2 Introduction to Load Balancing……………………………………... 5 2.3 System model……………………………………………………….. 6 2.4 Proposed Dynamic Centralized load sharing algorithm...................... 7 3. Implementation details 9 3.1 At the server side……………………………………………………. 9 3.2 At the client side…………………………………………………….11 4. Conclusion

12

2

1. Introduction 1.1 Problem Specification The problem at our hand can be detailed as: 1 Study the mirroring techniques currently available by installing a mirror for a well known Linux Distribution like Debian. 2. Study of existing load balancing algorithms and formulating a dynamic, centralized load balancing algorithm for replicated servers. Validate the algorithm by implementing it. .

1.2 Literature Survey In the first phase, we referred many tutorials and support manuals provided by various Linux distributions for setting up of mirrors. To familiarize with the existing tools like rsync, wget, cron etc. referring Red Hat Linux 9.0 Bible and manual pages offered by these tools in the internet were very beneficial. For studying about the existing load balancing techniques and algorithms Zeng Zeng, Bharadwaj Veeravalli[1], L. Anand, D. Ghose, and V. Mani[2] were helpful. For the basic comparative studies, Y. Zhang, K. Hakozaki, H. Kameda, and K. Shimizu, [3]were used. For implementing the dynamic centralized algorithm, W. Richard Stevens [4] and the various man pages of unix [5] were used.

1.3 Motivation The rate of downloading from a website may affect the performance of the server. To reduce the overuse of a particular server, there are a large number of mirrors being setup. For a particular server, to provide an optimum performance to all the clients, load balancing becomes a necessity. Mirroring fosters free dissemination of resources in a non-hierarchical, peer-to-peer manner and can contribute to development of more useful knowledge for society. Having replicated servers by mirroring, it would be more efficient when supplemented by proper load balancing techniques. As the manner in which a heterogeneous set of replicated servers/ mirrors react, depend on certain factors that vary with time, we need algorithms that balance the load between them, dynamically.

3

2 Design 2.1 Mirroring Techniques For mirroring a distribution, we first analyze the requirements and once the requirements are met, we start setting up the mirror. A web server (apache) should be installed, configured and added to the services list. Once server is up, we re-configure tools like rsync, wget, cron, ssh etc. which are used during mirroring. These mirrors, get the updates from the original server via mechanisms like rsync, wget etc. which are stimulated by tools like crone job daemon.

2.1.1 RSYNC Rsync is a computer program which synchronizes files and directories from one location to another while minimizing data transfer using delta encoding when appropriate. An important feature not found in most similar programs/protocols is that the mirroring takes place with only one transmission in each direction. Rsync is a very useful alternative to rcp. This tool can copy files and directories between a local host and a remote host (source and destination can also be local). The main advantage is that rsync can use SSH as a secure channel, send/receive only the bytes inside files that changed since the last replication, and remove files on the destination host if those files were deleted on the source host to keep both hosts in sync. Mirroring make use the rsync remote-update protocol to greatly speed up file transfers when the destination file is being updated by transferring just the differences between two sets of files using an efficient checksum-search algorithm. The rsync algorithm works in the manner depicted in Fig.1.The client splits old data into blocks of size b, computes a hash value for each block and sends it to the server. Server stores the received hashes in a dictionary. Server checks for match between the new hash values, of any block of size b, with any of the values in the dictionary. Server then transmits the new data to client, but replaces any b-byte window that hashes to value in dictionary by reference.

4

Rsync can be done in two ways, directly connecting to a remote rsync daemon, typically using TCP port 873 or using a remote shell as the transport, then spawning a single-use "daemon" server. The files can be transferred in "archive" mode, which ensures that symbolic links, attributes, permissions, etc. are preserved in the transfer. It also includes exclude and exclude-from options including a CVS exclude mode and can use any transparent remote shell, including ssh or rsh, though it is configured to use ssh by default. It also supports anonymous or authenticated rsync daemons which is ideal for mirroring. The mirror is updated on a regular basis using a utility like cron, which wakes up every minute, examining all stored crontabs and checking each command to see if it should be run in the current minute. Generally, the steps for mirroring are: 1. Develop a script to run the mirroring application refined for our requirement: the set of architectures & packages we intend to mirror. 2. Test the script and if possible, we add some output redirections so that diagnostic messages are logged to a file. 3. Install the latest versions of the tools used, and configure them. 4. Use crontab to add the script to the set of scheduled tasks, to run it periodically. Mirroring using rsync is totally different from RAID, which is just a backup system protecting our data from disk failures. However, it provides no protection against file corruption, files destroyed by a virus or a hacker etc. In RAID, data should always be backed up regardless of what media it is stored on or how redundant that media may be. 2.1.2 Push and Pull Mirroring: Mirroring servers implement two types of mirroring: Push and Pull. Push mirroring is a form of mirroring using rsync that minimizes the time it takes for changes to the main archive to reach mirrors. The server mirror uses a triggering mechanism to inform the client mirror it needs to be updated. Push mirroring takes a little more effort to set up since the maintainers of the upstream and downstream mirror must exchange information. The benefit is that the upstream mirror initiates the mirror process immediately after its archive has been updated. This allows changes to the archive to propagate extremely quickly. In Pull mirroring, the client has to pull the information from the server without any such ‘push’ from the server.

2.2 Introduction to Load Balancing A distributed computer system consists of many heterogeneous processors with different processing capabilities, connected by two-way communication links and having their own resources or buffers. Load balancing should be used to distribute the job loads and improve performance measures such as the mean response time (MRT)-the time difference between the time instant at which a job arrives to the system and the time instant at which the job gets processed.

5

Before designing any load balancing algorithm, there are several influencing factors which should be considered, the underlying network topology, communication network bandwidth, job arrival rates at each processor in the system. Load balancing algorithms can be centralized or distributed. In centralized load balancing algorithm, the pool of processors is divided into one manager and many workers. The manager processor maintains a list of tasks to be assigned. When a worker processor has nothing to do, it requests a task from the manager. The manager replies with a task. The worker completes the task, returns the solution and requests for another task. A potential problem with this style is that the manager processor can become a bottle-neck. In distributed load scheduling algorithm, each processor maintains its own list of available tasks. A mechanism is needed to spread the tasks among the other processors. Some algorithms rely on a “push” strategy in which processors with too many available tasks send some of their tasks to neighboring processors. Other algorithms rely on a “pull” strategy: processors with no task do ask neighboring processors for work. A challenge is determining the termination condition: the uncompleted task is spread among the processors and it is difficult for any process to know when all of them have been completed. Load balancing algorithms can be classified as either dynamic or static. A dynamic algorithm makes its decision according to the state of the system, where the state could refer to certain type of information such as the number of jobs waiting in the queue, the current job arrival rate, the job processing rate, etc., at each processor. On the other hand, static algorithm performs by a predetermined policy, without considering the state of the system. However, dynamic load balancing algorithms improves load distribution at the expense of additional communication and computation overheads. To minimize the communication overheads, some methods like obtaining optimal solutions, randomization and static algorithms namely Load Balancing via Virtual Routing were proposed to estimate the state information of the nodes in the system. Dynamic algorithms can be classified into three policies: Queue Adjustment Policy (QAP), Rate Adjustment Policy (RAP) and Combination of Queue and Rate Adjustment Policy (QRAP).We discuss Estimated Load Information Scheduling algorithm(ELISA) based on QAP and another RAP algorithm, Rate based Load balancing via Virtual Routing (RLBVR) based on Load Balancing via Virtual Routing (LBVR).

2.3

System model

A generic server client model that consists of N heterogeneous clients and a single server. S denotes the server and N denotes the set of clients i.e. n=|N| and for each client i and server s we define 2 ordered pairs (s,i) and (i,s) which are called links and we denote L as the set of links. We assume that jobs arrive at node i according to a Poisson distribution with intensity function, λ i (t).

6

The service time of a job is a random variable that follows an exponential distribution with mean S.T (i) where S.T (i) denotes the average job service rate of client i. We denote B(t) as the rate at which jobs are processed at client i at time t. Once a job starts to undergo processing in a client, it is allowed to complete processing with out interruption and cannot be transferred to another node in the meanwhile. In this model we assume that there is a delay between transferring a job from server to client and start of the processing and denote X (i) as the delay time from server to client. Further, we assume that each link (i, j) can transfer the load at its own transmission capability. We denote C as the set of transmission capacities of all the links and cij as the transmission capacity of a link (i, j). In dynamic load balancing algorithms, the nodes in the system exchange their status information with the centralized server at periodic interval of time Ts, which is called the status exchange interval. The status information consists of the queue length at the instance of information exchange and an estimate of the job arrival rate. The instant at which this information exchange takes place is called a status exchange epoch. Each node estimates the job arrival rate by considering the number of arrivals in a certain fixed interval of time (called a window). The size of this window depends on how rapidly the arrival rate varies with time. Here, we consider the window to be an integer (w) multiple of Ts, i.e., window size = wTs. Also, Ts = m × Te time units from the last status exchange instant and λni is denoted as the estimated arrival rate of node i in the nth Ts. This estimate is made at starting of the interval Ts at time t = Tn−1, Tn.. For load balancing algorithms, the model for a system comprises of a server with an infinite buffer to hold the jobs and a scheduler and a fixed number of client processes. The scheduler is to schedule the jobs arriving at the server such that the mean response time of the jobs is a minimum. In the absence of a scheduler in a node, the job flow takes the following sequence of actions: a job enters the buffer, waits in the queue for processing, leaves the queue and gets processed in the processor and then leaves the node (system). However, when a scheduler is present, depending on where a scheduler resides in a node to exercise its control on the jobs, we classify the dynamic load balancing algorithms into three policies

Queue Adjustment Policy (QAP) The scheduler is placed immediately after the queue. Algorithms of this policy try to balance the jobs in the queues of the nodes. When a job arrives at node i, if the queue is empty, the job will be sent to processor directly; otherwise, the job will have to wait in the queue. The scheduler of node i periodically detects the queue lengths of other nodes that node i concerns. When an imbalance exists (some queues are too long and some are too short), the scheduler will decide how many jobs in the queue should be transferred and where each of the jobs should be sent to. By queue adjustment, the algorithms could balance the load in the system.

7

Rate Adjustment Policy (RAP) The scheduler is immediately placed before the queue. When a job arrives at node i, the scheduler decides where the job should be sent, whether it is to be sent to the queue of node i or to other nodes under consideration. Once the job has entered the queue, it will be processed by processor and will not be transferred to other nodes. Using this policy, the static algorithms, can attempt to control the job processing rate on each node in the system and eventually obtain an optimal solution for load balancing. Because of the high computation overheads in this policy, this dynamic algorithm is not commonly used.

Hybrid Policy: Combination of Queue and Rate Adjustment Policy (QRAP) The scheduler is allowed to adjust the incoming job rate and also allowed to adjust the queue size of node i in some situations. In a dynamic situation, especially when we use RAP, in some cases, the queue size may exceed a predefined threshold and load imbalance may result. Once this happens, QAP starts to work and guarantees that the jobs in the queues are balanced in the entire system. In this policy, we can consider the rate adjustment as a “coarse” adjustment and the queue adjustment as “fine” adjustment.

Figure 2 (a) Node model of queue adjustment policy;(b) Node model of rate adjustment policy; (c) Node model of combination of queue and rate adjustment policy.

2.4

Proposed Dynamic Centralized load sharing algorithm

Primarily, the server starts running the algorithm and a fixed number of heterogeneous clients /nodes, connect to the server. As each of the client or node is heterogeneous, it will take its own different time to finish the job assigned to it eg: first client in the range a-b, second client in the range b-c and so on. The different times taken by the clients can be attributed as the different capacities of each processor, the delay in the communication links due to the large number of hops or geographical proximities etc Once the main server starts receiving requests, the server first sends or redirects all the requests on a round robin basis to the client mirrors for a specific time interval or the status exchange interval. At each status exchange epoch, the server receives status information: the time left to finish the jobs in each client and decides the policy to be adopted in the next status exchange interval. Now the main server has two options: 8

(a) Continue with the round robin method (b) redesign to a weighted round robin based on the ratios of the time left for each client and thereafter the jobs are distributed in this manner, till the next status exchange epoch, when the status information is again received by the server and server decides the policy to be adopted. It decides the policy based on the following condition: If the individual times left for each processor / client is greater than the average time left to process, considering all processors, by more than a threshold ‘θ’, we switch to weighted round robin or else stick with the basic round robin at the status exchange epoch. The status exchange interval should be based on the number of job requests per unit time. Both the threshold ‘θ’ and the status exchange interval should be modeled mathematically or derived through empirical tests. Each job request(HTTP request) comes to the parent process and based on the algorithm, the parent redirects it to that client, so as to balance the load among all the clients. When a redirected job is received at the client side, the client processor services the request as per the job specification and once the client completes the job, the next waiting job will be serviced. Each client process has a queue of all the jobs left for it to service and hence the time left to complete all the uncompleted jobs can be easily calculated.

3. Implementation Details In the first phase, we have setup a mirror of Debian Linux distribution for i386 architecture, available at http://nitc.no-ip.org or http://220.2225.198.20/ .HTTP, FTP and RSYNC and SSH have been enabled after reconfiguring. The mirror is updated daily, cron, from ftp.nz.debian.org . The total size is currently 52.8 GB, which will increase as updates come up. The centralized load balancing server was implemented by setting up a server – client model. The various functions handled by the sever and client are enlisted below:

3.1

At the server side

TCP/IP connections are accepted from all the mirror servers.. The server side uses threads in its implementation. We used the pthread library for this purpose. The main thread of server handles the incoming job requests and redirects each of them to the mirror servers based on the algorithm. The second thread gets the status information from the mirror servers at specific time intervals. This is done by sending a message with request number zero.We decide to shift to weighted round robin if the average of the loads is greater than a threshold value Based on the ratios of the loads at the different mirror servers, a pattern is generated according to which further requests are redirected to appropriate mirror servers in the next time interval. This pattern is recalculated for each time interval. In our implementation, time interval is set as 60 seconds

9

3.1.1

Pseudo code of main thread

Begin for each mirror client in N do { accept connection } While(1) { Get lock Get request no num_req which is initialized to 1 Set the num_req field of variable ne to num_req Set the time field of variable ne to time t Get the socket to which data has to be send from the distribution pattern variable distr Increment num_req by 1 Release the lock } End struct req_details { int num_req; time_t time; };

3.1.2

Pseudo code of second thread

Begin Sleep for a time t=7 Get the lock first Send the load response message to each of the mirror servers in N Save the load field in each load response in the array variable get Take the ceiling of the maximum in get divided by each entry in getand store each value in to_get Sort the values in the array to_get and store sum of the values in to_get as sum Create an array of length sum as a distribution array Evenly distribute each value in to_give across the distribution array If each value in to_get > threshold value, we shift to Weighted round robin. Relase the lock End struct client { int num; int to_give; };

10

3.2

At the client side

There are four mirror servers in our implementation. There are two threads: one waiting for further requests from the server and, the second services the various requests already received at the client side. The client handles two kind of requests. (1) Load request: the client calculates the time needed to service the pending job requests and sends it back as the ‘load’. (2) Job requests: with job number and job arrival time at the server side passed to the client. It adds the request to the FIFO queue, array_list, from where the second thread gets the next job to be processed. It then prints the job arrival times and time at which it is serviced at the client side. The structures are passed between the server and client, by type casting it to a character array and sending and receiving them using the send() and recv() functions. 3.2.1 Pseudo code of main thread Begin Wait to receive any messages from server. Received message If Load message Calculate the load, calculating the remaining time required to service the pending requests. Send it to the server as load_response. else its job request Receive the job parameters into request_list Enqueue it to the buffer of jobs, that the client should be servicing. End struct request_list { int num; // request num differentiates between load and request time_t arrive_time; time_t finish_time; int sleep_time; struct request_list * next; }; struct load_response { int load; //from now to end of list int x; // from iter to now. };

3.2.2 Pseudo code of second thread Begin Till the queue is empty Get the next request to be serviced from the queue at the client side Sleep for a specified time, considered to be the job processing time. After waking, print that the job has been processed, the arrival time, the departure time and increment the no of jobs serviced in this time interval. Continue End 11

4 Conclusion A mirror of Debian Linux distribution for i386 architecture was set up. A system model was developed for server client model in the centralized architecture and the proposed dynamic centralized load balancing algorithm was implemented successfully.

12

References [1] Zeng Zeng, Bharadwaj Veeravalli, "Rate-Based and Queue-Based Dynamic Load Balancing Algorithms in Distributed Systems," Icpads, 10th International Conference on Parallel and Distributed Systems (ICPADS'04), p.349, 2004. [2] L. Anand, D. Ghose, and V. Mani, “ELISA: An Estimated Load Information scheduling Algorithm for Distributed Computing System,” Computers and Mathematics with Applications, 37, p. 57-85, 1999. [3] Y. Zhang, K. Hakozaki, H. Kameda, and K. Shimizu, “A Performance Comparison of Adaptive and Static Load Balancing in Heterogeneous Distributed Systems,” Proc. IEEE 28th Annual Simulation Symposium., p. 332-340, Phoenix, Ariz., April 1995. [4] Sayal, Breibart et al – 98,IEEE/ACM Transactions on networking,Vol 10,NO.4,Aug 2002,Dynamic Parallel Acess to Replicated Content [5] Hiroshi Yokota, Shigetomo Kimura, Yoshihiko Ebihara, “A Proposal of DNS based adaptive load balancing method for Mirror server systems and its implementation”, Pg 208,18th International Conference on Advanced Information Networking and Application, Vol. 2,2004 [6] W.Richard Stevens, Unix Network Programming, Pearson education Asia, 2002 [7] The UNIX man pages. [8] Network Programming, Beej's Guide to Network Programming http://beej.us/guide/ [9] Rsync website http://www.rsync.samba.org [10] The Apache software foundation, http://www.apache.org [11] The Official Debian website http://www.debian.org

13