支持路由压缩的TCAM高速更新方法

摘要

支持路由压缩的TCAM高速更新方法属于互联网IP地址高速查找技术领域，其 特征在于它是一种把都基于树结构的路由压缩以及建立在三态内容可寻址存储器(TCAM)芯片内的空间划分为N个子空间的前缀链约束基础上的前缀更新这两个步骤前后合在一起的TCAM高速更新方法，其中，判断前缀是否需更新的原则是该结点是否冗余，冗余则不更新，反之，则更新；在判断N个子空间的划分是否影响TCAM更新性能时，使用了子空间划分评价函数。它具有支持高速的路由更新，支持有效的路由表压缩，对IPv6协议具有很好的扩展性的优点。

主权项

1.支持路由压缩的TCAM高速更新方法含有路由压缩的步骤，其特征在于：它是一种把都基于树结构的路由压缩和建立在把TCAM，即三态内容可寻址存储器芯片内的空间划分为N个子空间的前缀链约束基础之上的前缀更新这两个步骤前后合在一起的TCAM高速更新方法，它依次含有以下步骤：(1)在树结构中，找到代表更新路由的结点fn，更新路由是指增加路由或删除路由；(2)根据fn的前缀是否冗余来判断是否需要更新至TCAM中：若此路由前缀和其父结点具有不同的下一跳地址和出端口，也就是说，它们的转发结果是不同的，则此路由前缀在路由表中不是冗余的，因此需要更新，执行步骤(3)；若此路由前缀和其父结点具有相同的下一跳地址和出端口，也就是说，它们的转发结果是一样的，则此路由前缀在路由表中是冗余的，因此无需更新，执行步骤(4)；(3)把fn的前缀更新至TCAM；(3.1)利用评价函数Tmin(W，N)把TCAM空间划分为N子空间，其中：$T_{\min }(W,N)=\underset{i=\mathrm{NtoW}}{\mathrm{Min}}(T_{\min }(i-1,N-1)+F(i,W))$ W表示IP地址长度，也是最大路由前缀长度；N表示划分子空间的个数；Tmin(W，N)表示[0，W]长度区间的前缀，在N子空间划分下，移动操作和写入操作总和的最小值；Tmin(i-1，N-1)表示[0，i-1]长度区间的前缀，在N-1子空间划分下，移动操作和写入操作总和的最小值；F(i，W)表示在区间[i，W]内的前缀，在一个子空间内更新所需操作的数目；(3.2)根据前缀的长度找到TCAM中对应的前缀子空间Lk＝[lk-1+1，lk]；(3.3)在子空间Lk内，按照前缀链约束，对树中链上的路由前缀进行移动操作；(3.4)把fn的前缀更新至TCAM中；(4)判断fn的子结点是否需要更新至TCAM中：若需要更新，则执行步骤(5)；若无需更新，则执行步骤(6)；(5)把fn子结点的前缀更新至TCAM；(6)更新结点fn的数据成员。