A search engine maintains local copies of different web pages to provide quick search results. This local cache is kept up-to-date by a web crawler that frequently visits these different pages to track changes in them. Ideally, the local copy should be updated as soon as a page changes on the web. However, finite bandwidth availability and server restrictions limit how frequently different pages can be crawled. This brings forth the following optimization problem: maximize the freshness of the local cache subject to the crawling frequencies being within prescribed bounds. While tractable algorithms do exist to solve this problem, these either assume the knowledge of exact page change rates or use inefficient methods such as MLE for estimating the same. We address this issue here. We provide three novel schemes for online estimation of page change rates, all of which have extremely low running times per iteration. The first is based on the law of large numbers and the second on stochastic approximation. The third is an extension of the second and includes a heavy-ball momentum term. All these schemes only need partial information about the page change process, i.e., they only need to know if the page has changed or not since the last crawled instance. Our main theoretical results concern asymptotic convergence and convergence rates of these three schemes. In fact, our work is the first to show convergence of the original stochastic heavy-ball method when neither the gradient nor the noise variance is uniformly bounded. We also provide some numerical experiments (based on real and synthetic data) to demonstrate the superiority of our proposed estimators over existing ones such as MLE. Our algorithms are readily applicable to the synchronization of databases and network inventory management.

We propose a new Lévy Flights Graph Convolutional Networks (LFGCN) method for semi-supervised learning, which casts the Lévy Flights into random walks on graphs and, as a result, allows both to accurately account for the intrinsic graph topology and to substantially improve classification performance, especially for heterogeneous graphs. Furthermore, we propose a new preferential P-DropEdge method based on the Girvan-Newman argument. That is, in contrast to uniform removing of edges as in DropEdge, following the Girvan-Newman algorithm, we detect network periphery structures using information on edge betweenness and then remove edges according to their betweenness centrality. Our experimental results on semi-supervised node classification tasks demonstrate that the LFGCN coupled with P-DropEdge accelerates the training task, increases stability and further improves predictive accuracy of learned graph topology structure. Finally, in our case studies we bring the machinery of LFGCN and other deep networks tools to analysis of power grid networks - the area where the utility of GDL remains untapped.

In this paper we consider a graph clustering problem with a given number of clusters and approximate desired sizes of the clusters. One possible motivation for such task could be the problem of databases or servers allocation within several given large computational clusters, where we want related objects to share the same cluster in order to minimize latency and transaction costs. This task differs from the original community detection problem. To solve this task, we adopt some ideas from Glauber Dynamics and Label Propagation Algorithm. At the same time we consider no additional information about node labels, so the task has the nature of unsupervised learning. We propose an algorithm for the problem, show that it works well for a large set of parameters of Stochastic Block Model (SBM) and theoretically show that its running time complexity for achieving almost exact recovery is of O(n.d-.ω) for the mean-field SBM with d-being the average degree and w tending to infinity arbitrary slow. Other significant advantage of the proposed approach is its local nature, which means it can be efficiently distributed with no scheduling or synchronization.

We consider caching of video streams in a cellular network in which each base station is equipped with a cache. Video streams are partitioned into multiple substreams and the goal is to place substreams in caches such that the residual backhaul load is minimized. We consider two coding mechanisms for the substreams: Layered coding (LC) mechanism and multiple description coding (MDC). We develop a distributed asynchronous algorithm for deciding which files to store in which cache to minimize the residual bandwidth, i.e., the cost for downloading the missing substreams of the user's requested video with a certain video quality from the gateway (i.e., the main server). We show that our algorithm converges rapidly. Finally, we show that MDC partitioning is better than the LC mechanism when the most popular content is stored in caches; however, our algorithm enables to use the LC mechanism as well without any performance loss.

The performance of computer networks relies on how bandwidth is shared among different flows. Fair resource allocation is a challenging problem particularly when the flows evolve over time. To address this issue, bandwidth sharing techniques that quickly react to the traffic fluctuations are of interest, especially in large-scale settings with hundreds of nodes and thousands of flows. In this context, we propose a distributed algorithm based on the alternating direction method of multipliers (ADMM) that tackles the multi-path fair resource allocation problem in a distributed SDN control architecture. Our ADMM-based algorithm continuously generates a sequence of resource allocation solutions converging to the fair allocation while always remaining feasible, a property that standard primal-dual decomposition methods often lack. Thanks to the distribution of all computer intensive operations, we demonstrate that we can handle large instances at scale.

