IPv4储存的数据结构和算法-前缀搜索的高效实现

Question

我正在寻找用于IPV4的数据结构，它应该存储什么？前缀：（基础+掩码）->例如85.23.0.0/16

基础= 85.23.0.0 -> 32位无符号

掩码= 16也就是255.255.0.0 ->char 8位无符号

所以最小主机是85.23.0.0，最大主机是85.23.255.255（我知道在正常情况下应该是.0.1和.255.254，但我想简化它）

我需要的主要是在存储的前缀中搜索IP的速度。例如，我提供一个无符号整数（32位），并且我需要告诉它是否存在。

我正在使用C++编写，因此可以使用STL。

现在它存储在STL set（对base + mask进行排序），我一一搜索，所以这有点O（n）（除非它可能是BST树，因此遍历可能比O（n）更慢）

总之：我不需要有效存储IPV4的方式，我需要一种有效的搜索它的方法。数据结构不会存储端口或家族类型等，它将存储PREFIX（基础+掩码）。

我正在寻找数据结构+一些搜索算法。

- user3613919

---

如果前缀的总数不是非常大，那么一个简单的二叉树，表示最高位到最低位的位，就足够了。 - Sam Varshavchik

我必须确保即使对于大量的前缀也能保持效率。 - user3613919

你能将它们存储为64位无符号整数吗？ - Logman

Answer 1

您可以查看2012年的DXR论文“Towards a Billion Routing Lookups per Second in Software”：

http://info.iet.unipi.it/~luigi/papers/20120601-dxr.pdf

本文介绍DXR，一种基于将大型路由表转换为紧凑的查找结构的查找方案，这些结构可以轻松适配现代CPU的缓存层次结构。

我们的转换将一个包含417,000个IPv4前缀和213个不同下一跳的实际BGP快照精简成一个只占用782 Kbytes的结构，每个前缀不到2个字节。实验表明，相应的查找算法随着CPU核心数量线性扩展：在普通8核CPU上运行，对于均匀随机的IPv4键，它产生了平均840百万次查找每秒的吞吐量。

虽然您可能会问“不需要高效存储IPV4”，但紧凑的存储方式将有助于查找性能，因为内存非常慢，而CPU缓存速度更快（计算机存储层次结构的内存墙变体）。更紧凑的表示具有较少的L3缓存未命中，可能更快。

DXR具有非常好的速度（在3.6 GHz AMD FX-8150和DDR3 1866MHz内存上）：

使用随机搜索键（最坏情况），D18R在单个核上的速度为117百万次查找每秒（Mlps），当所有8个核心都处于活动状态时，速度为840 Mlps。根据配置和查询模式，DXR在1个核心上可实现50至250百万次查找每秒。117 mlps在3.6 GHz上大约是每次查找30个CPU周期;对于DDR3 1866MHz的内存随机访问延迟来说,读取第一个字节从内存到内存控制器需要32-36个CPU周期,必须打开DRAM行(通常可能不会打开-打开行也很慢)。需要额外的时间来读取完整的缓存行和一些时间将此缓存行转发到L3、L2、L1、寄存器。完全的内存延迟可能接近100纳秒 （360个CPU周期）。

- osgx

---

DXR网站，更新和资源在这里：http://www.nxlab.fer.hr/dxr/。 2012年发表了题为“ DXR：软件中每秒十亿个路由查找”的论文，发表在ACM计算机通信评论，卷42（5），第29-36页。 这些引用它的文件中可能会有一些有趣的论文：https://scholar.google.com/scholar？gws_rd=ssl&um=1&ie=UTF-8&lr&cites=17851808599136542137 - osgx

Answer 2

为什么不使用std:unordered_map呢？它的时间复杂度应该在O(1)和O(n)之间，或者您可以使用std:map，如果您只关心搜索阶段的性能，则固定性能为O(log n)。除非您的数据集很大，否则您可能会发现没有显着的差异。

- Robbykk

---

你也可以使用 https://github.com/sparsehash/sparsehash，它可以针对速度或空间进行优化。 - Robbykk

