SIGCOMM 2004 Wokshop Papers

Future Directions in Network Architecture

Practice and Theory of Incentives and Game Theory in Networked Systems

Network and System Support for Games

Network Troubleshooting: Research, Theory and Operations Practice Meet Malfunctioning Reality

The Case for Seperating Routing from Routers
Nick Feamster (MIT),  Hari Balakrishnan (MIT),  Jennifer Rexford (AT&T Labs--Research),  Aman Shaikh (AT&T Labs--Research),  Kobus van der Merwe (AT&T Labs--Research)
Abstract:
Over the past decade, the complexity of the Internet’s routing infrastructure has increased dramatically. This complexity and the problems it causes stem not just from various new demands made of the routing infrastructure, but also from fundamental limitations in the ability of today’s distributed infrastructure to scalably cope with new requirements.  The limitations in today’s routing system arise in large part from the fully distributed path-selection computation that the IP routers in an autonomous system (AS) must perform. To overcome this weakness, interdomain routing should be separated from today’s IP routers, which should simply forward packets (for the most part).  Instead, a separate Routing Control Platform (RCP) should select routes on behalf of the IP routers in each AS and exchange reachability information with other domains. Our position is that an approach like RCP is a good way of coping with complexity while being responsive to new demands and can lead to a routing system that is substantially easier to manage than today. We present a design overview of RCP based on three architectural principles—path computation based on a consistent view of network state, controlled interactions between routing protocol layers, and expressive specification of routing policies—and discuss the architectural strengths and weaknesses of our proposal. This paper is available in Adobe PDF format. TOP

Simplified Layering and Flexible Bandwidth with TWIN
Indra Widjaja (Bell Laboratories, Lucent Technologies), Iraj Saniee (Bell Laboratories, Lucent Technologies)
Abstract:
This paper describes a novel network architecture with simplifed layering, called Time-domain Wavelength Interleaved Networking (TWIN), that scales end-to-end bandwidth granularity flexibly up to the wavelength capacity. In TWIN, all packet and complex processing functions are pushed to the network edge such that the network core only has to deal with an optical forwarding layer. Furthermore, by avoiding fast optical switching and optical buffering in the core through scheduling fast-tunable lasers and buffering packets at the edge, TWIN effectively makes the network act like a switch. We examine distributed network scheduling for this architecture and show its performance via analysis and simulation. We also explore other research issues that are unique in TWIN. This paper is available in Adobe PDF format. TOP

Secure Routerless Routing
Vince Grolmusz (Eotvos University),  Zoltan Kiraly (Eotvos University)
Abstract:
Suppose that there are n Senders and r Receivers. Our goal is to design a communication network such that long messages can be sent from Sender i to Receiver π(i) such that no other receiver can retrieve the message intended for Receiver π(i). The task can easily be completed using some classical interconnection network and routers in the network. Alternatively, if every Receiver is directly connected to all n Senders, then the Senders can choose which channel to use for communication, without using any router. Fast optical networks are slowed down considerably if routers are inserted in their nodes. Moreover, handling queues or buffers at the routers is extremely hard in all-optical setting. An obvious routerless solution, connecting each possible Sender-Receiver pairs with direct channels seems to be infeasible in most cases. The main result of the present work is the mathematical model of two networks and corresponding networkprotocols in which the Senders and the Receivers are connected with only ro(1) channels (in practice no more than 32 channels in both networks); there are no switching or routing-elements in the network, just linear combinations of the signals are computed. Such designs would be usable in fast all-optical networks. In the proof of the security of the networks we do not use any unproven cryptographical or complexity theoretical assumptions: the security is information-theoretically proved, and does not depend on cryptographical primitives. This paper is available in Adobe PDF format. TOP

A Virtualized Link Layer with Support for Indirection
Richard Gold (Uppsala University),  Per Gunningberg (Uppsala University),  Christian Tschudin (University of Basel)
Abstract:
The current Internet today hosts several extensions for indirection like Mobile IP, NAT, proxies, route selection and various network overlays. At the same time, user-controlled indirection mechanisms foreseen in the Internet architecture (e.g., loose source routing) cannot be used to implement these extensions. This is a consequence of the Internet’s indirection semantics not being rich enough at some places and too rich at others. In order to achieve a more uniform handling of indirection we propose SelNet, a network architecture that is based on a virtualized link layer with explicit indirection support.  Indirection in this context refers to user-controlled steering of packet flows through the network. We discuss the architectural implications of such a scheme and report on implementation progress. This paper is available in Adobe PDF format. TOP

