Selected Abstracts

My research interests are distributed systems, networking, and wireless multihop sensor networks. I have related interests in mobile and pervasive computing.

Flexible Power Scheduling
    a network protocol for radio power scheduling in wireless sensor networks

Flexible Power Scheduling (FPS) is a novel architectural approach for reducing radio power consumption in wireless sensor networks through traffic scheduling. The approach uses a decentralized algorithm to schedule entire data flows, not packets, at the network layer across multiple hops. The scheduling is based on time-division at the network layer, rather than the MAC layer, to achieve significant power savings, reduced contention, and increased multihop throughput and fairness. Energy savings are achieved by powering down nodes during idle times identified through dynamic scheduling. FPS is implemented in TinyOS and has been evaluated on two real-world sensor network applications, TinyDB and GDI, and three hardware platforms, mica|mica2|mica2dot. We show that a  power savings of 4.3x for a 35-mote TinyDB deployment can be achieved compared with the existing power management of TinyDB (applicaton-level duty cycling), and a 160x power savings over no power management. In in-lab experiments comparing GDI/fps with GDI/low-power-listening, FPS has increased yields by 12% and lower power consumption by a factor of 4.6X over low-power-listening. We also present experiments that show a 3x reduction in contention, a 3-4x improvement for throughput for multihop flows, and a significant increase in fairness across multihop flows. 

FPS Project Page
My most recent talk on Network Power Scheduling .
Selected code available at  SourceForge TinyOS Project.
       Scheduled Queuing and Buffer Management:   tinyos-1.x/contrib/ucb/tos/lib/BufferManager
       Pseudo-Random Number Generation:             tinyos-2.x/tos/system/,

Using Pthreads in Parallel Computing

"Pthread Parallel K-means" [pdf] December 2001

K-means is a popular non-hierarchical method for clustering large data sets. The time requirements increase linearly with the size of the data set which make it paticulary suited for extremely large data sets.such as those found in digital libraries. The method was developed by McQueen in 1967. In our project we take a uniprocessor k-means algorithm and implement a parallel k-means algorithm using pthreads. The algorithm we use is from the Normalized Cuts (Ncuts) code base of the Vision Group at UC Berkeley. The parellel implementation demonstrated good speedup and improved performance.

VideoAnnotation Library

"Active Learning for Video Annotation" [pdf],  technical report TJ Watson, August 2001

In this paper, we present the design and implemention of  the Video Annotation Library. VAL interfaces with the IBM VideoAnn annotation tool and is designed to aide in the semantic labeling of video and image databases using  active learning techniques.  A list of confidence values and nearest neighbbor values is maintained for each video segment in the VideoAnn database. A variety of similarity measures are used interchangeably to create hierarchies (or cluster trees) of features of each video. The learning approach proposes sample video segments to the user for annotation and updates the database with the new annotations. It then uses its accumulative knowledge to label the rest of the database, after which it proposes new samples for the user to annotate. The proposed samples are selected by their knowledge gain to the active learner.

Master's Thesis, May 2001

"A B-tree For Distributed Data Structures" [ps] (errata) [ppt]  [code]
This paper presents the design and implementation of a single node b-tree storage layer for Ninja Distributed Data Structures (Gribble et al.). The implementation follows the finite state machine (FSM) programming model used in DDS and described by the Ninja Project. The key features of the b-tree design are a lock-free and non-blocking implementation.  Control-flow based concurrency control (as opposed to lock-based concurrency control) manages concurrency using non-blocking FSMs and queues. Performance measurements show the b-tree scales  well and exhibits graceful degradation under heavy loads. The in-and-out-of-core measurements on the DDS Buffer Cache showed the primary contributor to latency was not I/O, but  rather computation. The CPU costs for traversing the b-tree index are the dominating costs.

"Wide Area Events Using Distributed Data Structures" ( ppt ) ( PSN interfaces )
The Distributed Data Structure (DDS) API is a powerful abstraction on which to easily build cluster applications using reusable components. We show how the DDS can support the Publish-Subscribe-Notify class of internet services efficiently. As an example, the "Food in the Woz" application constructs a channel that notifies subscribers when food is available in the Woz lounge. The channel records user-preferences (such as the device that the user wishes to be contacted on) and delivers food events to subscribers after a transducer has recieved events from Ninjamail and a filter has generated events for each user.

Nortel Programmable Routers

The Berkeley OpenetLab

"Using Programmable Routers to Protect Intranets"(ppt) ( pdf) (html) December 2000
We are facing a trend towards ubiquitous connectivity where users demand access at anytime, anywhere. This has lead to the deployment of public network ports and wireless networks. Current solutions to network access control are inflexible and only provide all-or-nothing access. It is also increasing important to protect Intranet hosts from other mobile and static hosts on the same Intranet, in order to contain damages in the case that a host gets compromised.

We present an architecture that addresses these issues by using a programmable router to provide dynamic fine-grained network access control. The Java-enabled router dynamically generates and enforces access control rules using policies and user profiles as input, reducing administrative overhead.  Our modular design integrates well with existing authentication and directory servers, further reducing admininstrative costs. Our prototype is implemented using Nortel's Accelar router and moves users to VLANs with the appropriate access privilege.

Iceberg MediaManager and Transcoding Services

[download] Available in the Iceberg release.

"Automatic Content Extraction for Voicemail In Iceberg", ( ppt ) ( ps )  [html] December 1999
Everyday, more and more devices are being hooked up to the global information network, which partly consists of the telephony, cellular, Internet, and pager networks. There is a need for infrastructure support which effectively accesses information from heterogeneous networks and devices. Our approach is the use of transcoding operators for multi-modal information access and a mail access service which handles both regular email and voicemail encoded in MIME .  The Iceberg Transcoder Service uses audio and text processing algorithms for extracting content from audio and text. Users may access all their messages from any mail respository in one place with calls to the Iceberg MediaManager and have the content displayed on any device, be it a speaker or PDA. The MediaManager Mail Access Service handles mail related mime types along with our own mime attribute extensions, across any mail protocol. It uses the Transcoder service to perform transformations on mail content.

My ViaVoice Custom Audio Library for File I/O. Here's the download and readme. The Media Manager Service and Transcoder Service make use of this custom audio library.

Automatic Path Creation ("Ninja Paths")

"System Support for Multi-Modal Information Access and Device Control" [psWMCSA '99, February 1999

[download]  Available in the Iceberg release.

[ppt]  A talk on the prototype.

Automatic Path Creation (APC)  is a data-flow based framework for dynamically composing services. The original prototype was used to implement an interactive voice response (IVR) system for remote audio/visual devices. Given a set of  strongly typed input and output devices, transcoding operators, and data streams, APC automatically creates a path from the input device to the output device. APC involves two steps: choosing the transcoding operators for the path and instantiating the path. Path instaniation involves taking a path that has been created and instantiating the operators and connecting them together.

Also see

Send Email to: