设为首页 加入收藏

TOP

Linux协议栈查找算法优化随想(二)
2014-11-23 17:31:54 来源: 作者: 【 】 浏览:147
Tags:Linux 协议 查找 算法 优化 随想
路由查找算法的思想一样,采用多层hash查找而不是单一hash加冲突链表遍历。


我以conntrack查找为例,我可以将conntrack简化为一个{IP1,IP2}对,第一个元素为键,第二个为值,这样就可以将conntrack的查找做成BSD系统的路由查找的样子,其中IP2可以被看成下一跳。或者别的......


我并不是说多级的hash算法要比单独的hash算法更高效,而是说多级的hash表可以在多个CPU核心分别计算,多级hash表可以将每一个hash计算视为一个维度,每一个CPU核心计算一个维度的hash值,定位该维度的坐标,反观单一hash表就不能利用多CPU核心优势,你必须先计算好hash值才能定位hash桶从而遍历冲突链表。在多CPU核心时代,传统的基于时间复杂度计算分析性能的方式可能已经过时。


首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇Linux环境编程:获取网卡的实时网.. 下一篇TCP/IP详解2 学习笔记2---ifne..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: