MLS

Abstract

ALGO is a distributed location service to track the position of mobile nodes and to route messages between any two nodes. The lookup of nodes is achieved by searching in a hierarchy of pointers that each node maintains. We show that ALGO has constant stretch for lookup requests. In contrast to previous work, we consider a concurrent setup where nodes are truly mobile and move even while messages are being routed towards them. We prove correctness and efficiency of ALGO and determine the maximum speed at which the nodes might move, which is up to 1/15 of the routing speed. To the best of our knowledge, this is the first work that bounds the node speed, a necessity to prove the success of a lookup algorithm. We verified our theoretical results through extensive simulation and show that the average lookup stretch is around 6.