Switching ethernet controller

0001Notice: More than one reissue application has been filed and/or reissue patent has issued based on U.S. Pat. No. 5,923,660. The present application is a continuation reissue application of application Ser. No. 11/469,807, filed Sep. 1, 2006 now U.S. Pat. No. Re. 43,058, which is a continuation reissue application of application Ser. No. 10/872,147, filed Jun. 21, 2004, now U.S. Pat. No. Re. 39,514, which is a continuation reissue application of application Ser. No. 09/903,808, filed Jul. 12, 2001, now U.S. Pat. No. Re. 38,821, which is a reissue of U.S. Pat. No. 5,923,660, filed Jan. 28, 1997 as application Ser. No. 08/790,155.

FIELD OF THE INVENTION

0002The present invention relates to network switches generally and to switching Ethernet controllers in particular.

BACKGROUND OF THE INVENTION

0003A network switch creates a network among a plurality of end nodes, such as workstations, and other network switches connected thereto. Each end node is connected to one port of the network. The ports also serve to connect network switches together.

0004Each end node sends packets of data to the network switch which the switch then routes either to another of the end nodes connected thereto or to a network switch to which the destination end node is connected. In the latter case, the receiving network switch routes the packet to the destination end node.

0005Each network switch has to temporarily store the packets of data which it receives from the units (end node or network switch) connected to it while the switch determines how, when and through which port to retransmit the packets. Each packet can be transmitted to only one destination address (a “unicast” packet) or to more than one unit (a “multicast” or “broadcast” packet). For multicast and broadcast packets, the switch typically stores the packet only once and transmits multiple copies of the packet to some (multicast) or all (broadcast) of its ports. Once the packet has been transmitted to all of its destinations, it can be removed from the memory or written over.

0006Switching Ethernet controllers are network switches that implement the Ethernet switching protocol. According to the protocol, the Ethernet network (cabling and Ethernet ports) operates at 10 Megabits per second. However, most switches do not operate at that speed, since they require longer than the 10 Mbps to process the incoming packets. Thus, their throughput is less than 10 Mbps. Switches which do operate at the desired speed are known as providing “full-wire” throughput.

SUMMARY OF THE PRESENT INVENTION

0007It is an object of the present invention to provide an improved switching Ethernet controller (SEC) which provides full-wire throughput.

0008The SEC of the present invention achieves the high-speed operation by utilizing a plurality of elements whose operations are faster than those of the prior art.

0009For example, in accordance with a preferred embodiment of the present invention, the communication between SECs attempts to utilize the bus as little as possible so that the bus will be available as soon as an SEC wants to utilize it. In accordance with the present invention, each SEC includes a write-only bus communication unit which transfers the packets out of the SEC by utilizing the bus only for write operations. Thus, packets enter each SEC by having been written therein from other SECs and not by reading them in, since read operations utilize the bus for significant amounts of time compared to write operations. Having the bus available generally whenever a SEC needs it helps to provide the full-wire throughput.

0010In addition, the address table controller operates with a hash table storing addresses of the ports within the Ethernet network. The controller hashes the address of a packet to an initial hash table location value and then accesses that table location. If the address stored at the table location matches that of the input address, the port information is retrieved. However, if the address stored at the table location is other than that of the input address, rather than reading a pointer to the next location where values corresponding to the same hashed address can be found (as in the prior art), the present invention changes the hash table location values by a fixed jump amount and reads the address stored at the next table address. Due to the fixed jump amount, the hash table controller of the present invention always knows what the next possible table location is.

0011A further speed increase is found in the accessing of the temporarily stored packets. In the present invention, the packets are stored in a storage buffer including a multiplicity of contiguous buffers. Associated with the buffers is an empty list including a multiplicity of single bit buffers. A packet storage manager associates the state of the bit of a single bit buffer with the empty or full state of an associated contiguous buffer and generates the address of a contiguous buffer through a simple function of the address or number of its associated single bit buffer. The simple function is typically a multiplication operation.

0012The present invention also incorporates a network of SECs interconnected with PCI busses.

0013Finally, there is provided, in accordance with a preferred embodiment of the present invention, an Ethernet network including a) at least two groups of network switches, b) at least two PCI switch busses, wherein each group of network switches is connected to one of the PCI busses, c) at least two PCI-to-PCI bridges, wherein each PCI-to-PCI bridge is connected to one of the PCI switch busses and d) at least one interconnection PCI bus to which the PCI-to-PCI bridges are connected.

BRIEF DESCRIPTION OF THE DRAWINGS

0014The present invention will be understood and appreciated more fully from the following detailed description taken in conjunction with the drawings in which:

0015<figref idref="DRAWINGS">FIG. 1A</figref> is a schematic illustration of a network of switching Ethernet controllers;

0016<figref idref="DRAWINGS">FIG. 1B</figref> is a schematic illustration of a network of switching Ethernet controllers interconnected by PCI busses;

0017<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustration of a generally full-wire throughput, switching Ethernet controller, constructed and operative in accordance with a preferred embodiment of the present invention;

0018<figref idref="DRAWINGS">FIG. 3</figref> is a schematic illustration of an empty list block unit forming part of the switching Ethernet controller of <figref idref="DRAWINGS">FIG. 2</figref>;

0019<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart illustration of a bit clearing mechanism forming part of the empty list block unit of <figref idref="DRAWINGS">FIG. 3</figref>;

0020<figref idref="DRAWINGS">FIG. 5</figref> is a schematic illustration of a hash table address recognition unit, constructed and operative in accordance with a preferred embodiment of the present invention;

0021<figref idref="DRAWINGS">FIG. 6</figref> is a block diagram illustration of the logic elements of the address recognition unit of <figref idref="DRAWINGS">FIG. 3</figref>;

0022<figref idref="DRAWINGS">FIG. 7</figref> is a schematic diagram of a hash function, useful in the address recognition unit of <figref idref="DRAWINGS">FIG. 3</figref>;

0023<figref idref="DRAWINGS">FIG. 8</figref> is a schematic illustration of two network switches performing a write-only bus transfer protocol;

0024<figref idref="DRAWINGS">FIG. 9A</figref> is a flow chart illustration of the operations performed by the two switches of <figref idref="DRAWINGS">FIG. 8</figref> during the data transfer operation of the present invention; and

0025<figref idref="DRAWINGS">FIG. 9B</figref> is a timing diagram illustration of the activity of the bus during the operation of <figref idref="DRAWINGS">FIG. 9A</figref>.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

0026Reference is now made to <figref idref="DRAWINGS">FIGS. 1A</figref>, <b>1</b>B and <b>2</b> which illustrate, in general terms, the generally full-wire throughput, switching Ethernet controller (SEC) <b>10</b> of the present invention and its connection within a network, wherein each SEC <b>10</b> forms part of a network switch <b>12</b>.

0027<figref idref="DRAWINGS">FIG. 1A</figref> illustrates a plurality of network switches <b>12</b> connected as a peripheral component interface (PCI) bus, thereby to form a network. Optionally, a processor <b>16</b> and its associated memory unit <b>18</b> can also be connected to the bus <b>14</b>.

0028<figref idref="DRAWINGS">FIG. 1A</figref> illustrates one network switch <b>12</b> in some detail. As shown, the switch <b>12</b> comprises a memory unit <b>20</b>, such as a dynamic random access memory (DRAM) array, and a plurality of twisted pair drivers <b>22</b> for filtering data from an Ethernet unit <b>19</b> which implements a plurality of Ethernet ports. There typically is one twisted pair driver <b>22</b> per Ethernet port. The SECs <b>10</b> of each network switch typically provide the switching operations, switching data from port to port and from port to network switch, all in accordance with the switching information found in the headers of each data packet. The processor <b>16</b> can also be involved in the switching, as described in more detail hereinbelow.

0029<figref idref="DRAWINGS">FIG. 1B</figref> illustrates the interconnection of network switches <b>12</b> to create a large network or to enlarge an existing network. A plurality of network switches <b>12</b> are connected to PCI busses <b>14</b>A and <b>14</b>B. In <figref idref="DRAWINGS">FIG. 1B</figref>, PCI busses <b>14</b>A and <b>14</b>B are connected together via PCI bus <b>14</b>C to which they are connected through PCI-to-PCI bridges <b>28</b>A and <b>28</b>B, respectively. Thus, two bus networks can be connected together through the addition of another PCI bus and two PCI-to-PCI bridges.

0030<figref idref="DRAWINGS">FIG. 2</figref> details the elements of one SEC <b>10</b>. It comprises an Ethernet interface unit <b>30</b>, a frame control unit <b>32</b>, a switching unit <b>34</b>, an inter SEC control unit <b>36</b> and a bus interface unit <b>38</b>. The Ethernet interface unit <b>30</b> performs the Ethernet protocol through which unit <b>30</b> communicates the packets to and from the other elements of the SEC <b>10</b>. The frame control unit <b>32</b> directs the packet into and out of the DRAM memory unit <b>20</b>, as per instructions of the switching unit <b>34</b>, and provides the Ethernet header data to the switching unit <b>34</b>. The switching unit <b>34</b> determines where to send each packet, either out one of its ports or out the bus <b>14</b> to another of the network switches. The inter SEC control unit <b>36</b> controls the communication with the bus <b>14</b>. The bus interface unit <b>38</b> physically transfers packets to and from the bus <b>14</b>. The two interface units <b>30</b> and <b>38</b> perform standard protocols (Ethernet and PCI bus, respectively) and therefore, will not be described hereinbelow in any detail.

