網際網路快速路由搜尋演算法之設計與分析

Abstract

在骨幹網際網路中，欲提升封包的傳送速度需要快速的傳送連結以及高速路由器，目前商用上已經提供每秒能傳送Gigabit的光纖，因此，快速的路由器成為提升網際網路容量的關鍵。一個高速的路由器內部必須要有足夠的資料頻寬以及封包處理的能力來達到每秒鐘處理百萬個以上的封包，在交換技術日亦成熟的現今，需要多次記憶體存取的封包路由搜尋便成為路由器中最大的瓶頸。 在本論文中，我們提出了快速的路由搜尋以及原則比對演算法。在路由搜尋中，我們必須針對封包的目的位址找出最佳對應的路由，而在原則比對演算法中，則是針對Header中的多個欄位去找出最低成本的封包處理原則。 我們的第一個路由搜尋演算法是針對現有的演算法加以改進，我們以增加少許記憶體的代價，將所需的記憶體存取次數從三次降為兩次，而且我們的方法可以利用管線化硬體設計來達到進一步的加速。 接下來，我們研究路由表的特性並提出第二個方法。藉由事先的運算處理，我們可以將最佳對應路由問題複雜度降至最低，並利用較為簡單的演算法來作路由搜尋。在實驗中，我們的方法可以提供每秒30個百萬封包以及五千次路由更新的能力。 在第三個演算法中，我們設計了階層智慧壓縮樹，利用此新的資料結構，我們可將擁有十萬路由的路由表放置於約900 Kbytes的記憶體中，並在九次記憶體存取的時間內完成IPv4的路由搜尋，此方法並提供累計增加的更新，以及其他改良的方式，例如快速的IPv6路由搜尋。 最後，為了解決更為廣泛的原則比對問題，我們提出了改良的Tuple修整演算法，在增加合理的記憶體成本之下，我們可以大幅減少存取Tuple的個數。我們的演算法皆針對現有的路由表設計，並希望這些技術也可以應用在下一代Terabit的傳輸技術上。

Speeding up the packet forwarding in the Internet backbone requires high-speed transmission links and high performance routers. The transmission technology keeps evolving and provision of gigabit fiber links is commonly available. Consequently, the key to increase the capacity of the Internet lies in fast routers. A multi-gigabit router must have enough internal bandwidth to switch packets between its interfaces at multi-gigabit rates and enough packet processing power to forward multiple millions of packets per second (MPPS). Switching in the router has been studied extensively and solutions for fast packet processing are commercially available. As a result, the remaining major obstacle for the high performance router design is the slow, multi-memory-access IP header processing. In this thesis, we present efficient algorithms for destination address lookups and fast filter matching; these are important components of packets processing in a router. The destination address lookup problem is to find the best matching prefix (BMP) for a given address from among a set of prefixes in the routers' forwarding table while in the filter matching, the problem is to find the lowest-cost filter for a given packet header. Each filter is a rule specified on multiple header fields. Our first address lookup algorithm is to improve the lookup performance of the existing scheme which performs the IP address lookup with reasonable-size SRAM and three memory accesses in hardware. We claim that with a little extra memory, it is able to further reduce the lookup time to two memory accesses. Moreover, it can be implemented in pipelined hardware so that one routing lookup per memory access can be achieved. Consequently, we investigate the properties of the routing table and present the second approach for IP lookups, our approach does not require the rule of BMP and thus significantly reduces the complexity. By applying our proposed approach, the computation cost of existing schemes can be significantly reduced. With the efficient IP lookup algorithm, we improve the binary search on prefixes to 30 MPPS and 5,000 route updates/s under the same experiment setup with an even larger routing table. In the third algorithm, we propose the level smart-compression tries. With the new concept, the size of the forwarding table can be compressed to less than 900 Kbytes for a large routing table with more than 100,000 routing entries. It can accomplish one IPv4 route lookup with maximum nine memory accesses. And also, incremental update is supported. Several enhancements are presented for feasible implementation and IPv6 scalability. To deal with the further general policy-based routing problem, the enhanced tuple pruning is proposed. With few extra filters adding to the tuples, the number of probed tuples can be reduced to one. Our algorithms are predominantly based on the properties of the real-life routing tables to facilitate fast searching. While we have presented algorithms for gigabit speed lookups, we expect that similar techniques can be used to develop terabit speed lookups when the need arises in the future.