CROWN: A Service Grid Middleware for e-Science - Grid Computing: Infrastructure, Service, and Applications - page 16

A (500, 800)

B1 (100, 300) B2 (800, 1000)

C1 (0, 100)

C2 (300, 500)

FIGURE 1.7 An example of an RCT.

Compared with traditional AVLs, each node of the RCT manages a
range of values, instead of a single value. Each node only needs to main-
tain its connection with direct child nodes and a parent, and operations
like registration, updating, and querying can start from any node. Unlike
the traditional AVL structure, higher-level nodes of RCT are not required
to maintain more information or bear more load than those in lower lev-
els, which provide the basis for RCT to scale easily.
Suppose D is the value domain of the PA of an RCT. Each node n of an
RCT is responsible for a subrange of D , or D n . All resources with PA values
belonging to D n register themselves to node n. We name each RCT node an
HR (head of a subrange). The terms “HR n ” and “node n ” will be used
interchangeably in the rest of this chapter. In Figure 1.7, the circles denote
HRs, while the squares below an HR denote computational resources regis-
tered with an HR.
Suppose N is the total number of HRs in an RCT, and lc( n ) and rc( n ) are
the left and right child nodes of HR n , respectively. Since an RCT is a
binary search tree, the following observations can be found:

D i ∩ D j = j, ∀ i , j Œ [1, N ] (1.1)

D lc( i ) < D i < D rc( i ) , ∀ i Œ [1, N ] (1.2)

D i < D j if the upper bound of D i is less than the lower bound of D j ; for
example, [1, 2] < [3, 4].
If the ranges of node i and node j , that is, D i and D j , are adjacent, node i is
referred to as a neighbor of node j , and vice versa. If node i is a neighbor
of node j and D i < D j , node i is called the left neighbor of node j (denoted
by L-neighbor( j )) and node j is called the right neighbor of node i (denoted
by R-neighbor( i )). Note that there are two exceptions: the leftmost HR and