PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Tenant Radio Access Network Slicing: Statistical Multiplexing of Spatial Loads

P. Caballero, A. Banchs, G. de Veciana, X. Costa-Perez

arXiv:1607.08271v2cs.NI

TL;DR

Dynamic RAN slicing must allocate resources fairly across operators and their users while adapting to changing network loads. This paper proposes weighted proportional-fair resource sharing and an approximation algorithm, reporting capacity savings and improved download times in simulations.

  • Problem

    Dynamic multi-tenant slicing requires fair resource allocation across operators and their users while accounting for user association and changing network loads.

    Source: §I · p. 1, A. System model · p. 2

  • Method

    The paper formulates MORA as weighted proportional-fair resource allocation and proposes a distributed semi-online approximation algorithm for its NP-hard optimization.

    Source: §I · pp. 1–2

  • Results

    Operators can save up to 80% capacity while providing the same user quality, and file download times improve by up to 30% for fixed capacity.

    Source: §I · p. 2

  • Takeaways & Limitations

    The paper’s analytical results and simulations support practical solutions that scale to large networks and track network-load dynamics.

    Source: §V · p. 11

Abstract

from arXiv · show

This paper addresses the slicing of Radio Access Network (RAN) resources by multiple tenants, e.g., virtual wireless operators and service providers. We consider a criterion for dynamic resource allocation amongst tenants, based on a weighted proportionally fair objective, which achieves desirable fairness/protection across the network slices of the different tenants and their associated users. Several key properties are established, including: the Pareto optimality of user association to base stations, the fair allocation of base stations resources, and the gains resulting from dynamic resource sharing across slices, both in terms of utility gains and capacity savings. We then address algorithmic and practical challenges in realizing the proposed criterion. We show that the objective is NP-hard, making an exact solution impractical, and design a distributed semi-online algorithm which meets performance guarantees in equilibrium and can be shown to quickly converge to a region around the equilibrium point. Building on this algorithm, we devise a practical approach with limited computational, information, and handoff overheads. We use detailed simulations to show that our approach is indeed near-optimal and provides substantial gains both to tenants (in terms of capacity savings) and end-users (in terms of improved performance).

I. INTRODUCTION

The paper proposes dynamic resource slicing among operators to address changing spatial loads and the limits of long-term fixed sharing agreements. Its MORA criterion uses weighted proportional fairness to allocate resources across operators and among their users.

I. INTRODUCTION

  • Dynamic slicing replaces long-term fixed sharing agreements with resource allocation that adapts to changing user numbers, locations, and transmission rates.The paper also anticipates slices for service providers as well as traditional and virtual operators.Source: §I · p. 1
  • A practical sharing criterion must balance fairness across operators and within each operator’s users, accommodate coarse-grained sharing levels, and account for spatially varying demand.The implementing algorithm must also be distributed, computationally efficient, responsive to network changes, and limit handoff overhead.Source: §I · p. 1
  • The weighted proportional-fair multi-operator problem is NP-hard, motivating an approximation algorithm; prior work addressed single-operator networks or lacked an efficient algorithm grounded in analytical results.The paper identifies its contribution as an efficient algorithm for multi-tenant slicing supported by analytical results.Source: §I · p. 2

B. MORA criterion

  • MORA jointly optimizes user association to base stations and allocation of base-station resources, using weighted proportional fairness based on operator shares.Each user’s weight is the operator’s network share divided equally among its current users.Source: §II · p. 2, B. MORA criterion · p. 3

A. System model

  • The system model represents users as associated with one base station and receiving rates determined by their user–station transmission rates and allocated resource fractions.The model is developed with LTE/LTE-A systems in mind and is stated to apply generally to cellular systems.Source: A. System model · pp. 2–3

C. Properties of MORA Resource Allocation

MORA allocates each base station’s resources proportionally to associated users’ weights and produces Pareto-optimal user associations. Its operator-level utility also cannot be substantially improved by unilateral reassociation.

1) Per-base station resource allocation:

  • At each base station, MORA allocates resources among associated users in proportion to their weights; for an optimal association, this is the MORA resource allocation.The allocation is unique when user associations are fixed.Source: 1) Per-base station resource allocation · p. 3
  • An operator’s allocation depends on its active-user count and spatial distribution, because operator weights and the loads of the base stations serving its users affect resource availability.The allocations are coupled across base stations through the operator’s total user count.Source: 1) Per-base station resource allocation · p. 4

2) Characteristics of user association:

  • MORA allocations are Pareto-optimal: improving one user’s throughput through an alternative allocation requires lowering another user’s throughput.The result rules out an association in which a user could gain throughput without another user losing throughput.Source: 2) Characteristics of user association · p. 4
  • An operator that unilaterally changes its users’ associations and reallocates resources under MORA can improve its utility by at most log(e).The theorem bounds the utility loss relative to the MORA optimum below by −log(e).Source: 2) Characteristics of user association · p. 4

D. Gains and Savings

Against static slicing, MORA dynamically shares resources and protects operator utility under a fixed user association. The section also develops a model for estimating capacity savings under spatially homogeneous traffic.

