· · · Institutional Repository

Our society depends more strongly than ever on large networks such as transportation networks, the Internet and power grids. Engineers are confronted with fundamental questions such as “how to evaluate the robustness of networks for a given service?”, “how to design a robust network?”, because networks always affect the functioning of a service. Robustness is an important issue for many complex networks, on which various dynamic processes or services take place. In this work, we define robustness as follows: a network is more robust if the service on the network performs better, where performance of the service is assessed when the network is either (a) in a conventional state or (b) under perturbations, e.g. failures, virus spreadings etc. In this thesis, we survey a particular line of network robustness research within our general framework: robustness quantification, optimization and the interplay between service and network. Significant progress has been made in understanding the relationship between the structural properties of networks and the performance of the dynamics or services taking place on these networks. We assume that network robustness can be quantified by a topological measure of the network. A brief overview of the topological measures is presented. Each measure may represent the robustness of a network with respect to a certain performance aspect of a service. We focus on the measure known as algebraic connectivity. Evidence collected from literature shows that the algebraic connectivity characterizes network robustness with respect to synchronization of dynamic processes at nodes, random walks on graphs and the connectivity of a network. Moreover, we illustrate that, on a given diameter, graphs with large algebraic connectivity tend to be dense in the core and sparse at the border. Such structures distribute traffic homogeneously and are thus robust in terms of traffic engineering. How do we design a robust network with respect to the metric algebraic connectivity? First, the complete graph has the maximal algebraic connectivity, while its high link density makes it impractical to use due to the cost of constructing links. Constraints on other network features are usually set up to incorporate realistic requirements. For example, constraint on the diameter may guarantee certain end-to-end quality of service levels such as the delay. We propose a class of clique chain structures which optimize the algebraic connectivity and many other robust features among all graphs with diameter D and size N. The optimal graph within the class can be determined either analytically or numerically. Second, complete replacement of an existing infrastructure is expensive. Thus, we design strategies for robustness optimization using minor topological modifications. These strategies are evaluated in various classes of graphs. The robustness quantification, or equivalently, the association of the performance of a service with a topological measure, may be implicit. In this case, we explore the interplay between topology and service in determining the overall performance. Many services on communications and transportation networks are based on shortest path routing. The weight of a link, such as delay or bandwidth, is generally a metric optimized via shortest path routing. Thus, link weight tuning, a mechanism to control traffic, is also considered as part of the service. The interplay between service (shortest path routing and link weight tuning) and topology is investigated for the following performance aspects: (a) the structure of the transport overlay network, which is the union of shortest paths between all node pairs and (b) the traffic distribution in the overlay network. Important new findings are (i) the universal phase transition in overlay structures as we tune the link weight structure over different classes of networks and (ii) the power law traffic distribution in the overlay networks when link weights vary strongly in various classes of networks. Furthermore, we consider the service that measures a network topology as the union of shortest paths among a set of testboxes (nodes). The measured topology is a subgraph of the overlay network, which is again a subgraph of the actual network. The performance in terms of the sampling bias of measuring a network topology is investigated. Our work contributes substantially to a better understanding of the effect of the service (testbox selection) and the actual network structure on the performance with respect to sampling bias. Our investigations on the interplay between service and network reveal again the association between the performance of a service and certain topological feature, and thus, contribute to the quantification of network robustness. The multidisciplinary nature of this research lies not only in the presence of robustness issues in many complex networks, but also in that advances in other disciplines such as graph theory, combinatorics, linear algebra and statistical physics are widely applied throughout the thesis to study optimization problems and the performance of large networks.

In this paper, we present a design and an analysis of customized crossbar schedulers for reconfigurable on-chip crossbar networks. In order to alleviate the scalability problem in a conventional crossbar network, we propose adaptive schedulers on customized crossbar ports. Specifically, we present a scheduler with a weighted round robin arbitration scheme that takes into account the bandwidth requirements of specific applications. In addition, we propose the sharing of schedulers among multiple ports in order to reduce the implementation cost. The proposed schedulers arbitrate on-demand (at design time) interconnects and adhere to the link bandwidth requirements, where physical topologies are identical to logical topologies for given applications. Considering conventional crossbar schedulers as reference designs, a comparative performance analysis is conducted. The hardware scheduler modules are parameterized. Experiments with practical applications show that our custom schedulers occupy up to 83% less area, and maintain better performance compared to the reference schedulers.

This thesis focuses on the topological characterization of complex networks. It specifically focuses on those elementary graph measures that are of interest when quantifying topology-related aspects of the robustness of complex networks. This thesis makes the following contributions to the field of complex networks. Firstly, the thesis analyses the relationships among a variety of graph measures and proposes a definite set, capable of expressing the most relevant topological properties of complex networks. Secondly, the thesis relies on spectral measures to initiate a classification of the qualitative topological properties that characterize specific classes of complex networks. Thirdly, the thesis illustrates the use of spectral measures in a quantitative characterization of topology-related aspects of the network robustness. Finally, this thesis demonstrates the use of spectral measures in a quantitative characterization of the extent to which the robustness to different types of failures manifests itself in the underlying complex networks structure.

Biological networks exhibit intriguing topological properties such as small-worldness. In this paper, we investigate whether the topology of a metabolic network is related to its robustness. We do so by perturbing a metabolic system in silico, one reaction at a time and studying the correlations between growth, as predicted by flux balance analysis, and a number of topological metrics, as computed from three network representations of the metabolic system. We find that a small number of metrics correlate with growth and that only one of the network representations stands out in terms of correlated metrics. The most correlated metrics point to the importance of hub nodes in this network: so-called "currency metabolites". Since they are responsible for interconnecting distant functional modules in the network, they are important points in the networks for predicting if reaction removal affects growth. Source code and data are available upon request.

The present Low Voltage (LV) grid, which until recently was mainly composed of passive electrical components (consumers), is being gradually overrun by active electrical components (prosumers), who not only consume but also generate and share power locally. This development is introducing changes in the operational dynamics of the LV grid that could result in voltage stability problems and the violation of infrastructural constraints if not well managed. A re-design of the present LV grid is, therefore, imperative to enable it meet these new requirements. This thesis was aimed at studying the influence of topological metrics on the operational performance of the LV grid in view of current developments in energy consumer behaviour with a view to proposing the topological changes and/or modifications in network architecture that would yield optimal outcomes. We modelled the present LV grid as a radial network, and compared it to three other network models -random, small-world and scale-free networks- under different loading scenarios. We proposed novel structural and operational metrics that are suitable for the LV grid, and analysed the networks in terms of these metrics. We also compared their robustness under different attack scenarios and demonstrated the correlation between the structural and the operational metrics, thus, identifying important structural metrics that need to be optimized to improve the future LV grid performance. Finally, we then investigated the possible modifications of the radial network model of the present LV grid that would yield similar results. The results highlighted the structural weaknesses of the present LV grid under futuristic and simultaneous loading conditions and presented the scale-free model as the most suitable architecture for the future LV grid as it out-performed all the other network models under similar loading conditions. They also showed that the insertion of additional links at critical positions in the radial network could achieve similar results. We therefore proposed this structural modification as a more cost-effective approach to improved operational performance of the LV grid.