OPL using CPLEX Optimizer help

Dear Sir/Madam
I am working on virtual network mapping modelling Using IBM ILOG Optimization ? Mathematical Programming OPL using CPLEX Optimizer.
If you have experience with OPL using CPLEX Optimizer by IBM please contact me.
All the optimazation equations and constraint are ready. I need some one to help code it using CPLEX. 

My work is Virtual network mapping , the Mixed integer programming (objective and constraints are ready) i need to code it in CPLEX so it can be solved. 
In the attached file you find the base paper for the work, the objective function and constraints well explained. 
my work is similar to the work in this paper . 
If you are able to help please let me know?
Thanks and regards

On the Optimal Allocation of Virtual
Resources in Cloud Computing Networks

Chrysa Papagianni, Aris Leivadeas, Symeon Papavassiliou,

Vasilis Maglaris, Cristina Cervelló-Pastor, and �Alvaro Monje

Abstract—Cloud computing builds upon advances on virtualization and distributed computing to support cost-efficient usage of

computing resources, emphasizing on resource scalability and on demand services. Moving away from traditional data-center oriented

models, distributed clouds extend over a loosely coupled federated substrate, offering enhanced communication and computational

services to target end-users with quality of service (QoS) requirements, as dictated by the future Internet vision. Toward facilitating the

efficient realization of such networked computing environments, computing and networking resources need to be jointly treated and

optimized. This requires delivery of user-driven sets of virtual resources, dynamically allocated to actual substrate resources within

networked clouds, creating the need to revisit resource mapping algorithms and tailor them to a composite virtual resource mapping

problem. In this paper, toward providing a unified resource allocation framework for networked clouds, we first formulate the optimal

networked cloud mapping problem as a mixed integer programming (MIP) problem, indicating objectives related to cost efficiency of

the resource mapping procedure, while abiding by user requests for QoS-aware virtual resources. We subsequently propose a method

for the efficient mapping of resource requests onto a shared substrate interconnecting various islands of computing resources, and

adopt a heuristic methodology to address the problem. The efficiency of the proposed approach is illustrated in a simulation/emulation

environment, that allows for a flexible, structured, and comparative performance evaluation. We conclude by outlining a proof-of-

concept realization of our proposed schema, mounted over the European future Internet test-bed FEDERICA, a resource virtualization

platform augmented with network and computing facilities.

Index Terms—Federated infrastructures, resource allocation, resource mapping, virtualization, cloud computing, quality of service

Ç

1 INTRODUCTION

CLOUD computing promises reliable services deliveredthrough next generation data centers that are built on
compute and storage virtualization technologies. According
to Buyya et al., [1] “a cloud is a type of parallel and distributed
system consisting of a collection of interconnected and virtualized
computers that are dynamically provisioned and presented as one
or more unified computing resources based on service-level
agreements established through negotiation between the service
provider and the consumers” and accessible as a composable
service via web 2.0 technologies.

Therefore, with respect to cloud computing there exist
the “as a service” definitions, which include software as a
service (SaaS), infrastructure as a service (IaaS), and plat-
form as a service (PaaS). Each of these has a very different
business value proposition. However, despite of the model
adopted and followed, ultimately the goal of cloud comput-
ing is to create a fluid pool of virtual resources across
computers, servers, and data centers that enable users to
access stored data and applications on an as-needed basis.

In distributed computing environments, up to 85 percent
of computing capacity remains idle [2]. Cloud IaaS emerged
as a solution providing immediate and on demand access to
computing resources with significant cost savings for the
users. The same need for cost efficiency however applies
also to the cloud IaaS providers. Cloud providers try to take
advantage of the cloud’s elastic service provisioning model,
by utilizing solely the needed capacity to satisfy targeted
end-user quality of service (QoS) at any given time. In such
an environment, the probability of all embedded requests in
the cloud utilizing their maximal capacity requirements
simultaneously is low [3]. Therefore, the capacity of
physical resources can be multiplexed among requested
resources allowing us to accommodate more requests [4].
The term thin provisioning is used to differentiate from the
established overprovisioning methodology that plans capa-
city for peak workloads [3].

Moreover, in future Internet (FI) vision, where Internet
connection of objects and federation of infrastructures
become of high importance, the cloud involves two
different key players: cloud computing and networking.
For many cloud computing applications, network perfor-
mance will be the key to cloud computing performance and
its subsequent adoption. QoS delivery in the cloud is
intrinsically integrated with the network, its infrastructure,
and capacity. Therefore, the convergence between cloud
computing and networking is becoming more a require-
ment than a desire, motivating and driving the creation of
networked cloud paradigm.

Toward facilitating the efficient realization of this
emerging paradigm, traditional cloud computing resources
and networking related resources need to be jointly treated

1060 IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 6, JUNE 2013

. C. Papagianni, A. Leivadeas, S. Papavassiliou, and V. Maglaris are with
the Division of Communication, Electronic and Information Engineering,
School of Electrical and Computer Engineering, National Technical
University of Athens, Iroon Polytechniou 9, Athens 15780, Greece.
E-mail: chrisap@noc.ntua.gr,
{arisleiv,papavass,maglaris}@netmode.ntua.gr

. C. Cervelló-Pastor and �A. Monje are with the Department of Telematics
Engineering, Universitat Politècnica de Catalunya, Castelldefels 08860,
Barcelona, Spain. E-mail: {cristina, alvaro.monje}@entel.upc.edu.

Manuscript received 22 Apr. 2011; revised 6 Dec. 2012; accepted 20 Jan. 2013;
published online 14 Feb. 2013.
For information on obtaining reprints of this article, please send e-mail to:
tc@computer.org, and reference IEEECS Log Number tcsi-2011-04-0260.
Digital Object Identifier no. 10.1109/TC.2013.31.

0018-9340/13/$31.00 � 2013 IEEE Published by the IEEE Computer Society

and optimized. Therefore, one needs to consider the
dynamic provisioning, configuration, reconfiguration, and
optimization of both computing resources (e.g., servers) as
well as networking resources (e.g., bandwidth pipes
enabling interconnectivity though network infrastructure
operating either seamlessly or providing fully reconfigur-
able network abstractions via appropriate virtualization
models). Moreover, functional and nonfunctional character-
istics of these resources need to be also taken into account
[6]. Functional parameters define characteristics and prop-
erties of computing/networking resources, for example,
operating system, supported virtualization environment,
and so on, while nonfunctional parameters specify criteria
and constraints of the various resources, e.g., maximum
number of interfaces for each node, maximum disk space,
and so on. Application QoS in this networked cloud
environment is directly linked to the provisioning model
adopted for computational resources and networking
performance. Networking performance related metrics can
be further viewed as objectives that need to be optimized
and/or constraints that need to be satisfied. For instance,
one feasible way to reduce delay along a communication
path is by minimizing transit “hops”.

1.1 Paper Contributions and Structure

Promoting a unified management and control framework
for delivering efficiently cloud IaaS, we propose a method
for efficient mapping of user requests for virtual resources
(denoted as virtual network requests) onto a shared
substrate interconnecting previously isolated islands of
computing resources. The problem essentially amounts to
solving optimally the real-time problem of mapping virtual
resources to substrate resources with limited assets (e.g., of
virtual nodes and virtual links also known as virtual
network embedding (VNE) problem [7]).

Specifically, in our work toward optimizing the cloud,
we study and formulate the corresponding VNE problem
in the envisioned networked cloud computing environ-
ment (in the following we will refer to this problem as
networked cloud mapping (NCM)). Following the metho-
dology introduced in [7] and the above considered cloud
service paradigm, our work aims to:

1. extend the pool of shared resources to a layer 2/3
network topology including heterogeneous network
infrastructure possibly across multiple domains;

2. provide a generic formulation for the resource
mapping problem at hand capable of taking into
consideration QoS requirements;

3. support QoS provisioning of cloud IaaS;
4. design and implement an experimentation simula-

tion environment that allows a flexible and struc-
tured evaluation of the performance and efficiency
of the proposed approach; and finally

5. provide a proof of concept of the operational
efficiency of the proposed approach via a prototype
implementation of the framework on an FI experi-
mentation platform, namely the FEDERICA [8].

The remainder of this paper is organized as follows. In
Section 2, a brief review of the related work regarding VNE
problem is provided. In Section 3, the formulation of the
optimal NCM problem is presented, supporting QoS
provisioning of Cloud IaaS, indicating objectives related to
cost efficiency of the resource mapping procedure and

network performance. In addition, the adopted methodol-
ogy to treat and solve this problem is summarized. Section 4
provides an overview of the experimentation environment
implemented to test the efficiency of the proposed solution.
Within this environment, in Section 5, the experiment setup
is described along with numerical results and relevant
discussions. In addition, in Section 6, the application of the
proposed resource mapping methodology in a prototype
implementation utilizing the FEDERICA FI experimenta-
tion testbed is demonstrated. Finally, Section 7 concludes
the paper.

2 RELATED WORK

The problem of assigning interconnected virtual nodes to
the substrate network with constraints on virtual nodes and
virtual links, can be reduced to the NP-hard multiway
separator problem [9]. Most of the proposed approaches
decompose the problem into the node mapping phase and
the link mapping phase, to reduce the overall complexity of
the problem. Researchers usually employ some greedy
heuristic approach for node mapping, while link mapping
is performed using (k) shortest path or multicommodity
flow algorithms (e.g., [10], [11]). Recent approaches tend to
solve the two problems either simultaneously (e.g., [6]) or
providing some type of coordination among the two phases
(e.g., [7]). In the proposed study, we follow the latter
approach. The two phases are correlated in the sense that
the node mapping phase facilitates the link mapping phase.

Additional ways to deal with the complexity of the
problem is to restrict the search space in one or more
dimensions. For example, one may omit admission control
by assuming infinite capacity on the substrate network [12],
[13], [14] or ignore either node or link requirements (e.g.,
[12], [13]). In several cases(e.g., [11], [13], [14], [15]), VNE
requests are not handled upon arrival (offline variants),
while recently several researchers (e.g., [7], [16]) investi-
gated methodologies for handling virtual network requests
as they arrive. Additional constraints have been imposed on
the problem, such as location constraints for virtual
resources (e.g., [7], [17]). The online version of the problem
is studied hereafter supporting admission control dictated
by the limits of substrate resources in terms of capacity.
Upon the arrival of a request, its topology is assigned to the
substrate network with the target to achieve balanced load
on both substrate nodes and links.

Static formulations of the VNE problem have been
studied, where during the life-time of the request, no
change is allowed in resource assignment (e.g., [13], [14]). In
the proposed methodology, the resource mapping solution
is also static in the sense that resource allocation does not
change for the duration of the lease from the cloud
provider. However, complementary to our approach,
dynamic reconfiguration of virtual network mapping (links
or links/nodes) based on current traffic conditions, could be
used to improve the efficient utilization of substrate
resources (e.g., [10], [12], [14]). Although the latter is not
treated in this paper, at the end of Section 5, some
discussion about potential reconfiguration strategies and
emerging tradeoffs is provided.

VNE algorithms suffer from scalability issues and hence
request partitioning has been studied for mapping each part
of a request to a different part of the substrate network (e.g.,
[14], [18]). Distributed algorithms have been proven to

PAPAGIANNI ET AL.: ON THE OPTIMAL ALLOCATION OF VIRTUAL RESOURCES IN CLOUD COMPUTING NETWORKS 1061

enhance overall network resiliency as well as surmount
scalability limitations and delays imposed by maintaining
information centrally (e.g., [15], [19]). Apart from heuristic
algorithms, metaheuristics have been also applied for
solving the VNE problem (e.g., [20], [21]). An overview
and extensive literature review is available in [22] and [23].

All of the aforementioned approaches study the intra-
domain VNE problem. However, recently the interdomain
VNE problem has been also tackled with (e.g., [6], [24], [25],
[26]) by considering virtual network provisioning across
multiple infrastructure providers. In all cases substrate
resources are restricted to computing resources and
bandwidth pipes. Houidi et al in [27] attempt to deal with
heterogeneous substrate resources, where a method for
resource discovery and a clustering technique of the
attributes of the physical resources is proposed, in order
to facilitate association of virtual and physical resources.
Following, a matching algorithm is applied trying to find
the best match between virtual and physical resources.
Optimization algorithms however have not been applied
that would optimize mapping of resources according to
multiple constraints and objectives.

The objective of our work is to deal with the NCM
problem, by efficiently embedding requests for intercon-
nected virtual resources into a pool of heterogeneous
substrate resources with finite capacities in realtime, while
QoS related parameters are also taken into consideration.
Moreover, multiple nonfunctional attributes of those re-
sources are considered.

3 PROBLEM FORMULATION AND SOLUTION

A networked cloud request is modeled as a weighted
undirected graph denoted by GV ¼ðNV ;EV Þ where NV
represents the set of virtual nodes and EV the set of virtual
links. Similarly, the substrate network is modeled as a
weighted undirected graph GS ¼ðNS;ESÞ. Every node is
associated with a resource of type a 2 A (e.g., server, router,
etc.) so that nX 2 V Xa � NX; a 2 A;X 2fV ;Sg and A

S
V Xa ¼

NX;X 2fV ;Sg. Based on its type, node nX 2 V Xa � NX is
attributed with an explicit set I of nonfunctional attributes,
denoted as capacities, ciðnXÞ; i 2 I; nX 2 V Xa ;X 2fV ;Sg
(e.g., CPU capacity, memory, storage capacity, number per
type of available network interfaces, etc.). The vector of
capacities for each node is denoted as cðnXÞ. Moreover,
every edge ðnX;mXÞ 2 EX; 8nX;mX 2 NX;X 2fV ;Sg, is
associated with a link of bandwidth capacity bwðnX;mXÞ.

3.1 Networked Cloud Mapping

Resource mapping determines the allocation of physical
resources (substrate nodes, links, and paths) to the net-
worked cloud request. Resource allocation does not change
for the duration of the lease from the cloud provider while
substrate resources are released upon request expiration.
Request mapping is comprised of node assignment and link
assignment. Specifically, node assignment is denoted as:

MN : NV ! NS

where MNðnV Þ 2 V Sa ;n
V 2 V Va � N

V :

Expressing anticollocation constraints for the computational
resources, each virtual node from the same networked
cloud request must be assigned to a different substrate
node. Therefore,

MNðnV Þ¼ MNðmV Þ() nV � mV :

For a virtual node nV 2 V Va to be mapped to substrate
node nS 2 V Sa each requested capacity i 2 I must not exceed
the remaining capacity Ci of the substrate node nS. That is,

ciðnV Þ� CiðnSÞ

CiðnSÞ¼ ciðnSÞ�

X

8mV ;where
MNðmV Þ¼nS

ciðmV Þ:

On the other hand, every virtual link can be mapped to a
single substrate path PS for nonbifurcated routing or a set
of substrate paths PS, when traffic is split in multiple routes
among the mapping solutions of the virtual link end points.
Under the assumption that flow bifurcation is enabled, that
is traffic may be split among multiple paths, link mapping
is denoted as

ME : EV ! PS

where MEðnV ;mV Þ 2 PSðMNðnV Þ;MNðmV ÞÞ:

Similarly, the bandwidth capacity of the virtual link is
subject to,

bwðnV ;mV Þ�
X

8PS2MEðnV ;mV Þ
bwðPSÞ

bwðPSÞ¼ min
8ðuS;vSÞ2PS

BWðuS;vSÞ

BWðuS;vSÞ¼ bwðuS;vSÞ�
X

8ðjV ;kV Þ;ðuS;vSÞ
2MEðjV ;kV Þ

bw
�
jV ;kV

�
:

The available bandwidth capacity of a substrate path is
restricted to the available capacity BW of the most loaded
link in the path.

An example of a networked cloud request mapped to a
substrate network is provided in Fig. 1. There are two
types of nodes available (namely computational nodes and
routers) so that fa0S;b0S;c0Sg2 V1 � NS, fd0S;e0S;f0Sg2
V2 � NS and faV ;bVg2 V1 ¼ NV . In the particular exam-
ple, computational nodes are associated with {CPU cores,
memory, disk space} while a router’s capacity corresponds

1062 IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 6, JUNE 2013

Fig. 1. Networked cloud environment and request mapping.

to the number of logical router instances it can support.
The values of nominal capacities and available resources
for substrate nodes and links are provided in the
preceding table within Fig. 1. Regarding the request,
values over the virtual nodes and links represent
computational and bandwidth requirements. Moreover,
resource mapping is provided schematically in the figure
where virtual nodes aV and bV have been mapped to
nodes a0S and b0S, respectively, and virtual link ðaV ;bVÞ to
path fða0S;d0SÞ;ðd0S;e0SÞ;ðe0S;f0SÞ;ðf0S;c0SÞg.

3.2 Hard/Soft QoS on Computational Resources

A simple scheme regarding provisioning of computing
resources is employed, to cater for both elastic and hard
cloud provisioning models. Specifically, hard and soft QoS
provisioning is adopted to facilitate capacity requirements
imposed by users. Soft QoS provisioning implies that no
guarantees can be provided on meeting high-workload
demands for elastic cloud services. Instead a best-effort
approach is followed, exploiting the fact that virtual
resources exhibit time-varying resource demand patterns
with bursts of high-demand periods, intermixed with low-
utilization regions [5]. Only a percentage of requested
resources capacity is reserved, necessary to facilitate the
operation of a virtual machine as, e.g., in the case of
VMware’s vStorage thin provisioning scheme [28], enabling
the colocation of more virtual machines in the same
physical node via oversubscription of physical resources.
On the other hand, hard QoS provisioning guarantees
performance at peak workloads via explicit reservation of
maximum requested resources capacity.

Therefore, computational capacity requirements are
modeled as follows: a virtual node nV 2 V Va can be mapped
to substrate node nS 2 V Sa in the case that a percentage
PciðnV Þ of the requested capacity i 2 I, as defined by the
resources provisioning scheme (hard or soft QoS provision-
ing), will not exceed the available capacity Ci of the
substrate node nS. That is,

PciðnV Þciðn
VÞ� CiðnSÞ

CiðnSÞ¼ ciðnSÞ�
X

8mV ;MNðmV Þ¼nS
PciðmV Þciðm

VÞ:

3.3 Mixed Integer Programming Formulation

As already mentioned in Section 2, the node and link
mapping phase are not independent of each other. To
correlate the node and link mapping phase, the methodol-
ogy proposed in [7] is adopted, without however posing
any location constraints on virtual nodes. Specifically, the
substrate network graph is augmented with the virtual
nodes of the request. Every newly added (virtual) node in
the augmented substrate graph is connected to every
substrate node with infinite bandwidth. Hence, the aug-
mented undirected substrate graph is denoted as GS

0 ¼
ðNS0;ES0Þ where NS0 ¼ NS [ NV and ES0 ¼ ES [fðnV ;
nSÞj8nV 2 NV ;8nS 2 NSg.

Every virtual linkðnV ;mV Þ 2 EV with bandwidth require-
ments bwðnV ;mV Þ is considered a commodity in the
augmented substrate graph originated at the virtual node
nV 2 NS0 nNS and ending at the virtual node mV 2 NS0 nNS.
The resource allocation problem in the augmented substrate
graph is formulated as a mixed integer programming (MIP)

jEV j-commodity flow problem, where the communication
demands among the NS

0

nodes are specified as a jNS0 j� jNS0 j

demand matrix. For the sake of simplicity superscripts V ;S

will be omitted in the following.
Variables
xnmuv : a binary variable set to 1 if there is traffic flow of the

virtual link ðn;mÞ 2 EV routed via the augmented substrate
link ðu;vÞ 2 ES0.
fnmuv :the amount of traffic for the virtual link ðn;mÞ 2 EV

routed over the link ðu;vÞ 2 ES0 from u to v.
Objective

min
X

uv2ES

X

nm2EV

Cuvf

nm
uv

þ
X

a2A

X
nm2EV
X

w2V Sa �NS

X

p2V Va �NS
0nNS

Dwx
nm
pw

X

i2I
ciðpÞ

þ
X
uv2ES
X

nm2EV
Cuvx

nm
uv :

ð1Þ

Constraints

fnmuv � 0; 8u;v2NS
0
;8ðn;mÞ2EV ð2Þ

xnmuv 2f0; 1g; 8u;v2NS
0
;8ðnmÞ2EV ð3Þ

X

w2NS0
fnmuv �

X

w2NS0
fnmwu ¼ 0; 8ðn;mÞ2EV ;8u2NS

0nfn;mg

X

w2NS0
fnmnw �

X

w2NS0
fnmwn ¼ bðn;mÞ; 8ðn;mÞ2EV ;n2NS

0
X

w2NS0
fnmmw �

X

w2NS0
fnmwm ¼�bðn;mÞ; 8ðn;mÞ2EV ;m2NS

0

ð4Þ

PciðpÞciðpÞx
nm
pw �CiðwÞ; 8p2V Va �NS

0nNS;

8w2V Sa �NS;8i2I;8a2A;8ðn;mÞ2EV
ð5Þ

�
fnmuv þf

nm
vu

�
�BWðu;vÞxnmuv 8u;v 2 N

S0;8ðn;mÞ 2 EV

ð6Þ

X
nm2EV
�
fnmuv þf
nm
vu

�
�BWðu;vÞ 8u;v2NS0 ð7Þ

X

p2V V
A
�NS

0
nNS

xmnpw � 1; 8w2V SA�NS;8mn2EV ;8A ð8Þ

X

w2V S
A0
�NS

xmnpw ¼ 0; 8p2V VA �NS
0nNS;8mn2EV ;8A;A0;A6¼A0 ð9Þ

X

w2V S
A
�NS

xmnpw ¼ 1; 8p2V VA �NS
0nNS;8mn2EV ;8A: ð10Þ

xnmuv ¼ x
nm
vu ; 8u;v2N

S0 ;8ðn;mÞ2EV ð11Þ

xnmuv ¼ x
nk
uv ¼ x

lm
uv; 8u;v2N

S0nNV ;k;l2NS0nNS;ðn;mÞ2EV ð12Þ

xnmuv �
�
fnmuv þf

nm
vu

�
; 8u;v2NS0 ;8ðn;mÞ2EV : ð13Þ

PAPAGIANNI ET AL.: ON THE OPTIMAL ALLOCATION OF VIRTUAL RESOURCES IN CLOUD COMPUTING NETWORKS 1063

1. The goal of the minimization problem (objective 1) is
twofold;

a To minimize the cost of mapping the request into the
substrate, as provided by the first two summation
terms. The cost of embedding a networked cloud
request corresponds to the sum of substrate
resources allocated to that request. Specifically,
the first terms reflect the total amount of
bandwidth allocated on substrate links that are
parts of the substrate paths mapped to the
requested virtual links. The second terms
correspond to the total amount of computational
resources that are allocated to the physical
servers mapped to requested virtual nodes.
Each of these terms multiplied by the corre-
sponding monetary factor can provide the cost
of embedding the particular request to the cloud
provider resources. Weights Cuv and Dw can be
adjusted to balance the load on the substrate
links and nodes, respectively. As an example, in
[7] the weights Cuv and Dw have been set equal
to the inverse values of the available bandwidth
of the link and the specific node-type available
capacity, respectively. In this way, it is ensured
that less loaded resources are preferred over
more loaded ones. The same approach is
followed in this study.

b To minimize the overall number of hops for a virtual
link mapped on a substrate path, according to the
third summation term. The rationale behind it is
that reducing the number of hops along a traffic
route between two communication nodes is a
common practice to provide QoS enhancements
with regards to latency. Moreover, since the
objective function expresses essentially a biob-
jective problem, an appropriately defined
weight has been also included in the third term
of the summations to control the impact of the
specific objective on the optimization process. In
the particular case, it has been set equal to Cuv to
associate the length of the substrate path
mapped to the virtual link ðm;nÞ and available
capacity of links included in the path, since both
are implicitly related to latency.

2. Constraints (2) and (3) provide the domain con-
straints of the two vector variables.

3. Flow conservation is guaranteed via constraints
set (4).

4. Constraints set (5) ensures that the requested
capacity i 2 I for a virtual node of type a 2 A that
is mapped to substrate node w 2 V Sa � NS does not
exceed the substrate node’s available capacity.

5. Constraints set (6) and (7) ensure that the sum of all
virtual flows that are routed through the substrate
link ðu;vÞ does not exceed its available bandwidth
capacity.

6. Constraints sets (8) and (9) are adopted to ensure
that at most one virtual node is linked to a substrate
node of the same type a 2 A.

7. Constraints set (10) assures that only one substrate
node is selected for each virtual node.

8. Constraints set (11) and (13) ensure that the binary
variable xnmuv is set whenever there is traffic routed of
virtual link ðn;mÞ over the substrate link ðu;vÞ
regardless of the direction. Constraints set (12)
guarantees that the resource mapping solution is a
connected graph.

3.4 Solution

In the previous sections, we have presented the NCM
problem from a pool of heterogeneous physical resources
with the goal of minimizing the mapping cost and the overall
number of hops for every virtual link mapped to a substrate
path. The problem is formulated as a MIP problem. MIPs
provide a flexible and mathematically precise way of
formulating many real-world problems. Such problems are
known to be NP-Hard [29], and thus, large-scale instances
and models exhibiting a high degree of symmetry are often
computationally intractable. Integer programming is a
commonly used technique for resource allocation and
scheduling in wired and wireless networks. The main two
problem types that MIP addresses in this field are: 1) network
synthesis and 2) resource assignment problems [30]. How-
ever, due to the computational intractability of MIP models,
efficient heuristics, problem preprocessing, and reformula-
tions are proposed in the literature such as Lagrangian
relaxation, problem decomposition, branch and bound and
linear programming relaxation.

To solve this problem, the following methodology is
applied. Specifically, the request is mapped to the net-
worked cloud in two phases: 1Þ solving the flow allocation
problem as was described in the previous section that
results in substrate node mapping; and 2Þ allocating virtual
links to the substrate.

Node Mapping Phase
The flow allocation problem as was described in the

previous section is solved, taking into consideration virtual
links as demands. Due to the nature of the MIP problem
presented, the optimal fractional solution is computed for
the problem’s linear programming relaxation of the integer
variable xnmuv , which can provide a solution at least as good as
the integer one. The relaxed problem can be solved by any
suitable linear programming method, in polynomial time
(e.g., CPLEX dual simplex routine). A rounding technique is
applied to obtain the integer solution of the aforementioned
relaxed MIP problem. Randomized rounding for LP relaxa-
tions was introduced by Raghavan and Thompson [31] for
multicommodity routing problems, where the fractional
values contained in the optimal LP solution were treated as
probabilities.

The randomized rounding technique proposed in [7] is
adopted, where the correlation between the linear variable
fnmuv and the binary variable x

nm
uv , during the LP relaxation

process is maintained. Specifically, the substrate node that
maximizes the xnmuv , f

nm
uv product per virtual link is selected.

Link Mapping Phase
Once the aforementioned node mapping procedure has

been successfully completed, link mapping is achieved by
solving the multicommodity flow allocation problem allow-
ing traffic bifurcation [30]. Alternatively, a shortest path
algorithm can be applied to restrict each flow to a single path.

1064 IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 6, JUNE 2013

4 EXPERIMENTATION ENVIRONMENT

A discrete event java-based simulator called simulator for
controlling virtual infrastructures (CVI-Sim) was imple-
mented to provide an extendable experimentation environ-
ment that will enable us to evaluate the performance of the
proposed approach and the efficiency of the mapping
solution. This generic purpose simulator can facilitate
further research on the control and management plane of
virtualized infrastructures. In this concept, CVI-Sim acts as
an emulator of a resource mapping service, because it is
designed to support importing actual resource specification
files (e.g., PlanetLab RSpec [32]) to test substrate networks
and networked cloud requests based on real-world deploy-
ments. Additionally, it allows for bulk random creation of
requests for virtual resources, according to user selected
probabilistic distributions on requests interarrival time and
virtual resources lifetime as well as random generation of
interconnected substrate resources. Finally, via an editing
tool bench, graphic design of requests/substrates is also
supported.

An extended resource set along with resource specific
functional and nonfunctional parameters has been adopted
in CVI-Sim, to allow easy evaluation of virtual resource
mapping algorithms in heterogeneous virtual environments.
Functional and nonfunctional parameters are grouped by
type of resource; e.g., computing node parameters include
operating system, supported virtualization environment,
supported network stack, CPU computational capacity,
available memory, total disk space, maximum number of
interfaces, maximum number of supported VMs. Moreover a
third set of simulation parameters has been defined to capture
the need for request specific information; e.g., description of
the request arrival process, distribution of the lifetime of a
request, adoption of path splitting or unsplittable flows.

CVI-Sim is based on the JUNG software library [33] that
provides a common and extendible language for the
manipulation, analysis, and visualization of data that can
be represented as a graph. The GUI of the simulator is
implemented under JFC (Swing/AWT) framework [34].
The library CPLEX has been used to solve the relaxed MIP
problem [35].

5 PERFORMANCE EVALUATION

In this section, the effectiveness of the proposed network
cloud mapping problem formulation along with the
performance of the proposed solution is evaluated via
simulation. To better illustrate the efficiency and superior
performance of the proposed NCM approach, we compare
it against the corresponding performances of the following
two well-known methods applied in the literature, in terms
of a well-defined set of metrics.

