Final Thesis.docx

BALANCING OF LOAD FOR DISTRIBUTED FILE SYSTEMS IN CLOUDS USING LOAD REBALANCING

Thesis submitted in partial fulfillment of the Requirements for the Degree of Master of Engineering in

Computer Science & Engineering Submitted by Varsha B. Jadhav

DEPARTMENT OF COMPUTER ENGINEERING S.S.V.P.S.’s B.S. DEORE COLLEGE OF ENGINEERING, DHULE 2015-2016

BALANCING OF LOAD FOR DISTRIBUTED FILE SYSTEMS IN CLOUDS USING LOAD REBALANCING Thesis submitted in partial fulfillment of the Requirements for the Degree of Master of Engineering in

Computer Science & Engineering Submitted by Varsha B. Jadhav Guided by Prof. B. R. Mandre

DEPARTMENT OF COMPUTER ENGINEERING S.S.V.P.S.’s B.S. DEORE COLLEGE OF ENGINEERING, DHULE 2015-2016

S.S.V.P.S.’s B.S. DEORE COLLEGE OF ENGINEERING, DHULE DEPARTMENT OF COMPUTER ENGINEERING

CERTIFICATE This is to certify that the Thesis entitled “Balancing of load for Distributed File Systems in Clouds using Load rebalancing” has been carried out by Varsha B. Jadhav under my guidance in partial fulfillment of the degree of Master of Engineering in Computer Science & Engineering of North Maharashtra University, Jalgaon. The work submitted by the candidate has been carried under my supervision and to the best of my knowledge and belief this work has not been submitted elsewhere for the award of any other degree.

Date: Place: Dhule

Examiner

Guide Prof. B. R. Mandre

Head

Principal

Dr. Hitendra D. Patil

Dr. Hitendra D. Patil

DECLARATION This is to certify that Thesis entitled “Balancing of load for Distributed File Systems in Clouds using Load rebalancing” which is submitted by me in partial fulfillment of the requirement for the award of degree Master of Engineering in Computer Science and Engineering to North Maharashtra University, Jalgaon (M.S.) comprises only my original work and due acknowledgement has been made in the text to all other material used.

Date:

Varsha B. Jadhav

ACKNOWLEDGEMENT This Thesis has taken its current shape after a lot of hard work and perseverance-not only just by me. I would like to express our sincere gratitude for the assistance and support of a number of people who are helping to make this thesis a success. I am greatly indebted to Prof. B. R. Mandre, my internal guide for his guidance and enlightening comments throughout the project work. It has been an altogether different experience to work with him and I would like to thank for his helpful suggestion and numerous discussions. I am also gladly taking this opportunity to thank Prof. B. S. Chordia (PG Coordinator, Computer Engineering) for providing facilities during progress of the project work. Special thanks to my Family and Friends. I am also thankful to all those who helped us directly or indirectly to develop this report and complete it successfully. Then I would like to thank all the Staff for their encouragement. They had always been very prompt at extending in their helping hand & sharing valuable technical knows. The smooth completion of this project would not have been possible without their guidance.

Thank you.

Varsha B. Jadhav

ABBREVIATIONS Abbreviation

Details

HDFS

Hadoop Distributed File System

GFS

Google File System

LB

Load Balancing

VS

Virtual Server

VSA

Virtual Server Assignment

LBI

Load Balancing Information

DHT

Distributed Hash Table

RR

Round Robin

RB

ReBalancing

P2P

Peer-to-Peer

CAN

Content Addressable Network

Table of Contents ABSTRACT ........................................................................................................................ 1 1. INTRODUCTION .......................................................................................................... 2 1.1 Cloud Computing ......................................................................................................2 1.1.1 Cloud Components .............................................................................................3 1.1.2 Type of Clouds ...................................................................................................4 1.1.3 Virtualization ......................................................................................................5 1.1.4 Services provided by Cloud computing..............................................................6 1.2 Load Balancing .........................................................................................................9 1.2.1 Goals of Load balancing ...................................................................................10 1.2.2 Types of Load balancing algorithms ................................................................10 1.2.3 Load Balancing Matrices ..................................................................................11 1.3 Necessity .................................................................................................................13 1.4 Motivation ...............................................................................................................13 1.5 Problem Statements .................................................................................................13 1.6 Objectives ................................................................................................................13 1.7 Organization of Report ............................................................................................14 1.8 Summary .................................................................................................................14 2. LITERATURE SURVEY ............................................................................................. 15 2.1 Different Load Balancing Algorithms.....................................................................15 2.2 Summary .................................................................................................................29 3. SYSTEM DEVELOPMENT ........................................................................................ 30 3.1 Methodology ...........................................................................................................30 3.1.1 Existing Load Balancing System ......................................................................30 3.1.2 Load Rebalancing Problem ..............................................................................31 3.1.3 Current work using Load Rebalancing .............................................................33 3.2 Implementation........................................................................................................34 3.2.1 Architecture: .....................................................................................................34 3.2.2 Pros of Running Simulation .............................................................................38 3.3 Cloud Simulation Tools ..........................................................................................39 3.3.1 CloudSim Architecture .....................................................................................39 3.3.2 Features of CloudSim .......................................................................................41

3.3.3 WorkflowSim ...................................................................................................42 3.4 Simulation ...............................................................................................................42 3.4.1 Simulation setup ...............................................................................................43 3.5 Graphical User Interface Snapshots ........................................................................43 3.5.1 Home Screen.....................................................................................................43 3.5.2 Select File and Algorithm .................................................................................45 3.5.3 Output window .................................................................................................46 3.6 Used Technology.....................................................................................................48 3.7 Summary .................................................................................................................48 4. PERFORMANCE ANALYSIS .................................................................................... 49 4.1 Performance Analysis of Existing Work.................................................................49 4.1.1 Simulation results For Existing work ...............................................................49 4.2 Performance Analysis of Load Rebalancing Algorithm .........................................50 4.2.1 Simulation Results for Load Rebalancing Algorithm ......................................50 4.3 Experimental Comparision......................................................................................51 4.3.1 Comparison of Round Robin and Load Rebalancing Algorithm .....................51 4.4 Justification Difference ...........................................................................................53 4.5 Summary .................................................................................................................53 5. CONCLUSION ............................................................................................................. 54 5.1 Conclusion...............................................................................................................54 5.2 Future Scope............................................................................................................54 5.3 Applications ............................................................................................................54 BIBLIOGRAPHY ............................................................................................................. 55 PUBLICATION ................................................................................................................ 59

Figure Index 1.1 A Cloud use in Network diagram to depict the Internet ............................................... 2 1.2 Clod Computing Components....................................................................................... 3 1.3 Types of Cloud ............................................................................................................. 4 1.4 Full Virtualization ....................................................................................................... 5 1.5 Para Virtualization ...................................................................................................... 6 1.6 Software as a Service .................................................................................................. 7 1.7 Platform as a Service (PaaS) ....................................................................................... 8 1.8 Hardware as a Service (HaaS) ..................................................................................... 9 1.9 Cloud models ............................................................................................................... 9 1.10 Load Balancing ......................................................................................................... 10 3.1 Architecture................................................................................................................ 34 3.2 File Allocation ........................................................................................................... 35 3.3 Distributed Hash Table .............................................................................................. 36 3.4 Under loaded and Overloaded node ........................................................................... 37 3.5 Load Balance State .................................................................................................... 37 3.6 Flowchart for Load Rebalancing ............................................................................... 38 3.7 CloudSim Architecture .............................................................................................. 41 3.8 Home Screen .............................................................................................................. 44 3.9 Without selecting file ................................................................................................. 45 3.10 Selecting File and Algorithm .................................................................................... 46 3.11 First output after executing Rebalancing Algo. ........................................................ 46 3.12 Second output after executing Rebalancing Algo. .................................................... 47 3.13 Graph Time (in ms) vs. processing seq. of chunk..................................................... 47 4.1 Comparision of load distribution using RR and RB ................................................. 52 4.2 Comparison of Execution time for Diff. size of load................................................ 53

Table Index 1. Metrics in existing LB techniques in cloud computing ................................................ 11 2. Used Symbols ............................................................................................................... 32 3. Files and its respective chunks ...................................................................................... 32 4. File Chunks allocated to Nodes .................................................................................... 32 5. Files and its respective chunks ...................................................................................... 33 6. Chunks allocated to Nodes in Rebalancing system ...................................................... 33 7. Parameter values ........................................................................................................... 43 8. Load distribution using Round Robin Algo. ................................................................. 49 9. Execution time (in ms) for different load size .............................................................. 50 10. Load distribution using Load Rebalancing Algo. ....................................................... 50 11. Execution time (in ms) for different load size ............................................................ 51 12. Comparison of load distribution among nodes ........................................................... 51 13. Comparison of Exe. time (in ms) for diff. size of load ............................................... 52

ABSTRACT One of the most significant and important concepts in cloud computing based application is Distributed file systems. The storage functions and computation of the nodes are performed simultaneous or parallel in the distributed file systems; the files are partitioned into a “number of chunks” which are allocated in “different nodes” so that the tasks can be served “simultaneous” over the different nodes. However, in a cloud computing environment, failure is the norm, and nodes may be replaced,, upgraded, and added in the system. The dynamic creation, deletion, appending of files of the system can occur, this causes load imbalance in the distributed file system; that is, the files are split into chunks, and chunks are not distributed uniformly among the nodes. If the system is centralized and the distribution of files is large then there is lot of workload on the central node, which causes single point of failure and may thus become performance bottleneck. A fully distributed “Load Rebalancing Algorithm” is offered to deal with the load imbalance problem. The simulation takes place by using “CloudSim” simulator. The simulation results indicate that load rebalancing algorithm is comparable with the existing load balancing algorithm and considerably outperforms in terms of load distribution and execution time of an algorithm.

Key Words – Load balance, Distributed file system, clouds

1

CHAPTER – 1 INTRODUCTION Balancing of Load for Distributed File Systems in Clouds using Load Rebalancing, include some basic terms like Cloud Computing, Load Balancing, and Distributed File System.

1.1

CLOUD COMPUTING

Cloud computing is an on demand service in which shared information, software, resources and other devices are provided at specific time according to the clients requirement. This term is generally used in case of Internet. The whole Internet can be viewed as a cloud. Operational and capital and costs can be cut using cloud computing [9, 13].

Figure 1.1: A Cloud use in Network diagram to depict the Internet [13]

