Grid transaction management and an efficient development kit

Grid transaction management aims at guaranteeing the system consistency in face of various failures in Grid environments. In this paper, we propose a Grid transaction service (GridTS) and design coordination mechanisms for atomic, long-lived and real-time Grid transactions respectively, based on the features of Grid environments. GridTS has the following three advantages. Firstly, it separates the transaction management unit with transaction coordination algorithms so that it can coordinate the above three categories of transactions in a uniform way. Secondly, GridTS can dynamically generate compensating transactions during the long-lived transaction processing. Finally, it provides the programming interfaces similar to traditional distributed transactions. Moreover, we implement a Grid transaction development kit (GridTDK) for application programmers based on our GridTS. We evaluate the feasibility and effectiveness of GridTS by developing an application system using our GridTDK. ©2012 CRL Publishing Ltd.

An algorithm to median shortest path problem (MSPP) in the design of urban transportation networks

This paper proposes an efficient solution algorithm for realistic multi-objective median shortest path problems in the design of urban transportation networks. The proposed problem formulation and solution algorithm to median shortest path problem is based on three realistic objectives via route cost or investment cost, overall travel time of the entire network and total toll revenue. The proposed solution approach to the problem is based on the heuristic labeling and exhaustive search technique in criteria space and solution space of the algorithm respectively. The first labels each node in terms of route cost and deletes cyclic and infeasible paths in criteria space imposing cyclic break and route cost constraint respectively. The latter deletes dominated paths in terms of objectives vector in solution space in order to identify a set of Pareto optimal paths. The approach, thus, proposes a non-inferior solution set of Pareto optimal paths based on non-dominated objective vector and leaves the ultimate decision to decision-makers for purpose specific final decision during applications. A numerical experiment is conducted to test the proposed algorithm using artificial transportation network. Sensitivity analyses have shown that the proposed algorithm is advantageous and efficient over existing algorithms to find a set of Pareto optimal paths to median shortest paths problems.

Malwise-an effective and efficient classification system for packed and polymorphic malware

Signature-based malware detection systems have been a much used response to the pervasive problem of malware. Identification of malware variants is essential to a detection system and is made possible by identifying invariant characteristics in related samples. To classify the packed and polymorphic malware, this paper proposes a novel system, named Malwise, for malware classification using a fast application-level emulator to reverse the code packing transformation, and two flowgraph matching algorithms to perform classification. An exact flowgraph matching algorithm is employed that uses string-based signatures, and is able to detect malware with near real-time performance. Additionally, a more effective approximate flowgraph matching algorithm is proposed that uses the decompilation technique of structuring to generate string-based signatures amenable to the string edit distance. We use real and synthetic malware to demonstrate the effectiveness and efficiency of Malwise. Using more than 15,000 real malware, collected from honeypots, the effectiveness is validated by showing that there is an 88 percent probability that new malware is detected as a variant of existing malware. The efficiency is demonstrated from a smaller sample set of malware where 86 percent of the samples can be classified in under 1.3 seconds.

Accurate and efficient face recognition from video

As a problem of high practical appeal but outstanding challenges, computer-based face recognition remains a topic of extensive research attention. In this paper we are specifically interested in the task of identifying a person from multiple training and query images. Thus, a novel method is proposed which advances the state-of-the-art in set based face recognition. Our method is based on a previously described invariant in the form of generic shape-illumination effects. The contributions include: (i) an analysis of computational demands of the original method and a demonstration of its practical limitations, (ii) a novel representation of personal appearance in the form of linked mixture models in image and pose-signature spaces, and (iii) an efficient (in terms of storage needs and matching time) manifold re-illumination algorithm based on the aforementioned representation. An evaluation and comparison of the proposed method with the original generic shape-illumination algorithm shows that comparably high recognition rates are achieved on a large data set (1.5% error on 700 face sets containing 100 individuals and extreme illumination variation) with a dramatic improvement in matching speed (over 700 times for sets containing 1600 faces) and storage requirements (independent of the number of training images).

Developing an empirical algorithm for protecting text-based CAPTCHAs against segmentation attacks

