基于扩展安全级的Torus网络容错路由算法研究

在存在故障结点的网络中如何设计最小容错路由是网络容错研究中的一个热点问题。以存在矩形故障块的二维Torus网络为例,将扩展安全级运用到Torus中,对于网络中任意一对结点,给出存在最小路径的充要条件;并且结合扩展安全级的概念,给出建立最小通路区的方法,并用实验验证了方法的可行性。研究为存在故障结点的Torus网络寻找最小容错路径提供了理论依据。     

Fault-tolerant routing in hypercube multicomputers using local safety information

This paper studies fault-tolerant routing for injured hypercubes using local safety information. It is shown that a minimum feasible path is always available if the spanning subcube that contains both source and destination is safe. The safety information outside the spanning subcube is applied only when derouting is needed. A routing scheme based on local safety information is proposed and the extra cost to obtain local safety information is comparable to the one based on global safety information. The proposed algorithm guarantees to find a minimum feasible path if the spanning subcube is contained in a maximal safe subcube and the source is locally safe in the maximal safe subcube. A new technique to set up a partial path is proposed based on local safety information when the above conditions are not met. Sufficient simulation results are provided to demonstrate the effectiveness of the method by comparing with the previous methods.     

A routing-table-based adaptive and minimal routing scheme on network-on-chip architectures

In this paper, we present a routing algorithm that combines the shortest path routing and adaptive routing schemes for NoCs. In specific, routing follows the shortest path to ensure low latency and low energy consumption. This routing scheme requires routing information be stored in a series of routing tables created at the routers along the routing path from the source to the destination. To reduce the exploration space and timing cost for selecting the routing path, a routing list and routing table for each node are created off-line. Routing table is updated on-line to reflect the dynamic change of the network status to avoid network congestion. To alleviate the high hardware implementation cost associated with the routing tables, a method to help reduce the size of the routing tables is also introduced. Compared to the existing routing algorithms, the experimental results have confirmed that the proposed algorithm has better performance in terms of routing latency and power consumption.     

Fault-tolerant routing in mesh architectures

It is important for a distributed computing system to be able to route messages around whatever faulty links or nodes may be present. We present a fault-tolerant routing algorithm that assures the delivery of every message as long as there is a path between its source and destination. The algorithm works on many common mesh architectures such as the torus and hexagonal mesh. The proposed scheme can also detect the nonexistence of a path between a pair of nodes in a finite amount of time. Moreover, the scheme requires each node in the system to know only the state (faulty or not) of each of its own links. The performance of the routing scheme is simulated for both square and hexagonal meshes while varying the physical distribution of faulty components. It is shown that a shortest path between the source and destination of each message is taken with a high probability, and, if a path exists, it is usually found very quickly     

A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes

In this paper we propose a sufficient codition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes,It is based on an early work of the author on minial routing in 2-dimensional(2-D) meshes,Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information,our approach is based on the concept of limited global fault information,First,we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes.Fault information is then distributed to limited number of nodes while it is still sufficeint to support minimal routing.The limited fault information collcted at each node is represented by a vector caaled extended safety level.The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination .Specifically,we study the existence of minimal paths at a given source node,limited distribution of fault information,minimal routing,and deadlock-free and livelock-free routing.our results show that any minimal routing that is partially adaptive can be applied in our model as long as the dstination node meets a certain conditon.We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes.Our approach is the first attempt to address adaptive and minimal routing is 3-D meshes with faulty nodes using limited fault information.     

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.     

Fault-tolerant adaptive routing under an unconstrained set of node and link failures for many-core systems-on-chip

An online fault tolerant routing algorithm for 2D mesh Networks-on-Chip is presented in this work. It combines an adaptive routing algorithm with neighbor fault-awareness and a new traffic-balancing metric. To be able to cope with runtime permanent and temporary failures that may result in message corruption, message loss or deadlocks, the routing algorithm is enhanced with packet retransmission and a new message recovery scheme.     

Fault-tolerant control of linear systems using adaptive virtual actuator