In case of Cloud computing services can be used from widespread and diverse resources, rather than remote servers or local machines. There is no any standard definition of Cloud computing. Generally cloud consists of a bunch of distributed servers known as masters, providing demanded resources and services to different clients in a network with reliability and scalability of datacenter. On-demand services are provided by the distributed computers. Services may be of software resources (e.g. Software as a 2

Service) or physical resources (e.g. Platform as a Service) or hardware or infrastructure (e.g. Hardware as a Service or Infrastructure as a Service). Amazon Elastic Compute Cloud (Amazon EC2) is an example of cloud computing services [30].

1.1.1 Cloud Components A Cloud system consists of clients, distributed servers and datacenter. These are the major components of the cloud. Each element has plays a specific role.

Figure 1.2: Cloud Computing Components [13]

1.1.1.1 Clients To manage information related to the cloud, end users interact with the clients. Clients generally fall into three categories as follows: 

Mobile clients: smart-phones, an iPhone, or Windows Mobile Smartphone.



Thin clients: Thin clients only display the information. They don’t do any computation work. Thin clients don’t have any internal memory. Servers do all the works for them.



Thick clients: These use different browsers like IE (Internet Explorer), Mozilla Firefox or Google Chrome etc. to connect to the Internet cloud.

Now a day, thin clients are more popular because of their low price, easily replaceable and repairable, less noise, low consumption of power, security, etc. 1.1.1.2 Datacenter For hosting different applications a collection if servers are used it is known as Datacenter. An end user connects to the datacenter to subscribe different applications. A

3

datacenter may locate at a large distance from the client. Now-a-days, to install the software that allows multiple instances of virtual server applications, virtualization concept is used. 1.1.1.3 Distributed Servers Distributed servers are present throughout the Internet hosting different applications. But the user will feel that they are using this application from its own machine while using the application from the cloud.

1.1.2 Type of Clouds Clouds can be divided into 4 categories Based on the domain or environment in which clouds are used. They are as follows [14]: 

Public Clouds



Private Clouds



Community Cloud



Hybrid Clouds (combination of both private and public clouds)

Figure 1.3: Types of Cloud [14]

1.1.2.1 Public cloud The Public Cloud allows services and systems to be easily accessible to the general public. Security point view public cloud may be less secure because of its openness, e.g., e-mail. 1.1.2.2 Private cloud The Private Cloud allows services and systems to be accessible within an organization. Because of its private nature, it offers increased security. 4

1.1.2.3 Community cloud The Community Cloud allows systems and services to be accessible by group of organizations. 1.1.2.4 Hybrid cloud The Hybrid Cloud is mixture of private and public cloud. However, by using private cloud the critical activities are performed while using public cloud the non-critical activities are performed.

1.1.3 Virtualization A very useful concept in context of cloud systems is virtualization. Virtualization means “Something which isn’t real”, but gives all the facilities of a real. An end user can use different services of a cloud by using virtualization. The datacenter will provide different services in a partial or full virtualized manner. In case of clouds virtualization are categorized into two types. They are as follows: 

Full virtualization



Para-virtualization

1.1.3.1 Full Virtualization In case of full virtualization a complete installation is done from one machine to another machine. It will result in a virtual machine will have all the software that is present in the actual server.

Figure 1.4: Full Virtualization [13]

The remote datacenter delivers the services in fully virtualized manner. Full virtualization has been successful for following purposes: 

Sharing of a computer system among multiple users



Isolating users from the control program and from each other. 5



Hardware emulation on another machine

1.1.3.2 Para-virtualization In para-virtualization, efficient use of system resources such as processor and memory, multiple operating systems run on single machine is allowed by using hardware e.g. VMware software. All the services are not fully available in para-virtualization.

Figure 1.5: Para Virtualization [13]

Para-virtualization has the following advantages: Disaster recovery: Guest instances are moved to other hardware until the machine is repaired or replaced, in the event of a system failure. Migration: As the hardware can be easily replaced, hence to move or to migrate the different parts of a new machine is easier and faster. Capacity management: It is faster and easier to add more hard drive capacity and processing power in a virtualized environment. [30].

1.1.4 Services provided by Cloud computing Across different servers, Different types of applications provided in the cloud are called service. Services in a cloud are of 3 types [9]: 

Software as a Service (SaaS)



Platform as a Service (PaaS)



Infrastructure as a Service (IaaS) or Hardware as a Service (HaaS)

1.1.4.1 Software as a Service (SaaS) In this service, a complete application is offered to the customer, as a service on demand. A single instance of the service runs on the cloud & multiple end users are serviced. On 6

the customer’s side, there is no need for upfront investment in servers or software licenses, while for the provider, the costs are lowered, since only a single application needs to be hosted & maintained. Today SaaS is offered by companies such as Google, Salesforce, Microsoft, Zoho, etc.

Figure 1.6: Software as a Service [13]

The client will have to pay for to use the software. The software that does a simple task without any need to interact with other systems makes it an ideal candidate for Software as a Service. Customer who isn’t inclined to perform software development but needs high-powered applications can also be benefitted from SaaS [9]. Applications: Video conferencing, Accounting, Web analytics, Customer resource management (CRM), IT service management, Web content management Benefits: 

Costing less money than buying the whole application is the biggest benefit of SaaS.



The service provider generally offers cheaper and more reliable applications as compared to the organization.



Number of other benefits like Familiarity with the Internet, reliability of the Internet, Better marketing, data Security, smaller staff, More bandwidth etc.

Limitations: 

SaaS isn’t of any help when the organization has a very specific computational need that doesn’t match to the SaaS services.

7



It will increase the unnecessary costs because of while making the contract with a new vendor, there may be a problem. Because the old vendors may charge for moving fee.



The availability of cheaper hardware and open source applications are the challenges which are faces by SaaS.

1.1.4.2 Platform as a Service (PaaS) All the resources that are required for building applications and services completely from the Internet, without downloading or installing software are provided by PaaS. PaaS services include software design, development, testing, deployment, and hosting. Other services can be database integration, team collaboration, storage, web service integration, data security and versioning etc.

Figure 1.7: Platform as a Service (PaaS) [13]

Limitations: 

Lack of portability among different providers.



The user’s application data will be lost, if the service provider is out of business.

1.1.4.3 Hardware as a Service (HaaS) HaaS offers the hardware as a service to the organization so that it can put anything into the hardware according to its will. It is also known as Infrastructure as a Service (IaaS). HaaS allows the user to “rent” resources such as Server space, Network equipment, Memory, CPU cycles, Storage space.

8

Figure 1.8: Hardware as a Service (HaaS) [13]

Following Figure 1.7 shows the cloud models with its application [14]. SaaS

PaaS

High scale Internet base applications

Google docs,

Are hosted on the cloud & offered

acrobat.com,

as service to end users

salesforce.com

Here Platforms used to design,

Azure service

develop, build& test applications

Platform,

provided by the cloud infrastructure GoogleApp Engin

HaaS

In this pay per use model, services

Amazon web

Like storage, D/B mgnt & Compute

services, 3Tera

capabilities are offerd on demand

GoGrid

Figure 1.9: Cloud models [14]

1.2 LOAD BALANCING A process of reassigning the total load to the individual nodes of the collective system to improve the response time of the job, to make resource utilization effective and simultaneously removing a condition in which some of the nodes are over loaded while some others are under loaded is known as load balancing. A load balancing algorithm which is dynamic in nature does not consider the previous state or behavior of the system, that is, it depends on the present behavior of the system. The important things to consider while developing such algorithm are : estimation of load, comparison of load, 9

stability of different system, performance of system, interaction between the nodes, nature of work to be transferred, selecting of nodes and many other ones. This load considered can be in terms of CPU load, amount of memory used, delay or Network load [9].

Figure 1.10: Load Balancing

1.2.1 Goals of Load balancing The goals of load balancing are: 

To improve the performance.



In case of the system fails even partially, it has a backup plan.



To maintain the system stability



To accommodate future modification in the system

1.2.2 Types of Load balancing algorithms Who initiated the process depending on that, load balancing algorithms can be of three categories as follows [9]: Sender Initiated: If the load balancing algorithm is initialized by the sender. Receiver Initiated: If the load balancing algorithm is initiated by the receiver. Symmetric: It is the combination of both sender initiated and receiver initiated. Depending on the current state of the system, load balancing algorithms can be divided into 2 categories as follows [9]: Static: Prior knowledge of the system is needed in static load balancing. It doesn’t depend on the current state of the system.

10

Static load balancing is the basic method of load balancing. In this method the performance of the workers is determined at the commencement of execution. The work load is distributed in the start depending upon their performance. The workers compute their assigned work and submit their result to the master. Less communication required between the master and the workers which boosts the performance is one of the advantage of this method. But it cannot adjust the runtime performance of the workers and non homogeneous nature of the application is the drawback of this method. Dynamic: Decisions on load balancing are based on current state of the system. No prior knowledge is needed. So it is better than static approach. In Dynamic load balancing the distribution of workload takes place at run-time. Depending on the recent information collected the master assigns new task to the worker. Since the workload distribution is done during runtime, it may give better performance. But the performance gained is at the cost of overhead associated with communication. So, the overhead associated should be in reasonable limit to achieve better performance.

1.2.3 Load Balancing Matrices Following table shows mostly considered metrics in existing load balancing techniques in cloud computing [10]. Table 1: Metrics in existing LB techniques in cloud computing [10]

LOAD BALANCING METRICS Metric Throughput

Illustration It is used to calculate the no. of tasks whose execution has been completed. It should be high to improve the performance of the system

Overhead

It determines the amount of overhead involved while implementing a load balancing algorithm. It is composed of overhead due to movement

of

tasks,

inter-processor

and

inter-process

communication. This should be minimized so that a load balancing technique can work efficiently.

11

Fault Tolerance

It is the time to migrate resources or the jobs from one node to other. It should be minimized in order to enhance the performance of the system.

Response Time

It is the amount of time taken to respond by a particular load balancing algorithm in a distributed system. This parameter should be minimized.

Resource

It is used to check the utilization of resources. It should be optimized

Utilization

for an efficient load balancing.

Scalability

It is the ability of an algorithm to perform load balancing for a system with any finite number of nodes. This metric should be improved.

Performance

It is used to check the efficiency of the system. This has to be improved at a reasonable cost, e.g., reduce task response time while keeping acceptable delays

