A complex network can be modeled as a graph representing who knows relationship. In the context of graph theory for social networks, the notion of centrality is used to assess the relative importance of nodes in a given network topology. For example, in a network composed of large dense clusters connected through only a few links, the nodes involved in those links are particularly critical as far as the network survivability is concerned. This may also impact any application running on top of it. Such information can be exploited for various topological maintenance issues to prevent congestion and disruption. This can also be used offline to identify the most important nodes in large social interaction graphs. Several forms of centrality have been proposed so far. Yet, they suffer from imperfections: designed for abstract graphs, they are either of limited use (degree centrality), either uncomputable in a distributed setting (random walk betweenness centrality). In this talk we present a novel form of centrality: the second order centrality which can be computed in a fully decentralized manner. This provides locally each node with its relative criticality and relies on a random walk visiting the network. Both through theoretical analysis and simulation, we show that the second order centrality can be used to accurately identify critical nodes as well as to globally characterize graphs topology in a fully decentralized way. Finally, we compare the behavior of different centralities on a social network.

Bio:
Gilles Tredan is about to complete his PhD in the ASAP team at INRIA Rennes, under the supervision of Achour Mostefaoui. His research interests include distributed agreement problems, graph drawing, Open/Complex/Social networks modeling and processing, sensor networks, and Byzantine and malicious behaviours.

Large scale concepts, and in particular phase transitions, have always been factored in the analysis of natural systems, such as large ensembles of atoms and molecules. This is more recent in the context of man-made systems, such as wireless multi-hop networks. Like spin glasses in Physics, these networks are governed by phase transitions: a small change in one variable (which is here the channel access attempt rate) has a dramatic effect on the properties of the whole network (throughput and fairness). We explore the fundamental trade-off that exists between high spatial reuse (or throughput) and fairness, which is inherent to decentralized CSMA/CA MAC protocols such as IEEE 802.11. We show in particular that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. In large 1-dim. networks, nodes sufficiently far away from the border of the network have equal access to the channel, but not in 2-dim networks, where we observe a phase transition implying a strong unfairness of the protocol. This is a joint work with Mathilde Durvy and Olivier Dousse.

Bio:
Patrick Thiran is an associate professor at EPFL. He received the electrical engineering degree from the Universite Catholique de Louvain, Louvain-la-Neuve, Belgium, in 1989, the M.S. degree from the University of California at Berkeley, USA, in 1990, and the PhD degree from EPFL, Switzerland, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002 and an associate professor in 2006. From 2000 to 2001, he was with Sprint Advanced Technology Labs, Burlingame, CA, and in 2008 with Nokia Research, Helsinki. His research interests include communication networks and stochastic models. He is currently active in the analysis and design of wireless multi-hop networks and in network monitoring. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99, and he is currently an associate editor for the IEEE/ACM Transactions on Networking since 2006. He also served on the program committee of different conferences in networking, including Sigcomm, Sigmetrics, Mobihoc and Infocom. He was the recipient of the 1996 EPFL Ph.D. award, and of the 2008 Credit Suisse Teaching Award.

Social networks and collaborative tagging systems have taken off at an unexpected scale and speed (Facebook, YouTube, Flickr, Last.fm, Delicious, etc). Web content is now generated by you, me, our friends and millions of others. This represents a revolution in usage and a great opportunity to leverage collaborative knowledge to enhance the user's Internet experience. The Gossple project aims at precisely achieving this: automatically capturing affinities between users that are potentially unknown yet share similar interests, or exhibiting similar behaviors on the Web. This fully personalizes the search process, increasing the ability of a user to find relevant content. This personalization calls for decentralization. (1) Centralized servers might dissuade users from generating new content for they expose their privacy and represent a single point of attack. (2) The amount of information to store grows exponentially with the size of the system and centralized systems cannot sustain storing a growing amount of data at a user granularity. We believe that the salvation can only come from a fully decentralized user centric approach where every participant is entrusted to harvest the Web with information relevant to her own activity. This poses a number of scientific challenges: How to discover similar users, how to define the relevant metrics for such personalization, how to preserve privacy when needed, and how to manage efficiently a growing amount of data.

Bio:
Anne-Marie Kermarrec is a senior researcher at INRIA, Rennes. She leads the ASAP (As Scalable As Possible) research team and is the Principal Investigator of the ERC Starting Grant GOSSPLE. Before that she was with Microsoft Research, Cambridge (UK) from 2000 to 2004. Her research interests are in distributed systems, peer to peer computing, gossip protocols, social networks, collaborative systems.

Major chip manufacturers have recently shifted their focus from speeding individual processors to multiplying them on the same chip and shipping multicore architectures. Boosting the performance of programs will thus necessarily go through parallelizing them. This is not trivial and the average programmer will badly need abstractions for synchronizing concurrent accesses to shared memory objects. The transaction abstraction looks promising for this purpose and there is a lot of interest around its use in modern parallel programming. A lot of work has been devoted to implementing transactional memories but very little to how to precisely evaluate their correctness and complexity. This talk will report on some of recent research being conducted in this direction.

Bio:
Rachid Guerraoui is full professor in computer science at EPFL: the Swiss Federal Institute of Technology in Lausanne He graduated from the university of Paris in 1989 and got a PhD from the university of Orsay in 1992. Since then, and besides EPFL, Rachid has also been affiliated with HP Labs in Palo Alto and more recently with MIT. He is mainly interested in distributed computing and has written more than 200 papers on the topic, ranging from distributed algorithms and systems to distributed programming languages.

