In-Depth Analysis of the Linux Routing Subsystem: Framework, Implementation, and Code Paths

In-Depth Analysis of the Linux Routing Subsystem: Framework, Implementation, and Code Paths

1. Core Framework of the Routing Subsystem
2. Core Framework and Components of the Routing Subsystem
3. Detailed Explanation of the Routing Lookup Process (Taking IPv4 Forwarding as an Example)
4. Implementation Mechanisms of Core Components

1. Routing Policy Database (RPDB)
2. Forwarding Information Base (FIB)
3. Destination Cache (dst_entry)
4. Integration with the Neighbour Subsystem

5. Analysis of Core Path Code

1. Input Path Routing (ip_route_input)
2. Output Path Routing (__ip_route_output_key)
3. FIB Update Operation (fib_table_insert)

6. Key Mechanism Implementation Details

1. Multipath Routing (ECMP)
2. Integration with the Neighbour Subsystem

7. Performance Optimization Mechanisms

1. RCU Lock Optimization
2. Routing Cache Optimization (Historical)

8. Diagnostic Tools and Debugging Interfaces

1. /proc Filesystem Interface
2. ftrace Trace Points

9. Summary Architecture Diagram
Key Implementation Points:

In-Depth Analysis of the Linux Routing Subsystem: Framework, Implementation, and Code Paths

1. Core Framework of the Routing Subsystem

+-----------------------+
|     User Space Tools   |
|   (iproute2, net-tools) |
+----------+------------+
           | Netlink (RTM)
           v
+-----------------------+
|     Netlink Interface  |<---------------------------------+
| (rtnetlink, fib_netns_ops) |                             |
+----------+------------+                             |
           |                                         |
           | Routing Configuration Management       |
           v                                         |
+----------------------+                              |
|  Routing Table Management Subsystem  |                              |
| (fib_frontend.c)     |--+                           |
| - fib_table_insert   |  |                           |
| - fib_table_delete   |  |                           |
+----------+-----------+  |                           |
           |              | Routing Rule Notification   |
           | Routing Rule Operations   v                           |
+----------+-----------+  +----------------------+     |
|  Routing Policy Database (RPDB) |<->| FIB Notification Mechanism (fib_notifier) |
| (fib_rules.c)        |  +----------------------+     |
| - fib_rules_lookup   |                             |
| - fib_default_rule_add|                             |
+----------+------------+                             |
           | Policy Matching                            |
           v                                         |
+----------------------+                              |
|  Forwarding Information Base (FIB)  |<-----------------------------+
| (fib_trie.c)         |
| - fib_find_node      |
| - fib_table_lookup   |
+----------+-----------+
           | LPM Lookup
           v
+----------------------+
|  Routing Entry (fib_info) |
| (fib_semantics.c)    |
| - fib_create_info    |
| - fib_release_info   |
+----------+-----------+
           | Next Hop Information
           v
+----------------------+    +----------------------+
|  Next Hop (fib_nh)   +--->|  Destination Cache (dst_entry) |
| - nh_dev, nh_gw      |    | - input, output      |
+----------------------+    +----------+-----------+
                                       | Association
                                       v
                               +----------------------+
                               |  Neighbour Subsystem (neighbour) |
                               | - neigh_output       |
                               | - neigh_resolve_output|
                               +----------------------+

Now, let’s conduct a detailed analysis of the extremely critical Routing Subsystem in the Linux networking subsystem, covering its framework design and core implementation mechanisms.

Core Tasks of the Routing Subsystem: Determine the next hop for packets entering the kernel network stack (whether generated locally or received from a network interface), i.e., decide which network interface the packet should be sent from, which gateway it should go to (or directly to the target host), and which source IP address to use. It is the foundation for implementing the IP protocol’s “connectionless” and “best-effort” forwarding.

2. Core Framework and Components of the Routing Subsystem

The routing subsystem adopts a layered and modular design, mainly consisting of the following core parts:

Routing Cache (Route Cache) – Historical Component (Removed):

