Method and apparatus for providing fault tolerance to memory

Network device and related method capable of providing memory fault tolerance

The present invention relates to the memory fault tolerance of network devices, in particular to a network device and related methods that can provide memory fault tolerance

When constructing a computer network structure composed of multiple computers, network devices such as switches and routers are very important components. The data sent by the computer on the road is sent to the destination address of the data through the network port of the network device. In order to achieve this function, a look-up table (look-up table) that records the relative relationship between the host and the network port must be stored in the memory of the network device. Such a look-up table is usually called "media storage". Take control address table" (media access control address table, hereinafter referred to as MAC address table).

The aforementioned MAC address table records the source MAC identification code (SID) of the input packet received by the network device. If you want to store an input packet in the MAC memory, a rule called "hashing" is usually used to base the input packet's MAC identification code (MAC ID) maps the input packet to a specific field in the lookup table. Whenever a packet is sent to the network device, the network device will find the target MAC identification code (DID) contained in it, and perform a "hashing" task based on the DID to map this input packet to the search A specific field in the table. At this time, the network device will check whether the MAC identification code stored in this field has ever appeared and has been stored in the lookup table. This step is usually called a "search" step. If the MAC ID stored in this field is invalid, expired, or valid but different from the searched DID, the search result can be called "missed" (missed); However, if the MAC identification code stored in this field is valid and the same as the DID of the input packet, the search result can be called a "hit". The network device will determine how to send the packet based on the search result. If the search result is "Search Missed" and the input packet is a qualified packet, the network device will "broadcast" this packet to All network ports (except the network port that received this packet of course); if the search result is a "search hit", the input packet will be sent to the relevant network port. This step can be called It is "forward". After sending, the network device will try to associate the SID with the input port (inbound The corresponding relationship between port) is "learned", and this relationship is stored in the lookup table.

The use of the lookup table in the MAC memory to determine how to transmit the input packet can prevent unnecessary "broadcasting" actions, thus reducing the amount of data transmitted. Since MAC memory (which stores the relationship between the host/network port) is of considerable importance in network devices, currently common network devices only use defect free memory As MAC memory.

However, the manufacturing process of the memory cannot be flawless. In other words, during the manufacturing process, the yield of the memory without physical defects cannot reach 100%. In every batch of memory produced, it is inevitable that a part of the memory is defective and needs to be discarded as a defective product. This situation causes higher manufacturing costs.

For a more detailed description of the "hash" operation, please refer to the article "A comparison of hashing" published by Jain in the "IEEE Transactions on Communications" journal October 1992, pages 1570-1573. schemes for address lookup in computer networks".

Therefore, an object of the present invention is to provide a network device and related method that can provide memory fault tolerance.

According to the embodiments presented below, the present invention discloses a network device that can provide memory fault tolerance, which includes: a first memory, including a plurality of fields, used to store a one-bit address The relevant data of the packet of information, wherein the relevant data of the packet can be stored in a field of the first memory according to the address information; and a second memory for storing in the first memory The status of at least one field, where the status is used to indicate whether the corresponding field has defects.

According to the embodiments presented below, the present invention further discloses a method for providing fault tolerance of a network device memory. The method includes: performing a built-in self-test on a first memory, wherein the The first memory includes a plurality of fields; a second memory is marked to indicate the state of at least one of the fields, wherein the state indicates the defect state of the corresponding field; according to one The one-bit address information of the packet is used to find a field in the first memory; and the second memory is checked to determine whether the field corresponding to the address information of the packet is defective.

Please refer to Figure 1. Figure 1 is a simple schematic diagram of a network device according to an embodiment of the present invention. In this embodiment, the network device 10 includes: a MAC address memory 20; a status record memory 30; a replacement memory 40; and a processor 50 coupled to the memory 20, 30, With 40. The MAC address memory 20 is used to store the relationship between the host/network port (that is, the corresponding relationship between the SID and the input port), and its function is widely known by those who are familiar with this technology; state record memory 30 is used to indicate the state of the MAC address memory 20; as for the replacement memory 40, it is the second memory used to store the relationship between the host/network port besides the MAC address memory 20; and the processor 50 is used to manipulate memories 20, 30, and 40.

