由於網際網路的快速普及，各種應用服務層出不窮，如網路電視、視訊會議、即時通訊、線上遊戲及社群網站等，這些應用服務帶給使用者諸多便利，卻也使得網路管理變得相當不易，因此各式各樣的流量辨識系統因應而生。
早期在辨識網路流量，可以透過封包表頭的通訊埠號來判別，各種應用服務都會使用固定的通訊埠號，是為 Well-known Port[12]，如 HTTP (Hypertext Transfer Protocol) 即採用通訊埠號 80 來傳輸。但隨著網際網路的快速發展，許多應用服務為了躲避管理系統的辨識，開始使用隨機埠號來傳輸，因此基於通訊埠號的辨識方法其準確度已經明顯下降[2]，取而代之的是基於特徵字串的辨識方法，目前網路上有許多使用此辨識方法的開源碼軟體如 L7-Filter[5]、Snort[16] 及 Classifier[24]。
L7-Filter 和 Snort 的共通點是利用正規表示式[14]建立規則，具有強而有力的表示性及彈性，但在做特徵字串比對的時候卻是非常耗費時間的[8]，會有效能上的瓶頸；Classifier 採用多模式比對的方式來提升效能改善正規表示式的缺點。然而現今骨幹網路的頻寬愈來愈大，Classifier 在高負載的網路環境下，其改善的效能有限；因此，本研究透過分析 Classifier 中規則表的組成結構與查表方式，重新建置規則表並且提出較有效率的比對方法，排除不必要的比對，以提升封包比對的效能。

With the rapid development of the Internet, there are more and more applications and services available on it, such as Internet TV, video conference, instant message, online game, and social network, which bring lots of convenience to users. Nevertheless, it makes network management getting troublesome for network quality and bandwidth. That is the reason why the traffic classifier is necessary.
In early days, the traffic classifier can identify application service by the port number [12] in the packet header, such as 80 for HTTP (Hypertext Transfer Protocol). But now there are more and more application services communicating in random port numbers to bypass the management system. The identification precision of port-based classification has dropped apparently [2]. Much open-source software such as L7-Filter [5], Snort [16] and Classifier [24] has used signature-based classification thanks to its higher identification precision.
L7-Filter and Snort construct rules by regular expressions [14] which are of powerful expressiveness and flexibility; on the contrary, they have performance bottlenecks in signature matching [8]. Classifier improves performance by using multiple pattern matching. As the bandwidth of backbone network is getting larger, Classifier also has performance bottlenecks in heavy-loaded network environment. As a consequence, this thesis analyzes the structure and lookup algorithm of the rule table in Classifier, rebuilds the rule table and proposes a more efficient matching algorithm to obviate unnecessary matching, improving the performance of traffic classification.

[1] A. V. Aho and M. J. Corasick, “Efficient string matching: an aid to bibliographic search,” Communications of the ACM, vol. 18, no. 6, pp. 333-340, 1975
[2] Alok Madhukar, and Carey Williamson, “A Longitudinal Study of P2P Traffic Classification,” MASCOTS '06 Proceedings of the 14th IEEE International Symposium on Modeling, Analysis, and Simulation
[3] Andrew W. Moore, and Konstantina Papagiannaki, “Toward the Accurate Identification of Network Applications,” International workshop on passive and active network measurement, Boston MA, 31 March - 1 April, 2005
[4] Angelo Spognardi, Alessandro Lucarelli, and Roberto Di Pietro, “A Methodology for P2P File-Sharing Traffic Detection,” HOT-P2P '05 Proceedings of the Second International Workshop on Hot Topics in Peer-to-Peer Systems
[5] Application Layer Packet Classifier for Linux, http://l7-filter.sourceforge.net/
[6] B. Commentz-Walter. “A string matching algorithm fast on the average.” In Proceedings of ICALP, page 118-132, 1979.
[7] D. Knuth, “The Art of Computer Programming: Semi-numerical Algorithms,” volume Vol.2, third edition, Addison-Wesley, ISBN: 0-201-89684-2, 1997.
[8] Fang Yu, Zhifeng Chen, Yanlei Diao, T. V. Lakshman, and Randy H. Katz, “Fast and Memory-Efficient Regular Expression Matching for Deep Packet Inspection,” ANCS'06, December 3–5, 2006, San Jose, California, USA
[9] K. V. Rajkumar, V. Vaidehi, S. Pradeep, N. Srinivasan, and M. Vanishree, “Application Level IDS Using Protocol Analysis,” IEEE-ICSCN, Feb. 22-24, 2007
[10] Netfilter/iptables Project, http://www.netfilter.org/
[11] Netperf, http://www.netperf.org/netperf/
[12] Port Numbers, IANA, http://www.iana.org/assignments/port-numbers
[13] R. S. Boyer, and J. S. Moore, “A fast string searching algorithm, Communications of the ACM,” Vol. 20, No. 10, pp.761-772, 1977.
[14] Regular-Expression.info, http://www.regular-expressions.info/
[15] S. Wu and U. Manber. “A fast algorithm for multi-pattern searching.” Technical Report TR-94-17, Department of Computer Science, University of Arizona, 1994.
[16] Snort, http://www.snort.org/
[17] Soulseek, http://www.slsknet.org/
[18] Subhabrata Sen, and Jia Wang, “Analyzing peer-to-peer traffic across large networks,” IEEE/ACM Transactions on Networking (TON) archive Volume 12 Issue 2, April 2004
[19] Subhabrata Sen, Oliver Spatscheck, and Dongmei Wang, “Accurate, Scalable In-Network Identification of P2P Traffic Using Application Signatures,” WWW '04 Proceedings of the 13th international conference on World Wide Web
[20] TCPDUMP & LiBPCAP, http://www.tcpdump.org/
[21] Wireshark, http://www.wireshark.org/
[22] 吳寶欽(2006)，「適合在網路處理器上使用之多模式比對演算法」，國立中山大學資訊工程學系碩士論文
[23] 徐于三(2008)，「隨機變換通訊埠的網路流量之分析與影響評估」，國立中山大學資訊工程學系碩士論文
[24] 陳建華(2006)，「基於 Linux Netfilter 的通訊協定分類器之設計與實作」，國立中山大學資訊工程學系碩士論文