我正在搜索 IPV4 的数据结构。它应该存储什么？前缀:(base + mask) --> 例如 85.23.0.0/16
base = 85.23.0.0 -> 32 位无符号
mask = 16 AKA 255.255.0.0 -> char 8 bit unsigned
所以最小主机是 85.23.0.0，最大主机是 85.23.255.255(我知道在正常情况下它应该是 .0.1 和 .255.254，但我想简化它)
我主要需要的是在存储的前缀中搜索 IP 的速度。例如，我给出 unsigned int (32bit)，我需要判断它是否存在。
我正在用 C++ 编写，所以我可以使用 STL
现在它存储在 STL 集合(pair base + mask)中，我正在一个一个地搜索，所以它有点像 O(n)(排除它可能是 BST 树，所以遍历它可能会更慢比 O(n))
总结一下:我不需要有效的方式来存储 IPV4，我需要一种有效的方式来在某些数据结构中搜索它。并且数据结构不会存储端口或家族类型等。它会存储前缀(基数+掩码)。
我正在搜索数据结构 + 一些搜索算法。
最佳答案
您可以查看 2012 年的 DXR 论文“在软件中实现每秒十亿次路由查找”:
http://info.iet.unipi.it/~luigi/papers/20120601-dxr.pdf
This paper presents DXR, a lookup scheme based on transforming large routing tables into compact lookup structures which easily fit into cache hierarchies of modern CPUs.
Our transform distills a real-world BGP snapshot with 417,000 IPv4 prefixes and 213 distinct next hops into a structure consuming only 782 Kbytes, less than 2 bytes per prefix. Experiments show that the corresponding lookup algorithm scales linearly with the number of CPU cores: running on a commodity 8-core CPU it yields average throughput of 840 million lookups per second for uniformly random IPv4 keys.
当您问“不需要有效的方式来存储 IPV4”时，压缩存储将有助于查找性能，因为内存非常慢，而 CPU 缓存更快(计算机 memory wall 的变体 memory hierarchy) .更紧凑的表示从 L3 缓存到内存的丢失更少，并且可能更快。
DXR 具有非常好的速度(在 3.6 GHz AMD FX-8150 和 DDR3 1866MHz 内存上):
With random search keys (a worst-case situation) D18R goes from 117 million lookups per second (Mlps) on a single core, to 840 Mlps with all 8 cores active. ... Depending on the configuration and query pattern, DXR achieves between 50 and 250 million lookups per second on 1 core
3.6 GHz 上的 117 mlps 是每次查找大约 30 个 cpu 滴答； DDR3 1866MHz 的内存随机访问延迟是 .. 超过 9-10 ns或者 32-36 个 cpu 周期只是为了在 DRAM 行打开时从内存到内存 Controller 获取第一个字节(通常它可能不是 - 打开行也很慢)。需要额外的时间来读出完整的缓存行，并且需要更多的时间将此缓存行转发到 L3、L2、L1 寄存器。全内存延迟可能是 close to 100 ns (360 个 CPU 周期)
关于c++ - ipv4存储的数据结构+算法——高效的前缀搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38033135/