0031The frame control unit <b>32</b> typically includes input and output multiple first-in, first-out (FIFO) buffers <b>40</b> and <b>42</b>, respectively, a direct memory access (DMA) unit <b>44</b> and a descriptor control <b>46</b>. The FIFO buffers <b>40</b> and <b>42</b> each have one FIFO buffer per port defined by the Ethernet interface unit <b>30</b>. The descriptor control <b>46</b> controls <b>9</b> circular (or ring) transmit queues which are stored in the DRAM <b>20</b>. Each queue lists the packets to be transmitted through one of the eight ports or through the PCI bus <b>14</b>. The descriptor control <b>46</b> maintains read and write pointers for each queue so as to know which packets are still waiting to be transmitted.

0032For incoming packets, input FIFO buffer <b>40</b> receives and buffers packets from the ports. The DMA unit <b>44</b> transfers the currently available packet provided by the input FIFO buffer <b>40</b> to the DRAM <b>20</b> in accordance with the instructions from the switching unit <b>34</b>. After the packet has been properly received, the switching unit <b>34</b> indicates to the descriptor control <b>46</b> through which port to transfer the packet. The descriptor control <b>46</b> places information about the packet into the relevant transmit queue and, when the packet rises to the top of the transmit queue, the descriptor control <b>46</b> indicates to the DMA <b>44</b> to transfer the packet from the DRAM <b>20</b> to the buffer in output FIFO <b>42</b> for the appropriate port.

0033The switching unit <b>34</b> typically includes an empty list block <b>50</b>, a hash table address control unit <b>52</b>, an arbiter <b>54</b> and a DRAM interface <b>56</b>. The empty list block <b>50</b> manages the organization of the DRAM <b>20</b>, noting which buffers of the DRAM <b>20</b> are available for storing newly arrived packets and which buffers contain packets to be transferred out. As will be described in more detail hereinbelow, the empty list block <b>50</b> associates an empty list of single bit buffers with the buffers of the DRAM <b>20</b>. In addition, the empty list block <b>50</b> associates the state of the bit of a single bit buffer with the empty or full state of an associated DRAM buffer and generates the address of a DRAM buffer through a simple function of the address or number of its associated single bit buffer. The simple function is typically a multiplication operation. Thus, when a buffer request is received, the empty list block <b>50</b> relatively quickly can determine the address of the next available buffer.

0034When the empty list block <b>50</b> receives buffer assignment requests from the DMA <b>44</b> or from the inter SEC control unit <b>36</b>, the empty list block <b>50</b> assigns the currently available buffer based on the state of the single bits of the empty list. Similarly, on output, when the empty list block <b>50</b> receives notification from the descriptor control <b>46</b> of the buffers which have successfully been either placed into the output FIFO <b>42</b> or transferred to another SEC (via the inter SEC control unit <b>36</b>), the empty list block <b>50</b> then updates the state of the associated single bit buffer.

0035The hash table address control unit <b>52</b> receives the source and destination address information of the packet header from the Ethernet interface unit <b>30</b>. As will be described in more detail hereinbelow, control unit <b>52</b> operates in conjunction with a hash table (physically found in DRAM <b>20</b>) of the possible addresses of the entire network. The control unit <b>52</b> hashes the address of a packet to an initial hash table location value and then accesses that table location. If the address stored at the table location matches that of the input address, the port information is retrieved. However, if the address stored at the table location is other than that of the input address, the present invention changes the hash table location values by a fixed jump amount and reads the address stored at the next table address. Due to the fixed jump amount, the hash table controller of the present invention always knows what the next possible table location is for the current hash value and thus, can generally quickly move through the hash table to match the input address and to produce the associated port number.

0036Arbiter <b>54</b> controls the access to the DRAM <b>20</b> and DRAM interface <b>56</b> accesses the DRAM <b>20</b> for each piece of data (a packet or an address in the hash table) being stored or removed. Arbiter <b>54</b> receives DRAM access requests from the hash table control unit <b>52</b>, the DMA unit <b>44</b>, the descriptor control unit <b>46</b> and the inter SEC control unit <b>36</b>.

