The surge in online interactions and advancement in Big Data related techniques have generated vast amounts of hybrid data in the sense that the data are symbolic, numerical or missing features, and usually only a small number of data objects possess true labels due to high annotation costs. A necessary step of fully releasing the potential of these partially labeled hybrid data lies in feature selection, for which the neighborhood rough set (NRS) is an efficient mathematical method to apply. In NRS, setting proper neighborhood granules greatly influences the effectiveness and robustness of algorithms atop it. However, existing methods usually determine the optimal neighborhood radius of neighborhood granule via computationally intensive grid search, where the neighborhood radius for each object is the same, i.e., “unadaptive”. Some methods investigate adaptive granulation strategies, yet they inevitably hinge on preset parameters or a-prior knowledge. To tackle this problem, we propose an adaptive granules-enabled semi-supervised feature selection method that can adaptively generate suitable neighborhood radii for both labeled and unlabeled objects. The core idea lies in using the purity of decision labels as the threshold for granularity maximization construction. Then, by combining with neighborhood entropy and local density, a feature metric is designed to measure the feature significance. A semi-supervised feature selection algorithm is utilized to select feature subset by using the information from both labeled and unlabeled objects. Instead of hinging on expert knowledge, the proposed method only rely on the data per se. Experimental results on real-world datasets demonstrate the effectiveness of the designed method and its superiority over other state-of-the-art.

Deep Neural Networks (DNNs) have grown rapidly in size and complexity, requiring various optimizations to make training and deployment practically feasible. For example, BLOOM 176B and Megatron-Turing 530B require terabytes of memory and zettaflops of compute, which are far beyond the capabilities of any single device. Generally, training at such scales requires the use of large multi-machine, multi GPU/CPU systems, where parallelization techniques such as data, model, pipeline, and tensor parallelism must be explored and employed at different levels. Following the main body of research in this direction, we represent DNNs as DAG-structured workflows and formulate DNN training as a workflow mapping problem for throughput maximization. We design a class of approximation algorithms for DNN workflow partitioning and mapping with a performance bound, specifically targeting heterogeneous systems. Extensive experimental results show the efficacy of our proposed method and also confirm our theoretical analysis.

Microservice architecture has demonstrated immense advantages in solving the scalability and maintainability problems confronted by traditional monolithic systems. However, existing microservice architectures still encounter the problem of blurred boundaries, which significantly impact the system performance. The primary reason being the lack of unified evaluation indicators and efficient microservice splitting strategies. Specifically, some approaches divide entities like classes subjectively, resulting in inconsistent microservice boundaries, while others utilize objective criteria, but their complexity makes practical implementation challenging. To this end, we formalize the optimal microservice granulation problem, show its NPcompleteness and propose the granulation solution based on granular-ball computing. Our designs encompass a microservicebased information decision system to quantify the structural similarity between entities, a microservice granulation representation method based on granular-ball computing, and an optimal microservice granulation method given fixed budget constraint. Extensive experiments are conducted on open-source microservice projects to showcase the granulation result and the experimental results also show the efficacy and effectiveness.

Many modern software systems provide numerous configuration options with a large parameter space that users can adjust for specific running environments. However, configuring such systems always incurs an undue burden on users due to the lack of domain knowledge to understand complex interactions between the performance and the parameters. To address this issue, various tuning techniques have been developed to automatically determine the optimal configuration by either directly searching the configuration space or learning a surrogate model to guide the exploration process. Most previous studies only apply simple search strategies to explore the complex configuration space , which often leads to fruitless attempts in suboptimal areas. Inspired by previous studies, we define configuration structures to describe the positions of various configurations in the performance space of software systems. This idea leads to the design of a novel Configuration Structure-Aware Tuning (CSAT) algorithm. CSAT constructs a structure model for system configurations using the framework of Adaptive Network-based Fuzzy Inference System (ANFIS), learns a comparison-based distribution model through Gaussian Process Regression (GPR), and uses Bayesian Inference to generate potentially promising configurations based on the structure. The experimental results demonstrate that in terms of tuning performance, on average, CSAT outperforms default configurations by 65.51% and outperforms six state-of-the-art tuning algorithms by 22.10%–33.20%. In terms of handling internal constraints, CSAT achieves an average probability of 0.767 in generating valid configurations.

Fine-grained image retrieval (FGIR) is a crucial task in computer vision, with broad applications in areas such as biodiversity monitoring, e-commerce, and medical diagnostics. However, capturing discriminative feature information to generate binary codes is difficult because of high intraclass variance and low interclass variance. To address this challenge, we (i) build a novel and highly reliable fine-grained deep hash learning framework for more accurate retrieval of fine-grained images. (ii) We propose a part significant region erasure method that forces the network to generate compact binary codes. (iii) We introduce a CNN-guided Transformer structure for use in fine-grained retrieval tasks to capture fine-grained images effectively in contextual feature relationships to mine more discriminative regional features. (iv) A multistage mixture loss is designed to optimize network training and enhance feature representation. Experiments were conducted on three publicly available fine-grained datasets. The results show that our method effectively improves the performance of fine-grained image retrieval.

Abstract Many computing workloads in big data and machine learning applications are structured as directed acyclic graphs (DAG) and deployed on PC clusters for parallel execution using multiple physical or virtual machines. The scheduling of such workloads is critical to the application performance such as execution time and a plethora of techniques have been developed, taking into account various aspects such as data locality, network bandwidth, and server capability. We formulate DAG-structured workload scheduling as a nonlinear integer programming (NIP) problem and prove it to be NP-complete. Our empirical study reveals a positive correlation between scheduling plan distance (SPD) and finish time gap (FTG), and based on this finding, we propose a running time gap strategy (RTGS) to tackle this scheduling problem in multiprocessor environments. RTGS follows the main optimization strategy in the family of whale optimization algorithm (WOA). We derive a new function and use a greedy algorithm to generate an effective scheduling plan in RTGS. Extensive experiments with real production traces from Alibaba on simulation environments and realistic Hadoop environments show that our approach significantly improves the stability of WOA when applied to the scheduling problem of DAG-structured workloads, and also reduces the workload completion time by up to $$93\%$$ 93 % in comparison with seven state-of-the-art baseline algorithms.

Scientific applications of the next generation are undergoing a paradigm shift, transitioning from traditional experiment-centric methodologies to extreme-scale simulation-centric computations. These simulations, characterized by intricate numerical modeling with numerous adjustable parameters, generate vast datasets that necessitate meticulous processing and analysis against experimental or observational data for parameter calibration and model validation. However, manual parameter adjustment by domain experts in complex and distributed environments proves impractical. To address this challenge, we propose an online computational steering service facilitating real-time multi-user interaction. Towards this end, we design a versatile steering framework and conduct a theoretical performance evaluation of the steering service empowered by machine learning techniques. Furthermore, we present a case study involving the Weather Research and Forecast (WRF) model, comparing the performance of our steering solution with alternative heuristic methods and default settings to demonstrate its efficacy. The processing of big data generated by scientific simulations typically requires the use of big data systems as exemplified by Hadoop with Hadoop Distributed File System (HDFS) serving as a foundational technology layer. HDFS supports parallel computing in upper layers, offering fault tolerance and high throughput in data storage through block replication and cluster-wide distribution. However, the default block distribution strategy in HDFS overlooks the diverse capacities and data access patterns of nodes in heterogeneous Hadoop clusters, rendering it suboptimal for such environments. To address this issue, we formulate a class of block distribution problems in heterogeneous clusters, establishing its NP-completeness, and design an approximate algorithm, LPIR-BD, which leverages linear programming-based iterative rounding with a rigorous performance guarantee. Extensive experimental evaluations demonstrate the superior performance of LPIR-BD over several existing algorithms, corroborating our theoretical analyses and underscoring its efficacy in heterogeneous clusters.

The rapidly increasing demand for big data processing has necessitated the development of advanced scheduling policies that can effectively accommodate urgent job requirements. This paper presents the Urgent Job Priority Scheduler (UJPS) for Hadoop YARN, aimed at handling urgent jobs efficiently in big data processing. UJPS uses an Aging model to cut waiting times and prevent job starvation, a Dynamic Priority model for urgency-based prioritization, and a Container Load model to boost data locality and efficiency. Tested on Hadoop with benchmark tasks, UJPS outperforms five advanced schedulers, lowering waiting times by up to 81.42% and reducing job runtime by 32.90%. It prioritizes urgent tasks while ensuring overall efficiency, offering benefits to organizations using Hadoop YARN for timely job execution.

Hadoop stands out as one of the most widely employed systems for processing big data. Embedded within Hadoop as a foundational technological layer is the Hadoop Distributed File System (HDFS), providing fault tolerance and high throughput in data storage. This is achieved through mechanisms such as data partitioning, block replication, and cluster-wide distribution, which in turn facilitate parallel computing in the upper layers. Consequently, the strategy governing block placement emerges as a pivotal factor influencing the performance of Hadoop clusters. However, the default block distribution approach of HDFS overlooks the varying capacities of data nodes and their diverse data access patterns, rendering it unsuitable for heterogeneous Hadoop clusters. To address this challenge, we formulate a Block Distribution problem for heterogeneous clusters, prove it to be NP-complete, and design an approximation algorithm, Linear Programming-based Iterative Rounding (LPIR-BD), with a rigorous performance guarantee. Extensive experiments illustrate the notable performance superiority of LPIR-BD over several state-of-the-art algorithms, thus confirming the efficacy of our theoretical analysis.

Pathfinding is the search of an optimal path between two points on a graph. This paper investigates the performance of pathfinding algorithms in 3D voxel environments, focusing on optimizing paths for both time and distance. Utilizing computer simulations in Unreal Engine 5, four algorithms—A*, Dijkstra’s algorithm, Dijkstra’s algorithm with speed consideration, and a novel adaptation referred to as Time*—are tested across various environment sizes. Results indicate that while Time* exhibits a longer execution time than A*, it significantly outperforms all other algorithms in traversal time optimization. Despite slightly longer path lengths, Time* can compute more efficient paths. Statistical analysis of the results suggests consistent performance of Time* across trials. Implications highlight the significance of speed-based pathfinding algorithms in practical applications and suggest further research into optimizing algorithms for variable speed environments.

Peer-to-peer (P2P) content delivery networks (CDNs) have demonstrated immense potential to mitigate escalating network traffic. Meanwhile, blockchain emerges as a promising technology that can overcome the shortcomings confronted by P2P CDNs via acting as a trusted third party (TTP) to ensure critical security properties such as fairness and offering monetary incentivization. However, existing protocols for blockchain-based P2P CDNs still encounter the delivery efficiency issue, one of the primary reasons being the absence or failure to identify the most suitable deliverers. Specifically, some overlook the process of selecting deliverers, entrusting them haphazardly, and some merely consider a single evaluation dimension for a deliverer, resulting in a lack of comprehensiveness. Even when multiple dimensions are considered, the outcome of each dimension is not verifiable, leading to unreliability. To this end, we propose an optimized deliverer selection method in blockchain-based P2P CDNs. Our designs encompass a proof of delivery quality (PoQD) protocol to quantify the accumulative verifiable contributions of a deliverer, a comprehensive credibility evaluation mechanism based on neighborhood entropy, and a provider budget constraint optimized deliverer selection algorithm. Extensive experiments are conducted on Ethereum test network to justify our adaptive selection of k optimized deliverers, desired delivery efficiency and feasible on-chain costs. The experiment results indicate the efficacy and effectiveness of our proposed method.

With the recent development of AIoT (AI+IoT), crowdsourcing has emerged as a promising paradigm for distributed problem solving and business practice. Crowdsourcing entails posting tasks on a dedicated Web platform, enabling networked workers to choose preferred tasks on a first-come, first-served basis, typically of the same type to ensure high assignment accuracy. However, existing crowdsourcing task assignment methods do not take into account the potential fatigue of workers for similar tasks. In this article, we propose a task assignment architecture using a (TA-GAE), which comprehensively considers the relationship between the occupation and skills of workers and potential tasks, facilitating an accurate assignment of a wide variety of tasks to workers. The proposed architecture consists of three modules, The Graph Creation module analyzes the potential connections between tasks based on worker evaluations and constructs an initial task graph that represents these connections. The gravity-based graph autoencoder module is inspired by Newton’s law of universal gravitation. We analogize the tasks on the crowdsourcing platform to masses in the universe and calculate the mutual attractive force between two tasks to quantify their correlation. The Hybrid Task Assignment module recommends task lists to workers by combining traditional collaborative filtering and content-based task assignment strategies. The experimental results demonstrate that the proposed architecture outperforms several state-of-the-art methods and achieves a diversity rate of over 40% across four data sets: 1) fliggy trip; 2) MovieLens 1M; 3) library; and 4) survey.

Air quality monitoring is important to the green development of smart cities. Several technical challenges exist for intelligent, high-precision monitoring, such as computing overhead, area division, and monitoring granularity. In this article, we propose a fine-grained air quality monitoring system based on visual inspection analysis embedded in unmanned aerial vehicle (UAV), referred to as AQMon . This system employs a lightweight neural network to obtain an accurate estimate of atmospheric transmittance in visual information while reducing computation and transmission overhead. Considering that air quality is affected by multiple factors, we design a dynamic fitting approach to model the relationship between scattering coefficients and PM2.5 concentration in real time. The proposed system is evaluated using public datasets and the results show that AQMon outperforms four existing methods with a processing time of 13.8 ms.

