 the sought identifier in each hop, after log2b (N) hops a lookup is resolved. When a node N joins an existing Pastry network, the following steps are needed. Step 1 contacts its bootstrap node g (also called gateway node). Step 2 uses g to find a closer gateway g'. Step 3 performs a lookup for its own identifier through g' to figure out the numerically closest node S to N, and gets the routing path P. Step 4 uses the leaf set of S as its own for initialization. Step 5 takes the i-th row from the i-th node on the path from t to S, which is a latency probe defined in [12], and uses those rows in initializing its routing table. Step 6 informs every node in its neighborhood set, leaf set, and routing table of its presence. The cost is about 3 X 26 log26(N). (9.4) C 2009 by Taylor & Francis Group, LLC P2P SIP: Network Architecture and Resource Location Strategy 00000000 10000000 20000000 30000000 Row 0 10000000 11000000 12000000 13000000 Row 1 10000000 10100000 10200000 10300000 Row 2 log(N)-2 10233100 10233101 10233102 10233100 Node 10233102 log(N)-1 An interval in the id space A pointer to any node having Lines used to zoom the lowest delay in the interval inside an interval FIGURE 9.4 Illustration of how the Pastry node 10233102 chooses its routing edges in an identifier space of size N = 2128 and encoding base 2b = 4. Node departures are detected as failures and repaired in a routing table by ask- ing a node in the same row of the failed node for its entry on the failed position. The overlay network and routing algorithm of Bamboo is identical to Pastry. The difference lies in how Bamboo maintains the network as nodes join and leave the network and the network conditions vary. A new Bamboo node performs only step 1, 3, and 4 of the Pastry join algorithm described above, using g for g' in step 3. It adds the nodes in P to its routing table, but sends no latency probes. After this quick bootstrapping, it considers itself joined. Its routing table is then filled and optimized through a continuous process that stops 