Run-Based Trieから構成される決定木の枝刈り法

Size: px

Start display at page:

Download "Run-Based Trieから構成される決定木の枝刈り法"

えつみふじがわ
6 years ago
Views:

1 Run-Based Trie

2 Run-Based Trie Simple Search Run-Based Trie

3 Network A Network B Packet Router Packet Filtering Policy Rule Network A, K Network B Network C, D Action Permit Deny Permit Network X Default Deny Figure :

4 f f : {, } dw { P, D } dw, P, D

5 i R v i = b b 2... b dw (b i {,, }, v {P, D}) Table : Table : Filter F R R 2 R 3 R 4 R 5 R 6 Filter F F 2 R R 2 R 3 R 4 R 5 R 6

6 Packet Rule R P permit Packet to pass if Packet match R then permit Packet else Rule R D 2 deny Packet to pass if Packet match R 2 then deny else Rule R D 3 deny Packet to pass if Packet match R 3 then deny else if Rule R P n permit Packet to pass if Packet match R n then permit else deny Packet to pass deny Packet Figure : R D n

7 SubGraph Merging Tapdiya et al [] 29 [2] 23 [3] 23 Srinivassan et al [4] 998 HiCuts, HyperCuts Gupta et al [5], Singh et al [6] 2, 23 Grouper Ligatti et al [7] 2 Run-Based Trie [8] 25

8 Run-Based Trie HiCuts HyperCuts ( ) Run-Based Trie

9 (, Run-Based Trie )

10 Run-Based Trie Table : Filter F Filter F R R 7 R 2 R 8 R 3 R 9 R 4 R R 5 R R 6 R 2 R 2 4 R 3 3

11 Run-Based Trie T T 2 T 3 T 4 R 3 R 4 R R R 2 4 R 2 R2 R 2 R 8 R 6 R 9 R 2 3 R 7 R R 2 R 5 Figure : Run-Based Trie i T i R = R 3 =

12 Simple Search T T 2 T 3 T 4 R 3 R 4 R R R 2 4 R 2 R2 R 2 R 8 R 6 R 9 R 2 3 R 7 R R 2 R 5 Figure : Run-Based Trie R 6, R 4, R, R 2 R O(NdW + (dw) 2 ) N

13 T i S i S = { {R 3, R 4}, {R 2, R 3, R 4}, {R 3, R 4, R 8}, {R 5}, ϕ } S 2 = { {R }, {R, R }, {R, R 6}, {R }, {R 9, R }, ϕ } S 3 = { {R 2 3}, {R 2 4}, {R 2 4, R 7}, ϕ } S 4 = { {R 2, R 2, R 2}, ϕ }

14 Decision Tree S 2 S 3 2 S S 3 2 ϕ ϕ S 3 S 2 3 S 3 3 ϕ S 3 S 2 3 S 3 3 ϕ S 3 S 2 3 S 3 3 ϕ S 3 S 2 3 S 3 3 ϕ S 4 ϕs 4 ϕ S 4 ϕs 4 ϕ S 4 ϕs 4 ϕ S 4 ϕs 4 ϕ S 4 ϕs 4 ϕ S 4 ϕs 4 ϕ R R 3 R R 4 R R 4 R R R 3 R R 4 R R 4 R R R R 3 R R 4 R R 4 R R 6 S 4 ϕs 4 ϕ S 4 ϕs 4 ϕ R 2 R 2 R 7 R 7 R 2 Figure : Run-Based Trie O((dW) 2 ) N

15 O((dW) 2 ) O(N dw ) T, T 2,..., T k T k+

16 S = { {R 3, R 4}, {R 2, R 3, R 4}, {R 3, R 4, R 8}, {R 5}, ϕ } S 2 = { {R }, {R, R }, {R, R 6}, {R }, {R 9, R }, ϕ } S 3 = { {R 2 3}, {R 2 4}, {R 2 4, R 7}, ϕ } S 4 = { {R 2, R 2, R 2}, ϕ } S = {,,,, ϕ } S 2 = {,,,,, ϕ } S 3 = {,,, ϕ } S 4 = {, ϕ }

17 R R 6 T 2 R R 9 S 2 ϕ T 2 {R } () {R } () R S 2 ϕ Figure : T 2 S 2 = { {R }, {R, R }, {R, R 6}, {R }, {R 9, R }, ϕ }

18 / // / // Decision Tree Figure : (T ) (T 2 )

19 Decision Tree //// / // T T T 2 Figure :

20 Decision Tree ϕ () / //// // // / // ϕ// Figure :

21 Decision Tree ϕ ϕ ϕ ϕ ϕ ϕ ϕ ϕ ϕ ϕ ϕ ϕ R 2 R 4 R 4 R 3 R 8 R 4 R R R 5 R R 6 R R R 7 R 9 R ϕ ϕ Figure : :

22 Decision Tree R 2 R4 R ϕ ϕ R 3 R 8 R 4 R R 5 R ϕ R R R 6 R R 7 R 9 Figure : : 48 23

23 OS : CentOS Release 6.2 CPU : Intel Core i7-98x 3.33 GHz : 24GB : C++ : gcc version 4.4.6

24 pruned Decision Tree Decision Tree Memory (MB) Length of bit (dw) Figure :

25 7 pruned Decision Tree Decision Tree 6 5 Create time (s) Length of bit (dw) Figure :

26 6.5 pruned Decision Tree.4 Search Time (s).3.2. Number of Rule (N) Figure :

27 Run-Based Trie O(N dw ) 6

28 A. Tapdiya, and E. Fulp, Towards optimal firewall rule ordering utilizing directed acyclical graphs, Computer Communications and Networks, 29. ICCCN 29. Proceedings of 8th Internatonal Conference on, pp.-6, Aug 29. K. TANAKA, K. MIKAWA, and M. HIKIN, A heuristic algorithm for reconstructing a packet filter with dependent rules, IEICE Trans. Commun., vol.96, no., pp.55-62, Jan 23. K. Tanaka, K. Mikawa, and K. Takeyama, Optimization of packet filter with maintenance of rule dependencies, IEICE Communications Express, vol.2, no.2, pp.8-85, Feb 23. V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, Fast and scalable layer four switching, SIGCOMM Comput. Commun. Rev., vol.28, no.4, pp.9 22, Oct P. Gupta, and N. McKeown, Classifying packets with hierarchical intelligent cuttings, Micro, IEEE, vol.2, no., pp.34-4, Jan 2. S. Singh, F. Baboescu, G. Varghese, and J. Wang, Packet classification using multidimensional cutting, Proceedings of the 23 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp , New York, NY, USA, 23, ACM. J. Ligatti, J. Kuhn, and C. Gage, A packet-classification algorithm for arbitrary bitmask rules, with automatic time-space tradeoffs, Proceedings of the International Conference on Computer Communication Networks (ICCCN), pp.45 5, Aug. 2. K. MIKAWA, and K. TANAKA, Run-based trie involving the structure of arbitrary bitmask rules, IEICE Transactions on Information and Systems, vol.e98.d, no.6, pp.26-22, 25.

23

Master's Thesis / 修士論文映像配信の中断から復旧までの時間を短縮するネットワーク再構築手法の改良隅田, 貴久三重大学, 2011. 三重大学大学院地域イノベーション学研究科博士前期課程地域イノベーション学専攻 http://hdl.handle.net/10076/12400

Run-Based Trieから構成される 決定木の枝刈り法

Run-Based Trieから構成される決定木の枝刈り法