In-Depth Analysis of the Linux Routing Table Establishment Process

1. Working Principle

The routing table is a core component of the Linux networking stack, used to determine the forwarding path of packets. The establishment process is divided into three levels:

Kernel Initialization Stage

Automatically create the local routing table (local table)
Generate direct routes for each network interface (scope link)
Local address routes (scope host)

User Space Configuration

Static routes: Added via ip route or configuration files
Dynamic routes: Injected by daemons (e.g., BIRD/FRR)

Kernel Decision Mechanism

Based on the Longest Prefix Match (LPM) algorithm
Multi-routing table support (policy routing)
Routing cache (merged into the main table)

2. Implementation Mechanism and Code Framework

Core Path: net/ipv4/route.c and net/ipv4/fib_*.c

Detailed Process Analysis:

User Space Initiates Request

Send route add request via ip route add command or Netlink API
Message Type: RTM_NEWROUTE (nlmsg_type in netlink message header)

Kernel Receives and Processes

static void rtnetlink_rcv(struct sk_buff *skb)
{
    netlink_rcv_skb(skb, &amp; rtnetlink_rcv_msg);
}

Entry Function: rtnetlink_rcv() (net/core/rtnetlink.c)

Route Addition Process

static int rtm_to_fib_config(struct net *net, struct sk_buff *skb,
    struct nlmsghdr *nlh, struct fib_config *cfg)
{
    // Parse netlink attributes: destination network, gateway, device, etc.
}

Core Function: rtm_to_fib_config() (net/ipv4/fib_frontend.c)

Routing Table Operations

struct fib_table *fib_get_table(struct net *net, u32 id)
{
    // Get routing table by ID (main table ID=254)
}

Routing Table Selection: fib_get_table() (net/ipv4/fib_trie.c)

Trie Tree Insertion

static int fib_insert_node(struct trie *t, struct key_vector *tp,
    struct fib_alias *new, t_key key)
{
    // Insert new node in LC-Trie
    // Handle node splitting and merging
}

Core Algorithm: trie_insert() (net/ipv4/fib_trie.c)

Routing Information Update

struct fib_info *fib_create_info(struct fib_config *cfg)
{
    // Allocate fib_info structure
    // Set next hop (fib_nh), scope, etc.
}

Create Routing Information Structure: fib_create_info() (net/ipv4/fib_semantics.c)

Notification Mechanism

static void rtmsg_fib(int event, __be32 key, struct fib_alias *fa,
    int dst_len, u32 tb_id, struct nl_info *info)
{
    // Send RTM_NEWROUTE notification via netlink
}

Routing Update Notification: rtmsg_fib() (net/ipv4/fib_frontend.c)

Key Code Flow:

Route Addition Entry: rtnetlink_rcv() (net/core/rtnetlink.c)
Routing Table Operations: fib_table_insert() (net/ipv4/fib_trie.c)
Trie Tree Operations: trie_insert() (net/ipv4/fib_trie.c)
Route Lookup: ip_route_input_slow() (net/ipv4/route.c)

3. Core Data Structures

// Routing table abstraction (include/net/ip_fib.h)
struct fib_table {
    u32         tb_id; // Routing table ID (e.g. RT_TABLE_MAIN)
    int (*tb_lookup)(...); // Lookup function
    struct trie *tb_data; // Trie tree root node
};

// Trie tree node (net/ipv4/fib_trie.c)
struct tnode {
    t_key key; // Key value
    unsigned long pos; // Bit position
    struct tnode __rcu *child[0]; // Child nodes
};

// Routing information (include/net/ip_fib.h)
struct fib_info {
    struct hlist_node fib_hash;
    int              fib_treeref;
    u32              fib_prefsrc; // Preferred source address
    unsigned char    fib_scope; // Scope
    struct fib_nh    fib_nh[0]; // Next hop array
};

// Next hop information
struct fib_nh {
    struct net_device *nh_dev; // Egress device
    u32               nh_gw; // Gateway IP
};

4. Example Code for Adding Routes

#include <arpa/inet.h>
#include <linux/netlink.h>
#include <linux/rtnetlink.h>
#include <net/if.h>
#include <string.h>
#include <sys/socket.h>
#include <unistd.h>

