P2PSP (Peer-to-Peer Straightforward Protocol)

January 22, 2019

Abstract

P2PSP (https://p2psp.github.io) is an application-layer protocol that provides real-time broadcasting, also known as Application Layer Multicast (ALM), of a media stream on the Internet. Peers collaborate to diseminate the stream that is generated by a single source, minimizing the latency and the protocol overhead. P2PSP overlays are push-based (topology-driven) meshes. To minimize the transmission latency, P2PSP establishes a communication between nearby peers, and chunks of data are ﬂooded without explicit requests. P2PSP has a modular design organized in sets of rules, where each module is especialized in implementing diﬀerent functionalities.

Contents

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

http://server/mount_point

P2PSP does not perform data-ﬂow control over the stream. The transmission bit-rate between P2PSP entities is controlled by an external (Icecast, for example) server, which provides the stream. Fig. 1 shows an example of a streaming overlay where several servers relay a set of channels produced by a set of source-clients, directly or through other servers. As can be seen, a listener (which usually plays de stream) can be replaced by a splitter, a P2PSP entity that sends the received stream (a single channel) to a set of P2PSP peers, called team. Notice that, considering that at least one player can be attached to each peer, the scalability of the hybrid alternative is much higher than the pure client/server architecture.

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 or 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 a HTTP 302 code) to a suitable server.

This idea can be extended to minimize the response time of hybrid CDN/P2P structures. When a P2PSP user (who knows an URL of the channel) runs a local peer, it provides the peer with the URL of the channel: 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 “optimal” 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, all splitters associated to the same stream should generate exactly the same chunks (content and header). See Section 9.

 Parameter Meaning $B$ Buﬀer size in chunks $C$ Chunk size ${L}^{\ast }$ Maximum losses of chunk allowed $M$ Number of monitors ${N}^{\ast }$ Maximum number of peers in a team

Table 1: Nomenclature used in DBS.

DBS provides ALM [2] of a media stream in unicast environments [5]. The media is sent by a streaming server, and received by a splitter (see Sec. 1). The splitter divides the stream into a sequence of chunks of data, and relay them to its team using a round-robing schema, where it can be up to ${N}^{\ast }$ peers. Each peer gathers the chunks from the splitter and the rest of peers of the team, and sends them to at least one player5 .

In Tab. 1 the deﬁnitions used in the DBS have been summarized.

2.1 Team deﬁnition

A team is a set of one or more peers that share the same stream. By deﬁnition, in a team of size one, the only peer is known as a monitor peer. In a team with more than one peer, at least one of them must be a monitor peer. Monitor peers are instantiated by the overlay administrator to monitorize diﬀerent aspects of the broadcasting, such as, the quality of the rendered video.

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 origin peer6 , using a round-robin schema. Chunks are enumerated to distinguish them at the peers.

We deﬁne a round as the process of transmitting $N$ diﬀerent chunks from the splitter to a team of $N$ peers. In other words, for a team of size $N$, the round-time is $N$ chunk-times. Notice that the round-time is variable, and depends on the current number of peers in the team ($N$), the chunk size ($C$), and the average bit-rate of the media stream.

The splitter remembers which chunk, of a list of the last $B$ transmitted chunks, was sent to each peer of the team. Notice that, in order to remember in a round which chunk was sent to each peer, $B\ge N$. See $\text{destination_of_chunk}\left[\right]$ in splitter_dbs.py.

2.3 Joining a team

After connecting with a splitter, incoming peers request (using a reliable communication) to the splitter the current list of peers in the team. To minimize the joining time, the peer sends a $\left[\mathtt{hello}\right]$ message to each 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 a table of peers called $\text{forward}\left[\right]$ (see $\text{forward[]}$ in peer.py). If a peer ${P}_{i}$ has an entry $\text{forward}\left[{P}_{j}\right]={P}_{k}$ then, each chunk received by ${P}_{i}$ and originated at ${P}_{j}$ will be forwarded to ${P}_{k}$.

The splitter, in a loop: (1) listens to the incoming peers, (2) sends the list of peers in the team, and (3) adds the incoming peer to the list.

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 playing them. A chunk with number $x$ is inserted in the position $\left(x\mathit{mod}2B\right)$ of the buﬀer, where $B$ is the maximum number of chunks that the buﬀer will store. In a peer’s life, $B$ is constant, but it is not compulsory that all peers of the same team use the same $B$ value.

