OPTIMA: On-Line Partitioning Skew Mitigation for MapReduce with Resource Adjustment

Partitioning skew has been shown to be a major issue that can significantly prolong the execution time of MapReduce jobs. Most of the existing off-line heuristics for partitioning skew mitigation are inefficient; they have to wait for the completion of all the map tasks. Some solutions can tackle this problem on-line, but will impose an additional overhead by repartitioning the workload of overloaded tasks. In this paper, we present OPTIMA, an on-line partitioning skew mitigation technique for MapReduce. OPTIMA predicts the workload distribution of reduce tasks at run-time, leverages the deviation detection technique to identify the overloaded tasks and pro-actively adjusts resource allocation for these tasks to reduce their execution time. We provide the upper bound of OPTIMA in time complexity, while allowing OPTIMA to perform totally on-line. Through experiments using both real and synthetic workloads running on an 11-node Hadoop cluster, we have observed OPTIMA can effectively mitigate the partitioning skew and improved the job completion time by up to 36.73 % in our experiments.     

Cost-Efficient Traffic Aggregation Employing Cross-Layer Shared Protection

Shared protection/restoration is a promising solution for reducing protection resources and is supported at each layer of the current multi-layer networks. Software-defined networking is expected to reduce equipment cost as well as operational cost by orchestrating these shared protection functionalities. However, although protection resource sharing improves link utilization, it sometimes increases the required equipment. Meanwhile, traffic re-aggregation at each layer is an important technique for low volume traffic to utilize the underlying link capacity more efficiently, but re-aggregation also makes it difficult to share protection resources with traffic at lower layers. In this paper, we present multi-layer network design strategy and method that reduce equipment cost by means of both traffic re-aggregation at each layer and protection resource sharing among multiple service traffic at different layers. The strategy first prioritizes traffic re-aggregation at each layer, and then maximally delegates shared protection to lower layers as long as it does not increase the required capacity at the lower layer. Evaluation results from the example three-layer networks confirm that the proposed method can effectively reduce equipment cost compared to the conventional design method. Cost reduction is achieved by leveraging shared protection functions at multiple layers.     

Reliable Communication Networks for Smart Grid Transmission Systems

In this paper, we discuss the communications reliability requirements posed by the smart power grid with a focus on communications in support of wide area situational awareness. Implementation of wide area situational awareness relies on both transmission substation networks and wide area optical networks. We study the reliability of a sample communications network of the California Power Grid and find that its reliability falls short of proposed requirements. To overcome this issue, we consider the problem of designing the substation network and the wide area network to meet the reliability requirements while minimizing the network cost. For the wide area network design problem, we propose two alternate design approaches, namely: (1) following the power lines and (2) a mesh based design interconnecting the nodes. For the first approach we develop two greedy iterative heuristics and a heuristic integer linear programming (H-ILP) model using minimum cut-sets for network reliability optimization. The greedy iterative algorithms outperform the H-ILP approach in terms of cost, but require a larger amount of computing resources. Both proposed models are in fact complementary and thus provide a framework to optimize the reliability of smart grid communications networks restricted to following the power lines. In the second approach a greenfield mesh network method is proposed based on starting with a minimum spanning tree which is then augmented through a greedy heuristic into a mesh. Comparative numerical results show that the reliable mesh design has advantages in terms of the number of links and total link distance needed.     

Exploiting SSDs in operational multiversion databases

Multiversion databases store both current and historical data. Rows are typically annotated with timestamps representing the period when the row is/was valid. We develop novel techniques to reduce index maintenance in multiversion databases, so that indexes can be used effectively for analytical queries over current data without being a heavy burden on transaction throughput. To achieve this end, we re-design persistent index data structures in the storage hierarchy to employ an extra level of indirection. The indirection level is stored on solid-state disks that can support very fast random I/Os, so that traversing the extra level of indirection incurs a relatively small overhead. The extra level of indirection dramatically reduces the number of magnetic disk I/Os that are needed for index updates and localizes maintenance to indexes on updated attributes. Additionally, we batch insertions within the indirection layer in order to reduce physical disk I/Os for indexing new records. In this work, we further exploit SSDs by introducing novel DeltaBlock techniques for storing the recent changes to data on SSDs. Using our DeltaBlock, we propose an efficient method to periodically flush the recently changed data from SSDs to HDDs such that, on the one hand, we keep track of every change (or delta) for every record, and, on the other hand, we avoid redundantly storing the unchanged portion of updated records. By reducing the index maintenance overhead on transactions, we enable operational data stores to create more indexes to support queries. We have developed a prototype of our indirection proposal by extending the widely used generalized search tree open-source project, which is also employed in PostgreSQL. Our working implementation demonstrates that we can significantly reduce index maintenance and/or query processing cost by a factor of 3. For the insertion of new records, our novel batching technique can save up to 90 % of the insertion time. For updates, our prototype demonstrates that we can significantly reduce the database size by up to 80 % even with a modest space allocated for DeltaBlocks on SSDs.     

