We consider the resource allocation problem in the design of intranets or virtual private networks (VPNs) that is faced by a service provider, which has service level agreements with various customers to carry their multiservice traffic. The design allocates bandwidth on each link to the VPNs such that, when the traffic of a customer is optimally routed over its VPN, a weighted aggregate measure of carried bandwidth over the service provider's infrastructure is maximized, subject to constraints that each VPN carries a specified minimum. Multiplexing is across services and routes within each VPN, but not across VPNs. The traffic modelling is at the flow or call level, with random arrivals and holding times of calls and each call requiring (effective) bandwidth, which is characteristic of the call's service type, on all links in its route. The network is modelled as a multirate loss network. Scalability of the design process, i.e., the ability to handle OC3 and higher rates, is an important contribution, and this is achieved by the systematic use of a refined uniform asymptotic approximation. Our software package VPN DESIGNER incorporates these results. We report on numerical results for problems with up to 8 VPNs on a network with 8 nodes, 24 OC3 links, 5 services and up to 640 routes.

ATM network design and optimization at the call-level may be formulated in the framework of multirate, circuit-switched, loss networks with effective bandwidth encapsulating cell-level behavior. Each service supported on the ATM network is characterized by a rate or bandwidth requirement. Future networks will be characterized by links with very large capacities in circuits and by many rates. Various asymptotic results are given to reduce the attendant complexity of the numerical calculations. A central element is a uniform asymptotic approximation (UAA) for link analyses. Moreover, a unified hybrid approach is given which allows asymptotic and nonasymptotic (exact) methods of calculations to be used cooperatively. Network loss probabilities are obtained by solving fixed point equations. A canonical problem of route and logical network design is considered. An optimization procedure is proposed, which is guided by gradients obtained by solving a system of equations for implied costs. Finally, we report numerical results obtained by the software package TALISMAN, which incorporates the theoretical results. The network considered has 8 nodes, 20 links, 6 services and as many as 160 routes.

Asynchronous transfer mode (ATM) network design and optimization at the call-level may be formulated in the framework of multirate, circuit-switched, loss networks with effective bandwidth encapsulating cell-level behavior. Each service supported on the (wide area, broadband) ATM network is characterized by a rate or bandwidth requirement. Future networks will be characterized by links with very large capacities in circuits and by many rates. Various asymptotic results are given to reduce the attendant complexity of numerical calculations. A central element is a uniform asymptotic approximation (UAA) for link analyses. Moreover, a unified hybrid approach is given which allows asymptotic and nonasymptotic methods of calculations to be used cooperatively. Network loss probabilities are obtained by solving fixed-point equations. A canonical problem of route and logical network design is considered. An optimization procedure is proposed, which is guided by gradients obtained by solving a system of equations for implied costs. A novel application of the EM algorithm gives an efficient technique for calculating implied costs with changing traffic conditions. Finally, we report numerical results obtained by the software package TALISMAN, which incorporates the theoretical results. The network considered has eight nodes, 20 links, six services, and as many as 160 routes.

We consider a basic teletraffic model, which has applications to integrated multirate services on ATM and wireless systems. In the "finite-sources" version of the model an unbuffered resource with C channels is shared by heterogeneous sources which alternate between arbitrarily distributed random periods in the on and off states, and in the on state require a fixed number of channels. If a source does not find enough free channels when it turns on, then it is blocked and the burst is lost. In the "infinite-sources" version of the model requests for connections form Poisson streams and connections hold fixed numbers of channels for random periods. The stationary distribution of the system has the product-form and the insensitivity property. Our main results for the finite-sources model are for the asymptotic scaling in which C and the number of sources of each type are large. The central result is a uniform asymptotic approximation (UAA) for the blocking probabilities. It is uniformly effective for the complete range of loadings, simple to calculate and gives accurate results even for relatively small systems. The UAA is also specialized to the overloaded, critical and underloaded regimes. For the admission control of the system we calculate its Erlang capacity, i.e., the set of combinations of sources of various types such that the blocking probabilities for all types do not exceed specified values. For the first two regimes we obtain the boundaries of the admissible sets in the form of hyperplanes, and thus the effective bandwidths of sources of each type. For the underloaded regime the boundary is nonlinear and we obtain a convenient parameterized characterization. Finally, various numerical results are presented.>

Hashing with lazy deletion is a simple method for maintaining a dynamic dictionary: items are inserted and sought as usual in a separate-chaining hash table; however, items that no longer need to be in the data structure remain until a later insertion operation stumbles on them and removes them from the table. Because hashing with lazy deletion does not delete items as soon as possible, it keeps more items in the dictionary than methods that use more careful deletion strategies. On the other hand, its space overhead is much smaller than those more careful methods, so if the number of extra items is not too large, hashing with lazy deletion can be a practical algorithm when space is scarce. In this paper, we analyze the expected amount of excess space used by hashing with lazy deletion.

An interactive computer system’ service is characterized by the random waiting (or response) time perceived by users. This paper presents a novel solution to the problem of efficiently computing the second moment of the waiting time of a class of large interactive systems. The physical system consists of a bank of terminals, each of which asynchronously alternates between “thinking” and waiting for service from a CPU which operates under the processor-sharing discipline. The problem of obtaining higher order waiting time moments is quite different from that of obtaining CPU queue statistics. Only the first moment of the waiting time is obtainable from the CPU queue statistics. The technique for arriving at the second moment of the waiting time consists of developing an asymptotic expansion in inverse powers of the number of terminals. Hence, as the system grows, quite fortuitously, fewer terms of the series require computation to achieve the desired accuracy. Beside its numerical advantages, the results give new insight since the leading terms of the series, which contain most of the information, are obtained explicitly. The novelty also rests on the fact that instead of solving matrix equations, the problem is turned into one of solving a second order differential equation. A simple two-dimensional recursion yields all the terms of the asymptotic expansion.

A discrete-time queueing problem involving two queues in tandem, with unit service time, is considered. Such a situation can arise within a packet-switching network. Arrivals at the queues occur from separate sources, which may be correlated. The joint arrivals from the two sources are assumed to be independently and identically distributed in each unit time interval. In addition, the output of the first queue enters the second queue. Both queues are assumed to have unlimited size, and the generating function of the steady state distribution of the two queue lengths is calculated, under the assumption that the mean combined input rate from the two sources is less than unity. The average waiting times are also derived, under the assumption that all arrivals take place at the end of a unit time interval. A particular example, in which the input to the first queue is geometrically distributed in each unit time interval, while the input from the source into the second queue is either 0 or 1, with fixed probabilities, is analyzed. The steady state probability that the length of the second queue exceedsmis calculated. The asymptotic behavior form \gg 1changes significantly when a certain threshold, depending on the mean input rates, is reached. Numerical results are presented.