PaperlayerView exact revision on arXiv

Source-linked AI summary

Virtual Network Function Placement in Satellite Edge Computing with a Potential Game Approach

Xiangqiang Gao, Rongke Liu, Aryan Kaushik

arXiv:2012.00941v3cs.NIcs.DC

TL;DR

Remote IoT users may lack terrestrial coverage, and satellite edge resources are limited, motivating cost-aware VNF placement. The paper uses a decentralized potential game to allocate ordered service chains; simulations report that PGRA outperforms Viterbi and Greedy, including in the N=12 network-payoff comparison.

  • Problem

    The paper addresses VNF placement for satellite edge computing, aiming to serve more IoT users while minimizing deployment costs under limited satellite resources.

    Source: §I · p. 2, A. Problem Description · p. 4

  • Method

    The authors formulate VNF placement as a potential game and use decentralized PGRA iterations to seek a Nash equilibrium.

    Source: §I · p. 2, A. VNF Placement Game · p. 7

  • Results

    For N=12, PGRA’s average network payoff increases by 0.96% over Viterbi and 2.08% over Greedy.

    Source: §VII · p. 14

  • Takeaways & Limitations

    The potential-game formulation has the finite improvement property, so the placement problem can be addressed by iterating toward a Nash equilibrium.

    Source: A. VNF Placement Game · p. 7

Abstract

from arXiv · show

Satellite networks, as a supplement to terrestrial networks, can provide effective computing services for Internet of Things (IoT) users in remote areas. Due to the resource limitation of satellites, such as in computing, storage, and energy, a computation task from a IoT user can be divided into several parts and cooperatively accomplished by multiple satellites to improve the overall operational efficiency of satellite networks. Network function virtualization (NFV) is viewed as a new paradigm in allocating network resources on-demand. Satellite edge computing combined with the NFV technology is becoming an emerging topic. In this paper, we propose a potential game approach for virtual network function (VNF) placement in satellite edge computing. The VNF placement problem aims to maximize the number of allocated IoT users, while minimizing the overall deployment cost. We formulate the VNF placement problem with maximum network payoff as a potential game and analyze the problem by a game-theoretical approach. We implement a decentralized resource allocation algorithm based on a potential game (PGRA) to tackle the VNF placement problem by finding a Nash equilibrium. Finally, we conduct the experiments to evaluate the performance of the proposed PGRA algorithm. The simulation results show that the proposed PGRA algorithm can effectively address the VNF placement problem in satellite edge computing.

I. INTRODUCTION

Remote IoT users may lack terrestrial coverage, while LEO satellites offer edge computing but have limited resources. The paper frames VNF placement as a cost-aware allocation problem and proposes a decentralized potential-game algorithm.

I. INTRODUCTION

  • The objective is to maximize allocated IoT users while minimizing energy, bandwidth, and service-delay deployment costs through maximum network payoff.Each request is an ordered SFC of VNFs, and network payoff sums allocated users’ payoffs.Source: §I · p. 2
  • PGRA formulates VNF placement as a potential game and uses decentralized strategy updates toward a Nash equilibrium, with Viterbi search for each request’s feasible path.The method assumes players’ allocation strategies can be shared through message synchronization.Source: §I · p. 2
  • PGRA outperforms the Greedy and Viterbi baselines in the reported LEO satellite simulations.The supplied introduction reports the comparison without giving an aggregate numerical result.Source: §I · p. 2

II. RELATED WORK

  • Prior satellite offloading work often treats a computation task as a whole, whereas this paper places ordered VNFs across LEO satellites and routes flows between adjacent VNFs.The paper also jointly considers energy, bandwidth, and service delay costs.Source: §II · p. 2

III. SYSTEM MODEL

  • The system model covers the physical network, user requests, and VNF placement in satellite edge computing.The supplied system-model passage states these components but does not provide their detailed specifications.Source: §III · p. 3

A. Satellite Network

The system model represents the satellite network, ordered VNF requests, and time-varying resource allocation. It assumes fixed topology during each request’s service period and illustrates how requests can be placed and routed across satellites.

