A mechanism of bandwidth allocation for peer-to-peer file-sharing networks via particle swarm optimization

Abstract

In the last years peer-to-peer (P2P) networks have become an important and prevalent architecture in the Internet and have been commonly applied into many scenarios such as big data storage and management, cloud computing, vehicular networks and social networking. The overall performance of P2P networks mainly depends on cooperation between peers, so as to encourage each peer to contribute its resource to others and reduce free-riding behaviors. Then each peer has to face a dilemma decision that how much of its available bandwidth it will allocate to uploads for others and how much it will reserve for its own downloads. In this paper we consider bandwidth allocation in P2P networks where both upstream and downstream flows traverse one common access link with finite capacity, and formulate the utility maximization model for bandwidth allocation. The model is difficult to resolve since it is an interplay problem between upload and download decisions of each peer. In order to achieve the optimal bandwidth allocation, we present a heuristic scheme using Particle Swarm Optimization (PSO), and discuss the performance with numerical examples in different network scenarios. Simulation results show that the scheme can achieve the global optimum within reasonable iterations.

Keywords

Peer-to-peer networks resource allocation particle swarm optimization utility maximization

1 Introduction

Peer-to-peer (P2P) networks have received much attention in the last several years. They are used to share resources like bandwidth, storage capacity and CPU cycles directly with its members. The benefit derived by a peer from the networks will be more if greater number of peers exchange their resources. In contrast to the traditional client-server architectures, which mainly rely on a small number of powerful servers, P2Ps have many advantages such as high scalability and strong robustness. Therefore, they have been commonly applied into several scenarios such as data storage and management [1 –3], cloud computing [4 –6], vehicular networks [7, 8], social networking [9 –11], and so on.

The system performance of P2P networks is mainly determined by the cooperation between peers. However, P2P networks face a fundamental problem of unfairness, that is, many peers are free-riding with only consuming much download bandwidth of others but contributing little or no upload bandwidth to others. By unfairly taking the upload bandwidth of contributing peers, free-riders cause slower download time for reasonable peers and degrade the system overall performance. Thus, reasonable resource allocation has become an emerging area in recent years and some interesting resource allocation schemes are presented accordingly, such as reputation-based resource allocation [12 –14], credit-based incentive mechanisms [15, 16], microeconomics-based resource allocation [17 –20], pricing-based approaches [21 –24], game-based mechanisms [25, 26], fairness-aware schemes [27 –30], and so on. The main motivation of these resource allocation approaches is to promote cooperation between peers, so as to improve performance of P2P networks such as reducing free-riding and realizing fairness and achieve reasonable resource allocation among all participating peers.

In this paper, we consider bandwidth as the shared resource because it is the most commonly demanded resource in P2P networks. We assume that peers share their downloaded files with each other (e.g., in Bittorent), thus contributing back to network by sharing the uplink bandwidth. Then, in P2P networks, each peer is characterized by a utility function that describes its perceived satisfaction or QoS for receiving a specific amount of bandwidth and its costs for granting certain bandwidth to others. Then the network-wide objective is to maximize the total network utility as a whole (social welfare), i.e., the sum of peers utilities. However, the network utility maximization problem for P2P networks is difficult to resolve due to the fact that the client and the server role of each peer are interrelated and the one restrains the other. Furthermore, each peer may be connected to the backbone network through a local hub or through cable modem or ADSL line. In the former case, both upstream and downstream flows use one common access link with finite capacity. Each peer has to face a dilemma decision that how much of its available bandwidth it will allocate to uploads and how much it will use for its own downloads. Obviously, increasing the amount of bandwidth for uploads directly affects the download bandwidth and thus the perceived utility. All these issues above make the utility maximization problem difficult to handle.

To achieve the optimal resource allocation in decentralized P2P architectures, reasonable resource allocation schemes should be developed to solve the optimization problem, so that each peer can decide how much of its available bandwidth should be allocated to other peers and how much should be reserved for its own download. In order to deal with the difficult optimization problem, we apply Particle Swarm Optimization (PSO) to resolve the bandwidth allocation model, propose a heuristic scheme to realize optimal bandwidth allocation, and verify the performance with simulation results in different network scenarios.

The rest of this paper is summarized as follows: We review some resource allocation work in P2P networks in Section 2, and introduce the bandwidth allocation model for P2P networks in Section 3. Then we propose a heuristic scheme by applying PSO to resolve the problem and achieve optimal bandwidth allocation in Section 4. In Section 5 we present some numerical results to illustrate the performance of the scheme. We further discuss the application of this scheme to another type of utility maximization model in Section 6. Finally we conclude this paper in Section 7.

2 Related Work

P2P networks face free-riding problem, which causes unfairness among peers and degrades the performance of the networks. Creus-Mir et al. [31] presented a model of bandwidth allocation in a stylized P2P file-sharing networks, where some peers are freeriders who only download from sharers but do not contribute files. This work constitutes a first step towards a general analytical foundation for scarce resource allocation in P2P file-sharing networks. In recent years, resource allocation in P2P networks has received much attention and some interesting research results have been obtained. Among these research work, various incentive schemes are presented as a means for encouraging peers’ cooperation. For example, Gupta et al. [13] proposed a reputation based probabilistic resource allocation scheme for avoiding free riding and formation of common interest groups in unstructured P2P networks. Kang and Yang [16] investigated experience optimization for peer-to-peer streaming networks with credit-based incentive mechanisms. From the game theoretic perspective, Kang and Wu [25] presented an incentive mechanism design for heterogeneous peer-to-peer networks, and Goswami et al. [14] gave a reputation-based resource allocation in P2P systems. Vakili et al. [32] devised a self-organized mechanism for cooperation policy setting of the interacting peers based on decision-theoretic analysis. The main motivation behind these incentive schemes is to encourage each peer to cooperate and serve other peers, so as to improve the performance of P2P networks such as reducing free-riding and achieving fairness.

