IEICE TRANS. COMMUN., VOL.E96–B, NO.1 JANUARY 2013

56

PAPER

Special Section on Network Virtualization, and Fusion Platform of Computing and Networking

Dynamic Virtual Network Allocation for OpenFlow Based Cloud
Resident Data Center
Tri TRINH†a) , Student Member, Hiroshi ESAKI†b) , Member, and Chaodit ASWAKUL†c) , Nonmember

SUMMARY
Dynamic virtual network allocation is a promising traffic control model for cloud resident data center which oﬀers virtual data
centers for customers from the provider’s substrate cloud. Unfortunately,
dynamic virtual network allocation designed in the past was aimed to theInternet so it needs distributed control methods to scale with such a large
network. The price for the scalability of the completely distributed control
method at both virtual layer and substrate layer is the slow convergence ofalgorithm and the less stability of traﬃc. In this paper, we argue that the
distributed controls in both virtual and substrate networks are not necessary for the cloud resident data center environment, because cloud resident
data center uses centralized controller as the way to give network control
features to customers. In fact, we can use the centralized algorithm in each
virtual data center which is not very large network and the distributed algorithm is only needed in substrate network. Based on the specific propertiesof this model, we have used optimization theory to re-design the substratealgorithm for periodically re-adjusting virtual link capacity. Results fromtheoretical analysis, simulations, and experiments show that our algorithm
has faster convergence time, simpler calculation and can make better useof the feedback information from virtual networks than the previous algorithm.
key words: network virtualization, OpenFlow, data center, centralized
controller, traﬃc management

1.

Introduction

The cloud resident data center [1], which has been proposed
to replace the Amazon virtual private cloud (Amazon VPC)[2], oﬀers customers not only a bunch of virtual machines
but also the network services to connect and control traffics among these virtual machines. The restricted traﬃccontrol features provided by the Amazon VPC (e.g. statically add/remove routing entries, access control list) arenot enough for the various requirements of customers. In
fact, customers need the ability of freely choosing dynamic
routing algorithms, security systems and caching systems
to match with their operating model. A cloud resident data
center oﬀers those flexibilities by giving each of virtual data
center customers a physical controller. This controller canthen be used to enable those customers to install proper network control features to control their virtual network portion
rented from the infrastructure cloud. There are three main
properties of cloud resident data center to define the traffic management model. Firstly, a cloud resident data center
is typically based on the physical network structure of disManuscript received May 18, 2012.
Manuscript revised August 30, 2012.
†
The authors are with Chulalongkorn University, Thailand.
a) E-mail: tri.m@student.chula.ac.thb) E-mail: hiroshi@wide.ad.jpc) E-mail: chaodit.a@chula.ac.th
DOI: 10.1587/transcom.E96.B.56

tributed data centers each with a fat-tree topology. This allows the usage of cheaper switches in the network core layer
than with a conventional topology requiring high-densityport switches for interconnections within each data center.
This topology has many paths between each end-host pairso the multi-path traﬃc engineering is the most suitable
for the traﬃc management model. Secondly, the traﬃc demands coming from virtual network customers are a priori
unknown so static traﬃc controls can lead to higher chancesof demand loss or capacity waste than dynamically adaptive traﬃc controls can. Thirdly, the requirement for virtual network provision to each customer suggests that cloud
resident data centers should support the network virtualization [1]. The multi-path load balancing problem has beentackled in [3] by designing a traﬃc scheduler to estimate
the elephant or big demands and using heuristic algorithms
to search for the optimal mapping between these demands
and physical paths. The dynamic congestion-control problem presented in [4] uses a marking system to decrease thesource sending rate variation for archiving the high throughput even with a small buﬀer size. The combination of thesetwo problems has been formulated and solved in the framework of centralized optimization algorithm [5]. However,
all the aforementioned works have dealt with the traﬃc management problems in only one network layer. A cloud resident data center model needs the co-operation of traﬃc management mechanisms between virtual layer and substratelayer to maximize the total utility and make most uses ofthe physical resources. Davinci [6] has addressed this traﬃcmanagement problem in two layers. At the virtual layer, an
optimization problem has been formulated on the requirements of customers and solved distributedly by a decomposition method. At the substrate layer, a periodically updated
mechanism has been proposed to control the capacity of virtual links according to the derived congestion prices. Unfortunately, this approach has been aimed at such big networks
as the Internet so the distributed algorithms have been usedin both substrate layer and virtual layer. This is not suitable for the traﬃc management problem in the cloud resident data center with virtualized networks each managed bya centralized controller dedicated for each of the virtual data
center customers. This paper contains two original contributions.
Firstly, in this paper, the cloud resident data center
testbed has been implemented in the OpenFlow platform.
We have decided to use the OpenFlow because of its centralized system structure whose controller can have a global

