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

Computer Sciences Commons

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

Washington University in St. Louis

Discipline
Keyword
Publication Year
Publication
Publication Type

Articles 271 - 300 of 830

Full-Text Articles in Computer Sciences

A Simple Algorithm For Triconnectivity Of A Multigraph, Abusayeed Saifullah, Alper Ungor Jan 2009

A Simple Algorithm For Triconnectivity Of A Multigraph, Abusayeed Saifullah, Alper Ungor

All Computer Science and Engineering Research

Vertex-connectivity and edge-connectivity represent the extent to which a graph is connected. Study of these key properties of graphs plays an important role in varieties of computer science applications. Recent years have witnessed a number of linear time 3-edge-connectivity algorithms - with increasing simplicity. In contrast, the state-of-the-art algorithm for 3-vertex-connectivity due to Hopcroft and Tarjan lacks the simplicity in the sense of ease of implementation as well as the number of passes over the graph although its time and space complexity is theoretically linear. In this paper, we propose a linear time reduction from 3-vertex-connectivity to 3-edge- connectivity of …


Defending Against Distributed Denial-Of-Service Attacks With Weight-Fair Router Throttling, Abusayeed Saifullah Jan 2009

Defending Against Distributed Denial-Of-Service Attacks With Weight-Fair Router Throttling, Abusayeed Saifullah

All Computer Science and Engineering Research

A high profile internet server is always a target of denial-of-service attacks. In this paper, we propose a novel technique for protecting an internet server from distributed denial-of-service attacks. The defense mechanism is based on a distributed algorithm that performs weight-fair throttling at the upstream routers. The throttling is weight-fair because the traffics destined for the server are controlled increased or decreased ) by the leaky-buckets at the routers based on the number of users connected, directly or through other routers, to each router. To the best of our knowledge, this is the first weight-fair technique for saving an internet …


Architectures For The Future Networks And The Next Generation Internet: A Survey, Subharthi Paul, Jianli Pan, Raj Jain Jan 2009

Architectures For The Future Networks And The Next Generation Internet: A Survey, Subharthi Paul, Jianli Pan, Raj Jain

All Computer Science and Engineering Research

Networking research funding agencies in the USA, Europe, Japan, and other countries are encouraging research on revolutionary networking architectures that may or may not be bound by the restrictions of the current TCP/IP based Internet. We present a comprehensive survey of such research projects and activities. The topics covered include various testbeds for experimentations for new architectures, new security mechanisms, content delivery mechanisms, management and control frameworks, service architectures, and routing mechanisms. Delay/Disruption tolerant networks, which allow communications even when complete end-to-end path is not available, are also discussed.


Scalable Scheduling Policy Design For Open Soft Real-Time Systems, Robert Glaubius, Terry Tidewell, Braden Sidoti, David Pilla, Justin Meden, Christopher Gill, William D. Smart Jan 2009

Scalable Scheduling Policy Design For Open Soft Real-Time Systems, Robert Glaubius, Terry Tidewell, Braden Sidoti, David Pilla, Justin Meden, Christopher Gill, William D. Smart

All Computer Science and Engineering Research

Open soft real-time systems, such as mobile robots, must respond adaptively to varying operating conditions, while balancing the need to perform multiple mission specific tasks against the requirement that those tasks complete in a timely manner. Setting and enforcing a utilization target for shared resources is a key mechanism for achieving this behavior. However, because of the uncertainty and non-preemptability of some tasks, key assumptions of classical scheduling approaches do not hold. In previous work we presented foundational methods for generating task scheduling policies to enforce proportional resource utilization for open soft real-time systems with these properties. However, these methods …


Scheduling Design With Unknown Execution Time Distributions Or Modes, Robert Glaubius, Terry Tidwell, Christopher Gill, William D. Smart Jan 2009

Scheduling Design With Unknown Execution Time Distributions Or Modes, Robert Glaubius, Terry Tidwell, Christopher Gill, William D. Smart

All Computer Science and Engineering Research

