PaperlayerView exact revision on arXiv

Source-linked AI summary

On Orchestrating Virtual Network Functions in NFV

Md. Faizul Bari, Shihabur Rahman Chowdhury, Reaz Ahmed, Raouf Boutaba

arXiv:1503.06377v2cs.NI

TL;DR

The paper addresses how to place and route VNFs while balancing operational cost, resource use, and service-level constraints. It formulates the problem as an ILP and introduces a dynamic-programming heuristic for larger networks. The heuristic stays close to optimal solutions, while experiments report substantial OPEX reductions versus hardware middleboxes.

  • Problem

    VNF-OP determines VNF counts, placements, and routes that minimize operational costs and resource fragmentation while respecting capacities and SLOs.

  • Method

    The paper combines a CPLEX-based ILP for small networks with a dynamic-programming heuristic for larger instances.

  • Results

    The heuristic produces solutions within 1.3 times the optimum, while trace-driven simulations report up to 4x lower network OPEX with VNF orchestration.

  • Takeaways & Limitations

    Dynamic VNF orchestration can adapt active VNF counts and locations to changing traffic conditions while reducing network OPEX.

Abstract

from arXiv · show

Middleboxes or network appliances like firewalls, proxies and WAN optimizers have become an integral part of today's ISP and enterprise networks. Middlebox functionalities are usually deployed on expensive and proprietary hardware that require trained personnel for deployment and maintenance. Middleboxes contribute significantly to a network's capital and operational costs. In addition, organizations often require their traffic to pass through a specific sequence of middleboxes for compliance with security and performance policies. This makes the middlebox deployment and maintenance tasks even more complicated. Network Function Virtualization (NFV) is an emerging and promising technology that is envisioned to overcome these challenges. It proposes to move packet processing from dedicated hardware middleboxes to software running on commodity servers. In NFV terminology, software middleboxes are referred to as Virtualized Network Functions (VNFs). It is a challenging problem to determine the required number and placement of VNFs that optimizes network operational costs and utilization, without violating service level agreements. We call this the VNF Orchestration Problem (VNF-OP) and provide an Integer Linear Programming (ILP) formulation with implementation in CPLEX. We also provide a dynamic programming based heuristic to solve larger instances of VNF-OP. Trace driven simulations on real-world network topologies demonstrate that the heuristic can provide solutions that are within 1.3 times of the optimal solution. Our experiments suggest that a VNF based approach can provide more than 4x reduction in the operational cost of a network.

I. INTRODUCTION

The paper frames VNF orchestration as a cost-and-performance problem arising from proprietary middleboxes and ordered service chains. It develops an ILP for small networks and a fast heuristic for larger instances.

  • Proprietary middleboxes impose high CAPEX and OPEX, require trained personnel, and are difficult to modify or relocate.
  • Ordered middlebox chains make manually configured routing cumbersome and error-prone as network conditions change.
  • NFV moves packet processing from hardware middleboxes to software middleboxes running on commodity servers.
  • VNF-OP seeks VNF counts, placements, and routes that minimize OPEX, SLO-violation penalties, and resource fragmentation while preserving suitable paths.
  • The paper formulates VNF-OP as an ILP implemented in CPLEX for optimal small-network solutions.
  • The proposed heuristic finds solutions within 1.3 times the optimum and is evaluated on real-world topologies and traffic traces.

B. Virtualized Network Functions (VNFs)

This section models VNFs, traffic requests, resources, and operating costs for provisioning ordered network services. It defines the optimization setting and the constraints governing feasible placements and routes.

  • Each VNF type has deployment cost, resource requirements, processing capacity, and processing delay.
  • Hardware requirements and operator preferences restrict the servers on which each VNF type may be provisioned.
  • A traffic request specifies ingress and egress switches, bandwidth demand, SLA delay, and an ordered VNF sequence.
  • The directed traffic graph explicitly represents switches, VNFs, and links so provisioning preserves the required VNF order.
  • The operational scenario includes existing VNFs and routes while new requests are provisioned individually or in accumulated lookahead batches.
  • VNF-OP minimizes network OPEX and physical resource fragmentation while selecting VNF counts, locations, and routes under capacity constraints.
  • OPEX includes VNF deployment, energy, traffic forwarding, and SLO-violation penalty costs.
  • Resource fragmentation measures idle resources on active servers and links, whose reduction can increase capacity for additional traffic.

III. INTEGER LINEAR PROGRAMMING (ILP) FORMULATION

The ILP transforms the physical network into an augmented pseudo-network to represent possible VNF placements and simplify flow constraints. Enumeration bounds candidate VNFs using server capacities and eligibility rules.

  • III. INTEGER LINEAR PROGRAMMING (ILP) FORMULATION: VNF-OP is harder than virtual-network embedding because it preserves VNF order, enforces processing capacities, and optimizes unknown VNF counts.
  • III. INTEGER LINEAR PROGRAMMING (ILP) FORMULATION: Nested packing of traffic into VNFs and VNFs into servers creates quadratic resource-capacity constraints for the optimization.
  • A. Physical Network Transformation: The physical topology is transformed into an augmented pseudo-network to reduce VNF-OP complexity.
  • 1) VNF Enumeration:: VNF enumeration computes the maximum deployable count of each VNF type on every server from server capacity and VNF requirements.
  • 1) VNF Enumeration:: Pseudo-VNFs form the candidate set M, with each pseudo-VNF implicitly attached to a physical server through ζ(m) and Ω(n̄).
  • 1) VNF Enumeration:: The binary variable q_mp indicates whether pseudo-VNF m has type p.
  • 1) VNF Enumeration:: Eligibility constraints ensure that enumerated VNFs are placed only on servers capable of hosting their VNF type.
  • 1) VNF Enumeration:: The binary variable y_m records whether pseudo-VNF m is active in the solution.

2) Adding Pseudo-Switches:

The formulation augments the topology with pseudo-switches and defines constraints and objectives for feasible, cost-aware VNF placement. It minimizes operational cost and resource fragmentation while preserving prior allocations and respecting capacity, mapping, flow, and SLO requirements.

  • 2) Adding Pseudo-Switches:: Pseudo-switches simplify the ILP flow-conservation expressions without increasing the solution space.They are inserted between each pseudo-VNF and its original switch and are used only for flow conservation.
  • B. ILP Formulation: The formulation enforces VNF, server, and link capacity constraints, traffic-node mapping, flow conservation, and physical-link provisioning.It also prevents deallocation of resources used by previously provisioned traffic and restricts directed traffic links from using both physical-link directions.
  • B. ILP Formulation: The ILP seeks the optimal number and placement of VNFs while minimizing OPEX and physical resource fragmentation.The weighted objective combines network operational costs with fragmentation costs using weighting factors.
  • B. ILP Formulation: The OPEX objective includes VNF deployment, energy, traffic forwarding, and SLO-violation penalty costs.Energy modeling accounts for both resource use and server idle consumption; forwarding cost is based on per-link traffic cost.
  • B. ILP Formulation: The VNF-OP is NP-Hard through a reduction to a capacitated facility-location or trans-shipment problem.The reduction imposes a constraint on the maximum number of VNFs deployed in the network.

IV. HEURISTIC SOLUTION

The heuristic solves VNF-OP by finding VNF counts and locations for a topology, middlebox specifications, and traffic batch while prioritizing low OPEX. It omits explicit resource fragmentation to remain simple and fast, yet produces near-optimal solutions.

  • IV. HEURISTIC SOLUTION: The heuristic determines the number and locations of VNF types needed for a topology, middlebox specifications, and traffic requests.Its stated objective is to operate the network with minimal OPEX.
  • IV. HEURISTIC SOLUTION: The heuristic omits explicit resource fragmentation from its optimization to keep the algorithm simple and fast.The paper reports that experiments nevertheless show solutions very close to the optimum.
  • IV. HEURISTIC SOLUTION: The heuristic targets near-optimal VNF orchestration rather than solving the full optimization objective exactly.Its reported simplification concerns resource fragmentation, while OPEX remains the operational objective.

