Design of reliable SONET feeder networks

We address the physical SONET network design problem of selecting stackable, unidirectional rings connecting central office nodes (COs) and remote nodes (RNs). This problem frequently arises in designing feeder transport networks to support centralized traffic between the COs and RNs. We formulate a 0–1 programming model for this problem. A simulated annealing-based Lagrangian relaxation procedure to find optimal or near-optimal solutions is then described. Computational results are reported showing that our procedures produce solutions that are on average within 1.1% of optimality. We show that using simulated annealing to augment the pure Lagrangian approach produces superior solutions to the Lagrangian approach.     

Highly reliable message-passing mechanism for cluster file system

With the increase in personal computer clusters in popularity and quantity, message passing between nodes has been an important issue for high failure rate in the network. File access in a cluster file system often contains several sub-operations; each includes one or more network transmissions. Any network failures cause the file system service unavailable. In this paper, we describe a highly reliable message-passing mechanism (HR-NET), which tolerates both software and hardware network failures. HR-NET provides fine-grained, connection-level failover across redundant communication paths. With it, the file system can keep passing messages because HR-NET handles failures automatically by either recovery from network failures or failed over to a backup; therefore, it screens network failures from requests or data transmission of cluster file system. Load balance for messages is also achieved to relieve network traffic. For transmission timeout, HR-NET proposes a priority-based message scheduling which dynamically manages messages in an appropriate order to tolerate request–response failures between clients and servers. HR-NET is implemented upon standard network protocol stack. Performance results show that HR-NET can provide almost full underlying network bandwidth with average 6.17% throughput loss and provide a fast recovery. Experiments with cluster file system show that the overall performance degradation is below 8% due to failover of HR-NET while the reliability is highly enhanced.     

Efficient reliable communication over partially authenticated networks

Reliable communication between processors in a network is a basic requirement for executing any protocol. Dolev [7] and Dolev et al. [8] showed that reliable communication is possible if and only if the communication network is sufficiently connected. Beimel and Franklin [1] showed that the connectivity requirement can be relaxed if some pairs of processors share authentication keys. That is, costly communication channels can be replaced by authentication keys. In this work, we continue this line of research. We consider the scenario where there is a specific sender and a specific receiver in a synchronous network. In this case, the protocol of [1] has n^O(n) rounds even if there is a single Byzantine processor. We present a more efficient protocol with round complexity of (n/t)^O(t), where n is the number of processors in the network and t is an upper bound on the number of Byzantine processors in the network. Specifically, our protocol is polynomial when the number of Byzantine processors is O(1), and for every t its round complexity is bounded by 2^O(n). The same improvements hold for reliable and private communication. The improved protocol is obtained by analyzing the properties of a "communication and authentication graph" that characterizes reliable communication. Received: 13 January 2004, Accepted: 22 September 2004, Published online: 13 January 2005 A preliminary version of this paper appeared in [2].     

The problem of synthesis of reliable networks

The problem of determination of a throughput of network edges on an unidirected graph with a minimal total network cost is considered in the paper, provided that, if any edge is removed from the graph, ways exist along which a single flow goes from the source to the sink in the obtained network. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 145–156, July–August, 2000.     

The basics of reliable distributed storage networks

Because of storage protocols that operate over extended distances, various distributed storage applications that improve the efficiency and reliability of data storage are now possible. Distributed storage applications improve efficiency by allowing any network server to transparently consolidate and access data stored in multiple physical locations. Remote backup and mirroring improve the system's reliability by copying critical data. These processes improve efficiency by eliminating backup downtime and manual backup operations. Business continuity and disaster recovery capabilities enable enterprises to recover quickly and transparently from system failure or data loss. Storage protocols and gateway devices enable rapid and transparent data transfer between mainframe applications and open-systems applications. NAS applications provide shared file access for clients using standard LAN-based technology, and can integrate with SAN architectures to provide truly distributed network capabilities. All these distributed storage network applications enable IT managers to improve data availability and reliability while minimizing management overhead and costs.     

Network coding-based reliable multicast in wireless networks

Reliable multicast, the lossless dissemination of data from one sender to a group of receivers, has a wide range of important applications. Recently, network coding has been applied to the reliable multicast in wireless networks, where multiple lost packets with distinct intended receivers are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. However, the simple XOR operation cannot fully exploit the potential coding opportunities and finding the optimal set of lost packets for XOR-ing is a complex NP-complete optimization problem. In this work, we intend to move beyond the simple XOR to more general coding operations. Specifically, we propose two new schemes (a static scheme which repeatedly retransmits one coding packet until all intended receivers receive it and a dynamic scheme which updates the coding packet once one or more receivers receive it) to encode packets with more general coding operations, which not only can encode lost packets with common intended receivers together to fully exploit the potential coding opportunities but also have polynomial-time complexity. We demonstrate, through both analytical and simulation results, that the proposed schemes can more greatly reduce the bandwidth requirement than the available coding-based schemes, especially in the case of high packet loss probabilities and a larger number of receivers. This reduction can vary from a few percents to over 15% depending on the packet loss probabilities and the number of receivers.     

