BibTeX for papers by David Kotz; for complete/updated list see https://www.cs.dartmouth.edu/~kotz/research/papers.html @Article{newport:axioms, author = {Calvin Newport and David Kotz and Yougu Yuan and Robert S. Gray and Jason Liu and Chip Elliott}, title = {{Experimental Evaluation of Wireless Simulation Assumptions}}, journal = {SIMULATION: Transactions of The Society for Modeling and Simulation International}, year = 2007, month = {September}, volume = 83, number = 9, pages = {643--661}, publisher = {SAGE Publications}, copyright = {Simulation Councils}, DOI = {10.1177/0037549707085632}, URL = {https://www.cs.dartmouth.edu/~kotz/research/newport-axioms/index.html}, abstract = {All analytical and simulation research on ad hoc wireless networks must necessarily model radio propagation using simplifying assumptions. A growing body of research, however, indicates that the behavior of the protocol stack may depend significantly on these underlying assumptions. The standard response to this problem is a call for more realism in designing radio models. But how much realism is enough? This study is the first to approach this question by validating simulator performance (both at the physical and application layers) with the results of real-world data. Referencing an extensive set of measurements from a large outdoor routing experiment, we start by evaluating the relative realism of common assumptions made in radio model design, identifying those which provide a reasonable approximation of reality. Although several such investigations have been made for static sensor networks, radio behavior in mobile network deployments is a much less-studied topic. We then reproduce our experimental setup in our simulator, and generate the same application-layer metrics under progressively smaller sets of these assumptions. By comparing the simulated outcome to the outcome of our experiment, we are able to discern at what point our balance of simplification and realism captures the real behavior of our target environment.}, } @InProceedings{kumar:fbcast, author = {Rajnish Kumar and Arnab Paul and Umakishore Ramachandran and David Kotz}, title = {{On improving wireless broadcast reliability of sensor networks using erasure codes}}, booktitle = {{Proceedings of the International Conference on Mobile Ad-hoc and Sensor Networks (MSN)}}, series = {Lecture Notes in Computer Science}, year = 2006, month = {December}, volume = 4325, pages = {155--170}, publisher = {Springer-Verlag}, copyright = {Springer}, DOI = {10.1007/11943952_14}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kumar-fbcast/index.html}, abstract = {Efficient and reliable dissemination of information over a large area is a critical ability of a sensor network for various reasons such as software updates and transferring large data objects (e.g., surveillance images). Thus efficiency of wireless broadcast is an important aspect of sensor network deployment. In this paper, we study FBcast, a new broadcast protocol based on the principles of modern erasure codes. We show that our approach provides high reliability, often considered critical for disseminating codes. In addition FBcast offers limited data confidentiality. For a large network, where every node may not be reachable by the source, we extend FBcast with the idea of repeaters to improve reliable coverage. Simulation results on TOSSIM show that FBcast offers higher reliability with lower number of retransmissions than traditional broadcasts.}, } @Article{liu:jdirex, author = {Jason Liu and Yougu Yuan and David M. Nicol and Robert S. Gray and Calvin C. Newport and David Kotz and Luiz Felipe Perrone}, title = {{Empirical Validation of Wireless Models in Simulations of Ad Hoc Routing Protocols}}, journal = {Simulation: Transactions of The Society for Modeling and Simulation International}, year = 2005, month = {April}, volume = 81, number = 4, pages = {307--323}, publisher = {Sage Publications}, copyright = {Simulation Councils}, DOI = {10.1177/0037549705055017}, URL = {https://www.cs.dartmouth.edu/~kotz/research/liu-jdirex/index.html}, note = {``Best of PADS 2004'' special issue}, abstract = {Computer simulation has been used extensively as an effective tool in the design and evaluation of systems. One should not, however, underestimate the importance of validation--- the process of ensuring whether a simulation model is an appropriate representation of the real-world system. Validation of wireless network simulations is difficult due to strong interdependencies among protocols at different layers and uncertainty in the wireless environment. The authors present an approach of coupling direct-execution simulation and traces from real outdoor experiments to validating simple wireless models that are used commonly in simulations of wireless ad hoc networks. This article documents a common testbed that supports direct execution of a set of ad hoc routing protocol implementations in a wireless network simulator. By comparing routing behavior measured in the real experiment with behavior computed by the simulation, the authors validate the models of radio behavior upon which protocol behavior depends.}, } @MastersThesis{jiang:msthesis, author = {Zhenhui Jiang}, title = {{A Combined Routing Method for Ad hoc Wireless Networks}}, school = {Dartmouth College Computer Science}, year = 2005, month = {December}, copyright = {Zhenhui Jiang}, address = {Hanover, NH}, URL = {https://www.cs.dartmouth.edu/~kotz/research/jiang-msthesis/index.html}, note = {Available as Dartmouth Computer Science Technical Report TR2005-566}, abstract = {To make ad hoc wireless networks adaptive to different mobility and traffic patterns, we studied in this thesis an approach to swap from one protocol to another protocol dynamically, while routing continues. By the insertion of a new layer, we were able to make each node in the ad hoc wireless network notify each other about the protocol swap. To ensure that routing works efficiently after the protocol swap, we initialized the destination routing protocol's data structures and reused the previous routing information to build the new routing table. We also tested our approach under different network topologies and traffic patterns in static networks to learn whether the swap is fast and whether the swap incurs too much overload . We found that the swap latency is related to the destination protocol and the topology of the network. We also found that the control packet ratio after swap is close to the protocol running without swap, which means our method does not incur too many control packets for swap.}, } @TechReport{gray:compare-tr, author = {Robert S. Gray and David Kotz and Calvin Newport and Nikita Dubrovsky and Aaron Fiske and Jason Liu and Christopher Masone and Susan McGrath and Yougu Yuan}, title = {{Outdoor Experimental Comparison of Four Ad Hoc Routing Algorithms}}, institution = {Dartmouth Computer Science}, year = 2004, month = {June}, number = {TR2004-511}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/gray-compare-tr/index.html}, abstract = {Most comparisons of wireless ad hoc routing algorithms involve simulated or indoor trial runs, or outdoor runs with only a small number of nodes, potentially leading to an incorrect picture of algorithm performance. In this paper, we report on the results of an outdoor trial run of four different routing algorithms, APRL, AODV, GPSR, and STARA, running on top of thirty-three 802.11-enabled laptops moving randomly through an athletic field. The laptops generated random traffic according to the traffic patterns observed in a prototype application, and ran each routing algorithm for a fifteen-minute period over the course of the hour-long trial run. The 33-laptop experiment represents one of the largest outdoor tests of wireless routing algorithms, and three of the algorithms each come from a different algorithmic class, providing insight into the behavior of ad hoc routing algorithms at larger real-world scales than have been considered so far. In addition, we compare the outdoor results with both indoor (``tabletop'') and simulation results for the same algorithms, examining the differences between the indoor results and the outdoor reality. The paper also describes the software infrastructure that allowed us to implement the ad hoc routing algorithms in a comparable way, and use the same codebase for indoor, outdoor, and simulated trial runs.}, } @InProceedings{gray:compare, author = {Robert S. Gray and David Kotz and Calvin Newport and Nikita Dubrovsky and Aaron Fiske and Jason Liu and Christopher Masone and Susan McGrath and Yougu Yuan}, title = {{Outdoor Experimental Comparison of Four Ad Hoc Routing Algorithms}}, booktitle = {{Proceedings of the ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM)}}, year = 2004, month = {October}, pages = {220--229}, publisher = {ACM}, copyright = {ACM}, DOI = {10.1145/1023663.1023703}, URL = {https://www.cs.dartmouth.edu/~kotz/research/gray-compare/index.html}, abstract = {Most comparisons of wireless ad hoc routing algorithms involve simulated or \emph{indoor} trial runs, or outdoor runs with only a small number of nodes, potentially leading to an incorrect picture of algorithm performance. In this paper, we report on an outdoor comparison of four different routing algorithms, APRL, AODV, ODMRP, and STARA, running on top of thirty-three 802.11-enabled laptops moving randomly through an athletic field. This comparison provides insight into the behavior of ad hoc routing algorithms at larger real-world scales than have been considered so far. In addition, we compare the outdoor results with both indoor (``tabletop'') and simulation results for the same algorithms, examining the differences between the indoor results and the outdoor reality. Finally, we describe the software infrastructure that allowed us to implement the ad hoc routing algorithms in a comparable way, and use the \emph{same} codebase for indoor, outdoor, and simulated trial runs.}, } @TechReport{kotz:axioms-tr2, author = {David Kotz and Calvin Newport and Robert S. Gray and Jason Liu and Yougu Yuan and Chip Elliott}, title = {{Experimental evaluation of wireless simulation assumptions}}, institution = {Dartmouth Computer Science}, year = 2004, month = {June}, number = {TR2004-507}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-axioms-tr2/index.html}, abstract = {All analytical and simulation research on ad hoc wireless networks must necessarily model radio propagation using simplifying assumptions. Although it is tempting to assume that all radios have circular range, have perfect coverage in that range, and travel on a two-dimensional plane, most researchers are increasingly aware of the need to represent more realistic features, including hills, obstacles, link asymmetries, and unpredictable fading. Although many have noted the complexity of real radio propagation, and some have quantified the effect of overly simple assumptions on the simulation of ad hoc network protocols, we provide a comprehensive review of six assumptions that are still part of many ad hoc network simulation studies. In particular, we use an extensive set of measurements from a large outdoor routing experiment to demonstrate the weakness of these assumptions, and show how these assumptions cause simulation results to differ significantly from experimental results. We close with a series of recommendations for researchers, whether they develop protocols, analytic models, or simulators for ad hoc wireless networks.}, } @InProceedings{kotz:axioms, author = {David Kotz and Calvin Newport and Robert S. Gray and Jason Liu and Yougu Yuan and Chip Elliott}, title = {{Experimental Evaluation of Wireless Simulation Assumptions}}, booktitle = {{Proceedings of the ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM)}}, year = 2004, month = {October}, pages = {78--82}, publisher = {ACM}, copyright = {ACM}, DOI = {10.1145/1023663.1023679}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-axioms/index.html}, abstract = {All analytical and simulation research on ad hoc wireless networks must necessarily model radio propagation using simplifying assumptions. We provide a comprehensive review of six assumptions that are still part of many ad hoc network simulation studies, despite increasing awareness of the need to represent more realistic features, including hills, obstacles, link asymmetries, and unpredictable fading. We use an extensive set of measurements from a large outdoor routing experiment to demonstrate the weakness of these assumptions, and show how these assumptions cause simulation results to differ significantly from experimental results. We close with a series of recommendations for researchers, whether they develop protocols, analytic models, or simulators for ad hoc wireless networks.}, } @InProceedings{liu:direx, author = {Jason Liu and Yougu Yuan and David M. Nicol and Robert S. Gray and Calvin C. Newport and David Kotz and Luiz Felipe Perrone}, title = {{Simulation Validation Using Direct Execution of Wireless Ad-Hoc Routing Protocols}}, booktitle = {{Proceedings of the Workshop on Parallel and Distributed Simulation (PADS)}}, year = 2004, month = {May}, pages = {7--16}, publisher = {ACM}, copyright = {IEEE}, DOI = {10.1109/PADS.2004.1301280}, URL = {https://www.cs.dartmouth.edu/~kotz/research/liu-direx/index.html}, abstract = {Computer simulation is the most common approach to studying wireless ad-hoc routing algorithms. The results, however, are only as good as the models the simulation uses. One should not underestimate the importance of \emph{validation}, as inaccurate models can lead to wrong conclusions. In this paper, we use direct-execution simulation to validate radio models used by ad-hoc routing protocols, against real-world experiments. This paper documents a common testbed that supports direct execution of a set of ad-hoc routing protocol implementations in a wireless network simulator. The testbed reads traces generated from real experiments, and uses them to drive direct-execution implementations of the routing protocols. Doing so we reproduce the same network conditions as in real experiments. By comparing routing behavior \emph{measured} in real experiments with behavior \emph{computed} by the simulation, we are able to validate the models of radio behavior upon which protocol behavior depends. We conclude that it is \emph{possible} to have fairly accurate results using a simple radio model, but the routing behavior is quite sensitive to one of this model's parameters. The implication is that one should i) use a more complex radio model that explicitly models point-to-point path loss, or ii) use measurements from an environment typical of the one of interest, or iii) study behavior over a range of environments to identify sensitivities.}, } @TechReport{newport:thesis, author = {Calvin Newport}, title = {{Simulating mobile ad hoc networks: a quantitative evaluation of common MANET simulation models}}, institution = {Dartmouth Computer Science}, year = 2004, month = {June}, number = {TR2004-504}, copyright = {the author}, address = {Hanover, NH}, URL = {https://www.cs.dartmouth.edu/~kotz/research/newport-thesis/index.html}, note = {Available as Dartmouth Computer Science Technical Report TR2004-504}, abstract = {Because it is difficult and costly to conduct real-world mobile ad hoc network experiments, researchers commonly rely on computer simulation to evaluate their routing protocols. However, simulation is far from perfect. A growing number of studies indicate that simulated results can be dramatically affected by several sensitive simulation parameters. It is also commonly noted that most simulation models make simplifying assumptions about radio behavior. This situation casts doubt on the reliability and applicability of many ad hoc network simulation results. \par In this study, we begin with a large outdoor routing experiment testing the performance of four popular ad hoc algorithms (AODV, APRL, ODMRP, and STARA). We present a detailed comparative analysis of these four implementations. Then, using the outdoor results as a baseline of reality, we disprove a set of common assumptions used in simulation design, and quantify the impact of these assumptions on simulated results. We also more specifically validate a group of popular radio models with our real-world data, and explore the sensitivity of various simulation parameters in predicting accurate results. We close with a series of specific recommendations for simulation and ad hoc routing protocol designers.}, } @TechReport{kotz:axioms-tr, author = {David Kotz and Calvin Newport and Chip Elliott}, title = {{The mistaken axioms of wireless-network research}}, institution = {Dartmouth Computer Science}, year = 2003, month = {July}, number = {TR2003-467}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-axioms-tr/index.html}, abstract = {Most research on ad-hoc wireless networks makes simplifying assumptions about radio propagation. The ``Flat Earth'' model of the world is surprisingly popular: all radios have circular range, have perfect coverage in that range, and travel on a two-dimensional plane. CMU's ns-2 radio models are better but still fail to represent many aspects of realistic radio networks, including hills, obstacles, link asymmetries, and unpredictable fading. We briefly argue that key ``axioms'' of these types of propagation models lead to simulation results that do not adequately reflect real behavior of ad-hoc networks, and hence to network protocols that may not work well (or at all) in reality. We then present a set of 802.11 measurements that clearly demonstrate that these ``axioms'' are contrary to fact. The broad chasm between simulation and reality calls into question many of results from prior papers, and we summarize with a series of recommendations for researchers considering analytic or simulation models of wireless networks.}, }