Flow-control methods and systems for multibus systems

Methods and systems are provided that prevent buffer overflow in multibus systems. In one aspect, a method for controlling the flow of data in a multibus system includes, for each node having an associated broadcast bus in the multibus system, generating status information regarding available data storage space of each receive buffer of the node. The method includes broadcasting the status information to the other nodes connected to the broadcast bus and collecting status information regarding the available storage space of receive buffers of the other nodes connected to the broadcast bus. The method also includes determining whether or not to send data from the node to at least one of the other nodes over the broadcast bus based on the collected status information.

TECHNICAL FIELD

Computer systems, and, in particular, methods and systems for controlling buffer overflow in a multibus systems, are disclosed.

BACKGROUND

Organizations that maintain and manufacture data centers face increasing bandwidth demands. In particular, the bandwidth requirement for typical data center switches is increasing dramatically due to the growth in data center size and due to the shift to higher bandwidth link standards, such as 10 Gb, 40 Gb, and 100 Gb Ethernet standards. However, simply sealing up the bandwidth of existing electronic switch designs can be problematic. The scope for increasing the data rate of electronic signals is often limited by signal integrity considerations. Also, increasing the bandwidth of data paths increases cost and may be impractical. The energy efficiency of elements of the data center has become an important consideration, because as data rates increase a greater proportion of the power consumed by network switches can be attributed to electronic interconnects. Moreover, electronic switched fabrics typically used to handle switching in a data center, use point-to-point flow control on each individual link. As a result, flow control is buffered on every link in order to avoid data loss. Switch manufacturers and users continue to seek interconnect solutions for switches that provide for several generations of bandwidth scaling at reduced interconnect power, without increasing overall system cost.

DETAILED DESCRIPTION

Methods and systems that prevent buffer overflow in multibus systems are disclosed. In particular, method and system examples disclosed herein are directed to multicast flow control methods and to multicast flow control systems that prevent buffer overflow in multibus systems. The methods and systems can be adapted to a variety of different types of multicast routing schemes ranging from broadcasting to unicasting. The term broadcasting refers to simultaneously transmitting data to all destination nodes, while the term unicasting refers to sending messages to a single destination node. The multibus system can be implemented using multibus optical interconnect fabrics that can be used to replace packet switch devices in systems such as a sealable switches and multiprocessors. If the aggregate input bandwidth at any particular time exceeds either the internal bandwidth of the switch or the aggregate output bandwidth then information can be lost or corrupted. In order to avoid loss or corruption, the switch will need to have potentially unbounded input buffer capacity or flow control must be employed to prevent buffer overflow. Only the latter solution is possible. An example method and system prevents buffer overflow by periodically distributing buffer status information to all nodes. Every node receives the status information and knows the status of all buffers in the system. Each node filters the buffer status information to maintain only the status of the buffers connected to the node's transmit bus. When status information received by a node indicates that any of the buffers which the node transmits to is full, the node stops transmission.

The detailed description is organized into three subsections as follows: A description of multibus optical interconnect fabrics is provided in a first subsection in order to give an example multibus system in which flow control methods and systems can be applied. Flow control methods and flow control systems are described in the second and third subsections, respectively. Note that although flow control methods and systems are described with reference to an example multibus optical interconnect fabric, the methods and systems are not intended to be so limited. In practice, an example flow control method and system can be implemented in many different kinds of optical and electrical multibus systems.

Multibus Optical Interconnect Fabrics

Multibus optical interconnect fabrics (“optical fabrics”) transmit data encoded in optical signals. An optical signal encodes information in high and low amplitude states or phase changes of a channel of electromagnetic radiation. A channel refers to a single wavelength of electromagnetic radiation or a narrow band of electromagnetic radiation centered about a particular wavelength. For example, a high amplitude portion of an optical signal can represent a logic binary value (“bit”) “1” and a low amplitude portion of the same optical signal can represent a bit “0,” or vice versa. Optical fabrics can use multiple optical buses implemented in low loss waveguides and optoelectronics to replace the electronic connections and electronic fabric switches found in scalable data center switches. Optical fabrics are less constrained by signal integrity considerations and are amenable to higher spectral efficiency through the use of wavelength division multiplexing (“WDM”) and various modulation formats. Optical communication with optical signals can also be more power efficient than communication with electronic signals due to the low loss properties of the optical channels.

