Trading Potatoes in Distributed Multi-Tier Routing Systems

The Internet is an example of a distributed system where the task of routing is performed in a multi-tier fashion: interdomain paths between autonomously-managed networks are subject to a global agreement (BGP), and the choice of intradomain paths is left to the discretion of each such network. When forwarding packets, Autonomous Systems (ASes) frequently choose the shortest path in their network to the next-hop AS in the BGP path, a strategy known as hot potato routing.