. Greedy node mapping followed by a shortest path
algorithm for the link mapping phase (G-SP) [14]

. Greedy node mapping followed by solving the
multicommodity flow problem (G-MCF) [10].

5.1 Evaluation Setup and Metrics

Regarding substrate network creation, two types of nodes
have been used (servers and routers) to provide a more

realistic networked cloud environment. Each node is
characterized from its type (server, router), its operating
system (Windows, Linux, Android, Solaris, JUNOS, etc.),
and its virtualization environment (Xen, VMware, KVM,
JUNOS specific, etc.). Moreover, the nodes have different
nonfunctional characteristics based on their type, e.g., CPU
computational capacity, memory, storage for servers, and
number of available logical router instances for routers.
Matching the experimentation setup in [7], the available
CPU capacity per server and available bandwidth capacity
per substrate link are uniformly distributed in the interval
[50-100]. These present unit values. Similarly, available
storage and memory capacities are also defined as real
numbers uniformly distributed between [50-100]. A max-
imum of 15 available logical routers can be instantiated on
every physical router [36]. Substrate topologies are ran-
domly generated as partial mesh topologies, while each
substrate is comprised of 50 nodes. The probability of
generating a specific type of node is 80 percent for servers
and 20 percent for routers.

In the same fashion as in [7], the requested CPU capacity
is uniformly distributed in the interval [0-20] for every
requested virtual machine and requested bandwidth is
uniformly distributed in the interval [0-50]. Requested
storage and memory capacities are also defined as real
numbers uniformly distributed between [0-20]. One logical
router corresponds to each requested machine with routing
capabilities. The number of virtual nodes per request is
randomly selected by a uniform distribution between 2 and
10 with 50 percent connectivity, following similar setups in
the literature [10], [14]. The probability of generating a
specific type of node is 90 percent for VMs and 10 percent
for virtual routers. The ratio between hard and soft QoS
provisioning for networked cloud requests is set to
50 percent, while the percentage of resources capacity
reserved PciðnV Þ is set to 50 percent.

NCM requests arrive according to a Poisson process with
a varying rate (1 request per 100 time units to five requests
per 100 time units; step 0.5). Each of them is assumed to
have exponentially distributed lifetime with an average of
1,000 time units. Each simulation is executed for 1,000
requests and repeated for 10 iterations. The aforementioned
experimentation setup is aligned with commonly used
environments in the literature (e.g., [7], [10], [14] ).

To quantify the performance of these approaches, we
use the metrics presented in Table 1. The revenue metric is
an indicator of the cloud provider’s gain from accepting
NCM requests, while the mapping cost reflects the
corresponding cost for embedding a request and allocating
substrate resources.

PAPAGIANNI ET AL.: ON THE OPTIMAL ALLOCATION OF VIRTUAL RESOURCES IN CLOUD COMPUTING NETWORKS 1065

TABLE 1
Evaluation Metrics

5.2 Numerical Results and Comparison

Figs. 2 and 3 present the behavior of the three algorithms
under consideration in this study, namely NCM, G-SP, and
G-MCF, regarding the metrics of acceptance ratio and
mapping revenue, respectively, as a function of increasing
request arrival rate. As we can observe from those figures,
NCM outperforms G-SP with regards to the cloud
provider’s revenue and number of networked cloud
requests that are successfully embedded in the substrate.
That effect is more pronounced as the request arrival rate
increases leading to a more loaded substrate. On the other
hand, NCM exhibits similar revenue and acceptance ratio to
the G-MCF approach; both metrics are slightly increased
for the G-MCF in higher arrival rates partially due to the
fact that the algorithm tends to accept more requests with
soft QoS resource provisioning (e.g., approximately 2 per-
cent for arrival rate five requests per 100 time units).

Fig. 4 signifies that the NCM succeeds in reducing the
number of hops along a traffic route between two commu-
nication nodes (i.e., according to the second objective in the
problem formulation). Despite the fact that traffic bifurca-
tion is allowed, NCM’s behavior with regards to the
particular metric is slightly enhanced in lower arrival rates

compared to the G-SP, where the shortest substrate path
between two nodes is always selected, due to more efficient
node mapping in that terms. This decrease is also supported
by the lower mapping cost of the NCM in comparison to the
G-SP, as depicted in Fig. 5. On the other hand, as the request
arrival rate increases, the average hop number per virtual
link is slightly higher for the NCM because it maps
successfully a larger number of requests than the G-SP.
These two factors lead to a slight increase of the mapping
cost for the NCM as depicted in Fig. 5.

Similarly, at low arrival rates the NCM and G-MCF
exhibit similar behavior with regards to accepting incoming
requests. Despite the fact that the G-MCF results in higher
average hop number per virtual link, the mapping cost for
the NCM is slightly higher (Fig. 5). The latter observation,
along with the fact that revenues for the two algorithms are
also similar, is an indicator that the proposed approach, due
to the second objective in the problem formulation, tends to
attain a smaller bifurcation ratio than the G-MCF. At higher
arrival rates, the difference in cost increases slightly due to
the difference in the number of accepted requests. The latter
observation along with fact that the values of average hop
number per virtual link are more diverse, is an indicator

1066 IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 6, JUNE 2013

Fig. 2. Acceptance ratio.

Fig. 3. Mapping revenue.

Fig. 4. Hop count.

Fig. 5. Mapping cost.

that the proposed approach tends to embed requests that
generate more revenue, instead of requests with a smaller
node/link number that increase the acceptance ratio.

The key observation that the average hop number per
virtual link (Fig. 4) is maintained at low values for the NCM
approach, demonstrates the efficiency of the problem
formulation and solution. This reduction of hops can be
implicitly translated to improvement in the provided QoS
parameters (e.g., delay). There is an obvious tradeoff
between the number of hops on the adopted path(s) and
the ability of accepting incoming requests, a fact witnessed
by both G-SP and G-MCF (Fig. 2 and 4). The NCM on the
other hand manages to overcome this tradeoff by exhibiting
similar behavior to the G-MCF with regards to acceptance
ratio and revenue while maintaining the number of hops on
the adopted path(s) at similar levels with those achieved by
the G-SP. Moreover, another key observation is that by
controlling the bifurcation ratio for the NCM algorithm we
can adjust the embedding cost, e.g., an increase in the
bifurcation ratio would decrease the cost at the expense of a
increase in the average hop number per virtual link.

It is noted that based on our evaluation all three algorithms
present similar trend and comparable results regarding
utilization of substrate resources, with NCM’s performance
positioned in between the corresponding performances of
G-SP and G-MCF. Indicatively, server CPU, server memory,
and link utilization, for an arrival rate of four requests per
100 time units is presented in Table 2. We should note that
despite the fact that the number of accepted requests are very
close for both NCM and G-MCF (2 percent difference),
utilization is lower for NCM due to adopted load balancing
feature.

The evaluation results demonstrate the benefits of the
proposed approach for the cloud infrastructure provider
and motivate its adoption in real systems. Specifically, it
enables service differentiation (e.g., soft or hard QoS
provisioning for capacity requirements, low delay substrate
paths) in the sense that requests with different requirements
can be served by providing the corresponding set of virtual
resources at different cost. Furthermore, NCM tends to
accept more requests for guaranteed resources (i.e., hard
QoS), hence providing more revenue, assuming that an
appropriate unit monetary cost per type of service is
applied. In addition, it allows the provider to control the
parameters of the algorithm and the corresponding sub-
strate resources allocation process, to better meet its
operational objectives. For example, adjusting the weight
of the objective related to the hop number, the bifurcation
ratio can be implicitly regulated. Fine tuning the tradeoff
between the number of hops on the adopted path(s) and the
ability of accepting incoming requests, enables each cloud
provider to pursue their specific business goals.