The buﬀer is implemented as a circular queue of $2B$ chunks, which is ﬁlled up to only $B$ chunks in the buﬀering time (which is the main part of the start-up time that the users experiment). Chunks with a higher number (newer chunks) are inserted in the head of the buﬀer. The chunk pointed by the tail of the buﬀer is sent to the player (if there is a chunk in that cell of the buﬀer). This action is carried out each time a new chunk is received.

The buﬀering time determines how much time the peers must wait before start playing the chunks. Considering that chunks can be lost in transit or delayed more than $B$ times of chunk, randomly, it is diﬃcult to determine, a priori, the optimal buﬀering time. In the current implementation, peers buﬀer a variable number of chunks that depends on the order in which chunks are received. If ${x}_{1}$ is the (number of the) ﬁrst chunk received (the ﬁrst chunk to be played), the buﬀering time ﬁnishes when the chunk ${x}_{1}+B$ is received.7

2.5 Chunk ﬂooding

DBS implements a content-unaware push-based protocol, and when a peer receives a chunk, it can be retransmitted to a large number of neighbors. To avoid network congestion while ﬂooding, some kind of ﬂow control must be performed.

Congestion may be avoided by means of a basic idea: if I have received a chunk, I should send a chunk. It is easy to see that, in a fully connected overlay, this allows to control the data ﬂow. However, in more realistic scenarios, peers can be “connected” with a variable number of neighbors and therefore, if the splitter follows a pure round-robin strategy, some peers can send more chunks that they receive.

The previous idea can be improved to handle a variable connectivity degree. Each peer uses a table of lists, $\text{pending}\left[\right]$, indexed by the neighbor end-points, where each list stores the positions in the buﬀer of those chunks that must be transmited to the corresponding neighbor, the next time such neighbor be selected. Thus, if for example $\text{pending}\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}$ (when a round-robin scheduler used by the peer selects ${P}_{x}$). The current scheduler used by the peers selects a diﬀerent neighbor, using a round-robin scheme, for each new received chunk.

Note:

An example of the ﬂooding with congestion control algorithm has been show in the Figs. 2, ...

2.6 Overlay organization

Chunks can be lost.8 A chunk is considered as lost when it is time to send it to the player and the chunk has not been received. In this situation, for each lost chunk, the peer sends a $\left[\mathtt{request}\text{lost_chunk_number}\right]$ (that is the number of the next chunk to be played) to a randomly selected peer of the team. When a peer ${P}_{x}$ receives a $\left[\mathtt{request}\text{lost_chunk_number}\right]$ from ${P}_{y}$, ${P}_{x}$ adds ${P}_{y}$ to $\text{forward}\left[{P}_{o}\right]$, where ${P}_{o}$ is the origin peer of the chunk stored in the position $lost\text{_}chunk\text{_}number$ of the buﬀer.

In this situation, it is also possible that some peers can request redundant paths between an origin peer and itself, and therefore, some chunks could be received more than once. If this case, for each duplicate chunk, a peer ${P}_{i}$ should send a $\left[\mathtt{prune}\text{duplicate_chunk_number}\right]$ message to those neighbors that have sent to it the duplicate chunk. Neighbors receiving such message from peer ${P}_{i}$ should remove the ${P}_{i}$ from $\text{forward}\left[{P}_{o}\right]$, where ${P}_{o}$ is the origin peer of the duplicate chunk.

2.7 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 timeout, the leaving procedure is reset a number of times.

When a peer of the team receives a $\left[\mathtt{goodbye}\right]$, removes the sender from the $\text{forward}$ table.

The splitter removes the outgoing peer from the list of peers.

2.8 Free-riding control

In each team there are a set of monitors (trusted peers whose behavior is predictable and that are only known by the splitter), which complain to their splitter with a $\left[\mathtt{lost}\text{lost_chunk_number}\right]$ for each lost chunk. The splitter only considers these type of messages if they come from a monitor.

If a peer ${P}_{o}$ accumulates more than ${L}^{\ast }$ losts in $R$ rounds, ${P}_{o}$ is removed from the splitter’s list of peers. Peers do the same, but in this case they remove the selﬁsh neighbors from the $\text{forward}$ and $\text{pending}$ tables.

