[19]
`United States Patent
`5,805,808
`
`Hasani ct al.
`[45] Date of Patent:
`Sep. 8, 1998
`
`[11] Patent Number:
`
`USOUSSOSSOSA
`
`[54] REAL TIME PARSER FOR DATA PACKETS
`IN A COMMUNICATIONS NETWORK
`
`[75]
`
`Inventors: Santosll K. Hasani, Nashua, N.II.;
`Salish L. Rege, (lmlon; Mark F.
`Kcmpf, Stow, both of Mass.
`
`.
`173] M‘tlgnw Digital Equipment Cflrporatifln,
`Maynard, M335.
`
`[21] Appl. No.: 838,678
`
`395.1650
`21l99fl Bourne
`4,905,138
`T1l990 Fischer .................................... 3641200
`4,941,089
`12.11991! MCCOUI
`................................. 37"W85A
`4,979,167
`211991 David Ct 31.
`36419111.)
`4,991,133
`5,056,058 1011991
`lIirata Cl 31.
`..
`. 364N110
`
`.............................. 370185
`5,058,110
`1011991 Beach at al.
`5,067,lf|4
`“([991 Krishnakumar cl al.
`395.5375
`5.228.083
`111993 Lozowick cl al.
`..... 330m
`
`..
`5,235,644
`811993 Gupta Ct 31.
`380141.}
`
`. 3951650
`5,249,292
`9.11993 Cltiappa
`
`5,361,353
`1111994 Carr el al.
`395nm
`
`[22]
`
`Filed:
`
`Apr. 9, I997
`.
`.
`‘
`Related U'b' Application Data
`[63] Conlinualinn of Ser. No. 365,993, Dec. 29, 1994, aban—
`duned. which is a continualion ()1 Ser. No. 814,997, Dec. 27,
`1991, abandoned.
`
`[51]
`[52]
`[58]
`
`[56]
`
`...................................................... G061” 13100
`Int. Cl.‘i
`[1.5. CI. ......................................... 39512002, 37021392
`Field Of Search
`3951801), 2011.15,
`395-20222 84“: 841: 851: 1:53: 18113;
`3701-5" 351’ 353’ 389’ 39" 401’ 402;
`38013, 4, 9, 28, 37, 42,49, 50
`
`References Cited
`U.S. PA'l'IiN'l' DOCUMENTS
`
`Primary EJt'rrmr'ner—Alpcsh M. Shah
`Afton-re}; Agent, or Firm—Christine M. Kuta; A. Sidney
`101105101]
`
`[57]
`
`ABSTRACT
`
`Aparscr for reading bits of a packet has a set of logic circuits
`implemented in a computer chip; 3 memory interacting with
`[he c0mpulcrchip,1hc memory vaiding lirsl dam 10 [ha gel
`01‘ logic circuits; means I‘m reading hits from any field 01
`packet into the set nilugic circuits, the hits providing second
`_
`1
`,
`._ 5 _
`-
`,_
`_
`_
`,
`_-
`‘
`_
`data In the act L11 lug“. LlTLllllE-u, means, responsive to the Inst
`
`data and the second data, for the logic circuits to interpret
`bits of the packet.
`
`4,869,8le
`
`6;]989 Knhayashi el al.
`
`....................... 370m
`
`13 Claims, 21 Drawing Shoots
`
`PACK”
`PAGE TABLE mm
`0“ MMME
`170
`190
`
`SYSTEM
`BUS
`
`PACKET
`MEMORY
`
`INTERFACE
`
`
`
`
`ACTIVE —
`
`
`BULKHEAD I
`144
`
`
`-
`
`202
`
`214
`
`m
`
`'
`
`142
`
`EX 1015 Page 1
`EX 1015 Page 1
`
`

`

`US. Patent
`
`Sep. 8, 1998
`
`Sheet 1 of 21
`
`5,805,808
`
`
`
`13_0
`
`110
`
`110
`
`FIG. 2
`
`EX 1015 Page 2
`EX 1015 Page 2
`
`

`

`US. Patent
`
`pe5
`
`w.
`
`n...m
`
`5,805,808
`
`
`
`eHmo§m§§nEvzma...mwfiEng
`
`Nrmoa
`
`EEEE
`
`GE
`
`a:
`
`2395
`
`man
`
`NvuOE”
`
`3:
`
`m.03
`
`
`
`8.,mod“;
`
`.01}asknow
`%333a.
`
`rmezm6sz
`
`“nmummmmb$323”
`
`2E
`
`m>§o<
`
`BEES?”Sn
`
`EX 1015 Page 3
`EX 1015 Page 3
`
`
`
`

`

`US. Patent
`
`Sep.8,1998
`
`Sheet 3 of 21
`
`5,805,808
`
`
`
`PARSER
`DATABASE
`
` 182
`
`FIG. 4
`
`
`
`
`
`PMC CONTROL
`
`. RMC CONTROL
`
`MISC. CONTROL
`
`15
`
`14 13
`
`12
`
`11
`
`10
`
`9
`
`8
`
`7
`
`6
`
`5
`
`4
`
`0
`
`HIE IIMMM
`
`FIG. 6
`
`EX 1015 Page 4
`EX 1015 Page 4
`
`

`

