Distributed routing in tree networks with few landmarks

摘要: We consider the problem of finding a short path between any two nodes network when no global information is available, nor oracle to help in routing. A mobile agent, situated starting node, has walk target node traversing minimum length. All about adjacencies distributed certain called landmarks. wish minimize total memory requirements as well keep per landmark reasonable levels. propose selection and distribution scheme with overall requirement linear number nodes, constant consumption non-landmark node. prove that navigation algorithm using this attains stretch factor overhead tree topologies, compared an optimal landmark-based routing obeys restrictions. The flexibility our approach allows for various trade-offs, such landmarks size region assigned each landmark.