`
` ScSteeSeteeSeLSeneesbeebeesseneccensRSRSARGERRREHAKERUDESOWESooeeee
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IW 7696177
`
`
`
`R
`
`ener
`ESEND
`
`S$) SHAT, CO
`
`ME:
`
`UNITED STATES DEPARTMENT OF COMMERCE
`
`United States Patent and Trademark Office
`
`October 17, 2018
`
`RECORDSOF THIS OFFICE OF THE FILE WRAPPER AND CONTENTS
`
`PATENT NUMBER:
`
`APPLICATION NUMBER:
`
`09/608,126
`June 30, 2000
`
`FILING DATE:
`
`6,839,751
`ISSUE DATE: January 04, 2005
`
`By Authority of the
`UnderSecretary of Commercefor Intellectual Property
`and Director of the United States Patent and Trademark Offic
`
`e
`
`YW Meda
`
`~» MONTG
`
`ERY
`
`Certifying Officer
`
`Pp coe"
`
`
`
`
`
`
`
`NOAC Ex. 1018 Page 1
`
`
`
`
`
`
`
`

`

`
`
`PATENT DATE
`
`
`
`
`JAN G&G
`
`
`
`APPLIGATIONNO,
`
`
`EXAVINER
`7aeees1 26 ;
`Tie:yee: Vetd
`
`
` Rusell. Digtz.
` wm
`a7
`v
`2
`Joseph Maixner
`~ Ae
`:
`a
`‘
`S Andrew Koppenhaver
`-
`:
`.
`oe
`
`
`g Certificate—-Andre Ke | | a
`
`
`
`
`te Be
`:
`oe
`|
`i
`i.
`4 Ree-using. iriformation From data transactions for maith98,2005.
`nT
`
`“statistics: in networ k monitoring |
`:
`Of Correction -a md
`
`
`
`
`
` -
`
`
`(1 Thetom ofthis patent
`subsequent to
`has beendisclaimed.
`~
`
`:
`Oo The term ofthis patent shall
`not exteria, beyond.the ponedate
`of U.S Patent. No.
`:
`
`+|2 Amount mse Date Paid.
`(PrimaryExaminer).
`ate) os
`| *.
`6 23oFJem
`
`go:
`2
`.
`:
`.. ISSUEBATCH NUMBER...
`
`>| The terminal ___.months of
`:
`:
`
`inis patent have beendisclaimed. ”
`
`5
`,
`:
`WARNING:
`_|The information disclosed herein may be restricted. Unauthorizeddisclosure may-be prohibited by the United States Code Tile 235, Sections 122, 181 and 368.
`Possession outside the U.S. Ratent & Trademark Otficeis restricted to authorized employees and contractors only.
`
`fameto#304
`FILED wiTH: [[] DISK (CRF)
`
`ISSUE FEE IN FILE.
`
`
`
`
`‘|enna]
`Lcwass
`ait rece
`|ciass |
`|
`pena
`
`|[Tnvemnronacassmesron|—_ I
`iceTaeAG
`cs E
`ae
`ei.
`-———
`
`TERMINAL
`DISCLAIMER
`
`(date)
`
`
`:
`:
`-
`"(Assistant Examiner).
`
`:
`;
`(Lagat Instrumalits Examiner}
`
`(FACE)
`
`[_]FICHE []cp-RoM |
`(AttachedIn pocket on rightinside flap)
`|
`
`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. 20231
`www.uspto.gov
`
`TO
`Bib Data Sheet
`
` FILING DATE
`
`cass
`9
`
`GROUP ART UNIT
`798
`
`ATTORNEY
`
`DOCKET NO.
`APPT-001-3
`
`06/30/2000
`RULE
`
`SERIALNUMBER
`‘
`APPLICANTS
`Russell S. Dietz, San Jose, CA;
`Joseph R. Maixner, Aptos, CA;
`Andrew A. Koppenhaver, Fairfax, VA ;
`
`?
`
`dk CONTINUING DATA KEKEREREKERERREREERERERERK
`THIS APPLN CLAIMS BENEFIT OF 60/141,903 06/30/1999
`
`ae FOREIGN APPLICATIONS RARRRRRKRRERRRERRARER
`
`IF REQUIRED, FOREIGN FILING LICENSE
`SIRANTED ** 08/21/2000
`.
`
`, TOTAL
`SHEETS
`STATEOR|
`DD yes no
`ForeignPriority claimed
`
`
`£5 USC 119 (2-4) conditions COUNTRY| DRAWING|CLAIMSLY yos [2 no OD set after
`met
`Allowance —
`CA
`‘erified and
`“Ws
`21
`Acknowledged
`Examiner's Signature
`DDRESS
`
`Initials
`
`—
`
`
`
`Dov Rosenfeld
`Suite2
`5507 College Avenue
`Oakland ,CA 94618
`ITLE
`
`Re-using information from data transactions for maintaining statistics in network monitoring
`
`
`
`
`
`OQ all Fees
`C) 1.16 Fees( Filing )
`U 1.17 Fees ( Processing Ext. of
`
`LI 1.18 Fees ( Issue )
`C) other
`
`QI) credit
`
`FILING FEE |FEES: Authority has been given in Paper
`RECEIVED jNo.
`to charge/credit DEPOSIT ACCOUNT
`.
`for
`following:
`858
`for tolowing
`
`file://C:\APPS\PreExam\correspondence\!_A.xml
`
`12/14/00
`
`WEmae
`
`NOACEx. 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
`
`
`
`teererehelldtHimee
`
`eyde
`
`Inventor(s):
`
`DIETZ, Russell S.
`San Jose, CA
`
`MAIXNER,Joseph R.
`Aptos, CA
`
`KOPPENHAVER,Andrew A.
`Fairfax, VA
`
`kL
`
`‘Certificate of Mailing under 37 CFR 1.10
`Therebycertify that this application andall attachments are being deposited with the United States Postal Service as Express Mail
`(Express Mail Label: EI417961927USin an envelope addressed to Box Patent Application, Assistant Commissioner for Patents,
`Washington, D.C. 20231 on.
`©, LO00
`
`Name~Dov Rosenfeld, Reg. No. 38687
`
`Signed:
`
`NOAC Ex. 1018 Page 4
`
`

`

`1
`
`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 No.:
`
`60/141,903 for METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A
`NETWORKto inventorsDietz, et al., filed June 30, 1999, the contents of which are
`
`incorporated herein by reference.
`
`
`HapehPeseaH
`
`“ya
`teethipsaab
`
`Hyey
`
`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. 64 / $0827for METHOD AND APPARATUSFOR
`
`MONITORING TRAFFIC IN A NETWORK,to inventors Dietz,et al., filed June 30,
`
`2000, Attorney/Agent Reference Number APPT-001-1, and incorporated herein by
`
`’ reference.
`
`15
`
`U.S. Patent Application Serial No. 03 _/601'77for PROCESSING PROTOCOL
`
`SPECIFIC INFORMATIONIN PACKETS SPECIFIED BY A PROTOCOL
`
`DESCRIPTION LANGUAGE,to inventors Koppenhaver,etal., filed June 30, 2000,
`
`Attorney/Agent Reference Number APPT-001-2, and incorporated herein by
`
`reference.
`
`20
`
`U.S. Patent Application Serial No. 04/402 L-6éfor ASSOCIATIVE CACHE
`
`STRUCTURE FOR LOOKUPS AND UPDATES OF FLOW RECORDSIN 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
`
`9 6T
`for STATE PROCESSOR FOR
`U.S. Patent Application Serial No. 99 1693
`PATTERN MATCHING IN A NETWORK MONITORDEVICE,to inventors
`
`Sarkissian,et al., filed June 30, 2000, Attorney/Agent Reference Number APPT-001-
`
`5, and incorporated herein by reference.
`
`NOACEx. 1018 Page 5
`
`NOAC Ex. 1018 Page 5
`
`

`

`S
`
`2)
`
`fatcuraGnaanaeetaaMeelbgodtOHfled"(2HeateaIpiMHaeMettaMateHiatt
`PeaweeeaaLHWdike
`
`soapehnatHd
`
`FIELD OF INVENTION
`
`The present invention relates to computer networks,specifically to the real-time
`
`elucidation of packets communicated within a data network, includingclassification
`
`according to protocol and application program.
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document contains material thatis
`
`subject to copyright protection. The copyright owner has no objection to the facsimile
`
`reproduction by anyoneof the patent documentor the patent disclosure, as it appears in
`
`the Patent and Trademark Office patent file or records, but otherwise reservesall
`
`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
`
`interconnected networks. In particular, there is a need for a real-time network monitor
`
`15
`
`that can provide details as to the application programs being used. Such a monitor should
`
`enable non-intrusive, remote detection, characterization, analysis, and captureofall
`
`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
`
`20
`
`determinethe 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 bereliant upon server resident information suchas log files. Rather, it should allow a
`
`25
`
`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 ofdata that is
`
`collected and analyzed; to undertakereal time analysis; andto receive timely notification
`
`of network problems.
`
`r
`23a
`Related and incorporated by reference U.S. Patent application .>1/(08? for
`METHODAND APPARATUS FOR MONITORINGTRAFFIC IN A NETWORK, to
`
`30
`
`NOACEx. 1018 Page 6
`
`NOAC Ex. 1018 Page 6
`
`