On Demand Label Switching for Spontaneous Networks
Vincent Untz (IMAG), Martin Heusse (IMAG), Franck Rousseau (IMAG), Andrzej Duda (IMAG)
Abstract:
We consider the problem of interconnecting hosts in spontaneous edge networks composed of various types of wired or wireless physical and link layer technologies. All or some hosts in a spontaneous network can be organized as a multihop ad hoc network, connected or not to the global Internet.  We argue that this kind of networks requires a more sophisticated approach than standard IP forwarding: communication paths should be managed on a per flow basis, multiple paths need to be maintained to cope with link failures or changing topologies, and the interconnection architecture should provide information on destination reachability.  We have designed and implemented Lilith, a prototype of an interconnection node for spontaneous edge networks.  We handle network dynamics by establishing MPLS (MultiProtocol Label Switching) label switched paths (LSP) on demand with a reactive ad hoc routing protocol. Interconnection at layer 2.5 makes all the hosts to appear as one single IP subnet so that configuration protocols can use the subnet broadcast for all forms of discovery (addresses, names, services).  Performance measurements of the Lilith implementation on Linux show good performance compared with standard IP forwarding and important performance gains when multiple paths are used. This paper is available in Adobe PDF format. TOP

NUTSS: A SIP-based Approach to UDP and TCP Network Connectivity
Saikat Guha (Cornell University),  Yutaka Takeda (Cornell University),  Paul Francis (Cornell University)
Abstract:
The communications establishment capability of the Session Initiation Protocol is being expanded by the IETF to include establishing network layer connectivity for UDP for a range of scenarios, including where hosts are behind NAT boxes, and host are running IPv6. So far, this work has been limited to UDP because of the assumed impossibility of establishing TCP connections through NAT, and because of the difficulty of predicting port assignments on certain common types of NATs. This paper reports on preliminary success in establishing TCP connections through NAT, and on port prediction. In so doing, we suggest that it may be appropriate for SIP to take a broader architectural role in P2P network layer connectivity for both IPv4 and IPv6. This paper is available in Adobe PDF format. TOP

Steps Towards a DoS-Resistant Internet Architecture
Mark Handley (UCL), Adam Greenhalgh (UCL)
Abstract:
Defending against DoS attacks is extremely difficult; effective solutions probably require significant changes to the Internet architecture.  We present a series of architectural changes aimed at preventing most flooding DoS attacks, and making the remaining attacks easier to defend against. The goal is to stimulate a debate on tradeoffs between the flexibility needed for future Internet evolution and the need to be robust to attack. This paper is available in Adobe PDF format. TOP

Loose Source Routing as a Mechanism for Traffic Policies
Katerina Argyraki (Stanford University),  David Cheriton (Stanford University)
Abstract:
Internet packet delivery policies have been of concern since the earliest times of the Internet, as witnessed by the presence of the Type of Service (ToS) eld in the IPv4 header. Efforts continue today with Differentiated Services (DiffServ) and Multiprotocol Label Switching (MPLS). We claim that these approaches have not succeeded because they re- quire, either explicitly or subtly, a network-layer virtual circuit mechanism.  In this paper, we describe how adding a form of Loose Source and Record Route (LSRR) capability into the next generation Internet provides adequate support for transmit and receive policies, including filtering, while avoiding the problems of virtual circuits and the original problems with LSRR in IPv4. This paper is available in Adobe PDF format. TOP