External sorting on flash storage: reducing cell wearing and increasing efficiency by avoiding intermediate writes

This paper studies the problem of how to conduct external sorting on flash drives while avoiding intermediate writes to the disk. The focus is on sort in portable electronic devices, where relations are only larger than the main memory by a small factor, and on sort as part of distributed processes where relations are frequently partially sorted. In such cases, sort algorithms that refrain from writing intermediate results to the disk have three advantages over algorithms that perform intermediate writes. First, on devices in which read operations are much faster than writes, such methods are efficient and frequently outperform Merge Sort. Secondly, they reduce flash cell degradation caused by writes. Thirdly, they can be used in cases where there is not enough disk space for the intermediate results. Novel sort algorithms that avoid intermediate writes to the disk are presented. An experimental evaluation, on different flash storage devices, shows that in many cases the new algorithms can extend the lifespan of the devices by avoiding unnecessary writes to the disk, while maintaining efficiency, in comparison with Merge Sort.     

Rotation,scaling and translation invariant texture recognition by Bessel-Fourier moments

The ideal of Bessel-Fourier moments (BFMs) for image analysis and only rotation invariant image cognition has been proposed recently. In this paper, we extend the previous work and propose a new method for rotation, scaling and translation (RST) invariant texture recognition using Bessel-Fourier moments. Compared with the others moments based methods, the radial polynomials of Bessel-Fourier moments have more zeros and these zeros are more evenly distributed. It makes Bessel-Fourier moments more suitable for invariant texture recognition as a generalization of orthogonal complex moments. In the experiment part, we got three testing sets of 16, 24 and 54 texture images by way of translating, rotating and scaling them separately. The correct classification percentages (CCPs) are compared with that of orthogonal Fourier-Mellin moments and Zernike moments based methods in both noise-free and noisy condition. Experimental results validate the conclusion of theoretical derivation: BFM performs better in recognition capability and noise robustness in terms of RST texture recognition under both noise-free and noisy condition when compared with orthogonal Fourier-Mellin moments and Zernike moments based methods.     

Design and implementation of a block‐backstepping based tracking control for nonholonomic wheeled mobile robot

This paper presents formulation of a novel block‐backstepping based control algorithm to overcome the challenges posed by the tracking and the stabilization problem for a differential drive wheeled mobile robot (WMR). At first, a two‐dimensional output vector for the WMR has been defined in such a manner that it would decouple the two control inputs and, thereby, allow the designer to formulate the control laws for the two inputs one at a time. Actually, the decoupling has been carried out in a way to convert the system into block‐strict feedback form. Thereafter, block‐backstepping control algorithm has been utilized to derive the expressions of the control inputs for the WMR system. The proposed block‐backstepping technique has further been enriched by incorporating an integral action for enhancing the steady state performance of the overall system. Global asymptotic stability of the overall system has been analyzed using Lyapunov stability criteria. Finally, the proposed control algorithm has been implemented on a laboratory scale differential drive WMR to verify the effectiveness of the proposed control law in real‐time environment. Indeed, the proposed design approach is novel in the sense that it has judiciously exploited the nonholonomic constraint of the WMR to result in a reduced order block‐backstepping controller for the WMR, and thereby, it has eventually yielded a compact expression of the control law that is amenable to real‐time implementation. Copyright © 2015 John Wiley & Sons, Ltd.     

Topology Optimization in Aircraft and Aerospace Structures Design

Topology optimization has become an effective tool for least-weight and performance design, especially in aeronautics and aerospace engineering. The purpose of this paper is to survey recent advances of topology optimization techniques applied in aircraft and aerospace structures design. This paper firstly reviews several existing applications: (1) standard material layout design for airframe structures, (2) layout design of stiffener ribs for aircraft panels, (3) multi-component layout design for aerospace structural systems, (4) multi-fasteners design for assembled aircraft structures. Secondly, potential applications of topology optimization in dynamic responses design, shape preserving design, smart structures design, structural features design and additive manufacturing are introduced to provide a forward-looking perspective.     

Non-intrusive Coupling: Recent Advances and Scalable Nonlinear Domain Decomposition

This paper provides a detailed review of the global/local non-intrusive coupling algorithm. Such method allows to alter a global finite element model, without actually modifying its corresponding numerical operator. We also look into improvements of the initial algorithm (Quasi-Newton and dynamic relaxation), and provide comparisons based on several relevant test cases. Innovative examples and advanced applications of the non-intrusive coupling algorithm are provided, granting a handy framework for both researchers and engineers willing to make use of such process. Finally, a novel nonlinear domain decomposition method is derived from the global/local non-intrusive coupling strategy, without the need to use a parallel code or software. Such method being intended to large scale analysis, we show its scalability. Jointly, an efficient high level Message Passing Interface coupling framework is also proposed, granting an universal and flexible way for easy software coupling. A sample code is also given.