(3.238.7.202) 您好!臺灣時間:2021/03/04 21:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:賴秦宇
研究生(外文):Chin-Yu Lai
論文名稱:研究與設計多維度封包分類器的衝突偵測演算法
論文名稱(外文):Study and Design of Conflict Detection Algorithms for Multidimensional Packet Filters
指導教授:王丕中
口試委員:陳耀宗詹家泰詹益禎
口試日期:2011-06-20
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學與工程學系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:英文
論文頁數:41
中文關鍵詞:封包分類封包分類規則衝突偵測位元向量
外文關鍵詞:packet classificationpacket filtersconflict detectionbit vector
相關次數:
  • 被引用被引用:0
  • 點閱點閱:97
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
封包分類是擷取封包表頭的欄位值,對封包分類規則作比對,根據比對的結果決定該封包的處置方式。若一封包同時符合多個分類規則,而導致意義不明決策,我們稱此現象為分類規則的衝突。在封包分類的應用服務中,這些衝突可能會產生安全上的漏洞,因此,我們有必要在合理的時間內偵測出這些衝突。SBV是第一個可用於偵測多維度分類規則衝突的演算法,但是SBV在偵測衝突時,沒有區分是由分類規則間交集所產生的衝突,或是完全覆蓋所產生的衝突。完全覆蓋所產生的衝突可以藉由重新排序分類規則的權重而解決;而部分交集所產生的衝突在某些情況下,無法藉由重新排序權重而得以解決。在本篇論文中,我們先提出兩個修改SBV的演算法用以偵測部分交集的衝突,並且可以支援多變範圍屬性的欄位。接著,我們提出新的演算法偵測部分交集的衝突,此方法採用邊界觀點來處理多變範圍屬性的欄位,並且利用新的位元向量的定義來加速衝突偵測。最後,根據實驗的結果,我們提出的三種演算法可以偵測部分交集的衝突,而且新的演算法比兩種修改SBV的演算法至少快一倍。

Packet filters are rules of packet classification for classifying packets based on their header fields. A filter conflict occurs when two or more filters overlap, causing an ambiguity in packet classification. These conflicts may cause some security vulnerabilities in packet classification based services, e.g. firewalls and access control lists. It is necessary to detect conflicts within a reasonable time period. SBV is the first algorithm designed for multidimensional conflict detection, but it cannot distinguish between overlapping conflict and subset conflict. The problem of subset conflict can be solved by reordering filters, while overlapping conflict cannot. In this paper, we describe how to extract overlapping conflicts by modifying the original SBV algorithm. The modified algorithm can support the range fields in packet filters to generate correct result of overlapping conflict. To further shorten the time of conflict detection, we redefine the bit vectors and deal range fields with boundary address concept to speed up the procedure of conflict detection. Our experimental results show that the new algorithm is two times faster than the modified SBV algorithm in detecting overlapping conflict.

中文摘要 i
Abstract ii
List of Figures v
List of Tables vi
1. Introduction 1
2. Related Work 4
2.1. Trie-based Algorithm 4
2.2. Geoetric-based Algorithm 5
2.3. BV-based Algorithm 6
2.4. Conflicts Caused by More Than Two Filters 6
3. Definitions of Relationships Between Two Filters 8
4. Our Main Idea 10
4.1. SBV 10
4.2. How to Exclude Containment and Enclosure Filters 13
4.3. The Problem of Applying Excluding-Procedure to Range Fields 14
5. Modified SBV 18
5.1. SBV_ES 18
5.2. SBV_EP 20
6. Toward A New Scheme 22
6.1. New Semantic of Bit Vector (Boundary Bit Vector, BBV) 22
6.2. Detecting Procedure with BBV 24
6.3. Comparing The Perforance of Algorithms in The Range Field 28
7. Experimental Results 31
7.1. Conflict Detection Results 31
7.2. Comparing Speed Performance of Each Algorithm 32
7.3. Comparing Storage Performance of Each Algorithm 34
7.4. Scaling The Size of Databases 36
8. Conclusion 38
References 39


[1] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and scalable layer four switching,” SIGCOMM Comput. Commun. Rev., vol. 28, pp. 191–202, October 1998. [Online]. Available: http://doi.acm.org/10.1145/285243.285282
[2] V. Srinivasan, S. Suri, and G. Varghese, “Packet classification using tuple space search,” SIGCOMM Comput. Commun. Rev., vol. 29, pp. 135–146, August 1999. [Online]. Available: http://doi.acm.org/10.1145/316194.316216
[3] F. Baboescu and G. Varghese, “Scalable packet classification,” IEEE/ACM Trans. Netw., vol. 13, pp. 2–14, February 2005. [Online]. Available: http://dx.doi.org/10.1109/TNET.2004.842232
[4] T. V. Lakshman and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching,” SIGCOMM Comput. Commun. Rev., vol. 28, pp. 203–214, October 1998. [Online]. Available: http://doi.acm.org/10.1145/285243.285283
[5] P. Gupta and N. McKeown, “Packet classification on multiple fields,” SIGCOMM Comput. Commun. Rev., vol. 29, pp. 147–160, August 1999. [Online]. Available: http://doi.acm.org/10.1145/316194.316217
[6] D. E. Taylor and J. S. Turner, “Classbench: a packet classification benchmark,” IEEE/ACM Trans. Netw., vol. 15, pp. 499–511, June 2007. [Online]. Available: http://dx.doi.org/10.1109/TNET.2007.893156
[7] A. Hari, S. Suri, and G. Parulkar, “Detecting and resolving packet filter conflicts,” in INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 3, mar 2000, pp. 1203 –1212 vol.3.
[8] F. Baboescu and G. Varghese, “Fast and scalable conflict detection for packet classifiers,” in Proceedings of the 10th IEEE International Conference on Network Protocols, ser. ICNP ’02. Washington, DC, USA: IEEE Computer Society, 2002, pp. 270–279. [Online]. Available: http://portal.acm.org/citation.cfm?id=645532.656180
[9] H. Lu and S. Sahni, “Conflict detection and resolution in twodimensional prefix router tables,” Networking, IEEE/ACM Transactions on, vol. 13, no. 6, pp. 1353 – 1363, dec. 2005.
[10] Y. Yin, Y. Katayama, and N. Takahashi, “Detection of conflicts caused by a combination of filters based on spatial relationships,” Transactions of Information Processing Society of Japan, vol. 49, no. 9, pp. 3121–3135, 2008-09-15.
[11] D. Eppstein and S. Muthukrishnan, “Internet packet filter management and rectangle geometry,” in Proceedings of the twelfth annual ACMSIAM symposium on Discrete algorithms, ser. SODA ’01. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2001, pp. 827–835.
[12] C. Maindorfer, K. Mohamed, T. Ottmann, and A. Datta, “A new outputsensitive algorithm to detect and resolve conflicts in internet router tables,” in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, may 2007, pp. 2431 –2435.
[13] S. Thanasegaran, Y. Yin, Y. Tateiwa, Y. Katayama, and N. Takahashi, “A topological approach to detect conflicts in firewall policies,” in Proceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing. Washington, DC, USA: IEEE Computer Society, 2009, pp. 1–7. [Online]. Available: http://portal.acm.org/citation.cfm?id=1586640.1587533
[14] A. Wool, “A quantitative study of firewall configuration errors,” Computer, vol. 37, no. 6, pp. 62 – 67, june 2004.
[15] A. Liu and M. Gouda, “Complete redundancy removal for packet classifiers in tcams,” Parallel and Distributed Systems, IEEE Transactions on, vol. 21, no. 4, pp. 424 –437, april 2010.
[16] V. Puˇs and J. Korenek, “Fast and scalable packet classification using perfect hash functions,” in Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, ser. FPGA ’09. New York, NY, USA: ACM, 2009, pp. 229–236.
[17] X. He, J. Peddersen, and S. Parameswaran, “Lop re: Range encoding for low power packet classification,” in Local Computer Networks, 2009. LCN 2009. IEEE 34th Conference on, oct. 2009, pp. 137 –144.
[18] N. Guinde, S. Ziavras, and R. Rojas-Cessa, “Efficient packet classification on fpgas also targeting at manageable memory consumption,” in Signal Processing and Communication Systems (ICSPCS), 2010 4th International Conference on, dec. 2010, pp. 1 –10.
[19] A. G. Alagu Priya and H. Lim, “Hierarchical packet classification using a bloom filter and rule-priority tries,” Comput. Commun., vol. 33, pp. 1215–1226, June 2010.
[20] B. Vamanan, G. Voskuilen, and T. N. Vijaykumar, “Efficuts: optimizing packet classification for memory and throughput,” SIGCOMM Comput. Commun. Rev., vol. 40, pp. 207–218, August 2010.
[21] H. Lim and S. Y. Kim, “Tuple pruning using bloom filters for packet classification,” Micro, IEEE, vol. 30, no. 3, pp. 48 –59, may-june 2010.
[22] B. Zhang and T. Ng, “On constructing efficient shared decision trees for multiple packet filters,” in INFOCOM, 2010 Proceedings IEEE, march 2010, pp. 1 –9.
[23] A. Liu, C. Meiners, and Y. Zhou, “All-match based complete redundancy removal for packet classifiers in tcams,” in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, april 2008, pp. 111–115.
[24] R. McGeer and P. Yalagandula, “Minimizing rulesets for tcam implementation,” in INFOCOM 2009, IEEE, april 2009, pp. 1314 –1322.
[25] O. Rottenstreich and I. Keslassy, “Worst-case tcam rule expansion,” in INFOCOM, 2010 Proceedings IEEE, march 2010, pp. 1 –5.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