This paper examines a model involving two dynamic Erdős–Rényi random graphs that evolve in parallel, with edges in each graph alternating between being present and absent according to specified on- and off-time distributions. A key feature of our setup is regime switching: the graph that is observed at any given moment depends on the state of an underlying background process, which is modeled as an alternating renewal process. This modeling framework captures a common situation in various real-world applications, where the observed network is influenced by a (typically unobservable) background process. Such scenarios arise, for example, in economics, communication networks, and biological systems. In our setup we only have access to aggregate quantities such as the number of active edges or the counts of specific subgraphs (such as stars or complete graphs) in the observed graph; importantly, we do not observe the mode. The objective is to estimate the on- and off-time distributions of the edges in each of the two dynamic Erdős-Rényi random graphs, as well as the distribution of time spent in each of the two modes. By employing parametric models for the on- and off-times and the background process, we develop a method of moments approach to estimate the relevant parameters. Experimental evaluations are conducted to demonstrate the effectiveness of the proposed method in recovering these parameters.

In this paper we analyze the distribution of the Age of Information (AoI) of a tagged data stream sharing a processor with a set of other data streams. We do so in the highly general setting in which the interarrival times pertaining to the tagged stream can have any distribution, and also the service times of both the tagged stream and the background stream are generally distributed. The packet arrival times of the background process are assumed to constitute a Poisson process, which is justified by the fact that it typically is a superposition of many relatively homogeneous streams. The first main contribution is that we derive an expression for the Laplace-Stieltjes transform of the AoI in the resulting GI+M/GI+GI/1 model. Second, we use stochastic ordering techniques to identify tight stochastic bounds on the AoI, leading to an explicit lower and upper bound on the mean AoI. In addition, when approximating the tagged stream’s inter-generation times through a phase-type distribution (which can be done at any precision), we present a computational algorithm for the mean AoI. As illustrated through a sequence of numerical experiments, the analysis enables us to assess the impact of background traffic on the AoI of the tagged stream. It turns out that the upper bound on the mean AoI is remarkably close to its true value, which yields an explicit expression (in terms of the model parameters) for an accurate proxy of the AoI-minimizing generation rate.

In this paper we establish a necessary and sufficient stability condition for a stochastic ring network. Such networks naturally appear in a variety of applications within communication, computer, and road traffic systems. They typically involve multiple customer types and some form of priority structure to decide which customer receives service. These two system features tend to complicate the issue of identifying a stability condition, but we demonstrate how the ring topology can be leveraged to solve the problem.

To improve the routing decisions of individual drivers and the management policies designed by traffic operators, one needs reliable estimates of travel time distributions. Since congestion caused by both recurrent patterns (e.g., rush hours) and non-recurrent events (e.g., traffic incidents) leads to potentially substantial delays in highway travel times, we focus on a framework capable of incorporating both effects. To this end, we propose to work with the Markovian velocity model, based on an environmental background process that tracks both random and (semi-)predictable events affecting the vehicle speeds in a highway network. We show how to operationalize this flexible data-driven model in order to obtain the travel time distribution for a vehicle departing at a known day and time to traverse a given path. Specifically, we detail how to structure the background process and set the speed levels corresponding to the different states of this process. First, for the inclusion of non-recurrent events, we study incident data to describe the random durations of the incident and inter-incident times for different periods of day. Second, for an estimation of the speed patterns in both incident and inter-incident regime, loop detector data for each of these periods is studied. In numerical examples that use road network detector data of the Dutch highway network, we obtain the travel time distribution estimates that arise under different traffic regimes, and illustrate the advantages compared to deterministic travel time prediction methods, or methods that only take recurrent patterns into account.

BACKGROUND: A birth-death process of which the births follow a hypoexponential distribution with L phases and are controlled by an on/off mechanism, is a population process which we call the on/off-seq-L process. It is a suitable model for the dynamics of a population of RNA molecules in a single living cell. Motivated by this biological application, our aim is to develop a statistical method to estimate the model parameters of the on/off-seq-L process, based on observations of the population size at discrete time points, and to apply this method to real RNA data. METHODS: It is shown that the on/off-seq-L process can be seen as a quasi birth-death process, and an Erlangization technique can be used to approximate the corresponding likelihood function. An extensive simulation-based numerical study is carried out to investigate the performance of the resulting estimation method. RESULTS AND CONCLUSION: A statistical method is presented to find maximum likelihood estimates of the model parameters for the on/off-seq-L process. Numerical complications related to the likelihood maximization are identified and analyzed, and solutions are presented. The proposed estimation method is a highly accurate method to find the parameter estimates. Based on real RNA data, the on/off-seq-3 process emerges as the best model to describe RNA transcription.

