This paper proposes a novel mechanism to discover delay-optimal diverse paths using distributed learning automata for Voice-over-IP (VoIP) routing in service overlay networks. In addition, a novel link failure detection method is proposed for detecting and recovering from link failures to reduce the number of dropped voice sessions. The main contributions of this paper are a decentralized, scalable method for minimizing delay on both a primary and secondary path between all pairs of overlay nodes, while at the same time maintaining the link disjointness between the primary and the secondary optimal paths. Simulations of a 50-node model of AT&T's backbone network show that the proposed method improves the quality of voice calls from unsatisfactory to satisfactory, as measured by the R-factor. With the proposed link failure detection mechanism, the time to recover from a link failure is considerably reduced.

We propose a novel approach using active probingand learning techniques to track minimum delay pathsfor real-time applications in service overlay networks.Stochastic automata are used to probe paths in a decentralized,scalable manner. We propose four variationson active probing and learning strategies. It canbe proved that our approach converges to the user equilibriumfor minimum delay routing. The performanceof these strategies is studied via fluid simulations of amodel of AT&Ts backbone network. The simulation resultsshow that the proposed strategies converge to theminimum delay paths rapidly. We also observe, via simulation,that our approach scales well in the size of theservice overlay network.

Toll quality Voice-over-IP (VoIP) provision over Service Overlay Networks (SONs) is still a big challenge for the current best-effort Internet. The end to end network delay, as one of the most important performance concerns, is the focus in this paper. In the paper, network delay characteristics, e.g. probability distribution and autocorrelation are studied. We propose an approach to synthesize network delay traces for QoS routing research in a full mesh Service Overlay Network(SON) given only partial information of the network delay trace. The main contributions of the paper include: 1) A parametric model of the network delay; 2) Method to synthesize network delay traces for voice packets sent over SONs. The synthesized network delay traces are shown to be close to real network delay traces. The synthetic network delay traces can be used to study quality of service provision mechanisms for VoIP applications over the Service Overlay Networks.

This paper studies the capacity and flow assignment problem arising in the design of self-healing asynchronous transfer mode (ATM) networks using the virtual path concept. The problem is formulated here as a linear programming problem which is solved using standard methods. The objective is to minimize the spare capacity cost for the given restoration requirement. The spare cost depends on the restoration strategies used in the network. We compare several restoration strategies quantitatively in terms of spare cost, notably: global versus failure-oriented reconfiguration, path versus link restoration, and state-dependent versus state-independent restoration. The advantages and disadvantages of various restoration strategies are also highlighted. Such comparisons provide useful guidance for real network design. Further, a new heuristic algorithm based on the minimum cost route concept is developed for the design of large self-healing ATM networks using path restoration. Numerical results illustrate that the heuristic algorithm is efficient and gives near-optimal solutions for the spare capacity allocation and flow assignment for tested examples.

We first present a heuristic algorithm which is based on the minimum cost route concept for capacity allocation and flow assignment in self-healing networks, and show via numerical examples that it can yield near-optimal solutions for both spare and joint optimization. Based on the near-optimal solutions, we then compare two important path restoration schemes applicable in ATM VP networks, named state-independent (SI) and state-dependent (SD) schemes, in terms of spare capacity requirement (SCR), restoration speed, VPI redundancy and node storage capacity. The comparison is based on the common single link failure scenario and 100% restoration. It is found that SI scheme has advantages over the SD scheme if their difference in SCR is small. However, if the difference cannot be ignored and there is no shortage in VPI resources the SD scheme may be a good candidate. Further, fast restoration can be achieved by using bidirectional or group VP restoration.

This paper studies the capacity and flow assignment problem arising in the design of self-healing ATM networks using the virtual path (VP) concept. The problem is formulated as a linear programming problem which is solved using standard methods. The objective is to minimize the spare capacity cost for the given restoration requirement. The spare cost depends on the restoration strategies used in the network. We compare several restoration strategies, notably, global versus failure-oriented reconfiguration, path versus link based restoration and state-dependent versus state-independent restoration, quantitatively in terms of spare cost. The advantages and disadvanages of various restoration strategies are also highlighted. Such comparisons provide useful guidance for real network design. Further, a new heuristic algorithm is developed for the design of large self-healing ATM networks using path based restoration. Numerical results illustrate that the heuristic algorithm is efficient and can give near-optimal solutions for spare capacity allocation and flow assignment.

A (large) multicast ATM switch with an external structure of output queueing and an internal structure of buffered MINs (multistage interconnection networks) is considered, where the buffered MINs (also called a switching network) are composed of switching elements with shared buffer output queueing. A cell replication while routing scheme is used in the switch to implement the multicast function. In this paper, we study the performance of the switch with multicast traffic, mainly via computer simulations. The multicast traffic can be random and bursty. From our study we found that for multicast traffic with a truncated geometric distribution of cell fanouts it has only a slightly worse impact on the performance of the switching elements in isolation or in the last stage of the switching network. The multicast traffic has no worse effect on the switch output buffer behaviour and cell delay in the switching network. Moreover, traffic splitting can substantially improve the switching network performance for highly bursty traffic. Some analytical approximations are given which could be useful in the dimensioning of switching networks.

