Portal de Periódicos da CAPES

Biased contribution index: a new faster convergent index to maintain the fairness in peer‐to‐peer networks

2018; Institution of Engineering and Technology; Volume: 54; Issue: 20 Linguagem: Inglês

10.1049/el.2018.5649

1350-911X

Sateesh Kumar Awasthi, Yatindra Nath Singh,

Caching and Content Delivery

Electronics LettersVolume 54, Issue 20 p. 1174-1176 Information and communicationsFree Access Biased contribution index: a new faster convergent index to maintain the fairness in peer-to-peer networks S.K. Awasthi, Corresponding Author S.K. Awasthi awasthisk@nitj.ac.in Department of Electronics and Communication Engineering, Dr. B. R. Ambedkar National Institute of Technology, Jalandhar, Punjab, IndiaSearch for more papers by this authorY.N. Singh, Y.N. Singh orcid.org/0000-0002-7311-3116 Department of Electrical Engineering, Indian Institute of Technology, Kanpur, UP, IndiaSearch for more papers by this author S.K. Awasthi, Corresponding Author S.K. Awasthi awasthisk@nitj.ac.in Department of Electronics and Communication Engineering, Dr. B. R. Ambedkar National Institute of Technology, Jalandhar, Punjab, IndiaSearch for more papers by this authorY.N. Singh, Y.N. Singh orcid.org/0000-0002-7311-3116 Department of Electrical Engineering, Indian Institute of Technology, Kanpur, UP, IndiaSearch for more papers by this author First published: 01 October 2018 https://doi.org/10.1049/el.2018.5649Citations: 4AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract The free-riding and large difference between upload and download amount of resources is a fundamental problem in a peer-to-peer network. An incentive mechanism, which can be implemented in a distributed fashion, can solve this problem. Global contribution (GC) approach is one such mechanism, but its speed of convergence is slow. This letter proposes a new index named biased contribution index (BCI). It is proved that BCI always converges at a certain value. Simulation results show that it converges faster than the GC. Introduction Peer-to-peer (P2P) networks have changed the paradigm of resource sharing, where each peer can act as a client as well as a server. But lack of central control leads to the new challenges of free-riding and unfairness, i.e. large difference between upload and download amount of resources in each peer. In the recent years, different incentive mechanisms have been proposed by many authors to motivate the peers to share the resources [1-6]. Among these, global contribution (GC) [1] approach performs better, but its slow speed of convergence makes its implementation complex. In this Letter, we propose a similar approach with different index named biased contribution index (BCI). Mathematically, we will prove that the BCI always converges at a certain value. By comparing the simulation results of BCI with GC [1], we found that BCI also converges faster than the GC. Network model and BCI Let there be N peers in a P2P network. Peers share their resources with each other and their contribution is evaluated globally. A simple metric which can best reflect the contribution of a peer in the network could be the ratio of its total upload to the network to the total download from it. But to motivate the peers to upload more to the peers who contribute more and to download more from the peers who contribute less, we need to bias this ratio by some incentive factor. Let this incentive factor be, , for peer i. We define, the upload to download ratio (biased ratio) for this peer i as (1)Here, is a column vector containing incentive factors. is the share matrix; its element represents the amount of resource shared by peer i to peer j. is transpose of matrix . is the row vector with its entry as '1' and all other entries as zero. In order to give higher incentive to more contributing peers, let us define the incentive factor, , of peer i as a monotonically increasing function of biased ratio, i.e. (2)We call this incentive factor as BCI, as it is calculated using biased ratio. Now to start the process of sharing, we need to give some initial value of BCI to all the peers. Let us define a parameter to decide the initial value of BCI. Later we will see that the parameter makes the share matrix irreducible and acyclic, which will guarantee the convergence of BCI. The BCI is modified to include this parameter , as given below (3)Here, is the initial value of BCI, when neither upload nor download has happened at the node. Peers are allowed to take the resources from network only if their BCI is above a certain threshold value. Therefore, every peer will try to increase its BCI, so that it can get the required amount of resources whenever needed. It can be observed easily from (3) that a peer's BCI will be higher if (1) Its contribution is higher, (2) It shares more of its resources with higher contributing peers, (3) It takes more of the services from lower contributing peers. Therefore, intuitively, we can say that this metric can assure fairness in the whole network. The BCI of any peer is expressed in the terms of the BCI of other peers. In the network of N nodes, there will be N unknown BCI and N non-linear equations. So nothing can be said about the solution of these equations. In the next section, we will show that these equations can be solved by a suitable iterative function. Solution of BCI If , (3) can be written as (4)Here, and . Since , these sets of N equations can be written in the form of matrix as Here, is a diagonal matrix with its element as . In order to solve these set of equations, we propose the following lemmas. Lemma 1.The BCI vector Proof.When any peer i only takes the resources from the network and does not contribute anything, then and . In this case, BCI, , of peer i will be minimum and is given by, .When the peer i only contributes the resources to the network without taking anything, then and . In this case, BCI, , of peer i will be maximum and is given by, .In all other cases, it will be in between these values. Hence, □ Lemma 2.Let be non-negative, irreducible and acyclic matrix, then the BCI vector , in the above expression can be calculated by an iterative function where element of iterative function is . Proof.The element of iterative function is Let and be far from actual solution by and , respectively, then Using (4) or where is . Here, and are the row of matrices and , respectively. It can be observed about the matrices and that, and .The matrices and are derived from irreducible and acyclic matrices and , respectively, hence matrices and will also be irreducible and acyclic. Elements of vector are positive (see Lemma 1), so for non-negative matrix , matrices and will also be non-negative. Therefore, spectral radius of matrices and will be '1' and corresponding eigenvector will be (see [7, 9]).If , then . Hence (see Theorem 1, [8]), and if , then . Hence in this case, will decrease more rapidly till .Hence, by the aforementioned iterative function, we will finally converge to . □ Simulation results Considered the share matrix, as The number of iterations required to converge the BCI were estimated for two different values of . For , BCI in each step is shown in Table 1. We can see that it converges in seven iterations. For (see Table 2), it converges only in five iterations. Thus, impact of is clearly evident. Smaller the , faster the convergence of the estimate. Table 1. BCI for in each iteration i 1 2 3 4 0.6000 0.6000 0.6000 0.6000 0.7440 0.5000 0.5333 0.6174 0.7266 0.4823 0.5161 0.6373 0.7202 0.4861 0.5170 0.6379 0.7207 0.4870 0.5177 0.6371 0.7210 0.4869 0.5177 0.6370 0.7210 0.4868 0.5177 0.6370 0.7210 0.4868 0.5177 0.6370 Table 2. BCI for in each iteration i 1 2 3 4 0.8000 0.8000 0.8000 0.8000 0.8720 0.7500 0.7667 0.8087 0.8690 0.7465 0.7634 0.8124 0.8685 0.7468 0.7634 0.8124 0.8686 0.7468 0.7635 0.8124 0.8686 0.7468 0.7635 0.8124 Table 3. Number of iterations required to converge the BCI and GC [1] for different values of and Number of iteration required in GC [1] Number of iteration required in BCI , , , , , , , , , , , , , , , , , , , , , , , , We compared the number of iterations required for the convergence of the BCI with that of the GC [1]. In latter case, we have taken the different values of and as defined in [1]. Results are shown in Table 3. We observe that the number of iterations required for the convergence of BCI is always lesser than that of the GC. In order to compare the results for higher order of share matrix, we varied the number of peers in the network from 5 to 50. The results are shown in Fig. 1. It is evident from the figure that the average number of iterations required to converge the BCI and GC remains almost in the same range even if we increase the number of peers and BCI always converges faster than the GC. Fig 1Open in figure viewerPowerPoint Average number of iterations required for the convergence of BCI and GC [1] for different settings of node population Conclusion In this work, we proposed a new index called BCI to maintain the balance between total upload and download by a peer in the network. We proved that the BCI can be calculated by iterative method, therefore, it can be implemented in a distributed fashion. We compared our index with another existing index GC [1]. With the help of a numerical example, we have shown that our index converges in lesser number of iterations. References 1Nishida, H., Nguyen, T.: 'A global contribution approach to maintain fairness in P2P networks', Trans. Parallel Distrib. Syst., 2010, 21, (6), pp. 812– 826 (https://doi/org/10.1109/TPDS.2009.122) 2Feldman, M., Lai, K., Stoica, I. et. al.,: ' Robust incentive techniques for peer-to-peer networks'. Proc. Fifth ACM Conf. Electronic Commerce, New York, NY, USA, May 2004, pp. 102– 111 3Garbacki, P., Epema, D.H.J.: ' An amortized tit-for-tat protocol for exchanging bandwidth instead of content in P2P networks'. First Int. Conf. Self-Adaptive and Self-Organizing Systems, Cambridge, MA, USA, July 2007, pp. 119– 228 4Lian, Q., Peng, Y., Yang, M. et. al.,: 'Robust incentives via multi-level tit-for-tat', Concurrency Comput. Pract. Exp., 2008, 20, pp. 167– 178 (https://doi/org/10.1002/cpe.1190) 5Mol, J.J.D., Pouwelse, J.A., Epema, D.H.J. et. al.,: ' Give-to-get: free-riding resilient video-on-demand in P2P systems'. Proc. Multimedia Computing and Networking, San Jose, CA, USA, January 2008, pp. 681804– 1–681804–8 6Sherman, A., Nieh, J., Stein, C.: 'Fairtorrent: a deficit-based distributed algorithm to ensure fairness in peer-to-peer systems', IEEE/ACM Trans. Netw., 2012, 20, (5), pp. 1361– 1374 (https://doi/org/10.1109/TNET.2012.2185058) 7Seneta, E.: ' Non-negative matrices and markov chains' ( Springer-Verlag, New York, 1981, 2nd edn.) 8Awasthi, S.K., Singh, Y.N.: ' Absolute trust: algorithm for aggregation of trust in peer-to-peer network'. Available at: http://arxiv.org/abs/1601.01419 9Serre, D.: ' Matrices theory and applications' ( Springer-Verlag, New York, NY, USA, 2002) Citing Literature Volume54, Issue20October 2018Pages 1174-1176 FiguresReferencesRelatedInformation