We propose a local message passing algorithm based on Belief Propagation (BP) to detect a small hidden Erdos-Rényi (ER) subgraph embedded in a larger sparse ER random graph in the presence of side-information. We consider side-information in the form of revealed subgraph nodes called cues, some of which may be erroneous. Namely, the revealed nodes may not all belong to the subgraph, and it is not known to the algorithm a priori which cues are correct and which are incorrect. We show that asymptotically as the graph size tends to infinity, the expected fraction of misclassified nodes approaches zero for any positive value of a parameter λ, which represents the effective Signal-to-Noise Ratio of the detection problem. Previous works on subgraph detection using BP without side-information showed that BP fails to recover the subgraph when λ <; 1/e. Our results thus demonstrate the substantial gains in having even a small amount of side-information.

In this paper we address the problem of finding top k eigenvalues and corresponding eigenvectors of symmetric graph matrices in networks in a distributed way. We propose a novel idea called complex power iterations in order to decompose the eigenvalues and eigenvectors at node level, analogous to time-frequency analysis in signal processing. At each node, eigenvalues correspond to the frequencies of spectral peaks and respective eigenvector components are the amplitudes at those points. Based on complex power iterations and motivated from fluid diffusion processes in networks, we devise distributed algorithms with different orders of approximation. We also introduce a Monte Carlo technique with gossiping which substantially reduces the computational overhead. An equivalent parallel random walk algorithm is also presented. We validate the algorithms with simulations on real-world networks. Our formulation of the spectral decomposition can be easily adapted to a simple algorithm based on quantum random walks. With the advent of quantum computing, the proposed quantum algorithm will be extremely useful.

Are Online Social Network (OSN) A users more likely to form friendships with those with similar attributes? Do users at an OSN B score content more favorably than OSN C users? Such questions frequently arise in the context of Social Network Analysis (SNA) but often crawling an OSN network via its Application Programming Interface (API) is the only way to gather data from a third party. To date, these partial API crawls are the majority of public datasets and the synonym of lack of statistical guarantees in incomplete-data comparisons, severely limiting SNA research progress. Using regenerative properties of the random walks, we propose estimation techniques based on short crawls that have proven statistical guarantees. Moreover, our short crawls can be implemented in massively distributed algorithms. We also provide an adaptive crawler that makes our method parameter-free, significantly improving our statistical guarantees. We then derive the Bayesian approximation of the posterior of the estimates, and in addition, obtain an estimator for the expected value of node and edge statistics in an equivalent configuration model or Chung-Lu random graph model of the given network (where nodes are connected randomly) and use it as a basis for testing null hypotheses. The theoretical results are supported with simulations on a variety of real-world networks.

The betweenness centrality is one of the basic concepts in the analysis of the social networks. Initial definition for the betweenness of a node in the graph is based on the fraction of the number of geodesics (shortest paths) between any two nodes that given node lies on, to the total number of th e shortest paths connecting these nodes. This method has polynomial complexity. We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory. The characteristic function is determined by special way for different coalitions (subsets of the graph). Two approaches are used to determine the characteristic function. In the first approach the characteristic function is determined via the number of direct and indirect weighted connecting paths in the coalition. In the second approach the coalition is considered as an electric network and the characteristic function is determined as a total current in this network. We use the Kirchhoff’s law. After that the betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks, in particular, for the popular social network “VKontakte”, as well as the comparing with the PageRank method are presented.

We consider an extension of Erdös-Rényi graph known in literature as Stochastic Block Model (SBM). We analyze the limiting empirical distribution of the eigenvalues of the adjacency matrix of SBM. We derive a fixed point equation for the Stieltjes transform of the limiting eigenvalue empirical distribution function (e.d.f.), concentration results on both the support of the limiting e.s.f. and the extremal eigenvalues outside the support of the limiting e.d.f. Additionally, we derive analogous results for the normalized Laplacian matrix and discuss potential applications of the general results in epidemics and random walks.

Clustering of a graph is the task of grouping its nodes in such a way that the nodes within the same cluster are well connected, but they are less connected to nodes in different clusters. In this paper we propose a clustering metric based on the random walks' properties to evaluate the quality of a graph clustering. We also propose a randomized algorithm that identifies a locally optimal clustering of the graph according to the metric defined. The algorithm is intrinsically distributed and asynchronous. If the graph represents an actual network where nodes have computing capabilities, each node can determine its own cluster relying only on local communications. We show that the size of clusters can be adapted to the available processing capabilities to reduce the algorithm's complexity.

