路由表的结构与算法分析--trie插入

简介:

在linux的trie树中插入一条路由是很复杂的,远比查找要复杂的多,因为每插入一条路由就要看看是否要动态调整trie树,不是还好,如果要动态调 整,那活儿就大了,正是因为这一点,trie路由表往往在大型的机器上用到,那些机器不吝啬动态调整trie树的时候的空间损失,如果是性能不那么靠铺的 机器,还是老老实实用哈希路由表吧,只要不是疯狂插入很多路由表导致很多哈希碰撞,性能是很棒的,我在pc上装过trie,一旦路由条目大了,内存疯狂耗 尽,要知道,路由表用的可是内核内存阿,不被换出的。bsd一向巨猛,unix嘛,linux一向不管那么多,代码凌乱而有序,要懂得欣赏,仔细品味才有收获。 
bsd以前的路由表是基于二叉radix树的,而现在是固定多分枝trie树,具体就是32位分为4段,然后类似于页目录页表那样多叉树搜索,如果是二叉 树的,那么只要访问路由表就要锁住全树,这么说好像多分枝树就不用锁了一样,错了,同样要锁,不同之处在于二叉树如果只锁一个节点那么对下面同样影响很大,想象一下如果锁住了根的左孩子,那么满树的情况下一半的节点都要受影响,但是多分枝就不同了,比如n分枝,如果锁住根的第m孩子(m如果一位一位的比较,那么就是二叉radix树,,因为一位非0即1,所以树就有2个孩子,如果32位32位比较,那么就是2的32次方叉树,也就是根节 点有2的32次方个孩子,所有的ip地址每个为一个孩子,世界上没有哪个路由表是这么实现的,还是二叉树的好一些,但是考虑到前面说的缺点,bsd改进了 radix树,使之成为固定分支的trie树,实质和二叉radix树是一样的。linux来了,世界不吭气了,你不是说叉数多了不好,少了又有这样那样 的缺点,bsd来了个折中,不多不少,2的8次方,在数字上来个折中,linux则更进一步,在动态效果上来了个折中,也就是说,linux的trie完 全动态,游走于二叉和2的32次方叉之间,看你还怎么说,即使你说m叉正好,那么盯着linux几分钟,更新一下路由表,它确实到了m叉,如果你说n叉很 糟糕,但linux这时确实是n叉树,那么继续盯几分钟,插入几条路由或删除几条,哈哈,不是n叉了吧,这一切是怎么实现的呢?这正是我这篇文章要说的动态trie树的插入。来吧,看代码:

static



 本文转自 dog250 51CTO博客,原文链接:http://blog.51cto.com/dog250/1274167

相关文章
|
6天前
|
机器学习/深度学习 自然语言处理 算法
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
|
12天前
|
机器学习/深度学习 算法 数据可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
|
13天前
|
算法 搜索推荐 数据挖掘
MATLAB模糊C均值聚类FCM改进的推荐系统协同过滤算法分析MovieLens电影数据集
MATLAB模糊C均值聚类FCM改进的推荐系统协同过滤算法分析MovieLens电影数据集
|
13天前
|
算法 数据可视化 数据挖掘
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
|
13天前
|
数据采集 存储 算法
数据分享|Weka数据挖掘Apriori关联规则算法分析用户网购数据
数据分享|Weka数据挖掘Apriori关联规则算法分析用户网购数据
|
14天前
|
网络协议 算法 数据库
【专栏】OSPF是广泛应用的链路状态路由协议,通过分层网络结构和SPF算法实现高效路由。强烈建议收藏!
【4月更文挑战第28天】OSPF是广泛应用的链路状态路由协议,通过分层网络结构和SPF算法实现高效路由。其关键特性包括区域划分、链路状态数据库、邻居关系和路由更新。工作过程涉及邻居发现、信息交换、数据库构建、路由计算及收敛。理解OSPF对于网络管理和规划具有重要意义。
|
16天前
|
机器学习/深度学习 数据采集 算法
共享单车需求量数据用CART决策树、随机森林以及XGBOOST算法登记分类及影响因素分析
共享单车需求量数据用CART决策树、随机森林以及XGBOOST算法登记分类及影响因素分析
|
17天前
|
移动开发 算法 数据可视化
数据分享|Spss Modeler关联规则Apriori模型、Carma算法分析超市顾客购买商品数据挖掘实例
数据分享|Spss Modeler关联规则Apriori模型、Carma算法分析超市顾客购买商品数据挖掘实例
|
2天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
3天前
|
存储 算法 数据可视化
基于harris角点和RANSAC算法的图像拼接matlab仿真
本文介绍了使用MATLAB2022a进行图像拼接的流程,涉及Harris角点检测和RANSAC算法。Harris角点检测寻找图像中局部曲率变化显著的点,RANSAC则用于排除噪声和异常点,找到最佳匹配。核心程序包括自定义的Harris角点计算函数,RANSAC参数设置,以及匹配点的可视化和仿射变换矩阵计算,最终生成全景图像。