Peer-to-peer systems are a highly decentralised form of distributed computing, which has ad¬
vantages of robustness and redundancy over more centralised systems. When the peer-to-peer
system has a stable and static population of nodes, variations and bursts in traffic levels cause
momentary levels of congestion in the system, which have to be dealt with by routing policies
implemented within the peer-to-peer system in order to maintain efficient and effective routes.
Peer-to-peer systems, however, are dynamic in nature, as they exhibit churn, i.e. nodes
enter and leave the system during their use. This dynamic nature makes it difficult to identify
consistent routing policies that ensure a reasonable proportion of traffic in the system is routed
successfully to its destination. Studies have shown that chum in peer-to-peer systems is difficult
to model and characterise, and further, is difficult to manage.
The task of creating and maintaining efficient routes and network topologies in dynamic
environments, such as those described above, is one of dynamic optimisation. Complex adap¬
tive systems such as ant colony optimisation and genetic algorithms have been shown to display
adaptive properties in dynamic environments. Although complex adaptive systems have been
applied to a small number of dynamic optimisation problems, their application to dynamic opti¬
misation problems is new in general and also application to routing in dynamic environments is
new. Further, the problem characteristics and conditions under which these algorithms perform
well, and the reasons for doing so, are not yet fully understood. The assessment of how good
the complex adaptive systems are at creating solutions to the dynamic routing optimisation
problem detailed above is dependent on the metrics used to make the measurements.
A contribution of this thesis is the development of a theoretical framework within which we
can analyse the behaviours and responses of any peer-to-peer system. We do this by considering
a peer-to-peer system to be a graph generating algorithm, which has input parameters and has
outputs which can be measured using topological metrics and statistics that characterise the
traffic through the network. Specifically, we consider the behaviour of an ant-based peer-to-peer system and we have designed and implemented an ant-based peer-to-peer simulator to
Recently methods for characterising graphs by their scaling properties have been developed and a small number of distinct categories of graphs have been identified (such as random
graphs, lattices, small world graphs, and scale-free graphs). These graph characterisation methods have also enabled the creation of new metrics to enable measurements of properties of the
graphs belonging to different categories.
We use these new graph characterisation techniques mentioned above and the associated
metrics to implement a systematic approach to the analysis of the behaviour of our ant peer-to-peer system. We present the results of a number of simulation runs of our system initiated with
range of values of key parameters. The resulting networks are then analysed from both the
point of view of traffic statistics, and also topological metrics.
Three sets of experiments have been designed and conducted using the simulator created
during this project. The first set, equilibrium experiments, consider the behaviour of the system
when the number of operational nodes in the system is constant and also the demand placed on
the system is constant. The second set of experiments considers the changes that occur when
there are bursts in traffic levels or the demand placed on the system. The final set considers the
effect of churn in the system, where nodes enter and leave the system during its operation. In
crafting the experiments we have been able to identify many of the major control parameters
of the ant-based peer-to-peer system.
A further contribution of this thesis is the results of the experiments which show that under conditions of network congestion the ant peer-to-peer system becomes very brittle. This
is characterised by small average path lengths, a low proportion of ants successfully getting
through to their destination node, and also a low average degree of the nodes in the network.
This brittleness is made worse when nodes fail and also when the demand applied to the system
A further contribution of this thesis is the creation of a method of ranking the topology of a
network with respect to a target topology. This method can be used as the basis for topological
control (i.e. the distributed self-assembly of network topologies within a peer-to-peer system
that have desired topological properties) and assessing how best to modify a topology in order
to move it closer to the desired (or reference) topology. We use this method when measuring the
outcome of our experiments to determine how far the resulting graph is from a random graph.
In principle this method could be used to measure the distance of the graph of the peer-to-peer
network from any reference topology (e.g. a lattice or a tree).
A final contribution of this thesis is the definition of a distributed routing policy which
uses a measure of confidence that nodes in the system are in an operational state when making
calculations regarding onward routing. The method of implementing the routing algorithm
within the ant peer-to-peer system has been specified, although this has not been implemented
within this thesis. It is conjectured that this algorithm would improve the performance of the
ant peer-to-peer system under conditions of churn.
The main question this thesis is concerned with is how the behaviour of the ant-based
peer-to-peer system can best be measured using a simulation-based approach, and how these
measurables can be used to control and optimise the performance of the ant-based peer-to-peer
system in conditions of equilibrium, and also non-equilibrium (specifically varying levels of
bursts in traffic demand, and also varying rates of nodes entering and leaving the peer-to-peer