Open soft real-time systems, such as mobile robots, experience unpredictable interactions with their environments and yet must respond both adaptively and with reasonable temporal predictability. Because of the uncertainty inherent in such interactions, many of the assumptions of the real-time scheduling techniques traditionally used to ensure predictable timing of system actions do not hold in those environments. In previous work we have developed novel techniques for scheduling policy design where up-front knowledge of execution time distributions can be used to produce both compact representations of resource utilization state spaces and efficient optimal scheduling policies over those state spaces. This paper …


Enhanced Coordination In Sensor Networks Through Flexible Service Provisioning, Chien-Liang Fok, Gruia-Catalin Roman, Chenyang Lu Jan 2009

Enhanced Coordination In Sensor Networks Through Flexible Service Provisioning, Chien-Liang Fok, Gruia-Catalin Roman, Chenyang Lu

All Computer Science and Engineering Research

Heterogeneous wireless sensor networks represent a challenging programming environment. Servilla addresses this by offering a new middleware framework that provides service provisioning. Using Servilla, developers can construct platform-independent applications over a dynamic set of devices with diverse computational resources and sensors. A salient feature of Servilla is its support for dynamic discovery and binding to local and remote services, which enables flexible and energy-efficient in-network collaboration among heterogeneous devices. Furthermore, Servilla provides a modular middleware architecture that can be easily tailored for devices with a wide range of resources, allowing resource-constrained devices to provide services while leveraging the capabilities of …


Volumeviewer: An Interactive Tool For Fitting Surfaces To Volume Data, Ross Sowell, Lu Liu, Tao Ju, Cindy Grimm, Christopher Abraham, Garima Gokhroo, D Low Jan 2009

Volumeviewer: An Interactive Tool For Fitting Surfaces To Volume Data, Ross Sowell, Lu Liu, Tao Ju, Cindy Grimm, Christopher Abraham, Garima Gokhroo, D Low

All Computer Science and Engineering Research

Recent advances in surface reconstruction algorithms allow surfaces to be built from contours lying on non-parallel planes. Such algorithms allow users to construct surfaces of similar quality more efficiently by using a small set of oblique contours, rather than many parallel contours. However, current medical imaging systems do not provide tools for sketching contours on oblique planes. In this paper, we take the first steps towards bridging the gap between the new surface reconstruction technologies and putting those methods to use in practice. We develop a novel interface for modeling surfaces from volume data by allowing the user to sketch …


Robust Sensor Networks In Homes Via Reactive Channel Hopping, Mo Sha, Greg Hackmann, Chenyang Lu Jan 2009

Robust Sensor Networks In Homes Via Reactive Channel Hopping, Mo Sha, Greg Hackmann, Chenyang Lu

All Computer Science and Engineering Research

Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy and assisted living. A key challenge faced in deploying robust wireless sensor networks (WSNs) for home automation applications is the need to provide long-term, reliable operation in the face of the varied sources of interference found in typical residential settings. To better understand the channel dynamics in these environments, we performed an in-depth empirical study of the performance of HANs in ten real-life apartments. Our empirical study leads to several key insights into designing robust HANs for residential environments. …


Open Workflows: Context-Dependent Construction And Execution In Mobile Wireless Settings, Louis Thomas, Justin Wilson, Grui-Catalin Roman, Christopher Gill Jan 2009

Open Workflows: Context-Dependent Construction And Execution In Mobile Wireless Settings, Louis Thomas, Justin Wilson, Grui-Catalin Roman, Christopher Gill

All Computer Science and Engineering Research

Existing workflow middleware executes tasks orchestrated by rules defined in a carefully handcrafted static graph. Workflow management systems have proved effective for service-oriented business automation in stable, wired infrastructures. We introduce a radically new paradigm for workflow construction and execution called open workflow to support goal-directed coordination among physically mobile people and devices that form a transient community over an ad hoc wireless network. The quintessential feature of the open workflow paradigm is dynamic construction and execution of custom, context-specific workflows in response to unpredictable and evolving circumstances by exploiting the knowledge and services available within a given spatiotemporal context. …


Partial Program Admission, Michael Wilson, Ron Cytron, Jon Turner Jan 2009

Partial Program Admission, Michael Wilson, Ron Cytron, Jon Turner

All Computer Science and Engineering Research

