Autonomous learning of load and traffic patterns to improve cluster utilization

Adaptive clustering aims at improving cluster utilization for varying load and traffic patterns. Locality-based least-connection with replication (LBLCR) scheduling that comes with Linux is designed to help improve cluster utilization through adaptive clustering. A key issue with LBLCR, however, is that cluster performance depends much on a single threshold value that is used to determine adaptation. Once set, the threshold remains fixed, regardless of the load and traffic patterns. If a cluster of PCs is to adapt to different traffic patterns for high utilization, a good threshold has to be selected and used dynamically. We present in this paper an adaptive clustering framework that autonomously learns and adapts to different load and traffic patterns at runtime with no administrator intervention. The cluster is configured once and for all. As the patterns change, the cluster automatically expands/contracts to meet the changing demands. At the same time, the patterns are proactively learned so that when similar patterns emerge in the future, the cluster knows what to do to improve utilization. We have implemented this autonomous learning method and compared it with LBLCR using published Web traces. Experimental results indicate that our autonomous learning method produces high performance scalability and adaptability for different patterns. On the other hand LBLCR-based clustering suffers from performance scalability and adaptability for different traffic patterns since it is not designed to obtain good threshold values and use them at runtime.     

Contention-Aware Communication Schedule for High-Speed Communication

A lot of efforts have been devoted to address the software overhead problem in the past decade, which is known as the major hindrance on high-speed communication. However, this paper shows that having a low-latency communication system does not guarantee to achieve high performance, as there are other communication issues that have not been fully addressed by the use of low-latency communication, such as contention and scheduling of communication events. In this paper, we use the complete exchange operation as a case study to show that with careful design of communication schedules, we can achieve efficient communication as well as prevent congestion. We have developed a complete exchange algorithm, the Synchronous Shuffle Exchange, which is an optimal algorithm on the non-blocking network. To avoid congestion loss caused by the non-deterministic delays in communication events, a global congestion control scheme is introduced. This scheme coordinates all participating nodes to monitor and regulate the traffic load, which effectively avoids congestion loss and maintains sufficient throughput to maximize the performance. To improve the effectiveness of the congestion control scheme when working on the hierarchical network, we incorporate information on the network topology to devise a contention-aware permutation. This permutation scheme generates a communication schedule, which is both node and switch contention-free as well as distributing the network loads more evenly across the hierarchy. This relieves the congestion build-up at the uplink ports and improves the synchronism of the traffic information exchange between cluster nodes. Performance results of our implementation on a 32-node cluster with various network configurations are examined and reported in this paper.     

Cyclone: A High-Performance Cluster-Based Web Server with Socket Cloning

With the ever-growing web traffic, cluster-based web server is becoming more and more important to the Internet's infrastructure. Making the best use of all the available resources in the cluster to achieve high performance is thus a significant research issue. In this paper, we introduce Cyclone, a cluster-based web server that can achieve nearly optimal throughput. Cyclone makes use of a novel network support mechanism called Socket Cloning (SC), together with the method of hot object replication, to obtain high performance. SC allows an opened socket to be moved efficiently between cluster nodes. With SC, the processing of HTTP requests can be migrated to the node that has a cached copy of the requested document, thus obviating the need for any cache transfer between cluster nodes. To achieve better load balancing, frequently accessed documents (hot objects) are replicated to other cluster nodes. Trace-driven benchmark tests using http_load show that Cyclone outperforms existing approaches and can achieve a throughput of 14575 requests/s (89.5 MBytes/s), which is 98% efficiency of the available network bandwidth, with eight web server nodes.     

A distributed clustering algorithm for large-scale dynamic networks

We propose an algorithm that builds and maintains clusters over a network subject to mobility. This algorithm is fully decentralized and makes all the different clusters grow concurrently. The algorithm uses circulating tokens that collect data and move according to a random walk traversal scheme. Their task consists in (i) creating a cluster with the nodes it discovers and (ii) managing the cluster expansion; all decisions affecting the cluster are taken only by a node that owns the token. The size of each cluster is maintained higher than m nodes (m is a parameter of the algorithm). The obtained clustering is locally optimal in the sense that, with only a local view of each clusters, it computes the largest possible number of clusters (i.e. the sizes of the clusters are as close to m as possible). This algorithm is designed as a decentralized control algorithm for large scale networks and is mobility-adaptive: after a series of topological changes, the algorithm converges to a clustering. This recomputation only affects nodes in clusters where topological changes happened, and in adjacent clusters.     

