在最近幾年當中，網際網路位址(路由)查詢已經受到廣泛的注意，許多高效能的路由查詢演算法相繼被提出。在這些演算法中，其中ㄧ類是透過「事先計算」來加快路由查詢的速度及減低記憶體的需求。這類的演算法通常是無法有效的進行路由表更新的；但「事先計算」可以簡化由路由查詢演算法所建立的資料結構，因而在查詢速度及記憶體需求上有較佳的效能。另ㄧ方面，由於骨幹網路會因不同的原因而有多筆的路由更新。因此可以支援快速更新的路由查詢演算法是有必要的。
在本論文中，針對「事先計算」的方法，我們針對因為路由表更新所造成的成本加以討論，並將其直接列為「事先計算」的首要考慮因素，以便計算出來的資料結構能有效地支援動態路由更新，同時又可以保有快速的查詢速度。我們著重在一個以多元樹為基礎的查詢演算法，藉由討論路由表更新在多元樹上的成本，我們設計出一個演算法，讓我們在建構一個多元樹的時候可以使這個多元樹具有最小的更新成本。在這個演算法中我們使用到動態規劃的方法來幫助我們完成成本的計算，來達到多元樹的優化。

In high performance routers design IP address lookup is a major bottleneck. Using multibit tries to represent IP routing tables for IP lookup is efficient together with pre-computation. The advantages of implementing IP lookup using multibit tries are simplicity and slight search time; and drawbacks of that are large memory usage and large update cost. To reduce memory usage, Controlled Prefix Expansion was proposed by Srinivasan and Varghese (1999), which was a pre-computation based on dynamic programming to determine the best strides of multibit tries, including fix-strides multibit tries and variable-stride multibit tries that makes the storage of these multibit tries are minimal. By such pre-compute algorithm we can simplify the data structure construction and thus archive fast lookup speed and improve memory requirement, but it didn’t concern about when a single prefix is added or deleted. Since instabilities in the backbone protocols can lead prefixes update, algorithms that can support fast updates are desirable.
In this thesis we proposed a pre-compute algorithm that can support fast updates by modifying Srinivasan’s algorithm. We explore optimization issues proposed in Srinivasan’s algorithm. Our proposed algorithm aims to reduce update overhead of multibit tries, and finds out the update optimal multibit tries solutions appropriate to a given update traffic. Compared the tries solution obtained by controlled prefix expansion (Srinivasan’s algorithm), our solutions reach a 30% reduction of update overhead when number of multibit trie level is eight.

[1] A. Basu and G. Narlikar, “Fast Incremental Updates for Pipelined Forwarding Engines,” IEEE/ACM Transactions on Networking, vol.13, no.3, pp. 690-703, June 2005.
[2] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
[3] C. Labovitz, G. Malan and F. Jahabnian, “Internet routing instability,” Proceeding of ACM SIGCOMM, pp. 115-126, September 1997.
[4] D. Meyer, University of Oregon Route Views Archive Project, at http://archive.routeviews.org/.
[5] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of data structures in C++. New York: W.H. Freeman, 1995.
[6] H. Chao, “Next Generation Routers,” Proceeding of the IEEE, vol. 90, no. 9, pp. 1518-1558, September 2002.
[7] Jae-Young Kim, Byung-Jun Ahn and Young Sun Kim, “High Speed Lookup Scheme based on Two-Pass for Core Router,” The 9th Asia-Pacific Conference on Communications, Vol.3, pp. 1115-1118, 2003.
[8] Liang Zhiyong, Xu Ke, and Wu Jianping, “A Novel Model to Analyze the Performance of Routing Lookup Algorithms,” International Conference on Communication Technology Proceedings, Vol.1, pp.508- 513, 2006.
[9] M.A.Ruiz-Sanchez, E.W.Biersack, W.Dabbous, Dept. of Comput. Sci., INRIA, Sophia Antipolis, “Survey and Taxonomy of IP Address Lookup Algorithm,” IEEE Network, Vol.15, pp.8- 23, 2001.
[10] P. Gupta, S Lin, and N. McKeown, “Routing lookups in hardware at memory access speeds,” Proceeding of IEEE INFOCOM, pp. 1240-1247, April 1998.
[11] Priyank Warkhede, Subhash Suri, and George Varghese, “Multiway range trees: scalable IP lookup with fast updates,” Computer Networks: The International Journal of Computer and Telecommunications Networking, vol. 44, no. 3, pp. 289-303, February 2004.
[12] S. Nilsson and G. Karlsson, “IP-Address lookup using LC-trie,” IEEE Journal of Selected Areas in Communications, vol. 17, no. 6, pp. 1083-1092, June 1999.
[13] S. Sahni and K. S. Kim, “Efficient Construction Of Multibit Tries For IP Lookup,” IEEE/ACM Transactions on Networking, vol.11, no.4, pp.650-662, 2003.
[14] S. Sahni and K. Kim, “An O(logn) dynamic router-table design,” IEEE Transactions on Computers, vol. 53, no. 3, pp. 351-363, March 2004.
[15] S. Sahni, Data Structures, Algorithms, and Applications in Java, second edition Silicon Press, 2005.
[16] S. Sahni and K. S. Kim, “Efficient Construction of Pipelined Multibit-Trie Router-Tables,” Transactions on Computers, vol.56, no. 1, pp.32-43, Jan 2007.
[17] S. Sahni and Wencheng Lu, “Recursively Partitioned Static IP Router-Tables,” 12th IEEE Symposium on Computers and Communications, pp.437-442, July 2007.
[18] T. Cormen, C. Lieserson, R. Rivest, and C. Stein, Introduction to Algorithms, second edition MIT Press, 2001.
[19] V. Srinivasan and G. Varghese, “Fast address lookups using controlled prefix expansion,” ACM Transactions on Computer Systems, vol. 17, no. 1, pp. 1–40,Feb. 1999.
[20] Wencheng Lu and Sartaj Sahni, “Packet Forwarding Using Pipelined Multibit Tries,” 11th IEEE Symposium on Computers and Communications, Vol.3, pp.802- 807, 2006.
[21] Y. Jiang and F. Shang, “Research on Multibit-Trie Tree IP Classification Algorithm,” International Conference on Communications, Circuits and Systems Proceedings, Vol.3, pp.1786-1790, 2006.