Graph Theory based Design of Scalable Network Systems

Due to the Internet's enormous growth in size, interconnecting heterogeneous networks reliably and efficiently has been a major topic in computer networks research for decades. Currently, more than four billions users (hosts) are connected through the Internet and the number is still growing. To achieve scalable networking, many researchers have invented and improved communication topologies and network protocols. Among these efforts, Graph theory plays an important role in protocol design and topology development. In this dissertation, we discuss graph theory based network design to enhance scalability and efficiency, and we provide applications to Wireless Sensor Networks (WSNs).;Borel Cayley Graphs (BCGs) are regular and dense graphs with promising properties when used as a communication topology: efficient topological/spectral properties, Generalized Chordal Ring (GCR) representation and vertex transitivity. However, a BCG's topological properties such as diameter and average path length have large variations depending on the choice of its discrete generators. Further, despite having a short diameter, a BCG can result in large communication distances between nodes.;In this dissertation, we propose Expanded Borel Cayley Graphs (Ex-BCGs), a systematic expansion of BCGs that preserve BCG's advantageous network properties. Ex-BCGs are based on node ID space expansion and connection rule redefinition, without changing the associated BCG generating parameters. We found that the resulting Ex-BCGs have scalable network properties even after a large scale size expansion. Using these properties, we provide the Class-level Vertex Transitive (CVT) routing protocol to construct a distributed and optimal routing algorithm with a small routing table. We exploit the Cut-Through Rewiring (CTR) algorithm to resize Ex-BCGs to arbitrary sized networks without downgrading the network connectivity and performance. For fault-tolerant routing in resized Ex-BCGs, we present the Aggressive Multi-path Aware (AMA) routing protocol that involves routing and rewiring around node failures. Simulation results over a variety of node failure rates show that the AMA routing protocol produces reliable reachability and efficient average routing path length.;For Ex-BCGs network applications, we construct a communication topology and design a routing algorithm for WSNs. We developed the Ex-BCGs Topology Construction (EBTC) algorithm to discover physical neighbors without collision and to establish efficient logical connections. This was made with the cycle characteristic of Ex-BCGs connections. As a result, EBTC constructs an energy efficient communication topology with a small nodal degree and a short average path length. For routing in WSNs, we present the Ex Clustering algorithm that forms clusters for hierarchical routing in the communication topology generated from the modified EBTC operation. The Ex Clustering algorithm enables a deterministic time schedule for data transmission without collisions and provides energy saving by allowing nodes to enter sleep mode when not clustered. From comparison studies with LEACH and Selective LEACH algorithms, we observed that Ex Clustering produces lower energy consumption, longer network lifetime and higher reported event ratio.