## P2PSP (Peer-to-Peer Straightforward Protocol)

December 1, 2019

Abstract

P2PSP (Peer-to-Peer Straighforward Protocol) is an application-layer multicast protocol that provides real-time broadcasting of media streams in the Internet. The peers relay the stream split into chunks, using an UDP push communication model. The data ﬂow is controlled by the source(s) of the stream, and the peers use a congestion control method based on the relaying of chunks, only when chunks are received. The topology of the overlay is dynamic and adapts to the requirements of the physical topology and startup latency required, which is proportional to the maximum number of peers in the P2P overlay. In absence of connectivity restrictions (such as the imposed by NATs) and selﬁsh peers, all peers have an input/output ratio close to 1. P2PSP can use IP Multicast communications, when available.

### Notation

Cursive is used the ﬁrst time a P2PSP-related term/concept is introduced, and for key concepts or ideas.

### Introduction

P2PSP has a modular design organized in sets of rules, where each module is especialized in implementing diﬀerent functionalities.

### 1 LBS (Load Balancing Set)

Note: Finished but not implemented.

LBS describes the bootstrap procedure that peers must follow in order to join the overlay. LBS is an standalone set of rules, and it is compatible with any other set.

P2PSP supposes that there is a collection of streams (usually, video) that are broadcasted in parallel.1 The streams are available at one or more2 streaming servers, and each stream has a diﬀerent Universal Resource Locator, usually expressed as a Web address with the structure:

http://server/mount_point

Notice that a server can be serving several channels.

P2PSP does not perform data-ﬂow control over the stream. The transmission bit-rate between P2PSP entities is controlled by the servers (Icecast servers, for example), which provides the stream to the P2PSP teams. Fig. 1 shows an example of a streaming overlay where several servers relay a set of channels generated by a set of source-clients, directly or through other servers. As can be seen, a listener (which usually plays the stream) can be replaced by a splitter, a P2PSP entity that sends the received stream (a single channel) to a set of P2PSP peers.

In a pure CDN system, users request the channels directly to the servers. Unfortunately, this simple procedure has a drawback: normally, users do not know the load nor the distance to the servers. This problem can be solved by using a load balancer. The listeners, which know the URL of the required channel, connects ﬁrst to a load balancer which redirects them (with an HTTP 302 code) to a suitable server.

This idea can be extended to minimize the response time of hybrid CDN/P2PSP structures. When a user (who knows an URL of the channel) runs a local peer, it provides to his peer the URL of the channel (the URL pointing to a server and a mount point). Then, the peer (as any other listener does) contacts a load balancer which in this case sends a list of splitters which are broadcasting the channel.3 Then, the peer tries to connect with all the splitters in parallel, and the ﬁrst establised connection determines the selected splitter (the rest of connections are closed). If only those splitters with space in their teams answer to the peer, this procedure should select the “nearest” splitter for the peer in terms of response time.

For the case of the incorporation of new splitters to the network, the procedure is similar. A new splitter (which is instantiated knowing an URL of a channel) contacts the load balancer which returns a list of servers and peers, which are serving the channel. Then, the splitter tries to connect with all of them in parallel, and the ﬁrst successfull connection is ﬁnally selected.4

Using the idea of the extended load balancer, when a player (listener) connects to it, if there is a local peer running in the same host or the same private network that the player, the balancer will redirect the player to the local peer.

Finally, it is compulsory that all the splitters associated to the same channel to generate exactly the same chunks (content and header).

### 2 DBS (Data Broadcasting Set)

Note: Finished and implemented.

Note: DBS is the most basic set of rules. The rest of sets extends or modify its functionality.

DBS provides ALM of a media stream in unicat environments. The media is sent by a streaming server (which is not related to P2PSP), and it is received by a splitter. (see Sec. 1) The splitter divides the stream into a sequence of chunks of data, and relays them to a team of peers, following a round-robing schema. Each peer of a team gathers the chunks from the splitter and the rest of peers of the team, and sends them to at least one player.Peer should run even if no player(s) are connected to it. Peers are organized in a unstructured topology (all peers perform the same tasks).

#### 2.1 Team deﬁnition and types of peers

A team is a set of one or more peers (referenced by their end-points) that share the same stream. By deﬁnition, in a team at least one peer is a monitor. Monitors are deployed by the overlay administrator to check diﬀerent aspects of the broadcasting, such as, the expected quality of the rendered video at the peers or the estimated latency.

The number of peers (normal peers and monitors) in a team has a maximum ${N}^{\ast }$ (see Tab. 1). This parameter has an signiﬁcative impact on the maximum latency of the protocol (see Sec. 2.4), and is usually deﬁned by the administrator of the overlay.

 Parameter Meaning ${N}^{\ast }$ : Maximum number of peers in a team $T$ : Average round-time ${l}^{\mathrm{chunk}}$ : Chunk length $B$ : Buﬀer size, in chunks, used by the peers ${B}^{\prime }$ : Length of the list of the last ${B}^{\prime }$ peers served by the splitter $D$ : Diameter of the ﬂooding tree ${L}^{\ast }$ : Maximum allowed number of lost chunks $M$ : Number of monitors $R$ : Average bit-rate of the media $H$ : Pre-fetching horizon $P$ : The list of peers in the team Variable $N$ : Number of peers in the team $L$ : Number of lost chunks ${t}_{c}$ : Chunk time ${t}_{r}$ : Round time ${t}_{b}$ : Buﬀering time $\Delta {t}_{b}$ : Protocol (buﬀering) jitter ${t}_{p}$ : Physical (network) latency $\Delta {t}_{p}$ : Physical jitter ${t}_{s}$ : Start-up time ${i}_{p}$ : The played chunk index

