Request redirection and data layout for network traffic balancing in cluster-based video-on-demand s
Cluster architecture is a cost-effective approach to building up scalable servers. For I/O-intensive videoon-demand (VoD) applications, network bandwidth is usually the primary bottleneck. In this paper, we propose a request redirection strategy to balance the network traffic in cluster-based VoD servers. The redirection strategy utilizes the servers' internal backbone bandwidth to equalize their external network traffic. Performance of redirection is related with data layouts based on replication. We implemented two replication methods and two placement methods for videos with different popularities. Furthermore, we evaluated redirection strategy with different data layouts. The simulation results verify the effectiveness of the redirection strategy and proposed data layout methods.

title: Design and evaluation of an environment APE for automatic parallelization of programs
abstract: In this paper, we present the design and evaluation of a compiler system, called APE, for automatic parallelization of scientific and engineering applications on distributed memory computers. APE is built on top of SUIF compiler. It extends SUIF with capabilities in parallelizing loops with non-uniform cross-iteration dependencies, and in handling loops that have indirect access patterns. We have evaluated the effectiveness of SUIF with several CFD test codes, and found that SUIF handles uniform loops over dense and regular data structures very well. For non-uniform loops, an innovative and efficient parallelization approach based on convex theory have been proposed and is being implemented. We have also presented a class of scalable algorithms for parallel distribution and redistribution of unstructured data structures during parallelizing irregular loops.

title: sMonitor: A Non-Intrusive Client-Perceived End-to-End Performance Monitor of Secured Internet Services
abstract: End-to-end performance measurement is fundamental to building high-performance Internet services. While many Internet services often operate using HTTP over SSL/TLS, current monitors are limited to plaintext HTTP services. This paper presents sMonitor, a non-intrusive server-side end-to-end performance monitor that can monitor HTTPS services. The monitor passively collects live packet traces from a server site. It then uses a size-based analysis method on HTTP requests to infer characteristics of client accesses and measures client-perceived pageview response time in real time. We designed and implemented a prototype of sMonitor. Preliminary evaluations show measurement error of less than 5%.

title: Hash-based proximity clustering for load balancing in heterogeneous DHT networks
abstract: DHT networks based on consistent hashing functions have an inherent load uneven distribution problem. The objective of DHT load balancing is to balance the workload of the network nodes in proportion to their capacity so as to eliminate traffic bottleneck. It is challenging because of the dynamism nature of DHT networks and time-varying load characteristics. In this paper, we present a hash-based proximity clustering approach for load balancing in heterogeneity DHTs. In the approach, DHT nodes are classified as regular nodes and supernodes according to their computing and networking capacities. Regular nodes are grouped and associated with supernodes via consistent hashing of their physical proximity information on the Internet. The supernodes form a self-organized and churn resilient auxiliary network for load balancing. The hierarchical structure facilitates the design and implementation of a locality-aware randomized load balancing algorithm. The algorithm introduces a factor of randomness in the load balancing processes in a range of neighborhood so as to deal with both the proximity and dynamism. Simulation results show the superiority of the approach, in comparison with a number of other DHT load balancing algorithms. The approach performs no worse than existing proximity-aware algorithms and exhibits strong resilience to the effect of churn. It also greatly reduces the overhead of resilient randomized load balancing algorithms due to the use of proximity information.

title: Decay function model for resource configuration and adaptive allocation on Internet servers
abstract: Server-side resource configuration and allocation for QoS guarantee is a challenge in performance-critical Internet applications. To overcome the difficulties caused by the high-variability and burstiness of Internet traffic, this paper presents a decay function model of request scheduling algorithms for the resource configuration and allocation problem. Under the decay function model, request scheduling is modelled as a transfer-function based filter system that has an input process of requests and an output process of server load. Unlike conventional queueing network models that rely on mean-value analysis for input renewal or Markovian processes, this decay function model works for general time-series based or measurement based processes and hence facilitates the study of statistical correlations between the request traffic, server load, and QoS of requests. Based on the model, we apply filter design theories in signal processing in the optimality analysis of various scheduling algorithms. We reveal a relationship between the server capacity, scheduling policy, service deadline, and other request properties in a formalism and present the optimality condition with respect to the second moments of request properties for an important class of fixed-time scheduling policies. Simulation results verify the relationship and show that optimal fixed-time scheduling can effectively reduce the server workload variance and guarantee service deadlines with high robustness on the Internet.

