 resource utilization and expected latency and solution number of machines used number of machines used Input Heuristic Optimization Expected latency Present results to user method computation Figure 3.10 VNF placement system overview. 3 Network Function Virtualization Decision variables: The decision variables describe the assignment of VNF instances to leaf nodes, the mapping of each service chain to one or more paths in the network, the volume of flow for each chain along each of its paths, the rate of traffic into each node, and performance metrics associated with the solution. - Xv.1 E (0,1) indicates whether an instance of VNF type U is placed on leaf l. - ye., E [0,1] is the fraction of traffic for the ith function in service chain C that is served by leaf node l. - Zi.k.I E [0, 1] is the fraction of traffic going from the ith to (i + 1)st function in service chain C that travels from leaf node k to leaf node l. - bk > 0 is the total traffic rate in packets per second into node k E N. - p is the maximum node utilization over all nodes in the network. Constraints: The MIP's constraints ensure that flow for each service chain is conserved at each node, that the solution does not use more than the available network resources, and that the maximum utiliza- tion metric is measured. Model objectives: The objective is to minimize a weighted combina- tion of the number of nodes utilized and the maximum utilization over all nodes in the network. (3.1) When B=0, the objective reduces to minimizing the maximum utilization over all nodes in the network. This choice of objective has the effect of distributing the traffic as uniformly as possible in order to reduce the highest utilization over all nodes. If instead B = 1, the objective becomes minimizing the total number of nodes used to host VNFs. A placement that minimizes the number of VNFs tends to concentrate traffic in part of the network, leaving other network resources unused. Solving the MIP over a range of B E [0, 1] yields a set of solutions that represent di