通过 IPv6 地址进行二进制搜索？

Question

一年前，我不得不在 IPv4 地址范围内实施二进制搜索，以用作优化的 HTTP 请求过滤器，以应对可能的 DOS 攻击。

今天我需要重新实现它以使用 IPv6，但是由于在如何转换和比较地址方面有很多差异，这似乎是一个很大的挑战。我试图为此找到一个现有的解决方案，但运气不佳。充其量，我可以找到简单的 IPv6 实用程序来解析地址并进行非常基本的操作，而无需提供太多优化搜索。例如，这个库：whitequark/ipaddr.js

我的旧解决方案中的关键方法是依赖地址的整数表示，使用以下转换：

function intFromIPv4(ip){
    var octets = ip.split(".");
     return octets[0] * 16777216 + octets[1] * 65536 + octets[2] * 256 + octets[3] * 1;
}

然后我可以 merge/align IP 范围，这样就可以进行简单的二进制搜索。

这是我为此写的class：

function IPv4Checker() {

    this.ipList = [];

    // takes array of [{f,l}] integers and returns its merged-range version as [{first, last}];
    // works only if:
    // a) the array is ordered by 'f' in ascending order.
    // b) 'f' is always defined, while 'l' is either undefined or not less than 'f'.
    this.mergeRanges = function (data) {
        var ips = [];
        if (data.length > 0) {
            var start = data[0].f;
            var end = data[0].l || start;
            for (var i = 1; i < data.length; i++) {
                if (data[i].f > end + 1) {
                    var d = {first: start};
                    if (end > start) {
                        d.last = end;
                    }
                    ips.push(d);
                    start = data[i].f;
                }
                var v = data[i].l || data[i].f;
                end = v > end ? v : end;
            }
            var d = {first: start};
            if (end > start) {
                d.last = end;
            }
            ips.push(d);
        }
        return ips;
    };

    // Calculates IP address against the current list,
    // using binary / logarithmic search algorithm.
    // It relies on the list of IP-s that is ordered by
    // 'first' in ascending order, and then with all the
    // range overlaps merged.
    this.isValid = function (ip) {
        if (ip === '127.0.0.1') {
            return true; // no checks for the local IP;
        }
        var addr = intFromIPv4(ip);
        var low = 0;
        var high = this.ipList.length - 1;
        var mid;
        while (low <= high) {
            mid = Math.round((low + high) / 2);
            var a = this.ipList[mid];
            if (addr > a.first) {
                if (a.last && addr <= a.last) {
                    return true;
                }
                low = mid + 1;
            } else {
                if (addr < a.first) {
                    high = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    };
}

创建支持范围的优化 IPv6 过滤器以实现类似的快速搜索结果的正确方法应该是什么？

归根结底，我只需要一个 IPv6 过滤器，它可以快速处理 2-3 个 IPv6 范围或 2000-3000 个 IPv6 范围。那是因为我需要在每个 HTTP 请求上使用它，所以使用非二进制搜索并不是一个真正的选择。

如果有人能指出我可能错过的一个很好的现有解决方案，那也很棒。

更新

虽然我接受了答案，但真正的帮助是这里的答案：

Answer 1

由于您可以将任何 IPv6 地址表示为 128 位数字，因此您的问题将简化为对 128 位数字执行二进制搜索。

现在 JS 没有原生处理 128 位数字的能力。所以你可以使用 BigInteger JS 库；例如，快速 google 搜索 big-integer。

但是，这对于您的应用程序来说可能有点矫枉过正。您可以简单地将数字表示为四个 32 位数字的元组。对于二分查找算法，你只需要实现一个函数来比较两个用这种格式写的数字。这可以通过简单的词典比较来完成。

通过 IPv6 地址进行二进制搜索？

Binary search through IPv6 addresses?

javascript

ipv6

node.js