`
`
`
`UNITED STATES DEPARTMENT OF COMMERCE
`
`United States Patent and Trademark Office
`
`October 17, 2018
`
`
`
`
`
`
`APPLICATION NUMBER:
`
`09/608,126
`
`FILING DATE:
`
`June 30, 2000
`
`PATENT NUMBER:
`
`6,839, 75]
`
`ISSUE DATE: January 04, 2005
`
`By Authority of the
`
`Under Secretary of Commerce for Intellectual Property
`and Director of the United States Patent and Trademark Offic
`
`e
`
`4y . W. MONTG
`
`ERY
`
`Certifying Officer
`
`
`
`
`
`
`
`
`
`
`
`’rfirflvaarivppgttzfiriiVH-trvvgttuavaaaatMmflrhpéptelt.9,335.6...
`1111!);
`
`NOAC Ex. 1018 Page 1
`
`
`
`
`
`
`
`
`
`
`-
`, UTS'. UTILITY PatentAppncatrori”
`
`
`FF-
`0.I.P.E.
`PATENT‘DATE
`
`
`scmnaofifim. Q :1.
`
`
`EXAMINén
`ii.
`‘m “A
`>SUBCLAS‘S
`'Ali-lTUNIT
`APPLICATION No.
`JCDNVPWOR
`
`
`
`
`
`
`
`
`
`
`I "
`4,,
`I
`"
`3" "i
`,
`.'
`.3
`z
`A"
`I
`'
`v
`'
`4/74!
`ewe-9
`09(608126 -
`D
`. Woven—r. V1 \.
`.
`7% .
`.
`_
`._
`_
`.
`.
`
`
`
`
`'
`*0. RL453§el'1:.,D’i:étz v
`I
`'
`X/ l
`E
`ij'SEgF-‘h: "Mai xner
`",
`’
`'
`g Qrwgir'ew Koppenhaver'
`CeriIfIcate
`_
`‘
`_
`.
`.
`_
`E
`.
`_
`~
`.
`‘ MAR 0 8
`05
`'lil-i—usinia ir'i'for'matvi'uri .fNr-rn 35+:
`'
`V.
`~'
`t---g.:l:.
`.--.
`..
`.
`_.
`.
`-
`'stat1st1;5'1h network mumitpr-rilmgrv.Em a
`"lo-ha f“ {Mirtélnlnég
`.
`-.
`.
`0 Correction
`
`Promo
`....-_-—..—.-A.--——»»TV__ «~-~—'--v—~-~
`,1;_:
`L
`.;.
`1:
`‘
`.
`.
`12,99
`
`
`
`
`g
`
`2"
`
`7-
`
`'
`
`4
`
`‘
`
`'
`
`v
`
`'
`
`’
`
`.
`
`.-
`
`=
`
`V,
`‘2
`:1
`
`
`
`i-
`
`i'
`;_
`(
`
`
`‘ “
`'
`f
`"
`
`‘
`
`J —-—-—
`
`---
`
`_.
`
`.
`
`a.
`
`,I
`
`.
`
`
`
`
`“1,.225. L -“;L.
`
`2',
`
`
`
`709
`
`'
`
`“
`
`"
`
`t
`
`.
`
`H
`
`,
`
`i
`
`,
`
`i
`
`I:
`l
`
`‘1.
`
`1
`
`II
`
`,7;
`
`:
`I
`
`l
`
`)‘K
`
`I
`
`1
`
`‘
`F
`
`“
`I
`
`
`
`.
`
`-
`
`j
`
`i
`
`-,
`
`~
`
`,
`.I
`i
`
`-
`
`.
`I
`‘ ORIGINAL ‘
`.
`_CLAss
`7 o ‘1.
`
`.
`
`x.
`-'
`
`‘
`
`A
`
`'
`
`v
`'
`
`i
`.
`.
`
`I
`a
`;
`I
`
`L'.
`
`,
`
`:5
`i”
`,
`l.
`
`I
`
`
`
`.
`
`;
`
`i
`I:
`.
`i
`
`Ill
`-
`
`|
`.'
`I
`'
`
`‘
`
`j
`'3
`.‘
`3
`
`TERMINAL
`. D'§CLA'MEB
`
`,
`’
`Sheets 9M9;
`
`i3 Thetenn ofthispatenl
`subsequent to
`has been disciaimed‘.‘
`
`'
`
`:
`
`'
`
`’
`(date)
`
`_
`3'
`-
`'i
`j l
`
`'
`'
`-
`'
`
`_ CLAIMSAITLOWED-v_
`* Total claims 3
`
`Print Clalm‘forOG. "
`
`,
`
`Nance o'eALLOWANcé MAILEDf
`
`"
`
`7
`
`'
`
`.
`D The tern; of this patent shall
`not extend beyondlhe expiration’dale
`of US Patent. No.
`‘
`'
`5
`*
`
`, 0.
`V.
`l
`'l
`th
`“‘Thet
`ermIna _‘___.mon so
`5 J
`mil: patent have been disclaimed.
`.
`
`_
`
`'
`
`,
`(Primary Examiner)
`
`'
`
`L.
`
`V
`.
`v
`(Legal instmments Examiner)
`
`‘
`
`Date Paid.
`I AmountDue'
`>
`,-
`flls’so-ffi-
`6 23 oqr_ Jm .
`‘
`.
`W
`.I ISSUE-BATCH NUMBER 11-.
`=--”
`~
`4
`.
`.
`
`‘
`
`i»
`
`.
`
`.
`
`,
`
`H
`
`.
`
`.
`
`,
`
`
`
`
`"i
`:'\
`Vl
`
`
`
`
`
`
`I‘.'
`
`
`
`
`
`
`,
`
`I
`i
`I
`I
`
`
`
`
`
`
`
`
`,1
`E
`
`.
`
`,'
`
`|.
`.
`.-
`I
`
`-.
`._
`.
`.
`t
`._
`.
`WARNING:
`_ The information disclosed herein may be reslncted. Unauthorized disclosure may-be prohibited by the United States Code Title 35. Sections 122. 181 and 368.
`Possession oulside the us. Patent & Trademark Office is restricted to authorized employees and contractors only.
`Form PTO-436A
`.
`_
`(RHYME,
`.
`FILED WITH.
`|:] DISK (CFiF) E] FICHE C] CD ROM
`.
`(Anached In pocket on right Inside flap)
`ISSUE FEE IN FiLE- ‘
`
`
`
`‘
`.
`.
`}
`
`:,
`Iv
`
`.
`
`_
`
`I’FACE) ‘
`
`NOAC Ex. 1018 Page 2
`
`
`
`Page 1 of 1
`
`
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`COMMISSIONER FOR PATENTS
`UNITED STATES PATENT AND TRADEMARK OFFICE
`WASHINGTON. D.C. ZOZSI
`www.uspto.gov
`
`.
`
`‘
`
`s||||||||l||||||||ll|l|||||l|||ll||||||||l|l|lllllllllllllllllllllllll
`Bib Data Sheet
`
`FILING DATE I
`
`_
`
`06/30/2000
`RULE
`_
`
`CLASS
`709
`
`GROUP ART UNIT
`2755
`
`ATTORNEY
`DOCKET NO.
`APPT-001-3
`
`SERBIQIébhélIIIZIISBER
`’
`APPLICANTS
`
`Russell 8. Dietz, San Jose, CA ;
`Joseph R. Maixner. Aptos, CA ;
`Andrew A. Koppenhaver, Fairfax, VA;
`
`,;
`
`H: CONTINUING DATA ****i**i***‘ktktktiiktktki
`THIS APPLN CLAIMS BENEFIT OF 60/141,903 06/30/1999
`
`** FOREIGN APPLICATIONS ******i*************
`
`IF REQUIRED, FOREIGN FILING LICENSE
`EiRANTED ** 08/21/2000
`,
`F'Wnpfioritydaimed
`D yes ‘1 ”°
`fif§350119‘a'd’°°”d"‘°”5 U yes '2] no D Metafier
`Allowance ,
`r'erified and
`’ \M/
`Examiner's Sinature
`cknowleded ,
`
`Initials
`
`DDRESS
`
`Dov Rosenfeld
`
`Suite-2
`
`5507 College Avenue
`ikland ,CA 94618
`ITLE
`
`—
`SHEETS
`STATE OR
`COUNTRY DRAWING
`CA ,
`
`
`
`. TOTAL
`CLAIMS
`21
`
`INDEPENDEN
`CLAIMS
`2
`
`Rte—using information from data transactions for maintaining statistics in network monitoring
`
`FILING FEE FEES: Authority has been given in Paper
`RECEIVED No.
`to charge/credit DEPOSIT ACCOUNT
`858
`.___for following:
`
`CI 1.17 Fees ( Processing Ext. of
`time I
`D 1 18 Fees ( Issue)
`
`D All Fees
`
`Cl 1.16 Fees ( Filing)
`
`
`
`
`CI Credit
`
`file://C:\APPS\PreExarn\correspondence\1_A.xml
`
`12/ 1 4/00
`
`my.-.,
`
`NOAC EX. 1018 Page 3
`
`NOAC Ex. 1018 Page 3
`
`
`
`Our Ref./Docket No.: APPT-001-3
`
`RE-USING INFORMATION FROM DATA TRANSACTIONS FOR MAINTAINING
`
`STATISTICS IN NETWORK MONITORING
`
`
`
`miifiLiI}
`
`2'.‘I.i!I:I!1;:im
`
`Inventor(s):
`
`DlETZ, Russell S.
`
`San Jose, CA
`
`MAIXNER, Joseph R.
`Aptos, CA
`
`KOPPENHAVER, Andrew A.
`
`Fairfax, VA
`
`‘Certificate of Mailing under 37 CFR 1.10
`
`I hereby certify that this application and all attachments are being deposited with the United States Postal Service as Express Mail
`(Express Mail Label: EI417961927US in an envelope addressed to Box Patent Application, Assistant Commissioner for Patents,
`Washington, D.
`. 20231 on.
`:
`<9 m Signed:
`Name.
`
`ov Rosenfeld, Reg. NO. 38687
`
`NOAC Ex. 1018 Page 4
`
`
`
`l
`
`RE-USING INFORMATION FROM DATA TRANSACTIONS FOR
`MAINTAINING STATISTICS IN NETWORK MONITORING
`
`CROSS-REFERENCE TO RELATED APPLICATION
`
`This application claims the benefit of U.S. Provisional Patent Application Serial N0.:
`
`60/141,903 for METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A
`
`NETWORK to inventors Dieti, et al., filed June 30, 1999, the contents of which are
`
`incorporated herein by reference.
`
`
`
`II
`
`munis
`
`nunuI;1}‘Im
`
`This application is related to the following U.S. patent applications, each filed
`
`concurrently with the present application, and each assigned to Apptitude, Inc., the
`
`10
`
`assignee of the present invention:
`
`U.S. Patent Application Serial No.
`
`0 GI / 50% l7ff‘for METHOD AND APPARATUS FOR
`
`MONITORING TRAFFIC IN A NETWORK, to inventors Dietz, et al., filed June 30,
`
`2000, Attorney/Agent Reference Number APPT-OOl-l, and incorporated herein by
`
`' reference.
`
`.15
`
`U.S. Patent Application Serial No. 09 / MI I7jfor PROCESSING PROTOCOL
`
`SPECIFIC INFORMATION IN PACKETS SPECIFIED BY A PROTOCOL
`
`DESCRIPTION LANGUAGE, to inventors Koppenhaver, et al., filed June 30, 2000,
`
`Attorney/Agent Reference Number APPT—001—2, and incorporated herein by
`
`reference.
`
`20
`
`U.S. Patent Application Serial No. 04 mag Wfor ASSOCIATIVE CACHE
`
`STRUCTURE FOR LOOKUPS AND UPDATES OF FLOW RECORDS IN A
`
`NETWORK MONITOR, to inventors Sarkissian, et al., filed June 30, 2000,
`
`Attorney/Agent Reference Number APPT-001-4, and incorporated herein by
`
`reference.
`
`25
`
`U.S. Patent Application Serial No.
`
`SE] If”;3
`
`Z 6
`
`for STATE PROCESSOR FOR
`
`PATTERN MATCHING IN A NETWORK MONITOR DEVICE, to inventors
`
`Sarkissian, et al., filed June 30, 2000, Attorney/Agent Reference Number APPT—OOI-
`
`5, and incorporated herein by reference.
`
`NOAC EX. 1018 Page 5
`
`NOAC Ex. 1018 Page 5
`
`
`
`9
`
`3
`
`
`
`u...”ruinit:Iml'ii"1:umn"muII3|
`
`
`
`‘Iml!‘MI!
`
`if"?!Ma”!5353'
`
`FIELD OF INVENTION
`
`The present invention relates to computer networks, specifically to the real—time
`
`elucidation of packets communicated within a data network, including classification
`
`according to protocol and application program.
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document contains material that is
`
`subject to copyright protection. The copyright owner has no objection to the facsimile
`
`reproduction by anyone of the patent document or the patent disclosure, as it appears in
`
`the Patent and Trademark Office patent file or records, but otherwise reserves all
`
`10
`
`copyright rights whatsoever.
`
`BACKGROUND
`
`There has long been a need for network activity monitors. This need has become
`
`especially acute, however, given the recent popularity of the Internet and other
`
`15
`
`20
`
`25
`
`interconnected networks. In particular, there is a need for a real—time network monitor
`
`that can provide details as to the application programs being used. Such a monitor should
`
`enable non-intrusive, remote detection, characterization, analysis, and capture of all
`
`information passing through any point on the network (i.e., of all packets and packet
`
`streams passing through any location in the network). Not only should all the packets be
`
`detected and analyzed, but for each of these packets the network monitor should
`
`determine the protocol (e. g., http, ftp, H.323, VPN, etc.), the application/use within the
`
`protocol (e. g., voice, video, data, real-time data, etc.), and an end user’s pattern of use
`
`within each application or the application context (e.g., options selected, service
`
`delivered, duration, time of day, data requested, etc.). Also, the network monitor should
`
`not be reliant upon server resident information such as log files. Rather, it should allow a
`
`user such as a network administrator or an Internet service provider (ISP) the means to
`
`measure and analyze network activity objectively; to customize the type of data that is
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`of network problems.
`
`a)?“
`Related and incorporated by reference US. Patent application fl for
`
`3O
`
`METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A NETWORK, to
`
`NOAC EX. 1018 Page 6
`
`NOAC Ex. 1018 Page 6
`
`
`
`
`
`Q
`
`'3
`
`inventors Dietz, et a1, Attomey/Agent Docket APPT—OOl—l, describes a network monitor
`
`that includes carrying out protocol specific operations on individual packets including
`
`extracting information from header fields in the packet to use for building a signature for
`
`identifying the conversational flow of the packet and for recognizing future packets as
`
`belonging to a previously encountered flow. A parser subsystem includes a parser for
`
`recognizing different patterns in the packet that identify the protocols used. For each
`
`protocol recognized, a slicer extracts important packet elements from the packet. These
`
`form a signature (i.e., key) for the packet. The slicer also preferably generates a hash for
`
`rapidly identifying a flow that may have this signature from a database of known flows.
`
`The flow signature of the packet, the hash and at least some of the payload are
`
`passed to an analyzer subsystem. In a hardware embodiment, the analyzer subsystem
`
`includes a unified flow key buffer (UFKB) for receiving parts of packets from the parser
`
`subsystem and for storing signatures in process, a lookup/update engine (LUE) to lookup
`
`a database of flow records for previously encountered conversational flows to determine
`
`whether a signature is from an existing flow, a state processor (SP) for performing state
`
`processing, a flow insertion and deletion engine (FIDE) for inserting new flows into the
`
`database of flows, a memory for storing the database of flows, and a cache for speeding
`
`up access to the memory containing the flow database. The LUE, SP, and FIDE are all
`
`coupled to the UFKB, and to the cache.
`
`Each flow~entry includes one or more statistical measures, e. g., the packet count
`
`related to the flow, the time of arrival of a packet, the time differential.
`
`In the preferred hardware embodiment, each of the LUE, state processor, and
`
`FIDE operate independently from the other two engines. The state processor performs
`
`one or more operations specific to the state of the flow.
`
`It is advantageous to collect statistics on packets passing through a point in a
`
`network rather than to simply count each and every packet. By maintaining statistical
`
`measures in the flow-entries related to a conversational flow, embodiments of the present
`
`invention enable specific metrics to be collected in real~time that otherwise would not be
`
`10
`
`15
`
`20
`
`25
`
`possible. For example, it is desirable to maintain metrics related to bi-directional
`
`30
`
`conversations based on the entire flow for each exchange in the conversation. By
`
`maintaining the state of flow, embodiments of the present invention also enable certain
`
`NOAC EX. 1018 Page 7
`
`NOAC Ex. 1018 Page 7
`
`
`
`o
`
`'3
`
`metrics related to the states of flows to be determined.
`
`Most prior-art network traffic monitors that use statistical metrics collect only
`
`end—point and end-of-session related statistics. Examples of such commonly used metrics
`
`include packet counts, byte counts, session connection time, session timeouts, session
`
`and transport response times and others. All of these deal with events that can be directly
`
`related to an event in a single packet. These prior-art systems cannot collect some
`
`important performance metrics that are related to a complete sequence of packets of a
`
`flow or to several disjointed sequences of the same flow in a network.
`
`Time based metrics on application data packets are important. Such metrics could
`
`be determined if all the timestamps and related data could be stored and forwarded for
`
`later analysis. However when faced with thousands or millions of conversations per
`
`second on ever faster networks, storing all the data, even if compressed, would take too
`
`much processing, memory, and manager down load time to be practical.
`
`Thus there is a need for maintaining and reporting time-base metrics from
`
`statistical measures accumulated from packets in a flow.
`
`Network data is properly modeled as a population and not a sample. Thus, all the
`
`data needs to be processed. Because of the nature of application protocols, just sampling
`
`some of the packets may not give good measured related to flows. Missing just one
`
`critical packet, such as one the specified an additional port that data will be transmitted
`
`on, or what application will be run, can cause valid data to be lost.
`
`Thus there is also a need for maintaining and reporting time-base metrics from
`
`statistical measures accumulated from every packet in a flow.
`
`There also is a need to determine metrics related to a sequence of events. A good
`
`example is relative jitter. Measuring the time from the end of one packet in one direction
`
`to another packet with the same signature in the same direction collects data that relates
`
`normal jitter. This type of jitter metric is good for measuring broad signal quality in a
`
`packet network. However, it is not specific to the payload or data item being transported
`
`in a cluster of packets.
`
`Using the state processing described herein, because the state processor can
`
`..nI}y“1:it'nmytin-nn1|
`
`It...“1,.
`
`”ml!j)I!
`
`HHI]llllll5]“:
`
`10
`
`15
`
`20
`
`25
`
`NOAC EX. 1018 Page 8
`
`NOAC Ex. 1018 Page 8
`
`
`
`3
`
`3
`
`search for specific data payloads, embodiments of monitor 300 can be programmed to
`
`collect the same jitter metric for a group of packets in a flow that are all related to a
`
`specific data payload. This allows the inventive system to provide metrics more focused
`
`on the type of quality related to a set of packets. This in general is more desirable than
`
`metrics related to single packets when evaluating the performance of a system in a
`
`network.
`
`Specifically, the monitor system 300 can be programmed to maintain any type of
`
`metric at any state of a conversational flow. Also the system 300 can have the actual
`
`statistics programmed into the state at any point. This enables embodiments of the
`
`monitor system to collect metrics related to network usage and performance, as well as
`
`metrics related to specific states or sequences of packets.
`
`Some of the specific metrics that can be collected only with states are events
`
`related to a group of traffic in one direction, events related to the status of a
`
`communication sequence in one or both directions, events related to the exchange of
`
`packets for a specific application in a specific sequence. This is only a small sample of
`
`the metrics that requires an engine that can relate the state of a flow to a set of metrics.
`
`In addition, because the monitor 300 provides greater visibility to the specific
`
`application in a conversation or flow, the monitor 300 can be programmed to collect
`
`metrics that may be specific to that type of application or service. In other word, if a flow
`
`is for an Oracle Database server, an embodiment of monitor 300 could collect the
`
`number of packets required to complete a transaction. Only with both state and
`
`application classification can this type of metric be derived from the network.
`
`Because the monitor 300 can be programmed to collect a diverse set of metrics,
`
`the system can be used as a data source for metrics required in a number of
`
`environments. In particular, the metrics may be used to monitor and analyze the quality
`
`and performance of traffic flows related to a specific set of applications. Other
`
`implementation could include metrics related to billing and charge—back for specific
`
`traffic flow and events with the traffic flows. Yet other implementations could be
`
`programmed to provide metrics useful for troubleshooting and capacity planning and
`
`related directly to a focused application and service.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`NOAC EX. 1018 Page 9
`
`"ii
`iii
`
`
`
`
`'“Esta”;3.:rt
`
`um.,
`
`NOAC Ex. 1018 Page 9
`
`
`
`
`
`SUMMARY
`
`Another aspect of the invention is determining quality of service metrics based on
`
`each and every packet. A method of and monitor apparatus for analyzing a flow of
`
`packets passing through a connection point on a computer network are disclosed that
`
`may include such quality of service metrics. The method includes receiving a packet
`
`from a packet acquisition device, and looking up a flow-entry database containing flow—
`
`entries for previously encountered conversational flows. The looking up to determine if
`
`the received packet is of an existing flow. Each and every packet is processed. If the
`
`packet is of an existing flow, the method updates the flow-entry of the existing flow,
`
`10
`
`including storing one or more statistical measures kept in the flow-entry. If the packet is
`
`of a new flow, the method stores a new flow-entry for the new flow in the flow—entry
`
`database, including storing one or more statistical measures kept in the flow-entry. The
`
`statistical measures are used to determine metrics related to the flow. The metrics may be
`
`base metrics from which quality of service metrics are determined, or may be the quality
`
`15
`
`of service metrics.
`
`20
`
`25
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Although the present invention is better understood by referring to the detailed
`
`preferred embodiments, these should not be taken to limit the present invention to any
`
`specific embodiment because such embodiments are provided only for the purposes of
`
`explanation. The embodiments, in turn, are explained with the aid of the following
`
`figures.
`
`FIG. 1 is a functional block diagram of a network embodiment of the present
`
`invention in which a monitor is connected to analyze packets passing at a connection
`
`point.
`
`FIG. 2 is a diagram representing an example of some of the packets and their
`
`formats that might be exchanged in starting, as an illustrative example, a conversational
`
`flow between a client and server on a network being monitored and analyzed. A pair of
`
`flow signatures particular to this example and to embodiments of the present invention is
`
`also illustrated. This represents some of the possible flow signatures that can be
`
`
`
`m.“u
`an”r
`
`H
`
`.5“a",..
`
`NOAC EX. 1018 Page 10
`
`NOAC Ex. 1018 Page 10
`
`
`
`Q
`
`:1)
`
`
`
`‘3!:”u
`
`"-Lirp11
`
`
`
`if1;5:up1.1:|---
`
`generated and used in the process of analyzing packets and of recognizing the particular
`
`server applications that produce the discrete application packet exchanges.
`
`FIG. 3 is a functional block diagram of a process embodiment of the present
`
`invention that can operate as the packet monitor shown in FIG. 1. This process may be
`
`implemented in software or hardware.
`
`FIG. 4 is a flowchart of a high-level protocol language compiling and
`
`optimization prOCess, which in one embodiment may be used to generate data for
`
`monitoring packets according to versions of the present invention.
`
`FIG. 5 is a flowchart of a packet parsing process used as part of the parser in an
`
`embodiment of the inventive packet monitor.
`
`FIG. 6 is a flowchart of a packet element extraction process that is used as part of
`
`the parser in an embodiment of the inventive packet monitor.
`
`FIG. 7 is a flowchart of a flow—signature building process that is used as part of
`
`the parser in the inventive packet monitor.
`
`FIG. 8 is a flowchart of a monitor lookup and update process that is used as part
`
`of the analyzer in an embodiment of the inventive packet monitor.
`
`FIG. 9 is a flowchart of an exemplary Sun Microsystems Remote Procedure Call
`
`application than may be recognized by the inventive packet monitor.
`
`FIG. 10 is a functional block diagram of a hardware parser subsystem including
`
`the pattern recognizer and extractor that can form part of the parser module in an
`
`embodiment of the inventive packet monitor.
`
`FIG. 11 is a functional block diagram of a hardware analyzer including a state
`
`processor that can form part of an embodiment of the inventive packet monitor.
`
`FIG. 12 is a functional block diagram of a flow insertion and deletion engine
`
`process that can form part of the analyzer in an embodiment of the inventive packet
`
`monitor.
`
`FIG. 13 is a flowchart of a state processing process that can form part of the
`
`analyzer in an embodiment of the inventive packet monitor.
`
`10
`
`15
`
`20
`
`25
`
`NOAC EX. 1018 Page 11
`
`NOAC Ex. 1018 Page 11
`
`
`
`
`
`'3
`
`FIG. 14 is a simple functional block diagram of a process embodiment of the
`
`present invention that can operate as the packet monitor shown in FIG. 1. This process
`
`may be implemented in software.
`
`FIG. 15 is a functional block diagram of how the packet monitor of FIG. 3 (and
`
`FIGS. 10 and 11) may operate on a network with a processor such as a microprocessor.
`
`FIG. 16 is an example of the top (MAC) layer of an Ethernet packet and some of
`
`the elements that may be extracted to form a signature according to one aspect of the
`
`invention.
`
`10
`
`15
`
`III"'I_\IIII
`
`
`
`
`
`
`y)3grII1''ngin-
`
`FIG. 17A is an example of the header of an Ethertype type of Ethernet packet of
`
`FIG. 16 and some of the elements that may be extracted to form a signature according to
`
`one aspect of the invention.
`
`FIG. 17B is an example of an IP packet, for example, of the Ethertype packet
`
`shown in FIGs. 16 and 17A, and some of the elements that may be extracted to form a
`
`signature according to one aspect of the invention.
`
`FIG. 18A is a three dimensional structure that can be used to store elements of
`
`the pattern, parse and extraction database used by the parser subsystem in accordance to
`
`one embodiment of the invention.
`
`FIG. 18B is an alternate form of storing elements of the pattern, parse and
`
`extraction database used by the parser subsystem in accordance to another embodiment
`
`20
`
`of the invention.
`
`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
`
`25
`
`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
`
`NOAC EX. 1018 Page 12
`
`NOAC Ex. 1018 Page 12
`
`
`
`*9:
`
`Zing:3111"magpm“I!‘u
`
`.ml-
`n"
`
`~1221a:
`
`llllllfl“
`
`It:111
`
`o
`
`3
`
`102 that communicates packets (e. g., IP datagrams) between various computers, for
`
`example 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 (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 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
`
`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 may need to be parsed then analyzed in the context of various protocols, for
`
`example, the transport through the application session layer protocols for packets of a
`
`type conforming to the ISO layered network model.
`
`Communication protocols are layered, which is also referred to as a protocol
`
`stack. The ISO (International Standardization Organization) has defined a general model
`
`that provides a framework for design of communication protocol layers. This model,
`
`shown in table form below, serves as a basic reference for understanding the
`
`functionality of existing communication protocols.
`
`NOAC EX. 1018 Page 13
`
`NOAC Ex. 1018 Page 13
`
`
`
`
`=.
`
`
`
`10
`
`ISO MODEL
`
`Application
`
`
`
`Telnet, NFS, Novell NCP, HTTP,
`
`H.323
`
`Data Link
`
`Network Interface Card (Hardware
`
`Interface). MAC layer
`
`7
`
`5
`
`4
`
`3
`
`2
`
`
`
`
`
`
`
`
`Physical
`
`Ethernet, Token Ring, Frame Relay,
`
`
`
`
`ATM, T1 (Hardware Connection)
`
`Different communication protocols employ different levels of the ISO model or
`
`may use a layered model that is similar to but which does not exactly conform to the ISO
`
`model. A protocol in a certain layer may not be visible to protocols employed at other
`
`layers. For example, an application (Level 7) may not be able to identify the source
`
`computer for a communication attempt (Levels 2—3).
`
`In some communication arts, the term “frame” generally refers to encapsulated
`
`data at OSI layer 2, including a destination address, control bits for flow control, the data
`
`or payload, and CRC (cyclic redundancy check) data for error checking. The term
`
`“packet” generally refers to encapsulated data at OSI layer 3. In the TCP/IP world, the
`
`term “datagram” is also used. In this specification, the term “packet” is intended to
`
`encompass packets, datagrams, frames, and cells. In general, a packet format or frame
`
`format refers to how data is encapsulated with various fields and headers for
`
`transmission across a network. For example, a data packet typically includes an address
`
`destination field, a length field, an error correcting code (ECC) field, or cyclic
`
`redundancy check (CRC) field, as well as headers and footers to identify the beginning
`
`LII
`
`10
`
`15
`
`NOAC EX. 1018 Page 14
`
`NOAC Ex. 1018 Page 14
`
`
`
`
`
`11
`
`and end of the packet. The terms “packet format” and “frame format,” also referred to as
`
`“cell format,” are generally synonymous.
`
`Monitor 108 looks at every packet passing the connection point 121 for analysis.
`
`However, not every packet carries the same information useful for recognizing all levels
`
`of the protocol. For example, in a conversational flow associated with a particular
`
`application, the application will cause the server to send a type-A packet, but so will
`
`another. If, though, the particular application program always follows a type—A packet
`
`with the sending of a type—B packet, and the other application program does not, then in
`
`order to recognize packets of that application’s conversational flow, the monitor can be
`
`available to recognize packets that match the type-B packet to associate with the type—A
`
`packet. If such is recognized after a type-A packet, then the particular application
`
`program’s conversational flow has started to reveal itself to the monitor 108.
`
`Further packets may need to be examined before the conversational flow can be
`
`identified as being associated with the application program. Typically, monitor 108 is
`
`simultaneously also in partial completion of identifying other packet exchanges that are
`
`parts of conversational flows associated with other applications. One aspect of monitor
`
`108 is its ability to maintain the state of a flow. The state of a flow is an indication of all
`
`previous events in the flow that lead to recognition of the content of all the protocol
`
`levels, e. g., the ISO model protocol levels. Another aspect of the invention is forming a
`
`signature of extracted characteristic portions of the packet that can be used to rapidly
`
`identify packets belonging to the same flow.
`
`In real-world uses of the monitor 108, the number of packets on the network 102
`
`passing by the monitor 108’s connection point can exceed a million per second.
`
`Consequently, the monitor has very little time available to analyze and type each packet
`
`and identify and maintain the state of the flows passing through the connection point.
`
`The monitor 108 therefore masks out all the unimportant parts of each packet that will
`
`not contribute to its classification. However, the parts to mask-out will change with each
`
`packet depending on which flow it belongs to and depending on the state of the flow.
`
`10
`
`15
`
`2O
`
`25
`
`The recognition of the packet type, and ultimately of the associated application
`
`30
`
`programs according to the packets that their executions produce, is a multi-step process
`
`within the monitor 108. At a first level, for example, several application programs will
`
`NOAC EX. 1018 Page 15
`
`
`
`H‘l-n!‘l‘11”ml!Mm]:111‘.
`
`(wwxv.m
`
`
`
`
`n)12|nHll
`
`
`
`
`
`”31‘1"“'W‘mfivfli"~.’Ts‘!3‘."'sf€a"\-3<JV
`
`NOAC Ex. 1018 Page 15
`
`
`
`o
`
`«.3
`
`12
`
`all produce a first kind of packet. A first “signature” is produced from selected parts of a
`
`packet that will allow monitor 108 to identify efficiently any packets that belong to the
`
`
`
`$5.;«W-k‘.2,.x_.
`
`same flow. In some cases, that packet type may be sufficiently unique to enable the
`
`monitor to identify the application that generated such a packet in the conversational
`
`flow. The signature can then be used to efficiently identify all future packets generated in
`
`traffic related to that application.
`
`
`
`
`
`irkmit:f~-'.~
`~*1.t.«as;
`
`
`
`...i)‘I
`
`
`:1!limil...
`.zvuuu‘
`
`
`
`u'mil"miln"i:.........
`
`,9
`
`3%
`if
`
`
`
`10
`
`15
`
`20
`
`25
`
`In other cases, that first packet only starts the process of analyzing the
`
`conversational flow, and more packets are necessary to identify the associated
`
`application program. In such a case, a subsequent packet of a second type—but that
`
`potentially belongs to the same conversational flow—is recognized by using the
`
`signature. At such a second level, then, only a few of those application programs will
`
`have conversational flows that can produce such a second packet type. At this level in
`
`the process of classification, all application programs that are not in the set of those that
`
`lead to such a sequence of packet types may be excluded in the process of classifying the
`
`conversational flow that includes these two packets. Based on the known patterns for the
`
`protocol and for the possible applications, a signature is produced that allows recognition
`
`of any future packets that may follow in the conversational flow.
`
`It may be that the application is now recognized, or recognition may need to
`
`proceed to a third level of analysis using the second level signature. For each packet,
`
`therefore, the monitor parses the packet and generates a signature to determine if this
`
`signature identified a previously encountered flow, or shall be used to recognize future
`
`packets belonging to the same conversational flow. In real time, the packet is further
`
`analyzed in the context of the sequence of previously encountered packets (the state), and
`
`of the possible future sequences such a past sequence may generate in conversational
`
`flows associated with different applications. A new signature for recognizing future
`
`packets may also be generated. This process of analysis continues until the applications
`
`are identified. The last generated signature may then be used to efficiently recognize
`
`future packets associated with the same conversational flow. Such an arrangement makes
`
`it possible for the monitor 108 to cope with millions of packets per second that must be
`
`30
`
`inspected.
`
`NOAC EX. 1018 Page 16
`
`NOAC Ex. 1018 Page 16
`
`
`
`Q
`
`:3
`
`13
`
`Anothe