The structure of connected graphs of given size and order that have minimal algebraic connectivity is investigated. It is shown that they must consist of a chain of cliques. Moreover, an upper bound for the number of maximal cliques of size 2 or larger is derived. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

Network resiliency pertains to the vulnerability of telecommunication networks in the case of failures and malicious attacks. With the increasing capacity catering of network for the booming multi-services in Next Generation Networks (NGNs), reducing recovery time and improving capacity efficiency while providing high quality and resiliency of services has become increasingly important for the future network development. Providing network resiliency means to rapidly and accurately reroute the traffic via diversely routed spare capacity in the network when a failure takes down links or nodes in the working path. Planning and optimization for NGNs require an efficient algorithm for spare capacity allocation (SCA) that assures restorability with a minimum of total capacity. This dissertation aims to understand and advance the state of knowledge on spare capacity allocation in network resiliency for telecommunication core networks. Optimal network resiliency design for restorability requires considering: network topology, working and protection paths routing and spare capacity allocation. Restorable networks should be highly efficient in terms of total capacity required for restorability and be able to support any target level of restorability. The SCA strategy is to decide how much spare capacity should be reserved on links and to pre-plan protection paths to protect traffic from a set of failures. This optimal capacity allocation problem for survivable routing is known as NP-complete. To expose the problem structure, we propose a model of the SCA problem using a matrix-based framework, named Distributed Resilience Matrix (DRM) to identify the dependencies between the working and protection capacities associated with each pair of links and also to capture the local capacity usage information in a distributed control environment. In addition, we introduce a novel ant-based heuristic algorithm, called Friend-or-Foe Resilient (FoF-R) ant-based routing algorithm to find the optimal protection cycle (i.e., two node-disjoint paths between a source-destination node pair) and explore the sharing ability among protection paths using a capacity headroom-dependent attraction and repulsion function. Simulation results based on the OMNeT++ and AMPL/CPLEX tools show that the FoF-R scheme with the DRM structure is a promising approach to solving the SCA problem for survivable routing and it gives a good trade off between solution optimality and computation speed. Furthermore, for the SCA studies of survivable networks, it is also important to be able to differentiate between network topologies by means of a robust numerical measure that indicates the level of immunity of these topologies to failures of their nodes and links. Ideally, such a measure should be sensitive to the existence of nodes or links, which are more important than others, for example, if their failure causes the network’s disintegration. Another contribution in this dissertation is to introduce an algebraic connectivity metric, adopted from the spectral graph theory, namely the 2nd smallest eigenvalue of the Laplacian matrix of the network topology, instead of the average nodal degree, to characterize network robustness in studies of the SCA problem. Extensive simulation studies confirm that this metric is a more informative parameter than the average nodal degree for characterizing network topologies in network resiliency studies.

We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector. (author´s abstract) / Series: Research Report Series / Department of Statistics and Mathematics

We will study various quantities related to connectivity of a graph. To this end, we look at Nordhaus-Gaddum type problems, which are problems where the same quantity is studied for a graph $G$ and its complement $G^c$ at the same time. For a graph $G$ on $n$ vertices with normalized Laplacian eigenvalues $0 = \lambda_1(G) \leq \lambda_2(G) \leq \cdots \leq \lambda_n(G)$ and graph complement $G^c$, we prove that \begin{equation*} \max\{\lambda_2(G),\lambda_2(G^c)\}\geq \frac{2}{n^2}. \end{equation*} We do this by way of lower bounding $\max\{i(G), i(G^c)\}$ and $\max\{h(G), h(G^c)\}$ where $i(G)$ and $h(G)$ denote the isoperimetric number and Cheeger constant of $G$, respectively. We also discuss some related Nordhaus-Gaddum questions.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Don Gruenbacher / Caterina Scoglio / Cyber physical systems emerge when physical systems are integrated with communication networks. In particular, communication networks facilitate dissemination of data among components of physical systems to meet key requirements, such as efficiency and reliability, in achieving an objective. In this dissertation, we consider one of the most important cyber physical systems: the smart grid. The North American Electric Reliability Corporation (NERC) envisions a smart grid that aggressively explores advance communication network solutions to facilitate real-time monitoring and dynamic control of the bulk electric power system. At the distribution level, the smart grid integrates renewable generation and energy storage mechanisms to improve reliability of the grid. Furthermore, dynamic pricing and demand management provide customers an avenue to interact with the power system to determine electricity usage that satisfies their lifestyle. At the transmission level, efficient communication and a highly automated architecture provide visibility in the power system; hence, faults are mitigated faster than they can propagate. However, higher levels of reliability and efficiency rely on the supporting physical communication infrastructure and the network technologies employed. Conventionally, the topology of the communication network tends to be identical to that of the power network. In this dissertation, however, we employ a Demand Response (DR) application to illustrate that a topology that may be ideal for the power network may not necessarily be ideal for the communication network. To develop this illustration, we realize that communication network issues, such as congestion, are addressed by protocols, middle-ware, and software mechanisms. Additionally, a network whose physical topology is designed to avoid congestion realizes an even higher level of performance. For this reason, characterizing the communication infrastructure of smart grids provides mechanisms to improve performance while minimizing cost. Most recently, algebraic connectivity has been used in the ongoing research effort characterizing the robustness of networks to failures and attacks. Therefore, we first derive analytical methods for increasing algebraic connectivity and validate these methods numerically. Secondly, we investigate impact on the topology and traffic characteristics as algebraic connectivity is increased. Finally, we construct a DR application to demonstrate how concepts from graph theory can dramatically improve the performance of a communication network. With a hybrid simulation of both power and communication network, we illustrate that a topology which may be ideal for the power network may not necessarily be ideal for the communication network. To date, utility companies are embracing network technologies such as Multiprotocol Label Switching (MPLS) because of the available support for legacy devices, traffic engineering, and virtual private networks (VPNs) which are essential to the functioning of the smart grid. Furthermore, this particular network technology meets the requirement of non-routability as stipulated by NERC, but these benefits are costly for the infrastructure that supports the full MPLS specification. More importantly, with MPLS routing and other switching technologies, innovation is restricted to the features provided by the equipment. In particular, no practical method exists for utility consultants or researchers to test new ideas, such as alternatives to IP or MPLS, on a realistic scale in order to obtain the experience and confidence necessary for real-world deployments. As a result, novel ideas remain untested. On the contrary, OpenFlow, which has gained support from network providers such as Microsoft and Google and equipment vendors such as NEC and Cisco, provides the programmability and flexibility necessary to enable innovation in next-generation communication architectures for the smart grid. This level of flexibility allows OpenFlow to provide all features of MPLS and allows OpenFlow devices to co-exist with existing MPLS devices. Therefore, in this dissertation we explore a low-cost OpenFlow Software Defined Networking solution and compare its performance to that of MPLS. In summary, we develop methods for designing robust networks and evaluate software defined networking for communication and control in cyber physical systems where the smart grid is the system under consideration.