How can we design a product or movie that will attract, for example, the interest of Pennsylvania adolescents or liberal newspaper critics? What should be the genre of that movie and who should be in the cast? In this work, we seek to identify how we can design new movies with features tailored to a specific user population. We formulate the movie design as an optimization problem over the inference of user-feature scores and selection of the features that maximize the number of attracted users. Our approach, PNP, is based on a heterogeneous, tripartite graph of users, movies, and features (e.g. actors, directors, genres), where users rate movies and features contribute to movies. We learn the preferences by leveraging user similarities defined through different types of relations, and show that our method outperforms state-of-the-art approaches, including matrix factorization and other heterogeneous graph-based analysis. We evaluate PNP on publicly available real-world data and show that it is highly scalable and effectively provides movie designs oriented towards different groups of users, including men, women, and adolescents.

In many monitoring applications, recent data is more important than distant data. How does this affect privacy of data analysis? We study a general class of data analyses --- predicate sums --- in this context.

The opportunities to understand human-mobility have increased significantly of late with the rapid adoption of wireless devices that report locations frequently. In this work1, we utilize one such rich data-set comprising of nationwide call data records from several million users to analyze and understand their location patterns. We define a location pattern as the set of locations visited by a user, which roughly speaking, can be considered to be the footprint of the user. Such an analysis is useful since it allows insight into aspects such as the range covered by a user, general direction and major routes of travel, characterization of geographic areas etc.,. These in turn are useful inputs for network planning, traffic planning and mobility models. We propose a systematic methodology that utilizes geometric structures like the Minimum Area Rectangle, line segmentation and clustering techniques to extract meaningful information for location patterns and apply it to our large data-set. Based on this we report on aspects such as the size and orientation of footprints, length of major routes as well as characterize and compare locales based on movement patterns. Finally, we identify some key features of location patterns that can be modeled very well with a single statistical distribution, the Double Pareto LogNormal (DPLN) distribution regardless of locale.

The defining characteristic of wireless and mobile networking is user mobility, and related to it is the ability for the network to capture information on where users are located and how users change location over time. Information about location is becoming critical, and therefore valuable, for an increasingly larger number of location-based or location-aware services. One key open question, however, is how valuable exactly this information is. Our goal in this paper is to develop an analytic framework, namely models and the techniques to solve them, to help quantify the economics of location information. Our aim is to derive models which can be used as decision making tools for entities interested in or involved in the location data economics chain, such as mobile operators or providers of location aware services (mobile advertising, etc). We consider in particular the fundamental problem of quantifying the value of different granularities of location information, for example how much more valuable is it to know the GPS location of a mobile user compared to only knowing the access point, or the cell tower, that the user is associated with. We illustrate our approach by considering what is arguably the quintessential location-based service, namely proximity-based advertising. We make three main contributions. First, we develop several novel models, based on stochastic geometry, which capture the location-based economic activity of mobile users with diverse sets of preferences or interests. Second, we derive closed-form analytic solutions for the economic value generated by those users. Third, we augment the models to consider uncertainty about the users' location, and derive expressions for the economic value generated with different granularities of location information. To our knowledge, this paper is the first one to present and analyze this class of economic models.

We examine a very large-scale data set of more than 30 billion call records made by 25 million cell phone users across all 50 states of the US and attempt to determine to what extent anonymized location data can reveal private user information. Our approach is to infer, from the call records, the "top N" locations for each user and correlate this information with publicly-available side information such as census data. For example, the measured "top 2" locations likely correspond to home and work locations, the "top 3" to home, work, and shopping/school/commute path locations. We consider the cases where those "top N" locations are measured with different levels of granularity, ranging from a cell sector to whole cell, zip code, city, county and state. We then compute the anonymity set, namely the number of users uniquely identified by a given set of "top N" locations at different granularity levels. We find that the "top 1" location does not typically yield small anonymity sets. However, the top 2 and top 3 locations do, certainly at the sector or cell-level granularity. We consider a variety of different factors that might impact the size of the anonymity set, for example the distance between the "top N" locations or the geographic environment (rural vs urban). We also examine to what extent specific side information, in particular the size of the user's social network, decrease the anonymity set and therefore increase risks to privacy. Our study shows that sharing anonymized location data will likely lead to privacy risks and that, at a minimum, the data needs to be coarse in either the time domain (meaning the data is collected over short periods of time, in which case inferring the top N locations reliably is difficult) or the space domain (meaning the data granularity is strictly higher than the cell level). In both cases, the utility of the anonymized location data will be decreased, potentially by a significant amount.

In this paper, we present a general technique based on Bayesian inference to locate mobiles in cellular networks. We study the problem of localizing users in a cellular network for calls with information regarding only one base station and hence triangulation or trilateration cannot be performed. In our call data records, this happens more than 50% of time. We show how to localize mobiles based on our knowledge of the network layout and how to incorporate additional information such as round-trip-time and signal to noise and interference ratio (SINR) measurements. We study important parameters used in this Bayesian method through mining call data records and matching GPS records and obtain their distribution or typical values. We validate our localization technique in a commercial network with a few thousand emergency calls. The results show that the Bayesian method can reduce the localization error by 20% compared to a blind approach and the accuracy of localization can be further improved by refining the a priori user distribution in the Bayesian technique.

Entities in the Internet, ranging from individuals and enterprises to service providers, face a broad range of epidemic risks such as worms, viruses, and botnet-driven attacks. Those risks are interdependent risks, which means that the decision by an entity to invest in security and self-protect affects the risk faced by others (for example, the risk faced by an individual decreases when its providers increases its investments in security). As a result of this, entities tend to invest too little in self-protection, relative to the socially efficient level, by ignoring benefits conferred on by others. In this paper, we consider the problem of designing incentives to entities in the Internet so that they invest at a socially efficient level. In particular, we find that insurance is a powerful incentive mechanism which pushes agents to invest in self-protection. Thus, insurance increases the level of self-protection, and therefore the level of security, in the Internet. As a result, we believe that insurance should be considered as an important component of risk management in the Internet.

Managing security risks in the Internet has so far mostly involved methods to reduce the risks and the severity of the damages. Those methods (such as firewalls, intrusion detection and prevention, etc) reduce but do not eliminate risk, and the question remains on how to handle the residual risk. In this paper, we take a new approach to the problem of Internet security and advocate managing this residual risk by buying insurance against it. Using insurance in the Internet raises several questions because entities in the Internet face correlated risks, which means that insurance claims will likely be correlated, making those entities less attractive to insurance companies. Furthermore, risks are interdependent, meaning that the decision by an entity to invest in security and self-protect affects the risk faced by others. We analyze the impact of these externalities on the security investments of users using a simple 2-agent model. Our key results are that there are sound economic reasons for agents to not invest much in self-protection, and that insurance is a desirable incentive mechanism which pushes agents over a threshold into a desirable state where they all invest in self-protection. In other words, insurance increases the level of self-protection, and therefore the level of security, in the Internet. Therefore, we believe that insurance should become an important component of risk management in the Internet.

We analyze a massive social network, gathered from the records of a large mobile phone operator, with more than a million users and tens of millions of calls. We examine the distributions of the number of phone calls per customer; the total talk minutes per customer; and the distinct number of calling partners per customer. We find that these distributions are skewed, and that they significantly deviate from what would be expected by power-law and lognormal distributions.

Getting new security features and protocols to be widely adopted and deployed in the Internet has been a continuing challenge. There are several reasons for this, in particular economic reasons arising from the presence of network externalities. Indeed, like the Internet itself, the technologies to secure it exhibit network effects: their value to individual users changes as other users decide to adopt them or not. In particular, the benefits felt by early adopters of security solutions might fall significantly below the cost of adoption, making it difficult for those solutions to gain attraction and get deployed at a large scale.

Packet delay and loss are two fundamental measures of performance. Using active probing to measure delay and loss typically involves sending Poisson probes, on the basis of the PASTA property (Poisson Arrivals See Time Averages), which ensures that Poisson probing yields unbiased estimates. Recent work, however, has questioned the utility of PASTA for probing and shown that, for delay measurements, i) a wide variety of processes other than Poisson can be used to probe with zero bias and ii) Poisson probing does not necessarily minimize the variance of delay estimates.

Locating mobile users and devices efficiently is a critical operation in cellular networks. This is done using a combination of location update(by the mobile) and paging (by the network). The paging scheme determines how and where to search for a mobile user given the latestlocation update information from that user. In this paper, we considerhow to increase the efficiency of the paging scheme.

Packet sampling is widely used in network monitoring. Sampled packet streams are often used to determine flow-level statistics of network traffic. To date there is conflicting evidence on the quality of the resulting estimates. In this paper we take a systematic approach, using the Fisher information metric and the Cramér-Rao bound, to understand the contributions that different types of information within sampled packets have on the quality of flow-level estimates. We provide concrete evidence that, without protocol information and with packet sampling rate p = 0.005, any accurate unbiased estimator needs approximately 1016 sampled flows. The required number of sampled flows drops to roughly 104 with the use of TCP sequence numbers. Furthermore, additional SYN flag information significantly reduces the estimation error of short flows. We present a Maximum Likelihood Estimator (MLE) that relies on all of this information and show that it is efficient, even when applied to a small sample set. We validate our results using Tier-1 Internet backbone traces and evaluate the benefits of sampling from multiple monitors. Our results show that combining estimates from several monitors is 50% less accurate than an estimate based on all samples.

Poisson Arrivals See Time Averages (PASTA) is a well known property applicable to many stochastic systems. In active probing, PASTA is invoked to justify the sending of probe packets (or trains) at Poisson times in a variety of contexts. However, due to the diversity of aims and analysis techniques used in active probing, the benefits of Poisson based measurement, and the utility and role of PASTA, are unclear. Using a combination of rigorous results and carefully constructed examples and counter-examples, we map out the issues involved, and argue that PASTA is of very limited use in active probing. In particular, Poisson probes are not unique in their ability to sample without bias. Furthermore, PASTA ignores the issue of estimation variance, and the central need for an inversion phase to estimate the quantity of interest ased on what is directly observable. We give concrete examples of when Poisson probes should not be used, and explain why, and offer initial guidelines on suitable alternative sending processes.

Active probing heuristics are usually based on queuing systems. However, a rigorous probabilistic treatment of probing methods has been lacking. For instance, it is not known even in principle, what can and cannot be measured in general, nor the true limitations of existing methods. We provide a probabilistic treatment for the measurement of cross traffic in the 1-hop case. We derive inversion formulae for the cross traffic process, and explain their fundamental limits, using an intuitive geometric framework.

End-to-end congestion control mechanisms such as those in TCP are not enough to prevent congestion collapse in the Internet, and they must be supplemented by control mechanisms inside the network. The IRTF has singled out random early detection (RED) as one queue management scheme recommended for rapid deployment throughout the Internet. However, RED is not a thoroughly understood scheme-witness for example how the recommended parameter setting, or even the various benefits RED is claimed to provide, have changed over the past few years. In this paper, we describe simple analytic models for RED, and use these models to quantify the benefits (or lack thereof) brought about by RED. In particular, we examine the impact of RED on the loss and delay suffered by bursty and less bursty traffic (such as TCP and UDP traffic, respectively). We find that: (i) RED does eliminate the higher loss bias against bursty traffic observed with tail drop, but not by decreasing the loss rate of bursty traffic, rather by increasing that of non bursty traffic; (ii) the number of consecutive packet drops is higher with RED than tail drop, suggesting RED might not help as anticipated with the global synchronization of TCP flows; (iii) RED can be used to control the average queueing delay in routers and hence the end to end delay, but increases the jitter of non bursty streams. Thus, applications that generate smooth traffic, such as interactive audio applications, will suffer higher loss rates and require large playout buffers, thereby negating at least in part the lower mean delay brought about by RED.

We examine in this paper the tradeoff between application complexity, network complexity, and network efficiency. We argue that the design of the current Internet reflects a tradeoff between lower network complexity (no state in the network, no signalling) and higher application complexity (rate and error control mechanisms to obtain an adaptive application) assuming a unicast service model. For such a service model, a design methodology that leans heavily towards application complexity has proven very successful. However, we also argue that this tradeoff changes radically for a multicast/multilayer service model. These insights motivate a new service model which slightly departs from the best-effort model, and which trades off a slightly higher network complexity for much lower application complexity and higher network efficiency. We describe this service model and the associated network protocols. The protocol complexity is only marginally higher than that of a simple multicast routing protocol with receiver-initiated join/leave capabilities. The dependencies between multilayer flows are established and maintained as soft state; therefore, no explicit session signalling to establish and tear down the flow dependence state is necessary.

Excessive packet loss rates can dramatically decrease the audio quality perceived by users of Internet telephony applications. Previous results suggest that error control schemes using forward error correction (FEC) are good candidates for decreasing the impact of packet loss on audio quality. However, the FEC scheme must be coupled to a rate control scheme. Furthermore, the amount of redundant information used at any given point in time should also depend on the characteristics of the loss process at that time (it would make no sense to send much redundant information when the channel is loss free), on the end to end delay constraints (destination typically have to wait longer to decode the FEC as more FEC information is used), on the quality of the redundant information, etc. However, it is not clear given all these constraints how to choose the "best" possible redundant information. We address this issue, and illustrate the approach using an FEC scheme for packet audio standardized in the IETF. We show that the problem of finding the best redundant information can be expressed mathematically as a constrained optimization problem for which we give explicit solutions. We obtain from these solutions a simple algorithm with very interesting features, namely (i) the algorithm optimizes a subjective measure (such as the audio quality perceived at a destination) as opposed to an objective measure of quality (such as the packet loss rate at a destination), (ii) it incorporates the constraints of rate control and playout delay adjustment schemes, and (iii) it adapts to varying loss conditions in the network (estimated online with RTCP feedback). We have been using the algorithm, together with a TCP-friendly rate control scheme and we have found it to provide very good audio quality even over paths with high and varying loss rates. We present simulation and experimental results to illustrate its performance.

Schemes based on the tagging of packets have been proposed as a low-cost way to augment the single class best effort service model of the current Internet by including some kind of service discrimination. Such schemes have a number of attractive features, however, it is not clear exactly what kind of service they would provide to applications. Yet quantifying such service is very important to understand the benefits and drawbacks of the different tagging schemes and of the mechanisms in each scheme (for example how much RED with input and output (RIO) contributes in the assured scheme), and to tackle key performance and economic issues (e.g. the difference in tariff between different service classes would presumably depend on the difference in performance between the classes). The goal in this paper is to obtain a quantitative description of the service provided by tagging schemes. Specifically, we describe and solve simple analytic models of two previously proposed schemes, namely the assured service scheme and the premium service scheme. We obtain expressions for performance measures that characterize the service provided to tagged packets, the service provided to non-tagged packets, and the fraction of tagged packets that do not get the better service they were supposed to. We use these expressions, as well as simulations and experiments from actual implementations, to illustrate the benefits and shortcomings of the schemes.

There is much experimental evidence that network traffic processes exhibit ubiquitous properties of self-similarity and long-range dependence, i.e., of correlations over a wide range of time scales. However, there is still considerable debate about how to model such processes and about their impact on network and application performance. In this paper, we argue that much previous modeling work has failed to consider the impact of two important parameters, namely the finite range of time scales of interest in performance evaluation and prediction problems, and the first-order statistics such as the marginal distribution of the process. We introduce and evaluate a model in which these parameters can be controlled. Specifically, our model is a modulated fluid traffic model in which the correlation function of the fluid rate matches that of an asymptotically second-order self-similar process with given Hurst parameter up to an arbitrary cutoff time lag, then drops to zero. We develop a very efficient numerical procedure to evaluate the performance of a single-server queue fed with the above fluid input process. We use this procedure to examine the fluid loss rate for a wide range of marginal distributions, Hurst (1950) parameters, cutoff lags, and buffer sizes. Our main results are as follows. First, we find that the amount of correlation that needs to be taken into account for performance evaluation depends not only on the correlation structure of the source traffic, but also on time scales specific to the system under study. For example, the time scale associated with a queueing system is a function of the maximum buffer size. Thus, for finite buffer queues, we find that the impact on loss of the correlation in the arrival process becomes nil beyond a time scale we refer to as the correlation horizon. This means, in particular, that for performance-modeling purposes, we may choose any model among the panoply of available models (including Markovian and self-similar models) as long as the chosen model captures the correlation structure of the source traffic up to the correlation horizon. Second, we find that loss can depend in a crucial way on the marginal distribution of the fluid rate process. Third, our results suggest that reducing loss by buffering is hard for traffic with correlation over many time scales. We advocate the use of source traffic control and statistical multiplexing instead.

Much of the work on distributed virtual environments (DVEs) has focused on efficient schemes and algorithms for the description and visual rendering of such environments. However, there has been comparatively little effort on senses other than sight, and in particular on live voice. This is surprising because adding voice to DVEs enhances the sense of immersion in the environment, and can in fact completely change the way entities interact. For example, adding voice in a distributed game impacts tactics, team building, cheating, etc. We examine issues related to adding voice between participants in DVEs. We consider in particular a special kind of DVE, namely distributed games over the Internet. We consider all stages of voice manipulation, including voice generation (with emphasis on echo cancellation), voice transmission (with emphasis on RTP and packetization), and voice restitution (with emphasis on spatial rendition and on synchronization between voice and visual cues). We also consider implementation issues, and illustrate these with the MiMaze game and the FreePhone audio tool, both developed at INRIA.

Anecdotal evidence suggests that the quality of many videoconferences in the Internet is mediocre because of high packet loss rates. This makes it important to design and implement mechanisms that minimize packet loss and its impact in video (and audio) applications. There are two such types of mechanisms. Rate control mechanisms attempt to minimize the amount of packet loss by matching the bandwidth requirements of a video flow to the capacity available in the network. However, they do not prevent packet loss altogether. Error control mechanisms attempt to minimize the visual impact of lost packets at the destinations. We provide motivation for using error control mechanisms based on forward error correction (FEC) and packet reconstruction. We examine a specific mechanism, and evaluate its cost as well as the benefit expected from using it. This mechanism can be augmented to obtain a joint source/channel coding scheme suitable for both the current and the future integrated services Internet.

The Internet provides a single class best effort service. From an application's point of view, this service amounts in practice to providing channels with time-varying characteristics such as delay and loss distributions. One way to support real time applications such as interactive audio given this service is to use control mechanisms that adapt the audio coding and decoding processes based on the characteristics of the channels, the goal being to maximize the quality of the audio delivered to the destinations. In this paper, we describe and analyze a set of such control mechanisms. They include a jitter control mechanism and a combined error and rate control mechanism. These mechanisms have been implemented and evaluated over the Internet and the MBone. Experiments indicate that they make it possible to establish and maintain reasonable quality audioconferences even across fairly congested connections.

There is much experimental evidence that network traffic processes exhibit ubiquitous properties of self-similarity and long range dependence (LRD), i.e. of correlations over a wide range of time scales. However, there is still considerable debate about how to model such processes and about their impact on network and application performance. In this paper, we argue that much recent modeling work has failed to consider the impact of two important parameters, namely the finite range of time scales of interest in performance evaluation and prediction problems, and the first-order statistics such as the marginal distribution of the process. We introduce and evaluate a model in which these parameters can be controlled. Specifically, our model is a modulated fluid traffic model in which the correlation function of the fluid rate matches that of an asymptotically second-order self-similar process with given Hurst parameter up to an arbitrary cutoff time lag, then drops to zero. We develop a...

We present simple exponential approximations to the transient behavior of the stable M/M/1 queue. The approximations are optimal in a least-squares sense, and we find them to agree well with exact results. Our approach can be used to derive approximations for any time-dependent quantity with a known Laplace transform, e.g., the probability distribution and the moments of the queue size, of the waiting time, etc. It is the only approach we are aware of in which the error between approximations and exact results can be explicitly computed.>

Datagram networks such as the Internet do not provide guaranteed resources such as bandwidth or guaranteed performance measures such as maximum delay. One way to support packet video in these networks is to use feedback mechanisms that adapt the output rate of video coders based on the state of the network. The authors present one such mechanism. They describe the feedback information, and how it is used by the coder control algorithm. They also examine how the need to operate in a multicast environment impacts the design of the control mechanism. This mechanism has been implemented in the H.261 video coder of IVS. IVS is a videoconference system for the Internet developed at INRIA. Experiments indicate that the control mechanism is well suited to the Internet environment. In particular, it makes it possible to establish and maintain quality videoconferences even across congested connections in the Internet. Furthermore, it prevents video sources from swamping the resources of the Internet, which could lead to unacceptable service to all users of the network.>

We describe a mechanism for scalable control of multicast continuous media streams. The mechanism uses a novel probing mechanism to solicit feedback information in a scalable manner and to estimate the number of receivers. In addition, it separates the congestion signal from the congestion control algorithm, so as to cope with heterogeneous networks.

The OSI (Open Systems Interconnection) X.500 directory system and other distributed naming systems use name caching to minimize the cost of name lookups for nonlocal names. The authors evaluate the impact of name caching on the performance of the OSI directory system. They consider the issues of cache sizing and cache replacement policies. It was found that a locality of reference property holds in name resolution requests, and hence name caching does increase performance significantly. Using trace-driven simulation, it is shown that small caches (smaller than 30 items) yield hit ratios up to 60% and decrease the average name resolution time by 60%. For small caches, the LRU (least recently used) replacement policy is better than other implementable policies. Large caches yield predictably larger hit ratios. For large caches, however, the LRU policy is not better than a random replacement policy. It was also found that partitioning the cache buffer into a small number of independent caches, each one associated with a different kind of name request, further decreases the average name resolution time.>

We use the measured round trip delays of small UDP probe packets sent at regular time intervals to analyze the end-to-end packet delay and loss behavior in the Internet. By varying the interval between probe packets, it is possible to study the structure of the Internet load over different time scales. In this paper, the time scales of interest range from a few milliseconds to a few minutes. Our observations agree with results obtained by others using simulation and experimental approaches. For example, our estimates of Internet workload are consistent with the hypothesis of a mix of bulk traffic with larger packet size, and interactive traffic with smaller packet size. We observe compression (or clustering) of the probe packets, rapid fluctuations of queueing delays over small intervals, etc. Our results also show interesting and less expected behavior. For example, we find that the losses of probe packets are essentially random unless the probe traffic uses a large fraction of the available bandwidth. We discuss the implications of these results on the design of control mechanisms for the Internet.

The authors consider a flow control mechanism that dynamically regulates the rate of data flow into a network based on feedback information about the network state. Such mechanisms have been introduced in a variety of networks, and have been advocated for future high-speed networks. The authors first model the flow control mechanism by a discrete-space stochastic process and define appropriate performance measures for transient and steady-state regimes. However, the model does not appear to be analytically tractable, and the authors study it through simulation. They then simplify it to a continuous-space deterministic (or fluid) model for which closed-form solutions can be derived easily. It is found that the analytical results for the fluid model agree well with the simulation results obtained using the discrete-space model. Both models explicitly consider delay of the feedback information, thus making them relevant for high-speed networks.>