PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Energy Efficient and QoS-aware Path Allocation and VNF Placement for Service Function Chaining

Mohammad M. Tajiki, Stefano Salsano, Luca Chiaraviglio, Mohammad Shojafar, Behzad Akbari

arXiv:1710.02611v7cs.NI

TL;DR

The paper tackles energy-aware SFC in SDN while preserving QoS. It develops a resource reallocation architecture, optimization formulations, and scalable heuristics, whose evaluations report near-optimal solutions with execution times applicable to real-life networks.

  • Problem

    Network providers need to reduce the high energy consumption of SDN/NFV networks without violating SFC and QoS requirements.

    Source: §I · p. 1

  • Method

    The paper proposes a five-component resource-allocation architecture, formulates energy-aware VNF placement and path allocation as optimization problems, and develops heuristics for larger networks.

    Source: §I · pp. 1–2

  • Results

    The proposed schemes achieve energy consumption near the optimal solution, while heuristic execution is reported as applicable to real-life networks.

    Source: §I · p. 2, C. Energy, Path Length, and… · pp. 17–18, §VII · p. 18

  • Takeaways & Limitations

    Energy-aware joint VNF placement and routing can allocate network resources while meeting flow requirements and limiting network reconfiguration side effects.

    Source: §VII · p. 18

Abstract

from arXiv · show

Service Function Chaining (SFC) allows the forwarding of a traffic flow along a chain of Virtual Network Functions (VNFs, e.g., IDS, firewall, and NAT). Software Defined Networking (SDN) solutions can be used to support SFC reducing the management complexity and the operational costs. One of the most critical issues for the service and network providers is the reduction of energy consumption, which should be achieved without impact to the quality of services. In this paper, we propose a novel resource (re)allocation architecture which enables energy-aware SFC for SDN-based networks. To this end, we model the problems of VNF placement, allocation of VNFs to flows, and flow routing as optimization problems. Thereafter, heuristic algorithms are proposed for the different optimization problems, in order find near-optimal solutions in acceptable times. The performance of the proposed algorithms are numerically evaluated over a real-world topology and various network traffic patterns. The results confirm that the proposed heuristic algorithms provide near optimal solutions while their execution time is applicable for real-life networks.

I. INTRODUCTION

The paper addresses energy-aware Service Function Chaining in SDN by jointly considering VNF placement, flow routing, QoS, and network reconfiguration. It formulates resource-allocation problems and proposes heuristics for larger networks, while evaluating energy, utilization, path, side-effect, and computational measures.

I. INTRODUCTION

  • The paper proposes an SDN-based resource-allocation architecture with five components for energy-aware VNF placement and path allocation.The components are Single Flow Resource Allocation, Global Resource Reallocation, Network Monitoring, Server/Network Configurator, and Congestion Detector/Predictor.Source: §I · p. 1
  • Resource allocation jointly accounts for energy, SFC, and QoS constraints, including flow delay, link utilization, and server utilization.The formulation includes initial allocation and global reallocation, with servers modeled in OFF, ON-IDLE, and ON-ACTIVE states.Source: §I · p. 1
  • The natural formulations are INLPs, linearized into ILPs solvable by exact solvers for small networks.The paper uses near-optimal heuristics for larger-scale scenarios where exact optimization is less applicable.Source: §I · pp. 1–2
  • The proposed heuristics are evaluated against optimal algorithms across energy, path length, reconfiguration side effects, resource utilization, and computational complexity.The evaluation uses generated network resources and flows with requirements such as VNF chaining, delay tolerance, flow size, and server functionality.Source: §I · p. 2
  • The architecture leaves its precise mapping to ETSI NFV MANO functional entities for future study and identifies burst traffic and additional processing or queuing delays as future work.These boundaries concern implementation mapping, traffic robustness, and QoS-related delay modeling.Source: §I · p. 2
  • Prior work covers VNF placement, routing and SFC, and green SFC, but the cited methods do not jointly address SFC and VM energy consumption in SDN.The related work includes optimization and approximation approaches for placement, routing, operational cost, utilization, energy, and SLA performance.Source: §II · p. 2, A. VNF/VM Placement · p. 2