Besides, there is another type of research where peers are assumed to cooperate with each other to improve overall network performance. In this filed, resource pricing is often used to adjust the bandwidth demand and supply between interactive peers and to ensure a fair bandwidth allocation of each peer among its requesters [21]. This approach takes into account economic issues when managing limited resources in P2P networks. For example, Kumar et al. [22] designed a mechanism for pricing and resource allocation in P2P networks that allows users in a firm to effectively share computing resources. Koutsopoulos and Iosifidis [17] formulated the utility maximization model for bandwidth allocation in a star topology network with the capacity bottleneck being the peer access link to the backbone. By introducing new auxiliary variables and constraints, they transformed the original problem into one that is amenable to distributed solution by dual decomposition methods. Chen et al. [20] presented the utility maximization model for resource allocation of video conferencing applications in P2P systems, and implemented a distributed algorithm in a peer-assisted multiparty conferencing system by utilizing only end-to-end delay measurements between P2P nodes. In [23, 24] the authors presented a novel price-based resource allocation scheme for P2P file-sharing networks by applying the first order Lagrangian method and low-pass filtering scheme, thus a service provider could allocate its resources to its customers based on offered prices. They also discussed the convergence and stability through both theoretical analysis and simulation results. Recently Li et al. [33] investigated bandwidth allocation of access links in P2P file-sharing networks and developed a network-wide utility maximization model that combines both fully coupled and uncoupled cases by adopting an adjustable parameter, that is, service customers can not and can discriminate bandwidth provision among different providers.

In this paper we concentrate on the latter research field and consider bandwidth allocation in P2P file-sharing networks. This work is different from the research results aforementioned, where upload bandwidth is assumed to be scarcer than download bandwidth and efficient allocation schemes are always proposed for upload bandwidth. We consider the case that both upstream and downstream flows traverse one common access link with finite capacity in P2P networks. That is, each peer has to decide how much of its available bandwidth it will allocate to uploads and how much it will use for its own downloads. It is an interplay problem between upload and download decisions of each peer, and is difficult to resolve through traditional methods, especially when the number of peers is very large. In order to overcome it, we apply PSO to resolve the bandwidth allocation model, and propose a heuristic scheme to achieve optimal bandwidth allocation. It is to find the optimal position (the optimal bandwidth allocation for peers) according to the fitness function (the objective function) through the velocity (the auxiliary variable). It has many advantages, for example, it does not need to calculate the gradients of the objective function, especially when the gradients are difficult to obtain or even they do not exist.

3 Model Formulation

3.1 Model description

3.1.1 Network architecture

In a P2P network there are a set N of peers. The peers interact with each other for a certain time by requesting or allocating resources to each other. During the period of peer interaction and resource allocation the P2P network is static, i.e., we do not consider the churn of this network due to peer arrivals or departures during resource allocation.

In the P2P network, each peer p is connected to the backbone network through an access link with certain capacity C_p. The backbone network is supposed as to be of high enough capacity and it does not occur in-network congestion. Thus the access link of each peer is the performance bottleneck. The resources (i.e. upload bandwidth of a peer) are divisible and any allocation of resources has a benefit for a requesting peer. Then the upload bandwidth of providing peers is scare such that competition between requesting peers arises. We consider the case that the access link of a peer is shared among several upstream and downstream flows and simultaneously used for upload and download. Nevertheless, the resource allocation model can also be reduced to the case of separate upstream and downstream links, e.g., ADSL link.

3.1.2 Granted bandwidth

In the P2P network, each peer as client sends its content requests to other peers. On the other hand, each peer as server receives requests from others and needs to serve them by granting them a certain amount of bandwidth. Let x_pi be the amount of bandwidth which is granted from peer p to peer i, x_p be the bandwidth provisioning vector which denotes the bandwidth granted by peer p to other peers, and ${\tilde{x}}_{p}$ be the bandwidth vector which denotes the amounts of bandwidth x_ip provided to peer p by others i ≠ p. Clearly, x_pp = 0 for all p ∈ N.

3.2 Utility function

Each peer p is characterized by a utility function U_p (·) which quantifies the amount of perceived satisfaction from receiving certain amount of bandwidth. It consists of two parts. The first part is related to the granted bandwidth from other peers, and represents the benefit of a peer. The second one represents the cost to a peer, since it offers bandwidth to others. The utility function is assumed to be strictly concave, twice continuously differentiable and bounded.

