(12) United States Patent
`(10) Patent N0.:
`US 6,771,646 B1
`9
`Sarkissian et al.
`45 Date of Patent:
`Au . 3 2004
`
`
`U5006771646B1
`
`(54) ASSOCIATIVE CACHE STRUCTURE FOR
`LOOKUPS AND UPDATES 0F FLOW
`RECORDS IN A NETWORK MONITOR
`
`(75)
`
`-
`.
`.
`.
`.
`Inventors. Haig A. Sarkissmn, San Antonio, TX
`(US); Russell S. Dietz, San Jose, CA
`(US)
`
`11/1994 Hershey et al.
`5,365,514 A
`12/1994 Hershey et al.
`5,375,070 A
`2/1995 Crowther et al.
`5,394,394 A
`5/1995 Hekhuis ................ 364/715.02
`5,414,650 A
`5/1995 Spinney
`5,414,704 A
`7/1995 Galloway
`5’430’709 A
`(List continued on next page.)
`
`............. 364/550
`
`(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. 154(b) by 591 days.
`
`(21) Appl.No.: 09/608’266
`(22)
`Filed:
`Jun. 30, 2000
`
`(60)
`
`Related US. Application Data
`Provisional application No. 60/141,903, filed on Jun. 30,
`1999-
`Int. Cl.7 ................................................ G01R 31/08
`(51)
`(52) us. 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,
`3951, 709/223, 224
`
`(56)
`
`References Cited
`
`US. 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 * 12/1985 Houseman et a1.
`.
`....... 365/49
`4,736,320 A
`4/1988 Bristol
`....................... 364/300
`
`1/1990 Nakamura ..........
`.. 340/8255
`4,891,639 A
`
`..... 711/207
`4,910,668 A *
`3/1990 Okamoto et al.
`........... 379/10
`4,972,453 A
`11/1990 Daniel, III et a1.
`571017402 A
`3/1992 Chi“ 6t al~
`5,247,517 A
`9/1993 Ross et a1. ................. 370/855
`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.
`
`JP
`
`iiiiiiiiii GO6F/17/30
`2/2003
`02003044510 A
`OTHER PUBLICATIONS
`
`.
`.
`R. Periakaruppam and E. Nemeth. “GTrace—A Graphical
`Traceroute T001.”
`1999 Usenix LISA. Available on
`WWW.caida.org, URL:
`http://WWW.caida.org/outreach/pa-
`pers/1999/GTracepdf.
`W. Stallings. “Packet Filtering in the SNMP Remote Moni-
`tor.” Nov. 1994. Available on www.ddj.com, URL: http://
`WWW.ddj.Com/documentS/S=1013/ddj9411h/9411h.htm.
`“Technical Note: the Narus System,” Downloaded Apr. 29,
`1999 from WWWharuscom Narus Corporation, Redwood
`CRY Ca11f0m1a~
`Primary Examiner—Ricky Ngo
`Assistant Examiner—Alan V. Nguyen
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`
`(57)
`
`ABSTRACT
`.
`A cache system for looking up one or more elements of an
`external memory includes a set of cache memory elements
`coupled to tile eggs/1211 mentlofy.’ asst 0230mm Eidressgtile
`memory CC 5 (
`5) C0“ ammg “1 a
`“355 a“
`a P01“ er
`to one of the cache memory elements, and 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 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.
`
`20 Claims, 21 Drawing Sheets
`
`PAEEER
`
`
`OF
`DATABASE
`
`FLOWS
`H ll 0 :|
`
`PACKET
`‘CQUISITION
`DEVICE
`
`
`
`
`
`
`HOST
`PROCESSO'
`
`MONITOR
`10.0
`
`NETWORK
`INTERFACE
`CARD
`
`EX 1003 Page 1
`EX 1003 Page 1
`
`

`

`US 6,771,646 B1
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`59432776 A
`5,493,689 A
`55009855 A
`5,511,215 A
`5,530,834 A *
`5,530,958 A *
`5,535,338 A
`595689471 A
`5,574,875 A
`5586266 A
`5,606,668 A
`5,608,662 A
`576347009 A
`5,651,002 A
`59684954 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
`
`~~~~~~~~~~~~ 395/800
`~~~~~~~~~~~~~~ 711/136
`
`711/3
`~~~~~~~~~~~ 395/2002
`
`7/1995 Harper
`2/1996 Waclawsky et al.
`3/1996 Hershey et al~
`4/1996 Terasaka et a1.
`6/1996 Colloff et a1.
`6/1996 AgarwaletaL
`7/1996 Krause et a1.
`10/1996 Hershey et al~
`.......... 395/403
`11/1996 Stansfield et al.
`12/1996 Hershey et a1~ ~~~~~~~~ 395/200-11
`2/1997 Shwed .................. 395/200.11
`
`-
`- 364/72401
`3/1997 Large et a1.
`5/1997 Idderr et al-
`395/200-11
`7/1997 Van Seters et al.
`......... 370/392
`
`“/1997 Kaiserswerth et al~
`395/2002
`................ 370/395
`12/1997 Nuberetal.
`2/1998 PicaZO, Jr. et al.
`....... 395/200.2
`
`~~~~~~
`- 395/200-11
`3/1998 Gessel et a1.
`~~~~~~ 395/183-21
`4/1998 Watanabe et a1.
`5/1998 HOOVer et al.
`.............. 711/108
`
`~~
`6/1998 Adams et a1.
`395/20047
`6/1998 Ketchurn ~~~~~~~~~~~~~~~~~~~~ 370/401
`7/1998 Southard ............... 395/20054
`
`-
`7/1998 Hershey et a1.
`~~~~~~ 364/557
`7/1998 McCreery et al.
`..... 395/200.61
`9/1998 Bellenger
`................... 370/401
`
`............ 395/200.2
`............. 370/245
`
`5,805,808 A
`5,812,529 A
`5,819,028 A
`
`9/1998 Hasani et a1.
`9/1998 Czarnik et al.
`10/1998 Manghirmalani
`et al.
`....................... 395/185.1
`10/1998 Ready et al.
`............... 370/401
`5,825,774 A
`11/1998 Shwed et al.
`.......... 395/20059
`5,835,726 A
`11/1998 Yoshioka etal.
`........... 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
`........... 370/252
`12/1998 Anderson et a1.
`5,850,388 A
`1/1999 Sell ............................ 711/146
`5,860,114 A
`.. 395/20054
`1/1999 Welch, Jr. et a1.
`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 .............
`395/680
`5,903,754 A
`
`6/1999 Gobuyan et al.
`........... 370/392
`5,917,821 A
`................ 711/207
`6,003,123 A * 12/1999 Carter et a1.
`
`6,014,380 A
`1/2000 Hendel et a1.
`..
`370/392
`................ 370/469
`6,115,393 A
`9/2000 Engeletal.
`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 Beigietal.
`6,424,624 B1
`7/2002 Galand et al.
`.............. 370/231
`
`6,625,657 B1
`9/2003 Bullard ...........
`709/237
`................. 709/224
`6,651,099 B1
`11/2003 Dietz et al.
`
`* cited by examiner
`
`EX 1003 Page 2
`EX 1003 Page 2
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 1 0121
`
`US 6,771,646 B1
`
`100 —
`CLIENT 4
`
`”\
`107
`
`ANALYZER
`
`108
`
`CUENT3
`
`\
`106
`
`116
`
`W10
`
`12‘
`
` DATA COMMUNICATIONS
`
`NETWORK
`
`102
`
`125
`
`118
`—
`SERVER 4 — 105 —J
`N
`CLIENT 2
`CLIENT 1 —\
`112
`104
`
`123
`
`FIG. 1
`
`EX 1003 Page 3
`EX 1003 Page 3
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 2 0f 21
`
`US 6,771,646 B1
`
`E
`
` mafia
`
`u
`
`mNNNNN_,NNONNENENENEN
`
`mmm>mmw
`ZO_._.<O_._n_n_<
`
`mom
`
`
`
`fiasco;E330
`
`EmumayNR
`
`
`vaummNuNmNuFmNaooNu
`EmuONNu
` an;
`
`
`
`u
`
`
`
`m._.2m_._O
`
`EX 1003 Page 4
`EX 1003 Page 4
`
`
`
`
`
`
`
`

`

`
`cm»Illllllillll.Smmmme
`
`
`J..\.--..----..-----
`
`"oz—EFZMD.
`
`mom
`
`Em:
`
`
`
`"mm/E.ZEmCKn.
`
`oz<
`
`ZO_._.O<m._.Xm
`
`ww<m<k<o
`
`E<n=
`
`ZOE-{immuni—
`ZOF<2mOmz_
`
`oz<m~>4<z<
`
`MN_ZGOOmm
`
`gawk-Em
`
`US. Patent
`
`Aug. 3, 2004
`
`Sheet 3 0f 21
`
`US 6,771,646 B1
`
`wm<m<k<o
`
`@304“.“.0
`
`2305*
`
`mom—00w.“—
`
`205.
`
`
`
`69.00.._3592:35m
`
`.z0.20.2350
`
`omoomm20.20::sz_gnaw-mgmEBw
`
`WEE:Eco-SE
`
`macs.
`
`8.
`
`«‘5
`
`Z._.<O_.-.=w.w<-_O
`
`295.5354."—
`
`m8
`
`mm~h<z<
`
`E05.
`
`zoFEmmo
`
`uzwwwooma
`
`30453
`
`mm><4
`
`.ZOFow-Ew
`
`m;
`
`02
`
`w«8
`
`08
`
`wwa
`
`commwooma
`
`ZOFUDEwZ
`
`mw<m<k<o
`
`54:58
`
`nz<
`
`$52.50
`
`Own
`
`EX 1003 Page 5
`EX 1003 Page 5
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 4 0f 21
`
`US 6,771,646 B1
`
`PACKET
`DECODING
`
`V
`
` HIGH LEVEL
`I ESCRIPTION ‘
`
`
`GENERATE
`
`PACKET
`COMPILE
`STATE
`PACKET
`
`
`
`INSTRUCTION
`PARSE AND
`
`
`EXTRACT
`
`
`AND
`
`OPERATIONS
`OPERATIONS
`
`
`
`
`
`
`
`406 7/-ATTERN, PARS
`STATE
`PROCESSOR
`AND
`
`
`INSTRUCTION
`EXTRACTION
`
`
`
`DATABASE
`DATABASE
`
`
`
`
`
`
`
`LOAD
`LOAD STATE
`
`PARSING
`NSTRUCTION
`
`
`SUBSYSTEM
`DATABASE
`
`
`
`MEMORY
`MEMORY
`
`407
`
`
`
`400
`
`EX 1003 Page 6
`EX 1003 Page 6
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 5 0f 21
`
`US 6,771,646 B1
`
`512
`
`I
`: I
`PACKET
`KEY
`
`502
`
`0 W
`
`LOAD PACKET
`COMPONENT
`
`
`ORE IN PACKE I»
`
`
`FETCH NODE AN I
`PROCESS FROM
`PATTERN
`
`503
`
`504
`
`
`
` NEXT
`
`MORE
`PACKET
`PATTERN
`
`NODES?
`COMPONE
`
` ‘I-V‘.' “.‘
`
`PROCESS TO
`
`COMPONENT
`
`
`V
`
`510
`
`V
`
`PATTERN
`NODE
`
`509
`
`EXTRACT
`ELEMENTS
`
`
`
`FIG. 5
`
`513
`
`51 1
`
`500
`
`EX 1003 Page 7
`EX 1003 Page 7
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 6 0f 21
`
`US 6,771,646 B1
`
`.
`
`601
`
`PACKET
`COMPONENT AND
`PATTERN NODE
`
`602
`
`LOAD PACKET
`COMPONENT
`
`MORE PACKE
`COMPONENT
`
`YES
`
`FETCH EXTRACTION
`
`‘ ND PROCESS FROM
`PATTERNS
`
`605
`
`603
`
`6
`
`04
`
`NO
`
`606
`
`507
`
`610
`
`LOAD KEY
`BUFFER
`
`@
`
`611
`
`609
`
`\
`
`600
`
`EX 1003 Page 8
`EX 1003 Page 8
`
`
`ELEMENTS?
`ORE EXTRACTIO ‘
`
`
`
`
`N O
`
`NEXT
`PACKET
`COM PONEN
`
`YES
`
`APPLY EXTRACTION
`Egocgs TO
`MP NENT
`
`
` MORE TO
`
`EXTRACT?
`
`
`
`508
`
`YE
`
`FIG. 6
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 7 0f 21
`
`US 6,771,646 B1
`
`o
`
`EY BUFFER AND
`PATTERN NODE
`
`702
`
`703
`
`704
`
`LOAD PATTERN
`NODE ELEMENT
`
`
`
`MORE PATTERN
`NODES?
`
`
`
`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
`
`EX 1003 Page 9
`EX 1003 Page 9
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 8 0f 21
`
`US 6,771,646 B1
`
`. 801
`
`UFKB ENTRY FOR
`PACKET
`
`802
`
`800 \
`
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH
`
`803
`
`REQUEST RECORD BIN/
`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
`
`No@ 808
`
`YES
`
`809
`
`MARK RECORD BIN AND
`
`BUCKET 'IN PROCESSI IN
`CACHE AND TIMESTAMP
`
`810
`
`8“
`
`812
`
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`813m.
`
`FIG. 8
`
`EX 1003 Page 10
`EX 1003 Page 10
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 9 0f 21
`
`US 6,771,646 B1
`
`901
`
`902
`
`910
`
`
`
`
`RPC
`BIND LOOKU "
`
`
`
`REQUEST
`
`909
`
`903
`
`EXTRACT PORT
`
`
`
` EXTRACT PROGRAM
`GET 'PROGRAM',
`GET 'PROGRAM',
`
`'VERSION', 'PORT' AND
`'VERSION‘ AND
`'PROTOCOL (TCP OR
`'PROTOCOL (TCP OR
`
`UDP)
`UDP)‘
`
`SAVE REQUEST
`
`CREATE SERVER STAT
`
`904
`
`SAVE 'PROGRAM',
`
`
`SAVE 'PROGRAM',
`
`
`'VERSION' AND
`'PROTOCOL (TCP OR
`'VERSION', 'PORT' AND
`
`
`UDP)‘ WITH
`'PROTOCOL (TCP OR
`
`UDP)I 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
`
`
`
`
`
`LOOKUP REQUE "
`FIND 'PROGRAM'
`
`900/
`
`AND 'VERSION'
`
`WITH LOOKUP OF
`
`'PROTOCOL (TCP
`
`SOURCE NETWORK
`
`OR UDP)‘.
`
`
`ADDRESS.
`
`EXTRACT
`PROG RAM
`
`
`
`
`GET 'PORT' AND
`
`FIG. 9
`
`EX 1003 Page 11
`EX 1003 Page 11
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 10 0f 21
`
`US 6,771,646 B1
`
` PATTERN
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1001
`
`100
`
`1 00
`
`1031
`
`1004
`
` INFO OUT
`
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS
`
`CONTRL N
`
`100
`
`100.
`
`
`PATTERN
`
`
`RECOGNITN
`
`
`
`ENGINE
`
`
`
`(PRE)
`
`EXTRACTION ENGINE
`(SLICER)
`
`1031
`
`1007
`
`
`
`PA KET
`INPUT
`
`
`
`PARSER
`
`
`
`PARSER INPUT BUFFER
`OUTPUT PACKET KEY
`
`MEMORY
`BUFFER AND PAYLOAD
`
`
`MEMORY
`
`
`1012
`
`1021
`
`
`
`
`
`INPUT BUFFER
`ANALYZER
`DATA REA'
`
`INTERFACE
`INTERFACE
`
`
`
`CONTROL
`CONTROL
`
`
`
`ANALYZER
`PACKET
`
`READY
`
`KET
`PQTART
`‘
`V
`
`
`102
`1023
`
`FIG. 10
`
`1027
`
`EX 1003 Page 12
`EX 1003 Page 12
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 11 0f 21
`
`US 6,771,646 B1
`
`1 103
`
`1115
`
`1107
`
`
`
`(ACIC)
`
`LOOKUP/
`
`UPDATE
`ENGINE
`. (LUE)
`
`
`PROCESS -‘
`INSTRUCN
`DATABASE
`(SPID)
`
`
`
`
`UNIFIED
`FLOW
`
`KEY
`
`
`hi
`UFFER
`
` (UFKB)
`
`PROCESSR
`(SP)
`
`PARSER
`INTER-
`FACE
`
`CONTROL
`
`1119112
`
`
`
`
`UNIFIED
`MEMORY
`
`
`MEMORY h INTER—FACE
`h CONTROL
`
` FLOW
`
`INSERTION/
`(UMC)
`
`
`DELETION
`
`ENGINE
`
`(FIDE)
`
`
`EX 1003 Page 13
`EX 1003 Page 13
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 12 0f 21
`
`US 6,771,646 B1
`
`1201
`
`
`
`1200
`
`N
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`
`ACCESS
`
`
`
`CONVERSATION
`RECORD BIN
`
`
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`
`
`WITH TIMESTAMP
`
`1 202
`
`1203
`
`1204
`
`1206
`
`1208
`
`1210
`
`
`REQUEST NEXT
`NO
`
`<-IN/BUCKET EMPTY
`BUCKET FROM
`
`CACHE
`
`YES
`
`
`
`:
`
`NO INSERT KEY AND HASH
`N BUCKET, MARK 'USED
`
`1205
`
`1207
`
`
`YES
`OMPARE CURRENT BIN 1209
`
`AND BUCKET RECORD
`
`SET UFKB FOR
`PACKET AS
`KEY TO PACKET
`'DROP'
`
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS'
`AND 'NEW' IN CACHE
`
`1211
`
`
`
`
`FOR RECORD IN CACHE
`
`. 1213
`
`
`FIG. 1 2
`
`EX 1003 Page 14
`EX 1003 Page 14
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 13 0f 21
`
`US 6,771,646 B1
`
`1300 N
`
`@1301
`
`UFKB ENTRY FOR
`PACKET WITH STATUS
`'NEW' oR '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
`
`
`POINTER TO
`VALUE FOUND IN
`
`CURRENT STATE
`
`NO
`
`
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET?
`
`
`
`
`
`1307
`
`1308
`1310
`
`YES
`
`NO
`
`
`
`DONE PROCESSING
`
`
`
`
`
`1309
`
`TATES FOR THIS FLOW?
`FLOW RECORD
`
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`
`
`YES
`
`SET AND SAVE FLOW REMOVA
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`
`EX 1003 Page 15
`EX 1003 Page 15
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 14 0f 21
`
`US 6,771,646 B1
`
`~.—-——————.—————————_—————____—
`
`w>>OxE".0
`
`025.5%.
`+o<m§m
`
`coma.a06.2.
`
`DZ<mN>J_<Z.
`
`mNEOOOmI
`
`2mmt<m
`
` DECOME
`mw<m<h<ozOFSszuz.
`ZO_h0<mkxm
`
`wh<on5zmmt<m
`Z>>OZ¥QZ<.
`
`__>>O.E_.mmmnhonmhm
`
`ZO_._.<N_.._<ZE
`
`._.<0_m_wwso
`
`EMN>J<Z<
`
`Ewkm>wm3m
`
`m.._.<._.w
`
`wZ_IO<_2
`
`IOhOwJMm
`
`one._.
`
`WEI—m
`
`m_w>._<2<
`
`_2mm>wmnm_Ewes.
`
`mZO_._.<m_mn_O
`
`w—-——————___—
`
`o3
`
`EX 1003 Page 16
`EX 1003 Page 16
`
`
`
`
`
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 15 0f 21
`
`US 6,771,646 B1
`
`._.mOI
`
`>IO_>_m=>_
`
`EOtZOE
`
`am
`
`FNF
`
`vEO>>._.m_Z
`
`m_0<u_mm_._.z_
`
`Dm<0
`
`Nor
`
`
`
`.mN>._<z<Emmi
`
`aman”
`
`._.m_v_o<n_
`
`ZO_._._m_DOO.
`
`m_O_>m_n_
`
`EX 1003 Page 17
`EX 1003 Page 17
`
`
`
`
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 16 0f 21
`
`US 6,771,646 B1
`
`Dst Hash (2
`
`Dst MAC (6)
`
`.
`
`EX 1003 Page 18
`EX 1003 Page 18
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 17 0f 21
`
`US 6,771,646 B1
`
`1 702
`
`ff
`t
`12%;?
`
`1704
`
`X
`
`1706
`
`1708
`Type (2)
`17101)
`-.et =14
`
`K1700
`
`FIG. 17A
`
`i
`
`IDP = 0X0600*
`IP = 0x0800*
`CHAOSNET = 0x0804
`ARP = 0x0806
`VIP = OXOBAD*
`VLOOP = OXOBAE
`VECHO = OXOBAF
`NETBIOS-3COM = OX3C00 -
`0x3COD#
`DEC-MOP = 0x6001
`DEC-RC = Ox6002
`DEC-DRP = 0x6003*
`DEC-LAT = 0x6004
`DEC-DIAG = 0X6005
`DEC-LAVC = 0X6007
`RARP = 0X8035
`ATALK = 0x809B*
`VLOOP = 0X80C4
`VECHO = 0x8005
`SNA—TH = 0X8OD5*
`ATALKARP = 0x80F3
`IPX = Ox8137*
`SNMP = 0x814C#
`va6 = 0x86DD*
`LOOPBACK = 0x9000
`
`
`
`//
`1712
`
`
`
`mmemmmmmlllln
`
`WWW- v ~
`1
`I-
`.3
`:0 VIEW
`L310
`
`
`[63:34 VIIAiTIn-rilmmem
`
`
`
`
`Dst Address—
` 'IIIIIII:LWiIMiiiifi'fl/IIIIIIIIM
`
`
`-1]
`
`
`
`
`
`
`
`Dst Address
`
`Dst Hash (2)
`
`Src Address
`
`Src Hash (2)
`
`
`
`
`
`
`
`Ian»
`
`FIG. 178
`
`-et = L3 + (lHL/4)
`
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`1 752
`
` ICMP = 1
`
`
`
`
`
`
`
`
`IGMP = 2
`GGP = 3
`TOP = 6*
`EGP = 8
`IGRP = 9
`PUP = 12
`CHAOS = 16
`
`UDP = 17*
`
`IDP = 22#
`
`ISO-TP4 = 29
`
`DDP = 37#
`
`lSO-IP = 80
`
`VIP = 83#
`
`EIGRP = 88
`
`OSPF = 89
`
`
`
`* L4 Decoding
`# L3 Re-Decoding
`
`
`EX 1003 Page 19
`EX 1003 Page 19
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 18 0f 21
`
`US 6,771,646 B1
`
`mi.hilt!kihhiiii!
`.‘h‘....\
`Eismmfl
`,-ail!
`
`PROTOCOL
`TYPE (IDZ
`
`EiE I
`
`hilt.‘-
`ii...iii
`.hihinnhum"hath!ii.
`
`
`C r/
`SggN
`
`1 642
`
`
`
`I._.02m_l_Q._.u.=n_
`
`1802 M
`
`FIG. 18A
`
`8701/
`
`L
`
`UT NUM
`____}
`
`mm
`
`
`
`MQOOm._.>m
`
`GAME“.0
`
`._OOO._.Ow_n_
`
`FEE
`
`FIG. 188
`
`EX 1003 Page 20
`EX 1003 Page 20
`
`
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 19 0f 21
`
`US 6,771,646 B1
`
`82karm?
`W|.m_mm5._
`
`moor
`
`
`
`
`
`
`
`ll|t|l|lvZ_-rm-m_0<n*Z_-o-m_®<n_m5—.momwMl-I'll-I-I-Euge
`53-56-02:IIIIa,\<55moo<moo<l.mNvar<._.<D_._._
`
`
`mmmmmwmmmm&3mwmwmwamvmm©$m§<mpm064<no
`
`
`.IIII|.|IVH30-rm-m0<n_._.DO-o-m_O<n_
`
`
`mx:IdmmBEEVW
`
`
`<._.<D-O_>_D-<Owear
`
`wagesIII-II-I
`
`
`(Hm—mug“.SIII—mwmmmeDS.._.Om_._m_mPDQ—.30{EDI—M...
`
`lJMwm—DE
`|
`
`ldmnames:55mm562.mfimmxw
`
`:9.
`
`4wmm0<n_<0
`
`m5—.
`
`jH—
`
`,,.\._.<n_.vm
`
`EX 1003 Page 21
`EX 1003 Page 21
`
`moo<m<F<m|a#6
`
`3
`
`

`

`US. Patent
`
`Aug. 3, 2004
`
`Sheet 20 0f 21
`
`US 6,771,646 B1
`
`2001
`
`2005
`
`'—
`g
`CL
`LU
`3
`
`%
`CL
`DJ
`E
`
`
`
`
`
`SEL_LUE_F|DE—>
`CAM_HIT
`
`LUEMEMREQ
`EREADY
`SETLU
`SETLUESEL
`
`S
`
`L
`
`CAM_H|TPAGE
`
`AM LR PA E
`
`SEL_CACHE—>
`
`
`
`<>E
`g
`<I
`CACHE_CAM_SM
`
`
`FIDEMEMREQ
`C
`G
`3
`U
`‘
`
`
`0
`SETFIDEREADY
`LOAD_CAM
`
`ETFIDESE
`REFRESH_CAM
`
`
`GET BACKUP GOT/2003
`
`
`
`
`
`CACHEPORT
`
`CACHE ME
`
`SIGNALS
`
`
`
`_ CACHE_MEM_SM
`
`
`
`
`CA-MEM-RE
`
`CA-MEM-WRIT
`
`UMC-O-CA-NEXTA
`
`2
`D
`
`
`
`
`UMC-O-CA-REA
`
`FIG. 20
`
`EX 1003 Page 22
`EX 1003 Page 22
`
`

`

`LOADO
`
`LOAD1
`
`LOADZ
`
`LOADS
`
`LOAD4
`
`5T0 32
`
`LOADS
`
`DECOD
`
`LOADS
`
`LOAD?
`
`CAM[0]
`DAT ~lr
`CAM[1]
`DAT J,
`CAM[2]
`Jr
`CAM[3]
`J
`CAM4]
`t
`CAM[5]
`I
`CAMIB]
`*
`CAM[7]
`J7
`
`E
`2
`m
`F
`g
`g
`
`I
`
`2107
`
`
`
`l CAM NUMBER
`
`US. Patent
`
`Aug. 3, 2004
`
`Sheet 21 0f 21
`
`US 6,771,646 B1
`
`CAM_HITPAGE. REF-DATA
`
`CAM_LRUPAGE, REF— DATA
`2109
`
`LOAD, REFRESH. EVICT
`
`-
`- REF DATA
`
`2105
`
`2111
`
`CAM_INPUTDATA
`
`2103
`
`2113
`
`MATGHO
`
`.
`
`MATCH1
`
`MATCH2
`
`MATCH3
`
`MATCH4 32 TO 5
`
`2115
`
`MATCHS.
`
`MATCH6
`
`HiGH
`
`CAM
`HT
`
`MATCHT
`
`E
`o
`D.
`“-
`3
`§
`
`CAM_NUMBER
`
`I
`2127 DATA0
`
`I
`0 0 0 DATA31
`
`I
`DATA!
`
`1
`
`I
`' 0 DATA31
`
`'
`
`m 2123 m
`J
`2121
`wl
`DIRTY ENTRY
`CURRENT ENTRY
`
`2117
`
`DIRTY_PAGE. DIRTY_HASH, DIRTY_BUCKET
`v
`
`CAM_HITPAGE
`v\
`
`21“”
`
`FIG. 21
`
`EX 1003 Page 23
`EX 1003 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 US. 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 US. patents
`and US. patent applications, each filed concurrently with
`the present application, and each assigned to Apptitude, Inc.,
`the assignee of the present invention:
`US. 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.
`US. 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.
`
`US. 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.
`US. 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 US. 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.
`
`EX 1003 Page 24
`EX 1003 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
`
`EX 1003 Page 25
`EX 1003 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, HITP, H.323
`7 Application
`6
`Presentation XDR
`5
`Session
`RPC, NETBIOS, SNMP, etc.
`4
`Transport
`TCP, Novel SPX, UDP, etc.
`3 Network
`IP, Novell IPX, VIP, AppleTalk, etc.
`2 Data Link
`Network Interface Card (Hardware Interface). MAC
`layer
`Ethernet, Token Ring, Frame Relay, ATM, T1
`(Hardware Connection)
`
`Physical
`
`1
`
`Different communication protocols employ different lev-
`els of the ISO model or may use