Historical Role: In earlier kernels (before 2.6), to improve performance, the most recently successful routing results (struct rtable) were cached. The cache was hashed based on source/destination IP, TOS, incoming interface, etc., for very fast lookups.
Problems and Removal: With the maturity and widespread use of connection tracking (Netfilter Conntrack), as well as optimizations in the routing lookup algorithm itself (such as LPC-trie), the maintenance overhead of the routing cache (invalidations, synchronizations) exceeded its performance benefits, and it performed poorly under DoS attacks. The modern kernel (3.6+) has completely removed the routing cache. Lookups are now always based on the Forwarding Information Base (FIB).

Forwarding Information Base (FIB):

RT_TABLE_LOCAL (255): Local interface addresses and broadcast addresses (managed automatically by the kernel).
RT_TABLE_MAIN (254): Default Table, where routes added by users via ip route are typically placed.
RT_TABLE_DEFAULT (253): Usually empty.
Other tables (0-252) can be used for policy routing.

Core Data Plane: The FIB is the core data structure of the routing subsystem, storing all valid routing rules currently used by the kernel. It represents the kernel’s “routing table”.
Data Structure Evolution: Early versions used simple hash tables. Modern kernels (2.6+) primarily use a data structure based on the LC-trie (Level Compressed trie) algorithm. This is a highly optimized prefix tree (trie) designed for fast Longest Prefix Match (LPM), which is the core algorithm for IP routing lookups.
Support for Multiple FIB Tables: Linux supports multiple routing tables (up to 255 by default). Each table is identified by a unique numeric ID. The most commonly used are:
fib_lookup: This is the core function that performs LPM lookups. Given a target IP address, it looks for the most specific matching routing entry in the specified FIB table.

Routing Policy Database (RPDB):

Priority (r_priority)： The smaller the number, the higher the priority.
Selectors (r_prefsrc, r_src, r_dst, r_tos, r_iif, r_oif, r_fwmark, r_table, etc.): Match packets based on conditions such as source IP, destination IP, TOS, incoming interface, outgoing interface, firewall marks (fwmark), etc.
Actions (r_action)： The most common is FR_ACT_TO_TBL, indicating that if the rule matches, the routing table specified by the rule (r_table) should be used for FIB lookup. Other actions include FR_ACT_UNREACHABLE, FR_ACT_BLACKHOLE, FR_ACT_PROHIBIT, etc.
r_src_len, r_dst_len: The network mask lengths for source/destination addresses.

Control Plane Decision Maker: The RPDB defines how to choose which routing table to use for lookups. It provides policy-based routing functionality.
struct fib_rule: The core structure of policy rules. Each rule defines:
Lookup Process (fib_rules_lookup): When a routing decision is needed, the kernel traverses all rules in the RPDB in order of priority. Once the first rule matching the current packet attributes (source IP, destination IP, incoming interface, fwmark, etc.) is found, the action specified by that rule is executed (usually to perform an FIB lookup in the specified routing table). If no rules match, the RT_TABLE_MAIN<code> is typically used.

Routing Entry (struct fib_info)：

Prefix (fib_dst, fib_prefsrc)： The target network and mask length of the route, as well as the suggested source IP address (usually used for multihomed hosts).
Type (fib_type)： The type of route (RTN_UNICAST – Unicast, RTN_LOCAL – Local, RTN_BROADCAST, RTN_MULTICAST, RTN_BLACKHOLE, RTN_UNREACHABLE, RTN_PROHIBIT, etc.).
Scope (fib_scope)： The effective range of the route (RT_SCOPE_UNIVERSE – Globally valid, RT_SCOPE_LINK – Valid only on the same link, RT_SCOPE_HOST – Valid only on the local machine).
Next Hop Information (struct fib_nh)： This is the most critical part! A fib_info may contain multiple fib_nh (next hop) structures to support multipath routing (ECMP). Each fib_nh contains:
Associated Neighbour Entry (nh_pcpu_rth_output)： Points to the neighbour subsystem entry corresponding to the next hop (struct neighbour or struct dst_entry), which stores the link-layer address (MAC address) of the gateway (or destination host) and the output function pointer. This establishes the bridge between the routing subsystem and the neighbour subsystem.
Reference Count (fib_clntref)： Manages the reference count for the lifecycle of this structure.
Metric (fib_priority)： The routing priority (the smaller the value, the higher the priority for the same prefix length).

