Method and apparatus for selectively discarding packet for blocked output queues in the network switch

Method and device for selectively discarding packets in network switching device for blocked output queue

<u>Field of invention</u>

The present invention relates to the field of communication, and particularly relates to a method and device for transmitting multiple copies of data through multiple ports of a device.

<u>Background of the invention</u>

In many network systems, such as packet switching networks (ie, Ethernet), it is often necessary to send the same data from a single-ended website to multiple terminal websites (stotion). For example: in a traditional e-mail system, a user needs to send the same e-mail message to four other users connected to the e-mail system.

In a packet-switched network, when a switching device receives a frame of data from another terminal's website from the switching device port, it needs to make a quick forwarding strategy. If the frame is sent to multiple terminal websites, the switching device must send a copy of the frame to multiple correct ports.

In almost most systems, there are many examples of excessive load on the source side of the system. For example, in a network with multiple ports, there will be outbound traffic congestion at certain specific ports or ports, making these ports at least temporarily unavailable for data transmission. However, other ports can still be used to transmit data. Therefore, some of the ports designated to transmit the same copied data are blocked, and the other ports designated to transmit the copied data are not blocked.

In the traditional multi-port network switching device, when all the ports designated to transmit copied data are blocked, the data to be transmitted will be discarded, and the lost data will be notified to the management system. If only some designated ports are blocked and others are not, the discarding procedure will still be executed. In other words, in some cases, all data will be discarded and no duplicate data will be sent out, even if only one port is congested and ten ports are not. This procedure will cause a relatively large amount of data to be discarded in the event of congestion, because as long as a designated port is blocked, it will block the provision of data to the remaining ports.

<u>Summary of Invention</u>

Therefore, it is necessary to arrange and use a method to control the transmission of copied data from multiple ports of a device. Make the device discard less data and send more data.

Such needs and other needs are met by one embodiment of the present invention. The present invention proposes a method to control copy of frames sent from multiple ports. The method also specifies some ports, the frame will be sent from these ports, and then this method will determine which ports are not used to transmit frames . Provide the frame to be sent to a designated port in these frames that can be used to send copied frames. However, these designated ports that can be used to transmit the copied frame are not used to transmit the discarded copy frame.

The advantage of this method is that the copied frame is only sent by designated ports, and these ports can send data. The only copy frames that will be discarded are those that will be sent from the designated port, but cannot be sent for some reason. Therefore, the present invention provides more transmission capacity from port to destination platform than simply discarding the entire frame. Therefore, the congestion of one port will not block the data provided to so many designated ports. Therefore, the frame data will be received by those who want to receive the frame as much as possible.

The aforementioned need is also met by another embodiment of the present invention that provides a network switching device with multiple ports and capable of transmitting multiple copies of a single frame. The network switching device has a plurality of ports, and the duplicate frame is sent through these ports. A port vector generator (port vector generator) is used to generate a port vector, the port vector specifies which port to send the copied frame. A transmission plan determines the utilization rate of a single copy frame port designated by the port vector for transmission. The transmission plan allows the copy frame to be transmitted by the available port among the ports designated to transmit the copy frame, and the action of dropping the copy frame is performed by the unavailable port among the ports designated to transmit the copy frame.

The advantage of the above-mentioned embodiment of the present invention is that the switching device transmits the most copied frames in the network as much as possible. If only a few ports are not used to transmit the frame, the copied frame will not be automatically discarded. This increases the amount of useful data transmission in the network. Avoid transmitting the frame to the network switching device for the first time, but transferring a complete network resource garbage.

The above-mentioned characteristics and other other characteristics, viewpoints and advantages of the present invention will be more clearly described in the following detailed description with accompanying drawings.

<u>Detailed description of the exemplary embodiment</u>

The present invention will be explained by taking one of the switching devices in a packet switching network, such as an Ethernet circuit, as an example. However, it is obvious that the present invention can also be applied to other packet switching systems as described below.

Figure 1 is a block diagram of an exemplary system of the present invention. In this system, there will be great convenience in operation. This example system 10 is a packet switching system such as an Ethernet circuit. The packet switching network includes an integrated multi-port switching device 12 that enables the exchange of data packets between network websites. The network includes different types of web sites. For example, there are 24 10M\bps web sites 14 that transmit and receive data at 10 million bits per second, and those that transmit and receive data at 100 million bits per second. 2 100M\bps internet sites 22. Therefore, the switching device 12 receives the data packet from the website 14 or the website 22 according to the Ethernet communication protocol, and selectively forwards the data packet to an appropriate destination.

According to the embodiment of the present disclosure, the 10M\bps network website 14 receives data from the exchange device 12 or transmits data to the exchange device via the medium 17 according to the half-duplex Ethernet communication protocol. The Ethernet communication protocol ISO/IEC8802-3 (ANSI/IEEE Std.802.3, 1993Ed.) defines a half-duplex medium access mechanism to allow all websites 14 to access network channels equally. The transmission of data on the medium 17 is not particularly distinguished and has priority. Each website 14 includes an Ethernet interface card that uses collision detection and carrier-sense multiple aeeess with collision detection. deteetion CSMA/CD) to listen (listen) the data transmission on the medium. The disappearance of network data transmission is detected by the deassertion of the received carrier wave on the sensing medium. Any website 14 that has data to transmit will wait for a predetermined time (predetermined time) after receiving the deconfirmation of the carrier wave on the medium, and then try to access the channel. This period of time is called the packet gap period (interpacket gapintorval IPG). If a plurality of websites 14 have data to be transmitted over the network, after receiving the deconfirmation of the carrier wave on the sensing medium, and after waiting for the packet gap period, they will try to transmit the data and cause collision. Therefore, the website that transmits the data will monitor whether there is a collision in the medium due to the simultaneous transmission of the two websites. If a collision is detected, the two websites will stop sending data, wait for a random number of times, and then try sending again.

100M/bps website22, according to the Ethernet standard IEEF802.3x full-duplex working document with flow control (0.3), it is better to operate in full-duplex mode. The full-duplex environment provides a two-way, point-to-point communication link between each 100 M/bps network website 22 and the switching device 12, where the switching device 12 and the website 22 can simultaneously transmit, Receive data without collision. The 100M\bps website 22 is connected to the network medium 17 with 100Base-TX, 100Base-T4, 100Base-Fx 100M\bps physical equipment (PHY) 20 respectively. The switching device 12 includes a media independent interface (MII) 24 to connect to the physical device 20. The 100M\bps website 22 can be connected to other networks in the form of a server or a router.

As shown in Figure 1, the network 10 includes a series of switching device transmitters (transceiver) 16 for performing time division multiplexing (time division multipIexing) of data packets transmitted between the switching device 12 and the 10M\bps website 14 And time division solves multiple tasks. A magnetic transformer module 19 maintains the shape of the signal on the medium 17. The switching device 12 includes a transmitter-receiver interface 18 for transmitting and receiving data packets from the switching device transmitter-receiver 16, and used on the serial NRZ (series non-return to zero) interface 23 Time division multiplexing communication protocol to accomplish this kind of work. The switching device transmitter and receiver 16 receives the packet from the serial NRZ 23, demultiplexes the received packet, and outputs the packet to the appropriate terminal website 14 via the network medium 17. According to the embodiment of the present disclosure, each switch device transmitter 16 has four independent twisted pair ports, and uses 4:1 multiplexing via the NRZ interface, so the overall pin ratio is determined by the switch device 12 Directly connect the pin which is reduced by 4 times.

The switching device 12 has a decision making engine, a switching engine, a buffer memory interface, a configuration/control/status register, a management counter and a MAC (media access control). The control protocol interface is used to support routing of data packets between the Ethernet sites 14 and 22. The switching device 12 also has an enhanced function of intelligent switching decision-making, providing statistical network information in the form of MIB management information base objects to external management entities, which will be described later. The switching device 12 also has an interface for enabling storage of external data packets, and switching logic (switchingIogic) to reduce the chip size of the switching device 12. For example, the switching device 12 has a synchronous dynamic RAM (SDRAN) interface 34 for external memory 36 to access. The external memory 36 is used to store the received frame, memory structure, and MIB counter information. The external memory 36 can It is 80, 100, 120MHZ SDRAM with 2 to 4Mb memory capacity.

