Modeling P2P Grid Information Services with Colored Petri Nets - Grid Computing: Infrastructure, Service, and Applications - page 334

Query (q)
sender

Section 1

C

q1

A

q2

Section 2

Hop

q3

Section 3

B

Peer group

FIGURE 13.5 Splitting the search space.

restricting the direction, the receiving node will never have to check if it
has dealt with this request before to avoid redundant searches. Figure 13.5
depicts a search space being split with node q, sending three parallel search
queries (q1, q2, and q3) to PGs A, B, and C, with each query having upper
and lower bounds dei ning searching sections 1, 2, and 3 respectively.
Avalanching is also depicted in Figure 13.5, where q2, the query received
by PG A , is then allowed to further split the search space within searching
section 2. Using its TEC, a node in PG A forwards the search request simul-
taneously to two more peers, which in turn forward it to the remaining
PGs. For completeness, in cases where a peer receives a request that it can-
not deal with (no TEC entry within the search space), the request will then
be forwarded to another peer in the same PG to deal with it, so as not to
violate the sectioning boarders or send a request backwards.
As shown in Figure 13.5, the actual size (range) of a section must be
known to calculate the average delays incurred and the total messages
sent. Using Figure 13.4 as an example, this can be calculated with formula
(1) subtracting the ID numbers of PG A and PG B :

Range = [ID(PG B ) - 1] - ID(PG A ) (13.1)

In cases where there is no further sectioning (PIndex simple), the total
time it takes to execute a request can be computed using formula (13.2).
We assume the splitting is done evenly over the network. We also assume
that there are no processing delays incurred to send the initial request;
their delays are considered to be zero. Knowing that a processing delay
(D) will occur at every PG, multiplying D with the range of each section
would give the total delay per section. Since each section is queried in
parallel, this becomes the total delay. By multiplying the range with the