CoNEXT, Day 1

I am attending CoNEXT these days, and as usual I will maintain some notes on the talks I find more interesting.

ReArch'09

During the morning I decided to attend the ReArch workshop. Some interesting talks in the morning sessions, with Mark Handley and Van Jacobson figuring at the top of the list.

Keynote Presentation by Mark Handley (University College London)

A similar talk to the one Mark gave when he received the Royal Society-Wolfson Research Merit Award (as far as I can remember).

The Internet Control Architecture can be divided in three parts: routing, congestion control, and traffic engineering. These three things have been a bit disconnected because they were not planned together: they were an accumulation to fixes to specific problems (TCP with Jacobson addition for congestion control, BGP for routing, etc.). The control plane was made of incremental fixes, where the power of legacy had an important role.

It would be nice to have an architecture where all control protocols fit well.

Main question: is it possible to change the internet architecture in a planned way, so as to achieve long term goals?

By looking back to Internet control architecture, are there opportunities to change the game? In routing, it’s nearly impossible to replace BGP. It would have a huge network effect. For congestion control it is nearly impossible to replace TCP. But there is lots of stuff to do in-between these “layers”.

A wish list for control mechanisms: very high robustness (no downtime, robust to attack), load dependent routing (move traffic away from congestion), diverse traffic mix, and sane economics (reward net operators for investment).

Also, consider the problem of multi-homing. Multi-homing provides redundancy (more than one path provides robustness). However, routing is not a good way to access that redundancy. It would be good to access the redundancy at the transport layer, where congestion control can see it. With multi-homing (multipath) servers can do load balancing. Idea of pooling resources: several links working as if they were a single pool. Multipath TCP pools multiple link resources

Economics: what is the marginal cost of a packet? If no one else wanted to send at that time, no cost. It only makes sense to charge if our traffic displaces another user’s traffic. We should be charging for congestion.

Common models – rate based or volume based charging (x giga per month) don’t offer the right incentives. They are inefficient economically. Also, some apps are latency sensitive, some only care about long term throughput. Charging for congestion volume would thus make sense, encouraging machine to machine traffic to move to uncongested times.

ISPs can’t charge for congestion because they can’t see it properly. But end systems can – and some routers too. Bob Briscoe’s re-feedback and re-ECN ideas (congestion exposure): to indicate to an ISP the congestion seen by traffic downstream. Congestion exposure is thus an enabler for sane economics.

VoCCN: Voice Over Content-Centric Networks

Van Jacobson (Palo Alto Research Center (PARC), USA); Diana Smetters (PARC, USA); Nicholas H. Briggs (Palo Alto Research Center (PARC), USA); Michael Plass (Palo Alto Research Center (PARC), USA); Paul Stewart (Palo Alto Research Center (PARC), USA); James D. Thornton (PARC, USA); Rebecca L Braynard (PARC, USA)

Everybody knows that content based networking is great for content dissemination, but can’t handle conversational or real time traffic: everybody is half right... In fact, content networking is more general than IP, and does anything that IP can.

They implemented VoCCN, a VoIP functional equivalent based on CCN to prove this.

VoCCN: why bother? VoIP works badly for multipoint, multi-interface and mobility. VoIP wants to talk to an IP address, and in a voice call we want to talk to a person. Also, VoIP security is poor (only SSL between proxies).

With CCN, no need to map from a user to an address: we have very flexible names. And sender can encrypt its identity, with only the receiver able to decrypt it. No need for the user to reveal its identity. Supports secure VoIP.

They’ve built the voice app on top of CCN (instead of IP), and in the end the app performance was very similar to VoIP. They flipped frantically from one Ethernet connection to another, and the shift was almost imperceptible, and no packets were lost.

All this is available open source: www.ccnx.org. The VoCCN linphone code should be there by the end of the week.

Classifying Network Complexity

Michael H. Behringer (Cisco, France)

Network complexity is increasing: everybody knows that. But what is “network complexity”?

You need some complexity to achieve a certain level of robustness. How to deal with complexity? Divide and conquer (layering, o-o: “classes” matter, not instantiations), shifting complexity (e.g., away from the human – make simple user interfaces – look at the iPhone), meta-languages, structural approaches (reduce dependencies by design).

The “complexity cube” idea: a cube with three axes that represent the three areas of complexity: operator, physical network, network management.

Future work: quantitative metrics, impact of the rate of change, investigate human factors.

IP Version 10.0: A Strawman Design Beyond IPv6

Kenneth Carlberg (SAIC, USA); Saleem Bhatti (University of St Andrews, United Kingdom); Jon Crowcroft (University of Cambridge, United Kingdom)

Once upon a time: internet unknown by the general public, best effort was the only game in town, people used telnet. But now: need for security, and need for a Next Generation IP.

We were running out of address space. CIDR and NAT are near term solutions. Also, associated routing table size explosion. Solutions: new lookup algorithms to reduce impact, and faster hardware. But multi-homing has renewed the problem...

New Generation IP: 1) Simple IP (Steve’s IP) – minimise header, adding more extensibility (one or more Next Header), flow ID, larger flat address structure. 2) The P internet protocol (Paul’s IP) – change addressing to locater and identifier split, and hierarchical and variable length locator (implied source routing). Finally, 3), the grand compromise of 94: the simple IP-Plus. Simple IP with hierarchical addresses of Paul’s IP: IPv6.

Critique to IPv6: not much of an architectural change. 1) Large 128 bit address (retains locator & identifier, provider is still cling to NATs – they have no economic incentive to migrate). 2) Same size diff-serve field. 3) Multiple next headers (encapsulations or MPLS). 4) End to end flow labels (“market” uses islands to cut through routing (MPLS)). Note: recent report show IPv6 traffic is 1/100 of 1% of all IP traffic... Main questions: Does “more” qualify as architectural change? Where are the “must have” features?

Four significant discussions on “location/Identifier split”: 1) 1977 – tcp and mobility, 2) 1992-93: Paul’s IP work, 3) 1996 (O’Dell 8+8 proposal, 4) 2007 (IAB report). Three efforts now: HIP, LISP and ILNP.

Multi-homing problem: provider independent prefixes tend to be popular, but are non aggregatable.

IPv10 design: retain minimalism and extensibility of IPv6. Incorporate identifier/locator split. Besides headers, also introduce tails (change state insertion model: temporary headers and tails...). In the header include header navigation and forwarding info. In the trailer: trailer navigation , end to end info, diff-serv.

Impact of tails: change the end to end model of constructing headers (facilitate temporary insertion of overhead info). Avoid inefficient encapsulation. Forster the need to go beyond current ASIC header lookup limitation.

Should we be more radical in our design? Are there any must have features in IPv10?

ACM CoNEXT Student Workshop

During the afternoon we had the poster session, where I presented the poster “Relative Delay Estimator for Multipath Transport”. After that, a nice panel session to offer advice to PhD students, which included a discussion on what is best: to publish in conferences or journals? Contrary to most other fields, CS researchers tend to prefer conferences... However, there was some important points in favour of journals - namely the idea of creating a "scientific archive". Keshav, for instance, defended strongly journals, and invited everybody to publish their research in CCR... :) Also, TON wants to add bigger size papers and reduce the costs to add extra pages. We may see a move to papers in the meanwhile. A nice idea seems to be to publish in a top conference, and then to publish a longer version as a journal paper. Let's do it! :)

New internet TV announcements

An article in IT World mentions several announcements made recently that could make Internet TV a real possibility in the near future.

The first was You Tube, that anounced they will start offering full HD streams (1080p). So far, You Tube has an HD option with a resolution of only 720p. To understand the difference, check this wiki entry.

Next is Boxee. This company will launch a Boxee box that will enable web content to be delivered into your TV. Another possibility is to buy the new Dell Mini Desktop computer and connect it directly to the TV.

Now that you have Internet TV in your, well, TV, you need a nice programming guide. Look no further: Clicker has the solution.

Cable companies, be afraid. Internet TV is looming.

How broad is your band in the land?

akamai's view

http://www.akamai.com/dv5

doesn't appear to be consistent with cisco's:

http://news.bbc.co.uk/1/hi/technology/8282839.stm

(e-mail by Jon Crowcroft)

SIGCOMM Day 4

Session 6: Routing and Forwarding (Chair: Jia Wang, AT&T Research)

Stable and Flexible iBGP

Ashley Flavel (University of Adelaide), Matthew Roughan (University of Adelaide)

· Routing oscillation can decrease performance and lead to a high level of update churn.

· iBGP has also been shown to oscillate.

· More than eight years of research has not solved the problem of iBGP oscillation.

· Various solutions have been proposed but they all have problems: complicated to implement, restrict routing flexibility, or lack guarantees of stability.

· Their proposal is a very simple adaptation to the BGP decision process.

· They prove algebraically that it prevents iBGP oscillation.

LIPSIN: Line speed Publish/Subscribe Inter-Networking

Petri Jokela (Ericsson), Andras Zahemszky (Ericsson), Somaya Arianfar (Ericsson), Pekka Nikander (Ericsson), Christian Esteve (University of Campinas)

· Most Internet applications are internally publish/subscribe in nature

· Supporting efficient publish/subscribe requires 1) data-oriented naming, 2) efficient multicast, and 3) in-network caching.

· Deployment of native IP-based multicast has failed, and overlay- based multicast systems are inherently inefficient.

· Scalable and efficient publish/subscribe will require substantial architectural changes, such as moving from endpoint-oriented systems to information-centric architectures.

· Proposal: a novel multicast forwarding fabric, suitable for large-scale topic-based publish/subscribe. Fabric more energy efficient than the currently used ones.

PLUG: Flexible lookup modules for rapiddeployment of new protocols in high-speed routers

Lorenzo De Carli (University of Wisconsin-Madison), Yi Pan (University of Wisconsin-Madison), Amit Kumar (University of Wisconsin-Madison), Cristian Estan (University of Wisconsin-Madison), Karthikeyan Sankaralingam (University of Wisconsin-Madison)

· New protocols for the data link and network layer are being proposed to address limitations of current protocols (scalability, security, manageability).

· High-speed routers and switches that implement these protocols traditionally perform packet processing using ASICs. Why? High speed, low power, low chip area. But inflexible.

· Proposal: a flexible lookup module, PLUG (Pipelined Lookup Grid).

· They show that PLUG presents similar results to that of specialized lookup modules (in terms of throughput, area, power, and latency).

Session 7: Network Management (Chair: Thomas Karagiannis, Microsoft Research)

Modeling and Understanding End-to-End Class of Service Policies in Operational Networks

Yu-Wei Eric Sung (Purdue University), Carsten Lund (AT&T Labs Research), Mark Lyn (AT&T Labs), Sanjay Rao (Purdue University), Subhabrata Sen (AT&T Labs Research)

· Extensive use of service differentiation in Virtual Private Networks (VPNs) operated for business enterprises.

· The resulting Class of Service (CoS) designs embed complex policy decisions (bandwidth availability, cost).

· These complex high-level policies are realized through low-level router configurations (tedious process, error-prone ).

· They have proposed a formal approach to modeling CoS policies from router configuration files.

· They also present a practical and computationally efficient tool that can determine the CoS treatments received by an arbitrary set of flows across multiple routers

· They have validated their system using router configuration data from a cross-section of 150 diverse enterprise VPNs.

Towards Automated Performance Diagnosis in a Large IPTV Network

Ajay Mahimkar (The University of Texas at Austin), Zihui Ge (AT&T Labs - Research), Aman Shaikh (AT&T Labs - Research), Jia Wang (AT&T Labs - Research), Jennifer Yates (AT&T Labs - Research), Yin Zhang (The University of Texas at Austin), Qi Zhao (AT&T Labs - Research)

· IPTV is increasingly being deployed and offered as a commercial service.

· IPTV distribution network: hierarchical structure (instead of mesh), stringent requirements on reliability and performance, different distribution protocols (IP multicast), serious scalability challenges in managing millions of network elements.

· Characterisation and troubleshoot performance issues in one of the largest IPTV networks in North America.

· Measurement data used: device usage, error logs, user activity logs, video quality alarms, customer trouble tickets.

· They developed a novel diagnosis tool called Giza tailored to the enormous scale and hierarchical structure of the IPTV network.

· Multi-resolution data analysis to detect and localize regions experiencing problems.

· They make use of several statistical data mining techniques to troubleshoot the identified problems and diagnose their root causes.

Detailed Diagnosis in Enterprise Networks

Srikanth Kandula (Microsoft Research), Ratul Mahajan (Microsoft Research), Patrick Verkaik (UC San Diego), Sharad agarwal (Microsoft Research), Jitu Padhye (Microsoft Research), Paramvir Bahl (Microsoft Research)

· They analysed trouble tickets from small enterprise networks, and concluded that their operators need detailed fault diagnosis.

· They built a system (NetMedic) that enables detailed diagnosis by looking at info from operating systems and applications.

· Main idea: use the joint behaviour of two components in the past to estimate the likelihood of them impacting one another in the present.

· Prototype is effective at diagnosing faults that we inject in a live environment.

Session 8: Network Measurement (Chair: Gianluca Iannaccone, Intel Labs Berkeley)

Every Microsecond Counts: Tracking Fine-Grain Latencies with a Lossy Difference Aggregator

Ramana Rao Kompella (Purdue University), Kirill Levchenko (UC San Diego), Alex C. Snoeren (UC San Diego), George Varghese (UC San Diego)

· Network applications have stringent end-to-end latency requirements

· Fine-grain measurement demands cannot be met effectively by existing technologies, such as SNMP, NetFlow, or active probing.

· They propose a hash-based primitive LDA (Lossy Difference Aggregator) to measure latencies down to tens of microseconds and losses as infrequent as one in a million.

· They define a compact data structure that computes the average and standard deviation of latency and loss rate in a coordinated streaming environment.

· The system was compared with Poisson-spaced active probing with similar overheads. The LDA mechanism delivers orders of magnitude smaller relative error.

· Active probing requires 60 times as much bandwidth to deliver similar levels of accuracy.

Spatio-Temporal Compressive Sensing and Internet Traffic Matrices

Yin Zhang (University of Texas at Austin), Matthew Roughan (University of Adelaide), Walter Willinger (AT&T Labs -- Research), Lili Qiu (University of Texas at Austin)

· How to fill missing valies in a matrix (coulbe be a traffic matrix, delay matrix, social proximity matrix)

· They focus on traffic matrices.

· Missing values are quite common – direct measurement in infeasible, measurement unreliable, anomalies appear, and future traffic has not yet appeard