1) Static Slicing (SS) Baseline:

  • Static slicing gives each operator a fixed fraction of every base station’s resources, while MORA’s less constrained allocations yield higher overall network utility.Within its fixed slice, an operator can still optimize its user associations and resource allocations.Source: D. Gains and Savings · p. 4, 1) Static Slicing (SS) Baseline · p. 4

2) Operator Utility Gains and Protection:

  • For the same user association, every operator’s utility under MORA is at least its utility under static slicing, whose fixed per-base-station shares restrict resource allocation.Static slicing still lets each operator optimize its own users’ associations and allocation within its contracted slice.Source: 2) Operator Utility Gains and Protection · pp. 4–5, 1) Static Slicing (SS) Baseline · p. 4
  • When MORA and static slicing may choose different user associations, the operator utility gap under MORA is bounded below by −log(e).The result allows that an operator can have higher utility under static slicing, but the additional utility is no more than log(e).Source: 2) Operator Utility Gains and Protection · p. 5

3) Capacity Savings:

  • The capacity-savings analysis compares the spectrum required for equal average utility per operator under MORA and static slicing, assuming spatially homogeneous traffic and shares proportional to load.It models users as uniformly distributed across base stations, with equal per-user capacity to associated stations.Source: 3) Capacity Savings · p. 5

¯U MORA

The capacity-savings analysis links dynamic sharing gains to operators’ shares and user loads per base station. The paper then turns to an approximation algorithm because the MORA problem is difficult to solve exactly.

¯U MORA

  • Sharing savings are greatest when many operators have few users per base station, because larger operators already have substantial multiplexing gains without sharing.Savings also increase when an operator has a small network share; the analysis assumes its user count is proportional to that share.Source: ¯U MORA · p. 5

III. APPROXIMATION ALGORITHM FOR MORA

  • The paper characterizes MORA as NP-hard and introduces an approximation algorithm to address its complexity and the overheads of dynamic settings.The algorithm is presented as a response to changing mobile users and channels, where complexity and information overheads become excessive.Source: §III · p. 6

A. Complexity and State-of-the-Art Algorithms

MORA is NP-hard, motivating a distributed, semi-online algorithm that permits limited reassociations. Distributed Greedy has a logarithmic equilibrium performance bound, while the design targets practical computational and information overheads.

A. Complexity and State-of-the-Art Algorithms

  • The MORA optimization problem is a non-linear integer program and is NP-hard.An exact polynomial-time solution would imply P = NP.Source: A. Complexity and State-of-the-Art… · p. 6
  • Earlier alternatives are described as impractical at scale: takes 20 seconds for 100 users, while becomes impractical at about 50 users.The cited approaches are centralized; also provides no analytical performance bounds.Source: A. Complexity and State-of-the-Art… · p. 6

B. Algorithm design

  • The proposed algorithm tracks user dynamics and uses neighboring-base-station data for distributed operation, while limiting reassociations to control handoff overhead.Its design addresses joining, moving, and leaving users.Source: B. Algorithm design · p. 6

1) Need for reassociations:

  • An online algorithm that never reassociates existing users can have an unbounded utility gap from MORA, motivating semi-online approaches.Semi-online algorithms may reassociate a limited number of existing users when a new user joins.Source: 1) Need for reassociations · p. 6

2) Criterion for (re)associations:

  • At equilibrium, Distributed Greedy guarantees W(x′, f′) ≥ W(xMORA, fMORA) − log(e), close to ’s slightly tighter log(2 + ϵ) bound.The equilibrium guarantee is stated for the algorithm’s equilibrium allocation.Source: 2) Criterion for (re)associations · pp. 6–7

3) Order of reassociations:

Greedy Largest Gain gives a bounded utility trajectory, and the joining procedure limits reassociations while selecting candidates locally. The paper reports that a cap of three reassociations brings simulated utility close to its unconstrained-overhead maximum.

3) Order of reassociations:

  • GLLG utility increases until it is within 2 log(e) of MORA, then never falls below a gap of (2 + max_u w_u) log(e).When all operators have many users, 2 + max_u w_u ≈ 2.Source: 3) Order of reassociations · p. 7
  • For a joining user, GLLG considers reassociations among users at two base stations, selects candidates locally, and caps the number of reassociations at m.The final reassociation step selects the association that maximizes overall network utility rather than the reassociated user's throughput.Source: 3) Order of reassociations · p. 7
  • When users join, leave, or move, the procedure updates associations to rebalance base-station loads; a move can trigger the departure procedure at the old station and joining procedure at the new one.For the final joining step, the selected association maximizes network utility to avoid harming overall performance.Source: 3) Order of reassociations · p. 7

5) Controlling the number of reassociations:

  • The reassociation cap's theoretical performance improves exponentially with m, suggesting that a small cap can yield near-optimal network utility.The analysis compares maximum load under the m-reassociation algorithm with maximum load under the unconstrained optimum, for equal user weights and rates.Source: 5) Controlling the number of… · p. 8
  • For m = 3, normalized utility gains are already very close to their maximum across the scenarios shown in Fig. 1.The paper consequently sets m equal to 3 for the Section IV experiments.Source: Figure 1 · p. 8, 5) Controlling the number of… · p. 8

