On the Aggregatability of Router Forwarding Tables

Yaoqing Liu, Lan Wang, Xin Zhao, Beichuan Zhang

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

In this book chapter, the authors first present Optimal Routing Table Constructor (ORTC), an optimal one-time FIB aggregation algorithm that preserves strong forwarding correctness. The authors then present four-level FIB aggregation algorithm(s) that can handle dynamic routing updates while maintaining forwarding correctness. Afterwards, the authors evaluate our algorithms using routing tables from RouteViews, and compare the algorithms with ORTC using routing tables from a Tier-1 ISP. The authors found that ORTC's aggregation ratio is better than the Level 1, Level 2 and Level 3 algorithms, but the Level 4 algorithm has better aggregation ratio than ORTC as they relax the requirement of forwarding correctness. Finally, the authors evaluate the potential impact of introducing extra routable space in the Level 4 algorithm and discuss how to limit such negative impact.

Original languageEnglish (US)
Title of host publicationSolutions for Sustaining Scalability in Internet Growth
PublisherIGI Global
Pages39-59
Number of pages21
ISBN (Electronic)9781466643062
ISBN (Print)1466643056, 9781466643055
DOIs
StatePublished - Jul 31 2013

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'On the Aggregatability of Router Forwarding Tables'. Together they form a unique fingerprint.

Cite this