一個低空間需求的快速IP繞送演算法

Abstract

現今網際網路（Internet）蓬勃發展，網路速度、路由查表（Routing Table）與交通流量（Traffic）都逐漸增大，也因此IP位址查表（IP Address Lookup）的困難度也隨之增加。而自從未分類內部領域路由（CIDR, Classless Interdomain Routing）的採用，路由器必須在路由查表中尋找對於IP位址而言最長的對應字首（Prefix），此乃為最符合之位址字首（BMP, Best Matching Prefix）。而在提升Internet的效能方面，瓶頸即在於路由器上的查表（Lookup）步驟。如何達到快速執行查表、減少路由查表的檔案大小，並更進一步提供快速的更新功能，將是本篇論文所要深究的主題。在利用壓縮二位元樹狀結構（Binary tree）之後，我們可以將原本有58,000位址字首的路由查表壓縮到300 K位元組以下。至於IP位址查表，在IPv4的規格下，最多只需要九次的記憶體存取。此外，我們所提出的方法也支援快速的遞增更新。

Nowadays, IP address lookup is becoming critical because of increasing routing table sizes, speed, and traffic in the Internet. With classless interdomain routing (CIDR), routers must find out the best matching prefix (BMP) for IP packets forwarding, which complicates the IP lookup. Since the IP lookup performance is a major design issue for the new generation routers, in this thesis we investigate the properties of the routing table and present a new IP lookup scheme. By using the concept of compression of routing intervals’ binary tree, the forwarding table’s size can be reduced to less than 300 Kbytes for a large routing table with more than 58,000 prefixes. It can be accomplish one IPv4 route lookup with maximum nine memory accesses. Furthermore, the incremental update is supported.