Purpose
The Problem
Imagine you’re building a router for a network with hundreds of devices. How does your router know “to reach subnet 172.16.0.0/24, forward packets through interface eth2”? You could manually configure every route on every router, but this is:
- Brittle: Network changes require updating every device
- Error-Prone: One typo breaks connectivity for entire subnets
- Unscalable: Adding a new subnet requires touching every router config
The real question: How can routers automatically discover network topology and compute optimal paths without central coordination?
The Solution
We’re studying the Routing Information Protocol (RIP) implementation from router/sr_rt.c. This code demonstrates distance-vector routing—a distributed algorithm where routers share their knowledge with neighbors, and each router independently computes best paths.
RIP is defined by RFC 2453, but RFCs are specifications, not code. This tutorial shows how to bridge the gap: translating protocol wire formats, implementing Bellman-Ford path computation, and handling UDP checksum calculations.
Real-World Considerations
This implementation handles real-world constraints:
- Binary Protocol Compliance: Exact byte layouts matching RFC packet formats
- Network Byte Order: Big-endian integers for cross-platform compatibility
- UDP Checksum with Pseudo-Header: Correct IP header validation for transport layer
- Bellman-Ford with Split Horizon: Preventing routing loops in distributed systems
Prerequisites & Tooling
Knowledge Base
- Required: C structs, UDP/IP basics, linked lists, bitwise operations
- Helpful: Basic graph algorithms (shortest path), network byte order (htons/ntohs)
- Reference: RFC 2453 - RIP Version 2
Environment
From the project’s configuration:
# Compiler
GCC with network byte order macros (htonl, ntohl)
# Dependencies
<arpa/inet.h> # For byte order conversions
<sys/socket.h> # For socket operations
<netinet/in.h> # For IP structuresKey Files to Study
router/sr_protocol.h- RIP packet structure definitionsrouter/sr_rt.c- RIP protocol logic (this tutorial)router/sr_router.c- How RIP packets are received
High-Level Architecture
The Distance-Vector Algorithm
RIP implements the Bellman-Ford algorithm in a distributed fashion:
graph TB
subgraph "Router R1 Knowledge"
R1[R1's Routing Table]
R1 --> |"Subnet A: 0 hops (directly connected)"| A[10.0.1.0/24]
R1 --> |"Subnet B: 1 hop via R2"| B[192.168.2.0/24]
R1 --> |"Subnet C: 2 hops via R2"| C[172.16.0.0/16]
end
subgraph "RIP Update Process"
Timer[Every 30 seconds] --> BuildPacket[Build RIP Response]
BuildPacket --> |"My routes + metrics"| UDP[UDP packet to 224.0.0.9:520]
UDP --> R2[Neighbor Router R2]
UDP --> R3[Neighbor Router R3]
end
subgraph "Receiving Updates"
R2 --> Receive[Receive RIP packet]
Receive --> Parse[Parse each route entry]
Parse --> BellmanFord["metric_new = announced_metric + 1"]
BellmanFord --> Compare{Better than current?}
Compare -->|Yes| Update[Update routing table]
Compare -->|No| Ignore[Ignore]
end
Gossip Network for Directions
Imagine asking for directions in a small town:
- Direct Knowledge: “The bakery is 2 blocks north” (metric = 2, directly connected)
- Learned Knowledge: Your neighbor says “I can get to the library in 5 blocks.” You add this to your mental map as “Library: 6 blocks (5 + 1 to reach my neighbor)”
- Updates: Every hour, you chat with neighbors and update your mental map with better routes
RIP routers gossip routing information exactly this way, except:
- “Blocks” = hop count (number of routers to traverse)
- “Every hour” = Every 30 seconds
- “Neighbor” = Directly connected router interface
Implementation
Part 1: RIP Packet Structure (The Wire Format)
Goal: Understand the exact byte layout we must produce to comply with RFC 2453.
From sr_protocol.h, here’s the RIP packet format:
/* RIP Protocol Header */
typedef struct {
uint8_t command; /* 1 = Request, 2 = Response */
uint8_t version; /* Always 2 for RIPv2 */
uint16_t zero; /* Must be zero (padding/reserved) */
} __attribute__((packed)) sr_rip_hdr_t;
/* Each route entry in the RIP packet (20 bytes) */
typedef struct {
uint16_t afi; /* Address Family Identifier (2 for IP) */
uint16_t zero1; /* Padding */
uint32_t ip; /* Destination IP address */
uint32_t mask; /* Subnet mask */
uint32_t next_hop; /* Next hop IP (usually 0.0.0.0) */
uint32_t metric; /* Hop count (1-15, 16 = infinity) */
} __attribute__((packed)) sr_rip_entry_t;🔵 Deep Dive - The __attribute__((packed)):
Without this, the compiler might add padding bytes for alignment (e.g., putting 2-byte boundaries on even addresses). Packed structs guarantee the struct layout exactly matches the wire format—critical for network protocols.
Here’s what a complete RIP packet looks like in memory:
Byte Offset │ Field │ Value (hex) │ Meaning
────────────┼─────────────────┼──────────────┼─────────────────────
0x00 │ command │ 02 │ RIP Response
0x01 │ version │ 02 │ RIPv2
0x02-0x03 │ zero │ 00 00 │ Reserved
────────────┼─────────────────┼──────────────┼─────────────────────
0x04-0x05 │ afi │ 00 02 │ IP (family = 2)
0x06-0x07 │ zero1 │ 00 00 │ Padding
0x08-0x0B │ ip │ C0 A8 02 00 │ 192.168.2.0
0x0C-0x0F │ mask │ FF FF FF 00 │ 255.255.255.0 (/24)
0x10-0x13 │ next_hop │ 00 00 00 00 │ 0.0.0.0 (unused)
0x14-0x17 │ metric │ 00 00 00 01 │ 1 hop
────────────┼─────────────────┼──────────────┼─────────────────────
(Repeat entry structure for each route up to 25 entries max per packet)🔴 Danger: Notice all multi-byte integers are in network byte order (big-endian). If you forget htonl() conversions, your packet will be gibberish on little-endian systems (x86, ARM).
Part 2: Building a RIP Response Packet
Goal: Construct a UDP packet containing our routing table to broadcast to neighbors.
High-Level Flow:
- Count how many routes we have
- Allocate buffer for Ethernet + IP + UDP + RIP headers + entries
- Fill in each header layer
- Populate RIP entries from our routing table
- Compute checksums
- Send to all interfaces
Let’s break down the actual implementation from sr_rt.c:
Step 2.1: Calculate Packet Size
void send_rip_response(struct sr_instance *sr)
{
/* Count entries in our routing table */
int num_entries = 0;
struct sr_rt* rt = sr->routing_table;
while (rt != NULL) {
num_entries++;
rt = rt->next;
}
/* Calculate total packet size:
Ethernet(14) + IP(20) + UDP(8) + RIP Header(4) + N * Entry(20) */
int rip_entry_size = num_entries * sizeof(sr_rip_entry_t);
int total_len = sizeof(sr_ethernet_hdr_t) + // 14 bytes
sizeof(sr_ip_hdr_t) + // 20 bytes
sizeof(sr_udp_hdr_t) + // 8 bytes
sizeof(sr_rip_hdr_t) + // 4 bytes
rip_entry_size; // 20 * N bytes
/* Allocate heap buffer for entire packet */
uint8_t *packet = malloc(total_len);
memset(packet, 0, total_len); // Zero everything first🔵 Deep Dive - Why memset to zero?
Network protocols are paranoid about uninitialized memory. If you send random stack garbage in “reserved” fields, some routers may reject your packet. Zeroing ensures compliance and prevents information leakage.
Step 2.2: Fill Ethernet Header
/* Cast pointer to Ethernet header struct for easy field access */
sr_ethernet_hdr_t *eth_hdr = (sr_ethernet_hdr_t *)packet;
/* Destination MAC: Broadcast (FF:FF:FF:FF:FF:FF) */
memset(eth_hdr->ether_dhost, 0xFF, ETHER_ADDR_LEN);
/* Source MAC: This interface's MAC address */
struct sr_if *iface = sr->if_list; // We'll iterate interfaces later
memcpy(eth_hdr->ether_shost, iface->addr, ETHER_ADDR_LEN);
/* EtherType: 0x0800 = IPv4 (network byte order!) */
eth_hdr->ether_type = htons(0x0800);Step 2.3: Fill IP Header
sr_ip_hdr_t *ip_hdr = (sr_ip_hdr_t *)(packet + sizeof(sr_ethernet_hdr_t));
/* IP Version 4, Header Length 5 (20 bytes) */
ip_hdr->ip_v = 4;
ip_hdr->ip_hl = 5;
/* Type of Service: Routine (0) */
ip_hdr->ip_tos = 0;
/* Total Length: IP header + UDP + RIP payload */
ip_hdr->ip_len = htons(total_len - sizeof(sr_ethernet_hdr_t));
/* Identification: Increment counter for fragmentation tracking */
static uint16_t ip_id = 0;
ip_hdr->ip_id = htons(ip_id++);
/* Flags: Don't Fragment (0x4000) */
ip_hdr->ip_off = htons(0x4000);
/* TTL: 64 hops (standard default) */
ip_hdr->ip_ttl = 64;
/* Protocol: 17 = UDP */
ip_hdr->ip_p = 17;
/* Source IP: This interface's IP address */
ip_hdr->ip_src = iface->ip;
/* Destination IP: RIP multicast address 224.0.0.9 */
ip_hdr->ip_dst = htonl(0xE0000009); // 224.0.0.9 in hex
/* Checksum placeholder (will calculate after all fields set) */
ip_hdr->ip_sum = 0;
ip_hdr->ip_sum = cksum(ip_hdr, sizeof(sr_ip_hdr_t));🔵 Deep Dive - The Checksum Timing:
Notice we set ip_sum = 0 before calling cksum(). This is mandatory! The checksum algorithm includes the checksum field itself, which must be zero during calculation. After computing, we write the result back into that field.
Step 2.4: Fill UDP Header
sr_udp_hdr_t *udp_hdr = (sr_udp_hdr_t *)(packet +
sizeof(sr_ethernet_hdr_t) +
sizeof(sr_ip_hdr_t));
/* Source Port: RIP uses 520 for both source and destination */
udp_hdr->udp_sport = htons(520);
/* Destination Port: 520 */
udp_hdr->udp_dport = htons(520);
/* Length: UDP header + RIP payload */
udp_hdr->udp_len = htons(sizeof(sr_udp_hdr_t) +
sizeof(sr_rip_hdr_t) +
rip_entry_size);
/* Checksum: More complex - includes pseudo-header (explained below) */
udp_hdr->udp_sum = 0;
udp_hdr->udp_sum = udp_cksum(ip_hdr); // Custom functionStep 2.5: Fill RIP Header and Entries
sr_rip_hdr_t *rip_hdr = (sr_rip_hdr_t *)(packet +
sizeof(sr_ethernet_hdr_t) +
sizeof(sr_ip_hdr_t) +
sizeof(sr_udp_hdr_t));
/* RIP Header */
rip_hdr->command = 2; // 2 = Response (unsolicited update)
rip_hdr->version = 2; // RIPv2
rip_hdr->zero = 0; // Reserved field
/* Pointer to first RIP entry (immediately after RIP header) */
sr_rip_entry_t *rip_entry = (sr_rip_entry_t *)(rip_hdr + 1);
/* Iterate through our routing table and add each route */
rt = sr->routing_table;
int i = 0;
while (rt != NULL) {
rip_entry[i].afi = htons(2); // Address Family: IP
rip_entry[i].zero1 = 0; // Padding
rip_entry[i].ip = rt->dest.s_addr; // Destination network
rip_entry[i].mask = rt->mask.s_addr; // Subnet mask
rip_entry[i].next_hop = 0; // Unused in RIPv2
rip_entry[i].metric = htonl(rt->metric); // Hop count
rt = rt->next;
i++;
}🔴 Danger - Byte Order Mistakes:
Notice rt->dest.s_addr and rt->mask.s_addr are already in network byte order (they’re struct in_addr types from our routing table). We don’t call htonl() on them! But metric is a plain uint32_t, so we must convert it.
Part 3: The UDP Checksum (The Tricky Bit)
Goal: Compute a checksum that includes a “pseudo-header” for transport-layer integrity.
UDP checksums are unique because they include parts of the IP header to validate source/destination IPs:
uint16_t udp_cksum(sr_ip_hdr_t* ip_header)
{
/* Step 1: Build the pseudo-header (12 bytes) */
struct {
uint32_t src_ip; // Source IP (from IP header)
uint32_t dst_ip; // Destination IP (from IP header)
uint8_t zero; // Always 0
uint8_t protocol; // Protocol number (17 for UDP)
uint16_t udp_len; // UDP length (from UDP header)
} __attribute__((packed)) pseudo_hdr;
pseudo_hdr.src_ip = ip_header->ip_src;
pseudo_hdr.dst_ip = ip_header->ip_dst;
pseudo_hdr.zero = 0;
pseudo_hdr.protocol = 17; // UDP
/* Get pointer to UDP header (immediately after IP header) */
sr_udp_hdr_t* udp = (sr_udp_hdr_t*)((uint8_t*)ip_header +
sizeof(sr_ip_hdr_t));
pseudo_hdr.udp_len = udp->udp_len;
/* Step 2: Calculate total checksum buffer size */
int pseudo_size = sizeof(pseudo_hdr);
int udp_total_len = ntohs(udp->udp_len);
int total_size = pseudo_size + udp_total_len;
/* Step 3: Build combined buffer */
uint8_t* checksum_buffer = malloc(total_size);
memcpy(checksum_buffer, &pseudo_hdr, pseudo_size);
memcpy(checksum_buffer + pseudo_size, udp, udp_total_len);
/* Step 4: Compute standard Internet checksum */
uint16_t result = cksum(checksum_buffer, total_size);
free(checksum_buffer);
return result;
}🔵 Deep Dive - Why Pseudo-Headers?
The UDP header doesn’t contain source/destination IPs (those are in the IP header). To detect if a packet was misrouted (IP header corrupted mid-flight), the UDP checksum includes IP addresses in its calculation. If you receive a UDP packet claiming to be from 10.0.0.1 but the pseudo-header checksum fails, you know the IP header was corrupted.
Part 4: Receiving and Processing RIP Updates (Bellman-Ford)
Goal: When we receive a RIP packet, update our routing table if we learn better paths.
void update_route_table(struct sr_instance *sr,
uint8_t *packet,
unsigned int len,
char *interface)
{
/* Parse packet headers to get to RIP payload */
sr_ethernet_hdr_t *eth_hdr = (sr_ethernet_hdr_t *)packet;
sr_ip_hdr_t *ip_hdr = (sr_ip_hdr_t *)(packet + sizeof(sr_ethernet_hdr_t));
sr_udp_hdr_t *udp_hdr = (sr_udp_hdr_t *)(packet +
sizeof(sr_ethernet_hdr_t) +
sizeof(sr_ip_hdr_t));
sr_rip_hdr_t *rip_hdr = (sr_rip_hdr_t *)(packet +
sizeof(sr_ethernet_hdr_t) +
sizeof(sr_ip_hdr_t) +
sizeof(sr_udp_hdr_t));
/* Ignore RIP requests (command = 1), only process responses */
if (rip_hdr->command != 2) {
return;
}
/* Calculate number of route entries in this packet */
int udp_payload_len = ntohs(udp_hdr->udp_len) - sizeof(sr_udp_hdr_t);
int rip_data_len = udp_payload_len - sizeof(sr_rip_hdr_t);
int num_entries = rip_data_len / sizeof(sr_rip_entry_t);
/* Get pointer to first RIP entry */
sr_rip_entry_t *entries = (sr_rip_entry_t *)(rip_hdr + 1);
/* Process each advertised route */
for (int i = 0; i < num_entries; i++) {
uint32_t dest_ip = entries[i].ip;
uint32_t mask = entries[i].mask;
uint32_t announced_metric = ntohl(entries[i].metric);
/* Bellman-Ford: Add 1 hop to reach this destination via the sender */
uint32_t new_metric = announced_metric + 1;
/* Prevent infinity (RIP max metric is 15, 16 = unreachable) */
if (new_metric > 15) {
new_metric = 16;
}
/* Look up this destination in our current routing table */
struct sr_rt *existing = NULL;
struct sr_rt *rt = sr->routing_table;
while (rt != NULL) {
if (rt->dest.s_addr == dest_ip && rt->mask.s_addr == mask) {
existing = rt;
break;
}
rt = rt->next;
}
if (existing == NULL) {
/* NEW ROUTE - We didn't know about this destination */
struct in_addr dest, gw, mask_addr;
dest.s_addr = dest_ip;
mask_addr.s_addr = mask;
gw.s_addr = ip_hdr->ip_src; // Gateway = sender of this RIP packet
sr_add_rt_entry(sr, dest, gw, mask_addr, new_metric, interface);
} else if (new_metric < existing->metric) {
/* BETTER ROUTE - Update existing entry with superior path */
existing->gw.s_addr = ip_hdr->ip_src;
existing->metric = new_metric;
strcpy(existing->interface, interface);
} else {
/* WORSE OR EQUAL ROUTE - Ignore */
}
}
}🔵 Deep Dive - The Gateway Assignment:
Notice we set gw.s_addr = ip_hdr->ip_src. This is critical! The RIP packet tells us “destination X is N hops away,” but to forward packets there, we must know which router to send them to. The sender’s IP address (from the IP header) becomes our next-hop gateway.
Under the Hood
Network Byte Order: Why Big-Endian Wins
Consider sending the number 305,419,896 (0x12345678 in hex):
Little-Endian (x86) Memory Layout:
Address: 0x1000 0x1001 0x1002 0x1003
Value: 0x78 0x56 0x34 0x12 (least significant byte first)Big-Endian (Network) Wire Format:
Byte 0: 0x12 (most significant byte first)
Byte 1: 0x34
Byte 2: 0x56
Byte 3: 0x78If we forget htonl(), a little-endian machine sends 0x78563412 on the wire, which the receiver interprets as a completely different number!
The Conversion Functions:
htonl(x) // Host-to-Network Long (32-bit)
htons(x) // Host-to-Network Short (16-bit)
ntohl(x) // Network-to-Host Long
ntohs(x) // Network-to-Host ShortOn big-endian systems (some MIPS, older ARM), these are no-ops (compiled to nothing). On little-endian (x86, modern ARM), they compile to bswap instructions.
The Bellman-Ford Complexity
Distance-vector routing is based on the Bellman-Ford shortest path algorithm:
Formula: dist[v] = min(dist[v], dist[u] + weight(u,v))
In RIP terms:
dist[v]= Our current metric to destinationdist[u]= Sender’s metric to destinationweight(u,v)= 1 (cost to reach sender, always 1 hop)
Time Complexity: O(V × E) where V = number of destinations, E = number of neighbors
For a typical small network:
- V ≈ 20 subnets
- E ≈ 3 neighbors
- Updates every 30 seconds
- Cost: ~60 comparisons per update cycle (trivial)
🔵 Why Not Dijkstra?
Dijkstra requires global topology knowledge. In distributed routing, each router only knows its neighbors. Bellman-Ford works with partial information, making it ideal for distributed systems despite being slower than Dijkstra.
Memory Allocations: Heap vs Stack
For the RIP packet:
uint8_t *packet = malloc(total_len); // HeapWhy Heap?
total_lencan be up to ~534 bytes (25 routes × 20 bytes)- Stack frames are typically 4-8KB limit
- We need to pass this pointer to
send(), which may be async
Alternative (Stack):
uint8_t packet[534]; // Fixed maximum sizeThis would work but wastes stack space when we have fewer routes. The heap allocation is more flexible.
Edge Cases & Pitfalls
Concurrency: RIP Timer vs Packet Reception
The Race Condition:
Thread 1 (RIP Timer): Thread 2 (Packet Handler):
────────────────────── ─────────────────────────
send_rip_response()
├─ Iterate rt table
│ update_route_table()
│ ├─ Modify rt table
│ └─ Add new entry
└─ Read rt->next ──────> SEGFAULT (invalid pointer)The Fix (from code):
/* All routing table modifications are single-threaded */
// The main thread handles both RIP timer and packet reception sequentially
// No mutex needed because there's no true parallelism🔵 Educational Note: This router uses event-driven single-threaded architecture. In production routers with multicore packet processing, you’d need lock-free data structures or RCU (Read-Copy-Update) for routing tables.
Security: RIP Spoofing
Attack: Malicious actor sends fake RIP updates claiming “192.168.1.0/24 is 1 hop through me.”
Current Vulnerability:
/* The code accepts ANY RIP packet from ANY source */
if (rip_hdr->command == 2) {
update_route_table(sr, packet, len, interface); // Trusts blindly
}Production Hardening:
/* Only accept RIP from known neighbors */
struct sr_if *iface = sr_get_interface(sr, interface);
struct known_neighbor *neighbor = lookup_neighbor(iface, ip_hdr->ip_src);
if (neighbor == NULL) {
log("Ignoring RIP from unknown source %s", inet_ntoa(ip_hdr->ip_src));
return; // Drop packet
}
/* RIPv2 supports MD5 authentication (RFC 2082) */
if (!verify_rip_auth(rip_hdr, neighbor->shared_secret)) {
log("Authentication failed for RIP packet");
return;
}Routing Loops: The Count-to-Infinity Problem
Scenario:
- Router A announces: “Network X is 1 hop”
- Router B learns: “Network X is 2 hops via A”
- Link between A and X fails
- A hears from B: “X is 2 hops” → A updates to 3 hops
- B hears from A: “X is 3 hops” → B updates to 4 hops
- (Infinite loop continues…)
The Fix (Split Horizon):
void send_rip_response_to_interface(struct sr_instance *sr,
struct sr_if *outgoing_iface)
{
struct sr_rt *rt = sr->routing_table;
while (rt != NULL) {
/* Don't advertise a route back to the interface we learned it from */
if (strcmp(rt->interface, outgoing_iface->name) == 0) {
rt = rt->next;
continue; // Skip this route
}
/* Add to RIP packet */
add_rip_entry(packet, rt->dest, rt->mask, rt->metric);
rt = rt->next;
}
}This prevents B from telling A about routes that A originally announced to B.
Failure: Missing Convergence Detection
The Problem:
After a link failure, routes don’t immediately disappear—they time out. During convergence, packets may black-hole.
Current Limitation: The code has no “route invalidation” timer. In production RIP:
struct sr_rt {
// ... existing fields ...
time_t last_updated; /* When we last heard about this route */
int timeout; /* 180 seconds = route timeout */
};
/* In timeout sweeper thread */
void check_route_timeouts(struct sr_instance *sr) {
struct sr_rt *rt = sr->routing_table;
while (rt != NULL) {
if (difftime(time(NULL), rt->last_updated) > 180) {
/* Route expired - set to infinity */
rt->metric = 16;
}
rt = rt->next;
}
}Conclusion
What You Actually Learned
This wasn’t just “implement RIP.” You learned:
-
Binary Protocol Engineering: How to translate RFC wire formats into packed C structs with exact byte layouts—a skill applicable to any protocol (HTTP/2, gRPC, DNS, Bitcoin).
-
Distributed Algorithms: Bellman-Ford running across multiple independent agents without coordination—the same principle behind BGP (internet routing) and blockchain consensus.
-
Layer Composition: How protocols stack (Ethernet → IP → UDP → RIP), and how each layer’s checksum provides layered integrity verification.
-
Byte Order Paranoia: The critical difference between host and network byte order, and how forgetting one
htonl()breaks cross-platform compatibility.
Real-World Applications
This exact pattern appears in:
- BGP Implementations: Same distance-vector concept, but path-vector (stores entire AS path)
- IoT Mesh Networks: Low-power devices use RIP-like protocols for auto-configuration
- Docker Overlay Networks: Container orchestrators use gossip protocols descended from distance-vector routing
- Distributed Databases: Cassandra’s gossip protocol uses similar state dissemination
Next Steps
- Extend It: Implement RIPv2 authentication (MD5 signatures)
- Optimize It: Use hash tables for O(1) route lookup instead of O(n) linked list
- Visualize It: Add logging to show convergence in real-time (how routing tables stabilize)
- Compare It: Implement OSPF (link-state) and measure convergence time differences
The protocol is ancient (1988). The principles are eternal: distributed state synchronization through periodic gossip.
