Building a Distance-Vector Routing Protocol (RIP Implementation)

When Routers Have to Figure It Out Themselves

Manually configuring routes on every router in a network is brittle. One typo breaks connectivity for entire subnets. Add a new device and you’re touching every router config. Networks need a way for routers to discover topology and compute paths without central coordination.

The Routing Information Protocol solves this: routers share what they know with their neighbors, each neighbor adds its own hop count and forwards the information, and after a few exchange rounds the entire network has converged on optimal paths. It’s distributed Bellman-Ford — the algorithm runs across many independent agents simultaneously without any single node having global knowledge.

This tutorial walks through the RIP implementation in router/sr_rt.c, covering how to translate RFC 2453’s wire format into packed C structs, how to implement the Bellman-Ford update correctly, and how to compute the UDP checksum with its pseudo-header requirement.

What You Need Before Diving In

Required knowledge:

• C structs, UDP/IP basics, linked lists, bitwise operations
• Basic graph algorithms (shortest path), network byte order (htons/ntohs)

Reference: RFC 2453 - RIP Version 2

Key files:

• router/sr_protocol.h — RIP packet structure definitions
• router/sr_rt.c — RIP protocol logic (this tutorial)
• router/sr_router.c — how RIP packets are received

What a RIP Packet Looks Like on the Wire

From sr_protocol.h, here’s the exact byte layout the code must produce to comply with RFC 2453:

/* 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;

The __attribute__((packed)) annotation is not optional. Without it, the compiler may add padding bytes between fields for alignment (putting 2-byte values on even addresses, 4-byte values on 4-byte boundaries). Packed structs guarantee the struct layout exactly matches the wire format — critical for network protocols.

All multi-byte integers must be in network byte order (big-endian). On little-endian systems like x86, forgetting a single htonl() call sends the bytes in the wrong order, and the receiving router interprets 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 Short

On big-endian systems, these compile to no-ops. On little-endian, they compile to bswap instructions.

Building a RIP Response Packet

The overall flow: count routing table entries, allocate a buffer for all the protocol layers, fill each header, populate RIP entries, compute checksums, send to all interfaces.

Calculating the packet size:

void send_rip_response(struct sr_instance *sr) 
{
    int num_entries = 0;
    struct sr_rt* rt = sr->routing_table;
    while (rt != NULL) {
        num_entries++;
        rt = rt->next;
    }
    
    /* 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) +
                    sizeof(sr_ip_hdr_t) +
                    sizeof(sr_udp_hdr_t) +
                    sizeof(sr_rip_hdr_t) +
                    rip_entry_size;
    
    uint8_t *packet = malloc(total_len);
    memset(packet, 0, total_len);  // Zero everything first

Zeroing with memset before filling isn’t paranoia — it’s required. Network protocols are strict about reserved fields being zero. Sending random stack garbage in “reserved” positions may cause some routers to reject your packet. It also prevents information leakage from uninitialized memory.

Filling the Ethernet, IP, and UDP headers follows the same pattern: cast a pointer to the struct type at the correct offset, fill each field, remember byte order conversions for multi-byte values.

    sr_ip_hdr_t *ip_hdr = (sr_ip_hdr_t *)(packet + sizeof(sr_ethernet_hdr_t));
    ip_hdr->ip_v = 4;
    ip_hdr->ip_hl = 5;
    ip_hdr->ip_len = htons(total_len - sizeof(sr_ethernet_hdr_t));
    ip_hdr->ip_off = htons(0x4000);  // Don't Fragment
    ip_hdr->ip_ttl = 64;
    ip_hdr->ip_p = 17;  // UDP
    ip_hdr->ip_src = iface->ip;
    ip_hdr->ip_dst = htonl(0xE0000009);  // 224.0.0.9 — RIP multicast
    ip_hdr->ip_sum = 0;
    ip_hdr->ip_sum = cksum(ip_hdr, sizeof(sr_ip_hdr_t));

The checksum timing is important: set the checksum field to zero before calling cksum(). The checksum algorithm includes the checksum field itself in its calculation, so it must be zero during computation.

Populating RIP entries iterates the routing table:

    sr_rip_entry_t *rip_entry = (sr_rip_entry_t *)(rip_hdr + 1);
    rt = sr->routing_table;
    int i = 0;
    while (rt != NULL) {
        rip_entry[i].afi = htons(2);           // Address Family: IP
        rip_entry[i].zero1 = 0;
        rip_entry[i].ip = rt->dest.s_addr;     // Already in network byte order
        rip_entry[i].mask = rt->mask.s_addr;   // Already in network byte order
        rip_entry[i].next_hop = 0;
        rip_entry[i].metric = htonl(rt->metric); // Plain uint32_t, needs conversion
        rt = rt->next;
        i++;
    }

rt->dest.s_addr and rt->mask.s_addr are struct in_addr types from the routing table — they’re already stored in network byte order. Don’t call htonl() on them. metric is a plain uint32_t stored in host order, so it does need conversion. Mixing these up is one of the most common byte-order bugs.

The UDP Checksum: Why It Includes IP Header Fields

UDP checksums are unusual because they include parts of the IP header — specifically the source and destination IP addresses, the protocol number, and the UDP length. This creates a “pseudo-header” that’s used only for checksum calculation and never actually transmitted. The purpose is to detect if a packet was misrouted due to IP header corruption mid-flight.

uint16_t udp_cksum(sr_ip_hdr_t* ip_header) 
{
    struct {
        uint32_t src_ip;
        uint32_t dst_ip;
        uint8_t  zero;
        uint8_t  protocol;
        uint16_t udp_len;
    } __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;
    
    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;
    
    int pseudo_size = sizeof(pseudo_hdr);
    int udp_total_len = ntohs(udp->udp_len);
    int total_size = pseudo_size + udp_total_len;
    
    uint8_t* checksum_buffer = malloc(total_size);
    memcpy(checksum_buffer, &pseudo_hdr, pseudo_size);
    memcpy(checksum_buffer + pseudo_size, udp, udp_total_len);
    
    uint16_t result = cksum(checksum_buffer, total_size);
    free(checksum_buffer);
    return result;
}

Receiving RIP Updates: The Bellman-Ford Step

When we receive a RIP packet, we update our routing table if we learn better paths. The Bellman-Ford formula is: new metric = announced metric + 1. If that’s better than what we currently know, update the entry.

void update_route_table(struct sr_instance *sr, 
                       uint8_t *packet, 
                       unsigned int len, 
                       char *interface) 
{
    /* Parse headers to reach RIP payload */
    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));
    
    if (rip_hdr->command != 2) return;  // Only process responses
    
    int udp_payload_len = ntohs(udp_hdr->udp_len) - sizeof(sr_udp_hdr_t);
    int num_entries = (udp_payload_len - sizeof(sr_rip_hdr_t)) / sizeof(sr_rip_entry_t);
    
    sr_rip_entry_t *entries = (sr_rip_entry_t *)(rip_hdr + 1);
    
    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);
        
        uint32_t new_metric = announced_metric + 1;
        if (new_metric > 15) new_metric = 16;  // 16 = infinity in RIP
        
        /* Look up this destination in our 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 with the superior path */
            existing->gw.s_addr = ip_hdr->ip_src;
            existing->metric = new_metric;
            strcpy(existing->interface, interface);
        }
        /* Worse or equal route — ignore */
    }
}