Note: This last functionality has not been implemented, at least, as it has been explained here. The forget() thread is controlled by a timer, not by a counter of rounds.

3 IMS (Ip Multicast Set)

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

The idea of IMS is simple: 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 (all of them share the same private network address). 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. When implementing IMS, all peers in the same local network communicate using this IPM group address and port. The rest of external peers will be referenced using their public end-points.

4 FCS (Free-riding Control Set)

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 connectivity as a consecuence, for example, of NAT issues) can stay in the team thanks to the generosity of the rest of peers. If this is unnaceptable, this set of rules try to that all the peers of the team to share the same number of chunks that they receive.

To know the level of solidarity between neighbor peers, each peer implements a table of chunk debts, $\text{debt}\left[\right]$. Every time ${P}_{k}$ sends a chunk to ${P}_{l}$, ${P}_{k}$ runs $\text{debt}\left[{P}_{l}\right]=\text{debt}\left[{P}_{l}\right]+1$, and ${P}_{l}$ runs $\text{debt}\left[{P}_{k}\right]=\text{debt}\left[{P}_{k}\right]∕2$. So, peers increment the insolidarity measurement incrementally and decreases it exponentially towards zero. This respond to the idea of that, if a peer keeps sending chunks to their neighbors, it has doing its best in retransmitting the chunks it must forward.

With the $\text{debt}\left[\right]$ information, peers modify the way the neighbor are selected during the ﬂooding procedure. Now, the $\text{pending}\left[\right]$ list is sorted by debts (those peers with a lower debt will appear in the ﬁrst positions of $\text{pending}\left[\right]$), and when a peer receives a chunk from the splitter, the run over the $\text{pending}\left[\right]$ list will be reset. In this way, supportive peers will be served ﬁrst, incrementing the QoE of the corresponding users. On the other hand, those peers with a higher chunk debt will tend to be unserved if no enough bandwidth is available.

The second mechanism to increase the grade of solidarity is to send the $\left[\mathtt{request}\text{lost_chunk_number}\right]$ to those peers with a higher debt. So, if the insolidarity is produced by a overlay topology imbalance, badly connected peers peers can mitigate this problem forwarding more chunks to their neighbors.

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.

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.

6 MRS (Massively-lost chunk Recovery Set)

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.8). 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).

ACS relaxes the peer’s upload requirements imposed by DBS. It should be used in if it is known that some peers can provide the capacity than others cannot, or when we want to mix the CS and P2P models, sending more chunks from the splitter to one or more monitors controlled by the contents provider.

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.8), to send to those more reliable peers a higher number of chunks than to the others. In other words, ACS adapts the round-time of each peer to its capacity.

Notice that ACS only aﬀects the behavior of the splitter.

8 NTS (NAT Traversal Set)

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

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. 8). 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}$ (1)

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

2. Determine a port step
 (2)

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}$ (3)

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.$ (4)

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 11: 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. 9. 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.10). In fact, only the “NTS” entries should work, in general, with NTS, depending on the port prediction algorithm and the number of tries.

Fig. 11 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}$ (5)

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)

When using MDC [1], SVC [3], 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 is in 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)

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.

11 DPS (Data Privacy Set)

The following set of rules deals with privacy-related issues. Many content providers oﬀer pay-per-view channels as part of their services. From a technical point of view, this implies having a Key Server that ciphers the stream with a symmetric encryption key and delivers such key to authorized members only. However, this is not enough: it is crucial that the Key Server renews the encryption key after the expiration of a peer’s authorization period so the stream can not be decrypted any more by the peer (this feature is called forward secrecy). In addition, if we want to play on the safe side then the Key Server should renew the encryption key after a peer purchases an authorization period (if the key remained the same then the peer might decrypt previously captured stream packets for a later viewing). This renewal process is not trivial and is carried out by a secure multicast protocol. In order to alleviate the overhead incurred by avalanches of peers entering and leaving the authorized group (for example, at the beginning of a high interest event such as The Olympics) key renewal can be performed on a batch manner, i.e. renewing the key at a given ﬁxed frequency rather than on a per arrival/exit basis. Finally, key renewal messages should be authenticated by means of a digital signature or other alternative methods [Perrig].

