隨著網路的快速發展，各式各樣的網路服務開始出現，每種服務運作時皆或多或少要佔用些許的網路頻寛，而要如何在有限的頻寛下能讓各種服務皆能正常運作，有效的頻寛分配與管理便成了相當重要的課題。
    要能有效達到頻寛分配，首先便要能有效地分辨各種的通訊協定，然而舊有的封包過濾器皆未能有效地辨識P2P這類型的封包，因此本研究採用一種以正則表示法來分析應用層資訊的封包過濾器，並希望透過修改正則表示法函式庫的方式來提昇應用層封包過濾器的效能。本研究裏採用RE2這套新公佈的正則表式法函式庫為實驗組，原系統內建的GNU C Regex函式庫為對照組，透過比較二者的執行效能以驗証是否在改用RE2函式庫後能有效提昇封包過濾的效能，並進而達成改善頻寛分配的效能。

With the fast development of internet, various kinds of network service appear. Every of them need to take some amount of bandwidth when it work, so how to make all kinds of service work smoothly under limit bandwidth becomes very important issue for proper bandwidth distribution and management.
    If we want to distribute the bandwidth properly , at first, we have to correctly distinguish the communication protocol. However, the current packet filters are not able to recognize the P2P packet effectly. Thus,this research adopt the packet filter using regular expression for analyzing the application layer informations, and want to promote the efficiency of application layer packet filter through modifying the regular expression library. This research take RE2, a new released regular expression library on google code, as experimental group, and the original build-in GNU C Regex library as control group. Through comparing the execution efficiency to verify if we can promote the efficiency of packet filter after adopting the RE2 library, and to achieve the goal of bandwidth distribution improvement.

圖 目 錄	VI
表 目 錄	VII
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
第二章 相關文獻探討 4
2.1 L7-filter 探討 4
2.2 Regular Expression 探討 5
2.2.1 起源 5
2.2.2 正規化語言理論 6
2.2.3 自動機理論 8
2.2.4 正則表示式語法 11
2.3 Regex函式庫 13
2.4 RE2函式庫 17
2.4.1 歷史背景 17
2.4.2 資料處理流程 18
2.4.3 RE2的特性 25
第三章 研究方法 28
3.1 環境說明 28
3.1.1 系統環境 28
3.1.2 L7-filter安裝 29
3.1.3 資料來源 31
3.1.4 選用的Pattern 32
3.2 測試的方法 34
第四章 結果分析 36
4.1 單一封包比對分析 36
4.2 連續性封包比對分析 39
第五章 結論與未來展望 42
參考文獻 44
附錄---英文論文 46

圖 目 錄
圖2-1：a(bb)+a 的DFA圖形 8
圖2-2：a(bb)+a 的NFA圖形之一 9
圖2-3：a(bb)+a 的NFA圖形之二 9
圖2-4：用Thompson`s演算法判斷 abbb 11
圖2-5：Regex函式庫簡單示意圖 14
圖2-6：Full Unicode Automata Graph 21
圖2-7：NFA轉DFA圖形 26
圖3-1：L7-Filter.conf設定內容 30
圖3-2：截取ftp連線封包 33
圖4-1：Regex比對時間及CPU耗用率 40
圖4-2：RE2比對時間及CPU耗用率 40

表 目 錄
表2-1：POSIX BRE 語法表 12
表2-2：POSIX ERE語法表 13
表2-3：POSIX character classes語法表 13
表2-4：regex_t的資料結構 15
表2-5：cflags參數說明 15
表3-1：系統環境列表 28
表3-2：各Pattern之正則表達式列表 34
表4-1：單一封包Regex完成比對時間(10000次) 37
表4-2：單一封包RE2完成比對間(執行10000次) 37
表4-3：各Pattern單一比對執行時間(10000次) 38
表4-4：Regex及RE2比對時間 39
表4-5：Regex及RE2記憶體配置情形  單位: KB 41

[1] 徐於三,“隨機變換通訊埠的網路流量之分析與影響評估”, 國立中山大學資訊工程學系研究所碩士論文, 2007
[2] 張朝江、林盈達,沒有固定port 應用程式的偵測與過濾: L7-filter Classifier”,http://speed.cis.nctu.edu.tw/~ydlin
/miscpub/hands-on_L7-filter_classifier.pdf, Feb 2010
[3] 鳥哥的Linux私房菜, http://linux.vbird.org/,  Feb 2010
[4] 蔡東邦,“淺談Qos和L7-filter”, https://www.dbtsai.org/uploads/cv/2006_QoS_and_L7-Filter.pdf, March 2010
[5] 怎樣寫L7-filter的模版文件, http://rhcss.blog.51cto.com/672018/133641, 2010
[6] Ying-Dar Lin,Po-Ching Lin,Meng-Fu Tsai,Tsao-Jiang Chang,and Yuan-Cheng Lai,“kP2PADM An In-Kernel Architecture of P2P Management Gateway”,IEICE Transactions on Information and Systems, Vol.e91-d(No.10) , 2008
[7] Ken Thompson,”Regular expression search algorithm”,Communications of the ACM 11(6) (June 1968), pp. 419–422. http://doi.acm.org/10.1145/363347.363387 (pdf)
[8] Michela Becchi and Patrick Crowley,”Extending Finite Automata To Efficiently Match Perl-compatible Regular Expression.”,Proceedings of The 2008 ACM CoNEXT Conference, 2008
[9] Application Layer Packet Classifier for Linux, http://l7-filter.sourceforge.net/
[10] RE2–Project Hosting on Google Code, http://code.google.com/p/re2/, Apr 2010
[11] Regex, http://www.kernel.org/doc/man-pages/online/pages/man3/
regcomp.3.html, May 2010
[12] Russ Cox,“Regular Expression Matching Can Be Simple And Fast”, http://swtch.com/~rsc/regexp/regexp1.html, Mar 2010
[13] Russ Cox,”Regular Expression Matching In The Wild”, http://swtch.com/~rsc/regexp/regexp3.html, May 2010
[14] Regular Expression, http://en.wikipedia.org/wiki/Regular_expression#Lazy_quantification, May 2010
[15] Backtracking, http://en.wikipedia.org/wiki/Backtracking, May 2010
[16] Formal Language, http://en.wikipedia.org/wiki/Formal_language, May 2010
[17] Automata Theory, http://en.wikipedia.org/wiki/Automata_theory#Automata_theory, May 2010