A fast simulation technique based on importance sampling is developed for the analysis of path service availability in mesh networks with dynamic path restoration. The method combines the simulation of the path rerouting algorithm with a “dynamic path failure importance sampling” (DPFS) scheme to estimate path availabilities efficiently. In DPFS, the failure rates of network elements are biased at increased rates until path failures are observed under rerouting. The simulated model uses “failure equivalence groups,” with finite/infinite sources of failure events and finite/infinite pools of repair personnel, to facilitate the modeling of bidirectional link failures, multiple in-series link cuts, optical amplifier failures along links, node failures, and more general geographically distributed failure scenarios. The analysis of a large mesh network example demonstrates the practicality of the technique.

Practical reliability models are developed to support the engineering of carrier-class networks that provide VoIP service to enterprise customers. The focus is on end-to-end measures of service reliability. The paper first describes the typical architecture of large-scale carrier-class VoIP networks, the message flows that exist therein, and use case variations that arise in practice. Reliability measures of interest are then defined and models are developed in terms of the call flows and element reliabilities. The failover and repair mechanisms that may be employed in the various protocol layers are also surveyed. An example analysis illustrates the modeling of a particular use case. The developed models provide a convenient practical means to estimate end-to-end VoIP service reliability prior to field trials or network deployments. Such proactive modeling is an important step in the planning and engineering of new VoIP networks

A well-known objective method of speech quality measurement is the ITU-T P.862 PESQ. This input/output-based method of perceptual quality evaluation operates on a transmitted (input) and received (output) speech signal to compute an objective perceptual quality score for the received signal. In this paper, we present F-PESQ, a novel output-based method of applying PESQ to received speech signals assumed to be coded in a framed format. It enables the application of PESQ to voice calls in networks without requiring knowledge of the transmitted signals. As such, it may be applied in vivo to voice calls at end-devices. The accuracy of F-PESQ is evaluated with analysis and simulations of frame loss with G.711, G.723, and G.729 codecs. A client/server architecture is presented for minimizing the computational requirements that F-PESQ imposes on end-devices. We also show how F-PESQ can be combined with the ITU-T G.I 07 E-model in a MOSC (conversational mean opinion score) measurement method that accounts for additional factors such as round-trip delay.

Voice signal processing algorithms such as P.861 PSQM (perceptual speech quality measure) and P.862 PESQ (perceptual evaluation of speech quality) have been recommended by the ITU-T for the objective measurement of subjective speech quality. The algorithms have been implemented in commercially available products to measure the end-to-end speech quality of voice-over-IP (VoIP) calls. Such measurements are carried out by transmitting a packetized reference speech signal and then applying PSQM or PESQ to the received signal and the original reference to obtain an objective quality score. The measurements are intrusive since test calls are injected into the network. We develop a novel passive method for measuring and monitoring speech quality in live (i.e. in progress) VoIP calls. In contrast to the intrusive methods, the passive method does not require the transmission of any reference speech signal. Instead, the method operates directly on VoIP packet streams copied from the network and applies the ITU-T objective speech quality processing algorithms to the copied voice signals and specially constructed 'pseudo-packet' stream signals. Thus there is no need for any sending devices. The proposed passive method inherits the accuracy that is already provided by the ITU-T objective methods.

A quantitative approach is developed for modeling and analyzing objectively the perceptual performance of computer-communication networks and computer systems that involve real-time human interaction and communication with real-time streamed signals such as audio, speech, or video. The proposed 'perceptual analysis' method is based on augmenting traditional system performance models with the incorporation of ITU-T recommended objective perceptual quality assessment methods such as PEAQ (perceived audio quality) or PESQ (perceptual evaluation of speech quality). The approach provides an avenue for including the quantitative evaluation of perceptual quality measures, such as MOS (mean opinion score), in system performance modeling. The analysis of a voice-over-IP network access link model with G.711 and G.729 multiplexed calls is presented to demonstrate a perceptual teletraffic engineering application.

A major challenge in the development of integrated service packet networks is to devise mechanisms that can support services with different QoS requirements. Recently, a new mechanism was developed, called weighted fair blocking (WFB), that can be placed on top of almost any discrete-time multiplexing system for controlling packet loss. The WFB mechanism has a number of attractive features. It can offer sources a range of QoS loss levels or be used as a balanced fair blocking (BFB) mechanism to equalize blocking probabilities in the interest of fairness. The BFB mechanism also reduces multiplexer buffer requirements significantly. The mechanism was derived for multiple Bernoulli sources as well as for two bursty MMBP (Markov modulated Bernoulli processes) sources. In this paper, we extend the BFB mechanism to the more realistic case of multiple MMBPs. The extension is found to be theoretically tractable but significant practical complications arise. To circumvent these difficulties, a simple heuristic BFB (H-BFB) mechanism is proposed. The performance of H-BFB is found to be remarkably good in approaching that of theoretically exact BFB from the point of view of buffer gains and fairness.

