@inproceedings{Paek05,
title = {A Wireless Sensor Network for Structural Health Monitoring:
Performance and Experience},
author = {Jeongyeup Paek and Krishna Chintalapudi and John Cafferey and Ramesh Govindan and Sami Masri},
year = {2005},
date = {2005-05-01},
booktitle = {Proceedings of the Second IEEE Workshop on Embedded Networked Sensors (EmNetS-II),},
address = {Syndney, Australia},
abstract = {While sensor network research has made significant
strides in the past few years, the literature has relatively
few examples of papers that have evaluated and
validated a complete experimental system. In this paper
we discuss our deployment experiences and evaluate
the performance of a multi-hop wireless data acquisition
system (called Wisden) for structural health monitoring
(SHM) on a large seismic test structure used by civil
engineers. Our experiments indicate that, with the latest
sensor network hardware, Wisden can reliably deliver
time-synchronized tri-axial structural vibration data reliably
across multiple hops with low latencies for sampling
rates up to 200Hz. This performance was achieved by iteratively
refining the system design using a series of test deployments.
Our experiences suggested the need for careful
onset detection in order to preserve the fidelity of the structures
frequency response. Furthermore, the high damping
characteristics of large structures motivated an exploration
of the processing, sampling, and communication
limits of current platforms.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Gnawali05a,
title = {Data Centric, Position-Based Routing In Space Networks},
author = {Omprakash Gnawali and Mike Polyakov and Prasanta Bose and Ramesh Govindan},
year = {2005},
date = {2005-03-01},
booktitle = {Proceedings of the 26th IEEE Aerospace Conference},
address = {Big Sky, MT},
abstract = {Envisioned space exploration systems and planned space science
missions involve increasingly large number of satellites and surface
rovers/sensors communicating for coordinated science operations or for
on-demand commanding and/or transfer of data. Current approaches that
use static routing cannot scale to large numbers of satellites
and spacecrafts of future missions. This requires a dynamic approach
that can discover networks and links as they become available and
intelligently use them for routing. Furthermore, most of the science
missions will be geared towards collecting data using various
sensors. Adoption of a data-centric communication mechanism can enable
in-network aggregation and processing which help make data forwarding
more efficient. In this paper, we briefly describe ASCoT, a routing
system for science missions of tomorrow, which a) leverages the
predictability of satellite trajectories to effect position-based
routing in the space backbone, and b) departs from traditional
address-centric communication and uses a data-centric architecture to
enable energy efficient and low latency operation in proximity
networks. Our simulation study using STK/OPNET shows that ASCoT
architecture is viable.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{kairos-poster,
title = {Kairos: a macro-programming system for wireless sensor networks (Poster)},
author = {Ramakrishna Gummadi and Nupur Kothari and Ramesh Govindan and Todd Millstein},
year = {2005},
date = {2005-01-01},
booktitle = {SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{zhang05FPBFE,
title = {Fast Payload-Based Flow Estimation for Traffic
Monitoring and Network Security},
author = {Lakshman T V Fang Hao Muralidharan S. Kodialam and Hui Zhang},
year = {2005},
date = {2005-01-01},
booktitle = {Proc. ANCS.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{zhang05Fast,
title = {Fast, Memory-Efficient Traffic Estimation by Coincidence Counting},
author = {Lakshman T V Fang Hao Muralidharan S. Kodialam and Hui Zhang},
year = {2005},
date = {2005-01-01},
booktitle = {Proc. IEEE Infocom.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Gummadi05e,
title = {Practical Routing-Layer Support for Scalable Multihoming},
author = {Ramakrishna Gummadi and Ramesh Govindan},
year = {2005},
date = {2005-01-01},
booktitle = {Proceedings of IEEE Infocom - The Conference on Computer Communications},
address = {Miami, FL},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Xu04,
title = {A Wireless Sensor Network for Structural Monitoring},
author = {Ning Xu and Sumit Rangwala and Krishna Kant Chintalapudi and Deepak Ganesan and Alan Broad and Ramesh Govindan and Deborah Estrin},
doi = {http://doi.acm.org/10.1145/1031495.1031498},
isbn = {1-58113-879-2},
year = {2004},
date = {2004-11-01},
booktitle = {Proceedings of the ACM Conference on Embedded Networked Sensor Systems},
pages = {13--24},
publisher = {ACM Press},
address = {Baltimore, MD},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Gnawali04,
title = {Interaction of Retransmission, Blacklisting,
and Routing Metrics for Reliability in Sensor Network Routing},
author = {Omprakash Gnawali and Mark Yarvis and John Heidemann and Ramesh Govindan},
year = {2004},
date = {2004-10-01},
booktitle = {Proceedings of The First International Conference on Sensor and Ad Hoc
Communications and Networks (SECON)},
address = {Santa Clara, CA},
abstract = {Unpredictable and heterogeneous links in a wireless sensor network
require techniques to avoid low delivery rate and high delivery cost.
Three commonly used techniques to help discover high quality paths
include (1) link-layer retransmission, (2) blacklisting bad links, and
(3) end-to-end routing metrics. Using simulation and testbed
experiments, we present the first systematic exploration of the
tradeoffs of combinations of these approaches, quantifying the effects
of each of these three techniques. We identify several key results:
One is that per-hop retransmissions (ARQ) is a necessary addition to
any other mechanism if reliable data delivery is a goal. Additional
interactions between the services are more subtle. First, in a
multi-hop network, either blacklisting or reliability metrics like ETX
can provide consistent high-reliability paths when added to ARQ.
Second, at higher deployment densities, blacklisting has a lower
routing overhead than ETX. But at lower densities, blacklisting
becomes less stable as the network partitions. These results are
consistent across both simulation and testbed experiments. We
conclude that ETX with retransmissions is the best choice in general,
but that blacklisting may be worth considering at higher densities,
either with or without ETX.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Zhang04d,
title = {Making Eigenvector-Based Reputation Systems Robust to Collusions},
author = {H Zhang and A Goel and R Govindan and K Mason and Van B Roy},
year = {2004},
date = {2004-10-01},
booktitle = {Proceedings of the Third Workshop on Algorithms and Models for the Web Graph},
address = {Rome, Italy},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Chang04a,
title = {Exploring the Ability of Locating BGP Missing Routes from Multiple Looking Glasses},
author = {D -F Chang and R Govindan and J Heidemann},
year = {2004},
date = {2004-09-01},
booktitle = {First ACM Workshop on Network Troubleshooting},
address = {Portland, OR},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Corr04,
title = {The Impact of Spatial Correlation on Routing with Compression in Wireless Sensor Networks},
author = {S Pattem and B Krishnamachari and R Govindan},
year = {2004},
date = {2004-04-01},
booktitle = {Proceedings of the Third IEEE International Workshop on Information Processing in Sensor Networks},
address = {Berkeley, CA},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Geo04,
title = {On The Effect of Localization Errors on Geographic Face Routing on Sensor Networks},
author = {K Seada and A Helmy and R Govindan},
year = {2004},
date = {2004-04-01},
booktitle = {Proceedings of the Third IEEE International Workshop on Information Processing in Sensor Networks},
address = {Berkeley, CA},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{RangeBearing04,
title = {Localization Using Ranging and Sectoring},
author = {K Chintalapudi and A Dhariwal and R Govindan and G Sukhatme},
year = {2004},
date = {2004-03-01},
booktitle = {Proceedings of the IEEE Infocom},
address = {Hong Kong},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Gummadi04,
title = {Reduced State Routing in the Internet},
author = {Ramakrishna Gummadi and Nupur Kothari and Young-Jin Kim and Ramesh Govindan and Brad Karp and Scott Shenker},
year = {2004},
date = {2004-01-01},
booktitle = {Proceedings of Hotnets-III},
address = {San Diego, CA},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Enachescu04,
title = {Scale-Free Aggregation in Sensor Networks},
author = {M Enachescu and A Goel and R Govindan and R Motwani},
year = {2004},
date = {2004-01-01},
booktitle = {Proceedings of First International Workshop on Algorithmic Aspects of Wireless Sensor Networks},
pages = {71--84},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Chang03,
title = {The Temporal and Topological Characteristics of BGP Path Changes},
author = {Di-Fa Chang and R Govindan and J Heidemann},
year = {2003},
date = {2003-11-01},
booktitle = {Proceedings of the IEEE International Conference on Network Protocols},
address = {Atlanta, GA},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Zhao03b,
title = {Understanding Packet Delivery Performance In Dense Wireless Sensor Networks},
author = {Jerry Zhao and R Govindan},
year = {2003},
date = {2003-11-01},
booktitle = {Proceedings of the ACM Conference on Embedded Networked Sensor Systems},
address = {Los Angeles, CA},
abstract = {Wireless sensor networks promise fine-grain monitoring
in a wide variety of environments. Many of these environments
(eg indoor environments or habitats) can be harsh for wireless
communication. From a networking perspective, the most basic
aspect of wireless communication is the packet delivery performance:
the spatio-temporal characteristics of packet loss, and its
environmental dependence. These factors will deeply impact
the performance of data acquisition from these networks.

In this paper, we report on a systematic medium-scale (up to sixty nodes)
measurement of packet delivery in three different environments:
an indoor office building, a habitat with moderate foliage, and
an open parking lot.
Our findings have interesting implications for the design and
evaluation of routing
and medium-access protocols for sensor networks.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{DIM,
title = {Multi-dimensional Range Queries in Sensor Networks},
author = {Xin Li and Young Jin Kim and Ramesh Govindan and Wei Hong},
year = {2003},
date = {2003-11-01},
booktitle = {Proceedings of the ACM Conference on Embedded Networked Sensor Systems},
address = {Los Angeles, CA},
abstract = {In many sensor networks, data or events are named by attributes.
Many of these attributes have scalar values,
so one natural way to query events of interest is
to use a emphmulti-dimensional range query.
An example %of such a range query is:
``List all events whose temperature lies between 50$^circ$
and 60$^circ$, and whose light levels lie between 10 and 15.''
Such queries are useful for correlating events occurring
within the network.

In this paper, we describe the design of a distributed index
that scalably supports multi-dimensional range queries.
Our emphdistributed index for multi-dimensional data (or DIM)
uses a novel geographic embedding of a classical index data structure,
and is built upon the GPSR geographic routing algorithm.
Our analysis reveals that, under reasonable assumptions
about query distributions, DIMs scale quite well with
network size (both insertion and query costs scale as
$O(sqrtN)$).
In detailed simulations, we show that in practice, the
insertion and query costs of other alternatives
are sometimes an order of magnitude more than the costs of DIMs,
even for moderately sized network.
Finally, experiments on a small scale testbed validate
the feasibility of DIMs.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Narayan03,
title = {On the Impact of Routing and Address Allocation on the Structure and Implementation of Routing Tables},
author = {H Narayan and R Govindan and G Varghese},
year = {2003},
date = {2003-08-01},
booktitle = {Proceedings of ACM SIGCOMM Symposium on Network Architectures and Protocols},
address = {Karlsruhe, Germany},
abstract = {The recent growth in the size of the routing table
has led to an
interest in quantitatively understanding both the causes (e.g.
multihoming) as well as the effects (e.g. impact on router lookup
implementations) of such routing table growth. In this paper, we
describe a new model called ARAM that defines the structure of routing
tables of any given size. Unlike simpler empirical models that work
backwards from effects (e.g. current prefix length distributions),
ARAM approximately models the causes of table growth (allocation by
registries, assignment by ISPs, multihoming and load balancing). We
show that ARAM models with high fidelity three abstract measures
(prefix distribution, prefix depth, and number of nodes in the tree)
of the shape of the prefix tree --- as validated against 20 snapshots
of backbone routing tables from 1997 to the present. We then use ARAM
for evaluating the scalability of IP lookup schemes, and studying
the effects of multihoming and load balancing on their scaling behavior.
Our results indicate that algorithmic solutions based on multibit
tries will provide more
prefixes per chip than TCAMs (as table sizes scale toward a million)
unless TCAMs can be engineered to use 8 transistors per cell.
By contrast, many of today's SRAM based TCAMs use 12-16 transistors per cell.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Gummadi03,
title = {The Impact of DHT Routing Geometry on Resilience and Proximity},
author = {Krishna P Gummadi and Ramakrishna Gummadi and Steven D Gribble and Sylvia Ratnasamy and Scott Shenker and Ion Stoica},
year = {2003},
date = {2003-08-01},
booktitle = {Proceedings of the ACM SIGCOMM Symposium on Network Architectures and Protocols},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Zhang03,
title = {Incrementally Improving the Lookup Latency of Distributed Hash Table Systems},
author = {H Zhang and A Goel and R Govindan},
year = {2003},
date = {2003-06-01},
booktitle = {Proceedings of ACM SIGMETRICS},
address = {San Diego, CA},
abstract = {Distributed hash table (DHT) systems are an important class
of peer-to-peer routing infrastructures. They enable
scalable wide-area storage and retrieval of information,
and will support the rapid development of a wide variety of
Internet-scale applications ranging from naming systems and
file systems to application-layer multicast. DHT systems
essentially build an overlay network, but a path on the
overlay between any two nodes can be significantly
different from the unicast path between those two nodes on
the underlying network. As such, the lookup latency in
these systems can be quite high and can adversely impact
the performance of applications built on top of such
systems.

In this paper, we discuss a random sampling technique that
incrementally improves lookup latency in DHT systems. Our
sampling can be implemented using information gleaned from
lookups traversing the overlay network. For this reason, we
call our approach em lookup-parasitic random sampling (LPRS).
LPRS is fast, incurs little network overhead, and requires
relatively few modifications to existing DHT systems.

For idealized versions of DHT systems like Chord, Tapestry
and Pastry, we analytically prove that LPRS can result in
lookup latencies proportional to the diameter of the
network, provided the underlying physical topology has a
power-law latency expansion. We then validate this analysis
by implementing LPRS in the Chord simulator. Our
simulations reveal that LPRS-Chord exhibits a qualitatively
better latency scaling behavior relative to unmodified
Chord.

Finally, we provide evidence which suggests that the
Internet router-level topology resembles power-law latency
expansion. This finding implies that LPRS has significant
practical applicability as a general latency reduction
technique for many DHT systems. This finding is also of
independent interest since it might inform the design of
latency-sensitive topology models for the Internet.},
note = {to appear},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Chintala03,
title = {Localized Edge Detection in Wireless Sensor Networks},
author = {K Chintalapudi and R Govindan},
year = {2003},
date = {2003-04-01},
booktitle = {Proceedings of the IEEE ICC Workshop on Sensor Network Protocols and Applications},
address = {Anchorage, AK},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Zhao03,
title = {Computing Aggregates for Monitoring Wireless Sensor Networks},
author = {Jerry Zhao and R Govindan and D Estrin},
year = {2003},
date = {2003-04-01},
booktitle = {Proceedings of the International Workshop on Sensor Net Protocols and Applications},
address = {Anchorage, AK},
abstract = {Wireless sensor networks involve very large numbers of small,
low-power, wireless devices. Given their unattended nature, and their
potential applications in harsh environments, we need a monitoring
infrastructure that indicates system failures and resource depletion.
In this paper, we briefly describe an architecture for sensor network
monitoring, then focus on one aspect of this architecture: continuously
computing aggregates (sum, average, count) of network properties
(loss rates, energy-levels etc., packet counts).
Our contributions are two-fold. First, we propose a novel tree construction
algorithm that enables energy-efficient computation of some classes
of aggregates. Second, we show through actual implementation
and experiments that wireless
communication artifacts in even relatively benign environments can
significantly impact the computation of these aggregate properties.
In some cases, without careful attention to detail, the relative error
in the computed aggregates can be as much as 50%. However, by carefully
discarding lossy and asymmetric links, we can improve accuracy
by an order of magnitude.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}

@inproceedings{Dutta03,
title = {The Design of A Distributed Rating Scheme for Peer-to-peer Systems},
author = {D Dutta and A Goel and R Govindan and H Zhang},
year = {2003},
date = {2003-01-01},
booktitle = {Proceedings of the Workshop on the Economics of Peer-to-Peer Systems},
address = {Berkeley, CA},
abstract = {There exist many successful examples of
on-line reputation (or rating) systems, such as on-line
markets and e-tailer ratings.
However, for peer-to-peer applications, an explicit ratings
subsystem has often been ignored in system design because of the
implicit assumption of trust and altruism among P2P users.
This assumption might be true (or might not matter) when a P2P network
is still in its infancy and is relatively small in size.
But the assumption might break down with increase in the
size and diversity of the P2P network.
In this paper, we discuss issues in the
design of rating schemes for P2P systems.
In keeping with the design philosophy of many of these system,
we consider the design of distributed rating systems.
As a case study, we illustrate two different approaches to
a distributed rating system aimed at tackling the free-rider
problem in P2P networks.
A key challenge in designing such rating schemes is to make
them collusion-proof: we discuss our efforts in this direction.},
note = {to appear},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}