nh_dev： Pointer to the output network device (struct net_device).
nh_gw： The IP address of the gateway (if the route is indirect). For directly connected routes, this field is 0.
nh_weight： Weight (used for weighted ECMP).
nh_flags： Flags (e.g., RTNH_F_ONLINK – Gateway is on the local link).

This is a specific representation of the FIB lookup result. It contains all the key information needed to make routing decisions:
struct fib_result： The return value of the FIB lookup function (fib_lookup). It contains a pointer to the matching fib_info and some additional lookup information (such as routing table ID, rule type, etc.).

Destination Cache (struct dst_entry)：

__refcnt： Reference count.
dev： Output network device.
_metrics： Routing metrics (such as MTU, RTT, etc.).
flags： Flags.
lastuse： Last use timestamp.
input, output： Key function pointers! Define how to handle packets directed to this destination.
neighbour： Points to the corresponding neighbour entry (struct neighbour). This is a key point for the close cooperation between the routing subsystem and the neighbour subsystem. The output function will ultimately call neighbour->output<code> (e.g., <code>neigh_resolve_output or dev_queue_xmit) to send packets.

input： Typically used for the input path, pointing to functions that handle local delivery or forwarding (such as ip_local_deliver or ip_forward).
output： Used for the output path, pointing to the function that actually sends the packet. This function is usually set after resolving the link-layer address through the neighbour subsystem (such as neigh_output). When the routing lookup has just completed, it may point to a generic output function (such as ip_output), which will trigger processing by the neighbour subsystem.

Encapsulation of Routing Results and Output Interface: This is the final product of the routing lookup and a key object for subsequent processing in the network stack (especially for the output path).
Key Members:
struct rtable： This is the IPv4 specific dst_entry subtype, containing IPv4 specific information such as source/destination IP addresses, TOS, routing tags, etc.

Neighbour Subsystem (Neighbour Subsystem – ARP/ND):

If the state is NUD_REACHABLE, directly call neigh->ops->queue_xmit (which usually ends up calling dev_queue_xmit to place the packet in the device queue).
If the state is NUD_NONE or NUD_STALE, call neigh_resolve_output. This function checks whether an ARP request (for IPv4) or Neighbor Solicitation (for IPv6) needs to be sent. If needed, it caches the packet (to neigh->arp_queue) and initiates the address resolution process. Once resolved, the state changes to NUD_REACHABLE, and the cached packet will be sent.
If the state is NUD_FAILED, it usually results in a send failure.

Tight Integration: The routing subsystem determines the next hop’s IP address (gateway or target host) and the output interface. The neighbour subsystem is responsible for resolving this IP address to the corresponding link-layer address (such as Ethernet MAC address).
struct neighbour: Represents a neighbour (a host or router on the same link). It stores the link-layer address, state (NUD_NONE, NUD_INCOMPLETE, NUD_REACHABLE, NUD_STALE, etc.) and the output function pointer (output).
Interaction Process:

The routing lookup obtains a dst_entry (such as rtable).
The kernel attempts to send the packet through dst->output (initially possibly ip_output or ip6_output).
ip_output will call dst_neigh_output.
dst_neigh_output will get or create the neighbour entry associated with the dst_entry.
Based on the neighbour state, call its output method:

3. Detailed Explanation of the Routing Lookup Process (Taking IPv4 Forwarding as an Example)

Packet Reception: The network card driver places the packet into the receive queue via NAPI, triggering the soft interrupt NET_RX_SOFTIRQ which calls net_rx_action.
Protocol Processing (ip_rcv): The network layer processing function ip_rcv is called to perform basic IP header checks.
Routing Decision Entry (ip_route_input_noref / ip_route_input_rcu):

