(12) United States Patent
`Sarkissian et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,771,646 B1
`Aug. 3, 2004
`
`US006771646B1
`
`(54) ASSOCIATIVE CACHE STRUCTURE FOR
`LOOKUPS AND UPDATES OF FLOW
`RECORDS IN A NETWORK MONITOR
`
`.
`
`-
`
`-
`
`-
`
`-
`
`5,365,514 A
`5,375,070 A
`5,394,394 A
`5,414,650 A
`5,414,704 A
`
`11/1994 Hershey et al.
`12/1994 Hershey et al.
`2/1995 Crowther et al.
`5/1995 Hekhuis .............. .. 364/715.02
`5/1995 Spinney
`
`........... .. 364/550
`
`(US)
`
`(List continued on next page.)
`
`(73) Assignee: Hi/fn, Inc., Los Gatos, CA (US)
`
`FOREIGN PATENT DOCUMENTS
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C.154b b 591 d
`.
`( ) y
`ays
`
`JP
`
`""""" " GOGF/17/30
`2/2003
`02003044510 A *
`OTHER PUBLICATIONS
`R. Periakaruppam and E. Nemeth. “GTrace—A Graphical
`
`<29
`(22)
`
`Filed;
`
`Jun_ 30, 2000
`
`(60)
`
`Related U.S. Application Data
`Provisional application No. 60/141,903, filed on Jun. 30,
`1999-
`Int. Cl.7 .............................................. .. G01R 31/08
`(51)
`(52) U.s. Cl.
`..................... .. 370/392, 370/412, 370/252,
`_
`370/352; 709/223; 711/119
`(58) Field of Search ............................ .. 370/241.1, 252,
`370/253> 352> 353> 355> 389> 392> 401>
`395.1; 709/223, 224
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`3,949,369 A *
`4/1976 Churchill, Jr.
`.............. 711/128
`4,458,310 A *
`7/1984 Chang ................... .. 711/119
`4,559,618 A 4 12/1985 Houseman et alt
`t
`..... N 365/49
`4,736,320 A
`4/1988 Bristol
`..................... .. 364/300
`4,891,639 A
`1/1990 Nakamura ........ ..
`.. 340/825.5
`4,910,668 A *
`3/1990 Okamoto et al.
`711/207
`4,972,453 A
`11/1990 Daniel, H1 et a1-
`--------- -- 379/10
`5»101a402 A
`3/1992 Chi“ 91 31-
`............... .. 370/85.5
`5,247,517 A
`9/1993 Ross et al.
`5,247,693 A
`9/1993 Bristol
`..................... .. 395/800
`5,315,580 A
`5/1994 Phaal
`5,339,268 A
`8/1994 Machida .................... .. 365/49
`5,351,243 A
`9/1994 Kalkunte et al.
`
`
`
`pers/1999/GTrace.pdf.
`W. Stallings. “Packet Filtering in the SNMP Remote Moni-
`tor.” Nov. 1994. Available on wvvw.ddj.com, URL: http://
`WWW.ddj.C0m/documents/S=1013/ddj9411h/9411h.htm.
`“Technical Note: the Narus System,” Downloaded Apr. 29,
`1999 from WWW~harus~C0m, Narus Corporation, Redwood
`CW Ca11f°““a~
`Primary Examiner—Ricky Ngo
`Assistant Emmt-,te,,_A1an V Nguyen
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`
`ABSTRACT
`(57)
`kt
`h
`A
`t
`f
`1
`1
`t
`f
`cac e sys em or oo ng up one or more e emen s o an
`external memory includes a set of cache memory elements
`Coupled 1° 111119 eétAeEa1mem°.ry.’ asetofditontem 2:t‘t1dreSS.ab1e
`memory C9 S(
`5) ‘’°“‘a“““g an a
`I955 an 3‘ P919191
`to one of the cache memory elements, and a matching circuit
`haV1hg ah lhput such that the CAM asserts a thatch Output
`when the input is the same as the address in the CAM cell.
`The cache memory element which 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
`bettem CAM petttts te the least teeetttly used eaehe memety
`element
`‘
`
`20 Claims, 21 Drawing Sheets
`
`
`
`
`PARSER
`5&1
`
`PACKET
`'CQU|S|TlON
`DEVICE
`
`DATABASE
`OF
`FLOWS
`H H o :5
`
`HOST
`PROCESSO
`
`
`
`MONITOR
`10.0
`
`NETWORK
`INTERFACE
`CARD
`
`Petitioners‘ EX1001 Page 1
`
`Petitioners' EX1001 Page 1
`
`

`
`US 6,771,646 B1
`Page 2
`
`5,805,808 A
`5,812,529 A
`5,819,028 A
`
`.......... .. 395/200.2
`........... .. 370/245
`
`9/1998 Hasani et al.
`9/1998 Czarnik et al.
`10/1998 Manghirmalani
`er a1.
`..................... N 395/185.1
`10/1998 Ready et al.
`............. .. 370/401
`5,825,774 A
`11/1998 shwed er a1.
`........ N 395/200.59
`5,835,726 A
`
`11/1998 Yoshroka er a1.
`.... N 711/207
`5,835,963 A
`11/1998 Schwalleretal.
`395/200.54
`5,838,919 A
`11/1998 Huffman ................... .. 382/155
`5,841,895 A
`
`12/1998 Anderson et al.
`370/241
`5,850,386 A
`......... N 370/252
`12/1998 Anderson et a1.
`5,850,388 A
`1/1999 Sell .......................... .. 711/146
`5,860,114 A
`1/1999 Welchj Jr. et a1.
`N 39530054
`5,862,335 A
`
`3/1999 de la Salle ................. .. 707/10
`5,878,420 A
`4/1999 Cheriton ................... .. 711/144
`5,893,155 A
`5/1999 Pearson rrrrrrrr N
`395/680
`5,903,754 A
`6/1999 Gobuyan et al.
`......... .. 370/392
`5,917,821 A
`6,003,123 A * 12/1999 Carter et al.
`.............. .. 711/207
`6,014,380 A
`1/2000 Hendel er a1.
`370/392
`6,115,393 A
`9/2000 Engeletal.
`.............. .. 370/469
`6,279,113 B1
`8/2001 Vaidya ..................... .. 713/201
`
`6,330,226 B1
`12/2001 Chapman et a1.
`370/232
`............... .. 370/252
`6,363,056 B1
`3/2002 Beigi et al.
`6,424,624 B1
`7/2002 Galand er a1.
`............ N 370/231
`
`6,625,657 B1
`9/2003 Bnllard rrrrrr N
`709/237
`............... .. 709/224
`6,651,099 B1
`11/2003 Dietz et al.
`
`
`
`* cited by examiner
`
`Petitioners‘ EX1001 Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,432,776 A
`5,493,689 A
`5,500,855 A
`5,511,215 A
`5,530,834 A *
`5,530,958 A *
`5,535,338 A
`5,568,471 A
`5,574,875 A
`5,586,266 A
`5,606,668 A
`5,608,662 A
`5,634,009 A
`5,651,002 A
`5,684,954 A
`5,703,877 A
`5,720,032 A
`5,732,213 A
`5,740,355 A
`5,749,087 A *
`5,761,424 A
`5,764,638 A
`5,781,735 A
`5,784,298 A
`5,787,253 A
`5,802,054 A
`
`...... .. 395/821
`
`7/1995 Harper
`2/1996 Waclawsky et al.
`3/1996 Hershey et ah
`4/1996 Terasaka et al.
`.......... .. 395/800
`6/1996 Colloff et al.
`............ .. 711/136
`
`6/1996 Agarwal er a1
`711/3
`7/1996 Krause er a1 ~~~~~~~~~ ~~ 395/2002
`10/1996 Hershey et ah
`........ .. 395/403
`11/1996 Stansfield et al.
`12/1996 Hershey et ah ~~~~~~ ~~ 395/20011
`2/1997 Shwed ................ .. 395/200.11
`
`3/1997 Large er a1 ~
`~ 364/724,01
`5/1997 Idderr er a1 ~~~~~~~~~ ~~ 395/20011
`7/1997 Van Seters et al.
`....... .. 370/392
`
`11/1997 Kaiserswerth et ah
`395/2002
`~~~~~~~~~~~~~~ ~~ 370/395
`12/1997 Nuher et a1-
`2/1998 Picazo, Jr. et al.
`..... .. 395/200.2
`
`~ 395/20011
`3/1998 Gessel er a1 ~~~~ ~
`4/1998 Watarrahe et ah ,,,, ~ 395/18321
`5/1998 Hoover et al.
`............ .. 711/108
`
`6/1998 Adams er a1 ~~
`395/20047
`6/1998 Ketchum .................. .. 370/401
`7/1998 Southard ............. .. 395/200.54
`
`7/1998 Hershey er a1 ~
`,,,, ~~ 364/557
`7/1998 McCreery et al.
`395/200.61
`9/1998 Bellenger
`................. .. 370/401
`
`Petitioners' EX1001 Page 2
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 1 of 21
`
`US 6,771,646 B1
`
`100 —
`CLIENT 4
`
`”\
`107
`
`ANALYZER
`
`103
`
`CUENT3
`
`\
`106
`
`116
`
`W10
`
`121
`
`DATA COMMUNICATIONS
`
`NETWORK
`
`102
`
`125
`
`118
`T
`SERVER 4 6 105 */
`W
`CLIENT 2
`CLIENT 1 —\
`112
`104
`
`123
`
`FIG. 1
`
`Petitioners‘ EX1001 Page 3
`
`Petitioners' EX1001 Page 3
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 2 of 21
`
`US 6,771,646 B1
`
`EE_____aH
`
`
`
`mmmvmmmEmommEmmay
`
`N_.NQFN
`
`mmmmmmENommmmmmmmNNNomm
`mmmVNNKHEM_
`
`Emu9%NR
`ENONN
`¢¢
`
`u
`
`fiasco.EBMU
`
`Emnewmom
`-Ha,,,_uu5%8%
`
`m._.Zm_._O
`
`Petitioners‘ EX1001 Page 4
`
`Petitioners' EX1001 Page 4
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 3 of 21
`
`US 6,771,646 B1
`
`mm<m<»<o
`
`950.:no
`
`Smoomm
`
`
`
`0..."...zmz
`
`(ma
`
`momoomm
`
`
`
`2252.....
`
`zoP<smou_z_
`
`
`
`69.00.._m:o_z:.S5m.6<Exm_
`
`SDI“.o_.Emmm>zoo
`
`
`.oz_>uEzmo_
`
`
`
`Jon\V_mod:mmm<n_
`
`.5._Sm
`
`n_z<m~>._<z<
`
`muzwoomm
`
`zmm._.._.<m
`
`F5
`
`Z._.<O_...=w.w<._U
`
`zO_.—.<N3<Z.u_
`
`E,
`
`oz
`
`‘N8
`
`So
`
`Qmm~>..<z<
`
`macs.
`
`zoE§mn_o
`
`uzmmwooma
`
`.zo_»<mwn_o
`
`m>
`
`m.€E:
`
`..>>O....._..
`
`Z>>OZv._
`
`omoomm
`
`.2o:<o_u__mm<._o
`
`mics.
`
`mpfiwwJooopocm
`
`ZO:.<U_u__._.Zwo_
`
`.__
`
`_.
`
`mm<m<»<o_zo_.5<E.xm
`
`m.E¢w
`
`commmoomm
`
`zoFo:Ewz_
`
`mw<m<»<o
`
`_2<mo<.Eo
`
`mm><._
`
`mm._Es.oo
`
`n.z<
`
`mm~_s__Eo
`
`Petitioners‘ EX1001 Page 5
`
`Petitioners' EX1001 Page 5
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 4 of 21
`
`US 6,771,646 B1
`
` HIGH LEVEL
`‘I ESCRIPTION ‘
`
`PACKET
`DECODING
`
`407
`
`
`GENERATE
`PCKET
`PACKET
`STATE
`COMPILE
`PARSE AND
`INSTRUCTION
`
`AND
`EXTRACT
`
`OPERATIONS
`°PER'°‘T'°NS
`
`
`
`
`
`
`
`
`
`
`
`406 7/ATTERN, PARS
`STATE
`PROCESSOR
`AND
`
`INSTRUCTION
`EXTRACTION
`DATABASE
`DATABASE
`
`
`
`
`
`
`LOAD STATE
`NSTRUCTION
`DATABASE
`MEMORY
`
`
`
`
`
`LOAD
`PARSING
`SUBSYSTEM
`MEMORY
`
`
`
`400
`
`Petitioners‘ EX1001 Page 6
`
`
`
`Petitioners' EX1001 Page 6
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 5 of 21
`
`US 6,771,646 B1
`
`“
`
`501
`
` 502
`
`LOAD PACKET
`COMPONENT
`
`
`
`ORE IN PACKE Iv»
`
`
`503
`
`504
`
`
`
`FETCH NODE AN I
`PROCESS FROM
`PATTERN
`
`
`
`
`
`510
`
`,
`PATTERN
`NODE
`
`509
`
`EXTRACT
`ELEMENTS
`
`512
`
`I
`: I
`PACKET
`KEY
`
`513
`
`500
`
` MORE
`NEXT
`PATTERN
`PACKET
`NODES?
`COMPONE 511
`
`
` ‘I-V‘..
`PROCESS TO
`COMPONENT
`
`FIG. 5
`
`Petitioners‘ EX1001 Page 7
`
`Petitioners' EX1001 Page 7
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 6 of 21
`
`US 6,771,646 B1
`
`‘
`
`601
`
`PACKET
`COMPONENT AND
`PATTERN NODE
`
`602
`
`603
`
`604
`
`LOAD PACKET
`COMPONENT
`
`
`
`
`MORE PACKE
`COMPONENT
`
`YES
`
`FETCH EXTRACTION
`
`‘ ND PROCESS FROM
`PATTERNS
`
`605
`
`NO
`
`606
`
`507
`
`510
`
`LOAD KEY
`BUFFER
`
`6
`
`611
`
`609
`
`\
`
`600
`
`
`
`ELEMENTS?
`
`ORE EXTRACTIO ‘
`
`N I
`
`NEXT
`PACKET
`COM PONEN
`
`
`
`
`
`503
`
`YE
`
`YES
`
`APPLY EXTRACTION
`E|3OC%SS TO
`MP NENT
`
`
` MORE TO
`EXTRACT?
`
`
`
`
`
`
`FIG. 6
`
`Petitioners‘ EX1001 Page 8
`
`Petitioners' EX1001 Page 8
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 7 of 21
`
`US 6,771,646 B1
`
`“
`
`701
`
`EY BUFFER AND
`PATTERN NODE
`
`702
`
`703
`
`704
`
`LOAD PATTERN
`NODE ELEMENT
`
`
`
`MORE PATTERN
`NQDES?
`
`
`
`YES
`
`HASH KEY BUFFER
`ELEMENT FROM
`PATTERN NODE
`
`705
`
`PACK KEY & HAS
`
`NEXT PACKET
`COMPONENT
`
`706
`
`707
`
`FIG. 7
`
`708
`
`OUTPUT TO
`ANALYZER
`
`@
`
`709
`
`\
`
`700
`
`Petitioners‘ EX1001 Page 9
`
`Petitioners' EX1001 Page 9
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 8 of 21
`
`US 6,771,646 B1
`
`“ 801
`
`UFKB ENTRY FOR
`PACKET
`
`802
`
`800 \
`
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH
`
`303
`
`REQUEST RECORD B|N/
`BUCKET FROM CACHE
`
`804
`
`806
`
`
`
`805
`
` ORE BUCKET
`
`IN THE BIN?
`
`YES
`
`NO
`
`SET UFKB FOR
`PACKET AS ‘NEW’
`
`COMPARE CURRENT BIN
`AND BUCKET RECORD KEY
`TO PACKET
`
`807
`
`NEXTBUCKET N _ 808
`
`YES
`
`809
`
`MARK RECORD BIN AND
`
`BUCKET ‘IN PROCESS‘ IN
`CACHE AND TIMESTAMP
`
`810
`
`8“
`
`812
`
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`mm FIG. 8
`
`Petitioners‘ EX1001 Page 10
`
`Petitioners' EX1001 Page 10
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 9 of 21
`
`US 6,771,646 B1
`
`901
`
`902
`
`910
`
`' ORTMAPP '
`
`RPC
`BIND LOOKU '
`REQUEST
`
`909
`
`
`
`
` EXTRACT PROGRAM
`EXTRACT PORT
`
`GET 'PROGRAM‘,
`‘VERSION’, 'PORT' AND
`‘PROTOCOL (TCP OR
`
`UDP)
`
`GET 'PROGRAM‘,
`‘VERSION’ AND
`‘PROTOCOL (TCP OR
`UDP)‘
`
`
`
`CREATE SERVER STAT
`
`908
`
`SAVE REQUEST
`
`SAVE ‘PROGRAM’,
`
`SAVE ‘PROGRAM’,
`'VERS|ON‘ AND
`
` 904
`‘PROTOCOL (TCP OR
`‘VERSION‘, 'PORT' AND
`
`UDP)‘ WITH
`‘PROTOCOL (TCP OR
`
`UDP)‘ WITH NETWORK
`DESTINATION
`
`ADDRESS IN SERVER
`NETWORK ADDRESS.
`STATE DATABASE. KEY
`BOTH MAKE A KEY.
`
`ON SERVER ADDRESS
`
`AND TCP OR UDP PORT.
`
`
`
`
`
`RPC
`BIND
`
`LOOKUP
`REPLY
`
`
`
`EXTRACT
`PROG RAM
`
`GET 'PORT' AND
`
`
`
`‘PROTOCOL (TCP
`OR UDP)‘.
`
`
`
`FIND ‘PROGRAM'
`AND ‘VERSION'
`WITH LOOKUP OF
`SOURCE NETWORK
`ADDRESS.
`
`
`
`
`
`
`LOOKUP REQUE "
`
`900/
`
`FIG. 9
`
`Petitioners‘ EX1001 Page 11
`
`
`
`Petitioners' EX1001 Page 11
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 10 of 21
`
`US 6,771,646 B1
`
` PATTERN
`
`100
`
`100‘
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`100
`
`1031
`
`1004
`
` INFOOUT
`
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS
`
`CONTRL N
`
`1031
`
`1007
`
`
`
`EXTRA TION EN INE
`(CSLICER) G
`
`PATTERN
`RECOGNITN
`ENGINE
`(PRE)
`
`10°
`
`100:
`
`
`
`PARSER
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`MEMORY
`
`PARSER INPUT BUFFER
`MEMORY
`
`
`
`PA KET
`INPUT
`
`
`
`
`
`
`1012
`
`1021
`
`PACKET
`START
`‘
`V
`
`PACKET
`
`INPUT BUFFER
`INTERFACE
`CONTROL
`
`ANALYZER
`INTERFACE
`CONTROL
`
`DATA REA I’
`
`
`ANALYZER
`REAJTY
`
`
`
`102
`1023
`
`1027
`
`Petitioners‘ EX1001 Page 12
`
`Petitioners' EX1001 Page 12
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 11 of 21
`
`US 6,771,646 B1
`
`1100 3
`
`1101
`
`1103
`
`1115
`
`1118112
`
`1107
`
`
`
`
`PROCESS '<
`lNSTRUCN
`
`DATABASE
`(SPID)
`
`LOOKUP/
`
`
`
`UNIFIED
`FLOW
`
`PARSER ~ KEY
`|NTER-
`UFFER
`(UFKB)
`FACE
`
`
`
`
`PROCESSR
`(SP)
`
`1119112
`
`
`
`
`INSERTIONI
`
`
` FLOW
`
`UNIFIED
`MEMORY
`
`MEMORY
`INTER-
`
`Petitioners‘ EX1001 Page 13
`
`Petitioners' EX1001 Page 13
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 12 of 21
`
`US 6,771,646 B1
`
`1 202
`
`1203
`
`1204
`
`1201
`
`
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`ACCESS
`CONVERSATION
`RECORD BIN
`
`
`
`
`
`
`
`
`
`
`
`
`
`1200
`
`5‘
`
`
`
`REQUEST RECORD B|N/
`BUCKET FROM CACHE
`
`
`
`1206
`
`
`REQUEST NEXT
`BUCKET FROM
`
`CACHE
`
`
`IN/BUCKET EMPTY
`
`1205
`
`YES
`
`1207
`
`1208
`
`;
`
`NO INSERT KEY AND HASH
`N BUCKE'|', MARK ‘USED
`WITH TIMESTAMP
`
`
`
`OMPARE CURRENT BIN 1209
`AND BUCKET RECORD
`KEY TO PACKET
`
`1210
`
`SET UFKB FOR
`PACKET AS
`'DROP'
`
`YES
`
`
`
`MARK RECORD BIN AND
`BUCKET ‘IN PROCESS‘
`AND 'NEW' IN CACHE
`
`1211
`
`SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`
`
`1213
`
`
`
`FIG. 12
`
`Petitioners‘ EX1001 Page 14
`
`Petitioners' EX1001 Page 14
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 13 of 21
`
`US 6,771,646 B1
`
`1300 TA
`
`%FKB ENTRYSFOR S
`
`PA KET WITH TATU
`'NEW' R 'FOUND'
`I
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO
`ALUE FOUND IN UFKB ENTRY
`
`FETCH INSTRUCTION FROM
`STATE PROCESSOR
`INSTRUCTION MEMORY
`
`1302
`
`1303
`
`1304
`
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION
`
`1305
`
`SET STATE
`
`
`
`
`
`
`
`
`PROCESSOR
`
`INSTRUCTION
`NO
`DONE PROCESSING
`POINTER TO
`STATES FOR THIS
`VALUE FOUND IN
`PACKET?
`CURRENT STATE
`
`
`
`1307
`
`1309
`
`1308
`1310
`
`YES
`
`
`
`DONE PROCESSING
`
`
`
`
`
`NO
`
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`TATES FOR THIS FLOW‘?
`FLOW RECORD
`
`YES
`
`SET AND SAVE FLOW REMOVA
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`
`Petitioners‘ EX1001 Page 15
`
`Petitioners' EX1001 Page 15
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 14 of 21
`
`US 6,771,646 B1
`
`—..——.1:1——-...———.:—————.__.:1—._:11-_1—1
`
`mw<m<»<o
`
`m>>o.Eu_O
`
`m._.<Dn_3
`
`=§OI.E_.
`
`z>>ozv_
`
`DEOOME
`
`ZO_._.<N_.._<Z_n._
`
`._.<0_m_mQ30
`
`mmN>._<z<
`
`sm=m>wm:m
`
`
`
`comma9.2.zmm.E.<n_
`
`
`
`oz_E:zma_mmzooomm
`
`oz<m~>._<z.
`
`zo:<s_mou_z_
`
`mmm3._.O_.=..._._.m
`
`zmmti
`
`zo:o<Exm
`
`mzoF<mmn_o
`
`oz<.
`
`mpfim
`
`m_z_:o<s_
`
`m9.om._wm
`
`09._.
`
`m._.<....m
`
`m_m>._<z<
`
`_s_mm>wm:m
`
`Petitioners‘ EX1001 Page 16
`
`mm.....m<n_
`
`____________
`
`Petitioners' EX1001 Page 16
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 15 of 21
`
`US 6,771,646 B1
`
`._.mOI
`
`>mos_m__2
`
`mo:zo_>_
`
`an
`
`E.
`
`v_m_O>>._.m_z
`
`m_O<u_mm_._.Z_
`
`n_m<o
`
`N2
`
`nm_N>:_<Z<
`
`mom
`
`mmmm<n_
`
`Sm
`
`._.m_v_O<n_
`
`Petitioners‘ EX1001 Page 17
`
`Petitioners' EX1001 Page 17
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 16 of 21
`
`US 6,771,646 B1
`
`I
`
`Dst MAC (6)
`
`Dst Hash (2
`
`Petitioners‘ EX1001 Page 18
`
`Petitioners' EX1001 Page 18
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 17 of 21
`
`US 6,771,646 B1
`
`1 702
`
`ff12°51
`
`1 704
`
`X
`
`1706
`
`1708
`1710
`
`H
`
`Type (2)
`h 1
`)
`et =14
`
`VK__1700
`
`1CHAOSNET = 0x0804
`
`IDP = 0X0600*
`IP = 0x0800*
`
`ARP = 0x0806
`VIP = OXOBAD*
`VLOOP = OXOBAE
`VECHO = OXOBAF
`NETBIOS-3COM = OX3C0O -
`0x3COD#
`DEC-MOP = OXGOO1
`DEC-RC = Ox6002
`DEC-DRP = 0x6003*
`DEC-LAT = 0x6004
`DEC-DIAG = OXGOO5
`DEC-LAVC = OXGOO7
`RARP = 0X8035
`ATALK = 0x809B*
`VLOOP = 0X80C4
`VECHO = 0x8OC5
`SNA-TH = 0x8OD5*
`ATALKARP = 0x80F3
`IPX = Ox8137*
`SNMP = 0x814C#
`IPv6 = 0x86DD*
`LOOPBACK = 0x9000
`
`Apple = 0xO80007
`* L3 Decoding
`# L5 Decoding
`
`1 752
`
`FIG. 17A /
`
`1712
`
`
`
`,s1'a7n'.1.I11:»'I:;1':4z1rIi:-7.=*I.';i:1~»7II/I1
` r’-7'
`-7
`..
`.,
`.. 67-" .7
`7IIA7III’IAWI.%%‘L='£'.1:’.='i~1’{¢21fi:1
`
`
`
`L3to
`[L3 +
`
`"'1§’4
`
`Dst Address—
`
` VIIIIII:Lwiifiwiiizwlllllllllllfl
`
` ICMP = 1
`
`
`
`IGMP = 2
`GGP = 3
`TCP = 6*
`EGP = 8
`IGRP = 9
`PUP = 12
`CHAOS = 16
`UDP = 17*
`IDP = 22#
`ISO-TP4 = 29
`DDP = 37#
`ISO-IP = 80
`VIP = 83#
`EIGRP = 88
`OSPF = 89
`
`
`
`
`* L4 Decoding
`# L3 Re-Decoding
`
`Dst Address
`
`
`
`
`Dst Hash (2)
`
`
`
`om
`
`
`
`
`
`
`FIG. 17B
`
`et = L3 + (IHL/4)
`
`Petitioners‘ EX1001 Page 19
`
`Petitioners' EX1001 Page 19
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 18 of 21
`
`US 6,771,646 B1
`
`PROTOCOL
`TYPE (IDZ
`
`mIi,Kii\ \
`niuuunnii!
`IihIIII§
`iiiIiIII\
`5....$1
`--hill!
`
`\
`
`EIH n
`
`.\IIIIIiii
`uiiimnnunMninth!III
`
`~=
`QM.
`857.)
`
`1642
`
`
`
`_.:.wzm._n_._m__u_
`
`1802-1
`
`FIG. 18A
`
`058O
`
`LUT NUM
`Om
`
`870
`
`o._m_n_n_O
`
`
`
`Q00.u.._._.>m
`
`._ooo5m_n_
`
`MHIFQE
`
`FIG. 18B
`
`Petitioners‘ EX1001 Page 20
`
`Petitioners' EX1001 Page 20
`
`
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 19 of 21
`
`US 6,771,646 B1
`
`82kova,
`|._m_mn_mK|.m_mm_:._
`
`
`fl<+<o-<o-o-o_>5
`
`22l._mwm_o:
`
`mrmvmom?
`D|wmm_moo<-<o
`
`ii‘
`
`82
`
`
`
`
`
`wm_x:s_5m_._mm._.Dn_Z_
`
`
`
`
`
`Z_-5-m_o<n_Z_.o.m_O<n_
`
`:2
`
`
`
`mmmomfimm_.:E>m__._o<o
`
`ivSo-5-m_o<n_
`
`
`
`$9mm_o.&_>_<mEon._<DD
`
`
`
`._.DO-o-m_.®<n_
`
`
`
`<»<o-o_>5-<omom_.
`
`22I
`
`
`
`._mmm_0<n_<O
`
`
`
`._mmm5._E<oV%
`
`22
`
`HSEWM
`
`Im_mma_u_
`
`Iimmmmmess.Bm_._mm.5E.3O<EovTa6
`
`
`
`
`
`Petitioners‘ EX1001 Page 21
`
`Petitioners' EX1001 Page 21
`
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 20 of 21
`
`US 6,771,646 B1
`
`2001
`
`2005
`
`
`
`<>E
`E
`<|
`E
`0
`
`
`
`
`
`I-
`g
`CL
`Lu
`3
`
`%
`:1
`UJ
`E
`
`LUEMEMREQ
`ETL EREADY
`S
`U
`SETLUESEL
`
`FIDEMEMREQ
`SETFIDEREADY
`SETFIDESEL
`
`
`
`SEL_LUE_F|DE—>
`CAM_H|T
`
`CAM_H|TPAGE
`
`CACHE_CAM_SM
`
`C
`
`AM LR PA E
`
`G
`U
`—
`LOAD_CAM
`
`FiEFFiESH_CAM
`
`GET BACKUP GOT/2003
`
`SEL_CACHE—>
`
`
`
`CACHEPORT
`
`
`
`# CACHE_MEM_SM
`
`CACHE ME
`
`SIGNALS
`
`
`CA-MEM-WRIT
`
`
`CA-MEM-RE
`
`UMC-O-CA-NEXTA
`
`UMC-O-CA-REA
`
`UMC
`
`FIG. 20
`
`Petitioners‘ EX1001 Page 22
`
`Petitioners' EX1001 Page 22
`
`

`
`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 21 of 21
`
`US 6,771,646 B1
`
`CAM_HlTPAGE. REF-DATA
`
`CAM_LRUPAGE, FlEF- DATA
`2109
`
`LOAD, REFRESH. EVICT
`
`_
`
`211 i REF DATA
`CAM_|NPUTDATA
`
`1
`
`2103
`
`2113
`
`21
`
`05
`
`E
`2
`m
`1-
`E
`%
`
`5T0 32
`
`DECOD
`
`°’°‘M—”,"MBER
`I
`2127 DATA
`
`LOADO
`
`LOAD1
`
`LOAD2
`
`LOAD3
`
`LOAD4
`
`LOAD5
`
`LOAD6
`
`LDAD7
`
`CAM[0]
`DAT -Jr
`CAM[1]
`DAT J,
`CAM[2]
`Jr
`CAM[3]
`J
`CAM4]
`t
`CAM[5]
`~.v
`CAM[6]
`D
`CAM{7]
`
`MATCHO
`
`.
`
`MATCH1
`
`MATCH2
`
`MATCH3
`
`MATCH4 32 To 5
`
`2115
`
`MATCH5 _
`
`MATCH6
`
`MATCH7
`
`CAM
`HIGH H”
`
`E
`o
`D.
`Q.
`3
`g
`
`
`
`
`1
`- - ~ DATA31
`
`I
`DATA
`
`A
`
`-
`
`CAM NUMBER
`I
`- o DATA31
`
`- — E6’ 3123 Tm?
`J
`2121
`.1.
`DIRTY ENTRY
`cunnem ENTRY
`DlRTY_PAGE. DIHTY_HASH, DlRTY_BUCKET
`CAM__HlTPAGE
`V
`
`FIG. 21
`
`V\.
`
`2””
`
`2117
`
`Petitioners‘ EX1001 Page 23
`
`Petitioners' EX1001 Page 23
`
`

`
`US 6,771,646 B1
`
`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 Ser. No.: 60/141,903 for METHOD AND
`APPARATUS FOR MONITORING TRAFFIC IN A NET-
`WORK to inventors Dietz, et al., filed Jun. 30, 1999, the
`contents of which are incorporated herein by reference.
`This application is related to the following U.S. patents
`and U.S. patent applications, each filed concurrently with
`the present application, and each assigned to Apptitude, Inc.,
`the assignee of the present invention:
`U.S. Pat. No. 6,651,099 for METHOD AND APPARA-
`TUS FOR MONITORING TRAFFIC IN A NETWORK, to
`inventors Dietz, et al., and incorporated herein by reference.
`U.S. Pat. No. 6,665,725 for PROCESSING PROTOCOL
`SPECIFIC INFORMATION IN PACKETS SPECIFIED BY
`A PROTOCOL DESCRIPTION LANGUAGE, to inventors
`Koppenhaver, et al.,-filed and incorporated herein by refer-
`ence.
`
`U.S. patent application Ser. No. 09/608,126 for
`RE-USING INFORMATION FROM DATA TRANSAC-
`TIONS FOR MAINTAINING STATISTICS IN NET-
`WORK MONITORING, to inventors Dietz, et al., filed and
`incorporated herein by reference.
`U.S. patent application Ser. No. 09/608,267 for STATE
`PROCESSOR FOR PATTERN MATCHING IN A NET-
`WORK MONITOR DEVICE, to inventors Sarkissian, et al.,
`and incorporated herein by reference.
`FIELD OF INVENTION
`
`The present invention relates to computer networks, spe-
`cifically to the real-time elucidation of packets communi-
`cated within a data network, including classification accord-
`ing 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 applica-
`tion programs being used. Such a monitor should enable
`non-intrusive, remote detection, characterization, analysis,
`and capture of all information passing through any point on
`the network (i.e., of all packets and packet streams passing
`through any location in the network). Not only should all the
`packets be detected and analyzed, but for each of these
`packets the network monitor should determine the protocol
`(e.g., http, ftp, H.323, VPN, etc.), the application/use within
`the protocol (e.g., voice, video, data, real-time data, etc.),
`and an end user’s pattern of use within each application or
`the application context
`(e.g., options selected, service
`delivered, duration, time of day, data requested, etc.). Also,
`the network monitor should not be reliant upon server
`resident information such as log files. Rather, it should allow
`a user such as a network administrator or an Internet service
`
`provider (ISP) the means to measure and analyze network
`activity objectively; to customize the type of data that is
`collected and analyzed; to undertake real time analysis; and
`to receive timely notification of network problems.
`Related and incorporated by reference U.S. Pat. No.
`6,51,099 for METHOD AND APPARATUS FOR MONI-
`
`2
`TORING TRAFFIC IN A NETWORK, to inventors Dietz,
`et al, 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 conversa-
`tional 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 pat-
`terns in the packet that identify the protocols used. For each
`protocol recognized, a slicer extracts important packet ele-
`ments from the packet. These form a signature (i.e., key) for
`the packet. The slicer also preferably generates a hash for
`rapidly identifying a flow that may have this signature from
`a database of known flows.
`
`The flow signature of the packet, the hash and at least
`some of the payload are passed to an analyzer subsystem. In
`a hardware embodiment, the analyzer subsystem includes a
`unified flow key buffer (UFKB) for receiving parts of
`packets from the parser subsystem and for storing signatures
`in process, a lookup/update engine (LUE) to lookup a
`database of flow records for previously encountered con-
`versational flows to determine whether a signature is from
`an existing flow, a state processor (SP) for performing state
`processing, a flow insertion and deletion engine (FIDE) for
`inserting new flows into the database of flows, a memory for
`storing the database of flows, and a cache for speeding up
`access to the memory containing the flow database. The
`LUE, SP, and FIDE are all coupled to the UFKB, and to the
`cache.
`
`Each flow-entry includes one or more statistical measures,
`e.g., the packet count related to the flow, the time of arrival
`of a packet, the time differential.
`In the preferred hardware embodiment, each of the LUE,
`state processor, and FIDE operate independently from the
`other two engines. The state processor performs one or more
`operations specific to the state of the flow.
`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 expedit-
`ing 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 maximized.
`Prior art caches, for example, can use a lookahead mecha-
`nism to predict both instruction cache lookups and data
`cache lookups. Such lookahead mechanisms are not avail-
`able for a cache subsystem for the packet monitoring appli-
`cation. 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.
`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 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 likely that a
`packet associated with the least recently used flow-entry will
`soon arrive.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`Ahash 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.
`
`65
`
`There thus is a need for a associative cache subsystem that
`also includes a LRU replacement policy.
`
`Petitioners‘ EX1001 Page 24
`
`Petitioners' EX1001 Page 24
`
`

`
`US 6,771,646 B1
`
`3
`SUMMARY
`
`Described herein is an associative cache system for look-
`ing 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 when the input is the same as the address in
`the CAM cell. The cache memory element which a particu-
`lar 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 pro-
`vided only for
`the purposes of explanation. The
`embodiments, in turn, are explained with the aid of the
`following figures.
`FIG. 1 is a functional block diagram of a network embodi-
`ment of the present invention in which a monitor is con-
`nected 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 signa-
`tures that can be 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 embodi-
`ment 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 embodi-
`ment may be used to generate data for monitoring packets
`according to versions of the present invention.
`FIG. 5 is a flowchart of a packet parsing process used as
`part of the parser in an embodiment of the inventive packet
`monitor.
`
`FIG. 6 is a flowchart of a packet element extraction
`process that is used as part of the parser in an embodiment
`of the inventive packet monitor.
`FIG. 7 is a flowchart of a flow-signature building process
`that is used as part of the parser in the inventive packet
`monitor.
`
`FIG. 8 is a flowchart of a monitor lookup and update
`process that is used as part of the analyzer in an embodiment
`of the inventive packet monitor.
`FIG. 9 is a flowchart of an exemplary Sun Microsystems
`Remote Procedure Call application than may be recognized
`by the inventive packet monitor.
`FIG. 10 is a functional block diagram of a hardware parser
`subsystem including the pattern recognizer and extractor
`that can form part of the parser module in an embodiment of
`the inventive packet monitor.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`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.
`FIG. 14 is a simple functional block diagram of a process
`embodiment of the present invention that can operate as the
`packet monitor shown in FIG. 1. This process may be
`implemented in software.
`FIG. 15 is a functional block diagram of how the packet
`monitor of FIG. 3 (and FIGS. 10 and 11) may operate on a
`network with a processor such as a microprocessor.
`FIG. 16 is an example of the top (MAC) layer of an
`Ethernet packet and some of the elements that may be
`extracted to form a signature according to one aspect of the
`invention.
`
`FIG. 17A is an example of the header of an Ethertype type
`of Ethernet packet of FIG. 16 and some of the elements that
`may be extracted to form a signature according to one aspect
`of the invention.
`
`FIG. 17B is an example of an IP packet, for example, of
`the Ethertype packet shown in FIGS. 16 and 17A, and some
`of the elements that may be extracted to form a signature
`according to one aspect of the invention.
`FIG. 18A is a three dimensional structure that can be used
`
`to store elements of the pattern, parse and extraction data-
`base used by the parser subsystem in accordance to one
`embodiment of the invention.
`
`FIG. 18B is an alternate form of storing elements of the
`pattern, parse and extraction database used by the parser
`subsystem in accordance to another embodiment of the
`invention.
`
`FIG. 19 is a block diagram of the cache memory part of
`the cache subsystem of the analyzer subsystem of FIG. 11.
`FIG. 20 is a block diagram of the cache memory control-
`ler 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.
`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 how-
`ever the signal names are not needed to understand the
`operation and practice of the 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 example between the clients 104-107
`and servers 110 and 112. The network is shown schemati-
`
`cally as a cloud with several network nodes and links shown
`in the interior of the cloud. A monitor 108 examines the
`
`packets passing in either direction past its connection point
`121 and, according to one aspect of the invention, can
`elucidate what application programs are associated with
`each packet. The monitor 108 is shown examining packets
`(i.e., datagrams) between the network interface 116 of the
`server 110 and the network. The monitor can also be placed
`
`Petitioners‘ EX1001 Page 25
`
`Petitioners' EX1001 Page 25
`
`

`
`US 6,771,646 B1
`
`5
`at other points in the network, such as connection point 123
`between the network 102 and the interface 118 of the client
`104, or some other location, as indicated schematically by
`connection point 125 somewhere in network 102. Not
`shown is a network packet acquisition device at the location
`123 on the network for converting the physical information
`on the network into packets for input into monitor 108. Such
`packet acquisition devices are common.
`Various protocols may be employed by the network to
`establish and maintain the required communication, e.g.,
`TCP/IP, etc. Any network activity—for example an appli-
`cation program run by the client 104 (CLIENT 1) commu-
`nicating 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 par-
`ticular application programs. The packets may need to be
`parsed then analyzed in the context of various protocols, for
`example, the transport through the application session layer
`protocols for packets of a type conforming to the ISO
`layered network model.
`Communication protocols are layered, which is also
`referred to as a protocol stack. The ISO (International
`Standardization Organization) has defined a general model
`tha provides a framework for design of communication
`protocol layers. This model, shown in table form below,
`serves as a basic reference for understanding the functionaly
`of existing communication protocols.
`
`ISO MODEL
`
`Layer Functionality Example
`
`Telnet, NFS, Novell NCP, H