Optimal control of arrivals to queues with delayed queue length information

We consider discrete-time versions of two classical problems in the optimal control of admission to a queueing system: i) optimal routing of arrivals to two parallel queues and ii) optimal acceptance/rejection of arrivals to a single queue. We extend the formulation of these problems to permit a k step delay in the observation of the queue lengths by the controller. For geometric inter-arrival times and geometric service times the problems are formulated as controlled Markov chains with expected total discounted cost as the minimization objective. For problem i) we show that when k = 1, the optimal policy is to allocate an arrival to the queue with the smaller expected queue length (JSEQ: Join the Shortest Expected Queue). We also show that for this problem, for k greater than or equal to 2, JSEQ is not optimal. For problem ii) we show that when k = 1, the optimal policy is a threshold policy. There are, however, two thresholds m(0) greater than or equal to m(1) > 0, such that mo is used when the previous action was to reject, and mi is used when the previous action was to accept.

Queuing strategies for qos management of traffic between lans interconnected by low-speed wan links

We provide a comparative performance evaluation of packet queuing and link admission strategies for low-speed wide area network Links (e.g. 9600 bps, 64 kbps) that interconnect relatively highspeed, connectionless local area networks (e.g. 10 Mbps). In particular, we are concerned with the problem of providing differential quality of service to interLAN remote terminal and file transfer sessions, and throughput fairness between interLAN file transfer sessions. We use analytical and simulation models to study a variety of strategies. Our work also serves to address the performance comparison of connectionless vs. connection-oriented interconnection of CLNS LANS. When provision of priority at the physical transmission level is not feasible, we show, for low-speed WAN links (e.g. 9600 bps), the superiority of connection-oriented interconnection of connectionless LANs, with segregation of traffic streams with different QoS requirements into different window flow controlled connections. Such an implementation can easily be obtained by transporting IP packets over an X.25 WAN. For 64 kbps WAN links, there is a drop in file transfer throughputs, owing to connection overheads, but the other advantages are retained, The same solution also helps to provide throughput fairness between interLAN file transfer sessions. We also provide a corroboration of some of our modelling results with results from an experimental test-bed.

Mean first passage time approach to the problem of optimal barrier subdivision for Kramer's escape rate

We consider the effect of subdividing the potential barrier along the reaction coordinate on Kramer's escape rate for a model potential, Using the known supersymmetric potential approach, we show the existence of an optimal number of subdivisions that maximizes the rate, We cast the problem as a mean first passage time problem of a biased random walker and obtain equivalent results, We briefly summarize the results of our investigation on the increase in the escape rate by placing a blow-torch in the unstable part of one of the potential wells. (C) 1999 Elsevier Science B.V. All rights reserved.

Optimal control of a stochastic hybrid system with discounted cost

We address the optimal control problem of a very general stochastic hybrid system with both autonomous and impulsive jumps. The planning horizon is infinite and we use the discounted-cost criterion for performance evaluation. Under certain assumptions, we show the existence of an optimal control. We then derive the quasivariational inequalities satisfied by the value function and establish well-posedness. Finally, we prove the usual verification theorem of dynamic programming.

Prediction of reaeration rates in square, stirred tanks

Experiments were conducted on the oxygen transfer coefficient, k(L)a(20), through surface aeration in geometrically similar square tanks, with a rotor of diameter D fitted with six flat blades. An optimal geometric similarity of various linear dimensions, which produced maximum k(L)a(20) for any rotational speed of rotor N by an earlier study, was maintained. A simulation equation uniquely correlating k = k(L)a(20)(nu/g(2))(1/3) (nu and g are kinematic viscosity of water and gravitational constant, respectively), and a parameter governing the theoretical power per unit volume, X = (ND2)-D-3/(g(4/3)nu(1/3)), is developed. Such a simulation equation can be used to predict maximum k for any N in any size of such geometrically similar square tanks. An example illustrating the application of results is presented. Also, it has been established that neither the Reynolds criterion nor the Froude criterion is singularly valid to simulate either k or K = k(L)a(20)/N, simultaneously in all the sizes of tanks, even through they are geometrically similar. Occurrence of "scale effects" due to the Reynolds and the Froude laws of similitude on both k and K are also evaluated.

The influence of temperature gradient and lowering speed on the melt-solid interface shape of GaxIn1-xSb alloy crystals grown by vertical Bridgman technique