FIG. 1shows a schematic representation of an example multibus optical interconnect fabric100. The optical fabric100includes four optical broadcast buses (“broadcast buses”)102-105enabling each of the four nodes labeled0,1,2, and3to broadcast optical signals to itself and to three other nodes. As shown in the example ofFIG. 1, each broadcast bus is optically coupled at one end to one of the nodes0,1,2, and3. A node can include any combination of processors, memory, memory controllers, electrical-to-optical engines, optical-to-electrical engines, clusters of multi-core processing units, a circuit board, external network connections, or any other data processing, storing, or transmitting device. For example, the nodes0-3can be line cards in an optical communication switch, as described below in the subsequent subsection. In the example ofFIG. 1, the optical fabric100includes 16 optical tap arrays distributed so that four optical tap arrays are located along each broadcast bus. Each optical tap array is configured to divert a portion of the optical power associated with the optical signals carried by a broadcast bus to a corresponding node. For example, four optical tap arrays106-109are distributed along broadcast bus102. When node0broadcasts optical signals over broadcast bus102, optical tap array106diverts a portion111of the optical power associated with the optical signals back to node0, optical tap array107diverts a portion112of the optical power associated with the optical signals to node1, optical tap array108diverts a portion113of the optical power associated with the optical signals to node2, and optical tap array109diverts a portion114of the optical power associated with the optical signals to node3. As a result, nodes0,1,2, and3receive the same information encoded in the optical signals broadcast by node0, but at a fraction of the optical power associated with the optical signals output from node0.

In other examples, the broadcast buses of multibus optical fabrics are bundled reducing the number of optical tap arrays.FIG. 2shows a schematic representation of an example multibus optical interconnect fabric200. The optical fabric200is similar to the optical fabric100, but instead of using 16 optical tap arrays, the broadcast buses are bundled, reducing the number of optical tap arrays by a factor of 2. In particular, optical fabric200includes the same four broadcast buses102-105as optical fabric100, but with broadcast buses102and103bundled to form a bundled broadcast bus202and broadcast buses104and105bundled to form a bundled broadcast bus204. Optical fabric200includes four optical tap arrays206-209distributed along bundled broadcast bus202and four optical tap arrays210-213distributed along bundled broadcast bus204. Each optical tap array is configured to divert a portion of the optical power associated with optical signals carried by a bundled broadcast bus to a corresponding node. For example, suppose that node0is broadcasting a first set of optical signals on broadcast bus102and node1is broadcasting a second set of optical signals on broadcast bus103. Optical tap array206is configured to divert a portion214of the optical power associated with the first set of optical signals back to node0and divert a portion216of the optical power associated with the second set of optical signals to node0. Optical tap array207is configured to divert a portion218of the optical power associated with the first set of optical signals to node1and divert a portion220of the optical power associated with the second set of optical signals back to node1. Optical tap arrays208and209divert portions of the optical power associated with the first and second sets of optical signals to nodes2and3, respectively. As a result, the nodes0,1,2, and3receive the same information encoded in the first and second sets of optical signals broadcast by nodes0and1.

In the example ofFIG. 2, the broadcast buses are composed of four waveguides. For example, as shown inFIG. 2, where broadcast bus102couples to node0, slash “/” with the number “4” indicates that broadcast bus102is composed of four waveguides, and where optical tap array206diverts portions214and216of the optical power carried by bundled broadcast bus202of optical signals to node0is composed of 8 waveguides.

FIG. 3shows the waveguides comprising the broadcast buses102and103. In particular, broadcast bus102is composed of waveguides301-304, and broadcast bus103is composed of waveguides305-308. Each waveguide of a broadcast bus can transmit a separate optical signal generated by a node. For example, node0can broadcast data encoded in four separate optical signals, each optical signal carried by one of the four waveguides301-304. Each optical tap array is composed of a number of optical taps, each of which is configured to divert a portion of the optical power associated with an optical signal carried by one of the waveguides. For example, optical tap array206is composed of eight optical taps (not shown) with each optical tap configured to divert a portion of the optical signal carried by one of the waveguides301-308toward node0.

