Search

Nonlinear optimization under nonlinear constraints is usually difficult. However, standard ad-hoc search techniques may work successfully in some cases. Here, we consider an augmented Lagrangian formulation, and we develop a "projection heuristic" that "guides" the iterative search toward the optimum. We demonstrate the effectiveness of this approach by applying it to the problem of maximizing a circuit-switched communication network's throughput under quality-of-service (QoS) constraints by means of choosing the input offered load. This problem is useful for "sizing" the network capacity. Performance results using several versions of the algorithm demonstrate its robustness, in terms of its accuracy and convergence properties.

The problem of scheduling time-critical messages over a tree network is considered. Messages arrive at any of the nodes and have to reach the root node before their deadlines expire, else they are considered lost. The network is assumed to be operating in discrete time and the messages need one time unit for transmission from one node to the next along its path. The arrival and deadline processes are arbitrary. The policy which transmits messages with smallest extinction (arrival+deadline) time at every link is shown to minimize the number of lost messages over all time intervals and for every sample path.

The authors extend the validity of some results on the optimal control of two-server queueing models with service times of unequal distribution, operating in continuous or discrete time. The distribution of arrivals can be arbitrary subject to some conditions. Both discounted and long-run average costs are considered. Dynamic programming and probabilistic arguments are used to establish the assertion that the optimal policy is of threshold type, i.e. the slower server should be utilized only when the queue length exceeds a certain threshold value. >

In this paper, a class of multiple access schemes is introduced, especially suited for use in packet switched satellite networks. These schemes, called the Interleaved Frame Flush-Out (IFFO) protocols, are characterized by the mixing of free contention and regulated access for the use of the satellite channel. Such hybrid schemes possess desirable features of both extreme strategies and have a built-in capability to adapt to the traffic load profile. A Markov chain model is introduced for their description and analysis, and an optimization problem is formulated for choosing the "best" among the members of this class of protocols. The performance of the protocols is evaluated by computation and simulation, and comparison to other protocols. It is shown to be stable and superior to that of the other protocols over a wide range of throughput values.

The problem of dynamic scheduling of customers (messages) in time-critical environments is discussed. A single station (communication node) is considered, and it is assumed that each customer (message) must begin service (transmission) by an individually varying extinction time or else it is lost. Interest is in minimizing, in the sense of stochastic order, the number of messages lost over any time interval. A variety of results is proved that establishes the optimality of the shortest-time-to-extinction policy under rather general conditions. Similar results are found when messages have constraints on their complete transmission times. A network of M stations in tandem is considered under the hypothesis that a message is never lost and is scheduled irrespective of whether its extinction time (also called due date in this case) has expired or not. Under fairly general assumptions on the arrivals, deadlines, and services, it is shown that the earliest-due-date policy minimizes a form of average tardiness incurred over a finite operating horizon among all non-idling nonpreemptive policies. These problems are formulated in the context of stochastic dominance, and simple interchange arguments are used to establish all results. >

This paper analyzes the slotted ALOHA multiple access scheme for satellite channels with a finite number of users, each having a buffer of infinite capacity. The basic contribution of the paper is the introduction of an improved 2-Markov chain model that permits analysis of this heretofore unsolved problem. Finding an optimal value for the retransmission probability, p that minimizes the total average packet delay and at the same time ensures stability is also discussed.

The authors focus on two areas of communication network design in which methods of control and optimization theory have proven useful. These are the area of multiple access communication (for networks with shared links such as radio networks and local area networks) and the area of network routing (for networks with point-to-point interconnections). They review a few selected problems in each area to show the role of the control concepts involved and then proceed to identify other areas of communication network design in which the same control theoretic and optimization methodology may be applicable and useful. They attempt to bring to the attention of the control systems community the numerous instances of problems arising in the pure communication network design process that can benefit from the attention and the capabilities of this community. >

As jobs arrive they have to be routed to one of two similar exponential servers. It is shown that if the queue lengths at both servers are observed then the Optimal decision is to route jobs to the shorter queue, whereas if the queue lenths are not observed then it is best to alternate between queues, provided the initial distribution of the two queue sizes is the same. The optimality of these routing strategies is independent of the statistics of the job arrivals.