Internet Routing

Graph Theory · Axiom Academy

How Graph Theory Powers Every Click, Stream, and Message Across the Globe Every time you send an email, stream a video, or load a webpage, data packets travel across the internet—one of the largest and most complex graphs ever created. But what does this graph look like? Vertices (Nodes): Routers, servers, and network devices Edges (Links): Physical or wireless connections between devices Edge Weights: Latency (delay), bandwidth, cost, or reliability Right now, there are billions of vertices and trillions of potential paths. Your data needs to find the best route from source to destination—and it needs to do it in milliseconds. Let's visualize a simplified internet network. Each router is a vertex, and each connection is an edge with a weight representing latency (in milliseconds). How Do Routers Find the Best Path? You just watched the packet take the shortest path from A to G. But how did the routers know which path to choose? There are multiple possible routes! Think About It: What algorithm do you think routers use to find the shortest path? In the real internet, routers use sophisticated protocols to build and maintain routing tables. The two main approaches are: The most popular interior routing protocol uses Dijkstra's algorithm! Each router: Discovers its neighbors and link costs Floods this information to all other routers Builds a complete graph of the network Runs Dijkstra's algorithm to compute shortest paths Updates its routing table with next-hop information

This is the written version of the interactive lesson above. See the full Graph Theory course.