(12) United States Patent (cid:9)
`Sarkissian et al. (cid:9)
`
`11111111111111101111111111R1o111,111111!1111111111111110111111
`US 6,771,646 B1
`Aug. 3, 2004
`
`(to) Patent No.: (cid:9)
`(45) Date of Patent: (cid:9)
`
`(54)
`
`(75)
`
`ASSOCIATIVE CACHE STRUCTURE FOR
`LOOKUPS AND UPDATES OF FLOW
`RECORDS IN A NETWORK MONITOR
`
`Inventors: Haig A. Sarkissian, San Antonio, TX
`(US); Russell S. Dietz, San Jose, CA
`(US)
`
`(73)
`
`Assignee: Hi/fn, Inc., Los Gatos, CA (US)
`
`Notice: (cid:9)
`* )
`
`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: (cid:9)
`
`Jun. 30, 2000
`
`(60)
`
`(51)
`(52)
`
`(58)
`
`(56)
`
`Related U.S. Application Data
`Provisional application No. 60/141,903, filed on Jun. 30,
`1999.
`
`Int. C1.7 (cid:9)
`U.S. Cl. (cid:9)
`
` GO1R 31/08
` 370/392; 370/412; 370/252;
`370/352; 709/223; 711/119
` 370/241.1, 252,
`Field of Search (cid:9)
`370/253, 352, 353, 355, 389, 392, 401,
`395.1; 709/223, 224
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3,949,369 A (cid:9)
`4,458,310 A (cid:9)
`4,559,618 A (cid:9)
`4,736,320 A
`4,891,639 A
`4,910,668 A (cid:9)
`4,972,453 A
`5,101,402 A
`5,247,517 A
`5,247,693 A
`5,315,580 A
`5,339,268 A
`5,351,243 A
`
`* 4/1976 Churchill, Jr. (cid:9)
`* 7/1984 Chang (cid:9)
`* 12/1985 Houseman et al. (cid:9)
`4/1988 Bristol
`1/1990 Nakamura (cid:9)
`* 3/1990 Okamoto et al. (cid:9)
`11/1990 Daniel, III et al. (cid:9)
`3/1992 Chiu et al.
`9/1993 Ross et al. (cid:9)
`9/1993 Bristol
`5/1994 Phaal
`8/1994 Machida (cid:9)
`9/1994 Kalkunte et al.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`711/128
`711/119
`365/49
`364/300
`340/825.5
`711/207
`379/10
`
`370/85.5
`395/800
`
`365/49
`
`5,365,514 A (cid:9)
`5,375,070 A (cid:9)
`5,394,394 A (cid:9)
`5,414,650 A (cid:9)
`5,414,704 A (cid:9)
`5,430,709 A (cid:9)
`
`11/1994 Hershey et al.
`12/1994 Hershey et al. (cid:9)
`2/1995 Crowther et al.
`5/1995 Hekhuis (cid:9)
`5/1995 Spinney
`7/1995 Galloway
`
` 364/550
`
` 364/715.02
`
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`
`JP (cid:9)
`
`02003044510 A * 2/2003
`
` GO6F/17/30
`
`OTHER PUBLICATIONS
`
`R. Periakaruppam and E. Nemeth. "GTrace—A Graphical
`Traceroute Tool." 1999 Usenix LISA. Available on
`www.caida.org, URL: http://www.caida.org/outreach/pa-
`pers/1999/GTrace.pdf.
`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/ddj 9411 h/9411 h. htm.
`"Technical Note: the Narus System," Downloaded Apr. 29,
`1999 from www.narus.com, Narus Corporation, Redwood
`City California.
`
`Primary Examiner—Ricky Ngo
`Assistant Examiner (cid:9) Alan V. Nguyen
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`
`(57) (cid:9)
`
`ABSTRACT
`
`A cache system for looking up one or more elements of an
`external memory includes 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 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
`
`1502
`
`PARSER
`301
`
`ANALYZEF
`303
`
`4 (cid:9)
`
`PACKET
`ACQUISITION
`DEVICE
`
`r 324
`
`DATABASE
`OF
`FLOWS
`
`(MEMORY) (1504
`
`r 1506
`
`HOST
`HOST
`PROCESSOR~
`MEMORY
`
`MONITOR
`3_00
`
`r 1508
`
`1510
`
`NETWORK
`INTERFACE
`CARD
`
`DISK
`
`DB
`
`NOAC Ex. 1003 Page 1
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`US 6,771,646 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,805,808 A (cid:9)
`5,812,529 A (cid:9)
`5,819,028 A (cid:9)
`
`9/1998 Hasani et al. (cid:9)
`9/1998 Czarnik et al. (cid:9)
`10/1998 Manghirmalani
`et al. (cid:9)
`10/1998 Ready et al. (cid:9)
`5,825,774 A (cid:9)
`11/1998 Shwed et al. (cid:9)
`5,835,726 A (cid:9)
`11/1998 Yoshioka et al. (cid:9)
`5,835,963 A (cid:9)
`11/1998 Schwaller et al. (cid:9)
`5,838,919 A (cid:9)
`11/1998 Huffman (cid:9)
`5,841,895 A (cid:9)
`12/1998 Anderson et al. (cid:9)
`5,850,386 A (cid:9)
`12/1998 Anderson et al. (cid:9)
`5,850,388 A (cid:9)
`1/1999 Sell (cid:9)
`5,860,114 A (cid:9)
`1/1999 Welch, Jr. et al. (cid:9)
`5,862,335 A (cid:9)
`3/1999 de la Salle (cid:9)
`5,878,420 A (cid:9)
`4/1999 Cheriton (cid:9)
`5,893,155 A (cid:9)
`5/1999 Pearson (cid:9)
`5,903,754 A (cid:9)
`6/1999 Gobuyan et al. (cid:9)
`5,917,821 A (cid:9)
`6,003,123 A (cid:9) * 12/1999 Carter et al. (cid:9)
`6,014,380 A (cid:9)
`1/2000 Hendel et al. (cid:9)
`6,115,393 A (cid:9)
`9/2000 Engel et al. (cid:9)
`6,279,113 B1 (cid:9)
`8/2001 Vaidya (cid:9)
`6,330,226 B1 (cid:9)
`12/2001 Chapman et al. (cid:9)
`6,363,056 B1 (cid:9)
`3/2002 Beigi et al. (cid:9)
`6,424,624 B1 (cid:9)
`7/2002 Galand et al. (cid:9)
`6,625,657 B1 (cid:9)
`9/2003 Bullard (cid:9)
`6,651,099 B1 (cid:9)
`11/2003 Dietz et al. (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`395/200.2
`370/245
`
`395/185.1
`370/401
`395/200.59
`711/207
`395/200.54
`382/155
`370/241
`370/252
`711/146
`395/200.54
`707/10
`711/144
`395/680
`370/392
`711/207
`370/392
`370/469
`713/201
`370/232
`370/252
`370/231
`709/237
`709/224
`
`* cited by examiner
`
`5,432,776 A
`5,493,689 A
`5,500,855 A
`5,511,215 A
`5,530,834 A (cid:9)
`5,530,958 A (cid:9)
`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 (cid:9)
`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/200.2
`
`7/1995 Harper
`2/1996 Waclawsky et al. (cid:9)
`3/1996 Hershey et al.
`4/1996 Terasaka et al. (cid:9)
`* 6/1996 Colloff et al. (cid:9)
`* 6/1996 Agarwal et al. (cid:9)
`7/1996 Krause et al. (cid:9)
`10/1996 Hershey et al.
`395/403
`
`11/1996 Stansfield et al. (cid:9)
` 395/200.11
`12/1996 Hershey et al. (cid:9)
` 395/200.11
`2/1997 Shwed (cid:9)
` 364/724.01
`3/1997 Large et al. (cid:9)
` 395/200.11
`5/1997 Iddon et al. (cid:9)
`
`370/392
`7/1997 Van Seters et al. (cid:9)
`11/1997 Kaiserswerth et al. ... 395/200.2
`12/1997 Nuber et al. (cid:9)
`
`370/395
`2/1998 Picazo, Jr. et al. (cid:9)
`
`395/200.2
`3/1998 Gessel et al. (cid:9)
` 395/200.11
`4/1998 Watanabe et al. (cid:9)
` 395/183.21
`* 5/1998 Hoover et al. (cid:9)
`
`711/108
`6/1998 Adams et al. (cid:9)
` 395/200.47
`6/1998 Ketchum (cid:9)
`
`370/401
`7/1998 Southard (cid:9)
` 395/200.54
`7/1998 Hershey et al. (cid:9)
`
`364/557
`7/1998 McCreery et al. (cid:9)
` 395/200.61
`9/1998 Bellenger (cid:9)
`
`370/401
`
`NOAC Ex. 1003 Page 2
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 1 of 21 (cid:9)
`
`US 6,771,646 B1
`
`100
`
`CLIENT 4
`
`CLIENT 3
`
`106
`
`DATA COMMUNICATIONS
`NETWORK
`
`SERVER 2
`
`112
`
`CLIENT 1
`
`118
`
`104
`
`FIG. 1
`
`NOAC Ex. 1003 Page 3
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 2 of 21 (cid:9)
`
`US 6,771,646 B1
`
`1111
`
`.= ..
`...
`.,=,
`.0
`
`CV
`
`a U-
`
`I
`
`NOAC Ex. 1003 Page 4
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 3 of 21 (cid:9)
`
`US 6,771,646 B1
`
`1
`
`cr
`N 011
`—1> 81
`
`44-- I
`
`LI.
`
`eD
`
`I
`
`t
`
`4 (cid:9)
`
`r
`
`I 8
`
`o_
`
`NOAC Ex. 1003 Page 5
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004 (cid:9)
`
`Sheet 4 of 21 (cid:9)
`
`US 6,771,646 B1
`
`404
`
`GENERATE
`PACKET
`PARSE AND 4 (cid:9)
`EXTRACT
`OPERATIONS
`
`---..,
`-----"'
`_---"
`
`.---- (cid:9)
`........___
`.......... (cid:9)
`......
`HIGH LEVEL
`PACKET
`DECODING
`DESCRIPTIONS
`... (cid:9)
`---'
`
`1
`
`COMPILE
`DESCRIPTIONS
`
`/
`
`403
`
`402
`
`405
`
`GENERATE
`PACKET
`STATE
`(cid:9)► INSTRUCTIONS
`AND
`OPERATIONS
`
`.- (cid:9)
`Nik (cid:9)
`
`--...,
`00
`
`407
`
`406-2)3ATTEFAIII1bPARSE
`
`EXTRACTION
`DATABASE
`
`c 408
`
`409 D
`
`STATE
`PROCESSOR \.
`INSTRUCTION
`DATABASE
`
`LOAD
`PARSING
`SUBSYSTEM
`MEMORY
`
`LOAD STATE
`NSTRUCTION A (cid:9)
`DATABASE
`MEMORY
`
`)400
`
`410
`
`FIG. 4
`
`NOAC Ex. 1003 Page 6
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 5 of 21 (cid:9)
`
`US 6,771,646 B1
`
`501
`
`/INPUT PACKET (cid:9)
`
`502
`
`503
`
`504
`
`LOAD PACKET
`COMPONENT
`
`ORE IN PACKE
`
`512
`
`BUILD
`PACKET
`KEY
`
`MORE
`PATTERN
`NODES?
`
`506
`
`YES
`APPLY NODE AND
`PROCESS TO
`COMPONENT
`
`513
`
`NEXT
`PACKET ---)
`COMPONENITC_ 511
`A
`
`500
`
`508
`
`510
`
`509
`
`EXTRACT
`ELEMENTS
`
`FIG. 5
`
`NOAC Ex. 1003 Page 7
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 6 of 21 (cid:9)
`
`US 6,771,646 B1
`
`601
`
`/ PACKET
`
`COMPONENT AND
`PATTERN NODE
`
`602
`
`603
`
`604
`
`LOAD PACKET
`COMPONENT
`
`MORE PACKE
`COMPONENT
`
`610
`
`/
`
`LOAD KEY
`BUFFER
`
`vYES
`FETCH EXTRACTION
`AND PROCESS FROM-'7
`' 605
`PATTERNS (cid:9)
`
`NO
`606
`
`ORE EXTRACTIO
`ELEMENTS?
`
`NEXT
`PACKET
`NO.
`COMPONENT
`•
`
`607
`
`YES
`APPLY EXTRACTION
`PROCESS TO
`COMPONENT
`
`611
`
`609
`
`600
`
`FIG. 6
`
`NOAC Ex. 1003 Page 8
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004 (cid:9)
`
`Sheet 7 of 21 (cid:9)
`
`US 6,771,646 B1
`
`701
`
`/ EY BUFFER AND (cid:9)
`
`PATTERN NODE
`
`702
`
`703 --\____,,,
`
`•
`LOAD PATTERN
`(cid:9)
`N
`ELEMENT li
`
`704
`
`NO
`
`(cid:9)rTh (cid:9)
`
`YES
`ii
`HASH KEY BUFFER
`ELEMENT FROM
`PATTERN NODE
`
`705
`
`PACK KEY & HASH
`
`NEXT PACKET
`COMPONENT
`
`706
`
`707
`
`FIG. 7
`
`708 (cid:9) -\
`
`2
`OUTPUT TO
`ANALYZER
`
`10.
`
`709
`
`700
`
`NOAC Ex. 1003 Page 9
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 8 of 21 (cid:9)
`
`US 6,771,646 B1
`
`800
`
`a_x--- 801
`
`•
`/UFKB ENTRY FOR
`PACKET
`
`802
`
`V
`COMPUTE CONVERSATION
`r- 803
`RECORD BIN FROM HASH
`
`•
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`804
`
`806
`
`805
`
`4-
`
`NO
`
`SET UFKB FOR
`PACKET AS 'NEW'
`
`YES
`COMPARE CURRENT BIN
`AND BUCKET RECORD KEY
`TO PACKET
`
`807
`
`808
`
`809
`
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS' IN
`CACHE AND TIMESTAMP
`
`r-- 810
`
`•
`SET UFKB FOR PACKET
`811-x.
`AS 'FOUND'
`
`812
`
`V
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`813- (v) (cid:9)
`
`FIG. 8
`
`NOAC Ex. 1003 Page 10
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 9 of 21 (cid:9)
`
`US 6,771,646 B1
`
`901
`
`902
`
`910
`
`RPC
`
`REPLY KDliTMAPP
`
`RPC
`ANNOUNCME
`PORTMAPPE
`
`iRPC
`BIND LOOKU
`
`REQUEST
`
`909
`
`903
`
`904
`
`EXTRACT PROGRAM
`
`GET 'PROGRAM',
`'VERSION', 'PORT AND
`'PROTOCOL (TCP OR
`UDP)
`
`CREATE SERVER STATE
`
`SAVE 'PROGRAM',
`VERSION', 'PORT' AND
`'PROTOCOL (TCP OR
`UDP)' WITH NETWORK
`ADDRESS IN SERVER
`STATE DATABASE. KEY
`ON SERVER ADDRESS
`AND TCP OR UDP PORT.
`
`EXTRACT PORT
`
`GET 'PROGRAM',
`'VERSION' AND
`'PROTOCOL (TCP OR
`UDP)'
`
`908
`SAVE REQUEST
`
`SAVE 'PROGRAM',
`'VERSION' AND
`'PROTOCOL (TCP OR
`UDP)' WITH
`DESTINATION
`NETWORK ADDRESS.
`BOTH MAKE A KEY.
`
`907
`
`11:-1 P
`BIND
`LOOKUP
`\ REPLY
`
`- 905
`
`906
`
`LOOKUP REQUE
`
`FIND 'PROGRAM'
`900!
`AND 'VERSION'
`WITH LOOKUP OF
`SOURCE NETWORK
`ADDRESS.
`
`EXTRACT
`PROGRAM
`
`GET 'PORT' AND
`'PROTOCOL (TCP
`OR UDP)'.
`
`FIG. 9
`
`NOAC Ex. 1003 Page 11
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004 (cid:9)
`
`Sheet 10 of 21 (cid:9)
`
`US 6,771,646 B1
`
`1000 ---,k
`
`PATTERN
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`1005—\_
`
`1031
`1004
`
`(cid:9)i INR)OUT,
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS CONTRL liN
`
`1031)
`
`1007
`moor
`EXTRACTION ENGINE
`(SLICER)
`
`1013-Th
`
`PARSER I (cid:9)
`
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`MEMORY I
`
`1025
`
`DATA REA
`
`ANALYZER
`READY
`
`1006—\ PATTERN
`RECOGNITN (cid:9)
`ENGINE I (cid:9)
`(PRE)
`
`100
`
`PACKETN
`INPUT /
`
`PARSER INPUT BUFFER
`MEMORY
`
`(-1012
`
`1021
`
`101
`
`PACKET\
`START/ INPUT BUFFER
`INTERFACE
`CONTROL
`
`NEXT
`PACKET
`
`1011
`
`ANALYZER
`INTERFACE
`CONTROL
`
`102
`1023
`
`FIG. 10
`
`1027
`
`NOAC Ex. 1003 Page 12
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent
`
`Aug. 3, 2004 (cid:9)
`
`Sheet 11 of 21
`
`US 6,771,646 B1
`
`1103
`
`1115
`
`2
`1118 112
`
`1107
`
`LOOKUP/
`UPDATE
`ENGINE
`(LUE)
`
`
`
`STATE
`PROCESS
`INSTRUCN
`DATABASE
`(SPID)
`
`1109
`
`ANALYZER
`HOST
`INTERFACE
`AND
`CONTROL
`(ACIC)
`
`HOST
`BUS
`INTER-
`FACE
`(HIB)
`
`UNIFIED
`FLOW
`KEY
`WBUFFER
`(UFKB)
`
`PARSER
`INTER-
`FACE
`
`r---1108
`
`CACHE
`
`STATE
`PROCESSR
`(SP)
`
`(cid:9)
`
`1119 1123
`
`UNIFIED
`MEMORY
`CONTROL
`(UMC)
`
`MEMORY
`INTER-
`FACE
`
`1•11111111111
`FLOW
`INSERTION/ (cid:9)
`DELETION (cid:9)
`ENGINE
`(FIDE)
`
`
`
`
`1110
`
`FIG. 11
`
`NOAC Ex. 1003 Page 13
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 12 of 21 (cid:9)
`
`US 6,771,646 B1
`
`1200 ---.A.
`
`REQUEST NEXT
`BUCKET FROM
`1206f
`CACHE
`
`1208
`
`1210-\
`
`SET UFKB FOR
`PACKET AS
`'DROP'
`
`1212 (cid:9)
`
`a_ (cid:9)
`
`1201
`
`/ UFKB
`
`V
`ENTRY FOR
`
`PACKET WITH
`TATUS'NEW'
`S
`
`IF
`ACCESS
`CONVERSATION
`RECORD BIN
`
`1202
`
`1203
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`1204
`
`1205
`
`1207
`
`1209
`
`INSERT KEY AND HASH
`IN BUCKET, MARK 'USED
`WITH TIMESTAMP
`+
`OMPARE CURRENT BIN
`AND BUCKET RECORD
`KEY TO PACKET
`
`r
`
`•
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS' j-1211
`AND 'NEW IN CACHE
`
`1
`
`SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`1213
`
`FIG. 12
`
`NOAC Ex. 1003 Page 14
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 13 of 21 (cid:9)
`
`US 6,771,646 B1
`
`1301
`
`1300 —a / UFKB ENTRY FOR
`
`PACKET WITH STATUS
`'NEW' OR 'FOUND' 1-\__ 1302
`
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO
`VALUE FOUND IN UFKB ENTRY
`
`FETCH INSTRUCTION FROM
`STATE PROCESSOR
`INSTRUCTION MEMORY
`
`V
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION
`
`SET STATE
`PROCESSOR
`INSTRUCTION
`POINTER TO
`VALUE FOUND IN
`CURRENT STATE
`
`NO
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET?
`
`1303
`
`1304
`
`1305
`
`1307
`
`1308
`,-/--- 1310
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`NO
`
`YES
`
`DONE PROCESSING
`TATES FOR THIS FLOW?
`
`1309
`
`YES
`
`SET AND SAVE FLOW REMOVAL
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`FLOW RECORD
`
`1311
`
`1313
`
`FIG. 13
`
`NOAC Ex. 1003 Page 15
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 14 of 21 (cid:9)
`
`US 6,771,646 B1
`
`w
`CO ›.
`g
`u- u_
`O
`
`4-J
`
`II
`I I
`II
`I
`I I
`I.
`
`t
`
`z
`zw
`‹zccz< p w
`
`
`_,or cc
`‹0‹0
`zwELLL
`<— z
`
`47
`
`U-
`
`NOAC Ex. 1003 Page 16
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 15 of 21 (cid:9)
`
`US 6,771,646 B1
`
`CO
`0
`LO 1-
`
`U) Y od0 CO
`5
`01
`
`Lo
`1' .
`0
`
`2
`
`w (cid:9)
`>-
`() cc
`U) (cid:9)
`CO < 0 0 2
`--I w
`I— (cid:9)
`< (cid:9)
`I-I-
`0
`
`A
`
`it (cid:9)
`
`W
`N ›- MI
`JO
`< c0
`Z
`‹C
`
`cc
`W
`CC co1 a o_
`'5
`
`Z
`— 0 W
`w I= 0
`(f) 5
`° 5 < o_ 0 a 0
`
`NOAC Ex. 1003 Page 17
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004 (cid:9)
`
`Sheet 16 of 21 (cid:9)
`
`US 6,771,646 B1
`
`1602
`
`0 - 3 Bytes
`
`offsetlii- 11
`
`Dst MAC
`Dst MAC Src MAC
`Src MAC
`
`Ac-- 1600
`
`1604
`
`1608 7
`
`._Dst Hash (2)
`
`
`Src Hash (21
`
`1612
`
`1614
`
`Dst MAC (6)
`
`Src MAC (6)
`
`,L2 Offset = 12
`
`FIG. 16
`
`NOAC Ex. 1003 Page 18
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004 (cid:9)
`
`Sheet 17 of 21 (cid:9)
`
`US 6,771,646 B1
`
`1702
`
`1704
`
`offset (cid:9)
`
`12 to 13
`
`Type
`
`11/0//N
`
`1708
`
`1710
`
`Type (2)
`Hash
`1)
`
`Off
`
`et = 14
`
`1700
`
`FIG. 17A
`
`1712
`
`L3 to
`[L3 +
`OHL/ 4
`- 1]
`
`1723, HMV
`'ffEZEZNAra4,
`Th4/J Protocol VMEV-
`Src Address
`Dst Address
`
`IDP = 0x0600*
`IP = 0x0800*
`CHAOSNET = 0x0804
`ARP = 0x0806
`VIP = OxOBAD*
`VLOOP = OxOBAE
`VECHO = OxOBAF
`NETBIOS-3COM = Ox3C00 -
`0x3COD#
`DEC-MOP = 0x6001
`DEC-RC = 0x6002
`DEC-DRP = 0x6003*
`DEC-LAT = 0x6004
`DEC-DIAG = 0x6005
`DEC-LAVC = 0x6007
`RARP = 0x8035
`ATALK = 0x809B*
`VLOOP = 0x80C4
`VECHO = Ox80C5
`SNA-TH = 0x80D5*
`ATALKARP = 0x80F3
`IPX = 0x8137*
`SNMP = 0x814C#
`IPv6 = Ox86DD*
`LOOPBACK = 0x9000
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`1752
`
`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
`
`1750
`
`Dst Address
`Dst Hash (2)
`Src Address
`Src Hash (2)
`
`Protoc of (1)
`
`L4 Off et = L3 + (IHU4)
`
`FIG. 17B
`
`* L4 Decoding
`# L3 Re-Decoding
`
`NOAC Ex. 1003 Page 19
`
`(cid:9)
`

