WORKSHOP PROGRAM ABSTRACTS

Liquidity in Credit Networks: A Little Trust Goes a Long Way
Back to Program
Credit networks represent a way of modeling trust between entities in a network. Nodes in the network print their own currency and trust each other for a certain amount of each other's currency. This allows the network to serve as a decentralized payment infrastructure—arbitrary payments can be routed through the network by passing IOUs between trusting nodes in their respective currencies—and obviates the need for a common currency. Credit networks have the property that the loss incurred by nodes in the network due to the presence of malicious nodes is bounded and localized: a node cannot incur a loss greater than the total credit extended by it to other nodes in the network and the only nodes that incur a loss are the ones that extend credit to the malicious nodes. Also, routing payments in credit networks is not significantly less efficient compared to a centralized network since it only requires a max-flow computation. These properties make this model useful not only for monetary transactions, but also in any setting where there is a need to model trust between nodes in a network. It has been shown to be particularly well-suited for transactions in exchange economies such as P2P networks where it can be used to improve inefficiencies resulting from asynchronous demand and bilateral trading. It has been used as a way of imposing group budget constraint on bidders in a multi-unit auction. It can also be used in settings such as packet routing in mobile ad-hoc networks and combating spam in viral marketing over social networks. It has applications in military scenarios where it is important to know who to trust. However, in order for the model to be of practical use it should be able to support repeated transactions between nodes over a long period of time. This motivates the following question which we formulate and study in this paper: if the network is sufficiently well-connected and has sufficient credit to begin with, can we sustain transactions in perpetuity without additional injection of credit? How does liquidity depend upon network topology and transaction rates between nodes, and how does it compare with a centralized currency infrastructure with a common currency? We study these questions under a simple model of repeated transactions: at each time step we pick a pair of nodes (s, t) in the network with probability λst and try to route a unit payment along the shortest feasible path from s to t. If such a path exists, we route the flow and modify edge capacities along the path. The transaction fails if there is no path from s to t. We show that the success probability of transactions is independent of the path used to route flow between nodes. For symmetric transaction rates, we show analytically and via simulations that the success probability for complete graphs, Erdös-Rényi graphs and preferential attachment graphs goes to one as the size, the density or the credit capacity of the network increases. Further, we characterize a centralized currency system as a special type of a star network (one where edges to the root have infinite credit capacity, and transactions occur only between leaf nodes) and compute its steady-state success probability. We show how to construct a centralized system that is equivalent to a given credit network and that the steady-state failure probability in complete graphs and Erdös-Rényi networks is at most a constant-factor worse than equivalent centralized currency systems. So in return for all the benefits resulting from the decentralized nature of the system, we do not give up a lot of liquidity compared to a centralized model with a common currency.

