DNS & P2P Networks

Domain Name System (DNS) Recap

• DNS translates names to IP addresses and vice versa.
• Name translation goes from root servers to TLD servers and authoritative servers.
• Name translation can be iterative and recursive.
• Records are inserted into the DNS database.
• Vulnerabilities include denial of service, man-in-the-middle attacks, DNS poisoning, and DNS exploitation for denial-of-service attacks.

Introduction to Peer-to-Peer (P2P) Applications

• Focus shifts from client-server architecture to peer-to-peer (P2P) applications.
• P2P applications do not require an always-on server, unlike client-server models.
• Arbitrary end systems (peers) communicate directly without a central server.
• Peers in a P2P network can change their IP addresses, unlike servers in a client-server architecture.

Example P2P Applications

• BitTorrent: Used for file distribution.
• CamCan: Used for streaming.
• Skype: Used for Voice over IP (VoIP).
• All leverage the P2P architecture.

File Distribution: Client-Server vs. P2P

• Analysis looks at the time required to distribute a file in both client-server and P2P architectures.
• The goal is to determine which architecture offers faster file distribution.

Client-Server File Distribution: Analysis

• Scenario: a network with a server and N peers, each with upload and download capacities.
• Server upload capacity: US.
• Peer download capacity: DI.
• Peer upload capacity: UI
• The objective is to calculate the time it takes for the server to transmit a file of size F to all N users.
• Assumption: all users are downloading the same file, and the network core is dedicated to this task.

Server Transmission Time (Client-Server)