On an improved clustering algorithm based on node density for WSN routing protocol

To better collect data in context to balance energy consumption, wireless sensor networks (WSN) need to be divided into clusters. The division of clusters makes the network become a hierarchical organizational structure, which plays the role of balancing the network load and prolonging the life cycle of the system. In clustering routing algorithm, the pros and cons of clustering algorithm directly affect the result of cluster division. In this paper, an algorithm for selecting cluster heads based on node distribution density and allocating remaining nodes is proposed for the defects of cluster head random election and uneven clustering in the traditional LEACH protocol clustering algorithm in WSN. Experiments show that the algorithm can realize the rapid selection of cluster heads and division of clusters, which is effective for node clustering and is conducive to equalizing energy consumption.

     

Biophysical methods for biochip analysis. Use of wide field digital fluorescent microscopy

This paper discusses an issue on the development of biophysical methods for biochip analysis. A scheme and construction of a biochip analyzer based on wide-field digital fluorescence microscopy are described. The analyzer is designed to register images of biological microchips labeled with fluorescent dyes. The device developed is useful for high-sensitive throughput recording analyses by biochips after interaction of immobilized probes with fluorescently labeled sample molecules as well as it provides the higher rate of the analysis compared to laser scanning devices. With this analyzer a scope where biological microchips can be applied becomes wider, the development of new protocols of the analyses is possible and standard analyses run faster with the use of biochips, the expenses for the analysis performance can be reduced.     

Traffic load monitoring and load balancing for the Internet

This paper proposes a class-based multipath routing algorithm to support Quality of Service (QoS). The algorithm is called Two-level Class-based Routing with Prediction (TCRP). Since frequently flooding routing information is very expensive for dynamic routing, the TCRP is designed to have the traffic load information monitored in one stable period as a guide to control traffic forwarding in the next stable period. The monitoring function is implemented by adopting the leaky bucket mechanism. In TCRP, the path selection function can utilize resources on multipath to achieve load balancing, increase network throughput and reduce the queuing delay. The extensive simulation is conducted to analyze the performance of the TCRP algorithm. The simulation results show that the TCRP can reduce packet drops and increase network throughput in any size network topology. This revised version was published online in July 2006 with corrections to the Cover Date.     

Scalable and effective peer-to-peer desktop grid system

We have designed a set of protocols that use peer-to-peer techniques to efficiently implement a distributed and decentralized desktop grid. Incoming jobs with different resource requirements are matched with system nodes through proximity in an N-dimensional Content-Addressable Network, where each resource type is represented as a distinct dimension. In this paper, we describe a comprehensive suite of techniques that cooperate to maximize throughput, and to ensure that load is balanced across all peers. We balance load induced by job executions through randomly generated virtual dimension values, which act to disaggregate clusters of nodes/jobs, and also by a job pushing mechanism based on an approximate global view of the system. We improve upon initial job assignments by using a job-stealing mechanism to overcome load imbalance caused by heterogeneity of nodes/jobs and stale load information. We also describe a set of optimizations that combine to reduce the system load created by the management of the underlying peer-to-peer system and the job-monitoring infrastructure. Unlike other systems, we can effectively support resource constraints of jobs during the course of load balancing since we simplify the problem of matchmaking through building a multi-dimensional resource space and mapping jobs and nodes to this space. We use extensive simulation results to show that the new techniques improve scalability, system throughput, and average response time.     

A configuration scheme for connectivity-aware mobile P2P networks for efficient mobile cloud-based video streaming services

Mobile cloud-based video streaming services cannot be provided seamlessly when network traffic increases sharply in congested areas such as colleges, universities, and downtown at specific times. This paper proposes a configuration scheme for connectivity-aware P2P networks which can reduce network traffic of cloud-based streaming servers through sharing of streaming video by utilizing information on connectivity status of mobile devices, and which can improve the quality of mobile cloud-based video streaming services by considering mobility of mobile devices and QoS which have not been considered in existing P2P schemes. Our proposed scheme reduces the amount of server traffic and the disconnection times of mobile devices significantly, compared to the non-P2P scheme and the AODV scheme. It also increases considerably the number of mobile devices to which a cloud-based streaming server can provide video streaming services simultaneously, compared to the two schemes.     