5.3 Discussion on Virtual Topology
Reconfiguration

As noted before, the proposed resource mapping solution is
static in the sense that resource allocation does not change
for the duration of the lease from the cloud provider.
Although the load balancing feature of our approach can to
some extent mitigate the potential effects of static request
assignment since upon a request arrival, less loaded
resources are preferred over more loaded ones, to further
deal with the highly dynamic networked cloud environ-
ment, the proposed NCM algorithm could be complemen-
ted with the parallel application of an appropriate
reconfiguration mechanism. Such a reconfiguration me-
chanism triggers node and path migration for the purpose
of reallocating virtualized resources, according to a pre-
specified reconfiguration policy.

Reconfiguration policies may vary depending on several
operational parameters such as: 1) the degree of utilization
of substrate resources which may result in existing service
performance degradation or new service denial, 2) unba-
lanced allocation of substrate resources and/or resource
consolidation, 3) implementation of service prioritization
policies. The frequency of resources remapping along with
the number of already assigned sets of virtual resources
impacted by such a reconfiguration, determines to a large
extent the involved migration overhead and corresponding
cost. This cost includes among others, computational
resources required for recomputing resource assignment,
migration overhead and its impact on substrate networking
resources, and possible service disruption cost.

In practice, a methodology similar to the one proposed in
[14] could be adapted and executed periodically, where a
threshold-based approach on the resource utilization could
be employed for marking a resource for possible reconfi-
guration. Furthermore, instead of reconfiguring only the
virtual topologies with marked resources, the residual
lifetime of the requests could be also taken into account.
The goal should be to avoid reconfiguring requests that are
expected to expire soon. The cost of reconfiguration and
migration of resources (i.e., [14]), as mentioned before, could
reflect among others the expenses involved in recomputing
the topology assignment (e.g., embedding cost), as well as
the potential service disruption. Apart from periodical
reconfiguration, in an alternative approach, the reconfigura-
tion scheme could be activated upon request denial as means
to decrease reconfiguration cost and complexity. A max-
imum value should be applied on the number of virtual
topologies that are reconfigured on each occasion, because in
a highly loaded networked cloud the number of reconfi-
gurations could increase substantially.

6 APPLICATION OF THE PROPOSED FRAMEWORK ON
A FI EXPERIMENTATION PLATFORM: A PROOF OF
CONCEPT

A prototype of the proposed resource mapping algorithm
has been implemented within networking innovations over
virtualized infrastructures (NOVI) control framework [37],
a real-time provisioning system of heterogeneous resources
over federated shared infrastructures. NOVI is an experi-
mentally driven research project under the FIRE initiative
[38] with the goal to create a blueprint of FI federated

PAPAGIANNI ET AL.: ON THE OPTIMAL ALLOCATION OF VIRTUAL RESOURCES IN CLOUD COMPUTING NETWORKS 1067

TABLE 2
Resources Utilization

infrastructures. NOVI’s aim is to address the issue of

vertical federation by designing and prototyping a service

portfolio based on combined virtualized facilities from

shared infrastructures at different layers. NOVI control

framework [39] is being deployed in a federated testbed

including the FEDERICA [8] infrastructure. The latter is a

resource virtualization platform, augmented with network

and computing facilities hosted in European NREN Points

of Presence.
In this section, the application and operation of the

proposed resource mapping scheme over the FEDERICA
experimental platform is demonstrated. The module re-
sponsible for resource mapping has been adapted to
incorporate the embedding paradigm presented in the
previous sections and enable allocation within the admin-
istrative domain of FEDERICA. The presented prototype

serves as a proof of concept regarding the efficiency of the
embedding process.

To exhibit the functionality and operational differences of
the two algorithms (NCM and G-SP) an illustrative example
is presented in Fig. 6 and Fig. 7. Specifically, five networked
cloud requests arrive in sequence for the FEDERICA
substrate network, as depicted on each of the two figures.
Only hard QoS provisioning is supported for these requests.
The application of NCM results into mappings that reflect
the objectives of the MIP problem presented in Section 3.3;
that is, manages to balance the load across the entire
substrate topology in comparison to the G-SP, reduces the
average hop number per virtual link to 1.65 in comparison
to the 2.28 of G-SP, while simultaneously the cost for
embedding the requests is 1,072 for the NCM and 1,354 for
the G-SP.

1068 IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 6, JUNE 2013

Fig. 6. NCM mapping on the FEDERICA substrate.

7 CONCLUDING REMARKS

In this paper, we study the virtual resource allocation
problem for networked cloud environments, incorporating
heterogeneous substrate resources, and provide an appro-
priate approximation approach to address the problem.
Specifically, for the node mapping phase, we provide a MIP
problem formulation capable of taking into consideration
QoS requirements. Appropriate relaxation and application of
a randomized rounding technique leads to a polynomial-
time solution. Following, link mapping is determined by
solving the corresponding multicommodity flow problem.
The proposed solution is compared against two well-known
approaches on embedding virtual resource requests to a
physical substrate. Based on extensive modeling and
experimentation, utilizing CV I-Sim—a simulation/emula-
tion environment that allows for a flexible and structured

evaluation of the performance and efficiency of the proposed
approach, we conclude that the proposed NCM approach
overall outperforms other commonly applied algorithms.
Specifically, NCM provides a tradeoff between G-SP and
G-MCF in terms of acceptance ratio of NCM requests and
number of hops on the substrate, per virtual link. At the same
time, NCM manages to embed requests that generate
more revenue, at a cost similar to G-MCF. An appropriate
reconfiguration strategy has been also adopted to deal with
the highly dynamic networked cloud environment.

It should be noted that although in this paper the optimal
NCM problem has been addressed considering heteroge-
neous resources, the main focus has been placed on wired
and fixed networks and infrastructures. Extending however
the proposed framework to take into account new and more
dynamic heterogeneous environments and infrastructures,
beyond the traditional Internet (e.g., wireless), presents

PAPAGIANNI ET AL.: ON THE OPTIMAL ALLOCATION OF VIRTUAL RESOURCES IN CLOUD COMPUTING NETWORKS 1069

Fig. 7. G-SP mapping on the FEDERICA substrate.

additional challenges, due to the nature of the wireless

environment (e.g., coherence, isolation and uniqueness of

nodes), the stochastic nature of the corresponding re-

sources, as well issues associated with the existence of

mobile nodes. The development of such a holistic frame-

work is of high research and practical importance and is

part of our current and future work.

ACKNOWLEDGMENTS

This work was supported in part by the European Commis-

sion, seventh Framework Program for Research and Tech-

nological Development, Capacities, Grant No. 257867 – NOVI.

REFERENCES
[1] R. Buyya, C.S. Yeo, and S. Venugopal, “Market-Oriented Cloud

Computing: Vision, Hype, and Reality for Delivering it Services as
Computing Utilities,” Proc. IEEE Int’l Conf. High Performance
Computing and Communications (HPCC ’08), pp. 5-13, Sept. 2008.
doi: 10.1109/HPCC.2008.172.

[2] “Creating Energy Efficient Data Centers,” U.S. Dept. of Energy,
May 2007.

