{'fraction_non_alphanumeric': 0.036555891238670694, 'fraction_numerical': 0.009799848942598187, 'mean_word_length': 4.353922361504246, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Low-Complexity Distributed Radio Access Network Slicing: Algorithms and Experimental Results

Radio access network (RAN) slicing is an effective methodology to dynamically allocate networking resources in 5G networks. One of the main challenges of RAN slicing is that it is provably an NP-Hard problem. For this reason, we design near-optimal low-complexity distributed RAN slicing algorithms. First, we model the slicing problem as a congestion game, and demonstrate that such game admits a unique Nash equilibrium (NE). Then, we evaluate the Price of Anarchy (PoA) of the NE, i.e., the efficiency of the NE as compared to the social optimum, and demonstrate that the PoA is upper-bounded by 3/2. Next, we propose two fully-distributed algorithms that provably converge to the unique NE without revealing privacy-sensitive parameters from the slice tenants. Moreover, we introduce an adaptive pricing mechanism of the wireless resources to improve the network owner's profit. We evaluate the performance of our algorithms through simulations and an experimental testbed deployed on the Amazon EC2 cloud, both based on a real-world dataset of base stations from the OpenCellID project. Results conclude that our algorithms converge to the NE rapidly and achieve near-optimal performance, while our pricing mechanism effectively improves the profit of the network owner.


I. INTRODUCTION
Thanks to the ubiquitousness of modern smartphones and the rise of the Internet of Things (IoT), the number of mobile devices has seen an unprecedented expansion over the last few years. The latest report by Ericsson Mobility forecasts that the number of 5G subscriptions will exceed half a billion by the end of 2022, including more than 1.5 billion IoT devices equipped with cellular connections [1]. This massive increase in the number of connected devices will necessarily result in a staggering growth in cellular data traffic. For this reason, 5G cellular networks are expected to meet stringent requirements on ubiquitous connectivity, extremely low latency, and very high-rate data transfer [2][3][4].
What 5G systems are going to be has yet to be determined. However, there is wide consensus that 5G systems will singlehandedly cater to a plethora of different services, such as automotive, mobile broadband, and tactile Internet, just to name a few. Each service will have its own networking requirements, which will ultimately require the network to be polymorphic and seamlessly adapt to different constraints. To address this challenging problem, the notion of network slicing [5][6][7][8][9] has been recently proposed, where the physical and computational resources of the network are seen as a unique "object" that can be "sliced" and "served" according to an entity's current needs. In this way, heterogeneous requirements can be served by the same infrastructure in a cost-effective manner, as different network slice instances can be orchestrated and configured according to the specific requirements of the slice tenants.
Challenges. Network slicing does not just provide better network performance, but it also enables realistic and profitable business models in the mobile network ecosystem. In this paper, we consider the problem of network slicing in the context of radio access networks (RANs), where telco operators (TOs) provide physical network resources to mobile virtual network operators (MVNOs), who periodically rent slices to provide cellular network access to mobile users (MUs). While a similar model is currently being successfully applied by Amazon Web Services or Microsoft Azure in the context of cloud services, slicing RAN resources is an intrinsically different problem, since (i) spectrum is a scarce resource for which overprovisioning is not possible; (ii) the network capacity is dynamic and heavily depends on the location of the MUs, among other factors; and (iii) the agreements with MVNOs usually impose stringent requirements on the Quality of Experience (QoE) perceived by the MUs.
The main issue in designing RAN slicing algorithms is that the most realistic problem formulations are provably NP-hard [10]. For this reason, most of existing work has focused only on the architectural aspects of network slicing [11,12], with a limited focus on algorithmic aspects. Only very recently have a number of centralized algorithms for RAN slicing been proposed [10,13]. Although these algorithms achieve optimality, they do not scale with the number of MVNOs and RAN resources. This issue calls for the design and analysis of near-optimal, lower-complexity algorithms for RAN slicing. Another crucial aspect is that optimality is often achieved to the detriment of privacy. Specifically, it is assumed that the TO is provided with complete information regarding the MVNOs' system parameters and preferences, for example, monetary budget, number and location of served MUs, business strategies, and so on. Instead, in realistic scenarios MVNOs may be reluctant to disclose such sensitive information to the TOs. Finally, centralized solutions do not consider the competitive and selfish behavior of modern MVNOs, who will dynamically adopt different strategies to maximize their own utility without considering the broader needs of the network as a whole. This implies that distributed algorithms are in general more desirable than centralized solutions, as they are more likely to be adopted by MVNOs in real-world RAN slicing scenarios.

arXiv:1803.07586v1 [cs.NI] 20 Mar 2018
Contributions. In this paper, we investigate the challenging and novel problem of designing privacy-preserving, lowcomplexity, near-optimal distributed algorithms for RAN network slicing, where the MVNOs selfishly compete with each other to acquire slices from the TOs while minimizing their cost. First, we first mathematically formulate this problem; then, we rely on the game-theoretical framework of congestion games [14][15][16] to effectively model and analyze the competition among MVNOs. Next, we demonstrate the existence and uniqueness of the Nash equilibrium (NE) associated to the game, and prove that its Price of Anarchy (PoA), i.e., the efficiency of the NE as compared to the social optimum, is limited to 3 /2. We formulate two distributed algorithms that preserve the privacy of the MVNOs and provably converge to the unique NE. Moreover, we propose a pricing algorithm based on a stochastic iterative mechanism that allows the TO to optimize its profit by adapting pricing policies to the current load on the resources being sliced. Finally, we extensively evaluate the performance of our algorithms through simulations and a practical testbed implemented on the Amazon EC2 cloud [17], both based on a real-world dataset of base stations (BSs) from the OpenCellID project [18]. Results demonstrate the effectiveness of the proposed approach, as our algorithms converge to the NE rapidly while achieving near-optimal performance.
Paper Organization. The paper is organized as follows. Section II introduces the network scenario, while Section III defines the RAN slicing problem. Sections IV to VII introduce and analyze the network slicing problem as a congestion game, and present the distributed and privacy-preserving algorithms that compute the NE for the MVNOs in such game. Pricing and profit issues are discussed in Section VII. Sections VIII and VIII-D present the numerical and experimental results, while Sections IX and X conclude the paper by discussing related work and drawing conclusions, respectively.

II. NETWORK SCENARIO AND PROBLEM OVERVIEW
In this paper, we consider the network scenario depicted in Figure 1, which is composed by a core network (CN) and a radio access network (RAN). The CN is connected to the Internet and is in charge of routing uplink and downlink traffic. Furthermore, the RAN is composed of multiple heterogeneous remote radio heads (RRHs). We assume that both the CN and the RAN are owned and managed by a single TO. However, our model can also be applied to the more general case of multiple infrastructure owners. Given that RRHs are geographically located at different areas of the network, the RAN can be divided into multiple RAN clusters, which group together RRHs that are close to each other.
In the considered scenario, the TO dynamically leases the network infrastructure to multiple MVNOs, who do not own any infrastructure and build virtual RANs to provide MUs with networking capabilities [6]. Since RAN clusters are geographically isolated and autonomous, slicing policies are enforced on each RAN cluster individually.
We consider the problem of generating autonomous virtual RANs on top of the resources provided by the physical RAN owned by the TO. A virtual RAN is thus referred to as a network slice, since it represents a virtual "portion" of the physical RAN. Resources that may be assigned in each slice include available spectrum, antennas, computing resources, and so on. In this scenario, it is realistic to assume the MVNOs will need to provide the TO with some sort of payment based on the number and type of resources allocated to their slices. Thus, the slicing problem reduces to finding an allocation policy for each MVNO, to minimize the cost associated to its slice while ensuring that a predetermined number of MUs can be served. Within each slice, MVNOs are free to assign resources to the MUs according to their internal policies.
This problem can be approached in two different ways. In the first approach, which we call centralized, the TO collects the number of MUs that each MVNO would like to serve, referred to as MVNO user load. Then, the TO computes the slices by solving an optimization problem that takes the MVNO user loads into account. Although simple in nature, this approach suffers from a number of disadvantages. First, it requires the MVNOs to disclose their user load to the TO, which clearly raises privacy concerns as the MVNOs are usually interested in hiding such information from external entities. Second, since centralized approaches find the global optimum by mathematical optimization [10], they require significant computational resources as the network slicing problem becomes intractable as the number of MVNOs and resources increases [13]. Thus, since the MVNO user load is dynamic in nature, the centralized approach may fail to provide slices for the MVNOs before their user load changes again and a different slice is thus needed.
In this paper, we take a different approach and tackle the problem in a distributed way. Specifically, we design distributed slicing algorithms such that each MVNO computes its slice without revealing information to the TO or other MVNOs. Although such distributed solution is necessarily sub-optimal, we show that it is low-complexity (i.e., scalable) and approximates the optimum solution by a factor of 3 /2, a very small number. We use the framework of congestion games [14][15][16]  will nevertheless reach a solution (i.e., Nash equilibrium) that will satisfy each MVNO. In order to increase the TO's profit, we propose an adaptive resource pricing algorithm. Fig. 2 provides a roadmap of the following analytical sections.

III. RAN SLICING PROBLEM FORMULATION
Let us define M and C as the sets of the MVNOs and RAN clusters, respectively. We assume that a set R c of R heterogeneous RRHs are deployed for each cluster c ∈ C, and that RRHs can be classified into L classes according to their performance and resource availability (e.g., macro, micro, pico and femto cells). Accordingly, the set of RRHs in RAN cluster . For each RRH r ∈ R c , we also assume that the TO fixes a leasing price, here denoted as p r .
It is reasonable to assume that statistical information on the expected number of MUs and their position in each cluster may be obtained by exploiting real-time monitoring of the RAN [19]. Given such statistics are time-varying and depend on MUs mobility patterns, we assume that MVNOs change their slicing policy on regular basis. For these reasons, we assume time is discretized into slots, where t = 1, 2, . . . represents the slot index, and the number of MUs and their position in each cluster is assumed to vary at each slot.
Let Λ r be the maximum amount of resources of RRH r available at each slot 1 , and let N r denote the number of MUs that can be served by RRH r without any degradation in QoE. In other words, if the number of MUs served by RRH r is lower than N r , then all MUs connected to r enjoy high-quality communication. On the other hand, MUs would experience congestion and/or poor performance if their number is equal or greater than N r .
The N r parameter is specific to a given RRH and depends on Λ r , the desired minimum QoE level, the position of MUs and their number at a given slot. As an example, it is easy to observe that communication between distant RRHs and MUs is expected to result in more collisions and errors, which necessarily increases the number of re-transmissions and the transmission power. In general, the value of N r can be either fixed by hardware [22] or estimated by the TO by analyzing statistical information collected by using historical data such as transmission patterns and activities of MUs. For the sake of completeness, in the following we propose a methodology to estimate the value of N r that accounts for QoE requirements, resource availability, position and number of MUs. For the sake of simplicity, henceforth we will focus on a given cluster c ∈ C, and we will omit both c and the slot index t. We summarize the most relevant system parameters in Table I.

A. Derivation of N r
Let us consider an MU communicating with RRH r. The received power at the MU's side can be denoted as follows: where k is a constant that accounts for transceiver design parameters such as antenna gains, channel characteristics, transmission power of the RRH and operating frequency; d 0 is a reference distance for far-field communication; d r is the distance between the MU and r; and α is the path loss coefficient [23]. Specifically, α = 1 corresponds to the linear path loss model, α ≤ 2 models the free space or indoor path loss, and α > 3 models urban and sub-urban scenarios. Let us assume that the the RRH r serves all MUs in its range with the same transmission power level. Accordingly, the Signal-to-Interference-plus-Noise Ratio (SINR) measured by each MU at distance d r from r can be written as where N is the channel noise power, p r is defined in (1), and N r represents the expected number of interfering MUs in the RRH coverage range [23]. Given that RRH r can not allocate more than Λ r resources, the RRH may be modeled as an M/M/1 queue system with serving rate of Λ r . To avoid queue starvation and enjoy the minimum SINR in (2), it follows that the arrival rate of MUs must not exceed Λ r . In other words, N r should satisfy N r ≤ Λ r . Let µ ∈ [0, 1] such that µ·N r is the rate at which MUs request to access the available resources. By applying queuing theory [24], the expected number of the MUs in the system is derived µ ·N r Λ r −µN r , while the expected number of interfering MUs in the RRH coverage rangeÑ r is derived as By substituting (1) and (3) in (2), we obtain the maximum number N r of MUs that can be served simultaneously by r while satisfying the minimum SINR constraint in (2) as follows: where p r is a function of the distance between MUs and r and is defined in (1). Remark 1. From (4), we notice that (i) the maximum number of users that can be served by RRH r is proportional to the available network resources Λ r and decreases as µ increases; and that (ii) N r decreases as the minimum SINR level and the distance d r increase. Furthermore, the variable µ can be varied at each slicing slot and be used to model the time-varying nature of cellular traffic at different part of the day. In Section VIII we show the impact of µ on different performance metrics such as the congestion level of the RRHs.
The above discussion provides an estimation of N r when MUs are located at a fixed distance d r from r. However, in real networks MUs are expected to change their position within the cluster continuously. Thus, statistical information on the MUs' mobility distribution can be used to provide a more accurate estimation of N r . Specifically, we model the distance between MUs and RRH r as a continuous random variable with probability density function f D r (d) and N r in (4) can be rewritten as a function of d r , i.e., N r → N r (d r ). Accordingly, the expected maximum number of MUs that can be served by RRH r can be computed as The value of N r depends on the distribution f D r (d) of MUs in the cluster, and might be considerably different if different values of µ, SINR r , N, Λ r are considered. Also, since RRHs are located at different positions of the network, the function f D r (d) is expected to vary across different RRHs.

B. Definition of Slicing Policy
We define as slicing policy a function determining how each MVNO allocates its MUs to the available RRHs in a given RAN cluster. More formally, a slicing policy for an MVNO m is an allocation vector ξ m = (ξ m,r ) r ∈R ∈ [0, n m ], where ξ m,r represents the number of MUs in the cluster that the MVNO m expects to serve through RRH r.
Ultimately, the TO generates the global allocation policy ξ = (ξ m ) m∈M by considering all the allocation vectors for each cluster. For any given allocation policy ξ, the TO generates a corresponding network slice over the available RRHs. Specifically, the amount of resources at RRH r ∈ R provided to MVNO m under allocation policy ξ is: where Λ r is the maximum amount of resources of RRH r, and s(·) is the slicing function. For example, a simple (yet effective), slicing function can be provided by the proportional allocation function [25] σ m,r = ξ m,r l ∈M ξ l,r Λ r . Leasing price for RRH r ∈ R t = 1, 2, . . .
Slicing slot index n m, c (t) Expected number of MUs in cluster c for MVNOs m at slot t ξ m, r (t) Allocation policy at slot t Λ r Amount of resources available at RRH r σ m, r (ξ) Available resources allocated to MVNO m under allocation policy ξ φ r (ξ) Congestion level on RRH r ∈ R under allocation policy ξ π P m Weighing parameter for MVNO m Cost function for MVNO m under allocation policy ξ G RAN slicing congestion game Φ(ξ) Potential function for the game G under allocation policy ξ ξ OPT , ξ NE Optimal and Nash Equilibrium allocation policies C NE , C OPT Social welfares computed under the NE and optimal allocation policies γ n Step-size parameter used in the learning procedure in (25)

Π(t)
Profit ot the TO at slot t Since Λ r is a positive and finite real number, the relationship m∈M σ m,r ≤ Λ r always holds for each r ∈ R. For any ξ, a slicing rule σ r = (σ m,r ) m∈M for each RRH r ∈ R is derived, and a slicing policy σ = (σ r ) r ∈R is obtained. For the sake of simplicity, we also define Γ m (ξ m ) as the set of RRHs in R selected by MVNO m in its slice, and Θ r (ξ) as the set of MVNOs which have selected RRH r under slicing policy ξ. More formally, Γ m (ξ m ) = {r ∈ R : ξ m,r > 0, ξ m,r ∈ ξ m } and Θ r (ξ) = {m ∈ M : ξ m,r > 0, ξ m,r ∈ ξ }.

IV. RAN SLICING AS A CONGESTION GAME
When designing optimum slicing policies, MVNOs must also take into account aspects such as (i) the cost incurred when leasing RRHs; and (ii) QoS-related metrics such as (a) the distance of those RRHs from the MUs, (b) the congestion level on each RRH, and (c) the availability of resources at each RRH. Since MVNOs are assumed as selfish and interested in reaching their own optimum slicing policy, and given the RAN infrastructure is shared among MVNOs, slicing policies belonging to the same cluster will necessarily affect each other.
For these reasons, congestion games (CGs) [14][15][16] become the most natural choice to design and analyze efficient and distributed RAN slicing algorithms. Indeed, by using the theory of CGs, we are able to (i) demonstrate the existence and uniqueness of the Nash equilibrium (NE) associated to the CG; (ii) prove that its Price of Anarchy (PoA) is limited to 3 /2; and (iii) formulate two privacy-preserving distributed algorithms that provably converge to the unique NE.
We now formulate the RAN slicing problem as a congestion game and we define the slicing cost function used by MVNOs to select their optimum policy.

A. Congestion Game Problem Formulation
Let us define and consider the following weighted congestion game (CG) where M is the player set (i.e., the set of MVNOs), n m are the weights of the congestion game and represent the expected number of MUs in the cluster for MVNO m, R is the resource set, S = m∈M S m,c is the strategy space, and (c m ) m∈M is the cost function set, where c m will be defined in Section IV-B. A strategy for MVNO m consists in the selection of the allocation vector ξ m . Hence, a strategy profile is represented by Since the cost experienced by each MVNO depends on the RRHs they select, the congestion game G has to be weighted and to have player-specific cost functions. Furthermore, a slicing policy is derived by allocating different number of MUs to multiple RRHs in the cluster, implying that G has to be a CG with splittable flows [26]. To summarize, the slicing problem can be modeled as an atomic weighted CG with splittable flows on R parallel links. Figure 3 shows a CG with two MVNOs. In this example, five RRHs are divided into two distinct RRH classes R (1) and R (2) . Finally, ξ m,r represents the number of MUs allocated to RRHs m by MVNO m.

B. Definition of Slicing Cost Function
RRHs are heterogeneous in terms of type, position and available resources (i.e., spectrum and computational power). Thus, when selecting an RRH r, an MVNO m will incur in a cost that depends on the following two aspects: 1) RRH Congestion. RRHs serving an excessive amount of MUs are expected to provide low QoS to their MUs. Instead, RRHs that serve fewer MUs might provide their served MUs with better quality communication. Therefore the RRH congestion should be taken into account.
The congestion level on RRH r under policy ξ can be measured as follows: where N r has been defined in Section III-A and depends on several RRH-specific parameters such as the resource availability Λ r at RRH r and the quality of the wireless channel. It is worth noting that the congestion cost not only depends on the allocation policy ξ m of MVNO m, but it also depends on other MVNOs' allocation policies. 2) Deployment Cost. A second cost term is the deployment cost which MVNO m pays to the TO to add RRH r to its slice. Such cost depends on the price p r associated to RRH r. It models the revenue that the TO expects to receive when renting resources to MVNOs. The above two aspects can be considered by defining the following resource-and MVNO-specific cost function where the weight π P m is a resource-and MVNO-specific parameter that weighs the two terms in (10). π P m can be used to model a wide variety of network scenarios. For example, π P m = 0 can be used to model a MVNO m that cares about congestion only irrespective of the incurred deployment monetary cost.
The total cost incurred by MVNO m under allocation policy ξ can be expressed as where In the expressions above, (13) measures the overall congestion level experienced by all MUs served by the MVNO m under the slicing policy ξ = (ξ m , ξ −m ); and (14) represents the total monetary deployment cost of the requested slice.

V. NASH EQUILIBRIUM ANALYSIS
In the previous section, we showed how the slicing problem can be modeled as a congestion game G. In this section, we solve G by computing the Nash Equilibrium (NE) of the game, defined as follows: Thus, a NE is a strategy profile such that no MVNO can further reduce its own cost function by unilaterally switching to another strategy.
In the following, we will focus our efforts to address the next four questions: 1) Does game G admit one or more NEs? 2) Is the NE efficient with respect to the optimal solution? 3) Can we design an efficient distributed algorithm that will help the MVNOs reach the NE without interacting with each other?
Question 1) will be answered in Section V-A, while questions 2) and 3) will be answered in Sections V-B and VI, respectively.

A. Existence and Uniqueness of the NE
We first introduce the concept of exact potential games in Definition 2, and then we show that game G is an exact potential game in Proposition 3.
For each MVNO m ∈ M and RRH r ∈ R, let η m,r be defined as follows: Proposition 3 (Potential Function and NE Uniqueness). The congestion game G is an exact potential game with potential function (16) Furthermore, the congestion game G admits a unique NE.
For a detailed proof see Appendix A.

B. The Price of Anarchy (PoA)
In this section, we investigate the efficiency of the unique NE of the CG. Specifically, we will demonstrate that the Price of Anarchy (PoA) of the game is a small number. In particular, the PoA is a metric which measures the efficiency of the NE w.r.t. a social optimum solution, where the latter is computed as follows: In our considered case, let ξ NE be the unique NE of G, the PoA can be expressed as Since each MVNO aims at minimizing its cost function, it holds that PoA where v m,r is the first-order partial derivative of ξ m,r c m,r in (10), and is defined as Proposition 4. The relationship C NE ≤ 1 1−β C OPT holds, i.e., PoA ≤ 1 1−β . Please refer to Appendix B for the complete proof. For the detailed proof see Appendix C. It is worth noting that the result in Theorem 5 matches the result in [28], where it has been shown that the PoA for atomic splittable congestion games is bounded by 3M+1 2M+2 . However, their result applies to cost functions which are only resourcespecific, i.e., c m,r = c r for all m ∈ M. In Theorem 5, instead, we consider cost functions such as those in (10) which are both player and resource-specific, thus extending the results in [28].

VI. DISTRIBUTED ALGORITHMS FOR COMPUTING NASH EQUILIBRIUM
In this section, we propose two algorithms that provably converge to the unique NE of game G. Specifically, in Section VI-1 we develop a best response approach to develop a mechanism that computes a NE by solving a convex quadratic programming (QP) problem. Section VI-2 will be devoted to the design of a learning mechanism which provably converges towards a NE and further reduces the complexity of the NE computation.
1) Best Response approach: We introduce the concept of best response (BR) functions and then prove that algorithms based on BR converge towards the unique NE.
The BR is a function that minimizes the cost of each player m given the strategies ξ −m of the other players. Specifically, the BR for player m is defined as An iterative algorithm where each player updates its current strategy according to (21) is called a best response dynamics (BRD). The following Proposition 6 holds.
Proposition 6. The sequential BRD converges towards the unique NE of G. Furthermore, the BR of each MVNO m ∈ M is unique.
Proof: Since G admits a potential function, from (16) we have that any BR that minimizes the cost function of a given player also reduces the value of the potential Φ. Therefore, since the potential is bounded and always non-negative, the sequential BRD is an improvement path [29] and will surely converge towards the unique NE. Finally, let us note that the cost functions in (11) are strictly convex in each player's strategy ξ m . Thus, the BR of each MVNO is unique.
Note that Proposition 6 does not guarantee that the convergence towards the unique NE is attained in a finite number of iterations. However, potential games with continuous strategy space possess the approximate finite improvement path (A-FIP) property, which ensures the convergence to an approximate NE in a finite amount of iterations. Even though we cannot guarantee the convergence in finite time to the NE, in Section VIII we will show that such convergence is attained in a limited number of iterations in many practical scenarios.
Proposition 6 shows that it is possible to converge towards the NE through iterative BRs. The BR in (21) for any MVNO m and any adversarial strategy profile ξ −m is obtained by solving and φ r (ξ) and η m,r being defined in (9) and (15), respectively. An algorithmic implementation of the sequential BRD is described in Algorithm 1. 2) A low-complexity learning approach: In the previous section, we have shown that the BR of each MVNO can be computed by solving a QP problem, which is generally solved in polynomial time ≈ O(R 3 ). However, if the number R of RRHs is large, to compute a solution to Problem (22) would anyway require a non-negligible amount of time. Motivated by this latter discussion, in this section we provide another approach that builds on learning theory to provide a lowcomplexity approach to compute the unique NE of G.

