一种基于TCAM的PLO_OPT算法的改进

Improvement of PLO_OPT algorithm based on TCAM

在最大前缀长度为L的TCAM(Ternary Content Addressable Memory)中,采用PLO_OPT算法更新路由表项仍然有很大的时间消耗,其时间复杂度为O(L/2)。为了进一步提高路由更新速度,根据路由前缀数量分布图,本文提出了一种PLO_OPT路由更新算法的改进方案,每更新一次表项只需进行一次操作即可,可以使时间复杂度达到O(1),且更有效地利用了存储空间。

PLO_ OPT routing table updating algorithm promotes efficiency to update routing table in TCAM, but the time complexity still is O（L/2） （L is the longest prefix）. Therefore, according to the map of routing prefix distribution, this paper presents a perfect strategy of PLO_ OPT routing table updating algorithm for up- dating the routing table based on TCAM. The time complexity of this new strategy is up to O（1）. TCAM needs only one operation for updating the routing table elements each time. And the memory space of routing table is more effective.