Free-scaling your data center

The increasing popularity of both small and large private clouds and expanding public clouds poses new requirements to data center (DC) architectures. First, DC architectures should be incrementally scalable allowing the creation of DCs of arbitrary size with consistent performance characteristics. Second, initial DC deployments should be incrementally expandable supporting small-scale upgrades without decreasing operation efficiency. A DC architecture possessing both properties satisfies the requirement of free-scaling.Recent work in DC design focuses on traditional performance and scalability characteristics, therefore resulting in symmetric topologies whose upgradability is coarse-grained at best. In our earlier work we proposed Scafida, an asymmetric, scale-free network inspired DC topology which scales incrementally and has favorable structural characteristics. In this paper, we build on Scafida and propose a full-fledged DC architecture achieving free-scaling called FScafida. Our main contribution is threefold. First, we propose an organic expansion algorithm for FScafida; this combined with Scafida’s flexible original design results in a freely scalable architecture. Second, we introduce the Effective Source Routing mechanism that provides near-shortest paths, multi-path and multicast capability, and low signaling overhead by exploiting the benefits of the FScafida topology. Third, we show based on extensive simulations and a prototype implementation that FScafida is capable of handling the traffic patterns characteristic of both enterprise and cloud data centers, tolerates network equipment failures to a high degree, and allows for high bisection bandwidth.     

Topology management techniques for tolerating node failures in wireless sensor networks: A survey

In wireless sensor networks (WSNs) nodes often operate unattended in a collaborative manner to perform some tasks. In many applications, the network is deployed in harsh environments such as battlefield where the nodes are susceptible to damage. In addition, nodes may fail due to energy depletion and breakdown in the onboard electronics. The failure of nodes may leave some areas uncovered and degrade the fidelity of the collected data. However, the most serious consequence is when the network gets partitioned into disjoint segments. Losing network connectivity has a very negative effect on the applications since it prevents data exchange and hinders coordination among some nodes. Therefore, restoring the overall network connectivity is very crucial. Given the resource-constrained setup, the recovery should impose the least overhead and performance impact. This paper focuses on network topology management techniques for tolerating/handling node failures in WSNs. Two broad categories based on reactive and proactive methods have been identified for classifying the existing techniques. Considering these categories, a thorough analysis and comparison of all the recent works have been provided. Finally, the paper is concluded by outlining open issues that warrant additional research.     

System fault-tolerance analysis of COTS-based satellite on-board computers

Fault-tolerance analysis reveals possible system behavior under the influence of faults. Such analysis is essential for satellites where faults might be caused by space radiation and autonomous recovery is needed. In this paper we present a statistical simulation approach for fault-tolerance analysis of satellite On-Board Computers (OBCs) that are based on Commercial Off-The-Shelf (COTS) components. Since the logic level of COTS electronics is unknown to satellite designers, a new higher-level fault-tolerance analysis is required. We propose such technique that relies on OBC modeling and fault modeling, based on the modeling principle of Single-Event Upsets (SEUs). For the first time we can compare the efficiency of fault-tolerance techniques implemented in software and Field-Programmable Gate Array (FPGA). In addition, our approach enables to analyze system fault-tolerance at early development stages. In a case study the approach is applied to an OBC with a Microsemi SmartFusion SoC, that executes a satellite attitude control algorithm. The gained statistical simulation results enabled 50% reduction in the hardware overhead of the implemented memory scrubbing technique without loss in fault-tolerance. Our method revealed critical fault-tolerance drawbacks of the initial system design that could have lead to satellite mission failure.     

Accelerating incremental checkpointing for extreme-scale computing

Concern is beginning to grow in the high-performance computing (HPC) community regarding the reliability of future large-scale systems. Disk-based coordinated checkpoint/restart has been the dominant fault tolerance mechanism in HPC systems for the past 30 years. Checkpoint performance is so fundamental to scalability that nearly all capability applications have custom checkpoint strategies to minimize state and reduce checkpoint time. One well-known optimization to traditional checkpoint/restart is incremental checkpointing, which has a number of known limitations. To address these limitations, we describe libhashckpt, a hybrid incremental checkpointing solution that uses both page protection and hashing on GPUs to determine changes in application data with very low overhead. Using real capability workloads and a model outlining the viability and application efficiency increase of this technique, we show that hash-based incremental checkpointing can have significantly lower overheads and increased efficiency than traditional coordinated checkpointing approaches at the scales expected for future extreme-class systems.     

基于残迹融合的高可用分布式导航算法

导航通信中断等问题经常导致电子地图中的自动寻路功能失效.为了实现分布式导航系统的有效容灾和寻路优化,提出了基于道路残迹数据融合的高可用分布式导航算法;给出了该算法的主要思想、算法模型、数据结构以及运行流程.该算法应用了蒙特卡罗方法进行道路可通行度评估;采用了2维叠加空间进行"道路信息-寻路需求"匹配方法.最后进行了算法效能分析与仿真.仿真实验结果证明,该算法具有较好的容灾性能、响应速度和较好的适应能力.     

