USOO6996099B1
`
`(12) United States Patent
`Kadambi et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,996,099 B1
`Feb. 7, 2006
`
`(54)
`
`(75)
`
`(73)
`
`(*)
`
`(21)
`(22)
`
`(63)
`
`(60)
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`NETWORKSWITCH HAVING A
`PROGRAMMABLE COUNTER
`
`Inventors: Shiri Kadambi, Los Altos, CA (US);
`Shekhar Ambe, San Jose, CA (US)
`Assignee: Broadcom Corporation, Irvine, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`Appl. No.: 09/527,999
`
`Notice:
`
`Filed:
`
`Mar 17, 2000
`Related U.S. Application Data
`Continuation-in-part of application No. 09/343,409,
`filed on Jun. 30, 1999.
`Provisional application No. 60/149.706, filed on Aug.
`20, 1999, provisional application No. 60/135,603,
`filed on May 24, 1999, provisional application No.
`60/124878, filed on Mar. 17, 1999.
`
`Int. Cl.
`(2006.01)
`H04L 12/56
`U.S. Cl. ...................................................... 370,389
`Field of Classification Search ........ 370/229-231,
`370/412-424,395.4–395.53
`See application file for complete Search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`6/1995 Chung
`5,423,015 A
`
`5,473,607 A
`12/1995 Hausman et al.
`Hoang et al.
`7/1998
`5,787,084. A
`6/1999
`5,909,686 A *
`Muller et al. ............ 707/104.1
`2/2000
`6,021,132 A *
`Muller et al. ............... 370/412
`7/2000
`6,094.435 A *
`Hoffman et al. ......
`... 370/414
`6,246,680 B1* 6/2001
`Muller et al. .....
`... 370/389
`6,263,368 B1* 7/2001
`Martin ....................... 709/224
`6,526,060 B1* 2/2003 Hughes et al. ........... 370/395.4
`6,643,260 B1* 11/2003 Kloth et al. ................ 370/235
`FOREIGN PATENT DOCUMENTS
`
`1/1999
`1/1999
`1/1999
`1/1999
`1/1999
`1/1999
`1/1999
`
`WO99/00938
`WO
`WO99/00939
`WO
`WO99/00944
`WO
`WO99/00945
`WO
`WO99/00948
`WO
`WO99/00949
`WO
`WO99/00950
`WO
`* cited by examiner
`Primary Examiner-Chi Pham
`Assistant Examiner Thai Hoang
`(74) Attorney, Agent, or Firm-Squire, Sanders & Dempsey,
`LLP.
`
`(57)
`
`ABSTRACT
`
`A network switch for switching packets from a source to a
`destination includes a Source port for receiving an incoming
`packet from a Source, a destination port that contains a path
`to a destination for the packet, and a programmable counter
`unit for counting a number of packets of Selected packet
`types which are received by the Switch.
`
`8 Claims, 47 Drawing Sheets
`
`
`
`20a
`
`DATAPACKET
`
`112
`
`14a
`
`
`
`INGRESS
`SUBMODULE
`
`EGRESS
`SUBMODULE
`
`DISPATCHUNIT
`
`
`
`ARL & L3
`TABLES
`
`22a
`
`23a
`
`Ex.1026
`VERIZON / Page 1 of 81
`
`

