Mastering Dynamic Routing: BGP, IGPs, and Protocol Mechanics Explained

Previous List

《Future Internet Technology Development Chronicle, from ARPANET to Fully Programmable Networks》

《Ethernet Technology Development Chronicle》

《Network Protocol — ARP Address Resolution Protocol》

Table of Contents

Dynamic Routing Protocols

Basic Working Principle

Types

Common Protocols

Performance Metrics

BGP and Internet

BGP Router and Routes

BGP Message Types and Formats

BGP Message State Machine

BGP Path Attributes and Route Selection

BGP RR (Route‑Reflectors)

BGP MP (Multi‑protocol Extensions)

BGP Link‑state

Dynamic Routing Protocols

Dynamic routing protocols enable routers to periodically and automatically exchange route information, generate routing table entries, and achieve network convergence so that each router knows the next hop for any destination even when failures occur.

Basic Working Principle

Dynamic routing protocols operate in four stages:

Neighbor Discovery : Routers running the same protocol establish peer relationships.

Route Exchange : Each router advertises its routes to neighbors.

Route Computation : Routers apply their routing algorithms to compute the final routing table.

Route Maintenance : Periodic keep‑alive messages detect failures and trigger updates.

Types of Dynamic Routing Protocols

From an application perspective :

IGP (Interior Gateway Protocol) : Operates within a single Autonomous System (AS) – e.g., RIP, OSPF, I‑BGP.

EGP (Exterior Gateway Protocol) : Operates between different ASes – e.g., E‑BGP.

From a technical implementation perspective :

Distance Vector : Uses distance and direction metrics – examples: RIP, BGP.

Link State : Maintains a link‑state database (LSDB) representing the full network topology – examples: OSPF, IS‑IS.

Common Dynamic Routing Protocols

1. RIP (IGP, Distance Vector) : Simple configuration, slow convergence, mainly used in labs.

Simple to configure.

Slow convergence.

Typically for small networks.

2. OSPFv3 and IS‑IS (IGP, Link State) : Suitable for medium to large networks, provides a complete topology map and uses Dijkstra’s algorithm.

Full network map with link status.

Shortest‑path‑first calculation.

High CPU/memory usage.

3. BGPv4 (IGP/EGP, Distance Vector) : Initially designed for inter‑AS routing, now also used inside large ASes.

AS‑path used as distance metric.

Powerful policy control.

Handles massive routing tables.

Performance Metrics

Routing correctness : Avoid routing loops; link‑state protocols are generally superior.

Convergence speed : Faster convergence means quicker reaction to topology changes.

System overhead : CPU and memory consumption; link‑state protocols consume more resources.

Scalability : OSPF fits a few hundred routers; BGP can scale to the entire Internet.

BGP and Internet

BGP (Border Gateway Protocol) is a distance‑vector protocol designed for the Internet, enabling route exchange between Autonomous Systems (ASes).

Originating in the 12th IETF meeting in January 1989, BGP addressed the need for a scalable inter‑AS routing solution as the number of ASes grew rapidly.

An AS is a logically cohesive IP network; each AS is assigned a unique 16‑bit ASN by IANA. Ranges 1‑64511 are globally unique, while 64512‑65535 are private.

The original design ideas included deploying border routers in each AS, using AS‑path attributes to prevent loops, employing TCP for reliable transport, incremental synchronization, and TLV encoding for extensibility.

Modern BGPv4 supports IPv4/IPv6, CIDR, multipath, route reflectors, communities, route dampening, MP extensions, capability advertisement, BGPSEC, and many other features.

BGP Router and Routes

A BGP router (speaker) advertises routes via BGP messages. Peers establish sessions (I‑BGP or E‑BGP) and exchange Update, Keepalive, Notification, and Route‑Refresh messages.

Key components of a BGP router’s RIB:

Adj‑RIBs‑In : Stores routes received from peers.

Input Policy : Filters received routes before they enter the local RIB.

BGP Selection Process : Adds local AS, next‑hop, and other attributes.

Local RIB : Holds selected routes for the routing table.

Output Policy : Determines which routes may be advertised.

Adj‑RIB‑Out : Stores routes ready for transmission.

BGP Message Types and Formats

BGP messages consist of a 19‑byte header and a variable‑length payload (max 4096 bytes). Types:

Open – session negotiation.

Keepalive – session maintenance.