Invariants: A New Design Methodology for Network Architectures
Bengt Ahlgren (Swedish Institute of Computer Science), Marcus Brunner (NEC Network Laboratories),  Lars Eggert (NEC Network Laboratories), Robert Hancock (Siemens/Roke Manor Research), Stefan Schmid (NEC Network Laboratories)
Abstract:
The first age of Internet architectural thinking concentrated on defining the correct principles for designing a packet-switched network and its application protocol suites. Although these same principles remain valid today, they do not address the question of how to reason about the evolution of the Internet or its interworking with other networks of very different heritages. This paper proposes a complementary methodology, motivated by the view that evolution and interworking flexibility are determined not so much by the principles applied during initial design, but by the choice of fundamental components or “design invariants” in terms of which the design is expressed. The paper discusses the characteristics of such invariants, including examples from the Internet and other networks, and considers what attributes of invariants best support architectural flexibility. This paper is available in Adobe PDF format. TOP

Internet Congestion: A Laboratory Experiment
Daniel Friedman (UCSC), Bernardo Huberman (HP Labs)
Abstract:
Human players and automated players (bots) interact in real time in a congested network. A player’s revenue is proportional to the number of successful “downloads” and his cost is proportional to his total waiting time. Congestion arises because waiting time is an increasing random function of the number of uncompleted download attempts by all players. Surprisingly, some human players earn considerably higher profits than bots. Bots are better able to exploit periods of excess capacity, but they create endogenous trends in congestion that human players are better able to exploit. Nash equilibrium does a good job of predicting the impact of network capacity and noise amplitude. Overall efficiency is quite low, however, and players overdissipate potential rents, i.e., earn lower profits than in Nash equilibrium.. This paper is available in Adobe PDF format. TOP

Experiences Applying Game Theory to System Design
Ratul Mahajan (U. Wash.), Maya Rodrig (U. Wash.),  David Wetherall (U. Wash.), John Zahorjan (U. Wash.)
Abstract:
We applied techniques from game theory to help formulate and analyze solutions to two systems problems: discouraging selfishness in multi-hop wireless networks and enabling cooperation among ISPs in the Internet. It proved difficult to do so. This paper reports on our experiences and explains the issues that we encountered. It describes the ways in which the straightforward use of results from traditional game theory did not fit well with the requirements of our problems. It also identifies an important characteristic of the solutions we did eventually adopt that distinguishes them from those available using game theoretic approaches. We hope that this discussion will help to highlight formulations of game theory which are well-suited for problems involving computer systems. This paper is available in Adobe PDF format. TOP

Rethinking Incentives for Mobile Ad Hoc Networks
Elgan Huang (U. Cambridge), Jon Crowcroft (U. Cambridge), Ian Wassell (U.Cambridge)
Abstract:
Without sufficient nodes cooperating to provide relaying functions, a mobile ad hoc network cannot function properly.  Consequently various proposals have been made which provide incentives for individual users of an ad hoc mobile network to cooperate with each other. In this paper we examine this problem and analyse the drawbacks of currently proposed incentive systems. We then argue that there may not be a need for incentive systems at all, especially in the early stages of adoption, where excessive complexity can only hurt the deployment of ad hoc networks. We look at the needs of different customer segments at each stage of the technological adoption cycle and propose that incentive systems should not be used until ad hoc networks enter mainstream markets. Even then, incentive systems should be tailored to the needs of each individual application rather than adopting a generalised approach that may be flawed or too technically demanding to be implemented in reality. This paper is available in Adobe PDF format. TOP

On the Benefits and Feasibility of Incentive Based Routing Infrastructure
Mike Afergan (MIT), John Wroclawski (MIT)
Abstract:
Routing on the Internet today is as much about money as it is traffic. The business relationships of an ISP largely dictate its routing policy and drive the work of its engineers. In today's routing mechanism, this leads to a number of well-known pathologies. This structure is further challenged by the emergence of user-directed routing.  This paper explores these challenges and argues for the introduction of explicit incentives (prices) into the routing fabric of the Internet. We argue that doing so addresses limitations of the current system that are significant today and will only be exacerbated by user-directed routing. To support this claim, we describe the benefits and properties of incentive-based routing frameworks and demonstrate how such frameworks can be applied to a number of routing architectures, including BGP. This paper is available in Adobe PDF format. TOP