The network device 10 can be a network switch, a network router, or other similar network devices (however, in this embodiment, the network switch will be used as an example of the network device 10 for subsequent description); MAC The address memory can be static random access memory (SRAM); the state recording memory 30 can be a set of registers; in the embodiment of FIG. 1, each register corresponds to the MAC address memory A field in the volume 20; the replacement memory 40 may be a content addressable memory (CAM). However, the above are all feasible examples in implementation, and they are not limitations of the present invention.

Please note that the replacement memory 40 in this embodiment is a part that you can choose to add. Through the following description, you can more clearly understand the impact of using (or not using) the replacement memory 40 on the present invention. .

Please refer to Figure 2. FIG. 2 is a flowchart of an embodiment of the network device 10 processing packets according to the method of the present invention. The steps in Figure 2 are detailed below:

Step 100: When starting the network switch 10, execute a "Built In Self-Test" (BIST) to check whether there are any defects in the SRAM 20.

Step 110: Mark the status record memory 30. If a defect is found in the MAC address memory 20, corresponding to each defect found, the network switch 10 will mark a corresponding register in the state recording memory 30. In this way, the network switch 10 can know whether a specific field in the MAC address memory 20 is a usable field by checking the marked state of the register in the state recording memory 30. Please note that the above marking actions are not limited to one-to-one applications.

Step 120: Determine the position of the field in the MAC address memory 20. Whenever the network switch 10 wants to process an input packet, it performs a "search" step on the input packet, and determines the position of the field in the MAC address memory 20 according to the MAC identification code of the input packet. In this embodiment, the position of the field in the MAC address memory 20 is determined by the target identification code or source identification code of the input packet (depending on the network switch 10 performing packet transmission or packet information learning Work to decide). The determined field in the MAC address memory 20 can be used to indicate the network port from which the packet should be sent, or the field position to which the packet information should be learned.

Step 130: Check the status record memory 30. Since the field location determined in the MAC address memory 20 may be a defective memory location, it cannot indicate the correct network port to which the packet should be sent, nor can it be used to learn packet information. Therefore, the status of the status record memory 30 must be checked at this time. In this embodiment, the network switch 10 checks whether the corresponding register in the state recording memory 30 is in the marked state.

For more information about the "Built-in Self Test", please refer to the article "A programmable BIST core" published by Huang et al. in the January-March 1999 issue of the IEEE Design and Test Magazine of the Institute of Electrical and Electronics Engineers. for embedded DRAM".

Figures 3 to 6 are the continuation of the flow chart of Figure 2. After performing step 130 in FIG. 2, the subsequent steps must be determined according to the work performed by the network switch 10. Please refer to Figure 3 first. Figure 3 is a flow chart of the network device 10 transmitting a packet when the replacement memory 40 is not used. The steps in Figure 3 will be described in detail below:

Step 130: Check the status record memory 30. In this embodiment, the network switch 10 checks whether the corresponding register in the state recording memory 30 is in the marked state, and if the marking state of the corresponding register in the state recording memory 30 shows At this time, the determined field position in the MAC address memory 20 is a defective memory position, that is, step 140 is entered; otherwise, step 150 is entered.

Step 140: Broadcast the packet. Since the determined field location in the MAC address memory 20 is a defective memory location (or the comparison step did not find a match), the network switch 10 at this time has no way to determine the use To send out the correct network port of this packet. Therefore, the network switch 10 can broadcast the packet to all network ports (except the network port that received the packet).

Step 150: Compare the packet with the MAC address memory 20. Even if the marked status of the corresponding register in the status record memory 30 shows that the field position in the MAC address memory 20 determined at this time is not a defective memory position, the network switch 10 still has to compare this The MAC identification code of the packet and the content in the field determined in the MAC address memory 20. If the two are consistent with each other, then go to step 160; otherwise, go to step 140.

