Waveband routing and wavelength assignment (WRWA) has only recently attracted attention from the optical networking industry for its practical importance in reducing the control complexity and cost of optical cross-connects (OXCs). In this paper, we study WRWA tasks in hybrid hierarchical wavelength division multiplexing (WDM) networks with OXCs that can route multiple granularity (wavelengths and wavebands) at the same time. We develop a unique integer linear programming (ILP) model of a network with those OXCs with the objective to minimize the cost of optical-electronic-optical (OEO) and all optical (OOO) ports used. The optimal ILP solution can only be obtained for networks of smaller size. For larger problems we use a heuristic WRWA algorithm which was presented in our earlier work. Simulation results in this paper show near optimal performance of the heuristic WRWA algorithm for networks of smaller size.

We study routing and wavelength assignment (RWA) tasks in WDM mesh networks with wavelength conversion capabilities. For each lightpath request, we solve the routing and wavelength assignment sub-problems as a single problem, rather than separating them into two separate problems. We use four different optimization criteria: (1) minimum number of wavelength conversions; (2) minimum number of wavelengths used; (3) minimum hop count; (4) minimum use of scarce resources (trunking). Each of these problems is solved by a Dijkstra type of algorithm, executed sequentially on one request at a time. We also develop an integer linear programming (ILP) model with the objective of minimizing the number of wavelength conversions. The optimal ILP solution can only be obtained for small networks. We conduct a comprehensive simulation study of the performance of the algorithms for different network topologies and traffic scenarios.

Recently, a new global open Ethernet (GOE) architecture was proposed as a cost-effective scalable solution for the next generation of VPNs over an optical network infrastructure. In this paper, we present a traffic engineering design for networks that support the GOE architecture. The current extensions of the spanning tree protocol (STP), such as rapid spanning tree (RST) and multiple spanning tree (MST), use a link cost metric which is inversely proportional to the link capacity. In order to achieve a better load balancing in the network, we propose to use the link cost metric which is a function of the current link load. The traffic engineering algorithms presented in this paper use two different link cost functions. We comment on the performance of those heuristic algorithms for various network topologies and under several traffic scenarios. Our results demonstrate a significant improvement in the network utilization when the link cost metric is a function of the link load compared to the case when it is inversely proportional to the link capacity.

In this paper, we study the routing and wavelength assignment (RWA) tasks in WDM mesh networks with wavelength conversion capabilities. We solve the routing and wavelength assignment sub-problems as a single problem, rather than separating them into two separate problems. We use two different optimization criteria: (1) minimize the number of wavelength conversions used; and (2) minimize the number of wavelengths used. Each of these problems is solved by using a method based on the Dijkstra algorithm, sequentially on one connection at a time. We study and comment on the performance of the algorithms for different network topologies and traffic scenarios.

In this paper, we study the routing and wavelength assignment (RWA) tasks in WDM rings with heterogeneous wavelength conversion capabilities. By heterogeneous, we mean that different nodes of the WDM ring might have different wavelength conversion capabilities. An integer linear programming (ILP) formulation is used to optimally solve small examples of the problem. Because many RWA problems have exponential complexity, efficient heuristics are needed. We use the results from the ILP to evaluate the performance of several fast RWA algorithms, which are shown to give accurate solutions under various traffic scenarios.

In this paper, we propose a technique for reducing asynchronous transfer mode (ATM) call blocking which is achieved by splitting wide-band connections into multiple low-bandwidth subconnections and routing them independently through the network. The essence of the mechanism is to use fragmented network bandwidth for supporting calls which are otherwise blocked by conventional routing. ATM bandwidth fragmentation may take place in a situation when a connection occupies a part of a link bandwidth and the rest of it is not sufficient for another connection. The unused bandwidth becomes fragmented. We provide a detailed cell-level design for the split-scheduling algorithms, which use a special type of ATM resource management cell for maintaining cell ordering. The analysis and simulation of the scheduling algorithms show that connection splitting is capable of delivering acceptable cell-level quality of service to multiple traffic classes. We also deliver a solution for implementing splitting without requiring any protocol changes within the network. We show that it is sufficient to modify the data and control plane protocols only within the end stations. Finally, a set of routing-level simulations for splitting demonstrates that splitting can reduce blocking by up to 45% for high-bandwidth calls in a moderately loaded network. Considering that it does not incur any network expenses or protocol changes, we propose splitting as an efficient means for reducing connection blocking.

