Centre for Communication Systems Research (CCSR), University of Surrey, Guildford, UK.
Systems relying on increasingly large and dynamic communication networks must find effective ways to optimally localize service facilities. This can be achieved by efficiently partitioning the system and computing the partitions. centers, solving the classic p-median and p-center problems. These are NP-hard when striving for optimality. Numerous approximate solutions have been proposed during the past 30 years. However, they all fail to address the combined requirements of scalability, optimality and flexibility.
This thesis presents a novel location algorithm that is distributed, does not require any direct knowledge of the network topology, is computed in linear time, and leads to provably near-optimal p-medians. The algorithm exploits the key properties of Mobile Agents (MAs), the latter being autonomous software entities capable of roaming the network and cloning or spawning other Mobile Agents. Mobile Agents play the role of service facilities that are capable of iteratively partitioning the network and locating themselves in p-median locations.
This thesis motivates the use of Mobile Agents to provide a .distributed. solution to the p-median problem that is traditionally tackled only with .centralised. algorithms. Efficiency is achieved through a combination of distribution, code mobility and simple use of network routing information. The proposed near-optimal algorithm does not require the reconstruction of the network distance matrix and is characterized by linear computational complexity. The proposed approach outweighs existing algorithms, which are polynomial of 2nd and 3rd degree and require a complete knowledge of the network topology.
The evaluation of the proposed algorithm has been carried out through simulations. For this purpose, a simulation environment on top of NS (Network Simulator) was developed, which allows the implementation and evaluation of a Mobile Agent system. Along with the algorithm a set of applications that shows the flexibility of the algorithm to adapt to different requirements is presented. The range of algorithm applications focused on overlay networks and in particular Application-level Multicast, Content Adaptation Networks and Overlay Resource Management.
PhD Thesis, March 2005.
The full thesis in Acrobat pdf can be made available by contacting the author (carmalo_ragusa (at) hotmail.com).