Collusion-resilient Credit-based Reputations for Peer-to-Peer Content Distribution
Back to Program
With growing demand for high-quality multimedia content, content providers face enormous pressure to scale the serving capacity. Peer-to-peer content distribution is a natural low cost option to scale system capacity. In a P2P CDN model, content providers serve content using a small number of "official" seeder nodes and rely on participating users to act as individual seeders for others in the system. Although P2P CDNs have the potential to drastically reduce the required serving capacity of official seeders, they must address the challenge of incentivizing users to stay online in the P2P network and act as seeders. Unfortunately, the incentive mechanisms provided by BitTorrent [4] and its many variants [7, 13] are insufficient. BitTorrent only incentivizes peers that are actively downloading the same file to upload to each other. Once a user completes a download, he has no incentive to act as a seeder. In practice, most content distribution sites (e.g. YouTube, NetFlix VoD) consist of a large number of files that attract many users but not enough of them to ensure multiple simultaneous downloaders at all times. An ideal incentive mechanism should require users to contribute to the P2P CDN even after completing their downloads. This is also referred to as the seeder promotion problem [16]). The importance of seeder promotion can be witnessed in private BitTorrent communities. These private communities enforce sharing ratios among its members. For example, in TorrentLeech, each peer must serve as a seeder for 24 hours and its uploaded amount needs to be at least 0.4 times of its downloaded amount. These rules incentivize peers to become seeders. As a result, the download speeds and the availability of content in private BitTorrent communities are significantly higher. A recent measurement study [10] shows that private communities achieve 3-5x the median download speed of public communities and possess 10-50x more seeders than those in public communities. However, private BitTorrent communities require trustworthy participants: they rely on peers to self-report their upload/download volumes and can be easily manipulated by selfish nodes [11]. To motivate selfish peers to become seeders, a P2P CDN needs to have the desirable property that the more a peer contributes (in terms of its uploads) to the system, the better the service (in terms of download speed) it gets. In this paper, we propose Credo, a credit-based reputation system that achieves this property and is robust to various attacks. In Credo, peers issue credit tokens to uploaders when downloading data from them and collect credit tokens by uploading to others. Each credit token is explicitly associated with the identity of the original credit issuer. Nodes can either transfer credits received from other peers or issue new original credit tokens. Unlike currency systems [12, 16, 21] which suffer from the bankruptcy problem, Credo allows each node to mint its own credits, thus ensuring no honest node ever goes bankrupt. Credo uses the credits to compute a reputation score which dictates how a peer allocates its upload bandwidth to downloaders. The naive way of counting the number of credits as a node's reputation score is susceptible to the collusion attack where a set of colluders swap credits among themselves without doing actual uploads. Credo employs two techniques to defend against such an attack. First, a node's reputation is computed by its credit diversity which measures the number of distinct credit issuers among a node's collected credits. Doing so can effectively limit the reputation score of k colluders to at most k. Second, Credo explicitly models the distribution of the amount of self-issued credits by all nodes and filters a node's collection of credits according to the measured distribution. This prevents colluders from launching sustained attacks by introducing Sybil identities that generate arbitrary number of credits. Using the credit diversity and distribution modeling mechanism, Credo can effectively handle collusion attacks. We believe that Credo is an attack-resilient P2P CDN system that addresses many of the limitations of existing currency and reputation based P2P CDN solutions and also provides a better incentive model to address the seeder promotion problem.

Content Pricing in Peer-to-Peer Networks
Back to Program
We provide a game theoretic model of content production and sharing in a peer-to-peer (P2P) network. We characterize two benchmark outcomes: Nash equilibrium (NE) without any incentive scheme and social optimum. We show that the P2P network is not utilized at an NE outcome, whereas social optimum in general requires the utilization of the P2P network. In order to obtain a socially optimal (SO) outcome among self-interested peers, we introduce a pricing scheme where downloading peers compensate uploading peers for content provision. For any SO outcome, we can find a pricing scheme with link-dependent linear prices that achieves the SO outcome as an NE. We illustrate our results with several examples. Our illustration shows that the structures of social optimum and optimal prices vary depending on the characteristics of peers such as cost parameters and connectivity.

A Network Formation Model for Internet Transit Relations
Back to Program
Most Autonomous Systems in the Internet need to select one or more transit providers. The provider selection process is complex, influenced by dynamic pricing, contracts, performance, marketing and other factors. We propose a simple dynamic model that captures the salient features of the provider selection process. The model creates a positive feedback effect, where "the bigger a provider is the bigger it gets". We then study the resulting internetwork formation process, showing that it always leads to a stable, but not unique, internetwork. We also use computational experiments to understand how the convergence delay scales with the size of the network, the factor(s) that affect the number of distinct equilibria, and the impact of three key model parameters.

A Decision-Analytic Approach for P2P Cooperation Policy Setting
Back to Program
While overall performance of peer-to-peer systems depends strongly on the amount of resource contributions made by individual peers, autonomous and rational peers make decisions on their cooperation policies (resource contributions) according to their individual utilities. To deal with the inherent conflict among individual utilities of the rational peers to improve overall performance of the system, we propose a decision-analytic approach that determines the appropriate cooperation policies of the individual peers in a distributed manner and coordinates their rational decisions in compliance with the social welfare improvement.

