臺灣博碩士論文加值系統

隨著網際網路的快速成長以及許多的網路服務品質（QoS）需要被保證，下一代網路通訊協定（IPv6）以及封包分類的技術相繼被提出。為了達到IPv6上各種網路服務的QoS，有兩個問題需要注意，第一，在多欄分類器裡的分類規則有著複雜的重疊情況，規則間可能會有互相矛盾的狀況，本論文提出一個演算法來偵測規則間的重疊情況，如此即能解決規則間的矛盾。第二，多欄分類器進行分類封包的時間會隨著規則裡的欄位長度以及欄位數目而增加，因此多欄分類器將會是網路設備的瓶頸。
TCAM是應用在封包分類器上的硬體解決方法。它能做到平行比對，只需在一個時間週期內即可完成封包分類，因此在效能上能高於軟體的封包分類器許多。不過它有著兩個缺點。第一，加入的分類規則其每一個欄位必須都是Prefix的格式，本論文提出一個方法將Range格式的分類規則轉換成數個Prefix格式的分類規則。第二，TCAM裡的分類規則隨著存放位置會有不一樣的優先權，造成更新多欄的分類器時，分類規則需要以優先權的順序來做排序，這將帶來一些效能上的瓶頸，本論文針對以上的問題提出解決方法，使得每增加一個分類規則到TCAM裡，搬移次數只會與重疊的分類規則有關並且小於重疊規則的數目。最後，本論文將上述的方法設計並實做到x86與Windows NT平台上。

With the exponential growth of the Internet and various services provided, several requirements such as the next generation Internet Protocol (Internet Protocol Version 6) and the technique of classifications are needed. However, to achieve the requirements described above, there are two issues. First, filters in multi-field classifiers have more complex overlapping situations than in single-field. The thesis proposes an algorithm to detect the overlapped filters in multi-field classifiers and judge the overlapping situations when adding a filter. Second, the processing time of classifications is according to the total length of all fields and the number of filters in classifiers. Higher layer classifications take more time to classify packet flows.
A Ternary content-addressable memory (TCAM) is a hardware solution for classifying packet flows. TCAMs perform high-speed parallel search operations to promote the performance of classifiers. But the hardware architecture of TCAMs leads to two problems. First, filters inserted to TCAMs should be in the form of prefixes. To solve the problem, this thesis designs a method to translate from a range into prefixes. Second, locations in TCAMs and priorities of filters have relations. The relations cause a lot of updates to keep entries in decreasing order of priority in a classifier and bring about low performances. This thesis proposes a flexible and optimal method to update the TCAMs based classifiers, and gives simulation results to prove the practicability.

Chapter 1 Introduction 1
Chapter 2 Related Works 4
2.1 Software Based in Single-Field Classifiers 4
2.1.1 Prefix-Length Ordering (PLO_OPT) Algorithm 5
2.1.2 Chain-Ancestor Ordering (CAO_OPT) Algorithm 6
2.2 Hardware Based in Single-Field Classifiers 7
2.3 Differences Between Single-Field and Multi-Field Classifiers 9
2.3.1 Overlapping Situations 9
2.3.2 Priority 10
2.4 Software Based in Multi-Field Classifiers 10
2.4.1 Priority Ordering Algorithm 10
2.4.2 Chain-Ancestor Ordering (CAO_OPT) Algorithm 12
2.5 Hardware Based in Multi-Field Classifiers 13
2.6 Conflict Detection 14
Chapter 3 Range-to-Prefix Algorithm 17
Chapter 4 Overlap-Detection Algorithm 21
4.1 Building Two Trie-Structures 22
4.2 Detecting Overlapped Filters 23
4.3 Overlapping Situations 25
4.4 Solving Ambiguous Ranges 26
Chapter 5 Location-Boundary Algorithm 27
5.1 The Initial State 27
5.2 Finding the Inserted Range 29
5.3 Choosing the Suitable Location 30
5.4 Special Cases 31
5.5 Removing Filters 34
Chapter 6 Simulation and Analyses 35
6.1 Simulation Model 35
6.2 Simulation Results 36
6.3 Simulation Analyses 39
Chapter 7 Designs and Implementation 41
7.1 The Architecture of the Classifier Card 41
7.2 The Designs for Table Management 42
7.2.1 Software Design 43
7.2.2 Hardware Design 46
Chapter 8 Conclusions 51
References 52

