Many-field packet classification using AMQ-R-tree

2.1. Classical packet classification

Many of hardware and software solutions for the classical packet classification problem have been proposed. Hardware solutions such as Ternary Content Addressable Memory (TCAM) [27] and Bitmap Intersection [26,39] provide a good classification performance by using a parallel lookup, but using hardware resources limit the size of the forwarding tables and rule-sets. Hence, the software solutions are required to solve the scalability problem. Software solutions use extendible data structures to store the rule-sets and forwarding tables. The current classical packet classification solutions can be classified as:

Some researchers have turned their research on finding alternative ways to provide the packet classification services. The authors in [13] studied the non-linear dynamics of some specified traffic flow types and proposed a traffic classification approach. They based their analysis on non-linear statistics of the IP traffic flows that are not affected by payload encryption or dynamic port change. The non-linear analysis can be considered as an eminent alternative to linear analysis of traffic data. The authors in [11] use a cuckoo hashing for field-programmable gate arrays-based IP address filtering. Their proposed hash function is pipelined reconfigurable and supports parallel computation. They achieved a constant worst case lookup by using cuckoo hashing instead of the classical hashing in FPGAs. The classical hash functions have linear lookup and may map many IP addresses to a single table position while Cuckoo hashing guaranteed mapping each IP address to a unique hashing table position. The authors in [21] use neural network based on training function to perform packet classification. In their work, they used Artificial Neural Network (ANN) with combination of hidden layer neuron and training functions as an effective tool for packet classification. The authors in [28] study the existing decision-tree algorithms and their cutting schemes weaknesses and propose a new cutting schemes, they call their scheme BitCuts. BitCuts generates a decision-tree algorithm performs bit-level cutting and achieves 2.0×–2.2× the throughput of HyperCuts.

2.2. Many-field packet classification

Recently, the researchers focus in their works on many-field packet classification problem that classifies the incoming packets according to the rule-sets of more than 15 fields in each of their rules. We will list a group of the most recent works that try to accelerate the packet classification from different directions. A new approach to identify properties of the many-field packet classifier has been proposed in [25]. This approach has a linear space and logarithmic time complexity. It can classify packets with fields of more types including range type, but this approach uses a hardware device (TCAM). These devices are expensive and have a limited size that prevents to scale such approach to work on large rule-sets. Many software many-field packet classification algorithms had been proposed, many of these algorithms use tree structures to represent the rulesets, some of them use a probabilistic data structures to accelerate querying these trees. The authors in [20] proposed a packet classification algorithm using Bloom filter in a leaf-pushing area-based quad-tree. They hash the tree nodes in Bloom filter that stored in on-chip memories. Another Bloom search solution has been proposed in [42], using the GPU-accelerated implementation. The authors in [29] proposed a decision-tree based solution for many-field packet classification, they called their solution Binary search on levels (BSOL). They represent the rules as a hyper-rectangle in a two-dimensional address space, and then they generate a binary decision tree and associate each tree node with space. The space of each node is divided between its two children. They associate each node with a filter list. They concluded that their solution has a high classification speed. The authors of [9] employed a replication control scheme on the Binary search on levels (BSOL) algorithm to minimize the memory requirements, and the processing latency, they call the new algorithm as (BSOL-RC). The memory requirement is still high because they have to store the entire rule-set plus many additional data in their tree. A two-dimensional pipelined method for many-field packet classification has been proposed in [35], they used a two-dimensional array of Processing Elements (PEs). The array works as horizontal and vertical pipeline at the same time, and its PEs can access their memory locally and can support prefix, and exact match. Their method requires a special high-performance processing elements.

The authors in [34] proposed many-field packet classification approach using range-tree [45,47] and hash table [33] to build an efficient search algorithm. Firstly, they construct a range tree or hash table for each filed according to on the field’s type. Next they query their data structure for each field of the incoming packets independently. Later they merge the partial searching results to compute the final result. This approach also requires large preprocessing time and need high processing latency including the time required to reach in the range trees, the time required to search in the hash tables and the merging time.

