2005
|
Gummadi, Ramakrishna; Kothari, Nupur; Govindan, Ramesh; Millstein, Todd Kairos: a macro-programming system for wireless sensor networks (Poster) (Inproceedings) SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles, 2005. (BibTeX) @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}
}
|
Kodialam, Lakshman Fang Hao Muralidharan T V S; Zhang, Hui Fast Payload-Based Flow Estimation for Traffic
Monitoring and Network Security (Inproceedings) Proc. ANCS., 2005. (BibTeX) @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}
}
|
Zhang, Hui; Goel, Ashish; Govindan, Ramesh An empirical evaluation of internet latency expansion (Journal Article) SIGCOMM Comput. Commun. Rev., 35 (1), pp. 93–97, 2005. (BibTeX) @article{zhang05b,
title = {An empirical evaluation of internet latency expansion},
author = {Hui Zhang and Ashish Goel and Ramesh Govindan},
year = {2005},
date = {2005-01-01},
journal = {SIGCOMM Comput. Commun. Rev.},
volume = {35},
number = {1},
pages = {93--97},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Gummadi, Ramakrishna; Li, Xin; Govindan, Ramesh; Shahabi, Cyrus; Hong, Wei Energy-Efficient Data Organization and Query Processing in Sensor Networks (Journal Article) SIGBED Review, 2 (1), 2005. (BibTeX) @article{gummadi05d,
title = {Energy-Efficient Data Organization and Query Processing in Sensor Networks},
author = {Ramakrishna Gummadi and Xin Li and Ramesh Govindan and Cyrus Shahabi and Wei Hong},
year = {2005},
date = {2005-01-01},
journal = {SIGBED Review},
volume = {2},
number = {1},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Kodialam, Lakshman Fang Hao Muralidharan T V S; Zhang, Hui Fast, Memory-Efficient Traffic Estimation by Coincidence Counting (Inproceedings) Proc. IEEE Infocom., 2005. (BibTeX) @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}
}
|
Gummadi, Ramakrishna; Govindan, Ramesh Practical Routing-Layer Support for Scalable Multihoming (Inproceedings) Proceedings of IEEE Infocom - The Conference on Computer Communications, Miami, FL, 2005. (BibTeX) @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}
}
|
Bian, Fang; Li, Xin; Govindan, Ramesh; Shenker, Scott Using Hierarchical Location Names for Scalable Routing and Rendezvous in Wireless Sensor Networks (Journal Article) 2005. (BibTeX) @article{Fang05,
title = {Using Hierarchical Location Names for Scalable Routing and Rendezvous in Wireless Sensor Networks},
author = {Fang Bian and Xin Li and Ramesh Govindan and Scott Shenker},
year = {2005},
date = {2005-01-01},
booktitle = {International Journal of Ad Hoc and Ubiquitous Computing, special issue on wireless sensor networks},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Bian, Fang; Li, Xin; Govindan, Ramesh; Shenker, Scott Using Hierarchical Location Names for Scalable Routing and Rendezvous in Wireless Sensor Networks (Technical Report) Computer Science Department, University of Southern California (05-841), 2005. (BibTeX) @techreport{Fang05b,
title = {Using Hierarchical Location Names for Scalable Routing and Rendezvous in Wireless Sensor Networks},
author = {Fang Bian and Xin Li and Ramesh Govindan and Scott Shenker},
year = {2005},
date = {2005-01-01},
number = {05-841},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
Li, Xin; Bian, Fang; Zhang, Hui; Diot, Christophe; Govindan, Ramesh; Hong, Wei; Iannaccone, Gianluca Advanced Indexing Techniques for Wide-Area Network Monitoring (Journal Article) 2005. (BibTeX) @article{NetDB05,
title = {Advanced Indexing Techniques for Wide-Area Network Monitoring},
author = {Xin Li and Fang Bian and Hui Zhang and Christophe Diot and Ramesh Govindan and Wei Hong and Gianluca Iannaccone},
year = {2005},
date = {2005-01-01},
booktitle = {1st IEEE International Workshop on Networking Meets Databases (NetDB)},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Li, Xin; Bian, Fang; Zhang, Hui; Diot, Christophe; Govindan, Ramesh; Hong, Wei; Iannaccone, Gianluca Advanced Indexing Techniques for Wide-Area Network Monitoring (Technical Report) Computer Science Department, University of Southern California (05-847), 2005. (BibTeX) @techreport{MINDTR,
title = {Advanced Indexing Techniques for Wide-Area Network Monitoring},
author = {Xin Li and Fang Bian and Hui Zhang and Christophe Diot and Ramesh Govindan and Wei Hong and Gianluca Iannaccone},
year = {2005},
date = {2005-01-01},
number = {05-847},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
Li, Xin; Bian, Fang; Govindan, Ramesh; Hong, Wei Rebalancing Distributed Data Storage in Sensor Networks (Technical Report) Computer Science Department, University of Southern California (05-852), 2005. (BibTeX) @techreport{DIMRebalance,
title = {Rebalancing Distributed Data Storage in Sensor Networks},
author = {Xin Li and Fang Bian and Ramesh Govindan and Wei Hong},
year = {2005},
date = {2005-01-01},
number = {05-852},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
2004
|
Xu, Ning; Rangwala, Sumit; Chintalapudi, Krishna Kant; Ganesan, Deepak; Broad, Alan; Govindan, Ramesh; Estrin, Deborah A Wireless Sensor Network for Structural Monitoring (Inproceedings) Proceedings of the ACM Conference on Embedded Networked Sensor Systems, pp. 13–24, ACM Press, Baltimore, MD, 2004, ISBN: 1-58113-879-2. (Links | BibTeX) @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}
}
|
Gnawali, Omprakash; Yarvis, Mark; Heidemann, John; Govindan, Ramesh Interaction of Retransmission, Blacklisting,
and Routing Metrics for Reliability in Sensor Network Routing (Inproceedings) Proceedings of The First International Conference on Sensor and Ad Hoc
Communications and Networks (SECON), Santa Clara, CA, 2004. (Abstract | BibTeX) @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}
}
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. |
Zhang, H; Goel, A; Govindan, R; Mason, K; Roy, Van B Making Eigenvector-Based Reputation Systems Robust to Collusions (Inproceedings) Proceedings of the Third Workshop on Algorithms and Models for the Web Graph, Rome, Italy, 2004. (BibTeX) @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}
}
|
Chang, D -F; Govindan, R; Heidemann, J Exploring the Ability of Locating BGP Missing Routes from Multiple Looking Glasses (Inproceedings) First ACM Workshop on Network Troubleshooting, Portland, OR, 2004. (BibTeX) @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}
}
|
Radoslavov, P; Papadopoulos, C; Govindan, R; Estrin, D A Comparison of Application-Level and Router-Assisted Schemes for Reliable Multicast (Journal Article) ACM/IEEE Transactions on Networking, 12 (4), pp. 456–468, 2004. (BibTeX) @article{Radoslavov04,
title = {A Comparison of Application-Level and Router-Assisted Schemes for Reliable Multicast},
author = {P Radoslavov and C Papadopoulos and R Govindan and D Estrin},
year = {2004},
date = {2004-06-01},
journal = {ACM/IEEE Transactions on Networking},
volume = {12},
number = {4},
pages = {456--468},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Pattem, S; Krishnamachari, B; Govindan, R The Impact of Spatial Correlation on Routing with Compression in Wireless Sensor Networks (Inproceedings) Proceedings of the Third IEEE International Workshop on Information Processing in Sensor Networks, Berkeley, CA, 2004. (BibTeX) @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}
}
|
Seada, K; Helmy, A; Govindan, R On The Effect of Localization Errors on Geographic Face Routing on Sensor Networks (Inproceedings) Proceedings of the Third IEEE International Workshop on Information Processing in Sensor Networks, Berkeley, CA, 2004. (BibTeX) @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}
}
|
Chintalapudi, K; Dhariwal, A; Govindan, R; Sukhatme, G Localization Using Ranging and Sectoring (Inproceedings) Proceedings of the IEEE Infocom, Hong Kong, 2004. (BibTeX) @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}
}
|
0002, Hui Zhang; Goel, Ashish; Govindan, Ramesh Using the small-world model to improve Freenet performance. (Journal Article) Computer Networks, 46 (4), pp. 555-574, 2004. (Links | BibTeX) @article{zhang04,
title = {Using the small-world model to improve Freenet performance.},
author = {Hui Zhang 0002 and Ashish Goel and Ramesh Govindan},
url = {http://authors.elsevier.com/sd/article/S1389128604001550},
year = {2004},
date = {2004-01-01},
journal = {Computer Networks},
volume = {46},
number = {4},
pages = {555-574},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Gummadi, Ramakrishna; Kothari, Nupur; Kim, Young-Jin; Govindan, Ramesh; Karp, Brad; Shenker, Scott Reduced State Routing in the Internet (Inproceedings) Proceedings of Hotnets-III, San Diego, CA, 2004. (BibTeX) @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}
}
|
Goel, Ashish; Govindan, Ramesh; Zhang, Hui Improving Lookup Latency in Distributed Hash
Table Systems using Random Sampling (Technical Report) Computer Science Department, University of Southern California (04-825), 2004. (BibTeX) @techreport{Goel04,
title = {Improving Lookup Latency in Distributed Hash
Table Systems using Random Sampling},
author = {Ashish Goel and Ramesh Govindan and Hui Zhang},
year = {2004},
date = {2004-01-01},
number = {04-825},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
Zhang, Hui; Goel, Ashish; Govindan, Ramesh An Empirical Evaluation of Internet Latency Expansion (Technical Report) Computer Science Department, University of Southern California (04-822), 2004. (BibTeX) @techreport{Zhang04a,
title = {An Empirical Evaluation of Internet Latency Expansion},
author = {Hui Zhang and Ashish Goel and Ramesh Govindan},
year = {2004},
date = {2004-01-01},
number = {04-822},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
Zhang, Hui; Goel, Ashish; Govindan, Ramesh; Mason, Kahn; Roy, Benjamin Van Making Eigenvector-Based Reputation Systems Robust to Collusion (Technical Report) Computer Science Department, University of Southern California (04-817), 2004. (BibTeX) @techreport{Zhang04b,
title = { Making Eigenvector-Based Reputation Systems Robust to Collusion },
author = {Hui Zhang and Ashish Goel and Ramesh Govindan and Kahn Mason and Benjamin Van Roy},
year = {2004},
date = {2004-01-01},
number = {04-817},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
Chang, H; Govindan, R; Jamin, S; Shenker, S; Willinger, W Towards Capturing Representative AS-level Internet Topologies (Journal Article) Computer Networks, 44 (6), pp. 737–755, 2004. (BibTeX) @article{Chang04,
title = {Towards Capturing Representative AS-level Internet Topologies},
author = {H Chang and R Govindan and S Jamin and S Shenker and W Willinger},
year = {2004},
date = {2004-01-01},
journal = {Computer Networks},
volume = {44},
number = {6},
pages = {737--755},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Enachescu, M; Goel, A; Govindan, R; Motwani, R Scale-Free Aggregation in Sensor Networks (Inproceedings) Proceedings of First International Workshop on Algorithmic Aspects of Wireless Sensor Networks, pp. 71–84, 2004. (BibTeX) @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}
}
|
Woo, A; Madden, S; Govindan, R Networking Support for Query Processing in Sensor Networks (Journal Article) Communications of the ACM, 47 (6), pp. 47–52, 2004. (BibTeX) @article{Woo04,
title = {Networking Support for Query Processing in Sensor Networks},
author = {A Woo and S Madden and R Govindan},
year = {2004},
date = {2004-01-01},
journal = {Communications of the ACM},
volume = {47},
number = {6},
pages = {47--52},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
2003
|
Chang, Di-Fa; Govindan, R; Heidemann, J The Temporal and Topological Characteristics of BGP Path Changes (Inproceedings) Proceedings of the IEEE International Conference on Network Protocols, Atlanta, GA, 2003. (BibTeX) @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}
}
|
Zhao, Jerry; Govindan, R Understanding Packet Delivery Performance In Dense Wireless Sensor Networks (Inproceedings) Proceedings of the ACM Conference on Embedded Networked Sensor Systems, Los Angeles, CA, 2003. (Abstract | BibTeX) @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}
}
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. |
Li, Xin; Kim, Young Jin; Govindan, Ramesh; Hong, Wei Multi-dimensional Range Queries in Sensor Networks (Inproceedings) Proceedings of the ACM Conference on Embedded Networked Sensor Systems, Los Angeles, CA, 2003. (Abstract | BibTeX) @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}
}
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. |
Narayan, H; Govindan, R; Varghese, G On the Impact of Routing and Address Allocation on the Structure and Implementation of Routing Tables (Inproceedings) Proceedings of ACM SIGCOMM Symposium on Network Architectures and Protocols, Karlsruhe, Germany, 2003. (Abstract | BibTeX) @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}
}
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. |
Gummadi, Krishna P; Gummadi, Ramakrishna; Gribble, Steven D; Ratnasamy, Sylvia; Shenker, Scott; Stoica, Ion The Impact of DHT Routing Geometry on Resilience and Proximity (Inproceedings) Proceedings of the ACM SIGCOMM Symposium on Network Architectures and Protocols, 2003. (BibTeX) @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}
}
|
Zhang, H; Goel, A; Govindan, R Incrementally Improving the Lookup Latency of Distributed Hash Table Systems (Inproceedings) Proceedings of ACM SIGMETRICS, San Diego, CA, 2003, (to appear). (Abstract | BibTeX) @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}
}
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. |
Chintalapudi, K; Govindan, R Localized Edge Detection in Wireless Sensor Networks (Inproceedings) Proceedings of the IEEE ICC Workshop on Sensor Network Protocols and Applications, Anchorage, AK, 2003. (BibTeX) @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}
}
|
Zhao, Jerry; Govindan, R; Estrin, D Computing Aggregates for Monitoring Wireless Sensor Networks (Inproceedings) Proceedings of the International Workshop on Sensor Net Protocols and Applications, Anchorage, AK, 2003. (Abstract | BibTeX) @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}
}
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. |
Govindan, R Wireless Sensor Networks (Book Chapter) Znati, T; Sivalingam, K; Raghavendra, C S (Ed.): Chapter Data-Centric Storage in Sensor Networks, Kluwer Publishers, 2003. (BibTeX) @inbook{DCSBookChapter,
title = {Wireless Sensor Networks},
author = {R Govindan},
editor = {T Znati and K Sivalingam and C S Raghavendra},
year = {2003},
date = {2003-01-01},
publisher = {Kluwer Publishers},
chapter = {Data-Centric Storage in Sensor Networks},
keywords = {},
pubstate = {published},
tppubtype = {inbook}
}
|
Dutta, D; Goel, A; Govindan, R; Zhang, H The Design of A Distributed Rating Scheme for Peer-to-peer Systems (Inproceedings) Proceedings of the Workshop on the Economics of Peer-to-Peer Systems, Berkeley, CA, 2003, (to appear). (Abstract | BibTeX) @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}
}
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. |
Chintalapudi, K; Govindan, R Localized Edge Detection in Sensor Fields (Journal Article) Ad-hoc Networks Journal, 2003. (Abstract | BibTeX) @article{Chintala03a,
title = {Localized Edge Detection in Sensor Fields},
author = {K Chintalapudi and R Govindan},
year = {2003},
date = {2003-01-01},
journal = {Ad-hoc Networks Journal},
abstract = {A wireless sensor network for detecting large-scale
phenomena (such as a contaminant flow or a seismic disturbance)
may be called upon to provide a description of the boundary
of the phenomenon (either a contour or some bounding box).
In such cases, it may be necessary for each node to locally
determine whether it lies at (or near) the edge of the
phenomenon. In this paper, we show that such localized edge
detection techniques are non-trivial to design in an
arbitrarily deployed sensor network.
We define the notion of an edge and develop performance
metrics for evaluating localized edge detection algorithms. We
propose three different approaches for localized edge detection and
present one example scheme for each. In all our approaches, each
sensor gathers information from its local neighborhood and
determines whether or not it is an edge sensor. We evaluate
the performance of each of the example schemes and compare them with
respect to the developed metrics.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
A wireless sensor network for detecting large-scale
phenomena (such as a contaminant flow or a seismic disturbance)
may be called upon to provide a description of the boundary
of the phenomenon (either a contour or some bounding box).
In such cases, it may be necessary for each node to locally
determine whether it lies at (or near) the edge of the
phenomenon. In this paper, we show that such localized edge
detection techniques are non-trivial to design in an
arbitrarily deployed sensor network.
We define the notion of an edge and develop performance
metrics for evaluating localized edge detection algorithms. We
propose three different approaches for localized edge detection and
present one example scheme for each. In all our approaches, each
sensor gathers information from its local neighborhood and
determines whether or not it is an edge sensor. We evaluate
the performance of each of the example schemes and compare them with
respect to the developed metrics. |
Ratnasamy, S; Karp, B; Shenker, S; Estrin, D; Govindan, R; Yin, L; Yu, F Data-Centric Storage in Sensornets with GHT, A Geographic Hash Table (Journal Article) ACM MONET, 2003. (BibTeX) @article{Ratnasamy03a,
title = {Data-Centric Storage in Sensornets with GHT, A Geographic Hash Table},
author = {S Ratnasamy and B Karp and S Shenker and D Estrin and R Govindan and L Yin and F Yu},
year = {2003},
date = {2003-01-01},
journal = {ACM MONET},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
Greenstein, B; Estrin, D; Govindan, R; Ratnasamy, S; Shenker, S DIFS: A Distributed Index for Features In Sensor Networks (Journal Article) Ad-hoc Networks Journal, 2003. (Abstract | BibTeX) @article{Greenstein03,
title = {DIFS: A Distributed Index for Features In Sensor Networks},
author = {B Greenstein and D Estrin and R Govindan and S Ratnasamy and S Shenker},
year = {2003},
date = {2003-01-01},
journal = {Ad-hoc Networks Journal},
abstract = {Sensor networks pose new challenges in the collection and distribution
of data. Recently, much attention has been focused on standing queries
that use in-network aggregation of time series data to return data
statistics in a communication-efficient manner. In this work, rather
than consider searches over time series data, we consider searches
over semantically rich high-level events, and present the design,
analysis, and numerical simulations of a spatially distributed index
that provides for efficient index construction and range searches. The
scheme provides for a more balanced sharing of communication load
over index nodes by using
the governing property that the wider the spatial extent known to an
index node, the more constrained is the value range covered by that
node.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Sensor networks pose new challenges in the collection and distribution
of data. Recently, much attention has been focused on standing queries
that use in-network aggregation of time series data to return data
statistics in a communication-efficient manner. In this work, rather
than consider searches over time series data, we consider searches
over semantically rich high-level events, and present the design,
analysis, and numerical simulations of a spatially distributed index
that provides for efficient index construction and range searches. The
scheme provides for a more balanced sharing of communication load
over index nodes by using
the governing property that the wider the spatial extent known to an
index node, the more constrained is the value range covered by that
node. |
Seada, K; Helmy, A; Govindan, R On the Effect of Localization Errors on Geographic Face Routing in Sensor Networks (Technical Report) Computer Science Department, University of Southern California (03-797), 2003. (BibTeX) @techreport{Seada03a,
title = {On the Effect of Localization Errors on Geographic Face Routing in Sensor Networks},
author = {K Seada and A Helmy and R Govindan},
year = {2003},
date = {2003-01-01},
number = {03-797},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
Chintalapudi, K K; Dhariwal, A; Govindan, R; Sukhatme, G On The Feasibilty of Ad-Hoc Localization Systems (Technical Report) Computer Science Department, University of Southern California (03-796), 2003. (BibTeX) @techreport{Chintala03c,
title = {On The Feasibilty of Ad-Hoc Localization Systems},
author = {K K Chintalapudi and A Dhariwal and R Govindan and G Sukhatme},
year = {2003},
date = {2003-01-01},
number = {03-796},
institution = {Computer Science Department, University of Southern California},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
|
2002
|
Bian, Fang; Raghavendra, C S; Goel, Ashish; Li, Xin Energy-efficient Broadcast in Wireless Ad-hoc Networks: Lower bounds and Algorithms (Journal Article) pp. 149-166, 2002. (BibTeX) @article{Fang02,
title = {Energy-efficient Broadcast in Wireless Ad-hoc Networks: Lower bounds and Algorithms},
author = {Fang Bian and C S Raghavendra and Ashish Goel and Xin Li},
year = {2002},
date = {2002-01-01},
booktitle = {Journal of Interconnection Networks, 3(3-4)},
pages = {149-166},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
|
0000
|
() 0000. (BibTeX) @{,
keywords = {},
pubstate = {published},
tppubtype = {}
}
|