A unibit trie is special type of tree that is used for retrieving data. It allows a natural way to organize IP prefixes and uses the bits of prefixes to direct the branching. If the examined bit is 0 we branch left, otherwise we branch right. The unibit for the sample forwarding table is shown in Fig. 1.
An example data structure of each node in the unibit is also shown on the top right part of Fig. 1, including the next hop address (if it is a prefix node), a left pointer pointing to the left child location (with an address bit 0) and a right pointer pointing to the right child location (with an address bit 1).
Fig. 1: “Unibit Trie Example”
The node P5 at the level 3 represents a prefix formed by concatenating the labels of all the branches in the path from the root node to P5. For example, the concatenated label along the path to node P5 is 111, which is the same as prefix P2. In other words, it represents the set of all addresses that begin with the sequence 111.
Route Lookup: Each IP address lookup starts at the root node of the trie. Based on the value of each bit of the destination address of the packet, the search procedure determines whether the left or the right node is to be visited. The prefix node found along the path that contains forwarding information is maintained as Best Matching Prefix (BMP) while the trie is traversed.
The following java code can be used for finding the longest prefix match (BMP) in the unibit trie:
public String longestPrefixOf(String destinationAddress) {
numberOfNodesVisited = 0;
BMP = Search (root, destinationAddress, 0);
if (BMP == null)
return null;
return BMP.nextHop;
}
private Node Search(Node x, String destinationAddress, int b) {
if(x == null)
return BMP;
if (x.nextHop != null)
BMP = x;
if(b == destinationAddress.length())
return BMP;
if (destinationAddress.charAt(b) == '0') {
numberOfNodesVisited ++;
return Search(x.left, destinationAddress, b+1);
}
else {
numberOfNodesVisited ++;
return Search(x.right, destinationAddress, b+1);
}
}
For example, imagine a longest prefix match search for the destination address 1110100. The IP lookup starts at the root, traverses the path indicated by the destination address, and remembers the BMP node so far. The first bit of 1110100 is 1, so we go to the right and get to the node 1*, which is a prefix node, the longest prefix match so far. The 2nd–5th bits of the key are 1, 1, 0, and 1, respectively. So, we turn right, right, left, and right in sequence, and come to a leaf node P7. It is a prefix node and its associated next hop information is returned and the IP lookup terminates.
The insertion of a prefix starts by a search to locate the prefix to be added. For example, say 1100*, simply follow the pointer to where 1100 would be in the trie. If no pointer exists for that prefix, it should be added. If the node for the prefix already exists, the forwarding information is updated.
The following java code can be used for insertion operation in the unibit trie:
public void put(String prefix, String nextHop) {
root = put(root, prefix, nextHop, 0);
}
private Node put(Node x, String prefix, String nextHop, int b) {
if (x == null) {
x = new Node();
numberOfNodeCreated ++;
}
if(b == prefix.length()) {
x.nextHop = nextHop;
return x;
}
if (prefix.charAt(b) == '0')
x.left = put(x.left, prefix, nextHop, b+1);
else
x.right = put(x.right, prefix, nextHop, b+1);
return x;
}
Prefix deletion:
The deletion of a prefix starts by a search to locate the prefix to be deleted. Once the node containing the prefix is found, different operations are performed depending on the node type. If it is an internal node, then the forwarding information is only removed. If the node to be deleted is a leaf node, all the one-child nodes leading to the leaf node might have to be deleted as well.
Performance and evaluation: The main disadvantage of using the unibit trie for IP route lookup is its speed because it needs 32 random reads in the worst case for IPv4. To add a prefix to the trie, in the worst case it needs to add 32 nodes. In this case, the storing complexity is 32xNxS. In summary, the lookup complexity is O(W), so is the update complexity. The storage complexity is O(NW). Note that some of the nodes are shared along the prefix paths and, thus, the upper bound might not be tight.
Let us verify our unibit implementation java code using the sample prefixes shown in Fig. 1. The following java code is used to create a new unibit trie, insert the prefixes, and find the longest matching prefix of the destination address 1110100
UniBit rami = new UniBit();
rami.put("", "P1");
rami.put("1", "P2");
rami.put("00", "P3");
rami.put("101", "P4");
rami.put("111", "P5");
rami.put("1000", "P6");
rami.put("11101", "P7");
rami.put("111001", "P8");
rami.put("1000011", "P9");
System.out.println("Total number of nodes created is " +
rami.GetNumberOfNodesCreated());
String destinationAddress = "1110100";
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. 2 shows the console output after running the above code. Referring back to Fig. 1, we can see that there are 17 nodes in total. The longest prefix match for the destination address 1110100 is P7 and 6 nodes needs to be accessed in order to find the BMP. The unibit trie example is simple as W in the worst case is 7 because the longest prefix stored is P9 of length 7.
Fig. 2: “Unibit Trie Example Output”
Disjoint Prefixes
As we have seen earlier, prefixes can overlap with each other. The longest prefix matching rule breaks the tie by choosing the prefix that matches as many bits as possible. With disjoint prefixes (one prefix does not overlap with another) it is possible to avoid the longest prefix matching rule and still find the most specific forwarding information. A trie used to represent disjoint prefixes will have prefixes at the leaves and not at the internal nodes. To obtain a disjoint unibit trie, we simply add leaf nodes to nodes that have only one child. These new leaf nodes represent new prefixes and they inherit forwarding information from the closest ancestor marked as a prefix. Finally, internal nodes marked as prefixes are unmarked.
The disjoint-prefix unibit trie for the unibit trie in Fig. 1 is shown in Figure 3. Observe that new prefixes P6a, P6b, and P6c have been added. They inherit the next-hop information from the original prefix P6. Similarly, prefix P2a and P2b inherit the next-hop information from prefix P2. If an address lookup in the original binary trie ends up with prefix P6 being the best match, then in the disjoint-prefix unibit trie it will match P6a, P6b, or P6c. Consider an example of looking up the prefix 110∗. In the original unibit trie, the best matching prefix is P2. In the disjoint-prefix unibit trie, the search will end with P2b. Since P2b has the same next hop information as prefix P2, the result will be equivalent. Since this technique pushes all the prefixes in the internal nodes to the leaves, it is also called leaf pushing.
Fig. 2: “Disjoint Prefix (Leaf Pushed) Unibit Trie Example”
IP Address Lookup TUTORIAL 