24684227
Adaptive Control of Anytime Algorithm Parameters
11255660
A flexible contention resolution scheme for QoS provisioning in optical burst switching networks
Contention resolution is a major issue in bufferless optical burst switching (OBS) networks. The existing contention resolution schemes consider priority and arrival time to resolve contention. For most multimedia applications priority and delay are key parameters for QoS provisioning. In this paper, we propose a new signaling protocol for reducing contention in OBS networks and consider three parameters, namely, priority of the burst, number of hops traversed, and burst size into account to resolve contention. The source node in the proposed protocol can be informed of the contention up to halfway along the path of the burst, and thus, can reschedule the burst accordingly. The scheme is adaptable to both prioritized and delay constrained traffic. We call the scheme OBS-Flex. For selecting a data channel, we propose three channel selection algorithms, namely, Least Recently Used (LRU), First Fit (FF), and Priority Set (PS). We simulate OBS-Flex and compare with preemptive priority just-enough-time (PPJET) contention resolution scheme. We show that OBS-Flex outperforms PPJET in terms of burst loss rates. For simulation, we have considered Poisson and bursty traffic models.
6342150
Frame based fair multiprocessor scheduler: a fast fair algorithm for real-time embedded systems
This paper presents frame based fair multiprocessor scheduler (FBFMS) which provides accurate real-time proportional fair scheduling for a set of dynamic tasks on a symmetric multiprocessor environment with O(1) scheduling overhead. FBFMS meets these seemingly contradictory goals by applying the benefits of virtual time round-robin scheduling mechanism along with a frame based scheduling approach. Simulation results show that the algorithm provides 2.5 to 26 times speedup (over O(lg n) complexity schedulers) with distortion in fairness less than 1% in most cases, and less than 15% in the worst case.
39625638
Distributed dynamic slicing of Java programs
We propose a novel dynamic slicing technique for distributed Java programs. We first construct the intermediate representation of a distributed Java program in the form of a set of Distributed Program Dependence Graphs (DPDG). We mark and unmark the edges of the DPDG appropriately as and when dependencies arise and cease during run-time. Our algorithm can run parallely on a network of computers, with each node in the network contributing to the dynamic slice in a fully distributed fashion. Our approach does not require any trace files to be maintained. Another advantage of our approach is that a slice is available even before a request for a slice is made. This appreciably reduces the response time of slicing commands. We have implemented the algorithm in a distributed environment. The results obtained from our experiments show promise.
14984794
A Local Search Heuristic for Biobjective Intersecting Geometric Graphs
In this work, we consider the problem of constructing spanning trees from two geometric graphs corresponding to two nets, each with multiple terminals, with a goal to minimize the total edge cost and the number of intersections among the edges of the two trees. Such an optimization problem is computationally hard for which no efficient algorithm or good heuristic is known to exist. Additionally, in a biobjective setting, the major challenge to solve a problem is to obtain many representative diverse solutions across the (near-) optimal Pareto-front. We present a local search based heuristic to find near-optimal Pareto-front in the feasible solution space. Each element of this solution set is a tuple of two spanning trees corresponding to the given geometric graphs. The heuristic is shown to give superior results over the existing stochastic technique
5790802
Object-oriented symbol management in syntax-directed compiler systems
Each symbol in a source program has a series of attributes that govern the operations performed on it. In this paper, we explore object-oriented techniques for representing the attributes of symbols and translating the operations performed on them. This approach is shown superior in memory and run-time speed to the procedural style traditionally used for writing compilers. We demonstrate object-oriented symbol management in a compiler for an arithmetic subset of C. We have used C++ --- a single-dispatching language --- to implement the same, but we emphasize the need for multiple dispatching to develop programs in a heavily-object-oriented style.
9633354
Real-time personalized sports video filtering and summarization
We demonstrate a real-time fully automated software system for filtering important events in sports video. Events represent occurrences of actions or state changes in video content. In the current prototype, we demonstrate detection of pitching in baseball and serving in tennis. For wireless video applications, we propose and apply a unique notion of content-based adaptive streaming,in which video encoding rate and media modality is dynamically varied according to the event filtering results. Our system includes an event detection module, an adaptive encoding module, and a buffer management module for adaptive streaming. We achieve the real-time performance by exploring compressed-domain techniques and multi-stage multi-resolution content-analysis processes.
960483
Selecting devices for aggregation
As intelligent devices become affordable and wireless infrastructure becomes pervasive, the potential to combine, or aggregate, device functionality to provide a user with a better experience grows. Often, there will be multiple devices providing similar functionality that the user will have to choose from for the aggregation. We present the design and prototype implementation of a system for automatic selection of devices for aggregation in a dynamic environment. It allows a user to express trade-offs between the quality of device attributes, user distraction, and aggregation stability. This approach enables a user to have a richer experience without having to constantly worry about the device and the environment details.
10511055
RF2ID: A Reliable Middleware Framework for RFID Deployment
The reliability of RFID systems depends on a number of factors including: RF interference, deployment environment, configuration of the readers, and placement of readers and tags. While RFID technology is improving rapidly, a reliable deployment of this technology is still a significant challenge impeding widespread adoption. This paper investigates system software solutions for achieving a highly reliable deployment that mitigates inherent unreliability in RFID technology. We have developed (1) a virtual reader abstraction to improve the potentially error-prone nature of reader generated data (2) a novel path abstraction to capture the logical flow of information among virtual readers. We have designed and implemented an RFID middleware: RF2ID (reliable framework for radio frequency identification) to organize and support queries over data streams in an efficient manner. Prototype implementation using both RFID readers and simulated readers using an empirical model of RFID readers show that RF2ID is able to provide high reliability and support path-based object detection.
22550674
Timing-sync protocol for sensor networks
Wireless ad-hoc sensor networks have emerged as an interesting and important research area in the last few years. The applications envisioned for such networks require collaborative execution of a distributed task amongst a large set of sensor nodes. This is realized by exchanging messages that are time-stamped using the local clocks on the nodes. Therefore, time synchronization becomes an indispensable piece of infrastructure in such systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for sensor networks.In this paper, we present Timing-sync Protocol for Sensor Networks (TPSN) that aims at providing network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We implement our algorithm on Berkeley motes and show that it can synchronize a pair of neighboring motes to an average accuracy of less than 20ms. We argue that TPSN roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS) and verify this by implementing RBS on motes. We also show the performance of TPSN over small multihop networks of motes and use simulations to verify its accuracy over large-scale networks. We show that the synchronization accuracy does not degrade significantly with the increase in number of nodes being deployed, making TPSN completely scalable.
7841699
Dynamic data fusion for future sensor networks
DFuse is an architectural framework for dynamic application-specified data fusion in sensor networks. It bridges an important abstraction gap for developing advanced fusion applications that takes into account the dynamic nature of applications and sensor networks. Elements of the DFuse architecture include a fusion API, a distributed role assignment algorithm that dynamically adapts the placement of the application task graph on the network, and an abstraction migration facility that aids such dynamic role assignment. Experimental evaluations show that the API has low overhead, and simulation results show that the role assignment algorithm significantly increases the network lifetime over static placement.