BGP Routing Simulator

This project is a C++ simulator that models how BGP (Border Gateway Protocol) routes spread across the Internet. It uses real AS relationship data from CAIDA to build a large network graph and then simulates how routing announcements move between autonomous systems under standard BGP rules, with optional Route Origin Validation (ROV).

The simulator is designed to handle large topologies and produce routing tables similar to what real networks would observe.

What the Simulator Does

At a high level, the program:

-- Builds an Internet-scale AS graph using CAIDA relationship data -- Represents each autonomous system as an independent routing node -- Injects route announcements from CSV input -- Propagates routes according to BGP economic rules -- Optionally drops invalid routes at ROV-enabled ASes -- Writes final routing results to a CSV file

The output shows, for each AS, which prefixes it learned and the AS-path it selected.

Project Structure

src/ main.cpp ASGraph.h / ASGraph.cpp AS.h / AS.cpp Announcement.h / Announcement.cpp Policy.h / Policy.cpp BGPPolicy.h / BGPPolicy.cpp ROVPolicy.h / ROVPolicy.cpp

bench/ many/ prefix/ subprefix/

compare_output.sh CMakeLists.txt README.txt

Core Components

main.cpp

-- This file controls the full simulation flow -- Parses command-line arguments -- Loads AS topology from file or downloads CAIDA data -- Checks for invalid provider-customer cycles -- Builds propagation levels -- Loads ROV configuration -- Seeds initial route announcements -- Runs route propagation -- Writes ribs.csv output

ASGraph

-- This is the central data structure of the simulator -- Stores all autonomous systems -- Creates provider, customer, and peer relationships -- Detects cycles using DFS -- Flattens the graph into propagation levels -- Runs the three BGP propagation phases ---- Upward (customer to provider) ---- Peer (one hop only) ---- Downward (provider to customer) -- Writes final routing tables to CSV -- Most of the routing logic orchestration happens here

AS (Autonomous System)

-- Each AS represents a single network node -- Stores its ASN -- Tracks providers, customers, and peers -- Holds a routing policy (BGP or ROV) -- Receives announcements from neighbors -- Processes announcements using its policy -- Maintains a local routing table (RIB) -- The AS itself does not decide which route is best; that logic lives in the policy

Announcement

-- Represents a single BGP route -- Contains an IP prefix -- Stores an AS-path (vector of ASNs) -- Tracks the next-hop ASN -- Stores the relationship type (origin, customer, peer, provider) -- Includes a flag indicating whether the route is invalid -- Announcements are compared using BGP preference rules

Policy (Base Class)

-- Abstract base class defining routing behavior -- Provides a local routing table (RIB) -- Provides a queue for received announcements -- Includes helper functions for managing routes -- All routing policies inherit from this class

BGPPolicy

-- Implements standard BGP decision logic -- Accepts all incoming announcements -- Selects the best route per prefix based on: ---- Relationship preference ---- AS-path length ---- Next-hop ASN -- Prepends the current ASN to the AS-path when storing routes -- This models basic BGP behavior

ROVPolicy

-- Extends BGP with security checks -- Rejects announcements marked as invalid -- Simulates Route Origin Validation (ROV) -- Uses normal BGP logic after filtering -- Only ASes configured with ROV use this policy

Routing Model

Routes propagate through the network in three controlled stages.

Upward propagation -- Routes from customers move to providers

Peer propagation -- Customer and origin routes move one hop to peers

Downward propagation -- All routes move from providers to customers

This structure enforces valley-free routing and prevents routing loops.

Building the Project

Requirements

-- C++17-compatible compiler -- CMake 3.16 or newer -- libcurl development libraries

Build Steps

mkdir build cd build cmake .. make

This produces the bgp_simulator executable.

Running the Simulator

Basic Usage

./bgp_simulator [options]

Options

--relationships : AS relationship file --announcements : Route announcements CSV --rov-asns : ASNs deploying ROV --output : Output CSV file (default: ribs.csv)

If no topology file is provided, the simulator downloads CAIDA data automatically.

Example Run

./bgp_simulator --relationships ../bench/prefix/CAIDAASGraphCollector.txt --announcements ../bench/prefix/anns.csv --rov-asns ../bench/prefix/rov_asns.csv

Testing and Validation

The provided script compares simulator output against expected results.

../compare_output.sh expected.csv ribs.csv

The comparison ignores ordering and whitespace.

Successful output:

Files match perfectly.

Output Format

The simulator produces a CSV file with columns:

asn,prefix,as_path

Each row shows the final route selected by an AS for a given prefix.

Design Notes

-- Smart pointers are used to manage memory safely -- Routing logic is separated from graph structure -- Policies are modular and easy to extend -- Cycle detection prevents invalid topologies -- The simulator prioritizes correctness and clarity

References

-- Huston, G. “Interconnection, Peering, and Settlements.” APNIC, Internet routing economics overview. -- CAIDA Documentation: AS Relationships Inference Methodology. -- bgpsimulator.com interactive BGP visualization and examples. -- Cloudflare Learning Center: “What is BGP?”