In-line packet processing

• US 6,791,947 B2
• Filed: 08/04/1998
• Issued: 09/14/2004
• Est. Priority Date: 12/16/1996
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Lim, Raymond Marcelino Manese, Sindhu, Pradeep S., Oskouy, Rasoul Mirzazadeh, Veeragandham, Sreeram, Ju, Hann-Hwan, Hui, Michael, Zimmer, Jeff, Ferguson, Dennis C.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US09/129,137
• Publication Number:
  US 20020003795A1
• Time in Patent Office: 2,233 Days
• Field of Search: 370/235, 370/238, 370/351, 370/355, 370/389, 370/392, 370/396, 370/400, 370/401, 370/428, 370/463, 370/465, 370/466, 370/467, 370/469, 370/470, 370/471, 370/474, 370/477, 370/395.1, 709/230, 709/238, 709/241, 709/243, 709/249, 709/250
• US Class Current: 370/238
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/555 : Error detection
• CPC Class Codes: H04L 49/602 : Multilayer or multiprotocol switching, e.g. IP switching
• CPC Class Codes: H04L 49/608 : ATM switches adapted to switch variable length packets, e.g. IP packets
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/901 : using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 : including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 69/16 : Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 : Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: H04L 69/324 : in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections

Abstract

A method and apparatus for in-line processing a data packet while routing the packet through a router in a system transmitting data packets between a source and a destination over a network including the router. The method includes receiving the data packet and pre-processing layer header data for the data packet as the data packet is received and prior to transferring any portion of the data packet to packet memory. The data packet is thereafter stored in the packet memory. A routing through the router is determined including a next hop index describing the next connection in the network. The data packet is retrieved from the packet memory and a new layer header for the data packet is constructed from the next hop index while the data packet is being retrieved from memory. The new layer header is coupled to the data packet prior to transfer from the router.

Claims

1. A method of in-line processing a data packet while transmitting data packets between a source and a destination over a network, the method comprising:

receiving the data packet;

screening header data for the data packet for errors as the data packet is received and prior to transferring any portion of the data packet to a packet memory;

dropping the data packet prior to transferring any portion of the data packet to the packet memory when the data packet includes an error;

storing the data packet in the packet memory when the data packet includes no error;

retrieving the data packet from the packet memory;

constructing new header data for the data packet; and

adding the new header data to the data packet prior to transferring the data packet toward the destination.

2. The method of claim 1 where the screening includes screening Layer 2 (L2) and Layer 3 (L3) headers for errors.

3. The method of claim 2 where the L2 header is examined to detect errors arising from unrecognized L2 header formats and unconfigured L2 connections.

4. The method of claim 2 where the L3 header is examined to detect data packets with checksum errors, packet length errors and L3 header errors.

5. The method of claim 1 where the packet memory is a distributed memory and the storing the data packet in the packet memory includes dividing the data packet into cells of a fixed size and storing the cells in the distributed memory.

6. The method of claim 5 where the retrieving the data packet from the packet memory includes reconstructing the data packet from cells stored in the distributed memory.

7. The method of claim 1 where the screening header data includes stripping L2 header data from the data packet prior to storing the data packet in the packet memory.

8. The method of claim 1 where the screening header data includes identifying the beginning of an L3 header and examining the L3 header for errors prior to storing the data packet in the packet memory.

9. The method of claim 1 further comprising determining a packet routing including a next hop index identifying a next connection in the network, where the next hop index includes a pointer to a sequence stored in a storage device and the constructing new header data includes executing the sequence.

10. The method of claim 9 where the execution of the sequence includes retrieving a common template for constructing a common portion of an L2 header to be attached to the data packet and a custom template for constructing a unique portion of the L2 header.

11. The method of claim 10 where the common and custom templates are executable code operable to construct an associated portion of an L2 header for the data packet.

12. The method of claim 1 where the receiving the data packet includes receiving a plurality of data packets for processing from a plurality of input ports representing a plurality of streams of data.

13. The method of claim 1 where the screening header data for the data packet includes dividing the data packet into fixed length cells and parsing an L2 header associated with a first cell of the data packet prior to receipt of the entire data packet.

14. The method of claim 13 where the parsing an L2 header includes examining the L2 header for errors and identifying the start of next header data in the data packet.

15. The method of claim 14 further including temporarily storing the cells for a data packet in a queue after L2 header parsing is completed and spraying consecutive cells in the data packet to different banks in the packet memory.

16. The method of claim 15 further including snooping while the cells are being stored to the queue and parsing an L3 header including examining the L3 header for errors.

17. The method of claim 15 further including dropping the data packet if errors are detected in the L2 header during L2 header parsing without storing a cell associated with the data packet in the queue.

18. One or more devices in a data processing environment for in-line processing a data packet while transmitting data packets between a source and a destination over a network, the one or more devices comprising:

a packet memory for storing portions of the data packet;

an input port for receiving a data packets, evaluating header information for the data packet prior to storing the data packet in the packet memory, and dropping the data packet prior to storing the data packet in the packet memory when the header information for the data packet is determined to include an error; and

an output port for receiving the data packet from the packet memory, constructing new header information for the data packet, and transferring the data packet toward the destination.

19. The one or more devices of claim 18 where the input port screens Layer 2 (L2) and Layer 3 (L3) headers for errors.

20. The one or more devices of claim 19 where the input port examines the L2 header to detect errors arising from unrecognized L2 header formats and unconfigured L2 connections.

21. The one or more devices of claim 19 where the input port examines the L3 header to detect data packets with checksum errors, packet length errors and L3 header errors.

22. The one or more devices of claim 18 further comprising a cell packetizer operable to divide the data packet into cells of a fixed size prior to transfer to the packet memory.