We consider a general class of closed product-form queueing networks, consisting of single-server queues and infinite-server queues. Even if a network is of product-form type, performance evaluation tends to be difficult due to the potentially large state space and the dependence between the individual queues. To remedy this, we analyze the model in a Halfin–Whitt inspired scaling regime, where we jointly blow up the traffic loads of all queues and the number of customers in the network. This leads to a closed-form limiting stationary distribution, which provides intuition on the impact of the dependence between the queues on the network’s behavior. We assess the practical applicability of our results through a series of numerical experiments, which illustrate the convergence and show how the scaling parameters can be chosen to obtain accurate approximations.

This paper studies the diffusion limit for a network of infinite-server queues operating under Markov modulation, meaning that the system’s parameters depend on an autonomously evolving Markov chain , called the background process. In previous papers on single-node queues with Markov modulation, two variants were distinguished. In the first variant the arrival rate and the server speed are modulated, whereas in the second variant the arrival rate and the service requirement are modulated. The setup of the present paper, however, is more general: we not only extend single-node systems to a network setting, but also allow both the server speed and the service requirement to depend on the background process. For this model we derive a Functional Central Limit Theorem. In particular, we show that, after accelerating the arrival processes and the background process, a centered and normalized version of the network population vector converges to a multidimensional Ornstein–Uhlenbeck process. The proof of this result relies on weak convergence of stochastic integrals as well as continuous-mapping arguments.

A complete understanding of the dynamics of Multipath TCP (MPTCP) over Cellular and WiFi networks is still lacking. This is a highly challenging issue, as a consequence of the complex interdependencies between the losses, packet reordering due to heterogeneous wireless channel features, errors, and link layer retransmissions, as well as their (joint) influence on MPTCP's control mechanism. In this paper, we develop a comprehensive approach that is capable of assessing the performance of long-lived MPTCP flows with joint WiFi and Cellular network access, taking into account the diverse characteristics of both types of networks. Relying on a parallel queueing model, we develop a framework that features the controllable network parameters, such as the retransmission limit and the buffer sizes, so as to capture their impact on the TCP-level performance. We include a variety of numerical and simulation results highlighting various non-trivial findings and insights for adaptive MPTCP design. In particular, we design a novel MPTCP algorithm to exploit the route heterogeneity, and demonstrate that the proposed algorithm is capable of learning the network's characteristics. It also identifies the improved MPTCP window increment parameters for any given set of channel errors, retransmission limits, and buffer sizes.

This paper considers a network of infinite-server queues with the special feature that, triggered by specific events, the network population vector may undergo a linear transformation (a ‘multiplicative transition’). For this model we characterize the joint probability generating function in terms of a system of partial differential equations; this system enables the evaluation of (transient as well as stationary) moments. We show that several relevant systems fit in the framework developed, such as networks of retrial queues, networks in which jobs can be rerouted when links fail, and storage systems. Numerical examples illustrate how our results can be used to support design problems.

Information about intrinsic dimension is crucial to perform dimensionality reduction, compress information, design efficient algorithms, and do statistical adaptation. In this paper we propose an estimator for the intrinsic dimension of a data set. The estimator is based on binary neighbourhood information about the observations in the form of two adjacency matrices, and does not require any explicit distance information. The underlying graph is modelled according to a subset of a specific random connection model, sometimes referred to as the Poisson blob model. Computationally the estimator scales like $n\log n$, and we specify its asymptotic distribution and rate of convergence. A simulation study on both real and simulated data shows that our approach compares favourably with some competing methods from the literature, including approaches that rely on distance information.

We consider a network of data streams from which an anomalous process with known target distribution is to be identified. Because in practice obtaining observations may be expensive, we assume that there is a constraint on the total number of observations based on which the decision has to be made. We derive a sufficient condition on the sampling budget such that the error probability is kept below some desired level. Furthermore, we show how to obtain a sampling allocation that can improve upon equal sampling allocation and achieves the desired accuracy.