`US. Patent
`
`Sep. 8, 1998
`
`Sheet 4 of 21
`
`5,805,808
`
`Illa-Ill-
`
`mmDmmOm<w<flUQOWMm
`
`EggEma59m
`
`BEEEEEE
`
`E3042
`
`<m.05
`
`ED...$5$98.6$388
`
`FEI:m
`
`
`
`nan...32.04202;
`
`E5013
`
`EX 1015 Page 5
`EX 1015 Page 5
`
`
`
`

`

`US. Patent
`
`Sep.8,1998
`
`Sheet 5 or 21
`
`5,805,808
`
`72(64DATA + 3 PARITY)
`
`
` FC(8 BITS)
`
`
`BITS
`
`BLOCK 7-3
`
`DSAP(8 BITS)
`
`P1D(8 BITS x 5)
`
`Uindcx (5 BITS)
`
`BLOCK 9 (DSAPs)
`
`BLOCK 15-30
`
`( FILTERING
`INFORMATION FOR
`FC.DA AND LLC
`
`COMBINATION)
`
`( FIL'I'ERING INFORMATION
`FOR FC AND DA
`238
`
`
`COMBINATION)
`
`
`BLOCK10-14(PIDs) -
`
`
`
`
` 242
`
`
`
`
`BLOCK 31 (MORE
`FILTERING INFORMATION,
`
`243
`----------------------
`
`FC_CODE (3 BITS)
`pROMISCUOUS USER
`
`FILTBRING INFORMATION)
`
`
`FIG. 5B
`
`EX 1015 Page 6
`EX 1015 Page 6
`
`

`

`US. Patent
`
`Sep.8,1998
`
`Sheet 6 0f21
`
`5,805,808
`
`63
`
`62
`
`32
`
`31
`
`29 28
`
`0
`
`an a
`
`FIG. 7
`
`63
`
`62
`
`61
`
`0
`
`FIG. 8
`
`63
`
`62
`
`61 60
`
`59
`
`58 57
`
`53
`
`52 51
`
`0
`
`wan-mm-
`
`FIG. 9
`
`63
`
`62
`
`61
`
`{J
`
`fi-I—M
`
`FIG. 10
`
`EX 1015 Page 7
`EX 1015 Page 7
`
`

`

`US. Patent
`
`Sep.8,1998
`
`Sheet 7 of 21
`
`5,805,808
`
`63
`
`62
`
`61
`
`0
`
`II_I
`
`FIG. 11
`
`7
`
`6
`
`5
`
`4
`
`0
`
`III-
`
`FIG. 12
`
`63
`
`61 60
`
`59 58
`
`53
`
`52
`
`---E
`
`51
`
`50
`
`49
`
`48
`
`47
`
`46
`
`45
`
`4-4
`
`43
`
`42
`
`41
`
`D
`
`H/A
`HJA
`CLASSL HIA H/A H/A DIS HIA DIS HIA
`CXT RXT cm RUI RU] COT COT USLLC SNAP
`
`FIG. 13
`
`63
`
`62
`
`58 57
`
`53
`
`52
`
`51
`
`0
`
`I-II
`
`FIG. 14
`
`EX 1015 Page 8
`EX 1015 Page 8
`
`

`

`US. Patent
`
`Sep.8,1998
`
`Sheet 8 of 21
`
`5,805,808
`
` 402
`
`408
`
`FIG. 15A
`
`404
`
`Y
`
`FC
`DISCARD
`
`PROM
`405 FILTERING
`
`DA
`
`FILTERING
`
`
`FCDA
`DISCARD
`
`
`
`
`
`PROM USER
`FILTERING
`
`FIG. 15C
`
`
`
`USER
`VALIDITY
`
`FILTERING
`
`EX 1015 Page 9
`EX 1015 Page 9
`
`

`

`US. Patent
`
`Sep.8,1998
`
`Sheet 9 of 21
`
`5,805,808
`
`READ DATABASE FOR
`DA 6 TIMES AND GET
`
`412
`
`
`
`
`FINAL 63-BIT MASK
`
`
`
`OBTAIN 6-BIT
`DA INDEX FROM
`
`
`APPEND 6-BIT
`
`63-BIT MASK
`
`
`AMC INDEX
`
`PROM USER
`
`TO FC CODE
`
`FILTERING
`
`
`
` APPEN'D é—BIT DA
`
`418
`INDEX TO FC CODE
`
`
`
`
`
`FCANDDA
`FIL'I'ERING
`
`FIG. 15B
`
`EX 1015 Page 10
`EX 1015 Page 10
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 10 M21
`
`5,805,808
`
`NULL
`DSAP
`Emma
`
`
`READ DATABASE FOR
`PID 5 TIMES & GET
`63-BIT MASK
`
`SNAP
`DSAP
`mTERJNG
`
`
`
`492
`
`mom USER
`FIL'I‘ERING
`
`
`
`
`
`copy UNK BIT
`DSAP
`
`
`as?”
`FROM (:31 T0 FV
`
`494 OBTAIN 6-BIT LLC
`
`
`APPEND 6~BIT UNK
`INDEX TO PREVIOUS
`9-BIT INDEX
`
`APPEND 6-BIT INDEX
`TO PREVIOUS 9-BIT
`
`INDEX
`
`N
`
`48
`
`Y
`
`INDEX FROM 63-BIT
`
`MASK
`
`finflgmo
`
`FIG. 15D
`
`EX 1015 Page 11
`EX 1015 Page 11
`
`

`

`US. Patent
`
`Sep. 8, 1998
`
`Sheet 11 0f 21
`
`5,805,808
`
`488
`
`
`READ FC, DA,
`&. LLC DATA
`FROM DATABASE
`
`500
`
`
`
`
`PROM USER
`FILTERING
`
`
`
`READ FC, DA, & LLC USER
`DATA FROM DATABASE
`WITH FCDALLC INDEX
`
`506
`
`
`
`NON SNAP-SAP
`FILTERH‘IG
`
`COPY H/A(SNAP), TYPE, MD,
`INDEX IN FV
`
`512
`
`
`
`
`
`514
`
`USER
`VALIDITY
`FILTERING
`
`FIG. 15B
`
`EX 1015 Page 12
`EX 1015 Page 12
`
`

`

`US. Patent
`
`Sep. 8, 1998
`
`Sheet 12 0er
`
`5,805,808
`
`510
`
`NON SNAP SAP
`FILTER [N6
`
`522
`
`N
`
`COPY HIA(USLLC , TYPE,
`MD, UINDEXI FV
`
`520
`
`
`
`
`IS
`THIS
`
`
`CLASS 1
`
`
`USER
`
`
`Y
`
`530
`
`532 o
`
`524
`
`N
`
`Y
`
`534
`
`CLASS 1
`KID/TEST
`FILTERING
`
`RESPONSE
`
`COWAND
`
`USER
`VALIDITY
`FILTERING
`
`536
`
`540
`
`RUI
`DISCARD
`?
`
`Y
`
`542
`
`COPY HIA CUI), MD, TYPE,
`UIN EX IN FV
`
`PROM USER
`FILTERING
`
`N
`
`533
`
`COPY H/A(RUI), MD, TYPE,
`UINDEX IN FV
`
`544
`
`USER
`VALIDITY
`FILTERING
`
`546
`
`USER
`VALIDITY
`FILTERING
`
`FIG. 15F
`
`EX 1015 Page 13
`EX 1015 Page 13
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 13 M21
`
`5,805,808
`
`CLASS 1 XID I TEST
`FILTERING
`
`COT
`DISCARD
`
`PROM USER
`FIL'I'ERING
`
`COPY HIA(COT), TYPE,
`MD, UINDEX IN FV
`
`558
`
`USER VALIDITY
`FIIJ'ERING
`
`RESPONSE
`
`COMMAND
`
`570
`
`552
`
`
`
`COPY_/A(RXT),MD,TYPE_INDEXIN FV
`
`
`
`COPY HIA(CXT), TYPE,MD, UINDEx IN FV
`
`0
`
`USER VALIDITY
`FIL’I‘ERING
`
`O 5“
`
`USER VALIDITY
`FILTERING
`
`FIG. 156
`
`EX 1015 Page 14
`EX 1015 Page 14
`
`

`

`US. Patent
`
`Sep. 3, 1993
`
`Sheet 14 01'21
`
`5,805,808
`
`NULL DSAP
`FILTERING
`
`470
`
`575
`
`574
`
`N
`
`Y
`
`NULL NXT
`DISCARD
`(FROM
`CR 1)
`7
`
`
`
`N
`
`573
`
`Y
`
`PROM USER
`FILTERING
`
`532
`
`530
`
`PUT TYPE =
`OTHER IN FV
`
`USER
`VALIDITY
`FILTERING
`
`592
`
`
`
`
`NULL RXT
`DISCARD
`
`
`(FROM
`CR 1)
`1'
`
`N
`
`594
`
`Y
`
`PROM USER
`FILTERING
`
`534
`
`RESPONSE
`
`COMMAND
`
`586
`
`PUT TYPE =
`XID / TEST IN FV
`
`PUT TYPE -
`OTHER IN FV
`
`596
`
`0 59°
`
`USER
`VALIDITY
`FILTERING
`
`0 5”
`
`USER
`VALIDITY
`FILTERING
`
`FIG. 15H
`
`EX 1015 Page 15
`EX 1015 Page 15
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 15 6er
`
`5,805,808
`
`474
`
`SNAP DSAP
`FILTERING
`
`600
`
`N
`
`502
`
`
`
`
`SNAP NXT
`DISCARD
`(FROM
`CR 1)
`?
`
`604
`
`Y
`
`PROM USER
`FILTERING
`
`Y
`
`N
`
`608
`
`505
`
`PUT TYPE =
`OTHER IN FV
`
`610
`
`RESPONSE
`
`COMMAND
`
`USER
`VALIDITY
`FILTERING
`
`614
`
`
`
`SNAP RXT
`DISCARD
`(FROM
`CR? 1)
`
`
`N
`
`616
`
`Y
`
`PROM USER
`
`FILTERING
`
`PUT TYPE =
`OTHER IN FV
`
`620
`
`O
`
`USER
`VALIDITY
`FILTERING
`
`O
`
`USER
`VALIDITY
`FILTERING
`
`FIG. 151
`
`EX 1015 Page 16
`EX 1015 Page 16
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 16 M21
`
`5,805,808
`
`PROM USER
`FILTERING
`
`630
`
`
`
`USE FC CODE TO
`READ PROM DATA
`
`
`
`PROM
`
`DlsgARD
`
`
`
`BUFFER
`DIS CRIPTOR
`
`FILTERING
`
`
`
`USER
`VALIDITY
`FILTERING
`
`EX 1015 Page 17
`EX 1015 Page 17
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 17 M21
`
`5,805,808
`
`USER VALIDITY
`FILTERING
`
`654
`
`BUFFER
`DESCRIPTOR
`FILTERING
`
`
`
`
`
`
`BUFFER
`DESCRIPTOR
`FILTERING
`
`FIG. 15K
`
`662
`
`BUFFER
`DESCRI PTOR
`FILTERING
`
`EX 1015 Page 18
`EX 1015 Page 18
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 18 0121
`
`5,805,808
`
`BUFFER
`DESCRIPTOR
`FILTERING
`
`674
`
`1'00
`
`SET DISCARD
`BIT IN FV
`
`704
`
`703
`
`710
`
`712
`
`PUT
`TYPE =
`11 IN FV
`
`SET H l A
`BIT IN N
`To " 0 "
`
`670
`
`672
`
`
`
`IS
`
`POTENTIAL
`DIS BIT
`
`
`SET
`
`?
`
`
`Y
`
`
`
` N
`
`N
`
`714
`
`716
`
`FIG. 15L
`
`EX 1015 Page 19
`EX 1015 Page 19
`
`

`

`US. Patent
`
`Sep. 8, 1998
`
`Sheet 19 0121
`
`5,805,808
`
`I4—4 Barnes—bl {"800
`
`K.
`J 805
`
`READ DA
`
`313
`
`820
`
`810
`
`START
`LOGIC
`FLOW
`
`READ DSAP
`
`815/ 824
`READFC_DARAM 3“
`
`30A8
`
`DECODE RMC
`BUFFER
`DESCRIPTOR
`
`828 -\
`READ
`PID 330B
`i (”831
`
`READFCDALLC
`arr":—
`332 READUSERINFO
`833m
`READ PROM INFO
`
`Z._ 834
`
`EXECUTE REST OF ALGORII‘IM
`
`EX 1015 Page 20
`EX 1015 Page 20
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 20 01'21
`
`5,805,808
`
`900
`
`\
`902 RMCAD<31:0>
`‘~ RMCPAR < 3:0 >
`904
`MRMCRILL
`905\
`905 RMCRW
`uRMCDTACILL
`
`907 meow
`L RMOGT—L
`
`NPA < 3:0 >
`
`NPD < 15:0 :-
`
`NPPAR < 1:0 >
`
`PARSEL_L
`
`NPRW
`
`PARINI'_L
`afl—-—-—-
`
`PARTRLL
`
`IVIN
`
`IVOUT
`
`PAROUT
`
`BYTCLK
`
`SYMCLK
`
`FINIT L
`
`RMC
`— REQUEST
`_ RMC READ
`0R WR‘TE
`> BY MEMORY
`CONTROLLER
`_ GRANT BY
`MEMORY
`
`
`
`PARSER
`GA
`
`(1% USED
`IiOs + POWER
`& GND)
`
`RAMADD< 12:0>
`
`RAMCS_L<7:0>""922
`
`RAMDP < 71:0 > ““924
`
`RAMRW “926
`
`RAMOB__L —-\
`
`928
`
`FVRDY_L
`
`910
`FVOE_L
`FVDATA <14:0 > "J
`
`FVPAR "‘ 912
`
`PKTDIS —\
`930
`
`SMSEL < 2:0 >
`
`PARSM < 4:0 >
`
`FIG. 17
`
`EX 1015 Page 21
`EX 1015 Page 21
`
`

`

`US. Patent
`
`Sep. 3, 1998
`
`Sheet 21 01'21
`
`5,805,808
`
`15
`
`14
`
`13
`
`12
`
`11
`
`10
`
`0
`
`Hum—
`
`FIG. 18
`
`15
`
`0
`
`“-—
`
`UVRI
`
`FIG. 19
`
`15
`
`O
`
`UVRZ
`
`FIG. 20
`
`EX 1015 Page 22
`EX 1015 Page 22
`
`

`

`1
`REAL TIME PARSER FOR DATA PACKETS
`IN A COMMUNICATIONS NETWORK
`
`This is a continuation of Ser. No. 081365993, filed Dec.
`29, 1994, now abandoned, which is a continuation of Ser.
`No. (17f814,99'r', filed Dec. 27, 1991, now abandoned.
`
`FIELD OF THE INVENTION
`
`This invention relates generally to an interface between a
`communications network and a host computer, and more
`particularly to a parser for interpreting a packet received
`from the local area network.
`
`BACKGROUND OF THE INVENTION
`
`When a packet arrives at a host computer from a local area
`network, the packet must be read and interpreted in order for
`the host computer to decide what to do with the packet. For
`example, the host computer may decide that the packet has
`a destination address not used by the host computer, and in
`that case the host computer ignores the packet; that is the
`host detects the packet but does not receive the packet.
`Alternatively, the packet may be a token, in which case the
`host computer is given permission to begin transmission. As
`a further example, the host computer may match the desti-
`nation address of the packet, and so receive the packet into
`host computer main memory.
`In the above examples, the design of the interface between
`the host computer and the local area network attempts to
`read the incoming packet at the speed at which bits of the
`packet arrive at
`the interface. A simple match between
`station addresses used by the host computer and the desti—
`nation address in the DA field of the packet may be accom—
`plished by hardware using a table of addresses stored in a
`CAM.
`
`Further, for example, in a F DDI system the frame control
`field of the packet, the FC field, may be analyzed by the
`interface through match hardware using a CAM having
`common values stored in the CAM, where the common
`values are these commonly used in packet FC tields.
`The more diflicult problem of analyzing the full content of
`the packet headers, both the MAC header and the LLC
`header, where these are the standard IEEE 802.2 headers,
`remains unsolved as a task which can be accomplished at the
`rate at which packets may arrive at the host computer in a
`modern local area network. For example, the standard IEEE.
`802.2 MAC and LLC headers may contain a maximum of
`twenty two (22) bytes. Each byte has 8 bits, and so there are
`a possible two (2) to the 176 power unique combinations of
`bits. This is approximately 10*‘53 combinations. A CAM
`match scheme is unable to provide the required number of
`combinations.
`And in a modern local area network such as the FDDl
`
`optical fiber network, bits arrive at the rate of 100 megabits
`per second, or approximately 450,000 packets per second
`may arrive at the host computer. This arrival rate of bits is,
`in some cases, faster than the CPU of the host computer can
`execute software to read the packets into memory.
`A technique employed in the past for analyzing the header
`bytes of the packet, both MAC and LLC headers, has been
`to read the packets into adapter memory and then to slowly
`read the packets out of adapter memory so that adapter
`software can analyze the header bytes. However, the adapter
`software is slow: in firstly transferring the bytes to adapter
`memory; and in secondly analyzing the header bytes of the
`packet by reading the packets out of adapter memory.
`
`5
`
`10
`
`15
`
`10
`
`40
`
`60
`
`5,805,808
`
`2
`
`It is desirable to sort and store the packets arriving at a
`host computer from a modern local area network at the speed
`at which the bits arrive at the interface.
`
`SUMMARY OF THE INVEN‘I'ION
`
`A parser for reading bits of a packet has a set of logic
`circuits implemented in a computer chip; a memory inter—
`acting with the computer chip, the memory providing first
`data to the set of logic circuits; means for reading bits from
`any fleld of packet into the set of logic circuits, the bits
`providing second data to the set of logic circuits; means,
`responsive to the first data and the second data, for the logic
`circuits to interpret bits of the packet.
`BRIEF DESCRIPTION OF 'I‘IIL“. DRAWINGS
`
`FIG. 1 is a block diagram of a communications network.
`FIG. 2 is a block diagram of a station, or node, on a
`communications network.
`
`FIG. 3 is a block diagram of an adapter for connecting a
`host computer of a station to a local area network.
`FIG. 4 is a block diagram of a parser gate array.
`FIG. 5A is a field diagram of the fields of a message
`traveling on a local area network.
`FIG. 5|} is a memory diagram for a database for a parser.
`FIG. 6 is a field diagram of a forwarding vector produced
`by a parser.
`FIG. 7 is a field diagram ofan entry in a parser database.
`FIG. 8 is a field diagram ofan entry in a parser database.
`FIG. 9 is a field diagram of an entry in a parser database.
`FIG. 10 is a field diagram of an entry in a parser database.
`FIG. 11 is a field diagram of an entry in a parser database.
`FIG. 12 is a field diagram of an entry in a parser database.
`FIG. 13 is a field diagram of an entry in a parser database.
`FIG. 14 is a field diagram of an entry in a parser database.
`FIG. 15A, FIG. 15B, FIG. 15C, FIG. 15D, FIG. 15E, FIG.
`15F, FIG. 15G, FIG. 15H, FIG. 15], FIG. 15], FIG. 15K, and
`FIG. 15[. are a flow chart for the operation of a parser.
`FIG. 16 is a timing diagram for a parser.
`FIG. 17 is a connection diagram for a parser gate array.
`FIG. 18 is a field diagram of a control register.
`FIG. 19 and FIG. 20 are a field diagram of a user validity
`register.
`
`[)E’I'AII..L7I) DIL‘BCRIFI'ION
`
`Referring now to FIG. 1, there is shown a network 100.
`Network communications path 110 connects to host com—
`puters 112, 114, 116, 118, 120. Host computers 112, 114,
`116, 118, 120 communicate with each other by transmitting
`packets on communications pathway 110. For example,
`communication path 110 may be an ETHERNET commu-
`nications pathway, or for example may be a ring type
`communications pathway such as the FDDI Token Ring
`Communications System, etc. In any case, a IIISI. node, such
`as host computer 112, may desire to transmit a packet to host
`computer 120. [-Iost computer 112, then gains permission,
`through the access protocol for communications pathway
`110, to transmit the packet onto communications pathway
`110. Ilost computer 112 then transmits a packet onto cOm-
`munications pathway 110. The packet is detected by each of
`the host computers connected to the pathway, that is host
`computer 114, 116, 118, and 120. Because of address
`information contained within the packet, host computer 120
`receives the packet, and the other host computers discard the
`packet.
`
`EX 1015 Page 23
`EX 1015 Page 23
`
`

`

`5,805,808
`
`3
`the
`In modern communications systems, for example,
`FDDI Token Ring System, the bit rate on communications
`pathway 110 is 100 megabits per second, and as many as
`450,000 packets per second may travel on communications
`pathway 110. Consequently, each host computer 112, 114,
`116, 118, 120, must be capable of interpreting the address
`information, LLC information, and PID information of
`packets arriving at a wire speed of 100 megabits per second
`and at a rate of 450,000 packets per second.
`'l'uming now to ITIG. 2, there is shown an internal struc-
`ture of host computer 130. Ilost computer 130I may be any
`host computer such as host computers 112, 114, 116, 118,
`120 connected to communications pathway 110. Commu ni—
`cations pathway 110 connects to adapter 132. Adapter 132
`connects to host computer bus .134. Connected to host
`computer bus are the various components of host computer
`130, including CPU 136 and host computer memory 138.
`In operation, the apparatus of FIG. 2 operates as follows.
`A packet is detected traveling on communications pathway
`110 by adapter 132. Adapter 132, based on the addressing
`information in the packet, determines whether or not host
`computer 130 should receive the packet. [n the event that
`adapter 132 decides that host computer 130 should not
`receive the packet, adapter 132 simply does not pass the
`packet to other uniLs of host computer 130. In the event that
`adapter 132 decides that the packet should be received by
`host computer 130, the packet is transferred through con—
`nection 139 and host computer bus 134 to host computer
`memory 138. The present invention provides an improved
`mechanism, by increasing the information transferred with a
`packet, for the transfer of packets by adapter 132 to host
`computer memory 138. Accordingly, the host computer is
`not required to further process header information from the
`packets.
`Further, in operation, a packet arriving at host computer
`130 on communications pathway 110 is stored in a buffer
`memory in adapter 132. Once adapter 132 determines that
`the packet to be received by host computer 130, the packet
`is transferred to a buffer in host computer memory 138. The
`[Julfer located in host computer memory 138 is then emptied
`by a driver program running on host computer CPU 136. A
`driver program normally operates in host computer CPU 136
`to read and empty the buffers in host computer memory 138.
`Communications pathway 110I is shown in FIG. 2 as a
`token ring configuration. Communications pathway 110
`enters host computer 130 along leg 140. A packet passing
`into adapter 132 along leg 140 is repeated by adapter 132
`and then departs from host computer 130 along leg 142.
`From leg 142 the packet re-enters communications pathway
`110.
`
`‘10
`
`‘15
`
`10
`
`40
`
`'lhming now to FIG. 3, there is shown a block diagram of
`an adapter 132. A packet enters adapter 132 along leg 140
`from communications pathway 110. Apacket is repeated and
`departs from adapter 132 along leg 142 where it re-enters
`communication pathway 110. Leg 140 and leg 142 as well
`as communications pathway 110, are, in a preferred embodi-
`ment of the invention, an optical fiber communications
`pathway. Duplex connector 144 couples fiber optical cables
`of legs 140 and 142 to the combination transmitter and
`receiver 146. Receive converter 148 transmits the serial bit
`
`60
`
`stream along bus 150.
`Transmit converter 152 receives a serial bit stream along
`bus 154, and transmits the serial bit stream on leg 142 to
`communications pathway 110.
`In receive mode,
`the serial bit stream on bus 150 is
`received by interface 156.
`
`4
`
`Interface 156 manages receipt of packets from commu-
`nications pathway 110 through leg 140 through a sequence
`of three gate array computer chips: the elasticity butfer 160;
`the media access controller 162; and,
`the ring memory
`controller 164-.
`
`Serial to parallel conversion and parallel to serial conver-
`sion occurs at elasticity buffer 160.
`An address CAM 166 is used by the media access
`controller gate array 162 to decode the information carried
`in the MAC header ofan incoming packet. The MAC header
`ofthe incoming packet is described more fully hereinbelow
`with reference to FIG. 5A. The address CAM 166 may be
`used by the media access controller 162 in order to
`determine, from the MAC header of the packet, if a packet
`is to be received by the host computer. Alternatively, the
`media access controller 162 may be operated in promiscuous
`mode to accept all packets arriving at the host computer. The
`FC field is matched through hardwired logic within the
`media access controller 162.
`
`The DA field may be matched through a simple compare
`using a CAM to make this decision.
`In the event that a
`packet is determined to he one that is not to be received by
`the host computer, the packet is transferred no further than
`the media access controller 162. In the event that there is a
`
`the packet for further
`the MAC will accept
`DA match,
`filtering by the adapter. The packet is then transferred on ring
`memory controller bus, RMC bus 172 from ring memory
`controller 164 to packet memory controller 188.
`Parser gate array 180 snoops on RMC bus 172. Parser 180
`also is coupled to a local data base, parser data base 182.
`Parser 180 examines each of the fields of the incoming
`packet, where the fields are shown in detail in FIG. 5A. The
`parser, in combination with parser data base 182 and infor—
`mation received concerning the incoming packet on RMC
`bits 172, generates a forwarding vector. Parser 180 transfers
`the forwarding vector on line 184 to a control block 186
`located in packet memory 170.
`The forwarding vector transferred on line 184 controls the
`disposition of the packet through control of packet memory
`controller 188. The packet is transferred on RMC bus 172
`from ring memory controller 164 to packet memory con-
`troller 188. The packet is then stored by packet memory
`controller 188, into allocated buffers in packet memory 190.
`In the event that
`the packet is to be received by the host
`computer, the packet is then transferred on PM] ths 192,
`through system bus interface 194- to the system bus, host
`computer bus 134, as shown also in FIG. 2. By transfer
`through host computer bus 134,
`the packet
`is stored in
`butfers in host computer memory 138, also as shown in FIG.
`2. A driver process running on host computer CPU 136 then
`reads and empties the buffer in host computer memory 138.
`Referring again to interface 156, AM bus 191 provides
`connection between the adapter manager subsystem 202 and
`various chips contained in interface 156, including: parser
`180; elasticity buffer 160; media access controller 162; and
`ring memory controller 164. Adapter manager 202 commu-
`nicates through interface bus 204 with the system bus
`interface 194.
`
`Adapter manager 202 contains a CPU 210, a local
`memory 212, an EEPROM 214-, an interface 216 to bus 204,
`an AM bus 191, and a ROM 218. Adapter manager bus 220
`provides communication between the internal parts of the
`adapter manager subsystem 202, that is: CPU 210, memory
`212, EILPROM 214, interface 216, and ROM 218.
`Turning now to FIG. 4, there is shown a parser subsystem
`block diagram. Parser 180 is shown. Input from RMC bus
`
`EX 1015 Page 24
`EX 1015 Page 24
`
`

`

`5,805,808
`
`5
`172 is shown. Input from the parser data base 182 is shown
`on lines 230A, 230C, and 230D. Output from the parser is
`shown on forwarding vector line 184, FWD vector.
`In operation, parser 180 utilizes information obtained by
`snooping on RMC bus 172 in conjunction with data con-
`tained in parser data base 182 to produce forwarding vector
`184-. Forwarding vector 184 then controls the fate of a packet
`traveling on RMC bus 172 into packet memory controller
`188.
`Turning now to FIG. 5A, there is shown the field structure
`of a packet arriving along leg 140 from communications
`pathway 110. Parser 180 detects the bits in the fields shown
`in FIG. 5A by snooping on RMC bus 172. The letter
`designations shown in the fields depicted in FIG. 5A are a
`standard terminology utilized in the FDDl Standards by
`ANSI, and IEEE standard 802.2 for the Logical Link Con—
`trol for a local area network. The literal designations will be
`utilimd herein as reference numerals referring to the fields.
`The present example refers to the FDDI Standards and to the
`IEEE 802.2 Standard, however the invention applies to any
`standard packet format.
`The MAC header fields are next described.
`Field PRE is a preamble sequence, typically having 7'
`bytes.
`Field SD is a starting delimiter, and is one byte in length.
`Field I“C is a function code, and is one byte in length.
`Field DA is the destination address of the packet, and is
`six bytes in length.
`Field SA is the source address of the packet and is six
`bytes in length.
`The INFO field contains information for layers higher
`than the MAC layer of the communications protocol. The
`INFO field may be of length between 0 bytes and approxi—
`mately 4,500 bytes.
`Next, the MAC trailer fields are discussed.
`Field FCS is a frame check sequence and is four bytes in
`length.
`Field ED is an ending delimiter and is '/2 byte in length.
`Field FS is a frame status field and is one and V3 bytes in
`length.
`The fields SI), FC, DA, SA, and the trailing fields FCS,
`E1), FS, control the MAC layer of a station such as host
`computer 130. These fields are interpreted by cooperation
`between the elasticity buffer 160, the media access controller
`162, and the ring memory controller 164. The ring memory
`controller 164 also provides a count of the number of bytes
`in a packet, including the bytes in the before mentioned
`MAC layer fields plus the bytes in the INFO field.
`The ring memory controller 164 generates a butfer
`descriptor based upon interpreting the MAC header fields
`and trailer fields, counting the bytes in the packet, and
`verifying the Frame Check Sequence FCS. The buffer
`descriptor is transferred on RMC bus 172, after the packet
`transfer completes, to packet memory controller 188.
`In an LLC type packet as designated by the FC field, the
`first few bytes in the INFO field are a logical Link Control
`(LLC) level header, and are defined by the IEEE 802.2
`standard. The IEEE 8022 Standard defines three (3) LLC
`header fields, DSAP, SSAP, and CNTL. The MAC header
`fields and the Logical Link Control header are interpreted by
`parser 180. The byte size of the LLC header fields are as
`follows: DSAP field of 1 byte; SSAP field of 1 byte; CNTL.
`field of either I or 2 bytes.
`The PID field is present or absent in the packet depending
`upon the content of the DSAP, SSAP, and CN'IL fields. The
`PID field, when present,
`immediately follows the LLC
`header fields.
`
`‘10
`
`‘15
`
`2t]
`
`40
`
`60
`
`6
`In the event that the DSAP field has the value ofAA hex,
`{10101010 binary, representing the symbol SNAP),
`the
`SSAP field has the value AA hex (representing the symbol
`SNAP}, and the CNTL field has the value 03 hex
`{representing the symbol UI), then the packet is defined as
`a SNAP SAP packet. [11 the event that the packet is a SNAP
`SAP packet, then the PID field exists. The PID field is five
`(5) byte in length.
`In the event that the packet is not a SNAP SAP packet, the
`packet is then defined as a NON SNAP SAP packet. The PID
`field does not exist for a NON SNAP SAP packet.
`Each of the MAC layer, LLC layer, and PID fields
`contains a variety of allowable data. Parser 180 has as input:
`the results of reading the MAC layer fields as presented on
`RMC bus 172; and the results of parser 180 reading the
`MAC, the LLC header fields, and the PID field of the packet
`from the RMC bus 172. Parser 180 also has as input a parser
`database 182. A memory allocation diagram 230 for parser
`database 182 is shown in FIG. 513. By comparing the
`contents of the parser database 182 with the contents of the
`fields of the packet, the parser creates a forwarding vector
`for the packet. The forwarding Vector is transferred on line
`184 to control block 186 of the packet memory, and also to
`packet memory controller 188. The forwarding vector then
`determines the fate of the packet by providing information
`to the packet memory controller 188.
`Tuming now to FIG. 513,
`there is shown a memory
`allocation diagram 230 of parser database 182. Each block
`of memory allocation in the parser database 182 is defined
`as 256 words of72 bits each. The blocks are numbered and
`are referred to as BLOCK 0, BLOCK 1, etc. The 72 bits
`comprise 64 data bits and 8 parity bits. The parser database
`182 comprises a Static RAM (SRAM) type memory chip.
`The SRAM is used as a Content Addressable Memory, a
`CAM. The use of a SRAM memory chip as a CAM is fully
`disclosed in the United States patent application of Edgar,
`entitled “Content Addressable Memory”, application Ser.
`No. 546,414 filed Jun. 29, 1990, all disclosures of which are
`incorporated herein by reference. The parser database
`memory is organized in accordance with the memory allo—
`cation diagram 231] of FIG. SB.
`As shown in FIG. 5B,
`the organization of the parser
`database 182 is outlined. A more detailed description of
`parser database 182 is given hereinbelow in connection with
`the description of the operation of the parser database.
`Section 232, BLOCK 0, of the parser database is allocated
`to filtering the 15C field of the incoming packet. Section 234,
`BLOCK 1-6, is allocated to filtering the DA field of the
`incoming packet. Section 236, BLOCK 7—8, is allocated to
`filtering the FC and DA fields in combination. Section 238,
`BLOCK 9, is allocated to filtering the DSAP field of the
`incoming packet. Section 240, BLOCK 10-14, is allocated
`to filtering the PID field. Section 242, BLOCK 15—30, is
`allocated to filtering the combination of FC, DA, and DSAP
`or PID fields. Section 243, BLOCK 31,
`is allocated to
`filtering the userindex, UINDEX, and to filtering for a
`promiscuous user, as is described more fully hereinbelow.
`Turning now to FIG. 6, the fields of the forwarding vector
`are shown. The letter designations in the fields, as shown in
`FIG. 6, are used for reference numerals. The forwarding
`vector is the output produced by the parser as a result of
`filtering the header fields of the incoming packet against
`parser database 182.
`The packet is stored into packet memory 190 in pages of
`512 bytes length. In the event that a packet is longer than 512
`bytes, the packet is stored in a plurality of pages. A for-
`warding vector is generated for each page.
`
`EX 1015 Page 25
`EX 1015 Page 25
`
`

`

`5,805,808
`
`7
`PAR field is 1 bit, bit #15. The PAR field is a parity bit,
`and is used for a parity check for the bits of the forwarding
`vector as they are parallel transferred on the 16 fines of the
`forwarding vector line 184.
`COL field comprises two bits, bits 14 and 13. The COL
`field is normally used with the value 01.
`DIS field is 1 bit, bit #12. The DIS field is the discard field.
`The discard field bit may be either set or clear. With one
`value, the incoming frame on the RMC bus 172 is stored in
`packet memory 190. If the DIS bit is set to the other value,
`the incoming frame of line 172 is discarded by packet
`memory controller 188. That is, the frame is not received for
`storage in packet memory 190.
`llOST field is one bit, bit #11. In the event that IIOST bit
`has the value “'1”,
`the packet
`is destined for
`the host
`computer 130, as shown in FIG. 2. In the event that the
`MOST field bit has the value “0” the packet is destined for
`the adapter manager subsystem 202.
`TYPE field is of length 2 bits, bit 10 and bit 9. Values of
`the TYPE field and their meanings are as follows:
`00 the packet is an XIDE’l’esthther packet;
`01 the associated packet is an SMTMAC packet;
`10 the associated packet is a MOP packet;
`11 the associated packet is an error packet.
`The TYPE field is used, and is consequently only valid,
`when the packet is destined for the adapter manager sub-
`system 202. That is the type field is valid only when the host
`bit has the value “0”.
`
`UNK field is 1 bit in length, bit 8. The UNK bit designates
`the packet for a particular user defined as the "unknown”
`llSCT.
`
`‘10
`
`‘15
`
`10
`
`MI) field is 1 bit in length, bit 7. The MI) field indicates
`that there are multiple recipients for the packet when the MD
`bit is set.
`
`SOP field is one bit in length, bit 6. The SOP bit indicates
`the start of the packet, as described below.
`EOP field is one bit in length, bit 5. The EOP bit indicates
`the end of the packet, as described below.
`UINDEX field is five bits in length, bit 0, through bit 4.
`The UINDEX field is the user index. The user index
`
`40
`
`indicates a recipient process in host computer 130 for the
`incoming packet.
`The SOP field and the EOP field indicate to the packet
`memory controller 188 which page ofa packet was received.
`Each page ofa packet