The switching device 12 also includes a management port 30. The management port 30 enables an external management entity to enable the entity to control the overall operation of the switching device 12 through a management MAC interface 32 (magementMAC interface 32). The switching device 12 also includes a PCI interface 26, which is used to enable physical access via the external management of the PCI host and the bridge 28. On the other hand, if the PCI host and the bridge 28 have multiple switching devices 12 In occasions, it will be used like an expansion bus.

The exchange package 12 includes an internal decision-making body (Figure 2), which is used to selectively transmit data packets from any data source to at least one destination website. The internal decision-making body can also be replaced by an external rule checker. The switching device 12 includes an external rule checker (ERIC) 40, so that the external rule checker can generate a frame forwarding decision to replace the internal fast decision mechanism. Therefore, the frame forwarding decision can be generated by an internal exchange organization or by an external rule checker.

The switching device 12 also includes an LED interface 44 for outputting the status of each port and driving the LED external logic 46, the LED external selection 45 sequentially driving the human-readable LED elements 48. An oscillator 38 provides a 40 MHz clock input to the switching device 12.

FIG. 2 is a block diagram of the overall multi-port switching device 12 in FIG. The switching device 12 includes 24 10M\bps media access control ports 50, which are used to transmit and receive data packets in a half-duplex manner between separate 10M\bps websites (ports 1-24) . Two 100M\bpsMAC ports 53 are used to send and receive data packets in full duplex between separate 100M\bps websites (ports 25 and 26). As mentioned above, the management interface 30 also operates according to the MAC layer protocol (port 0). Each MAC port 50, 53, and 30 has a receive first-in-first-out (FIFO) buffer 52 and a transmit FIFO 54. Data packets from the website are received by the corresponding MAC port and stored in the corresponding FIFO 52. The received data packet is output from the corresponding FIFO 52 to the external memory interface 34 for storage in the external memory 36.

The header of the received packet is sent to the decision-making body at the same time, whether it is the internal rule checker 58 or the external rule check interface 40, to determine which MAC port will output the data. In particular, the packet header is sent to the internal rule checker 58 or the external rule check interface 40, regardless of whether the switching device 12 is planned to use the internal rule checker 58 or the external rule checker 42. The internal rule checker 58 and the external ruler 42 provide a decision-making logic to determine the destination MAC port of a specified data packet. Therefore, the decision-making organization sends a specified data packet to a single port, multiple ports, or all ports (that is, broadcast). For example, the header of each data packet has a source and a destination address, and the decision-making body can identify the appropriate output MAC port based on the destination address. On the other hand, the destination address is related to a virtual address (virtue address), which is considered to be related to a plurality of websites by the appropriate decision-making body. On the other hand, the received data frame will include a VLAN (virtue LAN) tagged frame according to the IEEE802.Id protocol, which stipulates other networks (via a router in the 22 group of the 100M\bps website) ) And the rules of the aforementioned website group. Therefore, the internal rule checker 58 or the external rule checker 42 via the interface 40 determines whether the frame temporarily stored in the buffer memory 36 is to be output to a single MAC port or multiple MAC ports.

The use of the external rule checker 42 has the following advantages, such as first, increase the capacity; second, before the frame is completely sent to the external buffer memory, a random-based ordering (radom-based ordering) is generated. The order is located in the decision queue of the enabling frame forwarding decision; thirdly, enabling to generate a first-order decision, regardless of the order of the received frame in the switching device 12.

The decision-making body (ie, internal rule checker 58 or external rule checker 42) outputs a forwarding decision to the switching subsystem 56 in the form of a port vector, where the port vector can identify the MAC of each data packet that should be received port. There are address data in the port vector from the rule checker. These addresses are located in the external memory 36 and store data packets. The port vector also contains the identification data of the MAC port used to receive data packets for transmission (for example, MAC ports 0-26). The switching device subsystem 56 retrieves the data packet identified by the port vector from the external memory photo 36 via the external memory interface 34, and provides the retrieved data packet to the appropriate, identified port's transmit FIFO 54.

More media and provide management and control information. For example, the management data interface 59 enables the switching device 12 according to the MII management standard (IEEE 802.3u), so that it exchanges control and status information with the switching device transmitter 16, 100 M\bps actual remaining device 20. The management data interface 59 outputs a management data clock (MDC), and supplies the bidirectional management data 10 signal path as its timing reference.

The PCI interface 26 is a 32-bit PCI interface that modifies the 2.1 compatible slave interface. It provides data access from the PCI host processor to the internal IMS state and configuration register 60, and provides the external memory 36 Data access. In the case of multiple switching devices, the PCI interface 26 can also be used as an expansion bus. The management port 30 interface passes a standard seven-wire (sevenwired) reverse-serial GPSI interface to an external MAC mechanism to enable a host controller that accesses the switching device 12 using a standard MAC layer protocol.

Fig. 3 is a more detailed description of the switching device subsystem 56 of Fig. 2 according to an exemplary embodiment of the present invention. The other components of the switching device 12 in FIG. 2 are redrawn in FIG. 3 to illustrate the relationship between the switching device subsystem 56 and these originals. The switching device subsystem 56 has a core switching engine (coreswitching engine) for receiving and forwarding frames. The main functional block diagram used to complete the switching mechanism includes: a port vector FIFO 70, a buffer manager 72, a plurality of port output queues (port output queue) 74, a management port output queue (management) port output queue) 75, an expansion bus port output queue (expansion bus port output queue) 77, a free buffer pool (free buffer pool) 104, a multiple copy queue (multiple copy queue) 90, multiple copy cache (multiplecopycache) 96, a reclaim queue (reclaim queue) 98. The operation and construction of these functional blocks will be explained in more detail, but a brief overview of the switching device subsystem 56 in Figure 3 is first presented in order to bring out the following discussion.

There are two basic types of frames for entering the multi-port switching device 12 from a port: a unicopy frame and a multicopy frame. A single copy frame is a frame received by one port and transmitted from the multi-port switching device 12 to another port. In contrast, a multi-copy frame is a frame that is received by one port and sent to more than one output port. In the third figure, each port can be represented by a MAC port 50, and the MAC port 50 has its own receiving FIFO 52 and transmission FIFO 54.

Regardless of whether a single frame or multiple duplicate frames are received by the internal MAC mechanism 50. When a frame packet is received by the port, the packet is placed in the receive FIFO 52. Each packet has a header, which is used to provide the rule checker, whether it is the internal rule checker 58 or the external rule checker 42. The internal rule checker 58 or the external rule checker 42 determines where the frame packet is to be dropped based on the information in the header, that is, which port or ports to which the frame packet is to be sent?

When the internal rule checker 58 or the external rule checker 42 makes its forwarding decision, the buffer manager 72 receives a free buffer pointer from the free buffer slot 104. The free buffer pointer is external memory. An address of 36, the receiving FIFO 52 will store the frame there. Once the buffer manager receives the free buffer indicator from the free buffer slot 104, the buffer pointed to by the free buffer indicator (point) will no longer be considered free, and the frame data will be accessed by direct memory access (DMA) The execution mode of the FIFO 52 is transmitted to the external memory 36 via the data bus 80. Although some buffers store frames, which will be described later, the frame data is stored at the address pointed by the free buffer indicator from the free buffer slot 104.

In addition to the header information, the external rule checker 42 or the internal rule checker 58 also receives a free buffer indicator from the buffer manager 72. This free buffer indicator is now called a frame pointer. Because it refers to the address in the external memory 36 where the frame is stored. The external rule checker 42 or the internal rule checker 58 uses the information in the header to make a forwarding decision, and generates a forwarding command in the form of a port vector. In this exemplary embodiment, the port vector is a 28-bit vector, and there is a set of bits for each output port to send a frame to the place where the frame should be sent. Assuming that in this overview example, the received frame is a single copy frame, the port vector generated by the external rule detector 42 or the internal rule detector 58 has only one bit set. The bit to be set is related to a certain port in the port group.

The external rule checker 42 or the internal rule checker 58 puts a port vector and frame indicator (also control opcode and VLAN tag (iudex)) to the port phasor FIFO 70. The port phasor FIFO 70 checks the port vector to determine which output queue 74 (or which multiple output queues 74) the frame indicator related to the port phasor should be placed in. The output queue 74 places the frame indicator at the top of the appropriate output queue 74. This will make the transmission of the frame line up.

