Smart mobile handheld devices (MHDs) are being adopted at a fast speed. Compared to wireless non-handheld devices (NHDs), MHDs tend to be more mobile and can be used more opportunistically. In this paper, we study two important network usage characteristics of MHDs, namely session lengths and IP address usage, in a university campus WiFi network. Specifically, we analyze two five-week long DHCP traces collected from the network, characterize session lengths of MHDs, and develop two hyper-exponential models to capture the distribution of session lengths.We further characterize the IP address usage of MHDs, and develop two analytical models to predict the number of concurrent IP addresses that are being used by MHDs at one point of time. Goodness of fit tests indicate that our analytical models of session lengths provide good fit, and evaluation results demonstrate that the predictions from our models for IP address usage are accurate. Our results provide important insights on managing MHDs as they are being adopted rapidly in WiFi networks.

We consider the problem of propagating an update to nodes in a distributed system using two gossiping protocols. The first is an idealized algorithm with static and dynamic knowledge of the system, and the second is a simple randomized algorithm. We construct a theoretical model that allows us to derive work and completion time statistics under varying transmission delay distributions. Numerical results are obtained for both exponential and nonexponential transmission times using linear-algebraic queueing theory techniques. Additionally, we present the results of simulation experiments showing that under node churn assumptions, the randomized algorithm's performance is qualitatively different than in a fault-free system.

An analytic cost model is presented for M/G/1/N queueing systems. It considers the cost of customer loss versus customer delays, by varying buffer size and processor speed. We find optimal (and near optimal) configurations for a wide variety of service-time distributions. The model can provide insight into when it is better to invest in increased processor speed than to supply more buffer space. It is seen that different distributions may need very different hardware for optimal performance, and that it may actually be better to reject customers.

It has been observed in recent years that in many applications service time demands are highly variable. Without foreknowledge of exact service times of individual jobs, processor sharing is an effective theoretical strategy for handling such demands. In practice, however, processor sharing must be implemented by time-slicing with a round-robin discipline. In this paper, we investigate how round-robin performs with the consideration of job switching overhead. Because of recent results, we assume that the best strategy is for new jobs to preempt the one in service. By analyzing time-slicing with overhead, we derive the effective utilization parameter, and give a good approximation regarding the lower bound of time-slice under a given system load and overhead. The simulation results show that for both exponential and non-exponential distributions, the system blowup points agree with what the effective utilization parameter tells us. Furthermore, with the consideration of overhead, an optimum time-slice value exists for a particular environment.

We study the effects of bursty Internet traffic through simulations. Both short-range dependency (SRD) traffic and long-range dependency (LRD) traffic are simulated over different burst parameters. The results are collected for 10 different 24 hour simulated periods in order to study and measure day-to-day statistical fluctuation. Effects of employing different traffic admission constraints are examined. An alternative for improving network throughput and utilization is proposed. Finally, a case when arrival patterns of traffic are correlated is explored.

Real-time resource scheduling is an important factor for improving the performance of cluster computing. In many distributed and parallel processing systems, particularly real-time systems, it is desirable and more efficient for jobs to finish as close to a target time as possible. This work models the execution time for such a stochastic environment and proposes a dynamic algorithm for optimizing the job completion times by dynamically allocating resources to jobs that are behind schedule and taking resources from jobs that are ahead of schedule. We validate our analytical model with simulations that represent the real computing environment. The results of our simulations show that our alternative is the best estimate to predict the time remaining by using earlier data. Emphasis is placed on where variance enters the system and how well it can be controlled. Also our dynamic algorithm involves modifying the architecture to help reduce the peak number of servers used to execute a job and thus optimize the computation cost.

In systems where job service demands are only known probabilistically, there is very little to distinguish between jobs. Therefore, no universal optimum scheduling strategy or algorithm exists. If the distribution of job times is known, then the residual time (expected time remaining for a job), based on the service it has already received, can be calculated. In a detailed discrete event simulation, we have explored the use of this function for increasing the probability that a job will meet its deadline. We have tested many different distributions with a wide range of sigma2and shape, four of which are reported here. We compare with RR and FCFS, and find that in all distributions studied our algorithm performs best. We also studied the use of two slow servers versus one fast server, and have found that they provide comparable performance, and in a few cases the double server system does better

Summary form only given. In studying or designing parallel and distributed systems one should have available a robust analytical model that includes the major parameters that determine the system performance. Jackson networks have been very successful in modeling parallel and distributed systems. However, they have their limitations. In particular, the product-form solution of Jackson networks assumes steady state and exponential service centers or certain specialized queueing disciplines. We use a transient model studying distributed systems with finite workload (no new arrivals). Using some nonexponential distributions we show to what extent the exponential distribution can be used to approximate other distributions. When the number of tasks to be executed is large enough, the model approaches the product-form solution in those cases where the Jackson networks can be applied. We also study some cases where Jackson networks can't be applied (the nonexponential servers have queueing). The model can be used for reliability analysis of systems that allow failures without repair (fail-stop).

The problem of characterizing the relationship between packet size and network delay has received little attention in the field. Research in that area has been limited to either simulation studies or empirical observations that are detached from analytic traffic modeling. From a queuing viewpoint, it is simple to show that these three variables are inter-related, which necessitates a more careful study. We present a traffic model of a router fed by ON/OFF-type sources with heavy-tailed burst sizes. The traffic model considered is consistent with the evidence that Web traffic is heavy-tailed. The analysis cases that are considered establish a quantitative characterization of the complex relationship among packet payload and header sizes, traffic burstiness, and router queuing delay.