Algorithm 1 Sequential BRD
Let us introduce the following exponential learning scheme where γ n is the step-size, v m,r is defined in (20) and n is the iteration indicator. Intuitively, the exponential map in (24) generates values of the allocation variable ξ m,r which always lie on the boundary of the (R − 1)−simplex S m . In Proposition 7, we show that (24) converges to the unique NE of G.
Proposition 7. Let ξ * ∈ S be the unique NE of G. If the stepsize γ n are chosen such that +∞ n=1 γ 2 n < +∞ n=1 γ n = +∞, the exponential learning scheme in (24) always converges towards ξ * from any starting point ξ(0) ∈ S. A suitable choice of γ n is γ n = 1 n β , with β ∈ (0.5, 1]. Proof: Let us first derive the continuous time version of (24) as follows: From the strict convexity of c m , it follows that v m,r is continuously differentiable, and thus Lipschitz-continuous. Since v m,r is always bounded, (25) admits a unique solution for any initial condition ξ(0). From (16), we have that the potential function Φ is strictly convex, which implies that Φ is also star-convex with respect to the unique NE ξ * . Accordingly, the theory of [30] ensures that the unique solution of (25) also corresponds to the unique NE ξ * , and (24) converges to ξ * if +∞ n=1 γ 2 n < +∞ and +∞ n=1 γ n = +∞. Finally, we have that γ n = 1 t β satisfies the above conditions.
The algorithmic implementation of (24) is described in Algorithm 2.

