Routing: Finding a Path

Part of: Computer Systems & Networks

What Is Routing? Routing is the process of choosing a path for each packet from sender to receiver. Special devices called routers read each packet's destination and forward it toward its goal, one hop at a time. There is no fixed circuit reserved in advance; routers make decisions dynamically based on the current network. The Network as a Graph We can model a network as a graph : each router is a node and each direct link is an edge . Finding a route then becomes finding a path between two nodes. The number of links a packet crosses is the hop count . Breadth-First Search Finds the Fewest Hops To find the route with the fewest hops , we explore the network level by level using breadth-first search (BFS) . BFS visits all nodes one hop away, then two hops away, and so on, so the first time it reaches the destination it has used the shortest path. Why Hop Count Matters - Fewer hops usually means lower latency , because each router adds a small processing delay. - Routers exchange information so each can pick a good next hop without knowing the whole network. - If the shortest path is congested or down, routing can shift packets onto another path. Routing is what turns a pile of indep

Challenge: Shortest Hop Count