In this paper, design and development of fault-tolerant control (FTC) is investigated for linear systems subject to loss of effectiveness and time-varying additive actuator faults as well as an external disturbance using the fault-hiding approach. The main aim of this approach is to keep the nominal controller and to design a virtual actuator that is inserted between the faulty plant and the nominal controller in order to hide actuator faults and disturbances from the nominal controller, and consequently the performance of the system before and after the occurrence of actuator faults is kept to be the same. The proposed adaptive virtual actuator does not require a separated fault detection, isolation and identification (FDII) unit and both state and output feedback cases are considered. An illustrative example is given to demonstrate the effectiveness of the proposed adaptive virtual actuator in both cases.     

Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.     

Improving routing protocol performance in delay tolerant networks using extended information

Delay tolerant networks (DTNs) are wireless mobile networks that do not guarantee the existence of a path between a source and a destination at any time. When two nodes move within each other’s transmission range during a period of time, they can contact each other. The contact of nodes can be periodical, predictable and nonpredictable. In this paper, we assume the contact of nodes is nonpredictable so that it can reflect the most flexible way of nodes movement. Due to the uncertainty and time-varying nature of DTNs, routing poses special challenges. Some existing schemes use utility functions to steer the routing in the right direction. We find that these schemes do not capture enough information of the network. Thus, we develop an extended information model that can capture more mobility information and use regression functions for data processing. Experimental results from both our own simulator and real wireless trace data show that our routing algorithms based on the extended information model can increase the delivery ratio and reduce the delivery latency of routing compared with existing ones.     

Fault-tolerant high-capacity quantum key distribution over a collective-noise channel using extended unitary operations

We propose two fault-tolerant high-capacity quantum key distribution schemes, in which an entangled pair over a collective-noise channel consisting of one logical qubit and one physical qubit can carry four bits of key information. The basic idea is to use 2-extended unitary operations from collective noises together with quantum dense coding. The key messages are encoded on logical qubits of two physical qubits with sixteen 2-extended unitary operations based on collective noises. The key can be recovered using Bell-state analysis on the logical qubit and a single-photon measurement on the physical qubit rather than three-qubit GHZ joint measurements. The proposed protocols require a collation table to be shared between Alice and Bob in advance. Consequently, the key messages carried by an entangled state, in our protocol, have doubled at the price of sharing the collation table between Alice and Bob. However, the efficiency of qubits is enhanced because a quantum bit is more expensive to prepare than a classical bit.     

Fully adaptive minimal deadlock-free packet routing in hypercubes,meshes, and other networks: algorithms and simulations

This paper deals with the problem of packet-switched routing in parallel machines. Several new routing algorithms for different interconnection networks are presented. While the new techniques apply to a wide variety of networks, routing algorithms will be shown for the hypercube, the two-dimensional mesh, and the shuffle-exchange. Although the new techniques are designed for packet routing, they can be used alternatively for virtual cut-through routing models. The techniques presented for hypercubes and meshes are fully-adaptive and minimal. A fully-adaptive and minimal routing is one in which all possible minimal paths between a source and a destination are of potential use at the time a message is injected into the network. Minimal paths followed by messages ultimately depend on the local congestion encountered in each node of the network. All of the new techniques are completely free of deadlock situations     

Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networks

This paper presents a fault-tolerant routing methodology for both injured hypercube and cube-connected cycles interconnection topologies. The proposed routing methodology efficiently tolerates any pattern of faulty regions with any number of faulty nodes in the network which is based on the best-first search and backtracking strategy. Deadlock freedom of the proposed routing methodology is obtained by only one virtual channel per physical channel. In order to evaluate the proposed routing methodology, a 7-dimensional hypercube network is simulated in various conditions, i.e., different traffic rates, different number of faulty nodes and different message lengths. Simulation results confirm that the proposed routing methodology in comparison with the previous methods provides acceptable performance while it significantly increases the reliability of the network. It also guarantees delivery of messages between any pair of source and destination while the network is connected.     

Fault-tolerant wormhole routing in mesh with overlapped solid fault regions

A fault-tolerant wormhole routing algorithm on mesh-connected processors is proposed. The proposed algorithm is based on the solid fault model and allows the fault polygons to be overlapped. The algorithm utilizes the position of fault region relative to the current channel to route a message around overlapped fault polygons. A node deactivating algorithm to convert a non-solid fault region into a solid fault region is also proposed. The proposed routing algorithm uses four virtual channels and is deadlock- and livelock-free.     