References
[1] A. Brodnik, S. Carlsson, M. Degermark, and S. Pink, “Small forwarding tables for fast routing lookups,” in Proceedings of ACM SIGCOMM’97, Cannes France, Oct. 1997, pp. 3—13.
[2] A. Hari, S. Suri and G. Parulkar, “Detecting and resolving packet filter conflicts,” IEEE INFOCOM 2000, Israel, Mar. 2000, pp. 1203 -1212.
[3] B. Lampson, V. Srinivasan, and G. Varghese, “IP lookups using multiway and multicolumn search,” in Proceedings of INFOCOM, Mar. 1998, San Francisco, California, pp. 1248—1256.
[4] D. Shah and P. Gupta, “Fast updating algorithms for TCAM,” IEEE Micro, Jan.-Feb. 2001, pp. 36 —47.
[5] IEEE Computer Society, “IEEE Standard Hardware Description Language Base on the Verilog Hardware Description Language”, IEEE Standard 1364-1995, 14 October 1996.
[6] Jun-Min Chen, The Design and Implementation of CAM-based IPv6 Packet Classifier, Master’s thesis, National Tsing Hua University, Jun. 2001.
[7] Kuo-Hui Lee, The Design and Implementation of IPv6 Switching Router, Master’s thesis, National Tsing Hua University, Jul. 2000.
[8] M. Kobayashi, T. Murase and A. Kuriyama, “A longest prefix match search engine for multi-gigabit IP processing,” IEEE ICC 2000, New Orleans, Louisiana, Mar. 2000, pp. 1360 —1364.
[9] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable high-speed ip routing lookups,” in Proceedings of ACM SIGCOMM’97, Cannes France, Oct. 1997, pp. 3—13.
[10] Nen-Fu Huang, Whai-En Chen, Jiau-Yu Luo, “A Novel Rule Table Design with Multiple TCAMs for IPv6 Packet Classification,” submit to IEEE GLOBECOM 2002, Taipei, R.O.C, 2002.
[11] P. Gupta and N. McKeown, "Packet Classification on Multiple Fields," Proc. Sigcomm, Comp. Commun. Rev., vol. 29, no. 4, Sept. 1999, pp. 147-60.
[12] P. Gupta and N. McKeown, "Packet Classification using Hierarchical Intelligent Cuttings," Proc. Hot Interconnects VII, Aug. 1999, Stanford,; also available in IEEE Micro, pp. 34-41, vol. 20, no. 1, January/February 2000.
[13] P. Gupta, S. Lin, and N. McKeown, “Routing lookups in hardware at memory access speeds,” in Proceedings of INFOCOM, San Francisco, California, Mar. 1998, pp. 1240—7.
[14] P. Tsuchiya, "A Search Algorithm for Table Entries with Non-contiguous Wildcarding," unpublished report, bellcore.
[15] Robert M. Hinden, Stephen E. Deering, “Internet Protocol, Version 6(IPv6) Specification, RFC2460, December 1998.
[16] S. Nilsson and G. Karlsson, “IP-address lookup using LC-tries,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 6, pp. 1083—92, 1999.
[17] V. Srinivasan and G. Varghese, “Fast address lookups using controlled prefix expansion,” ACM Transactions on Computer Systems, vol. 17, no. 1, Oct. 1999, pp. 1—40.
[18] V. Srinivasan et al., "Fast and Scalable Layer four Switching," Proc. ACM Sigcomm, Sept. 1998, pp. 203-14
[19] V. Srinivsdsn, S. Suri, and G. Varghese, "Packet Classification using Tuple Space Search," Proc. ACM Sigcomm, Sept. 1999, pp. 135-46.
[20] W. Richard Stevens, “TCP/IP Illustrated Volume1”, Addison-Wesley, 1994.
[21] Y. Rekhter and T. Li, “An Architecture for IP Address Allocation with CIDR,” RFC 1518, 1993.
[22] Altera Corporation, http://www.altera.com/
[23] Altera EPF10K200EBC600-1, Altera Corporation, http://www.altera.com/products/devices/flex10k/f10-index.html
[24] Altera Intellectual Property Megafunctions web page [online] Available WWW http://www.altera.com/products/ip/altera/t-alt-pci.html
[25] Microsoft NT http://www.microsoft.com/ntserver/
[26] NetLogic’s classification and forwarding processors (CFP) web page [online] Available WWW http://www.netlogicmicro.com/library/zerotable.html
[27] NetLogic’s Network Search Engine (NSE3128) web page [online] Available WWW http://www.netlogicmicro.com/datasheets/nse3128.html