Broadly, networking research has two flavors. First, ``system-design'' research is mainly about protocol and algorithmic design, implementation and experimentation. Second, ``network-theory'' research is mainly about performance analysis using mathematical tools. The research I enjoy most is a combination of these two, stemming from my desire to apply formal analytical and algorithmic methods to problems of high practical relevance, and propose solutions that can be implemented and used in practice.
Since I joined USC I have modeled and analyzed the performance of a variety of networks, including the Internet, mobile ad hoc networks, delay and disruptive tolerant networks, sensor networks, mesh networks, peer to peer networks and the web. I have also designed methods, algorithms, and protocols to solve problems related to such systems. In the rest of this statement I will highlight what I consider my most important contributions to the field of networking and briefly point to future directions of research.
Mobility-assisted communication departs drastically from the traditional view of networking and is more reminiscent of how the post-office operates: When a node wants to send a message to another node, it may transmit one or more copies of the message to one or more distinct relays. Each relay will carry the message further, and may transmit it to a new, better relay or directly to the destination. In collaboration with my co-authors [J1, J2, J18, J21, J22, C2, C4, C8, C11, C16, C18, C19, C20, C30] (all citations refer to the corresponding paper listed in my CV) I have investigated the routing space in such networks, designed routing schemes that are efficient under a wide range of node mobility characteristics, network connectivity degrees, and traffic loads, and analyzed and optimized their performance with formal mathematical analysis that takes into account significant real world limitations, like finite bandwidth and interference. Specifically, after formally establishing that flooding-based routing techniques lead to bad performance because they induce excessive interference, we introduced a family of routing algorithms that spray a small number of copies to a carefully selected number of relays, and intelligently route each copy towards the destination. Our analysis showed that the proposed schemes are highly scalable, perform very close to optimal, and, interestingly, achieve surprisingly low delays while using remarkably few resources.
The design and analysis of the routing schemes has appeared in two IEEE/ACM Transactions on Networking papers [J1,J2]. The analysis has been extended to account for real world limitations, like finite bandwidth and wireless interference [C16, C20] and is accepted to appear in its entirety at IEEE Transactions on Mobile Computing [J22]. Studies of fundamental mobility properties and their effect in the performance of mobility-assisted communication have appeared at ACM MobiHoc [C4] and at [C19]. This work has been extended and presented in its entirety as an invited journal [J18]. [C4] has also introduced a new mobility model that captures spatial correlations. The model has been extended to also capture temporal correlations and the extended model has appeared at IEEE Infocom [C2] and presented in its entirety at [J21]. The research has been funded by the National Science Foundation, the METRANS Transportation Center (with the goal of applying some of my ideas for safety applications in the context of vehicular networks), and USC's Zumberge Research and Innovation Award.
Ongoing research and future directions: The level of connectivity of an intermittently connected network may change very fast in time and space, and network nodes should adapt quickly to these changes. Thus, it is of outmost importance to design automated distributed mechanisms that allow nodes to characterize on the fly how connected the network is, and select appropriate protocols given the conditions. For example, as connectivity deteriorates there may be a need for more data replication. As connectivity deteriorates further there may even be a need for specialized nodes that move in the network with the sole purpose of assisting communication. With this in mind, I am working on distributed mechanisms that use local measurements, message passing, and analysis to access the level of connectivity and make optimal routing decisions that satisfy some quality of service guarantees. I am also particularly interested in designing application-specific routing protocols that provide efficient communication solutions in the context of vehicular and disaster recovery networks.
Achieving efficiency over random access schedulers requires the transport protocol to be aware of the existing complex interference. With this in mind, together with my coauthors [C3/J8] we have argued for the need to design clean-slate mechanisms for transporting data that view congestion and rate allocation as a neighborhood, not a single link affair. Specifically, we have designed, analyzed, and implemented a practical, fully distributed congestion and rate control scheme that assigns fair and efficient rates to flows traversing multi-hop networks with tree-like topologies. This work has appeared at ACM Sigcomm [C3]. In some recent work of ours, we have revisited the problem of neighborhood-centric congestion and rate control for multi-hop networks with the goal of addressing the problem for arbitrary mesh topologies and relating the new designs to fundamental transport approaches and principles. This work is accepted to appear at ACM MobiCom [C0].
Even with the best rate allocation scheme, one cannot exceed the performance limits imposed by interference and scheduling inefficiencies. An important open problem in the research community has been to characterize the fundamental performance limits of today's de facto standard random access scheduler, IEEE 802.11, in a multi-hop setting. Together with my coauthor [J19, C28] we have introduced an analytical methodology that gives a formal answer to this problem. Interestingly, under commonly used topologies the performance loss of 802.11 over perfect schedulers is surprisingly low. This work is accepted to appear, pending minor revision, at IEEE/ACM Transactions on Networking.
I have recently presented parts of this work at a workshop on the future of TCP, and more general, on the design of transport protocols for a future Internet held at Stanford University and sponsored by Cisco Systems, and I have received the "Best and Most Compelling Presentation and Demonstration Award". Further, Cisco Systems is funding this work through its university research program. Finally, I have recently won a National Science Foundation grant to continue and expand my work in this area.
Ongoing research and future directions: Improving the performance of mesh networks requires a joint effort at the scheduling and the rate control layer. As previously mentioned, optimal schedulers are very hard to implement. With this in mind, one possible direction is to restrict the design space to the use of the de facto standard scheduler, 802.11, and attempt to design optimal rate controllers. Such rate controllers may need to be aware of and react to wireless contention, in order to compensate for the scheduling inefficiencies introduced by random access. Another direction is to design provably near-optimal schedulers that are easier to implement than optimal ones. One approach to achieve this may be via intelligent network partitioning, that allows to independently compute optimal schedules within each (small) partition and combine them without much performance loss. I am actively pursuing both directions of research.
In collaboration with my co-authors [J3, J5, J11, J14/C23, C12, C15, C17, C22, C24, C29] we have shown via both theory and simulations that the performance of a large network can be successfully predicted by studying a carefully constructed small replica. Specifically, we have shown that a slower network-replica fed with a small sample of the original traffic can have nearly identical properties with the original network. This work has been published in IEEE/ACM Transactions on Networking [J11]. More recently, we have successfully downscaled the topology of Internet-like networks to accurately predict a variety of performance metrics using the smaller network-replica, and we have provided methodologies to efficiently construct such miniature topologies. Parts of this work have been published at IEEE Journal on Selected Areas in Communications [J5] and ACM Computer Communication Review [J3].
Ongoing research and future directions: The proposed downscaling methods aim to predict performance metrics of interest, like end-to-end flow delays, queueing delays, distributions of active flows going through a link, etc. However, they operate on miniature network topologies whose graph structure is not necessarily similar to the original one, and, as a result, they fall short in predicting phenomena that depend on the graph structure, e.g. routing table fluctuations. I plan to explore how to downscale a network while preserving both performance metrics of interest and the topological structure.
I will mention here a couple. Together with my coauthor [J7, C7, C10] we have created a parsimonious model for spatially correlated sensor networks data. This model can be used to synthetically generate traces and to analyze aggregation and other techniques that exploit data correlation. The model is a special case of Markov random fields and is similar in flavor to another model that I (and my coauthors) have proposed in the past to capture temporal correlation in web traces [J13].
Second, together with my coauthors [J4/C1, J6, J9/C5, J20] we have proposed an efficient algorithm for resource sharing in peer-to-peer networks based on the idea that offering uploads brings revenue to a node, and performing downloads has a cost. We also introduced an analytical model that predicts the performance of Gnutella-like and BitTorrent-like systems with high accuracy.
Finally, together with my coauthors [J10] we have introduced a simple yet accurate model for a central-queue with multiple servers assuming Poisson arrivals and general service times (M/G/K queue) that, as opposed to prior models, remains accurate when the service distribution is heavy-tailed. Our motivation has been the heavy-tailed nature of Internet flow sizes, web pages and computer files which causes standard scheduling policies to have a large average response time, a problem that can be addressed by a simple central-queue with enough servers.