Unsupervised anomaly detection (UAD) plays an important role in modern data analytics and it is crucial to provide simple yet effective and guaranteed UAD algorithms for real applications. In this paper, we present a novel UAD method for tabular data by evaluating how much noise is in the data. Specifically, we propose to learn a deep neural network from the clean (normal) training dataset and a noisy dataset, where the latter is generated by adding highly diverse noises to the clean data. The neural network can learn a reliable decision boundary between normal data and anomalous data when the diversity of the generated noisy data is sufficiently high so that the hard abnormal samples lie in the noisy region. Importantly, we provide theoretical guarantees, proving that the proposed method can detect anomalous data successfully, although the method does not utilize any real anomalous data in the training stage. Extensive experiments through more than 60 benchmark datasets demonstrate the effectiveness of the proposed method in comparison to 12 baselines of UAD. Our method obtains a 92.27% AUC score and a 1.68 ranking score on average. Moreover, compared to the state-of-the-art UAD methods, our method is easier to implement.

Large neural network models are hard to deploy on lightweight edge devices demanding large network bandwidth. In this article, we propose a novel deep learning (DL) model compression method. Specifically, we present a dual-model training strategy with an iterative and adaptive rank reduction (RR) in tensor decomposition. Our method regularizes the DL models while preserving model accuracy. With adaptive RR, the hyperparameter search space is significantly reduced. We provide a theoretical analysis of the convergence and complexity of the proposed method. Testing our method for the LeNet, VGG, ResNet, EfficientNet, and RevCol over MNIST, CIFAR-10/100, and ImageNet datasets, our method outperforms the baseline compression methods in both model compression and accuracy preservation. The experimental results validate our theoretical findings. For the VGG-16 on CIFAR-10 dataset, our compressed model has shown a 0.88% accuracy gain with 10.41 times storage reduction and 6.29 times speedup. For the ResNet-50 on ImageNet dataset, our compressed model results in 2.36 times storage reduction and 2.17 times speedup. In federated learning (FL) applications, our scheme reduces 13.96 times the communication overhead. In summary, our compressed DL method can improve the image understanding and pattern recognition processes significantly.

This paper proposes a new global model aggregation method based on using zero-knowledge federated learning (ZKFL). The purpose is to secure horizontal or P2P federated machine learning systems with shorter aggregation times, higher model accuracy, and lower system costs. We use a model parameter-sharing Chord overlay network among all client hosts. The overlay guarantees a trusted sharing of zero-knowledge proofs for aggregation integrity, even under malicious Byzantine attacks. We tested over popular datasets, Fashion-MNIST and CIFAR10, to prove the new system protection concept. Our benchmark experiments validate the claimed advantages of the ZKFL scheme in all objective functions. Our aggregation method can be applied to secure both rank-based and similarity-based aggregation schemes. For a large system with over 200 clients, our system takes only 3 seconds to yield high-precision global machine models under the ALIE attacks with the Fashion-MNIST dataset. We have achieved up to 85% model accuracy, compared to only 3%$\sim$45% accuracy observed with federated schemes without protection. Moreover, our method demands a low memory overhead for handling zero-knowledge proofs as the system scales greatly to a larger number of client nodes.

Distributed cloud/edge (DCE) platform has become popular in recent years. This paper proposes a new AI benchmark suite for assessing the performance of DCE platforms in machine learning (ML) and cognitive science applications. The benchmark suite is custom-designed to satisfy scenario-based performance requirements, namely the model training time, inference speed, model accuracy, job response time, quality of service, and system reliability. These metrics are substantiated by intensive experiments with real-life AI workloads. Our work is specially tailored for supporting massive AI multitasking across distributed resources in the networking environment. Our benchmark experiments were conducted on an AI-oriented AIRS cloud built at the Chinese University of Hong Kong, Shenzhen. We have tested a large number of ML/DL programs to narrow down the inclusion of ten representative AI kernel codes in the benchmark suite. Our benchmark results reveal the advantages of using the DCE systems cost-effectively in smart cities, healthcare, community surveillance, and transportation services. Our technical contributions are in the AIRS cloud architecture, benchmark design, testing, and distributed AI computing requirements. Our work will benefit computer system designers and AI application developers on clouds, edge, and mobile devices, that are supported by 5G mobile networks and AIoT resources.

Distributed cloud/edge resources are needed to execute pervasive artificial intelligence tasks, collectively. The AI workload and data sets have variable multitasking granularity, privacy constraints, and communication latency concerns. This article presents a novelfederated cloud/edge(FCE)framework, illustrated by distributed medical image processing across multiple hospital sites. This federated cloud system appeals to train many machine learning models efficiently with workload balancing and reduced communication overheads. We tested the FCE model on a multi-cloud platform recently built at the Chinese University of Hong Kong in Shenzhen. We claim three distinct advantages in using the FCE system. First, our federated cloud system results in 41.3% reduction in total AI processing time in large-scale ML/DL experiments. Second, high machine model accuracy was achieved at 87% level in telemedicine experiments. The virtual graph helps reduce internode traffic latencies to avoid ML inference slowdowns. Third, the system can tolerate multiple cloud failures to enter a graceful degradation mode in case of node failures. The scalable performance gains in AI processing speed, model accuracy, and fault tolerance make our federated clouds a truly viable approach to solving massive AI multitasking problems in pervasive AI applications.

In the big data era, resource-constrained mobile devices generate an overwhelmingly large amount of data with complex tasks that demand distributed execution. Offloading computation-intensive tasks to nearby edge clouds is promising to solve this problem. However, mobile end devices cannot handle heterogeneous or delay-sensitive tasks. These end devices are also energy constrained with weak adaptability to environment changes. To address and tackle these problems, we present a two-moduletransfer reinforcement learning(TRL) framework for adaptive task offloading. A domain adaptation module is used to align heterogeneous characteristics of mobile devices. The TRL makes offloading decisions with adeep reinforcement learning(DRL) module. We evaluate the performance of TRL through real-world experiments on edge clouds. Our experiment results show that TRL reduces the task processing time by a factor of 20% from using three well known DRL methods. Our method achieved (15.4$\sim$40)% reduction in task drop rate over these methods. With domain adaptation, the TRL results in (50$\sim$80)% reduction in model convergence time. These advantages in using the TRL framework make it appealing in real-life edge computing applications.

Drone-swarm-assisted mobile edge computing (MEC) provides extra computation and storage capacity for smart city applications and the Industrial Internet of Things. To solve the problems of traditional fixed base stations in a complex terrain, including cost of deployment, transmission loss of telecommunication, and limited coverage, this article brings forward the unmanned aerial vehicles (UAVs) as MEC nodes in the air. For the purpose of matching the dynamic mobile devices and UAV trajectory, this article raises a multi-UAVs-assisted MEC offloading algorithm based on global and local path planning controlled by ground station and onboard computer. Firstly, this article considers a drone swarm scheduling and allocation strategy based on the priority of monitoring areas, UAVs residual energy and distance to target points, so as to minimize the global flight length and energy consumption. Secondly, based on user mobility, this article calculates the optimal communication coverage of a UAV, and jointly optimizes the local path planning and computing offloading, so as to maximize the number of offloading services and minimize the total latency in completing the computation task. Finally, based on the total latency and energy consumption of path planning and computation offloading, a UAV cluster computation offloading strategy with optimized energy efficiency is realized. Experimental results prove that the proposed algorithm can provide more offloading services while obtaining shorter path length and greater energy efficiency.

The future ubiquitous network, which is mainly characterized by full coverage communication, air-ground integration, multidimensional fusion, network reconfiguration and sensing-communication-computing integration, has become the development trend of 6G technology. The realization of ubiquitous coverage and perceptive fusion of IoT-UAV-Edge is an urgent problem to be solved for complex fusion services. Therefore, this paper proposes a drone-enabled smart air agent in 6G edge fusion system. Firstly, the energy efficient dynamic routing strategy based on joint air-ground control optimization is designed to improve the fusion sensing performance and prolong the service time of drone swarm. Then, the system integration of user-IoT-UAV-Edge is realized to achieve the functionalities of perception, transmission, computing and analysis. Finally, an airborne data fusion mechanism based on multi-source sensing is designed to solve the associated cognitive optimization problem for multi-modal information. The experimental results invalidate the effectiveness and practicability of our system on autonomous path planning, effective computing offloading and accurate airborne fusion.

As the mainstream solution for semi-supervised learning (SSL), pseudo-labeling-based approaches have achieved re-markable success. However, an obvious drawback of existing methods is that the valuable semantic relationships among categories are often ignored, thus leading to suboptimal encoded embeddings. To address this, we present a novel Semantics-Enhanced Pseudo Labeling Network, called SEPL-Net, for image analysis in a semi-supervised manner. SEPL-Net explores the prior knowledge of visual similarity between different classes to improve the quality of pseudo label decision making. Particularly, we encode semantic labels combined with the one-hot label to jointly train our network by exploiting their disagreement. To alleviate the difficulty of labeling unlabeled images due to the introduction of semantic labels, we further design different classifiers with differentiated strong augmentation modes to enable cooperative pseudo labeling. Extensive experimental results show that our SEPL-Net outperforms existing SSL methods with the averaged 1.84% accuracy improvement on image classification task. Code is available at https://github.com/sweetvicky/SEPLNet.git.

Spark SQL has been widely deployed in industry but it is challenging to tune its performance. Recent studies try to employ machine learning (ML) to solve this problem, but suffer from two drawbacks. First, it takes a long time (high overhead) to collect training samples. Second, the optimal configuration for one input data size of the same application might not be optimal for others.

Big-data frameworks such as MapReduce/Hadoop or Spark have many performance-critical configuration parameters which may interact with each other in a complex way. Their optimal values for an application on a given cluster are affected by not only the application itself but also its input data. This makes offline auto-configuration approaches hard to be used in practice because the input data of an application may change at each run. To address this issue, we propose an Online Self-Configuring (OSC) approach that automatically determines the optimal parameter values for a given application. OSC synergistically integrates three key techniques. First, OSC leveragesensemble learningto build a precise performance model for a given application. Second, it quantifies theimportanceof the parameters andinteraction intensitybetween them to accelerate the genetic algorithm for searching optimal configuration parameters. Third, OSC supports anincremental modelingapproach to achieve low overhead of the models for online needs. These techniques allow OSC to effectively learn the characteristics of an application and optimize its performance by automatically adjusting the configurations at runtime. Our implementation of OSC atop MapReduce/Hadoop 2.6 improves performance by 60 percent on average and up to 120 percent compared with the state-of-the-art approach. Lastly, the performance benefit of an application running on OSC generally increases along with its input data size.

With the widespread application of artificial intelligence and the Internet of Things, the intellectualization of the industrial Internet of Things (IIoT) has received more and more attention. However, in the application scenario with numerous sensors, the contradiction between massive requests of computing tasks and high requirements of inference quality affects the operation efficiency and service reliability. Moreover, due to the heterogeneity of computing resources and the randomness of communication environments of the cloud-edge system, how to compute and deploy deep learning models in a cloud-edge collaborative environment has also become a challenging problem. Therefore, this article presents a collaborative cloud-edge service cognitive framework for deep neural network (DNN) model service configuration to provide dynamic and flexible computing services. In order to adapt to different service requirements, we explored the tradeoffs between accuracy, latency, and energy consumption indicators, and a revenue target is established, which considers the quality of service experience and the system energy consumption to improve resource utilization efficiency. By transforming the optimization of the revenue target into a partially observable DNN configuration reinforcement learning problem, a dueling deep Q-learning network-based self-adaptive DNN configuration algorithm is proposed. Experimental results show that the proposed mechanism can effectively learn from external experience, adapt to the dynamic network environment, and reduce delay and energy consumption while meeting the service requirements.

The outbreak of the corona virus disease 2019 (COVID-19) has caused serious harm to people’s physical and mental health. Due to the serious situation of the epidemic, a lot of negative energy information increases people’s psychological burden. However, effective interventions against mental health problems are not in abundance. To address such challenges, in this article, we propose the concept of negative information to describe information that has a negative impact on people’s mental health. To achieve the measurement of negative information, the level of mental health inversely measures the degree of negative information. Specifically, we design a system to measure the negative information used to monitor the mental health state of the user under the impact of negative information. The cognition of mental health is realized based on the intelligent algorithm deployed on the edge cloud, and the needs of users can be responded to in real time in practical applications. Finally, we use real collected dataset to verify the influence of negative information. The experiments show that the system can achieve negative information measurement and provide an effective countermeasure for solving mental health problems during a pandemic situation.

Different placement or collaboration policies in handling datasets and workloads across cloud, edge, and user-end may substantially affect a cloud-edge computing environment's overall performance. However, the common practice is to optimize the performance only on the edge layer, while ignoring the rest of the system. This paper calls attention to optimize AI-oriented workloads' performance across all components in cloud-edge architectures holistically. Our goal is to optimize AI-workload allocation in cloud clusters, edge servers, and end devices, achieving the minimum response time in latency-sensitive applications. This paper presents new workload allocation methods for AI workloads in cloud-edge computing systems. We have proposed two efficient allocation algorithms to reduce the end-to-end response time of single-workload and multi-jobs scenarios, respectively. We apply six edge AI workloads from a comprehensive edge computing benchmark - Edge AIBench for experiments. Besides, we conduct experiments in a real edge computing environment. Our experiment results demonstrate the high efficiency and effectiveness of our algorithms in real-life applications and datasets. Our multi-job allocation algorithm's end-to-end response time outperforms the other four baseline strategies by 33% to 63%.

As an information carrier, the Internet of Things (IoT) based on the Internet and sensing equipment makes all physical objects form an interconnected network. The 5th generation mobile networks (5G) technology has many advantages, such as high data rates, reduced latency, energy savings, reduced costs, increased system capacity and large-scale device connectivity, realize the real-time data collection, transmission, analysis, management, and application in the era of global Internet of Everything. In order to quickly respond to people’s daily requirements and provide the smart application based on artificial intelligence technology in various scenarios, the number of IoT devices will further increase. The integration of mobile-edge computing (MEC) and IoT is imperative, especially in industries needing real-time data computing, such as smart home, public security, automobile transportation, smart health, emotion care, etc. As a new form of IoT terminal combining 5G and MEC, wearable device based on intelligent fabrics plays an important role in smart health and emotion care, which is one of the potential development directions of the next generation of intelligent medical and rehabilitation systems.

Currently, the integration of distributed energy generators through virtual power plants in the Internet of Energy is a mainstream method. The complex structure of virtual power plants and the characteristics of distributed energy make it difficult to solve the economic dispatch problems of virtual power plants. In addition, the load of a virtual power plant is unstable and uncertain and thus requires a robust economic dispatch strategy. Because the selection of the set of uncertain conditions is conservative, the traditional robust economic dispatch strategies cannot effectively reduce the cost of virtual power plants. In addition, the traditional methods for solving robust strategies cannot directly solve nonlinear and nonconvex problems. In this article, we propose a scenario-based robust economic dispatch strategy for virtual power plants, aiming to reduce the operational costs of virtual power plants. First, to reduce the conservatism of the strategy, scenario-based data augmentation is adopted for data generation. Through a generative adversarial network, a large amount of scene data are generated to extend the set of uncertain conditions. The scene data cannot only reduce the conservatism but also can be used in the determination of robust strategies. Second, deep reinforcement learning is adopted for historical data training, directly solving nonlinear and nonconvex problems to obtain a robust economic dispatch strategy. As experiments show, with the accurate generation of scene data, the proposed economic dispatch strategy is robust and effectively reduces the cost of virtual power plants.

The frequent occurrence of suicides in modern society constitutes a serious public health issue. While the motives, methods, and consequences of suicide are quite complicated, if people at risk of suicide can be identified and intervened in time, the loss of life can be reduced. Through analyses based on combining a large number of suicide texts and professional medical literature, a dictionary of potential suicide risk impact factors has been established in this article. Based on this dictionary, a novel medical-level suicide risk standard is proposed to monitor suicide risk from point-to-surface under the timeline baseline. In order to solve the problem of insufficient Chinese suicide data sets, the manually assisted method based on knowledge perception is adopted to annotate the data set with corresponding to risk level. At the same time, a Bert evaluation model based on knowledge perception was established for the classification of risk level. The experimental results showed that proposed method has a 56% recognition accuracy in the prediction of 10-Label suicide risk level proposed in this article, and the classification performance is better than traditional machine learning algorithms. Therefore, the results showed that the classification standard and evaluation model can be effectively used for the identification and early warning of suicide risk, which can discover high suicide risk groups to reduce the occurrence of suicide. It is of great significance to people’s emotion care monitoring.

The unified management of IoT devices with interoperability can be inspired by cloud computing. In addition, sinking the 5G core network to the edge brings chances for the deployment of end-to-end ultralow-latency services. However, the resource efficiency brought by heterogeneous computing devices in 5G spectrum multiplexing environments has encountered challenges. To discuss this issue from a comprehensive perspective, this article first proposes an ultralow-latency service deployment architecture in 5G heterogeneous networks, and three cognitive engines are the key components for efficient service communication across the terminal/edge/cloud computing structure. Then we give an analysis of application task model in the proposed architecture, and following the service response time models are established. In addition, it is efficient to deploy multiuser tasks with constraint resources when the differentiated user requirements are met. Finally, we conducted some experiments and the result statistics are up to our expectations. The first one is the system performance under two microcloud covered cells, and the second one is the performance comparison of the proposed solution with three single scenes of terminal computing, edge computing and cloud computing.

Linux servers are being used in almost all clouds, datacenters and supercomputers today. Linux Kernel functions are facing a kind of malware attacks, known as rootkits with root-access capability. The rootkits appear asloadable kernel modules(LKM) in today's Linux servers. These modules hide from other kernel objects, and can redirect the kernel control flow by tampering with the metadata needed in kernel service functions. The kernel rootkits are invisible to users after loading, which may bypass most security shields. Both spatial and temporal appearance of rootkits are randomly distributed, which makes it difficult to detect or removal. To deal with rootkit threats, we propose a novelVirtual Wall(VTW) approach to filtering out the rootkit-embedded LKMs by tracing the incurred kernel activities. This VTW is essentially a lightweight hypervisor built with rootkit detection and event tracing capabilities. Normally, the Linux runs in a guest mode. When a LKM execution violates the security policy set by the VTW, the OS control will switch to a host mode. The VTW at host mode enables the detection and tracing of rootkit events timely. In other words, potential rootkit attacks are detected, traced and classified to make meaningful filtering decisions. The whole detection and tracing process is based on memory access control and event injection mechanisms. Experimental results show that the VTW defense system is effective to detect and defend against kernel rootkits timely. The CPU overhead for executing VTW is less than 2 percent. Compared with other defense schemes (such as DIKernel, etc.), our vs is easier to implement with low performance degradation on Linux servers. We will demonstrate the advantages of VTW through its simplicity in implementation and potential performance gains. We will also compare our system with seven other rootkit defense systems.

Future industrial cyber-physical system (CPS) devices are expected to request a large amount of delay-sensitive services that need to be processed at the edge of a network. Due to limited resources, service placement at the edge of the cloud has attracted significant attention. Although there are many methods of design schemes, the service placement problem in industrial CPS has not been well studied. Furthermore, none of existing schemes can optimize service placement, workload scheduling, and resource allocation under uncertain service demands. To address these issues, we first formulate a joint optimization problem of service placement, workload scheduling, and resource allocation in order to minimize service response delay. We then propose an improved deep Q-network (DQN)-based service placement algorithm. The proposed algorithm can achieve an optimal resource allocation by means of convex optimization where the service placement and workload scheduling decisions are assisted by means of DQN technology. The experimental results verify that the proposed algorithm, compared with existing algorithms, can reduce the average service response time by 8-10%.

With increasing popularity of related applications of mobile crowdsensing, especially in the field of Internet of Vehicles (IoV), task allocation has attracted wide attention. How to select appropriate participants is a key problem in vehicle-based crowdsensing networks. Some traditional methods choose participants based on minimizing distance, which requires participants to submit their current locations. In this case, participants' location privacy is violated, which influences disclosure of participants' sensitive information. Many privacy preserving task allocation mechanisms have been proposed to encourage users to participate in mobile crowdsensing. However, most of them assume that different participants' task completion quality is the same, which is not reasonable in reality. In this paper, we propose an optimal location privacy preserving and service quality guaranteed task allocation in vehicle-based crowdsensing networks. Specifically, we utilize differential privacy to preserve participants' location privacy, where every participant can submit the obfuscated location to the platform instead of the real one. Based on the obfuscated locations, we design an optimal problem to minimize the moving distance and maximize the task completion quality simultaneously. In order to solve this problem, we decompose it into two linear optimization problems. We conduct extensive experiments to demonstrate the effectiveness of our proposed mechanism.

The increasingly popular fused batch-streaming big data framework, Apache Flink, has many performance-critical as well as untamed configuration parameters. However, how to tune them for optimal performance has not yet been explored. Machine learning (ML) has been chosen to tune the configurations for other big data frameworks (e.g., Apache Spark), showing significant performance improvements. However, it needs a long time to collect a large amount of training data by nature. In this article, we propose a guided machine learning (GML) approach to tune the configurations of Flink with significantly shorter time for collecting training data compared to traditional ML approaches. GML innovates two techniques. First, it leverages generative adversarial networks (GANs) to generate a part of training data, reducing the time needed for training data collection. Second, GML guides a ML algorithm to select configurations that the corresponding performance is higher than the average performance of random configurations. We evaluate GML on a lab cluster with 4 servers and a real production cluster in an internet company. The results show that GML significantly outperforms the state-of-the-art, DAC (Datasize-Aware-Configuration) (Z. Yu et al. 2018) for tuning the configurations of Spark, with 2.4× of reduced data collection time but with 30 percent reduced 99th percentile latency. When GML is used in the internet company, it reduces the latency by up to 57.8× compared to the configurations made by the company.

In recent years, the rapid growth of traffic has become a serious problem of mobile network operators. For effectively mitigating this traffic explosion problem, there have been many efforts to research on offloading the traffic from cellular links to direct communications among users. In this paper, we are motivated by users' sharing activities, and hence propose the framework of Traffic Offloading assisted by Social network services (SNS) via opportunistic Sharing in mobile social networks (MSNs), TOSS, to offload SNS-based cellular traffic by user-to-user sharing. First, a subset of users who are to receive the same content was selected as initial population depending on their content spreading impacts in the online SNSs and their mobility patterns in the offline MSNs. Then users move, encounter and share the content via opportunistic local connectivity with each other, the content via opportunistic local connectivity with each other, e.g., Bluetooth, Wi-Fi Direct, Device-to-Device in LTE. Individual users have distinct access patterns, which potentially allow TOSS to exploit the user-dependent access delay between the content generation time and each user's access time for content sharing purposes. The traffic offloading and content spreading among users are analyzed by taking into account various options in linking SNS and MSN traces. Four mobility traces and online SNS trace for evaluation are analyzed. An extended evaluation over a large-scale data set are further carried out, and the effectiveness of TOSS is further proved.

