- 學位論文
在值組空間搜尋方式下的點對點封包分類演算法
P2P Packet Classification Algorithm using Tuple Space Search
摘要
隨著網際網路的普及化與使用者可使用的頻寬日益成長，網路使用的型態也日趨多樣化。其中更以點對點（Peer to Peer）傳輸的高使用率，使有限的網路頻寬，容易造成網路資源的耗盡。也因為點對點架構並不像傳統的用戶端伺服器模式可以容易將連線紀錄保存下來，所以在網路上常常存在藉由點對點傳輸非授權軟體或檔案。這對於ISP業者、學術研究相關單位以及智慧財產擁有者來說，是一件相當困擾的事。所以對於點對點網路的偵測與防範就有其必要性。 目前對於封包分類的方式主要有線性搜尋、查找樹格搜尋、值組空間搜尋、遞迴分類等方法。本論文是利用值組空間搜尋（Tuple Space Search）中的矩陣搜尋法，再加上使用標記的功能，提出在值組空間搜尋方式下的點對點封包分類演算法，並對於此演算法進行複雜度的分析。因為點對點封包特徵在值組空間分佈是相當具有獨特性的L型分佈，所以演算法的時間複雜度其效能比起線性搜尋較佳，但是也因此其所需的規則儲存空間也較多。最後經由程式的模擬驗證此演算法除了可以正確地分類出點對點傳輸封包，也可以維持有效率的封包分類。
並列摘要
As Internet becomes more popular and the network bandwidth increases, the network usage becomes more diversified. Among them, the high rate of peer-to-peer traffic consumes considerable large amount of the limited network bandwidth. Because it is difficult to trace the connections on peer-to-peer structure, many used it to exchange unauthorized software and files over the network. This causes problems to ISP, relevant academic organizations or intelligence property owners. So it is necessary to detect peer-to-peer traffic. There are many ways to classify the packets, such as linear search, grid-of tries, tuple space search and recursive flow classification. In this thesis, we proposed to use tuple space search for P2P packet classification. Our algorithm used rectangle search with a marker function. We analysed the time complexity and space complexity of the algorithm. The layout of the peer-to-peer packet signature is in L-type in the tuple space, so the algorithm is more efficient than linear search. But our algorithm needs more space to store the rules and markers.