Table 1: Nomenclature used in DBS.

#### 2.2 Feeding the team

The splitter divides the stream into chunks of constant length $C$, and sends exclusively each chunk to a diﬀerent origin5 peer, using a round-robin schema. Chunks are enumerated to distinguish them, and this information is transmitted as a part of a chunk header.

A round is deﬁned as the process of transmitting $N$ diﬀerent chunks from the splitter to a team of $N\le {N}^{\ast }$ peers (therefore, all the peers of the team are origin of a diﬀerent chunk, in each round). For a team of size $N$, the average round-time can be estimated as

 $T=N{t}^{\mathrm{chunk}},$ (1)

where ${t}^{\mathrm{chunk}}$ is the chunk time, deﬁned as

 ${t}^{\mathrm{chunk}}=\frac{{l}^{\mathrm{chunk}}}{R},$ (2)

where ${l}^{\mathrm{chunk}}$ is the length of the chunks (all the chunks are split with the same length) and $R$ is the average transmission bit-rate, that should match the average bit-rate of the stream in order to achieve a seamsless playing.

#### 2.3 Joining a team

After connecting with a splitter6 , incoming peers request (using a reliable communication) to the splitter the current list of peers in the team $T$. To minimize the joining time, the peer sends a $\left[\mathtt{hello}\right]$ message to each other peer of the team, in parallel with the reception of the list. When a peer of the team receives a $\left[\mathtt{hello}\right]$, it adds the sender of the message to the team list7 and to a jagged array of peers called $\mathtt{f}\left[\right]$ (see $\text{f[]}$ in peer.py). If a peer ${P}_{i}$ has an entry $\mathtt{f}\left[{P}_{j}\right]=\left\{{P}_{k}\right\}$, then each chunk received by ${P}_{i}$ and originated at ${P}_{j}$ will be forwarded to ${P}_{k}$. When an incoming peer ${P}_{i}$ has received the list of peers, its forwarding table has been initialized to $\mathtt{f}\left[{P}_{i}\right]=\left\{T\setminus {P}_{i}\right\}$. Notice that, as long as the forwarding table contains this information, all the chunks received from the splitter will be forwarded to the rest of the team, directly (in one single hop/chunk). So, in absence of communication constraints, the team will be organized as a full-connected overlay (see Fig. ??).

The splitter, in an inﬁnite loop: (1) listens to the incoming peers, (2) sends to them the list of peers of the team, (3) includes the incoming peer to the list, and (4) send a copy of the stream to the team using a round-robing, as a sequence of chunks. Notice that only those peers that are in the list of peers of the splitter are considered to be in the team served by such splitter.

#### 2.4 Buﬀering chunks

In order to hide the jitter generated by the physical network and the protocol itself, peers need to store the received chunks in a buﬀer during a period of time, before sending them to a player. A chunk with number $x$ is inserted in the position $\left(x\phantom{\rule{0.33em}{0ex}}\mathit{mod}\phantom{\rule{0.33em}{0ex}}2B\right)$ of the buﬀer, where $B$ is the maximum number of chunks that the buﬀer stores before start playing the ﬁrst chunk. In a peer’s life, $B$ is a constant speciﬁed by the user, but it is not compulsory that all peers of a team use the same buﬀer size.

The buﬀer is implemented as a circular array of $2B$ chunks, that is ﬁlled with up to $B$ chunks during the buﬀering time ${t}^{\mathrm{buﬀer}}$. Such time is the main component of the start-up time ${t}^{\mathrm{start-up}}$ experienced by users. The oldest chunk in the buﬀer is sent to the player each time a new chunk is received.

#### 2.5 Buﬀering time estimation

The start-up time ${t}_{l}$ is the latency that the end-user experiments during the redering of the media. ${t}_{l}$, deﬁned as

 ${t}_{l}={t}_{p}+{t}_{b},$ (3)

is the sum of the physical delay ${t}_{p}$ and the buﬀering time ${t}_{b}$, where

 ${t}_{b}=B{t}_{c},$ (4)

is the time that has elapsed since the peer receives two chunks distanced $B$ positions in the buﬀer, being $B$ the buﬀer size (in chunks), and ${t}_{c}$ the chunk time (considering ${t}_{c}$ a constant8 ). In other words, the buﬀering time is the delay in the rendering of the media required to expect a seamless playing. Notice that Eq. 4 does not assume that the chunks completely ﬁll the buﬀer during the buﬀering time.

To minimize ${t}_{l}$, ${t}_{p}$ and ${t}_{b}$ should be as small as possible. How to minimize ${t}_{p}$ is out of the scope of this discussion. However, to minimize ${t}_{b}$, we can reduce ${t}_{c}$ and/or $B$, but these actions carry two main drawbacks. On the one hand, ${t}_{c}$ should be large enough to reduce the overhead of the headers used by the transport protocol. On the other hand, if $B$ is too small (for instance $B), the peer will not have enough space to buﬀer all the chunks of a round, causing that some incoming chunks overwrite others before they can be played. This problem also arises even if $N\le B<2N$, because the maximum protocol jitter, ${\Delta }^{\ast }{t}_{b}$, that a chunk can experiment is the sum of the jitter produced by the splitter for this peer, that can as high as $N{t}_{c}$, and the jitter produced by the ﬂooding of the chunk to the rest of the team, that also can be has high as $N{t}_{c}$. Notice that this jitter is the same for two extreme topologies of the overlay: (1) a full-connected mesh (Fig. ??), or (2) a ring (Fig. ??), when the chunks travel only in one direction9 . Therefore, in the case of a full-connected mesh, peers have to use a

 $B\ge 2{N}^{\ast }$ (5)

in order to avoid the loss of chunks due to high $\Delta {t}_{p}$. We will refeer to $B=2{N}^{\ast }$ as the critical buﬀer size.

Lets analyze the buﬀering time ${t}_{b}$ in two interesting cases. Lets suppose that the number of the ﬁrst received chunk is ${x}_{1}$ and that the rest of chunks of the buﬀer of size $B$ are received10 , being the chunk ${x}_{1+B}$ the last one (the best scenario). In this case, the ${t}_{b}$ can still be estimated by Eq. 4. Lets imagine now that after receiving ${x}_{1}$ the chunk ${x}_{1+B}$ is received (chunks ${x}_{2},\cdots {x}_{1+B-1}$ have been lost or delayed too much), and the playing starts (probably, with severe artifacts). In this case, ${t}_{b}$ also corresponds to Eq. 4, because the chunk ${x}_{1+B}$ was generated $B$ chunk times after ${x}_{1}$, and we cannot wait more during the buﬀering time if we want to dimension ${t}_{b}$. After considering these two extreme situations, we can deduce that the start-up time ${t}_{s}$ does not depend on the chunk loss ratio during the buﬀering-time (for loss ratios smaller than one), but only on $B$, ${t}_{c}$ and ${t}_{p}$.

Finally, notice that the time that passes from an incoming peer request to join a team to a splitter until it accepts the peer, and the buﬀering time that the player can require, have not been considered in this discussion. However, both times should be, in general, signiﬁcantly lower than ${t}_{b}$, that in the case of P2PSP corresponds to the ${t}_{s}$ that end-users experiment.

#### 2.6 Chunk ﬂooding

DBS is a push-based protocol. When a peer receives a chunk, it can be retransmitted to a large number of neighbors, depending on the number of peers in its forwarding table. Therefore, even if the chunk rate is controlled by the streaming servers, some kind of ﬂow control must be performed by the peers in order to reduce network congestion while the overlay is ﬂooded.

The congestion may be avoided following the next idea: only if I have received a chunk, I send (not necessary to the sender) a chunk (and not necessary the received chunk). In a fully connected overlay (see Fig. ??), this allows to control the data ﬂow. However, in more realistic scenarios, where the physical media imposes interconnection constraints (such as those generated by ﬁrewalls and symmetric NATs), peers could not be directly “connected” with the rest the team. Therefore, if the splitter follows a pure round-robin strategy, some peers will send more chunks than they receive, as happens for example in Fig. ??. In such scenarios, the simple idea of sending a chunk for each received one does not work.

Fortunately, the initial congestion algorithm can be adapted to handle a variable connectivity degree (also called neighborhood degree). Each peer uses a table of lists, $\mathtt{p}\left[\right]$, indexed by the neighbor’s end-points, where each list references the indexes in the buﬀer of those chunks in the current peer that must be transmitted to the corresponding neighbor the next time such neighbor is selected in the ﬂooding process. For example, if $\mathtt{p}\left[{P}_{x}\right]=\left\{11,22\right\}$, chunks found at positions $11$ and $22$ of the buﬀer have to be sent to peer ${P}_{x}$.

Notice that using this procedure, more than one chunk can be sent to a neighbor in a transmission burst. This could congest the physical devices in very unbalanced overlays (see the Fig. ??), although these cases are rare. As an advantage, all the chunks of the burst travel between the two same hosts when a burst is produced, which usually increases the performance of the layer-3 routing. Additionally, several chunks could be grouped in one single packet, reducing the protocol overhead.

Note: An example of the temporal evolution of a team using the ﬂooding algorithm has been described in the Figures 3 to 7.

#### 2.7 Routes discovery and topology optimization

Chunks can be lost under bandwidth and buﬀering time constraints. A chunk is lost when it is time to send it to the player, i.e. when it is pointed by ${i}_{p}$, and the chunk has not been received. Therefore, when a peer realizes that a chunk has been lost, nothing can be done to recover it.

In order to mitigate this drawback, peers can pre-fetch “potentially lost” chunks at the buﬀer position ${i}_{p}+H$, where $H\ge 0$ is the pre-fetching horizon. Setting $H=0$, the pre-fetching is disabled and only those chunks that really are lost will be “requested”11 . On the contrary, the higher the $H$, the more aggressive the pre-fetching is.

For each (potentially, if $H>0$) lost chunk with number $\text{lost_chunk_number}$, peers send a $\left[\mathtt{request}\phantom{\rule{0.33em}{0ex}}\text{lost_chunk_number}\right]$ message to a random12 peer of the team. When a peer ${P}_{i}$ receives a request message from ${P}_{j}$, ${P}_{i}$ adds ${P}_{j}$ to $\mathtt{f}\left[{P}_{k}\right]$, where ${P}_{k}$ is the origin peer of the chunk stored in the position $\left(\text{lost_chunk_number}\phantom{\rule{0.33em}{0ex}}\mathit{mod}\phantom{\rule{0.33em}{0ex}}2B\right)$ of ${P}_{i}$’s buﬀer, in case this chunk has been received (otherwise, the request is ignored because ${P}_{i}$ cannot determine ${P}_{k}$). Therefore, if the requested chunk $\text{lost_chunk_number}$ is in ${P}_{i}$’s buﬀer, ${P}_{i}$ will start forwarding the chunks originated at ${P}_{k}$ to ${P}_{j}$.

As a consequece of the request messages, redundant routes can be created. Therefore, some chunks could be received more than once. To avoid future chunk duplicates, peers send pruning messages to those peers that send duplicates. The receiver ${P}_{i}$ of a $\left[\mathtt{prune}\phantom{\rule{0.33em}{0ex}}\text{duplicate_chunk_number}\right]$ message received from ${P}_{j}$, removes ${P}_{j}$ of $\mathtt{f}\left[{P}_{k}\right]$, where ${P}_{k}$ is the origin peer of the chunk stored in the position $\left(\text{lost_chunk_number}\phantom{\rule{0.33em}{0ex}}\mathit{mod}\phantom{\rule{0.33em}{0ex}}2B\right)$ of ${P}_{i}$’s buﬀer.

Now, we can deﬁne with more accuracy the neighborhood degree (see Sec. 2.6) as the number of diﬀerent destination peers for each possible origin that a peer forwards. For example, if a peer ${P}_{i}$ forwards chunks from the origin ${P}_{i}$ to $10$ neighbors, the neighborhood degree of ${P}_{i}$ for itself is $10$, and if the peer ${P}_{i}$ also forwards chunks from an origin ${P}_{j}$ to $5$ neighbors, the neighborhood degree of ${P}_{i}$ for the origin ${P}_{j}$ is $5$.

Initially, peers have, for the chunks originated in themselves, a neighborhood degree equal to $K=N-1$, and the $\mathtt{f}\left[\right]$ table has only one entry. As long as the topology of the overlay is optimized by the route discovery algorithm, peers insert new entries in the forwarding table and the length of this entry tend to be smaller. Therefore, the lists of forwarded peers for each origin changes with the processing of the requesting and pruning messages.

#### 2.8 Leaving a team

An outgoing peer must to: (1) say $\left[\mathtt{goodbye}\right]$ to the splitter and the neighbor peers (in this order), (2) relay any pending (received but yet not sent) chunks, and (3) wait for a $\left[\mathtt{goodbye}\right]$ from the splitter. In case of timeout13 , the leaving procedure is reset a number of times.

When a peer ${P}_{i}$ receives a $\left[\mathtt{goodbye}\right]$ from ${P}_{j}$, ${P}_{i}$ removes ${P}_{j}$ from all the lists (all the possible origins) of $\mathtt{forward}\left[\right]$ table. The splitter removes the outgoing peer from the list of peers as soon as the $\left[\mathtt{goodbye}\right]$ is received, to avoid sending chunks to it.

#### 2.9 Free-riding control at the splitter

Monitor peers (which are trusted peers) complain to their splitter with a $\left[\mathtt{lost}\phantom{\rule{0.33em}{0ex}}\text{lost_chunk_number}\right]$ for each lost chunk that they detect. The splitter only considers these type of messages if they come from a monitor.

The splitter remembers which chunk, of a list of the last ${B}^{\prime }>{N}^{\ast }$ transmitted chunks, was sent to each origin peer of the team. The splitter also counts of lost chunks for each peer of the team. The corresponding counter is incremented for each lost chunk reported by a monitor and, if the counter of a peer goes over a threshold ${L}^{\ast }$, the corresponding peer is removed from the list of peers, and the rest of counters are reset. Notice that the smaller the ${L}^{\ast }$, the higher the belligerence with the selﬁsh peers. The selection of ${L}^{\ast }$ should be also proportional to the number of monitor peers $M$.

#### 2.10 Free-riding control at peers

Peers check the sending activity of the rest of peers of the team, with the objective of stop sending chunks to selﬁsh peers. Such activities are represented by an array of counters, indexed by the origin of the received chunks. For each chunk received by ${P}_{i}$ and originated at ${P}_{o}$, ${P}_{i}$ increases $\mathtt{activity}\left[{P}_{o}\right]$. In each new round (when a chunk is received from the splitter), ${P}_{i}$ decreases $\mathtt{activity}\left[{P}_{o}\right]\forall {P}_{o}\in T$, and if $\mathtt{activity}\left[{P}_{o}\right]<{L}^{\ast }$ (in this case, ${L}^{\ast }$ is the maximum allowed number of chunks that a peer can “lost” with other peer), no more chunks nor control messages will be delivered to ${P}_{o}$. However, notice that this last consequence can be reversed if ${P}_{o}$ resumes its sending activity with ${P}_{i}$.

### 3 ACS (Adaptive Capacity Set)

Note: Unﬁnished. This set is incompatible with FCS (see Sec. 4).

