`Dietz et al. (cid:9)
`
`11111111111111101111111111111p11131y111111111111111111110111111
`
`(to) Patent No.: (cid:9)
`(45) Date of Patent: (cid:9)
`
`US 6,839,751 B1
`Jan. 4, 2005
`
`(54)
`
`(75)
`
`RE-USING INFORMATION FROM DATA
`TRANSACTIONS FOR MAINTAINING
`STATISTICS IN NETWORK MONITORING
`
`Inventors: Russell S. Dietz, San Jose, CA (US);
`Joseph R. Maixner, Aptos, CA (US);
`Andrew A. Koppenhaver, Littleton,
`CO (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 728 days.
`
`(21)
`
`Appl. No.: 09/608,126
`
`(22)
`
`Filed: (cid:9)
`
`Jun. 30, 2000
`
`Related U.S. Application Data
`(60) Provisional application No. 60/141,903, filed on Jun. 30,
`1999.
`
`GO6F 15/173
`
`Int. C1.7 (cid:9)
`(51)
`709/224; 709/223; 709/230
`
`(52) U.S. Cl. (cid:9)
`
`(58) Field of Search (cid:9)
`709/223, 224,
`709/231, 232, 230; 370/252, 231; 379/32;
`704/43; 714/39; 340/825
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,972,453 A (cid:9) * 11/1990 Daniel et al. (cid:9)
`7/1996 Krause et al. (cid:9)
`* (cid:9)
`5,535,338 A (cid:9)
`12/1997 Nuber et al. (cid:9)
`5,703,877 A (cid:9)
`* (cid:9) 2/1998 Picazo, Jr. et al. (cid:9)
`5,720,032 A (cid:9)
`* (cid:9) 6/1998 Thompson (cid:9)
`5,761,429 A (cid:9)
`* (cid:9) 8/1998 Kuriyan (cid:9)
`5,799,154 A (cid:9)
`* (cid:9) 9/1998 Bellenger (cid:9)
`5,802,054 A (cid:9)
`5,850,388 A (cid:9) * 12/1998 Anderson et al. (cid:9)
`4/1999 Kompella et al. (cid:9)
`5,892,754 A (cid:9)
`8/2000 Chen et al. (cid:9)
`6,097,699 A (cid:9)
`* (cid:9)
`* (cid:9) 9/2000 Engel et al. (cid:9)
`6,115,393 A (cid:9)
`6,269,330 B1 * (cid:9) 7/2001 Cidon et al. (cid:9)
`6,279,113 B1 * (cid:9) 8/2001 Vaidya (cid:9)
`6,282,570 B1 * (cid:9) 8/2001 Leung et al. (cid:9)
`
` 379/9.03
` 709/222
` 370/395
` 709/250
` 709/224
` 709/223
` 370/401
` 370/252
` 370/236
` 370/231
` 370/469
` 704/43
` 713/201
` 709/224
`
`6,330,226 B1 * 12/2001 Chapman et al. (cid:9)
`6,363,056 B1 * 3/2002 Beigi et al. (cid:9)
`6,381,306 B1 * 4/2002 Lawson et al. (cid:9)
`6,424,624 B1 * 7/2002 Galand et al. (cid:9)
`6,453,345 B2 * 9/2002 Trcka et al. (cid:9)
`6,625,657 B1 * 9/2003 Bullard (cid:9)
`6,651,099 B1 * 11/2003 Dietz et al. (cid:9)
`
`
`
`
`
`
`
`
`
`370/232
`370/252
`379/32
`370/231
`709/224
`709/237
`709/224
`
`OTHER PUBLICATIONS
`
`NOV94: Packet Filtering in the SNMP Remote Monitor ;
`www.skrymir.com/dobbs/articles/1994/9411/9411h/
`9411h.htm.*
`GTrace—A Graphical Traceroute Tool authored by Ram
`Periakaruppan, Evi Nemeth ; http://www.caida.org/out-
`re ach/p apers/1999/GTr ace/index .xml.*
`Advanced Methods for Storage and Retrieval in Image ;
`http://www.cs.tulane.edu/www/Prototype/proposal.html;
`1998.*
`Measurement and analysis of the digital DECT propagation
`channel; IEEE 1998.*
`
`* cited by examiner
`
`Primary Examiner—Thong Vu
`(74) Attorney, Agent, or Firm—Dov Rosenfeld; Inventek
`
`(57) (cid:9)
`
`ABSTRACT
`
`A method of and monitor apparatus for analyzing a flow of
`packets passing through a connection point on a computer
`network. The method includes receiving a packet from a
`packet acquisition device, and looking up a flow-entry
`database containing flow-entries for previously encountered
`conversational flows. The looking up to determine if the
`received packet is of an existing flow. Each and every packet
`is processed. If the packet is of an existing flow, the method
`updates the flow-entry of the existing flow, including storing
`one or more statistical measures kept in the flow-entry. If the
`packet is of a new flow, the method stores a new flow-entry
`for the new flow in the flow-entry database, including
`storing one or more statistical measures kept in the flow-
`entry. The statistical measures are used to determine metrics
`related to the flow. The metrics may be base metrics from
`which quality of service metrics are determined, or may be
`the quality of service metrics.
`
`21 Claims, 18 Drawing Sheets
`
`100
`
`CLIENT 4
`
`CLIENT 3
`
`106
`
`107
`
`-108
`ANALYZER
`
`1SERVER 2
`
`\-121
`
`116
`
`'110
`
`102
`
`125
`
`118
`
`CLIENT 1
` 104
`
`SERVER 2
`Th
`112
`
`NOAC Ex. 1004 Page 1
`
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 1 of 18 (cid:9)
`
`US 6,839,751 B1
`
`100
`
`I
`
`CLIENT 4
`
`CLIENT 3
`
`M
`106
`
`SERVER 2
`
`-121
`
`DATA COMMUNICATIONS
`NETWORK
`
`SERVER 2
`---
`112
`
`123
`
`105
`
`CLIENT 2
`
`CLIENT 1
`
`118
`
`----.
`
`104
`
`FIG. 1
`
`NOAC Ex. 1004 Page 2
`
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 2 of 18 (cid:9)
`
`US 6,839,751 B1
`
` == I= I=
`
`=1=0
`00
`I=
`
`1 Er 1:1 /'
`
`CV
`0
`u_
`
`CD
`0
`C\J
`
`C\J
`C\JCILZ---\
`
`an
`
`I
`
`NOAC Ex. 1004 Page 3
`
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 3 of 18 (cid:9)
`
`US 6,839,751 B1
`
`C7 Z
`-z0
`} l<7
`<
`I- cc W
`X 0
`° Z
`
`411 (cid:9)
`
`CO
`CO
`
`w Z N o
` < Z cc <
`N 0 I-U 2 CC -41
`>-01— mg
`w iSE
`Z
`
`z
`
`w
`0
`
`N O
`
`CO
`
`cc < 0w
`0 p
`0 <
`m < M P
`W <
`I-- X0 w
`
`co
`co co
`
`Co
`co
`
`CC CC
`W
`-J N
`
`0-
`O
`O 0
`
`co
`
`CO
`CY)
`CO
`
`U-
`
`NOAC Ex. 1004 Page 4
`
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005 (cid:9)
`
`Sheet 4 of 18 (cid:9)
`
`US 6,839,751 B1
`
`401
`
`402
`
`HIGH LEVEL
`PACKET
`DECODING
`DESCRIPTIONS
`
`
`COMPILE
`DESCRIPTIONS
`
`C 403
`
`405
`
`GENERATE
`PACKET
`STATE
`INSTRUCTIONS
`AND
`OPERATIONS
`
`404
`
`GENERATE
`PACKET
`PARSE AND 4 (cid:9)
`EXTRACT
`OPERATIONS
`
`406 7,PATTEFZIbPARSE
`
`EXTRACTION
`DATABASE
`
`408 (cid:9)
`
`409 D
`
`STATE
`PROCESSOR \,
`INSTRUCTION
`DATABASE
`
`407
`
`LOAD
`PARSING
`SUBSYSTEM
`MEMORY
`
`LOAD STATE
`INSTRUCTION (cid:9)
`DATABASE
`MEMORY
`
`)
`
`400
`
`410
`
`FIG. 4
`
`NOAC Ex. 1004 Page 5
`
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 5 of 18 (cid:9)
`
`US 6,839,751 B1
`
`501
`
`/INPUT PACKET (cid:9)
`
`502
`
`FETCH NODE ANC
`(cid:9) PROCESS FROM _ 505
`PATTERNS
`
`510
`
`500
`
`509
`
`EXTRACT
`ELEMENTS
`
`FIG. 5
`
`NOAC Ex. 1004 Page 6
`
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 6 of 18 (cid:9)
`
`US 6,839,751 B1
`
`601
`
`602
`
`•
`PACKET
`
`/COMPONENT AND
`
`PATTERN NODE
`
`•
`LOAD PACKET
`COMPONENT
`
`FETCH EXTRACTION
`AND PROCESS FROM---)
``--•
`
`PATTERNS (cid:9)
`
`605
`
`APPLY EXTRACTION
`PROCESS TO
`COMPONENT
`
`600
`
`FIG. 6
`
`NOAC Ex. 1004 Page 7
`
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 7 of 18 (cid:9)
`
`US 6,839,751 B1
`
`701
`
`•
`EY BUFFER AND (cid:9)
`PATTERN NODE
`
`702
`
`703 —\____7
`
`•
`LOAD PATTERN
`(cid:9)
`N
`ELEMENT 14
`
`708 —)
`
`704
`
`NO
`
`OUTPUT TO
`ANALYZER
`
`705
`
`YES
`V
`HASH KEY BUFFER
`ELEMENT FROM
`PATTERN NODE
`
`•
`
`PACK KEY & HASH
`
`•
`
`FIG. 7
`
`706
`
`707
`
`709
`
`700
`
`NOAC Ex. 1004 Page 8
`
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 8 of 18 (cid:9)
`
`US 6,839,751 B1
`
`800
`
`801
`
`/UFKB ENTRY FOR
`PACKET
`
`•
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH
`
`802
`
`803
`
`•
`REQUEST RECORD BIN/
`BUCKET FROM CACHE 7- 804
`
`806
`
`805
`
`ORE BUCKET
`IN THE BIN?
`
`NO
`
`SET UFKB FOR
`PACKET AS 'NEW'
`
`NEXT BUCKET
`
`4-N
`
`(_ 809
`
`811 --\_
`
`812
`
`YES
`•
`COMPARE CURRENT BIN
`AND BUCKET RECORD KEY
`TO PACKET
`
`807
`
`808
`
`MARK RECORD BIN AND
`-- 810
`BUCKET 'IN PROCESS' IN r
`CACHE AND TIMESTAMP
`•
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`V
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`813 -\ya FIG. 8
`
`NOAC Ex. 1004 Page 9
`
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 9 of 18 (cid:9)
`
`US 6,839,751 B1
`
`901 (cid:9)
`
`2
`
`RPC
`REPLY
`ORTMAPP
`
`902
`
`910
`
`RPC
`NNOUNCME
`ORTMAPPE
`
`eRPC 10
`
`BIND LOOKU! KRE,QUEST
`
`909
`
`903
`
`EXTRACT PROGRAM
`
`GET 'PROGRAM',
`'VERSION', 'PORT AND
`'PROTOCOL (TCP OR
`UDP)
`
`CREATE SERVER STATE
`
`904 --)
`
`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.
`
`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.
`
`I
`
`907
`
`BIND
`RPC)
`LOOKUP
`REPLY.,
`
`(---- 905
`
`906 -
`
`9001
`
`LOOKUP REQUE
`
`FIND 'PROGRAM'
`AND 'VERSION'
`WITH LOOKUP OF
`SOURCE NETWORK
`ADDRESS.
`
`EXTRACT
`PROGRAM
`
`A)
`
`GET 'PORT' AND
`'PROTOCOL (TCP
`OR UDP)'.
`
`FIG. 9
`
`NOAC Ex. 1004 Page 10
`
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005 (cid:9)
`
`Sheet 10 of 18 (cid:9)
`
`US 6,839,751 B1
`
`1000 ------A
`
`PATTERN
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1001
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`1005-____
`
`•- (cid:9)
`
`1031
`-1004
`
`h INFO OUT
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS CONTRL N
`
`1031)
`
`1007
`
`EXTRACTION ENGINE
`(SLICER)
`
`1013—)
`
``7
`PARSER I (cid:9)
`/
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`MEMORY I
`
`1006--\ PATTERN I
`RECOGNITN (cid:9)
`ENGINE I (cid:9)
`(PRE)
`
`1008-\_____
`
`PACKET
`INPUT
`
`PARSER INPUT BUFFER
`MEMORY
`
`1012
`
`1021Th
`
`101
`
`1025
`
`PACKET
`START
`
`INPUT BUFFER I 1011-I
`INTERFACE
` CONTROL
`NEXT
`PACKET
`
`ANALYZER DATA REA
`INTERFACE
`
`CONTROL
`ANALYZER
`(cid:9) READY
`
`102
`1023
`
`FIG. 10
`
`1027
`
`NOAC Ex. 1004 Page 11
`
`(cid:9)
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 11 of 18 (cid:9)
`
`US 6,839,751 B1
`
`1103
`
`1115
`
`1118 1122m
`
`7- (cid:9)
`
`1107
`
`LOOKUP/
`UPDATE
`ENGINE
`(LUE)
`
`
`
`STATE
`PROCESSR
`INSTRUCN
`DATABASE
`(SPID)
`
`110
`
`/
`
`HOST
`BUS
`INTER-
`FACE
`(HIB)
`
`ANALYZER
`HOST
`INTERFACE
`AND
`CONTROL
`(ACIC)
`
`UNIFIED
`FLOW
`
`1-1/1BUFFER
`(UFKB)
`
`PARSER
`INTER-
`FACE
`
`1108
`
`CACHE
`
`1119 1123
`
`UNIFIED
`MEMORY
`CONTROL
`(UMC)
`
`MEMORY
`INTER-
`FACE
`
`..
`
`.
`
`
`
`
`
`STATE
`PROCESSR
`(SP)
`
`FLOW
`INSERTION/ (cid:9)
`DELETION
`ENGINE
`(FIDE) (cid:9)
`
`1110
`
`FIG. 11
`
`NOAC Ex. 1004 Page 12
`
`(cid:9)
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 12 of 18 (cid:9)
`
`US 6,839,751 B1
`
`1201
`
`/ UFKB ENTRY FOR
`
`PACKET WITH
`STATUS 'NEW'
`
`1202
`
`1200 ---A
`
`REQUEST NEXT
`BUCKET FROM
`CACHE
`
`1206
`
`1208
`
`1210—\
`
`SET UFKB FOR
`PACKET AS
`'DROP'
`
`_7-1203
`
`viv
`ACCESS
`CONVERSATION
`RECORD BIN
`i.
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`1204
`
`1205
`
`1207
`
`
`vf
`INSERT KEY AND HASH
`IN BUCKET, MARK 'USED
`WITH TIMESTAMP
`
`+
`,--1209
`COMPARE CURRENT BIN
`AND BUCKET RECORD
`KEY TO PACKET
`
`V
`MARK RECORD BIN AND
`BUCKET 'IN PROCESS'
`AND 'NEW IN CACHE
`
`1211
`
`1212— SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`i,
`
`1213
`
`FIG. 12
`
`NOAC Ex. 1004 Page 13
`
`(cid:9)
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 13 of 18 (cid:9)
`
`US 6,839,751 B1
`
`1301
`
`1300 ----.4 / UFKB ENTRY FOR
`
`PACKET WITH STATUS
`'NEW' OR 'FOUND'
`
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO
`VALUE FOUND IN UFKB ENTRY
`1
`FETCH INSTRUCTION FROM
`STATE PROCESSOR
`INSTRUCTION MEMORY
`
`V
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION
`
`SET STATE
`PROCESSOR
`INSTRUCTION
`POINTER TO
`VALUE FOUND IN
`CURRENT STATE
`
`NO
`
`DONE PROCESSING
`STATES FOR THIS
`PACKET?
`
`1302
`
`1303
`
`1304
`
`1305
`
`1307
`
`1308
`,--'--- 1310
`SAVE STATE
`PROCESSOR
`INSTRUCTION
`POINTER IN
`CURRENT FLOW
`RECORD
`
`NO
`
`YES
`
`DONE PROCESSING
`TATES FOR THIS FLOW?
`
`1309
`
`YES
`
`SET AND SAVE FLOW REMOVAL
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`FLOW RECORD
`
`1311
`
`1313
`
`FIG. 13
`
`NOAC Ex. 1004 Page 14
`
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 14 of 18 (cid:9)
`
`US 6,839,751 B1
`
`4 (cid:9)
`
`Is-
`c.o
`o
`d-
`
`t
`0
`Z illN 0
`
`Q ZmZ <i=
`iii (cid:9) }
`w
`NOW2
`?j_orcc
`<2<0
`ZEE 0-1-1- < Z
`
`•Tr o
`
`o
`0 .4-
`
`COICOI
`
`NOAC Ex. 1004 Page 15
`
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 15 of 18 (cid:9)
`
`US 6,839,751 B1
`
`CO
`0
`LO
`1-
`
`.zr
`0
`LO
`
`T-- I
`
`Do
`u) ocs 0
`E
`
`i
`
`\J]1 (cid:9)
`
`cc
`0
`o
`E 01 0°1
`2
`
`LO
`T—
`.
`
`0
`LL
`
`A
`
`
`
`CC (cid:9)
`w
`N
`>- co
`_1 c.
`< op
`Z
`
`cc
`W
`u) 51
`
`cc col < a_
`
`N
`0 (cid:9)
`in
`1—
`\ \ (cid:9)
`
`NOAC Ex. 1004 Page 16
`
`(cid:9)
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 16 of 18 (cid:9)
`
`US 6,839,751 B1
`
`1602
`
`0 - 3 Bytes
`
`offset C) - 11
`
`Dst MAC
`Dst MAC
`Src MAC
`Src MAC
`
`A.- -1600
`
`1604
`
`1608 r
`
`Dst Hash (2)
`
`1612
`
`1614
`
`Dst MAC (6)
`
`Src MAC (6)
`
`Src Hash (2)
`
`2 Offs
`et = 12
`
`FIG. 16
`
`NOAC Ex. 1004 Page 17
`
`(cid:9)
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005 (cid:9)
`
`Sheet 17 of 18 (cid:9)
`
`US 6,839,751 B1
`
`1702
`
`1704
`
`offset ! (cid:9)
`12 to 131
`
`Type
`
`//////////
`
`1708 (cid:9)
`
`1710
`
`Type (2)
`Hash t1)
`
`Offset = 14
`
`1706
`
`1700
`
`FIG. 17A
`
`1712
`
`L3 to
`[L3 +
`(IHL / 4)
`- 1]
`
`MEE t
`A
`WIEZZEIEMEELM
`Protocol MAW= -
`r (cid:9)
`Src Address
`Dst Address
`'Si 111127
`
`IDP = 0x0600*
`IP = 0x0800*
`CHAOSNET = 0x0804
`ARP = 0x0806
`VIP = OxOBAD*
`VLOOP = OxOBAE
`VECHO = OxOBAF
`NETBIOS-3COM = Ox3C00 -
`0x3COD#
`DEC-MOP = 0x6001
`DEC-RC = 0x6002
`DEC-DRP = 0x6003*
`DEC-LAT = 0x6004
`DEC-DIAG = 0x6005
`DEC-LAVC = 0x6007
`RARP = 0x8035
`ATALK = 0x809B*
`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
`
`1750
`
`Dst Address
`Dst Hash (2)
`Src Address
`Src Hash (2)
`
`Protoc of (1)
`
`L4 Off et = L3 + (IHU4)
`
`FIG. 17B
`
`* L4 Decoding
`# L3 Re-Decoding
`
`NOAC Ex. 1004 Page 18
`
`(cid:9)
`(cid:9)
`
`
`U.S. Patent (cid:9)
`
`Jan. 4, 2005
`
`Sheet 18 of 18
`
`US 6,839,751 B1
`
`PROTOCOL
`TYPE (ICs
`
`A-1800
`
`1802-2
`1802-1
`
`1802-M
`
`FIG. 18A
`
`/ 870
`
`O
`0
`O
`0
`cc
`
`FIG. 18B
`
`NOAC Ex. 1004 Page 19
`
`(cid:9)
`(cid:9)
`
`
`1
`RE-USING INFORMATION FROM DATA
`TRANSACTIONS FOR MAINTAINING
`STATISTICS IN NETWORK MONITORING
`
`CROSS-REFERENCE TO RELATED (cid:9)
`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/608,237 for
`METHOD AND APPARATUS FOR MONITORING
`TRAFFIC IN A NETWORK, to inventors Dietz, et al., filed
`Jun. 30, 2000, and incorporated herein by reference.
`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, 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, 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, and incorporated herein by reference.
`
`FIELD OF INVENTION
`
`The present invention relates to computer networks, spe-
`cifically to the real-time elucidation of packets communi-
`cated within a data network, including classification accord-
`ing to protocol and application program.
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material that is subject to copyright protection. The
`copyright owner has no objection to the facsimile reproduc-
`tion by anyone of the patent document or the patent
`disclosure, as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`BACKGROUND
`
`There has long been a need for network activity monitors.
`This need has become especially acute, however, given the 55
`recent popularity of the Internet and other interconnected
`networks. In particular, there is a need for a real-time
`network monitor that can provide details as to the applica-
`tion programs being used. Such a monitor should enable
`non-intrusive, remote detection, characterization, analysis, 60
`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 65
`(e.g., http, ftp, H.323, VPN, etc.), the application/use within
`the protocol (e.g., voice, video, data, real-time data, etc.),
`
`US 6,839,751 B1
`
`2
`and an end user's pattern of use within each application or
`the application context (e.g., options selected, service
`delivered, duration, time of day, data requested, etc.). Also,
`the network monitor should not be reliant upon server
`resident information such as log files. Rather, it should allow
`a user such as a network administrator or an Internet service
`provider (ISP) the means to measure and analyze network
`activity objectively; to customize the type of data that is
`collected and analyzed; to undertake real time analysis; and
`to receive timely notificatior of network problems.
`Related and incorporated by reference U.S. patent appli-
`cation Ser. No. 09/607,237 for METHOD AND APPARA-
`TUS FOR MONITORING TRAFFIC IN A NETWORK, to
`inventors Dietz, et al, describes a network monitor that
`includes carrying out protocol specific operations on indi-
`vidual packets including extracting information from header
`fields in the packet to use for building a signature for
`identifying the conversational flow of the packet and for
`recognizing future packets as belonging to a previously
`encountered flow. A parser subsystem includes a parser for
`recognizing different patterns in the packet that identify the
`protocols used. For each protocol recognized, a slicer
`extracts important packet elements from the packet. These
`form a signature (i.e., key) for the packet. The slicer also
`preferably generates a hash for rapidly identifying a flow
`that may have this signature from a database of known
`flows.
`The flow signature of the packet, the hash and at least
`some of the payload are passed to an analyzer subsystem. In
`a hardware embodiment, the analyzer subsystem includes a
`unified flow key buffer (UFKB) for receiving parts of
`packets from the parser subsystem and for storing signatures
`in process, a lookup/update engine (LUE) to lookup a
`database of flow records for previously encountered con-
`versational flows to determine whether a signature is from
`an existing flow, a state processor (SP) for performing state
`processing, a flow insertion and deletion engine (FIDE) for
`inserting new flows into the database of flows, a memory for
`storing the database of flows, and a cache for speeding up
`access to the memory containing the flow database. The
`LUE, SP, and FIDE are all coupled to the UFKB, and to the
`cache.
`Each flow-entry includes one or more statistical measures,
`e.g., the packet count related to the flow, the time of arrival
`of a packet, the time differential.
`In the preferred hardware embodiment, each of the LUE,
`state processor, and FIDE operate independently from the
`other two engines. The state processor performs one or more
`operations specific to the state of the flow.
`It is advantageous to collect statistics on packets passing
`through a point in a network rather than to simply count each
`and every packet. By maintaining statistical measures in the
`flow-entries related to a conversational flow, embodiments
`of the present invention enable specific metrics to be col-
`lected in real-time that otherwise would not be possible. For
`example, it is desirable to maintain metrics related to
`bi-directional conversations based on the entire flow for
`each exchange in the conversation. By maintaining the state
`of flow, embodiments of the present invention also enable
`certain metrics related to the states of flows to be deter-
`mined.
`Most prior-art network traffic monitors that use statistical
`metrics collect only end-point and end-of-session related
`statistics. Examples of such commonly used metrics include
`packet counts, byte counts, session connection time, session
`timeouts, session and transport response times and others.
`
`NOAC Ex. 1004 Page 20
`
`
`
`US 6,839,751 B1
`
`3
`All of these deal with events that can be directly related to
`an event in a single packet. These prior-art systems cannot
`collect some important performance metrics that are related
`to a complete sequence of packets of a flow or to several
`disjointed sequences of the same flow in a network.
`Time based metrics on application data packets are impor-
`tant. Such metrics could be determined if all the timestamps
`and related data could be stored and forwarded for later
`analysis. However when faced with thousands or millions of
`conversations per second on ever faster networks, storing all
`the data, even if compressed, would take too much
`processing, memory, and manager down load time to be
`practical.
`Thus there is a need for maintaining and reporting time-
`base metrics from statistical measures accumulated from
`packets in a flow.
`Network data is properly modeled as a population and not
`a sample. Thus, all the data needs to be processed. Because
`of the nature of application protocols, just sampling some of
`the packets may not give good measured related to flows.
`Missing just one critical packet, such as one the specified an
`additional port that data will be transmitted on, or what
`application will be run, can cause valid data to be lost.
`Thus there is also a need for maintaining and reporting
`time-base metrics from statistical measures accumulated
`from every packet in a flow.
`There also is a need to determine metrics related to a
`sequence of events. A good example is relative jitter. Mea-
`suring the time from the end of one packet in one direction
`to another packet with the same signature in the same
`direction collects data that relates normal jitter. This type of
`jitter metric is good for measuring broad signal quality in a
`packet network. However, it is not specific to the payload or
`data item being transported in a cluster of packets.
`Using the state processing described herein, because the
`state processor can search for specific data payloads,
`embodiments of monitor 300 can be programmed to collect
`the same jitter metric for a group of packets in a flow that are
`all related to a specific data payload. This allows the
`inventive system to provide metrics more focused on the
`type of quality related to a set of packets. This in general is
`more desirable than metrics related to single packets when
`evaluating the performance of a system in a network.
`Specifically, the monitor system 300 can be programmed
`to maintain any type of metric at any state of a conversa-
`tional flow. Also the system 300 can have the actual statistics
`programmed into the state at any point. This enables
`embodiments of the monitor system to collect metrics
`related to network usage and performance, as well as metrics
`related to specific states or sequences of packets.
`Some of the specific metrics that can be collected only
`with states are events related to a group of traffic in one
`direction, events related to the status of a communication
`sequence in one or both directions, events related to the
`exchange of packets for a specific application in a specific
`sequence. This is only a small sample of the metrics that
`requires an engine that can relate the state of a flow to a set
`of metrics.
`In addition, because the monitor 300 provides greater
`visibility to the specific application in a conversation or flow,
`the monitor 300 can be programmed to collect metrics that
`may be specific to that type of application or service. In other
`word, if a flow is for an Oracle Database server, an embodi-
`ment of monitor 300 could collect the number of packets
`required to complete a transaction. Only with both state and
`application classification can this type of metric be derived
`from the network.
`
`5
`
`4
`Because the monitor 300 can be programmed to collect a
`diverse set of metrics, the system can be used as a data
`source for metrics required in a number of environments. In
`particular, the metrics may be used to monitor and analyze
`the quality and performance of traffic flows related to a
`specific set of applications. Other implementation could
`include metrics related to billing and charge-back for spe-
`cific traffic flow and events with the traffic flows. Yet other
`implementations could be programmed to provide metrics
`10 useful for troubleshooting and capacity planning and related
`directly to a focused application and service.
`
`SUMMARY
`Another aspect of the invention is determining quality of
`is service metrics based on each and every packet. A method
`of and monitor apparatus for analyzing a flow of packets
`passing through a connection point on a computer network
`are disclosed that may include such quality of service
`metrics. The method includes receiving a packet from a
`20 packet acquisition device, and looking up a flow-entry
`database containing flow-entries for previously encountered
`conversational flows. The looking up to determine if the
`received packet is of an existing flow. Each and every packet
`is processed. If the packet is of an existing flow, the method
`25 updates the flow-entry of the existing flow, including storing
`one or more statistical measures kept in the flow-entry. If the
`packet is of a new flow, the method stores a new flow-entry
`for the new flow in the flow-entry database, including
`storing one or more statistical measures kept in the flow-
`30 entry. The statistical measures are used to determine metrics
`related to the flow. The metrics may be base metrics from
`which quality of service metrics are determined, or may be
`the quality of service metrics.
`
`35
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Although the present invention is better understood by
`referring to the detailed preferred embodiments, these
`should not be taken to limit the present invention to any
`specific embodiment because such embodiments are pro-
`vided only for the purposes of explanation. The
`embodiments, in turn, are explained with the aid of the
`following figures.
`FIG. 1 is a functional block diagram of a network embodi-
`ment of the present invention in which a monitor is con-
`nected to analyze packets passing at a connection point.
`FIG. 2 is a diagram representing an example of some of
`the packets and their formats that might be exchanged in
`starting, as an illustrative example, a conversational flow
`between a client and server on a network being monitored
`50 and analyzed. A pair of flow signatures particular to this
`example and to embodiments of the present invention is also
`illustrated. This represents some of the possible flow signa-
`tures that can be generated and used in the process of
`analyzing packets and of recognizing the particular server
`55 applications that produce the discrete application packet
`exchanges.
`FIG. 3 is a functional block diagram of a process embodi-
`ment of the present invention that can operate as the packet
`monitor shown in FIG. 1. This process may be implemented
`60 in software or hardware.
`FIG. 4 is a flowchart of a high-level protocol language
`compiling and optimization process, which in one embodi-
`ment may be used to generate data for monitoring packets
`according to versions of the present invention.
`FIG. 5 is a flowchart of a packet parsing process used as
`part of the parser in an embodiment of the inventive packet
`monitor.
`
`40
`
`45
`
`65 (cid:9)
`
`NOAC Ex. 1004 Page 21
`
`
`
`US 6,839,751 B1
`
`5
`FIG. 6 is a flowchart of a packet element extraction
`process that is used as part of the parser in an embodiment
`of the inventive packet monitor.
`FIG. 7 is a flowchart of a flow-signature building process
`that is used as part of the parser in the inventive packet
`monitor.
`FIG. 8 is a flowchart of a monitor lookup and update
`process that is used as part of the analyzer in an embodiment
`of the inventive packet monitor.
`FIG. 9 is a flowchart of an exemplary Sun Microsystems
`Remote Procedure Call application than may be recognized
`by the inventive packet monitor.
`FIG. 10 is a functional block diagram of a hardware parser
`subsystem including the pattern recognizer and extractor
`that can form part of the parser module in an embodiment of
`the inventive packet monitor.
`FIG. 11 is a functional block diagram of a hardware
`analyzer including a state processor that can form part of an
`embodiment of the inventive packet monitor.
`FIG. 12 is a functional block diagram of a flow insertion
`and deletion engine process that can form part of the
`analyzer in an embodiment of the inventive packet monitor.
`FIG. 13 is a flowchart of a state processing process that
`can form part of the analyzer in an embodiment of the
`inventive packet monitor.
`FIG. 14 is a simple functional block diagram of a process
`embodiment of the present invention that can operate as the
`packet monitor shown in FIG. 1. This process may be
`implemented in software.
`FIG. 15 is a functional block diagram of how the packet
`monitor of FIG. 3 (and FIGS. 10 and 11) may operate on a
`network with a processor such as a microprocessor.
`FIG. 16 is an example of the top (MAC) layer of an
`Ethernet packet and some of the elements that may be
`extracted to form a signature according to one aspect of the
`invention.
`FIG. 17A is an example of the header of an Ethertype type
`of Ethernet packet of FIG. 16 and some of the elements that
`may be extracted to form a signature according to one aspect
`of the invention.
`FIG. 17B is an example of an IP packet, for example, of
`the Ethertype packet shown in FIGS. 16 and 17A, and some
`of the elements that may be extracted to form a signature
`according to one aspect of the invention.
`FIG. 18A is a three dimensional structure that can be used
`to store elements of the pattern, parse and extraction data-
`base used by the parser subsystem in accordance to one
`embodiment of the invention.
`FIG. 18B is an alternate form of storing elements of the
`pattern, parse and extraction database used by the parser
`subsystem in accordance to another embodiment of the
`invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`Note that this document includes hardware diagrams and
`descriptions that may include signal names. In most cases,
`the names are sufficiently descriptive, in other cases how-
`ever the signal names are not needed to understand the
`operation and practice of the invention.
`Operation in a Network
`FIG. 1 represents a system embodiment of the present
`invention that is referred to herein by the general reference
`numeral 100. The system 100 has a computer network 102
`
`5
`
`10
`
`15
`
`6
`that communicates packets (e.g., IP datagrams) between
`various computers, for example between the clients 104-107
`and servers 110 and 112. The network is shown schemati-
`cally as a cloud with several network nodes and links shown
`in the interior of the cloud. A monitor 108 examines the
`packets passing in either direction past its connection point
`121 and, according to one aspect of the invention, can
`elucidate what application programs are associated with
`each packet. The monitor 108 is shown examining packets
`(i.e., datagrams) between the network interface 116 of the
`server 110 and the network. The monitor can also be placed
`at other points in the network, such as connection point 123
`between the network 102 and the interface 118 of the client
`104, or some other location, as indicated schematically by
`connection point 125 somewhere in network 102. Not
`shown is a network packet acquisition device at the location
`123 on the network for converting the physical information
`on the network into packets for input into monitor 108. Such
`packet acquisition devices are common.
`Various protocols may be employed by the network to
`establish and maintain the required communication, e.g.,
`TCP/IP, etc. Any network activity—for example an appli-
`cation program run by the client 104 (CLIENT 1) commu-
`nicating with another running on the server 110 (SERVER
`2)—will produce an exchange of a sequence of packets over
`network 102 that is characteristic of the respective programs
`and of the network protocols. Such characteristics may not
`be completely revealing at the individual packet level. It
`may require the analyzing of many packets by the monitor
`30 108 to have enough information needed to recognize par-
`ticular application programs. The packets may need to be
`parsed then analyzed in the context of various protocols, for
`example, the transport through the application session layer
`protocols for packets of a type