FIG. 3also reveals how the optical tap arrays can be configured to divert, using partial reflection, a portion of the optical power associated with the optical signals transmitted in the bundles of broadcast buses. In certain examples, the optical tap arrays distributed along a broadcast bus, or bundle of broadcast buses, can be configured so that each node receives approximately the same optical power associated with each optical signal. For example, as shown in the example ofFIG. 3, suppose that the optical power associated with each optical signal carried by the waveguides301-308is represented by P. In order for each node to receive the optical signals with approximately the same optical power P/4, optical tap array206is configured to reflect approximately ¼ and transmit approximately ¾ of the optical power of each optical signal carried by the waveguides301-308. As a result, the optical power of each optical signal310reflected toward node0is approximately P/4, and the optical power of each transmitted optical signal is approximately 3P/4. The optical tap array207is configured to reflect approximately ⅓ and transmit approximately ⅔ of the optical power of each optical signal carried by the waveguides301-308. As a result, the optical power of each optical signal311reflected toward node1is approximately P/4 (i.e., ⅓×3P/4), and the optical power of each transmitted optical signal is approximately P/2 (i.e., ⅔×3P/4). The optical tap array208is configured to reflect and transmit approximately ½ of the optical power of the optical signals carried by waveguides301-308. As a result, the optical power of each optical signal312reflected toward node2is approximately P/4 (i.e., ½×P/2), and the optical power of each transmitted optical signal is also approximately P/4 (i.e. ½×P/2). The optical tap array209can be a fully reflective mirror that reflects the optical signals with the remaining optical power, P/4, to node3.

Multibus optical interconnect fabrics are not limited to optically interconnecting four nodes. In other examples, optical fabrics can be configured to accommodate as few as 2 nodes and as many as 5, 6, 7, or 8 or more nodes. The maximum number of nodes may be determined by the optical power of the optical signals, the overall system loss, and the minimum sensitivity of the receivers used to detect the optical signals located at each node, as described below with reference toFIG. 5. In general, the optical tap arrays distributed along a broadcast bus, or bundle of broadcast buses, are configured so that when a node broadcasts an optical signal, each of the nodes, including the broadcasting node, receives approximately 1/n of the total optical power P of the optical signal, where n is the number of nodes.

FIG. 4shows an example of n nodes in optical communication with a bundle of broadcast buses402coupled to n nodes, two of which are represented by nodes404and406. The broadcast buses, such as broadcast buses408and410, comprising the bundle of broadcast buses402can be composed of any suitable number of waveguides. The optical fabric includes n optical tap arrays distributed along the bundle of broadcast buses402, a few of which are represented by optical tap arrays411-416. Node406outputs optical signals onto the broadcast bus410with optical power P. The optical tap arrays are configured so that each node receives a reflected portion of the optical signals with approximately the same optical power of P/n, as indicated by directional arrows418-423.

The optical tap arrays denoted by OTminFIG. 4reflect a fraction of the optical signal power to an optically coupled node in accordance with:

Rm≈1(n-m+1)
and transmit a fraction of the optical signal power in accordance with:

Tm≈(n-m)(n-m+1)
where m is an integer ranging from 1 to n. Thus, an optical tap array OTmreceives an optical signal and outputs a reflected portion with optical power PRmtoward an optically coupled node and outputs a transmitted portion with optical power PTm, where P=PRm+PTm+Lmwith Lmrepresenting the optical power loss at the optical tap array OTmclue to absorption, scattering, or misalignment. Note that the optical tap array416OTncan be a mirror that reflects the remaining portion of optical power transmitted by broadcast bus402to node426.

Note that optical fabric examples describe diverting a portion of the optical signals generated by a node back to the same transmitting node. This is done for two primary reasons: 1) it ensures that the mirror reflectivity is identical for all the taps in an array of taps, and that the tap structure is identical at each point on the bus except for the value of reflectivity of the tap array mirror. In practice, the optical tap arrays can be fabricated as a single piece of material and are distributed across all of the waveguides of a bundle of broadcast buses, as shown inFIGS. 2 and 3. In other words, it may not be practical in implementing an optical fabric with a large numbers of waveguides per bundle with optical tap arrays that distinguish particular waveguides that do not divert optical signals. 2) By diverting optical signals back to the source node from which they originated, the source node is able to perform diagnostic tests on the optical signals, such as testing optical signal integrity.

In other examples, the broadcast buses of a multibus optical interconnect fabric can be implemented using star couplers. For example, returning toFIG. 1, a star coupler comprising one input port and four output ports can replace the broadcast bus1and optical tap arrays106-109, where the input port carries the optical signals carried by broadcast bus102and each of the four output ports carries one of the optical signals111-114. Each star coupler can be configured so that an optical signal received in the input port is split into four output optical signals, each output optical signal carrying approximately ¼ of the optical power of the input optical signal.