综合化航电核心处理系统容错技术研究

当前航空电子系统是一个高度综合化、模块化的系统,作为其基础平台的核心处理计算机系统是一个综合数据处理、信号处理和图像处理的实时分布武计算机系统,可靠性要求很高,必须采用客错技术.文章在介绍实时分布武计算机系统硬件和软件结构的基础上,重点对容错技术进行了研究,提出了分层的容错管理策略,并通过具体实例说明了故障监控、故障处理和系统重构的方法.     

Fault-accommodation with intelligent sensors

Optimal sensor fault-accommodation is considered for faults modelled by an increase in measurement noise. This noise is taken to be bounded and its probabilistic properties unknown. It is assumed that intelligent (e.g. self-validating) instrumentation is in use and estimates of the noise bounds are available. The fault-tolerant controller is designed to optimize a noise rejection and a nominal reference tracking index and leads to a mixed norm minimization problem (l₁/l₂). We exploit known results and a particular feedback configuration to show that it is possible to optimize simultaneously without a trade-off the two performance indices. The results are applied to systems where the presence of auxiliary measurements allows for an optimal fault-accommodation strategy. Using properties of the optimal solution, we define a factorization for the optimal controller alternative to the Youla parametrization, leading to an algorithm which is optimal, transparent and efficient.     

Self-stabilizing depth-first token circulation on networks

Summary This paper proposes a self-stabilizing protocol which circulates a token on a connected network in nondeterministic depth-first-search order, rooted at a special node. Starting with any initial state in which the network may have no token at all or more than one token, the protocol eventually makes the system stabilize in states having exactly one circulating token. With a slight modification to the protocol —by removing nondeterminism in the search — a depth-first-search tree on the network can be constructed. The proposed protocol runs on systems that allow parallel operations. Shing-Tsaan Huang was born in Taiwan on September 4, 1949. He got his Ph.D. degree in 1985 from Department of Computer Science, University of Maryland at College Park. Before he pursued his Ph.D. degree, he had worked several years in the computer industry in Taiwan. Professor Huang is currently the chairman of the Department of Computer Science, Tsing Hua University, Taiwan, Republic of China. His research interests include interconnection networks, operating systems and distributed computing. He is a senior member of the IEEE Computer Society and a member of the Association for Computing Machinery. Nian-Shing Chen was born in Taiwan on October 21, 1961. He received his Ph.D. degree in computer science from National Tsing Hua University in 1990. Dr. Chen is currently an associate professor with the Department of Information Management at Sun Yat-Sen University of Taiwan. His research interests include distributed systems, computer networks, computer viruses and expert systems. He is a member of IEEE and Phi Tau Phi honorary society.This research is supported by National Science Council of the Republic of China under the contract NSC81-0408-E-007-05 and NSC82-0408-E-007-027     

Proactive resource allocation for asynchronous real-time distributed systems in the presence of processor failures

We present two proactive resource allocation algorithms, RBA^*-FT and OBA-FT, for fault-tolerant asynchronous real-time distributed systems. The algorithms consider an application model where task timeliness is specified by Jensen's benefit functions and the anticipated application workload during future time intervals is described by adaptation functions. In addition, we assume that reliability functions of processors are available a priori. Given these models, our objective is to maximize aggregate task benefit and minimize aggregate missed deadline ratio in the presence of processor failures. Since determining the optimal solution is computationally intractable, the algorithms heuristically compute sub-optimal resource allocations, but in polynomial time. Experimental results reveal that RBA^*-FT and OBA-FT outperform their non-fault-tolerant counterparts in the presence of processor failures. Furthermore, RBA^*-FT performs better than OBA-FT, although OBA-FT incurs better worst-case and amortized computational costs. Finally, we observe that both algorithms robustly withstand errors in the estimation of anticipated failures.     

An effective routing algorithm in incomplete hypercubes

An incomplete hypercube appears interesting and practical because of its relaxed restriction on the system size and possession of salient properties of complete hypercubes. The performance of incomplete hypercubes can be improved considerably by reducing communication time, which can be achieved by forwarding messages through two parallel paths between a pair of nodes. This paper presents a simple and effective two-parallel-paths routing algorithm for incomplete hypercubes which takes advantage of the flexibility provided by incomplete hypercubes, and yet prevents traffic congestion and deadlock. Simulation results indicate that the mean latency for sending large sized messages is reduced and the degree of reduction becomes larger when the system load grows. This significant reduction in latency could translate to a respectable performance improvement. This algorithm can also tolerate one fault in the system by sending duplicate copies of messages through two parallel paths with little increase in the mean latency under light-traffic load.