IV. PERFORMANCE EVALUATION

In dense small-cell simulations, the proposed approach approaches centralized and distributed-greedy utility performance while reducing handoff overhead. MORA also yields positive utility gains for operators relative to static slicing, with larger gains in scenarios with more operators and lower loads.

IV. PERFORMANCE EVALUATION

  • The evaluation models dense small-cell deployments with 200-meter intersite spacing and 3-sector antennas, using a 57-sector network by default.Unless otherwise stated, all operators have equal shares, user counts are proportional to operator shares, and confidence intervals are below 1%.Source: §IV · p. 8

A. Utility gains

  • GLLG performs closely to DG and the centralized baseline, with a small utility cost for reducing handoff overhead; both improved association and dynamic sharing yield significant gains over static slicing.The comparisons use a scenario with 10 users per sector and 3 operators, evaluating network utility as network size varies.Source: A. Utility gains · p. 9, Figure 2 · p. 9
  • MORA produces positive operator-utility differences versus static slicing, with larger gains when there are more operators and lower loads.The figure presents distributions across multiple simulation runs for different operator counts and user densities.Source: A. Utility gains · p. 9, Figure 3 · p. 9

B. Capacity savings

Dynamic sharing delivers capacity savings and improves user performance, while the practical algorithm keeps computational and handoff overheads low. Simulations show that savings respond to user load and mobility patterns, and remain beneficial under non-uniform loads.

B. Capacity savings

  • Dynamic sharing achieves substantial capacity savings against both static-slicing baselines at matched network utility.The baselines use either SINR-based or enhanced user association.Source: B. Capacity savings · p. 9
  • Capacity savings rise with operator count and fall with per-sector user load; lighter loads allow greater statistical-multiplexing gains.The theoretical savings analysis is also confirmed under real conditions, with smaller-share operators benefiting more.Source: B. Capacity savings · pp. 9–10, Figure 5 · p. 10

C. User performance

  • Against static slicing with enhanced association, the approach improves median and percentile per-user throughput; file-download gains are substantial and fairly independent of file size.The throughput comparison also includes static slicing with SINR-based user association.Source: C. User performance · p. 10, Figure 6 · p. 10, Figure 7 · p. 10

D. Computational complexity

  • GLLG has lower execution time than the Distributed Greedy approach, while both run much faster than the centralized and non-linear-solver algorithms.Execution time is measured against user count for a fixed network size and four operators; GLLG limits handovers.Source: D. Computational complexity · p. 10, Figure 8 · p. 11

E. Impact of non-uniform load distributions

  • Under the SLAW mobility model with a shared mobility pattern, capacity savings decrease gradually as load non-uniformity increases.The authors attribute the decrease to reduced multiplexing gains when users cluster in some areas.Source: E. Impact of non-uniform load… · p. 11, Figure 9 · p. 11
  • When operators follow different mobility patterns, capacity savings instead increase with non-uniformity because their users concentrate in different hotspots.The comparison uses distinct SLAW instances to generate the operators’ hotspots.Source: E. Impact of non-uniform load… · p. 11, Figure 10 · p. 11

V. CONCLUSIONS

  • Analytical results support near-optimal allocations, and simulations show robust operator capacity savings and improved user performance.The proposed practical solutions are designed to scale to large networks and track load dynamics.Source: §V · p. 11

APPENDIX

The appendix supports allocation comparisons and complexity and convergence claims with optimization arguments, a 3-dimensional-matching reduction, and potential-function reasoning.

APPENDIX

  • For a fixed user association, SS maximizes each operator’s utility by equally distributing its resource blocks among that operator’s users.Source: APPENDIX · p. 12
  • Theorem 1’s optimization step allocates each base station’s resource share xb in proportion to yb.The constrained optimization is maximized at xb = yb / Σb′∈B yb′.Source: APPENDIX · p. 13
  • Theorem 3’s comparison bounds MORA utility against an intermediate allocation and shows MORA utility is at least SS utility for that same association.Source: APPENDIX · p. 13
  • The MORA decision problem is NP-hard via a 3-dimensional-matching reduction: a matching exists if and only if network utility reaches the stated threshold.The threshold is W = (n/m) log(R/2) + ((m − n)/m) log(R).Source: APPENDIX · p. 13
  • With |B|² arrivals followed by all but |B| users departing, the online algorithm’s utility gap is log(|B|), which grows unboundedly with |B|.Source: APPENDIX · p. 13
  • The Greedy Largest Gain proof uses W as a generalized ordinal potential, yielding finite convergence to a state where no user meets the reassociation condition.W increases at each iteration until that region is reached.Source: APPENDIX · pp. 14–15
  • When all users satisfy the reassociation condition, utility is at least MORA utility minus 2 log(e); a subsequent move permits a bound of (2 + maxu wu) log(e).After that move, utility increases until it again reaches the 2 log(e) bound.Source: APPENDIX · p. 15
Loading 1607.08271v2…