(12) United States Patent
`US 6,651,099 B1
`(10) Patent N0.:
`Dietz et al.
`(45) Date of Patent:
`Nov. 18, 2003
`
`USOO6651099B1
`
`(54)
`
`(75)
`
`METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`5,375,070 A
`5,394,394 A
`
`12/1994 Hershey et al.
`2/1995 Crowther et al.
`
`............. 364/550
`............. 370/60
`
`Inventors: Russell S. Dietz, San Jose, CA (US);
`Joseph R. Maixner, Aptos, CA (US);
`Andrew A. Koppenhaver, Littleton,
`CO (US); William H. Bares,
`Germantown, TN (US); Haig A.
`Sarkissian, San Antonio, TX (US);
`James F. Torgerson, Andover, MN
`(US)
`
`(List continued on next page.)
`OTHER PUBLICATIONS
`
`“Technical Note: the Narus System,” Downloaded Apr. 29,
`1999 from www.narus.com, Narus Corporation, Redwood
`City California.
`
`Primary Examiner—Moustafa M. Meky
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`
`(73)
`
`Assignee:
`
`Hi/fn, Inc., Los Gatos, CA (US)
`
`(57)
`
`ABSTRACT
`
`Notice:
`
`(*)
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 589 days.
`
`(21)
`
`(22)
`
`(60)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Appl. No.:
`Filed:
`
`09/608,237
`
`Jun. 30, 2000
`
`Related US. Application Data
`Provisional application No. 60/141,903, filed on Jun. 30,
`1999.
`
`Int. Cl.7 ................................................ G06F 13/00
`US. Cl.
`........................................ 709/224; 370/389
`Field of Search ................................. 709/200, 201,
`709/220, 223, 224, 231, 232, 236, 238,
`239, 240, 246; 370/389, 392, 395.32
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,736,320
`4,891,639
`5,101,402
`5,247,517
`5,247,693
`5,249,292
`5,315,580
`5,339,268
`5,351,243
`
`5,365,514>>>>>>>>>>
`
`4/1988
`1/1990
`3/1992
`9/1993
`9/1993
`9/1993
`5/1994
`8/1994
`9/1994
`11/1994
`
`....................... 364/300
`Bristol
`Nakamura ..
`340/825.5
`
`........ 370/17
`Chui et al.
`..
`Ross et al. ................. 370/85.5
`....................... 395/800
`Bristol
`Chiappa ..
`395/650
`.........
`Phaal
`370/13
`
`Machida ............
`365/49
`
`............. 370/92
`Kalkunte et al.
`Hershey et al.
`............... 370/17
`
`A monitor for and a method of examining packets passing
`through a connection point on a computer network. Each
`packets conforms to one or more protocols. The method
`includes receiving a packet from a packet acquisition device
`and performing one or more parsing/extraction operations
`on the packet to create a parser record comprising a function
`of selected portions of the packet. The parsing/extraction
`operations depend on one or more of the protocols to which
`the packet conforms. The method further includes looking
`up a flow-entry database containing flow-entries for previ-
`ously encountered conversational flows. The lookup uses the
`selected packet portions and determining if the packet is of
`an existing flow. If the packet is of an existing flow, the
`method classifies the packet as belonging to the found
`existing flow, and if the packet is of a new flow, the method
`stores a new flow-entry for the new flow in the flow-entry
`database, including identifying information for future pack-
`ets to be identified with the new flow-entry. For the packet
`of an existing flow, the method updates the flow-entry of the
`existing flow. Such updating may include storing one or
`more statistical measures. Any stage of a flow, state is
`maintained, and the method performs any state processing
`for an identified state to further the process of identifying the
`flow. The method thus examines each and every packet
`passing through the connection point in real time until the
`application program associated with the conversational flow
`is determined.
`
`10 Claims, 18 Drawing Sheets
`
`1000 N
`
`PATTERN
`EXTRACTTON
`
`RECOGNITION
`,
`_,
`OPERATIONS
`DATABASE
`DATABASE
`
`MEMORY
`MEMORY
`
`
`\
`1031 (
`\41004
`
`INFn‘ouT
`
`
`
`
`
`PATTERN
`‘ RECOGNITN
`ENGINE
`(PRE)
`
`
`
`100th
`K,
`
` PARSER INPUT BUFFER
`PACKET
`PACKET KEY
`INPUT
`MEMORY
`361261
`‘
`BUFFER AND FAYLOA'
`
`MEMORY
`
`77\ 1012
`
`1021-\1
`
`PACKET
`START
`INPUTEUFFEH
`10117.,‘.
`
`DATA REA Iv CONTROLANAWZER
`lNTERFACE
`
`INTERFACE
`,
`.
`CONTROL
`
`
`PACKET
`
`
`
`1 02%,!“
`* 1023
`1027 v /
`
`
`
`
`
`EX 1001 Page 1
`EX 1001 Page 1
`
`

`

`US 6,651,099 B1
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`5,414,650 A
`5,414,704 A
`594307709 A
`5,432,776 A
`5,493,689 A
`5,500,855 A
`5,511,213 A
`5,511,215 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
`596519002 A
`5,684,954 A
`5,703,877 A
`5,732,213 A
`5,740,355 A
`5,761,424 A
`5,764,638 A
`5781735 A
`5,784,298 A
`5,787,253 A
`
`5/1995 Hekhuis ................ 364/715.02
`5/1995 Spinney ....................... 370/60
`7/1995 Galloway ~~
`370/13
`
`........................ 370/17
`7/1995 Harper
`2/1996 Waclawsky et al.
`........ 395/821
`
`3/1996 Hershey et a1~ ~~~~~
`370/17
`4/1996 Correa ....................... 395/800
`4/1996 Terasaka et al.
`............ 395/800
`
`10/1996 Hershey et a1~ ~~~~~
`370/17
`.......... 395/403
`11/1996 Stansfield et al.
`12/1996 Hershey et al.
`........ 395/200.11
`
`2/1997 Shwed
`395/200-11
`3/1997 Large et a1~
`~~~~~~~~~~~ 364/724~01
`5/1997 Iddon et a1.
`........... 395/200.11
`7/1997 Van Seters et al~ ~~~~~~~~~ 370/392
`11/1997 Kaiserswerth et al.
`395/200.2
`12/1997 Nuber et a1.
`................ 370/395
`
`3/1998 GesseletaL
`395/20011
`4/1998 Watanabe et a1~ ~~~~~~ 395/183-21
`
`6/1998 Adams et al.
`395/200.47
`6/1998 Ketchum ~~~~~~~~~~~~~~ 370/401
`
`7/1998 Seuthard
`395/200~54
`7/1998 Hershey et al.
`............. 364/557
`7/1998 McCreery et al.
`..... 395/200.61
`
`5,802,054 A
`5,805,808 A
`5,812,529 A
`5,819,028 A
`
`................... 370/351
`9/1998 Bellenger
`9/1998 Hansani et al.
`.......... 395/200.2
`9/1998 Czarnik et a1.
`............. 370/245
`10/1998 Manghirmalani
`etal.
`....................... 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
`..... 395/200.54
`11/1998 Schwaller et al.
`5,838,919 A
`11/1998 Huffman ..................... 382/155
`5,841,895 A
`
`. 370/241
`12/1998 Anderson et a1.
`.
`5,850,386 A
`........... 370/252
`12/1998 Anderson et al.
`5,850,388 A
`1/1999 Welch, Jr. et a1.
`...... 395/20054
`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
`. 370/392
`6/1999 Gobuyan et al.
`.
`5,917,821 A
`
`.............. 370/392
`1/2000 Hendel et al.
`6,014,380 A
`9/2000 Zaumen et a1.
`............. 370/229
`6,118,760 A *
`
`6/2001 Kerr et a1.
`..
`703/27
`6,243,667 B1 *
`9/2002 Jorgensen ................... 370/338
`6,452,915 B1 *
`9/2002 Muller et al.
`............... 709/250
`6,453,360 B1 *
`
`. 709/238
`6,466,985 B1 * 10/2002 Goyal et a1.
`............... 370/230
`6,483,804 B1 * 11/2002 Muller et al.
`6,570,875 B1 *
`5/2003 Hegde ........................ 370/389
`
`* cited by examiner
`
`EX 1001 Page 2
`EX 1001 Page 2
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 1 0f 18
`
`US 6,651,099 B1
`
`108
`
`116
`
`W10
`
`102
`
`125
`
`V1 07
`
`ANALYZER
`
`_ C
`
`LIENT 4
`
`100
`
`CLIENT 3
`
`’\
`106
`
`121
`
` DATA COMMUNICATIONS
`
`NETWORK
`
`118
`—
`SERVER A — 105 —~/
`W
`CLIENT2 J
`CLIENT1 fl
`“2
`104
`
`123
`
`FIG. 1
`
`EX 1001 Page 3
`EX 1001 Page 3
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 2 0f 18
`
`US 6,651,099 B1
`
`Nimam-I...-
`
`“,avNNNNNNFNNONN2Nw—NENowNmFNVFN
`
`
`
`m0wuNmmsmmmzoEo:&<8mNamEN08
`
`¢u
`
`Nclltls
`
`mNN
`
`
`LEN/vmKNuNNNVKNVCNN
`I_____Iflfl
`
`m._.Zm__:_O
`
`EX 1001 Page 4
`EX 1001 Page 4
`
`
`
`
`
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 3 0f 18
`
`US 6,651,099 B1
`
`mm<m<._.<n_
`
`w>>O._n_m0
`
`
`
`>>Ol_n___>>mz
`
`«Om—00mm
`
`Z>>Ozx
`
`@105<_
`Emme__womoomm___
`
`n5v_oo.__.magzsasm
`
`EOE“.,O_._.<mmm_>ZOO
`
`m_._.<n_n_3
`
`__>>O._u_._
`
`Z>>OZ¥
`
`DmOOmE
`
`mIOS—
`
`O_._.<O_n=wm<1_0
`
`whimwJOOOFOEQ
`
`ZO_._.<O_u:._.Zm_n__
`
`BEbm.
`
`oz_>n_:2m_n__
`
`em:
`
`ZO_._.O<m._.Xm_
`
`mm<m<._.<o
`
`DZ<
`
`EEV
`
`zo_F<_>Eon_z_
`zoEsEouE.
`
`oz<m~>._<z<
`
`muzoooma
`
`zmmfiE
`
`zo:<N:<z_n_IZ._.<O_n__wm<._0
`mmm_2m
`
`EOmmmooE
`
`mm<m<k<o
`
`20.5352.mm.__n_s_oo
`
`oz<
`
`ENSEO
`
`aw
`
`mu~5<z<
`
`ozwmmoomm
`
`‘.ZO_._.<EMn_O
`
`
`
`§<mofi<o4805mm
`
`
`
`Eb:o_E_omm_o
`
`mo<aoz<._
`
`EX 1001 Page 5
`EX 1001 Page 5
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 4 0f 18
`
`US 6,651,099 B1
`
`
`
`
`HIGH LEVEL
`PACKET
`DECODING
`
`402
`
`
`
`GENERATE
`PACKET
`PACKET
`
`
`COMPILE
`STATE
`PARSE AND
`‘I ESCRIPTION ‘
`INSTRUCTION "
`
`EXTRACT
`
`AND
`
`OPERATIONS
`
`
`OPERATIONS
`
`‘
`
`I A
`
`
`
`
`
`
`
`
`
`407
`
`
`
`
`STATE
`406 7/‘ATTERN, PARS
`PROCESSOR
`AND
`
`INSTRUCTION
`EXTRACTION
`
`
`DATABASE
`DATABASE
`
`
`
`
`
`LOAD
`
`
`PARSING
`
`
`SUBSYSTEM
`
`
`MEMORY
`
`
`
`LOAD STATE
`NSTRUCTIO
`
`DATABASE
`
`MEMORY
`
`400
`
`EX 1001 Page 6
`EX 1001 Page 6
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 5 0f 18
`
`US 6,651,099 B1
`
`503
`
`504
`
`502
`
`
`
`
`
`
`PACKET
`
`ORE IN PACKE I»
`KEY
`
`
`
`FETCH NODE AN I
`PROCESS FROM
`PATTERN
`
`513
`
`
`
`
`N EXT
`
`
`MORE
`PACKET
`PATTERN
`
`
`NODES?
`COMPONE
`
`
`
`
`511
`
`510
`
`A" 'Von Aw
`
`
`PROCESS TO
`
`COMPONENT
`
`‘
`
`
`PATTERN
`NODE
`
`
`
`509
`
`500
`
`EX 1001 Page 7
`EX 1001 Page 7
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 6 0f 18
`
`US 6,651,099 B1
`
`0
`
`PACKET
`COMPONENT AND
`PATTERN NODE
`
`602
`
`603
`
`6
`
`04
`
`LOAD PACKET
`COMPONENT
`
`MORE PACKE
`COMPONENT
`
`
`
`
`
`
`
`YES
`
`FETCH EXTRACTION
`
`‘ ND PROCESS FROM
`PATTERNS
`
`605
`
`NO
`
`606
`
`
`ORE EXTRACTIO ‘
`ELEMENTS?
`
`
`
`610
`
`LOAD KEY
`BUFFER
`
`6
`
`611
`
`NEXT
`
`
`
`N O
`
`PACKET
`COM PONEN
`
`609
`
`607
`
`YES
`
`APPLY EXTRACTION
`ElgOCEDSS TO
`MP NENT
`
`
`
` MORE TO
`EXTRACT?
`
`
`
`FIG. 6
`
`608
`
`YE
`
`\
`
`600
`
`EX 1001 Page 8
`EX 1001 Page 8
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 7 0f 18
`
`US 6,651,099 B1
`
`0
`
`EY BUFFER AND
`PATTERN NODE
`
`702
`
`LOAD PATTERN
`NODE ELEMENT
`
`708
`
`OUTPUT To
`ANALYZER
`
`@
`
`709
`
`\
`
`700
`
`EX 1001 Page 9
`EX 1001 Page 9
`
`703
`
`704
`
`
`
`MORE PATTER
`NODES?
`
`
`
`YES
`
`HASH KEY BUFFER
`ELEMENT FROM
`PATTERN NODE
`
`705
`
`PACK KEY & HAS
`
`NEXT PACKET
`COMPONENT
`
`706
`
`707
`
`FIG. 7
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 8 0f 18
`
`US 6,651,099 B1
`
`0
`
`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 PROCESS' IN
`CACHE AND TIMESTAMP
`
`810
`
`8“
`
`812
`
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`813x.
`
`FIG. 8
`
`EX 1001 Page 10
`EX 1001 Page 10
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 9 0f 18
`
`US 6,651,099 B1
`
`901
`
`902
`
`910
`
`
`
`
` RPC
`mNDLOOKu-
`
`
`REQUEST
`
`909
`
`
`
` EXTRACT PROGRAM
`
`EXTRACT PORT
`
`904
`
`SAVE REQUEST
`
`GET 'PROGRAM'.
`GET 'PROGRAM',
`
`'VERSION' AND
`'VERSION', 'PORT' AND
`
`'PROTOCOL (TCP OR
`'PROTOCOL (TCP OR
`
`
`
`UDP)
`UDP)I
`
`
`
`
`
`
`
`CREATE SERVER STAT
`SAVE 'PROGRAM',
`
`
`
`‘VERSION' AND
`SAVE 'PROGRAM',
`
`
`
`'VERSION’, 'PORT' AND
`'PROTOCOL (TCP OR
`
`
`
`'PROTOCOL (TCP OR
`UDP)‘ WITH
`
`
`
`UDP)‘ WITH NETWORK
`DESTINATION
`
`
`NETWORK ADDRESS.
`ADDRESS IN SERVER
`
`
`
`STATE DATABASE. KEY
`BOTH MAKE A KEY.
`
`
`
`ON SERVER ADDRESS
`
`
`AND TCP OR UDP PORT.
`
`
`
`RPC
`
`
`BIND
`
`LOOKUP
`
`
`REPLY
`
`
`EXTRACT
`
`
`LOOKUP REQUE‘
`PROGRAM
`FIND 'PROGRAM'
`
`
`900/
`AND 'VERSION'
`WITH LOOKUP OF
`
`
`SOURCE NETWORK
`
`ADDRESS.
`
`GET 'PORT‘ AND
`
`
`
`'PROTOCOL (TCP
`OR UDP)’.
`
`
`FIG. 9
`
`EX 1001 Page 11
`EX 1001 Page 11
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 10 0f 18
`
`US 6,651,099 B1
`
` PATTERN
`
`100
`
`1001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`100
`
`1031
`
`1004
`
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS
`
` INFO OUT
`1031)
`
`CONTRL IN
`
`
`PATTERN
`
`
`
`RECOGNITN
`EXTRACTION ENGINE
`
`
`ENGINE
`(SLICER)
`
`
`
`(PRE)
`
`
`
`1007
`
`100'
`
`100:
`
`
`
`
`PARSER
`
`
`
`OUTPUT PACKET KEY
`PARSER INPUT BUFFER
`
`MEMORY
`BUFFER AND PAYLOA'
`
`
`MEMORY
`
`
`
`
`
`
`PA KET
`INPUT
`
`1012
`
`1021
`
`
`
`INPUT BUFFER
`PQTAKRETT
`ANALYZER
`DATA REA'Y
`
`
`
`
`INTERFACE
`INTERFACE
`
`
`
`1
`.
`CONTROL
`CONTROL
`
`
`
`ANALYZER
`PACKET
`READY
`
`102
`1023
`
`FIG. 10
`
`1027
`
`EX 1001 Page 12
`EX 1001 Page 12
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 11 0f 18
`
`US 6,651,099 B1
`
`1100 N
`
`1101
`
`1103
`
`1115
`
`1118 1122
`
`1107
`
`
`
`0011:
`ENGINE
`
`
`
`
`
`+13%?
`AwggTZE'
`
`h INTERFAC‘ INTER-
`
`
`
`AND
`FACE
`COANTICROL
`(HIB)
`
`
`( C )
`
`
`PROCESS!
`INSTRUCN
`DATABASE
`(SPID)
`
`
`UNIFIED
`
`FLOW
`
`PARSER
`KEY
`
`INTER- H UFFER
`
`(UFKB)
`FACE
`
`
`PROCESSR
`(SP)
`
`
`
`
`MEMORY
`UNIFIED
`INTER-
`MEMORY
`
`” CONTROL h FACE
`(UMC)
`
`
`
`
`
` INSIELF9T1VON/
`
`DELETION _
`ENGINE
`
`(FIDE)
`
`1110
`
`FIG. 11
`
`1119 1123
`
`EX 1001 Page 13
`EX 1001 Page 13
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 12 0f 18
`
`US 6,651,099 B1
`
`1201
`
`
`
`
`
`
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`
`
`
`ACCESS
`CONVERSATION
`
`
`RECORD BIN
`
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`1202
`
`1203
`
`1 204
`
`05
`
`REQUEST NEXT
`BUCKET FROM
`CACHE
`
`
`YES
`
`1207
`INSERT KEY AND HASH
`N BUCKET, MARK 'USED
`
`
`WITH TIMESTAMP
`
`YES
`
`
`OMPARE CURRENT BI
`AND BUCKET RECORD
`
` SET UFKB FOR
`KEY TO PACKET
`
`
`
`
`
`
`1206
`
`1208
`
`1210
`
`
`
`
`
`
`<‘IN/BUCKET EMPTY
`
`12
`
`.
`'
`
`NO
`
`PACKET AS
`'DROP'
`
`1209
`
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS'
`AND 'NEW' IN CACHE
`
`1211
`
`FOR RECORD IN CACHE
`
`. 1213
`
`FIG. 1 2
`
`EX 1001 Page 14
`EX 1001 Page 14
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 13 0f 18
`
`US 6,651,099 B1
`
`1300 N
`
`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
`NO
`DONE PROCESSING
`
`
`POINTER TO
`STATES FOR THIS
`
`
`VALUE FOUND IN
`PACKET?
`
`CURRENT STATE
`
`
`
`1308
`YES
`1310
`
`
`SAVE STATE
`
`PROCESSOR
`
`
`
`
`DONE PROCESSING
`INSTRUCTION
`
`
`
`
`TATES FOR THIS FLO
`POINTER IN
`CURRENT FLOW
`
`RECORD
`
`
`
`NO
`
`1307
`
`1309
`
`YES
`
`SET AND SAVE FLOW REMOVA
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`
`FLOW RECORD
`
`EX 1001 Page 15
`EX 1001 Page 15
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 14 0f 18
`
`US 6,651,099 B1
`
`mm<m<._.<n_
`
`W>>OIELO
`
`13x00;
`
`Z>>OZ¥
`
`momOOmm
`
`Avmvrmov
`
`
`
`>m_v___>>O._n___
`400mmwOmZ.
`
`OZ_>n__._.Zm_n=
`
`._.O<NFXm_
`
`m._.<._.m\
`
`m_N_ZOOOmm
`
`ZIMHHQQ
`
`ZO_._.<_>_N_OH_Z_
`
`DmOme
`
`m_._.<n_n5
`
`Z>>OZ¥
`
`__>>O._n___ZO_._.<O_n=mm<._O
`
`Z._.<O_u__mm<._0
`
`ZO_._.<N_._<Z_n_
`
`EMN>._<Z<
`
`_>_m_._.m>mm3m
`
`.ma>u<z<
`
`wgpm
`
`w._.<._.m
`
`wZ_IO<_2
`
`mO._.Om_._m_m
`
`omvw
`
`wmmDHODIFm
`
`zmw._I_.<&
`
`ZO_._.O<I._.Xm_
`
`wZO_._.<Em_n_O
`
`QZ<
`
`Imam—(n.
`
`_>_m_w>wm_3w_
`
`EX 1001 Page 16
`EX 1001 Page 16
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 15 0f 18
`
`US 6,651,099 B1
`
`._.mOI
`
`>EO_>_m=2
`
`m0<n_m_m_._.z_
`
`Dm<0
`
`mO._._ZO_>_
`
`an
`
`._.m_x0<n_
`
`ZO_._._w_DOO.
`
`m0_>m_n_
`
`
`
`EX 1001 Page 17
`EX 1001 Page 17
`
`
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 16 0f 18
`
`US 6,651,099 B1
`
`Dst Hash (2
`
`Dst MAC (6)
`
`\Iet=12
`
`FIG. 16
`
`EX 1001 Page 18
`EX 1001 Page 18
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 17 0f 18
`
`US 6,651,099 B1
`
`
`
`1 702
`
`1
`
`T pe
`
`offset
`12 to 13
`
`I
`1‘
`
`1706
`
`H “’9‘”
`ash 1
`1710 - ) K 1700
`_
`Laoma_14
`
`FIG 1 7A
`.
`
`
`
`'D.E=8"8388*
`= x
`CHAOSNET = 0x0804
`ARP = 0x0806
`VIP = OXOBAD*
`VLOOP = OXOBAE
`VECHO = OXOBAF
`NETBIOS-3COM = 8988004141
`X
`DE%$”SB=8X288%
`-
`= x
`DEC-DRP = 0x6003*
`DEC-LAT = 0x6004
`DEoDme=ommm
`DEC-LAVC = 0x600?
`RARP = 0x8035
`ATALK = 0x8098*
`VLOOP = 0X80C4
`VECHO = OXBOCS
`/ SNA—TH = 0x80D5*
`ATALKARP = Ox80F3
`1712
`lPX= 0x8137*
`SNMP = Ox814C#
`IPv6 = 0x86DD*
`LOOPBACK = 0x9000
`
`*
`
`
`
`Apple = 0x080007
`* L3 Decoding
`
`# L5 Decoding
`
`1752
`
`
`
`lflli’lflflfl'fl’lm’im'fl'lllll
`WW
`ICMP =1
`=
`L3 to
`«3g; :3
`[(11124 VIM/w;mum
`
`
`SrcAddress
`_
`-1] — TCP _ e
`
`Igg: :g
`CHKBEE1§
`IIIIIII"MIMIIWIIIIIIIIIIIIIA
`”13535;
`'SO‘JES;§%#
`
`.So_.p :80
`W = 83#
`536$? :33
`
`*
`
`
`#L3 Reetfgelggding
`
`
`* L4 D
`
`d'
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`-o1 (1)
`
`“”50
`
`
`
`Fl G. 1 78
`
`L4 Offet = L3 + (IHL/4)
`
`EX 1001 Page 19
`EX 1001 Page 19
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 18 0f 18
`
`US 6,651,099 B1
`
`PROTOCOL
`
`00
`
`
`
`5.0ijD._m__n_
`
`mmFr0EBEIwIlnvT.6099:
`
`-0G5
`
`
`
`.5...$1
`,-iill!
`
`1802 1
`
`mAr83.0:“.“.01EcomErm
`
`LUT NUM:
`
`ES
`
`L
`
`1870
`/
`
`FIG. 188
`
`EX 1001 Page 20
`EX 1001 Page 20
`
`
`
`

`

`US 6,651,099 B1
`
`1
`METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`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. patent
`applications, each filed concurrently with the present
`application, and each assigned to Apptitude,
`Inc.,
`the
`assignee of the present invention:
`US. patent application Ser. No. 09/609,179 for PRO-
`CESSING PROTOCOL SPECIFIC INFORMATION
`IN PACKETS SPECIFIED BY A PROTOCOL
`DESCRIPTION LANGUAGE,
`to inventors
`Koppenhaver, et al., filed Jun. 30, 2000, still pending,
`and incorporated herein by reference. US. patent appli-
`cation Ser. No. 09/608,126 for RE-USING INFORMA-
`TION FROM DATA TRANSACTIONS FOR MAIN-
`TAINING STATISTICS IN NETWORK
`MONITORING, to inventors Dietz, et al., filed Jun. 30,
`2000, still pending, and incorporated herein by refer-
`ence. US. patent application Ser. No. 09/608,266 for
`ASSOCIATIVE CACHE STRUCTURE FOR LOOK-
`UPS AND UPDATES OF FLOW RECORDS IN A
`NETWORK MONITOR, to inventors Sarkissian, et al.,
`filed Jun. 30, 2000, still penting, and incorporated
`herein by reference. US. patent application Ser. No.
`09/608,267 for STATE PROCESSOR FOR PATTERN
`MATCHING IN A NETWORK MONITOR DEVICE,
`to inventors Sarkissian, et al., filed Jun. 30, 2000, still
`pending, 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 TO THE PRESENT
`INVENTION
`
`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 internets—an
`“internet” being any plurality of interconnected networks
`which forms a larger, single network. With the growth of
`networks used as a collection of clients obtaining services
`from one or more servers on the network, it is increasingly
`important to be able to monitor the use of those services and
`to rate them accordingly. Such objective information, for
`example, as which services (i.e., application programs) are
`being used, who is using them, how often they have been
`accessed, and for how long, is very useful in the mainte-
`nance and continued operation of these networks.
`It
`is
`especially important that selected users be able to access a
`network remotely in order to generate reports on network
`use in real time. Similarly, a need exists for a real-time
`network monitor that can provide alarms notifying selected
`users of problems that may occur with the network or site.
`One prior art monitoring method uses log files. In this
`method, selected network activities may be analyzed retro-
`spectively by reviewing log files, which are maintained by
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`network servers and gateways. Log file monitors must
`access this data and analyze (“mine” its contents to deter-
`mine statistics about the server or gateway. Several problems
`exist with this method, however. First, log file information
`does not provide a map of real-time usage; and secondly, log
`file mining does not supply complete information. This
`method relies on logs maintained by numerous network
`devices and servers, which requires that the information be
`subjected to refining and correlation. Also, sometimes infor-
`mation is simply not available to any gateway or server in
`order to make a log file entry.
`One such case, for example, would be information con-
`cerning NetMeeting® (Microsoft Corporation, Redmond,
`Washington) sessions in which two computers connect
`directly on the network and the data is never seen by a server
`or a gateway.
`Another disadvantage of creating log files is that the
`process requires data logging features of network elements
`to be enabled, placing a substantial load on the device, which
`results in a subsequent decline in network performance.
`Additionally, log files can grow rapidly, there is no standard
`means of storage for them, and they require a significant
`amount of maintenance.
`
`Though Netfiow® (Cisco Systems, Inc., San Jose, Calif.),
`RMON2, and other network monitors are available for the
`real-time monitoring of networks, they lack visibility into
`application content and are typically limited to providing
`network layer level information.
`Pattern-matching parser techniques wherein a packet is
`parsed and pattern filters are applied are also known, but
`these too are limited in how deep into the protocol stack they
`can examine packets.
`Some prior art packet monitors classify packets into
`connection flows. The term “connection flow” is commonly
`used to describe all
`the packets involved with a single
`connection. A conversational flow, on the other hand, is the
`sequence of packets that are exchanged in any direction as
`a result of an activity—for instance,
`the running of an
`application on a server as requested by a client. It is desirable
`to be able to identify and classify conversational flows rather
`than only connection flows. The reason for this is that some
`conversational flows involve more than one connection, and
`some even involve more than one exchange of packets
`between a client and server. This is particularly true when
`using client/server protocols such as RPC, DCOMP, and
`SAP, which enable a service to be set up or defined prior to
`any use of that service.
`An example of such a case is the SAP (Service Adver-
`tising Protocol), a NetWare (Novell Systems, Provo, Utah)
`protocol used to identify the services and addresses of
`servers attached to a network. In the initial exchange, a client
`might send a SAP request to a server for print service. The
`server would then send a SAP reply that identifies a par-
`ticular address—for example, SAP#5—as the print service
`on that server. Such responses might be used to update a
`table in a router, for instance, known as a Server Information
`Table. A client who has inadvertently seen this reply or who
`has access to the table (via the router that has the Service
`Information Table) would know that SAP#5 for this particu-
`lar server is a print service. Therefore, in order to print data
`on the server, such a client would not need to make a request
`for a print service, but would simply send data to be printed
`specifying SAP#5. Like the previous exchange, the trans-
`mission of data to be printed also involves an exchange
`between a client and a server, but requires a second con-
`nection and is therefore independent of the initial exchange.
`
`EX 1001 Page 21
`EX 1001 Page 21
`
`

`

`US 6,651,099 B1
`
`3
`In order to eliminate the possibility of disjointed conversa-
`tional exchanges, it is desirable for a network packet monitor
`to be able to “virtually concatenate”—that is, to link—the
`first exchange with the second. If the clients were the same,
`the two packet exchanges would then be correctly identified
`as being part of the same conversational flow.
`Other protocols that may lead to disjointed flows, include
`RPC (Remote Procedure Call); DCOM (Distributed Com-
`ponent Object Model),
`formerly called Network OLE
`(Microsoft Corporation, Redmond, Wash); and CORBA
`(Common Object Request Broker Architecture). RPC is a
`programming interface from Sun Microsystems (Palo Alto,
`Calif.) that allows one program to use the services of another
`program in a lo remote machine. DCOM, Microsoft’s coun-
`terpart to CORBA, defines the remote procedure call that
`allows those objects—objects are self-contained software
`modules—to be run remotely over the network. And
`CORBA, a standard from the Object Management Group
`(OMG) for communicating between distributed objects,
`provides a way to execute programs (objects) written in
`different programming languages running on different plat-
`forms regardless of where they reside in a network.
`What
`is needed,
`therefore,
`is a network monitor that
`makes it possible to continuously analyze all user sessions
`on a heavily trafficked network. 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.
`Considering the previous SAP example again, because
`one features of the invention is to correctly identify the
`second exchange as being associated with a print service on
`that server, such exchange would even be recognized if the
`clients were not the same. What distinguishes this invention
`from prior art network monitors is that it has the ability to
`recognize disjointed flows as belonging to the same conver-
`sational flow.
`
`The data value in monitoring network communications
`has been recognized by many inventors. Chiu, et al.,
`describe a method for collecting information at the session
`level in a computer network in US. Pat. No. 5,101,402,
`titled “APPARATUS AND METHOD FOR REAL-TIME
`MONITORING OF NETWORK SESSIONS AND A
`
`LOCAL AREA NETWORK” (the “402 patent”). The 402
`patent specifies fixed locations for particular types of pack-
`ets to extract information to identify session of a packet. For
`example, if a DECnet packet appears, the 402 patent looks
`at six specific fields (at 6 locations) in the packet in order to
`identify the session of the packet. If, on the other hand, an
`IP packet appears, a different set of six different locations is
`specified for an IP packet. With the proliferation of
`protocols, clearly the specifying of all the possible places to
`look to determine the session becomes more and more
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`difficult. Likewise, adding a new protocol or application is
`difficult. In the present invention, the locations examined
`and the information extracted from any packet are adap-
`tively determined from information in the packet for the
`particular type of packet. There is no fixed definition of what
`to look for and where to look in order to form an identifying
`signature. A monitor implementation of the present
`invention, for example, adapts to handle differently IEEE
`802.3 packet from the older Ethernet Type 2 (or Version 2)
`DIX (Digital-Intel-Xerox) packet.
`The 402 patent system is able to recognize up to the
`session layer. In the present invention, the number of levels
`examined varies for any particular protocol. Furthermore,
`the present invention is capable of examining up to whatever
`level is sufficient to uniquely identify to a required level,
`even all the way to the application level (in the OSI model).
`Other prior art systems also are known. Phael describes a
`network activity monitor that processes only randomly
`selected packets in US. Pat. No. 5,315,580, titled “NET-
`WORK MONITORING DEVICE AND SYSTEM.” Naka-
`
`mura teaches a network monitoring system in US. Pat. No.
`4,891,639,
`titled “MONITORING SYSTEM OF NET-
`WORK.” Ross, et al., teach a method and apparatus for
`analyzing and monitoring network activity in US. Pat. No.
`5,247,517,
`titled “METHOD AND APPARATUS FOR
`ANALYSIS NETWORKS,” McCreery, et al., describe an
`Internet activity monitor that decodes packet data at the
`Internet protocol level layer in US. Pat. No. 5,787,253,
`titled “APPARATUS AND METHOD OF ANALYZING
`
`INTERNET ACTIVITY.” The McCreery method decodes
`IP-packets. It goes through the decoding operations for each
`packet, and therefore uses the processing overhead for both
`recognized and unrecognized flows. In a monitor implemen-
`tation of the present invention, a signature is built for every
`flow such that future packets of the flow are easily recog-
`nized. When a new packet in the flow arrives, the recogni-
`tion process can commence from where it last left off, and
`a new signature built to recognize new packets of the flow.
`
`SUMMARY
`
`In its various embodiments the present invention provides
`a network monitor that can accomplish one or more of the
`following objects and advantages:
`Recognize and classify all packets that are exchanges
`between a client and server into respective client/server
`applications.
`Recognize and classify at all protocol layer levels con-
`versational flows that pass in either direction at a point
`in a network.
`
`Determine the connection and flow progress between
`clients and servers according to the individual packets
`exchanged over a network.
`Be used to help tune the performance of a network
`according to the current mix of client/server applica-
`tions requiring network resources.
`Maintain statistics relevant to the mix of client/server
`applications using network resources.
`Report on the occurrences of specific sequences of pack-
`ets used by particular applications for client/server
`network conversational flows.
`
`Other aspects of embodiments of the invention are:
`Properly analyzing each of the packets exchanged
`between a client and a server and maintaining infor-
`mation relevant to the current state of each of these
`
`conversational flows. p1 Providing a flexible process-
`
`EX 1001 Page 22
`EX 1001 Page 22
`
`

`

