Apparatus and method for collecting responses to a plurality of parallel lookup queries from a flow of packets at a network switch

Patent metadata

Field	Value
Publication number	US-10430472-B2
Application number	US-201514632709-A
Country	US
Kind code	B2
Filing date	Feb 26, 2015
Priority date	Feb 26, 2015
Publication date	Oct 1, 2019
Grant date	Oct 1, 2019

Abstract

A network lookup engine in a network switch is configured to generate multiple lookup queries for each incoming packet in parallel to a remote search engine. The number and type of the lookup queries depend on the protocols supported by the network switch. The responses from the search engine arriving at the lookup engine are not in the same order as the order of the packets. The network lookup engine is configured to collect the responses for the parallel lookup queries in two modes: 1) in-order mode in which the first packet having its lookup queries sent to the search engine has its responses collected first regardless of the order of the responses received from the search engine; 2) out-of-order mode in which the first packet having complete responses to its lookup queries from the search engine has its responses collected first regardless of the order of incoming packets.

First claim

What is claimed is:

1. A network lookup engine in a network switch, comprising:
a hardware parallel queries generator configured to:
receive a flow of a plurality of incoming packets at the network switch;
generate a plurality of lookup queries in parallel on a plurality of query lanes for each individual incoming packet, wherein each individual incoming packet is processed with a different query of the plurality of generated lookup queries; and
transmit the plurality of parallel lookup queries to a remote search engine, which processes and generates responses to the plurality of parallel lookup queries; and

a hardware parallel responses collector configured to:
receive and store the responses to the parallel lookup queries from the search engine on a plurality of response lanes for the packets in parallel;
collect valid responses to the parallel lookup queries for each of the packets; and
after collecting all of the valid responses for one of the packets, informing the hardware parallel queries generator that the collecting of the valid responses for the one of the packets is complete, wherein
the one of the packets includes an id,
the hardware parallel queries generator is further configured to reuse the id with a next incoming packet, and
the next incoming packet is different from the one of the packets.

2. The network lookup engine of claim 1 , wherein:
the network lookup engine is configured to support an in-order collection mode in which the first packet having its lookup queries generated and transmitted by the hardware parallel queries generator gets its lookup responses collected by the hardware parallel responses collector first regardless of the order of the lookup responses returned by the search engine.

3. The network lookup engine of claim 1 , wherein:
the network lookup engine is configured to support an out-of-order mode in which the first packet having completed responses to its lookup queries received from the search engine has its lookup responses collected by the hardware parallel responses collector first regardless of the order of the incoming packets.

4. The network lookup engine of claim 2 , wherein said collecting mode is configurable by software through a configurable register.

5. The network lookup engine of claim 1 , wherein said hardware parallel queries generator comprises:
a queries builder configured to generate a plurality of lookup keys for the plurality of parallel lookup queries per input packet;
a query_id generator configured to generate a unique query_id for all of the parallel lookup queries per input packet.

6. The network lookup engine of claim 5 , wherein:
said queries builder is configured to acquire a query_id from the query_id generator for each packet; wherein the queries builder is allowed to transmit the lookup queries of the packet to the search engine only if the query_id generator returns a valid query_id.

7. The network lookup engine of claim 5 , wherein said query_id generator comprises:
a modulo-N circular counter configured to generate a plurality of query_ids in an in-order mode;
an id list with N entries configured to maintain the plurality of query_ids in an out-of-order mode; and
an outstanding packet counter configured to count number of outstanding packets having lookup queries have been sent but the responses to the lookup queries from the search engine have not yet been fully collected;
a first configurable register configured to enable a user to configure the maximum number of outstanding packets;
a second configurable register configured to enable the user to select between the in-order mode and the out-of-order mode.

8. The network lookup engine of claim 7 , wherein said id list is an N-depth first-in-first-out (FIFO) list in which entries are initialized by 0 N−1 in an arbitrary order.

9. The network lookup engine of claim 7 , wherein said id list is used in the out-of-order mode, wherein a query_id is popped out each time the query_id generator receives an id request signal from the queries builder and wherein a collecting_id is pushed in each time the query_id generator receives an collecting_done signal from the hardware parallel responses collector.

10. The network lookup engine of claim 7 , wherein value of the first configurable register is not larger than N to limit the number of outstanding packets and to avoid two outstanding packets having the same query_id.

11. The network lookup engine of claim 7 , wherein a query_id is recycled for a new packet after the hardware parallel responses collector has done collecting all lookup responses for a packet previously associated to that query_id.

12. The network lookup engine of claim 7 , wherein the said query_id generator is configured to send a query_valid_vector of a packet to the hardware parallel responses collector along with the query_id of the packet, wherein said query_valid_vector is a K-bit vector representing which query lanes among the plurality of query lanes containing valid lookup queries for that packet.

13. The network lookup engine of claim 1 , wherein said hardware parallel responses collector comprises:
a plurality of response buffers configured to store the lookup responses received from the search engine on the response lanes before these responses get collected for the packets;
a query_valid_vector array configured to store a plurality of query_valid_vectors of the packets; and
a response collecting controller configured to control the responses collection for the packets.

14. The network lookup engine of claim 13 , wherein each response buffer is a traditional one-read one-write N-depth static random-access memory (SRAM) memory.

15. The network lookup engine of claim 13 , wherein the received responses are written at the entry position of the response buffers given by its response_id, and the collected responses are collected at the position pointed by the collecting_id given by the response collecting controller.

16. The network lookup engine of claim 13 , wherein said query_valid_vector array is an array of N registers having one write port and K+1 read ports.

17. The network lookup engine of claim 16 , wherein said one write port is used to write the query_valid_vector per query packet at the position given by its associated query_id.

18. The network lookup engine of claim 16 , wherein said K read ports are used to read the query_valid_vectors by the response collecting controller in the out-of-order mode, wherein said another one read port is used to read one query_valid_vector by the response collecting controller in the in-order mode.

19. The network lookup engine of claim 13 , wherein said response collecting controller further comprises:
a response ids filter configured to select unique response_ids among the response_ids returned by the search engine and build the valid vectors for these unique response_ids;
a response_valid_vector array updating block configured to update the response_valid_vectors of the unique response_ids filtered by the response ids filter; and
a N-modulo circular counter and a valid vector comparator configured to collect the responses in the in-order mode;
a plurality of valid vector comparators configured to compare a plurality of response_valid_vectors in the response_valid_vector array with the plurality of query_valid_vectors in the query_valid_vector array in the out-of-order mode; and
a matched ids counter configured to get matched_ids from the matching results returned by the valid vector comparators in the out-of-or

Assignees

• Cavium Llc

Inventors

• Tran Anh
• Balan Mohan

Classifications

• G06F16/951 Primary

  Indexing; Web crawling techniques · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• G06F16/24532

  of parallel queries · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title

• G06F16/90335 Primary

  Query processing · CPC title