Pipelined network processing with FIFO queues
View Patent ↗A system and method for operating on data within a network device is described. Between two data operations in a network device is a FIFO queue, which is used to separate the clock domains of the data operations. Data from the first operation is stored in the FIFO queue, which signals an indication to the second operation that there is data in the queue. When the second operation is signaled that there is data in the FIFO queue, it immediately begins reading data from the queue, and begins performing its prescribed operations on the data once it has read enough data from the queue for it to begin operating.
1. A network device, comprising:
an input port adapted to be coupled to a computer network and structured to receive packets of data;
a first FIFO queue coupled to the input port and structured to store the received packets of data;
a first ingress process coupled to the first FIFO queue, the first ingress process configured to monitor an empty flag on the first FIFO queue and initiate reading data from the first FIFO queue when the empty flag signals there is data in the first FIFO queue;
a second FIFO queue coupled to the first ingress process and structured to store data from the first ingress process;
a second ingress process coupled to the second FIFO queue, the second ingress process configured to monitor an empty flag on the second FIFO queue and initiate reading data from the second FIFO queue when the empty flag signals there is data in the second FIFO queue;
a switch fabric coupled to the second ingress process;
a third FIFO queue coupled to the switch fabric and structured to accept a stream of data from the switch fabric grouped in data packets;
a first egress process coupled to the third FIFO queue and structured to monitor an empty flag on the third FIFO queue and initiate reading data from the third FIFO queue when the empty flag of the third FIFO queue indicates that there is data in the third FIFO queue;
a fourth FIFO queue coupled to the first egress process and structured to store data output by the first egress process; and
a second egress process coupled to the fourth FIFO queue and configured to monitor an empty flag on the fourth FIFO queue and initiate reading data from the fourth FIFO queue when the empty flag of the fourth FIFO queue indicates that there is data in the fourth FIFO queue.
2. The network device of claim 1 , wherein the second ingress process is configured to read data from the second FIFO queue before an entire data packet has been stored into the second FIFO queue.
3. The network device of claim 1 , wherein the second ingress process is configured to begin processing data retrieved from the second FIFO queue before it retrieves an entire data packet from the second FIFO queue.
4. The network device of claim 1 , wherein neither the first or second ingress processes nor the first or second egress processes operate in the same clock domain.
5. The network device of claim 1 , further comprising a first communication line coupled to the first ingress process and the second ingress process and configured to transfer data other than the packets of data from one ingress process to the other separate from the second FIFO queue.
6. The network device of claim 5 , further comprising a second communication line coupled to the first egress process and the second egress process and configured to transfer data from one egress process to the other separate from the fourth FIFO queue.
7. The network device of claim 1 , wherein one or more of the FIFO queues comprise:
a write bus coupled to a write port;
a read bus coupled to a read port;
a plurality of storage locations to store data each coupled to the write port and the read port;
a write pointer configured to indicate in which of the plurality of storage locations the next data written to the write port will be stored;
a read pointer configured to indicate from which of the plurality of storage locations the next data read from the read port will be retrieved;
a full flag configured to indicate when all of the plurality of storage locations have data stored in them; and
an empty flag configured to indicate when none of the plurality of storage locations have data stored in them.
8. A method of processing data in a network device, comprising:
reading packet data for a current packet from a first queue without waiting for all packet data from the current packet to be deposited in the first queue;
beginning performing a data operation for the current packet when enough packct data has been read from the first queue by a first process to begin performing the data operation, wherein for at least some packets the data operation is begun before all packet data from the current packet is deposited in the first queue;
completing the data operation by the first process;
storing the packet data that has been operated on by the first process into a second queue;
monitoring the second queue by a second process to determine when data has been stored in the second queue; and
retrieving data from the second queue by the second process when data has been stored in the second queue.
9. The network device of claim 8 , wherein the second process is configured to read data from the second queue before an entire data packet has been deposited into the second queue.
10. The network device of claim 8 , wherein the second process is configured to begin processing data read from the second queue before an entire data packet has been read from the second queue.
11. The method of claim 8 wherein monitoring a second queue by a second process comprises monitoring an empty flag of the second queue.
12. The method of claim 8 , wherein the first process and the second process operate in different clock domains.
13. The method of claim 8 , further comprising communicating between the first process and the second process over a communication line separate from the first queue and the second queue.
14. The method of claim 8 wherein storing the data that has been operated on by the first process into a second queue comprises:
checking a full flag on the second queue; and
when the full flag indicates that the second queue is not full, storing the data into the second queue.
15. The method of claim 8 , wherein at least one of the queues comprises:
a write bus coupled to a write port;
a read bus coupled to a read port;
a plurality of storage locations to store data each coupled to the write port and the read port;
a write pointer configured to indicate in which of the plurality of storage locations the next data written to the write port will be stored;
a read pointer configured to indicate from which of the plurality of storage locations the next data read from the read port will be retrieved;
a full flag configured to indicate when all of the plurality of storage locations have data stored in them; and
an empty flag configured to indicate when none of the plurality of storage locations have data stored in them.
16. The method of claim 8 , further comprising deencapsulating data retrieved from the second queue.
17. The method of claim 8 , further comprising validating the CRC data of a data packet retrieved from the second queue.
18. The method of claim 8 , further comprising performing a checksum operation on data retrieved from the second queue.
19. The method of claim 8 , further comprising looking up key values for data retrieved from the second queue.
20. A method of processing data in a network device, comprising:
performing a data operation, by a first process, on data within a current data packet;
checking a full flag on a queue that is coupled to the first process to determine if the queue is full of data;
storing the operated-on data for the current data packet in the queue when the full flag indicates that the queue is not full;
monitoring an empty flag of the queue by a second process to determine when data has been stored in the queue;
retrieving data from the queue by the second process when data has been stored in the queue, without waiting for all operated-on packet data from the current packet to be deposited in the queue; and
beginning operating on the data from the queue when enough data has been retrieved from the queue, wherein for at least some packets the operating is begun before all packet data from the current packet is stored in the queue.
21. The method of claim 20 , wherein operating on the data from the queue comprises stripping a header from data retrieved from the queue.
22. The method of claim 20 , wherein operating on the data from the queue comprises performing a table lookup on data retrieved from the queue.
23. The method of claim 20 , wherein operating on the data from the queue comprises performing a CRC validation on data retrieved from the queue.
24. The method of claim 20 , wherein operating on the data from the queue comprises encapsulating data retrieved from the queue into an encapsulated data packet.
25. The method of claim 20 , wherein the first process and the second process operate in different clock domains.
26. The method of claim 20 , further comprising communicating between the first process and the second process over a communication line separate from the queue.
27. The method of claim 20 , wherein the queue comprises:
a write bus coupled to a write port;
a read bus coupled to a read port;
a plurality of storage locations to store data each coupled to the write port and the read port;
a write pointer configured to indicate in which of the plurality of storage locations the next data written to the write port will be stored;
a read pointer configured to indicate from which of the plurality of storage locations the next data read from the read port will be retrieved;
a full flag configured to indicate when all of the plurality of storage locations have data stored in them; and
an empty flag configured to indicate when none of the plurality of storage locations have data stored in them.