c 2013 The Institute of Electronics, Information and Communication Engineers
Copyright TRINH et al.: DYNAMIC VIRTUAL NETWORK ALLOCATION FOR OPENFLOW BASED CLOUD RESIDENT DATA CENTER

57

view on the overall network. That centralized controller cangive a better decision to manage the traﬃcs inside the network. Additionally, the OpenFlow is the open system allowing devices from diﬀerent vendors to in-operate smoothly
via the OpenFlow standard. Our testbed has been implemented on Linux-based computers installed with OpenFlow
switch [7] as the physical layer, FlowVisor [8] as the network virtualization layer, and Network Operating System
NOX [9] as the centralized controller. All the system modules communicate via the OpenFlow [7] protocol to emulate
the dynamics of a small cloud resident data center testbed.
Secondly, this paper re-designs the traﬃc control
model in [6] for the OpenFlow-based network setting ofcloud resident data center. Due to the centralized control
structure of the OpenFlow, we have decided to implement
the centralized optimization algorithm on each virtual network instead of distributed algorithm. And we have implemented the distributed traﬃc control algorithm in the substrate network to periodically control the allocation of virtual link capacity for the new model of cloud resident data
center.
The rest of this paper is organized as follows. Section
2 describes the system model. Section 3 presents the derivation of our virtual link capacity updated algorithm for cloud
resident data center. Section 4 demonstrates how we implement our algorithm in OpenFlow based Testbed. Section 5shows the results and discussions. The final section is Conclusion and our future works.
2.

System Description

Figure 1 shows the OpenFlow-based cloud resident data
center system testbed constructed in this research. The system is comprised of four main elements, i.e., virtual network controller, substrate node, end-host and host manager.
The function of virtual network controller is to control how
substrate nodes switch the packet flows to suitable destinations. The substrate nodes switch the packet flows in accordance with the instructions from the virtual network controller and periodically calculate as well as update to thecontroller about the new capacity required for their virtual
links. An end-host is a virtual machine on a virtual network.
Each end-host gets traﬃc optimal rates and multi-path splitting ratio from its host manager to adjust its outgoing traﬃc
rates. The host manager calculates and controls the traﬃc
rate of all end-hosts in its virtual network in response to thedemands requested from end-hosts and the virtual network
state updated by the controller.
2.1 Traﬃc Control in Each Virtual Network
Initially, the virtual network controller creates tunnels toconnect its virtual network’s end-hosts by adding the appropriate switching entries to the OpenFlow switches. Each
end-host monitors its aggregated traﬃc data at its output port
and sends the capacity request to its host manager periodically. On receiving the requests from all of its end-hosts, thehost manager will calculate the optimal rate for each tunnel
and reply these optimal rate back to the end-hosts. The endhosts can then adapt the traﬃc sending rates to the tunnels
accordingly. With this mechanism, the applications on each
end-host does not need to wait for the optimal rate from hostmanager but they can send their traﬃc out immediately eachtime they want.
2.2 Traﬃc Control in Substrate Network
The mission of traﬃc control in a substrate network is toadjust the virtual link capacity periodically in order to maximize the total utility. In this paper, the substrate network
uses congestion price of each virtual link to calculate thesuitable bandwidth provided to virtual links. Here, a substrate node does not need to calculate the congestion pricefor virtual links one by one by itself as previously implemented in [6]. Instead, in this paper, the substrate nodecollects the congestion price for all virtual links from thehost manager. The optimization solver in the host manager
gives the solution of dual variables, which are congestion
prices, while solving the central optimization problem for
end-host traﬃc sending rate. This way of collecting congestion price information makes our algorithm outperform [6]because the substrate nodes do not need the computational
resources to calculate the congestion price for each virtual
link and they do not need to spend a lot of time to wait for thealgorithm of calculating congestion price to converge. So,
our algorithm can re-adjust the virtual link capacity fasterand hence more frequently than the approaches in [6].
3.

Proposed Optimization Framework for Cloud Resident Data Center

3.1 Modeling and Notations

Fig. 1

System functional description.

The substrate network is modeled by a weighted, directed
graph G(V s , E s ), where V s is the set of all substrate nodes
and E s is the set of all directed substrate links. In Fig. 2,
there are three substrate nodes indexed by {1, 2, 3} and six

IEICE TRANS. COMMUN., VOL.E96–B, NO.1 JANUARY 201358

