Information Technology Reference
In-Depth Information
Splitting Algorithm.
If node
p
(
bw1, l1, r1, NULL, NULL
) is a valid node, when
req
(
bw2,l2,r2
) arrives, if
l2<l1 && r2>r1,
the value of
bw
in node
p
is consistent with value(
bw1+bw2
) and it
does not need to split. If
p.bw
needs to change, the node
p
will be split
.
Three methods
of splitting are shown in Figure 6.
Insertion Algorithm.
In the building process of the resource binary tree, the most important is the node
insertion algorithm except for the splitting algorithm. The insertion algorithm is to
convert a reservation request into a node and then insert it into the tree. The main idea
is indicated as follows:
Addnode(req, p)
Input
req
; the root of a subtree
p
Stackin(p); //let the eligible node into the stack
q = top;
while q != NULL
if q->left == NULL
Leaves(req, q) //valid node
else
Stackin(q); //invalid node
end if
q = --top;
end while
6
Performance Measurements
6.1
Experimental Environment
The reservation request—
req
(
bw
ts
te
)—has been introduced in section 2. Qing-
Xiong et al. provide a method to generate random values for each field[9].
ts
U[20,100];
td
Exponential(0.01);
te
=
ts
+
td
.
Time units are seconds. The framework of experimental platform is shown in fig-
ure 7 and this paper focuses on the admission control and the data structure.
The establishment of the experimental platform and the implementation of
data structures are completed by C language. The server is running on Ubuntu
10.10 and deployed on the mobile platforms of Intel core i3M390. All the
experimental data below are derived based on this hardware and software
environment.