Radially homogeneous bulk alloys of GaxIn1-xSb in the range 0.7 < x < 0.8, have been grown by vertical Bridgman technique. The factors affecting the interface shape during the growth were optimised to achieve zero convexity. From a series of experiments, a critical ratio of the temperature gradient (G) of the furnace at the melting point of the melt composition to the ampoule lowering speed (v) was deduced for attaining the planarity of the melt-solid interface. The studies carried out on directional solidification of Ga0.77In0.23Sb mixed crystals employing planar melt-solid interface exhibited superior quality than those with nonplanar interfaces. The solutions to certain problems encountered during the synthesis and growth of the compound were discussed. (C) 1999 Elsevier Science B.V. All rights reserved.

Physics based basis function for vibration analysis of high speed rotating beams

The natural frequencies of continuous systems depend on the governing partial differential equation and can be numerically estimated using the finite element method. The accuracy and convergence of the finite element method depends on the choice of basis functions. A basis function will generally perform better if it is closely linked to the problem physics. The stiffness matrix is the same for either static or dynamic loading, hence the basis function can be chosen such that it satisfies the static part of the governing differential equation. However, in the case of a rotating beam, an exact closed form solution for the static part of the governing differential equation is not known. In this paper, we try to find an approximate solution for the static part of the governing differential equation for an uniform rotating beam. The error resulting from the approximation is minimized to generate relations between the constants assumed in the solution. This new function is used as a basis function which gives rise to shape functions which depend on position of the element in the beam, material, geometric properties and rotational speed of the beam. The results of finite element analysis with the new basis functions are verified with published literature for uniform and tapered rotating beams under different boundary conditions. Numerical results clearly show the advantage of the current approach at high rotation speeds with a reduction of 10 to 33% in the degrees of freedom required for convergence of the first five modes to four decimal places for an uniform rotating cantilever beam.

Jointly Optimal MMSE design for non-redundant FIR precoding and equalization

We provide a filterbank precoding framework (FBP) for frequency selective channels using the minimum mean squared error (MMSE) criterion. The design obviates the need for introducing a guard interval between successive blocks, and hence can achieve the maximum possible bandwidth efficiency. This is especially useful in cases where the channel is of a high order. We treat both the presence and the absence of channel knowledge at the transmitter. In the former case, we obtain the jointly optimal precoder-equalizer pair of the specified order. In the latter case, we use a zero padding precoder, and obtain the MMSE equalizer. No restriction on the dimension or nature of the channel matrix is imposed. Simulation results indicate that the filterbank approach outperforms block based methods like OFDM and eigenmode precoding.

Delay constrained optimal relay placement for planned wireless sensor networks

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.

A Complete Characterization of an Optimal Timer Based Selection Scheme

Timer-based mechanisms are often used in several wireless systems to help a given (sink) node select the best helper node among many available nodes. Specifically, a node transmits a packet when its timer expires, and the timer value is a function of its local suitability metric. In practice, the best node gets selected successfully only if no other node's timer expires within a `vulnerability' window after its timer expiry. In this paper, we provide a complete closed-form characterization of the optimal metric-to-timer mapping that maximizes the probability of success for any probability distribution function of the metric. The optimal scheme is scalable, distributed, and much better than the popular inverse metric timer mapping. We also develop an asymptotic characterization of the optimal scheme that is elegant and insightful, and accurate even for a small number of nodes.

Delay and energy optimal two-hop relaying in delay tolerant networks

We study the trade-off between delivery delay and energy consumption in delay tolerant mobile wireless networks that use two-hop relaying. The source may not have perfect knowledge of the delivery status at every instant. We formulate the problem as a stochastic control problem with partial information, and study structural properties of the optimal policy. We also propose a simple suboptimal policy. We then compare the performance of the suboptimal policy against that of the optimal control with perfect information. These are bounds on the performance of the proposed policy with partial information. Several other related open loop policies are also compared with these bounds.

Damped Belief Propagation Based Near-Optimal Equalization of Severely Delay-Spread UWB MIMO-ISI Channels

In this paper, we present a belief propagation (BP) based equalizer for ultrawideband (UWB) multiple-input multiple-output (MIMO) inter-symbol interference (ISI) channels characterized by severe delay spreads. We employ a Markov random field (MRF) graphical model of the system on which we carry out message passing. The proposed BP equalizer is shown to perform increasingly closer to optimal performance for increasing number of multipath components (MPC) at a much lesser complexity than that of the optimum equalizer. The proposed equalizer performs close to within 0.25 dB of SISO AWGN performance at 10-3 bit error rate on a severely delay-spread MIMO-ISI channel with 20 equal-energy MPCs. We point out that, although MIMO/UWB systems are characterized by fully/densely connected graphical models, the following two proposed features are instrumental in achieving near-optimal performance for large number of MPCs at low complexities: i) use of pairwise compatibility functions in densely connected MRFs, and ii) use of damping of messages.

On optimal timer-based distributed selection for rate-adaptive multi-user diversity systems

We develop an optimal, distributed, and low feedback timer-based selection scheme to enable next generation rate-adaptive wireless systems to exploit multi-user diversity. In our scheme, each user sets a timer depending on its signal to noise ratio (SNR) and transmits a small packet to identify itself when its timer expires. When the SNR-to-timer mapping is monotone non-decreasing, timers of users with better SNRs expire earlier. Thus, the base station (BS) simply selects the first user whose timer expiry it can detect, and transmits data to it at as high a rate as reliably possible. However, timers that expire too close to one another cannot be detected by the BS due to collisions. We characterize in detail the structure of the SNR-to-timer mapping that optimally handles these collisions to maximize the average data rate. We prove that the optimal timer values take only a discrete set of values, and that the rate adaptation policy strongly influences the optimal scheme's structure. The optimal average rate is very close to that of ideal selection in which the BS always selects highest rate user, and is much higher than that of the popular, but ad hoc, timer schemes considered in the literature.

Optimal allocation of carbon credits to emitting agents in a carbon economy

Reduction of carbon emissions is of paramount importance in the context of global warming. Countries and global companies are now engaged in understanding systematic ways of achieving well defined emission targets. In fact, carbon credits have become significant and strategic instruments of finance for countries and global companies. In this paper, we formulate and suggest a solution to the carbon allocation problem, which involves determining a cost minimizing allocation of carbon credits among different emitting agents. We address this challenge in the context of a global company which is faced with the challenge of determining an allocation of carbon credit caps among its divisions in a cost effective way. The problem is formulated as a reverse auction problem where the company plays the role of a buyer or carbon planning authority and the different divisions within the company are the emitting agents that specify cost curves for carbon credit reductions. Two natural variants of the problem: (a) with unlimited budget and (b) with limited budget are considered. Suitable assumptions are made on the cost curves and in each of the two cases we show that the resulting problem formulation is a knapsack problem that can be solved optimally using a greedy heuristic. The solution of the allocation problem provides critical decision support to global companies engaged seriously in green programs.

Minimizing buffer requirements under rate-optimal schedule in regular dataflow networks

Large-grain synchronous dataflow graphs or multi-rate graphs have the distinct feature that the nodes of the dataflow graph fire at different rates. Such multi-rate large-grain dataflow graphs have been widely regarded as a powerful programming model for DSP applications. In this paper we propose a method to minimize buffer storage requirement in constructing rate-optimal compile-time (MBRO) schedules for multi-rate dataflow graphs. We demonstrate that the constraints to minimize buffer storage while executing at the optimal computation rate (i.e. the maximum possible computation rate without storage constraints) can be formulated as a unified linear programming problem in our framework. A novel feature of our method is that in constructing the rate-optimal schedule, it directly minimizes the memory requirement by choosing the schedule time of nodes appropriately. Lastly, a new circular-arc interval graph coloring algorithm has been proposed to further reduce the memory requirement by allowing buffer sharing among the arcs of the multi-rate dataflow graph. We have constructed an experimental testbed which implements our MBRO scheduling algorithm as well as (i) the widely used periodic admissible parallel schedules (also known as block schedules) proposed by Lee and Messerschmitt (IEEE Transactions on Computers, vol. 36, no. 1, 1987, pp. 24-35), (ii) the optimal scheduling buffer allocation (OSBA) algorithm of Ning and Gao (Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, SC, Jan. 10-13, 1993, pp. 29-42), and (iii) the multi-rate software pipelining (MRSP) algorithm (Govindarajan and Gao, in Proceedings of the 1993 International Conference on Application Specific Array Processors, Venice, Italy, Oct. 25-27, 1993, pp. 77-88). Schedules generated for a number of random dataflow graphs and for a set of DSP application programs using the different scheduling methods are compared. The experimental results have demonstrated a significant improvement (10-20%) in buffer requirements for the MBRO schedules compared to the schedules generated by the other three methods, without sacrificing the computation rate. The MBRO method also gives a 20% average improvement in computation rate compared to Lee's Block scheduling method.