In this paper we address the problem of quick detection of high-degree entities in large online social networks. Practical importance of this problem is attested by a large number of companies that continuously collect and update statistics about popular entities, usually using the degree of an entity as an approximation of its popularity. We suggest a simple, efficient, and easy to implement two-stage randomized algorithm that provides highly accurate solutions to this problem. For instance, our algorithm needs only one thousand API requests in order to find the top-100 most followed users, with more than 90% precision, in the online social network Twitter with approximately a billion of registered users. Our algorithm significantly outperforms existing methods and serves many different purposes such as finding the most popular users or the most popular interest groups in social networks. An important contribution of this work is the analysis of the proposed algorithm using Extreme Value Theory - a branch of probability that studies extreme events and properties of largest order statistics in random samples. Using this theory we derive an accurate prediction for the algorithm's performance and show that the number of API requests for finding the top-k most popular entities is sub linear in the number of entities. Moreover, we formally show that the high variability of the entities, expressed through heavy-tailed distributions, is the reason for the algorithm's efficiency. We quantify this phenomenon in a rigorous mathematical way.

We consider storage devices located in the plane according to a general point process and specialize the results for the homogeneous Poisson process. A large data file is stored at the storage devices, which have limited storage capabilities. Hence, they can only store parts of the data. Clients can contact the storage devices to retrieve the data. We compare the expected cost of obtaining the complete data under uncoded as well as coded data allocation strategies. It is shown that for the general class of cost measures where the cost of retrieving data is increasing with the distance between client and storage devices, coded allocation outperforms uncoded allocation. The improvement offered by coding is quantified for two more specific classes of performance measures. Finally, our results are validated by computing the costs of the allocation strategies for the case that storage devices coincide with currently deployed mobile base stations.

P2P downloads still represent a large portion of today's Internet traffic. More than 100 million users operate BitTorrent and generate more than 30% of the total Internet traffic. Recently, a significant research effort has been done to develop tools for automatic classification of Internet traffic by application. The purpose of the present work is to provide a framework for subclassification of P2P traffic generated by the BitTorrent protocol. The general intuition is that the users with similar interests download similar contents. This intuition can be rigorously formalized with the help of graph based semi-supervised learning approach. We have chosen to work with a PageRank based semi-supervised learning method, which scales well with very large volumes of data. We provide recommendations for the choice of parameters in the PageRank based semi-supervised learning method. In particular, we show that it is advantageous to choose labelled points with large PageRank score.

We develop a generalized optimization framework for graph-based semi-supervised learning. The framework gives as particular cases the Standard Laplacian, Normalized Laplacian and PageRank based methods. We have also provided new probabilistic interpretation based on random walks and characterized the limiting behaviour of the methods. The random walk based interpretation allows us to explain differences between the performances of methods with different smoothing kernels. It appears that the PageRank based method is robust with respect to the choice of the regularization parameter and the labelled data. We illustrate our theoretical results with two realistic datasets, characterizing different challenges: Les Miserables characters social network and Wikipedia hyper-link graph. The graph-based semi-supervised learning classifies the Wikipedia articles with very good precision and perfect recall employing only the information about the hyper-text links.

The remarkable growth of the Internet infrastructure and the increasing heterogeneity of applications and users' behavior make more complex the manageability and monitoring of ISP networks and raises the cost of any new deployment. The main consequence of this trend is an inherent disagreement between existing monitoring solutions and the increasing needs of management applications. In this context, we present the design of an adaptive centralized architecture that provides visibility over the entire network through a network-wide cognitive monitoring system. Practically, given a measurement task and a constraint on the volume of collected information, the proposed architecture drives the sampling rates on the interfaces of network routers to achieve the maximum possible accuracy, while adapting itself to any change in network traffic conditions. We illustrate our work with an accounting application whose purpose is to estimate the volume of aggregate flows across a backbone transit network. The paper provides a global study of the functioning of the proposed system and the impact of the different parameters on its behavior. The performance of our system is validated in typical scenarios over an experimental platform we developed for the purpose of the study.

We consider a block fading interference channels with partial channel state information and we address the issue of joint power and rate allocation in a game theoretic framework. The system is intrinsically affected by outage events. Resource allocation algorithms based on Bayesian games are proposed. The existence, uniqueness, and some stability properties of Nash equilibriums (NE) are analyzed. For some asymptotic setting, closed form expressions of NEs are also provided.

