TCAM路由表项管理算法优化研究

TCAM(Ternary Content-Addressable Memory)能够很好的完成最长前缀匹配,实现快速路由查找和分组转发,但是其对路由表项的有序性要求使得表项管理比较复杂。在讨论已有TCAM表项管理算法的基础上,通过分析前缀表项的统计分布特性.对路由表的空间分配进行了优化,同时引入新的基于前缀块指针管理策略,提出了一种改进的表项管理方法,提高了路由表更新效率。

一种改进的TCAM路由表项管理算法及实现

在高速路由器上,为突破软件路由查表的速率瓶颈,广泛应用基于三态内容寻址存储器(Ternary Content-Addressable Memory,TCAM)的硬件路由查表的方法。虽然TCAM能快速完成表项的最长前缀匹配决策,可以让分组转发达到线速,但其表项的有序性要求又使得表项管理变得比较复杂。在讨论现有TCAM表项管理算法的基础上,通过对前缀块概率分布、动态平衡的特征进行分析,针对前缀块预留空间进行优化,并配合基于缓存的双链表管理策略,提出并实现了一种改进的表项管理算法,提高了表项更新速率。