(12) United States Patent
`Dietz et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,954,789 B2
`Oct. 11, 2005
`
`US006954789B2
`
`(54) METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`JP
`
`FOREIGN PATENT DOCUMENTS
`200344510 A
`2/2003
`
`IIIVCIIIOI‘SZ Russell S. Dietz, San JOSC, 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) App1_ NO; 10/684,776
`_
`(22) Flled:
`(65)
`
`Oct- 14’ 2003
`Prior Publication Data
`
`US 2004/0083299 A1 Apr- 29, 2004
`
`Related U-S- Application Data
`
`(63) Continuation of application No. 09/608,237, ?led on Jun.
`30 2000 now Pat NO 6 651 099
`(60) Provisional application No. 60/141,903, ?led on Jun. 30,
`1999
`
`(51) Int. CI.7 ............................................ .. G06F 15/173
`(52) US. Cl. ...................................... .. 709/224; 370/392
`(58) Field Of Search ............................... .. 709/200, 201,
`709/220, 223, 224, 231, 232, 236, 238—240,
`246; 370/389, 392
`
`(56)
`
`References Cited
`Us PATENT DOCUMENTS
`
`4/1976 Churchill, Jf- ------------ -- 711/128
`3,949,369 A
`7/1984 Chang ...................... .. 711/119
`4,458,310 A
`4,559,618 A 12/1985 Houseman et al. ......... .. 365/49
`
`Advanced Methods for Storage and Retrieval in Image;
`http://WWW.cs.tulane.edu/WW/Prototype/proposal.html;
`1998.
`
`_
`(Commued)
`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 ?oW-entry database containing ?ow-entries for previ
`ously encountered conversational ?oWs. The lookup uses the
`selected packet portions and determining if the packet is of
`an existing ?oW. If the packet is of an existing ?oW, the
`method Classl?es _the packet as belongmg to the found
`existing 110W, and 1f the packet is of a neW ?oW, the method
`stores a neW ?oW-entry for the neW How in the ?oW-entry
`database, including identifying information for future pack_
`ets to be identi?ed With the new ?OW_entI-y_ For the packet
`of an existing ?ow, the method updates the ?ow-entry 0f the
`existing ?oW. Such updating may include storing one or
`more statistical measures. Any stage of a 110W, state is
`maintained, and the method performs any state processing
`for an identi?ed state to further the process of identifying the
`How.' The method thus examines 'each and every packet
`passing through the connection pomt in real time until the
`application program associated With the conversational ?oW
`is determined
`
`(Continued)
`
`49 Claims, 18 Drawing Sheets
`
`{jun- - - - - ‘so; ““ - aamgg?": ________ _ _‘
`
`3,,
`
`'NFORMAT'O
`(Ell)
`
`ié’tv'é?é‘??: :
`312-]
`J :
`I """ ‘ ‘r -*
`
`‘FLOW" KEY l
`I
`
`|
`
`KNOWN
`“icons
`
`tingAscziiz
`
`REooFlnv
`
`“2w 1
`:
`I
`
`I
`N I
`
`)
`
`D‘TABASE
`oFFLows
`
`INHJHMA 1 lo
`(P H)
`
`I
`
`:
`:
`
`|
`
`|
`|
`PATIEHN. PARS
`1305} exTnA?gTlou
`:
`DATABASE
`
`- - - - 4
`
`‘- - - - 1
`
`#315
`
`PROTOCOL
`wilful-E | "J
`
`322'
`|
`
`-
`
`..
`.
`KNOWN
`
`I
`
`I
`l
`:
`I
`
`l
`:
`l
`|
`|
`
`cLAsslFlcATN
`FINALIZATION
`
`STATE
`
`msmucnou
`DATABASE
`
`526
`
`a
`?
`\ STATE
`r'nuu
`OPE HATION
`
`COK'P'LEH
`OPTIMIZER
`
`335
`
`PROTOCOL
`DESCIFTYO’
`LANGUAGE
`\_/
`
`DATAGRAM
`LAYER
`SELECTION
`
`I
`I
`335 |
`|
`I
`l
`I
`I
`l
`l
`
`Petitioners' EX1004 Page 1
`
`

`
`US 6,954,789 B2
`Page 2
`
`US. PATENT DOCUMENTS
`
`4/1988 Bristol ..................... .. 364/300
`4,736,320 A
`1/1990 Nakamura ............. .. 340/825.5
`4,891,639 A
`3/1990 Okamoto H a1~ -
`711/207
`4,910,668 A
`4,972,453 A 11/1990 Daniel, III et al. ......... .. 379/10
`5,101,402 A
`3/1992 Chiu et al. .................. .. 370/17
`5,247,517 A
`9/1993 Ross et a1- --
`370/85-5
`5,247,693 A
`9/1993 Bristol ..................... .. 395/800
`5,249,292 A
`9/1993 Chiappa ................... .. 395/650
`5315580 A
`5/1994 Phaal
`-- 370/13
`5,339,268 A
`8/1994 Machida .................... .. 365/49
`5,351,243 A
`9/1994 Kalkunte et al. ........... .. 370/92
`5,365,514 A 11/1994 Hershey er a1
`370/17
`5,375,070 A 12/1994 Hershey et al. ........... .. 364/550
`5,394,394 A
`2/1995 Crowther et al. ........... .. 370/60
`5,414,650 A
`5/1995 Hekhuis
`364/715-02
`5,414,704 A
`5/1995 Spinney --------------------- -- 370/60
`5,430,709 A
`7/1995 Galloway .................. .. 370/13
`5,432,776 A
`7/1995 Harper -------- --
`-- 370/17
`5,493,689 A
`2/1996 WadaWSky er a1- ------ -- 395/821
`5,500,855 A
`3/1996 Hershey et al. ............. .. 370/17
`5511213 A
`4/1996 Correa
`- 395/800
`5,511,215 A
`4/1996 Terasaka 9t a1~ ---------- -- 395/800
`5,530,834 A
`6/1996 Colloff et al. ............ .. 711/136
`5,530,958 A
`6/1996 Agalwal er a1- --
`711/3
`5535338 A
`7/1996 Krause 9t a1~ --------- -- 395/200-2
`5,568,471 A 10/1996 Hershey et al. ............. .. 370/17
`5,574,875 A 11/1996 Stans?eld 9t a1~ -------- -- 395/403
`5586266 A 12/1996 Hershey er a1- ------ -- 395/200-11
`5,606,668 A
`2/1997 Shwed ................ .. 395/200.11
`5,608,662 A
`3/1997 Large 94 a1-
`-- 364/724-01
`5,634,009 A
`5/1997 Iddon er a1
`395/200-11
`5,651,002 A
`7/1997 Van Seters et al.
`370/392
`5,680,585 A 10/1997 B91911 ----------------------- -- 703/26
`5,684,954 A 11/1997 Kaiserswerth 9t a1~
`395/200-2
`5,703,877 A 12/1997 Nuber et al. .............. .. 370/395
`5,720,032 A
`2/1998 PicaZo, Jr. et al.
`. 395/2002
`5,721,827 A
`2/1998 Logan et al.
`709/217
`5,732,213 A
`3/1998 Gesseletal. ........ .. 395/20011
`5,740,355 A
`4/1998 Watanabe et al. .... .. 395/183.21
`5,749,087 A
`5/1998 Hoover et al.
`..... .. 711/108
`5,761,424 A
`6/1998 Adams et al. .
`395/200.47
`5,761,429 A
`6/1998 Thompson
`709/224
`57647638 A
`6/1998 Ketchum
`370/401
`5,781,735 A
`7/1998 Southard ..... ..
`""" " 364/557
`2
`Z1998 Hershey et al'
`395/200.61
`/1998 McCreery et al.
`,
`,
`709023
`5,799,154 A
`8/1998 Kuriyan _______ __
`370/401
`5,802,054 A
`9/1998 Bellenger
`395/200_2
`5,805,808 A
`9/1998 Hasani et a1,
`5,812,529 A
`9/1998 CZarnik et al. ........... .. 370/245
`5,819,028 A 10/1998 Manghirmalani
`395/185.1
`et al. ........... ..
`5,825,774 A 10/1998 Ready et al. ............. .. 370/401
`
`5,835,726 A 11/1998 Shwed et al. ........ .. 395/20059
`5,838,919 A 11/1998 Schwaller et al.
`395/200.54
`5,841,895 A 11/1998 Huffman ___________________ u 382/155
`5,850,386 A 12/1998 Anderson et al_
`370/241
`5,850,388 A 12/1998 Anderson et al. ......... .. 370/252
`5,862,335 A
`1/1999 Welch’ Jr_ et a1_ ____ __ 395/20054
`5,878,420 A
`3/1999 de la Sane __
`707/10
`5,893,155 A
`4/1999 Cheriton ................... .. 711/144
`5903754 A
`5/1999 Pearson ____________________ __ 395/68O
`5,917,821 A
`6/1999 Gobuyan et aL
`370/392
`6,003,123 A 12/1999 Carter et al. .............. .. 711/207
`6,014,380 A
`1/2000 Hendel et aL ____________ u 370/392
`6,097,699 A
`53/2000 Chen et a1_ __
`370/231
`6,115,393 A
`9/2000 Engel et al. .............. .. 370/469
`6,118,760 A * 9/2000 Zaumen et aL """""""" " 370/229
`6,243,667 B1 * @2001 Ken et a1'
`“ 703/27
`6,269,330 B1
`7/2001 Cidon et al. ................ .. 704/43
`6,272,151 B1
`8/2001 Gupta etal. .............. .. 370/489
`6,279,113 B1
`53/2001 Vaidya _____ __
`_713/201
`6,282,570 B1
`8/2001 Leung et al. ............. .. 709/224
`6,330,226 B1
`12/2001 Chapman et al. ......... .. 370/232
`6,363,056 B1
`3/2002 Beigi et aL
`370/252
`6,381,306 B1
`4/2002 Lawson et al. ............. .. 379/32
`6,424,624 B1
`7/2002 Galand et al. ............ .. 370/231
`6,430,409 B1
`53/2002 Rossmann __
`_ 455/4221
`6,452,915 B1 * 9/2002 Jorgensen ................. .. 370/238
`6,453,345 B2
`9/2002 Trcka et al. .............. .. 709/224
`6,453,360 B1 * 9/2OO2 Muller et a1'
`7O9/25O
`6,466,985 B1 * 10/2002 Goyal et al. .............. .. 709/238
`6,483,804 B1 * 11/2002 Muller et al. ............. .. 370/230
`6,510,509 B1 * 1/2003 Chopra etaL
`__ 712/13
`6,516,337 B1
`2/2003 Tripp et al. ............... .. 709/202
`6,519,568 B1
`2/2003 Harvey etal. ............... .. 705/1
`6,570,875 B1 * 5/2003 Hegde
`_ 370/389
`6,625,657 B1
`9/2003 Bullard ..................... .. 709/237
`6,651,099 B1
`11/2003 DietZ et al. ............... .. 709/224
`6,791,947 B2 * 9/2OO4 Oskouy et a1' _________ “ 37O/238
`
`OTHER PUBLICATIONS
`_
`_
`_
`_
`MeasurementandAnalyslS Ofthe DlgltalDEcTpropagatlon
`Channel; IEEE; 1998
`R, Periakaruppam and E. Nemeth. “GTrace—A Graphical
`Traceroute Tool.” 1999 UseniX LISA. Available on
`WWW.caida.org, URL: http://WWW.caida.org/outreach/pa
`pars/1999/(}TI.aCe/(}TraCe'pdf~
`W. Stallings. “Packet Filtering in the SNMP Remote Moni
`”
`_
`_
`tor. Nov. 1994. Available on WWv7.dd].com, URL: http://
`WWW.dd].COIIl/dOCllIIleIlIS/S=1013/dd]9411h/9411h.htrr1.
`“Technical Note: the Narus System,” Downloaded Apr. 29,
`1999 from WWW.narus.com, Narus Corporation, RedWood
`City Ca1ifOrnia_
`
`* cited by examiner
`
`Petitioners' EX1004 Page 2
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 1 of 18
`
`US 6,954,789 B2
`
`100
`
`CLIENT 4
`
`107
`
`CLIENT s
`
`A
`106
`
`Q1053
`ANALYZER
`
`116
`_/
`SER
`VEF‘ 2
`“no
`
`121
`
`DATA COMMUNICATIONS
`NETWORK
`
`102
`
`125
`
`SERVER 2
`
`123
`
`105
`
`CLIENT 2
`
`FIG. 1
`
`CLIENT 1 —\
`1
`
`Petitioners' EX1004 Page 3
`
`