`

`U.S. Patent
`
`US 6,996,099 B1
`
`II
`
`TVNYISILXH
`
`
`
`
`
`
`
`Ex.1026
`VERIZON / Page 2 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 2 of 47
`
`US 6,996,099 B1
`
`£8 ~)-S - - - - - - - - - - - --
`
`
`
`Ex.1026
`VERIZON / Page 3 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 3 of 47
`
`US 6,996,099 B1
`
`Fig.3
`
`Cn0
`
`Cnl
`
`Cn2
`
`Cn
`
`
`
`LOCKED AND
`SYNCTO EACH
`OTHER
`
`C-CHANNEL
`
`P-CHANNEL
`
`S-CHANNEL
`
`Ex.1026
`VERIZON / Page 4 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 4 of 47
`
`US 6,996,099 B1
`
`
`
`3.TOXOTTIÑO I
`
`KORIXKnWRX@X@WW)
`
`
`
`W NOI. LO?IS
`
`Ex.1026
`VERIZON / Page 5 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 5 of 47
`
`US 6,996,099 B1
`
`Fig.5
`
`PROTOCOL CHANNEL MESSAGES
`30 28 26 24 2220 18 1614 12 108 6 42 0.
`OPCP RESE NXT SRC DEST PORT | COS
`CRC
`ODE IPX RWEDICELL
`
`62 60 58 56
`
`44 42 40 3836 3432
`54 5250 48 I 46
`MODULEIDBTMAP
`
`30 28 26 24
`
`
`
`22
`
`20
`
`18 161412 1086 42 0.
`Bc McPORTBTMAP
`62 60 58 5654 52 50 48 I 46
`44 42 40 38 36 .3432
`if
`new checks M
`MMM.DDITIDIME
`30 28 26 24 2220 1816 412 1086 420
`UNTAGGED PORTBITMAP1 SRCPORT NUMBER(bit0.5)
`
`62 60 5356 54 5250 4846 44 42 40 38 3634.32
`v Age
`SRCPORT
`| REMOTEPORT
`
`30.28 26 24 2220 181614121086 42 0.
`CPU OPCODES
`TIMESTAMP
`IOISIS ISI stili? I ( It Is IST II 2
`
`Ex.1026
`VERIZON / Page 6 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 6 of 47
`
`US 6,996,099 B1
`
`Fig.6
`
`
`
`SIDE BAND CHANNEL MESSAGES
`30.28 26 24
`22 201816 412 1086 4
`OPCODE
`DEST PORT |
`SRCPORT
`DataLen
`DESTINATION
`DEWID
`
`O
`2
`COS C
`
`ADDRESS
`DATA
`
`Ex.1026
`VERIZON / Page 7 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 7 of 47
`
`US 6,996,099 B1
`
`Fig.7
`PRIOR ART
`
`
`
`LAYER SEVEN
`APPLICATION
`
`LAYERSIX
`PRESENTATION
`
`LAYER FVE
`SESSION
`
`LAYER FOUR
`TRANSPORT
`
`LAYER THREE
`NETWORK
`
`LAYER TWO
`DATALINK
`
`LAYER ONE
`PHYSICAL
`
`Ex.1026
`VERIZON / Page 8 of 81
`
`

`

`U.S. Patent
`
`US 6,996,099 B1
`
`8
`
`61
`
`<T?5->
`
`–
`
`
`
`
`
`JLINIA HOIW, ISIQI
`
`
`
`Byz
`
`
`
`ZI ILEIXOWI WJVCI
`
`BOZ
`
`Ex.1026
`VERIZON / Page 9 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 9 of 47
`
`US 6,996,099 B1
`
`S
`
`-1
`
`:
`
`s
`
`s
`
`N
`
`s
`
`s
`
`Ex.1026
`VERIZON / Page 10 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 10 of 47
`
`US 6,996,099 B1
`
`Fig.10
`
`60
`
`GBP
`
`70
`
`CPS CHANNEL
`
`R-CHANNEL32 BITS
`
`CELL
`7
`is:
`FM
`M---- EgM
`
`76
`
`76
`
`76
`
`a
`
`MAC TX FIFO
`
`in II.
`
`MAC TX FIFO
`
`MAC TX FIFO
`
`TX MAC | 40
`
`Ex.1026
`VERIZON / Page 11 of 81
`
`

`

`U.S. Patent
`
`US 6,996,099 B1
`
`
`
`+– I SINIT
`
`~*~ Z SINIT
`
`?– 9 SINIT
`
`Ex.1026
`VERIZON / Page 12 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 12 of 47
`
`US 6,996,099 B1
`
`
`
`
`
`ESTPACKET
`LENGTH =
`EGRESSMGR.
`INCOMING CELL
`COUNT
`
`2
`
`
`
`
`
`
`
`EST.
`CELL COUNT
`GBPCOUNT (EST
`CELL COUNT
`
`
`
`Ex.1026
`VERIZON / Page 13 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 13 0f 47
`
`US 6,996,099 B1
`
`Fig.13
`
`R-CHANNEL
`
`32
`3 GIL, JP, NP. (19:0GPID/CPID
`III
`PDNX
`
`PIDN
`134 /cell DATA
`PEN
`/ POINTER CPDMY
`SCHEDULER / /
`::/
`/
`F
`
`/
`
`r
`
`CBP
`
`- 19
`
`SO
`
`CMC -79
`
`76
`
`\
`
`3.
`
`TRANSACTION
`FIFO WITH 8
`COS
`ab
`PRIORITY Qs
`133
`
`COS
`MANAGER
`
`
`
`
`
`
`
`
`
`APF
`
`.." reu
`
`MAC TXFEFO
`
`TCU
`
`MRU
`
`UNTAG UNIT
`
`TXMAC
`
`40
`
`NXT CELLACK
`
`NXT CELL REQ
`
`36
`
`138
`
`Ex.1026
`VERIZON / Page 14 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 14 of 47
`
`US 6,996,099 B1
`
`DATA FLOW
`
`
`
`Fig.14
`
`232
`
`PORT BASED
`WLANTABLE
`
`231
`
`ARLENGINE
`(L2/L3SEARCH
`ENGINE)
`
`ARL TABLE
`+ L3 TABLE
`
`2
`
`RULES
`TABLE
`
`2 2
`
`BUFFER
`SLCER
`
`DISPATCH
`UNIT
`
`81-
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`CCHNL
`
`Ex.1026
`VERIZON / Page 15 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 15 of 47
`
`US 6,996,099 B1
`
`Fig.15
`
`
`
`FROM INPUT
`FIFO
`
`41
`
`TO RULES
`TABLE
`
`Ex.1026
`VERIZON / Page 16 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 16 of 47
`
`US 6,996,099 B1
`
`
`
`
`
`
`
`
`
`
`
`DATA POSLAVE
`
`ADDRESS 42a
`DATA y
`32
`3 2
`-
`ESLAVE
`POSLAVE
`DATA
`2CMASTER
`IF
`
`
`
`C-CHANNEL 81
`P-CHANNEL 82
`
`S-CHANNEL 83
`
`Ex.1026
`VERIZON / Page 17 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 17 of 47
`
`US 6,996,099 B1
`
`Fi 9 17 FFPPROGRAMMINGFLOW CHART
`
`FFP
`PROGRAMMING
`
`
`
`17-1
`
`IDENTIFY ALL THE
`PROTOCOL FIELDS
`OF INTEREST.
`
`DETERMINE PACKET
`TYPE ANDFILTER
`CONDITIONS.
`
`
`
`CONSTRUCTFILTER
`MASKDEPENDING ON
`FILTER CONDITIONS
`AND PACKETTYPE.
`
`SELECTINCLUSIVE OR
`EXCLUSIVE FILTER
`DEPENDING ON
`PROBLEMTYPE.
`
`17-2
`
`17-3
`
`17-4
`
`17-5
`
`7.7
`
`FILTER
`ONEGRESS
`
`
`
`
`
`
`
`
`
`USE INGRESS
`PORT MASK
`
`17-9
`
`
`
`
`
`
`
`
`
`CONSTRUCTRULES
`TABLE ENTRY.
`
`INSERT THIS ENTRY
`INTORULESTABLE,
`
`7-10
`
`17-11
`
`Ex.1026
`VERIZON / Page 18 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 18 of 47
`
`US 6,996,099 B1
`
`AGE TIMEREXPRED->
`STARTARLAGING
`PROCESS; START WITH
`THE FIRSTARLENTRY
`
`THE PORT BELONG TO
`THIS ARL MODULE
`
`8-1
`
`18-2
`
`Fig.18
`
`IS THE
`HIT BITSET OR
`ISASTATIC
`ENTRY
`
`DELETE THE ARLENTRY.
`SEND DELETEARLENTRY
`TOOTHERMODULES,
`INCLUDING CPU
`
`RESET THE HIT
`BIT IN THE ARL
`ENTRY.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IS THES
`THE LAST ENTRY
`IN THE TABLE
`
`
`
`
`
`START THE
`AGE TIMER
`-> DONE
`
`
`
`GO TO THE
`NEXT ARL
`ENTRY.
`
`Ex.1026
`VERIZON / Page 19 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 19 of 47
`
`US 6,996,099 B1
`
`
`
`SW1
`
`SW2
`
`Fig.19
`
`Ex.1026
`VERIZON / Page 20 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 20 of 47
`
`US 6,996,099 B1
`
`
`
`Fig.20
`FIELD
`
`-
`
`OFFSET
`FOR
`ETHERNETETHERNET
`I
`TAGGED UNTAGGED TAGGED
`UNTAGGED
`DESTINATION MACADDRESS MAC 6BYTES
`0
`||
`0
`||
`0
`||
`0
`SOURCEMACADDRESS
`MAC 6BYTEs
`6
`6
`6
`6
`PROTOCOLTYPE
`MAC
`BYTES
`2
`16
`20
`24
`BYTE
`NA TNA
`4
`18
`SOURCESAP
`802.3
`BYTE
`NA
`NA
`5
`19
`MAC 3 BTS
`NA
`14
`NA
`14
`802.pPRIORITY
`VLAN Id
`MAC 12BTs
`NA
`144b
`NA
`144b
`TOSPRECEDENCE
`IP
`3BITS
`15
`19
`23
`27
`DIFFERENTIATED SERVICES
`P
`6 BTS
`15
`19
`23
`27
`DESTINATION PADDRESS
`IP
`4BYTES
`30
`34
`38
`42
`PROTOCOL
`IP
`BYTEI
`23
`3
`35
`sourcer.
`It parts
`DistiNToro.
`It parts
`| |
`
`
`
`
`
`UDP
`
`UDP
`TCP
`
`|
`
`
`
`47
`
`|
`
`59
`
`55
`
`TCPCONTROL FLAGS
`(FOR ALIGNING ON BYTE
`BOUNDARY 2 BITS OF
`RESERVED BITS PRECEDING
`THIS FIELD IS INCLUDED)
`DATAAT OFFSET
`
`NA
`
`8 BYTES
`
`
`
`
`
`
`
`- 8 BYTES
`
`8BYTES
`
`DATAAT OFFSET 4 r BYTES
`
`
`
`DATA
`OFFSET
`FROM
`START OF START OF START OF START OF
`IPIPX
`HEADER HEADER HEADER HEADER
`
`
`
`OFFSET2 OFFSET2 OFFSET2 OFFSET2
`
`START OF START OF START OF START OF
`
`HEADER HEADER HEADER HEADER
`
`OFFSET3 OFFSET3 OFFSET3 OFFSET3
`
`HEADER HEADER HEADER HEADER
`
`OFFSET4 OFFSET4 OFFSET4 OFFSET4
`
`START OF START OF START OF START OF
`
`
`
`HEADER HEADER HEADER HEADER
`
`
`
`Ex.1026
`VERIZON / Page 21 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 21 of 47
`
`US 6,996,099 B1
`
`Filter Mask Format:
`Filter
`Counter
`Rem
`Enable
`(5b)
`Port
`(1b)
`(1b)
`NMA
`Data
`Enb
`Offset
`(1b)
`4 (7b)
`
`No Match
`Action
`(10b)
`
`Output
`Mod
`(5b)
`Data
`Offset
`3 (7b)
`
`Output
`Port
`(6b)
`Data
`Data
`Offset
`Offset
`1 (7b)
`2(7b)
`Field Mask
`Field Mask
`Fig.21 a
`
`TOS Prec
`(3b)
`
`DiffServ
`(6b)
`
`802.lp Prior
`(3b)
`
`Egress
`Egress
`Ingress
`Port Mask Modd Mask Port Mask
`(6b)
`(5b)
`(6b)
`
`Field Mask Format:
`Dest
`802. Wan TOS Dif Src
`Src
`Dest
`Dest
`Src
`Prot
`IP
`p
`Id
`Prec Serv
`IP
`SAP SAP
`Mac Mac type
`addr
`addr
`addr
`(2B) (1B)(B) Prio (12b) (3b)
`(6b)
`addr
`(4B)
`(68)
`(6B)
`(3b)
`(4B)
`TCPCnir Flags
`Data2
`Data 4
`Data 3
`(lB)
`(8B)
`(8B)
`(8B)
`Fig.21b
`
`Data 1
`(8B)
`
`
`
`Dest
`Src
`Prot
`Port
`Port
`IP.
`(lB) (2B)(2B)
`
`Ex.1026
`VERIZON / Page 22 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 22 of 47
`
`US 6,996,099 B1
`
`Address
`resolution
`
`22-1
`
`22-2
`
`22-3
`
`22-4
`
`22-5
`
`22-6
`
`22-7
`
`
`
`
`
`Parsing packet to
`extract selected
`fields
`
`
`
`Construct
`a field value
`
`
`
`
`
`Go through all
`filters and apply mask
`
`Concatenate mask results
`with filter number
`generate search key
`
`
`
`Search rules table
`for search key match
`
`Perform action as
`specified based on match
`and filter type
`
`Fig.22
`
`
`
`
`
`
`
`
`
`
`
`Ex.1026
`VERIZON / Page 23 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 23 of 47
`
`US 6,996,099 B1
`
`
`
`lect
`
`Port
`
`Filter
`Walue
`
`Fig.23
`
`Ex.1026
`VERIZON / Page 24 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 24 of 47
`
`US 6,996,099 B1
`
`30 28 26 24 22 2018 1614 12108 6
`Source IPAddress
`Multicast IPAddress
`L3 Port Bitmap
`L3 Module Bitmap
`
`
`
`
`
`Unused
`
`TTL
`Threshold
`
`4 20
`
`
`
`Fig.24
`
`Ex.1026
`VERIZON / Page 25 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 25 0f 47
`
`US 6,996,099 B1
`
`25-1
`
`25-2
`
`25-3
`
`25-4
`
`25-5
`
`Walidate
`IP checksum
`
`Search IP
`Multicast
`Table
`
`TTL Below
`TTL threshold
`
`
`
`
`
`
`
`
`
`
`
`
`
`Source
`Port Match
`
`
`
`YES
`Send to CPS Channel
`
`Fig.25
`
`Ex.1026
`VERIZON / Page 26 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 26 of 47
`
`US 6,996,099 B1
`
`
`
`s
`
`Ex.1026
`VERIZON / Page 27 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 27 Of 47
`
`US 6,996,099 B1
`
`271(2)
`
`26
`
`Fig.27b
`
`
`
`261
`
`SOC 10(1)
`
`Ex.1026
`VERIZON / Page 28 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 28 of 47
`
`US 6,996,099 B1
`
`90
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9.
`
`IP Multicast
`Table
`
`
`
`
`
`i BP warning. BPDisard,
`
`GBPFGBPAval
`
`
`
`Pk FIFO
`8 Queues.
`
`
`
`RFrom ICMor
`Grant to SM if
`Arbiteris Disabled
`
`Gnt to ICM or
`Req ToSM if
`Arbiteris Disabled
`
`Fig.28
`
`26
`
`Ex.1026
`VERIZON / Page 29 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 29 of 47
`
`US 6,996,099 B1
`
`*N GBPFully Yes E. 29-2
`
`packet
`
`29-3
`
`No.
`
`29-4
`
`Fig. 29
`
`29-5
`
`29-7
`
`29-9
`
`Yes
`
`Send to
`
`29-6
`
`L.
`G) Ye sal-'
`{G} No
`
`No
`
`Yes
`
`29-10
`
`Yes
`
`
`
`29-1
`TT. N. Yes
`KThreshold
`
`Search of IP
`Multicast
`Table
`
`No d
`
`29-12
`
`29-15
`
`29-14
`No
`
`29-16
`s
`2
`(63.
`Dest
`NKsh
`Hit
`
`Yes
`Forward all
`
`Send to
`CPU
`
`No
`
`L3 Switching
`
`29-3
`
`29-17
`
`
`
`
`
`Drop Yes
`Packet
`
`29-19
`
`
`
`
`
`Get port
`bitmap from
`WLAN table
`
`Get port
`tip
`MC table
`
`Ex.1026
`VERIZON / Page 30 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 30 0f 47
`
`US 6,996,099 B1
`
`
`
`COS CNCA 802.lp. Rate
`Queue P (2b) Priority Counter Counter
`(8b) Threshold|Threhold Point Q
`(8b)
`(8b)
`(6b).
`
`Fig.30
`
`Ex.1026
`VERIZON / Page 31 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 31 of 47
`
`US 6,996,099 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`le
`
`is
`000
`00
`oil
`100
`101
`110
`111
`
`orial
`0-15
`8-23
`2439
`32-47
`40-55
`48-63
`56.71
`
`one
`16-31
`24-39
`40-55
`48-63
`567
`64-79
`72-87
`
`of
`32-47
`40-55
`56-7
`64-79
`72-87
`80-95
`88-103
`
`||
`
`oila!
`48-63
`56-7
`72-87
`80-95
`88-103
`96-111
`104-119
`
`Fig.31
`
`Ex.1026
`VERIZON / Page 32 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 32 0f 47
`
`US 6,996,099 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`N
`
`Z
`9
`
`@
`
`Ex.1026
`VERIZON / Page 33 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 33 of 47
`
`US 6,996,099 B1
`
`LXI
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex.1026
`VERIZON / Page 34 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 34 of 47
`
`US 6,996,099 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex.1026
`VERIZON / Page 35 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 35 0f 47
`
`US 6,996,099 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex.1026
`VERIZON / Page 36 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 36 of 47
`
`US 6,996,099 B1
`
`36-1
`
`
`
`ls bit l of action
`bit set
`
`Select Cos
`from the field
`in Filter mask.
`
`IsbitO of
`NoMatch
`action field set
`
`
`
`
`
`Y
`
`Get Cos from the field in s
`Filter mask. Modify Pkt for
`Priority Tagged field. Set
`Regenerate CRC bit.
`
`
`
`
`
`36-5
`
`is bitlO of
`NoMatch action
`field set.
`
`r
`ITOS is not modified by
`higherfiller ask (The
`DSCP is picked from the in
`DSCP field of the Filter
`Mask (only ifpkti py)
`Recalculate IPChecksum.
`Set Regenerate CRC in the
`message.
`
`
`
`
`
`
`
`
`
`ls
`bitll of
`no-match action bit
`st
`& Desport=
`Ox3f
`
`
`
`
`
`
`
`Fig.36
`
`
`
`SelectOutput Port
`& Output port module
`from the filter mask as
`egress port & egress module
`set port Bitmap
`
`Ex.1026
`VERIZON / Page 37 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 37 0f 47
`
`US 6,996,099 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Isbit of
`action bit set
`
`Remember to send
`a copy to CPU,
`Set the bit) of
`Cpu Opcodes.
`
`
`
`
`
`
`
`Isbit 6 of action
`bit set
`
`Remember to send
`a copy to
`Mirrored-to port.
`
`
`
`
`
`
`
`Increment counter
`indicated in the counter
`field of the Rule unless
`the counter was already
`incremented for this plkt
`
`is bit4 of
`action field set
`
`Drop the packet,
`but contine
`checking other
`action bits
`
`37-7
`
`ls bitSofaction
`field set AND
`Destport lsdrif
`
`Select Output Port
`and Output module
`idfrom the Rule
`entry as egress Port
`and egress module,
`Set Por Bitmap
`accordingly
`
`Action bit
`Set
`
`
`
`
`
`
`
`37.11
`
`s
`Action Bit 10
`Set
`
`N
`
`If Tos is not modified by
`a higher filter mask, the DSCP is
`picked. The In-DSCP field field
`of the rule-if plktislpw4-Recalculate
`the IP checksum-set Regenerate CRC
`
`Fig. 37
`
`Ex.1026
`VERIZON / Page 38 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 38 0f 47
`
`US 6,996,099 B1
`
`21
`
`
`
`210
`
`
`
`ADDRESS
`TABLE
`8K entries
`
`Search engine
`
`Fig.38
`
`Ex.1026
`VERIZON / Page 39 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 39 of 47
`
`US 6,996,099 B1
`
`
`
`2
`
`22
`
`21
`
`ADDRESS
`TABLE
`4K entries
`
`ADDRESS
`TABLE
`4K entries
`
`213
`
`214
`
`Fig.39
`
`Ex.1026
`VERIZON / Page 40 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 40 of 47
`
`US 6,996,099 B1
`
`
`
`
`
`U 8 M
`
`K
`I
`G
`E
`C
`A
`
`wn P
`
`× P
`
`is a
`
`r
`
`is
`
`a
`
`0
`
`up
`
`a
`
`a
`
`wo
`
`Fig.4Ob
`
`2
`
`9
`8
`7
`6
`5
`4.
`3
`2
`
`O
`
`Ex.1026
`VERIZON / Page 41 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 41 of 47
`
`US 6,996,099 B1
`
`
`
`9
`8
`6
`5
`4
`3
`2
`
`O
`
`Ex.1026
`VERIZON / Page 42 of 81
`
`

`

`US. Patent
`
`Feb. 7, 2006
`
`%
`
`US 6,996,099 B1
`
`3..
`
`3%:3a
`
`.332g.323
`
`_25
`
`
`
`
`
`..3.a»:.328>2..z,was:zéém£.3is?y>2..he93a:3zv.3
`
`
`
`f._2.33:“E:
`Md05Eas$20asum29%33.»
`
`
`70.858358505.85ins:Em38542%IV3..Em33.6~83.w2».
`
`.355:2.23asEm
`
`“E;E:a»
`
`€538:
`
`EX.1026
`
`VERIZON / Page 43 of 81
`
`~19”.
`
`.2526
`
`Ex.1026
`VERIZON / Page 43 of 81
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 43 of 47
`
`US 6,996,099 B1
`
`43-
`Ll
`lfpacket should be dropped due to FFP, Port
`Bitmap=0
`
`
`
`
`
`Port Bitmap = Port Bitmap/(lkCPU)
`
`43-2
`Get PortBitmap and AND with Forwarding Port
`Reg and AND with - Active Port Reg
`corresponding to COSQueue selected (after going
`through the Cos Mapping using C0S Select
`Register) AND HOLRegister, to get the egress
`PortBitmap
`Look at M Bits of Port Based WLAN table.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ls ingress port Mirrored (
`Mbit0) OR (stack Link
`&& Mbit is set)
`
`
`
`
`
`
`
`
`
`
`
`Y
`
`Is Mirroring
`Based On Filter
`Logic
`
`N
`
`Remember to send
`the packet to
`Mirrored Port
`
`Remember to send
`the packet to
`Mirrored Port
`
`
`
`
`
`
`
`
`
`
`
`
`
`43-7
`
`
`
`Isegress port
`Mirrored (from
`Egress Mirroring
`Register)
`
`Remember to send
`the packet to
`Mirrored Port
`
`Fig.43
`
`Ex.1026
`VERIZON / Page 44 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 44 of 47
`
`US 6,996,099 B1
`
`Out-Profile
`Actions
`
`44
`
`
`
`
`
`
`
`Y
`
`is bit)
`of action bit
`Set
`
`Y
`
`
`
`
`
`inter
`Set the bitO of
`Cou Opcodes.
`pu Upc
`
`Drop the packe
`rop the packet
`but continue
`checking other
`action bits
`
`
`
`If TOS is not modified
`higher filter mask
`prisia
`Oile Of
`of the Rule (only ifpkt is
`Act.
`Recalculate IP
`Checksum. Set
`Regenerate CRC in the
`message.
`
`
`
`
`
`
`
`
`
`
`
`ls bit of the
`action field set
`
`
`
`
`
`
`
`is bid of the Ya'
`action field set
`
`Set the Drop Precedence
`bit to 1.
`Set the CNG bit in the P.
`Channel
`
`32-13
`
`Fig.44
`
`Ex.1026
`VERIZON / Page 45 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 45 0f 47
`
`US 6,996,099 B1
`
`
`
`Address
`Resolution
`Logic
`
`Fast
`Filtering
`Logic
`
`Differentiated
`Services
`Logic
`
`COS
`Manager
`
`Fig.45
`
`Ex.1026
`VERIZON / Page 46 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 46 of 47
`
`US 6,996,099 B1
`
`46-2
`If FFP DSCP, then use the value of
`DSCP from FFPelse
`If DSCP Flag=l then use assigned
`DSCP value else use DSCP value from
`DSCP field of IP Header to index into
`DiffServ Table, increment DSCP Rate
`counter for this port (in Octets).
`
`
`
`
`
`Ifpktisan IP
`Packet and version
`
`46-2
`
`46-7
`
`ISDF
`Walue=02
`
`N
`
`46-8
`Y (Set CNG bit in
`the P-Channel
`
`N
`
`
`
`
`
`Israte counter)=
`DSCP Discard Threshold
`
`Y
`
`
`
`
`
`N
`
`46-6
`
`Y
`Set portbitmap=0
`If (CState or a copy
`should go to CPU
`{
`portbitmap = 1 (CCPU
`Goto Ll
`
`
`
`N
`
`46-12
`
`
`
`Y
`Get 802.lp packet
`priority from New
`DSCP assigned r
`802.lp priority field
`
`Y
`
`is DSCP rate counter
`>=DSCP re-mark
`46-10 Nhreshold 169
`is RMF = 0 or
`RMF = 3
`
`Y
`
`N
`
`46-11
`
`
`
`N
`
`N
`46-15 N
`sNP
`s
`y
`
`Y
`46-14 N
`Get 802.lp
`s
`priority from DSCP
`802.lp priority
`field and the
`corresponding COS
`value from the 802.lp
`Pickup the CoSQueue value from
`DSCP priority Queue.
`
`
`
`
`
`46-18
`
`if FFP DSCP or DSCP flag=l
`then change the DSCP field, recalculate
`IP checksum, regenerate CRC. (The
`DSCP field willcome from FFPlogicif
`FFPDSCP-1 ?on DSP logic)
`
`
`
`
`
`
`
`45-7
`The COS value is not changed
`Change the DSCP field to
`New DSCP field value recalculate
`Pchecksum, regenerate CRC.
`Ll
`
`Fig.46
`
`Ex.1026
`VERIZON / Page 47 of 81
`
`

`

`U.S. Patent
`
`Feb. 7, 2006
`
`Sheet 47 of 47
`
`US 6,996,099 B1
`
`43
`
`Ll
`Get PortBitmap and AND with Forwarding Port
`Reg and AND with Active Port Reg corresponding
`to COS Queue selected (after going through the
`Cos Mapping using COSSelect Register) AND
`HOLRegister, to get the egress PortBitmap
`Look at MBits of Port based WLAN table
`
`47-4
`Is Mirroring
`Based on Filter
`Logic
`
`N
`
`
`
`
`
`
`
`
`
`ls ingressport
`Mirrored (MbitO)
`OR (stack Link &
`Mbit is set)
`
`Y
`
`Remember to send Rye, to send
`packet to
`the packet to
`Minored Port
`Mirrored Port
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`47-6
`
`segress port
`Mirrored (from
`Egress Mirroring
`Register)
`
`Remember to send
`the packet to
`Mirrored Port
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig.47
`
`Ex.1026
`VERIZON / Page 48 of 81
`
`

`

`US 6,996,099 B1
`
`1
`NETWORKSWITCH HAVING A
`PROGRAMMABLE COUNTER
`
`REFERENCE TO RELATED APPLICATIONS
`
`This application claims priority of U.S. Provisional Patent
`Application Ser. No. 60/124,878, filed on Mar. 17, 1999,
`U.S. Provisional Patent Application Ser. No. 60/135,603,
`filed on May 24, 1999, and U.S. Provisional Patent Appli
`cation Ser. No. 60/149,706, filed on Aug. 20, 1999. This
`application is a continuation-in-part (CIP) of U.S. patent
`application Ser. No. 09/343,409, filed on Jun. 30, 1999. The
`Subject matter of these earlier filed applications is hereby
`incorporated by reference.
`
`BACKGROUND OF THE INVENTION
`
`15
`
`1. Field of the Invention
`The invention relates to a method and apparatus for high
`performance Switching of data packets in local area com
`munications networkS Such as token ring, ATM, Ethernet,
`fast Ethernet, and gigabit Ethernet environments, all of
`which are generally known as LANs. In particular, the
`invention relates to a new Switching architecture in an
`integrated, modular, Single chip Solution, which can be
`implemented on a Semiconductor SubStrate Such as a Silicon
`chip.
`2. Description of the Related Art
`The present invention advances network Switching tech
`nology in a Switch Suitable for use in Ethernet, fast Ethernet,
`gigabit Ethernet, and other types of network environments
`which require high performance Switching of data packets or
`data cells. A Switch utilizing the disclosed elements, and a
`System performing the disclosed Steps, provides cost and
`operational advantages over the prior art.
`
`25
`
`35
`
`SUMMARY OF THE INVENTION
`
`The present invention is directed to a Switch-on-chip
`Solution for a network Switch, capable of use at least on
`ethernet, fast ethernet, and gigabit ethernet Systems, wherein
`all of the Switching hardware is disposed on a single
`microchip. The present invention is configured to maximize
`the ability of packet-forwarding at lineSpeed, and to also
`provide a modular configuration wherein a plurality of
`Separate modules are configured on a common chip, and
`wherein individual design changes to particular modules do
`not affect the relationship of that particular module to other
`modules in the System.
`The present invention is therefore related to a network
`Switch for Switching packets from a Source to a destination,
`wherein the network Switch includes a Source port for
`receiving an incoming packet from a Source, a destination
`port that contains a path to a destination for the packet, and
`a programmable counter unit for counting a number of
`packets of Selected packet types which are received by the
`Switch.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The objects and features of the invention will be more
`readily understood with reference to the following descrip
`tion and the attached drawings, wherein:
`FIG. 1 is a general block diagram of elements of a
`network Switch as discussed herein;
`FIG. 2 is a more detailed block diagram of the network
`Switch;
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`FIG. 3 illustrates the data flow on the CPS channel of the
`network Switch;
`FIG. 4A illustrates demand priority round robin arbitra
`tion for access to the C-channel of the network Switch;
`FIG. 4B illustrates access to the C-channel based upon the
`round robin arbitration illustrated in FIG. 4A;
`FIG. 5 illustrates P-channel message types;
`FIG. 6 illustrates a message format for S channel message
`types,
`FIG. 7 is an illustration of the OSI 7 layer reference
`model;
`FIG. 8 illustrates an operational diagram of an EPIC
`module,
`FIG. 9 illustrates the slicing of a data packet on the ingreSS
`to an EPIC module;
`FIG. 10 is a detailed view of elements of the MMU;
`FIG. 11 illustrates the CBM cell format;
`FIG. 12 illustrates an internal/external memory admission
`flow chart;
`FIG. 13 illustrates a block diagram of an egreSS manager
`76 illustrated in FIG. 10;
`FIG. 14 illustrates more details of an EPIC module;
`FIG. 15 is a block diagram of a fast filtering processor
`(FFP);
`FIG. 16 is a block diagram of the elements of CMIC 40;
`FIG. 17 illustrates a series of steps which are used to
`program an FFP,
`FIG. 18 is a flow chart illustrating the aging process for
`ARL (L2) and L3 tables;
`FIG. 19 illustrates communication using a trunk group
`according to the present invention;
`FIG. 20 is a table listing numerous fields for various
`packet types;
`FIGS. 21A and 21B illustrate a filter mask format and a
`field mask format, respectively;
`FIG.22 is a flow chart which illustrates the formation and
`application of a filter mask,
`FIG.23 illustrates an example of a format for a rules table;
`FIG. 24 illustrates a format for an IP multicast table;
`FIG. 25 is a flow chart illustrating handling of an IP
`multicast packet;
`FIG. 26 illustrates an embodiment of stacked SOC
`Switches 10;
`FIGS. 27A and 27B illustrate alternate embodiments of
`stacked SOC 10 configurations;
`FIG. 28 is a detailed view of the functional modules of
`IPIC 90;
`FIG. 29 illustrates packet handling for packets coming in
`to the high performance interface of IPIC 90;
`FIG. 30 is a diffServ-to-COS mapping table;
`FIG. 31 illustrates the configuration of the offsets;
`FIG. 32 is a primary flowchart for the filtering/metering
`logic;
`FIG. 33 is a flowchart of the partial match logic;
`FIG. 34 is a flowchart of the in-profile action logic;
`FIG.35 is a flowchart of the partial match action logic for
`bits 3–6;
`FIG. 36 is a flowchart of the partial match action logic for
`bits 1, 0, and 10;
`FIG.37 is a flowchart of the in-profile action logic for bits
`2, 8, and 9;
`FIG.38 illustrates a first configuration of an address table
`and a Search engine;
`FIG. 39 illustrates a second configuration of two address
`tables and two Search engines,
`FIG. 4.0a illustrates a first example of address entries
`Stored in an a Single address table;
`
`Ex.1026
`VERIZON / Page 49 of 81
`
`

`

`US 6,996,099 B1
`
`3
`FIG. 40b illustrates a second example of address entries
`Stored in two separate Sorted address tables,
`FIG. 41a illustrates a third example of address entries
`Stored in a single address table;
`FIG. 41b illustrates a fourth example of address entries
`Stored in two separate Sorted address tables,
`FIG. 42 is a flowchart of the in-profile action logic forbits
`11-13;
`FIG. 43 is a flowchart of the mirrored port/final FFP
`actions,
`FIG. 44 is a flowchart of the out-profile action logic;
`FIG. 45 is a flowchart of the data flow of an incoming
`packet;
`FIG. 46 is a flowchart of the differentiated services logic;
`and
`FIG. 47 is a flowchart expanding step 46-4.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`4
`complex multi-chip Solution is necessary which requires
`logic circuitry, Sometimes referred to as glue logic circuitry,
`to enable the various chips to communicate with each other.
`Additionally, cost/benefit tradeoffs are necessary with
`respect to expensive but fast SRAMs versus inexpensive but
`slow DRAMs. Additionally, DRAMs, by virtue of their
`dynamic nature, require refreshing of the memory contents
`in order to prevent losses thereof. SRAMs do not suffer from
`the refresh requirement, and have reduced operational over
`head which compared to DRAMs such as elimination of
`page misses, etc. Although DRAMs have adequate Speed
`when accessing locations on the same page, Speed is reduced
`when other pages must be accessed.
`Referring to the OSI 7-layer reference model discussed
`previously, and illustrated in FIG. 7, the higher layers
`typically have more information. Various types of products
`are available for performing Switching-related functions at
`various levels of the OSI model. Hubs or repeaters operate
`at layer one, and essentially copy and “broadcast' incoming
`data to a plurality of Spokes of the hub. Layer two Switching
`related devices are typically referred to as multiport bridges,
`and are capable of bridging two separate networks. Bridges
`can build a table of forwarding rules based upon which
`MAC (media access controller) addresses exist on which
`ports of the bridge, and pass packets which are destined for
`an address which is located on an opposite Side of the bridge.
`Bridges typically utilize what is known as the “spanning
`tree' algorithm to eliminate potential data loops, a data loop
`is a Situation wherein a packet endlessly loops in a network
`looking for a particular address. The Spanning tree algorithm
`defines a protocol for preventing data loops. Layer three
`Switches, Sometimes referred to as routers, can forward
`packets based upon the destination network address. Layer
`three Switches are capable of learning addresses and main
`taining tables thereof which correspond to port mappings.
`Processing Speed for layer three Switches can be improved
`by utilizing Specialized high performance hardware, and
`off-loading the host CPU so that instruction decisions do not
`delay packet forwarding.
`FIG. 1 illustrates a configuration wherein a Switch-on
`chip (SOC) 10, in accordance with the present invention, is
`functionally connected to external devices 11, external
`memory 12, fast Ethernet ports 13, and gigabit Ethernet
`ports 15. For the purposes of this embodiment, fast Ethernet
`ports 13 will be considered low speed Ethernet ports, since
`they are capable of operating at Speeds ranging from 10
`Mbps to 100 Mbps, while the gigabit Ethernet ports 15,
`which are high Speed Ethernet ports, are capable of operat
`ing at 1000 Mbps. External devices 11 could include other
`Switching devices for expanding Switching capabilities, or
`other devices as may be required by a particular application.
`External memory 12 is additional off-chip memory, which is
`in addition to internal memory which is located on SOC 10,
`as will be discussed below. CPU 52 can be used as necessary
`to program SOC 10 with rules which are appropriate to
`control packet processing. However, once SOC 10 is appro
`priately programmed or configured, SOC 10 operates, as
`much as possible, in a free running manner without com
`municating with CPU 52. Because CPU 52 does not control
`every aspect of the operation of SOC 10, CPU 52 perfor
`mance requirements, at least with respect to SOC 10, are
`fairly low. Aless powerful and therefore less expensive CPU
`52 can therefore be used when compared to known network
`Switches. As also will be discussed below, SOC 10 utilizes
`external memory 12 in an efficient manner So that the cost
`and performance requirements of memory 12 can be
`
`15
`
`25
`
`35
`
`40
`
`AS computer performance has increased in recent years,
`the demands on computer networks has significantly
`increased; faster computer processors and higher memory
`capabilities need networks with high bandwidth capabilities
`to enable high Speed transfer of Significant amounts of data.
`The well-known Ethernet technology, which is based upon
`numerous IEEE Ethernet Standards, is one example of
`computer networking technology which has been able to be
`modified and improved to remain a viable computing tech
`nology. A more complete discussion of networking Systems
`can be found, for example, in SWITCHED AND FAST
`Ethernet, by Breyer and Riley (Ziff-Davis, 1996), and
`numerous IEEE publications relating to IEEE 802 standards.
`Based upon the Open Systems Interconnect (OSI) 7-layer
`reference model, network capabilities have grown through
`the development of repeaters, bridges, routers, and, more
`recently, “Switches', which operate with various types of
`communication media. Thickwire, thinwire, twisted pair,
`and optical fiber are examples of media which has been used
`for computer networks. Switches, as they relate to computer
`networking and to Ethernet, are hardware-based devices
`which control the flow of data packets or cells based upon
`destination address information which is available in each
`packet. A properly designed and implemented Switch should
`be capable of receiving a packet and Switching the p