A major challenge in integrated services packet networks is the design of packet multiplexing systems to support different QoS requirements. We focus on the problem of satisfying different loss requirements. In time-slotted multiplexing systems, one may have batch arrivals (i.e., simultaneous arrivals in a time slot), and it is necessary to reject some of the packets in a batch when there is an insufficient number of available buffers. We propose a simple and intelligent probabilistic mechanism for rejecting packets in order to meet the loss requirements. It may be used as a selective discard mechanism to provide different QoS levels in terms of loss (weighted fair blocking). It may also be used to achieve fairness (balanced fair blocking). It offers important advantages and gains relative to existing approaches while being very simple. It allows decoupling of buffer dimensioning from the parameterization of a discard mechanism. It is universal in the sense that it may be used on top of many discrete-time multiplexing schemes. It also reduces the buffer space needed to meet loss requirements compared to natural rejection methods such as random selection. The mechanism is derived explicitly for two Markov modulated Bernoulli sources. The derivation for an arbitrary number of Bernoulli sources is formulated as a linear programming problem.

A new mean-value type of algorithm is developed for analyzing multi-facility blocking models with state-dependent arrival rates. It can be applied to a broad class of blocking systems with simultaneous resource possession including, for example, circuit-switched networks. The underlying recursion is cast in terms of blocking probabilities and marginal state probabilities. The developments made here generalize previous results that were restricted to the case of constant arrival rates.

Single-hop and multi-hop wavelength division multiplex (WDM) access systems have been proposed to take advantage of the large bandwidth available in lightwave mediums. In such systems, there are one or several transmitters and receivers at each node in the network. The receivers and transmitters may be tunable or set at particular wavelengths. The lightwave medium makes available a large number of channels at different wavelengths. Recently, the stochastic analysis of single-hop and multi-hop systems has been studied. The authors present a unified 'multi-facility blocking model' approach to the stochastic modeling and analysis of WDM networks of both the single-hop and multi-hop type. The developed model is amenable to exact analysis by an efficient recursive algorithm. The modeling and analysis technique enables one to study the performance of arbitrary access configurations under general traffic conditions including the case of uniform traffic and the case where there are 'hot spots.'.>

Three new decomposition methods are developed for the exact analysis of stochastic multi-facility blocking models of the product-form type. The first is a basic decomposition algorithm that reduces the analysis of blocking probabilities to that of two separate subsystems. The second is a generalized M-subsystem decomposition method. The third is a more elaborate and efficient incremental decomposition technique. All of the algorithms exploit the sparsity of locality that can be found in the demand matrix of a system. By reducing the analysis to that of a set of subsystems, the overall dimensionality of the problem is diminished and the computational requirements are reduced significantly. This enables the efficient computation of blocking probabilities in large systems. Several numerical examples are provided to illustrate the computational savings that can be realized.

The performance analysis of a synchronous finite buffer ATM cell multiplexer with heterogeneous or homogeneous bursty sources and multiple servers is considered. A novel solution technique, based on the method of compensation, is formulated that reduces the problem of obtaining the ergodic state distribution and the associated performance measures to (1) the determination of the ergodic Green's density matrix for an associated homogeneous process defined on an infinite strip and (2) the solution of a system of linear equations whose order depends only on the number of sources. An important feature of the approach is that it facilitates a parametric analysis with respect to the buffer size. Several numerical examples are provided to illustrate the theory. Simulation results are also used to validate the theoretical analysis.>

In this paper, we present simple recursive algorithms for computing call and time congestion in the classical Engset model with M sources and N servers. The first recursion has the complexity of O(MN) and gives the blocking probabilities for all intermediate values of M and N. The second recursion assumes a particular value of M and has the complexity of O(N). It gives the blocking probabilities for all intermediate values of N. Both recursions are similar to the well-known recurrence for computing the Erlang loss function.

A hybrid analytic/simulation methodology is formulated for evaluating end-to-end response time distributions in closed product-form queueing networks. The method combines Markov-Monte-Carlo simulation with analytical results pertaining to uniformized Markov chains and product-form queuing networks. A stratified sampling plan is incorporated as a variance reduction technique. The concept of importance sampling is used to reduce the computational requirements of the plan and make it realizable in practice. The most important consequence of applying uniformization is that it enables the characterization of the response time distribution as an infinite mixture of Erlangian distributions. An estimate of the entire response time distribution may then be obtained in each simulation trial. This circumvents the practical problems associated with estimating tail probabilities. A numerical example is provided to illustrate the theory.>

