EP1252795A1

EP1252795A1 - Device and method for packet inspection

Info

Publication number: EP1252795A1
Application number: EP01904840A
Authority: EP
Inventors: Monier Maher; Otto Andreas Schmid; Jean Pierre Bordes; Manju Hegde; Curtis Davis
Original assignee: Celox Networks Inc
Current assignee: Celox Networks Inc
Priority date: 2000-01-30
Filing date: 2001-01-11
Publication date: 2002-10-30
Also published as: AU2001232784A1; WO2001056327A9; WO2001056327A1

Abstract

A method and device for packet inspection whereby packets presented via an interleaved cell stream can be inspected 'on the fly' to identify, for example, the sequence of protocol encapsulations for each packet, as well as those portions of the packet which should be captured. The packet inspector is therefore capable of operating at high speeds. The packet inspector can also be used to inspect the payload portion of packets, if desired. A connection table look-up unit is used that accesses connection-based control data from a connection table for each cell input to the packet inspector. The look-up unit forwards the cell-specific control data to a data inspector via a forward control path, and the data inspector uses this control data when processing the associated cell. When processing of that cell is complete, the data inspector updates the associated control data to summarize its findings thus far, and then sends the updated control data back towards the look-up unit via a reverse control path for storage. When the next cell of the same packet is presented to the packet processor, the look-up unit retrieves and forwards the stored control data, which the data inspector uses to resumes the packet inspection process. A mechanism is also provided for replacing the control data for a cell propagating on the forward control path with updated control data that is propagating on the reverse control path.

Description

DEVICE AND METHOD FOR PACKET INSPECTION

The present invention relates to the field of high speed data packet inspection and processing for network systems, and especially (but not exclusively) to the identification of protocol encapsulation sequences and/or those portions of a packet which, according to the packet header, should be captured for use in the packet routing process.

Background of the Invention

Within internetworked communication systems, data packets are frequently transmitted through many different types of networks running different communication protocols. As a result, packets may undergo several levels of protocol encapsulation. This encapsulation process is illustrated generally in Fig. 1 where, for example, a Transmission Control Protocol ("TCP") packet having a payload portion and a header A is shown encapsulated into an Internet Protocol ("IP") packet by adding header portion B. This IP packet is then itself shown encapsulated into an Ethernet packet by adding header portion C. As appreciated by those skilled in the art, the number of encapsulation levels for any given packet in any given internetworked system will vary, and could be greater or less than three. It is also known to segment packets (including variable length packets) to be transmitted over certain physical interfaces into cells of a fixed shorter length for transmission efficiency, etc. This process is called segmentation and is illustrated generally in Fig. 2, where a packet is shown segmented into five distinct cells. Each cell includes a cell header, an end of packet indicator, and a payload. The end of packet indicator is typically a single bit which indicates whether that particular cell is the last cell of the packet. Accordingly, the end of packet indicator for the fifth cell (the left most cell in Fig. 2) is set to a "1, " while this indicator is set to a "0" for the other four cells. The payload of the first cell (the right most cell in Fig. 2) contains portion C of the packet header as well as part of packet header portion B, the payload of the second cell contains a part of packet header portions B and A, the payload of the third cell contains a part of packet header portion A and a portion of the packet payload, and so on. For the specific example shown in Fig. 2, only a portion of the fifth cell payload is required to carry the final portion of the packet payload. This fifth cell is therefore "padded, " as is known in the art, so that its length is the same as the other cells. While the exemplary packet shown in Fig. 2 is segmented into five cells, it is well known to segment packets into a lesser or much greater number of cells. It is also possible, though less common, for a single cell to represent an entire packet .

Fig. 3 illustrates how variable length packets from different non-interleaved connections are converted into an interleaved cell stream by a variable access multiplexor, known in the art as an MPHY port scheduler, after the packets undergo segmentation (not shown) . Typically, such a scheduler will pass one cell (or a small number of cells) to its output from each input connection in turn, resulting in an interleaved cell stream output such as that shown in Fig. 3, where the first cell of Packet 1 (C1P1) is followed by the first cell of Packet 2 (C1P2) , and so on. Although it is possible for a scheduler to be configured in such a manner as to output all cells of the same packet in a back-to-back arrangement, this would require large buffers for temporarily holding all cells arriving on other connections, and is therefore generally not done. Fig. 4 illustrates one case of how Asynchronous Transfer Mode ("ATM") cells belonging to different non-interleaved connections become interleaved as a result of traversing the ATM network. For. example, although cells Al and A2 are arranged back-to-back when they enter the ATM network, these cells will not necessarily be so arranged when they exit the network, and may instead be separated by cells Bl and CI, as shown in Fig. 4. In order to process cell streams (including interleaved cell streams of the types shown in Figs. 3 and 4) at various junctions in a network, it is often necessary to determine the sequence of protocol encapsulations (referred to as a "classification") for each packet and/or identify those portions of a packet which, according to the packet header, should be captured for use in the packet routing process . The conventional approach to performing these functions is to reassemble the packet from its constituent cells and then examine the header of the reconstituted packet in software. However, this approach can create significant delays, as examination of the packet header is usually not conducted until the packet has been completely reassembled, and reassembly of the packet cannot be completed until all of its constituent cells arrive. Further, this approach requires a large separate queue for each connection over which cells of a packet arrive in order (but not necessarily back-to-back, in the case of an interleaved cell stream) , and therefore does not scale efficiently where many connections must be supported. Further still, examining the bits of a packet header in software is a time consuming process, and therefore limits the speed of packet processing. Summary of the Invention

In order to solve these and other needs in the art, the inventors hereof have succeeded at designing and developing a configurable, protocol independent packet inspection device and method whereby packets, including variable length packets, carried by a series of cells presented in an interleaved (or a non-interleaved) cell stream can be inspected on a cell-by-cell basis "on the fly" to identify, for example, the sequence of protocol encapsulations for each packet, as well as those portions of the packet which, according to the packet header, should be captured for use in the packet routing process . For operation at high speeds, the cell inspection and/or capture functions have been pipelined and, in order to maintain the state of processing at the cell level, the mechanism of a reverse flow and forward flow of control information is introduced. Significantly, these functions can be performed without use of large memory buffers, without reassembling packets, and without processing the bits of the packet headers using time-consuming software. The packet inspector of the present invention is therefore capable of operating at high speeds, and is readily scalable for even higher speed applications. The packet inspector of the preferred embodiment is particularly well-suited as a hardware assist to the routing process (that is, functions previously performed using time- consuming software can now be accomplished in hardware according to the present invention) . Although this is the most preferred embodiment of the invention, the invention can also be used to inspect the payload portion of packets, if desired. The preferred packet inspector of the present invention includes a connection table look-up unit that accesses connection-based control data from a connection table for each cell input to the packet inspector via an interleaved cell stream. The look-up unit forwards this connection-based control data to a data inspector (i.e., another component of the packet inspector) via a forward control path, and the data inspector uses this control data when processing the associated cell to, for example, begin determining the sequence of protocol encapsulations for the packet represented by that cell and/or the portions of that packet which should be captured. When processing of that cell is complete, the data inspector updates the associated control data to summarize its findings thus far, and then sends the updated control data back towards the look-up unit via a reverse control path. Once received, the look-up unit stores this updated control data in the connection table. When the next cell of the same packet is presented to the packet processor, the look-up unit retrieves the stored control data for that connection (which, again, represents where the data inspector left off in inspecting the packet when processing of the prior cell was completed) . The look-up unit then forwards this next cell along with the retrieved updated control data to the data inspector, which then resumes the packet inspection process much like it would have if the first and second (and subsequent) cells of the packet had been presented to the data inspector back-to-back. Because it is possible for a subsequent cell of a packet to enter the data inspector before the updated control data generated from the prior cell is delivered to and stored by the look-up unit, a mechanism is also provided for replacing a cell ' s control data that is propagating on the forward control path with updated control data that is propagating on the reverse control path. The preferred data inspector used within the packet inspector of the present invention includes a number of substantially identical and configurable stages, referred to as inspection units, which through the exchange and updating of control data, can collectively traverse a protocol tree structure to determine the sequence of protocol encapsulations for any given packet, as well other important packet-specific information. The scalability of the preferred packet inspector for speed is achieved through the highly pipelined operation of these inspection units, which have a low interconnect complexity. The pipelining of the inspection and/or capture operations by the inspection units is preferably implemented via use of forward and reverse control flow paths which permit the exchange of state information between any two cells of the same packet. Such pipelining provides two distinct advantages: it facilitates high speed operations; and it facilitates inspection of packets to a greater depth (including into the packet payload, if desired) . The number of inspection units in the pipeline determines the depth to which a packet can be examined. The manner in which the inspection units are configured is a function of the protocols, protocol sequences and number of encapsulation layers to be supported. The inspection units can also be reconfigured as new protocols come into use. While some of the principal features and advantages of the invention have been described above, a greater and more detailed understanding of the invention may be attained by referring to the drawings and the detailed description of the preferred embodiments which follows. Brief Description of the Drawings

