Abstract
This paper presents an overlay network protocol called “LASK: Locality-Aware Service discovery protocol for K-nearest search”, for supporting scalable and locality-aware distributed k-Nearest Service Discovery (kNSD). The kNSD provides a lookup function to find k service nodes located close to the requester. Importance of such function increases under the situation of growth in size and the diversity of the resources in the so-called edge computing environments. In LASK, efficient cooperative routing algorithm is implemented utilizing the two-dimensional structure of key-order preserving structured overlay networks that are constructed according to the network topology and the name of the service. This structure achieves scalable and locality-aware routing of the lookup messages to the matched nodes avoiding redundant data transmissions across the edge networks. Extensive simulation evaluations show that LASK could achieve small discovery latency in the large-scale edge computing environments; a typical kNSD took less than 5 ms in a data center network model and less than 100 ms in the Internet model even when there are 100,000 nodes in the entire network.