`
`
`
`m—v _~— _
`gummwuommrnsg 133135123119) @1490 (my
`
`October 16, 2018
`
`THIS IS TO CERTIFY THAT ANNEXED IS A TRUE COPY FROM THE
`
`RECORDS OF THIS OFFICE OF THE FILE WRAPPER AND CONTENTS
`
`OF:
`
`
`
`
`APPLICATION NUMBER: 09/608,266
`
`FILING DATE: June 30, 2000
`
`PATENT NUMBER: 6,771,646
`
`ISSUE DATE: August 03, 2004
`
`
`
`
`By Authority of the
`
`Under Secretary of Commerce for Intellectual Property
`and Director of the United Stat
`atent and Trademark Office
`
`
`
`P. SW N
`
`Ccrt'
`ing Officer
`
`
`
`
`
`
`
`
`won-Imurmur-w-on!gm
`
`
`
`
`UNITED STATES DEPARTMENT OF COMMERCE
`
`
`United States Patent and Trademark Office
`
`‘i'"3..(1‘}?!\C'
`
`33?
`
`,1
`AM,~ni-
`
`
`w
`anavrgfii
`‘3?me.
`
`\N—r«+3?
`
`\.
`'3:
`
`v4r»—
`~‘n- «-
`
`‘mn‘n'n‘fiaunwlnwfi‘l‘a2,‘33:
`Iw!w!!‘flfl<‘e§.~m"wit-tam!!!mtwn‘VnAIx-‘h‘,
`
`
`
`
`
`
`
`
`mmunnnmnmmuummunmnl
`
`
`
`
`
`
`
`
`NOAC EX. 1017 Pa e 1
`
`NOAC Ex. 1017 Page 1
`
`
`
`
`
`.S‘chlass
`
`
`"‘7‘ ‘ ‘quxrq :L- .,
`\k‘ “‘wvrfi;
`9.»—
`
`
`- us. UTILITY Patent AppIIcaIIon
`
`
`
`{I
`W 0.l
`.
`.
`_
`-
`PATENTDATE
`l
`6 77
`2';
`IIIIII
`o
`
`
`AUG 0 U
`[/1
`O.A.v
`U "thaw; ,_ W,
`V
`
`
`T’
`
`'
`
`>
`
`S ANNED
`,. 7‘
`
`,,
`
`,vv W ,-
`
`.
`
`7
`
`.7
`
`\— IL
`
`‘
`
`,
`
`'
`
`I
`
`,
`
`-
`5‘“
`
`’
`'
`
`'
`
`x .
`
`I
`
`~
`
`APZILICfllgg N39
`— -1 I. ._ I—ILC‘H
`
`,
`
`.
`
`/
`
`I
`
`*
`r.
`
`1
`
`-
`
`..
`
`I"
`"’
`"E “-
`U
`j
`E
`<
`
`E
`
`Certificate
`f
`'
`"“,.=IN0v;'1,62004« ,, m ~
`of CorrectIon
`<
`’
`1’:
`<5? I‘FIVCATI:
`OCT zzg 12.0114
`
`f
`
`,
`
`\
`
`ART UNIT
`2534-.
`p
`
`,4
`
`EXAMINER
`‘
`‘
`,
`. ”A;
`r‘
`TE*#1?77&fl1r ¢v~ ~
`’7
`'
`Y
`.
`4’ 5W 5'2 m I.
`/~I.
`I
`k
`C I ‘
`I
`I
`PI If a
`“f
`.ICJe
`mm
`SEP 21 2504
`12/99
`A
`I:
`‘ M - w
`GI LG? IeCIIGn
`
`‘
`
`I
`
`I
`I
`I
`I:
`,I
`:
`
`.
`
`.
`
`‘,
`
`I"
`
`f
`
`
`
`‘
`’
`'
`
`x‘
`
`I
`
`I|
`
`I
`II
`I
`II
`:
`
`II
`
`I
`
`1"
`
`‘1‘
`I
`
`i
`I
`I
`I.
`I
`I
`
`I
`
`I
`
`I II I
`
`‘
`I
`
`.
`I
`2
`
`'
`‘
`‘
`
`I
`
`I}
`I
`
`I
`'
`
`II
`
`I
`
`L
`
`i
`I
`‘;
`(I
`AII
`J
`
`J
`
`I
`
`J
`‘I
`'1
`I
`
`I
`I,II
`1.
`
`J
`
`‘I
`
`I
`
`ISSUING CLASSIFICATION
`cnoss REFERENCE(S)
`
`
`
`
`
`
`
`TERMINAL
`DISCLAIMER
`
`Contxnuedon Issue Slip Inside FIle Jacket
`» WW
`CLAIMSAflBWED
`Total 9m 5
`Print Claim for O.G.
`/,«P’§:O
`7
`
`f
`
`'
`
`
`
`
`
`
`
`
`’
`,
`
`subsequent to
`(dale)' A [an V. A/guygh
`7 [9 I1
`
`
`
`has been disclaImed‘
`IAssIsIanI Examlner)
`
`
`j The term of this patent shall
`i
`
`not extend beyond the expiration date
`
`of US Patent. No.
`
`
`
`—
`
`D The terrnInal
`months of
`this patent have been disclaimedl
`
`WARNING:
`
`
`The InIOImatIon disclosed heveIn may be reslncted Unauthonzed dIsCIosure may be prothIted bfihe United States Code Title 35. Secllons 122, 181 and 368
`
`Possession oulsIde the U.S. Patent a. Trademark Office Is veslncted to aulhonzed employees and contmclors‘only‘
`F°"" "WA
`(Remus?)
`..
`an
`ISSUE Fit-zit; IN FILE
`
`FILED WITH: [:1 DISK (CRF) [:1 FICHE [:1 CD-ROM
`(Aflahdl
`k
`thI Id
`II
`ce npoceIonglnseap
`
`)
`
`. ”I "
`
`.
`
`(FACE)
`
`NOAC EX. 1017 Page 2
`
`
`
`
`
`
`
`NOAC Ex. 1017 Page 2
`
`
`
`Page 1 ofl
`
`
`COMMISSIONER FOR PATENTS
`UNITED STATES PATENT AND TRADEMARK OFFICE
`WASHINGTON. D C. 2023|
`
`www uspto gov
`APPT-001—4
`
`Bib Data Sheet
`
`SERIAL NUMBER
`09/608266
`
`. PPLICANTS
`
`FILING DATE
`06/30/2000
`RULE
`
`CLASS
`37
`0
`
`GROUP ART UNIT
`7
`2 31
`
`ATTORNEY
`DOCKET NO.
`
`Haig A. Sarkissian, San Antonio; TX :1'
`RusseIl S. Dietz, San Joiser‘CA;
`,3/
`@119:
`L w
`* CONTINUING DATAnfiy *******u *t‘ktt‘kit‘ktt‘k
`THIS APPLNJSUG’LIAIMS BENEFIT OF 60/141,903 06/30/1999
`V f"
`/
`* FOREIGN APPLICATIONS ""A*mg’"m
`J
`/
`IF REQUIIRED, FOREIGN FILING LICENSE
`GRANT/ED ** 09/01/2000
`_7
`
`-
`
`I F
`
`oreIgn Enorlty claImed
`
`[:1 yes E no if" 5
`Iii/C]
`Me‘ 3‘19"
`‘AIonva Ge
`"0
`,
`=~
`..
`,2
`:7
`-
`Em; sr-m
`DDRESS ’ /
`
`SHEETS
`STATE OR
`COUNTRY DRAWING
`TX
`21
`
`TOTAL
`CLAIMS
`2O
`
`INDEPENDENT
`CLAIMS
`3
`
`__
`
`Dov Rosenfel
`
`5507 CoIIeg. Avenue
`Suite 2
`
`Oakland ,CA 94618
`
`ITLE
`
`ssociative cache structure for Iookups and updates of flow records In a network monitor
`
`______
`
`
` [11.16 Fees ( Filing)
`C] 1 17 Fees ( Processing Ext. of
`
`tlme)
`C] 118 Fees ( Issue)
`
`M D
`
`Credit
`
`FILING FEE FEES: Authority has been given In Paper
`RECEIVED No.
`to charge/credit DEPOSIT ACCOUNT
`for followmg:
`
`filezl/C:\APPS\PrcExam\correspondence\1_A.xml
`
`1 1/1
`
`NOAC EX. 1017 Page 3
`
`NOAC Ex. 1017 Page 3
`
`
`
`PATENT APPLICATION SERIAL NO.
`
`US. DEPARTMENT OF COMMERCE
`
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`y
`
`PTO-1556
`
`(5/87)
`
`‘US. GPO: 1999-459-GBZI19144
`
`5km,MH
`
`NOAC EX. 1017 Page 4
`
`NOAC Ex. 1017 Page 4
`
`
`
`09—03-100
`
`j:
`
`IN THE US. PATENT AND TRADEMARK OFFICE
`
`Application Transmittal Sheet
`
`Our Ref/Docket No.: APPT—001-4
`
`Box Patent Application
`ASSISTANT COMMISSIONER FOR PATENTS
`Washington, DC. 20231
`
`.
`.
`Dear Assistant Commlssmner:
`
`Transmitted herewith is the patent application of
`
`‘3 E
`2‘4: g
`.\o §
`0'32: E
`3Q E
`‘0 El
`3R5
`we. El
`,9, :
`
`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 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 a
`
`l )
`
`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.
`
` X
`
`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.
`
`Return postcard.
`X
`This application has:
`
`a small entity status. A verified statement:
`is enclosed
`
`was already filed.
`
`The fee has been calculated as shown in the following page.
`
`Certificate of Mailing under 37 CFR 1.10
`
`I hereby certify that this application and all attachments are being deposited with the United States Postal
`Service as Express Mail (Express Mail Label: EI417961895US in an envelope addressed to Box Patent
`Applicatio -
`Assistant Commissioner for Patents, Washington, DC. 20231 on.
`
`Name: Dov Rosenfeld, Reg. No. 38687
`
`Signe .
`
`NOAC EX. 1017 Page 5
`
`
`
`nin
`mHm“11...
`will11..
`Iifill
`
`L‘IIH11ml!
`
`
`
`u...iiii...iiii...ii{i:.:..
`
`
`
`
`
`NOAC Ex. 1017 Page 5
`
`
`
`SUBMISSION DOCUMENT
`ATTORNEY DOCKET NO. APPT-001~4
`
`Page 2
`
`
`
`
`INDEP.
`CLAIMS
`
`TOTAL CLAIMS
`
`NO. OF EXTRA
`CLAIMS
`
`3
`
`EXTRA CLAIM
`FEE
`
`RATE
`
`$78
`
`
`
`BASIC APPLICATION FEE:
`
`$ 690.00
`
`r'
`
`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 amount of § 40.00 is attached for recordation of the Assignment.
`The Commissioner 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 TRANSMITI‘AL IS ATTACHED):
`
`Respectfully Submitted,
`
`
`
`Date
`
`Dov Rosenfeld , Reg. No. 38687
`
`lilillH...“H...”
`
`Ilii,“lI...ll
`
`IillllIIIJI.
`
`1:"”mil
`
`
`
`11...“ll...“Fl...“I122...'22
`
`
`
`
`
`Correspondence Address:
`Dov Rosenfeld
`
`5507 College Avenue, Suite 2
`Oakland, California, 94618
`Telephone: (510) 547-3378; Fax: (510) 653-7992
`
`NOAC EX. 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
`
`
`RECORDS IN A NETWORK MONITOR
`
`
`
`
`LOOKUPS AND UPDATES OF FLOW
`
`Examiner: unassigned
`
`LETTER TO OFFICIAL DRAFTSPERSON
`
`SUBMISSION OF FORMAL DRAWINGS
`
`The Assistant Commissioner for Patents
`
`Washington, DC 20231
`ATTN: Official Draftsperson
`
`Dear Sir or Madam:
`
`Attached please find 2_1_ sheets of formal drawings to be made of record for the above
`identified patent application submitted herewith.
`
`Respectfully Submitted,
`
`3 0 WC
`
`Date
`
`3% X
`
`ov Rosenfeld, Reg. No. 38687
`
`Address for correspondence and attorney 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
`
`vi...”II..."....v‘'1...“fl...“
`
`
`
`
`
`
`.‘IIIIIIIIII’III}...
`
`
`
`
`
`FIJIiiiiin’fizz:“:31M
`
` Certificate of Mailing under 37 CFR 1.10
`I hereby certify that this application and all attachments are being deposited with the United States Postal
`Service as Express Mail (Express Mail Label: EI417961895US in an envelope addressed to Box Patent
`Applicati
`,Assistant Commissioner for Patents, Washington, DC. 202
`
`Date:A 3‘9: W Signed'
`
`N
`
`:
`
`ov Rosenfeld, Reg. No. 38687
`
`NOAC EX. 1017 Page 7
`
`NOAC Ex. 1017 Page 7
`
`
`
`Our Ref./Docket No.2 APPT-OOl-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
`
`
`
`
`
`H..."Ii..."II..."II".......nnu.»
`
`
`
`
`
` Certificate of Mailing under 37 CFR 1.10
`Ihereby certify that this application and all attachments are being deposited with the United States Postal Service as Express Mail
`(ExPreSS Mall Label: EI417961895US in an envelope addressed to Box Patent Application, Assistant Commissioner for Patents,
`
`Washington,
`
`Date:
`
`.C. 20231 on.
`
`E9 W Signed:
`
`g g 2
`
`“t
`
`
`
`
`
`
`
`NOAC EX. 1017 Page 8
`
`NOAC Ex. 1017 Page 8
`
`
`
`(3
`
`II..."H..."II..."n..."u.-.... O
`
`I
`
`\
`
`O
`
`'
`
`D
`
`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 US. 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
`
`‘VI ‘9. P‘ h“ +5 M (K
`incorporated herein by reference.
`This application is related to the following/ILLS. patent applications, each filed
`
`concurrently with the present application, and each assigned to Apptitude, Inc., the
`
`10
`
`assignee of the present invention:
`
`NO. (D,IP\5I( 5?!
`U.S. PatenkApphcatton-Sefla‘I—Nmmg for METHOD AND APPARATUS FOR
`
`MONITORING TRAFFIC IN A NETWORK, to inventors Dietz, et al., filed—.Iuneée;
`
`QQQWemefiAgenLReferenee—Number-AFPT—GOI—L and incorporated herein by
`
`reference.
`
`”0' ("10707671.5
`15 US. PateiigAppkeatron—Wm for PROCESSING PROTOCOL
`
`SPECIFIC INFORMATION IN PACKETS SPECIFIED BY A PROTOCOL
`
`DESCRIPTION LANGUAGE, to inventors Koppenhaver, et al., filed W99;
`
`ArttemeyhArgent—ReferencablumberAPPiILOQI—Q, and incorporated herein by
`
`reference.
`
`cw/gcglié
`
`20 US. Patent Application Serial Nok‘é: for RE—USING INFORMATION FROM
`DATA TRANSACTIONS FOR MAINTAINING STATISTICS IN NETWORK
`
`MONITORING, to inventors Dietz, et al., filedWWW
`
`Reference—NamberAPpT—Qw—g, and incorporated herein by reference.
`(37/6 06,1167
`US. Patent Application Serial NoA‘gs—é/w for STATE PROCESSOR FOR
`PA l'l ERN MATCHING IN A NETWORK MONITOR DEVICE, to inventors
`
`25
`
`Sarkissian, et al., filed-InneSOTZQ
`
`5, and incorporated herein by reference.
`
`FIELD OF INVENTION
`
`The present invention relates to computer networks, specifically to the real-time
`
`NOAC EX. 1017 Page 9
`
`NOAC Ex. 1017 Page 9
`
`
`
`o
`
`3
`
`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 of all
`
`information passing through any point on the network (i.e., of all packets and packet
`
`streams passing through any location in the network). Not only should all the packets be
`
`detected and analyzed, but for each of these packets the network monitor should
`
`determine the protocol (e. g., http, ftp, H.323, VPN, etc.), the application/use within the
`
`protocol (e. g., voice, video, data, real—time data, etc.), and an end user’s pattern of use
`
`within each application or the application context (e. g., options selected, service
`
`delivered, duration, time of day, data requested, etc). Also, the network monitor should
`
`not be reliant upon server resident information such as log files. Rather, it should allow a
`
`user such as a network administrator or an Internet service provider (ISP) the means to
`
`measure and analyze network activity objectively; to customize the type of data that is
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`10
`
`15
`
`20
`
`of network problems.
`
`No. (9,051, 0??
`Related and incorporated by reference U.S. Patenm for
`
`METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A NETWORK, to
`
`25
`
`30
`
`inventors Dietz, et al, AttemeyIAgent—Deeket—AEZI—QG-I—k describes a network monitor
`
`that includes carrying out protocol specific operations on individual packets including
`
`extracting information from header fields in the packet to use for building a signature for
`
`identifying the conversational flow of the packet and for recognizing future packets as
`
`belonging to a previously encountered flow. A parser subsystem includes a parser for
`
`recognizing different patterns in the packet that identify the protocols used. For each
`
`protocol recognized, a slicer extracts important packet elements from the packet. These
`
`form a signature (i. e., key) for the packet. The slicer also preferably generates a hash for
`
`rapidly identifying a flow that may have this signature from a database of known flows.
`
`NOAC EX. 1017 Page 10
`
`i3
`
`6
`
`it;
`
`
`
`NOAC Ex. 1017 Page 10
`
`
`
`o
`
`3
`
`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 of all
`
`information passing through any point on the network (i.e., of all packets and packet
`
`streams passing through any location in the network). Not only should all the packets be
`
`detected and analyzed, but for each of these packets the network monitor should
`
`determine the protocol (e. g., http, ftp, H.323, VPN, etc.), the application/use within the
`
`protocol (e. g., voice, video, data, real-time data, etc.), and an end user’s pattern of use
`
`within each application or the application context (e. g., options selected, service
`
`delivered, duration, time of day, data requested, etc.). Also, the network monitor should
`
`not be reliant upon server resident information such as log files. Rather, it should allow a
`
`user such as a network administrator or an Internet service provider (ISP) the means to
`
`measure and analyze network activity objectively; to customize the type of data that is
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`10
`
`15
`
`20
`
`of network problems.
`
`No. (9,051,099
`Related and incorporated by reference U.S. Patenggm for
`
`METHOD AND APPARATUS FOR MONITORING TRAFFIC INA NETWORK, to
`
`25
`
`30
`
`inventors Dietz, et al,WW describes a network monitor
`
`that includes carrying out protocol specific operations on individual packets including
`
`extracting information from header fields in the packet to use for building a signature for
`
`identifying the conversational flow of the packet and for recognizing future packets as
`
`belonging to a previously encountered flow. A parser subsystem includes a parser for
`
`recognizing different patterns in the packet that identify the protocols used. For each
`
`protocol recognized, a slicer extracts important packet elements from the packet. These
`
`form a signature (i.e., key) for the packet. The slicer also preferably generates a hash for
`
`rapidly identifying a flow that may have this signature from a database of known flows.
`
`NOAC EX. 1017 Page 11
`
`
`
`NOAC Ex. 1017 Page 11
`
`
`
`o
`
`3
`
`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 of all
`
`information passing through any point on the network (i. e., of all packets and packet
`
`streams passing through any location in the network). Not only should all the packets be
`
`detected and analyzed, but for each of these packets the network monitor should
`
`determine the protocol (e.g., http, ftp, H.323, VPN, etc.), the application/use within the
`
`protocol (e. g., voice, video, data, real-time data, etc.), and an end user’s pattern of use
`
`within each application or the application context (e. g., options selected, service
`
`delivered, duration, time of day, data requested, etc.). Also, the network monitor should
`
`not be reliant upon server resident information such as log files. Rather, it should allow a
`
`user such as a network administrator or an Internet service provider (ISP) the means to
`
`measure and analyze network activity objectively; to customize the type of data that is
`
`collected and analyzed; to undertake real time analysis; and to receive timely notification
`
`10
`
`15
`
`20
`
`of network problems.
`
`No. 0,1951, 09?
`Related and incorporated by reference U.S. Patenm for
`
`METHOD AND APPARATUS FOR MONITORING TRAFFIC IN A NETWORK, to
`
`inventors Dietz, et al, AttemeyIAgeat—DeeketAJEP—T-OGH describes a network monitor
`
`that includes carrying out protocol Specific operations on individual packets including
`
`extracting information from header fields in the packet to use for building a signature for
`
`identifying the conversational flow of the packet and for recognizing future packets as
`
`belonging to a previously encountered flow. A parser subsystem includes a parser for
`
`recognizing different patterns in the packet that identify the protocols used. For each
`
`protocol recognized, a slicer extracts important packet elements from the packet. These
`
`form a signature (i.e., key) for the packet. The slicer also preferably generates a hash for
`
`rapidly identifying a flow that may have this signature from a database of known flows.
`
`25
`
`30
`
`NOAC EX. 1017 Page 12
`
`NOAC Ex. 1017 Page 12
`
`
`
`o
`
`3
`
`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
`
`10
`
`15
`
`20
`
`25
`
`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
`
`includinga matching circuit having an input such that the CAM asserts a match output
`
`when the input is the same as the address in the CAM $113313; cache memory
`elerxfignctfia 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
`
`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 puiposes of
`
`explanation. The embodiments, in turn, are explained with the aid of the following
`
`figures.
`
`FIG.11 is a functional block diagram of a network embodiment of the present
`
`invention’in which a monitor is connected to analyze packets passing at a connection
`
`point.
`
`FIG. 2 is a diagram representing an example of some of the packets and their
`
`formats that might be exchanged in starting, as an illustrative example, a conversational
`
`flow between a client and server on a network being monitored and analyzed. A pair of
`
`flow signatures particular to this example and to embodiments of the present invention is
`
`also illustrated. This represents some of the possible flow signatures that can be
`
`NOAC EX. 1017 Page 13
`
`\
`
`2g
`15;
`ES
`
`
`
`NOAC Ex. 1017 Page 13
`
`
`
`O
`
`33
`
`5
`
`generated and used in the process of analyzing packets and of recognizing the particular
`
`server applications that produce the discrete application packet exchanges.
`
`FIG. 3'is a functional block diagram of a process embodiment of the present
`invention that can operate as the packet monitor shown in FIG. 1. This process may be
`/
`
`implemented in software or hardware.
`
`FIG. 4 is a flowchart of a high—level protocol language compiling and
`
`optimization process, which in one embodiment may be used to generate data for
`
`monitoring packets according to versions of the present invention.
`
`FIG. 5 is a flowchart of a packet parsing process used as part of the parser in an
`
`10
`
`embodiment‘of the inventive packet monitor.
`
`FIG. 6 is a flowchart of a packet element extraction process that is used as part of
`
`the parser in an embodiment of the inventive packet monitor.
`
`FIG. 7 is a flowchart of a flow-signature building process that is used as part of
`
`the parser in the inventive packet monitor.
`
`FIG. 8 is a flowchart of a monitor lookup and update process that is used as part
`
`of the analyzer in an embodiment of the inventive packet monitor.
`
`.
`
`I 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
`
`the pattern recognizer and extractor that can form part of the parser module in an
`
`embodiment of the inventive packet monitor.
`
`FIG. 11 is a functional block diagram of a hardware analyzer including a state
`
`processor that can form part of an embodiment of the inventive packet monitor.
`
`FIG. 12 is a functional block diagram of a flow insertion and deletion engine
`
`process that can form part of the analyzer in an embodiment of the inventive packet
`
`monitor.
`
`FIG. 13 is a flowchart of a state processing process that can form part of the
`
`analyzer in an embodiment of the inventive packet monitor.
`
`15
`
`20
`
`25
`
`NOAC EX. 1017 Page 14
`
`
`
`NOAC Ex. 1017 Page 14
`
`
`
`J
`
`3
`
`6
`
`FIG. 14 is a simple functional block diagram of a process embodiment of the
`
`present invention that can operate as the packet monitor shown in FIG. 1. This process
`maybe implemented in software.
`
`FIG. 15 is a functional block diagram of how the packet monitor of FIG. 3 (and
`
`5
`
`FIGS. 10 and 11) may operate on a network with a processor such as a microprocessor.
`
`FIG. 16 is an example of the top (MAC) layer of an Ethernet packet and some of
`
`the elements that may be extracted to form a signature according to one aspect of the
`
`invention.
`
`FIG. 17A is an example of the header of an Ethertype type of Ethernet packet of
`
`10
`
`FIG. 16 and some of the elements that may be extracted to form a signature according to
`
`one aspect of the invention.
`
`FIG. 17B is an example of an IP packet, for example, of the Ethertype packet
`
`shown in FIGs. 16 and 17A, and some of the elements that may be extracted to form a
`
`signature according to one aspect of the invention.
`
`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 accordance to
`
`one embodiment of the invention.
`
`FIG. 18B isra'n'altemate 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 /
`1115 of the analyzer subsystem of FIG. 11.
`’/
`WWW-«su.4, ____‘
`
`
`
`/,-
`
`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 1 1 15.
`
`.3!218
`.52
`
`
`
`NOAC EX. 1017 Page 15
`
`NOAC Ex. 1017 Page 15
`
`
`
`3
`
`3
`
`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
`
`5
`
`invention.
`
`Operation in a Network
`
`FIG. 1 represents a system embodiment of the present invention that is referred to
`
`herein by the general reference numeral 100. The system 100 has a computer network
`
`102 that communicates packets (e. g., IP datagrams) between various computers, for
`
`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
`
`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 programs and of the
`
`netWOrk protocols. Such characteristics may not be completely revealing at the
`
`individual packet level. It may require the analyzing of many packets by the monitor 108
`
`to have enough information needed to recognize particular application programs. The
`
`Packets may need to be parsed then analyzed in the context of various protocols, for
`
`
`
`NOAC EX. 1017 Page 16
`
`NOAC Ex. 1017 Page 16
`
`
`
`::>
`
`3
`
`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, which is also referred to as a protocol
`
`stack. The ISO (International Standardization Organization) has defined a general model
`
`5
`
`that provides a framework for design of communication protocol layers. This model,
`
`W s
`
`hown in table form below, serves as a basic reference for understanding the
`
`functionality of existing communication protocols.
`W
`
`ISO MODEL
`
`Application
`
`
`
`Telnet, NFS, Novell NCP, HTTP,
`
`H.323
`
`s
`
`4
`
`3
`
`2
`
`IP, Novell IPX, VIP, AppleTalk, etc.
`
`Data Link
`
`Network Interface Card (Hardware
`
`Interface). MAC layer
`
`
`
`
`Ethernet, Token Ring, Frame Relay,
`
`
`
`
`
`n-—
`
`
`
`1
`
`Physical
`
`ATM, Tl (Hardware Connection)
`
`Different communication protocols employ different levels of the ISO model or
`
`10
`
`swan...» _,_)_._»,_,..w. ..
`may use a layered model that is similar to but which does not exactly conform to the ISO
`\-..-~._/d
`
`model. A protocol in a certain layer may not be visible to protocols employed at other
`
`layers. For example, an application (Level 7) may not be able to identify the source
`
`computer for a communication attempt (Levels 2—3).
`
`
`
`In some communication arts, the term “frame” generally refers to encapsulated
`
`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
`
`NOAC EX. 1017 Page 17
`
`NOAC Ex. 1017 Page 17
`
`
`
`o
`
`3
`
`9
`
`“packet” generally refers to encapsulated data at 031 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 of the packet. The terms “packet format” and “frame format,” also referred to as
`
`“cell format,” are generally synonymous.
`
`Monitor 108 looks at every packet passing the connection point 121 for analysis.
`
`However, not every packet carries the same information useful for recognizing all levels
`
`of the protocol. For example, in a conversational flow associated with a particular
`
`application, the application will cause the server to send a type-A packet, but so will
`
`another. If, though, the particular application program always follows a type-A packet
`
`with the sending of a type-B packet, and the other application program does not, then in
`
`order to recognize packets of that application’s conversational flow, the monitor can be
`
`available to recognize packets that match the type-B packet to associate with the type—A
`
`packet. If such is recognized after a type—A packet, then the particular application
`
`program’s conversational flow has started to reveal itself to the monitor 108.
`
`Further packets may need to be examined before the conversational flow can be
`
`identified as being associated with the application program. Typically, monitor 108 is
`
`simultaneously also in partial completion of identifying other packet exchanges that are
`
`parts of conversational flows associated with other applications. One aspect of monitor
`
`108 is its ability to maintain the state of a flow. The state of a flow is an indication of all
`
`previous events in the flow that lead to recognition of the content of all the protocol
`
`levels, e.g., the ISO model protocol levels. Another aspect of the invention is forming a
`
`Signature of extracted characteristic portions of the packet that can be used to rapidly
`
`identify packets belonging to the same flow.
`
`In real—world uses of the monitor 108, the number of packets on the network 102
`
`PaSSing by the monitor 108’s connection point can exceed a million per second.
`
`Consequently, the monitor has very little time available to analyze and type each packet
`
`10
`
`15
`
`20
`
`25
`
`30
`
`NOAC EX. 1017 Page 18
`
`
`
`limitu...:-Human...
`
`a”
`3".
`
`A
`
`
`
`NOAC Ex. 1017 Page 18
`
`
`
`),
`
`:
`
`I
`
`l
`
`‘\
`
`D
`
`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
`
`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