In the evolving landscape of business analytical practice, big data stands as a pivotal force, steering organizational strategies, particularly in portfolio management across end-to-end businesses. With the surge in data's volume, variety, veracity and velocity, there is a pressing need for sophisticated computational methods to demystify intricate business portfolios, thereby facilitating astute decision-making. Traditional portfolio analysis techniques, although foundational, grapple with the challenges posed by expansive, multifaceted data and volatile market dynamics. To counter these challenges, our research pioneers an innovative approach, harnessing the power of clustering algorithms to refine and consolidate business portfolios. We employ big data techniques to analyze and categorize extensive portfolio datasets, unearthing inherent groupings and patterns. Leveraging clustering algorithms, we categorize business entities by similarity, yielding a streamlined and lucid portfolio blueprint. Our approach not only enhances the clarity of vast business portfolios but also strengthens strategic decision-making capabilities, propelling organizational nimbleness and market competitiveness. Through comparative analyses, our solution showcases significant advantages in portfolio simplification and decision-making efficacy over conventional techniques.

In Hadoop’s big data processing systems, YARN is responsible for resource management and job scheduling. The built-in job scheduling algorithms in YARN are simple to execute, but have some limitations such as job starvation, excessive server load, and load imbalance. In this paper, we propose a new Hybrid Dynamic Priority job Scheduling algorithm (HDPS) to address these limitations. HDPS dynamically adjusts the priority of a job as its waiting time increases to prevent job starvation. It also features a task assignment strategy designed specifically to address data locality by considering the available resources of servers and the distribution of data blocks stored on servers to reduce data transfer time and improve job execution efficiency. We implement and integrate HDPS into YARN and conduct experiments in a real Hadoop system using built-in benchmark test cases of Hadoop. Experimental results show that HDPS exhibits comprehensive superior performance over existing algorithms in terms of execution efficiency and load balance.

Machine learning techniques have gained significant traction in supply chain forecasting, driven by the increasing availability of data assets. These techniques offer opportunities to optimize management processes, reduce operational costs, and enhance decision-making for enterprise success. However, conventional statistical approaches dominating time series forecasting, such as the Autoregressive-moving-average model (ARMA), dynamic regression, and unobserved component models (UCMs), suffer from limitations in model accuracy and performance. They struggle to handle batch processing, large-scale big data, uncertainty-induced disruptions, and the synchronization of demand and supply scenarios. To address these challenges, we propose a class of ensemble techniques that combine neural networks with baseline models. Firstly, we conduct classification and segmentation by leveraging feature engineering on signal components, such as spikes and anomalies as outlier skews, to capture the complexity of combined scenarios in categorical data hierarchies and identify patterns for ensemble forecasting. Subsequently, we employ an ensemble model equipped with time series pattern sensors to automatically discern signal components, encompassing seasonality, promotions, trends, and intermittent or discontinued activities. We evaluate the performance of eight commonly-used model categories, and our proposed ensemble modeling approaches exhibit substantial improvements in accuracy compared to individual baseline models and other univariate time series algorithms.

Deep learning (DL) has become a dominating type of workloads on AI computing platforms. The performance of such platforms highly depends on how distributed DL jobs are scheduled. Reinforcement learning (RL)-based schedulers have been extensively studied and are capable of modeling interferences between concurrent jobs competing for resources. However, existing RL-based schedulers must learn from large number of samples and adapt to workload changes in real systems, which is a huge cost for production clusters. This paper proposes an intelligent, autonomous scheduler that employs sample-efficient RL for real-world resource scheduling on complex DL clusters. Specifically, we design a closed-loop meta-RL-based worker placement algorithm for DL training jobs. Instead of random exploration, we encourage the scheduler to explore combinatorial subspaces, where the performance model might be inaccurate, to improve the sampling efficiency of the scheduler agent. Extensive experimental results demonstrate that our algorithm outperforms other baselines in terms of average job completion time with 12.29% to 16.24% improvements. Further experiments with workload variations yield 15.76% to 22.13% improvements.

Gesture detection based on radio frequency signals has gained increasing popularity in recent years due to several benefits it has brought, such as eliminating the need to carry additional devices and providing better privacy. In traditional methods, significant breakthroughs have been made to improve recognition accuracy and scene robustness, but the limited computing power of edge devices (the first-level equipment to receive signals) and the requirement of fast response for detection have not been adequately addressed. In this article, we propose a lightweight Wi-Fi gesture recognition system, referred to as WiFine, which is designed and implemented for deployment on low-end edge devices without the use of any additional high-performance services in the process. Toward these goals, we first design algorithms for phase difference selection and amplitude enhancement, respectively, to tackle the problem of data drift caused by user change. Then, we design a cross-dimension fusion method to extract features of finer granularity from information of different dimensions, thus solving the precision problem of feature granularity. Finally, we design a lightweight neural network architecture by leveraging redundancy to reduce computational cost while ensuring satisfactory recognition accuracy. Extensive experimental results show that the proposed system achieves fast recognition of various actions with an accuracy up to 96.03% in 0.19 seconds.

Peer-to-peer (P2P) content delivery is up-and-coming to provide benefits comprising cost-saving and scalable peak-demand handling compared with centralized content delivery networks (CDNs), and also complementary to the popular decentralized storage networks such as Filecoin. However, reliable P2P delivery demands proper enforcement of delivery fairness, i.e., the deliverers should be rewarded in line with their in-time delivery. Unfortunately, most existing studies on delivery fairness are on the basis of non-cooperative game-theoretic assumptions that are arguably unrealistic in the ad-hoc P2P setting. We propose an expressive yet still minimalist security requirement for desired fair P2P content delivery, and give two efficient blockchain-enabled and monetary-incentivized solutions${\mathsf {FairDownload}}$and${\mathsf {FairStream}}$for P2P downloading and P2P streaming scenarios, respectively. Our designs not only ensure delivery fairness where deliverers are paid (nearly) proportional to their in-time delivery, but also guarantee exchange fairness where content consumers and content providers are also fairly treated. The fairness of each party can be assured even when other two parties collude to arbitrarily misbehave. Our protocols provide a general design of fetching content chunk from any specific position so the delivery can be resumed in the presence of unexpected interruption. Further, our systems are efficient in the sense of achieving asymptotically optimal on-chain costs and optimal delivery communication. We implement the prototype and deploy on the Ethereum Ropsten network. Extensive experiments in both LAN and WAN settings are conducted to evaluate the on-chain costs as well as the efficiency of downloading and streaming. Experimental results show the practicality and efficiency of our protocols.

A wide spectrum of large-scale applications in science, industry, and business domains generate colossal amounts of data that need to be moved across geographical locations for various purposes. Such big data transfer is increasingly carried out over connections with guaranteed bandwidth provisioned in high-performance networks, as exemplified by ESnet via advance bandwidth reservation agents such as OSCARS. Accurate performance prediction of big data transfer is vital for resource management to reserve appropriate bandwidth and optimize resource utilization. Data-driven methods using machine learning offer a promising solution to such prediction capabilities. However, most of these methods highly rely on the quality of training data and might suffer from low prediction accuracy when performance measurements are collected in environments with high dynamics or under latent effects. We propose a performance prediction method to help end users obtain a good estimate of achievable throughput, which could also be used by network managers to infer expected bandwidth usage and hence optimize bandwidth reservation and utilization. Based on Gaussian Process Regression (GPR), our approach is able to automatically detect intrinsic noise and identify latent effects to enhance prediction accuracy. We implement and evaluate the proposed method using performance measurements collected in real-life networks and the results demonstrate its effectiveness.

Many large-scale applications in various business and scientific domains require both parallel computing and distributed data management for big data processing. One typical scenario is the use of the Spark computing engine to process a large amount of data managed by HBase in Hadoop. Such computing workflows provide an opportunity to optimize application performance through strategic resource allocation with suitable parameter settings. As such, it necessitates accurate modeling and prediction of application performance to provide an effective recommendation of optimal system configurations to end users. However, this is a challenging problem for multiple reasons, mainly the large parameter space and the dynamic interactions between different technology layers of big data systems. In this paper, we propose a class of regression-based machine learning models to predict the execution performance of Spark-HBase applications in Hadoop. We first explore and identify an exhaustive set of system parameters across multiple layers including Spark and HBase, and then conduct in-depth exploratory analysis of their effects on the execution time of Spark-HBase applications. Based on these analysis results, we design a performance predictor using regression-based machine learning algorithms. Experimental results show that the resulted predictor achieves high accuracy with different algorithms in comparison. The proposed approach can facilitate automatic system configurations and has potential to be applied to other similar systems for big data processing.

Abstract Extracting frequent itemsets from datasets is an important problem in data mining, for which several mining methods including FP‐Growth have been proposed. FP‐Growth is a classical frequent itemset mining method, which generates pattern databases without candidates. Many improvements have been made in the literature due to the high time complexity and memory usage of FP‐Growth. However, most of them still suffer from performance issues on large datasets. In this paper, we design an auxiliary structure, Array Prefix‐Tree (AP‐Tree), and propose a new algorithm, Array Prefix‐Tree Growth (APT‐Growth), which is further parallelized as a Spark workflow, referred to as PAPT‐Growth. Based on a density threshold, we incorporate an adaptive algorithm selection process into PAPT‐Growth to ensure its running time performance. We conduct extensive experiments on different thresholds and multiple datasets, and experimental results show the performance superiority of PAPT‐Growth in comparison with several state‐of‐the‐art methods such as PFP, YAFIM, and DFPS. The analysis on density reveals a changing point, which justifies the necessity and validity of adaptive algorithm selection.

Data-intensive workflows (a.k.a. scientific workflows) are routinely used in many scientific disciplines today, especially in the context of parallel and distributed computing. Workflows, which are at the interface between end-users and computing infrastructures, provide a systematic way of describing complex processes for data analyses and rely on workflow management systems to execute such processes on a variety of distributed resources. With the dramatic increase of raw data volumes in every domain, they play an even more critical role to assist scientists in organizing and processing their data and to leverage High-performance Computing (HPC) or High-throughput Computing resources, for example, workflows played an important role in the discovery of Gravitational Waves. This Special Issue is intended to publish a collection of extended versions of high-quality papers presented at the 14th Workshop on Workflows in Support of Large-Scale Science (WORK'19: http://works.cs.cardiff.ac.uk), held in conjunction with SC19: The International Conference for High Performance Computing, Networking, Storage and Analysis, November 2019, Denver, CO. Through a rigorous and objective review process performed by our reviewers, four papers have been selected for final publication in this special issue. These papers cover various topics on workflow planning, provenance support, framework design, and applications to solve real-life problems. Specifically, In the paper titled “Data-Aware and Simulation-Driven Planning of Scientific Workflows on IaaS Clouds”, N'Takp et al. proposed a data-aware planning algorithm that leverages two characteristics of a family of virtual machine instances to improve data locality, hence reducing the amount of data transfers over the network during the execution of a workflow. In the paper titled “Workflow Provenance in the Lifecycle of Scientific Machine Learning”, Souza et al. leveraged workflow provenance techniques to build a holistic view to support the lifecycle of scientific machine learning. In the paper titled “A Co-Design Framework for Online Data Analysis and Reduction”, Mehta et al. presented a toolset for automating performance studies of composed HPC applications that perform online data reduction and analysis to facilitate understanding the impact of various factors such as process placement, synchronicity of algorithms, and storage vs. compute requirements for online analysis of large data. in the paper titled “On a Parallel Spark Workflow for Frequent Itemset Mining Based on Array Prefix-Tree”, Niu et al. designed an auxiliary structure, Array Prefix-Tree (AP-Tree), and a new algorithm, Array Prefix-Tree Growth (APT-Growth), which is further parallelized as a Spark computing workflow, to improve the running time performance for frequent itemset mining. As the Guest Editor, I would like to express my sincere appreciation to all the authors for their contributions and to all the reviewers for their voluntary services.

Hadoop Distributed File System (HDFS) was originally designed to store big files and has been widely used in big-data ecosystem. However, it may suffer from serious performance issues when handling a large number of small files. In this paper, we propose a novel archive system, referred to as Small File Merger (SFM), to solve small file problems in HDFS. The key idea is to combine small files into large ones and build an index for accessing original files. Unlike traditional archive systems such as Hadoop Archives (Har), SFM allows modification of archived files directly without re-archiving. Considering that most of the reads in HDFS are sequential, we design an adaptive readahead strategy based on the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm to maximize read performance. Furthermore, our system provides an HDFS-compatible interface, which can be used directly without recompiling and redeploying the existing HDFS cluster, hence facilitating convenient deployment for practical use. Preliminary experimental results show that our system achieves better performance than existing methods.

An increasing number of big data applications in various domains generate datasets continuously, which must be processed for various purposes in a timely manner. As one of the most popular streaming data processing systems, Spark Streaming applies a batch-based mechanism, which receives real-time input data streams and divides the data into multiple batches before passing them to Spark processing engine. As such, inappropriate system configurations including batch interval and executor count may lead to unstable states, hence undermining the capability and efficiency of real-time computing. Hence, determining suitable configurations is crucial to the performance of such systems. Many machine learning- and search-based algorithms have been proposed to provide configuration recommendations for streaming applications where input data streams are fed at a constant speed, which, however, is extremely rare in practice. Most real-life streaming applications process data streams arriving at a time-varying rate and hence require real-time system monitoring and continuous configuration adjustment, which still remains largely unexplored. We propose a novel streaming optimization scheme based on Simultaneous Perturbation Stochastic Approximation (SPSA), referred to as NoStop, which dynamically tunes system configurations to optimize real-time system performance with negligible overhead and proved convergence. The performance superiority of NoStop is illustrated by real-life experiments in comparison with Bayesian Optimization and Spark Back Pressure solutions. Extensive experimental results show that NoStop is able to keep track of the changing pattern of input data in real time and provide optimal configuration settings to achieve the best system performance. This optimization scheme could also be applied to other streaming data processing engines with tunable parameters.

With the rapid increase in GPS data collection through pervasive use of mobile devices, it has become an important problem to discover significant places of moving objects from complex spatial and temporal trajectories. This problem is challenging mainly because such trajectory data suffer from several issues including incompleteness, low quality, high redundancy, and oftentimes trajectory points do not follow Gaussian distribution . We propose a clustering-based method with temporal and spatial semantics, referred to as Stops and Moves of Trajectories using Attribute Selection (SMoTAS), whose technical advantages are multifold. Firstly, it improves data availability by using a self-adaptive algorithm to correct the deviation in traditional speed-based methods. Secondly, it improves place mining accuracy by filtering multi-label clustering results when there is a lack of detailed geographic data. Thirdly, it employs feature selection to exploit the core attributes of clustering and simplify the clustering results with Grubbs criterion. Experimental results on real-life datasets show that SMoTAS not only achieves substantial improvement of accuracy over existing methods in discovering significant places, but also exhibits superior adaptability to different trajectories and application scenarios.

The rapid advance in science and technology is made possible by research conduct and breakthroughs in a wide range of fields, which have resulted in a large number of academic papers. Searching through the enormous literature to find relevant information of one's research interest has become an increasingly important yet challenging problem for many researchers. Most existing methods for academic paper recommendation are based on the analysis of paper contents and only meet with limited success. We propose a novel method based on heterogeneous information networks for academic paper recommendation, referred to as HNPR. This method considers the citation relationship between papers, the collaboration relationship between authors, and the research area information of papers to construct two types of heterogeneous information networks. In such networks, a random walk-based strategy is used to simulate natural sentences for the discovery of relevance between two papers according to a mature natural language processing model. Extensive experimental results using real data in public digital libraries show that HNPR significantly improves the accuracy of academic paper recommendation in comparison with traditional content-based recommendation methods.

Big data generated by large-scale scientific and industrial applications need to be transferred between different geographical locations for remote storage, processing, and analysis. High-speed dedicated connections provisioned in High-performance Networks (HPNs) are increasingly utilized to carry out such big data transfer. HPN management highly relies on an important capability of performance (mainly throughput) prediction to reserve sufficient bandwidth and meanwhile avoid over-provisioning that may result in unnecessary resource waste. This capability is critical to improving the resource (mainly bandwidth) utilization of dedicated connections and meeting various user requests for data transfer. Conventional methods conduct performance prediction by fitting prior observed transfer history with predefined loss functions, without considering unobservable latent factors such as competing loads on end hosts. Such latent factors also have a significant impact on the application-level data transfer performance, which may result in an inaccurate prediction model. In this paper, we first investigate the impact of latent factors and propose a clustering-based method to eliminate their negative impact on performance prediction. We then develop a robust machine learning-based performance predictor by: i) incorporating the proposed latent factor elimination method into data preprocessing, and ii) adopting a customized domain guided loss function. Extensive experimental results show that our predictor achieves significantly higher prediction accuracy than several other state-of-the-art methods.