We have recently extended the notion of alpha fairness to include time scale considerations for fair assignment of resources. Two extreme cases are elastic traffic (file transfer) and interactive voice. In this paper we consider time scale separation in the fairness that is related to the mobility of the users. We propose and solve the problem when the utilities are linear in the resources. We apply these results in the context of fair resource allocation in femtocell networks in a dynamic setting. We show how mobility and the constraints on the averaging durations impact the amount of resources each user gets.

In many scenarios network design is not enforced by a central authority, but arises from the interactions of several self-interested agents. This is the case of the Internet, where connectivity is due to Autonomous Systems' choices, but also of overlay networks, where each user client can decide the set of connections to establish. Recent works have used game theory, and in particular the concept of Nash Equilibrium, to characterize stable networks created by a set of selfish agents. The majority of these works assume that users are completely non-cooperative, leading, in most cases, to inefficient equilibria. To improve efficiency, in this paper we propose two novel socially-aware network design games. In the first game we incorporate a socially-aware component in the users' utility functions, while in the second game we use additionally a Stackelberg (leader-follower) approach, where a leader (e.g., the network administrator) architects the desired network buying an appropriate subset of network's links, driving in this way the users to overall efficient Nash equilibria. We provide bounds on the Price of Anarchy and other efficiency measures, and study the performance of the proposed schemes in several network scenarios, including realistic topologies where players build an overlay on top of real Internet Service Provider networks. Numerical results demonstrate that (1) introducing some incentives to make users more sociallyaware is an effective solution to achieve stable and efficient networks in a distributed way, and (2) the proposed Stackelberg approach permits to achieve dramatic performance improvements, designing almost always the socially optimal network.

The problem of jamming plays an important role in ensuring the quality and security of wireless communications, especially at this moment when wireless networks are quickly becoming ubiquitous. Since jamming can be considered as a game in which jammer is playing against the user (transmitter) who would like to transmit signal with good quality and at the same time with a reasonable amount of energy, game theory is an appropriate tool for dealing with jamming. Here we investigate the effect of partially available information and correlation among sub-carriers on the user behavior. Specifically, to do so we deal with the scenario when the user does not know how jamming efforts are distributed among sub-carriers and the user does not know the fading channels' gains with certainty. As an object function for the user we consider SINR. We consider zero-sum games, so all of them can also be viewed as a minimax problem for the user playing against the nature. We study independent fading channel gains scenario as well as dependent fading channel gains scenario, both in discrete and continuous versions. We show that in all the scenarii the jammers equalize the quality of the best sub-carriers for the transmitter on as low level as their power constraints allow. Meanwhile the transmitter distributes his power among these jamming sub-carriers. We find the equilibrium strategies in closed form and specify the range of sub-carriers where the transmitter can expect the jamming attack. Also, we show for independent plot these strategies depend only on the expected value of the transmitters channel gains meanwhile for the dependent plot they depend on the whole spectra of these gains. Thus, for independent plot the behaviour of the jammer is less fine tuned under environment since it works with the expected gains. The user for both scenarios has to take the whole spectra of the jamming gains but, of course, for the independent scenario he is less specific because of the jammer.

We study power control in optimization and game frameworks. In the optimization framework there is a single decision maker who assigns network resources and in the game framework users share the network resources according to Nash equilibrium. The solution of these problems is based on so-called water-filling technique, which in turn uses bisection method for solution of non-linear equations for Lagrange multipliers. Here we provide a closed form solution to the water-filling problem, which allows us to solve it in a finite number of operations. Also, we produce a closed form solution for the Nash equilibrium in symmetric Gaussian interference game with an arbitrary number of users. Even though the game is symmetric, there is an intrinsic hierarchical structure induced by the quantity of the resources available to the users. We use this hierarchical structure to perform a successive reduction of the game. In addition to its mathematical beauty, the explicit solution allows one to study limiting cases when the crosstalk coefficient is either small or large. We provide an alternative simple proof of the convergence of the iterative water filling algorithm. Furthermore, it turns out that the convergence of Iterative water filling algorithm slows down when the crosstalk coefficient is large. Using the closed form solution, we can avoid this problem. Finally, we compare the non-cooperative approach with the cooperative approach and show that the non-cooperative approach results in a more fair resource distribution.

