Patent ID: 6658482
Filing Date: 2003-12-02
Classification: H04L

Abstract:
A method for speeding up an Internet Protocol (IP) address lookup with efficient use of memory, comprises:establishing a first Prefix Information Table (PIT) corresponding to the leaf nodes on the m-th level on a Trie, and a second PIT corresponding to all the leaf nodes on the n-th level on said Trie for partitioning said Trie into t segments to map all routing entries in the original routing table; looking up a Best Matching Prefix (BMP) for said IP address through said first PIT and said second PIT for finding an output port corresponding to said IP address or for finding an Lookup Table (LT) corresponding to said IP address; and checking up said LT for finding a BMP, and an exact output port is obtained, wherein the first PIT comprises an m-bit entry number identification field, a 1-bit direction identification field, a 1-bit prefix identification field, and a 14-bit pointer field; and the second PIT comprises an n-bit entry number identification field, a 1-bit direction identification field, a 1-bit prefix identification field, and a 14-bit pointer field.