Constructing Optimal IP Routing Tables

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.

tr-98-59.ps
PostScript file
tr-98-59.pdf
PDF file

Publisher  Institute of Electrical and Electronics Engineers, Inc.
© 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Details

TypeTechReport
URLhttp://www.ieee.org/
NumberMSR-TR-98-59
Pages25
InstitutionMicrosoft Research
> Publications > Constructing Optimal IP Routing Tables