IP地址的索引范围搜索算法

本文介绍了IP地址的索引范围搜索算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个具有100亿个CIDR表示形式或两个IP之间的IPv4范围的ACL列表:

Given an ACL list with 10 billion IPv4 ranges in CIDR notiation or between two IPs:

x.x.x.x/y x.x.x.x - y.y.y.y

什么是有效的搜索/索引算法，用于测试给定IP地址是否满足一个或多个ACL范围的条件?

What is an effecient search/indexing algorithm for testing that a given IP address meets the critera of one or more ACL ranges?

让我们假设大多数ACL范围定义跨越了很多C类块.

Lets assume most ACL range definitions span a great number of class C blocks.

通过哈希表索引点很容易，但是尝试一下，因为我可能无法提出一种合理的方法来检测哪些点被大量行"覆盖.

Indexing points via hash tables is easy but try as I might have not been able to come up with a reasonable method for detecting which points are covered by a large list of "lines".

有些想法，例如在某个特定级别上建立索引提示-例如，在C类级别上对覆盖该点的每个ACL进行预计算，但表可能太大..或某种KD树无法动态设置详细程度.

Had some thoughts like indexing hints at a certain level of detail -- say pre-computing at the class C level each ACL that covered that point but the table would be too large.. Or some sort of KD tree to dynamically set levels of detail.

还曾想过，也许有碰撞检测算法可以解决这个问题.

Also had the thought that maybe there are collision detection algorithms out there that can address this.

有没有正确方向的提示或指针?

Any hints or pointers in the right direction?

推荐答案

您可以查看间隔树查找与任何给定间隔或点重叠的所有间隔.

You can look at the Interval tree to find all intervals that overlap with any given interval or point.

对于不重叠的IP范围，您可以使用b树或紧凑型尝试，例如 Judy数组(64 -bits)进行索引和搜索(将start-ip作为键，将end-ip存储为值).

For non-overlapping ip-ranges, you can use a b-tree or compact-tries like Judy arrays (64-bits) for indexing and searching (Store the start-ip as key and the end-ip as value).