IP look-up with time or memory guarantee and low update time

IP look-up is one of the more important processes that take place during the transmission of an IP packet from its source to its destination. In every intermediate node a choice must be made as to which exit port the packet must be forwarded, after consulting the routing table. We propose two algorithms with different requirements. The ARPA algorithm emphasizes on memory management and update time for the routing table by using hashing and double linked lists, while the HYDRA algorithm achieves a steady, guaranteed performance in look-up time regardless of the size of the data structure by the use of an index structure, while greatly improving the update time of the expansion-compression algorithm