臺灣博碩士論文加值系統

在查找IP 位址，TCAM 是一個快速並且普遍的硬體。然而，TCAM有幾個缺點，包括高成本，高功耗和有限的空間。在本文中，我們提出了一個基於樹的演算法，最長後綴分割，降低了在查找IP地址時儲存在TCAM的條目數。我們的方法由兩部分組成：層數壓縮和最長後綴分割算法。首先我們對所有填充係數大於我們所預定的閾值的子樹進行層數壓縮。層數壓縮可移除有太多支路的子樹，在那樣的情況下，最長後綴分割算法的效能是比較低的。然後，我們使用最長後綴分割算法將剩餘的樹分割成多個可以使用一個TCAM條目和SRAM來儲存的後綴。實驗的結果表明相對於原始的路由表，通過改變預定的閾值，我們的方法可以降低50％到95％的TCAM條目。由於TCAM的缺點都跟所需要使用的條目數量有關，我們的方式顯著的提高了使用TCAM來執行IP位址查找的可行性。

Ternary content addressable memory (TCAM) is a fast and popular hardware device for IP address lookup. However, TCAM has several drawbacks, including high cost, high power consumption and limited space. In this paper, we present a trie-based algorithm, Longest Suffix Split, for reducing the number of TCAM entries that are stored in the TCAM for IP address lookup. Our scheme consist of two parts: level compression and longest suffix split algorithm. First we perform level compression to deal with the subtries, in which the fill factor exceeds a predefined threshold. Level compression can remove the subtries with too much braches, in which the longest suffix split algorithm is inefficient. Then, we employ the longest suffix split algorithm to divide the remaining prefix trie into different suffixes, which can be stored using one TCAM entry and SRAM word. The experimental results show that by varying the value of the fill factor, our scheme can reduce the TCAM entries for the original routing tables from 50% to 95%. Because the drawbacks of TCAM are related to the required entries, our scheme significantly improves the feasibility of TCAM-based IP address lookup.

摘要 i
Abstract ii
Table of Contents iii
Chapter 1 Introductions 1
Chapter 2 Related Works 4
Chapter 3 Longest Suffix Split 8
3.1 Longest Suffix Split Algorithm 8
3.2 Level Compression 11
3.3 Data Structures 14
3.4 Search Procedure 16
Chapter 4 Incremental Updates 20
Chapter 5 Experimental Results 22
5.1 Algorithm Analysis 22
5.2 Reduction Performance 29
5.3 Update Performance 31
Chapter 6 Conclusions 33
References 34

[1] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small forwarding tables for fast routing lookups,” ACM SIGCOMM Computer Communication Review, vol. 27, no. 4, pp. 3–14, 1997.
[2] V. Srinivasan and G. Varghese, “Faster ip lookups using controlled prefix expansion,” in ACM SIGMETRICS Performance Evaluation Review,vol. 26, no. 1. ACM, 1998, pp. 1–10.
[3] S. Nilsson and G. Karlsson, “Ip-address lookup using lc-tries,” Selected Areas in Communications, IEEE Journal on, vol. 17, no. 6, pp. 1083–1092, 1999.
[4] P. Gupta, S. Lin, and N. McKeown, “Routing lookups in hardware at memory access speeds,” in INFOCOM’98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings. IEEE, vol. 3. IEEE, 1998, pp. 1240–1247.
[5] B. Lampson, V. Srinivasan, and G. Varghese, “Ip lookups using multiway and multicolumn search,” IEEE/ACM Transactions on Networking (TON), vol. 7, no. 3, pp. 324–334, 1999.
[6] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable high speed ip routing lookups,” ACM SIGCOMM Computer Communication Review, vol. 27, no. 4, pp. 25–36, 1997.
[7] N. Huang and S. Zhao, “A novel ip-routing lookup scheme and hardware architecture for multigigabit switching routers,” Selected Areas in Communications, IEEE Journal on, vol. 17, no. 6, pp. 1093–1104, 1999.
[8] K. Huang, G. Xie, Y. Li, and A. Liu, “Offset addressing approach to memory-efficient ip address lookup,” in INFOCOM, 2011 Proceedings IEEE. IEEE, 2011, pp. 306–310.
[9] S. Kasnavi, P. Berube, V. Gaudet, and J. Amaral, “A cache-based internet protocol address lookup architecture,” Computer Networks, vol. 52, no. 2, pp. 303–326, 2008.
[10] L. Hung and Y. Chen, “Parallel table lookup for next generation internet,” in Annual IEEE International Computer Software and Applications Conference. IEEE, 2008, pp. 52–59.
[11] K. Ravindran, N. Satish, Y. Jin, and K. Keutzer, “An fpga-based soft multiprocessor system for ipv4 packet forwarding,” in Field Programmable Logic and Applications, 2005. International Conference on. IEEE, 2005, pp. 487–492.
[12] H. Liu, “Routing table compaction in ternary cam,” Micro, IEEE, vol. 22, no. 1, pp. 58–64, 2002.
[13] V. Ravikumar and R. Mahapatra, “Tcam architecture for ip lookup using prefix properties,” Micro, IEEE, vol. 24, no. 2, pp. 60–69, 2004.
[14] R. Brayton, Logic minimization algorithms for VLSI synthesis. Springer,1984.
[15] W. Lu and S. Sahni, “Low-power tcams for very large forwarding tables,” IEEE/ACM Transactions on Networking (TON), vol. 18, no. 3, pp. 948–959, 2010.
[16] T. Mishra and S. Sahni, “Duos-simple dual tcam architecture for routing tables with incremental update,” in Computers and Communications (ISCC), 2010 IEEE Symposium on. IEEE, 2010, pp. 503–508.
[17] F. Zane, G. Narlikar, and A. Basu, “Coolcams: Power-efficient tcams for forwarding engines,” in INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, vol. 1. IEEE, 2003, pp. 42–52.
[18] M. Akhbarizadeh, M. Nourani, R. Panigrahy, and S. Sharma, “A tcambased parallel architecture for high-speed packet forwarding,” IEEE Transactions on Computers, pp. 58–72, 2007.
[19] H. Lim and J. Mun, “Nxg06-1: An efficient ip address lookup algorithm using a priority trie,” in Global Telecommunications Conference, 2006. GLOBECOM’06. IEEE. IEEE, 2006, pp. 1–5.
[20] N. Tzeng, “Routing table partitioning for speedy packet lookups in scalable routers,” IEEE Transactions on Parallel and Distributed Systems, pp. 481–494, 2006.
[21] S. Dharmapurikar, P. Krishnamurthy, and D. Taylor, “Longest prefix matching using bloom filters,” in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications. ACM, 2003, pp. 201–212.
[22] F. Pong and N. Tzeng, “Suse: superior storage-efficiency for routing tables through prefix transformation and aggregation,” IEEE/ACM Transactions on Networking (TON), vol. 18, no. 1, pp. 81–94, 2010.
[23] H. Yu, “A memory-and time-efficient on-chip tcam minimizer for ip lookup,” in Proceedings of the Conference on Design, Automation and Test in Europe, 2010, pp. 926–931.
[24] “University of Oregon Route Views Project,” http://www.routeviews.org/, 2011, [Online; accessed 10-October-2011].
[25] V.C. Ravikumar, R. N. Mahapatra, L. N. Bhuyan. “EaseCAM: An Energy and Storage Efficient TCAM-Based Router Architecture for IP Lookup,” IEEE Transactions on Computers, vol. 54, no. 5, pp. 521–533, May 2005.
[26] T. Mishra and S.Sahni, PETCAM – A Power Efficient TCAM for Forwarding Tables, http://www.cise.ufl.edu/?sahni/papers/petcam.pdf
[27] E.W. B. Miguel A. Ruiz-Sanchez and W. Dabbous, “Survey and taxonomy of ip address lookup algorithms,” IEEE Network Magazine, vol. 15, no. 2, pp. 8–23, 2001.
[28] H. Song, S. Dharmapurikar, J. Turner, and J. Lockwood, “Fast hash table lookup using extended bloom filter: an aid tonetwork processing,” in Proceedings of ACM SIGCOMM ’05, Philadelphia, PA, August 2005, pp. 181–192.
[29] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, “Longest prefix matching using bloom filters,” in Proceedings ofACM SIGCOMM ’03, August 2003, pp. 201–212.