The link-path routing matrix for virtual network k [11]with its column representing each path in source-destination
pairs and its row representing each substrate link index isdenoted by H(k) , where Hli(k)j = 1 if demand i of virtual network k on path j uses virtual network link l and Hli(k)j = 0otherwise. For example, in Fig. 2, there are two routing matrices H(1) for virtual network 1 and H(2) for virtual network
2. Here, H(1) = [0 1; 0 0; 1 0; 0 0; 0 1; 0 0] because demand
1 of virtual network 1 on path 1 uses virtual network links
3 and demand 1 of virtual network 1 on path 2 uses virtual
network links 1 and 5. Similarly, the second routing matrix
H(2) = [1 0; 0 0; 0 1; 0 0; 0 1; 0 0].
3.2 Virtual-Network Centralized Algorithm
Fig. 2

System modeling example.

directed substrate links indexed by {1, 2, 3, 4, 5, 6} between
substrate node pairs {1 − 2, 2 − 1, 1 − 3, 3 − 1, 2 − 3, 3 − 2},
respectively. Similarly, a virtual network k is modeled as agraph G(V (k) , E (k) ), where k ∈ K is an element in the virtual network index set. Here, V (k) is the set of nodes invirtual network k and E (k) is the set of virtual links in virtual network k. For example, in Fig. 2, there are two virtual networks, the yellow one and the red one, each with thesame topology as that of substrate network. Let ri(k) denotethe demand i of virtual network k. The virtual network controllers use their own traﬃc engineering algorithm to control
the traﬃc flowing through their networks. And the substrate
network controls the virtual link capacity by using virtual
link congestion price information. For the example modelin Fig. 2, there is one demand on each of the two virtual
networks, denoted as r1(1) and r1(2) , respectively. There are
two paths {1 − 3, 1 − 2 − 3} for demand r1(1) and two paths{1 − 2, 1 − 3 − 2} for demand r1(2) .
Define l as the general link index, where l ∈ L denotes
the substrate link in the substrate network and l ∈ Lk denotes
the virtual link in virtual network k. Link l of substrate network has the capacity of cl . Link l of virtual network k has
capacity yl(k) . For virtual network k, each demand can usually be assigned along more than one path at the same timeas the max flow rate available on pathso let us define zi(k)jj for demand i of virtual network k. Usually, this flow rate
must be less than or equal to the instantanenous amount ofcapacity on path j that is assigned to that demand i to prevent any possible traﬃc losses. The aim of our optimization
is to find the proper values of these capacity and flow ratei(k)allocation parameters y(k)l and z j .
To define the set of all possible paths whose capacityand flow rate allocation will be found by our proposed optimization, we use the m-shortest path first algorithm [10] tofind m least cost paths from each source to each destinationin the substrate network as well as in the virtual networks.
Then we restrict our optimization search space within thoseobtainable paths only.

For each fixed k with fixed values of y(k)l : i(k) (k) maximize: U (k) z j , yl

i(k)
(k)
Hli(k)∀l ∈ Lk
subject to:j z j ≤ ylivariables:

j

zi(k)
j ≥0
zi(k)
j

∀i, j
(1)

As in [6], the objective function of the virtual network
centralized problem (1) can be any concave utility function
which varies with the capacity allocation parameters. The
first constraint implies for each virtual network that the instantateous capacity requirement or total flow rate from all
demands on their paths sharing a given virtual link cannot
exceed the capacity assigned for that virtual link by the substrate network. The second constraint states that the capacity
allocations must be non-negative.
3.3 Substrate-Network Distributed Algorithm
Our starting point is the same as [6] but with the setting ofcloud resident data center in mind, we have derived a diﬀerent virtual link capacity updated algorithm to match within
our OpenFlow based network testbed. Our centralized substrate network optimization is stated by:



(k)
w(k) U (k) zi(k)maximize:j , ylksubject to:


i



variables:

i(k)
(k)
Hli(k)
j z j ≤ yl∀l ∈ Lk , ∀kjyl(k) ≤ clk(k) i(k)yl , z j ≥ 0
(k)
zi(k)
j , yl∀l ∈ L∀i, j, k(2)Here, w(k) is the weight for each virtual network k. By using
the centralized solver for each virtual network, we can derive the new virtual link capacity updated algorithm which is
expectedly converging faster and better in processing bursty

TRINH et al.: DYNAMIC VIRTUAL NETWORK ALLOCATION FOR OPENFLOW BASED CLOUD RESIDENT DATA CENTER

59

