Source-linked AI summary
Specifying and Placing Chains of Virtual Network Functions
Sevil Mehraghdam, Matthias Keller, Holger Karl
TL;DR
Network operators need to specify dependent chains of virtual network functions and place them under limited resources and application requirements. The paper defines a context-free chaining language, constructs VNF graphs, and formulates their placement as an MIQCP. Evaluations examine ordering heuristics, placement trade-offs, and Pareto solutions across data rate, node usage, and latency objectives.
Problem
The paper addresses how to formalize network-function chaining with dependencies and place the resulting functions while satisfying tenant and operator requirements.
Method
The authors define a context-free language for chaining requests, construct VNF graphs, and formulate their placement in an operator network as an MIQCP.
Results
Evaluations examine ordering heuristics and Pareto trade-offs among remaining data rate, used network nodes, and total latency.
Takeaways & Limitations
Placement decisions depend on the desired objective, and some resource conditions permit solutions that optimize all three placement metrics.
Abstract
from arXiv · showhide
Network appliances perform different functions on network flows and constitute an important part of an operator's network. Normally, a set of chained network functions process network flows. Following the trend of virtualization of networks, virtualization of the network functions has also become a topic of interest. We define a model for formalizing the chaining of network functions using a context-free language. We process deployment requests and construct virtual network function graphs that can be mapped to the network. We describe the mapping as a Mixed Integer Quadratically Constrained Program (MIQCP) for finding the placement of the network functions and chaining them together considering the limited network resources and requirements of the functions. We have performed a Pareto set analysis to investigate the possible trade-offs between different optimization objectives.
I. INTRODUCTION
The paper addresses formalizing dependent network-function chains and placing them in an operator’s NFV network while balancing tenant and network-wide requirements. It introduces a flexible chaining model, placement optimization, and Pareto analysis of competing objectives.
- Motivation: Network flows typically traverse multiple network functions in a specified order, a process known as network function chaining.Examples include NATs, load balancers, firewalls, and intrusion detection systems.
- Motivation: Different functions can change flow rates or branch traffic, while dependencies may constrain their ordering.For example, IDS inspection should precede WAN-optimizer encryption when both process the same traffic.
- Challenges: The paper formalizes chaining requests with dependencies and determines function placement while considering individual requests, shared VNFs, and overall network requirements.These are presented as two central challenges for the operator.
- NFV setting: NFV makes changes to chaining and placement more practical than modifying physical network topology or appliance connections.The proposed solutions are intended for both virtualized and non-virtualized chaining scenarios.
- Approach: The placement problem is formulated as an MIQCP with objectives to maximize remaining data rate, minimize used nodes, and minimize total path latency.The paper also describes preprocessing, a runtime-reduction heuristic, evaluation, and multi-objective Pareto analysis.
- Scope: The model is designed to remain flexible while NFV standardization and implementation requirements are still evolving.The authors position it as compatible with emerging NFV models and architectures.
III. NETWORK FUNCTION CHAINING SPECIFICATION
The paper represents chaining requests as VNF graphs using a context-free language with fixed, optional, split, and parallel compositions. These graphs capture function ordering and branching before mapping onto a directed substrate network with heterogeneous computational resources.
- Network model: The substrate network is modeled as a connected directed graph whose nodes and links provide locations, computational capacities, data rates, and latencies.Switch nodes may offer limited computation, while data-center nodes provide larger computational capacity.
- Request inputs: A chaining request specifies requested function instances, their ordering, branch data-rate ratios, fixed endpoints, initial data rate, and latency requirements.The operator also maintains function resource requirements and placement eligibility across switch and data-center nodes.
- Language constructs: The context-free language composes individual functions, start/end points, optional-order modules, split modules, and parallel modules.Optional and parallel modules allow the operator to choose among function orderings or replicate modules across branches.
- Grammar: Sequentially nested modules represent simple fixed ordering, while grammar rules define optional orders, terms, branches, and parallel composition.The grammar uses non-terminals, function and endpoint symbols, delimiters, branch-count symbols, and an empty string.
- Graph representation: The resulting VNF graph contains functions and flow endpoints as nodes, directed edges for traversal order, and substrate paths for every graph link.Endpoints map to fixed substrate locations, whereas VNF locations must be determined during deployment.
IV. PROCESSING DEPLOYMENT REQUESTS
Deployment requests are parsed into candidate VNF graphs, with different chaining orders producing different data-rate and instance requirements. A heuristic selects one graph per request to avoid the rapidly growing cost of exhaustive combinations, while accepting possible non-optimality for instance count or latency.
- Each deployment request is parsed into a VNF graph whose nodes represent functions or flow endpoints.
- Load-balancer placement trades lower downstream link data rates against potentially requiring up to three instances of subsequent VNFs.Earlier splitting lowers each branch's rate, while later functions require more instances with lower processing demands.
- Optional-order and parallel modules generate n! function permutations, and combinations across modules multiply these possibilities.With modules of sizes 3 and 4, the process produces 3!·4!=144 combinations.
- The proposed heuristic sorts arbitrarily ordered functions by ascending outgoing-to-incoming data-rate ratio and selects one graph per request.The function reducing flow data rate most is placed first, producing a single VNF graph for each request.
- Exhaustive placement becomes impractical as request and function counts increase, so the heuristic may discard graphs optimal for VNF-instance count or latency.The execution-time gain can compensate for this deviation from optimality, which is examined through Pareto analysis.
V. PLACEMENT OF CHAINED NETWORK FUNCTIONS
The placement problem is formulated as an MIQCP using substrate capacities, function requirements, and the combined VNF graph. Its objectives are to maximize remaining data rate while minimizing used nodes and total path latency.
- The MIQCP takes network-node and link capacities, network-function requirements, and the combined VNF graph as input.
- The placement objectives are maximizing remaining data rate, minimizing used network nodes, and minimizing total latency over all paths.
- Decision variables include continuous remdr and lat variables, while all other decision variables are binary indicators.
A. Constraints
The placement constraints are organized into function placement and request mapping, path creation, and metric collection. This separation supports extending either placement or path modeling while preserving the necessary ties between them.
- Constraints place functions on network nodes and map requests to their function instances.
- Constraints create paths between chained functions after their placement is represented.
- Metric-collection constraints calculate the optimization measures used by the placement model.
- Placement and path-creation constraints are separated to facilitate extensions, with explicit ties connecting the two parts.
1) Network Function Placement Constraints:
Network-function placement constraints ensure each request is assigned consistently to an eligible node and that node resources and instance limits are respected.
- A request is assigned either as a switch function or as a data-center function, not both.
- Each VNF-use request is mapped to exactly one network node.
- Start and end flow points are fixed at their network locations, while their mapping values support path creation.
- Complementary constraints prevent unused function instances and require mapped requests to use a node hosting the required function.
- Computational requirements of mapped requests must not exceed the available resources of their target nodes.
2) Path Creation Constraints:
The path-creation constraints construct unique network paths between mapped VNF nodes while preventing invalid starts, ends, loops, and extensions.
- 2) Path Creation Constraints:: Constraints 23–27 identify required paths and enforce exactly one valid starting and ending edge for each path.They ensure paths begin at the node where the source request is mapped and end at the node where the destination request is mapped.
- 2) Path Creation Constraints:: Constraint 28 maintains path continuity by requiring an outgoing path edge after each incoming edge at intermediate network nodes.The rule excludes cases where the incoming edge is the path’s last edge or the outgoing edge is its first edge.
- 2) Path Creation Constraints:: Constraints 29–30 prevent infinite loops and unnecessary extensions of created paths.
3) Metrics Calculation Constraints:
The metric constraints mark used network nodes, compute remaining edge data rates after placement, and calculate latency for paths between mapped VNF nodes.
- 3) Metrics Calculation Constraints:: Constraint 35 calculates each network edge’s remaining data rate by subtracting the required rates of paths using it from its initial data rate.
- 3) Metrics Calculation Constraints:: Constraints 33–34 mark a network node as used when at least one function instance is mapped to it.
- 3) Metrics Calculation Constraints:: Constraint 36 sets path latency between mapped request nodes using the selected network-edge latency values.
B. Objectives
The placement model defines objectives for preserving network-link capacity and reducing the number of used nodes, with different objectives emphasizing different operational goals.
- B. Objectives: Different placement objectives can map the same VNF graphs differently because each objective prioritizes a specific goal.
- B. Objectives: The remaining-data-rate objective maximizes unused capacity across non-self-loop network edges and encourages functions placed on the same node to use self-loops.It targets lower risk from highly utilized links, which can result in congestion.
- B. Objectives: The used-node objective can produce energy-efficient placements by allowing more unused network nodes to be switched off.However, concentrating functions on a small node subset might cause network congestion.
3) Minimizing the latency of the created paths:
The latency objective minimizes mean latency across paths created for deployment requests, while evaluation examines latency trade-offs and the runtime cost of exploring optional orders.
- 3) Minimizing the latency of the created paths:: The latency objective minimizes the mean latency of all paths created for all deployment requests.In branching chains, different simple paths can have different latencies because they contain different edge sets.
- 3) Minimizing the latency of the created paths:: The three evaluated metrics can have trade-offs but are not necessarily conflicting, according to the Pareto analysis.
- 3) Minimizing the latency of the created paths:: The evaluation observes placement behavior and uses Pareto analysis to examine trade-offs between the metrics.The paper notes that no commonly accepted evaluation model exists for the actual chained functions or tenant requests.
- 3) Minimizing the latency of the created paths:: 13 minutes was the average runtime for sorting three optional-order requests, compared with 31 hours for evaluating all 144 combinations.The sorted-chain placement was optimal for remaining data rate and latency in this evaluation, but used more network nodes than some alternatives.
B. Pareto Set Analysis
Pareto analysis reveals trade-offs among remaining data rate, used nodes, and latency, while some resource conditions permit simultaneous optimization. These results help operators prioritize objectives when selecting placement solutions.
- The analysis used request sets resembling broadband, mobile core, and data center VNF chaining scenarios, with two complexity levels per scenario.
- Some placements trade off remaining data rate, used nodes, and latency, while others optimize all three metrics simultaneously.
- With enough free network resources, a placement may be optimal for remaining data rate, used nodes, and latency simultaneously.
- Using more nodes can lower latency and raise remaining data rate, but additional nodes eventually stop improving the results.
- At a fixed node count, increasing remaining data rate increases latency, so improving latency can reduce remaining data rate.
- Pareto results help operators prioritize optimization goals and choose objective functions for different placement requirements.
- The evaluations show that VNF placement decisions differ according to whether the objective is remaining data rate, latency, or used nodes.