Robustness and reliability are critical issues in network management. To provide resiliency, a popular protection scheme against network failures is simultaneous routing along multiple paths. The use of Software-Defined Networking (SDN), with fine-grained forwarding rules and the limited forwarding table size of commodity switches, brings a new set of constraints and challenges. In this work, we consider the problem of routing demands with dependability in a software-defined ISP backbone. We propose splitting large demands over multiple paths to reduce fragmentation and achieve service reliability under failures. We also minimize the delay differential among these paths to reduce the number of out-of-order packets. Finally, our routing algorithm works with forwarding tables of bounded size, commonly required by low-cost SDN switches. We report emulation and simulation results confirming the practicality of our solutions.

Consider the set of all sequences of n outcomes, each taking one of m values, whose frequency vectors satisfy a set of linear constraints. If m is fixed while n increases, most sequences that satisfy the constraints result in frequency vectors whose entropy approaches that of the maximum entropy vector satisfying the constraints. This well-known entropy concentration phenomenon underlies the maximum entropy method. Existing proofs of the concentration phenomenon are based on limits or asymptotics and unrealistically assume that constraints hold precisely, supporting maximum entropy inference more in principle than in practice. We present, for the first time, non-asymptotic, explicit lower bounds on n for a number of variants of the concentration result to hold to any prescribed accuracies, with the constraints holding up to any specified tolerance, considering the fact that allocations of discrete units can satisfy constraints only approximately. Again unlike earlier results, we measure concentration not by deviation from the maximum entropy value, but by the 11 and 12 distances from the maximum entropy-achieving frequency vector. One of our results holds independently of the alphabet size m and is based on a novel proof technique using the multi-dimensional Berry-Esseen theorem. We illustrate and compare our results using various detailed examples.

We describe a prototype tool that analyzes combined aspects of reliability and performance for a variety of networks. Our network-wide analysis systematically generates failure scenarios (called network states), maps their effects from the physical to the network to the traffic layer, calculates the probability of each state, and evaluates a metric on it, until the expected value of the metric or a point on its distribution is estimated to sufficient accuracy. We describe an application of this multi-layer probabilistic methodology to dealing with partial link failures in an ISP backbone network.

Consider the problem of predicting in real time the next value of a random quantity x/spl ges/0 from past observations. We present a flexible solution to this problem, a dynamic Bayesian model which represents the probability distribution of x by a mixture of gamma distributions /spl Sigma//sub i/c/sub i/G(z|a/sub i/, b/sub i/). Whenever a new observation on x becomes available, the model updates its estimates of the parameters a/sub i/, b/sub i/, and c/sub i/. It also contains a monitoring mechanism that allows it to react quickly to major changes in the behavior of the input and to adjust itself when its predictions become unsatisfactory. Numerous examples are given, which illustrate the difference between static and dynamic models, and show that the mixture form is flexible enough to represent adequately a variety of inputs, even if their distributions are very different from the gamma.

Abstraction is the process of lumping together some of the inputs, states, and outputs of a finite-state system (machine) M to transform it into a smaller, generally nondeterministic system M/sub A/. Theoretically, abstraction can be viewed as a method for approximate system simplification, and practically it finds application to system monitoring. Large and complex systems are usually observable through restricted interfaces, which allow an observer only a lumped (abstracted) view of the system, and render some erroneous behaviors undetectable. In spite of the nondeterminism introduced by the abstraction, there is still a class of faults in the system (changes in the next-state or output maps) which are immediately-detectable upon occurrence. Here the author studies the problem of finding an abstraction for an FSM which groups the inputs, states, and outputs into a specified number of classes, while maximizing the number of immediately-detectable (i.d.) next-state faults of multiplicity 1. Assuming that a partition of the machine's outputs is given, the author shows that the optimal choice of either the state or the input partition is an NP-hard or NP-complete problem. However, the author gives a polynomial-time algorithm that finds an approximately optimal partition of the machine's inputs for any given partition of the states. The author also provides a bound on the optimum, computable in polynomial time. Numerical experiments with the algorithm on randomly-generated machines with two types of state partitions, suggest that (a) the optimal number of i.d. next-state faults increases linearly with the number of blocks of the input partition, and (b) that more faults are i.d. in machines with "sparse" structure and with less uniform state partitions.

In large computer or communication networks, there are sometimes components that do not fail independently to each other, such that the dependencies among them are only partially known. To address the problem of estimating the reliability of such groups of components, we show how the maximum entropy principle can be used to calculate the probability of failure of a 3-component system (S/sub 1/, S/sub 2/, S/sub c/) when only some of the individual failure probabilities, and some of the joint or conditional failure probabilities for S/sub 1/, S/sub 2/, and S/sub c/ are known. If x/sub i/ is the state of system S/sub i/ ("available" or "failed"), maximum entropy yields "best" estimates for the probabilities of all events of the form x/sub 1/x/sub 2/x/sub c/. We derive almost closed-form expressions for these probabilities under various states of knowledge. We establish analytically that the maximum entropy distributions have many properties that agree with intuition, and show how the distributions illustrate Shore and Johnson's axioms for the maximum entropy principle. We obtain closed form expressions in almost all cases for the conditional and unconditional reliabilities of series and parallel connections of S/sub 1/ and S/sub 2/.>

A general way to make a smaller model of a large system, or to represent the fact that the observations possible on it are limited, is to apply an abstraction A to it. If the system is modeled by a finite-state machine M, the abstraction consists of three partitions, one for each of the state, input, and output sets. States, inputs, or outputs lumped together in one block by the partition are indistinguishable from each other, resulting in a nondeterministic machine M/sub A/. An observer of M/sub A/, whose task is to detect erroneous behavior in M, is prevented by the abstraction from seeing some of the faults. The authors investigate the choice of an abstraction that is optimal with respect to immediately detectable faults in the output map. It is shown that this requires solving an NP-complete 'set-partitioning' problem. A polynomial-time algorithm for finding an approximately optimal partition of either the states or the inputs of M, together with a way to check the goodness of the approximation is given. This algorithm also solves the undetectable fault minimization problem exactly, and in polynomial time.>

An observer, whose task is to monitor a large and complex system M̂ subject to malfunctions, may be interested in dealing with a simplified, abstracted model (M̂A of it, at the expense of some loss in fault-detection ability. Let M̂ be a finite- state machine whose inputs are modeled by stationary random variables. The abstraction A is effected by lumping M̂'s states, inputs, and outputs into classes, to obtain a smaller probabilistic machine M̂A. These ideas have been introduced in a previous paper, and the question of finding an optimal abstraction A* which minimizes the number of faults undetectable by the observer was posed. An algorithm for constructing the output component of the optimal abstraction A* is given in this paper. If there are no faults in the next-state map of M̂, this construction is sufficient to minimize the number of single faults in the output map that are undetectable by the observer because of the abstraction. Some experiments carried out using the algorithm provide general insight into the tradeoff between simplifying M̂ and making some faults in it undetectable. As a specific example, optimal output abstractions are found for a finite-state machine specification of the link level of the X.25 communication protocol.

We introduce a scheme for passive node-level fault detection in a distributed system. With each system node associate a low-cost, low-complexity observer which monitors the pattern of incoming and outgoing messages and compares it against an abstracted model of the node's behavior. We develop a fault detection procedure, which is probabilistic because of nondeterminism in the simplified node model. Abstraction reduces model complexity, but renders some errors undetectable by the observer. In the paper we characterize these undetectable errors. Succeeding studies show how to select model abstractions to lower the number of undetectable errors.