(12) United States Patent
`Dietz et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,651,099 B1
`Nov. 18, 2003
`
`US006651099B1
`
`(54) METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`5,375,070 A 12/1994 Hershey et al. ........... .. 364/550
`5,394,394 A
`2/1995 Crowther et al. ........... .. 370/60
`
`(75) Inventors: Russell S. Dietz, San Jose, CA (US);
`J 0861111 R- MaiXner, Aptos, CA (US);
`Andrew A. Koppenhaver, Littleton,
`CO (US); William H, Bares,
`Germantown, TN (Us); Haig A_
`Sarkissian, San Antonio, Tx (US);
`‘(Iglsnfs F‘ Torgerson’ Andover’ MN
`
`(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 589 days.
`
`(21) App1_ NO; 09/608,237
`_
`(22) F1169:
`
`Jun- 30’ 2000
`
`Related US. Application Data
`(60) Provisional application No. 60/141,903, ?led on Jun. 30,
`1999'
`(51) Int. Cl.7 .............................................. .. G06F 13/00
`(52) US. Cl. ...................................... .. 709/224; 370/389
`(58) Field of Search ............................... .. 709/200, 201,
`709/220, 223, 224, 231, 232, 236, 238,
`239, 240, 246; 370/389, 392, 39532
`
`(56)
`
`References Cited
`
`Us‘ PATENT DOCUMENTS
`4,736,320 A
`4/1988 Bristol ..................... .. 364/300
`4,891,639 A
`1/1990 Nakarnura _
`_ 340/8255
`5,101,402 A
`3/1992 Chui et al. .
`370/17
`5,247,517 A
`9/1993 ROSS et al- -
`-- 370/85-5
`52477693 A
`9/1993 Brlstol ~~~~ ~~
`395/800
`5249292 A
`9/1993 Chlappa
`395/650
`
`(Llst Connnued on next page‘)
`OTHER PUBLICATIONS
`
`“Technical Note: the Narus System,” Downloaded Apr. 29,
`1999 from WWW.narus.com, Narus Corporation, Redwood
`City California
`Primary Examiner—Moustafa M. Meky
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`(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 classi?es the packet as belonging to the found
`existing 110W, and if 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-entry. For the packet
`of an existing ?oW, the method updates the ?oW-entry of the
`existing ?oW. Such updating may include storing one or
`more Statistical measures~ Any Stage of a ?OW, State is
`maintained, and the method performs any state processing
`for an identi?ed state to further the process of identifying the
`110W. The method thus examines each and every packet
`passing through the connection point in real time until the
`application program associated With the conversational ?oW
`
`5,315,580 A
`
`5/1994 Phaal . . . . . . . .
`
`. . . .. 370/13
`
`is determined‘
`
`5,339,268 A
`
`8/1994 Machida . . . . . . . . . . .
`
`. . . .. 365/49
`
`370/92
`9/1994 Kalkunte et al. .
`5,351,243 A
`5,365,514 A 11/1994 Hershey et al. ............. .. 370/17
`
`10 Claims, 18 Drawing Sheets
`
`1000“
`
`PATTERN
`RECOGNITION 3
`DATABASE
`MEMORY
`
`,
`
`EXTHACTTON
`OPERATIONS
`DATABASE
`M EMORY
`
`PACKET KEY
`BUFFER AND PAVLOA
`MEMORV
`
`TNTEHFACE
`CONTROL
`
`ANALVZER DATA REA v
`CE
`INTERFA
`ONTROL
`
`‘1023
`
`1027 U "
`
`Petitioners' EX1003 Page 1
`
`

`
`US 6,651,099 B1
`Page 2
`
`US. PATENT DOCUMENTS
`_
`5/1995 Hekhuis .............. .. 364/71502
`
`5,414,650 A
`
`. . . . . . . .. 370/60
`5/1995 Spinney . . . . .
`5,414,704 A
`370/13
`7/1995 Galloway
`5,430,709 A
`370/17
`7/1995 Harper ---------- --
`5,432,776 A
`395/821
`2/1996 WadaWSky er a1
`5,493,689 A
`370/17
`3/1996 Hershey er a1- --
`5,500,855 A
`395/800
`4/1996 Correa ------- --
`5,511,213 A
`-- 395/800
`4/1996 Terasaka 9t a1~ -
`5511215 A
`5,568,471 A 10/1996 Hershey er a1- -
`370/17
`395/403
`5,574,875 A 11/1996 Stans?eld 9t a1~
`5,586,266 A 12/1996 Hershey er a1- -
`395/200-11
`395/200.11
`5,606,668 A
`2/1997 ShWed ....... ..
`5,608,662 A
`3/1997 Large 91 a1- -
`364/72“-01
`395/200.11
`5,634,009 A
`5/1997 Iddon et a1. ..
`5,651,002 A
`7/1997 Van Seters et a1. ....... .. 370/392
`5,684,954 A 11/1997 Kaiserswerth 618.1.
`395/2002
`5,703,877 A 12/1997 Nuber et a1. ........... .. 370/395
`5,732,213 A
`3/1998 Gessel et a1. .
`395/200.11
`5,740,355 A
`4/1998 Watanabe et a1.
`395/183.21
`5,761,424 A
`6/1998 Adams et a1~
`395/200~47
`5,764,638 A
`6/1998 Ketchum
`------ -- 370/401
`5781735 A
`7/1998 Southard ~~~~ -
`395/200-54
`5,784,298 A
`7/1998 Hershey et a1. ..
`...... .. 364/557
`5,787,253 A
`7/1998 McCreery et a1.
`395/200.61
`
`5,802,054 A
`5,805,808 A
`5,812,529 A
`
`9/1998 Bellenger ................. .. 370/351
`9/1998 Hansani et a1. ........ .. 395/2002
`9/1998 CZamik et aL ___________ u 370/245
`
`5,819,028 A 1O/1998 Manghirmalani
`et a1. ..................... .. 395/185.1
`5,825,774 A 10/1998 Ready et a1. ..
`..... .. 370/401
`5,835,726 A 11/1998 Shwed et a1. ........ .. 395/200.59
`5,838,919 A 11/1998 Schwaller et a1.
`395/200.54
`5,841,895 A 11/1998 Huffman ............ ..
`382/155
`5,850,386 A 12/1998 Anderson et a1. .
`370/241
`5,850,388 A 12/1998 Anderson et a1.
`370/252
`5,862,335 A
`1/1999 Welch, Jr. et a1. .... .. 395/200.54
`5,878,420 A
`3/1999 de la Salle ........... .. 707/10
`5,893,155 A
`4/1999 Cheriton
`_711/144
`5,903,754 A
`5/1999 Pearson .......... ..
`.395/680
`5,917,821 A
`6/1999 Gobuyan et a1_ _
`370692
`6,014,380 A
`1/2000 Hendel et aL
`370/392
`6,118,760 A * 9/2000 Zaumen et aL
`370/229
`6,243,667 B1 4 60001 Ken et aL
`703/27
`6,452,915 B1 4 90002 lorgensen ____ __
`_37O/338
`6,453,360 B1 * 9/2OO2 Muller et a1' __
`7O9/25O
`6,466,985 B1 * 10/2002 Goyal et a1.
`709/238
`6,483,804 B1 * 11/2002 Muller et a1. ..
`370/230
`6,570,875 B1 * 5/2003 Hegde ...................... .. 370/389
`
`* cited by examiner
`
`Petitioners' EX1003 Page 2
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 1 0f 18
`
`US 6,651,099 B1
`
`100
`
`CL|ENT4
`
`108
`J
`ANALYZER
`
`CLIENT3
`
`A
`
`116
`_/
`;
`SERVER 2
`\110
`
`121
`
`DATA COMMUNICATIONS
`NETWORK
`
`102
`
`125
`
`1
`
`CLIENT1 \
`
`SERVER 2
`W
`112
`
`105
`CLIENT2 J
`
`FIG. 1
`
`Petitioners' EX1003 Page 3
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 2 0f 18
`
`US 6,651,099 B1
`
`4
`
`?sEgMw \ J
`
`
`
`m: >59 85% Na Fm FO
`
`
`
`
`
`........ .. Emu Emu may NRV Emu ORV
`
`
`
`B269 52% mg PO
`
`W v V 0 W 0 V v n
`
`mlmJ mmmv qmmu 2% mmmv 5% 8% _
`
`> 9w 1 4| ..... a 5 Fw Z6! M . ./ V V t M v V j \
`m FN m B 8 A8: NON
`
`@N Em QN NE SN (E
`
`5 mm 4| ...... .1 ma Fo Fm $6! _
`H *
`
`3m 8m
`
`N
`
`Na Q7 0% 1 0. 3 r0, 6
`
`
`
`mmmvmmmxmmvommv @NNJNNVRNV 8% 8% wmmv 8N ....... ..
`
`mmmvmmwrmmvommdENJEVCNQ 9% 2% 3%
`
`Petitioners' EX1003 Page 4
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 3 0f 18
`
`US 6,651,099 B1
`
`aw
`
`mom
`
`own
`
`Petitioners' EX1003 Page 5
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 4 0f 18
`
`US 6,651,099 B1
`
`401
`
`402
`
`HIGH LEVEL
`PACKET
`DECODING
`
`405
`S404
`OENERATE
`PACKET
`GENERATE
`PIFF’I‘SE‘IEILD ~_ COMP'LE ____, STATE
`EXTRACT
`DESCRIPTIONS
`INSTFAII?JTIONS
`OPERATIONS
`OPERATIONS
`
`Q 403
`
`406 7/ ATTERN, PARS E
`AND
`EXTRACTION
`DATABASE
`
`_/ (
`
`408
`
`407
`
`STATE
`PROCESSOR
`INSTRUCTION
`DATABASE
`
`409
`
`3
`
`LOAD
`PARSING
`I SUBSYSTEM
`MEMORY
`
`LOAD STATE
`NSTRUCTION4
`DATABASE ‘
`MEMORY
`
`400
`
`agk 410
`
`FIG. 4
`
`Petitioners' EX1003 Page 6
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 5 0f 18
`
`US 6,651,099 B1
`
`501
`
`INPUT PACKET
`
`502
`
`LOAD PACKET
`503
`1/ COMPONENT ‘
`
`504
`
`ORE IN PACKE '
`
`512
`
`BUILD
`\ PACKET
`KEY
`
`YES
`
`V
`
`R
`FR M
`PATTERNS 1505
`
`MORE
`PATTERN
`NODES?
`
`506
`
`APPLY NODE AN
`p PROCESS TO
`507
`COMPONENT
`
`513
`
`NEXT
`PACKET Q
`COMPONENT 511
`‘L
`
`500
`
`EXTRACT
`509 -S\ ELEMENTS
`
`FIG. 5
`
`510\
`
`Petitioners' EX1003 Page 7
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 6 0f 18
`
`US 6,651,099 B1
`
`601
`
`PACKET
`
`PATTERN NODE
`
`U 602
`/COMPONENT AND
`i
`
`LOAD PACKET
`COMPONENT
`
`6103
`
`LOAD KEY
`BUFFER
`
`FETCH EXTRACTION
`AND PROCESS FROM
`PATTERNS
`
`606
`
`ORE EXTRACTIO ‘
`ELEMENTS?
`
`NEXT
`PACKET
`COMPONENT
`A
`
`607 1 APPLY EXTRACTION
`
`PROCESS TO
`COMPONENT
`
`MORE TO
`EXTRACT?
`
`608
`
`FIG. 6
`
`YES
`
`600
`
`Petitioners' EX1003 Page 8
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 7 0f 18
`
`US 6,651,099 B1
`
`701
`
`EY BUFFER AND
`PATTERN NODE
`
`702
`
`LOAD PATTERN
`703 ‘V NODE ELEMENT ‘—
`
`704
`
`OUTPUT TO
`\—’ ANALYZER
`
`YES
`V
`HASH KEY BUFFER
`ELEMENT FROM \5 705
`PATTERN NODE
`
`F PACK KEY & HASH
`706
`
`Y
`NEXT PACKET
`COMPONENT
`
`F
`
`707
`
`FIG. 7
`
`709
`
`700
`
`Petitioners' EX1003 Page 9
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 8 0f 18
`
`US 6,651,099 B1
`
`UFKB ENTRY FOR
`PACKET
`
`802
`
`800 \
`
`v
`803
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH /_
`
`V
`REQUEST REOORD BIN/
`BUCKET FROM CACHE /— 804
`
`5 806
`
`805
`
`ORE BUCKET
`IN THE BIN?
`
`SET UFKB FOR
`PACKET AS 'NEW'
`
`COMPARE CURRENT BIN /— 807
`AND BUCKET RECORD KEY
`TO PACKET
`
`NEXT BUCKET <—N
`
`KEY MATCH?
`
`Q 809
`
`YES
`
`MARK RECORD BIN AND
`BUCKET ‘IN PROCESS‘ IN
`CACHE AND TIMESTAMP
`
`808
`
`810
`
`811 _\J
`
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`812 X] UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`FIG. 8
`
`Petitioners' EX1003 Page 10
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 9 0f 18
`
`US 6,651,099 B1
`
`901
`
`ORTMAPP '
`
`EXTRACT PROGRAM
`903 X GET 'PROGRAM',
`‘VERSION’, 'PORT' AND
`‘PROTOCOL (TCP OR
`UDP)
`
`I
`
`I
`
`CREATE SERVER STAT
`
`BIND LOOKU
`
`EXTRACT PORT
`
`GET 'PROGRAM',
`'VERSION' AND
`‘PROTOCOL (TCP OR
`
`908
`i SAVE REQUEST
`SAVE 'PROGRAM',
`'VERSION' AND
`‘PROTOCOL (TCP OR
`UDP)‘ WITH
`DESTINATION
`NETWORK ADDRESS.
`BOTH MAKE A KEY.
`
`907
`
`906 w
`EXTRACT
`PROGRAM
`
`GET 'PORT‘ AND
`‘PROTOCOL (TCP
`OR UDP)’.
`
`904 x
`
`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.
`
`K’ 905
`LOOKUP REQUEST
`
`90
`
`FIND 'PROGRAM'
`AND 'VERSION'
`WITH LOOKUP OF
`SOURCE NETWORK
`ADDRESS.
`
`V
`FIG. 9
`
`Petitioners' EX1003 Page 11
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 10 0f 18
`
`US 6,651,099 B1
`
`1000 N
`
`PATTERN
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`1005»\
`
`1031
`
`INFO OUT
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS CONTRL IN
`
`PATTERN
`RECOGNITN
`ENGINE
`(PRE)
`
`100
`
`100
`
`EXTRACTION ENGINE
`(SLICEFI)
`
`1031)
`
`1007
`
`1013
`
`PA KET
`INPUT
`
`PARSER INPUT BUFFER
`MEMORY
`
`1012
`
`PARSER
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`MEMORY
`
`10213 PACKET
`
`START INPUT BUFFER 1011
`INTERFACE
`CONTROL
`
`‘
`
`Y
`
`PACKET
`
`INTERFACE
`CONTROL
`
`ANALYZER
`READY
`
`102
`1023
`
`. 1 O
`
`1027
`
`Petitioners' EX1003 Page 12
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 11 0f 18
`
`US 6,651,099 B1
`
`1100 H
`
`$1101
`
`1103
`
`LOOKUP/
`UPDATE
`
`1115
`
`1122:
`
`HOST
`BUS
`INTER
`FACE
`(HIB)
`
`PARSER
`INTER- M
`FACE
`
`1119 1123i
`
`MEA'AFCSEFR ME???
`“ CONTROL “ FACE
`(UMC)
`
`_
`
`|
`
`Petitioners' EX1003 Page 13
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 12 0f 18
`
`US 6,651,099 B1
`
`1201
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`1202
`
`ACCESS
`CONvERsATION
`RECORD BIN
`1
`
`/—1203
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE f1204
`
`IN/BUCKET EMPTY
`
`1205
`
`YES
`
`INsERT KEY AND HASH f1207
`IN BUCKET, MARK ‘USED
`WITH TIMESTAMP
`+
`COMPARE CURRENT B|N’_1209
`AND BUCKET RECORD
`KEY TO PACKET
`
`1206;
`
`REQUEST NEXT
`BUCKET FROM
`CACHE
`
`i
`
`1210
`SET UFKB FOR
`X PACKET AS
`'DROP'
`
`MARK RECORD BIN AND
`BUCKET ‘IN PROCESS‘ f 12“
`AND 'NEW' IN CACHE
`
`1
`
`‘2121 SET INITIAL sTATIsTICs
`FOR RECORD IN CACHE
`
`1213
`
`}
`
`FIG. 12
`
`Petitioners' EX1003 Page 14
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 13 0f 18
`
`US 6,651,099 B1
`
`1300 N UFKB ENTRY FOR
`PACKET WITH STATUS
`'NEW' OFi'FOUND'
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO [-1303
`VALUE FOUND IN UFKB ENTRY
`
`1302
`
`FETCH INSTRUCTION FROM
`——-> STATE PROCESSOR
`INSTRUCTION MEMORY
`
`1304
`/_
`
`I
`
`PERFORM OPERATION BASED
`ON THE STATE |NSTRuOT|ON f 1305
`
`SET STATE
`PROCESSOR
`INSTRUCTION
`POINTER TO
`VALUE FOUND IN
`CURRENT STATE
`
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`1308
`1310
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET?
`
`1307
`
`DONE PROCESSING
`TATES FOR THIS FLO
`
`1309
`
`SET AND SAvE FLOW REMOVAL
`STATE PROCESSOR
`$1311
`INSTRUCTION IN OuRRENT
`FLOW REOORD
`
`FIG. 13
`
`Petitioners' EX1003 Page 15
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 14 0f 18
`
`US 6,651,099 B1
`
`mmwf
`
`wmilw W02
`
`mm;
`
`mmvw
`
`0.1.
`
`Petitioners' EX1003 Page 16
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 15 of 18
`
`US 6,651,099 B1
`
`pmoz
`
`>mo§m2
`
`mo<mmm+z_
`
`om<o
`
`EOEZOE
`
`an
`
`+mxo<m
`
`Petitioners‘ EX1003 Page 17
`
`Petitioners' EX1003 Page 17
`
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 16 0f 18
`
`US 6,651,099 B1
`
`1602
`
`0 - 3 Bytes
`
`“
`
`Dst MAC
`
`F 1600
`
`offset 0 - 11 \ Dst MAC Src MAC ‘j1604
`Src MAC
`1
`
`\
`
`/
`
`1608 \\
`_Dst Hash (2
`161i
`1614 _Src Hash (2]
`
`7
`Dst MAC (6)
`
`Src MAC (6)
`
`\1.2 Offset = 12
`
`\ 1606
`//
`1610
`//
`
`FIG. 16
`
`Petitioners' EX1003 Page 18
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 17 of 18
`
`US 6,651,099 B1
`
`1 702
`
`12 to 13hn
`
`offset
`
`Type
`
`1704
`
`IDP = 0x0600*
`IP = 0x0800*
`CHAOSNET = 0 0804
`
`W, = Ogom
`
`‘
`
`1706
`
`VK—— 1700
`
`1710
`
`H 13"?“
`)
`_
`'-3 Ofiet ' 14
`
`Fl G 1 7A
`.
`
`VIP = 0xOBAD*
`VLOOP = 0x0BAE
`VECHO = OXOBAF
`NETBIOS-3COM = X
`°E%1§”8B‘8*888%
`_
`: X
`DEC-DRP = 0x6003*
`DEC-LAT = 0x6004
`DEC-DIAG = 0x6005
`DEC-LAVC = Ox6007
`RARP = Ox8035
`ATALK = 0x809B*
`VLOOP = 0x80C4
`VECHO = 0x80C5
`J SNA-TH = 0x8OD5*
`ATALKARP = 0x80F3
`1712
`lPX= 0x8137*
`SNMP = 0x814C#
`IPv6 = 0x86DD*
`LOOPBACK = 0x9000
`
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`1752
`
`
`
`
`
`
`
`
`
`
`ol (1)
`
`G _ 1 7 B
`
`f1'lA1E'fl'.’AF5'.I.1'I1i'£flI1W:’L!4'¢v'!4WIIIfl
`7 V
`1
`
`= 1
`L3 t0
`-
`:3
`:’o”l’,"~:
`1GMP:2
`13+
`VI1"1I1’.'I1W:1:'.-‘L17I1.’1".‘=2-Z£é~'1'.111
`
`GGP
`3
`(IHL I 4
`Src Address
`-1] — TCP = 6 *
`
`
`.33: :3
`7IIIIII7#I’b’.C'i7Ib’:“7fiifl3WJIIIIIIIIIII1
`CHZLDJE 5
`/7‘: :—\ “"5”
`
`
`
`
`
`
`UDP = 17*
`
`Z
`_
`'S°vl5 =33#
`Elgsgf-3 3
`°
`‘
`* L4 Decoding
`# L3 Re-Decoding
`
`et = L3 + (IHL/4)
`
`Petitioners‘ EX1003 Page 19
`
`Petitioners' EX1003 Page 19
`
`

`
`U.S. Patent
`
`Nov. 18,2003
`
`Sheet 18 0f 18
`
`US 6,651,099 B1
`
`PROTOCOL
`
`FIG. 18A
`
`r1850
`
`MQOOWt?
`
`DIET-m0
`
`6005mm
`||||v
`
`IL .
`
`M 5% WQ Kb U m U
`
`FIG. 18B
`
`Petitioners' EX1003 Page 20
`
`

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

`
`US 6,651,099 B1
`
`3
`In order to eliminate the possibility of disjointed conversa-
`tional exchanges, it is desirable for a network packet monitor
`to be able to “virtually concatenate”—that is, to link—the
`first exchange with the second. If the clients were the same,
`the two packet exchanges would then be correctly identified
`as being part of the same conversational flow.
`Other protocols that may lead to disjointed flows, include
`RPC (Remote Procedure Call); DCOM (Distributed Com-
`ponent Object Model),
`formerly called Network OLE
`(Microsoft Corporation, Redmond, Wash.); and CORBA
`(Common Object Request Broker Architecture). RPC is a
`programming interface from Sun Microsystems (Palo Alto,
`Calif.) that allows one program to use the services of another
`program in a lo remote machine. DCOM, Microsoft’s coun-
`terpart to CORBA, defines the remote procedure call that
`allows those objects—objects are self-contained software
`modules—to be run remotely over the network. And
`CORBA, a standard from the Object Management Group
`(OMG) for communicating between distributed objects,
`provides a way to execute programs (objects) written in
`different programming languages running on different plat-
`forms regardless of where they reside in a network.
`What
`is needed,
`therefore,
`is a network monitor that
`makes it possible to continuously analyze all user sessions
`on a heavily trafficked network. Such a monitor should
`enable non-intrusive,
`remote detection, characterization,
`analysis, and capture of all information passing through any
`point on the network (i.e., of all packets and packet streams
`passing through any location in the network). Not only
`should all the packets be detected and analyzed, but for each
`of these packets the network monitor should determine the
`protocol (e.g., http, ftp, H.323, VPN, etc.), the application/
`use within the protocol (e.g., voice, video, data, real-time
`data, etc.), and an end user’s pattern of use within each
`application or the application context (e.g., options selected,
`service delivered, duration, time of day, data requested, etc.).
`Also, the network monitor should not be reliant upon server
`resident information such as log files. Rather, it should allow
`a user such as a network administrator or an Internet service
`
`provider (ISP) the means to measure and analyze network
`activity objectively; to customize the type of data that is
`collected and analyzed; to undertake real time analysis; and
`to receive timely notification of network problems.
`Considering the previous SAP example again, because
`one features of the invention is to correctly identify the
`second exchange as being associated with a print service on
`that server, such exchange would even be recognized if the
`clients were not the same. What distinguishes this invention
`from prior art network monitors is that it has the ability to
`recognize disjointed flows as belonging to the same conver-
`sational flow.
`
`The data value in monitoring network communications
`has been recognized by many inventors. Chiu, et al.,
`describe a method for collecting information at the session
`level in a computer network in 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-
`ets to extract information to identify session of a packet. For
`example, if a DECnet packet appears, the 402 patent looks
`at six specific fields (at 6 locations) in the packet in order to
`identify the session of the packet. If, on the other hand, an
`IP packet appears, a different set of six different locations is
`specified for an IP packet. With the proliferation of
`protocols, clearly the specifying of all the possible places to
`look to determine the session becomes more and more
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`difficult. Likewise, adding a new protocol or application is
`difficult. In the present invention, the locations examined
`and the information extracted from any packet are adap-
`tively determined from information in the packet for the
`particular type of packet. There is no fixed definition of what
`to look for and where to look in order to form an identifying
`signature. A monitor implementation of the present
`invention, for example, adapts to handle differently IEEE
`802.3 packet from the older Ethernet Type 2 (or Version 2)
`DIX (Digital-Intel-Xerox) packet.
`The 402 patent system is able to recognize up to the
`session layer. In the present invention, the number of levels
`examined varies for any particular protocol. Furthermore,
`the present invention is capable of examining up to whatever
`level is sufficient to uniquely identify to a required level,
`even all the way to the application level (in the OSI model).
`Other prior art systems also are known. Phael describes a
`network activity monitor that processes only randomly
`selected packets in 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.
`
`Other aspects of embodiments of the invention are:
`Properly analyzing each of the packets exchanged
`between a client and a server and maintaining infor-
`mation relevant to the current state of each of these
`
`conversational flows. p1 Providing a flexible process-
`
`Petitioners‘ EX1003 Page 22
`
`Petitioners' EX1003 Page 22
`
`

`
`US 6,651,099 B1
`
`5
`ing system that can be tailored or adapted as new
`applications enter the client/server market.
`Maintaining statistics relevant to the conversational flows
`in a client/sever network as classified by an individual
`application.
`Reporting a specific identifier, which may be used by
`other network-oriented devices to identify the series of
`packets with a specific application for a specific client/
`server network conversational flow.
`invention
`In general,
`the embodiments of the present
`overcome the problems and disadvantages of the art.
`As described herein, one embodiment analyzes each of
`the packets passing through any point in the network in
`either direction, in order to derive the actual application used
`to communicate between a client and a server. Note that
`there could be several simultaneous and overlapping appli-
`cations executing over the network that are independent and
`asynchronous.
`A monitor embodiment of the invention successfully
`classifies each of the individual packets as they are seen on
`the network. The contents of the packets are parsed and
`selected parts are assembled into a signature (also called a
`key) that may then be used identify further packets of the
`same conversational flow, for example to further analyze the
`flow and ultimately to recognize the application program.
`Thus the key is a function of the selected parts, and in the
`preferred embodiment, the function is a concatenation of the
`selected parts. The preferred embodiment forms and remem-
`bers the state of any conversational flow, which is deter-
`mined by the relationship between individual packets and
`the entire conversational flow over the network. By remem-
`bering the state of a flow in this way,
`the embodiment
`determines the context of the conversational flow, including
`the application program it relates to and parameters such as
`the time, length of the conversational flow, data rate, etc.
`The monitor is flexible to adapt to future applications
`developed for client/server networks. New protocols and
`protocol combinations may be incorporated by compiling
`files written in a high-level protocol description language.
`The monitor embodiment of the present
`invention is
`preferably implemented in application-specific integrated
`circuits (ASIC) or field programmable gate arrays (FPGA).
`In one embodiment, the monitor comprises a parser sub-
`system that forms a signature from a packet. The monitor
`further comprises an analyzer subsystem that receives the
`signature from the parser subsystem.
`A packet acquisition device such as a media access
`controller (MAC) or a segmentation and reassemble module
`is used to provide packets to the parser subsystem of the
`monitor.
`
`the parsing subsystem
`In a hardware implementation,
`comprises two sub-parts, the pattern analysis and recogni-
`tion engine (PRE), and an extraction engine (slicer). The
`PRE interprets each packet, and in particular,
`interprets
`individual fields in each packet according to a pattern
`database.
`
`The different protocols that can exist in different layers
`may be thought of as nodes of one or more trees of linked
`nodes. The packet type is the root of a tree. Each protocol is
`either a parent node or a terminal node. A parent node links
`a protocol to other protocols (child protocols) that can be at
`higher layer levels. For example, An Ethernet packet (the
`root node) may be an Ethertype packet—also called an
`Ethernet Type/Version 2 and a DIX (DIGITAL-Intel-Xerox
`packet)—or an IEEE 802.3 packet. Continuing with the
`IEEE 802.3-type packet, one of the children nodes may be
`the IP protocol, and one of the children of the IP protocol
`may be the TCP protocol.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`The pattern database includes a description of the differ-
`ent headers of packets and their contents, and how these
`relate to the different nodes in a tree. The PRE traverses the
`tree as far as it can. If a node does not include a link to a
`
`deeper level, pattern matching is declared complete. Note
`that protocols can be