Many next-generation scientific and business applications feature large-scale data-intensive workflows, which require massive computing resources for execution on high-performance clusters in cloud environments. Such computing resources (e.g., VCores and virtual memory) requested through parameter setting in big data systems, if not fully utilized by workloads, are simply wasted due to the nature of exclusive access made possible by containerization. This necessitates accurate modeling and prediction of workflow performance to make an effective recommendation of appropriate parameter settings to end users. However, it is challenging to determine optimal workflow and system configurations due to the large parameter space and the interaction between various technology layers of big data systems. Towards this goal, we propose a machine learning-based feature selection method to identify influential parameters based on historical performance measurements of Spark-based computing workloads executed in big data systems with YARN. We first identify a comprehensive set of parameters across multiple layers in the big data technology stack including workflow input structure, Spark computing engine, and YARN resource management. We then conduct an in-depth exploratory analysis of their individual and coupled impact on workflow performance, and develop a performance-influence model using random forest for prediction. Experimental results show that the proposed approach identifies important features for performance modeling and achieves high accuracy in performance prediction.

The data volume of large-scale applications in various science, engineering, and business domains has experienced an explosive growth over the past decade, and has gone far beyond the computing capability and storage capacity of any single server. As a viable solution, such data is oftentimes stored in distributed file systems and processed by parallel computing engines, as exemplified by Spark, which has gained increasing popularity over the traditional MapReduce framework due to its fast in-memory processing of streaming data. Spark engines are generally deployed in cloud environments such as Amazon EC2 and Alibaba Cloud. However, storage and computing resources in these cloud environments are typically provisioned on a pay-as-you-go basis and thus an accurate estimate of the execution time of Spark workloads is critical to making full utilization of cloud resources and meeting performance requirements of end users. Our insight is that the execution pattern of many Spark workloads is qualitatively similar, which makes it possible to leverage historical performance data to predict the execution time of a given Spark application. We use the execution information extracted from Spark History Server as training data and develop a stage-aware hierarchical neural network model for performance prediction. Experimental results show that the proposed hierarchical model achieves higher accuracy than a holistic prediction model at the end-to-end level, and also outperforms other existing regression-based prediction methods.

Blockchain technology has been increasingly used for decentralizing cloud-based Internet of Things (IoT) architectures to address limitations faced by centralized systems. While many existing efforts are successful in decentralization with multiple servers (i.e., full nodes) to handle faulty nodes, an important issue has arisen that external clients have to rely on a relay node to communicate with the full nodes in the blockchain. Compromization of such relay nodes may result in a security breach and even a blockage of IoT sensors from the network. In this article, we propose blockchain-based decentralized IoT management systems for censorship resistance, which include a “diffusion” function to deliver all messages from sensors to all full nodes and an augmented consensus protocol to check data losses, replicate processing outcome, and facilitate opportunistic outcome delivery. We also leverage public key aggregation to reduce communication complexity and signature verification. The experimental results from proof-of-concept implementation and deployment in a real distributed environment show the feasibility and effectiveness in achieving censorship resistance.

In the data mining of road networks, trajectory clustering of moving objects is of particular interest for its practical importance in many applications. Most of the existing approaches to this problem are based on distance measurement, and suffer from several performance limitations including inaccurate clustering, expensive computation, and incompetency to handle high dimensional trajectory data. This paper investigates the complex network theory and explores its application to trajectory clustering in road networks to address these issues. Specifically, we model a road network as a dual graph, which facilitates an effective transformation of the clustering problem from sub-trajectories in the road network to nodes in the complex network. Based on this model, we design a label-based trajectory clustering algorithm, referred to as LBTC, to capture and characterize the essence of similarity between nodes. For the evaluation of clustering performance, we establish a clustering criterion based on the classical Davies-Bouldin Index (DB), Akaike Information Criterion (AIC), and Bayesian Information Criterion (BIC) to maximize inter-cluster separation and intra-cluster homogeneity. The clustering accuracy and performance superiority of the proposed algorithm are illustrated by extensive simulations on both synthetic and real-world dataset in comparison with existing algorithms.

Drowsiness detection is critical to driver safety, considering thousands of deaths caused by drowsy driving annually. Professional equipment is capable of providing high detection accuracy, but the high cost limits their applications in practice. The use of mobile devices such as smart watches and smart phones holds the promise of providing a more convenient, practical, non-invasive method for drowsiness detection. In this article, we propose a real-time driver drowsiness detection system based on mobile devices, referred to as dWatch, which combines physiological measurements with motion states of a driver to achieve high detection accuracy and low power consumption. Specifically, based on heart rate measurements, we design different methods for calculating heart rate variability (HRV) and sensing yawn actions, respectively, which are combined with steering wheel motion features extracted from motion sensors for drowsiness detection. We also design a driving posture detection algorithm to control the operation of the heart rate sensor to reduce system power consumption. Extensive experimental results show that the proposed system achieves a detection accuracy up to 97.1% and reduces energy consumption by 33%.

Modern big data computing systems exemplified by Hadoop employ parallel processing based on distributed storage. The results produced by parallel tasks such as computing modules in scientific workflows or reducers in the MapReduce framework are typically stored in a distributed file system across multiple data nodes. However, most existing systems do not provide a mechanism to compose such distributed information, as required by many big data applications. We construct analytical cost models and formulate a Distributed Information Composition problem in Big Data Systems, referred to as DIC-BDS, to aggregate multiple datasets stored as data blocks in Hadoop Distributed File System (HDFS) using a composition operator of specific complexity to produce one final output. We rigorously prove that DIC-BDS is NP-complete, and propose two heuristic algorithms: Fixed-window Distributed Composition Scheme (FDCS) and Dynamic-window Distributed Composition Scheme with Delay (DDCS-D). We conduct extensive experiments in Google clouds with various composition operators of commonly considered degrees of complexity including O(n), O(n log n), and O(n^2). Experimental results illustrate the performance superiority of the proposed solutions over existing methods. Specifically, FDCS outperforms all other algorithms in comparison with a composition operator of complexity O(n) or O(n log n), while DDCS-D achieves the minimum total composition time with a composition operator of complexity O(n^2). These algorithms provide an additional level of data processing for efficient information aggregation in existing workflow and big data systems.

Summary Cluster ensemble combines multiple base clustering results in a suitable way to improve the accuracy of the clustering result. In the conventional cluster ensemble frameworks, pairwise constraints and constraint projections have not been used together, and spectral clustering algorithm is rarely adopted to serve as the consensus function. In this paper, we design a constraint projections for semi‐supervised spectral clustering ensemble (CPSSSCE) model. It takes advantages of spectral clustering algorithm and executes semi‐supervised learning twice. Compared to traditional cluster ensemble approaches, CPSSSCE is characterized by several properties. First, the original data are transformed to lower‐dimensional representations by constraint projection before base clustering. Second, a similarity matrix is constructed using the base clustering results and modified using pairwise constraints. Third, the spectral clustering algorithm is applied to process the similarity matrix to obtain a consensus cluster result. Extensive experiments on standard University of California Irvine Machine Learning Repository (UCI) and Microsoft datasets demonstrated that the CPSSSCE is superior to other cluster ensemble algorithms including a semi‐supervised spectral clustering ensemble.

Radiation source detection is an important problem in homeland security-related applications. Deploying a network of detectors is expected to provide improved detection due to the combined, albeit dispersed, capture area of multiple detectors. Recently, localization-based detection algorithms provided performance gains beyond the simple “aggregated” area as a result of localization being enabled by the networked detectors. We propose the following three localization-based detection approaches: 1) source-attractor radiation detection (SRD); 2) triangulation-based radiation source detection (TriRSD); and 3) the ratio of square distance-based radiation source detection (ROSD-RSD). We use canonical datasets from Domestic Nuclear Detection Office's intelligence radiation sensors systems tests to assess the performance of these methods. Extensive results illustrate that SRD outperforms TriRSD and ROSD-RSD, and other existing detection algorithms based on the sequential probability ratio test and maximum likelihood estimation in terms of both false alarm and detection rates.

Big data transfer in next-generation scientific applications is now commonly carried out over dedicated channels in high-performance networks (HPNs), where transport protocols play a critical role in maximizing application-level throughput. Optimizing the performance of these protocols is challenging: i) transport protocols perform differently in various network environments, and the protocol choice is not straightforward; ii) even for a given protocol in a given environment, different parameter settings of the protocol may lead to significantly different performance and oftentimes the default setting does not yield the best performance. However, it is prohibitively time-consuming to conduct exhaustive transport profiling due to the large parameter space. In this paper, we propose a PRofiling Optimization Based DAta Transfer Advisor (ProbData) to help end users determine the most effective transport method with the most appropriate parameter settings to achieve satisfactory performance for big data transfer over dedicated connections in HPNs. ProbData employs a fast profiling scheme based on the Simultaneous Perturbation Stochastic Approximation algorithm, namely, FastProf, to accelerate the exploration of the optimal operational zones of various transport methods to improve profiling efficiency. We first present a theoretical background of the optimized profiling approach in ProbData and then detail its design and implementation. The advising procedure and performance benefits of FastProf and ProbData are illustrated and evaluated by both extensive emulations based on real-life performance measurements and experiments over various physical connections in existing production HPNs.

Microservice has been increasingly recognized as a promising architectural style for constructing large-scale cloud-based applications within and across organizational boundaries. This microservice-based architecture greatly increases application scalability, but meanwhile incurs an expensive performance overhead, which calls for a careful design of performance modeling and task scheduling. However, these problems have thus far remained largely unexplored. In this paper, we develop a performance modeling and prediction method for independent microservices, design a three-layer performance model for microservice-based applications, formulate a Microservice-based Application Workflow Scheduling problem for minimum end-to-end delay under a user-specified Budget Constraint (MAWS-BC), and propose a heuristic microservice scheduling algorithm. The performance modeling and prediction method are validated and justified by experimental results generated through a well-known microservice benchmark on disparate computing nodes, and the performance superiority of the proposed scheduling solution is illustrated by extensive simulation results in comparison with existing algorithms.

With the rapid deployment of cloud infrastructures around the globe and the economic benefit of cloud-based computing and storage services, an increasing number of scientific workflows have been shifted or are in active transition to clouds. As the scale of scientific applications continues to grow, it is now common to deploy data-and network-intensive computing workflows across multi-clouds, where inter-cloud data transfer has a significant impact on both workflow performance and financial cost. We construct rigorous mathematical models to analyze intra-and inter-cloud execution dynamics of scientific workflows and formulate a budget-constrained workflow mapping problem to optimize the network performance of MapReduce-based scientific workflows in Hadoop systems in multi-cloud environments. We show this problem to be NP-complete and design a heuristic solution that takes into consideration module execution, data transfer, and I/O operations. The performance superiority of the proposed mapping solution over existing methods is illustrated through extensive simulations and further verified by real-life workflow experiments deployed in public clouds. We observe about 15% discrepancy between our theoretical estimates and real-world experimental measurements, which validates the correctness of our cost models and also ensures accurate workflow mapping in real systems.