We consider the case that each peer as client can discriminate among other peers as servers. Fox example, each peer p may receive different content from different peers, then the obtained utility for peer p may be different even for the same amount of granted bandwidth. Thus, the satisfaction U_p (·) of peer p is separable. It depends on the amount of granted bandwidth x_ip from each other peer i separately, and also on the amounts of upload bandwidth x_pi this peer provides to each other peer i. The respective benefit or cost for the bandwidth may be different for different peers since they receive different contents. A peer p receives its benefit from its downloads based on a rule of diminishing marginal returns. This benefit can be represented by a non-decreasing differentiable concave function u_pi of the download bandwidth x_ip from each peer i. Meanwhile, peer p incurs a cost when it provides upload bandwidth for each peers. The cost can be described by a non-decreasing, differentiable convex function v_pi of the upload bandwidth x_pi to each peer i. Thus, the utility of peer p has the following form

$U_{p} (x_{p}, {\tilde{x}}_{p}) = \sum_{i : i \in N}^{} (u_{p i} (x_{i p}) - v_{p i} (x_{p i}))$ (1) Here, $U_{p} (x_{p}, {\tilde{x}}_{p})$ is differentiable, and concave with respect to x_ip and x_pi.

3.3 Problem statement

Performance evaluation for resource allocation in P2Ps can be characterized under different objectives. Examples of objectives include the following: maximizing the social welfare of the network as a whole (social welfare maximization), maximizing the profit of the peers as servers (profit maximization), and minimizing the cost of the peers as clients (cost minimization). In this work we consider the case where peers cooperate to maximize the social welfare, namely the aggregated utility of peers, subject to link capacity constraints of peers. The maximization requires that each peer who receives resource requests will grant the optimal amounts of its bandwidth to other peers in an efficient and reasonable manner.

The general resource allocation in P2Ps is formulated as follows: $\begin{array}{l} \max \sum_{p : p \in N}^{} U_{p} (x_{p}, {\tilde{x}}_{p}) \\ subject to \sum_{i : i \in N}^{} x_{i p} + \sum_{i : i \in N}^{} x_{p i} \leq C_{p}, p \in N \\ over x_{i p} \geq 0, x_{p i} \geq 0, i, p \in N . \end{array}$ (2) The resource allocation model (2) is considered as the P2P SYSTEM problem. Here, the objective of resource allocation is to maximize the aggregated utility of peers with the constraints of each peer’s access link capacity. The constraints indicate that the total downstream and upstream rate of a peer must not exceed its access link capacity.

3.4 Model analysis

From the nonlinear programming theory [34], the objective of resource allocation model (2) is concave with respect to primal variables. The constraints are linear, and thereby all of them are convex. So the feasible set is compact. Thus the resource allocation model (2) is a convex programming problem, and the optimal resource allocation can be deduced from convex theory.

The Lagrangian of this nonlinear optimization problem is $\begin{array}{l} L (x, \tilde{x}, λ) = \sum_{p : p \in N} \sum_{i : i \in N} (u_{p i} (x_{i p}) - v_{p i} (x_{p i})) \\ + \sum_{p : p \in N} λ_{p} (C_{p} - \sum_{i : i \in N} x_{i p} - \sum_{i : i \in N} x_{p i}) \end{array}$ (3) where λ = (λ_p, p ∈ N) is the price vector with element λ_p ≥ 0, which can be regarded as the price charged the access link of peer p.

The Lagrangian (3) can be rewritten as $\begin{array}{l} L (x, \tilde{x}, λ) = \sum_{p : p \in N} ((\sum_{i : i \in N} u_{p i} (x_{i p}) - λ_{p} \sum_{i : i \in N} x_{i p}) \\ - (\sum_{i : i \in N} v_{p i} (x_{p i}) + λ_{p} \sum_{i : i \in N} x_{p i})) + \sum_{p : p \in N} λ_{p} C_{p} \end{array}$ (4)

Note that the first term in (4) is separable in x_ip and x_pi. Then the objective function of the dual problem is $\begin{array}{l} D (λ) = \max_{x, \tilde{x}} L (x, \tilde{x}, λ) \\ = \sum_{p : p \in N} \max_{x} (\sum_{i : i \in N} u_{p i} (x_{i p}) - λ_{p} \sum_{i : i \in N} x_{i p}) \\ - \sum_{p : p \in N} \max_{\tilde{x}} (\sum_{i : i \in N} v_{p i} (x_{p i}) + λ_{p} \sum_{i : i \in N} x_{p i}) \\ + \sum_{p : p \in N} λ_{p} C_{p} \end{array}$ (5) Let ${Utility}_{p} (λ_{p}) = \max_{x} (\sum_{i : i \in N} u_{p i} (x_{i p}) - λ_{p} \sum_{i : i \in N} x_{i p})$ (6)

${Cost}_{p} (λ_{p}) = \max_{\tilde{x}} (\sum_{i : i \in N} v_{p i} (x_{i p}) - λ_{p} \sum_{i : i \in N} x_{i p})$ (7)

We can interpret the sub-problems (6) and (7) from the perspective of economics. Each peer is selfish and tries to maximize its own utility, which depends on the received bandwidth allocation. However, each peer has to pay a price for using bandwidth. Recall that, x_ip is the amount of bandwidth provided to peer p by peer i and λ_p is the price charged the access link of p, then the product λ_px_ip reflects the cost that peer p is willing to pay for its access link for transmitting its file content. Thus, u_pi (x_ip) - λ_px_ip means the profit of peer p after receiving granted bandwidth x_ip from peer i, and Utility_p is the total profit of peer p from all its providers. Meanwhile, x_pi is the amount of bandwidth that peer p grants to peer i, then the product λ_px_pi reflects the cost that peer i should pay for peer p when using p’s access link for download. Thus, v_pi (x_pi) + λ_px_pi denotes the cost of peer i when receiving bandwidth x_pi from peer p, and Cost_p is the total cost when peer p provides bandwidth for others.

