ROUTE LOOKUP ENGINE

摘要

A Route Lookup Engine (RLE) for determining a next hop index is disclosed. T he RLE receives a lookup key and performs a multi-bit trie search with prefix expansion and capture of a variable stride trie. The data that the RLE returns comprises t he next hop information and status flags. The RLE uses a compact, field reusable data structure. The RLE performs both unicast and multicast IP address lookups on Virtual Privat e Networks. The RLE uses separate indexing and forwarding memories. The upper bound of t he search time for the RLE is fixed regardless of the route table size.