Cooperative Recovery of Distributed Storage Systems from Multiple Losses with Network Coding

This paper studies the recovery from multiple node failures in distributed storage systems. We design a mutually cooperative recovery (MCR) mechanism for multiple node failures. Via a cut-based analysis of the information flow graph, we obtain a lower bound of maintenance bandwidth based on MCR. For MCR, we also propose a transmission scheme and design a linear network coding scheme based on (η, κ) strong-MDS code, which is a generalization of (η, κ) MDS code. We prove that the maintenance bandwidth based on our transmission and coding schemes matches the lower bound, so the lower bound is tight and the transmission scheme and coding scheme for MCR are optimal. We also give numerical comparisons of MCR with other redundancy recovery mechanisms in storage cost and maintenance bandwidth to show the advantage of MCR.     

On the path-loss attenuation regime for positive cost and linear scaling of transport capacity in wireless networks

Wireless networks with a minimum inter-node separation distance are studied where the signal attenuation grows in magnitude as 1/ρ/sup δ/ with distance ρ. Two performance measures of wireless networks are analyzed. The transport capacity is the supremum of the total distance-rate products that can be supported by the network. The energy cost of information transport is the infimum of the ratio of the transmission energies used by all the nodes to the number of bit-meters of information thereby transported. If the phases of the attenuations between node pairs are uniformly and independently distributed, it is shown that the expected transport capacity is upper-bounded by a multiple of the total of the transmission powers of all the nodes, whenever δ>2 for two-dimensional networks or δ>5/4 for one-dimensional networks, even if all the nodes have full knowledge of all the phases, i.e., full channel state information. If all nodes have an individual power constraint, the expected transport capacity grows at most linearly in the number of nodes due to the linear growth of the total power. This establishes the best case order of expected transport capacity for these ranges of path-loss exponents since linear scaling is also feasible. If the phases of the attenuations are arbitrary, it is shown that the transport capacity is upper-bounded by a multiple of the total transmission power whenever δ>5/2 for two-dimensional networks or δ>3/2 for one-dimensional networks, even if all the nodes have full channel state information. This shows that there is indeed a positive energy cost which is no less than the reciprocal of the above multiplicative constant. It narrows the transition regime where the behavior is still open, since it is known that when δ<3/2 for two-dimensional networks, or δ<1 for one-dimensional networks, the transport capacity cannot generally be bounded by any multiple of the     

End-to-end delay in wireless random networks

The focus of this letter is to derive a scaling law for the ene-to-end delay of wireless random networks under node mobility, where n nodes randomly move with the speed of v. To that end, we apply the cover time analysis and relate it to the delay scaling law. As a result, we derive that the mean delay per S-D pair as θ(n) or θ(√n÷v), and the worst case delay is θ(n log n) or θ(√log n÷v), corresponding to one slot time length that is either constant or 1÷v√n .     

Adding sense of spatial locality to routing protocols for mobile ad hoc networks

Recently, there has been an increasing interest in mobile ad hoc networks. In a mobile ad hoc network, each mobile node can freely move around and the network is dynamically constructed by collections of mobile nodes without using any existing network infrastructure. Compared to static networks, it faces many problems such as the inefficiency of routing algorithms. Also, the number of control packets in any routing algorithm increases as the mobile speed or the number of mobile nodes increases. Most of the current routing protocols in ad hoc networks broadcast the control packets to the entire network. Therefore, by reducing the number of control packets, the efficiency of the network routing will be improved. If we know where the destination is, we can beam our search toward that direction. However, without using global positioning systems, how can we do this? Define the range nodes as the 1‐hop or 2‐hop neighbors of the destination node. In this paper, we propose using the range nodes to direct our searches for the destination. It can be combined with the existing routing protocols to reduce the control overhead. We show through simulations that AODV and DSR combined with the range node method outperforms the original AODV and DSR routing protocols in terms of control packets overhead. We also show that the delay introduced in find range nodes is insignificant. Copyright © 2006 John Wiley & Sons, Ltd.     

Packet-centric approach to distributed sparse-graph coding in wireless ad hoc networks

