7

我有像这样的 CIDR 格式的文件，192.168.1.0/24它被转换成这两列结构

3232236030 3232235777

每个字符串 IP 地址转换都使用以下代码进行：

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);

Inet4Address a = (Inet4Address) InetAddress.getByName(utils.getInfo().getHighAddress());
long high = bytesToLong(a.getAddress());
Inet4Address b = (Inet4Address) InetAddress.getByName(utils.getInfo().getLowAddress());
long low = bytesToLong(b.getAddress());

private static long bytesToLong(byte[] address) {
   long ipnum = 0;
   for (int i = 0; i < 4; ++i) {
       long y = address[i];
       if (y < 0) {
           y += 256;
       }
       ipnum += y << ((3 - i) * 8);
   }
   return ipnum;
}

考虑有超过 500 万个(low high : 3232236030 3232235777).
还会有相交，因此 IP 可以来自多个范围。只是第一个就OK了。
数据是只读的。
找到ipToBefiltered所属范围的最快方法是什么？该结构将完全在内存中，因此没有数据库查找。

更新：

我找到了这个Peerblock项目（它有超过一百万的下载量，所以我认为它必须有一些快速算法）： http://code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp。 C

有谁知道该项目使用什么技术来创建范围列表而不是搜索它们？

4

5 回答 5

7

归根结底，我只需要知道 IP 是否存在于任何 5M 范围内。

我会考虑一个n叉树，其中 n=256，并从点分地址而不是转换后的整数工作。

顶层是一个包含 256 个对象的数组。条目表示“null否”，没有包含地址的范围，因此假设您的示例192.168.1.0/24array[192] 将包含一个对象，但 array[100] 可能为空，因为没有为任何 100.xxx/n 定义范围

存储的对象包含一个（引用）另一个数组[256] 和一个范围说明符，两者中只有一个会被设置，因此192.0.0.0/8最终会得到一个范围说明符，指示该范围内的所有地址都将被过滤。这将允许192.255.0.0/10地址的前 10 位是重要的地方1100 0000 11xx xxxx——否则您需要检查第二级数组中的下一个八位字节。

最初将重叠范围（如果有的话）合并成更大的范围......例如3 .. 10，and 7 .. 16become 3 .. 16...允许这样做，因为您不需要将给定的IP与定义它的范围相关联。

这应该需要不超过 8 次比较。每个八位字节最初直接用作索引，然后是 null 的比较，终端节点的比较（是范围还是指向下一个树级别的指针）

(256 ^ 4)如果每个IP 地址都在过滤范围内，理论上最坏情况的内存消耗为 4 GB ，但当然这会合并为一个范围，因此实际上只有 1 个范围对象。更现实的最坏情况可能更像是(256 ^ 3)16.7 MB。现实世界的使用可能会使每个级别的大多数 array[256] 节点为空。

这本质上类似于霍夫曼/前缀编码。一旦找到答案（范围），最短的不同前缀就可以终止，因此您通常会有< 4比较的平均值。

于 2011-11-29T22:02:52.503 回答
1

我将使用一个排序的 int 数组（基地址）和另一个相同大小的数组（结束地址）。这将使用 5M * 8 = 40 MB。第一个 IP 是基地址，第二个 IP 是范围内的最后一个地址。您将需要删除交叉点。

要查找地址是否被过滤到二进制搜索 O(log N) 并且如果不是完全匹配，请检查它是否小于（或等于）上限。

于 2011-11-29T19:42:23.763 回答
1

我在Vuze（又名 azureus）项目中发现了这个二进制斩波算法：

public IpRange isInRange(long address_long) {
    checkRebuild();

    if (mergedRanges.length == 0) {
        return (null);
    }

    // assisted binary chop

    int bottom = 0;
    int top = mergedRanges.length - 1;
    int current = -1;

    while (top >= 0 && bottom < mergedRanges.length && bottom <= top) {

        current = (bottom + top) / 2;

        IpRange e = mergedRanges[current];

        long this_start = e.getStartIpLong();
        long this_end = e.getMergedEndLong();

        if (address_long == this_start) {
            break;
        } else if (address_long > this_start) {

            if (address_long <= this_end) {
                break;
            }

            // lies to the right of this entry

            bottom = current + 1;

        } else if (address_long == this_end) {
            break;
        } else {
            // < this_end

            if (address_long >= this_start) {
                break;
            }
            top = current - 1;
        }
    }

    if (top >= 0 && bottom < mergedRanges.length && bottom <= top) {

        IpRange e = mergedRanges[current];

        if (address_long <= e.getEndIpLong()) {
            return (e);
        }

        IpRange[] merged = e.getMergedEntries();

        if (merged == null) {
            //inconsistent merged details - no entries
            return (null);
        }

        for (IpRange me : merged) {
            if (me.getStartIpLong() <= address_long && me.getEndIpLong() >= address_long) {
                return (me);
            }
        }
    }
    return (null);
}

似乎表现还不错。如果您知道更快的事情，请告诉我。

于 2011-11-30T19:25:41.027 回答
1

如果您只有一个 CIDR 地址（或它们的列表）并且您想检查某个 ipAddress 是否在该 CIDR（或 CIDR 的列表）的范围内，只需定义一组 SubnetUtils 对象。

除非您要过滤非常大的 N 个地址，否则这都是字符串比较，并且执行速度非常快。您不需要基于高/低位以及所有复杂的 Jazz 构建二叉树。

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);
//...
//for each subnet, create a SubnetUtils object
Set<SubnetUtils> subnets = getAllSubnets();
//...

使用 Guava 谓词过滤不在您的子网集范围内的 ipAddress：

   Set<String> ipAddresses = getIpAddressesToFilter();
   Set<String> ipAddressesInRange = 
       Sets.filter(ipAddresses, filterIpsBySubnet(subnets))


   Predicate<String> filterIpsBySubnet(final Set<SubnetUtils> subnets){
       return new Predicate<String>() {
            @Override
            public boolean apply(String ipAddress) {
                for (SubnetUtils subnet : subnets) {
                    if (subnet.getInfo().isInRange(ipAddress)) {
                        return true;
                    }
                }
                return false;
            }
        };
   }

现在，如果 IP 在任何子网中，您就有了一个很好的简单过滤器，并且您不必构建必须进行单元测试的数据结构。如果这还不够性能，则进行优化。不要过早优化:)

于 2013-03-08T18:44:30.837 回答
0

这是答案的开头，我有更多空闲时间会回来

设置：

  1. 按起始编号对范围进行排序。
  2. 由于这些是 IP 地址，我假设没有一个范围重叠。如果有重叠，您可能应该运行列表合并范围并修剪不必要的范围（例如，如果您的范围为 1 - 10，则可以修剪范围 5 - 7）。
    1. 要合并或修剪，请执行此操作（假设范围 a 紧接在范围 b 之前）：
      1. 如果 b.end < a.end 则范围 b 是范围 a 的子集，您可以删除范围 b。
      2. 如果 b.start < b.end and b.end > a.end 那么你可以合并范围 a 和 b。设置 a.end = b.end 然后删除范围 b。
于 2011-11-29T20:03:30.270 回答