UNITED STATES DEPARTMENT OF COMMERCE
`United States Patent and Trademark Office
`
`October 17, 2018
`
`THIS IS TO CERTIFY THAT ANNEXED IS A TRUE COPY FROM THE
`RECORDS OF THIS OFFICE OF THE FILE WRAPPER AND CONTENTS
`OF:
`
`APPLICATION NUMBER: 09/608,237
`FILING DA TE: June 30, 2000
`PA TENT NUMBER: 6,651,099
`ISSUE DA TE: November 18, 2003
`
`By Authority of the
`Under Secretary of Commerce for Intellectual Property
`and Director of the United States Patent and Trademark Office
`
`~~~
`
`P.R. GRANT
`Certifying Officer
`
`PART ({) OF (<A PART(S)
`
`EX 1017 Page 1
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`r J
`
`j ~
`t 9
`
`. w
`~; F~
`
`13
`
`DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
`
`Note that this document includes hardware diagrams and descriptions that may
`
`include signal names. In most cases, the names are sufficiently descriptive, in other cases
`
`however the signal names are not needed to understand the operation and practice of the
`
`5
`
`invention.
`
`Operation in a Network
`
`FIG. 1 represents a system embodiment of the present invention that is referred to
`
`herein by the general reference numeral 100. The system 100 has a computer network 102
`
`that communicates packets (e.g., IP datagrams) between various computers, for example
`
`10
`
`between the clients 104-107 and servers 110 and 112. The network is shown
`
`schematically as a cloud with several network nodes and links shown in the interior of the
`
`cloud. A monitor 108 examines the packets passing in either direction past its connection
`
`point 121 and, according to one aspect of the invention, can elucidate what application
`
`programs are associated with each packet. The monitor 108 is shown examining packets
`
`15
`
`(i.e., datagrams) between the network interface 116 of the server 110 and the network.
`
`The monitor can also be placed at other points in the network, such as connection point
`
`123 between the network 102 and the interface 118 of the client 104, or some other
`
`location, as indicated schematically by connection point 125 somewhere in network 102.
`
`Not shown is a network packet acquisition device at the location 123 on the network for
`
`20
`
`converting the physical information on the network into packets for input into monitor
`
`108. Such packet acquisition devices are common.
`
`Various protocols may be employed by the network to establish and maintain the
`
`required communication, e.g., TCP/IP, etc. Any network activity-for
`
`example an
`
`application program run by the client 104 (CLIENT 1) communicating with another
`
`25
`
`running on the server 110 (SERVER 2)-will produce an exchange of a sequence of
`
`packets over network 102 that is characteristic of the respective programs and of the
`
`network protocols. Such characteristics may not be completely revealing at the individual
`
`packet level. It may require the analyzing of many packets by the monitor 108 to have
`
`enough information needed to recognize particular application programs. The packets
`
`t
`
`30 may need to be parsed then analyzed in the context of various protocols, for example, the
`
`EX 1017 Page 21
`
`

`

`

`

`

`

`

`

`

`

`

