比尔盖*_*尔盖子 3 algorithm ip-address subnet
想象有一个防火墙,系统管理员阻止了许多子网,也许是特定国家的所有子网.
例如:
192.168.2.0 / 255.255.255.0
223.201.0.0 / 255.255.0.0
223.202.0.0 / 255.254.0.0
223.208.0.0 / 255.252.0.0
....
要确定IP地址是否已被阻止,防火墙可能会使用以下算法.
func blocked(ip)
foreach subnet in blocked_subnets
if in_subnet(subnet, ip)
return true
return false
但是,算法运行需要太多时间,时间复杂度为O(n).如果路由表包含太多条目,则网络几乎不可用.
有没有更有效的方法将IP地址与巨大的路由条目相匹配？它是基于某种树/图(特里？)我想.我已经阅读了有关最长前缀匹配和Trie的内容,但没有得到重点.
Jim*_*hel 13
你真正需要的只是一个四级的特里.每个非叶节点包含最多256个子节点的数组.每个节点还包含子网掩码.所以,举个例子:
192.168.2.0 / 255.255.255.0
223.201.0.0 / 255.255.0.0
223.202.0.0 / 255.254.0.0
223.208.0.0 / 255.252.0.0
你的树看起来就像下面那样.每个节点的两个数字是IP段,后跟子网掩码.
root
/ \
192,255 223,255
| -------------------------
168,255 | | |
| 201,255 202,255 208,255
2,255
当您获得IP地址时,将其分成若干段.您在根级别搜索第一个段.对于速度,您可能希望在根级别使用数组,以便可以直接查找.
假设IP地址的第一段是223.您将从中获取节点root[223],现在您正在处理这一个子树.您可能不希望在其他级别使用完整数组,除非您的数据非常密集.后续关卡的某种词典可能就是你想要的.如果下一个段是201,则201在字典中查找223节点,现在可能的候选列表只有64K项(即所有IP地址为223,201.xx).你可以用其他两个级别做同样的事情.结果是您只需四次查找即可解析IP地址:一个数组查找和三个字典查找.
这种结构也很容易维护.插入新地址或范围最多需要四次查找和添加.与删除相同.更新可以就地完成,而无需重建整个树.您只需要确保在更新时不要尝试阅读,而不是尝试进行并发更新.但是任何数量的读者都可以同时访问这个东西.
使用哈希映射或 trie 会让您很难处理 CIDR IP 范围（即掩码不一定是基于 8 的，如 192.168.1.0/28）
考虑到所有这些 IP 范围都不重叠，执行此操作的有效方法是二分搜索：
将范围转换A.B.C.D/X为表示起始 IP 地址的 32 位整数，以及此范围内有多少个 IP 的整数。例如，192.168.1.0/24转换为3232235776, 256.
将这些范围添加到列表或数组中，并按起始 IP 地址编号排序。
要将传入的 IP 地址与列表中的任何范围相匹配，就是执行二分搜索。
ami*_*mit -2
回想一下，IP 地址基本上是一个 32 位数字。
您可以将每个子网标准化为其规范形式，并将所有规范形式存储在哈希表中。
在运行时，对给定的地址进行规范化（很容易做到），并检查哈希表是否包含此条目 - 如果包含，则阻止。否则-允许。
例如，假设您要阻止子网5.*.*.*，这实际上是具有前导位的网络00000101。因此，将地址5.0.0.0或添加00000101 - 00000000 - 00000000 - 00000000到您的哈希表中。
一旦特定地址到达 - 例如5.1.2.3，将其规范化回5.0.0.0，并检查它是否在表中。
查询时间是O(1)使用哈希表的平均时间。