我正在尝试创建一种基于源和目标IP地址以及目标和源端口的算法来过滤TCP/IP数据包。基本上，我有一组规则，这些规则指定了一系列IP地址，例如192.168.0.0/24，对于目的地和源IP地址以及目的地和源端口的同等地址（[1:65535]）。
简而言之，给定一个数据包，我想找到哪些规则与IP地址和端口有关。目前，到目前为止，我唯一的想法是从源或目标IP地址构建一个TRIE，该地址会迅速过滤，但仍需要对其余参数进行线性搜索，并导致O(n)的复杂性。n规则。有没有更好的方法可以降低时间复杂性？
假设您将IP编码为范围内的整数[0，2^32]，则可以定义源和目标范围为四维矩形
min = [src_ip_min, src_prt_min, dst_ip_min, dst_prt_min]
max = [src_ip_max, src_prt_max, dst_ip_max, dst_prt_max]
您可以使用像R-Tree这样的空间索引结构来索引多维矩形，以有效地回答空间查询。在您的情况下，您将需要一个范围搜索（范围= 0）才能获取适用于某个查询的所有矩形（=规则）。
4维度仍然可以很好地索引，因此根据您的范围分布，您可以期望查询时间更接近O(log n)