Improving Routing Table Lookup in Software Routers

For the speed-up in the routing table lookup in software routers, we introduce a new data structure called, sTable that achieves space efficiency while causing low processing overhead without hardware parallelism. Using a hash table-like approach, sTable stores only next hop information to handle most packets within the on-chip fast memory while causing some accesses to the off-chip slow memory to handle lookup errors. Routing table lookup experiments using Click show that, causing less processing overhead and a smaller number of lookup errors than Bloom filter, sTable reduces the average table lookup time by 44% (i.e., from 119 ns to 67 ns) compared to Bloom filter.