[3] D. Breitgand, A. Epstein, and B. Rochwerger, “Resource Manage-
ment Mechanisms to Support SLAs in IaaS Clouds” Achieving
Federated and Self-Manageable Cloud Infrastructures: Theory and
Practice, pp. 288-307, IGI Global, 2012, doi:10.4018/978-1-4666-
1631-8.

[4] I.M. Lloriente, R.S. Montero, B. Sotomayor, B. Breitgand, and
D. Maraschini, “On the Management of Virtual Machines for
Cloud Infrastructures,” Cloud Computing: Principles and Para-
digms, pp. 157-191, John Wiley & Sons, Jan. 2011, doi:10.1145/
1809049.1809052.

[5] X. Meng, C. Isci, J. Kephart, L. Zhang, E. Bouillet, and D.
Pendarakis, “Efficient Resource Provisioning in Compute Clouds
via VM Multiplexing,” Proc. Seventh Int’l Conf. Autonomic Comput-
ing, pp. 11-20, June 2010. doi:10.1145/1809049.1809052.

[6] I. Houidi, W. Louati, W.B. Ameur, and D. Zeghlache, “Virtual
Network Provisioning Across Multiple Substrate Network,”
J. Computer Networks, vol. 55, no. 2, pp. 1011-1023, 2011,
dx.doi.org/10.1016/j.comnet.2010.12.011.

[7] M. Chowdhury, M.R. Rahman, and R. Boutaba, “ViNEYard:
Virtual Network Embedding Algorithms With Coordinated Node
and Link Mapping,” IEEE/ACM Trans. Networking, vol. 20, no. 1,
pp. 206-219, Feb. 2012, doi: 10.1109/TNET.2011.2159308.

[8] “The FEDERICA Project Website,” http://www.fp7-federica.
eu, 2013.

[9] D. Andersen, “Theoretical Approaches To Node Assignment,”
Unpublished Manuscript, http://www-2.cs.cmu.edu/~dga/
papers/andersen-assign.ps, 2002.

[10] M. Yu, Y. Yi, J. Rexford, and M. Chiang, “Rethinking Virtual
Network Embedding: Substrate Support for Path Splitting and
Migration,” ACM SIGCOMM Computer Comm. Rev., vol.38, no. 2,
pp. 17-29, Apr. 2008, doi:10.1145/1355734.1355737.

[11] W. Szeto, Y. Iraqi, and R. Boutaba, “A Multi-Commodity Flow
Based Approach to Virtual Network Resource Allocation,” Proc.
IEEE GLOBECOM ’03, vol. 6, pp. 3004-3008, Dec. 2003,
doi:10.1109/GLOCOM.2003.1258787.

[12] J. Fan and M.H. Ammar, “Dynamic Topology Configuration in
Service Overlay Networks: A Study of Reconfiguration
Policies,” Proc. IEEE INFOCOM ’06, pp. 1-12, Apr. 2006,
doi:0.1109/INFOCOM.2006.139.

[13] J. Lu and J. Turner, “Efficient Mapping of Virtual Networks onto a
Shared Substrate,” Technical Report WUCSE-2006-35, Washington
Univ. St. Louis, 2006.

[14] Y. Zhu and M.H. Ammar, “Algorithms for Assigning Substrate
Network Resources to Virtual Network Components,” Proc. IEEE
INFOCOM ’06, pp. 1-12, Apr. 2006, doi:10.1109/INFO-
COM.2006.322.

[15] I. Houidi, W. Louati, and D. Zeghlache, “A Distributed Virtual
Network Mapping Algorithm,” Proc. IEEE Int’l Conf. Comm.
(ICC ’08), pp. 5634-5640, May 2008, doi:10.1109/ICC.2008.1056.

[16] J. Lischka and K. Holger, “A Virtual Mapping Algorithm Based on
Subgraph Isomorphism Detection,” Proc. ACM SIGCOMM ’09,
pp. 81-88, Aug. 2009, doi:10.1145/1592648.1592662.

[17] L. Lallemand and A. Reifert, “On Force-Based Placement of
Distributed Services within a Substrate Network,” Proc. EUNICE/
IFIP WG 6.6 Conf. Networked Services and Applications: Eng., Control
and Management (EUNICE ’10), pp. 65-75, June 2010, doi:10.1007/
978-3-642-13971-0-7,

[18] Y. Liu, Y. Li, K. Xiao, and H. Cui, “Mapping Resources for
Network Emulation with Heuristic and Genetic Algorithms,”
Proc. Int’l Conf. Parallel and Distributed Computing, Applications and
Technologies (PDCAT ’05), pp. 670-674, 2005, doi:10.1109/
PDCAT.2005.166.

[19] I. Houidi, W. Louati, D. Zeghlache, P. Papadimitriou, and L.
Mathy, “Adaptive Virtual Network Provisioning,” Proc. ACM
SIGCOMM ’10, Sept. 2010.

[20] S. Zhang, Z. Qiant, S. Guo, and S. Lu, “FELL: A Flexible Virtual
Network Embedding Algorithm with Guaranteed Load Balan-
cing,” Proc. IEEE Int’l Conf. Comm. (ICC), pp. 1-5, June 2011,
doi: 10.1109/icc.2011.5962960.

[21] I. Fajjari, N. Aitsaadi, G. Pujolle, and H. Zimmermann, “VNE-AC:
Virtual Network Embedding Algorithm Based on Ant Colony
Metaheuristic,” Proc. IEEE Int’l Conf. Comm. (ICC), pp. 1-6, June
2011, doi: 10.1109/icc.2011.5963442.

[22] A. Haider, R. Potter, and A. Nakao, “Challenges in Resource
Allocation in Network Virtualization,” Proc. ITC Specialist Seminar
Network Virtualization, May 2009.

[23] N.M. Mosharaf, K. Chowdhury, and R. Boutaba, “A Survey of
Network Virtualization,” Computer Networks, vol. 54, no. 5,
pp. 862-876, Apr. 2010, doi:10.1016/j.comnet.2009.10.017.

[24] M. Chowdhury, F. Samuel, and R. Boutaba, “PolyViNE: Policy-
Based Virtual Network Embedding Across Multiple domains,”
Proc. ACM SIGCOMM ’10, pp. 49-56, Sept. 2010, doi:10.1145/
1851399.1851408.

[25] F. Zaheer, J. Xiao, and R. Boutaba, “Multi-Provider Service
Negotiation and Contracting in Network Virtualization,” Proc.
IEEE Network Operations and Management Symp. (NOMS), pp. 471-
478, June 2010, doi: 10.1109/NOMS.2010.5488487.

[26] Y. Xin, I. Baldine, A. Mandal, C. Heermann, J. Chase, and A.
Yumerefendi, “Embedding Virtual Topologies in Networked
Clouds,” Proc. Sixth Int’l Conf. Future Internet Technologies
(CFI’ 11), pp. 26-29, June 2011, doi:10.1145/2002396.2002403.

[27] I. Houidi, W. Louati, D. Zeghlache, and S. Baucke, “Virtual
Resource Description and Clustering for Virtual Network Dis-
covery,” Proc. IEEE Int’l Conf. Communications (ICC ’09), pp. 1-6,
June 2009, doi:10.1109/ICCW.2009.5207979.

[28] “VMware vStorage Thin Provisioning,” http://www.vmware.-
com/files/pdf/VMware-vStorage-Thin-Provisioning-DS-EN ,
2013.

[29] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide
to the Theory of NP-Completeness. W. H. Freeman & Co., 1979.

[30] M.G.C. Resende and P. Pardalos, Handbook of Optimization in
Telecommunication. Springer, 2006.