A Case for Taxation in Peer-to-Peer Streaming Broadcast
Yang-hua Chu (CMU), John Chuang (UC Berkeley), Hui Zhang (CMU)
Abstract:
Most existing research on peer-to-peer (p2p) has been on file sharing applications. In this paper, we focus on p2p streaming applications. In particular, we argue that the Bit-for-Bit model, widely adopted in p2p file sharing, is not applicable in p2p streaming. In p2p streaming, the bottleneck resource is the upstream bandwidth capacity. Our empirical experience with p2p streaming indicates that a large percent of peers on the Internet have limited upstream bandwidth capacity, and the Bit-for-Bit model severely limits the amount of bandwidth these resource-poor peers can receive. To address this issue, we propose a taxation model. In the taxation model, resource-rich peers contribute more bandwidth to the system, and subsidize for the resourcepoor peers. This redistribution of wealth improves social welfare. Such a model is applicable in the streaming context because the publisher of the video stream has the means to enforce taxation on peers and the will to maximize their collective social welfare. We design a simple linear taxation scheme and incorporate it in a distributed streaming protocol. Our simulation results indicate that taxation can significantly improve social welfare without incurring a significant overhead to the system. This paper is available in Adobe PDF format. TOP

Near Rationality and Competitive Equilibria in Networked Systems
Nicolas Christin (UC Berkeley), Jens Grossklags (UC Berkeley), John Chuang(UC Berkeley)
Abstract:
A growing body of literature in networked systems research relies on game theory and mechanism design to model and address the potential lack of cooperation between self-interested users. Most game-theoretic models applied to system research only describe competitive equilibria in terms of pure Nash equilibria, that is, a situation where the strategy of each user is deterministic, and is her best response to the strategies of all the other users. However, the assumptions necessary for a pure Nash equilibrium to hold may be too stringent for practical systems. Using three case studies on network formation, computer security, and TCP congestion control, we outline the limits of game-theoretic models relying on Nash equilibria, and we argue that considering competitive equilibria of a more general form helps in assessing the accuracy of a game theoretic model, and can even help in reconciling predictions from game-theoretic models with empirically observed behavior. This paper is available in Adobe PDF format. TOP

Faithfulness in Internet Algorithms
Jeff Shneidman (Harvard), David Parkes (Harvard), Laurent Massoulie (Microsoft Research)
Abstract:
Proving or disproving faithfulness (a property describing robustness to rational manipulation in action as well as information revelation) is an appealing goal when reasoning about distributed systems containing rational participants.  Recent work formalizes the notion of faithfulness and its foundation properties, and presents a general proof technique in the course of proving the ex post Nash faithfulness of a theoretical routing problem [11]. In this paper, we use a less formal approach and take some first steps in faithfulness analysis for existing algorithms running on the Internet. To this end, we consider the expected faithfulness of BitTorrent, a popular file download system, and show how manual backtracing (similar to the the ideas behind program slicing [22]) can be used to find rational manipulation problems. Although this primitive technique has serious drawbacks, it can be useful in disproving faithfulness. Building provably faithful Internet protocols and their corresponding specifications can be quite difficult depending on the system knowledge assumptions and problem complexity.  We present some of the open problems that are associated with these challenges. This paper is available in Adobe PDF format. TOP

Free-Riding and Whitewashing in Peer-to-Peer Systems
Michal Feldman (UC Berkeley), Christos Papadimitriou (UC Berkeley), Ion Stoica (UC Berkeley), John Chuang (UC Berkeley)
Abstract:
We develop a model to study the phenomenon of free-riding in peer-to-peer (P2P) systems. At the heart of our model is a user of a certain type, an intrinsic and private parameter that re ects the user's willingness to contribute resources to the system. A user decides whether to contribute or free-ride based on how the current contribution cost in the system compares to her type. When the societal generosity (i.e., the average type) is low, intervention is required in order to sustain the system. We present the effect of mechanisms that exclude low type users or, more realistic, penalize free-riders with degraded service. We also consider dynamic scenarios with arrivals and departures of users, and with white-washers: users who leave the system and rejoin with new identities to avoid reputational penalties. We find that when penalty is imposed on all newcomers in order to avoid whitewashing, system performance degrades significantly only when the turnover rate among users is high. This paper is available in Adobe PDF format. TOP