Algorithm 2 Exponential Learning Scheme
while Convergence is not achieved do for each m ∈ M do simultaneously ξ m,r ← n m e zm, r k ∈R e z m, k ; z m,r ← z m,r − γ n v m,r (ξ); end for end while As already discussed at the end of Section VI-1, Algorithm 2 can be implemented in a distributed fashion by only making the congestion level φ r (ξ) on each RRH publicly available. Furthermore, in opposition to the BR-based mechanism in Section VI-1, lines 5, 6 in Algorithm 2 have complexity O(1). Since both ξ m,r and z m,r have to be computed for each RRH in R and MVNO in M, the overall per-iteration computational complexity is O(RM), i.e., each iteration of Algorithm 2 can be computed in linear time.
In Proposition 7, we have shown that the learning scheme in (24), and thus Algorithm 2, converges to the unique NE of the game if some conditions on the step-size γ n are satisfied. As an example, a suitable choice of the step-size is γ n = 1 n β . Though this latter setting guarantees the convergence of the learning scheme, it might generate slow-convergent dynamics. To overcome this issue, it has been shown in [31] that the convergence process can be improved by using fixed values of the step-size. Although the convergence for this latter approach cannot be theoretically proven, using a fixed step-size still allows Algorithm 2 to converge to the NE with high probability. Accordingly, in this paper we will only consider fixed step-size rules, and we refer the interested readers to [31] for a more detailed discussion on the impact of different step-size rules on the convergence of the exponential learning scheme (24).

