Parallelisation of trie-based longest prefix matching for fast IP address lookups

摘要

IP address lookup is an important design issue for the high performance packet forwarding engine. The forwarding engine performs a longest prefix matching on the address lookup for an incoming IP packet to determine the next hop. A parallelisation scheme of longest prefix matching algorithms based on path-compressed trie is proposed. The proposed scheme reduces memory access time of IP address lookup while keeping memory spaces of parallel elements balanced.