`
`2B987,45
`
`9:.MN_©_u_
`
`U.S. Patent
`
`0021,1a0
`
`2ae_h__S
`
`U
`
`E3
`
`58:Now
`
`
`
` E3muBmmm>mmmzo:<o:n_n_<3%MM.mpzmzoU
`
`flmmzcm.
`
`Petitioners‘ EX1004 Page 4
`
`Petitioners' EX1004 Page 4
`
`
`

`
`U.S. Patent
`U.S. Patent
`
`Oct. 11,2005
`0a. 11, 2005
`
`Sheet 3 of 18
`Sheet 3 of 18
`
`US 6,954,789 B2
`US 6,954,789 B2
`
`¢I'IIIIIIUII|In——QJon\V_I
`
`
`
`dmoommzaozxEx._2,o:._
`
`mw<mE<o90:.E2.55_o:<mE>z8
`
`llllllllllllll
`
`5<Exm.z<m~>._<z<_momSm
`
`E<$
`
`o:<s_mou_z_
`
`m>>O.ELO
`
`womoomm
`
`m»<n_n5
`
`__>>O.E_.
`
`omoomIZ>>OZv_
`
`z»<o_u__mm<._o
`
`ZO_._.<N_n_<Z_n_
`
`3”
`
`mmN>._<z<
`
`w._.<._.wa._O0O._.Omn_
`
`
`
`mm<m_ZEmC.<n_
`
`n_z<
`
`zo_»o<Exm
`
`m_m<m<»<o
`
`uzmmmoomm
`
`..zO_._.<mmn_O
`
`_>_<mo<+<o
`
`Ew><._
`
`mowmmooma
`
`2o:o3Emz_
`
`m_m<m<»<o
`
`mm._E_2oo
`
`DZ<
`
`mm_N_s__Eo
`
`Petitioners‘ EX1004 Page 5
`
`nSxOO.__m5o_z:o.__:m
`
`
`wz_E_»zmo_mw__.m_w.%m_m
`
`
`Petitioners' EX1004 Page 5
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 4 0f 18
`
`US 6,954,789 B2
`
`HIGH LEVEL
`PACKET
`DECODING
`EsCRIPTION
`
`401
`
`402
`
`405
`
`GENERATE
`PACKET
`STATE
`COMPILE
`EsCRIPTIONs_—' INsTRuCTIONs
`AND
`OPERATIONS
`
`£403
`
`S404
`
`GENERATE
`plxggilm
`EXTRACT
`OPERAT'ONS
`
`4067/ ATrERN, PARs
`E
`AND
`EXTRACTION
`DATABASE
`
`(408
`
`409 3
`
`Pkg/£1916
`V
`SUBSYSTEM
`MEMORY
`
`LOAD STATE
`NSTRUCTIO
`DATABASE
`MEMORY
`
`407
`
`STATE
`PROCESSOR
`INSTRUCTION
`DATABASE
`
`400
`
`:41O
`FIG. 4
`
`Petitioners' EX1004 Page 6
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 5 of 18
`
`US 6,954,789 B2
`
`501
`
`502
`
`LOAD PACKET
`503
`\/ COMPONENT T
`
`504
`
`512
`
`.
`
`BUILD
`NO \ PACKET
`KEY
`
`YES
`PEFTCR NODE AND
`~ P OCEss PROM
`PATTFHNS 1505
`
`MORE
`PATTERN
`
`506
`
`513
`
`NEXT
`PACKET 2
`COMPONENT 511
`A
`
`PROCESS To
`507 p COMPONENT
`
`51o
`\ N XT
`PATTERN
`NODE
`
`NO
`
`508
`
`\ 50o
`
`YES
`
`EXTRACT
`509$ ELEMENTS
`
`FIG. 5
`
`Petitioners' EX1004 Page 7
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 6 of 18
`
`US 6,954,789 B2
`
`601
`
`PACKET
`COMPONENT AND
`PATTERN NODE
`
`602
`
`603 "\
`LOAD PACKET
`d’ COMPONENT
`
`I
`
`610 v
`
`LOAD KEY
`BUFFER
`
`FETCH EXTRACTION
`AND PROCESS FRO
`PATTERNS
`
`605
`
`NO
`
`606
`
`ORE EXTRACTIO \
`ELEMENTS?
`
`NEXT
`NO, PACKET \q 609
`COMPONENT
`
`611
`
`507 l APPLY EXTRACTIO
`PROCESS TO
`COMPONENT
`
`MORE TO
`EXTRACT?
`
`608
`
`FIG. 6
`
`YEFf
`
`,\
`600
`
`Petitioners' EX1004 Page 8
`
`

`
`U.S. Patent
`
`Oct.11,2005
`
`Sheet 7 of 18
`
`US 6,954,789 B2
`
`701
`
`EY BUFFER AND
`PATTERN NODE '.
`
`702
`
`LOAD PATTERN
`703 V NODE ELEMENT ‘_
`
`704
`
`\
`
`I OUTPUT TO
`ANALYZER
`
`YES
`
`AS EY BUFFER
`ELEMENT FROM \5 705
`PATTERN NODE
`l
`
`F PACK KEY & HAS}
`706
`l
`
`NEXT PACKET
`f COMPONENT
`707
`
`FIG. 7
`
`709
`
`\
`
`700
`
`Petitioners' EX1004 Page 9
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 8 0f 18
`
`US 6,954,789 B2
`
`800 \
`
`UFKB ENTRY FOR
`PACKET
`
`802
`
`'
`COMPUTE CONVERSATION
`f 803
`RECORD BIN FROM HASH
`
`r
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`f- 804
`
`805
`
`ORE BUCKET
`IN THE BIN?
`
`NO
`
`SET UFKB FOR
`PACKET AS 'NEW'
`
`COMPARE CURRENT BIN
`f“ 807
`AND BUCKET RECORD KEY
`TO PACKET
`
`NEXT BUCKET
`
`KEY MATCH?
`
`808
`
`Q 809
`
`YES
`
`MARK RECORD BIN AND
`BUCKET ‘IN PROCESS’ IN
`CACHE AND TIMESTAMP
`
`I
`SET UFKB FOR PACKET
`AS ‘FOUND’
`
`8“ \,
`
`V
`812 X UPDATE STATISTICS FOR
`RECORD lN CACHE
`
`FIG. 8
`
`Petitioners' EX1004 Page 10
`
`

`
`U.S. Patent
`
`Oct.11,2005
`
`Sheet 9 of 18
`
`US 6,954,789 B2
`
`902
`
`OHTMAPP '
`
`EXTRACT PROGRAM
`903 A GET ‘PROGRAM’.
`'VERSION', 'PORT' AND
`‘PROTOCOL (TCP DR
`UDP)
`
`[
`
`l
`
`CREATE SERVER STAT E
`
`SAVE 'PROGHAM',
`904 -\ ‘VERSION’, 'POHT‘ AND
`‘PROTOCOL (TCP DR
`UDP)‘ WITH NETwDRK
`ADDREss IN sERvER
`STATE DATABASE. KEY
`ON SERVER ADDRESS
`AND TCP OR UDP PORT.
`
`K 909
`
`EXTRACT PORT
`GET ‘PROGRAM‘,
`'VERSION' AND
`‘PROTOCOL (TCP 0R
`UDP)‘
`
`908 < SAVE REQUEST
`
`SAVE ‘PROGRAM’,
`'VERSION' AND
`‘PROTOCOL (TCP 0R
`UDP)‘ WITH
`DEsTINATIoN
`NETWORK ADDREss.
`BOTH MAKE A KEY.
`
`907
`
`906 W
`EXTRACT
`PROGRAM
`
`GET 'PORT‘ AND
`‘PROTOCOL (TCP
`OR UDP)’.
`
`/
`900
`
`K- 905
`LOOKUP REQuEsT
`FIND PROGRAM
`AND ‘VERSION’
`WITH LOOKUP OF
`SOURCE NETWORK
`
`ADDRESS. V
`
`FIG. 9
`
`Petitioners' EX1004 Page 11
`
`

`
`U.S. Patent
`
`0¢1.11,200s
`
`Sheet 10 of 18
`
`US 6,954,789 B2
`
`1000 N
`
`PATTERN
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`‘031
`INFO OUT
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS CONTRL N
`
`10051
`
`10°
`
`PATTERN
`RECOGNITN
`ENGINE
`(PRE)
`
`EXTRACTION ENGINE
`(SLICER)
`
`1031
`
`1007
`
`1013
`
`1008\
`
`INPUT
`
`T012
`
`1021 I
`
`I/
`
`'
`‘
`PACKET
`
`‘I02
`1023
`
`PARSER INPUT BUFFER
`MEMORY
`
`PARSER
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`MEMORY
`
`101.
`
`INTERFACE
`CONTROL
`
`INTERFACE
`CONTROL
`
`ANALY E
`READY
`
`FIG. ‘I0
`
`1027
`
`Petitioners' EX1004 Page 12
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 11 0f 18
`
`6,954,789 B2
`US
`
`1100 N
`
`X1101
`
`X1103
`
`LOOKUP/
`UPDATE
`
`PARSER
`INTER
`FACE
`
`STATE
`PHOCESSR
`
`UNIFIED
`MEMORY
`CONTROL
`(UMC)
`
`MEMORY
`INTER
`FACE
`
`Petitioners' EX1004 Page 13
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 12 0f 18
`
`US 6,954,789 B2
`
`1201
`
`/
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`pm
`
`v
`ACCESS
`CONVERSATION
`RECORD BIN
`
`I
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`REQUEST NEXT
`BUCKET FROM
`CACHE
`
`SET UFKB FOR
`PACKET AS
`'DROP'
`
`lN/BUCKET EMPTY
`
`1205
`
`YES
`
`INSERT KEY AND HASH f‘207
`N BUCKET, MARK ‘USED
`WITH TIM ESTAMP
`+
`COMPARE CURRENT BIN
`P1209
`AND BUCKET RECORD
`KEY TO PACKET
`
`1'
`MARK RECORD BIN AND
`f1211
`BUCKET 'IN PROCESS‘
`AND 'NEW' IN CACHE
`
`I
`
`‘2121/ SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`FIG. 12
`
`Petitioners' EX1004 Page 14
`
`

`
`U.S. Patent
`
`Oct.11,2005
`
`Sheet 13 of 18
`
`US 6,954,789 B2
`
`130° Tu
`
`UFKB ENTRY FOR
`PACKET WITH STATUS
`'NEW' Ofl ‘FOUND’
`
`1302
`
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO {-1303
`I/ALUE FOUND IN UFKB ENTRY
`
`‘ FETCH INSTRUCTION FROM
`———> STATE PRocEssoR
`INSTRUCTION MEMORY
`
`1304
`
`f
`
`I
`
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION r1305
`
`SET STATE
`PROCESSOR
`INSTRUCTION
`POINTER TO
`VALUE FOUND IN
`CURRENT STATE
`
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`1 308
`1310
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET’?
`
`DONE PROCESSING
`TATES FOR THIS FLO
`
`1 309
`
`SET AND SAVE FLOW REMovAI.
`STATE PROCESSOR
`$1311
`INsTRucTIoN IN CURRENT
`FLOW REcoRD
`
`,dfms
`
`FIG. 13
`
`Petitioners' EX1004 Page 15
`
`

`
`U.S. Patent
`U.S. Patent
`
`Oct. 11,2005
`0a. 11, 2005
`
`Sheet 14 of 18
`Sheet 14 of 18
`
`US 6,954,789 B2
`US 6,954,789 B2
`
`mm<m<»<o
`
`
`
`w>>O....._u_O
`
`2262:m3.09
`
`omoomm
`
`2.9.;we
`
`ZO_._.<N_._<2_n_
`
`»<om_mm<._o
`
`mmN>._<z<
`
`sm:m>mmam
`
`02
`
`whim
`
`m_Z_IO<_>_
`
`mo.6mdw
`
`83
`
`m_._.<_.m
`
`m_m5<z<
`
`mbans
`
`zmmC<n_
`
`Z>>OZv_OZ<
`
`
`
`..>>On_u___mmmnposmkm
`
`omoomm
`
`zo..6<mbm_
`
`mzo_»<mmn_o
`
`s_mm>mm:m_Emmi
`
`Petitioners‘ EX1004 Page 16
`
`_____________
`
`Ex..>>O._u__.
`
`
`._UOIn_aOn__/__
`
`55$
`
`Mo:<s_momz_
`
`zmm,P<n_
`
`0.:am
`
`»o<E.xm_
`
`oz_>n:._.ZmD_
`muzooommnZ<mN>._<Z.
`
`Petitioners' EX1004 Page 16
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`.m_h__
`
`51
`
`SU
`
`2B987,4
`
`.%.
`/099GE
`
`oxmozfimz
`
`8920Hmo<n_mm»z_
`
`NE
`
`U.S. Patent
`
`m
`
`1,1
`
`
`
`Lmom.com.
`
`.rm_v.O<m
`
`O_._._w_DOO.
`
`mo_>mo
`
`van
`
`mm<m<»<o
`
`;wN>4<z<
`
`mmmm<m
`
`ma
`
`_%
`
`mow;
`
`
`
`MEo_2m_>_.ommmoom.m.50:
`
`sam
`
`motzoz
`
`—N—
`
`Petitioners‘ EX1004 Page 17
`
`Petitioners' EX1004 Page 17
`
`
`
`
`
`

`
`U.S. Patent
`
`Oct.11,2005
`
`Sheet 16 of 18
`
`US 6,954,789 B2
`
`0 - 3 Bytes
`
`160i
`\
`Dst MAC
`offset '0 - 11 “‘ DSt MAC
`Src MAC
`Src MAC
`
`Ar- 1600
`
`7/ 1604
`
`1606
`
`//
`
`1610
`
`Dst MAC (6)
`
`h
`
`w\ 2
`Src MAC (6)
`H H O 1s. m 2 D- S» L\
`Q m 4...
`s m m a a %
`
`6 1 M 1 6 6
`1 1
`
`2
`
`FIG. 16
`
`Petitioners' EX1004 Page 18
`
`

`
`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 17 of 18
`
`US 6,954,789 B2
`
`1702
`
`‘D1? = 8"8S88’
`CHAOSQE; : gigggg
`
`= X
`
`*
`
`VIP = 0xOBAD"
`VLOOP = OXOBAE
`VECHO = 0xOBAF
`NETB|OS—3COM = 8x:3ag8g—
`X
`°%%'é”SE‘8*288%
`-
`= x
`DEC-DRP = 0x6003*
`D259a1,eg;3:283§
`DEC-LAVC = OX6007
`RARP = 0X8035
`ATALK= 0x809B"
`VLOOP = 0X80C4
`VECHO = Ox8OC5
`SNA-TH = 0X80D5*
`ATALKARP = Ox8OF3
`IPX = Ox8137"
`SNMP = OX814C#
`IPv6 = Ox86DD*
`LOOPBACK = Ox9000
`
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`1 752
`
`lCMP =1
`W = 2
`:2.
`jg
`Cwggg 51%
`UDP E1;
`[so-+25 Egg
`DDP = 3'/#
`|SO—|P = 80
`VIP = 83#
`EIGRP = 88
`OSPF = 89
`
`
`
`’#‘#1_‘113?R’eef(|I))C<jai::]c§>]ding
`
`‘“— 1750
`
`
`
`
`‘I
`
`offset
`
`\
`12 to 13 Wllllllllfl.‘
`
`1
`
`"M
`
`1706
`
`F—— 1700
`
`1710
`
`1
`
`H ‘2’
`)
`Ls
`
`Fl
`
`1
`
`.
`
`1712
`
`
`
`
`_'|'/#i'W.'.W§'I.'fl'I's'7‘.'11WWWWWIIIM
`I-3‘°
`"
`[L3 1
`VII471'1’lI11:'1.f-1:7;‘11721:1='1~'»'.’€I.1:1
`
`(IHL I 4
`Src Address
`- 1]
`Dst Address
`IIIIInwiiimimril/Inlllllln
`
`
`
`
`
`Dst Address
`
`Dst Hash (2)
`
`Src Hash (2)
`
`
`
`
`
`ol (1)
`
`L4 Of1et= L3 + (IHU4)
`
`Petitioners‘ EX1004 Page 19
`
`Petitioners' EX1004 Page 19
`
`

`
`U.S. Patent
`
`Oct.11,2005
`
`Sheet 18 of 18
`
`US 6,954,789 B2
`
`PRGTOCOL
`
`FIG. 18A
`
`F1 850
`
`
`
`wOOO wtm
`
`OIEE m0
`
`JOOOFOME
`|Y
`
`FIG. 18B
`
`Petitioners' EX1004 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 U.S. 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 U.S. Pat. No. 6,651,
`099,
`the contents of which are incorporated herein by
`reference.
`This invention claims the benefit of U.S. Provisional
`
`Patent Application Ser. No.: 60/141,903 for METHOD AND
`APPARATUS FOR MONITORING TRAFFIC IN A NET-
`WORK to inventors Dietz, et al., filed Jun. 30, 1999, the
`contents of which are incorporated herein by reference.
`This application is related to the following U.S. patent
`applications, each filed concurrently with the present
`application, and each assigned to the assignee of the present
`invention:
`
`U.S. 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 U.S. Pat. No. 6,665,725, and incorporated
`herein by reference.
`U.S. 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 U.S. Pat. No. 6,839,751, and incorporated
`herein by reference.
`U.S. 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 U.S. Pat. No. 6,771,646, and incorporated herein
`by reference.
`U.S. 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 U.S. 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 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
`
`Petitioners‘ EX1004 Page 21
`
`Petitioners' EX1004 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 U.S. 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 U.S. Pat. No. 5,315,580, titled “NET-
`WORK MONITORING DEVICE AND SYSTEM.” Naka-
`mura teaches a network monitoring system in U.S. 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 U.S. 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 U.S. 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.
`
`Petitioners‘ EX1004 Page 22
`
`Petitioners' EX1004 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 clien