Answer 3

这种方法仅适用于1-31的掩码范围。为了快速进行完整范围（0-32）的二进制搜索，您可能应该在64位整数内存储掩码和地址（例如像这样std :: vector <unsigned long long> networkAddrs（bases.size（））; ... networkAddrs [i] =（bases [i] << 32）+ masks [i];）

使用网络地址的简单属性，您可以将掩码存储在未使用的网址位中，可以简单地将掩码和基础存储在单个32位整数内，对它们进行排序并进行二进制搜索。类似于这样的东西：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> 
#include <cmath>

unsigned int insertMask(unsigned int ip, unsigned int mask)
{
    unsigned int longMask = (~0) << (32-mask);
    unsigned int netAdd = (ip & longMask) + (1 << (31-mask));
    return netAdd;
}

bool isInNetwork(std::vector<unsigned int>& nAs, unsigned int ip, unsigned int mask)
{
  unsigned int netAdd = insertMask(ip, mask);
  auto pos = std::lower_bound(nAs.begin(), nAs.end(), netAdd); 
  return pos != nAs.end() && *pos == netAdd;
}

int main()
{

  std::vector<unsigned int> bases {
       (192u<<24)+(168<<16)+(0<<8)+(0)
      ,190u<<24
      ,191u<<24
      ,192u<<24
      ,193u<<24
      ,194u<<24
      ,195u<<24
      ,196u<<24
  };

  std::vector<unsigned int> masks {24,24,24,24,24,16,8,4};

  std::vector<unsigned int> networkAddrs( bases.size() );

  for(int i=0; i<bases.size(); i++)
  {
      networkAddrs[i] = insertMask(bases[i], masks[i]);
  }

  std::sort (networkAddrs.begin(), networkAddrs.end());

  unsigned int ip_addr = (192u<<24)+(168<<16)+(0<<8)+(17);
  unsigned int mask = 24;

  if(isInNetwork(networkAddrs, ip_addr, mask))
    std::cout << "TRUE";
  else
    std::cout << "FALSE";

  std::cout << '\n';

}

编辑：

我将方法更改为代码掩码，如下所示：

对于IP地址XXX.XXX.YYY.YYY/16
0b XXXXXXXX XXXXXXXX 10000000 00000000

对于IP地址（XXX.XXX.0xXY.YYY/12）
0b XXXXXXXX XXXXXXXX XXXX1000 00000000

- Logman

---

你能解释一下为什么在 unsigned int netAdd = (ip & longMask) + mask; 中要加上 mask 吗？ - user3613919

这很简单哈 ;) 看看这个例子：IP地址为192.168.1.17/24，十六进制表示为"c0 a8 01 11"，掩码为"ff ff ff 00"。这使得网络地址变为"c0 a8 01 00"，现在你可以将压缩掩码"24"（十六进制为0x18或二进制为0b11000）存储在网络地址的最后5位。需要注意的是，你现在无法将掩码与基址分开，但问题是如何检查IP是否属于已存储的网络。 - Logman

也许我没有理解你的想法，但是：1）如果掩码是32怎么办？2）你将掩码添加到netAdd中，然后在向量中搜索它？ - user3613919

经过思考，可以重新获取掩码，但这并不是一件简单的事情。 - Logman

如果你只有IP地址，你可以做两件事。如果这是互联网地址，请使用标准的A、B、C、D IP范围掩码；如果不是，则需要对所有可能的掩码（32-n）进行检查。对于第二个选项，你只能预测IP地址是否在你存储的地址内，并且不能百分之百确定IP地址是否属于某个网络，但你可以百分之百确定它不属于你存储的网络。 - Logman

Answer 4

你可以使用CritBit树。它们非常简单，但也有许多开源变体可用。这是一种可搜索的树，它使用前缀共享，因此具有相同前缀的所有值都存储在同一个子树中。根据实现方式，前缀共享还可以用于减少空间要求，因为您只需为每个条目存储一次前缀，而不是每个条目都存储一次。

- TilmannZ