Linux system hardware routing forwarding principle

In Linux systems, route forwarding refers to a protocol in which signals are transferred from one site to another. Because some signals are forwarded and some signals are not forwarded, they constitute a complex network world. This article will introduce the forwarding principle of Linux system hardware routing.

forwarding hardware schematics:

Please note that there is no optimization, you can try some tips to further optimization, can be directly used to map the standard TCAM it. In this picture, I show in detail how the “longest prefix” logic is done, and in the case of the TCAM routing forwarding table, it is often drawn as a black box called “Priority Logic Controller”. However, this logic circuit is relatively simple, I believe that you can design it yourself if you think a little.

In fact, in the above figure, there is a container called “Anti-Mask”, which is arranged bit by bit next to the bit line comparison key behind the decoder. This is a standard. The TCAM practice is gone.

About Content Addressing and Addressing

We all know that the cache is expensive so it can't be too big, and the content can be very large because it is cheaper.

But can you explain it from a technical perspective? In fact, expensive and cheap difference is due to technical reasons, we look at the circuit memory array of memory:

This is a very typical matrix, is also very simple. But for CAM circuit, it is not so simple, as shown in the following figure:

For the TCAM, care need to add a logical, even more complex, not only is the circuit complexity, power consumption also increases It should be noted that in the CAM/TCAM matching process, all parts of the circuit work simultaneously.

About hardware HASH

Many people say that there is a hardware HASH in the CPU cache, such as taking the nth to m bits of the address, in fact, it is a shift, modulo operation! This can only be seen by programmers. The simplest HASH algorithms that programmers know are more complicated than this. In fact, hardware engineers are dismissive of the programmer's hustle and bustle, because their focus is how to make the circuit work at the same time with the lowest power consumption and smaller circuit scale. CAM/TCAM uses hardware HASH, very simple hardware HASH, but the circuit can work at the same time. This is a big problem with software hashes. Software hashes are designed to make hash distributions more uniform and average performance better. Thus the average variance of the length of the conflicting list is the smallest. The software hash is designed to resolve conflicts, and the hardware HASH does not need to do this, because when the software seems to have to serially traverse the conflicting list, the hardware can be done simultaneously.

CPUs for sequential execution

Computers are designed to be a sequential execution model, and instructions are executed one after the other. This is because it completely simulates the behavior of people in the real world. This means that all the algorithmic steps that run on the computer are implemented serially in time, and a good algorithm is designed to minimize time. However, the design of the hardware circuit does not follow the way that real-world people do things, at least not too much. A person can't do a lot of things at the same time. The execution process of the hardware circuit is more like a flooding process. Because of the potential energy, the flood goes to (at the same time!) all the places where it can go, and instantly swallows everything.

The above is the forwarding principle of Linux system hardware routing. Of course, routing forwarding is only part of the Linux network link, and of course the most irreplaceable part.