Getting to know the cloud: how dynamic traffic distribution methods work

In one of our past materials, we are they told about static methods of load balancing in the IaaS-provider cloud. Today, dynamic methods are on the way: "bee" and "ant" algorithms, as well as the approach of Biased Random Sampling.
 
 
Getting to know the cloud: how dynamic traffic distribution methods work

 
/Flickr / Quinn Dombrowski / CC BY-SA
 
 
Dynamic balancing methods, in contrast to static balancing, take into account in their work. current state of the whole system and respond to changes in it. Often information about the load of nodes is stored in the state table, from which the load balancing systems and draw information.
 
 

 
The dynamic load distribution is is performed. monitoring
 
 

Biased Random Sampling


 
To implement this approach, the network is represented by in the form of a virtual directed graph in which all servers are the vertices. At receipt request to perform any task, the load balancer assigns it to that node (node), which has a half-degree of approach equal to at least one.
 
 
When a node receives a task, the processor starts its execution and simultaneously signals a decrease in the number of available computing resources, decreasing the half-degree of the call. When the task is "solved", the node increments this indicator, reporting the release of resources.
 
 
Selection of the initial vertex for the task becomes randomly (hence random sampling); subsequent tasks are assigned to neighbors, which are also selected in random order. This method of load balancing is completely decentralized and therefore suitable for working in cloud networks. Including geographically distributed.
 
 
Scientists from Liverpool have established that Biased Random Sampling, which additionally takes into account the geographical distribution of nodes in the network, allows to reduce latency in data transmission by 22%. In the test with 512 nodes located within a radius of thousands of kilometers, the average delay was approximately 70 ms (in an experiment with a network that did not take into account the geographical distribution of nodes, this figure was 92.5 ms).
 
 

"Ant" optimization algorithm (Ant colony optimization)


 
For the first time this concept was in the early nineties. She draws inspiration from the ants' behavior. An ant is always able to find a way from a food source to an anthill, even if the habitual way was "blocked." For this, these insects mark the route with special pheromones. It is believed that the stronger this "smell", the closer the source of food is.
 
 
In the context of load balancing in telecommunication networks, it looks like this. The network is represented in the form of a graph, and from all possible nodes the main one, which has the largest number of neighbors, is selected. The switching stations are mapped to the nodes of the graph, and the communication lines between them are in the edges.
 
 
Each node contains a "pheromone table", which contains data on the resources used and available capacities: the amount of memory, the number of processors, etc. Periodically, from each node run ants that are sent to random nodes-receivers. "Insects" move between nodes, guided by a pheromone table. This table is updated every time it is accessed by an ant.
 
 
Ants have an age equal to the distance traveled. Also, the ants linger in the knots, full of challenges. Those insects that choose a short and less loaded path affect the probability of selecting this route by subsequent ants to a greater extent than the ants choosing the worst along the length and loading path.
 
 
This is due to the fact that the first ants fall into the node-receiver and have a smaller age. New requests are sent on the shortest unloaded routes. This allows you to balance resources by unloading nodes on "dense" directions in the network.
 
 
One of the variations of this algorithm is uses framework for P2P-applications Anthill. This system is a self-organizing network of connected "anthill chambers" - nodes that can perform calculations and process data.
 
 

 
Structure of the anthill network
 
 
When a node receives a request from an application, it launches an autonomous agent, the ant, which must complete the task. It moves across the network from node to node until it completes the request. Moving, the ants "carry" information about the request, the result and other metadata with them.
 
 
Ants do not communicate directly with each other, instead they leave the information necessary for solving the problem from resource managers located in the nodes they visit. For example, an ant that implements a search service can leave routing information so that it helps other ants to make their way to the nodes that contain the data they need. A similar form of indirect communication is also used by real ants - this is called stigmergia .
 
 

The "bee" algorithm of optimization (honeybee foraging)


 
The first articles describing the method of the bee swarm were published in 2005. It is based on modeling the behavior of bees when searching for nectar. In the hives there are so-called scout bees, which are looking for glades with flowers. When they find a food source, they return to the hive to tell others about it with the help of a special "wagging dance".
 
 
 
/Flickr / Irregular Blog - Daedalus / CC BY-SA
 
 
With this dance, the bee tells you how good the nectar is in the clearing and how far away it is. After that, her beaks-foragers respond to her call, which fly behind the scout, collect the "harvest" and return to the hive with "prey". Then, the foraging bee can do one of the following: become an unoccupied forager, leaving the current source of nectar, continue collecting it yourself, or call several other unoccupied bees with them to help.
 
 
This model is used for load balancing as follows. First thing is is calculated. the current load on virtual machines and determines their state (balanced, unloaded, overloaded), depending on the thresholds they set. If the load on the VM is small, then all new tasks will be directed to it.
 
 
In the event that the system has overloaded virtual machines, each of them can take the role of scout or forager. When processing a request, the virtual server calculates a certain value that is an analog of the "quality" of the glade with the colors that bee dance demonstrates. One way to estimate this value can be the time that the CPU will spend on its execution. Then the server "advertises" this task to the entire system, as if posting it on the bulletin board - thus the server assumes the role of scout. Other servers can view this bulletin board and process requests there, becoming foragers.
 
 
Other materials from the corporate blog 1cloud:

 
 
Load balancing: difficulties of forecasting
 
Data Security in the Cloud: Threats and Ways of Protection
 
What is the difference between the network and the subnet: where the boundary is
 
How to create a computer class in the cloud
 
+ 0 -

Comments 1

Offline
Stella Flood
Stella Flood 1 August 2018 10:50
With write of these words on here you make easy for those people who want to bring traffic on their platforms. Many students of different classes like to hire assignment services rating online for achievement of best grades.

Add comment