0037The hash table control unit <b>52</b> provides the port associated with the destination address of the incoming packet to the descriptor control <b>46</b>. Similarly, the empty list block <b>50</b> provides the descriptor control <b>46</b> with the buffer number in which the incoming packet is stored. When both values are received and the packet has been properly received (that is, without any corrupted data), the descriptor control <b>46</b> places the received buffer information in the transmit queue for the received buffer number and, at the appropriate moment, initiates the transfer of the packet from the DRAM <b>20</b> into the queue of output FIFO <b>42</b> for the appropriate port. A slightly different operation occurs for the PCI transmit queue, as will be described hereinbelow.

0038The inter SEC control unit <b>36</b> typically includes a PCI DMA <b>60</b>, a write-only transfer manager <b>62</b> and three interrupt registers, buffer request register <b>64</b>, start of packet register <b>66</b> and end of packet register <b>68</b>. The transfer manager <b>62</b> supervises the transfer protocol which, in accordance with a preferred embodiment of the present invention, is performed with only write operations. As discussed hereinabove, write operations utilize the bus <b>14</b> for relatively short periods of time only.

0039The descriptor control <b>46</b> activates the write only transfer manager <b>62</b> whenever there is buffer information in the PCI transmit queue for a packet which has not been transmitted. The descriptor control <b>46</b> provides the transfer manager <b>62</b> with the buffer address of the packet to be transferred and the port number of the destination SEC <b>10</b> to which the destination end node is attached.

0040To begin the transfer, the transfer manager <b>62</b> first prepares a “buffer request” message and writes the message into the buffer request register <b>64</b> of the destination SEC <b>10</b>. Typically the buffer request includes at least the address of the buffer storing the packet to be transferred and the port number of the destination SEC <b>10</b> to which the destination end node is attached.

0041The presence of a message in register <b>64</b> causes the transfer manager <b>62</b> of the destination SEC <b>10</b> to request that the empty list block <b>50</b> allocate a buffer in the DRAM <b>20</b> for the packet to be transferred. The empty list block <b>50</b> reviews its empty list (without reading anything from the DRAM <b>20</b>) and allocates the next available buffer (by changing the state of the bit associated with the buffer) to the packet to be transferred. The empty list block <b>50</b> provides the address of the allocated buffer to the transfer manager <b>62</b> which prepares a “start of packet” message with the address of the allocated buffer. The transfer manager <b>62</b> of the destination SEC <b>10</b> then writes the “start of packet” message to the start of packet register <b>66</b> of the source SEC <b>10</b>. Typically, the “start of packet” message includes at least the address of the allocated buffer (in the destination SEC <b>10</b>), the address of the buffer (in the source SEC <b>10</b>) storing the packet to be transferred and the port number of the destination end node.

0042The presence of a message in the start of packet register <b>66</b> causes the transfer manager <b>62</b>, of the source SEC <b>10</b>, to activate the PCI DMA <b>60</b> to write the contents of the buffer storing the packet to be transferred in the allocated buffer in the destination SEC <b>10</b>. The PCI DMA <b>60</b> of the source SEC <b>10</b> actually writes the packet to the PCI DMA <b>60</b> of the destination SEC <b>10</b> which, in turn, writes the transferred packet to the allocated buffer of its DRAM <b>20</b> after receiving permission from its arbiter <b>54</b>. The transfer manager <b>62</b> also prepares an “end of packet” message and then writes the message into the end of packet register <b>68</b> once the packet to be transferred has been successfully transferred. Finally, the transfer manager <b>62</b> indicates to the empty list block <b>50</b> to clear the bit of the empty list which is associated with the transferred packet. The “end of packet” message includes at least the destination port number.

0043The transfer manager <b>62</b> of the destination SEC <b>10</b> responds to the “end of packet” message by providing its descriptor control <b>46</b> with the port and buffer numbers of the transferred packet. The descriptor control <b>46</b> then adds the buffer information to the transmit queue for the indicated port. The packet is then transferred to the port as described hereinabove.

0044The following describe the empty list block <b>50</b>, the hash table control unit <b>52</b> and the write-only transfer protocol in more detail.

Empty List Block

50

0045Reference is now made to <figref idref="DRAWINGS">FIG. 3</figref> which schematically illustrates the empty list block <b>50</b> and its operation with the other elements of the SEC <b>10</b>. Block <b>50</b> comprises an empty list <b>110</b> and its associated multiple buffer <b>112</b> (stored in DRAM <b>20</b>), an empty list controller <b>114</b> and a bit clearing mechanism <b>121</b>. <figref idref="DRAWINGS">FIG. 3</figref> also shows the ports <b>120</b> (of Ethernet unit <b>30</b>) to and from which the packets of data pass, DMA <b>44</b> and hash table address control <b>52</b>.