We analyze human mobility by relying on the short-term mobility traces gathered from publicly available web-based repositories of GPS tracks. We show how the data collected voluntarily by individuals, equipped with GPS-enabled devices, can be used to infer accurate, large-scale footprint of collective urban mobility. This method, unlike others - for example, personal interviewing, is more scalable and less time consuming. It exploits the fact that the on-line masses are willing to share their experience with others. We present a set of heuristics used to filter out from the dataset the GPS tracks with contain positioning errors. We show that the mobility patterns, inferred from the remaining, credible, short-term mobility traces have macroscopic characteristics similar to the characteristics of mobility patterns retrieved from the long-term mobility traces, gathered in different urban environments. The results of our analysis lead to a proposal for creating city-specific mobility profiles. We discuss how such profiles could help improving location privacy.

Bio:
Michal Piorkowski is finishing his PhD under the direction of prof. Matthias Grossglauser in the Laboratory for Computer Communications and Applications at EPFL, Switzerland. He is exploring the field of mobile ad hoc networks, in particular his research focuses on exploiting mobility for communication. He is also interested in mobility modeling, data mining and in the design of context-aware applications.

Existing indoor WiFi networks in the 2.5 GHz and 5 GHz use too much transmit power, needed because the high carrier frequency limits signal penetration and connectivity. Instead, we propose a novel indoor wireless design paradigm, based on Low Frequency, using the newly freed white spaces previously used as analogue TV bands, and Low Power – 100 times less power than currently used. Preliminary experiments show that this maintains a similar level of connectivity and performance to existing networks. We also advocate full-duplex networking in a single band, which becomes possible in this setting (because we operate at low frequencies). Full-duplex potentially doubles the throughput of each link. It also repairs carrier sensing, making it possible to successfully eliminate hidden terminal problems, even when using current multi-user MAC protocols; but it also provides the opportunity to design new distributed MAC scheduling algorithms that increase the spatial reuse and solve most of the fairness problems associated with current algorithms. We use simulations to illustrate the performance gains achieved when our new approach is used and we obtain both a throughput increase over current systems, as well as a significant improvement in fairness.

Bio:
Bozidar Radunovic is a Researcher in the Systems and Networking group at Microsoft Research, Cambridge. His research interests are in architecture and performance evaluation of computer systems with particular interest in wireless communication, cross-layer design and application of advanced communication techniques in network system design.
Bozidar received his PhD in technical sciences from EPFL, Switzerland, in 2005, and his BSc at the School of Electrical Engineering, University of Belgrade, Serbia, in 1999. He was a PhD student at LCA, EPFL from 2000–2005. Then he did a one year post-doc at TREC, at ENS Paris, in 2006. He also did a 6 month internship in IBM Zurich Research Labs in winter 2004/05. In 2008 he has been awarded IEEE William R. Bennett Prize Paper Award in the Field of Communications Systems.

The Internet is a vast, complicated and quickly evolving infrastructure that continues to grow in importance to the world's socio-economic fabric. Our quest is to develop an empirical understanding of the behavioral and structural characteristics of the Internet, to pave the way for continued growth and diversification of the infrastructure. In the first part of this talk, we will describe our work on DNS traffic monitoring. We develop and apply a new context-aware clustering method that enables DNS analysis to be scaled to expose the desired level of detail of traffic types, and to expose their time varying characteristics. Our application of these methods to a large DNS trace from our campus highlights both the coarse and fine level of detail on unwanted network behavior and the capabilities of our approach to the general problem of traffic classification. In the second part of the talk, we will describe our work on Internet topology discovery from simple passive measurements of IP packet traffic. We describe algorithms that enable 1) traffic sources that share network paths to be clustered accurately without relying on IP address or autonomous system information, 2) topological structure to be inferred accurately with only a small number of active measurements, 3) missing connectivity information to be recovered, which is a serious challenge in the use of passive packet measurements. This new, passive measurement-based approach offers the promise of near real time topology recovery at cost of the potential loss of some accuracy in resultant maps.

Bio:
Paul Barford an associate professor in the computer science department at the University of Wisconsin-Madison where he has been since 2001. He received a BS in electrical engineering from the University of Illinois and a PhD in computer science from Boston University. He is the founder and director of the Wisconsin Advanced Internet Laboratory - a widely used network testbed sponsored by Cisco Systems and the NSF. His research is focused on developing new techniques for gathering information on the structure and dynamic behavior of the Internet. He is also focused on developing new methods for protecting networks and systems from malicious attacks, and is the founder of Nemean Networks, a network security start-up company. Prof. Barford has authored numerous publications in highly competitive journals and conferences. He has served on committees of many conferences including ACM SIGCOMM, SIGMETRICS ('10 TPC chair), IMC ('06 TPC chair), CCS and USENIX Security. He is a member of the ACM Internet Measurement Conference steering committee, an associate editor of IEEE/ACM Transactions on Networking, and a voting member of the Board of Directors of the National LambdaRail.

