`Us 6,954,789 B2
`Dietz et al.
`(45) Date of Patent:
`Oct. 11,2005
`
`(10) Patent N0.:
`
`USOO6954789B2
`
`(54)
`
`(75)
`
`METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`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)
`
`(73)
`
`Assignee: Hi/fn, Inc., Los Gatos, CA (US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`
`(22)
`
`(65)
`
`(63)
`
`(60)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Appl. No.: 10/684,776
`
`Filed:
`
`Oct. 14, 2003
`Prior Publication Data
`
`US 2004/0083299 A1 Apr. 29, 2004
`
`Related U.S. Application Data
`
`Continuation of application No. 09/608,237, filed on Jun.
`30, 2000, now Pat. No. 6,651,099.
`Provisional application No. 60/141,903, filed on Jun. 30,
`1999.
`
`Int. Cl.7 .............................................. G06F 15/173
`U.S. Cl.
`........................................ 709/224; 370/392
`Field of Search ................................. 709/200, 201,
`709/220, 223, 224, 231, 232, 236, 238—240,
`246; 370/389, 392
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3,949,369 A
`4,458,310 A
`4,559,618 A
`
`.............. 711/128
`4/1976 Churchill, Jr.
`7/1984 Chang ........................ 711/119
`12/1985 Houseman et al.
`........... 365/49
`
`(Continued)
`
`I
`
`FOREIGN PATENT DOCUMENTS
`
`JP
`
`2003—445 10 A
`
`2/2003
`
`OTHER PUBLICATIONS
`
`Advanced Methods for Storage and Retrieval in Image;
`http://www.cs.tulane.edu/ww/Prototype/proposal.html;
`1998.
`
`(Continued)
`
`Primary Examiner—Moustafa M. Meky
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`
`(57)
`
`ABSTRACT
`
`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.
`
`49 Claims, 18 Drawing Sheets
`
`
`FAITEFIN. PARS
`AND
`EXTRACTION
`
`DATABASE
`
`
`
`
`PROTOCOL
`11 STATE
`IDENTIFICATID
`
`
`
`
`I
`
`310
`
`
`
`COMPILER
`AND
`OPTIMIZER
`
`
`3:15 II
`
`(
`eDATAGHAM
`PROTOCOL
`
`
`SELECTION
`STATE
`LAYER
`DESCIFTIO
`LANGUAGE
`PROCESSNt
`OPERATION .
`
`
`
`
`
`
`FARSEFI 311
`
`
`EXTRACT
`
`
`wCONVEHsATIOBUILD UNIQUE LOOKUP
`IDENTIFYING
`FROMKNOWN
`INFORMATIO
`
`
`
`
`
`(Ell)
`asconns
`(DB 324
`
`
`IA CACHE
`
`
`RECORD
`
`
`
`
`
`PROCESSOR
`INSTRUCTION
`
`DATABASE
`
`
`
`EX 1005 Page 1
`EX 1005 Page 1
`
`IIIIII
`
`
`
`||II|I
`
`32A
`.—
`
`“FLOW'
`KNOWN
`
`
`VE‘
`
`315
`MORE
`CLASSIFICATID
`320 VES
`
`
`
`US 6,954,789 B2
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`4,736,320 A
`4,891,639 A
`4,910,668 A
`4,972,453 A
`5,101,402 A
`5,247,517 A
`5,247,693 A
`5,249,292 A
`5315580 A
`5,339,268 A
`5,351,243 A
`5365514 A
`5,375,070 A
`5,394,394 A
`5,414,650 A
`5,414,704 A
`5,430,709 A
`5432776 A
`5,493,689 A
`5,500,855 A
`55117213 A
`5,511,215 A
`5,530,834 A
`5,530,958 A
`55357338 A
`5,568,471 A
`55747875 A
`5586266 A
`5,606,668 A
`5,608,662 A
`5,634,009 A
`596519002 A
`5,680,585 A
`5,684,954 A
`5,703,877 A
`5,720,032 A
`5,721,827 A
`5,732,213 A
`5,740,355 A
`5,749,087 A
`5,761,424 A
`5,761,429 A
`57647638 A
`5,781,735 A
`3’32??? 2
`,
`,
`5,799,154 A
`5,802,054 A
`5,805,808 A
`5,812,529 A
`5,819,028 A
`
`5,825,774 A
`
`....................... 364/300
`4/1988 Bristol
`1/1990 Nakamura .............
`340/8255
`
`--
`3/1990 Okamete et al-
`711/207
`........... 379/10
`11/1990 Daniel, III et al.
`3/1992 Chiu et al. .................... 370/17
`
`9/1993 Ross et ah
`370/85~5
`....................... 395/800
`9/1993 Bristol
`9/1993 Chiappa ..................... 395/650
`
`5/1994 Phaal
`~~~~~ 370/13
`8/1994 Machida ...................... 365/49
`9/1994 Kalkunte et al.
`............. 370/92
`
`11/1994 Hershey et ah -
`~~ 370/17
`............. 364/550
`12/1994 Hershey et al.
`2/1995 Crowther et al.
`............. 370/60
`
`5/1995 Hekhuis
`364/715~02
`5/1995 Spinney ~~~~~~~~~~~~~~~~~~~~~~~ 370/60
`7/1995 Galloway .................... 370/13
`
`~~ 370/17
`7/1995 Harper
`~~~~~~~~~~~~~
`~~~~~ 395/821
`2/1996 Waelawsky et ah
`3/1996 Hershey et al.
`............... 370/17
`
`4/1996 Correa
`~ 395/800
`4/1996 Terasaka et al-
`------------ 395/800
`6/1996 Colloff et al.
`.............. 711/136
`
`6/1996 Aganvaletah
`711/3
`---------
`395/2002
`7/1996 Krause et al-
`10/1996 Hershey et al.
`............... 370/17
`
`11/1996 Stahsfield etal-
`-
`395/403
`12/1996 Hershey et ah ~~~~~~~~ 395/200-11
`2/1997 Shwed .................. 395/200.11
`-
`- 364/724~01
`3/1997 Large etal-
`
`-
`- 395/200-11
`5/1997 Idden etal-
`
`7/1997 Van Seters et ah
`370/392
`~~~~~~~~~~~~~~~~~~~~~~ 703/26
`10/1997 Bruell
`11/1997 Kaiserswerth et al-
`395/2002
`
`12/1997 Nuher et ah ~~~~~~~
`370/395
`2/1998 Picazo, Jr. et al
`395/2002
`
`2/1998 Logan et al.
`709/217
`. 395/20011
`3/1998 Gesseletal.
`
`4/1998 Watanabe et a1.
`. 395/183.21
`
`..
`5/1998 Hoover et al.
`711/108
`
`
`395/200.47
`..
`6/1998 Adams et al.
`6/1998 Thompson .......... 709/224
`
`----- 370/401
`6/1998 KetChum
`
`7/1998 Southard .......
`395/200.54
`3/1998 HerShey et al'
`'
`""" 364557
`
`/1998 McCreery et al.
`.
`. 395/200.61
`8/1998 Kuriyan ................ 709/223
`
`9/1998 Bellenger
`370/401
`
`..
`9/1998 Hasani et a1.
`395/2002
`9/1998 Czarnik et al.
`............. 370/245
`10/1998 Manghirmalani
`. 395/185.1
`et al.
`.....
`
`10/1998 Ready et al.
`............... 370/401
`
`.......... 395/200.59
`11/1998 Shwed et al.
`5,835,726 A
`11/1998 Schwaller et al.
`..... 395/200.54
`5,838,919 A
`11/1998 Huffman ..................... 382/155
`5,841,895 A
`
`12/1998 Anderson et al.
`..
`370/241
`5,850,386 A
`........... 370/252
`12/1998 Anderson et al.
`5,850,388 A
`1/1999 Welch, Jr. et al.
`...... 395/20054
`5,862,335 A
`
`........ 707/10
`3/1999 de la Salle
`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
`................ 711/207
`12/1999 Carter et al.
`6,003,123 A
`1/2000 Hendel et a1.
`.............. 370/392
`6,014,380 A
`
`8/2000 Chen et al.
`.....
`370/231
`6,097,699 A
`................ 370/469
`9/2000 Engel et al.
`6,115,393 A
`9/2000 Zaumen et a1.
`............. 370/229
`6,118,760 A *
`
`6/2001 Kerr et a1.
`......
`703/27
`6,243,667 B1 *
`.................. 704/43
`7/2001 Cidon et al.
`6,269,330 B1
`8/2001 Gupta etal.
`................ 370/489
`6,272,151 B1
`
`8/2001 Vaidya ...........
`713/201
`6,279,113 B1
`............... 709/224
`8/2001 Leung et al.
`6,282,570 B1
`12/2001 Chapman et al.
`........... 370/232
`6,330,226 B1
`
`3/2002 Beigi et a1.
`........
`370/252
`6,363,056 B1
`............... 379/32
`4/2002 Lawson et al.
`6,381,306 B1
`7/2002 Galand et al.
`.............. 370/231
`6,424,624 B1
`
`8/2002 Rossmann
`455/4221
`6,430,409 B1
`9/2002 Jorgensen ................... 370/238
`6,452,915 B1 *
`9/2002 Trcka et al.
`................ 709/224
`6,453,345 B2
`
`9/2002 Muller et a1.
`709/250
`6,453,360 B1 *
`................ 709/238
`6,466,985 B1 * 10/2002 Goyal etal.
`6,483,804 B1 * 11/2002 Muller et al.
`............... 370/230
`
`6,510,509 B1 *
`“2003 Chopra et a1.
`..
`..... 712/13
`................. 709/202
`6,516,337 B1
`2/2003 Tripp etal.
`6,519,568 B1
`2/2003 Harvey etal.
`................. 705/1
`
`6,570,875 B1 *
`5/2003 Hegde ............
`370/389
`9/2003 Bullard ....................... 709/237
`6,625,657 B1
`6,651,099 B1
`11/2003 Dietz et al.
`................. 709/224
`6,791,947 B2 *
`9/2004 Oskouy et al.
`............. 370/238
`
`OTHER PUBLICATIONS
`.
`.
`.
`.
`Measurement and Analy51s of the D1g1tal DECT propagatlon
`Channel; IEEE; 1998.
`R, Periakaruppam and E. Nemeth. “GTrace—A Graphical
`Traceroute T001.”
`1999 UseniX LISA. Available on
`www.caida.org, URL: http://www.caida.org/outreach/pa-
`pers/1999/GTrace/GTrace.pdf.
`W. Stallings. “Packet Filtering in the SNMP Remote Moni-
`”
`.
`.
`ton N0.“ 1994 AVallable 0“ WWW~de~C°m> URL: httpi”
`www.de.com/documents/s=1013/dd]9411h/9411h.htm.
`“Technical Note: the Narus System,” Downloaded Apr. 29,
`1999 from www.narus.com, Narus Corporation, Redwood
`City California.
`
`* cited by examiner
`
`EX 1005 Page 2
`EX 1005 Page 2
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 1 0f 18
`
`US 6,954,789 B2
`
`100 _
`CUENT4
`
`1 08
`
`W
`107
`
`ANALYZER
`
`—
`CLIENT 3
`
`fi
`106
`
`_
`SERVER .
`
`1 16
`
`N1 10
`
`121
`
` DATA COMMUNICATIONS
`
`NETWORK
`
`—
`
`123
`
`— 105 —
`
`W112
`
`CLIENT 2
`
`CLIENT1
`
`FIG. 1
`
`102
`
`125
`
`118
`
`104
`
`EX 1005 Page 3
`EX 1005 Page 3
`
`
`
`US. Patent
`
`0021,1a0
`
`2aehS
`
`2B987.,459,6SU
`
`5838
`
`Nx\
`
`
`
`3NmW3%v8»new8%5%8%uMmm>mm.20509;:Ezmjo“
`
`
`
`
`EN\\2%NR“EmuEN
`
`EX 1005 Page 4
`EX 1005 Page 4
`
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 3 0f 18
`
`US 6,954,789 132
`
`mw<m<k<o
`
`m>>O.ELO
`
`
`
`>>Ol_u_._>>m2
`
`womoomm
`
`meOOA
`
`20mm
`
`Z>>OZx
`
`meOONE
`
`mk<DmD
`
` mh<hww_:59“...585%.
`
`
`wwmmwm,o:<om:2mg
`
`
` L304“..._O_H<wmm>ZOO_mDQZD01:3m
`>wv_
`
`wz_>n_:2mo_mmwwwrwmm.
`
`0.2251;
`
`
`
`Km_IIIIIIIIIIIII._Q,$.me
`
`
`
`Jom\.v_I
`
`Fo<mem
`
`.z<m~>4<z<_8m3m
`
`
`
`mm<m.metki
`
`DZ<
`
`ZO_._.0<E._.xm
`
`mm<m<k<o
`
`Efi:
`
`.au
`
`mmN>._<z<
`
`uzmmmOOmm
`
`..ZO_._.<mmn_O
`
`_>_<IO<._.<D
`
`mw><4
`
`z._.<0_n__mm<1_0
`
`ZOF<N3<ZE
`
`
`
`EmemOOmQ
`
`20:03me2_
`
`wm<m<h<o
`
`Em.=n=200
`
`DZ<
`
`IMNSFQO
`
`orm
`
`EX 1005 Page 5
`EX 1005 Page 5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`US. Patent
`
`Oct
`
`. 11,2005
`
`Sheet 4 0f 18
`
`US 6,954,789 132
`
`. 401
`
`402
`
`
`
`HIGH LEVEL
`PACKET
`DECOWNG
`IESCNPWON‘
`
`COMPlE
`IESCNPWON‘
`
`
`
`403
`
`404
`
`GENERATE
`PACKET
`PARSEAND
`EXTRACT
`
`OPERAHONS
`
`
`
`406 7/‘A'ITERN, PARE AND
`DATABASE
`
`EXTRACWON
`
`408
`
`409
`
`LOAD
`PARQNG
`SUBSYSTEM
`MEMORY
`
`MEMORY
`
`LOADSTATE
`NSTRUCWO
`DATABASE
`
`405
`
`V
`
`- A
`
`
`
`PACKET
`STATE
`
`AND
`
`OPERAHONS
`
`
`
`407
`
`DATABASE
`
`STATE
`PROCESSOR
`INSTRUCWON
`
`400
`
`EX 1005 Page 6
`EX 1005 Page 6
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 5 0f 18
`
`US 6,954,789 B2
`
`502
`
`
`
`
`
`
`ORE IN PACK "
`
`
`
`PACKET
`
`
`KEY
`
`
`503
`
`504
`
`
`FETCHNODEANI
`PROCESS FROM
`
`';I :L
`
`
`
`
`
`N EXT
`MORE
`PATTERN
`PACKET
`
`
`NODES?
`COMPONE
`
`
`
`
`
`‘9. V‘.. “'
`PROCESS TO
`
`
`
`COMPONENT 510
`
`513
`
`511
`
`500
`
`EX 1005 Page 7
`EX 1005 Page 7
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 6 0f 18
`
`US 6,954,789 B2
`
`0
`
`PACKET
`COMPONENT AND
`PATTERN NODE
`
`502
`
`603
`
`604
`
`NO
`
`606
`
`607
`
`LOAD PACKET
`COMPONENT
`
`610
`
`MORE PACKE
`COMPONENT
`
`
`
`YES
`
`FETCH EXTRACTION
`
`ND PROCESS FRO
`PATTERNS
`
`605
`
`LOAD KEY
`BUFFER
`
`6
`
`N.
`
`NEXT
`PACKET
`COMPONEN
`
`611
`
`609
`
`
`ELEMENTS?
`ORE EXTRACTIO ‘
`
`
`
`
`YES
`
`APPLY EXTRACTIO
`P%%CESSEL‘%
`C
`PON
`
`
`MORE TO
`EXTRACT?
`
`
`
`
`608
`
`YE
`
`\
`
`600
`
`FIG. 6
`
`EX 1005 Page 8
`EX 1005 Page 8
`
`
`
`US. Patent
`
`Oct. 11, 2005
`
`Sheet 7 0f 18
`
`US 6,954,789 132
`
`o
`
`EY BUFFER AND
`PATTERN NODE '.
`
`702
`
`703
`
`704
`
`LOAD PATTERN
`NODE ELEMENT
`
`
`
`
`MORE PATTER
`NODES?
`
`YES
`
`EY BUFFER
`AS
`ELEMENT FROM
`PATTERN NODE
`
`705
`
`PACK KEY 81 HAS
`
`NEXT PACKET
`COMPONENT
`
`706
`
`707
`
`FIG. 7
`
`708
`
`OUTPUT To
`ANALYZER
`
`709
`
`700
`
`EX 1005 Page 9
`EX 1005 Page 9
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 8 0f 18
`
`US 6,954,789 B2
`
`0
`
`UFKB ENTRY FOR
`
`800 \
`
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH
`
`803
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`804
`
`806
`
`
`
`805
`
` ORE BUCKET
`
`IN THE BIN?
`
`YES
`
`“0
`
`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
`
`813$.
`
`FIG. 8
`
`EX 1005 Page 10
`EX 1005 Page 10
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 9 0f 18
`
`US 6,954,789 B2
`
`901
`
`902
`
`
`
`RPC
`
`BIND LOOKU '
`
`
`‘ NNOUNCME
`.
`
`REQUEST
`ORTMAPP
`ORTMAPP .
`
`
`
`909
`
`EXTRACT PROGRAM
`
`EXTRACT PORT
`
`GET 'PROGFIAM'.
`GET 'PROGRAM‘,
`
`
`'VERSION', 'PORT' AND
`'VERSION' AND
`
`
`'PFIOTOCOL (TCP OR
`'PROTOCOL (TCP OR
`
`
`
`UDP)
`UDP)‘
`
`
`
`
`
`
`CREATE SERVER STA E
`
`SAVE REQUEST
`
`904
`
`
`
`
`
`
`
`
`SAVE 'PROGRAM’,
`
`SAVE 'PROGRAM',
`'VERSION' AND
`
`
`'VERSION'. 'PORT' AND
`'PROTOCOL (TCP OR
`
`
`
`'PROTOCOL (TCP OR
`UDP)‘ WITH
`
`UDP)‘ WITH NETWORK
`DESTINATION
`
`
`ADDRESS IN SERVER
`NETWORK ADDRESS.
`
`
`STATE DATABASE. KEY
`BOTH MAKE A KEY.
`
`ON SERVER ADDRESS
`
`AND TCP OR UDP PORT.
`
`
`900/
`
`
` EXTRACT
`LOOKUP REQUE
`PROGRAM
`
`FIND 'PROGRAM'
`AND 'VERSION'
`
`GET 'PORT‘ AND
`
`
`WITH LOOKUP OF
`
`
`“PROTOCOL (TCP
`SOURCE NETWORK
`OR UDP)‘.
`
`
`
`ADDRESS.
`
`FIG. 9
`
`EX 1005 Page 11
`EX 1005 Page 11
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 10 0f 18
`
`US 6,954,789 B2
`
` PATTERN
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`100‘
`
`100
`
`100
`
`1031
`
`1004
`
` INFO OUT
`
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS CONTRL N
`
`100-
`
`
`
`PATTERN
`RECOGNITN
`
`
`EXTRACTION ENGINE
`
`ENGINE
`
`(SUCER)
`
`
`
`(PRE)
`
`
`1031
`
`1 007
`
`100&\\\
`
`
`
`3‘ V’—
`
`INPUT
`
`1012
`
`1021
`
`
`PARSER
`
`
`
`PARSER INPUT BUFFER
`OUTPUT PACKET KEY
`
`
`MEMORY
`BUFFER ANDPAYLOAo
`
`MEMORY
`
`
`
`
`PéA-IQAKRETI
`
`
`
`
`
`INPUT BUFFER
`ANALYZER DATA READY
`
`INTERFACE
`INTERFACE
`
`
`CONTROL
`CONTROL
`1
`~
`
`
`ANALY E-
`PACKET
`READY
`
`102
`1023
`
`FIG. 10
`
`1027
`
`EX 1005 Page 12
`EX 1005 Page 12
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 11 0f 18
`
`US 6,954,789 B2
`
`1100-5*
`
`1101
`
`1103
`
`1115
`
`1118 112
`
`1107
`
`
`
`
`
`ANALYZE'
`13E:
`HOST
`ENGWE
`
`H INT/ElngC u INTER-
`(LUE)
`
`FACE
`
`
`STATE
`CONTROL
`aflB)
`
`
`PROCESS"
`(Acm)
`
`
`INSTRUCN
`
`DATABAS:
`UNHHED
`
`FLOW
`
`PARSER
`KEY
`INTER- H-UFFER
`
`
` (UFKB)
`
`FACE
`
`
` PROCESSR
`(SP)
`
`
`1119112
`
`
`
`
`
`ENGINE
`
`(FIDE)
`
`
`MEMORY
`UNIFIED
`INTER.
`MEMORY
`
`H CONTROL” FACE
`(UMC)
`
`
`EX 1005 Page 13
`EX 1005 Page 13
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 12 0f 18
`
`US 6,954,789 B2
`
`1201
`
` UFKB ENTRY FOR
`
`
`PACKET WITH
`
`
`STATUS 'NEW'
`
`
`
`
`
`ACCESS
`CONVERSATION
`
`RECORD BIN
`
`
`
`1202
`
`1203
`
`1204
`
`
`
`REQUEST NEXT
`BUCKET FROM
`1205
`
`CACHE
`
`
`1206
`
`.
`'
`
`NO .
`
`1207
`
`1208
`
`1210
`
`
`
`
`
`SET UFKB FOR
`PACKET AS
`'DROP'
`
` 1211
`
`
`
`
`
`
`1209
`OMPARE CURRENT BI
`
`AND BUCKET RECORD
`
`
`KEY TO PACKET
`
`
`
`
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS'
`AND 'NEW' IN CACHE
`
`SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`1213
`
`
`
`FIG. 12
`
`EX 1005 Page 14
`EX 1005 Page 14
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 13 0f 18
`
`US 6,954,789 B2
`
`1300 Tu
`
`$1301
`
`UFKB ENTRY FOR
`PACKET WITH STATUS
`' w- on 'FOUND'
`I
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO
`ALUE FOUND IN UFKB ENTRY
`
`FETCH INSTRUCTION FROM
`STATE PROCESSOR
`INSTRUCTION MEMORY
`
`1302
`
`1303
`
`‘304
`
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION
`
`1305
`
`
`
`
`
`SET STATE
`
`PROCESSOR
`
`
`
`INSTRUCTION
`POINTER TO
`
`I
`VALUE FOUND |
`CURRENT STAT:
`
`
`
`NO
`
`
`DONE PROCESSING
`STATES FOR THIS
`
`PACKET?
`
`
`1308
`YES
`1310
`
`
`
`SAVE STATE
`
`PROCESSOR
`
`
`INSTRUCTION
`
`POINTER IN
`
`
`CURRENT FLOW
`RECORD
`
`NO
`
`DONE PROCESSING
`TATES FOR THIS FLO
`
`YES
`
`
`
`
`
`
`SET AND SAVE FLOW REMOVA
`STATE PROCESSOR
`
`
`INSTRUCTION IN CURRENT
`
`FLOW RECORD
`
`@1313
`
`FIG. 13
`
`1307
`
`1309
`
`1311
`
`EX 1005 Page 15
`EX 1005 Page 15
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 14 0f 18
`
`US 6,954,789 132
`
`@504;m0
`
`2&3me
`
`wh<kw\
`
`@369BEEN.z<mN>._<z.
`
`
`
`
`
`2262:muzwoomm025325
`
`mZOF<mmmO
`ZOCbSnFXm
`____________mO_._.<SEOH_Z__
`Emw>mm3m_mmwm<m
`
`
`
`
`
`mm<m§<o308:down.wE;zmmfii
`
`Z>>OZv_
`
`OEOOmm
`
`
`mgr/REDZEmEIr/xn.
`
`..>>On_u.__mmkaODmkm
`oz<
`
`ZO_._.<N_._<ZE
`
`H<0E_mm<._0
`
`mm~>4<z<
`
`Emkm>mm3m.
`
`.2PER
`
`m_m>1.<z<
`
`whim
`
`m_2_I932
`
`mOFOMAMw
`
`mm:
`
`EX 1005 Page 16
`EX 1005 Page 16
`
`
`
`
`
`
`
`
`
`
`
`US. Patent
`
`1,
`
`1.55%w83vom—0:658.
`
`Fm¥O<Q
`
`vmm
`
`mm<m<k<o
`
`;wN>4<Z<
`
`Qmmmm<a
`
`mammom?
`
`
`
`%Eozms..0mmmoom.M.So:
`
`”mm
`
`SU
`
`2B987w4
`
`MN.6,m_.OE
`
`8920H5552
`
`oxmozcmzNor—
`
`motzoz
`
`am.9
`
`EX 1005 Page 17
`EX 1005 Page 17
`
`
`
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 16 0f 18
`
`US 6,954,789 B2
`
`
`
`EX 1005 Page 18
`EX 1005 Page 18
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 17 0f 18
`
`US 6,954,789 B2
`
`1702
`
`‘
`offset
`12 to 13 _WIIIIIIIIIA‘
`
`\
`
`1706
`
`as
`
`H If?”
`- “-17%
`_
`L3 Ofie‘ ‘ 14
`
`FIG 1 7A
`.
`
`1712
`
`M +
`(lHL/4
`-1]
`
`'7, 7,411.,
`
`-.,,,..
`
`7,, _I 1,,3 I
`
`plai[ME/{IIIIJ’MIJEMIIMIIM
`
`
`”nirln—mwimm
`
`
`Src Address
`
`
`
`Dst Address_
`
`
`VIII/lifi'iiiifiWiiifiilllllllllllll
`
`Dst Address
`
`Dst Hash (2)
`
`Src Hash (2)
`
`
`
`
`
`
`
`FIG_1 7B
`-ol (1)
`-et = L3 + (IHL/4)
`
`*
`
`"3.511333
`= x
`CHAOSNET = 0x0804
`ARP = exosoe
`VIP = OXOBAD’
`VLOOP = OxOBAE
`VECHO = OXOBAF
`NETBIOS—300M = gxgggg—
`X
`Deg-eemxggg;
`-
`= X
`DDEECéDLirsxsgsz‘
`= X
`-
`DEC-DIAG = 0x6005
`DEC-LAVC = OX6007
`RARP = 0X8035
`ATALK= 0x809?
`VLOOP = 0X80C4
`VECHO = OXSOCS
`SNA-TH = 0X80D5*
`ATALKARP = Ox80F3
`IPX = 0x813?"
`SNMP = 0X814C#
`IPv6 = OXBSDD*
`LOOPBACK = OXQOOO
`
`Apple = 0x080007
`* L3 Decoding
`
`1 752
`
`# L5 Decoding
`
`
`IGMP = 2
`GGP =3
`TCF' =6’
`EGP =8
`IGRP =9
`PUP =12
`CHAOS =16
`UDP =17”
`IDP =22#
`lSO-TP4 = 29
`DDP = 37#
`ISO—IP = 80
`VIP = 83#
`EIGRP = 88
`W =89
`
`;Lngzsgcgggding
`
`EX 1005 Page 19
`EX 1005 Page 19
`
`
`
`US. Patent
`
`Oct. 11,2005
`
`Sheet 18 0f 18
`
`US 6,954,789 132
`
`
`
`IFOZM...DAME
`
`PROTOCOL
`
`T
`
`wiii...in.Nm5.55:.%%
`
`uh.....:.i.
`
`InnisII.%m
`
`--D4ll“h”.
`
`1642
`
`F1 800
`
`nihili!
`ihhiiiii,
`ithiII!
`iniii-3
`.......,§
`-1hihm!
`
`W
`
`JOOOHOEQ
`
`BEE
`
`mDOOmtm
`
`DIE—mm0
`
`U_1L_
`MESwe,.,\m\mTwwwa
`
`FIG. 188
`
`EX 1005 Page 20
`EX 1005 Page 20
`
`
`
`
`
`
`
`US 6,954,789 B2
`
`1
`METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This invention is a continuation of US. patent application
`Ser. No. 09/608,237 for METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK to inventors
`Dietz, et al., filed Jun. 30, 2000, now US. Pat. No. 6,651,
`099,
`the contents of which are incorporated herein by
`reference.
`This invention 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 the assignee of the present
`invention:
`
`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, now US. Pat. No. 6,665,725, and incorporated
`herein by reference.
`US. patent application Ser. No. 09/608,126 for
`RE-USING INFORMATION FROM DATA TRANSAC-
`TIONS FOR MAINTAINING STATISTICS IN NET-
`WORK MONITORING, to inventors Dietz, et al., filed Jun.
`30, 2000, now US. Pat. No. 6,839,751, 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, now US. Pat. No. 6,771,646, 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, now US. Pat. No. 6,789,116, 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`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
`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,
`Wash.) 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 Netflow® (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
`
`EX 1005 Page 21
`EX 1005 Page 21
`
`
`
`US 6,954,789 B2
`
`3
`
`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.
`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 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-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`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
`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.
`
`EX 1005 Page 22
`EX 1005 Page 22
`
`
`
`US 6,954,789 B2
`
`5
`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.
`
`Providing a flexible processing 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
`the embodiments of the present
`In general,
`overcome the problems and disadvantages of the art.
`As described herein, one