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.

Large-scale location, sizing and homing problems of distributed network elements, have received much attention recently due to the massive deployment of broadband communication networks for services like Internet telephony and Web caching. Key considerations in designing these networks include modularity of capacity, economies of scale in cost, and reliability. We formulate a general class of such network design problems as Mixed-Integer Programs. These problems are computationally intractable in general; under various asymptotic conditions, we show how to compute near-optimal solutions. To deal with arbitrary instances, we develop new algorithms based on linear programming, as well as greedy randomized adaptive search. These algorithms achieved near-optimal solutions with reasonable computation time for our experiments.

In this paper we describe an efficient algorithm for the constrained shortest path problem which is defined as follows. Given a directed graph with two weights on each link e, a cost l/sub e/, and a delay t/sub e/, find the cheapest path from a source to all destinations such that the delay of each path is no more than a given threshold. The constrained shortest path problem arises in quality-of-service-sensitive routing in data networks and is of particular importance in real time services. The problem formulation and the algorithmic framework presented are quite general; they apply to IP, ATM, and optical networks. Unlike previous algorithms, our algorithm generates paths from one source to all destinations. Our algorithm is strongly polynomial, and is asymptotically faster than earlier algorithms. We corroborate our analysis by a preliminary simulation study.

We present a new algorithm, A*Prune, to list (in order of increasing length) the first K multiple-constrained-shortest-path (KMCSP) between a given pair of nodes in a digraph in which each are is associated with multiple quality of-service (QoS) metrics. The algorithm constructs paths starting at the source and going towards the destination. But, at each iteration, the algorithm gets rid of all paths that are guaranteed to violate the constraints, thereby keeping only those partial paths that have the potential to be turned into feasible paths, from which the optimal paths are drawn. The choice of which path to be extended first and which path can be pruned depend upon a projected path cost function, which is obtained by adding the cost already incurred to get to an intermediate node to an admissible cost to go the remaining distance to the destination. The Dijkstra's shortest path algorithm is a good choice to give a good admissible cost. Experimental results show that A*Prune is comparable to the current best known /spl epsiv/-approximate algorithms for most of randomly generated graphs, BA*Prune, which combines the A*Prune with any known polynomial time /spl epsiv/-approximate algorithms to give either optimal or /spl epsiv/-approximate solutions to the KMCSP problem, is also presented.

We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an integer programming approach to solve this problem, it quickly becomes intractable even for modest-sized networks. Instead, our topology design uses random graphs that we show to be nearly optimal in cost, highly connected, and computationally efficient even for large networks. We then formulate a quadratic assignment problem (QAP) to map the abstract topology into the physical network to achieve optimal load balancing for given demand forecasts, which we solve using randomized heuristics. Numerical results on several example networks illustrate the performance and computational efficiency of our method. A graphical design tool has been developed based on our algorithms.

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.

The paper considers the problem of routing a set of permanent virtual circuit requests over a backbone network. Several factors make this routing problem complicated. Routing decisions must be made on-line without any knowledge of future request sets. Furthermore, frequent rerouting to correct inefficiencies that can result from the on-line routing decisions is not possible since rerouting creates a service disruption for the customer. Finally, the forward and reverse bandwidth of a virtual circuit must be routed over the same single path. Using an extensive set of simulations, the paper evaluates several different strategies for on-line permanent virtual circuit routing. The authors find that a strategy based on results in competitive analysis and ideas from combinatorial optimization consistently provides the best performance. The problem of admission control is closely related to the problem of routing. The paper also provides a theoretical lower bound that suggests that non-greedy admission control is a fundamental component of an efficient on-line permanent virtual circuit routing algorithm.

The two-commodity transportation problem with coupling constraints occurs in the formulation of a variety of plant-location models, including those for locating power plants and distributing electrical power The constraint matrix of the problem has a structure resembhng the structure of MCTP(M, N, 2) However, the structure of the coupling constraints is unique to this kind of problem.An effic,ent pr,mal algorithm that explo,ts both the underlying network formulation, as well as the structure of the couphng constraints, is developed The derivation of the algorithm ts based on three basic results" (i) defining for the problem a class of bases which can be represented as spanning trees of the underlying network, (u) establishing the existence of an opt,mal basis that is both primal and dual feasible, which belongs to this class; and 0Ii) specializing the simplex method so that only bases belonging to this class are examined dunng the execution of the algorithm It ts shown that this algorithm is similar to the algorithm for solving a pure transportation problem in one commodity from a computational complexity viewpoint Computational experiments suggest that the algorithm is two orders of magnitude faster than the MPSX on the IBM 3(60,/67.The algorithm involves only operations of addition and subtraction during the lteratlve part and can be implemented in mteger arithmetic, resultmg In a numerically stable code