SIP Handbook: Services, Technologies, and Security Stored items A node with id n An item with id k Successor pointer Predecessor pointer The node which an item stored Routing table of a Chord Node n: Every Node should know the first node in 1/2, 1/4, 1/2 log 2 (N) of identifier space and starting from n. n+1 n+2 n+2 log (N)-1 n+N-1 2 the id space 1/2(log 2 (N)-2) of the id space 1/2(log (N)- 1) of the id space 1/2 of the id space Succ(10) A node with id n An item with id k Successor pointer of node 9 Successor pointer of node 2 FIGURE 9.3 (a) A chord network with N = 16 populated with 6 nodes and 5 items. (b) The general policy for Chord's routing tables. (c) Example of inserting a new item. C 2009 by Taylor & Francis Group, LLC P2P SIP: Network Architecture and Resource Location Strategy The network contains nodes with identifiers 0, 2, 5, 9, 12. The policy for constructing routing tables is shown in Figure 9.3b. As pointed out ear- lier, Node n chooses its pointers by assuming that the identifier space starts from its identifier. It chooses to have the pointers to the successors of the identifiers: N + 22 and N + 23. In this way, the last pointer n + 23 divides the space into two halves. The one before it, n + 22, divides the first half into two quarters, and SO on. When no node exists at the desired position, its successor will be taken instead. As shown in Figure 9.3a, an item is stored at the first node that follows clockwise on the identifier space. If items with identifiers 3, 6, 9, 11, and 15 are to be stored in this network, then {3} will be stored at 5; {6,9 at 9; {11} at 12; and {15} at 0. The lookup process follows the result of the way the identifier space is partitioned. Both the insertion and querying of items depend on how to find the successor of an id. As illustrated in Figure 9.3c, if node 12 wants to insert a new item with an identifier of 7, the lookup is forwarded to node 5, which is the closest preceding finger to the identifier 7 from the point of view of 12. Similarly, node 5 will lookup 