Multi-Parametric Clustering for Sensor Node Coordination in Cognitive Wireless Sensor Networks

The deployment of wireless sensor networks for healthcare applications have been motivated and driven by the increasing demand for real-time monitoring of patients in hospital and large disaster response environments. A major challenge in developing such sensor networks is the need for coordinating a large number of randomly deployed sensor nodes. In this study, we propose a multi-parametric clustering scheme designed to aid in the coordination of sensor nodes within cognitive wireless sensor networks. In the proposed scheme, sensor nodes are clustered together based on similar network behaviour across multiple network parameters, such as channel availability, interference characteristics, and topological characteristics, followed by mechanisms for forming, joining and switching clusters. Extensive performance evaluation is conducted to study the impact on important factors such as clustering overhead, cluster joining estimation error, interference probability, as well as probability of reclustering. Results show that the proposed clustering scheme can be an excellent candidate for use in large scale cognitive wireless sensor network deployments with high dynamics.     

Fault tolerance and QoS scheduling using CAN in mobile social cloud computing

The performance of mobile devices including smart phones and laptops is steadily rising as prices plummet sharply. So, mobile devices are changing from being a mere interface for requesting services to becoming computing resources for providing and sharing services due to immeasurably improved performance. With the increasing number of mobile device users, the utilization rate of SNS (Social Networking Service) is also soaring. Applying SNS to the existing computing environment enables members of social network to share computing services without further authentication. To use mobile device as a computing resource, temporary network disconnection caused by user mobility and various HW/SW faults causing service disruption should be considered. Also these issues must be resolved to support mobile users and to provide user requirements for services. Accordingly, we propose fault tolerance and QoS (Quality of Services) scheduling using CAN (Content Addressable Network) in Mobile Social Cloud Computing (MSCC). MSCC is a computing environment that integrates social network-based cloud computing and mobile devices. In the computing environment, a mobile user can, through mobile devices, become a member of a social network through real world relationships. Essentially, members of a social network share cloud service or data with other members without further authentication by using their mobile device. We use CAN as the underlying MSCC to logically manage the locations of mobile devices. Fault tolerance and QoS scheduling consists of four sub-scheduling algorithms: malicious-user filtering, cloud service delivery, QoS provisioning, and replication and load-balancing. Under the proposed scheduling, a mobile device is used as a resource for providing cloud services, faults caused from user mobility or other reasons are tolerated and user requirements for QoS are considered. We simulate scheduling both with and without CAN. The simulation results show that our proposed scheduling algorithm enhances cloud service execution time, finish time and reliability and reduces the cloud service error rate.     

Declarative platform for high-performance network traffic analytics

This paper presents Scalanytics, a declarative platform that supports high-performance application layer analysis of network traffic. Scalanytics uses (1) stateful network packet processing techniques for extracting application layer data from network packets, (2) a declarative rule-based language called Analog for compactly specifying analysis pipelines from reusable modules, and (3) a task-stealing architecture for processing network packets at high throughput within these pipelines, by leveraging multi-core processing capabilities in a load-balanced manner without the need for explicit performance profiling. In a cluster of machines, Scalanytics further improves throughput through the use of a consistent-hashing based load partitioning strategy. Our evaluation on a 16-core machine demonstrate that Scalanytics achieves up to 11.4 \(\times \) improvement in throughput compared with the best uniprocessor implementation. Moreover, Scalanytics outperforms the Bro intrusion detection system by an order of magnitude when used for analyzing SMTP traffic. We further observed increased throughput when running Scalanytics pipelines across multiple machines.     

Biophysical methods for biochip analysis. Use of wide-field digital fluorescence microscopy

