Efficient representation of packet classifiers has become a significant challenge due to the rapid growth of data stored and processed in the forwarding, or routing, tables. In our work we propose two algorithms for reducing the size of forwarding tables both in length and width by the deletion of redundant bits and unreachable rules based on FCA analysis. We consider the task of transferring the forwarding packet to the correct destination as the task of multinomial classification. Thus, the process of reducing the forwarding table size corresponds to feature selection procedure with slight modifications. The presented techniques are based on closed descriptions and decision trees. The main challenge in applying decision trees to the task is processing the overlapping rules. To overcome this challenge we propose to employ concept-based hypotheses to delete unreachable actions assigned to the overlapping rules. The experiments were performed on data generated by the ClassBench software. The proposed approach results in significant decrease in bits in the forwarding tables as features.
A FIB (forwarding information base) is a wide-spread network instrument used for routing and forwarding packets to the proper output network interface. Due to the rapid growth of the forwarding tables size the time of lookup and forwarding process increases significantly. Modern networking systems require the process of packet transferring to be more and more efficient and fast. In our research we introduce a novel technique for optimization of forwarding tables. Application of the proposed algorithm results in the reduction of the number of bits, which are kept in the memory and used for the lookup process. We consider the task of transferring the forwarding packet to the correct destination in accordance with the FIB as a special task of multinomial classification, where train and test data are the same, so overfitting is not an issue. Thus, the process of reducing the size of the table is considered as the task of feature selection and rule reduction. The presented approaches are based on closed descriptions defined in terms of Formal Concept Analysis (FCA).
Some of the existing techniques for FIB optimization utilize the decision tree
approach, e.g. in [
In [
The paper is organized as follows. In Section 2 we describe data and formalize the model of forwarding tables. Section 3 contains the description of the evolving approaches. Experimental results are reported in Section 4. Section 5 concludes the paper. 2
The basic scheme of packet classification using forwarding table can be presented as follows. The incoming packet goes through the table, and the first row that matches the packet description defines the respective action.
We start with the main definitions of packet forwarding. The table entry is a packet
header ( ), { }, which is a sequence of bits, each of them
can take values zero or one. This sequence goes through the ordered set of rules
( ), where each rule is represented by the ordered set of ternary
values 0, 1, and * (“don’t care”), and the corresponding action , ̅̅̅̅̅, where
is a number of all possible actions. This set of rules is often implemented in ternary
content-addressable memory (TCAM). The forwarding process looks for exact values
for all fields, assigning the packet header to the corresponding action. A header
matches a rule if for every bit from the corresponding bits from takes either the
same or * value [
The forwarding table is used with due account of the priority relation on actions. Let ( ) be a priority of action , then ( ) ( ) if . If an input packet matches more than one rule, then the rule with the action having the highest priority is applied.
The initial packet is not given in the binary form. Packet descriptions consist of several fields, the number of fields depends on the specific protocol version (e.g., IPv4 or IPv6). In general, the source and destination hosts, port numbers, or the port numbers range make the fields of classification rule. To follow the definition mentioned above each of the field values should be performed in TCAM format. For instance, the IP-address with the mask can be presented in 32-bit form, where the mask marks the significant bits. Table 1 gives an example of simplified routing table.
In this simplified table the rule is built upon one field, which is IP-address of the source port, and the action is represented by IP-address of the destination port.
First, the initial data is transformed to TCAM format, where each number is
encoded by zero, one, or * (“don’t care”) value. Table 2 gives an example of ternary
forwarding table, where only last eight bits of the IP-address are encoded. In this
example there are 7 various actions and 8 features , which generate the rules of
the forwarding table.
The algorithms we describe below are formulated in terms of Formal Concept
Analysis (FCA). To operate with TCAM data we propose a specific pattern structure [
( )} ( ) ( ) { 0 1 * 0 0 * * { )
In our case is a set of rules, scriptions of each rule in the alphabet { The scheme of intersection operation is a set containing all possible TCAM de
}, so the pattern structure (is ( ) ).
is presented in Table 3.
the result of intersection operation is the following: ( ( ) ) ( )
( ) ( ), as ( ( ) }, and ( ). 3
We consider the general task as a standard multinomial classification problem, where
the rows of the table stay for objects described by features and assigned to the
corresponding classes (actions). The application of informative feature selection results in
revealing the minimal combination of the informative features, thus decreasing the
width of the routing table. Therefore, the look-up procedure of assigning the packet to
the corresponding action can become faster. We consider two techniques based on
concept-based hypotheses. The first approach is based on a variation of Close-by-One
(CbO) algorithm [
Concept-based hypotheses [
The first approach is based on an adaptation of CbO algorithm in the depth-first
strategy [
For each context ( ( ) ) we build the CbO tree trying to define a minimal feature subset responsible for defining the -th action. Let be a set of rules, and be a common description for each rule from , where is a node index in CbO tree (e.g. for the root equals zero, for the root’s children nodes node will be one, etc.). 1. The root of the tree is a pair ( ), where and .
Its child nodes consist of just one rule and its description ( ), { } and ( ) . If ( ) includes a rule corresponding to action then the rule can be deleted from the routing table as unreachable. It is explained by the priority property, because each packet that satisfies also satisfies , hence as ( ) ( ), will never be reached. 2. Having created the children nodes of the first generation, we construct the next generations of children nodes ( ), . To accomplish this step we add one of the remaining rules to the previous rules set . To get the feature-bit vector describing this new set of rules we should intersect the feature-bit vector corresponding to the added rule ( ) with the current node description ) . This step can be formulated in accordance with the following rules. { },
; ( ) 3. If includes a rule corresponding to action , then we have got an overgeneralized description. We should return to the parent and add one of the remaining rules. We aim to create the most common description of the -th action that does not cover the description of other actions.
Example. Consider the work of the method by the example of data in Table 2. As we have only one rule for , we leave it without modification, so { } and { }.
The first action is also defined by one rule only: { } and { }, however, { } and ( ) { }, where defines . According to the second step of the algorithm, since ( ) ( ), rule can be deleted from the routing table as unreachable.
The fourth action is determined by two rules { }. The second generation of children is { }, { }. { }, which means that is the most compact description for action .
For the fifth action there are also two rules { }, { }. However, { }, where defines , in accordance with the third step of the algorithm, the obtained description is too general, and we should return to the parent nodes { } and { }. Thus, action cannot be presented by one rule, both rules and should be kept in the final routing table.
The actions , and remain the same, because they are described by one rule only. To illustrate the process described above we present the part of CbO-tree built for FIB given in Table 2 (Fig. 1). The final FIB is given in Table 4.
Fig 1. A part of CbO tree. It should be mentioned that the proposed technique does not affect the width of the routing table significantly. It can reduce the number of informative features for each action separately. Besides, it is able to decrease the length of the table by deleting unreachable actions and compressing the number of rules. In some cases the width of the table can also be reduced, for instance, if a feature-bit takes the same value for each rule in the table (i.e. the column of the table consists either of zeros, or ones), this feature-bit can be deleted from the table as uninformative. 3.3
The second approach uses concept-based hypotheses in a different way. Here we use them not for feature selection, but in the preprocessing step for deleting unreachable rules. While the final stage of feature selection is performed by a standard machine learning technique, decision tree induction in our case.
As we already mentioned some rules can be redundant in the initial table. These unreachable rules complicate the process of building the decision tree, whereas they should not be taken into account in the first way. We consider using concept-based hypotheses to detect them. Having deleted the unreachable rules we generate a decision tree. To create the optimized table we parse the decision tree finding the route for each action with zero error. A route is represented as a row from the optimized table.
As in the algorithm based on CbO we find pairs ( ), where defines the minimal description for -th action to detect the unreachable rules. If the proportion of “*” in is less than some threshold , and contains a rule corresponding to action , then we perform a checking procedure as follows. For all rules { } if ( ) ( ), then is an unreachable rule and can be deleted from the forwarding table.
Threshold is used to catch overgeneralized descriptions that can match large number of rules, we set it to ⁄ in this work. For instance, in example given in Section 3.2 the proportion of “*” in { } equals to ⁄ , which is more than a half. So, we assume that it is an overgeneralized description and there is no need to compute and check the inclusion. In this algorithm we do not aim at finding minimal hypotheses for the actions, but at deleting the unreachable rules. Thus, this stage is responsible for decreasing the length of the routing table. We should mention that is a hyperparameter aiming at avoiding long execution time, in our experiments the value ⁄ has provided good performance; however, its impact could be examined more carefully in future works.
Upon deleting all unreachable rules we propose to use decision tree algorithm to find the routes that are able to distinguish all the actions. This stage results in selection of the feature-bits that are informative for classification process, this selection decreases the width of the table. The choice of decision tree algorithm is based upon two reasons: ─ built-in procedure of feature selection, thus finding a rule for this or that action we obtain a short way of defining it. ─ overfitting does not present a problem for this specific task, because the routing table should be an exact classifier by definition, future data cannot violate it without a general rearrangement of the routing scheme due to external reasons.
We use python implementation of decision tree classifier based on CART
algorithm [
( ) This means that table.
The
Having created the decision tree for the initial data without the unreachable rules we can apply the simple false-positive check procedure to check the correctness of the classification results.
Thus, in the proposed method the length of the forwarding table is reduced by applying concept-based hypotheses, whereas, the decision tree with feature selection reduces the width of the table. We have applied this method to the sample FIB given in Table 2.
Example. Let us consider the optimization procedure of the sample FIB given in Table 2 using the proposed method. In this specific example the most pairs ( ) forming the nodes of CbO tree describe one rule only (see Fig. 1), so they are not included in the procedure of unreachable rules defining. However, there are several pairs that should be processed. The first pair is ( ) ({ } { }), where { } and corresponds to action , which has less priority than defined by . Thus, we should check for ; the proportion of “*” in equals to ⁄ , which is less than ⁄ . This means that the description is not too general, and is a candidate for unreachable rule. Then we examine the inclusion of rules’ descriptions ( ) ( ). In our case ( ) { } { } { } ( ).
is an unreachable rule and can be deleted from the forwarding second pair which describes more than one rule is ( ) ({ } { }). The set { } does not include rules corresponding to different actions (both and define action ) and, hence, there are no unreachable rules in this pair.
The third candidate is ( ) ({ } { }), where { }. Rule corresponds to , while and define . However, as has been mentioned above, the proportion of “*” in is greater than a threshold . Thus, we assume that the obtained description is too general and there are no unreachable rules in the set . In this case the assumption is correct, because action cannot be described by the one rule only, both and should be kept in the final table. Neither the description of nor the description of covers ( ), which means that is a reachable rule.
Application of the preprocessing stage resulted in deleting of one unreachable rule from the initial sample table. After this step we apply decision tree procedure to generate the paths of bits, which are able to define remaining actions, and build the optimized forwarding table using these paths. The optimized version of FIB given in Table 2 is presented in Tables 5 and 6. * * * * * * * *
A4 A5 A5 A6
A7 * 1 * * * 0 1 * 0 1 * 1 * 0 1 * 1 * * * 1 * * 0 * * Upon the deletion of unreachable rules the decision tree classifier has revealed the set of uninformative bits { }, which are not included in any classification rule. These bits take “*” value for each rule in Table 5. If we delete some bits from initial table we may have a so called false positives, when some packet satisfies the reduced table (without several bits), whereas it does not correspond to any rule in the initial FIB. To make the problem clear, let consider two reduced tables (table 4 and 6), obtained with the proposed approaches.
In accordance with the resulting table 4 the packet ( ) will be forwarded to by rule, whereas does not satisfies any of the initial actions or , which have been the basis for this new rule.
In table 6 the same problem occurs. For example, let ( ) be a forwarded packet. In accordance with the values of the 1st, 2nd, and 6th bits the reduced table will assign this packet to action 3, whereas actually this packet should not be assigned to any action and should be stopped by the table.
To prevent this type of errors a false-positive check procedure should be included
in the algorithms [
The experiments were performed using the synthesized data provided with
ClassBench software [
Two proposed methods were applied to the tables described above. We compared
the performance of the proposed methods with the results of the approach similar to
the one presented in [
Reduced number of feature-bits (column 1) shows how many bits of the 32 initial ones have been declared informative. Reduced number of rules (column 2) gives the amount of rules in the final table. This property demonstrates how many rules have been declared unreachable or have been united. The last property (column 3) says how many actions have been deleted from the table as unreachable. We can see that the best results in reduction of table width are obtained by the decision tree algorithm in combination with concept-based hypotheses. Applying conceptbased hypotheses resulted in deleting two of 57 in the first experiment, and 32 and 38 actions of 95 in the second and the third experiments respectively. This approach deleted more than a half of all initial features of the first and second synthesized FIBs. In two of three experiments the length of the table was reduced by CbO-based algorithm in the best way. It confirms the fact that the first approach succeeds in deleting redundant rules, while the other techniques are better in width reduction. It should be mentioned that we keep in the memory initial rules, which constitute the new modified rules and correspond to reachable actions, in order to perform false-positive check procedure by necessity.
The baseline approach utilizing order-independence property [
In our work we have presented two approaches to forwarding table minimization based on decision trees and concept-based hypotheses. The first technique is based on CbO-tree construction using a special pattern structure. The second approach utilizes decision tree classification algorithm in combination with concept-based (JSM) hypotheses (DT + JSM) aiming to delete the unreachable rules and reduce the length of the table.
The experiments performed on data provided by the ClassBench software showed that the best trade-off between decreasing the width and the length of the classifier is obtained by DT + JSM technique. This method resulted in significant reduction in both the rules and bits number. The former was obtained by revealing the contradicting hypotheses and, thus, unreachable rules deletion, whereas the latter was achieved by applying the decision tree algorithm to the modified table without unreachable rules. The proposed approaches were compared to the existing technique based on keeping order-independence property of the table. Whereas the number of deleted redundant features is comparable, the number of the rules kept in the final table is larger for the order-independent approach. The method based on CbO-tree construction resulted in significant reduction of routing table length, which was obtained by intersection of the rules corresponding to specific action; however, it could not reduce big number of features.
Overall, the proposed algorithms can be applied to the task of forwarding table minimization. In this work we overview the simplified version of the table that does not include range features. Thus, in our future research we are planning to apply interval pattern structures to process such type of fields and make our algorithms competitive with the state-of-the-art approaches.
The work of Sergei O. Kuznetsov shown in all the sections has been supported by the Russian Science Foundation grant no. 17-11-01276 and performed at St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, Russia.