(12) United States Patent (cid:9)
`Dietz et al. (cid:9)
`
`1111111111111110111111111111I19111,111111111111111111111110111111
`
`(to) Patent No.: (cid:9)
`(45) Date of Patent: (cid:9)
`
`US 6,954,789 B2
`Oct. 11, 2005
`
`(54) METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`FOREIGN PATENT DOCUMENTS
`
`JP (cid:9)
`
`2003-44510 A (cid:9)
`
`2/2003
`
`(75) 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: (cid:9)
`* )
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`
`Appl. No.: 10/684,776
`
`(22)
`
`Filed: (cid:9)
`
`Oct. 14, 2003
`
`(65)
`
`Prior Publication Data
`
`US 2004/0083299 Al Apr. 29, 2004
`
`(63)
`
`(60)
`
`(51)
`(52)
`(58)
`
`(56)
`
`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.
` GO6F 15/173
`Int. C1.7 (cid:9)
` 709/224; 370/392
`U.S. Cl. (cid:9)
` 709/200, 201,
`Field of Search (cid:9)
`709/220, 223, 224, 231, 232, 236, 238-240,
`246; 370/389, 392
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3,949,369 A (cid:9)
`4,458,310 A (cid:9)
`4,559,618 A (cid:9)
`
`4/1976 Churchill, Jr. (cid:9)
`7/1984 Chang (cid:9)
`12/1985 Houseman et al. (cid:9)
`
` 711/128
` 711/119
` 365/49
`
`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) (cid:9)
`
`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.
`
`(Continued)
`
`49 Claims, 18 Drawing Sheets
`
`302—,
`
`PACKET
`
`04
`
`ANALYZE ANI
`RECOGNIZE
`PATTERN
`INFORMATIO
`(PAR)
`
`308 -7
`
`I DEEXNTT7F19I TN G (cid:9)
`INFORMATIO
`(Ell)
`
`PARSER 301
`
`BUILD UNIQUE
`ONVERSATIOI
`'FLOW KEY
`
`312-/ (cid:9)
`
` -I
`
`ri 314,
`LOOKUP
`
`KFNROZ
`I RECORDS
`(DS 324
`I
`VIA CACHE
`
`6-)
`
`Der
`
`PATTERN, PARS
`AND
`EXTRACTION
`DATABASE
`
`PROTOCOL
`& STATE
`IDENTIFICATION
`
`310
`
`COMPILER
`AND
`1 OPTIMIZER
`
`
`
`_OM
`
`STATE
`PROCESSOR
`INSTRUCTION
`DATABASE
`
`PROTOCOL --A- DATAGRAM
`DESCIPTION (cid:9)
`LAYER
`LANGUAGE (cid:9)
`SELECTION;
`
`324
`
`DATABASE
`OF FLOWS
`
`- (cid:9)
`UPDATE
`
` 3221
`
`KNOWN ...-
`RECORD
`
`NO—t 34
`
`ANALYZER
`
`303
`
`NOAC Ex. 1005 Page 1
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`US 6,954,789 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`364/300
`
`4/1988 (cid:9) Bristol
`340/825.5
`
`1/1990 Nakamura (cid:9)
`711/207
`
`3/1990 (cid:9) Okamoto et al. (cid:9)
`379/10
`
`11/1990 (cid:9) Daniel, III et al. (cid:9)
`370/17
`
`3/1992 (cid:9) Chiu et al. (cid:9)
`370/85.5
`
`9/1993 (cid:9) Ross et al. (cid:9)
`395/800
`
`9/1993 (cid:9) Bristol
`395/650
`
`9/1993 Chiappa (cid:9)
`370/13
`
`5/1994 (cid:9) Phaal (cid:9)
`365/49
`
`8/1994 Machida (cid:9)
`370/92
`
`9/1994 (cid:9) Kalkunte et al. (cid:9)
`370/17
`
`11/1994 (cid:9) Hershey et al. (cid:9)
`364/550
`
`12/1994 (cid:9) Hershey et al. (cid:9)
`370/60
`
`2/1995 (cid:9) Crowther et al. (cid:9)
` 364/715.02
`5/1995 Hekhuis (cid:9)
`
`370/60
`5/1995 (cid:9) Spinney (cid:9)
`
`370/13
`7/1995 Galloway (cid:9)
`
`370/17
`7/1995 (cid:9) Harper (cid:9)
`
`395/821
`2/1996 Waclawsky et al. (cid:9)
`
`370/17
`3/1996 (cid:9) Hershey et al. (cid:9)
`
`395/800
`4/1996 (cid:9) Correa
`
`395/800
`4/1996 (cid:9) Terasaka et al. (cid:9)
`
`711/136
`6/1996 (cid:9) Colloff et al. (cid:9)
`
`711/3
`6/1996 (cid:9) Agarwal et al. (cid:9)
`
`395/200.2
`7/1996 (cid:9) Krause et al. (cid:9)
`
`370/17
`10/1996 (cid:9) Hershey et al. (cid:9)
`
`395/403
`11/1996 (cid:9) Stansfield et al. (cid:9)
` 395/200.11
`12/1996 (cid:9) Hershey et al. (cid:9)
` 395/200.11
`2/1997 Shwed (cid:9)
` 364/724.01
`3/1997 (cid:9) Large et al. (cid:9)
` 395/200.11
`5/1997 (cid:9)
`Iddon et al. (cid:9)
`
`370/392
`7/1997 (cid:9) Van Seters et al. (cid:9)
`
`703/26
`10/1997 (cid:9) Bruell (cid:9)
`11/1997 (cid:9) Kaiserswerth et al. ... 395/200.2
`12/1997 (cid:9) Nuber et al. (cid:9)
`
`370/395
`2/1998 (cid:9) Picazo, Jr. et al. (cid:9)
`
`395/200.2
`2/1998 (cid:9) Logan et al. (cid:9)
`
`709/217
`3/1998 (cid:9) Gessel et al. (cid:9)
` 395/200.11
`Measurement and Analysis of the Digital DECT propagation
`4/1998 Watanabe et al. (cid:9)
` 395/183.21
`Channel; IEEE; 1998.
`5/1998 (cid:9) Hoover et al. (cid:9)
`
`711/108
`6/1998 Adams et al. (cid:9)
` 395/200.47
`R, Periakaruppam and E. Nemeth. "GTrace—A Graphical
`6/1998 Thompson (cid:9)
`
`709/224
`Traceroute (cid:9) Tool." (cid:9) 1999 (cid:9) Usenix (cid:9) LISA. (cid:9) Available (cid:9) on
`6/1998 Ketchum (cid:9)
`
`370/401
`www.caida.org, (cid:9) URL: (cid:9) http://www.caida.org/outreach/pa-
`7/1998 Southard (cid:9)
` 395/200.54
`pers/1999/GTrace/GTrace.pdf.
`7/1998 (cid:9) Hershey et al. (cid:9)
`
`364/557
` 395/200.61 W. Stallings. "Packet Filtering in the SNMP Remote Moni-
`7/1998 McCreery et al. (cid:9)
`tor." Nov. 1994. Available on www.ddj.com, URL: http://
`8/1998 Kuriyan (cid:9)
`
`709/223
`www.ddj .com/documents/s=1013/ddj 9411 h/9411 h. htm.
`9/1998 (cid:9) Bellenger (cid:9)
`
`370/401
`"Technical Note: the Narus System," Downloaded Apr. 29,
`9/1998 (cid:9) Hasani et al. (cid:9)
`
`395/200.2
`9/1998 (cid:9) Czarnik et al. (cid:9)
`
`370/245
`1999 from www.narus.com, Narus Corporation, Redwood
`10/1998 Manghirmalani
`City California.
`et al. (cid:9)
`10/1998 (cid:9) Ready et al. (cid:9)
`
`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
`5,315,580 A
`5,339,268 A
`5,351,243 A
`5,365,514 A
`5,375,070 A
`5,394,394 A
`5,414,650 A
`5,414,704 A
`5,430,709 A
`5,432,776 A
`5,493,689 A
`5,500,855 A
`5,511,213 A
`5,511,215 A
`5,530,834 A
`5,530,958 A
`5,535,338 A
`5,568,471 A
`5,574,875 A
`5,586,266 A
`5,606,668 A
`5,608,662 A
`5,634,009 A
`5,651,002 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
`5,764,638 A
`5,781,735 A
`5,784,298 A
`5,787,253 A
`5,799,154 A
`5,802,054 A
`5,805,808 A
`5,812,529 A
`5,819,028 A
`
`5,825,774 A
`
`11/1998 (cid:9) Shwed et al. (cid:9)
`5,835,726 A (cid:9)
`11/1998 (cid:9) Schwaller et al. (cid:9)
`5,838,919 A (cid:9)
`11/1998 Huffman (cid:9)
`5,841,895 A (cid:9)
`12/1998 Anderson et al. (cid:9)
`5,850,386 A (cid:9)
`12/1998 Anderson et al. (cid:9)
`5,850,388 A (cid:9)
`1/1999 (cid:9) Welch, Jr. et al. (cid:9)
`5,862,335 A (cid:9)
`3/1999 (cid:9) de la Salle (cid:9)
`5,878,420 A (cid:9)
`4/1999 (cid:9) Cheriton (cid:9)
`5,893,155 A (cid:9)
`5/1999 (cid:9) Pearson (cid:9)
`5,903,754 A (cid:9)
`6/1999 (cid:9) Gobuyan et al. (cid:9)
`5,917,821 A (cid:9)
`12/1999 (cid:9) Carter et al. (cid:9)
`6,003,123 A (cid:9)
`1/2000 (cid:9) Hendel et al. (cid:9)
`6,014,380 A (cid:9)
`8/2000 (cid:9) Chen et al. (cid:9)
`6,097,699 A (cid:9)
`9/2000 (cid:9) Engel et al. (cid:9)
`6,115,393 A (cid:9)
`* (cid:9) 9/2000 Zaumen et al. (cid:9)
`6,118,760 A (cid:9)
`6,243,667 B1 * (cid:9)
`6/2001 (cid:9) Kerr et al. (cid:9)
`6,269,330 B1 (cid:9)
`7/2001 (cid:9) Cidon et al. (cid:9)
`6,272,151 B1 (cid:9)
`8/2001 (cid:9) Gupta et al. (cid:9)
`6,279,113 B1 (cid:9)
`8/2001 (cid:9) Vaidya (cid:9)
`6,282,570 B1 (cid:9)
`8/2001 (cid:9) Leung et al. (cid:9)
`6,330,226 B1 (cid:9)
`12/2001 (cid:9) Chapman et al. (cid:9)
`6,363,056 B1 (cid:9)
`3/2002 (cid:9) Beigi et al. (cid:9)
`6,381,306 B1 (cid:9)
`4/2002 (cid:9) Lawson et al. (cid:9)
`6,424,624 B1 (cid:9)
`7/2002 (cid:9) Galand et al. (cid:9)
`6,430,409 B1 (cid:9)
`8/2002 Rossmann (cid:9)
`6,452,915 B1 * (cid:9) 9/2002 Jorgensen (cid:9)
`6,453,345 B2 (cid:9)
`9/2002 (cid:9) Trcka et al. (cid:9)
`6,453,360 B1 * (cid:9)
`9/2002 (cid:9) Muller et al. (cid:9)
`6,466,985 B1 * 10/2002 (cid:9) Goyal et al. (cid:9)
`6,483,804 B1 * 11/2002 (cid:9) Muller et al. (cid:9)
`6,510,509 B1 * (cid:9)
`1/2003 (cid:9) Chopra et al. (cid:9)
`6,516,337 B1 (cid:9)
`2/2003 (cid:9) Tripp et al. (cid:9)
`6,519,568 B1 (cid:9)
`2/2003 (cid:9) Harvey et al. (cid:9)
`6,570,875 B1 * (cid:9) 5/2003 Hegde (cid:9)
`6,625,657 B1 (cid:9)
`9/2003 (cid:9) Bullard (cid:9)
`6,651,099 B1 (cid:9)
`11/2003 (cid:9) Dietz et al. (cid:9)
`6,791,947 B2 * (cid:9)
`9/2004 (cid:9) Oskouy et al. (cid:9)
`
`OTHER PUBLICATIONS
`
` 395/200.59
` 395/200.54
`382/155
` 370/241
` 370/252
` 395/200.54
` 707/10
` 711/144
` 395/680
` 370/392
` 711/207
` 370/392
` 370/231
` 370/469
` 370/229
` 703/27
` 704/43
` 370/489
` 713/201
` 709/224
` 370/232
` 370/252
` 379/32
` 370/231
` 455/422.1
` 370/238
` 709/224
` 709/250
` 709/238
` 370/230
` 712/13
` 709/202
` 705/1
` 370/389
` 709/237
` 709/224
` 370/238
`
`
`
`
`395/185.1
`370/401
`
`* cited by examiner
`
`NOAC Ex. 1005 Page 2
`
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 1 of 18 (cid:9)
`
`US 6,954,789 B2
`
`100
`
`CLIENT 4
`
`107
`
`CLIENT3
`
`----
`106 (cid:9)
`
`),'
`
`-'-—.
`
`121
`
`DATA COMMUNICATIONS
`NETWORK
`
`108
`
`116
`
`--\110
`
`102
`
`125
`
`SERVER 2
`M
`112
`
`123
`
`105
`
`118
`J
`CLIENT 1 M
`104
`
`FIG. 1
`
`NOAC Ex. 1005 Page 3
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 2 of 18 (cid:9)
`
`US 6,954,789 B2
`
`C\1
`0
`LL
`
`in N. c.i ,..., ›,
`
`in.
`2
`E
`D
`115
`D
`
`(.7
`
`a) O
`N
`
`datum request
`
`N
`CL
`
`6
`
`cir
`
`1:1 11 110
`
`.. ,==,.., _.=, .. .. I=
`.==.
`
`(NI
`cc
`w
`cc
`w
`z
`0
`i=
`ciT <
`U_
`1
`a_
`a_
`a
`
`..r-
``,.....
`
`NOAC Ex. 1005 Page 4
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 3 of 18 (cid:9)
`
`US 6,954,789 B2
`
`---1-11j4:9
`Z
`
`1
`
`c% —\
`
`I
`
`co
`W
`>-
`
`I
`
`M cv
`CO
`
`t (cid:9)
`
`I
`
`1
`i
`1
`1
`I
`
`el
`CO
`CD
`CO
`
`,c—' (cid:9)
`co (cid:9)
`
`1-'
`c0
`0
`CO
`
`r .:r
`
`CO
`
`CV
`0
`CO
`
`0
`CO CO
`
`2 1 >- I
`1
`1
`....— 1
`1
`1
`1
`1
`1
`1
`1
`
`(cid:9)i
`
`CO
`CO CO
`
`7 (cid:9) 2 N
`i cc g
`0 w 1—
`< ›- 0
`i_ < LLI
`< --i —I
`0 LY)
`
`Al (cid:9)
`
`
`
`r \ \V - 5, 6 !Eiji
`0 I= <
`0 CL D
`
`0c I— 5
`u) z
`cn
`cn / (cid:9)
`Er W <
`V vil ct_ o -1 1
`
`co
`
`d U-
`
`NOAC Ex. 1005 Page 5
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 4 of 18 (cid:9)
`
`US 6,954,789 B2
`
`0-----\-- 401
`
`j- 402
`
`"."-........
`
`.---
`.---.
`HIGH LEVEL
`PACKET
`DECODING
`DESCRIPTIONS
`,... (cid:9)
`--,
`
`COMPILE
`DESCRIPTIONS
`
`C 403
`
`c 408
`
`409 --)
`
`405
`
`GENERATE
`PACKET
`STATE
`INSTRUCTIONS
`AND
`OPERATIONS
`
`►
`
`407
`
`41.---immer (cid:9)
`
`1:04
`,--
`STATE
`PROCESSOR \..
`INSTRUCTION
`DATABASE
`...... (cid:9)
`--,
`
`404
`
`GENERATE
`PACKET
`PARSE AND
`EXTRACT
`OPERATIONS
`
`4
`
`--.
`
`..--- (cid:9)
`...._,
`-----
`,---
`406 77PATTERN, PARSE
`AND
`EXTRACTION
`... DATABASE
`...,
`
`LOAD
`PARSING
`SUBSYSTEM
`MEMORY
`
`LOAD STATE
`NSTRUCTIONA4 (cid:9)
`DATABASE
`MEMORY
`
`\ 400
`
`-----°.C----4-TO
`FIG. 4
`
`NOAC Ex. 1005 Page 6
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent
`
`Oct. 11, 2005
`
`Sheet 5 of 18 (cid:9)
`
`US 6,954,789 B2
`
`501
`
`/INPUT PACKET (cid:9)
`
`502
`
`503 *._7
`
`LOAD PACKET
`COMPONENT 4 (cid:9)
`
`504
`
`ORE IN PACK
`
`NO
`
`512
`
`BUILD
`PACKET
`KEY
`
`YES
`
`o.
`
`MORE
`PATTERN
`NODES?
`
`506
`
`YES
`ir
`APPLY NODE AND
`PROCESS TO
`COMPONENT
`
`507 —C----
`
`513
`
`NO
`
`NEXT
`PACKET ---)
`COMPONENITC_ 511
`4.
`
`510
`
`N EXT
`PATTERN
`NODE
`
`N
`
`ATTERN MAT
`
`508
`
`500
`
`YES
`
`•
`EXTRACT
`ELEMENTS
`
`509
`
`FIG. 5
`
`NOAC Ex. 1005 Page 7
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 6 of 18 (cid:9)
`
`US 6,954,789 B2
`
`601
`
`602
`
`PACKET
`
`/COMPONENT AND
`
`PATTERN NODE
`
`LOAD PACKET
`COMPONENT
`
`604
`
`"YES
`It1/4 FETCH EXTRACTION
`ND PROCESS FROM-_
`PATTERNS
`
`605
`
`NO
`
`NEXT
`PACKET (cid:9)
`COMPONENT
`
`NO* , (cid:9)
`
`611
`
`609
`
`607 7.____
`
`YES
`APPLY EXTRACTION
`PROCESS TO
`COMPONENT
`
`\600
`
`FIG. 6
`
`NOAC Ex. 1005 Page 8
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 7 of 18 (cid:9)
`
`US 6,954,789 B2
`
`701
`
`•
`
`EY BUFFER AND (cid:9)
`ERN NODE
`/PATT
`
`702
`
`LOAD PATTERN
`(cid:9)
`703 —\.____-- N
`ELEMENT 14
`
`708
`
`704
`
`NO
`
`YES
`V
`HASH KEY BUFFER
`ELEMENT FROM
`PATTERN NODE
`
`705
`
`PACK KEY & HASH
`
`•
`
`NEXT PACKET
`COMPONENT
`
`706
`
`707
`
`FIG. 7
`
`709
`
`700
`
`NOAC Ex. 1005 Page 9
`
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 8 of 18 (cid:9)
`
`US 6,954,789 B2
`
`(1).
`
`— 801
`
`800 \
`
`/UFKB ENTRY FOR
`PACKET
`
`802
`
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH
`
`803
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE 7-- 804
`
`806
`
`805
`
`ORE BUCKET
`IN THE BIN?
`
`NO
`
`SET UFKB FOR
`PACKET AS 'NEW'
`
`YES
`COMPARE CURRENT BIN
`AND BUCKET RECORD KEY
`TO PACKET
`
`807
`
`NEXT BUCKET
`
`KEY MATCH?
`
`808
`
`809
`
`811
`
`812
`
`YES
`
`MARK RECORD BIN AND (cid:9)
`BUCKET 'IN PROCESS' IN / (cid:9)
`CACHE AND TIMESTAMP
`•
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`n
`—
`
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`813 —(:) (cid:9)
`
`FIG. 8
`
`NOAC Ex. 1005 Page 10
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 9 of 18 (cid:9)
`
`US 6,954,789 B2
`
`c 902
`
`Qs, (cid:9) 910
`
`BIND LOOKU
`REQUEST
`
`ERPC
`
`909
`
`EXTRACT PORT
`
`GET 'PROGRAM',
`'VERSION' AND
`'PROTOCOL (TCP OR
`UDP)'
`
`908
`SAVE REQUEST
`
`SAVE 'PROGRAM',
`'VERSION' AND
`'PROTOCOL (TCP OR
`UDP)' WITH
`DESTINATION
`NETWORK ADDRESS.
`BOTH MAKE A KEY.
`
`)
`
`907
`
`(cid:9) 1RPC'-‘‘\)
`
`BIND
`LOOKUP
`REPLY
`
`901
`
`RPC
`REPLY
`ORTMAPP
`
`RPC
`NNOUNCME
`ORTMAPP
`
`903
`
`904
`
`EXTRACT PROGRAM
`
`GET 'PROGRAM',
`'VERSION', 'PORT AND
`'PROTOCOL (TCP OR
`UDP)
`
`7
`CREATE SERVER STATE
`
`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.
`
`(--- 905
`
`906 —\
`
`9001
`
`LOOKUP REQUE
`
`FIND 'PROGRAM'
`AND 'VERSION'
`WITH LOOKUP OF
`SOURCE NETWORK
`ADDRESS.
`
`EXTRACT
`PROGRAM
`
`GET 'PORT AND
`'PROTOCOL (TCP
`OR UDP)'.
`
`2
`
`FIG. 9
`
`NOAC Ex. 1005 Page 11
`
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 10 of 18 (cid:9)
`
`US 6,954,789 B2
`
`1000 --,k
`
`PATTERN
`RECOGNITION
`DATABASE
`MEMORY
`
`100 (cid:9)
`
`1 001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`wilav
`
`100
`
`7
`
`1005---v_
`
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS
`
`1031
`\-1004
`"K.7
`
`k INFO OUT
`!
`
`CONTRL (N
`
`"4... 7
`
`EXTRACTION ENGINE
`(SLICER)
`
`1•111IP•milTIMINIIIIIIIII.
`
`1031-1
`
`1007
`
`1013—
`
`11
`
`
`
`100 (cid:9)6—\
`PATTERN
`\ RECOGNITN (cid:9)
`ENGINE
`(cid:9)
`(PRE)
`
`1008Th
`
`PACKE
`INPUT
`
`(-1012
`
`10211
`
`V
`
`PARSER INPUT BUFFER
`MEMORY
`
`PARSER I (cid:9)
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`MEMORY I
`
`/
`
`PACKET\
`START/ INPUT BUFFER
`INTERFACE
`CONTROL
`
`NEXT
`PACKET
`
`101
`
`1011
`
`1025
`
`ANALYZER
`INTERFACE
`CONTROL
`
`DATA REA Y
`
`ANALYZER
`READY
`
`1022
`1023
`
`HG. 10
`
`1027 i
`
`NOAC Ex. 1005 Page 12
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005 (cid:9)
`
`Sheet 11 of 18 (cid:9)
`
`US 6,954,789 B2
`
`1100
`
`1103
`
`LOOKUP/
`UPDATE
`ENGINE
`(LUE)
`
`
`
`STATE
`PROCESSR
`, I NSTRUCN
`} DATABASE
`1109 (cid:9)
`(S PI D)
`
`1115
`
`2—)
`1118 112
`
`
`1107
`
`A NALYZE F
`HOST
`INTER FAC
`AND
`CONTROL
`(AC IC)
`
`HOST
`BUS
`INTER-
`FACE
`(HIB)
`
`-77
`L.
`
`UNIFIED
`FLOW
`/LA (cid:9) K EY
`PARSER
`INTER-
`sc—i1BUFFER
`(UFKB)
`FACE
`
`1108
`
`CACHE
`
`STATE
`PROCESSR
`(SP)
`
`1111111
`
`.
`
`FLOW
`INSERTION/
`DELETION
`ENGINE
`(FIDE)
`
`—1110
`
`FIG. 11
`
`1123?
`
`UNIFIED
`MEMORY
`CONTROL
`(U MC)
`
`MEMORY
`INTER-
`FAC E
`
`11.111111111111k
`
`NOAC Ex. 1005 Page 13
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 12 of 18 (cid:9)
`
`US 6,954,789 B2
`
`1201
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`1202
`
`1200 ----A
`
`j-1203
`
`v
`ACCESS
`CONVERSATION
`RECORD BIN
`
`i.
`
`REQUEST RECORD BIN/
`_7-1204
`BUCKET FROM CACHE
`
`1206-1
`
`REQUEST NEXT
`BUCKET FROM
`CACHE
`
`1205
`
`1208
`
`1210----\
`
`SET UFKB FOR
`PACKET AS
`'DROP'
`
`INSERT KEY AND HASH
`N BUCKET, MARK 'USED
`WITH TIM ESTAMP
`
`COMPARE CURRENT BI
`AND BUCKET RECORD
`KEY TO PACKET
`
`1209
`
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS'
`AND 'NEW IN CACHE
`
`1211
`
`1212---\___
`
`SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`1213
`
`FIG. 12
`
`NOAC Ex. 1005 Page 14
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 13 of 18 (cid:9)
`
`US 6,954,789 B2
`
`1300
`
`1301
`
`UFKB ENTRY FOR
`PACKET WITH STATUS
`'NEW' OR 'FOUND' (cid:9)
`71,
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO
`VALUE FOUND IN UFKB ENTRY
`
`FETCH INSTRUCTION FROM
`STATE PROCESSOR
`INSTRUCTION MEMORY
`
`1302
`
`1303
`
`1304
`
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION
`
`1305
`
`SET STATE
`PROCESSOR
`INSTRUCTION
`POINTER TO
`VALUE FOUND IN
`CURRENT STATE
`
`NO
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET?
`
`1307
`
`1308
`1310
`
`- (cid:9)
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`1 NO
`POINTER IN
`CURRENT FLOW
`RECORD
`
`YES
`
`DONE PROCESSING
`TATES FOR THIS FLO
`
`1309
`
`YES
`
`SET AND SAVE FLOW REMOVAL
`j-1311
`STATE PROCESSOR (cid:9)
`INSTRUCTION IN CURRENT
`FLOW RECORD
`
`1313
`
`FIG. 13
`
`NOAC Ex. 1005 Page 15
`
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 14 of 18 (cid:9)
`
`US 6,954,789 B2
`
`r"-
`
`4 (cid:9)
`
`4 (cid:9)
`
`r
`CO
`0
`•••••
`
`0_ Z
`zkli 0
`..z17.:
`-NwNOPm<
`>-Opm
`0<0
`,9?- Nr z< L
`"k-
`- <
`z
`...
`
`-
`
`w z u)
`w soz
`z m — 0
`MD 1--
`
`W1-00 1—
`<<
`1— D<CM
`
`<11i 1—
`cc
`MI—
`Xm
`cp w0
`
`21
`CCuj i
`w
`1 CC, >-
`M'
`<COI
`MD
`w 1
`
`NOAC Ex. 1005 Page 16
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 15 of 18 (cid:9)
`
`US 6,954,789 B2
`
`CD
`0
`LC) ,-.
`
`>-
`cc
`u) 0
`Om
`i w
`2
`
`co 0u, •,--
`
`4111----11.
`0
`LU
`
`2
`
`LU
`1-
`
`0
`
`Tr
`0
`LO
`•-•
`
`__.
`
`w
`P
`(i) (cid:9)
`c
`co_
`a
`m
`u_5
`< 0 2
`_.1
`I-- (cid:9)
`Li- 2
`4:C (cid:9)
`....
`
`0c
`
`W
`N
`
`< (i)1 z
`<
`
`cc
`w
`cc (V,
`Q a_
`
`NOAC Ex. 1005 Page 17
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 16 of 18 (cid:9)
`
`US 6,954,789 B2
`
`1602
`
`0 - 3 Bytes
`
`Dst MAC
`offset 0 - 11 Dst MAC I Src MAC —
`Src MAC
`
`k 1600
`
`(cid:9)_i 1604
`
`1608
`
`1612
`
`__Dst Hash (21 (cid:9)
`
`/N (cid:9)
`
`Dst MAC (6)
`
`Src MAC (6)
`
` 1606
`
`1610
`..------2
`
`1614 Src Hash (2;
`
`.,1_2 Offs
`et = 12
`
`FIG. 16
`
`NOAC Ex. 1005 Page 18
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`
`Oct. 11, 2005
`
`Sheet 17 of 18 (cid:9)
`
`US 6,954,789 B2
`
`1702
`
`offset
`12 to 13
`
`Type
`
`1704
`
`1706
`
`lr-- 1700
`
`1708 (cid:9)
`
`1710
`
`Type (2)
`Hash ,1)
`
`1_.L.3 Off
`
`et = 14
`
`FIG. 17A
`
`1712
`
`L3 to
`[L3 +
`OHL /
`- 1]
`
`irLIF (cid:9)
`
`Protocol
`Src Address
`Dst Address
`I 2717 at71111117
`
`A
`fA
`
`IDP = 0x0600*
`IP = 0x0800*
`CHAOSNET = 0x0804
`ARP = 0x0806
`VIP = Ox0BAD*
`VLOOP = OxOBAE
`VECHO = OxOBAF
`NETBIOS-3COM = Ox3C00 -
`0x3COD
`DEC-MOP = 0x6001
`DEC-RC = 0x6002
`DEC-DRP = 0x6003*
`DEC-LAT = 0x6004
`DEC-DIAG = 0)(6005
`DEC-LAVC = 0x6007
`RARP = 0x8035
`ATALK= Ox809B*
`VLOOP = 0x80C4
`VECHO = 0x8005
`SNA-TH = 0x80D5*
`ATALKARP= 0x80F3
`IPX = 0x8137*
`SNMP = 0x814C#
`IPv6 = Ox86DD'
`LOOPBACK = 0x9000
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`1752
`
`ICMP = 1
`IGMP = 2
`GGP = 3
`TCP = 6*
`EGP =8
`IGRP = 9
`PUP = 12
`CHAOS = 16
`UDP = 17*
`IDP = 22#
`ISO-TP4 = 29
`DDP = 37#
`ISO-IP = 80
`VIP = 83#
`EIGRP = 88
`OSPF = 89
`
`IF— 1750
`
`Dst Address
`Dst Hash (2)
`Src Address
`Src Hash (2)
`
`
`
`of (1) Protoc
`
`L4 Off' et = L3 + (IHU4)
`
`FIG. 17B
`
`* L4 Decoding
`# L3 Re-Decoding
`
`NOAC Ex. 1005 Page 19
`
`(cid:9)
`

`

`U.S. Patent
`
`Oct. 11,2005
`
`Sheet 18 of 18
`
`US 6,954,789 B2
`
`PROTOCOL
`TYPE (Ili
`
`AL---1800
`
`FIELD LENGTH
`
`I- OCA,
`(Opps N
`
`1642
`
`1802-2
`1802-1
`
`1802-M
`
`FIG. 18A
`
`1870
`
`LUT NUM 4.
`
`__Ji
`0
`0
`0
`O cc
`
`[ (cid:9) I
`
`FIG. 18B
`
`NOAC Ex. 1005 Page 20
`
`

`

`1
`METHOD AND APPARATUS FOR
`MONITORING TRAFFIC IN A NETWORK
`
`US 6,954,789 B2
`
`CROSS-REFERENCE TO RELATED
`APPLICATION (cid:9)
`
`5
`
`10
`
`15
`
`20
`
`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. 25
`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.
`
`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
`35 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
`
`30
`
`40
`
`45
`
`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.
`
`50
`
`BACKGROUND TO THE PRESENT
`INVENTION
`There has long been a need for network activity monitors. 55
`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 60
`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 65
`accessed, and for how long, is very useful in the mainte-
`nance and continued operation of these networks. It is
`
`NOAC 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 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-
`
`1 0
`
`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
`5 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
`is 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
`20 examined varies for any particular protocol. Furthermore,
`the present invention is capable of examining up to whatever
`level is sufficient to uniquely identify to