A unified framework for traffic control and bandwidth management in ATM networks is proposed. It bridges algorithms for real-time and data services. The central concept of this framework is adaptive connection admission. It employs an estimation of the aggregate equivalent bandwidth required by connections carried in each output port of the ATM switches. The estimation process takes into account both the traffic source declarations and the connection superposition process measurements in the switch output ports. This is done in an optimization framework based on a linear Kalman filter. To provide a required quality of service guarantee, bandwidth is reserved for possible estimation error. The algorithm is robust and copes very well with unpredicted changes in source parameters, thereby resulting in high bandwidth utilization while providing the required quality of service. The proposed approach can also take into account the influence of the source policing mechanism. The tradeoff between strict and relaxed source policing is discussed.

A fundamental problem in connection oriented multiservice networks (ATM and STM) is finding the optimal policy for call acceptance. One seeks an admission control policy that efficiently utilizes network resources while at the same time being fair to the various call classes being supported. The theory of cooperative games provides a natural and precise framework for formulating such multicriterion problems as well as solution concepts. The authors describe how this framework can be used for analysis and synthesis of call admission strategies in broadband networks. In particular they investigate the Nash (1950), Raiffa-Kalai-Smorodinsky (Raiffa, 1953; Kalai and Smorodinsky, 1975), and modified Thomson (Cao, 1982) arbitration solutions from game theory. The performance of all solutions is evaluated by applying the value iteration algorithm from Markov decision theory. The approach is illustrated on a one-link network example for which the exact solutions can be achieved. The results indicate that the arbitration schemes from game theory provide some attractive features especially when compared to traditional control objectives: blocking equalization and traffic maximization. The authors also compare the optimal solutions with some simplified policies belonging to four different classes: complete sharing, coordinate convex, trunk reservation, and dynamic trunk reservation. The comparison indicates that in many cases, the trunk reservation and dynamic trunk reservation policies can provide fair, efficient solutions, close to the optimal ones.

A state-dependent policy for call admission and routing in a multi-service circuit-switched network is synthesized. To meet different requirements the objective function is defined as the mean value of reward from the network. Policy iteration is applied to find the optimal control. Assuming link independence the network reward process is decomposed into the set of link reward processes thereby significantly reducing complexity. The approach is implementable for large systems if certain approximations are used. A simulation study shows that the algorithm converges in two iterations, exhibits good traffic efficiency, and provides a flexible tool for performance allocation among services. The approach also constitutes a framework for studying, synthesizing and optimizing other call admission and routing strategies. In particular the results of sensitivity analysis are used to compare the proposed decomposition approach with that developed by F. P. Kelly (1988) for optimization of a load sharing policy in telephone networks.>

A state-dependent call admission and routing policy for a multiservice circuit-switched network is analyzed. The policy is based on decomposition of the Markov decision problem into a set of separable link problems. To provide an exact link analysis model a value iteration algorithm was offered. This allows examination of the accuracy of several approximations used to reduce the complexity of the problem. The numeral study showed that the convergence of the analyzed strategy is achieved in at most two iterations. The study also showed the good traffic efficiency of the approach and confirmed the predicted ability to control the distribution of call classes grade of service. The approach, together with its sensitivity analysis with respect to the arrival rates, provides a very general framework for studying, constructing, and optimizing other call admission and routing strategies. The results of sensitivity analysis are used to compare the proposed decomposition approach with the decomposition approach developed by F.P. Kelly (1988) for optimization of a load sharing policy. Also, the relationship to other routing strategies based on Markov decision theory is investigated.>

Admission control and routing in circuit-switched networks are investigated with two types of traffic: wideband with delayed call set up and narrowband operating in loss mode. Markov decision theory is used to construct a state-dependent routing policy. Optimality conditions for a load sharing routing are derived from the first-order Kuhn-Tucker equations. These models together with a direct routing scheme are used in a simulation study to determine the best approach for control of traffic with delayed call setup. State-dependent routing is found to be superior to direct routing and load sharing routing, although its operation is much more complex.>

A general mathematical model for a network design problem with reliability constraints and a revised formulation which seems particularly appropriate for fiber-optics networks is presented. Upper and lower bounding procedures based on continuous relaxations of this modified formulation are described. Preliminary computational results are reported. Limited computational results indicate a good performance of the algorithm, producing a gap between lower and upper bounds that is sufficiently small for a branch-and-bound procedure to be applicable.>

An approximate model (with finite or infinite waiting room) is presented for an integrated service system with three types of traffic: a first-offered narrowband traffic, an overflow narrowband traffic, and a wideband traffic. A narrowband call requires a single server, while the number of servers required to serve a wideband call is N. The blocked narrowband calls are lost while the blocked wideband calls are delayed in a finite or infinite waiting room. Based on two assumptions with regard to the characteristics of the system, the system is resolved by decomposition. The corresponding improvements in numerical efficiency as well as in computational storage requirements are significant enough to enable use of the model within network optimization algorithms. The model provides a very good approximation for the system performance, i.e. the blocking probabilities of the two narrowband traffics, the loss probability (in the case of finite waiting room), the probability of nonwaiting, and the average waiting time of wideband traffic.>