iptables 匹配 n 条 rule 的时间复杂度是多少?

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1739 天前的主题，其中的信息可能已经有所发展或是发生改变。

简单起见, 假设都在一个 chain 中, 每个 rule 是 /32 地址, ACCEPT 或 DROP

4 条回复 • 2020-02-26 11:36:48 +08:00

zhs227

2020-02-26 11:19:09 +08:00

建议使用 ipset，只知道效率很低，具体有多低不知道。基本上相当于 O(n)?

feng32

2020-02-26 11:32:47 +08:00

@zhs227 我知道 ipset，只是有点好奇 iptables 原始规则是不是真的那么低效

ipwx

2020-02-26 11:35:04 +08:00

iptables 应该是 O(n)，不然管不住它这么复杂的规则。

用上 ipset 应该可以 O(logN)。

ipwx

2020-02-26 11:36:48 +08:00

@feng32 iptables 非常强大，规则之间有先后匹配顺序。现在有两条路，第一是让运维人员用 ipset 优化规则集，第二是算法自动优化。考虑到人工都优化不了的规则集，算法肯定优化不了，所以我觉得这个优化器大概率内核没写。（摊手