On storage partitioning of internet routing tables: A P2P-based enhancement for scalable routers

Fueled by increasing demands of enterprise and individual users, the Internet has developed extremely fast in the past two decades. The global routing table, which is commonly quantified as kernel routing entries(REs), has also been growing at an alarming rate over the last few years. In particular, the scale of the Internet REs has exceeded 400k, causing a severe bottleneck to routing storage. To mitigate such a problem, scalable routing systems have been widely suggested. Up to now, the research on routing table (RT) partitioning storage has only achieved limited results. Furthermore, the current RT partitioning applies the caching mechanism, whose implementation on routers is complex and the performance is dissatisfactory. In this paper, we investigate a peer-to-peer (P2P) based storage partitioning approach called P2P packet routing (PPR) for the first time to better manage the Internet RTs. Our design organizes the line cards (LCs) into a P2P network; the LCs will act as peers in our system and provide such basic functions as routing and forwarding services to each other. RT locating can be achieved using a very few of virtual REs(VREs) which can perfectly merge with the real REs. To further balance the LC storage, enhanced PPR (EPPR) is introduced to guarantee that the REs of RT can be evenly partitioned into each LC. Our trace-based evaluation shows that the proposed framework can dramatically balance and reduce the total number of REs on LCs. It is worth noting that such enhancement is compatible with commercial routing systems and only requires minor modifications on the existing design.