# Simulating Network Coding for Accelerating Tit-for-Tat in Peer-to-Peer Content Sharing

Ákos Ludányi, Tamás Lukovszki, Péter Ekler

► To cite this version:

Ákos Ludányi, Tamás Lukovszki, Péter Ekler. Simulating Network Coding for Accelerating Tit-for-Tat in Peer-to-Peer Content Sharing. 18th European Conference on Information and Communications Technologies (EUNICE), Aug 2012, Budapest, Hungary. pp.408-411, 10.1007/978-3-642-32808-4_37 hal-01543140

HAL Id: hal-01543140

https://inria.hal.science/hal-01543140

Submitted on 20 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Simulating network coding for accelerating Tit-for-
Tat in peer-to-peer content sharing¹

Ákos Ludányi, Tamás Lukovszki, Péter Ekler

18th EUNICE Conference on Information and Communications Technologies
29-31 August 2012, Budapest, Hungary
akos.ludanyi@aut.bme.hu, lukovszki@inf.elte.hu,
peter.ekler@aut.bme.hu

**Abstract.** The deterministic network coding has several advantages over random network coding methods, like lower communication overhead and faster linear independence check. We would like to create a P2P content sharing simulation environment, where nodes communicate with deterministic network coding to observe the different properties of deterministic source coding. Our simulator is based on the Peersim generic P2P simulation framework. We examine the diversity of block combinations, as this property is the key for increasing the P2P network reliability.

**Keywords:** network coding, P2P, deterministic network coding, content sharing, network simulation

**Introduction**

In network coding the nodes sends linear combinations of data. This technique has
several benefits: better bandwidth usage, faster download speed, increase fault
tolerance, etc. For accelerating tit-for-tat piece exchange in BitTorrent like systems
Locher et al. [1] proposed special network coding at the seeders. The deterministic
network coding was introduced in [2] as an alternative solution. The authors used
special coding vectors, such that any M different coding vectors form a Vandermonde
matrix, where M is the number of blocks in a segment. It is a well-known property of
a Vandermonde matrices over field (finite or infinite) is that those Vandermonde
matrices are non-singular (see e.g. [3] Ch. 4 Lemma 17), i.e. after receiving M
different coded blocks the decodeability is guaranteed. We would like to create a P2P
content sharing simulation environment to measure the different properties of
deterministic network coding.

¹ Acknowledgment: This work is connected to the scientific program of the " Development of quality-oriented and harmonized R+D+I strategy and functional model at BME" project. This project is supported by the New Hungary Development Plan (Project ID: TÁMOP-4.2.1/B-09/1/KMR-2010-0002, TÁMOP-4.2.1/B-09/1/KMR-2010-0003).
## Related work

Network coding is typically used in systems where robustness is a key requirement. This technique allows handling the failures of nodes and links efficiently. In [4] the authors propose a distributed scheme for practical network coding. The result of their research is a practical system for network coding that is robust to random packet loss and delay as well as robust to any changes in the network topology or capacity due to joins, leaves, node or link failures, congestion, and so on. Another researches [5, 6] focuses on linear network coding, they have proven that linear coding suffices to achieve the optimum in multicast environments.

In order to bridge theory with practice, in [4] the authors discuss about practical issues and proposed a distributed scheme that does not need centralized need knowledge of the network topology. They showed that the proposed new architecture for wireless mesh networks largely increased network throughput. Another research [7] shows different ways of cooperation in large network environment, where network coding can also be applied efficiently. In our research we focus on deterministic network coding and we propose a simulator that can be used in different measurements and research areas.

## Simulation environment

For our simulation we have used PeerSim [8], which is an open source simulator.

<figure><img src="image_2.png" /><figcaption>Fig. 1. a) Segment finish timing histogram b) average segment download speed as a function of uploaded blocks</figcaption></figure>

We have done some simulations to test, weather our tit-for-tat implementation is working as expected in our simulator. There were 1000 nodes in the network. The upload bandwidth of a node was randomly determined by Gaussian distribution with 5 block/sec expected value and variance 4. The maximum download speed was 20 block/sec. There were 8 segments each segment consisted of 8 blocks. The coding was done over $GF(p)$, where $p = 2^{31} - 1$ (the largest 31 bit prime). We have measured the elapsed time between the first block arrival and the last block arrival. With tit-for-tat, we expect that peers, which uploaded more, will receive segments
faster. On Fig. 1. b), we can see the average block download time as a function of upload blocks. As one would expect, nodes, which uploaded more, are usually downloading faster. The number of samples line shows, how many nodes have uploaded the given amount of blocks. As the number of samples decreases, the average download time becomes noisier.

