Abstract— Router is a device which is used to route the incoming data packets from the sender to the destination using the IP address of the destination side. Since the router performs the task in the real time so there are millions and millions of the data packets which the router has to process. The main task in the routing process is to find the corresponding port number for a particular IP address entry stored in the router. Since the router performs the searching task for the millions of incoming data packets an efficient searching algorithm is required to be performed on the routing table. In this paper we proposed an efficient searching algorithm for the routing table of the routers. Various algorithms has been performed in this field with the best time complexity of logm(n) of the balanced m way search tree and log2log2(n), we in this paper proposed an efficient searching algorithm with the time complexity of logmlogm(n) in the worst case applicable to both the IPV4 and IPV6.

Index Terms— IP address lookup, IPV6, logmlogm(n) complexity, IPV4.

Cite: Abhishant Prakash and Alok Sagar Gautam, "Fast and Scalable IP Address Lookup with Time Complexity of LogmLogm(n)," Journal of Advances in Information Technology, Vol. 5, No. 2, pp. 58-64, May, 2014.doi:10.4304/jait.5.2.58-64