Information Technology Reference
In-Depth Information
(a) Before leaf pushing.
(b) After leaf pushing.
Fig. 3.
Segment tree built on the FIB shown in Fig. 1(a)
Algorithm 1.
Leaf Pushing
Input
:
curNode,nextHop
1
if
curNode
=
NULL
or
curNode.isPrefixSeg
then
2
return
;
3
end
4
LeafPushing (
curNode.leftChild,nextHop
);
5
if
curNode.isLeaf
then
6
ModifyNode (
curNode,nextHop
);
7
end
8
LeafPushing (
curNode.rightChild, nextHop
);
off-line updates. In order to generate as less segments as possible, we build a
compact segment tree (as shown in Fig. 3), in which a segment should not be
broken unless necessary. Originally, a prefix corresponds to only one segment
(let's call it
prefix segment
), whose value is set as the entry index of this prefix.
So, each update request needs only modify just one prefix segment, enabling
update process be simple and ecient.
However, since two prefix segments may intersect with each other, on-line
updates produced by them may toward the same unit, making it unavailable
to process them in parallel. To address this issue, we introduce a special leaf
pushing technique
3
to push all prefix segments' values into leaf segments (shown
in Fig. 3(b)). Unlike the traditional leaf-pushing algorithm [6], there are two
important special rules for ours:
1)
All prefix segments still reserve their own
values after leaf pushing.
2)
Each value is pushed from some prefix segment
down to all possible leaf segments, until reaching another prefix segment. This
algorithm is described in Algorithm 1.
3
Leaf Pushing is a widely used technique for Trie-based IP lookup.