A. Modeling with Multi-Stage Graph

Each traffic request is modeled as a multi-stage graph whose stages represent ingress, ordered VNFs, and egress, with candidate server locations and transition costs encoding placement and routing choices.

  • A. Modeling with Multi-Stage Graph: A traffic request becomes a graph with lΨt + 2 stages for ingress, the ordered VNF sequence, and egress.Ingress and egress stages each contain one switch node; intermediate stages correspond to VNFs.
  • A. Modeling with Multi-Stage Graph: Nodes in each VNF stage represent possible server locations and carry deployment and energy costs.These costs are defined by the corresponding ILP cost expressions.
  • A. Modeling with Multi-Stage Graph: Edges connect candidate placements in successive stages and encode traffic-forwarding costs and SLO-violation penalties.Thus, transitions represent moving from one VNF location to the next in the required sequence.

B. Finding a Near-Optimal Solution

The provisioning heuristic applies dynamic programming on the multi-stage graph, retaining minimum-cost predecessor choices and backtracing the final path to obtain a VNF placement.

  • B. Finding a Near-Optimal Solution: The algorithm computes minimum cumulative costs stage by stage and stores predecessor pointers for reconstruction.The final placement is obtained by tracing pointers backward from the final stage.
  • B. Finding a Near-Optimal Solution: ProvisionTraffic takes a traffic request and network topology as input and returns a placement of its VNF sequence.It updates residual server resources and link bandwidth after allocating each path.
  • B. Finding a Near-Optimal Solution: The heuristic runs in Θ(n^2m) time for each traffic request, where n is the number of switches and m is the VNF sequence length.This complexity is stated for the path-based provisioning procedure.

V. PERFORMANCE EVALUATION

The evaluation uses trace-driven simulations on three real-world network topologies, combining real and synthetic traffic with server, VNF, and middlebox cost data. It compares hardware and VNF deployments and evaluates the heuristic against CPLEX using OPEX, execution time, utilization, and placement metrics.

  • Evaluation Setup: The evaluation covers Internet2, a university data center, and AS-3967 network topologies.The topologies contain 12, 23, and 79 nodes, respectively.
  • Evaluation Setup: Traffic inputs combine real traces with synthetic time-varying traffic generated for the evaluated topologies.Internet2 uses a 12 × 12 traffic-matrix snapshot, while the Rocketfuel topology uses FNSS-generated traffic.
  • Evaluation Setup: The experiments use manufacturer and service-provider data for server energy, SLO penalties, resource requirements, processing capacities, and hardware middlebox energy consumption.These parameters are listed in Table I, and “middlebox” denotes both hardware middleboxes and VNFs in the evaluation.
  • Metrics: OPEX is measured according to Eq. 15, and CPLEX is compared with the heuristic using OPEX and component ratios.The evaluation also examines execution time, resource utilization, and topological properties of middlebox locations.

2) Execution Time:

The experiments compare VNF and hardware deployments and assess the heuristic against CPLEX across cost, topology, utilization, and execution time. VNFs reduce OPEX substantially, while the heuristic remains close to optimal with much lower execution time, though topology diversity creates larger placement gaps in data centers.

  • VNFs vs. Hardware Middleboxes: More than 4× reduction in OPEX is achieved by VNFs compared with hardware middleboxes.The comparison includes energy and transit costs but excludes hardware deployment cost because no public estimate was available.
  • VNFs vs. Hardware Middleboxes: VNFs are more often placed within 2 hops of ingress and egress switches and have lower path stretch than hardware middleboxes.Some VNFs are placed farther away when that reduces OPEX through lower energy cost.
  • CPLEX vs. Heuristic: The heuristic’s total cost ratio stays between 1 and 1.1 on Internet2 and between 1.1 and 1.3 on the data center network.The heuristic’s energy and transit cost ratios vary with traffic, while the total ratio remains close to the optimal solution.
  • Execution Time: The heuristic runs several orders of magnitude faster than CPLEX while producing solutions very close to the optimum.Average execution times are reported in Table II.
  • Resource Utilization: On Internet2, the heuristic uses fewer servers and has lower mean utilization than CPLEX, which deploys more VNFs to shorten traffic paths.In the data center network, CPLEX uses fewer servers and achieves higher utilization, while the heuristic has greater resource fragmentation.
  • Topological Properties: The heuristic’s placement is close to CPLEX on Internet2 but diverges more in data centers because it does not explore alternate equal-cost paths.This path-diversity limitation also produces larger path stretch in the data center network.

E. Effect of High Traffic Volume

Higher traffic increases OPEX and server utilization, while the heuristic remains close to the optimal solution. More VNFs can reduce transit cost, which dominates energy cost.

  • OPEX grows linearly with network utilization as traffic increases by 10% to 40%.The cost grows at nearly the same rate for CPLEX and the heuristic.
  • The heuristic follows the optimal solution closely under higher traffic volumes.
  • Transit cost is two orders of magnitude larger than energy cost.
  • Server utilization increases sub-linearly with network load while the number of used servers remains unchanged.More cores are used because more VNFs are deployed.
  • More VNFs can increase energy cost but decrease transit cost as traffic load rises.Transit cost is the major OPEX contributor in this case.

APPENDIX A GLOSSARY OF SYMBOLS

The glossary defines the physical network, VNF, traffic, and optimization variables used by the heuristic and its cost computation. The heuristic tracks placement costs across ordered middlebox sequences and backtraces the minimum-cost sequence.

  • The heuristic computes placement costs for each middlebox stage and stores predecessor links for backtracing.IsResourceAvailable checks resource and bandwidth constraints; GetCost computes placement cost.
  • The physical network is modeled as an undirected graph of switches and links, with servers attached to switches.
  • VNF types specify deployment cost, resource requirements, processing capacity, and processing delay.
  • A traffic request records ingress, egress, ordered VNF sequence, bandwidth, expected delay, and SLA penalty.
  • Decision variables assign traffic nodes to pseudo-VNFs and physical links, while derived variables indicate active VNFs and switch attachments.
  • The heuristic performs Θ(n^2m) operations after Θ(nm) initialization, where n is the number of switches and m the maximum sequence length.

APPENDIX C HEURISTIC IN ACTION

The heuristic places an ordered VNF sequence by traversing a multi-stage graph and selecting minimum-cost transitions. Rocketfuel results show adaptation to changing traffic, localized placements, and measurable path stretching.

  • Heuristic in action: A traffic path from switch 1 to 6 must traverse a firewall, IDS, and proxy in that order.
  • Heuristic in action: Each multi-stage graph node represents placing one VNF, with allowed servers differing by VNF type.The IDS is restricted to servers connected to switches 3 and 4, while the firewall and proxy can use any server.
  • Heuristic in action: At each stage, the heuristic selects the incoming transition with minimum cost.The selected predecessor determines the preceding middlebox placement.
  • Rocketfuel results: The Rocketfuel evaluation could not compare against an optimal solution because CPLEX exceeded available model memory.The optimization program crashed after total memory usage reached around 300 GB.
  • Rocketfuel results: Dynamic VNF orchestration scales active VNFs and changes their locations as traffic volume varies.
  • Rocketfuel results: More than 90% of middleboxes are deployed within 5 hops of the ingress switch, while 20% of traffic follows the shortest path.
Loading 1503.06377v2…