DefinePK

Abstract

Common overlay network arranges nodes in a particular topology such as a ring, a tree or a hyper-tree on top of its’ physical network and takes advantage of its structure to improve network efficiency. The structured overlay network may provide efficient routing but the constructed structured network may not consider physical proximity in the physical network. The construction of any structured network requires nodes to be topologically sorted. Topologically sorting nodes is not a difficult task, however, to keep nodes in a correct state where transient faults exist like the overlay network created on top of the mobile network can be daunting. In this paper, we introduce an algorithm to improve the performance of an overlay network by ensuring physical proximity. Furthermore, the linearized nodes will self-stabilize to a correct state as soon as the transient fault stops. A segment based self-stabilizing linearizing algorithm that creates a linear overlay network (topologically sorting) over the mobile network is proposed.