[31] P. Raghavan and C.D. Thompson, “Randomized Rounding: A
Technique for Provably Good Algorithms and Algorithmic
Proofs,” Combinatorica, vol. 7, no. 4, pp. 365-374, 1987,
doi:10.1007/BF02579324.

[32] “PlanetLAB Website,” http://www.planet-lab.org, 2013.
[33] “JUNG 2.0.1 Website,” http://jung.sourceforge.net, 2013.
[34] “JFC(Swing/AWT) Website,” http://download.oracle.com/

javase/6/docs/technotes/guides/swing, 2013.
[35] “IBM ILOG CPLEX Optimizer,” http://www-01.ibm.com/

software/integration/optimization/cplex-optimizer/, 2013.
[36] Juniper MX480, http://www.juniper.net/, 2013.
[37] “NOVI FP7 STREP Project Website,” http://www.fp7-novi.eu,

2013.
[38] FIRE: Future Internet Research and Experimentation, http://

cordis.europa.eu/fp7/ict/fire, 2013.
[39] L. Lymberopoulos, M. Grammatikou, M. Potts, P. Grosso, A.

Fekete, B. Belter, M. Campanella, and V. Maglaris, “NOVI Tools
and Algorithms for Federating Virtualized Infrastructures,” Future
Internet – From Technological Promises to Reality, pp. 213-224,
Springer-Verlag, 2012, doi: 10.1007/978-3-642-30241-1_19.

1070 IEEE TRANSACTIONS ON COMPUTERS, VOL. 62, NO. 6, JUNE 2013

Chrysa Papagianni received the diploma
degree and the PhD degree in electrical and
computer engineering, both from NTUA in 2003
and 2009, respectively. She is a senior R&D
associate at the Network Management and
Optimal Design Laboratory (NETMODE), Na-
tional Technical University of Athens (NTUA),
Athens, Greece, since October 2010. Her
research interests include the area of computer
networks with emphasis on cloud computing,

virtualization, network optimization and management, and service
provisioning.

Aris Leivadeas received the diploma degree in
electrical and computer engineering from the
University of Patras, Greece in 2008, and the
MSc degree in mobile and personal commu-
nications from King’s College London, United
Kingdom, in 2009. He has been a member of the
Network Management and Optimal Design
Laboratory (NETMODE), National Technical
University of Athens, Greece, since October
2010, where he is currently working toward the

PhD degree. His research interests include cloud computing, wired/
wireless virtualization, and optimization.

Symeon Papavassiliou received the diploma
degree in electrical and computer engineering
from the National Technical University of
Athens, Greece, in 1990, and the MSc and
PhD degrees in electrical engineering from
Polytechnic University, Brooklyn, NY, in 1992
and 1996, respectively. He is currently an
associate professor with the Faculty of Electrical
and Computer Engineering Department, Na-
tional Technical University of Athens. From

1995 to 1999, he was a senior technical staff member at AT&T
Laboratories in Middletown, New Jersey, and in August 1999 he joined
the Electrical and Computer Engineering Department at the New Jersey
Institute of Technology (NJIT), where he was an associate professor
until 2004. He was awarded the Best Paper Award in IEEE
INFOCOM ’94, the AT&T Division Recognition and Achievement Award
in 1997, the US National Science Foundation (NSF) Career Award in
2003, and the Best Paper Award in IEEE WCNC 2012. He has an
established record of publications in his field of expertise, with more than
200 technical journal and conference published papers. His main
research interests include the area of computer and communication
networks with emphasis on wireless communications, resource alloca-
tion, and optimization, network virtualization and performance analysis,
and evaluation of stochastic systems.

Vasilis Maglaris received the diploma degree in
mechanical and electrical engineering from
NTUA in 1974 and the PhD degree from
Columbia University, New York in 1979. He is
a professor of Electrical & Computer Engineer-
ing (ECE) at the National Technical University of
Athens (NTUA) since 1989. He subsequently
held various industrial and academic positions in
the USA (1979-1989) and in Greece (1989-
now). His research interests include Internet

technologies, network design and optimization and distributed comput-
ing systems. He is currently chairing the Policy Committee that governs
GEANT the Pan-European next generation interconnection of more than
34 National Research & Education Networks in the extended European
Research Area. He also served on the board of the Greek National
Regulatory Authority on Telecommunications and Posts for two five-year
terms (1995-2005). He is currently directing the Network Management &
Optimal Design (NETMODE) Laboratory within the ECE School at
NTUA. He has authored more than 100 research papers and regularly
delivers lectures on Internet advances.

Cristina Cervelló-Pastor received the MSc
degree in telecom engineering and the PhD
degree in telecommunication engineering, both
from the Barcelona School of Telecommunica-
tions Engineering (ETSETB), Universitat Poli-
técnica de Catalunya (UPC), Barcelona, Spain.
She is an associated professor in the Depart-
ment of Telematics Engineering of UPC. Cur-
rently, she is the head of this Department. She is
also the leader of the line of investigation on

Optical Networks within the BAMPLA group. The research trajectory has
been centered on the field of routing in high speed networks and the
development of new protocols and services in optical networks, taking
part in diverse national and European projects (NOVI, FEDERICA,
ATDMA, A@DAN, Euro-NGI, Euro-FGI, EURO-NF) and being respon-
sible of various public and private funding R&D projects. In parallel, she
has published diverse papers in national and international journals and
conferences and she is supervising thesis in the field of routing and
contention resolution in high-speed networks

�Alvaro Monje received the degree in informatics
engineering in 2009 from the Facultat d’Informá-
tica de Barcelona (FIB), Universitat Politécnica
de Catalunya (UPC), Barcelona, Spain. He is
currently with the NOVI project. He has worked
in the FEDERICA project and previously for FIB
as administrator and maintenance coordinator.

. For more information on this or any other computing topic,
please visit our Digital Library at www.computer.org/publications/dlib.

PAPAGIANNI ET AL.: ON THE OPTIMAL ALLOCATION OF VIRTUAL RESOURCES IN CLOUD COMPUTING NETWORKS 1071

<< /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles false /AutoRotatePages /None /Binding /Left /CalGrayProfile (None) /CalRGBProfile (None) /CalCMYKProfile (None) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.6 /CompressObjects /Off /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.1000 /ColorConversionStrategy /LeaveColorUnchanged /DoThumbnails true /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams true /MaxSubsetPct 100 /Optimize true /OPM 0 /ParseDSCComments false /ParseDSCCommentsForDocInfo false /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo false /PreserveFlatness true /PreserveHalftoneInfo true /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Remove /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 36 /ColorImageMinResolutionPolicy /Warning /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 2.00333 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages false /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >>
/ColorImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >>
/JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >>
/JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 36
/GrayImageMinResolutionPolicy /Warning
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 2.00333
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages false
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >>
/GrayImageDict << /QFactor 0.76 /HSamples [2 1 1 2] /VSamples [2 1 1 2] >>
/JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >>
/JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 15 >>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 36
/MonoImageMinResolutionPolicy /Warning
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 600
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.00167
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict << /K -1 >>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName (http://www.color.org)
/PDFXTrapped /False
/CreateJDFFile false
/Description << /JPN
/DEU
/FRA
/PTB
/DAN
/NLD
/ESP
/SUO
/ITA
/NOR
/SVE
/ENU (IEEE Settings with Allen Press Trim size)
>>
>> setdistillerparams
<< /HWResolution [600 600] /PageSize [567.000 774.000] >> setpagedevice