In this paper, we aim to provide an effective and efficient method to generate text-based Captchas which are resilient against segmentation attack. Different to the popular industry practice of using very simple color schemes, we advocate to use multiple colors in our Captchas. We adopt the idea of brush and canvas when coloring our Captchas. Furthermore, we choose to use simple accumulating functions to achieve diffusion on painted colors and DES encryption to achieve a good level of confusion on the brush pattern. To facilitate ordinary users and developers, we propose an empirical algorithm with support of Taguchi method to guarantee the quality of the chosen color schemes. Our proposed methodology has at least three advantages — 1) the settings of color schemes can be fully customized by the user or developer; 2) the quality of selected colors have desirable statistical features that are ensured by Taguchi method; 3) the algorithm can be fully automated into computer programs. Moreover, our included examples and experiments prove the practicality and validity of our algorithm.

GLOA : a new job scheduling algorithm for grid computing

The purpose of grid computing is to produce a virtual supercomputer by using free resources available through widespread networks such as the Internet. This resource distribution, changes in resource availability, and an unreliable communication infrastructure pose a major challenge for efficient resource allocation. Because of the geographical spread of resources and their distributed management, grid scheduling is considered to be a NP-complete problem. It has been shown that evolutionary algorithms offer good performance for grid scheduling. This article uses a new evaluation (distributed) algorithm inspired by the effect of leaders in social groups, the group leaders' optimization algorithm (GLOA), to solve the problem of scheduling independent tasks in a grid computing system. Simulation results comparing GLOA with several other evaluation algorithms show that GLOA produces shorter makespans.

An efficient and distributed file search in unstructured peer-to-peer networks

Peer-to-peer (P2P) networks are gaining increased attention from both the scientific community and the larger Internet user community. Data retrieval algorithms lie at the center of P2P networks, and this paper addresses the problem of efficiently searching for files in unstructured P2P systems. We propose an Improved Adaptive Probabilistic Search (IAPS) algorithm that is fully distributed and bandwidth efficient. IAPS uses ant-colony optimization and takes file types into consideration in order to search for file container nodes with a high probability of success. We have performed extensive simulations to study the performance of IAPS, and we compare it with the Random Walk and Adaptive Probabilistic Search algorithms. Our experimental results show that IAPS achieves high success rates, high response rates, and significant message reduction.

Finite element model updating using estimation of distribution algorithm

Finite Element (FE) model updating has been attracting research attentions in structural engineering fields for over 20 years. Its immense importance to the design, construction and maintenance of civil and mechanical structures has been highly recognised. However, many sources of uncertainties may affect the updating results. These uncertainties may be caused by FE modelling errors, measurement noises, signal processing techniques, and so on. Therefore, research efforts on model updating have been focusing on tackling with uncertainties for a long time. Recently, a new type of evolutionary algorithms has been developed to address uncertainty problems, known as Estimation of Distribution Algorithms (EDAs). EDAs are evolutionary algorithms based on estimation and sampling from probabilistic models and able to overcome some of the drawbacks exhibited by traditional genetic algorithms (GAs). In this paper, a numerical steel simple beam is constructed in commercial software ANSYS. The various damage scenarios are simulated and EDAs are employed to identify damages via FE model updating process. The results show that the performances of EDAs for model updating are efficient and reliable.

Efficient road detection and tracking for unmanned aerial vehicle

Abstract - An unmanned aerial vehicle (UAV) has many applications in a variety of fields. Detection and tracking of a specific road in UAV videos play an important role in automatic UAV navigation, traffic monitoring, and ground–vehicle tracking, and also is very helpful for constructing road networks for modeling and simulation. In this paper, an efficient road detection and tracking framework in UAV videos is proposed. In particular, a graph-cut–based detection approach is given to accurately extract a specified road region during the initialization stage and in the middle of tracking process, and a fast homography-based road-tracking scheme is developed to automatically track road areas. The high efficiency of our framework is attributed to two aspects: the road detection is performed only when it is necessary and most work in locating the road is rapidly done via very fast homography-based tracking. Experiments are conducted on UAV videos of real road scenes we captured and downloaded from the Internet. The promising results indicate the effectiveness of our proposed framework, with the precision of 98.4% and processing 34 frames per second for 1046 x 595 videos on average.