We propose a new private network-to-network interface (PNNI) aggregation algorithms for hierarchical ATM networks. Standard PNNI routing provides a scalable hierarchical routing capability to support a large ATM network, and its hierarchy mechanism can decrease the network complexity significantly. However, in order to support effective QoS-based routing across foreign subnetworks, the topology aggregation mechanism, representing the lower level network topology to higher level, becomes a key issue. PNNI specification defines general notions of this aggregation mechanism, leaving enough opportunities for subnetwork administrators to choose the amount of aggregated information that they advertise. So far, no feasible PNNI compliant algorithms have been proposed. We propose a new three step aggregation scheme to solve the problem. We evaluated the proposed scheme, based on large-scale simulations with different network topologies, traffic scenarios, and performance metrics. The proposed scheme delivers good network performance while significantly reducing the network complexity.

A new service class, called VBR/sup +/ has been proposed for multimedia applications on ATM networks. VBR/sup +/ extends the functionality of the traditional VBR service with the added capability of dynamic resource renegotiation. It makes the specification and modification of the usage parameter controls flexible, and potentially can increase the network resource utilization through statistical multiplexing. These advantages come at the expense of a more complex connection admission controller which should be designed to handle bandwidth renegotiation efficiently. A connection admission controller for the VBR/sup +/ service class is proposed. We identify the desirable features of a VBR/sup +/ connection admission controller, and present a novel one that can achieve them through (1) dynamic resource partitioning, and (2) dynamic resource redistribution among active connections. Simulation results showing the performance of the controller using a number of actual video traces are presented. The results show that the controller is robust in admitting a variety of video sources with widely different traffic burstiness. By partitioning the resource pool dynamically, and distributing resources among contending connections fairly, it can maintain very good quality, and can achieve high utilization. Comparison with the traditional VBR service reveals that the CAC is able to provide comparable quality with higher network utilization.

For multirate wireless ATM traffic, the first part of the call admission process is to determine whether to admit calls as long as bandwidth is available or to deny admission to a call of a particular class even if there is enough bandwidth available, in the hope of admitting calls of some other class later. A second part of the process is to determine if the quality of service requested by the call can be met. A scenario in which the first part is particularly important is when the blocking probability requirements for different classes are different. We consider four policies to determine the circumstances under which calls of different types are admissible. For each of these policies, we show how to compute the blocking probabilities. For three of these policies, the blocking probabilities can be found by using results from product form networks. For the fourth, we provide an approximation which works extremely well in practice. We also formulate a non-linear programming problem which attempts to determine the parameters of the admissibility policies in such a way to maximize the call arrival rates while keeping the blocking probabilities under specified bounds. We provide an algorithm for solving the non-linear programming problem and use this as a basis for comparing the policies. We show that under some circumstances, it is possible to improve the system throughput by as much as 35% by a suitable use of the admissibility policies. This improvement in throughput is particularly important in wireless ATM networks, supporting high rate multimedia traffic because of the inherent limitations in bandwidth availability.

Current designs of high-speed networks assume that all customers are tolerant of some amount of losses. However, it is possible that some applications may require very high reliability, and would be willing to pay more for it, if such a service were available. Motivated by this, we propose a design of a hybrid network which can guarantee zero cell loss probability for type 1 traffic while allowing some losses for type 2 traffic. This paper has three contributions. Our first contribution in this paper is to propose a service discipline (which can be implemented easily on a specific switch architecture) which guarantees zero losses for type 1 traffic. Our second contribution is to propose an algorithm for a scheduling strategy which reduces the number of buffers required at the output pods of the switches to zero for type 1 traffic. Our last contribution is to solve a difficult queueing problem involving service interruptions, which characterizes the performance of type 2 traffic.

