Constructing Optimal IP Routing Tables
Source: Northeastern University
The Border Gateway Protocol (BGP) populates Internet backbone routers with routes or prefixes. The authors present an algorithm to locally compute (without any modification to BGP) equivalent forwarding tables that provably contain the minimal number of prefixes. For large backbone routers, the Optimal Routing Table Constructor (ORTC) algorithm that they present produces routing tables with roughly 60% of the original number of prefixes. The publicly available MaeEast database with 41315 prefixes reduces to 23007 prefixes when ORTC is applied. They present performance measurements on four publicly available databases and a formal proof that ORTC does produce the optimal set of routes.