How does router perform IP Lookup?

Router confirms routing table before forwarding of any packet to any destination. If route exists in the routing database, packet forwarding will happen otherwise packet gets dropped. Let assume destination address or prefix is available in the routing table but how does router search the prefix from the routing table. Does router search in the form of binary, hex decimal, octal or decimal?

Obviously, router understands digital which means only binary (zeros and ones). Route prefixes are stored in the form of TRIE which means a binary ordered tree which is used to store an array. 

Let’s see how router stores the given prefixes in the routing table. To make it short I am assuming that prefix length is not more than 4 bits.

1. 0

2. 1

3. 001

4. 011

5. 0100

6. 010  

The above 4 bit prefixes will store in the router as depicted in the diagram. In diagram, red color circled numbers are showing the prefix serial number like prefix 5 is 0100.

                                                                        

                                                                             Figure 1                                                                          

           

Now how the router will search the destination prefix 0110 which is not present in the routing table but the search will be based on the longest prefix match. So router will search first 0, second 1 and third 1 but after third search it will not find anything. So prefix number 4 will be the longest prefix match and traffic forwarding will happen on next hop of prefix 4.

                                                                            Figure 2                                                                              

The above shown binary tree is also known as TRIE. The programming of this TRIE is done in with the help of data structure.      

People who read this post also read :