The methods and systems herein are not limited to nodes broadcasting over a single multibus optical interconnect fabric. In other examples, nodes can communicated over more than one multibus optical interconnect fabric.FIG. 5shows a schematic representation of an example of four multibus optical interconnect fabrics enabling eight nodes to broadcast optical signals. As shown in the example ofFIG. 5, nodes0-3broadcast optical signals over optical fabric200, as described above. Like nodes0-3described above, nodes4-7broadcast optical signals to each other over bundles of broadcast buses502and504.FIG. 5also reveals that nodes0-3broadcast optical signals to nodes4-7over bundles of broadcast buses506and508, and that nodes4-7broadcast optical signals to nodes0-3over bundles of broadcast buses510and512.

Each of the nodes0-3shown inFIGS. 1-4includes flow-control electronics and a transceiver.FIG. 6shows a schematic representation of a node including flow-control electronics601and an example transceiver comprising a transmitter602and four receivers603-606. As shown in the example ofFIG. 6, the flow-control electronics601are in electronic communication with the transmitter602and the receivers603-606. The transmitter602can be configured with an array of light-emitting sources, such as light-emitting diodes, semiconductor edge-emitting lasers, or vertical-cavity surface-emitting lasers (“VCSELs”). In certain examples, the sources can be configured to emit electromagnetic radiation with approximately the same wavelength. In other examples, each source can be configured to emit a different wavelength providing for dense-wave division multiplexing channel spacing. In still other examples, the sources can be configured to emit wavelengths in wavelength ranges providing for coarse-wave division multiplexing channel spacing. The use of wavelength division multiplexing reduces the number of waveguides needed for the same number of channels. In the example shown inFIG. 6, the transmitter602comprises 4 sources, each of which is separately controlled by the flow-control electronics601to emit an optical signal. The transmitter602may include separate electronically operated modulators for modulating each channel of light generated by the transmitter602. Directional arrows610each represent a separate optical signal generated by a corresponding source. In certain examples, the optical signals610can be sent in separate waveguides of a broadcast bus in the multibus optical interconnect fabric. For example, with reference toFIG. 3, the transmitter602can represent the transmitter of node0with each of the 4 optical signals610carried by one of the waveguides301-304.

Each of the receivers603-606comprises an array of photodetectors. The photodetectors can be p-n junction or p-i-n junction photodetectors. Sets of arrows611-614each represent 4 optical signals generated by different nodes in the same manner as the optical signals generated by the transmitter602. For example, referring toFIG. 3, the sets of optical signals611and612correspond to optical signals310. In certain examples, each optical signal can be carried to a photodetector of a receiver via a separate waveguide. In other examples, each optical signal can be optically coupled directly from the associated broadcast bus to a photodetector of a receiver.

Flow-control electronics601are electronically coupled to the transmitter602and receivers603-606. The flow-control electronics601may include drivers for operating the light-emitting sources of the transmitter602and may include amplifiers tar amplifying the electronic signals generated by the photodetectors of the receivers603-606. The flow-control electronics receive electronic signals from a device, such as server in a data center, and send the electronic signals to the transmitter602to generate optical signals. The optical signals sent to the photodetectors of the receivers603-606are converted into separate corresponding electronic signals that are sent to the flow-control electronics601. The flow-control electronics601controls the flow of data in the multibus optical interconnect fabric. The flow-control electronics601monitor the utilization of input buffers (not shown) associated with the node. A buffer is considered full when the amount of free space in the buffer falls below a predefined threshold. Each node periodically broadcasts the state of all of the buffers used to receive data broadcast by the other nodes. Because each node is connected to all of the buses over the optical fabric, each node knows the status of all the buffers in the system. When any buffer is full, the flow-control electronics601are configured to stop transmission on the corresponding bus to avoid butter overrun. The flow-control electronics601are configured to handle point-to-point and multicast communications.

Multicasting Flow Control

Examples of multicast flow-control operations carried out by the flow-control electronics of each node are now described with reference toFIGS. 7-14. When each node sends an optical signal over an associated broadcast bus in broadcast or a unicast, the optical signal includes one or more data packets. Each packet includes a header and user data. The header includes control information, such as information identifying the node that sent the packet and information identifying the node, or nodes, destined to receive the packet. Each node receives the packets broadcast by all of the nodes connected to the optical fabric, as described above, and examines the header information. On the one hand, if a node is not identified as a destination node in the header, the node discards the packet. On the other hand, if a node is identified as a destination node in the header, the packet is accepted and the user data is processed. Because multiple packets can arrive at the same destination node concurrently, buffering is used to temporarily store the user data sent to the destination node. Flow control is used to prevent buffer overflow in cases where the rate of packet arrival from the optical fabric exceeds the rate that packets can be forwarded to the external ports.

