In this paper, we propose a heterogeneous risk-aware Software-Defined Networking (SDN) migration method for designing survivable networks in the face of multiple correlated failures. The migration method, which is implemented in one shot, specifies how many nodes of each SDN implementation are needed, and where such nodes must be located, in order to yield an SDN migrated network with maximal survivability, when multiple correlated failures impact the entire network connectivity. We formulated the survivable SDN migration problem through integer optimization, where the proposed cost function assesses the survivability of the migrated network in terms of the number of connected components after a failure. The numerical results calculated over test networks show the capability of migration method to provide survivable SDN topologies, which trade-off the heterogeneity in the SDN implementations and the number of shared risks.

This paper presents a flow-based entropy characterization of a small/medium-sized campus network that uses network address translation (NAT). Although most networks follow this configuration, their entropy characterization has not been previously studied. Measurements from a production network show that the entropies of flow elements (external IP address, external port, campus IP address, campus port) and tuples have particular characteristics. Findings include: i) entropies may widely vary in the course of a day. For example, in a typical weekday, the entropies of the campus and external ports may vary from below 0.2 to above 0.8 (in a normalized entropy scale 0-1). A similar observation applies to the entropy of the campus IP address; ii) building a granular entropy characterization of the individual flow elements can help detect anomalies. Data shows that certain attacks produce entropies that deviate from the expected patterns; iii) the entropy of the 3-tuple {external IP, campus IP, campus port} is high and consistent over time, resembling the entropy of a uniform distribution's variable. A deviation from this pattern is an encouraging anomaly indicator; iv) strong negative and positive correlations exist between some entropy time-series of flow elements.

While the reliability of distributed-computing systems (DCSs) has been widely studied under the assumption that computing elements (CEs) fail independently, the impact of correlated failures of CEs on the reliability remains an open question. Here, the problem of modeling and assessing the impact of stochastic, correlated failures on the service reliability of applications running on DCSs is tackled. The service reliability is modeled using an integrated analytical and Monte-Carlo (MC) approach. The analytical component of the model comprises a generalization of a previously developed model for reliability of non-Markovian DCSs to a setting where specific patterns of simultaneous failures in CEs are allowed. The analytical model is complemented by a MC-based procedure to draw correlated-failure patterns using the recently reported concept of probabilistic shared risk groups (PSRGs). The reliability model is further utilized to develop and optimize a novel class of dynamic task reallocation (DTR) policies that maximize the reliability of DCSs in the presence of correlated failures. Theoretical predictions, MC simulations, and results from an emulation testbed show that the reliability can be improved when DTR policies correctly account for correlated failures. The impact of correlated failures of CEs on the reliability and the key dependence of DTR policies on the type of correlated failures are also investigated.

In this paper, we present an algorithm for minimizing the processing time of a video sequence on a handheld-based distributed computing system. The algorithm considers the energy use and the remaining energy of the nodes, and steers a Monte-Carlo-based allocation according to the following rationale: images should be mapped more likely onto those nodes that communicate and process faster, consume less energy, and possess more energy reservoirs. Simulation results show that these simple ideas allow the allocation algorithm to deal efficiently with the fundamental tradeoff between turnaround time and energy.

In wireless sensor networks (WSNs), random failures at the sensor nodes and the communication level reduce the likelihood of completing a prescribed mission. This likelihood is further reduced when geographically correlated failures affect the sensing and communication capabilities of the network. In this work, a mission allocation algorithm for WSNs accounting for geographically correlated failures is proposed. The algorithm maximizes the likelihood of completing a mission in WSNs by allocating resources onto the sensor nodes according to a score that weighs the resources, the availability, and the likelihood of sensor nodes to be affected by geographically correlated failures.

Average service time, quality-of-service (QoS), and service reliability associated with heterogeneous parallel and distributed computing systems (DCSs) are analytically characterized in a realistic setting for which tangible, stochastic communication delays are present with nonexponential distributions. The departure from the traditionally assumed exponential distributions for event times, such as task-execution times, communication arrival times and load-transfer delays, gives rise to a non-Markovian dynamical problem for which a novel age dependent, renewal-based distributed queuing model is developed. Numerical examples offered by the model shed light on the operational and system settings for which the Markovian setting, resulting from employing an exponential-distribution assumption on the event times, yields inaccurate predictions. A key benefit of the model is that it offers a rigorous framework for devising optimal dynamic task reallocation (DTR) policies systematically in heterogeneous DCSs by optimally selecting the fraction of the excess loads that need to be exchanged among the servers, thereby controlling the degree of cooperative processing in a DCSs. Key results on performance prediction and optimization of DCSs are validated using Monte-Carlo (MC) simulation as well as experiments on a distributed computing testbed. The scalability, in the number of servers, of the age-dependent model is studied and a linearly scalable analytical approximation is derived.