`

`O
`
`)
`
`inventors Dietz, et al, Attorney/Agent Docket APPT-001-1, describes a network monitor
`
`that includes carrying out protocol specific operations on individual packets including
`
`extracting information from headerfields 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 includesa parser for
`
`recognizing differentpatterns 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 havethis signature from a database of knownflows.
`
`The flow signature of the packet, the hash andat least some of the payload are
`
`passed to an analyzer subsystem. In a hardware embodiment, the analyzer subsystem
`
`includesa 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
`
`whethera signature is from an existing flow, a state processor (SP) for performingstate
`
`processing, a flow insertion and deletion engine (FIDE)forinserting new flowsinto 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 FIDEareall
`
`coupled to the UFKB, andto the cache.
`
` 10
`
`15
`
`20
`
`Each flow-entry includes one or morestatistical 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
`
`FIDEoperate independently from the other two engines. Thestate processor performs
`
`one or more operations specific to the state of the flow.
`
`25
`
`It is advantageousto collect statistics on packets passing through a pointin a
`
`network rather than to simply count each and every packet. By maintainingstatistical
`
`measuresin the flow-entries related to a conversational flow, embodimentsof the present
`
`invention enablespecific metrics to be collected in real-time that otherwise would not be
`possible. For example,it is desirable to maintain metrics related to bi-directional
`conversations based on the entire flow for each exchangein the conversation. By
`maintainingthe state of flow, embodiments ofthe present invention also enable certain
`
`30
`
`NOACEx. 1018 Page 7
`
`NOAC Ex. 1018 Page 7
`
`

`

`anpaadeaaHonRERtededs
`
`Wallgeeoh
`
`GetetabHe
`
`eaePwdeeyeee
`
`Nas
`
`9
`
`>
`
`metricsrelated to the states of flows to be determined.
`
`Mostprior-art network traffic monitors that usestatistical metrics collect only
`
`end-point and end-of-sessionrelated statistics. Examples of such commonly used metrics
`
`include packet counts, byte counts, session connection time, session timeouts, session
`
`and transport response times andothers. All of these deal with events that can bedirectly
`
`related to an event in a single packet. These prior-art systems cannotcollect some
`
`important performance metrics that are related to a complete sequenceof packets of a
`
`flow or to several disjointed sequences of the sameflow in a network.
`
`Time based metrics on application data packets are important. Such metrics could
`
`10
`
`be determinedif all the timestamps andrelated data could be stored and forwarded for
`
`later analysis. However when faced with thousandsor millions of conversations per
`
`second on everfaster networks, storing all the data, even if compressed, would take too
`
`muchprocessing, memory, and manager download timeto bepractical.
`
`Thusthere is a need for maintaining and reporting time-base metrics from
`
`15
`
`statistical measures accumulated from packetsin a flow.
`
`Network data is properly modeled as a population and not a sample. Thus, all the
`
`data needs to be processed. Becauseofthe nature of application protocols, just sampling
`
`some of the packets may not give good measuredrelated to flows. Missing just one
`
`critical packet, such as one the specified an additional port that data will be transmitted
`
`20
`
`on, or what application will be run, can cause valid data to belost.
`
`Thusthere is also a need for maintaining and reporting time-base metrics from
`
`statistical measures accumulated from every packetin a flow.
`
`There also is a need to determine metrics related to a sequence of events. A good
`
`exampleis relative jitter. Measuring the time from the end of one packet in one direction
`
`25
`
`to another packet with the same signature in the samedirection collects data that relates
`
`normal jitter. This type ofjitter 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.
`
`Usingthe state processing described herein, because the state processor can
`
`NOACEx. 1018 Page 8
`
`NOAC Ex. 1018 Page 8
`
`

`

