基于FPGA的快速路由查找算法研究及实现的中期报告.docx

基于FPGA的快速路由查找算法研究及实现的中期报告
一、研究背景和意义
随着互联网的不断发展，网络规模不断扩大，网络流量也越来越大。如何快速、准确地进行路由查找成为了网络性能优化的关键。而FPGA具有高度的可编程性和并行计算能力，是进行高速路由查找的理想平台。因此，基于FPGA的快速路由查找算法研究具有重要的理论和实际意义。
二、研究内容和方法
本文主要研究基于FPGA的快速路由查找算法。其中，路由查找算法采用Trie树和哈希表相结合的方式实现。具体流程如下：
1.将输入的IP地址转化成二进制数列，并按照子网掩码对其进行划分，得到相应的子网前缀。
2.将子网前缀信息插入到Trie树中，Trie树节点存储子网前缀和对应的端口信息。
3.将Trie树转化为哈希表，加快查找速度。哈希表的key值为子网前缀，value值为对应的端口信息。
4.对于输入的IP地址，从哈希表中查找其对应的端口信息，输出结果。
本文所提出的算法将重点放在如何快速查找哈希表中的数据，以及如何将Trie树优化为哈希表。在实现过程中，采用VivadoHLS进行高层次综合，加快设计调试的速度。
三、预期结果
预计通过本文的研究，能够实现基于FPGA的快速路由查找算法，并取得如下成果：
1.实现高效的Trie树转换为哈希表的算法。
2.实现基于哈希表的快速路由查找算法，并测试其查找速度和准确性。
3.分析不同输入规模下算法的性能和资源占用情况，给出算法的优化方法。
四、进度安排
1.完成文献综述和算法设计，2021年6月底。
2.完成基于VivadoHLS的算法实现，2021年8月底。
3.对算法进行测试和优化，2021年10月底。
4.完成论文写作和答辩，2022年1月底。