Step 160: Transmit the packet. Since the MAC identification code of this packet is consistent with the content in the field determined in the MAC address memory 20, the network switch 10 can use the packet in the field determined in the MAC address memory 20. The content of is sent to the corresponding network port.

Step 170: End. At this point, the processing of the input packet has been completed, and the network switch 10 can return to step 120 in FIG. 2 to start processing the next input packet.

Next, please refer to Fig. 4. Fig. 4 is a flow chart of the network device 10 transmitting a packet in the case of using the replacement memory 40. The steps in Fig. 4 will be described in detail below:

Step 130: Check the status record memory 30. In this embodiment, the network switch 10 checks whether the corresponding register in the state recording memory 30 is in the marked state. If the state of the corresponding register in the state recording memory 30 is marked, it displays If the field position in the MAC address memory 20 determined at this time is a defective memory position, then go to step 240; otherwise, go to step 250.

Step 240: Search for alternative memory 40. Since the field position in the MAC address memory 20 is a defective memory position, the network switch 10 can search for the replacement memory 40 to find out whether there is information about the network port that can transmit the packet. The method here is that the network switch 10 searches the replacement memory 40 according to the packet to see if there is a match with the packet. If the search is successful, go to step 260; otherwise, go to step 270.

Step 250: Compare the packet with the MAC address memory 20. Even if the marked status of the corresponding register in the status record memory 30 shows that the field position in the MAC address memory 20 determined at this time is not a defective memory position, the network switch 10 still has to compare this The MAC identification code of the packet and the content in the field determined in the MAC address memory 20. If the two are consistent with each other, then go to step 260; otherwise, go to step 240.

Step 260: Transmit the packet. At this time, the network switch 10 can send the packet to the corresponding field according to the content of the field determined in the MAC address memory 20 (or the content of the field found in the replacement memory 40) Network port.

Step 270: Broadcast the packet. Since the determined field position in the MAC address memory 20 is a defective memory position (or the search in step 240 fails), the network switch 10 at this time has no way to determine which one to send out. The correct network port for the packet. Therefore, the network switch 10 can broadcast the packet to all network ports (except the network port that received the packet).

Step 280: End. At this point, the processing of the input packet has been completed, and the network switch 10 can return to step 120 in FIG. 2 to start processing the next input packet.

The difference between Figure 4 and Figure 3 is that when it is found that the field position in the determined MAC address memory 20 is a defective memory position (or compare the packet with the determined MAC address memory 20 When the field content is found to be inconsistent), in Figure 3, the packet will be transmitted directly by broadcasting. However, in Figure 4, there is an additional step of searching for the replacement memory 40. Please note that the replacement memory 40 is used to provide additional (or replacement) storage space for the MAC address memory 20. If the field in the MAC address memory 20 is a defective field, the network switch 10 can store the content of the input packet in the replacement memory 40 (it must be stored in the MAC address memory 20 with Defective field). As mentioned above, the replacement memory 40 can be "content addressable memory", so as long as the content of the input packet must be stored in the defective field in the MAC address memory 20, the network switch 10 can be stored in the content addressable memory 40 instead.

Please refer to FIG. 5. FIG. 5 is a flowchart of the packet information learning process performed by the network device 10 without using the replacement memory 40. The steps in FIG. 5 will be described in detail below:

Step 130: Check the status record memory 30. In this embodiment, the network switch 10 checks whether the corresponding register in the state recording memory 30 is in the marked state, and if the marking state of the corresponding register in the state recording memory 30 shows At this time, the determined field position in the MAC address memory 20 is a defective memory position, that is, step 340 is entered; otherwise, step 350 is entered.

Step 340: Execute the learning process in the MAC address memory 20. Since the field determined in the MAC address memory 20 is not a defective field, the network switch 10 can store information therein. Therefore, the network switch 10 can execute the learning process through the MAC address memory 20. This learning procedure includes: checking the content of the determined field in the MAC address memory 20, and learning the information about this packet. For example, the network switch 10 can check the ID stored in this field, and learn the relative relationship between the SID of the packet and the network port (unless the ID stored in this field is valid but is related to the packet SID is different).