23. The one or more devices of claim 22 where the packet memory is a distributed memory and the one or more devices further comprise a spray engine for distributing cells across the distributed memory.

24. The one or more devices of claim 18 where the input port strips L2 header data from the data packet prior to storing the data packet in the packet memory.

25. The one or more devices of claim 24 where the input port identifies the beginning of an L3 header and examines the L3 header for errors prior to the storage of the data packet in the packet memory.

26. The one or more devices of claim 18 further comprising a controller for determining packet routing including a next hop index indicating a next connection in the network, where the next hop index is a pointer to a sequence stored in a storage device and the output port executes the sequence to construct the new header information.

27. The one or more devices of claim 26 where the storage device includes a common template for constructing a common portion of an L2 header to be attached to the data packet and a custom template for constructing a unique portion of the L2 header.

28. The one or more devices of claim 27 where the storage device is distributed and includes a local portion within the output port and a remote portion elsewhere and where the common template is stored in the local portion and the custom template is stored in the remote portion.

29. The one or more devices of claim 27 where the common and custom templates are executable code operable to construct an associated portion of an L2 header for the data packet.

30. The one or more devices of claim 18 further including a plurality of input ports and a plurality of output ports, each of the input ports and output ports configurable to receive and process a plurality of data packets representing a plurality of streams of data.

31. The one or more devices of claim 18 further including a cell packetizer operable to divide the data packet into fixed length cells and an L2 parsing engine operable to examine an L2 header associated with the first cell of the data packet prior to receipt of the entire data packet.

32. The one or more devices of claim 31 where the L2 parsing engine is operable to examine the L2 header for errors and identify the start of next header information in the data packet.

33. The one or more devices of claim 32 further including a queue operable for temporarily storing the cells for a data packet after L2 header parsing is completed and a spray engine operable to spray consecutive cells in the data packet to different banks in the packet memory.

34. The one or more devices of claim 33 further including an L3 parsing engine operable to snoop while the cells are being written to the queue and parse the L3 header including examining the L3 header for errors.

35. The one or more devices of claim 33 where the L2 parser engine is operable to drop a data packet if errors are detected in the L2 header during L2 header parsing without storing a cell associated with the data packet in the queue.

36. A method of transmitting a data packet in a path between a source and a destination, the method comprising:

receiving the data packet;

dividing the data packet into cells;

storing the cells in a memory;

screening header data of the data packet for errors and dropping a bad data packet prior to storing any of the cells in the memory;

reconstructing the data packet from cells stored in the memory;

constructing new header data for the data packet; and

outputting the data packet towards the destination.

37. In a system including a plurality of input ports and a plurality of output ports, a method of forwarding data packets from at least one input port to at least one output port, comprising:

receiving, at a first input port, a data packet containing header data;

analyzing the header data for errors prior to completely receiving the data packet at the first input port;

dropping the data packet prior to storing the data packet in memory when the header data includes an error;

storing the data packet in the memory when the header data includes no errors;

determining a first output port to which the data packet is to be forwarded based, at least in part, on the header data;

retrieving the data packet from memory;

constructing a new portion of header data;

adding the new portion of header data to the header data of the data packet to form a modified data packet; and

outputting the modified data packet from the first output port.

38. The method of claim 37, wherein the header data includes layer 2 header data.

39. The method of claim 37, wherein the header data includes layer 3 header data.

40. The method of claim 37, further including:

determining a next hop to which the data packet is to be output based, at least in part, on a first portion of header data; and

before the new portion of header data is added, modifying the first portion of header data in the data packet based, at least in part, on the determination of the next hop.

41. In a system including a plurality of input ports and a plurality of output ports, a method of forwarding data packets from at least one input port to at least one output port, comprising:

receiving, at a first input port, a data packet containing header data;

checking the header data for errors prior to entirely receiving the data packet at the first input port;

storing the data packet in memory when the header data includes no errors;

dropping the data packet prior to transferring the data packet to the memory when the header data includes an error;

determining a first output port to which the data packet is to be forwarded and a next hop to which the data packet is to be output, based, at least in part, on a first portion of the header data;

retrieving the data packet from memory;

modifying the first portion of header data in the retrieved data packet based, at least in part, on the next hop; and

outputting the modified data packet from the first output port.

42. A system for forwarding data packets, comprising:

at least one input port for receiving data packets;

a first header processor module for processing header data contained in the received data packets, analyzing the header data for errors before completely receiving the data packets at the at least one input port, and dropping the data packets when the header data of the data packets include errors;

a memory for storing the data packets processed by the first header processor module when the header data associated with the received data packets include no errors;

a second header processor module for processing the header data for data packets retrieved from the memory; and

at least one output port for outputting the data packets processed by the second header processor module.

43. The system of claim 42, wherein the first header processor module includes logic for stripping layer 2 header data from the received data packets.

44. The system of claim 42, wherein the second header processor module includes logic for constructing layer 2 header data.

45. The system of claim 42, further comprising:

a controller for determining the output port to which received data packets are to be output and a next hop to which the data packets are to be sent.

46. The system of claim 45, wherein the second header processor module includes logic for modifying layer 2 header data for data packets retrieved from the memory, based on the determined next hop.

47. In a system including a plurality of input ports and a plurality of output ports, a method for forwarding data packets from input ports to output ports, comprising:

receiving, at ones of the input ports, data packets containing header data;

analyzing the header data for errors prior to completely receiving the data packets at the ones of the input ports;

dropping the data packets when the data packets include errors;

identifying, when the data packets include no errors, ones of the output ports to which the data packets are to be forwarded based, at least in part, on the header data;

forming a new portion of header data for the data packets;

adding the new portion of header data to the header data of the data packets to form modified data packets; and

outputting the modified data packets from the ones of the output ports.