Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences Commons™

Open Access. Powered by Scholars. Published by Universities.®

Dartmouth College

Discipline
Keyword
Publication Year
Publication
Publication Type
File Type

Articles 601 - 630 of 1103

Full-Text Articles in Computer Sciences

Scalability In A Secure Distributed Proof System, Kazuhiro Minami, David Kotz May 2006

Scalability In A Secure Distributed Proof System, Kazuhiro Minami, David Kotz

Dartmouth Scholarship

A logic-based language is often adopted in systems for pervasive computing, because it provides a convenient way to define rules that change the behavior of the systems dynamically. Those systems might define rules that refer to the users' context information to provide context-aware services. For example, a smart-home application could define rules referring to the location of a user to control the light of a house automatically. In general, the context information is maintained in different administrative domains, and it is, therefore, desirable to construct a proof in a distributed way while preserving each domain's confidentiality policies. In this paper, …

Go to article

Visualizing Paths In Context, Fabio Pellacini, Lori Lorigo, Geri Gay Apr 2006

Visualizing Paths In Context, Fabio Pellacini, Lori Lorigo, Geri Gay

Computer Science Technical Reports

Data about movement through a space is increasingly becoming available for capture and analysis. In many applications, this data is captured or modeled as transitions between a small number of areas of interests, or a finite set of states, and these transitions constitute paths in the space. Similarities and differences between paths are of great importance to such analyses, but can be difficult to assess. In this work we present a visualization approach for representing paths in context, where individual paths can be compared to other paths or to a group of paths. Our approach summarizes path behavior using a …

Go to article

Crawdad: A Community Resource For Archiving Wireless Data At Dartmouth, Jihwang Yeo, David Kotz, Tristan Henderson Apr 2006

Crawdad: A Community Resource For Archiving Wireless Data At Dartmouth, Jihwang Yeo, 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, a Community Resource for Archiving Wireless Data at Dartmouth, is a new NSF-funded project to build a wireless network data archive for the research community. We host wireless data, and provide tools and documents to make it easy to collect and use wireless network data. We hope that this resource will help researchers identify and evaluate real and interesting problems in mobile and pervasive computing. This report outlines the CRAWDAD project, the kick-off workshop that was held …

Go to article

Extracting A Mobility Model From Real User Traces, Minkyong Kim, David Kotz, Songkuk Kim Apr 2006

Extracting A Mobility Model From Real User Traces, Minkyong Kim, David Kotz, Songkuk Kim

Dartmouth Scholarship

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 …

Go to article

Predictability Of Wlan Mobility And Its Effects On Bandwidth Provisioning, Libo Song, Udayan Deshpande, Ulaş C. Kozat, David Kotz, Ravi Jain Apr 2006

Predictability Of Wlan Mobility And Its Effects On Bandwidth Provisioning, Libo Song, Udayan Deshpande, Ulaş C. Kozat, David Kotz, Ravi Jain

Dartmouth Scholarship

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 …

Go to article

Channel Sampling Strategies For Monitoring Wireless Networks, Udayan Deshpande, Tristan Henderson, David Kotz Apr 2006

Channel Sampling Strategies For Monitoring Wireless Networks, Udayan Deshpande, Tristan Henderson, David Kotz

Dartmouth Scholarship

Monitoring the activity on an IEEE 802.11 network is useful for many applications, such as network management, optimizing deployment, or detecting network attacks. Deploying wireless sniffers to monitor every access point in an enterprise network, however, may be expensive or impractical. Moreover, some applications may require the deployment of multiple sniffers to monitor the numerous channels in an 802.11 network. In this paper, we explore sampling strategies for monitoring multiple channels in 802.11b/g networks. We describe a simple sampling strategy, where each channel is observed for an equal, predetermined length of time, and consider applications where such a strategy might …

Go to article

A Simple Computational Method For The Identification Of Disease-Associated Loci In Complex, Incomplete Pedigrees, Gregory Leibon, Dan Rockmore, Martin R. Pollak Mar 2006

A Simple Computational Method For The Identification Of Disease-Associated Loci In Complex, Incomplete Pedigrees, Gregory Leibon, Dan Rockmore, Martin R. Pollak

Computer Science Technical Reports

We present an approach, called the Shadow Method, for the identification of disease loci from dense genetic marker maps in complex, potentially incomplete pedigrees. Shadow is a simple method based on an analysis of the patterns of obligate meiotic recombination events in genotypic data. This method can be applied to any high density marker map and was specifically designed to explore the fact that extremely dense marker maps are becoming more readily available. We also describe how to interpret and associated meaningful P-Values to the results. Shadow has significant advantages over traditional parametric linkage analysis methods in that it can …

Go to article

Path Planning Algorithms Under The Link-Distance Metric, David Phillip Wagner Feb 2006

Path Planning Algorithms Under The Link-Distance Metric, David Phillip Wagner

Dartmouth College Ph.D Dissertations

The Traveling Salesman Problem and the Shortest Path Problem are famous problems in computer science which have been well studied when the objective is measured using the Euclidean distance. Here we examine these geometric problems under a different set of optimization criteria. Rather than considering the total distance traversed by a path, this thesis looks at reducing the number of times a turn is made along that path, or equivalently, at reducing the number of straight lines in the path. Minimizing this objective value, known as the link-distance, is useful in situations where continuing in a given direction is cheap, …

Go to article

Secure Context-Sensitive Authorization, Kazuhiro Minami Feb 2006

