Routing and BGP

When a router receives two paths to the same prefix—one with a shorter AS_PATH and the other with a higher local preference—the latter may be selected. However, if the destination address also matches a more specific prefix, the actual forwarding will use that more specific route. To understand routing, one must first distinguish between "selecting a candidate path for the same prefix" and "performing a longest prefix match for a destination address."

RIB and FIB: Candidate Information and Forwarding Results

The RIB (Routing Information Base) is the logical organization of routing information, while the FIB (Forwarding Information Base) is oriented towards actual forwarding. BGP further distinguishes between Adj-RIB-In (received from neighbors), Loc-RIB (locally selected), and Adj-RIB-Out (advertised to neighbors). These are protocol models and do not require every implementation to maintain three completely independent data structures exactly as described. RFC 4271: Routing Information Model

In Linux software routing scenarios, daemons like FRR can install routes via the kernel interface; hardware devices may also need to further push configurations to the ASIC. Having a route in the RIB does not guarantee that the next-hop is resolvable or that installation will succeed; having a route in the FIB does not guarantee that the egress neighbor and return path are normal.

Longest prefix match is the semantics; trie, compressed levels, and hardware tables are the implementations. You cannot abbreviate Linux LC-trie as a constant O(1) under all scales and access conditions, nor can you describe the memory requirements of all routers using a constantly changing global prefix count: neighbor count, address families, candidate paths, and policies are equally important.

Calculating Longest Prefix Correctly

Assume a table contains a default route, 203.0.113.0/24 via A, and 203.0.113.128/25 via B. Destination .140 matches all three, so /25 via B is selected; destination .20 selects /24 via A. Even if the BGP LOCAL_PREF for /24 is high, it will not override the longest prefix advantage of the installed /25.

Cross-protocol priority usually resolves candidate competition for the same prefix and should not mix the administrative distance of a static route on one device with a prefix of a different length. Route aggregation reduces entries but also expands the covered range, so you need to consider whether traffic will be sent into a black hole when more specific routes are missing.

Linux Policy Routing: Deciding Which Table to Query First

RPDB (Routing Policy Database) processes rules in ascending order of priority. It can select actions based on source address, fwmark, input interface, etc. After a rule matches, a table lookup is performed. If no terminating result is obtained, subsequent rules may continue; therefore, "the first matching rule always ends the process" is inaccurate. A throw route can end the lookup in the current table and continue the rule chain, while blackhole, unreachable, etc., have different termination semantics. ip-rule man page, ip-route man page

Common pre-configured rules query the local (255), main (254), and default (253) tables in sequence. A table named default does not equal a default route: 0.0.0.0/0 or ::/0 can reside in the main or other tables. Custom table numbers are not limited to 1–252.

For example, if a source prefix first queries table 100, and table 100 has no matching route, it can continue to query main; if table 100 has a default route, it usually provides a result and will not continue to search for a more specific route in main. Longest prefix comparison occurs within the context of the current table lookup, not by merging and sorting all tables.

# Read-only observation commands; replace actual interfaces, destinations, and source addresses according to the environment.
ip rule show
ip route show table all
ip route get <destination IPv4> from <source IPv4>
ip -6 route get <destination IPv6> from <source IPv6>

Why might a more-specific route never be consulted?

Keep main’s match ranges visible and check whether the lookup actually reaches main. A destination inside/25 can still use C because an earlier rule terminates, without changing longest-prefix semantics.

IGP: Accumulating Link Costs onto Paths

OSPF and IS-IS propagate link states within their respective areas and calculate paths; the cost expresses the configured metric and does not necessarily equal the measured latency. Using a simplified single-area topology as an example, A→B cost is 10, B→D is 10, A→C is 5, and C→D is 30. Thus, via B totals 20, which is better than via C's 35. After A→B fails, the path via C may become the new available shortest path. RFC 2328: OSPFv2

Actual convergence also involves failure detection, state propagation, SPF scheduling, and forwarding table updates; area structure, route types, and policies add more rules. You cannot derive a fixed network-wide switchover time in milliseconds solely from the Dijkstra algorithm. IGP is also commonly used to provide intra-domain reachability for BGP NEXT_HOP, and they work together.

BGP Sessions: TCP Connectivity is Just the Start

BGP uses TCP port 179, then exchanges OPEN, KEEPALIVE, UPDATE, and other messages to establish protocol state. The version in OPEN is 4, and the BGP Identifier is a 32-bit identifier, which does not have to be the session endpoint address. Hold Time is negotiated between the two parties; a non-zero value must be at least three seconds. If negotiated to zero, the corresponding Hold/Keepalive timers do not run, so it is incorrect to universally write 90/30 seconds.

The My Autonomous System field in the basic OPEN is still two bytes; four-byte ASNs are supported through capability negotiation and compatibility mechanisms, not by simply extending the field length. RFC 6793: Four-octet ASN UPDATEs announce or withdraw prefixes and carry attributes; multi-protocol extensions use corresponding attributes to carry different address families, so you cannot force the IPv4 unicast basic layout onto all MP-BGP packets.

A session is Established but has no routes; this could be due to the address family not being enabled, import policies rejecting them, or the peer not exporting them, rather than a TCP failure. RFC 8212 provides restrictions on default eBGP import/export policies; actual products should also check version and configuration modes. RFC 4271, RFC 8212: Explicit eBGP Policies

Path Selection: Explaining Priority via Candidate Tables

In this example, both paths are valid, NEXT_HOP is resolvable, and no earlier local attribute differences exist. A's LOCAL_PREF=200 is higher than B's 100, so A is selected even though A's AS sequence is longer. After changing A to 100, B is selected when comparing path lengths under otherwise identical preceding conditions.