Highly reliable testing of ULSI memories with on-chip voltage-downconverters

Two testing techniques for ultra-large-scale integrated (ULSI) memories containing on-chip voltage downconverters (VDCs) are described. The first in an on-chip VDC tuning technique that adjusts internal V_CC to compensate for the monitored characteristics of the process parameters during repair analysis testing. The second is an operating-voltage margin test, performed at various internal V_CC levels during the water sort test (WT) and the final shipping test (FT)     

A reliable linear algebra library for transputer networks

This paper presents a collection of linear algebra subroutines for transputer networks. The developed pilot library is intended to form a basis of a complete parallel linear algebra library for validating computations, whose routines will deliver (as accurately as necessary) either the best possible result, or a corresponding inclusion based on controlled rounding and an optimal scalar product. So far, as a first step, we have produced code for interval arithmetic, scalar products and simple vector-matrix operations with maximum accuracy. For the solution of triangular systems and the LU decomposition of dense matrices, new versions of classical methods are implemented which allow the application of optimal scalar products as a single, invidisible operation and optimize the overlap of communication and computation. The library also contains routines for computing inclusions of unstructured, dense linear systems of equations. Network topology dependency is avoided in all numerical routines by the use of general communication routines. This way the user is able to work with different topologies like ring structures, binary trees and hypercubes.     

On the computational efficiency of symmetric neural networks

An open problem concerning the computational power of neural networks with symmetric weights is solved. It is shown that these networks possess the same computational power as general networks with asymmetric weights; i.e., these networks can compute any recursive function. The computations of these networks can be described as a minimmization process of a certain energy function; it is shown that for uninitialized symmetric neural networks this process presents a Σ₂-complete problem.     

Permitted and forbidden sets in symmetric threshold-linear networks

The richness and complexity of recurrent cortical circuits is an inexhaustible source of inspiration for thinking about high-level biological computation. In past theoretical studies, constraints on the synaptic connection patterns of threshold-linear networks were found that guaranteed bounded network dynamics, convergence to attractive fixed points, and multistability, all fundamental aspects of cortical information processing. However, these conditions were only sufficient, and it remained unclear which were the minimal (necessary) conditions for convergence and multistability. We show that symmetric threshold-linear networks converge to a set of attractive fixed points if and only if the network matrix is copositive. Furthermore, the set of attractive fixed points is nonconnected (the network is multiattractive) if and only if the network matrix is not positive semidefinite. There are permitted sets of neurons that can be coactive at a stable steady state and forbidden sets that cannot. Permitted sets are clustered in the sense that subsets of permitted sets are permitted and supersets of forbidden sets are forbidden. By viewing permitted sets as memories stored in the synaptic connections, we provide a formulation of long-term memory that is more general than the traditional perspective of fixed-point attractor networks. There is a close correspondence between threshold-linear networks and networks defined by the generalized Lotka-Volterra equations.     

Parameterized synthesis of self-stabilizing protocols in symmetric networks

Self-stabilization in distributed systems is a technique to guarantee convergence to a set of legitimate states without external intervention when a transient fault or bad initialization occurs. Recently, there has been a surge of efforts in designing techniques for automated synthesis of self-stabilizing algorithms that are correct by construction. Most of these techniques, however, are not parameterized, meaning that they can only synthesize a solution for a fixed and predetermined number of processes. In this paper, we report a breakthrough in parameterized synthesis of self-stabilizing algorithms in symmetric networks, including ring, line, mesh, and torus. First, we develop cutoffs that guarantee (1) closure in legitimate states, and (2) deadlock-freedom outside the legitimate states. We also develop a sufficient condition for convergence in self-stabilizing systems. Since some of our cutoffs grow with the size of the local state space of processes, scalability of the synthesis procedure is still a problem. We address this problem by introducing a novel SMT-based technique for counterexample-guided synthesis of self-stabilizing algorithms in symmetric networks. We have fully implemented our technique and successfully synthesized solutions to maximal matching, three coloring, and maximal independent set problems for ring and line topologies.     

A reliable model for global planning of mobile networks

In this paper, we propose a global model for WiMAX networks planning. This model represents the network planning problem and helps to solve it entirely without dividing it into several subproblems. The objective of the model is to minimize the cost of the network while maximizing its survivability. The model has been compared to a sequential model with the same constraints, which consists in solving the subproblems sequentially, and to a global model without reliability constraints. The results show that the proposed model performs on an average 25% better than the other models.     

一种无线传感器网络可靠拓扑的生成算法

在无线传感器网络（ WSNs）的应用中,网络中的节点需要将采集到的数据信息传送到汇聚节点,其信息传输的可靠性是十分重要的。然而,由于无线通信信道容易受到干扰和噪音的影响,极限情况时甚至可能造成数据传输失败,这对无线传感器网络的正常工作提出了极大挑战。针对上述问题,提出一种可靠拓扑的生成算法,通过该算法设计了一组可靠的路由拓扑,并通过仿真验证了其可靠性。     

A fast and reliable multi-sender algorithm for peer-to-peer networks