At a certain point in time, the frame indicator passes through the output queue 74 to its bottom. When the frame pointer reaches the bottom end of the output queue 74, the buffer manager extracts the frame pointer and reads the frame pointer through the frame pointer read bus 86, and transmits the frame pointer to the transmit FIFO of the appropriate port 54. In this way, the frame transmission time will be scheduled. The frame data will be pointed to an address in the external memory 36 by the frame indicator and read by DIMA. Currently, it is placed in the appropriate FIFO 54. Waiting for delivery. Multi-copy transmission is similar to single-copy transmission, except that multiple bits in the port phasor are set. After these bits are set, you can specify which ports the frame should be sent to. The frame indicator is put into the appropriate output queue 74 and sent out by the relevant transmission FIFO 54.

The buffer manager 72 uses a special control queue, namely free buffer pool 104, muItiple copy queue 90, reclaim queue 98, and copy cache 96. These special control banks will manage the process of configuring buffers to store received frames. And manage the recovering buffer, so that once these frames are sent to the port where it is assigned to be sent, the car will use these buffers newly. The buffer manager 72 is also the output queue 74, and the control queues 104, 90, 98 are maintained in the overflow region of the external memory 36. This part will be described in detail later.

With the above operation overview as a background, each part of the switching device subsystem 56 and various viewpoints will be discussed in more detail here. The first viewpoint of the present invention is that there are different output queue 74 structures in the present invention. In addition to the output queue 74 designated for the 10 Mb/s output port and 100 Mb/s output port, there is an output queue 75 for the management port 30 and an output queue 77 for the expansion port 26. These output queues 75 and 77 have the same external structure as the output queue 74, but have different internal configurations, which will be described later.

FIG. 4 is a block diagram of the external structure of the output queue 74 according to an embodiment of the present invention. It is obvious from the fourth figure that the output queue 74 has three parts. If the highest performance is required, it is best to maintain all the sequence structure of the chip (refer to the multi-port switching device 12). If this is done, the value of the chip will be extremely high. When the chip is designed for use in a switching device, it has to arrange a large number of inputs, which becomes a dilemma. The present invention solves this dilemma by providing a single-output queue with a high-performance low-memory capacity area on the chip and an overload area outside the chip. When needed, the overload zone allows the queue to serve as a high-capacity queue, although this zone has lower performance than the area on the chip.

According to the embodiment of Fig. 4, the single logic output queue 74 of the present invention has three physical areas. This includes an output queue writing terminal 76, an output queue reading terminal 78, and an output queue overload area (generally designated as 110) in the external memory. As mentioned above, all the output queues 74 access the external memory 36 via the external memory interface 34. The present invention takes advantage of the bursting nature of the external memory, so that the data (frame index) is sent into and out of the overload area 110 via the bus 84 connecting the chip 12 and the external memory 36.

The output queue writing end 76 and the output queue reading end 78 are located on the chip 12. The output queue writing terminal 76 and the output queue reading terminal 78 are considered small and expensive resources. Conversely, composing the third part of the output queue 74, the overload area 110 is considered large and cheap. When the path to the overload area provides a low-performance, high-capacity path, the output queue writing end 76 and The output queue reads 78 questions, providing high performance.

In operation, the output queue writing terminal 76 receives an input data. According to an exemplary embodiment of the multi-port switching device 12 of the present invention, the input data is a frame indicator used to point to the first buffer of the external memory, and the buffer stores the first 256 bytes of a frame . The techniques of these techniques are easy to understand, however, whether it is the multi-port switch 12 or other technologies. The output queue structure 74 does not limit the type of its input data to only one type of frame index, but can arrange other forms of input data widely.

After the input data passes through the output queue writing end 76 and reaches its bottom end, the control logic related to the output queue 74 determines how to handle the input data. If there is still room at the output queue reading terminal 78 and the overload area 110 of the output queue 74 is empty, one or more input data will be transferred from the output queue writing terminal 76 to the output queue reading terminal 78. The operation of the output queue writing end 76 to transfer one or more pages of input data to the output queue reading end 78 is completely executed on the chip 12. Therefore, it is a low-lateney and fast input data flow.

If the output queue reading end 78 is full, and the output queue writing end 76 has at least one burst-size data amount (that is, 16-bit size), then the input data is written in a burst-size format To the overload area 110 of the output queue 74. If the output queue reading end 78 is full, but there is no burst-size data volume at the output queue writing end 76, then the input data stays at the output queue writing end 76, and nothing happens. Don't do it. At the end, the reading end 78 of the output queue will be vacated. When the reading end 78 of the output queue has enough capacity to accommodate the data volume of one group, if there is one data in the overload area 110 at this time, one is from the overload A group of the area 110 sends the data, which will be sent to the output queue and fetch end 78.

In the structure of the output queue, the output queue reading terminal 78 generally operates like a traditional queue because it extracts input data one by one. The output queue writing terminal 76 basically operates as a colletion function, combining data into a group and sending data for writing to the external memory 36. Therefore, the present invention converts a single event (putting an input data into the output queue 74) into a burst event (burstevont). If necessary, the output queue writing end 76 allows the accumulation of data, and then the group sends it to the overload area 110 of the external memory 36. The overload area 110 provides a cheap storage area during the data congestion period, instead of providing expensive, Its functional chips are only used in a few occasions. Although the overload area 110 of the present invention is located outside the chip, the access to the overload area 110 is an efficient way to group and send a number of bytes of information at the same time. This contrasts with the traditional queue structure, which is different from writing or reading only one input data at a time in the queue.

During the operation, if a large amount of data arrives at the input half queue 74, these input data are put into the overload area 110 to avoid overload of the queue 78 on the chip. Therefore, using the queue structure of the present invention, the action of dropping the frame can be mostly avoided. At the same time, the capacity of the overload area 110 can be easily adjusted by changing the size of the external memory 36. Furthermore, the overload area 110 with a special size can be classified to customize the size of the queue without affecting the performance of the output queue 74.

Typically, the queue is a prioritized structure with a first-in, first-out structure. In some types of queues, for example, the recovery queue 98 and the free buffer slot 104, the order of input data is not important. If it is possible to send data directly from the write end 100 to the read end 102, the present invention allows information to be transmitted through this path, that is, bypassing the overload area for queues. As long as the information is not order-sentive, even if the information is in the relevant overload zone, this operation is allowed. For example, the buffer of the reclaim area is not sensitive to order, so it can work like this, because when the buffer no longer needs to store the frame, it will eventually return to the free list of the free buffer slot. The order in the buffer is acceptable. Therefore, when the data is not sensitive to order, if the recovery queue 98 is written to the external memory overload area 110, in order to avoid changes in the bandwidth of the rabbit, as long as there is a space in the reading terminal 102, the information will be sent to the writing terminal 100. Transfer directly to the reading terminal 102. The recovery queue 98 is an example of a queue in which order-insensitive data is arranged in the queue. In many applications, there are still many data types that are not sensitive to order. Therefore, the feature of the present invention is to find a queued application that arranges such relatively different data types.

As shown in Figure 1 and Figure 2 of the exemplary embodiment of the present invention, there are 28 output queues in total (each one is related to an output port); 24 of them are for 10Mb/s user ports, 2 One for 100 Mb/user port, one for management port, and one for expansion bus port. When the frame indicators are arranged in a row for transmission, the output queues 74, 75, 77 provide a temporary storage place for the frame indicators. This is to extract the port vector of this type previously indicated by the FIFO 70 according to the port vector in a first-in-first-out (FIFO) manner, and write the frame indicator to one of the different output queues 74, 75, 77.

In the preferred embodiment of the present invention, the different output queues 74, 75, 77 include many or all of the following fields: single copy bit, frame indicator, control operation code or control signal, and VLAN (Virtual Local Area Network) Road) mark, the single copy bit marks the frame so that the frame will only be sent to a single output port. The frame indicator points to the frame on the external memory 36. The control operation code identifies the special information related to the frame (newly learned frame). The control signal is the information from the control opcode to instruct these ports how to control the frame before transmitting the frame. The VLAN tag provides a reference for the VLAN tag that must be attached to the output frame (if necessary). However, these examples are just examples, and the present invention can be applied to other fields of output queues in different forms.

