A router’s main function is to forward an incoming packet to its destination by using routing and forwarding techniques. Forwarding can be defined as taking the incoming packet, looking at its destination IP address, consulting the forwarding table, and directing the packet to the appropriate next-hop and output link based on the information retrieved from the forwarding table. On the other hand, routing is the process by which the forwarding table itself is built. Forwarding is a relatively simple process performed locally at the router, whereas routing depends on a variety of distributed dynamic and static routing protocols.
To consult the forwarding table, the router uses the packet’s destination IP address as a key to retrieve the forwarding information (e.g., next-hop and output interface) – this operation is called IP address lookup. Once the forwarding information is available, the router transfer the packet from the incoming interface to the appropriate outgoing interface.
The greatest challenge and major bottleneck is how to make the IP address lookup fast enough to keep up with backbone routers that support high data rate interfaces (up to 10 Gbps and more). Therefore, they must be able to perform millions of address lookup operations per second which means the address lookup algorithms must perform according to these requirements.
In this web based tutorial. First we give a brief overview about the impact of addressing on lookup operations. We then present a series of different address lookup algorithms along with their advantages and disadvantages. Finally, we compare between all of them and see how they are suited in today’s networks and we also give a brief analysis about our findings based on implementing unibit trie, Patricia trie, and fixed stride multibit.
IP Address Lookup TUTORIAL 