Check if the destination address is a local address? Check the local table (RT_TABLE_LOCAL). If a route of type RTN_LOCAL is found, the packet is destined for the local machine.
Check if forwarding is enabled (net->ipv4.ip_forward)? If not enabled, and the packet is not destined for the local machine, drop it and reply with ICMP destination unreachable.
Execute RPDB Lookup (fib_rules_lookup): Traverse the routing policy rules using the packet’s attributes (source IP, destination IP, incoming interface, TOS, fwmark, etc.).
FIB Lookup (fib_lookup): Perform a longest prefix match lookup in the routing table selected by the RPDB rules (usually the main table), obtaining a fib_result.
Build dst_entry (rt_dst_alloc): Create a struct rtable (IPv4’s dst_entry) based on the fib_result. Set key fields:
Associate Neighbour: Implicitly initializes the neighbour association for this rtable (specific resolution will occur during subsequent output).

rtable->dst.input： Set to ip_forward (for forwarding) or ip_local_deliver (for local delivery, but this is usually determined when checking the local table).
rtable->dst.output： Initially usually set to ip_output (for locally generated or forwarded packets, the neighbour subsystem will replace it later).
rtable->rt_gateway： Next hop IP (gateway address or destination address).
rtable->rt_dev： Output device (from fib_nh).
rtable->rt_route_iif： Input device.

This is the entry function for input path routing lookups. The main task is to determine whether the packet is destined for the local machine (INPUT), needs to be forwarded (FORWARD), or is a broadcast/multicast.
Key Steps:

Set skb Destination (skb_dst_set): Associate the created rtable (as a dst_entry) with the sk_buff (skb->dst<code>).

Subsequent Processing: Call the corresponding processing function based on the dst->input<code> function pointer:

If it is ip_local_deliver: The packet enters the upper protocol stack on the local machine (TCP/UDP/ICMP, etc.).
If it is ip_forward: Execute forwarding logic (decrement TTL, handle options, fragmentation, etc.), then call dst_output(skb).

Output Path (dst_output -> skb_dst(skb)->output(skb)):

NUD_CONNECTED/NUD_REACHABLE： Directly call neigh->ops->queue_xmit (which ultimately calls dev_queue_xmit to place the packet in the network card’s send queue).
Other states (NUD_INCOMPLETE, NUD_STALE, NUD_DELAY, NUD_PROBE): Call neigh_resolve_output, which is responsible for handling ARP/ND resolution (possibly sending requests and caching packets), and sends the packet after successful resolution.

This will call rtable->dst.output, which is usually ip_output.
ip_output processes possible IP options, then calls ip_finish_output.
ip_finish_output handles possible fragmentation, then calls ip_finish_output2.
ip_finish_output2 calls dst_neigh_output.
dst_neigh_output gets or creates the neighbour entry corresponding to rtable->rt_gateway (struct neighbour) and calls neigh_output.
neigh_output calls its output method based on the neighbour entry’s state (neigh->nud_state):

4. Implementation Mechanisms of Core Components

1. Routing Policy Database (RPDB)

Data Structure:

// Policy rule definition
struct fib_rule {
    u32             priority; // Priority (the smaller the value, the higher the priority)
    u32             table; // Target routing table ID
    u8              action; // Action type
    u8              l3mdev; // L3 main device flag
    u32             flags; // Rule flags
    u32             fwmark; // Firewall mark
    u32             fwmask; // Firewall mask
    __be32          src; // Source address
    __be32          dst; // Destination address
    u8              src_len; // Source address length
    u8              dst_len; // Destination address length
};

Policy Matching Process:

// net/ipv4/fib_rules.c
int fib_rules_lookup(struct fib_rules_ops *ops, struct flowi *fl, int flags,
                     struct fib_lookup_arg *arg) {
    struct fib_rule *rule;

    list_for_each_entry(rule, &ops->rules_list, list) {
        if (!fib_rule_match(rule, ops, fl, flags))
            continue;

        if (rule->action == FR_ACT_GOTO) {
            // Jump to other rule chains
        } else if (rule->action == FR_ACT_TO_TBL) {
            // Use specified routing table
            err = ops->action(rule, fl, flags, arg);
            if (err != -EAGAIN)
                return err;
        }
    }
    return -ESRCH; // No match
}