A Mobile Gaming Platform for the IMS
Amjad Akkawi, Sibylle Schaller, Oliver Wellnitz, Lars Wolf
Abstract:
Mobile devices offer the opportunity to play games nearly everywhere. Moreover, networked games allow individual players to interact with other people and to participate in a larger gaming world, which also provides for new business opportunities.  Hence, we currently see an increased interest from game developers, providers and players in mobile games. In this paper we propose a novel architecture and platform for games on the IMS. This allows games to utilize the features and capabilities that are inherent to the IMS. At the same time existing games can be flexibly adapted to this new type of network and have the possibility to reserve network resources for game data transmission, thus improving the experience of players. This paper is available in Adobe PDF format. TOP

Lightweight QoS-Support for Networked Mobile Gaming
Marcel Busse, Bernd Lamparter, Martin Mauve, Wolfgang Effelsberg
Abstract:
In this paper, we present an approach to provide Quality of Service (QoS) for networked mobile gaming. In order to examine the QoS requirements of mobile games, we ported a simple real-time game called GAV (GPL Arcade Volleyball) to a PDA and performed several traffic measurements over both GPRS and UMTS networks.  We show that due to high end-to-end delay and delay jitter, realtime games are not supported by GPRS. While UMTS improves both delay and jitter, it still does not match the requirements of real-time games. The key reason for this problem is that overprovisioning, as it is used to allow real-time games in the Internet, is very expensive in mobile networks. At the same time, QoS classes for mobile networks are not tailored to real-time games. In order to reduce delay and jitter for this application class, while still accounting for the very bursty nature of real-time game flows, we propose to use a combination of statistical multiplexing and QoS guarantees.  The general idea is to aggregate multiple game flows and perform reservation for that aggregate. As a theoretical background, we use a queuing system based model. Through simulation of a sample network with the traffic data generated by GAV, we validate our assumptions and demonstrate the performance and characteristics of our approach. This paper is available in Adobe PDF format. TOP

Feedback, Latency, Accuracy: Exploiting Tradeoffs in Location-Aware Gaming
Kieran Mansley, David Scott, Alastair Tse, Anil Madhavapeddy
Abstract:
We are witnessing the development of large-scale location systems and a corresponding rise in the popularity of location-aware applications, especially games. Traditional computer games have pushed the limits of CPU and graphics card performance for many years and experience suggests that location-aware games will place similar demands upon location systems. Unlike traditional gaming platforms however, the mobile devices that interact with location systems are heavily constrained especially in the number of ways that feedback can be provided. In this paper we describe a location-aware, fast-paced, close quarters action game and use it to experiment with three key components of future location-aware gaming platforms: (i) the location system, (ii) the network to connect the mobile devices, and (iii) the feedback and computational capabilities of the mobile devices themselves. We investigate the tradeoffs that are possible between these components, the effect of the feedback channel and the suitability of Bluetooth as a network for mobile game devices. This paper is available in Adobe PDF format. TOP

Using Session Initiation Protocol to Build Context-Aware VOIP Support for Multiplayer Networked Games
Aameek Singh, Arup Acharya
Abstract:
Multiplayer networked games are the trend of the day. Receiving a major boost from various commercial ventures like Microsoft Xbox  [19] and Sony Playstation  [13], the networked gaming industry is set to grow dramatically. These multiplayer games allow geographically dispersed and possibly distant players to participate in a single game. In order to provide interaction amongst players in such environments, text messaging and recently, real-time voice interaction through VoIP is used. However, such interactions are mostly out-of-band (not based on game contexts), user-initiated and limited in operability, failing to exploit the entire potential and functionality of VoIP.  In this paper, we present mechanisms and design of a prototype that allows game-context based VoIP communication between players. Thus, in addition to allowing players to talk to each other to coordinate teammates and activities (through a static team-based audio conference) as in some of the current systems, it supports communication among players based on shared contexts like the same physical location or room within the gaming environment. We use the Session Initiation Protocol (SIP) [14] to realize VoIP and describe mechanisms for building network gaming services using SIP. We also propose a sophisticated gaming scenario, in which VoIP is used to relay information about another player's distance and location with respect to the recipient, e.g. players farther away sound farther away. This paper is available in Adobe PDF format. TOP

