Information Technology Reference
In-Depth Information
Fig. 2.
TSTT's architecture based on CUDA
collect all produced unit modifications in batchs, and send them to the GPU
batch by batch, by utilizing multiple streams
1
.
Besides, to avoid storing complicated next hop information (such as multi-
next-hop [13]) on the GPU, we store their index in the TST and the TBL24
instead, with entire next hop information stored in a separated Next Hop Table
on the CPU.
3 Threaded Segment Tree (TST)
3.1 Segment Tree and Prefix Transforming
Segment Tree is a special binary search tree that supports dynamic lookup and
update. Some of its extensions have been already used in IP lookup [14] and
packet classifying [15]. They all transform prefixes into segments in a straight-
forward way. As shown in Fig. 1(b), the maximum prefix length is supposed to
be
max
, if the length and value
2
for a prefix are denoted as
len
and
pre
respec-
tively, then, its corresponding segment can be calculated as [
pre
2
max−len
,pre
×
×
2
max−len
+2
max−len
−
1].
3.2 Building Leaf-pushed Segment Tree
After transforming all prefixes into segments (as shown in Fig. 1(b)), a segment
tree can be easily constructed. But in our case, the segment tree is only used
to produce segments that represents unit modifications toward TBL24 during
1
In CUDA, a steam is a sequence of operations executed in order.
2
For a prefix formatted as
a.b.c.d/len
, its prefix length is
len
and its prefix value is
(
a ×
2
24
+
b ×
2
16
+
c ×
2
8
+
d
)
>>
(32
− len
).