In our previous work [2], we used the classical R-tree for packet classification. In this work, we introduce a generalized extension of BR-tree called AMQ-R-tree that integrates AMQ data structure with R-tree. We use this AMQ-R-tree in many-field packet classification, first, we use the Bloom filter based R-tree structure (BR-tree), and then we introduce and use two new data structures named Quotient filter based R-tree (QR-tree), and Cuckoo filter based R-tree (CR-tree). In the proposed solution, we avoid all the factors that restrict the scalability of the classifier and we shift the tree construction to the off-line phase to avoid the preprocessing time that is needed by the most of the classification methods that described in this section.

3.1. BR-tree

A BR-tree [19] is d-dimensional tree data structure. Each node in the BR-tree is R-tree node in the combination with Bloom filter array. Figure 1 depicts an example of a simple BR-tree data structure. In BR-tree of M degree, each node can contain between (m and M) d-dimensional entries, m ⩾ M 2 . In BR-tree nodes, each entry attribute is stored as a hashed item in the corresponding Bloom filter.

OPEN IN VIEWER

Fig. 1.

An example of Bloom-filter-based R-tree data structure.

BR0 is the root node and contains a big range to represent all possible attributes. In BR-tree of M degree, each internal node can contain m ( M 2 ⩽ m ⩽ M ) pointers to next level nodes, and the leaf nodes contain m ( M 2 ⩽ m ⩽ M ) pointers to the database location. When the number of entries becomes more than M for some nodes, BR-tree performs splitting on that node to generate two new nodes. Each node contains m entries as minimum allowed number of entries. Each internal node contains up to M entries in the form of ( MBR i , Bloomfilter , Pointer ) where MBR i = ( m b r 0 , m b r 1 , … , m b r M − 1 ) is a rectangle that bounds the entry range in minimum area called Minimum Bounded Rectangle (MBR), Pointer is a link to the next level node, and Bloom filter is a bit-array which stores all hashed attributes of the corresponding item. The internal nodes store a meta-data and ranges about their children, and the real data are stored only in the leaf nodes that appear in the last tree level. The leaf nodes are defined as ( MBR i , Bloomfilter , Item-pointer ) where Item-pointer represents a pointer to the database location. BR-tree guarantees the data integrity so that the range union of all entries at each level is the same as the range union as the upper level.

The approximate membership query (AMQ) data structures use a small amount of memory and have the ability to identify whether an item has a match in a large previously programmed dictionary or not. The AMQ data structures can answer the item is definitely not in the set or it may be in the set with high probability [6]. In this work, three types of AMQ filters have been used. In the next sections, we will introduce a summary of the filters that used in this work for approximate membership query purpose.

3.2.1. Bloom filter

Bloom filter (BF) [24] proposed by Burton Howard Bloom in 1970 is a probabilistic data structure, used to query about the elements membership. When querying BF about an item if it in a set, the result will be possibly in the set, with some error probability (false positive), or definitely not in the set without any false negative. The classical BF is a bit-array structure, where the items can be hashed to the BF, but cannot remove. Advanced BF versions (such as Counting BF) have the ability to remove items. The BF contains an array of m bits all set to 0, to add n new items to a BF of size m, first, feed each of these items to K different hash functions. These hash functions return K array positions, and set these positions in the BF array to 1. To query BF for an item, first feed that item to the same K hash functions, if all the K positions that returned from hash functions are already set to 1 in the BF array, then the item possibly in the set. If any of the K positions is 0 in the BF array, then the item is definitely not in the set. The size of the BF m, and the number of hash functions k are related to the required false positive rate. Also adding more items to BF increase the probability of false positive. BF false positives probability = ( 1 − e − k n / m ) k .

OPEN IN VIEWER

Fig. 2.

A simple example to add three items { X , Y , Z } to BF, and querying the BF for an item { W } .

Figure 2 depicts a simple example to add three items { X , Y , Z } to the BF, and querying the BF for an item { W } . In this example, to add ( n = 3 ) elements, we feed each of them to ( K = 3 ) hash functions, and set the resulted position to 1. The colored arrows point to the resulted positions in the BF array of size ( m = 17 ) in this example. To query for an element W, feeds it to the same hash functions, and checks the resulted K positions if any of them pointing to a location its value is 0, then the element is not in that set, otherwise, it is possibly in that set. In the example, W is not in the set { X , Y , Z } , and one of its pointers points on 0.

3.2.3. Cuckoo filter

A Cuckoo Filter (CF) [43] is another probabilistic data structure. Its idea was originated from Cuckoo hashing, which was proposed by Pagh et al. [32]. CF can perform the usual probabilistic data structures operations (insertion, and query), as well as removing, re-size, and merging. An empty CF is an array of buckets, each bucket can store K fingerprints. CF usually uses two hash functions to generate a key and two positions. If the CF fails to insert the key in the first position (the slot already contains k keys), then it will try to insert it to the second position. If the alternative position is also full, then the CF uses specific operation called reallocation operation to deal with such situations. An advanced version of CF uses only one position to insert the element’s key, and if it fails to insert the key in that position, then it generates another position using the key in order to accelerate the reallocation operation. CF has better query performance and fewer memory requirements than both BF and QF. Figure 3 depicts a Cuckoo filter with size of 8 buckets, each bucket can store k=1 item. Initially, the items b and c are already in the Cuckoo filter. Figure 3(a) depicts how to add element “a” into the filter, h 1 ( a ) = 1 , h 2 ( a ) = 6 , we will check both buckets if one of them is empty we can add f h ( a ) into that empty bucket, in this case, both h 1 ( a ) = 1 , and h 2 ( a ) = 6 buckets are empty, then we select one of them randomly (bucket(6)) and insert f h ( a ) into it. Figure 3(b) depicts how to add element “d” into the filter, h 1 ( d ) = 2 , h 2 ( d ) = 5 . In this case, one bucket is empty (bucket(5)), then we can add f h ( d ) into that empty bucket. Figure 3(c) depicts how to add element “e” into the filter, h 1 ( e ) = 2 , h 2 ( e ) = 6 . In this case, both buckets are not empty, then we add it into one of that buckets (bucket 6), kicks out the existing item (“a”), and reinserts this old item to its own alternate location (bucket 1). The process of kicking out of existing items and reinserting them in their alternate locations called reallocation process. In some cases, reallocating the old item may also require kicking out another existing item, and this procedure may repeat until a vacant bucket is found or the maximum number of reallocation is reached (e.g., 150 times in our implementation). Even with long sequence of reallocation process, Cuckoo filter still has O ( 1 ) insertion time and high space occupancy.

To lookup Cuckoo filter for a given item x, first calculate x’s fingerprint f h ( x ) and two candidate buckets h 1 ( x ) , and h 2 ( x ) , and then read these two buckets. If there is fingerprint match f h ( x ) in these two buckets then returns true. Otherwise, returns false. The Cuckoo filter has more advanced features such as: it ensures that there is no false negatives as long as bucket overflow never occurs, it has better lookup performance and it supports deleting items dynamically [17].

OPEN IN VIEWER

Fig. 3.

(a) Inserting “a” at bucket (6). (b) Inserting “d” at bucket (5). (c) Inserting item “e” at bucket (6).

To insert a new entry to an AMQ-R-tree, subsequent steps should be followed. We describe the insertion process in a simple example depicted in Fig. 5 that shows how to insert the objects of Table 1. In this table there is a set of objects, each object has one multidimensional attribute ( range ), two identities ( length , and color ). We need to insert these objects one by one in an empty R-tree of degree M = 3 (maximum number of entries at each node) and m ⩾ M 2 (minimum number of entries at each node = 2). In the first step, we generate an MBR from each entry. Since an inserted MBR should be placed in a leaf node, we first need to locate the appropriate leaf node and then insert it. To locate the appropriate leaf, the tree from the root node to the leaves is traversed. At each level, the node entry that can cover the new MBR with the minimum area is selected, and the search is moved to its child until reaching the leaves. At the corresponding leaf, if that leaf can accommodate the new MBR, then the AMQ-R-tree inserts that MBR into that leaf and updates the MBRs in the path from the root to that leaf so that all of them should cover the new MBR. For the instance, Fig. 5(a) inserts K, L, and M to the root node. In this case, the root node is a leaf at the same time. Figure 5(c) depicts the insertion of items J to O.