Fig. 1 is a diagram illustrating a packet undergoing a sequence of protocol encapsulations;

Fig. 2 is a diagram illustrating the segmentation of an encapsulated packet into several cells having a fixed size; Fig. 3 illustrates how variable length packets from different non-interleaved connections can be converted into an interleaved cell stream;

Fig. 4 illustrates how ATM cells belonging to different non-interleaved connections can become interleaved as a result of traversing the ATM network;

Fig. 5 is a block diagram of the preferred packet inspector of the present invention;

Fig. 6 is a functional block diagram of the packet inspector shown in Fig. 5 and an exemplary environment;

Fig. 7 is a more detailed functional block diagram of the packet inspector shown in Fig. 6 and the series of stages included within its preferred data inspector;

Fig. 8 illustrates a simplified protocol tree structure and how it is examined by multiple stages of the preferred data inspector;

Fig. 9 is a detailed functional block diagram of a representative stage of the preferred data inspector;

Fig. 10 is a functional block diagram of the window extractor shown in Fig. 9;

Fig. 11 is a functional block diagram of the data comparator shown in Fig. 9;

Fig. 12 is a functional block diagram of a representative CCU for the data comparator shown in Fig. 11; Fig. 13 is a functional block diagram of the CAM array shown in Fig. 9; and

Fig. 14 is a functional block diagram of a representative row of the CAM array shown in Fig. 13. Detailed Description of the Preferred Embodiments A packet inspector according to one preferred embodiment of the present invention is illustrated in Fig. 5 and is indicated generally by reference character 200. As shown therein, an interleaved cell steam is input to the packet inspector 200, which, in turn, outputs an interleaved cell stream along with associated control data. This control data preferably represents the sequence of protocol headers present in each packet processed by the packet inspector 200 (i.e., the "classification" of each packet) and/or the particular portions of those packets which should be captured for use in the packet routing process. In the particular preferred embodiment described immediately below, the control data represents both packet classifications and capture data, and the packet inspector 200 is configured for ascertaining this information from the input cell steam "on the fly" without modifying the cell stream or reassembling packets. The packet inspector 200 of this preferred embodiment is therefore particularly well suited for high speed networking applications.

As recognized by those skilled in the art, given that the packet inspector 200 is capable of ascertaining the control data from cells presented to the packet inspector via an interleaved cell stream, the packet inspector is also well suited for ascertaining the control data from cells presented to the packet inspector via a non-interleaved cell stream. A more detailed block diagram of the preferred packet inspector 200 and an exemplary environment is provided in Fig. 6. As shown therein, the packet inspector 200 includes a connection table lookup unit ("CTLU") 202, a connection table ("CT") 204 and a data inspector 206. The CTLU 202 is connected to the CT 204 via a data link 208 through which the CTLU 202 ^' can retrieve and store control data to the CT 204, as further explained below. The preferred embodiment of packet inspector 200 also includes a cell path 210 along which the interleaved (or a non-interleaved) cell stream can propagate from the input of the inspector 200, through the CTLU 202 and the data inspector 206, to the output of the packet inspector 200. Also shown in Fig. 6 is a forward control path 212 which extends from the CTLU 202, through the data inspector 206, to the output of the packet inspector 200, as well as a reverse control path 214 which extends from within the data inspector 206 to the CTLU 202. The cell path 210 and the forward control path 212 preferably extend from the output of the preferred packet inspector 200 to a controller 216, which decides whether to forward cells to a packet buffer 218 via a cell path 220, and whether to send cells and related capture instructions to an extractor 222 via a cell path 224 and an instruction path 221, respectively. The extractor 222 is also connected to a protocol processing unit ("PPU") 226 via a data link 228. Although only one controller, packet buffer, extractor and PPU are shown in Fig. 6, there may be multiple controllers (preferably connected to the output of the preferred packet inspector 200 in parallel) , and at least one packet buffer, at least one extractor, and multiple PPUs per controller, as recognized by those skilled in the art.

With further reference to Fig. 6, a general functional overview of the preferred packet inspector 200 will now be provided. When the first cell of a packet (of any length) arrives at the CTLU 202 over the cell path 210, the CTLU will identify the connection identification ("CID") of the packet. As appreciated by those skilled in the networking arts, this CID uniquely identifies the virtual or physical connection to which the packet belongs, and over which the cells of that packet arrive in order. The CTLU 202 uses this CID to index the CT 204 for retrieving connection-based control data that will be used in processing the first cell of the packet within the data inspector 206. The CTLU 202 forwards this control data to the data inspector 206 via the forward control path 212 while, at the same time, the first cell of the packet is forwarded (i.e., clocked) to the data inspector 206 via the cell path 210. Thus, the first cell of the packet and its corresponding control data are preferably forwarded to the data inspector 206 along parallel paths. The data inspector 206 then processes that portion of the packet header which is carried by the first cell using the corresponding control data.

In the typical case where the first cell represents only a portion of a packet header, the data inspector 206 may only begin to identify from this first cell the packet classification and those portions (typically in terms of bytes) , if any, of the packet that should be captured for use in the subsequent routing process. Thus, when processing of this first cell is complete within the data inspector 206, the data inspector updates (i.e., modifies and/or augments) the control data associated with that cell to represent what has been determined for the packet thus far (i.e., to represent the state of processing for that packet) . This updated control data is then forwarded by the data inspector 206 back towards the CTLU 202 along the reverse control path 214.

In some cases, there will be sufficient time for the updated control data to propagate back to the CTLU 202, and to be stored in the CT 204 (preferably in place of the original control data for that CID) , before the second cell of the same packet is forwarded to the data inspector 206 by the CTLU 202. In that event, when the second cell arrives at the CTLU 202, the CTLU identifies and uses its CID (which is the same as the CID for the first cell of that packet) to retrieve the updated control data back from the CT 204, and then forwards the second cell to the data inspector 206 via the cell path 210 while, at the same time, the updated control data is forwarded to the data inspector 206 via the forward control path 212. Because the updated control data represents where the data inspector 206 previously left off in processing the packet represented by the first and second cells, the data inspector 206 is capable of resuming processing of this packet in a seamless manner (from the standpoint of the data inspector) upon the arrival of the second cell and the updated control data. In other cases, there will not be sufficient time for the updated control data to propagate back to the CTLU 202, and to be stored in the CT 204 in place of the original control data for that CID, before the second cell of the same packet is forwarded to the data inspector 206 by the CTLU 202. For this reason, the data inspector is also configured to compare and replace control data propagating within the data inspector 206 on the forward control path 212 with control data (for the same packet) propagating on the reverse control path 214, as further explained below. Thus, regardless of whether updated control data for the second cell is retrieved from the CT 204 or received "on the fly" from the reverse control path 214, the data inspector 206 will obtain the updated control data for the second cell before it processes the packet information carried by such cell.

The forward control path 212 and the reverse control path 214 together comprise a control link and, in this preferred embodiment, are two physically distinct paths. The forward and reverse control paths are also clocked in such manners that it is impossible for the CTLU 202 to forward the second cell of the packet to the data inspector 206 during the period of time in which the control data updated upon processing the first cell is delivered to the CTLU 202 via the reverse control path 214 and stored in the CT 204 via the data link 208. As explained above, the CTLU 202 forwards the first cell of the packet to the data inspector 206 along with the original connection-based control data that was retrieved from the CT 204. Immediately thereafter, the CTLU 202 modifies the original control data stored in the CT 204 for this CID so as to indicate that the first cell is now being processed in the data inspector 206. In the case where the updated control data propagates back to the CTLU 202 before the second cell arrives, the process of saving the updated control data in place of the original control data in the CT 204 will remove the indication that the first cell is being processed in the data inspector 206. In the case where the updated control data does not propagate back to the CTLU 202 before the second cell arrives, the CTLU will forward the second cell of the packet to the data inspector 206 along with the control data retrieved from the CT 204, which indicates that the first cell is still being processed. The data inspector 206 will interpret this indication as an indication that the second cell is awaiting a transfer of updated control data from the reverse control path 214 within the data inspector, and will not attempt to process the packet information carried by the second cell until the transfer of the updated control data occurs .