0046In accordance with the present invention, the buffer <b>112</b> comprises a multiplicity of contiguous buffers <b>122</b>, each of M bits and large enough to store, for example, at least one packet of 1518 bytes. For example, M might be 1.5K or 1536 bytes. Alternatively, each buffer <b>122</b> might hold many packets.

0047Furthermore, in accordance with a preferred embodiment of the present invention, the empty list <b>110</b> is a buffer of single (0 or 1) bits <b>124</b>, each associated with one of the buffers <b>122</b>. <figref idref="DRAWINGS">FIG. 3</figref> shows 12 of each of buffers <b>122</b> and single bit buffers <b>124</b>; typically, there will be 1024 or more of each of buffers <b>122</b> and single bit buffers <b>124</b>.

0048Buffers <b>124</b> store the value of 1 when their associated buffer <b>122</b> stores a not-yet retransmitted packet and a 0 when their associated buffer <b>122</b> is free to be written into. The buffers <b>122</b> and bits <b>124</b> are associated as follows: the address of the beginning of a buffer <b>122</b> is M times the address (or number) of the single bit buffer <b>124</b> associated therewith. In other words, for M=1.5K, the buffer <b>122</b> labeled 3 begins at address 4.5K and the buffer <b>122</b> labeled 0 begins at address 0. Alternatively, the first buffer <b>122</b> can begin at an offset K and thus, the address of the beginning of a buffer i is M times the address of the single bit buffer <b>124</b> associated therewith plus the offset K.

0049The empty list block <b>50</b> operates as follows: when a port <b>120</b> provides a packet, the DMA <b>44</b> requests the number of the next available buffer <b>122</b> from the empty list controller <b>114</b>. Empty list controller <b>114</b> reviews the empty list <b>110</b> for the next available single bit buffer <b>124</b> whose bit has a 0 value. Empty list controller <b>114</b> then changes the bit value to 1, multiplies the address of next available buffer <b>124</b> by M (and adds an offset K if there is one) and provides the resultant address, which is the start location of the corresponding buffer <b>122</b>, to DMA <b>44</b>.

0050It will be appreciated that the empty list block <b>50</b> provides a very simple mechanism by which to determine and store the address of the next available buffer <b>122</b>. The mechanism only requires one multiplication operation to determine the address and the address value is stored as a single bit (the value of buffer <b>124</b>), rather than as a multiple bit address.

0051DMA <b>44</b> then enters the data from the incoming packet into the selected buffer <b>122</b>. Once DMA <b>44</b> has finished entering the data, it indicates such to the hash table address control unit <b>52</b> which in the meantime, has received the destination and source end node addresses from the Ethernet unit <b>30</b>. Unit <b>52</b> determines through which port to retransmit the packet. Empty list controller <b>114</b> provides unit <b>52</b> with the number of the buffer <b>122</b> in which the packet is stored.

0052When a packet is to be retransmitted, the empty list controller <b>114</b> provides the DMA <b>44</b> with the buffer address for the packet and the hash table address control <b>52</b> provides the DMA <b>44</b> with the port number. DMA <b>44</b> reads the data from the buffer <b>122</b> and provides the packet to the FIFO buffer for the relevant port <b>120</b>.

0053For unicast packets, once the DMA <b>44</b> has finished transmitting the data of the selected buffer <b>122</b>, DMA <b>44</b> indicates such to empty list controller <b>114</b> and includes in the indication the beginning address of the selected buffer <b>122</b>. Empty list controller <b>114</b> then determines the buffer number of the selected buffer <b>122</b> and changes the bit value of the associated single bit buffer <b>124</b> to 0, thereby indicating that the selected buffer <b>122</b> is now available.

0054Buffers <b>122</b> are larger by at least N bits than the maximum amount of data to be stored therein. N is the number of ports connected to the switch plus the number of switches connected to the current switch. For example, N might be <b>46</b>. The extra bits, labeled <b>132</b>, are utilized, for multicast packets, to indicate the multiple ports through which the packet has to be transmitted.

0055When the multicast packet enters the switch, DMA <b>44</b> sets all of the bits <b>132</b> (since multicast packets are to be sent to everyone). After the DMA <b>44</b> has transmitted a packet, whose port number it receives from the address control <b>52</b>, the DMA <b>44</b> indicates such to the empty list controller <b>114</b>. If the packet is a multicast packet, the address control unit <b>52</b> indicates to the empty list controller <b>114</b> to read the N bits <b>132</b> to determine if any of them are set. If they are, empty list controller <b>114</b> indicates to DMA <b>44</b> to reset the bit associated with the port <b>120</b> through which the packet was sent. When the DMA <b>44</b> indicates that it has finished resetting the bit, the empty list controller <b>114</b> does not change the associated single bit buffer <b>124</b>.