Due to special constraints in peer-to-peer (P2P) networks (such as bandwidth limitation) and because of their highly dynamic characteristics, a single node cannot provide a reliable multimedia stream to the receivers. Several multi-sender algorithms are proposed to reliably deliver a media stream to the receiver through the intrinsically unreliable P2P networks. Based on upload bandwidths and availability of peers as well as the bandwidths of the links connecting the senders and the receiver, PROMISE selects a set of active senders to maximize the expected bit-rate delivered to the receiver. By careful investigation of PROMISE, in this paper, we present why and how it deviates from finding the optimal solution. The proposed algorithm, we call IPROMISE, consistently provides a higher media quality to the receiver, with a computational complexity similar to PROMISE. We also introduce FastIPROMISE which provides the same quality as IPROMISE but requires much less computations. That is achieved by shrinking the search space.     

Rate-lifetime tradeoff for reliable communication in wireless sensor networks

The network lifetime and application performance are two fundamental, yet conflicting, design objectives in wireless sensor networks. There is an intrinsic tradeoff between network lifetime maximization and application performance maximization, the latter being often correlated to the rate at which the application can send its data reliably in sensor networks. In this paper we study this tradeoff by investigating the interactions between the network lifetime maximization problem and the rate allocation problem with a reliable data delivery requirement. Severe bias on the allocated rates of some sensor nodes may exist if only the total throughput of the sensor network is maximized, hence we enforce fairness on source rates of sensor nodes by invoking the network utility maximization (NUM) framework. To guarantee reliable communication, we adopt the hop-by-hop retransmission scheme. We formulate the network lifetime maximization and fair rate allocation both as constrained maximization problems. We characterize the tradeoff between them, give the optimality condition, and derive a partially distributed algorithm to solve the problem. Furthermore, we propose an approximation of the tradeoff problem using NUM framework, and derive a fully distributed algorithm to solve the problem.     

Low-cost and reliable mutual anonymity protocols in peer-to-peer networks

We present several protocols to achieve mutual communication anonymity between an information requester and a provider in a P2P information-sharing environment, such that neither the requester nor the provider can identify each other, and no other peers can identify the two communicating parties with certainty. Most existing solutions achieve mutual anonymity in pure P2P systems without any trusted central controls. Compared with two such representative ones, our protocols improve efficiency in two different ways. First, utilizing trusted third parties and aiming at both reliability and low-cost, we propose a group of mutual anonymity protocols. We show that with some limited central support, our protocols can accomplish the goals of anonymity, efficiency, and reliability. Second, we propose a mutual anonymity protocol which relies solely on self-organizations among peers without any trusted central controls. In this protocol, the returning path can be shorter than the requesting path. This protocol does not need to broadcast the requested file back to the requester so that the bandwidth is saved and efficiency is improved. In addition, this protocol does not need special nodes to keep indices of sharing files, thus eliminating the index maintenance overhead and the potential for inconsistency between index records and peer file contents. We have evaluated our techniques in a browser-sharing environment. We show that the average increase in response time caused by our protocols is negligible, and these protocols show advantages over existing protocols in a P2P system.     

Maximal selection in tandem networks with symmetric hearing range

We consider an infinite tandem network in which every node is capable of hearing its neighbors up to a given distancen. At any moment of time every node may contain in the top of its queue a message destined to one of its neighbors. This network can be used as a model for a microwave or optic link with many users. For small and largen we investigate the maximal selection of nodes in the network, for which their transmissions are collision-free. For a large hearing range we show that the upper bound on the maximal selection, which is found herein, is asymptotically achievable. For small hearing ranges we show that a greedy selection is better but not asymptotically optimal. We also specify a sequence of upper bounds which converge to the maximal throughput.     

Maximal selection in tandem networks with symmetric hearing range

We consider an infinite tandem network in which every node is capable of hearing its neighbors up to a given distancen. At any moment of time every node may contain in the top of its queue a message destined to one of its neighbors. This network can be used as a model for a microwave or optic link with many users. For small and largen we investigate the maximal selection of nodes in the network, for which their transmissions are collision-free. For a large hearing range we show that the upper bound on the maximal selection, which is found herein, is asymptotically achievable. For small hearing ranges we show that a greedy selection is better but not asymptotically optimal. We also specify a sequence of upper bounds which converge to the maximal throughput.This research was done while J. M. Jaffe was on leave at the IBM Israel Scientific Center.     

Fully symmetric swapped networks based on bipartite cluster connectivity

The class of swapped or OTIS (optical transpose interconnect system) networks, built of n copies of an n-node cluster by connecting node i in cluster j to node j in cluster i for i≠j, has been studied extensively. One problem with such networks is that node i of cluster i has no intercluster link. This slight asymmetry complicates a number of algorithms and hinders both theoretical investigations and practical pursuits, such as building parallel node-disjoint paths for fault tolerance. We introduce biswapped networks that are fully symmetric and have cluster connectivity very similar to swapped/OTIS networks. We derive basic topological parameters, present a simple distributed shortest-path routing algorithm, and point to a number of other interesting properties under investigation for biswapped networks.