Real-time systems on non-preemptive platforms require a means of bounding the execution time of programs for admission purposes. Worst-Case Execution Time (WCET) is most commonly used to bound program execution time. While bounding a program’s WCET statically is possible, computing its true WCET is difficult.We present a new technique we call partial program admission, a means of statically enforcing an otherwise untrusted assertion of WCET without adding runtime overhead, by means of code duplication. We apply this technique to real programs from the virtual networking arena and present the results.


Design Of An Extensible Network Testbed With Heterogeneous Components, Charlie Wisemen, Jyoti Parwatikar, Ken Wong, John Dehart, Jonathan Turner Jan 2009

Design Of An Extensible Network Testbed With Heterogeneous Components, Charlie Wisemen, Jyoti Parwatikar, Ken Wong, John Dehart, Jonathan Turner

All Computer Science and Engineering Research

Virtualized network infrastructures are currently deployed in both research and commercial contexts. The complexity of the virtualization layer varies greatly in different deployments, ranging from cloud computing environments, to carrier Ethernet applications using stacked VLANs, to networking testbeds. In all of these cases, there are many users sharing the resources of one provider, where each user expects their resources to be isolated from all other users. Our work in this area is focused on network testbeds. In particular, we present the design of the latest version of the Open Network Laboratory (ONL) testbed. This redesign generalizes the underlying infrastructure to …


Self-Stabilizing Computation Of 3-Edge-Connected Components, Abusayeed Saifullah, Yung Tsin Jan 2009

Self-Stabilizing Computation Of 3-Edge-Connected Components, Abusayeed Saifullah, Yung Tsin

All Computer Science and Engineering Research

No abstract provided.


Non-Programmers Identifying Functionality In Unfamiliar Code: Strategies And Barriers, Paul Gross, Caitlin Kelleher Jan 2009

Non-Programmers Identifying Functionality In Unfamiliar Code: Strategies And Barriers, Paul Gross, Caitlin Kelleher

All Computer Science and Engineering Research

Source code on the web is a widely available and potentially rich learning resource for non-programmers. However, unfamiliar code can be daunting to end-users without programming experience. This paper describes the results of an exploratory study in which we asked non-programmers to find and modify the code responsible for specific functionality within unfamiliar programs. We present two interacting models of how non-programmers approach this problem: the Task Process Model and the Landmark-Mapping model. Using these models, we describe code search strategies non-programmers employed and the difficulties they encountered. Finally, we propose guidelines for future programming environments that support non-programmers in …


Adaptive Service Provisioning For Wireless Sensor Networks, Chien-Liang Fok, Gruia-Catalin Roman, Chenyang Lu Jan 2009

Adaptive Service Provisioning For Wireless Sensor Networks, Chien-Liang Fok, Gruia-Catalin Roman, Chenyang Lu

All Computer Science and Engineering Research

Service provisioning has gained significant attention as a promising programming model for heterogeneous wireless sensor networks. Its key idea is to exploit the decoupling of service providers and consumers to enable platform-independent applications that are dynamically bound to platform-specific services. We explore novel adaptive service binding strategies that are able to cope with network dynamics and to promote energy conservation. To achieve this goal, we developed policies and algorithms that automatically switch providers in response to network topology changes and adapt application behavior when opportunities for energy savings surface. The latter is accomplished by providing limited information about the energy …


Performance-Engineered Network Overlays For High Quality Interaction In Virtual Worlds, Mart Haitjema, Ritun Patney, Jon Turner, Charlie Wiseman, John Dehart Jan 2009

Performance-Engineered Network Overlays For High Quality Interaction In Virtual Worlds, Mart Haitjema, Ritun Patney, Jon Turner, Charlie Wiseman, John Dehart

All Computer Science and Engineering Research

Overlay hosting systems such as PlanetLab, and cloud computing environments such as Amazon’s EC2, provide shared infrastructures within which new applications can be developed and deployed on a global scale. This paper ex-plores how systems of this sort can be used to enable ad-vanced network services and sophisticated applications that use those services to enhance performance and provide a high quality user experience. Specifically, we investigate how advanced overlay hosting environments can be used to provide network services that enable scalable virtual world applications and other large-scale distributed applications requiring consistent, real-time performance. We propose a novel network architecture called …


