三態內容尋址記憶體 (Ternary Content-Addressable Memory) 是一個有效率的硬體設備可以用來幫助我們進行快速的IP查找。然而，由於網路上路由路徑時常更新，存在TCAM中的IP位址前綴也必須同時做更新的動作，也就是指加入新的IP位址前綴到TCAM之中或者從TCAM之中刪除某些IP位址前綴。為了保持TCAM查找的速度跟正確性，存在TCAM之中的IP位址前綴必須要保持彼此之間互相包含的相對關係，也因此每當TCAM更新時，有少量的IP位址前綴搬移的動作會發生。
在這篇論文之中，我們基於路由表中IP位址前綴彼此之間的階層關係提出了一個新的TCAM更新演算法。我們利用TCAM之中未使用到的extra bits來幫助我們進行TCAM管理的動作，此外我們使用了極少量的記憶體來記錄那些因為刪除動作而產生在TCAM之中的空白位置。我們利用BGP網站獲得的路由表及使用V6Gen路由表產生器所產生的路由表來進行實驗，實驗結果顯示我們的方法在每次進行更新時所平均需要的搬移次數幾乎跟CAO_OPT一樣好，重要的是，我們的方法不需要額外花費記憶體儲存複雜的資料結構，也不需要停止update的動作來等待記憶體的存取。

A Ternary Content-Addressable Memory (TCAM) is an efficient hardware device for fast IP lookups. However, prefixes may be added/deleted into/from the TCAM due to the Internet route changes. To keep the speed and correctness of the TCAM search process, TCAM coprocessors must maintain the enclosure relationship among prefixes and perform a small number of TCAM movements for the update process.
In this paper, we propose a novel TCAM update algorithm based on the hierarchy of prefixes in routing tables. We using the extra bits in TCAM to support the proposed TCAM management and present a simple and efficient auxiliary data structure to record the free empty that created from deletion. The experimental results based on the routing table got from BGP and routing table from V6Gen generator show the average movements per update are almost as well as the existing CAO_OPT scheme based on prefix chain-ancestor ordering. Besides, our method save the memory that using in CAO_OPT for maintains the tries structure and update without memory access time.