A. Satellite Network

  • The network is a directed graph of satellite nodes and inter-satellite links, with limited node resources and link bandwidth and transmission delay.The model considers CPU and storage at satellite nodes and four neighboring inter-satellite links per satellite.Source: A. Satellite Network · p. 3

B. User Requests

  • Each user request is an ordered SFC of VNFs, with per-VNF resource and execution-time requirements and bandwidth requirements on links between VNFs.Requests also have source and destination nodes and a maximum acceptable delay.Source: B. User Requests · p. 3

C. VNF Placement Problem

  • Requests arrive in batches at each time slot, and completed requests release resources for new allocations under remaining-resource and service constraints.The satellite topology is assumed constant throughout each request’s computing-service period.Source: C. VNF Placement Problem · pp. 3–4
  • The three-user example places one request’s VNFs on a single satellite and splits the other requests’ VNFs across satellites along routed paths.The example uses nine satellite nodes; the supplied table passage gives only its title, not its contents.Source: C. VNF Placement Problem · p. 4, Table I · p. 4

IV. PROBLEM FORMULATION

The VNF placement problem is formulated as an integer nonlinear program that maximizes network payoff under satellite resource and service constraints. Network payoff aggregates user payoffs tied to energy, bandwidth, and delay costs.

A. Problem Description

  • The objective maximizes overall network payoff, equivalent to allocating more user requests while minimizing energy, bandwidth, and service-delay costs.The formulation is an integer nonlinear program subject to physical-resource and service-requirement constraints.Source: A. Problem Description · pp. 4, 6
  • Each request's deployment cost is a weighted sum of normalized energy, bandwidth, and service-delay costs, and its payoff is non-negative and inversely proportional to that cost.The weights adjust preferences among the three costs and sum to one.Source: A. Problem Description · pp. 4–6
  • Binary placement variables indicate which satellite hosts each VNF, while binary path variables identify the routes used between adjacent VNFs.A separate binary variable indicates whether a request is deployed to satellites.Source: A. Problem Description · pp. 4–5
  • Energy costs distinguish VNF placement across four edge-server states, including off or idle servers that will or will not provide service in the next time slot.The formulation accounts for the server's current state and expected next-slot service when modeling placement energy.Source: A. Problem Description · p. 5
  • A request's source-to-destination delay includes VNF computation and transmission, and its acceptable delay uses average transmission time across satellite-network paths.Source: A. Problem Description · pp. 5–6
  • Feasible placement requires each VNF to occupy one satellite and a route to connect the satellites hosting adjacent VNFs.Source: A. Problem Description · p. 6
  • Satellite resource demands must stay within node capacities, link bandwidth use within link capacity, and each request's source-to-destination delay within its limit.Source: A. Problem Description · p. 6
  • Edge-server idle and off durations are constrained by their respective maximum-idle and minimum-off thresholds.Source: A. Problem Description · p. 6

B. Problem Analysis

The VNF placement problem is shown to be NP-hard by reducing the capacitated plant location problem with single-source constraints to it. The reduction maps plant locations, capacities, customers, and costs to satellite-network counterparts.

B. Problem Analysis

  • Because the capacitated plant location problem with single-source constraints is NP-hard, the corresponding VNF placement problem is also NP-hard.Source: B. Problem Analysis · pp. 6–7
  • The reduction maps plants to satellite nodes, plant capacities to satellite resources, customers to user requests, and customer demands to computation-resource requirements.Source: B. Problem Analysis · pp. 6–7
  • Plant operational costs correspond to energy costs, while transportation costs correspond to bandwidth and source-to-destination delay costs.Source: B. Problem Analysis · p. 7

V. VNF PLACEMENT GAME AND PROPOSED ALGORITHM

The section formulates VNF placement as a potential game, analyzes its properties, and proposes a decentralized resource-allocation algorithm.

