5.2 Service Function Chaining 131
Algorithm 2 Optical NFV Placement algorithm
procedure Place(PodList, ChainList, NFList
create a bipartite graph N with two sets of nodes for all elements in
P and G
for each NF chain c in ChainList do
Initiate an empty pod list PodListc.
Sort the NFs needed by c in a descending order by resource
demand
end for
for each unprocessed NF n of c do
Set flag=false
Sort PodListc in an ascending order by available resource and
select the first pod p
if p has enough resources for n then
provision n by p and set flag=true
else
go to the next pod p in PodListc
end if
if flag=false then
add the most-available-resource pod pm of PodList to PodListc.
Provision n by pm.
end if
end for
In PodList, select pod pa with the least resources consumed by NFs
provisioned in Step 3, and pod pb with the most available resources.
Move all the NFs of pa to pb if resources allow and continue on 4a,
otherwise end the algorithm.
constraint or by simply having the operator manually assign VNFs for
the chain in question.
According to the problem statement above, we formulate the problem of NF placement as integer linear programming (ILP). Since the
ILP formulation has only binary variables, it becomes binary integer
programming (BIP). In this formulation, we assume integrity of NF,
that is, an NF cannot be split into more than one pod.
However, the BIP-based solution does not scale with the size of the
input (e.g., C, M, and N); therefore, we design a heuristic algorithm for
computation efficiency, shown in Algorithm 2. Similar to BIP, Algorithm 2 takes CPU as the most limiting resource and may conduct