A general-purpose decomposition method is formulated for the exact analysis of blocking probabilities in multirate circuit-switched networks. The procedure is based on a decomposition and aggregation technique that exploits the sparsity that can be found in the routing matrix of a network. Use is also made of a recursive algorithm developed by the authors (see Ann. Oper. Res. vol.35, no.1-4, p.31-41, 1992). No special assumptions are made with regard to the structure of the network. By reducing the analysis to that of a set of interrelated subsystems and a reduced system, the overall dimensionality of the problem is diminished, and the computational costs are reduced significantly. This enables the efficient exact analysis of larger network models. An example is provided to illustrate the computational savings that can be realized.>

Several approaches to quantitatively evaluating the effects of multiple layers of protocol and the associated processing overheads are discussed. Performance models that are made up of two or three layers are surveyed. Methodologies that are oriented toward a full seven-layer architecture are discussed. These methodologies include a hierarchical decomposition and aggregation method, a method of analysis based on formal specifications, and an iterative decomposition method based explicitly on a generic queuing network model. The comparative advantages of the methods are discussed.>

A computational algorithm is developed for closed multichain product-form queueing networks. For networks that consist of only single-server fixed rate and infinite-server service centers, it involves only mean performance measures. The algorithm, called mean value analysis by chain (MVAC), is based on a recursion that is quite different in form from the recursion used in the well-known mean value analysis (MVA) algorithm and has quite different computational and storage costs. For networks with few service centers and many chains, MVAC typically has much lower costs than MVA, although it becomes more costly than MVA as the number of service centers increases. The MVAC recursion is similar in structure to a recursion involving normalizing constants that was derived by A.E. Conway and N.D. Georganas (1986). That recursion formed the basis for their recursion by chain (RECAL) algorithm for computing the normalizing constant and from it the mean performance measures. The computational and storage costs for MVAC are shown to be similar to those for RECAL.>

The class of product-form semi-homogeneous queueing networks is introduced as a generalization of the class of homogeneous networks, which has been considered by Balbo et al for the performance modeling of local area networks. In semi-homogeneous networks, the relative traffic intensity at the various shared resources may depend on the routing chain to which a customer belongs. We develop an efficient algorithm for the exact analysis of this class of networks. It is based on the equations which form the foundation of RECAL, a general purpose exact algorithm for multiple-chain closed queueing networks. The complexity of the algorithm is shown to be of order less than exponential in (P-1)1/2, where P is the number of processors (workstations) in the network. It is therefore, in general, more efficient than a direct application of either convolution, MVA or RECAL to the class of semi-homogeneous queueing networks. The algorithm presented here may be situated between the algorithms of Balbo et al and the general purpose algorithms, both in terms of its generality and efficiency.

RECAL, a Re cursion by C hain Al gorithm for computing the mean performance measures of product-form multiple-chain closed queuing networks, is presented. It is based on a new recursive expression that relates the normalization constant of a network with r closed routing chains to those of a set of networks having ( r - 1) chains. It relies on the artifice of breaking down each chain into constituent subchains that each have a population of one. The time and space requirements of the algorithm are shown to be polynomial in the number of chains. When the network contains many routing chains, the proposed algorithm is substantially more efficient than the convolution or mean value analysis algorithms. The algorithm, therefore, extends the range of queuing networks that can be analyzed efficiently by exact means.

A method is described whereby a multiple-class closed network of first-come first-served (FCFS) queues can be analyzed exactly by a decomposition and aggregation procedure that proceeds class by class, rather than node by node. First, the FCFS network is transformed into an equivalent network of processor-sharing queues in which a hierarchy of subsystems associated with subsets of the classes may be identified. This decomposition and aggregation procedure reduces the multiple-class queuing networks into a hierarchy of single-class queueing network problems. The reduced system is constructed containing one particular class of customers. A parametric analysis of this class with respect to the routing can then be made. The time and space requirements of this parametric analysis technique are derived and compared to the requirements of a straightforward repetitive analysis of the network using the convolution algorithm. An example parametric analysis of a store-and-forward communication network model is given.

RECAL, a Recursion by Chain Algorithm for computing the mean performance measures of product-form multiple-chain closed queueing networks, is presented. It is based on a new recursive expression which relates the normalization constant of a network with r closed routing chains to those of a set of networks having (r-l) chains. It relies on the artifice of breaking down each chain into constituent sub-chains that each have a population of one. The time and space requirements of the algorithm are shown to be polynomial in the number of chains. When the network contains many routing chains the proposed algorithm is substantially more efficient than the convolution or mean value analysis algorithms. The algorithm therefore extends the range of queueing networks which can be analyzed efficiently by exact means. A numerical example is given.