This paper presents three mathematical models for network design of cellular networks. The models reflect varying degrees of complexity. Model 1 is a 1-period fixed-link capacity model. Three heuristics are used for solving this problem. All the heuristics first use linear programming relaxations to yield the near-optimal integer solution, then use clever rounding-schemes to find the final solution. The three heuristics are compared with an integer branch-and-bound algorithm to show the efficacy of the heuristics and the speed with which they achieve their solution. The first heuristic is the best. An appendix presents a detailed algorithmic description of the first heuristic. Model 2 allows the capacities of the links to vary. This is a much more difficult mathematical programming problem, yet certain features of the problem reveal valuable characteristics of the linear programming relaxations. Two heuristics are generated; the first heuristic is superior to the second. The heuristics are compared with an optimal branch-and-bound algorithm. Model 3 presents a multi-period demand problem. This is a very complex problem and, while no heuristics are developed and no computational experiments are shown, the structure of the final problem is similar to models 1 and 2; thus linear programming relaxations should be a viable strategy for its solution.

In this paper, we consider the problem of multicommodity flows in a ring network. Using necessary and sufficient conditions to ensure feasible linear and integral flows in the network, and the special structure of the ring topology, we construct efficient algorithms to route all the demands.

A simple model for determination of an optimal limit on taking corrective action in a slowly deteriorating repairable system is presented. The performance of such a system is assumed to be characterized by a single parameter which is continuously being monitored. The underlying deterioration process is assumed to be governed by a Brownian motion process with a positive drift. When the measured value of the parameter reaches the action limit, the repair/replacement procedure is initiated. The optimal action limit is derived so that the expected long run average total cost is minimized. Some simple numerical examples illustrate the model and the optimization.>

We provide a new algorithm for assessing network reliability (and performability, the more general case). As in some well-known approaches, the algorithm identifies most probable states in iterations and provides converging upper and lower bounds after each iteration. The algorithm distinguishes itself by providing superior bounds after the same number of iterations. In some instances, the algorithm can even find the exact reliability in a small number of iterations. The time complexity for each iteration, excluding the time for computing the performance value of a generated state, is only O(n) (where n is the number of components), which is the same as any existing optimal algorithm for enumerating most probable states. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A general simulation/analytic approach for jointly assessing the reliability and performance of a communication/computer network is proposed. The advantages of this approach are the following: (a) it allows consideration of a variety of performance measures, (b) it allows consideration of a general structure of network components failure distribution, (c) it reduces complexity of the model and related calculations, (d) it is relatively simple to implement, and (e) it can derive sensitivity information about network performance with respect to various parameters-the first step for an effective network optimization algorithm. The method is illustrated in a number of examples using network connectivity and weighted network bandwidth as a measure of performance.>

Tandem links with burst errors are analyzed using alternative renewal processes in continuous time. As in the well-known Gilbert model it is assumed that individual links can be either in the good state in which the bit error rate is low, or in the bad (bursty) state in which the bit error rate is momentarily high. For end-to-end digital connection utilizing M links in tandem, three performance measures are derived: average bit error rate, the percentage of available time and the percentage of error-free seconds. These measures are currently being proposed by CCITT for developing performance specifications of ISDN connections.>

A general multimode model for jointly assessing the performance and reliability (performability) of a communication network is considered. The performability is computed by averaging the performance over the most probable network states. An efficient algorithm, superior to all previous algorithms in both speed and flexibility, is proposed to enumerate the most probable network states. The algorithm keeps generating the network states one by one, in order of decreasing probability, until some stopping rule (if specified) is met.>

System performance and reliability are jointly assessed for highly reliable telecommunication or computer networks. The underlying model assumes that at most a small number of components can be "down" at a time, and that the average repair/replacement time of a failed component is small when compared to the average uptimes of network components. At steady state the system is assumed to follow a regenerative stochastic process. This methodology is used to evaluate highly distributed voice/data integrated networks. The performance measure selected for this application is the traffic loss rate.

A decision procedure to determine when computer software should be released is described. This procedure is based upon the cost-benefit for the entire company that has developed the software. This differs from the common practice of only minimizing the repair costs for the data processing division. Decision rules are given to determnine at what time the system should be released based upon the results of testing the software. Necessary and sufficient conditions are identified which determine when the system should be released (immediately, before the deadline, at the deadline, or after the deadline). No assumptions are made about the relationship between any of the model's parameters. The model can be used whether the software was developed by a first or second party. The case where future costs are discounted is also considered.