B. Routing and Service Function Chaining

The paper frames SFC routing and VNF placement as joint resource-allocation problems that must satisfy chaining, QoS, utilization, and energy objectives. It addresses the gap that prior SFC approaches generally did not account for VM energy consumption while jointly handling routing and placement.

B. Routing and Service Function Chaining

  • Prior routing and placement studies addressed SFC formation, congestion, migration, or cost, but did not jointly consider VM energy consumption in SFC.The paper identifies this omission across the reviewed SFC-routing category.Source: B. Routing and Service Function Chaining · pp. 2–3
  • The paper extends earlier work with five subproblems, VNF ordering constraints, and delay constraints that were absent from the previous conference version.The extension covers initial assignment, rerouting, and online/offline procedures.Source: C. Green Service Function Chaining · p. 3
  • The proposed model jointly assigns VNF chains, routes flows, and manages VM states while enforcing link, processing, delay, and QoS-related constraints.The architecture maps ordered VNF chains onto VM instances and explicitly configures paths between ingress, VNFs, and egress.Source: §III · pp. 3–4
  • The operator can optimize energy consumption together with QoS and load-related objectives, while experiments focus on energy minimization rather than network reconfiguration cost.Servers may be OFF, ON-IDLE, or ON-ACTIVE, with activation changes treated as relatively long-term operations.Source: §III · p. 4
  • The architecture represents networking and processing devices in an infrastructure layer, controlled through a logically centralized SDN controller and supporting application-level resource management.The infrastructure includes switches and servers, while the controller configures forwarding and collects topology and traffic information.Source: A. Architecture · pp. 4–5

B. Outline of the resource management procedures and algorithms

The resource-management workflow combines long- and short-term reallocation with online responses to new flows and congestion. Because the underlying formulations are NP-hard, the paper uses relaxed optimization problems and heuristics for different operational settings.

B. Outline of the resource management procedures and algorithms

  • GRR globally reallocates resources to reduce energy consumption while controlling link and server utilization and preserving flow QoS.The paper formulates both single-flow allocation and global reallocation as optimization problems.Source: B. Outline of the resource management… · p. 5
  • The SFRA and GRR formulations are NP-hard, motivating relaxed versions and heuristic algorithms for the considered allocation and reallocation variants.The offline 3R procedure uses a relaxed formulation and can operate with either knowledge-base or current-state inputs.Source: B. Outline of the resource management… · pp. 5–6
  • SFRA assigns links and servers to one newly arriving flow using current network state, while NSF provides a fast heuristic for this immediate allocation.Its inputs include the source, destination, average flow rate, and current network state.Source: B. Outline of the resource management… · p. 5
  • LT-ENSF handles online long-term reconfiguration after congestion or predicted congestion, whereas ST-ENSF periodically reroutes flows and changes ON-server ACTIVE/IDLE states.ST-ENSF outputs a selected path for each flow and the state of currently ON servers.Source: B. Outline of the resource management… · pp. 5–6
  • The workflow invokes long-term reallocation from predicted flow rates and reacts online to new flows, congestion, or scheduled reconfiguration events.The knowledge base is updated periodically, while distinct procedures handle long-term server states and short-term active/idle states.Source: B. Outline of the resource management… · pp. 5–7

IV. PROBLEM FORMULATION

The architecture combines single-flow allocation with global reallocation, using SDN control and network-state information to configure forwarding paths and manage VNF resources. Its model represents topology, routing, ordered paths, VNF requirements, server capacities, utilization, and energy states.

IV. PROBLEM FORMULATION

  • The architecture uses Single Flow Resource Allocation for arriving flows and Global Resource Reallocation for simultaneous network-wide optimization.SFRA produces forwarding-table entries for a new flow, whereas GRR considers all flows simultaneously.Source: §IV · p. 7
  • Global reconfiguration can respond to congestion or elapsed intervals to reduce congestion or energy consumption while improving throughput and satisfying flow requirements.Source: §IV · p. 7