0056If the empty list controller <b>114</b> reads that only one bit is still set (i.e. the previous transmission was the last time the packet had to be transmitted), when the DMA <b>44</b> indicates that it has finished resetting the bit, the empty list controller <b>114</b> changes the bit value of the associated single bit buffer <b>124</b> to 0, thereby indicating that the associated buffer <b>122</b> is now available.

0057In the empty list <b>110</b>, bits typically change as data is received and transmitted. However, it is possible for data not to be transmitted if there are some errors in the network, such as a port being broken or a switch being removed from the network. In any of these cases, the bits in the empty list <b>110</b> associated with those ports must be cleared or else the associated buffers <b>122</b> will never be rewritten.

0058Therefore, the present invention includes bit clearing mechanism <b>121</b> which reviews the activity of the bits in the single bit buffers <b>124</b> and clears any set bits (i.e. of value 1) which have not changed during a predetermined period T. The period T is typically set to be small enough to avoid wasting storage space for too long but large enough to avoid clearing a buffer before its turn for transmission has occurred.

0059Bit clearing mechanism <b>121</b> comprises a multiplexer <b>140</b> and a state reviewer <b>142</b>. The multiplexer <b>140</b> connects, at one time, to a group of single bit buffers <b>124</b> and switches between groups of buffers every period T. State reviewer <b>142</b> reviews the state of the group of single bit buffers <b>124</b> to determine if all of the single bit buffers <b>124</b> changed from 1 to 0 at least once during the period T. If, at the end of period T, one or more bits in buffers <b>124</b> have remained in the set state (i.e. with value 1), the state reviewer <b>142</b> clears them to 0. Multiplexer <b>140</b> then connects to the next group of single bit buffers <b>124</b>.

0060The operations of the bit clearing mechanism <b>121</b> are detailed in <figref idref="DRAWINGS">FIG. 4</figref>. Specifically, at each clock tick t_i, the state reviewer <b>142</b> checks (step <b>150</b>) each bit. If the bit has changed to 0, the bit is marked (step <b>152</b>) as “changed”. Otherwise, nothing occurs. The process is repeated until the period T has ended (step <b>154</b>).

0061At the end of the period T, the state reviewer <b>142</b> clears (step <b>156</b>) any unchanged bits and the multiplexer <b>140</b> changes (step <b>158</b>) the group. The process is repeated for the next time period T.

Hash Table Control Unit

52

0062Reference is now made to <figref idref="DRAWINGS">FIGS. 5 and 6</figref> which illustrate the hash table control unit <b>52</b> of the present invention. <figref idref="DRAWINGS">FIG. 5</figref> illustrates the hash table control unit <b>52</b> and its operation and <figref idref="DRAWINGS">FIG. 6</figref> details the elements of unit <b>52</b>. The term “address” will be used herein to refer to MAC addresses and the term “location” will be utilized to refer to addresses within the hash table <b>212</b>.

0063Hash table control unit <b>52</b> comprises a hash table <b>212</b> and a hash table location generator <b>214</b>. Hash table <b>212</b> is shown with only 18 locations; it will be appreciated that this is for the purposes of clarity only. Typically, hash table <b>212</b> will have 32K locations therein and, in accordance with the present invention, stores only the MAC address and the port associated therewith.

0064Location generator <b>214</b> receives the MAC address, whether of the source end node or of the destination end node, and transforms that address, via a hash function, to a table location. The hash function can be any suitable hash function; one suitable function is provided hereinbelow with respect to <figref idref="DRAWINGS">FIG. 7</figref>.

0065In accordance with the present invention, if the generated table location stores an address which is not the same as the input MAC address, the location generator <b>214</b> generates a second location which is X locations further down in the hash table <b>212</b>. The hash table does not store any pointers to the next location. In accordance with the present invention, X is a prime number such that, if it is necessary to move through the entire hash table <b>212</b>, each location will be visited only once during the review.

0066For example, and as shown in <figref idref="DRAWINGS">FIG. 5</figref>, X is 5 and the first table location is the location labeled <b>1</b>. If the MAC address of location <b>2</b> does not match that of the input MAC address, the location generator <b>214</b> “jumps” to location <b>6</b> (as indicated by arrow <b>220</b>), and then to location <b>11</b> (arrow <b>222</b>), and then to location <b>16</b> of the hash table <b>212</b> (arrow <b>224</b>). Since there are only 18 locations in the hash table <b>212</b> of <figref idref="DRAWINGS">FIG. 5</figref>, location generator <b>214</b> then jumps to location <b>3</b> (arrow <b>226</b>) which is (16+5) mod <b>18</b>. If location <b>4</b> is also full, location generator <b>214</b> will generate locations until all of the locations of table <b>212</b> have been visited.