ACS relaxes the peer’s uploading requirements imposed by DBS. ACS is based on the idea of using the information that the splitter knows about the number of chunks that each peer has lost (see Sec. 2.10), to send to the more reliable peers a higher number of chunks. In other words, ACS adapts the round-time of each peer to its capacity, in such a way that the higher the capacity, the lower the round-time. Notice that ACS only aﬀects the behavior of the splitter.

ACS should be used if we want some peers to contribute with the uploading capacity than others cannot provide. A possible situation could be when we want to mix the CS and P2P models, sending more chunks from the contents provider’s hosts to the users’s peers, with the objective, for example, of incrementing the QoS. Because monitors should lost a minimum number of chunks (supposedly the hosts of the contents provider should have enough capacity), the ratio of chunks emitted by the contents provider’s hosts can be controlled if a high enough number of monitor peers (the more monitors, the higher the ratio).

### 4 FCS (Free-riding Control Set)

Note: Finished but not implemented. This set is incompatible with ACS (see Sec 3).

FCS (Free-riding Control Set) modiﬁes the functionality of DBS.

DBS does not imposes any control over the grade of solidarity of the peers. This means that selﬁsh peers (or simply peers with reduced upload capacity) can stay in the team thanks to the generosity of the rest of peers, even if they never achieve to deliver a chunk to any peer of the team. FCS precludes this possible behavior by imposing a minimum degree of solidarity between neighbor peers.

To know the level of solidarity between neighbor peers, each peer uses a table of chunk debts, $\mathtt{debt}\left[\right]$. Every time a peer ${P}_{i}$ sends a chunk to ${P}_{j}$, ${P}_{i}$ increments $\mathtt{debt}\left[{P}_{j}\right]$, and decrements $\mathtt{debt}\left[{P}_{j}\right]$ when ${P}_{i}$ receives a chunk from ${P}_{j}$.

Using DBS, peers forward chunks to their neighbors using a simple round-robing scheduler. FCS modiﬁes this behavior:

1. The $\mathtt{pending}\left[\right]$ table is run in the order provided by $\mathtt{debt}\left[\right]$, selecting ﬁrst those entries with a smaller debts.
2. If ${P}_{i}$ realises that $\mathtt{debt}\left[{P}_{j}\right]>{L}^{\ast }$ (the maximum number of lost chunks threshold), ${P}_{i}$ removes ${P}_{j}$ from $\mathtt{forward}\left[\right]$ and from $\mathtt{pending}\left[\right]$. This decreases the neighborhood degree of ${P}_{i}$. ${P}_{j}$ will decrease its neighborhood degree as well because it will consider ${P}_{i}$ as unsupportive peer.
3. In DBS, request messages are sent selecting the destination peers at random. In FCS, request messages are sent to those peers with a higher debt. Thus, if the lack of solidarity is produced by an overlay topology imbalance (an extreme example is in Fig. ??), peers poorly connected could have the chance of mitigating this problem by forwarding more chunks to their neighbors.

Using FCS, supportive peers will be served ﬁrst, incrementing the QoE of the users of the corresponding peers. On the other hand, those peers with a higher chunk debt will tend to be unserved if no enough bandwidth is available. Notice that FCS is incompatible with ACS.

Note: The prioritized round-robin neighbor selection has not yet been implemented as it has been explained here. The $\text{debt}\left[\right]$ structure exists, but is used for a diﬀerent purporse.

### 5 IMS (Ip Multicast Set)

Note: Finished and implemented. IMS modiﬁes the functionality of DBS.

IMS runs on the top of DBS and provides eﬃcient native IPM, where available. IMS is available in LANs (Local Are Networks) and VLANs (Virtual LANs) [4], but not in the global Internet [3].

All peers in the same LAN or VLAN have the same network address. When a joining peer ${P}_{i}$ receives the list of peers from its splitter, ﬁrst checks if there are neighbors in the same subnet. For all those peers, ${P}_{i}$ uses the IP address $\mathtt{224.0.0.1}$ (all systems on this subnet), (default) port $\mathtt{1234}$, to multicast (only) the chunks received from the splitter. Therefore, all peers in the same local network communicate using this multicast group address and port. The rest of external peers will be referenced using their public end-points.

### 6 TAS (Topology Adaptation Set)

Note: Unﬁnished.

In TAS, the splitter request to each peer of the team the list of neighbors (peers that send chunks directly, in one hop). This communication is reliable (TCP) and transmits the lists as a collection of end-points. The number of requests per round is limited by the available bandwidth in the overlay, and by the request-ratio deﬁned at the splitter. Obviously, the higher the ratio, a more accurate description of the real connectivity in the overlay will be obtained.

After knowing the connectivity degree of each peer, the slitter can adapt the round-robin scheduling of the origin peers by sending a number of chunks proportional to the inverse of the degree of the origin peer.

### 7 MRS (Massively-lost chunk Recovery Set)

Note: Finished but not implemented.

MRS extends DBS (or an extension of it) to retransmit massively-lost chunks. MRS should be implemented if error-prone communications are expected, specially if these channels are used by the splitter. MRS is based on the use of monitors (see Sec: 2.10). The idea is: the splitter will resend lost chunks to one or more the monitors when all monitors report their loss. To increase the probability of receiving on time the resent chunk (by normal peers), monitors halves the number of chunks in their buﬀers in relation to common peers. Notice that MRS only modiﬁes the behavior of the splitters and the monitors (normal peers does no need to implement LRS or its extensions).

