Constructing Optimal IP Routing Tables

Richard P. Draves, Christopher King, Srinivasan Venkatachary, and Brian N. Zill

Abstract

The Border Gateway Protocol (BGP) populates Internet backbone routers with routes or prefizes . We 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 we 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. We present performance measurements on four publicly available databases and a formal proof that ORTC does produce the optimal set of routes.

Details

Publication typeTechReport
URLhttp://www.ieee.org/
NumberMSR-TR-98-59
Pages25
InstitutionMicrosoft Research
PublisherInstitute of Electrical and Electronics Engineers, Inc.
> Publications > Constructing Optimal IP Routing Tables