Performance of Multicast Communication on Hypercubes

Based upon hypercube multiprocessor systems,this paper analyses in detail the communication performance under the background of the greedy multicast algorithm GMA.The mean delay time of a message both at a node and in the system under multicasting is derived.For the sake of contrast,the delay of multicast message is compared with that of multiple one-to-one messages.     

Unicast-based multicast communication in wormhole-routed networks

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log ₂ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given     

Optimal broadcast in all-port wormhole-routed hypercubes

We give an optimal algorithm that broadcasts on an n-dimensional hypercube in O(n/ log₂ (n+1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of P.K. McKinley and C. Trefftz (1993) requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n ⩽7     

Near-optimal broadcast in all-port wormhole-routed hypercubes usingerror-correcting codes

A new broadcasting method is presented for hypercubes with wormhole routing mechanism. The communication model assumed allows an n-dimensional hypercube to have at most n concurrent 110 communications along its ports. It further assumes a distance insensitivity of (n+1) with no intermediate reception capability for the nodes along the communication path. The approach is based on determination of the set of nodes (called stations) in the hypercube such that for any node in the network there is a station at distance of at most 1. Once stations are identified, parallel disjoint paths are formed from the source to all stations. The broadcasting is accomplished first by sending the message to all stations which will in turn inform the rest of the nodes of the message. To establish node-disjoint paths between the source node and all stations, we introduce a new routing strategy. We prove that multicasting can be done in one routing step as long as the number of destination nodes are at most n in an n-dimensional hypercube. The number of broadcasting steps using our routing is equal to or smaller than that obtained in an earlier work; this number is optimal for all hypercube dimensions n⩽12, except for n=10     

A trip-based multicasting model in wormhole-routed networks withvirtual channels

This paper focuses on efficient multicasting in wormhole-routed networks. A trip-based model is proposed to support adaptive, distributed, and deadlock-free multiple multicast on any network with arbitrary topology using at most two virtual channels per physical channel. This model significantly generalizes the path-based model proposed earlier which works only for Hamiltonian networks and cannot be applicable to networks with arbitrary topology resulted due to system faults. Fundamentals of the trip-based model, including the necessary and sufficient condition to be deadlock-free, and the use of appropriate number of virtual channels to avoid deadlock are investigated. The potential of this model is illustrated by applying it to hypercubes with faulty nodes. Simulation results indicate that the proposed model can implement multiple multicast on faulty hypercubes with negligible performance degradation     

Fault-tolerant multicasting in hypercubes using local safety information

A fully unsafe hypercube according to the global safety can be split into a unique set of maximal safe subcubes. Multicasting in a maximal safe subcube can be completed reliably based on information related to the maximal safe subcube. A time-optimal multicasting exists if (1) the multicast source is locally safe in the minimum subcube that contains the source and destinations (called a multicast subcube), or (2) the spanning subcube between each destination and the source is safe. We show a sufficient condition for the existence of a multicasting is: the multicast subcube is safe or the spanning subcube between the source and each destination is either safe or is contained in a safe subcube. Methods are presented to set up a partial multicast tree when the above sufficient conditions fail. It is shown that effectiveness of the algorithm can be improved drastically using the partial multicast tree setup technique. Extensive simulation results are also presented.     

Maximizing the throughput of parallel jobs on hypercubes

We study a problem of scheduling n independent parallel jobs on hypercubes. A parallel job is required to be scheduled on a subcube of processors. All jobs are available at the beginning, each of which is associated with a due date. The objective is to maximize the total number of early jobs. We provide an optimal polynomial time algorithm for the unit processing time job system.     

A note on path bipancyclicity of hypercubes

In [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97], the authors showed that any path in an n-cube with length of k, 2k2n−4, lies on a cycle of every even length from 2k to 2ⁿ inclusive. Base on Lemma 5 of that paper, they proved the subcase 2.2.1 of the main theorem of that paper. However, the lemma is false, therefore, we propose a lemma to replace that lemma. Therefore, the main result of [C.H. Tsai, S.Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93–97] is still correct.     

Regular connected bipancyclic spanning subgraphs of hypercubes

An n-dimensional hypercube Q_n is a Hamiltonian graph; in other words Q_n (n≥2) contains a spanning subgraph which is 2-regular and 2-connected. In this paper, we explore yet another strong property of hypercubes. We prove that for any integer k with 3≤k≤n, Q_n (n≥3) contains a spanning subgraph which is k-regular, k-connected and bipancyclic. We also obtain the result that every mesh P_m×P_n (m,n≥2) is bipancyclic, which is used to prove the property above.     

A fault tolerant RPC mechanism based on IP multicasting

This paper presents a fault tolerant Remote Procedure Call (RPC) mechanism based on Sun RPC and IP multicast protocol. The fault tolerant RPC mechanism is provided as an RPC library, called libFTRPC, whose interface is compatible with that of conventional Sun's RPC library. Thanks to this compatibility, a reliable RPC server can be developed in the same way a conventional RPC server is constructed. The service reliability is ensured by replicating the server to a group of server replicas. Coordinator-cohort replication model in conjunction with read-one/write-all policy is used to guarantee state consistency between server replicas. We also incorporate a simple and effective approach to balance loads among server replicas to improve performance for read-only requests.     

Cycles embedding in hypercubes with node failures

The hypercube has been widely used as the interconnection network in parallel computers. The n-dimensional hypercube Qn is a graph having n² vertices each labeled with a distinct n-bit binary strings. Two vertices are linked by an edge if and only if their addresses differ exactly in the one bit position. Let fv denote the number of faulty vertices in Qn. For n?3, in this paper, we prove that every fault-free edge and fault-free vertex of Qn lies on a fault-free cycle of every even length from 4 to n²−2fv inclusive even if fv?n−2. Our results are optimal.     

Modeling and optimization of survivable P2P multicasting

Various solutions based on Peer-to-Peer (P2P) multicasting have been gaining much popularity in recent years, since P2P multicasting can effectively support live streaming of various content. In this work we assume that the P2P multicasting is used to distribute content with high reliability requirements, e.g., weather warnings, security updates, financial data, security warnings, etc. The main idea to provide protection of the system against network failures is to establish several (at least two) disjoint multicasting trees. Our discussion in this paper centers on the problem how additional survivability constraints to provide failure-disjoint trees impact the operation of P2P multicasting systems. As the performance metrics we propose to use: streaming cost, maximum delay and throughput. The possible failure scenario we take into account is a single failure of one of the following network elements: streaming server, overlay link, uploading node and ISP link. We examine the topic of survivable P2P multicasting applying offline optimization methods and simulations. In the former case we formulate Mixed Integer Programming (MIP) models and use the CPLEX solver to obtain optimal results. For the streaming cost objective we compare two MIP formulations in terms of the complexity and execution time. Results show that our formulation provides much better performance compared to the classical P2P multicasting formulation proposed in the literature. Moreover, in the case of the streaming cost problem we propose a new evolutionary algorithm that yields results for larger networks than the CPLEX solver. The simulations are run to emulate a distributed network environment, in which each node makes its own decisions. Results obtained using both research methods confirm that the survivability of P2P multicasting can be achieved with relatively low additional system overhead for all three considered performance metrics: streaming cost, maximum delay and system throughput.     

Edge-fault-tolerant diameter and bipanconnectivity of hypercubes

Let n(?3) be a given integer and . And let Qn be an n-dimensional hypercube and F⊂E(Qn), such that every vertex of the graph Qn−F is incident with at least two edges. Assume x and y are any two vertices with Hamming distance H(x,y)=h. In this paper, we obtain the following results: (1) If h?2 and |F|?min{n+h−1,2n−5}, then in Qn−F there exists an xy-path of each length l∈Ωh+2, and the upper bound n+h−1 on |F| is sharp when 2?h?n−4, and the upper bound 2n−5 on |F| is sharp when n−4?h?n−1 and h=2. (2) If |F|?2n−5, then in Qn−F there exists an xy-path of each length l∈Ωs, where s=h if n−1?h?n, and s=h+2 if n−4?h?n−2 and h?2, and s=h+4 otherwise. Hence, the diameter of the graph Qn−F is n. Our results improve some previous results.     

Robust fault-tolerant self-recovering control of nonlinear uncertain systems

In this paper, the problem of devising a fault-tolerant robust control for a class of nonlinear uncertain systems is investigated. Possible failures of the sensor measuring the state variables are considered, and a robust measure is developed to identify the stability- and performance-vulnerable failures. Based on evaluation of the robust measure, a fault-tolerant robust control will switch itself between one robust control strategy designed under normal operation and another under the faulty condition. It is shown that, under two input-to-state stability conditions, the proposed scheme guarantees not only the desired performance under normal operations but also robust stability and best achievable performance when there is a sensor failure of any kind.     

CoRAL: A transparent fault-tolerant web service

The Web is increasingly used for critical applications and services. We present a client-transparent mechanism, called CoRAL, that provides high reliability and availability for Web service. CoRAL provides fault tolerance even for requests being processed at the time of server failure. The scheme does not require deterministic servers and can thus handle dynamic content. CoRAL actively replicates the TCP connection state while maintaining logs of HTTP requests and replies. In the event of a primary server failure, active client connections fail over to a spare, where their processing continues seamlessly. We describe key aspects of the design and implementation as well as several performance optimizations. Measurements of system overhead, failover performance, and preliminary validation using fault injection are presented.     

A Fault-Tolerant and Heuristic Routing Algorithm for Faulty Hypercubes

A fault-tolerant and heuristic routing algorithm for faulty hypercube systems is described.To improve the efficiency,the algorithm adopts a heuristic backtracking strategy and each node has an array to record its all neighbors‘ faulty link information to avoid unnecessary searching for the known faulty links.Furthermore,the faulty link information is dynamically accumulated and the technique of heuristically searching for optimal link is used.The algorithm routes messages through the minimum feasible path between the sender and receiver if at least one such path exists,and takes the optimal path with higher probability when faulty links exist in the faulty hypercube.     

三维非线性自适应容错导引律设计

本文针对部分执行器失效情形下的三维鲁棒导引律设计问题,利用输入–状态稳定性原理,设计一种三维非线性自适应容错导引律.与已存在结果相比,所设计算法能够实现对部分执行器失效的自动补偿,并且具备克服机动目标未知机动性对制导效果的影响.理论分析和数值仿真验证了该算法的有效性,并且数值仿真还表明其能够恢复特定时间段内执行器完全失效时的系统稳定性,具有很强的鲁棒性.     

Preference-oriented real-time scheduling and its application in fault-tolerant systems

In this paper, we consider a set of real-time periodic tasks where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) while still meeting their deadlines. After introducing the idea of preference-oriented (PO) execution, we formally define the concept of PO-optimality. For fully-loaded systems (with 100% utilization), we first propose a PO-optimal scheduler, namely ASAP-Ensured Earliest Deadline (SEED), by focusing on ASAP tasks where the optimality of ALAP tasks’ preference is achieved implicitly due to the harmonicity of the PO-optimal schedules for such systems. Then, for under-utilized systems (with less than 100% utilization), we show the discrepancies between different PO-optimal schedules. By extending SEED, we propose a generalized Preference-Oriented Earliest Deadline (POED) scheduler that can obtain a PO-optimal schedule for any schedulable task set. The application of the POED scheduler in a dual-processor fault-tolerant system is further illustrated. We evaluate the proposed PO-optimal schedulers through extensive simulations. The results show that, comparing to that of the well-known EDF scheduler, the scheduling overheads of SEED and POED are higher (but still manageable) due to the additional consideration of tasks’ preferences. However, SEED and POED can achieve the preference-oriented execution objectives in a more successful way than EDF.     

液位传感器容错控制方法研究

传统的PID(比例-积分-微分)控制法在液位过程控制中占据主要地位,但由于液位控制系统,特别是其系统传感器容易发生故障,使得PID控制法具有抗故障能力不足的缺陷,对生产生活造成重大损失,因此需采用容错控制方法使得液位传感器发生故障时仍能较为正常运行,提出状态观测器估计传感器液位故障值的容错控制方法,使状态观测器对故障状态产生观测跟踪,将故障状态作用于原控制器,并使原控制器弃置已经存在故障的传感器信号,使得故障值被抵消。     

Edge-fault-tolerant vertex-pancyclicity of augmented cubes

The n-dimensional augmented cube, denoted as AQn, a variation of the hypercube, possesses some properties superior to those of the hypercube. In this paper, we show that every vertex in AQn lies on a fault-free cycle of every length from 3 to n², even if there are up to n−1 edge faults. We also show that our result is optimal.