The physical infrastructure of communication networks is vulnerable to spatially correlated failures arising from various physical stresses such as natural disasters (earthquakes and hurricanes) as well as malicious coordinated attacks using weapons of mass destruction. Some disaster events such as earthquakes and terrorist attacks may occur in more than one location in a short period of time. Hence multiple sets of correlated link failures may occur if more events occurred before the previous set of failed links were repaired. Here, the statistical properties of induced-failure patterns depend upon the spatial interaction among stress centers (e.g., interaction among earthquake or attack locations). This paper presents a stochastic model, based on spatial point processes, for representing stress centers in geographical plane in order to facilitate the modeling of spatially inhomogeneous and correlated link failures in communication networks. This model is then used to further generate scenarios with inhibition or clustering between stress centers, which enables detailed assessment of vulnerabilities of the network to the level of inhomogeneity and spatial correlation in the stress-event centers. Detailed simulation results are presented to compare network reliability for various scenarios of link failures and to find geographically vulnerable areas of a network as well as worst-case scenarios of stress-events. Overall, this effort will provide some critical knowledge and simulation capability for other focus areas of research in network reliability and survivability.

This paper presents a general framework for optimal task reallocation in heterogeneous distributed-computing systems and offers a rigorous analytical model for the stochastic execution time of a workload. The model takes into account the heterogeneity and stochastic nature of the tasks' service and transfer times, servers' failure times, as well as an arbitrary task-reallocation policy. The stochastic service, transfer and failure times are assumed to have general, age-dependent (non-exponential) distributions, resulting in a tandem distributed queuing system with non-Markovian dynamics. Auxiliary age variables are introduced in the analysis to capture the memory associated with the non-Markovian stochastic times, thereby enabling a regenerative age-dependent analytical characterization of the statistics of the execution time of a workload. The model is utilized to devise task reallocation policies that optimize three metrics: the average execution time of a workload, the quality-of-service in executing a workload by a prescribed deadline and the reliability in executing a workload. Implications of the non-exponential event times on these metrics are also studied. Key results are verified experimentally on a distributed-computing testbed.

In distributed computing systems (DCSs) where server nodes can fail permanently with nonzero probability, the system performance can be assessed by means of the service reliability, defined as the probability of serving all the tasks queued in the DCS before all the nodes fail. This paper presents a rigorous probabilistic framework to analytically characterize the service reliability of a DCS in the presence of communication uncertainties and stochastic topological changes due to node deletions. The framework considers a system composed of heterogeneous nodes with stochastic service and failure times and a communication network imposing random tangible delays. The framework also permits arbitrarily specified, distributed load-balancing actions to be taken by the individual nodes in order to improve the service reliability. The presented analysis is based upon a novel use of the concept of stochastic regeneration, which is exploited to derive a system of difference-differential equations characterizing the service reliability. The theory is further utilized to optimize certain load-balancing policies for maximal service reliability; the optimization is carried out by means of an algorithm that scales linearly with the number of nodes in the system. The analytical model is validated using both Monte Carlo simulations and experimental data collected from a DCS testbed.

A regeneration-based approach is undertaken to derive an expression for the expected value of total service time for an arbitrary customer distribution when scheduling is performed in a distributed queuing system. The service times and the transfer delays for customers in the shared communication medium are both considered random. The theory is applied to a distributed wireless-sensor network and the interplay between the total service time and the energy consumption of each sensor is investigated.

A regeneration-theory approach is undertaken to analytically characterize the average overall completion time in a distributed system. The approach considers the heterogeneity in the processing rates of the nodes as well as the randomness in the delays imposed by the communication medium. The optimal one-shot load balancing policy is developed and subsequently extended to develop an autonomous and distributed load-balancing policy that can dynamically reallocate incoming external loads at each node. This adaptive and dynamic load balancing policy is implemented and evaluated in a two-node distributed system. The performance of the proposed dynamic load-balancing policy is compared to that of static policies as well as existing dynamic load-balancing policies by considering the average completion time per task and the system processing rate in the presence of random arrivals of the external loads.

In many distributed computing systems that are prone to either induced or spontaneous node failures, the number of available computing resources is dynamically changing in a random fashion. A load-balancing (LB) policy for such systems should therefore be robust, in terms of workload re-allocation and effectiveness in task completion, with respect to the random absence and re-emergence of nodes as well as random delays in the transfer of workloads among nodes. In this paper two LB policies for such computing environments are presented: The first policy takes an initial LB action to preemptively counteract the consequences of random failure and recovery of nodes. The second policy compensates for the occurrence of node failure dynamically by transferring loads only at the actual failure instants. A probabilistic model, based on the concept of regenerative processes, is presented to assess the overall performance of the system under these policies. Optimal performance of both policies is evaluated using analytical, experimental and simulation-based results. The interplay between node-failure/recovery rates and the mean load-transfer delay are highlighted