One limitation on the operating speed of electronic circuits is the rate at which the packaging can dissipate heat. In CMOS technology, the heat generated by a processor is approximately proportional to its clock rate. The paper examines the idea of using a variable speed processor (VSP) that can be operated at a high clock speed, and then slowed down to a lower speed before heat accumulation destroys the circuit. Under a workload consisting of bursts of work alternating with idle periods (corresponding to cache misses or other delays), this results in a higher average operating speed. The paper shows the optimality of a bang bang control for the clock rate. It also examines an easier to implement policy that estimates the junction temperature through an upper bound, and uses this to control the clock rate. Closed form expressions are derived for the mean rate of instructions executed by a VSP using each control method. Numerical studies show that both policies give substantial improvements in performance over a single speed processor. Furthermore, the studies suggest that a VSP with a maximum clock rate of 2-4 times that of the single speed processor would suffice to obtain the bulk of the performance improvement. In many cases, the average throughput gain is on the order of 40-60%, without exceeding thermal limits.

Considers a problem of network design of personal communication services (PCS). The problem is to assign cells to the switches of a PCS network in an optimum manner. The authors consider two types of costs. One is the cost of handoffs between cells. The other is the cost of cabling (or trunking) between a cell site and its associated switch. The problem is constrained by the call volume that each switch can handle. The authors formulate the problem exactly as an integer programming problem. They also propose a heuristic solution for this problem and show that it performs extremely well.>

Considers a problem of network design of personal communication services (PCS). The problem is to assign cells to the switches of a PCS network in an optimum manner. The authors consider two types of costs. One is the cost of handoffs between cells. The other is the cost of cabling (or trunking) between a cell site and its associated switch. The problem is constrained by the call volume that each switch can handle. They formulate the problem exactly as an integer programming problem. They also propose three heuristic solutions for this problem and show that two of them perform extremely well.>

One purpose of a traffic shaping mechanism (such as the leaky bucket) is to smooth out an input process into an output process. In so doing, a question of interest is the following: to what extent has the input process been modified, or, to what extent does the output process conform to the input process? To this end, the authors define and characterize a conformance measure. They apply this idea to a leaky bucket in a high-speed network in which this issue may arise naturally. They show how to find the conformance measure for a leaky bucket with the Markovian arrival process.>

The letter considers modeling methodologies of variable bit-rate (VBR) video sources for performance evaluation of integrated networks. The authors consider an example in which compressed H.261 standard VBR video is transmitted over a local area network carrying both video and data. A group-of-block (GOB) level source model has been constructed using TES (transform-expand-sample)-a new general methodology for generating stationary autocorrelated time series, which can simultaneously capture a prescribed marginal distribution and autocorrelation function. The TES model is used to drive CSMA/CD network simulations for a performance evaluation study. Numerical comparisons with a conventional autoregressive (AR) modeling approach are given.>

In broadband ISDN, different classes of traffic expect to receive different quality of service. One way of providing service is to implement a priority structure among traffic classes. The authors analyze a single server queue in which video and voice traffic receive priority over data traffic. Corresponding to the fixed cell size of ATM, they assume that service times are deterministic. They further assume that the high priority traffic is correlated and the arrivals are governed by a Markov chain. With these assumptions, they characterize the queue length distributions and the waiting time distributions for this problem. They show by numerical examples that the delay distribution depends highly on the correlations and that a priority service discipline is capable of providing very good service for real time traffic.>

