Randomized loadbalancing and hashingIncomputing, load balancing improves the distribution of workloads acrossmultiple computing resources, such as computers, a computer cluster, networklinks, central processing units, or disk drives.
Load balancing aims tooptimize resource use, maximize throughput, minimize response time, and avoidoverload of any single resource. Using multiple components with load balancinginstead of a single component may increase reliability and availability throughredundancy. Load balancing usually involves dedicated software or hardware,such as a multilayer switch or a Domain Name System server process.Aserver program that is installed on a targeted system has limited resources.These resources include system memory, hard disk space, and processor speed.Since the server capacity is limited, so it can handle only certain number ofclients.
- Thesis Statement
- Structure and Outline
- Voice and Grammar
With more number of clients a server will be overloaded and that maylead to slow down of the performance, hang and crash issues. So, it is crucialto balance the load on server and this can be achieved by keeping copies ofservers and distribute the load among them.Loadbalancing is the process of making a group of servers participate in the sameservice and do the same work.
The general purpose of load balancing is toincrease availability, improve throughput, reliability, maintain stability,optimize resource utilization and provide fault tolerant capability. As thenumber of servers grows, theriskof a failure anywhere increases and such failures must be handled carefully.The ability to maintain unaffected service during any number of simultaneousfailures is termed as high availability. Loadbalancing is also provided by few operating systems. Microsoft’s Network LoadBalancing (NLB), a software-based solution that allows you to effortlessly clustermultiple machines 3.
There are variety open source load balancers and load balancingsoftware available for Linux, such as Linux Virtual Server, Ultra Monkey, Red HatCluster Suite, High Availability Linux (Linux HA); which can be used efficientlywith most of the network services, including FTP, HTTP, DNS, SMTP, POP/IMAP, VoIP,etc. LOAD BALANCING CONCEPT”Loadbalancing” means an even distribution of the total load amongst all servingentities.Load balancing is very essential in distributed computing systems toimprove the quality of service by managing customer loads that are changingover time. Therequestdemands of incoming requests are optimally distributed among available systemresources to avoid resource bottlenecks as well as to fully utilize available resources5. Load balancing also provides horizontal scaling e.
g., adding computingresources in order to address increased loads. Inorder to balance the requests of the resources it is important to recognize afew major goals ofloadbalancing algorithms:a)Cost effectiveness: primary aim is to achieve an overall improvement in systemperformanceat a reasonable cost.b)Scalability and flexibility: the distributed system in which the algorithm isimplementedmaychange in size or topology.
So the algorithm must be scalable and flexibleenough toallowsuch changes to be handled easily.c)Priority: prioritization of the resources or jobs need to be done on before handthrough thealgorithmitself for better service to the important or high prioritized jobs in spite ofequalserviceprovision for all the jobs regardless of their origin. Types of loadbalancingthereare two major types of load balancing . 1. Static loadbalancing2. Dynamic loadbalancing Static loadbalancingInthis category of static load balancing techniques, the performance of theserver nodes is determined at the initial stage of process.
Then based on theirperformance the work load is distributed by the master node. The slave nodes evaluatetheir allocated work and then send their result to the master node. A job isalways executed on the server node to which it is assigned that is static loadbalancing techniques are non-preemptive. The main intention of static loadbalancing method is to reduce the overall execution time of a concurrentprogram while minimizing the communicationdelays.A usual disadvantage of all static methods is thatthe final selection of aserver node for process allocation is made when the process is initiallycreated and it cannot be changed during process execution in order to make variationsin the system load.Dynamic loadbalancingDynamicload balancing techniques depend on recent system load information and determinethe job assignments to server nodes at run time. In case of dynamic approach,the load balancing decisions are based on the current state of the system andhence work loads are allowed to shift dynamically from an overloaded node to anunder-loaded node to get faster response from the server nodes.
This ability torespond to variations in the system is the main advantage of the dynamic loadbalancing. But, since the load balancer has to continuously monitor the currentsystem load on all the nodes, it becomes an extra overhead as monitoringconsumes CPU cycles. So, a proper decision must be taken when to invoke themonitoring operation by the load balancer.Applications 1. Load Balancing for JDBC Connections· Loadbalancing of JDBC connection requires the use of a multi data source configuredfor load balancing. Load balancing support is an option you can choose whenconfiguring a multi data source.
· Aload balancing multi data source balances the load among the data sources inthe multi data source. A multi data source has an ordered list of data sourcesit contains. If you do not configure the multi data source for load balancing,it always attempts to obtain a connection from the first data source in thelist.
In a load-balancing multi data source, the data sources it contains areaccessed using a round-robin scheme. In each successive client request for amulti data source connection, the list is rotated so the first pool tappedcycles around the list.2. Network load balancingNetwork LoadBalancing has several potential use cases and advantages. By distributingnetwork traffic across multiple servers or virtual machines, traffic can beprocessed faster than in a scenario in which all traffic flowed through asingle server. The feature can also enable an organization to quickly scale upa server application (such as a Web server) by adding hosts and thendistributing the application’s traffic among the new hosts. Similarly, ifdemand decreases, servers can be taken offline and the feature will balance trafficamong the remaining hosts.
Network Load Balancing can also ensure networktraffic is re-routed to remaining hosts if one or more hosts within the clusterfail unexpectedly. A Network Load Balancing cluster can scale up to 32 servers.3. load balancing on a routerNetwork loadbalancing (commonly referred to as dual-WAN routing or multihoming) is theability to balance traffic across two WAN links without using complex routingprotocols like BGP.This capabilitybalances network sessions like Web, email, etc. over multiple connections inorder to spread out the amount of bandwidth used by each LAN user, thusincreasing the total amount of bandwidth available.
For example, a user has asingle WAN connection to the Internet operating at 1.5Mbit/s. They wish to adda second broadband (cable, DSL, wireless, etc.) connection operating at2.5Mbit/s. This would provide them with a total of 4Mbit/s of bandwidth whenbalancing sessions.
Sessionbalancing does just that, it balances sessions across each WAN link. When Webbrowsers connect to the Internet, they commonly open multiple sessions, one forthe text, another for an image, another for some other image, etc. Each ofthese sessions can be balanced across the available connections. An FTPapplication only uses a single session so it is not balanced; however if asecondary FTP connection is made, then it may be balanced so that on the whole,traffic is evenly distributed across the various connections and thus providesan overall increase in throughput.
Additionally,network load balancing is commonly used to provide network redundancy so thatin the event of a WAN link outage, access to network resources is stillavailable via the secondary link(s). Redundancy is a key requirement forbusiness continuity plans and generally used in conjunction with criticalapplications like VPNs and VoIP.Finally, mostnetwork load balancing systems also incorporate the ability to balance bothoutbound and inbound traffic. Inbound load balancing is generally performed viadynamic DNS which can either be built into the system, or provided by anexternal service or system. Having the dynamic DNS service within the system isgenerally thought to be better from a cost savings and overall control point ofview.4. load balancing in cloud computingCloud loadbalancing is the process of distributing workloads and computing resources in acloud computing environment. Load balancing allows enterprises to manageapplication or workload demands by allocating resources among multiplecomputers, networks or servers.
Cloud load balancing involves hosting thedistribution of workload traffic and demands that reside over the Internet.Cloud loadbalancing helps enterprises achieve high performance levels for potentiallylower costs than traditional on-premises load balancing technology. Cloud loadbalancing takes advantage of the cloud’s scalability and agility to meetrerouted workload demands and to improve overall availability.
In addition toworkload and traffic distribution, cloud load balancing technology can providehealth checks for cloud applications.To avoid noisyneighbors and poor application performance in a public cloud environment, cloudload balancing uses virtual local area networks (VLANs), which group networknodes in various geographic locations to communicate as if they were in thesame physical location.Application chosenCloudcomputingBest solutionRandomisedload balancingRandomized loadbalancing is a type of static load balancing. Ina random allocation method, the client requests, for example HTTP requests, areassigned to any server picked randomly among the group of available servers. Insuch acase, one of the servers may beassigned more requests to process, while the other servers are sitting idle.
However, on an average, each server gets its share of the client load due tothe random selectionThe random method of load balancing applies onlyto EJB and RMI object clustering. In random loadbalancing, requests are routed to servers at random. Random load balancing is recommendedonly for homogeneous cluster deployments, where each server instance runs on asimilarly configured machine. A random allocation of requests does not allowfor differences in processing power among the machines upon which serverinstances run. If a machine hosting servers in a cluster has significantly lessprocessing power than other machines in the cluster, random load balancing willgive the less powerful machine as many requests as it gives more powerfulmachines.
Random load balancing distributes requestsevenly across server instances in the cluster, increasingly so as thecumulative number of requests increases. Over a small number of requests theload may not be balanced exactly evenly. Randomized algorithm is of type static innature. In this algorithm 25 aprocess can be handled by a particular node nwith a probability p. The process allocationorder is maintained for each processorindependent of allocation from remote processor.
This algorithm works well in case of processesare of equal loaded. However, problemarises when loads are of different computationalcomplexities. Randomized algorithm doesnot maintain deterministic approach. It workswell when Round Robin algorithm generatesoverhead for process queue. Disadvantages of random load balancingDisadvantages of random load balancing includethe slight processing overhead incurred by generating a random number for eachrequest, and the possibility that the load may not be evenly balanced over asmall number of requests.The algorithmAs its name implies, this algorithm matches clientsand servers by random, i.
e. using an underlying random number generator. Incases wherein the load balancer receives a large number of requests, a Randomalgorithm will be able to distribute the requests evenly to the nodes. So likeRound Robin, the Random algorithm is sufficient for clusters consisting ofnodes with similar configurations (CPU, RAM, etc). Using a random numbergenerator, the load balancer directs connections randomly to the web serversbehind it. This type of algorithm may be used if the web servers are of similaror same hardware specifications. If connection monitoring is not enabled, thenthe load balancer will continue sending traffic to failed web servers. Loadbalancers use a number of algorithms to direct traffic.
Some of the most commonalgorithms are listed below.Other Load Balancing Algorithms and their comparisons Name Working Example Limitation Round robin Using a circular queue, the load balancer walks through it, sending one request per server. Same as the random method, this works best when the web servers are of similar or same hardware specifications. The Round Robin algorithm is best for clusters consisting of servers with identical specs. Here’s how it works.
Let’s say you have 2 servers waiting for requests behind your load balancer. Once the first request arrives, the load balancer will forward that request to the 1st server. When the 2nd request arrives (presumably from a different client), that request will then be forwarded to the 2nd server. Because the 2nd server is the last in this cluster, the next request (i.e., the 3rd) will be forwarded back to the 1st server, the 4th request back to the 2nd server, and so on, in a cyclical fashion. The method is very simple. However, it won’t do well in certain scenarios.
For example, what if Server 1 had more CPU, RAM, and other specs compared to Server 2? Server 1 should be able to handle a higher workload than Server 2, right? Unfortunately, a load balancer running on a round robin algorithm won’t be able to treat the two servers accordingly. In spite of the two servers’ disproportionate capacities, the load balancer will still distribute requests equally. As a result, Server 2 can get overloaded faster and probably even go down. You wouldn’t want that to happen. Weighted Round Robin Web servers or a group of web servers are assigned a static weight. For instance, new web servers that can handle more load are assigned a higher weight and older web servers are assigned a lower weight.
The load balancer will send more traffic to the servers with a higher weight than the ones to the lower weight. The Weighted Round Robin is similar to the Round Robin in a sense that the manner by which requests are assigned to the nodes is still cyclical, albeit with a twist. The node with the higher specs will be apportioned a greater number of requests. But how would the load balancer know which node has a higher capacity? Simple.
You tell it beforehand. Basically, when you set up the load balancer, you assign “weights” to each node. The node with the higher specs should of course be given the higher weight. You usually specify weights in proportion to actual capacities. So, for example, if Server 1’s capacity is 5x more than Server 2’s, then you can assign it a weight of 5 and Server 2 a weight of 1. There can be instances when, even if two servers in a cluster have exactly the same specs (see first example/figure), one server can still get overloaded considerably faster than the other. One possible reason would be because clients connecting to Server 2 stay connected much longer than those connecting to Server 1.
This can cause the total current connections in Server 2 to pile up, while those of Server 1 (with clients connecting and disconnecting over shorter times) would virtually remain the same. As a result, Server 2’s resources can run out faster. This is depicted below, wherein clients 1 and 3 already disconnect, while 2, 4, 5, and 6 are still connected Least Connections Keeps a track of the connections to the web servers, and prefers to send connections to the servers with the least number of connections. This algorithm takes into consideration the number of current connections each server has. When a client attempts to connect, the load balancer will try to determine which server has the least number of connections and then assign the new connection to that server. So if say (continuing our last example), client 6 attempts to connect after 1 and 3 have already disconnected but 2 and 4 are still connected, the load balancer will assign client 6 to Server 1 instead of Server 2. Again the problem of weights.
Weighted Least Connections The Weighted Least Connections algorithm does to Least Connections what Weighted Round Robin does to Round Robin. That is, it introduces a “weight” component based on the respective capacities of each server. Just like in the Weighted Round Robin, you’ll have to specify each server’s “weight” beforehand. A load balancer that implements the Weighted Least Connections algorithm now takes into consideration two things: the weights/capacities of each server AND the current number of clients currently connected to each server. Plain ProgrammerDescription: The system builds an array of Servers beingload bal anced, and uses the random number generator to determine who gets thenext connection… Far from an elegant solution, and most often found in largesoftware packages that have thrown load balancing in as a feature.
Theidea of random algorithm is to randomly assign the selected jobs to theavailable Virtual Machines (VM). The algorithm does not take intoconsiderations thestatusof the VM, which will either be under heavy or low load. Hence, this may resultin the selection of a VM under heavy load and the job requires a long waitingtime before service is obtained.
The complexity of this algorithm is quite lowas it does not need any overhead or preprocessing. Figure 1: Process of random algorithmSteps for RANDOMALGORITHM The algorithmIndex = random() *(NoVM – 1) (1)Where:index = The index tothe selected VMrandom() = Functionthat returns a random valuebetween 0 and 1NoVM = The totalnumber of available VMs Problems Thisattempt to load-balance can fail in two ways.First,the typical “random” partition of the address space among nodes is not completelybalanced. Some nodes end up with a larger portion of the addresses and thusreceivealarger portion of the randomly distributed items. Second, some applications maypreclude the randomization of data items’ addresses. For example, to supportrangesearching in a database application the items may need to be placed in a specificorder, or even at specific addresses, on the ring.
In such cases, we may findthe items unevenly distributed in address space, meaning that balancing theaddress space among nodes is not adequate to balance the distribution of itemsamong nodes. Tight bounds ofrandomized load balancingAsan application, we consider the following problem. Given a fully connectedgraph of n nodes, where each node needs to send and receive up to n messages,and in each round each node may send one message over each link, deliver allmessages as quickly as possible to their destinations. We give a simple androbust algorithm of time complexity O(log* n) for this task and provide a generalizationto the case where all nodes initially hold arbitrary sets of messages. A lesspractical algorithm terminates within asymptotically optimal O(1) rounds. Allthese bounds hold with high probability.Solution proposedHybridalgorithm.
TheHybrid algorithm as given in Figure 3.3 is a load balancing algorithm used bythe datacenter to distribute the received tasks efficiently over the virtualmachine under a normal workload by finding the best VM among the group of VMsto assign the load in heterogeneous of a processors power in cloud computingenvironment. The hybrid algorithm consists of both random and greedy algorithms;the random algorithm which randomly select a VM to process the received tasks,does not need complex computation to make a decision but it does not select thebest VM. On the other hand, Greedy algorithm selects the best VM to handle thereceived task, but the selectionprocessneeds some complex computation to find the best VM.
The hybrid algorithmconsiders the current resource information and the CPU capacity factor. The hybridalgorithm selects k nodes (VMs) randomly, and chooses the current load for eachVM selected. Then the hybrid algorithm will choose a VM that have least VMcurrent loads and return the VM ID to the Data center. The data center willassign the load to the selected VM and update the value of selected VM in the tableof current loads. Finally, when the VM finishes processing the request, it willinform the data center to update its current load value. TheHybrid Load balancing algorithm uses randomization and greedy, it distributesthe load over VMs to achieve efficient performance in heterogeneous cloudcomputing environment. The algorithm depends on current resource allocationcount.
Load balancing andhashingLoadbalancing uses a number of algorithms, called load balancing methods, todetermine how to distribute the load among the servers. When a Load balancer isconfigured to use the hash method, it computes a hash value then sends therequest to the server. Hash load balancing is similar to persistence based loadbalancing, ensuring that connections within existing user sessions areconsistently routed to the same back-end servers even when the list ofavailable servers is modified during the user’s session.Theload balancer computes two hash values using:Theback-end server IP Address and Port (X).
Oneof the incoming URL, Domain name, Destination IP, Source IP, Source &Destination IP, Source IP & Source Port, Call ID, Token (Y).Theload balancer computes a new hash value (Z) based on (X) and (Y).Thehash value (Z) is stored in cache.Theload balancer forwards the request to the server with highest hash value, byusing the value (Z) from the computed hash values. Subsequent requests with thesame hash value (cached) are sent to the same server.
Thefollowing example shows how a Load Balancer works using the hash method. Theload balancer delivers the request based on the value of Hash(Z) as follows:Server-1receives the first request.Ifserver-1 is down, the hash value is calculated again.
Theload balancer selects the server with the highest hash value, and forwards therequest.Note:If the load balancer fails to select a service by using a hash value, it usesthe least connections method to select the server.Whetherit’s load balancing XenApp Web Interface, iPhone/iPad resources, websites,linux servers, windows servers, e-commerce sites, or enterprise applications,NetScaler is the perfect choice. NetScaler, available as a network device or asa virtualized appliance, is a web application delivery appliance thataccelerates internal and externally-facing web application up to 5x, optimizesapplication availability through advanced L4-7 traffic management, increasessecurity with an integrated application firewall, and substantially lowerscosts by increasing web server efficiency. CitrixNetScaler is a comprehensive system deployed in front of web servers thatcombines high-speed load balancing and content switching with applicationacceleration, highly-efficient data compression, static and dynamic contentcaching, SSL acceleration, network optimization, application performancemonitoring, and robust application security. Available as a virtual machine,the NetScaler is perfect for load balancing virtual servers in the datacenter orin the cloud.