`US 6,651,099 B1
`
`5
`ing system that can be tailored or adapted as new
`applications enter the client/server market.
`Maintaining statistics relevant to the conversational flows
`in a client/sever network as classified by an individual
`application.
`Reporting a specific identifier, which may be used by
`other network-oriented devices to identify the series of
`packets with a specific application for a specific client/
`server network conversational flow.
`invention
`In general,
`the embodiments of the present
`overcome the problems and disadvantages of the art.
`As described herein, one embodiment analyzes each of
`the packets passing through any point in the network in
`either direction, in order to derive the actual application used
`to communicate between a client and a server. Note that
`there could be several simultaneous and overlapping appli-
`cations executing over the network that are independent and
`asynchronous.
`A monitor embodiment of the invention successfully
`classifies each of the individual packets as they are seen on
`the network. The contents of the packets are parsed and
`selected parts are assembled into a signature (also called a
`key) that may then be used identify further packets of the
`same conversational flow, for example to further analyze the
`flow and ultimately to recognize the application program.
`Thus the key is a function of the selected parts, and in the
`preferred embodiment, the function is a concatenation of the
`selected parts. The preferred embodiment forms and remem-
`bers the state of any conversational flow, which is deter-
`mined by the relationship between individual packets and
`the entire conversational flow over the network. By remem-
`bering the state of a flow in this way,
`the embodiment
`determines the context of the conversational flow, including
`the application program it relates to and parameters such as
`the time, length of the conversational flow, data rate, etc.
`The monitor is flexible to adapt to future applications
`developed for client/server networks. New protocols and
`protocol combinations may be incorporated by compiling
`files written in a high-level protocol description language.
`The monitor embodiment of the present
`invention is
`preferably implemented in application-specific integrated
`circuits (ASIC) or field programmable gate arrays (FPGA).
`In one embodiment, the monitor comprises a parser sub-
`system that forms a signature from a packet. The monitor
`further comprises an analyzer subsystem that receives the
`signature from the parser subsystem.
`A packet acquisition device such as a media access
`controller (MAC) or a segmentation and reassemble module
`is used to provide packets to the parser subsystem of the
`monitor.
`
`the parsing subsystem
`In a hardware implementation,
`comprises two sub-parts, the pattern analysis and recogni-
`tion engine (PRE), and an extraction engine (slicer). The
`PRE interprets each packet, and in particular,
`interprets
`individual fields in each packet according to a pattern
`database.
`
`The different proto