Data exchange is one of the huge challenges in Internet of Things (IoT) with billions of heterogeneous devices already connected and many more to come in the future. Improving data transfer efficiency, scalability, and survivability in the fragile network environment and constrained resources in IoT systems is always a fundamental issues. In this paper, we present a novel message routing algorithm that optimizes IoT data transfers in a resource constrained and fragile network environment in publish-subscribe model. The proposed algorithm can adapt the dynamical network topology of continuously changing IoT devices with the rerouting method. We also present a rerouting algorithm in Message Queuing Telemetry Transport (MQTT) to take over the topic-based session flows with a controller when a broker crashed down. Data can still be communicated by another broker with rerouting mechanism. Higher availability in IoT can be achieved with our proposed model. Through demonstrated efficiency of our algorithms about message routing and dynamically adapting the continually changing device and network topology, IoT systems can gain scalability and survivability. We have evaluated our algorithms with open source Eclipse Mosquitto. With the extensive experiments and simulations performed in Mosquitto, the results show that our algorithms perform optimally. The proposed algorithms can be widely used in IoT systems with publish-subscribe model. Furthermore, the algorithms can also be adopted in other protocols such as Constrained Application Protocol (CoAP).

With the popularity of wearable devices, along with the development of clouds and cloudlet technology, there has been increasing need to provide better medical care. The processing chain of medical data mainly includes data collection, data storage and data sharing, etc. Traditional healthcare system often requires the delivery of medical data to the cloud, which involves users' sensitive information and causes communication energy consumption. Practically, medical data sharing is a critical and challenging issue. Thus in this paper, we build up a novel healthcare system by utilizing the flexibility of cloudlet. The functions of cloudlet include privacy protection, data sharing and intrusion detection. In the stage of data collection, we first utilize Number Theory Research Unit (NTRU) method to encrypt user's body data collected by wearable devices. Those data will be transmitted to nearby cloudlet in an energy efficient fashion. Second, we present a new trust model to help users to select trustable partners who want to share stored data in the cloudlet. The trust model also helps similar patients to communicate with each other about their diseases. Third, we divide users' medical data stored in remote cloud of hospital into three parts, and give them proper protection. Finally, in order to protect the healthcare system from malicious attacks, we develop a novel collaborative intrusion detection system (IDS) method based on cloudlet mesh, which can effectively prevent the remote healthcare big data cloud from attacks. Our experiments demonstrate the effectiveness of the proposed scheme.

Understanding the scalability of MapReduce applications is a challenging problem. The difficulty lies in the distributed mapping of the input big data. The distribution of data and compute resources must match with fluctuating network substrates. User-defined Map and Reduce functions over application parameters further complicate the issue. Therefore, it offers great payoff to use small datasets and limited test runs to reveal the behavior of MapReduce applications over big-data. In this paper, we analyze the scaling effects of server cluster-size over varieties of Map- and Reduce-intensive applications. In our study, we discover specific conditions which lead to the power-law conformity in representative MapReduce applications. We report four major discoveries: (1) Within a range of scaling parameters, MapReduce execution time follows the power-law distribution. (2) Power-law scalability for Map-intensive applications work well even with a small cluster size. (3) Shuffle-intensive applications exhibit power-law behavior starting from larger cluster size. (4) The scaling effects may depart from power-law distribution, if the cloud resources are heavily overprovisioned than the workload demands. The above findings enable users to use bounded test runs to allocate and configure virtual and physical resources in large-scale MapReduce applications. These results can be also applied in generating business models for providing cost-effective cloud computing services.

With the growing popularity of mobile devices, a new type of peer-to-peer communication mode for mobile cloud computing has been introduced. By applying a variety of short-range wireless communication technologies to establish connections with nearby mobile devices, we can construct a mobile cloudlet in which each mobile device can either works as a computing service provider or a service requester. Although the paradigm of mobile cloudlet is cost-efficient in handling computation-intensive tasks, the understanding of its corresponding service mode from a theoretic perspective is still in its infancy. In this paper, we first propose a new mobile cloudlet-assisted service mode named Opportunistic task Scheduling over Co-located Clouds (OSCC), which achieves flexible cost-delay tradeoffs between conventional remote cloud service mode and mobile cloudlets service mode. Then, we perform detailed analytic studies for OSCC mode, and solve the energy minimization problem by compromising among remote cloud mode, mobile cloudlets mode and OSCC mode. We also conduct extensive simulations to verify the effectiveness of the proposed OSCC mode, and analyze its applicability. Moreover, experimental results show that when the ratio of data size after task execution over original data size associated with the task is smaller than 1 (i.e.,r<; 1) and the average meeting rate of two mobile devices λ is larger than 0:00014, our proposed OSCC mode outperforms existing service modes.

In this paper, we present generic cloud performance models for evaluating Iaas, PaaS, SaaS, and mashup or hybrid clouds. We test clouds with real-life benchmark programs and propose some new performance metrics. Our benchmark experiments are conducted mainly on IaaS cloud platforms over scale-out and scale-up workloads. Cloud benchmarking results are analyzed with the efficiency, elasticity, QoS, productivity, and scalability of cloud performance. Five cloud benchmarks were tested on Amazon IaaS EC2 cloud: namely YCSB, CloudSuite, HiBench, BenchClouds, and TPC-W. To satisfy production services, the choice of scale-up or scale-out solutions should be made primarily by the workload patterns and resources utilization rates required. Scaling-out machine instances have much lower overhead than those experienced in scale-up experiments. However, scaling up is found more cost-effective in sustaining heavier workload. The cloud productivity is greatly attributed to system elasticity, efficiency, QoS and scalability. We find that auto-scaling is easy to implement but tends to over provision the resources. Lower resource utilization rate may result from auto-scaling, compared with using scale-out or scale-up strategies. We also demonstrate that the proposed cloud performance models are applicable to evaluate PaaS, SaaS and hybrid clouds as well.

The four papers in this special section aim to present high-quality contributions and innovations in this interdisciplinary area of mobile big data technologies, systems, and services, especially mobile big data management and innovative applications.

In the era of cloud computing and big data, virtualization is gaining great popularity in storage systems. Since multiple guest virtual machines (DomUs) are running on a single physical device, disk I/O fairness among DomUs and aggregated throughput remain the challenges in virtualized environments. Although several methods have been developed for disk I/O performance virtualization among multiple DomUs, most of them suffer from one or more of the following drawbacks. (1) A fair scheduling mechanism is missing when requests converge together from multiple queues. (2) Existing methods rely on better performance of the underlying storage system such as solid state drive (SSD). (3) Throughput and latency are not considered simultaneously. To address these disadvantages, this paper presents a virtual multi-channel of disk I/O (VMCD) method that can be built on top of an ordinary storage utility, which mitigates the interference among multiple DomUs by using separated virtual channel (V-Channel) and an I/O request queue for each DomU. In our VMCD, several mechanisms are employed to enhance the I/O performance, including a credit allocation mechanism, a global monitoring strategy, and a virtual multi-channel fair scheduling algorithm. The proposed techniques are implemented on the Xen virtual disk and evaluated on Linux guest operating systems. Experiments results show that VMCD increases fairness by 70 percent approximately compared with CFQ and Anticipatory schedulers, by 30 percent approximately compared with Deadline scheduler; and enhances bandwidth utilization by 28 percent approximately compared with CFQ and Anticipatory schedulers, by 37 percent compared with Deadline in the case of three or more virtual DomUs running on the same physical host.

A cloud mashup is composed of multiple services with shared datasets and integrated functionalities. For example, the elastic compute cloud (EC2) provided by Amazon Web Service (AWS), the authentication and authorization services provided by Facebook, and the Map service provided by Google can all be mashed up to deliver real-time, personalized driving route recommendation service. To discover qualified services and compose them with guaranteed quality of service (QoS), we propose an integrated skyline query processing method for building up cloud mashup applications. We use a similarity test to achieve optimal localized skyline. This mashup method scales well with the growing number of cloud sites involved in the mashup applications. Faster skyline selection, reduced composition time, dataset sharing, and resources integration assure the QoS over multiple clouds. We experiment with the quality of Web service (QWS) benchmark over 10,000 Web services along six QoS dimensions. By utilizing block-elimination, data-space partitioning, and service similarity pruning, the skyline process is shortened by three times, when compared with two state-of-the-art methods.

The scheduling of multitask jobs on clouds is an NP-hard problem. The problem becomes even worse when complex workflows are executed on elastic clouds, such as Amazon EC2 or IBM RC2. The main difficulty lies in the large search space and high overhead of generating optimal schedules, especially for real-time applications with dynamic workloads. In this work, a new iterative ordinal optimization (IOO) method is proposed. The ordinal optimization method is applied in each iteration to achieve sub-optimal schedules. IOO aims at generating more efficient schedules from a global perspective over a long period. We prove through overhead analysis the advantages in time and space efficiency in using the IOO method. The IOO method is designed to adapt to system dynamism to yield suboptimal performance. In cloud experiments on IBM RC2 cloud, we execute 20,000 tasks in LIGO (Laser Interferometer Gravitational-wave Observatory) verification workflow on 128 virtual machines. The IOO schedule is generated in less than 1,000 seconds, while using the Monte Carlo simulation takes 27.6 hours, 100 times longer to yield an optimal schedule. The IOO-optimized schedule results in a throughput of 1,100 tasks/sec with 7 GB memory demand, compared with 60 percent decrease in throughput and 70 percent increase in memory demand in using the Monte Carlo method. Our LIGO experimental results clearly demonstrate the advantage of using the IOO-based workflow scheduling over the traditional blind-pick, ordinal optimization, or Monte Carlo methods. These numerical results are also validated by the theoretical complexity and overhead analysis provided.

Processing large volumes of data has presented a challenging issue, particularly in data-redundant systems. As one of the most recognized models, the conditional random fields (CRF) model has been widely applied in biomedical named entity recognition (Bio-NER). Due to the internally sequential feature, performance improvement of the CRF model is nontrivial, which requires new parallelized solutions. By combining and parallelizing the limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) and Viterbi algorithms, we propose a parallel CRF algorithm called MapReduce CRF (MRCRF) in this paper, which contains two parallel sub-algorithms to handle two time-consuming steps of the CRF model. The MapReduce L-BFGS (MRLB) algorithm leverages the MapReduce framework to enhance the capability of estimating parameters. Furthermore, the MapReduce Viterbi (MRVtb) algorithm infers the most likely state sequence by extending the Viterbi algorithm with another MapReduce job. Experimental results show that the MRCRF algorithm outperforms other competing methods by exhibiting significant performance improvement in terms of time efficiency as well as preserving a guaranteed level of correctness.

An elastic cloud provisions machine instances upon user demand. Auto-scaling, scale-out, scale-up, or any mixture techniques are used to reconfigure the user cluster as workload changes. We evaluate three scaling strategies to upgrade the performance, efficiency and productivity of elastic clouds like EC2, Rack space, etc. We developed new performance models and run the Hi Bench benchmark to test Hadoop performance on various EC2 configurations. The strengths and shortcomings of three scaling strategies are revealed in our Hi Bench experiments: (1). Scale-out overhead is shown lower than that experienced in scale-up or mixed scaling clouds. Scale-out to a larger cluster of small nodes demonstrated high scalability. (2). Scaling up and mixed scaling have high performance in using smaller clusters with a few powerful machine instances. (3). With a mixed scaling mode, the cloud productivity is shown upgradable with higher flexibility in applications with performance/cost tradeoffs.

To support an efficient carpooling service in heavy urban traffic, we propose an intelligent routing scheme based on mining Global Position System trajectories from shared riders. The carpooling system provides many-to-many services with multiple pickup and dropping points. To join a daily carpooling group, the riders must accept a compromised route that is efficient after merging the routes that are preferred by all qualified riders. We developed three frequency-correlated algorithms for route mining, rider selection, and route merging in an urban carpool service. Our approach can cope with the traffic dynamics to yield a suboptimal shared route. Our scheme was successfully tested under heavy Beijing traffic over hundreds of riders. We developed performance metrics to measure the service cost and mileage saved. The ultimate goal is to minimize the riding distances and the transportation costs, and thus alleviate urban traffic jams.

With the advent of many-core systems capable of hosting multiple concurrently running applications, the traffic characteristics of networks-on-chip (NoCs) may exhibit new regional behaviors. By recognizing and exploiting these traffic behaviors, the effectiveness of NoC interference reduction techniques can be greatly improved. However, few works have investigated these regional behaviors and their potential impact on interference, leaving the opportunity largely unexplored. In this paper, we identify and characterize regional behavior in NoC and propose RAIR, a region-aware interference reduction technique that not only removes any restrictions on the inter-region traffic patterns, but also captures and exploits regional behavior throughout the design, thus improving the effectiveness of interference reduction. Evaluation using a cycle-accurate simulator shows that RAIR can improve the average packet latency by up to 17% on synthetic traffic patterns and up to 26% on PARSEC benchmarks compared to state-of-the-art interference reduction techniques.

The 13 papers in this special issue cover three major areas including privacy enhanced technology, trust and reputation, as well as applications in cloud computing environments.

As cloud computing becomes more and more popular, understanding the economics of cloud computing becomes critically important. To maximize the profit, a service provider should understand both service charges and business costs, and how they are determined by the characteristics of the applications and the configuration of a multiserver system. The problem of optimal multiserver configuration for profit maximization in a cloud computing environment is studied. Our pricing model takes such factors into considerations as the amount of a service, the workload of an application environment, the configuration of a multiserver system, the service-level agreement, the satisfaction of a consumer, the quality of a service, the penalty of a low-quality service, the cost of renting, the cost of energy consumption, and a service provider's margin and profit. Our approach is to treat a multiserver system as an M/M/m queuing model, such that our optimization problem can be formulated and solved analytically. Two server speed and power consumption models are considered, namely, the idle-speed model and the constant-speed model. The probability density function of the waiting time of a newly arrived service request is derived. The expected service charge to a service request is calculated. The expected net business gain in one unit of time is obtained. Numerical calculations of the optimal server size and the optimal server speed are demonstrated.

A new scheme of service oriented architecture for federating services provided by multiple clouds as one application is introduced. Service federating inter-cloud application configuration requires selecting a set of services from various clouds such that the user preferences and constraints are satisfied. This configuration process is defined as a multi criteria design problem with posterior articulation of preferences. An efficient scheme for the configuration of a service federating inter-cloud application is also presented. The experimental results prove the feasibility of our new scheme.

In large-scale computational Grids, discovery of heterogeneous resources as a working group is crucial to achieving scalable performance. This paper presents a resource management scheme including a hierarchical cycloid overlay architecture, resource clustering and discovery algorithms for wide-area distributed Grid systems. We establish program/data locality by clustering resources based on their physical proximity and functional matching with user applications. We further develop dynamism-resilient resource management algorithm, cluster-token forwarding algorithm, and deadline-driven resource management algorithms. The advantage of the proposed scheme lies in low overhead, fast and dynamism-resilient multiresource discovery. The paper presents the scheme, new performance metrics, and experimental simulation results. This scheme compares favorably with other resource discovery methods in static and dynamic Grid applications. In particular, it supports efficient resource clustering, reduces communications cost, and enhances resource discovery success rate in promoting large-scale distributed supercomputing applications.

QoS in a P2P video streaming system is evaluated in three stages: content generation, data delivery and video playback. We use jitter-free probability as the main performance metric to study Quality of Data delivery (QoD). A new model that incorporates both bandwidth and data availability of P2P network is proposed. Our model relies on a sharing factor that models data availability among all peers. We simulate on a minimalistic network to demonstrate how to apply the analytical model to design a P2P video streaming system with a very low jitter rate. Our simulation experimental results reveal that the lower bound on jitter-free probability is indeed effective to reflect the QoD of the entire system. Our model captures the impact of many design choices, including upload bandwidth limit, peer selection strategies, and video stream chunking schemes.

Elastic compute clouds are best represented by the virtual clusters in Amazon EC2 or in IBM RC2. This paper proposes a simulation based approach to scheduling scientific workflows onto elastic clouds. Scheduling multitask workflows in virtual clusters is a NP-hard problem. Excessive simulations in months of time may be needed to produce the optimal schedule using Monte Carlo simulations. To reduce this scheduling overhead is necessary in real-time cloud computing. We present a new workflow scheduling method based on iterative ordinal optimization (IOO). This new method outperforms the Monte Carlo and Blind-Pick methods to yield higher performance against rapid workflow variations. For example, to execute 20,000 tasks on 128 virtual machines for gravitational wave analysis, an ordinal optimized schedule can be generated in a few minutes, which is O(103)~O(104) faster than using Monte Carlo simulations. The ordinal optimized schedule results in higher throughput with lower memory demand. The cloud experimental results being reported verified our theoretical findings on the relative performance of three workflow scheduling methods studied in this paper.

Massive data dissemination is often disrupted by frequent join and departure or failure of client nodes in a peer-to-peer (P2P) network. We propose a new churn-resilient protocol (CRP) to assure alternating path and data proximity to accelerate the data dissemination process under network churn. The CRP enables the construction of proximity-aware P2P content delivery systems. We present new data dissemination algorithms using this proximity-aware overlay design. We simulated P2P networks up to 20,000 nodes to validate the claimed advantages. Specifically, we make four technical contributions: 1). The CRP scheme promotes proximity awareness, dynamic load balancing, and resilience to node failures and network anomalies. 2). The proximity-aware overlay network has a 28-50 percent speed gain in massive data dissemination, compared with the use of scope-flooding or epidemic tree schemes in unstructured P2P networks. 3). The CRP-enabled network requires only 1/3 of the control messages used in a large CAM-Chord network. 4) Even with 40 percent of node failures, the CRP network guarantees atomic broadcast of all data items. These results clearly demonstrate the scalability and robustness of CRP networks under churn conditions. The scheme appeals especially to web-scale applications in digital content delivery, network worm containment, and consumer relationship management over hundreds of datacenters in cloud computing services.

Predicting grid performance is a complex task because heterogeneous resource nodes are involved in a distributed environment. Long execution workload on a grid is even harder to predict due to heavy load fluctuations. In this paper, we use Kalman filter to minimize the prediction errors. We apply Savitzky-Golay filter to train a sequence of confidence windows. The purpose is to smooth the prediction process from being disturbed by load fluctuations. We present a new adaptive hybrid method (AHModel) for load prediction guided by trained confidence windows. We test the effectiveness of this new prediction scheme with real-life workload traces on the AuverGrid and Grid5000 in France. Both theoretical and experimental results are reported in this paper. As the lookahead span increases from 10 to 50 steps (5 minutes per step), the AHModel predicts the grid workload with a mean-square error (MSE) of 0.04-0.73 percent, compared with 2.54-30.2 percent in using the static point value autoregression (AR) prediction method. The significant gain in prediction accuracy makes the new model very attractive to predict Grid performance. The model was proved especially effective to predict large workload that demands very long execution time, such as exceeding 4 hours on the Grid5000 over 5,000 processors. With minor changes of some system parameters, the AHModel can apply to other computational grids as well. At the end, we discuss extended research issues and tool development for Grid performance prediction.

Internet clouds work as service factories built around web-scale datacenters. The elastic cloud resources and huge datasets processed are subject to security breaches, privacy abuses, and copyright violations. Provisioned cloud resources on-demand are especially vulnerable to cyber attacks. The cloud platforms built by Google, IBM, and Amazon all reveal this weaknesses. We propose a new approach to integrating virtual clusters, security-reinforced datacenters, and trusted data accesses guided by reputation systems. A hierarchy of P2P reputation systems is suggested to protect clouds and datacenters at the site level and to safeguard the data objects at the file-access level. Different security countermeasures are suggested to protect cloud service models: IaaS, PaaS, and SaaS, currently implemented by Amazon, IBM, and Google, respectively.

Peer-to-peer (P2P) networks are vulnerable from malicious attacks by anonymous users. By populating unprotected peers with poisoned file indices, the attacker can launch a poisoning DDoS (distributed denial-of-service) attacks on any host in the network. We solve this security problem with identity-based signatures contained in file indexes to establish peer accountability. We prove that index accountability can effectively block index-poisoning DDoS attacks in any open P2P environment. A new Accountable Indexing Protocol (AIP) is proposed to enforce peer accountability. This protocol is applicable to all P2P file-sharing networks, either structured or unstructured. The system allows gradual transition of peers to become AIP-enabled. We develop an analytical model to characterize the poison propagation patterns. The poisoning model is validated by simulated AIP experiments on large-scale P2P networks over one million of peer nodes.

Provides an abstract of the keynote presentation and a brief professional biography of the presenter. The complete presentation was not made available for publication as part of the conference proceedings.

In large-scale computational or P2P grids, discovery of heterogeneous resources as a working group is crucial to achieving scalable performance. This paper presents a hierarchical cycloid overlay (HCO) architecture with resource clustering and discovery algorithms for efficient and robust resource discovery in wide-area distributed grid systems. We establish program/data locality by clustering resources based on their physical proximity and functional matching with user applications. We further develop randomized probing and cluster-token forwarding algorithms. The novelty of the HCO scheme lies in low overhead, fast speed and dynamism resilience in multi-resource discovery. The paper presents the HCO framework, new performance metrics, and simulation experimental results. This HCO scheme compares favorably with other resource management methods in static and dynamic grid applications. In particular, it supports efficient resource clustering, reduces communications cost, and enhances resource discovery success rate in promoting large-scale distributed supercomputing applications.

In Peer-to-peer (P2P) IPTV networks, jitter rate is one of the most important metrics for Quality of Service. In this paper, we develop a new approach to estimate jitter rate during playback. Unlike traditional approaches that focus on the download speed, our method relies on the distribution of peer download latencies. We demonstrated how to apply the proposed methodologies in a real-life environment. We report simulation results over a P2P IPTV network with 5 seeds and 2,000 clients. Experimental results not only validated the theoretical projections, but also show that our model captures impacts of many design factors. It is thus suggested to use the proposed method as a guiding tool to design P2P IPTV networks with low jitter rate.

Collusive piracy is the main source of intellectual property violations within the boundary of a P2P network. Paid clients (colluders) may illegally share copyrighted content files with unpaid clients (pirates). Such online piracy has hindered the use of open P2P networks for commercial content delivery. We propose a proactive content poisoning scheme to stop colluders and pirates from alleged copyright infringements in P2P file sharing. The basic idea is to detect pirates timely with identity-based signatures and time-stamped tokens. The scheme stops collusive piracy without hurting legitimate P2P clients by targeting poisoning on detected violators, exclusively. We developed a new peer authorization protocol (PAP) to distinguish pirates from legitimate clients. Detected pirates will receive poisoned chunks in their repeated attempts. Pirates are thus severely penalized with no chance to download successfully in tolerable time. Based on simulation results, we find 99.9 percent prevention rate in Gnutella, KaZaA, and Freenet. We achieved 85-98 percent prevention rate on eMule, eDonkey, Morpheus, etc. The scheme is shown less effective in protecting some poison-resilient networks like BitTorrent and Azureus. Our work opens up the low-cost P2P technology for copyrighted content delivery. The advantage lies mainly in minimum delivery cost, higher content availability, and copyright compliance in exploring P2P network resources.

