由於IPv6位址逐漸的增加，路由容量（route capacity）與查表延遲（lookup latency）已成為最重要的兩個議題。當路由器被應用在IPv6位址的不同層次時，路由字首的長度分佈（prefix length distribution）將有所不同。因此，如果將現存的IPv4位址查表法延伸到IPv6的系統中，查表的效能有可能因為路由字首的長度分佈而降低。為了減少字首長度分佈的影響，本文提出一個可多範圍查詢的查表機制，此機制可以同時對不同範圍的字首長度做查表，此查表方法之中使用平行式循環多餘檢查碼（parallel CRC compression mechanism）以減少記憶體空間。本文並且將提出的IPv6查表機制以硬體實作，實作的硬體架構分為：Multi-cycle與Pipeline方式。實驗結果顯示：整個記憶體的需求只有21 Mbytes，在Multi-cycle的架構下，查表的平均記憶體存取次數為1.5；在Pipeline下，平均每一個時脈週期可完成一筆位址查表。

　　Due to the increased address space in IPv6, route capacity and lookup latency become two of the most significant issues for a forwarding subsystem. The prefix length distribution can be quite different when a switching router is applied to the different level of the IPv6 address hierarchy. Hence, if an existing IPv4 routing lookup scheme is used in the IPv6 system, the performance may be degraded due to the variation of prefix length distribution. To reduce the impact of the prefix length distribution, it is necessary to lookup multi-range of the prefix length and perform address lookup in different range of the prefix length simultaneously. Thus, we propose the Three-Set-FLT lookup scheme: setting three range of the prefix length: 24 ~ 47, 48 ~ 55 and 56 ~ 64 to performe address lookup at the same time. The proposed lookup scheme adapts to the variation of prefix length distribution. This scheme employs a parallel CRC compression mechanism to significantly reduce memory size. Our proposed scheme is implemented by two architectures: Multi-cycle and Pipeline. The simulation result shows that the total memory size used is only 21 Mbytes. In the multi-cycle architecture, the average number of memory reference is about 1.5. In the pipeline architecture, the throughput is close to one address lookup per clock cycle when one pipeline is used.

[1]　“Answering IPv6 Lookup Challenges,” Available: http://www.commsdesign.com/news/showArticle.jhtml?articleID=51200476.

[2]　P. Hinden, and S. Deering, “IP Version 6 Addressing Architecture,” RFC 2373, IETF, Available: http://ww.ieft.org, July 1998.

[3]　P. Hinden, M. O’Dell, and S. Deering, “An IPv6 Aggregatable Glogal Unicast Address Format,” RFC 2374, IETF, Available: http://ww.ieft.org, July 1998.

[4]　M.A. Ruiz-Sanchez, E.W. Biersack, and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithm,” IEEE Network, Vol. 15, Mar.-Apr. 2001, pp. 8-23.

[5]　B. Gamache, Z. Pfeffer, and S.P. Khatri, “A FastTernary CAM Design for IP Networking Applications,” in Proc. IEEE ICCCN 2003, Oct. 2003, pp. 434-439.

[6]P. Gupta, S. Lin, and N. Mckeown, “Routing Lookups in Hardware at Memory Access Speeds,” in Proc. IEEE INFOCOM 1998, Apr. 1998, pp. 240-47.

[7]　Hyesook Lim, and Yeojin Jung, “A Parallel Multiple Hashing Architecture for IP Address Lookup,” in IEEE HPSR. 2004, pp.91-95.

[8]　B.A. Al-Khaffaf, E.K. Karuppiah, and R. Abdulah, ”Efficient Partition Based IPv6 Lookup Algorithm for Packet Forwarding,” IEEE Asia-Pacific Communications Conference 2003, Vol.1 , 21-24 Sept. 2003, pp.238 – 242.

[9]　R.C. Chang, and B.H. Lim, ”Efficient IP Routing Table Lookup Scheme,” IEEE Proc. Communications 2002, Vol.149 , Issue: 2 , April 2002, pp.77 – 82.

[10]　X.o Yao, L. Li, and G. Hu, “A Fast IPv6 Route Lookup Algorithm with Hash Compression,” IEEE Communications, Circuits and Systems Conference 2004, Vol.1 , 27-29 June 2004, pp.674 – 677.

[11]　Z. Wang, H. Wang, and Y. Sun, “High-Performance IPv4/IPv6 Dual-Stack Routing Lookup,” IEEE Proc. Advanced Information Networking and Applications Conference 2004, pp.476 – 481.

[12]　T. Hayashi, and T. Miyazaki, “High-Speed Table Lookup Engine for IPv6 Longest Prefix Match,” IEEE Global Telecommunications Conference 1999, pp.1576 – 1581.

[13]　M. Zitterbart, T. Harbaum, D. Meier, and D. Brokelmann, “Efficient Routing Table Lookup for IPv6,” The Fourth IEEE Workshop 1997, High-Performance Communication Systems, 23-25 June 1997, pp1 – 9.

[14]　S. Asadullah, and C. Popoviciu, ”IPv6 Deployment Scenarios & Case Studies,” Available: http://www.nanog.org/mtg-0410/pdf/asadullah.pdf, 2004.

[15]　M. Wang, S. Deering, T. Hain, and L. Dunn, ”Non-Random Generator of IPv6 Tables,” IEEE Proc. High Performance Interconnects 2004, 25-27 Aug. 2004, pp.35 – 40.

[16]　“Section 3: The SRAM Market,” Available: http://www.iitd.ac.in/vdtt/resources/memory04/SRAM_SEC03.pdf

[17]　M. Waldvogel, G. Varghese, J. Turner, and B, Plattner, “Scalable High Speed IP Routing Lookups,” in Proc. ACM SIGCOMM 1997, Sept 1997, pp25-36.

[18]　B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookups Using Multiway and Multicolumn Search,” IEEE/ACM Transactions on Networking, Vol.7, No.3, June 1999, pp.324-334.

[19]　W.C. Chang, “On the Routing Lookup Algorithm for IPv6,” Electronical Theses Heap of NSYSU 1999, 22 July 1999.

[20]　N. Huang, S. Zhao, J. Pan, and C. Su, “A Fast IP Routing Lookup Scheme for Gigabit Switching Routers,” in Proc. IEEE INFOCOM’99, Vol. 3, 1999, pp. 1429-1436.

[21]　P. Yilmaz, A. Belenkiy, and N. Uzun, ”A Trie-based Algorithm for IP Lookup Problem,” in IEEE Global Telecommunications Conference 2000, Vol.1 , 27 Nov.-1 Dec. 2000, pp593 – 598.

[22]　R. Balapumi, E.K. Karuppiah, and R. Abdullah, “IPv6 Anycast Address Lookup Using Trier-Based Algorithm,” IEEE Asia-Pacific Communications Conference 2003, Vol.3 , 21-24 Sept. 2003, pp.1082 – 1086.

[23]　“IPv6 Address Allocation and Assignment Global Policy,”Available: http://www.ripe.net/ipv6/global-ipv6-assign-2002-04-25.html, Apr. 2002.

[24]　P.A. Yilmaz, A. Belenkiy, N. Uzun, N. Gogate, and M. Toy, “A Trie-based Algorithm for IP Lookup Problem,” IEEE Global Telecommunications Conference 2000, Vol.1 , 27 Nov.-1 Dec. 2000 pp.593 – 598.

[25]　“IPv4 to IPv6 is Not Merely 50% More,” Available: http://www.ezchip.com.