· Many network tasks are sensitive to missing values

· Ideas: 1) Exploit low rank nature of Traffic Matrices (TM); 2) exploit spatio-temporal properties (TM rows and columns close to each other are often close in value); 3) Exploit local strucytures in TMs

· Compressive sensing is used (generic technique for dealing with missing values that exploits the presence of structure and redundancy). However, existing compressive-sensing solutions perform poorly for traffic matrix interpolation.

· In the paper a novel spatio-temporal compressive sensing framework was developed. Key components: 1) a new technique called Sparsity Regularized Matrix Factorization (SRMF) that leverages the low-rank nature of traffic matrices and their spatio-temporal properties; 2) a mechanism for combining low-rank approximations with local interpolation procedures.

· They used real datasets from 3 networks.

· Compared to all other algorithms, this one is always better. Even with 98% missing values, the error is only of about 20%.

Passive Aggressive Measurement with MGRP

Pavlos Papageorgiou (University of Maryland, College Park), Justin McCann (University of Maryland, College Park), Michael Hicks (University of Maryland, College Park)

· Active proboing is very expensive – bandwidth expensive, and probes can interfere with the data

· With custom active measurement you shape the application data for measurement. This is efficient but not modular. And it is not reusable

· They propose MGRP – main intuition: MGRP piggybacks application data inside active probes.

· MGRP properties: 1) end to end measurement architecture (schedules probes for tx, and piggybacks application data on probes), 2) transparent to applications, 3) independent of measurement algorithms, 4) easy to adapt existing measurement tools, 5) can piggyback data across applications

· It enables aggressive probing with passive-like overhead.

· Piggybacking reduces bandwidth wasted by probes and enables measurement tools to be more aggressive faster and more accurate.

· Any measurement algorithm can now be written as if active, but implemented as passive.

Session 9: Performance Optimization (Chair: Ratul Mahajan, Microsoft Research)

ROAR: Increasing the Flexibility and Performance of Distributed Search

Costin Raiciu (UCL), Felipe Huici (UCL, NEC Labs), Mark Handley (UCL), David S. Rosenblum (UCL)

· We rely in distributed search everyday.

· Characteristics : big data set that doesn’t fit in one server. To reduce latency you use multiple servers, and put a bit of the data in each. But we also replicate the data. We create clusters of servers.

· PR = N (Number of Query Partitions * Replication = Number of Servers)

· P affects system behaviour. It dictates how much data each node stores, and it impacts latency.

· Partitioning determines latency and cost.

· Question: how to choose P, without knowing the workload? Choose the biggest value? Not desirable. CPU load increases...

· P is very difficult to change with existing solutions.

· How does google change P? In a way that requires over-provisioning, and lots of copies of the data (an estimate of 20TB/date center).

· The proposal: ROAR. Key observation: we do not need clusters to ensure each query meets all the data.

· ROAR uses consistent hashing. It uses a single parameter: P.

· ROAR copies zero data to increase P (while google’s algorithm has to copy a lot of data)

· Minimal data is copied when P decreases.

· They demonstrate the system using a privacy-preserving search application built upon ROAR.

· ROAR Changes P efficiently.

· The system scales. They tested this with 1000 servers in Amazon EC2.

Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication

Vijay Vasudevan (Carnegie Mellon University), Amar Phanishayee (Carnegie Mellon University), Hiral Shah (Carnegie Mellon University), Elie Krevat (Carnegie Mellon University), David Andersen (Carnegie Mellon University), Greg Ganger (Carnegie Mellon University), Garth Gibson (Carnegie Mellon University and Panasas, Inc), Brian Mueller (Panasas, Inc.)

· Timeout delay in TCP is big – 200 ms could be a big problem for datacenters.

· Some datacenter applications are very sensitive to these 200ms timeouts.

· Solution: enable microsecond retx (being safe in the wide area).

· Datacenter environment: 1-10Gbps, commodity Ethernet switches, and 10-100 microseconds latency.

· In a datacenter environment, 1 TCP timeout means more than 1000 RTTs...

· Long periods of idle links due to these high timeouts

· Other TCP variants did not prevent TCP timeouts.

· Timeouts also increase latency

· The solution: Microsecond TCP retransmissions

· 1^st solution: simple one line change in Linux (eliminate minRTO). It improves throughput, but still not microsecond RTO.

· Requirements for microsecond RTO: TCP must track RTT in microseconds (timestamp option). Efficient high resolution kernel timers (use HPET for efficient interrupt signalling).

· They were able to provide high throughput sustained for up to 47 servers.

· Is it safe? One has to look at the interaction with delayed ACK, and the performance in the wide area.

· Better performance with delayed ACK disabled.

· Is it safe for the wide area? Potential concerns: stability (could we cause congestion collapse?), and performance (do we oftenb timeeout unnecessarily?)

· Stability is preserved, because timeouts retain exponential backoff and spurious timeouts slow rate of transfer.

