# SVDC: Synchronous Update with the Division and Combination of SRv6 Policy
## 4 Policy-Dividing Algorithm in SUDC
### Algorithm Procedure
#### 4.2.2 Dictionary Tree  
The dictionary tree is utilized to store SRv6 policies that are waiting to be abstracted from the longest common prefixes to construct policy distribution SID blocks. The dictio  
Figure 3: The core idea of policy-dividing algorithm. nary tree will merge the common prefixes of SID lists of different policies. For example, the current dictionary tree has two SID lists of different policies, 1->2->3->6 and 1->2->3->7, and their common prefix 1->2->3 are merged. The left part of Figure 4 shows how the dictionary tree stores and merges SID lists with the same prefixes. The current policy with SID list 1->2->3 successfully matches with two policies in the dictionary tree. The common prefix will be deleted from the dictionary tree and abstracted into the policy distribution SID block. The whole process is shown in the Figure 4.  
Suppose a single prefix matching is performed on a policy set of size N and average policy length M. When not using the dictionary tree, the current matching policy needs to be compared with n policies one by one, with the time complexity of O(N*M). The dictionary tree can merge the same prefixes of different SID lists, so the time complexity of a single prefix matching is O(M) when using the dictionary tree. The dictionary tree drastically reduces the time for each prefix matching. In addition, the dictionary tree can also effectively save storage space. With the above two data structures, the time complexity of prefix matching is approximately O(width*height), where width represents the average number of child nodes for each branching node, and height signifies the height of the tree. This time complexity will be much lower than the time complexity of the naive prefix-matching algorithm. We define a series of functions in the algorithm to operate on the dictionary tree. STARTWITHPREFIX(Argus) function is to check whether the dictionary tree contains branches prefixed with the SID list of the incoming policy and return TRUE or FALSE. INSERT(Argus) function is to insert the incoming policy into the dictionary tree. The DELETEWITHPREFIX(Argus) function deletes all the branches in the dictionary tree prefixed with the SID list of the incoming policy and returns the suffix policies of these branches. GETALLLIST() function is to obtain all the policies stored in the dictionary tree. Algorithm 1 depicts the detailed procedure of SRv6 policy dividing. Collection S holds all the SRv6 policies to be distributed. Policies are divided to form multiple policy distribution SID blocks. These policy distribution SID blocks are stored in collection R. Priority queue P is used to control the order in which SRv6 policies perform prefix matching. The longer the SID list length of the policy, the higher the priority. The dictionary tree T is utilized to store the set of SRv6 policies waiting to be matched. All the policies in the policy set S are added to the priority queue P (line4 -line6). Process each policy dequeued in descending order of priority in turn until all policies have been processed (line7-line21). The current policy dequeued from P is p (line8). If no branch prefixed with the SID list of p exists in the current dictionary tree T, then policy p is inserted into T (line9-line10). Otherwise, it indicates that there exists one or more policies whose SID lists are prefixed by the SID list of p. Then the SID lists of these matched policies can be divided, and the longest common prefix that is also the SID list of p can be abstracted into  
Figure 4: The role of the dictionary tree. a policy distribution SID block r (line12). The target nodes of r should contain the target node of strategy p and the target nodes of all the matched policies (line13, line18). The SID list of r is the SID list of Policy p (line14). All the matched policies are then removed from the dictionary tree (line15). The suffix policies of these matched policies have not yet been distributed to the corresponding policy target nodes.