A general treatment of discrete-time buffers with one randomly interrupted output line

A discrete-time buffer with one single output channel, synchronous transmission of messages and an infinite waiting room is considered, where the output line is subjected to random interruptions in time. The stochastic nature of the interruption process is described by two independents sets of i.i.d. random variables: ‘available periods’, during which the output line is available for the transmission of data from the buffer, and ‘blocked periods’, during which it is not. It is shown how expressions of the probability generating function of the buffer occupancy at random clock times can be derived, under the assumption that both available and blocked periods are arbitrarily distributed with the restriction that the available periods have a rational probability generating function. Many prior treatments of this kind of buffer system are shown to be special cases of the present one. An illustrative example of the method is given.     

Optimal lot-sizing in an imperfect production system with homogeneous reworkable jobs

We consider a lot-sizing problem in a single-stage imperfect production system where the job processing is failure-prone. The processing may generate two types of defects: 1) reworkable defects which must be sent back for rework; 2) nonreworkable defects which are discarded immediately. The production process will switch between new jobs and rework jobs. Both new-job processing time and rework time are random. We discuss the optimal lot-sizing control, under a class of operating policies, to maximize the average profit over an infinite time horizon. We establish the existence of an optimal lot size. Furthermore, we characterize the profit function. Through the discussion, we obtain a very efficient algorithm for determining an optimal lot size.     

ROI-based procedures for progressive transmission of digital images: A comparison

Nowadays, problems arise when handling large-sized images (i.e. medical image such as Computed Tomographies or satellite images) of 10, 50, 100 or more Megabytes, due to the amount of time required for transmitting and displaying, this time being even worse when a narrow bandwidth transmission medium is involved (i.e. dial-up or mobile network), because the receiver must wait until the entire image has arrived. To solve this issue, progressive transmission schemes are used. These schemes allow the image sender to encode the image data in such a way that it is possible for the receiver to perform a reconstruction of the original image from the very beginning of transmission. Despite this reconstruction being, of course, partial, it is possible to improve the reconstruction on the fly, as more and more data of the original image are received. There are many progressive transmission methods available, such as it planes, TSVQ, DPCM, and, more recently, matrix polynomial interpolation, Discrete Cosine Transform (DCT, used in JPEG) and wavelets (used in JPEG 2000). However, none of them is well suited, or perform poorly, when, in addition to progressive transmission, we want to include also ROIs (Region Of Interest) handling. In the progressive transmission of ROIs, we want not only to reconstruct the image as we receive image data, but also to be able to select which part or parts of the emerging image we think are relevant and want to receive first, and which part or parts are of no interest. In this context we present an algorithm for lossy adaptive encoding based on singular value decomposition (SVD). This algorithm turns out to be well suited for progressive transmission and ROI selection of 2D and 3D images, as it is able to avoid redundancy in data transmission and does not require any sort of data recodification, even if we select arbitrary ROIs on the fly. We compare the performing of SVD with DCT and wavelets and show the results.     

Scheduling transmissions in a network

Consider k stations wishing to transmit messages over a network of channels to a common receiver. The capacity of a channel is the maximum amount of data which can be transmitted in a time unit. In addition to the transmission stations, the network contains switching nodes. Given that the jth station has σ_j messages (j = 1,…, k) to transmit, it is desired to find a schedule with minimum completion time T. The amount of data sent over a channel may vary in time. A schedule is stationary if the amount of data sent in a time unit is constant throughout the schedule. It is first shown that for every schedule there exists a stationary schedule with the same completion time. Thus, the search for an optimum schedule is confined to stationary schedules. The problem of finding an optimum stationary schedule is formulated as a multisource single-sink network flow problem, in which the net amount of outgoing flow from each source (transmission station) within one time unit is $\text{σ}{}_{\mathrm{j}}\text{T}$. An O(k|E||V|²) time algorithm to find the minimum T similar to Dinic's flow algorithm is suggested. Using Sleator and Tarjan's techniques an O(k²|E||V|log|V|) algorithm is derived. The running time of both algorithms is independent of the σ_j's and the capacities.     

Spare routing problem with p minimal paths for time-based stochastic flow networks

A time-based stochastic flow network (TBSFN), in which each arc has several possible capacities/states and a lead time, is addressed to discuss the system reliability of spare routing for a computer network. The minimum transmission time to send a given amount of data through a single minimal path is uncertain. Although the transmission time will be shortened even if the data are sent through p (p > 1) disjoint minimal paths simultaneously, it is still variable in a TBSFN. This paper is concerned with evaluating the probability that a specified amount of data can be sent through p minimal paths simultaneously within a time threshold. Such a probability is named the system reliability, which can be treated as a performance index for measuring the transmission ability. We present an efficient methodology to assess the system reliability. Furthermore, a spare routing for boosting the system reliability is established in advance to indicate the main and spare p minimal paths. Subsequently, the system reliability of the spare routing can be computed easily, which shows the contribution of the spare design. From the viewpoint of decision support, we may conduct the sensitive analysis to find out the most important arc which will increase/decrease the system reliability most significantly.     

Transient analysis of an M/G/1 retrial queue subject to disasters and server failures

An M/G/1 retrial queueing system with disasters and unreliable server is investigated in this paper. Primary customers arrive in the system according to a Poisson process, and they receive service immediately if the server is available upon their arrivals. Otherwise, they will enter a retrial orbit and try their luck after a random time interval. We assume the catastrophes occur following a Poisson stream, and if a catastrophe occurs, all customers in the system are deleted immediately and it also causes the server’s breakdown. Besides, the server has an exponential lifetime in addition to the catastrophe process. Whenever the server breaks down, it is sent for repair immediately. It is assumed that the service time and two kinds of repair time of the server are all arbitrarily distributed. By applying the supplementary variables method, we obtain the Laplace transforms of the transient solutions and also the steady-state solutions for both queueing measures and reliability quantities of interest. Finally, numerical inversion of Laplace transforms is carried out for the blocking probability of the system, and the effects of several system parameters on the blocking probability are illustrated by numerical inversion results.     

On worst-case aggregation analysis for network location problems

Network location problems occur when new facilities must be located on a network, and the network distances between new and existing facilities are important. In urban, regional, or geographic contexts, there may be hundreds of thousands (or more) of existing facilities, in which case it is common to aggregate existing facilities, e.g. represent all the existing facility locations in a zip code area by a centroid. This aggregation makes the size of the problem more manageable for data collection and data processing purposes, as well as for purposes of analysis; at the same time, it introduces errors, and results in an approximating location problem being solved. There seems to be relatively little theory for doing aggregation, or evaluating the results of aggregation; most approaches are based on experimentation or computational studies. We propose a theory that has the potential to improve the means available for doing aggregation.This research was supported in part by the National Science Foundation, Grant No. DDM-9023392.     

A signal-recovery system: asymptotic properties,and construction of an infinite-volume process

We consider a linear sequence of ‘nodes’, each of which can be in state 0 (‘off’) or 1 (‘on’). Signals from outside are sent to the rightmost node and travel instantaneously as far as possible to the left along nodes which are ‘on’. These nodes are immediately switched off, and become on again after a recovery time. The recovery times are independent exponentially distributed random variables. We present results for finite systems and use some of these results to construct an infinite-volume process (with signals ‘coming from infinity’), which has some peculiar properties. This construction is related to a question by Aldous and we hope that it sheds some light on, and stimulates further investigation of, that question.     

CONNECTIVITY OF CARTESIAN PRODUCT DIGRAPHS AND FAULT-TOLERANT ROUTINGS OF GENERALIZED HYPERCUBE

ＣＯＮＮＥＣＴＩＶＩＴＹＯＦＣＡＲＴＥＳＩＡＮＰＲＯＤＵＣＴＤＩＧＲＡＰＨＳＡＮＤＦＡＵＬＴ┐ＴＯＬＥＲＡＮＴＲＯＵＴＩＮＧＳＯＦＧＥＮＥＲＡＬＩＺＥＤＨＹＰＥＲＣＵＢＥＸＵＪＵＮＭＩＮＧＡｂｓｔｒａｃｔ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｐｒｏｂｌｅｍ...     

Timed Petri nets and prediction to improve the Chandy–Misra conservative-distributed simulation

The main contribution of this paper shows that distributed simulation of timed Petri nets (TPN) can take advantage of their structure to obtain a significant lookahead which is usually difficult to compute with other models. In this paper, we introduce a conservative-distributed simulation with a reduced number of control messages and without deadlock resolution. This approach is based on a part of optimism computed on the prediction time each logical process can determine for its advancement. Obviously this prediction time must be computed easily according to the structure of the simulated logical process. Timed Petri nets meet these requirements and we use their structure to evaluate the depth of the prediction. In conservative-distributed simulation, it is known that the deeper the prediction, the better the efficiency of the simulation. We present a method we have devised based on channel time prediction. We compare its performance to the Chandy–Misra method and to some related Petri nets approaches (Chiola). Experiments carried out on Sun stations show that there is more parallelism and a reduced number of null messages in the cases of deadlock avoidance. Moreover, considering deadlock detection and resolution technique we observe that in many cases no deadlock occurs with less control messages.     

Characterization of correlated equilibria in stochastic games

A general communication device is a device that at every stage of the game receives a private message from each player, and in return sends a private signal to each player; the signals the device sends depend on past play, past signals it sent, and past messages it received.  An autonomous correlation device is a general communication device where signals depend only on past signals the device sent, but not on past play or past messages it received.  We show that the set of all equilibrium payoffs in extended games that include a general communication device coincides with the set of all equilibrium payoffs in extended games that include an autonomous correlation device. A stronger result is obtained when the punishment level is independent of the history. Final version July 2001     

Join tree propagation utilizing both arc reversal and variable elimination

In this paper, we put forth the first join tree propagation algorithm that selectively applies either arc reversal (AR) or variable elimination (VE) to build the propagated messages. Our approach utilizes a recent method for identifying the propagated join tree messages à priori. When it is determined that a join tree node will construct a single distribution to be sent to a neighbouring node, VE is utilized as it builds a single distribution in the most direct fashion; otherwise, AR is applied as it maintains a factorization of distributions allowing for barren variables to be exploited during propagation later on in the join tree. Experimental results, involving evidence processing in four benchmark Bayesian networks, empirically demonstrate that selectively applying VE and AR is faster than applying one of these methods exclusively on the entire network.     

A heavy-traffic comparison of shared and segregated buffer schemes for queues with the head-of-line processor-sharing discipline

As network speeds increase and the data traffic becomes more diverse, the need arises for service disciplines that offer fair treatment to diverse applications, while efficiently using resources at high speeds. Disciplines that approximate round-robin or processor-sharing service per channel are well suited for data networks because, over a wide range of time scales, they allocate bandwidth fairly among channels without needing to distinguish between different types of applications. This study is among the few to address head-of-line processor sharing. In most previous models of processor-sharing disciplines, the system immediately serves any arriving message at a rate depending only on the number of messages in the system regardless of how these messages are distributed among the channels. This model is commonly called pure processor sharing. In our model, the server completes the work from a given channel at a rate depending on the number of other channels with work in the system. That is, the service rate depends on how messages are distributed among the channels, and only indirectly on the total number of messages in the system. In this paper, we contrast the buffer requirements of shared and non-shared buffer schemes, when both types of schemes provide head-of-the-line processor-sharing service among channels. We formulate the problem as a system of functions representing the cumulative input and cumulative lost (potential) output to parts of the queueing system and model the vector of input functions as a multi-dimensional Brownian motion. The resulting heavy-traffic approximations predict much larger benefits from sharing buffers than those predicted by pure processor sharing.     

A mathematical model for discrete-time buffer systems with correlated output process