Credential chains are needed in trusted peer-to-peer (P2P) applications, where trust delegation must be established between each pair of peers at specific role level. Role-based trust is refined from the coarse-grained trust model used in most P2P reputation systems. This paper offers a novel heuristic-weighting approach to selecting the most likely path to construct a role-based trust chain. We apply history-sensitive heuristics to measure the path complexity and assess the chaining efficiency. We discover successive edges of a trust chain, adaptively, to match with the demands from various P2P applications. New heuristic chaining algorithms are developed for backward, forward, and bi-directional discovery of trust chains. Our heuristic chain discovery scheme shortens the search time, reduces the memory requirement, and enhances the chaining accuracy in scalable P2P networks. Consider a trust graph over N credentials and M distinct role nodes. Our heuristic trust-chain discovery algorithms require O(N2logN) search time and O(M) memory space, if the secondary heuristics are generated off-line in advance. These are improved from O(N3) search time and O(NM) space required in non-heuristic discovery algorithms by Li, Winsborough, and Mitchell (2003). Our analytical results are verified by extensive simulation experiments over typical classes of role-based trust graphs.

In peer-to-peer (P2P) networks, reputation aggregation and ranking are the most time-consuming and space-demanding operations. This paper proposes a new gossip protocol for fast score aggregation. We developed a Bloom filter architecture for efficient score ranking. These techniques do not require any secure hashing or fast lookup mechanism, thus are applicable to both unstructured and structured P2P networks. We report the design principles and performance results of a simulated GossipTrust reputation system. Randomized gossiping with effective use of power nodes enables light-weight aggregation and fast dissemination of global scores in O(log2n) time steps, where n is the P2P network size. The Gossip-based protocol is designed to tolerate dynamic peer joining and departure, as well as to avoid possible peer collusions. The scheme has a considerably low gossiping message overhead, i.e. O(n log2n) messages for n nodes. Bloom filters demand at most 512 KB memory per node for a 10,000-node network. We evaluate the performance of GossipTrust with distributed P2P file-sharing and parameter-sweeping applications. The simulation results demonstrate that GossipTrust has small aggregation time, low memory demand, and high ranking accuracy. These results suggest promising advantages of using the GossipTrust system for trusted P2P applications.

The RoQ (reduction-of-quality) attacks are low- rate DDoS attacks that degrade the QoS to end systems stealthily but not to deny the services completely. These attacks are more difficult to detect than the flooding DDoS attacks. This paper explores the energy distributions of Internet traffic flows in frequency domain. Normal TCP traffic flows present periodicity because of protocol behavior. Our results reveal that normal TCP flows can be segregated from malicious flows according to energy distribution properties. We discover the spectral shifting of attack flows from that of normal flows. Combining flow-level spectral analysis with sequential hypothesis testing, we propose a novel defense scheme against RoQ attacks. Our detection and filtering scheme can effectively rescue 99% legitimate TCP flows under the RoQ attacks.

Scalable resource monitoring and discovery are essential to the planet-scale infrastructures such as grids and PlanetLab. This paper proposes a scalable grid monitoring architecture that builds distributed aggregation trees (DAT) on a structured P2P network like Chord. By leveraging Chord topology and routing mechanisms, the DAT trees are implicitly constructed from native Chord routing paths without membership maintenance. To balance the DAT trees, we propose a balanced routing algorithm on Chord that dynamically selects the parent of a node from its finger nodes by its distance to the root. This paper shows that this balanced routing algorithm enables the construction of almost completely balanced DATs, when nodes are evenly distributed in the Chord identifier space. We have evaluated the performance and scalability of a DAT prototype implementation with up to 8192 nodes. Our experimental results show that the balanced DAT scheme scales well to a large number of nodes and corresponding aggregation trees. Without maintaining explicit parent-child membership, it has very low overhead during node arrival and departure. We demonstrate that the DAT scheme performs well in grid resource monitoring.

Summary form only given. Computational grids and peer-to-peer (P2P) are emerging as two of the most promising distributed computing technologies that may change the world in the next decade. In this talk, Dr. Hwang presents recent advances in network security technologies, cyber trust systems, and integrated solutions for trusted computing over the Internet. The talk covers the integration of Web services with P2P grid computing, new cybertrust models, Internet worm containment, P2P reputation systems, and hybrid defense systems to protect distributed resources from network worms, DDoS attacks or peer intrusions or collusions. Research findings and benchmark results from the USC GridSec project might be reported for automated trust management to facilitate security binding and defense against worms and DDoS attacks in grids, P2P systems, and Web services. The author assesses frontier research topics on fast reputation aggregation for trusted P2P file sharing, security-aware grid job scheduling, game-theoretic modeling of non-cooperative grids, new performance metrics, and DETER experiments for cybertrust development. The fortified grids, P2P systems, and Internet resources can benefit many security-sensitive applications in digital government, e-commerce, distance learning, distributed supercomputing, etc.

Peer-to-peer (P2P) reputation systems are needed to evaluate the trustworthiness of participating peers and to combat selfish and malicious peer behaviors. The reputation system collects locally generated peer feedbacks and aggregates them to yield global reputation scores. Development of decentralized reputation system is in great demand for unstructured P2P networks since most P2P applications on the Internet are unstructured. In the absence of fast hashing and searching mechanisms, how to perform efficient reputation aggregation is a major challenge on unstructured P2P computing. We propose a novel reputation aggregation scheme called GossipTrust. This system computes global reputation scores of all nodes concurrently. By resorting to a gossip protocol and leveraging the power nodes, GossipTrust is adapted to peer dynamics and robust to disturbance by malicious peers. Simulation experiments demonstrate the system as scalable, accurate, robust and fault-tolerant. These results prove the claimed advantages in low aggregation overhead, storage efficiency, and scoring accuracy in unstructured P2P networks. With minor modifications, the system is also applicable to structured P2P systems with projected better performance.

Fast and accurate generation of worm signatures is essential to contain zero-day worms at the Internet scale. Recent work has shown that signature generation can be automated by analyzing the repetition of worm substrings (that is, fingerprints) and their address dispersion. However, at the early stage of a worm outbreak, individual edge networks are often short of enough worm exploits for generating accurate signatures. This paper presents both theoretical and experimental results on a collaborative worm signature generation system (WormShield) that employs distributed fingerprint filtering and aggregation over multiple edge networks. By analyzing real-life Internet traces, we discovered that fingerprints in background traffic exhibit a Zipf-like distribution. Due to this property, a distributed fingerprint filtering reduces the amount of aggregation traffic significantly. WormShield monitors utilize a new distributed aggregation tree (DAT) to compute global fingerprint statistics in a scalable and load-balanced fashion. We simulated a spectrum of scanning worms including CodeRed and Slammer by using realistic Internet configurations of about 100,000 edge networks. On average, 256 collaborative monitors generate the signature of CodeRedl-v2 135 times faster than using the same number of isolated monitors. In addition to speed gains, we observed less than 100 false signatures out of 18.7-Gbyte Internet traces, yielding a very low false-positive rate. Each monitor only generates about 0.6 kilobit per second of aggregation traffic, which is 0.003 percent of the 18 megabits per second link traffic sniffed. These results demonstrate that the WormShield system offers distinct advantages in speed gains, signature accuracy, and scalability for large-scale worm containment.

This paper reports the design principles and evaluation results of a new experimental hybrid intrusion detection system (HIDS). This hybrid system combines the advantages of low false-positive rate of signature-based intrusion detection system (IDS) and the ability of anomaly detection system (ADS) to detect novel unknown attacks. By mining anomalous traffic episodes from Internet connections, we build an ADS that detects anomalies beyond the capabilities of signature-based SNORT or Bro systems. A weighted signature generation scheme is developed to integrate ADS with SNORT by extracting signatures from anomalies detected. HIDS extracts signatures from the output of ADS and adds them into the SNORT signature database for fast and accurate intrusion detection. By testing our HIDS scheme over real-life Internet trace data mixed with 10 days of Massachusetts Institute of Technology/Lincoln Laboratory (MIT/LL) attack data set, our experimental results show a 60 percent detection rate of the HIDS, compared with 30 percent and 22 percent in using the SNORT and Bro systems, respectively. This sharp increase in detection rate is obtained with less than 3 percent false alarms. The signatures generated by ADS upgrade the SNORT performance by 33 percent. The HIDS approach proves the vitality of detecting intrusions and anomalies, simultaneously, by automated data mining and signature generation over Internet connection episodes

This paper presents a new distributed approach to detecting DDoS (distributed denial of services) flooding attacks at the traffic-flow level The new defense system is suitable for efficient implementation over the core networks operated byInternet service providers(ISPs). At the early stage of a DDoS attack, some traffic fluctuations are detectable at Internet routers or at the gateways of edge networks. We develop adistributed change-point detection(DCD) architecture using change aggregation trees (CAT). The idea is to detect abrupt traffic changes across multiple network domains at the earliest time. Early detection of DDoS attacks minimizes the floe cling damages to the victim systems serviced by the provider. The system is built over attack-transit routers, which work together cooperatively. Each ISP domain has a CAT server to aggregate the flooding alerts reported by the routers. CAT domain servers collaborate among themselves to make the final decision. To resolve policy conflicts at different ISP domains, anew secureinfrastructure protocol(SIP) is developed to establish mutual trust or consensus. We simulated the DCD system up to 16 network domains on the Cyber Defense Technology Experimental Research (DETER) testbed, a 220-node PC cluster for Internet emulation experiments at the University of Southern California (USC) Information Science Institute. Experimental results show that four network domains are sufficient to yield a 98 percent detection accuracy with only 1 percent false-positive alarms. Based on a 2006 Internet report onautonomous system(AS) domain distribution, we prove that this DDoS defense system can scale well to cover 84 AS domains. This security coverage is wide enough to safeguard most ISP core networks from real-life DDoS flooding attacks.

Selfish behaviors of individual machines in a grid can potentially damage the performance of the system as a whole. However, scrutinizing the grid by taking into account the noncooperativeness of machines is a largely unexplored research problem. In this paper, we first present a new hierarchical game-theoretic model of the grid that matches well with the physical administrative structure in real-life situations. We then focus on the impact of selfishness in intrasite job execution mechanisms. Based on our novel utility functions, we analytically derive the Nash equilibrium and optimal strategies for the general case. To study the effects of different strategies, we have also performed extensive simulations by using a well-known practical scheduling algorithm over the NAS (numerical aerodynamic simulation) and the PSA (parameter sweep application) workloads. We have studied the overall job execution performance of the grid system under a wide range of parameters. Specifically, we find that the optimal selfish strategy significantly outperforms the Nash selfish strategy. Our performance evaluation results can serve as a valuable reference for designing appropriate strategies in a practical grid

Peer-to-Peer (P2P) reputation systems are essential to evaluate the trustworthiness of participating peers and to combat the selfish, dishonest, and malicious peer behaviors. The system collects locally-generated peer feedbacks and aggregates them to yield the global reputation scores. Surprisingly, most previous work ignored the distribution of peer feedbacks. We use a trust overlay network (TON) to model the trust relationships among peers. After examining the eBay transaction trace of over 10,000 users, we discover a power-law distribution in user feedbacks. Our mathematical analysis justifies that power-law distribution is applicable to any dynamically growing P2P systems, either structured or unstructured. We develop a robust and scalable P2P reputation system, PowerTrust, to leverage the power-law feedback characteristics. The PowerTrust system dynamically selects small number of power nodes that are most reputable using a distributed ranking mechanism. By using a look-ahead random walk strategy and leveraging the power nodes, PowerTrust significantly improves in global reputation accuracy and aggregation speed. PowerTrust is adaptable to dynamics in peer joining and leaving and robust to disturbance by malicious peers. Through P2P network simulation experiments, we find significant performance gains in using PowerTrust. This power-law guided reputation system design proves to achieve high query success rate in P2P file-sharing applications. The system also reduces the total job makespan and failure rate in large-scale, parameter-sweeping P2P Grid applications.

