I
`
`'Z
`
`coioe
`
`PATENT NUMBER
`
`6TT 1646
`
`I
`
`Certiticalle
`
`NOV 1. 6 Z004
`
`of' 6or,r,ection
`
`Certif "co
`
`I
`
`te
`
`SEP 2 12004
`
`PTO-2040
`12/99
`
`of Correction
`
`ISSUING CLASSIFICATION
`
`ORIGINAL
`
`CROSS REFERENCE(S)
`
`CLASS
`
`SUSCL&W"
`
`CLASS
`
`SUBCLASS (ONE SUBCLASS PER BLOCK)
`
`;? o
`INTERNATIONAL CVAIFIC'A'TION
`
`3s
`
`7//
`
`Continued on issue Slip inside File Jacket
`
`x
`
`I
`
`Form PTO-436A
`(Rev. 6199)
`
`ISSUE FtE IN FILE
`
`FILED WITH: E] DISK (CRF) [] FICHE [] CD-ROM
`
`(Attached in pocket on right inside flap)
`
`(FACE)
`
`Petitioners' EX1013 Page 1
`
`

`
`PATENT APPLICATION
`
`JC836 U.S. PTO
`
`1111111111111111111111111111111111111111111
`
`09608266
`
`CONTENTS
`
`Date Received
`(incl. C. of M.)
`or
`Date Mailed
`
`42.
`
`43.
`
`44.
`
`45.
`
`46.
`
`47.
`
`P14 48.
`49.
`
`50.
`
`-4 - /ZL-:o
`q
`
`/
`
`/jz-
`
`AppfidafiorIXrflol pa pers.
`
`in,\ klc
`
`4# e-S
`
`4.7r D,5 Wl KE-f 15 r,
`
`e- e s
`
`41,
`
`61-9
`
`Ir-It
`
`INITIALS
`
`JUL
`
`Date Rerelved
`(Incl. C' of M.)
`I
`or
`Date Mailed
`
`53.-
`
`54._7
`2.w
`
`60.-
`
`61.
`
`65.
`
`69.
`
`76.
`
`80,
`
`(LEFT OUTSIDE)
`
`Petitioners' EX1013 Page 2
`
`

`
`I
`
`Page I of I
`
`UNITED STATEs PATENT AND TRADEMARK OFFIGE
`
`COMMISSIONER FOR PATENTS
`uNITIED ZOA1 ES, r-ATENT AND IRADEMARK OFFICF
`WASHING'TON, D.C, 20231
`www.uspto.gov
`
`1111111111 IM 11111111111111111111111111111111111111 IN
`
`Bib Data Sheet\\
`
`SERIAL NUMBER
`09/608,266
`
`FILING DATE
`
`06/30/2000
`
`RULE
`
`APPLICANTS
`X;
`Haig A. Sarkissian, San Ant
`00X
`eA
`Russell S. Dietz, S; n
`
`CLASS
`
`51-
`
`GROUP ART UNIT
`2731
`
`ATTORNEY
`DOCKETNO.
`AP
`PT-QOf-4
`
`I
`
`L4 96
`
`CONTINUING DAT
`THISAPPL
`1) Z
`PLICATIONS
`
`**.FOREIGN
`
`AIMS BEINEFIT OF 60/141,903 06130/19919
`
`FO
`IF REQ
`GRAN D
`
`ED, FOREIGN FILING LICENSE
`09/01/2000
`
`10011'
`
`WX
`
`Li yes
`
`Ll yes
`
`,,Allo
`
`ce
`
`n
`
`no Ll Met after
`
`SHEETS
`STATE OR
`COUNTRY DRAWING
`TX
`21
`
`TOTAL
`CLAIMS
`20
`
`INDEPENDENT
`CLAIMS
`3
`
`p
`
`'wForeign ' iority claimed
`C
`
`35 USC 119 (a-d) conditions
`met
`
`Verified and
`Acknowledged
`ADDRESS
`
`Dov Rosenfel
`
`5507 Colleg Avenue
`
`Suite 2
`
`Oakland , A 94618
`
`sclqTature
`
`,- 9-
`
`Initials
`
`:,sociative cache structure for lookups and updates of flow records in a network monitor
`
`FILING FEE FEES: Authoritv has been aiven in Paner
`RECEIVED
`to charge/credit DEPOSIT AC-COUNT
`No.
`No.
`840
`for following:
`
`All Fees
`
`Ll 1. 16 Fees ( Filing
`
`T' 17 Fees ( Processing Ext. of
`
`Ll 1. 18 Fees( Issue
`
`Ll Other
`
`Ll Credit
`
`file://C:\APPS\PreExam\correspondence\IA.xmI
`
`11/2/00
`
`Petitioners' EX1013 Page 3
`
`

`
`0) - 03- 0 0
`
`m
`
`IN THE U.S. PATENT AND TRADEMARK OFFICE
`Application Transmittal Sheet
`
`CS1,1110V6
`
`po
`
`me.4M 0
`
`Box Patent Application
`ASSISTANT COMMISSIONER FOR PATENTS
`Washington, D.C. 20231
`
`Dear Assistant Comniissioner:
`
`Transniitted herewith is the patent application of
`
`OurRef./DocketNo.: APPT-0014
`01, m
`a$%93
`
`u
`
`Last Name
`
`Sarkissian
`
`Dietz
`
`E14VENTOR(s)/APPLICANT(s)
`First Name, MI
`Residence (City and State or Country)
`
`Haig A.
`
`Russell S.
`
`San Antonio, Texas
`San Jose, CA
`
`TITLE OF THE INVENTION
`
`ASSOCIATIVE CACHE STRUCTURE FOR LOOKUPS AND UPDATES OF FLOW RECORDS IN A
`NETWORK MONITOR
`
`CORRESPONDENCE ADDRESS AND AGENT FOR APPLICANT(S)
`
`Dov Rosenfeld, Reg. No. 38,387
`
`5507 College Avenue, Suite 2
`Oakland, California, 94618
`
`Telephone: (510) 547-3378; Fax: (510) 653-7992
`
`ENCLOSED APPLICATION PARTS (check all that apply)
`
`Included are:
`*
`*
`
`65
`21
`
`sheet(s) of specification, claims, and abstract
`
`sheet(s) of formal Drawing(s) with a submission letter to the Official Draftsperson
`
`Information Disclosure Statement.
`Form PTO- 1449: INFORMATION DISCLOSURE CITATION IN ANAPPLICATION, together with a
`copy of each references included in PTO- 1449.
`
`Declaration and Power of Attorney
`
`An assignment of the invention to Apptitude, Inc.
`
`A letter requesting recordation of the assignment.
`
`An assignment Cover Sheet.
`
`Additional inventors are being named on separately numbered sheets attached hereto.
`
`*
`This application has:
`
`Return postcard.
`
`a small entity status. A verified statement:
`
`is enclosed
`
`was already filed.
`
`The fee has been calculated as shown in the following page.
`
`I
`
`Certificate of Mailing under 37 CFR 1.10
`
`1
`
`1
`
`I hereby certify that this application and all attachments are being deposited with the United States Postal
`Service as Express Mail (Express Mail Label: E1417961895US in an envelope addressed to Box Patent
`
`Applicat'
`
`Assi tant Comniissioner for Patents, Washington, D.C. 20231 on
`
`Date:
`
`gne
`
`N
`
`eov Rosenfeld,Reg.N
`
`o.38687
`
`Petitioners' EX1013 Page 4
`
`

`
`SUBMISSION DOCUMENT
`ATTORNEY DOCKET NO. APPT-001-4
`
`Page 2
`
`TOTAL CLAMS
`
`NO.OFEXTRA
`CLAMS
`
`TOTAL
`CLAIMS
`
`INDEP.
`CLAIMS
`
`20
`
`3
`
`0
`
`0
`
`I
`
`BASIC APPLICATION FEE:
`
`TOTAL FEES PAYABLE:
`
`RATE
`
`$18
`
`$78
`
`EXTRA CLAIN4
`FEE
`
`$ 0.00
`
`$ 0.00
`
`$690.00
`
`$690.00
`
`METHOD OF PAYMENT
`
`A check in the amount of
`is attached for application fee and presentation of claims.
`A check in the amount of $ 40.0 is attached for recordation of the Assigmnent.
`The Conunissioner is hereby authorized to charge payment of the any missing filing or other fees
`required for this filing or credit any overpayment to Deposit Account No. 50-0292
`(A DUPLICATE OF THIS TRANSMITTAL IS ATTACHED):
`
`Respectfully Submitted,
`
`Date
`
`Dov Rosenfeld, Reg. No. 38687
`
`Correspondence Address:
`Dov Rosenfeld
`5507 College Avenue, Suite 2
`Oakland, California, 94618
`Telephone: (510) 547-3378; Fax: (510) 653-7992
`
`Petitioners' EX1013 Page 5
`
`

`
`OurRef/DocketNo.: APPT-001-4
`
`ASSOCIATIVE CACHE STRUCTURE FOR LOOKUPS AND UPDATES OF FLOW
`RECORDS IN A NETWORK MONITOR
`
`Inventor(s):
`
`SARKISSIAN, Haig A.
`San Antonio, Texas
`
`DEETZ, Russell S.
`San Jose, CA
`
`Certiflcate 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: E1417961895US in an envelope addressed to Box Patent Application, Assistant Commissioner for Patents,
`C. 20231 on.
`
`Wash
`Date.
`
`Signed
`Name: Dovfo-s-enfeld, Reg. No. 38687
`
`Petitioners' EX1013 Page 6
`
`

`
`1
`
`ASSOCIATIVE CACHE STRUCTURE FOR LOOKUPS AND
`UPDATES OF FLOW RECORDS IN A NETWORK MONITOR
`
`CROSS-REFERENCE TO RELATED APPLICATION
`
`This application claims the benefit of U.S. Provisional Patent Application Serial No.:
`
`5
`
`60/141,903 for METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A
`
`NETWORK to inventors Dietz, et al., filed June 30, 1999, the contents of which are
`
`incorporated herein by reference.
`
`This application is related to the followinAi-S. patent applications, each filed
`
`concurrently with the present application, and each assigned to Apptitude, Inc., the
`
`10
`
`assignee of the present invention:
`
`ho. (#( (.6 It w
`U.S. PatentAppU"4omSekfti-?ie-,,&,ki,
`
`for METHOD AND APPARATUS FOR
`
`MONITORING TRAFFIC 11%; A NETWORK, to inventors Dietz, et al., 94ed iiatie 90&
`
`29GO,
`
`reference.
`
`and incorporated herein by
`
`No. (o
`U.S. PateniLApp4ee
`
`15
`
`"erifti Newuc6N,
`
`for PROCESSING PROTOCOL
`
`SPECIFIC INFORMATION IN PACKETS SPECMMD BY A PROTOCOL
`
`DESCRIPTION LANGUAGE, to inventors Koppenhaver, et al., filed J4aae 99, i994,-
`
`and incorporated herein by
`
`C,
`
`C-1
`
`reference.
`
`20
`
`U.S. Patent Application Serial No.
`
`41%
`
`Ol/ go e, /a &
`for RE-USING INFORMATION FROM
`
`DATA TRANSACTIONS FOR MAINTAINING STATISTICS IN NETWORK
`
`MONITORING, to inventors Dietz, et al., filed itifte 39-, 2069_
`
`APPF @944, and incorporated herein by reference.
`
`016 oe ;L 67
`U.S. Patent Application Serial No;-1i--d, for STATE PROCESSOR FOR
`
`25
`
`PATTERN MATCHING IN A NETWORK MONITOR DEVICE, to inventors
`
`(cid:173)5
`11) 0 D -,,A,y/A-e(cid:173) RPifRwPwqP N-tifftber-A43PET-004,
`Sarkissian, et al., filed juno ;Qj-2,
`
`and incorporated herein by reference.
`
`FIELD OF INVENTION
`
`The present invention relates to computer networks, specifically to the real-time
`
`0
`
`Petitioners' EX1013 Page 7
`
`

`
`elucidation of packets communicated within a data network, including classification
`
`2
`
`according to protocol and application program.
`0
`
`BACKGROUND
`
`There has long been a need for network activity monitors. This need has become
`
`especially acute, however, given the recent popularity of the Intemet and other
`
`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
`
`10
`
`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 pattem of use
`
`within each application or the application context (e.g., options selected, service
`
`15
`
`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 adn-iinistrator or an Intemet service provider (ISP) the means to
`
`measure and analyze network activity objectively; to custorriize the type of data that is
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`20
`
`of network problems.
`
`(11
`
`Related and incorporated by reference U.S. Patent
`
`for
`
`METHOD AND APPARATUS FOR MONITORING TRAFFIC INA NETWORK, to
`
`go.
`
`inventors Dietz, et al, Aftar-aeyAgeof Peekm A.=-494-4, describes a network monitor
`
`that includes carrying out protocol specific operations on individual packets including
`
`25
`
`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 pattems in the packet that identify the protocols used. For each
`
`protocol recognized, a slicer extracts important packet elements from the packet. These
`
`30
`
`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.
`
`Petitioners' EX1013 Page 8
`
`

`
`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
`
`10
`
`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 prefeffed hardware embodiment, each of the LUE, state processor, and
`
`FIDE operate independently from the other two engines. The state processor performs
`
`15
`
`one or more operations specific to the state of the flow.
`
`Because of the high speed that packets may be entering the system, it is desirable
`
`to maximize the hit rate in a cache system. Typical prior-art cache systems are used to
`
`expediting memory accesses to and from microprocessor systems. Various mechanisms
`
`are available in such prior art systems to predict the lookup such that the hit rate can be
`
`20 maximized. Prior art caches, for example, can use a lookahead mechanism to predict
`
`both instruction cache lookups and data cache lookups. Such lookahead mechanisms are
`
`not available for a cache subsystem for the packet monitoring application. When a new
`
`packet enters the monitor, the next cache access, for example from the lookup engine,
`may be for a totally different conversational flow than the last cache lookup, and there is
`no way ahead of time of knowing what flow the next packet will belong to.
`
`25
`
`Thus there is a need in the art for a cache subsystem suitable for use in a packet
`
`monitor. One desirable property of such a cache system is a least recently used (LRU)
`
`replacement policy that replaces the LRU flow-entry when a cache replacement is
`
`needed. Replacing least recently used flow-entries is preferred because it is likely that a
`
`30
`
`packet following a recent packet will belong to the same flow. Thus, the signature of a
`
`new packet will likely match a recently used flow record. Conversely, it is not highly
`
`).
`
`x
`
`Petitioners' EX1013 Page 9
`
`

`
`4
`
`likely that a packet associated with the least recently used flow-entry will soon arrive.
`
`A hash is often used to facilitate lookups. Such a hash may spread entries
`
`randomly in a database. In such a case, a associative cache is desirable.
`
`There thus is a need for a associative cache subsystem that also includes a LRU
`
`replacement policy.
`
`SUMMARY
`
`Described herein is an associative cache system for looking up one or more
`
`elements of an extemal memory. The cache system comprises a set of cache memory
`
`elements coupled to the extemal memory, a set of content addressable memory cells
`
`10
`
`(CAMs) containing an address and a pointer to one of the cache memory elements, and
`
`including- a matching circuit having an input such that the CAM asserts a match output
`TW e,
`when the input is the same as the address in the CAM cell
`Whi& cache memory
`.
`wh
`element a particular CAM points to changes over time. In the preferred implementation,
`
`the CAMs are connected in an order from top to bottom, and the bottom CAM points to
`
`15
`
`the least recently used cache memory element.
`
`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
`
`20
`
`explanation. The embodiments, in tum, are explained with the aid of the following
`
`figures.
`
`FIG.Yis a functional block diagram of a network embodiment of the present
`
`"0'W-in which a molnitb"'iis connected to analyze packets passing at a connection
`
`25
`
`FIG
`
`a diagram representing an example of some of the packets and their
`
`formats
`
`might be exchanged in starting, as an illustrative example, a conversational
`
`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
`
`Petitioners' EX1013 Page 10
`
`

`
`5
`
`generated and used in the process of analyzing packets and of recognizing the particular
`
`server applications_ksrproduce the discrete application packet exchanges.
`
`is a functional block diagram of a process embodiment of the present
`
`that can operate as the packet monitor shown in FIG. 1. This process may be
`
`5
`
`ted in software orhardware.
`
`FIG. 4 is'41A
`
`.owchart of a high-level protocol language compiling and
`
`optimizatlyp7pro=,
`41K
`monitgoffig packets
`
`s, which in one embodiment may be used to generate data for
`
`accorojag'6 versions of the present invention.
`
`FIG. ;5is
`
`of a packet parsing process used as part of the parser in an
`
`io
`
`embodimey of the
`
`packet monitor.
`
`FIG. 6 iWf
`
`of a packet element extraction process that is used as part of
`
`the parserj&an err,
`
`'of the inventive packet monitor.
`
`FIG. 7 is;d'
`
`of a flow-signature building process that is used as part of
`
`the parserlin the in
`
`monitor.
`
`15
`
`"FIG. 8,jeaflowchart of a monitor lookup and update process that is used as part
`
`of the anAzer in an ern'qdiifient of the inventive packet monitor.
`
`FIG. 9 ip.flowchart of an exemplary Sun Microsystems Remote Procedure Call
`
`',io7ean
`a pplicat
`
`may be recorg""zed by the inventive packet monitor.
`ni
`
`,,f, FIG. 10J19"a functional block diagram of a hardware parser subsystem including
`
`20
`
`the pattern4ecognizer and extractor that can form part of the parser module in an
`
`erabod,A" nent of the inv"'entive packet monitor.
`
`,,III to a functional'block di4gram of a hardware analyzer includirig a state
`
`processor that can f9pi
`
`,
`
`part of an embodiment of the inventive packet monitor.
`
`FIG.
`
`S"
`
`s a functional block diagram of a flow insertion and deletion engine
`
`25
`
`process th
`
`can form part of the analyzer in an embodiment of the inventive packet
`
`FIG. 13
`
`flowchart of a state processing process that can form part of the
`
`analyzer in
`
`idiment of the inventive packet monitor.
`
`Petitioners' EX1013 Page 11
`
`

`
`I
`
`R
`
`FIG. 14
`
`zgimple functional block diagram of a process embodiment of the
`
`present invpdi(
`
`that can operate as the packet monitor shown in FIG. 1. This process
`
`may b implem
`
`in sottvare.
`
`FIG. 15
`
`oer
`a functional block diagram of how the packet monitor of FIG. 3 (and
`
`5
`
`FIGS. 10 fid 11) may operate on, a network with a processor such as a microprocessor.
`
`FIG. 16 is an
`
`of the top (MAC) layer of an Ethemet packet and some of
`
`I/
`
`the elements th'at'nay be extracted to form a signature according to one aspect of the
`
`invent on.
`
`FIG. l7kig'an example of the header of an Ethertype type of Ethemet packet of
`
`io
`
`FIG 16 an
`
`ome of the eleme, ts that may be extracted to form a signature according to
`
`one as
`
`ct of the inw,-rition.
`
`FIG,
`-7
`shown i-nFIGs. 16 and 17A, and some of the elements that may be extracted to form a
`
`B is an example of an IP packet, for example, of the Ethertype packet
`
`signature according to o $,agpect of the invention.
`
`15
`
`FIG. 1
`
`a three dimensional structure that can be used to store elements of
`
`the pattem,
`
`1
`
`c
`
`and extraction database used by the parser subsystem in accordance to
`
`one em
`
`im
`
`'
`
`oftheinveuu
`
`FIG. 18B i§Arn altemate form of storing elements of the pattem, parse and
`
`a*6ase used by the parser subsystem in accordance to another embodiment
`extraction d
`
`20
`
`of the invtn/i
`
`on.
`
`FIG.
`
`is a block diagrafh of the cache memory part of the cache subsystem
`
`1115 of 06
`
`analyzerjuesystem of FIG. 11.
`
`FIG. 26'ls a block diagram,of the cache memory controller and the cache CAM
`
`controllef of the cache s;
`
`ystem.
`
`25
`
`FIG. 2 1 js
`
`block diagram of one implementation of the CAM array of the cache
`
`subsystem, Pl 15.
`
`I
`
`Petitioners' EX1013 Page 12
`
`

`
`7
`
`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
`
`invention.
`
`Operation in a Network
`
`FIG. I 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., EP datagrams) between various computers, for
`
`10
`
`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
`
`15
`
`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/EP, etc. Any network activityfor example an
`
`application program run by the client 104 (CLIENT 1) communicating with another
`running on the server 110 (SERV-ER 2)will produce an exchange of a sequence of
`packets over network 102 that is characteristic of the respective progr'ams and of the
`network protocols. Such characteristics may not be completely revealing at the
`
`20
`
`25
`
`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
`
`30
`
`packets may need to be parsed then analyzed in the context of various protocols, for
`
`b
`
`Petitioners' EX1013 Page 13
`
`

`
`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 (Intemational 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.
`
`ISO MODEL
`
`Layer
`
`Functionality
`
`Example
`
`7
`
`6
`
`5
`
`4
`
`3
`
`2
`
`1
`
`Application
`
`Telnet, NFS, Novell NCP, HTTP,
`
`H.323
`
`Presentation
`
`XDR
`
`Session
`
`RPC, NETBIOS, SNMP, etc.
`
`Transport
`
`TCP, Novel SPX, UDP, etc.
`
`Network
`
`EP, Novell IPX, VIP, AppleTalk, etc.
`
`Data Link
`
`Network Interface Card (Hardware
`
`Interface). MAC layer
`
`Physical
`
`Ethemet, Token Ring, Frame Relay,
`
`ATM, Tl (Hardware Connection)
`
`Different conununication protocols employ different levels of the ISO model or
`io may use a layered model that is similar to but which does not exactly conform to the ISO
`- - -------------------- ,
`model. A protocol iri 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
`
`15
`
`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
`
`Petitioners' EX1013 Page 14
`
`

`
`W
`
`"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 coffecting code (ECC) field, or cyclic
`
`redundancy check (CRC) field, as well as headers and footers to identify the beginning
`
`and end of the packet. The terms "packet format" and "frame format," also refeffed to as
`
`"cell format," are generally synonymous.
`
`10
`
`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
`
`15
`
`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.
`
`20
`
`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
`
`25
`
`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 fonning 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
`
`30
`
`passing by the monitor 108's connection point can exceed a rnillion per second.
`
`Consequently, the monitor has very little time available to analyze and type each packet
`
`O
`
`Petitioners' EX1013 Page 15
`
`

`
`10
`
`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.
`
`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 programs will
`
`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
`
`10
`
`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.
`
`In other cases, that first packet only starts the process of analyzing the
`
`15
`
`conversational flow, and more packets are necessary to identify the associated
`
`application program. In such a case, a subsequent packet of a second typebut that
`potentially belongs to the same conversational flowis 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
`
`20
`
`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 pattems 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.
`
`25
`
`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 bel6nging to the same conversational flow. In real time, the packet is further
`
`30
`
`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
`
`Petitioners' EX1013 Page 16
`
`

`
`11
`
`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
`
`inspected.
`
`Another aspect of the invention is adding Eavesdropping. In altemative
`
`embodiments of the present invention capable of eavesdropping, once the monitor 108
`
`has recognized the executing application programs passing through some point in the
`
`10
`
`network 102 (for example, because of execution of the applications by the 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 and uses it to
`
`read the content being exchanged over the network. In other words, once the monitor 108
`
`15
`
`has accomplished recognition of the application program, eavesdropping can commence.
`
`The Network Monitor
`
`FIG. 3 shows a network packet monitor 300, in an embodiment of 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
`
`PA
`
`acquisition device at the location 121 in network 102 (FIG. 1), and the packet evaluated,
`
`for example in an attempt to determine its characteristics, e.g., all the protocol
`
`information in a multilevel model, including what server application produced the
`
`packet.
`
`The packet acquisition device is a conunon interface that converts the physical
`
`25
`
`signals and then decodes them into bits, and into packets, in accordance with the
`
`particular network (Ethemet, frame relay, ATM, etc.). The acquisition device indicates to
`
`the monitor 109 the type of network of the acquired packet or packets.
`
`Aspects shown here include: (1) the initialization of the monitor to generate what
`
`30
`
`operations need to occur on packets of different typesaccomplished by compiler and
`optimizer 310, (2) the processingparsing and extraction of selected portionsof
`packets to generate an identifying signatureaccomplished by parser subsystem 301,
`
`\t
`
`Petitioners' EX1013 Page 17
`
`

`
`and (3) the analysis of the packetsaccomplished by analyzer 303.
`
`12
`
`The purpose of compiler and optiniizer 3 10 is to provide protocol specific
`
`infonnation to parser subsystem 301 and to analyzer subsystem 303. The initialization
`
`occurs prior to operation of the monitor, and only needs to re-occur when new protocols
`
`are to be added.
`
`A flow is a stream of packets being exchanged between any two addresses in the
`
`network. For each protocol there are known to be several fields, such as the destination
`
`(recipient), the source (the sender), and so forth, and these and other fields are used in
`
`monitor 300 to identify the flow. There are other fields not important for identifying the
`
`10
`
`flow, such as checksums, and those parts are not used for identification.
`
`Parser subsystem 301 exaniines the packets using pattem recognition process 304
`
`that parses the packet and determines the protocol types and associated headers for each
`
`protocol layer that exists in the packet 302. An extraction process 306 in parser
`
`subsystem 301 extracts characteristic portions (signature information) from the packet
`
`15
`
`302. Both the pattem information for parsing and the related extraction operations, e.g.,
`
`extraction masks, are supplied from a parsing-pattem-structures and extraction-
`
`operations database (parsing/extractions database) 308 filled by the compiler and
`
`optiniizer 3 10.
`
`The protocol description language (PDL) files 336 describes both pattems and
`
`20
`
`states of all protocols that an occur at any layer, including how to interpret header
`
`information, how to detem-line from the packet header information the protocols at the
`next layer, and what information to extract for the purpose of identifying a flow, and
`
`ultimately, applications and services. The layer solections database 338 describes the
`particular layering handled by the monitor. That is, what protocols run on top of what
`
`25
`
`protocols at any layer level. Thus 336 and 338 combined describe how one would
`
`decode, analyze, and understand the information in packets, and, furthermore, how the
`
`information is layered. This information is input into compiler and optiniizer 3 10.
`
`When compiler and optimizer 3 10 executes, it generates two sets of intemal data
`
`structures. The first is th