The formation of consortiums of a broadband access Internet Service Provider (ISP) and multiple Content Providers (CP) is considered for large-scale content caching. The consortium members share costs from operations and investments in the supporting infrastructure. Correspondingly, the model's cost function includes marginal and fixed costs; the latter has been important in determining industry structure. Also, if Net Neutrality regulations permit, additional network capacity on the ISP's last mile may be contracted by the CPs. The number of subscribers is determined by a combination of users' price elasticity of demand and Quality of Experience. The profit generated by a coalition after pricing and design optimization determines the game's characteristic function. Coalition formation is by a bargaining procedure due to Okada (1996) based on random proposers in a non-cooperative, multi-player game-theoretic framework. A necessary and sufficient condition is obtained for the Grand Coalition to form, which bounds subsidies from large to small contributors. Hence, for the Grand Coalition to form it is necessary to administer Coalition Admission Control. Caching is generally supported even under Net Neutrality regulations. The Grand Coalition's profit matches upper bounds. Numerical results illustrate the analytic results.

We study engineering and business relationships between Content Providers and broadband access ISPs in various organizational and policy environments. We focus on pricing and capacity decisions for bandwidth and caches for delivery of the CP's content over the “last mile” of the ISP's infrastructure. We model the CP-ISP interaction by the Stackelberg “leader-follower” game and the Integrated Operations model. We consider cases where premium bandwidth is offered to subscribers of the CP's service over the last mile, and cases where this is prohibited by Net Neutrality regulations. We develop a uniform solution procedure for all four resulting models. We explore the connections between optimal bandwidth and cache deployments, and, together with fees, their impact on the number of users, and related business and policy topics. We show that the decrease in profitability of caching due to Net Neutrality regulations is greater than the decrease from Integrated Operations to the Stackelberg game. In the Stackelberg game we prove that if a certain condition is satisfied, then with Net Neutrality the ISP will increase the cache price so that it is unprofitable for the CP to use caches. Moreover, this condition is satisfied in a typical case studied in detail.

We present a novel approach for joint optical network provisioning and Internet protocol (IP) traffic engineering, in which the IP and optical networks collaboratively optimize a combined objective of network performance and lightpath provisioning cost. We develop a framework for distributed multilayer optimization. Our framework is built upon the IP-over-optical (IPO) overlay model, where each network domain has a limited view of the other. Our formulation allows the two domains to communicate and coordinate their decisions through minimal information exchange. Our solution is based on a novel application of Generalized Bender's Decomposition, which divides a difficult global optimization problem into tractable subproblems, each solved by a different domain. The procedure is iterative and converges to the global optimum. We present case studies to demonstrate the efficiency and applicability of our approach in various networking scenarios. Our work builds a foundation for "multilayer" grooming, which extends traditional grooming in the optical domain to include data networks. The data networks are active participants in the grooming process with intelligent homing of data traffic to optical gateways

The Internet transport infrastructure is moving towards a model of high-speed router networks that are directly interconnected by re-configurable optical core networks. This IP over optical (IPO) architecture, when coupled with the emerging IP-based generalized multi-protocol label switching (GMPLS) control plane, offers network operators opportunities for dynamic, multi-layer optimization of traffic engineering. We present a novel approach for joint optical network provisioning and IP traffic engineering, in which the IP and optical network domains collaboratively achieve the objective of maximizing the benefit of carrying end-to-end IP traffic at the minimum lightpath design cost. Our approach is developed under the overlay inter-networking model with each network having a limited view of the other. The cooperation is achieved through minimal information exchange. Our solution is based on a novel application of generalized bender's decomposition to implement distributed, multi-layer optimization. The process converges to the optimal value of the objective function. A case study is presented to illustrate the proposed method.

I will describe two networking models, together with their optimization techniques, that span several time scales. In the longest time scale, where the goal is capacity planning, I will describe the work of Bienstock, Raskina, Saniee and Wang that considers joint pricing and network design of optical transport networks. Technological innovations are yielding sharply decreasing unit costs. There is also empirical evidence that suggests that the elasticity of bandwidth demand to price is high. Integrating these features in a unified profit-maximizing model leads to a large- scale nonlinear optimization problem. In this work, efficient solution techniques are developed to maximize the carrier's net present value with respect to pricing strategies and investment decisions for technology acquisitions. In the work of Mitra and Wang the time scale is shorter, the network infrastructure is fixed, and a model for stochastic traffic engineering is given in which the optimization is with respect to bandwidth provisioning and route selection. Traffic demands are uncertain, and the objective is to maximize a risk-adjusted measure of network revenue that is generated by serving demands. Considerable attention is given to the appropriate measure of risk in the network model. Risk-mitigation strategies are also advanced. The optimization model, which is based on mean-risk analysis, enables a service provider to maximize a combined measure of mean revenue and revenue risk. The conditions under which the optimization problem is an instance of convex programming are obtained. The solution is shown to satisfy the stochastic efficiency criterion asymptotically. The efficient frontier, which is the set of Pareto optimal pairs of mean revenue and revenue risk, is obtained.