One of the most significant and important concepts in cloud computing based application is Distributed file systems. The storage functions and computation of the nodes are performed simultaneous or parallel in the distributed file systems; the files are partitioned into a “number of chunks” which are allocated in “different nodes” so that the tasks can be served “simultaneous” over the different nodes. Now a day the concept of Load balancing in cloud computing systems is really a challenge. It is not always practically feasible or cost efficient to maintain one or more idle services just as to fulfill the required demands therefore always a distributed solution is required. Cloud has a very complex structure and components are presented throughout a wide spread area, load can’t be assigned to appropriate servers and clients individually for efficient load balancing. Here some uncertainty is attached while loads are assigned. The load of a node is typically proportional to the number of file chunks the node possesses, in such Distributed File System. Because the files can be created, deleted, and appended arbitrarily in cloud and nodes can be upgraded, replaced and added in the file system, so the distribution of the file chunks are not as uniform as possible among the

12

nodes. Balancing of load among storage nodes is a critical function in clouds. In a loadbalanced cloud, the resources can be well utilized and provisioned, maximizing the performance [5].

1.3 NECESSITY With the exponential increase in demands of online applications and services, cloud computing has evolved as a boon in modern information technology. Built over the base of grid and distributed computing, cloud computing offers services to cater the dynamic needs of massive user base. However, with the novelty associated with the system, cloud computing is also associated with certain issues like availability, cost, load balancing, security and performance. Very recently in last three years there has been abundant set of research work conducted aiming at mitigating the issues connected to load balancing in cloud computing. Number of load balancing technique causes load rebalancing problem that is load imbalance. By using Load rebalancing algorithm this problem can be avoided and distribution of load uniformly as possible among nodes.

1.4 MOTIVATION Cloud computing is a vast concept. Many of the algorithms for load balancing in cloud computing have been proposed. Some of those algorithms have been overviewed in this thesis. The whole Internet can be considered as a cloud of many connections less and connection oriented services, so balancing of load for distributed file systems in clouds using load rebalancing. In this dissertation, there is the study of load rebalancing problem in distributed file systems specialized for large-scale, dynamic and data-intensive clouds. Such a large-scale cloud has hundreds or thousands of nodes.

1.5 PROBLEM STATEMENTS To allocate the chunks of files as uniformly as possible among the nodes such that no node manages an excessive number of chunks. As failure is the norm, nodes are newly added to sustain the overall system performance, resulting in the heterogeneity of nodes.

1.6 OBJECTIVES 

To study the performance of some of the existing load balancing algorithms.



To design and develop the concept of Balancing of Load for Distributed File Systems in Clouds using Load Rebalancing algorithm. 13



To compare the performance parameters like algorithm execution time.



To study the distribution of load as uniform as possible among nodes.

1.7 ORGANIZATION OF REPORT The Thesis is organized as follows: Chapter-1 gives the introduction of cloud computing, Load balancing, Necessity of load balancing, Motivation, Problem statement and objectives. Chapter-2 gives Literature Survey in order to study about research contribution of various researchers in fields of load balancing. Chapter 3 is System Development that gives description about methodology along with algorithms that we have used in our thesis work. It also gives brief introduction to CloudSim and WorkflowSim which is used for system development. Chapter 4 gives Performance Analysis that is related to experimental analysis of our work along with comparison for performance of various methods. Chapter 5 gives Conclusions, Future scope of load rebalancing technique.

1.8 SUMMARY This chapter gives a brief idea about Cloud Computing and load balancing. It also gives an overall idea about the necessity, motivation, problem statement, objectives and organization of thesis.

14

CHAPTER – 2 LITERATURE SURVEY There are different load balancing algorithms for cloud. Each algorithm design by considering different matrices of load balancing as described in Table 1.

2.1

DIFFERENT LOAD BALANCING ALGORITHMS

Chord: a scalable peer-to-peer lookup service for internet applications Ion Stoica, et al., [32] use the concept of virtual servers as a means of improving load balance. Each physical node can be responsible for more than one virtual server but a virtual server looks like a single peer to the underlying DHT. The main problem of P2P application is that, the efficient location of the node which stored the desired data item. A distributed lookup protocol, Chord, addressed this problem. Merits: Splitting load into virtual servers is that the movement of a virtual server from any node to any other node in the system can be possible. In contrast, if each node has only one virtual server, it can only transfer load to nodes that are its successor and predecessor in the ID space. 

Load balance: Chord acts as a distributed hash function, spreading keys evenly over the nodes; this provides a degree of natural load balance.



Decentralization: Chord is fully distributed: no node is more important than any other. This improves robustness and makes Chord appropriate for looselyorganized peer-to-peer applications.



Scalability: The cost of a Chord lookup grows as the log of the number of nodes, so even very large systems are feasible. No parameter tuning is required to achieve this scaling.



Availability: Chord automatically adjusts its internal tables to reflect newly joined nodes as well as node failures, ensuring that, barring major failures in the underlying network, the node responsible for a key can always be found. This is true even if the system is in a continuous state of change.

15



Flexible naming: Chord places no constraint on the structure of the keys it looks up the Chord key-space is flat. This gives applications a large amount of flexibility in how they map their own names to Chord keys.

Demerits: 

Even though splitting load into virtual servers will increase the path length on the overlay, the flexibility to move load from any node to any other node is crucial to any load-balancing scheme over DHTs.



These schemes assume that nodes are homogeneous; objects have the same size, and object ID’s are uniformly distributed.

Simple load balancing for distributed hash tables John Byers et al., [6] has done the use of the power of two choices to achieve better load balance. The previous schemes based on consistent hashing, it requires both substantial storage overhead and considerable implementation complexity to achieve desired load balancing goals. These goals can be achieved more simply and more cost-effectively which is described in this paper. First, they have done the use of “power of two choices” paradigm that is two new protocols are discussed in this paper. To support other load balancing strategies including load-stealing or load-shedding, they consider how associating a key with a small constant number of hash values can naturally be extended, and also providing natural fault-tolerance mechanisms. Merits: 

Goals can be achieved more simply and more cost-effectively.

Demerits: 

Analysis and simulation of this scheme was not considered for heterogeneous node capacities and object sizes, and in any case is not prepared to handle a dynamic system.

Load balancing in structured p2p systems A. Rao, et al., [1] based on the concept of virtual servers. The many-to-many framework is considered with the load imbalance in a DHT. In this type of framework some dedicated nodes namely, the directories are considered. The light and heavy nodes register their loads with this directory node. The directories compute matches between

16

light nodes and heavy nodes and then respectively, request the light and heavy nodes to receive and to transfer designated virtual servers. Simple efficient load balancing algorithms for peer-to-peer systems D. Karger, et al. [11] gives two new load balancing protocols whose provable performance guarantees are within a constant factor of optimal. These protocols refine the consistent hashing data structure that underlies the Chord P2P network. Both preserve Chord’s logarithmic query time and near-optimal data migration cost. First protocol balances the distribution of the key address space to nodes, which yields a load-balanced system when the DHT maps items “randomly” into the address space. This yields the first P2P scheme simultaneously achieving O(logn) degree, O(logn) look-up cost, and constant-factor load balance. Second protocol aims to directly balance the distribution of items among the nodes. This is useful when the distribution of items in the address space cannot be randomized—for example, if wish to support range searches on “ordered” keys, then gives a simple protocol that balances load by moving nodes to arbitrary locations “where they are needed.” As an application, there is use the last protocol to give an optimal implementation of a distributed data structure for range searches on ordered data. Range search data structure does not easily generalize to more than one order. For example when storing music files, one might want to index them by both artist and song title, allowing lookups according to two orderings. Merits: 

Preserve Chord’s logarithmic query time and near-optimal data migration cost.



To give an optimal implementation of a distributed data structure for range searches on ordered data.

Demerits: 

In File System Load balancing method even distribution of item should be limited.



Each node should be limited number of hash function and address should be balanced or limited number of address space. If address fails and node will fail this is major drawback in the System.

17

Mercury: Supporting Scalable Multi-Attribute Range Queries A. Bharambe et al. [27] has presents the design of Mercury, a scalable protocol for supporting multi-attribute range-based searches. Mercury differs from previous range based query systems in that it supports performs explicit load balancing as well as multiple attributes. To guarantee efficient routing and load balancing, Mercury uses novel light-weight sampling mechanisms for uniformly sampling random nodes in a highly dynamic overlay network. Mercury is able to achieve its goals of logarithmic hop routing and near uniform load balancing. Also, Mercury can be used to solve a key problem for an important class of distributed applications: distributed state maintenance for distributed games. They show that the Mercury-based solution is easy to use, and that it reduces the game's messaging overhead significantly. In this model, each query is a conjunction of ranges in one or more attributes. The attributes not present in the query are assumed to be wildcards. Range queries significantly enhance search flexibility in a number of scenarios. In addition to being useful for answering user queries, they find that range-based queries can also be useful in the construction of distributed applications. There are two main components of Mercury's design. First, Mercury handles multi-attribute queries by creating a routing hub for each attribute in the application schema. Each routing hub is a logical collection of nodes in the system. Queries are passed to exactly one of the hubs corresponding to the attributes that are queried, while a new data item is sent to all hubs for which it has an associated attribute. This ensures that queries retrieve all relevant data items present in the system. Second, for supporting range queries, Mercury organizes each routing hub into a circular overlay of nodes and places data contiguously on this ring, i.e., each node is responsible for a range of values for the particular attribute. While the notion of a circular overlay is similar in spirit to some existing DHT designs, due to the choice to support range queries by placing data contiguously, in this no use of randomizing hash functions for placing data. This requirement introduces a fundamental challenge: because Mercury cannot use hash functions, data partitioning among nodes can become non-uniform, thus, requiring an explicit load-balancing mechanism. However, the load-balancing mechanism is fundamentally incompatible with many of the techniques that DHTs use to guarantee routing efficiency.

18

The solution to the above challenges some of the interesting algorithms in Mercury include: 1. Message routing algorithm - supports range based lookups within each routing hub. 2. Low-overhead random sampling algorithm - allows each node to create an estimate of system-wide metrics such as load distribution. 3. Load-balancing algorithm - ensures that routing load is uniformly distributed across all participating nodes. 4. An algorithm for reducing query flooding - by estimating how selective each of the predicates in a query is based on past database insertions. Merits: 

To support for multiple attributes and explicit load balancing.



To support random sampling of nodes within the system. Random sampling enables a number of lightweight.



Approaches to perform load-balancing, node count estimation and query selectivity estimation.



Mercury scales well, has low lookup latency and provides good load balancing properties.



