網路位址查詢是不斷增長的Internet流量中一項很重要的運算，網路位址包含在封包中，而通過不同網絡之間的路由器將封包轉送到目的位址的過程稱為網路路由。每個路由器都有一個路由表，當封包傳輸到路由器時，路由器將依據封包的目的地址查找路由表，再決定封包轉送的下一個出口。

在本文中，我們提出了兩種資料結構，Partitioning Multi-Level Trie（PMLT）和Partitioning Multi-Level Trie with a Bloom Filter（PMLT-BF）。提出PMLT主要是因為降低平均樹高可以獲得更高的位址搜尋速度和位址更新速度；提出PMLT-BF主要是由於減少存取記憶體的次數可以實現更快的位址搜尋時間。

在實驗中，使用IPv4資料庫AS1221，AS4637和AS6447，得到提出的兩種資料結構優於前人方法。由於分層PMLT和PMLT-BF的搜尋時間和更新時間優於前人方法；並且由於布隆過濾器技術，搜尋速度更快。在一般情況下，我們的資料結構對性能更好。

Currently, Internet Protocol (IP) address lookup is one of the most important operations in the era of growing Internet traffic. An IP address constitutes packets. The process of transfering a package to a destination through a router between different networks is called network routing. Each router has a router table. When a package is transferred to a router, the router looks up the router table according to the destination address of the package and determines the next destination of the packet.

In this paper, we propose two data structures namely partitioning multi-level trie (PMLT) and PMLT with a Bloom filter (PMLT-BF). The primary objective of the PMLT is to reduce the average tree height in order to obtain higher lookup and update speeds. The primary objective of PMLT-BF is to reduce of the number of memory accesses to achieve a faster lookup time.

Experimental revealed that the proposed data structures outperformed previously developed data structures, as determined according to the following benchmarks: IPv4 prefix databases AS1221, AS4637 and AS6447. In particular, the superior lookup time and update time of PMLT and PMLT-BF can be attributed to partitioning, and the superior lookup speed can be attributed to the application of a Bloom filter. In general, our data structures are superior options for achieving high performance.

[1] BGP Table obtained from http://bgp.potaroo.net/.
[2] M. Berger, IP lookup with low memory requirement and fast update," IEEE High Performance Switching and Routing, pp. 287-291, Jun. 2003.
[3] A. Broder and M. Mitzenmacher, Using Multiple Hash Functions to Improve IP lookups," Proceedings IEEE INFOCOM, vol. 3, pp. 1454-1463, 2001.
[4] S. Deering and R. Hinden, Internet protocol version 6 (IPv6) speci cation," RFC 1883, Dec. 1995.
[5] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, Small forwarding tables for fast routing lookups," Proceedings of SIGCOMM, pp. 3-14, 1997.
[6] S. Dharmapurikar, P. Krishnamurthy, and D. Taylor, Longest Pre x Matching Using Bloom Filters," IEEE/ACM Trans. Networking, vol. 14, no. 2, pp. 397{409, Feb. 2006.
[7] B. Fan, AD. G. ndersen, M. Kaminsky, and M. D. Mitzenmacher, Cuckoo lter: Practically better than bloom" In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies , pp. 75-88, Dec. 2014.
[8] V. Fuller, T. Li, J. Yu, and K. Varadhan, Classless inter-domain routing (CIDR): an address assignment and aggregation strategy," RFC 1519, Sep. 1993.
[9] S. Y. Hsieh, Y. L. Huang, and Y. C. Yang, Multi-Pre x Trie: a New Data Structure for Designing Dynamic Router-Tables," IEEE Transactions on Computers, vol. 60, no. 5, pp. 693-706, May 2011.
[10] S. Y. Hsieh, and Y. C. Yang, A Classi ed Multisu x Trie for IP Lookup and Update," IEEE Transactions on Computers, vol. 61, no. 5, pp. 726-731, May. 2012.
[11] S.-J. Huang, Multilevel Length-Based-Classi ed Index Table for IP Lookups and Updates," M.S. thesis, National Cheng Kung University, Taiwan.
[12] R. Jain, A Comparison of Hashing Schemes for Address Lookups in Computer Networks," IEEE Transactions on Communications, vol. 40, no. 10, pp. 1570-1573, Oct. 1992.
[13] J. Lee and H. Lim, Binary search on Trie levels with a Bloom lter for longest pre x match, International Conference on High Performance Switching and Routing, pp.
38-43, Jul. 2014.
[14] H. Lim, K. Lim, N. Lee and K. H. Park, On Adding Bloom Filters to Longest Pre x Matching Algorithms," IEEE Transactions on Computers, vol. 63, no. 2, pp. 411-423, Feb. 2014.
[15] H. Lim and Y.J. Jung, A Parallel Multiple Hashing Architecture for IP Address Lookup," IEEE High Performance Switching and Routing (HPSR), pp. 91-95, 2004.
[16] H. Lim, J. Seo, and Y. Jung, High Speed IP Address Lookup Architecture Using Hashing," IEEE Communications Letters, vol. 7, no. 10, pp. 502-504, Oct. 2003.
[17] H. Lim, C. Yim and E. E. Swart, Priority trie for IP address lookup," IEEE Transactions on Computers, vol. 59, no. 6, pp. 784-794, Jun. 2010.
[18] C. H. Lin, C. Y. Hsu, and S. Y. Hsieh, A Multi-index Hybrid Trie for IP Lookup and Updates," IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 10, pp. 2486-2498, Oct. 2014.
[19] J. H. Mun and H. Lim, New Approach for E cient IP Address Lookup Using a Bloom Filter in Trie-Based Algorithms," IEEE Transactions on Computers, vol. 65, no. 5, pp. 1558-1565, Jun. 2015.
[20] S. Nilsson and G. Karlsson, IP-address lookup using LC-trie," IEEE Journal on selected Areas in Communications, vol. 17, no. 6, pp. 1083-1092, Jun. 1999.
[21] J. Postel, Internet protocol darpa internet program protocol speci cation," RFC791, Sep. 1981.