A configuration method for structured P2P overlay network considering delay variations Tomoya KITANI (Shizuoka Univ.、Japan) Yoshitaka NAKAMURA (NAIST, Japan) Overview A Novel Space Filling Curve efficiently lets a 2D space coordinate be converted into a 1D space 2 easily gives each node ID from the space coordinate and the link delay between the nodes 8/20/2009 Backgrounds Realization of location-aware service by the spread of mobile Internet environment Providing the service that considered the location information of the node P2P overlay network based on location information Advertisement for the specific area is possible 3 Range specified information search 8/20/2009 Related work LL-net Structured P2P overlay network where the area on the map is hierarchically divided into 4 sub areas, and in each hierarchy the overlay links should be the different length Dynamic construction of overlay network by join/leave of mobile terminals 4 8/20/2009 Related work SkipGraph Performance of LL-net turns worse by deflection of nodes LL-net constructs quad-tree and search over the tree Depth of the tree is biased because nodes are distributed following power law in reality Efficiency of the search can be kept O(log N) at any time by usingSkipGraph into LL-net SkipGraph uses ID mapping 2D information to 1D Mapping 2D->1D 5 Space Filling Curve 8/20/2009 Space filling curve known as technique to map information of a multidimensional space such as location information onto the one-dimensional(1D) space such as ID One-dimensional ID Can use the distributed resource management technique of P2P DHT, SkipGraph, etc. Conventional Space Filling Curves 6 Lebesgue curve (Z-ordering) Hilbert curve Sierpinski curve 8/20/2009 Lebesgue Curve（Z-ordering） Divide into 4 clusters and connect nodes in the shape of Z Physical link length between clusters is long The nodes that are near on 2D space may not become near on 1D space either Lebesgue is used well practically because conversion from latitude and longitude is easy 7 8/20/2009 Node labeling using location information Geographical location information ((x,y)) of 2D space is converted into 1D x = (x1 x2 x3 ... xH) y = (y1 y2 y3 ... yH) p = (x1 y1 x2 y2 x3 y3 ... xH yH) Go around in order of assuming p as a binary number -> Lebesgue Curve (Z-ordering） 8 x 00 01 10 11 00 0000 0010 1000 1010 01 0001 0011 1001 1011 10 0100 0110 1100 1110 11 0101 0111 1101 1111 y 8/20/2009 Hilbert Curve All nodes are connected with a link of length 1 Neighbor nodes on the 2D space are relatively near also on 1D space It is complex to calculate the position in 1D space from latitude and longitude 9 8/20/2009 Advantage of space filling curve Geographically near nodes are close in 1D-ID Information search that specifies the range is efficiently executable when the information related to location information Divide into 5 ranges and search 10 Divide into 3 ranges and search 8/20/2009 New space filling curve Purpose Convertible from latitude and longitude easily as the Lebesgue curve Convertible geographically near node into near ID Introduction of label and connection relationship of Hierarchical Chordal Ring Network 11 Hamming distance between the neighbor nodes’ ID can be 1 8/20/2009 Hierarchical Chordal Ring Network20) Topology where number of average hops and network diameter are assumed O(log N) based on ring type network HCRN has the ring type structure and the tree structure HCRN is originally designed so that number of necessary wave length may become O(log N) on ring type WDM network 12 8/20/2009 ID labeling of HCRN x 00 00 0000 01 0010 00 10 11 1000 1010 10 01 0001 0011 1001 1011 10 0100 0110 1100 1110 y 01 11 0101 13 11 0111 8/20/2009 1101 1111 Correspondence to dynamic join/leave of nodes Hierarchical number of each segmented domain depends on the number of participating nodes Space filling curve that covers all nodes that belong to all hierarchies is proposed In Lebesgue, it is possible to correspond by enhancing to arrange nodes of a higher hierarchy in the oblique side of Z character 14 8/20/2009 Generation processes of HCRN from latitude & longitude Generate by the following conversion processes (x,y) : latitude & longitude of the node of the k th hierarchy To adjust Hamming distance of the label between the neighbor nodes to 1, 1. 2. 3. 4. 15 Each even number bits of x, y are reversed and p = (x1 y1 x2 y2 x3 y3 ... xk yk)= (p1... p2k) is obtained Sequence number seqp is obtained by right expression (H is the maximum number of hierarchy) Nodes are connected in order of seqp 8/20/2009 New space filling curve using HCRN Label lp of HCRN is obtained from p with the following conversions l p p ( p 1) Nodes with Hamming distance 1 are connected This curve is closed space filling curve looks like Hilbert and is connected hierarchically 16 8/20/2009 Evaluation of proposed curve Object of comparison Proposed curve(2D-HCRN) Lebesgue curve Lebesgue enhanced to multi hierarchies(2D-Lebesgue) Lowest hierarchy of proposed curve Hilbert curve Evaluation item 17 Distance on 1D-ID with the neighborhood nodes on 2D by Index Range. Delay to need to go around all nodes by simulation 8/20/2009 Index Range19) To evaluate how far each two nodes physically in 4 neighborhoods on the filling curves Logarithmic average distance on 1D-ID of geographically 4 neighborhoods 18 seq(i) : Sequence number on 1D-ID of node i pos(i) : Position (x,y) on 2D-plane of node i 8/20/2009 Smaller is better Index Range of each space filling curve 19 8/20/2009 Simulation environment 10-10,000 nodes participate into the network sequentially Nodes join according to the following algorithm 1. 2. 3. 4. The node with latitude & longitude p = (x1 y1 x2 y2 ... xH yH) = (p1 p2 ... p2H) joins i =2 If the node with the label of p’ = (p1... pi) does not exist yet, p’ is assumed to be a label that shows the location information of the node If there is p‘ , i = i + 2 and go to 3. Position p of the participation node is decided by a random number according to "random distribution" and "Zipf distribution" 20 8/20/2009 Average physical distance between neighbor nodes in ID (Randomly distributed) 21 8/20/2009 Average physical distance between neighbor nodes in ID (Distributed following Zipf law) 22 8/20/2009 Square average of physical distance between neighbor nodes in ID (Randomly distributed) 23 8/20/2009 Square average of physical distance between neighbor nodes in ID (Distributed following Zipf law) 24 8/20/2009 Conclusions We proposed the new space filling curve for small delay structured P2P overlay network Geographical round distance is small and conversion is comparatively easy More suitable for hierarchical-spread nodes than the conventional curves Future work 25 Performance evaluation of the proposed space filling curve in the real network environment especially in node distribution with bias Reexamination of the routing entry of each node to improve the performance 8/20/2009
© Copyright 2024 ExpyDoc
