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.

  • 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.

  • Results

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

  • Takeaways & Limitations

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

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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.
  • I. INTRODUCTION: 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.

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.
  • B. Routing and Service Function Chaining: 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.
  • B. Routing and Service Function Chaining: 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.
  • B. Routing and Service Function Chaining: 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.
  • B. Routing and Service Function Chaining: 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.

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.
  • B. Outline of the resource management procedures and algorithms: 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.
  • B. Outline of the resource management procedures and algorithms: 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.
  • B. Outline of the resource management procedures and algorithms: 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.
  • B. Outline of the resource management procedures and algorithms: 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.

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.
  • IV. PROBLEM FORMULATION: Global reconfiguration can respond to congestion or elapsed intervals to reduce congestion or energy consumption while improving throughput and satisfying flow requirements.
  • A. System Model and Assumptions: The SDN-based system dynamically programs switches, with each flow traversing an ordered sequence of VNFs between source and destination switches.
  • A. System Model and Assumptions: Servers operate in OFF, IDLE, or ACTIVE modes, with energy variables distinguishing absolute consumption from the IDLE-to-ACTIVE difference.
  • A. System Model and Assumptions: Forwarding-table minimization is proportional to minimizing average path hops and therefore reduces network reconfiguration overhead.
  • A. System Model and Assumptions: The topology is represented through link capacities, propagation delays, current link loads, source and destination vectors, and per-flow routing matrices.
  • A. System Model and Assumptions: The ordering-aware matrix Q records the sequence of links and nodes crossed by each flow, unlike a routing matrix that only indicates selected links.

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: The constraint formulation is divided into QoS and unordered SFC constraints, ordered SFC constraints, and energy-consumption constraints.
  • B. Mathematical Formulation of constraints: The first component is Binary Linear Programming, while ordered SFC and energy components are Integer Quadratic Programming before nonlinear terms are linearized.
  • 1) QoS and SFC Constraints without VNF Ordering:: The QoS and unordered-SFC formulation guarantees delay and traffic-rate requirements while ensuring that each flow crosses its requested VNFs.
  • 1) QoS and SFC Constraints without VNF Ordering:: The constraints enforce valid VNF chains, VNF delivery on crossed servers, server support, single delivery, processing capacity, and link capacity.

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:: Ordered SFC requires an additional constraint set that links the sequence of VNFs to the flow’s route.
  • 2) SFC Constraints with VNF Ordering:: The ordering constraints ensure valid step progression, source departure, destination handling, path length, and consistency between routing and ordering matrices.
  • 2) SFC Constraints with VNF Ordering:: The formulation checks that lower-index VNFs in the requested order are delivered before higher-index VNFs on their hosting servers.
  • 2) SFC Constraints with VNF Ordering:: Energy-aware constraints prevent unused servers from being active and require servers delivering VNFs to active flows to be ON.
  • 2) SFC Constraints with VNF Ordering:: Nonlinear constraints are replaced by linear formulations that preserve routing, VNF-order, and server-activation conditions.
  • 2) SFC Constraints with VNF Ordering:: The linearized activation condition sets a server’s ON/OFF state according to whether it delivers VNFs to any flow.
  • 2) SFC Constraints with VNF Ordering:: The ordering formulation uses step comparisons so a server hosting a lower-index VNF is crossed before servers hosting higher-index VNFs.

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): SFRA applies the earlier QoS and SFC constraints to allocate resources for a newly arrived flow.
  • C. Single Flow Resource Allocation (SFRA): In the worst case, the routing representation can traverse all switches, bounding the relevant path-order quantity by 2N − 1.
  • C. Single Flow Resource Allocation (SFRA): The SFRA objective minimizes forwarding-table additions, equivalently minimizing the number of hops between a flow’s source and destination.
  • C. Single Flow Resource Allocation (SFRA): When a new flow’s rate is unknown, SFRA uses the current average flow rate and does not directly minimize energy to avoid congestion for large flows.
  • C. Single Flow Resource Allocation (SFRA): SFRA is NP-hard because a special case maps to the weight constrained shortest path problem.
  • C. Single Flow Resource Allocation (SFRA): The NP-hardness of SFRA supports using heuristics and relaxed formulations for the resource-allocation variants.

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.
  • GRR jointly minimizes normalized reconfiguration overhead and network energy consumption using the weighting parameter α.The objective combines the two components after normalization.
  • 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.
  • Lemma 2 classifies GRR as an NP-hard problem.The supplied proof reference points to the proof of Lemma 1.

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.
  • 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.
  • 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.
  • 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.

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.
  • 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.
  • 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.
  • 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.

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: ST-ENSF reconfigures networks at predefined intervals, whereas LT-ENSF reacts to congestion by switching on additional servers.LT-ENSF supports transitions among OFF, IDLE, and ACTIVE states.
  • C. Online Resource Reallocation: For each required VNF, the online heuristic prunes links below the flow size and excludes servers that do not support that VNF.It then evaluates candidate paths and energy consumption before selecting a server and updating capacity.
  • C. Online Resource Reallocation: ENS prefers already-ON servers supporting the required VNF and otherwise searches IDLE servers to minimize energy consumption.The selected path is added to the flow route, and its link capacities are reduced.
  • D. Mathematical Computational Complexity: ENSF has computational complexity O(F · Ψ · (N · log N + |E|)).The expression accounts for flows, required VNFs, and shortest-path computations over the network.

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.
  • 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.
  • System configuration: 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%.
  • 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.

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.
  • 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.
  • 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.
  • 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.
  • 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.
Loading 1710.02611v7…