15-440 & 15-441: Distributed Systems and Networks

Raft (15-440)

Reimplementing the distributed log consensus protocol - Raft.

Raft Routine

Live Sequence Protocol (LSP) (15-440)

A distributed transport layer protocol with both features from TCP and UDP.

The Live Sequence Protocol (LSP) was developed as part of this project to provide a reliable client-server communication layer over the UDP protocol. UDP, while efficient for fast data transmission, lacks the built-in reliability mechanisms present in TCP. To address this, LSP incorporates features to overcome common issues in UDP-based communication, such as packet loss, duplication, and corruption, thereby enabling error-free, sequential message delivery.

• Reliable Message Delivery: The protocol uses acknowledgment (Ack) and cumulative acknowledgment (CAck) messages to confirm message delivery and maintain the correct sequence, ensuring all messages are received in order.
• Sliding Window Flow Control: A sliding window mechanism controls the flow of unacknowledged messages, preventing network congestion by aligning message transmission with acknowledgment rates.
• Epoch-Based Retransmission System: By utilizing epoch timers, LSP detects lost messages and initiates retransmissions. This system also manages connection timeouts and sends regular heartbeat signals to maintain active connections.
• Data Integrity Verification: LSP applies a checksum to every message, allowing detection and rejection of corrupted messages. This feature ensures that only complete and accurate data is processed, maintaining high data integrity.

The result is a robust protocol layer that combines the speed of UDP with the reliability of TCP, suitable for applications requiring reliable, real-time client-server communication.

TCP + TCP Reno (15-441)

TCP protocol implemented in C, with Reno congestion control.

TCP is a transport layer protocol that enables processes on different devices to communicate reliably. TCP’s beauty stems from its ability to give applications a simple abstraction with strong guarantees, even though the underlying network only provides best-effort delivery.

This project includes the following components of TCP:

• Start and Teardown: TCP three-way handshake and connection teardown via FIN
• Sliding Window: Transmit multiple packets before an ACK by using a fixed window size
• Reliable Retransmission (include option to use either Go-Back-N or Selective Retransmit): Retransmit packets after a timeout (Go-Back-N and Selective Retransmit), on duplicate ACKs (Selective Retransmit), etc.
• Flow Control: Advertised window
• Congestion Control: TCP Reno

TCP Routine

TCP Reno

Liso Server - HTTP 1.1 (15-441)

A Liso web server supporting HTTP 1.1 at the application layer, and a smart client able to parallelly process and request files based on a lineage graph.

Liso HTTP 1.1 Server Implementation

• A web server capable of handling HTTP requests (GET, HEAD, etc.) from multiple clients concurrently.
• Implements robust error handling (e.g., HTTP 404, HTTP 503, HTTP 400) and overload protection.
• Efficient handling of concurrent connections using the poll() system call.

Smart Client Implementation

• A custom client replacing standard web browsers to interact with the server.
• Implements HTTP/1.1 optimizations such as pipelining (concurrent inflight requests) and parallel connections.

Mix Network - Mixnet (15-441)

A distributed network layer algorithm to establish reliable, efficient, and secure communication between nodes in the network.

The Mix Network (Mixnet) project aims to create a privacy-preserving network overlay that enables anonymous communication by obscuring both the message content and the identities of communicating parties.

Key Features

• Encryption: Ensures that any intercepted messages are unintelligible without proper decryption, keeping message contents secure.
• Redirection: Messages are relayed through intermediate nodes to hide the source and destination, making it difficult for observers to link senders and recipients.
• Mixing: Nodes delay and batch messages before forwarding, further concealing the source-destination pairings from observers.

Network Architecture

• Composed of interconnected nodes that operate as both sources and forwarders, Mixnet forms an undirected graph where nodes are linked to each other.
• Each node uses a combination of shortest-path and random routing strategies to relay messages, balancing efficiency and privacy.
• Mixnet uses the Spanning Tree Protocol (STP) to create a loop-free topology, enabling safe and efficient broadcast of control messages across the network.

Packet Structure
Mixnet packets contain a standardized header and payload, with various packet types (STP, FLOOD, LSA, DATA, PING) supporting routing, control, and communication functions.