2005 |
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. @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. @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. @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. @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. @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. @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). @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. @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). @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. @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. @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 = {} } |
2005 |
An empirical evaluation of internet latency expansion (Journal Article) SIGCOMM Comput. Commun. Rev., 35 (1), pp. 93–97, 2005. |
Energy-Efficient Data Organization and Query Processing in Sensor Networks (Journal Article) SIGBED Review, 2 (1), 2005. |
Fast, Memory-Efficient Traffic Estimation by Coincidence Counting (Inproceedings) Proc. IEEE Infocom., 2005. |
Practical Routing-Layer Support for Scalable Multihoming (Inproceedings) Proceedings of IEEE Infocom - The Conference on Computer Communications, Miami, FL, 2005. |
Using Hierarchical Location Names for Scalable Routing and Rendezvous in Wireless Sensor Networks (Journal Article) 2005. |
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. |
Advanced Indexing Techniques for Wide-Area Network Monitoring (Journal Article) 2005. |
Advanced Indexing Techniques for Wide-Area Network Monitoring (Technical Report) Computer Science Department, University of Southern California (05-847), 2005. |
Rebalancing Distributed Data Storage in Sensor Networks (Technical Report) Computer Science Department, University of Southern California (05-852), 2005. |
2004 |
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. |
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. |
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. |
Exploring the Ability of Locating BGP Missing Routes from Multiple Looking Glasses (Inproceedings) First ACM Workshop on Network Troubleshooting, Portland, OR, 2004. |
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. |
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. |
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. |
Localization Using Ranging and Sectoring (Inproceedings) Proceedings of the IEEE Infocom, Hong Kong, 2004. |
Using the small-world model to improve Freenet performance. (Journal Article) Computer Networks, 46 (4), pp. 555-574, 2004. |
Reduced State Routing in the Internet (Inproceedings) Proceedings of Hotnets-III, San Diego, CA, 2004. |
Improving Lookup Latency in Distributed Hash Table Systems using Random Sampling (Technical Report) Computer Science Department, University of Southern California (04-825), 2004. |
An Empirical Evaluation of Internet Latency Expansion (Technical Report) Computer Science Department, University of Southern California (04-822), 2004. |
Making Eigenvector-Based Reputation Systems Robust to Collusion (Technical Report) Computer Science Department, University of Southern California (04-817), 2004. |
Towards Capturing Representative AS-level Internet Topologies (Journal Article) Computer Networks, 44 (6), pp. 737–755, 2004. |
Scale-Free Aggregation in Sensor Networks (Inproceedings) Proceedings of First International Workshop on Algorithmic Aspects of Wireless Sensor Networks, pp. 71–84, 2004. |
Networking Support for Query Processing in Sensor Networks (Journal Article) Communications of the ACM, 47 (6), pp. 47–52, 2004. |
2003 |
The Temporal and Topological Characteristics of BGP Path Changes (Inproceedings) Proceedings of the IEEE International Conference on Network Protocols, Atlanta, GA, 2003. |
Understanding Packet Delivery Performance In Dense Wireless Sensor Networks (Inproceedings) Proceedings of the ACM Conference on Embedded Networked Sensor Systems, Los Angeles, CA, 2003. |
Multi-dimensional Range Queries in Sensor Networks (Inproceedings) Proceedings of the ACM Conference on Embedded Networked Sensor Systems, Los Angeles, CA, 2003. |
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. |
The Impact of DHT Routing Geometry on Resilience and Proximity (Inproceedings) Proceedings of the ACM SIGCOMM Symposium on Network Architectures and Protocols, 2003. |
Incrementally Improving the Lookup Latency of Distributed Hash Table Systems (Inproceedings) Proceedings of ACM SIGMETRICS, San Diego, CA, 2003, (to appear). |
Localized Edge Detection in Wireless Sensor Networks (Inproceedings) Proceedings of the IEEE ICC Workshop on Sensor Network Protocols and Applications, Anchorage, AK, 2003. |
Computing Aggregates for Monitoring Wireless Sensor Networks (Inproceedings) Proceedings of the International Workshop on Sensor Net Protocols and Applications, Anchorage, AK, 2003. |
Wireless Sensor Networks (Book Chapter) Znati, T; Sivalingam, K; Raghavendra, C S (Ed.): Chapter Data-Centric Storage in Sensor Networks, Kluwer Publishers, 2003. |
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). |
Localized Edge Detection in Sensor Fields (Journal Article) Ad-hoc Networks Journal, 2003. |
Data-Centric Storage in Sensornets with GHT, A Geographic Hash Table (Journal Article) ACM MONET, 2003. |
DIFS: A Distributed Index for Features In Sensor Networks (Journal Article) Ad-hoc Networks Journal, 2003. |
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. |
On The Feasibilty of Ad-Hoc Localization Systems (Technical Report) Computer Science Department, University of Southern California (03-796), 2003. |
2002 |
Energy-efficient Broadcast in Wireless Ad-hoc Networks: Lower bounds and Algorithms (Journal Article) pp. 149-166, 2002. |
0000 |
() 0000. |