The gateway assignment deserves attention: gw.s_addr = ip_hdr->ip_src. The RIP packet tells us “destination X is N hops away,” but to forward packets there, we need to know which router to send them to next. The sender’s IP address (from the IP header) becomes our next-hop gateway — the neighbor that claims to have a path to the destination.

Problems This Implementation Doesn’t Fully Solve

Count-to-infinity. When a link fails, routers don’t immediately learn the route is dead — it times out slowly. In the meantime, they may start routing around the problem by sending packets in circles, each router incrementing the metric by one per hop. RIP caps the metric at 16 (infinity) to limit how long this goes on, but convergence is still slow. Split horizon prevents the most common form: don’t advertise a route back to the interface you learned it from.

/* 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;
}

Security. The current implementation accepts RIP updates from any source without authentication. An attacker on the same network could send fake updates claiming “route to 10.0.0.0/8 is 1 hop through me,” redirecting all traffic through their machine. RIPv2 supports MD5 authentication (RFC 2082) as a defense. The implementation would check a shared secret before trusting any update.

Route invalidation. There’s no timer that marks routes as stale if we stop hearing about them. RFC 2453 specifies a 180-second timeout — routes not refreshed in that window should be marked with metric 16 (unreachable) and eventually removed. Without this, a dead route stays in the table indefinitely.

Concurrency. The routing table is a linked list modified by both the RIP timer thread and the packet handler thread. This router uses a single-threaded event-driven architecture, so there’s no actual race. In a production router with multi-core packet processing, you’d need lock-free data structures or RCU (Read-Copy-Update) for routing tables.

The deeper skill this implementation teaches is not RIP specifically — it’s how to translate a protocol specification into working C code. RFC 2453 describes wire formats and algorithm behavior; the code bridges that gap with packed structs, byte-order conversions, and checksum calculations. The same approach applies to any protocol: DNS, HTTP/2, gRPC, Bitcoin. Read the RFC, build the structs, handle the byte order, implement the algorithm.