OPEN IN VIEWER

Fig. 5.

The full steps of generating R-tree from the objects in Table 1.

In the case of the selected leaf is already full, then splitting operation is performed on the selected leaf (Figs 5(b) and (d)). The splitting operation is performed by selecting two seeds ( s 1 , s 2 ) from the M entries that the full node contains plus the new entry (in Fig. 5(d) M = { M , N , O } and the new entry is P so that s 1 and s 2 have the maximum distance between them among all other pairs ( s 1 = M , s 2 = P ). Two new nodes (Node1, Node2) have been formed so that Node1 contains s 1 , and Node2 contains s 2 (Node1 contains M, and Node2 contains P). The remaining entries ( M − 2 ) { N , O } have been allocated to Node1, and Node2 depending on which of Node1, and Node2 can accommodate each of the remaining entries with minimum area (allocate N to Node1, O to Node2), then a new entries in the parent have been generated and the parent’s entries node have been updated to cover these two new nodes (generate F and update E ′ s range in the parent). After that, AMQ-R-tree performs splitting into the upper levels if necessary. If splitting is required on the root node, then it splits the root node into two new nodes and generates a new root with two entries to cover the newly generated nodes, and increases the tree height by one. As can be seen in Fig. 5(e), inserting I to leaf node that is already full needs to split the old leaf, and adding a new entry to its parent and updating the other entries in its parent. Since the parent (the root in this case) is also already full (contain 3 entries D , E , and F), the root node has to split too. The splitting operation is performed by selecting two seeds ( C , F ) from the M entries that the full node contains plus the new entry ( D , E , F , and the new entry C). Then forms two new nodes (Node1, Node2) so that Node1 contains C, Node2 contains F, allocates D to Node1, and E to Node2. After that, it generates a new root node with two entries (A, and B) so that A covers C , D and B covers E , F , then increases the tree height by one.

The second step to construct AMQ-R-tree is to add an AMQ filter for each node’s entry. The AMQ filter is a small data structure which stores all hashed attributes of the corresponding entry. In the AMQ-R-tree root and internal nodes, the AMQ filter stores the hashed attributes of all the nodes in the lower levels that belong to its corresponding entry. In our implementation of AMQ-R-tree, a dynamic length AMQ filter at each tree level has been used, starting from the leaves. We select the static size m of required AMQ filter in order to insert all of node entries’ item identities with false positive rate less than decided upper bound of false positive probability. Then group all leaf entries AMQ filters in one larger dynamic length AMQ filter to hash them at the next upper level AMQ filters, so that the size of AMQ filter in the next upper level can hold all AMQ filters for the entries that bounded by that node entry.

OPEN IN VIEWER

Fig. 6.

An example of how to add AMQ filters to R-tree nodes, SAMQ shows the static AMQ filter and DAMQ shows dynamic AMQ filter.

To program AMQ filter, we use a set S of hash functions, each hash function returns insertion position with P bits, the number of P bits depends on the used AMQ filter. To insert a new item to the AMQ filter, we feed it to all of these S hash functions, each of the S hash functions returns P bits, since the size of the AMQ filters is variable at each tree level. We select a d bits from these P bits to fit the size of the AMQ filters at the corresponding level. Figure 6 shows a simple example of how to add AMQ filters to R-tree nodes. After constructing the R-tree, we start from the leaves and hash all the item identities in a static length AMQ filter. We select a d bits from the P bits that generated by the S hash functions. In the next upper level, we hash all the item identities in a dynamic length AMQ filter of the parent node, and so on till the root. To hash the item identities in the dynamic length AMQ filter of the parent node, we use d + c bits so that c is a positive integer value, so that d + c ⩽ p , and d + c fits the length of the dynamic length AMQ filter of the parent.

To query AMQ-R-tree for an item, first we should create MBR from that item’s multi-dimensional attributes and feed its identities to the same S hash functions that used at AMQ filters programming, then the AMQ-R-tree will traverse from the root to the leaves. At each level, we select the appropriate node entry that its MBR covers the queried MBR with minimum area, and its filter gives a positive result to the query identities. When querying the AMQ filters, we select appropriate number from the bits returned from the S hash functions according to the AMQ filter size at that level. At the leaves level, if the queried MBR matches any leaf entry and the AMQ filter gives a positive result for all the query attributes, we report that leaf’s entry (or entries) as a matching result.

For each rule in the rule-set, we generate one MBR as the tree entry. To create MBR, first we convert the SIP & DIP from each rule into range values, and represent these ranges as MBR, then describe the similar objects with bigger MBR in the next higher level. The converting of prefixes into ranges is performed by representing the minimum allowed value for the corresponding prefix as the start of the range, and the maximum allowed value as the end of the range. Table 2 depicts a simple example of 13 rules with SIP & DIP and their corresponding MBRs after conversion. Figure 8(a) depicts the corresponding MBRs for Table 2 after representing them in the geographic coordinate system. The dotted blue rectangles (R3-R7) represent the upper-level rectangles that AMQ-R-tree define, and the dotted black rectangles (R1, and R2) represent the root rectangles that AMQ-R-tree define. Figure 8(b) shows the corresponding AMQ-R-tree for Fig. 8(a).

OPEN IN VIEWER

Fig. 8.

Minimum bounding rectangles (MBRs) creation & AMQ-R-tree construction.

In our implementation of AMQ-R-tree, three different types of AMQ filters (Bloom Filter (BF), Quotient Filter (QF), and Cuckoo Filter (CF)) have been used to generate three different types of AMQ-R-tree that we named them BR-tree, QR-tree, and CR-tree. To insert a new rule to an AMQ-R-tree, first we generate an MBR from SIP & DIP, and then traverse the tree from the root node to the leaves, and perform the insertion operation as described in Section 4. After that, the remaining fields from each rule is hashed in AMQ filter. Each of the proposed trees adopts different standards for the programming operation. The following sections describe the programming operation for each of the proposed trees.

5.3. On-line AMQ-R-tree query

To classify N incoming packets, K independent threads have been used, where each thread is responsible for classifying N K incoming packets. Each thread will perform the same on-line AMQ-R-tree query, then the intermediate results from each thread will add to the answer set.

Each thread, to classify an incoming packet (test whether it maps a rule in the rule-set), first it creates the query’s MBR from the incoming packet’s SIP & DIP, and feeds the remaining fields to the hash functions to get the keys and locations. Then the thread performs two queries simultaneously, one is MBR query, and the second is reminder fields approximate membership query. The MBR query is the same query at each of the proposed trees, where the thread will query the AMQ-R-tree by traversing it from the root to the leaves. At each level, it selects an appropriate node that its MBR covers the queried MBR with minimum area, then it moves the search to the next tree level and so on until reaching the leaves. At the leaves, it performs a matching between the queried MBR and the selected node’s MBRs and reports the corresponding rule as a primary search result, if there is any match. The thread will report these results as final results if it is a success at the remainder fields approximate membership query too. To perform the remainder fields approximate membership query, there are three cases:

If there is more than one rule in the result, then the rule with the highest priority is selected, and the results from each thread are added to the answer set.

5.4. Theoretical analysis

In this section, we use the most commonly used two metrics in literature including query time, and memory consumption.

The search speed is highly depended on AMQ filter performance and the number of memory accesses. In this evaluation, the memory access has been considered as the most time-consuming operation. We have used the dynamic size AMQ filters for each of our proposed trees (BR-tree, QR-tree, and CR-tree), then the average of memory access number to classify packets using each of the proposed data structures have been counted. In Table 5, we show performance comparison in terms of the required storage, and the number of memory accesses in both average and worst cases using variable size and type of rule-sets for our proposed trees against three many-field packet classification algorithms (A Decomposition-Based Approach for Scalable Many-Field Packet Classification on Multi-core Processors (DBAMCP) [34] , Binary Search on Levels with Replication Control (BSOL-RC) [9], and Packet Classification Using a Bloom Filter in a Leaf-Pushing Area-based Quad-Trie (BF-AQT) [20]). We have chose these algorithms because they related to our proposed algorithm so that they use tree structures in their solutions. In [20] they use a tree structure combined with a bloom filter.

As can be seen, the performance of the proposed classification algorithm for all the simulated rule-sets is distinctly better or similar to the other solutions. In BSOL-RC, each node in the tree has a filter list, these filters overlap the spaces of the corresponding nodes. The filters of each node are inserted to the child that overlaps its space. In the case of the parent space overlap both of its two children, insert the filter in both of its two children. However, inserting the parent space in both of its two children causes a memory expansion. Also, when the number of replicated filters became unacceptable due to the high decision tree, they divide the filter set into multi-subsets, and they generate a hash table for each tree level contains a leaf, this may generate a large set of hash tables and affects the classification performance. The range tree in DBAMCP has empty nodes and more tree levels than CR-tree in our approach. Also, it uses separated filters to stores the remainders fields. Hence, it required more memory accesses and storage memory. The BF-AQT builds a leaf-pushing Area base Quad Tree by assigning codewords for SIP & DIP fields. They give every SIP & DIP that have the same length one codewords. For SIP & DIP that have varied lengths, they determine the codewords by the shorter length. For example, for a given rule with SIP&DIP = (11*, 101*), since DIP is longer, they extend the SIP to three bits, 110* and 111*, then they generate two codewords for each one combined with DIP. For SIP & DIP that varied in length with large number of bits, the BF-AQT generates a huge number of codewords and stores these codewords in a hash table. Hence, it requires more storage memory and memory accesses.

Table 5 shows that the performance of the proposed solution on the IPC rule-sets type is better than other types in terms of worst and average number of memory accesses. Since IPC type has a small number of the overlapped rules, the more overlapped rules lead to more tree overlapped MBRs, which make the internal tree nodes have the minimum allowed number of entries that affect the tree height, and increases the required number of memory access. In case of FW type, it has worst performance, since it has many overlapped rules that affect the tree height and needs more number of memory accesses to traverse the tree. The number of memory accesses that required in the ACL type is between two other rule-sets. Our proposed trees show very good performance in comparison to the other packet classification algorithms, especially CR-tree that requires storing single fingerprint for each entry, and one or two memory access only. CR-tree performs as the best data structure of our proposed data structures and almost the best one between all the other techniques.

CR-tree has high scalability and low memory storage as we describe in Section 6.4 comparing to other many-field packet classification. BSOL-RC stores the replicated filters in a new decision tree, and this will increase its memory usage and memory accesses. DBAMCP uses unbalanced range tree with many empty unused nodes to stores prefixes and ranges fields, these nodes cost more memory storage and memory accesses. BF-AQT needs to store large number of rules to represents small rulesets, and huge number of rule to represents big rulesets especially for those rulesets that contain SIP & DIP with different size.

6.2. Processing latency

The processing latency (L) is defined as average processing time to classify a single packet. We assume that all 15 field of the packet header is already available for use. To measure the processing latency, we use rule-sets of type IPC with variable size (1K, 2K, 4K, 8K, 16K, 32K, and 64K) rules. Then we compare the processing latency of our approach with the many-field packet classification in [9] (BSOL-RC), [34] (DBAMCP), [20] (BF-AQT). Each of these approaches uses rule-sets generated by the same tool (Classbench tool) that we use to generate our rule-sets. The DBAMCP uses range-tree and hashing to search the fields of the input packet header in parallel. It merges the partial results from all the fields in rules ID to produce the final match results. BSOL-RC enhances the binary search on levels BSOL [44] by employing a replication control scheme. The range tree in DBAMCP has more empty nodes and more tree level than R-tree in our approach. Also, it uses a separated filters to store the remainders fields. The overall processing latency of DBAMCP contains range tree search, filter query, and partial results merging process. Hence, as can be seen in Fig. 9, the proposed approaches latency outperform the DBAMCP approach. CR-tree outperforms the DBAMCP approach by (2×) times with respect to various rule-set sizes. The BSOL-RC constructs an unbalanced binary search tree and uses a set of hash tables to store the leaves nodes for every tree level that contains a leaf. Moreover, in BSOL-RC, the rule-set may divide into more than two sub-rule-sets because that single decision tree may not be scalable for large rule-sets. Also BSOL-RC dynamically stores replicated filters in a new decision tree to result in fewer memory requirements. Hence, as can be seen in 9, the BSOL-RC outperforms the DBAMCP only in the small rule-sets, and increasing the rule-sets size increases BSOL-RC latency rapidly. Also, the proposed approaches outperform BSOL-RC and BF-AQT with respect to various rule-set sizes.

OPEN IN VIEWER

Fig. 9.

Processing latency comparison with respect of various rule-set sizes.

To evaluate the throughput for our proposed approaches, we define classification throughput as the number of the incoming packets that our system can classify in a second measured as Mega packet per second (MPPS). We have generated variable size of rule-sets, for each type (100, 1k, 5k, and 10k) rules. Then we perform the tree query for N incoming packets using a variable number of threads, at each time. We have used a varied number of tracing data as incoming packets. We have generated the tracing data by the same tool that we use to generate the simulated rule-sets. The results show that the best number of the threads should be used in our machine is 32. For example Fig. 10(a), (b), and (c) show the throughput of our proposed BR-tree, QR-tree, and CR-tree, respectively. All of these trees were built for IPC rule-sets using a different number of threads to classify a different number of the incoming packets. The best number of threads to be used for classification is highly depends on the used machine specifications, and it is variable from machine to other.

OPEN IN VIEWER

Fig. 10.

The average throughput for BR-tree, QR-tree, and CR-tree using a different number of threads.

As can be seen in Fig. 10(a) that BR-tree can classify the incoming packets in up to 1 MPPS when working on rule-set of type IPC with size 100 rules, and up to 0.830 MPPS when working on the rule-set of type IPC with size 10K rules. For QR-tree and CR-tree, we get the same results about the number of threads. Figure 10(b) shows the average throughput for QR-tree using a different number of threads to query IPC rule-set. Figure 10(c) shows the average throughput for CR-tree using a different number of threads to query IPC rule-set. From this results, we conclude that the best number of threads to classify packets in our proposed trees in our machine was 32 threads. In the rest of this paper, we will use 32 threads to measure all of the proposed data structures performance. Figure 11 shows our proposed trees throughput for different types of rule-sets using 32 threads.

OPEN IN VIEWER

Fig. 11.

The proposed data structures throughput for different types of rule-sets using 32 threads for querying.

As can be seen from Fig. 11, the throughput of our three trees have same patterns, and this is because the throughput highly depends on the R-tree height multiplied by the number of memory access required to query each node’s AMQ filters. The main R-tree was built independently from the AMQ filters, that means the R-tree height is not affected of what type of AMQ filter used in it, and the number of nodes that required to be visited is fixed. The only difference of the performance of our three trees is how many memory access required to matching the incoming packets in each tree level at query operation. The CR-tree presents the best classification performance among our other proposed trees because it requires the minimum number of memory accesses. BR-tree requires more memory accesses because it uses more hash functions. QR-tree uses two hash functions, but it needs more processing overhead to check up additional bits to mention the exact location of stored items. On its best case, CR-tree can classify up to 1.42 MPPS on rule-sets of size 100 rules and up to 1.2 MPPS on rule-sets of size 10K rules. In comparing to BR-tree and QR-tree, the best throughput that BR-tree can perform was 0.98 MPPS and the best throughput that QR-tree can perform was 1.21 MPPS.

To evaluate the scalability of the proposed data structures from the respects of storage requirements and the average number of memory accesses. We have generated 15 large rule-sets with different size (from 20K rules to 100K rules) and characteristics. Since this experiment uses rule-sets with different size, we use Bytes per rule (BpR) to provide a better evaluation of proposed data structures scalability [44]. BpR is equal to the total required storage to represent the entire rule-set in the proposed data structures divided by the number of rules.

OPEN IN VIEWER

Fig. 12.

Storage evaluation using Bytes per rule, and throughput evaluation of the proposed data structures.

Figure 12(a) shows the required Bytes per rule (BpR) for the proposed data structures. As can be seen, the proposed data structures require 40 to 96 Bytes to store each rule for rule-sets of size 20K to 100K. As a result, the proposed data structures do not incur any exponentially increased storage. Moreover, the average required storage of the proposed data structures is only 70 Bytes for rule-sets with size of up to 100K rules. The proposed data structures are rectangular trees integrated with AMQ data structures, and these data structures are balanced and semi-full trees. The main factor to increase the BpR in such trees is the tree height. Increasing the tree height by one required to represent each rule in one more AMQ data structure in the new level. For large rule-sets, it requires adding a large number of rules till the tree became full or semi-full to increase the tree height one more time. Also, the bigger AMQ filters in the internal levels can hash relatively larger number of rules. Therefore, the proposed data structures could maintain the required storage without being affected by the growing size of rule-sets. Figure 12(b) shows the average number of memory accesses for the proposed data structures with variable size rule-sets. For each rule, up to one million packets have been used as tracing data to measure the average number of memory accesses. The proposed data structures require 20 to 49 memory accesses to classify each packet with average memory access equal to 34 for rule-sets of size up to 100K rules. The average required memory accesses increases only when the tree height increases. Hence, the average required memory accesses increases moderately in very slow rate with the growing size of rule-sets.

In our experimental scalability evaluation, the results show that the proposed data structures could obtain regular storage requirement and reasonable memory accesses for 15 different rule-sets, and provide good scalability in terms of variable sizes and characteristics of rule-sets.

In our proposed system, we have used a set of space-efficient probabilistic data structures. These data structures provide false positive in a very small probability, but they do not provide false negatives. In other words, when querying such data structures, the result will be either “possibly in the set” or “definitely not in set”. The false positive rate in such data structures is not a constant value, instead of that, it has a probability depends on a set of factors, such as the number of items to be inserted, the size of the data structure, the number of hash functions, and the size of the fingerprints. Each of the AMQ data structures that used in the proposed solution has a standard equation to calculate the false positives probability. The Bloom filter, Quotient filter, and Cuckoo filter have been used with R-tree data structure. To insert n elements, if k is the number of hash functions, m is the number of bits in the filter array, f is the fingerprint bits, and b is bucket size, then: (12) BF false positive probability = ( 1 − e − k n / m ) k , (13) QF false positive probability = ( 1 − e − α / 2 − f ) ⩽ 2 − f : α = n m , (14) CF false positive probability = 1 − ( 1 − 1 2 f ) 2 b ≃ 2 b / 2 f . All these filters used in our system in a dynamic form, so that the exact number of the array bits is not static, and hence the false positive probability is very difficult to calculate in a theoretical manner. For each of our proposed data structures, we have calculated the false positives probability experimentally by classification the variable sets of the incoming packets that generated especially to match the existing rules, and then we find the ratio between the incoming packet that classified as expected and those that fail to find its corresponding rules and classified to wrong rules. Table 6 depicts the false positive probability for all our proposed solutions.

The results in Table 6 show that our proposed solutions have false positive rates ( 2 × 10 − 3 , 7 × 10 − 4 , and 1 × 10 − 4 ) for BR, QR and CR trees respectively, that rate includes false positive from all levels and the R-tree itself. Note that the quality of the employed hash function and the length of the array will affect noticeably on the false positive rate. We have used simple hash functions such as (Murmurhashing2 [38], and CRC32 [31]). In general, BR-tree has the highest false positive rate, this is because Bloom filter uses a very simple hashing technique, QR-tree uses high-quality hashing technique, but still has high hard collision probability, and CR-tree is the best data structure among the other proposed data structures, which has very small false positive probability. This is because that CF uses the reallocation technique that prevents inserted elements collision.