The notion of perceptible degradation of quality of the received signal seen by an individual user is introduced. It is proposed that the design of high-speed networks that support real-time traffic be carried out on the basis of a new performance measure, which is defined as the expected number of perceptible degradations that a customer is likely to encounter per unit of time. By using fluid-flow models, an analytical methodology is obtained for calculating the new performance measure. The method is illustrated by representative numerical examples from voice and video traffic for various link speeds and buffer sizes.>

The authors present a predictive congestion control policy for carrying data traffic in the presence of real-time traffic that has stringent delay requirements, such as voice and video traffic. The predictive policy attempts to predict the buffer content of a node at some time in the future. The policy is based on information exchange between adjacent nodes of the network. The cross traffic is characterized by its mean rate, its variance, and the correlation, and the performance of the scheme is studied over a wide range of cross traffic parameter values. The effect of higher link speeds and larger propagation delays on the performance is studied. The predictive policy is compared to other policies. The investigation shows that predictive control policy performs significantly better than static or adaptive end-to-end rate control policies.>

A variable-bit-rate (VBR) MPEG video compression encoder is introduced, and the performance of a statistically multiplexed asynchronous transfer mode (ATM) network supporting a number of such VBR video sources is evaluated. Bit-rate characteristics obtained from a detailed simulation are provided for a VBR MPEG encoder for CCIR601 video (operating in the 5-10 Mb/s regime) appropriate for medium-quality multimedia or broadcasting applications. The results presented include bit-rate traces and signal-to-noise-ratio data for typical test sequences, along with summary statistics such as the marginal distribution of frame rate. Data from a study of statistical multiplexing on an ATM network are also given. Simulation results for an ATM statistical multiplexer with N>>1 VBR MPEG sources are presented in terms of key performance measures such as cell loss rate and delay versus throughput. The results confirm that ATM channel efficiencies of approximately 80-90% can be obtained at reasonable cell loss rate and delay levels.>

A threshold-based priority scheme in which a tuning parameter is used to provide adequate quality of service to real-time traffic while providing the best possible service to the non-real-time traffic is proposed. The priority scheme is a generalization of the static priority scheme and the one-limited scheme and is more flexible than both. For this scheme, the authors carry out a queueing analysis and obtain the joint distribution of the queue-lengths. They show by numerical examples how the parameter of this scheme can be tuned dynamically, so that the tuning function can be integrated with the call admission policy.>

The authors examine the behavior of a source subject to flow control by a credit manager. The source receives packets for transmission into a high-speed network according to a renewal process. The credit manager regulates the flow of data into the network by the following method. First, credit is generated at a fixed rate and is allowed to accumulate subject to an upper bound. Second, a packet is allowed to start transmission only if the accumulated credit is at least as large as the service time of the packet. Otherwise, the packet waits until the required amount of credit has been accumulated. Third, the credit bank is depleted at the onset of service by an amount which equals the service time. The main purpose of the credit manager is to smooth out the burstiness of the input process, thereby making it easier for the network to handle large amounts of data without undue delays, congestion, or buffer overflows. Despite the difficulty of this problem, the authors find the distributions of queue length, sojourn time, and interdeparture time by assuming a special structure for the service-time distribution and the credit bank. Numerical examples are included.>

The authors examine the behavior of a source subject to flow control by a credit manager. The source receives packets for transmission into a high speed network according to a renewal process. The credit manager regulates the flow of data into the network by the following method. First, credit is generated at a fixed rate and is allowed to accumulate, subject to an upper bound. Second, a packet is allowed to start transmission only if the accumulated credit is at least and as large as the service time of the packet. Otherwise, the packet waits until the required amount of credit has been accumulated. Third, the credit bank is depleted at the onset of service by an amount which equals the service time. The main purpose of the credit manager is to smooth out the burstiness of the input process, thereby making it easier for the network to handle large amounts of data without undue delays, congestion, or buffer overflows. Despite the difficulty of this problem, the distributions of queue length and sojourn time are found by assuming a special structure for the service time distribution and the credit bank. Numerical examples show that the algorithms can be used to solve practical problems.>

