High-speed message forwarding lookups for arbitrary length strings using pipelined memories
View Patent ↗The invention provides a method and system for lookup of message header information that has the advantages of low-power, speed, and flexibility. The invention uses a sequence of pipelined on-chip memories, each having only a portion of the header information intended for lookup. Each one of the on-chip memories simultaneously performs a lookup on a portion of the header information, allowing embodiments of the invention to operate on multiple messages worth of header information substantially simultaneously. The invention uses a novel data structure for recording destination addresses in the sequence of on-chip memories, having the property that moving information about destination addresses, or otherwise responding to changes in network topology is flexible, while at the same time maintaining relatively dense usage of the on-chip memories. The novel data structure allows embodiments of the invention to find the longest match destination address with no substantial additional processing over random-access memory lookup.
1. A method including
coupling each one of a sequence of inputs to a sequence of memories, said sequence of memories having a last memory and a next memory corresponding to each said memory, other than said last memory, wherein each said memory is responsive to a distinct portion of information supplied to one of said inputs, and wherein at least some inputs have their information applied to all said memories at least once, and to at least some of said memories at least twice;
coupling a result from each said memory, other than said last memory, to its corresponding said next memory in said sequence of memories; and
providing an output of at least one of said memories;
whereby said sequence of inputs is each coupled to said sequence of memories in a pipelined manner to provide said output at a rate substantially equaling one output as each input is received.
2. A method as in claim 1 , including providing results associated with a plurality of said inputs by, accessing different sub-sequences of said memories in parallel.
3. A method as in claim 1 , wherein each said input has substantially equal amounts of said information.
4. A method as in claim 1 , wherein said sequence of inputs includes at least one of: a destination IP address, an IP address, and packet header information.
5. A method as in claim 1 , wherein said sequence of memories are included in a single monolithic integrated circuit.
6. A method as in claim 1 , wherein said output is responsive to a sequence of individual memory accesses, each said individual memory access being performed at one of said memories.
7. A method as in claim 6 , wherein said sequence of individual memory accesses includes one said individual memory access at each said memory.
8. A method as in claim 6 , wherein said sequence of individual memory accesses includes one said individual memory access at each said memory, followed by a second individual memory access at each said memory for at least a subsequence of said memories.
9. A method as in claim 6 , wherein said sequence of individual memory accesses includes one said individual memory access at each said memory for only a subsequence of said memories.
10. A method as in claim 1 , wherein said sequence of memories collectively include lookup results including at least one datum responsive to each one of said inputs.
11. A method as in claim 10 , wherein said lookup results collectively include a set of packet forwarding information.
12. Apparatus including
a sequence of memories,said sequence having a last memory and a next memory corresponding to each said memory other than said last memory, each said memory being coupled to a distinct portion of one of a sequence of lookup search keys;
each said memory, other than said last memory, being coupled to its corresponding said next memory in said sequence; and
whereby each input in a sequence of inputs is coupled to said sequence of memories in a pipelined manner to provide an output at a rate substantially equaling one output as each input is received.
13. Apparatus as in claim 12 , wherein a plurality of output registers associated with different memories are each coupled to an output for said apparatus.
14. Apparatus as in claim 12 , wherein an output register associated with a memory other than said last memory is coupled to corresponding output distinct from said output for the apparatus.
15. Apparatus as in claim 12 , wherein said last memory is coupled to an associated earlier memory in said sequence.
16. Apparatus as in claim 12 , wherein said sequence of lookup search keys includes at least one of: a destination IP address, an IP address, and packet header information.
17. Apparatus as in claim 12 , wherein said sequence of memories collectively include lookup results including at least one datum responsive to each one of said lookup search keys.
18. Apparatus as in claim 17 , wherein said lookup results collectively include a set of packet forwarding information.