PaperlayerView exact revision on arXiv

Source-linked AI summary

VNF Placement with Replication for Load Balancing in NFV Networks

Francisco Carpio, Samia Dhahri, Admela Jukan

arXiv:1610.08266v1cs.NI

TL;DR

VNF placement must balance deployment and forwarding costs, yet network load balancing has received less attention than minimizing VNF counts. This paper models placement with replicas and compares optimization and genetic-algorithm approaches with random allocation. Optimal placement with replication improves load balancing, while the proposed GA targets larger networks.

  • Problem

    VNF placement must trade off server deployment costs and forwarding costs, while comparatively less effort has addressed network load balancing.

    Source: §I · p. 1

  • Method

    The paper models VNF placement with replication and uses optimization and a staged Genetic Algorithm, comparing placement approaches including random allocation.

    Source: §I · p. 1, §V · p. 4, A. Genetic Algorithm (Algorithm 1) · p. 4

  • Results

    Almost no links exceed 60% utilization with optimum and near-optimum allocation, and optimal placement with replication significantly improves load balancing over operator-preferred server placement.

    Source: A. Link utilization results · p. 6, §VII · p. 6

  • Takeaways & Limitations

    The proposed heuristics can find near-optimal solutions with complexity that grows linearly with network size.

    Source: §VII · p. 6

Abstract

from arXiv · show

Network Function Virtualization (NFV) is a new paradigm, enabling service innovation through virtualization of traditional network functions located flexibly in the network in form of Virtual Network Functions (VNFs). Since VNFs can only be placed onto servers located in networked data centers, which is the NFV's salient feature, the traffic directed to these data center areas has significant impact on network load balancing. Network load balancing can be even more critical for an ordered sequence of VNFs, also known as Service Function Chains (SFCs), a common cloud and network service approach today. To balance the network load, VNF's can be placed in a smaller cluster of servers in the network thus minimizing the distance to the data center. The optimization of the placement of these clusters is a challenge as also other factors need to be considered, such as the resource utilization. To address this issue, we study the problem of VNF placement with replications, and especially the potential of VNFs replications to help load balance the network. We design and compare three optimization methods, including Linear Programing (LP) model, Genetic Algorithm (GA) and Random Fit Placement Algorithm (RFPA) for the allocation and replication of VNFs. Our results show that the optimum placement and replication can significantly improve load balancing, for which we also propose a GA heuristics applicable to larger networks.

I. INTRODUCTION

The introduction frames VNF placement as a trade-off between deployment cost and forwarding cost, with network load balancing comparatively underexplored. The paper studies replication-based placement and proposes optimization and heuristic approaches; related work motivates this focus against earlier placement objectives.

I. INTRODUCTION

  • VNF placement trades the cost of deploying servers against forwarding cost, while prior solutions have focused more on minimizing VNF counts than balancing network load.Remote data centers can lower deployment cost but typically increase delay and network-load churn; additional in-network servers require investment.Source: §I · p. 1
  • The paper studies VNF placement with replications, formulates an optimization model, compares it with random allocation, and proposes a Genetic Algorithm for scalable near-optimal solutions.The GA is described as growing linearly with network size.Source: §I · p. 1

II. RELATED WORK

  • Earlier placement studies optimize objectives such as physical-node counts, latency, and link utilization, while other work applies heuristics or genetic algorithms to placement and orchestration.The cited work also includes a genetic algorithm for satisfying SLA and QoS objectives under dynamic traffic demands.Source: §II · p. 2
  • The authors distinguish their approach by considering VNF replication for mobile-core placement optimized for network load balancing.They describe replication as novel relative to previous work and connect the setting to scalable mobile-data growth.Source: §II · p. 2

III. REFERENCE ARCHITECTURE

The reference architecture describes NFV components and resource-allocation stages, then focuses on a mobile-core service chain. The study asks where to place its functions and replicas to balance traffic while determining the number of network servers needed.

III. REFERENCE ARCHITECTURE

  • NFV comprises Services, NFV Infrastructure (NFVI), and NFV Management and Orchestration (NFV-MANO), whose orchestrator assigns VNF chains to physical resources.NFVI provides connectivity, computing, and storage; NFV-MANO includes the orchestrator, VNF managers, and infrastructure managers.Source: §III · p. 2
  • Network resource allocation is divided into VNF chain composition, forwarding-graph embedding, and VNF scheduling.Forwarding-graph embedding determines where to allocate VNFs according to an objective such as network load balancing.Source: §III · p. 2

A. Service Function Chaining (SFC) in Mobile Core Networks

  • The mobile-core use case places S-GW and P-GW traffic on a path toward the Internet that may require services such as load balancing, TCP optimization, firewalls, and NATs.The gateways connect to e-NodeB and send end-user traffic toward Internet gateways.Source: A. Service Function Chaining (SFC) in… · p. 2
  • The study asks where and how many NFV-capable nodes are needed to place the remaining mobile-core functions while balancing network load.It considers virtualization of the S-GW and P-GW on small data centers, then chains and virtualizes the other functions across physical locations.Source: A. Service Function Chaining (SFC) in… · p. 2
  • Original functions and replicas can be placed at different network locations, with the required replica count related to traffic demand and indicating how many servers to build.Replicas preserve the service-function sequence.Source: A. Service Function Chaining (SFC) in… · p. 3

B. Network Traffic Model

The model distinguishes background traffic from data-center traffic carrying service-chain demands. Its optimization formulation minimizes link costs while constraining routing and VNF placement.

B. Network Traffic Model

  • Background traffic follows traditional IP routing, while data-center traffic traverses the VNFs required by its service before reaching Internet gateways.The traffic model defines these as the two traffic categories.Source: B. Network Traffic Model · p. 3

IV. OPTIMIZATION MODEL

  • The formulation minimizes cost across all network links for both traffic-engineering and resource-allocation models.Link cost is zero below 60% utilization and rises exponentially from 60% to 100%.Source: §IV · p. 3
  • Each traffic demand uses one path, and added replicas increase the number of paths available to a service chain for load balancing.The formulation also preserves VNF sequence order and limits node allocations and replica counts; non-replicable functions appear once per service chain.Source: §IV · pp. 3–4

V. HEURISTICS

The heuristics address the computational limits of LP-based placement by using genetic and random-fit approaches. The genetic algorithm separates traffic engineering, VNF allocation, and replication tasks.

V. HEURISTICS

  • Because VNF allocation is NP-hard, the authors propose a genetic algorithm for placement and replication to reduce computation time on larger networks.LP models are described as feasible only for small networks.Source: §V · p. 4
  • The genetic algorithm uses separate sub-algorithms for traffic engineering, service-chain resource allocation, and replica placement.Its listed outputs include link utilizations and chosen paths, allocation nodes, and replication nodes.Source: §V · p. 4
  • Random Fit Placement tests whether random VNF allocation can load-balance the network comparably to deployment at operator-preferred nodes.Source: §V · p. 4

A. Genetic Algorithm (Algorithm 1)

The genetic algorithm divides traffic engineering, VNF allocation, and replication into linked stages. It tests additional replicas only while they reduce network cost.

A. Genetic Algorithm (Algorithm 1)

  • The algorithm passes admissible paths and network cost from traffic engineering to resource allocation, which places original VNFs in service-chain order.The selected allocation nodes then inform the replication stage.Source: A. Genetic Algorithm (Algorithm 1) · p. 4
  • The replication stage searches alternative paths and allocates replicas according to network cost, following the resource-allocation approach.The algorithm compares the no-replica case with successive replica counts.Source: A. Genetic Algorithm (Algorithm 1) · p. 4
  • Replication stops when adding replicas can no longer improve network cost.Source: A. Genetic Algorithm (Algorithm 1) · p. 5

B. Random-Fit Placement Algorithm (Algorithm 2)

Random-fit placement selects a valid constrained allocation at random, then chooses admissible paths and traffic routes randomly.

B. Random-Fit Placement Algorithm (Algorithm 2)

VI. PERFORMANCE EVALUATION

The evaluation compares the LP model, genetic algorithm, and random allocation approach across network topologies under fixed data-center and link-capacity settings.

  • The evaluation compares the LP model, genetic algorithm, and random allocation approach.Source: §VI · p. 5
  • The evaluation includes network cost in relation to the number of replicas.Source: Figure 6 · p. 5
  • Topologies are characterized by connection count, data-center bandwidth, and background bandwidth, with two data centers and 2.5 Gbps maximum link capacity fixed.Source: §VI · p. 5

A. Link utilization results

Link utilization comparisons show that random placement produces more overload, while optimum and near-optimum placement with replicas leaves almost no links above 60% utilization.

A. Link utilization results

B. Total network cost

Replication reduces total network cost across the compared approaches, with especially strong performance for the genetic algorithm and optimum solution.

B. Total network cost

  • Replication decreases network cost for all three approaches, especially for the genetic algorithm and optimum solution.Source: B. Total network cost · p. 6
  • Random allocation has higher network cost than the genetic and optimum solutions on Nobel-us and Janos-us.Source: B. Total network cost · p. 6
  • For larger topologies where LP cannot produce results in a reasonable time, the genetic algorithm finds solutions at much lower computational cost, particularly with replication.Source: B. Total network cost · p. 6

C. Genetic algorithm benchmark

The genetic algorithm takes longer to find valid solutions with replication but its computation time grows linearly with topology size, unlike the typical exponential growth of LP models.

C. Genetic algorithm benchmark

VII. CONCLUSION

VNF placement with replication is studied as a way to balance network load, particularly when traffic traverses an ordered service chain. The conclusion reports improved load balancing over building servers at operator-preferred nodes and near-optimal solutions from heuristics whose complexity grows linearly with network size.

  • The study focuses on how VNF replication can help balance network traffic, especially when traffic traverses an ordered service chain.Source: §VII · p. 6
  • Optimum VNF placement and replication significantly improve load balancing compared with building servers at network-operator-preferred nodes.Source: §VII · p. 6
  • Heuristics can find near-optimal solutions with complexity that grows only linearly with network size.Source: §VII · p. 6
Loading 1610.08266v1…