### 8 NTS (NAT Traversal Set)

Note: Finished but not implemented.

Most of the peers run inside of “private” networks, i.e. behind NAT devices. NTS14 is an DBS extension which provides peer connectivity for some NAT conﬁgurations where DBS can not provide direct peer communication.15

Peers behind the same NAT will use the same external (also called “public”, because in most cases we have not nested NAT conﬁgurations) IP address of the NAT. Basically, there exist two diﬀerent types of NATs: (1) cone, and (2) symmetric. At the same time, NATs can implement diﬀerent ﬁltering strategies for the packets that comes from the external side: (a) no ﬁltering, (b) source IP ﬁltering, and (c) source end-point ﬁltering. Finally, NATs can use several port allocation algorithms, among which, the most frequent are: (i) port preservation and (ii) random port. Notice that in this discussion, only UDP transmissions will be considered.

#### 8.1 Traﬃc ﬁltering

Lets suppose a team in which, for the sake of simplicity, there is only one external (public) peer ${P}_{e}$, and that a new internal (private) peer ${P}_{i}$ has sent the sequence of [$\mathtt{hello}$]’s (see Sec 2.3). Lets denote ${P}_{i}$’s NAT as $A$. When no ﬁltering is used at all, $A$ forwards to ${P}_{i}$ any external packet that arrives to it (obviously, if it was sent to the entry in $A$’s translation table that was created during the transmission of the sequence of [$\mathtt{hello}$]’s), independently on the source end-points of the packets. In the case of source (IP) address ﬁltering, $A$ will forward the packets only if they come from ${P}_{e}$’s host. When source end-point ﬁltering is used, $A$ also checks the source port, i.e., that the packets were originated at ${P}_{e}$’s end-point.

#### 8.2 Cone VS symmetric

Cone NATs use the same external end-point for every packet that comes from the same internal end-point, independently on the destination of the packets (see Fig. 9). For the external peer ${P}_{e}$, the situation is identical to the case in which the NATed peer ${P}_{i}$ would be running in a public host.

Symmetric NATs use diﬀerent external end-points for diﬀerent packets that comes from the same internal end-point, when these packets have diﬀerent destination end-points (see Fig. ??). Thus, two diﬀerent external peers will see two diﬀerent public end-points of ${P}_{e}$.

#### 8.3 Port allocation

In the case of port preservation, if $X$:$Y$ is the private end-point (IP address:port) of a UDP packet, the NAT will use the public port $Y$, if available (notice that $Y$ cound have been assigned to a previous communcation). If $Y$ were unavailable, the NAT usually will assign the closer free port (this is called “sequentially port allocation”), usually by increasing the port value, although this behavior has not been standarized at all.

When random port allocation is implemented, the public port will be assigned at random. Notice that, even in SN-PPA conﬁgurations, in most of the real situations (where peers must compete with the rest of processes that use the network for the same NAT resources,) some kind of randomization should be always expected during a the port assignment.

#### 8.4 NAT type analysis

An incoming peer ${P}_{i}$ can determine its NAT behavior using the following steps:

1. Let ${A}_{0},{A}_{1},\cdots \phantom{\rule{0.3em}{0ex}},{A}_{M}\right\}$ the public ports used by peer ${P}_{i}$, whose NAT is $A$, to send the [$\mathtt{hello}$] UDP packets towards the splitter $S$ and the $M$ monitor peers of the team, in this order. This data is known by ${P}_{i}$ after receiving the acknowledgment of each [$\mathtt{hello}$]. Compute
 ${\Delta }_{k}={\mathsf{A}}_{k}-{\mathsf{A}}_{k-1}$ (6)

for $k=1,2,\cdots \phantom{\rule{0.3em}{0ex}},M$, the port distances gathered by ${P}_{i}$.

2. Determine a port step
 (7)

where GCD is the Greatest Common Divisor operator.

3. If $\Delta =0$ ($A$ is using the same external port for communicating ${P}_{i}$ with the rest of peers of the team) then ${P}_{i}$ is behind a cone NAT. Notice that public (not NATed) peers will be considered as being using this type of NAT, also.
4. If $\Delta >0$ ($A$ is using a diﬀerent external port for each external peer) then ${P}_{i}$ is behind a symmetric NAT. In this case:
1. If
 ${\Delta }_{1}={\Delta }_{2}=\cdots ={\Delta }_{m}$ (8)

then $A$ is using sequentially port allocation.

2. If
 $\Delta =\underset{m\to \infty }{lim}\mathrm{GCD}\left({\Delta }_{1},\cdots \phantom{\rule{0.3em}{0ex}},{\Delta }_{m}\right)=1.$ (9)

then $A$ is using random port allocation.

#### 8.5 (Theoretical) NAT traversal performance of DBS

 Peer1/2 CN CN-AF CN-EF SN-PPA SN-RPA CN DBS DBS DBS DBS DBS CN-AF DBS DBS DBS NTS - CN-EF DBS DBS DBS NTS - SN-PPA DBS NTS NTS NTS - SN-RPA DBS - - - -

