Optimal Placement and Traffic Steering of VNFs and Edge Servers using Column Generation in Data Center Networks

Abstract

Telecom Service Providers (TSPs) were traditionally dependent on physical devices to provide end-to-end communication. The services provided were high quality and stable but low in agility and hardware-dependent. As the demand for quick deployment of diverse services increased, TSP-s needed much higher flexibility and agility. This is how Network Functions Virtualization (NFV) came into being. NFV is the concept of replacing dedicated hardware with commercial-off-the-shelf (COTS) servers. It decouples the physical hardware and the function running on it. A network function can be dispatched as an instance of the software, called a Virtual Network Function (VNF). Thus, a service can be decomposed into several VNFs that can be run on industry-standard physical servers. The optimal placement of these VNFs is a potential question for TSPs to reduce the overall cost.

We first study a network operations problem where we optimally deploy VNFs in Service Chains (SCs) such that the maximum consumed bandwidth across network links is minimized. The network parameters (link bandwidths, compute capacities of nodes, link propagation delays, etc.) and the number of SCs are known a priori. The problem formulated is a large Mixed-Integer Linear Program (MILP). We use the Column Generation (CG) technique to solve the problem optimally. Through various examples, we show the power of CG. We compare our results with recent heuristics and demonstrate that our approach performs better as it gives exact optimal solutions quickly.

Second, we extend our previous setup to the online case where the number of SCs is not known a priori. We serve SC requests as they come. A new SC is implemented on the "residual network" while the previously deployed SCs are undisturbed. The problem formulated is a large MILP, and we use CG as the solution technique. The results show the percentage improvement in the solutions over those obtained using heuristics.

Next, we study a network design problem in an Edge Computing Environment. A general communication network has a single Data Center (DC) in its "core," which serves as a gateway to the Internet. For delay-constrained services of the kind needed by online gaming, this model does not suffice because the propagation delay between the subscriber and the DC may be too high. This requires some servers to be located close to the network edge. Thus, the question of the optimal placement of these edge servers arises. To lower the network design cost, it is also essential to ensure good traffic routing, so that aggregate traffic on each link remains as low as possible. This enables lower capacity assignment on each link and thereby minimizes design cost.

We study a novel joint optimization problem of network design cost minimization. Edge server placement cost and link capacity assignment cost constitute the total cost. The problem formulated is a large MILP, and we again use CG to solve it. We compare our results with many heuristics and show the improvement in design cost.

Finally, we extend the above work by relaxing some assumptions and constraints. Unlike previously, we consider servers with different capacities. Also, a server can serve more than one request depending on its core capabilities. We also consider the split-and-merge of an SC through various paths in the network. The formulated problem can also provide the minimum number of servers to be used. Again, the formulation is a large MILP, and CG is used to solve it exactly.