This paper presents a new approach to trusted grid computing in a peer-to-peer (P2P) setting. Trust and security are essential to establish lasting working relationships among the peers. A P2P reputation system collects peer trust scores and aggregates them to yield a global reputation. We use a new trust overlay network (TON) to model the trust relationships among the peers. After analyzing the eBay transaction trace data, we discover a power-law distribution in user feedbacks. We develop a new reputation system, PowerTrust, to leverage power-law feedback characteristics. The PowerTrust system is built with locality-preserving hash functions and a lookahead random walk strategy. Dynamic system reconfiguration is enabled by the use of power nodes with well-established reputations. Through P2P simulation experiments on distributed file sharing and grid parameter-sweeping applications (PSA), we demonstrate the PowerTrust advantages in fast reputation convergence and accurate ranking of peer reputations. We report performance results with enhanced P2P query success rate, shortened job makespan, and increased job success rate in scalable P2P grid applications.

In scheduling a large number of user jobs for parallel execution on an open-resource grid system, the jobs are subject to system failures or delays caused by infected hardware, software vulnerability, and distrusted security policy. This paper models the risk and insecure conditions in grid job scheduling. Three risk-resilient strategies, preemptive, replication, and delay-tolerant, are developed to provide security assurance. We propose six risk-resilient scheduling algorithms to assure secure grid job execution under different risky conditions. We report the simulated grid performances of these new grid job scheduling algorithms under the NAS and PSA workloads. The relative performance is measured by the total job makespan, grid resource utilization, job failure rate, slowdown ratio, replication overhead, etc. In addition to extending from known scheduling heuristics, we developed a new space-time genetic algorithm (STGA) based on faster searching and protected chromosome formation. Our simulation results suggest that, in a wide-area grid environment, it is more resilient for the global job scheduler to tolerate some job delays instead of resorting to preemption or replication or taking a risk on unreliable resources allocated. We find that delay-tolerant min-min and STGA job scheduling have 13-23 percent higher performance than using risky or preemptive or replicated algorithms. The resource overheads for replicated job scheduling are kept at a low 15 percent. The delayed job execution is optimized with a delay factor, which is 20 percent of the total makespan. A Kiviat graph is proposed for demonstrating the quality of grid computing services. These risk-resilient job scheduling schemes can upgrade grid performance significantly at only a moderate increase in extra resources or scheduling delays in a risky grid computing environment.

Selfish behaviors of individual machines in a grid can potentially damage the performance of the system as a whole. However, scrutinizing the grid by taking into account the non-cooperativeness of machines is a largely unexplored research problem. In this paper, we first present a new hierarchical game-theoretic model of the grid that matches well with the physical administrative structure in real-life situations. We then focus on the impact of selfishness in intra-site job execution mechanisms. Based on our novel utility functions, we analytically derive the Nash equilibrium and optimal strategies for the general case. To study the effects of different strategies, we have also performed extensive simulations by using a well-known practical scheduling algorithm over the NAS (Numerical Aerodynamic Simulation) workload. We have studied overall job execution performance of the grid system under a wide range of parameters. Specifically, we find that the optimal selfish strategy significantly outperforms the Nash selfish strategy. Our performance evaluation results can serve as valuable reference for designing appropriate strategies in a practical grid.

The shrew distributed denial of service (DDoS) attacks are periodic, bursty, and stealthy in nature. They are also known as reduction of quality (RoQ) attacks. Such attacks could be even more detrimental than the widely known flooding DDoS attacks because they damage the victim servers for a long time without being noticed, thereby denying new visitors to the victim servers, which are mostly e-commerce sites. Thus, in order to minimize the huge monetary losses, there is a pressing need to effectively detect such attacks in real-time. Unfortunately, effective detection of shrew attacks remains an open problem. In this paper, we meet this challenge by proposing a new signal processing approach to identifying and detecting the attacks by examining the frequency-domain characteristics of incoming traffic flows to a server. A major strength of our proposed technique is that its detection time is less than a few seconds. Furthermore, the technique entails simple software or hardware implementations, making it easily deployable in a real-life network environment.

This work introduces a new Internet trace technique for generating frequent episode rules to characterize Internet traffic events. These episode rules are used to distinguish anomalous sequences of TCP, UDP, or ICMP connections from normal traffic episodes. Fundamental pruning techniques are introduced to reduce the rule search space by 70%. The new detection scheme was tested over real-life Internet trace data at USC. Our anomaly detection scheme results in a success rate of 47% for DoS, R2L, and port-scanning attacks. These results demonstrate an average of 51% improvement over the use of association rules. We experienced 20 or fewer false alarms over 200 network attacks in 9 days of tracing experiments. This anomaly detection scheme can be used jointly with signature-based IDS to achieve even higher detection efficiency.

This paper presents a new distributed disk-array architecture for achieving high I/O performance in scalable cluster computing. In a serverless cluster of computers, all distributed local disks can be integrated as a distributed-software redundant array of independent disks (ds-RAID) with a single I/O space. We report the new RAID-x design and its benchmark performance results. The advantage of RAID-x comes mainly from its orthogonal striping and mirroring (OSM) architecture. The bandwidth is enhanced with distributed striping across local and remote disks, while the reliability comes from orthogonal mirroring on local disks at the background. Our RAID-x design is experimentally compared with the RAID-5, RAID-10, and chained-declustering RAID through benchmarking on a research Linux cluster at USC. Andrew and Bonnie benchmark results are reported on all four disk-array architectures. Cooperative disk drivers and Linux extensions are developed to enable not only the single I/O space, but also the shared virtual memory and global file hierarchy. We reveal the effects of traffic rate and stripe unit size on I/O performance. Through scalability and overhead analysis, we find the strength of RAID-x in three areas: 1) improved aggregate I/O bandwidth especially for parallel writes, 2) orthogonal mirroring with low software overhead, and 3) enhanced scalability in cluster I/O processing. Architectural strengths and weakness of all four ds-RAID architectures are evaluated comparatively. The optimal choice among them depends on parallel read/write performance desired, the level of fault tolerance required, and the cost-effectiveness in specific I/O processing applications.

This paper reports the design experiences and research findings of a new distributed security architecture for protecting exposed Intranets or clusters of computers from malicious attacks. We present a new approach of building micro-firewalls on network hosts to enable distributed intrusion detection with dynamic policy change, as the threat pattern changes. This distributed security can effectively counteract attacks from intruders or insiders. Three policy-update mechanisms are evaluated for achieving dynamic security. Mobile agents are shown most scalable and robust for policy update, but prone to attacks by other agents or hosts. The CORBA has the best speed performance with lower overhead The Java-based RMI demonstrates the highest security based on the sandbox model. The optimal choice depends on the tradeoffs among operating speed, Intranet scalability, host robustness, and the security level demanded by specific network applications.

This paper presents the design and performance of a new parallel graphics renderer for 3D images. This renderer is based on an adaptive supersampling approach that works for time/space-efficient execution on two classes of parallel computers. Our rendering scheme takes subpixel supersamples only along polygon edges. This leads to a significant reduction in rendering time and in buffer memory requirements. Furthermore, we offer a balanced rasterization of all transformed polygons. Experimental results prove these advantages on both a shared-memory SGI multiprocessor server and a Unix cluster of Sun workstations. We reveal performance effects of the new rendering scheme on subpixel resolution, polygon number, scene complexity, and memory requirements. The balanced parallel renderer demonstrates scalable performance with respect to increase in graphic complexity and in machine size. Our parallel renderer outperforms Crow's scheme in benchmark experiments performed. The improvements are made in three fronts: (1) reduction in rendering time, (2) higher efficiency with balanced workload,: and (3) adaptive to available buffer memory size. The balanced renderer can be more cost-effectively embedded within many 3D graphics algorithms, such as those for edge smoothing and 3D visualization. Our parallel renderer is MPI-coded, offering high portability and cross-platform performance. These advantages can greatly improve the QoS in 3D imaging and in real-time interactive graphics.

A new RAID-x (redundant array of inexpensive disks at level x) architecture is presented for distributed I/O processing on a serverless cluster of computers. The RAID-x architecture is based on a new concept of orthogonal striping and mirroring (OSM) across all distributed disks in the cluster. The primary advantages of this OSM approach lie in: (1) a significant improvement in parallel I/O bandwidth; (2) hiding disk mirroring overhead in the background; and (3) greatly enhanced scalability and reliability in cluster computing applications. All claimed advantages are substantiated with benchmark performance results on the Trojans cluster built at USC in 1999. The authors discuss the issues of scalable I/O performance, enhanced system reliability, and striped checkpointing on distributed RAID-x in a serverless cluster environment.

Support of single system image (SSI) services is the main approach that enables better utilization of PC/workstation clusters. Some SSI services can be easily built with the support of other low-level, elementary, SSI services. In this paper, we describe a single I/O space architecture for achieving a SSI at the I/O subsystem level. Furthermore, we demonstrate how the single I/O space can facilitate the development of other key SSI services. Typical SSI services which can benefit from the single I/O space include single file hierarchy, single memory space, checkpointing systems and single process space with process migration facilities. Benchmark performance results show that our design achieves both performance and storage size scalabilities that are essential to building I/O-intensive clusters.

To access a RAID (redundant arrays of inexpensive disks), the disk stripe size greatly affects the performance of the disk array. In this article, we present a performance model to analyze the effects of striping with different stripe sizes in a RAID. The model can be applied to optimize the stripe size. Compared with previous approaches, our model is simpler to apply and more accurately reveals the real performance. Both system designers and users can apply the model to support parallel I/O events. Copyright © 2000 John Wiley & Sons, Ltd.

Presently, massively parallel processors (MPPs) are available only in a few commercial models. A sequence of three ASCI Teraflops MPPs has appeared before the new millenium. This paper evaluates six MPP systems through STAP benchmark experiments. The STAP is a radar signal processing benchmark which exploits regularly structured SPMD data parallelism. We reveal the resource scaling effects on MPP performance along orthogonal dimensions of machine size, processor speed, memory capacity messaging latency, and network bandwidth. We show how to achieve balanced resources scaling against enlarged workload (problem size). Among three commercial MPPs, the IBM SP2 shows the highest speed and efficiency, attributed to its well-designed network with middleware support for single system image. The Cray T3D demonstrates a high network bandwidth with a good NUMA memory hierarchy. The Intel Paragon trails far behind due to slow processors used and excessive latency experienced in passing messages. Our analysis projects the lowest STAP speed on the ASCI Red, compared with the projected speed of two ASCI Blue machines. This is attributed to slow processors used in ASCI Red and the mismatch between its hardware and software. The Blue Pacific shows the highest potential to deliver scalable performance up to thousands of nodes. The Blue Mountain is designed to have the highest network bandwidth. Our results suggest a limit on the scalability of the distributed shared-memory (DSM) architecture adopted in Blue Mountain. The scaling model offers a quantitative method to match resource scaling with problem scaling to yield a truly scalable performance. The model helps MPP designers optimize the processors, memory, network, and I/O subsystems of an MPP. For MPP users, the scaling results can be applied to partition a large workload for SPMD execution or to minimize the software overhead in collective communication or remote memory update operations. Finally, our scaling model is assessed to evaluate MPPs with benchmarks other than STAP.

We evaluate the architectural support of collective communication operations on the IBM SP2, Cray T3D, and Intel Paragon. The MPI performance data are obtained from the STAP benchmark experiments jointly performed at the USC and HKU. The T3D demonstrated clearly the best timing performance in almost all collective operations. This is attributed to the special hardware built in the T3D for fast messaging and block data transfer. With hardwired barriers, the T3D performs the barrier synchronization in 3 /spl mu/s at least 30 times faster than the SP2 or Paragon. The startup latency of collective operations increases either linearly or logarithmically in three multicomputers. For short messages, the SP2 outperforms the Paragon in the barrier, total exchange, scatter, and gather operations. Various collective operations with 64 KBytes per message over 64 nodes of the three machines can be completed in the time range (5.12 ms, 675 ms). The Paragon outperforms the SP2 in almost all collective operations with long messages. We have derived closed-form expressions to quantify the collective messaging times and aggregated bandwidth on all three machines. For total exchange with 64 nodes, the T3D, Paragon, and SP2 achieved an aggregated bandwidth of 1.745, 0.879, and 0.818 GBytes/s, respectively. These findings are useful to those who wish to predict the MPP performance or to optimize parallel applications by trade-offs between divided computation and collective communication.

Summary form only given, as follows. With the increasing speed of computers and communication linlts, and the successful convergence of both fields, computers connected by high speed links now represent an enormously large distributed computing system. However, current information distributed system architectures are too rigid to cope with heterogeneity, inaccuracy and inflexibility of the real world requirements. In order to overcome such limitations, in this talk, we present Post Modem Distributed System based on Flexible Network using the concept of Flexible Computing proposed by the authors. We first give the outline of the Flexible Computing and the basic architecture of Flexible Network based on multi-agent systems. Then the characteristics of Modem Distributed Systems based on Flexible Network will be discussed. As application examples, we will show a virtual office and flexible video conference system.

This paper evaluates the IBM SP2 architecture, the AIX parallel programming environment, and the IBM message-passing library (MPL) through STAP (Space-Time Adaptive Processing) benchmark experiments. Only coarse-grain parallelism was exploited on the SP2 due to its high communication overhead. A new parallelization scheme is developed for programming message passing multicomputers. Parallel STAP benchmark structures are illustrated with domain decomposition, efficient mapping of partitioned programs, and optimization of collective communication operations. We measure the SP2 performance in terms of execution time, Gflop/s rate, speedup over a single SP2 node, and overall system utilization. With 256 nodes, the Maul SP2 demonstrated the best performance of 23 Gflop/s in executing the High-Order Post-Doppler program, corresponding to a 34% system utilization. We have conducted a scalability analysis to reveal the performance growth rate as a function of machine size and STAP problem size. Important lessons learned from these parallel processing benchmark experiments are discussed in the context of real-time, adaptive, radar signal processing on massively parallel processors (MPP).

Stochastic timed Petri nets are developed to evaluate the relative performance of distributed shared memory models for scalable multiprocessors, using multithreaded processors as building blocks. Four shared memory models are evaluated: the sequential consistency (SC) model by Lamport (1979), the weak consistency (WC) model by Dubois et al. (1986), the processor consistency (PC) model by Goodman (1989), and the release consistency (RC) model by Gharachorloo et al. (1990). We assumed a scalable network with a sufficient bandwidth to absorb the increased traffic from multithreading, coherent caches, and memory event reordering. The embedded Markov chains are solved to reveal the performance attributes. Under saturated conditions, we find that multithreading contributes more than 50% of the performance improvement, while the improvement from memory consistency models varies between 20% to 40% of the total performance gain. Petri net models are effective to predict the performance of processors with a larger number of contexts than that can be simulated in previous benchmark studies. The accuracy of these memory performance models was validated with the simulation results from Stanford University. Our analytical results reveal the lowest performance of the SC model amongst four memory consistency models. The PC model requires to use larger write buffers, while the WC and RC models require smaller write buffers. The PC model may perform even lower than the SC model, if a small buffer was used. The performance of the WC model depends heavily on the synchronization rate in user code. For a low synchronization rate, the WC model performs as well as the RC model. With sufficient multithreading and network bandwidth, the RC model shows the best performance among the four models. Furthermore, we discovered that cache interferences cause very little performance degradation in all relaxed memory consistency models; as long as the network is contention-free even when multithreading has saturated the system.>

Conventional multiprocessors mostly use centralized, memory-based barriers to synchronize concurrent processes created in multiple processors. These centralized barriers often become the bottleneck or hot spots in the shared memory. In this paper, we overcome the difficulty by presenting a distributed and hardwired barrier architecture, that is hierarchically constructed for fast synchronization in cluster-structured multiprocessors. The hierarchical architecture enables the scalability of cluster-structured multiprocessors. A special set of synchronization primitives is developed for explicit use of distributed barriers dynamically. To show the application of the hardwired barriers, we demonstrate how to synchronize Doall and Doacross loops using a limited number of hardwired barriers. Timing analysis shows an O(10/sup 2/) to O(10/sup 5/) reduction in synchronization overhead, compared with the use of software-controlled barriers implemented in a shared memory. The hardwired architecture is effective in implementing any partially ordered set of barriers or fuzzy barriers with extended synchronization regions. The versatility, scalability, programmability, and low overhead make the distributed barrier architecture attractive in constructing fine-grain, massively parallel MIMD systems using multiprocessor clusters with distributed shared memory.>

In order to execute a parallel PDE (partial differential equation) solver on a shared-memory multiprocessor, we have to avoid memory conflicts in accessing multidimensional data grids. A new multicoloring technique is proposed for speeding sparse matrix operations. The new technique enables parallel access of grid-structured data elements in the shared memory without causing conflicts. The coloring scheme is formulated as an algebraic mapping which can be easily implemented with low overhead on commercial multiprocessors. The proposed multicoloring scheme bas been tested on an Alliant FX/80 multiprocessor for solving 2D and 3D problems using the CGNR method. Compared to the results reported by Saad (1989) on an identical Alliant system, our results show a factor of 30 times higher performance in Mflops. Multicoloring transforms sparse matrices into ones with a diagonal diagonal block (DDB) structure, enabling parallel LU decomposition in solving PDE problems. The multicoloring technique can also be extended to solve other scientific problems characterized by sparse matrices.

Stochastic timed Petri nets are developed to evaluate the relative performance of distributed shared memory models for scalable multithreaded multiprocessors. The shared memory models evaluated include the Sequential Consistency (SC), the Weak Consistency (WC), the Processor Consistency (PC) and the Release Consistency (RC) models. Under saturated conditions, we found that multithreading contributes more than 50% of the performance improvement, while the improvement from memory consistency models varies between 20% to 40% of the total performance gain. Our analytical results reveal the lowest performance of the SC model. The PC model requires to use larger write buffers and may perform even lower than the SC model if a small buffer was used. The performance of the WC model depends heavily on the synchronization rate in user code. For a low synchronization rate, the WC model performs as well as the RC model. With sufficient multithreading and network bandwidth, the RC model shows the best performance among the four models.

A new multicoloring technique is proposed for parallel sparse matrix-vector multiplication, which dominates the computing cost of iterative PDE (partial differential equation) solvers. The new technique enables parallel solution of grid-structured nonsymmetric PDE problems on shared-memory multiprocessors through resolving memory access conflicts by multiple processors. The coloring scheme is formulated as an algebraic mapping which can be implemented with low overhead.

The authors describe a neural network approach for combining processing of multiple early vision modules. Energy functions for coupling the computation of intensity contours, optical flow, and stereo disparity are defined. Hopfield neural networks are used for function minimization with deterministic annealing to avoid spurious local minima. Vision integration schemes are developed by extending the work of T.A. Poggio et al. (1988) to include cooperative interactions between different vision modules and the Hebbian adaptation of vision module coupling on a massively parallel computer consisting of 4096 processing elements operated in a single-instruction-multiple-data mode. Simple experiments assess the performance of various integration approaches. The resulting algorithms facilitate fast, robust image segmentation.>

The authors present the concept of vector register windows (VRWs) geared towards large scale matrix computation and image processing applications. The VRWs consist of multiple windows for vector registers providing parallel access and manipulation of large matrix data in the orthogonal multiprocessor (OMP). The number of windows and the number of registers in a window are dynamically reconfigurable over a range of values to match with the application problem size. An associated index manipulator provides programmable and on-the-fly data manipulation. The index manipulation feature is shown to be quite powerful for carrying out complex data manipulation functions like row (column) shift, row (column) exchange, matrix rotation, etc. Some matrix algorithms, efficiently utilizing the VRWs, are illustrated.>

This paper presents the architectural design and RISC based implementation of a prototype supercomputer, namely the Orthogonal MultiProcessor (OMP). The OMP system is constructed with 16 Intel 1860 RISC microprocessors and 256 parallel memory modules, which are 2-D interleaved and orthogonally accessed using custom-designed spanning buses. The architectural design has been validated by a CSIM-based multiprocessor simulator. The design choices are based on worst-case delay analysis and simulation validation. The current OMP prototype chooses a 2-dimensional memory architecture, mainly for image processing, computer vision, and neural network simulation applications. The 16-processor OMP prototype is targeted to achieve a peak performance of 400 RISC integer MIPS or a maximum of 640 Mflops. This paper presents the architectural design of the OMP prototype at system and PC board levels. We are presently entering the fabrication stage of all the PC boards. The system is expected to become operational in late 1991 and benchmarking results will be available in 1992. Only hardware design features are reported here. Software and simulation results are reported elsewhere.

The scheme is based on using easy-to-implement heuristics and a variable threshold in migrating processes among the multicomputer nodes. It uses a distributed control over all processor nodes as coordinated by a host processor. Four heuristic methods for process migration are presented, which are distinguished by choosing different policies for process migration and threshold update. A parallel simulator (PSIM) with distributed load balancers is developed on an iPSC/2 hypercube system. The load balancing scheme is evaluated to determine the effects of various system utilizations, load imbalances, communication and migration overheads, and multicomputer sizes. The relative merits of the four methods are revealed under various multicomputer conditions.>

New optical representations and symbolic substitution (SS) rules are presented for performing high-radix arithmetic in optics. A set of SS rules is proposed for high-radix optical arithmetic, which satisfies the arithmetic completeness property. Tradeoff parameters like representational efficiency, projected speedup, and estimated implementation cost are analyzed. The SS mechanism together with the signed-digit (SD) representation reinforces massive parallelism in optics. A digit-plane architecture, blending very well with the SS technique and SD representation, is considered for implementing high-radix arithmetic. An optical adder, exploiting massive parallelism, is proposed. The set of SS rules and their implementations on a digit-plane architecture provide the basis for achieving pipelining, systolization, and online arithmetic in future optical computers.>

An architecture called an orthogonal multiprocessor (OMP) is proposed. This OMP architecture has a simplified busing structure and partially shared memory and compares very favorably with fully shared-memory multiprocessors using crossbar switches, multiple buses, or multistage networks. The higher performance comes mainly from significantly increased memory bandwidth, fully exploited parallelism, reduced communication overhead, and lower hardware control complexities. Parallel algorithms being mapped include matrix arithmetic, linear system solver, FFT, array sorting, linear programming, and parallel PDE solutions. In most cases, linear speedup can be achieved on the OMP system. The OMP architecture provides linearly scalable performance and is well suited for building special-purpose scientific computers.>

A new language construct, called molecule, is described for the efficient implementation of algorithms on parallel computers. A molecule can be considered a procedure associated with a molecule type. Each molecule type characterizes a particular computation mode (sequential, pipelining, array processing, dataflow, multiprocessing, etc.). Basic concepts of molecule are introduced with a procedural language, called PAL. A concrete example is presented to illustrate layered software development using PAL on a multicomputer (the iPSC). It is concluded that high-level languages, augmented with the molecule construct, offer application flexibility, user friendliness, and efficiency in implementing parallel programs.>