Many secure multicast protocols protocols exist in the literature, for example [Xu],[Lin],[Zhou],[Yoon]. Here we suggest the implementation of a protocol by Naranjo et al [Naranjo]. On it, every authorized peer receives a large prime number from the Key Server at the beginning of its authorization period (this communication is done under a secure channel, for example SSL/TLS). For every renewal, the Key Server generates a message containing the new key to be used by means of algebraic operations: all the authorized primes are involved in this message generation process, and the key can only be extracted from the message by a peer with a valid prime. This protocol is eﬃcient and suits P2PSP architecture in a natural way: every splitter can act as a Key Server for its own team. Hence, the stream would be ﬁrst transmitted among splitters (possible encrypted by a diﬀerent key, shared by the splitters). Within each team, its corresponding splitter would control the encryption and key renewal process.

@article{Perrig,
author = {Perrig, A. and Szewczyk, R. and Tygar, J. D. and Wen, V. and Culler, David E.},
title = {{SPINS}: security protocols for sensor networks},
journal = {Wirel. Netw.},
volume = {8},
issue = {5},
year = {2002},
issn = {1022-0038},
pages = {521--534},
numpages = {14},
url = {http://dx.doi.org/10.1023/A:1016598314198},
doi = {http://dx.doi.org/10.1023/A:1016598314198},
acmid = {582464},
}

@article{Xu,
author = {Xu, Lihao and Huang, Cheng},
title = {Computation-Efficient Multicast Key Distribution},
journal = {IEEE Trans. Parallel Distrib. Syst.},
issue_date = {May 2008},
volume = {19},
number = {5},
month = may,
year = {2008},
issn = {1045-9219},
pages = {577--587},
numpages = {11},
url = {http://dx.doi.org/10.1109/TPDS.2007.70759},
doi = {10.1109/TPDS.2007.70759},
acmid = {1399352},
publisher = {IEEE Press},
}

@article{Lin,
title = "Secure and efficient group key management with shared key derivation",
journal = "Comput. Stand. Inter.",
volume = "31",
number = "1",
pages = "192 - 208",
year = "2009",
note = "",
issn = "0920-5489",
doi = "DOI: 10.1016/j.csi.2007.11.005",
url = "http://www.sciencedirect.com/science/article/B6TYV-4R8H1TR-6/2/fb531f2c68f8b92beebf1608a5a82746",
author = "J. Lin and K. Huang and F. Lai and H. Lee",
keywords = "Secure group communication",
keywords = "Group key management",
keywords = "Key tree",
keywords = "Shared key derivation"
}

@inproceedings{Zhou,
author = {Zhou, Z. and Huang, D.},
title = {An optimal key distribution scheme for secure multicast group communication},
booktitle = {INFOCOM’10},
year = {2010},
isbn = {978-1-4244-5836-3},
location = {San Diego, California, USA},
pages = {331--335},
numpages = {5},
url = {http://portal.acm.org/citation.cfm?id=1833515.1833582},
acmid = {1833582},
keywords = {group key management, multicast, security},
}

@article{Yoon,
title = "A secure broadcasting cryptosystem and its application to grid computing",
journal = "Future Generation Computer Systems",
volume = "27",
number = "5",
pages = "620 - 626",
year = "2011",
note = "",
issn = "0167-739X",
doi = "10.1016/j.future.2010.09.012",
url = "http://www.sciencedirect.com/science/article/pii/S0167739X10001913",
author = "Eun-Jun Yoon and Kee-Young Yoo",
}

@article{Naranjo,
author = {Naranjo, J. A. M. and Casado, L. G. and L\’opez-Ramos, J. A.},
title = {Group Oriented Renewal of Secrets and Its Application to Secure Multicast},
journal = {\href{http://www.iis.sinica.edu.tw/page/jise/Introduction.html}{Journal of Information Science and Engineering}},
volume = {27},
number = {4},
pages = {1303--1313},
month = {july},
year = {2011}
}

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]   Suman Banerjee, Bobby Bhattacharjee, and Christopher Kommareddy. Scalable application layer multicast, volume 32. ACM, 2002.

[3]   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.

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

[5]   Douglas E Comer and Ralph E Droms. Computer networks and internets. Prentice-Hall, Inc., 2003.

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