V. VNF PLACEMENT GAME AND PROPOSED ALGORITHM

  • The VNF placement problem is formulated as a potential game.Source: §V · p. 7
  • The game is analyzed using a game-theoretical approach.Source: §V · p. 7
  • A decentralized resource-allocation algorithm based on a potential game is proposed to address VNF placement.Source: §V · p. 7

A. VNF Placement Game

The game treats user requests as players choosing VNF placements, with payoffs that can conflict. Its network-payoff potential is exact, supporting a finite-iteration search for Nash equilibrium.

A. VNF Placement Game

  • A Nash equilibrium is reached when no player can unilaterally change strategy to improve its payoff.Source: A. VNF Placement Game · p. 7
  • Each user request is a player whose strategy is its VNF placement solution, and requests' payoff-maximizing strategies can conflict.Source: A. VNF Placement Game · p. 7
  • The game is an exact potential game whose potential function is the network payoff.Source: A. VNF Placement Game · p. 7
  • Because the game has the finite improvement property, placement can be addressed by finding a Nash equilibrium through finite gradual iteration.Source: A. VNF Placement Game · p. 7

B. Decentralized Resource Allocation Algorithm

PGRA decentralizes VNF placement through a potential game, with a Viterbi search that approximates each user request’s placement strategy. The resulting strategy profile is a Nash equilibrium and an approximate VNF-placement solution.

B. Decentralized Resource Allocation Algorithm

  • PGRA uses a decentralized potential-game algorithm to find an approximate VNF-placement solution, since the placement problem is NP-hard.Satellites interact by sharing network-resource states and placement strategies, without exchanging information with IoT users during the algorithm’s running time.Source: B. Decentralized Resource Allocation… · p. 7
  • For each request, PGRA evaluates its d shortest source-to-destination paths and uses Viterbi to find a high-payoff placement strategy for each path.The request’s best strategy is selected while other requests’ strategies remain unchanged; only the request that maximizes overall network payoff wins the update opportunity.Source: B. Decentralized Resource Allocation… · p. 8
  • The final strategy profile is a Nash equilibrium and represents an approximate solution to VNF placement.Iterations stop when no request has an incentive to deviate unilaterally or the maximum iteration threshold is exceeded.Source: B. Decentralized Resource Allocation… · p. 8
  • Viterbi models the ordered VNFs as stages and deployment choices as states, then selects a minimum-cumulative-cost state path.To limit search complexity, the algorithm retains the first B candidate paths by user payoff at each stage; Algorithm 2 has complexity O(FBN).Source: B. Decentralized Resource Allocation… · pp. 8–9

VI. PERFORMANCE EVALUATION

The evaluation tests PGRA in satellite-edge VNF placement, examining parameter effects and comparing it with centralized baselines. It also considers online strategy performance.

VI. PERFORMANCE EVALUATION

  • The experiments evaluate PGRA for VNF placement in satellite edge computing.The evaluation includes both system-parameter effects and comparisons with two centralized baseline algorithms.Source: §VI · p. 9
  • A Taguchi design varies the number of shortest paths d and the Viterbi search-tree width B.These two factors are used to investigate system-parameter effects on PGRA performance.Source: §VI · p. 9
  • PGRA is compared with Viterbi and Greedy using network payoff and percentage of allocated users.The section also discusses PGRA performance in online strategy.Source: §VI · p. 9

A. Simulation Setup

The simulations model LEO satellite networks with edge servers and randomly generated service chains and resource demands. They use a commodity server as the simulation platform.

A. Simulation Setup

  • The simulation varies the network size across 6, 9, 12, and 15 LEO satellites, each equipped with an edge server.Each server is configured with 112 vCPUs and 192 GB of memory; inter-satellite links have 100 Mbps capacity.Source: A. Simulation Setup · pp. 9–10
  • User service-function chains and resource requirements are randomly generated, with 5–10 VNFs per request.Each non-source, non-destination VNF requires 4–8 vCPUs and 4–16 GB of memory; VNF execution takes 10–30 ms and adjacent-VNF bandwidth demand is 10–30 Mbps.Source: A. Simulation Setup · p. 10
  • The simulation runs on a commodity server with an i7-4790K CPU, 16 GB memory, and Windows 10.The implementation uses Python; the three weights in equation (10) are set equally to 1/3.Source: A. Simulation Setup · p. 10

