Type
Text
Type
Dissertation
Advisor
Eric C. Noel | K. Wendy Tang. Thomas G. Robertazzi. | Yuanyuan Yang | Jie Gao.
Date
2011-05-01
Keywords
Computer Science -- Computer Engineering | Graph Theory, Interconnection Networks, Network Modeling, Network Topology
Department
Department of Electrical Engineering
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/71753
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
As modern networks grow quickly in size, and the amount of data to be processed in the network explodes, fast information dissemination and data exchange is gaining strong attention today. In this research, we observe that the underlying topology of a network plays a greater role in determining the efficiency of the networks in terms of information dissemination speed especially for large networks. However, there has been a lack of constructive research encompassing network modeling, performance evaluation, and application of such network models. Therefore, we devote our efforts to identify a network model enabling ultrafast information exchange, recognize issues that may arise when applying such network model in real networks, and provide corresponding solutions for the problems. In regard to these efforts, this dissertation makes the following contributions. We identified Borel Cayley Graphs (BCGs) to be one of the fastest network topologies in information dissemination for large and dense networks. In addition, we showed that BCGs have favorable topological properties including deterministic topology generation, small nodal degree, short average path length, and small diameter. However, besides these superior properties, it has been challenging to use BCG as an underlying topology for real networks because of its lack of size flexibility. To resolve BCG's size limitation, we proposed BCG Pruning and Expansion algorithms that transform the original BCGs into Quasi BCGs in any desired sizes while maintaining the superior properties of the original BCGs. Analytical and simulation results showed that Quasi BCGs exhibit almost the same information dissemination performance and similar topological properties as those of the original BCGs. In addition, we considered wireless sensor networks to demonstrate the potential of BCGs as a real network topology. Specifically, we developed a topology control protocol called BCG Topology Control (BCG-TC) that constructs Quasi BCG network topology in wireless sensor networks. Lastly, we proposed the Dynamic BCG Routing Protocol that allows nodes in a network to update their routing table dynamically as network topology changes over time.
Recommended Citation
Yu, Jaewook, "Quasi Borel Cayley Graphs for Ultrafast Information Dissemination in Large and Dense Networks" (2011). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 958.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/958