A segment consists of *M* blocks. We send linear combination of blocks to other nodes, the combination is described by the coding vector. To retrieve the original data, a node needs exactly *M* linearly independent blocks. As discussed in [9] rare block problem can occur in BitTorrent (that does not combine blocks), the authors suggested using network coding to avoid the problem. This way, the number of possible coding vector is exponentially increased, so the possibility of a rare piece is significantly decreased, by using more distinct coding vectors. Note that we only require any set of *M* linearly independent block for decoding.

Assume the segment consists of *N* blocks, let *T* denote the number of different block combinations. We assume that the blocks are distributed uniformly at random in the network, each block has the same frequency. Let *p* be the probability that (all instances of) a block combination becomes unavailable in the network. Then if at most *N*−1 different block combinations are available in the network, the nodes will not be able to reconstruct the original data. Let *P* be the probability of the event that nobody can reconstruct the original data. Then:

$$P = \sum_{i=0}^{N-1} \binom{T}{i} (1-p)^i p^{T-i} \quad (1)$$

*P* is binomially distributed. It is well known if *N* is large enough the binomial distribution can be approximated with normal distribution: $N(Tp, Tp(1-p))$. The tail of this distribution decreases exponentially if *T* increases. Fig. 2. a) shows, how *P* decreases, when the diversity (*T*) is increased. When *N* = *T* (this is also the case without network coding), if a single block disappears from the network, the file can not be downloaded anymore. In our simulation *N* = 20. By increasing the diversity, we see that even if *p* is a (high) constant (0.5), *T* = 4*N* results in a system, where the peers almost surely can reconstruct the file. Our simulations support this dependence.

Using RLNC [10] based network coding a node can recombine the received blocks, and forward them to other nodes immediately, thus probably increasing the number of different coding vectors in the network. On the other hand the deterministic network coding cannot recombine the received data immediately, because the sum of two rows from the Vandermonde matrix is not a valid row of any Vandermonde matrix. So a node has to wait till it can decode the data. However, until the node cannot decode, it can still forward the received blocks without recombining them, unfortunately the diversity of blocks in the network will not increase.
We have created a simulation environment, for measuring the diversity of coded blocks in the network. In the simulation each node was connected randomly to other 5 nodes. We used a single segment for measurement. The network consisted of 1000 nodes, the examined segment consisted of 20 blocks. As the number of seeders increases, the diversity is also increasing. We can say the connection between them is linear.
<figure><img src="image_3.png" /><figcaption>Fig. 2. a) *P* as a function of *T*, *N* = 20 b) Diversity of combined blocks in the network as a function of time.</figcaption></figure>

Conclusions and future work

We have created a P2P content sharing simulator that uses deterministic network coding based on a well-known P2P simulator framework. We have simulated how the diversity is affected by deterministic network coding. Currently all nodes stay active during the simulation, we are planning to measure, how the diversity is influenced, when nodes leave the network.

Reference

1. Locher, T.; Schmid, S.; Wattenhofer, R.;, "Rescuing Tit-for-Tat with Source Coding," Peer-to-Peer Computing, 2007. P2P 2007. Seventh IEEE International Conference on, vol., no., pp.3-10, 2-5 Sept. 2007 doi: 10.1109/P2P.2007.10

2. Balaton, A.; Lukovszki, T.; Agocs, A.;, "A new deterministic source coding method in peer-to-peer systems," Computational Intelligence and Informatics (CINTI), 2011 IEEE 12th International Symposium on, vol., no., pp.403-408, 21-22 Nov. 2011

3. F. J. McWilliams and N. J. A.Sloane: The Theory of Error-Correcting Codes. North-Holland, Amsterdam 1977.

4. P. A. Chou, Y. Wu, K. Jain, "Practical Network Coding", Microsoft Research, 2003.

5. R. Roetter, M. Medard, „An algebraic approach to network coding”, Networking, IEEE/ACM Transactions on, vol.11, no.5, pp. 782-795, Oct. 2003.

6. S.-Y.R Li, R.W. Yeung, N. Cai, „Linear network coding”, Information Theory, IEEE Transactions on, vol.49, no.2, pp. 371-381, Feb. 2003.

7. F. H. P. Fitzek, M. D. Katz, "Cooperation in Wireless Networks: Principles and Applications", Springer, ISBN 978-1-4020-4710-7, 2006.

8. PeerSim, http://peersim.sourceforge.net/

9. Ekler, P.; Lukovszki, T.; Nurminen, J.K.;, "Extending mobile BitTorrent environment with network coding," Consumer Communications and Networking Conference (CCNC), 2011 IEEE, vol., no., pp.529-530, 9-12 Jan. 2011

10. Ho, T.; Medard, M.; Koetter, R.; Karger, D.R.; Effros, M.; Jun Shi; Leong, B.;, "A Random Linear Network Coding Approach to Multicast," Information Theory, IEEE Transactions on, vol.52, no.10, pp.4413-4430, Oct. 2006