Dept. of Computer Science, University College London, University of London, UK.
The tremendous success of the Internet has made possible and even encouraged the realisation of systems characterised by very large scale and high level of distribution. Managing such systems requires systematic communication between a centralised station and distributed components. In many cases, a pure centralised model is adopted in which the management station retrieves information directly from the managed elements and performs all the required computation. For large, distributed systems this model is prone to information implosion, which tends to cause congestion both to the management station and to its attached network. Therefore, pure centralised management, despite having the advantage of simplicity, inherits the intrinsic limitations of centralised systems, namely their limited responsiveness, accuracy, and scalability.
The approach traditionally followed to address those limitations is to decentralise management intelligence. A natural approach is to introduce several area managers in charge of collecting and preprocessing raw data from different portions of the system. When possible, the event-driven model of computation is adopted. In this case, the area managers or even the managed elements are equipped with logic that performs semantic compression of local information and sends notifications to the manager only under particular circumstances. In this way, the central station is alleviated and the traffic incurred in its vicinity can be dramatically reduced. Event-driven and hierarchical management system organization can cope with scalability problems only to a limited extent. Such approaches are inherently more complex that centralised ones, while they still lack the flexibility, adaptability and relatively loose system organization, which are desirable in large-scale, highly dynamic networked systems.
This thesis is focused on the design and evaluation of a dynamic distributed monitoring system based on the use of mobile software agents. Agents act in the role of area managers but, differently from the case of static distributed monitoring systems, they can be placed in strategic locations within the network by accounting for the network state and for the type of task to be performed. In addition, at run time, agents can migrate to other locations or clone other agents in order to provide adaptation to changes in the underlying network.
The core of the thesis addresses the problem of efficiently computing the agent locations. In graph theoretical terms, this is the problem of optimally placing p servers within a network of N nodes, which falls in the class of the p-centre and p-median problems. These are NP-complete problems when striving for optimality. The thesis proves that existing approximate solutions, computable in polynomial time, are not viable. Consequently, a novel approximate solution, aiming at minimising the overall traffic and delay incurred by the agent-based distributed monitoring system, is proposed. The proposed algorithm is proved O(N*R(u)) (where R(u) is the network radius and N the number of monitored nodes). Moreover, it is demonstrated that the computed agent locations are near-optimal.
The agent location algorithm is solved in a distributed fashion making use of agent weak mobility, which is the ability of agents to move around the network from node to node carrying their code and data. The algorithm relies also on agent cloning, the ability of an agent to create and dispatch copies of itself. Both weak mobility and agent cloning are properties that so far have not been exploited to the full extent of their potential in the field of management. A distributed monitoring system based on this algorithm is assessed by simulation and it is shown that significant reductions in both network traffic and response time can be achieved in addition to the increased flexibility and adaptability offered by agent mobility.
PhD Thesis, August 2001.
The full thesis in Acrobat pdf (1.5M) can be made available by contacting the author (a.liotta (at) tue.nl).