UIllted States Patent [19]
`Baker et a1.
`
`[54] SYSTEM AND METHOD FOR GENERAL
`PURPOSE NETWORK ANALYSIS
`
`[75] Inventors: Peter D. Baker. Aliso Viejo; Karen
`Neal. Los Angeles. both of Calif.
`
`.
`[73] Assigneez NB Networks. Aliso Viejo. Calif.
`
`[21] Appl. N0.: 575506
`[22] Filed:
`Dec. 20, 1995
`
`‘
`
`11500579394111
`
`5
`[11] Patent Number:
`[45] Date of Patent:
`
`‘
`
`‘
`
`1
`
`‘
`
`5,793,954
`Aug. 11, 1998
`
`5.062.055 10/1991 Chinnaswamy et a1.
`5.210.530
`5/1993 Kammerer et a1.
`
`364/55101
`l .
`
`5.442.639
`
`8/1995 Crowder et al. ..................... .. 371/201
`
`Primary Emminer—Emanue1 T. Voeltz
`Asst-5mm Examiner_Thomas Peaso
`Attorney, Agent, or Firm-Lyon & Lyon LLP
`
`[57]
`
`ABSTRACT
`
`[51] Int. cl.6 ................................................... .. H04L 12/28
`[52] US. Cl. .............. ..
`395/2003; 371/35
`[58] Field 01' Search .......................... .. 364/514 C. 514 R.
`364/55101; 340/825.06: 371/35. 48. 53.
`67-1~ 6&1 20-1~ 3? 395/182-02- 182-19-
`183'13‘ 183'15 ‘ 18322‘ 185‘01‘20O'8
`References Cited
`
`[56]
`
`U.S. PATENT DOCUMENTS
`
`A network interface System and r¢1at¢d methods- A Single
`logic control module. which may be implemented in hard
`ware or software. is utilized to perform any of a number of
`data manipulation functions including. for example. parsing.
`?ltering. data generation or analysis. based upon one or
`more programmably con?gurable protocol descriptions
`which may be stored in and relrieved from an associated
`memory.
`
`4,851,997
`
`7/1939 Tamra ............................... .. 395/20001
`
`4 Claims, 20 Drawing Sheets
`
`20 /'\_/
`
`r\/ 22
`
`{NPUT
`.
`.
`.7
`UEVKIES
`/\
`K
`
`7 P
`
`NETWORK
`DATA
`F‘LFS
`
`PROTOCOL
`DESCRIPTION
`F‘LES
`
`,
`OUTPUT
`DEVTCES
`\
`E
`
`7 8
`
`NETWORK DEVICE
`CO N TROT
`|_ O G T C
`
`/ \/ 76
`
`Petitioners' EX1012 Page 1
`
`

`
`US. Patent
`
`Aug. 11, 1998
`
`Sheet 1 0f 20
`
`5,793,954
`
`70 /\_/
`
`STORAGE
`
`/\,/ 74
`
`,
`
`7
`
`OUTPUT
`
`\
`
`K
`
`78
`
`WW:
`
`NETWORK
`
`DATA
`
`PROTOCOL
`
`DESCRIPTION
`
`\
`
`F
`
`79
`
`NETWORK DEVICE
`CONTROL
`LOGlC
`
`Petitioners' EX1012 Page 2
`
`

`
`US. Patent
`
`Aug. 11, 1998
`
`Sheet 2 of 20
`
`5,793,954
`
`OPTIONAL DATA
`
`PROTOCOL
`HEADER #m‘
`
`PROIOCOL
`HEADt'R #1
`
`F/G. 2
`
`[FIELD #? SUBRECORD
`
`PROTOCOL
`CONTROL
`RECORD
`
`F/G. 3
`
`Petitioners' EX1012 Page 3
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 3 of 20
`
`5,793,954
`
`“SE0”.
`
`
`
`muzmzfiwEummxoEa.ExuonuE
`
`
`
`
`
`598..59.3Enm
`
`
`
`
`
`...1_“_.ss_£§_,_mfiEH§_§§
`
`
`
`Eooom_o:cooEEm£m
`
`co:m_m:m._._.
`
`
`
`
`
`...uc__m.mSom.mmu_..
`
`..c3oS.::..
`
`mw.3
`
`%&..Eu_.aEl%88858885Hgggg.8205
`
`
`
`
`
`Bauazm.a3_oo..mm2no<.oucm>cozmczmmo
`
`
`
`
`
`Petitioners‘ EX1012 Page 4
`
`Petitioners' EX1012 Page 4
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 4 of 20
`
`5,793,954
`
`
`
`m:2o::mq:xoo._mmm:uu<._oucm>mofiom
`
`
`
`
`
`vtutlt
`
`:o:m_mcE._.
`
`__c3oSE3._
`
`230523..
`
`HHatsmamasH.:<mags$3.5E
`%.535885mIEEE
`
`Q»,.3
`
`..8_.emsoEm$..j<88858886
`
`._§a§.5_.H&&&xo588$
`
`Petitioners‘ EX1012 Page 5
`
`Petitioners' EX1012 Page 5
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 5 of 20
`
`5,793,954
`
`SEE...52$
`
`u:xoo4
`
`
`
`
`
`Sumo:mEn._mxomnoasI
`
`m=.zo::m
`
`1_E.§IEIlEI .i
`..=m%._59.353uzmzzw5m
`
`G)
`A
`
`27:‘.
`>3:
`“*0
`
`E3“.I2:5EEoumm
`
`_O.::0O
`
`
`
`mEmz_ooSo..a
`
`
`
`.ou2oiocmcwo.no
`
`gEEEIIEIEI
`_E_§
`EIIIIEIHEIIE
`IIIII
`
`V‘
`
`V
`
`.mv_oommeaomE%%EO
`
`Petitioners‘ EX1012 Page 6
`
`Petitioners' EX1012 Page 6
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 6 of 20
`
`5,793,954
`
`
`
`
`
`m:2u::m_ouo.o&:82m
`
`nibmEmi
`
`Petitioners‘ EX1012 Page 7
`
`Petitioners' EX1012 Page 7
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 7 of 20
`
`5,793,954
`
`
`
`mzauazm_O0o.O..&“X02Exuommusom
`
`
`
`
`
`
`
`_._82en__mm2_...
`
`j<«:9688.5
`
`:3<
`
`tnaxo856Hzm>m$55.25.5HEH$555'Eu
`
`Petitioners‘ EX1012 Page 8
`
`Petitioners' EX1012 Page 8
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 8 of 20
`
`5,793,954
`
`u:xoo4
`
`o._3o::m
`
`2%IEIEEIEIHHEEHHHIEU0;
`
`.222
`
`
`
`._co_ao._ommo:
`
`EaoEms:“.9Egg
`_.5__.o§ss.5_.ggg
`._s_ao82ma,EEE
`
`Petitioners‘ EX1012 Page 9
`
`
`
`£95..£95..E3E5595,.Bate
`
`
`
`muzmzflm._@Um@IoEw._u_xouzo:3gmgm
`
`
`
`
`
`wEm.ZEmi
`
`EEHIII
`
`wEm
`
`01
`
`co:
`
`.o
`
`.
`O
`
`
`
`%E,,.%:.__..zEEoumm_9Eooco_aO_2mm_2no
`
`
`
`
`
`
`
`oEmz_ou2oE
`
`
`
`co_EoBum:no
`
`Petitioners' EX1012 Page 9
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 9 of 20
`
`5,793,954
`
`aaxooq
`
`o._3u::m
`
`8_§§m
`
`:o=m_m:m.F
`
`EE
`Egg%_E._sz
`Ii!‘
`
`:o_.qO.m_._.0Emn_O
`
`
`
`mEmz_oo2o.a
`
`
`
`Hoax.228ceaoSmno
`
`mgmeaz
`
`
`
`some:9:2...,_8._oEm_m:3._m._m
`
`
`
`
`
`mEm2Emi
`
`xoc:_
`
`xxEm
`
`59.8..59.3Eam
`
`
`E5czm598..32.0
`
`Eli:
`
`H
`mmmm%
`
`
`
`u:xoo._._Ow
`
`%Egg3.2.E2Em:2o_.:.m
`
`HE
`
`Petitioners‘ EX1012 Page 10
`
`Petitioners' EX1012 Page 10
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 10 of 20
`
`5,793,954
`
` g:¥Eou_._2_E
`
`
`m._3u:.zw
`
`E
`
`é.u..§..o%
`Egg
`II!‘
`
`
`
`oEaz_ooo.o._m
`
`ceaouoozmo
`
`
`
`
`
`Eoumm_O:COO.._o:QOQOOZQ0
`
`a:xoo4
`
`
`
`oEm.ExuocoE91to;gm.52.52Emi
`
`IEIEIEIHHEHEH
`
`59.3593..
`
`
`
`Esmcam55£m:m4..ammo
`
`lilo;
`
`:o:m_mcm.:.
`
`m:3u:.:m9203qooz
`
`lg
`%E§_s_..__2
`
`Hxou:_:82_oo2o.i
`
`ma.3
`
`xmnE
`
`Petitioners‘ EX1012 Page 11
`
`Petitioners' EX1012 Page 11
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 11 of 20
`
`5,793,954
`
`
`
`Eoumm_EEoo:o_EOm~_mxmsE:2aw
`
`
`
`
`
`_mE_omu
`
`_mE_uwU
`
`EIEIEIIIIE
`JEIIEIIEIII
`lz.EEI.i.i
`
`a:xoo4
`
`Efiuabw
`
`
`
`
`
`Sumo:oEm..u_xoozoE
`
`
`
`59:...5.9.35.;£5gm._
`
`E2230
`EmEm_u_
`
`
`
`UBESU.u.u_m¢E=zE
`
`
`
`mEmz_ouo.o.a
`
`
`
`cozaom~_mxmE
`
`co:m_mcE.—
`
`_.mN_mxm2ss_..
`
`IEfig
`
`Petitioners‘ EX1012 Page 12
`
`Petitioners' EX1012 Page 12
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 12 of 20
`
`5,793,954
`
`
`
`mSU::m_o:cooEccmco._m:_n_
`
`
`
`
`
`
`
`memzEccaco
`
`:o_§m5m.._no
`
`.aE_omE2...
`
`mX8532:.E
`o$9...3mama
`_x%:_.3m::._n.
`%%%
`
`
`m_m::m:U.252.mE_ouBEE.6.8832masm.25Esmm
`weIIm_§:e,__1,
`
`9wt
`
`Petitioners‘ EX1012 Page 13
`
`Petitioners' EX1012 Page 13
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 13 of 20
`
`5,793,954
`
`.
`
`._:_<
`
`=305£0:
`4._<HE
`
`
`
`
`
`..::U::w9:00..co___uSo_m=Emx%:_
`
`:o:m_mcE.~
`
`
`
`
`
`|<|&&.aEEgg
`
`
`QEEIEEEE
`m::o::mazxonjcoavcoo_$_EFxouc_
`
`
`
`
`
`920259203coaucoo_m.=Eoxmus
`
`cozsmcmfi
`
`
`
`LOO.“_ou8>..
`
`
`j<|E8.aIoooooxoIggéafifi
`|<lfitxo Hggl
`
`o:_m>Eaom
`
`m_s.<E1mm5::
`
`ws_<E$S_M
`
`Petitioners‘ EX1012 Page 14
`
`Petitioners' EX1012 Page 14
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 14 of 20
`
`5,793,954
`
`3»
`
`mt
`
`82
`
`
`
` EamgaEE>§wE:m_dw_:am
`
`
`
`m_>§m§:é_E~Bz_
`
`SE:9232%mmbi91oUo§_n__Zw_V_.5am/1:N
`
`s:_,_§_v25%:
`
`as;Q5>2<
`
`my
`
`m9____mm_,.E
`
`
`
`éémmi/1%
`
`agzowézfiaE0
`
`%::§9E53mm
`
`25;:923.2%mm
`
`
`
`o9EEEd>5§§.255:mm
`
`NS
`
`\\wt
`
`«Q
`
`Q3
`
`22mrfi
`
`37525,.E05
`
`839%232%_1_;_mz§_
`
`
`
`§<,a_§:55UEEE_
`
`7.o_%.§5E
`
`
`
`
`
`33..§3_..,z8fi<may
`
`Q3
`
`«Eta“:45:2
`
`N:
`
`3.23:V255:3
`
`S85E52
`
`252
`
`B»
`
`ms
`
`885%
`
`.35..9soeoizfiamm
`
`at
`
`§29E&§
`
`
`
`GBEEQEZ£355
`
`as
`
`_8o§%azEéofiéafiamm
`
`Petitioners‘ EX1012 Page 15
`
`Petitioners' EX1012 Page 15
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`US. Patent
`
`Aug. 11, 1998
`
`Sheet 15 of 20
`
`5,793,954
`
`150" PARSEPROTOO [
`
`__
`
`752
`
`PARSEFIELD
`
`(RE Y‘URNS LOOALPROO}
`
`ALL BITS PARSED
`PARSELEN >: HWLEN '?
`
`‘
`YES
`
`P155
`RETURN
`NULL
`
`I75
`
`YES
`
`:72
`
`154
`
`NO
`
`CURRENTPROTOCOL SUPPORT
`56”
`
`NO
`
`YES
`
`SET CURRENTPROTOCOL TO OPTION f 755
`CQNTROL PROTOCOL
`
`—
`
`NO
`
`ANY OPTIONS
`PROTOPARSELEN<HEADERLEN ?
`
`NO
`
`ALL OOs PARSED
`PARSELEN >2 HWLEN '9
`
`I60
`
`YES
`
`SUBTRACT PROTOPARSELEN FROM w ,6;
`HEADERLEN
`
`PARSEFIELDS
`(RETURNS NEXTOPHON)
`
`754
`
`1!
`LSET CURRENWROIOCOL TO NEXIOPOON k“ F66
`
`F/G. /2
`
`Petitioners' EX1012 Page 16
`
`

`
`U.S. Patent
`
`Aug. 11, 1993
`
`Sheet 16 of 20
`
`5,793,954
`
`am
`
`32wt
`
`go.
`
`
`
`:32EOBKEESEmoEzfimmmiogg_Qd_E3mm
`
`
`
`mm\wt2252585%225%?am
`
`
`
`m\wt33wt
`
`
`
`mum-/1E$mm<n9zlamznopogQ2
`
`9
`
`2§§n_o§_n_-2m§§_VQ2
`
`Edmmé
`
`255%EzEm%%5%mm
`
`QR
`
`Em392%:
`
`
`
`“.17Em~§o5%_Az..1._$Q§_wo93:59m_
`
`§EEWSQ02.3E35mm
`
`ammom
`
`E5mafia:
`
`z5$Q:IvzEm~_§9o&
`
`
`
`m5:9ed:5:52/K
`
`m%
`
`:5mg§<E
`
`2:§§_.._vzEm%_
`
`M3,;E
`
`E3;$3.53age023
`
`B»mew
`
`Sm
`
`Petitioners‘ EX1012 Page 17
`
`Petitioners' EX1012 Page 17
`
`
`
`
`
`
`
`
`
`
`

`
`US. Patent
`
`Aug. 11, 1998
`
`Sheet 17 0f 20
`
`5,793,954
`
`P11521116
`cowncum 011 [HIS +1110 '2
`
`YES
`
`APPLY FILTER
`
`/
`
`232
`
`DOES HELD
`CONT/UN A CHECKSUM ?
`
`VERIFY CHECKSOM
`
`COLLECT STANSNCS
`
`2J6
`
`PERFORM ROUTING
`
`DOES ‘FIELD
`CONTAIN HEADERLEN ?
`
`s11 HEADERLEN 10 m
`VALUE*HEADERLENFLAG
`258
`
`390
`
`NO 1
`
`ADD CURFIiLD 511115110111 10
`ZZZ/“11111135191 AND PROTOPARSELEN
`
`0015 HFLD
`comm FRAMELEN '2
`/
`224
`
`2?”
`
`SET FRAMELEN 10 MINMUM OF
`HWLEN AND
`(VALUE*FRAMELENFLAG + PARSELEN
`— PROTOPARSELEN)
`|
`
`F/G. L315
`
`Petitioners' EX1012 Page 18
`
`

`
`US. Patent
`
`Aug. 11, 1998
`
`Sheet 18 0f 20
`
`5,793,954
`
`J00’
`
`VALIOATE VALUE
`
`DOES LOOKUP
`TABLE EXTST '4’
`
`Jig
`
`TALL VALUES OKT
`INCRLMEM CURFIFTD BY 1
`
`V
`LVAIUE TS TTTTOALT
`TNCTTEMENT CU‘THLLD BY T
`
`J04
`
`VALUE FOUND
`IN LOOKUP TABLE ?
`
`TS
`NEXTDROTOCOL NULL ?
`
`SET NEXTPROTOCOL TO LOOKUP
`PROTOCOL
`
`A SET CURFIELD TO LOOKUP iNDFX _|
`m
`
`RETURN =
`
`F/G. l4
`
`Petitioners' EX1012 Page 19
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 19 of 20
`
`5,793,954
`
`APPLY FTLTER
`
`YES
`
`IS INDEX<
`NEXTCRITERTALTNDEX?
`SKIP
`
`INJLX>CQUNT '?
`MTSSzD
`
`TBNODKJSLYTBQF
`
`404
`
`406
`
`TT
`405 ?\ SET NEXTCRITERTAUNDEX TO
`ENTRY NEXTTNDEX HELD
`
`TS ENTRY STATUS PASS ?
`
`409
`
`4/6
`
`SET‘ mm STATUS
`10 PASS
`
`474
`/
`T
`
`T!
`(DTSABLE FILTER)
`SET NEXTCRITERAHNDTX TO
`' TOTALCRITERTA
`
`= RETURN
`
`420w
`
`T
`
`Petitioners' EX1012 Page 20
`
`

`
`U.S. Patent
`
`Aug. 11, 1998
`
`Sheet 20 of 20
`
`5,793,954
`
`K.‘m3<>mi“E5
`
`m?§<§w_
`
`
`
`BE:3E323,;::m
`
`m__mxlf3.1>3<>zzm
`
`wouE<>mEn.Awas,mfg>m<>
`
`zo_§§_28E815%232>>m<>
`
`
`
`Bzcam2.5J_<>>m<>
`
`_,_E<%o_a,._z8>m
`
`mm;
`
`E;25%32>83>E35
`
`1:35333>gm;
`
`E;25%Siam3%
`
`Eu:
`
`3mm
`
`Mam
`
`Petitioners‘ EX1012 Page 21
`
`E22:+E5/avEE225Eea.2Emm
`
`:25E53>Emm952>am
`
`52>Z3%Em
`
`Petitioners' EX1012 Page 21
`
`
`
`
`
`
`
`
`

`
`1
`SYSTEM AND METHOD FOR GENERAL
`PURPOSE NETWORK ANALYSIS
`
`TECHNICAL FIELD
`
`The present invention relates to network communications
`systems and. in particular. to improved systems and methods
`for parsing. filtering. generating and analyzing data com-
`posed of inter-related structures such as protocols found
`within network frames.
`
`BACKGROUND ARI"
`
`Existing network interface devices provide systems for
`receiving. analyzing. filtering and transmitting network data
`or frames of data. Network Protocol Analyzers. Bridges. and
`Routers are among the most common network interface
`devices currently available.
`Conventional network protocol analyzers provide. for a
`predefined set of network frame structures or protocols. a
`system for monitoring the activity of a network and the
`stations on it by allowing network traffic to be captured and
`stored for later analysis. Common capture and analysis
`capabilities include the gathering of statistics. subsequent
`report generation.
`the ability to filter frames based on
`specific criteria. and the ability to generate network traflic.
`Bridges and routers are network devices that pass frames
`from one network interface to another. Bridges operate at the
`data—link layer and routers at the network layer of the OSI
`reference model. Like protocol analyzers. both bridges and
`routers may gather statistics and filter incoming network
`frames based on specific criteria. however incoming frames
`also may be forwarded to other networks based on infor-
`mation collected by the bridge or router. Routers typically
`support only a limited number of network protocols.
`Each of these network devices requires an ability to
`separate network frames into individual protocols and their
`components (typically referred to as parsing). an ability to
`filter incoming frames based on a logical combination of one
`or more field values extracted during parsing. and an ability
`to gather statistics based in part on extracted field values.
`Typically.
`it
`is a requirement
`that network frames be
`received. analyzed and forwarded at full network speeds.
`sometimes on many different networks at one time.
`A frame filter consists of one or more criteria which
`
`specify one or more valid values for a frame (or segments of
`a frame). Frame filtering criteria are typically implemented
`using an offset (from frame or protocol header start). a length
`in bits which defines a field. a value for comparison. and
`mask values for identifying relevant and irrelevant bits
`within the field. For multiple value filter criteria. the result
`from each filter value is logically OR’ed together to obtain
`an overall result. Therefore. each additional result adds to
`the processing required to filter a given field. For filtering on
`optional protocol fields that do not occur at the same relative
`offset
`in each protocol frame.
`this method is time-
`consuming. Thus. it would be desirable to perform filtering
`on both fixed and optional variable offset fields for any
`number of values or ranges of values without incurring any
`additional overhead.
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`Parsing. the process wherein network frames are broken
`up into their individual protocols and fields. is necessary for
`filtering with oflsets relative to protocol headers. gathering
`field based statistics. generating network traflic. routing data
`frames. verifying field values. and displaying network
`frames in human readable form. In conventional systems.
`
`65
`
`5.793.954
`
`2
`
`the parsing process has an overall structure which incorpo-
`rates conlrol logic for each supported protocol. Therefore.
`additional control logic must be developed when support for
`a new protocol is added to a conventional system. As the
`development of additional control
`logic. whether imple-
`mented in hardware or software. may be both time consum-
`ing and expensive. it would be highly desirable to be able to
`parse all protocols with a single configurable software (or
`hardware) module so that support for additional protocols
`could be added to a system without requiring substantial
`modification to the system or its control logic.
`Further. although microprocessors (or CPUS) available
`today can execute tens or even hundreds of millions of
`instructions per second. vendors often must provide dedi-
`cated hardware assistance and/or front-end processors with
`hand-coded assembly language routines to achieve the nec-
`essary processing rates for more than one pair of networks.
`Unfortunately. this solution requires hardware and/or soft-
`ware modifications whenever changes are made to the
`number of supported features or protocols.
`Finally. as networks become larger and more complex. the
`maintenance of a comprehensive statistics database by each
`network device becomes more important. Because these
`statistics databases typically are not utilized by a maintain-
`ing device. but instead are collected by a network manage-
`ment device. the collection process may affect performance
`adversely without any corresponding benefit to the collect-
`ing device.
`is
`it
`In light of the considerations discussed above.
`believed that a network interface system having a config-
`urable protocol analysis capability with common control
`logic applicable to many difierent network devices would be
`highly desirable.
`
`SUMMARY OF INVENTION
`
`The present invention is directed to improved systems and
`methods for parsing. filtering. generating and analyzing data
`(or fiames of data) transmitted over a data communications
`network. In one particularly innovative aspect of the present
`invention. a single logic control module. which may be
`implemented in hardware or software. is utilized to perform
`any of a number of data manipulation functions (for
`example. parsing. filtering. data generation or analysis
`functions) based upon one or more programmably config-
`urable protocol descriptions which may be stored in and
`retrieved from an associated memory.
`The use of common control logic (i.e. the use of a single
`logic control module) and programmably configurable pro-
`tocol descriptions allows changes to existing protocols to be
`made and support for new protocols to be added to a system
`in accordance with the present invention through configu-
`ration only—without the need for hardware and/or software
`system modifications. Thus. those skilled in the art will
`appreciate that a network interface in accordance with the
`present invention may be configured and reconfigured. if
`necessary. in a highly efiicient and cost elfective manner to
`implement numerous data manipulation functions and to
`accommodate substantial network modifications (for
`example. the use of different data transmission hardware.
`protocols or protocol suites) without necessitating substan-
`tial system changes.
`In one preferred form. the system of the present invention
`may employ a CPU or other hardware implementable
`method for analyzing data from a network in response to
`selectively programmed parsing. filtering. statistics
`gathering. and display requests. Moreover. the system of the
`
`Petitioners‘ EX1012 Page 22
`
`Petitioners' EX1012 Page 22
`
`

