一种硬件哈希表压缩方法及其性能研究

Study of a hardware Hash list compression method and its performance analysis

在高速、大容量的基于流的报文分类应用中,采用硬件哈希表具有成本低、扩展性好等优点。但由于需要在硬件哈希表中保存流标识,而流标识的长度依不同应用可能长达几十字节,一方面需要较大的存储空间,另一方面也严重影响了哈希查表的性能。提出了一种硬件哈希表压缩方法,可以有效压缩保存在哈希表中流标识的长度,减小所需存储器容量,提高查表性能,同时实现复杂度低,具有较高的实用价值。

In high speed and large volume flow of packet classification, hardware Hash table has the advantage of lower cost and better performance. In these applications, the flow ID should be stored in the hardware hash table. While in some applications, the flow ID can be very long, e.g. 300 bits, and it requires a much larger memory to hold these flow ID. At the same time, the Hash table look-up performance is degraded remarkably. In this paper, we proposed a hardware Hash list compression method. It can effectively reduce the flow ID length and Hash table memory size needed and improves the table look-up performance. The implementation of this method is very simple and it has much merit in practical applications.