· Today’s TCP has mechanisms to detect spurious timeouts (using timestamp) and to recover from spurious timeour (forward RTO), and they are both implemented widely.

· They analysed wide area performance without minRTO, to see if it harms the wide area. They didn’t find any difference in throughput. Reason? Few total timeouts (supuious or legitimate).

Matchmaking for Online Games and Other Latency-Sensitive P2P Systems

Sharad Agarwal (Microsoft Research), Jacob R. Lorch (Microsoft Research)

· Latency is the main factor to be aware of in multiplayer online games.

· Predicting latency would help.

· They have an extensive matchmaking trace.

· Current approaches: geolocation, and network coordinate system. They mix both to get Htrae.

· Weakness of geolocation: inflexible. Weakness of network coordinate systems: sensitive to initial conditions (takes a while to converge).

· They have refined their original system that basically mixed geolocation for the initial condition and a network coordinate system to have flexibility. Refinements: 1) autonomous system correction (to change the height of the node); 2) symmetric updates to speed up convergence.

· Trace replays for evaluation: 30 days, 3.5 million machines, 50 million probes.

· Absolute error median for Htrae is 15ms.

· Htrae can find the best server 70% of the time.

· Deployed systems have to guess a lot, so Htrae is way better.

SIGCOMM Day 3

Session 3: Network Architecture (Chair: Renata Teixeira, LIP6)

De-anonymizing the Internet Using Unreliable IDs

Yinglian Xie (Microsoft Research Silicon Valley), Fang Yu (Microsoft Research Silicon Valley), Martín Abadi (Microsoft Research Silicon Valley and UCSC)

· The Internet is open and anonymous. Therefore, attackers that generate malicious traffic cannot typically be held accountable.

· HostTracker is presented. It tracks dynamic bindings between hosts and IP addresses by leveraging application-level data with unreliable IDs.

· They use a month-long user login trace from a large email provider

· HostTracker can attribute most of the activities reliably to the responsible hosts, despite the existence of dynamic IP addresses, proxies, and NATs.

SmartRE: An Architecture for Coordinated Network-wide Redundancy Elimination

Ashok Anand (University of Wisconsin-Madison), Vyas Sekar (Carnegie Mellon University), Aditya Akella (University of Wisconsin-Madison)

· Application-independent Redundancy Elimination (RE) (identifying and removing repeated content from network transfers), is used to improve network performance.

· A network-wide RE service would be beneficial for ISPs (to reduce link loads, increase effective network capacity)

· The authors present SmartRE, a architecture for network-wide RE.

· SmartRE enables more effective utilization of the available resources at network devices.

· They used real and synthetic traces to evaluate.

Design and Implementation of High Performance Dual-radio Mesh Networks

Aditya Dhananjay (New York University), Jinyang Li (New York University), Lakshminarayanan Subramanian (New York University), Hui Zhang (Tsinghua University)

· How to realise the full potential of a multi-radio mesh network? 1) how to assign channels to radios at each node to minimize interference; 2) how to choose high throughput routing paths in the face of lossy links, variable channel conditions and external load?

· ROMA is a distributed channel assignment and routing protocol that achieves good multi-hop path performance.

· They assign non-overlapping channels to links along each gateway path to eliminate intra-path interference.

· They reduce inter-path interference by assigning different channels to paths destined for different gateways whenever possible.

· They evaluated on a 24-node dual-radio testbed.

Session 4: Novel Aspects to Networking (Chair: Jon Crowcroft, Cambridge University)

Pathlet Routing

P. Brighten Godfrey (University of Illinois at Urbana-Champaign), Igor Ganichev (UC Berkeley), Scott Shenker (ICSI and UC Berkeley), Ion Stoica (UC Berkeley)

· Pathlet is a new routing protocol.

· Networks advertise fragments of paths (pathlets) that sources concatenate into end-to-end source routes.

· Pathlet routing can emulate the policies of BGP, source routing, and several recent multipath proposals.

· When a router's routing policy has only local constraints, it can be represented using a small number of pathlets, leading to very small forwarding tables

· Pathlet does not impose a global requirement on what style of policy is used, but rather allows multiple styles to coexist.

Cutting the Electric Bill for Internet-Scale Systems

Asfandyar Qureshi (MIT), Hari Balakrishnan (MIT), John Guttag (MIT), Bruce Maggs (Akamai/CMU), Rick Weber (Akamai)

· Energy expenses are becoming an increasingly important fraction of data center operating costs.

· Energy expense per unit of computation can vary significantly between two different locations.

· The paper characterizes the variation due to fluctuating electricity prices.

· Existing distributed systems should be able to exploit this variation for significant economic gains.

· Electricity prices exhibit both temporal and geographic variation.

· They use simulation to quantify the possible economic gains for a realistic workload.

· Existing systems may be able to save millions of dollars a year in electricity costs.

Persona: An Online Social Network with User-Defined Privacy

Randolph Baden University of Maryland Adam Bender (University of Maryland), Daniel Starin (University of Maryland), Neil Spring (University of Maryland), Bobby Bhattacharjee (University of Maryland)

· In OSNs users share private content, and trust the OSN service.

· Persona is an OSN where users dictate who may access their information.

· They hide user data with attribute-based encryption (ABE), allowing users to apply fine-grained policies over who may view their data

· They describe an implementation of Persona that replicates Facebook applications and show that Persona provides acceptable performance.

Session 5: Wireless Networking 2 (Chair: Suman Banerjee, University of Wisconsin at Madison)

In Defense of Wireless Carrier Sense

Micah Z. Brodsky (MIT), Robert T. Morris (MIT)

· The wireless medium is semi shared

· Carrier Sense: “Can I talk now?”. Interference protection and space reuse. Very simple.

· Is it too simple? If networks are far apart, concurrency is the best option. If they are close, time mux. What about in the middle?

· Main question: How well does CS work?

· When does CS works well? When interferer is very far away, or when it is very close to the sender. Intermediate distance is the hard case. What about shadows and obstacles?

· They start with a simple model, only 2 contending tx, with same power, omni antennas

· The effect of varying sender-sender distance is investigated.

· They use a standard model for radio propagation that include path loss and environmental shadowing. They ignore multipath fading because wideband channels average this away.

· They use Shannon capacity as a model for throughput (Adaptive bit rate)

· Answer for intermediate problem: Adaptive Bit Rate.

· Obstacles aren’t fatal. Usually you have alternate propagation paths.

· By analysing average throughput, they realise Carrier Sense works.

· Intuitions summary: Distant interferers affect receivers uniformly; nearby interferes don’t but they’re loud so everybody prefers mux anyway; rate adaptation helps in intermediate situation; and shadowing is not such a big problem.

· Implications for future research: adaptive bit rate is essential.; hidden terminals can be a problem in terms of reliability, but they don’t matter much for average performance; exposed terminals don’t cost very much, if ABR is working.

· Carrier sense does work. There is room for improvement, but not much in overall performance.

Interference Alignment and Cancellation

Shyamnath Gollakota (MIT), Samuel D. Perli (MIT), Dina Katabi (MIT)

· MIMO LANs increase throughput by sending more concurrent packets.

· In this paper the authors present a technique that doubles concurrent packets in MIMO LAN

· Concurrent MIMO decodes as many concurrent packets as there are antennas per AP. Can we do better?

· With 2 antennas, current MIMO LANs can decode only 2 packets. All current MIMO LANs are limited by number of antennas per AP.

· What if the APS coordinate over the Ethernet? 2 APs with 2 antennas each could communicate via Ethernet, and then decode more than 2 packets. But there is an impractical overhead in this solution. Can we leverage the Ethernet with minimal overhead?

· Their solution: Interference Alignment and Cancelation (IAC)

· IAC overcomes the antennas per AP throughput limit. A packet is decoded then broadcasted once on the Ethernet, with minimal overhead.

· Contributions of the work: first MIMO LAN to overcome the antennas per AP limit; IAM synthesises interference alignment and cancelation; IAM doubles MIMO throughput; implementation of the scheme in software radios to prove this.

· For a large number of antennas, IAC doubles MIMO throughput

· They tested with a 20 node testbed. Uplink gain: IACs median gain is 2.1x better than current MIMOs. Gain is partially due to diversity but even more to concurrency. Downlink: IAC median gain is 1.5x. IAC is beneficial across the operational range of SNRs.

DIRC: Increasing Indoor Wireless Capacity Using Directional Antennas

Xi Liu (Carnegie Mellon University), Anmol Sheth (Intel Research Seattle), Michael Kaminsky (Intel Research Pittsburgh), Konstantina Papagiannaki (Intel Research Pittsburgh), Srinivasan Seshan (Carnegie Mellon University), Peter Steenkiste (Carnegie Mellon University)

· Driving demand for wireless capacity. Interference can be a big issue.

· Goal: use directional antennas to improve wireless capacity by increasing spatial reuse.

· They use phased array antennas – they electronically steer the signal to a specific direction, hence having small reconfiguration time. They assume that only APs use these antennas – they are too bulky for clients.~

· Limitations in indoor environment: LOS may be blocked, indoor space is rich scattered. The conventional wisdom is that directional antennas are not effective in indoors environment.

· Key idea: leverage multiple paths and obstacles to improve spatial reuse

· How to find antenna orientations? 1) Naive solution, max cap, is too slow. The objective is to find optimal antenna orientations quickly.

· How to coordinate between antennas? They use a centralised controller, and TDMA scheduling MAC. They also separate directional and omni-directional antennas.

· They made measurements in 2 indoor environments: 3 directional APs and 6 omni clients in each testbed.

· 2x improvement over OMNI CSMA and 1.6x over MAX SNR.

· Conclusion: coordination is required to use directional antennas effectively in indoors environments

SIGCOMM Day 2

Keynote Speech

