Presents a combinatorial analysis to derive a closed-form expression for the number of transmission errors that occur in a block transmitted through a Gilbert channel. This expression simplifies the computations needed to investigate the tradeoffs among the decoding error probability, degree of interleaving, and the error-correction ability of a code. The authors illustrate how a designer may apply the method to determine different combinations of the degree of interleaving and error correction ability to achieve a specified decoding error rate.>

We investigate the impact of the locations of the gateways on the performance of the internet. We consider the problem of determining (i) the routing assignments for the intranet and internet traffic and (ii) the number of gateways and their locations to interconnect existing data networks to minimize a linear combination of the average internet and intranet packet delays subject to a cost constraint on the amount to be spent to establish the gateways. This joint routing and topological design problem is important in the design of internets and should be solved before networks are actually interconnected. This problem is formulated as a nonlinear combinatorial optimization problem. When the gateway locations are fixed, the resulting routing problem is not a convex programming problem. This is unexpected since the routing problem in datagram networks is usually formulated as a convex program. We develop an algorithm based upon Lagrangian relaxation to solve this problem. In the computational experiments, the algorithm was shown to be effective in interconnecting (i) two WANs and (ii) two grid networks. The experiments also showed that the algorithm finds better feasible solutions than an exchange heuristic.>

Reconfiguration capability in asynchronous transfer mode (ATM) networks and its ability to reduce ATM cell losses are studied. An implementation that restricts the transmission of ATM cells of an O-D pair to certain channels in each physical link in a simple path from origin to destination is proposed. The joint topology, discrete capacity, and routing problem in a reconfigurable ATM network is formulated as a nonlinear mixed integer programming problem. It is proven that this problem with integrality constraints relaxed can be simplified to a convex programming problem, providing a method for computing a lower bound on the original problem. An algorithm is developed to solve the nonlinear mixed integer programming problem. In computational experiments, the reconfiguration capability decreased the total cell losses by more than 50%.>

The problem of determining admission controls and a path for each admitted user pair (session) to satisfy user quality of service (QOS) requirements (required throughput, tolerable average cell delay, and tolerable cell loss probability) is considered. The problem is formulated as a nonlinear combinatorial optimization problem. The objective is the maximization of the total reward for the admitted sessions where the reward for each session reflects its priority. The emphasis is on developing a real-time distributed algorithm to determine path assignments and admission controls. In computational experiments, the proposed distributed algorithm is compared with the minimum hop algorithm on test networks with up to 61 nodes and 10000 macro sessions. The proposed algorithm achieved a 36% (on the average) improvement in the total reward over a minimum hop routing algorithm and heuristic admission control scheme in less than 1.5 s of CPU time using distributed computation.>

A flow model for evaluating the performance of a network of asynchronous transfer mode (ATM) switches is presented. The performance measures used include the link (nodal) and end-to-end cell loss probabilities as well as the link (nodal) and end-to-end cell delays. In the model, the routing assignments are assumed to be given. The assumed form of routing assignments may be used to represent either virtual circuit or datagram service. Due to the nonlinear relationship between cell losses and offered flows, the flow model is a system of nonlinear equations. The authors develop a sufficient condition for the existence of a unique solution to the nonlinear system of equations. They present an iterative model and prove that it converges to a unique fixed point provided the sufficient condition is satisfied. The unique fixed point corresponds to the unique solution to the flow model.>

In this paper, the routine problem in virtual circuit networks is considered. In virtual circuit networks, all of the packets in a session are transmitted over exactly one path established between the origin and the destination. We consider the problem of choosing a path for each origin-destination pair so as to minimize the average number of packets in the network. We consider the formulation of this problem as a nonlinear multicommodity flow problem with integer decision variables. The emphasis of this work is to develop a distributed algorithm to solve this optimization problem. The basic approach is Lagrangean Relaxation. We introduce a new multiplier update rule which facilitates the solution of the nonlinear integer programming problem using distributed computation. In computational experiments, our proposed distributed algorithm determines solutions that are within 1% of an optimal solution in less than 2 minutes of CPU time for networks with 26 to 61 nodes. In addition, the proposed multiplier adjustment procedure provides better bounds and is less sensitive to the algorithm parameters than the subgradient method. An analysis of the communication delays of the control messages needed to support a distributed implementation is given. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract In virtual circuit networks, all the packets in a session are transmitted over exactly one path established between the origin and the destination. For each origin–destination pair, it is assumed that there are multiple sessions. We consider the problem of choosing a path for each session so as to minimize the average packet delay in the network. We formulate this problem as a nonlinear multicommodity flow problem with integer decision variables. An iterative scheme that is similar to local search is developed to solve this problem. In each iteration, we apply Lagrangean relaxation and a multiplier adjustment procedure to solve a restricted problem. We show that the Lagrangean dual problem can be solved exactly by solving a convex program. In computational experiments, our algorithm determines solutions that are within 1% of an optimal solution in minutes of CPU time for networks with 26–61 nodes. In addition, we show that our proposed algorithm is better both theoretically and computationally than K(0)‐ordering, single‐path routing, or round‐off Frank–Wolfe heuristics.

An investigation is conducted of the problem of determining routing assignments in slotted Aloha packet radio networks to maximize the end-to-end throughput. It is assumed that the networks have an arbitrary topology and that the relative traffic requirements matrix is arbitrary. The problem is formulated as a nonlinear programming problem. Unfortunately, the problem is not a convex program, which explains why the development of an algorithm to find global optimal solutions has been so elusive. A heuristic algorithm is developed based upon ideas from resource directive decomposition. The heuristic is applied to several standard problems. The numerical results show that the method compares favorably to other methods in the literature.>

The configuration and routing problem (or the joint trunk and traffic routing problem) is first formulated as a mixed integer nonlinear minimization problem. Then certain properties are proved about the problem structure. These properties lead to an efficient algorithm that determines near-optimal configurations and routing assignments. A lower bound is also computed in order to evaluate the quality of the solution. The algorithm was coded and tested on several networks. Present computational experiments clearly show that the performance of a self-planning network is always better than that of the same network without the trunk routing capability. The reduction in average packet delay is as much as 67%.>

The problem of interconnecting two virtual circuit networks is considered. More specifically, the problem is to determine: (1) which nodes (one from each network) should be connected by gateways; and (2) the routing assignments to minimize the routing costs subject to a limitation on the cost of the gateways. This problem is NP-hard. The problem is formulated here as a linear combinatorial optimization problem. A two-phase algorithm is proposed to obtain good solutions. The first phase is a greedy heuristic algorithm. The second phase is an algorithm based on Lagrangian relaxation with the subgradient method. This method has been implemented. In the present computational experiments, the method determines gateway locations to interconnect networks (of various sizes) that are within a few percent of an optimal solution in a few minutes of CPU time.>

In virtual circuit networks, all of the packets in a session are transmitted over exactly one path established between the origin and the destination. The problem of choosing a path for each origin-destination pair so as to minimize the average number of packets in the network is considered here. The usual formulation of this problem as a nonlinear multicommodity flow problem with integer decision variables is considered. A distributed algorithm is developed to solve the optimization problem, using Lagrangean relaxation as the basic approach. A multiplier update technique is developed which facilitates the solution of the nonlinear integer programming problem using distributed computation.>

The load balancing and routing problems are combined as a single problem to capture the interaction between them. An optimization problem for joint load balancing and routing is formulated using a linear combination of the average job response time and average message delay as the performance criterion. Given an initial feasible solution, the Frank-Wolfe method is applied to solve the problem. An algorithm which gives an optimal solution is obtained. The algorithm is then extended to solve the same problem with multiple types of jobs.>