(12) United States Patent
`Dietz et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,839,751 B1
`Jan. 4, 2005
`
`US006839751B1
`
`(54) RE-USING INFORMATION FROM DATA
`TRANSACTIONS FOR MAINTAINING
`
`STATISTICS IN NETWORK MONITORING
`
`(75) IIIVGIIIOI‘SZ Russell S. DiEFZ, San 1056, CA (US);
`Joseph R. Malxner, Aptos, CA (US);
`A d
`A. K
`h
`L'ttl t
`Cg
`Oppen aver’ 1 eon’
`
`_
`_
`(73) AsslgneeZ Hl/fns Inc» L05 Gat0s> CA (Us)
`
`(*) Notlce:
`
`SubJeCt_tO any dlsclalmer: the term of thls
`Patent 15 extended or adlusted under 35
`U.S.C. 154(1)) by 728 days-
`
`(21) App1_ NO_; 09/608,126
`
`(22) Filedi
`
`JllIl- 30, 2000
`
`Related US. Application Data
`(60) Provisional application No. 60/141,903, ?led on Jun. 30,
`1999'
`(51) Int. Cl.7 ............................................ .. G06F 15/173
`
`(58) Field of Search ............................... .. 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
`379/9 03
`4 972 453 A * 11/1990 Daniel et al
`709/2'22
`5’535’338 A * 7/1996 Krause et a1:
`5:703:877 A 12/1997 Nuber et a1_ ___________ __ 370/395
`5,720,032 A * 2/1998 Picazo, Jr, et a1, ,,
`709/250
`5,761,429 A * 6/1998 Thompson . . . . . . . . .
`. . . .. 709/224
`
`- - - -- 709/223
`5,799,154 A * 8/1998 Kuriyan - - - - - - -
`- - - ~~ 370/401
`5,802,054 A i 9/ 1998 Bellenger - - - - - - -
`57850388 A 12/1998 Anderson et a1‘ """"" " 370/252
`5,892,754 A
`4/1999 Kompella et al. ........ .. 370/236
`6 097 699 A * 8/2000 Chen et a1
`37O/231
`6’115’393 A * 9/2000 Engel et ai_
`37O/469
`6,269,330 B1 * 7/2001 Cidon et al. .
`..... .. 704/43
`6,279,113 B1 * 8/2001 Vaidya .............. .. 713/201
`6,282,570 B1 * 8/2001 Leung et a1. ............. .. 709/224
`
`6,330,226 B1 * 12/2001 Chapman et a1. ......... .. 370/232
`6,363,056 B1 * 3/2002 Beigi et a1. ..... ..
`370/252
`6,381,306 B1 * 4/2002 Lawson et al.
`379/32
`6,424,624 B1 * 7/2002 Galand et al.
`370/231
`6453 345 B2 * 92002 T k t
`l.
`.... ..
`709 224
`6:625:657 B1 * 92003 P5101135
`709/237
`6,651,099 B1 * 11/2003 DietZ et a1. ............... .. 709/224
`OTHER PUBLICATIONS
`
`NOV94: Packet Filtering in the SNMP Remote Monitor ;
`WWW.skrymir.com/dobbs/articles/l994/9411/9411h/
`9411h.htm.*
`GTrace—A Graphical Traceroute Tool authored by Ram
`Periakaruppan, Evi Nemeth ; http://WWW.caida.org/out
`reach/papers/l999/GTrace/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.*
`*
`_
`_
`cued by exammer
`Primary Examiner—Thong Vu
`(74) Attorney, Agent, or Firm—D0v Rosenfeld; Inventek
`
`A method of and monitor apparatus for analyzing a How 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 ?oW-entry
`database containing ?ow-entries for previously encountered
`conversational ?oWs. The looking up to determine if the
`received packet is of an existing ?oW. Each and every packet
`is processed. If the packet is of an existing ?oW, the method
`updates the ?oW-entry of the existing ?oW, including storing
`one or more statistical measures kept in the ?oW-entry. 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
`storing one or more statistical measures kept in the 110w
`entry. The statistical measures are used to determine metrics
`.
`.
`related to the 110w. The metrics may be base metrics from
`Which quality of service metrics are determined, or may be
`the 91121110’ 0f servlce metrlcs
`
`21 Claims, 18 Drawing Sheets
`
`DATA COMMUNICATIONS
`NETWORK
`
`102
`
`118
`
`_\104
`
`@ a @ 112
`
`Petitioners' EX1002 Page 1
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 1 of 18
`
`US 6,839,751 B1
`
`100
`
`10s
`_/
`CLIENT 4
`\ ANALYZER
`107
`
`116
`_/
`
`CLIENT 3
`W 106
`
`SERVER 2
`\110
`
`121
`
`DATA COMMUNICATIONS
`NETWORK
`
`102
`
`125
`
`SERVER 2
`W
`112
`
`118
`123
`J
`105
`CLIENT 2 J CLIENT 1 w
`104
`
`FIG. 1
`
`Petitioners' EX1002 Page 2
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 2 of 18
`
`US 6,839,751 B1
`
`
`
`Nm_m_>mm_mzo:<o_._n_n_<
`
`.389E3mu
`
`8%.
`
`Emu8%mmw5%8%
`
`Petitioners‘ EX1002 Page 3
`
`Petitioners' EX1002 Page 3
`
`
`
`
`

`
`U.S. Patent
`U.S. Patent
`
`«mm_Elmmmmmi
`F\Y_IIIIIIIIIIIIIIIIII1
`
`m_m<m_<»<os_oE_o:<wmm_>zoo7%__%«”__»m_%m_u_oJ_zmmE<n_
`
`Ex..>>O|_n_._
`
`ZO_._.<S_m_On_Z_
`
`aJ
`Jan. 4,2005
`
`u_OOO._.OW_n_2,_m:<onS4IH...1
`
`_.MEGS.m:<5woz<0___>>O:_n_
`
`
`
`o:<o:_wm<._oomoommZO_._.<O_...=._.ZmO_zo_5<ExmM_z>>ozv_
`_m_w<m<»<o
`
`Sheet 3 of 18
`
`
`t_ZO_._.<N_:_<Z_n_|I_w_zEo:_mm<._o%__
`0_mommmoomm
`
`3en
`
`8_mm<m<»<o_n_z<H_to,zo_5:Emz__mm:_n_s_oo
`
`US 6,839,751 B1
`1B
`
`m_IIIIIIIIIIIIIIIIIIIIIIIIIIII_99_an_3_mm_N>._<z<_8,_.zoEEm_n_o_6ozmmmoomm
`
`
`
` mo<:oz<._S__mm_><._o_E_ommoU_.s_<mw<»<o______mam__m_m_N_s__Eo
`
`momoomm
`
`EEV
`
`m>>O._.._noz>>ozv_em;
`
`
`
`
`
`
`%xoo._M592:o._5m5<Exmmuzwoomm_n_z<mN>._<z<
`
`wow
`
`05
`
`Petitioners‘ EX1002 Page 4
`
`Petitioners' EX1002 Page 4
`
`
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 4 0f 18
`
`US 6,839,751 B1
`
`401
`
`HIGH LEVEL
`PACKET
`DECODING
`
`S 404
`
`405
`
`GENERATE
`GENERATE
`PACKET
`PAPQgSLD
`STATE
`COMPILE
`"—-DEsORIPTIONs—’ INSTRUCTIONS
`EXTRACT
`AND
`OPERAT'ONS
`OPERATIONS
`
`Q 403
`
`406 7/ ATI'ERN, PARSE
`AND
`EXTRACTION
`_____/ ( 408
`DATABASE
`PIRAEIG
`
`—> SUBSYSTEM
`MEMORY
`
`409 3
`8g“:
`
`N TRU TI N
`DATABASE
`MEMORY
`
`407
`
`STATE
`PROCESSOR
`INsTRuOTION
`DATABASE
`
`‘
`
`——>% 410
`
`FIG. 4
`
`Petitioners' EX1002 Page 5
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 5 0f 18
`
`US 6,839,751 B1
`
`501
`
`502
`
`503 \/ LOAD PACKET
`
`COMPONENT
`
`504
`
`NO
`
`512
`
`BUILD
`PACKET
`KEY
`
`YES
`
`FETCH NODE AND
`PROCESS FROM
`PATTERNS Q 505
`
`513
`
`NEXT
`PACKET ?_
`COMPONENT 511
`A
`
`MORE
`PATTERN
`NODES?
`
`506
`
`APPLY NODE AND
`PROCESS TO
`507 P
`COMPONENT
`
`XT
`PATTERN
`NODE
`
`NO
`
`500
`
`508
`
`YES
`
`EXTRACT
`ELEMENTS
`
`FIG. 5
`
`Petitioners' EX1002 Page 6
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 6 of 18
`
`US 6,839,751 B1
`
`601
`
`PACKET
`COMPONENT AND
`PATTERN NODE
`
`602
`
`LOAD PACKET
`’ COMPONENT
`
`610 3
`
`LOAD KEY
`BUFFER
`
`FETCH EXTRACTION
`AND PROCEss FROM
`PATTERNS
`
`605
`
`NO
`
`606
`
`ORE EXTRACTIO \
`ELEMENTS?
`
`NEXT
`NO, PACKET \C 609
`COMPONENT
`A
`
`611
`
`607 2/ APPLY EXTRACTION
`PROCEss TO
`COMPONENT
`
`MORE TO
`EXTRACT?
`
`608
`
`\
`600
`
`FIG. 6
`
`Petitioners' EX1002 Page 7
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 7 of 18
`
`US 6,839,751 B1
`
`701
`
`EY BUFFER AND
`PATTERN NODE
`
`702
`
`LOAD PATTERN
`703 V NODE ELEMENT ‘—
`
`704
`
`MORE PATTERN
`NODES?
`
`\
`
`I OUTPUT TO
`ANALYZER
`
`YES
`Y
`HASH KEY BUFFER
`ELEMENT FROM \5 705
`PATTERN NODE
`l
`
`f PACK KEY & HASH
`706
`
`i
`
`NEXT PACKET
`f COMPONENT
`
`707
`
`FIG. 7
`
`709
`
`\70o
`
`Petitioners' EX1002 Page 8
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 8 0f 18
`
`US 6,839,751 B1
`
`801
`
`UFKB ENTRY FOR
`PACKET
`
`802
`
`800 \
`
`COMPUTE CONVERSATION
`RECORD BIN FROM HASH
`
`I
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`5 806
`
`805
`
`ORE BUCKET
`IN THE BIN?
`
`SET UFKB FOR
`PACKET AS 'NEW'
`
`COMPARE CURRENT BIN
`f' 807
`AND BUCKET RECORD KEY
`TO PACKET
`
`NEXT BUCKET
`
`KEY MATCH?
`
`808
`
`Q 809
`
`YES
`
`MARK RECORD BIN AND
`BUCKET 'IN PROCESSI IN
`CACHE AND TIMESTAMP
`
`[-810
`
`I
`
`SET UFKB FOR PACKET
`AS 'FOUND'
`
`I
`
`UPDATE STATISTICS FOR
`RECORD IN CACHE
`
`813mb
`
`6.8
`
`Petitioners' EX1002 Page 9
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 9 0f 18
`
`US 6,839,751 B1
`
`901
`
`902
`
`ORTMAPP '
`
`‘ NNOUNCME
`ORTMAPPE "
`
`EXTRACT PROGRAM
`903 X GET ‘PROGRAM’,
`'VERSION‘, 'PORT' AND
`‘PROTOCOL (TCP OR
`UDP)
`
`f
`
`1
`
`CREATE SERVER STATI
`
`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.
`
`RPC
`BIND LOOKU '
`REQUEST
`
`g 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
`
`906 —\
`EXTRACT
`PROGRAM
`
`GET ‘PORT’ AND
`IPROTOCOL (TCP
`OR UDP)‘.
`
`/
`900
`
`K'- 905
`LOOKUP REQUEST
`FIND ‘PROGRAM‘
`AND ‘VERSION’
`WITH LOOKUP OF
`SOURCE NETWORK
`ADDRESS.
`
`U
`
`FIG. 9
`
`Petitioners' EX1002 Page 10
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 10 of 18
`
`US 6,839,751 B1
`
`PATTERN
`RECOGNITION
`DATABASE
`MEMORY
`
`100
`
`1°01
`
`EXTRACTION
`OPERATIONS
`DATABASE
`MEMORY
`
`100K
`
`1004
`
`INFO OUT
`HOST INTERFACE MULTIPLEXR & CONTROL REGISTERS CONTRL N
`
`PATTERN
`RECOGNITN
`ENGINE
`(PRE)
`
`100
`
`100
`
`EXTRACTION ENGINE
`(sLIOER)
`
`1031
`
`1007
`
`1013
`
`PA KET
`INPUT
`
`PARSER INPUT BUFFER
`MEMORY
`
`PARSER
`OUTPUT PACKET KEY
`BUFFER AND PAYLOA
`MEMORY
`
`INPUT BUFFER 1011
`INTERFACE
`CONTROL
`
`ANALYZER DATA REA I)
`INTERFACE
`CONTROL
`
`ANALYZER
`READY
`
`1027
`
`‘
`
`V
`
`PACKET
`
`102
`1023
`
`Petitioners' EX1002 Page 11
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 11 0f 18
`
`US 6,839,751 B1
`
`LOOKUP/
`UPDATE
`
`DATABASE
`
`PROCESSR
`(S
`
`PARSER
`INTER- M
`FACE
`
`UNIFIED
`MEMORY
`M
`CONTROL
`(UMC)
`
`MEMORY
`INTER
`FACE
`
`Petitioners' EX1002 Page 12
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 12 0f 18
`
`US 6,839,751 B1
`
`1201
`
`/
`
`UFKB ENTRY FOR
`PACKET WITH
`STATUS 'NEW'
`
`#1202
`
`ACCESS
`CONVERSATION
`RECORD BIN
`
`I
`
`REQUEST RECORD BIN/
`BUCKET FROM CACHE
`
`REQUEST NEXT
`BUCKET FROM
`CACHE
`
`I
`
`1206f
`
`1 208
`
`NO
`
`YES
`
`SET UFKB FOR
`PACKET AS
`‘DROP’
`
`INSERT KEY AND HASH
`IN BUCKET, MARK IUSED
`WITH TIMESTAMP
`+
`COMPARE CURRENT BlN/_1209
`AND BUCKET RECORD
`KEY TO PACKET
`I
`MARK RECORD BIN AND
`f1211
`BUCKET IIN PROCESS'
`AND 'NEW' IN CACHE
`
`I
`12121 SET INITIAL STATISTICS
`FOR RECORD IN CACHE
`
`1213
`
`P
`
`FIG. 12
`
`Petitioners' EX1002 Page 13
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 13 0f 18
`
`US 6,839,751 B1
`
`Q\/ 1301
`
`1300 \A /
`UFKB ENTRY FOR
`PACKET WITH STATUS
`'NEW' OI1'FOUND'
`SET STATE PROCESSOR
`INSTRUCTION POINTER TO
`I/ALUE FOUND IN UFKB ENTRY
`
`1302
`
`FETCH INSTRUCTION FROM
`STATE PROCESSOR
`INSTRUCTION MEMORY
`
`I
`
`PERFORM OPERATION BASED
`ON THE STATE INSTRUCTION
`
`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?
`
`1 307
`
`DONE PROCESSING
`TATES FOR THIS FLOW’?
`
`1309
`
`SET AND SAVE FLOW REMOVAL
`STATE PROCESSOR
`INSTRUCTION IN CURRENT
`FLOW RECORD
`
`,éJms
`
`FIG. 13
`
`Petitioners' EX1002 Page 14
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 14 of 18
`
`US 6,839,751 B1
`
`4
`
`wmilw F|Oz
`
`mm;
`
`Petitioners' EX1002 Page 15
`
`

`
`U.S. Patent
`U.S. Patent
`
`Jan. 4,2005
`24,
`J
`
`m8232
`
`._.m_v_O<n_
`
`«mm
`
`m_m<m<»<n_
`
`
`
`mfiam.mN>._<z<mmmmé
`
`mom_.
`
`5>mo_>m__>_m50:
`
`Sheet 15 of 18
`51Mh
`
`US 6,839,751 B1
`1B157.,
`6SU
`
`9I&m_.G_u_
`
`P
`
`om<omm_o<u_mmPz_Mv_mo>>Ez
`
`N2
`
`Sam
`
`mo:zos_
`
`—.N—
`
`Petitioners‘ EX1002 Page 16
`
`Petitioners' EX1002 Page 16
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 16 of 18
`
`US 6,839,751 B1
`
`1602
`x
`“
`
`1
`
`0 - 3 Bytes
`
`Dst MAC
`
`k‘- 1600
`
`offset 0 - 11 \ Dst MAC Src MAC ~//1604
`1
`Src MAC
`’
`/
`
`\
`
`/—__)% 1606
`1608 \\
`Dst MAC (6)
`//
`_Dst Hash (2}
`1610
`161i
`//
`1614 _Src Hash (2}
`\L2 Off set = 12
`
`Src MAC (6)
`
`FIG. 16
`
`Petitioners' EX1002 Page 17
`
`

`
`U.S. Patent
`
`Jan. 4, 2005
`
`Sheet 17 of 18
`
`US 6,839,751 B1
`
`1702
`
`1704
`
`1
`offset
`12to1s Wllllllfllli
`
`X
`
`1706
`
`1708
`
`Type (2)
`Hash 1
`
`e*=14
`
`FIG. 17A
`
`IDP = OxO600*
`IP = OX0800*
`CHAOSNET = 0xO804
`ARP = 0xO806
`VIP = 0x0BAD*
`VLOOP = OXOBAE
`VECHO = OXOBAF
`NETBIOS-3COM = 0x3C00 -
`OX3COD#
`DEC-MOP = 0X5001
`DEC-RC = 0x6002
`DEC-DRP = 0x6003*
`DEC-LAT = 0X6004
`DEC-DIAG = 0x6005
`DEC-LAVC = 0X6007
`RARP = 0x8035
`ATALK = 0X809B*
`VLOOP = 0x80C4
`VECHO = 0X80C5
`SNA-TH = 0X8OD5*
`ATALKARP = 0x80F3
`IPX = Ox8137*
`SNMP = 0x814C#
`IPV6 = OX86DD*
`LOOPBACK = 0x9000
`
`j
`1712
`
`
`moI(5,3;, 4
`
`-1]
`
`
`
`Apple = 0x080007
`* L3 Decoding
`# L5 Decoding
`
`1752
`
`
`
`rIIi;'i.IIir»'.r.-:.=*.-".='ii;»:'.'.='.:l';~'II»1
`
`7IIIII£:Wi"ifiwiiifilflllllllllllfl
`
`
`
`
`
`Dst Hash (2)
`Src Address
`
`Src Hash (2)
`
`cm
`
`FIG. 17B
`
`L4 Offet = L3 + (IHL/4)
`
`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
`
`# L3 Re-Decoding
`
`* L4 Decoding
`
`Petitioners‘ EX1002 Page 18
`
`Petitioners' EX1002 Page 18
`
`

`
`U.S. Patent
`
`Jan. 4,2005
`
`Sheet 18 of 18
`
`US 6,839,751 B1
`
`PROTOCOL
`
`
`
`IPQZmj DAME
`
`FIG. 18A
`
`870
`
`r1850
`
`GAME "6
`
`FIG. 18B
`
`
`
`UT NUM L
`
`__—> $5
`/ E5
`
`Petitioners' EX1002 Page 19
`
`

`
`US 6,839,751 B1
`
`1
`RE-USING INFORMATION FROM DATA
`TRANSACTIONS FOR MAINTAINING
`STATISTICS IN NETWORK MONITORING
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`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 ?les. 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 noti?catior of netWork problems.
`Related and incorporated by reference US. 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 speci?c operations on indi
`vidual packets including extracting information from header
`?elds in the packet to use for building a signature for
`identifying the conversational How of the packet and for
`recogniZing future packets as belonging to a previously
`encountered ?oW. 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 How
`that may have this signature from a database of knoWn
`?oWs.
`The How 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
`uni?ed ?oW 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 How records for previously encountered con
`versational ?oWs to determine Whether a signature is from
`an existing ?oW, a state processor (SP) for performing state
`processing, a How insertion and deletion engine (FIDE) for
`inserting neW ?oWs into the database of ?oWs, a memory for
`storing the database of ?oWs, and a cache for speeding up
`access to the memory containing the How database. The
`LUE, SP, and FIDE are all coupled to the UFKB, and to the
`cache.
`Each ?oW-entry includes one or more statistical measures,
`e.g., the packet count related to the ?oW, 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 speci?c to the state of the ?oW.
`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
`?oW-entries related to a conversational ?oW, embodiments
`of the present invention enable speci?c 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 ?oW for
`each exchange in the conversation. By maintaining the state
`of ?oW, embodiments of the present invention also enable
`certain metrics related to the states of ?oWs 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.
`
`This application claims the bene?t of US. Provisional
`Patent Application Ser. No. 60/141,903 for METHOD AND
`APPARATUS FOR MONITORING TRAFFIC IN A NET
`WORK to inventors DietZ, et al., ?led Jun. 30, 1999, the
`contents of Which are incorporated herein by reference.
`This application is related to the following US. patent
`applications, each ?led concurrently With the present
`application, and each assigned to Apptitude, Inc., the
`assignee of the present invention:
`US. patent application Ser. No. 09/608,237 for
`METHOD AND APPARATUS FOR MONITORING
`TRAFFIC IN ANETWORK, to inventors DietZ, et al., ?led
`Jun. 30, 2000, and incorporated herein by reference.
`US. patent application Ser. No. 09/609,179 for PRO
`CESSING PROTOCOL SPECIFIC INFORMATION IN
`PACKETS SPECIFIED BYA PROTOCOL DESCRIPTION
`LANGUAGE, to inventors Koppenhaver, et al., ?led Jun.
`30, 2000, and incorporated herein by reference.
`US. patent application Ser. No. 09/608,266 for ASSO
`CIATIVE CACHE STRUCTURE FOR LOOKUPS AND
`UPDATES OF FLOW RECORDS IN A NETWORK
`MONITOR, to inventors Sarkissian, et al., ?led Jun. 30,
`2000, and incorporated herein by reference.
`US. patent application Ser. No. 09/608,267 for STATE
`PROCESSOR FOR PATTERN MATCHING IN A NET
`WORK MONITOR DEVICE, to inventors Sarkissian, et al.,
`?led Jun. 30, 2000, and incorporated herein by reference.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`FIELD OF INVENTION
`
`The present invention relates to computer netWorks, spe
`ci?cally to the real-time elucidation of packets communi
`cated Within a data netWork, including classi?cation 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 Of?ce
`patent ?le or records, but otherWise reserves all copyright
`rights Whatsoever.
`
`BACKGROUND
`
`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 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,
`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.),
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioners' EX1002 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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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
`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
`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
`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.
`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
`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
`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
`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.
`
`Petitioners‘ EX1002 Page 21
`
`Petitioners' EX1002 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`to store elements of the pattern, parse and extraction data-
`base used by the parser subsystem in accordance to one
`embodiment of the invention.
`
`50
`
`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
`
`55
`
`60
`
`65
`
`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
`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 conforming to the ISO
`layered network model.
`Communication protocols are layered, which is also
`referred to as a protocol stack. The ISO (International
`Standardization Organization) has defined a general model
`that provides a framework for design of communication
`protocol layers. This model, shown in table form below,
`serves as a basic reference for understanding the function-
`ality of existing communication protocols.
`
`ISO MODEL
`
`Layer
`
`Functionality
`
`Example
`
`7
`6
`5
`4
`3
`2
`
`1
`
`Application
`Presentation
`Session
`Transport
`Network
`Data Link
`
`Physical
`
`Telnet, NFS, Novell NCP, HTTP,
`H.323
`XDR
`RPC, NETBIOS, SNMP, etc.
`TCP, Novel SPX, UDP, etc.
`IP, Novell IPX, VIP, AppleTalk, etc.
`Network Interface Card (Hardware
`Interface). MAC layer
`Ethernet, Token Ring, Frame Relay,
`ATM, T1 (Hardware Connection)
`
`Different communication protocols employ different lev-
`els of the ISO model or may use a layered model that is
`similar to but which does not exactly conform to the ISO
`model. A protocol in a certain layer may not be visible to
`protocols employed at other layers. For example, an appli-
`cation (Level 7) may not be able to identify the so