Modern data-intensive applications require the transfer of big data over high-performance networks (HPNs) through bandwidth reservation for various purposes such as data storage and analysis. The key performance metrics for bandwidth scheduling include the utilization of network resources and the satisfaction of user requests. In this paper, for a given batch of Deadline-Constrained Bandwidth Reservation Requests (DCBRRs), we attempt to maximize the number of satisfied requests with flexible scheduling options over link-disjoint paths in an HPN while achieving the best average Earliest Completion Time (ECT) or Shortest Duration (SD) of scheduled requests. We further consider this problem from two bandwidth-oriented principles: (i) Minimum Bandwidth Principle (MINBP), and (ii) Maximum Bandwidth Principle (MAXBP). We show that both of these problem variants are NP-complete, and propose two heuristic algorithms with polynomial-time complexity for each. We conduct bandwidth scheduling experiments on both small-and large-scale DCBRRs in a real-life HPN topology for performance comparison. Extensive results show the superiority of the proposed algorithms over existing ones in comparison.

Target detection is one fundamental problem in many sensor network-based applications, and is typically tackled in two separate stages for sensor deployment and data fusion. We propose an integrated solution, referred to as SSEM, which combines 2-level clustering-based sensor deployment and Source Strength Estimate Map-based data fusion for the detection of a single static or moving target. SSEM conducts the first level of clustering to determine a sensor deployment scheme and the second level of clustering to divide the deployed sensors into multiple subsets. For each sensor, the source strength is estimated at each grid point of the entire region based on a signal attenuation model, and for each subset of sensors, the target location is estimated using a strength distribution map-based statistical analysis method. A final detection decision is made by thresholding the clustering degree of the target location estimates computed by all subsets of sensors. Compared with traditional grid-based target detection methods, SSEM significantly reduces the computation complexity and improves the detection performance through an integrated optimization strategy. Extensive simulation results show the performance superiority of the proposed solution over several well-known methods for target detection.

Many scientific applications are generating extremely large amounts of data at a high speed, which must be transferred to remote collaborating sites for storage and analysis. Such high- demanding data transfer has been increasingly supported by bandwidth reservation services in high-performance networks (HPNs). For each bandwidth reservation request (BRR), most existing scheduling algorithms return either the best-case reservation option or a reject message if the BRR cannot be satisfied. To perform intelligent scheduling, we provide two alternative reservation options in the latter case: schedule the BRR within the closest time intervals before and after the user-specified time interval. We consider two different types of BRRs and for each, we design a flexible bandwidth scheduling algorithm with a rigorous optimality proof to compute both the best and alternative reservation options. For comparison, we also design two heuristics adapted from existing bandwidth scheduling algorithms. Extensive simulations show that the proposed algorithms have superior performance to those in comparison.

Bandwidth reservation has been increasingly used to provide QoS for various network applications. To accommodate a high-priority bandwidth reservation request (BRR), the bandwidth scheduler sometimes needs to preempt existing bandwidth reservations that have been made for BRRs with a lower priority, which is traditionally known as connection preemption. When such preemption is unavoidable, one primary goal of bandwidth scheduling is to minimize the disruption to existing reservations. In this paper, we study the problem of bandwidth reservation preemption for two types of BRRs, bandwidth- and data transfer- oriented, respectively, on one given link of the scheduling network with two different objectives: (i) minimize the number and then the total bandwidth of existing bandwidth reservations to be preempted, and (ii) minimize the total bandwidth and then the number of existing bandwidth reservations to be preempted. We prove these four problems to be NP-complete and propose a heuristic algorithm for each. We also design baseline heuristic algorithms for performance comparison. Extensive simulation results show that the proposed heuristic algorithms outperform those in comparison.

Intrusion detection systems (IDS) play an important role in the protection of network operations and services. In this paper, we propose an effective network intrusion detection scheme based on deep learning techniques. The proposed scheme employs a denoising autoencoder (DAE) with a weighted loss function for feature selection, which determines a limited number of important features for intrusion detection to reduce feature dimensionality. The selected data is then classified by a compact multilayer perceptron (MLP) for intrusion identification. Extensive experiments are conducted on the UNSW-NB dataset to demonstrate the effectiveness of the proposed scheme. With a small feature selection ratio of 5.9%, the proposed scheme is still able to achieve a superior performance in terms of different evaluation criteria. The strategic selection of a reduced set of features yields satisfactory detection performance with low memory and computing power requirements, making the proposed scheme a promising solution to intrusion detection in high-speed networks.

Parallel computing combined with distributed data storage and management has been widely adopted by most big data analytics systems. Scheduling computing tasks to improve data locality is crucial to the performance of such systems. While existing schedulers target near-data scheduling on top of physical data blocks, these systems face a new scheduling problem where computing tasks process table-based datasets directly and access large physical blocks indirectly through their indices stored in associated small logical blocks. This new problem invalidates the basic assumption made by many existing algorithms on near-data scheduling. In this paper, we propose a Logical-block Affinity Scheduling (LAS) algorithm to coordinate the near-data scheduling of computing tasks and the placement of logical blocks for a desired balance between data-locality and load-balancing to maximize system throughput. The proposed algorithm is implemented and evaluated using a well-known big data benchmark and a practical production system deployed in public clouds. Extensive experimental results illustrate the performance superiority of LAS over three existing scheduling algorithms.

Hadoop is one of the most popular distributed systems for big data computing in both industry and science communities. The default data placement strategy of Hadoop Distributed File System (HDFS), which was initially designed for homogenous environments, may suffer from performance degradation when deployed in heterogeneous clusters comprised of data nodes with disparate computing power and disk capacity, hence undermining the performance of MapReduce applications. In this paper, we use a Grey Forecast model to predict data hotness dynamically and determine an appropriate number of data block replicas on the fly. Based on such information, we further propose a dynamic data placement strategy (DDPS) to decide the best location for new replicas according to their hotness. The proposed method is able to dynamically adjust data replicas stored on each node in a heterogeneous Hadoop cluster and reduce the response time of big data applications. Experimental results on a heterogeneous Hadoop cluster show that DDPS together with the prediction model significantly increases application execution efficiency and improve MapReduce performance over the default HDFS configuration.

Multi-path routing has been increasingly used to improve aggregate bandwidth for big data transfer in various network environments. Typical solutions to this problem include a path set with the largest total bandwidth and the widest path pair. In this paper, we formulate a multi-path routing problem to maximize the total bandwidth of k edge-disjoint paths, where k > 1. We show this problem to be NP-complete and propose a heuristic algorithm with focus on global optimization. We implement the proposed algorithm and evaluate its performance in comparison with existing solutions in the literature. Extensive simulation results illustrate the superiority of the proposed algorithm in terms of aggregate bandwidth and satisfaction of edge count constraint.

Blockchain technology has been increasingly used for decentralizing cloud-based Internet of Things (IoT) architectures to address some limitations faced by centralized systems. While many existing efforts are successful in leveraging blockchain for decentralization with multiple servers (full nodes) to handle faulty nodes, an important issue has arisen that external clients (also called lightweight clients) have to rely on a relay node to communicate with the full nodes in the blockchain. Compromization of such relay nodes may result in a security breach and even a blockage of IoT sensors from the network. We propose censorship resistant decentralized IoT management systems, which include a "diffusion" function to deliver all messages from sensors to all full nodes and an augmented consensus protocol to check data loss, replicate processing outcome, and facilitate opportunistic outcome delivery. We also leverage the cryptographic tool of aggregate signature to reduce the complexity of communication and signature verification.

Bandwidth reservation has been increasingly used in high-performance networks to provide quality of service for various applications ranging from real-time multimedia communication in early years to big data transfer more recently. In this paper, we consider multiple bandwidth reservation requests in a batch awaiting to be scheduled in a dedicated network, and formulate two scheduling maximization problems: 1) maximize the amount of data to be transferred and 2) maximize the number of requests to be scheduled. We prove both problems are NP-complete and very difficult to approximate. We then design two heuristic algorithms and evaluate their performance against a scheduling algorithm widely used in real production networks through extensive simulation-based experiments. The experimental results show that the proposed heuristic algorithms achieve significantly better overall scheduling performance than the existing algorithm.

Big data workflows comprised of moldable parallel MapReduce programs running on a large number of processors have become a main consumer of energy at data centers. The degree of parallelism of each moldable job in such workflows has a significant impact on the energy efficiency of parallel computing systems, which remains largely unexplored. In this paper, we validate with experimental results the moldable parallel computing model where the dynamic energy consumption of a moldable job increases with the number of parallel tasks. Based on our validation, we construct rigorous cost models and formulate a dynamic scheduling problem of deadline-constrained MapReduce workflows to minimize energy consumption in Hadoop systems. We propose a semi-dynamic online scheduling algorithm based on adaptive task partitioning to reduce dynamic energy consumption while meeting performance requirements from a global perspective, and also design the corresponding system modules for algorithm implementation in Hadoop architecture. The performance superiority of the proposed algorithm in terms of dynamic energy saving and deadline violation is illustrated by extensive simulation results in Hadoop/YARN in comparison with existing algorithms, and the core module of adaptive task partitioning is further validated through real-life workflow implementation and experimental results using the Oozie workflow engine in Hadoop/YARN systems.

Multi-resolution grid computation is a technique used to speed up source localization with a Maximum Likelihood Estimation (MLE) algorithm. In the case where the source is located midway between grid points, the MLE algorithm may choose an incorrect location, causing following iterations of the search to close in on an area that does not contain the source. To address this issue, we propose a modification to multi-resolution MLE that expands the search area by a small percentage between two consecutive MLE iterations. At the cost of slightly more computation, this modification allows consecutive iterations to accurately locate the target over a larger portion of the field than a standard multi-resolution localization. The localization and computation performance of our approach is compared to both standard multi-resolution and single-resolution MLE algorithms. Tests are performed using seven data sets representing different scenarios of a single radiation source located within an indoor field of detectors. Results show that our method (i) significantly improves the localization accuracy in cases that caused initial grid selection errors in traditional MLE algorithms, (ii) does not have a negative impact on the localization accuracy in other cases, and (iii) requires a negligible increase in computation time relative to the increase in localization accuracy.

Dedicated wide-area network connections are increasingly employed in high-performance computing and big data scenarios. One might expect the performance and dynamics of data transfers over such connections to be easy to analyze due to the lack of competing traffic. However, non-linear transport dynamics and end-system complexities (e.g., multi-core hosts and distributed filesystems) can in fact make analysis surprisingly challenging. We present extensive measurements of memory-tomemory and disk-to-disk file transfers over 10 Gbps physical and emulated connections with 0-366 ms round trip times (RTTs). For memory-to-memory transfers, profiles of both TCP and UDT throughput as a function of RTT show concave and convex regions; large buffer sizes and more parallel flows lead to wider concave regions, which are highly desirable. TCP and UDT both also display complex throughput dynamics, as indicated by their Poincarέmaps and Lyapunov exponents. For diskto-disk transfers, we determine that high throughput can be achieved via a combination of parallel I/O threads, parallel network threads, and direct I/O mode. Our measurements also show that Lustre filesystems can be mounted over long-haul connections using LNet routers, although challenges remain in jointly optimizing file I/O and transport method parameters to achieve peak throughput.

With the maturity and proliferation of Software-Defined Networking (SDN), there has been an increasing number of network deployments that provide dedicated connections through on-demand and in- advance scheduling in support of data-intensive applications for global scientific collaboration. In such dedicated network environments, bandwidth scheduling serves as a key technique to improve the utilization of network resources and meet diverse user requests. In this paper, we formulate a periodic bandwidth scheduling problem to maximize the number of satisfied user requests for variable slot-bandwidth reservation under deadline constraint on a network path, referred to as VSBR- DC. We show that VSBR-DC is NP-complete, and propose a bandwidth scheduling algorithm based on optimal scheduling order and allocation strategy, referred to as OSOAS-BS. Extensive simulation results show that OSOAS-BS has a superior performance in terms of scheduling success ratio over three heuristic algorithms designed for performance comparison, and may be used to facilitate scientific collaboration that requires VSBR- based reservation services for coordinated data transfer over high- speed network links.

There is an increasingly prominent trend in many big data scientific applications to move a substantial portion of or even all of the computing workflow executions to a cloud environment, which calls for an effective and efficient solution to optimize the performance of such workflow applications. We focus on computing workflows of streaming applications, and consider a faulty cloud environment where both nodes and links may fail at a certain probability. We tackle a triobjective optimization problem that reduces the total energy consumption while enforcing a bound on the throughput, and a constraint on the reliability. A layer-based mapping algorithm is proposed to schedule each subtask in the workflow to an appropriate node in the cloud in order to achieve three objectives (energy, throughput, and reliability) in a distributed manner. The proposed scheme automatically recomputes a mapping solution adapting to the network changes after a certain period. The performance superiority of the proposed scheme is illustrated by an extensive set of comparisons with other existing methods.

Cloud computing provides a cost-effective computing platform for big data workflows where moldable parallel computing models such as MapReduce are widely applied to meet stringent performance requirements. The granularity of task partitioning in each moldable job has a significant impact on workflow completion time and financial cost. We investigate the properties of moldable jobs and design a big-data workflow mapping model, based on which, we formulate a workflow mapping problem to minimize workflow makespan under a budget constraint in public clouds. We show this problem to be strongly NP-complete and design i) a fully polynomial-time approximation scheme (FPTAS) for a special case with a pipeline-structured workflow executed on virtual machines in a single class, and ii) a heuristic for a generalized problem with an arbitrary directed acyclic graph-structured workflow executed on virtual machines in multiple classes. The performance superiority of the proposed solution is illustrated by extensive simulation-based results in Hadoop/YARN in comparison with existing workflow mapping models and algorithms.

An increasing number of high-performance networks are built over the existing IP network infrastructure to provision dedicated channels for big data transfer. The links in these overlay networks correspond to underlying paths and may share lower-level link segments. We consider a model of overlay networks that incorporates correlated link capacities and linear capacity constraints (LCCs) to formulate such shared bottleneck components. The overlay links are typically shared by multiple users through advance reservations, resulting in varying bandwidth availability in future time. Therefore, efficient bandwidth scheduling algorithms are needed to improve the network resource utilization and also meet the user's transport requirements. We investigate two advance scheduling problems in overlay networks with LCCs: Fixed-Bandwidth Path and Varying-Bandwidth Path, with the objective to minimize the data transfer end time for a given data size. We prove that both problems are NP-complete and non-approximable, and propose heuristic algorithms using a gradual relaxation procedure on the maximum number of links from each LCC allowed for path computation. The performance superiority of these heuristics is verified by extensive simulation results in comparison with optimal and greedy strategies.