Several research efforts have recently attempted to characterize the effects of heavy-tailed traffic on router performance, while the effects of light-tailed traffic have for long been understood. Since general Web traffic originates from heterogeneous sources, the study of traffic mixing is of importance as it can reveal the degree to which heavy-tailed traffic can be handled by networking infrastructure before router delay becomes unacceptable. We present a model for heterogeneous traffic sources, where each is an ON/OFF process with an exponential OFF time and an arbitrary ON-time distribution. We consider the case of a 2-source process where one has exponential ON time and the other power tailed and present some analysis results showing the significance of traffic mixing on router performance.

A wide variety of traffic models are presently used to study the performance of telecommunications networks. These are shown to be limiting cases of N-burst/G/1 queues. The analytic N-burst model describes traffic as superposition of N packet streams of ON/OFF type. When using power-tail distributions for the duration of the ON periods, self-similar properties, which are critical for understanding tele-traffic, are observed. For very low intraburst packet rates, the N-burst/G/1 model reduces to an M/G/1 queue. For /spl lambda//sub p/ /spl rarr/ /spl infin/ all packets in a burst arrive simultaneously and the model becomes a bulk arrival, or M/sup (X)//G/1, queue. In the same limit, the packet-based model can be compared to a model of the burst level, an M/G/1 queue where the individual customers represent complete bursts rather than individual packets. Thus the mean system time describes the mean delay for the last packet in a burst rather than the average over all packets. The continuous flow model is also shown to be a limiting case of the N-burst model by letting the number of packets in a burst, n/sub p/, and the router's packet service rate, /spl nu/, go to infinity while holding their ratio constant. Numerical results are presented comparing the steady-state results for mean packet delay and for buffer overflow probabilities of the different analytic models. They collectively show the critical importance of the burstiness parameter. The N-burst/M/1 model with self-similar properties shows drastically changing steady-state performance for specific values of the burstiness parameter. The limiting models are incapable of describing the detailed structure of the performance in this transition region.

We present a Markov model for analyzing the performance of parallel/distributed processors that execute a job consisting of N independent tasks in parallel using P processors. The model is a Markov chain with states representing service and failure rates with k (0

Previous work on analyzing three switching schemes for isotropic networks, namely single hop and two cut-through communication schemes (with and without error checking by intermediate nodes), is extended. Each scheme is modeled by a discrete Markov chain. It is shown how the performance of the communication schemes depends on path length (n), load on the network ( lambda ), and the error rate (p). As expected, the cut-through schemes perform much better than the single hop when the communication load is light, but as the load increases, the cut-through schemes deteriorate more rapidly, until they are comparable. In fact, when the load approaches saturation ( lambda is close to 1-p), the cut-through schemes are actually worse than the single-hop schemes. The schemes with checking always outperform those without, but each node must perform more work in checking the correctness of the packets passing through. The time delay becomes infinite when the throughput approaches 1-p. The solutions are expressed as simple formulas and/or algorithms for each scheme.>

The problem of obtaining approximate formulas for mean resequencing waiting times of M/GI/c queueing systems is considered. Two assumptions, commonly used in the study of M/GI/c systems, to derive the formulas are adopted. The formulas are quite accurate and the accuracy increases as c becomes larger. The relative differences between simulation results and the ones calculated by the formulas are below 4%, even for larger server utilization ( rho ). For small rho , the differences are below 1%. Both small rho , the differences are below 1%. Both numerical and simulation results indicate that when the squared coefficient of variation of service time distribution is greater than 1, the mean resequencing waiting time is likely to be very large.>

An architecture assessment environment is proposed for the design and performance evaluation of massively parallel real-time systems. Included are the major inherent phases of design activity and performance analysis that are implicit in the real-time design process. The major contribution is the definition of a comprehensive methodology and corresponding software support tools to allow and assist a designer in his/her development and assessment of parallel real-time systems. Included in the formulation is the ability to specify either homogeneous or heterogeneous hardware architectures, and to provide a basis for determining performance estimates early in the design process which could allow and direct intelligent design decisions. In addition, the methodology presented can be used to support the entire system life-cycle.>

A procedure is developed for testing the accuracy of approximations to probability density functions (PDF) in queueing theory. The approximation can be constructed from the derivatives and moments of a given PDF, if they exist. Four subjects are considered which can be used as criteria to judge the goodness of approximations over the entire range of values of the traffic intensity parameter, rho . A detailed example is presented to discuss the effect which different derivatives/moments matching combinations have on the accuracy of the approximations. The exponential factor is used as an optimizing parameter.>

The authors consider a class of AND-OR tree circuits and study their response to random-pattern inputs as the depth of the tree is allowed to increase indefinitely. Each binary input of a circuit is independently chosen to be one (zero) with probability x (1-x). The logic of the circuit determines the probability of success (one) at the output as a monotonically increasing S-shaped function of x called the probability transfer function. The probability transfer function of an AND-OR tree is shown to have just one interior fixed point (with respect to changes in depth of the tree) in the

An explicit steady-state solution is given for any queuing loop made up of two general servers, whose distribution functions have rational Laplace transforms. The solution is in matrix geometric form over a vector space that is itself a direct or Kronecker product of the internal state spaces of the two servers. The algebraic properties of relevant entities in this space are given in an appendix. The closed-form solution yields simple recursive relations that in turn lead to an efficient algorithm for calculating various performance measures such as queue length and throughput. A computational-complexity analysis shows that the algorithm requires at least an order of magnitude less computational effort than any previously reported algorithm.

A simplified method is presented to calculate moments of failure time and residual lifetime of a fault-tolerant system. The method is based on recent results in queueing theory. Its effectiveness is illustrated by considering a dual repairable system from the literature.

The queueing theory of exponential servers as applied to time sharing computer systems is discussed in detail with respect to response time and throughput. The restriction that only a fixed number of transactions may be processed simultaneously by the computer subsystem is treated, with comparison made among four different approximations.