We present a stochastic traffic engineering framework for optimizing bandwidth provisioning and route selection in networks. The objective is to maximize revenue from serving demands, which are uncertain and specified by probability distributions. We consider heterogenous demands with different unit revenues and uncertainties. Based on mean-risk analysis, the optimization model enables a carrier to maximize mean revenue and contain the risk that the revenue falls below an acceptable level. Our framework is intended for off-line traffic engineering design, which takes a centralized view of network topology, link capacity, and demand. We obtain conditions under which the optimization problem is an instance of convex programming and therefore efficiently solvable. We also study the properties of the solution and show that it asymptotically meets the stochastic efficiency criterion. We derive properties of the optimal solution for the special case of Gaussian distributions of demands. We focus on the impact of demand uncertainty on various aspects of traffic engineering, such as link utilization, bandwidth provisioning and total revenue. The carrier's tolerance to risk is shown to have a strong influence on traffic engineering and revenue management decisions. We develop the efficient frontier, which is the entire set of Pareto optimal pairs of mean revenue and revenue risk, to aid the carrier in selecting an appropriate operating point.

Stochastic traffic engineering for demand uncertainty and risk-aware network revenue management We present a stochastic traffic engineering framework for optimizing bandwidth provisioning and route selection in networks. Traffic demands are uncertain and specified by probability distributions, and the objective is to maximize a risk-adjusted measure of network revenue that is generated by serving demands. Considerable attention is given to the appropriate measure of risk in the network model. We also advance risk-mitigation strategies. The optimization model, which is based on mean-risk analysis, enables a service provider to maximize a combined measure of mean revenue and revenue risk. The framework is intended for off-line traffic engineering, which takes a centralized view of network topology, link capacity and demand. We obtain conditions under which the optimization problem is an instance of convex programming. We study the properties of the solution and show that it asymptotically meets the stochastic efficiency criterion.In our numerical investigations we illustrate the impact of demand uncertainty on various aspects of the optimally traffic engineered solutions. The service provider's tolerance to risk is shown to have a strong influence on the traffic engineering and revenue management decisions. We develop the efficient frontier, which is the set of Pareto optimal pairs of mean revenue and revenue risk, to aid the service provider in selecting its operating point.

A stochastic traffic engineering framework for optimizing bandwidth provisioning and path selection in networks is presented. The objective is to maximize revenue from serving demands, which are uncertain and specified by probability distributions. We consider a two-tier market structure, where demands in the two markets are associated with different unit revenues and uncertainties. Based on mean-risk analysis, the optimization model enables a carrier to maximize mean revenue and contain the risk that the revenue falls below an acceptable level. Our framework is intended for off-line traffic engineering design, which takes a centralized view of network topology, link capacity, and demand. We obtain conditions under which the optimization problem is an instance of convex programming and therefore efficiently solvable. We derive properties of the optimal solution for the special case of Gaussian distributions of demands. We focus on the impact of demand variability on various aspects of traffic engineering, such as link utilization, routing, capacity provisioning, and total revenue.

At the access to networks, in contrast to the core, distances and feedback delays, as well as link capacities are small, which has network engineering implications that are investigated in this paper. We consider a single point in the access network which multiplexes several bursty users. The users adapt their sending rates based on feedback from the access multiplexer. Important parameters are the user's peak transmission rate p, which is the access line speed, the user's guaranteed minimum rate r, and the bound /spl epsi/ on the fraction of lost data. Two feedback schemes are proposed. In both schemes the users are allowed to send at rate p if the system is relatively lightly loaded, at rate r during periods of congestion, and at a rate between r and p, in an intermediate region. For both feedback schemes we present an exact analysis, under the assumption that the users' job sizes and think times have exponential distributions. We use our techniques to design the schemes jointly with admission control, i.e., the selection of the number of admissible users, to maximize throughput for given p, r, and /spl epsi/. Next we consider the case in which the number of users is large. Under a specific scaling, we derive explicit large deviations asymptotics for both models. We discuss the extension to general distributions of user data and think times.

The paper proposes a structure for quality-of-service (QoS)-centered service level agreements (SLA), and a framework for their real-time management in multiservice packet networks. The SLA is structured to be fair to both parties, the service provider and their customer. The SLA considered here are for QoS assured delivery of aggregate bandwidth from ingress to egress nodes; however, the control and signaling is for the more granular flows or calls. A SLA monitoring scheme is presented in which revenue is generated by the admission of flows into the network, and penalty incurred when flows are lost in periods when the service provider is not SLA compliant. In the SLA management scheme proposed, the results of a prior off-line design are used, in conjunction with measurements taken locally at ingress nodes, to classify the loading status of routes. The routing and resource management are based on virtual partitioning and its supporting mechanism of bandwidth protection. The effectiveness of SLA management is measured by the robustness in performance in the presence of substantial diversity in actual traffic conditions. A simulation testbed called D'ARTAGNAN has been built from which we report numerical results for a case study. The results show that the SLA management scheme is robust, fair and efficient over a broad range of traffic conditions.

Generalized processor sharing (GPS) is a scheduling discipline which provides minimum service guarantees as well as fair resource sharing. The performance of GPS is governed by the scheduling weights associated with individual connections. We address the design of the GPS weights, along with the related connection admission control (CAC). Our main goal is to achieve statistical multiplexing gains in the presence of multiple traffic and quality-of-service (QoS) classes of connections that share a common trunk. We present novel techniques to compute and adapt the weights. We also characterize the capacity region of the system, and propose a natural CAC procedure. Numerical results on 2-class and 3-class examples demonstrate the effectiveness of our methods.