The network infrastructures have been rapidly upgraded in many high-performance networks (HPNs). However, such infrastructure investment has not led to corresponding performance improvement in big data transfer, especially at the application layer, largely due to the complexity of optimizing transport control on end hosts. We design and implement ProbData, a PRofiling Optimization Based DAta Transfer Advisor, to help users determine the most effective data transfer method with the most appropriate control parameter values to achieve the best data transfer performance. ProbData employs a profiling optimization-based approach to exploit the optimal operational zone of various data transfer methods in support of big data transfer in extreme-scale scientific applications. We present a theoretical framework of the optimized profiling approach employed in ProbData as well as its detailed design and implementation. The advising procedure and performance benefits of ProbData are illustrated and evaluated by proof-of-concept experiments in real-life networks.

The transfer of big data in various applications across high-performance networks (HPNs) in a national or international scope consumes a significant amount of energy on a daily basis. However, most existing bandwidth scheduling algorithms only consider traditional objectives, such as data transfer time minimization, and very limited efforts have been devoted to energy efficiency in HPNs. In this paper, we consider two widely adopted power models, i.e., power-down and speed-scaling, and formulate two instant bandwidth scheduling problems to minimize energy consumption under data transfer deadline and reliability constraints. We prove the NP-completeness of both problems, and design a fully polynomial time approximation scheme for the problem using the power-down model. We also design an approximation algorithm and a heuristic approach that considers the tradeoff between objective optimality and time cost in practice for the problem using the speed-scaling model. The performance superiority of the proposed solutions is illustrated by extensive results based on both simulated and real-life networks in comparison with existing methods.

High-performance networks (HPNs) are being increasingly developed and deployed to support the transfer of big data. However, such HPN-based technologies and services have not been fully utilized as their use often requires considerable networking and system domain knowledge and many application users are even not aware of their existence. This work develops an integrated solution to discover system and network resources and compose end-to-end paths for big data movement. We first develop profiling and modeling approaches to characterize various types of resources distributed in end systems, edge segments, and backbone networks. A comprehensive set of performance metrics and network parameters are considered in different phases including device deployment, circuit setup, and data transfer. Based on these profiles and models, we then formulate a class of transport-support workflow optimization problems to compose the best end-to-end path that meets various performance requirements. We prove this problem to be NP-complete and design pseudo-polynomial optimal algorithms. We conduct extensive simulations to evaluate the proposed algorithms in comparison with a greedy approach, and also carry out real-life experiments across different network segments in production HPNs to evaluate the validity of the constructed cost models and illustrate the efficacy of the proposed transport solution.

The transfer of big data is increasingly supported by dedicated channels in high-performance networks, where transport protocols play an important role in maximizing application-level throughput and link utilization. The performance of transport protocols largely depend on their control parameter settings, but it is prohibitively time consuming to conduct an exhaustive search in a large parameter space to find the best set of parameter values. We propose FastProf, a stochastic approximation-based transport profiler, to quickly determine the optimal operational zone of a given data transfer protocol/method over dedicated channels. We implement and test the proposed method using both emulations based on real-life performance measurements and experiments over physical connections with short (2ms) and long (380ms) delays. Both the emulation and experimental results show that FastProf significantly reduces the profiling overhead while achieving a comparable level of end-to-end throughput performance with the exhaustive search-based approach.

Wide-area data transfers in high-performance computing and big data scenarios are increasingly being carried over dedicated network connections that provide high capacities at low loss rates. UDP-based transport protocols are expected to be particularly well-suited for such transfers but their performance is relatively unexplored over a wide range of connection lengths, compared to TCP over shared connections. We present extensive throughput measurements of UDP-based Data Transfer (UDT) over a suite of physical and emulated 10 Gbps connections. In sharp contrast to current UDT analytical models, these measurements indicate much more complex throughput dynamics that are sensitive to the connection modality, protocol parameters, and round-trip times. Lyapunov exponents estimated from the Poincaré maps of UDT traces clearly indicate regions of instability and complex dynamics. We propose a simple model based on the ramp-up and sustainment regimes of a generic transport protocol, which qualitatively illustrates the dominant monotonicity and concavity properties of throughput profiles and relates them to Lyapunov exponents. These measurements and analytical results together enable us to comprehensively evaluate UDT performance and select parameters to achieve high throughput, and they also provide guidelines for designing effective transport protocols for dedicated connections.

Mobile technology is changing the data collection and analytics in traditional healthcare practice. The distributed and real time nature of the operation brings security challenges in the gathering, processing, and analysis of personal biometrics data gathered by various wearable health monitoring devices. We present a security framework which identifies the anomalies not only based on the range of bio-metric parameters but also the history and the context. The values of the bio-metric parameters are used to construct the matrices to define the events. The matrices are de-noised using Random Matrix Theory. The correlation between different parameters is captured by the Pearson correlation. A canonical database, populated over time, of the vital signs of the patient and the values of the related bio-metric parameters through correlation network provide the history and context to detect anomalies. The security of the data collected in real time is very critical in establishing if an event is an anomaly. Our security framework ensures user authentication, confidentiality using encryption, confirms source device identity and packet level data validation. We provide a fully functional centralized visualization system to keep track of both patient and the doctors involved during any event of interest/ concern.

Many large-scale applications in science and business domains require the transfer of big data over high-performance networks for remote operations. Such big data transfer is increasingly supported by bandwidth reservation services that discover feasible and efficient routing options in dynamic network environments with time-varying resources. By exploring the flexility and capacity of variable paths, we formulate a generic problem of Bandwidth Scheduling with Two Variable Node-Disjoint Paths (BS-2VNDP), in which, we further consider two variable paths of fixed or variable bandwidth with negligible or non-negligible switching delay, referred to as 2VPFB/VB-0/1. We show the NP-completeness and propose a heuristic approach for each of them. We implement and test these proposed scheduling algorithms in both simulated and real-life networks. Extensive results show that they significantly outperform greedy scheduling methods in large-scale networks.

The efficiency of bandwidth scheduling in high-performance networks is critical to the utilization of network resources and the satisfaction of user requests. In this paper, we formulate a periodic bandwidth scheduling problem to maximize the number of satisfied user requests for bandwidth reservation with deadline constraint on a fixed network path, referred to as multiple deadline-constrained bandwidth scheduling (M-DCBS). We show the NP-completeness of this problem and propose a Maximum User Number Resource Reservation Algorithm (MUNRRA). Extensive simulation results show that MUNRRA exhibits a superior performance over existing algorithms in terms of scheduling success ratio and execution time. Considering the popularity of the DCBS-based service model and the rapid expansion of high-performance networks in both speed and scope, the proposed scheduling algorithm has great potential to improve the network performance of big data applications that require the DCBS service for data transfer.

Multiple-radio multiple-channel (MRMC) wireless mesh networks (WMNs) generally serve as wireless backbones for ubiquitous Internet access. These networks often face a challenge to satisfy multiple user traffic requests simultaneously between different source-destination pairs with different data transfer requirements. We construct analytical network models and formulate such multi-pair routing as a rigorous optimization problem. We design a cooperative routing and scheduling algorithm with channel assignment, in which, a primary path is built upon the selection of appropriate link patterns. The performance of the proposed algorithm is illustrated by simulation-based combinatorial experiments.

Large-scale e-science features complex DAG-structured workflows comprised of computing modules with intricate inter-module dependencies. Mapping such workflows in heterogeneous network environments and optimizing their end-to-end performance are crucial to the success of scientific collaborations that require fast system response and smooth data flow. We construct analytical cost models and formulate workflow mapping as optimization problems for minimum end-to-end delay and maximum frame rate. The difficulty of these problems essentially arises from the topological matching nature in the spatial domain, which is further compounded by the resource sharing complicacy in the temporal dimension. For unitary processing applications, we develop a workflow mapping algorithm based on a recursive critical path optimization procedure to minimize the latency; while for streaming applications, we conduct a rigorous workflow stability analysis and develop a layer-oriented dynamic programming solution based on topological sorting to identify and minimize the global bottleneck time. The accuracy of the proposed exact delay calculation algorithm is verified in comparison with an approximate solution, a dynamic distributed system simulation program, and a real network deployment, and the performance superiority of the proposed mapping approaches are illustrated by extensive simulation-based comparisons with existing algorithms and verified by large-scale experiments on real-life scientific workflows through effective system implementation and deployment in real networks.

In software-defined networks (SDNs) with multiple logically centralized controllers, it is challenging to maintain accurate link-state information, perceived as a global network view (GNV), at every controller in a consistent manner. Since online bandwidth scheduling, where every successful reservation triggers a GNV update at the controller, is expensive in terms of overhead, most networks adopt periodic scheduling with infrequent link-state information update, which, however, is the main cause of such inaccuracy/inconsistency. Even if up-to-date information is available, a controller does not always make frequent updates as it may cause network convergence issues. Consequently, bandwidth scheduling in such environments may lead to blocking or rejection of reservation requests, which deteriorates as the level of inaccuracy/inconsistency increases. To minimize such service disruptions, we formulate bandwidth scheduling in SDNs as an optimization problem and propose a randomization-based routing scheme to schedule bandwidth reservation requests such that the total number of blocked requests due to the inaccurate/inconsistent GNV is minimized. Simulation results show that the proposed solution exhibits a superior performance over existing methods.

We propose and develop an integrated transport solution to big data movement in high-performance networks in support of data-and network-intensive applications in various science domains. This solution integrates three major components, i.e. (i) transport-support workflow optimization, (ii) transport profile generation, and (iii) transport protocol design, into a unified framework.

The efficiency of bandwidth scheduling in high-performance networks (HPNs) is critical to the utilization of network resources and the satisfaction of user requests. We consider a periodic bandwidth scheduling problem to maximize the number of satisfied fixed-slot bandwidth reservation requests, referred to as multiple fixed-slot bandwidth scheduling (MFSBS), which is shown to be NP-complete. We first design a minimum resource occupation algorithm for a special type of M-FSBS with identical slots, referred to as MinRO-IS, and further propose a generalized version of MinRO for M-FSBS with arbitrary slots. We also design four greedy algorithms for performance comparison. Extensive simulation results illustrate that both MinRO-IS and MinRO have a superior performance over the existing algorithms in the literature and the other four greedy algorithms in comparison. Considering the popularity of the FSBS-based service model and the rapid expansion of HPNs in both speed and scope, the proposed scheduling algorithms have great potential to improve the network performance of big-data applications that require the FSBS service in HPNs.

Next-generation e-Science features large-scale, compute-intensive workflows of many computing modules that are typically executed in a distributed manner. With the recent emergence of cloud computing and the rapid deployment of cloud infrastructures, an increasing number of scientific workflows have been shifted or are in active transition to cloud environments. As cloud computing makes computing a utility, scientists across different application domains are facing the same challenge of reducing financial cost in addition to meeting the traditional goal of performance optimization. We develop a prototype generic workflow system by leveraging existing technologies for a quick evaluation of scientific workflow optimization strategies. We construct analytical models to quantify the network performance of scientific workflows using cloud-based computing resources, and formulate a task scheduling problem to minimize the workflow end-to-end delay under a user-specified financial constraint. We rigorously prove that the proposed problem is not only NP-complete but also non-approximable. We design a heuristic solution to this problem, and illustrate its performance superiority over existing methods through extensive simulations and real-life workflow experiments based on proof-of-concept implementation and deployment in a local cloud testbed.

The over operator is commonly used for α-blending in various visualization techniques. In the current form, it is a binary operator and must respect the restriction of order dependency, hence posing a significant performance limit. This paper proposes a fully generalized version of this operator. Compared with its predecessor, the fully generalized over operator is not only n-operator compatible but also any-order friendly. To demonstrate the advantages of the proposed operator, we apply it to the asynchronous and order-dependent image composition problem in parallel visualization for big data science and further parallelize it for performance improvement. We conduct theoretical analyses to establish the performance superiority of the proposed over operator in comparison with its original form, which is further validated by extensive experimental results in the context of real-life scientific visualization.

The elastic resource provision, non-interfering resource sharing and flexible customized configuration provided by the Cloud infrastructure has shed light on efficient execution of many scientific applications. Due to the increasing deployment of data centers and computer servers around the globe escalated by the higher electricity price, the energy cost on running the computing, communication and cooling together with the amount of CO2emissions have skyrocketed. In order to maintain sustainable Cloud computing facing with ever-increasing problem complexity and big data size in the next decades, we design and develop energy-aware scientific workflow scheduling algorithm to minimize energy consumption and CO2emission while still satisfying certain Quality of Service (QoS) such as response time specified in Service Level Agreement (SLA). We also apply Dynamic Voltage and Frequency Scaling (DVFS) and DNS scheme to further reduce energy consumption within acceptable performance bounds. Our multiple-step resource provision and allocation algorithm achieves the response time requirement in the step of forwarding task scheduling and minimizes the VM overhead for reduced energy consumption and higher resource utilization rate in the backward task scheduling step. The effectiveness of our algorithm is evaluated under various performance metrics and experimental scenarios using software adapted from open source CloudSim simulator.

Next-generation e-Science features large-scale, compute-intensive workflows of many computing modules that are typically executed in a distributed manner. With the recent emergence of cloud computing and the rapid deployment of cloud infrastructures, an increasing number of scientific workflows have been shifted or are in active transition to cloud environments. As cloud computing makes computing a utility, scientists across different application domains are facing the same challenge of reducing financial cost in addition to meeting the traditional goal of performance optimization. We construct analytical models to quantify the network performance of scientific workflows using cloud-based computing resources, and formulate a task scheduling problem to minimize the workflow end-to-end delay under a user-specified financial constraint. We rigorously prove that the proposed problem is not only NP-complete but also non-approximable. We design a heuristic solution to this problem, and illustrate its performance superiority over existing methods through extensive simulations and real-life workflow experiments based on proof-of-concept implementation and deployment in a local cloud test bed.