采用双状态传播卡方检验和模糊自适应滤波的容错组合导航算法

太阳能高空长航时无人机导航系统中,捷联惯导/北斗2κ全球卫星导航/星光导航(SINS/BD2/GPS/CNS)是一种可用的组合方案.针对常规容错组合导航算法故障检测类型单一,故障时滤波精度下降的问题,提出一种采用双状态卡方检验(TSPCST)和模糊自适应滤波(FAF)的容错组合导航算法.为了同时检测多种故障,将TSPCST应用于联邦滤波结构中;为了防止故障数据污染系统,利用FAF输出的高精度导航信息,对双状态传播器定期交替校正;进一步,FAF运用TSPCST检测得到的故障信息变量,定义量测子系统模糊有效域,将检测阈值模糊化,以弥补常规固定检测阈值算法难以选取阈值的不足;最后,通过计算信息分配因子,自适应处理多种故障数据.仿真结果表明,该容错组合导航算法性能优于常规固定检测阈值算法.     

Online linear optimization and adaptive routing

This paper studies an online linear optimization problem generalizing the multi-armed bandit problem. Motivated primarily by the task of designing adaptive routing algorithms for overlay networks, we present two randomized online algorithms for selecting a sequence of routing paths in a network with unknown edge delays varying adversarially over time. In contrast with earlier work on this problem, we assume that the only feedback after choosing such a path is the total end-to-end delay of the selected path. We present two algorithms whose regret is sublinear in the number of trials and polynomial in the size of the network. The first of these algorithms generalizes to solve any online linear optimization problem, given an oracle for optimizing linear functions over the set of strategies; our work may thus be interpreted as a general-purpose reduction from offline to online linear optimization. A key element of this algorithm is the notion of a barycentric spanner, a special type of basis for the vector space of strategies which allows any feasible strategy to be expressed as a linear combination of basis vectors using bounded coefficients.We also present a second algorithm for the online shortest path problem, which solves the problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs slightly better than the first, as measured by their additive regret.     

无线传感器网络分层带宽自适应路由协议

在无线传感器网络(WSNs)中,节点能量使用严格受限,限制了网络的使用寿命。固定环带宽度的分层路由协议是一种有效的解决方法。在此基础上,提出了一种引入环带宽度自适应调整的路由机制。该机制根据节点剩余能量和传输数据能耗自动调整环带宽度,并决定节点是否参与网内数据报文的传输。采用Matlab作为仿真工具对该路由机制进行了仿真分析,结果表明:该算法通过调整环带宽度的方式能够有效延长网络使用寿命和维持网内负载均衡。     

车辆网络中一种有效自适应的复制路由协议

已经提出的一些基于复制的路由协议,如传染路由,不能以低代价实现高成功率.对车辆网络中设计了一种有效的基于复制的路由协议ARR.ARR是一种完全分布式协议,它包含两个设计目标:a)在消息生存期内将绝大多数消息成功发送;b)尽可能产生较低的发送代价.为了以低代价实现高成功率,ARR对一条消息的拷贝数量采取自适应策略.另外,为分配消息拷贝提出了两种分配方法.基于真实车辆行驶数据的仿真实验表明,相比其他四种路由协议,ARR以较低的发送代价实现了较高的发送成功率.     

A general theory for deadlock-free adaptive routing using a mixedset of resources

This paper presents a theoretical framework for the design of deadlock-free fully adaptive routing algorithms for a general class of network topologies and switching techniques in a single, unified theory. A general theory is proposed that allows the design of deadlock avoidance-based as well as deadlock recovery-based wormhole and virtual cut-through adaptive routing algorithms that use a homogeneous or a heterogeneous (mixed) set of resources. The theory also allows channel queues to be allocated nonatomically, utilizing resources efficiently. A general methodology for the design of fully adaptive routing algorithms applicable to arbitrary network topologies is also proposed. The proposed theory and methodology allow the design of efficient network routers that require minimal resources for handling infrequent deadlocks     

A novel minimal distortion-based edge adaptive image steganography scheme using local complexity

Multimedia Tools and Applications - The advantage of spatial domain image steganography techniques is their capacity to embed high payloads of data by directly modifying image pixels. While these...