`9
`
`)
`
`search for specific data payloads, embodiments of monitor 300 can be programmedto
`
`collect the samejitter metric for a group of packetsin a flow thatare 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 programmedto maintain any type of
`
`metric at any state of a conversational flow. Also the system 300 can havethe actual
`
`Statistics programmedinto the state at any point. This enables embodiments ofthe
`
`10
`
`monitor system to collect metrics related to network usage and performance,as well as
`
`metrics related to specific states or sequences of packets.
`
`Someof the specific metrics that can be collected only with states are events
`
`related to a group oftraffic in one direction, events related to the status of a
`
`communication sequencein 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 toaset of metrics.
`
`
`
`PSAeo
`
`Rt
`
`In addition, because the monitor 300 providesgreater visibility to the specific
`
`application in a conversation or flow, the monitor 300 can be programmedtocollect
`
`metrics that may be specific to that type of application or service. In other word,if a flow
`
`20
`
`is for an Oracle Database server, an embodiment of monitor 300 could collect the
`
`numberof 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 programmedto collect a diverse set of metrics,
`
`the system can be used as a data source for metrics required in a number of
`
`25
`
`environments. In particular, the metrics may be used to monitor and analyze the quality
`
`and performanceoftraffic 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
`
`programmedto provide metrics useful for troubleshooting and capacity planning and
`
`30
`
`related directly to a focused application and service.
`
`NOACEx. 1018 Page 9
`
`NOAC Ex. 1018 Page 9
`
`

`

`
`
`SUMMARY
`
`Another aspectof 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 determineif
`
`the received packet is of an existing flow. Each and every packet is processed. If the
`
`packetis of an existing flow, the method updates the flow-entry of the existing flow,
`
`10
`
`including storing one or morestatistical measures kept in the flow-entry. If the packetis
`
`of a new flow, the method stores a new flow-entry for the new flow in the flow-entry
`
`database, including storing one or morestatistical 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.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Although the present invention is better understood by referring to the detailed
`
`preferred embodiments, these should notbe takento limit the present invention to any
`
`specific embodiment because such embodiments are provided only for the purposes of
`
`20
`
`explanation. The embodiments, in turn, are explained with the aid of the following
`
`figures.
`
`FIG.1 is a functional block diagram of a network embodimentofthe present
`
`invention in which a monitor is connected to analyze packets passing at a connection
`
`point.
`
`
`
`
`
`25
`
`FIG.2 is a diagram representing an example of someofthe packets andtheir
`
`formats that might be exchangedin starting, as an illustrative example, a conversational
`flow betweenaclient and server on a network being monitored and analyzed. A pair of
`flow signatures particular to this example and to embodimentsofthe present invention is
`
`also illustrated. This represents someofthe possible flow signatures that can be
`
`a
`
`NOACEx. 1018 Page 10
`
`NOAC Ex. 1018 Page 10
`
`

`