Mercury is well suited for distributed state maintenance in distributed games.

Demerits: 

Mercury cannot use hash functions, data partitioning among nodes can become non-uniform, thus, requiring an explicit load-balancing mechanism.

Online Balancing of Range-Partitioned Data with Applications to peer-to-peer Systems P. Ganesan, et al. [20] discussed the online load-balancing problem for parallel databases. Online load-balancing solutions, which dynamically move data across nodes and avoid skew at all times. A well-known concern in range partitioning is skew, where only a few partitions (disks/nodes) are involved in the execution of most queries. Skew can be classified into two types: (a) Data skew, where data may be unequally distributed across the partitions, and (b) Execution skew, where data accesses may not be uniform across the partitions. Algorithms for eliminating data skew to achieve storage balance, although to handle 19

execution skew as well algorithms can be easily generalized. The load-balancing algorithms guarantee that imbalance ratio is always bounded by a small constant c. The bound c is, in fact, a tunable parameter that can be set to values as low as 4.24. Each insert or delete of a tuple is guaranteed to require just an (amortized) constant number of tuple movements, even against an adversarial sequence of inserts and deletes. Thus, this algorithms offer storage balance at all times, against all data distributions, while ensuring that the overhead is asymptotically optimal, and often much less than that of periodic repartitioning. Online load balancing algorithms are motivated by a new application domain for range partitioning: peer-to-peer (P2P) systems. P2P systems store a relation over a large and dynamic set of nodes, and support queries over this relation. Merits Online load-balancing gives following major advantages over periodic manual repartitioning: 

A consistently efficient 24/7 operation by eliminating performance degradation between manual repartitioning.



A simplified control panel by eliminating partition configuration from the administrator’s list of chores.



A smaller cost especially in systems with a high degree of parallelism, where even a few inserts/deletes may cause a large skew.



The Threshold Algorithm achieves the desired imbalance ratio for a range of imbalance ratio values on various workloads.



The amortized cost of load balancing is very small, decreases with increasing imbalance ratio, and is much lower than the cost of periodic reorganization.



The P2P variant achieves the desired imbalance ratio at a small cost, and scales gracefully with increasing dynamism in the network.



The Randomized variant provides good imbalance ratios even with a small number of samples.

Efficient, Proximity-Aware Load Balancing for DHT-Based P2P Systems Y. Zhu, et al. [4] uses proximity information to guide virtual server reassignments such that virtual servers are reassigned between physically close nodes, thereby reducing the load movement cost and allowing efficient load balancing. Second, this approach 20

performs virtual server reassignments along the k-ary tree in a bottom-up fashion and it can bind virtual server reassignments in O (log N) time. In the Many-to-Many scheme, randomly rehashing heavy nodes and light nodes into the directory nodes may not be able to bind the virtual server reassignment time. The Load balancing scheme is not restricted to a particular type of resources. This load balancing scheme consists of four phases: 1. Load balancing information (LBI) aggregation: Aggregate load and capacity information in the whole system. 2. Node classification: Classify nodes into overloaded (heavy) nodes, under loaded (light) nodes, or neutral nodes according to their loads and capacities. 3. Virtual server assignment (VSA): Determine virtual server assignment from heavy nodes to light nodes in order to have heavy nodes become light. The VSA process is a critical phase because in this phase the proximity information is used to make this load balancing scheme proximity-aware. 4. Virtual server transferring (VST): Transfer assigned virtual servers from heavy nodes to light nodes. VSA and VST to partly overlap for fast load balancing. Load balancing in dynamic structured p2p systems S.Surana, et al. [28] discussed on the many-to-many framework essentially reduces the load balancing problem to a centralized algorithmic problem. In many to many frameworks, light and heavy nodes register their loads with some dedicated nodes called directories. The directories compute matches between heavy and light nodes and then request the heavy and light nodes to transfer and to receive designated virtual servers respectively. As the entire system heavily depends on the directory nodes, the directory nodes may thus become the performance bottleneck and single point of failure. A comparative study into distributed load balancing algorithms for cloud computing M. Randles, et al. [8] discussed on Distributed Load Balancing Algorithms are Honeybee Foraging Behavior, Biased Random Sampling, and Active Clustering. Honeybee Foraging Algorithm: This algorithm is derived from the behavior of honey bees for finding and reaping food. There is a class of bees called the forager bees which forage for food sources, upon 21

finding one, they come back to the beehive to advertise this using a dance called waggle dance. The display of this dance, gives the idea of the quality or quantity of food and also its distance from the beehive. Scout bees then follow the foragers to the location of food and then began to reap it. They then return to the beehive and do a waggle dance, which gives an idea of how much food is left and hence results in more exploitation or abandonment of the food source. In case of load balancing, as the web servers demand increases or decreases, the services are assigned dynamically to regulate the changing demands of the user. The servers are grouped under virtual servers (VS), each VS having its own virtual service queues. Each server processing a request from its queue calculates a profit or reward, which is analogous to the quality that the bees show in their waggle dance. One measure of this reward can be the amount of time that the CPU spends on the processing of a request. The dance floor in case of honey bees is analogous to an advert board here. This board is also used to advertise the profit of the entire colony. Each of the servers takes the role of either a forager or a scout. The server after processing a request can post their profit on the advert boards with a probability of pr. A server can choose a queue of VS by a probability of px showing explore behavior, or it can check for advertisements and serve it, thus showing scout behavior. A server serving a request, calculates its profit and compare it with the colony profit and then sets its px. If this profit was high, then the server stays at the current virtual server; posting an advertisement for it by probability pr. If it was low, then the server returns to the forage or scout behavior. Honeybee Foraging Behavior investigated a decentralized honeybee-based load balancing technique that is a nature-inspired algorithm for self-organization. It achieves global load balancing through local server actions. Performance of the system is enhanced with increased system diversity but throughput is not increased with an increase in system size. It is best suited for the conditions where the diverse population of service types is required. Merits: 

Performance of the system is enhanced with increased system diversity.

22

Demerits: 

Throughput is not increased with an increase in system size.

Biased Random Sampling: Here a virtual graph is constructed, with the connectivity of each node or server representing the load on the server. Each server is symbolized as a node in the graph, with each in-degree directed to the free resources of the server. Regarding job execution and completion, 

Whenever a node does or executes a job, it deletes an incoming edge, which indicates reduction in the availability of free resource.



After completion of a job, the node creates an incoming edge, which indicates an increase in the availability of free resource.

The addition and deletion of processes is done by the process of random sampling. The walk starts at any one node and at every step a neighbor is chosen randomly. The last node is selected for allocation for load. Alternatively, another method can be used for selection of a node for load allocation, that being selecting a node based on certain criteria like computing efficiency, etc. Yet another method can be selecting that node for load allocation which is underloaded i.e. having highest in degree. If b is the walk length, then, as b increases, the efficiency of load allocation increases. We define a threshold value of b, which is generally equal to log n experimentally. A node upon receiving a job, will execute it only if its current walk length is equal to or greater than the threshold value. Else, the walk length of the job under consideration is incremented and another neighbor node is selected randomly. When, a job is executed by a node then in the graph, an incoming edge of that node is deleted. After completion of the job, an edge is created from the node initiating the load allocation process to the node which was executing the job. Finally they get a directed graph. The load balancing scheme used here is fully decentralized, thus making it apt for large network systems like that in a cloud. Biased Random Sampling investigated a distributed and scalable load balancing approach that uses random sampling of the system domain to achieve self-organization thus balancing the load across all nodes of the system. The performance of the system is improved with high and similar population of resources thus resulting in an increased 23

throughput by effectively utilizing the increased system resources. It is degraded with an increase in population diversity. Merits: 

It is fully decentralized.



The performance of the system is improved with high and similar population of resources thus resulting in an increased throughput by effectively utilizing the increased system resources.

Active Clustering: Active Clustering works on the principle of grouping similar nodes together and working on these groups. The process involved is: 

A node initiates the process and selects another node called the matchmaker node from its neighbors satisfying the criteria that it should be of a different type than the former one.



The so called matchmaker node then forms a connection between neighbors of it which is of the same type as the initial node.



The matchmaker node then detaches the connection between itself and the initial node.

The above set of processes is followed iteratively. Active Clustering investigated a self-aggregation Load Balancing Techniques that is self aggregation algorithm to optimize job assignments by connecting similar services using local re-wiring. The performance of the system is enhanced with high resources thereby increasing the throughput by using these resources effectively. It is degraded with an increase in system diversity. Merits: 

It investigated a self-aggregation Load Balancing Techniques that is self aggregation algorithm to optimize job assignments by connecting similar services using local re-wiring.



The performance of the system is enhanced with high resources thereby increasing the throughput by using these resources effectively.

24

Demerits: 

It is degraded with an increase in system diversity.

Symbiotic Routing in Future Data centers H. Abu-Libdeh et al. [23] has been work for distributed applications that are run in datacenter. To build distributed applications that run in data centers is hard. The CamCube project explores the design of a shipping container sized data center with the goal of building an easier platform on which to build these applications. This design impacts the services that run in the data center. External facing applications, like Search, Hotmail or Shopping Carts, rely on a set of internal distributed services. These services like Google GFS [29], Google BigTable [16], Amazon Dynamo [22], Yahoo Hadoop, and Microsoft Dryad, act as the building blocks for the external facing applications, and Building services efficiently on current data centers is hard, in part because the network is a black box, and the services have to infer properties like end-system network proximity within the data center. They have been exploring new data center architectures targeted at shipping container sized data centers, aimed at making it easier to build efficient services. The observations show that many of the services running in data centers are key-based and have similarities with services that run on overlays. Conceptually, in this they want to take a topology used in a structured overlay and create a physical instantiation of that topology. Their prototype, called CamCube, uses a 3D torus, also known as a k-ary 3-cube, which is the topology used in the Content Addressable Network (CAN) structured overlay. This creates a direct-connect topology, where each server connects directly to a small set of other servers, without using any switches or routers. Using this topology means that the virtual and physical topologies are the same, and the key space is a 3D wrapped coordinate space, where each server is assigned an (x; y; z) coordinate that represents the server's location within the 3D torus. The core CamCube API then exposes the coordinate space, and only provides functionality to send and receive packets to and from physical one-hop neighbors. This API with the coordinate space provides properties similar to those used in structured overlays. DCell and BCube [24], that also explore incorporating hybrid direct connect topologies in data centers. Merits: 

At the network level this can provide better performance.

25



The individual services can obtain better application-level performance by utilizing their own protocols.



For all services the network load is reduced when the service uses its own optimized protocol.

Gossip-based Aggregation in Large Dynamic Networks Mark Jelasity, et al. [7], has present aggregation protocol is based on the “push-pull gossiping” scheme. In this paper, the main focus is on aggregation which is useful building block in large, unreliable and dynamic systems. The name aggregation is for a set of functions that provide a summary of some global system property. They also distinguish reactive and proactive protocol for computing aggregation functions. Reactive protocols respond to specific queries issued by nodes in the network. The answers are returned directly to the query issuer while the rest of the nodes may or may not learn about the answer. On the other hand, Proactive protocols continuously provide the value of some aggregate function to all nodes in the system in an adaptive fashion. By adaptive protocol it mean that if the aggregate changes due to network dynamism or because of variations in the input values, the output of the aggregation protocol should track these changes reasonably quickly. This paper introduces a robust and adaptive protocol for calculating aggregates in a proactive manner. Each node maintains a local approximate of the aggregate value. Merits:



To provide up-to-date estimates, the protocol must be periodically restarted.



Presented a full-fledged proactive aggregation protocol.



To demonstrate several desirable properties including low cost, rapid convergence, adaptive and robustness to network dynamics through theoretical an experimental analysis.



To suggests both efficiency and scalability.

Demerits: 

The protocol described so far is based on the assumption that. In a large-scale distributed system, assumptions like cycle and epochs proceed in lock step at all nodes cannot be satisfied due to the unpredictability of message delays and the different drift rates of local clocks.



It examined two sources of random failures: node crashes and link failures.

26



It also shows that performance degrades gracefully with increasing link failure probability.

Locality-Aware and Churn-Resilient Load Balancing Algorithms in Structured P2P Networks H. Shen, et al. [26] took both proximity [4] and dynamic features of DHTs [28] to present the locality aware randomized load balancing algorithm. Randomized matching between heavy and light nodes can be done for dynamic feature. But physical proximity of node do not consider. Locality-aware methods in load balancing deal with this problem but it is costly in terms of construction and maintenance of network. According to node capacities, as well as node proximity information in topology-aware DHTs, algorithms distribute application load among the nodes by “moving items”. This paper presented a new scheme of load balancing for key value cache system in cloud environment in consideration with the effect of load balancing and the scope of invalid cache. To improve the effect of load balancing randomized factor in the searching process to deal with proximity Cache-invalidation-scope model is established. Also improve the efficiency of load balancing by d-way probing. Load balancing in cloud computing system Ram Prasad Padhy, et al. [9] discussed on basic concepts of Cloud Computing and Load balancing and studied that, the closed-form solutions for minimum measurement and reporting time for single level tree networks with different load balancing strategies were also studied. The performance of these strategies with respect to the timing and the effect of link and measurement speed were studied. Load Balance with Imperfect Information in Structured Peer-to-Peer Systems Hung-Chang Hsiao, et al. [25] proposed a novel load balancing algorithm that is unique in that the partial knowledge of the system required for each participating peer, to estimate the probability distributions of the capacities of peers and the loads of virtual servers, resulting in imperfect knowledge of the system state. Peers can compute their expected loads and reallocate their loads in parallel, with the imperfect system state. For balancing loads among participating peers, also concern with the minimizing movement cost as much as possible and also concern with the minimizing load imbalance factor. 27

Merits: 

The load of virtual servers based on partial knowledge of the system.



The participating peers perceive the nearly identical workload.



Applicable to any DHT network because does not considering any specific geometry of DHT’s.

Load Rebalancing for Distributed File Systems in Clouds Hung-Chang Hsiao et al. [5] gives the load rebalancing algorithm to distribute load among nodes as uniform as possible for distributed file system in clouds. This algorithm is to deal with load rebalancing problem in large scale, dynamic and distributed file systems in clouds. This proposal strives to balance the loads of nodes and reduce the movement cost as much as possible. The concept of algorithm is, file is partitioned into number of disjoined and fixed size chunks. These chunks are distributed among nodes or also called chunkserver, then find overloaded and underloaded node. Underloaded node transfers their load to its successor and joins this node as successor to overloaded node and seeks for load from overloaded node. This process repeat until all nodes become in balance state. This algorithm implemented in Hadoop HDFS. The file chunks are allocated in distinct nodes so that MapReduce tasks can be performed in parallel over nodes. This algorithm outperform in terms of load imbalance factor, movement cost and algorithmic overhead. Also this algorithm exhibits a fast convergence rate. Merits: 

Outperform in terms of load imbalance factor, movement cost and algorithmic overhead.



Algorithm exhibits a fast convergence rate i.e. light nodes seeks to relieve the load of heaviest node, leading to quick system convergence towards the loadbalanced state.



Reduce demanded movement cost as much as possible while taking the advantage of physical network locality and node heterogeneity.

Decentralized Approach for Balancing Load in Dynamic Cloud Environment Karthick Smiline Britto.J et Al. [31] has designed Effective weight based load balancing algorithm. The virtualization is established as an important phenomenon in the process of balancing and simulating the load in any type of the environment. Involving 28

virtualization technique and also considering the virtual machines in the process of simulating the load balancing can be effectively done on means of using the Effective Weight Based Algorithm. It involves in it the set of clients used for uploading the files in the system and then it also has in it the master and the Weighted Active Balancer. Merits: 

To balance the loads of nodes and reduce the demanded movement cost as much as possible, while taking advantage of the weight of every node.



It may also deal with the process of minimizing the movement cost and maximize the processing speed of the distributed environment.

2.2

SUMMARY

This chapter gives an overall description of various load balancing algorithms that can be used in case of peer-to-peer systems, large scale, and dynamic and distributed file systems in clouds.

29

CHAPTER-3 SYSTEM DEVELOPMENT 3.1

METHODOLOGY

Several load balancing techniques have been developed to balance load but some of them having load rebalancing problem. In this thesis, the main interest in studying the load rebalancing problem in distributed file systems specialized for large scale, data intensive and dynamic clouds.

3.1.1

Existing Load Balancing System

Here we are considering already existing load balancing technique that is Round Robin algorithm. Round robin algorithm is based on the random sampling. It means that in this load balancing technique the load selects randomly. Therefore in such case some server is heavily loaded (overloaded) or some are lightly loaded (underloaded). For allocation purpose virtual machines are selected. If the more than one virtual machine is freely available and if the virtual machines are going to be selected on randomly bases, this algorithm will affects, then as compared to the demanded machine possibility of selecting more configured virtual machine will be high [19]. Algorithm: Algorithm - Round_Robin_Load_Balancing () Data Structure – 1. Hash Map- in which it stores the entry for the last VM allocated to a request from a given user base. 2. VM State List- the allocation status (i.e. busy available) of each VM is stored. 1. Initialize all the VM allocation status to AVAILABLE in the VM state list; 2. Initialize hash map with no entries; 3. While(new request are received by the Data Centre Controller) Do { a. Data Center Controller queue the requests; b. Data Centre Controller removes a request from the beginning of the queue; c. If (status of VM allocation == AVAILABLE && any entry of a VM

30

Corresponding to the current requesting user base contain in hash map) { - Reallocation of VM to the user base request; } Else { - For the user base request allocate VM using Round Robin Algorithm; - Update the entry of the VM and the user base in the hash map and the VM State list; } } In above algorithm that is Round Robin Load Balancing Algorithm, it selects the load randomly in case that some servers are lightly loaded or some are heavily loaded. It randomly selects virtual machines for the allocation. It may cause load rebalancing problem that is some nodes are overloaded and some are underloaded so there is imbalance state in the system. Due to imbalance state of system causes Load Rebalance problem. Load Rebalance problem discuss below in detail [19].

3.1.2

Load Rebalancing Problem

A large scale distributed file system consisting of set of nodes also called chunkservers V in a cloud, where n is the cardinality of chunkserver V i.e. | V | = n. Number of files stored in the n chunkservers. Set of files is denoted by F. Each file f ∈ F is partitioned into number of chunks denoted by Cf. The main objective of studying this load rebalancing algorithm is to design a load rebalancing algorithm to reallocate file chunks such a way that the chunks can be distributed among system or nodes as uniform as possible. Let A be the ideal number of chunks that any chunkserver i ∈ V is required to manage load balanced state, that is, 𝐴=

∑𝑓∈𝐹 |𝐶𝑓 | 𝑛

(3.1)

To minimize load imbalance factor in each chunkserver i defined as follows: ||𝐿𝑖 − 𝐴||

(3.2)

Table 2 summarized the used symbols. 31

Table 2: Used Symbols

V F F Cf N A

Chunkserver Set of Files Single file, f ∈ F Single chunk No. of chunkserver Ideal nu. Of chunks

In clouds, the files in F may be arbitrarily created, appended and deleted. Sometime the file chunks are not being uniformly distributed to the node or chunkservers. The number of existing system has this load rebalancing problem. For Example, in existing system load balancing takes place as follows [3], Table 3: Files and its respective chunks File

Chunks

f1

2

f2

5

f3

5

f4

3

Total Chunks

15

Table 3 shows files and its respective chunks. File f1is partitioned into 2 chunks. File f2 is partitioned into 5 chunks. File f3 is partitioned into 5 chunks. File f4 is partitioned into 3 chunks. Therefore files are divided into total 15 chunks. Table 4: File Chunks allocated to Nodes N1

N2

N3

N4

N5

f1-c1

f1-c2

f2-c1

f2-c2

f2-c3

f2-c4

f2-c5

f3-c1

f3-c2

f3-c3

f3-c4

f3-c5

f4-c1

f4-c2

f4-c3

Table 4 shows the allocation of chunks to nodes. Table 4 shows that the existing system is in imbalance state. It shows that there are 5 nodes and distribution of these chunks take place among these nodes but not in a uniform manner thus causing

32

imbalance in the load .This affects some parameters like load imbalance factor, the resource utilization, movement cost and convergence rate, etc.

3.1.3

Current work using Load Rebalancing

Table 5 shows existing system is in imbalance state. Table 5: Files and its respective chunks File

Chunks

f1

2

f2

5

f3

5

f4

3

Total Chunks

15

Table 5 shows files and its respective chunks. File f1 is partitioned into 2 chunks. File f2 is partitioned into 5 chunks. File f3 is partitioned into 5 chunks. File f4 is partitioned into 3 chunks. Therefore files are divided into total 15 chunks. Nodes not balance dimensionally. Table 6: Chunks allocated to Nodes in Rebalancing system N1