Great keynote speech by the winner of the SIGCOMM award (well deserved!): Jon Crowcroft. Here are the slides:

http://conferences.sigcomm.org/sigcomm/2009/pecha-kucha-dozen.pdf

Session 1: Wireless Networking 1 (Chair: Brad Karp, University College London)

Cross-Layer Wireless Bit Rate Adaptation

Mythili Vutukuru (MIT), Hari Balakrishnan (MIT), Kyle Jamieson (UCL)

· We have time varying wireless channels: due to large scale attenuation, small scale fading and interference

· So we need online bit rate adaptation: varying modulation and coding.

· Currently we have frame-based and SNR based algorithms for this.

· They have problems: slow, need look up tables, so they propose SoftRate. Use per-bit confidences, no need for look up tables – they get interference free BER.

· SoftPHY design more general than earlier work.

· Adapts to channel accurately and quickly, robust to collision losses, 2x gains over existing protocols.

· They propose using a soft output decoder (instead of the normal decoder) in the receiver, and use a different protocol, SoftRate.

· They created a GNU radio with USERP. Physical layer was from real traces, but then used ns-3 for TCP. They used a channel simulator for some scenarios (like train travelling).

· Good results predicting the BER of the channel.

· The comparison was made with other protocols: static best (best for each packet), SNR-based and Frame based.

· Compared to the optimum (static best): was within 10% of the optimal.

· Compared to the frame based: up to 2x over best frame based (these are very slow).

· Compared to SNR based: 4x over untrained SNT based algorithms

SMACK - A SMart ACKnowledgment Scheme for Broadcast Messages in Wireless Networks

Aveek Dutta (University of Colorado at Boulder), Dola Saha (University of Colorado at Boulder), Dirk Grunwald (University of Colorado at Boulder), Douglas Sicker (University of Colorado at Boulder)

· Question: Can we reduce the ACK time for broadcast/multicast scenarios?

· Instead of each user answering at its time, multiple users response at the same time to reduce the ACK time – using OFDM.

· The objective is to speed up group communication, like route discovery, neighbour info, etc.

· Nodes are assigned unique sub carriers. They send a tone to say “yes”.

· No packet transmission + concurrent response = faster ACK

· They have made an implementation of the system.

· In summary, main idea: PHY layer signalling can be used to innovate new protocols for wireless networks.

White Space Networking with Wi-Fi like Connectivity – Best paper award

Paramvir Bahl (Microsoft Research), Ranveer Chandra (Microsoft Research), Thomas Moscibroda (Microsoft Research), Rohan Murty (Harvard University), Matt Welsh (Harvard University)

· Main objective: How to build a wireless network using the white spaces?

· Spectrum allocation: there is more spectrum for broadcast TV than to WiFi.

· Moving from analog TV to digital TV.

· White spaces: unoccupied TV channels. Let's use them!

· We must not interfere with TV and mikes that are using that part of the spectrum: so we can use it iff no one else is using it.

· So we have more spectrum (3x that of 802.11g) and longer range (at least 3 to 4x WiFi)

· Goal: deploy infrastructure wireless – give good throughput without interfering with incumbents (TV and mike)

· Problems: fragmentation of spectrum (so we have variable channel widths), location impacts spectrum availability (spectrum exhibits spatial variation), and there is also temporal variation (incumbents appear/disappear over time).

· They’ve built the WhiteFi system – to evaluate by deployment of prototypes and by simulations.

· How do the new clients know which channels to use (discovery time)? They infer by analysing for how long the amplitude of a received signal is increased. They achieve a 2x reduction of discovery time for 30MHz width.

· Spectrum assignment algorithm: they implement MCHAM – a multi channel airtime metric. They consider not only if the channel has room, but also how much it has.

Session 2: Datacenter Network Design (Chair: Stefan Saroiu, Microsoft Research)

PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric

Radhika Niranjan Mysore (University of California San Diego), Andreas Pamboris (University of California San Diego), Nathan Farrington (University of California San Diego), Nelson Huang (University of California San Diego), Pardis Miri (University of California San Diego), Sivasankar Radhakrishnan (University of California San Diego), Vikram Subramanya (University of California San Diego), Amin Vahdat (University of California San Diego)

· Portland is a single logical layer 2 data centre network fabric. It separates host identity (IP) with host location (a “PMAC”).

· Data centres are growing in scale

· Goals for data centre network fabrics: plug and play, scalability, small switch state, seamless VM migration

· Layer 2 data centre fabrics. Advantages: plug and play, and seamless VM migration.

· Layer 3 data centre fabrics. Advantages: scalability, small switch state.

· With flat address you need about 100MB of chip memory (150 times what we put in a chip today).

· Other network fabrics: SEATTLE (SIGCOMM08) – problems: large switch table and broadcast based routing protocol. VL2 (SIGCOMM09).

· Portland: Plug and Play + Small Switch state.

· Main assumption: Hierarchical structure of data centre networks; they are multilevel, multi-routed tree.

· They impose a hierarchy on a multi-rooted tree.

VL2: A Scalable and Flexible Data Center Network

Albert Greenberg (Microsoft Research), Navendu Jain (Microsoft Research), Srikanth Kandula (Microsoft Research), Changhoon Kim (Princeton), Parantap Lahiri (Microsoft Research), David A. Maltz (Microsoft Research), Parveen Patel (Microsoft Research), Sudipta Sengupta (Microsoft Research)

· Cloud service data centre need to be agile (assign any servers to any services) and must scale out.

· VL2: First DC network that enables agility in a scaled out fashion.

· They analysed a large cluster, and realised that traffic patterns are highly volatile and unpredictable – so optimisation should be made frequently and rapidly

· We need a huge L2 switch, or an abstraction of one

· VL2 achieves agility at scale via 1) L2 semantics, 2) uniform high capacity between server, and 3) performance isolation between services

· Lessons: 1) randomisation can tame volatility, 2) add functionality where you have control, 3) there’s no need to wait.

BCube: A High Performance, Server-centric Network Architecture for Modular Data Centers

Chuanxiong Guo (Microsoft Research Asia), Guohan Lu (Microsoft Research Asia), Dan Li (Microsoft Research Asia), Haitao Wu (Microsoft Research Asia), Xuan Zhang (Tsinghua University), Yunfeng Shi (Peking University), Chen Tian (Huazhong Universtiy of Science and Technology), Yongguang Zhang (Microsoft Research Asia), Songwu Lu (UCLA)

· Novel network architecture for container based, modular data centres.

· BCube design goals: high network capacity for various traffic patterns (one to one unicast, one to all and one to several groupcast, and all to all data shuffling); only use low-end commodity switches, graceful performance degradation

· BCube is a server centric network.

· They compare their system with Tree, Fat-Tree, and DCell+, achieving higher performances.

SIGCOMM, Day 1

MobiHeld Session III: Services

Chair: Lakshminarayanan Subramanian (New York University)

Virtual Individual Servers as Privacy-Preserving Proxies for Mobile Devices

Ramón Cáceres (AT&T Labs), Landon Cox (Duke University), Harold Lim (Duke University), Amre Shakimov (Duke University), Alexander Varshavsky (AT&T Labs)

· Main goal: keeping ownership and control of your data

· Idea: each person has its own virtual machine

· People increasingly upload content from their mobile devices to 3^rd party services (facebook, twitter, etc.)

· This leads to privacy issues. They focus on 2 issues: 1) these services are centralised (vulnerable to large scale privacy breaches), 2) terms of service often grant provider rights to user data

· Virtual Individual Servers: instead of uploading our info to 3^rd party services, upload data to a VIS (a machine the user owns). Individuals maintain rights to their data. Data is distributed across many administrative domains.

· Advantages: privacy, flexibility (my own machine, I can install whatever I like), long term availability, cost scalability

· Disadvantages: management burden (users are bad to manage their machines at home, so managing a virtual machine will be complicated), cost to the individual

· VISs vs. serving data from devices – advantages: resource richness, high availability; disadvantages: requires access to wired infrastructure, need network connection

D^3N: Programming Distributed Computation in Pocket Switched Networks

Eiko Yoneki (University of Cambridge), Ioannis Baltopoulos (University of Cambridge), Jon Crowcroft (University of Cambridge)

· Evolution of mobile networks: a more disconnected network: a path from A to B may exist, but only over time.

· Looking at human to human connectivity

· Use of declarative networking

Apprehending Joule Thieves with Cinder

Stephen M. Rumble (Stanford University), Ryan Stutsman (Stanford University), Phil Levis (Stanford University), David Mazieres (Stanford University), Nickolai Zeldovich (MIT)

· Desktop resource management: if it’s slow, add more resources

· State of mobile devices: complex... and users care about energy and network

· Future of mobile devices: need new OS mechanisms for resource management

· Consider energy as a first class resource: track it, ration it, delegate it.

· They define a “capacitor abstraction” to explain the way they manage the mobile phone energy usage –kind of a leaky bucket concept.

· Capacitors can offer fine grained tracking, rationing and delegation. They easily express real world policies.

Game Action Based Power Management for Multiplayer Online Game

Bhojan Anand (National University of Singapore), A.L. Ananda (National University of Singapore), Mun Choon Chan (National University of Singapore), Rajesh Krishna Balan (Singapore Management University), Le Thanh Long (National University of Singapore)

· Main contribution: game action based resource management

· Black box approach: Lose some packets to save energy; White box approach: reduce number of packets, use some AI to remove redundancy – both baseline approaches failed.

· Application assisted approaches: go to off or deep sleep mode, without reducing quality

· Check Player Activity Level (PAL) – if it’s low, go to sleep mode.

· Can we predict current PAL with the previous PALs? Yep.

· How long can we put the WNIC to sleep? Must find optimum.

· They also looked at the frequency of game actions (shooting, walking, etc.)