Scale the Internet routing table by generalized next hops of strict partial order

Qing Li, Mingwei Xu, Qi Li, Dan Wang, Yong Jiang, Shu Tao Xia, Qingmin Liao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

The Internet routing tables have been expanding at a dramatic and increasing rate. Although the latest high-performance routers provide enough capacities, Internet Service Providers (ISPs) cannot afford to upgrade their routers at the pace of routing table growth. Shrinking the routing table, especially the TCAM-based Forwarding Information Base (FIB), is more feasible. In this paper, we propose a scheme to aggregate the FIB based on generalized next hops of strict partial order (SPO). We first use generalized SPO next hops to construct the Nexthop-Selectable FIB (NSFIB), where each prefix has multiple next hops. Our NSFIB aggregation avoids the aggregation performance degrading with the network density increasing, which is one main defect of the traditional single-nexthop FIB aggregation. We then design different levels of aggregation algorithms to aggregate the NSFIB. Besides, we control the path stretch by setting an upper limit to filter bad next hops. We also introduce routing protection by the pre-computed SPO next hops. According to our simulation, our aggregation algorithms shrink the FIB to 5–15%, compared with 20–60% of single-nexthop FIB aggregation algorithms; our method works very well in controlling the path stretch; and SPO next hops protect 50–95% (topology-related) failure-affected packets.

Original languageEnglish
Pages (from-to)101-115
Number of pages15
JournalInformation Sciences
Volume412-413
DOIs
Publication statusPublished - 1 Oct 2017

Keywords

  • FIB aggregation
  • Forwarding information base
  • Routing scalability
  • SPO next hop

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Cite this