The authors consider modeling methodologies of variable-bit-rate video sources for performance evaluation of integrated networks. They consider an example in which compressed video is transmitted over a local area network carrying both video and data. A new modeling methodology called transform-expand-sample (TES) which is a method for generating autocorrelated variates, is used. TES is a nonparametric method which can accurately capture the histogram and approximate autocorrelation function of any data set. The TES model was used to drive a network simulation for performance measures.>

The authors develop a new analytic model for a variable bit rate video source, which can model a variety of video applications by a suitable choice of model parameters. Using the model they studied the performance of a video multiplexer that multiplexes several full motion video sources. The video sources were assumed to use a layered coding technique. A service strategy is proposed that guarantees delivery of packets marked essential, whereas nonessential packets may be dropped in the event of congestion. The study showed that with layered coding, good tail probabilities can be obtained for a given number of sources at the expense of some loss for nonessential packets. The performance of the video multiplexer was investigated when the video sources were correlated, and when independent video sources with different thresholds for essential packet rate were multiplexed together.>

In this paper, we examine a problem which is an extension of the limited service in a queueing system with a cyclic server. In this service mechanism, each queue, after receiving service in cycle j, makes a reservation for its service requirement in cycle j + 1. In this paper, we consider symmetric case only, i.e., the arrival rates to all the queues are the same. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.

In this paper, we consider the performance of a node in a high speed network which is subject to a threshold type of feedback control policy.We obtain the loss probability and throughput at the node as a function of round-trip propagation delay and buffer size.These parameters are critical in high speed networks.We show that the simple feedback control policy is effective only when the ratio of propagation delay to job transmission time is not too large.Otherwise, a simple static "open-Icmp" control policy, which does not rely on constant exchanges of state information, can perform better.

A packet multiplexer is modeled for continuous bit rate (CBR) traffic in an asynchronous transfer mode (ATM) network as an nD/D/1 queue. The efficiencies of various algorithms for finding the delay distribution are compared. In particular, a new algorithm is proposed whose time complexity is O(n/sup 2/), where n is the number of voice sources being multiplexed. The use of the central limit theorem can reduce the time complexity to O(n) for large n. An asymptotic formula is found whose time complexity is independent of n and it works well (for practical purposes) over a wide range of parameter values. The authors examine and comment on the use of the M/D/1 results as an approximation. In addition to comparing the performances of these algorithms, they show that the buffer requirements for such a queue are significantly less than the theoretical maximum (even when the requirement on the call disruption probability is very low). This result has important implications in the design of buffer size. The buffer requirement is relatively insensitive to the design criterion (call disruption probability).>

The performance of a statistical multiplexer whose inputs consist of a superposition of voice packet streams is studied. The delay for such a system is analyzed by solving the Sigma D/sub i//D/1 queue. The analytic method can be used to find the approximate mean delay for an arbitrarily large number of trunks and the approximate delay distribution when the number of trunks is less than 100. An efficient hybrid simulation of the packet voice multiplexer which can be used to find the delay distribution for a large number of trunks is presented. In addition, easily computable error bounds for the present approximation are provided, and the accuracy of the M/D/1 approximation is investigated.>

This paper describes a hybrid model, combining both analytical and simulation techniques, which was developed to study the performance of a netted computer based system. The computer based system that was modeled is the Facility Assignment and Control System (FACS). This system is presently being deployed within several Bell Operating Companies to inventory and assign central office and outside plant facilities. A key feature of the model is its ability to characterize the dynamic nature of FACS. An understanding of this dynamic nature is necessary in establishing important operational guidelines such as allowable CPU utilization, levels of multiprogramming and priority of transaction processing. In addition, the model allows the user to investigate the sensitivity of the system to a wide range of conditions. Typical study items could include the effect of various load scenarios, ability of the system to meet performance objectives, and different hardware configurations. As part of this paper, both the practical aspects of modeling a netted computer based system and the theoretical development of the hybrid model are considered.