Hi,

I am working on an optimization problem dealing where the objective is to find a best placement of Virtual Machines given a physical network composed of several servers connected via switches/routers. The goal in the objective function is to maximize a profit. We associate to each server s a profit P_s.

The inputs of the mathematical program are the set of request R (which are the virtual machines and their inter-connectivity) and the physical network topology defined as a bidirectional graph.

I have two decision variables defined as follows :

a[r,u,x] = 1 if virtual machine u of request r is deployed  on server x 0 otherwise. 
b[r,u,v,x,y] = 1 if physical link (x,y) of request r is allocated to virtual link (u,v) 0 otherwise.

Each virtual machines asks for a set of resources (cpu, memory, storage) and each server has a set of available resources (cpu, memory, storage). Each physical link has a capacity in terms of bandwidth and delay(latency) and connects two servers.

I have defined following this a set of constraints regarding the non violation of the servers and links capacity.

Here is the link to the mathematical program I have implemented using Gurobi via Python API for a complete description.

For the sake of simplicity suppose we have a request of 3 VMs connected together in a linear topology say :

VM1<---> VM2 <---> VM3.

I am getting this output :

Optimal solution found (tolerance 1.00e-04)
Best objective 9.200000000000e-02, best bound 9.200000000000e-02, gap 0.0000%
Optimal objective: 0.092

    Variable            X 
-------------------------
a_request_id_i_j[0,1,7]            1 
a_request_id_i_j[0,2,4]            1 
a_request_id_i_j[0,3,1]            1 
b_request_id_uv_xy[0,1,2,7,6]            1 
b_request_id_uv_xy[0,1,2,3,4]            1 
b_request_id_uv_xy[0,1,2,2,4]            1 
b_request_id_uv_xy[0,2,3,4,3]            1 
b_request_id_uv_xy[0,2,3,2,1]            1 
b_request_id_uv_xy[0,2,3,4,2]            1 
b_request_id_uv_xy[0,2,3,3,1]            1
b_request_id_uv_xy[0,2,3,3,4]            1 
b_request_id_uv_xy[0,2,3,2,4]            1

The thing is that, the last two values are not correct i.e the constraint c1 and c2 if we verify them at hand will not yield the same value (I am not sure where is the mistake though!) while other values for beta are correct:

b_request_id_uv_xy[0,2,3,3,4]            1 
b_request_id_uv_xy[0,2,3,2,4]            1

The meaning of c1 and c2 is given a virtual link (u,v) connecting two VMs say u and v : if VM u is placed on x or VM v is placed on v then allocate a physical link where they are placed.

I formulated a constraint saying that if b[r,u,v,x,y] equals 1 then either VM u is placed on x or VM v is placed on y or both VMs are placed on x and y respectively by : b[r,u,v,x,y] <= a[r,u,x] + a[r,v,y]. This fixed the issue I mentioned earlier and gives this result :

Optimal solution found (tolerance 1.00e-04)
Best objective 9.200000000000e-02, best bound 9.200000000000e-02, gap 0.0000%
Optimal objective: 0.092

Variable            X 
-------------------------
a_request_id_i_j[0,1,7]            1 
a_request_id_i_j[0,2,4]            1 
a_request_id_i_j[0,3,1]            1 
b_request_id_uv_xy[0,1,2,7,6]            1 
b_request_id_uv_xy[0,1,2,3,4]            1 
b_request_id_uv_xy[0,1,2,2,4]            1 
b_request_id_uv_xy[0,2,3,4,3]            1 
b_request_id_uv_xy[0,2,3,2,1]            1 
b_request_id_uv_xy[0,2,3,4,2]            1 
b_request_id_uv_xy[0,2,3,3,1]            1

I am having an issue where several physical links are allocated to a virtual link. For instance, physical link (3,4) and (2,4) are allocated to the virtual link (1,2) i.e b_request_id_uv_xy[0,1,2,3,4]=1 and b_request_id_uv_xy[0,1,2,2,4]=1. I need to have only one. Do I have to reformulate it in such a way to say : allocate only one physical link where the VM (or the pair of VMs) is(are) placed ?

Another point is, I need to find a constraint that will help me to build a path between each pair of virtual machines. The model so far is not able to perform this task, I understand it has to be formulated first and I do not know how and where to start from to do so.

Any suggestions will be highly appreciated.

asked 01 Nov '17, 21:53

src_src's gravatar image

src_src
213
accept rate: 0%


Hi,

I was wondering whether my question is clear or not regarding my issue. Is it clear for readers ? Any feedback is welcome and appreciated.

link

answered 02 Nov '17, 21:20

src_src's gravatar image

src_src
213
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×127
×7

Asked: 01 Nov '17, 21:53

Seen: 300 times

Last updated: 02 Nov '17, 21:20

OR-Exchange! Your site for questions, answers, and announcements about operations research.