VII. PRICING POLICIES
In the previous sections, we have shown that the developed algorithm does not require perfect knowledge with respect to MVNOs' parameters, and effectively preserves the privacy of all MVNOs. In addition, although the proposed algorithm has limited complexity, we have proven that close-to-optimal solutions can be obtained with no need to run complex and time-consuming centralized approaches at the TO side. Despite the above important properties, another relevant issue that has not yet been considered is related to pricing policies enforced by the TO and their impact on the achievable profit.
It is worth noting that the set of MVNOs, the availability of RRHs and the position and number of MUs in each cluster vary at each slot t. In such a dynamic scenario, it is straightforward to show that static pricing policies could fail to provide high profit to the TO. On the contrary, adaptive pricing policies are more suited to deal with time-varying systems such as the one we are considering in this paper. For this reason, in this section we focus on adaptive pricing policies, and we propose a stochasticbased algorithm that exploits past observations to adapt the pricing policy at future slots.
Let us focus on a given cluster c. Furthermore, let ξ * (t) = (ξ * m,r (t)) m∈M,r ∈R be the unique NE of G at slot t, and let n r (t) be the number of MUs served through RRH r at the NE. We have that The profit of the TO is defined as where C(n r (t)) is the cost experienced by the TO to manage n r (t) MUs at RRH r. The allocation variables ξ * m,r are obtained by iteratively executing either Algorithm 1 or Algorithm 2. Unfortunately, there is no closed-form for those variables, which makes it hard to predict the behavior of the MVNOs, and the actual allocation of the MUs. Also, ξ * m,r depends on the weighting parameters π P m . Those values are not known by the TO and might vary at each slot t. Therefore, an adaptive pricing policy should be considered such that the price p r can be updated at each slot t.
In this paper, we propose the following stochastic-based approximation pricing mechanism where σ > 0 is a fixed step-size used to weigh the two terms in the stochastic procedure. The proposed pricing scheme in (28) works as follows. If n r (t) > n r (t − 1), i.e., the number n r of MUs served through RRH r has been increased in the last slot, then the price at the next slot is increased as well, i.e., p r (t + 1) > p r (t). Otherwise, if n r (t) < n r (t − 1), the price is decreased, and p r (t + 1) < p r (t). Furthermore, since the achieved profit must always be nonnegative, the condition p r (t + 1) ≥ C(n r (t)) has to be satisfied for each RRH r. Since the stochastic procedure in (28) might generate a price p r (t + 1) that violates the above constraint, a minimum value p r (t + 1) = C(n r (t)) is considered at each iteration of (28).

VIII. PERFORMANCE EVALUATION
In this section, we investigate on the performance of the proposed congestion game-based slicing mechanism through numerical simulation and experimental results. To emulate a realistic network setup, in our simulations we have extracted a cluster R (FULL) of multiple RRHs deployed in Boston, MA (USA) from the OpenCellID database [32]. A cluster consisting of 100 RRHs, and the position of each RRH is illustrated in Fig. 4. We assume that the density of wireless devices in the considered cluster equals the population density in Boston and is set to 5000 devices/km 2 [33]. Furthermore, we consider the case where a set M of M = 20 MVNOs are willing to competitively deploy RAN slices to provide MUs with wireless access to the internet. We assume that each MVNO m serves the same number n m of devices. Hence, the density of wireless devices served by each MVNO is 5000/M devices/km 2 .
We assume that all RRHs are LTE base stations operating at 2.4GHz. The path-loss exponent in (1) is set to α = 3, e.g., urban scenario, and the channel noise power is N = −174dBm/Hz [31]. We consider isotropic antennas with antenna gain equal to 3dBi and a reference distance d 0 = 1m [34]. Thus, the k parameter in (1) is k = 9.89 · 10 −5 [23].
We assume that the amount of available resources at each RRH r, i.e., Λ r , is represented by the number of LTE Resource Elements (RE) within an LTE Resource Block (RB). Specifically, we assume that each RB consists of s r = 7 OFDM symbols transmitted over c r = 12 subcarriers for all r ∈ R. Note that the number of available RBs, and thus Λ r depends on the LTE channel bandwidth. Specifically, we have that Λ r = N RB · s r · c r , where N RB ∈ {25, 50, 100} represents the number of available RBs in the LTE system when the bandwidth is set to 5, 10, and 20 MHz, respectively. Unless otherwise stated, we assume b = 20MHz. That is, Λ r = 100 REs are available for MU transmission at each RRH. Furthermore, to investigate the impact of different minimum Quality of Experience (QoE) levels on the performance of the slicing mechanism, in our simulations we consider three different minimum SINR requirements such that SINR r ∈ {−5, 0, 5} dB.
The price p r associated to each RRH r ∈ R (FULL) is assumed to be generated according to a normal distribution with mean value µ p = 10 Price Units (PU) and standard deviation σ p = 4 PU. Instead, the weight π P m in (10) and the access rate µ of MUs in (4) are assumed to be uniformly distributed and are randomly generated at each simulation run. More in detail, π P m takes value in [0, π P ], with π P = 5 · 10 −4 , while µ ∈ [0, 1].
To investigate the impact of the number R of RRHs deployed in the network on the achievable performance of the network, for any given R ∈ Z, in our simulations we generate a subset R ⊆ R (FULL) of R RRHs which are randomly picked from R (FULL) . The results presented in the following are averaged over 2000 independent simulation runs. The 95% confidence intervals are not shown when below 2% of the average.