In this paper we present a packet-centric approach for distributed coding in decentralized wireless ad hoc networks, for applications in distributed data storage, data persistence and efficient data gathering. We study the setting where each of N network nodes generates an information packet and the goal is to efficiently encode information packets and disseminate produced encoded packets across the network in such fashion that gathering of any subset of slightly more than N encoded packets allows for retrieval of the original information. The process of distributed encoding is performed using packets that randomly walk over the network and sample information packets from network nodes, producing the encoded packets in a simple, elegant, fully decentralized and stateless way. The proposed scheme maintains properties of centralized codes in terms of performance parameters, offering at the same time advantage of robustness to node failures and changes in network topology. We specialize the proposed scheme for several important classes of low-complexity encodable/decodable sparse-graph codes – LDGM, LDPC (IRA), LT, and Raptor codes, evaluating its performance via simulation for various data-gathering scenarios.     

Expected interference in wireless networks with geometric path loss: a closed-form approximation

In this letter, we derive 2λπP/((α - 2)g^{(α - 2)} as a closed-form approximation of the expected interference around a receiver in wireless networks. We use a geometric path loss model, assume that nodes are randomly distributed, and that only nodes outside a guard zone around the receiver simultaneously transmit. The derived solution depends on the path loss exponent α, node density λ, transmission power per node P, and the radius g of the guard zone. The simplicity of this solution makes it widely applicable in wireless network analysis.     

Routing with Guaranteed Delivery in Ad Hoc Wireless Networks

We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some fixed unit. We describe the first distributed algorithms for routing that do not require duplication of packets or memory at the nodes and yet guarantee that a packet is delivered to its destination. These algorithms can be extended to yield algorithms for broadcasting and geocasting that do not require packet duplication. A byproduct of our results is a simple distributed protocol for extracting a planar subgraph of a unit graph. We also present simulation results on the performance of our algorithms.     

A Class of Decentralized Routing Algorithms Using Relaxation

An important problem in packet-switched communication networks is the optimal assignment of routes to the message packets. An optimal routing assignment is one which chooses network paths for the packets in a way that minimizes some cost function, typically average message delay. A class of optimal routing algorithms is described which utilize a type of iterative computation known as relaxation. Computation is decentralized in the sense that each node computes its routing strategy using only information supplied from adjacent nodes. Being iterative, the algorithms are inherently adaptive. The routing computation is based conceptually on an electrical network analog for the optimization problem. We show that a simple, convergent relaxation procedure can be used to "solve" the analog network, thereby yielding the optimal routing strategy. A simple example is presented to illustrate the method. In general, the computational load compares favorably with other (centralized) methods, although further work is needed to obtain quantitive comparisons in specific cases.     

Optimal Unicast Capacity of Random Geometric Graphs: Impact of Multipacket Transmission and Reception

We establish a tight max-flow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-sparsity scale as θ(n²r³(n)/k), for a random choice of k = ω(n) source-destination pairs, where n and r(n) are the number of nodes and the communication range in the network respectively. The MCF equals the interference-free capacity of an ad-hoc network. We exploit this fact to develop novel graph theoretic techniques that can be used to deduce tight order bounds on the capacity of ad-hoc networks. We generalize all existing capacity results reported to date by showing that the per-commodity capacity of the network scales as θ(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as θ(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of (perfect) multiple-packet transmission (MPT) and reception (MPR), then it is feasible to achieve the optimal scaling of θ(n²r³(n)/k), despite the presence of interference. In comparison to the Gupta-Kumar model, the realization of MPT and MPR may require the deployment of a large number of antennas at each node or bandwidth expansion. Nevertheless, in stark contrast to the existing literature, our analysis presents the possibility of actually increasing the capacity of ad-hoc networks with n even while the communication range tends to zero!     

Scheduling algorithms for shared fiber-delay-line optical packet Switches-part I: the single-stage case

In all-optical packet switching, packets may arrive at an optical switch in an uncoordinated fashion. When contention occurs, fiber delay lines (FDLs) are needed to delay (buffer) the packets that have lost the contention to some future time slots for the desired output ports. There have been several optical-buffered switch architectures and FDL assignment algorithms proposed in the literature. However, most of them either have high implementation complexity or fail to schedule in advance departure time for the delayed packets. This paper studies the packet scheduling algorithms for the single-stage shared-FDL optical packet switch. Three new FDL assignment algorithms are proposed, namely sequential FDL assignment (SEFA), multicell FDL assignment (MUFA), and parallel iterative FDL assignment (PIFA) algorithms for the switch. The proposed algorithms can make FDLs and output-port reservation so as to schedule departure time for packets. Owing to FDL and/or output-port conflicts, the packets that fail to be scheduled are discarded before entering the switch so that they do not occupy any FDL resources. It is shown by simulation that with these algorithms, the optical-buffered switch can achieve a loss rate of /spl sim/10/sup -7/ even at the load of 0.9. These algorithms are extended to the three-stage Clos-Network optical packet switches in the companion paper.     

A secure wireless mission critical networking system for unmanned aerial vehicle communications

A privacy-preserving secure communication in ad hoc (without infrastructure) mission critical wireless networking system suitable for unmanned aerial vehicle communication systems is introduced and analyzed. It is expected that in a critical condition, few ad hoc (without infrastructure) mission critical wireless networking systems will work together. To make the simple and low cost privacy-preserving secure communication among the same network, each transmitting mobile node generates packets in such a way that its wanted receiving mobile nodes can read the message packets easily. On the other hand, the unwanted receiving mobile nodes from other networks cannot read those message packets. In addition, the unwanted receiving mobile nodes receive ‘jamming packets’ if they try to read them. This mechanism prevents the malicious receivers (readers from other networks) from reading the packets and obtaining information from this network. Results show that the throughput is very high and does not detect any jamming packets, if the receiving nodes of a network try to read packets transmitted by the nodes from the same networks.     

Efficient algorithms for performing packet broadcasts in a meshnetwork

A common task for network protocols is the broadcasting of information from one node to the rest of the nodes in the network. This task is often required during the execution of parallel algorithms in a network of processors, or other situations where the nodes of a mesh network generate packets to be broadcast at random time instances. We consider processors communicating over a mesh network with the objective of broadcasting information among each other. One instance of the problem involves a number of nodes all with the same message to be broadcasted. For that problem, a lower-bound on the time to complete the broadcast, and an algorithm which achieves this bound are presented. In another instance, every node in the mesh has packets to be broadcast arriving independently, according to a Poisson random process. The stability region for performing such broadcasts is characterized, and broadcast algorithms which operate efficiently within that region are presented. These algorithms involve interacting queues whose analysis is known to be very difficult. Toward that end we develop an approximation which models an n-dimensional infinite Markov chain as a single-dimensional infinite Markov chain together with an n-dimensional finite Markov chain. This approximate model can be analyzed and the results compare favorably with simulation     

Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |E_J| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |E_J|, one would need to perform the direct enumeration of error patterns with weight ι ⩽ J. The complexity of enumeration increases exponentially with J, essentially as η^J, where η is the code block length. This limits the application of direct enumeration to codes with small η and J. In this letter, we approximate J and |E_J | by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.     

Multidomain Network Based on Programmable Networks: Security Architecture

This paper proposes a generic security architecture designed for a multidomain and multiservice network based on programmable networks. The multiservice network allows users of an IP network to run programmable services using programmable nodes located in the architecture of the network. The programmable nodes execute codes to process active packets, which can carry user data and control information. The multiservice network model defined here considers the more pragmatic trends in programmable networks. In this scenario, new security risks that do not appear in traditional IP networks become visible. These new risks are as a result of the execution of code in the programmable nodes and the processing of the active packets. The proposed security architecture is based on symmetric cryptography in the critical process, combined with an efficient manner of distributing the symmetric keys. Another important contribution has been to scale the security architecture to a multidomain scenario in a single and efficient way.     

LHAP: A lightweight network access control protocol for ad hoc networks

Most ad hoc networks do not implement any network access control, leaving these networks vulnerable to resource consumption attacks where a malicious node injects packets into the network with the goal of depleting the resources of the nodes relaying the packets. To thwart or prevent such attacks, it is necessary to employ authentication mechanisms to ensure that only authorized nodes can inject traffic into the network. We propose LHAP, a hop-by-hop authentication protocol for ad hoc networks. LHAP resides in between the network layer and the data link layer, thus providing a layer of protection that can prevent or thwart many attacks from happening, including outsider attacks and insider impersonation attacks. Our detailed performance evaluation shows that LHAP incurs small performance overhead and it also allows a tradeoff between security and performance.     

TDMA scheduling algorithms for wireless sensor networks

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.     

Conflict multiplicity estimation and batch resolution algorithms

The standard model of a multiple-access channel with ternary feedback is considered. When packets of a batch of k nodes initially collide, it is assumed that no a priori statistical information about k is available. An algorithm is presented and analyzed that enables the nodes to compute a statistical estimate of k. Combining the estimation procedure with tree algorithms leads to batch-resolution algorithms that resolve conflicts more efficiently than any other reported to date. Both complete-resolution and partial-resolution algorithms are presented     

Prevention of deadlocks and livelocks in lossless backpressured packet networks

No packets will be dropped inside a packet network, even when congestion builds up, if congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity-stopping them from forwarding more packets until enough buffer becomes available. While there are potential advantages in backpressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network or part of the network goes to zero (i.e., no packets are transmitted). In this paper, we describe a simple, lossless method of preventing deadlocks and livelocks in backpressured packet networks. In contrast with prior approaches, our proposed technique does not introduce any packet losses, does not corrupt packet sequence, and does not require any changes to packet headers. It represents a new networking paradigm in which internal network losses are avoided (thereby simplifying the design of other network protocols) and internal network delays are bounded.     

Data aggregation in sensor networks using learning automata

One way to reduce energy consumption in wireless sensor networks is to reduce the number of packets being transmitted in the network. As sensor networks are usually deployed with a number of redundant nodes (to overcome the problem of node failures which is common in such networks), many nodes may have almost the same information which can be aggregated in intermediate nodes, and hence reduce the number of transmitted packets. Aggregation ratio is maximized if data packets of all nodes having almost the same information are aggregated together. For this to occur, each node should forward its packets along a path on which maximum number of nodes with almost the same information as the information of the sending node exist. In many real scenarios, such a path has not been remained the same for the overall network lifetime and is changed from time to time. These changes may result from changes occurred in the environment in which the sensor network resides and usually cannot be predicted beforehand. In this paper, a learning automata-based data aggregation method in sensor networks when the environment’s changes cannot be predicted beforehand will be proposed. In the proposed method, each node in the network is equipped with a learning automaton. These learning automata in the network collectively learn the path of aggregation with maximum aggregation ratio for each node for transmitting its packets toward the sink. To evaluate the performance of the proposed method computer simulations have been conducted and the results are compared with the results of three existing methods. The results have shown that the proposed method outperforms all these methods, especially when the environment is highly dynamic.     

A dynamic threshold based approach for mitigating black-hole attack in MANET

Mobile ad-hoc network is an infrastructure less type of network which does not require any kind of fixed infrastructure. It provides multi-hop communication between the source and destination nodes which are not within the direct range of each other through the intermediate nodes. These intermediate nodes cooperate with other nodes in finding an optimum and shortest route toward the destination. However, in holistic environments, some nodes do not cooperate with other nodes in finding the optimal route towards the destination and intentionally give the false route information of having the shortest path toward the destination with a high destination sequence number in order to attract the traffic toward itself and start dropping of the data packets instead of forwarding it. This type of routing misbehaviour is generally called as black hole attack or full packet dropping attack which is one of the most severe destructive attacks that lead to the network degradation. In this paper, we have proposed a protocol called as Mitigating Black Hole effects through Detection and Prevention (MBDP-AODV) based on a dynamic threshold value of the destination sequence number. In order to validate the efficiency of proposed protocol, the NS-2.35 simulator is used. The simulation results show that proposed protocol performs better as compared with existing one under black hole attack.