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.

One of the key distinctive requirements of white-space networks is the power asymmetry. Static nodes are allowed to transmit with 15dB-20dB higher power than mobile nodes. This poses significant coexistence problems, as high-power nodes can easily starve low-power nodes. In this paper, we propose Weeble, a novel distributed and state-less MAC protocol that solves the coexistence problem. One of the key building blocks is an adaptive preamble support, an add-on to the PHY layer that allows high-power nodes to detect a low-power transmission even when the difference in transmit power is as high as 20dB. The other key building block is a MAC protocol that exploits the adaptive preambles functionality. It implements a virtual carrier-sensing and automatically adapts the preamble size to optimize network performance. We extensively evaluate our system in a test-bed and in simulations. We show that we can prevent starvation of low-power nodes in almost all existing scenarios and improve the data rates of low-power links several-fold over existing MACs, and as a trade-off we decrease the throughput of the rest of the system by 20%-40%.

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.

We consider the problem of delivering information streams to interested mobile users, leveraging both access to the infrastructure and device-to-device data transfers. The goal is to design practical relaying algorithms that aim at optimizing a global system objective that accounts for two important aspects: first, the user interest in content with respect to its type and delivery time; and, second, resource constraints such as storage and transmission costs. We first examine a set of real-world datasets reporting contacts between users moving in relatively restricted geographic areas (e.g. a city). These datasets provide evidence that significant performance gains can be achieved by extending the information dissemination from one to two hops, and that using longer paths only brings marginal benefits. We also show that correlation of delays through different paths is typically significant, thus asking for system design that would allow for general user mobility.

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.

In this paper, we aim at characterizing podcast services both from publishers' and users' perspectives, and at analyzing the implications of these characteristics on the design of efficient dissemination systems. Specifically, our goal is to characterize how podcasting content is generated and published, and how users subscribe and consume podcasts. We are also interested in understanding whether podcast episodes are efficiently disseminated to users just using a sporadic direct access to the Internet (which is the current way of downloading podcast episodes), or whether the use of peer-to-peer mobile device-to-device dissemination systems could help enhancing the performance of podcast services.Our study is based on traces of podcast episode releases, subscriptions, and play times from major podcast service providers. An extensive analysis of the traces allows us to develop a comprehensive model of current podcast services, and provide statistics about the type and content of the typical podcasts, the size and the release frequencies of their episodes, as well as their popularity. By studying podcast usage, we show that the service is delay-tolerant, as users may well play podcast episodes a long time after their actual release. An interesting consequence of this delay tolerance is that mobile device-to-device dissemination systems would not be very useful for the current typical podcasts, while they may become more attractive for future interactive podcast services.

We consider the problem of ranking the popularity of items and suggesting popular items based on user feedback. User feedback is obtained by iteratively presenting a set of suggested items, and users selecting items based on their own preferences either from this suggestion set or from the set of all possible items. The goal is to quickly learn the true popularity ranking of items (unbiased by the made suggestions), and suggest true popular items. The difficulty is that making suggestions to users can reinforce popularity of some items and distort the resulting item ranking. The described problem of ranking and suggesting items arises in diverse applications including search query suggestions and tag suggestions for social tagging systems. We propose and study several algorithms for ranking and suggesting popular items, provide analytical results on their performance, and present numerical results obtained using the inferred popularity of tags from a month-long crawl of a popular social book marking service. Our results suggest that lightweight, randomized update rules that require no special configuration parameters provide good performance.

This paper aims to quantify two common assumptions about social tagging: (1) that tags are "meaningful" and (2) that the tagging process is influenced by tag suggestions. For (1), we analyze the semantic properties of tags and the relationship between the tags and the content of the tagged page. Our analysis is based on a corpus of search keywords, contents, titles, and tags applied to several thousand popular Web pages. Among other results, we find that the more popular tags of a page tend to be the more meaningful ones. For (2), we develop a model of how the influence of tag suggestions can be measured. From a user study with over 4,000 participants, we conclude that roughly one third of the tag applications may be induced by the suggestions. Our results would be of interest for designers of social tagging systems and are a step towards understanding how to best leverage social tags for applications such as search and information extraction.

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.

Digital media companies have recently started embracing P2P networks as an alternative distribution mechanism. However, with current P2P swarming systems users need to download the full video, and hence have to wait a long time before they can start watching it. While a lot of effort has gone into optimizing the distribution of large files, little research has been done on enabling Video-on-Demand (VoD) functionality with P2P swarming systems. The main challenges reside in ensuring that users can start watching a movie at any point in time, with small start-up times and sustainable playback rates. In this work, we address the issues of providing VoD using P2P mesh-based networks. We investigate scheduling techniques, and network coding in particular. Using both simulations and a prototype implementation, we show that high-quality VoD is feasible, and give guidelines to build play-as-you-download P2P swarming systems with high playback rates and low start-up delays.

We propose a novel transport control protocol, Competitive and Considerate Congestion Control (4CP). This yields a fixed per-flow bandwidth to other connections (e.g. TCP) if the network can support this and uses the residual bandwidth for 4CP. The main contribution is a novel window based congestion controller that combines congestion phase detection and congestion window control to achieve the stated bandwidth sharing objective. 4CP may be viewed as a non strict low priority emulator. Consequently, 4CP does not suffer from bandwidth starvation when competing with a single TCP connection. Furthermore, when congestion is low, 4CP can utilise residual bandwidth. When congestion is high, 4CP will back-off. The properties of 4CP described above, suggest its applicability for bulk data transfer applications that must be considerate of competing traffic whilst still making transfer progress themselves. We present analytical results, simulation findings and Internet experiments that demonstrate validity of 4CP in addition to guidance on parameter setting.

Peer-to-peer technologies are increasingly becoming the medium of choice for delivering media content, both professional and homegrown, to large user populations. Indeed, current P2P swarming systems have been shown to be very efficient for large-scale content distribution with few server resources. However, such systems have been designed for generic file distribution and provide a limited user experience for viewing media content. For example, users need to wait to download the full video before they can start watching it. In general, the main challenge resides in designing systems that ensure that users can start watching a movie at any point in time, with small start-up times and sustainable playback rates. In this work, we address the issues of providing a Video-on-Demand (VoD) using P2P mesh-based networks. We show that providing high quality VoD using P2P is feasible using a combination of techniques including (a) network coding, (b) optimized resource allocation across different parts of the video, and (c) overlay topology management algorithms. Our evaluation also shows that systems that do not optimize in all these dimensions could significantly under-utilize the network resources resulting in poor VoD performance. We present our results based on simulations and a prototype implementation. Categories and Subject Descriptors

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.