Reliable Patient Monitoring: A Clinical Study In A Step-Down Hospital Unit, Octav Chipara, Chenyang Lu, Thomas C. Bailey, Gruia-Catalin Roman Jan 2009

Reliable Patient Monitoring: A Clinical Study In A Step-Down Hospital Unit, Octav Chipara, Chenyang Lu, Thomas C. Bailey, Gruia-Catalin Roman

All Computer Science and Engineering Research

This paper presents the design, deployment, and empirical study of a wireless clinical monitoring system that collects pulse and oxygen saturation readings from patients. The primary contribution of this paper is an in-depth clinical trial that assesses the feasibility of wireless sensor networks for patient monitoring in general (non-ICU) hospital units. The trial involved 32 patients monitored in a step-down cardiology unit at Barnes-Jewish Hospital, St. Louis. During a total of 31 days of monitoring, the network achieved high reliability (median 99.92%, range 95.21% - 100%). The overall reliability of the system was dominated by sensing reliability (median 80.55%, range …


Achieving Coordination Through Dynamic Construction Of Open Workflows, Louis Thomas, Justin Wilson, Grui-Catalin Roman, Christopher Gill Jan 2009

Achieving Coordination Through Dynamic Construction Of Open Workflows, Louis Thomas, Justin Wilson, Grui-Catalin Roman, Christopher Gill

All Computer Science and Engineering Research

Workflow middleware executes tasks orchestrated by rules defined in a carefully handcrafted static graph. Workflow management systems have proved effective for service-oriented business automation in stable, wired infrastructures. We introduce a radically new paradigm for workflow construction and execution called open workflow to support goal-directed coordination among physically mobile people and devices that form a transient community over an ad hoc wireless network. The quintessential feature of the open workflow paradigm is dynamic construction of custom, context-specific workflows in response to unpredictable and evolving circumstances by exploiting the knowledge and services available within a given spatiotemporal context. This paper introduces …


Globally Clocked Magnetic Logic Circuits, Michael Hall, Albrecht Jander, Roger D. Chamberlain, Pallavi Dhagat Jan 2009

Globally Clocked Magnetic Logic Circuits, Michael Hall, Albrecht Jander, Roger D. Chamberlain, Pallavi Dhagat

All Computer Science and Engineering Research

Magnetic spin valve devices enable the design of logic and memory elements that are suitable for use when constructing digital systems. A master-slave flip-flop design is proposed that can be clocked using an externally applied global magnetic field. With an external global clock, the digital system no longer needs to deliver the clock on-chip, thereby eliminating the need for a clock distribution network. We assess the power, area, and speed implications associated with the ability to eliminate the clock distribution network on a hybrid CMOS-magnetologic digital system.


Radio Mapping For Indoor Environments, Octav Chipara, Gregory Hackmann, Chenyang Lu, William D. Smart Jan 2009

Radio Mapping For Indoor Environments, Octav Chipara, Gregory Hackmann, Chenyang Lu, William D. Smart

All Computer Science and Engineering Research

The efficient deployment and robust operation of many sensor network applications depend on deploying relays to ensure wireless coverage. Radio mapping aims to predict network coverage based on a small number of link measurements from sampled locations. Radio mapping is particularly challenging in complex indoor environments where walls significantly affect radio signal propagation. This paper makes the following key contributions to indoor radio mapping. First, our empirical study in an office building identifies a wall-classification model as the most effective model for indoor environments due to its balance between model complexity and accuracy. Second, we propose a practical algorithm to …


Supporting Collaboration In Mobile Environments, Rohan Sen Aug 2008

Supporting Collaboration In Mobile Environments, Rohan Sen

All Computer Science and Engineering Research

Continued rapid improvements in the hardware capabilities of mobile computing devices is driving a parallel need for a paradigm shift in software design for such devices with the aim of ushering in new classes of software applications for devices of the future. One such class of software application is collaborative applications that seem to reduce the burden and overhead of collaborations on human users by providing automated computational support for the more mundane and mechanical aspects of a cooperative effort. This dissertation addresses the research and software engineering questions associated with building a workflow-based collaboration system that can operate across …


Modeling Timed Component-Based Real-Time Systems, Huang-Ming Huang, Christopher Gill Jan 2008

Modeling Timed Component-Based Real-Time Systems, Huang-Ming Huang, Christopher Gill

All Computer Science and Engineering Research

Component based middleware helps to facilitate software reuse by separating application-specific concerns into modular components that are shielded from the concerns of other components and from the common concerns addressed by underlying middleware services. In real-time systems, concerns such as invocation rates, execution latencies, deadlines, and concurrency semantics cross-cut multiple component and middleware abstractions. Thus, the verification of these systems must consider features of the application components (e.g., their execution latencies and relative invocation rates) and of the supporting middleware (e.g., concurrency and scheduling) together. However, existing approaches only address a sub-set of the features that must be modeled in …


Scheduling For Reliable Execution In Autonomic Systems, Terry Tidwell, Robert Glaubius, Christopher Gill, William D. Smart Jan 2008

Scheduling For Reliable Execution In Autonomic Systems, Terry Tidwell, Robert Glaubius, Christopher Gill, William D. Smart

All Computer Science and Engineering Research

Scheduling the execution of multiple concurrent tasks on shared resources such as CPUs and network links is essential to ensuring the reliable operation of many autonomic systems. Well known techniques such as rate-monotonic scheduling can offer rigorous timing and preemption guarantees, but only under assumptions (i.e., a fixed set of tasks with well-known execution times and invocation rates) that do not hold in many autonomic systems. New hierarchical scheduling techniques are better suited to enforce the more flexible execution constraints and enforcement mechanisms that are required for autonomic systems, but a rigorous foundation for verifying and enforcing concurrency and timing …


Partial Program Admission By Path Enumeration, Michael Wilson, Ron Cytron, Jon Turner Jan 2008

Partial Program Admission By Path Enumeration, Michael Wilson, Ron Cytron, Jon Turner

All Computer Science and Engineering Research

Real-time systems on non-preemptive platforms require a means of bounding the execution time of programs for admission purposes. Worst-Case Execution Time (WCET) is most commonly used to bound program execution time. While bounding a program's WCET statically is possible, computing its true WCET is difficult without significant semantic knowledge. We present an algorithm for partial program admission, suited for non-preemptive platforms, using dynamic programming to perform explicit enumeration of program paths. Paths - possible or not - are bounded by the available execution time and admitted on a path-by-path basis without requiring semantic knowledge of the program beyond its Control …


Practical Schedulability Analysis For Generalized Sporadic Tasks In Distributed Real-Time Systems, Yuanfang Zhang, Donald K. Krecker, Christopher Gill, Chenyang Lu, Guatam H. Thaker Jan 2008

Practical Schedulability Analysis For Generalized Sporadic Tasks In Distributed Real-Time Systems, Yuanfang Zhang, Donald K. Krecker, Christopher Gill, Chenyang Lu, Guatam H. Thaker

All Computer Science and Engineering Research

Existing off-line schedulability analysis for real-time systems can only handle periodic or sporadic tasks with known minimum inter-arrival times. Modeling sporadic tasks with fixed minimum inter-arrival times is a poor approximation for systems in which tasks arrive in bursts, but have longer intervals between the bursts. In such cases, schedulability analysis based on the existing sporadic task model is pessimistic and seriously overestimates the task's time demand. In this paper, we propose a generalized sporadic task model that characterizes arrival times more precisely than the traditional sporadic task model, and we develop a corresponding schedulability analysis that computes tighter bounds …


Local Neighborhoods For Shape Classification And Normal Estimation, Cindy Grimm, William Smart Jan 2008

Local Neighborhoods For Shape Classification And Normal Estimation, Cindy Grimm, William Smart

All Computer Science and Engineering Research

We introduce the concept of local neighborhoods, a generalization of the one-ring on a mesh to unlabeled 3D data points arising from sampling a 2D surface embedded in 3D. The local neighborhood supports both local shape classification and robust normal estimation. In particular, local neighborhoods out-perform traditional approaches in unevenly sampled, curved regions. We show that the local neighborhood can be used in place of a full mesh structure for applications such as smoothing, moving least-squares reconstruction, and parameterization. Longer version of paper submitted to CAGD


Financial Monte Carlo Simulation On Architecturally Diverse Systems, Naveen Singla, Michael Hall, Berkley Shands, Roger D. Chamberlain Jan 2008

Financial Monte Carlo Simulation On Architecturally Diverse Systems, Naveen Singla, Michael Hall, Berkley Shands, Roger D. Chamberlain

All Computer Science and Engineering Research

Computational finance relies heavily on the use of Monte Carlo simulation techniques. However, Monte Carlo simulation is computationally very demanding. We demonstrate the use of architecturally diverse systems to accelerate the performance of these simulations, exploiting both graphics processing units and field-programmable gate arrays. Performance results include a speedup of 74× relative to an 8 core multiprocessor system (180× relative to a single processor core).


A Practical Schedulability Analysis For Generalized Sporadic Tasks In Distributed Real-Time Systems, Yuanfang Zhang, Donald K. Krecker, Christopher Gill, Chenyang Lu, Guatam H. Thakar Jan 2008

A Practical Schedulability Analysis For Generalized Sporadic Tasks In Distributed Real-Time Systems, Yuanfang Zhang, Donald K. Krecker, Christopher Gill, Chenyang Lu, Guatam H. Thakar

All Computer Science and Engineering Research

Existing off-line schedulability analysis for real-time systems can only handle periodic or sporadic tasks with known minimum inter-arrival times. Modeling sporadic tasks with fixed minimum inter-arrival times is a poor approximation for systems in which tasks arrive in bursts, but have longer intervals between the bursts. In such cases, schedulability analysis based on the existing sporadic task model is pessimistic and seriously overestimates the task's time demand. In this paper, we propose a generalized sporadic task model that characterizes arrival times more precisely than the traditional sporadic task model, and we develop a corresponding schedulability analysis that computes tighter bounds …


Reliable Data Collection From Mobile Users For Real-Time Clinical Monitoring, Octav Chipara, Christopher Brooks, Sangeeta Bhattacharya, Chenyang Lu Jan 2008

Reliable Data Collection From Mobile Users For Real-Time Clinical Monitoring, Octav Chipara, Christopher Brooks, Sangeeta Bhattacharya, Chenyang Lu

All Computer Science and Engineering Research

Real-time patient monitoring is critical to early detection of clinical patient deterioration in general hospital wards. A key challenge in such applications is to reliably deliver sensor data from mobile patients. We present an empirical analysis on the reliability of data collection from wireless pulse oximeters attached to users. We observe that most packet loss occur from mobile users to their first-hop relays. Based on this insight we developed the Dynamic Relay Association Protocol (DRAP), a simple and effective mechanism for dynamically discovering the right relays for wireless sensors attached to mobile users. DRAP enables highly reliable data collection from …


Real-Time Performance And Middleware On Multicore Linux Platforms, Yuanfang Zhang, Christopher Gill, Chenyang Lu Jan 2008

Real-Time Performance And Middleware On Multicore Linux Platforms, Yuanfang Zhang, Christopher Gill, Chenyang Lu

All Computer Science and Engineering Research

An increasing number of distributed real-time applications are running on multicore platforms. However, existing real-time middleware (e.g., Real-Time CORBA) lacks support for scheduling soft real-time tasks on multicore platforms while guaranteeing their time constraints will be satisfied. This paper makes three contributions to the state of the art in real-time system software for multicore platforms. First, it offers what is to our knowledge the first experimental analysis of real-time performance for vanilla Linux primitives on multicore platforms. Second, it presents MC-ORB, the first real-time object request broker (ORB), designed to exploit the features of multicore platforms, with admission control and …


Verification Of Component-Based Distributed Real-Time Systems, Huang-Ming Huang, Christopher Gill Jan 2008

Verification Of Component-Based Distributed Real-Time Systems, Huang-Ming Huang, Christopher Gill

All Computer Science and Engineering Research

Component-based software architectures enable reuse by separating application-specific concerns into modular components that are shielded from each other and from common concerns addressed by underlying services. Even so, concerns such as invocation rates, execution latencies, deadlines, and concurrency and scheduling semantics still cross-cut component boundaries in many real-time systems. Verification of these systems therefore must consider how composition of components relates to timing, resource utilization, and other properties. However, existing approaches only address a sub-set of the concerns that must be modeled in component-based distributed real-time systems, and a new more comprehensive approach is thus needed. To address that need, …