A. System Model and Assumptions

B. Mathematical Formulation of constraints

The formulation separates QoS, unordered and ordered SFC, and energy constraints into optimization components with different mathematical forms. These constraints enforce feasible paths, VNF delivery, capacity limits, and flow requirements.

B. Mathematical Formulation of constraints

1) QoS and SFC Constraints without VNF Ordering:

2) SFC Constraints with VNF Ordering:

The ordered-SFC formulation augments routing with step-aware constraints so VNFs are delivered in the requested sequence. Additional constraints activate only necessary servers and connect VNF placement to energy-aware operation.

2) SFC Constraints with VNF Ordering:

C. Single Flow Resource Allocation (SFRA)

SFRA allocates a newly arrived flow using the existing QoS and SFC constraints while minimizing forwarding-table additions and associated path length. The resulting problem is NP-hard, motivating heuristic or relaxed solution methods.

C. Single Flow Resource Allocation (SFRA)

D. Global Resource Reallocation (GRR)

GRR jointly optimizes network energy consumption and flow-rerouting overhead under processing and link-capacity constraints. Its formulation is NP-hard and assumes estimated flow rates for reallocation.

  • Reconfiguration overhead reflects differences between current and previous routing matrices and depends on the number of rerouted flows.More rerouted flows may increase instability, packet loss, and end-to-end delay.Source: D. Global Resource Reallocation (GRR) · pp. 11–12
  • GRR jointly minimizes normalized reconfiguration overhead and network energy consumption using the weighting parameter α.The objective combines the two components after normalization.Source: D. Global Resource Reallocation (GRR) · p. 12
  • GRR enforces server-processing and inter-switch link-capacity constraints using estimated flow rates from the current network state.These constraints are included because reallocation assumes flow-rate estimates are available.Source: D. Global Resource Reallocation (GRR) · p. 12
  • Lemma 2 classifies GRR as an NP-hard problem.The supplied proof reference points to the proof of Lemma 1.Source: D. Global Resource Reallocation (GRR) · p. 12

V. HEURISTICS

The heuristic layer addresses resource allocation for newly arriving flows with NSF, which selects nearby feasible servers and paths for each required VNF. It updates capacities while completing the chain and routing the flow to its destination.

  • NSF builds each flow path by selecting the nearest server supporting each required VNF, then adds a shortest path to the destination.The procedure iterates through VNFs, updates the current server, and finally routes from the last selected server to the destination.Source: A. Nearest Service Function first (NSF) · p. 12
  • NSF reduces available network capacity after each selected VNF path and after the final path to the destination.Capacity reduction uses the median size of recently communicated flows, MFS.Source: A. Nearest Service Function first (NSF) · p. 12
  • Find Nearest Providers prunes links below MFS capacity and excludes servers lacking the requested VNF or sufficient processing capacity.Among the remaining candidates, it selects the minimum-cost nearest server.Source: A. Nearest Service Function first (NSF) · p. 12
  • NSF’s selection procedure uses shortest-path computation followed by server filtering and minimum-cost selection.The method applies Dijkstra-based paths before checking VNF support and processing capacity.Source: A. Nearest Service Function first (NSF) · pp. 12–13

B. Offline Resource Reallocation