The internal structure of one of the first types of output queue 74. The 10Mb/s output queue is shown in Figure 5. The 10Mb/s output queue 74 holds the input data for the frame to be sent to the 10Mb/s port. In this illustrative embodiment, the output queue writing terminal 76 of these queues holds 32 input data, and the output queue reading terminal 78 of these queues holds 16 input data. Each input data of 10Mb/s out of queue 74 has single copy bits and frame indicators. In the exemplary embodiment of the multi-port switching device of the present invention, the VLAN tag is not required because there is no VLAN tag attached to the 10Mb/s port.

The internal structure of an exemplary embodiment of the second output queue 74 is 100Nb/s output queue shown in Figure 6. The 100Mb/s output queue 74 holds the input data for the frame to be sent to the 100Mb/s port. The output queue writing terminal 76 of these queues holds 64 input data, and the output queue reading terminal 78 of these queues holds 16 input data. Each input data packet contains a VLAN tag, a partial control opcode, a single copy bit, and a frame indicator.

An example drawing of the external memory 36 is shown in Figure 7. The overall capacity of the external memory may be 4Mb, although in other embodiments, there are different capacities. According to the present invention, the external memory 36 as the overload area allows Simply change its external memory to increase or decrease the size of the output queue. It is better than imitating all the queue structures on one chip, so that the capacity of all the queues is determined by the production of the chip.

In order to meet the storage requirements of the switching device 12, an exemplary embodiment of the external memory 36 is configured with the following areas: the free buffer slot overload area 120, the recovery queue overload area 122, the multiple replication queue overload area 124, and the management port output queue Column overload area 126, individual output queue area 128 for 10Mb/s and 100Mb/s destination ports, expansion bus port output queue overload area 130, MIB counter 132, and global frame buffer pool (global frame bufferpool )134.

On the memory chip, the base address (baseaddress) of the memory in the register 60 group is programmable. The base address of each area in the external memory corresponding to (memory map) is programmable, and does not need length register (Iengthregister), corresponding to the length of any area is equal to from one base address to the next base bit The length of the address.

Because the length (and capacity) of the individual overload zones can be planned, the overall capacity of each queue can be planned. These features of the present invention allow an exchange device to be customized to provide a special output queue with a larger capacity when needed.

The input data stored in the following overload area is not suitable for the control queue of the chip 12 and therefore is put into the external memory 36. The free buffer overload area 120 stores the address index to the currently unused global frame buffer slot 134, and the reclaimed queue overload area 122 stores the frame index to the unneeded linked list chains, multiple copies of the queue The overload area 124 stores the frame index, accompanied by the copy code "&gt;=1" (indicating the arrangement of the frame index), or accompanied by the copy code "-1" (indicating the successful transmission of the frame).

The following overload area stores input data that is not suitable for the chip 12 to be used by the output buffer. The management port output queue overload area 126 stores frame indicators waiting to be transmitted to the management port. The output queue overload area 128 stores the frame indicators waiting to be sent to the appropriate 10Mb/s and 100Mb%s. The expansion bus port output queue overload area 130 stores frame indicators waiting to be transmitted to the expansion bus port.

The MIB counter area 132 contains statistics of all individual ports, and the statistics are updated periodically by the switching device 12. The switching device 12 maintains 8-bit and 16-bit counters on the chip for storing MIB statistics. The switching device 12 uses a frequency that prevents the loss of MIB data to update the 32-bit or 64-bit MIB counter on the external memory 36.

The global frame buffer slot 134 includes a buffer in a link list, and the link list stores received frame data. At any time, these linked lists contain the correct frame data, and the invalid buffers will be returned by the buffer manager 72 to the free buffer slot 104 or belong to the PCI host processor 28.

Referring now to FIG. 8, an exemplary embodiment of the present invention, the frame data received by any MAC port or PCI bus is stored in the external memory 36 in the form of a linked list. Although different embodiments of the present invention have different buffer lengths, the length of the buffer 140 used to create the link list in this example is 256 bytes, and the bit indicators of these buffers 140 are stored in the exchange. In the free buffer slot 104 of the device 12.

Once a frame is received at any port in the switching device 12, the buffer manager 72 requests the free buffer 104 to send an address indicator to link the address indicator 140 to store the frame. The address index of the first buffer of the external memory 36 originally stored the frame, but now it becomes the frame index of the frame. The frame indicator is used in the switching device subsystem 56 to arrange the frame to be transmitted.

The buffer 140 is linked together with the address index of the buffer header 142, and the buffer header 142 will point to the next buffer in the memory. The buffer header 142 also contains information about the frame data in the buffer 140. The first buffer header has 12 bytes, as shown in the format of the example buffer in Figure 9a. The next buffer header is 4 bytes. As shown in Figure 9b, the external memory group has 2 memory banks and 16 bytes in length. So the storage capacity of each buffer frame is 2568-16B=240B.

As shown in Figure 9a and Figure 9b, the format of the first and subsequent buffers includes the following columns:

Buffer format bit: Indicates the format of the buffer in use. If it is "1", it means that it is the first buffer. The buffer is 12 bytes in length. If it is "0", it means it is not the first buffer, and the buffer format is 4 bits. When linking these buffers, this rule applies to every remaining buffer.

E bit (marking the end of the frame): Indicates that this is the last buffer of a frame. When this bit is set to "1", there are no other buffers in the string.

C bit (CRC error detection): indicates that a CRC error is detected by the receiver. When the C bit is detected, the transmission function deliberately transmits an inverted CRC (inverted CRC) L bit (alignment error) ): indicates that the frame alignment error of the received frame is detected (accompanied by a CRC error).

Bit 0 (receiving FIFO overload): indicates that the receiving FIFO is overloaded and the data in the buffer is incorrect.

Buffer length: The correct number of bytes in the buffer data field from the first byte after the buffer header. This length cannot include the shift byte value.

Next buffer indicator: This indicator points to the next buffer. When the E bit is set to 1, the next buffer index is not the correct value.

Offset byte count: indicates the data area of the buffer frame, where the first bit of the frame starts, and the zero shift amount means that the data will be the first bit after the buffer header 142 Start with one bit, zero shift means that the data will start at the 16th bit of the buffer. A non-zero shift bit, the frame data will start after 16B + shift amount from the beginning of the buffer. The transmit function will skip the number of bytes recorded in the shift bit column.

P bit (port type): indicates the port type of the newly entered receiving frame. Zero means 10Mb/s, and one means 100Mb/s. This bit is designed to transfer the frame to the expansion bus before the frame is completely received by the switching device 12, and use the external memory 36 as a buffer. When the frame is sent to the external memory 36, this bit is changed by The host 28 works in conjunction with the time stamp.

T bit: indicates the type of received frame: tagged or untagged. One indicates the tag frame, and the ULAN identification column contains the received VLAN ID. Zero means untagged frame and ULAN ID is wrong.

Receiving port number: the port number will be received in the port frame

VLAN ID: The VLAN ID received by the tagged port. If the frame is received by an untagged port, this field is wrong.

R bit (recalculate CRC): indicates that the CRC in the transfer function must be disassembled and recalculated. When a tagged frame has been received, the switching device 12 sets this bit to 1. Furthermore, if the host 28 modifies the content of the frame, the host 28 must set this bit to 1. When the switching device 12 transmits a frame, it will check this bit to determine whether to transmit the existing CRC or disassemble and recalculate the CRC.

A bit (additional CRC): It means that there is no CRC at the end of the frame data. The host 28 can generate a frame in the memory (the frame has no CRC), and then set this bit to 1. When transmitting the frame, the switching device 12 will generate and append a CRC. If the A bit has been set, the frame must not contain CRC.

F bit (format bit): Identify the frame length/time stamp field. Zero means that this field is the time stamp of the newly entered frame, and one means that this field is the frame length of the received frame.

