This technique was first adapted in the Patricia tries. The basic idea relies on the observation that each internal node of the unibit trie that does not contain a next-hop and has only one child can be removed in order to shorten the path from the root node. By removing these nodes, we need a mechanism to record which nodes are missing. A simple procedure is to store in each node additional information:
Skipped bits: A number indicating the index of the bit to be tested to decide which path to take out of that node. Thus, we jump directly to the bit where a significant decision is to be made, bypassing the bit comparisons at nodes where all the keys in the subtree have the same bit value
Prefix: we store prefixes in internal nodes and replace links to external nodes with links that point back upwards to the correct internal node in the trie.
Building Patricia Tries
There are two rules associated with building Patricia tries – the ‘existing put procedure’ and the ‘new put procedure’. The ‘new put procedure’ is used to establish a new trie, and is only usually used when there is no appropriate branch of the trie to search on. The ‘existing put procedure’ is the procedure you will use the most often to insert nodes into your trie.
The new put procedure:
Step 1) find Bit Index of the new node = position of the leftmost ‘1’ in the prefix. Example: Prefix 00110 would have a bit index of 2, since the leftmost 1 is at position 2.
Note: The keys (prefixes in our case) in a Patricia trie are bit strings, and the indices are labeled in descending order from left to right. An example is below: Index: 0 1 2 3 4 Key: 0 0 1 1 0Step 2) Insert node in trie. There will only be one position to insert it in, as we’re doing the insertion on a null link (an unconnected branch).
Step 3) Establish link. For a new node in an unestablished trie, the left child will always be null, and the right child will always be an upward link to itself.
The existing put procedure
This is the procedure you will use to do most of the insertions on a trie:
Step 1) Conduct a search for the new node on the trie. The node you end up at is known as the ‘closest node’, and you will use this to determine the bit index. It’s also a good idea to mark (for later reference) the upward link you followed to reach the ‘closest node’.
Step 2) The bit index of the new node = the leftmost bit where the new node’s key and the closest node’s key differ.
Example: New node: A = 00001 Closest node: B = 00110. The bit index of A will be 2, since the leftmost bit where A’s key and B’s key differ is at position 2, bolded above.Step 3) Insert the node in the tree. Where you insert the node is dependent on the bit index of the new node – if it is lower than that of the closest node, it goes above, otherwise it goes below.
For new bit index > closest bit index: If the bit index of the new node is higher, you can simply insert the new node in place of the upward link you followed on the unsuccessful search.
For new bit index < closest bit index: This can sometimes be a bit tricky – you need to traverse back up the trie to find an appropriate position for the new node. You determine the new position by traversing upwards from the closest node and inserting the new node in the first valid position as specified by the bit index.
Step 4) Determine links. One of the links will always lead back to the new node, and this is determined by looking at the key of the new node at the new node’s bit index. If the new node’s key is a ‘0’ at the bit index, the left link will lead back up to the new node; if it is a ‘1’ at the bit index, the right link will lead back upwards. The other link will lead either back to the closest node (if you inserted above or one level below) or alternatively if you had to go up a few levels, the other link will lead to the node above the new one’s position.
Now let us insert the following prefixes into a new Patricia trie in the order given.
| Prefix | Forwarding Information |
| 00001 | P1 |
| 10011 | P2 |
| 00101 | P3 |
| 10010 | P4 |
| 00011 | P5 |
| 01000 | P6 |
| 01001 | P7 |
| 01110 | P8 |
Table 1: “Patricia Prefix Table Example”
Insert P1 – 00001
Since there is no trie to do searching on, we use the ‘new put procedure’.
1) Find bit index. In this case it is the index of the leftmost ‘1’, which is at index 4.
2) Build links. As we remember, for a new trie node, the leftmost child is unconnected (points to null) and the right link always leads back up to itself.
Fig. 1: ” Insert P1 into Patricia Trie”
Insert P2 – 10011
We do a search for P2 on our existing tree. We start at P1, which has a skipped value of 4, and branch on bit 4 of our new key. Since bit 4 of P2 is a 1, we branch right, which leads us to P1 – thus, P1 is our closest node, and we use the ‘existing put procedure’
1) Find bit index – compare P1 and P2 and find the leftmost bit where they differ:
01234
P1 00001
P2 10011
The leftmost bit where the two keys differ is at bit 0 – thus P2 has a bit index of 0.
2) Find position: Since 0 is less than P1’s skipped value of 4, it must be inserted above
P1 in the trie. We traverse up the trie to find the first available position. In this case, it is on the level directly above P1
3) Establish links – At bit index 0, P2 has a 1. This immediately tells us that the right link will lead to P2. By a process of elimination, this also tells us that the left link will lead back to P1:
Fig. 2: ” Insert P2 into Patricia Trie”
Insert P3 – 00101
As always, we conduct a search on the trie to find P3. Now starting at P2, we branch left (P3 has a 0 at bit 0), which leads us to P1. At P1, we branch right (P3 is 1 at bit 4), leading us back up to P1. Thus, P1 is our closest node.
1) Find bit index for P3 – This is the leftmost bit where P3 and P1 differ:
01234
P3 00101
P1 00001
The leftmost bit where P1 and P3 differ is at bit 2, shown in bold. Therefore, P3’s skipped values will be 2.
2) Find position: Since 2 is less than P1’s skipped value of 4, it must be inserted above P1 in the trie. We traverse up the trie to find the first available position. In this case, it is on the level directly above P1 and below P2.
3) Establish links – At bit index 2, P3 has a 1. This immediately tells us that the right link will lead to P3. By a process of elimination, this also tells us that the left link will lead to P1:
Fig. 3: ” Insert P3 into Patricia Trie”
Insert P4 – 10010
As always, we conduct a search on the trie to find P4. Now starting at P2, we branch right (P4 has a 1 at bit 0), which leads us back up to P2. Thus, P2 is our closest node.
1) Find bit index for P4 – This is the leftmost bit where P4 and P2 differ:
01234
P4 10010
P2 10011
The leftmost bit where P4 and P2 differ is at bit 4, shown in bold. Therefore, P4’s skipped values will be 4.
2) Find position – Since P4’s index 4 is greater than P2’s 0, we can insert P4 below P2 in the trie. Thus, P4 replaces the link we followed to get to P2, which is P2’s right link.
3) Establish links – P4 has a 0 at its bit index of 4, so it gets the left-hand link. P2 has the 1 at bit index 2, so the right link will lead to P2:
Fig. 4: ” Insert P4 into Patricia Trie”
Insert P5 – 00011
As always, we conduct a search on the trie to find P5. Now starting at P2, we branch left (P5 has a 0 at bit 0), which leads us to P3. At P3, we branch left (P5 is 0 at bit 2), which leads us to P1. At P1, we branch right (P5 has 1 at bit 4), leading us back up to P1. Thus, P1 is our closest node.
1) Find bit index for P5 – This is the leftmost bit where P5 and P1 differ:
01234
P5 00011
P1 00001
The leftmost bit where P1 and P5 differ is at bit 3, shown in bold. Therefore, P5’s skipped values will be 3.
2) Find position: Since 3 is less than P1’s skipped value of 4, it must be inserted above P1 in the trie. We traverse up the trie to find the first available position. In this case, it is on the level directly above P1 and below P3.
3) Establish links – At bit index 3, P5 has a 1. This immediately tells us that the right link will lead to P5. By a process of elimination, this also tells us that the left link will lead to P1:
Fig. 5: ” Insert P5 into Patricia Trie”
Insert P6 – 01000
As always, we conduct a search on the trie to find P6. Now starting at P2, we branch left (P6 has a 0 at bit 0), which leads us to P3. At P3, we branch left (P6 is 0 at bit 2), which leads us to P5. At P5, we branch left (P6 has 0 at bit 3), which leads us to P1. At P1, we branch left (P6 is 0 at bit 4) leading us to unconnected link. Thus, P1 is our closest node.
1) Find bit index for P6 – This is the leftmost bit where P6 and P1 differ:
01234
P6 01000
P1 00001
The leftmost bit where P1 and P5 differ is at bit 1, shown in bold. Therefore, P6’s skipped values will be 1.
2) Find position: Since 1 is less than P1’s skipped value of 4, it must be inserted above P1 in the trie. We traverse up the trie to find the first available position. In this case, it is on the level between P2 and P3.
3) Establish links – At bit index 1, P6 has a 1. This immediately tells us that the right link will lead to P6. By a process of elimination, this also tells us that the left link will lead to P3:
Fig. 6: ” Insert P6 into Patricia Trie”
Insert P7 – 01001
As always, we conduct a search on the trie to find P7. Now starting at P2, we branch left (P7 has a 0 at bit 0), which leads us to P6. At P6, we branch right (P7 is 1 at bit 1), which leads us back to P6. Thus, P6 is our closest node.
1) Find bit index for P7 – This is the leftmost bit where P7 and P6 differ:
01234
P7 01001
P6 01000
The leftmost bit where P7 and P6 differ is at bit 4, shown in bold. Therefore, P7’s skipped values will be 4.
2) Find position – Since P7’s index 4 is greater than P6’s 1, we can insert P7 below P6 in the trie. Thus, P7 replaces the link we followed to get to P6, which is P6’s right link.
3) Establish links – P7 has a 1 at its bit index of 4, so it gets the right-hand link. P6 has the 0 at bit index 4, so the left link will lead to P6:
Fig. 7: ” Insert P7 into Patricia Trie”
Insert P8 – 01110
As always, we conduct a search on the trie to find P8. Now starting at P2, we branch left (P8 has a 0 at bit 0), which leads us to P6. At P6, we branch right (P8 is 1 at bit 1), which leads us to P7. At P7, we branch left (P8 has a 0 at bit 4), which leads us back to P6. Thus, P6 is our closest node.
1) Find bit index for P8 – This is the leftmost bit where P8 and P6 differ:
01234
P8 01110
P6 01000
The leftmost bit where P8 and P6 differ is at bit 2, shown in bold. Therefore, P8’s skipped values will be 2.
2) Find position – Since P8’s index 2 is greater than P6’s 1, it must be inserted below P6 in the tries. We traverse down the trie to find the first available position. In this case, it is on the level directly below P6 and above P7.
3) Establish links – At bit index 2, P8 has a 1. This immediately tells us that the right link will lead to P8. By a process of elimination, this also tells us that the left link will lead to P7:
Fig. 8: ” Insert P8 into Patricia Trie”
Route Lookup: Each IP lookup starts at the root node of the trie. Based on the value of skipped bits of the destination address of the packet, the lookup algorithm determines whether the left or the right node is to be visited. The next hop of the longer matching prefix found along the path is maintained as Best Matching Prefix (BMP) while the trie is traversed. For example imagine a search for the destination address 10011110 for the patricia trie shown in Fig. 8 above, The IP lookup starts at the (head.left node) P2, remembers it as the BMP node so far because. The first bit of 100011110 is 1, so we go to the right and get to the prefix node P4 and save it as the BMP. As the fourth bit of the key is 1, we go right again which leads us back to P2 (up). As a result, the longest prefix is 10001 and the next hop address stored at P2 is returned.
Let us verify our Patricia implementation java code using the sample prefixes shown in table 1. The following java code is used to create a new patricia trie, insert the prefixes, and find the longest matching prefix of the destination address 10011110
Patricia rami = new Patricia();
rami.put("00001", "P1");
rami.put("10011", "P2");
rami.put("00101", "P3");
rami.put("10010", "P4");
rami.put("00011", "P5");
rami.put("01000", "P6");
rami.put("01000", "P7");
rami.put("01110", "P8");
System.out.println("Total number of nodes created is " + rami.getNumberOfNodeCreated());
String destinationAddress = "10011110";
System.out.println("Longest prefix match for the destination address " + destinationAddress + " is " + rami.longestPrefixOf(destinationAddress));
System.out.println("Number of nodes visited is " + rami.getNumberOfNodesVisited());
Fig. 9 shows the console output after running the above code. Referring back to Fig. 8, we can see that there are 8 nodes in total. The longest prefix match for the destination address 10011110 is P2 and 3 nodes needs to be accessed in order to find the BMP (One access is due to backtracking). The patricia trie example is simple as W in the worst case is 6.
Fig. 9: “Patricia Trie Example Output”
Performance: compression can reduces the height of a sparse unitbit trie. However, when the unibit trie is full (every node has two children) and there is no compression possible, the two versions will look identical. Thus, a lookup operation requires 32 random reads in the worst case for IPv4, O(W). Considering a unibit trie with N leaves, there can be N-1 internal nodes between the leaves and the root including the root, as described in Fig. 9 below. The total amount of memory required will be at most 2N − 1, Since path compression is possible and some internal nodes can be removed, the space complexity becomes O(N), independent of W. Thus, path compressed tries reduce space requirements, but not the search complexity.
Fig. 9: “Example of Full Unibit Trie with N Leaves”
IP Address Lookup TUTORIAL 