Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 1 of 26 PageID #: 188
`
`Ulllted States Patent [19]
`Lawler et al.
`
`[54] HIGH SPEED CACHE MANAGEMENT UNIT
`FOR USE IN A BRIDGE/ROUTER
`[75] Inventors: Christopher P. LaWler, Wellesley;
`Shannon Q. Hill, Westford; David
`Lipschutz, Lexington; Thomas A.
`Radogna, Westborough; John A.
`Flanders, Ashland; Robert M, France,
`Littleton; Stephen L, Van Seters, Stow,
`all of Mass_
`
`[73] Assignee: 3Com Corporation, Santa Clara, Calif.
`
`[21] App]_ No; 08/927,336
`_
`Sep- 11, 1997
`Flled?
`[22]
`[51] Int. Cl? .................................................. .. H03M 13/00
`[52] US. Cl. ......................... .. 714/758; 370/392; 370/401
`5
`F, M f S
`h
`_
`[ 8]
`1e
`0 53512632
`/
`’
`
`’
`
`’
`
`’
`
`’
`
`’
`
`/5 ’
`18 '02
`
`[56]
`
`.
`References Cited
`
`U_S_ PATENT DOCUMENTS
`
`5:64Oj399
`5,708,659
`5,742,792
`
`sgflsi?et a1‘ """"""""""""" "
`370/232
`6/1997 Rostoker et a1‘
`370/392
`1/1998 Rostoker et al.
`4/1998 Yanai et al. ........................... .. 711/162
`
`US005978951A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,978,951
`Nov. 2, 1999
`
`9/1998 Isfeld et al. ...................... .. 395/20079
`5,802,278
`Primary Examiner—Emmanuel L. Moise
`‘353mg,’ ‘352m’ Or F W m—Wemgarten’ Schurgm’ Gagnebm
`ayes
`[57]
`
`ABSTRACT
`
`A method and cache management for a bridge or bridge/
`router providing high-speed, ?exible address cache manage
`ment. The unit maintains a network address cache and an age
`table, searches the cache for layer 2 and layer 3 addresses
`from received frame headers, and returns address search
`results. The unit includes an interface permitting processor
`manipulation of the cache and age table, and supports a
`4-Way set associative cache to store the network addresses.
`A plurality of functions implemented in hardWare enables
`softwi‘fe manépula?on ‘if tthilass?atedfachegmgfcachg
`Opera mg Yno .65 are 56 6.6a. 6'
`e um can 1 en 1 y an
`select dest1nat1on ports W1th1n a Load Balanced Port Group
`for frame forWarding. The unit utilizes Virtual LAN identi
`?cation in conjunction With a MAC address for lookup in the
`cache. A cyclic redundancy code for each address to be
`looked up in the cache is used as an index into the cache. If
`a cache thrash rate exceeds a predetermined threshold, CRC
`table values can be reWritten. Four time-sliced cache lookup
`units are provided, each consisting of a cache lookup con
`troller for comparing a received netWork address to an
`address retrieved from an identi?ed cache set.
`
`26 Claims, 14 Drawing Sheets
`
`12A
`
`MOTHERBQARD
`
`A
`30
`
`FRAME
`PROCESSOR
`M
`
`V
`
`AGE
`TABLE
`
`A130
`
`N'C
`0
`14"‘NIM o
`100/‘ MC
`1
`
`7
`
`(
`
`[7112
`NETWORK
`[' INTFC INPUT
`
`REGISTER FlLE
`
`L NETWORK
`INTFC OUTPUT
`REGISTER FILE
`k
`L
`123
`124
`
`_
`
`—
`
`NlC
`2
`N|M1
`NIC
`
`3
`
`I
`I
`.
`| NIM 3 |
`NIC
`7
`
`PIO REGISTER +
`SETS
`r105 F108
`104.1
`‘7
`CRC LRU VLD
`_ 1_2O_ __
`ENG TBL TBL
`P116 1
`‘
`‘
`‘
`CACHE
`LOOKUP
`I
`PACKETIZATION
`'
`ENGINE
`QUEUE
`I
`114i
`|
`t
`{\122
`0118 '
`CACHE
`I
`OUTPUT
`‘
`T |
`PACKET
`T I
`ASSEMBLY
`@ LOOKUP 7 |
`:
`CONTROLLER
`I
`@LC?ElQOlQPEEU
`
`F _ _
`[
`I
`|
`|~>
`'
`I
`
`23
`F
`
`ADDRESS
`CACHE
`
`ACA
`
`p26
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 2 of 26 PageID #: 189
`
`U.S. Patent
`
`Nov. 2, 1999
`
`Sheet 1 0f 14
`
`5,978,951
`
`wcmaxumm
`
`E8226:
`8%25
`08:95
`8%25
`9555
`
`xazwz
`x6262
`{262
`{0202
`
`2:82
`
`0:622
`
`2:82
`
`2:82
`
`3
`
`“3
`
`3
`
`~ 6H“
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 3 of 26 PageID #: 190
`
`Case 4:17-Cv-00141-ALM Document 17-2 Filed 05/19/17 Page 3 Of 26 PagelD #: 190
`
`ADDRESS
`
`
`
`MOTHERBOARD
`
`
`
`APPLICATION
`
`FRAME
`
`FIG. 2 mamaSH
`
`
`
`
`BACKPLANE r
`
`—-IlI-Il--_—l—
`
`
`
`
`NETWORK
`
`INTERFACE
`
`
`r PROCESSOR fl
`PROCESSOR x
`CACHE @
`MASTER BUFFER
`ADDRESS I
`
`
`ASIC
`3_2
`CACHE ASIC 26‘
`- —
`
`
`
`6661‘z'AON
`
`171J0Z139118
`
`PROTOCOL
`
`TAgLE
`I
`53
`
`
`-
`RECEIVE FRAME
`RECEIVE HEADER
`PROCESSOR "- PROCESSOR
`;'—=l- 48
`I—' --i —
`
`MODULE(s)
`
`VLAN
`
`MAPPING
`
`TABLE 4_7
`
`"‘
`LLC TABLE
`
`BUFFER
`
`RAM
`
`22
`
`RECEIVE STATE
`MACHINE
`
`RSEG ffl
`
`STATISTICS
`
`
`49
`PROCESSOR
`—
`
`VLAN
`60
`
`
`
`
`FORWARDING
`
`
`
`TABLE
`5—4
`
`TRANSMIT HEADER
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 4 of 26 PageID #: 191
`
`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 4 of 26 PagelD #: 191
`
`MOTHERB ARD
`
`30
`
`mamaSH
`
`6661‘z'AON
`
`I71J09199118
`
`ADDRESS
`
`I |
`
`LOOKUP
`
`CONTROLLER
`CACHE LOOKUP UNIT
`
`| |
`
`NETWORK
`
`INTFC INPUT
`
`REGISTER FILE
`
`NETWORK
`
`INTFC OUTPUT
`
`-
`
`PACKETIZATION
`
`ENGINE
`
`OUTPUT
`
`PACKET
`
`ASSEMBLY
`
`__.__.________1
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 5 of 26 PageID #: 192
`
`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 5 of 26 PagelD #: 192
`
`ACA bridge only cache address format
`
`Hash 13-0
`
`Set(1-0)
`
`CHO
`
`ACA bridge/route bridge cache address format
`
`n Seth—0)
`
`0 i0
`
`ACA route cache address format
`4
`
`15
`
`Sew-o)
`
`elm-0)
`
`FIG. 5
`
`
`
`JHBJBJ'sn
`
`6661‘Z°A0N
`
`171J017139118
`
`Bridge Cache
`
`SetO Set1 Set2 Set3
`
`
`
`
`SetO Set1 Set2 Set3
`
`Route Cache
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 6 of 26 PageID #: 193
`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 6 of 26 PagelD #: 193
`
`US. Patent
`
`N0V.2, 1999
`
`Sheet 5 0f 14
`
`5,978,951
`
`Cache configured with 1 Bank of 128KX8 SRAMs
`
`BankA
`
`
`11X128KX8
`
`
`
`aca_ac_ram_data(87—40)
`aca_ac_ram_adr_b(16—0)
`aca_ac_ram_oe_b_l
`aca_ac_ram_we_b_l
`aca_ac_ram_data_(39-0)
`
`FIG. 6A
`
`Cache configured with 2 Banks of 64KX16 SRAMs
`
`
`
`ACA
`BankA 6x64kx 16
`
`aca_ac_ram_adr_a(15-0)
`
`aca_ac_ram_oe_a_l
`aca_ac_ram_we_a_|
`
`
`aca_ac_ram_data(87—0)
`
`aca_ac_ram_oe_b_i
`
`aca_ac_ram_adr_b(15-0)
`
`
`BankB 6x64kx 16
`
`FIG. 6B
`
`Cache configured with 1 Bank of 64KX16 SRAMs
`
`
`ACA
`BankA 6x64kx 16
`
`aca_ac_ram_adr_a(15-0)
`
`aca_ac_ram_oe__a_l
`
`aca_ac_ram_we_a_l
` aca_ac_ram_data(87-0) aca_ac_ram_adr_b(15—0)
`
`
`
`aca_ac_ram_oe_b_|
`aca_ac_ram_we_b_|
`
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 7 of 26 PageID #: 194
`
`U.S. Patent
`
`N0v.2, 1999
`
`Sheet 6 0f 14
`
`5,978,951
`
`200 q
`RECEIVE PACKET OF
`HEADER ADDRESSES
`FROM FHP IN INPUT
`REGISTER FILE
`
`202
`
`MAC SA
`RECEIVED?
`
`204\
`CRC ENGINE RECEIVES
`CACHE SIZE AND MODE
`FROM PIO REGISTER
`SETS LOADED vIA FP
`206%
`CRC PERFORMS HASH
`ON MAC SA USING OAOHE
`CONFIGURATION INFO
`AND PROTOCOL IO
`208_\
`I
`PACKETIZATION ENGINE
`USES HASH TO RETRI EVE
`VALUES FROM LRU AND
`VALID TABLES
`2101
`PACKETIZATION ENGINE
`PUTS HASH, MAC SA,
`PROTOCOL ID IN
`PACKET AND LOADS
`CACHE LOOKUP QUEUE
`
`G
`
`212\
`RECEIvE PACKET OF
`HEADER ADDRESSES
`FROM FHP IN INPUT
`REGISTER FILE
`
`MAC OR
`NETWORK DA
`RECEWED?
`
`214w
`CRC PERFORMS HASH
`ON DA (MAC OR
`NETWORK) USING CACHE
`CONFIGURATION INFO
`AND PROTOCOL ID
`216“
`PACKETIZATION ENGINE
`USES HASH TO RETRIEvE
`vALUES FROM LRU AND
`vALID TABLES
`218'\
`PACKETIZATION ENGINE
`PUTS HASH, DA‘
`PROTOCOL ID IN
`PACKET AND LOADS
`CACHE LOOKUP QUEUE
`
`FIG. 7A
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 8 of 26 PageID #: 195
`
`U.S. Patent
`
`Nov. 2, 1999
`
`Sheet 7 0f 14
`
`5,978,951
`
`2% @
`
`LOOKUP UNIT CONTROLLER
`STRIPS PACKET FROM CACHE I
`LOOKUP QUEUE AND ADDS
`SET # AND VALID BIT
`
`SELECT NEXT
`SET NUMBER
`
`WAIT ONE
`CLOCK CYCLE
`
`LOOKUP CONTROLLER READS
`CACHE USING HASH
`CONCATENATED W/ SET #
`
`READ DATA VALUE ASSOCIATED
`WITH THIS CACHE ADDRESS
`
`é
`
`FIG. 7B
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 9 of 26 PageID #: 196
`
`U.S. Patent
`
`Nov. 2, 1999
`
`Sheet 8 0f 14
`
`5,978,951
`
`IDENTIFY PROPER OUTPUT
`PACKET ASSY FOR THIS LOOKUP
`238“
`I,
`OUTPUT PACKET ASSY FILLS
`NETWORK INTERFACE OUTPUT
`REGISTER FILE W/FRAME ID INFO
`
`240-‘
`
`I:
`
`OUTPUT PACKET ASSY FILLS
`NETWORK INTERFACE OUTPUT
`REGISTER FILE W/LOOKUP
`STATUS AND DATA
`
`242
`
`SA & DA
`DONE FOR
`THIS FRAME
`ID?
`
`244 ‘j
`OUTPUT PACKET ASSY SIGNALS
`RHP AND RHP TO RETRIEIVE
`
`@
`
`FIG. 7C
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 10 of 26 PageID #: 197
`
`U.S. Patent
`
`Nov. 2, 1999
`
`Sheet 9 of 14
`
`5,978,951
`
`Field
`‘Protocol ID
`Destination address length
`Receive port
`Sequence number
`Reserved for future use
`Frame control
`LEC ID
`VLAN ID
`Source address
`Destination address
`Unused
`
`NIC to ACA data
`Nibbles
`2
`2
`2
`2
`2
`2
`6
`2
`12
`40
`3
`
`cluq bits
`127-120
`119-112
`111-104
`103-96
`95-88
`87-80
`79-56
`55-48
`47-0
`159-0
`
`FIG. 8
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 11 of 26 PageID #: 198
`
`U.S. Patent
`
`Nov. 2, 1999
`
`Sheet 10 0f 14
`
`5,978,951
`
`ACA to NIC data
`Bridged Frame
`
`_Unicast
`__
`Protocol ID
`Frame control
`DA VC handle
`
`SA search status
`SA address state
`DA search status
`DA address state
`
`Unused
`Unused
`
`Unused
`RHP vlan ID
`Unused
`
`lylulticast
`_
`Protocol ID
`Frame control
`DA VC handle
`
`SA search status
`SA address state
`DA search status
`DA address state
`
`Unused
`Unused
`
`Unused
`RHP vlan lD
`Unused
`
`Transmit virtual port
`LBPG mask
`
`Transmit virtual port
`LBPG mask
`
`
`
`DA adr group mask(31-24) DA adr group mask(23-0)
`
`
`
`_ RQSéWfédf-‘ffiii-511;;Iii-II}:fl-Li-If-L-f ..... DA vport mask
`
`DA adr group mask(31-0)
`
`DA adr group mask(31-O)
`
`DA learned port
`Discard bit, TX encap
`Receive virtual port
`Sequence number
`
`SA software tag
`DA software tag
`
`Puma multicast mask
`Receive virtual port.
`Sequence number
`
`SA software tag
`DA software tag
`
`Unused (12 bits)
`
`Unused (12 bits)
`
`FIG. 9A
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 12 of 26 PageID #: 199
`
`U.S. Patent
`
`Nov. 2, 1999
`
`Sheet 11 of 14
`
`5,978,951
`
`ACA to NIC data
`Routed Frame
`
`Unicast
`Protocol ID
`Frame control
`DA VC handle
`
`SA search status
`SA address state
`DA search status
`DA address state
`
`DA(47-24) ,
`DA(23-16)
`
`DA(15-0)
`RHP vlan lD
`ACA vlan lD
`
`Multicast
`Protocol ID
`Frame control
`DA VC handle
`
`SA search status
`SA address state
`DA search status
`DA address state
`
`Parent port mask
`Forward port mask(23-16)
`
`Fonlvard port mask(15-O)
`RHP vlan lD
`ACA vlan lD
`
`Transmit virtual port
`LBPG mask
`
`Transmit virtual port
`LBPG mask
`
`QOS(39-32)
`QOS(31-8)
`
`QOS(39-32)
`QOS(31-8)
`
`DA adr group mask(31-0)
`
`DA adr group mask(31-0)
`
`DA learned port
`Discard bit, TX encap
`QOS(7-0)
`Sequence number
`
`SA software tag
`DA software tag
`
`Unused (12 bits)
`
`Puma multicast mask
`k-f'RéSén/Qdj Ij-F-Z'j-I J51 "" .
`QOS(7-0)
`Sequence number
`
`if-l 513F553 I-‘j-T
`
`SA software tag
`DA software tag
`
`Unused (12 bits)
`FIG. 9B
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 13 of 26 PageID #: 200
`
`U.S. Patent
`
`NOV.2, 1999
`
`Sheet 12 of 14
`
`5,978,951
`
`Bridge cache address beat
`48 .47
`87
`86 80 79
`56 55
`Lock '-:I-J{Spa're_-j§
`Lec ID
`VLAN f
`Bridge cache unicast data beat
`9
`16 15
`32 31
`48 47 4544 40 39
`87
`56
`55
`Address port group
`Learned Bridg xmit Address
`Software
`Circuit
`port
`misc encap
`state
`tag
`handle
`
`0
`
`\
`
`MAC address
`
`Bridge cache muiticast data beat
`0
`16 15
`32 31
`48 47 4544 40 39
`87 I 80 79
`56 55
`Address port mask
`Puma Bridg
`Address
`Software
`Circuit
`mask misc
`state
`tag
`handle
`FIG. 10
`
`'
`
`Route cache address beat 0
`87
`86 _85_ 84 80 79
`Lock €==:Spare;j- Proto iD
`Route cache address beat 1
`87
`80 79
`
`Unusable
`
`i
`Network address(79-0)
`
`Network address(159-80)
`FIG. 11
`
`0
`
`0
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 14 of 26 PageID #: 201
`
`U.S. Patent
`
`NOV.2, 1999
`
`Sheet 13 of 14
`
`5,978,951
`
`Route cache unicast data beat 0
`0
`1615
`32 31
`48 47 4544 40 39
`87 80 79
`'64 63. _
`'56 55
`-'
`Dest ;_i;=j~Rg-ry-
`" '
`_
`-.;I_-_I;;4 Learned Route Xmit Address
`Software
`Circuit
`VLAN
`T5531
`11-; I"j-§-_-.j-j-I;"‘i_j
`port
`misc encap
`state
`tag
`handle
`
`Route cache unicast route ?ow data beat 1
`87
`
`MAC destination address
`
`40
`
`39
`
`008 ?ow data
`
`Route cache unicast bridge ?ow data beat 1
`87 ‘
`72 71
`=;-‘{~Resjertiedji
`
`Address port group
`
`40
`
`39
`
`QOS ?ow data
`
`0
`
`0
`
`Route cache muiticast data beat 0
`48 47 45444039
`87 80 79
`56
`55
`Dest
`Reserved
`Puma Route 31;;
`VLAN
`mask
`misc
`
`0
`1615
`32 31
`Software
`Circuit
`tag
`handle
`
`Route cache muiticast data beat 1
`64 63
`87
`Parent port mask
`
`Forward port mask
`
`40 39
`
`\
`QOS ?ow data
`
`0
`
`FIG. 12
`
`ACA cache status bits
`Bit descri
`Bit
`
`uai
`Leo id
`Broadcast
`Multicast
`
`resses on
`resses
`
`FIG. 14
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 15 of 26 PageID #: 202
`
`U.S. Patent
`
`Nov. 2, 1999
`
`Sheet 14 0f 14
`
`5,978,951
`
`Network address state field bits
`Bit description
`Bit position
`Multicast identi?er
`39
`CRC not required
`38
`Quality of service loss
`37
`Queue select high
`36
`Queue select low
`35
`Internal address
`34
`Noti?cation High
`33
`Noti?cation low
`32
`
`QOS ?ow data
`Bit description
`Class of service (COS)
`
`-;R@seneda~;a --- ~I=i-; """"""" ‘ I~-;;:-lj~‘;~i=:-;;1--_~i;-.-:3;:1353133441:.~::.::. ' Minimum packet size
`
`Bit positions
`39-36
`
`359323’? 31-28
`
`Token bucket depth
`Token bucket index
`QOS state ?ags
`QOS state ?ags
`Bit description
`QOS enable
`RSVP ?ow indicator
`Excess action code
`Excess monitor enable
`Excess loss eligible ?ag
`Excess transmit queue
`Bridge Misc ?eld
`Bit description
`
`Static
`Reset-‘led? ............................ _.
`
`27-16
`15-8
`7-0
`
`Bit position
`7
`6
`5-4
`3
`2
`1-0
`
`Bit position
`
`Bit description
`Regérjvejd-j._if.j.;I_{-.jj '''''
`Discard
`Alternate source address
`
`Bit position
`1311215‘Ij-f--;41.i~-}Ijs-}.‘ii-1f;
`46
`45
`
`FIG. 13
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 16 of 26 PageID #: 203
`
`5,978,951
`
`1
`HIGH SPEED CACHE MANAGEMENT UNIT
`FOR USE IN A BRIDGE/ROUTER
`
`RELATED APPLICATIONS
`
`Not Applicable
`
`STATEMENT REGARDING FEDERALLY
`SPONSORED RESEARCH
`
`Not Applicable
`
`BACKGROUND OF THE INVENTION
`
`Network devices such as bridges and routers are
`employed in networks Which are operating at relatively high
`speeds. Functions such as frame header parsing, address
`lookup, frame processing, and related functions have previ
`ously been performed primarily in softWare. SoftWare pro
`cessing of frames results in higher device latency, implicat
`ing a higher frame drop rate due to congestion and the
`necessity of providing expensive buffering.
`
`1O
`
`15
`
`SUMMARY OF THE INVENTION
`
`The presently disclosed cache management unit is also
`referred to herein as an Address Cache ASIC (ACA), though
`the functions and features presently described are also
`realiZed, in alternative embodiments of the invention, via
`any other hardWare structure. The ACA is preferably used as
`one element of a netWork device such as a bridge or
`bridge/router, and provides high-speed, ?exible address
`cache management. The ACA is responsible for: maintain
`ing a hardWare address table and a hardWare age table;
`searching the hardWare address table for layer 2 and layer 3
`addresses received from a Received Header Processing
`(RHP) element Which parses frame headers for address
`information; and returning address search results, including
`the destination port(s) for received frames, to a Received
`Frame Processor (RFP) element. The ACA includes an
`interface Which permits a Frame Processor to manipulate the
`hardWare address table and age table.
`A cache associated With the ACA stores data associated
`With each of plural netWork addresses. The ACA receives
`packets of source and destination addresses from RHP’s in
`the netWork device, and searches the associated cache for
`each address. The ACA responds to the appropriate RFP
`With a response packet Which indicates Whether the source
`and destination addresses Were located (hit) in the cache and,
`for each located address, includes data associated With that
`address. If there Was a hit, the RFP generates a transmit
`vector Which contains information Which permits the frame
`to be processed in hardWare at speeds approximating frame
`reception rates. The ACA supports a 4-Way set associative
`cache to store the netWork addresses. This hardWare imple
`mentation provides better performance than the binary
`search table employed in the prior art due to a signi?cantly
`shorter search time in the cache.
`The ACA, through a plurality of discrete functions imple
`mented by ACA hardWare, enables softWare manipulation of
`the associated cache. Such manipulation includes installing
`entries, removing entries, changing entries and diagnosing
`the memory. Entry installation by a processor executing such
`softWare is the mechanism by Which the cache learns neW
`addresses. One further function, the SEARCH function,
`enables automatic address processing and lookup in the
`cache by the ACA Without softWare intervention.
`The ACA provides four cache operating modes:
`DISABLE, LEARN, BRIDGE ONLY, and BRIDGE/
`
`25
`
`35
`
`45
`
`55
`
`65
`
`2
`ROUTE MODE. When in DISABLE mode, the cache is
`accessible only through diagnostic read and Write opera
`tions. In LEARN mode, address installation, as Well as
`diagnostic read and Write operations, are enabled. In
`BRIDGE ONLY mode, the cache is employed solely for
`storing data associated With bridge addresses. Lastly, in
`BRIDGE/ROUTE mode, the cache is divided into equal
`portions for layer 2 (bridge) address processing and for layer
`3 (route) address processing.
`In a netWork element Which supports Load Balanced Port
`Groups (LBPGs), a group of ports treated as a single
`high-bandWidth port, the presently disclosed ACA identi?es
`and selects destination ports Within the identi?ed LBPG for
`respective frame forWarding.
`When functioning in a netWork bridge Which supports
`Virtual Local Area Networks (VLANS), the present ACA
`utiliZes the VLAN identi?cation in conjunction With the
`MAC for address lookup in the cache.
`A cyclic redundancy code is generated for each address to
`be looked up in the cache by the ACA. The CRC code is used
`as the index for lookup Within the cache. As noted, the cache
`is 4-Way associative, meaning that there are four sets of
`addresses and data for each CRC code. If the thrash rate
`exceeds a predetermined threshold, softWare can reWrite the
`CRC table values, thus causing alternative CRC codes to be
`generated, and avoiding the high thrash rate problem.
`Finally, oWing to the fact that the cache itself is accessed
`at most once out of every four clock cycles for a single
`address search, the presently disclosed ACA provides four
`cache lookup units, each being provided With access to the
`cache every four clock cycles. Each cache lookup unit
`consists of a cache lookup queue for storing the CRC code
`of the address to be searched, and a cache lookup controller
`for pulling codes from the queue concatenated With a set
`number from a least-recently-used table value for the code,
`and compares the netWork address associated With the code
`to that of the identi?ed set. If the addresses match, the
`controller signals that the lookup is complete and moves on
`to the next code in the queue. OtherWise, When all sets are
`exhausted Without a match, the controller reports the failure
`to match and moves on to the next code in the queue.
`Thus, the presently disclosed ACA enables netWork
`address lookup to permit frame processing at high speed
`While enabling ?exible modi?cation and diagnosis of the
`cache via softWare instituted functions.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention Will be more fully understood by reference
`to the folloWing Detailed Description of the Invention in
`conjunction With the draWings of Which:
`FIG. 1 is pictorial diagram of a netWork device in accor
`dance With the present invention illustrating NetWork Inter
`face Modules and a Motherboard mounted to a backplane;
`FIG. 2 is a block diagram of a netWork device in accor
`dance With the present invention illustrating one NetWork
`Interface Module coupled to the Motherboard via a back
`plane;
`FIG. 3 is a block diagram of an Address Cache ASIC
`(ACA) according to the present invention, interfaced to an
`Address Cache, Frame Processor, and plural NetWork Inter
`face Modules;
`FIG. 4A illustrates the organiZation of at least a portion of
`the Address Cache of FIG. 3 con?gured as a Bridge Cache;
`FIG. 4B illustrates the organiZation of at least a portion of
`the Address Cache of FIG. 3 con?gured as a Route Cache;
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 17 of 26 PageID #: 204
`
`5,978,951
`
`3
`FIG. 5 illustrates the format of words used to address the
`Address Cache of FIG. 3;
`FIGS. 6A, 6B and 6C are block diagrams of various
`physical con?gurations of memory devices comprising the
`Address Cache of FIG. 3 in conjunction the ACA;
`FIGS. 7A, 7B and 7C collectively comprise a How
`diagram of the method of operation of the ACA and Address
`Cache according to the present invention;
`FIG. 8 illustrates the data content of a packet transmitted
`from a Network Interface Chip (NIC), associated with a
`Network Interface Module, to the ACA;
`FIGS. 9A and 9B illustrate the data content of bridged and
`routed frame packets transmitted from the ACA to a Net
`work Interface Chip (NIC);
`FIG. 10 illustrates bridge cache beat formats;
`FIGS. 11 and 12 illustrate route cache beat formats;
`FIG. 13 illustrates speci?cs of various ?elds of FIGS.
`10—12; and
`FIG. 14 provides a description of the status bits sent from
`the ACA to a Network Interface Chip.
`
`10
`
`15
`
`4
`The MBA 32, located on the motherboard 12, serves to
`provide global data buffer management of frames which
`reside in buffers in the Buffer RAM 22 disposed on respec
`tive Network Interface Modules 14.
`Each network interface module 14 includes a receive
`ASIC and a transmit ASIC, both of which are speci?c to the
`type of data traf?c supported by the respective network
`interface module (such as Ethernet, ATM and FDDI).
`Address Cache ASIC (ACA) Overview
`The principle functions of the Address Cache ASIC
`(ACA) 26 include maintaining hardware address tables,
`maintaining a hardware age table, searching the hardware
`address table for layer 2 and layer 3 addresses provided by
`network interfaces, returning address search results includ
`ing a destination port identi?er for received frames to the
`network interfaces, and providing a mechanism for software
`to manipulate the hardware address table and age table. A
`4-way set associative cache 28 (discussed subsequently) is
`employed to store network addresses.
`The main function of the ACA 26 is to look up network
`addresses in the cache 28. The ACA receives packets con
`taining two addresses, a source address and a destination
`address, from the Network Interface Chips (NICs) 100. The
`ACA 26 searches the cache 28 for each of these addresses
`and responds to the Network Interface Module (NIM) 14,
`and more speci?cally to the respective NIC that sent the
`packet after the searches are completed, by assembling a
`response packet and forwarding the packet to the respective
`NIC 100. The response packet indicates whether or not the
`addresses were found in the cache 28 and, for each found
`address, the packet includes data stored in association with
`the network address. A more detailed explanation of this
`process is provided subsequently.
`The ACA 26 also provides an interface for software to
`manipulate and diagnose the cache 28. A Frame Processor
`(FP) 30 allows software to install and remove network
`addresses and associated data from the cache 28. Although
`the ACA does not learn addresses by itself, it provides
`hardware assistance, through Programmable Input/Output
`(PIO) register sets 102, in installing addresses in the cache
`at a rate of approximately 500K addresses per second. The
`FP 30 also provides a software path (soft path) accessible
`into an age RAM and hardware assistance during the aging
`process.
`The ACA 26 runs at speeds approximately the frame
`reception rate (wire speed) to avoid a costly and complex
`queuing system for received frames. To achieve wire speed,
`the ACA handles 4 million packets per second from the NICs
`100. In contrast, received frames handled by software can be
`processed at approximately 1/2 million packets per second.
`Since each packet from a NIC 100 contains two addresses
`(SA and DA), the ACA 26 must be able to search the entire
`cache 8 million times per second, or 4.5 cycles per search at
`an ACA clock rate of 37.5 MHZ.
`The cache 28 stores data link and network layer addresses.
`As described later, the cache can be con?gured as a bridge
`only cache or as a split bridge/route cache. The bridge cache
`store both data link layer SAs and DAs, while the route
`cache store network layer DAs and link layer SAs.
`If a frame is intended for a destination address which is
`not in the cache 28, the frame is transmitted out all ports
`under software control. If a reply frame is received from the
`device having the uncached MAC address, the port associ
`ated with the previously unknown DA address becomes
`known and the frame is forwarded via a high-speed hard
`ware forwarding path within the device 10 since the reply
`frame destination address (the original source address) is
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`FIGS. 1 and 2 Overview
`Referring to FIGS. 1 and 2, a bridge/router network
`device 10 for use in a telecommunications network includes
`a motherboard 12 and at least one network interface module
`14. Each of the network interface modules 14 interfaces to
`the motherboard 12 through a backplane 16.
`Each network interface module 10 includes at least one
`input port 18 through which data units such as frames,
`packets and cells are received and at least one output port 20
`through which data units are forwarded downstream for
`receipt by another network device. In particular, the ports
`provide connections via communication links to other
`devices in the network. Incoming data units may be bridged,
`routed, translationally routed or ?ltered.
`In one embodiment of the presently disclosed network
`device 10, four slots are provided for network interface
`modules 14. Each slot may be populated with an Ethernet,
`FDDI or an ATM UNI interface module. In a preferred
`embodiment, each 10/100 megabyte Ethernet network inter
`face module 14 includes six input/output ports, each FDDI
`network interface module 14 includes six input/output ports,
`and each gigabit Ethernet network interface module 14
`includes one input/output port. An ATM network interface
`module 14 includes four OC3 input/output ports or one
`OC12 input/output port.
`Elements in the motherboard 12 and interface modules 14
`are responsible for data unit reception and transmission,
`parsing of data link and network layer headers within
`received frames, look-up of source and destination Media
`Access Control (“MAC”) and network layer addresses and
`for making forwarding decisions regarding the received
`frames.
`The motherboard 12 includes an address cache ASIC
`(“ACA”) 26 with an associated cache 28, a Frame Processor
`30, an application processor 31 and a Master Buffer ASIC
`(“MBA”) 32.
`The ACA 26 serves to perform look-ups on source and
`destination addresses (SAs and DAs) passed to the ACA
`from a Receive Header Processor (“RHP”) within the
`respective network interface modules 14. The ACA 26 is
`capable of looking up MAC addresses for bridging support
`and Network Layer destination addresses for routing sup
`port.
`
`25
`
`35
`
`45
`
`55
`
`65
`
`

`

`Case 4:17-cv-00141-ALM Document 17-2 Filed 05/19/17 Page 18 of 26 PageID #: 205
`
`5,978,951
`
`5
`known and included in the cache. SoftWare updates the
`cache to include the address of the station having the
`original, unknown destination address (the subsequent
`source address). Software also updates the cache 28 if the
`ACA 26 determines that the source address data received
`does not agree With the source address data stored in the
`cache. This situation may arise in the event a device is
`moved such that frames it originates are received at a
`different port of the device 10. The ACA 26 also makes a
`determination of Whether the destination address and the
`source address are on the same segment, and if so, constructs
`a packet indicating this situation to the RFP 46, Which Will
`inhibit retransmission of the frame.
`In a preferred embodiment, the address cache 28 is 4-Way
`set associative, can vary in depth up to a maXimum of 16K
`roWs, and is 88 bits Wide. Each cache roW contains four
`cache entries, one per set. The cache 28 itself is implemented
`in SRAMS and the ACA 26 supports both X8 and X16
`devices. For a cache organiZed as bridge-only cache, there
`are tWo storage elements or “beats” per bridge cache set
`(FIG. 4A). For a bridge-route cache, there are four beats per
`route cache set (FIG. 4B). The speci?c format of these beats
`are found in FIGS. 10, 11 and 12. FIG. 13 provides details
`of What is stored in various ?elds in FIGS. 10, 11 and 12.
`At a high level, a cache lookup occurs as folloWs. An
`address to be searched (MAC SA, MAC DA, or netWork
`DA) is received by the ACA26. A Cyclic Redundancy Code
`(CRC) process is performed by a CRC engine 104 on the
`address to generate a CRC. This code is then used to identify
`a cache roW. There being four sets associated With each
`cache roW, the ACA uses a Least Recently Used (LRU)
`algorithm to identify a set order for address comparison, and
`a valid table is referenced to identify Whether any of the sets
`are invalid. From the latter tWo values, a most likely, valid
`set in the identi?ed cache roW is chosen, and the address
`value stored therein is compared against the address from
`Which the CRC Was generated. If a match occurs, the data
`stored in conjunction With that address in the cache set is
`retrieved and returned to the respective NIC 100. If no match
`occurs, the neXt valid set in the roW is selected and compared
`to the received address. When all valid sets have been
`searched Without a match, an indication thereof is forWarded
`to the frame processor 30 so that the received frame can be
`processed under softWare control.
`With reference to FIG. 5, the cache address generated by
`the ACA 26 for the purpose of addressing the cache 28 has
`three parts. A CRC generated from the address of interest is
`knoWn as a “hash.” The hash serves as a roW indeX into the
`cache, and identi?es a roW of four sets, i.e. sets 0—3 (see also
`FIGS. 4A and 4B). The set indeX identi?es one of four cache
`sets in the roW. A Cache Line Index (CLI) identi?es a line
`(or “beat”) Within a cache set; the CLI is one bit for the
`bridge cache and tWo bits for the route cache. For bridge/
`route addresses, each half of the cache 28 is addressed
`differently. The most signi?cant bit of the cache address
`indicates Whether the address is for the bridge or route cache
`searching.
`The ACA 26 accesses the cache 28 once per cycle. In the
`Worst case, the ACA must read and compare to the address
`beat of all four sets before a match (or “hit”) occurs.
`Subsequent to a hit occurring, a cycle is needed to read the
`associated data beat, for a total of ?ve cycles. This is more
`than the 4.5 cycle maXimum required to operate at Wire
`speed. HoWever, if the hit occurs on the ?rst, second or third
`compare, the total time is up to 4 cycles, beloW the maXi
`mum. On average, the search time Will be beloW the 4.5
`cycle threshold.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`HoWever, the presently disclosed ACA 26 is provided
`With a fallback option. The number of addresses queued up
`to be searched is monitored, and if it reaches a given
`threshold, the ACA 26 operates in a degraded mode Where
`the maXimum number of sets searched is reduced. When the
`number of enqueued searches falls beloW the threshold
`again, the normal search mode involving the search of up to
`all four sets is resumed.
`While each route address set is provided With four beats,
`tWo for address and tWo for data, not every lookup of a route
`address Will require comparison against both address beats.
`If the route netWork layer destination address is less than ten
`bytes in length, the second address beat is not used. Both
`data beats are used regardless of the length of the address
`compared.
`For a short route address (less than ten bytes), the Worst
`case search requires four address compares, and tWo cycles
`for data retrieval. All route frames have a MAC layer SA
`Which has a Worst case search of ?ve cycles, as above.
`Therefore, the ACA 26 processes route frames With short
`addresses in eleven cycles, Worst case. In degraded mode,
`limiting the number of sets searched per roW, the ACA 26
`does three searches on the MAC layer SA and three searches
`on the netWork layer DA. The maXimum search time is then
`reduced to an acceptable nine cyc