`
`5.793.954
`
`3
`present invention may be incorporated in a network device.
`such as a network analyzer. bridge. router. or traflic
`generator. including a CPU and a plurality of input devices.
`storage devices. and output devices. wherein frames of
`network data may be received from an associated network.
`stored in the storage devices. and processed by the CPU
`based upon one or more programmably configurable proto-
`col descriptions also stored in the storage devices. The
`protocol descriptions may take the form of one or more
`protocol description files for each supported network pro-
`tocol and may include a protocol header record and plurality
`of field sub-records having data corresponding to an asso-
`ciated protocol and fields defined therein.
`The system of the present
`invention also preferably
`includes logic for extracting field values from particular
`network frames. performing validation and error checking.
`and making parsing decisions based upon field values and
`information in the programmably configurable protocol
`descriptions.
`invention also preferably
`The system of the present
`includes logic for filtering a subset of network frames
`received from the input or storage devices which satisfy a
`filter criteria based upon information defined in the pro-
`grammably configurable protocol descriptions.
`The system of the present
`invention also preferably
`includes logic for filtering network frames which satisfy a
`plurality of filter criteria which. if desired. may be joined
`together by Boolean operators.
`invention also preferably
`The system of the present
`includes logic for analyzing a filter request by breaking the
`request into its component criteria to determine whether the
`result from evaluating a particular filter request criteria when
`combined with results from earlier criteria can be used to
`filter (i.e. discard) a particular network frame.
`The system of the present
`invention also preferably
`includes logic for collecting statistics based upon extracted
`field values satisfying a statistics criteria based upon infor-
`mation defined in the programmably configurable protocol
`descriptions.
`invention also preferably
`The system of the present
`includes logic for determining a next protocol description
`structure required to continue analyzing a network frame.
`The system of the present
`invention also preferably
`includes logic for determining a frame length and individual
`protocol header lengths from extracted field values in a
`network frame.
`
`invention also preferably
`‘The system of the present
`includes logic for making routing decisions based upon
`information contained in the programmably configurable
`protocol descriptions.
`invention also preferably
`The system of the present
`includes logic for determining display formats based on
`information contained in the programmably configurable
`protocol descriptions.
`invention also preferably
`The system of the present
`includes logic for verifying individual field values and
`making parsing decisions based on the validity of the value.
`The system of the present
`invention also preferably
`includes logic for constructing and transmitting network
`frames with varying field contents based on information
`contained in the programmably configurable protocol
`descriptions.
`The system of the present invention may be employed in
`any system where it is useful to be able to examine and
`perform various operations on contiguous bit-fields in data
`structures. wherein each data structure is composed of
`predefined fields of one or more contiguous bits. Further. the
`system of the present
`invention is particularly efficient
`where operations must be performed on a subset of included
`fields.
`
`20
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4
`
`Those skilled in the art will recognize that the system of
`the present invention gains a distinct advantage in size and
`maintainability over conventional network devices by
`implementing analysis capabilities for multiple known and
`unknown protocols using common control
`logic.
`Furthermore. the system gains a distinct advantage in speed
`and efiiciency over conventional network devices when the
`control logic is implemented in hardware or a front-end
`processor. without incurring the penalty of additional hard-
`ware and/or software development when protocol defini-
`tions change.
`Accordingly. it is an object of the present invention to
`provide an improved system for network analysis wherein
`the system may determine which protocols and which pro-
`tocol fields exist in a network frame (also referred herein as
`parsing) using common control logic combined with con-
`figurable protocol descriptions.
`It is yet another object of the present invention to provide
`an improved system for network analysis wherein the con-
`trol logic may be implemented in hardware as well as
`software.
`
`It is yet another object of the present invention to provide
`an improved system for network analysis wherein each
`supported analysis capability is configurable even when the
`control logic is implemented in hardware.
`It is another object of the present invention to provide an
`improved system for network analysis wherein the system
`may determine whether a particular network frame includes
`a field that satisfies a particular filter criteria based upon
`information stored in a programmably configurable protocol
`description.
`It is yet another object of the present invention to provide
`an improved system for network analysis wherein the sys-
`tem may determine if a particular network frame includes a
`protocol field that satisfies a particular statistics gathering
`criteria defined in a prograrnmably configurable protocol
`description.
`It is yet another object of the present invention to provide
`an improved system for network analysis wherein the sys-
`tem may generate network traffic in the form of frames
`constructed from selected protocol descriptions with the
`ability to specify a variety of methods for varying individual
`field values.
`
`It is still another object of the present invention to provide
`an improved system for network analysis wherein the sys-
`tem may route network frarnes (deterrnine the appropriate
`destination interface) that satisfy a particular routing criteria
`defined in a programmably configurable protocol descrip-
`tion while providing a capability to specify a variety of
`methods for varying individual
`field values during the
`routing process.
`It is still another object of the present invention to provide
`an improved system for network analysis wherein the sys-
`tem may determine if a particular network frame includes a
`protocol field that contains a value related to either the
`overall length of the frame or the current protocol header
`length.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a network interface system
`in accordance with one form of the present invention.
`FIG. 2 is a diagram representing a set of data records of
`a typical network frame which may be contained in the data
`files of the network interface system illustrated in FIG. 1.
`FIG. 3 is a diagram representing a set of data records of
`a protocol description in accordance with one form of the
`present invention.
`FIG. 4 is a diagram representing a control record of an
`Ethernet protocol description which may be utilized in a
`
`Petitioners‘ EX1012 Page 23
`
`Petitioners' EX1012 Page 23
`
`