Secure Context-Sensitive Authorization, Kazuhiro Minami

Dartmouth College Ph.D Dissertations

Pervasive computing leads to an increased integration between the real world and the computational world, and many applications in pervasive computing adapt to the user's context, such as the location of the user and relevant devices, the presence of other people, light or sound conditions, or available network bandwidth, to meet a user's continuously changing requirements without taking explicit input from the users. We consider a class of applications that wish to consider a user's context when deciding whether to authorize a user's access to important physical or information resources. Such a context-sensitive authorization scheme is necessary when a mobile …

Go to article

A Novel Minimized Dead-End Elimination Criterion And Its Application To Protein Redesign In A Hybrid Scoring And Search Algorithm For Computing Partition Functions Over Molecular Ensembles, Ivelin Georgiev, Ryan H. Lilien, Bruce R. Donald Jan 2006

A Novel Minimized Dead-End Elimination Criterion And Its Application To Protein Redesign In A Hybrid Scoring And Search Algorithm For Computing Partition Functions Over Molecular Ensembles, Ivelin Georgiev, Ryan H. Lilien, Bruce R. Donald

Computer Science Technical Reports

Novel molecular function can be achieved by redesigning an enzyme's active site so that it will perform its chemical reaction on a novel substrate. One of the main challenges for protein redesign is the efficient evaluation of a combinatorial number of candidate structures. The modeling of protein flexibility, typically by using a rotamer library of commonly-observed low-energy side-chain conformations, further increases the complexity of the redesign problem. A dominant algorithm for protein redesign is Dead-End Elimination (DEE), which prunes the majority of candidate conformations by eliminating rigid rotamers that provably are not part of the Global Minimum Energy Conformation (GMEC). …

Go to article

Improving Data Access For Computational Grid Applications, Ron Oldfield, David Kotz Jan 2006

Improving Data Access For Computational Grid Applications, Ron Oldfield, David Kotz

Dartmouth Scholarship

High-performance computing increasingly occurs on “computational grids” composed of heterogeneous and geographically distributed systems of computers, networks, and storage devices that collectively act as a single “virtual” computer. A key challenge in this environment is to provide efficient access to data distributed across remote data servers. Our parallel I/O framework, called Armada, allows application and data-set providers to flexibly compose graphs of processing modules that describe the distribution, application interfaces, and processing required of the dataset before computation. Although the framework provides a simple programming model for the application programmer and the data-set provider, the resulting graph may contain bottlenecks …

Go to article

On Improving Wireless Broadcast Reliability Of Sensor Networks Using Erasure Codes, Rajnish Kumar, Arnab Paul, Umakishore Ramachandran, David Kotz Jan 2006

On Improving Wireless Broadcast Reliability Of Sensor Networks Using Erasure Codes, Rajnish Kumar, Arnab Paul, Umakishore Ramachandran, David Kotz

Dartmouth Scholarship

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 …

Go to article

How Hard Is It To Cheat In The Gale-Shapley Stable Matching Algorithm, Chien-Chung Huang Dec 2005

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 …

Go to article

A Steerable, Untethered, 250x60 Micron Mems Mobile Micro-Robot, Bruce R. Donald, Christopher G. Levey, Craig D. Mcgray, Igor Paprotny, Daniela Rus Dec 2005

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 …

Go to article

A Combined Routing Method For Ad Hoc Wireless Networks, Zhenhui Jiang Dec 2005

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 …

Go to article

Crawdad: A Community Resource For Archiving Wireless Data At Dartmouth, David Kotz, Tristan Henderson Dec 2005

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 …

Go to article

Master’S Thesis Proposal: Computation Reuse In Stacking And Unstacking, Anne Loomis Nov 2005

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 …

Go to article

Detection Of Covert Channel Encoding In Network Packet Delays, Vincent Berk, Annarita Giani, George Cybenko Nov 2005

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 …

Go to article

Combinatorial Theorems About Embedding Trees On The Real Line, Amit Chakrabarti, Subhash Khot Oct 2005

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.

Go to article

A Quasi-Ptas For Unsplittable Flow On Line Graphs, Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber Oct 2005

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 …

Go to article

Performance Evaluation Of Distributed Security Protocols Using Discrete Event Simulation, Meiyuan Zhao Oct 2005

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, …

Go to article

Improving Large-Scale Network Traffic Simulation With Multi-Resolution Models, Guanhua Yan Sep 2005

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 …

Go to article

Efficient Wait-Free Algorithms For Implementing Ll/Sc Objects, Srdjan Petrovic Aug 2005

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.

Go to article

The Theory Of Trackability With Applications To Sensor Networks, Valentino Crespi, George Cybenko, Guofei Jiang Aug 2005

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 …

Go to article

Efficiently Implementing A Large Number Of Ll/Sc Objects, Prasad Jayanti, Srdjan Petrovic Aug 2005

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 …

Go to article

On The Design Of An Immersive Environment For Security-Related Studies, Yougu Yuan Aug 2005

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) …

Go to article

Natural Image Statistics For Digital Image Forensics, Siwei Lyu Aug 2005

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. …

Go to article

Mining Frequent And Periodic Association Patterns, Guanling Chen, Heng Huang, Minkyong Kim Jul 2005

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 …

Go to article

Towards Tiny Trusted Third Parties, Alexander Iliev, Sean Smith Jul 2005

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 …

Go to article

More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties, Alexander Iliev, Sean Smith Jul 2005

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 …

Go to article

First Prev Next Last