Modeling the Internet Routing Scalability: From Qualitative Description to Quantitative Evaluation

The Internet has been growing rapidly during the past few decades. Its routing system may encounter scalability problem as the size of Internet keeps growing. The Internet Research Task Force (IRTF) highlighted this issue lately and inspired many proposals that attempt to address this problem. However, those proposals do not reach a consensus on a fruitful solution. Instead of presenting another new proposal, this paper deals with specification, analysis and evaluation of the routing scaling of the Internet. The qualitative analysis in this paper reveals gains and losses of different techniques that aim to improve the scalability of the Internet routing system. In particular, the analysis focuses on techniques of route aggregation, forwarding information base (FIB) compression and route cache mechanism, which correspond to tradeoffs between routing scaling and engineering considerations on the functioning, overhead and performance of the routing system respectively. Based on understanding of these tradeoffs, we apply the Analytic Hierarchy Process (AHP) to develop a quantitative evaluation framework that can evaluate alternative routing schemes. This modeling tool can systematically capture various evaluation criteria, where each routing scheme leads to quantified gains and losses under given evaluation criteria.