论文部分内容阅读
三重内容可寻址存储器(TCAM)技术是近年来出现的一种硬件查找技术,它可以实现高速路由查找,满足Internet的发展需求。但是TCAM的高功耗一直限制着它的发展。分块TCAM和路由压缩是两种解决TCAM高功耗的策略,但是它们都有更新速度慢和更新能耗高的弊端。因此,本文结合因特网报文数急速增长和路由规则迅速扩大的现状,着重研究了基于TCAM的低功耗路由更新和路由查找等问题,主要工作如下：(1)基于动态更新存储空问策略,提出了一种TCAM分块溢出解决算法。分块TCAM是指把TCAM存储空问划分为若干个小块,每次路由查找只到其中一个分块进行匹配查询,以降低查找能耗。由于路由更新具有随机性和突发性的特点,更新操作有可能集中发生在某些分块从而造成分块溢出,迫使重划分块。这会极大地影响路由查找速度。本文通过动态调整溢出分块的TCAM存储空间,提出了一种分块溢出解决算法,可以很好地避免因分块溢出而造成的重划分块。(2)基于前缀按序排列的特征,提出了一种分块TCAM空闲资源分配算法。存储在TCAM的前缀也是按照长度降序排列的,以满足最长前缀查询。因此,路由更新带来的插入和删除操作,会造成大量的前缀移动。在分块TCAM策略中,每个分块都有相应的空闲存储空间。本文依据前缀按序排列的特征,优化了各分块空闲存储空间的分配,可以极大地减少更新时不相关前缀的位置移动,从而提高更新速度,降低更新能耗。(3)针对现有规则集冗余度较大的特点,提出了一种路由规则压缩算法。一般路由器的接口比较少,而路由规则数则成千上万,因此路由表具有很大的压缩空间。本文深入分析路由规则的冗余形式,提出了一种规则集压缩算法,在不改变路由语义的情况下,可以较好地压缩路由规则,降低系统能耗,提高路由查找速度。同时,为了满足路由表的动态更新,本文为压缩路由从前缀插入和前缀删除两方面分别提出了更新策略。