`

`Cl
`
`(}
`
`19
`
`The other internal data structure that is built by compiler 310 is the set of state
`
`patterns and processes 326. These are the different states and state transitions that occur in
`
`different conversational flows, and the state operations that need to be performed (e.g.,
`
`patterns that need to be examined and new signatures that need to be built) during any
`
`5
`
`state of a conversational flow to further the task of analyzing the conversational flow.
`
`Thus, compiling the PDL files and layer selections provides monitor 300 with the
`
`information it needs to begin processing packets. In an alternate embodiment, the contents
`
`of one or more of databases 308 and 326 may be manually or otherwise generated. Note
`
`that in some embodiments the layering selections information is inherent rather than
`
`IO
`
`explicitly described. For example, since a POL file for a protocol includes the child
`
`protocols, the parent protocols also may be determined.
`
`In the preferred embodiment, the packet 302 from the acquisition device is input
`
`into a packet buffer. The pattern recognition process 304 is carried out by a pattern
`
`analysis and recognition (PAR) engine that analyzes and recognizes patterns in the
`
`15
`
`packets. In particular, the PAR locates the next protocol field in the header and
`
`determines the length of the header, and may perform certain other tasks for certain types
`
`of protocol headers. An example of this is type and length comparison to distinguish an
`
`IEEE 802.3 (Ethernet) packet from the older type 2 (or Version 2) Ethernet packet, also
`
`called a DIGITAL-Intel-Xerox (DIX) packet. The PAR also uses the pattern structures
`
`20
`
`and extraction operations database 308 to identify the next protocol and parameters
`
`associated with that protocol that enables analysis of the next protocol layer. Once a
`
`pattern or a set of patterns has been identified, it/they will be associated with a set of none
`
`or more extraction operations. These extraction operations (in the form of commands and
`
`associated parameters) are passed to the extraction process 306 implemented by an
`
`25
`
`extracting and information identifying (Em engine that extracts selected parts of the
`
`packet, including identifying information from the packet as required for recognizing this
`
`packet as part of a flow. The extracted information is put in sequence and then processed
`
`in block 312 to build a unique flow signature (also called a "key") for this flow. A flow
`
`signature depends on the protocols used in the packet. For some protocols, the extracted
`
`30
`
`components may include source and destination addresses. For example, Ethernet frames
`
`have end-point addresses that are useful in building a better flow signature. Thus, the
`
`signature typically includes the client and server address pairs. The signature is used to
`
`EX 1017 Page 27
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`26
`
`the PRD 308 includes two parts, a single protocol table 1850 (PT) which has an entry for
`
`each protocol known for the monitor, and a series of Look Up Tables 1870 (LUT's) that
`
`are used to identify known protocols and their children. The protocol table includes the
`
`parameters needed by the pattern analysis and recognition process 304 (implemented by
`
`5
`
`PRE 1006) to evaluate the header information in the packet that is associated with that
`
`protocol, and parameters needed by extraction process 306 (implemented by slicer 1007)
`
`to process the packet header. When there are children, the PT describes which bytes in the
`
`header to evaluate to determine the child protocol. In particular, each PT entry contains
`
`the header length, an offset to the child, a slicer command, and some flags.
`
`10
`
`The pattern matching is carried out by finding particular "child recognition codes"
`
`in the header fields, and using these codes to index one or more of the LUT' s. Each LUT
`
`entry has a node code that can have one of four values, indicating the protocol that has
`
`been recognized, a code to indicate that the protocol has been partially recognized (more
`
`LUT lookups are needed), a code to indicate that this is a terminal node, and a null node
`
`15
`
`to indicate a null entry. The next LUT to lookup is also returned from a LUT lookup.
`
`Compilation process is described in FIG. 4. The source-code information in the
`
`form of protocol description files is shown as 402. In the particular embodiment, the high
`
`level decoding descriptions includes a set of protocol description files 336, one for each
`
`protocol, and a set of packet layer selections 338, which describes the particular layering
`
`20
`
`(sets of trees of protocols) that the monitor is to be able to handle.
`
`A compiler 403 compiles the descriptions. The set of packet parse-and-extract
`
`operations 406 is generated ( 404 ), and a set of packet state instructions and operations
`
`407 is generated ( 405) in the form of instructions for the state processor that implements
`
`state processing process 328. Data files for each type of application and protocol to be
`
`25
`
`recognized by the analyzer are downloaded from the pattern, parse, and extraction
`
`database 406 into the memory systems of the parser and extraction engines. (See the
`
`parsing process 500 description and FIG. 5; the extraction process 600 description and
`
`FIG. 6; and the parsing subsystem hardware description and FIG. 10). Data files for each
`
`type of application and protocol to be recognized by the analyzer are also downloaded
`
`30
`
`from the state-processor instruction database 407 into the state processor. (see the state
`
`processor 1108 description and FIG. 11.).
`
`EX 1017 Page 34
`
`

`

`' . G)
`
`. ·~
`
`27
`
`Note that generating the packet parse and extraction operations builds and links
`
`the three dimensional structure (one embodiment) or the or all the lookup tables for the
`
`PRD.
`
`Because of the large number of possible protocol trees and subtrees, the compiler
`
`5
`
`process 400 includes optimization that compares the trees and subtrees to see which
`
`children share common parents. When implemented in the form of the LUT' s, this
`
`process can generate a single LUT from a plurality ofLUT's. The optimization process
`
`further includes a compaction process that reduces the space needed to store the data of
`
`thePRD.
`
`10
`
`As an example of compaction, consider the 3-D structure of FIG. 18A that can be
`
`thought of as a set of 2-D structures each representing a protocol. To enable saving space
`
`by using only one array per protocol which may have several parents, in one embodiment,
`
`the pattern analysis subprocess keeps a "current header" pointer. Each location (offset)
`
`index for each protocol 2-D array in the 3-D structure is a relative location starting with
`
`15
`
`the start of header for the particular protocol. Furthermore, each of the two-dimensional
`
`arrays is sparse. The next step of the optimization, is checking all the 2-D arrays against
`
`all the other 2-D arrays to find out which ones can share memory. Many of these 2-D
`
`arrays are often sparsely populated in that they each have only a small number of valid
`
`entries. So, a process of "folding" is next used to combine two or more 2-D arrays
`
`20
`
`together into one physical 2-D array without losing the identity of any of the original 2-D
`
`arrays (i.e., all the 2-D arrays continue to exist logically). Folding can occur between any
`
`2-D arrays irrespective of their location in the tree as long as certain conditions are met.
`
`Multiple arrays may be combined into a single array as long as the individual entries do
`
`not conflict with each other. A fold number is then used to associate each element with its
`
`25
`
`original array. A similar folding process is used for the set of LUTs 1850 in the alternate
`
`embodiment of PIG. l8B.
`
`In 410, the analyzer has been initialized and is ready to perform recognition.
`
`FIG. 5 shows a flowchart of how actual parser subsystem 301 functions. Starting
`
`at 501, the packet 302 is input to the packet buffer in step 502. Step 503 loads the next
`
`30
`
`(initially the first) packet component from the packet 302. The packet components are
`
`extracted from each packet 302 one element at a time. A check is made (504) to determine
`
`EX 1017 Page 35
`
`

`

`28
`
`if the load-packet-component operation 503 succeeded, indicating that there was more in
`
`the packet to process. If not, indicating all components have been loaded, the parser
`
`subsystem 301 builds the packet signature (512)-the next stage (FIG 6).
`
`If a component is successfully loaded in 503, the node and processes are fetched
`
`5
`
`(505) from the pattern, parse and extraction database 308 to provide a set of patterns and
`
`processes for that node to apply to the loaded packet component. The parser subsystem
`
`301 checks (506) to determine if the fetch pattern node operation 505 completed
`
`successfully, indicating there was a pattern node that loaded in 505. If not, step 511
`
`moves to the next packet component. If yes, then the node and pattern matching process
`
`10
`
`are applied in 507 to the component extracted in 503. A pattern match obtained in 507 (as
`
`indicated by test 508) means the parser subsystem 301 has found a node in the parsing
`
`elements; the parser subsystem 301 proceeds to step 509 to extract the elements.
`
`If applying the node process to the component does not produce a match (test
`
`508), the parser subsystem 301 moves (510) to the next pattern node from the pattern
`
`15
`
`database 308 and to step 505 to fetch the next node and process. Thus, there is an
`
`"applying patterns" loop between 508 and 505. Once the parser subsystem 301 completes
`
`all the patterns and has either matched or not, the parser subsystem 301 moves to the next
`
`packet component (511).
`
`Once all the packet components have been the loaded and processed from the
`
`20
`
`input packet 302, then the load packet will fail (indicated by test 504), and the parser
`
`subsystem 301 moves to build a packet signature which is described in FIG. 6
`
`FIG. 6 is a flow chart for extracting the information from which to build the
`
`packet signature. The flow starts at 601, which is the exit point 513 of FIG. 5. At this
`
`point parser subsystem 301 has a completed packet component and a pattern node
`
`25
`
`available in a buffer (602). Step 603 loads the packet component available from the
`
`pattern analysis process of FIG. 5. If the load completed ( test 604), indicating that there
`
`was indeed another packet component, the parser subsystem 301 fetches in 605 the
`
`extraction and process elements received from the pattern node component in 602. If the
`
`fetch was successful (test 606), indicating that there are extraction elements to apply, the
`
`30
`
`parser subsystem 301 in step 607 applies that extraction process to the packet component
`
`based on an extraction instruction received from that pattern node. This removes and
`
`EX 1017 Page 36
`
`

`

`

`

`•
`
`30
`
`802 those elements are shown in the form of a UFKB-entry in the buffer. The LUE, the
`
`lookup engine 314 computes a "record bin number" from the hash for a flow-entry. A bin
`
`herein may have one or more "buckets" each containing a flow-entry. The preferred
`
`embodiment has four buckets per bin.
`
`5
`
`Since preferred hardware embodiment includes the cache, all data accesses to
`
`records in the flowchart of FIG. 8 are stated as being to or from the cache.
`
`Thus, in 804, the system looks up the cache for a bucket from that bin using the
`
`hash. ff the cache successfully returns with a bucket from the bin number, indicating there
`
`are more buckets in the bin, the lookup/update engine compares (807) the current
`
`10
`
`signature (the UFKB-entry's signature) from that in the bucket (i.e., the flow-entry
`
`signature). ff the signatures match (test 808), that record (in the cache) is marked in step
`
`810 as "in process" and a timestamp added. Step 811 indicates to the UFKB that the
`
`UFKB-entry in 802 has a status of "found." The "found" indication allows the state
`
`processing 328 to begin processing this UFKB element. The preferred hardware
`
`15
`
`embodiment includes one or more state processors, and these can operate in parallel with
`
`the lookup/update engine.
`
`In the preferred embodiment, a set of statistical operations is performed by a
`
`calculator for every packet analyzed. The statistical operations may include one or more
`
`of counting the packets associated with the flow; determining statistics related to the size
`
`20
`
`of packets of the flow; compiling statistics on differences between packets in each
`
`direction, for example using timestamps; and detennining statistical relationships of
`
`timestamps of packets in the same direction. The statistical measures are kept in the flow(cid:173)
`
`entries. Other statistical measures also may be compiled. These statistics may be used
`
`singly or in combination by a statistical processor component to analyze many different
`
`25
`
`aspects of the flow. This may include determining network usage metrics from the
`
`statistical measures, for example to ascertain the network's ability to transfer information
`
`for this application. Such analysis provides for measuring the quality of service of a
`
`conversation, measuring how well an application is performing in the network, measuring
`
`network resources consumed by an application, and so forth.
`
`30
`
`To provide for such analyses, the lookup/update engine updates one or more
`
`counters that are part of the flow-entry (in the cache) in step 812. The process exits at 813.
`
`EX 1017 Page 38
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`39
`
`the flow-entry. The flow removal state may be a NOP (no-op) instruction which means
`
`there are no removal instructions.
`
`Once the appropriate flow removal instruction as specified for this flow (a NOP or
`
`otherwise) is set and saved, the process is exited at 1313. The state processor 1108 can
`
`5
`
`now obtain another unified flow key buffer entry to process.
`
`If at 1309 it is determined that processing for this flow is not completed, then in
`
`1310 the system saves the state processor instruction pointer in the current flow-entry in
`
`the current flow-entry. That will be the next operation that will be performed the next
`
`time the LRE 1107 finds packet in the UFKB that matches this flow. The processor now
`
`10
`
`exits processing this particular unified flow key buffer entry at 1313.
`
`Note that state processing updates information in the unified flow key buffer 1103
`
`and the flow-entry in the cache. Once the state processor is done, a flag is set in the
`
`UFKB for the entry that the state processor is done. Furthermore, If the flow needs to be
`
`inserted or deleted from the database of flows, control is then passed on to the flow
`
`15
`
`insertion/deletion engine 1110 for that flow signature and packet entry. This is done by
`
`the state processor setting another flag in the UFKB for this UFKB-entry indicating that
`
`the state processor is passing processing of this entry to the flow insertion and deletion
`
`engine.
`
`The flow insertion and deletion engine 1110 is responsible for maintaining the
`
`20
`
`flow-entry database. In particular, for creating new flows in the flow database, and
`
`deleting flows from the database so that they can be reused.
`
`The process of flow insertion is now described with the aid of FIG. 12. Flows are
`
`grouped into bins of buckets by the hash value. The engine processes a UFKB-entry that
`
`may be new or that the state processor otherwise has indicated needs to be created.
`
`25
`
`FIG. 12 shows the case of a new entry being created. A conversation record bin
`
`(preferably containing 4 buckets for four records) is obtained in 1203. This is a bin that
`
`matches the hash of the UFKB, so this bin may already have been sought for the UFKB(cid:173)
`
`entry by the LUE. In 1204 the FIDE 1110 requests that the record bin/bucket be
`
`maintained in the cache system 1115. If in 1205 the cache system 1115 indicates that the
`
`30
`
`bin/bucket is empty, step 1207 inserts the flow signature (with the hash) into the bucket
`
`and the bucket is marked "used" in the cache engine of cache 1115 using a timestamp that
`
`EX 1017 Page 47
`
`

`

`

`

`

`

`

`

`•
`
`43
`
`~-~ddition,
`
`........
`MlB Compilers are available. An MlB Compiler is a tool that greatly
`simplifies the creation and maintenance of proprietary MlB extensions.
`
`Examples of Packet Elucidation
`
`Monitor 300, and in particular, analyzer 303 is capable of carrying out state
`
`analysis for packet exchanges that are commonly referred to as "server announcement"
`
`type exchanges. Server announcement is a process used to ease communications between
`
`a server with multiple applications that can all be simultaneously accessed from multiple
`
`clients. Many applications use a server announcement process as a means of multiplexing
`
`a single port or socket into many applications and services. With this type of exchange,
`
`messages are sent on the network, in either a broadcast or multicast approach, to
`
`announce a server and application, and all stations in the network may receive and decode
`
`these messages. The messages enable the stations to derive the appropriate connection
`
`point for communicating that particular application with the particular server. Using the
`
`server announcement method, a particular application communicates using a service
`
`channel, in the form of a TCP or UDP socket or port as in the 1P protocol suite, or using a
`
`SAP as in the Novell JPX protocol suite.
`
`The analyzer 303 is also capable of carrying out "in-stream analysis'' of packet
`
`exchanges. The "in-stream analysis" method is used either as a primary or secondary
`
`recognition process. As a primary process, in-stream analysis assists in extracting detailed
`
`information which will be used to further ~cognize both the specific application and
`
`application component. A good example of in-stream analysis is any Web-based
`
`application. For example, the commonly used PointCast Web information application can
`
`be recognized using this process; during the initial connection between a PointCast server
`
`and client, specific key tokens exist in the data exchange that will result in a signature
`
`being generated to recognize PointCast.
`
`The in-stream analysis process may also be combined with the server
`announcement process. In many cases in-stream analysis will augment other recognition
`
`processes. An example of combining in-stream analysis with server announcement can be
`
`found in business applications such as SAP and BAAN.
`
`"Session tracking" also is known as one of the primary processes for tracking
`
`applications in client/server packet exchanges. The process of tracking sessions requires
`
`EX 1017 Page 51
`
`

`

`44
`
`an initial connection to a predefined socket or port number. This method of
`
`communication is used in a variety of transport layer protocols. It is most commonly seen
`
`in the TCP and UDP transport protocols of the IP protocol.
`
`During the session tracking, a client makes a request to a server using a specific
`
`5
`
`port or socket number. This initial request will cause the server to create a TCP or UDP
`
`port to exchange the remainder of the data between the client and the server. The server
`
`then replies to the request of the client using this newly created port. The original port
`
`used by the client to connect to the server will never be used again during this data
`
`exchange.
`
`10
`
`One example of session tracking is TFfP (Trivial File Transfer Protocol), a
`
`version of the TCP/IP FfP protocol that has no directory or password capability. During
`
`the client/server exchange process of TFfP, a specific port (port number 69) is always
`
`used to initiate the packet exchange. Thus, when the client begins the process of
`
`communicating, a request is made to UDP port 69. Once the server receives this request, a
`
`15
`
`new port number is created on the server. The server then replies to the client using the
`
`new port. In this example, it is clear that in order to recognize TFTP; network monitor
`
`300 analyzes the initial request from the client and generates a signature for it. Monitor
`
`300 uses that signature to recognize the reply. Monitor 300 also analyzes the reply from
`
`the server with the key port information, and uses this to create a signature for monitoring
`
`20
`
`the remaining packets of this data exchange.
`
`Network monitor 300 can also understand the current state of particular
`
`connections in the network. Connection-oriented exchanges often benefit from state
`
`tracking to correctly identify the application. An example is the common TCP transport
`
`protocol that provides a reliable means of sending information between a client and a
`
`25
`
`server. When a data exchange is initiated, a TCP request for synchronization message is
`
`sent. This message contains a specific sequence number that is used to track an
`
`acknowledgement from the server. Once the server has acknowledged the synchronization
`
`request, data may be exchanged between the client and the server. When communication
`
`is no longer required, the client sends a finish or complete message to the server, and the
`
`30
`
`server acknowledges this finish request with a reply containing the sequence numbers
`
`from the request. The states of such a connection-oriented exchange relate to the various
`
`types of connection and maintenance messages.
`
`EX 1017 Page 52
`
`

`

`

`

`()
`
`46
`
`1.
`
`A client (CLIENT 3, 106 in FIG. 1) sends a TCP packet to SERVER 2
`
`(110 in FIG. 1) on port 111, with an RPC Bind Lookup Request
`
`(rpcBindLookup). TCP or UDP port 111 is always associated Sun RPC. This
`
`request specifies the program (as a program identifier), version, and might
`
`5
`
`specify the protocol (UDP or TCP).
`
`2.
`
`The server SERVER 2 (110 in FIG. 1) extracts the program identifier and
`
`version identifier from the request. The server also uses the fact that this
`
`packet came in using the TCP transport and that no protocol was specified, and
`
`thus will use the TCP protocol for its reply.
`
`10
`
`3.
`
`The server 110 sends a TCP packet to port number 111, with an RPC Bind
`
`Lookup Reply. The reply contains the specific port number (e.g., port number
`
`'port') on which future transactions will be accepted for the specific RPC
`
`program identifier (e.g., Program 'program') and the protocol (UDP or TCP)
`
`for use.
`
`15
`
`It is desired that from now on every time that port number 'port' is used, the
`
`packet is associated with the application program 'program' until the number 'port' no
`
`longer is to be associated with the program 'program'. Network monitor 300 by creating a
`
`flow-entry and a signature includes a mechanism for remembering the exchange so that
`
`future packets that use the port number 'port' will be associated by the network monitor
`
`20 with the application program 'program'.
`
`In addition to the Sun RPC Bind Lookup request and reply, there are other ways
`
`that a particular program-say
`
`'program'-might
`
`be associated with a particular port
`
`number, for example number 'port'. One is by a broadcast announcement of a particular
`
`association between an application service and a port number, called a Sun RPC
`
`25
`
`portMapper Announcement. Another, is when some server-say
`
`the same SERVER 2-
`
`replies to some client-say CLIENT !-requesting
`
`some portMapper assignment with a
`
`RPC portMapper Reply. Some other client-say CLIENT 2-might
`
`inadvertently see this
`
`request, and thus know that for this particular server, SERVER 2, port number 'port' is
`
`associated with the application service 'program'. It is desirable for the network monitor
`
`30
`
`300 to be able to associate any packets to SERVER 2 using port number 'port' with the
`
`application program 'program'.
`
`EX 1017 Page 54
`
`

`

`

`

`

`

`

`

`

`

`51
`
`large collections of flow signatures are kept in a lookup table in a least-to-highest order
`
`for the best spread of flow signatures and hashes.
`
`Thereafter, the client and server exchange a number of packets, e.g., represented
`
`by request packet 208 and response packet 209. The client 106 sends packets 208 that
`
`have a destination and source address S I and C 1, in a pair of fields 260 and 261. A field
`
`262 defines the protocol as "p2", and a field 263 defines the destination port number.
`
`Some network-server application recognition jobs are so simple that only a single
`
`state transition has to occur to be able to pinpoint the application that produced the packet.
`
`Others require a sequence of state transitions to occur in order to match a known and
`
`predefined climb from state-to-state.
`
`Thus the flow signature for the recognition of application "a2" is automatically set
`
`up by predefining what packet-exchange sequences occur for this example when a
`
`relatively simple Sun Microsystems Remote Procedure Call bind lookup request
`
`instruction executes. More complicated exchanges than this may generate more than two
`
`flow signatures and their corresponding states. Each recognition may involve setting up a
`complex state transition diagram to be traversed before a "final" resting state such as "st(
`
`in field 255 is reached. All these are used to build the final set of flow signatures for
`
`recognizing a particular application in the future.
`
`Embodiments of the present invention automatically generate flow signatures with
`
`the necessary recognition patterns and state transition climb procedure. Such comes from
`
`analyzing packets according to parsing rules, and also generating state transitions to
`
`search for. Applications and protocols, at any level, are recognized through state analysis
`
`of sequences of packets.
`
`Note that one in the art will understand that computer networks are used to
`
`connect many different types of devices, including network appliances such as telephones,
`
`"Internet" radios, pagers, and so forth. The term computer as used herein encompasses all
`
`such devices and a computer network as used herein includes networks of such
`
`computers.
`
`Although the present invention has been described in terms of the presently
`
`preferred embodiments, it is to be understood that the disclosure is not to be interpreted as
`
`EX 1017 Page 59
`
`

`

`

`

`

`

`

`

`55
`
`3.
`
`A packet monitor according to claim 1, wherein the parser subsystem includes a
`
`mechanism for building a hash from the selected portions, and wherein the hash is
`
`used by the lookup engine to search the flow-entry database, the hash designed to
`
`spread the flow-entries across the flow-entry database.
`
`5
`
`4.
`
`A packet monitor according to claim 1, further comprising:
`
`a compiler processor coupled to the parsing/extraction operations memory, the
`
`compiler processor configured to run a compilation process that includes:
`
`receiving commands in a high-level protocol description language that
`
`describe the protocols that. may be used in packets encountered by the
`
`10
`
`monitor, and
`
`translating the protocol description language commands into a plurality of
`
`parsing/extraction operations that are initialized into the parsing/extraction
`
`operations memory.
`
`5.
`
`A packet monitor according to claim 4, wherein the protocol description language
`
`1s
`
`commands also describe a correspondence between a set of one or more application
`
`programs and the state transition patterns/operations that occur as a result of
`
`particular conversational flow-sequences associated with an application program,
`
`wherein the compiler processor is also coupled to the state patterns/operations
`
`memory, and wherein the compilation process further includes translating the
`
`20
`
`protocol description language commands into a plurality of state patterns and state
`
`operations that are initialized into the state patterns/operations memory.
`
`6.
`
`A packet monitor according to claim 1, further comprising:
`
`a cache memory coupled to and between the lookup engine and the flow-entry
`
`database providing for fast access of a set of likely-to-be-accessed flow-entries from
`
`25
`
`the flow-entry database.
`
`7.
`
`A packet monitor according to claim 6, wherein the cache functions as a fully
`
`associative, least-recently-used cache memory.
`
`EX 1017 Page 63
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`65
`
`ABSTRA
`
`A monitor for and a method of examining packets passi
`
`through a connection point on
`
`~ a computer network. Each packets conforms to one o
`
`ore protocols. The method
`
`/
`
`'.
`~
`
`includes receiving a packet from a packet acquisitio device and performing one or more
`
`5
`
`parsing/extraction operations on the packet to ere e a parser record comprising a
`
`function of selected portions of the packet. Th parsing/extraction operations depend on
`
`one or more of the protocols to which the pa et conforms. The method further includes
`
`looking up a flow-entry database containi
`
`flow-entries for previously encountered
`
`conversational flows. The lookup uses t e selected packet portions and determining if
`
`1 o
`
`the packet is of an existing flow. If th packet is of an existing flow, the method
`
`classifies the packet as belonging to he found existing flow, and if the packet is of a new
`
`flow, the method stores a new flo -entry for the new flow in the flow-entry database,
`
`including identifying informatio for future packets to be identified with the new flow(cid:173)
`
`entry. For the packet of an exi
`
`·ng flow, the method updates the flow-entry of the
`
`15
`
`existing flow. Such updatin may include storing one or more statistical measures. Any
`
`stage of a f