2. Forwarding Information Base (FIB)

Data Structure:

// Routing table structure
struct fib_table {
    struct hlist_node   tb_hlist; // Hash linked list
    u32                 tb_id; // Table ID
    unsigned            tb_num_default; // Number of default routes
    struct rcu_head     rcu; // RCU protection
    struct trie __rcu *tb_trie; // LC-trie tree root
};

// LC-trie node structure
struct tnode {
    t_key key; // Key value
    unsigned long pos; // Bit position
    struct tnode __rcu *parent; // Parent node
    struct tnode __rcu *child[0]; // Child nodes
};

LPM Lookup Algorithm:

// net/ipv4/fib_trie.c
static struct key_vector *fib_find_node(struct trie *t, struct key_vector **tp,
                                        u32 key) {
    struct key_vector *n, *pn;
    unsigned long index;

    pn = t->kv;
    n = get_child(pn, 1);

    while (n) {
        if (index >= n->key && index <= n->key + n->pos) {
            *tp = pn;
            return n;
        }
        pn = n;
        n = get_child_rcu(n, get_index(key, n));
    }
    return NULL;
}

3. Destination Cache (dst_entry)

Core Structure:

struct dst_entry {
    struct net_device *dev; // Output device
    unsigned long           _metrics; // Routing metrics
    unsigned long           expires; // Expiration time
    struct neighbour __rcu  *neighbour; // Neighbour entry
    int (*input)(struct sk_buff *); // Input processing function
    int (*output)(struct net *, struct sock *, struct sk_buff *); // Output processing function
};

// IPv4 specific routing cache
struct rtable {
    struct dst_entry    dst;
    __be32              rt_key_dst; // Destination address
    __be32              rt_key_src; // Source address
    __be32              rt_gateway; // Gateway address
    u8                  rt_type; // Route type
};

4. Integration with the Neighbour Subsystem

Routing to Neighbour Conversion:

// net/ipv4/ip_output.c
static int ip_finish_output2(struct net *net, struct sock *sk, struct sk_buff *skb) {
    struct dst_entry *dst = skb_dst(skb);
    struct rtable *rt = (struct rtable *)dst;
    struct neighbour *neigh;

    // Get neighbour entry
    neigh = __ipv4_neigh_lookup_noref(dst->dev, rt->rt_gateway);
    if (unlikely(!neigh))
        neigh = __neigh_create(&arp_tbl, &rt->rt_gateway, dst->dev, false);

    // Send via neighbour subsystem
    return neigh_output(neigh, skb);
}

5. Analysis of Core Path Code

1. Input Path Routing (ip_route_input)

// net/ipv4/route.c
int ip_route_input_noref(struct sk_buff *skb, __be32 daddr, __be32 saddr,
                         u8 tos, struct net_device *dev) {
    struct fib_result res;
    struct flowi4 fl4;

    // Initialize flow information
    memset(&fl4, 0, sizeof(fl4));
    fl4.flowi4_iif = dev->ifindex;
    fl4.daddr = daddr;
    fl4.saddr = saddr;
    fl4.flowi4_tos = tos;

    // Policy routing lookup
    if (fib_rules_lookup(net->ipv4.rules_ops, flowi4_to_flowi(&fl4), 0, &res))
        goto no_route;

    // Create routing cache
    rth = rt_dst_alloc(dev_net(dev), flags);
    if (!rth)
        goto e_nobufs;

    // Set routing attributes
    rth->dst.input = ip_forward;
    rth->dst.output = ip_output;
    rth->rt_key_dst = daddr;
    rth->rt_gateway = res.fi->fib_nh[0].nh_gw;

    // Associate with skb
    skb_dst_set(skb, &rth->dst);
    return 0;
}

2. Output Path Routing (__ip_route_output_key)