Frame length/time stamp: Determined in F bit. If the F bit is clear, this field represents the timestamp from the beginning of the received frame. The time stamp has a resolution of 1ms. If the F bit is set to 1, this field indicates the total length of the received frame, which includes the CRC and any received VLAN tags. When a frame is received, the switching device 12 uses a time stamp (from the timer register) to mark this field. If the host 28 has planned the switching device 12 to forward the frame to the expansion bus before the frame is fully received, it can use the time stamp to measure (with the speed of the receiving port) how much data it can grab from the external memory 36 , Without over-reading frame data. Once all frames are received, the switching device 12 writes the length of the frame into this field and sets the F bit to 1.

Copy number: used to indicate the number of copies that are successfully arranged by the port vector FIFO70 for transmission. If the buffer manager 72 needs to leave a place in the multi-copy cache 96 for new input data, this field is used to store the frame The number of copies of the indicator.

Figure 10 details certain elements of the switching device subsystem 56 of Figure 3. These components provide buffer storage space for storing frames and reclaiming these buffers. Once the buffers no longer store these frames, the buffers are reused. As mentioned earlier, all the output queues 74 and 75 pass frame indicators to the buffer manager (except for the output queue 77), and the buffer manager 72 will time the frames pointed to by the frame indicators. The buffer manager controls the following functions: 1) Manage the internal bus of the switching device 12. 2) It is convenient to sort the frame indicators to the output queue 74 and reverse the order of the frame indicators from the output queue 74. 3) Manage and control the queues 90 and 98 to allocate and return buffers to the free buffer 104. 4) Control the data flow to the external memory 36 and the data flow from the external memory 36. 5) Maintain the structure of the memory, including MIBs and overload areas. The buffer manager 72 includes a scheduling function to configure all external memory 36 accesses. These accesses include 1) writing a received frame data to the memory buffer 140. 2) reading from the memory The frame data of the buffer 140 is available for transmission. 3) Maintain (ie read and write) the frame index in each overload zone of the output queue 74 and the control queues 90 and 98. 4) Update the MIB counter.

After the buffer manager copies a specified frame to all appropriate output queues 74 and 75, the port vector FIFO70 calculates the number of copies (copy number), and places the frame index and copy number in the writing of the multi-copy queue 90end92. If the copy number is zero, it means that the frame is not forwardable; if it is one, it means a single copy transmission; if the number is greater than one, it means a multiple copy transmission. These three examples will be explained below. When the copy number is zero. It means that the frame indicator has a zero forwarding port vector and no bit is set. The port vector FIFO70 directly transmits the frame indicator to the writing end 100 in the recovery queue 98. When the port vector FIFO 70 serves the recovery queue 98, this situation will be described below. The buffer manager 72 breaks the link string of the buffer, and returns the address indicator of each free buffer to the writing end 106 of the free buffer slot 104.

When the copy number is one, it means that it is a single copy transmission. The port FIFO70 copies the frame indicator, control signal/control operation code, and VLAN indicator to the output queue 74 of the appropriate port, and the port vector FIFO70 sets the output queue 74 The single copy bit in the (see Figures 5 and 6) to indicate that this is a single copy transmission. When the buffer manager 72 reads the frame indicator and the single copy bit from the port output queue 74 , The buffer manager 72 will schedule the transmission as described above. The buffer manager 72 uses the frame indicator to configure the first buffer in the external memory 36, and this buffer stores the frame. The buffer manager 72 reads the first buffer, obtains the data from the first buffer, and sends the data to the appropriate MAC transmission FIFO 54. Assuming that the frame is extended to multiple buffers, the link described above will be linked to the next buffer. This structure provides the buffer manager 72 with an address that can be used to find and transmit the link related to the frame. All buffers of the knot. Once the data is placed in the FIFO 54 for transmission, the buffer will be invalidated and returned to the free buffer slot 104 for reconfiguration to provide other frames to store data.

When the copy number is greater than one, the port vector FIFO 70 copies the frame indicator, control signal/control operation code, and VLAN indicator to the output queue 74 of the appropriate port. (This is the case when referring to queue 74, and the same situation is when referring to queues 75 and 77). The port vector FIFO 70 clears the single copy bit in the normal frame indicator in the output queue 74, and puts the frame indicator in the writing end 92 of the multiple copy queue 90 in a state where the copy number is greater than one.

As long as the buffer manager 72 reads a frame indicator and clears the single copy bit in one of the output queue 74, the buffer manager will schedule the transmission of the frame and check the multiple copy cache 96 at the same time, see the input Whether the frame indicator of the data has a copy number of 1, if there is a frame indicator with a copy number of 1 in the multi-copy cache 96. The buffer manager 72 schedules the frame for transmission like the single copy transmission of the frame, and reclaims the buffer during the transmission. However, if the frame index is not in the multi-copy cache 96, or the frame index in the multi-copy cache 96 is greater than 1, the buffer manager 72 will transmit the frame but does not reclaim the buffer. After the transmission is successful, the buffer manager 72 places a copy of the frame indicator, along with the copy number "-1, to the output terminal 92 of the multi-copy queue 90.

Every time a multi-copy frame is transmitted, as long as the buffer manager 72 does not find a frame index with a copy number of 1 in the multi-copy cache 96, the buffer manager 72 will place a copy of the frame index To the multi-copy queue 90. Therefore, at any time, the multi-copy storage 90 will contain the frame indicator with the copy number.&gt;1, or the copy of the frame indicator with the multi-copy number -1.

The buffer manager 72 often serves the multi-copy queue 90 and the multi-copy cache 96 in order to recover obsolete buffers. When it serves the multi-copy queue 90 and reads the frame index with the copy number "&gt;1", the buffer manager tries to put this new input data (frame index and copy number) into the multi-copy cache 96. If the multi-copy cache 96 is full, the buffer manager 72 will leave room for a new frame indicator. The buffer manager 72 reads an older input data and updates the copy number of the input data in the external memory 36 in the buffer header, and then the multiple copy queue 96 clears the older input data. If there is still space available in the multi-copy cache 96, the buffer manager 72 can send the new input data from the multi-copy queue 90 to the multi-copy cache 96.

The buffer manager 72 serves the multi-copy queue 90 and reads the frame index of the copy number -1. It searches the multi-copy cache 96 to find the frame index address of the copy number "&gt;=1". In order to reduce or delete. If the buffer manager 72 finds a frame index of "&gt;=1", the buffer manager 72 will 1) if the copy number is greater than 1, then reduce the frame index of the multi-copy cache, or 2) if the copy number is just right If it is 1, delete the frame pointer in the multi-copy cache/copy several input data and put the frame pointer in the recovery queue 98.

If the buffer manager does not find the frame index with the copy number "&gt;=1", the buffer manager 72 will search the frame index buffer header in the external memory 36 (see Figure 9) to find a match Copy number. If the copy number in the memory is "1". The buffer manager 72 puts the frame pointer into the recycling queue 98. If the number in the memory is "&gt;1". The buffer management bay 72 puts the buy frame indicator and the copy number to the multi-copy queue 96, and then reduces the copy number.

The buffer manager 72 often serves the recovery queue 98 by reading frame indicators. Then the walking link serial returns the buffer to the free buffer slot 104. This action returns the buffer of the zero port vector frame, and the port vector FIFO 70 is arranged in the recovery queue. Or there is a frame that has been transferred from multiple copies to the most. As mentioned above, after the single copy frame is transmitted, the buffer link for the single copy signal will be directly returned to the buffer slot 104.

If the output queue 74 and the overload area 110 in the external memory 36 are full, so that the port vector FIFO 70 cannot put the frame pointer with the single copy transfer vector into the output queue 74, the frame will be abandon. The frame indicator is returned to the recovery queue 98, and the action of discarding the frame is recorded by the management resource of the switch.

If because one or more output queues and their overload area 116 in the external memory 36 are full, the port vector FIFO 70 cannot place one or more frame indicators with multiple copy transfer vectors, so the frame can only be forwarded To the output queue where there is room, and the copy number is placed in the multi-copy queue 90, it only reflects that the frame indicator has been successfully placed. Non-placement frame indicators will be recorded by the switch device management resources for which the frame indicators cannot arrange ports. If because one or more output queues and their overload area 110 in the external memory 36 are full, the port vector FIFO 70 cannot place one or more frame pointers with multiple copy transfer vectors, the frame will be passed to the recovery Queue 98, and the exchange of equipment trade management resources is officially notified.