Then, the dual problem of bandwidth allocation for P2Ps is $\begin{array}{l} \min D (λ) \\ over λ_{p} \geq 0, p \in N . \end{array}$ (8)

The dual problem above is modeled as an optimization problem with prices charged by access links of peers, which is to minimize the total price under the constraints that each peer is guaranteed with certain level of satisfaction.

It is found that solving the resource allocation model (2) or its dual problem (8) in a distributed fashion is difficult due to the fact that there exists coupling in the constraints or gradients. Meanwhile, the utility function of each peer p depends on bandwidth allocation variables x_ip of other peers and also on local allocation decisions x_pi, which is an interplay problem between upload and download decision of each peer. In the following our aim is to devise distributed iterative algorithm to solve the coupled resource allocation problem (2).

4 Bandwidth allocation scheme

4.1 PSO method

4.1.1 PSO background

Particle swarm optimization (PSO), originally developed by Kennedy and Eberhart [35], is inspired by the social behavior and auto-organization of bird flocking and fish schooling. The social behavior, demonstrated by the exchange of information between the particles of the population, generates exploration for better positions, while the individual learning corresponds to the exploitation component. This method has been found to be robust for solving optimization problems featuring nonlinearity and nondifferentiability multiple optima, as well as high dimensionality through adaptation, in the fields of network resource allocation [36], power optimization [37], neural network training [38], data clustering [39], and so on. For more details, please refer to the survey on the potential of PSO for solving various kinds of optimization problems in chemometrics [40].

PSO is an evolutionary computation technique. It belongs to the family of algorithms based on the concept of swarm intelligence. In a PSO system [35], each particle flies in the search space with a velocity which is dynamically adjusted according to its own experience, and the experience of neighboring particles, making use of the best position encountered by itself and its neighbors. The swarm direction of a particle is defined by the set of its history experience.

Each particle keeps track of its coordinates in the space of interest, which are associated with the best solution (fitness) it has achieved so far. This best value is called Pbest. Another best value which is tracked by the particle swarm optimizer is the overall best value, and its location, obtained so far by particles in the population. This location is called Gbest. At each iteration step, the particle swarm optimization process consists of velocity changes of each particle toward Pbest and Gbest locations. Acceleration is weighted by a random term, which separates random numbers generated for acceleration toward Pbest and Gbest locations. Let x and v denote a particle coordinates (position) and its corresponding flight speed (velocity) in a search space, respectively.

4.1.2 PSO methodology

In the physical space, the position and velocity of particle a are represented as $X^{a} = (x_{11}^{a}, \dots, x_{1 p}^{a};$ $\dots; x_{i 1}^{a}, \dots, x_{ip}^{a})$ , and V^a = $(v_{11}^{a}, \dots, v_{1 p}^{a}; \dots; v_{i 1}^{a},$ $\dots, v_{ip}^{a})$ , respectively, in the PSO algorithm. Let ${Pbest}^{a} = (x_{11}^{aPbest}, \dots$ , $x_{1 p}^{aPbest}, \dots, x_{i 1}^{aPbest}, \dots,$ $x_{ip}^{aPbest})$ and $Gbest = (x_{11}^{Gbest}, \dots, x_{1 p}^{Gbest}, \dots, x_{i 1}^{Gbest},$ $\dots, x_{ip}^{Gbest})$ be the best position of particle a and its neighbors’ best position so far, respectively. Following the basic PSO mechanism [35], the velocity of particle a is updated by the following law

$\begin{matrix} V^{a} (k + 1) = ω V^{a} (k) + c_{1} * R_{1} * ({Pbest}^{a} (k) \\ - X^{a} (k)) + c_{2} * R_{2} * (Gbest (k) - X^{a} (k)), \end{matrix}$ (9) where V^a (k) is the velocity of particle a at the iteration step k and satisfies $V_{min}^{a} < V^{a} (k) < V_{max}^{a}$ , ω is the inertia weight factor, c₁ and c₂ are the acceleration constants, $R_{1}$ and $R_{2}$ are the uniform random values between 0 and 1, X^a (k) is the current position of particle a at the iteration step k, Pbest^a (k) and Gbest (k) are the best position of the particle a and the best position of the whole group at the iteration step k.

Meanwhile, particle a moves from the current position to the better one according to the following law $X^{a} (k + 1) = X^{a} (k) + V^{a} (k + 1),$ (10) where X^a (k + 1) is the position of particle a at iteration k + 1.

In the update law above, the parameters $V_{min}^{a}$ and $V_{max}^{a}$ determine the solution, or fitness, with which regions between the present position and target position are searched. This limit enhances the local exploration of the problem space and realistically simulates the incremental changes of human learning. The constants c₁ and c₂ represent the weighting of the stochastic acceleration terms that pull each particle toward Pbest and Gbest positions. Suitable inertia weight ω selection provides a balance between global and local explorations. The suitable choice of acceleration constants and inertia weight factor is vital for algorithm performance.

4.1.3 The fitness function

