Peer To Peer Networking

History

Traditionally, the internet has been built on a client-server architecture. There were distinct roles given to the devices which were involved. They were either clients who received data or servers who serve data.

Extending on that concept, there is now delegation of roles. The role of the client remained the same while servers can be iterative or recursive.

An example of this is used in Domain Name Systems (DNS). When a client sends a DNS request, it can either be resolve iteratively or recursively.

Iterative Resolution

In iterative resolution, the client sends a request to a DNS server A. A then sends a request to another DNS server B.

However, B does not help A ask C for the address for the target, it sends A the address of C for A to ask C itself.

A then iteratively ask each of the DNS servers until the domain name is resolved before replying to the client.

Recursive Resolution

Similar to the iterative resolution, the client sends a request to DNS server A. A then sends a request to another DNS server B.

Instead of replying with an IP address of C for A to check out, B helps A to ask C. This process repeats (C asks D, D asks E, etc) until the domain name is resolved.

Each DNS Server recursively asks the next DNS server until the domain name is resolved before replying to the client.

Eventually, C replies B, B replies A, A replies the client.

Peer To Peer

However, peer to peer systems do not have the same architecture. There is no central server which all the clients connect to, instead, arbitrary clients can connect to each other and communicate directly. It has a flat architecture with no hierarchy unlike DNS above.

However, switching to this architecture has its own set of problems.

1. Peers intermittently connect and disconnect
2. Service providers may be unreliable
3. Resource lookup is hard

Let us look at how technology over the years have tried to tackle this problem.

Some examples of P2P systems

1. File Sharing
   1. Napster (1999 - 2002)
   2. KaZaa (2001 - 2012)
   3. Gnutella
2. Content Distribution
   1. BitTorrent
3. Voice over IP
   1. Skype
4. Video Streaming
   1. PPLive
   2. PPStream
5. Other applications
   1. Blockchain & Cryptography
   2. P2P Computation

We will be going some of the examples above (ones in bold) to see how they tackle the issues with P2P systems.

Napster (1999-2001)

Napster is a peer to peer file sharing application. It was launched on 1st June 1999 with an emphasis on digital audio distribution.

It is based on a central index server which keeps track of users. The server sends a list of files to be shared to the peers and the server knows all the peers and the files in the network.

Searching based on keywords were supported and the server will return a list of files together with the peer carrying the file. Some information was keyed in by the user manually which is unreliable.

How does it work?

Similar to Delegation, the central Napster server indexes all the clients and files in the network. When a client wants to search for a file, it sends a request to the server.

The server then redirects you to a peer which has the file and the client downloads the file from the peer directly.

Using the diagram above, when Napster client A wants to download a file:

1. It first sends a request to the server
2. The server sends the location of the peer which has the file
3. Client A requests the file from Client B and downloads it

Pros and Cons

Pros:

1. It had a consistent view of the network
2. There was fast and efficient searching
3. Searches were guaranteed correct answers

Cons:

1. The central server was a single point of failure
2. Large computations were required to handle queries
3. Download was only from a single peer
4. Content was unreliable
5. It was vulnerable to attacks
6. There was no copyright protection for the files being shared which lead to a lawsuit.

The lawsuit eventually resulted in their shutdown in 2002.

Gnutella

Gnutella was a peer to peer network protocol which was developed in 2000. It was the first of its kind, leading other networks to adopt a similar model.

Unlike Napster, it was a decentralized network and does not require a central server.

How does it work?

Gnutella only consisted of a network of fully equal peers.

To join the network, peer needs the address of another separate peer through out of band channels. (IE: Through websites, chat rooms, etc)

Once joined, the peer learns about others as well as the topology of the network. Queries flood the network and download happens directly between peers.

Using the diagram above, when Gnutella Peer A sends a request for a particular file, it floods the network with the request.

1. Gnutella Peer A sends the query to B, E and F
2. E has the file and sends a hit reply to Peer A
3. B does not have the file but is connected to other peers
4. B floods the query to C and D
5. D replies to B with a hit reply
6. B replies to A with a hit reply

Pros and Cons

Pros:

1. The system was fully distributed
2. The protocol was open source
   1. It was easy to write clients.
3. The system was robust to node failures
   1. This is only true for random failures as it forms a power-law network
4. Less susceptible to denial of service

Cons:

1. The queries were inefficient
   1. It is a waste of network resources to flood the network with queries
2. Inefficient network management
   1. Constant probing is required to check if the peer was still active

KaZaA

Similar to Napster, KaZaA was a peer to peer file sharing application using the FastTrack protocol. It was launched in March 2001 after the shutdown of Napster.

Similarly to Napster, it also faced a lawsuit which let to its shutdown in August 2012.

How does it work?

KaZaA contains 2 kinds of nodes.

1. Ordinary nodes (ON) which acts as a normal user peer.
2. Super Nodes (SN) which is a peer with more resources and responsibilities.

This results in a 2 tier hierarchy.

The top level contains only Super Nodes and the bottom level contains only Ordinary Nodes. Each Ordinary Node is connected to 1 Super Node. This can change but it can only connect to at most 1 super node at any 1 time.

The super nodes acts as a hub for all of its ordinary node children. This includes keeping track of files within the ON children peers.

Using the diagram above, if an ordinary node wants to download a file, it sends a request to the super node that it is connected to. By default, the request have a time to live (TTL) of 7.

The super node will flood the request to other super nodes. After receiving the request, the super node will reduce the TTL by 1 and continue querying the other super nodes. When it runs out, the request will stop propagating.

After the file is found, the file is transferred directly over the network from the source node to the destination node using HTTP (Hyper Text Transfer Protocol).