This paper discusses the development of biophysical methods for biochip analysis. A scheme and construction of a biochip analyzer based on wide-field digital fluorescence microscopy are described. The analyzer is designed to register images of biological microchips labeled with fluorescent dyes. The device developed is useful for high-sensitivity throughput recording of analyses with biochips after interaction of immobilized probes with fluorescently labeled sample molecules as well as it provides a higher rate of the analysis compared with laser scanning devices. With this analyzer, the scope where biological microchips can be applied becomes wider, development of new protocols of the analyses is possible and standard analyses run faster with the use of biochips, the expenses for performing routine analyses can be reduced.     

Misty Mountain clustering: application to fast unsupervised flow cytometry gating

Background  

There are many important clustering questions in computational biology for which no satisfactory method exists. Automated clustering algorithms, when applied to large, multidimensional datasets, such as flow cytometry data, prove unsatisfactory in terms of speed, problems with local minima or cluster shape bias. Model-based approaches are restricted by the assumptions of the fitting functions. Furthermore, model based clustering requires serial clustering for all cluster numbers within a user defined interval. The final cluster number is then selected by various criteria. These supervised serial clustering methods are time consuming and frequently different criteria result in different optimal cluster numbers. Various unsupervised heuristic approaches that have been developed such as affinity propagation are too expensive to be applied to datasets on the order of 10⁶ points that are often generated by high throughput experiments.     

Heterogeneous process state capture and recovery through Process Introspection

The ability to capture the state of a process and later recover that state in the form of an equivalent running process is the basis for a number of important features in parallel and distributed systems. Adaptive load sharing and fault tolerance are well-known examples. Traditional state capture mechanisms have employed an external agent (such as the operating system kernel) to examine and capture process state. However, the increasing prevalence of heterogeneous cluster and “metacomputing” systems as high-performance computing platforms has prompted investigation of process-internal state capture mechanisms. Perhaps the greatest advantage of the process-internal approach is the ability to support cross-platform state capture and recovery, an important feature in heterogeneous environments. Among the perceived disadvantages of existing process-internal mechanisms are poor performance in multiple respects, and difficulty of use in terms of programmer effort. In this paper we describe a new process-internal state capture and recovery mechanism: Process Introspection. Experiences with this system indicate that the perceived disadvantages associated with process-internal mechanisms can be largely overcome, making this approach to state capture an appropriate one for cluster and metacomputing environments. This revised version was published online in July 2006 with corrections to the Cover Date.     

Clustering microarray gene expression data using weighted Chinese restaurant process

MOTIVATION: Clustering microarray gene expression data is a powerful tool for elucidating co-regulatory relationships among genes. Many different clustering techniques have been successfully applied and the results are promising. However, substantial fluctuation contained in microarray data, lack of knowledge on the number of clusters and complex regulatory mechanisms underlying biological systems make the clustering problems tremendously challenging. RESULTS: We devised an improved model-based Bayesian approach to cluster microarray gene expression data. Cluster assignment is carried out by an iterative weighted Chinese restaurant seating scheme such that the optimal number of clusters can be determined simultaneously with cluster assignment. The predictive updating technique was applied to improve the efficiency of the Gibbs sampler. An additional step is added during reassignment to allow genes that display complex correlation relationships such as time-shifted and/or inverted to be clustered together. Analysis done on a real dataset showed that as much as 30% of significant genes clustered in the same group display complex relationships with the consensus pattern of the cluster. Other notable features including automatic handling of missing data, quantitative measures of cluster strength and assignment confidence. Synthetic and real microarray gene expression datasets were analyzed to demonstrate its performance. AVAILABILITY: A computer program named Chinese restaurant cluster (CRC) has been developed based on this algorithm. The program can be downloaded at http://www.sph.umich.edu/csg/qin/CRC/.     

Network slicing to improve multicasting in HPC clusters