The architectural requirements for efficiently simulating large neural networks on a multicomputer system with thousands of fine-grained processors and distributed memory are investigated. Models for characterizing the structure of a neural network and the function of individual cells are developed. These models provide guidelines for efficiently mapping the network onto multicomputer technologies such as the hypercube, hypernet, and torus. They are further used to estimate the amount of interprocessor communication bandwidth required, and the number of processors needed to meet a particular cost/performance goal. Design issues such as memory organization and the effect of VLSI technology are also considered.>

An architecture based on optical technology is presented for constructing parallel computers. The architecture uses optics for its ultrahigh speed, massive parallelism, and dense connectivity. The processing is based on a technique called 2-D symbolic substitution that can be implemented with very fast optical components. Two-dimensional symbolic substitution algorithms are developed for arithmetic/logic operations as well as for complex scientific computations such as matrix algebra and fast Fourier transforms (FFTs). The predicted performance of the system is compared with the performance of existing electronic array processors and is shown to be potentially superior. The bit-plane architecture is shown to be both feasible and economical based on state-of-the-art optical and electrooptical technologies.>

An efficient vector-processing technique is proposed; it is based on a novel concept of multipipeline networking, which is generalized from the techniques of pipeline chaining and systolization. The authors also present the design principles of pipeline nets and provide programming, compiling and run-time techniques for converting scientific programs into pipeline net implementations. Performance analysis of the pipeline net is provided with projected performance of various Livermore loops implemented with pipeline nets of various sizes.>

Fast evaluation of vector-valued elementary functions plays a vital role in many real-time applications. In this paper, we present a pipeline networking approach to designing a Chebyshev polynomial evaluator for the fast evaluation of elementary functions over a string of arguments. In particular, pipeline nets are employed to perform the preprocessing and postprocessing of various elementary functions to boost the overall system performance. Design tradeoffs are analyzed among representational accuracy, processing speed and hardware complexity.

This paper investigates advanced parallel processing techniques and innovative hardware/software architectures that can be applied to boost the performance of supercomputers. Critical issues on architectural choices, parallel languages, compiling techniques, resource management, concurrency control, programming environment, parallel algorithms, and performance enhancement methods are examined and the best answers are presented. We cover advanced processing techniques suitable for supercomputers, high-end mainframes, minisupers, and array processors. The coverage emphasizes vectorization, multitasking, multiprocessing, and distributed computing. In order to achieve these operation modes, parallel languages, smart compilers, synchronization mechanisms, load balancing methods, mapping parallel algorithms, operating system functions, application library, and multidiscipline interactions are investigated to ensure high performance. At the end, we assess the potentials of optical and neural technologies for developing future supercomputers.

A new class of modular networks is proposed for hierarchically constructing massively parallel computer systems for distributed supercomputing and AI applications. These networks are called hypernets. They are constructed incrementally with identical cubelets, treelets, or buslets that are well suited for VLSI implementation. Hypernets integrate positive features of both hypercubes and tree-based topologies, and maintain a constant node degree when the network size increases. This paper presents the principles of constructing hypernets and analyzes their architectural potentials in terms of message routing complexity, cost-effective support for global as well as localized communication, I/O capabilities, and fault tolerance. Several algorithms are mapped onto hypernets to illustrate their ability to support parallel processing in a hierarchically structured or data-dependent environment. The emulation of hypercube connections using less hardware is shown. The potential of hypernets for efficient support of connectionist models of computation is also explored.

This paper analyzes the potential performance of a high-level language (HLL) microprocessor architecture for special- purpose real-time applications. Our approach is based on mapping of HLL constructs into microcode, a concept called vertical migration. An analytical execution-time model of the reduced vertical-migration architecture is developed. It is applied to two different workload models: one corresponding to statement mixes, and the other showing some HLL kernel routines. Performance evaluation results are compared to different forms of the reduced vertical-migration architecture, and in various application domains. We underline in this paper the, basic relationships among microprocessor architecture, GaAs technology, and real-time applications.

In the above paper, an error was made in the Load Balancing Algorithm. A more clear recursive way to present this algorithm is to modify steps S3 to S5 as follows.

A dynamic network approach is proposed for designing multifunctional arithmetic processors to support complex, interval, vector, matrix, polynomial, and other compound arithmetic operations. This arithmetic-network approach is extended from the multipipleline chaining concept implemented in Cray Research supercomputers. The proposed design methodology offers a viable way of developing very powerful and flexible arithmetic multiprocessors for scientific supercomputing.

Vector-reduction arithmetic accepts vectors as inputs and produces scalars as outputs. This class of vector operation forms the basis of many scientific computations, such as inner product and finding the maximum among the vector components. Vector reduction on a pipeline processor demands a feedback connection around the pipeline. Since the output of such a pipeline depends on the previous output, improper control of the feedback input may destroy the benefit from pipelining. Two new vector-reduction techniques are proposed in this paper. In addition to saving reduction time and eliminating intermediate storage (as compared to Kuck's method and Kogge's method), the new methods will greatly simplify the machine-level programming effort needed to implement vector-reduction operations. An interleaved technique is introduced to reduce multiple vectors to corresponding scalars using the same arithmetic pipeline. The pipeline can be fully utilized by interleaving multiple vector-reduction processes. The proposed techniques can be applied to improve the performance of vector-arithmetic pipelines in scientific supercomputers.

In this correspondence we show how long division of polynomials can be performed in a pipelined fashion on a linear systolic array in linear time.

A loosely coupled multiprocessor system contains multiple processors which have their own local memories. To balance the load among multiple processors is of fundamental importance in enhancing the performance of such a multiple processor system. Probabilistic load balancing in a heterogeneous multiple processor system with many job classes is considered in this study. The load balancing scheme is formulated as a nonlinear programming problem with linear constraints. An optimal probabilistic load balancing algorithm is proposed to solve this nonlinear programming problem. The proposed load balancing method is proven globally optimum in the sense that it results in a minimum overall average job response time on a probabilistic basis.

Packet switched Multistage Interconnection Networks (MINs) have been mostly proposed to use unique connection path between any source and destination. We propose to add a few extra stages in an MIN to create multiple paths between any source and destination. Connection principles of Multipath MINs (MMINs) for packet switching are presented in this paper. Performance of such network is analyzed for possible use in multiprocessor systems and dataflow computers. For an MMIN with n nodes, the number of required stages is confined in the range [log2n+1, 2log2n-1]. Each stage consists of n/2 buffered 2-by-2 switching cells. In practice, one or two extra stages is sufficient beyond log2n stages required in a unique-path MIN. The delays of MMINs are shown much shorter than that of using unique-path MINs for packet switching. The improvement lies in significantly reduced packet wait delays in buffers, especially under heavy traffic conditions. The tradeoffs between reduced network delays and increased hardware cost are studied. Optimal design criteria and procedures are provided for developing MMINs with a fixed network size and stages.

Most packet switched multistage networks have been proposed to use a unique path between any source and destination. We propose to add a few extra stages to create multiple paths between any source and destination. Connection principles of such multipath networks for packet switching are presented. Performance of such networks is analyzed for possible use in multiprocessor systems or in data flow computers.

Vector reduction arithmetic accepts a vector as input and produces a scalar output. This class of vector operations forms the basis of many scientific computations. In a pipelined processor, a feedback loop is required to reduce vectors. Since the output of the pipeline depends on previous outputs, improper control of the feedback loop will destroy the benefit from pipelining. A generalized computing model is proposed to schedule the activities in a vector reduction pipeline. Two new vector reduction methods, symmetric and asymmetric, are proposed and analyzed for pipelined processing. These two methods compare favorably with the known recursive reduction method in achieving higher pipeline utilization and in eliminating large memory for intermediate results. An interleaving method is proposed to reduce multiple vectors to multiple scalars in a single arithmetic pipeline. The pipeline can be fully utilized by interleaved multiple vector processing.

The PUMPS architecture consists of P task processing units (TPU) which share a pool of special peripheral processors, VLSI functional units, and a common two-dimensional shared memory (SM) via a block transfer oriented interconnection network. A shared cache is provided between the TPU's and SM for efficient MIMD interprocessor communication. The SM is also connected via a backend database management network (BDMN) with distributed control to the file memories, which are disk-based database storage devices.

A new class of partitioned matrix algorithms is developed for possible VLSI implementation of large-scale matrix solvers. Fast matrix solvers are higherly demanded in signal/image processing and in many real-time and scientific applications. Only a few functional types of VLSI arithmetic chips are needed for submatrix computations after partitioning. This partitioned approach is not restricted by problem sizes and thus can be applied to solve arbitrarily large linear systems of equations in an iterative fashion. The following four matrix computations are shown systematically partitionable into submatrix operations, which are feasible for direct VLSI implementation.

VLSI modular arithmetic structures and new partitioned matrix algorithms are developed in this paper to perform hardware matrix computations in solving large-scale linear system of equations. Gaussian elimination and inversion of triangular matrices are shown systematically partitionable. All the partitioned algorithms being developed can achieve linear computation time 0(n), where n is the order of the linear system. The partitioned matrix computations are feasible for modular VLSI implementation with constrained I/O terminals. Performance analysis and design tradeoffs of the partitioned VLSI arithmetic structures are also provided.

This paper presents a Markov chain model to analyze the performance of shared-resource array processors for multiple vector processing. Such a parallel processor contains multiple control units sharing a resource pool of processing elements and operating with multiple single-instruction multiple-data streams (MSIMD). In the steady state, the Markov model corresponds to a two-dimensional Markov chain, which can be expressed by a set of equilibrium equations. An iterative method is developed to solve the Markov chain after projecting the equilibrium equations onto a one-dimensional state space. The convergence rate of the iterative method can be greatly enhanced by choosing starting values corresponding to the approximated analytical results obtained earlier by the authors.

Performance optimization of a shared-resource parallel computer is studied in this correspondence. Such a parallel computer contains multiple control units (CU's) sharing a resource pool of processing elements (PE's) and operating with multiple single-instruction-multiple-data (MSIMD) streams. A formal queueing model is proposed for MSIMD machines used in multiple array processing. Analytic results are obtained to evaluate the performance of MSIMD computers. Systematic procedures are given to optimize the size of PE resource pool and to determine the sufficient job queue size for a given vector workload distribution.

Two new families of LSI iterative logic arrays are proposed to perform two's complement multiplication based on the Baugh–Wooley algorithm [2]. The global approach is faster and attractive for LSI but limited in size due to current monolithic and packaging technology. The modular approach is better suited to realizing arbitrarily large array multipliers at only slight decrease in speed. The proposed additive multiply modules can be externally programmed by hardwiring to multiply binary numbers in either two's complement or unsigned format. No peripheral logic circuits such as Wallace trees or complementers are needed in constructing the proposed modular multiplication networks. Speed analysis, hardware complexity, packaging, and application requirements of the proposed array multipliers are also provided.

A new interleaved rational/radix number system is proposed for upgrading the precision of normalized Floating-Point (FLP) arithmetic operations without increasing the basic word length. A complete set of rational rounding and arithmetic algorithms are developed. The Average Relative Representation Error (ARRE) of the proposed flexible FLP system is computed through a series of simulation studies on CDC 6500. Our results show a 10% improvement of representation accuracy when compared with the ARRE of conventional FLP system. The architecture of a rational FLP arithmetic processor is also presented. Tradeoffs between operating speed and computing accuracy are discussed.

A new realization scheme is proposed for implementing sequential machines with nontrivial periods. The scheme is primarily based on state assignments related to cyclic partitions on internal states of a sequential machine. Operational linkages of cyclic partitions to the input-independent autonomous clocks of sequential machines are established. Special logic design and IC implementation advantages of the scheme are demonstrated in terms of input and/or state dependencies, logic complexities, and memory requirements of sequential machines.