Cloud computing as a powerful economic stimulus widely being adopted by many companies. However, the management of cloud infrastructure is a challenging task. Reliability, security, quality of service, and cost-efficiency are important issues in these systems. They require resource optimization at multiple layers of the infrastructure and applications. The complexity of cloud computing systems makes infeasible the optimal resource allocation, especially in presence of uncertainty of very dynamic and unpredictable environment. Hence, load balancing algorithms are a fundamental part of the research in cloud computing. We formulate the problem of load balancing in distributed computer environments and review several algorithms. The goal is to understand the main characteristics of dynamic load balancing algorithms and how they can be adapted for the domain of VoIP computations on hybrid clouds. We conclude by showing how none of these works directly addresses the problem space of the considered problem, but do provide a valuable basis for our work.
and storage to deploy services. (Scalability) The user can increase or decrease resources (storage, CPUs, memory, etc.) at any time, he only pays for what he is really used. (Mobility) The data can be accessed anytime anywhere, the user only needs a device with internet connection (laptop, smartphone, etc.). (Virtualization) It is a technology used to share resources. It makes a single physical resource appear as many individually separate virtual resources. It allows the use of the server capacity effectively, reducing unused CPU cycles, and minimizing wasted energy.
The management of the large-scale cloud infrastructure is a challenge. Resource management for clouds has been subject to research and development for many years. Here, we discuss different aspects related with our study.
Load balancing is a mechanism to improve the overall performance of the system by distribution
of the workload between the nodes. By reducing idle times, providers can improve the profit and
achieve a higher user satisfaction. Proper load balancing can help on utilizing the available resources,
thereby, minimizing the resource consumption [
Quality of service (QoS). In cloud computing, providers need to ensure that sufficient amount of
resources are provisioned to ensure that QoS requirements of cloud service consumers such as
deadline, response time, and budget constraints are met [
These SLAs contain the list of services, metrics, responsibilities of the provider and auditing mechanisms. Any violation will lead to a penalty. Several ways exist to provide QoS: scheduling, admission control, traffic control, dynamic resource provisioning, etc.
Energy management. Energy consumption is determined by hardware efficiency, resource
management system deployed on the infrastructure, and the efficiency of applications running on the
system. The efficiency is very important due to its impacts to users in terms of resource usage costs,
which are typically determined by the total cost of ownership incurred by a resource provider [
The paper is structured as follow. The next section presents several important issues of dynamic load balancing algorithms. Section 3 provides details of the Internet telephony and voice over IP telephony (VoIP). Section 4 describes VoIP provider model and quality of service (QoS). Section 5 presents more formal definition (jobs, cloud infrastructure and criteria). Section 5 gives a brief overview of the load balancing algorithms in cloud computer environments. Section 6 presents our load balancing algorithm. Section 7 concludes the paper.
Load balancing is a job distribution decision-making process used in many production systems
and computing. It is widely known as a technique for the efficient utilization of resources, and it can
be implemented with hardware and software support. Jobs arrival rate, communication delay, the
variability of the job parameters, and other factors affect the performance of the systems, to deal with such
complex factors it is essential to design efficient and scalable load balancing algorithms. It helps in
implementing fail-over, scalability, avoiding bottlenecks, over-provisioning, reducing response time,
reducing energy consumption, etc. [
Load balancing of services, computational jobs, virtual machines, virtual storages, database requests, and VoIP traffic on the network are identified as a major concern for the efficient use of cloud computing.
The development of an effective dynamic load balancing algorithm involves many important
issues: load estimation, load levels comparison, performance indices, system stability, amount of
information exchanged among nodes, job resource requirements estimation, job selection for transfer,
remote nodes selection, etc. [
Storage replications. Full replication of data increases the storage and communication overhead. Partial replication saves information in different nodes (with overlap), so that, the utilization, fault tolerance and availability of data are increased.
Virtual machine migrations. A heavily loaded node can migrate its virtual machines (VM) to reduce the overload, but determinate which VMs have to be moved, the destination node, and the profit of the migration are questions difficult to answer.
The Internet telephony (VoIP–Voice over Internet Protocol) refers to the provisioning of communication services over the Internet, rather than via the traditional telephone network. VoIP services significantly reduce calling rates, leading VoIP vendors continue offering extraordinary service using modern cloud technology. Selection of a cloud based VoIP further reduces resource costs, adds new features and capabilities, provides easier implementations, uniform deployments, and integrates services that are dynamically scalable.
To deploy and manage effective telephony tools via clouds a variety of factors need to be improved. The most important one is the utilization of the infrastructure. (b)
Fig. 3. Data centers in clouds (a) and the cloud federation (b).
However, it has several unsolved problems. To optimize the overall system performance, a processor load of the voice signal processing over IP (jobs) should be balanced. The overload of a processor reduces the quality of the call. A similar problem could happen with the network capability. Further, the processor idle time increases the useless expenses of the provider.
Load-balancing maximizes VoIP performance by keeping processor idle time and interprocessor communication overhead as low as possible. To minimize the overall computation time, all processors should contain the same amount of computational work.
It is necessary to design a multi-level distributed VoIP load balancer to improve the local load imbalance in data centers, and new techniques to scale on federation of data centers (Figure 4).
The most important cause of load imbalance in VoIP is the dynamic nature of the problem over time (in both computational and communication costs). Other causes may include the interference from other users in time-sharing mode, the migration process, the time arrival, variability on the utilization process, etc.
Most load balancing algorithms focus on deterministic environments assuming knowledge of the user jobs and system parameters. In general, it is impossible to get exact knowledge about the system. Parameters like processor speed, number of available processors, and actual bandwidth are changing over the time. However, load balancing algorithms should search how to improve resources and ensure Quality of Service (QoS).
An important factor of VoIP on cloud computing is the rental time of the infrastructure. The VoIP providers rent the resources during a time interval, this factor affects the incoming of the providers and even can increase the cost of the service, for this reason is important to consider when a new resources are rented and the rented time interval.
Fig. 4 shows an example of VMs that provide VoIP services. This example consider the load balancing of the utilization on the VMs. In Figure 5a, the VoIP provider needs three VMs to deal with the load of time during the day. starts its execution when cannot process all calls in the system. During the rental time of , its utilization is low, in this case the provider has to paid for the rent of three VMs. Figure 5b shows the same example, but in this case the load balancer distributes the arrival calls between and . When rental time is almost completed, a consolidation technique is used to reduce utilization (number of call running on ). This approach helps providers to reduce the number of VMs for calls processing. (a) Rent of 3 virtual machines. (b) Rent of 2 virtual machines.
VM 2 M V tfo VM 1 n u o m A
Time-interval
VM 1
Overflow of call on the VM
VoIP providers also have to guarantee QoS to the users. Quality of service requirements for VoIP are very important but several factor can affect the quality of calls. The quality degradation is determined by the transit of the packets across the Internet, queuing delays at the routers, packet travel time from source to destination, jitter (deviations of the packet inter-arrivals), packet loss, call set-up time, and call tear-down time, etc. Processor utilization of 100% provides the best expected performance. However, with increasing number of call, hence utilization, CPU cannot be able to handle the stress anymore and jitters and broken audio symptoms will appear (Fig. 5).
M V f tno VM1 u o m A
VM 2 Time-interval
Fig. 6 shows an example of VM rental to provide VoIP services with QoS. In Figure 6a, the VoIP provider needs three VMs to deal with the load during a day. In this case, the QoS is not considered as independent optimization criteria. The utilization of is above the utilization threshold. Figure 6b shows the same example. However, load balancing guarantees the QoS by maintaining the VMs utilization under the utilization threshold. Moreover, it reduces the amount of VMs to process calls.
This model allows providers to deploy services in different countries by renting infrastructure in public or/and private clouds providers.
(a) Rent of 3 virtual machines without QoS.
(b) Rent of 3 virtual machines with QoS.
VM2 Overflow of utilization to ensure
QoS
We address load balancing problem in the hierarchical federated cloud environment, where clouds of different providers collaborate to be able to fulfill requests during peak demands. We assume heterogeneous clouds and data centers with different number of cores, execution speed, energy efficiency, amount of memory, bandwidth, etc.
Let us consider cloud that consists of nodes (data centers, sites) . Each node , for all , consists of servers (blades, boards) and processors per board. We assume that processors in the data center are identical and have the same number of cores. Let be the number of identical cores of one processor in .
We denote the total number of cores belonging to the data center by , and belonging to all data centers of the cloud by .
The processor of data center is described by a tuple { , , , , }, where is a measure of instruction execution speed (MIPS), is the amount of memory (MB), is the available bandwidth (Mbps), and is energy efficiency (MIPS per watt).We assume that data centers have enough resources to execute any job but their resources are limited.
A data center contains a set of routers and switches that transport traffic between the servers and to the outside world. They are characterized by the amount of traffic flowing through it (Mbps). A switch connects a redistribution point or computational nodes. The connections of the processors are static but their utilization change, overload can occur due to a large amount of I/O being pushed through it. The interconnection network architecture is Three-tier data center architectures that include: access, aggregation, and core layers. The interconnection between clouds will be done through public Internet.
In addition, to satisfy requests during the peak demands that exceed the capacity of the cloud , it collaborates with external independent clouds (sites) .
We consider n independent jobs that must be scheduled on federation of clouds. The job (call) is described by a tuple { } that consist of: its release time , the duration of the job and the contribution to the processor utilization of the job j. The release time of a job is not available before the job is submitted, the duration of the job is unknown until the job has completed its execution, and contribution is a constant for a given job. Due to the virtualization technique and resource sharing, the resources are constantly changing. A job can be allocated to one cloud only. Jobs submitted to the one cloud can be migrated to another one. is defined as a set of indexes { } of data
The admissible set of data centers for a job centers that can be used for migration of the job.
In this paper, two criteria are considered for the model: the billing hours for VMs to provide a service, and their utilization to increase quality of service.
In order to optimize VoIP cloud solutions, we use metrics that are useful for systems with VMs. They have to allow the provider to measure the cost of the system in terms of number of demanded VMs and time of their using. These metrics enable us to compare different load balancing policies: total VM rented ( ) (number of billing hours) and utilization of VM ( ).
allows providers to measure the cost of the system in terms of parameters that helps him to establish utility margins.
In general, QoS standards for VoIP traffic are set for voice. One of the possible generalizations of the voice quality is processor utilization. Each codec provides a certain quality of speech only if processor utilization is low enough in order to ensure QoS. If the number of calls is increased, and utilization is close to 100%, CPU cannot be able to handle the stress anymore and reduced audio quality will appear. Hence, we use as a way of measure the user satisfaction for the service.
Previously, we briefly overview the load balancing algorithms in different computer environments
[
HBB -LB - Honeybee Foraging Behavior [
DT - PALB - Power Aware Load Balancing [
TBSLB-PSO - Particle Swarm Optimization [
LBS-BF - Load Balance Scheduling Based on firefly [
ancing algorithm for cloud environment. The load balancer mechanism comprises of three agents: Load agent (LA), Channel agent (CA) and Migration agent (MA). LA is a static agent and it controls information policy and maintains all detail of a datacenter, it most important job is to calculate the load on every available VM. CA is a static agent, it controls the transfer policy, selection policy and location policy. Finally, MA is an ant (special category of mobile agents), it will move to other datacenters and communicate to enquire the status of VMs.
cloud computing. It uses a binary representation for the chromosomes, a random single point crossover, and a mutation with probability of 0.05. This algorithm considers an estimate of penalty (delay cost), the amount of money that cloud service provider needs to pay to customer when job finishing time being more than the deadline advertised by the service provider HBB-LB DT-PALB TBSLB-PSO LBS-BF A2LB GA FFA-DLB
Task VM
Task Task
ting [
Campos and Scherson proposed a dynamic distributed load balancing algorithm named Rate of
Change (RoC-LB) [
To define WHEN load balancing should be started the algorithm considers three thresholds: upper bound, lower bound, and critical bound. If the load is larger than then the Bal is considered as a source of the load and can satisfy job requests. If the predicted load is less than the Bal is considered as a sink. When the current load is between these two bounds, the Bal is in the neutral state. However, if the load or the predicted load fall below , the Bal immediately initiates a request for a load.
We extend this algorithm and design a VM-Aware Adaptive Rate of Change (VMA-AdRoC)
algorithm that is based on an adaptive decision policy and virtual machine utilization optimization.
Adaptability is essential for the efficient use of cloud infrastructure. Clouds differ from previous
computing environments in the way that they introduce a continuous uncertainty into the computational
process. The uncertainty becomes the main feature of the cloud computing and the principal difficulty
of the efficient resource management [
There are several major sources of uncertainty: dynamic elasticity, dynamic performance changing, virtualization, loosely coupling application to the infrastructure, among many others. A workload in such an environment is not predictable and can be changed dramatically. It is impossible to get exact knowledge about the system. Parameters such as an effective processor speed, number of available processors, and actual bandwidth are changing over the time.
VMA-AdRoC takes into account these uncertainties. The accuracy of each balancing decision depends on the actual cloud characteristics at the moment of balancing. Cloud parameters are changing over time and balancing parameters should be adapted to these changes. This dynamic and adaptive approach can cope with different workloads, and cloud properties. To adjust , , and , the past information within a given time interval can be analyzed to determine an appropriate parameters. This interval should be set according to the dynamics of the system.
Let be the utilization of ith Bal at time . Let be the utilization change during sample interval = . We named it utilization change speed or utilization consumption speed. The sampling time interval is an adaptive parameter; finer sampling allows detecting the need to balance the system faster, but it generates a larger communication overhead.
Bal uses as a predictor of the future utilization. It can be also used to estimate the number of sampling intervals to reach an idle state. Let be the response delay of at time . It is an adaptive parameter, and it is defined as the time it takes between the initiation of a load request and the reception of load. If the time to reach idle state is less than , then Bal must initiate a migration request. Let us note that and are independent from others Bals.
Fig. 7 shows possible load balancing scenarios. Solid line shows real utilization, dashed lines are predicted utilization.
At time the Bal immediately initiates a request for load regardless of the predicted future utilization based upon the estimation value or it initializes migration of the load to other VM. Estimation on is under but Bal cannot initiates a request because the request at is not arrived, a new request only can be generate at . In VMA-AdRoC, unlike RoC-LB, if the utilization is above than then the Bal sends jobs to the sinks.
To define WHERE a load is requested from or send to, each Bal keeps two lists. The sink list records Bals that previously needed jobs, and source list enrolls Bals that previously offered jobs. Bal that initiates a request is considered to be a sink. A sink selects a Bal from its source list for a load request, and sends a requesting message. The source can accept the request or broadcast the request to other Bals from its own source list. Bal does not send several load requests at the same time. It has to wait an answer for the first request until it sends another message. The result of this message is the load coming from other Bal or the request comes back as unfulfilled.
In our algorithm, each element of the source and sink lists includes not only IP address like in RoC-LB, but utilization , of the corresponding Bal. This information is not accurate and updated dynamically. In our case, choosing the sink/source node is a two-parameter problem. In the future work, we consider also requested load , , , answer time of the request , admissibility of Bals, etc. The goal is to choose the most adequate compromise solution.
In this paper, we formulate and discuss load balancing problem addressing VoIP in cloud computing federation. We define models for VoIP load balancing. We overview the last advances of load balancing in distributed computer environments to understand the main characteristics and requirements of load balancing algorithms. We show that none of these works directly addresses the problem space of the considered problem, but do provide a valuable basis for our study.
In real clouds, the load balancing bounds can be dynamically adjusted to cope with the dynamic workload situation. To this end, the past workload must be analyzed for a certain time interval to determine an appropriate lower and upper bounds. The time interval should be set according to workload characteristics, communication delays, and cloud configurations. While the scope of this work is the introduction of the adaptive dynamic distributed load balancing algorithm, in future work, we also intend to evaluate the practical performance of the proposed strategy and their derivatives to assess its actual efficiency and effectiveness. To this end, we plan simulations using real VoIP traces and corresponding VoIP cloud configurations. Further, we will compare our approach with other existing strategies which are typically based on round robin approach.