132 5 SDN and NFV in 5G
additional checks to ensure no violation of other resource constraints.
Due to the space limitation, we do not include this part in Algorithm 2.
The high-level idea of Algorithm 1 is, VNF placement for chain c follows a “best-fit” strategy, that is, for each NF chain c, the required NFs
are first sorted by their resource demand in a descending order. Next,
each time the algorithm selects an unplaced NF of chain c with the
highest resource demand, and places it to the pod in PodListc with the
least (but sufficient) CPU resources. PodListc is initialized as an empty
list for NF chain c, and records all the pods used by c. If PodListc is
empty, or no such pod can be found in PodListc, the algorithm selects
the pod with the most resources from the entire pod list PodList, add
it to PodListc, and repeat VNF placement in Step 3. In this study, we
assume sufficient pods to avoid NF blocking. A variant of the problem
can be minimizing the block ratio of NF placement, given a limited
number of pods. In Step 3, as pod usage is optimized per NF chain
basis, this does not automatically lead to minimization of overall pod
number. Therefore, we introduce Step 4, which conducts an additional
optimization to consolidate pods for all NF chains.
5.2.4 Verification of Service Function Chaining
The traditional approach to detecting configuration errors is to apply
network verification. Unfortunately, current network verification
techniques focus on verifying the flow table rules in Layer 2 and
Layer 3 devices against basic invariants such as loop freeness and no
blackholing [74, 110]. These approaches assume a simple stateless
forwarding model where the action solely depends on a match on
the header fields of each packet. However, many NFs are stateful; the
handling of a packet depends not only on the current packet but also
on previously encountered packets, in some cases, on the content of
packets. For example, a firewall, discussed earlier, allows packets from
external hosts only if it has previously seen an outgoing packet from
internal host for that connection.
One way to extend verification to NFs is using test packets to probe
the NF and determine the set of invariants that are satisfied or violated given the NF’s current state. These active probing techniques can
detect problems after they are deployed, but we still need static verification to capture the problems before the deployment. In addition,
these techniques require access to the source code but, due to proprietary reasons, most NFs are closed source. An alternate approach is
additional checks to ensure no violation of other resource constraints.
Due to the space limitation, we do not include this part in Algorithm 2.
The high-level idea of Algorithm 1 is, VNF placement for chain c follows a “best-fit” strategy, that is, for each NF chain c, the required NFs
are first sorted by their resource demand in a descending order. Next,
each time the algorithm selects an unplaced NF of chain c with the
highest resource demand, and places it to the pod in PodListc with the
least (but sufficient) CPU resources. PodListc is initialized as an empty
list for NF chain c, and records all the pods used by c. If PodListc is
empty, or no such pod can be found in PodListc, the algorithm selects
the pod with the most resources from the entire pod list PodList, add
it to PodListc, and repeat VNF placement in Step 3. In this study, we
assume sufficient pods to avoid NF blocking. A variant of the problem
can be minimizing the block ratio of NF placement, given a limited
number of pods. In Step 3, as pod usage is optimized per NF chain
basis, this does not automatically lead to minimization of overall pod
number. Therefore, we introduce Step 4, which conducts an additional
optimization to consolidate pods for all NF chains.
5.2.4 Verification of Service Function Chaining
The traditional approach to detecting configuration errors is to apply
network verification. Unfortunately, current network verification
techniques focus on verifying the flow table rules in Layer 2 and
Layer 3 devices against basic invariants such as loop freeness and no
blackholing [74, 110]. These approaches assume a simple stateless
forwarding model where the action solely depends on a match on
the header fields of each packet. However, many NFs are stateful; the
handling of a packet depends not only on the current packet but also
on previously encountered packets, in some cases, on the content of
packets. For example, a firewall, discussed earlier, allows packets from
external hosts only if it has previously seen an outgoing packet from
internal host for that connection.
One way to extend verification to NFs is using test packets to probe
the NF and determine the set of invariants that are satisfied or violated given the NF’s current state. These active probing techniques can
detect problems after they are deployed, but we still need static verification to capture the problems before the deployment. In addition,
these techniques require access to the source code but, due to proprietary reasons, most NFs are closed source. An alternate approach is