Communication Networks: Dynamic Traffic Distribution and Spatial Diffusion Disruptions

Abstract

This thesis concerns robust load allocation in communication networks. The main goal of this work is to avoid the situation in which the failure of a node (or nodes) causes a cascade of failures through an entire network, with a sequence of healthy nodes becoming overloaded and failing from picking up the slack from previously failed nodes. The network should remain functional even after some of the nodes have failed. In the dissertation we present a new methodology for dynamically distributing the load across a network so as to avoid the overloading of any of the networks nodes. A numerical solution is proposed to solve this model and build a simulation tool. This numerical method adjusts the classic explicit form of Runge-Kutta 4th order in order to integrate graph principles and produce synchronized numerical solutions for each network element. Unlike most solutions in the literature, as for example, Motter et al. [2002], Motter and Adilson [2004], Liang et al. [2004], Schafer et al. [2006], Wang and Kim [2007] and Ping et al. [2007] our methodology is generic in the sense that it works on any network topology. This means not only that it is applicable to a large range of networks, but also that it continues to be relevant after failure has destroyed part of a network, thereby changing the topology. In particular, geographical catastrophes can be of both random and intended types, taking place within a heterogeneous physical environment, on a civil (populated) area. Unlike most fault methodologies in the literature our methodology is generic in the sense that it simulates real-world geographic failure propagation towards any type of network which can be embedded to a two dimenional metric system [Chen and He, 2004], Liu et al. [2000], Callaway et al. [2000], Albert and Barabasi [2000]. It describes how physical one dimensional catastrophic waves spread in heterogeneous environments and how built–in resilience, within each network element determines its percentage of damage. We have tested our system on various randomly generated graphs with faults injected according to a model we have developed that simulates real-world geographic failure propagation. We present results from our dynamic traffic distribution methodology applied to networks, which have been either under attack or not. Throughout our case studies we prove that as soon as the topology is assigned the appropriate resources comparing to the load that it is to serve, our methodology successfully redistributes the load across the network and prevents a potential cascade failure. We either prevent the propagation of cascading failures or suggest recovery strategies after an unavoidable failure. Therefore, our methodology is instrumental in designing and testing reliable and robust networks.