We propose an analytical model for a Wi-Fi network acting as a last-mile Internet access with multiple long-lived TCP connections on both the up and down links. Our model considers the joint impact of buffer losses at the access point, contention at the medium access control layer, and packet losses due to the wireless channel being erroneous. We show that the model accurately quantifies the probability of an arbitrary TCP packet being discarded, and the total throughput obtained on the up and down links. Furthermore, quantitative insights can be gained into the throughput that long-lived TCP flows achieve under the joint impact of all aforementioned types of losses. In particular, we find that the wireless channel errors and buffer overflows both lead to throughput unfairness, but that they do so in the opposite direction on the up and down links, respectively. We demonstrate that this insight can be exploited so as to significantly mitigate the throughput unfairness without compromising the total obtainable network throughput.

TCP NewReno is one of the most widely deployed TCP versions in today's Internet. However, a full understanding of the complex inter-dependencies between the losses due to wireless channel errors and those due to buffer overflows, and their (joint) impact on TCP NewReno's congestion control algorithm in wireless and wired-cum-wireless networks is still lacking. In this paper, we develop a comprehensive analytical model for, and study the performance of, TCP NewReno with a cellular last-mile access, taking into account both types of losses. We assume a frame-level Markovian loss model, and build a model that features the system's basic controllable parameters (such as the number of retransmissions and the buffer size), so as to study how they (jointly) affect the TCP-level throughput. We model certain finer aspects, e.g., correlations in wireless and buffer losses and their cross-correlation. We provide a summary of numerical results highlighting several non-trivial findings. In particular, we demonstrate that there exist optimal (i.e., TCP throughput maximizing) pairs of the number of retransmissions and the buffer size.

For effective capacity management in access networks, it is essential to have a good insight in the service quality perceived by the users. As users share the service capacity available, one would want to know how the achieved per-user throughput fluctuates over time. In this paper we present a novel method that assesses the per-user throughput performance on the basis of throughput measurements at equidistant points in time. Our method relies on a queueing-theoretic framework, and allows us to explicitly quantify various statistics concerning the minimum per-user throughput obtained in a sample period, given the measured per-user throughput at the end points of that sample period, as well as the measured utilization during the interval. In an extensive numerical study we show the impact of important system parameters on these statistics. In addition, using illustrative examples, we demonstrate how the developed method can be used in practice for capacity management, with a specific focus on applications in cable access networks, an application for which our approach is particularly suitable.

Anomaly-based intrusion detection systems classify network traffic instances by comparing them with a model of the normal network behavior. To be effective, such systems are expected to precisely detect intrusions (high true positive rate) while limiting the number of false alarms (low false positive rate). However, there exists a natural trade-off between detecting all anomalies (at the expense of raising alarms too often), and missing anomalies (but not issuing any false alarms). The parameters of a detection system play a central role in this trade-off, since they determine how responsive the system is to an intrusion attempt. Despite the importance of properly tuning the system parameters, the literature has put little emphasis on the topic, and the task of adjusting such parameters is usually left to the expertise of the system manager or expert IT personnel. In this paper, we present an autonomic approach for tuning the parameters of anomaly-based intrusion detection systems in case of SSH traffic. We propose a procedure that aims to automatically tune the system parameters and, by doing so, to optimize the system performance. We validate our approach by testing it on a flow-based probabilistic detection system for the detection of SSH attacks.

In First Person Shooter (FPS) games the Round Trip Time (RTT), i.e., the sum of the network delay from client to server and the network delay from server to client, impacts the gamer's performance considerably. Game client software usually has a built-in process to measure this RTT (also referred to as ping time), and therefore gamers do not want to connect to servers with a long ping time. This paper develops a methodology to evaluate the ping time in a scenario where gamers access a common gaming server over an access network, consisting of a link per user that connects this user to a shared aggregation node that in turn is connected to the gaming server via a bottleneck link. First, a model for the traffic the users and the server generate, is proposed based on experimental results of previous papers. It turns out that the characteristics of the (downstream) traffic from server to clients differ substantially from the characteristics of the client-to-server (upstream) traffic. Then, two queuing models are developed (one for the upstream and one for the downstream direction) and combined such that a quantile of the RTT can be calculated given all traffic and network parameters (packet sizes, packet inter-arrival times, link rate, network load, ...). This methodology is subsequently used to assess the (quantile of the) RTT in a typical Digital Subscriber Line (DSL) access scenario. In particular, given the capacity dedicated to gaming traffic on the bottleneck link (between the aggregation node and gaming server), the number of gamers (or equivalently the gaming load the bottleneck link can support) is determined under the restriction that the quantile of the RTT should not exceed a predefined bound. It turns out that this tolerable load is surprisingly low in most circumstances. Finally, it is remarked that this conclusion depends to some extent on the details of the downstream traffic characteristics and that measurements reported in literature do not give conclusive evidence on the exact value of all parameters, such that, although the qualitative conclusion still remains valid, additional experiments could refine the detailed quantitative results.

It is often assumed that Internet traffic exhibits Gaussian characteristics, and this assumption has been validated in various studies of real Internet traffic. Less is known, however, about possible boundaries: at what timescales is traffic Gaussian and how much user aggregation is required for traffic to be Gaussian? The goal of this paper is to investigate these questions by analyzing hundreds of traffic traces, collected at four representative locations. To assess whether traffic is Gaussian, the paper starts with introducing an easy and fast procedure, based on earlier work of Kilpi and Norros. This procedure is used to investigate Gaussianity at timescales ranging from 5 msec to 5 sec. Our study shows that, if traffic is Gaussian at one timescale, it usually preserves this property at other timescales. The paper also investigates Gaussianity as function of the number of users. We conclude that, although it is impossible to give a hard number saying `above N users traffic is Gaussian', it is fair to say that `only a few tens of users' usually makes the aggregated traffic fairly Gaussian.

We consider the problem of traffic anomaly detection in IP networks. Traffic anomalies typically arise when there is focused overload or when a network element fails and it is desired to infer these purely from the measured traffic. We derive new general formulae for the variance of the cumulative traffic over a fixed time interval and show how the derived analytical expression simplifies for the case of voice over IP traffic, the focus of this paper. To detect load anomalies, we show it is sufficient to consider cumulative traffic over relatively long intervals such as 5 min. We also propose simple anomaly detection tests including detection of over/underload. This approach substantially extends the current practice in IP network management where only the first-order statistics and fixed thresholds are used to identify abnormal behavior. We conclude with the application of the scheme to field data from an operational network.

This paper analyzes a communication network with heterogeneous customers. We investigate priority queueing as a way to differentiate between these users. Customers join the network as long as their utility (which is a function of the queueing delay) is larger than the price of the service. We focus on the specific situation in which two types of users play a role: one type is delay-sensitive ('voice'), whereas the other is delay-tolerant ('data'); these preferences are reflected in their utility curves. Two models are considered: in the first the network determines the priority class of the users, whereas the second model leaves this choice to the users. For both models we determine the prices that maximize the provider's profit. Importantly, these situations do not coincide. Our study uses elements from queueing theory, but also from microeconomics and game theory (e.g., the concept of a Nash equilibrium). We conclude the paper by considering a model in which throughput (rather than delay) is the main performance measure. Again the pricing strategy exploits the heterogeneity in required service and willingness-to-pay.

We consider a queue fed by a mixture of light-tailed and heavy-tailed traffic. The two traffic flows are served in accordance with the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing, have emerged as an important mechanism for achieving service differentiation in integrated networks. We derive the asymptotic workload behavior of the light-tailed traffic flow under the assumption that its GPS weight is larger than its traffic intensity. The GPS mechanism ensures that the workload is bounded above by that in an isolated system with the light-tailed flow served in isolation at a constant rate equal to its GPS weight. We show that the workload distribution is in fact asymptotically equivalent to that in the isolated system, multiplied with a certain pre-factor, which accounts for the interaction with the heavy-tailed flow. Specifically, the pre-factor represents the probability that the heavy-tailed flow is backlogged long enough for the light-tailed flow to reach overflow. The results provide crucial qualitative insight in the typical overflow scenario.

We consider a queue fed by a mixture of light-tailed and heavy-tailed traffic. The two traffic classes are served in accordance with the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing (WFQ), have emerged as an important mechanism for achieving service differentiation in integrated networks. We derive the asymptotic workload behavior of the light-tailed class for the situation where its GPS weight is larger than its traffic intensity. The GPS mechanism ensures that the workload is bounded above by that in an isolated system with the light-tailed class served in isolation at a constant rate equal to its GPS weight. We show that the workload distribution is in fact asymptotically equivalent to that in the isolated system, multiplied with a certain pre-factor, which accounts for the interaction with the heavy-tailed class. Specifically, the pre-factor represents the probability that the heavy-tailed class is backlogged long enough for the light-tailed class to reach overflow. The results provide crucial qualitative insight in the typical overflow scenario.

At the access to networks, in contrast to the core, distances and feedback delays, as well as link capacities are small, which has network engineering implications that are investigated in this paper. We consider a single point in the access network which multiplexes several bursty users. The users adapt their sending rates based on feedback from the access multiplexer. Important parameters are the user's peak transmission rate p, which is the access line speed, the user's guaranteed minimum rate r, and the bound /spl epsi/ on the fraction of lost data. Two feedback schemes are proposed. In both schemes the users are allowed to send at rate p if the system is relatively lightly loaded, at rate r during periods of congestion, and at a rate between r and p, in an intermediate region. For both feedback schemes we present an exact analysis, under the assumption that the users' job sizes and think times have exponential distributions. We use our techniques to design the schemes jointly with admission control, i.e., the selection of the number of admissible users, to maximize throughput for given p, r, and /spl epsi/. Next we consider the case in which the number of users is large. Under a specific scaling, we derive explicit large deviations asymptotics for both models. We discuss the extension to general distributions of user data and think times.

The main network solutions for supporting QoS rely on traffic policing (conditioning, shaping). In particular, for IP networks the IETF has developed Intserv (individual flows regulated) and Diffserv (only aggregates regulated). The regulator proposed could be based on the (dual) leaky-bucket mechanism. This explains the interest in network element performance (loss, delay) for leaky-bucket regulated traffic. This paper describes a novel approach to the above problem. Explicitly using the correlation structure of the sources' traffic, we derive approximations for both small and large buffers. Importantly, for small (large) buffers the short-term (long-term) correlations are dominant. The large buffer result decomposes the traffic stream in a stream of constant rate and a periodic impulse stream, allowing direct application of the Brownian bridge approximation. Combining the small and large buffer results by a concave majorization, we propose a simple, fast and accurate technique to statistically multiplex homogeneous regulated sources. To address heterogeneous inputs, we present similarly efficient techniques to evaluate the performance of multiple classes of traffic, each with distinct characteristics and QoS requirements. These techniques, applicable under more general conditions, are based on optimal resource (bandwidth and buffer) partitioning. They can also be directly applied to set GPS (generalized processor sharing) weights and buffer thresholds in a shared resource system.

We consider a fluid queue fed by multiple on-off flows with heavy-tailed (regularly varying) on-periods. Under fairly mild assumptions, we prove that the workload distribution is asymptotically equivalent to that in a reduced system. The reduced system consists of a dominant subset of the flows, with the original service rate subtracted by the mean rate of the other flows. We describe how a dominant set may be determined from a simple knapsack formulation. We exploit a powerful intuitive argument to obtain the exact asymptotics for the reduced system. Combined with the reduced-load equivalence, the results for the reduced system provide an asymptotic characterization of the buffer behavior.

In the planning of modern cellular mobile communication systems, the impact of customer behavior has to be carefully taken into account. Two models dealing with the call retrial phenomenon are presented. The first model considers a base station with a finite customer population and repeated attempts. A Markov chain modeling is proposed, and an efficient recursive solution of the state probabilities is presented. The second model focuses on the use of the guard channel concept to prioritize the handover traffic. Again, the retrial phenomenon plays an important role. The influence of the repeated attempt effect on the quality of service experienced by the mobile customers is discussed by means of numerical results.

In addition to the traditional best effort Internet protocol (IP) service of the Internet, the Internet Engineering Task Force has defined two new services that provide quality of service guarantees on throughput and delay. In this paper, we analyze the delay performance that can be achieved with the service that provides the most firm guarantees-the guaranteed quality of service. Using a voice and a video application as examples, the end-to-end delay is calculated. Three different scenarios are presented: local, regional, and long distance, differing in the distance covered and the number of IP routers traversed. It is shown that even in the long-distance case, the achievable end-to-end delay for the guaranteed service can be kept sufficiently low to support interactive applications with strict delay requirements. It is concluded that for low-rate applications, the efficiency cannot be higher than about 60-75%. For connections traversing a large number of routers, the variable delay as advertised by the routers is much higher than the expected delay. The second new service, called the controlled-load network element service, provides less firm delay guarantees. The end-to-end delay for this service is estimated using similar techniques. The results suggest that this service is suitable for interactive applications in the local and regional scenarios only. For the long distance scenario, the end-to-end delay is expected to be below 300 ms.