BibTeX for papers by David Kotz; for complete/updated list see https://www.cs.dartmouth.edu/~kotz/research/papers.html @Article{kim:anomaly, author = {Minkyong Kim and David Kotz}, title = {{Identifying Unusual Days}}, journal = {Journal of Computing Science and Engineering (JCSE)}, year = 2011, month = {March}, volume = 5, number = 1, pages = {71--84}, publisher = {Korean Institute of Information Scientists and Engineers}, copyright = {KIISE}, DOI = {10.5626/JCSE.2011.5.1.071}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kim-anomaly/index.html}, abstract = {Pervasive applications such as digital memories or patient monitors collect a vast amount of data. One key challenge in these systems is how to extract interesting or unusual information. Because users cannot anticipate their future interests in the data when the data is stored, it is hard to provide appropriate indexes. As location-tracking technologies, such as global positioning system, have become ubiquitous, digital cameras or other pervasive systems record location information along with the data. In this paper, we present an automatic approach to identify unusual data using location information. Given the location information, our system identifies unusual days, that is, days with unusual mobility patterns. We evaluated our detection system using a real wireless trace, collected at wireless access points, and demonstrated its capabilities. Using our system, we were able to identify days when mobility patterns changed and differentiate days when a user followed a regular pattern from the rest. We also discovered general mobility characteristics. For example, most users had one or more repeating mobility patterns, and repeating mobility patterns did not depend on certain days of the week, except that weekends were different from weekdays.}, } @InCollection{song:chapter, author = {Libo Song and David F. Kotz}, title = {{Routing in Mobile Opportunistic Networks}}, booktitle = {{Mobile Opportunistic Networks}}, editor = {Mieso K. Denko}, year = 2011, chapter = 1, pages = {1--24}, publisher = {Taylor \& Francis}, copyright = {Taylor \& Francis}, ISBN13 = {978-1-4200-8813-7}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-chapter/index.html}, } @InProceedings{mare:models, author = {Shrirang Mare and David Kotz and Anurag Kumar}, title = {{Experimental Validation of Analytical Performance Models for IEEE 802.11 Networks}}, booktitle = {{Proceedings of the Workshop on WIreless Systems: Advanced Research and Development (WISARD)}}, year = 2010, month = {January}, pages = {1--8}, publisher = {IEEE}, copyright = {IEEE}, DOI = {10.1109/COMSNETS.2010.5431957}, URL = {https://www.cs.dartmouth.edu/~kotz/research/mare-models/index.html}, abstract = {We consider the simplest IEEE 802.11 WLAN networks for which analytical models are available and seek to provide an experimental validation of these models. Our experiments include the following cases: (i) two nodes with saturated queues, sending fixed-length UDP packets to each other, and (ii) a TCP-controlled transfer between two nodes. Our experiments are based entirely on Aruba AP-70 access points operating under Linux. We report our observations on certain non-standard behavior of the devices. In cases where the devices adhere to the standards, we find that the results from the analytical models estimate the experimental data with a mean error of 3-5\%.}, } @PhdThesis{song:thesis, author = {Libo Song}, title = {{Evaluating Mobility Predictors in Wireless Networks for Improving Handoff and Opportunistic Routing}}, school = {Dartmouth College Computer Science}, year = 2008, month = {January}, copyright = {Libo Song}, address = {Hanover, NH}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-thesis/index.html}, note = {Available as Dartmouth Computer Science Technical Report TR2008-611}, abstract = {We evaluate mobility predictors in wireless networks. Handoff prediction in wireless networks has long been considered as a mechanism to improve the quality of service provided to mobile wireless users. Most prior studies, however, were based on theoretical analysis, simulation with synthetic mobility models, or small wireless network traces. We study the effect of mobility prediction for a large realistic wireless situation. We tackle the problem by using traces collected from a large production wireless network to evaluate several major families of handoff-location prediction techniques, a set of handoff-time predictors, and a predictor that jointly predicts handoff location and time. We also propose a fallback mechanism, which uses a lower-order predictor whenever a higher-order predictor fails to predict. We found that low-order Markov predictors, with our proposed fallback mechanisms, performed as well or better than the more complex and more space-consuming compression-based handoff-location predictors. Although our handoff-time predictor had modest prediction accuracy, in the context of mobile voice applications we found that bandwidth reservation strategies can benefit from the combined location and time handoff predictor, significantly reducing the call-drop rate without significantly increasing the call-block rate. We also developed a prediction-based routing protocol for mobile opportunistic networks. We evaluated and compared our protocol's performance to five existing routing protocols, using simulations driven by real mobility traces. We found that the basic routing protocols are not practical for large-scale opportunistic networks. Prediction-based routing protocols trade off the message delivery ratio against resource usage and performed well and comparable to each other.}, } @Article{kim:jclassify, author = {Minkyong Kim and David Kotz}, title = {{Periodic properties of user mobility and access-point popularity}}, journal = {Journal of Personal and Ubiquitous Computing}, year = 2007, month = {August}, volume = 11, number = 6, pages = {465--479}, publisher = {Springer-Verlag}, copyright = {Springer London}, DOI = {10.1007/s00779-006-0093-4}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kim-jclassify/index.html}, note = {Invited paper; special issue of papers from LoCA 2005}, abstract = {Understanding user mobility and its effect on access points (APs) is important in designing location-aware systems and wireless networks. Although various studies of wireless networks have provided useful insights, it is hard to apply them to other situations. Here we present a general methodology for extracting mobility information from wireless network traces, and for classifying mobile users and APs. We used the Fourier transform to reveal important periods and chose the two strongest periods to serve as parameters to a classification system based on Bayes' theory. Analysis of 1-month traces shows that while a daily pattern is common among both users and APs, a weekly pattern is common only for APs. Analysis of 1-year traces revealed that both user mobility and AP popularity depend on the academic calendar. By plotting the classes of APs on our campus map, we discovered that their periodic behavior depends on their proximity to other APs.}, } @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{song:dtn, author = {Libo Song and David Kotz}, title = {{Evaluating Opportunistic Routing Protocols with Large Realistic Contact Traces}}, booktitle = {{Proceedings of the ACM MobiCom workshop on Challenged Networks (CHANTS 2007)}}, year = 2007, month = {September}, pages = {35--42}, publisher = {ACM}, copyright = {ACM}, DOI = {10.1145/1287791.1287799}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-dtn/index.html}, abstract = {Traditional mobile ad hoc network (MANET) routing protocols assume that contemporaneous end-to-end communication paths exist between data senders and receivers. In some mobile ad hoc networks with a sparse node population, an end-to-end communication path may break frequently or may not exist at any time. Many routing protocols have been proposed in the literature to address the problem, but few were evaluated in a realistic ``opportunistic'' network setting. We use simulation and contact traces (derived from logs in a production network) to evaluate and compare five existing protocols: direct-delivery, epidemic, random, PRoPHET, and Link-State, as well as our own proposed routing protocol. We show that the direct delivery and epidemic routing protocols suffer either low delivery ratio or high resource usage, and other protocols make tradeoffs between delivery ratio and resource usage.}, } @InProceedings{kim:mobility, author = {Minkyong Kim and David Kotz and Songkuk Kim}, title = {{Extracting a mobility model from real user traces}}, booktitle = {{Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)}}, year = 2006, month = {April}, pages = {1--12}, publisher = {IEEE}, copyright = {IEEE}, address = {Barcelona, Spain}, DOI = {10.1109/INFOCOM.2006.173}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kim-mobility/index.html}, abstract = {Understanding user mobility is critical for simulations of mobile devices in a wireless network, but current mobility models often do not reflect real user movements. In this paper, we provide a foundation for such work by exploring mobility characteristics in traces of mobile users. We present a method to estimate the physical location of users from a large trace of mobile devices associating with access points in a wireless network. Using this method, we extracted tracks of always-on Wi-Fi devices from a 13-month trace. We discovered that the speed and pause time each follow a log-normal distribution and that the direction of movements closely reflects the direction of roads and walkways. Based on the extracted mobility characteristics, we developed a mobility model, focusing on movements among popular regions. Our validation shows that synthetic tracks match real tracks with a median relative error of 17\%.}, } @InProceedings{kim:wardriving, author = {Minkyong Kim and Jeffrey J. Fielding and David Kotz}, title = {{Risks of using AP locations discovered through war driving}}, booktitle = {{Proceedings of the International Conference on Pervasive Computing (Pervasive)}}, series = {Lecture Notes in Computer Science}, year = 2006, month = {May}, volume = 3968, pages = {67--82}, publisher = {Springer-Verlag}, copyright = {Springer-Verlag}, address = {Dublin, Ireland}, DOI = {10.1007/11748625_5}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kim-wardriving/index.html}, abstract = {Many pervasive-computing applications depend on knowledge of user location. Because most current location-sensing techniques work only either indoors or outdoors, researchers have started using 802.11 beacon frames from access points (APs) to provide broader coverage. To use 802.11 beacons, they need to know AP locations. Because the actual locations are often unavailable, they use estimated locations from \emph{war driving}. But these estimated locations may be different from actual locations. In this paper, we analyzed the errors in these estimates and the effect of these errors on other applications that depend on them. We found that the estimated AP locations have a median error of 32 meters. We considered the error in tracking user positions both indoors and outdoors. Using actual AP locations, we could improve the accuracy as much as 70\% for indoors and 59\% for outdoors. We also analyzed the effect of using estimated AP locations in computing AP coverage range and estimating interference among APs. The coverage range appeared to be shorter and the interference appeared to be more severe than in reality.}, } @Article{song:jpredict, author = {Libo Song and David Kotz and Ravi Jain and Xiaoning He}, title = {{Evaluating next cell predictors with extensive Wi-Fi mobility data}}, journal = {IEEE Transactions on Mobile Computing}, year = 2006, month = {December}, volume = 5, number = 12, pages = {1633--1649}, publisher = {IEEE}, copyright = {IEEE}, DOI = {10.1109/TMC.2006.185}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-jpredict/index.html}, abstract = {Location is an important feature for many applications, and wireless networks can better serve their clients by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors, using a two-year trace of the mobility patterns of over 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. The surprising results provide critical evidence for anyone designing or using mobility predictors. \par We implemented and compared the prediction accuracy of several location predictors drawn from four major families of domain-independent predictors, namely Markov-based, compression-based, PPM, and SPM predictors. We found that low-order Markov predictors performed as well or better than the more complex and more space-consuming compression-based predictors.}, } @Article{song:reserv-poster, author = {Libo Song and Udayan Deshpande and Ula{\c{s}} C. Kozat and David Kotz and Ravi Jain}, title = {{MobiCom Poster Abstract: Bandwidth Reservation using WLAN Handoff Prediction}}, journal = {ACM SIGMOBILE Mobile Computing and Communication Review}, year = 2006, month = {October}, volume = 10, number = 4, pages = {22--23}, publisher = {ACM}, copyright = {ACM}, DOI = {10.1145/1215976.1215987}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-reserv-poster/index.html}, note = {Poster presented at Mobicom 2005}, abstract = {Many network services may be improved or enabled by successful predictions of users' future mobility. The success of predictions depend on how much accuracy can be achieved on real data and on the sensitivity of particular applications to this achievable accuracy. We investigate these issues for the case of advanced bandwidth reservation using real WLAN traces collected on the Dartmouth College campus.}, } @InProceedings{song:reserv, author = {Libo Song and Udayan Deshpande and Ula{\c{s}} C. Kozat and David Kotz and Ravi Jain}, title = {{Predictability of WLAN Mobility and its Effects on Bandwidth Provisioning}}, booktitle = {{Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)}}, year = 2006, month = {April}, pages = {1--13}, publisher = {IEEE}, copyright = {IEEE}, address = {Barcelona, Spain}, DOI = {10.1109/INFOCOM.2006.171}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-reserv/index.html}, abstract = {Wireless local area networks (WLANs) are emerging as a popular technology for access to the Internet and enterprise networks. In the long term, the success of WLANs depends on services that support mobile network clients. \par Although other researchers have explored mobility prediction in hypothetical scenarios, evaluating their predictors analytically or with synthetic data, few studies have been able to evaluate their predictors with real user mobility data. As a first step towards filling this fundamental gap, we work with a large data set collected from the Dartmouth College campus-wide wireless network that hosts more than 500 access points and 6,000 users. Extending our earlier work that focuses on predicting the next-visited access point (i.e., location), in this work we explore the predictability of the time of user mobility. Indeed, our contributions are two-fold. First, we evaluate a series of predictors that reflect possible dependencies across time and space while benefiting from either individual or group mobility behaviors. Second, as a case study we examine voice applications and the use of handoff prediction for advance bandwidth reservation. Using application-specific performance metrics such as call drop and call block rates, we provide a picture of the potential gains of prediction. \par Our results indicate that it is difficult to predict handoff time accurately, when applied to real campus WLAN data. However, the findings of our case study also suggest that application performance can be improved significantly even with predictors that are only moderately accurate. The gains depend on the applications' ability to use predictions and tolerate inaccurate predictions. In the case study, we combine the real mobility data with synthesized traffic data. The results show that intelligent prediction can lead to significant reductions in the rate at which active calls are dropped due to handoffs with marginal increments in the rate at which new calls are blocked.}, } @TechReport{kim:classify-tr, author = {Minkyong Kim and David Kotz}, title = {{Classifying the Mobility of Users and the Popularity of Access Points}}, institution = {Dartmouth Computer Science}, year = 2005, month = {May}, number = {TR2005-540}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kim-classify-tr/index.html}, abstract = {There is increasing interest in location-aware systems and applications. It is important for any designer of such systems and applications to understand the nature of user and device mobility. Furthermore, an understanding of the effect of user mobility on access points (APs) is also important for designing, deploying, and managing wireless networks. Although various studies of wireless networks have provided insights into different network environments and user groups, it is often hard to apply these findings to other situations, or to derive useful abstract models. \par In this paper, we present a general methodology for extracting mobility information from wireless network traces, and for classifying mobile users and APs. We used the Fourier transform to convert time-dependent location information to the frequency domain, then chose the two strongest periods and used them as parameters to a classification system based on Bayesian theory. To classify mobile users, we computed diameter (the maximum distance between any two APs visited by a user during a fixed time period) and observed how this quantity changes or repeats over time. We found that user mobility had a strong period of one day, but there was also a large group of users that had either a much smaller or much bigger primary period. Both primary and secondary periods had important roles in determining classes of mobile users. Users with one day as their primary period and a smaller secondary period were most prevalent; we expect that they were mostly students taking regular classes. To classify APs, we counted the number of users visited each AP. The primary period did not play a critical role because it was equal to one day for most of the APs; the secondary period was the determining parameter. APs with one day as their primary period and one week as their secondary period were most prevalent. By plotting the classes of APs on our campus map, we discovered that this periodic behavior of APs seemed to be independent of their geographical locations, but may depend on the relative locations of nearby APs. Ultimately, we hope that our study can help the design of location-aware services by providing a base for user mobility models that reflect the movements of real users.}, } @InProceedings{kim:classify, author = {Minkyong Kim and David Kotz}, title = {{Classifying the Mobility of Users and the Popularity of Access Points}}, booktitle = {{Proceedings of the International Workshop on Location- and Context-Awareness (LoCA)}}, editor = {Thomas Strang and Claudia Linnhoff-Popien}, series = {Lecture Notes in Computer Science}, year = 2005, month = {May}, volume = 3479, pages = {198--209}, publisher = {Springer-Verlag}, copyright = {Springer-Verlag}, address = {Germany}, DOI = {10.1007/11426646_19}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kim-classify/index.html}, abstract = {There is increasing interest in location-aware systems and applications. It is important for any designer of such systems and applications to understand the nature of user and device mobility. Furthermore, an understanding of the effect of user mobility on access points (APs) is also important for designing, deploying, and managing wireless networks. Although various studies of wireless networks have provided insights into different network environments and user groups, it is often hard to apply these findings to other situations, or to derive useful abstract models. \par In this paper, we present a general methodology for extracting mobility information from wireless network traces, and for classifying mobile users and APs. We used the Fourier transform to convert time-dependent location information to the frequency domain, then chose the two strongest periods and used them as parameters to a classification system based on Bayesian theory. To classify mobile users, we computed diameter (the maximum distance between any two APs visited by a user during a fixed time period) and observed how this quantity changes or repeats over time. We found that user mobility had a strong period of one day, but there was also a large group of users that had either a much smaller or much bigger primary period. Both primary and secondary periods had important roles in determining classes of mobile users. Users with one day as their primary period and a smaller secondary period were most prevalent; we expect that they were mostly students taking regular classes. To classify APs, we counted the number of users visited each AP. The primary period did not play a critical role because it was equal to one day for most of the APs; the secondary period was the determining parameter. APs with one day as their primary period and one week as their secondary period were most prevalent. By plotting the classes of APs on our campus map, we discovered that this periodic behavior of APs seemed to be independent of their geographical locations, but may depend on the relative locations of nearby APs. Ultimately, we hope that our study can help the design of location-aware services by providing a base for user mobility models that reflect the movements of real users.}, } @InProceedings{kim:hotspots, author = {Minkyong Kim and David Kotz}, title = {{Modeling users' mobility among WiFi access points}}, booktitle = {{Proceedings of the International Workshop on Wireless Traffic Measurements and Modeling (WiTMeMo)}}, year = 2005, month = {June}, pages = {19--24}, publisher = {USENIX Association}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kim-hotspots/index.html}, abstract = {Modeling movements of users is important for simulating wireless networks, but current models often do not reflect real movements. Using real mobility traces, we can build a mobility model that reflects reality. In building a mobility model, it is important to note that while the number of handheld wireless devices is constantly increasing, laptops are still the majority in most cases. As a laptop is often disconnected from the network while a user is moving, it is not feasible to extract the exact path of the user from network messages. Thus, instead of modeling individual user's movements, we model movements in terms of the influx and outflux of users between access points (APs). We first counted the hourly visits to APs in the syslog messages recorded at APs. We found that the hourly number of visits has a periodic repetition of 24 hours. Based on this observation, we aggregated the visits of multiple days into a single day. We then clustered APs based on the different peak hour of visits. We found that this approach of clustering is effective; we ended up with four distinct clusters and a cluster of stable APs. We then computed the average arrival rate and the distribution of the daily arrivals for each cluster. Using a standard method (such as \emph{thinning}) for generating non-homogeneous Poisson processes, synthetic traces can be generated from our model.}, } @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.}, } @TechReport{chen:traces, author = {Guanling Chen and David Kotz}, title = {{A Case Study of Four Location Traces}}, institution = {Dartmouth Computer Science}, year = 2004, month = {February}, number = {TR2004-490}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/chen-traces/index.html}, abstract = {Location is one of the most important context information that an ubiquitous-computing application may leverage. Thus understanding the location systems and how location-aware applications interact with them is critical for design and deployment of both the location systems and location-aware applications. In this paper, we analyze a set of traces collected from two small-scale one-building location system and two large-scale campus-wide location systems. Our goal is to study characteristics of these location systems ant how these factors should be taken into account by a potentially large number of location-aware applications with different needs. We make empirical measurements of several important metrics and compare the results across these location systems. We discuss the implication of these results on location-aware applications and their supporting software infrastructure, and how location systems could be improved to better serve applications' needs. In places where possible, we use location-aware applications discussed in existing literatures as illustrating examples.}, } @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{song:predict-tr, author = {Libo Song and David Kotz and Ravi Jain and Xiaoning He}, title = {{Evaluating location predictors with extensive Wi-Fi mobility data}}, institution = {Dartmouth Computer Science}, year = 2004, month = {February}, number = {TR2004-491}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-predict-tr/index.html}, abstract = {Location is an important feature for many applications, and wireless networks may serve their clients better by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors using a two-year trace of the mobility patterns of more than 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. The surprising results provide critical evidence for anyone designing or using mobility predictors. We implemented and compared the prediction accuracy of several location predictors drawn from four major families of domain-independent predictors, namely, Markov-based, compression-based, PPM, and SPM predictors. We found that low-order Markov predictors performed as well or better than the more complex and more space-consuming compression-based predictors.}, } @InProceedings{song:predict, author = {Libo Song and David Kotz and Ravi Jain and Xiaoning He}, title = {{Evaluating location predictors with extensive Wi-Fi mobility data}}, booktitle = {{Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)}}, year = 2004, month = {March}, volume = 2, pages = {1414--1424}, publisher = {IEEE}, copyright = {IEEE}, DOI = {10.1109/INFCOM.2004.1357026}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-predict/index.html}, abstract = {Location is an important feature for many applications, and wireless networks can better serve their clients by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors, using a two-year trace of the mobility patterns of over 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. \par We implemented and compared the prediction accuracy of several location predictors drawn from two major families of domain-independent predictors, namely Markov-based and compression-based predictors. We found that low-order Markov predictors performed as well or better than the more complex and more space-consuming compression-based predictors. Predictors of both families fail to make a prediction when the recent context has not been previously seen. To overcome this drawback, we added a simple fallback feature to each predictor and found that it significantly enhanced its accuracy in exchange for modest effort. Thus the Order-2 Markov predictor with fallback was the best predictor we studied, obtaining a median accuracy of about 72\% for users with long trace lengths. We also investigated a simplification of the Markov predictors, where the prediction is based not on the most frequently seen context in the past, but the most recent, resulting in significant space and computational savings. We found that Markov predictors with this recency semantics can rival the accuracy of standard Markov predictors in some cases. Finally, we considered several seemingly obvious enhancements, such as smarter tie-breaking and aging of context information, and discovered that they had little effect on accuracy. The paper ends with a discussion and suggestions for further work.}, } @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.}, } @Article{song:predict-poster, author = {Libo Song and David Kotz and Ravi Jain and Xiaoning He}, title = {{MobiCom Poster: Evaluating location predictors with extensive Wi-Fi mobility data}}, journal = {ACM SIGMOBILE Mobile Computing and Communication Review}, year = 2003, month = {October}, volume = 7, number = 4, pages = {64--65}, publisher = {ACM}, copyright = {ACM}, DOI = {10.1145/965732.965747}, URL = {https://www.cs.dartmouth.edu/~kotz/research/song-predict-poster/index.html}, } @TechReport{lee:thesis, author = {Clara Lee}, title = {{Persistence and Prevalence in the Mobility of Dartmouth Wireless Network Users}}, institution = {Dartmouth Computer Science}, year = 2003, month = {May}, number = {TR2003-455}, copyright = {the author}, address = {Hanover, NH}, URL = {https://www.cs.dartmouth.edu/~kotz/research/lee-thesis/index.html}, note = {The data in this paper is highly suspect; see TR2003-480. Available as Dartmouth Computer Science Technical Report TR2003-455}, abstract = {Wireless local-area networks (WLANs) are increasing in popularity. As more people use WLANs it is important to understand how these users behave. We analyzed data collected over three months of 2002 to measure the persistence and prevalence of users of the Dartmouth wireless network. \par We found that most of the users of Dartmouth's network have short association times and a high rate of mobility. This observation fits with the predominantly student population of Dartmouth College, because students do not have a fixed workplace and are moving to and from classes all day.}, } @InProceedings{mills-tettey:mvoip, author = {G. Ayorkor Mills-Tettey and David Kotz}, title = {{Mobile Voice Over IP (MVOIP): An Application-level Protocol for Call Hand-off in Real Time Applications}}, booktitle = {{Proceedings of the IEEE International Phoenix Conference on Computers and Communications (IPCCC)}}, year = 2002, month = {April}, pages = {271--279}, publisher = {IEEE}, copyright = {IEEE}, DOI = {10.1109/IPCCC.2002.995160}, URL = {https://www.cs.dartmouth.edu/~kotz/research/mills-tettey-mvoip/index.html}, abstract = {This paper presents Mobile Voice Over IP, an application-level protocol to support terminal mobility in real-time applications such as voice over IP, on a wireless local area network. We describe our MVOIP implementation based on the ITU-T H.323 protocol stack, present experimental results on call hand-off latency, and discuss various implementation issues, including the task of quickly and accurately determining when call hand-off is necessary. We also discuss how MVOIP relates to other proposed mobility support schemes, and how it can be generalized to provide application-level mobility support in a wide range of real and non real-time applications.}, }