// net/ipv4/route.c
struct rtable *__ip_route_output_key(struct net *net, struct flowi4 *fl4) {
    struct fib_result res;

    // Policy routing lookup
    if (fib_rules_lookup(net->ipv4.rules_ops, flowi4_to_flowi(fl4), 0, &res))
        return ERR_PTR(-ENETUNREACH);

    // Create routing cache
    rth = rt_dst_alloc(out_dev, flags);
    rth->rt_key_dst = fl4->daddr;
    rth->rt_key_src = fl4->saddr;

    // Set output function
    rth->dst.output = ip_output;

    // Multipath routing handling
    if (res.fi->fib_nhs > 1 && fl4->flowi4_oif == 0)
        fib_select_multipath(&res, hash);

    return rth;
}

3. FIB Update Operation (fib_table_insert)

// net/ipv4/fib_trie.c
int fib_table_insert(struct net *net, struct fib_table *tb,
                     struct fib_config *cfg, struct netlink_ext_ack *extack) {
    struct trie *t = (struct trie *)tb->tb_data;
    struct fib_alias *fa, *new_fa;

    // Find insertion position
    l = fib_find_node(t, &tp, key);

    // Create new entry
    new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
    new_fa->fa_info = fi;
    new_fa->fa_tos = cfg->fc_tos;
    new_fa->fa_type = cfg->fc_type;

    // Insert into trie tree
    if (!l) {
        // Create new leaf node
        l = leaf_new(key);
        insert_leaf(t, tp, l);
    }

    // Add to alias list
    hlist_add_head_rcu(&new_fa->fa_list, &l->leaf);

    // Notify routing change
    rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len, tb->tb_id, cfg, NLM_F_CREATE);
}

6. Key Mechanism Implementation Details

1. Multipath Routing (ECMP)

// net/ipv4/fib_semantics.c
void fib_select_multipath(struct fib_result *res, int hash) {
    struct fib_info *fi = res->fi;
    u32 w;

    for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
        struct fib_nh *nh = &fi->fib_nh[nhsel];

        // Calculate weight
        w = nh->nh_weight;
        if (w == 0)
            continue;

        // Hash select path
        if (hash <= atomic_read(&nh->nh_upper_bound)) {
            res->nh_sel = nhsel;
            return;
        }
        hash -= atomic_read(&nh->nh_upper_bound);
    }
}

2. Integration with the Neighbour Subsystem

// net/core/neighbour.c
int neigh_output(struct neighbour *n, struct sk_buff *skb) {
    // Choose output function based on neighbour state
    if (n->nud_state && NUD_CONNECTED)
        return n->output(n, skb); // Directly send
    else
        return neigh_resolve_output(n, skb); // Needs resolution
}

int neigh_resolve_output(struct neighbour *neigh, struct sk_buff *skb) {
    // Send ARP request
    if (!(neigh->nud_state && (NUD_STALE | NUD_INCOMPLETE))) {
        neigh->ops->solicit(neigh, skb);
        __skb_queue_tail(&neigh->arp_queue, skb);
        return 0;
    }

    // Already resolved, send directly
    return neigh->ops->output(neigh, skb);
}

7. Performance Optimization Mechanisms

1. RCU Lock Optimization

// FIB lookup uses RCU protection
static struct key_vector *fib_find_node(struct trie *t, struct key_vector **tp, u32 key) {
    struct key_vector *pn, *n;

    rcu_read_lock();
    pn = t->kv;
    n = rcu_dereference(pn->tnode[0]);
    ...
    rcu_read_unlock();
}

2. Routing Cache Optimization (Historical)

// Old routing cache (before 3.6)
struct rt_hash_bucket {
    struct rtable *chain;
};

// Cache lookup (removed)
static inline struct rtable *rt_hash_result(u32 saddr, u32 daddr, int iif) {
    unsigned int hash = rt_hash_code(saddr, daddr, iif);
    struct rtable *rth = rt_hash_table[hash].chain;

    while (rth) {
        if (rth->fl.fl4_src == saddr &&
            rth->fl.fl4_dst == daddr &&
            rth->fl.iif == iif)
            return rth;
        rth = rth->u.dst.rt_next;
    }
    return NULL;
}

