2274256
Overlay Networks with Linear Capacity Constraints
Overlay networks are virtual networks residing over the IP network; consequently, overlay links may share hidden lower level bottlenecks. Previous work has assumed an independent overlay model: a graph with independent link capacities. We introduce a model of overlays that incorporates correlated link capacities and linear capacity constraints (LCC) to formulate hidden shared bottlenecks; we refer to these as LCC-overlays. We define metrics to qualitatively measure overlay quality in terms of its accuracy (in representing the true network topology) and efficiency (that is, performance). Through analysis and simulations, we show that LCC-overlay is perfectly accurate and, hence, enjoys much higher efficiency than the inaccurate independent overlay. We discover that even a highly restricted LCC class-node-based LCC-yields near-optimal accuracy and significantly higher efficiency. We study two network flow problems in the context of LCC-graphs: widest path and maximum flow. We prove that Widest Path with LCC is NP-complete. We formulate Maximum Flow with LCC as a linear program and propose an efficient distributed algorithm to solve it. Based on the LCC model, we further study the problem of optimizing delay while still maintaining optimal or near-optimal bandwidth. We also outline a distributed algorithm to efficiently construct an overlay with node-based LCC.
5921080
Dynamic reconfiguration for complex multimedia applications
Current state-of-the-art distributed multimedia applications require an environment that provides stable quality of service (QoS). However, these applications typically run on best-effort heterogeneous platforms, and compete with other applications or connections for end system and network resources, hence suffer from instability and dynamic variations with regards to QoS. We present a dynamically reconfigurable middleware control architecture to enhance adaptation awareness of these applications. Our middleware architecture allows for detecting QoS fluctuations in the surrounding environment and signaling optimal control actions to the application. Furthermore, we discuss the design of a core component, the Configurator, that adopts a fuzzy control approach to compute optimal control actions. Preliminary experimental results with a distributed visual tracking application show that our approach is viable and effective in controlling adaptive applications.
584351
Efficient peer-to-peer data dissemination in mobile ad-hoc networks
Without infrastructural support from base stations, mobile nodes in an ad hoc network communicate with each other in a peer-to-peer fashion. This poses a challenge in data dissemination among the mobile peers, each having limited transmission range and unpredictable mobility. We first propose a novel mobility model to characterize user mobility in a civilian environment, such as a college campus. We then propose the application of Tornado coding as an efficient solution to the challenge of ad hoc peer-to-peer data dissemination. A mobile node is able to download coded file segments from different peers-at different times and in different locations. When it receives sufficient segments, it will be able to re-construct the original file. Although Tornado coding itself is not new, we for the first time propose its application to mobile ad hoc data dissemination. Furthermore, we show how Tornado coding parameters affect the performance of peer-to-peer data dissemination.
8043231
QoS-Aware Adaptive Services in Mobile Ad-Hoc Networks
Ad-hoc wireless networks consist of mobile nodes interconnected by multi-hop wireless paths. Unlike conventional wireless networks, ad-hoc networks have no fixed network infrastructure or administrative support. Because of the dynamic nature of the network topology and limited bandwidth of wireless channels, Quality-of-Service (QoS) provisioning is an inherently complex and difficult issue. In this paper, we propose a fully distributed and adaptive algorithm to provide statistical QoS guarantees with respect to accessibility of services in an ad-hoc network. In this algorithm, we focus on the optimization of a new QoS parameter of interest, service efficiency, while keeping protocol overheads to the minimum. To achieve this goal, we first theoretically derive the lower and upper bounds of service efficiency based on a novel model for group mobility, followed by extensive simulation results to verify the effectiveness of our algorithm.
15776548
Cross-layer flow control in lightly-loaded multi-hop ad hoc networks
The throughput in multi-hop ad hoc networks (MANETs) is highly dependent on the sending rate and the route length from the source node to the destination. Sending packets at the optimal rate for a given route length maximizes throughput in the network, whereas slightly increasing the sending rate over the optimal value may decrease throughput by up to 55%. This paper presents a novel cross-layer technique for flow control in lightly-loaded MANETs. The technique allows applications to send packets at the rate that maximizes throughput for a given route length. To achieve this, the routing layer notifies interested applications about routing changes, and the applications adaptively modify their sending rates based on the new route length to the destination. In static and mobile networks, this technique outperforms UDP-based flows with a fixed sending rate and doubles the throughput of TCP for networks with up to 2 concurrent flows.
3208295
Price-based resource allocation in wireless ad hoc networks
The shared-medium multi-hop nature of wireless ad hoc networks poses fundamental challenges to the design of an effective resource allocation algorithm to maximize the aggregated utility of flows, while maintaining basic fairness among multiple flows. When previously proposed scheduling algorithms have been shown to perform well in providing fair shares of bandwidth among single-hop wireless flows, they did not consider multi-hop flows with an end-to-end perspective. Moreover, the resource allocation strategies employed in the wireline network can not be applied directly in the context of ad hoc networks due to the unique characteristic of location dependent contention and spatial reuse of the shared wireless channel. In this paper, we propose a price-based resource allocation model to achieve maximized aggregated utility (i.e., social welfare) of flows. Our original contributions are: First, we propose to use maximal clique-associated shadow prices for wireless channel access coordination, rather than link-associated price for wireline link access arbitration. Second, we present a new pricing policy for end-to-end multi-hop flow. Using this model, different fairness goals can be realized in ad hoc networks for end-to-end flows. With a two-tier distributed and iterative algorithm, scarce channel capacity is allocated fairly among multi-hop flows from an end-to-end perspective, using shadow prices as the mechanism to arbitrate channel access. Through extensive analysis and simulation results, we show that our proposed algorithm is able to fairly distribute resources among multi-hop flows, while simultaneously maximizing the aggregated utility of flows globally.
46149042
Data reconciliation for real-time optimization of an industrial coke-oven-gas purification process
Online optimization is more and more used in the chemical industry to run a process near its optimum operating condition by providing real-time computed optimal set-points to the distributed control system. Process measurements are necessary for these applications to determine the actual state of the process and to increase the accuracy of the model with parameter estimation techniques. However, these measurements usually contain random as well as gross errors which have to be identified and eliminated before the measurements are used for online optimization. In this contribution, a data reconciliation approach was integrated into an online optimization framework for the ammonia hydrogen sulfide circulation scrubbing, a common industrial coke-oven-gas purification process. We used a rigorous rate-based model to describe this reactive absorption and desorption process. To increase the accuracy of the model, we estimated several process parameters using a sequential parameter estimation approach. Data reconciliation was performed based on simple component balances to achieve model-consistent data and to identify measurement biases. The model was then validated online on a pilot plant by connecting the estimation package through the process control system. Based on the online measured data, operating cost minimization was carried out and the computed optimal set-points realized real-time. A satisfactory agreement between measured data and optimization was achieved.
12626074
Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks
Blocking probability has been one of the key performance indexes in the design of wavelength-routed all-optical WDM networks. Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately; in particular the existing RWA algorithms have seldom considered the presence of wavelength conversion. In this paper, we firstly demonstrate that the existing dynamic RWA algorithms do not work well in the presence of wavelength conversion as they usually only take into account the current traffic, and do not explicitly consider the route lengths. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly. We further introduce an analytical model that can evaluate the blocking performance for WLCR algorithm. We carry out extensive numerical studies over typical topologies including ring, mesh-torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion.
5536365
Simulation of Diabetic Retinopathy Neovascularization in Color Digital Fundus Images
Diabetic retinopathy (DR) has been identified as a leading cause of blindness. One type of lesion, neovascularization (NV), indicates that the disease has entered a vision-threatening phase. Early detection of NV is thus clinically significant. Efforts have been devoted to use computer-aided analyses of digital retina images to detect DR. However, developing reliable NV detection algorithms requires large numbers of digital retinal images to test and refine approaches. Computer simulation of NV offers the potential of developing lesion detection algorithms without the need for large image databases of real pathology. In this paper, we propose a systematic approach to simulating NV. Specifically, we propose two algorithms based on fractal models to simulate the main structure of NV and an adaptive color generation method to assign photorealistic pixel values to the structure. Moreover, we develop an interactive system that provides instant visual feedback to support NV simulation guided by an ophthalmologist. This enables us to combine the low level algorithms with high-level human feedback to simulate realistic lesions. Experiments suggest that our method is able to produce simulated NVs that are indistinguishable from real lesions.
14151705
An adaptive k-nearest neighbor text categorization strategy
k is the most important parameter in a text categorization system based on the k-nearest neighbor algorithm (kNN). To classify a new document, the k-nearest documents in the training set are determined first. The prediction of categories for this document can then be made according to the category distribution among the k nearest neighbors. Generally speaking, the class distribution in a training set is not even; some classes may have more samples than others. The system's performance is very sensitive to the choice of the parameter k. And it is very likely that a fixed k value will result in a bias for large categories, and will not make full use of the information in the training set. To deal with these problems, an improved kNN strategy, in which different numbers of nearest neighbors for different categories are used instead of a fixed number across all categories, is proposed in this article. More samples (nearest neighbors) will be used to decide whether a test document should be classified in a category that has more samples in the training set. The numbers of nearest neighbors selected for different categories are adaptive to their sample size in the training set. Experiments on two different datasets show that our methods are less sensitive to the parameter k than the traditional ones, and can properly classify documents belonging to smaller classes with a large k. The strategy is especially applicable and promising for cases where estimating the parameter k via cross-validation is not possible and the class distribution of a training set is skewed.
3592974
Code Compaction of Matching Single-Entry Multiple-Exit Regions
With the proliferation of embedded devices and systems, there is renewed interest in the generation of compact binaries. Code compaction techniques identify code sequences that repeatedly appear in a program and replace them by a single copy of the recurring sequence. In existing techniques such sequences are typically restricted to single-entry single-exit regions in the control flow graph. We have observed that in many applications recurring code sequences form single-entry multipleexit (SEME) regions. In this paper we propose a generalized algorithm for code compaction that first decomposes a control flow graph into a hierarchy of SEME regions, computes signatures of SEME regions, and then uses the signatures to find pairs of matching SEME regions. Maximal sized matching SEME regions are found and transformed to achieve code compaction. Our transformation is able to compact matching SEME regions whose exits may lead to a combination of identical and differing targets. Our experiments show that this transformation can lead to substantial reduction in code size for many embedded applications.