`QO
`
`»)
`
`
`
`sistaaeadd;aed
`
`waleahfellHo
`
`
`
`iWDDtheeHiattWattAdeotras
`
`generated and usedin 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 embodimentof the present
`
`invention that can operate as the packet monitor shownin FIG. 1. This process may be
`
`implementedin 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 accordingto versions of the present invention.
`
`FIG. 5 is a flowchart of a packet parsing process usedas part of the parser in an
`
`10
`
`embodimentof the inventive packet monitor.
`
`FIG.6 is a flowchart of a packet element extraction processthat is used as part of
`
`the parser in an embodimentof 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 embodimentof 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
`
`20
`
`the pattern recognizer and extractor that can form part of the parser module in an
`
`embodimentof the inventive packet monitor.
`
`FIG.11 is a functional block diagram of a hardware analyzer includinga state
`
`processor that can form part of an embodiment ofthe inventive packet monitor.
`
`FIG. 12 is a functional block diagram of a flow insertion and deletion engine
`
`25
`
`process that can form part of the analyzer in an embodimentof the inventive packet
`
`monitor.
`
`FIG. 13 is a flowchart of a state processing process that can form part of the
`analyzer in an embodimentof the inventive packet monitor.
`
`NOAC Ex. 1018 Page 11
`
`NOAC Ex. 1018 Page 11
`
`

`

`
`
`2
`
`FIG. 14 is a simple functional block diagram of a process embodimentof the
`
`present invention that can operate as the packet monitor shownin FIG.1. This process
`
`may be implementedin 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 aspectof the
`
`invention.
`
`
`
`
`
`waeaeiygeeHOPMBdee
`
`FIG. 17A is an example of the header of an Ethertype type of Ethernet packet of
`
`10
`
`FIG. 16 and someof the elements that may be extracted to form a signature according to
`
`one aspectof the invention.
`
`FIG. 17B is an example of an IP packet, for example, of the Ethertype packet
`
`shown in FIGs. 16 and 17A, and someof the elements that may be extracted to form a
`
`signature according to one aspect ofthe invention.
`
`15
`
`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 accordanceto
`
`one embodimentof 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 namesare sufficiently descriptive, in other cases
`
`howeverthe signal namesare not needed to understand the operation and practice of the
`
`25
`
`invention.
`
`Operation in a Network
`
`FIG. 1 represents a system embodimentof the present inventionthat 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
`
`

`

`O
`
`D
`
`seeRtadeyveHoghala
`
`aay
`ay
`
`wayCe
`IERORtheeadhytOFae
`
`hoawedvX
`
`102 that communicates packets (e.g., IP datagrams) between various computers, for
`
`example betweenthe clients 104-107 and servers 110 and 112. The network is shown
`
`schematically as a cloud with several network nodes and links showninthe 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 programsare 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 andthe interface 118 of the client 104, or
`
`10
`
`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
`
`15
`
`required communication,e.g., TCP/IP, etc. Any network activity—for example an
`
`application program run bythe 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
`
`20
`
`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 needto 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 conformingto the ISO layered network model.
`
`25
`
`Communication protocols are layered, whichis 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,
`shownin table form below,servesas a basic reference for understanding the
`
`functionality of existing communication protocols.
`
`NOACEx.1018 Page 13
`
`NOAC Ex. 1018 Page 13
`
`

`

