Patent 6985483 was granted and assigned to North Carolina State University on January, 2006 by the United States Patent and Trademark Office.
Methods and systems for fast packet forwarding include traversing a trie data structure stored in on-chip memory based on bits in an input address. The bits in the input address result in a predetermined location in the data structure. The number of bits that have a first value and that are located before the determined location is calculated. The calculated number of bits corresponds to an offset in a second memory device of an address to which the packet having the input address is to be forwarded. The address can be extracted using a single access to an off-chip memory device.