In order to prevent buffer overflow and provide flow control, each node includes a number of receive buffers for temporarily storing data sent to the node over the optical fabric. In certain examples, the number of receive buffers at each node corresponds to the total number of nodes coupled to the node's broadcast bus in the optical fabric. Each receive buffer separately and temporarily stores the data generated by each node connected to the node's broadcast bus.FIG. 7shows an example of buffers associated with each of the nodes0-3described above. Each of the nodes includes four receive buffers identified by RX0, RX1, RX2, and RX3, where the numerical label identifies the node from which the data stored in the receive buffer originated from. Each receive buffer can be a region of memory used to separately and temporarily store the data sent by a particular node while the data is being input to the node. For example, each of the receive buffers700-703separately and temporarily stores data sent by corresponding nodes0-3and is destined for node0. Receive buffer RX0700temporarily stores the data sent by node0and is sent back to node0, as described above with reference toFIGS. 1-4: receive buffer RX1701temporarily stores data sent by node1; receive buffer RX2702temporarily stores data sent by node2; and receive buffer RX3703temporarily stores data sent by node3.

In certain examples, the nodes can all broadcast status information regarding that storage space available at each receive buffer every x clock cycles, such as every 20 clock cycles. The buffer status information may also be broadcast any time a node has no data to send. When all of the nodes broadcast status information at approximately the same time, all of the nodes know which nodes have buffer space available and which nodes cannot receive any more data.

FIG. 7also represents a snapshot of the status of the receive buffers associated with the nodes0-3at a particular point in time. In the example ofFIG. 7, each buffer broadcasts its buffer status information, where a bit “0” identifies an associated receive buffer as “not full” and a bit “1” identifies an associated buffer as “full.” The receive buffers700,702, and703of node0are not full and the receive buffer701is identified as “full.” Node0broadcasts status information704composed of four entries706-709with each entry identifying the status of a particular receive buffer. Entries706,708, and709have binary logic values “0” which correspond to nut full receive buffers700,702and703, and entry707has a binary logic value “1” which corresponds to a full receive buffer701. Node1broadcasts the status information710; node2broadcasts the status information712; and node3broadcasts the status information714. After nodes0-3have broadcast their status information, each node collects the status information of all the other nodes and formulates a collective status report of the buffers, which is represented inFIG. 7by an array716. Rows in the status report716corresponds to the status information704,710,712, and714. Each node filters the collective status report to monitor only the status of the buffers connected to the node's broadcast bus. The information contained in each column of the collective status report716is associated with a particular node and can be used by the node to determine whether or not the node can broadcast. For example, column718indicates the status of the buffers connected to node0's broadcast bus, and column720indicates the status of the buffers connected to node1's broadcast bus. Each node desiring to broadcast data examines the status information of the nodes connected the sending node's broadcast bus and determines whether or not the sending node can broadcast. For example, node0examines the entries in column718, which indicates that the receive buffers used by the nodes0-3to temporarily store data generated by node0are not full. As a result, node0can broadcast. However, when node1examines the entries in column720one of the entries is a bit “1,” indicating that one of the nodes, node0, does not have sufficient receive buffer space available for receiving data broadcast by node1. As a result, node1does not broadcast data and has to wait for the next round of status information to determine whether or not broadcasting is permitted. The status report716also indicates that node2stops broadcasting, but node3can broadcast.

FIG. 8shows a control-flow diagram summarizing a method for controlling the flow of data broadcast over a multibus optical fabric carried out by each node. The steps represented inFIG. 8are carried out by each node at the beginning of the dock cycle associated with broadcasting status information. In step801, a for-loop repeats the steps802-806for each receive buffer of the node. In step802, the node checks the available storage space in a receive buffer. In step803, when the space available in the receive buffer is below a threshold, the method proceeds to the step804; otherwise the method proceeds to step805. In step804, the node records the status of the receive buffer as “full.” In step805, the node records the status of the receive buffer as “not full.” In step806, if the available storage space of all of the receive buffers have been checked, the method proceeds to step807, otherwise, the method repeats steps802through805. In step807, the node generates status information identifying which receive buffers are full and which receive buffers are not full. In step808, the status information is broadcast over the optical fabric to all of the nodes connected to the node's broadcast bus. In step809, the node collects the status information generated by the other nodes connected to the node's broadcast bus. In step810, the node checks the receive buffer status associated with the other nodes connected to the broadcast bus. In step811, if the node determines that any one of the buffers is full, the method proceeds to step812, otherwise the method proceeds to step813. In step812, the node does not broadcast data and repeats the steps801-811at the start of the next clock cycle associated with checking and reporting the available storage status of the receive buffers. In step813, the node broadcast data.

Multicasting flow control methods are not limited to controlling broadcast data. Flow control examples can also be applied to multicasting data to one or more nodes. As described above, the nodes can all broadcast status information regarding the storage space available at each receive buffer every clock cycles or any time a node has no data to send. When all of the nodes broadcast status information at approximately the same time, all of the nodes know which nodes have buffer space available and which nodes cannot receive any more data, as described above with reference toFIG. 7. But unlike the flow control applied to a broadcast, under a multicast routing scheme a node can send data to receive buffers of one or more destination nodes even though an associated receive buffer of a non-destination node is full. Note that if the node sends data exclusively to only one destination node with a not full receive buffer, then the sending node is engaging in unicast communication.

FIG. 9represents a snapshot of the status of the receive buffers associated with the nodes0-3at a particular point in time during a data multicast. In the example ofFIG. 9, each buffer broadcasts its buffer status information, as described above with reference toFIG. 7. Node0broadcasts the status information902; node1broadcasts the status information903; node2broadcasts the status information904; and node3broadcasts the status information905. After nodes0-3have broadcast their status information, each node collects the status information of all the other nodes and formulates a collective status report908. As described above, rows in the status report908corresponds to the status information902,903,904, and905, and the information contained in each column of the status report908is associated with a particular node and can be used by the node to determine whether or not to send data to one or more nodes. However, unlike the flow control for a broadcast described above with reference toFIG. 7, for a multicast, each node can send data to the other nodes unless the associated receive buffer is full. For example, node1examines the entries in column910, which indicates that the receive buffers used by the nodes0-3to temporarily store data generated by node1are not full. As a result, node1can send data to the nodes0,1,2, and3. On the other hand, when node3examines the entries in column912the entry associated with the receive buffer RX3914of node2is a bit “1,” indicating that receive buffer RX3914of the node2is full, and node2does not have sufficient receive buffer space available for receiving data from node3. As a result, node3does not send data to node2, and has to wait for the next round of status information to determine whether or not sending data to node2is permitted. If, however, the data generated by node3is intended for nodes0and/or1, even though node2cannot receive data from node3, node3can send the data to nodes0and/or1. Note that if node3sends data exclusively to one node, say node0or node1, then node3is unicasting the data.

FIGS. 10A-10Bshow a control-flow diagram summarizing a method for controlling the flow of data multicast over a multibus optical fabric carried out by each node. Note that the first nine steps1001-1009, shown inFIG. 10A, are the same as the first nine steps801-809of the method shown inFIG. 8. InFIG. 10B, once the node collects the status information generated by the other nodes connected to the node's broadcast bus of step1009, the method proceeds to step1010, shown inFIG. 10B. In step1010, a for-loop repeats the steps1011-1015for each destination node. In step1011, the sending node checks the status of the destination node's receive buffer for storing data generated by the sending node, as described above with reference to the example ofFIG. 9. In step1012, if the space available at the associated buffer is not below the threshold, the method proceeds to step1013, otherwise the method proceeds to step1014. In step1013, the sending node sends the data to the destination node. In step1014, the sending node does not send data to the destination node. In step1015, if another destination's status information should be checked, the method proceeds to step1011, otherwise the method proceeds to step1016. In step1016, the steps1001-1015are repeated at the start of the next clock cycle associated with checking and reporting the available storage status of the receive buffers.

Multicast Flow-Control Systems

FIG. 11shows a schematic representation of an example first logic circuit diagram1100for implementing data broadcasting flow-control electronics601described above with reference toFIG. 6. The circuit diagram represents an example implementation of the logic for buffering and flow control in a node interfacing between point-to-point links on multibus optical fabric, as described above with reference toFIGS. 7 and 8. The logic circuit diagram1100includes a multiplexer1102that transmits electronic signals to the transmitter602and receivers1103-1106that receive electronic signals from receivers603-606, respectively. The circuit diagram1100also includes a demultiplexer1108and a point-to-point output multiplexer1110for interfacing with a computing device (not shown). For example, the computing device can be a line card of an optical switch, a server, a processor, and any other computing device. The demultiplexer1108receives data generated by the device and separates the data from the reverse flow control information that controls flow on the point-to-point output multiplexer1110. The multiplexer1110sends the data to a transmit buffer1112, where the data is temporarily stored before sending the data to the multiplexer1102which places the data on the corresponding broadcast bus of an optical fabric via the transmitter602. The point-to-point output multiplexer1110is electronically coupled to an arbitration unit1114and the transmit buffer1112. The transmitter buffer1112generates buffer status information which is sent to the multiplexor1110. The buffer status may be a value indicating the available space or a single bit indicating the buffer is full. The multiplexor1110sends the transmit buffer status; 1) any time there is no data to be sent; 2) when the far end of the link cannot receive further data; 3) and periodically during data transmission. The demultiplexer1108is also in electronic communication with the multiplexer1110and inhibits the sending of data when the destination node has insufficient buffer space. The multiplexer1102sends the full/empty status information of the receive buffers1122-1125any time there is no data to send. Additionally if data is being sent continuously to the multiplexer1102, the device periodically pauses data transmission, sends the receive buffer status information to the multiplexer1102, so that the other end of the link has status information that is up to date within this time interval.

The demultiplexers1103-1106are in electronic communication with corresponding select circuits1116-1119, which, in turn, are in electronic communication with corresponding receive buffers1122-1125and are in electronic communication with latches1128-1131. Each demultiplexer1103-1106sends data packets to a corresponding select circuit. Rich select circuit reads the header and determines whether or not the data is destined for the device. For example, suppose the select circuit1116receives a data packet from the demultiplexer1103. When the header indicates the data is destined for the device, the select circuit1116sends the data to the receive buffer RX01122, which temporarily stores the data. On the other hand, when the header indicates that the data is destined for a different device, the select circuit1116discards the data. Arbitration1114extracts the data stored in each receive buffer and transmits the data to the multiplexer1110, where the data is forwarded to the device for processing. The arbitration1114can use any well-known technique for deciding which of the receive buffers1122-1125to extract data from.

Each of the receive buffers1122-4125is also in electronic communication with the multiplexer1102and periodically checks the amount of data storage space available and sends the status information to the multiplexer1102, as described above with reference toFIGS. 7-8. The status information is transmitted from the multiplexer1102to the transmitter602and is broadcast to all of the nodes connected to the device's broadcast bus. The multiplexor1102continually broadcasts the receive buffer status when there is no data to send to the fabric. If data is being streamed continuously from the transmit buffer1112, the multiplexor1102periodically interrupts data transmission to send the buffer status information provided by the receive buffers1122-1125.

FIG. 11also shows each of the select circuits1116-1120electronically connected to corresponding latches1128-1131, which are connected to inputs of a logic OR gate1132. The output of the logic OR gate1132is connected to the multiplexer1102. During a receive buffer status reporting period described above, each of the demultiplexers1103-1106receives status information from a corresponding node connected to the device's broadcast bus. Each select circuit sends the status information to a corresponding latch. A latch outputs an electronic signal corresponding to bit “0” when the receive buffer on the corresponding node is not full and outputs an electronic signal corresponding to bit “1” when the receive buffer on the corresponding node is full. The logic OR gate1132receives the bits from the latches1128-1131. When at least one of the bits sent by the latches1128-1131is “1,” the logic OR gate1132generates and sends a status signal representing bit “1” to the multiplexer1102, which causes the multiplexer1102stop sending data and only send buffer status information. The status signal stops transmission onto the optical fabric. On the other hand, when all of the bits sent to the latches1128-1131are “0,” the logic OR gate1132sends a status signal representing bit “0,” allowing data to be transmitted.

FIG. 12shows a schematic representation of an example second logic circuit diagram1200for implementing data multicasting flow-control electronics601described above with reference toFIG. 6. The circuit diagram1200represents an example implementation of the logic for buffering and flow control in a node interlacing between point-to-point links on a multibus optical fabric, as described above with reference toFIGS. 9 and 10. As shown in the example ofFIG. 12, the circuit diagram is similar to the circuit diagram1100, except the circuit diagram includes logic AND gates1201-1204. Each logic AND gate has one input from the transmit buffer1112and one input from one of the latches1128-1131. For example. AND gate1201receives input from the transmit buffer1112and receives input from the latch1128. The outputs from the AND gates1201-1204are four separate inputs to the OR gate1132.