`10
`
`ISO MODEL
`
`
`
`
`
`
`
`
`
`|
`
`NetworkInterface Card (Hardware
`
`Interface). MAC layer
`
`i
`
`Ethernet, Token Ring, Frame Relay,
`
`ATM,T1 (Hardware Connection)
`
`7
`
`Application
`
`
`
`Telnet, NFS, Novell NCP, HTTP,
`
`H.323
`
`Tafreonioe
`
`TCP, Novel SPX, UDP,etc.
`
`IP, Novell IPX, VIP, AppleTalk, etc.
`
`
`
` foeomigodeeenPhalAd
`
`
`2
`
`ahHaut
`
`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 notbe visible to protocols employed at other
`
`an
`
`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
`
`10
`
`“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
`
`encompasspackets, 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
`
`15
`
`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
`
`We
`
`NOACEx. 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 recognizingall 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 doesnot, then in
`
`order to recognize packets of that application’s conversational flow, the monitor can be
`
`
`
`
`ceeom
`
`SEITR,RETOntRYAye
`
`10
`
`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 hasstarted 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
`
`15
`
`simultaneously also in partial completion of identifying other packet exchangesthat are
`
`parts of conversational flows associated with other applications. One aspect of monitor
`
`108is its ability to maintain the state of a flow. The state of a flow is an indication ofall
`
`previous events in the flow thatlead to recognition of the content ofall the protocol
`
`levels, e.g., the ISO model protocol levels. Another aspect of the invention is forming a
`
`20
`
`signature of extracted characteristic portions of the packet that can be usedto rapidly
`
`identify packets belonging to the same flow.
`
`In real-world uses of the monitor 108, the numberof 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
`
`25
`
`and identify and maintainthestate of the flows passing through the connectionpoint.
`
`The monitor 108 therefore masksoutall the unimportantparts of each packetthat will
`
`not contribute to its classification. However, the parts to mask-out will change with each
`packet depending on whichflow it belongs to and dependingonthestate of the flow.
`
`30
`
`The recognition of the packet type, and ultimately of the associated application
`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 programswill
`
`NOACEx.1018 Page 15
`
`NOAC Ex. 1018 Page 15
`
`

`

`teaptet,@ees
`
`
`
`
`
`RRRON
`croTR
`
`
`onaisHe
`
`
`O
`
`5
`
`12
`
`all produce a first kind of packet. A first “signature” is produced from selected parts of a
`
`packetthat will allow monitor 108to identify efficiently any packets that belong to the
`
`same flow. In somecases, 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 usedto efficiently identify all future packets generated in
`
`traffic related to that application.
`
`In othercases, 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—butthat
`
`10
`
`potentially belongs to the same conversational flow—is recognized by using the
`
`signature. At such a secondlevel, then, only a few of those application programswill
`
`have conversational flows that can produce such a second packettype. At this level in
`
`the process of classification, all application programs that are notin the set of those that
`
`lead to such a sequenceof packet types may be excludedin the processofclassifying the
`
`15
`
`conversational flow that includes these two packets. Based on the knownpatterns 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
`
`proceedto a third level of analysis using the second level signature. For each packet,
`
`20
`
`therefore, the monitor parses the packet and generates a signature to determineif 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
`
`25
`
`flows associated with different applications. A new signature for recognizing future
`
`packets mayalso be generated. This process of analysis continues until the applications
`
`are identified. The last generated signature may then be usedto 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.
`
`NOACEx. 1018 Page 16
`
`NOAC Ex. 1018 Page 16
`
`

`

`O
`
`J
`
`13
`
`Anotheraspect of the invention is adding Eavesdropping. In alternative
`
`embodiments of the present invention capable of eavesdropping, once the monitor 108
`
`has recognized the executing application programs passing through somepointin the
`
`network 102 (for example, because of execution of the applications bythe client 105 or
`
`server 110), the monitor sends a message to some general purpose processor on the
`
`network that can input the same packets from the same location on the network, and the
`
`processor then loads its own executable copy of the application program andusesit to
`
`read the content being exchanged over the network. In other words, once the monitor 108
`
`has accomplished recognition of the application program, eavesdropping can commence.
`
`
`
`
`
`
`
`10
`
`The Network Monitor
`
`FIG. 3 showsa network packet monitor 300, in an embodimentof the present
`
`invention that can be implemented with computer hardware and/or software. The system
`
`300 is similar to monitor 108 in FIG. 1. A packet 302 is examined, e.g., from a packet
`
`acquisition device at the location 121 in network 102 (FIG. 1), and the packet evaluated,
`
`15
`
`for example in an attempt to determineits characteristics, e.g., all the protocol
`
`information in a multilevel model, including what server application produced the
`
`packet.
`
`The