Generalized processor sharing (GPS) is the basis for the packet scheduler of choice in IP routers and ATM switches of the future. The currently accepted approach for the design of GPS schedulers is based on deterministic QoS guarantees, which, it is generally accepted, is overly conservative and leads to limitations on capacity. We develop a framework for GPS scheduling which is based on statistical QoS guarantees and statistical multiplexing. We give the design of GPS weights which maximize the coverage of operating points, and also the design of the connection admission control (CAC). The general framework is end-to-end, with two heterogeneous QoS classes coexisting with a third, best effort class. Each QoS class has a specified delay bound together with a bound on the probability of its violation. An important objective is to maximize the bandwidth available to best effort traffic, while just satisfying the guarantees of the QoS classes. To this end, we consider output regulated GPS scheduling, which limits each connection's share of the bandwidth to a designed value. The sources are subject to standard dual leaky bucket regulation. For the design of the GPS weights we give procedures based on two key concepts, the realizable set and the critical weights. The realizable set is the union of all admissible sets of connections of both classes over all weights. One of the main contributions is a pragmatic design process by which most of the realizable set is realized by only two critical weights. The numerical results show that there are substantial capacity gains from statistical multiplexing.

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.

We consider a switching system which has multiple ports that share a common buffer, in which there is a FIFO logical queue for each port. Each port may support a large number of flows or connections, which are approximately homogeneous in their statistical characteristics, with common QoS requirements in cell loss and maximum delay. Heterogeneity may exist across ports. Our first contribution is a buffer management scheme based on buffer admission control, which is integrated with connection admission control at the switch, and is at the same time fair, efficient and robust in sharing the buffer resources across ports. Our scheme is based on the resource-sharing technique of virtual partitioning. Our second major contribution is to advance the practice of discrete-event fluid simulations. Such simulations are approximations to cell-level simulations and offer orders of magnitude speed-up. A third contribution of the paper is the formulation and solution of a problem of optimal allocation of bandwidth and buffers to each port having specific delay bounds, in a lossless multiplexing framework. Finally, we report on extensive simulation results. The scheme is found to be effective, efficient and robust.

We consider virtual partitioning (VP), which is a scheme for sharing a resource among several traffic classes in an efficient, fair, and robust manner. In the preliminary design stage, each traffic class is allocated a nominal capacity, which is based on expected offered traffic and required quality of service. During operations, if the current capacity usage by a class exceeds its nominal allocation, then it is declared to be in "overload," and a state-dependent trunk reservation mechanism gives it lower priority in the admission of new calls. We develop efficient computational algorithms for the case of heterogeneous traffic, and perform extensive numerical experiments to demonstrate the accuracy of the various approximations. The performance of VP is examined and compared to that of complete sharing and complete partitioning. Particular weight is placed on robustness, meaning that traffic classes with arrival rates conforming to the design continue to receive the required quality of service, despite the presence of misbehaving classes with excessive arrival rates. We adopt a reward-penalty paradigm as a combined measure for efficiency and fairness, and show that not only is the revenue generated by VP extremely close to the maximum achievable value, but that the structural form of the optimal policy also closely resembles that of VP. The numerical results confirm that the scheme is efficient, fair, and very robust.

The design of connection admission control (CAC) for a simple Markovian model of a multiservice statistical multiplexer is considered. The paper begins by laying the foundation through several fundamental analytic concepts, such as a semi-Markov decision process formulation of the design problem and time scale decomposition, before progressively leading up to real-world requirements, like robustness and simplicity of design. Several numerical illustrations are given. The salient contributions of the paper are as follows. (1) A unified treatment of multiclass cell and call QoS. (2) A CAC design which is robust, fair, and efficient. (3) Simplicity in the CAC design, together with an evaluation of the tradeoff with performance. (4) An analytic technique for computing the feasibility region in the space of call arrival rates where some control exists to satisfy QoS. (5) The discovery of near linearity of the boundary of the feasible region, which is then used to decompose the design problem. (6) A unified treatment of aggressive and conservative forms of CAC, the latter being conventional and the former yielding better call level performance. (7) An effective bandwidth definition based on the aggressive form of CAC, which influences the CAC design. (8) A demonstration of the beneficial impact on performance of cell level control. (9) An asymptotic theory of the joint behavior of cell loss and call blocking. (10) A rigorous development of time scale decomposition. (11) A numerical evaluation of the accuracy of the notion of nearly completely decomposable Markov chains.

This paper develops a framework of traffic shaping which has the goal of increasing the nodal connection-carrying capacity. The shaping filters are designed to interwork with statistical multiplexers which use FIFO buffers. Differences in delay tolerances between traffic classes are exploited to shape and smooth the less delay sensitive traffic. The source model used in the analysis is asynchronous, worst-case subject to dual leaky bucket regulation, where the asynchrony is due to the assumption of independent sources. This, together with the allowance of small loss probabilities, makes statistical multiplexing feasible. We require the shapers to be lossless so that losses, if any, occur only at the multiplexer. We obtain the optimal design of the shaper such that a given delay tolerance for the connection is satisfied. For purposes of admission control we obtain the admissible region of combinations of sources of various types such that the QoS requirements in loss and delay are satisfied. By examining the regions obtained with and without shaping we quantify the capacity gain from shaping. Our numerical results show that the gain can be substantial.

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.

