| dc.description.abstract | Infrastructures like telecommunication systems, power transmission
grids and the Internet are complex networks that are vulnerable to
catastrophic failure. A common mechanism behind this kind of failure
is avalanche-like breakdown of the network's components. If a
component fails due to overload, its load will be redistributed, causing
other components to overload and fail. This failure can propagate
throughout the entire network. From studies of catastrophic failures in
di erent technological networks, the consensus is that the occurrence
of a catastrophe is due to the interaction between the connectivity
and the dynamical behaviour of the networks' elements.
The research in this thesis focuses particularly on packet-oriented networks.
In these networks the tra c (dynamics) and the topology
(connectivity) are coupled by the routing mechanisms. The interactions
between the network's topology and its tra c are complex as
they depend on many parameters, e.g. Quality of Service, congestion
management (queuing), link bandwidth, link delay, and types of
tra c. It is not straightforward to predict whether a network will
fail catastrophically or not. Furthermore, even if considering a very
simpli ed version of packet networks, there are still fundamental questions
about catastrophic behaviour that have not been studied, such
as: will a network become unstable and fail catastrophically as its size
increases; do catastrophic networks have speci c connectivity properties?
One of the main di culties when studying these questions is that,
in general, we do not know in advance if a network is going to fail
catastrophically. In this thesis we study how to build catastrophic
5
networks. The motivation behind the research is that once we have
constructed networks that will fail catastrophically then we can study
its behaviour before the catastrophe occurs, for example the dynamical
behaviour of the nodes before an imminent catastrophe.
Our theoretical and algorithmic approach is based on the observation
that for many simple networks there is a topology-tra c invariant for
the onset of congestion. We have extended this approach to consider
cascading congestion. We have developed two methods to construct
catastrophes. The main results in this thesis are that there is a family
of catastrophic networks that have a scale invariant; hence at the
break point it is possible to predict the behaviour of large networks
by studying a much smaller network. The results also suggest that
if the tra c on a network increases exponentially, then there is a
maximum size that a network can have, after that the network will
always fail catastrophically.
To verify if catastrophic networks built using our algorithmic approach
can re
ect real situations, we evaluated the performance of a small
catastrophic network. By building the scenario using open source
network simulation software OMNet++, we were able to simulate a
router network using the Open Shortest Path First routing protocol
and carrying User Datagram Protocol tra c. Our results show that
this kind of networks can collapse as a cascade of failures. Furthermore,
recently the failure of Google Mail routers [1] con rms this kind
of catastrophic failure does occur in real situations. | en_US |
