We examine competition between two Internet Service Providers (ISPs), where the first ISP provides basic Internet service, while the second ISP provides Internet service plus content, i.e., enhanced service, where the first ISP can partner with a Content Provider to provide the same content as the second ISP. When such a partnering arrangement occurs, the Content Provider pays the first ISP a transfer price for delivering the content. Users have heterogeneous preferences, and each in general faces three options: (1) buy basic Internet service from the first ISP; (2) buy enhanced service from the second ISP; or (3) buy enhanced service jointly from the first ISP and the Content Provider. We derive results on the existence and uniqueness of a Nash equilibrium, and provide closed-form expressions for the prices, user masses, and profits of the two ISPs and the Content Provider. When the first ISP has the ability to choose the transfer price, then when congestion is linear in the load, it is never optimal for the first ISP to set a negative transfer price in the hope of attracting more revenue from additional customers desiring enhanced service. Conversely, when congestion is sufficiently super-linear, the optimal strategy for the first ISP is either to set a negative transfer price (subsidizing the Content Provider) or to set a high transfer price that shuts the Content Provider out of the market.

As the quality of computer hardware increases over time, cloud service providers have the ability to offer more powerful virtual machines (VMs) and other resources to their customers. But providers face several trade-offs as they seek to make the best use of improved technology. On one hand, more powerful machines are more valuable to customers and command a higher price. On the other hand, there is a cost to develop and launch a new product. Further, the new product competes with existing products. Thus, the provider faces two questions. First, when should new classes of VMs be introduced? Second, how should they be priced, taking into account both the VM classes that currently exist and the ones that will be introduced in the future?

We propose a system for determining properties of mathematical functions given an image of their graph representation. We demonstrate our approach for two-dimensional graphs (curves of single variable functions) and three-dimensional graphs (surfaces of two variable functions), studying the properties of convexity and symmetry. Our method uses a Convolutional Neural Network which classifies functions according to these properties, without using any hand-crafted features. We propose algorithms for randomly constructing functions with convexity or symmetry properties, and use the images generated by these algorithms to train our network. Our system achieves a high accuracy on this task, even for functions where humans find it difficult to determine the function's properties from its image.

The Generalized Second Price (GSP) auction has appealing properties when ads are simple (text based and identical in size), but does not generalize to richer ad settings, whereas truthful mechanisms such as VCG do. However, a straight switch from GSP to VCG incurs significant revenue loss for the search engine. We introduce a transitional mechanism which encourages advertisers to update their bids to their valuations, while mitigating revenue loss. In this setting, it is easier to propose first a payment function rather than an allocation function, so we give a general framework which guarantees incentive compatibility by requiring that the payment functions satisfy two specific properties. Finally, we analyze the revenue impacts of our mechanism on a sample of Bing data.

The layouts of the buildings we live in shape our everyday lives. In office environments, building spaces affect employees' communication, which is crucial for productivity and innovation. However, accurate measurement of how spatial layouts affect interactions is a major challenge and traditional techniques may not give an objective view.

We examine trade-offs among stakeholders in ad auctions. Our metrics are the revenue for the utility of the auctioneer, the number of clicks for the utility of the users and the welfare for the utility of the advertisers. We show how to optimize linear combinations of the stakeholder utilities, showing that these can be tackled through a GSP auction with a per-click reserve price. We then examine constrained optimization of stakeholder utilities.

We consider a large-scale Ad-auction where adverts are assigned over a potentially infinite number of searches. We capture the intrinsic asymmetries in information between advertisers, the advert platform and the space of searches: advertisers know and can optimize the average performance of their advertisement campaign; the platform knows and can optimize on each search instance; and, neither party knows the distribution of the infinite number of searches that can occur. We look at maximizing the aggregate utility of the click-through rates of advertisers subject to the matching constraints of online ad allocation.

Object localization is an image annotation task which consists of finding the location of a target object in an image. It is common to crowdsource annotation tasks and aggregate responses to estimate the true annotation. While for other kinds of annotations consensus is simple and powerful, it cannot be applied to object localization as effectively due to the task's rich answer space and inherent noise in responses. We propose a probabilistic graphical model to localize objects in images based on responses from the crowd. We improve upon natural aggregation methods such as the mean and the median by simultaneously estimating the difficulty level of each question and skill level of every participant. We empirically evaluate our model on crowdsourced data and show that our method outperforms simple aggregators both in estimating the true locations and in ranking participants by their ability. We also propose a simple adaptive sourcing scheme that works well for very sparse datasets.