In general, the manner in which the preferred packet inspector 200 processes any particular cell of a packet and the next cell of the same packet is the same as that described above for said first and second cells, with one significant exception. When the CTLU 202 receives the last cell of a packet, the CTLU will recognize this cell as such via the end of packet indicator that is preferably provided immediately behind the cell header (see Fig. 2) and will store this information in the CT 204. Thus, when the next cell having the same CID arrives at the CTLU 202, the CTLU will recognize from the control data stored in the CT 204 that this next cell is the first cell of a new packet. The CTLU will therefore reset the CT 204 for this CID such that any updated control data for the prior packet is replaced with the original connection-based control data. The CTLU 202 will then forward this first cell of the new packet to the data inspector 206 along with the original connection-based control data. As apparent from the above description, the CT 204 serves two important roles: it acts as a repository of initial connection-based information that is used by the data inspector 206 when processing the first cell of a packet; and it acts as an intermediate repository of updated connection-based information which represents the state of processing already initiated within the data inspector 206.

For each cell received via the cell path 210 by the controller 216, the controller also receives associated control data via the forward control path 212. The controller 216 uses this control data to determine "on the fly" whether to send the received cell to the packet buffer 218, and whether to send the received cell along with capture instructions (contained within or derived from the control data) to the extractor 222 via the cell path 224 and the instruction path 221, respectively. Upon receiving a cell and corresponding capture instructions from the controller 216, the extractor 222 sends to the PPU 226 only those portions of the received cell that are needed by the PPU 226, as determined from the capture instructions, so as to efficiently use the typically limited bandwidth provided on the input side of the PPU 226.

In view of the description of the preferred packet inspector 200 thus far, it should already be clear how this packet inspector can process packets in a disjointed manner. In other words, the packet inspector can begin processing a certain packet using the first cell of that packet, and then continue processing prior packets as additional cells of the prior packets arrive, and/or process subsequent packets as their cells arrive, before continuing processing of the "certain packet" mentioned above when one or more additional cells of that packet arrive. (Actually, the preferred embodiment of packet inspector 200 can process multiple cells of multiple packets in this manner simultaneously, as will be apparent) . The preferred packet inspector 200 can therefore ascertain important control information for packets represented by cells arriving over an interleaved cell stream without reassembling the packets, and without interrupting the cell flow. The preferred packet inspector 200 of the present invention is shown in greater detail in Fig. 7. As shown therein, the data inspector 206 comprises a number of preferably identical stages, referred to hereinafter as inspection units 230, 232, 234, 236, connected together in series. Fig. 7 also illustrates how the cell path 210, the forward control path 212 and the reverse control path 214 extend between each pair of adjacent inspection units. In this preferred embodiment, the purpose of each inspection unit is to examine the packet header (or a portion thereof) at the cell level to determine at least a portion of the protocol encapsulation sequence for that packet, and to also determine whether any portion (s) of that packet should be captured for forwarding to the PPU 226 shown in Fig. 6. These functions of the inspection units and the manner in which they sequentially process a packet can be conceptualized with the aid of the exemplary tree structure shown in Fig. 8. As apparent to those skilled in the art, this tree structure represents only a limited number of possible protocols, layers and sequences of protocol encapsulations. It does illustrate, however, that although a packet may have been encapsulated using a number of communication protocols, there are certain dependencies in any such encapsulation process, as indicated in Fig. 8. For example, a TCP packet cannot (at least currently) be encapsulated directly into an Ethernet packet, but must first be encapsulated into an IP (i.e., IPv4 or Ipv6) packet which, in turn, can be encapsulated into an Ethernet packet.

The inspection units sequentially examine portions of the packet header to determine the path to be taken at each possible juncture in the tree, and this will now be explained in terms of a specific example. Note that the lowest level protocol for any given packet (i.e., GE, ATM or SONET, for the simplified tree structure of Fig. 8) is a given from the input connection, and an identifier for this protocol can therefore be stored in the CT 204 as connection-based data (using the PID field, explained below) . Thus, if the lowest level protocol for a packet is, for example, GE, this information can be provided as a starting point to the data inspector 206 via the forward control path 212.

Suppose that Inspection Unit A is the inspection unit configured to identify the first branch in the tree (the next higher level protocol) for such a packet. By examining certain bytes in the first cell of the packet (as determined from a FWSP field, explained below) , Inspection Unit A may determine that the next higher level protocol is Ethernet (because the examined bytes match a predefined pattern indicative of the Ethernet protocol) . Inspection Unit A will then summarize this finding in the control data associated with the first cell (by modifying the PIDS field, explained below) , will indicate in that control data the particular bytes of the packet (if any) that it identified as needing to be captured for the PPU 226 (by modifying the CM field, explained below) , will further indicate in the control data the next set of bytes in the packet that should next be examined (by modifying the WSP field, explained below) , and will then forward this updated control data along to the next inspection unit via the forward control path. If processing of the first cell is complete, Inspection Unit A will also place the updated control data in the reverse control path 214 so that it ultimately becomes associated with the next cell of the same packet in one of the manners described above.

Using the information determined by Inspection Unit A, Inspection Unit B will identify the next branch in the tree (i.e., the protocol used in the level above the Ethernet level) , either by continuing the examination of the first cell or by examining the second cell of the packet if examination of the first cell is complete. If this examination determines that the next level protocol is the IPv4 protocol, Inspection Unit B will further update the control data for the associated cell to summarize this finding, to identify the next set of bytes to be examined, to indicate whether it identified any portions of the packet that should be captured, etc. The final examination of the exemplary packet may be done by Inspection Unit C which, upon examining the bytes specified for examination by Inspection Unit B, may determine that the protocol used in the level above the IPv4 level is the TCP protocol. Inspection Unit C will then update the control data associated with the cell it examined for forwarding to the output of the preferred packet inspector 200 via the forward control path 212.

Although Inspection Units A, B and C were each described above as fully identifying a protocol for one of the encapsulation levels, it is possible that the examination of a cell by, for example, Inspection Unit B, will merely narrow the set of possible protocols at a given location in the tree. In that event, Inspection Unit B will summarize what it determined for Inspection Unit C, and Inspection Unit C will then use these findings to continue the process started by Inspection B. Note that Inspection Units A, B and C discussed above are not necessarily the first three inspection units^' 230, 232, 234 shown in Fig. 7, and are not necessarily adjacent to one another. The particular inspection unit that is used to ■ examine the contents of any particular cell will be a function of how each inspection unit is configured. In this preferred embodiment, the particular inspection unit that is used to examine the contents of any particular cell is also a function of which inspection unit was used to examine the contents of the prior cell of the same packet. This is because, for ease of programming, no inspection unit will examine the contents of more than one cell of any given packet, and each cell of a packet will not be examined by an inspection unit that precedes (i.e., that is further to the left in Fig. 7 than) the inspection unit that examined the contents of the prior cell of the same packet .

For purposes herein, every packet is considered to have a protocol sequence classification, including packets having only one level of encapsulation (i.e., a sequence of length one). Although four inspection units 230, 232, 234, 236 are shown in Fig. 7, the actual number of inspection units required is a function of the number of possible packet encapsulation sequences to be supported and the length of those sequences in any given application of the invention. In the inventors' currently preferred embodiment, fourteen identical inspection units are connected in series in the manner illustrated in Fig. 7, as this number is believed to be sufficient for the preferred packet inspector 200 to identify virtually all possible packet classifications at any given location within a network .

The following control fields are preferably stored in the CT 204 for each connection to be supported: (1) the end of packet flag ("EOP"), which indicates whether the prior cell for this connection was the last cell of a packet (as noted above, this is the flag which, when set, prompts the CTLU 202 to reset the CT 204 for this connection upon the arrival of the next cell, which will necessarily be the first cell of a new packet); (2) an identification of the first stage ("Fstage"), i.e., inspection unit, that should begin processing the first cell of a new packet; (3) a first window starting pointer ("FWSP"), which indicates the location in the first cell of a packet where the data inspector 206 should begin its examination; (4) a packet forward flag ( "Pkt_Forward") which, when set, indicates that the entire packet should be forwarded to the packet buffer 218; (5) a packet capture flag ( "Pkt_Capture") which, when set, indicates that the entire packet should be captured for forwarding to the PPU 226; (6) a discard flag ("Discard"), which, when set, indicates that a protocol in the packet header is not supported and that the next cell and subsequent cells of the same packet should be discarded (this flag is also used to clear any cells of the same packet from the packet buffer 218) ; (7) a protocol identifier ("PID") field, which initially identifies the lowest level protocol for this connection,- (8) an identification of the stage ("Stage"), i.e., inspection unit, where examination of the associated cell should begin (preferably a number between 0 and N, where there are N-l stages) ; (9) a window starting pointer ("WSP"), which indicates the location in the associated cell where the data inspector 206 should continue its examination; and (10) a capture matrix ("CM"), which identifies those portions of a packet (preferably in terms of bytes) , if any, which should be captured and sent to the PPU 226.

In this preferred embodiment, the PID field is three bits long. Thus, the PID for any given connection can initially identify one of up to eight possible protocols at the lowest encapsulation level. Several of the fields stored in the CT 204 are included in the control data that propagates along the forward control path 212 (hereinafter referred to as "forward control data" or "FCD") in parallel with an associated cell propagating on the cell path 210. The FCD associated with each cell is utilized by the series of inspection units in the preferred data inspector 206 to conduct the sequential identification of the protocol encapsulations for each packet. The FCD into inspection unit 230 (i.e., Stage 0) of the data inspector 206 includes the following fields: CID; Pkt_Forward; Pkt_Capture; Stage; WSP; and CM. In the case of the first cell of a packet, Fstage and FWSP are used in lieu of the Stage and WSP fields. The FCD for each cell also includes: a start-of-packet ("SOP") flag (which is produced by the CTLU 202 from the EOP flag and which, when set, indicates that the associated cell is the first cell of packet) ; a PIDS string, which is preferably a twenty-four bit space holder generated by the CTLU, and which can be used to record the sequence of protocol encapsulations identified by the data inspector 206 from the examination of the associated cell; and a turn ("Turn") flag which, when set, indicates that updated control data for the associated cell has been sent over the reverse control path.

Other variables of the type commonly used in packet processing and routing functions may also be included in the forward control flow, as apparent to those skilled in the art. For example, the forward control flow may also include a PPU identifier, which may be necessary when more than one controller 216 and/or PPU 226 is used on the output side of the preferred embodiment of the packet inspector 200 shown in Fig. 6.

When first generated, the PIDS string comprises the three bits stored in the CT 204 under the PID field. Thus, when the PIDS string for the first cell of a packet is generated, it merely identifies the lowest level protocol for the corresponding packet. Thereafter, each stage of the data inspector 206 that identifies, through examination of the associated cell, another level in the packet encapsulation sequence can add three more bits to the PIDS string to identify its findings, and/or can modify. the existing string such as when an additional protocol level was not fully determined. Thus, the PIDS string associated with any given cell can identify a sequence of up to eight protocol encapsulations.

The PIDS string preferably behaves as a stack for the set of PID values obtained from each inspection unit in which the associated cell undergoes examination. This stack has a last in, first out structure with push and pop operations that can be conducted in the same cell time.

