路由器為網路上用於傳送封包之設備，其最主要的功能之一即為路由查詢。由於近年來網路發展迅速，導致資訊量及路由表之資料筆數大為增加，其結果嚴重影響路由器之效能，因此設計一高效能路由查詢演算法有其必要。
在此篇論文中，我們基於對未覆蓋IP位址空間之觀察，提出兩個方法來提高路由查詢的效能，我們使用未覆蓋IP位址空間來過濾出不可能會比對成功之前綴，此兩種方法之不同之處在於，其中一種為按照前綴長度將前綴分組，而另一種為按照層將前綴分組。
我們的實驗數據顯示，在記憶體消耗部分，按照前綴長度分組的方法所消耗的記憶體相較於另外一個以節省記憶體為名的演算法Tree Bitmap [11] 還少一些，再者，另一按照層分組的方法甚至又比第一種提出的方法消耗又再少的記憶體。在路由平均查詢效能部分，以前綴長度分組之方法，其平均消耗時脈與Tree Bitmap相似，但就另外一個按照層分組之方法，其平均消耗時脈為Tree Bitmap之62%，2-MPT [12]之45%，及二元樹之24%。因此，在實務上，我們所提出的方法可被考量實作於路由器上。

A router is a network device that forwards packets in the internet and IP lookup operation is one of its major functions. As the internet is rapidly expanded nowadays, the internet traffic dramatically increases the entries of the routing table, and hence poses a serious degradation on the capacity of a router. A design of high performance IP lookup algorithm is needed.
In this thesis, based on the observations of the uncovered address space, we propose two schemes to improve the IP lookup performance. These schemes make the use of uncovered address space as filters that filter out groups of prefixes which don’t contain candidate for the best-matching prefix. The difference between the two proposed schemes is that one is to group prefixes by length and the other one is to group prefixes by layer.
As the simulation results show, the proposed scheme which group prefixes by length consumes slightly less memory than Tree Bitmap [11] that is known for a memory efficient algorithm. Furthermore, the other proposed scheme which group prefixes by layer consumes even less memory than the first proposed scheme. For search performance, the average number of clocks consumed by the first proposed scheme is similar to the Tree Bitmap. But for the proposed scheme of grouping prefixes by layer, the average number of clocks consumed is about 62% of Tree Bitmap, 45% of 2-MPT [12], and 24% of binary trie. Therefore, in practice, our proposed schemes can be considered to be implemented in the routers.

[1] D. Meyer, University of Oregon Route Views Archive Project, at routeviews.org
[2] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
[3] Y.-K. Chang and D.-J. Lin, “Design and Implementation of Dynamic Routing Tables,” Master Thesis of Computer Science and Information Engineering, NCKU, 2005.
[4] Y.-K. Chang and Y.-C. Lin, “Dynamic Routing Tables Using Simple Balanced Search Trees,” Lecture Notes on Computer Science (LNCS) 3961 (International Conference on Information Networking (ICOIN)), 2006.
[5] X. Meng, Z. Xu, B. Zhang, G.. Huston, S. Lu, and L. Zhang, “IPv4 Address Allocation and the BGP Routing Table Evolution,” ACM SIGCOMM, pp. 71-80, Jan. 2005.
[6] Yeim-Kuan Chang, Fang-Chen Kuo, Han-Jhen Kuo, Cheng-Chien Su, "LayeredTrees: Most Specific Prefix based Pipelined Design for On-Chip IP Address Lookups", IEEE Transactions on Computers, accepted.
[7] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups,” Proceeding of ACM SIGCOMM, pages 25-36, September 1997.
[8] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed Prefix Matching,” ACM Transactions on Computer Systems, Volume 19 Issue 4 pages 440-482, November 2001.
[9] H. Lim, K. Lim, N. Lee and K, park, “On Adding Bloom Filters to Longest Prefix Matching Algorithms”, IEEE Transactions on Computers, Volume PP, Issue 99, August, 2012.
[10] V. Fuller, T. Li, J. Yu, and K. Varadhan, "Classless inter-domain routing (CIDR): an address assignment and aggregation strategy," RFC 1519, Sept. 1993.
[11] W. Eatherton, G. Varghese, Z, Dittia, “Tree Bitmap : Hardware/Software IP Lookups with Incremental Updates,” ACM SIGCOMM Computer Communication Review, Volume 34 Issue 2, Pages 97-122, April 2004.
[12] Sun-Yuan Hsieh, Yi-Ling Huang, Ying-Chi Yang, “Multiprefix Trie: A New Data Structure for Designing Dynamic Router-Tables,” IEEE Transactions on Computers, Volume 60, Issue 5, pp. 693-706, May 2011.
[13] Y.-K. Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding,” COMPUTER NETWORKS, SCI, 2007.
[14] H. Lim and Y. J. Jung, “A parallel multiple hashing architecture for IP address lookup,” IEEE HPSR, pp.91–95, 2004.