Distributed storage of data files in different nodes of a network enhances its fault tolerance capability by offering protection against node and link failures. Reliability is often achieved through redundancy in one of the following two ways: (i) storage of multiple copies of the entire file at different locations (nodes) or (ii) storage of file segments (not entire files) at different node locations. In the file distribution scheme, file segments from a file are created in such a way that it is possible to reconstruct the entire file, just by accessing any segments. For the reconstruction scheme to work, it is essential that the segments of the file are stored in nodes that are connected in the network. However, in the event of node/link failures, the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially correlated or region based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The first goal of this research is to design a least cost file storage scheme to ensure that no matter which region is destroyed; resulting in fragmentation of the network, a largest connected component of the residual network will have enough file segments with which to reconstruct the entire file. In case the least cost to ensure this objective is within the allocated budget, the storage design will be all region fault‐tolerant (ARFT). In case the least cost exceeds the allocated budget, design of an ARFT file storage system design is impossible. The second goal of this research is to design file storage schemes that will be maximum region fault‐tolerant within the allocated budget. The third goal of this research is to investigate the impact of the coding parameters and on storage requirements for ensuring all region or \textit{maximum region} fault‐tolerant design. We provide maximum region fault‐tolerant design. We provide approximation algorithms for the problems and evaluate their performance through simulation using two real networks and compare their results to the optimal solutions obtained using Integer Linear Program. The simulation results demonstrate that the approximation algorithms almost always produce near optimal results in a fraction of the time needed to find the optimal solution. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 380–395 2015

The orthogonal frequency division multiplexing (OFDM) technology provides an opportunity for efficient resource utilization in optical networks. It allows allocation of multiple sub-carriers to meet traffic demands of varying size. Utilizing OFDM technology, a spectrum efficient and scalable optical transport network called SLICE was proposed recently. The SLICE architecture enables sub-wavelength, super-wavelength resource allocation and multiple rate data traffic that results in efficient use of spectrum. However, the benefit is accompanied by additional complexities in resource allocation. In SLICE architecture, in order to minimize utilized spectrum, one has to solve the routing and spectrum allocation (RSA) problem, a generalization of the routing and wavelength allocation (RWA) problem. In this paper, we focus our attention to the on-line version of RSA problem and provide an algorithm for the ring network with a competitive ratio of min{O(log(dmax)), O(log(k))} where k is the total number of requests and dmaxis the maximum demand in terms of the number of sub-carriers. Moreover, we provide a heuristic for the network with arbitrary topology and measure the effectiveness of the heuristic with extensive simulation.

The orthogonal frequency division multiplexing (OFDM) technology provides an opportunity for efficient resource utilization in optical networks. It allows allocation of multiple sub-carriers to meet traffic demands of varying size. Utilizing OFDM technology, a spectrum efficient and scalable optical transport network called SLICE was proposed recently. The SLICE architecture enables sub-wavelength, super-wavelength resource allocation and multiple rate data traffic that results in efficient use of spectrum. However, the benefit is accompanied by additional complexities in resource allocation. In SLICE architecture, in order to minimize the utilized spectrum, one has to solve the routing and spectrum allocation problem (RSA). In this paper, we focus our attention to RSA and (i) prove that RSA is NP-complete even when the optical network topology is as simple as a chain or a ring, (ii) provide approximation algorithms for RSA when the network topology is a binary tree or a ring, (iii) provide a heuristic for the network with arbitrary topology and measure the effectiveness of the heuristic with extensive simulation. Simulation results demonstrate that our heuristic significantly outperforms several other heuristics proposed recently for RSA.

It has been observed that individuals' decisions to adopt a product or innovation are often influenced by the recommendations of their friends and acquaintances. Motivated by this observation, the last few years have seen a number of studies on influence maximization in social networks. The primary goal of these studies is identification of k most influential nodes in a network. A major limitation of these studies is that they focus on a non-adversarial environment, where only one player is engaged in influencing the nodes. However, in a realistic scenario multiple players attempt to influence the nodes in a competitive fashion. The proposed model considers a competitive environment where a node that has not yet adopted an innovation, can adopt only one of the several competing innovations and once it adopts an innovation, it does not switch. The paper studies the scenario where the first player has already chosen a set of k nodes and the second player, with the knowledge of the choice of the first, attempts to identify a smallest set of nodes (excluding the ones already chosen by the first) so that when the influence propagation process ends, the number of nodes influenced by the second player is larger than the number of nodes influenced by the first.

Distributed storage of data files in different nodes of a network enhances the reliability of the data by offering protection against node failure. In the (N,K),N ≥ K file distribution scheme, from a file F of size |F|, N segments of size |F|/K are created in such a way that it is possible to reconstruct the entire file, just by accessing any K segments. For the reconstruction scheme to work it is essential that the K segments of the file are stored in nodes that are connected in the network. However in case of node failures the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially-correlated or region-based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The goal of this research is to devise a file segment distribution scheme so that, even if the network becomes disconnected due to any region fault, at least one of the largest connected components will have at least K distinct file segments with which to reconstruct the entire file. The distribution scheme will also ensure that the total storage requirement is minimized. We provide an optimal solution through Integer Linear Programming and an approximation solution with a guaranteed performance bound of O(ln n) to solve the problem for any arbitrary network. The performance of the approximation algorithm is evaluated by simulation on two real networks.

Robustness or fault-tolerance capability of a network is an important design parameter in both wired and wireless networks. Connectivity of a network is traditionally considered to be the primary metric for evaluation of its fault-tolerance capability. However, connectivity κ(G) (for random faults) or region-based connectivity κR(G) (for spatially correlated or region-based faults, where the faults are confined to a region R) of a network G, does not provide any information about the network state, (i.e., whether the network is connected or not) once the number of faults exceeds κ(G) or κR(G). If the number of faults exceeds κ(G) or κR(G), one would like to know, (i) the number of connected components into which G decomposes, (ii) the size of the largest connected component, (iii) the size of the smallest connected component. In this paper, we introduce a set of new metrics that computes these values. We focus on one particular metric called region-based component decomposition number (RBCDN), that measures the number of connected components in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBCDN of a network. In addition, we study the problem of least cost design of a network with a target value of RBCDN. We show that the optimal design problem is NP-complete and present an approximation algorithm with a performance bound of O(log K + 4log n), where n denotes the number of nodes in the graph and K denotes a target value of RBCDN. We evaluate the performance of our algorithm by comparing it with the performance of the optimal solution. Experimental results demonstrate that our algorithm produces near optimal solution in a fraction of time needed to find an optimal solution.

Connectivity k(G) of a network G is traditionally considered to be the primary metric for evaluation of its fault tolerance capability. However, connectivity as a metric has several limitations - e.g., it has no mechanism to distinguish between localized and random faults. Also it does not provide any information about the network state, if number of failures exceed k(G). The network state information that might be of interest in such a scenario is the size of the largest connected component. In this paper, we address both these limitations and introduce a new metric called region-based largest component size (RBLCS), that provides the largest size of the component in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBLCS for a given network. In addition, we study the problem of least cost design of a network with a target value of RBLCS. We prove that the optimal design problem is NP-complete and present a heuristic to solve the problem. We evaluate our heuristic by comparing its solutions with the optimal solutions. Experimental results demonstrate that our heuristic produces near optimal solution in a fraction of time needed to find the optimal.