We analyze the performance of regular decomposition, a method for compression of large and dense graphs. This method is inspired by Szemerédi’s regularity lemma (SRL), a generic structural result of large and dense graphs. In our method, stochastic block model (SBM) is used as a model in maximum likelihood fitting to find a regular structure similar to the one predicted by SRL. Another ingredient of our method is Rissanen’s minimum description length principle (MDL). We consider scaling of algorithms to extremely large size of graphs by sampling a small subgraph. We continue our previous work on the subject by proving some experimentally found claims. Our theoretical setting does not assume that the graph is generated from a SBM. The task is to find a SBM that is optimal for modeling the given graph in the sense of MDL. This assumption matches with real-life situations when no random generative model is appropriate. Our aim is to show that regular decomposition is a viable and robust method for large graphs emerging, say, in Big Data area.

A method for compression of large graphs and matrices to a block structure is further developed. Szemerédi's regularity lemma is used as a generic motivation of the significance of stochastic block models. Another ingredient of the method is Rissanen's minimum description length principle (MDL). We continue our previous work on the subject, considering cases of missing data and scaling of algorithms to extremely large size of graphs. In this way it would be possible to find out a large scale structure of a huge graphs of certain type using only a tiny part of graph information and obtaining a compact representation of such graphs useful in computations and visualization.

Peer-to-peer protocols that rely on fully random peer and chunk selection have recently been shown to suffer from instability. The culprit is referred to as the missing piece syndrome, whereby a single chunk is driven to near extinction, leading to an accumulation of peers having almost complete files, but waiting for the missing chunk. We investigate three distributed random peer sampling protocols that tackle this issue, and present proofs of their stability using Lyapunov function techniques. The first two protocols are based on the sampling of multiple peers and a rare chunk selection rule. The last protocol incorporates an incentive mechanism to prevent free riding. It is shown that this incentive mechanism interacts well with the rare chunk selection protocol and stability is maintained. Besides being stable for all arrival rates of peers, all three protocols are scalable in that the mean upload rate of each peer is bounded uniformly independent of the arrival rate.

We consider three approaches to the modeling of systems with repairable components by a multivariate stochastic on-off process. First, we discuss the Palm calculus framework for stationary processes and its power in the derivation of general formulae for joint downtime statistics in the case of statistically independent components. Second, a class of Generalized Semi-Markov (GSMP) models is proposed for incorporating both arbitrary component downtime distributions and statistical dependence of component failures. The case of two components is studied in detail. Third, we define the property referred to as weakened-by-failures for a system of repairable components, and prove that it implies association under fairly general conditions. We also give sufficient conditions for our GSMP models to possess this property.

We propose a new model for peer-to-peer networking which takes the network bottlenecks into account beyond the access. This model can cope with key features of P2P networking like degree or locality constraints together with the fact that distant peers often have a smaller rate than nearby peers. Using a network model based on rate functions, we give a closed form expression of peers download performance in the system's fluid limit, as well as approximations for the other cases. Our results show the existence of realistic settings for which the average download time is a decreasing function of the load, a phenomenon that we call super-scalability.

A reliability model for IP networks is considered, where the routers and links are modeled by independent stationary on/off processes. Component downtimes may obey any probability distribution. The model combines component reliability to a topological analysis, taking into account the routing rules of the network. This allows the derivation of on-off processes describing with high accuracy the IP-availability delivered to customers of each access router. The approach also provides estimates for risk in terms of lost traffic and allows analytic comparison of basic strategies for reliability improvement. The methodology is illustrated by studying the Finnish research backbone network.

We analyse a random graph where the node degrees are (almost) independent and have a distribution with finite mean but infinite variance - a region observed in empirical studies of the Internet. We show that the existence of very large nodes has a great influence on the connectivity. If N denotes the number of nodes it seems that the distance between two randomly chosen nodes of the giant component grows as slowly as log log(N). The essential observation is that very large nodes form a spontaneously arising "core network", which plays a crucial role in the connectivity, although its proportional size goes to zero as N /spl rarr/ /spl infin/. Several results related to the core are proven rigorously, and a sketch of a full proof is given. Some simulations providing illustration of the findings are presented. Consequences of the results are discussed.

We search for methods or tools to detect whether the 1-dimensional marginal distribution of traffic increments of aggregate TCP-traffic satisfy the hypothesis of approximate normality. Gaussian approximation requires a high level of aggregation in both "vertical" (source aggregation) and "horizontal" (time scale) directions. We discuss these different concepts of aggregation first separately, with an example from real data traffic, and show how to rule out cases where the level of aggregation will not be sufficient. Gaussian approximation is then quantified with the square of the linear correlation coefficient in normal-quantile plots. We propose an elementary method based on this correlation test, by looking at the behavior of the test statistic for different sample sizes, and show positive and negative examples from the example data. We use this method to look for the first time scale, where the Gaussian approximation is plausible with the example data, and then we look how much more vertical aggregation would be needed for smaller time scales in order to obtain a reasonable approximation by normal distribution.

This article considers Gaussian flows which are fed into a GPS (Generalized Processor Sharing) scheduler. The system is analyzed using a most probable path approach. This method gives quite good approximations for performance measures, like queue length distributions in the full range of queue levels. The approximations are based on the distinction whether it is more probable that an aggregated queue consists of traffic from one class only or whether it is a combination of several classes. The approximate queue length distribution for a specific flow is then calculated either using the Empty Buffer Approximation or the authors' Rough Full Link Approximation, respectively.

An abstract model for aggregated connectionless traffic, based on the fractional Brownian motion, is presented. Insight into the parameters is obtained by relating the model to an equivalent burst model. Results on a corresponding storage process are presented. The buffer occupancy distribution is approximated by a Weibull distribution. The model is compared with publicly available samples of real Ethernet traffic. The degree of the short-term predictability of the traffic model is studied through an exact formula for the conditional variance of a future value given the past. The applicability and interpretation of the self-similar model are discussed extensively, and the notion of ideal free traffic is introduced.>

When variable-bit-rate sources are multiplexed in an asynchronous transfer mode (ATM) network, there arise queues with a particular form of correlated arrival process. Such queues are analyzed by exploiting a result expressing the distribution of work in system of the G/G/1 queue originally derived by V.E. Benes (1963). A simple alternative demonstration of this result is analyzed and extended to the case of fluid input systems. The result is applied first to a queue where the arrival process is a superposition of periodic sources (the Sigma D/sub i//D/1 queue), and then to a variable-input-rate constant-output-rate fluid system. The latter is shown to model the so-called burst component of the considered superposition queuing process. The difference between this and the real queue, the cell component, can be evaluated by means of the results obtained for the Sigma D/sub i//D/1 queue. The relative importance of these two components is explored with reference to the particular case of a superposition of on/off sources.>