A "dirty little secret" of network measurements is that what we can measure is often not what we want to (or think we) measure. To illustrate, I will discuss some of the main problems and challenges associated with analyzing and modeling measurements collected for the purpose of inferring certain types of Internet-related connectivity structures (e.g., a network provider's physical infrastructure or router-level topology). In particular, I will demonstrate with some concrete examples the need to (i) understand the process by which Internet connectivity measurements are obtained, (ii) explore the sensitivity of inferred graph properties to known ambiguities in the data, and (iii) be more serious/ambitious when it comes to model validation. Ignoring any of these issues is bound to lead to specious models (e.g., preferential attachment-type network models) that quickly collapse when scrutinized by domain experts.

Bio:
Walter Willinger is a member of the Information and Software Systems Research Center at AT&T Labs Research in Florham Park, NJ. He is well-known for his work that led to the discovery of the self-similar ("fractal") nature of Internet traffic. More recently, he has focused on investigating the topological structure of the Internet and on developing a theoretical foundation for the study of large-scale communication networks such as the Internet. He is a Fellow of ACM, IEEE, AT&T, and SIAM and co-recipient of the 1996 IEEE W.R.G. Baker Prize Award and the 1994 W.R. Bennett Prize Paper Award from the IEEE Communications Society.

We study the complexity of non-cryptographic authenticated broadcast in radio networks in which a fraction of the nodes may be malicious. We present two authenticated broadcast protocols for multi-hop radio networks, neither of which relies on public-key cryptography. The first protocol, RobustRB, combines optimal running time with maximal number of tolerated faulty nodes. Specifically, RobustRB tolerates up to approximately ¼ of the devices in each neighborhood acting maliciously, which is optimal. The protocol is also asymptotically optimal in terms of running time.

In practice, however, the constants hidden in the asymptotic notation can be quite large. With this in mind, we introduce our second protocol, FastRB, which trades some fault tolerance for efficiency. We evaluate both RobustRB and FastRB using the WSNet simulator in the context of three different fault models: crash failures, jamming, and malicious attacks. Both protocols provide a good level of fault tolerance in all three cases, and the FastRB protocol achieves significantly better performance than the RobustRB protocol. Compared to a time-efficient simple epidemic protocol that does not tolerate any faults, the FastRB protocol is less than a factor of ten slower. We therefore believe that the additional overhead for providing fault tolerance in authenticated broadcast is quite reasonable, especially in applications that use authenticated broadcast only when necessary, such distributing an authenticated digest.

Bio:
Dan Alistarh is currently a PhD student in the Distributed Programming Laboratory at EPF Lausanne, under the guidance of Rachid Guerraoui. He received his B.Sc. in Computer Science and Mathematics from Jacobs University Bremen in 2007. His research interests include the complexity of agreement problems in failure-prone distributed systems and communication in wireless sensor networks.

Despite almost a decade of research on peer-to-peer systems, and much interest, potential and development of structured overlays, large scale deployment of such overlays out in the open has generally remained elusive. The first half of this talk will highlight some of the outstanding challenges for such large-scale deployment and recent results and mechanisms to address the same – including on decentralized bootstrapping, ring-less routing and securing structured overlays from various malicious and uncooperative behaviors.

The later half of the talk will delve into some ongoing initiatives (occasionally disjoint from each other) to realize social networking and collaborative applications in a decentralized setting, including using aforementioned structured overlay based infrastructure.

Bio:
Anwitaman Datta did his PhD at EPFL Lausanne before moving to NTU Singapore in 2006 where he is currently an assistant professor. He is interested in large-scale networked distributed information systems and social collaboration networks, self-organization and algorithmic issues of these systems and networks and their scalability, resilience, security and performance. He won the best paper award at ICDCS 2007, is one of the recipients of HP Labs Innovation Research Program award 2008 and serves as a program co-chair of P2P 2009.

NetHood (nethood.org) is a new cross-disciplinary project aiming to bring together researchers from social sciences, urban planning, computer science, and networking. The purpose of this collaboration is to design self-organizing online neighborhood communities that will promote face-to-face interactions and a healthy life style, and that will empower local communities with a customizable social communication tool, which will respect their privacy requirements and independence. In this presentation I motivate the need to create such hybrid communities, bridging the virtual with the physical space in the city, and identify some challenging research questions that the Nethood project wishes to address. I then discuss the trade-offs related to the requirement of self-organization at the application and network layers. I focus on the incentives required for users to participate, build trust and share different types of resources, the more distributed the system architecture becomes. I argue that social software can play a critical role for stimulating intrinsic instead of extrinsic human motivations, and contribute this way to both encouraging resource sharing and shaping a strong sense of community. Based on lessons learned from existing web-based online communities, I identify some important principles that should guide the design of social software for building successful self-organizing hybrid communities.

Bio:
Panayotis Antoniadis is a postdoctoral fellow at UMPC Paris Universitas (Paris 6). His main research contributions are in the economic modelling and incentive mechanisms for peer-to-peer systems (2002–2006) and in distributed scheduling algorithms for high-speed switches (2000).He is currently working on resource management mechanisms and federation policies for shared network facilities (IST project Onelab). He is also exploring the role of social software, wireless networks and peer-to-peer systems on the design of sustainable hybrid neighborhood communities and urban planning (project nethood). He received his B.Sc. and M.Sc. degree from the Computer Science Department of University of Crete in 1998 and 2000 respectively and his Ph.D. degree from the Department of Informatics of Athens University of Economics and Business in 2006.

Models of user traffic demand are fundamental inputs to the design and engineering of data networks. This talk addresses this requirement in the context of large-scale wireless infrastructures using real-measurement (i.e., empirical) data.

Our proposed models are validated over two different monitoring periods at various levels of spatial aggregation, from individual access points (APs) to the whole network. Based on these models, we generated synthetic traffic for various spatio-temporal granularities and compared them with the empirical data. The comparison clearly illustrates the trade-off between model scalability and accuracy in capturing local-scale traffic dynamics.

This talk will present the evaluation of these models using also systems-based benchmarks, such as the throughput, goodput, delay and jitter per flow in a hotspot AP. Specifically, the performance of the proposed models is very close to the one produced when the empirical traces are used. Moreover, the performance of popular models deviates substantially from the empirical data. These results were verified via both simulations and emulations and using tcp- and udp-based scenarios. The analysis will also highlight the impact of flow sizes, flow interarrivals, and application mixes on the wireless lan performance. Finally, a flexible framework that can be used to generate synthetic traces with different workload characteristics for various performance analysis studies will be presented.

Bio:
Maria Papadopouli (Ph.D. Columbia University, October 2002) is an assistant professor in the Department of Computer Science at University of Crete, a research associate in FORTH-ICS, and an adjunct professor in the University of North Carolina at Chapel Hill (UNC). From July 2002 until June 2006, she was a tenure-track assistant professor at UNC (on leave from July 2004 until June 2006). Her current research interests are in mobile peer-to-peer computing, wireless networks, network modelling and performance analysis, and pervasive computing. She has co-authored a monograph on Peer-to-Peer Computing for Mobile Networks: Information Discovery and Dissemination (Springer 2008). In 2004 and 2005, she was awarded with an IBM Faculty Award.

More information about her research activities can be found at http://www.ics.forth.gr/mobile/.

based on joint work with Ruben Cuevas Rumin (Univ. Carlos III de Madrid), Xiaoyuan Yang, Georgos Siganos, Pablo Rodriguez (Telefonica Research)

Localizing BitTorrent traffic within an ISP in order to avoid excessive and often times unnecessary transit costs has recently received a lot of attention. Most existing work has focused on exploring the design space between bilateral cooperation schemes that require ISPs and P2P applications to talk to each other, and unilateral (client- or ISP-only) solutions that do not require cooperation. The above proposals have been evaluated in a hand full of ISPs with encouraging initial results. In this work we delve into the details of locality and attempt to answer yet unanswered questions like “what are the boundaries of win-win outcomes for both ISPs and users from locality?”, “what does the tradeoff between ISPs and users look like?”, and “are some ISPs more in need of locality biasing than others?”. To answer the above questions we have conducted a large scale measurement study of BitTorrent demand demographics spanning 100K torrents with more than 3.5M clients at 9K ASes. We have also developed scalable, yet accurate methodologies for computing traffic matrices from the above huge input without sacrificing essential BitTorrent mechanisms like the unchoke algorithm and the operation of seeders. We have validated our answers from the above study using an instrumented BitTorrent client and several live torrents.

Bio:
Nikolaos Laoutaris is a research scientist at Telefonica Research, Barcelona. Prior to that he was a postdoc fellow at Harvard University and a Marie Curie postdoc fellow at Boston University. He holds a Ph.D. degree in Computer Science from the University of Athens, Greece (2004). His main research interests are on system, algorithmic, and performance evaluation aspects of computer networks and distributed systems with emphasis on content distribution, overlay networks, P2P, and multimedia communications.

Perfect is the enemy of good. Most backoff schemes wait until a single contending thread survives. But it is the “last mile” which is usually the most costly: backoff systems which wait on some fixed number k > 1 of threads perform better that those that require perfection, i.e., k = 1.

This paper asks what tasks are read-write solvable “k-concurrently”, i.e., tasks where progress can be guaranteed when contention goes below k + 1. In other words, how good is backoff to k > 1? While backoff to k = 1 is omnipotent what set of tasks can be solved with k > 1? We show that the set of tasks that are solvable k-concurrently is exactly the set of tasks that are solvable wait-free with the availability of k-set consensus. It is now up to the system designer to decide whether good is good enough.

Joint work with Rachid Guerraoui, EPFL

Bio:
Eli Gafni is a professor of CS at UCLA. He joined UCLA in 1982, the year he got his PhD in EECS from MIT. He got his Ms.C from University of Illinois at Urbana-Champaign in 1979, and his Bs.C from the Technion, Israel in 1972. He was at the right place at the right time with the emergence of the ARPAnet, and his PhD Thesis is still quoted in the networks community. Alas, his abstarction tendencies got the better of him, and since then through progression of abstractions he is now completely theoretical investigating the limits of Shared-Memory models.

Experimental facilites (or testbeds) are instrumental in the development and evaluation of new Internet technologies. Evaluations based on simulation and emulation do provide valuable, yet inexpensive insight into the performance of new networking technologies at large scales. However, simulators and emulators inherently make simplifying model assumptions. Thus convincing the networking industry and community to widely adopt and deploy new algorithms or mechanisms also requires comprehensive analysis in real-world settings.

The talk will provide an overview as well as a few example of our cOntrol and Management Framework (OMF), a suite of software components which provide control, measurement, and management tools & services to users and operators of networking testbeds to address this need. A key feature of OMF is that it facilitates describing software installations, experiment workloads and actions, and measurement collection in a single integrated experiment description (script). This experiment description can then also serves to document the experiment and can be shared with other researchers to allow repeating the experiment. We hope that this will aid the development of a culture of rigorous peer veri\ufb01cation of experimental results and increase the scienti\ufb01c rigour of our \ufb01eld.

Bio:
Dr. Ott leads the Networked Systems research group at NICTA's Sydney laboratory. NICTA is Australia's Information and Communications Technology (ICT) Centre of Excellence. Before coming to NICTA he co-founded Semandex, which is a pioneer provider of Con- tent-Based Networks, a new generation of Enterprise Information Integration and Knowl- edge Management systems and content routing products. Dr. Ott holding a Research Professor appointment at WINLAB, Rutgers University where he is responsible for the software architecture of the ORBIT testbed. He received his Ph.D. in electrical engineering from the University of Tokyo, Japan, and a Dipl.Ing. from the Technical University, Vienna, Austria.

Heterogeneous Wireless Networks (HWNs) simultaneously provide universal coverage and high-bandwidth access where available. We investigate into optimal admission control policies for HWNs, considering an integration of wireless mesh networks with an overlaying cellular infrastructure. A Partially-Observable Markov-Modulated Poisson Process (PO-MMPP) model is used to characterize the overflow traffic from the underlaying mesh to the overlay, which captures the burstiness of the overflow traffic under the imperfect observability of the mesh network states. By modeling the overlay network as a controlled PO-MMPP/M/C/ C queueing system and obtaining structured results on the admission decision, it is shown that the optimal control policies for this class of HWNs can be characterized as monotonic threshold curves. Subsequently, these results are used to design a computationally efficient Structured Coordinate Search Algorithm (SCSA) to determine suitable admission policies in terms of thresholds. We present two versions of SCSA, a base version that is highly efficient, and an extended version, SCSA-OPT, which is guaranteed to converge to the optimal policy. Numerical observations suggest that the proposed algorithms have low time-complexity and can significantly reduce the cost of dropped and blocked calls.

Bio:
Ben Liang received honors simultaneous B.Sc. (valedictorian) and M.Sc. degrees in electrical engineering from Polytechnic University in Brooklyn, New York, in 1997 and the Ph.D. degree in electrical engineering with computer science minor from Cornell University in Ithaca, New York, in 2001. In the 2001 academic year, he was a visiting lecturer and post-doctoral research associate at Cornell University. He joined the Department of Electrical and Computer Engineering at the University of Toronto in 2002, where he is now an Associate Professor. His current research interests are in mobile networking and multimedia systems. He is an editor for the IEEE Transactions on Wireless Communications and an associate editor for the Wiley Security and Communication Networks journal. He serves on the organizational and technical committees of a number of conferences each year. He is a senior member of IEEE and a member of ACM and Tau Beta Pi.

Next-generation network architectures provide new levels of performance and flexibility in router systems to support heterogeneous end-systems, novel communication abstractions, security, and manageability. In this talk, I present our design of a network service architecture that can provide data path "network services" that go beyond the simple store-and-forward capabilities of today's Internet. To make these network services accessible to end-systems, it is necessary to develop a novel control infrastructure as well as programmable routers that can adapt dynamically to changing workloads. In this context, I present my group's recent research on distributed routing protocols for network services. I also discuss our recent work on runtime systems for network processors that automatically map processing tasks to multi-core processing resources. I conclude the talk with a brief overview of current and emerging research challenges.

Bio:
Tilman Wolf is an associate professor in the Department of Electrical and Computer Engineering at the University of Massachusetts Amherst. He received a Diplom in informatics from the University of Stuttgart, Germany, in 1998. He also received a M.S. in computer science in 1998, a M.S. in computer engineering in 2000, and a D.Sc. in computer science in 2002, all from Washington University in St. Louis. He is engaged in research and teaching in the areas of computer networks, computer architecture, and embedded systems. His research interests include network processors, their application in next-generation Internet architectures, and embedded system security.

Coding can help achieve the min-cut capacity in wireless broadcasts. For example, in random linear coding, packets are encoded in batches and the throughput increases with larger batch sizes. Unfortunately, packets are decoded in batches and as a result, delay suffers with larger batch sizes. This is a critical concern in streaming media, especially with interactive services or other delay-sensitive applications. Between receivers with vastly different channel conditions, unfairness in terms of delay can be observed as well.
The average packet delay among receivers can be reduced if (i) an appropriate batch size and (ii) packet scheduling, are used. In particular, random linear coding is an upper bound in delay performance and other hybrid network coding method might achieve better delay gains. In this talk, analysis of the upper and lower delay bounds from queueing theory is presented, and a heuristic scheme for achieving minimal average packet delay is explained.

Bio:
Wai-Leong Yeow received his B.Eng (1st class hons.) and Ph.D degrees from the National University of Singapore (NUS), in 2003 and 2008, respectively. He is a research engineer at the Institute for Infocomm Research (I2R), Singapore, from 2007. Since 2009, he is a visiting research scientist at DoCoMo USA Labs. His research interests include coding and wireless networking, stochastic decision processes and reinforcement learning, and network virtualization.

Classical Queuing Theory (as well as modern Adversarial Queuing Theory) study the conditions under which a queuing system is stable, i.e., the queue sizes remain bounded. Ideally, a stable system can be designed so that buffer overflows virtually never occur, and hence the issue of buffer overflows was largely overlooked by these disciplines. However, in modern networks like the Internet, buffer overflows occur quite often (being intentionally caused by TCP).

The talk will focus on settings where buffer resources are limited, while traffic is arbitrary and requires some Quality-of-Service (QoS) guarantees. In these settings buffer overflows are the common case, rather than the exception. We will consider several such problems including buffer management for traffic consisting of both committed and excess traffic, and buffer management for traffic with inter-packet dependencies.

We will discuss these problems from a competitive point of view, and present algorithms for admission control and scheduling. Our results consist of both analytic guarantees in terms of the competitive ratio of algorithms for these problems, as well as simulation studies. Our models and solutions are especially applicable to audio and video streaming, which are gaining ever-increasing popularity recently.

Based on joint works with Alex Kesselman, Boaz Patt-Shamir, and Yuval Shavitt.

Bio:
Received the B.Sc. degree in Mathematics and Philosophy from the Hebrew University of Jerusalem, Israel, in 1999, and the M.Sc. and Ph.D. degrees in Computer Science from the Technion, Haifa, Israel, in 2002 and 2007, respectively. In 2007–08 he was a postdoctoral fellow at the School of Electrical Engineering, Tel Aviv University, Israel, and he is currently a postdoctoral fellow at the Department of computer Science, University of Toronto, Canada. His research interests include scheduling and routing problems in computer networks, online and approximation algorithms, network protocols, algorithmic game theory, and wireless networks.

Social networks are all the rage. Of course, people were in social networks before the advent of MySpace, Facebook, Bebo, Orkut etc. Real life social networks have been the object of many studies by social scientists, looking at anything from school ties and retirement, to judo clubs and wealth creation. Social science traditionally invovles "heavy lifting" in terms of gathering empirical data through observation, questionannaire and so forth. In recent work, we (and other researchers) have measured human mobility and co-location more directly. We realise that mining this data, alongside online-social networks where people "self-declare" their relationships and interests, and combining this with analysis of communication patterns, can yield rich results that

1. give us deeper understanding of human society

2. allow us to build better infrastructures for communication

3. may better match technology for online versus real social life.

This talk is about some of our work in this space.

Bio:
Jon Crowcroft is the Marconi Professor of Networked Systems in the Computer Laboratory, of the University of Cambridge. Prior to that he was professor of networked systems at UCL in the Computer Science Department.
more …

802.11 wireless mesh networks are currently deployed worldwide but suffer from severe performance degradations due to the poor synergy of the 802.11 CSMA MAC protocol with the higher layers. Several solutions have been proposed but they either involve significant modifications to the 802.11 MAC or to legacy protocols at higher layers.

In this talk we will present a framework for online optimization of real-world 802.11 wireless mesh networks using rate control at the network layer. The framework can be implemented with standard, widely available traffic shapers and is based on a light-weight model that characterizes the capacity region of an operational 802.11 wireless mesh network. Unlike existing 802.11 modeling approaches, the parameters of this model can be measured and estimated with minimal overhead during network operation, using standard probing mechanisms at the network layer.

Using analysis and extensive measurements over an 802.11 wireless mesh network testbed, we experimentally validate the assumptions on which the model is built, and explain the principles behind the choice and estimation of its parameters. The throughput, fairness and stability performance of the resulting rate control optimization framework are demonstrated operationally in the testbed for a wide range of topologies and traffic patterns.

Bio:
Theodoros Salonidis is a research staff member at Thomson Corporate Research, Paris. He has been a research staff member at Intel Research Cambridge, UK (2006) and a Post-doctoral Research Associate in the Department of Electrical and Computer Engineering at Rice University (2004–2006). He received the Diploma in Electronic and Computer Engineering from the Technical University of Crete, Greece in 1997 and the M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of Maryland, College Park in 1999 and 2004, respectively. During one year (1999–2000) he worked at the IBM T.J. Watson Research Center, New York. His current research interests include high performance protocol design, distributed resource allocation mechanisms and performance analysis and optimization of wireless networks.

Abstract: Security in wireless networks is a notorious problem, suffering from the following dilemma: On the one hand the wireless medium access puts the attacker into a much better position, on the other hand wireless devices most often have resource deficiencies (processing, memory, energy) which make strong attack countermeasures based on cryptographic solutions impossible. Though, there have been many approaches towards lightweight security for wireless networks, this dilemma always persists, at least for the low-cost sector, say, for example, sensor networks or RFIDs. So far the overwhelming majority of wireless security approaches followed a conventional security paradigm which abstracts the physical communication as a logical channel. We depart from this paradigm, and try to leverage from the physical characteristics of wireless communications as much as possible, thus bringing us again in equality of arms with the attacker. This we coined the security by wireless principle. In the talk, several incarnations of the security by wireless principle are presented. These are taken from WLAN as well as wireless sensor network scenarios and show for different security goals that security by wireless designs can lead to interesting security solutions.

Bio:
Jens Schmitt is professor for Computer Science at the TU Kaiserslautern. Since 2003 he has been the head of the Distributed Computer Systems Lab (disco). His research interests are broadly in performance and security aspects of networked and distributed systems. He received his PhD from TU Darmstadt in 2000.

Web 2.0 sites have made networked sharing of user generated content increasingly popular. Serving rich-media content with strict delivery constraints requires a distribution infrastructure. Traditional caching and distribution algorithms are optimised for globally popular content and will not be efficient for user generated content that often show a heavy-tailed popularity distribution. New algorithms are needed. This paper shows that information encoded in social network structure can be used to predict access patterns which may be partly driven by viral information dissemination, termed as a social cascade. Specifically, knowledge about the number and location of friends of previous users is used to generate hints that enable placing replicas closer to future accesses.

Bio:
Nishanth Sastry is a PhD student in Computer Science at The University of Cambridge. Prior to this, he was at IBM Research. He has a Masters degree from The University of Texas at Austin and a Bachelor's degree from Bangalore University, both in Computer Science. Nishanth is broadly interested in Computer Networks, and has worked on several topics including congestion control and metropolitan area Wi-Fi networks. He is currently working on novel applications of social networks to systems.

Overlay-based services are a popular approach for providing functionality like multicast, quality of service or security in the Internet without requiring infrastructure support. This talk presents an overview of the Spontaneous Virtual Networks (SpoVNet) architecture and its Underlay Abstraction layer that enables easy and flexible creation of such services. Also building on an overlay approach, the Underlay Abstraction provides generic functionality to cope with mobility, multi-homing, and heterogeneity. It manages node mobility by separating node identifiers from network locators and it provides persistent connections by transparently switching locators. Multi-homing is supported by choosing the most appropriate pair of network locators for each connection. In order to cope with network and protocol heterogeneity, it uses dedicated overlay nodes, e.g., for relaying between IPv4 and IPv6 hosts. Since the functionality provided by the Underlay Abstraction can be used by several overlay-based services in parallel, redundant functionality is removed from services and applications.

Bio:
Oliver Waldhorst received a Diplom-Informatiker degree (comparable to M.Sc. in computer science) in 2000 and a Ph.D. in computer science in 2005 from University of Dortmund, Germany. He is currently a post doctoral researcher at University of Karlsruhe, Germany, where he is head of a Young Investigator Group, a junior research group funded by the Concept for the Future of Karlsruhe Institute of Technology within the framework of the German Excellence Initiative. His research interest include peer-to-peer- and overlay-networks in next-generation communication systems, Grid applications in mobile and hybrid environments as well as modeling and analysis of spontaneous, self-organizing systems. For more information visit http://www.yin.kit.edu/en/junior-research-groups/dr.-oliver-waldhorst.

People use an increasing number of personal electronic devices such as notebook computers, PDAs, MP3 player, and mobile phones in their daily lives. Making sure that the data stored on these devices is available where needed and backed up regularly represents a time-consuming and error-prone burden on users. In this talk, I present PodBase, a system that automates storage management on personal devices. PodBase ensures the durability of data despite the loss or failure of a subset of devices; at the same time, PodBase aims to make sure that data is available on devices where it is useful. The system takes advantage of unused storage resources and pairwise connectivity between devices to propagate the system state and replicate files. PodBase must be able to operate under a wide range of conditions and without attention from expert users. Towards this goal, PodBase uses a linear programming solver to compute an optimal replication plan based on the current distribution of files, availability of storage, and the likelihood of future device connections. Whenever two devices connect, PodBase computes a new plan and executes its first step (which can be viewed as a move in a game between the system and its environment). Results from a small prototype deployment with real users show that, under a wide range of conditions, this approach allows PodBase to maximize the durability and availability of data stored on personal devices with minimal user attention.

Bio:
Ansley Post is a Ph.D. candidate at Rice University, currently completing his doctoral research at the Max Planck Institute for Software Systems. He received his bachelors degree in Computer Science from the Georgia Institute for Technology, and his Masters degree from Rice University. His research interest is broadly in decentralized systems; particularly in making them more autonomous and easier to manage.

Accurate estimates of the available bandwidth on a path through a network can lead to significant improvements in the performance of routing and congestion-control procedures, and aid overlay applications. Unfortunately, generating an accurate estimate involves saturating the path for a short period of time with a few high-rate packet trains. If this is done rarely, then the overhead is acceptable, but if many paths in a subnetwork are being monitored simultaneously, then due to shared links, the additional load can become unacceptable and the measurement process itself can significantly bias the estimates. In this talk, I will describe a distributed algorithm for simultaneously estimating the bandwidth of multiple paths through a network. The procedure exploits the fact that each packet train provides information not only about the path it traverses, but also about any path that shares a link with the monitored path. We form a graphical model to capture these relationships and propagate the measurement information using loopy belief propagation. In addition, we employ an active learning algorithm to decide which path to measure and at what rate to probe in order to maximize the information provided by the probe. Simulations and PlanetLab experiments indicate that this process can dramatically reduce the number of probes required to generate acceptably accurate available bandwidth estimates.

Bio:
Mark Coates received the B.E. degree (first class honours) in computer systems engineering from the University of Adelaide, Australia, in 1995, and a Ph.D. degree in information engineering from the University of Cambridge, U.K., in 1999. Currently, he is an Associate Professor at McGill University, Montreal, Canada. He was awarded the Texas Instruments Postdoctoral Fellowship in 1999 and was a research associate and lecturer at Rice University, Texas, from 1999-2001. His research interests include communication and sensor/actuator networks, statistical signal processing, causal analysis, and Bayesian and Monte Carlo inference.

Motivated by emerging cooperative P2P applications that go beyond file-sharing, we study new uplink allocation algorithms for substituting the rate-based choke/unchoke algorithm of BitTorrent which becomes inefficient in these cases. Our goal is to reduce further the download times. We do so by improving the uplink utilization when it is mostly challenged: in young torrents, and when there exist downlink and network bottlenecks. We develop a new family of uplink allocation algorithms which we call BitMax, to stress the fact that they allocate to each unchoked node the maximum rate it can sustain, instead of an 1/(k+1) equal share as done in the existing BitTorrent. BitMax computes in each interval the number of nodes to be unchoked, and the corresponding allocations, and thus does not need any empirically preset parameters like k. We demonstrate experimentally that BitMax can reduce significantly the download time in a typical reference scenario involving mostly ADSL nodes. We also consider scenarios involving network bottlenecks caused by filtering of P2P traffic at ISP peering points and show that BitMax retains its gains also in these cases. This is a joint work with Nikos Laoutaris and Damiano Carra.

Short Bio:
Pietro Michiardi received his M.S. in Communication Systems in 1999 from Institut Eurecom and his M.S. in Electrical Engineering from "Politecnico di Torino" in 2001. In September 2001 Pietro joined "Ecole Nationale Superieure des Telecommunications" (ENST, Paris) as a Ph.D. student working on security for mobile, wireless multi-hop networks. During his Ph.D. Pietro worked in the Network Security Team at Institut Eurecom focusing on topics ranging from game theoretic models of multi-hop networks to trust and reputation establishment schemes and identity-based cryptographic techniques. He obtained his Ph.D. in December 2004. Since January 2005, Pietro is an Assistant Professor in the Networking department, working on distributed systems and algorithms. His research interests are in Peer-to-Peer Systems, Distributed Applications for Wireless multi-hop networks, Game theory and Mechanism Design, and theory of Distributed and randomized algorithms.

Motivated by our 4-month measurement of a P2P VoD application (Joost), we infer several design issues with P2P streaming. We propose D-MORE, a dynamic mesh-based generic overlay infrastructure for P2P networking and illustrate its two example use cases among other potentials.

In this talk, we explore the key techniques with D-MORE, namely capacity classification, locality-awareness and incentive mechanisms for construction of the tiered infrastructure. We show D-MORE scales well with the increasing number of hosts, in terms of control overhead, link stress and data path length, for supporting media distribution services.

We propose further improvements to enhance the D-MORE performance, which brings up to 35% network resource savings and up to 200% control overhead reduction in our simulations.

This is joint work with Jun Lei.

Biography:
Xiaoming Fu received a PhD degree in Computer Science from Tsinghua University (Beijing, China) in 2000. He is currently Professor and Head of Computer Networks Group at the Institute of Computer Science at Georg-August-Universität Göttingen, where he has been since September 2002. Prior to that, he worked as member of scientific staff at the Telecommunications Networks Group, Technische Universität Berlin. His research interests include network architectures, protocols, and applications, in particular QoS, network resilience, wireless mesh and mobile networks, congestion control and P2P overlays. In these fields he has been involved in several EU projects, including ENABLE, Daidalos-II, VIDIOS and MING-T, as well as the ACM Workshop on Mobility in the Evolving Internet Architecture (MobiArch). He was a guest editor for the IEEE Network Magazine Special Issue on Implications and Control of Middleboxes in the Internet (Sept/Oct 2008), and currently serves as the secretary of the IEEE Communications Society's Technical Committee on Computer Communications (TCCC), and an editorial board member for the Computer Communications Journal (Elsevier).

Online social networking sites like MySpace, Facebook, and Flickr have become a popular way to share and disseminate content. Their massive popularity has led to viral marketing techniques that attempt to spread content, products, and political campaigns on these sites. However, there is little data publicly available on viral propagation in the real world and few studies have characterized how information spreads over current online social networks.

In this talk, I will present results from a study of information dissemination in the Flickr social network. Using the crawled data of the favorite markings of 11 million photos and the social network of 2.5 million users, I will address the following key questions: (a) how widely does information propagate in the social network? (b) how quickly does information propagate? and (c) what is the role of word-of-mouth exchanges between friends in the overall propagation of information in the network?

Contrary to popular expectations about viral marketing, we find that (a) even popular information does not spread widely throughout the network, (b) even popular photos spread very slowly through the network, and (c) information exchanged between friends is likely to account for over 50% of all favorite bookmarks, however, with a significant delay at each hop.

Biography: Meeyoung Cha is a post-doctoral researcher at Max Planck Institute for Software Systems (MPI-SWS) in Germany. She received a Ph.D. degree in Computer Science from KAIST in 2008. Meeyoung's research interests are in the design and analysis of large-scale networked systems. Her recent work has focused on multimedia streaming systems and online social networks. She won the best paper award at ACM Internet Measurement Conference 2007 for her work characterizing the YouTube workload. Her recent work includes an analysis of viewing behaviors of 250,000 users watching Internet television.

The Distributed Coordination Function (DCF) aims at fair and efficient medium access in Wireless LANs. In face of the success there is, however, little consensus on the actual degree of fairness that is achieved. Closely linked to short- and long-term fairness are per-flow service characteristics like channel access delays and average throughput.

In this talk, we report on a fairness study of the IEEE 802.11 DCF. We derive the probability distribution of fairness deviations and support our analytical results by measurements. We identify the significance of the random distribution used by the backoff procedure and we find a closed-form expression for the improvement of long-term over short-term fairness.

We view the DCF as emulating Generalized Processor Sharing (GPS) and quantify possible deviations from a fair rate allocation. We deduce a stochastic service curve model for the DCF to predict packet delays in IEEE 802.11. Finally, we show how a station can estimate its fair bandwidth share from passive measurements of its traffic arrivals and departures.

This talk presents joint work with Michael Bredel (TU Darmstadt).

Biography: Markus Fidler is currently the leader of an Emmy Noether research group funded by the German Research Foundation (DFG) at the Multimedia Communications Lab, TU Darmstadt. He received his Dipl.-Ing. in electrical engineering from RWTH Aachen University in 1997, Dipl.-Kfm. in business economics from Hagen University in 2001, and Dr.-Ing. from RWTH Aachen University in 2003.

Before he joined the department of computer science at Aachen University in 2001 he was a GSM/GPRS systems engineer with Hagenuk Telecom in 1997 and with Alcatel R&D from 1998 until 2000. During the years 2004 through 2006 he was a visiting researcher at the institute Mittag-Leffler in Stockholm, at NTNU Trondheim, and at the University of Toronto.

Social expectations play an important role in distributed systems that span multiple administrative domains. For example, participants in peer-to-peer systems are expected to contribute resources for the common good, and members of federated systems are expected to adhere to best practices and fulfill contractual obligations. However, these expectations are not always met – sometimes by mistake, sometimes to gain an advantage, and sometimes even due to a deliberate attack.

In society, accountability is widely used to counter such threats. Accountability incentivizes good performance, exposes failures and unwanted behavior, and builds trust between competing individuals and organizations. In this talk, I will argue that accountability is also a powerful tool in designing distributed systems. Accountability ensures that misbehavior can be detected and linked to a faulty node. Thus, it complements fault tolerance techniques and offers an alternative to these techniques in systems that provide best-effort service.

I will also present NetReview, a system that uses accountability to detect faults in the Internet's interdomain routing system. Despite many attempts to fix it, the routing system remains vulnerable to configuration errors, buggy software, flaky equipment, and intentional attacks. NetReview reliably detects such faults by recording BGP routing messages in a tamper-evident log, and by enabling ISPs to check each other's log against a high-level specification of the expected behavior, such as a peering agreement or a set of best practices. At the same time, NetReview respects the ISPs' privacy and allows them to protect sensitive information.