(12) United States Patent
`(10) Patent N0.:
`US 6,839,751 B1
`
`Dietz et al.
`(45) Date of Patent:
`Jan. 4, 2005
`
`USOO6839751B1
`
`(54) RE-USING INFORMATION FROM DATA
`TRANSACTIONS FOR MAINTAINING
`
`(75)
`
`STATISTICS IN NETWORK MONITORING
`Inventors: Russell S. Dietz, San Jose, CA (US);
`Joseph R. Malxner, Aptos, CA (US);
`A d
`A. K
`h
`L'ttl t
`C8 (r53)
`Oppen aver’
`1 eon’
`_
`.
`(73) A551gnee: Hl/fn, Inc., L05 Gatos, CA (US)
`
`(*) Notice:
`
`Subjectto any disclaimer, the term 0fth15
`patent 15 extended or adjusted under 35
`U.S.C. 154(b) by 728 days.
`
`(21) Appl. No.: 09/608,126
`
`(22)
`
`Filed:
`
`J1111- 30, 2000
`
`(60)
`
`51
`
`Related US. Application Data
`Provisional application No. 60/141,903, filed on Jun. 30,
`1999’
`Int. Cl.7 .............................................. G06F 15 173
`/
`(
`)
`
`.. 709/224, 709/223, 709/230
`.............
`(52) U.S. Cl.
`(58) Field of Search ................................. 709/223, 224,
`709/231, 232, 230; 370/252, 231; 379/32;
`704/43; 714/39; 340/825
`
`6,330,226 B1 * 12/2001 Chapman et a1.
`........... 370/232
`
`6,363,056 B1 *
`3/2002 Beigi et a1.
`........
`370/252
`..... 379/32
`6,381,306 B1 *
`4/2002 Lawson et al.
`
`.....
`6,424,624 B1 *
`7/2002 Galand et al.
`370/231
`...... 709 224
`B2 *
`92002 T k
`t
`l.
`
`42003 131611;: a.......... 709/237
`2:233:245‘3 B1 *
`................. 709/224
`6,651,099 B1 * 11/2003 Dietz et a1.
`OTHER PUBLICATIONS
`NOV94: Packet Filtering in the SNMP Remote Monitor ;
`www.skrymir.com/dobbs/articles/1994/9411/9411h/
`9411h.htm.*
`
`GTrace—A Graphical Traceroute Tool authored by Ram
`Periakaruppan, Evi Nemeth ; http://www.caida.org/out-
`reach/papers/1999/GTrace/indeX.Xml.*
`Advanced Methods for Storage and Retrieval in Image ;
`http://www.cs.tulane.edu/www/Prototype/proposal.html;
`1998.*
`
`Measurement and analysis of the digital DECT propagation
`channel; IEEE 1998.*
`*
`,
`,
`Cited by examiner
`Primary Examiner—Thong Vu
`74 Attorne , A em, or Firm—DOV Rosenfeld; Inventek
`y
`g
`
`(57)
`
`ABSTRACT
`
`A method of and monitor apparatus for analyzing a flow of
`packets passing through a connection point on a computer
`network. The method includes receiving a packet from a
`packet acquisition device, and looking up a flow-entry
`database containing flow-entries for previously encountered
`conversational flows. The looking up to determine if the
`U~S- PATENT DOCUMENTS
`Feceived PaCket is Of “1 “1.“ng flownE3Ch and every PaCket
`4 972 453 A * 11/1990 Daniel et al.
`.............. 379/903
`is processed. If the packet is of an eXistmg flow, the method
`..... 709/222
`5,535,338 A *
`7/1996 Krause et a1.
`
`updates the flow-entry of the existing flow, including storing
`12/1997 Nuber et a1. ............. 370/395
`5:703:877 A
`
`one or more statistical measures kept in the flow-entry. If the
`..
`5,720,032 A *
`2/1998 Picazo, Jr. et a1.
`709/250
`packet is of a new flow, the method stores a new flow-entry
`6/1998 Thompson ............... 709/224
`5,761,429 A *
`
`for the new flow in the flow-entry database,
`including
`8/1998 Kuriyan ............ 709/223
`5,799,154 A *
`
`storing one or more statistical measures kept in the flow-
`~~~~~~~~~~~~~~~~ 370/401
`5,802,054 A *
`9/1998 Bellenger
`
`entry. The statistical measures are used to determine metrics
`””” 370/252
`578507388 A * 12/1998 Anderson et al‘
`related to the flow. The metrics may be base metrics from
`2,333,233 2 * 3:333 Eggpglgletallux
`378/23?
`
`9/2000 Engel et a1. .......... 370/469 Wthh quality of serv1ce metrics are determined, or may be
`6,115,393 A *
`7/2001 Cidon et al. ............ 704/43
`6:269:330 B1 *
`the quahty 0f SCIVICC metrlcs
`
`8/2001 Vaidya ................. 713/201
`6,279,113 B1 *
`............... 709/224
`6,282,570 B1 *
`8/2001 Leung et a1.
`
`(56)
`
`References Cited
`
`21 Claims, 18 Drawing Sheets
`
`
`
`fl
`107
`
`ANALVZER
`
`
`116_/
`
`
`J211
`SERVER
`
`10
`
`CLIENT 3
`j
`
`
`
`\
`106
`
`DATA COMMUNICATIONS
`NETWORK
`
`102
`
`125
`
`
`SERVER g
`
`W
`112
`
`123
`
`
`CLIENT 2 J
`CLIENT 1
`105
`
`
`
`
`
`
`EX 1004 Page 1
`EX 1004 Page 1
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 1 0f 18
`
`US 6,839,751 B1
`
`100 _
`
`—\
`107
`
`ANALYZER
`
`—
`CLIENT 3
`
`“W
`106
`
`116
`
`No
`
`SERVER A
`
`121
`
` DATA COMMUNICATIONS
`
`NETWORK
`
`102
`
`125
`
`118
`_
`SERVER A _ 105 ——/
`W
`CLIENT2 J
`CLIENT1 fl
`”2
`104
`
`123
`
`FIG. 1
`
`EX 1004 Page 2
`EX 1004 Page 2
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 2 0f 18
`
`US 6,839,751 B1
`
`
`
`
`
`“5...:6269EBMU
`
`m
`
` m-x\
`
`mow
`
`au
`
`EN8mNew
`5Ncom
`au
`
`m._.Zm__|_O
`
`
`
`EmFmNRmafia“EN
`
`EX 1004 Page 3
`EX 1004 Page 3
`
`N
`
`mmmummmmeommmFNmFmFFNoF
`
`
`mwNvrm
`
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 3 0f 18
`
`US 6,839,751 B1
`
`mm<m<._.<o
`
`m>>OIE“.0
`
`m._.<on5
`
`__>>O._n__.
`
`z>>OZv_
`
`QmOowm
`
`Z._.<0_n=ww<n_o
`
`ZO_._.<N_._<z_u_
`
`m>
`
`an
`
`mmN>._<z<
`
`
`
`mom—00mmZ>>Ozx
`
`mom—00mm
`
`Emme
`
`mzo<o<_
`
`ngZDD..__Dm
`
`
`
`>m_v___>>O._n_._
`
`O_.r<wmm_>zOO
`zoEsEOuz.
`ozEfizmo.
`zOEéEEz.
`
`Fo<mkxm
`
`cm:
`
`oz<m~>._<z<
`
`muzoooma
`
`zmmEE
`
`
`>>o._n___>>m220E_13x09_
`
`
`MEGS.
`
`O_._.<0_n=ww<._0
`
`m._.<._.wwJOOOPONE
`
`ZO_._.<O_...=._.Zmo_
`
`Nmm
`
`mOwwMOOIn.
`
`ZO_._.ODE._.mZ_
`
`mw<m<h<o
`
`mmu=n=200
`
`DZ<
`
`EMN=>=._.n_O
`
`own
`
`02mmmOOm—m
`
`.ZO_._.<Em_n_O
`
`§<IG<P<D
`
`
`
`mm_><u_O_._.m_0wmn_
`
`m0<302<4
`
`EX 1004 Page 4
`EX 1004 Page 4
`
`DZ<
`
`ZO_._.O<E._.xw
`
`mw<m<._.<D
`
`E<$
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 4 0f 18
`
`US 6,839,751 B1
`
`402
`
`HIGH LEVEL
`PACKET
`DECODING
`
`
`
`
`GENERATE
`
`PACKET
`
`
`PACKET
`
`
`COMPILE
`STATE
`
`
`
`
`PARSE AND
`n ESORIPTION ~
`INSTRUCTION
`
`
`EXTRACT
`AND
`
`
`
`OPERATIONS
`OPERATIONS
`
`
`407
`
`
`
`
`406 ZAWEm’DPARS
`PRggE-QEOR
`
`
`INSTRUCTION
`EXTRACTION
`
`
`
`DATABASE
`DATABASE
`
`
`
`
`
`
`
`LOAD
`LOAD STATE
`
`PARSING
`Tl N
`
`SUBSYSTEM
`”$23235
`
`
`
`
`
`MEMORY
`MEMORY
`
`
`
`400
`
`0
`
`FIG. 4
`
`EX 1004 Page 5
`EX 1004 Page 5
`
`

`

`US. Patent
`
`Jan. 4,2005
`
`Sheet 5 0f 18
`
`US 6,839,751 B1
`
`502
`
`LOAD PACKET
`COMPONENT
`
`503
`
`504
`
`
`
`
`
`PACKET
`ORE IN PACKE I"
`KEY
`
`
`FETCH NODE AND
`PROCESS FROM
`PATTERN
`
`
`
`
`
`
`MORE
`NEXT
`PATTERN
`PACKET
`
`
`
`NODES?
`COMPONE
`
`
`511
`
`513
`
`. V r
`v V . I
`‘ n n
`
`
`PROCESS TO
`COMPONENT
`
`
`
`
`V
`
`‘
`
`PATTERN
`NODE
`
`510
`
`
`
`509
`
`500
`
`EX 1004 Page 6
`EX 1004 Page 6
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 6 0f 18
`
`US 6,839,751 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
`
`610
`
`LOAD KEY
`BUFFER
`
`@
`
`611
`
`NO
`
`606
`
`
`
`ORE EXTRACTIO ‘
`ELEMENTS?
`
`
`
`YES
`
`507
`
`APPLY EXTRACTION
`BEfi‘éfiiL?
`
`NEXT
`
`N o
`
`PACKET
`COMPON EN
`
`609
`
`
` MORE TO
`EXTRACT?
`
`
`
`608
`
`YE
`
`FIG. 6
`
`600
`
`EX 1004 Page 7
`EX 1004 Page 7
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 7 0f 18
`
`US 6,839,751 B1
`
`0
`
`EY BUFFER AND
`PATTERN NODE
`
`702
`
`LOAD PATTERN
`NODE ELEMENT
`
`708
`
`OUTPUT TO
`ANALYZER
`
`®
`
`709
`
`\
`
`700
`
`EX 1004 Page 8
`EX 1004 Page 8
`
`703
`
`704
`
`
`M RE PATTERN
`
`ONODES?
`
`
`YES
`
`HASH KEY BUFFER
`ELEMENT FROM
`PATTERN NODE
`
`705
`
`PACK KEY & HAS
`
`NEXT PACKET
`COMPONENT
`
`706
`
`707
`
`FIG. 7
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 8 0f 18
`
`US 6,839,751 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 PROCESS' IN
`CACHE AND TIMESTAMP
`
`810
`
`8”
`
`812
`
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`813m.
`
`FIG. 8
`
`EX 1004 Page 9
`EX 1004 Page 9
`
`

`

`
`
`CREATE SERVER STAT-
`
`
`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.
`
`
`
`
`
`
`
`SAVE 'PROGRAM',
`'VERSION' AND
`
`'PROTOCOL (TCP OR
`UDP)‘ WITH
`DESTINATION
`NETWORK ADDRESS.
`BOTH MAKE A KEY.
`
`US. Patent
`
`Jan. 4, 2005
`
`Sheet 9 0f 18
`
`US 6,839,751 B1
`
`901
`
`902
`
`910
`
`
`
`RPC
`REPLY
`
`'ORTMAPP
`‘ NNOUNCME
`
`
`'ORTMAPPE "
`
`
`
`
`RPC
`
`BIND LOOKU '
`REQUEST
`
`
`
`903
`
`EXTRACT PROGRAM
`
`GET 'PROGRAM',
`'VERSION‘, 'PORT' AND
`'PROTOCOL (TCP OR
`UDP)
`
`
`
`909
`
`
`
`EXTRACT PORT
`
`GET ‘PROGRAM',
`'VERSION' AND
`
`‘PROTOCOL (TCP OR
`UDP)‘
`
`SAVE REQUEST
`
`904
`
`
`
`
`
`RPC
`BIND
`
`
`LOOKUP
`REPLY
`
`
`
`900/
`
`
`
`EXTRACT
`
`LOOKUP REQUE ‘
`PROG RAM
`
`FIND 'PROGRAM'
`
`AND 'VERSION'
`GET 'PORT‘ AND
`
`WITH LOOKUP OF
`'PROTOCOL (TCP
`SOURCE NETWORK
`OR UDP)‘.
`ADDRESS.
`
`
`
`FIG. 9
`
`EX 1004 Page 10
`EX 1004 Page 10
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 10 0f 18
`
`US 6,839,751 B1
`
` PATTERN
`
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`100
`
`100
`
`1031
`
`1004
`
`
`
`INFO OUT
`
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS
`
`
`
`CONTRL N
`
`1031
`
`1007
`
`PATTERN
`RECOGNITN
`ENGINE
`(PRE)
`
`EXTRACTION ENGINE
`(SLICER)
`
`
`
`100'
`
`100:
`
`PA KET
`INPUT
`
`1012
`
`1021
`
`
`
`PARSER
`
`
`
`OUTPUT PACKET KEY
`PARSER INPUT BUFFER
`
`BUFFER AND PAYLOA
`MEMORY
`
`MEMORY
`
`
`
`
`
`
`Péflé'?
`INPUT BUFFER
`ANALYZER
`DATA REAn»
`
`INTERFACE
`INTERFACE
`
`
`‘
`V
`
`CONTROL
`CONTROL
`
` ANALYZER
`PACKET
`READY
`
`
`102
`1023
`
`FIG. 10
`
`1027
`
`EX 1004 Page 11
`EX 1004 Page 11
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 11 0f 18
`
`US 6,839,751 B1
`
`11oofik
`
`1101
`
`1103
`
`1115
`
`1118112
`
`0012/
`ENGINE
`
`
`PROCESS'1 )
`INSTRUCN
`DATABASE
`(SPID)
`
`
`IRS;
`ANALYZE-
`INTER
`”INTERFAC.
`AND
`1" FACE
`
`«18>
`
`
`
`
`UNIFIED
`FLOW
`
`PARSER
`KEY
`INTER- h UFFER
`
`(UFKB)
`FACE
`
`
`PROCESSR
`(SP)
`
`
`
` FLOW
`
`INSERTION/
`
`h DELETION _
`ENGINE
`(FIDE)
`
`
`1110
`
`FIG. 11
`
`1119112
`
`
`MEMORY
`UNIFIED
`INTER-
`MEMORY
`
`” CONTROL“ FACE
`(UMC)
`
`
`EX 1004 Page 12
`EX 1004 Page 12
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 12 0f 18
`
`US 6,839,751 B1
`
`1201
`
`
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`
`ACCESS
`
`
`CONVERSATION
`
`
`RECORD BIN
`
`
`1 202
`
`1203
`
`
`
`1200
`
`N
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`1204
`
`
`REQUEST NEXT
`BUCKET FROM
`
`CACHE
`
`-IN/BUCKET EMPTY
`
`
`1205
`
`YES
`
`1206
`
`1208
`
`1210
`
`
`
`NO INSERT KEY AND HASH
`
`
`N BUCKET, MARK 'USED
`WITH TIMESTAMP
`
`
`OMPARE CURRENT BIN 1209
`AND BUCKET RECORD
`
`
`
` SET UFKB FOR
`KEY TO PACKET
`
`
`MARK RECORD BIN AND
`BUCKET IIN PROCESS'
`
`AND 'NEW' IN CACHE
`
`
`=
`
`YES
`
`PACKET AS
`'DROP'
`
`1207
`
`1211
`
`SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`
`
`1213
`
`FIG. 12
`
`EX 1004 Page 13
`EX 1004 Page 13
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 13 0f 18
`
`US 6,839,751 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
`
`1 303
`
`1 304
`
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION
`
`1305
`
`
`
`
`
`
`
`
`
`
`
`
`
`SET STATE
`PROCESSOR
`INSTRUCTION
`POINTER TO
`VALUE FOUND IN
`CURRENT STATE
`
`
`
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET?
`
`NO
`
`
`
`1 308
`
`1310
`
`YES
`
`1 307
`
`TATES FOR THIS FLOW?
`
`
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`NO
`
`
`
`DONE PROCESSING
`
`
`
`
`
`1 309
`
`
`
`YES
`
`SET AND SAVE FLOW REMOVA
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`FLOW RECORD
`
`EX 1004 Page 14
`EX 1004 Page 14
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 14 0f 18
`
`US 6,839,751 B1
`
`m>>o._n_“.0
`
`
`mm<m<k<o9.08mEx=39“...50Ea92szLE
`.3:meESQzo:<_\,_mou_z_
`nsxogB<Exm
`
`226$ozEfizmQmuzooomE
`
`w._.<on5ZINE/E
`
`Z>>Ozv_DZ<
`__>>On_u___wmmDFODEFm
`
`
`
`DmOOmmZO_._.O<m._.Xm_
`
`wZO_._.<Im_n_O
`
`Z._.<O_n=mm<n_o
`
`ZO_._.<N_._<Z_n_
`
`mmN>._<Z<
`
`_>_m_._.m>mm_3m
`
`m_._.<._.m
`
`m_Z_IO<_>_
`
`mOhOmflmm
`
`mwvF
`
`m_._.<._.m
`
`m._w>._<z<
`
`§ww>mm3w_mmmm<m
`
`EX 1004 Page 15
`EX 1004 Page 15
`
`
`
`
`
`

`

`51w
`
`6SU
`
`1B157,
`
`9-&mFGE
`
`om<ommofimmfizMxmozfimz
`
`Nor
`
`US. Patent
`
`J
`
`24,
`
`m8232
`
`._.m_x0<n_
`
`202.5500.
`
`mO_>m_D
`
`Lvmm
`
`mw<m<._.<n_
`
`
`
`.mN>._<z<EmmE
`
`maaw,
`
`mom_.
`
`5>mo_>m__>_m50:
`
`hlS08
`
`motzo:
`
`FNF
`
`EX 1004 Page 16
`EX 1004 Page 16
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 16 0f 18
`
`US 6,839,751 B1
`
`
`
`\-set=12
`
`FIG. 16
`
`EX 1004 Page 17
`EX 1004 Page 17
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 17 0f 18
`
`US 6,839,751 B1
`
`1702
`
`offset
`12 to 13
`
`Type
`
`,
`VIIIIIIIIII‘
`
`1704
`
`X
`
`1706
`
`1708
`
`Type (2)
`h 1
`
`H
`
`FIG. 17A
`
`1712
`
`
`
`mmmmmywwgyllgm
`
`
`mm mm-
`
`[5,35, 4 "mm—rymmmam
`
`
`
`
`
`
`VIII/[£9Wififlifflfli’llllllllllll
`
`-1]
`
`Dst Hash (2)
`Src Address
`
`Src Hash (2
`
`-ol<1>
`
`IG. 178
`
`IDP = 0X0600*
`IP = 0X0800*
`CHAOSNET = 0x0804
`ARP = 0X0806
`VIP = OXOBAD*
`VLOOP = OXOBAE
`VECHO = OXOBAF
`NETBIOS-3COM = OXSCOO -
`Ox3COD#
`DEC-MOP = 0x6001
`DEC-RC = 0x6002
`DEC-DRP = 0X6003*
`DEC-LAT = 0X6004
`DEC-DIAG = 0x6005
`DEC-LAVC = 0X6007
`RARP = 0x8035
`ATALK = 0X809B*
`VLOOP = 0x8004
`VECHO = 0X80C5
`SNA—TH = 0X80D5*
`ATALKARP = 0X80F3
`lPX = 0x8137*
`SNMP = 0x814C#
`IPv6 = OX86DD*
`LOOPBACK = 0x9000
`
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`
`# L3 Re-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#
`ElGRP = 88
`OSPF = 89
`
`* L4 Decoding
`
` / F
`
`-et = L3 + (lHL/4)
`
`EX 1004 Page 18
`EX 1004 Page 18
`
`

`

`US. Patent
`
`Jan. 4, 2005
`
`Sheet 18 0f 18
`
`US 6,839,751 B1
`
`
`
`I._.Ozm:DIE.“—
`
`PROTOCOL
`TYPE ("32
`
`mEiiii!
`iihiili!rihhiiii!
`fih‘hfii‘fi
`.Ihi...§
`5.5%
`
`hiiiiiiii
`
`hiiinllhum.
`
`1 642
`
`1802-1
`
`FIG. 18A
`
`8701/
`
`L
`
`UT NUM
`___}
`
`058H
`
`m.
`
`000m:.>m
`
`GAME“5
`
`.._OOO._.Omn_
`FEE
`
`FIG. 188
`
`EX 1004 Page 19
`EX 1004 Page 19
`
`
`
`

`

`US 6,839,751 B1
`
`1
`RE-USING INFORMATION FROM DATA
`TRANSACTIONS FOR MAINTAINING
`STATISTICS IN NETWORK MONITORING
`
`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/608,237 for
`METHOD AND APPARATUS FOR MONITORING
`TRAFFIC IN ANETWORK, to inventors Dietz, et al., filed
`Jun. 30, 2000, and incorporated herein by reference.
`US. patent application Ser. No. 09/609,179 for PRO-
`CESSING PROTOCOL SPECIFIC INFORMATION IN
`PACKETS SPECIFIED BYA PROTOCOL DESCRIPTION
`
`LANGUAGE, to inventors Koppenhaver, et al., filed Jun.
`30, 2000, and incorporated herein by reference.
`US. patent application Ser. No. 09/608,266 for ASSO-
`CIATIVE CACHE STRUCTURE FOR LOOKUPS AND
`UPDATES OF FLOW RECORDS IN A NETWORK
`MONITOR, to inventors Sarkissian, et al., filed Jun. 30,
`2000, 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.,
`filed Jun. 30, 2000, 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.
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material that is subject to copyright protection. The
`copyright owner has no objection to the facsimile reproduc-
`tion by anyone of the patent document or
`the patent
`disclosure, as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`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.),
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`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 notificatior of network problems.
`Related and incorporated by reference US. patent appli-
`cation Ser. No. 09/607,237 for METHOD AND APPARA-
`TUS FOR MONITORING TRAFFIC IN A NETWORK, to
`inventors Dietz, et al, describes a network monitor that
`includes carrying out protocol specific operations on indi-
`vidual packets including extracting information from header
`fields in the packet
`to use for building a signature for
`identifying the conversational flow of the packet and for
`recognizing future packets as belonging to a previously
`encountered flow. A parser subsystem includes a parser for
`recognizing different patterns in the packet that identify the
`protocols used. For each protocol
`recognized, a slicer
`extracts important packet elements from the packet. These
`form a signature (i.e., key) for the packet. The slicer also
`preferably generates a hash for rapidly identifying a flow
`that may have this signature from a database of known
`flows.
`
`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.
`It is advantageous to collect statistics on packets passing
`through a point in a network rather than to simply count each
`and every packet. By maintaining statistical measures in the
`flow-entries related to a conversational flow, embodiments
`of the present invention enable specific metrics to be col-
`lected in real-time that otherwise would not be possible. For
`example,
`it
`is desirable to maintain metrics related to
`bi-directional conversations based on the entire flow for
`
`each exchange in the conversation. By maintaining the state
`of flow, embodiments of the present invention also enable
`certain metrics related to the states of flows to be deter-
`mined.
`
`Most prior-art network traffic monitors that use statistical
`metrics collect only end-point and end-of-session related
`statistics. Examples of such commonly used metrics include
`packet counts, byte counts, session connection time, session
`timeouts, session and transport response times and others.
`
`EX 1004 Page 20
`EX 1004 Page 20
`
`

`

`US 6,839,751 B1
`
`3
`All of these deal with events that can be directly related to
`an event in a single packet. These prior-art systems cannot
`collect some important performance metrics that are related
`to a complete sequence of packets of a flow or to several
`disjointed sequences of the same flow in a network.
`Time based metrics on application data packets are impor-
`tant. Such metrics could be determined if all the timestamps
`and related data could be stored and forwarded for later
`analysis. However when faced with thousands or millions of
`conversations per second on ever faster networks, storing all
`the data, even if compressed, would take too much
`processing, memory, and manager down load time to be
`practical.
`Thus there is a need for maintaining and reporting time-
`base metrics from statistical measures accumulated from
`packets in a flow.
`Network data is properly modeled as a population and not
`a sample. Thus, all the data needs to be processed. Because
`of the nature of application protocols, just sampling some of
`the packets may not give good measured related to flows.
`Missing just one critical packet, such as one the specified an
`additional port that data will be transmitted on, or what
`application will be run, can cause valid data to be lost.
`Thus there is also a need for maintaining and reporting
`time-base metrics from statistical measures accumulated
`
`from every packet in a flow.
`There also is a need to determine metrics related to a
`
`sequence of events. A good example is relative jitter. Mea-
`suring the time from the end of one packet in one direction
`to another packet with the same signature in the same
`direction collects data that relates normal jitter. This type of
`jitter metric is good for measuring broad signal quality in a
`packet network. However, it is not specific to the payload or
`data item being transported in a cluster of packets.
`Using the state processing described herein, because the
`state processor can search for specific data payloads,
`embodiments of monitor 300 can be programmed to collect
`the same jitter metric for a group of packets in a flow that are
`all related to a specific data payload. This allows the
`inventive system to provide metrics more focused on the
`type of quality related to a set of packets. This in general is
`more desirable than metrics related to single packets when
`evaluating the performance of a system in a network.
`Specifically, the monitor system 300 can be programmed
`to maintain any type of metric at any state of a conversa-
`tional flow. Also the system 300 can have the actual statistics
`programmed into the state at any point. This enables
`embodiments of the monitor system to collect metrics
`related to network usage and performance, as well as metrics
`related to specific states or sequences of packets.
`Some of the specific metrics that can be collected only
`with states are events related to a group of traffic in one
`direction, events related to the status of a communication
`sequence in one or both directions, events related to the
`exchange of packets for a specific application in a specific
`sequence. This is only a small sample of the metrics that
`requires an engine that can relate the state of a flow to a set
`of metrics.
`
`In addition, because the monitor 300 provides greater
`visibility to the specific application in a conversation or flow,
`the monitor 300 can be programmed to collect metrics that
`may be specific to that type of application or service. In other
`word, if a flow is for an Oracle Database server, an embodi-
`ment of monitor 300 could collect the number of packets
`required to complete a transaction. Only with both state and
`application classification can this type of metric be derived
`from the network.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Because the monitor 300 can be programmed to collect a
`diverse set of metrics, the system can be used as a data
`source for metrics required in a number of environments. In
`particular, the metrics may be used to monitor and analyze
`the quality and performance of traffic flows related to a
`specific set of applications. Other implementation could
`include metrics related to billing and charge-back for spe-
`cific traffic flow and events with the traffic flows. Yet other
`
`implementations could be programmed to provide metrics
`useful for troubleshooting and capacity planning and related
`directly to a focused application and service.
`SUMMARY
`
`Another aspect of the invention is determining quality of
`service metrics based on each and every packet. A method
`of and monitor apparatus for analyzing a flow of packets
`passing through a connection point on a computer network
`are disclosed that may include such quality of service
`metrics. The method includes receiving a packet from a
`packet acquisition device, and looking up a flow-entry
`database containing flow-entries for previously encountered
`conversational flows. The looking up to determine if the
`received packet is of an existing flow. Each and every packet
`is processed. If the packet is of an existing flow, the method
`updates the flow-entry of the existing flow, including storing
`one or more statistical measures kept in the flow-entry. 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
`storing one or more statistical measures kept in the flow-
`entry. The statistical measures are used to determine metrics
`related to the flow. The metrics may be base metrics from
`which quality of service metrics are determined, or may be
`the quality of service metrics.
`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.
`
`EX 1004 Page 21
`EX 1004 Page 21
`
`

`

`US 6,839,751 B1
`
`5
`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.
`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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`to store elements of the pattern, parse and extraction data-
`base used by the parser subsystem in accordance to one
`embodiment of the invention.
`
`50
`
`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.
`
`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
`
`55
`
`60
`
`65
`
`6
`
`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
`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
`that provides a framework for design of communication
`protocol layers. This model, shown in table form below,
`serves as a basic reference for understanding the function-
`ality of existing communication protocols.
`
`ISO MODEL
`
`Layer
`
`Functionality
`
`Example
`
`7
`6
`5
`4
`3
`2
`
`1
`
`Application
`Presentation
`Session
`Transport
`Network
`Data Link
`
`Physical
`
`Telnet, NFS, Novell NCP, HTTP,
`H.323
`XDR
`RPC, NETBIOS, SNMP, etc.
`TCP, Novel SPX, UDP, etc.
`IP, Novell IPX, VIP, AppleTalk, etc.
`Network Interface Card (Hardware
`Interface). MAC layer
`Ethernet, Token Ring, Fra