In PSO method the fitness function defines how well the position vector of each particle satisfies the requirements of the optimization problem. It denotes the objective function that is being maximized. Note that the resource allocation model (2) for P2Ps is subjected to inequality constraints, then we use penalty function method to construct the fitness function. Penalty function techniques transform the constrained problem into an unconstrained problem by penalizing the infeasible solutions. Using a penalty function has become one common approach to solve constrained optimization problems and has been applied into the PSO algorithm [41]. In the penalty method, the fitness function is described as follows: $F_{f} = {\begin{matrix} f (X), & if the solution is feasible \\ f (X) + h (k) H (X), & otherwise \end{matrix}$ (11)

where f (X) is the original objective function to be optimized; h (k) is a penalty value where k is the algorithm’s current iteration number; and H (X) is a penalty factor which is a relative violated function of the constraints. Regarding the penalty value, it is usually set to $h (k) = \sqrt{k}$ or $h (k) = k \sqrt{k}$ .

4.1.4 The adaptive inertia weight factor (AIWF)

In PSO method, it is very important to coordinate global exploration and local exploitation so as to efficiently find the optimum [42], since the performance of PSO mainly relies on its parameters. Note that the rule (9) represents the influence of previous velocity, and provides the necessary momentum for particles to roam across the search space. It is regarded that a larger inertia weight pressures toward global exploration, while a smaller inertia weight pressures toward fine-tuning of the current search area. In [43] the authors improved the update law of PSO with a linearly varying inertia weight over the generations. Later, in [44] the authors presented an adaptively varying inertia weight to realize trade-off between exploration and exploitation. Generally, the adaptive inertia weight factor (AIWF) has the following form

$ω = {\begin{array}{l} ω_{\min} + & \frac{(ω_{\max} - ω_{\min}) (f - f_{\min})}{f_{a v g} - f_{\min}}, \\ if f \leq f_{a v g}, \\ ω_{\max}, & otherwise \end{array}$ (12) where ω_max and ω_min represent the maximum and minimum of ω respectively, f is the current objective value of the particle, f_avg and f_min are the average and minimum objective values of all particles, respectively. The improved inertia weight factor (12) varies depending on the objective value of the particle. Thus particles with low objective values can be protected while particles with objective values over the average will be disrupted. That is, good particles tend to perform exploitation to improve results by local search, while bad particles tend to perform large modification to explore space with large steps.

4.2 Bandwidth allocation using PSO

In this paper, our aim is to devise an efficient scheme to resolve the resource allocation model (2) for P2Ps where exists coupling variables in the constraints and also in the objective functions. In the following we will present a resource allocation mechanism using PSO method to solve the optimization problem efficiently.

4.2.1 The corresponding relation of the variables

The important notations of the resource allocation scheme using PSO are defined as follows.

Particle: Position of each particle within the population in PSO represents a candidate solution for solving the resource allocation problem (2). That is, each particle X^a represents one possible resource allocation solution for model (2). The ipth dimension of the particle a corresponds to the amount of granted bandwidth x_ip from peer i to peer p. In the process of initialization, the position of particle a is bounded in [0, C_p], where C_p is the access link capacity.

Velocity: The velocity V^a in PSO is the auxiliary variable for the algorithm to find the solution. In the iteration process, it satisfies $V^{a} \in [V_{min}^{a}, V_{max}^{a}]$ .

4.2.2 The definition of the fitness function

The objective is to maximize aggregated utility subject to access link capacity constraints in the resource allocation model for P2Ps, so we give the following fitness function according to (11)

$F_{f} = {\begin{array}{l} \sum_{p : p \in N} U_{p} (x_{p}, {\tilde{x}}_{p}), if \sum_{i : i \in N} x_{i p} + \sum_{i : i \in N} x_{p i} \leq C_{p} \\ \sum_{p : p \in N} U_{p} (x_{p}, {\tilde{x}}_{p}) + \\ \sum_{p : p \in N} (C_{p} - \sum_{i : i \in N} x_{i p} - \sum_{i : i \in N} x_{p i}) \\ otherwise . \end{array}$ (13)

where the penalty value μ_p > 0, p ∈ N, is a positive value, and is interpreted as the access link price of peer p in the network. So if one particle satisfies all constraints, it is a feasible particle. Otherwise, an extra charge should be paid which is proportional to the amount of violation with large positive price.

4.2.3 The stopping criterion

The searching procedure can be stopped when the current iteration number reaches the predetermined maximum iteration number or the best position does not change any more. In all, the algorithm is to find the optimal position (the optimal resource allocation for peers) according to the fitness function (the objective function) through the velocity (the auxiliary variable).

4.2.4 Main steps

Now we present the heuristic scheme using PSO to resolve the resource allocation problem (2) (position in PSO) according to the objective function (fitness function in PSO) through the auxiliary variable (velocity in PSO). The following iteration steps are carried out until convergence.

Step 1: Initialize the variables and the parameters.

Let k be zero and initialize PSO parameters (ω, c₁, c₂). Initialize position of particle X^a, which corresponds to a set of resource allocation, and initialize velocity of particle V^a, which is a auxiliary variable in the scheme. The particle must be one of the feasible candidate solutions satisfying the inequality constraints on link capacities.

Step 2: Calculate fitness.

The current searching points are evaluated by using the objective functions of the target problem, i.e., F_f in (13). Pbest^a (k) is set to be the searching point, and Gbest (k) is the best evaluated value among all Pbest^a (k) at the iteration k, respectively.

Step 3: Update the searching points.

If the evaluation of each point is better than the previous Pbest^a (k), the value is set to Pbest^a (k).If the best Pbest^a (k) is better than Gbest (k), the value is set to be Gbest (k). All the Gbest (k) are candidates for the final control strategy. Update velocities and positions according to the update law.

Step 4: Set stop criterion.

As mentioned before, when the link capacity constraint is violated, an extra charge should be paid, which is proportional to the amount of violation with the penalty value. When the optimal objective is achieved (i.e., the objective of resource allocation model does not change any more), the searching procedure can be stopped. The last Gbest (k) can be drawn as the optimal position, and the corresponding $x_{ip}^{Gbest} (k)$ is the optimal resource allocation of peer p from peer i in the network.

The flowchart of resource allocation scheme using PSO is shown in Fig. 1.

Fig. 1

Flowchart of the proposed scheme

The scheme has many distinct advantages such as: (i) it is conceptually simple and can be easily implemented in practice; (ii) it does not need to calculate the gradients of the objective function, especially when the gradients do not exist; and (iii) it can deal with very complicated optimization problems, such as discontinuous, nonconvex and nonlinear optimization problems.

5 Simulation results

Consider the following concave utility function u_pi (x_ip) = ξ_p log(x_ip + 1), where ξ_p is a private parameter which captures the valuation of obtained bandwidth of each peer p from others. This type of utility function represents the benefit of each peer from the download bandwidth of others. Choose the convex cost function $v_{pi} (x_{pi}) = η_{p} x_{pi}^{2}$ , where η_p is a parameter which describes the valuation of granted bandwidth of peer p. This choice of function represents the cost of each peer for granting its bandwidth to others.

We first consider a simple P2P network consisting of N = 50 peers which interact with each other. The peers have same link capacities of C_p =20Mbps. In order to ensure the convergence of the proposed scheme, the acceleration coefficients c1, c2 are set to 2, and the inertia weight factor range is set to [0.4, 0.9] as suggested in [45]. The swarm size is chosen to be 20.

We consider the impacts of parameters ξ_p and η_p on the performance of the scheme, and depict the evolution of aggregated utility for this network in Fig. 2. The scheme is gradually driven to a steady state where the utilization of the access link of each peer is approximately 100% as we observed in the simulation, since each peer tries to best utilize the bandwidth of others so as to maximize its own utility. From the results, we also observe that in the case with larger ξ_p/η_p utility functions peers obtain more resources (i.e., download bandwidth) and finally higher perceived utility. This is expected since our original problem is to maximize total utility of peers.

Fig. 2

Performance of the scheme for the P2P network with N = 50 peers

Now we investigate the impact of churn on the performance of our scheme. The simulation setup is identical with the one above except that the peers are not static, i.e., after a period of peer interaction some customers leave the network while other new peers join. Assume at iteration k = 300, 20 peers leave the network after completion of one service (e.g., download) and at iteration k = 600 new 10 peers join the network for requesting services. We depict the evolution of aggregated utility for the dynamic network in Fig. 3. We find that the algorithm behaves well after the transitional points of peer arrivals and departures and converges to the optimum within reasonable iteration times.

Fig. 3

Performance of the scheme with peer arrivals anddepartures

We also consider larger scale networks and investigate the performance of the proposed scheme. As shown in Fig. 4, we depict the evolution of aggregated utility for larger P2P networks with different number of peers. We observe that the size of the network (i.e., number of peers) have no significant impact on the convergence speed. The optimal total utility increases with the number of peers but, almost in all cases, the optimal value is achieved in the same number of iterations (e.g., 200 iterations). This is rather expected. The scheme is synchronously operated, and different peers run the separate optimization iterations in parallel. Thus the number of peers does not alter the convergence speed obviously.

Fig. 4

Performance of the scheme for P2P networks with different numbers of peers

Finally we investigate the influence of the swarm size on the performance of the scheme and depict the simulation results in Fig. 5. We observe that increasing the swarm size from 20 to 100 slightly improves the performance of the algorithm. In fact, recall that the performance in different scales of network shown in Fig. 4, the convergence speed mainly depends on algorithm parameters such as swarm size other than the number of peers.

Fig. 5

Performance of the scheme with different swarm sizes

6 Discussion

In our model formulation and discussion above we assume that each peer as client discriminates bandwidth allocation among other peers as servers, since it may download different file contents from different servers. Now we consider another option for utility function, which is coupled. That is, each peer p does not discriminate among its providers, and the utility function U_p (·) of peer p depends only on aggregated download bandwidth from other peers and on the total granted bandwidth to others. In other words, the peer does not care about the file content, what he concentrates on is only the total amount of bandwidth that he grants and receives. Then the utility function can be described as

$U_{p} (x_{p}, {\tilde{x}}_{p}) = u_{p} (\sum_{i : i \in N} x_{i p}) - v_{p} (\sum_{i : i \in N} x_{p i}) .$ (14) Here, benefit function u_p (·) and cost function v_p (·) have the respective features of concavity and convexity, which are similar to the corresponding parts of utility function (1).

Then in the simulation, consider the following concave utility function u_p (y_p) = ξ_p log(y_p + 1), y_p = ∑_i:i∈Nx_ip and the convex cost function $v_{p} = η_{p} z_{p}^{2}$ , z_p = ∑_i:i∈Nx_pi, where ξ_p and η_p are private parameters which represent the valuation of obtained and granted bandwidth of peer p, respectively. We also investigate the performance of our scheme with this new type of utility function in above several simulation setups, and find that similar results hold for the case when we choose the peer utility function (14). This is rather expected since our original problem is to maximize total utility of peers which can also be proved to be convex.

7 Conclusions

In today’s Internet-based social communities, P2P networks offer a popular, cheap, and effective way to distribute content, and have many advantages such as scalability, resilience, and effectiveness in coping with dynamics and heterogeneity. In P2P networks, each peer acts as the role of both client and server. As a client, each peer sends requests to other peers to download files and obtains resource allocation from them. As a server, each peer receives service requests from others and allocates its resources to them. Several schemes are proposed to encourage cooperation between peers and to achieve reasonable resource allocation.

In this paper, we consider bandwidth as the shared resource because it is the most commonly demanded resource in P2P networks and formulate the utility maximization model for bandwidth allocation among peers. The model is hard to resolve since there are coupled variables, that is, each peer has to make a decision that how much of its available bandwidth it will allocate to others and how much it will reserve for itself. Obviously, increasing the amount of bandwidth for uploads directly affects its download bandwidth and thus the perceived utility. We apply PSO to resolve the bandwidth allocation model, propose a heuristic scheme to achieve optimal bandwidth allocation, and illustrate the performance with simulation results in different network scenarios. The scheme behaves well and can achieve the global optimum within reasonable iterations.

Footnotes

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 71671159 and 71301139), the Humanity and Social Science Foundation of Ministry of Education of China (No. 16YJC630106), the Natural Science Foundation of Hebei Province (Nos. G2018203302 and G2016203236), the project Funded by Four Batch of Talents Program in Hebei Province, the project Funded by Hebei Education Department (Nos. BJ2017029, BJ2016063 and QN2018207), and the project Funded by Hebei Talents Program (No. A2017002108), the China Postdoctoral Science Foundation (No. 2018T110205).

References

Pacifici

, Lehrieder

and Dan

, Cache bandwidth allocation for P2P file-sharing systems to minimize Inter-ISP traffic, IEEE/ACM Transactions on Networking 24(1) (2016), 437–448.

Yan

, Gao

, Su

, Foh

C.H.

, Zhang

and Vasilakos

A.V.

, Caching strategy based on hierarchical cluster for named data networking, IEEE Access 5 (2017), 8433–8443.

Zhou

, Gao

, Xu

, Zhang

, Mumtaz

and Rodriguez

, Social big data based content dissemination in Internet of vehicles, IEEE Transactions on Industrial Informatics 14(2) (2018), 768–777.

F.Song, D. Huang, H. Zhou, H. Zhang and I. You, An optimization-based scheme for efficient virtual machine placement, International Journal of Parallel Programming 42(5) (2014), 853–872.

Khethavath

, Thomas

J.P.

and Chan-Tin

, Towards an efficient distributed cloud computing architecture, Peer-to-Peer Networking and Applications 10(5) (2017), 1152–1168.

Shao

, Jibiki

, Teranishi

and Nishinaga

, An efficient load-balancing mechanism for heterogeneous rangequeriable cloud storage, Future Generation Computer Systems 78 (2018), 920–930.

, Zhao

, Guan

, Zhang

and Muntean

, QoEdriven user-centric vod services in urban multihomed P2Pbased vehicular networks, IEEE Transactions on Vehicular Technology 62(5) (2013), 2273–2289.

K.Wang, H. Yin, W. Quan and G. Min, Enabling collaborative edge computing for software defined vehicular networks, IEEE Network (2018). doi: 10.1109/MNET.2018.1700364.

Lin

, Chung

P.-C.

and Fang

, P2P-iSN: A peer-to-peer architecture for heterogeneous social networks, IEEE Network 28(1) (2014), 56–64.

10.

Lin

, Li

and Wang

, Social commerce research: Definition, research themes and the trends, International Journal of Information Management 37(3) (2017), 190–201.

11.

Wang

E.K.

, Li

, Ye

, Yiu

S.M.

and Hui

L.C.K.

, A dynamic trust framework for opportunistic mobile social networks, IEEE Transactions on Network and Service Management 15(1) (2018), 319–329.

12.

Satsiou

and Tassiulas

, Reputation-based resource allocation in P2P systems of rational users, IEEE Transactions on Parallel and Distributed Systems 21(4) (2010), 466–479.

13.

Gupta

, Singha

and Singh

Y.N.

, Reputation based probabilistic resource allocation for avoiding free riding and formation of common interest groups in unstructured P2P networks, Peer-to-Peer Networking and Applications 9(6) (2016), 1101–1113.

14.

Goswami

, Parashari

G.S.

and Gupta

, Evolutionary stability of reputation based incentive mechanisms in P2P systems, IEEE Communications Letters 22(2) (2018), 268–271.

15.

, Liang

and Wu

, Utilizing layered taxation to provide incentives in P2P streaming systems, The Journal of Systems & Software 85(8) (2012), 1749–1756.

16.

Kang

and Yang

, Viewing experience optimization for peer-to-peer streaming networks with credit-based incentive mechanisms, Computer Networks 114 (2017), 67–79.

17.

Koutsopoulos

and Iosifidis

, A framework for distributed bandwidth allocation in peer-to-peer networks, Performance Evaluation 67(4) (2010), 285–298.

18.

Analoui

and Rezvani

M.H.

, Microeconomics-based resource allocation in overlay networks by using non-strategic beavihor modeling, Communications in Nonlinear Science and Numerical Simulation 16(1) (2011), 493–508.

19.

Neely

M.J.

and Golubchik.

, Utility optimization for dynamic peer-to-peer networks with tit-for-tat constraints, IEEE INFOCOM (2011), 1458–1466.

20.

Chen

, Ponec

, Sengupta

, Li

and Chou

P.A.

, Utility maximization in peer-to-peer systems with applications to video conferencing, IEEE/ACM Transactions on Networking 20(6) (2012), 1681–1694.

21.

Eger

and Killat

, Resource pricing in peer-to-peer networks, IEEE Communications Letters 11(1) (2007), 82–84.

22.

Kumar

, Altinkemer

and De

, A mechanism for pricing and resource allocation in peer-to-peer networks, Electronic Commerce Research and Applications 10(1) (2011), 26–37.

23.

and Sun

, A mechanism for resource pricing and fairness in peer-to-peer networks, Electronic Commerce Research 16(4) (2016), 425–451.

24.

, Sun

, E

C.-G.

and Shi

, A scheme of resource allocation and stability for peer-to-peer file-sharing networks, International Journal of Applied Mathematics & Computer Science 26(3) (2016), 707–719.

25.

Kang

and Wu

, Incentive mechanism design for heterogeneous peer-to-peer networks: A stackelberg game approach, IEEE Transactions on Mobile Computing 14(5) (2015), 1018–1030.

26.

Goswami

, Gupta

and Parashari

G.S.

, Reputation-based resource allocation in P2P systems: A game theoretic perspective, IEEE Communications Letters 21(6) (2017), 1273–1276.

27.

C.-L.

, Chen

D.-Y.

, Chang

Y.-H.

and Chen

Y.-W.

, Fair peer assignment scheme for peer-to-peer file sharing, KSII Transactions on Internet and Information Systems 4(5) (2010), 709–735.

28.

Nishida

and Nguyen

, A global contribution approach to maintain fairness in P2P networks, IEEE Transactions on Parallel and Distributed Systems 21(6) (2010), 812–826.

29.

Sherman

, Nieh

and Stein

, FairTorrent: A deficit-based distributed algorithm to ensure fairness in peer-to-peer systems, IEEE/ACM Transactions on Networking 20(5) (2012), 1361–1374.

30.

Kim

, Karrer

R.P.

, Park

J.-W.

and Kim

, A novel fairnessaware parallel download scheme, Peer-to-Peer Networking and Applications 9(1) (2016), 42–53.

31.

Creus-Mir

, Casadesus-Masanell

and Hervas-Drane

, Bandwidth allocation in peer-to-peer file sharing networks, Computer Communications 31(2) (2008), 257–265.

32.

Vakili

, Khorsandi

and Papaioannou

T.G.

, A selforganized mechanism of resource allocation in P2P systems, International Journal of Computational Intelligence Systems 5(6) (2012), 1148–1159.

33.

, Sun

and Li

Q.-L.

, Utility maximization for bandwidth allocation in peer-to-peer file-sharing networks, Journal of Industrial and Management Optimization (2018).

34.

Bertsekas

D.P.

Nonlinear Programming, Athena Scientific, (2003).

35.

Kennedy

and Eberhart

R.C.

, Particle swarm optimization, in Proceedings of IEEE International Conference on Neural Networks (ICNN 1995) 1995.

36.

Tang

, Xin

, Li

and Zhai

, Nonconvex resource control and lifetime optimization in wireless video sensor networks based on chaotic particle swarm optimization, Applied Soft Computing 13(7) (2013), 3273–3284.

37.

Niknam

and Zeinoddini

, Meymand and H. Doagou Mojarrad, A novel multi-objective fuzzy adaptive chaotic PSO algorithm for optimal operation management of distribution network with regard to fuel cell power plants, European Transactions on Electrical Power 21(7) (2011), 1954–1983.

38.

Melo

and Watada

, Gaussian-PSO with fuzzy reasoning based on structural learning for training a Neural Network, Neurocomputing 172 (2016), 405–412.

39.

Danesh

and Shirgahi

, A novel hybrid knowledge of firefly and PSO swarm intelligence algorithms for efficient data clustering, Journal of Intelligent and Fuzzy Systems 33(6) (2017), 3529–3538.

40.

Marini

and Walczak

, Particle swarm optimization (PSO). A tutorial, Chemometrics and Intelligent Laboratory Systems 149 (2015), 153–165.

41.

Konstantions

and Michael

M.N.

, Particle swarm optimization method for constrained optimization problems, in Slovakia, Euro-International Symposium on Computational Intelligence 2002.

42.

Shi

and Eberhart

R.C.

, A modified particle swarm optimizer, in Proceedings of the IEEE Conference on Evolutionary Computation Anchorage, USA (1998), pp 69–73.

43.

Shi

and Eberhart

R.C.

, Empirical study of particle swarm optimization, in Proceedings of the IEEE Conference on Evolutionary Computation

Washington, DC

1999 pp. 1945–1950.

44.

Liu

, Wang

, Jin

, Tang

and Huang

, Improved particle swarm optimization combined with chaos, Chaos, Solitons & Fractals 25(5) (2005), 1261–1271.

45.

Wiegand

R.P.

, An analysis of cooperative coevolutionary algorithms, George Mason University, Virgina, 2003.