Source-linked AI summary
Optimal Virtual Network Function Placement and Resource Allocation in Multi-Cloud Service Function Chaining Architecture
Deval Bhamare, Mohammed Samaka, Aiman Erbad, Raj Jain, Lav Gupta, H. Anthony Chan
TL;DR
The paper addresses service function chain placement across geographically distributed clouds while accounting for inter-cloud traffic, response time, deployment cost, and SLAs. It formulates an ILP model and proposes an Affinity-based Allocation heuristic, comparing it with a greedy approach as ILP scalability becomes limited.
Problem
Existing work often considers individual virtual functions or single-cloud settings, while overlooking end-to-end delays, QoS, SLAs, and interconnectivity among service chains.
Method
The paper formulates multi-cloud VNF placement and client-workflow assignment as an ILP, then uses traffic-affinity-based placement to reduce inter-cloud traffic and delays.
Results
The Affinity-based Allocation heuristic improves results by almost 50% compared with the simple greedy approach in the reported comparison.
Takeaways & Limitations
The study provides a multi-cloud SFC placement framework that incorporates deployment cost, delay tolerances, QoS, and placement-related SLAs.
Takeaways & Limitations
The ILP has high computational complexity, limiting its applicability to small user-node datasets; the model also assumes disjoint client and cloud sites with VNFs mapped directly to VMs.
Abstract
from arXiv · showhide
Service Function Chaining (SFC) is the problem of deploying various network service instances over geographically distributed data centers and providing inter-connectivity among them. The goal is to enable the network traffic to flow smoothly through the underlying network, resulting in an optimal quality of experience to the end-users. Proper chaining of network functions leads to optimal utilization of distributed resources. This has been a de-facto model in the telecom industry with network functions deployed over underlying hardware. Though this model has served the telecom industry well so far, it has been adapted mostly to suit the static behavior of network services and service demands due to the deployment of the services directly over physical resources. This results in network ossification with larger delays to the end-users, especially with the data-centric model in which the computational resources are moving closer to end users. A novel networking paradigm, Network Function Virtualization (NFV), meets the user demands dynamically and reduces operational expenses (OpEx) and capital expenditures (CapEx), by implementing network functions in the software layer known as virtual network functions (VNFs). VNFs are then interconnected to form a complete end-to-end service, also known as service function chains (SFCs). In this work, we study the problem of deploying service function chains over network function virtualized architecture. Specifically, we study virtual network function placement problem for the optimal SFC formation across geographically distributed clouds. We set up the problem of minimizing inter-cloud traffic and response time in a multi-cloud scenario as an ILP optimization problem, along with important constraints such as total deployment costs and service level agreements (SLAs). We consider link delays and computational delays in our model.
1. INTRODUCTION
The introduction motivates dynamically placing virtual network functions across geographically distributed clouds to form SFCs while reducing end-to-end delay, inter-cloud traffic, and deployment cost under SLA constraints.
- Motivation: Growing user traffic and data-centric computing increase pressure on costly, complex proprietary networks.Mobile-device growth, IoT, and resources moving closer to users motivate more flexible networking approaches.
- NFV and SFC: NFV implements network functions in software as VNFs, which can be interconnected dynamically into end-to-end SFCs.SFCs can include functions such as firewalls and deep packet inspectors.
- NFV and SFC: SFCs vary dynamically in length, branching, and VNF-instance count as user demand and traffic load change.Multiple chaining policies may also be required to satisfy SLAs and QoS requirements.
- Paper approach: The paper formulates multi-cloud SFC placement as an ILP minimizing end-to-end delay and inter-cloud traffic under deployment-cost and SLA constraints.The model includes link queues and server queues to estimate delays in geographically distributed clouds.
- Paper approach: M/D/1 models link queues and M/M/1 models server queues, while the ABA heuristic addresses larger networks beyond ILP scalability.The paper compares ABA with a greedy first-fit decreasing approach.
2. RELATED WORK
Related work covers VM, NFV, SDN, orchestration, resource allocation, and SFC placement, but identifies unresolved multi-cloud challenges involving chain interconnectivity, latency, traffic, QoS, and SLAs.
- Research gap: Prior VM-placement research largely emphasizes single-cloud environments, whereas SFC placement must account for ordered functions and dynamic traffic flows.These characteristics impose constraints beyond conventional VM placement.
- Research gap: Multi-cloud SFC placement is more complex because geographically distributed deployments must respect costly WAN link-capacity constraints.The related work contrasts WAN links with less expensive intra-datacenter links.
- Research gap: Existing work addresses SFC implementation and optimization, but interconnectivity among workloads or chains remains insufficiently considered.Latency, network traffic, and QoS optimization in data-center and inter-cloud SFC settings remain open areas.
- This paper: The paper models multiple VNF instances across multiple clouds and service chains induced by packet-flow ordering.Its optimization targets end-user latency by reducing inter-cloud traffic.
- This paper: The proposed ILP incorporates M/D/1 link queues and M/M/1 server queues, followed by affinity-based heuristics for larger networks.The heuristics are compared with ILP and with greedy first-fit decreasing.
3. OPTIMIZATION MODEL
The paper formulates multi-cloud SFC placement as an ILP that minimizes client response time while satisfying resource, allocation, cost, queuing, and SLA constraints. It models computational and link delays and varies deployment-site counts to study network delay, while recognizing that ILP complexity limits large-scale use.
- Optimization objective: The ILP minimizes response time or latency by placing VNFs and assigning client requests to workflows across multiple clouds.The model also targets inter-cloud traffic and incorporates deployment and placement constraints.
- Delay modeling: Computational delays use M/M/1 cloud queues, while link delays use M/D/1 queues whose load depends on flows traversing each link.Processing stability requires each processing rate to be at least its corresponding arrival rate.
- Decision variables: The allocation matrix assigns user nodes to cloud nodes for each virtual function, and the instance matrix records deployed instances at each site.A placement matrix indicates where each VNF may be installed under SLA rules.
- Constraints: Cloud capacity, VM capacity, unity, integrity, cost-threshold, queuing, and SLA constraints restrict feasible VNF deployments and request assignments.The unity constraint assigns each user to one cloud for a particular VNF, while users may use different clouds for different VNFs.
- Deployment-cost analysis: The number of deployment sites varies from Γmin to Γmax, with Γmax = F/f, and total network delay is observed across these settings.F is the total cost limit and f is the operational cost of one cloud.
- Objective construction: The objective sums transmission delays between successive VFs and computational delays at destination clouds, with a separate term for the first VNF.The formulation assumes VFs are visited in numerical order and supports different chains containing different subsets of functions.
- Computational limitation: The ILP has complexity O(V4M2), or O(V4) when M << V, so the optimization may be restricted to small datasets.The paper therefore proposes heuristic approaches for real-time problems with larger numbers of users.
4. HEURISTICS
The heuristics address VNF placement across clouds and allocation of user flows to placed VNFs. They combine resource, SLA, delay, cost, affinity, and cloud-location constraints when forming service chains.
- Heuristics: The problem has two stages: placing VNFs in clouds and allocating user flows to the placed VNF instances.The proposed affinity-based allocation heuristic is compared with a greedy first-fit decreasing method.
- Greedy heuristic: The greedy heuristic places required VNF instances sequentially while satisfying SLA and cloud-capacity constraints.It determines needed instances from user demands and iterates through VNF instances before allocating users.
- Placement constraints: Placement constraints distinguish edge and core clouds, requiring some VNFs near users and others at core sites.For example, NAT is assigned to edge sites while business logic is assigned to core locations.
- User allocation: Users are allocated only when sufficient VNF instances exist and predicted delays remain below their class-specific tolerance.The heuristic uses packet arrival rates and link processing rates, and includes computational delays in total delay calculations.
- Affinity-based heuristic: Affinity-based allocation co-locates VNFs with higher mutual traffic affinity to reduce inter-cloud traffic and end-to-end delay.Traffic affinity is derived from the fraction of total traffic flowing between VNF pairs.
- Affinity-based heuristic: O(N×M×V) is the stated execution complexity of affinity-based allocation, where N users, M clouds, and V virtual functions determine scale.The approach considers both VNF placement and subsequent user-flow allocation.
5. EXPERIMENTAL SETUP AND RESULTS
The experiments compare ILP, FFD Greedy, and the affinity-based approach across increasing cluster sizes, traffic loads, and larger topologies. ABA approaches ILP quality while substantially improving scalability and reducing delays relative to FFD.
- ILP scalability: ILP becomes computationally expensive as problem size increases, limiting experiments to topologies with 10–100 clusters.For 10 clusters, ILP took around 500 seconds and 4 GB RAM; for 100 clusters, about 5000 seconds and 30 GB RAM.
- ILP versus FFD Greedy: At 80% traffic load and cluster size 90, FFD Greedy trails the optimal ILP solution by almost 30% to 40%.Total response time also increases with cluster count and traffic load because queuing delays increase.
- ILP versus ABA: ABA produces close-to-optimal performance with a reduced gap from ILP and much lower response time.The reported gap between ILP and ABA is less than 10%.
- Heuristic comparison: For 100 user clusters at 40% traffic load, ABA reduces total delay from 324.5 seconds with Greedy to 139.5 seconds.The comparison uses larger input sizes and includes standard deviations and 95% confidence-interval margins of error.
- Heuristic comparison: For 1000 user-clusters at 40% traffic load, ABA lowers total delay from approximately 50K seconds with FFD to 25K seconds.The paper reports this as an improvement of almost 50%, including at larger topologies and higher traffic loads.
6. CONCLUSIONS
The paper studies multi-cloud SFC placement to reduce end-user delay and deployment cost while satisfying service constraints. It solves the placement model with ILP and proposes ABA for larger instances, where ABA improves solution quality over FFD with only a marginal execution-time increase.
- The work focuses on placing service function chains across multi-cloud environments while reducing end-user delay and deployment cost.
- The ILP model incorporates cost, QoS, delay-tolerance, placement, and traffic-affinity constraints for VNF placement.
- ABA addresses ILP’s computational-complexity limitation for larger problem instances and is compared with FFD Greedy.
- ABA substantially improves solution quality over FFD with only a marginal increase in execution time.