Table 2: NAT traversal success for diﬀerent NAT typical combinations. CN-NF (also known by “full cone NAT”) stands for Cone NAT (without packet ﬁltering). CN-AF (also known as “restricted cone NAT”) stands for Cone NAT with source Address Filtering. CN-EF (also known by “port restricted cone NAT”) stands for Cone NAT source End-point Filtering. SN-PPA stands for Symmetric NAT Port Preservation Allocation, and no packet ﬁltering has been considered. SN-RPA stands for Symmetric NAT Random Port Allocation, and no packet ﬁltering has been used.

Figure 12: Timeline of an (ideal) NTS interaction between two peers ${P}_{1}$ and ${P}_{2}$ which are behind symmetric NATs.

Table 2 shows the theoretical traversal success of DBS (or an extension of it) for diﬀerent NAT type combinations. Peer1 represents to a peer already joined to the team, and Peer2 to an incoming peer. The entries labeled with “DBS” are those that will be handled by DBS, out-of-the-box. An explanation of why the DBS handshake works for such conﬁgurations is shown in Fig. 10. Notice that source end-point ﬁltering has been used in this example, although a similar results should be obtained for simple source address ﬁltering. On the other hand, the combinations labeled with “-” or “NTS” will not work with DBS (see Fig.11). In fact, only the “NTS” entries should work, in general, with NTS, depending on the port prediction algorithm and the number of tries.

Fig. 12 shows an example of an NTS (NAT traversal) success. When the new NATed peers, ${P}_{1}$ and ${P}_{2}$, arrive at the team, the following events happen:

• $M$ requests to join the team (the joining request is not shown in the ﬁgure for brevity) and $S$ sends to $M$ an empty list of peers. At this moment, $M$ has joined the team.
• ${P}_{1}$ requests $S$ to join through an external port ${A}_{0}$ (again, this message is not shown). $S$ sends to ${P}_{1}$ the list of peers. This list contains only the endpoint of $M$.
• NAT $A$ relays towards ${P}_{1}$ the previuos message.
• ${P}_{1}$ answers $\left[\mathtt{hello}M\right]$ to $M$.
• $A$ relays the previous message, which is received by $M$. Due to $A$ is a symmetric NAT, a new source port ${A}_{1}$ is used for this message.
• $M$ sends $\left[\mathtt{ack}M\right]$ towards $\left(A,{A}_{1}\right)$.
• The previous message is relayed by $A$. Simultaneously, $M$ informs to $S$ that ${P}_{1}$ has communicated with it, using the external endpoint $\left(A,{A}_{1}\right)$.
• $S$ acknowledges the reception of the previous message.
• ${P}_{2}$ requests to join the team (not shown) and $S$ sends to it the current list of peers, which contains the endpoint of $M$ and the tuple $\left(\left(A,{A}_{0}\right),{\Delta }_{A},#{P}_{2}\right)$ (the external endpoint used by ${P}_{1}$ to communicate with $S$, the maximum port step in NAT $A$, ${\Delta }_{A}$ measured by $S$ for ${P}_{1}$ thoroughtout its incorporation to the team, and the index of ${P}_{2}$, $#{P}_{2}$, in the list of peers). Using this information, ${P}_{2}$ will perform the port prediction for the external port that $\mathsc{𝒜}$ will assign to ${P}_{1}$ when it be communicating with ${P}_{2}$. This prediction is the list of ports ${Z}_{#{P}_{1}}=$ get_guessed_ports($#{P}_{2}$,${A}_{0}$,${\Delta }_{A}$) is populated by ${P}_{2}$ using the Algorithm ??.
• $B$ retransmits the previous message.
• ${P}_{2}$ sends a $\left[\mathtt{hello}M\right]$ towards $M$.
• $B$ retransmits the previous message, which arrives to $M$, and ${P}_{2}$ sends a $\left[\mathtt{hello}\left(A,{A}_{2}\right)\right]$ towards $\left(A,{A}_{2}\right)$, which has been computed in the Step 08.
• The previous message arrives to $\left(A,{A}_{2}\right)$ (which is correct), but $A$ discards this packet because still there is not a working entry in its translation table for the key $\left(\left(B,{B}_{2}\right),{A}_{2}\right)$.
• $M$ acknowledges the $\left[\mathtt{hello}M\right]$, which arrived in the Step 11.
• The $\left[\mathtt{ack}M\right]$ message is received by ${P}_{2}$ and $M$ informs to $S$ that ${P}_{2}$ is also using the port ${B}_{1}$ (this information is used to compute the maximum port step ${\Delta }_{B}$ in NAT $B$, measured for ${P}_{2}$ thoroughout its incorporation.
• $S$ acknowledges the previous reception.
• $S$ sends to ${P}_{1}$ the message $\left[\left(B,{B}_{0}\right),{\Delta }_{B},{S}^{\prime }\right]$ (external end-point used by ${P}_{2}$ to talk with $S$, port step measured for ${P}_{2}$ and a new temporaly listenning port ${S}^{\prime }$ at node $S$). The tuple $\left(\left(B,{B}_{0}\right),{\Delta }_{B}\right)$ allows ${P}_{1}$ to predict which external port (${B}_{2}$) will use $\mathrm{NAT}B$ when ${P}_{2}$ sends a packet to ${P}_{1}$. The extra socket bound by $S$ to ${S}^{\prime }$ will be used to update the external port that ${P}_{1}$ is currently using to communicate with the rest of peers of the team.
• ${P}_{1}$ receives the previous message.
• ${P}_{1}$ says $\left[\mathtt{hello}{P}_{2}\right]$ to EEP $\left(\mathrm{NAT}B,{B}_{2}\right)$.
• ${P}_{1}$ says $\left[\mathtt{hello}S\right]$ to EEP $\left(S,{S}^{\prime }\right)$.
• $\mathrm{NAT}B$ relays the message $\left[\mathtt{hello}{P}_{2}\right]$ towards ${P}_{2}$ and $\left[\mathtt{hello}S\right]$ is received by $S$ (which updates the external port for ${P}_{1}$). Notice that at this moment, ${P}_{2}$ knows that ${P}_{1}$ is able to send data to it.
• Both, $S$ and ${P}_{2}$ acknowledges the $\left[\mathtt{hello}\right]$ messages.
• $\left[\mathtt{ack}S\right]$ is received by ${P}_{1}$, $\left[\mathtt{ack}{P}_{2}\right]$ is received by $\mathrm{NAT}A$ and the timer assigned to the message $\left[\mathtt{hello}{P}_{1}\right]$ sent in Step 11 timeouts and this message is re-sent.
• ${P}_{1}$ receives $\left[\mathtt{ack}{P}_{2}\right]$ and $\mathrm{NAT}A$ receives $\left[\mathtt{hello}{P}_{1}\right]$.
• $\left[\mathtt{hello}{P}_{1}\right]$ is delivered to ${P}_{1}$. At this moment, ${P}_{1}$ knows that ${P}_{2}$ is able to send data to it.
• ${P}_{1}$ acknowledges the previous $\left[\mathtt{hello}{P}_{1}\right]$.
• $\left[\mathtt{ack}{P}_{1}\right]$ arrives to $\mathrm{NAT}B$.
• $\left[\mathtt{ack}{P}_{1}\right]$ arrives to ${P}_{2}$.
• ${P}_{1}$ and ${P}_{2}$ annouce to the $S$ the source port used by the other peer.
• This information is received by the $S$, which updates the external port information for ${P}_{1}$ and ${P}_{2}$.

Summarizing, NTS can provide connectivity for those peers that are behind port-preservation symmetric NATs with sequential port allocation.

#### 8.6 A port prediction algorithm (Max’s proposal)

When both peers, Peer1 and Peer2, are behind symmetric NATs, both must predict the port that the NAT of the interlocutor peer will use to send the packets towards it. And obviously, this must be performed by each already incorporated peer that is behind a symmetric NAT.

The list of predicted ports $Z$ that a a peer ${P}_{x}$ performs is determined by:

 $\begin{array}{ccc}\hfill Z& \hfill =\hfill & {A}_{0}+x+\left\{s\in \left\{0,1,\cdots \phantom{\rule{0.3em}{0ex}},N∕2-1\right\}\right\};\hfill \\ \hfill Z& \hfill +=\hfill & {A}_{0}+\left(x+\left\{s\in \left\{0,1,\cdots \phantom{\rule{0.3em}{0ex}},N-1\right\}\right\}\right)\cdot \Delta .\hfill \end{array}$ (10)

where “$+=$” denotes the concatenation of lists and $N$ is the number of guessed ports, ${A}_{0}$ is the ﬁrst external port (the port used to communicate with $S$) assigned to the incoming peer and $\Delta$ is the (maximum) port step measured for the incoming peer’s NAT.

### 9 MCS (Multi-Channel Set)

Note: Unﬁnished.

When using MDC [1], SVC [2], or for emulating the CS model, it can be interesting for peers to belong to more than one team. To implement MCS, peers must replicate the P2PSP modules (DBS at least) for each team (channel), except the buﬀer.

The use of MDC is trivial: the higher the number received descriptions (channels), even partially, the higher the quality of the playback. However, when transmitting SVC media, peers should prioritize the reception of the most important layers.

When a peer belongs to more than one team, and the teams broadcast exactly the same stream (the same chunks and headers), it could move between teams seamless (without losts of signal).

A pure CS service could be provided if the corresponding splitter announces one empty team and sends each chunk so many times as teams (with one peer/team) there are.

### 10 CIS (Content Integrity Set)

Note: Unﬁnished.

A variety of techniques to ﬁght pollution in P2P live streaming systems are available in the literature, including hash-based signature and data encryption techniques.

### References

[1]   Pierpaolo Baccichet, Jeonghun Noh, Eric Setton, and Bernd Girod. Content-aware p2p video streaming with low latency. In Multimedia and Expo, 2007 IEEE International Conference on, pages 400–403. IEEE, 2007.

[2]   Xiaowen Chu, Kaiyong Zhao, Zongpeng Li, and Anirban Mahanti. Auction-based on-demand p2p min-cost media streaming with network coding. IEEE Transactions on Parallel and Distributed Systems, 20(12):1816–1829, 2009.

[3]   Douglas E. Comer. Internetworking with TCP/IP. Principles, Protocols, and Architectures (4th Edition), volume 1. Prentice Hall, 2000.

[4]   Lior Shabtay and Benny Rodrig. Ip multicast in vlan environment, April 12 2011. US Patent 7,924,837.