`

`U.S. Patent
`
`Aug. 3, 2004
`
`Sheet 18 of 21
`
`US 6,771,646 B1
`
`k-----1800
`
`FIELD LENGTH
`
`1802-2
`1802-1
`
`1802-M
`
`FIG. 18A
`
`870
`
`LUT NUM)
`
`k--1850 w
`0 0
`0 -'
`0 w
`W II
`
`O
`
`-.4-----
`PROTOCOL
`
`FIG. 18B
`
`NOAC Ex. 1003 Page 20
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 19 of 21 (cid:9)
`
`US 6,771,646 B1
`
`• •
`
`OUTPUT SELECT MUXES
`
`I,- 0 0) •-
`
`a
`
`0 0
`
`I
`CACHE WRITE STROBES
`
`PAGE-31-OUT
`
`DUAL PORT RAM PAGES (32)
`
`a M
`<D I—
`0 0
`a s
`t (cid:9) 00
`
`PAGE-O-OUT
`
`<
`<
`(cid:9) <
`<
`0
`0 (cid:9)
`* rd3§-1 *
`1-11-1 (cid:9)
`ICI-i-
`
`1
`
`0 o ---\
`
`a)
`%-'
`
`CA-ADDRESS
`
`4iFIDESEL-
`Cl
`.FLUESEL-
`
`I
`_1
`w
`u)
`a.
`
`
`
`AD D R DATA
`
`INPUT SELECT MUXES
`
`cr
`
`0 0 Q
`
`4 # A 1 4
`a cc 'S 12 < cc
`1— 0
`1— 0 < a
`< a
`
`< 5 a a
`° < 1
`
`ill,I
` cIS (cid:9)
`I I
`I 3n11 (cid:9)
`I 3CIld I
`
`NOAC Ex. 1003 Page 21
`
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 20 of 21 (cid:9)
`
`US 6,771,646 B1
`
`CAM ARRAY
`
`SEL_LUE_FIDE-1.-
`
`CAM_HIT (cid:9)
`
`
`
`CAM_HITPAGE
`
`CAM_LRUPAGE
`
`LOAD_CAM (cid:9)
`
`N.
`
`REFRESH_CAM-o-
`
`1-
`cc
`LUEMEMREQ
`0
`a_
`-4--SETLUEREADY
`w
`SETLUESEL
`D
`4 (cid:9)
`_1
`
`FIDEMEMREQ
`-41- SETFIDEREA DY
`-0—SETFIDESEL
`
`FIDE PORT
`
`GET BACKUP GOT
`
`2003
`
`vi, (cid:9)
`
`I
`
`SEL_CACHE—*
`
`(cid:9) CA-MEM-RE
`CA-MEM-WRIT
`
`-4-UMC-0-CA-NEXTA
`
`UMC-O-CA-REA
`
`CACHE MEM
`SIGNALS
`
`CACHE_MEM_SM
`
`CACHE PORT
`
`FIG. 20
`
`NOAC Ex. 1003 Page 22
`
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Aug. 3, 2004
`
`Sheet 21 of 21 (cid:9)
`
`US 6,771,646 B1
`
`CAM_HITPAGE, REF-DATA
`
`LOAD, REFRESH, EVICT
`(cid:9)/2111
`-2105
`
`—LOADO-01 (cid:9)
`
`— LOAD 1 -01
`
`—LOAD2-*I (cid:9)
`
`—LOAD3-*I
`
`CAM LRUPAGE, REF-DATA
`2109
`REF-DATA
`
`2103 --/
` 2113
`
`CAM_I N P UTDATA
`V
`CAM[0]
`DATA
`CAM[1]
`DATAQ.,
`CAM[2] (cid:9)
`4
`CAM[3]
`
`—MATCHO*
`
`MATCH1*
`
`MATCH2*
`
`MATCH3 •
`
`MATCH4*
`32 TO 5 2115
`MATCH5* LOW
`TO
`MATCH6* HIGH
`
`cc
`0
`a_
`
`CAM_,
`HIT - 0
`9
`
`—LOAD4-0.1
`
`CAM4]
`
`510 32 —LOADS-1.1
`
`CAM[5]
`
`DECOD
`
`—LOAD6-*I
`
`CAM[6]
`
`UPDATE PORT
`
`—LOAD7-1.-1
`
`CAM[7]
`
`ENCOD
`MATCH7-.
`
`2107
`
`—LOAD30
`
`CAM[3O]
`
`MATCH30*
`
`—LOAD31
`
`CAM NUMBER (cid:9)
`— I
`
`CAM[311
`DATA3
`UPAGE
`CAM L'
`
`MATCH31*
`
`CAM
`
`NUMBER
`
`2127 DATAC
`
`• • • DATA31 (cid:9)
`
`NMUX32 (cid:9)
`
`DATAC1
`V
`2123 y\
`
`• • • DATA31
`
`NMUX32 A
`
`2121
`
`DIRTY ENTRY I (cid:9)
`
`CURRENT ENTRY
`
`DIRTY_PAGE, DIRTY HASH, DIRTY BUCKET CAM_HITPAGE
`—V
`
`FIG. 21
`
`TN-2119
`
`2117 —
`
`NOAC Ex. 1003 Page 23
`
`(cid:9)
`

`

`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
`
`5
`
`15
`
`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 10
`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 20
`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 25
`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 3o
`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.
`
`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
`35 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.
`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.
`
`40
`
`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 45
`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 50
`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.), 55
`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 60
`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. (cid:9)
`Related and incorporated by reference U.S. Pat. No.
`6,51,099 for METHOD AND APPARATUS FOR MONI-
`
`65
`
`NOAC Ex. 1003 Page 24
`
`(cid:9)
`(cid:9)
`

`

`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
`
`10
`
`15 (cid:9)
`
`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
`5 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
`20 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
`25 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
`40 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.
`
`50
`
`55
`
`60
`
`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
`
`30 (cid:9)
`
`35
`
`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-
`45
`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. (cid:9)
`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 65
`that can form part of the parser module in an embodiment of
`the inventive packet monitor.
`
`NOAC 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 ano