• Time to transmit one copy of the file: F / US (F is the file size, US is the server's upload rate).
• Time to transmit the file to N clients: N * F / US

Client-Side Download Time (Client-Server)

• Each client has a different download rate (DI).
• Dmin: represents the minimum download rate among all clients, where Dmin = min(D1, D2, D3,..., DN).
• Time for the slowest client to download the file: F / Dmin.

Total Distribution Time (Client-Server)

• Distribution time using the client-server approach (DCS) is the maximum of:
  • N * F / US (time for the server to send to all clients)
  • F / Dmin (time for the slowest client to download)
• DCS = max(N * F / US, F / Dmin).
• Distribution time increases linearly with the number of clients (N).

P2P File Distribution: Analysis

• Server initially sends the complete file to only one peer.
• After the initial send, the server’s role is complete.
• Peers then share the file among themselves.
• Time for the server to upload the file to the first peer: F / US
• Minimum client download time remains F / Dmin.
• Aggregate download requirement: Clients must collectively download N * F bits.
• Maximum upload rate: sum of the server's upload rate and the upload rates of all peers US + ΣUi (summation from U1 to UN).

Total Distribution Time (P2P)

• Distribution time using P2P architecture is the maximum of:
  • F / US (time for the server to upload to the first peer)
  • F / Dmin (time for the slowest client to download)
  • N * F / (US + ΣUi) (time for all clients to download, considering aggregate upload capacity)
• DP2P = max(F / US, F / Dmin, N * F / (US + ΣUi)).
• Increasing N also increases the aggregate upload capacity (ΣUi), mitigating the increase in distribution time compared to the client-server model.

Comparison: Client-Server vs. P2P

• Scenario: Client upload rate = U, Server upload rate = US = 10U, Dmin > US.
• Client-server distribution time increases linearly with N.
• P2P distribution time remains significantly lower and is less affected by N due to the increasing cumulative upload rate.
• In some cases, the distribution time can be less than the time for the server to transmit to the network core.

BitTorrent: P2P File Distribution in Practice

• BitTorrent divides files into chunks (typically 256 KB).

BitTorrent: Peers and Trackers

• Peers: Users in the BitTorrent network receive and send file chunks.
• Tracker: a node that maintains a list of all participating peers in a torrent, and keeps track of active nodes.
• Torrent: A group of peers exchanging file chunks, and want to exchange chunks of a file.

Joining a Torrent

• Alice wants to join a BitTorrent network.
• Alice first retrieves a list of peers from the tracker.
• Alice attempts to open TCP connections with these peers to start receiving file chunks, and connects via TCP with peers to receive chunks.
• Some peers accept Alice's TCP connections, and those become Alice's neighbors.

Chunk Exchange

• A new peer initially has no chunks but accumulates them over time.
• Peers upload chunks to other peers while downloading.
• Exchange happens while downloading.
• Peers can dynamically change the peers they exchange chunks with.
• Peers may change which other participants they exchange with, making this a dynamic process.

Dynamic Peer Participation (Churn)

• Peers can join and leave the torrent network at any time they choose.
• Any peer can come in/out of any network anytime.
• A peer might leave after acquiring the complete file (selfish behavior) or remain to provide chunks to others (altruistic behavior).

Chunk Requests

• Peers request chunks they don't have.
• Different peers possess different subsets of the file's chunks at any given time, depending on who has contributed/downloaded what.
• Peers periodically ask each other for lists of available chunks.
• They exchange periodically any lists available with each peer.
• Alice requests missing chunks from peers who have them.

Requesting the "Rarest" Chunks

• Alice prioritizes requesting the rarest chunk first, because some of the sources of the less rare Chunks may be more persistent on the network.
• Goal: to ensure that rare chunks are replicated across the network to prevent data loss if a peer leaves.

Sending Chunks: Tit-for-Tat

• Alice sends chunks to the four peers currently sending chunks to her at the highest rate, and sends back to the top 4 peers she's receiving them from.
• Other peers are "choked" (not sent data by Alice).
• The top four peers are re-evaluated every 10 seconds.
• Every 30 seconds, Alice optimistically unchokes a random peer to see if it can offer a higher data rate.

Optimistic Unchoking

• Goal: to discover better trading partners.

Advantages of High Upload Rate

• A high upload rate leads to finding better trading partners, facilitating faster file download.

Distributed Hash Tables (DHTs): Introduction

• DHTs are P2P applications used for storing distributed databases.

Hash Tables: Basics

• A simple database consists of key-value pairs.
• Example: name + social security number.
• A hash function is applied to the key (e.g., name) to convert it into an integer number, facilitating efficient searching and assignment.
• Keys can be converted to a number to make interpretation simpler.

Distributed Hash Tables: Scalable Key-Value Stores

• DHTs are databases (key-value pairs) distributed across millions of peers.

DHT: Assignment and Searching

• Integer values are mapped to other integer numbers.
• Queries and assignments are made based on integer keys.
• Each peer only knows a small number of other peers and is robust to peer churn.

Assigning Keys to Peers

• Keys are assigned to peers with the closest ID, acting as an immediate successor.
• You give a key to the peer who is closest.
• Example: with an ID space of 0-64, a key of 51 is assigned to peer 60 because it is the closest.
• If a key is 61, then the mapping will be set to 1 since that produces a remainder of 1.
• A modulus calculation will need to be performed.

Circular DHT

• Each peer is only aware of its immediate successor and predecessor.
• Peers must be aware of predecessor and successor.
• Example: If peer 12 needs to find the value associated with key 53, it forwards the query to its successor 13, and so on, until the closest peer (60) is found.
• Relies on transferring values from one peer to the next.
• Resolved in big O of n.
• Problem: Each node must transfer messages

Circular DHT with Shortcuts

• Each peer tracks the IP addresses of its predecessor, successor, and a "shortcut" peer.
• Each peer keeps track of IPs of the above.
• Shortcuts reduce the number of messages needed.
• Complexity with a small neighborhood, is a big o of log n.
• When 4 peers are found within the big o of log n then more shortcuts must be designed to improve efficiency.

Peer Churn Handling

• Peer churn: peers can join or leave at any time.
• Each peer can come or go.
• Each peer knows the addresses of its two successors.
• Peers know two successors.
• Peers periodically ping their two successors to check their liveness, and make sure the 2 successors are still active.
• If a peer detects that its immediate successor has left, it chooses its second successor as its new successor and also adopts the successor of the departed peer.