Step 350: End. At this point, the processing of the input packet has been completed, and the network switch 10 can return to step 120 in FIG. 2 to start processing the next input packet.

Please refer to FIG. 6. FIG. 6 is a flowchart of the packet information learning process performed by the network device 10 when the replacement memory 40 is used. The steps in FIG. 6 will be described in detail below:

Step 130: Check the status record memory 30. In this embodiment, the network switch 10 checks whether the corresponding register in the state recording memory 30 is in the marked state, and if the marking state of the corresponding register in the state recording memory 30 shows At this time, the determined field position in the MAC address memory 20 is not a defective memory position, that is, step 440 is entered; otherwise, step 450 is entered.

Step 440: Check the found fields. Since the field found in the MAC address memory 20 is not a defective field, the network switch 10 can store information in it (that is, perform a learning process). However, before executing the learning procedure, the network switch 10 first checks the content stored in this field. If the stored ID is valid but different from the SID of the packet, it proceeds to step 450; otherwise, it proceeds to step 445 .

Step 445: Execute the learning process in the MAC address memory 20. At this time, the field found in the MAC address memory 20 is valid, so the network switch 10 can learn the relative relationship between the SID of the packet and the network port (unless the ID stored in this field is Valid but different from the SID of the packet).

Step 450: Search for alternative memory 40. At this time, the network switch 10 will try to learn the information related to the packet into the replacement memory 40. The approach here is. The network switch 10 searches for the replacement memory 40 according to the packet, and if the found field is available, it proceeds to step 460; otherwise, it proceeds to step 470.

Step 460: Learn the information into the substitute memory 40. At this time, the network switch 10 can learn the information related to the packet into the replacement memory 40. The information learned in this step is the same as step 440.

Step 470: End. At this point, the processing of the input packet has been completed, and the network switch 10 can return to step 120 in FIG. 2 to start processing the next input packet.

The difference between Fig. 6 and Fig. 5 is that when it is found that the field found in the MAC address memory 20 is a defective field (or the ID stored in this field is valid but is not compatible with the packet When the SID is different), the method in FIG. 5 is to directly end the processing of the packet, and the method in FIG. 6 is to let the network switch 10 learn the information of the packet into the replacement memory 40.

In other words, Figure 2 to Figure 6 illustrate the processing procedure for a packet. More specifically, Figures 2 and 3 are the packet transfer procedures when only the MAC address memory 20 and the status recording memory 30 are used; Figures 2 and 4 are the packet transfer when the replacement memory 40 is used more. Procedure; Figure 2 and Figure 5 are the packet information learning procedures when only the MAC address memory 20 and the status recording memory 30 are used; Figure 2 and Figure 6 are the packet information learning procedures when the replacement memory 40 is used more program.

Obviously, if the method proposed by the present invention is used, the manufacturer can use the defective memory in the network device. And the function that the defective memory can provide to the network device will be the same as the case of using the non-defective memory.

The foregoing descriptions are only preferred embodiments of the present invention, and all equivalent changes and modifications made in accordance with the scope of the patent application of the present invention shall fall within the scope of the patent of the present invention.

<p>10Network Device</p><p>20MAC address memory</p><p>30Status record memory</p><p>40Replacement memory</p><p>50Processor</p>

A brief description of the schema

Figure 1 is a schematic diagram of an embodiment of the network device of the present invention.

FIG. 2 is a flowchart of an embodiment of using a network device to process packets according to the method of the present invention.

FIG. 3 is a flowchart of an embodiment of using a network device to transmit packets according to the method of the present invention when the replacement memory is not used.

FIG. 4 is a flowchart of an embodiment of using a network device to transmit packets according to the method of the present invention when a substitute memory is used.

FIG. 5 is a flowchart of an embodiment of a packet information learning process using a network device according to the method of the present invention when the replacement memory is not used.

FIG. 6 is a flowchart of an embodiment of a packet information learning process using a network device according to the method of the present invention when a substitute memory is used.