powerpoint presentation - presentation - caida.ppt

1Greedy Forwarding inDynamic Scale-worksEmbedded in Hyperbolic Metric SpacesDmitri KrioukovCAIDA/UCSDJoint work withF. Papadopoulos, M. Bogu?á, A. Vahdat2OutlineModel of scale-works embeddedin hyperbolic metric spacesGreedy forwarding in the modelConclusionMotivationMotivationMotivationRouting overhead is a serious scaling limitation in works (, wireless, overlay/works, etc.)Search for infinitely scalable routing without any overheadDo not propagate any information about changing topologyRoute without any global topology knowledge, using only local informationHow is it possible?3Greedy geometric forwarding as routing using only local work topology is embedded in a geometric spaceTo reach a destination, each node forwards the packet to the neighbor that is closest to the destination in the space45Hidden space visualizedDesired properties of greedy forwarding, and related metricsProperty 1: Greedy routes should never get stuck at local minima, nodes that do not have any neighbor closer to the destination than themselves?ess ratio, percentage of essful greedy paths reaching their destinations, should be close to 1Property 2: Greedy paths should be close to shortest paths?Stretch, ratio of the lengths of greedy to shortest paths, should be also close to 1Property 3: Even if topology changes, ess ratio and stretch should stay close to 1 without any putation (., without nodes changing their positions in the space)6Problem formulation (high-level)Find bination work topology and underlying geometric space which would satisfy these desired propertiesAny suggestions?Nature offers some: many works in nature and society do route information without any topology knowledge (brain, regulatory, works, etc.)All works have power-law degree distributions (scale-free) and strong clustering (many triangular subgraphs)Let’s focus on these topologies (which, luckily, also characterize the and works)But what about the underlying space?7Conjecture: space is odes in works can often be cl