Topology and congestion invariant in global internet-scale networks

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.