traﬃcs than that of [6].
The problem in (2) is the convex problem because theobjective function of this problem is the positive-weighted
sum of concave objective functions (1) and the constraints(k)are aﬃne with zi(k)j , yl . The problem has coupled vari(k)ables zi(k)j , yl so we decouple it by the primal decomposi-tion method [12]. We fix the the variable yl(k) to make theproblem only varies with zi(k)j and the new problem can be divided into many centralized problems of (1). The optimization solver CVXOPT [15] which implements the so called
primal-dual interior point method [13] is used to solve eachproblem of (1) centrally in the controller of each virtual network.
The results of optimization solver for each sub-problem
and link congestion price λl∗(k) .
are optimal flow rates z∗i(k)jNow, after solving the sub-problem, we need to find the
new virtual link capacity y(k)l that we have fixed in the previous step. The updated algorithm is derived from the masterproblem as follows:
w(k) U (k) z∗i(k), y(k)
maximize:jlkvariables:y(k)l ≤ clk(k)yl ≥ 0y(k)l∀l ∈ LTo find μl , we define p∗(k) as the optimal value of (1) and p∗
as the optimal value of (3). We havep∗ =w(k) p∗(k)k

∂p∂p∗(k)=w(k)∂cl k∈K
∂cl
∗

μ∗l =

∀k, l
(3)

k

Using (6) we have partial derivative of Lagrange function as∂
L yl(k) , μl = w(k) λl∗(k) − μl
(7)
(k)
∂yl

l

The above master optimization problem is also the convex
problem because it has the same concave objective functionas (2) and the aﬃne constraints. As suggested in [13] for theconvex optimization problem, because it is easy to projecton the non-negative orthant constraint y(k)l ≥ 0, we simplify
the way to solve the problem (3) by considering the constraint y(k)l ≥ 0 as implicit constraint and solve the problem
with explicit constraint first then project the results on theimplicit constraint domain. The
 problem with explicit constraint has coupled constraint k y(k)l ≤ cl so we use the dual
decomposition [12] to decouple it. We find the Lagrangefunction of (3) as follow:
L yl(k) , μl⎛⎞  ⎜⎜⎜ (k) ⎟⎟⎟(k) (k) ∗i(k) (k)⎜= w U z j , yl − μl ⎜⎝ yl −cl ⎟⎟⎠
k
l
k


   (k) (k) (k) ∗i(k) (k)yl μl + μl cl(4)= w U z j , yl −kwhere T s is the time period for updating virtual link capacity in the substrate network and the updated time argument
has been appended in the parenthesis following the variableyl(k) . []+ denotes the projection on to non-negative orthantdomain.
Like [13], we have the partial derivative of objectivefunction at the optimality as the link congestion price so⎛⎞∂ ⎜⎜⎜⎜ (k)  ∗i(k) (k) ⎟⎟⎟⎟
∗(k)
U
,
y
(6)
z
⎜
⎠ = λljl ⎟(k) ⎝∂yl k∈Kll

Note that μl is the dual variable for the master problem which is diﬀerent from λ(k)l , the dual variable of subproblems.
We use the subgradient projection method to find thesupremum of problem (4) which has implicit constraint of
non-negative orthant and the variable of y(k)l . The update
function for y(k)isl⎡⎤
 (k) ⎥⎥+⎢⎢⎢ (k)∂(k)yl (t + T s ) = ⎢⎢⎣yl (t) + α (k) L yl , μl ⎥⎥⎥⎦
(5)
∂yl



w(k) λl∗(k)

k∈Kl

∂y(k)
l
∂cl

(8)

where Kl is the set of virtual networks hosted on substratelink l.
In practical networks, a service provider prefers to allocate all their capacity fairly to increase the qualityof ser
vices. In our system, by constraining on cl = k∈Kl y(k)l , weallocate fairly all of our residual capacity to virtual network
customers:
y(k)
∂y(k)
l
=  l (κ)
∂cl
κ∈K y
l

(9)

l

Hence, we have from (8), (9) that(k) ∗(k) (k)k∈Kl w λl yl
∗
μl =

(k)
k∈Kl yl(10)

And the final virtual link capacity update function canbe obtained by combining (5),(7),(10) :yl(k) (t + T s )⎡⎢⎢⎢⎢ (k) ∗(k)= y(k)⎣w λl −
l (t)+α ⎢⎤+(k) ∗(k) (k)λl yl (t) ⎥⎥⎥
⎥⎥⎦

(k)
y
(t)
k∈Kl lk∈Kl w(11)

As a summary, in (11), we can find the value of y(k)l at time
t + T s from the previously updated value of y(k)l at time t.
In the recursion, α is a constant stepsize that can be chosen
through experiments to improve the algorithm convergence.
The value of link congestion price λl∗(k) in virtual network
k can be obtained by centralized optimization solver. This

