Information Technology Reference
In-Depth Information
Fig. 6.
Comprehensive performance on rrc12 and rrc14
all based on the DIR-24-8 scheme. However, as update frequency is increasing,
TSTT's superiority becomes more and more significant. Actually, in GALE, the
throughput decreases by 53
.
4% and 61
.
4% on
rrc
12 and
rrc
14 respectively. But
such descents in TSTT are even below 0
.
4%. In another word, with the help
of an ecient update mechanism, TSTT enables more stable throughput under
frequent updates than GALE.
5Conluon
In this paper, we have proposed an ecient update mechanism for a GPU-
accelerated IP lookup engine. By deploying the TBL24 of DIR-24-8 onto GPU's
global memory, our proposed engine, TSTT, enables O(1) lookup. Moreover, we
presented an novel tree-like structure, Threaded Segment Tree (TST), to help
update the TBL24 on the GPU. Actually, by threading necessary leaf segments
during off-line updates, the number of unit modifications for on-line updates are
minimized, and all of them can be processed completely in parallel. According
to the experiment results, using our mechanism, the average required memory
accesses for on-line updates and the overall update overhead on both the CPU
and the GPU in average are reduced by at least 82
.
5% and 89
.
6% respectively.
What's more, due to the proposed update mechanism, the throughput in TSTT
has been proved more stable. Actually, it only decreased by at most 0
.
9% even
if update frequency increases to 100
,
000
/s
.
Acknowledgment.
This work is supported by the National Basic Research
Program of China (973) under Grant 2012CB315805, and the National Science
Foundation of China under Grant 61173167.
References
1. Jiang, W., Wang, Q., Prasanna, V.K.: Beyond TCAMs: An SRAM-based parallel
multi-pipeline architecture for terabit ip lookup. In: IEEE INFOCOM 2008 The
27th Conference on Computer Communications, pp. 1786-1794. IEEE (2008)
