key: cord-0055561-04eanb8r
authors: Li, Shiyong; Sun, Wei; Liu, Huan
title: Optimal resource allocation for multiclass services in peer-to-peer networks via successive approximation
date: 2021-01-25
journal: Oper Res Int J
DOI: 10.1007/s12351-021-00622-9
sha: c3f23e78e93fe8a20056e87cca01e5710e4b71d6
doc_id: 55561
cord_uid: 04eanb8r

Peer-to-peer (P2P) networks support a wide variety of network services including elastic services such as file-sharing and downloading and inelastic services such as real-time multiparty conferencing. Each peer who acquires a service will receive a certain level of satisfaction if the service is provided with a certain amount of resource. The utility function is used to describe the satisfaction of a peer when acquiring a service. In this paper we consider optimal resource allocation for elastic and inelastic services and formulate a utility maximization model which is an intractable and difficult non-convex optimization problem. In order to resolve it, we apply the successive approximation method and approximate the non-convex problem to a serial of equivalent convex optimization problems. Then we develop a gradient-based resource allocation scheme to achieve the optimal solutions of the approximations. After a serial of approximations, the proposed scheme can finally converge to an optimal solution of the primal utility maximization model for resource allocation which satisfies the Karush–Kuhn–Tucker conditions.

Nowadays, peer-to-peer (P2P) networks have become an important network architecture supporting file sharing and video distribution over the Internet. P2Ps are different from traditional client/server data networks, where the performance mainly depends on a small number of powerful servers. In P2Ps the role of each peer is treated as the same. Each peer can not only serve as a server to provide network services for other peers, but also serve as a client to obtain services from others, thus avoiding the impact of server failure in the traditional networks. They can generate multiple routes between service providers and customers, thus improving the network throughput and routing optimization Wang et al. (2019) . In recent years, many research scholars have carried out studies on P2Ps and applied them into various scenarios, e.g., distributed storage Yan et al. (2017) , edge-cloud computing , multipath industrial networks , and vehicular networks Wang et al. (2018) .