A. PoA and Convergence Speed Analysis
We first investigate the performance of the proposed RAN slicing algorithms as compared to an algorithm computing the social optimum as discussed in Section V-B. In Fig. 5    Step-size, t   Furthermore, Fig. 5 shows that the proposed solution achieves better performance in terms of optimality gap when a small number of RBs is considered. Fig. 6 shows the impact of the weighing parameter π P m on the cost function (11) of the PoA. The weight π P m is uniformly distributed in [0, π P ]. Accordingly, in Fig. 6 we let the upperbound π P vary for different values of the minimum SINR requirement. Fig. 6 clearly shows the existence of two distinct regions;the first region is associated to small values of π P , i.e., those network scenarios where MVNOs primarily aim at minimizing the congestion cost in (11). In this case, the PoA increases until a maximum value is attained. Instead, when higher values of π P are considered, i.e., the deployment cost associated to each slice is no more negligible, the PoA asymptotically decreases to one until near-optimality is achieved. Fig. 7 compares the execution time of the solution proposed in this paper. Specifically, we compare the time needed by a centralized algorithm to compute an optimal solution, and that needed by Algorithms 1 and 2 to compute a NE. The results conclude that the centralized algorithm (dotted lines) suffers from severe complexity issues when dense networks are considered. On the contrary, both the BRD (dashed lines) and learning (solid) algorithms show faster convergence rate. Furthermore, Algorithm 1 still requires to solve the QP problem (22), which usually has polynomial computational complexity. Instead, Algorithm 2 has linear per-iteration and per-user complexity, which results in faster convergence towards the NE.
To investigate the convergence speed of Algorithm 2 under the fixed step-size rule, in Fig. 8 is shown the number of iterations needed by the learning algorithm to converge to the NE as a function of the value of the step-size parameter for different minimum SINR requirements and values of the number R of RRHs. It is worth noting that the higher the value of the step-size, the higher the convergence speed of the algorithm. Furthermore, the convergence of Algorithm 2 is slowed down when the number R of RRHs is large. However, by increasing the value of the fixed step-size, the convergence speed is reduced even in those scenarios where the number of RRHs and MVNOs is high. Fig. 9 shows the impact of the ratio R/M on both the average congestion and the deployment cost of the network for different values of the number of RBs and the minimum SINR requirement when µ = 0.8 and π P = 5 · 10 − 2. Specifically, the congestion at each RRH is evaluated as in (9). Instead, the deployment cost of each MVNO m ∈ M is computed according to (14) and then normalized by the corresponding weight π P m to obtain the actual monetary cost. The figure concludes that the congestion is decreasing as a function of R/M. Intuitively, this is because the deployment of additional RRHs on the network allows the MVNOs to generate RAN slices which contain different RRHs, thus inevitably reducing the congestion level on those RRHs. Furthermore, it is shown that the deployment cost decreases as well when a larger number of RRHs are deployed. In this case, MVNOs can select those RRHs with a low price p r , thus reducing the overall monetary expenditure. Fig. 9 also shows that when SINR = 5dB (dashed lines), both the congestion level and the deployment cost of the network are higher as compared to the case where SINR = −5dB (solid lines). In other words, higher values of the minimum SINR requirements reduce the maximum number of MUs that can be served by each RRH, which, on average, leads to higher values of congestion and deployment cost.

B. Congestion and Deployment Costs Analysis
From (4), the number N r of MUs that can be served with high QoE by each RRH decreases as the access rate µ of MUs increases. As a consequence, the congestion on each RRH increases due to the high traffic demand generated by MUs. This phenomenon is depicted in Fig. 10 where we show the average congestion level on each RRH and deployment cost of a slice as a function of the access rate µ for different values of the minimum SINR requirement and R. Intuitively, the congestion increases when both µ and the minimum SINR level are high, and a small number of RRHs is deployed. Accordingly, to support the high traffic demand, MVNOs add more RRHs to their slice, which increases the deployment cost of each slice.
The impact of π P m on the congestion level of the sliced network is investigated in Fig. 11, where we show the average congestion level and deployment cost as a function of π P for different values of the minimum SINR requirement and number of RRHs when µ = 0.8. The lowest values of congestion are achieved when π P = 0. In this case, from (11) we have that the proposed solution computes a NE that individually minimizes the congestion level on each slice. Accordingly, such a setting produces low congested slices. On the contrary, the average congestion increases when π P increase as well. As expected, the average congestion when only few RRHs are available (i.e., dotted lines) is higher than the case where a high number R of RRHs is deployed on the network (i.e., dashed lines). Fig. 11 also shows that the deployment cost of the slices decreases as π P increases. Such a result stems from the fact that, by increasing the weight parameter, MVNOs are more affected by deployment costs and converge towards more conservative slicing strategies to avoid high monetary expenses.

C. Profit Analysis
In this section, we investigate the profit achieved by the TO and we compare different pricing policies. Specifically, we consider three different pricing schemes as follows: • Uniform Pricing: all the RRHs in R are equally priced, i.e., a fixed price equal to p r = µ p is enforced on each RRH r ∈ R; • Weighted Pricing: the price enforced on each RRH is proportional to N r . Specifically, the price p r for the RRH r ∈ R is set to p r = µ p N r max e∈R N e . Under this pricing policy, the TO fixes higher prices to those RRHs which can serve a higher number N r of devices simultaneously; • Adaptive Pricing: this policy has been introduced and discussed in Section VII. Intuitively, at each slot t, the price of RRH r is updated according to (28) by considering the congestion level on r at slot t − 1. From (28), it can be shown that the adaptive scheme will eventually converge towards a stable pricing policy when t → ∞. The profit achieved by the TO is shown in Fig. 12 as a function of the mean value µ p for different pricing schemes. Since the proposed adaptive pricing model updates the price of the RRHs at each slicing slot t, in Fig. 12 we show the profit achieved by the TO when t → ∞. As expected, the profit achieved by the TO increases when the value of µ p increases as well, and it is shown that the proposed pricing model outperforms the other mechanisms.

D. Experimental Results
To understand the impact of our system in real-world deployments, Fig. 13 shows the experimental results obtained by executing the learning algorithm on a testbed deployed on the Amazon Elastic Computing (EC2) cloud service. Specifically, we have deployed the TO's code on a t2.micro instance, having 1 virtual CPU, one 1 GByte of RAM with 3.3GHz clock speed. We have deployed the code implementing the MVNO's slicing policy learning algorithm on an iMac desktop computer located on Northeastern University campus. As we can see from      Fig. 14 shows the average congestion level on each RRH in the network at each iteration of Algorithm 2. It is worth noting that Algorithm 2 quickly adapts to network changes and rapidly converges towards a NE in few iterations even though the network configuration changes over time.