N2

N3

N4

N5

f1-c1

f1-c2

f4-c1

f4-c2

f4-c3

f2-c1

f2-c2

f2-c3

f2-c4

f2-c5

f3-c1

f3-c2

f3-c3

f3-c4

f3-c5

3

3

3

3

3

Table 6 shows the distribution of chunks in current system such a way that the load balance in the current system takes place. It shows that there are 5 nodes and the distribution of these chunks takes place among them in a uniform manner thus causing “load rebalance”. According to table 6 each node has equal number of chunks or load thus avoiding excess load on only any particular nodes [3]. The goal of load rebalancing algorithm is to distribute load among nodes as uniform as possible [5].

33

Algorithm: Algorithm: Load Rebalancing Input: File from using Dataset files F i.e. f Output: Load of nodes or chunkserver as uniform as possible 1. Estimate number of ideal chunks A. 2. Each file f partition into chunks Cf. 3. Initially distribute file chunks among n chunkservers. 4. Find light node and heavy node 5. Heavy node migrate its excessive load to light node, but load of light node does not exceed the ideal chunks A. 6. Repeat step 3 and 4 until load or file chunk distribution among all nodes or chunkservers as uniform as possible. 7. Stop if no one node is heavily loaded.

3.2

IMPLEMENTATION

3.2.1

Architecture:

The basic architecture we have implemented for load rebalancing has been shown in Figure 3.1.

Input

File

DHT

Load

file (f)

Allocation

formulation

Rebalancing

Load Balance state

Figure 3.1: Architecture



File Allocation



DHT formulation



Load balancing algorithm

1) File Allocation In this module, large file is partitioned or divided into number of chunks (C1, C2, ..., Cn) and it allocates to Chunkserver. Here the files can be appended, added, or deleted dynamically to sub server. It will help to avoid the data loss. Figure 3.2 Shows that, given 34

large file is partitioned into number of parts or chunks and those chunks are distributed among different Chunkserver. Name node Chunkserver

ChunkServer Chunkserver

File

File File

C1

C1

C3

C3

C1

C2

C3

C2

C2

Figure 3.2: File Allocation

2) DHT Formulation In this the organization of the chunkserver are as a DHT network that is each chunkserver implements a DHT protocol. The DHT structure can be decomposed into several main components. An abstract key-space is the foundation. An ownership of this key-space split among the participating nodes in a key-space partitioning scheme. To connect the nodes by using an overlay network and then allowed them to find the owner of any given key in the key-space. The use of the DHT for storage and retrieval might proceed as follows. To store a file with given filename and data in the DHT, the SHA-1 hash of filename is generated, producing key k, and a message put( k, data) is sent to any DHT participating node. The message is forwarded from one node to another node through the overlay network until it reaches the single node responsible for key k as specified by the key-space partitioning. This node then stores the data and the key. Again by hashing, any other node can retrieve the contents of the file to produce k and also find the data associated with k with a message get(k) by asking to any DHT node. The message will again be routed to the node responsible for k through the overlay network, which will reply with the stored data. To structure over network the distributed hash table (DHT) has unique identifier which assign to each file chunk that is each file chunk has a unique chunk id. Each file chunk having rapid key lookup in DHTs. DHT guarantees that if any node or 35

chunkserver leaves then allocated chunks are migrated to its successor; if node or chunkserver joins then it allocate the chunks which are stored in successor. Each chunkserver also has unique id. DHT network is transparent to the metadata management. DHT network specifies the location of chunks that can be integrated with existing distributed file system where master node manages namespace of file system and mapping of chunks to storage nodes. In DHT, if file chunks and nodes are designated with uniform IDs, the maximum load of a node is guaranteed to be O(log n) times the average in a probability of 1 – O(1/n)., thus balancing the loads of nodes to a certain extent. Figure 3.3 shows the structure of Distributed Hash Table which is visible to all nodes. Distributed Application

put (key, data) get (key)

data

Distributed Hash Table

Chunkserver

Chunkserver Chunkserver

…..

Figure 3.3: Distributed Hash Table

3) Load Rebalancing Algorithm Overview In load rebalancing algorithm, each chunkserver first, to find whether node is lightly loaded (Under loaded) or heavily loaded (Overloaded) in each sub server. A node is light if, number of chunk < (1-ΔL).A and a node is heavy if, Number of chunk > (1 +ΔU).A Where ΔL (0≤ ΔL < 1) and ΔU (0 ≤ ΔU < 1) are the system parameters. All heavily loaded nodes shared its load with lightly loaded node. If node ‘i’ is the lightly loaded and node ‘j’ is the highly loaded, then light node transfer its load to its successor ‘i+1’ and after transferring load node ‘i’ become free and then join instantly as successor i.e. ‘j+1’ to heavy node ‘j’. The heavily loaded node ‘j’ transfer requested chunks to lightly loaded node ‘j+1’ and it traverse through physical network link. 36

Consider example, the capacity of each chunkserver is 512 MB i.e. 3 chunks (each chunk is of 128 MB) then according to below Figure 3.4 and load rebalancing algorithm chunkserver1 is light node having load 384 MB (no. of chunk < (1-ΔL) A) and Chunkserver 3 is the heavy node having load 640 MB (no. of chunk > (1-ΔU) A). Using the load equalization technique, heavy node transfers its load to light node i.e. Chunkserver 3 transfer its some load to Chunkserver 1 [5]. Under loaded

Name node

node

Over

loaded

node

C1

C2

C1

11

C2

C1

C3

C2

C3 C3

C4

C4

C5

Figure 3.4: Under loaded and Overloaded node

After transferring load from heavy node to light node to balance the load among chunkserver, this balance state shows in following figure 3.5. In Figure 3.5, file chunk c5 migrate from heavy node to light node. So file chunks are distributed among nodes as uniformly as possible. Name node

C1

C2

11 C3

C1

C2

C4

C3

C2

C5 C3

C1

C4

Figure 3.5: Load Balance State

Figure 3.6 shows the flowchart for implementation of a Load Rebalancing algorithm.

37

Input sample file f

Estimate A

Create file chunks

Allocation/Migrate file chunks

Find light & heavy node

yes

no Stop Figure 3.6: Flowchart for Load Rebalancing

3.2.2

Pros of Running Simulation

Cloud computing, according to NIST, is a pay per usage, distributed model for enabling on demand network access to a wide variety of resources like hardware, software, network etc that is provided by the cloud service provider to the customer as per his request. People, today, are shifting from traditional computing towards cloud as it provides higher reliability, fault tolerance, broad network access, on demand usage etc. But cloud suffers from some serious issues as well, the major of which is monetary cost involved in using cloud resources and also cost involved in making sure that internet is always available, as cloud computing is purely an internet based technology. For, this reason, the need of the hour is to have some less costly solution, and thus having an option of using simulation tools in cloud. Use of cloud computing is increasing at a very fast space everywhere because it turns the capital expenditure cost into operational cost. In addition to that, use of simulation tools is considered a better option in spite of being on the real cloud as performing experiments in a controlled and dependent environment is difficult and costly to handle. Moreover, effective resource utilization is not possible in case of Cloud. So, need to just shift towards cloud simulation tools. Following are the advantages of running simulation tools in cloud:

38



No capital cost involved: As discussed earlier, that cloud computing makes a shift from capital expenditure cost to operational cost. Having a cloud simulation tool also involves having no installation cost or maintenance cost as well.



Leads to better results: Using such tools helps to change inputs and other parameters as well very easily which results in better and efficient output



Evaluation of risks at an early stage: Because simulation tools involve no cost while running as is in case of being on cloud, so user can identify and solve any risk that is associated with the design or with any parameter.



Easy to learn: While working with such simulation tools, user needs to have only programming abilities and rest all depend on that. If the user is well versed with the language, then simulation tools offer no problem.

So, above are some of the advantages that are provided by the tools.

3.3

CLOUD SIMULATION TOOLS

There are various simulation tools for cloud, some of which are as follows [17]:       

CloudSim WorkflowSim GDCSim Cloud Analyst Network Cloud MDCSim SPECI

CloudSim 3.0.3 and WorkflowSim, Extended version of CloudSim both are used to implement Load Rebalancing Algorithm. CloudSim: Analyzing the performance, policies in real cloud is difficult to achieve because of its altering nature, so in such a situation, there is an option for CloudSim. CloudSim is a famous tool that is actually a toolkit for simulation of cloud scenarios. CloudSim has been developed as a Cloud Bus project in Australia. CloudSim actually enables the users to have a proper insight into cloud scenarios without worrying about the low level implementation details.

3.3.1

CloudSim Architecture

CloudSim has a layered architecture as shown in Figure 3.7; it is composed of several layers. Here, CloudSim 3.0.3 layered architecture has been discussed. 39

Initial releases of CloudSim used SimJava as the discrete event simulation engine that supports several core functionalities, such as queuing and processing of events, creation of Cloud system entities (services, host, data center, broker, VMs), communication between components, and management of the simulation clock. However in the current release, the SimJava layer has been removed in order to allow some advanced operations that are not supported by it. The CloudSim simulation layer provides support for modeling and simulation of virtualized Cloud-based data center environments including dedicated management interfaces for VMs, memory, storage, and bandwidth. The fundamental issues, such as provisioning of hosts to VMs, managing application execution, and monitoring dynamic system state, are handled by this layer. A Cloud provider, who wants to study the efficiency of different policies in allocating its hosts to VMs (VM provisioning), would need to implement his strategies at this layer. Such implementation can be done by programmatically extending the core VM provisioning functionality. There is a clear distinction at this layer related to provisioning of hosts to VMs. A Cloud host can be concurrently allocated to a set of VMs that execute applications based on SaaS provider’s defined QoS levels. This layer also exposes the functionalities that a Cloud application developer can extend to perform complex workload profiling and application performance study. The top-most layer in the CloudSim stack is the User Code that exposes basic entities for hosts (number of machines, their specification, and so on), applications (number of tasks and their requirements), VMs, number of users and their application types, and broker scheduling policies. By extending the basic entities given at this layer, a Cloud application developer can perform the following activities: (i) generate a mix of workload request distributions, application configurations; (ii) model Cloud availability scenarios and perform robust tests based on the custom configurations; and (iii) implement custom application provisioning techniques for clouds and their federation. As Cloud computing is still an emerging paradigm for distributed computing, there is a lack of defined standards, tools, and methods that can efficiently tackle the infrastructure and application level complexities. Hence, in the near future there will be a number of research efforts both in the academia and industry toward defining core algorithms, policies, and application benchmarking based on execution contexts. By extending the basic functionalities already exposed to CloudSim, researchers will be able 40