8. Diagnostic Tools and Debugging Interfaces

1. /proc Filesystem Interface

# View routing table
cat /proc/net/route

# View FIB statistics
cat /proc/net/stat/rt_cache

# View routing policies
cat /proc/net/rt_acct

2. ftrace Trace Points

# Enable routing trace points
echo 1 > /sys/kernel/debug/tracing/events/fib/enable
echo 1 > /sys/kernel/debug/tracing/events/neigh/enable

# View trace results
cat /sys/kernel/debug/tracing/trace_pipe

9. Summary Architecture Diagram

+-------------------+     +-------------------+     +-------------------+
|  User Space Configuration Tools   |     |   Network Protocol Stack        |     |    Network Device Driver     |
| (ip route add/del) |     | (TCP/UDP/ICMP)    |     | (Driver for sending/receiving packets)     |
+---------+---------+     +---------+---------+     +---------+---------+
          | Netlink                 |                        |
          v                         v                        v
+-------------------+     +-------------------+     +-------------------+
|  Netlink Subsystem    |     |   IP Routing Entry      |     |  Neighbour Subsystem ARP/ND   |
| (Handles RTM_NEWROUTE) |     | (ip_route_input)  |     | (MAC Address Resolution)       |
+---------+---------+     +---------+---------+     +---------+---------+
          |                         |                        |
          v                         v                        |
+-------------------+     +-------------------+              |
|  Routing Policy Database RPDB |     |  Destination Cache dst_entry |<----------+
| (Policy-based Routing Selection)       |     | (Input/Output Function Pointers)  |
+---------+---------+     +---------+---------+
          |                         |
          v                         v
+-------------------+     +-------------------+
|  Forwarding Information Base FIB     |     |  Multipath Routing ECMP    |
| (LC-trie Implementing LPM)    |     | (Traffic Load Balancing)      |
+-------------------+     +-------------------+

Key Implementation Points:

Layered Architecture: User Space → Netlink → RPDB → FIB → dst_entry → Neighbour Subsystem
High-Performance Lookup: LC-trie implements O(log n) complexity LPM lookup
Policy Routing: RPDB supports multidimensional routing based on source/destination addresses, firewall marks, etc.
Seamless Integration: dst_entry connects various layers of the network stack through input/output function pointers
Dynamic Updates: RCU protection enables lock-free updates to the routing table
Multipath Support: ECMP implements traffic load balancing and high availability

The routing subsystem achieves a highly modular design and sophisticated algorithms, providing near line-speed forwarding performance while ensuring functional flexibility, making it a core infrastructure of the modern Linux networking stack.

In-Depth Analysis of the Linux Routing Subsystem: Framework, Implementation, and Code Paths

Table of Contents

In-Depth Analysis of the Linux Routing Subsystem: Framework, Implementation, and Code Paths

1. Core Framework of the Routing Subsystem

2. Core Framework and Components of the Routing Subsystem

3. Detailed Explanation of the Routing Lookup Process (Taking IPv4 Forwarding as an Example)

4. Implementation Mechanisms of Core Components

1. Routing Policy Database (RPDB)

2. Forwarding Information Base (FIB)

3. Destination Cache (dst_entry)

4. Integration with the Neighbour Subsystem

5. Analysis of Core Path Code

1. Input Path Routing (ip_route_input)

2. Output Path Routing (__ip_route_output_key)

3. FIB Update Operation (fib_table_insert)

6. Key Mechanism Implementation Details

1. Multipath Routing (ECMP)

2. Integration with the Neighbour Subsystem

7. Performance Optimization Mechanisms

1. RCU Lock Optimization

2. Routing Cache Optimization (Historical)

8. Diagnostic Tools and Debugging Interfaces

1. /proc Filesystem Interface

2. ftrace Trace Points

9. Summary Architecture Diagram

Key Implementation Points:

Leave a Comment Cancel reply