知识卡片

LPM两级表用空间换时间

专业/工作 · 1108.b

内容

路由查找要找最长前缀匹配的表项——子网掩码越长、匹配越精确的表项优先命中。DPDK LPM把查找拆成两级表:一张覆盖全部24位前缀的巨表tbl24(2^24条目),只要前缀长度不超过24位,一次访存直接命中,这是大概率场景;当规则前缀超过24位(更精确的小范围规则)才需要跳到第二级8位子表tbl8做第二次访存。这是典型的”用空间换时间”设计——牺牲tbl24占用的可观内存,把绝大多数查找压到一次内存访问,只让少数场景多付出一次访存代价。

参考来源

《深入浅出DPDK》第5章《报文转发》