[1]Y. Rekhter and T. Li, RFC1518: An Architecture for IP Address Allocation with CIDR, Internet Engineering Task Force (IETF), Sept. 1993.
[2]J. Yu V. Fuller, T. Li and K. Varadhan, RFC1519: Classless Inter- Domain Routing (CIDR): an Address Assignment and Aggregation Strategy, Internet Engineering Task Force (IETF), Sept. 1993.
[3]W.Doeringer, G .Karjoth, and M.Nassehi, “Routing on Longest- Matching Prefixes,” IEEE/ACM Trans. Networking, Vol. 4, Feb.1996, pp. 86-97.
[4]R. Hinden and S. Deering, RFC3513: Internet Protocol Version 6 (IPv6) ddressing Architecture, Internet Engineering Task Force (IETF), April. 2003.
[5]S. Deering R. Hinden and E. Nordmark, RFC3587: IPv6 Global Unicast Address Format, Internet Engineering Task Force (IETF), August. 2003.
[6]Z. Pfeffer B. Gamache and S.P. Khatri, “A fast ternary cam design for IP networking applications,” ICCCN 2003, 20-22 Oct. 2003, pp. 434 – 439.
[7]Wang He-Ming Wang Zhen-Xing and Sun Ya-Min, “High-performance IPv4/IPv6 dual-stack routing lookup,” 18th International Conference on Advanced Information Networking and Applications, 2004. AINA 2004., 2004, vol. 1, pp. 476–
[8]Kai Zheng , Chengchen Hu, Hongbin Liu and Bin Liu, “An ultra high throughput and power efficient TCAM based IP lookup engine,” INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 7-11 March 2004 Volume: 3, on page(s): 1984-1994 vol.3.
[9]Zhiyong Liang and Jianping Wu, Ke Xu, “A TCAM based IP lookup scheme for multi nexthop routing,” Computer Networks and Mobile Computing, 2003. ICCNMC 2003. 2003 International Conference on, 20-23 Oct. 2003 on page(s): 128-135.
[10]Ravikumar, V.C. and Mahapatra, R.N., “TCAM Architecture for IP Lookup Using Prefix Properties,” Micro, IEEE, Mar-Apr 2004 Volume: 24, Issue: 2 On page(s): 60- 69
[11]P. Francis A.J. McAuley, “Fast routing table lookup using cams,” INFOCOM 93, 28 March-1 April 1993, vol. 3, pp. 1382 – 1391.
[12]Ravikumar, V.C. and Mahapatra, R.N., “TCAM Architecture for IP Lookup Using Prefix Properties,” Micro, IEEE, Mar-Apr 2004 Volume: 24, Issue: 2, on page(s): 60- 69.
[13]Mohammed J.Akhbarizadeh, Mehrdad Nourani, Rina Panigraphy, and Samar Sharma, “A TCAM-based parallel architecture for high speed packet forwarding,” IEEE Transactions on Computers, vol.56, pp.58- 72, 2007.
[14]Panigrahy, R. and Sharma, S.,“Reducing TCAM power consumption and increasing throughput,” High Performance Interconnects, 2002. Proceedings. 10th Symposium on, 2002 on page(s): 107- 112.
[15]http://bgp.potaroo.net/index-bgp.html.
[16]Devavrat Shah and Pankaj Gupta, “Fast updating algorithms for TCAMs,” IEEE Micro Volume 21, Issue 1 (January 2001) Pages: 36 – 47.
[17]Kai Zheng and Bin Liu, “A Scalable IPv6 Prefix Generator for Route Lookup Algorithm,” Advanced Information Networking and Applications, 2006. AINA 2006. 20th International Conference on , 18-20 April 2006 Volume: 1, On page(s): 6.
[18]Yeim-Kuan Chang, "Simple and Fast IP Lookups Using Binomial Spanning Trees," COMPUTER COMMUNICATIONS, Volume 28, Number 5, pp. 529-539, March 2005. (SCI)
[19]Yeim-Kuan Chang, Yung-Chieh Lin, "A Fast and Memory Efficient Dynamic IP Lookup Algorithm Based on B-Tree," Proc. of the IEEE 23'rd International Conference on Advanced Information Networking and Applications (AINA-09) pp. 78 - 284, 26-29 May, 2009.
[20]Weidong Wu and Ruixuan Wang, “A TCAM management scheme for IP lookup,” Networks, 2006. ICON '06. 14th IEEE International Conference on, Sept. 2006 Volume: 1, on page(s): 1-4
[21]WANG Zhi-heng, YE Qiang and BAI Ying-cai, “Fast update algorithm for TCAM-Based routing lookups,” journal of Shanghai Jiaotong University, Vol.E7, No.1, 2002, 8~14.
[22]Weidong Wu, Bingxin and Feng Wang, “Efficient location of free spaces in TCAM to improve router performance,” International journal of communication systems, March 2005.
[23]Yi Tang, Wei Lin and Bin liu, ”A TCAM Index Scheme for IP Address Lookup” Communications and Networking in China, 2006. ChinaCom '06. First International Conference on, 25-27 Oct. 2006, On page(s): 1 – 5
[24]Miguel A. Ranchez, Ernst W. Biersack and Walid Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Trans. Networking, Mar/Apr 2001, Volume 15, Issue:2, On page(s): 8 – 23.
[25]Mohammad J. Akhbarizadeh and Mehrdad Nourani Cyrus D. Cantrell, “Prefix segregation scheme for a TCAM-Based IP forwarding engine” IEEE micro, July/August 2005 (vol. 25 no. 4).
[26]Pi-Chung WANG, Yi-Ting FANG and Tzung-Chain Huang, “Routing Table Compaction for TCAM-Based IP Address Lookup” IEEE TRANS. COMMUNICATIONS, VOL.E98-B, NO.5, MAY 2010.
[27]Yi-Mao Hsiao, Ming-Jen Chen, Yu-Jen Hsiao, Hui-Kai Su and Yuan-Sun Chu, “A Fast Update Scheme for TCAM-Based Ipv6 Routing Lookup Architecture,” Proceedings of the 15th Asia-Pacific Conference on Communications (APCC 2009)-204.
[28]Parineeth M Reddy, ”Fast Updating Algorithm for TCAMs using Prefix Distribution Prediction” 2010 International Conference on Electronics and Information Engineering (ICEIE 2010).