Routing and BGP

Internet routing is divided into two parts: IGP (OSPF/IS-IS) manages intra-domain routing, while BGP manages inter-domain routing. BGP does not select the "fastest" path, but rather the "policy-optimal" path based on a priority chain of AS_PATH, local pref, and MED—it is a reflection of the internet's political landscape.

Overview

Routing is the internet's "navigation system"—determining which path an IP packet takes to reach its destination. A single host only needs a default gateway, but Autonomous Systems (AS) exchange reachability information via BGP: currently, the global internet BGP table contains approximately 950,000 prefixes. BGP does not "select the fastest path"—it is policy-based (business relationships, traffic engineering), and the shortest AS_PATH is just one of many decision factors. Within an autonomous system, OSPF/IS-IS uses link-state algorithms to calculate the shortest path. Linux can function as a host router (ip route) or run a BGP daemon (FRRouting/BIRD) to become a fully functional router.

Routing Table Architecture

RIB vs FIB

RIB (Routing Information Base):
  control plane — all routes learned by routing protocols (BGP/OSPF)
  resides in user-space daemons (FRRouting/BIRD/bgpd)
  can be very large (global internet BGP table: ~950K prefixes)

FIB (Forwarding Information Base):
  data plane — the actual routing table used for forwarding
  best paths are selected from the RIB → installed into the kernel (ip route add)
  must be highly optimized (LC-trie for Linux, O(1) lookup for longest prefix match)

Linux kernel routing table:
  table local (255): local interface addresses, automatic
  table main (254): main routing table (default)
  table default (253): default route
  table N (1-252): user-defined

Policy-Based Routing

# In addition to destination-based routing, Linux supports policy routing:
ip rule add from 192.168.1.0/24 table 100 priority 100
# → Traffic from 192.168.1.0/24 uses table 100

ip rule add fwmark 1 table 200
# → iptables -j MARK --set-mark 1 → uses table 200

ip rule add iif eth0 table 300
# → Packets received on eth0 → uses table 300

# Lookup: ip rule → iterates from priority 0→32766 → first matching rule
# Each table: longest prefix match (trie lookup)

BGP Protocol

BGP Session

BGP establishes sessions using TCP port 179:

  1. TCP 3-way handshake → port 179
  2. BGP OPEN:
       Version: 4
       My AS: <local ASN, 16 or 32 bit>
       Hold Time: <typically 90s>
       BGP Identifier: <router ID, usually loopback IP>
       Optional Parameters: Capabilities (4-byte ASN, MP-BGP, Route Refresh, ...)

  3. BGP KEEPALIVE: heartbeat, interval of Hold Time/3 (default 30s)

  4. BGP UPDATE: route announcement / withdrawal
       Withdrawn Routes: list of prefixes to withdraw
       Path Attributes: attributes of the new prefix
         ORIGIN: IGP (network statement) / EGP / INCOMPLETE (redistribution)
         AS_PATH: sequence of ASes on the path (appends own AS#)
         NEXT_HOP: next-hop IP
         MED (MULTI_EXIT_DISC): Multi-Exit Discriminator (lower = preferred)
         LOCAL_PREF: local preference (higher = preferred, not propagated out of AS)
         COMMUNITIES: 32-bit tags

       NLRI (Network Layer Reachability Information): actual list of prefixes

AS_PATH and Loop Prevention

AS_PATH is BGP's loop prevention mechanism:
  Upon receiving a route → if own AS is in the AS_PATH → reject (loop!)

AS_PATH Operations:
  eBGP: prepend own AS# when sending out
  iBGP: do not prepend (propagated within the same AS)

AS_PATH Prepend (Traffic Engineering):
  AS 100: announces prefix 1.1.1.0/24 to upstream A: AS_PATH = 100 100 100
          announces the same prefix to upstream B: AS_PATH = 100
  → Internet sees: path to 1.1.1.0/24 via B is shorter → selects B
  → However, A still has this prefix (backup)

BGP Communities

32-bit community tag, format: ASN:value

Standard Communities:
  NO_EXPORT (0xFFFFFF01):    do not propagate to eBGP peers
  NO_ADVERTISE (0xFFFFFF02): do not propagate to any BGP peer
  LOCAL_AS (0xFFFFFF03):     do not propagate to external AS (confederation-aware)

Extended Communities (8 bytes):
  Type + Value → SOO (Site of Origin), RT (Route Target for VPN), ...

Large Communities (RFC 8092, 12 bytes):
  Global Admin (4) + Local Data 1 (4) + Local Data 2 (4)
  → More tagging space, no longer limited to 16-bit ASN

Best Path Selection

Cisco/Huawei BGP best path algorithm (simplified):

  1. Highest Weight (Cisco proprietary, local to router)
  2. Highest LOCAL_PREF (default 100)
  3. Prefer locally originated
  4. Shortest AS_PATH length
  5. Lowest ORIGIN type (IGP < EGP < INCOMPLETE)
  6. Lowest MED (compared only when from the same AS)
  7. Prefer eBGP over iBGP
  8. Lowest IGP metric to NEXT_HOP
  9. (if multi-path enabled) — ECMP over equal paths
  10. Oldest eBGP route (stability)
  11. Lowest Router ID (final tie-breaker)

ECMP

# Equal-Cost Multi-Path: multi-path load balancing
ip route add 10.0.0.0/8 nexthop via 192.168.1.1 weight 1 \
                        nexthop via 192.168.1.2 weight 1

# Hash: default src_ip + dst_ip → same flow always takes the same path
# Weight: distributed proportionally (weight 2 = 2× traffic)

References

• RFC: 4271 (BGP-4), 6793 (4-byte ASN), 8092 (Large Communities), 2992 (ECMP)
• Source Code: net/ipv4/fib_trie.c (FIB trie), net/ipv4/fib_rules.c (policy routing)
• Tools: FRRouting (vtysh -c "show ip bgp"), BIRD (birdc show route), ip route

Keywords: BGP, AS, AS_PATH, LOCAL_PREF, MED, community, FIB, RIB, policy routing, ECMP, FRR