Shulou(Shulou.com)06/01 Report--

What kind of computing do you think looks and must be super fast in general-purpose computers with modern operating systems? there is no doubt that the answer is memory access.

What kind of computing do you think looks and theoretically super slow in general-purpose computers with modern operating systems? there is no doubt that the answer is routing addressing.

It's really boring to have an early holiday!

Why do you think memory addressing is fast? Why do you think it has to be fast?

Because now the operating system is based on virtual memory address addressing, there needs to be a mapping between virtual address and physical address, which actually slows down memory access, but we have the gift of CPU, address cache, or TLB!

The Great God said that the core of modern programming technology is the technology of addressing. Yes, indeed. The processing performance of CPU core has long been no longer a bottleneck, because CPU always has to communicate with peripherals, all kinds of bus laying and core, long-distance fatigue, electromagnetic impact, its efficiency actually slows down the overall processing progress. The function of all levels of CPU cache at this time is to avoid remote addressing as much as possible, including L1/L2/L3 Cache,TLB, etc., where TLB caches address translation results, and it tries to improve efficiency for the last time after the data / instruction cache L1/L2/L3 misses. If TLB also misses, it needs to perform the slowest process: perform a page table lookup and map to a physical address; the address bus transmits a physical address The data bus acquires data.

Let's broaden our horizons a bit.

Today, the entire IP network is a huge computer, and the IP address is that you can think of it as a memory address. Try to compare the memory address of a 32-bit system with the IPv4 address, and you might think of something. In today's Internet, CDN has been playing the role of CPU Lx Cache, avoiding remote addressing as much as possible, but the performance optimization of IP routing is rarely unified. For this reason, there is no unified solution because in the network field, on the contrary to the computer field, the transmission capacity is constantly increasing, and its development speed once far exceeds the development of CPU. Network transmission technology, like the outbreak of the general, currently 10Gbit Ethernet has no pressure, these cables can be buried in the soil, winding on the crossbeam. Compared with the board bus whose tall and neat arrangement on the multi-layer interchange circuit board can not reach the 10Gbit/s, it is really a hero regardless of the provenance. At this point, if you use CPU for pure software routing lookup, it will slow down the wire-speed capability of midbox, and CPU, which is high-end on the same board, becomes a bottleneck to the high-speed network.

Bypass hardware forwarding of CPU

In the past ten years, the development speed of network technology is much faster than that of CPU capability, which is mainly limited by the integration technology of on-chip Cache, bus technology, concurrent technology and lock technology, unlike 10 Gigabit / 100000 Ethernet technology can be regarded as an independent technology, general-purpose computers need to consider the cooperation of various resources, CPU technology, memory bus, electromagnetic compatibility. Therefore, the professional router basically put aside the CPU, but directly do the forwarding chip. A card is plugged into a general-purpose computer and transformed into a professional router. The data path is done entirely on the card, bypassing CPU completely, which is like having a small computer built into the computer. General-purpose computers only provide management and control functions, such as Cisco Express forwarding.

If you stay together for a long time, you must be divided, and if you divide for a long time, you must be in harmony.

With the improvement of the integration ability of on-chip technology and on-board bus technology, all levels of general CPU Cache have been greatly improved in terms of size, efficiency and use, and the efficiency of accessing memory has also been improved. At this point, CPU once again has the opportunity to unify all kinds of route forwarding hardware cards. Of course, it does not mean that all hardware forwarding technologies will be replaced by CPU forwarding technology. if you want to pursue higher speed, professional hardware forwarding is better than CPU forwarding, but at least, high-speed CPU forwarding technology can eliminate and integrate most of the hardware forwarding technologies in the market.

Analogical Virtual address Mapping Technology-an Ancient algorithm

Those who are proficient in Linux network technology should know that the two existing routing lookup algorithms are HASH lookup and TRIE tree algorithm, both of which include complex and scattered data structures, and they are well designed for pure software imagination; in addition, those who are proficient in BSD protocol stack should also know that BSD's Radix tree algorithm also performs well in software routing lookup. But when you think about it, almost all of these algorithms are born out of decades of booming hardware routing and forwarding technology, so they are more like a spontaneous sprout of hidden forces than the result of the general trend. This kind of algorithm is essentially a kind of general routing lookup algorithm, they do not make use of the hardware structure of their hardware, such as CPU Cache, and they do not know what platform they are running on, which are blocked by the interface of OS. All the optimizations for the architecture are in the form of precompiled macros or patches.

Analogical Virtual address Mapping Technology-DxR algorithm

Considering the destination IPv4 address as a virtual memory address in the address space and the next hop arriving at the destination address as the physical page address corresponding to the virtual memory address, is it possible to construct a routing table like a page table? Imagine how often virtual addresses are translated into physical pages and how efficient it is! Unfortunately, there is no MMU mechanism within CPU to handle IPv4 addresses, and of course, as a general-purpose CPU, it should not have such a mechanism. But you can always learn something by analogy.

The efficiency of routing table lookup does not lie in the time complexity of the algorithm itself (I believe that few people use the traversal method, and the algorithms that can be selected as the system search algorithm are all algorithms with acceptable time complexity), but lies in the opening pin in the implementation. if the Cache of CPU can be used, then the algorithm with the same time complexity and the algorithm that does not use Cache have an order of magnitude of efficiency. If you want to take advantage of CPU's Cache, then the logarithmic data structure has strict requirements, must be compact, and can not take up too much space. Organizing the routing table into a page directory / page table class structure is a good idea, compact enough to load Cache. Another point of optimization, IPv4 address and virtual memory address can be compared, but the routing table corresponding to the page directory part of the bits is not a fixed IPv4 address to do the index, but K > = 16, where to index? The index is not a page table, but a range table, which can also be indexed according to 32merk, but since many routing items are aggregated, it can be a binary tree organization and is still a compact array in organization. This is the core of the DxR algorithm. It can be seen that there is nothing new, but the data structure of the existing algorithm has been reorganized, and the core idea can be seen in the MMU implementation of CPU.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.