The port FIFO 70 adopts the logic that can complete the above actions. For example, to determine which output queue is full, only put the frame indicator into those queues that are not full, and discard the others that are full. This logic can be controlled by this logic. The basic skills of functional narrative techniques are easily provided. Whether the output queue is full or not can be determined by comparing the number of frame indicators of a special output queue (this value is recorded in a register 60), and a threshold that can indicate that the queue is full comparing. Based on the above knowledge, for the multi-copy frame, the port vector FIFO 70 only discards those frame indicators that will be put into the output queue, and increases the count value of the abandoned frame (stored in another register 60). ).

The multi-copy queue 90 is a high-priority queue used by the buffer manager 72 to record how much of a specific multi-copy frame has to be transmitted before all the buffers (ie, address indicators) store frames To complete, all buffers can be recycled to the free buffer slot 104. The writing end 92 and the reading end 94 of this output queue hold 64 and 16 input data, respectively. The multi-copy queue 90 feeds data to the multi-copy cache 96, and the multi-copy cache 96 is used by the buffer manager 72 to determine when to reclaim the buffer. The structure of the multi-copy queue is described in Figure 12.

The port vector FIFO 70, according to the number of frame indicators successfully put into the output queue 74 of the frame indicator, copies the frame indicator of the frame and the copy number of "&gt;1" to the multi-copy queue 90. If a particular output queue 74 is full, the port vector FIFO 70 cannot place a copy of the frame indicator into the output queue 74; therefore, it cannot treat this event as an example of successfully determining the copy number.

Each time the buffer manager 72 reads an output queue frame indicator, and finds that the single copy bit is "0" (that is, this is a multiple copy action). It will look for the frame indicator with the copy number "1" in the multi-output cache. The frame indicator with the copy number "1" indicates that this is the last transmission. If it is found, after transmitting the contents of each buffer, the buffer manager 72 transmits the frame and reclaims the buffer like a single copy transmission by providing the invalid buffer to the free buffer slot 104. If it is not found, the buffer is buffered. The server manager 72 transmits the multiple copy frame and places a copy of the frame pointer with the copy number "-1" to the multiple copy queue 90. When the host runs out of a frame index of a multi-copy frame arranged in expansion bus output queue 75 or management port output queue 77 (via PCI interface 26), the host will send a copy number of "-1" The frame indicator copy is written into the multi-copy queue via the frame indicator register. This register is the one described in the block diagram of the register 60 in FIG. 2.

Similar to the output queue 74, the multi-copy queue 90 is constructed into an input path and an output path. The input path, or the writing end, allows the port vector FIFO 70 and the buffer manager to place the frame pointer/copy number to the copy queue 90. The input path, or read side, allows the multi-copy queue 90 to place the frame pointer to the multi-copy cache 96. The memory area that provides more storage capacity for frame indicators/copy numbers is called the multiple copy queue overload area 124, and this multiple copy queue overload area is provided by the external memory 36.

When the common frame indicators/copy numbers are written into a multi-copy queue 90, they are transferred from the writing end 92 to the reading end 94 until the reading end 94 is full. If there are more frame indicators/copy numbers to be written into the writing end 92 of the multi-copy storage 90, they will be written in the overload area 124 of the external memory 36. Once the reading end 94 and the overload area 124 of the multi-copy queue 90 are full, too many frame indicators/copy numbers placed in the winter copy queue begin to be filled into the writing end 92.

The order of the multi-copy queue 90 is maintained, so that as long as the reading end 94 of the multi-copy queue is cleared out of the position, the frame indicator/copy number will be moved from the multi-copy queue overload area 124 to the multi-copy queue 90 The reading end 94 and the writing end 92 of the multi-copy queue are moved to the multi-copy queue overload area 124.

Multi-copy queue cache 96 is similar to multi-copy queue 90, but provides a searchable area for scanning frame indicators/copy numbers. Multi-copy queue cache 96 holds 256 input data. The buffer manager 72 reads the frame index from the multi-copy queue 90, and places it in the multi-copy cache 96 or processes the frame index according to the copy number "&gt;1" or "-1".

Furthermore, every time the buffer manager 72 reads a frame indicator from the reading end 78 of the output queue 74, the buffer manager 72 will schedule the transmission. If the single copy bit is "0", (indicating a Multi-copy frame), the buffer manager 72 scans the multi-copy queue 96 to see if there is a frame indicator with the copy number "1". The copy number "1" indicates that this is the last transmission of the frame. If it is found, the buffer manager 72 will input the data during the transmission and return the buffer to the free buffer slot. If the buffer manager 72 is not found, after the transmission is completed, a frame indicator with a copy number "-1" is placed in the multi-copy queue 90.

The buffer manager 72 serves the multi-copy queue 90 by reading the frame index/copy number, puts the frame index/copy number into the multi-copy cache 96, or processes the frame index/copy number. This action has nothing to do with frame transmission. The following two examples are related to the buffer manager reading the copy number of the frame indicator, and see if the copy number is "1" or "-1".

1) If the buffer manager 72 reads a frame index of a copy number "&gt;1" from the multiple copy queue 90. Assuming that the multi-copy cache 96 has storage space at this time, it writes a new input data. If the multi-copy cache 96 has no storage space, the buffer manager 72 must clear some space in the multi-copy cache 96. The way to clear the space is to read the older frame indicator/copy number in the multi-copy cache 96, and update the header of the frame indicator buffer in the external memory 36 with the copy number in the multi-copy cache 96 , And then delete the older input data in Duplicate Cache 96, so that a storage space can be cleared. Once there is storage space, the new frame indicator/copy number can be written into the multi-copy cache 96.

2) If the buffer manager 72 reads a frame index of a copy number "-1" from the multiple copy queue 90. Then the buffer manager 72 searches the multi-copy cache 96 to see if there is a frame index with the frame index copy number "&gt;=1. The following two cases depend on whether the buffer manager 72 finds it in the multi-copy cache 96 Eligible frame indicators.

a) If the buffer manager 72 finds a qualified frame indicator, assuming that the input data copy number of the multi-copy cache 96 is "1", the buffer manager 72 will delete the input data of the multi-copy cache and add the The frame indicator is placed in the recovery queue 98. If the copy number of the input data of the multiple complex cache 96 is "&gt;1", the buffer manager 72 will decrement the copy number by one.

b)) The buffer manager 72 does not find a matching frame indicator, which means that the matching frame indicator has been moved to the buffer header of the frame link series on the external memory 36. The buffer manager 72 must go to the head of the buffer and read the copy number. If the value of the copy number is "1", the frame is no longer needed, and the buffer manager 72 puts the frame indicator in the recovery queue 98. If the value of the copy number (in the memory) is "&gt;1", the buffer manager 72 will put a copy of the frame indicator/copy number into the multiple copy cache 96 and reduce the copy number by one. If the multi-copy cache 96 is full, the buffer manager 72 moves an older frame pointer/copy number to the external memory 36 in order to clear a storage space.

The recovery queue 98 stores frame indicators that point to unnecessary link series. When the buffer manager 72 serves the multi-copy cache and finds that the value of the copy number of the frame indicator is "1", it will write a frame indicator to the recovery queue. (This means that the final transmission of the frame has been successfully achieved). Furthermore, the port vector FIFO will also write a frame indicator to the re-declared queue 98 under the following conditions: 1) The port vector of the frame indicator is empty, or 2) because all port vectors are forwarded to the queue It is full, causing the frame indicators to be unable to be arranged. Finally, when the host finishes using a single copy frame arranged by the expansion bus port output queue 77 or the management port output queue 75, the host will write a frame pointer to the recovery queue 98 (using the frame pointer temporarily Memory).

When the buffer management shell 72 processes the input data of the recovery queue, it operates a link series of frame pointers to return each buffer to the space buffer slot 104. In the exemplary embodiment of the present invention, the internal structure of the recovery queue is not described. In the exemplary embodiment of the present invention, the recovery queue only contains a frame indicator (14-bit) structure. The writing end of the recovery queue holds 64 input data, and the reading end of the recovery queue holds 16 input data. Similar to the output queue 74, the recovery queue 98 is constructed into an input path and an output path. The input tenon, or writing end, allows the buffer manager 72 to place the frame indicator in the recovery queue 98. The output path, or the reading end, allows the buffer manager 72 to read the frame indicator and return all related buffers to the free buffer 104. More frame indicator storage capacity is provided by the recovery queue overload area 122, and this recovery queue overload area is provided by the external memory 36.

