Seminars

Handling interference is one of the major challenges in the design of multi-user distributed wireless systems. In current systems, interference is managed through carrier sensing mechanisms such as CSMA/CA and through MAC algorithms based on random back-off. However, the asymmetry in channel sensing inevitably causes degraded throughput and fairness issues, such as those caused by hidden terminal problems. We propose ContraFlow, a solution based on self-interference cancellation and innovative scheduling mechanisms that increases spatial reuse, eliminates hidden terminals, and rectifies decentralized coordination inefficiencies among nodes, thereby improving fairness. Self-interference cancellation is a technique allowing a node to cancel its own transmitted signal and hence to successfully receive data while transmitting on the same channel. We demonstrate the feasibility of such techniques in a low power WPAN setting, using Lyrtech software-defined radios. Self-interference cancellation 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 ContraFlow is used and we obtain both a throughput increase over current systems, as well as a significant improvement in fairness.

In this talk, I will describe HomeMaestro, a distributed system for monitoring and instrumentation of home networks. By performing extensive measurements at the host level HomeMaestro infers application network requirements, and identifies network-related problems. By sharing and correlating information across hosts in the home network, HomeMaestro automatically detects and resolves contention over network resources among applications based on predefined policies. Finally, our system implements a distributed virtual queue to enforce those policies by prioritizing applications without additional assistance from network equipment such as routers or access points. In the talk, I will outline the challenges in managing home networks, describe the design choices and the architecture of our system, and highlight the performance og HomeMaestro components in typical home scenarios.

Packet schedulers with tight bandwidth and delay guarantees must keep up with rapidly increasing link speeds at the core of the Internet and within enterprise switched Ethernets.

There is a tradeoff between an algorithm's complexity and the strength of the service guarantees it provides. State-of-the-art solutions range from fast round-robin schedulers with O(N) guarantees, to O(log N) timestamp-based schedulers with optimal guarantees. While approximated timestamp-based schedulers exist that achieve near-optimal service guarantees in O(1) time, they do so only with significant constants hidden in the O() notation. For 10 Gbps links and beyond, even the magnitude of an algorithm's constants limits scalability.

We present QFQ, a truly practical WFQ scheduler with near-optimal guarantees *and* truly low complexity (250 x86 instructions per packet, irrespective of number of flows and configuration parameters). QFQ combines known techniques to group flows and round timestamps with a novel approach to manipulate multiple groups of flows at once, thus cutting the constant factors in the algorithm's complexity, and enhancing scalability.

I will discuss the problem of building fast, programmable routers. I will present RouteBricks, a high-end router architecture that consists entirely of commodity servers. RouteBricks achieves high performance by parallelizing router functionality both across multiple servers and across multiple cores within a single server; it is fully programmable using the familiar Click/Linux environment. I will also present RB4, our 4-server prototype that routes at 35Gbps; this routing capacity can be linearly scaled through the use of additional servers. I will close the talk with an example of what we can do with RouteBricks - I will briefly discuss a simple protocol for Internet-wide troubleshooting and neutrality monitoring.

This work will appear in SOSP 2009.

Katerina Argyraki got her PhD in Electrical Engineering from Stanford University in 2007 and is currently a research scientist at EPFL, Switzerland. For her PhD, she worked on the TRIAD project and developed AITF - a network-based solution to bandwidth flooding. Before joining EPFL, she worked for Arista Networks, helping build the control plane for high-end switches. Her research interests lie in the areas of network architecture and protocols with a focus on denial-of-service defenses and network troubleshooting.

Helios is an operating system designed to simplify the task of writing, deploying, and tuning applications for heterogeneous platforms (like your desktop PC). Helios introduces satellite kernels to provide a uniform set of OS abstractions across CPUs of disparate architectures and performance characteristics. This talk will cover the design of Helios and its performance in the context of a pair of heterogeneous systems.

This work will appear in SOSP 2009.

Orion Hodson is a Software Engineer in the Systems and Networking group at Microsoft Research Cambridge. At MSR, he has worked extensively on the Singularity Operating System and a heterogeneous multicore derivative known as Helios. Prior to Microsoft Research, he was a member of the eXtensible Open Router Project (XORP) team at ICIR at Berkeley working on an open-source IP router. He is a former member of the networked multimedia research group at UCL and was a contributor to the RAT multicast audio conferencing tool.