// Create netlink route message
void add_route(const char *dst, int prefixlen, const char *gw, const char *dev) {
    int sock = socket(AF_NETLINK, SOCK_RAW, NETLINK_ROUTE);
    struct {
        struct nlmsghdr nh;
        struct rtmsg rt;
        char buf[1024];
    } req = {0};

    // Initialize netlink header
    req.nh.nlmsg_len = NLMSG_LENGTH(sizeof(struct rtmsg));
    req.nh.nlmsg_flags = NLM_F_REQUEST | NLM_F_CREATE | NLM_F_EXCL;
    req.nh.nlmsg_type = RTM_NEWROUTE;

    // Set route attributes
    req.rt.rtm_family = AF_INET;
    req.rt.rtm_dst_len = prefixlen;
    req.rt.rtm_table = RT_TABLE_MAIN;
    req.rt.rtm_scope = RT_SCOPE_UNIVERSE;
    req.rt.rtm_protocol = RTPROT_STATIC;
    req.rt.rtm_type = RTN_UNICAST;

    // Add destination network
    struct rtattr *rta = (struct rtattr *)((char *)&req + NLMSG_ALIGN(req.nh.nlmsg_len));
    rta->rta_type = RTA_DST;
    rta->rta_len = RTA_LENGTH(4);
    inet_pton(AF_INET, dst, RTA_DATA(rta));
    req.nh.nlmsg_len += rta->rta_len;

    // Add gateway or device
    if (gw) {
        rta = (struct rtattr *)((char *)&req + NLMSG_ALIGN(req.nh.nlmsg_len));
        rta->rta_type = RTA_GATEWAY;
        rta->rta_len = RTA_LENGTH(4);
        inet_pton(AF_INET, gw, RTA_DATA(rta));
        req.nh.nlmsg_len += rta->rta_len;
    } else {
        rta = (struct rtattr *)((char *)&req + NLMSG_ALIGN(req.nh.nlmsg_len));
        rta->rta_type = RTA_OIF;
        rta->rta_len = RTA_LENGTH(4);
        int ifindex = if_nametoindex(dev);
        memcpy(RTA_DATA(rta), &ifindex, 4);
        req.nh.nlmsg_len += rta->rta_len;
    }

    // Send to kernel
    send(sock, &req, req.nh.nlmsg_len, 0);
    close(sock);
}

int main() {
    // Add route: destination 10.1.0.0/24 via gateway 192.168.1.1
    add_route("10.1.0.0", 24, "192.168.1.1", NULL);
    return 0;
}

Compile command: gcc route_add.c -o route_add

5. Common Tools and Debugging Commands

Routing Management Tools

# View routing table
ip route show table main
ip -6 route  # IPv6 routes

# Add/Delete routes
ip route add 192.168.2.0/24 via 10.0.0.1 dev eth0
ip route del default via 192.168.1.1

# Policy routing
ip rule add from 192.168.1.100 lookup custom_table

Debugging Commands

# Kernel routing logs
dmesg | grep "IPv4:"

# Route lookup simulation
ip route get 8.8.8.8 from 192.168.1.100 iif eth0

# Routing table statistics
cat /proc/net/stat/rt_cache

# Netlink monitoring
lmon  # Requires loading nlmon driver

Dynamic Debugging

# Enable kernel debugging
echo 8 > /proc/sys/kernel/printk
echo "file net/ipv4/* +p" > /sys/kernel/debug/dynamic_debug/control

# Ftrace tracing
echo function > /sys/kernel/tracing/current_tracer
echo fib_table_lookup > /sys/kernel/tracing/set_ftrace_filter
cat /sys/kernel/tracing/trace_pipe

####6. Key Debugging Techniques

Route Lookup Issues

Check if ip route get output matches expectations
Verify reverse path filtering: sysctl net.ipv4.conf.all.rp_filter
Check routing table ID: ip route show table all

Inconsistent Routing Tables

Compare ip route and cat /proc/net/route (hexadecimal format)
Check the status of routing protocol daemons (e.g., BIRD/FRR)

Kernel Crash Analysis

Use crash tool to inspect fib_info structure
Analyze function call stack in oops logs

7. Performance Optimization

Routing Table Structure Selection

Small-scale networks: Hash table
Large-scale routing: LC-Trie (default in Linux)
Very large scale: Hardware offload (e.g., DPDK)

Routing Cache Strategy

Disable deprecated routing cache: sysctl net.ipv4.route.flush=1
Optimize garbage collection parameters: sysctl net.ipv4.route.gc_timeout

Multi-core Scaling

Use per-core routing tables
Configure RPS (Receive Packet Steering)

By deeply understanding the routing table establishment mechanism, one can effectively diagnose network issues (such as routing black holes and forwarding loops) and optimize routing performance in large network environments. In practical applications, it is necessary to choose between static configuration or dynamic routing protocols (such as OSPF/BGP) based on specific scenarios.