P2Ps can support a wide variety of network services such as file-sharing and video conferencing, e.g., Tencent meeting, Zoom, and are known to cause much network traffic over the Internet through various P2P protocols, e.g., BitTorrent, EDonkey, VoIP. In fact, each peer has a certain level of satisfaction when it requests a network service, which can be described as a form of utility function. Based on the shapes of utility functions, network services can be classified into two categories (Lee et al. 2005; Hande et al. 2007; Li et al. 2015 . One type is the traditional data services, such as file download and upload, which are not very sensitive to the bandwidth requirements. These services are elastic in their bandwidth requirement intervals. Usually a concave utility function is used to describe peer's satisfaction for acquiring an elastic service. The other type is related to delay or bandwidth sensitive multimedia services, such as realtime streaming video service. These services are known as to be inelastic in their bandwidth requirement intervals. They usually have high requirements for bandwidth resource so as to guarantee certain level of QoS. The utility function for an inelastic service is often nonconcave, e.g., sigmoidal or general.

In recent years, many scholars have investigated the resource allocation for both elastic and inelastic services in P2Ps and presented some interesting resource allocation schemes. Firstly, resource allocation for elastic services mainly concentrates on resource pricing strategies, e.g., Eger and Killat (2007a, b) , Kumar et al. (2011) , Koutsopoulos and Iosifidis (2010) , Li and Sun (2016) and . In this type of research, a resource pricing scheme is proposed to balance the resource requests and provisions, thus service providers adjust their bandwidth allocation according to the difference between the prices provided by service requesters and the prices charged by service providers, and finally achieve a weighted fairness among service requesters. Since the utility functions of elastic services are usually concave, then the resource allocation problem for elastic services is a convex optimization problem, which can be solved through the first order Lagrangian method. Besides resource pricing mechanisms, reputationbased methods are also used to encourage cooperation amongst selfish peers so as to promote each peer to provide resource for others and achieve efficient resource allocation, e.g., Satsiou and Tassiulas (2010) , Gupta et al. (2016) and Goswami et al. (2017) .

P2Ps also provide a variety of inelastic services such as VoIP and real-time conferencing (e.g., Tencent meeting), however, the resource allocation problem of inelastic services is much more difficult than that of elastic services because the utility functions of inelastic services are often non-concave. Thus, how to achieve effective resource allocation for inelastic services becomes very important, which is also a crucial challenge and difficult problem. For example, P2P multiparty conferencing applications are considered in Chen et al. (2012) , where a problem of utility maximization for resource allocation is formulated. In order to solve the nonstrictly concave optimization problem, a primal-dual distributed algorithm is presented and proven to converge to the global optimum under the proposed sufficient conditions. Resource allocation for inelastic services are also investigated in Li et al. (2017) , and a heuristic algorithm using particle swarm optimization (PSO) is proposed to solve the difficult nonconvex optimization problem. As for the scenario with both elastic and inelastic services, the utility maximization model for resource allocation is also an intricate and difficult problem.

In this paper we consider resource allocation problem for P2Ps where both elastic and inelastic services are coexisting. We formulate the utility maximization (social welfare) model for resource allocation, i.e., the total satisfaction of all peers in the networks when they acquire these services. However, the utility maximization model is a non-convex problem which is hard to resolve. By applying the successive approximation method, we transform the non-convex problem into an equivalent convex optimization problem and develop a gradient-based resource allocation scheme to achieve the optimal solution of the approximations. After a serial of approximations, the proposed scheme can finally converge to an optimal solution of the primal utility maximization model for resource allocation which also satisfies the Karush-Kuhn-Tucker (KKT) conditions. The rest of this paper is summarized as follows: We review research work on resource allocation for elastic and inelastic service in P2P networks in Sect. 1. Then we introduce the utility maximization model for resource allocation of both elastic and inelastic services and formulate a serial of approximations in Sect. 2. In Sect. 3 we develop a gradient-based resource allocation scheme to converge to the optimum of the primal resource allocation problem. Then we give some numerical examples to illustrate the performance of the proposed scheme in Sect. 4. Finally we conclude this paper in Sect. 5.

Realizing effective resource allocation in P2P networks has become an important research field and received extensive attention in recent years. P2P networks can provide elastic services such as file sharing and downloading. For the resource allocation of this type of services, in order to reduce the "free-riding" due to the peers' selfish nature, many scholars proposed incentive mechanisms to encourage each peer to provide its own upload bandwidth for others, such as resource pricing, reputation-based schemes, and so on. Eger and Killat (2007a) presented a resource pricing scheme to achieve a fair bandwidth allocation among service requesters. They further expanded the scheme to achieve a weighted fairness among service requesters, such that service providers could adjust their service rates and offered prices (Eger and Killat 2007b) . Later, Koutsopoulos and Iosifidis (2010) considered bandwidth allocation in a star topology P2P network where the peer access link to the backbone is the capacity bottleneck. They developed the problem of maximizing total network utility through controlling the bandwidth allocation for download and upload of each peer, respectively. Then Kumar et al. (2011) considered computing resources shared by users in P2Ps and proposed a resource pricing and allocation scheme. Pacifici et al. (2016) considered cache bandwidth allocation for P2P file-sharing networks which is formulated as a Markov decision process, and proposed three approximations to the optimal cache bandwidth allocation policy, so as to minimize inter-ISP traffic. Recently, Li and Sun (2016) and applied the first order Lagrangian method and low-pass filtering scheme to design a novel scheme of resource pricing and allocation. Antal and Vinkó (2016) investigated max-min fair bandwidth allocation in BitTorrent communities and proposed an algorithm to realize max-min fairness bandwidth allocation in multi-swarm P2P content sharing community. considered fair bandwidth allocation of access links in P2P file-sharing networks and developed a coupled network-wide utility maximization model which aims at achieving several kinds of fairness among requesting peers.

Besides resource pricing schemes, reputation-based mechanisms are also used to promote cooperation between selfish peers and achieve reasonable resource allocation for peers. For example, Satsiou and Tassiulas (2010) assumed each peer could earn its reputation analogous to its contributions and presented a reputation-based resource allocation scheme. Later, Gupta et al. (2016) described a reputation-based probabilistic resource allocation mechanism for avoiding free riding in unstructured P2P networks. Kang and Wu (2015) proposed a credit-based incentive mechanism to encourage peers to cooperate with each other in a heterogeneous network consisting of wired and wireless peers. The mechanism can provide differentiated service to peers with different credits through biased resource allocation. Goswami et al. (2017) investigated a reputation-based resource allocation mechanism through two non-cooperative games in P2P networks and proved evolutionary stability of reputation-based resource allocation (Goswami et al. 2018) .

P2P networks can also support inelastic services such as live streaming services. Therefore, to achieve reasonable resource allocation for inelastic services is also very important. Liang et al. (2011) investigated optimal bandwidth sharing in multiswarm multiparty P2P video-conferencing systems. Chen et al. (2012) considered resource allocation for P2P multiparty conferencing applications where quality of service (QoS) guarantee is a crucial challenge, and formulated the resource allocation problem as utility maximization. Liu et al. (2015) considered resource allocation in underprovisioned multioverlay peer-to-peer live video sharing services. They designed various objective functions for the upload bandwidth allocation problem and showed how optimal solutions could be computed using a bipartite flow network. Rohmer et al. (2015) investigated the problem of maximizing the P2P streaming system capacity by effectively alternating between different resource allocation strategies, and combined different, even potentially conflicting, performance objectives when deciding which resource allocation strategy to use for the current time period. Mostafavi and Dehghan (2016) considered bandwidth sharing and allocation in helper-assisted P2P streaming using non-cooperative game theory and double auction, and proposed an algorithm to reach significant performance improvements in terms of utility per selling helpers. They Mostafavi and Dehghan (2017) also considered resource allocation for HD live streaming and proposed a decentralized, stochastic approximation helper selection mechanism which is adaptable to supply and demand pattern of various video channels. Recently, Li et al. (2017) also developed a utility maximization model for resource allocation of P2P inelastic services. In order to resolve the intrinsically difficult nonconvex optimization, they presented a heuristic algorithm using PSO to achieve the optimal resource allocation.

In this paper we consider resource allocation for multiclass services and introduce a utility maximization model for resource allocation, which is also a non-convex optimization problem. We apply successive approximation method to resolve the non-convex optimization, and approximate the primal problem into an equivalent convex optimization problem. The approximate approach is very useful in dealing with intricate difficult optimization problems (Rismanchian and Lee 2018) . The successive approximation method is first introduced in Marks and Wright (1978) . It has been applied into power control problems (Tran and Hong 2010; Vo et al. 2011) , wireless random access problem (Vo et al. 2012) , bandwidth allocation problems in single-path networks (Vo et al. 2013 ) and multipath networks (Vo et al. 2014) , and cloud resource allocation problem for enterprise applications migration . This method is generally composed of two parts: inner-iterations and outer-iterations, and requires inner-iterations to converge to the optimum of the approximation problem. We prove the convergence of the resource allocation scheme derived from successive approximation method within a certain number of inner-iterations and illustrate the performance with some numerical examples.

P2P networks support a wide variety of network services. Each peer who acquires a service will receive a certain level of satisfaction if the service is provided with a certain amount of resource. The utility function derived from economics is found useful to describe the satisfaction of a peer when acquiring a service. According to the different shapes of utility functions, they can be divided into two categories: elastic services and inelastic services (Lee et al. 2005; Hande et al. 2007; Li et al. 2015) . The former one mainly refers to traditional data services such as file uploading and downloading services in P2P file-sharing networks. The utility functions for this type of services are generally concave. The latter one is mainly related to multimedia video and audio services such as P2P multiparty conferencing services and VoIP over P2P networks. This type of services are usually very sensitive to granted resources and the QoS will drop drastically if resources are below a certain threshold. They usually have non-concave utility functions, such as sigmoidal functions. The shapes of utility functions of elastic and inelastic services are generally illustrated in Fig. 1 . We adopt the utility functions proposed for resource allocation of services in IP networks (Lee et al. 2005; Hande et al. 2007; Li et al. 2015) . If a peer acquires an elastic service s, it will have a concave utility as follows and if it acquires an inelastic service r, then it will have a sigmoidal utility as follows where y is the service rate, w is the willing-to-pay of the peer, a and b are parameters of the inelastic service. We find that for inelastic service r, there is a demarcation point y 0 that divides the utility function into a convex part and a concave part, that is, d 2 U r (y)∕dy 2 > 0 if y < y 0 , and d 2 U r (y)∕dy 2 < 0 if y > y 0 .

Consider a P2P network which is composed of a set of peers, a set S of elastic services and a set R of inelastic services. Each peer in the network acquires at least one service, elastic or inelastic. For example, a peer who is downloading files from other peers is also interested in taking part in a P2P multiparty conferencing. On the other hand each peer can also provide one or several services for others. Therefore, each peer acts as both a service customer and a service provider. In P2P networks, each peer uses its access link not only to obtain services from other peers, such as downloading files, but also to provide services for other peers, such as uploading files. Therefore, the upload bandwidth of a peer becomes a rare resource in the network, and other peers will compete for the upload bandwidth so as to obtain services. Therefore, the P2P networks are faced with the problem of how to allocate the peers' upload bandwidth reasonably and effectively among service requesters, which is the main aim of this work.

Let the set P be peers acting as service providers that offer upload bandwidth to requesters. Also define the sets C s and C r of peers acting as service customers that request elastic services and inelastic services, respectively. Introduce x s pc and x r pc as the service rates offered by service provider p for customer c who requests elastic service s and inelastic service r, respectively. Then, each peer c ∈ C s receives a total bandwidth y s c offered by its providers P s (c) when it requests elastic service s, and peer c ∈ C r obtains a total bandwidth y r c offered by its providers P r (c) when it requests inelastic service r. Finally, the total bandwidth allocation of service provider p does not exceed its access link capacity C p .

Then we formulate the resource allocation for multiclass services in P2P networks as the following optimization problem

Here, in the resource allocation problem P1, the objective is to maximize the aggregated utility of obtained bandwidth y s c and y r c over all service customers under the constraints that each service provider offers no more than its own access link capacity. As described by the equality of the resource allocation model, the aggregated bandwidth provision y s c ( y r c ) for elastic service s (inelastic service r) of service customer c is the sum of the rates x s pc ( x r pc ) that its service providers grant. Here, x s min pc ≥ 0 ( x r min pc ≥ 0 ) is the minimal resource requirement of customer c from provider p for elastic service s (inelastic service r). Similarly, x s max pc ( x r max pc ) is the maximal resource requirement of customer c from provider p for elastic service s (inelastic service r). Also, as described by the inequality in the optimization problem above, the bandwidth provision of provider p is constrained by its own upload capacity of access link, i.e. C p .

In this part we give an analysis on the resource allocation problem P1 for multiclass services in P2P networks. Firstly we obtain the Lagrangian

where is the price vector with elements s c and r c , which can be interpreted as the prices per unit bandwidth paid by customer c when acquiring elastic service s and inelastic service r, respectively; is the price vector with element p , which can be thought as the price per unit bandwidth charged by provider p when offering bandwidth allocation for customers; is the service rate matrix with elements x s pc and x r pc for elastic service s and inelastic service r of customer c, respectively; is the rate vector with elements y s c for elastic service s and y r c for inelastic service r of customer c.

We rewrite the Lagrangian (4) as following

We find the first part in (5) is separable in variables y s c and y r c , and the second part is separable in variables x s pc and x r pc . Thus the objective function of the dual problem is described as where (4)

We give an economic interpretation for Eqs. (7)-(10) as follows. In (7), service customer c acquires elastic service s with total bandwidth provision y s c and wants to maximize its own utility U s c (y s c ) . Meanwhile, it needs to pay a fee for its obtained bandwidth to support the elastic service. Recall that s c is the price per unit bandwidth paid by customer c for service s, then s c y s c is regarded as the total fee paid by customer c. Therefore, the economic meaning of (7) is that each peer as service customer aims at achieving the objective of maximizing its own profit. The interpretation for (8) is similar to that of (7). As for (9), p is considered as the price per unit bandwidth charged by service provider p. The product x s pc s c is the fee paid by customer c to provider p for elastic service s, and x s pc p is the expense demanded by provider p for its granting bandwidth x s pc . Then, the economic meaning of (9) is that each peer as service provider wants to achieve the objective of maximizing its own revenue.

At the optimum of sub-problems (7)- (10), the KKT conditions are satisfied, which are listed as following Then, we can obtain the dual problem of resource allocation model P1

The objective of the dual problem (14) is to minimize the total price charged by all service providers under the constraints that service customers are guaranteed with certain levels of satisfaction. In order to obtain the optimal price and bandwidth allocation, distributed algorithm should be developed to resolve the resource allocation model (3) and its dual problem (14). Traditional subgradient-based schemes can converge to the global optimum when only considering elastic services since their utility functions are all concave. However, these schemes do not work well when considering both elastic and inelastic services since the resource allocation problem becomes an intractable and difficult non-convex problem. They may produce suboptimal or even infeasible bandwidth allocation for each peer.

(11) ∇ x L P1 ( * , * ; * , * ) = 0, and ∇ y L P1 ( * , * ; * , * ) = 0

In this part we will approximate the utility maximization problem to an equivalent convex optimization problem by applying the successive approximation method. The resource allocation problem P1 equals to the following problem

The primal problem P1 and its extended problem P2 share the same optimal or suboptimal solutions. Furthermore, if

Proof The first part is obvious since the objective of P2 is a monotonically increasing logarithm function. For the second part, we can obtain the Lagrangian of problem P2 as follows ◻

Then the KKT point of P2 satisfies the following equations

x r pc .

(17) ∇ x L P2 ( * , * ; * , * ) = 0 and ∇ y L P2 ( * , * ; * , * ) = 0

Then the second statement can be easily verified by comparing the KKT conditions of P1 and P2 pair-by-pair. Thus this result can be obtained. Now the problem P2 is still a nonconvex optimization problem. Then, based on the transformations for an optimization problem (p.4.2.4 in Boyd and Vandenberghe 2004) , we transform the equivalent problem P2 into the following epigraph-form problem.

We find that the aforementioned model P3 is still a nonconvex optimization problem, since the first constraint is still nonconvex. In order to obtain a convex approximate problem, we derive an inequality to replace the nonconvex constraint with a convex one. Following Jensen's inequality, we introduce an important result as follows. Then we obtain the following approximation problem based on Lemma 2 

.

Then, we consider the canonical form for optimization problem, and deduce the following equivalent approximation problem

. Now the approximation problem P5 indeed includes a series of approximations when we choose different values of . Given an initial value of , the solution to P5 is a suboptimal solution to P1. After substituting this suboptimal solution, a new value is deduced by the update rule (22). With this new value , the corresponding new P5 is solved. After a sequence of approximations, the solution to P5 will finally converge to the global solution to P1. We will provide a resource allocation scheme for convergence to the stationary point of P5, which satisfies the KKT conditions for an optimization problem. At the stationary point the problem P5 is equivalent to P1, thus the point is exactly the optimal resource allocation of P1. It is not difficult to find that the extended utility U s c (y s c , s c ) for elastic service s is still a concave function since U s c (y s c ) is concave. For inelastic service r, we analyze the extended utility function U r c (y r c , r c ) , and obtain the following result.

The extended utility functions U r c (y r c , r c ) are continuously differentiable and strictly concave for inelastic services.

Proof We prove the result by verifying the second derivative of U r c (y r c , r c ) with respect to variable y r c . ◻ 

Thus, utility functions U(y r c , r c ) are strictly concave if the second derivatives are negative, that is, U r c (y r c )d 2 U r c (y r c )∕dy r2 c − dU r c (y r c )∕dy r c 2 < 0.

For elastic service with utility function (1), we can obtain For inelastic service with utility function (2), we obtain Thus the result is obtained. Now the objective of approximation problem P5 is strictly concave with respect to variables y s c and y r c , but is not strictly concave with respect to variables x s pc and x r pc . Meanwhile, the constraint conditions are linear, thus the constraint set of this optimization problem is convex. Thus, based on the convex optimization theory Bertsekas et al. (2003), we can obtain the following result.

Theorem 1 For the approximation problem P5 of resource allocation for multiclass services in P2P networks, there exists unique optimal resource allocation y s * c and y r * c for customer c when requesting elastic service s and inelastic service r. However, the optimal resource provision x s * pc and x r * pc from provider p to customer c is not necessarily unique.

In order to obtain the optimum of approximation problem P5, we firstly introduce the Lagrangian of problem P5

We apply the gradient projection method to solve approximate problem P5 and present the following resource allocation algorithm to achieve the optimum. The algorithm only depends on locally available information of each service provider that supports elastic and/or inelastic services.

x r pc .

Each service provider p updates its resource allocation for customer c who requests elastic service s with the following rule And each service provider p updates its resource allocation for customer c who requests inelastic service r with the following rule where (t) > 0 is the step size; > 0 is the parameter for low-pass filtering; a = (b) d c means a = min{d, max{b, c}} . Here, the augmented variables x s pc (t) and x r pc (t) are the optimal estimation of resource allocation x s pc (t) and x r pc (t) , respectively, which can be assisted to remove the possible oscillation without changing the optimal solutions x s * pc and x r * pc . Each service provider p updates its price p (t) with the following rule

x s pc (t).

Note that the approximation problem P5 indeed includes a series of approximations, where each one is identified by a value . If we select an appropriate value , we can achieve the optimum of the corresponding approximation problem by applying the resource allocation scheme above. In order to guarantee that the approximations of problem P5 finally become exact where the equality (21) always holds, each customer c updates its parameter s c for elastic service s with the following rule and parameter r c for inelastic service r with the following rule

In the proposed resource allocation scheme above, if customer c requests elastic service s from provider p, it computes the price s c (t) paid for provider p according to (29). And provider p calculates its charged price p (t) according to (35), and updates its resource allocation x s pc (t) for customer c with the rule of (27). We observe that resource allocation scheme (27) is a gradient-based fluid model which depends on the difference between the price s c (t) paid by customer c and the price p (t) charged by provider p. Meanwhile, if customer c requests inelastic service r from provider p, resource allocation scheme (31)-(34) will be executed to realize the optimum. On the other hand, provider p observes the aggregated load z p (t) from (36), and updates its charged price p (t) according to (35) . Thus the update rules for resource allocation and price are both a scaled gradient-based algorithm, which has been proven to be efficiently convergent to the optimum when choosing appropriate step sizes. However, each customer needs to learn the total utility values of all customers so as to update s c with the law of (37) and r c with the law of (38). Therefore, after each iteration each customer c communicates its utility value to all other customers in the network. In a new iteration the initial value is the stationary value of the previous iteration.

Therefore, the resource allocation algorithm can be described by the following pseudocode:

.

The algorithm presents a modification of the successive approximation method where the number of inner-iterations is limited to a certain value T. In the proposed resource allocation scheme, the value in the last inner-iteration of the previous outeriteration is the initial value in the next outer-iteration (Step 4). To solve the new approximate optimization, is computed according to the resource allocation in the last iteration of the previous outer-iteration ( Step 5). In next part we will investigate the performance of the proposed resource allocation scheme.

In this part we first obtain the following result by applying convex optimization approach. x r * pc − y r * c = 0

We can verify that the point ( * , * ; * , * ) also satisfies the Eqs. (17)-(19) which just are the KKT conditions of problem P2 after substituting s * c = U s c (y s * c )∕V * and r * c = U r c (y r * c )∕V * into the equations above, where

. Then this result is obtained. We study the convergence of the proposed resource allocation scheme, and obtain the following theorem.

Theorem 2 If the step sizes are sufficient small, then the proposed resource allocation scheme finally converges to a stationary point that satisfies the KKT conditions of primal problem P1.

Proof Define (k) (0) to be the initial point of outer-iteration k, and (k) * to be the stationary point of outer-iteration k. We first prove that (k) * is obtainable in each outeriteration k. Given a value , the approximation problem P5 is strictly concave with respect to variables y s c (t) and y r c (t) , thus it has a unique optimum solution * . However, the optimal resource allocation x s * pc and x r * pc from provider p to customer c for elastic service s and inelastic service r is not necessarily unique. With the assumptions on the small step sizes (t) > 0 and (t) > 0 , the proposed resource allocation scheme which is a gradient-based algorithm can converge to one of the optimums given s(k) c and r(k) c in each k outer-iteration Bertsekas et al. (2003) . Furthermore, we apply low-pass filtering method in the proposed resource allocation scheme, which can remove the possible oscillation due to non-uniqueness of optimum. Thus the optimum (k) * as well as (k) * is obtainable. ◻ Now we prove the convergence of the proposed resource allocation scheme. Denote the objective of P2 as

x s pc and y r c = ∑ p∶p∈P r (c) x r pc . The solution of P5 indeed increases monotonically G( ) in each outer-iteration.

The second equality is deduced by substituting (k) (0) = (k−1) * and

, into the right-hand size. The first inequality is obtained since (k) * is the optimum of P5 given a value (k) . The second inequality is satisfied from (21). Meanwhile, G( ) is a continuous function, then G( ) is bounded as is bounded (recall that is bounded). Furthermore,

the sequence {G( (k) * ), k = 1, 2, …} monotonically increases, thus it can converge from convex optimization (Bertsekas et al. 2003, Prop.A.3) . Then the sequence { ∑ c∶c∈C s U s c (y s(k) * c ) + ∑ c∶c∈C r U r c (y r(k) * c ), k = 1, 2, …} also converges. From Lemma 4 we have known that the stationary point of the approximation problem P5 is also the KKT point of P2. On the other hand, based on Lemma 1, we have obtained the KKT conditions of P2 are equivalent to those of P1. Thus the proposed resource allocation scheme can eventually converge to the stationary point which satisfies the KKT conditions of primal problem P1. Then, this theorem is completed.

Recall that the utility maximization model of resource allocation for multiclass services in P2Ps is a non-convex optimization problem, since the utility functions for inelastic services are sigmoidal, then the final stationary points satisfying the KKT conditions may be suboptimal solutions to the primal problem. By substituting these KKT points into the utility maximization model and comparing the corresponding objective value, the final optimal solution can be derived, as well as the optimal objective.

In this part we consider the performance of the proposed resource allocation mechanism and present some numerical examples to show its convergence in P2P networks. We firstly investigate the scheme in a simple network architecture and then analyze its performance in large scale networks.

Consider a simple network which is composed of two service providers and four service customers. The service providers have the access link capacity C = (C 1 , C 2 ) = (5, 10) Mbps. The minimal and maximal resource requirements for each elastic or inelastic service are 0.01 Mbps and 10 Mbps, respectively. The initial rates x s pc (t) and x r pc (t) are all set to 0.5 Mbps, and the initial parameters s c and r c are all chosen 0.25. The low-pass filtering parameter is chosen = 0.2.

In this case we consider the four customers are only requesting elastic services and analyze the proposed resource allocation scheme. The willingness-to-pay of four customers is w = (4, 3, 2, 1) , then the utility functions when customers request these elastic services are given by: U s 1 (y s 1 ) = 4 log(y s 1 + 1) , U s 2 (y s 2 ) = 3 log(y s 2 + 1) , U s 3 (y s 3 ) = 2 log(y s 3 + 1) , and U s 4 (y s 4 ) = log(y s 4 + 1). We observe that the proposed scheme has two levels of convergence. The outeriterations update , and the inner-iterations solve the convex approximation problem P5. In order to guarantee the convergence of every outer-iteration process, the step sizes should be small enough and the number of inner-iterations should be large enough. Then we choose the step sizes (t) = (t) = 0.2∕t and the number of inneriterations as a fixed value T = 500.

We depict the simulation results obtained from the proposed resource allocation scheme in Fig. 2 and can observe its validity and performance. We find that the scheme gradually tends to a steady state and finally converges to an optimal resource allocation for each service customer within reasonable iterations.

We list the optimum derived from the proposed scheme in Table 1 . Meanwhile, we also presented the optimal solution by using nonlinear programming software LINGO in this table. Since the objective function is not a strictly concave function with the variable x = (x s pc , p ∈ P, c ∈ C s ) , the optimal resource allocated by service providers for customers is not unique, which is also discussed in Theorem 1. However, the objective function is a strictly concave function with the variable y = (y s c , c ∈ C s ) , thus as we can observe in Table 1 , the optimal total resource obtained by each customer is unique.

Next we analyze the convergence speed of the proposed resource allocation algorithm. In order to improve the convergence speed of the algorithm, we conduct several experiments to find an appropriate value for the number T of inner-iterations. Also we apply a constant step size for the subgradient-based update law since it often has a faster convergence speed than the diminishing step size. In this simulation we choose the inner-iterations number T = 100 and step sizes (t) = (t) = 0.2 , and depict the performance of the scheme in Fig. 3 . We find that the convergence speed of the algorithm is improved at this time, and the optimum can be achieved in fewer iterations. 

In this part we investigate the performance of the proposed resource allocation scheme for both elastic and inelastic services. Without loss of generality, we assume the first two customers request inelastic services with utility functions U r 1 (y r 1 ) = 6 1+e −(y r 1 −4) − 6 1+e 4 and U r 2 (y r 2 ) = 4 1+e −(y r 2

−2) − 4 1+e 2 . The others request elastic services with utility functions U s 3 (y s 3 ) = 2 log(y s 3 + 1) , and U s 4 (y s 4 ) = log(y s 4 + 1) . We firstly choose the number of inner-iterations T = 500 and the diminishing step sizes (t) = (t) = 0.2∕t , and present the behavior of the scheme in Fig. 4 . We observe that the scheme finally converges to an optimal resource allocation x * = (2.1474, 4.2731, 1.3096, 2.5993, 1.1372, 2.3098, 0.4057, 0.8178)Mbps within reasonable iterations.

We also investigate the convergence speed of the resource allocation scheme in this scenario where elastic and inelastic services are coexisting. We choose the inner-iterations number T = 100 and constant step sizes (t) = (t) = 0.2 , and depict the scheme behavior in Fig. 5 . We can observe that the scheme converges 

Now we consider the performance of the resource allocation scheme in large scale networks with different number of peers. The access link capacity of service providers are all assumed to be 20 Mbps. The low-pass filtering parameter is = 0.2 and the initial parameters are all s c = 0.25 . And the number of inner-iterations is T = 100 and the step sizes are (t) = (t) = 0.2.

Considering the different willingness-to-pay of customers when they request services, we assume that there are four types of customers in the P2P networks. Each type of customers has the same number and is with one of the utility functions Fig. 6 , we depict the evolution of aggregated utility in large scale P2P networks with different number of peers. We find that the number of peers does not influence the convergence speed of the resource allocation scheme. The aggregated utility increases gradually with the number of peers but, in almost all cases, the optimal value is achieved within the same number of iterations (e.g., 200 iterations). In fact, it is the parameters of the resource allocation scheme such as inner-iterations number and step sizes that mainly affect the convergence speed, as we have discussed in Sect. 5.1.

In this case of resource allocation for multiclass services in large scale networks, we assume that both customers requesting elastic services and those requesting inelastic services are divided into two types. Each type of customers has the same one of the utility functions considered in Sect. 5.1.2. Then in Fig. 7 , we present the evolution of aggregated utility of multiclass services in different scale networks. Similar to the results for only elastic services in Sect. 5.2.1, the optimal objective can be finally reached in almost the same number of iterations. However, it appears to converge slower than that in the case for only elastic services. This is rather expected. When considering only elastic services, the service customers have the same structure of logarithmic utility functions and run the separate update steps in parallel. We Iterations Aggregated utility P=2,C s =2,C r =2 P=4,C s =8,C r =8 P=20,C s =40,C r =40 P=50,C s =100,C r =100 believe that the convergence speed can be also improved if we choose proper parameters such as more suitable inner-iterations number and step sizes.

In recent years P2P networks have played an important role in supporting elastic applications (e.g., file sharing) and inelastic applications (e.g., video distribution) over the Internet, and been applied into many scenarios, e.g., distributed storage, cloud computing, edge computing and vehicular networks. Especially, P2Ps have well supported online video conferencing applications (e.g., Tencent meeting, Zoom) in 2020 due to the epidemic of COVID-19. However, it is a crucial challenge and difficult problem to achieve reasonable and effective resource allocation for peers who acquire both elastic and inelastic services. In this paper we concentrate on resource allocation for both elastic and inelastic services in P2P networks, and formulate the utility maximization model for peers who request these services. The utility maximization model is an intractable and difficult nonconvex optimization problem, since the inelastic services have non-concave utility functions. In order to obtain the optimal resource allocation, we approximate the utility maximization problem to an equivalent convex optimization problem by applying the successive approximation method, and design a gradient-based resource allocation scheme to achieve the optimal solution of the approximations. The proposed scheme is proven to converge to an optimal solution of the primal utility maximization model which also satisfies the KKT conditions. Numerical examples verify the convergence of resource allocation scheme for both elastic and inelastic services. For further research work, we will investigate the resource allocation of multiclass applications in edge computing which builds on P2Ps.

Modeling max-min fair bandwidth allocation in BitTorrent communities

Convex analysis and optimization

Utility maximization in peer-to-peer systems with applications to video conferencing

Resource pricing in peer-to-peer networks

Fair resource allocation in peer-to-peer networks (extended version)

Reputation-based resource allocation in P2P systems: a game theoretic perspective

Evolutionary stability of reputation-based incentive mechanisms in P2P Systems

Reputation based probabilistic resource allocation for avoiding free riding and formation of common interest groups in unstructured P2P networks. Peer-to-Peer

Distributed rate allocation for inelastic flows

Incentive mechanism design for heterogeneous peer-to-peer networks: a Stackelberg game approach

A framework for distributed bandwidth allocation in peer-to-peer networks

A mechanism for pricing and resource allocation in peer-to-peer networks

Non-convex optimization and rate control for multi-class services in the Internet

A mechanism for resource pricing and fairness in peer-to-peer networks

Utility maximisation for resource allocation of migrating enterprise applications into the cloud

Resource allocation for multi-class services in multipath networks

A scheme of resource allocation for heterogeneous services in peer-to-peer networks using particle swarm optimization

Utility optimization-based bandwidth allocation for elastic and inelastic services in peer-to-peer networks

Optimal resource allocation model and algorithm for elastic enterprise applications migration to the cloud

Utility maximization for bandwidth allocation in peer-to-peer file-sharing networks

Optimal bandwidth sharing in multiswarm multiparty P2P videoconferencing systems

Resource allocation in underprovisioned multioverlay peer-to-peer live video sharing services. Peer-to-Peer

A general inner approximation algorithm for nonconvex mathematical programs

Game-theoretic auction design for bandwidth sharing in helperassisted P2P streaming

A stochastic approximation resource allocation approach for HD live streaming

Cache bandwidth allocation for P2P file-sharing systems to minimize inter-ISP traffic

Moment-based approximations for first-and second-order transient performance measures of an unreliable workstation

A learning-based resource allocation approach for P2P streaming systems

Reputation-based resource allocation in P2P systems of rational users

Smart collaborative tracking for ubiquitous power IoT in edge-cloud interplay domain

Smart collaborative automation for receive buffer control in multipath industrial networks

Joint rate and power control in wireless network: a novel successive approximations method

Joint rate and power control for elastic and inelastic traffic in multihop wireless networks

The random access NUM with multiclass traffic

Network utility maximisation framework with multiclass traffic

Multi-path utility maximization and multipath TCP design

Enabling collaborative edge computing for software defined vehicular networks

Betweenness centrality based software defined routing: observation from practical Internet datasets

Caching strategy based on hierarchical cluster for named data networking

The authors would like to thank the anonymous reviewers and Associate Editor for very detailed and helpful comments and suggestions to improve this work, and the support from the National Natural Science Foundation of China (Nos. 71671159 and 71971188), the Humanity and Social Science Foundation of Ministry of Education of China (No. 16YJC630106), and the Natural Science Foundation of Hebei Province (Nos. G2018203302, G2020203005).