At any given location within the data inspector 206, the three bits that were most recently added to the PIDS string are considered the PID field for the associated cell. When processing of a cell is complete within the data inspector 206, this PID is extracted from the PIDS string and placed on the reverse control path where it will ultimately become associated with the next cell of the same packet (and thus become the first three bits of that next cell ' s PIDS string) . The PIDS string does remain in the forward control path at all times, and is thus ultimately forwarded to the controller 216 shown in Fig. 6 along with the associated cell. Further, as a cell undergoes processing in any particular inspection unit, other of the fields in the associated FCD are modified and passed to subsequent inspection units to facilitate the sequential examination. The WSP is used by an inspection unit to identify the particular portions (preferably in terms of bytes) of a packet to be examined. As a result of this examination, the inspection unit will compute a new WSP to identify the next series of bytes to be examined in a subsequent inspection unit. The Pkt_Forward and Pkt_Capture flags may also be set as a result of the examination. The Stage field may also be modified by the inspection unit to reflect the next inspection unit that must continue the processing of this particular packet (which is a function of how each inspection unit is programmed) .

As noted above, each packet may be processed a maximum of one time in each inspection unit and, for ease of programming, if a cell is examined in inspection unit k, the next cell of the same packet will not be examined any sooner than in inspection unit k+1. Thus, many cells will propagate through various inspection units without being examined by those inspection units. Further, in this particular embodiment of the invention, which focuses on ascertaining control data for use in the packet routing process, once the classification and capture data for a packet have been fully determined, the remaining cells of the packet will not be examined further other than to determine whether the FCD for each cell should be replaced with updated control data propagating on the reverse control path 214.

After the WSP is updated by an inspection unit in accordance with the examination conducted, and before the updated FCD and the associated cell are forwarded to the next inspection unit, the inspection unit will determine whether the updated WSP points to a portion of the packet that is carried by the particular cell in question. For example, in the case of the first cell of a packet, if the updated WSP identifies the starting byte of the next examination as byte z, and z is greater than 64, the inspection unit will know that this starting byte is carried by a subsequent cell (because in this preferred embodiment, each cell is only 64 bytes) , and that processing of the first cell is complete. When this occurs, the inspection unit will forward the current cell and the updated FCD to the next stage of the data inspector 206 (or to the controller 216, in the case of the last stage of the data inspector 206) , and will also place the updated control data in the reverse control path 214 so that it will ultimately become associated with the next cell of the same packet.

As noted above, when a cell belonging to a particular connection is forwarded by the CTLU 202 to the data inspector 206, the CTLU 202 makes a notation in the CT 204 that this cell is being processed in the data inspector 206. This is done by setting the Stage field for this connection to a value of N in the CT 204. Thus, if the next cell of the same packet arrives at the CTLU 202 before updated control data is obtained by the CTLU 214 from the reverse control path 214 and stored in place of the current control data in the CT 204, then this next cell will be forwarded along with the current control data (including the Stage value of N) to the data inspector 206. Because there are only N-l stages in the data inspector 206 (i.e., the first stage in this preferred embodiment is designated as Stage 0) , each inspection unit will interpret the Stage value of N as meaning that the cell should not be processed in that particular inspection unit. As a result, the cell will not be examined by any inspection unit until the FCD for this cell is replaced with CD generated using the prior cell and its associated FCD.

A detailed block diagram of a preferred inspection unit 250 for the preferred data inspector 206 shown in Fig. 7 is provided in Fig. 9. As shown therein, the inputs to the inspection unit 250 include the cell path 210, the forward control path 212, and the reverse control path 214. Likewise, the outputs from the inspection unit 250 include the cell path 210, the forward control path 212, and the reverse control path 214. As shown in Fig. 7, a turn signal path 252 branches from the forward control path 212 to a FIFO unit 276, and is used to provide the "Turn" signal to the FIFO 276 (three clock cycles ahead of the associated cell) as further described below. The inspection unit 250 also includes a window extractor 256, a data comparator 258, a CAM array 260, and a decision controller 262. Positioned within the cell path 210 are three delay elements 264, 266, 268, and positioned within the forward control path 212 are three delay elements 270, 272, 274. The purpose of the delay elements 262-274 is to ensure that cells and their corresponding FCD are synchronized as they propagate through the inspection unit 250. Also shown in Fig. 9 are a FIFO delay block 276, a path coupler 278, and a compare and replace module for controlling the replacement of FCD with reverse control data ("RCD"), when appropriate, as described below. The inputs, outputs and functions of the window extractor 256, the data comparator 258, the CAM array 260 and the deciβion controller 262 will now be described with reference to Figs. 10-14. It should be noted that, for the preferred packet inspector 200 described herein, it is assumed that 64 byte cells having an 8 byte width are input via the cell path 210. Thus, one cell is received every 8 clock cycles, with 64 bits of the cell being latched on each clock cycle. Referring now to Fig. 10, the preferred window extractor 256 includes an 8 byte input 282 (which is branched from the cell path 210, as shown in Fig. 9), a controller 284, a selector 286, two 8 byte registers 288, 290, and an 8 byte output 292. As can be seen from Fig. 10, the selector 286 receives instructions at an appropriate time from the controller 284 so as to select 8 consecutive bytes from the cell starting at the location designated by the WSP (or the FWSP, in the case of the first cell of a packet) . These selected 8 bytes (designated as bytes DB0-DB7) are then provided to the data comparator 258 via the output 292. The preferred data comparator 258, shown in Fig. 11, inspects bytes DB0-DB7 using thirty-two comparison control units ("CCUs") which are pre-configured via a configuration bus 294. Note that to simplify the illustration, only twenty-four CCUs are shown in Fig. 11. Each CCU (shown in greater detail in Fig. 12) is programmed with a one byte comparison value (labeled "CompParameter" in Figs. 11 and 12), the "Type" of comparison to be made (i.e., either an "equal to" or "greater than" comparison) , a one byte "Mask" (in the preferred embodiment, only eight of the thirty-two CCUs support a mask for design simplicity) that will be AND-ed (in the "Decision

Making" module) with the results of the chosen comparison, and a Setup variable which is used for timing control, and which also chooses one of four input bytes (1 byte each) for the chosen comparison with the "CompParameter" value. The Setup, CompParameter, Mask, and Type inputs are programmable variables whose values are a function of the protocol sequences to be supported, the values encoded for processing each sequence, and the portion of the encapsulation sequence (i.e., the location in a tree structure) that is currently under examination. The output of each CCU is a single bit representing the result of the comparison. When taken together, these bytes form a thirty-two bit vector that is passed to the CAM array 260. The preferred data comparator 258 may compare the chosen input byte against several predefined data patterns, including patterns of varying lengths, where each pattern may represent a possible encapsulation protocol .

This thirty-two bit vector, when combined with a 3 bit PID taken from the FCD, forms an index into a fifteen row content addressable memory (CAM) array 260. The purpose of the CAM array is to reduce the 32 bit output of the data comparator to one of sixteen possible decisions. Each row of the CAM array (shown in Fig. 14) consists of a value and a mask. In parallel, the input vector is first XNOR-ed with the CAM_Entry value, then OR-ed with the CAM_Mask value. A match is found if all bits in the result are set to 1, as determined by the AND gate. The output of the CAM array 260 is the row number (0-15, with 15 representing the bottom row) of the highest (lowest numbered) matching row. If no matches are found in the top fifteen rows, the output will be the bottom row since the it is a dummy row that is always asserted. The output of the CAM array 260 is used as an index into a table within the decision controller 262.

This table within the decision controller 262 contains sixteen entries, the fields of which contain information about what operations to perform next, including updating the WSP and the PIDS. These fields are described in detail in section 5.3 of Exhibit A, which is a programmer's guide to the preferred data inspector 206. All fields in this table are loaded from microcode (as are the various fields used in the data comparator 258 and the CAM array 260) via the programmable input line 298 shown in Fig. 9. Note that if the "Stage" variable received by the decision controller 262 indicates that the associated cell should not be processed in this particular stage of the data inspector, the decision controller will not update the forward control data for that cell, and will simply ignore the lookup index received from the CAM array 260. With further reference to Fig. 9, when the decision controller 262 determines (via the updated WSP) that processing of the cell is complete, it inserts the updated control data into the reverse control .path 214 via the path coupler 278 and sets the "Turn" flag in the FCD for the associated cell. The FCD is preferably sent to the next stage of the data inspector three clock cycles ahead of its associated cell and, therefore, reaches the next stage three cycles ahead of its associated cell. This Turn signal informs the FIFO 276 of the subsequent stage not to forward RCD at that time. This allows the updated control data from the decision controller 262 to be placed in the reverse control path immediately, so that it can become associated with the next cell of the same packet, which could be immediately behind the cell just processed in this inspection unit . The turn signal also prevents multiple RCD units from competing with one another at the path coupler 278. Once placed in the reverse control path 214, this RCD will enter the FIFO 276, which provides the CIDs of each RCD unit stored therein to the compare and replace module 280, as shown in Fig. 9. This module 280 then compares the CID of the "oldest" (i.e., left most, in Fig. 9) RCD unit with the CIDs of all FCD units propagating in the forward control path 212. If a match is found (indicating that the FCD and the RCD is for the same connection, and thus the same packet) , the compare and replace module (which will prioritize a match will the FCD of the oldest cell; the right most in Fig. 9) will replace the fields of the matching FCD with those from the matching RCD, and will remove (i.e., purge) the matching RCD unit from the • reverse control path 214. At any given time, there can be at most one RCD unit with a given CID. Therefore, no cell will have to swap control data between the forward and reverse control paths more than once. The SOP indicator is carried in the FCD for the following reason. If there is a match between the CIDs in any given set of FCD and RCD, but the SOP flag in the FCD is set (i.e., indicating that the FCD is associated with the first cell of a packet) , then the FCD is not replaced by the RCD, and the RCD is simply purged from the reverse control path (to prevent it from propagating back and incorrectly updating the CT 204) .

To ensure that the FCD for any given cell is replaced by RCD, when appropriate, the forward and reverse control paths are clocked on different cycles . Generally, the preferred timing for this overall process is as follows: the RCD is clocked; the FCD is compared with and then replaced by the RCD, when appropriate, and then the FCD is clocked. After the reverse control path is clocked, the last (most recently added) entry in the FIFO 276 is compared against the FCD that is about to .be shifted into the next stage. After the forward control path is clocked, that same entry in the FIFO 276 is compared against the next two FCD units. Additionally, all other entries in the FIFO are compared against the FCD that was just shifted into this stage in the manner described above.

In the preferred embodiment described above, the packet inspector 200 and the components thereof illustrated in Figs. 5-14 are implemented in an application specific integrated circuit ("ASIC") .

Although the packet inspector of the present invention has been described in detail only in the context of identifying networking control information for use in packet routing processes, the packet inspector may also be readily configured to inspect packet payloads for particular data (i.e., pattern matching) or for data in a particular range (e.g., less and/or greater than comparisons) , either instead of or in addition to performing the networking control functions described above. As apparent to those skilled in the art of networking software, configuring the packet inspector to perform packet payload inspection functions would merely require minor programming changes, including modifications of the CTLU and DCB table contents, the CAM entries and masks, etc., and would not require any significant hardware changes.

There are various changes and modifications which may be made to the particular embodiments of the invention described herein, as recognized by those skilled in the art. However, such changes and modifications are suggested by this disclosure. Thus, the rights in this invention should be limited only by the scope of the claims appended hereto, and their equivalents .

CELOX 48000

Packet Inspector Microcode Requirements Document

25^th Jan 2000 RevA03

Table Of Contents Introduction 4

1.1 Scope 4

1.2 Definitions and Acronyms i. 4 Requirements Overvie 4 Data Inspector Unit Overview 5 DIU Control Flows 6 PIDS definitions 7 Data Inspector Microcode , 8

6.1 CCU programming .^'. 8

6.1.1 CCU block register arrangement 8

6.1.2 CCU block register format 9

6.2 CAM programming 9

6.3 DCB programming 10

6.3.1 DCB Lookup Table Entry Format 10

6.3.2 DCB Operation 11 Sample PIDS file 12 Sample Microcode 12

8.1 CCB 12

8.2 CAM 12

8.3 DCB 12

1 Introduction

1.1 Scope

This document defines the requirements for programming the Packet Inspector. Separate programming must be created for each different situation in which the PI is used: the IPE card, as well as the ingress and egress sides of the ATM, POS, and Ethernet line cards. This will result in 7 different sets of PIDS definitions and microcode tables.

1.2 Definitions and Acronyms

IPE - Internet Protocol Engine (processing card)

PPU - Protocol Processing Unit

PI - Packet Inspector ASIC

BA - Buffer Access Controller ASIC

PM - Packet Manager ASIC

PID -Protocol ID

PIDS -Protocol ID Sequence

DIU - Data Inspector Unit

CCU - Comparison Control Unit

CAM - Content Addressable Memory

DCB - Decision Control Block

2 Requirements Overview

The first phase of programming the Packet Inspector involves defining all the Protocol ID Sequences (PIDS) that the Packet Inspector will generate and subsequently send to the PPUs. This list is based on the protocol scenarios described in the Protocol Processing Detailed Design Document. This list will be used to generate a jump table for the PPU protocol processing software.

The second phase of programming the PI is to generate the CCB, CAM and DCB tables for each of the 14 stages of the DIU.

Sample PIDS and microcode files are shown at the end of this document.

The easiest way to generate the PIDS and microcode files is to write a compiler using tools such as yacc and lex.

Data Inspector Unit Overview

The DIU consists of a pipeline of 14 identical "stages" connected together in series. The above figure shows one such stage. The purpose of the DIU is to identify the sequence of protocol headers present in each packet passing through it, and to generate control information used by other parts of the system to process the packet The inspection of packets is complicated by the fact that each packet is divided into one or more 64 byte cells, and the cells from multiple packet streams arrive at the DIU interleaved with each other. In order to handle interleaved packets, the DIU must be able to save state information about each packet (or flow) until the next cell of the flow arrives. The CLU provides the DIU with this capability.

The first stage of the DIU receives cells fiom me IFU, as well as saved state information (the forward control flow) from the CLU. One cell is received every 8 clock cycles, with 64 bits of the cell being latched on each clock cycle. The control information is all latched on the same clock edge, once every 8 clock cycles (hereafter referred to as one cell time). One of the fields in the forward control flow is the Window Starting Pointer (WSP). This value is used by the Window Extraction Block to select any 8 consecutive bytes from the cell. These 8 bytes are then passed to the Comparison Block, where they are inspected by 32 pre-configured Comparison Control Units (CCU)- Ea°ⁿ CCU is programmed with a value (1 byte) to compare against, the type of comparison (equals or greater-than- or-equal-to), a one byte mask (only 8 of the 32 CCUs support a mask) that is AND-ed with the data byte before comparison, as well as a two bit number to select one of the 8 data bytes to compare against. The byte number to compare against is determined by adding the byte selector to the row number of the CCU. Since the byte selector is a two bit number, a particular CCU can compare against one of 4 of the 8 data bytes, which allows for as many as 16 CCUs to compare against a single data byte. The output of each CCU is a single bit representing the result of the comparison. When taken together, these bits form a 32 bit vector that is passed to the CAM Block. This vector, when combined with a 3 bit PID and 1 bit DestPPU field taken from the forward control flow, forms a 36 bit "index" into a 15 row Content Addressable Memory (CAM). Each row of the CAM consists of a value and a mask (36 bits each). In parallel, the input vector is first ExclusiveNOR-ed with the CAM value, then OR-ed with the mask A match is found if all 36 bits in the result are set to 1. The output of the CAM is the row number (0-14) of the first (lowest numbered) matching row. If no matches are found, the output is 15 (OxF). This number, will be used as an index into the DCB Table, and is therefore passed to the DCB.

The DCB contains a table with 16 entries, the fields of which contain information about what operations to perform next These fields are described in detail in section 5.3.

It takes 24 clock cycles (or 3 cell times) for a cell to pass through a stage of the DIU. After being processed in a particular stage, the cell passes to the next stage, until it has passed through all 14 stages, at which point it moves on to the Distributor Flow Unit (DFU) for further processing. DIU Control Flows

Once per cell time, a 64 byte cell get inspected in each stage of the DIU. One of the many results of this inspection is a decision regarding whether or not to "turn around" the control information for this cell. Exactly what is meant by "turn around" will be explained in the paragraphs to follow.

There are only two condition in which a cell's control information can get turned around. Both occur only when a match is found in the CAM, and an entry in the DCB table is fetched. The first of these conditions occurs when the DCB sets STAGE to OxF. The second occurs when the DCB increments the window starting pointer (WSP) past the end of the cell (WSP>63).

One of the forward direction control signals associated with each cell is called diu urn. This signal is set to 0 when the cell enters the first stage. When a cell gets turned around, this signal gets set to 1, and it remains that way until the cell exits the pipeline. Each cell can only get turned around once as it travels through the pipeline.

In each stage, the forward flow of control information consists of a 3-entry shift register. Each entry contains all the control information associated with a particular data cell. Once every cell time, all the control information in this shift register is shifted over, with the last entry getting shifted to the first entry in the next stage.

The backward flow, however, is not a shift register. It is a FIFO with a maximum iwe, of 4 entries. Once eveiy cell time, a decision is made by the previous (N-l) stage as to whether or not it will accept a control cell from this stage's FIFO. If the previous stage will not accept a cell, this stage's FIFO remains unchanged (except that a new entry may get added to the FIFO if the last cell in the forward direction gets "turned around".

The decision made by each stage as to whether or not to accept a control cell from die next stage's reverse direction FIFO is strictly based on whether or not the cell leaving the stage during this cell time has "diu_turn" asserted. This is what prevents the FIFOs from overflowing. As a cell that has not been turned around flows through the pipeline, it enables the reverse direction information to flow back toward the CLU. This makes room later in the pipeline for that cell to eventually be turned around. But when a cell that has already been turned around flows through the pipeline, it temporarily blocks the reverse direction control information from flowing. However, this is alright, since this cell cannot be turned around a second time.

Although both the forward and backward direction control flows are each advanced once per cell time (8 clocks), they are not advanced on the same clock. This is because every control cell traveling in the reverse direction must be compared with every control cell traveling in the forward direction (as they pass each other). Comparisons can only occur between control cells within a single stage. Therefore, in order to prevent "ships passing in the night", nie forward and backward flows must be clocked on different cycles.

After the backward flow is clocked, the last (most recently added) entry in the FIFO is compared against the forward control cell that is about to be shifted into the next stage. After the forward flow is clocked, that same entry in the FIFO is compared against the next two forward ςontrol cells. Additionally, the other entries in the FIFO are compared against the forward control cell that was just shifted into this stage.

PIDS definitions

The Protocol ID Sequence (PIDS) keeps a record of all encapsulations, which have been found by each DIU stage. Each DIU stage can append the new PID to the PIDS and shift the remaining part to the right, or delete the last PID and shift the remaining part to the left, or simply replace the last PID. The type of update to the PEDS is determined by die UPID and DPID bits in the DCB table.

Update_PIDS

3 2 1

New PID appended = 3

Replace PID in PIDS

3 1

PID 2 is replaced by new PID 3.

As shown in the following diagram, the set of valid PIDS forms a tree structure, where each node of the tree (a PID) represents a particular protocol header, and each leaf represents a particular type of packet with a particular encapsulation. The actual numeric value of each PID is arbitrary.

In the PPU software, the PIDS can be used as an index into a jump table containing flie entry points (function pointers) to the protocol processing code specific to particular types of packet or encapsulations.

6 Data Inspector Microcode

6.1 CCU programming

The comparison control units are arranged as rows and columns as shown in the figure below.

• The table consists of 32 comparison units and has been arranged as 4 columns and 8 rows.

• ONLY the first column's comparison units are capable of masking.

• The first column's registers are mapped between 00 - IF

• The second column's registers are mapped between 20 - 2F. Addresses 30-3F are reserved.

• The third column's registers are mapped between 40 - 4F. Addresses 50 - 5F are reserved.

• The fourth column's registers are mapped between 50 - 5F. Addresses 70 - 7F are reserved.

6.1.1 CCU block register arrangement

Comp # 0 comp # 8 Comp # 16 comp # 24 Re : 00-02 Reg : 20 Reg : 40 Reg : 60

Comρ # l comp # 9 Comp # 17 comp # 25 Reg : 04-06 Reg : 22 Reg : 42 Reg : 62

Comp # 2 comp # 10 Comp # 18 comp # 26 Re : 08-0A Re : 24 Re : 44 Reg : 64

Comp # 3 comp # 11 Comp # 19 comp #27 Reg : 0C-0E Reg : 26 Reg : 46 Reg : 66

Comp # 4 comp # 12 Comp # 20 comp # 28 Reg : 10-12 Reg : 28 Reg : 48 Reg : 68 Comp # 5 comp # 13 Comp #21 comp #29 Reg : 14-16 Reg : 2A Reg : 4A Reg : 6A

Comp #6 comp # 14 Comp #22 comp #30 Reg : 18-1A Reg : 2C Reg : 4C Reg : 6C

Comp #7 comp # 15 Comp # 23 comp #31 Reg : lC-lE Reg : 2E Reg : 4E Reg : 6E

6.1.2 CCU block register format Data and Mask registers for the first column

Control Registers for the first column

Data and Control Registers for columns 2-4

6.2 CAM programming

The 32 bit comparison matrix from Comparison Control Block, together with the previous PID (from the Control Flow Block) and DestinationPPU (from CFB) form the 36 bit input data to the CAM. The CAM block checks for a matching entry in the CAM array and get the corresponding Table Index [0 - OxE]. If there is no match for the input data in the CAM, table index will be OxF. This table index is passed to the Decision Control Block.

This section describes how to configure CAM entries from CPU.

Each CAM Entry uses 72 bits. So Six registers are allocated for one CAM entry. One entry in the CAM table is as follows:

The CAM block in one DIU stage requires 15 such table entries.

So CAM Block in one DIU requires 15 * 6 = 90 CPU registers. ( Address space 0x00 - OxBF )

* If the Mask bit is set, then comparison is masked for that bit Results of comparison with masked bits will be always TRUE (logic 1).

6.3 DCB programming

The DCB gets the Lookup Table pointer from the CAM block and using this pointer extracts the lookup table entry. Based on the lookup table entry, new settings (protocol information and capture information) for the next Data Inspector are calculated.

The Decision Control Block consists of a lookup table with 16 entries. Each table entry is of 61 bits and hence requires 4 16-bit CPU registers. So, the DCB in one DIU stage (DIU-X) requires 16*4=64 16-bit registers.

This following table shows the register addressing and registers arrangement in the DCB block. 6.3.1 DCB Lookup Table Entry Format

DCB Operation

• PL is used to calculate the new Window Starting Pointer (WSP) using the following formula: WSP = WSP + PL

• PID is the 3-bit value that gets appended to the PIDS if the UPID bit is set

• UPID and DPID specify how the PIDS should be updated. First, if DPID is set, the most recent PID in the PIDS is removed (popped), then if UPID is set, PID is added (pushed) on to the PIDS.

• STAGE is the next stage in which this packet should be inspected. If STAGE is OxF, then no further processing will be done on this packet

• If DP is set, this packet will be discarded. It will not be stored in the cell buffer, and it will not be sent to the PPU.

• If CP is set, this entire packet will be sent to the PPU. It will also be stored in the cell buffer (unless STOPEN is set, in which case, only this cell and the previously inspected cells will be stored in the cell buffer, but the following cells will not).

• Any bits that are set in flie PCM identify bytes of flie packet that should be captured. The bit positions of bits that are set in the PCM represent the offsets from the WSP of the bytes of the packet that should be captured. For example, if bits 4..7 of the PCM are set, then bytes WSP..WSP+3 of this cell (or of the next cell, if WSP > 60) will be captured.

• If flie IP checksum verification bit is set, the DIU will verify the checksum of an IP header (without options) starting at the WSP. The WSP is incremented by PL BEFORE being used as the starting point for the checksum calculation. The result of the checksum verification is passed to the PPUs using the ICE (Ip Checksum Error) field in the control cell header.

• HSP is the starting point for the hash calculation (see description below).

• If HLENGTH is greater than zero, the DFU (the next unit to process the cells after the DIU) will calculate a hash over HLENGTH bytes of the current cell, starting at WSP+HSP bytes from the beginning of the cell The WSP is incremented by PL bytes AFTER the calculation of the starting point of the hash is made. If WSP+HSP+HLENGTH is greater than 64, then only flie bytes from WSP+HSP through the end of the current cell are used for the hash calculation. The calculation does NOT¹ continue into the next cell.

• The STOPEΝQ can be used to stop enqueuing the current packet into the cell buffer. This can be used if CP is set and there is no need to store the packet in the cell buffer. However, at least one cell will have been already stored in the cell buffer, and will need to be dequeued later by the PPU.

7 Sample PIDS file

# This is a sample PIDS definition file for the IPE card 000 IPCL

001-000 PPP, Control 001-001 PPP, IP

010-000 IP, Other 010-001-000 IP, TCP, Other 010-001-001 IP, TCP, HTTP 010-001-010 IP, TCP, Telnet

010-010-000 IP, UDP, Other 010-010-001 IP, UDP, NFS

8 Sample Microcode

8.1 CCB

# stage col row offset greater-or-equal value mask

0 0 0 00 Oxfe Oxff

0 0 1 0 0 Oxfe Oxff

0 0 2 0 0 0x03 Oxff

0 0 3 0 0 Oxcf Oxff

0 1 0 0 0 Oxaa

0 1 1 0 0 Oxaa

0 1 2 0 0 0x03

8.2 CAM

# stage row cmatrix pid destppu cmatrix-mask pid-mask destppu-mask 0 0 OxeOeOeOOO 0 0 Oxlflflfff 0 0

0 1 OxeOeOeOOO 0 0 Oxlflflfff 0 0

0 2 ^' OxeOeOeOOO 0 0 Oxlflflfff 0 0

0 3 OxeOeOeOOO 0 0 Oxlflflfff 0 0

8.3 DCB

# stage row pi pid upid dpid stage chksm dp pcm hsp hlen cp stopenq

0 0 20 3 1 0 0x4 1 0 OxOOfOOOOO 0 0 0 0

0 1 4 2 1 0 0x4 1 0 0x00000000 0 0 0 0 0 2 8 0 0 0 Oxf 1 1 0x00000000 0 0 0 0

Claims

What is claimed is:

1. A device for examining packets represented by cells in a cell stream, said device comprising^*: an input for receiving said cell stream; circuitry connected to said input for examining cells of a packet in the order said cells arrive through said input, and without reassembling said packet, to determine whether said packet contains at least one predefined data pattern, and for generating data representing the results of said examination; and an output connected to said circuitry for transmitting said cell stream and said generated examination data.

2. The device of claim 1 wherein said cell stream comprises multiple cells of multiple packets interleaved with one another, and said circuitry is configured to examine cells in the order they arrive through said input to determine whether each said packet contains at least one predefined data pattern.

3. The device of claim 2 wherein said circuitry is configured to determine from said examination whether each said packet contains one of a plurality of predefined data patterns .

4. The device of claim 3 wherein said predefined data patterns have varying lengths with respect to each other.

5. The device of claim 3 wherein each said packet includes a payload and said circuitry is configured to inspect cells carrying at least portions of. said packet payloads .

6. The device of claim 3 wherein each said packet includes a header and said circuitry is configured to inspect cells carrying at least portions of said packet headers.

7. The device of claim 6 wherein said predefined data patterns represent possible packet classifications and said examination data represents the classifications determined for said packets by said circuitry.

8. The device of claim 7 wherein said circuitry is further configured for identifying portions of said packets, if any, that should be captured for use in routing said packets, and said examination data further represents said portions to be captured.

9. The device of claim 3 wherein said output includes separate paths for said interleaved cell stream and said examination data.

10. A packet inspector comprising: a data inspector for examining the content of cells presented thereto; a look-up unit for accessing initial control data for cells presented to said data inspector; and a control link extending between said data inspector and said look-up unit and over which said initial control data is provided by said look-up unit to said data inspector.

11. The packet inspector of claim 10 wherein said data inspector is configured to examine said cell contents using said initial control data.

12. The packet inspector of claim 11 wherein said lookup unit is configured to access initial control data on a connection basis for each cell presented to said data inspector.

13. The packet inspector of claim 12 wherein said data inspector is configured to update initial control data associated with a particular cell of a given packet after examining at least a portion of said particular cell.

14. The packet inspector of claim 13 further comprising an output, wherein said control link extends to said packet inspector output and said data inspector is further configured to send said updated control data over said control link and towards said output .

15. The packet inspector of claim 13 wherein said data inspector is configured to send, upon determining that examination of said particular cell is complete, said updated control data over said control link for becoming associated with a subsequent cell of said given packet.

16. The packet inspector of claim 15 wherein said packet inspector is configured to associate said updated control data with the next cell of said given packet.

17. The packet inspector of claim 16 wherein said packet inspector is configured to associate said updated control data with said next cell prior to examining the contents of said next cell.

18. The packet inspector of claim 15 wherein said control link extends within said data inspector, and said data inspector is configured to replace initial control data associated with said subsequent cell with said updated control data if said initial control data and said updated control data are both traveling over said control link within said data inspector at the same time.

19. The packet inspector of claim 15 wherein said control link includes a forward control path and a reverse control path, said look-up unit is configured to provide said data inspector with said initial control data over said forward control path, and said data inspector is configured to send said updated control data over said reverse control path.

20. The packet inspector of claim 19 wherein said forward control path and said reverse control path are clocked differently.

21. The packet inspector of claim 15 wherein said lookup unit is configured to associate said updated control data, if received by said look-up unit over said control link, with said subsequent cell .

22. The packet inspector of claim 21 wherein said lookup unit is configured to store said updated control data, if received over said control link, and to retrieve said stored updated control data for use as initial control data for said subsequent cell .

23. The packet inspector of claim 22 wherein said lookup unit is configured to store said updated control data, if received over said control link, in a table on a connection basis .

24. The packet inspector of claim 23 wherein said lookup unit is configured to record in said table when a last cell of a packet is forwarded to said data inspector, and to restore initial control data in said table upon an arrival of a cell belonging to the same connection as said last cell.

25. The packet inspector of claim 14 further comprising an input for receiving a stream of cells, and wherein said output is configured for transmitting said stream of cells and updated control data delivered thereto over said control link.

26. The packet inspector of claim 25 wherein said output includes a first physical path for said stream of cells and a second physical path for said updated control data delivered thereto.

27. The packet inspector of claim 25 further comprising a cell path connected to said input and said output and extending through said look-up unit and said data inspector.

28. A method for examining a packet represented by a series of cells, the method comprising the steps of: forwarding control data relating to a cell of said packet to a data inspector; updating said control data in accordance with an examination of said cell by said data inspector; and associating said updated control data with a subsequent cell of the same packet.

29. The method of claim 28 further comprising the step of examining said cell with said data inspector using said control data.

30. The method of claim 29 wherein said subsequent cell is the next cell of said packet.

31. The method of claim 30 wherein said associating step includes one of the following steps : storing said updated control data in a table external to said data inspector for accessing upon an arrival of said next cell; and associating said updated control data with said next cell within said data inspector.

32. The method of claim 30 wherein said data inspector includes forward and reverse control paths extending therein, and said associating step includes transferring said updated control data from the reverse control path to the forward control path.

33. The method of claim 32 wherein said associating step includes replacing control data traveling on said forward control path with said updated control data from the reverse control path.

34. A packet inspector comprising: a data inspector for examining a packet represented by a plurality of cells in a stream of cells; and a cell path for providing said stream of cells to said data inspector, said data inspector comprising a plurality of interconnected inspection units, each inspection unit being configured to examine a different portion of said packet than any other inspection unit.

35. The packet inspector of claim 34 wherein cells in said cell path are provided to a first one of said inspection units with associated control data, and said first inspection unit is configured to update the control data associated with a particular cell upon examining said particular cell, and to forward said updated control data and said particular cell to an adjacent inspection unit.

36. The packet inspector of claim 35 wherein said data inspector includes a control link extending through and between said inspection units, and said first inspection unit is configured to forward said updated control data to said adjacent inspection unit over said control link.

37. The packet inspector of claim 36 wherein said cell path extends through said inspection units, and said first inspection unit is configured to forward said particular cell to said adjacent inspection unit over said cell path.

38. The packet inspector of claim 37 further comprising a look-up unit for accessing and providing said control data to said data inspector.

39. The packet inspector of claim 38 wherein said control link extends between said look-up unit and said data inspector, and said look-up unit is configured to forward said control data to said look-up unit over said control link.

40. The packet inspector of claim 39 wherein each inspection unit is configured to forward updated control data towards said look-up unit over said control link upon determining that examination of a cell associated with said updated control data is complete.

41. The packet inspector of claim 40 wherein each inspection unit includes a module for comparing and replacing, within said inspection unit, control data associated with a given cell of a given packet with updated control data for said given packet that is traveling over said control link.

42. The packet inspector of claim 35 wherein said control data includes data identifying the portion of the associated cell to be examined.

43. The packet inspector of claim 35 wherein said control data includes data identifying a particular inspection unit for examining the associated cell.

44. The packet inspector of claim 35 wherein said control data includes data indicating whether examination of the associated cell is complete.

45. The packet inspector of claim 34 wherein said packet is represented by a plurality of cells in an interleaved cell steam, and said data inspector is configured for examining said packet .

46. The packet inspector of claim 34 wherein said inspection units are substantially identical to one another.

47. The packet inspector of claim 34 wherein said inspection units are connected together in series.

48. The packet inspector of claim 34 wherein each inspection unit is programmably configurable with respect to a manner in which said packet may be examined therein.

49. The packet inspector of claim 34 wherein said packet inspector is configured such that each inspection unit inspects a maximum of one cell from any given packet.

50. The packet inspector of claim 34 wherein said packet inspector is configured such that each cell of a packet is inspected, if at all, in an inspection unit that is subsequent to the inspection unit in which an immediately prior cell of said packet was inspected.

51. The packet inspector of claim 34 wherein said data inspector is configured to examine a cell from a first packet in one inspection unit and a cell from a second packet in another inspection unit simultaneously.

52. A packet inspector for examining the contents of packets comprising multiple cells in a high speed data network, said packet inspector having means for examining constituent cells of each said packet and means for determining from said examination the classification of each said packet.

53. A device for processing packets represented by cells in a high speed data network, said device including a data capture unit having a first input for receiving a stream of data cells and a second input for receiving control data associated with said data cells, said data capture unit being configured for processing the control data associated with a particular cell of a given packet to identify a portion of said packet to be captured, and for updating the control data associated with said particular cell to designate said identified portion.

54. A packet inspector for inspecting the contents of multiple cells comprising data packets in a high speed data network, said packet inspector having a look-up unit for receiving a cell and accessing control information for said cell, a data inspector connected to said look-up unit for receiving said cell and said control information, and a reverse control link connected between said data inspector and said look-up unit over which updated control information may be transmitted back to said look-up unit for use in processing additional cells comprising said packet.

AMENDED CLAIMS

[received by the International Bureau on 10 duly 2001 (10.07.01); original claims 1,2,4,5,8 and 9 cancelled; original claims3,6,7, and 10 replaced by new claims 3,6,7 and 10; new claims 11 - 14 added (3 pages)]

3. A hair dryer having a heater, a fan positioned to provide an air flow that is heated by the heater, a battery, and a switch connected in circuit with the fan and the battery, the battery being chargeable via an electrical source when the hair dryer is seated in a base, said hair dryer comprising:

a handle that can be inserted into and removed from the base;

a manually operated trigger for operating the switch to connect and disconnect the fan and the battery when the handle is unseated from the base,

means for interlocking the fan and the battery, said means for interlocking including a pin and being responsive to the handle being seated in the base to physically prevent the switch from being closed, thereby preventing the fan from operating when the handle is seated in the base.

6. The hair dryer of claim 3, further comprising an arc prevention assembly dimensioned to prevent arcing between a first plurality of contacts disposed on the handle and a second plurality of mating electrical contacts disposed on the base.

7. The hair dryer of claim 6, wherein the arc prevention assembly includes a second switch that is located in the base and that, when closed, connects the second plurality of contacts with the source of electrical power, and wherein the arc prevention assembly is dimensioned so that the second switch does not close during insertion of the handle until the first plurality of contacts is in substantial electrical contact with the second plurality of contacts and so that the second switch opens during removal of the handle while the first plurality of contacts is in substantial electrical contact with the second plurality of contacts.

10. The hair dryer of claim 7, wherein the arc prevention assembly further Includes a pin and a spring that are adapted to open and close the second switch, the pin travels between a first position at which the second switch is open and a second position at which the second switch is closed during insertion and removal of the handle to and from the base, respectively, and wherein the spring biases the pin to the first position during removal.

11. A hair dryer having a heater, a fan positioned to provide an air flow that is heated by the heater, a battery, and a switch connected in circuit with the fan and the battery, the battery being chargeable via an electrical source when the hair dryer is seated in a base, said hair dryer comprising:

a manually operated trigger for operating the switch to connect and disconnect the fan and the battery when the hair dryer is unseated from the base; and

means for interlocking the fan and the battery, said means for interlocking including a pin and being responsive to the hair dryer being seated in the base to physically prevent the switch from being closed, thereby preventing the fan from operating when the hair dryer is seated in the base.

12. The hair dryer of claim 11, wherein said means for interlocking further comprises a spring.

13. The hair dryer of claim 12, wherein seating the hair dryer in the base engages the pin with the base, thereby positioning the pin to prevent the switch from connecting the fan and the battery, and wherein the hair dryer is not seated in the base, the spring biases the pin to a position to permit the switch to connect the fan and the battery.

14. The hair dryer of claim 11, wherein seating the hair dryer ln the base engages the pin with the base, thereby positioning the pin to prevent the switch from connecting the fan and the battery, and wherein the hair dryer is not seated in the base, the pin is positioned to permit the switch to connect the fan and the battery.