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

the bulk of the monitoring load within a PG, enabling one to query the
whole network through a fast and efi cient P2P query mechanism. By
dynamically splitting up the search space into sections, PIndex enables
parallel searches to be carried out using contacts in a node's TEC. At the
same time, it appends upper and lower PG ID bounds for each message
being sent. These bounds limit the destinations where these requests can
be forwarded to, effectively splitting the search space dynamically at the
time of the search. However, as the sizes of sections become large, delays
within each section could also grow. PIndex resolves this by using the
same splitting algorithm to split a section at every hop, as the one used to
split the whole search space into many sections.
Figure 13.4 depicts how a single request can be dynamically reproduced
to split a search space. As shown in Figure 13.4, PG1 receives a search
request with an upper bound of 14 and a lower bound of 1 (14-1). It then
for wa rd s t h r e e copie s to PG2, PG7, a nd PG11 r e s p e c t ive ly w it h new b ou nd s
(sections) 6-2, 10-7, and 14-11 respectively. PG2 then sends another two
more search requests within its range of 6-2 to PG3 and PG5, who in turn
forward copies to the remaining PG4 and PG6. Thus all the PGs 1-14 can
be queried in 13 hops, which is the same cost as if a simple forwarding to
the nearest neighbor method was used. However, Figure 13.4 also groups
these hops that occur at the same time (hops 1, 2, and 3). As these hops
work in parallel, the time taken to query all the PGs will be equivalent to
three hops. Producing more parallel hops can reduce search times, resem-
bling a controlled form of l ooding of messages (avalanching).
As shown in Figure 13.4, messages must be restricted in movement to
one direction to ensure that searches begin at the start of the section. By

2nd Parallel hop

1st Parallel hop

123456789 0 1 2 3 4

Peer group

3rd Parallel hop

FIGURE 13.4 Dynamic sectioning.