Dynamic Routing (OSPF & BGP)

1. Discover neighbors: Routers send Hello packets on each OSPF-enabled interface (multicast 224.0.0.5). Routers that share a link and agree on parameters (area ID, hello/dead timers, authentication) become neighbors.
2. Form adjacencies: Neighbors exchange their complete Link-State Databases (LSDBs) using Database Description (DBD) packets, then fetch missing/newer LSAs with Link-State Request/Update.
3. Flood LSAs: Each router generates LSAs describing its own links and floods them to all routers in the area. Every router ends up with an identical LSDB.
4. Run SPF: Each router independently runs Dijkstra's Shortest Path First algorithm on the LSDB to build a shortest-path tree rooted at itself.
5. Install routes: The SPF tree determines the best next-hop for each destination. These are installed in the routing table (FIB).

Given the complete LSDB, each router runs SPF independently:

1. Start with the root node (self). Set cost to self = 0, cost to all others = infinity.
2. Examine all links from the current node. For each neighbor, calculate total cost (current cost + link cost). If this is less than the neighbor's current known cost, update it.
3. Mark current node as "visited." Move to the unvisited node with the lowest cost.
4. Repeat steps 2-3 until all reachable nodes are visited.
5. The resulting tree gives the shortest path (lowest total cost) from this router to every other router in the area.

On broadcast/multi-access segments (Ethernet), full-mesh adjacencies between N routers would create N*(N-1)/2 adjacencies. Instead, OSPF elects:

• DR (Designated Router): All routers form adjacencies with the DR (not with each other). The DR represents the segment with a Network LSA (Type 2). Elected by highest OSPF priority (default 1), then highest Router ID.
• BDR (Backup Designated Router): Takes over if the DR fails. Second-highest priority.
• DROther: All other routers. They only form full adjacencies with DR and BDR, not with each other.

Updates are sent to 224.0.0.6 (DR/BDR listen) and the DR floods to 224.0.0.5 (all OSPF routers).

BGP uses TCP port 179 for reliable transport. Peers are explicitly configured (no autodiscovery like OSPF Hello).

# FRRouting (common on Linux) BGP config example
router bgp 64512
  bgp router-id 10.0.0.1
  neighbor 10.0.0.2 remote-as 64513     # eBGP peer (different AS)
  neighbor 10.0.0.3 remote-as 64512     # iBGP peer (same AS)
  !
  address-family ipv4 unicast
    network 192.168.1.0/24              # Originate this prefix
    neighbor 10.0.0.2 route-map IMPORT-POLICY in
    neighbor 10.0.0.2 route-map EXPORT-POLICY out
  exit-address-family

Most common tiebreakers in practice: Local Preference (step 2) for outbound traffic engineering, AS_PATH length (step 4) as the natural metric, and MED (step 6) for inbound traffic engineering. Most other steps rarely matter.

• The full BGP table contains approximately 1,000,000+ IPv4 prefixes and 200,000+ IPv6 prefixes (as of 2026)
• A "full table" router (transit provider, IXP participant) must store all of these
• Edge routers often only take a default route from their upstream provider (no need for full table if you only have one exit)
• Route reflectors and confederations solve the iBGP full-mesh scaling problem (N routers would need N*(N-1)/2 iBGP sessions)

• RPKI (Resource Public Key Infrastructure): Cryptographically binds IP prefixes to authorized ASNs using ROAs (Route Origin Authorizations). Prefix owners create ROAs signed by RIR certificates.
• ROV (Route Origin Validation): Routers validate received BGP announcements against RPKI data. Routes that fail validation (the announcing AS doesn't match the ROA) are marked as "Invalid" and can be rejected.
• BGPsec: Extends RPKI to validate the entire AS_PATH (not just origin). Cryptographic signatures at each hop. Not widely deployed due to performance and incremental deployment challenges.
• IRR (Internet Routing Registry): Older, non-cryptographic approach. Operators register their prefixes and routing policies. Used for generating prefix filters. Less secure than RPKI (no crypto verification).