Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
- Publication
- Publication Type
Articles 1 - 30 of 39
Full-Text Articles in Physical Sciences and Mathematics
A Combined Routing Method For Ad Hoc Wireless Networks, Zhenhui Jiang
A Combined Routing Method For Ad Hoc Wireless Networks, Zhenhui Jiang
Dartmouth College Master’s Theses
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 …
A Steerable, Untethered, 250x60 Micron Mems Mobile Micro-Robot, Bruce R. Donald, Christopher G. Levey, Craig D. Mcgray, Igor Paprotny, Daniela Rus
A Steerable, Untethered, 250x60 Micron Mems Mobile Micro-Robot, Bruce R. Donald, Christopher G. Levey, Craig D. Mcgray, Igor Paprotny, Daniela Rus
Computer Science Technical Reports
We present a steerable, electrostatic, untethered, MEMS micro-robot, with dimensions of 60 µm by 250 µm by 10 µm. This micro-robot is 1 to 2 orders of magnitude smaller in size than previous micro-robotic systems. The device consists of a curved, cantilevered steering arm, mounted on an untethered scratch drive actuator. These two components are fabricated monolithically from the same sheet of conductive polysilicon, and receive a common power and control signal through a capacitive coupling with an underlying electrical grid. All locations on the grid receive the same power and control signal, so that the devices can be operated …
How Hard Is It To Cheat In The Gale-Shapley Stable Matching Algorithm, Chien-Chung Huang
How Hard Is It To Cheat In The Gale-Shapley Stable Matching Algorithm, Chien-Chung Huang
Computer Science Technical Reports
We study strategy issues surrounding the stable marriage problem. Under the Gale-Shapley algorithm (with men proposing), a classical theorem says that it is impossible for every liar to get a better partner. We try to challenge this theorem. First, observing a loophole in the statement of the theorem, we devise a coalition strategy in which a non-empty subset of the liars gets a better partner and no man is worse off than before. This strategy is restricted in that not everyone has the incentive to cheat. We attack the classical theorem further by means of randomization. However, this theorem shows …
Crawdad: A Community Resource For Archiving Wireless Data At Dartmouth, David Kotz, Tristan Henderson
Crawdad: A Community Resource For Archiving Wireless Data At Dartmouth, David Kotz, Tristan Henderson
Dartmouth Scholarship
Wireless network researchers are seriously starved for data about how real users, applications, and devices use real networks under real network conditions. CRAWDAD (Community Resource for Archiving Wireless Data at Dartmouth) is a new National Science Foundation-funded project to build a wireless-network data archive for the research community. It will host wireless data and provide tools and documents to make collecting and using the data easy. This resource should help researchers identify and evaluate real and interesting problems in mobile and pervasive computing. To learn more about CRAWDAD and discuss its direction, about 30 interested people gathered at a workshop …
Master’S Thesis Proposal: Computation Reuse In Stacking And Unstacking, Anne Loomis
Master’S Thesis Proposal: Computation Reuse In Stacking And Unstacking, Anne Loomis
Computer Science Technical Reports
Algorithms for dynamic simulation and control are fundamental to many applications, including computer games and movies, medical simulation, and mechanical design. I propose to explore efficient algorithms for finding a stable unstacking sequence -- an order in which we can remove every object from a structure without causing the structure to collapse under gravity at any step. We begin with a basic unstacking sequence algorithm: consider the set of all objects in a structure. Collect all possible subsets into a disassembly graph. Search the graph, testing the stability of each node as it is visited. Any path of stable nodes …
Detection Of Covert Channel Encoding In Network Packet Delays, Vincent Berk, Annarita Giani, George Cybenko
Detection Of Covert Channel Encoding In Network Packet Delays, Vincent Berk, Annarita Giani, George Cybenko
Computer Science Technical Reports
Covert channels are mechanisms for communicating information in ways that are difficult to detect. Data exfiltration can be an indication that a computer has been compromised by an attacker even when other intrusion detection schemes have failed to detect a successful attack. Covert timing channels use packet inter-arrival times, not header or payload embedded information, to encode covert messages. This paper investigates the channel capacity of Internet-based timing channels and proposes a methodology for detecting covert timing channels based on how close a source comes to achieving that channel capacity. A statistical approach is then used for the special case …
Combinatorial Theorems About Embedding Trees On The Real Line, Amit Chakrabarti, Subhash Khot
Combinatorial Theorems About Embedding Trees On The Real Line, Amit Chakrabarti, Subhash Khot
Computer Science Technical Reports
We consider the combinatorial problem of embedding a tree metric into the real line with low distortion. For two special families of trees --- the family of complete binary trees and the family of subdivided stars --- we provide embeddings whose distortion is provably optimal, up to a constant factor. We also prove that the optimal distortion of a linear embedding of a tree can be arbitrarily low or high even when it has bounded degree.
A Quasi-Ptas For Unsplittable Flow On Line Graphs, Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber
A Quasi-Ptas For Unsplittable Flow On Line Graphs, Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber
Computer Science Technical Reports
We study the Unsplittable Flow Problem (UFP) on a line graph, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP is contained in DTIME(2^polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. Earlier results on this problem included a polynomial time (2+epsilon)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. Unlike most …
Performance Evaluation Of Distributed Security Protocols Using Discrete Event Simulation, Meiyuan Zhao
Performance Evaluation Of Distributed Security Protocols Using Discrete Event Simulation, Meiyuan Zhao
Dartmouth College Ph.D Dissertations
The Border Gateway Protocol (BGP) that manages inter-domain routing on the Internet lacks security. Protective measures using public key cryptography introduce complexities and costs. To support authentication and other security functionality in large networks, we need public key infrastructures (PKIs). Protocols that distribute and validate certificates introduce additional complexities and costs. The certification path building algorithm that helps users establish trust on certificates in the distributed network environment is particularly complicated. Neither routing security nor PKI come for free. Prior to this work, the research study on performance issues of these large-scale distributed security systems was minimal. In this thesis, …
Improving Large-Scale Network Traffic Simulation With Multi-Resolution Models, Guanhua Yan
Improving Large-Scale Network Traffic Simulation With Multi-Resolution Models, Guanhua Yan
Dartmouth College Ph.D Dissertations
Simulating a large-scale network like the Internet is a challenging undertaking because of the sheer volume of its traffic. Packet-oriented representation provides high-fidelity details but is computationally expensive; fluid-oriented representation offers high simulation efficiency at the price of losing packet-level details. Multi-resolution modeling techniques exploit the advantages of both representations by integrating them in the same simulation framework. This dissertation presents solutions to the problems regarding the efficiency, accuracy, and scalability of the traffic simulation models in this framework. The ``ripple effect'' is a well-known problem inherent in event-driven fluid-oriented traffic simulation, causing explosion of fluid rate changes. Integrating multi-resolution …
Efficient Wait-Free Algorithms For Implementing Ll/Sc Objects, Srdjan Petrovic
Efficient Wait-Free Algorithms For Implementing Ll/Sc Objects, Srdjan Petrovic
Dartmouth College Ph.D Dissertations
Over the past decade, a pair of instructions called load-linked (LL) and store-conditional (SC) have emerged as the most suitable synchronization instructions for the design of lock-free algorithms. However, current architectures do not support these instructions; instead, they support either CAS (e.g., UltraSPARC, Itanium, Pentium) or restricted versions of LL/SC (e.g., POWER4, MIPS, Alpha). Thus, there is a gap between what algorithm designers want (namely, LL/SC) and what multiprocessors actually support (namely, CAS or restricted LL/SC). To bridge this gap, this thesis presents a series of efficient, wait-free algorithms that implement LL/SC from CAS or restricted LL/SC.
The Theory Of Trackability With Applications To Sensor Networks, Valentino Crespi, George Cybenko, Guofei Jiang
The Theory Of Trackability With Applications To Sensor Networks, Valentino Crespi, George Cybenko, Guofei Jiang
Computer Science Technical Reports
In this paper, we formalize the concept of tracking in a sensor network and develop a rigorous theory of {\em trackability} that investigates the rate of growth of the number of consistent tracks given a sequence of observations made by the sensor network. The phenomenon being tracked is modelled by a nondeterministic finite automaton and the sensor network is modelled by an observer capable of detecting events related, typically ambiguously, to the states of the underlying automaton. More formally, an input string, $Z^t$, of $t+1$ symbols (the sensor network observations) that is presented to a nondeterministic finite automaton, $M$, (the …
Natural Image Statistics For Digital Image Forensics, Siwei Lyu
Natural Image Statistics For Digital Image Forensics, Siwei Lyu
Dartmouth College Ph.D Dissertations
We describe a set of natural image statistics that are built upon two multi-scale image decompositions, the quadrature mirror filter pyramid decomposition and the local angular harmonic decomposition. These image statistics consist of first- and higher-order statistics that capture certain statistical regularities of natural images. We propose to apply these image statistics, together with classification techniques, to three problems in digital image forensics: (1) differentiating photographic images from computer-generated photorealistic images, (2) generic steganalysis; (3) rebroadcast image detection. We also apply these image statistics to the traditional art authentication for forgery detection and identification of artists in an art work. …
On The Design Of An Immersive Environment For Security-Related Studies, Yougu Yuan
On The Design Of An Immersive Environment For Security-Related Studies, Yougu Yuan
Dartmouth College Master’s Theses
The Internet has become an essential part of normal operations of both public and private sectors. Many security issues are not addressed in the original Internet design, and security now has become a large concern for networking research and study. There is an imperative need to have an simulation environment that can be used to help study security-related research problems. In the thesis we present our effort to build such an environment: Real-time Immersive Network Simulation Environment (RINSE). RINSE features flexible configuration of models using various networking protocols and real-time user interaction. We also present the Estimate Next Infection (ENI) …
Efficiently Implementing A Large Number Of Ll/Sc Objects, Prasad Jayanti, Srdjan Petrovic
Efficiently Implementing A Large Number Of Ll/Sc Objects, Prasad Jayanti, Srdjan Petrovic
Computer Science Technical Reports
Over the past decade, a pair of instructions called load-linked (LL) and store-conditional (SC) have emerged as the most suitable synchronization instructions for the design of lock-free algorithms. However, current architectures do not support these instructions; instead, they support either CAS (e.g., UltraSPARC, Itanium) or restricted versions of LL/SC (e.g., POWER4, MIPS, Alpha). Thus, there is a gap between what algorithm designers want (namely, LL/SC) and what multiprocessors actually support (namely, CAS or RLL/RSC). To bridge this gap, a flurry of algorithms that implement LL/SC from CAS have appeared in the literature. The two most recent algorithms are due to …
Structural Analysis Of Social Networks With Wireless Users, Guanling Chen, David Kotz
Structural Analysis Of Social Networks With Wireless Users, Guanling Chen, David Kotz
Computer Science Technical Reports
Online interactions between computer users form Internet-based social networks. In this paper we present a structural analysis of two such networks with wireless users. In one network the wireless users participate in a global file-sharing system, and in the other they interact with each other through a local music-streaming application.
Towards Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
Towards Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
Computer Science Technical Reports
Many security protocols hypothesize the existence of a {\em trusted third party (TTP)} to ease handling of computation and data too sensitive for the other parties involved. Subsequent discussion usually dismisses these protocols as hypothetical or impractical, under the assumption that trusted third parties cannot exist. However, the last decade has seen the emergence of hardware-based devices that, to high assurance, can carry out computation unmolested; emerging research promises more. In theory, such devices can perform the role of a trusted third party in real-world problems. In practice, we have found problems. The devices aspire to be general-purpose processors but …
Mining Frequent And Periodic Association Patterns, Guanling Chen, Heng Huang, Minkyong Kim
Mining Frequent And Periodic Association Patterns, Guanling Chen, Heng Huang, Minkyong Kim
Computer Science Technical Reports
Profiling the clients' movement behaviors is useful for mobility modeling, anomaly detection, and location prediction. In this paper, we study clients' frequent and periodic movement patterns in a campus wireless network. We use offline data-mining algorithms to discover patterns from clients' association history, and analyze the reported patterns using statistical methods. Many of our results reflect the common characteristics of a typical academic campus, though we also observed some unusual association patterns. There are two challenges: one is to remove noise from data for efficient pattern discovery, and the other is to interpret discovered patterns. We address the first challenge …
More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties, Alexander Iliev, Sean Smith
Computer Science Technical Reports
Secure Function Evaluation (SFE) problems. We assume that a really trustworthy TTP device will have very limited protected memory and computation environment---a \emph{tiny TTP}. This precludes trivial solutions like "just run the function in the TTP". Traditional scrambled circuit evaluation approaches to SFE have a very high overhead in using indirectly-addressed arrays---every array access's cost is linear in the array size. The main gain in our approach is that array access can be provided with much smaller overhead---$O(\sqrt{N}\log N)$. This expands the horizon of problems which can be efficiently solved using SFE. Additionally, our technique provides a simple way to …
Managing Access Control In Virtual Private Networks, Twum Djin
Managing Access Control In Virtual Private Networks, Twum Djin
Dartmouth College Undergraduate Theses
Virtual Private Network technology allows remote network users to benefit from resources on a private network as if their host machines actually resided on the network. However, each resource on a network may also have its own access control policies, which may be completely unrelated to network access. Thus users� access to a network (even by VPN technology) does not guarantee their access to the sought resources. With the introduction of more complicated access privileges, such as delegated access, it is conceivable for a scenario to arise where a user can access a network remotely (because of direct permissions from …
Lower Bounds On The Communication Complexity Of Shifting, Marco D. Adelfio
Lower Bounds On The Communication Complexity Of Shifting, Marco D. Adelfio
Dartmouth College Undergraduate Theses
We study the communication complexity of the SHIFT (equivalently, SUM-INDEX) function in a 3-party simultaneous message model. Alice and Bob share an n-bit string x and Alice holds an index i and Bob an index j. They must send messages to a referee who knows only n, i and j, enabling him to determine x[(i+j) mod n]. Surprisingly, it is possible to achieve nontrivial savings even with such a strong restriction: Bob can now make do with only ceil(n/2) bits. Here we show that this bound is completely tight, for all n. This is an exact lower bound, with no …
On-Line Metasearch, Pooling, And System Evaluation, Robert A. Savell
On-Line Metasearch, Pooling, And System Evaluation, Robert A. Savell
Dartmouth College Ph.D Dissertations
This thesis presents a unified method for simultaneous solution of three problems in Information Retrieval--- metasearch (the fusion of ranked lists returned by retrieval systems to elicit improved performance), efficient system evaluation (the accurate evaluation of retrieval systems with small numbers of relevance judgements), and pooling or ``active sample selection" (the selection of documents for manual judgement in order to develop sample pools of high precision or pools suitable for assessing system quality). The thesis establishes a unified theoretical framework for addressing these three problems and naturally generalizes their solution to the on-line context by incorporating feedback in the form …
Modeling Users' Mobility Among Wifi Access Points, Minkyong Kim, David Kotz
Modeling Users' Mobility Among Wifi Access Points, Minkyong Kim, David Kotz
Dartmouth Scholarship
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 …
Analysis Of A Wi-Fi Hotspot Network, David P. Blinn, Tristan Henderson, David Kotz
Analysis Of A Wi-Fi Hotspot Network, David P. Blinn, Tristan Henderson, David Kotz
Dartmouth Scholarship
Wireless hotspot networks have become increasingly popular in recent years as a means of providing Internet access in public areas such as restaurants and airports. In this paper we present the first study of such a hotspot network. We examine five weeks of SNMP traces from the Verizon Wi-Fi HotSpot network in Manhattan. We find that far more cards associated to the network than logged into it. Most clients used the network infrequently and visited few APs. AP utilization was uneven and the network displayed some unusual patterns in traffic load. Some characteristics were similar to those previously observed in …
A Toy Rock Climbing Robot, Matthew P. Bell
A Toy Rock Climbing Robot, Matthew P. Bell
Dartmouth College Undergraduate Theses
The goal of this thesis was to build a simple toy rock climbing robot, and to explore problems related to grasping, path planning, and robot control. The robot is capable of climbing a wall of pegs either under manual control through a host system and an infrared interface, or on the basis of a set of pre-recorded keyframes. In addition, the robot can climb certain peg configurations using a cyclic gait. The robot climbs in an open-loop mode without sensor feedback. All communications are sent through the IR connection, and the tether to the robot consists only of two power …
Preventing Theft Of Quality Of Service On Open Platforms, Kwang-Hyun Baek, Sean W. Smith
Preventing Theft Of Quality Of Service On Open Platforms, Kwang-Hyun Baek, Sean W. Smith
Computer Science Technical Reports
As multiple types of traffic converge onto one network (frequently wireless), enterprises face a tradeoff between effectiveness and security. Some types of traffic, such as voice-over-IP (VoIP), require certain quality of service (QoS) guarantees to be effective. The end client platform is in the best position to know which packets deserve this special handling. In many environments (such as universities), end users relish having control over their own machines. However, if end users administer their own machines, nothing stops dishonest ones from marking undeserving traffic for high QoS. How can an enterprise ensure that only appropriate traffic receives high QoS, …
Aggregated Path Authentication For Efficient Bgp Security, Meiyuan Zhao, Sean W. Smith, David M. Nicol
Aggregated Path Authentication For Efficient Bgp Security, Meiyuan Zhao, Sean W. Smith, David M. Nicol
Computer Science Technical Reports
The border gateway protocol (BGP) controls inter-domain routing in the Internet. BGP is vulnerable to many attacks, since routers rely on hearsay information from neighbors. Secure BGP (S-BGP) uses DSA to provide route authentication and mitigate many of these risks. However, many performance and deployment issues prevent S-BGP's real-world deployment. Previous work has explored improving S-BGP processing latencies, but space problems, such as increased message size and memory cost, remain the major obstacles. In this paper, we combine two efficient cryptographic techniques---signature amortization and aggregate signatures---to design new aggregated path authentication schemes. We propose six constructions for aggregated path authentication …
An O(N^{5/2} Log N) Algorithm For The Rectilinear Minimum Link-Distance Problem In Three Dimensions (Extended Abstract), Robert Scot Drysdale, Clifford Stein, David P. Wagner
An O(N^{5/2} Log N) Algorithm For The Rectilinear Minimum Link-Distance Problem In Three Dimensions (Extended Abstract), Robert Scot Drysdale, Clifford Stein, David P. Wagner
Computer Science Technical Reports
In this paper we consider the Rectilinear Minimum Link-Distance Problem in Three Dimensions. The problem is well studied in two dimensions, but is relatively unexplored in higher dimensions. We solve the problem in O(B n log n) time, where n is the number of corners among all obstacles, and B is the size of a BSP decomposition of the space containing the obstacles. It has been shown that in the worst case B = Theta(n^{3/2}), giving us an overall worst case time of O(n^{5/2} log n). Previously known algorithms have had worst-case running times of Omega(n^3).
Classifying The Mobility Of Users And The Popularity Of Access Points, Minkyong Kim, David Kotz
Classifying The Mobility Of Users And The Popularity Of Access Points, Minkyong Kim, David Kotz
Computer Science Technical Reports
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. In this paper, we present a general methodology for extracting mobility information from wireless network …
Classifying The Mobility Of Users And The Popularity Of Access Points, Minkyong Kim, David Kotz
Classifying The Mobility Of Users And The Popularity Of Access Points, Minkyong Kim, David Kotz
Dartmouth Scholarship
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 …