instances. Two types of VM instances are considered by this
research in the SOVMPO problem. The communication cost
and utility rate are calculated from these VM role instances.
We assume that a service is preceded by a web role and four
worker role instances.
2.3 Related works
In the existing literature some researchers focused on placing
VMs in different data center architectures [26, 27, 29]while
others investigated the VM placement in distinct orientations
[30, 31].
The works most related to ours are [26, 27, 30, 31]. In [26,
27],thethree-tierarchitectureindatacenterisalsoconsidered.
However, the researchers in [26] surveyed the influences of
TCP Incast and congestion notification unlike the communi-
cation cost of inbound and outbound in our work. The traffic
characteristic is not covered in [26] but we eliminate the costs
from the outbound communication, which minimizes the traf-
fic loads within different LANs. Although the data center
architecture is con sidered, two parts differ entiate [27]our
work. First, in spite of the considered architecture, the VL2
[32], fat-tree [26] and BCube [33] architecture are adopted in
[27], but we follow the three-tier architecture of traditional
data center networks in this work. Second, the proposed work
in [27] is based on traffic-aware VM placement while in our
work the proposed algorithms are based on service-oriented
VM placement. In [30, 31] both researc h es are bas ed on
application-aware viz. AppAware. Althou gh the propo sed
scheme in [30] is based on the graph theoretical technique as
our work, the authors focus on the appli cation-aware VM
migration unlike the data center placement problem in our
work. The VM demand, physical machine capacity and com-
munication are considered in [30] which is similar to our
work, but the authors investigated the communication fre-
quency performance unlike the communication cost in this
paper. Finally, the distinct orientation towards VM placement
is considered in [31], but some parts are still different. First of
all, the AppAware orientation is completely differentiated
from our service-oriented VM placement algorithms. The au-
thors propose an application-aware VM placement algorithm
based on the convex optimization theory unlike the proposed
algorithms in this paper based on ILP model and graph theo-
retical technique. We propose a novel VM placement scheme
based on service and investigate a vital issue minimizing the
inbound and outbound communication costs which are fre-
quently neglected in other studies.
3 Proposed algorithms
3.1 Problem definition
The virtual machine optimization problem for service-
oriented cloud networks is formulated based on integer linear
programming (ILP). The definitions of variables used in
SOVMPO are listed in Table 1.
In the cloud infrastructure a tree structure is used to connect
the hardware which includes the routers, middle-tier aggrega-
tions, switches and servers. The same structure is also applied
to the virtual machines within the physical servers. Therefore,
we let V be a set of nodes and E be a set of edges between
nodes. Given a graph G=(V,E), where V=V
1
∪V
2
and E=E
1
∪
E
2
. It can be easily shown that V
1
∩V
2
=∅ and E
1
∩E
2
=∅.
Assume that V
1
={z
1
,…,z
k
}with|V
1
|=k,andV
2
={q
1
,…,q
s
}
with |V
2
|=s.
The nodes in V
1
are the equipment in cloud infrastructure,
which can be core routers, middle-tier aggregations, edg e
Core Router
Middle-tier Aggregation
Edge Switch
Physical Server
Fig. 1 Data center network infrastructure
558 Mobile Netw Appl (2015) 20:556–566