Stability and throughput analysis of unslotted CDMA‐ALOHA with finite number of users and code sharing

We consider a system comprising a finite number of nodes, with infinite packet buffers, that use unslotted ALOHA with Code Division Multiple Access (CDMA) to share a channel for transmitting packetised data. We propose a simple model for packet transmission and retransmission at each node, and show that saturation throughput in this model yields a sufficient condition for the stability of the packet buffers; we interpret this as the capacity of the access method. We calculate and compare the capacities of CDMA‐ALOHA (with and without code sharing) and TDMA‐ALOHA; we also consider carrier sensing and collision detection versions of these protocols. In each case, saturation throughput can be obtained via analysis of a continuous time Markov chain. Our results show how saturation throughput degrades with code‐sharing. Finally, we also present some simulation results for mean packet delay. Our work is motivated by optical CDMA in which “chips” can be optically generated, and hence the achievable chip rate can exceed the achievable TDMA bit rate which is limited by electronics. Code sharing may be useful in the optical CDMA context as it reduces the number of optical correlators at the receivers. Our throughput results help to quantify by how much the CDMA chip rate should exceed the TDMA bit rate so that CDMA‐ALOHA yields better capacity than TDMA‐ALOHA. This revised version was published online in June 2006 with corrections to the Cover Date.     

Designing content distribution networks for optimal cost and performance

One strategy for alleviating excess latency (delay) in the Internet is the caching of web content at multiple locations. This reduces the number of hops necessary to reach the desired content. This strategy is used for web content such as html pages, images, streaming video, and Internet radio. The network of servers which store this content, and the collections of objects stored on each server, is called a content distribution network (CDN). In order to optimally design a CDN, given a network topology with available server storage capacity at various points in the network, one must decide which object collections to place on each server in order to achieve performance or cost objectives. The placements must be within the storage limits of the servers and must reflect the request patterns for each collection of objects to be cached. Researchers have suggested formulations for the CDN problem which address performance by minimizing latency (the average number of hops is a commonly accepted measure of latency) from client to content, or formulations that focus on minimizing cost of storage and/or bandwidth. In this research, we develop a model which allows for the simultaneous treatment of performance and cost, present examples to illustrate the application of the model and perform a detailed designed experiment to gain insights into cost/hops tradeoff for a variety of network parameters.     

A role for isothiocyanates in plant resistance against the specialist herbivore Pieris rapae

We experimentally reanalyzed the classic interaction between Pieris rapae, a specialist lepidopteran herbivore, and isothiocyanates (mustard oils) that are characteristic phytochemicals of the Brassicaceae. Previous investigations have suggested that P. rapae is unaffected by isothiocyanates. Using whole plants, root extracts, and a microencapsulated formulation of allyl isothiocyanate, we now show that isothiocyanates reduce herbivore survival and growth, and increase development time, each in a dose-dependent manner. Neither the substrate allyl glucosinolate, nor myrosinase, the enzyme that results in the breakdown of glucosinolates, negatively affected P. rapae. Thus, we present strong evidence for a role for isothiocyanates in plant resistance against the specialist herbivore P. rapae.     

Modeling finite buffer effects on TCP traffic over an IEEE 802.11 infrastructure WLAN

The network scenario is that of an infrastructure IEEE 802.11 WLAN with a single AP with which several stations (STAs) are associated. The AP has a finite size buffer for storing packets. In this scenario, we consider TCP-controlled upload and download file transfers between the STAs and a server on the wireline LAN (e.g., 100 Mbps Ethernet) to which the AP is connected. In such a situation, it is well known that because of packet losses due to finite buffers at the AP, upload file transfers obtain larger throughputs than download transfers. We provide an analytical model for estimating the upload and download throughputs as a function of the buffer size at the AP. We provide models for the undelayed and delayed ACK cases for a TCP that performs loss recovery only by timeout, and also for TCP Reno. The models are validated in comparison with NS2 simulations.     

Automatic recognition of handwritten medical forms for search engines

A new paradigm, which models the relationships between handwriting and topic categories, in the context of medical forms, is presented. The ultimate goals are: (1) a robust method which categorizes medical forms into specified categories, and (2) the use of such information for practical applications such as an improved recognition of medical handwriting or retrieval of medical forms as in a search engine. Medical forms have diverse, complex and large lexicons consisting of English, Medical and Pharmacology corpus. Our technique shows that a few recognized characters, returned by handwriting recognition, can be used to construct a linguistic model capable of representing a medical topic category. This allows (1) a reduced lexicon to be constructed, thereby improving handwriting recognition performance, and (2) PCR (Pre-Hospital Care Report) forms to be tagged with a topic category and subsequently searched by information retrieval systems. We present an improvement of over 7% in raw recognition rate and a mean average precision of 0.28 over a set of 1,175 queries on a data set of unconstrained handwritten medical forms filled in emergency environments. This work was supported by the National Science Foundation.     

Unconstrained handwritten document retrieval

With the ever-increasing growth of the World Wide Web, there is an urgent need for an efficient information retrieval system that can search and retrieve handwritten documents when presented with user queries. However, unconstrained handwriting recognition remains a challenging task with inadequate performance thus proving to be a major hurdle in providing robust search experience in handwritten documents. In this paper, we describe our recent research with focus on information retrieval from noisy text derived from imperfect handwriting recognizers. First, we describe a novel term frequency estimation technique incorporating the word segmentation information inside the retrieval framework to improve the overall system performance. Second, we outline a taxonomy of different techniques used for addressing the noisy text retrieval task. The first method uses a novel bootstrapping mechanism to refine the OCR’ed text and uses the cleaned text for retrieval. The second method uses the uncorrected or raw OCR’ed text but modifies the standard vector space model for handling noisy text issues. The third method employs robust image features to index the documents instead of using noisy OCR’ed text. We describe these techniques in detail and also discuss their performance measures using standard IR evaluation metrics.     

Fault containment in weakly stabilizing systems

Research on fine tuning stabilization properties has received attention for more than a decade. This paper presents probabilistic algorithms for fault containment. We demonstrate two exercises in fault containment in a weakly stabilizing system, which expedite recovery from single failures, and confine the effect of any single fault to the constant-distance neighborhood of the faulty process. The most significant aspect of the algorithms is that the fault gap, defined as the smallest interval after which the system is ready to handle the next single fault with the same efficiency, is independent of the network size. We argue that a small fault gap increases the availability of the fault-free system.     

Distributed key management for dynamic groups in MANETs

Most existing solutions to group security in Mobile Ad Hoc Networks (MANETs) rely on a multicast Core Based Tree (CBT) for key distribution. Such solutions, although suitable for systems with low mobility and static characteristics, are unsuitable for dynamic and sparse groups with changing neighborhoods. In this paper, we propose an entirely decentralized key generation mechanism, employing a central trusted entity only during initialization. Using our approach, keys can be established between group members with absolutely no prior communication. The solution relies on threshold cryptography and introduces a novel concept of Node-Group-Key (NGK) mapping. We have provided an extensive analytical model for the computations involved and communication costs and have also provided a lie detection mechanism. Simulation results show appreciable performance improvement and enhanced robustness.     

M2Tracker: A Multi-View Approach to Segmenting and Tracking People in a Cluttered Scene

When occlusion is minimal, a single camera is generally sufficient to detect and track objects. However, when the density of objects is high, the resulting occlusion and lack of visibility suggests the use of multiple cameras and collaboration between them so that an object is detected using information available from all the cameras in the scene.In this paper, we present a system that is capable of segmenting, detecting and tracking multiple people in a cluttered scene using multiple synchronized surveillance cameras located far from each other. The system is fully automatic, and takes decisions about object detection and tracking using evidence collected from many pairs of cameras. Innovations that help us tackle the problem include a region-based stereo algorithm capable of finding 3D points inside an object knowing only the projections of the object (as a whole) in two views, a segmentation algorithm using bayesian classification and the use of occlusion analysis to combine evidence from different camera pairs.The system has been tested using different densities of people in the scene. This helps us determine the number of cameras required for a particular density of people. Experiments have also been conducted to verify and quantify the efficacy of the occlusion analysis scheme.