title: Stochastic modeling and analysis of hybrid mobility in reconfigurable distributed virtual machines
abstract: Virtualization provides a vehicle to manage the available resources and enhance their utilization in network computing. System dynamics requires virtual machines be distributed and reconfigurable. To construct reconfigurable distributed virtual machines, service migration moves the runtime services among physical servers when necessary. By incorporating the mobile agent technology, distributed virtual machines can improve their resource utilization and service availability significantly. This paper focuses on finding the optimal migration policies for service and agent migrations for high throughput in reconfigurable distributed virtual machines. We analyze three issues of this decision problem: migration candidate determination, migration timing and destination server selection. The service migration timing and destination server selection are formulated by two optimization models. We derive the optimal migration policy for distributed and heterogenous systems based on stochastic optimization theories. Renewal processes are applied to model the dynamics of migration. We solve the agent migration problem by dynamic programming and extend the optimal service migration decision by considering the interplay of the hybrid mobility. We verify the accuracy of our migration decision policy in simulations.

title: A topology preserving deformable model using level sets
abstract: Active contour and surface models, also known as deformable models, constitute a class of powerful segmentation techniques. Geometric deformable models implemented via level-set methods have advantages over parametric ones due to their intrinsic behavior, parameterization independence, and ease of implementation. However, a long claimed advantage of geometric deformable models, the ability to automatically handle topology changes, turns out to be a liability in applications where the objects to be segmented have a known topology that must be preserved. In this paper, we present a geometric deformable model that preserves topology using the simple point concept from digital topology. This algorithm maintains the other advantages of standard geometric deformable models including sub-pixel accuracy and production of nonintersecting curves (or surfaces). Several experiments on simulated and real data are provided to demonstrate the performance of the proposed algorithm.

title: Nearly Completely Positive Graphs
abstract: A non-cp graph G is called nearly vertex (edge) cp if any subgraph of G obtained by deleted a vertex (an edge) of G is completely positive. This paper presents necessary and sufficient conditions for any doubly nonnegative matrix realization A of a nearly cp graph to be completely positive.

title: A 2D moving grid geometric deformable model
abstract: Geometric deformable models based on the level set method have become very popular. To overcome an inherent limitation in accuracy while maintaining computational efficiency, adaptive grid techniques using local grid refinement have been developed for use with these models. However, this strategy requires a very complex data structure, yields large numbers of contour points, and is inconsistent with our previously presented topology-preserving geometric deformable model (TGDM). In this paper, we incorporate an alternative adaptive grid technique called the moving grid method into the geometric deformable model framework. We find that it is simpler to implement than grid refinement, requiring no large, complex, hierarchical data structures. It also limits the number of contour vertices in the final contour and supports the incorporation of the topology-preserving constraint of TGDM. After presenting the algorithm, we demonstrate its performance using both simulated and real images.

title: Gradient vector flow: a new external force for snakes
abstract: Snakes, or active contours, are used extensively in computer vision and image processing applications, particularly to locate object boundaries. Problems associated with initialization and poor convergence to concave boundaries, however, have limited their utility. This paper develops a new external force for active contours, largely solving both problems. This external force, which we call gradient vector flow (GVF) is computed as a diffusion of the gradient vectors of a gray-level or binary edge map derived from the image. The resultant field has a large capture range and forces active contours into concave regions. Examples on simulated images and one real image are presented.

title: Snakes, shapes, and gradient vector flow
abstract: Snakes, or active contours, are used extensively in computer vision and image processing applications, particularly to locate object boundaries. Problems associated with initialization and poor convergence to boundary concavities, however, have limited their utility. This paper presents a new external force for active contours, largely solving both problems. This external force, which we call gradient vector flow (GVF), is computed as a diffusion of the gradient vectors of a gray-level or binary edge map derived from the image. It differs fundamentally from traditional snake external forces in that it cannot be written as the negative gradient of a potential function, and the corresponding snake is formulated directly from a force balance condition rather than a variational formulation. Using several two-dimensional (2-D) examples and one three-dimensional (3-D) example, we show that GVF has a large capture range and is able to move snakes into boundary concavities.