When the frame indicators are written into an empty recovery queue 98, they are passed from the writing end 100 to the reading end 102 until the reading end 102 is full. If there are more frame indicators to be written into the writing end 100 of the recovery queue 98, they will be written into the overload area 122 of the external memory 36. Once the reading end 102 and the overload area 122 of the recovery queue 98 are full, too many frame indicators placed in the recovery queue 98 begin to fill the writing end 100.

FIG. 11 illustrates an exemplary embodiment of the internal structure of the free buffer slot 104. The free buffer slot 104 is a FIFO, and contains an address indicator to all free buffers 140 in the external memory 36. When all the frames are received, the buffer management shell 72 captures the available address indicators from the free buffer slot 104 to store the new incoming data. The buffer manager 72 also configures the address index from the free buffer slot 104 to the host processor 28 (when required to do so). The host can request or return an address indicator to the space buffer slot 104 by writing or reading a register in the free buffer register 60 in the direct input or output space (dircer input/output space). In the present invention, the writing end 106 and the reading end 108 of the free buffer slot 104 each hold 64 input data.

The free buffer slot 104 is configured as an input path and an output path. (Similar to the output queue 74), the input path or the writing end 106 allows the buffer manager 72 or the host 28 to place the address pointer to the free buffer slot 104. The output path is also referred to as the reader 108, allowing the buffer manager 72 to provide the address indicator to the host 28, or to pull the address indicator from the free buffer slot 104 for storing the received frame data. The storage space for storing more available address indicators is provided by the free buffer and overload area 120 of the external memory 36, as described above.

When the switching device 12 starts to operate, the reading terminal 108 generates an address indicator for the idle buffer slot. When the frame comes, the free list in the free buffer slot 104 is read. If there are not enough buffer indicators at the writing end 106 to control data communication, the overload area 120 is accessed to obtain more buffer indicators.

When the switching device 12 starts to operate, a specific exemplary embodiment of the present invention proposes a method for providing a better buffer index. When the switching device is connected to the power supply for the first time, the overload area 120 in the external memory 36 does not need to have a buffer indicator. Instead, the buffer index is generated during operation. When the switching device 12 is connected to the power supply, a buffer index can be generated and can be placed in the overload area 120. However, at this time, there are 16,000 to 32,000 such buffer indexes, which will reduce the booting action of the switching device 12. The invention adopts some good features during the start-up period, for example, all the buffers are free, and the identification codes of these buffers are also known. Therefore, after power-on, when these buffers are needed, the count 180 is used to generate these buffers. As described in Figure 10. A free list count generator 180 (free list count generator) is connected to the input of the multiplexer 182. At startup, because the free list in the free buffer slot 104 is empty, the free count list generator 180 generates a buffer index. Once the free list reaches its highest count, it no longer generates buffer indicators.

When a frame packet is received by the switching device 12, the frame packet will be broken up into a fixed-length buffer. Generally speaking, the size of the frame will vary. The buffers have a length of 256 bytes, and the data storage part has a length of 240 bytes. After the content of the buffer is transmitted, the buffer indicator is placed in the recovery queue 98, and if the buffer chain can work, it is directly placed in the empty buffer slot 104. During the operation of the switching device 12, any address indicator that returns to the empty buffer slot 104 is transferred from the writing end 106 to the reading end 108. If the reading end 108 is full, more address indicators will be written to the external In the overload area 120 of the memory 36. Once the reading end 108 and the overload area 122 are full, and the address index of the free buffer slot 104 is placed, the writing end 106 of the space buffer slot 104 will start to be filled.

FIG. 13 is a block diagram illustrating the internal management of the multi-copy queue 96 according to an embodiment of the present invention. As discussed briefly above, the chronological order of the input data of the multi-copy cache 96 is maintained. In the present invention, as in the aforementioned technique, the chronological order is not maintained by the time stamp, but by the physical ordering of the memory. The multiple copy cache 96 of the present invention must avoid the use of correctness bits at the same time, but instead use the correctness of decoding. This aspect will be discussed below.

Referring to Figure 13, the multi-copy cache 96 is constructed as a four-channel set-associative memory. Any input data that enters the multi-copy queue 96 includes frame indicators and their copy numbers. , As mentioned earlier. The lowest six bits of the frame indicator determine which row of each group of related caches 96 to store the frame in. In an embodiment of the present invention, although the size of the cache can be increased, and the number of rows There is no limit, but the cache 96 of the present invention has only 64 rows.

Each group of related cache 96 divides all the rows into four major rows, and each major row can be searched in parallel. When the buffer manager 72 stores an input data in the cache 96, it is always stored in the upper leftmost bit (51-39), which is specified by the lowest 6 bits of the frame indicator. When this large line is read, all input data is shifted to the right by 13 bits, and this large line will be written back again. The input data actually written into the cache 96 includes the leftmost 8-bit address tag of the frame indicator and the 5-bit copy number related to the frame indicator. When the input data is read out from the cache 96, all the bits of the frame label in the frame indicator and the line number in the cache 96 will be rearranged.

If the cache is full and there are new input data to be written, the oldest input data in the cache will be removed from the cache. As mentioned above, in the case of the buffer 142, the copy number followed by the removed frame indicator will be written into the frame buffer header 142 pointed to by the removed frame indicator in the external memory. Therefore, the frame is stored in the external memory 36 (ie, the buffer 140), and this external memory serves as the overload area of the multi-copy cache 06 for storing the copy number.

An advantageous feature of the present invention is that there is no separate correct bit in each group of related cache 96. When the copy number is 00000, the buffer manager 72 knows that the input data is no longer correct, so the input data is taken from the cache. Removed in 96. This simplifies the structure of the cache. In addition, another advantage of the cache 96 of the present invention is that it allows fast searches to be performed. Because the buffer manager 72 only needs to check one row, and this row has been determined by the frame indicator leaving the multi-copy queue 90. The input data of the four major lines is checked in parallel to further increase the search speed. Although the cache structure is described as a four-channel memory related to each group, this is just an example to show that the memory related to each group of n channels does not depart from the scope of the present invention.

From the above description, we can know that the present invention can maintain the time sequence of the input data (the new and old of the input data) by placing the physical position of the input data in each row. In other words, the physical position of the input data represents this How old is the input data. To change the old input data can be achieved by rearranging this memory.

In a specific embodiment of the present invention, the latency of frames switched by the switching device 12 can be customized on a port-by-port basis. Referring to Figure 14, the port vector FIFO 70 checks the programmed switch mode of the receiving port (the switching device mode is changeable) to determine when to put the frame indicator and related information into the appropriate transmission The output queue 74 of the port. In the first mode (waiting time quality mode), the port view FIFO 70 does not limit when to put the frame indicator to the output port 74. The second mode (medium-duration mode) port vector FIFO 70 places the frame pointer to the output queue 74, only after 64 bits of the frame pointer are received, the third mode (high-latency mode) port vector The FIFO 70 places the frame indicator in the output queue 74 only after the frame indicator is all received.

Here are some special examples. The time for the port vector FIFO 70 to transmit the frame indicator to the output queue 74 must be changed. 1) Transmit the frame from the 10Mb/s port in the first mode or the second mode to the 100Mb/s port. 2) The frame is forwarded to the management port 30. 3) The frame is forwarded to the expansion bus port. In 1), the rate difference between the 10Mb/s port and the 100Mb/s port forces the transfer mode to be forced to the third high latency mode. In 2), all frames are delivered to the management port using the third mode frame. In 3), so the frame transmitted to the expansion bus port uses the switching mode of the expansion bus port 26. When a multi-duplicate port vector contains one of these special ports, the longest waiting time must be used to switch the mode. For example, if a frame is received by a port in the first or second mode, but its multi-duplication port vector includes the management port 30, the switching mode must use the third mode. In this case, only after all the frame indicators are received, a copy of the frame indicator is placed in the output storage 74.

The switching device mode will be discussed in more detail. The switching device mode applied to the input port can determine the forwarding waiting time (how fast the switching device 12 will forward the frame once it receives the frame), and it can be reduced to every The ability to delay the fragment/error propagation of an output port. Furthermore, the second mode, the medium latency mode, is the default mode for each port. In the register 60, the switching device mode can be planned in units of one port.

In the three switching device mode, the frame received by the internal MAC port FIFO 52 will be transferred to the external memory buffer 140 as much as possible. At about the same time, the rule detector 42 or 58 receives the destination address and source address, the receiving port vector, the frame indicator and some additional information, and then performs appropriate checks. Once the check is completed, the rule checker 42 or 58 returns the frame index and the forwarding port vector to the FIFO 70.

The port vector FIFO 70 places the frame indicator on the writing end 76 of the output queue 74, and provides a port vector to identify the output port. When the port vector FIFO 70 receives the port vector (frame indicator) and puts the frame indicator in the output queue 74 for a period of time, the switch device mode of the receiving port defines the forwarding waiting time of this port. This is a description for the following three modes. Once the frame indicator is delivered to the reading end 78 of the output queue 74, the buffer manager 72 reads the frame indicator and schedules the transmission time. The buffer manager 72 starts to move the frame data from the address pointed to by the frame pointer. Once the FIFO54 of the transmission MAC port returns to the point where it first started (assuming that the media can be used for the transmission of frame data), the transmission of the frame is started.

The first mode is designed to provide a transmission mode with the lowest latency. The transmission and forwarding of the frame is transmitted at a line-rated speed. In the first mode, because the frame has not yet determined the signal The frame is a segment (ie less than 26 bits) or is arranged for transmission before it contains a CRC error, so there is no network error protection (network error protection). In the first mode, the frame reception may not be completed before the frame transmission of the output port. If the reception of the frame ends in an immature transmission cycle (runt) or with an incorrect CRC, the receiving MAC will mark the buffer 142 of the external memory 36 to show that these conditions are currently occurring. The transmission mac guarantees that if it starts to transmit a frame, and this frame will subsequently end in an immature transmission cycle, or there is a wrong CRC, then the MAC will generate a bad CRC. The MAC has not yet started the transmission of the frame, but the buffer 142 has indicated that the frame has ended in an immature transmission period or has an incorrect CRC, and the buffer manager will not forward the frame to the output port.

The second mode provides a low-latency frame forwarding mode, but has some network error protection. After receiving 64 bits or more, the frame will be forwarded. This will allow the exchange of frames that filter out (ie not forward) fragments. However, this mode cannot completely filter out frames with more than 64 bits and CRC errors.

In the second mode, the frame indicators of the frames that reach the 64-bit threshold are arranged in the appropriate output queue 74. Frames that do not reach the 64-bit threshold will be deleted, and their frame indicators will not be placed in the output queue 74. If a frame greater than or equal to 64 bits ends with an incorrect CRC, receive the MAC mark (mark) the buffer 142 of the external memory 36 to indicate that this situation is currently occurring. If the transmission starts with a frame greater than or equal to 64 bits and then ends with an incorrect CRC, the transmitting MAC will end the transmission with a bad CRC. If a transmitting MAC does not start transmitting a frame, but the buffer 142 indicates that the frame (greater than or equal to 64 bits) ends with an incorrect CRC, the buffer manager 72 returns the frame indicator to the recovery queue 98 ( Single copy transfer) or multiple copy queue 96 (multiple copy transfer) without transferring to the output queue 74.

The third mode is the store-and-forward mode (store-and-forward mode) with the highest level of network error protection and high forwarding time among the three modes. The frames are completely received before the switching device 12 will forward them to the output port. The switching device 12 isolates all fragments and all CRC frames before forwarding. In the third mode, once a frame is successfully terminated at the receiving end (greater than or equal to 64 bits and has the correct CRC), the frame The indicator will be successfully arranged in the appropriate output queue 74. Frames ending with a receiving error (incorrect CRC, immature cycle, etc.) will be deleted, and their frame indicators will not be placed in the output queue.

The port vector FIFO 70 makes the decision of putting the port vector into the output queue, and has nothing to do with the mode selected by the receiving port and the amount of data received. Although there are different numbers of thresholds in other embodiments, in this embodiment, there are three thresholds. In this exemplary embodiment, these thresholds are 1) receiving n bits (such as six bits), where n is less than 64, 2) receiving 64 bits and 3) receiving all frames.

The present invention forwards the frame to the output queue 74 according to the threshold. The port vector FIFO 70 rearranges the transmission sequence according to the amount of received data and the planned mode of the port. Although the forwarding decision is made based on the amount of received data, in some implementations of the present invention, the forwarding decision is made based on other factors, such as the type of received data.

When completing the transfer plan of the present invention, the buffer manager 72 maintains a table 160 in the cache 161. This table connects the frame indicator with the receiving port. Each time the port vector FIFO 70 receives a new port direction and frame indicator from the rule checker 42 or 58, it will generate an association to determine whether the input port has completely received a frame signal, if not, determine how many The frame is received. The port vector FIFO 70 does not receive any identification data about the receiving port from the checker 42 or 58. The only identification data about the receiving port received by the port vector FIFO is the frame indicator.

No matter if the frame is still receiving, the address table is returned to the receiving port, or because the frame has been completely received, the address table 160 cannot find the frame indicator, the port vector FIFO 70 will use the frame Index to query the address table 160. Once the frame is completely received, its frame indicator will be moved out of the address table 160. This situation indicates that the third mode (full frame reception) has been encountered. Therefore, the frame indicator immediately falls into the output queue.

If the address table 160 is returned to the receiving port, the port view FIFO 70 puts the frame indicator and related information into the holding area 162, and the receiving port starts to monitor the two signals. These two signals flag one of three events. The first event indicates when n bits are received by the port. At this point in time, if the port is in the first mode, the port vector FIFO 70 starts processing the frame by sending it to the appropriate output queue 74. If it is not in the first mode, the port vector FIFO 70 will wait until it receives a signal indicating that it has encountered the second event. If the port is in the second mode, the port vector FIFO 70 will release the frame indicator from the holding area 162 to the appropriate output queue 74. Finally, if the port is in the third mode, the port vector FIFO 70 will wait until it receives a flag indicating that the frame has been completely received. Each receiving port (refer to number 164 in Figure 14) maintains this flag and provides this information to the port vector FIFO 70. This flag provides information to the port vector FIFO 70 to determine which frame indicator the port is associated with. The port vector FIFO 70 will keep the information of which mode the port is in. In short, when receiving a frame indicator, the port vector FIFO 70 queries the address table 160 of the buffer manager 72 to determine which receiving port it is, to determine the mode of the receiving port, and the receiving port monitors some flags. According to the mode and these flags to release the frame indicator.

Although the present invention has been explained and illustrated in detail, it should be clearly understood that these examples are only used to illustrate the present invention and not to limit the present invention. The spirit and scope of the present invention will be limited by the appended terms of the scope of patent application.

Figure 1 is a block diagram of a packet switching system according to an embodiment of the present invention.

FIG. 2 is a block diagram of a multi-port switching device according to an embodiment of the present invention, and is used in the switching system of FIG. 1.

Figure 3 is a diagrammatic illustration of Figure 2 of the secondary switching system of the multi-port switching device according to the embodiment of the present invention.

Figure 4 is an output queue of the secondary switching system in Figure 3 according to the embodiment of the present invention.

Figure 5 is a detailed structure of the first output queue according to an embodiment of the present invention.

Figure 6 is a detailed structure of the second output queue according to an embodiment of the present invention.

Fig. 7 is a detailed structure of the external memory overload area according to an embodiment of the present invention.

Figure 8 is a block diagram of the link serial data structure operating in the present invention.

Figure 9 schematically illustrates the format of the frame buffer according to an embodiment of the present invention.

FIG. 10 is a detailed diagram of the multiple copies, recovery, and space buffer slots of the switching device sub-system constructed according to the embodiment of the present invention shown in FIG. 4. FIG.

Figure 11 is a block diagram of a free buffer slot structure according to an embodiment of the present invention.

Figure 12 is a block diagram of a multi-copy queue configured according to an embodiment of the present invention.

Figure 13 is a schematic representation of a multi-copy cache according to an embodiment of the present invention.

Figure 14 is a block diagram of a buffer manager arrangement of a switching device system according to an embodiment of the present invention, and a FIFO.