Clustering hypertext document collection is an important task in Information Retrieval. Most clustering methods are based on document content and do not take into account the hyper-text links. Here we propose a novel PageRank based clustering (PRC) algorithm which uses the hypertext structure. The PRC algorithm produces graph partitioning with high modularity and coverage. The comparison of the PRC algorithm with two content based clustering algorithms shows that there is a good match between PRC clustering and content based clustering.

We consider the situation where N nodes share a common access point. With each node i there is an associated buffer and channel state that change in time. Node i dynamically chooses both the power and the admission control to be adopted so as to maximize the expected capacity, which depends on the actions and states of all the players, given its power and delay constraints. The information structure that we consider is such that each player knows the state of its own buffer and channel and its own actions. It does not know the states of, and the actions taken by other players. Using Markov Decision Processes we analyze the single player optimal policies under different model parameters. In the context of stochastic games we study the equilibria of the N player scenario.

We consider an uplink power control problem where each mobile wishes to maximize its throughput (which depends on the transmission powers of all mobiles) but has a constraint on the average power consumption. A finite number of power levels are available to each mobile. The decision of a mobile to select a particular power level may depend on its channel state. We consider two frameworks concerning the state information of the channels of other mobiles: (i) the case of full state information and (ii) the case of local state information. In each of the two frameworks, we consider both cooperative as well as non-cooperative power control. We manage to characterize the structure of equilibria policies and, more generally, of best-response policies in the non-cooperative case. We present an algorithm to compute equilibria policies in the case of two non-cooperative players. Finally, we study the case where a malicious mobile, which also has average power constraints, tries to jam the communication of the other mobile. Our results are illustrated and validated through various numerical examples.

We study an adaptive window protocol (AWP) with a general increase and decrease profile in the presence of window dependent random losses. We derive a steady-state Kolmogorov equation and obtain its solution in analytic form. We obtain some stochastic ordering relations for a protocol with different bounds on window. A closed form necessary and sufficient stability condition using the stochastic ordering for the window process is established. Finally, we apply the general results to particular TCP versions such as NEW Reno TCP, scalable TCP and Highspeed TCP. We observe that Highspeed TCP can be used to approximate almost any kind of window behavior by varying only one design parameter.

The multiplicative increase multiplicative decrease (MIMD) congestion control algorithm in the form of scalable TCP has been proposed for high speed networks. We study fairness among sessions sharing a common bottleneck link, where one or more sessions use the MIMD algorithm. Losses, or congestion signals, occur when the capacity is reached but could also be initiated before that. Both synchronous as well as asynchronous losses are considered. In the asynchronous case, only one session suffers a loss at a loss instant. Two models are then considered to determine which source looses a packet: a rate dependent model in which the packet loss probability of a session is proportional to its rate at the congestion instant, and the independent loss rate model. We first study how two MIMD sessions share the capacity in the presence of general combinations of synchronous and asynchronous losses. We show that, in the presence of rate dependent losses, the capacity is fairly shared whereas rate independent losses provide high unfairness. We then study inter protocol fairness: how the capacity is shared in the presence of synchronous losses among sessions some of which use additive increase multiplicative decrease (AIMD) protocols whereas the others use MIMD protocols.

As a natural multi-class generalization of the well-known (egalitarian) processor sharing (PS) service discipline, discriminatory processor sharing (DPS) is of great interest in many application areas, including telecommunications. Under DPS, the mean response time conditional on the service requirement is only known in closed form when all classes have exponential service requirement distributions. For generally distributed service requirements, Fayolle et al. (1980) showed that the expected conditional response times satisfy a system of integro-differential equations. In this paper, we exploit that result to prove that, provided the system is stable, for each class the expected unconditional response time is finite and that the expected conditional response time has an asymptote. The asymptotic bias of each class is found in closed form, involving the mean service requirements of all classes and the second moments of all classes but the one under consideration. In the course of the development we prove two other results that are of independent interest: we establish a conservation law for the time average unfinished work of all classes and, using a stochastic coupling argument, we show that the response times of different classes are stochastically ordered according to the DPS weights. Finally, we study DPS as a tool to achieve size based scheduling and we provide guidelines as to how the weights of DPS must be chosen such that DPS outperforms PS.

