`Hasani et al.
`
`54 REAL TIME PARSER FOR DATA PACKETS
`IN A COMMUNICATIONS NETWORK
`
`75 Inventors: Santosh K. Hasani, Nashua, N.H.,
`Satish L. Rege, Groton; Mark F.
`Kempf, Stow, both of Mass.
`
`73 Assignee: Digital Equipment Corporation,
`Maynard, Mass.
`
`21 Appl. No.: 838,678
`22 Filed:
`Apr. 9, 1997
`
`USOO.5805808A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,805,808
`Sep. 8, 1998
`
`4.905,138 2/1990 Bourne .................................... 395/650
`4.941,089 7/1990 Fischer .....
`... 364/200
`4,979,167 12/1990 McCool ...
`... 370/85.4
`4,991,133 2/1991 David et al. ............................ 364/900
`5,056,058 10/1991 Hirata et al. .
`. 364/900
`5,058,110 10/1991 Beach et al. ............
`... 370/85
`5,067,104 11/1991 Krishnakumar et al.
`395/375
`5,228,083 7/1993 Lozowick et al. .......................... 380/9
`5,235,644 8/1993 Gupta et al. .
`... 380/40
`5.249,292 9/1993 Chiappa ......
`... 395/650
`5,361,353 11/1994 Carr et al. ............................... 395/700
`
`Primary Examiner Alpesh M. Shah
`O
`O
`Attorney, Agent, or Firm-Christine M. Kuta; A. Sidney
`Related U.S. Application Data
`Johnston
`63 Continuation of Ser. No. 365,993, Dec. 29, 1994, aban-
`doned, which is a continuation of Ser. No. 814,997, Dec. 27,
`ABSTRACT
`57
`1991, abandoned.
`
`51 Int. Cl." - G06F 13/00 Aparser for reading bits of a packet has a set of logic circuits
`
`52) U.S. C. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 395/2002; 370/392
`
`implemented in computer chip; memory interacting with
`
`58 Field of Search ............................... 395/800, 200.15,
`395/200.2, 840, 841, 851, 853, 182.13;
`370/252, 351, 353, 389, 392, 401, 402;
`380/3, 4, 9, 28, 37, 42, 49, 50
`References Cited
`
`56)
`
`U.S. PATENT DOCUMENTS
`6/1989 Kobayashi et al. ....................... 370/94
`
`4,839,891
`
`the computer chip, the memory providing first data to the set
`of logic circuits, means for reading bits from any field 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.
`
`13 Claims, 21 Drawing Sheets
`
`PACKET
`MEMORY
`
`170
`
`SYSTEM
`BUS
`
`PAGE TABLE ENTRY
`
`156
`
`INTERFACE
`
`190
`PACKET
`MEMORY
`
`RMC
`BUS
`
`134
`
`
`
`
`
`
`
`
`
`ACTIVE
`BULKHEAD
`144
`
`NOAC EX1064 Page 1
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 1 of 21
`
`5,805,808
`
`
`
`130
`
`110
`
`110
`
`FIG. 2
`
`NOAC EX1064 Page 2
`
`
`
`US. Patent
`
`Sep. 8, 1998
`
`Sheet 2 0f 21
`
`5,805,808
`
`oHmo§mme§mwmezmmqmfi.m0§E92
`
`VMOENE
`
`
`
`mDmEvdfl2‘5.me
`
`8H
`
`62
`
`NE
`
`N>HHU<
`
`Q<maADm
`
`v9
`
`NOAC EX1064 Page 3
`
`NOAC EX1064 Page 3
`
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 3 of 21
`
`5,805,808
`
`FIG. 4
`
`PARSER
`DATABASE
`
`182
`
`
`
`
`
`RMC CONTROL
`
`MISC, CONTROL
`
`7
`
`6
`
`5 4
`
`O
`
`PAR colds Host TYPE UNKMDsoPEOPUNDEx
`
`15 14 13 12
`
`1. 1
`
`10 9 8
`
`FIG. 6
`
`NOAC EX1064 Page 4
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 4 of 21
`
`5,805,808
`
`VS "?IH
`
`JLSHOEL •
`
`CIDX •
`CIIII •
`) | (z-1) | (1) | (1)
`
`
`
`AVNS NON •
`AIVS AVNS •
`:TVS
`
`
`
`YIGLAVI OVW
`
`
`
`X{{XVI OTTI
`
`
`
`
`
`JLVýNTRIOH JÆD?OWA ICHCIA
`
`
`
`NOAC EX1064 Page 5
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet S of 21
`
`5,805,808
`
`FC(8BITS)
`
`DAC8BITS x 6)
`
`
`
`238
`
`DSAP(8BITS)
`
`PID(8BITS x 5)
`
`72C64 DATA + 8 PARITY)
`
`232
`
`BLOCK1-6 (DAs)
`
`8
`BLOCK7
`(FILTERING INFORMATION
`FORFC AND DA
`COMBINATION)
`
`BLOCK9 (DSAPs) s
`
`
`
`BLOCK10-14 (PIDs)
`
`242
`Uindex (5 BITS)
`
`BLOCKS-30
`( FILTERING
`INFORMATION FOR
`FC.DA AND LLC
`COMBINATION)
`BLOCK31 (MORE
`FILTERING INFORMATION,
`243 -----------------------
`PROMISCUOUS USER
`FILTERING INFORMATION)
`
`
`
`
`
`
`
`FC CODE (3 BITS)
`
`FIG. 5B
`
`NOAC EX1064 Page 6
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 6 of 21
`
`5,805,808
`
`63 62
`
`DIs
`
`NUp
`
`32
`
`31
`
`Fccode
`
`29 28
`
`NUP
`
`O
`
`63
`
`62
`
`61
`
`O
`
`FIG. 8
`
`63
`
`62
`
`6 60
`
`59 58 57
`
`53 52 51
`
`Disendhatyre MDunarcs Nur
`
`O
`
`FIG. 9
`
`63
`
`62
`
`61
`
`unkcores - Erco
`.
`........... . .
`unkticalles
`
`FIG. 10
`
`NOAC EX1064 Page 7
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 7 of 21
`
`5,805,808
`
`63
`
`62
`
`61
`
`unkticolics - ico
`
`O
`
`FIG. 11
`
`7
`
`6
`
`S
`
`4
`
`Disrsvd MD under
`
`O
`
`FIG. 12
`
`nup
`
`53
`
`52
`
`res.
`
`63
`
`nur
`
`61. 60
`
`59 58
`
`type
`
`51
`
`44
`45
`46
`47
`48
`49
`50
`H/A H/A H/A DISH/AIDS H/A
`
`43
`HVA
`
`classistEEGEEGEANur
`
`0
`
`42. 41
`H/A
`
`FIG. 13
`
`63 62
`
`dis
`
`Nur
`
`58 57
`
`53
`
`52 51
`
`underes Nur
`
`O
`
`FIG. 14
`
`NOAC EX1064 Page 8
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 8 of 21
`
`5,805,808
`
`
`
`FIG. 15A
`
`
`
`FILTERING
`
`405
`
`DA
`FILTERING
`
`
`
`
`
`
`
`
`
`FCDA
`DISCARD
`
`
`
`
`
`PROM USER
`FILTERING
`
`FIG. 15C
`
`
`
`USER
`VALIDITY
`FILTERING
`
`NOAC EX1064 Page 9
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 9 of 21
`
`5,805,808
`
`405
`
`DA FILTERING
`
`STORE 3 BIT FC CODE
`
`410
`
`READ DATABASE FOR
`DA 6 TMES AND GET
`FINAL 63-BIT MASK
`
`412
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`41
`
`DOES
`AMC
`USER.EXIST
`(FROM
`CSR 1)
`
`OBTAN 6-BT
`DANDEXFROM
`63-BIT MASK
`
`
`
`
`
`
`
`
`
`
`
`
`
`PROMUSER
`FILTERING
`
`APPEND 6-BIT
`AMCNDEX
`TO FC CODE
`
`APPEND 6-BT DA
`INDEXTO FC CODE
`
`
`
`418
`
`FC AND DA
`FILTERING
`
`FIG. 15B
`
`NOAC EX1064 Page 10
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 10 of 21
`
`5,805,808
`
`
`
`
`
`466
`
`N
`
`S
`DSAP =
`NULL
`
`Y
`
`READ IDATABASE FOR
`PID 5 TIMES & GET
`63-BIT MASK
`
`IS
`AP =
`AA
`
`
`
`470
`
`468
`S
`NULL
`S-G)
`NABLED
`NULL
`DSAP
`FILTERING
`
`Y
`
`GET DSAP 63-BIT MASK
`FROM DATABASE
`
`476
`
`490
`
`ANY UNKNN
`USER (FROM
`CSR 1)
`
`
`
`
`
`
`
`464
`
`474
`
`GO
`
`SNAP
`DSAP
`FILTERNG
`
`492
`
`PROMUSER
`FILTERING
`
`OBTAIN 6-BIT LLC
`INDEX FROM 63-BIT
`MASK
`
`APPEND 6-BIT INDEX
`TO PREVIOUS 9-BIT
`INDEX
`
`494
`
`APPEND 6-BIT UNK
`INDEX TO PREVIOUS
`9-BIT INDEX
`
`Firing
`
`FIG. 15D
`
`NOAC EX1064 Page 11
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 11 of 21
`
`5,805,808
`
`488
`
`
`
`
`
`READ FC, DA,
`& LLC DATA
`FROM DATABASE
`
`500
`
`FCDALLCYNY
`DISCARD
`
`PROM USER
`FILTERING
`
`READ FC, DA, & LLC USER
`DATA FROM DATABASE
`WITH FCDALLC INDEX
`
`506
`
`NONSNAP-SAP
`FILTERING
`
`COPY H/ACSNAP), TYPE, MD,
`INDEX IN FV
`
`512
`
`FIG. 15E
`
`514
`
`USER
`VALIDITY
`FILTERING
`
`
`
`
`
`
`
`
`
`
`
`NOAC EX1064 Page 12
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 12 of 21
`
`5,805,808
`
`510
`
`NON SNAP SAP
`FILTERING
`
`520
`
`
`
`
`
`IS
`THIS
`CLASS 1
`USER
`
`
`
`522
`
`NL COPY H/ACUSLLC), TYPE,
`MD, UINDEX IN FV
`
`530
`
`Y
`
`N
`
`524
`532 GD
`USER
`VALIDITY
`FILTERING
`
`Y
`
`S34
`
`CLASS 1
`XID/TEST
`FILTERING
`
`RESPONSE
`
`COMMAND
`
`536
`
`542
`
`COPY HIACUI), MD, TYPE,
`UINDEX IN FV
`
`540
`
`RUI NY
`DISCARD
`
`N
`
`PROM USER
`FILTERING
`
`538
`
`COPY H/ACRUI), MD, TYPE,
`UINDEX IN FV
`
`544
`
`USER
`VALIDITY
`FILTERING
`
`546
`
`USER
`VALIDITY
`FILTERING
`
`FIG. 15F
`
`NOAC EX1064 Page 13
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 13 of 21
`
`5,805,808
`
`532
`
`550
`
`CLASS 1 XID / TEST
`FILTERING
`
`552
`
`554
`
`N
`
`COT Y
`DISCARD
`
`556
`
`Y
`
`N
`
`PROMUSER
`FILTERING
`
`COPY H/ACCOT), TYPE,
`MD, UINDEX IN FV
`
`560
`
`558
`
`USERVALIDITY
`FILTERNG
`
`RESPONSE
`
`COMMAND
`
`570
`
`562
`
`COPY H/ACRXT), MD,
`TYPE, UINDEX INFV
`
`COPY H/ACCXT), TYPE,
`MD, UINDEX INFV
`
`O
`
`USERVALIDITY
`FLTERNG
`
`CD"
`
`USERVALIDITY
`FILTERING
`
`FIG. 15G
`
`NOAC EX1064 Page 14
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 14 of 21
`
`5,805,808
`
`470
`
`NULL, DSAP
`FILTERING
`
`574
`
`N
`
`Y
`
`576
`
`578
`
`NULL NXT Y. Y
`DISCARD
`(FROM
`CR 1)
`
`PROM USER
`FILTERING
`
`
`
`N
`
`582
`
`580
`
`PUT TYPE is
`OTHER IN FV
`
`USER
`VALIDITY
`FILTERING
`
`592
`
`594
`
`NULL RXT Y. Y
`DISCARD
`(FROM
`CR 1)
`
`PROM USER
`FILTERING
`
`N
`
`584
`
`RESPONSE
`
`
`
`
`
`COMMAND
`
`586
`
`PUT TYPE -
`XID / TEST IN FV
`
`PUT TYPE
`OTHER IN FV
`
`596
`
`G) *
`
`USER
`VALIDITY
`FILTERING
`
`G).3"
`
`USER
`VALIDITY
`FILTERING
`
`FIG. 15H
`
`NOAC EX1064 Page 15
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 15 Of 21
`
`5,805,808
`
`474
`
`SNAP DSAP
`FILTERING
`
`600
`
`N
`
`Y
`
`602
`
`604
`
`
`
`SNAP NXT NY
`DISCARD
`(FROM
`CR 1)
`
`PROM USER
`FILTERING
`
`N
`
`608
`
`606- PUT TYPE =
`OTHER IN FV
`
`610
`
`RESPONSE
`
`
`
`
`
`
`
`COMMAND
`
`USER
`VALIDITY
`FILTERING
`
`614
`
`616
`
`SNAP RXT YNY
`DISCARD
`(FROM
`Sr, 1)
`
`PROM USER
`FILTERING
`
`N
`
`PUT TYPE =
`OTHER IN FV
`
`620
`
`GD5"
`
`USER
`VALIDITY
`FILTERING
`
`G);
`
`USER
`VALIDITY
`FILTERING
`
`FIG. 15
`
`NOAC EX1064 Page 16
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 16 of 21
`
`5,805,808
`
`PROM USER
`FILTERING
`
`630
`
`USE FC CODE TO
`READ PROM DATA
`
`
`
`PROM
`
`piscARD
`
`
`
`
`
`
`
`
`
`640
`
`BUFFER
`DISCRIPTOR
`FILTERING
`
`USER
`VALIDITY
`FILTERING
`
`NOAC EX1064 Page 17
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 17 Of 21
`
`5,805,808
`
`USERVALIDITY
`FILTERING
`
`
`
`HOST
`
`
`
`BUFFER
`DESCRIPTOR
`FILTERING
`
`FIG. 15K
`
`654
`
`BUFFER
`DESCRIPTOR
`FILTERING
`
`662
`
`BUFFER
`DESCRIPTOR
`FILTERING
`
`NOAC EX1064 Page 18
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 18 of 21
`
`5,805,808
`
`BUFFER
`DESCRIPTOR
`FILTERING
`
`670
`
`
`
`IS
`POTENTIAL
`DS BT
`SET
`
`N
`
`Y USET DISCARD
`BIT IN FV
`
`
`
`702
`
`IS
`ERROR YaN
`BIT SET
`
`Y
`
`
`
`
`
`
`
`704
`
`708
`
`710
`
`712
`
`PUT
`TYPE -
`11 NFV
`
`SET H / A
`BIT IN FV
`TO 0
`
`N
`
`714.
`
`716
`
`FIG. 15L
`
`NOAC EX1064 Page 19
`
`
`
`WS 1
`
`WS2
`
`F Fc
`D DA
`D DA
`SA
`SA
`808 DSAP |ssAP CNTL PID
`
`8 02
`
`816
`
`
`
`
`
`
`
`
`
`
`
`801D
`- 802A
`O
`1805A
`8 .''' 4806
`READ FC
`160
`803
`
`814
`
`814A
`
`810
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 19 of 21
`
`5,805,808
`
`--
`p1 800
`- 4. BYTES
`C/A
`
`
`
`
`
`801A
`801B
`
`DATA
`
`x F t
`
`x
`
`READ IDA
`1.
`818
`820
`
`START
`LOGIC
`FLOW
`
`811
`
`815 - 824 /
`READ FC DARAM
`READ IDSAP
`830A
`
`822
`
`A/C OFD
`
`DATA
`
`A/C OF OWN
`
`880
`
`960
`1040
`
`1120
`
`DECODE RMC
`BUFFER
`DESCRIPTOR
`828-N
`READ
`PID 830B
`4. 831
`READ FC DALLC
`1200 -TA
`READUSERINFO
`1280 833 TS
`READ PROMINFO
`-r 834
`
`1360
`
`2240
`
`TIME UNIT = mS
`
`EXECUTE REST OF ALGORTHM
`838 y
`Y
`
`2240
`
`FIG. 16
`
`NOAC EX1064 Page 20
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 20 of 21
`
`5,805,808
`
`900
`
`
`
`902 RMCAD C 31:0
`NRMCPAR <3:0>
`904
`NRMCRO L
`905,
`906 RMCRW
`NRMCDTACK L
`
`907 RMCOWN
`NRMCGT L
`
`NPAC 3:0
`
`NPD a 15:0s
`
`RMC
`- REQUEST
`RMC READ
`OR WRITE
`> BY MEMORY
`CONTROLLER
`GRANT BY
`MEMORY
`
`NPPAR < 1:0s
`PARSELL
`NPRW
`PARINT L
`-dim-R-H PARSER
`GA
`(195 USED
`I/Os + POWER
`& GND)
`
`PARTRI L
`VN
`IVOUT
`-GHammam
`PAROUT
`
`BYTCLK
`
`SYMCLK
`FINIT L
`
`RAMADD C 12:02
`922
`RAMCS L C 7:0>
`RAMDP a 71:0. T924
`RAMRW T 926
`RAMOE L-N.
`928
`
`FVRDYL
`FVOEL 910
`FVDATA-14:0>-1
`FVPAR 1912
`PKTDISN
`930
`
`SMSEL C2:0>
`
`PARSMC 4.0 e
`
`FIG. 17
`
`NOAC EX1064 Page 21
`
`
`
`U.S. Patent
`
`Sep. 8, 1998
`
`Sheet 21 of 21
`
`5,805,808
`
`15
`
`14,
`
`13
`
`12
`
`Rrur size Rw
`
`11
`
`10
`
`no
`
`O
`
`O
`
`O
`
`FIG. 18
`
`FIG. 19
`
`FIG. 20
`
`15
`
`UVR 1.
`
`15
`
`UVR 2
`
`NOAC EX1064 Page 22
`
`
`
`1
`REAL TIME PARSER FOR DATA PACKETS
`IN A COMMUNICATIONS NETWORK
`
`5,805,808
`
`This is a continuation of Ser. No. 08/365,993, filed Dec.
`29, 1994, now abandoned, which is a continuation of Ser.
`No. 07/814,997, filed Dec. 27, 1991, now abandoned.
`
`5
`
`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.
`
`15
`
`25
`
`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 FDDI 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 those commonly used in packet FC fields.
`The more difficult 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
`50
`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 FDDI
`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.
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`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 INVENTION
`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 field 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 THE 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. 5B 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 of an entry in a parser database.
`FIG. 8 is a field diagram of an 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. 15I, FIG. 15J, FIG.15K, and
`FIG. 15L 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.
`
`DETAILED DESCRIPTION
`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 first node, Such
`as host computer 112, may desire to transmit a packet to host
`computer 120. Host computer 112, then gains permission,
`through the acceSS protocol for communications pathway
`110, to transmit the packet onto communications pathway
`110. Host 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.
`
`NOAC EX1064 Page 23
`
`
`
`5,805,808
`
`15
`
`25
`
`3
`In modern communications Systems, for example, the
`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.
`Turning now to FIG. 2, there is shown an internal struc
`ture of host computer 130. Host computer 130 may be any
`host computer such as host computers 112, 114, 116, 118,
`120 connected to communications pathway 110. Communi
`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. In 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 units 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
`40
`buffer 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 110 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.
`Turning 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. A packet 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
`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 buffer 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 of an incoming packet. The MAC header
`of the 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 be 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
`DA match, the MAC will accept the packet for further
`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
`bus 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 online 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 PMI bus 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
`buffers 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, EEPROM 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
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`NOAC EX1064 Page 24
`
`
`
`5,805,808
`
`15
`
`25
`
`35
`
`40
`
`S
`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 database 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 FDDI Standards by
`ANSI, and IEEE standard 802.2 for the Logical Link Con
`trol for a local area network. The literal designations will be
`utilized 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 FC 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 % byte in length.
`Field FS is a frame status field and is one and 2 bytes in
`length.
`The fields SD, FC, DA, SA, and the trailing fields FCS,
`ED, 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 buffer
`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 802.2 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 1 or 2 bytes.
`The PID field is present or absent in the packet depending
`upon the content of the DSAP, SSAP, and CNTL fields. The
`PID field, when present, immediately follows the LLC
`header fields.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`In the event that the DSAP field has the value of AA 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. In 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 SNAPSAP packet, the
`packet is then defined as a NON SNAPSAP 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. 5B. 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.
`Turning now to FIG. 5B, 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 of 72 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 230 of FIG. 5B.
`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 FC 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.
`
`NOAC EX1064 Page 25
`
`
`
`5,805,808
`
`15
`
`25
`
`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 lines 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.
`HOST field is one bit, bit #11. In