Implementation of a Service Platform for Online Games
Anees Shaikh, Sambit Sahu, Marcel Rosu, Michael Shea, Debanjan Saha
Abstract:
Large-scale multiplayer online games require considerable investment in hosting infrastructures. However, the difficulty of predicting the success of a new title makes investing in dedicated server and network resources very risky. A shared infrastructure based on utility computing models to support multiple games offers an attractive option for game providers whose core competency is not in managing large server deployments. In this paper we describe a prototype implementation of a shared, on demand service platform for online games. The platform builds on open standards and off-the-shelf software developed to support utility computing offerings for Web-based business applications. We describe our early experience with identifying appropriate performance metrics for provisioning game servers and with implementing the platform components that we consider essential for its acceptance. This paper is available in Adobe PDF format. TOP

OpenPING: A Reflective Middleware for the Construction of Adaptive Networked Game Applications
Paul Okanda, Gordon Blair
Abstract:
The emergence of distributed Virtual Reality (VR) applications that run over the Internet has presented networked game application designers with new challenges. In an environment where the public internet streams multimedia data and is constantly under pressure to deliver over widely heterogeneous user-platforms, there has been a growing need that distributed VR applications be aware of and adapt to frequent variations in their context of execution. In this paper, we argue that in contrast to research efforts targeted at improvement of scalability, persistence and responsiveness capabilities, much less attempts have been aimed at addressing the flexibility, maintainability and extensibility requirements in contemporary distributed VR platforms. We propose the use of structural reflection as an approach that not only addresses these requirements but also offers added value in the form of providing a framework for scalability, persistence and responsiveness that is itself flexible, maintainable and extensible. We also present an adaptive middleware platform implementation called OpenPING1 that supports our proposal in addressing these requirements. This paper is available in Adobe PDF format. TOP

Zoned Federation of Game Servers: A Peer-to-Peer Approach to Scalable Multi-Player Online Games
Takuji Iimura, Hiroaki Hazeyama, Youki Kadobayashi
Abstract:
Today’s Multi-player Online Games (MOGs) are challenged by infrastructure requirements, because of their server-centric nature. Peer-to-peer networks are an interesting alternative, if they can implement the set of functions that are traditionally performed by centralized authoritative servers. In this paper, we propose a zoned federation model to adapt MOG to peer-to-peer networks. In this model, zoning layer is inserted between the game program and peer-to-peer networks. We introduce the concept of zone and zone owner to MOG. Zone is some part of the whole game world, and zone owner is an authoritative server of a specific zone. According to the demands of the game program, each node actively changes its role to zone owner and works in the same way as a centralized authoritative server. By dividing the whole game world into several zones, workloads of the centralized authoritative game server can be distributed to a federation of nodes. We have implemented the zoned federation model, and evaluate it with a prototypical multi-player game. Evaluation results indicate that our proposed approach is applicable to small and medium-sized MOGs, where the number of nodes is less than 500. This paper is available in Adobe PDF format. TOP

Realizing Bullet Time Effect in Multiplayer Games with Local Perception Filters
Jouni Smed, Henrik Niinisalo, Harri Hakonen
Abstract:
Local perception filters exploit the limitations of human perception to reduce the effects of network latency in multiplayer computer games. Because they allow temporal distortions in the rendered view, they can be modified to realize bullet time effect, where a player can get more reaction time by slowing down the surrounding game world. In this paper, we examine the concepts behind local perception filters and extend them to cover artificially increased delays. The presented methods are implemented in a testbench program, which is used to study the usability and limitations of the approach. This paper is available in Adobe PDF format. TOP

Scalable Peer-to-Peer Networked Virtual Environment
Shun-Yun Hu, Guan-Ming Liao
Abstract:
We propose a fully-distributed peer-to-peer architecture to solve the scalability problem of Networked Virtual Environment in a simple and efficient manner. Our method exploits locality of user interest inherent to such systems and is based on the mathematical construct Voronoi diagram. Scalable, responsive, fault-tolerant NVE can thus be constructed and deployed in an affordable way. This paper is available in Adobe PDF format. TOP