Agents are asked to rank two objects in a setting where effort is costly and agents differ in quality (which is the probability that they can identify the correct, ground truth, ranking). We study simple output-agreement mechanisms that pay an agent in the case she agrees with the report of another, and potentially penalizes for disagreement through a negative payment. Assuming access to a quality oracle, able to determine whether an agent's quality is above a given threshold, we design a payment scheme that aligns incentives so that agents whose quality is above this threshold participate and invest effort. Precluding negative payments leads the expected cost of this quality-oracle mechanism to increase by a factor of 2 to 5 relative to allowing both positive and negative payments. Dropping the assumption about access to a quality oracle, we further show that negative payments can be used to make agents with quality lower than the quality threshold choose to not to participate, while those above continue to participate and invest effort. Through the appropriate choice of payments, any design threshold can be achieved. This self-selection mechanism has the same expected cost as the cost-minimal quality-oracle mechanism, and thus when using the self-selection mechanism, perfect screening comes for free.

In a sponsored search auction, decisions about how to rank ads impose tradeoffs between objectives such as revenue and welfare. In this paper, we examine how these tradeoffs should be made. We begin by arguing that the most natural solution concept to evaluate these tradeoffs is the lowest symmetric Nash equilibrium (SNE). As part of this argument, we generalise the well known connection between the lowest SNE and the VCG outcome. We then propose a new ranking algorithm, loosely based on the revenue-optimal auction, that uses a reserve price to order the ads (not just to filter them) and give conditions under which it raises more revenue than simply applying that reserve price. Finally, we conduct extensive simulations examining the tradeoffs enabled by different ranking algorithms and show that our proposed algorithm enables superior operating points by a variety of metrics.

We examine designs for crowdsourcing contests, where participants compete for rewards given to superior solutions of a task. We theoretically analyze tradeoffs between the expectation and variance of the principal's utility (i.e. the best solution's quality), and empirically test our theoretical predictions using a controlled experiment on Amazon Mechanical Turk. Our evaluation method is also crowdsourcing based and relies on the peer prediction mechanism. Our theoretical analysis shows an expectation-variance tradeoff of the principal's utility in such contests through a Pareto efficient frontier. In particular, we show that the simple contest with 2 authors and the 2-pair contest have good theoretical properties. In contrast, our empirical results show that the 2-pair contest is the superior design among all designs tested, achieving the highest expectation and lowest variance of the principal's utility.

We propose a natural model for agent failures in congestion games. In our model, each of the agents may fail to participate in the game, introducing uncertainty regarding the set of active agents. We examine how such uncertainty may change the Nash equilibria (NE) of the game. We prove that although the perturbed game induced by the failure model is not always a congestion game, it still admits at least one pure Nash equilibrium. Then, we turn to examine the effect of failures on the maximal social cost in any NE of the perturbed game. We show that in the limit case where failure probability is negligible new equilibria never emerge, and that the social cost may decrease but it never increases. For the case of non-negligible failure probabilities, we provide a full characterization of the maximal impact of failures on the social cost under worst-case equilibrium outcomes.

We investigate dynamic channel, rate selection and scheduling for wireless systems which exploit the large number of channels available in the White-space spectrum. We first present measurements of radio channel characteristics from an indoor testbed operating in the 500 to 600MHz band and comprising 11 channels. We observe significant and unpredictable (non-stationary) variations in the quality of these channels, and demonstrate the potential benefit in throughput from tracking the best channel and also from optimally adapting the transmission rate. We propose adaptive learning schemes able to efficiently track the best channel and rate for transmission, even in scenarios with non-stationary channel condition variations. We also describe a joint scheduling scheme for providing fairness in an Access Point scenario. Finally, we implement the proposed adaptive scheme in our testbed, and demonstrate that it achieves significant throughput improvement (typically from 40% to 100%) compared to traditional fixed channel selection schemes.

Sponsored search advertisement slots are currently sold via Generalized Second Price (GSP) auctions. Despite the simplicity of their rules, these auctions are far from being fully understood. Our observations on real ad-auction data show that advertisers usually enter many distinct auctions with different opponents and with varying parameters. We describe some of our findings from these observations and propose a simple probabilistic model taking them into account. This model can be used to predict the number of clicks received by the advertisers and the total price they can expect to pay depending on their bid, or even to estimate the players valuations, all at a very low computational cost.

Recent advances in PHY layer design demonstrated efficient self-interference cancellation and full-duplex in a single band. Building a MAC that exploits self-interference cancellation is a challenging task. Links can be scheduled concurrently, but only if they either (i) don't interfere or (ii) allow for self-interference cancellation. Two issues arise: Firstly, it is difficult to construct a schedule that fully exploits the potentials for self-interference cancellation for arbitrary traffic patterns. Secondly, designing an efficient and fair distributed MAC is a daunting task; the issues become even more pronounced when scheduling under the constraints. We propose ContraFlow, a novel MAC that exploits the benefits of self-interference cancellation and increases spatial reuse. We use full-duplex to eliminate hidden terminals, and we rectify decentralized coordination inefficiencies among nodes, thereby improving fairness. Using measurements and simulations we illustrate the performance gains achieved when ContraFlow is used and we obtain both a throughput increase over current systems, as well as a significant improvement in fairness.

As more technologies enter the home, householders are burdened with the task of digital housekeeping-managing and sharing digital resources like bandwidth. In response to this, we created and evaluated a domestic tool for bandwidth management called Home Watcher. Our field trial showed that when resource contention amongst different household members is made visible, people's understanding of bandwidth changes and household politics are revealed. In this paper, we describe the consequences of showing real time resource usage in a home, and how this varies depending on the social make up of the household.

We consider the problem of traffic management in small networks with both wireless and wired devices, connected to the Internet through a single gateway. Examples of such networks are small office networks or residential networks, where typically traffic management is limited to flow prioritization through port-based filtering.

This paper studies the performance of contention based medium access control (MAC) protocols. In particular, a simple and accurate technique for estimating the throughput of the IEEE 802.11 DCF protocol is developed. The technique is based on a rigorous analysis of the Markov chain that corresponds to the time evolution of the back-off processes at the contending nodes. An extension of the technique is presented to handle the case where service differentiation is provided with the use of heterogeneous protocol parameters, as, for example, in IEEE 802.11e EDCA protocol. Our results provide new insights into the operation of such protocols. The techniques developed in the paper are applicable to a wide variety of contention based MAC protocols.

The past ten years have seen dramatic changes in networking. For example, wireless and the Internet have overtaken traditional telecommunication networks. Yet some of the economic incentives and standardspsila policies that have enabled such growth have also inhibited other forms of evolutionary development. For instance, the fundamental architecture of the Internet has changed little. This has led to flurry of interest in ldquoClean Slaterdquo approaches to next-generation networks. Instead, we ask how far it is possible go without re-architecting networks, by exploiting some current research ideas.We discuss control strategies for communication networks such as the Internet, or multihop networks where the aim is to optimize network performance in some sense. We address some key issues concerned with economics, bandwidth guarantees and security, using content distribution as a motivating example. We describe how welfare maximization can be used as a paradigm for network resource allocation, and also be used to derive practical rate-control algorithms. We apply this to the case of multipath transfers, where multiple paths are used to transfer data, and where we can use decentralised protocols to effectively load-balance across the network. We discuss how this, coupled with a dynamic path selection scheme can lead to an efficient ldquosocial welfarerdquo optimum, and how some current peer-to-peer systems embody elements of this approach. The benefit to the users is better performance, while offering simpler and more robust engineering for ISPs. We comment on incentives and pricing issues for both users and providers.

We consider the problem of determining the "closest", or best Internet host to connect to, from a list of candidate servers. Most existing approaches rely on the use of metric, or more specifically Euclidean coordinates to infer network proximity. This is problematic, given that network distances such as latency are known to violate the triangle inequality. This leads us to consider non-metric coordinate systems. We perform an empirical comparison between the "min-plus" non-metric coordinates and two metric coordinates, namely L-infinity and Euclidean. We observe that, when sufficiently many dimensions are used, min-plus outperforms metric coordinates for predicting Internet latencies. We also consider the prediction of "widest path capacity" between nodes. In this framework, we propose a generalization of min-plus coordinates. These results apply when node coordinates consist in measured network proximity to a random subset of landmark nodes. We perform empirical validation of these results on widest path bandwidth between PlanetLab nodes. We conclude that appropriate non-metric coordinates such as generalized min-plus systems are better suited than metric systems for representing the underlying structure of Internet distances, measured either via latencies or bandwidth.

We consider wireless mesh networks, and exploit the inherent broadcast nature of wireless by making use of multipath routing. We present an optimization framework that enables us to derive optimal flow control, routing, scheduling, and rate adaptation schemes, where we use network coding to ease the routing problem. We prove optimality and derive a primal-dual algorithm that lays the basis for a practical protocol. We use simulation to show on realistic topologies that we can achieve 20-200% throughput improvement compared to single path routing, and several times compared to a recent related opportunistic protocol (MORE).

There has been extensive work on network architectures that support multi-path routing to improve performance in wireless mesh networks. However, previous work uses ad-hoc design principles that cannot guarantee any network-wide performance objectives such as conjointly maximizing resource utilization and improving fairness. In parallel, numerous theoretical results have addressed the issue of optimizing a combined metric of network utilization and fairness using techniques based on back-pressure scheduling, routing and flow control. However, the proposed theoretical algorithms are extremely difficult to implement in practice, especially in the presence of the 802.11 MAC and TCP. We propose Horizon, a novel system design for multi-path forwarding in wireless meshes, based on the theoretical results on back-pressure. Our design works with an unmodified TCP stack and on top of the existing 802.11 MAC. We modified the back-pressure approach to obtain a simple 802.11-compatible packet-forwarding heuristic and a novel, light-weight path estimator, while maintaining global optimality properties. We propose a delayed reordering algorithm that eliminates TCP timeouts while keeping TCP packet reordering to a minimum. We have evaluated our implementation on a 22-node testbed. We have shown that Horizon effectively utilizes available resources (disjoint paths). In contrast to previous work, our design not only avoids bottlenecks but also optimally load-balances traffic across them when needed, improving fairness among competing flows. To our knowledge, Horizon is the first practical wireless system based on back-pressure.

Designing high throughput wireless mesh networks involves solving interrelated scheduling, routing, and interference problems. In this paper, we exploit the broadcast properties and the path diversity of wireless meshes to implement an efficient multipath routing protocol, Multipath Code Casting (MC2).

Combining transport-layer congestion control with multi-path routing is a cross-layer approach that provides performance benefits over treating the layers separately. We phrase this as an optimisation problem, examine the case of data transfers, and show how a coordinated controller gives strictly better performance than an uncoordinated controller, which sets up parallel paths. For fixed demands, and the case of random-path selection, we show how coordinated control also achieves better load balancing than greedy least-loaded path selection. We then comment on adaptive path selection.

In this paper we investigate the potential benefits of coordinated congestion control for multipath data transfers, and contrast with uncoordinated control. For static random path selections, we show the worst-case throughput performance of uncoordinated control behaves as if each user had but a single path (scaling like log(log(N))/log(N) whereNis the system size, measured in number of resources). Whereas coordinated control gives a throughput allocation bounded away from zero, improving on both uncoordinated control and on the greedy-least loaded path selection of e.g. Mitzenmacher. We then allow users to change their set of routes and introduce the notion of a Nash equilibrium. We show that with RTT bias (as in TCP Reno), uncoordinated control can lead to inefficient equilibria. With no RTT bias, both uncoordinated or coordinated Nash equilibria correspond to desirable welfare maximising states. Moreover, simple path reselection polices that shift to paths with higher net benefit can find these states.

Abstract — Current generation worms have caused considerable damage, despite their use of unsophisticated scanning strategies for detecting vulnerable hosts. A number of adaptive techniques have been proposed for quarantining hosts whose behaviour is deemed suspicious. Such techniques have been proven to be effective against fast scanning worms. However, worms could evade detection by being less aggressive. In this paper we consider the interplay between worm strategies and detection techniques, which can be described in game-theoretic terms. We use epidemiological modelling to characterise the outcome of the game (the pay-off function), as a function of the strategies of the worm and the detector. We design detection rules that are optimal against scanning worms with known characteristics. We then identify specific detection rules that are close to optimal, in some mathematically precise sense, against any scanning worm. Finally, we design methods for coordinating information among a set of end-hosts, using Bayesian decision theory. We evaluate the proposed rules using simulations driven by traces from a corporate environment of 600 hosts, and assess the benefits of coordination. I.

Abstract — We study the performance of contention based medium access control (MAC) protocols. In particular, we pro-vide a simple and accurate method for estimating the throughput of IEEE 802.11 DCF and IEEE 802.11e EDCA. Our method is based on a rigorous analysis of the Markov chain associated with the back-off process at the contending nodes. Our results provide new insights into the operation of IEEE 802.11 DCF and IEEE 802.11e EDCA. Although we focus on IEEE 802.11 MAC protocol in this paper, the techniques developed are applicable to a wide variety of contention based MAC protocols. I.

Fluctuations in network conditions are a common phenomenon. They arise in the current wired Internet due to changes in demand, and in wireless networks due to changing interference patterns. However, current congestion control design typically does not account for this, and in this sense the majority of congestion controllers proposed so far can be deemed as "myopic". The present work deals with the following question: how should network end-users exploit such temporal fluctuations? We introduce a formal framework, in which time diversity is explicitly described by phases in network condition. We propose as bandwidth allocation criterion the solution to an optimization problem, which features both classical (myopic) users and so-called farsighted users. We identify the corresponding farsighted user strategy as that maximizing throughput subject to a social norm related to TCP-friendliness. We establish basic desirable properties of the resulting allocations. We propose adaptive decentralized algorithms for farsighted users to achieve their target allocation. The algorithms do not require either explicit knowledge of dynamics in network conditions, or special feedback from the network.

The flow control algorithms currently used in the Internet have been tailored to share available capacity between users on the basis of the physical characteristics of the network links they use rather than the characteristics of their applications. However, real-time applications typically have very different requirements from file transfer or Web browsing, and treating them identically can result in a perception of poor quality of service even when adequate bandwidth is available. This is the motivation for differentiated services. In this paper, we explore service differentiation between persistent (fixed duration) and transient (fixed volume) flows, and also between transient flows of markedly different sizes; the latter is stimulated by current discussion on Web mice and elephants. We propose decentralized bandwidth allocation algorithms that can be implemented by end-systems without requiring the support of a complex network architecture, and show that they achieve performance very close to what is achievable by the optimal centralized scheme.

We introduce PIC, a practical coordinate-based mechanism to estimate Internet network distance (i.e., round-trip delay or network hops). Network distance estimation is important in many applications; for example, network-aware overlay construction and server selection. There are several proposals for distance estimation in the Internet but they all suffer from problems that limit their benefit. Most rely on a small set of infrastructure nodes that are a single point of failure and limit scalability. Others use sets of peers to compute coordinates but these coordinates can be arbitrarily wrong if one of these peers is malicious. While it may be reasonable to secure a small set of infrastructure nodes, it is unreasonable to secure all peers. PIC addresses these problems: it does not rely on infrastructure nodes and it can compute accurate coordinates even when some peers are malicious. We present PIC's design, experimental evaluation, and an application to network-aware overlay construction and maintenance.

Low priority data transfer across the wide area is useful in several contexts, for example for the dissemination of large files such as OS updates, content distribution or prefetching. Although the design of such a service is reasonably easy when the underlying network supports service differentiation, it becomes more challenging without such network support. We describe an application level approach to designing a low priority service -- one that is 'lower than best-effort' in the context of the current Internet. We require neither network support nor changes to TCP. Instead, we use a receive window control to limit the transfer rate of the application, and the optimal rate is determined by detecting a change-point. We motivate this joint control-estimation problem by considering a fluid-based optimisation framework, and describe practical solutions, based on stochastic approximation and binary search techniques. Simulation results demonstrate the effectiveness of the approach.

The aim of this article is to propose and analyse measurement-based admission control schemes. We distinguish between large-scale and small-scale systems, where scale is measured in the number of concurrent applications that can run simultaneously. For large scale systems, we show that simple end-user probing strategies, based on ECN-type feedback provided by the network, achieve a good utilisation/quality trade-off. We explicitly take account of feedback delay, and use limiting results for assessing performance. We illustrate the benefits of using ECN-type feedback rather than relying on loss. For small-scale systems, the previous strategies are no longer adequate and we propose alternative, more gradual probing strategies.

This paper describes a framework for admission control for a packet-based network where the decisions are taken by edge devices or end-systems, rather than resources within the network. The decisions are based on the results of probe packets that the end-systems send through the network, and require only that resources apply a mark to packets in a way that is load dependent. One application example is the Internet, where marking information is fed back via an ECN bit, and we show how this approach allows a rich QoS framework for flows or streams. Our approach allows networks to be explicitly analyzed, and consequently engineered.

This paper describes a simple and robust ATM call admission control, and develops the theoretical background for its analysis. Acceptance decisions are based on whether the current load is less than a precalculated threshold, and Bayesian decision theory provides the framework for the choice of thresholds. This methodology allows an explicit treatment of the trade-off between cell loss and call rejection, and of the consequences of estimation error. Further topics discussed include the robustness of the control to departures from model assumptions, its performance relative to a control possessing precise knowledge of all unknown parameters, the relationship between leaky bucket depths and buffer requirements, and the treatment of multiple call types.>