0067It will be appreciated that the hash table control unit <b>52</b> does not need to have pointers in table <b>212</b> pointing to the “next” location in the table. As a result, unit <b>52</b> knows, a priori, which locations in the table are next and can, accordingly, generate a group of locations upon receiving the MAC address. If desired, the data in the group of locations can be read at once and readily compared to the input MAC address.

0068<figref idref="DRAWINGS">FIG. 6</figref> illustrates the elements of the location generator <b>214</b> and its operation in conjunction with the table <b>212</b>. Location generator <b>214</b> comprises a hash function generator <b>230</b>, DRAM interface <b>56</b> (since the hash table <b>212</b> is typically implemented in DRAM <b>20</b>), a latch <b>234</b> and a comparator <b>236</b>.

0069The hash function generator <b>230</b> converts the MAC address MA, of 48 bits, to the table location TL₀, of 15 bits. The DRAM interface <b>56</b> generates the group of next table locations TL₀, TL₁and TL₂, where TL₁=TL₀+X and TL₂=TL₀+2X, etc. It will be appreciated that <figref idref="DRAWINGS">FIG. 6</figref> illustrates only three table locations but many more or many less can be generated at once, as desired.

0070DRAM interface <b>56</b> accesses the table <b>212</b> to read the addresses, A₀, A₁and A₂, and their associated data d₀, d₁and d₂, stored in table locations TL₀, TL₁and TL₂, respectively. The data d_iinclude the necessary information about the address, such as the switch identification number and any other desired information. The read operation can be performed at once or successively.

0071The output of each table location is latched by latch <b>234</b>. Comparator <b>236</b> then compares the address information A_iwith that of MAC address MA. If the two addresses match (i.e. a “hit”), then comparator <b>236</b> indicates to latch <b>234</b> to output the associated data d_istored therein. Otherwise, comparator <b>236</b> indicates to DRAM interface <b>56</b> to read the address A_iand associated data d_istored in the next table location.

0072If many table locations are to be read at once, the location generator <b>214</b> can include a multiplicity of latches <b>234</b>, one for each location to be read at once.

0073If one of the table locations is empty, as indicated by a valid bit of the data d_i, all locations after it will also be empty. Thus, the input MAC address has no corresponding stored address and therefore, the input MAC address is typically input into the empty table location. The valid bit in the associated data d_iis then set to ‘not empty’.

0074<figref idref="DRAWINGS">FIG. 7</figref>, to which reference is now made, illustrates an exemplary hash function, for typical MAC addresses, which can be performed by hash function generator <b>230</b>. In this embodiment, generator <b>230</b> considers only the 33 lowest significant bits (LSBS) of the MAC address. The 33 LSBs are divided into four bytes, labeled A, B, C and D. Byte A consists of bits <b>0</b>:<b>5</b>, byte B consists of bits <b>6</b>:<b>14</b>, byte C consists of bits <b>15</b>:<b>23</b> and byte D consists of bits <b>24</b>:<b>32</b>. Thus, byte A is 6 bits and the remaining bytes are 9 bits.

0075Hash function generator <b>230</b> comprises two XOR units <b>240</b>A and <b>240</b>B, a concatenator <b>242</b> and a swap unit <b>244</b>. The XOR unit <b>240</b>A performs an exclusive OR between bytes C and D and XOR unit <b>240</b>B performs an exclusive OR between the output of XOR unit <b>240</b>A and byte B. Concatenator <b>242</b> concatenates the output of XOR unit <b>240</b>B with byte A, thereby producing variable T of 15 bits. Swap unit <b>244</b> swaps the bits of variable T to produce the output table location TL. Thus, the value of TL<14> receives the value of T<0>, the value of TL<13> receives that of T<1>, etc. It will be appreciated that any hash function can be utilized. However, the desired hash functions are those which provide a uniform distribution of table locations for the expected MAC addresses. It is noted that the above hash function is easily implemented in hardware since XOR units and concatenators are simple to implement.

Write-Only Transfer Manager

62

0076Reference is now made to <figref idref="DRAWINGS">FIG. 8</figref> which illustrates the network configuration of the present invention and to <figref idref="DRAWINGS">FIGS. 9A and 9B</figref> which illustrate the data transfer operation of the present invention. Elements of <figref idref="DRAWINGS">FIG. 8</figref> which are similar to those of <figref idref="DRAWINGS">FIG. 2</figref> have the same reference numerals. It is noted that bus <b>14</b> has at least two lines, a data line <b>340</b> and an address line <b>342</b>.

0077In accordance with the write-only protocol of the present invention, packets of data are not transferred until a buffer location <b>319</b> is allocated for them in the DRAM <b>20</b> of the destination network switch <b>12</b>B. Furthermore, since the transfer operation is a DMA transfer, a packet is directly written into the location allocated therefor.

0078In accordance with a preferred embodiment of the present invention, when a packet of data is to be transferred, the source network switch <b>12</b>A initially writes (step <b>350</b>, <figref idref="DRAWINGS">FIG. 9A</figref>) a “buffer request” message to the buffer request register <b>64</b>b of the destination network switch <b>12</b>B. The buffer request message asks that the destination network switch allocate a buffer for the data to be transferred.

0079In the DMA transfer embodiment of the present invention, the source network switch <b>12</b>A provides, on address line <b>342</b>, the address of the “buffer request” register, the address of destination network switch <b>12</b>B and its “return” address. Source network switch <b>12</b>A provides, on data line <b>340</b>, the size (or byte count) of the packet to be transferred and the buffer location <b>319</b>A in which it is stored. The data of the data line is then written directly into the buffer request register.

0080In response to the buffer request message, the destination network switch <b>12</b>B determines (step <b>352</b>) the buffer location <b>319</b>B in which the packet can be stored. It then writes (step <b>354</b>) a “start of packet” message to the start of packet register <b>66</b>a of the source network switch <b>12</b>A which includes at least the location of the allocated buffer and the port numbers of the source and destination network switches. It can also include the byte count.

0081For example, in the DMA transfer embodiment of the present invention described hereinabove, the destination network switch <b>12</b>B provides, on address line <b>342</b>, the address of the “start of packet” register and the address of source network switch <b>12</b>A. Destination network switch <b>12</b>B provides, on data line <b>340</b>, at least the following: the byte count of the packet to be transferred, the address <b>319</b>B of the allocated buffer, the port number of the destination network switch <b>12</b>B, and, for identification, the buffer location <b>319</b>A in which the data is stored in the source network switch <b>12</b>A and the port number of the source network switch <b>12</b>A. As before, the data of the data line is then directly written into the start of packet register.

0082In response to receipt of the start of packet message in the start of packet register, the source network switch <b>12</b>A writes (step <b>356</b>) the packet of data to the allocated buffer location, followed by an “end of packet” message. Once the source network switch <b>12</b>A has finished writing the end of packet message, it is free to send the next packet, beginning at step <b>350</b>.

0083In the above described embodiment, the writing of the packet of data involves providing the address of the destination network switch <b>12</b>B and the buffer location <b>319</b>B on the address line <b>342</b> and the packet to be transferred on the data line <b>340</b>. The transferred packet is then directly written into the allocated buffer location <b>319</b>B. The end of packet message is written in a similar manner to the other messages, but to end of packet register <b>68</b>b. The address information includes the address of the end of packet register and the address of the destination network switch <b>12</b>B. The data includes the port number of the destination network switch <b>12</b>B, the buffer location <b>319</b>B and the byte count.

0084When the packet arrives at the destination network switch <b>128</b> it directly writes (step <b>360</b>) the packet into the allocated buffer location <b>319</b>B, as per the address on the address line <b>342</b>, until it receives the end of packet message for that allocated buffer location. The destination network switch <b>12</b>B is now free to perform other operations until it receives a next buffer allocation request.

0085<figref idref="DRAWINGS">FIG. 9B</figref> illustrates the timing of the packet transfer described in <figref idref="DRAWINGS">FIG. 9A</figref>. The initial source write operation of the buffer request message (step <b>350</b>) is typically relatively short since write operations take relatively little time and since the message to be transferred is small. Some time later, there is a destination write (DW) operation of the start of packet message (step <b>354</b>). The destination write operation takes approximately the same length of time as the first source write operation. Some time later, there is a further source write operation (step <b>356</b>) of the packet transfer and end of packet message. Since, for this operation, there is more data to be transferred, this source write operation is shown to take a longer time than the other two write operations. The source and network switches are free to perform other operations after they finish their writing operations.

0086It is also noted that, in the present invention, the source network switch <b>12</b>A is free to operate on other packets once it has finished writing its packet, and its associated end of packet message, to the bus. The source network switch <b>12</b>A does not need to ensure that the destination network switch <b>12</b>B has successfully received the packet since, in the present invention, the address for the data (in the destination network switch) is known and is fully allocated prior to sending the packet; the packet would not be sent if there was no buffer location available for it. In the present invention, the time it takes for the destination network switch <b>12</b>B to process the packet is not relevant to the operation of the source network switch <b>12</b>A.

0087It will be appreciated by persons skilled in the art that the present invention is not limited to what has been particularly shown and described hereinabove. Rather the scope of the present invention is defined by the claims which follow: