Nonhomogeneous Poisson process (NHPP) and software reliability growth models (SRGM) are a popular approach to estimate useful metrics such as the number of faults remaining, failure rate, and reliability, which is defined as the probability of failure free operation in a specified environment for a specified period of time. We propose performance-optimized expectation conditional maximization (ECM) algorithms for NHPP SRGM. In contrast to the expectation maximization (EM) algorithm, the ECM algorithm reduces the maximum-likelihood estimation process to multiple simpler conditional maximization (CM)-steps. The advantage of these CM-steps is that they only need to consider one variable at a time, enabling implicit solutions to update rules when a closed form equation is not available for a model parameter. We compare the performance of our ECM algorithms to previous EM and ECM algorithms on many datasets from the research literature. Our results indicate that our ECM algorithms achieve two orders of magnitude speed up over the EM and ECM algorithms of [1] when their experimental methodology is considered and three orders of magnitude when knowledge of the maximum-likelihood estimation is removed, whereas our approach is as much as 60 times faster than the EM algorithms of [2]. We subsequently propose a two-stage algorithm to further accelerate performance.

Since its introduction in 1977, the expectation maximization (EM) algorithm has been one of the most important and widely used estimation method in estimating parameters of distributions in the presence of incomplete information. In this paper, a variant of the EM algorithm, the expectation conditional maximization (ECM) algorithm, is introduced for the first time and it provides a promising alternative in estimating the parameters of nonhomogeneous poisson (NHPP) software reliability growth models (SRGM). This algorithm circumvents the difficult M-step of the EM algorithm by replacing it by a series of conditional maximization steps. The utility of the ECM approach is demonstrated in the estimation of parameters of several well-known models for both time domain and time interval software failure data. Numerical examples with real-data indicate that the ECM algorithm performs well in estimating parameters of NHPP SRGM with complex mean value functions and can produce a faster rate of convergence.

This paper presents a queueing theoretic performance model for a multipriority preemptive M/G/1/./EDF system. Existing models on EDF scheduling consider them to be M/M/1 queues or nonpreemptive M/G/1 queues. The proposed model approximates the mean waiting time for a given class based on the higher and lower priority tasks receiving service prior to the target and the mean residual service time experienced. Additional time caused by preemptions is estimated as part of mean request completion time for a given class and as part of the mean delay experienced due to jobs in execution, on an arrival. The model is evaluated analytically and by simulation. Results confirm its accuracy, with the difference being a factor of two on average in high loads. Comparisons with other algorithms (such as First-Come-First-Served, Round-Robin and Nonpreemptive Priority Ordered) reveal that EDF achieves a better balance among priority classes where high priority requests are favored while preventing lower priority requests from overstarvation. EDF achieves best waiting times for higher priorities in lower to moderate loads (0.2-0.6) and while only being 6.5 times more than static priority algorithms in high loads (0.9). However, for the lowest priority classes, it achieves comparable waiting times to Round-Robin and First-Come-First-Served in low to moderate loads and achieves waiting times only twice the amount of Round-Robin in high system loads.

Service time distribution of certain computing workloads such as static web content is well known. However, for many other computing workloads (e.g., dynamic web content, scientific workloads) the service time distribution is not well understood and it is not correct to assume that these tasks follow a particular distribution. In this paper, we consider task assignment in server farms when both the service time distribution of tasks and (actual) sizes of tasks are not known a priori. We propose an adaptive task assignment policy, called ADAPT-POLICY, which is based on the concept of multiple static-based task assignment policies. ADAPT-POLICY defines a set of policies for a given system taking into account the specific properties of the system. These policies are selected in such a way that they have different performance characteristics under different workload conditions (i.e., service time distributions, etc.). The objective is to use the task assignment policy with the best performance (i.e., the one with the least expected waiting time) to assign tasks. Which task assignment policy performs the best depends on the traffic conditions that vary over time. ADAPT-POLICY determines the best task assignment using the service time distribution of tasks (and various other traffic properties), which is estimated on-line and then it adaptively changes the task assignment policy to suit the most recent traffic conditions. The experimental results show that ADAPT-POLICY can result in significant performance improvements over both static and dynamic task assignment policies.

The mean residual life (MRL) function is one of the most important, widely used reliability measures in practice. For example, it is used to design burn-in programs, plan spare provision, and formulate warranty policies. Parametric techniques, which rely on the assumption that the parametric form of the failure time is known, are usually employed in estimating the MRL function. However, this approach could lead to an inconsistent, inaccurate estimator of the MRL function if the assumption is violated. A nonparametric approach in such a setup provides a promising alternative. In this paper, we employ local polynomial regression with fixed design points accompanied by appropriate binning to construct several new estimators for the MRL function. The asymptotic unbiasedness and consistency of the these estimators are proven. We then bring in two popular bandwidth selection methods to select the bandwidth of the proposed MRL estimators. Finally, we evaluate the performance of the estimators using several simulated and real life examples. Results indicate that the proposed estimators perform well in estimating MRL functions, particularly MRL models with constant, bathtub-shaped, and upside-down bathtub-shaped MRL functions.

Software reliability growth models (SRGMs) are extensively employed in software engineering to assess the reliability of software before their release for operational use. These models are usually parametric functions obtained by statistically fitting parametric curves, using Maximum Likelihood estimation or Least -- squared method, to the plots of the cumulative number of failures observed N(t) against a period of systematic testing time t. Since the 1970s, a very large number of SRGMs have been proposed in the reliability and software engineering literature and these are often very complex, reflecting the involved testing regime that often took place during the software development process. In this paper we extend some of our previous work by adopting a nonparametric approach to SRGM modeling based on local polynomial modeling with kernel smoothing. These models require very few assumptions, thereby facilitating the estimation process and also rendering them more relevant under a wide variety of situations. Finally, we provide numerical examples where these models will be evaluated and compared.

There is extensive evidence indicating that modern computer workloads exhibit highly variability in their processing requirements. Under such workloads, traditional task assignment policies do not perform well. Size-based policies perform significantly better than traditional policies under highly variable workloads. The main limitation of existing size-based policies though is that these have been targeted for batch computing systems. In this paper, we provide performance analysis of 3 novel task assignment policies that are based on multi-level time sharing policy, namely MLMS (Multi-level Multi-server Task Assignment Policy), MLMS-M (Multi-level Multi-server Task Assignment Policy with Task Migration) and MLMS-M* (Multi-tier Multi-level Multi-server Task Assignment policy with Task Migration). These policies attempt to improve the performance first by giving preferential treatment to small tasks and second by reducing the task size variability in host queues. MLMS only reduces the variability of tasks locally, while MLMS-M and MLMS-M* utilise both local and global variance reduction mechanisms. MLMS outperforms existing size-based policies such as TAGS under specific workload conditions. MLMS-M outperforms TAGS under all the scenarios considered. MLMS-M*outperforms TAGS and MLMS-M under specific workload conditions and vice versa.

Existing task assignment policies designed to schedule highly variable computer workloads are not scalable and they generate large amount of wasted processing. This paper proposes a scalable Multi-Tier Task Assignment Policy with Minimum Excess Load (MTTMEL) that can efficiently schedule tasks with highly variable processing requirements. Unlike existing policies, the proposed policy does not assign all incoming tasks to the first host in the system, rather it assigns incoming tasks to a subset of hosts in the system. The proposed policy has multiple tiers that consist of one or more hosts. The proposed policy scales well and it significantly reduces the amount wasted processing (excess load). For example, the TAGS policy produces 460% more wasted processing compared to MTTMEL under certain workloads. MTTMEL outperforms existing policies under a wide range of workload conditions. It outperforms RANDOM by a factor of 23 and TAGS by a factor of 2.6 under certain scenarios.

Size-based task assignment policies have shown significant performance improvements over traditional task assignment policies under highly variable workload conditions. However, these policies are not suitable to assign tasks in time sharing systems. Moreover, these policies are not scalable and they also generate significant amount of wasted processing. This paper proposes a Multi-Level-Multi-Server Task Assignment Policy with Work-Conserving Migration (MLMS-WC-M) that addresses these issues. MLMS-WC-M has three important features. First, it gives preferential treatment to tasks with short processing requirements. Second, it utilises a 2-level variance reduction mechanism. Third, it supports work-conserving migration. We evaluate the performance of MLMS-WC-M against the performance of several well known task assignment policies. The proposed policy outperforms existing policies significantly under a wide range of workload conditions.

Many existing works on multi-level time sharing policies have assumed infinitely small quanta, infinite levels or exponential service time distributions. In this paper, we investigate the performance of a multi-level time sharing policy under heavy-tailed workloads under finite levels when quanta are not infinitely small. Such a policy is consistent with those implemented on modern computer systems and these findings will enable system designers to better understand how various factors (e.g. system load, task size variability and number of levels) affect the overall performance of a given system. First, we obtain the performance metrics for a multi-level time sharing policy with finite number of levels. Second, for the case of 2 and 3 levels (queues), we show that optimal quantum multi-level time sharing policy (MLOQTP) can result in significant performance improvements over other policies under certain traffic and workload conditions. Finally, we investigate the impact of number of levels on the overall performance and propose a simple statistical regression model that can accurately estimate overall performance of a multi-level time sharing system.

Exponential distributions have traditionally been used to model the traffic (e.g. inter-arrival and service distributions) experienced in computer networks. They are attractive as they are amenable to analysis typically utilised in queueing models. However, modern traffic analysis has shown that many computing workloads are in fact 'heavy-tailed' and highly variable, and are better represented by general distributions such as Log-normal and Pareto. The use of General distributions can make an analytical analysis of some queueing metrics (e.g. waiting time, busy period, slowdown) difficult due to the fact that the Markovian properties of certain stochastic processes in queues are no longer in force. For such distributions Prony 's method can be utilised to fit a series of exponentials to the original General distribution, resulting in a Hyper-exponential distribution that represents the characteristics of the original workload, but is more amenable to analysis. Bounded representations of general distributions (such as Bounded Pareto) are frequently used, but by default, Prony's method is not ideally suited to fitting such distributions. We present two ways of addressing this issue: by normalising the Hyper-exponential resulting from Prony's method between the bounds of the workload distribution being approximated, and by re-evaluating Prony's method to fit directly to a Bounded Hyper-exponential.

On the Internet many different paths exist between each source and destination. When single path routing is used these paths can be under utilized, not used fairly or not used at all. One way to overcome this is to allow multipath routing. But when multiple paths are used TCP congestion control can be negatively affected and cause poor goodput performance due to the reordering of packets. We proposeMATCP (Multipath Aware TCP) which makes modifications to TCP that allows it to monitor and select which path it takes through the network for each flow. MATCP is compared to single path routing and is validated using extensive simulation. MATCP is found to greatly improve fairness between flows while providing equal or better utilization of links than single best path networks.

Many interactive applications require continuous user interaction, for example ssh and many Web applications. The TCP connections created by these applications are therefore in a class called interactive. When interactive applications suffer from packet loss, the packet retransmission time severely increases the user perceived delay. This work introduces a dynamic priority RED queue (DPRQ) algorithm that dynamically changes the priority of queues instead of dropping packets when the queue is overloaded. The algorithm reduces the user perceived delay by reducing packet loss in interactive TCP connections. The DPRQ is compared to an existing class-based queue which incorporates RED (RCBQ) as would typically be used for assured forwarding. An analytical model of the DPRQ and RCBQ is presented with both experimental and analytical results. The DPRQ is found by simulation to decrease packet loss by up to eight times and therefore provide a lower user perceived delay even though queuing delay is increased by up to five times.

In a Web service environment, such as Parlay X, contracts are agreed between the involved participants to guarantee a reasonable measure of quality of service (QoS). A common policy adopted is for contracts to involve only one parameter which places a limit on the number of incoming operation calls. This constraint is expressed as the maximum number of operation calls per second that a source is allowed to request. In this paper, we investigate the impact that different constraints placed on the incoming traffic have on performance and guarantees. By expressing shaping conditions mathematically, analysis can be performed for a scenario which considers hard time constraints. Simulations will be used to investigate scenarios involving soft time constraints.

Some known properties regarding the concept of "almost total" information convergence of order\alpha (\alpha >0)for an arbitrary sequence of distributions are defined and reviewed. A theorem is then proved showing that in the case of stochastic point processes almost total information convergence is equivalent to two simple conditions,