Run-Based Trie 2 2 25 6
Run-Based Trie Simple Search Run-Based Trie
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 :
f f : {, } dw { P, D } dw, P, D
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
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
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
Run-Based Trie HiCuts HyperCuts ( ) Run-Based Trie
(, Run-Based Trie )
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
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 =
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
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}, ϕ }
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
O((dW) 2 ) O(N dw ) T, T 2,..., T k T k+
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 = {, ϕ }
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 }, ϕ }
/ // / // Decision Tree Figure : (T ) (T 2 )
Decision Tree //// / // T T T 2 Figure :
Decision Tree ϕ () / //// // // / // ϕ// Figure :
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 : : 396 48
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
OS : CentOS Release 6.2 CPU : Intel Core i7-98x 3.33 GHz : 24GB : C++ : gcc version 4.4.6
pruned Decision Tree Decision Tree Memory (MB) 2 4 6 8 Length of bit (dw) 2 4 6 Figure :
7 pruned Decision Tree Decision Tree 6 5 Create time (s) 4 3 2 2 4 6 8 2 4 6 Length of bit (dw) Figure :
6.5 pruned Decision Tree.4 Search Time (s).3.2. Number of Rule (N) Figure :
Run-Based Trie O(N dw ) 6
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. 998. 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.23 224, 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.