April 15, 2018 at 11:57Introducing the Cloud: How Dynamic Traffic Distribution Methods Work
In one of our past materials, we talked about static methods of load balancing in the cloud of an IaaS provider. Today, dynamic methods are next in turn: “bee” and “ant” algorithms, as well as the Biased Random Sampling approach.
/ Flickr / Quinn Dombrowski / CC BY-SA
Dynamic balancing methods, in contrast to static ones, take into account the current state of the entire system and react to changes in it. Often, information about the load of nodes is stored in a state table from which load balancing systems draw information.
Dynamic load balancing - performed monitoring
To implement this approach, the network is represented in the form of a virtual directed graph in which all servers are vertices. Upon receipt of a request to perform a task, the load balancer assigns it to that vertex (node) that has a semi-degree of approach equal to at least one.
When the node receives the task, the processor begins its execution and simultaneously signals a decrease in the number of available computing resources, decreasing the semi-degree of approach. When the task is "solved", the node increments this indicator, reporting the release of resources.
The choice of the initial vertex for the task is donerandomly (hence random sampling); subsequent tasks are assigned to neighboring nodes, which are also randomly selected. This load balancing method is completely decentralized and therefore suitable for use in cloud networks. Including geographically distributed.
Scientists from Liverpool found that Biased Random Sampling, which additionally takes into account the geographical distribution of nodes in the network, can reduce latency in data transmission by 22%. In the test with 512 nodes located within a thousand km radius, 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).
This concept was first introduced in the early nineties. She draws inspiration from the behavior of ants. An ant is always able to find a path from a food source to an ant hill, even if the habitual path was “blocked”. For this, these insects mark the route with special pheromones. It is believed that the stronger this “smell”, the closer the food source is.
In the context of load balancing in telecommunication networks, this is as follows. The network is represented in the form of a graph, and from all possible nodes the main one is selected, which has the largest number of neighbors. Switching stations are displayed in the nodes of the graph, and communication lines between them - in the edges.
Each node contains a “pheromone table”, which contains data on used resources and available capacities: amount of memory, number of processors, etc. Periodically ants are launched from each node and sent to random receiver nodes. "Insects" move between nodes, guided by a pheromone table. This table is updated every time an ant accesses it.
Ants have an age equal to the length of the path traveled. Ants also linger in nodes overflowing with calls. Those insects that choose a shorter and less busy path affect the likelihood of choosing this route by subsequent ants to a greater extent than ants that choose the worst path in length and load.
This is due to the fact that the first ants get into the receiving node earlier and are of less age. New requests are sent along the shortest unloaded routes. This allows you to balance resources by unloading nodes in dense directions in the network.
One of the variations of this algorithm uses the framework for P2P Anthill applications. This system is a self-organizing network of connected “anthill chambers” - nodes capable of performing calculations and processing data.
The structure of the anthill network
When a node receives a request from an application, it launches a stand-alone agent - an ant, which must complete the task. It moves across the network from node to node until it completes the request. Moving, the ants "carry" with them information about the request, the result and other metadata.
Ants do not communicate with each other directly, instead they leave the information necessary for solving the problem with the resource managers located in the nodes they visit. For example, an ant that implements a search service can leave routing information in this way, which would help other ants make their way to nodes containing the data they need. A similar form of indirect communication is also used by real ants - this is called stigmergia..
The first articles describing the bee swarm method 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 who are looking for glades with flowers. When they find a source of food, 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 reports how good the nectar is in the clearing and how far it is. After that, forager bees respond to her call, who fly after the scout, collect the “harvest” and return to the hive with the “prey”. Then the forager bee can do one of the following: become an unoccupied forager, leaving the current source of nectar, continue to collect it on its own or call along with several other unoccupied bees to help.
This model is used to balance the load as follows. First of all , the current load on virtual machines is calculated and their state (balanced, unloaded, overloaded) is determined depending on the threshold values set by them. If the load on the VM is small, then all new tasks will be directed to it.
If the system has overloaded virtual machines, each of them can assume the role of scout or forager. Processing the request, the virtual server calculates a certain value, which is an analogue of the "quality" of the meadow with flowers, which shows a bee dance. One of the options for evaluating this value may be the time that the CPU takes to complete it. Then the server “advertises” this task to the entire system, as if posting it on the bulletin board - in this way the server assumes the role of scout. Other servers can view this bulletin board and process the requests made there, becoming foragers.
Dynamic load balancing - performed monitoring
Biased random sampling
To implement this approach, the network is represented in the form of a virtual directed graph in which all servers are vertices. Upon receipt of a request to perform a task, the load balancer assigns it to that vertex (node) that has a semi-degree of approach equal to at least one.
When the node receives the task, the processor begins its execution and simultaneously signals a decrease in the number of available computing resources, decreasing the semi-degree of approach. When the task is "solved", the node increments this indicator, reporting the release of resources.
The choice of the initial vertex for the task is donerandomly (hence random sampling); subsequent tasks are assigned to neighboring nodes, which are also randomly selected. This load balancing method is completely decentralized and therefore suitable for use in cloud networks. Including geographically distributed.
Scientists from Liverpool found that Biased Random Sampling, which additionally takes into account the geographical distribution of nodes in the network, can reduce latency in data transmission by 22%. In the test with 512 nodes located within a thousand km radius, 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)
This concept was first introduced in the early nineties. She draws inspiration from the behavior of ants. An ant is always able to find a path from a food source to an ant hill, even if the habitual path was “blocked”. For this, these insects mark the route with special pheromones. It is believed that the stronger this “smell”, the closer the food source is.
In the context of load balancing in telecommunication networks, this is as follows. The network is represented in the form of a graph, and from all possible nodes the main one is selected, which has the largest number of neighbors. Switching stations are displayed in the nodes of the graph, and communication lines between them - in the edges.
Each node contains a “pheromone table”, which contains data on used resources and available capacities: amount of memory, number of processors, etc. Periodically ants are launched from each node and sent to random receiver nodes. "Insects" move between nodes, guided by a pheromone table. This table is updated every time an ant accesses it.
Ants have an age equal to the length of the path traveled. Ants also linger in nodes overflowing with calls. Those insects that choose a shorter and less busy path affect the likelihood of choosing this route by subsequent ants to a greater extent than ants that choose the worst path in length and load.
This is due to the fact that the first ants get into the receiving node earlier and are of less age. New requests are sent along the shortest unloaded routes. This allows you to balance resources by unloading nodes in dense directions in the network.
One of the variations of this algorithm uses the framework for P2P Anthill applications. This system is a self-organizing network of connected “anthill chambers” - nodes capable of performing calculations and processing data.
The structure of the anthill network
When a node receives a request from an application, it launches a stand-alone agent - an ant, which must complete the task. It moves across the network from node to node until it completes the request. Moving, the ants "carry" with them information about the request, the result and other metadata.
Ants do not communicate with each other directly, instead they leave the information necessary for solving the problem with the resource managers located in the nodes they visit. For example, an ant that implements a search service can leave routing information in this way, which would help other ants make their way to nodes containing the data they need. A similar form of indirect communication is also used by real ants - this is called stigmergia..
"Bee" optimization algorithm (honeybee foraging)
The first articles describing the bee swarm method 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 who are looking for glades with flowers. When they find a source of food, 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 reports how good the nectar is in the clearing and how far it is. After that, forager bees respond to her call, who fly after the scout, collect the “harvest” and return to the hive with the “prey”. Then the forager bee can do one of the following: become an unoccupied forager, leaving the current source of nectar, continue to collect it on its own or call along with several other unoccupied bees to help.
This model is used to balance the load as follows. First of all , the current load on virtual machines is calculated and their state (balanced, unloaded, overloaded) is determined depending on the threshold values set by them. If the load on the VM is small, then all new tasks will be directed to it.
If the system has overloaded virtual machines, each of them can assume the role of scout or forager. Processing the request, the virtual server calculates a certain value, which is an analogue of the "quality" of the meadow with flowers, which shows a bee dance. One of the options for evaluating this value may be the time that the CPU takes to complete it. Then the server “advertises” this task to the entire system, as if posting it on the bulletin board - in this way the server assumes the role of scout. Other servers can view this bulletin board and process the requests made there, becoming foragers.