The AND gates1201-1204in combination with the OR gate1132can be used to control the flow of datamulticast to one or more nodes as follows. First, suppose each of the four nodes0-3is assigned a four bit word address represented in table 1:

NodeAddress01000101002001030001
The transmit buffer1112receives data packets that are destined for particular nodes. The data packet includes the address of a destination node and each bit of the four bit address is sent to one of the AND gates1201-1204. For example, the first bit “1” of the address “1000” is input to the AND gate1201, the second bit “0” is input to the AND gate1202, etc. As described above with reference toFIG. 9, each latch also inputs either a “0” bit or a “1” bit representing the status information associated with receive buffers. For example, if the receive buffer of node0is not full, the latch1128inputs a “0” bit to the AND gate1201, and if the receive buffer of the node1is full, the latch1129inputs a “1” bit to the AND gate1202. The four bit addresses of the destination nodes and the four bit status information associated with the corresponding receive buffers of the nodes are input to the logic AND gates1201-1204and the OR gate1132to determine whether or not data packets can be multicast to one or more destination nodes.

As an example, suppose the transmit buffer1119receives a data packet destined for node1(i.e., a unicast). The data packet includes the address of node1which is given by four bit word “0100,” and a “0” bit is input to AND gate1201, a “1” bit is input to AND gate1202, and “0” bits are input to AND gates1203and1204. Also suppose the latches1128-1131send the status information “0010,” indicating that the receive buffer of node2is full, but the receive buffers of nodes0,1and3are not full. The latch1130inputs a “1” bit to AND gate1203and the latches1128,1129, and1131each input a “0” bit to AND gates1201,1203, and1204, respectively. As a result, the AND gates1201-1204each output a “0” bit into the tour inputs of the OR gate1132, which outputs a status signal representing the bit “0,” indicating that the data packet destined for node1and temporarily stored in the transmit buffer1112can be sent to node1. By contrast, suppose the latches1128-1131actually sent the status information “0100,” indicating, that the receive buffer of node1is full, but the receive buffers of nodes0,2and3are not full. The latch1129inputs a “1” bit to AND gate1202and the latches1128,1130, and1131each input a “0” bit to AND gates1201,1203, and1204, respectively. As a result, the AND gate1202receives two “1” bits at both inputs and outputs a “1” bit to the OR gate1132. The OR gate1132outputs a status signal representing the bit “1” indicating that the data packet temporarily stored in the transmit buffer1112is not sent.

When the data rate onto the optical fabric is equal to or greater than the data rate from the point-to-point link, the transmit buffer1112from the point-to-point link can be omitted. However, with no transmit buffer1112, data transmission cannot be stopped on this flow-control electronic device, but instead is stopped at the data source at the remote end of the point to point link.FIG. 13shows a schematic representation of an example third logic circuit diagram1300for implementing data broadcasting flow-control electronics601described above with reference toFIG. 6, the circuit1300is similar to the circuit1100except the transmit buffer1112is omitted and the status signal output of the logic OR gate1132is input to the multiplexer1110. In particular, when at least one of the bits sent by the latches1128-1131is “1,” the logic OR gate1132sends status signal to the multiplexer1110, and the multiplexer1110forwards the status signal to the device, which responds by not transmitting data. On the other hand, when all of the bits sent to the latches1128-1131are “0,” the logic OR gate1132allows the device to send data to the demultiplexer1108.

Note that because the stop point-to-point transmission signal takes a longer path in the circuit1300than in the circuit1100, being forwarded across the point-to-point link to the device instead of controlling a transmitter602, the threshold at which the receive buffers of the circuit1300are considered full is lower than the threshold at which the receive buffers of the circuit1100are considered full in order to allow more space for data in transit.

FIG. 14shows a schematic representation of an example fourth logic circuit diagram1400for implementing data multicasting flow-control electronics601described above with reference toFIG. 6. The circuit1400is similar to the circuit1200except the transmit buffer1112and the OR gate1132are omitted and the status information output from the latches1129-1131is input to the multiplexer1110. The electronic device then determines whether or not to send data to the destination node based on the status information.