高效率之IP位址查詢技術:單點廣播與多點廣播

Abstract

由於網際網路快速掘起，使得路由器(router)在IP位址查詢運作上的負擔逐漸加重，為了使其不致成為網路上的瓶頸所在，快速的IP位址查詢技術是很重要的設計環節；另一方面，使用者急遽增加導致路由表格的大小也快速遞增，如何設計一高空間效率(space efficiency)的路由表格架構來容納大量路由資訊是另一個重要設計環節。在本篇論文中，我們首先針對單點廣播位址查詢，運用壓縮位元映對(CBM)技術在trie搜尋資料結構上，進而提出一種壓縮trie (compression trie)的路由表格架構，其架構空間效率相當高，故能以較小的表格空間儲存大量路由資訊；由於路由字首長度(prefix length)絕大多數分佈在24以下，此壓縮trie將可使一次IP位址查詢運作所需的表格存取次數降低至三次以內，達到高速IP位址查詢的目的；藉由表格的快速建立，我們可以重新建立一份路由表格的方式解決路由更新(route update)的問題。 在多點IP位址查詢技術方面，必須同時對目的地(destination)及來源(source)位址作絕對符合(exact matching)的搜尋動作，方式上和單點IP位址查詢不同。我們運用類似CBM技術搭配內容定址記憶體(content addressable memory)設計了一種多點IP位址查詢技術；除了一次的多點IP位址查詢只需要三次表格存取，維持高速位址查詢的需求外，表格本身大小的成長幅度亦在合理範圍內；但實際網路上的多點廣播使用者分佈狀況尚無從得知，因此表格大小本身的擴充性是無法正確斷定的。

The load of a router on performing the IP address lookup operation is more heavy with the explosive growth of the Internet. In order to prevent it from becoming the bottleneck, a router needs a fast IP address lookup scheme. On the other hand, the router needs an efficient forwarding table structure to store a large amount of routing prefixes. In this thesis, we first adopt the compression bit map (CBM) technique on a general trie to propose an enhanced forwarding table structure, compression trie (CT). Because of its better space-efficiency, the forwarding table can store many routing entries and the table size is still small. Most of the prefixes are of prefix length less than or equal to 24 such that almost all address lookups can be accomplished in one to three memory accesses. On the other hand, we employ a fast forwarding table construction algorithm to rebuild it quickly for solving the route update problem. Different from the unicast address lookup scheme, a router performs the exact matching search on the destination and source addresses at the same time when executing the multicast address lookup. We adopt the CBM-like technique incorporating with the content addressable memory (CAM) to design a multicast address lookup scheme. Each multicast address lookup needs three memory accesses and the forwarding table size increases under a reasonable scaling factor. Unfortunately, it can not be predicted that how many the groups and sources will the network really have. Therefore the property about the scalability of this forwarding table structure could not be precisely assessed.