The nonlinear stochastic control problem related with flow control is considered. The state of the link is described by controlled hidden Markov process while the loss flow is described by the counting process with the intensity depending on the current transmission rate and unobserved link state. The control is the transmission rate and have to be chosen as non-anticipating process depending on the observation of the loss process. The aim of the control is to achieve the maximum of some utility function taking into account the losses of transmitted information. Originally the problem belongs to a class of stochastic control with incomplete information, however, the optimal filtering equations giving the estimation of the current link state based on the observation of the loss process give the opportunity to reduce the problem to the standard stochastic control problem with full observations. Then, a necessary optimality condition is derived in the form of stochastic maximum principle which allows us to obtain explicit analytic expressions for the optimal control in some particular cases. The optimal and suboptimal controls are investigated and compared with the flow control schemes which is used in TCP/IP networks. In particular, the optimal control demonstrates a much smoother behavior than the currently used TCP/IP congestion control.

In this paper, we present a model for TCP/IP congestion control mechanism. The rate at which data is transmitted increases linearly in time until a packet loss is detected. At this point, the transmission rate is divided by a constant factor. Losses are generated by some exogenous random process which is assumed to be stationary ergodic. This allows us to account for any correlation and any distribution of inter-loss times. We obtain an explicit expression for the throughput of a TCP connection and bounds on the throughput when there is a limit on the window size. In addition, we study the effect of the Timeout mechanism on the throughput. A set of experiments is conducted over the real Internet and a comparison is provided with other models that make simple assumptions on the inter-loss time process. The comparison shows that our model approximates well the throughput of TCP for many distributions of inter-loss times.

Internet measurements show that a small number of large TCP flows are responsible for the largest amount of data transferred, whereas most of the TCP sessions are made up of few packets. Several authors have invoked this property to suggest the use of scheduling algorithms, which favor short jobs, such as LAS (least attained service), to differentiate between short and long TCP flows. We propose a packet level stateless, threshold based scheduling mechanism for TCP flows, RuN2C. We describe an implementation of this mechanism, which has the advantage of being TCP compatible and progressively deployable. We compare the behavior of RuN2C with LAS based mechanisms through analytical models and simulations. As an analytical model, we use a two level priority processor sharing PS + PS. In the PS + PS system, a connection is classified as high or low priority depending on the amount of service it has obtained. We show that PS + PS reduces the mean response time in comparison with standard processor sharing when the hazard rate of the file size distribution is decreasing. By simulations we study the impact of RuN2C on extreme values of response times and the mean number of connections in the system. Both simulations and analytical results show that RuN2C has a very beneficial effect on the delay of short flows, while treating large flows as the current TCP implementation does. In contrast, we find that LAS based mechanisms can lead to pathological behavior in extreme cases.

No abstract available.

We present an analytical model for the calculation of network load and drop probabilities in a TCP/IP network with general topology. First we formulate our model as a nonlinear complementarity problem. Then we transform the model into two equivalent formulations: fixed point formulation and nonlinear programming formulation. These equivalent formulations provide efficient computational procedures for the solution of our model. Furthermore, with the help of the fixed point formulation we are able to prove the existence of a solution. Our model has the main advantage of not requiring the pre-definition of bottleneck links. The model also takes into account the receiver congestion window limitation. Our approach can be used for TCP/IP networks with drop tail buggers as well as for TCP/IP networks with active queue management buggers. We solve the problem for some network examples and we show how the distribution of load varies with network parameters. The distribution of load is sometimes counter-intuitive which cannot be detected by other models making prior assumptions on the locations of bottlenecks.

We study in this paper a TCP-like linear-increase multiplicative-decrease flow control mechanism. We consider congestion signals that arrive in batches according to a Poisson process. We focus on the case when the transmission rate cannot exceed a certain maximum value. We write the Kolmogorov equations and we use Laplace transforms to calculate the distribution of the transmission rate in the steady state as well as its moments. Our model is particularly useful to study the behavior of TCP, the congestion control mechanism in the Internet. By a simple transformation, the problem can be reformulated in terms of an equivalent M/G/1 queue, where the transmission rate in the original model corresponds to the workload in the 'dual' queue. The service times in the queueing model are not i.i.d., and they depend on the workload in the system.

We present a technique for identifying repetitive information transfers and use it to analyze the redundancy of network traffic. Our insight is that dynamic content, streaming media and other traffic that is not caught by today's Web caches is nonetheless likely to derive from similar information. We have therefore adapted similarity detection techniques to the problem of designing a system to eliminate redundant transfers. We identify repeated byte ranges between packets to avoid retransmitting the redundant data.

No abstract available.