Efficient consolidation-aware VCPU scheduling on multicore virtualization platform

Multicore processors are widely used in today's computer systems. Multicore virtualization technology provides an elastic solution to more efficiently utilize the multicore system. However, the Lock Holder Preemption (LHP) problem in the virtualized multicore systems causes significant CPU cycles wastes, which hurt virtual machine (VM) performance and reduces response latency. The system consolidates more VMs, the LHP problem becomes worse. In this paper, we propose an efficient consolidation-aware vCPU (CVS) scheduling scheme on multicore virtualization platform. Based on vCPU over-commitment rate, the CVS scheduling scheme adaptively selects one algorithm among three vCPU scheduling algorithms: co-scheduling, yield-to-head, and yield-to-tail based on the vCPU over-commitment rate because the actions of vCPU scheduling are split into many single steps such as scheduling vCPUs simultaneously or inserting one vCPU into the run-queue from the head or tail. The CVS scheme can effectively improve VM performance in the low, middle, and high VM consolidation scenarios. Using real-life parallel benchmarks, our experimental results show that the proposed CVS scheme improves the overall system performance while the optimization overhead remains low.

AMC: an adaptive multi-level cache algorithm in hybrid storage systems

Hybrid storage systems that consist of flash-based solid state drives (SSDs) and traditional disks are now widely used. In hybrid storage systems, there exists a two-level cache hierarchy that regard dynamic random access memory (DRAM) as the first level cache and SSD as the second level cache for disk storage. However, this two-level cache hierarchy typically uses independent cache replacement policies for each level, which makes cache resource management inefficient and reduces system performance. In this paper, we propose a novel adaptive multi-level cache (AMC) replacement algorithm in hybrid storage systems. The AMC algorithm adaptively adjusts cache blocks between DRAM and SSD cache levels using an integrated solution. AMC uses combined selective promote and demote operations to dynamically determine the level in which the blocks are to be cached. In this manner, the AMC algorithm achieves multi-level cache exclusiveness and makes cache resource management more efficient. By using real-life storage traces, our evaluation shows the proposed algorithm improves hybrid multi-level cache performance and also increases the SSD lifetime compared with traditional multi-level cache replacement algorithms.

Layered workflow scheduling algorithm

Workflow applications require workflow processing in which workflow tasks are processed based on their dependencies. With the emergency of complex distributed systems such as grids and clouds, efficient workflow scheduling (WFS) algorithms have become the core components of the workflow management systems (WfMS). Thus, WFS that allocates each task in the workflow to a relevant resource with the aim of improving system performance and end user satisfaction is fundamentally important. In this paper, we propose a new workflow scheduling algorithm called Layered Workflow Scheduling Algorithm (LWFS) for scheduling workflow applications. We studied the efficacy of the LWFS scheduling experimentally and compared its performance with approaches including Improved Critical Path using Descendant Prediction (ICPDP), Highest Level First with Estimated Time (HLFET), Modified Critical Path (MCP) and Earliest Time First (ETF). The results of the experiments show that the proposed approach outperforms other approaches.

A new physarum network based genetic algorithm for bandwidth-delay constrained least-cost multicast routing

Bandwidth-delay constrained least-cost multicast routing is a typical NP-complete problem. Although some swarm-based intelligent algorithms (e.g., genetic algorithm (GA)) are proposed to solve this problem, the shortcomings of local search affect the computational effectiveness. Taking the ability of building a robust network of Physarum network model (PN), a new hybrid algorithm, Physarum network-based genetic algorithm (named as PNGA), is proposed in this paper. In PNGA, an updating strategy based on PN is used for improving the crossover operator of traditional GA, in which the same parts of parent chromosomes are reserved and the new offspring by the Physarum network model is generated. In order to estimate the effectiveness of our proposed optimized strategy, some typical genetic algorithms and the proposed PNGA are compared for solving multicast routing. The experiments show that PNGA has more efficient than original GA. More importantly, the PNGA is more robustness that is very important for solving the multicast routing problem.