找出 IP 属于哪个子网的最有效方法是什么

Question

假设我有数十亿条记录，每条记录都包含 IPv4 字段。我想知道：

如果每条记录都属于我关注的子网之一
如果满足条件1，属于哪个子网

每个相关子网都定义为几个掩码（61.232.85.0/25、61.232.86.0/27）和一些离散的 IP，我总共有 1000 个子网定义要处理。

那么，什么是最有效的算法 and/or 数据结构来处理这项工作？

另外，我找到了 Trie 一个可能的解决方案，有什么建议吗？

Answer 1

这真的很简单。将 IP 转换为无符号 32 整数。然后 if (IP1 & Mask) = (IP2 & Mask)，其中 mask 是两个掩码中较小的一个。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string IP1str = "61.232.85.0/25";
            cIP IP1 = new cIP(IP1str);
            string IP2str = "61.232.86.0/27";
            cIP IP2 = new cIP(IP2str);
            string IP3str = "61.232.85.0/22";
            cIP IP3 = new cIP(IP3str);
            string IP4str = "61.232.86.0/22";
            cIP IP4 = new cIP(IP4str);

            bool sameNet = (new cIP()).InSubnet(IP3str, IP4str);
        }
    }
    public class cIP
    {
        public UInt32 IP { get; set; }
        public string IPHex { get; set; }
        public UInt32 mask { get; set; }
        public string maskHex = "";

        public cIP(){}

        public cIP(string IPstr)
        {
            //remove mask
            string maskStr = IPstr.Substring(IPstr.LastIndexOf("/") + 1);
            mask = (UInt32)(Math.Pow(2, 32) - Math.Pow(2, 32 - UInt32.Parse(maskStr)));
            maskHex = mask.ToString("x8");
            IPstr = IPstr.Substring(0,IPstr.LastIndexOf("/"));
            string[] IParray = IPstr.Split(new char[] { '.' });
            for (int i = 3; i >= 0; i--)
            {
                IP = IP + (UInt32.Parse(IParray[3 - i]) << (i * 8));
            }
            IPHex = IP.ToString("x8");
        }
        public bool InSubnet(string IP1str, string IP2str)
        {
            bool results = false;
            cIP IP1 = new cIP(IP1str);
            cIP IP2 = new cIP(IP2str);

            if (IP1.mask <= IP2.mask)
            {
                results = (IP1.IP & IP1.mask) == (IP2.IP & IP1.mask);
            }
            else
            {
                results = (IP1.IP & IP2.mask) == (IP2.IP & IP2.mask);
            }

            return results;
        }
        public bool InSubnet(cIP IP1, cIP IP2)
        {
            bool results = false;
            if (IP1.mask <= IP2.mask)
            {
                results = (IP1.IP & IP1.mask) == (IP2.IP & IP1.mask);
            }
            else
            {
                results = (IP1.IP & IP2.mask) == (IP2.IP & IP2.mask);
            }

            return results;
        }

    }

}

Answer 2

您可以将子网表示为 int 值，将它们全部放入一个数组中，对其进行排序，然后对其进行二进制搜索。尽管从那以后多头可能会更好，但您不必在二进制搜索中处理负数。最多需要 10 个步骤才能找到一个子网。尝试可能需要例如/25 子网的 25 个步骤。还要记住，1000 个多头只有 8 kb。这很容易适合 CPU 缓存，使其非常快。当然，您还可以使用第二个数组来存储每个掩码所属的子网。

这是 Scala 中的一个例子 findMaskIdx 使用二进制搜索查找给定掩码（子网定义的 ip 部分）的索引。如果它找不到任何东西，它 returns 比它搜索的那个大的第一个掩码的索引。 findIpIdx 取一个 IP 地址和 returns 它所属的子网定义的索引，如果没有找到则为 -1。

findIpIdx 可以是运行每秒大约 100 到 2 亿次。所以看起来还是挺快的。这种方法只有一个问题。如果两个不同大小的子网重叠，代码可能会找到错误的子网。但我希望这不会太难解决。

def ipStringToInt(s: String): Int = {
  var ip = 0
  for(num <- s.split("\.")) {
    ip = ip * 256 + num.toInt
  }
  ip
}

def parseSubnet(s: String): (Long, Int) = {
  val mask_length = s.split("/")
  val length = if(mask_length.size > 1) mask_length(1).toInt else 32
  var mask = ipStringToInt(mask_length(0)) & 0xFFFFFFFFL
  (mask, length)
}

val subnetGroups = Vector(
  Vector("61.232.85.0/25", "61.232.86.0/27"),
  Vector("123.234.12.24/16", "1.2.3.4"),
  Vector("61.232.87.5", "253.2.0.0/16")
)

val subnetData = (for {
  (group, idx) <- subnetGroups.zipWithIndex
  maskString <- group
  (mask, length) = parseSubnet(maskString)
} yield (mask, length, idx)).sortBy(_._1)

val masks: Array[Long] = subnetData.map(_._1).toArray
val maskLengths: Array[Int] = subnetData.map(_._2).toArray
val groupNr: Array[Int] = subnetData.map(_._3).toArray

def findMaskIdx(ip: Long): Int = {
  var low = 0
  var high = masks.size
  while(high > low) {
    val mid = (low + high)/2
    if(masks(mid) > ip) high = mid
    else if(masks(mid) < ip) low = mid + 1
    else return mid
  }
  low
}

def findIpIdx(ip: Int): Int = {
  val ipLong = ip & 0xFFFFFFFFL
  var idx = findMaskIdx(ipLong)
  if(idx < masks.size && masks(idx) == ipLong) return idx
  idx -= 1
  if(idx < 0) return -1
  val m = (0xFFFFFFFF00000000L >>> maskLengths(idx)) & 0xFFFFFFFFL
  if((m & masks(idx)) == (m & ipLong)) return idx
  return -1
}


println("subnet data (mask, bit length of mask, index of subnet group):")
println(subnetData.map {
  case (mask, length, idx) => (mask.toHexString, length, idx)
})
println()

println("masks = " + masks.toVector.map(_.toHexString))
println()

def testIP(ipString: String) {
  println("ipString = " + ipString)
  val ip = ipStringToInt(ipString)
  val dataIdx = findIpIdx(ip)
  println("dataIdx = " + dataIdx)
  if(dataIdx >= 0) {
    val data = subnetData(dataIdx)
    println("data = " + (subnetData(dataIdx) match {
      case (mask, length, idx) => (mask.toHexString, length, idx)
    }))
  }
  println()
}

testIP("61.232.86.12")
testIP("253.2.100.253")
testIP("253.3.0.0")

找出 IP 属于哪个子网的最有效方法是什么

What is the most efficient way to find out which subnet an IP belongs to

algorithm

scala

ip-address

trie

data-structures