IEICE TRANS. COMMUN., VOL.E96–B, NO.1 JANUARY 201360

equation also has a reasonable interpretation because if theweighted rate of utility increase per unit of capacity being
added for a given virtual link l, i.e. the term w(k) λl∗(k) , isgreater than the rate of utility increase as averaged over all
the virtual link capacity upgrade, then that virtual link l ofthe virtual network k should be allocated more capacity. On
the contrary, if the weighted rate of utility increase per unitof capacity being added for a given virtual link l is lower
than the rate of utility increase as averaged over all the virtual link capacity upgrade, then that virtual link l should be
assigned less capacity.

We have built a testbed to implement and evaluate our optimization algorithm with a rack of seven computers named
PC1-5 and TA, TB, respectively. Each computer is equippedwith Core 2 quad 2.40 GHz and 4 GBytes of RAM. Ubuntu
OS 11.04 with the core of 2.6.38 has been installed on eachphysical computer.

3.4 Convergence and Optimality

4.2 Logical Model

Theorem: The updated Eq. (11) converges to optimal pointof (2) if:

The logical model of our network is presented in Fig. 3. In
this model, three substrate nodes have been created by installing OpenFlow switch software v0.8.9r2 on computers
PC1-3 to make them work as PC-based switches. FlowVisor has been used to create a virtualization layer on those
substrate nodes. The virtual network controller has been instantiated by a Python script running on top of the network
operating system NOX. We have written a Python script to
add the switching entries to OpenFlow switches and control them to forward packets according to VLAN IDs. To
implement end-hosts to split the traﬃc through paths andlimit the rate of outgoing traﬃcs, we have written a Python
script using Scapy [14] to create two kinds of packets with
VLAN ID = 2 and VLAN ID = 3. And the end-hosts send
the packets to output ports according to the control information from the central host manager. This host manager has
been implemented on PC5 by a Python script which communicates with all end-hosts and the controller in the corresponding virtual network. This script periodically takes traffic demands from end-hosts and virtual link capacity value
updates from substrate nodes as its inputs and use CVXOPT [15] to calculate the optimal rates for all end-hosts• The problem (1) is convex optimization.
• The virtual link bandwidth allocation is updated after
the convegence of (1)• The stepsize α in (11) is small enough or diminishing(diminishing stepsize usually converge faster constantstepsize).
Proof: From the above interpretation of (11) about the
principal for increasing and decreasing bandwidth of each
virtual link y(k)l , the aggregated utility on each physical
link
l
and
hence,
total utility overall substrate network: (k) (k) ∗i(k) the, y(k))
will be increased after each virtualk w U (z jllink capacity
updatedperiod T s . Because we always keep

(k)
,
L(y
,
μ
cl = k y(k)l ) increases monotonically after evllery period of updating virtual link capacity. But, L(yl(k) , μl )is concave function so it is only able to increase until the
maximum point which also be the stationary point when y(k)lmoves to the limited point ỹ(k)l . At the limited point we have:w(k) λl∗(k) =(k) ∗(k) (k)λl ỹl(k)k∈Kl ỹlk∈Kl w(12)

4.

Implementation

4.1 General Testbed Description

It means that at the limited point ỹ(k)l , the weighted rateof utility increase per unit of capacity being added for agiven virtual link l is equal to the rate of utility increase as
averaged over all the virtual link capacity upgrade and y(k)ldoes not change anymore.
At the ỹl(k) :
 (k)
 (k)
∂
L(ỹ(k)k yl ≤ cl , and μl ( k yl − cl ) =l , μl ) = 0 ∀l, k;∂y(k)l0. The KKT conditions [13] are satisfied for the convex
problem of (3), then the limited point of (11) is the optimal
point of (3).
Because Eq. (1) is converged before the virtual linki(k)= ỹ(k)=bandwidth update time, at y(k)ll , we also have z j

and they are the optimal point yl∗(k) and z∗i(k)for thez∗i(k)
jj
problem of (2).

Fig. 3

Logical model.

TRINH et al.: DYNAMIC VIRTUAL NETWORK ALLOCATION FOR OPENFLOW BASED CLOUD RESIDENT DATA CENTER

61

and congestion price values for all virtual links in the virtual network. There are three networks used to connect allelements of system as depicted in Fig. 3. Controller network (172.16.0.x) is used for controllers on PC4 to send
control signals to switches PC1-3. Host control network(192.168.0.x) is used by the host manager to get informationfrom end-hosts and controllers as well as to send control signals to end-hosts. The main network is used for end-hosts
in a virtual network to send traﬃcs to each other. Switches
are connected to the first controller (named ENG) via tcp
port:7000 and the second controller (named SCI) via tcp
port:9000.
4.3 Virtual-Network Centralized Algorithm Implementation
We have implemented the throughput-sensitive centralizedalgorithm on each host manager using Python CVXOPT[15] with the objective function of maximizing the overall
network throughput, meanwhile keeps the link capacity uncongested as follows:⎞⎛⎜⎜⎜ ⎟⎟⎟ 
 
(k)
i(k)⎟
⎜
wi log ⎜⎝⎜ z j ⎟⎠⎟ −q exp u(k)
(13)
max :
l
i

j

l∈Lk

where the utilization u(k)l of virtual link l can be calculated(k) (k)from ul(k) = H y(k)∗z and q serves as a weighting coeﬃcientl

for regulating the utilization of virtual links. This objectivefunction is diﬀerent from [6] in that we add weight w(k)i toeach demand for controlling the network resources provided

OpenFlow switches. Each OpenFlow switch on receiving
the congestion price calculates the new capacity of its virtual links by using the equation that we have derived in (11).
The new virtual link capacity information is then updated tothe host manager, which in turn uses this information in its
capacity constraints to calculate the optimal flow rate for
end-hosts in the next optimization step.
4.5 Simulator
Since our physical testbed is restricted to 7 PCs with 3
switching nodes, we have implemented our algorithm in
MATLAB environment for two nodes topology and Abilene topology [6] to test and compare our algorithm withthe previous approach in larger topology. We not only use
throughput-sensitive utility function for both virtual networks as in testbed implementation but also add the delaysensitive utility function which tries to minimize the total
delay of network as follows:


(1)
zi(1)
Hli(1)(14)min:jj (pl + f (ul ))ijl

In our testbed implementation, with two throughputsensitive utility functions, congestion price alone is enoughto reflect the demand for more bandwidth of each virtual
link. But in our simulation, the throughput-sensitive utility
function and delay-sensitive utility function are so diﬀerent
in the form, we have added ∂y∂(k) Ul(k) to congestion price λ∗l tolbetter reflect the demand for bandwidth than the congestion
price alone.

r(k)ito each demand. This weight is calculated by w(k)i =  r(k) ,i iwhere ri(k) is the demand i of virtual network k. End-hosts
TA, TB periodically send the requested demand to the hostmanager which calculates the optimal flow rate for each endhost to send its traﬃc through each path. Upon receiving thisoptimal sending rate, end-hosts then adjust their outboundflow rate. We use Scapy [14] to create the packets with thewanted VLAN IDs to split traﬃc to diﬀerent paths. For example, if end-host TA receives the optimal rate of (100, 40),
it knows that it should send the traﬃc with the rate of 100
packets/s on VLAN 2 and 40 packets/s on VLAN 3. The
end-host uses Scapy to create and send 100 packets with
VLAN-ID = 2 as well as 40 packets with VLAN-ID = 3 toswitch PC1. Then, at switch PC1, the packets with VLANID = 2 are forwarded through the upper path with two hops
and the packets with VLAN-ID = 3 are forwarded throughthe lower path with one hop.

5.

Evaluation

5.1 Simulation Results
Figure 4 compares the time to convergence between our proposed algorithm and Davinci algorithm [6] in two nodes
topology. The upper graph of Fig. 4 shows that with thesame setting of q = 0.5, w1 = 1, w2 = 105 α = .2 andr1(1) = 110 Mbps, our proposed algorithm needs nearly thesame number of outer iterations, which are the number of
iterations to solve the master problem (3) distributedly, as in

4.4 Substrate-Network Distributed Algorithm Implementation
We have implemented our substrate algorithm on each
OpenFlow switch. After each time a host manager completes calculating the optimal rate for all end-hosts, the hostmanager sends the newly updated congestion price to theFig. 4Comparing with Davinci in two nodes topology.

IEICE TRANS. COMMUN., VOL.E96–B, NO.1 JANUARY 2013

62

Fig. 5

Stepsize α vs. convergence in Abilene topology.

Fig. 6

Traﬃc on ENG and SCI network.

[6]. But, as showed in the lower graph, our algorithm needs
much shorter time to converge than the one in [6]. The reason for this phenomenon is that for each outer iteration weneed maximum 0.2 seconds to solve optimization problems
on two virtual networks centrally but [6] needs 2 seconds
to solve them distributedly. The more time needed for [6]to solve problem at each iteration make it converge slower
than our proposed algorithm.
Figure 5 presents the number of iterations to convergence of our algorithm in the Abilene topology. From thefigure, the algorithm converges very slow when stepsize α
is so small and diverses when stepsize α is large. The reason is that when α is large, the searching point will jump
through optimal point after each iteration. Also from thefigure, the graph with demand r1(1) = 200 Mbps on delay sensitive network converges faster than the graph with demand
r1(1) = 110 Mbps. The reason of this phenomenon is that theinitial capacity for all virtual links of all virtual networks are
set to be 500 Mbps which is the half of each substrate link
capacity. The initial virtual link capacity vector is the initialpoint for our optimization algorithm. This initial point isnearer to the solution of demand 200 Mbps than the solutionof demand 110 Mbps. So, the algorithm with input demandof 200 Mbps converges faster than the algorithm with input
demand of 110 Mbps.
5.2 Testbed Evaluation Results
Figure 6 depicts the dynamics of actual traﬃc on ENG virtual network (upper graph) and SCI virtual network (lower

Fig. 7

Time to converge vs. T s .

graph). This result is based on the demands which arechanged randomly every 40 optimization iterations and α
which is 0.05 at the beginning and being added by 0.05 eachtime the demand changes. The substrate link capacity is set
to 5 Mbps. From the figure, the convergence rate increases
after each time demand changes. But there are some periods such as 120, 200, 320, the convergence rate decreases
even with higher α. This phenomenon is caused by the largechanging in demand. Our algorithm uses the optimal points
from previous optimization period to be the initial point for
the next optimization period. If the initial point is so far
from the demand, our algorithm needs more iterations toconverge.
Figure 7 depicts the virtual link updated period T s andthe time to convergence in 2 demand patterns which are: increase with 1 Mbps step and 2 Mbps step. From the figure, if
the virtual link update period is smaller than the maximum
time to solve the optimization problem in each virtual network added with the communication time between end hosts
with HostManager of that virtual network which is equal 0.7
in our case, our algorithm will need very long time to converge. If T s ≥ 0.7 second, the virtual network optimization
problem is guaranteed to be solved completely before theupdated time of our proposed algorithm (11) and our algorithm is converged. When our proposed algorithm converge,
the time to convergence is quite linear with the iteration period (T s ). The reason is that the number of iterations needed
to solve the master problem is nearly constant. The linear
increase of time to converge is only caused by the increasein the updated time period T s .
Figure 8 shows how virtual capacity of each virtual network adapts when there is a link-down event from iteration
36 − 148. At iteration 36, when the physical link VLAN
3 is down, the capacity which was allocated to both vir(2)tual networks ENG (y(1)
2 ) and SCI (y2 ) from physical link
VLAN 3 is vanished. The capacity allocated to virtual net(2)work ENG (y(1)
1 ) and SCI (y1 ) from physical link VLAN 2
is adjusted in around 20 iterations by our updated Eq. (11)to converge to the new optimal point that the allocated virtual link capacity are proportional to the demands from both
virtual networks. When the physical link of VLAN 3 is up
again at iteration 148, our updated algorithm immediately
allocates the equal bandwidth 3.5 Mbps to each virtual link
hosted on the physical link VLAN 3. This initial allocation

TRINH et al.: DYNAMIC VIRTUAL NETWORK ALLOCATION FOR OPENFLOW BASED CLOUD RESIDENT DATA CENTER

63

Fig. 8Link recovery.

phenomenon caused by fair allocation of Eq. (9). After the
initial allocation, our algorithm gradually adjusts the allocated capacity to the new optimal point which allocates total
3 Mbps of traﬃc for the virtual network ENG and 7 Mbps oftraﬃc for the virtual network SCI.
6.

Conclusion

In this paper, we have derived an algorithm to dynamicallyallocate the capacity to virtual network links for maximizing
the aggregated utility. With the cloud resident data centersetting in mind, we have used the centralized algorithm toimplement in each virtual network to be suitable with OpenFlow centralized controller. At the substrate network, wehave derived a new updated algorithm to make use of congestion price which is calculated from the centralized controllers. We have implemented our algorithm in MATLAB
as well as testbed environment and the results show that ouralgorithm converge to the optimality faster than the previous
approach so it can use physical resource more eﬀectively.
To make any optimization algorithm work in the realworld, we need to tune many parameters of our algorithm.
The convergence time of our algorithm is based heavily
on the convergence time of each centralized algorithm oneach virtual network. In the future, we intend to improvethe convergence rate of virtual network algorithm by precalculating the optimization problem in virtual networks
with all the input demands and make a mapping table between traﬃc demands and primal/dual solutions. When
there is a demand come to the network, the host manager
only needs to find the optimal results from the mapping table. Future results will be reported accordingly.
References[1] E. Keller, D. Drutskoy, J. Szefer, and J. Rexford, “Cloud resident
data center,” http://www.cs.princeton.edu/research/techreps/TR914-11[2] “Amazon virtual private cloud (amazon vpc),” http://aws.amazon.
com/vpc/, 2011.
[3] M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, andA. Vahdat, “Hedera: Dynamic flow scheduling for data center networks,” Proc. 7th USENIX Conference on Networked Systems Design and Implementation, p.19, 2010.

[4] M. Alizadeh, A. Greenberg, D. Maltz, J. Padhye, P. Patel,
B. Prabhakar, S. Sengupta, and M. Sridharan, “Data center tcp(dctcp),” ACM SIGCOMM Computer Communication Review,
pp.63–74, 2010.
[5] K. Ousterhout and J. Rexford, “Reef: A reactivate, eﬃcient, andflexible system for internet traﬃc management,” 2011.
[6] J. He, R. Zhang-Shen, Y. Li, C.Y. Lee, J. Rexford, and M. Chiang,“Davinci: Dynamically adaptive virtual networks for a customized
internet,” Proc. 2008 ACM CoNEXT Conference, CoNEXT’08,
pp.15:1–15:12, New York, NY, USA, 2008.
[7] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar,
L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: Enabling innovation in campus networks,” ACM SIGCOMM Computer Communication Review, vol.38, no.2, pp.69–74, 2008.
[8] R. Sherwood, G. Gibb, K. Yap, G. Appenzeller, M. Casado,
N. McKeown, and G. Parulkar, “Flowvisor: A network virtualization layer,” OpenFlow Switch Consortium, Tech. Rep. 2009.
[9] N. Gude, T. Koponen, J. Pettit, B. Pfaﬀ, M. Casado, N. McKeown,
and S. Shenker, “Nox: Towards an operating system for networks,”
ACM SIGCOMM Computer Communication Review, vol.38, no.3,
pp.105–110, 2008.
[10] D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput.,vol.28, no.2, pp.652–673, 1998.
[11] M. Pióro and D. Medhi, Routing, flow, and capacity design in communication and computer networks, Elsevier/Morgan Kaufmann,
2004.
[12] D. Palomar and M. Chiang, “A tutorial on decomposition methods
for network utility maximization,” IEEE J. Sel. Areas Commun.,vol.24, no.8, pp.1439–1451, 2006.
[13] S. Boyd and L. Vandenberghe, Convex optimization, Cambridge
Univ Pr, 2004.
[14] “Scapy.” http://www.secdev.org/projects/scapy[15] “Cvxopt: Python software for convex optimization.” http://abel.ee.
ucla.edu/cvxopt/index.html

Tri Trinh
received Bachelor as well as Master degree from Hanoi University of Science andTechnology, Vietnam in 2004 and 2006 respectively. He is now a Ph.D. student in the Department of Electrical Engineering, Chulalongkorn
Unversity since 2009. In 2011, he was an exchanged researcher in Esaki’s lab, The University of Tokyo. His research interest is Network Virtualization, Cloud Resident Data Center, OpenFlow, Traﬃc Engineering, Network
Optimization.

Hiroshi Esaki
received the Ph.D. degreefrom the University of Tokyo, Tokyo, Japan, in
1998. In 1987, he joined the Research and Development Center, Toshiba Corporation. From1990 to 1991, he was with the Applied Research Laboratory, Bell-Core Inc., NJ, as a Residential Researcher. From 1994 to 1996, he
was with the Center for Telecommunication Research, Columbia University, New York. Since
1998, he has served as a Professor at the University of Tokyo, and as a board member of WIDE
Project. Currently, he is the Executive Director of IPv6 promotion council,
Vice President of JPNIC, IPv6 Forum Fellow, Director of Green Universityof Tokyo Project, and Director of WIDE Project.

IEICE TRANS. COMMUN., VOL.E96–B, NO.1 JANUARY 2013

64

Chaodit Aswakul
received the B.Eng. degree with 1st class honour in Electrical Engineering from Chulalongkorn University, Thailand, in 1994. From 1995 to 2000, he received
the Ananda Mahidol Foundation scholarship to
study for Ph.D. at the Imperial College of Science, Technology and Medicine, University of
London, U.K. After getting Ph.D. in communications networking, he returned to Thailand andis currently an assistant professor at the Department of Electrical Engineering, Chulalongkorn
University. In 2008–2009, he has also served as the manager of the Next
Generation Network Testing/Trial Use Project in Phuket of the National
Telecommunications Commission of Thailand. He is the cofounder of theuniversity’s Network Research Group with focuses on researching in thequality of service and reliability issues of both communication and transportation network systems.