System and method for processing data packets

• US 6,032,190 A
• Filed: 10/03/1997
• Issued: 02/29/2000
• Est. Priority Date: 10/03/1997
• Status: Expired due to Fees

• Current Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Original Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Inventors: Vanderwarn, Brian D., Bremer, Clark, Severns, Christine E.
• Primary Examiner(s): Matar, Ahmad F.
• Assistant Examiner(s): Tran, Philip B.
• Application Number:
  US08/943,512
• Time in Patent Office: 879 Days
• Field of Search: 395/200.64, 395/200.66, 395/200.68, 395/200.75, 709/100, 370/423, 370/310, 370/413, 370/389
• US Class Current: 709/238
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

An apparatus and method for processing a data packet to determine the routing of the data packet through a communications network is provided in which the data packet has a header portion and a data portion. The apparatus stores the header portion of the data packet, and processes the header portion of the data packet. The processing may include using a processing core for executing instructions for processing the header portion, searching through a route table to determine a route of the data packet, and searching through a table memory for information about the destination of the data packet in which the route table search, the table memory search and the processing core operate simultaneously to process the header portion and generate an internal header or a network media header. A modified header portion is generated to route the data packet through the communications network. A method for processing data packets to determine the route of the data packet is also provided in which a header portion is received from an incoming data packet, an search based on the received header portion is performed, a route look-up search is performed, and the information contained within the header portion is processed simultaneously for determining if the header portion is valid and generating an internal header or network media header based on the results of the route look-up search, the interface search, and other processing.

Claims

1. An apparatus for processing a data packet to determine the routing of the data packet through a communications network, the data packet having a header portion and a data portion, the apparatus comprising:

means for storing the header portion of the data packet;

means, connected to the header storing means, for processing the header portion of the data packet;

said processing means comprising;

a processing core for executing instructions for processing the header portion,

means, responsive to an instruction from the processing core and a first value contained within said header portion, for searching through a route table to determine a route of the data packet,

means, responsive to an instruction from the processing core and a second value contained within said header portion, for searching through a table memory for information about the destination of the data packet, wherein said table memory includes an interface table storing information related to one or more interfaces and a circuit table storing information related to one or more virtual circuits,

said processing core, said route table search means and said table memory search means operating simultaneously to process said header portion and generate one of an internal header and a network media header; and

means for generating a modified header portion containing at least some of the received header portion together with said generated one of the internal header and the network media header.

2. The apparatus of claim 1, wherein said header storing means comprises a first set of header registers and a second set of header registers so that while the processing means is processing the header contained in one of the set of header registers a new header portion may be stored in the other set of header registers.

3. The apparatus of claim 2, wherein said header storing means further comprises means for switching between said set of header registers.

4. The apparatus of claim 3, wherein said header storing means further comprises means for unloading a header portion from the first set of registers that has been processed by said processing core and loading a header portion into the first set of registers that has not been processed while the processing means is processing a header contained in the second set of registers.

5. The apparatus of claim 1, wherein said route table search means comprises a plurality of registers for communications between said processing core and said route table search means.

6. The apparatus of claim 1, wherein said table memory search means comprises a plurality of registers for communications between said processing core and said table memory search means.

7. The apparatus of claim 1 further comprising a central processor interface for controlling said processing core, said header storing means, said route table search means and said table memory search means and means for communicating between said central processor interface and said processing core, said header storing means, said route table search means and said table memory search means.

8. The apparatus of claim 7, wherein said communications means comprises a set of registers.

9. The apparatus of claim 1, wherein said processing core comprises an arithmetic logic unit and a sequence engine for executing instructions to process the header portion.

10. The apparatus of claim 2, wherein said header storing means further comprises means for storing information about a data packet that is being discarded so that the space in the header storing means occupied by the discarded packet and space in a data store are immediately reused.

11. The apparatus of claim 1, wherein said processing core comprises means for executing predetermined instructions that facilitate the processing of data packets.

12. The apparatus of claim 1 further comprising a central processing unit for controlling the processing core, the central processing unit comprising means for steering the processing core to one of a predetermined set of routines.

13. A method for processing a data packet to determine the routing of the data packet through a communications network, the data packet having a header portion and a data portion, the method comprising:

storing the header portion of the data packet;

processing the header portion of the data packet;

said processing comprising executing instructions for processing the header portion, searching, responsive to a first value contained within said header portion, through a route table to determine a route of the data packet, searching, responsive to a second value contained within said header portion, through a table memory for information about the destination of the data packet, wherein said table memory includes an interface table storing information related to one or more interfaces and a circuit table storing information related to one or more virtual circuits, said route table search and said table memory search operating simultaneously to process said header portion and generate one of an internal header and a network media header; and

generating a modified header portion containing at least some of the received header portion together with said generated one of the internal header and the network media header.

14. The method of claim 13, wherein said header storing comprises using a first set of header registers and a second set of header registers so that while processing the header contained in one of the set of header registers a new header portion is stored in the other set of header registers.

15. The method of claim 14, wherein said header storing further comprises switching between said set of header registers.

16. The method of claim 15, wherein said header storing further comprises unloading a header portion that has been processed by said processing core from the first set of registers and loading an unprocessed header portion into the first set of registers while the processing core processes a header in the second set of registers.

17. The method of claim 15, wherein said header storing further comprises storing information about a data packet that is being discarded so that the space in the header storing means occupied by the discarded packet and space in a data store are immediately reused.

18. The method of claim 13 further comprising controlling the processing core using a central processing unit, the controlling comprises steering the processing core to one of a predetermined set of routines.

19. A method for processing data packets to determine the route of the data packet, the data packet having a header portion and a data portion, the method comprising:

receiving a header portion of an incoming data packet;

performing a flat table memory access based on a first value contained within the received header portion, wherein said flat table memory includes an interface table storing information related to one or more interfaces and a circuit table storing information related to one or more virtual circuits;

performing a route look-up search simultaneously with said flat table memory access, said route table look-up search responsive to a second value contained within the received header portion;

checking information contained within the header portion while said flat table memory access and said route look-up search are being performed for determining if the header portion is valid;

generating one of an internal header and a network media header based on the results of the route look-up search and the flat table memory access; and

generating a modified header portion including the received header portion and said generated one of the internal header and the network media header.

20. The method of claim 19, wherein checking information in the header portion further comprises verifying a checksum value contained in the received header portion, decrementing a time-to-live counter contained with the header portion and generating a new checksum value to be inserted into the header portion.

21. The method of claim 19, further comprising processing a multicast data packet destined for a plurality of addresses comprising generating a header portion for each destination address, outputting a header and the same data portion for each destination address, and deleting the data portion from a buffer memory when the processing of the multicast data packet is completed.