This article considers an infinite buffer system with one or more input channels and multiple output channels. Transmission of messages from the buffer is synchronous and the arrival process of messages to the buffer is general. Each of the output channels is subjected to a random interruption process, i.e., the number of available output channels varies in time and is stochastic. The analysis of this system is carried out under the assumption that the output process can be described as a first order Markov process, i.e., the probability distribution of the number of available output channels during some clock time interval depends only on the number of available output channels during the previous clock time interval.A set of equations describing the behavior of this buffer system is derived. For a number of interesting special cases this set is solved and explicit expressions are obtained for the probability generating function of the number of messages in the buffer. Several prior studies are found as special cases of the present one. An illustrative example is treated and the results are compared to the ones obtained for an uncorrelated output process with the same equilibrium distribution. Some considerable deviations from these results are found.     

On the discrete-time Geo/G/1 queue with randomized vacations and at most J vacations

This paper examines a discrete-time Geo/G/1 queue, where the server may take at most J − 1 vacations after the essential vacation. In this system, messages arrive according to Bernoulli process and receive corresponding service immediately if the server is available upon arrival. When the server is busy or on vacation, arriving messages have to wait in the queue. After the messages in the queue are served exhaustively, the server leaves for the essential vacation. At the end of essential vacation, the server activates immediately to serve if there are messages waiting in the queue. Alternatively, the server may take another vacation with probability p or go into idle state with probability (1 − p) until the next message arrives. Such pattern continues until the number of vacations taken reaches J. This queueing system has potential applications in the packet-switched networks. By applying the generating function technique, some important performance measures are derived, which may be useful for network and software system engineers. A cost model, developed to determine the optimum values of p and J at a minimum cost, is also studied.     

Real-time data gathering in sensor networks

Wireless sensor networks represent a new generation of real-time traffic communications and high data rate sensor applications, such as structural health monitoring and control. We study some problems related to data gathering in sensor networks when the sensors collect the sensed data about their environment and this information should be delivered to a collecting central Base Station. We prove that scheduling messages through the network to minimize the maximal delivery time with restrictions on the total idle time allowed is NP-hard. We also refer to a special case of linear network topology for which we present two polynomial time optimization algorithms: One is for minimizing the maximal lateness and maximal delay, while the other is for minimizing the number of tardy messages.     

On the computational complexity of continuous routing

We study the problem of routing and broadcasting messages in a network, in which messages are generated at processors at arbitrary times and each message must reach its destination by a specific deadline. We present distributed and global routing algorithms for some restricted continuous routing problems on arrays of processors. We show that distributed algorithms are unlikely to exist in more general situations by giving an NP-hardness proof for their corresponding feasibility problem; i.e., the problem of determining whether all messages can be routed without violating the constraints of the network. We also present a distributed algorithm for the continuous broadcasting problem.     

OPTIMAL TIMING OF SALVAGE HARVEST IN RESPONSE TO A STOCHASTIC INFESTATION

Abstract Following a catastrophic disturbance, forest managers may choose to perform a salvage harvest to recoup timber losses. When the disturbance process evolves stochastically, a unique option value arises associated with the salvage harvest decision. This option value represents the value of postponing a salvage harvest to gain more information about the disturbance process. This paper uses a real options approach to determine how much of a forested area must be infested to trigger a salvage harvest when the forest provides both timber and nontimber values. Analytical results indicate slower rates of forest recovery will optimally delay a salvage harvest while forested areas with large timber values and where nontimber values are more sensitive to the presence of dead and dying trees should be harvested more immediately. The model is applied to a mountain pine beetle outbreak in Idaho's Sawtooth National Forest using readily available aerial detection survey data.     

The numerical implementation of risk

If one is to estimate environmemtal risk based on data or predict risk based on expert opinion, the parameter environmental risk must be defined precisely so that when data becomes available the numerical values of the estimates and/or prediction can be evaluated. Also, the definition must be precise so that it may be successfully used in regulatory and litigation activities. The presentation is a development of a definition which lends to statistical analysis and the inference in addition lends to ease of engineering interpretation. Various implications and useful extensions in measuring numerically for two or more dimensional mixed effects of several toxicants could be developed in further research.