B. System Parameters Evaluation

The parameter study finds better network payoff as d and B increase, but larger settings raise computational complexity. Its reported ideal settings are d = 8 and B = 4.

B. System Parameters Evaluation

  • Network payoff improves as d and B increase for M = 10, 20, and 30 user requests.The study uses a Taguchi design with four levels for each factor: 1, 2, 4, and 8.Source: B. System Parameters Evaluation · p. 10
  • Larger d expands PGRA’s explored solution space, while larger B retains more Viterbi states for later search stages.Both settings can improve performance, but they also increase computational complexity.Source: B. System Parameters Evaluation · p. 10
  • The reported ideal parameter settings are d = 8 and B = 4.The authors recommend considering the two values as a tradeoff rather than simply maximizing both.Source: B. System Parameters Evaluation · p. 10

C. Performance Comparison with Baseline Algorithms

In static satellite networks, PGRA generally outperforms Viterbi and Greedy on deployment costs, network payoff, and allocated-user percentages. Its advantages vary with request load and network size, while resource limits constrain allocation as demand grows.

C. Performance Comparison with Baseline Algorithms

D. Performance Analysis in On-line Strategy

In an online setting with requests arriving over time and resources released after their run periods, PGRA is compared with Viterbi and Greedy across four satellite-network sizes. It outperforms both in network payoff and allocated-user percentages, while bandwidth and delay comparisons show trade-offs.

D. Performance Analysis in On-line Strategy

  • PGRA has lower energy costs across the four network sizes, but its bandwidth costs exceed Viterbi's at 12 and 15 satellites, as do its delay costs there.The paper attributes the delay comparison to a trade-off between bandwidth use and energy consumption.Source: D. Performance Analysis in On-line… · p. 13, Figure 9 · p. 14
  • In online experiments with 6, 9, 12, and 15 satellites, PGRA achieves higher network payoff and allocated-request percentages than Viterbi and Greedy.Its payoff improvements over Viterbi are 1.31%, 0.21%, 0.31%, and 0.42%, and over Greedy are 2.92%, 1.45%, 0.73%, and 1.18%, respectively.Source: D. Performance Analysis in On-line… · pp. 13–14, Figure 9 · p. 14
  • Across 6-, 9-, 12-, and 15-satellite networks, PGRA allocated 96.01%, 99.50%, 99.96%, and 99.92% of user requests, outperforming Viterbi and Greedy in this dynamic environment.Source: D. Performance Analysis in On-line… · p. 14

VII. CONCLUSION

The paper formulates VNF placement as an NP-hard potential game and proposes decentralized PGRA to seek an approximate solution. Simulations report higher network payoff and allocated-user percentages than Viterbi and Greedy, including in a dynamic environment.

VII. CONCLUSION

  • The NP-hard VNF placement problem seeks to maximize allocated user requests while minimizing deployment costs for energy, bandwidth, and service delay.The formulation uses maximum network payoff as a potential game, with requests making deployment decisions in a distributed manner.Source: §VII · p. 14
  • PGRA is a decentralized resource-allocation algorithm that uses the potential game's Nash equilibrium property to find an approximate solution.The paper states that requests optimize strategies by competing with one another.Source: §VII · p. 14
  • For N = 12, average network payoff rises 0.96% over Viterbi and 2.08% over Greedy, while allocated-user percentage improves 0.43% and 1.46%, respectively.These comparisons are reported for the satellite-network experiments.Source: §VII · p. 14
  • For dynamic environments at N = 12, network payoff improves 0.31% over Viterbi and 0.73% over Greedy, while allocated-user percentage increases 0.09% and 0.16%, respectively.The reported improvements compare PGRA with the same two baseline algorithms.Source: §VII · p. 14
Loading 2012.00941v3…