Open Access. Powered by Scholars. Published by Universities.®
Articles 31 - 47 of 47
Full-Text Articles in Computer Engineering
Real-Time Query Scheduling For Wireless Sensor Networks, Octav Chipara, Chenyang Lu, Gruia-Catalin Roman
Real-Time Query Scheduling For Wireless Sensor Networks, Octav Chipara, Chenyang Lu, Gruia-Catalin Roman
All Computer Science and Engineering Research
Recent years have seen the emergence of wireless sensor network (WSN) systems that require high data rate real-time communication. This paper proposes Real-Time Query Scheduling (RTQS), a novel approach to conflict-free transmission scheduling for real-time queries in WSNs. We show that there is an inherent trade-off between prioritization and throughput in conflict-free query scheduling. RTQS provides three new real-time scheduling algorithms. The non-preemptive query scheduling algorithm achieves high throughput while introducing priority inversions. The preemptive query scheduling algorithm eliminates priority inversion at the cost of reduced throughput. The slack stealing query scheduling algorithm combines the benefits of preemptive and non-preemptive …
Mlds: A Flexible Location Directory Service For Tiered Sensor Networks, Sangeeta Bhattacharya, Chien-Liang Fok, Chenyang Lu, Gruia-Catalin Roman
Mlds: A Flexible Location Directory Service For Tiered Sensor Networks, Sangeeta Bhattacharya, Chien-Liang Fok, Chenyang Lu, Gruia-Catalin Roman
All Computer Science and Engineering Research
Many emergent distributed sensing applications need to keep track of mobile entities across multiple sensor networks connected via an IP network. To simplify the realization of such applications, we present MLDS, a Multi-resolution Location Directory Service for tiered sensor networks. MLDS provides a rich set of spatial query services ranging from simple queries about entity location, to complex nearest neighbor queries. Furthermore, MLDS supports multiple query granularities which allow an application to achieve the desired tradeoff between query accuracy and communication cost. We implemented MLDS on Agimone, a unified middleware for sensor and IP networks. We then deployed and evaluated …
Network Access In A Diversified Internet, M. Wilson, F. Kuhns, J. Turner
Network Access In A Diversified Internet, M. Wilson, F. Kuhns, J. Turner
All Computer Science and Engineering Research
There is a growing interest in virtualized network infrastructures as a means to enable experimental evaluation of new network architectures on a realistic scale. The National Science Foundation's GENI initiative seeks to develop a national experimental facility that would include virtualized network platforms that can support many concurrent experimental networks. Some researchers seek to make virtualization a central architectural component of a future Internet, so that new network architectures can be introduced at any time, without the barriers to entry that currently make this difficult. This paper focuses on how to extend the concept of virtualized networking through LAN-based access …
Splice: A Standardized Peripheral Logic And Interface Creation Engine, Master's Thesis, May 2007, Justin Thiel
Splice: A Standardized Peripheral Logic And Interface Creation Engine, Master's Thesis, May 2007, Justin Thiel
All Computer Science and Engineering Research
Recent advancements in FPGA technology have allowed manufacturers to place general-purpose processors alongside user-configurable logic gates on a single chip. At first glance, these integrated devices would seem to be the ideal deployment platform for hardware-software co-designed systems, but some issues, such as incompatibility across vendors and confusion over which bus interfaces to support, have impeded adoption of these platforms. This thesis describes the design and operation of Splice, a software-based code generation tool intended to address these types of issues by providing a bus-independent structure that allows end-users to easily integrate their customized peripheral logic into embedded systems. To …
Architecture For Document Clustering In Reconfigurable Hardware, Master's Thesis, December 2006, Adam G. Covington
Architecture For Document Clustering In Reconfigurable Hardware, Master's Thesis, December 2006, Adam G. Covington
All Computer Science and Engineering Research
High-performance document clustering systems enable similar documents to automatically self-organize into groups. In the past, the large amount of computational time needed to cluster documents prevented practical use of such systems with a large number of documents. A full hardware implementation of K-means clustering has been designed and implemented in reconfigurable hardware that rapidly clusters a half million documents. Documents and concepts are represented as vectors with 4000 dimensions. The circuit was implemented in Field Programmable Gate Array (FPGA) logic and uses four parallel cosine distance metrics to cluster document vectors together. An exploration of the effect of the integer …
Link Layer Support For Unified Radio Power Management In Wireless Sensor Networks, Master's Thesis, May 2007, Kevin Klues
Link Layer Support For Unified Radio Power Management In Wireless Sensor Networks, Master's Thesis, May 2007, Kevin Klues
All Computer Science and Engineering Research
Radio power management is of paramount concern in wireless sensor networks that must achieve long lifetimes on scarce amounts of energy. While a multitude of power management protocols have been proposed in the past, the lack of system support for flexibly integrating them with a diverse set of applications and network platforms has made them difficult to use. Instead of proposing yet another power management protocol, this thesis focuses on providing link layer support towards realizing a Unified Power Management Architecture (UPMA) for flexible radio power management in wireless sensor networks. In contrast to the monolithic approaches adopted by existing …
Price Of Asynchrony: Queuing Under Ideally Smooth Congestion Control, Maxim Podlesny, Sergey Gorinsky
Price Of Asynchrony: Queuing Under Ideally Smooth Congestion Control, Maxim Podlesny, Sergey Gorinsky
All Computer Science and Engineering Research
The ability of TCP (Transmission Control Protocol) or alternative congestion control algorithms to operate successfully in networks with small link buffers has recently become a subject of intensive research. In this paper, we investigate fundamental limitations on minimum buffer requirements for any congestion control. We present an idealized protocol where all flows always transmit at their fair rates. The ideally smooth congestion control causes link queuing only due to asynchrony of flow arrivals, which is intrinsic to computer networks. Our analysis and simulations for different distributions of flow interarrival times agree that the buffer size needed for a fixed loss …
Fair Efficiency, Or Low Average Delay Without Starvation, Christoph Jechlitschek, Sergey Gorinsky
Fair Efficiency, Or Low Average Delay Without Starvation, Christoph Jechlitschek, Sergey Gorinsky
All Computer Science and Engineering Research
Elastic applications are primarily interested in minimal delay achievable for their messages under current network load. In this paper, we investigate how to transmit such messages over a bottleneck link efficiently and fairly. While SRPT (Shortest Remaining Processing Time) is an optimally efficient algorithm that minimizes average delay of messages, large messages might starve under SRPT in heavy load conditions. PS (Processor Sharing) and ViFi (Virtual Finish Time First) are fair but yield higher average delays than under SRPT. We explore the class of fair algorithms further and prove that no online algorithm in this class is optimally efficient. Then, …
A Fingerspelling Sign Language Visualization , Carol S. Brickman
A Fingerspelling Sign Language Visualization , Carol S. Brickman
All Computer Science and Engineering Research
The goal of the Fingerspell Visualization Project is to research methods to improve learning of reading skills through sign language. The techniques are centered on Fingerspelling as the method to bridge stages of skill development. Visualization of a string of text in images of a hand performing the letters of the alphabet in standardized fingerspell sign language positions provide Full Motion Learning as opposed to learning from single pictures.
Lower Bounds On Queuing And Loss At Highly Multiplexed Links, Maxim Podlesny, Sergey Gorinsky
Lower Bounds On Queuing And Loss At Highly Multiplexed Links, Maxim Podlesny, Sergey Gorinsky
All Computer Science and Engineering Research
Explicit and delay-driven congestion control protocols strive to preclude overflow of link buffers by reducing transmission upon incipient congestion. In this paper, we explore fundamental limitations of any congestion control with respect to minimum queuing and loss achievable at highly multiplexed links. We present and evaluate an idealized protocol where all flows always transmit at equal rates. The ideally smooth congestion control causes link queuing only due to asynchrony of flow arrivals, which is intrinsic to computer networks. With overprovisioned buffers, our analysis and simulations for different smooth distributions of flow interarrival times agree that minimum queuing at a fully …
Hexa: Compact Data Structures For Faster Packet Processing, Sailesh Kumar, Jonathan Turner, Patrick Crowley, Michael Mitzenmacher
Hexa: Compact Data Structures For Faster Packet Processing, Sailesh Kumar, Jonathan Turner, Patrick Crowley, Michael Mitzenmacher
All Computer Science and Engineering Research
Directed graphs with edge labels are used in packet processing algorithms for a variety of network applications. In this paper we present a novel representation for such graph that significantly reduces the memory required for such graphs. This approach called History-based Encoding, eXecution and Addressing (HEXA) challenges the conventional assumption that graph data structures must store pointers of log2n bits to identify successor nodes. HEXA takes advantage of implict information to reduce the information that must be stored explicitly. We demonstrate that the binary tries used for IP route lookup can be implemented using just two bytes per stored prefix …
Leveraging Est Evidence To Automatically Predict Alternatively Spliced Genes, Master's Thesis, December 2006, Robert Zimmermann
Leveraging Est Evidence To Automatically Predict Alternatively Spliced Genes, Master's Thesis, December 2006, Robert Zimmermann
All Computer Science and Engineering Research
Current methods for high-throughput automatic annotation of newly sequenced genomes are largely limited to tools which predict only one transcript per gene locus. Evidence suggests that 20-50% of genes in higher eukariotic organisms are alternatively spliced. This leaves the remainder of the transcripts to be annotated by hand, an expensive time-consuming process. Genomes are being sequenced at a much higher rate than they can be annotated. We present three methods for using the alignments of inexpensive Expressed Sequence Tags in combination with HMM-based gene prediction with N-SCAN EST to recreate the vast majority of hand annotations in the D.melanogaster genome. …
Distributed Allocation Of Workflow Tasks In Manets, Rohan Sen, Gruia-Catalin Roman, Christopher Gill
Distributed Allocation Of Workflow Tasks In Manets, Rohan Sen, Gruia-Catalin Roman, Christopher Gill
All Computer Science and Engineering Research
When multiple participants work on a workflow that represents a large, collaborative activity, it is important to have a well defined process to determine the portions of the workflow that each participant is responsible for executing. In this paper, we describe a process and related algorithms required to assign tasks in a workflow, to hosts that are willing to carry out the execution of these tasks, and thereby contributing to the completion of the activity. This problem is a stylized form of the multi-processor scheduling algorithm which has been shown to be NP-Hard. Further complicating the issue is that we …
Efficient Fair Algorithms For Message Communication, Sergey Gorinsky, Eric J. Friedman, Shane Henderson, Christoph Jechlitschek
Efficient Fair Algorithms For Message Communication, Sergey Gorinsky, Eric J. Friedman, Shane Henderson, Christoph Jechlitschek
All Computer Science and Engineering Research
A computer network serves distributed applications by communicating messages between their remote ends. Many such applications desire minimal delay for their messages. Beside this efficiency objective, allocation of the network capacity is also subject to the fairness constraint of not shutting off communication for any individual message. Processor Sharing (PS) is a de facto standard of fairness but provides significantly higher average delay than Shortest Remaining Processing Time (SRPT), which is an optimally efficient but unfair algorithm. In this paper, we explore efficient fair algorithms for message communication where fairness means that no message is delivered later than under PS. …
Context-Aware Publish Subscribe In Mobile Ad Hoc Networks, Davide Frey, Gruia-Catalin Roman
Context-Aware Publish Subscribe In Mobile Ad Hoc Networks, Davide Frey, Gruia-Catalin Roman
All Computer Science and Engineering Research
The publish-subscribe communication paradigm is enjoying increasing popularity thanks to its ability to simplify the development of complex distributed applications. However, existing solutions in the publish-subscribe domain address only part of the challenges associated with the development of applications in dynamic scenarios such as mobile ad hoc networks. Mobile applications must be able to assist users in a variety of situations, responding not only to their inputs but also to the characteristics of the environment in which they operate. In this paper, we address these challenges by extending the publish-subscribe paradigm with the ability to manage and exploit context information …
Roadmap Analysis Of Protein-Protein Interactions. Master's Thesis, August 2007, Brian C. Haynes
Roadmap Analysis Of Protein-Protein Interactions. Master's Thesis, August 2007, Brian C. Haynes
All Computer Science and Engineering Research
The ability to effectively model the interaction between proteins is an important and open problem. In molecular biology it is well accepted that from sequence arises form and from form arises function but relating structure to function remains a challenge. The function of a given protein is defined by its interactions. Likewise a malfunction or a change in protein-protein interactions is a hallmark of many diseases. Many researchers are studying the mechanisms of protein-protein interactions and one of the overarching goals of the community is to predict whether two proteins will bind, and if so what the final conformation will …
Perpetual: Byzantine Fault Tolerance For Federated Distributed Applications, Sajeeva L. Pallemulle, Haraldur D. Thorvaldsson, Kenneth J. Goldman
Perpetual: Byzantine Fault Tolerance For Federated Distributed Applications, Sajeeva L. Pallemulle, Haraldur D. Thorvaldsson, Kenneth J. Goldman
All Computer Science and Engineering Research
Modern distributed applications rely upon the functionality of services from multiple providers. Mission-critical services, possibly shared by multiple applications, must be replicated to guarantee correct execution and availability in spite of arbitrary (Byzantine) faults. Furthermore, shared services must enforce strict fault isolation policies to prevent cascading failures across organizational and application boundaries. Most existing protocols for Byzantine fault-tolerant execution do not support interoperability between replicated services while others provide poor fault isolation. Moreover, existing protocols place impractical limitations on application development by disallowing long-running threads of computation, asynchronous operation invocation, and asynchronous request processing. We present Perpetual, a protocol that …