`
`
`
`I
`1© ALL,TOWHOM THESE; PRESENTS) SHAWL:COME!
`
`
`
`UNITED STATES DEPARTMENT OF COMMERCE
`
`
`United States Patent and TrademarkOffice
`
`
`e
`
`
`Ge*s teh
`
`
`THIS IS TO CERTIFY THAT ANNEXED IS A TRUE COPY FROM THE
`Ne
`EELS
`
`
`
`RECORDSOF THIS OFFICE OF THE FILE WRAPPER AND CONTENTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`October 16, 2018
`
`OF:
`
`APPLICATION NUMBER: 09/608,266
`
`FILING DATE: June 30, 2000
`
`PATENT NUMBER: 6,771,646
`
`ISSUE DATE: August 03, 2004
`
`
`CELLEELELELEREEaeeae
`
`
`
`Phihidchbabhitl
`
`
`
`FistELLbbehabhi!
`
`
`
`ao
`
`
`
`
`
`
`
`
`
`By Authority of the
`Under Secretary of Commercefor Intellectual Property
`and Director of the United StatesPatent and Trademark Office
`
`
`
`
`
`
`
`
`
`NOAC Ex. 1017 Page 1
`
`
`
`
`
`PATENT NUMBER
`
`
`|e771648
`
`. menmun
`
`—
`
`
`
`Wee teSS
`
`771646
`a ,|US. UTILITY Patent Applicationee
`
`
`
`i wr ai >TPATENTDATE.
`
`
`
`N
`a
`c
`:
`o
`99g4
`y
`scannen
`AW
`an. Ke
`aye Oe m
`t
`a
`
`
`
`APPLICATION NO, CONT/PRIOR|CLASS SUBCLASS ART UNIT EXAMINER —
`
`
`
`
`wet
`-
`t
`oarcnecse
`. a .
`a)
`2e64 ~
`cars
`avn
`Oo /SI8556
`|
`o
`370
`Mea (| ?} oe A ‘
`/at
`| 3
`4
`+
`r
`\
`°
`a
`gs
`Certificate
`&
`ayy g20b Certificate
`pro-z040
`of Correction
`SEP 21 2004
`CERRIFICATE
`of Correct a
`
`:
`
`ve
`
`1
`
`.
`
`' Mh .
`
`.
`
`‘
`
`
`
`
`
`
`TERMINAL
`DISCLAIMER
`
`
`
`
`
`“
`
`
`
` C1 theterm ofthis patent
` “A lan V. Nauyer
`(date)-
`subsequent to
`
`
`has been disclaimed.
`(Assistant Examine)
`
`
`
`C1 The term ofthis patentshall
`
`not extend beyond the expiration date
`
`a
`of U.S Patent. No.
`RICKYNGO
`
`y|ioog:
`PRIMARY EXAMINER
`
`
`
`
`{Primary Examiner)
`(Date)
`
`months of
`C] The terminal
`this patent have been disclaimed.
`
`WARNING:
`
`
`wyeet$nagreementY ae
`The infosmation disclosed herein may be restncted Unauthorized disclosure may be prohibited the United States Code Title 35, Sections 122, 181 and 368
`
`Possession outside the U.S. Patent & Trademark Office ts restncted to authonzed employees and contractors-only.
`Coe ye,AeA
`FILED WITH: [_| Disk (cRF) []rtcHe [_] cp-Rom
`(Rev. 6/99)
`(Attached in pocket on right inside flap)
`~
`_
`ont
`IGSUE Fre IN FILE
`
`F
`
`<
`
`
`
`
`
` Continued on Issue Slip Inside File Jacket
`
`CLAIMS-ACLOWED
`Total Cjairis
`Print Claim for O.G.
`al
`
`Seo
`
`7
`
`‘
`
`,
`zs
`y
`‘
`
`
`
`NOTICE OF ALLOWANCE MAILED
`
`!
`
`{‘
`
`Temene
`
`
`
`
`
`
`~~
` ee&al B
`
`¢
`
`1
`
`4
`
`& “
`v
`
`(FACE)
`
`NOACEx. 1017 Page 2
`
`NOAC Ex. 1017 Page 2
`
`
`
`Page | of |
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`COMMISSIONER FOR PATENTS
`UNITED STaTES PATENT ANO TRADEMARK OFFICE
`WASHINGTON, DC, 20231
`www uspio gov
`
`
`‘NERC
`APPT-001-4
`
`Bib Data Sheet
`
`FILING DATE
`ATTORNEY
`
`SERIAL NUMBER GROUP ART UNIT|Docket NO.06/30/2000 CLASS
`
`
`09/608, 266
`RULE
`|
`370
`2731
`
`APPLICANTS
`Haig A. Sarkissian, San Antonio; TX 1”
`Russeil S. Dietz, San Josey’CA;
`ae
`L ®
`* CONTINUING DATA,prtornnassr]Brareatees
`THIS APPLN,etaims BENEFIT OF 60/141 ,903 06/30/1999
`wy
`* FOREIGN APPLICATIONS vveelleearanenne
`
`IF REQUIRED, FOREIGN FILING LICENSE
`GRANTED * 09/01/2000
`.
`-
`Foreign Priority claimed
`CJ yes ano,on
`
`
`86 USC 119 (a-d) conditionsLYyes Jano a Metafter COUNTRY|DRAWING|CLAIMS CLAIMS
`Q SHEETS|TOTALSTATEOR| |INDEPENDENT
`
`
`
`.
`Allewtes
`;
`TX
`21
`20
`3
`Examprier'sSs*Sig nature
`
`(nitiats
`
`ADDRESS °
`
`Dov Rosenfel
`
`5507 College’ Avenue
`Suite 2
`
`Oakland ,CA 94618
`
`TLE
`
`Associative cache structure for lookups and updatesof flow records in a network monitor
`[a All Fees
`Cl 1.16 Fees( Filing )
`Q 1 17 Fees ( Processing Ext. of
`jitime)
`Cl] 1.18 Fees( Issue )
`[Dotter
`Q Credit
`
`_
`
`FILING FEE |FEES:Authority has been given in Paper
`RECEIVED }No.
`to charge/credit DEPOSIT ACCOUNT
`for following:
`
`
`
`~,
`
`file://C:\APPS\PreExam\correspondence\l_A.xml
`
`Li.
`
`NOACEx.1017 Page 3
`
`NOAC Ex. 1017 Page 3
`
`
`
`PATENT APPLICATION SERIAL NO.
`
`U.S. DEPARTMENT OF COMMERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`oa
`
`PTO-1556
`(5/87)
`
`“U.S. GPO: 1999-459-682/19144
`
`myo
`
`NOACEx. 1017 Page 4
`
`NOAC Ex. 1017 Page 4
`
`
`
`07 -03-¢°
`
`Ss
`
`IN THE U.S. PATENT AND TRADEMARK OFFICE
`Application Transmittal Sheet
`
`826UN
`-PTO6
`
`m
`Oo
`SS
`om =
`L =
`
`a5
`
`Box Patent Application
`ASSISTANT COMMISSIONER FOR PATENTS
`Washington, D.C. 20231
`
`.
`Dear Assistant Commissioner:
`Transmitted herewith is the patent application of
`
`Last Name
`
`Sarkissian
`Dietz
`
`INVENTOR(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 RECORDSIN 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(checkall that apply)
`
` "S'
`96LEF
`
`Our Ref./Docket No.:_APPT-001-4
`
`ety
`
`ieWeelShae
`wallth
`
`hacibs.
`
`Included are:
`
`sheet(s) of specification, claims, and abstract
`x
`65___
`
`x 21___sheet(s) of forma! Drawing(s) with a submissionletter to the Official Draftsperson
`Information Disclosure Statement.
`Form PTO-1449: INFORMATION DISCLOSURE CITATIONIN ANAPPLICATION,together with a
`copyof each references included in PTO-1449.
`Declaration and Power of Attorney
`An assignmentof the invention to_Apptitude, Inc.
`A letter requesting recordation of the assignment.
`Anassignment Cover Sheet.
`Additional inventors are being named on separately numbered sheets attached hereto.
`
`Return postcard.
`Xx
`This application has:
`
`a smallentity status. A verified statement:
`is enclosed
`wasalready filed.
`
`The fee has been calculated as shownin the following page.
`
`Certificate of Mailing under 37 CFR 1.10
`I hereby certify that this application andall attachments are being deposited with the United States Postal
`Service as Express Mail (Express Mail Label: EI417961895USin an envelope addressed to Box Patent
`Application, Assistant Commissioner for Patents, Washington, D.C. 20231 on.
`
`Name: Dov Rosenfeld, Reg. No. 38687
`
`Signed?
`
`NOACEx. 1017 Page 5
`
`NOAC Ex. 1017 Page 5
`
`
`
`SUBMISSION DOCUMENT
`ATTORNEY DOCKET NO.
`
`_APPT-001-4
`
`Page 2
`
`NO. OF EXTRA
`CLAIMS
`
`TOTAL CLAIMS
`
`20
`
`RATE
`
`$18
`
`EXTRA CLAIM
`FEE
`
`TOTAL
`CLAIMS
`
`INDEP.
`CLAIMS
`
`
`
`
`
`ee|fm
`
`
`
`
`BASIC APPLICATION FEE:
`
`$ 690.00
`
`”
`
`TOTAL FEES PAYABLE:
`
`$ 690.00
`
`METHOD OF PAYMENT
`
`is attached for application fee and presentation of claims.
`A check in the amount of
`A check in the amountof $ 40.00 is attached for recordation of the Assignment.
`The Commissioneris hereby authorized to charge paymentofthe any missingfiling or other fees
`required forthis filing or credit any overpayment to Deposit Account No. 50-0292
`(A DUPLICATE OF THIS TRANSMITTAL IS ATTACHED):
`
`Respectfully Submitted,
`
`
`tae 30 2@20O0
`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
`
`itedtMaatHt
`
`fllan
`
`ill
`
`a
`
`NOACEx. 1017 Page 6
`
`NOAC Ex. 1017 Page 6
`
`
`
`Our Ref./Docket No: APPT-001-4
`
`Patent
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`
`
`Applicant(s): Sarkissian,et al.
`Group Art Unit: unassigned
`
`Title: ASSOCIATIVE CACHE STRUCTURE FOR
`LOOKUPS AND UPDATES OF FLOW
`
`
`RECORDSIN A NETWORK MONITOR
`
`
`Examiner: unassigned
`
`LETTER TO OFFICIAL DRAFTSPERSON
`SUBMISSION OF FORMAL DRAWINGS
`
`HeMellcdlMeltatt
`
`ted)IIMA
`
`ee
`
`The Assistant Commissionerfor Patents
`Washington, DC 20231
`ATTN: Official Draftsperson
`
`Dear Sir or Madam:
`
`Attached please find 21 sheets of formal drawings to be madeofrecord for the above
`identified patent application submitted herewith.
`
`2EP 20280
`
`Date
`
`Respectfully Submitted,
`
`ZB ——
`
`ov Rosenfeld, Reg. No. 38687
`
`Address for correspondence andattorney for applicant(s):
`Dov Rosenfeld, Reg. No. 38,687
`5507 College Avenue,Suite 2
`Oakland, CA 94618
`Telephone: (510) 547-3378; Fax: (510) 653-7992
`
` Certificate of Mailing under 37 CFR 1.10
`I herebycertify that this application andall attachments are being deposited with the United States Postal
`Service as Express Mail (Express Mail Label: EI417961895USin an envelope addressed to Box Patent
`Applicatign, Assistant Commissioner for Patents, Washington, D.C. 202
`
`Date: ese. 32) LOCO
`
`Signed;
`
`N
`
`“Dov Rosenfeld, Reg. No. 38687
`
`NOACEx.1017 Page 7
`
`NOAC Ex. 1017 Page 7
`
`
`
`Our Ref./Docket No.:
`
`_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
`
`DIETZ,Russell S.
`San Jose, CA
`
`
`
`Certificate of Mailing under 37 CFR 1.10
`
`Thereby 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 Commissionerfor Patents,
`
`
`
`Washington,
`
`Date:
`
`D.C. 20231on.
`
`ZO A960.
`
`Signed:
`
`E ZA
`
`NOACEx. 1017 Page 8
`
`
`
`
`
`MealHeftWaalHasseaeaedtneers
`
`Ams
`
`NOAC Ex. 1017 Page 8
`
`
`
`oa
`
`2)
`
`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
`
`NETWORKtoinventors Dietz,et al., filed June 30, 1999, the contents of which are
`incorporated herein by reference.
`WS Ps tents ime
`This application is related to the followingJ.S. patent applications, eachfiled
`>aa
`aly ley
`concurrently with the present application, and each assigned to Apptitude,Inc., the
`
`assignee of the present invention:
`No. b,'05 I yt
`C
`US. Patent, ApplicationSertatNemnahnfor METHOD AND APPARATUS FOR
`
`
`
`10
`
`MONITORING TRAFFIC IN A NETWORK,to inventors Dietz,et al., fledFane30,
`
`
`
`
`
`-2000,Atterney/AgentReferenceNumberAPPF-00144, and incorporated herein by
`
`reference.
`
`No. (,l65,725
`
`
`
`
`U.S. Patent AppheationSerratNe~henen.for PROCESSING PROTOCOL
`
`te.
`
`15
`
`SPECIFIC INFORMATION IN PACKETS SPECIFIED BY A PROTOCOL
`
`DESCRIPTION LANGUAGE,to inventors Koppenhaver,etal., filed June30-2000,
`
`
`
`
`
`Attorney/Agent-ReferenceNumberAPPFO01-2, and incorporated herein by
`
`CL
`
`20
`
`reference.
`
`oy/ bee, re
`U.S. Patent Application Serial No,t+ for RE-USING INFORMATION FROM
`DATA TRANSACTIONS FOR MAINTAINING STATISTICS IN NETWORK
`
`
`
`
`
`MONITORING,to inventors Dietz,et al., filedKine30,2060)Attorney/Acent
`
`
`ReferenceNumberAPPT-96+-3, and incorporated herein by reference.
`oft CORE?
`io
`U.S. Patent Application Serial No,wetzee, for STATE PROCESSOR FOR
`25
`PATTERN MATCHINGIN A NETWORK MONITOR DEVICE,to inventors
`
`Sarkissian, et al., filedJune-30-20
`
`3, and incorporated herein by reference.
`
`FIELD OF INVENTION
`
`The present invention relates to computer networks, specifically to the real-time
`
`NOACEx. 1017 Page 9
`
`NOAC Ex. 1017 Page 9
`
`
`
`O
`
`)
`
`2
`
`elucidation of packets communicated within a data network,includingclassification
`
`according to protocol and application program.
`
`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
`
`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
`
`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 be reliant upon server resident information suchaslog files. Rather, it should allow a
`
`user such as a network administrator or an Internet service provider (ISP) the meansto
`
`measure and analyze networkactivity objectively; to customize the type of data thatis
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`20
`
`of network problems.
`
`No, 6,051, 079
`
`Related and incorporated by reference U.S. Patentyeppltcation7/14,for
`METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A NETWORK,to
`
`
`—™
`
`
`
`inventors Dietz, et al, Atterney/+AsentDecketAPPT-O01-1,describes a network monitor
`
`that includes carrying out protocol specific operations on individual packets including
`
`25
`
`extracting information from headerfields in the packetto 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
`
`30
`
`form a signature (i.e., key) for the packet. Theslicer also preferably generates a hash for
`
`rapidly identifying a flow that may have this signature from a database of knownflows.
`
`
`
`NOACEx.1017 Page 10
`
`NOAC Ex. 1017 Page 10
`
`
`
`0
`
`)
`
`2
`
`elucidation of packets communicated within a data network, including classification
`
`according to protocol and application program.
`
`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
`
`that can provide details as to the application programs being used. Such a monitor should
`
`enable non-intrusive, remote detection, characterization, analysis, and capture ofall
`
`information passing through any point on the network(i.e., of all packets and packet
`
`streams passing through anylocation 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 suchaslog files. Rather, it should allow a
`
`user such as a network administrator or an Internet service provider (ISP) the meansto
`
`measure and analyze network activity objectively; to customize the type of data thatis
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`20
`
`of network problems.
`
`No, blot, 079
`Related and incorporated by reference U.S. Patentpappheaten7,/for
`METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A NETWORK,to
`
`inventors Dietz,et al, Atterney/AgentDecketAPPT-O004-4,describes a network monitor
`
`
`
`
`(™
`
`that includes carrying out protocol specific operations on individual packets including
`
`25
`
`extracting information from headerfields in the packetto 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 different patterns 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 havethis signature from a database of knownflows.
`
`
`
`NOACEx. 1017 Page 11
`
`NOAC Ex. 1017 Page 11
`
`
`
`0
`
`)
`
`2
`
`elucidation of packets communicated within a data network, including classification
`
`according to protocol and application program.
`
`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
`
`that can provide details as to the application programs being used. Such a monitor should
`
`enable non-intrusive, remote detection, characterization, analysis, and capture ofall
`
`information passing through any point on the network (i.e., of all packets and packet
`
`10
`
`streams passing through anylocation 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 serverresident information suchaslog 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 thatis
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`20
`
`of network problems.
`
`No, 6/651, 079
`Related and incorporated by reference U.S. Patentappleation7/asfor
`METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A NETWORK,to
`
`™
`
`inventors Dietz,et al, Atterney/AgentDecketAPPT-OO014, describes a network monitor
`
`that includes carrying out protocol specific operations on individual packets including
`
`25
`
`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 different patterns in the packetthat 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 havethis signature from a database of knownflows.
`
`NOACEx. 1017 Page 12
`
`NOAC Ex. 1017 Page 12
`
`
`
`0
`
`3
`
`4
`
`likely that a packetassociated with the least recently used flow-entry will soon arrive.
`
`A hashis often used to facilitate lookups. Such a hash mayspreadentries
`
`randomly in a database. In such a case, a associative cache is desirable.
`
`There thusis a need for a associative cache subsystem that also includes a LRU
`
`replacementpolicy.
`
`SUMMARY
`
`Described herein is an associative cache system for looking up one or more
`
`elements of an external memory. The cache system comprises a set of cache memory
`
`elements coupled to the external memory,a set of content addressable memory cells
`
`(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
`whenthe inputis the sameas the address in the CAM cell,Whieh cache memory
`clement particular CAM points to changesovertime. In the preferred implementation,
`
`the CAMsare 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
`
`Althoughthe 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 turn, are explained with the aid of the following
`
`figures.
`
`FIG. 1 is a functional block diagram of a network embodimentof the present
`inventionin which a monitor is connected to analyze packets passing at a connection
`
`point.
`
`25
`
`FIG.2 is a diagram representing an example of someof the packets and their
`
`formats that might be exchangedinstarting,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 embodimentsofthe present inventionis
`also illustrated. This represents some of the possible flow signatures that can be
`
`NOACEx. 1017 Page 13
`
`
`
`NOAC Ex. 1017 Page 13
`
`
`
`3
`
`5
`
`generated and usedin the process of analyzing packets and of recognizing the particular
`
`server applications that produce the discrete application packet exchanges.
`
`FIG. 3is a functional block diagram of a process embodimentofthe present
`invention that can operate as the packet monitor shownin FIG. 1. This process may be
`f
`implémented 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 accordingto versions of the present invention.
`
`FIG.5 is a flowchart of a packet parsing process used as part of the parser in an
`
`embodimentof 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 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.
`
`15
`
`FIG.8 is a flowchart of a monitor lookup and update processthat is used as part
`
`of the analyzer in an embodimentofthe inventive packet monitor.
`
`. FIG. 9 isa 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
`
`processorthat can form part of an embodimentof the 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. 1017 Page 14
`
`
`
`NOAC Ex. 1017 Page 14
`
`
`
`Q
`
`)
`
`6
`
`FIG. 14 is a simple functional block diagram of a process embodimentofthe
`present invention that can operate as the packet monitor shownin FIG. |. This process
`may be implemented in software.
`
`FIG.15 is a functional block diagram of how the packet monitorof 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.
`
`FIG. 17A is an example of the header of an Ethertype type of Ethernet packet of
`
`FIG. 16 and someof 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
`
`shownin FIGs. 16 and 17A, and someofthe elements that may be extracted to form a
`
`signature according to one aspect of the invention.
`
`15
`
`FIG. 18A is a three dimensionalstructure that can be used to store elements of
`
`the pattern, parse and extraction database used by the parser subsystem in accordance to
`
`one embodimentofthe invention.
`
`FIG. 18B is-analternate 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.
`
` FIG. 19 is a block diagram of the cache memory part of the cache subsystem
`fo
`1115 of the analyzer subsystem of FIG.11.
`<
`
`rrenepeetralia —
`
`FIG. 20 is a block diagram of the cache memory controller and the cache CAM
`
`controller of the cache subsystem.
`
`FIG. 21 is a block diagram of one implementation of the CAM array of the cache
`
`subsystem 1115.
`
`
`
`NOACEx.1017 Page 15
`
`NOAC Ex. 1017 Page 15
`
`
`
`5
`
`5
`
`7
`
`DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
`
`Note that this documentincludes hardware diagrams and descriptions that may
`
`include signal names. In mostcases, the namesare sufficiently descriptive, in other cases
`
`howeverthe signal namesare not needed to understand the operation and practice of the
`
`5
`
`invention.
`
`Operation in a Network
`
`FIG. 1 represents a system embodimentof the present invention that is referred to
`
`herein by the general reference numeral 100. The system 100 has a computer network
`
`102 that communicates packets (e.g., IP datagrams) between various computers, for
`
`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 pastits
`
`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
`
`15
`
`examining packets(i.e., datagrams) between the networkinterface 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
`
`someother location, as indicated schematically by connection point 125 somewhere in
`
`network 102. Not shownis a network packet acquisition device at the location 123 on
`
`20
`
`‘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 programsandofthe
`
`network protocols. Such characteristics may not be completely revealing at the
`individual packetlevel. 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 analyzedin the contextof various protocols, for
`
`
`
`NOACEx. 1017 Page 16
`
`NOAC Ex. 1017 Page 16
`
`
`
`O
`
`D
`
`8
`
`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, 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,iitannnennenaaleniinn
`shownin table form below, serves as a basic reference for understanding the
`
`functionality of existing communication protocols.
`ne
`
`ISO MODEL
`
`Application
`
`Telnet, NFS, Novell NCP, HTTP,
`
`H.323
`
`Physical
`
`
`
`
`
`
`P=eeefee
`
`
`sfoe
`[efron
`
` Network Interface Card (Hardware
`aa
` Ethernet, Token Ring, Frame Relay,
`
`
`
`Interface). MAClayer
`
`
`
`
`
`ATM, T1 (Hardware Connection)
`
`10
`
`15
`
`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 protocolin a certain layer may notbe visible to protocols employedat 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 communicationarts, 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
`
`
`
`NOACEx. 1017 Page 17
`
`NOAC Ex. 1017 Page 17
`
`
`
`o
`
`)
`
`9
`
`“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
`
`and end ofthe 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
`
`15
`
`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
`
`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 exchangesthat 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 ofall
`
`previous events in the flow that lead to recognition of the contentof 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 usedto rapidly
`
`identify packets belonging to the sameflow.
`
`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
`
`20
`
`25
`
`30
`
`5i i
`
`NOACEx.1017 Page 18
`
`NOAC Ex. 1017 Page 18
`
`
`
`q
`
`\
`
`+)
`
`10
`
`and identify and maintainthestate of the flows passing through the connection point.
`
`The monitor 108 therefore masksout all the unimportant parts of each packet that will
`
`not contributeto its classification. However, the parts to mask-out will change with each
`
`packet depending on whichflow it belongs to and dependingonthestate of the flow.
`
`The recognition of the packet type, and ultimately of the associated application
`
`programsaccording 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
`
`all producea 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
`
`same flow. In somecases, that packet type maybe 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 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—butthat
`
`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. Atthis level in
`
`20
`
`the processof classification,all application programsthat are notin the set of those that
`
`lead to such a seque