Towards a Disconnection-Tolerant, Opportunistic Internet
This project aims to develop fundamentally new, unstructured building blocks to extend today’s Internet to the realm of highly dynamic, disconnection-tolerant, opportunistic networks (DTONs). Large-scale DTONs can be viewed as the next stage of dynamism from today’s mobile ad-hoc networks (MANETs) where nodes are not only mobile and need to find multi-hop routes, but networks may also be arbitrarily partitioned and end-to-end connectivity may be available only over time.
Today’s internet infrastructure (including MANET and p2p technologies) allows a certain degree of dynamism, but falls short of what is truly required. In particular, such indirection mechanisms (eg: routing, naming) depend either upon structures (eg: hierarchies, DHT structures) or default to flooding. Structure is hard to maintain with dynamism since mappings are also increasingly dynamic. Flooding schemes used as the final fallback to robustly maintain or discover such mappings does not scale for larger networks.
Brief explanations of our activities and the publications by topics follow:
- Routing in highly dynamic networks
Our proposal is the systematic investigation of unstructured, scalable building blocks for highly dynamic and large-scale DTONs. We propose to investigate efficient, unstructured building blocks such as random walks (instead of flooding) and probabilistic indirections and routing tables (a.k.a “weak state”, instead of currently “strong” and “brittle” state semantics in structured routing tables).Publications:
Utku Günay Acer, Shivkumar Kalyanaraman, Alhussein A. Abouzeid, "Weak State Routing for Large Scale Dynamic Networks", MobiCom '07: Proceedings of the 13th Annual ACM
International Conference on Mobile Computing and Networking, Montréal, Québec, Canada, 2007, PDF , PPT - Random Walks in Time-Graphs/Tensors
A significant component of our work is the study and modeling of time graphs, a combinatorial object that is becoming ubiquitous in diverse applications, ranging from bioinformatics and computational physics to internet applications and data analysis. We focus on random walks on time graphs, a natural way of exploring these highly dynamic and stochastic objects. Towards that end, we suggested the use of tensor representations of time graphs, and proposed to explore the behavior of the eigenvalues of the resulting tensors in order to understand the convergence properties of random walks on such graphs.Publications:
P. Drineas and M.W. Mahoney, "A Randomized Algorithm for a Tensor-Based Generalization of the SVD", Linear Algebra and its Applications, 420, pp. 553-571, 2007, PDFM.W. Mahoney, M. Maggioni, and P. Drineas, "Tensor-CUR decompositions and data applications", to appear in the SIAM Journal on Matrix Analysis and Applications
- Unstructured Building Blocks & Analysis for Peer-to-Peer Networks
Unstructured protocols are crucial for DTON. We perform research on efficiency of search protocols in unstructured networked systems such as large-scale peer-to-peer content networks. Ultimately we may see the convergence of peer-to-peer content and mobile, DTON platforms on vehicles etc. Better search performance is particularly important when routing state information is weak and potentially inconsistent. This is directly relevant to the proposed work on weak-state based protocol development, especially in routing.Publications:
H. Guclu and M. Yuksel, "Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks", Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS), Toronto, Canada, June 2007 - Basic Limits on Protocol Information in Variable Topology Computer Networks
This component of the project is developing mathematical analysis leading to fundamental understanding of the performance limits and design principles of routing protocols in variable topology networks, in particular related to the routing overhead as a key parameter of interest. We are developing an information-theoretic framework for the characterization of bounds on the least overhead incurred by various classes of routing protocols.Publications:
N. Bisnik, A.A. Abouzeid, “Capacity Deficit in Mobile Ad Hoc Networks Due to Geographic Routing Overheads,” Proceedings of 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007), Anchorage, Alaska, USA, May 6-12, 2007, PDFN. Zhou and A.A. Abouzeid, “Routing in Ad Hoc Networks: A Theoretical Framework with Practical Implications,” IEEE Transactions on Information Theory, submitted April 2004, revised August 2006. PDF
People:
Co-PIs: Shivkumar Kalyanaraman (Rensselaer Polytechnic Institute (RPI)), Alhussein A. Abouzeid (RPI), Petros Drineas (RPI), Murat Yuksel (University of Nevada, Reno)
PhD Students: Utku Günay Acer (RPI), Mona Lisa (RPI)