IX. RELATED WORK
Due to its capability to enable agile and efficient sharing of wireless network resources in 5G systems, the network slicing problem has attracted increasing attention in the literature [10,13,[35][36][37]. Network slicing is not trivial, and it can be shown that in general it is NP-hard [10]. Centralized solutions have been proposed for both the slicing of both the backbone and RAN portions of the network [10,13,38,39], but they generally require perfect knowledge of the network configuration and suffers from high complexity issues. As a consequence, a variety of low-complexity heuristic and distributed approaches have been proposed [40][41][42]. However, the above solutions do not consider the adversarial behavior of virtual operators, which makes it hard to implement them in competitive scenarios where privacy must be preserved among multiple entities.
It is worth noting that many instances of the network slicing problem can actually be reduced to the so-called Virtual Network Embedding (VNE) problem [43], which consists in the problem of generating a set of virtual networks upon a shared physical infrastructure while satisfying a given set of constraints. Unfortunately, the VNE problem is NP-hard. Thus, to design effective algorithms with low computational complexity, a variety of centralized and distributed heuristic approaches have been proposed in the literature [43]. However, all of those solutions are not well-suited to deal with the competitive slicing of the RAN, where information on the expected number of users and their distribution in the network is available. Thus, they cannot be straightforwardly applied to the RAN slicing problem we are tackling in this paper.
Competition among virtual operators has been recently considered in [25], where game-theoretical tools have been effectively exploited to address the RAN slicing problem. In [25], a RAN slicing game is developed, where the available RAN resources are allocated to the MUs through an auction-based mechanism which competitively maximizes the data rate of each slice while guaranteeing a certain level of fairness.
Though the problem tackled in [25] is similar to that addressed in this paper, there are several fundamental differences. First, in [25] a fixed share of RAN resources is assigned to each MVNO a-priori, and the auction game is then played by the MVNOs to decide on how to divide those resources to the mobile users. In our paper, conversely, the share of RAN resources allocated to each MVNO has been obtained as a consequence of a non-cooperative game played among the competing MVNOs. Another important difference is that perfect knowledge about the presence of users is assumed in [25]. In our paper, instead, we have relaxed this assumption by assuming that only statistical information on the presence and position of the users is available.
In the previous sections, we have emphasized the importance of deriving theoretical bounds on the efficiency of the NE, and designing effective distributed and convergent algorithms. Due to their interesting properties with respect to the above issues, congestion games [16], and their application to many networking problems such as the network service chaining [15] and load balancing [44], have been investigated in the literature [14,26,28,[45][46][47].
In this paper, we have leveraged on a particular class of congestion games, i.e., the atomic splittable congestion games. Although the uniqueness of the NE for this class of games is a well-known result in the literature, how to efficiently compute a NE is still a challenging issue. Closed-form solutions have been derived in [45], which however only hold for resourcespecific cost functions. When closed-form solutions cannot be derived, then traditional sequential BRD have been considered [46]. However, those approaches generally require to solve QP problems, and are guaranteed to converge to the unique NE only after an infinite number of iterations. Recently, a quantization approach which can compute the NE in a finite amount of time has been proposed in [26]. However, it suffers from highly polynomial complexity, which makes it hard to implement it in dynamic scenarios. Upper-bounds on the PoA of atomic congestion games have been investigated in [28] and [47], but they only apply to the case of resource-specific cost functions.
If compared to the above literature on atomic congestion games, in this work we have proposed a simple low-complexity learning algorithm where each MVNO iteratively updates its strategy to provably converge to the unique NE. We have further derived an upper-bound on the PoA of the class of atomic splittable congestion games where resource and player-specific cost functions are considered, thus extending the results in [28] and [47]. Specifically, we have proved that the PoA for this particular class of cost functions matches the PoA of atomic splittable congestion games where only resource-specific cost functions are considered [28].

X. CONCLUSIONS
In this paper, we have leveraged congestion games and learning mechanisms to design a distributed solution to the wireless network slicing problem. The proposed solution accounts for the limited availability of wireless resources and considers several aspects such as congestion, deployment costs and distance among the RRHs and MUs. We have shown that the proposed solution achieves near-optimal global performance with limited computational complexity while preserving the privacy of MVNOs. Numerical and experimental results have shown the effectiveness of the proposed approach in terms of cost reduction, scalability and convergence time.

A. Proof of Proposition 3 (Potential Function and NE Uniqueness)
Proof: The cost functions in (11) are strictly convex in each player's strategy ξ m . Thus, the general theory of [48] on concave games ensures the existence of at least one NE.
Let us consider the j-th MVNO in M, and consider two allocation profiles (ξ j , ξ −j ) and (ν j , ν −j ) such that ξ −j = ν −j and ξ j ν j . Since ξ −j = ν −j , we have Φ(ξ j , ξ −j )−Φ(ν j , ξ −j ) = r ∈R 1 N r (ξ 2 j,r − ν 2 j,r )+η j,r (ξ j,r − ν j,r ) + r ∈R m∈M Since ξ −j = ν −j by assumption, we have that j−1 m=1 ξ m,r k<m ξ k,r = j−1 m=1 ν m,r k<m ν k,r . Thus, the last summation in (29) can be rewritten as follows: where the last step is obtained by exploiting ξ −j = ν −j . By substituting (31) in (29), we obtain: which proves that the function Φ(·) in (16) is an exact potential function for the game G. Note that the Hessian matrix of Φ(ξ) with respect to ξ has strictly positive eigenvalues, which guarantees that the potential function is strictly convex and admits a unique global minimizer. It is worth noting that Φ(ξ) is a potential function for G, and is convex on the convex set S. Hence, the set of minimizers of Φ(ξ) coincides with the set of NEs of G [49]. Since Φ(ξ) admits a unique global minimizer, it must follows that the NE of G is unique.