I 1111111111111111 11111 111111111111111 111111111111111 IIIII 111111111111111111
`US007403521B2
`
`c12) United States Patent
`Saxena
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 7,403,521 B2
`Jul. 22, 2008
`
`(54) MULTICAST AND BROADCAST
`OPERATIONS IN ETHERNET SWITCHES
`
`(75)
`
`Inventor: Rahul Saxena, Sunnyvale, CA (US)
`
`(73) Assignee: Intel Corporation, Santa Clara, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 828 days.
`
`(21) Appl. No.: 10/004,765
`
`(22) Filed:
`
`Dec. 3, 2001
`
`(65)
`
`Prior Publication Data
`
`US 2003/0103517 Al
`
`Jun. 5, 2003
`
`(51)
`
`Int. Cl.
`H04L 12128
`(2006.01)
`(52) U.S. Cl. ........................ 370/390; 370/412; 370/432
`( 58) Field of Classification Search . ... ... ... ... .. .. 3 70/230,
`370/389-390,392,400,412-414,419-421,
`370/422-423,428--429,431-432
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,410,540 A * 4/1995 Aiki et al. ................... 370/390
`
`5,548,588 A *
`5,646,886 A *
`5,915,097 A
`6,272,567 Bl *
`6,574,194 Bl*
`6,724,761 Bl *
`6,751,219 Bl*
`2005/0041579 Al*
`* cited by examiner
`
`....... 370/395.7
`8/1996 Ganmukhi et al.
`7/1997 Brahmbhatt ........... 365/185.16
`6/1999 Chao ..................... 395/200.68
`8/2001 Pal et al ........................ 710/56
`6/2003 Sun et al. .................... 370/235
`4/2004 Moy-Yee et al. ............ 370/390
`6/2004 Lipp et al.
`.................. 370/390
`2/2005 Medina et al.
`.............. 370/229
`
`Primary Examiner-Huy D. Vu
`Assistant Examiner-Jason Mattis
`(74) Attorney, Agent, or Firm-Kacvinsky LLC
`
`(57)
`
`ABSTRACT
`
`A switch and a process of operating a switch are described
`where a received data frame is copied one or more times into
`a memory before being transmitted out of the switch. The
`switch and method determine how much space in the memory
`is needed to store all of the copies of the received data frame
`and then the switch and method determine locations in the
`memory for storing the copies of the received data frames.
`The copies of the received data frame are stored until the ports
`designated as transmitting the copies of the received data
`frame are ready. When a port is ready, a copy of the received
`data frame is read out of the memory and the port is instructed
`where to locate the copy on a bus. When the port has retrieved
`the copy of the data frame, it transmits the data frame out of
`the switch.
`
`25 Claims, 10 Drawing Sheets
`
`100
`
`/
`
`110b
`
`110a
`
`MEMORY
`
`105c
`
`110c
`
`105d
`
`110d
`
`Ex.1028
`VERIZON / Page 1 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 1 of 10
`
`US 7,403,521 B2
`
`100
`
`/
`
`110b
`
`PORT
`
`130a
`OCLC
`
`!
`
`~ CCSLC
`
`PORT
`
`MEMORY
`
`110a
`
`115c
`
`125
`
`1k
`t
`
`105c
`
`PORT
`
`110c
`
`OCLS 130c
`
`1 - - - - - - - - - 1
`
`-~77
`-+- rr=
`PORT
`
`OCLC
`130d
`
`105d
`
`110d
`FIG. 1
`
`Ex.1028
`VERIZON / Page 2 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 2 of 10
`
`US 7,403,521 B2
`
`110a
`
`r
`105a
`
`r115a
`
`r210
`
`CONTROL
`
`220
`j
`II
`l
`
`,
`,,
`
`220
`)
`r t
`l
`
`220
`J
`
`J
`
`/
`
`1
`
`220
`rl
`' l
`
`V
`
`FIG. 2
`
`"-FROM C CLSC
`ND
`120A
`30a
`OCLC 1
`
`(',
`
`115c
`
`Ex.1028
`VERIZON / Page 3 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 3 of 10
`
`US 7,403,521 B2
`
`CCSLC
`
`115a
`
`120
`
`315
`
`COPIER
`
`305
`
`310
`
`MEMORYl-4---......i
`
`CONTROLLER I - - - - - - - '
`
`TO/FROM OCLC
`FIG. 3
`
`115b
`
`150
`
`Ex.1028
`VERIZON / Page 4 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 4 of 10
`
`US 7,403,521 B2
`
`TO CONTROLLER 310
`
`405
`
`305 r
`
`410
`
`READ
`
`WRITE
`
`CELL
`ARRAY
`
`CHANNEL
`DECODER
`
`FROM
`CONTROLLER
`310
`
`SEGMENT DECODER
`
`FROM CONTROLLER 310
`FIG. 4a
`
`420
`
`~ - - - -S
`WRITE
`
`OUT - - - -
`
`~ - - - -R ENABLE
`READ
`
`FIG. 4b
`
`CHANNEL DECODER
`
`SEGMENT DECODER
`
`Ex.1028
`VERIZON / Page 5 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 5 of 10
`
`US 7,403,521 B2
`
`550
`115b
`----'-----------~DNA
`WE
`
`64
`BYTES
`
`RE
`
`115c
`
`555
`DATA
`WE
`1--'1"-------l RE
`
`64
`BYTES
`
`560
`
`150
`
`DECODER
`
`READ WRITE
`FIG. 5
`
`Ex.1028
`VERIZON / Page 6 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 6 of 10
`
`US 7,403,521 B2
`
`310
`
`605
`
`620
`
`ARBITER
`
`FROM
`MEMORY
`305
`
`605a
`
`HEADER
`DATA
`
`610
`
`CHANNEL
`AVAILABILITY
`
`SIZE CONVERTER
`SIZE ADD/ PORT
`RES.
`DET.
`ADJUSTER
`
`SEGMENT
`AVAILABILITY
`
`605c
`
`615
`
`Ab~Ss
`
`GENERATOR
`
`625
`
`TO MEMORIES
`125AND 305
`
`TOOCLCs
`
`TO MEMORIES
`125AND 305
`
`FROMOCLCs
`FIG. 6
`
`Ex.1028
`VERIZON / Page 7 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 7 of 10
`
`US 7,403,521 B2
`
`105b
`
`110b
`
`PORT
`
`700
`
`I
`
`115c
`
`~
`
`~
`
`720
`
`125
`
`150
`
`t
`
`11 Oc
`
`MEMORY
`
`PORT
`
`t
`
`105c
`
`115a
`
`•
`
`t
`
`110a
`
`PORT
`
`105a
`
`t
`
`PORT
`
`105d
`
`FIG. 7
`
`Ex.1028
`VERIZON / Page 8 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 8 of 10
`
`US 7,403,521 B2
`
`800
`,J
`
`805
`
`810
`
`815
`
`820
`
`825
`
`830
`
`835
`
`840
`
`845
`
`RECEIVE DATA
`FRAME
`
`EXTRACT HEADER
`INFORMATION
`
`DETERMINE# OF
`PORTS TO
`TRANSMIT
`
`DETERMINE SIZE
`OF DATA FRAME
`
`DETERMINE
`NEEDED SPACE
`IN MEMORY
`
`DETERMINE
`EMPTY LOCATIONS
`IN MEMORY
`
`SELECT
`ADE~UATE
`MEMORY OCATION
`
`STORE COPIES
`OF DATA FRAME
`
`STORE LOCATION
`DATA
`
`END
`
`850
`FIG. 8
`
`Ex.1028
`VERIZON / Page 9 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 9 of 10
`
`US 7,403,521 B2
`
`935
`
`SELECT MULTIPLE
`ASSOCIATIONS
`
`900 i
`
`N
`
`915
`
`READ DATA
`FRAMES
`
`920
`PORT(S) SELECT
`DATA FRAMES
`FOR OUTPUT
`
`925
`
`END
`
`y
`
`930
`
`INSTRUCT ONE
`..._____ CONFLICTING PORT
`TO WAIT
`
`FIG. 9
`
`Ex.1028
`VERIZON / Page 10 of 17
`
`

`

`U.S. Patent
`
`Jul. 22, 2008
`
`Sheet 10 of 10
`
`US 7,403,521 B2
`
`NO.OF
`COPIES
`
`1005
`
`1015
`
`1020
`
`1010
`
`COPIES
`
`TO
`PORTS
`
`2
`2
`2
`2
`
`t
`
`SEGMENT9
`
`\.
`
`y
`FIG. 1 Oa
`
`SEGMENT
`\.
`
`)
`
`N
`N
`0
`0
`
`9
`
`M
`M
`
`t
`
`8
`
`t
`y
`FIG. 1 Ob
`
`TO
`PORTS
`
`J
`
`SEGMENT
`
`5
`
`4
`
`'---------- ______ _.,)
`"Y"
`FIG. 1 Oc
`
`3 2
`
`2 1
`
`Ex.1028
`VERIZON / Page 11 of 17
`
`

`

`US 7,403,521 B2
`
`1
`MULTICAST AND BROADCAST
`OPERATIONS IN ETHERNET SWITCHES
`
`TECHNICAL FIELD
`
`2
`is to retransmit the data frame. Since only one of the multiple
`channels is accessed at a time, the useful bandwidth of an SAF
`switch decreases when multicasting or broadcasting data
`frames.
`
`This invention relates to forwarding data frames through a
`switch, and more particularly to routing data frames for effi(cid:173)
`cient multicast and broadcast operations in Ethernet switches.
`
`BACKGROUND
`
`DESCRIPTION OF DRAWINGS
`
`10
`
`FIG. 1 is a block diagram of a switch.
`FIG. 2 is a block diagram of a port of the switch of FIG. 1.
`FIG. 3 is a block diagram of a copier, channel select logic
`circuit of the switch of FIG. 1.
`FIG. 4a is a block diagram of a memory circuit in the
`copier, channel select logic circuit of FIG. 3.
`FIG. 4b is a block diagram of a cell of the memory circuit
`15 of FIG. 4a.
`FIG. 5 is a block diagram of a main memory circuit of the
`switch of FIG. 1.
`FIG. 6 is a block diagram of a controller circuit of the
`copier, channel select logic circuit of FIG. 3.
`FIG. 7 is a block diagram of another switch.
`FIG. 8 is a flow chart of a process for storing copies of a
`received data frame for the switches shown in FI GS. 1 and 7.
`FIG. 9 is a flow chart of a process for reading stored copies
`ofa received data frame for the switches shown in FI GS. 1 and
`25 7.
`
`Some switches, such as Ethernet switches, receive data
`frames at one or more ports. A data frame is an organized
`format of control or header data and payload data. The header
`data typically include fields such as the source address of the
`device transmitting the data frame, the destination address or
`addresses to which the data frame is being transmitted,
`length/type data indicating the length of the data frame as well
`as the data type of the payload data, and a frame check
`sequence field used as a form of error checking in verifying 20
`receipt of the data frame by the destination device. The con(cid:173)
`trol data are overhead that are used to assure that the payload
`data arrive at the destination device.
`The payload data are the data of interest that are sent to the
`destination device. Examples of payload data include pixel
`data for image rendering, audio data, text data and control
`data ( e.g., commands requesting that the destination device
`transmit information back to the original source device).
`In some network implementations, data frames may have
`different sizes. For example, in a typical Ethernet network, 30
`frame size may vary from a minimum of 64 bytes to a maxi(cid:173)
`mum of 1,518 bytes. In general, forwarding received data
`frames from a switch includes one of three methods: unicast,
`multicast and broadcast. A unicast transmission employs a
`one-to-one correspondence between the source device and 35
`the destination device such that the data frame output by a
`source device will only be received and used by a single
`destination device. A multicast transmission employs a one(cid:173)
`to-many correspondence such that a single source device
`transmits a data frame for receipt and use by multiple desti- 40
`nation devices. A broadcast transmission employs a one-to-
`all correspondence such that a single source device transmits
`a data frame to all destination devices on a particular network
`to which the source device is connected.
`A switch receives data frames and forwards them to output
`ports for retransmission to other switches or destination
`devices. In some switches, a memory is employed to tempo(cid:173)
`rarily store a received data frame until the needed port
`becomes free to output that data frame. These types of
`switches may be referred to as store-and-forward (SAF) 50
`switches.
`Memory bandwidth usage can be inefficient as some of the
`memory bandwidth is not used when storing smaller data
`frames. To compensate for this, a memory is divided into
`independently addressable channels. This allows for smaller 55
`data frames to be stored in particular channels, which results
`in more efficient use of memory and increased throughput.
`That is, different channels may be accessed independently for
`reading or writing data frames. By dividing a large memory
`into channels, the overall speed, or useful bandwidth ( data 60
`frame width multiplied by the memory access frequency), of
`a switch increases. By increasing the useful bandwidth of the
`internal hardware, additional ports may be supported without
`unnecessarily increasing the size of the memory.
`When using an SAF switch to multicast or broadcast data 65
`frames over the network, a particular data frame may be read
`from memory multiple times, such as once for each port that
`
`FIGS. 10a, 10b and 10c are representations of data stored
`in the switches of FIGS. 1 and 7.
`Like reference symbols in the various drawings indicate
`like elements.
`
`DETAILED DESCRIPTION
`
`As showninFIG.1, a switch l00has four ports 105a-105d.
`Ports 105a-l 05d are circuits may include hardware, software,
`firmware or any combination thereof. The ports 105a-105d
`are coupled to four buses ll0a-ll0d respectively, and are
`used to transmit data from and receive data into switch 100.
`Ports 105a-105d and buses 11 0a-11 0d are full duplex in that
`they can transmit and receive data simultaneously. In one
`implementation, switch 100 is an Ethernet switch.
`A receiving bus 115a and a transmitting bus 115c are
`coupled to ports 105a-105d. Receiving bus 115a forwards
`received data frames from ports 105a-105dto a copier, chan(cid:173)
`nel select logic circuit (CCSLC) 120. An intermediate bus
`45 115b forwards received data frames from CCSLC 120 to
`main memory 125, and a bus 150 forwards address data to
`main memory 125 for use in storing the received data frames.
`The transmitting bus 115c forwards data frames stored in
`main memory 125 to ports 105a-105d. Interspersed in switch
`100 are four output control logic circuits (OCLCs) 130a-130d
`that are associated with ports 105a-105d, respectively.
`CCSLC 120 is coupled to the four OCLCs 130a-130d and
`main memory 125 through control signal paths. It should be
`noted that a logic circuit may include gates, hardware, soft(cid:173)
`ware, firmware or any combination thereof.
`Memory 125 includes channels and segments. A channel is
`a portion of the total width of a memory unit. A segment is an
`individually addressable collection of channels (e.g., a seg(cid:173)
`ment may include four channels). A location is a part of
`memory that is addressable by both a channel address and a
`segment address.
`In general, the switch 100 receives data frames on buses
`ll0a-11 0d at ports 105a-l 05d. The received data frames then
`are forwarded to CCSLC 120 using receiving bus 115a.
`CCSLC 120 determines how many copies of the received data
`frame are needed for broadcast or multicast operations, cop(cid:173)
`ies the received data frame, and determines particular loca-
`
`Ex.1028
`VERIZON / Page 12 of 17
`
`

`

`US 7,403,521 B2
`
`4
`3
`tions in main memory 125 for storing the copies of the
`signals indicate that data is being loaded into the correspond(cid:173)
`received data frame. OCLCs 130a-130d determine when to
`ing portion of memory 125, and is set to zero when the read
`output the stored copies of the data frame over buses ll0a(cid:173)
`signal is asserted and the decoder signals indicate that data is
`ll0d through ports 105a-105d based upon control data
`being read from the corresponding portion of main memory
`received from CCSLC 120.
`5 125. The cell 420 may be further configured to produce an
`As shown in FIG. 2, exemplary port 105a contains control
`output only when the enable signal is asserted so as to permit
`circuit 210 and multiplexers 220. Exemplary port 105a
`the controller to poll the memory 305 to detect cells having
`receives a data frame on transmitting bus 115c for forward(cid:173)
`values indicative of available portions of main memory 125.
`ing. The data frame received on transmitting bus 115c is
`An exemplary main memory 125 may have four channels,
`extracted from transmitting bus 115c by multiplexers 220.
`10 each of which is 64 bytes wide, and sixteen segments. This
`Control circuit 215 exchanges control signals with CCSLC
`means that main memory 125 can store 64, 64-byte data
`120 and OCLCs 130a-130d.
`frames (one in each channel in each segment), sixteen, 256-
`As shown in FIG. 3, CCSLC 120 includes memory 305
`byte data frames ( one spanning all four channels in each
`coupled to a controller 310. The controller 310 is coupled to
`segment), or other combinations.
`a copier circuit 315 that receives incoming data frames on 15
`FIG. 5 shows a pair of exemplary cells 550, 555 in main
`receiving bus 115a and outputs a number of copies of the
`memory 125 that each store 64 bytes. Each cell represents one
`incoming data frames onto intermediate bus 115b. The
`location in main memory 125 (i.e., one channel of one seg(cid:173)
`incoming data frames on receiving bus 115a contain header
`ment). A decoder 560 uses the address bus 150 to generate
`data and payload data. The output data frames on intermedi(cid:173)
`signals that are combined with read and write signals to
`ate bus 115b are exact copies of the data frames received on
`20 enable writing to and reading of a particular one of cells 550,
`555. It should also be noted that any type of data randomly
`receiving bus 115a and, accordingly, also include header data
`and payload data.
`accessible, writeable storage device. Examples include
`As described earlier, exemplary header data may include at
`RAM, SRAM, DRAM, RDRAM and SDRAM.
`least the destination address of the data frame and the length
`When a data frame is received, a determination is made as
`of the data frame. Controller 310 uses the destination address 25
`to which portion of main memory 125 is to store the received
`and length data fields to determine how many copies of the
`data frame. The received data frame then is copied onto bus
`115b and the address bus 150 is used to identify one or more
`received data frame are required and where in main memory
`125 to store those copied data frames. The controller 310
`appropriate cells. The appropriate cells are activated by a
`forwards addresses on address bus 150 to identify locations in
`combination of a signal from the decoder 560 and a write
`main memory 125 to be used. In addition, the controller 310 30
`enable signal from the controller 310. Similarly, a stored data
`generates control signals that are sent to OCLCs 130a-130d
`frame is forwarded onto bus 115c by signals on the address
`bus 150 identifying the appropriate cells. The cells are acti(cid:173)
`and used to determine which data frames to read out from
`main memory 125 and at what time to transmit those data
`vated by a combination of a signal from the decoder 560 and
`a read enable signal from the controller 310.
`frames.
`Memory 305 is used to track locations in main memory 125 35
`As shown in FIG. 6, an exemplary controller 310 includes
`a size converter circuit 605, a channel availability circuit 610,
`that are available to accept copies of received data frames.
`Memory 305 can be any suitable digital storage device. In one
`a segment availability circuit 615, an arbiter circuit 620, and
`implementation, memory 305 is a volatile memory that can be
`a frame address generator 625. Size converter circuit 605
`accessed quickly for both reading and writing. The size of
`receives a portion of the header data from a data frame on
`memory 305 correlates with the size of main memory 125.
`40 receiving bus 115a. Size converter 605 includes a size deter(cid:173)
`As shown in FIG. 4a, an exemplary memory 305 may
`miner circuit 605a, an address/port resolver circuit 605b, and
`include an array of memory cells 405, a channel decoder 410
`an adjuster circuit 605c. Channel availability circuit 610
`and a segment decoder 415. In one implementation, array 405
`receives all of the bits stored in memory 305 as inputs. In the
`exemplary circuit shown in FIG. 6, memory 305 outputs 64
`is four bits wide and sixteen bits long. This correlates to main
`memory 125, which has four channels and sixteen segments. 45 bits. Segment availability circuit 615 receives output data
`Each cell in array 405 holds a single bit and correlates to a
`from size converter circuit 605 and channel availability cir(cid:173)
`cuit 610. Arbiter circuit 620 receives output data from size
`particular channel in a particular segment of main memory
`converter circuit 605, channel availability circuit 610 and
`125. If a particular cell in memory 305 currently stores a 1-bit,
`segment availability circuit 615. Frame address generator 625
`that is an indication that the corresponding channel of the
`50 receives signals from OCLCs 130a-130d and outputs signals
`corresponding segment of main memory 125 contains valid
`to main memory 125 and memory 305.
`frame data and cannot presently accept a new data frame.
`Alternatively, if a particular location in memory 305 currently
`Size converter circuit 605 receives the size data of the data
`frame being transmitted on receiving bus 115a. Size data are
`stores a 0-bit, that is an indication that the corresponding
`channel of the corresponding segment of main memory 125
`extracted from the header data for a frame.
`Since main memory 125 is divided into discrete channels,
`contains invalid frame data, (i.e., it is empty) and can pres- 55
`ently accept new data.
`a determination is needed as to how many channels are
`Each cell in array 405 is individually addressable through
`required to store one copy of the received data frame.Using a
`channel decoder 410 and segment decoder 415, which receive
`maximum data frame width of 256 bytes, a standard binary
`control signals from the controller 310. The cells also may be
`encoding technique requires an 8-bit word to indicate the size
`60 of the data frame. Size converter circuit 605 takes the 8-bit
`addressable by row or column in another implementation.
`As shown in FIG. 4b, each cell 420 of array 405 may be
`word for a particular frame and generates an output indicative
`implemented as an S-R flip flop that is enabled by a combi(cid:173)
`of how many channels of a single segment in main memory
`125 are required to store the frame. As an example, if the data
`nation of the appropriate channel decoder and segment
`frame on receiving bus 115a is 17 6 bytes wide, size converter
`decoder signals. The set input of the flip-flop is connected to
`circuit 605 generates an output signal indicating that this data
`a write signal, and the reset input is connected to a read signal. 65
`Thus, the value of the cell is set to one when the write signal
`frame requires three channels ( each of which is 64 bytes
`wide) of the segment.
`is asserted and the channel decoder and segment decoder
`
`Ex.1028
`VERIZON / Page 13 of 17
`
`

`

`US 7,403,521 B2
`
`5
`
`5
`Address-port resolver circuit 605b receives at least the
`destination address( es) from the header, and uses this data to
`produce an output indicative of which ports 105a-l 05d are to
`transmit the received data frame. The output of the address(cid:173)
`port resolver circuit 605b is used to control operation of other
`parts of switch 100 so as to produce the correct number of
`copies of the received data frame and routing of the copies of
`the received data frame to the proper port or ports.
`Adjuster circuit 605creceives the output from size deter(cid:173)
`miner circuit 605a and the output from address-port resolver
`circuit 605b and generates an output indicative of the number
`of segments needed to store the number of copies of the data
`frame. For example, if a 128-byte received data frame is to be
`broadcast through all four ports, such that four copies of the
`received data frame are to be stored in main memory 125, the
`adjusted 605c will indicate that the data frame is to be stored
`in at least two segments, with each copy being stored in two
`channels of a segment.
`Channel availability circuit 610 receives the outputs from
`memory 305 and determines where there are vacant channels.
`This is accomplished using logic gates or the like to determine
`sets of zeroes in a segment of memory 305. That is, channel
`availability circuit 610 determines if there are any single
`zeroes, pairs of zeroes, triples of zeroes or quads of zeroes.
`The results are output to segment availability circuit 615 and
`arbitrator circuit 620. Depending on the design of channel
`availability circuit 610, it may only register availability if
`contiguous channels in a segment are vacant or it may register
`availability if the proper number of channels is available
`regardless of contiguousness.
`Arbitrator 620 selects the channel(s) and segment(s) to
`receive the copies of the input data frame. Typically, main
`memory 125 will have multiple locations that are available to
`receive the copies of the input data frame. As an example, if
`switch 100 receives a 64-byte data frame for which only one
`copy is needed, and main memory 125 is empty, there are 64
`locations that can accept this data frame. Arbitrator 620
`selects one location from the available pool of 64 locations.
`Each OCLC stores data that are in turn used to determine
`when each port is to receive and output a stored data frame. In 40
`one implementation, each OCLC receives a code word that
`translates to one or more locations in main memory 125. This
`code word is stored in a queue. As the data are output from
`main memory 125 to the port associated with the OCLC, the
`code words stored in the queue are advanced. When a par(cid:173)
`ticular code word in the OCLC reaches the head of the queue,
`it is forwarded to frame address generator circuit 625.
`In the implementation shown having four ports, it is pos(cid:173)
`sible that two or more OCLCs will request data from the same
`channel or segment at one time. To avoid this collision of data
`from main memory 125, the frame address generator circuit
`625 arbitrates between the received code words.
`FIG. 7 shows an alternative switch 700 that includes a
`general processor 720. Like exemplary switch 100, switch
`700 includes four ports 105a-l 05d that are coupled with four 55
`external buses ll0a-ll0d and internal buses 115a-115c. Pro-
`cessor 720 is coupled with internal bus 115a and intermediate
`bus 115b. Memory 125 is coupled with internal buses 115b
`115c.
`The function and operation of most of the elements of
`exemplary switch 700 have been previously described and
`will not be repeated. One difference between exemplary
`switches 100 and 700 is the use ofa general purpose processor
`to perform the copying, the determining of acceptable
`memory locations to store the copies, and the outputting of
`data frames from memory 125 to ports 105a-105d for trans(cid:173)
`mission over buses ll0a-ll0d. Processor 720 contains
`
`6
`memory such as ROM or RAM (not shown) that holds the
`instructions used to control the operation of processor 720
`and therefore the operation of switch 700.
`FIG. 8 shows an exemplary process 800 for copying data
`frames into a memory. This process is initiated when the
`switch receives a data frame (step 805). The header informa(cid:173)
`tion, which contains at least destination information and
`frame size, is extracted from the data frame (step 810). From
`the destination information, the number of ports that are to
`10 output the data frame is determined (step 815) along with the
`size of the received data frame (step 820). From the numberof
`ports to output the data frame and the size of the received data
`frame, the minimum amount of memory necessary to store
`the copies of the data frame, with one copy for each port that
`15 is to output the data frame, is determined (step 825).
`Next, the empty locations in memory are determined (step
`830). In one implementation, the determination is made by
`storing I-bits and 0-bits in a separate memory, with the I-bits
`and 0-bits corresponding to full and empty locations, respec-
`20 tively, in the data frame memory, and polling this separate
`memory to locate an adequate concentration of0-bits empty
`locations to store the copies of the received data frame. Once
`all of the suitable locations in frame memory have been
`identified, one or more locations are selected to store the
`25 copies of the data frame (step 835). The copies of the data
`frame are then stored in the selected memory locations of the
`frame memory (step 840). Each copy of the data frame is
`associated with a port that will transmit that copy of the data
`frame and this association is stored along with the locations in
`30 frame memory of the copies of the data frame( step 845). The
`process then ends (step 845).
`FIG. 9 shows an exemplary process 900 for outputting data
`frames from a switch. The process begins when multiple
`associations are selected (step 905). In other words, every
`35 port of the switch is polled to determine if they have a data
`frame in frame memory that is ready to be transmitted. One
`exemplary method of performing this step is to store the
`associations in a queue and read them in a first-in-first-out
`(FIFO) order.
`With multiple ports requesting data from the frame
`memory at the same time, it is possible that a conflict may
`arise such that two ports will require data from locations that
`share a data output bus in the frame memory. Accordingly, a
`determination is made to see if there is a conflict (step 910). If
`45 there is no conflict such that every port that has data frames to
`output may do so simultaneously, then the data frames are
`read from the frame memory in parallel (step 915). The ports
`select the data frames that are to be output, based on the
`association described above, and output the selected data
`50 frames (step 920). The process then ends (step 925).
`If a conflict is determined (see step 910), then one of the
`ports that has a conflict is instructed to wait (step 930) and the
`remaining associations are checked again for a conflict (step
`910). At worst case, ports will be instructed to wait until only
`one port remains and then the remaining port will be able to
`retrieve and output its data frames freely (see steps 915-925).
`As shown in FIG. 10a, four data frames, each only a single
`channel wide, are stored in a segment 1005 of main memory
`in a conventional switch. The data frames are forwarded to
`60 copier 1010 where the necessary copies are made. In this
`example, two copies of each data frame are generated before
`the data frames are output to the ports. Since copier 1010 can
`only copy one data frame at a time, it follows that four read
`cycles are needed to output the four data frames L-O from
`65 Segment 9. It should be noted that if copier circuit 1010 were
`not present, the number of read cycles to output the four data
`frames shown increases to eight. It should also be noted that
`
`Ex.1028
`VERIZON / Page 14 of 17
`
`

`

`7
`if multiple data frames are not packed into a single segment,
`the use of the memory would be less efficient.
`In contrast, FIG. lOb, shows two segments, 1015 and 1020,
`which have multiple copies of data frames already in them, in
`accordance with the implementations described above. Due
`to the packing of all of the needed copies of the data frames
`into a single segment, the implementations described above
`will output the required Land M data frames in one read cycle
`and the N and O frames in another cycle. Assuming that there
`are no port collisions such as the L data frame and the M data
`frame being transmitted over the same port, the implementa(cid:173)
`tions described can transmit the needed data frames in half the
`time of conventional switches (i.e., in two read cycles).
`In one implementation, multiple segments of main
`memory 125 may be accessed simultaneously. This also pro(cid:173)
`vides increased efficiency. In FIG. 10c, the K and L data
`frames are read and transmitted first and the M data frames are
`read and transmitted second. Suppose that the arbitration
`circuit 620 or process places the N data frames and the O data
`frames in segments 4 and 5, respectively. If multiple segment
`access was not allowed, two read cycles would be needed to
`output the N data frames and the O data frame. However, in
`the implementation described above, multiple segment
`access is permitted and the N and O data frames can be read
`simultaneously if they do not have a port conflict.
`Another advantage of the described implementations over
`conventional switches is the ability to determine where there
`is adequate memory space in a segment to accept the data
`frame. In some implementations, the described circuit and
`process are systematic like a queue. In other words, the data
`frames are stored in main memory 125 as they are received
`and little packing of different frames into a single segment is
`done (i.e., each received data frame and its corresponding
`copies are stored in a single segment). However, in other
`implementations, the circuitry looks for available space and
`only arbitrarily selects channel(s) or segment(s) when a con(cid:173)
`flict arises. Thus, the data frames are not stored in a strict
`queue-like structure in main memory 125. Instead, the
`described implementations can pack different data frames or
`multiple copies of a data frame ( one per channel) into a single 40
`segment to allow for increased bandwidth when forwarding
`data frames over different ports in one read cycle.
`It should be noted that other details are implicit in the above
`descriptions. For instance, multiple ports are receiving data
`frames and attempting to have them stored in memory. In the
`exemplary circuit described above, two or more ports 105a-
`105d may attempt to simultaneously place a data frame on
`receiving bus 115a. This internal data collision can be
`avoided by implementing well-known techniques.
`In addition, most switches have error detection/correction.
`One example of an error is receiving only part of a data frame.
`Most switches, including those that implement circuits and
`techniques similar to those described above, will have error
`detection/correction techniques that will discard a received 55
`erroneous data frame and prevent it from being stored and/or
`transmitted in the network.
`Similarly, common error correction methods in broadcast
`and multicast situations may also be employed. For example,
`broadcast storms, where data frames are replicated and sent 60
`back and forth between two switches until there is no room for
`new data frames, can be avoided by using protocol techniques
`that will cause the excess data frames to be considered as error
`data frames and not copied nor forwarded.
`It should also be noted that the above discussion did not 65