Methods and systems for fast packet forwarding
First Claim
1. A method for determining an output port corresponding to the next node to which a packet is to be directed in a computer network, the method comprising:
- (a) constructing a data structure based on a plurality of variable-length network address prefixes;
(b) storing the data structure in a first memory device;
(c) storing, in a second memory device, a set of output port identifiers corresponding to the network address prefixes;
(d) traversing the data structure in the first memory device based on bits in an input address to determine a location in the data structure corresponding to the longest network address prefix that matches the input address; and
(e) determining, based on the location in the data structure, an offset in the second memory device for the output port identifier corresponding to the input address.
1 Assignment
0 Petitions
Accused Products
Abstract
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.
71 Citations
20 Claims
-
1. A method for determining an output port corresponding to the next node to which a packet is to be directed in a computer network, the method comprising:
-
(a) constructing a data structure based on a plurality of variable-length network address prefixes; (b) storing the data structure in a first memory device; (c) storing, in a second memory device, a set of output port identifiers corresponding to the network address prefixes; (d) traversing the data structure in the first memory device based on bits in an input address to determine a location in the data structure corresponding to the longest network address prefix that matches the input address; and (e) determining, based on the location in the data structure, an offset in the second memory device for the output port identifier corresponding to the input address. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for determining an output port identifier corresponding to a network address of the next node to which a packet is to be routed, the method comprising:
-
(a) traversing a trie data structure based on bits in an input network address and determining a location in the data structure based on the bits in the input network address; (b) maintaining a count of a number of bits having a first value up to and including the location; (c) determining, based on the number of bits having the first value, an offset for extracting an output port identifier from a memory device; and (d) extracting the output port identifier using the offset. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A fast packet forwarding engine for performing fast lookups for output port identifiers corresponding to network addresses, the fast packet forwarding engine comprising:
-
(a) a first memory device storing a trie data structure corresponding to a plurality of variable-length network address prefixes, the trie data structure including a plurality of leaf nodes at locations corresponding to variable-length network address prefixes; (b) a second memory device storing a plurality of output port identifiers; and (c) a processor for determining the location of a leaf node in the trie data structure in the first memory device based on bits in an input address, and for determining an offset for extracting an output port identifier from the second memory device based on the location. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification