Technical Reports and MS Project Reports

Ad hoc networks are dynamic, open environments that exhibit decoupled computing due to frequent disconnections and transient interactions. Reliable deploy-ment of components in such demanding settings requires a different design approach for the mechanisms that perform these functions. Not only do the deployment mechanisms have to perform the traditional tasks of deploying, installing, integrating and activat-ing components, they must also be robust enough to handle the nuances of an ad hoc network. This paper proposes a mechanism for component deployment that is adapted for use in ad hoc networks, and, ...Read More

Ad hoc networks are dynamic environments where fre-quent disconnections and transient interactions lead to de-coupled computing. Typically, participants in an ad hoc network are small mobile devices such as PDAs or cellu-lar phones that have a limited amount of resources avail-able locally, and must leverage the resources on other co-located devices to provide the user with a richer set of func-tionalities. Service-oriented computing (SOC), an emerging paradigm that seeks to establish a standard way of mak-ing resources and capabilities available for use by others in the form of services, is ...Read More

The increasing ubiquity of wireless mobile devices is promoting unprecedented levels of electronic collaboration among devices interoperating to achieve a common goal. Issues related to host interoperability are addressed partially by the service-oriented computing paradigm. However, certain technical concerns relating to reliable interactions among hosts in ad hoc networks have not yet received much attention. We introduce ”follow-me sessions”, where interaction occur between a client and a service, rather than a specific provider or server. We allow the client to switch service providers if needed. The redundancy offers scope for ...Read More

We propose the notion of Java-program gestures that are composed of a series of memory-accessing instructions. By finding patterns in gestures whose execution can be atomic, we can load them in an intelligent memory controller. This process can improve performance of the Java Virtual Machine, decrease code footprint, and reduce power consumption in hardware. In this thesis we formally define a language of gestures and introduce a method of detecting them statically at compile-time. We introduce a simple heuristic for reducing the number of gestures that must be loaded into ...Read More

This paper presents FAR, a Face-Aware Routing protocol for mobicast, a spatiotemporal variant of multicast tailored for sensor networks with environmental mobility. FAR features face-routing and timed-forwarding for delivering a message to a mobile delivery zone. Both analytical and statistical results show that, FAR achieves reliable and just-in-time mes-sage delivery with only moderate communication and memory overhead. This paper also presents a novel distributed algorithm for spatial neighborhood discovery for FAR boot-strapping. The spatiotemporal performance and reliability of FAR are demonstrated via ns-2 simulations.

The increased pervasiveness of wireless mobile com-puting devices draws new attention to the need for coor-dination among small networked components. The very nature of the environment requires devices to interact opportunistically when resources are available. Such interactions occur unpredictably as mobile agents gen-erally have no advance knowledge of other agents they will encounter over the lifetime of the application. In addition, as the ubiquity of communicating mobile de-vices increases, the number of application agents sup-ported by the network grows drastically. Managing ac-cess control is crucial to such systems, and applica-tion ...Read More

Some of the most dynamic systems being built today consist of physically mobile hosts and logically mobile agents. Such systems exhibit frequent configuration changes and a great deal of resource variability. Applications executing under these circumstances need to react continuously and rapidly to changes in operating conditions and must adapt their behavior accordingly. Applications with these capabilities are referred to as context-aware. Much of the current work on context-aware computing relies on information directly available to an application via context sensors on its local host, e.g., user profile, host location, ...Read More

Context-aware computing is characterized by the ability of a software system to continuously adapt its behavior to a changing environment over which it has little or no control. This style of interaction is imperative in ad hoc mobile networks that consist of numerous mobile hosts coordinating with each other opportunistically via transient wireless interconnections. In this paper, we provide a formal abstract characterization of a host’s context that extends to encompass a neighborhood within the ad hoc network. We provide an application in an ad hoc network a specification mechanism ...Read More

Context-aware mobile applications require constant adapta-tion to their changing environments. Technological advancements have increased the pervasiveness of mobile computing devices such as laptops, handhelds, cellular phones, and embedded sensors. The sheer amount of context information necessary for adaptation places a heightened burden on application developers as they must manage and utilize vast amounts of data from diverse sources. Facilitating programming in this data-rich environment requires a middleware infrastructure for sensing, collect-ing, and providing context information to applications. In this paper, we demonstrate the feasibility of providing such a middleware that ...Read More

This thesis motivates a fully automatic approach for locating roads in aerial video by using active contours in conjunction with motion cues. Directed active contours provide ideal parametric representations of roads due to their ability to fit the variety seen in road shapes. Motion in stabilized aerial video can be represented as a distribution of spatio-temporal derivatives. These motion cues can then be incorporated into the energy function, which yields active contours that better model the active roads in a scene. We present results using this approach on typical models ...Read More

Recent studies have shown that suitably-designed packet discard policies can dramatically improve the performance of fair queueing mechanisms in internet routers. The Queue State Deficit Round Robin algorithm (QSDRR) preferentially discards from long queues, but in-troduces hysteresis into the discard policy to minimize synchronization among TCP flows. QSDRR provides higher throughput and much better fairness than simpler queueing mech-anisms, such as Tail-Drop, RED and Blue. However, since QSDRR needs to maintain a separate queue for each active flow, there is a legitimate concern that it may be too costly for ...Read More

Minimax is a recently proposed procedure for electing committees, but it cannot be applied without an understanding of its computational complexity and its susceptibility to manipulate. We examine two compelling variations of minimax and prove both to be NP-complete. We derive upper and lower bounds on the size of minimax winner set for a given election. We present a heuristic for calculating a minimax winner set and present experiments based on its use. Finally, we present a general strategy for manipulating a minimax election.

An increasing number of distributed real-time systems face the critical challenge of provid-ing quality of service guarantees in open and unpredictable environments. In particular, such systems often need to enforce utilization bounds on multiple processors in order to avoid over-load and meet end-to-end deadlines even when task execution times are unpredictable. While recent feedback control real-time scheduling algorithms have shown promise, they cannot han-dle the common end-to-end task model where each task is comprised of a chain of subtasks dis-tributed on multiple processors. This paper presents the End-to-end Utilization CONtrol ...Read More

This paper presents MobiQuery, a spatiotemporal query service that allows mobile users to periodically gather information from their surrounding areas through a wireless sensor network. A key advantage of MobiQuery lies in its capability to meet stringent spatiotemporal performance constraints crucial to many applications. These constraints include query latency, data freshness and fidelity, and changing query areas due to user mobility. A novel just-in-time prefetching algorithm enables MobiQuery to main-tain robust spatiotemporal guarantees even when nodes op-erate under extremely low duty cycles. Furthermore, it sig-nificantly reduces the storage cost and ...Read More

Several approaches to hard, real-time garbage collection have been recently proposed. All of these approaches require knowing certain statistical properties about a program's execution, such as the maximum extent of live storage, the rate of storage allocation, and the number of non-null object references. While these new approaches offer the possibility of guaranteed, reasonably bounded behavior for garbage collection, the determination of the required information may not be straight forward for the application programmer. In this paper we present evidence suggesting that the necessary factors can vary widely over the ...Read More

In this thesis, we describe the use of Genetic Programming (GP) to learn obstacle detectors to be used for obstacle avoidance on a mobile robot. The first group of experiments focus on learning visual feature detectors for this task. We provide experimental results across a number of different environments, each with different characteristics, and draw conclusions about the performance of the learned feature detector and the training data used to learn such detectors. We also explore the utility of seeding the initial population with previously evolved individuals and subtrees, and ...Read More

We describe middleware and programming environment tools (JPie/qt) that allow programmers to access relational databases in an object-oriented way. Building on top of the JDBC API and leveraging live dynamic class creation and modification in JPie, the JPie/qt middleware presents the user with a simple interactive mechanism for creating object-oriented applications that access databases. Classes are generated mirroring the database schema and programmers deal directly with these classes. Objects of these classes can be database-bound, so reads and writes to their fields are reflected in the relational database immediately. Database ...Read More

We describe middleware and programming environment tools (JPie/qt) that allow programmers to access relational databases in an object-oriented way. Building on top of the JDBC API and leveraging live dynamic class creation and modification in JPie, the JPie/qt middleware presents the user with a simple interactive mechanism for creating object-oriented applications that access databases. Classes are generated mirroring the database schema and programmers deal directly with these classes. Objects of these classes can be database-bound, so reads and writes to their fields are reflected in the relational database immediately. Database ...Read More

A network of adaptive processing elements has been developed that transforms and fuses video captured from multiple sensors. Unlike systems that rely on end-systems to process data, this system distributes the computation throughout the network in order to reduce overall network bandwidth. The network architecture is scalable because it uses a hierarchy of processing engines to perform signal processing. Nodes within the network can be dynamically reprogrammed in order to compose video from multiple sources, digitally transform camera perspectives, and adapt the video format to meet the needs of specific ...Read More

We present middleware for a Server Development Environment that facilitates live development of SOAP and CORBA servers. As the underlying implementation platform, we use JPie, a tightly integrated programming environment for live software construction of Java applications. JPie provides dynamic classes whose signature and implementation can be modified at run time, with changes taking effect immediately upon existing instances of the class. We extend this model by automating the server deployment process, allowing developers to devote their full attention to the implementation of server logic. Moreover, the live development model ...Read More

We present middleware for a Client Development Environment that facilitates live development of client applications for SOAP or CORBA servers. We use JPie, a tightly integrated programming environment for live software construction in Java, as the target platform for our design. JPie provides dynamic classes whose signature and implementation can be modified at run time, with changes taking effect immediately upon existing instances of the class. We extend this model to automate addition, mutation, and deletion of dynamic server methods within dynamic clients. Our implementation simplifies distributed application development by ...Read More

Most scalable switches are required to buffer packets at both their inputs and outputs to overcome the slow memory speeds of packet queues. This thesis deals with the design of scheduling algorithms for such Combined Input and Output Queued (CIOQ) switches. For crossbar based CIOQ switches, we demonstrate the underperformance of commercially used scheduling algorithms under overload traffic conditions using targeted stress tests and present ideas to develop robust, stress resistant versions of these algorithms that are still simple enough to be implemented in high speed switches. To regulate the ...Read More

Buffered multistage interconnection networks offer one of the most scalable and cost-effective approaches to building high capacity routers and switches. Unfortunately, the performance of such systems has been difficult to predict in the presence of the extreme traffic conditions that can arise in Internet routers. Recent work introduced the idea of distributed scheduling, to regulate the flow of traffic in such systems. This work demonstrated (using simulation and experimental measurements) that distributed scheduling can en-able robust performance, even in the presence of adversarial traffic patterns. In this paper, we show ...Read More

Context-aware computing, an emerging paradigm in which applications sense and adapt their behavior to changes in their operational environment, is key to de-veloping dependable agent-based software systems for use in the often unpredictable settings of ad hoc net-works. However, designing an application agent which gathers, maintains, and adapts to context can be a diffi-cult undertaking in an open and continuously changing environment, even for a seasoned programmer. Our goal is to simplify the programming task by hiding such issues from the programmer, allowing one to quickly and reliably produce a ...Read More

Context-aware computing, an emerging paradigm in which applications sense and adapt their behavior to changes in their operational environment, is key to developing dependable agent-based soft-ware systems for use in the often unpredictable settings of ad hoc net-works. However, designing an application agent which interacts with other agents to gather, maintain, and adapt to context can be a difficult undertaking in an open and continuously changing environment, even for a seasoned programmer. Our goal is to simplify the programming task by hiding the details of agent coordination from the programmer, ...Read More

Aerial video provides strong cues for automatic road extraction that are not available in static aerial images. Using stabilized (or geo-referenced) video data, capturing the distribution of spatio-temporal image derivatives gives a powerful, local representation of scene variation and motion typical at each pixel. This allows a functional attribution of the scene; a “road” is defined as paths of consistent motion --- a definition which is valid in a large and diverse set of environments. Using a classical relationship between image motion and spatio-temporal image derivatives, road features can be ...Read More

In this proposal, we introduce the reserved delivery subnetwork (RDS), a mechanism that can al-low information service providers to deliver more consistent service to their customers without perflow resource reservation. In addition to service performance improvements, reserved delivery sub-networks can also provide protection against network resource attacks. Many applications such asweb content delivery services and virtual private networks can benefit from reserved delivery sub-networks. We address a number of issues with the deployment of RDSs. First, we formulate theconfiguration problem of an RDS as a minimum concave cost network flow ...Read More

The minimum concave cost network flow problem (MCCNFP) has many applications in areas such as telecommunication network design, facility location, production and inventory planning, and traffic scheduling and control. However, it is a well known NP-hard problem, and all existing search based exact algorithms are not practical for networks with even moderate numbers of vertices. Therefore, the research community also focuses on approximation algorithms to tackle the problems in practice. In this paper, we present an improved local search algorithm for the minimum concave cost network flow problem based on ...Read More

Optical Burst Switching (OBS) is an experimental network technology that enables the construction of very high capacity routers using optical data paths and electronic control. In this dissertation, we study the design of network components that are needed to build an OBS network. Specifically, we study the design of the switches that form the optical data path through the network. An OBS network that switches data across wavelength channels requires wave-length converting switches to construct an OBS router. We study one particular design of wavelength converting switches that uses tunable ...Read More

Context-aware computing refers to a computing paradigm in which the behavior of individual components is determined by the circumstances in which they find themselves to an extent that greatly exceeds the typical system/environment interaction pattern common to most modern computing. The environment has an exceedingly powerful impact on a particular application component either because the lat-ter needs to adapt in response to changing external conditions or be-cause it relies on resources whose availability is subject to continuous change. In this paper we seek to develop a systematic understanding of the ...Read More

Coordination is a style of interaction in which information exchange among independent system components is accomplished by means of high-level constructs designed to enhance the degree of decoupling among participants. A de-coupled mode of computation is particularly important in the design of mobile systems which emerge dynamically through the composition of independently developed components meeting under unpredictable circumstances and thrust into achieving purposeful cooperative behaviors. This paper examines a range of coordination models tailored for use in mobile computing and shows that the constructs they provide are reducible to simple ...Read More

Background: One of the most promising but challenging task in the post-genomic era is to reconstruct the transcriptional regulatory networks. The goal is to reveal, for each gene that responds to a certain biological event, which transcription factors affect its transcription, and how several transcription factors coordinate to accomplish specific regulations. Results: Here we propose a supervised machine learning approach to address these questions. We build decision trees to associate the expression level of a gene with the transcription factor binding data of its promoter. From the decision trees, we ...Read More

There is a critical need to perform advanced data processing on network traffic. In order to accom-plish this, protocol processing must first be performed to reassemble individual network packets into consistent data streams representing the exact dataset being transferred between end systems. This task is currently performed by protocol stacks running on end systems. Similar protocol processing opera-tions are needed to process the data on the interior of the network. Given millions of network connections operating on multi-gigabit per second network links, this task is extremely difficult. The TCP-Processor addresses ...Read More

The growth of the Internet has enabled it to become a critical component used by businesses, governments and individuals. While most of the traffic on the Internet is legitimate, a proportion of the traffic includes worms, computer viruses, network intrusions, computer espionage, security breaches and illegal behavior. This rogue traffic causes computer and network outages, reduces network throughput, and costs governments and companies billions of dollars each year. This dissertation investigates the problems associated with TCP stream processing in high-speed networks. It describes an architecture that simplifies the processing of ...Read More

This paper considers the technical challenges associated with the development of applications designed to work over mobile ad hoc net-works (MANETs). The setting is one in which a miniature application core residing on a mobile host with limited resources is able to support a complex application in a changing open environment by exploiting ser-vices made available by other hosts it encounters. The proposed solution extends in a novel way the applicability of the service provision paradigm to the ad hoc wireless setting. The novelty of the approach rests with the ...Read More

In the proxy approach to Service Oriented Comput-ing, a service advertises a proxy, which is searched for, retrievedand used by interested clients as a local handle to the serviceprocess that runs on a remote host. Due to software evolution,it becomes necessary at times to upgrade the service. Some ofthese upgrades may require an upgrade of the proxy software,in addition to the server itself. This paper addresses the issue ofupgrading both the server and its proxy in a manner transparentto the client, and ensures only momentary interruption duringthe switching process. The ...Read More

Service oriented computing is a new paradigm that is gaining popularity in dis-tributed computing environments due to its emphasis on highly specialized, modular and platform-agnostic code facilitating interoperability of systems. It borrows concepts from more mature paradigms such as object-oriented and component computing. This results in a progression from object-oriented computing to component computing and finally to service oriented computing, a new paradigm for designing and delivering software. Just as an object encapsulates state and behavior at a fine level of granularity, a service offers similar encapsulation at a larger ...Read More

Service oriented computing, with its aim of unhindered in-teroperability, is an appropriate paradigm for ad hoc net-works, which are characterized by physical mobility of het-erogenous hosts and by the absence of standardized application level protocols. The decoupled nature of computing in ad hoc networks can result in disconnections at inoppor-tune times during the client-service interaction process. We introduce the notion of a priori selection of services to reduce the likelihood of disconnection during service usage. A client may specify the times when it requires certain ser-vices. A knowledge base of ...Read More

TCAMs are the most popular practical approach to high performance packet classifica-tion, but they suffer from inefficient handling of range matches; the standard approach of rule replication can result in a 2-6x increase in TCAM words needed, for typical firewall databases. We describe three CMOS implementations of a range check circuit to address this problem; the most efficient of these designs allows classification on the standard IPv4 5-tuple with only a 46% increase in transistor count, rather than relying on rule replication. By avoiding replication, the overall transistor count required ...Read More

In this proposal, we seek to develop methods for packet classification that can deliver high performance (e.g. wire speed processing at 10 Gb/s) while being reasonably cost-effective (e.g. memory-efficient and having low hardware complexity). In particular, we discuss a new approach involving extended TCAMs. This new approach eliminates the problems that preclude TCAMs from being considered viable solutions to the packet classification problem.

For various reasons, a dedicated cluster is not always fully utilized even when all of its processors are allocated to jobs. This occurs any time that a running job does not use 100% of each of the processors allocated to it. Keeping in mind the needs of both the cluster’s system administrators and its users, we would like to increase the throughput and efficiency of the cluster while maintaining or improving the average turnaround time of the jobs and the quality of service of the “primary” jobs originally scheduled on ...Read More

We present an image-space camera manipulation widget that sup-ports visualization of the relationship of the camera with respect tothe scene. The form of the widget presents the user with naturalaffordances for camera manipulation. Visual aids such as ghostingof the scene and preview animations are used to acquaint noviceusers with the functions of different parts of the widget. Mousegestures are used to transition between different perspective viewsof the scene in an intuitive way. Finally, we provide a novel methodfor visualizing camera bookmarks.

Packet classification is an enabling function for a variety of Internet applications including Quality of Ser-vice, security, monitoring, and multimedia communications. In order to classify a packet as belonging to a particular flow or set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. In general, there have been two major threads of research addressing packet classification: algorithmic and architectural. A few pioneering groups of researchers posed the problem, provided complexity bounds, and offered a collection ...Read More

The growth and diversification of the Internet imposes increasing demands on the performance and functionality of network infrastructure. Routers, the devices responsible for the switch-ing and directing of traffic in the Internet, are being called upon to not only handle increased volumes of traffic at higher speeds, but also impose tighter security policies and provide support for a richer set of network services. This dissertation addresses the searching tasks performed by Internet routers in order to forward packets and apply network services to packets belonging to defined traffic flows. As ...Read More

Robust Header Compression (ROHC) provides for more efficient use of radio links for wireless communication in a packet switched network. Due to its potential advantages in the wireless access area andthe proliferation of network processors in access infrastructure, there exists a need to understand the resource requirements and architectural implications of implementing ROHC in this environment. We presentan analysis of the primary functional blocks of ROHC and extract the architectural implications on next-generation network processor design for wireless access. The discussion focuses on memory space andbandwidth dimensioning as well as ...Read More

Due to the importance and complexity of the packet classification problem, a myriad of algorithms and re-sulting implementations exist. The performance and capacity of many algorithms and classification devices, including TCAMs, depend upon properties of the filter set and query patterns. Unlike microprocessors in the field of computer architecture, there are no standard performance evaluation tools or techniques avail-able to evaluate packet classification algorithms and products. Network service providers are reluctant to distribute copies of real filter sets for security and confidentiality reasons, hence realistic test vectors are a scarce ...Read More

Packet classification is a multi-field searching task performed by Internet routers in order to apply security policies and network services to packets belonging to defined traffic flows. As this searching task must be performed for every packet traversing a router, fast and scalable solutions are required in order to prevent packet classification from becoming a performance bottleneck. A wide variety of packet classification al-gorithms and devices exist in the research literature and commercial market. The existing solutions exploit various design tradeoffs to provide high search rates, power and space efficiency, ...Read More

Three methods for analyzing sequencing traces derived from sequencing reactions containing two DNA templates are presented. All rely on alignment to a segment of assembled genomic sequence containing the original template sequence. Spliced alignment algorithms are used so that traces derived from processed mRNA can be analyzed. The main application of these techniques is the elucidation of alternately spliced transcripts. Several experimental verification of one of the techniques is presented including testing on a set of 48 alternately spliced targets from the human genome and 47 negative controls.

The advent and maturation of component-based middleware frameworks have sim-plified the development of large-scale distributed applications by separating system devel-opment and configuration concerns into different aspects that can be specified and com-posed at various stages of the application development lifecycle. Conventional component middleware technologies, such as J2EE [73] and .NET [34], were designed to meet the quality of service (QoS) requirements of enterprise applications, which focus largely on scalability and reliability. Therefore, conventional component middleware specifications and implementations are not well suited for distributed real-time and embedded (DRE) ap-plications with ...Read More

Real-time image transmission is crucial to an emerging class of distributed embedded systems operating in open network environments. Examples include avionics mission re-planning over Link-16, security systems based on wireless camera networks, and online collaboration using camera phones. Meeting image transmission deadlines is a key chal-lenge in such systems due to unpredictable network condi-tions. In this paper, we present the design, modeling, and analysis of CAMRIT, a Control-based Adaptive Middleware framework for Real-time Image Transmission in distributed real-time embedded systems. CAMRIT features a distributed feedback control loop that meets image ...Read More