基于TCAM的高效率路由更新算法

摘要

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

目录

文摘

英文文摘

论文说明:图表目录

第1章 绪论

1.1 本文的研究背景及意义

1.2 研究内容

1.3 本文主要工作

1.4 本文结构

第2章 路由查找背景知识

2.1 前言

2.2 基于软件的路由查找算法

2.2.1 线性查找

2.2.2 缓存策略

2.2.3 二进制Trie树(binary Trie)

2.2.4 路径压缩Trie树

2.3 FCAM技术简介

2.3.1 TCAM的基本结构

2.3.2 TCAM的优缺点

2.4 TCAM路由查找

2.5 小结

第3章 基于分块TCAM的路由更新算法

3.1 前言

3.2 分块TCAM技术

3.3 FCAM路由前缀更新

3.4 快速低功耗的分块TCAM更新算法

3.4.1 初始空闲TCAM资源大小

3.4.2 分块溢出解决算法

3.4.3 空闲资源的管理

3.5 仿真实验结果分析

3.5.1 有效性

3.5.2 可行性

3.6 小结

第4章 基于TCAM的路由前缀压缩算法

4.1 前言

4.2 路由前缀在TCAM存储的形式

4.3 基于掩码位拓展的路由压缩技术

4.3.1 冗余裁剪

4.3.2 掩码拓展路由压缩算法

4.4 基于TCAM的路由前缀压缩算法

4.4.1 前缀压缩

4.4.2 前缀更新策略

4.5 实验结果分析

4.6 小结

结论

参考文献

致谢

附录A 攻读硕士期间发表的论文及成果