to perform tests based on specific scenarios and configurations, thereby allowing the development of best practices in all the critical aspects related to Cloud Computing [17].

Figure 3.7: CloudSim Architecture

All components in CloudSim communicate through the process of message passing. The lowermost layer is responsible for managing the communication between various components. The second layer has all the sub layers in it that have the main cloud components.

3.3.2

Features of CloudSim

CloudSim features [17]: 

Support for modeling and simulation of large scale Cloud computing data centers.



Support for modeling and simulation of virtualized server hosts, with customizable policies for provisioning host resources to virtual machines.



Support for modeling and simulation of energy-aware computational resources.



Support for modeling and simulation of data center network topologies and message-passing applications.



Support for modeling and simulation of federated clouds.



Support for dynamic insertion of simulation elements, stop and resume of simulation. 41



support for user-defined policies for allocation of hosts to virtual machines and policies for allocation of host resources to virtual machines



Physical Machine - The allocation policy is applied at initial state. In case of storage, cloudsim has partially implemented storage area network. All the files needed to start an application are first copied & the application starts.



Communication Between VMs - In the cloudsim, all the communication between virtual machines happen, before the start of the application.



Migration Policies - Currently, cloudsim implemented a migration policy based on load on a specific physical machine.



Scalability - Currently cloudsim uses configuration about physical and virtual machines, using java source code.



Resource - In cloudsim approach, there is no interference between different resources. Here interference means, usage of disk operation, also creates CPU load.

3.3.3

WorkflowSim

WorkflowSim extends the CloudSim simulation toolkit by introducing the support of workflow preparation and execution with an implementation of a stack of workflow parser, workflow engine and job scheduler. It supports a multi-layered model of failures and delays occurring in the various levels of the workflow management systems. A series of popular workflow scheduling algorithms (e.g., HEFT, Min-Min, and Max-Min) and task clustering algorithms have been implemented in WorkflowSim. Parameters are directly learned from traces of real executions that were run by workflow management systems such as Pegasus. WorkflowSim has been developed by Weiwei Chen and team at University of Southern California, USA.

3.4

SIMULATION

Load Rebalancing Algorithm is executed by using CloudSim and Extended version of CloudSim i.e. WorkflowSim simulator. WorkflowSim contain .xml file, these files consider as input file to Rebalancing algorithm. Here, simulation takes place by considering single Datacenter (i.e. Datacenter ID is 2), these datacenter has single host, and single host has 5 virtual machines (VM) (i.e.

42

VM ID 0 to 4). File chunks (i.e. Cloudlet ID) are allocated to VM based on the algorithm. These are the assumption in implementation of Load Rebalancing Algorithm.

3.4.1

Simulation setup

Load rebalancing algorithm is implemented with the help of simulation package like Cloudsim and cloudsim based tool. Java language is used for implementing VM load rebalancing algorithm. We assume that the cloudsim toolkit has been deployed in one data centre having 5 virtual machines (with 512 Mb of memory in each VM running on physical host with 1000 MIPS) where the parameter values are as under. Table 7: Parameter values

Parameter

Values

VM image size

10000

VM memory

512 MB

VM bandwidth

1000

Datacenter Architecture

X86

Datacenter OS

Linux

Datacenter VMM

Xen

Datacenter no. of machines

5

Datacenter memory per machines

2048MB

Datacenter storage per machines

10000MB

Datacenter available BW per machines 1000 Datacenter machines

no.

of

processor

per 5

Datacenter VM policy

Time shared

Service broker policy

Optimized Response Time

3.5 3.5.1

GRAPHICAL USER INTERFACE SNAPSHOTS Home Screen

Following Figure 3.8 shows the home screen for Load Rebalancing Algorithm:

43

Figure 3.8: Home Screen

The basic components of Home screen are: 1.

List of log files which is input to the algorithm.

2.

Select Algorithm.

3.

Start button is used to run the algorithm.

4.

Exit button is used to close home screen.

Without selecting any file if click on start button, it will show some message which is shown in Figure 3.9:

44

Figure 3.9: Without selecting file

3.5.2

Select File and Algorithm

Select file from list and select one of the algorithms by clicking on the one of the radio button. This is shown in Figure 3.10. Here, files consider from the dataset which is present in WorkflowSim. For Example, in following figure Rebalancing algorithm is selected for Inspiral_30.xml file.

45

Figure 3.10: Selecting File and Algorithm

3.5.3

Output window

After selecting input file from list of log files and Algorithm, click on Start button to execute algorithm. Figure 3.11, Figure 3.12 and Figure 3.13 shows the generated output.

Figure 3.11: First output after executing Rebalancing Algo.

46

Figure 3.12: Second output after executing Rebalancing Algo.

Figure 3.13: Graph Time (in ms) vs. processing seq. of chunk

47

First output window in Figure 3.11 shows file chunk (i.e. Cloudlet id) allocated to virtual machine (i.e. VM ID) using load rebalancing algorithm. Here single Datacenter is considered which has id=2, Status shows that cloudlet or chunk allocated to virtual machine successfully or not from that it will generate SUCCESS or FAIL message. In CloudSim simulator these two status message generated. Second output window in Figure 3.12 shows cloudlet or chunks are rearranged from their arriving time. Sequence of cloudlet is rearranged. Figure 3.13 shows graph, time vs. sequence of chunk, from these two output windows.

3.6

USED TECHNOLOGY

For programming purpose Java programming language is used. Here jdk1.7 is used. Java has some features like Object Oriented, Platform independent, Portable, Secure, Robust due to high functionality, Distributed, for that purpose here is use of this language. Open source CloudSim tool is already implemented in java. Load Rebalancing Algorithm is easily implemented using this language.

3.7

SUMMARY

This chapter gives brief introduction about used simulation tool and technology as well as considered assumption for simulation purpose. The CloudSim simulator is probably the most sophisticated among the simulators overviewed.

48

CHAPTER-4 PERFORMANCE ANALYSIS 4.1

PERFORMANCE ANALYSIS OF EXISTING WORK

Here we are considering already existing load balancing technique that is Round Robin algorithm. Round robin algorithm is based on the random sampling. It means that in this load balancing technique the load selects randomly. Therefore in such case some server is heavily loaded (overloaded) or some are lightly loaded (underloaded). Virtual machines are selected for the allocation. If freely available virtual machine are more than one then this algorithm will affects and the virtual machines are going to be selected on randomly bases, then as compared to the demanded machine possibility of selecting more configured virtual machine will be high.

4.1.1 Simulation results For Existing work Table 8 shows the load distribution of among virtual machines after taking file “Montage_50.xml” as input from given list of files. After performing simulation more than one time, by averaging all load distribution which was takes place by using Round Robin algorithm as shown in Table 8. Table 8: Load distribution using Round Robin Algo.

RR

vm0

vm1

vm2

vm3

vm4

10

12

13

6

10

Load distribution among 5 virtual machines having id 0, 1, 2, 3, 4. RR means Round Robin algorithm. From Table 8, we can say that virtual machine 3 (i.e. vm3) is underloaded and virtual machine 2 (i.e. vm2) is overloaded. Size of chunks will get increase the execution time will also increase. Execution time for algorithm for different size of load is shown in Table 9. Simulation performs on different number of chunks or different size of load.

49

Table 9: Execution time (in ms) for different load size

4.2

Load size

25

50

100

1000

Exe.Time (ms)

823.2650907

1194.15156

1953.058525

21827.10268

PERFORMANCE

ANALYSIS

OF

LOAD

REBALANCING ALGORITHM The main aim of to design Load Rebalancing algorithm for Distributed file Systems in Cloud is to remove load rebalancing problem and distribution of load among nodes as uniform as possible. Already existing load balancing technique has Load Rebalancing problem. By using this algorithm we can minimize this problem by distributing load among nodes as uniform as possible that is no one node is underloaded (lightly loaded) and no one node is overloaded (heavily loaded).

4.2.1 Simulation Results for Load Rebalancing Algorithm Table 10 shows the load distribution among virtual machines using Load Rebalancing (RB) algorithm. Same file, which was taken for Round Robin algorithm that is, “Montage_50.xml” is consider as input file for this algorithm.

After performing

simulation more than one time, by averaging all load distribution which was takes place by using Load Rebalancing algorithm as shown in Table 10. Table 10: Load distribution using Load Rebalancing Algorithm

RB

vm0

vm1

vm2

vm3

vm4

12

8

7

12

12

Load distribution among 5 virtual machines having id 0, 1, 2, 3, 4 using RB means Load Rebalancing Algorithm. From Table 8, we can say that distribution of load among virtual machine 0 (i.e. vm0), virtual machine 3 (i.e. vm3) and virtual machine 4 (i.e. vm4) is uniform. As compare to these 3 virtual machines, virtual machine 1 (i.e. vm1) and virtual machine (i.e. vm2) having less load but the difference is not much more. So we can say that the distribution of load among nodes or virtual machines is as uniform as possible. Execution time for Load Rebalancing algorithm for different size of load is shown in Table 11. Simulation performs on different number of chunks or different size of load. 50

Table 11: Execution time (in ms) for different load size

Load size Exe.Time (ms)

4.3

25

50

100

1000

510.9873455

1343.192157

1897.653793

19738.46927

EXPERIMENTAL COMPARISION

In order to improve the distribution of load among nodes as uniform as possible and also execution time for algorithms for different size of load or file chunks. Perform simulation for same input file from dataset for both Round Robin algorithm and Load Rebalancing algorithms. The simulation result we have already seen performance analysis.

4.3.1 Comparison of Round Robin and Load Rebalancing Algorithm The result of simulation for distribution of load by using Round Robin Algorithm as well as Load Rebalancing Algorithm for same input file from dataset files i.e. “Montage_50.xml”. Table 12 shows the comparison of load distribution among virtual machines using both algorithms. Table 12: Comparison of load distribution among nodes

vm0

vm1

vm2

vm3

vm4

RR

10

12

13

10

6

RB

12

8

7

12

12

Figure 4.1 show the comparison of load distribution by Round Robin (RR) and Load distribution by Load Rebalancing (RB).

51

14 12 10 Load

8 6

RB

4

RR

2 0 0

1

2

3

4

VM ID

Figure 4.1: Comparison of load distribution using RR and RB

Load distribution among node by using RB is as uniform as possible as compare to by using RR. At VM ID 0, 3 and 4 the load is uniformly distributed and At VM ID 1 and 2 load distribution is not uniform but it also does not have much more difference. But by using RR algorithm Load distribution at VM ID 0 and 3 is uniform i.e. 10 and VM ID 1 has load 12 and VM ID 2 has load 13, that is nearly uniform but VM ID 4 has load 6. As compare to VM ID 0, 1, 2 and 3, the VM ID 4 is underloaded and load distribution difference is high, nearly ‘double’. From this comparison we can say that Load distribution among nodes by using RB better than RR. Table 13 shows the execution time (in ms) for both algorithms that is Load Rebalancing Algorithm (RB) and Round Robin Algorithm (RR) by considering different size of load. Table 13: Comparison of Execution time (in ms) for diff. size of load

Load

25

50

100

1000

RR

823.2650907

1194.15156

1953.058525

21827.10268

RB

510.9873455

1343.192157

1897.653793

19738.46927

Algorithm

Figure 4.2 shows the time required to execute respective algorithm for different size of load or different number of chunks. Figure 4.2 show the graph for load (number of chunks) vs. required execution time (in ms) for RR and RB algorithm.

52

25000 20000

Exe. Time (in ms)

15000 RB

10000

RR 5000 0 25

50

100

1000

Load

Figure 4.2: Comparison of Execution time for Different size of load

4.4

JUSTIFICATION DIFFERENCE

1. In our implementation of Load Rebalancing algorithm the distribution of load among nodes is as uniform as possible as compare to existing load balancing technique. 2. Also the execution time required for this implemented algorithm is slightly less than that of existing algorithm for different size of load or for different number of file chunk.

4.5 SUMMARY In this chapter, we discuss about the performance analysis of implemented algorithm that is Load Rebalancing algorithm. And this algorithm compare with existing algorithm, Round Robin algorithm. Comparison is takes place for load distribution among nodes and also compare the execution time for different size of load for both algorithms.

53

CHAPTER-5 CONCLUSION 5.1

CONCLUSION

In this thesis we have implemented Balancing of Load for Distributed File Systems in Cloud using Load Rebalancing in short Load Rebalancing algorithm. Large scale, Distributed file system, dynamic in nature in clouds has Load Rebalancing problem. To minimize or overcome this problem is possible by using Load Rebalancing algorithm. Our implementation of this algorithm, the simulation result shows that distribution of load among nodes is as uniform as possible as compare to existing algorithm. Also the execution time required for Load Rebalancing algorithm is less than that of existing algorithm.

5.2

FUTURE SCOPE



Load rebalancing algorithm will also implement for number of different parameters to improve the efficiency of an algorithm.



To elaborate system in future, in this simulation intermediates steps are not seen because of simulator limitation.

5.3

APPLICATIONS

This algorithm has been implemented for following areas: 

Balancing load in large scale environment.



Balancing load for Distributed File System.



Balancing Load for Dynamic environment.



Balancing load in clouds.

54

BIBLIOGRAPHY [1] K. Lakshmi narayanan, S. Surana, R. Karp and I. Stoica A. Rao, "Load Balancing in Structured P2P Systems," Proc. Second Int'l Workshop Peer-to-Peer Systems (IPTPS „02), pp. 68-79, Feb. 2003. [2] S. Penmatsa and T. Chronopoulos, "Game-theoretic static load balancing for distributed systems," Journal of Parallel and Distributed Computing, vol. 71(4), pp. 537-555, Apr. 2011. [3] W.

Chen

and

E.

Deelman,

"WorkflowSim:

A

toolkit

for

simulating

scientificworkflows in distributed environments," in IEEE 8th International Conference on (e- Science), 2012. [4] Y. Zhu and Y. Hu, "Efficient, Proximity-Aware Load Balancing for DHT-Based P2P Systems," IEEE Trans. Parallel and Distributed Systems, vol. 16(4), pp. 349361, Apr. 2005. [5] Hsueh Yi Chung, Haiying Shen and Yu Chang Chao Hung Chang Hsiao, "Load Rebalancing for Distributed File Systems in Clouds," IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, vol. 24(5), pp. 951-962, May 2013. [6] Jeffrey Considine and Michael Mituenmacher John Byers, "Simple Load Balancing for Distributed Hash Tables," Pmc.IPTFS, Feb. 2003. [7] A. Montresor, and O. Babaoglu M. Jelasity, "Gossip-Based Aggregation in Large Dynamic Networks," ACM Tran. Computer System Vol. 23(3), pp. 219-252, Aug. 2005. [8] D. Lamb and A. Taleb Bendiab M. Randles, "A Comparative Study into Distributed Load Balancing Algorithms for Cloud Computing," Proceedings of 24th IEEE International Conference on Advanced Information Networking and Applications Workshops, Perth, Australia, pp. 551-556, April 2010. [9] Ram Prasad Padhy and PGoutam Prasad, "Load balancing in cloud computing system," Department of Computer Science and Engineering National Institute of Technology, Rourkela Rourkela-769 008, Orissa, May 2011.

55

[10] Suriya Begum and Dr. Prashanth, "Investigational Study of 7 Effective Schemes of Load Balancing in Cloud Computing," International Journal of Computer Science Issues, Vol. 10(1), pp. 276-287, Nov. 2013. [11] D. Kargar and M. Ruhl, "Simple Efficient Load Balancing Algorithms for Peer-toPeer Systems," Proc. 16th ACM Symp. Parallel Algorithms and Architectures (SPAA ’04), pp. 36-43, June 2004. [12] J. R. Douceur and R. P. Watlenhofer, "Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System," in Pmc. DISC, 2001. [13] "Cloud Computing Basics.pdf,". [14] "Cloud_Computing_Tutorial.pdf,". [15] Distributed

Hash

Table.

[Online].

https://en.wikipedia.org/wiki/Distributed_hash_table [16] MPI Forum. [Online]. http://www.mpi-forum.org. [17] Cloud Computing and Distributed Systems (CLOUDS) Laboratory. [Online]. http://www.cloudbus.org/cloudsim/ [18] Hadoop Distributed File System. [Online]. http://hadoop.apache.org/hdfs/, 2012. [19] Nusrat Pasha Dr. Ravi Rastogi and Dr. Amit Agarwal, "Round Robin Approach for VM Load Balancing Algorithm in Cloud Computing Environment," International Journal of Advanced Research in Computer Science and Software Engineering, vol. 4, no. 5, pp. 34-39, May 2014. [20] M. Bawa, and H. Garcia-Molina P. Ganesan, "Online Balancing of RangePartitioned Data with Applications to Peer-to-Peer Systems," in Proc. 13th Int'l Conf. Very Large Bases (VLB ' 04), pp. 444-455, Sept. 2004. [21] A. Rowstron and P. Druschel, "Parsty: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems," Proc. IFIP/ ACM Int'l Conf. Distributed Systems Platforms Heidelberg, pp. 161-172, Nov. 2001.

56

[22] D. Hastorun, M.Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sicasubramanian, P. Vosshall, and W. Vogels G. DeCandia, "Dynamo: Amazon's Highly Available Key-Value Store," Proc. 21st ACM Symp. Operating Systems Principles (SOSP' 07), pp. 205-220, Oct. 2007. [23] P. Costa, A. Rowstron, G. O'Shea, and A. Donnelly H. Abu-Libdeh, "Symbiotic Routing in Future Data Centers," Proc. ACM SIGCOMM '10, pp. 51-62, Aug. 2010. [24] G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang and S. Lu C. Guo, "BCube: A High Performance, Server-Centric Network Architecture for Modular Data Centers," Proc. ACM SIGCOMM'09, pp. 63-74, Aug. 2009. [25] H. Liao, S. S. Chen, and K. C. Huang H. C. Hsiao, "Load Balance with Imperfect Information in Structured Peer-to-Peer Systems," IEEE Trans. Parallel Distributed Systems, vol. 22, no. 4, pp. 634-649, Apr.2011. [26] H. Shen and C. Z. Xu, "Locality-Aware and Churn-Resilient Load Balancing Algorithma in Structured P2P Networks," IEEE Trans. Parallel and Distributed Systems, vol. 18, no. 6, pp. 849-862, June 2007. [27] M. Agrawal, and S. Seshan A. Bharambe, "Mercury: Supporting Scalable MultiAttribute Range Queries," Proc. ACM SIGCOMM'04, pp. 353-366, Aug. 2004. [28] B. Godfrey, K. Lakshminarayanan, R. Karp and I. Stoica S. Surana, "Load Balancing in Dynamic Structured P2P Systems," Performance Evaluation, vol. 63(6), pp. 217-240, March 2006. [29] H. Gobioff and S. T. Leung S. Ghemawat, "The Google File System," Proc. 19th ACM Symp. Operating Systems Principles (SOSP), pp. 29-43, Oct. 2003. [30] B. Santhosh Kumar and Dr. Latha Parthiban, "An Implementation of Load Balancing Policy for Virtual Machines Associated With a Data Center," International Journal of Computer Science & Engineering Technology, vol. Vol. 5, no. 3, pp. 253-261, March 2014. [31] PrittoPaul.P and Karthick Smiline Britto.J, "Decentralized Approach for Balancing Load in Dynamic Cloud Environment," International Journal of Innovative Research in Computer and Communication Engineering, vol. 2(1), pp. 2603-2610,

57

March 2014. [32] Robert Morris, David Karger, M. Frans Kaashoek and Hari Balakrishnan Ion Stoica, "Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications," IEEE/ACM Transaction On Networking, vol. 11, no. 1, pp. 149-160, Feb. 2003. [33] Sushil Chaturvedi and S.K. Shrivastava Divya Diwakar, "Water-Filling: A Novel Approach of Load Rebalancing for File Systems in Cloud," International Journal of Computer Applications, vol. 126(14), pp. 0975 – 8887, Sept. 2015. [34] Radha G. Dobale and Prof. R. P. Sonar, "Review of Load Balancing for Distributed Systems in Cloud," International Journal of Advanced Research in Computer Science and Software Engineering, vol. 5, no. 2, pp. 393-400, Feb. 2015.

58

PUBLICATION [1] Jadhav Varsha and Mandre B. R., “Balancing of Load for Distributed File Systems in Clouds Using Load Rebalancing”, International Journal of Computer Science and Mobile Computing, vol. 5(1) , pp. 170-177, Jan. 2016.

59