The main contributions of this paper are two-fold. First, we prove fundamental, similarly behaving lower and upper bounds, and give an approximation based on the bounds, which is effective for analyzing ATM multiplexers, even when the traffic has many, possibly heterogeneous, sources and their models are of high dimension. Second, we apply our analytic approximation to statistical models of video teleconference traffic, obtain the multiplexing system's capacity as determined by the number of admissible sources for given cell loss probability, buffer size and trunk bandwidth, and, finally, compare with results from simulations, which are driven by actual data from coders. The results are surprisingly close. Our bounds are based on Large Deviations theory. Our approximation has two easily calculated parameters, one is from Chernoff's theorem and the other is the system's dominant eigenvalue. A broad range of systems are analyzed and the time for analysis in each case is a fraction of a second.

This paper gives a class of flow control algorithms for the adaptive allocation of bandwidths to virtual connections (VC) in high-speed, wide-area ATM networks. The feedback rate to the source from the network is parsimonious, with each feedback bit indicating whether the buffer at a distant switch is above or below a threshold. The service discipline at the switch is first-come-first-served. The important goal of adaptability aims to make all of the network bandwidth available to the active VCs, even though the number of such VCs is variable over a given range. Each VC has two parameters, one giving its minimum guaranteed bandwidth and the other is the weight for determining its share of the uncommitted bandwidth. Judicious selection of these parameters defines distinctive services, such as best effort and best effort with minimum bandwidth. We derive design rules for selecting the parameters of the algorithms such that the appropriate guarantees and fairness properties are exhibited in the dynamical behavior. The systematic use of "damping" in right proportion with "gain" is shown to be a powerful device for stabilizing behavior and achieving fairness. Our analyses are based on a simple analytic fluid model composed of a system of first-order delay-differential equations, which reflect the propagation delay across the network. Extensive simulations examine the following: (1) fairness, especially to start-up VCs; (2) oscillations; (3) transient behavior, such as the rate of equalization from different initial conditions; (4) disparate bandwidth allocations; (5) multiple paths with diverse propagation delays; (6) adaptability and robustness with respect to parameters; and (7) interoperability of different algorithms.>

The main contributions of this paper are two-fold. First, we prove fundamental, similarly behaving lower and upper bounds, and give an approximation based on the bounds, which is effective for analyzing ATM multiplexers, even when the traffic has many, possibly heterogeneous, sources and their models are of high dimension. Second, we apply our analytic approximation to statistical models of video teleconference traffic, obtain the multiplexing system's capacity as determined by the number of admissible sources for given cell-loss probability, buffer size and trunk bandwidth, and, finally, compare with results from simulations, which are driven by actual data from coders. The results are surprisingly close. Our bounds are based on large deviations theory. The main assumption is that the sources are Markovian and time-reversible. Our approximation to the steady-state buffer distribution is called Chenoff-dominant eigenvalue since one parameter is obtained from Chernoffs theorem and the other is the system's dominant eigenvalue. Fast, effective techniques are given for their computation. In our application we process the output of variable bit rate coders to obtain DAR(1) source models which, while of high dimension, require only knowledge of the mean, variance, and correlation. We require cell-loss probability not to exceed 10/sup -6/, trunk bandwidth ranges from 45 to 150 Mb/s, buffer sizes are such that maximum delays range from 1 to 60 ms, and the number of coder-sources ranges from 15 to 150. Even for the largest systems, the time for analysis is a fraction of a second, while each simulation takes many hours. Thus, the real-time administration of admission control based on our analytic techniques is feasible.>

A new approach to determining the admissibility of variable bit rate (VBR) traffic in buffered digital networks is developed. In this approach all traffic presented to the network is assumed to have been subjected to leaky-bucket regulation, and extremal, periodic, on-off regulated traffic is considered; the analysis is based on fluid models. Each regulated traffic stream is allocated bandwidth and buffer resources which are independent of other traffic. Bandwidth and buffer allocations are traded off in a manner optimal for an adversarial situation involving minimal knowledge of other traffic. This leads to a single-resource statistical-multiplexing problem which is solved using techniques previously used for unbuffered traffic. VBR traffic is found to be divisible into two classes, one for which statistical multiplexing is effective and one for which statistical multiplexing is ineffective in the sense that accepting small losses provides no advantage over lossless performance. The boundary of the set of admissible traffic sources is examined, and is found to be sufficiently linear that an effective bandwidth can be meaningfully assigned to each VBR source, so long as only statistically-multiplexable sources are considered, or only nonstatistically-multiplexable sources are considered. If these two types of sources are intermixed, then nonlinear interactions occur and fewer sources can be admitted than a linear theory would predict. A qualitative characterization of the nonlinearities is presented. The complete analysis involves conservative approximations; however, admission decisions based on this work are expected to be less overly conservative than decisions based on alternative approaches.>

Statistical multiplexing with loss priorities is a central element in ATM-based B-ISDN. Cell priorities arise from the marking schemes employed by the access regulators to identify excess cells, which are dropped during periods of congestion, Also, in real time applications, such as hierarchically coded voice and video, cells are assigned priorities which correspond to their importance to service quality, so that when congestion occurs only the least important are dropped. The authors present a stochastic fluid model of statistical multiplexing with loss priorities. Each Markov modulated fluid source generates streams of different priorities. The burstiness of each stream and the correlation between the priority streams are captured in the mode. The loss priority is implemented by selectively discarding cells of certain priority classes when the buffer content exceeds a corresponding threshold. To handle high dimensional source models, the authors develop an algebraic theory for the efficient computation of the spectrum of the statistical multiplexing system, which generalizes previous results for on-off sources. It is shown that to obtain the solution of the statistical multiplexing problem with J priority classes, J different 1-class problems need to be solved, together with a system of linear equations which describe the behavior of the stationary distribution at the thresholds. The numerical results demonstrate the manner in which i) the threshold level controls the tradeoff between delay of higher priority cells and the loss probability of lower priority cells, and ii) the buffer size controls the loss probability of higher priority cells.>

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.>

A prime instrument for controlling congestion in high-speed broadband ISDN (BISDN) networks is admission control, which limits call and guarantees a grade of service determined by delay and loss probability in the multiplexer. It is shown, for general Markovian traffic sources, that it is possible to assign a notational effective bandwidth to each source which is an explicitly identified, simply computing quantity with provably correct properties in the natural asymptotic regime of small loss probabilities. It is the maximal real eigenvalue of a matrix which is directly obtained from the source characteristics and the admission criterion, and for several sources it is simply additive. Both fluid and point process models are considered, and parallel results are obtained. Numerical results show that the acceptance set for heterogeneous classes of sources is closely approximated and conservatively bounded by the set obtained from the effective bandwidth approximation.>

The aggregated-least-busy-alternative (ALBA), a distributed, state-dependent, dynamic routing strategy for circuit-switched loss networks is discussed. The networks considered are symmetric and fully connected. The offered calls form Poisson streams, and routes have at most two links. In ALBA(K), the states of each link are lumped into K (K>or=2) aggregates, and the route of each call is determined by local information on the aggregate states of the links of the alternate routes at the time of the call's arrival. The last aggregate is always the set of states reserved for direct traffic. A fixed-point model for ALBA(K) for general K is presented. The particular case of ALBA in which there is no aggregation is least busy alternative (LBA); ALBA(2) represents the other extreme of aggregation. Simulation and analytic results for LBA are compared. An asymptotic scaling based on the fixed-point models is also discussed. It is shown that there is a dichotomy in network behavior: if the offered traffic is below a threshold, then the network loss probability decreases exponentially with increasing network size, and above the threshold, performance is poor.>

A prime instrument for controlling congestion in a high-speed network is admission control, which limits calls and guarantees a grade of service determined by delay and loss probability in the multiplexer. It is shown that for general Markovian traffic sources it is possible to assign a notional effective bandwidth to each source that is an explicitly identified, simply computed quantity with provably correct properties in the natural asymptotic regime of small loss probabilities. It is the maximal real eigenvalue of a matrix that is directly obtained from the source characteristics and the admission criterion, and for several sources it is simply additive. Both fluid and point process models are considered. Numerical results show that the acceptance set for heterogeneous classes of sources is closely approximated and conservatively bounded by the set obtained from the effective bandwidth approximation. The bandwidth-reducing properties of the leaky bucket regulator are exhibited numerically.>

The authors give the complete solution for a stochastic fluid model of statistical multiplexing with loss priorities in asynchronous transfer mode (ATM)-based broadband ISDN. In this model each Markov modulated fluid source generates priority and marked cell streams which are bursty, mutually correlated, and periodic during bursts. The output of many such sources is buffered and multiplexed for transmission. The loss priority is implemented by selectively discarding marked cells when the buffer content exceeds a threshold level. The equilibrium state distribution exhibits jumps, a feature not existent in prior fluid models. The computational complexity for two-state sources is dominated by a single system of linear equations of dimension equal to twice the number of sources, in particular, the complexity is independent of buffer size. The complete delay distribution for each traffic class is obtained. Numerical results are given. The analysis is generalized to several priority classes of traffic.>

The basic mechanism of sliding windows for the congestion control of virtual circuits is examined. A problem concerning the optimal design of windows is formulated and formulas for basic quantities of interest, such as throughput, delay and moments of packet queues, in the optimal operating regime as well as in other regimes, are obtained. All results are asymptotic, in which the main parameter is lambda , the delay-bandwidth product. It is shown that K* approximately lambda +O( square root lambda ), where K* is the optimum window size. Also, in the optimal operating regime, the steady-state mean and standard deviation of the queued packets at individual nodes O( square root / lambda ). The design consequences are examined in the contexts of adaptive dynamic windowing, buffer sizing, and shared versus separate buffers in the case of multiple virtual circuits.>

The optimal design of windows for virtual circuits has been studied for high-speed, wide-area data networks in an asymptotic framework in which the delay-bandwidth product is the large parameter. The authors (1990) previously proposed and evaluated a new class of algorithms for dynamically adapting windows in single path, multi-hop networks. Here they develop algorithms for networks having multiple paths with different propagation delays. The source of each virtual circuit (VC) measures the round-trip response time of its packets and uses these measurements to adjust its window with the goal of satisfying certain asymptotic identities that have been proven to hold in stationary asymptotically optimal designs. Also evaluated is the performance of the new adaptive algorithms in realistic, nonstationary conditions by simulations of networks with data rates of 45 Mb/s and propagation delays of up to 47 ms. The simulation results generally confirm that the realizations of the adaptive algorithms give stable, efficient performance and are close to theoretical expectations.>

The performances of two classes of routing algorithms, randomized and deterministic, are evaluated and compared in terms of revenue generated and link failures. The randomized algorithm evaluated is dynamic alternate routing, and for the deterministic algorithm, attempts to carry a call are made in a specific precomputed order. The design of the routing sequences depends upon analytic approximations based on fixed-point equations to evaluate network performance and heuristics for the complicated problem of network revenue maximization. The control mechanism of trunk reservations is shown to play an important role in all cases. The performances of the algorithms were evaluated on a fully connected six-node network, the data for which were extracted from a realistic network. The design tools, time constants of various algorithms, and hybrid algorithms developed using the evaluation results are described.>

The basic mechanism of sliding windows for the congestion control of virtual circuits is examined. A problem of optimal design of windows is formulated and solved, and formulas are obtained for basic quantities of interest, such as throughput, delay, and moments of packet queues, in the optimal operating regime as well as in other regimes. All results are asymptotic in which the large parameter is lambda , the mean number of packets of the virtual circuit which may be processed and transmitted at a single node in an interval equal to the mean propagation delay. It is shown that K* approximately lambda +O( square root lambda ), where K* is the optimal window size. Also, in the optimal operating condition, the steady-state mean and standard deviation of the queue packets at individual nodes are O( square root K*). The constants associated with these asymptotic solutions are oblivious to the minutiae of the physical model and therefore universal; these constants have been computed.>

Recent results on the asymptotically optimal design of sliding windows for virtual circuits in high speed, geographically dispersed data networks in a stationary environment are exploited here in the synthesis of algorithms for adapting windows in realistic, non-stationary environments. The algorithms proposed here require each virtual circuit's source to measure the round trip response times of its packets and to use these measurements to dynamically adjust its window. Our design philosophy is quasi-stationary: we first obtain, for a complete range of parameterized stationary conditions, the relation, called the “design equation”, that exists between the window and the mean response time in asymptotically optimal designs; the adaptation algorithm is simply an iterative algorithm for tracking the root of the design equation as conditions change in a non-stationary environment. A report is given of extensive simulations of networks with data rates of 45 Mbps and propagation delays of up to 47 msecs. The simulations generally confirm that the realizations of the adaptive algorithms give stable, efficient performance and are close to theoretical expectations when these exist.

We study systems consisting of a number of service cells in tandem, each containing a finite buffer. Several policies governing the operation of such systems are described and compared. These include traditional and novel blocking schemes, with applications to computer communications and production lines. In particular, it is shown that kanban, a novel discipline for coordinating cells in a manufacturing context, is obtained by combining two, more basic, concepts: a blocking policy introduced here as minimal blocking, and shared buffers. The Kanban discipline is superior in terms of throughput to the ordinary transfer blocking policy.

This paper gives a simple, accurate first order asymptotic analysis of the transient and steady state behavior of a network which is closed, not product-form and has multiple classes. One of the two nodes of the network is an infinite server and the discipline in the other node is discriminatory processor-sharing. Specifically, if there are nj jobs of class j at the latter node, then each class j job receives a fraction wj/(Σwini) of the processor capacity. This work has applications to data networks. For the asymptotic regime of high loading of the processor and high processing capacity, we derive the explicit first order transient behavior of the means of queue lengths. We also give explicit expressions for the steady state mean values and a simple procedure for finding the time constants (eigenvalues) that govern the approach to steady state. The results are based on an extension of Kurtz's theorem concerning the fluid limit of Markov processes. Some numerical experiments show that the analysis is quite accurate.

Parallel communication algorithms and networks are central to large-scale parallel computing and, also, data communications. This paper identifies adverse source-destination traffic patterns and proposes a scheme for obtaining relief by means of randomized routing of packets on simple extensions of the well-known omega networks. Valiant and Aleliunas have demonstrated randomized algorithms, for a certain context which we call nonrenewal, that complete the communication task in time O (log N ) with overwhelming probability, where N is the number of sources and destinations. Our scheme has advantages because it uses switches of fixed degree, requires no scheduling, and, for the nonrenewal context, is as good in proven performance. The main advantage of our scheme comes when we consider the renewal context in which packets are generated at the sources continually and asynchronously. Our algorithm extends naturally from the nonrenewal context. In the analysis in the renewal context we, first, explicitly identify the maximum traffic intensities in the internal links of the extended omega networks over all source-destination traffic specifications that satisfy loose bounds. Second, the benefits of randomization on the stability of the network are identified. Third, exact results, for certain restricted models for sources and transmission, and approximate analytic results, for quite general models, are derived for the mean delays. These results show that, in the stable regime, the maximum mean time from source to destination is asymptotically proportional to log N . Numerical results are presented.

Given a nonnegative, irreducible matrix P of spectral radius unity, there exists a positive vector π such that π = πP. If P also happens to be stochastic, then π gives the stationary distribution of the Markov chain that has state-transition probabilities given by the elements of P. This paper gives an algorithm for computing π that is particularly well suited for parallel processing. The main attraction of our algorithm is that the timing and sequencing restrictions on individual processors are almost entirely eliminated and, consequently, the necessary coordination between processors is negligible and the enforced idle time is also negligible. Under certain mild and easily satisfied restrictions on P and on the implementation of the algorithm, x(.), the vectors of computed values are proved to converge to within a positive, finite constant of proportionality of π. It is also proved that a natural measure of the projective distance of x(.) from π vanishes geometrically fast, and at a rate for which a lower bound is given. We have conducted extensive experiments on random matrices P, and the results show that the improvement over the parallel implementation of the synchronous version of the algorithm is substantial, sometimes exceeding the synchronization penalty to which the latter is always subject.

A method is presented for calculating the partition function, and from it, performance measures, for closed Markovian stochastic networks with queuing centers in which the service or processing rate depends on the center's state or load. The analysis on which this method is based is new and a major extension of our earlier work on load-independent queuing networks. The method gives asymptotic expansions for the partition function in powers of 1/ N , where N is a parameter that reflects the size of the network. The expansions are particularly useful for large networks with many classes, each class having many customers. The end result is a decomposition by which expansion coefficients are obtained exactly by linear combinations of partition function values of small network constructs called pseudonetworks. Effectively computable bounds are given for errors arising from the use of a finite number of expansion terms. This method is important because load dependence is at once an essential element of sophisticated network models of computers, computer communications, and switching, teletraffic, and manufacturing systems, and the cause of very intensive computations in conventional techniques. With this method, very large load-dependent networks can be analyzed, whereas previously only small networks were computationally tractable.

In this paper a method for calculating the first and higher order moments of the queue lengths for each customer class at each node in a dosed Markovian queuing network is presented.The method is based on asymptotic expansions in powers of N -~ for the moments of interest.N is a parameter that reflects the size of the network.The derivation of the asymptotic expansions presented here is based on the techniques developed by us earlier to get asymptotic expansions in powers of N -a of the mean utilization of each processor by each class of customers.These expansions are valid in the "normal usage" case in which none of the processors are too heavily utilized.These expansions are particularly useful m the ease of large networks with many classes of customers, each class having many customers.With these expansions, we are able to analyze very large networks that earlier were computationally intractable.This is important, because dosed Markovian queuing networks have emerged as one of the most important tools for modeling computer systems, computer communication systems, on-line computer networks and other real-time computer-based system.Previous to the work reported here, their use had been restricted to relatively small networks since their use in large networks involved intractably large calculations.

Locking, although essential in concurrent database processing, also impairs concurrency, and the latter efl~ct is quantified here.The difficult feature in locking is the interference phenomenon, by which we mean that if a particular item in the database is locked, which is true in our model for all constituent items of all transactions undergoing processing, then all arriving transactions requiring this particular item are blocked.The interference phenomenon is exactly modeled and exact formulas for equilibrium database performance, such as mean concurrency and throughput, and efficient algorithms for their computation are obtained.Formulas for large databases are derived and proved to be asymptouc; this formula is insightful, and found to fit well to exact solutions.The probabilistic model is a Markov process with combinatorial quantities as transition rates.This model is tractable because of the time reversibility of the equilibrium Markov process.In a database with Nitems and p transaction classes, the probabilistic model has O(N p) states, time reversibility reduces the calculations to evaluating the sum of O(N p) terms, the recurrence formulas that are derived here require O(Np) multiplications, and, finally, the asymptotic formula requires negligible computation.

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.

The paper contains a proposal and an analysis of a hybrid method for synchronizing the clocks in a digital switching network to a more select group of "master clocks." The scheme is a hybrid of two well-known techniques, "mutual synchronization" and "masterslave," offering certain unique advantages. It allows different synchronizing disciplines for the masters (such as the toll switching machines) and the remaining subnetwork (composed, for example, of local switches). We begin by considering an idealized model containing only one master with constant clock frequency. The behavior of the controlled frequencies in the subnetwork is described by linear delay-differential equations with the delays determined by distances separating switches. We show that in all cases all clocks in the subnetwork approach in steady state the master clock frequency. Considerable emphasis is placed on the rate of synchronization, as determined by the principal root, the root with largest real part, of the characteristic function of the differential equations. The idealized model is extended in stages. First we consider the effects of many masters with constant but possibly nonidentical frequencies and show that the steady state frequencies in the subnetwork are narrowly bounded. Next, we allow clock drift and the master clocks to fluctuate about nominal centers with given tolerances. An expression for the residual steady-state departures from perfect synchronization shows the tradeoff between transient and stead-state behavior. Finally, two illustrative examples are numerically solved.

To cope with the effects of channel errors, robust adaptive quantization schemes contain a leakage parameter in the step size adaptation algorithm. Unfortunately, this mechanism also introduces its own distortion. A method for compensating for the leakage-induced distortion is proposed here. It consists of a quite novel generalization of the adaptive quantizer with the novelty contained entirely in the decoding procedure. The generalization is illustrated by a PCM and a DPCM example. In both examples the generalized systems perform consistently better than existing systems and give improvements in SNR of about 100% for signal intensities at the extremities of a 50 dB range.

A considerable amount of information regarding the behavior and performance of robust adaptive quantizers is contained in the functionC(\sigma)which denotes the dependence of the central (or typical) step size,C, on the intensity, σ, of the input random variables. The graphical representation ofC(\sigma)is called the load curve. It is quite remarkable that plots of logC(\sigma)are found to be almost linearly dependent on log σ. One of our contributions is to show that this linearity follows from an unusual, but quite effective, approximation to the Gaussian and Laplacian distributions of the input random variables. The central result is a quite explicit expression for the functionC(\sigma), and thus for the load curve, derived from the aforementioned approximation:\log C(\sigma) = S \log \sigma + T. The quantitiesSandTare explicitly given in terms of the various fixed parameters of the system. The expression forSprovides insight into the tradeoffs between the dynamic range of the step size, the robustness in the presence of channel errors and the ability to track changes in the signal intensity σ.

To cope with the effects of channel errors, robust adaptive quantization schemes contain a leakage parameter in the step-size adaptation algorithm. Unfortunately, this mechanism also introduces its own distortion in the form of reduced dynamic range of the step size which causes the signal-to-noise ratio to drop appreciably at the far ends of the range of input signal intensities typically associated with speech applications. A method for compensating for the leakage-induced distortion is proposed here. It consists of a generalization of the adaptive quantizer with the novelty contained entirely in the decoding procedure. Whereas the reconstruction or decoded values in existing adaptive quantizers are proportional to the adapted step size, with the prespecified and fixed reconstruction parameters\{\eta_{r}\}giving the constants of proportionality, the generalization will have these parameters replaced by reconstruction functions\{\eta_{r}(\bullet)\}of the time-evolving step size. The sole time-varying parameter in the generalized quantizer is, as originally, the step size which is adapted in exactly the same manner as in existing robust quantizers. Two straightforward methods for the synthesis of the reconstruction functions are presented. The first is analytic while the second is a method for generating the functions through simulations. Computed results for two examples are presented. In the first example, the input signals are independent, Gaussian random variables. In the second example, the inputs are correlated and generated by a first-order Markov model. The communication system is adaptive differential PCM. In both examples, the generalized systems perform consistently better than existing systems and give significant improvements in SNR for signal intensities at the extremities of a 50 dB range.

A variety of theoretical results are derived for a well-known class of discrete-time adaptive filters. First the following idealized identification problem is considered: a discrete-time system has vector inputx(t)and scalar outputz(t)= h \' x(t)wherehis an unknown time-invariant coefficient vector. The filter considered adjusts an estimate vector\hat{h}(t)in a control loop according to\hat{h}(t + \Delta t) = \hat{h}(t) + K[z(t) - \hat{z} (t)]x(t), where\hat{z}( t)= \hat{h}( t) \' x( t)andKis the control loop gain. The effectiveness of the filter is determined by the convergence properties of the misalignment vectorr(t) = h - \hat{h}(t). It is shown that a certain nondegeneracy "mixing" condition on the Input { x(t)} is necessary and sufficient for the exponential convergence of the misalignment. Qualitatively identical upper and lower bounds are derived for the rate of convergence. Situations where noise is present inz(t)andx(t)and the coefficient vectorhis time-varying are analyzed. Nonmixing inputs are also considered, and it is shown that in the idealized model the above stability results apply with only minor modifications. However, nonmixing input in conjunction with certain types of noise lead to bounded input - unbounded output, i.e., instability.

Recently, we have shown that a necessary and sufficient condition for uniform convergence in a well-known class of digital adaptive filters is that the inputs satisfy a 'mixing condition'. In the case of mixing inputs, system noise, or errors incurred in the digital implementation, with bounded size, can produce only bounded behavior of the filter. We show here that, in many applications, inputs may be expected not to mix. We analyze the effects of two specific types of implementation errors in both the mixing and nonmixing cases. We show that arbitrarily small bounds on each type of error leads to unbounded behavior of the filter if the input is nonmixing and both types of errors are present. However, if only one type of error is present, then unbounded behavior does not occur if the error is small.

The diffusion of an innovation such as a new communication service is modeled using a randomly generated network of interpersonal influence between members of a social system. Each member decides to adopt the innovation when K out of his particular set of L influencers have already become adopters. A discrete-time recursion is obtained which describes the evolution in time of the fraction of adopters. The model exhibits a critical mass effect, where the number of initial adopters must exceed a critical value for the diffusion to saturate the population, otherwise the diffusion ends prematurely without substantial growth. Also exhibited is a bandwagon effect, which explains a sudden upsurge in growth following an initial period of slow diffusion. Both phenomena are amply corroborated by Monte Carlo simulations for a population of 10 000 people.

A class of demand paging algorithms for some two-level memory hierarchies is analyzed. The typical memory hierarchy is comprised of the core and a backing device. A distance matrix characterizes the properties of the latter device. The sequence of address references directed to the hierarchy by the CPU and channels is modeled as a Markov process. A compact expression for the mean time required to satisfy the page demands is derived and this expression provides the basis for some optimization problems concerning partitionings and rearrangements of pages in the backing device. In connection with these problems, a class of random processes is defined in terms of an ordering property of a joint probability matrix which is central to memory hierarchies. Three results are given on the ordering property, its relation specifically to partitionings inherent in hierarchies and the problem of optimal rearrangements. Finally, for such a class of ordered processes, certain results due to the author are specialized to yield the solution to the problem of optimal rearrangement of pages on an assembly of magnetic bubble loops.