In high performance computing (HPC) resources’ extensive experiments are frequently executed. HPC resources (e.g. computing machines and switches) should be able to handle running several experiments in parallel. Typically HPC utilizes parallelization in programs, processing and data. The underlying network is seen as the only non-parallelized HPC component (i.e. no dynamic virtual slicing based on HPC jobs). In this scope we present an approach in this paper to utilize software defined networking (SDN) to parallelize HPC clusters among the different running experiments. We propose to accomplish this through two major components: A passive module (network mapper/remapper) to select for each experiment as soon as it starts the least busy resources in the network, and an SDN-HPC active load balancer to perform more complex and intelligent operations. Active load balancer can logically divide the network based on experiments’ host files. The goal is to reduce traffic to unnecessary hosts or ports. An HPC experiment should multicast, rather than broadcast to only cluster nodes that are used by the experiment. We use virtual tenant network modules in Opendaylight controller to create VLANs based on HPC experiments. In each HPC host, virtual interfaces are created to isolate traffic from the different experiments. The traffic between the different physical hosts that belong to the same experiment can be distinguished based on the VLAN ID assigned to each experiment. We evaluate the new approach using several HPC public benchmarks. Results show a significant enhancement in experiments’ performance especially when HPC cluster experiences running several heavy load experiments simultaneously. Results show also that this multi-casting approach can significantly reduce casting overhead that is caused by using a single cast for all resources in the HPC cluster. In comparison with InfiniBand networks that offer interconnect services with low latency and high bandwidth, HPC services based on SDN can provide two distinguished objectives that may not be possible with InfiniBand: The first objective is the integration of HPC with Ethernet enterprise networks and hence expanding HPC usage to much wider domains. The second objective is the ability to enable users and their applications to customize HPC services with different QoS requirements that fit the different needs of those applications and optimize the usage of HPC clusters.     

Clustering huge data sets for parametric PET imaging

A new preprocessing clustering technique for quantification of kinetic PET data is presented. A two-stage clustering process, which combines a precluster and a classic hierarchical cluster analysis, provides data which are clustered according to a distance measure between time activity curves (TACs). The resulting clustered mean TACs can be used directly for estimation of kinetic parameters at the cluster level, or to span a vector space that is used for subsequent estimation of voxel level kinetics. The introduction of preclustering significantly reduces the overall time for clustering of multiframe kinetic data. The efficiency and superiority of the preclustering scheme combined with thresholding is validated by comparison of the results for clustering both with and without preclustering for FDG-PET brain data of 13 healthy subjects.     

Multiphase electrodes for microbead control applications: integration of DEP and electrokinetics for bio-particle positioning

Advances in microfabrication have introduced new possibilities for automated, high-throughput biomedical investigations and analysis. Physical effects such as dielectrophoresis (DEP) and AC electrokinetics can be used to manipulate particles in solution to coordinate a sequence of bioanalytical processing steps. DEP is accomplished with non-uniform electric fields that can polarize particles (microbeads, cells, viruses, DNA, proteins, etc.) in suspension causing translational or rotational movement. AC electrokinetics is another phenomena involved with movement of particles in suspension with electric fields and is comprised of both electro-thermal and electro-osmotic effects. This paper investigates single layer electrodes that are effective for particle localization and clustering based on DEP and AC electrokinetic effects. We demonstrate a novel multi-electrode setup capable of clustering particles into an array of discrete bands using activated and electrically floating electrodes. These bands shift to adjacent regions on the electrode surface by altering the electrode activation scheme. The predictability of particle placement to specific locations provides new opportunities for integration and coordination with raster scanning lasers or a charge coupled device (CCD) for advanced biomedical diagnostic devices, and more sophisticated optical interrogation techniques.     

ILLUMINA Golden Gate DNA甲基化芯片的KL-FCM聚类分析

DNA甲基化作为一种重要的表观遗传修饰,其甲基化水平被发现与疾病的发生发展密切相关,对其进行聚类分析有希望发现新的疾病亚型并建立有效的疾病预测预后方法。传统的聚类分析方法之一模糊C-均值（FCM：Fuzzy C-means）适用于特征空间呈球形或椭球形分布的场景,缺乏普适性。而Illumina Golden Gate平台通过计算基因的各甲基化位点的甲基化百分比描述其甲基化程度,其值位于（0,1）之间,服从混合贝塔分布,不能直接采用FCM进行聚类分析。鉴于此,本文提出基于KL特征测度的KL-FCM聚类算法,采用各样本间的K-L距离作为样本划分时的度量准则。最后,本文基于KL-FCM算法实现IRIS测试数据集和基因的DNA甲基化水平数据的聚类分析。实验结果表明该方法可以以更低的计算负荷获得优于k-均值（k-means）和传统FCM的分类效果。