Update – route advertisement/withdrawal.

Notification – error reporting.

Route‑Refresh – request re‑advertisement.

Open Message

Sent after TCP connection establishment to negotiate version, AS number, hold time, and BGP identifier.

Version : Usually 4.

My AS : Local ASN.

Hold Time : Maximum interval without receiving Keepalive or Update.

BGP Identifier : Router’s IP identifier.

Keepalive Message

Periodically exchanged to confirm session liveliness.

Update Message

Contains withdrawn routes, path attributes, and NLRI (network layer reachability information).

Withdrawn Routes Length and Withdrawn Routes .

Total Path Attribute Length and Path Attributes .

NLRI – IP prefixes.

Notification Message

Used to report errors and terminate the session.

Error Code / Subcode .

Data – error details.

Route‑Refresh Message

Requests a peer to resend routes for a specific address family.

BGP State Machine

The protocol progresses through Idle, Connect, Active, OpenSent, OpenConfirm, and Established states, handling events such as Start, TCP connection success/failure, receipt of Open, Keepalive, Notification, and errors.

BGP Path Attributes and Route Selection

Attributes are divided into four categories:

Well‑known Mandatory

ORIGIN : IGP, EGP, or INCOMPLETE.

AS_PATH : Ordered list of ASes traversed.

NEXT_HOP : IP address of the next hop.

Well‑known Discretionary

LOCAL_PREF : Preference within an AS (shared only among I‑BGP peers).

ATOMIC_AGGREGATE : Indicates route aggregation.

Optional Transitive

AGGREGATOR : Identifies the router that performed aggregation.

Community : Groups routes for policy control (e.g., INTERNET, NO_EXPORT).

Optional Non‑transitive

MED : Multi‑exit discriminator; lower value is preferred.

ORIGINATOR_ID : Used by route reflectors to avoid loops.

CLUSTER_ID : Identifies route‑reflector clusters.

Route Selection Principles

Typical decision order (simplified): Weight → Local‑Preference → Locally originated → Shortest AS‑path → Best ORIGIN → Lowest MED → E‑BGP over I‑BGP → Earliest arrival → Lowest I‑BGP next‑hop cost → Shortest cluster list → Smallest Router‑ID → Smallest peer IP.

BGP RR (Route‑Reflectors)

Route‑reflectors reduce the number of required BGP sessions in large clusters by reflecting routes from non‑client peers to client peers and vice‑versa.

BGP MP (Multi‑protocol Extensions)

MP‑BGP adds AFI/SAFI fields to support multiple address families (IPv4, IPv6, VPNv4, VPNv6, L2VPN EVPN, etc.) and route types (unicast, multicast, flow).

BGP Link‑state (BGP‑LS)

BGP‑LS transports IGP topology information (nodes, links, prefixes) over BGP, enabling controllers to obtain a complete network view without implementing IGP protocols.

BGP‑LS Route Types

Node Route

[NODE][ISIS-LEVEL-1][IDENTIFIER0][LOCAL[as100][bgp-ls-identifier11.1.1.2][ospf-area-id0.0.0.0][igp-router-id0000.0000.0001.00]]

Link Route

[LINK][ISIS-LEVEL-1][IDENTIFIER0][LOCAL[as255.255][bgp-ls-identifier192.168.102.4][ospf-area-id0.0.0.0][igp-router-id0000.0000.0002.01]][REMOTE[as255.255][bgp-ls-identifier192.168.102.4][ospf-area-id0.0.0.0][igp-router-id0000.0000.0002.00]][LINK[if-address0.0.0.0][peer-address0.0.0.0][if-address::][peer-address::][mt-id0]]

Prefix Route

[IPV4-PREFIX][ISIS-LEVEL-1][IDENTIFIER0][LOCAL[as100][bgp-ls-identifier192.168.102.3][ospf-area-id0.0.0.0][igp-router-id0000.0000.0001.00]][PREFIX[mt-id0][ospf-route-type0][prefix192.168.102.0/24]]

Application Examples

Within a single IGP area, deploying BGP‑LS on any router provides the full topology to a controller. For multi‑area or multi‑AS scenarios, a single BGP‑LS speaker can still supply the complete view, and redundancy can be achieved with multiple speakers or a BGP‑LS reflector.

In SR‑TE deployments, BGP‑LS feeds the controller with node, link, prefix, and SR‑policy data, enabling path computation across domains.