You should verify the complete order and switches against the documentation of the implementation in use; for example, FRR's MED comparison, multipath relaxation, and router-ID related options affect results. In teaching, deduce candidates only under explicit assumptions to avoid mixing Cisco, Huawei, and FRR rules into a so-called standard algorithm. FRR BGP Selection Documentation

Why can a shorter AS path lose?

First let higher LOCAL_PREF outweigh A’s longer path, then equalize preference to expose the next criterion. Disabling next-hop reachability excludes A before either numeric comparison. The order applies to this explicitly limited candidate set.

Loop Prevention, iBGP, and Route Reflection

Standard eBGP advertisements add the local AS to the path; paths received containing the local AS are usually excluded. iBGP does not repeatedly add the local AS when propagating within the same AS. This mechanism suppresses AS-level routing loops but cannot replace all data plane loop and misconfiguration checks.

Traditional iBGP does not directly advertise routes learned from one iBGP neighbor to another iBGP neighbor, so simple interconnection does not automatically form complete propagation. Full mesh, route reflection, and confederations solve scale or organizational issues respectively; reflectors rely on additional mechanisms like ORIGINATOR_ID and CLUSTER_LIST to prevent corresponding reflection loops. RFC 4456: Route Reflection

iBGP sessions can be established across multiple hops, and the NEXT_HOP in the route must still be recursively resolvable. next-hop-self is a policy choice to change the next-hop advertisement, not a mandatory setting for all deployments.

Communities and Traffic Engineering: Labels Require Policy Interpretation

Standard Community is 32 bits, often written as two 16-bit decimal values; Extended is 8 bytes, Large is 12 bytes. You cannot assume the three differ only in display format. RFC 8092: Large Communities Standard labels have no automatic actions; both parties must agree on how to match and implement policies.

NO_ADVERTISE restricts advertisement to any BGP neighbor; the boundary for NO_EXPORT is the confederation boundary, so it cannot be roughly equated to prohibiting propagation in any form of eBGP session. Inside confederations, semantics like NO_EXPORT_SUBCONFED must also be distinguished. RFC 1997: Standard Communities

AS_PATH prepend can increase the apparent length of a path, influencing inbound selection at the remote end, but the remote LOCAL_PREF may decide the result first. Therefore, "prepending twice will definitely change the path to another exit" is incorrect. Outbound preference is mostly controlled directly by your own policies; inbound influence is usually limited to advertisements and agreements with the other party.

ECMP: Sharing Hash Results, Not Exact Byte Quotas

Multiple qualifying next-hops can be installed in the FIB, hashed based on address, port, Flow Label, or other selected fields. The specific fields depend on the protocol family, kernel, and configuration; Linux documentation provides fib_multipath_hash_policy, and it does not always use only source/destination IP.

Under a stable member set and hash policy, the same flow usually maintains path consistency to reduce out-of-order packets. Member addition/removal or route changes may remap flows; even with weights of 2:1, uneven large flow sizes can cause actual byte volumes to deviate significantly from 2:1, and it certainly does not guarantee that a single connection gets throughput equal to the sum of two links. Linux Multipath Hash Configuration

Convergence and Origin Validation: Don't Just Look at Green Session Status

After a path fails, the device needs to detect, withdraw or exclude candidates, re-select the best path, install the FIB, and propagate the change to other nodes. BFD and others can change the detection phase but do not eliminate the overhead of the entire chain. The assumption behind Graceful Restart preserving the old forwarding table must also hold; otherwise, preserving state may prolong black holes.

RPKI origin validation compares the route prefix, origin AS, and authorization information, resulting in Valid, Invalid, or NotFound. Valid does not authenticate the entire AS_PATH, nor does it guarantee the absence of route leaks; NotFound does not equal a definitive error. Whether to drop or adjust priority requires policy enforcement. RFC 6811: Origin Validation

When checking, answer sequentially: what was received, which policy processed it, why it was selected or rejected, how the NEXT_HOP is resolved, whether it is installed, and whether real packets and return paths pass through. This breaks down "BGP has a route but it doesn't work" into specific, verifiable issues.

Local Deduction: Prefixes and Policy Order

from ipaddress import ip_network, ip_address

def lookup(address, entries):
    matches = [(ip_network(prefix), hop) for prefix, hop in entries
               if ip_address(address) in ip_network(prefix)]
    return max(matches,key=lambda item:item[0].prefixlen)[1] if matches else None

main = [('0.0.0.0/0','default'),('203.0.113.0/24','A'),('203.0.113.128/25','B')]
assert lookup('203.0.113.140',main) == 'B'
assert lookup('203.0.113.20',main) == 'A'
policy_table = [('0.0.0.0/0','C')]
assert (lookup('203.0.113.140',policy_table) or lookup('203.0.113.140',main)) == 'C'

# Simulates only LOCAL_PREF and AS sequence length when preceding conditions are consistent.
paths = [('A',200,[64501,64502,64503]),('B',100,[64504,64503])]
def best(candidates):
    return min(candidates,key=lambda x:(-x[1],len(x[2])))[0]
assert best(paths) == 'A'
paths[0] = ('A',100,[64501,64502,64503])
assert best(paths) == 'B'
assert min(10+10,5+30) == 20
print('Longest prefix, policy table priority, two BGP candidates, and path cost checks passed')

This is not a complete BGP implementation, nor does it simulate MED, route reflection, or convergence timers.

Continue Reading

• IPv4 Protocol: Addresses, next-hops, and forwarding fields.
• ICMP and PMTUD: Path observation and error feedback.
• TCP: Reliable transport over the network path.