Offline resource reallocation uses traffic measurements and estimated flow rates to optimize longer-term server and path assignments. The proposed 3R method relaxes GRR by reallocating flows sequentially to trade optimality for lower complexity.

  • The offline procedure can use measured or predicted traffic patterns to decide which servers should be turned on or off at predefined intervals.The paper notes that solving the full GRR formulation with an ILP solver is not applicable to medium and large networks in its experiment.Source: B. Offline Resource Reallocation · p. 13, 2) Relaxed Resource Reallocation (3R) · p. 13
  • Energy-aware SFRA minimizes the number of servers turned on to support an individual existing flow and measures the additional energy required for that flow.The objective distinguishes servers newly activated for the current flow from servers already used by other flows.Source: 1) Energy-aware SFRA · p. 13
  • 3R is proposed as a near-optimal alternative because GRR becomes computationally complex in medium and large networks.The method seeks a trade-off between the optimality gap and computational complexity.Source: 2) Relaxed Resource Reallocation (3R) · p. 13
  • 3R reallocates resources flow by flow using Energy-aware SFRA rather than considering all flow interactions simultaneously.After each flow is rerouted, the available link capacities are updated before processing the next flow.Source: 2) Relaxed Resource Reallocation (3R) · p. 13

C. Online Resource Reallocation

Online reallocation uses fast energy-aware heuristics for short-term and congestion-triggered changes. ST-ENSF and LT-ENSF select feasible VNF servers while accounting for energy, path cost, capacity, and server states.

C. Online Resource Reallocation

D. Mathematical Computational Complexity

VI. NUMERICAL RESULTS

The evaluation uses generated traffic demands over the real-world Abilene topology, varying flow size, VNF-hosting capacity, and requested chain length across five scenarios. Server modes, processing capacity, and energy parameters define the simulation environment.

Experimental setup

  • The experiments evaluate the proposed algorithms under different traffic patterns on the real-world Abilene network topology.A traffic-demand generator produces flows with specified rates, endpoints, VNF requirements, and tolerable delays.Source: §VI · p. 15, A. Traffic-Demand Generator · p. 15

System configuration

  • Servers are modeled with ACTIVE, IDLE, and OFF modes, while their processing capacity is scaled by Θ to create potential bottlenecks.The study sets Θ to 0.1 in one experiment to investigate processing-capacity effects on energy consumption.Source: B. Simulation Setup · p. 16
  • The simulations assign server energy values between Emin=200J and Emax=400J and increase flow rates across five iterations.Subsequent iterations increase flow rates using a uniform distribution averaging 10%.Source: B. Simulation Setup · p. 16

Simulation scenarios

  • Five traffic scenarios vary flow-size ratio, VNF-hosting server ratio, and average requested VNFs per flow.The scenarios use Bf values of 0.2 and 0.3 alongside changes in γ and Rf.Source: B. Simulation Setup · p. 16

C. Energy, Path Length, and Reconfiguration Side-effect

The heuristics achieve energy consumption close to optimal solutions while trading off path length, utilization, reconfiguration overhead, and execution time. ST-3R and ST-ENSF generally improve resource-use measures over energy-only strategies, while ENSF supports real-time reallocation.

Short-Term Resource Reallocation

  • ST-ENSF and ST-3R have near-optimal energy consumption in all test cases, with ST-3R usually achieving lower path length and reconfiguration overhead.ST-3R is lower on both measures in every scenario except scenario 1.Source: C. Energy, Path Length, and… · p. 17

Long-Term Resource Reallocation

  • LT-3R and LT-ENSF achieve energy consumption close to optimal while producing much lower path length and reconfiguration overhead than ASR and the optimal solution.The comparison covers long-term resource reallocation across all test cases.Source: C. Energy, Path Length, and… · pp. 17–18

Server and Link Utilization

  • ST-ENSF and ST-3R yield lower average and maximum server utilization than ST-GRR while maintaining similar total throughput.ST-ENSF can have higher maximum link utilization because it favors nearby VNFs for delay and path length.Source: D. Server and Link Utilization · p. 18

Computational Complexity

  • ENSF has very low execution time for real-time online reallocation, whereas 3R is suited to offline resource reallocation.The execution-time comparison uses the computational-complexity results reported in Table IV.Source: E. Computational Complexity · p. 18, Table IV · p. 18

Overall conclusion

  • The proposed schemes jointly target energy consumption and network-reconfiguration side effects while satisfying flow requirements.The conclusion reports near-optimal energy consumption from the resource-allocation schemes.Source: §VII · p. 18
Loading 1710.02611v7…