Many extreme-scale scientific applications generate colossal amounts of data that require an increasing number of processors for parallel visualization. Among the three well-known parallel architectures, i.e. sort-first/middle/last, sort-last, which comprises of two stages, i.e. image rendering and composition, is often preferred due to its adaptability to load balancing. We propose a generalized method, namely, Grouping More and Pairing Less (GMPL), for order-independent image composition in sort-last parallel rendering. GMPL is of two-fold novelty: i) it takes a prime factorization-based approach for processor grouping, which not only obviates the common restriction in existing methods on the total number of processors to fully utilize computing resources, but also breaks down processors to the lowest level with a minimum number of peers in each group to achieve high concurrency and save communication cost; ii) within each group, it employs an improved direct send method to narrow down each processor's pairing scope to further reduce communication overhead and increase composition efficiency. The performance superiority of GMPL over existing methods is evaluated through rigorous theoretical analysis and further verified by extensive experimental results on a high-performance visualization cluster.

An increasing number of high-performance networks provision dedicated channels through circuit-switching or MPLS/GMPLS tunneling techniques to support large data transfer. The link bandwidths of these networks are typically shared by multiple users through advance scheduling and reservation. The sheer volume of data transfer across such networks in a national or international scope requires a significant amount of energy on a daily basis. However, most existing bandwidth scheduling algorithms only concern traditional objectives such as data transfer time minimization, and very limited efforts have been devoted to energy efficiency in high-performance networks. In this paper, we adopt a practical power model and formulate an advance instant bandwidth scheduling problem to minimize energy consumption under a data transfer deadline constraint. We design a polynomial-time optimal solution to this problem and provide a rigorous correctness proof. The performance superiority of the proposed solution in terms of energy saving is illustrated by extensive results based on both simulated and real-life networks in comparison with existing methods.

An increasing number of high-performance networks provision dedicated channels through circuit switching or MPLS/GMPLS techniques to support large data transfer. The link bandwidths in such networks are typically shared by multiple users through advance reservation, resulting in varying bandwidth availability in future time. Developing efficient scheduling algorithms for advance bandwidth reservation has become a critical task to improve the utilization of network resources and meet the transport requirements of application users. We consider an exhaustive combination of different path and bandwidth constraints and formulate four types of advance bandwidth scheduling problems, with the same objective to minimize the data transfer end time for a given transfer request with a prespecified data size: fixed path with fixed bandwidth (FPFB); fixed path with variable bandwidth (FPVB); variable path with fixed bandwidth (VPFB); and variable path with variable bandwidth (VPVB). For VPFB and VPVB, we further consider two subcases where the path switching delay is negligible or nonnegligible. We propose an optimal algorithm for each of these scheduling problems except for FPVB and VPVB with nonnegligible path switching delay, which are proven to be NP-complete and nonapproximable, and then tackled by heuristics. The performance superiority of these heuristics is verified by extensive experimental results in a large set of simulated networks in comparison to optimal and greedy strategies.

High-performance networks have been increasingly deployed to provision dedicated channels for large data transfers over long distances to support various network-intensive applications with promised Quality of Service in terms of bandwidth and delay. These networks are generally capable of both advance and immediate bandwidth reservations, the former reserving resources ahead of time in a future time slot, while the latter allocating resources upon availability in the next immediate time slot. At the activation of an advance reservation typically with a higher priority, some ongoing data transfer tasks based on immediate reservations may be preempted due to the lack of resources. We propose a comprehensive bandwidth reservation solution to optimize network resource utilization by exploring the interactions between advance and immediate reservations. This solution integrates two major interrelated components: (i) a scheduling algorithm based on statistical analysis of reservation dynamics to route incoming advance reservations with both bandwidth and delay constraints for minimal impact on ongoing immediate reservations, (ii) a runtime preemption scheme to minimize the actual number of immediate reservations that must be preempted at the activation of an advance reservation. Extensive simulation results show that the proposed reservation solution exhibits a superior performance over existing methods.

Advanced networking technologies and services have been rapidly developed and deployed to facilitate bulk data transfer so as to support next-generation eScience applications. However, these technologies and services have not been fully utilized due to the knowledge lack of scientific domain experts. By leveraging the functionalities of an existing data movement advising utility, we propose a new Workflow-based Intelligent Network Data Movement Advisor (WINDMA) with end-to-end performance optimization. WINDMA provides a web interface and interacts with existing data/space management and discovery services such as Storage Resource Management, transport methods such as GridFTP and GlobusOnline, and network resource provisioning brokers such as ION and OSCARS. Efficacy of WINDMA has been demonstrated in several use cases based on its implementation and deployment in wide-area networks.

Cloud computing enables the delivery of computing, software, storage, and data access through web browsers as a metered service. In addition to commercial applications, an increasing number of large-scale workflow-based scientific applications are being supported by cloud computing. In order to meet the rapidly growing and dynamic computing demands of scientific users, the cloud service provider needs to employ efficient and cost-effective job schedulers to guarantee workflow completion time as well as improve resource utilization for high throughput. Based on rigorous cost models, we formulate a delay-constrained optimization problem to maximize resource utilization and propose a two-step workflow scheduling algorithm to minimize the cloud overhead within a user-specified execution time bound. The extensive simulation results illustrate that our approach consistently achieves lower computing overhead or higher resource utilization than existing methods within the execution time bound. Our approach also significantly reduces the total execution time by strategically selecting appropriate mapping nodes for prioritized modules.

Many high-performance networks support both advance and immediate bandwidth reservations, the former reserving bandwidth ahead of time in a future time slot to provide guaranteed bandwidth, while the latter allocating bandwidth upon availability in the next immediate time slot. As a result, an ongoing data transfer task based on an immediate reservation may be preempted by the activation of an advance reservation due to the lack of bandwidth. We propose a bandwidth reservation solution to optimize network resource utilization by exploring the interactions between advance and immediate reservations. This solution integrates two major interrelated components: (i) We design a scheduling algorithm based on rigorous statistical analysis of reservation dynamics to route incoming advance reservations with minimal impact on immediate reservations. (ii) We design a preemption scheme to minimize the actual number of immediate reservations that must be preempted at runtime due to insufficient bandwidth. The performance superiority of the proposed bandwidth reservation solution is illustrated by extensive simulations in comparison with existing methods.

High-performance networking technologies and services are being rapidly developed and deployed across the nation and around the globe to support the transfer of large data sets generated by next-generation scientific applications for collaborative data processing, analysis, and storage. However, these networking technologies and services have not been fully utilized mainly because their use often requires considerable domain knowledge and many application users are even not aware of their existence. The main goal of our work is to provide end users an integrated solution to discovering system and network resources and composing end-to-end paths for large data transfer. By leveraging the resource discovery capability previously developed in Network-Aware Data Movement Advisor (NADMA), we propose novel profiling and modeling approaches to characterize various types of resources that are available in end systems, edge segments, and backbone networks, taking into consideration a comprehensive set of performance metrics and network parameters in different phases including device deployment, circuit setup, and data transfer. Based on these profiles and models, we formulate a class of transport-support workflow optimization problems where an appropriate set of technologies and services are selected to compose the best transport-support workflow to meet the user's data transfer request in terms of various performance requirements. We conduct wide-area network experiments to validate the cost models and illustrate the efficacy of the proposed workflow-based transport solution.

Many network-intensive applications in various science, engineering, and business domains require high bandwidths to support large-scale data transfer over long distances. Such bandwidth requirements give rise to the development and deployment of high-performance networks that are capable of provisioning dedicated channels with reserved bandwidths through circuit/lambda-switching or MPLS/GMPLS techniques. We consider both advance and immediate bandwidth reservations, the former reserving bandwidth ahead of time in a future time slot to provide guaranteed bandwidth, while the latter allocating bandwidth upon availability in the next immediate time slot. As a result, an ongoing data transfer task based on an immediate reservation may be preempted by the activation of an advance reservation due to the lack of bandwidth. We formulate the advance bandwidth scheduling problem to minimize the impact on immediate reservations. Based on rigorous statistical analysis of reservation dynamics, we propose a scheduling solution to route incoming advance reservations such that the number of preempted immediate reservations by the advance reservations is minimized. The performance superiority of the proposed scheduling solution is illustrated by extensive simulations in comparison with existing algorithms.

Efficient visualization of cyber incidents is the key in securing increasingly complex information infrastructure. Extrapolating security-related information from data from multiple sources can be a daunting task for organizations to maintain safe and secure operating environment. However, meaningful visualizations can significantly improve decision-making quality and help security administrators in taking rapid response. The purpose of this work is to explore this possibility by building on previously gained knowledge and understanding of weather maps used in meteorology, assessing the gaps, and applying various techniques and matrices to quantify the impacts of cyber incidences in an efficient way.

With the advent of next-generation scientific applications, the workflow-based computing technology has become an indispensable research method for managing and streamlining large-scale distributed data processing. This paper investigates a problem of mapping distributed workflows for streaming data processing in faulty networks where nodes and links are subject to probabilistic failures. We formulate this problem as a bi-objective optimization problem in terms of both throughput and reliability, and propose a decentralized layer-oriented method to achieve high throughput for smooth data flow while satisfying a prespecified overall failure rate bound for a guaranteed level of reliability. The superiority of the proposed mapping solution is illustrated by both extensive simulation-based performance comparisons with existing algorithms and experimental results from a real-life scientific workflow deployed in wide-area networks.

Supporting large-scale scientific workflows in distributed network environments and optimizing their performances are crucial to the success of collaborative scientific discovery. We develop a generic scientific workflow platform, referred to as SciFlow, which constitutes a flexible framework to facilitate the distributed execution and management of scientific workflows and incorporates a class of workflow mapping schemes to achieve optimal end-to-end performances. The functionalities of SciFlow are provided and its interactions with other tools or systems are enabled through web services for easy access over standard Internet protocols while being independent of different platforms and programming languages. The performance superiority of SciFlow over existing workflow mapping schemes and management systems is illustrated by extensive simulations and is further verified by large-scale experiments on real-life scientific workflows through effective system implementation and deployment in distributed network environments.

Energy efficiency and fault tolerance are two important features required for sustained and reliable operations of wireless sensor networks deployed in unstructured environments. This paper investigates an approach to prolonging network lifetime and ensuring sensing reliability by organizing the sensors into several disjoint subsets, each of which takes shift to cover the entire region. This strategy is made possible by the enormous redundancy in large-scale sensor network applications where many small and inexpensive sensors are deployed to achieve quality through quantity. However, such energy savings through shift taking in time and fault tolerance via redundant coverage require an appropriate network partition in space: each on-duty subset must (i) cover the entire region, (ii) maintain its own connectivity, and (iii) cover every point with multiple sensors. Based on a general sensor network model, we formulate this problem as an NP-complete Connected M-SET k-Coverage problem. We rigorously derive a necessary and sufficient condition for checking the sensor coverage of a continuous two-dimensional space based on geometric reasoning, and analytically derive the upper bounds on both M and k for any given sensor network. We further propose a heuristic approach to this problem and evaluate its performance through extensive simulations.

Spectrum allocation algorithms are able to improve the performance of wireless mesh networks by exploiting the frequency agility of modern radios, and several such algorithms have been proposed. However, their interference constraints are at a coarse-grained level, which results in a low spectrum efficiency. To achieve higher spectrum resource utilization, we use interference pairs as a finer granularity to model the interference constraints in wireless mesh networks, and derive a sufficient and necessary condition for interference-free spectrum allocation. Based on a set of rigorous models, we formulate spectrum allocation as an optimization problem and divide it into two subproblems, for which we propose a two-phase interference pair-based distributed spectrum allocation (IPDSA) algorithm. In IPDSA, a negotiation-based frequency hierarchy mechanism heuristically determines the relation between the center frequencies of links in each interference pair; and then a dual decomposition-based spectrum allocation algorithm converges to the optimal allocation of center frequencies and spectral widths of all links. Extensive simulation results show that IPDSA is able to significantly improve spectrum utilization and thus increase network utility and aggregate throughput, thanks to a high accuracy in modeling interference constraints.

Many computation-intensive scientific applications feature complex workflows of distributed computing modules with intricate execution dependencies. Such scientific workflows must be mapped and executed in shared environments to support distributed scientific collaborations. We formulate workflow mapping as an optimization problem for latency minimization, whose difficulty essentially arises from the topological matching nature in the spatial domain, which is further compounded by the resource sharing complicacy in the temporal dimension. We conduct a rigorous analysis of the resource sharing dynamics in workflow executions, which constitutes the base for a workflow mapping algorithm to minimize the end-to-end delay. The correctness of the dynamics analysis is verified in comparison with an approximate solution, a dynamic system simulation program, and a real network deployment, and the performance superiority of the proposed mapping solution is illustrated by extensive comparisons with existing methods using both simulations and experiments.

The computing modules in distributed scientific workflows must be mapped to computer nodes in shared network environments for optimal workflow performance. Finding a good workflow mapping scheme critically depends on an accurate prediction of the execution time of each individual computational module in the workflow. The time prediction of a scientific computation does not have a silver bullet as it is determined collectively by several dynamic system factors including concurrent loads, memory size, CPU speed, and also by the complexity of the computational program itself. This paper investigates the problem of modeling scientific computations and predicting their execution time based on a combination of both hardware and software properties. We employ statistical learning techniques to estimate the effective computational power of a given computer node at any point of time and estimate the total number of CPU cycles needed for executing a given computational program on any input data size. We analytically derive an upper bound of the estimation error for execution time prediction given the hardware and software properties. The proposed statistical analysis-based solution to performance modeling and prediction is validated and justified by experimental results measured on the computing nodes that vary significantly in terms of the hardware specifications.

Several research and production high-performance networks now provision multi-Gbps dedicated channels to support large data transfers in network-intensive applications. However, end users have not seen a corresponding increase in application throughput mainly because traditional end-to-end transport methods are not optimized for such connections. New congestion or flow control mechanisms are desirable to meet the challenges brought by dedicated connections to transport protocol design. The advent and proliferation of multi-core processors make it now possible to improve application throughput by providing multiple processing and networking resources to a single data transfer. Based on the existing PLUT method, we propose a new transport method, Para-PLUT, which utilizes multiple parallel UDP connections to take advantage of the full power of multicore processors for maximum aggregate goodput. We implement and test Para-PLUT in a local dedicated network testbed and the experimental results illustrate its superior performance over several existing methods.

Detecting and identifying security events to provide cyber situation awareness has become an increasingly important task within the network research and development community. We propose a graph similarity-based approach to event detection and identification that integrates a number of techniques to collect time-varying situation information, extract correlations between event attributes, and characterize and identify security events. Diverging from the traditional rule- or statistical-based pattern matching techniques, the proposed mechanism represents security events in a graphical form of correlation networks and identifies security events through the computation of graph similarity measurements to eliminate the need for constructing user or system profiles. These technical components take fundamentally different approaches from traditional empirical or statistical methods and are designed based on rigorous computational analysis with mathematically proven performance guarantee. The performance superiority of the proposed mechanism is demonstrated by extensive simulation and experimental results.

Large-scale computation-intensive applications in various science fields feature complex DAG-structured workflows comprised of distributed computing modules with intricate intermodule dependencies. Mapping such workflows in heterogeneous network environments and maximizing their throughput are crucial to the success of large-scale scientific applications that process streaming datasets. We construct analytical cost models and formulate workflow mapping as an optimization problem for maximum frame rate. The difficulty of this problem essentially arises from the topological matching nature in the spatial domain, which is further compounded by the resource sharing complicacy in the temporal dimension if multiple modules are deployed on the same node. We conduct a rigorous workflow stability analysis and design a workflow mapping scheme based on a topological layer-oriented dynamic programming solution to identify and minimize the global bottleneck. The performance superiority of the proposed mapping scheme is illustrated by extensive simulation-based comparisons with existing algorithms.

This paper considers a hybrid hierarchical P2P overlay network structure that consists of both super and normal peers. The media streaming architecture is built upon a tree-structured network of super peers and the tree construction process has a significant impact on the overall system performance. We build network cost models and formulate a specific type of problem to maximize the minimum node throughput in Tree Construction (max-minTC), which aims at optimizing the system's stream rate by constructing an efficient spanning tree among super peers. We consider two scenarios: (i) When the overlay network has an arbitrary topology, we prove max-minTC to be NP-complete by reducing from the Degree Constrained Spanning Tree problem and propose an efficient heuristic algorithm. The performance superiority of the proposed algorithm is justified by experimental results collected by a live media streaming system deployed in real networks and is also illustrated by extensive simulations performed on a large set of simulated networks of various sizes from small to large scales in comparison with other methods, (ii) When the topology of the overlay network is complete, we rigorously prove that the same heuristic algorithm yields an optimal solution.

Sensor deployment is one fundamental task in sensor network implementation. We generalize and investigate the problem of deploying a minimum set of wireless sensors at candidate locations in constrained 3D space of interest to achieve k-coverage of given target areas such that each point in the target areas is covered by at least k sensors. Based on different constraints on sensor locations and target areas, we formulate four sensor deployment problems: Discrete / Continuous sensor Locations (D/CL) with Discrete / Continuous Target areas (D/CT). We propose an approximate algorithm for DLDT and reduce DLCT and CLDT to DLDT by discretizing continuous sensor locations or target areas into a number of divisions without loss of sensing precision. We further consider the connected version of these four sensor deployment problems where deployed sensors must form a connected network, and propose an approximate algorithm for each of these connected deployment problems.

The traditional client-server architecture widely adopted on the Internet is not adequate to meet the increasing user loads and bandwidth demands in live streaming systems especially for multimedia content delivery. Peer-to-peer P2P) overlay networks provide excellent system scalability and high resource utilization, which make it an attractive solution to this problem. This paper considers a hybrid hierarchical P2P overlay network structure that consists of both super and normal peers. The media streaming architecture is built upon a tree structured network of super peers and the tree construction process has a significant impact on the overall system performance. We construct network cost models and formulate a Bandwidth Constrained Tree (BCT) construction problem, which aims at maximizing the number of peers that satisfy a specified bandwidth constraint. We prove that BCT is NP-complete and propose optimal algorithms in two special cases and a heuristic approach in a general case. The performance superiority of the proposed method is illustrated by an extensive set of experiments on simulated networks of various sizes in comparison with existing greedy and degree constrained algorithms.

Many large-scale scientific applications feature distributed computing workflows of complex structures that must be executed and transferred in shared wide-area networks consisting of unreliable nodes and links. Mapping these computing workflows in such faulty network environments for optimal latency while ensuring certain fault tolerance is crucial to the success of eScience that requires both performance and reliability. We construct analytical cost models and formulate workflow mapping as an optimization problem under failure rate constraint. We propose a distributed heuristic mapping solution based on recursive critical path to achieve minimum end-to-end delay and satisfy a pre-specified overall failure rate for a guaranteed level of fault tolerance. The performance superiority of the proposed mapping solution is illustrated by extensive simulation-based comparisons with existing mapping algorithms.

The client-server architecture widely adopted on the Internet is not adequate to meet the ever-increasing user loads and bandwidth demands in live streaming systems especially for multimedia content delivery. Peer-to-peer (P2P) overlay networks provide excellent system scalability and high resource utilization, which make it an attractive solution to this problem. We consider a hybrid hierarchical P2P overlay network that consists of both super and normal peers to support live streaming applications. This architecture is built upon a tree-structured network of super peers, which organize normal peers into clusters. The tree construction process has a significant impact on the overall system performance. We formulate a specific type of problem, max-minTC, to maximize the minimum node throughput in tree construction, where the system's stream rate is optimized by constructing an efficient spanning tree among super peers. We present a decentralized approach where super peers run the same algorithm in parallel to derive a tree from an identical database describing the topology of the streaming system. This approach is able to quickly converge to a new tree upon the detection of any topological changes in super peers. The performance superiority of the proposed solution is illustrated by extensive simulations on a large set of simulated networks of various sizes from small to large scales in comparison with other methods.

Peer-to-peer (P2P) overlay networks provide a highly effective and scalable solution to live media streaming systems that require the collective use of massively distributed network resources. A P2P media streaming architecture is typically built completely or partially upon a tree-structured network topology and the process of tree construction has a significant impact on the overall system performance. We build network cost models and formulate a specific type of topology construction problem, Maximum Average Bandwidth Spanning Tree (MABST), which aims at optimizing the system's average stream rate. We prove that MABST is NP-complete by reducing from Hamiltonian Path problem and propose an efficient heuristic algorithm. The performance superiority of the proposed algorithm is justified by experimental results using a live media streaming system deployed in real networks and is also illustrated by an extensive set of simulations on simulated networks of various sizes in comparison with other methods based on a degree constraint or a greedy strategy.

We propose a binary decision fusion rule that reaches a global decision on the presence of a target by integrating local decisions made by multiple sensors. Without requiring a priori probability of target presence, the fusion threshold bounds derived using Chebyshev's inequality ensure a higher hit rate and lower false alarm rate compared to the weighted averages of individual sensors. The Monte Carlo-based simulation results show that the proposed approach significantly improves target detection performance, and can also be used to guide the actual threshold selection in practical sensor network implementation under certain error rate constraints.

New types of specialized network applications are being created that need to be able to transmit large amounts of data across dedicated network links. TCP fails to be a suitable method of bulk data transfer in many of these applications, giving rise to new classes of protocols designed to circumvent TCP's shortcomings. It is typical in these high-performance applications, however, that the system hardware is simply incapable of saturating the bandwidths supported by the network infrastructure. When the bottleneck for data transfer occurs in the system itself and not in the network, it is critical that the protocol scales gracefully to prevent buffer overflow and packet loss. It is therefore necessary to build a high-speed protocol adaptive to the performance of each system by including a dynamic performance-based flow control. This paper develops such a protocol, Performance Adaptive UDP (henceforth PA-UDP), which aims to dynamically and autonomously maximize performance under different systems. A mathematical model and related algorithms are proposed to describe the theoretical basis behind effective buffer and CPU management. A novel delay-based rate-throttling model is also demonstrated to be very accurate under diverse system latencies. Based on these models, we implemented a prototype under Linux, and the experimental results demonstrate that PA-UDP outperforms other existing high-speed protocols on commodity hardware in terms of throughput, packet loss, and CPU utilization. PA-UDP is efficient not only for high-speed research networks, but also for reliable high-performance bulk data transfer over dedicated local area networks where congestion and fairness are typically not a concern.

Supporting visualization pipelines over wide-area networks is critical to enabling large-scale scientific applications that require visual feedback to interactively steer online computations. We propose a remote computational steering system that employs analytical models to estimate the cost of computing and communication components and optimizes the overall system performance in distributed environments with heterogeneous resources. We formulate and categorize the visualization pipeline configuration problems for maximum frame rate into three classes according to the constraints on node reuse or resource sharing, namely no, contiguous, and arbitrary reuse. We prove all three problems to be NP-complete and present heuristic approaches based on a dynamic programming strategy. The superior performance of the proposed solution is demonstrated with extensive simulation results in comparison with existing algorithms and is further evidenced by experimental results collected on a prototype implementation deployed over the Internet.

Several research and production networks now provide multiple Gbps dedicated connections to meet the demands of large data transfers over wide-area networks. Application throughputs, however, were not able to match these rates because the traditional transport methods have not been optimized for suc

The timely and reliable data transfer required by many networked applications necessitates the development of comprehensive security solutions to monitor and protect against an increasing number of malicious attacks. However, providing complete cyber space situation awareness is extremely challenging because of the lack of effective translation mechanisms from low-level situation information to high-level human cognition for decision making and action support. We propose an adaptive cyber security monitoring system that integrates a number of component techniques to collect time-series situation information, perform intrusion detection, keep track of event evolution, characterize and identify security events, and present a visual representation in order to provide comprehensive situational view so that corresponding defense actions can be taken in a timely and effective manner. We explore the principles of designing and applying appropriate visualization techniques for situation monitoring by defining graphical representations of security events. This differs from the traditional rule-based pattern matching techniques in that security events in the proposed system are represented as forms of correlation networks using random matrix theory and identified through the computation of network similarity measurement. The events and corresponding event types are visualized using a stemplot to show location and quantity. Extensive simulation results on event identification illustrate the efficacy of the proposed system.

Supporting high-performance computing pipelines in wide-area networks is crucial to enabling large-scale distributed scientific applications that require minimizing end-to-end delay for fast user interaction or maximizing frame rate for smooth data flow. We formulate and categorize the linear pipeline configuration problems into six classes with two mapping objectives, i.e. minimum end-to-end delay and maximum frame rate, and three network constraints, i.e. no, contiguous, and arbitrary node reuse. We design a dynamic programming-based optimal solution to the problem of minimum end-to-end delay with arbitrary node reuse and prove the NP-completeness of the rest five problems, for each of which, a heuristic algorithm based on a similar optimization procedure is proposed. These heuristics are implemented and tested on a large set of simulated networks of various scales and their performance superiorities are illustrated by extensive experimental results in comparison with existing methods.

Sensor network lifetime is largely affected by the energy consumption for data transmission from sensor nodes to a base station. We generalize and solve the problems of deploying multiple base stations in sensor networks using one-hop and multi-hop communication models to maximize network lifetime. Under the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution for small-scale networks and a heuristic approach for large-scale ones based on the smallest enclosing circle algorithm that deploys a base station at the geometric center of each cluster. Under the multi-hop communication model, both the base station locations and the data routing scheme need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing path for benchmark purposes. Extensive simulation results show superior network lifetime performance of the proposed deployment algorithms in comparison with existing ones.

Several research and production high-performance networks now provision multi-Gbps dedicated channels to meet the demands of large data transfers in network-intensive applications. However, end users have not seen corresponding increase in application throughput mainly because (i) the existence of high-bandwidth links has shifted the congestion from the network to end hosts, and (ii) such congestion is not well handled by TCP's Additive Increase and Multiplicative Decrease algorithm. Particularly, due to the sharing with unknown background workloads, the data receiver oftentimes lacks sufficient system resources to process the arriving packets, hence leading to significant packet drops at the end system. This paper proposes a UDP-based transport method that incorporates a performance-adaptive flow control mechanism to regulate the activities of both the sender and receiver in response to system dynamics to achieve high throughput. We construct a mathematical model for the socket receive buffer and data receiving process, and employ a profiling-based method to estimate the initial receiving bottleneck rate, which is dynamically adjusted and sent back to the sender for source rate control. The sending rate is stabilized at the estimated bottleneck rate based on a stochastic approximation algorithm. We test the proposed method on a local dedicated connection and the experimental results illustrate its superior performance over existing methods.

Many complex sensor network applications require the use of a large number of low-end sensors to achieve quality through quantity. Deploying a relatively small number of high-end sensors in the region to gather and forward sensor data to the base station is generally considered as an efficient and scalable way to facilitate the management and operation of large-scale sensor networks. The number and location of high-end sensors do not only affect the network deployment cost but also the total energy consumption for data communication. We investigate the problem of deploying a minimum set of high-end sensors to collect the measurements of all low-end sensors with a minimum amount of energy consumption. We propose a heuristic algorithm, distance- and connectivity-based H-sensor deployment to solve this problem. The simulation results illustrate the performance superiority of the proposed algorithm in comparison with two greedy schemes.

Supporting high-performance computing pipelines in wide-area networks is crucial to enabling large-scale distributed scientific applications that require minimizing end-to-end delay for fast user interaction or maximizing frame rate for smooth data flow. We formulate and categorize the linear pipeline configuration problems into six classes with two mapping objectives, i.e. minimum end-to-end delay and maximum frame rate, and three network constraints, i.e. no, contiguous, and arbitrary node reuse. We design a dynamic programming-based optimal solution to the configuration problem for minimum end-to-end delay with arbitrary node reuse and prove the NP-completeness of the rest five problems, for each of which, a heuristic algorithm based on a similar optimization procedure is proposed. Performance superiorities of these heuristics are illustrated by extensive experimental results in comparison with existing methods.

The significance of high-performance dedicated networks has been well recognized due to the rapidly increasing number of large-scale applications that require high-speed data transfer. Efficient algorithms are needed for path computation and bandwidth scheduling in dedicated networks to improve the utilization of network resources and meet diverse user requests. We consider two periodic bandwidth scheduling problems: multiple data transfer allocation (MDTA) and multiple fixed-slot bandwidth reservation (MFBR), both of which schedule a number of user requests accumulated in a certain period. MDTA is to assign multiple data transfer requests on several pre-specified network paths to minimize the total data transfer end time, while MFBR is to satisfy multiple bandwidth reservation requests, each of which specifies a bandwidth and a time slot. For MDTA, we design an optimal algorithm and provide its correctness proof; for MFBR, we prove it to be NP-complete and propose a heuristic algorithm, Minimal Bandwidth and Distance Product Algorithm (MBDPA). Extensive simulation results illustrate the performance superiority of the proposed MBDPA over a greedy heuristic approach and provide valuable insight into the advantage of periodic bandwidth scheduling over instant bandwidth scheduling.

Augmented reality (AR) often makes use of a 2D fiducial marker to render computer graphics onto a video frame so that the computer-generated object appears aligned with the scene. We extend this idea to 3D where real-world objects are used as fiducial markers and propose a distributed AR system that utilizes geographically located resources to meet high computing demand, enable sustained remote operations, and support collaborative efforts. Within the distributed AR system, we present technical solutions to several key modules in AR that form a linear computing pipeline. We generalize and formulate the pipeline network mapping as optimization problems under different mapping constraints and develop heuristic algorithms that maximize the frame rate to achieve smooth data flow. Extensive simulation-based results show that the proposed mapping heuristics outperform the existing methods.

Next-generation computation-intensive applications in various fields of science and engineering feature large-scale computing workflows with complex structures that are often modeled as directed acyclic graphs. Supporting such task graphs and optimizing their end-to-end network performances in heterogeneous computing environments are critical to the success of these distributed applications that require fast response. We construct analytical models for computing modules, network nodes, and communication links to estimate data processing and transport overhead, and formulate the task graph mapping with node reuse and resource sharing for minimum end-to-end delay as an NP-complete optimization problem. We propose a heuristic approach to this problem that recursively computes and maps the critical path to the network using a dynamic programming-based procedure. The performance superiority of the proposed approach is justified by an extensive set of experiments on simulated data sets in comparison with existing methods.

New types of networks are emerging for the purpose of transmitting large amounts of scientific data among research institutions quickly and reliably. These exotic networks are characterized by being high-bandwidth, high-latency, and free from congestion. In this environment, TCP ceases to be an appropriate protocol for reliable bulk data transfer because it fails to saturate link throughput. Of the new protocols designed to take advantage of these networks, a subclass has emerged using UDP for data transfer and TCP for control. These high-speed variants of reliable UDP, however, tend to underperform on all but high-end systems due to constraints of the CPU, network, and hard disk. It is therefore necessary to build a high-speed protocol adaptive to the performance of each system. This paper develops such a protocol, Performance Adaptive UDP (henceforth PA-UDP), which aims to dynamically and autonomously maximize performance under different systems. A mathematical model and related algorithms are proposed to describe the theoretical basis behind effective buffer and CPU management. Based on this model, we implemented a prototype under Linux and the experimental results demonstrate that PA-UDP outperforms an existing high-speed protocol on commodity hardware in terms of throughput and packet loss. PAUDP is efficient not only for high-speed research networks but also for reliable high-performance bulk data transfer over dedicated local area networks where congestion and fairness are typically not a concern.

Supporting high performance computing pipelines over wide-area networks is critical to enabling large-scale distributed scientific applications that require fast responses for interactive operations or smooth flows for data streaming. We construct analytical cost models for computing modules, network nodes, and communication links to estimate the computing times on nodes and the data transport times over connections. Based on these time estimates, we present the efficient linear pipeline configuration method based on dynamic programming that partitions the pipeline modules into groups and strategically maps them onto a set of selected computing nodes in a network to achieve minimum end-to-end delay or maximum frame rate. We implemented this method and evaluated its effectiveness with experiments on a large set of simulated application pipelines and computing networks. The experimental results show that the proposed method outperforms the streamline and greedy algorithms. These results, together with polynomial computational complexity, make our method a potential scalable solution for large practical deployments.

We describe a system for computational monitoring and steering of an on-going computation or visualization on a remote host such as workstation or supercomputer. Unlike the conventional “launch-and-leave” batch computations, this system enables: (i) continuous monitoring of variables of an on-going remote computation using visualization tools, and (ii) interactive specification of chosen computational parameters to steer the computation. The visualization and control streams are supported over wide-area networks using transport protocols based on stochastic approximationmethods to provide stable throughput. Using performance models for transport channels and visualization modules, we develop a visualization pipeline configuration solution that minimizes end-to-end delay over wide-area connections. The user interface utilizes Asynchronous JavaScript and XML (Ajax) technologies to provide an interactive environment that can be accessed by multiple remote users using web browsers. We present experimental results on a geographically distributed deployment to illustrate the effectiveness of the proposed system.

We consider six classes of linear pipeline configuration problems with different mapping objectives and network constraints in distributed heterogeneous computing environments. We prove that two of them are polynomially solvable and the rest are NP-complete, for each of which, an optimal or heuristic algorithm based on dynamic programming is designed. Extensive simulation results illustrate the efficacy of these algorithms in comparison with existing methods.

Next-generation scientific applications require the capability to visualize large archival data sets or on-going computer simulations of physical and other phenomena over wide-area network connections. To minimize the latency in interactive visualizations across wide-area networks, we propose an approach that adaptively decomposes and maps the visualization pipeline onto a set of strategically selected network nodes. This scheme is realized by grouping the modules that implement visualization and networking subtasks and mapping them onto computing nodes with possibly disparate computing capabilities and network connections. Using estimates for communication and processing times of subtasks, we present a polynomial-time algorithm to compute a decomposition and mapping to achieve minimum end-to-end delay of the visualization pipeline. We present experimental results using geographically distributed deployments to demonstrate the effectiveness of this method in visualizing data sets from three application domains.

The advance in high-throughput genomic technologies including microarrays has generated a tremendous amount of gene expression data for the entire genome. Deciphering transcriptional networks that convey information on members of gene clusters and cluster interactions is a crucial analysis task in the post-sequence era. Most of the existing analysis methods for large-scale genome-wide gene expression profiles involve several steps that often require human intervention. We propose a random matrix theory-based approach to analyze the cross correlations of gene expression data in an entirely automatic and objective manner to eliminate the ambiguities and subjectivity inherent to human decisions. The correlations calculated from experimental measurements typically contain both "genuine" and "random" components. In the proposed approach, we remove the "random" component by testing the statistics of the eigenvalues of the correlation matrix against a "null hypothesis" - a truly random correlation matrix obtained from mutually uncorrelated expression data series. Our investigation on the components of deviating eigenvectors using varimax orthogonal rotation reveals distinct functional modules. We apply the proposed approach to the publicly available yeast cycle expression data and produce a transcriptional network that consists of interacting functional modules. The experimental results nicely conform to those obtained in previously published literatures

A control-plane architecture for supporting advance reservation of dedicated bandwidth channels on a switched network infrastructure is described including the front-end web interface, user and token management scheme, bandwidth scheduler, and signaling daemon. A path computation algorithm for bandwidth scheduling is proposed based on an extension of Bellman-Ford algorithm to an algebraic structure on sequences of disjoint non-negative real intervals. An implementation of this architecture for UltraScience Net is briefly described.

Abstract Past researches on sensor network routing have been focused on efficiency and effectiveness of data dissemination. Few of them consider security issues during the design time of routing protocols. Security is very important for many sensor network applications. Studies and experiences have shown that considering security during design time is the best way to provide security for sensor network routing. In this paper, we propose an efficient key management scheme and a novel secure routing protocol—Secure cell relay (SCR) for sensor networks. We also present an effective key setup scheme for sensor nodes deployed in the later stage. We analyze the security of SCR under various attacks and show that SCR is very effective in defending against several sophisticated attacks, including selective forwarding, sinkhole, wormhole, Sybil, hello flooding, and clone attacks. SCR is an energy‐efficient routing protocol with acceptable security overhead. Our simulations demonstrate that with all the security primitives, SCR still has lower energy consumption and higher delivery ratio than a popular routing protocol—directed diffusion. Copyright © 2006 John Wiley & Sons, Ltd.

The capacities of Internet backbone links have been continuously improving over the last decade, but such improvements have not been fully realized at the application level, particularly in high-performance applications. The complicated and monolithic TCP-AIMD dynamics are responsible to a large degree for low throughputs as a result of the difficulty in optimally configuring its parameters such as buffer sizes, AIMD coefficients, and slow-start transition points. In this paper, we propose a new class of UDP-based transport protocols that utilize a rate control scheme founded on the stochastic approximation method to achieve high throughputs at the application level. These protocols operate around a local maximum of the throughput regression curve by dynamically adjusting the source rate in response to acknowledgements and losses based on the statistical behavior of the network connection. We analytically show that this protocol generates a TCP-friendly flow, and also stochastically converges to the maximum throughput under a monotone loss rate condition. Our implementation achieved very robust performance over diverse Internet connections with different characteristics: it tracked the peak throughput in presence of time-varying cross traffic and consistently achieved 2-5 times the throughput of default TCP without significantly affecting the concurrent regular traffic.

A number of science applications employing collaborative computations require transport methods that guarantee end- to-end performance at the application level. Throughputs achieved by the traditional transport methods are limited to single default best-effort IP paths, which are often insufficient for the application tasks. In this paper, we present a measurement-based approach that utilizes application-level daemons at the collaborating sites to enhance the transport performance by utilizing multiple quickest paths. This method is based on a linear approximation of the effective bandwidth, and is computationally efficient and analytically tractable under fairly general conditions. We implemented and tested this method at Internet nodes, and the experimental results show significant performance improvements over the default TCP.

This paper discusses algorithmic and implementation aspects of a remote visualization system, which adoptively decomposes and maps the visualization pipeline onto a wide-area network. Visualization pipeline modules such as filtering, geometry extraction, rendering, and display are dynamically assigned to network nodes to achieve minimal total delay or maximal frame rate. Polynomial-time optimal algorithms using the dynamic programming method to compute the optimal decomposition and mapping are proposed. We implemented an OpenGL-based remote visualization system. We evaluated its performance using a deployment at three geographically distributed nodes.

The problem of computing a route for a mobile agent that incrementally fuses the data as it visits the nodes in a distributed sensor network is considered. The order of nodes visited along the route has a significant impact on the quality and cost of fused data, which, in turn, impacts the main objective of the sensor network, such as target classification or tracking. We present a simplified analytical model for a distributed sensor network and formulate the route computation problem in terms of maximizing an objective function, which is directly proportional to the received signal strength and inversely proportional to the path loss and energy consumption. We show this problem to be NP-complete and propose a genetic algorithm to compute an approximate solution by suitably employing a two-level encoding scheme and genetic operators tailored to the objective function. We present simulation results for networks with different node sizes and sensor distributions, which demonstrate the superior performance of our algorithm over two existing heuristics, namely, local closest first and global closest first methods.

In window-based transport methods for stabilizing and/or maximizing the goodput at the destination, it is very important to understand the statistical properties of the transport control and performance response parameters. Based on traffic measurements collected over the Internet during a 6-month period, we formulate and test hypotheses on the main effects of two control parameters on the goodput response and the interaction effects between them. We infer from the statistical analysis that the congestion window and sleep time parameters strongly interact with each other, and they both have significant main effects on the destination goodput. Consequently the underlying randomness in network traffic must be explicitly accounted for in the design of flow control methods.

Mobile robot teams are increasingly deployed in various applications involving remote operations in unstructured environments that do not support wireless network infrastructures. We propose a class of protocols based on the connectivity-through-time concepts that exploit the robot movements to extend the traditional notions of network connectivity. These protocols enable the formation of adhoc networks of mobile robots without the infrastructure of access points by utilizing the robots as routers. These protocols are implemented as a collection of daemons that track connectivity changes, compute single and multiple hop connectivity, route the packets via robots with suitable buffering, and adapt the transport parameters to the connection characteristics. The implementation employs UDP with window-based flow control that is tuned to the nature of connections. We present experimental performance results based on our implementation on robot teams to illustrate the salient features of this approach.

Abstract The explosive growth of digital image collections on the Web sites is calling for an efficient and intelligent method of browsing, searching, and retrieving images. In this article, an artificial neural network (ANN)‐based approach is proposed to explore a promising solution to the Web image retrieval (IR). Compared with other image retrieval methods, this new approach has the following characteristics. First of all, the Content‐Based features have been combined with Text‐Based features to improve retrieval performance. Instead of solely relying on low‐level visual features and high‐level concepts, we also take the textual features into consideration, which are automatically extracted from image names, alternative names, page titles, surrounding texts, URLs, etc. Secondly, the Kohonen neural network model is introduced and led into the image retrieval process. Due to its self‐organizing property, the cognitive knowledge is learned, accumulated, and solidified during the unsupervised training process. The architecture is presented to illustrate the main conceptual components and mechanism of the proposed image retrieval system. To demonstrate the superiority of the new IR system over other IR systems, the retrieval result of a test example is also given in the article.