Both proposed update algorithms are divided into three major parts. The first section is finding the right place to enter the rule. The speed of finding the packet location is one of the most important issues in updating the problem in the first part. In fact, the main goal in this section is to reduce the number of clocks needed for each search. The proposed updating plans aimed at reducing the number of searches. By each searching, the limit of the rule entered is reduced. In fact, the speed of finding the right place for locating the rule is increased. In the second part, after finding the appropriate location for the packet, the location of the spots is determined. The importance of the number of displacements is in the number of writings. Three-time clocks are required for each write at TCAM [10]. There are two goals in upgrading. The first aim is the transposition of rules related to the entered rule, and the second goal is the transposition of unconnected rules with the entered rule. In this paper, by prioritizing the second goal, we try to eliminate the transposition of inadequate rules, and the number of displacements associated with the rule entered is decreased. The third section of the presented update algorithm is related to the examining of free space in TCAM.
3 − 1. First proposed algorithm
Updating the lookup table in the routers or firewalls includes two sections of the adding and the removal of the rule. In the first proposed algorithm, there are 65 bits corresponding to each rule in two dimensions. The structure of these 65 bits is as follows: 32 bits for the first field, 32 bits for the second field and one bit for showing the validity of the TCAM line. The first field is for the source IP address and the second field for the destination IP address. IP addresses are considered as prefixes. By entering the rule in order to be added to the first proposed algorithm, a general search is performed in TCAM. The obtained output has two states. The first state is when the match has not occurred and the second state is when the matching occurs. In the absence of matching, there is no need to continue the search the rule. If the match occurs, there are three situations, depending on the state of the two fields of rule. In the first position, the entered rule is covered by the rule. In the second situation, the entered rule will cover the found rule. In the third position, the match is exact and there is a rule in the router. By search and precise matching occurrence, the removal operation is performed and some replacements occur in the router. The number of searches and the number of writings in this algorithm is of the order of O (R), where R represents the number of TCAM. Following the examination, the two sections of adding and removal are performed in the first proposed algorithm.
3-1-1. Adding the rule
Adding a rule with two prefix fields in the first algorithm starts with a general search in the TCAM, and in the case of no occurrence of the rule match in the first address of the free space, the adding action is performed. In the case of a match occurrence, the occurred matching, the type of the occurred match is examined and the appropriate reactions for locating the rule in TCAM. Some states occur in the case of match occurring. These states are as follows:
First State: The length of the first and second prefix of the rule found equates the length of the first and second prefix of the entered rule. Therefore, there is no need to add the rule entered and the exact match has occurred.
Second State: the first and second prefix of the found rule covers the corresponding first and second prefixes of the entered rule, or the first or second prefix of the found rule is equal to the corresponding first or second prefix of the entered rule and covers another prefix. So, the entered rule locates in the address of the found rule. The found address, along with the rules established after the address of the found rule, transform one address size to the lower address.
Third state: The first and second prefix of the entered rule covers the first and second prefix of the found rule, or the first or second prefix of the entered rule equals with the corresponding first or second found prefix. It covers the next prefix, or one of the prefixes is covered and the other may not be covered. Therefore, from the address found to the last address, searching is done in order to investigate the occurrence of one of the three following conditions. The first condition is the exact match. The second condition occurs if the entered rule is covered by the found rule. Therefore, the entry rule is located at the found address, and the rest of the rules one address size are moved to the lower. The third condition come out in the case of a non-compliance until achieving the last considered address for inserting the rules, i.e., no matching is found. Hence, the rule is added in the first empty address of free space.
Figure 2 shows an example of adding an input rule into the TCAM memory. The Px rule is inserted for adding to TCAM. A search is done in TCAM. Match has taken place. The Px rule is surrounded by P3; therefore, the p3 rule, along with the rules in the lower TCAM addresses, is passed to a lower address by a single unit.
3-1-2. Deleting the rule
The search for finding the right place for the entered rule for deletion is the same as adding the rule in the first algorithm. Deletion starts with a search in TCAM. Obviously, the absence of compliance and the lack of compliance with the rule that entered into it means that there is no rule in the TCAM. If the rule to be removed in the TCAM is found, all the rules found in the address after the found rule are converted to the same rule by one single address size.
Figure 3 shows an example of the exact match occurrence during deletion. All rules in the TCAM move as one address size as to the address where the match occurred, and the last rule is removed from the TCAM
3 − 2. The second proposed algorithm
In order to update TCAM by the second proposed algorithm, in addition to the 64 bits mentioned, 11 bits are needed to resolve 1089 layers, and a bit is also used to determine the TCAM line validity. Therefore, each TCAM line is composed of 76 bits. There are no relationships between both of the two rules in one layer. If a rule is located in the higher layer, for example, the second layer, it means that there is a rule in layer one and the rule in layer 2 is covered by the rule specified in the number one. In the case of a search in TCAM, if there is a relationship between the two prefixes of the entered rule with both prefixes from found rules, the matching is performed. The number of layers filled during the addition of the rule in TCAM is called the length of the chain of rule. The circle surrounding the rule is a chain in which the rules are linked together throughout a chain. The number of searches to find the appropriate layer in the TCAM is of the grade of O(log2L), and the number of displacements between the layers is from O(L). Here, L represents the number of TCAM layers. In the following, two major sections of the TCAM update, including adding and deleting the rule in the second proposed algorithm, are discussed.
3-2-1. Adding a new rule
Adding a rule with two prefix fields in the second algorithm starts with a total TCAM search, and if the match does not occur, the rule in the first address of the free space is added to layer one. If the match occurs, the matching states are considered as follows:
-
First State: If there is an exact match, there is no need to add the rule; the first and second found prefix of the rule is equal to the first and second prefix of the entered rule, respectively. And it is the implied that there is a rule in TCAM.
-
Second state: In the case of surroundings matching occurrence, the entered rule is set in the address of the found rule and the found rule is transferred to a higher layer. Surrounding matching occurrence is a matching in which both the first and the second prefix of the found rule surround both the first and second prefixes of the entered rule, or one of the first or second prefixes of the found rule equal with the first and second prefix of the entered rule, respectively, and another prefix of the found rule contain the corresponding prefix of the entered rule.
-
Third State: If the surrounded matching occurred, it means that the proper layer for the rule layer settlement is placed in the layers after the found rule layer. Therefore, the middle layer is chosen among the last layer, the rule layer and the layer after the found rule layer and the search is performed in the selected layer. Surrounding matching is an adaptation in which both the first and the second prefix of the entered rule encompass both the first and the second prefix of the found rule, respectively, or one of the first or second prefixes of the entered rule equals with the first or second prefix, respectively, and another prefix of the entered rule surrounds the corresponding prefix in the found rule. As overall search is done, given that matching occurrence happen in which one of the two prefixes of the found rule is covered by the corresponding prefix of the entered rule and the other prefix, the middle layer is selected and the search is done in the middle layer. According to the search of the middle layer in the third state, the following states can occur:
-
Accurate matching occurs. So, there is no need to add the rule and the rule exists in TCAM.
-
In the absence of matching or surrounded matching, the desired layer can be located in the upper half of the TCAM. So, the middle layer is selected between the layers before the searched layer and the lower layer and the search is performed in the selected layer.
-
In the case of a match occurrence in which one of the two prefixes of the found rule is covered by the equivalent prefix from the entered rule and the other layer covers the other prefix from the lower layer on, then due to the impossibility of predicting the location of the entered rule for examining the surrounding chain, the rule is being searched.
By selecting a suitable layer, the free space is being examined. In the absence of free space, the closest layer with free space is selected based on computations that takes the lowest number of displacements into account, and the free space of the selected layer is transferred to the supposed layer. The rule will be added to the desired layer later on.
Figure 4 shows an example of adding the rule to the TCAM. Rules P8، P1، P3، P6, make up a chain of surrounding rule. The Px rule will be entered for adding to the TCAM. Matching occurs in layer one. Due to the fact that the rule Px covers the rule P6 and the fact that the last filled layer is Layer 4, the search takes place in the middle layer, Layer 2, of TCAM. Matching has been occurred. The Px rule is surrounded by P3 .So the P3 rule is moved to the third layer and the P1 rule that covers the P3 rule is transferred to the fourth layer. Also, during the rule chain, the Ps rule is moved to the lower layer.
3-2-2. Deleting the Rule
In the second algorithm, the search for finding the right place for the entered rule for deletion is the same as adding the rule. If the rule is found, the found rule will be deleted from the TCAM. A search is performed with the content of the deleted rule in the higher layer. Considering the performed search, the following states can occur:
State 1: Failure in matching occurrence means that there is no rule in the higher level to cover the deleted rule. Accordingly, there is no need for movement.
State 2: If matching with the content of found rule occurs, a search is done in the deleted rule layer. If no matching occurs, the found rule in the upper layer will be passed to the layer that the removed rule is located. This procedure will be performed for the higher layers. If matching happens, there is no need for displacement, and only the last rule from the deleted rule will be transferred to the place of the deleted rule. This is the rule, for freeing up the space. Figure 5 shows the removal of the P3 rule from the TCAM. P1 and P8 rules which are located in the lower layer and in the same chain of rule are transferred to the upper layer.