`
`5.793.954
`
`5
`network interface system in accordance with one form of the
`present invention.
`FIG. 4a is a diagram representing five defined field
`sub-records of the Ethernet protocol description illustrated
`in FIG. 4.
`
`FIGS. 4b, 4c, and 4d are diagrams representing lookup
`structures referenced in FIG. 4a fields 0. 2 and 4 respec-
`tively.
`FIG. 5 is a diagram representing a control record of an
`imaginary Generic Protocol description which may be uti-
`lized in a network interface system in accordance with one
`form of the present invention.
`FIG. 5a is a diagram representing eleven defined field
`sub-records of the GP description illustrated in FIG. 5.
`FIGS. Sb, Sc, 5d, and 5e are diagrams representing lookup
`structures referenced in FIG. 5(a) fields 1. 3. 7 and 8.
`respectively.
`FIGS. 6. 6a, and 6b are diagrams representing the control
`record and field sub-record of a protocol description struc-
`ture that allows parsing of optional fields of the GP descrip-
`tion shown in FIGS. 5-Se.
`
`FIGS. 7. 7a, and 7b are diagrams representing the control
`record and field sub-records of a protocol description struc-
`ture that describes the End Of List option of the GP
`description shown in FIGS. 5-Se.
`FIGS. 8. 8a, and 8b are diagrams representing the control
`record and field sub-records of a protocol description struc-
`ture that describes the No Operation option of the GP
`description shown in FIGS. 5—5e.
`FIGS. 9. 9a, and 9b are diagrams representing the control
`record and field records of a protocol description file that
`describes the Maximum Frame Size option of the GP
`description shown in FIGS. S—5e.
`FIGS. 10. 10a, 10b, 10c, 10d and we are diagrams
`representing data records of a filter expression control and
`associated field filter structures.
`FIG. 11 is a flow chart illustrating top level frame parsing
`control logic in accordance with one form of the present
`invention.
`
`FIG. 12 is a flow chart illustrating protocol parsing control
`logic in accordance with one form of the present invention.
`FIG. 13 is a flow chart of the field parsing control logic
`in accordance with one form of the present invention.
`FIG. 14 is a flow chart representing value verification.
`error checking. next protocol and branch determination
`control logic in accordance with one form of the present
`invention.
`
`FIG. 15 is a flow chart representing field filtering control
`logic in accordance with one form of the present invention.
`FIG. 16 is a flow chart illustrating field value extraction
`and varying control logic in accordance with one form of the
`present invention.
`
`DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`Referring now to FIG. 1. a network interface system in
`accordance with one form of the present invention. generally
`referred to as 10. may be implemented in a network device
`including input devices 12. data storage devices 14. analysis
`control logic 16 for facilitating the input. storage. retrieval.
`and analysis of network frames. and output devices 18 for
`forwarding frames or displaying or printing the results of
`analyses. A data storage device 14 may include a data file 20
`of network frames having n protocol data records. wherein
`each data record contains data stored in a plurality of
`predefined fields. Protocol description files 22 also may be
`stored in the data storage device 14. The protocol description
`
`6
`files 22 may include a protocol control record and n field
`sub-records. which together may describe a subset of a
`network protocol and include rules for analyzing that pro-
`tocol.
`
`The network device control logic 16 is capable of retriev-
`ing a subset of network frames from the input devices 12 or
`data files 20 which satisfy one or more criteria based upon
`extracted field values and filtering criteria contained in one
`or more of the protocol description files 22. The network
`device control logic 16 also includes logic for determining
`frame and protocol header lengths. gathering statistics. veri-
`fication and error checking. determining routes. varying
`values. and formatting output.
`
`A personal computer or conventional network device.
`such as an IBM PC (or compatible). Apple Macintosh®. or
`any Unix®. or Zenix® workstation. protocol analyzer.
`bridge. router. traffic generator. or similar system may be
`utilized in accordance with the system of the present inven-
`tion. The data input devices 12 may comprise any of a
`number of commercially available network interface devices
`and may include a conventional keyboard or mouse if
`required. The data storage devices 14 may take the form of
`any of a number of commercially available data storage
`options (such as RAM. ROM. EPROM. or various sized
`fixed disk drives). and the data output devices 18 may
`comprise any of a number of commercially available user
`interface devices. such as CR1‘ displays. monitors. network
`interface devices and/or printers (if required). The analysis
`control logic 16 rrmy be implemented as a computer program
`written in any language suitable for systems programming or
`may be implemented in hardware if better performance is
`required.
`In one presently preferred form.
`the analysis
`control logic 16 may be implemented via the programming
`files set forth in the attached microfiche Appendix. which is
`incorporated herein. However. those skilled in the art will
`appreciate that the analysis control logic 16 might equiva-
`lently be implemented in dedicated hardware using. for
`example. one or more application specific integrated circuits
`(“ASICs") or one or more field programmable gate arrays
`(“FPGAs”).
`
`The network interface system 10 of the present invention
`is preferably implemented on a personal computer. work-
`station or conventional network device having a 32-bit or
`larger bus and register set. an optional math co-processor. at
`least one megabyte of available RAM. and for personal
`computer and workstation applications. a fixed disk having
`at least 10 megabytes of available storage space. As shown
`in the microfiche appendix. the analysis control logic 16 may
`be programmed in the C-H- language. with abstract data
`types defined for statistics gathering. value verification. next
`protocol determination. filtering. varying values. checksum-
`ming and route determination capabilities. and protocol
`control and field records.
`
`Referring now to FIG. 2. a data file 20 in accordance with
`one form of the present invention may include a plurality (n)
`of protocol header data records and optional Data and Pad
`records. Each protocol record contains data organized into a
`plurality of predefined fields. Each field comprises a collec-
`tion of 1 or more contiguous bits and includes a set of valid
`values for that field. For example. a particular protocol
`specification might include a 6 bit header length field that
`limits the protocol header length to values between 20 and
`60 inclusive. thereby excluding values less than 20 and
`values from 61 to 64.
`
`The number of possible contiguous bit fields for a pro-
`tocol header of length N bits where N is greater than 1 can
`be expressed by the following formula:
`
`10
`
`20
`
`25
`
`30
`
`35
`
`45
`
`SO
`
`55
`
`65
`
`Petitioners‘ EX1012 Page 24
`
`Petitioners' EX1012 Page 24
`
`

`
`5.793.954
`
`8
`
`7
`
`N
`
`Ntunber of Possible Fielcb = 121 i
`
`It will be appreciated by those skilled in the art that any
`possible organization of fields for any possible protocol
`specification is contemplated for the network interface sys-
`tem 10 of the present invention.
`Referring now to FIG. 3. a protocol description file 22 in
`accordance with one form of the present invention may
`include a protocol control record. and a plurality (n) of field
`data records. In a particularly preferred embodiment. the
`protocol control record (shown below in Table 1) may define
`the overall structure of a network protocol and reference
`other information relating to the network protocol.
`
`10
`
`TABLE 3
`STATISTICS STRUCTURECLASS RECORD
`
`Olfset Name Description
`
`0-3
`pointer to user assigned name for statistic
`Stat.Name
`4-7
`pointer to derived smrcturelclass for accumulating
`Stat
`configured statistic
`
`The next protocol lookup records referenced in the field
`sub-record table (Table 2) at bytes 28-31 are preferably
`organized as shown in Table 4:
`
`TABLE 1
`
`PROTOCOL CONTROL RECORD
`
`
`
` Offset Name Description
`
`name_length
`0-3
`protocol_name
`4-7
`filename
`8-ll
`12-15 numBits
`16-17 numFie1ds
`18-19 curField
`20-23 outFlag
`24-27 dbW
`28-31 fields
`32-25 optional
`
`length of protocol name in bytes including NULL terminator
`name of protocol control record is describing
`name of tile control record is stored in
`total bit length of protocol header control record is describing
`number of fields requirai to describe protocol header
`index of field currently referenced
`flag indicating template has been output to file
`display bit width for protocol header display
`field records that describe protocol hearhr
`pointer to option control record to use