Autonomous mobility in multilevel networks
MetadataShow full item record
Autonomous Mobile Programs (AMPs) are mobile agents that are aware of their resource needs and sensitive to the execution environment. AMPs are unusual in that, instead of using some external load management system, each AMP periodically recalculates network and program parameters and independently moves to a new location if it provides a better execution environment. Dynamic load management emerges from the behaviour of collections of AMPs. AMPs have previously been measured using mobile languages like Java Voyager on local area networks (LANs). The thesis develops an accurate simulation for AMPs on networks and validates it by reproducing the behaviour of collections of AMPs on homogeneous and heterogeneous LANs. The analysis shows that AMPs exhibit thrashing like other distributed load balancers. This thrashing is investigated in collections of AMPs, and two types of redundant movement (greedy effect) are identified. The thesis explores the extent of greedy effects by simulating collections of AMPs, and proposes negotiating AMPs (NAMPs) to ameliorate the problem. The design of AMPs with a competitive negotiation scheme (cNAMPs) is presented, followed by a performance comparison AMPs and cNAMPs using simulation. To estimate the significance of the greedy effects the properties of balanced states are established, such as independent balance, singleton optimality, and consecutive optimality. The balanced states are characterised for homogeneous and heterogeneous networks where AMPs are analysed as the general case. The significance of the cNAMP greedy effect is established by conducting a worst case analysis of redundant movements, and the maximum number, and probability of, redundant movements are calculated for homogeneous and heterogeneous networks. One of three theorems proves that in a heterogeneous network of q subnetworks the number of redundant movements does not exceed q − 1. i The thesis proposes and evaluates a multilevel cNAMP architecture that abstracts over network topologies to effectively distribute cNAMPs in large networks. The thesis investigates alternatives for implementation of this multilevel architecture and proposes a fusion-based scheme where information is first available to neighbour nodes. These neighbour nodes modify the information and pass it to remote locations. The effectiveness of the scheme is evaluated by simulating networks with up to five levels, varying the number of locations from 5 to 336, and the number of cNAMPs from 8 to 3360. The experiments investigate the effects depending on the number of levels, topologies, number of locations, number of cNAMPs, work of cNAMPs, type of cNAMPs, speed of locations, and type of rebalancing. The architecture is found to be effective because it delivers performance close to the hypothetical, e.g. each additional level increases mean cNAMP completion time by just 2%.