Software-defined networks (SDNs) facilitate more efficient routing of traffic flows using centralized network view. On the other hand, traditional distributed routing still enjoys the advantage of better scalability, robustness, and swift reaction to events such as failure. There are therefore significant potential benefits to adopt a hybrid operation where both distributed and centralized routing mechanisms co-exist. This hybrid operation however imposes a new challenge to network stability since a poor and inconsistent design can lead to repeated route switching when the two control mechanisms take turns to adjust the routes. In this paper, we discuss ways of solving the stability problem. We first define stability for hybrid SDNs and then establish a per-priority stabilizing framework to obtain stable routing patterns. For each priority class, we discuss three approaches to reach hybrid SDN stability: global optimization, greedy, and local search. It is argued that the proposed local search provides the best tradeoff among cost performance, computational complexity, and route disturbance. Furthermore, we design a system on a centralized controller, which utilizes those algorithms to stabilize the network. The design is implemented and extensively tested by simulations using realistic network information, including a trace of the Abilene network and data from a tier-1 Internet service providers backbone network.

It is desirable to have fast detection of failures followed by fast restoration and recovery in data networks (IP, ATM, frame relay, etc.) using link-state interior gateway protocols (IGP). This requires faster hello exchanges (unless one relies on link level detection which is not always possible), fast flooding, and more frequent shortest-path-first calculations. However, through analysis and simulation we show that this compromises the scalability and stability of the network. This is mainly because hello packets received at a router are indistinguishable from other packets and may experience long queueing delays during a sudden burst of many LSA (link-state advertisement) updates and cause the associated link to be declared down. At a later instant the link would recover. Both the failure and recovery generate fresh LSA, in effect developing a feedback loop to sustain the LSA storm. We suggest that hello and potentially some other IGP packets, such as acknowledgments, be marked explicitly so that they may be distinguished and queued separately from other IGP and data packets at the line rate and provided prioritized treatment. This allows significant reduction in IGP convergence time while maintaining network stability.

In earlier papers, we proposed the PCC (parallel connection control) algorithm for the setup and release of on-demand ATM (asynchronous transfer mode) connections. This paper describes an implementation and analysis of PCC. The PCC algorithm is implemented on a testbed of three types of ATM switches from which service time measurements (software execution times) are obtained. These measured service times are used as input data for an analytical queueing network model to characterize the PCC end-to-end setup delay and maximum throughputs. Assuming all connections pass through ten switches, for this measured data, PCC has a theoretical maximum throughput of 343 calls/sec/switch, and at about 90% of this maximum limit (i.e., at 310 calls/sec/switch), the mean end-to-end connection setup delay is only 43 ms. We also compare PCC performance against an equivalent sequential connection setup/release approach. We observe that PCC end-to-end setup delay is much smaller than the sequential setup delay (34% at low load and even smaller at higher load). Also, the per-switch maximum throughput of the PCC approach is 80% more compared to the sequential approach.

It is known that probability density functions and probability mass functions usually can be calculated quite easily by numerically inverting their transforms (Laplace transforms and generating functions, respectively) with the Fourier-series method. Other more general functions can be substantially more difficult to invert, because the aliasing and roundoff errors tend to be more difficult to control. In this article we propose a simple new scaling procedure for nonprobability functions that is based on transforming the given function into a probability density function or a probability mass function and transforming the point of inversion to the mean. This new scaling is even useful for probability functions, because it enables us to compute very small values at large arguments with controlled relative error.

We identify conditions under which relatively large buffers will be required in broadband communication networks. For this purpose, we analyze an infinite-capacity stochastic fluid model with a general stationary environment process (without the usual independence or Markov assumptions). With that level of generality, we are unable to establish asymptotic results, but by a very simple argument we are able to obtain a revealing lower bound on the steady-state buffer-content tail probability. The bounding argument shows that the steady-state buffer content will have a long-tail distribution when the sojourn time in a set of states with positive net input rate itself has a long-tail distribution. If a set of independent sources, each with a general stationary environment process, produces a positive net flow when all are in high-activity states, and if each of these sources has a high-activity sojourn-time distribution with a long tail, then the steady-state buffer-content distribution will have a long tail, but possibly one that decays faster than the tail for any single component source. The full buffer-content distribution can be derived in the special case of a two-state fluid model with general high- and low-activity-time distributions, assuming that successive high- and low-activity times come from independent sequences of i.i.d. random variables. In that case the buffer-content distribution will have a long tail when the high-activity-time distribution has a long tail. We illustrate by giving numerical examples of the two-state model based on numerical transform inversion.

A common approach used for decreasing end-to-end connection setup delay in ATM networks is to provision partial segments a priori using virtual path connections (VPCs). In this paper, we present an analysis to study the effect of such provisioning. The analysis demonstrates that significant savings in bandwidth, and hence network costs, are achieved if the number of provisioned VPCs are minimized, especially if there is uncertainty in the traffic pattern characterization. For a given example, we show that to achieve a 0.1% blocking probability requirement, if link capacities are shared (i.e., not partitioned a priori to provisioned VPCs), resource savings of 14.4%, 47.9% or 80% are possible under exact, approximate and poor traffic characterizations, respectively. If the above bandwidth savings are to be achieved in networks that use traditional node-by-node connection setup approaches, end-to-end connection setup delay will increase. In this paper, we propose a new connection setup algorithm that allows the savings in bandwidth obtained through sharing while at the same time controlling the connection setup delay.

The Laguerre method for numerically inverting Laplace transforms is an old established method based on the 1935 Tricomi–Widder theorem, which shows (under suitable regularity conditions) that the desired function can be represented as a weighted sum of Laguerre functions, where the weights are coefficients of a generating function constructed from the Laplace transform using a bilinear transformation. We present a new variant of the Laguerre method based on: (i) using our previously developed variant of the Fourier-series method to calculate the coefficients of the Laguerre generating function, (ii) developing systematic methods for scaling, and (iii) using Wynn's ϵ-algorithm to accelerate convergence of the Laguerre series when the Laguerre coefficients do not converge to zero geometrically fast. These contributions significantly expand the class of transforms that can be effectively inverted by the Laguerre method. We provide insight into the slow convergence of the Laguerre coefficients as well as propose a remedy. Before acceleration, the rate of convergence can often be determined from the Laplace transform by applying Darboux's theorem. Even when the Laguerre coefficients converge to zero geometrically fast, it can be difficult to calculate the desired functions for large arguments because of roundoff errors. We solve this problem by calculating very small Laguerre coefficients with low relative error through appropriate scaling. We also develop another acceleration technique for the case in which the Laguerre coefficients converge to zero geometrically fast. We illustrate the effectiveness of our algorithm through numerical examples.

Although ATM seems to be the wave of the future, one analysis requires that the utilization of the network be quite low. That analysis is based on asymptotic decay rates of steady-state distributions used to develop a concept of effective bandwidths for connection admission control. The present authors have developed an exact numerical algorithm that shows that the effective-bandwidth approximation can overestimate the target small blocking probabilities by several orders of magnitude when there are many sources that are more bursty than Poisson. The bad news is that the appealing simple connection admission control algorithm using effective bandwidths based solely on tail-probability asymptotic decay rates may actually not be as effective as many have hoped. The good news is that the statistical multiplexing gain on ATM networks may actually be higher than some have feared. For one example, thought to be realistic, the analysis indicates that the network actually can support twice as many sources as predicted by the effective-bandwidth approximation. The authors also show that the effective bandwidth approximation is not always conservative. Specifically, for sources less bursty than Poisson, the asymptotic constant grows exponentially in the number of sources (when they are scaled as above) and the effective-bandwidth approximation can greatly underestimate the target blocking probabilities. Finally, they develop new approximations that work much better than the pure effective-bandwidth approximation.

A new algorithm is developed for calculating normalization constants (partition functions) and moments of product-form steady-state distributions of closed queuing networks and related models. The essential idea is to numerically invert the generating function of the normalization constant and related generating functions appearing in expressions for the moments. It is known that the generating function of the normalization constant often has a remarkably simple form, but numerical inversion evidently has not been considered before. For p -dimensional transforms, as occur with queuing networks having p closed chains, the algorithm recursively performs p one-dimensional inversions. The required computation grows exponentially in the dimension, but the dimension can often be reduced by exploiting conditional decomposition based on special structure. For large populations, the inversion algorithm is made more efficient by computing large sums using Euler summation. The inversion algorithm also has a very low storage requirement. A key ingredient in the inversion algorithm is scaling. An effective static scaling is developed for multichain closed queuing networks with only single-server and (optionally) infinite-server queues. An important feature of the inversion algorithm is a self-contained accuracy check, which allows the results to be verified in the absence of alternative algorithms.

The algorithm developed in Choudhury et al. (1994) for computing (exact) steady-state blocking probabilities for each class in product-form loss networks is extended to cover general state-dependent arrival and service rates. This generalization allows to consider, for the first time, a wide variety of buffered and unbuffered resource-sharing models with non-Poisson traffic, as may arise with overflows in the context of alternative routing. As before, the authors consider noncomplete-sharing policies involving upper-limit and guaranteed-minimum bounds for the different classes, but in the present paper both bounds are discussed simultaneously. These bounds are important for providing different grades of service with protection against overloads by other classes. The algorithm is based on numerically inverting the generating function of the normalization constant, which is derived in the present paper. Major features of the algorithm are: dimension reduction by elimination of nonbinding resources and by conditional decomposition based on special structure, an effective scaling algorithm to control errors in the inversion, efficient treatment of multiple classes with identical parameters and truncation of large sums. The authors show that the computational complexity of the inversion approach is usually significantly lower than the alternative recursive approach.>

Exact results are presented on the mean waiting time in a nonsymmetric polling system with general service order table and gated service. The results are obtained using a generalization of the work of Ferguson and Aminetzah (see IEEE Trans. on Commun., vol.COM-33, p.223-31 , 1985). Pseudocycle times are defined, the relationship between cycle times and pseudocycle times is expressed, and the generating functions for the waiting times and the number of messages at the stations and at the pseudostations are obtained as functions of pseudocycle times. Equations are derived for the case of zero first two moments of the switch-over time at every station. Using numerical examples, a previously published pseudoconservation law is verified. The numerical results quantify the significant reductions in the waiting time and the queue occupancy at a station (particularly at high server utilizations) by listing it more frequently in the polling table.>

The commenters identify and correct errors in some of the equations in the above-titled paper by Ferguson and Aminetzah (see ibid., vol.COM-33, p.223-31, Mar. 1985), particularly those related to gated service discipline. In addition, they compare equivalent gated and exhaustive systems (using the corrected equations) numerically in terms of the mean waiting time behaviors at the various nodes, and in terms of the overall mean and variance of the mean waiting times across the nodes.>

Some CSMA-CD schemes for multiple priority message classes are suggested. For all the schemes, an approximate analytic technique for calculating the mean packet delay (for each priority) at the stable operating point of the system has been developed. The analytic results are tested against computer simulation. A Poisson packet arrival process and a general packet length distribution are considered. The mean packet retransmission delay is a general function of priority and the number of unsuccessful attempts. There is a variation in delay differences among priorities for the different schemes. This allows one to single out the particular scheme that is optimal for a given system delay requirement. Some of the priority schemes possess the desirable property of having less average delay compared to a corresponding nonpriority system.

A generalization of the slotted ALOHA random access scheme is considered in which a user transmits multiple copies of the same packet. The multiple copies can be either transmitted simultaneously on different frequency channels (frequency diversity) or they may be transmitted on a single high-speed channel but spaced apart by random time intervals (time diversity). In frequency diversity, two schemes employing channel selections with and without replacements have been considered. In time diversity, two schemes employing a fixed number of copies or a random number of copies for each packet have been considered. In frequency diversity, activity factor-throughput tradeoffs and in time diversity, delay-throughput tradeoffs for various diversity orders have been compared. It is found that under light traffic, multiple transmission gives better delay performance. If the probability that a packet fails a certain number or more times is specified not to exceed some time limit (realistic requirement for satellite systems having large round trip propagation delay), then usually multiple transmission gives higher throughput.