Super Vs Ordinary Nodes

Super nodes:

1. Exchange information within themselves
2. Do not form a complete mesh
3. SNs change connections to other SN every 10s of minutes
   1. This allows for larger network ranges to be explored
   2. SNs have an average lifespan of 2.5 hours with large variances
4. SNs do not cache information from disconnected ONs
5. 1 SN has connection to roughly 30-50 other SNs
6. There are roughly 30,000 SNs at any given time.
7. Each super node serves 60 to 150 ordinary nodes at any one time

Ordinary Nodes

1. Obtain address of super node and sends request and gives list of files to share
2. Super node keeps track of ordinary node
3. Ordinary nodes under a super node are not visible to other super nodes.
4. Can be promoted to a super node when it has sufficient bandwidth and up time.
   1. But the nodes can refuse to become a super node
   2. Bandwidth requirements are usually between 160 - 200 kb/s
5. Roughly 13% of the ONs are responsible for 80% of the uploads

Skype

Skype is a proprietary telecom application which allows users to make voice calls over the internet.

Instead of using real phone networks and real phone numbers to make calls, skype makes use of the internet to make calls. This reduces the cost of making calls for the user.

In 2017 it was migrated over to a centralized Azure-based service. In this blog, we will be discussing its peer to peer capabilities before migration.

How it works?

Similar to Kazaa, the architecture of Skype is also a 2 tier hierarchy consisting of super nodes and ordinary nodes.

Although the protocol was not released, it is believed that the pairs of users used a proprietary, encrypted application-layer protocol.

Each client maintains a host cache with the IP address and port numbers of reachable super nodes. The skype user directory is decentralized and distributed among the super nodes in the network.

Super nodes are grouped into slots (of 9 to 10 super nodes) and slots are group in blocks (of 8 slots). Before they were acquired by Microsoft, any node who has good bandwidth, no restrictions due to firewall or NAT (Network Address Translation) and sufficient processing power can become a super node.

After being acquired by Microsoft, they changed the design to only use their own servers as super nodes.

As shown in the diagram above, the network contains three types of entities, namely:

1. Super Nodes
2. Ordinary Nodes
3. Login Service

When client A searches for client B, the request is sent to a Super Node. If the Super Node does not have the information required, it will send a list of other Super Nodes to query and the client iteratively queries the other Super Nodes (Similar to DNS Server’s Iterative Query). The Process continues until the client finds the user or determines that the user does not exist.

After searching for the user, it caches the information about the user on its local machine. When the client makes a call to the user, it will send a TCP packet to the user’s IP address and port number and the call will continue from there.

Problems

There might be a problem with the call when both clients are behind NAT (Network Address Translation) boxes which prevents an outside peer from initiating a call to an inside peer.

To solve this problem, a relay is chosen using the super node of the caller and the callee. Each peer will initiate the connection to the relay and the relay will inform both peers of the other peer’s IP address and port number.

The peers will then communicate through their NATs via the relay.

BitTorrent

BitTorrent is a peer to peer file sharing protocol which allows users to download files from each other. It was first released in 2001 and is still widely used today.

BitTorrent builds a network (swarm) for every file that is distributed.

Pros and Cons

Pros

1. A Link can be sent to a friend
2. A Link always refers to the same file
3. Not feasible on search-based p2p networks (Like Napster, Gnutella or Kazaa)

Cons

1. Websites with link collections and search exists but there is no name service.

How does it work?

For each shared file, there is (initially) one server (seed) which hosts the original copy of the file. The file is broken into chunks on the server.

A torrent file is created which contains the metadata about the contents of the file. The file is typically hosted on a web server.

Clients download the torrent file from the website and use the information to identify a tracker and get the size and checksums of chunks.

The diagram above shows the steps involved when a file is hosted by the seed and downloaded by a new client.

The tracker only keeps track of which seeds and peers are in the swarm but does not actually participate in the actual file distribution.

A torrent refers to a group of peers exchanging chunks of a file (IE: Me downloading a torrent from another peer)

A Swarm refers to seeds and peers.

Details of BitTorrent

The chunk size for files in BitTorrent is 256 KB. For peers joining the torrent:

1. They start with no chunks and will slowly accumulate them over time.
2. They register with tracker to get list of peers and connects to a subset of them.

When downloading chunks, peers upload chunks to other peers at the same time. Once the peer has the entire file (Download finishes), it may leave or remain within the swarm.

To keep the peers synchronized and optimized, BitTorrent makes use of the following mechanism:

1. Pulling chunks
2. Tit-for-tat

Pulling Chunks

At any given time, peers have a different subset of file chunks. Periodically, a peer asks each neighbor for a list of chunks that they possess. The peer then sends requests for the chunks which she is missing (By rarest first).

This process keeps the peers up to date on the chunks and aids in the chunks accumulation process.

Tit-for-tat

In this mechanism, a peer sends chunks to four neighbors currently sending her chunks (at the highest rate) and reevaluates the top 4 every 10 seconds.

Every 30 seconds after that, the peer will randomly select another peer and start sending chunks to it. The new peer may be chosen to be the new top 4. This is known as optimistically un-choking.

Summary

We went through a list of P2P systems of various categories and how they worked. We also looked at the pros and cons of each system.

1. File Sharing
   1. Napster (1999 - 2002)
   2. KaZaa (2001 - 2012)
   3. Gnutella
2. Content Distribution
   1. BitTorrent
3. Voice over IP
   1. Skype

References

• Napster Wiki
• Gnutella
• Query Flooding
• Kazaa
• Kazaa
• Skype Protocol
• Silver Needle in the Skype
• An Analysis of the Skype p2p Protocol
• BitTorrent