Areas of interest: theory of distributed computing; distributed algorithms and data structures; analysis and design of communication algorithms for wireless, sensor, and optical networks; data directories for sensor networks; data streaming algorithms; algorithmic game theory.
Specific topics studied:
Oblivious Routing in Wireless Networks
Routing in Mobile Ad Hoc Networks
MAC Protocols for Wireless Sensor Networks
Data Directories for Mobile Objects
The task of any routing algorithm is to select paths for
packets in a communication network. Ideally, the paths should have small
stretch (ratio of chosen path to shortest path length) and small congestion
(number of overlapping paths), resulting to faster packet delivery and load
balanced networks. In oblivious routing, the paths are chosen independent from
each other according to some a priori probability distribution. Oblivious
algorithms are ideal for wireless sensor networks where global coordination
between the nodes is infeasible and load balancing is desirable.
It is known that with oblivious routing it is impossible to simultaneously minimize stretch and congestion in arbitrary networks. Thus, most of the known oblivious algorithms focus on minimizing only the congestion while ignoring the stretch, resulting to very long paths. We show that for interesting classes of network topologies it is possible to simultaneously minimize the stretch and congestion. Such topologies are grids, uniformly distributed disc graphs in the Euclidian plane, and other geometric networks. Publications:
·
Oblivious
Routing on Geometric Networks. [slides]
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2005.
·
Optimal
Oblivious Path Selection on the Mesh. [slides]
IEEE International Parallel & Distributed Processing Symposium (IPDPS),
2005.
In mobile ad hoc networks, there is no underlying network infrastructure. The primary consideration in these networks is to establish and maintain routing paths. Link reversal algorithms construct paths in mobile ad hoc networks by maintaining directed links toward the destination(s). Link reversal algorithms are highly distributed and able to tolerate dynamic network changes. A well known example of a link reversal algorithm is TORA. Since their introduction in 1981, link reversal algorithms have only been analyzed experimentally. Our research provides the first formal performance analysis of link reversal algorithms in terms of the time and work (energy) consumed until stabilization. This research demonstrates that it is feasible to analyze routing algorithms in mobile ad hoc networks. Publications:
·
Analysis
of Link Reversal Routing Algorithms. [slides]
Siam Journal on Computing, 2005.
·
Load
Balanced Link Reversal Routing in Mobile Wireless Ad Hoc Networks. [slides]
Asian International Mobile Computing Conference (AMOC), 2006.
Medium access control (MAC) protocols specify how network nodes access the communication medium. In a wireless sensor network, an important consideration is packet collisions which are caused when neighbor nodes transmit simultaneously. Packet collisions cause network performance degradation and excess energy consumption. Contention-based MAC protocols (i.e. 802.11), react to collisions dynamically. However, these protocols suffer from extensive collisions until they stabilize. Time division multiplexing (TDMA) offers an attractive alternative solution, where each node is assigned a particular time slot in a repeated time frame where the node is able to transmit without collisions. In our research, we provide novel distributed, local, and self-stabilizing TDMA MAC protocols, where the throughput is near-optimal and depends only on the size of the local neighborhood. Publication:
·
Contention-Free
MAC Protocols for Wireless Sensor Networks. [slides]
Conference on Distributed Computing (DISC), 2004.
All-optical networks are characterized by their inability to buffer packets in transit, since packets remain in the form of light until they are delivered, and light is hard to be stored. Motivated by optical networks, I study the fundamental question of whether the lack of buffers degrades the network performance. We showed the surprising result that the performance is slightly affected.
Direct scheduling represents the simplest bufferless packet delivery scenario. A packet travels on a path without any interruptions (we assume that the path is given). The only task is to compute the injection times of the packets in order to avoid packet collisions. I showed that it an NP-hard (and also hard to approximate) problem of computing the optimal injection times. However, we can obtain good approximations for interesting network topologies such as the tree, grid, butterfly, and hypercube. Publication:
·
Direct
Routing: Algorithms and Complexity. [slides]
Algorithmica, 2006.
The hardness of direct scheduling suggests that in order to
obtain optimal delivery times, in arbitrary topologies of bufferless
networks, the packets have to be deflected. In a deflection a packet can either
go backwards on its path, or follow an alternate path which could be close to
the original path. We showed the significant result that with deflections we
can achieve near-optimal delivery time in any network topology without using
buffers. Before that we demonstrated the result for particular network topologies.
Publications:
·
Universal
Bufferless Packet Switching. [slides]
Siam Journal on Computing, to appear.
·
Õ(Congestion + Dilation) Hot-Potato Routing on Leveled
Networks. [slides]
Theory of Computing Systems, 2004.
·
Efficient
Bufferless Routing on Leveled Networks. [slides]
International Conference on Parallel and Distributed Computing (EUROPAR), 2005.
·
Near-Optimal
Hot-Potato Routing on Trees. [slides]
International Conference on Parallel and Distributed Computing (EUROPAR), 2004.
The first bufferless algorithms
(introduced in 1964) where known as hot-potato algorithms (due to deflections)
where the packets did not have pre-selected paths, but rather greedily followed
any path that could bring them closer to the destinations. Hot-potato
algorithms are interesting because they tend to be simple with efficient
hardware implementations. In our research, we give the first greedy hot-potato
algorithms for grid network topologies with near-optimal delivery time for the
packets. Publications:
·
Hard-Potato
Routing. [slides]
ACM Symposium on Theory of Computing (STOC), 2000.
·
Randomized
Greedy Hot-Potato Routing. [slides]
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000.
·
Routing
without Flow Control. [slides]
ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2001.
We consider a network congestion game in networks, where the strategy set of each player is a set of paths in the network, and each player selects a path which minimizes the maximum congestion (path overlaps) of its chosen path. The social cost is the maximum edge congestion along all chosen paths. We study the quality of Nash equilibrium in such problems. This game is interesting because the social cost represents the time that a scheduler needs to deliver all the packets along the chosen paths. Our work is the first to study such network games. Publication:
·
Atomic
Routing Games on Maximum Congestion. [slides]
International Conference on
Algorithmic Aspects in Information and Management (AAIM), 2006.
We have also studied the cake-cutting problem where different users wish to share a resource (i.e. the cake) in way that each user is satisfied according to its own evaluation function. The best known cake-cutting algorithms use O(n log n) cuts for n users. An open question is if this number of cuts optimal. In our research, we proved that indeed so many cuts are necessary for general classes of cake-cutting algorithms. Publication:
·
Cake-Cutting
is Not a Piece of Cake. [slides]
International Symposium on Theoretical Aspects of Computer Science (STACS),
2003.
There are many distributed computing applications that produce enormous quantities of data in the form of streams, for example sensor network applications. It is necessary to compute aggregates and statistics at a sink node using very small space and time. In most cases, we are only interested in a recent sliding time window of the data. All the previously known algorithms consider the synchronous model where data arrive at the sink in the same order it was generated. However, networks are usually asynchronous and cannot provide time delivery guarantees. In our research, we give the first data streaming algorithms for a recent time window of data that arrive asynchronously. We compute important statistics such as average, sum, and median using only poly-logarithmic space and time. Publications:
·
Sketching
Asynchronous Streams Over a Sliding Window. [slides]
ACM SIGACT-SIGOPS Symposium on
Principles of Distributed Computing (PODC), 2006.
·
A
Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding
Window.
International Symposium on Theoretical Aspects of Computer Science (STACS),
2007.
Wireless sensor networks are often used in monitoring applications where sensors track objects that appear in their observation range. The sensors keep track of the objects by storing observation data. In pull query systems, the queries about the objects are forwarded to the nodes which observed the objects. A directory is a distributed data structure which organizes the observed data in a way that queries are answered efficiently. The directories are updated when the objects move around. Sparse covers are data structures which are used to build efficient data directories for mobile objects. In my work, I give the first optimal sparse cover construction for planar graphs, which is an interesting class of graphs that represents spanners of wireless sensor networks. The work appears in:
·
Improved Sparse Covers for
Graphs Excluding a Fixed Minor.
Technical Report, Rensselaer
Polytechnic Institute, 2006.
In distributed multiprocessor systems often arise distributed coordination problems such as distributed counting, distributed stacks, load balancing, and barrier synchronization. Simple centralized solutions to these problems (i.e. a shared memory variable) suffer from sequential bottlenecks. Counting networks are highly distributed data structures which solve these problems efficiently without sequential bottlenecks. Counting networks are built from balancers interconnected in a directed graph. Their structure is similar to sorting networks. They have a particular set of input wires and output wires which is the width. We systematically study tradeoffs in the structure of counting networks relating the widths of the balancers used to the total width of the counting network.
·
A
Combinatorial Treatment of Balancing Networks.
Journal of the ACM, 1996.
·
Impossibility Results for Weak Threshold
Networks.
Information Processing Letters, 1997.
We give new counting network constructions with improved
structural characteristics. In particular we provide small-depth counting
network constructions with arbitrary output widths. We also give constructions
with different input and output widths that improve on the contention.
Representative Publications:
·
Sorting
and Counting Networks of Arbitrary Width and Small Depth.
Theory of Computing Systems, 2002.
·
An
Efficient Counting Network. [slides]
Merged International Parallel Processing Symposium and Symposium on Parallel
and Distributed Processing (IPPS/SPDP), 1998.
Counting networks naturally solve the distributed counting problem, when each operation is a mathematical increment. We showed that counting networks can be extended to implement decrement operations too. Publications:
·
Supporting
Increment and Decrement Operations in Balancing Networks. [slides]
Chicago Journal of Theoretical Computer Science, 2000.
·
A
Combinatorial Characterization of Properties Preserved by Antitokens.
International Conference on Parallel
Processing (EUROPAR), 2000.
·
Threshold
Counters with Increments and Decrements.
Theoretical Computer Science, 2002.
A more general question is if we can extend counting
networks to perform arbitrary mathematical operations such as multiplication,
division, etc. We showed that such operations require linearizable
executions where the time order of operations reflects the final result. This
is a significant constraint on any distributed data structure that implements
such operations. For example, any counting network should have infinite size to
implement general mathematical operations. Publications:
·
The
Cost of Concurrent, Low-Contention Read&Modify&Write.
Theoretical Computer Science, 2005.
·
Monotone
Operations and Monotone Groups.
International Conference on Algebraic Informatics, 2005.
In a related topic, we examine the difference in the computation cost between distributed queuing and counting:
·
Concurrent
Counting is Harder than Queuing. [slides]
IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.