Innovations and Upgrades in Virtualized Network Architectures
Back to Program
The difficulty of making changes to the internet architecture has spawned widespread interest in virtualized testbeds as a place to deploy new services. Despite the excitement, uncertainty surrounds the question of how technologies can bridge the gap from testbed to global availability. It is recognized that no amount of validation will spur today's ISPs to make architectural changes, so the testbed itself must somehow provide global availability. We investigate whether a virtualized architecture that is widely offered by commercial ISPs would support the adoption of new services or upgrades to the infrastructure, and whether ISPs would ever support such an architecture. According to our economic analysis, the answer depends critically on how money flows to network and service providers. If the virtualized network inherits the market structure prevalent on the internet today, which we call network-gatekeeper, investment levels are likely to be poor. On the other hand, we identify two superior market types, mix-and-match and service-gatekeeper, which can improve incentives to invest in services, and even in network upgrades. We discuss how these market types may be implemented.

Trade & Cap: A Customer-Managed, Market-Based System for Trading Bandwidth Allowances at a Shared Link
Back to Program
We propose Trade & Cap (T&C), an economics-inspired mechanism that incentivizes users to voluntarily coordinate their consumption of the bandwidth of a shared network link so as to converge on what they perceive to be an equitable allocation, while ensuring efficient resource utilization. Under T&C, rather than acting as an arbiter, a service provider acts as an enforcer of what the community of rational users sharing the resource decides is a fair allocation of that resource. Our T&C mechanism proceeds in two phases. In the first, software agents acting on behalf of users engage in a strategic trading game in which each agent selfishly chooses reserved bandwidth slots to acquire in support of primary network usage activities. In the second phase, these agents acquire additional bandwidth slots in support of a presumed open-ended need for fluid bandwidth, catering to secondary applications. The acquisition of this fluid bandwidth is subject to the remaining "buying power" of each user and by prevalent "market prices"—both of which are determined by the outcomes of the trading phase, and by a desirable aggregate cap on link utilization. We present analytical results that establish the underpinnings of our T&C mechanism, including game-theoretic results pertaining to the trading phase, and pricing of fluid bandwidth allocation pertaining to the capping phase. Using Internet traffic traces, our experimental results demonstrate the benefits of our scheme, which we also show to be practical by highlighting the salient features of an efficient implementation architecture.

Tiered Incentives for Integrity Based Queuing
Back to Program
We propose an tiered incentive system called Integrity-Based Queuing (IBQ) for protection against Internet Distributed Denial-of-Service (DDoS) attacks. Our proposal can be implemented step-by-step where each integrity improvement brings a direct benefit to the autonomous system making it. IBQ proposes preferential queuing based on integrity: good, bad and middle. Since implementation can rarely be complete or network-wide we provide incremental benefit by prioritizing service for domains with better integrity. We have provided a basic analysis to relate performance to measurable integrity of the client. We have designed the architecture for authentication, queuing and defense. We have tested IBQ for applications with real-time requirements and show how performance improves with higher assurance.

Subscription Dynamics and Competition in Communications Markets
Back to Program
Multiple technologies, possibly administered by different entities, are expected to coexist in the rapidly-expanding communications market. In order to understand the complex interactions between different technologies, it is of fundamental importance to understand how technologies affect the demand of users and competition between network service providers (NSPs). To this end, we analyze user subscription dynamics and competition between NSPs in a duopoly communications market. First, we investigate the impact of technologies on the users' dynamic subscription and show that, for any charged prices, the equilibrium point of the considered user subscription dynamics exists and is unique. Next, we derive a sufficient condition on the technologies of the NSPs that ensures the user subscription dynamics to reach the equilibrium point. Then, we model the NSP competition using a non-cooperative game, in which the two NSPs choose their market shares independently, and provide a sufficient condition that guarantees the existence of at least one pure Nash equilibrium in the market competition game.

Mathematical Modeling of Competition in Sponsored Search Market
Back to Program
Sponsored search mechanisms have drawn much attention from both academic community and industry in recent years since the seminal papers of [3] and [4]. However, most of the existing literature concentrates on the mechanism design and analysis within the scope of only one search engine in the market. In this paper we propose a mathematical framework for modeling the interaction of publishers, advertisers and end users in a competitive market. We study the competition between two search engines as a three-stage dynamic game and prove the existence of Nash equilibrium prices when allowing advertisers to participate in both advertising systems simultaneously. To compare the expected revenues and social welfare under competition and monopoly, we carry out extensive simulation under common parameter setting of participants. Our results can provide useful insight in regulating the sponsored search market and protecting the interests of advertisers and end users.