This paper presents a new policy called the threshold priority policy (TPP) for assigning channels in cellular networks. The performance of TPP is compared with the performance of the well-known cutoff priority policy (CPP) and the nonprioritized complete sharing policy (CSP). Several numerical experiments are done for various values of offered load and portable mobility. The results are compared using three unified performance metrics which take into account the trade-off between new call blocking probability and the forced termination probability.

Abstract Location of facilities on tree networks is an important problem in transportation and telecommunication systems. For tree networks, The best‐known algorithm to find 2‐medians has a time complexity of O(n2). By exploiting the properties relating the 1‐median and the 2‐medians in tree networks, and the properties inherent in tree structure, an improved algorithm is developed for computing the 2‐median. The time complexity of this algorithm is O(n lg n). The details of the algorithm are described along with an illustrative example.

A new approach to the joint selection of primary and secondary routes in a network with unreliable components is presented. The mathematical model captures the changes in the operational characteristics of the network as it adapts to failures. Lagrangian relaxation and subgradient optimization techniques are used to obtain good heuristic solutions to the problem, as well as lower bounds to be used as benchmarks against which the quality of the solution is assessed. Results of numerical experiments are reported, and directions for further enhancements of the model are discussed. >

This paper studies the problem of assigning capacities to the links in a backbone network and determining the primary routes used by messages for each origin-destination communicating pair in the network. The topology of the backbone network is assumed to be known and the end to end traffic requirements are given. The problem is to find the least cost design where the system costs are composed of connection costs which depend on link capacities and queueing costs which are incurred by users due to the limited capacities of links. The goal is to determine the routing and link capacities simultaneously. The problem is formulated and lower bounds are obtained by Lagrangean relaxation embedded in a subgradient optimization procedure. Cut constraints which are redundant in the original formulation are introduced, they improve the lower bounds. A heuristic method based on the Lagrangean solution is described. Extensive computational results are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A general mathematical model for a network design problem with reliability constraints and a revised formulation which seems particularly appropriate for fiber-optics networks is presented. Upper and lower bounding procedures based on continuous relaxations of this modified formulation are described. Preliminary computational results are reported. Limited computational results indicate a good performance of the algorithm, producing a gap between lower and upper bounds that is sufficiently small for a branch-and-bound procedure to be applicable.>

Given the set of intended transactions, the authors model the problem of choosing the most efficient decomposition of the universal set of attributes. Unlike other models which neglect the logical structure developed in database theory, the model developed incorporates it as part of a mathematical program. This provides a comprehensive and an integrated formulation for the combined logical and physical database design problem. The integrated problem and its epsilon -approximation schemes are shown to be NP-complete. An example shows the benefit of such an approach over more conventional ones.>

The combined problem of selecting a primary route for each communicating pair and a capacity value for each link in computer communication networks is considered. The network topology and traffic characteristics are given: a set of candidate routes and of candidate capacities for each link are also available. The goal is to obtain the least costly feasible design where the costs include both capacity and queuing components. Lagrangean relaxation and subgradient optimization techniques were used to obtain verifiable solutions to the problem. The method was tested on several topologies, and in all cases good feasible solutions, as well as tight lower bounds, were obtained. The model can be generalized to deal with different classes of customers, characterized by different priorities, message lengths, and/or delay requirements.>

This paper develops models for designing the architecture of distributed computing systems of the type used to support corporate management and control activities. The data for the design process consist of two major data sets describing the inputs and outputs to the information system and the relationships between them. The model accepts a listing of the relevant data sources in the organization, their physical locations, the number and rate of transactions originating from those locations and the amount of data that have to be transferred before the transactions can be updated, the list of reports that have to be generated by the system, their generation frequency and their physical distribution of those reports to end users. For each report type, the sources of data needed to generate it and the volume of data that have to be transferred for each run.

Design of distributed computer systems is a complex task requiring solutions for several difficult problems. Location of computing resources and databases in a wide-area network is one of these problems which has not yet been solved satisfactorily. Solution of this problem involves determining number and size of computer facilities and their locations, configuring databases and allocating these databases among computer facilities. An integer programming formulation of the problem is presented. Heuristic and optimal solution procedures are developed and computational experience with these procedures is reported. Implications of the model for designing distributed systems are discussed.

This paper addresses the problem of optimizing queries that involve set operations (set queries) in a distributed relational database system. A particular emphasis is put on the optimization of such queries in horizontally partitioned database systems. A mathematical programming model of the set query problem is developed and its NP-completeness is proved. Solution procedures are proposed and computational results presented. One of the main results of the computational experiments is that, for many queries, the solution procedures are not sensitive to errors in estimating the size of results of set operations.

Capacitated spanning tree problems appear frequently as fundamental problems in many communication network design problems. An integer programming formulation and a new set of valid inequalities are presented for the linear characterization of the problem. A combination of a subgradient optimization procedure and an augmented Lagrangean-based procedure is used to generate tight lower bounds. The procedure begins with an explicit representation of a subset of the constraints, and the corresponding Lagrangean problem is solved. The solution is examined in order to identify implicit constraints that are violated. Those are added to the Lagrangean problem, forming an expanded problem, and an efficient dual ascent procedure is then applied. When no further improvement is possible through this procedure, a subgradient optimization procedure is invoked in order to further tighten the lower bound value. An exchange heuristic is applied to the nonfeasible Lagrangean solution, in an attempt to generate good feasible solutions to the problem. The procedure has been tested and has generated bounds that are significantly better than ones obtained through previously published procedures.

The Capacltated Minmaal Directed Tree Problem is fundamental m many network design problems.A new linear integer programming formulauon of the problem which leads to a Dantzlg-Wolfe decomposmon and to a new Lagrangean relaxation procedure for the Capacaated Mmunal Directed Tree Problem as presented This relaxation is used for deriving tight lower bounds on the optunal solution and m heunsucs for obtaining approxtmate solutions The effectiveness of the procedure is demonstrated in computational tests Categories and SubJect Descriptors: C.2.

The problem of selecting a single route for each class of service and each pair of communicating nodes in an SNA network is considered. The nodes, links, sets of candidate routes, and traffic characteristics are given. The goal is to select a set of routes which minimizes the expected network end-to-end queueing and transmission delay. Queueing is modeled as a network ofM/M/1queues which leads to a nonlinear combinatorial optimization problem. Using Lagrangean relaxation and subgradient optimization techniques, we obtain a tight lower bound on the minimal expected delay as well as sets of feasible solutions for the problem. An experimental interactive system has been used to evaluate the procedure; very favorable results have been obtained on a variety of networks.

Abstract In recent years we have evidenced an extensive effort in the development of computer communication networks. One of the important aspects of the network design process is the solution of the topological design questions involved in establishing a communication network. In this article, formulations are presented for a variety of centralized network design problems such as the minimal spanning tree problem, capacitated and degree constrained minimal spanning tree problems, The Telpak problem, and, heterogeneous network design problems. The applicability of these formulations to algorithmic development is demonstrated by developing an efficient algorithm for solving the degree constrained minimal spanning tree problem. Computational results are reported for 630 test problems. A Bender's decomposition procedure is developed and tested for the capacitated minimal spanning tree problem with less favorable results.

The last few years have witnessed the intensive growth of computer communication networks. The need for nationwide and multination computer communication systems brought about the development of packet-switching networks such as the ARPANET. In this paper we examine a model for computer-to-computer communication via a satellite link. In each network, a single node, the satellite communication concentrator (SCC), manages the flow of information between the terminals in the network and the satellite link. The SCC buffers messages from the terminals and retransmits them over the satellite channel. Buffer space claimed by a message is made free only after the SCC receives an acknowledgment from the receiving network; transmission errors cause the buffer to retransmit the message. The statistical behavior of such a system is considered.