The EuroSys conference report blog

Session Chair: Bruce Maggs, Carnegie Mellon University/Akamai

NetReview: Detecting When Interdomain Routing Goes Wrong
Andreas Haeberlen, MPI-SWS and Rice University; Ioannis Avramopoulos, Deutsche Telekom Laboratories; Jennifer Rexford, Princeton University; Peter Druschel, MPI-SWS

————————-

There are problems with BGP:
- Wrong announcements
- Problems caused by implementation bugs
- Attacks

Fault Detection:
1) Reliably each routing problem
2) Link to the AS the causes it

A central log collector would not be a good solution because of
- Privacy of the logs
- Reliability of the logs

In NetReview:
- Border routers log BGP messages
- Prove it to a third party

What is a BGP fault?
- A fault happens when the “sent BGP” messages do not conform the “expected behavior”.
- Thus, a solution would be capturing “send BGP” messages and checking it against the “expected behavior”.
Concern: How easy is expressing the expected behaviors as some rules? What people have usually in mind about the expected behavior is just a vague idea and expressing as a formal rule would not be easy.

An AS does not need to reveal all its rules to all peers; each peer needs to know only the rules that will affect it.

For the first part, NetReview uses a “Tamper-evident” log.
- It is based on Hash Chain.
- Each log entry has a hash value that covers its value and also the hash value of its previous entry. Transitively, it covers the values of all other previous entries.
- Any modification to the log would be caught by observing the reflected change to the hash value.

Auditing and rule evaluation:
- Sort states by time
- Check the sequence of messages against the specified rules

Incremental deployment: A new AS would prefer to peer with reliable routers. This makes a good incentive for routers to dopey the framework.

Overhead:
- 1 pc is enough
- 356GB/year message overhead
- 420kbps BGP traffic

Q: What if two ASes decide to hide some information from the others?
A: If those information concerns the others, the other routers need to check it personally. If it does not concern them, it does not hurt them as well, then the hiding would be OK.

Making Routers Last Longer with ViAggre
Hitesh Ballani, Paul Francis, and Tuan Cao, Cornell University; Jia Wang, AT&T Labs—Research

————————-

Problem: rapid routing table growth
- 282,000 prefixes at Sep’08.

Virtual Aggregation (ViAggre):
- Key insight: divide the routing burden between routers

Routers:
- Control plane: Uses RIB, slow and cheap memory (DRAM)
- Data plane: Uses FIB, fast and expensive memory (SRAM)

Related works need architectural change.
- In this work, we focus only on FIB growth. However, we do not need architectural change.

Solution:
- Today: All routers have routes to all destinations
- ViAggre: Divide address space into virtual prefixes (VPs)
- Routers only have routes to a fraction of the address space
- Route-reflector Suppression: External router peers with a route-reflector
- Route-reflectors exchange routes with each other
- When the intermediate routers don’t have route to destination prefix, forward it to external router by tunnelling.

Concerns:
- What about Failure of aggregation point?
- ViAggre paths can be longer than native paths.
- The traffic load on routers would increase.

Traffic volume follows power-law distribution
- 95% of the traffic goes to 5% of prefixes
- We can install “Popular Prefixes” in routers

Q: IP tunneling used to happen in slow path?
A: It has changed now. It is on fast path.

Q: If the power-law in prefixes is true, why not simply forward the rest 5% of traffic to the upper layer router?
A: I believe the complexity of ViAggre would be less.

Q: Can you apply the same solution to data-centers?
A: They work on layer 2, but there are already related works on that.

Session Chair: Dina Katabi, Massachusetts Institute of Technology

Softspeak: Making VoIP Play Well in Existing 802.11 Deployments

Patrick Verkaik, Yuvraj Agarwal, Rajesh Gupta, and Alex C. Snoeren, University of California, San Diego

——————-

We have many VoIP users over 802.11
- However, 802.11 is designed for data traffic.
- What is the call quality for them?
- What is its impact on users who only transfer data?

There are problems which lead to degradation of call quality.
- Exponential back-off when contention happens
- Framing overhead per packet

Possible Solutions:
- Decrease the packet rate
- Use higher speed networks like 802.11g
- It would not help, the degradation problem still exist
- Use 802.11e which prioritize VoIP traffic
- It would increase contention

Our solution:
- For uplink: prioritized TDMA
- Stablish an schedule for sending packets
- Sync clock between nodes
- Compete with non-TDMA traffics
- use several level of prioritization
- For downlink: use an aggregator
- Send the aggregated traffic towards only one station
- The other stations must overhear that

Evaluation:
- On 801.11b and 802.11g
- The improvement on 802.11g is less

Q: Your evaluation did not cover the case for multiple TCP traffics
A: We had experiments with Web traffic which is the case of multiple TCP traffics

Q: How does it work in practice? In practice, we have collisions and also assigning slides between multiple hops is a big challenge!
A: -

Q: What is the delay performance?
A: -

Q: Why not just give higher priority to short packets?
A: -

Q: Why not use a separate single channel for all VoIP traffics?
A: Yes, why not?

Block-switched Networks: A New Paradigm for Wireless Transport
Ming Li, Devesh Agrawal, Deepak Ganesan, and Arun Venkataramani, University of Massachusetts Amherst

—————————

TCP performs bad over wireless.
1) It is because end-to-end rate control mechanism is too conservative
- It leads to redundant retransmissions
2) It uses packets as unit of control
3) It has complex cross-layer interaction

Re-design:
1) End-to-end -> hop by hop
2) Packets -> Blocks
3) Complexity -> minimalism

Techniques:
- virtual retransmission
- use data in cache for retransmission
- Back pressure
- limit # of outstanding blocks per flow at forwarder node
- ACK withholding

Q: What about connections to wired networks?
A: Future work

Q: What about responsiveness? For SSH traffics, the responsiveness is very important.
A: In the evaluation, we have results related to small files.

Q: Your solution does not cover the case that two routers are feeding a downstream router.
A: We treat them similarly.

Session Chair: Jeff Mogul, HP Labs

Somniloquy: Augmenting Network Interfaces to Reduce PC Energy Usage
Yuvraj Agarwal, University of California, San Diego; Steve Hodges, Ranveer Chandra, James Scott, and Paramvir Bahl, Microsoft Research; Rajesh Gupta, University of California, San Diego

——————————

People do not use the sleep mode often, even if the CPU is idle.
Objective: make the PC responsive even when it is in sleep mode.
Key idea: use a secondary processor which is functionally similar but uses much less power.

Implementation: Augment USB-based network interface
- Wakes up host whenever it is needed to handle some applications.
- It uses filters on incoming traffic not to wake up the host PC unnecessary.
- Stub: a small version of the application that can be run in the secondary CPU and take care of some part of ingoing and outgoing traffic.
- It should be small to run under the limited resources of secondary CPU.
- e.g. BitTorrent download.

Q: Windows sideshow has a second screen showing some information. How is that different from your work?
A: The information in sideshow are not actively updated; they are just some information before the computer goes to sleep mode.

Q: What would be the cost of having a dedicated proxy for an organization instead of a secondary CPU for each PC?
A: Administrative cost

Q: What about the transition cost between sleep and wake-up mode?
A: Our results already include this cost.

Skilled in the Art of Being Idle: Reducing Energy Waste in Networked Systems
Sergiu Nedevschi, International Computer Science Institute and Intel Research; Jaideep Chandrashekar, Intel Research; Junda Liu, University of California, Berkeley, and International Computer Science Institute; Bruce Nordman, Lawrence Berkeley National Laboratories; Sylvia Ratnasamy and Nina Taft, Intel Research

—————————–

The need for network connectivity makes people not to use the sleep mode.

What is the potential for energy saving?
What would be the design space for possible solutions?

Collect traces of 250 boxes: 90% laptop, 10% desktop.

About 60 TWh/year is wasting: 6 billion dollar per year

Proxy can handle some part of incoming traffic.
Do we need proxies?
- incoming traffic is high even when the CPU is idle
- sleep time would be very bad if the we want to wake up the CPU for each packet
- then, yes we need proxies.

Large portion of the broadcast and the multicast traffic could have a simple response or could be simply ignored.
According to this, they propose a list of rules regarding how to handle each type of traffic.

Q: What is the trade-off between saving more energy and increasing future performance?
A: We are doing our best.

Q: What about active applications where the outgoing traffic triggers the incoming traffic?
A: We have no solution for that.

Q: What do you think about the future trend, using a proxy or using a secondary processor?
A: -

Session Chair: Farnam Jahanian, University of Michigan

Unraveling the Complexity of Network Management
Theophilus Benson and Aditya Akella, University of Wisconsin, Madison; David Maltz, Microsoft Research

——————————-

Metrics for measuring complexity of a network by analysis of its configuration file.

Types of complexities:
- Referential dependence: complexity behind configuring routers correctly
- Inherent complexity:

Metrics:
- Number of reference links per router
- Normalized by number of devices
- Number of routing instances

Capturing network policies with reachability sets
- [taken from paper] Reachability sets identify the set of packets that a collection of network paths will allow based on the packet filters, access control rules and routing/forwarding configuration in routers on path.

Results: Most of the networks are complex.

Q: Why do you normalize by # of instances?
A: We are interested in average complexity per device.

NetPrints: Diagnosing Home Network Misconfigurations Using Shared Knowledge

Bhavish Aggarwal, Ranjita Bhagwan, and Tathagata Das, Microsoft Research India; Siddharth Eswaran, IIT Delhi; Venkata N. Padmanabhan, Microsoft Research India; Geoffrey M. Voelker, University of California, San Diego

——————————-

Problems of Home Networks:
- Mis-configured router
- Mis-configured end-host
- Remote problem, local changes

What do the users do today?
- Average time to resolve solutions: 2 hours

NetPrints = Network Problem Fingerprinting
- Take the configuration file from the user and propose a solution to resolve that.

Assumptions:
- Not dealing with performance: it only says that if the configuration is right or not?

Strategy: Snapshot-based
- sending normal snapshots to the server for training
- In the case of a problem, server suggest changes to the current snapshot (configuration)

Solution:
1) Configuration scrapper: taking configuration files related to the router, end-host, and remote problems.
2) Server knowledge-base: using a separate decision tree for each application
3) Configuration mutation:
- walk over the decision tree looking for a correct configuration
- frequently changing parameters have priority for mutation
- Assumption: higher the frequency, less disruptive the change would be.

Problems in making a perfect decision tree:
- Insufficient data: a new router
- Hidden configuration: application specific parameters

Q: why not take advantage of decision trees made for similar devices:
A: Future work

Q: What if your proposed solution was unacceptable for the user?
A: We can propose a list of suggestions to the user to pick the one that works for her.

Q: What about the configurations that can not be captured?
A: Nothing.

Session Chair: Geoffrey M. Voelker, University of California, San Diego

Studying Spamming Botnets Using Botlab
John P. John, Alexander Moshchuk, Steven D. Gribble, and Arvind Krishnamurthy, University of Washington

———————

Botnet: a network of compromised machines

It is very hard to study.

We used a Black Box approach.

We need to gather more data to understand Botnets.
Botlab: make it easier to monitor botnets.
- Get the bot binary, and pass it through the phases of initial analysis and safe execution.

1) Obtaining bot binaries:
- Active crawling
- Analyzing emails
2) Selecting interesting ones
3) Safe execution
4) Manual adjustment

Challenge:
- We have local view of spam producers
- We have global view of produced spams
- How to map between these two?

Results:
- 79% of spams come from a few botnets
- spam campaign relation to botnets is many-to-many
- 80% of spam points to 57 web server IPs

Q: Why not take advantage of information about saturated net links?
A: Good idea

Q: What about the ones which come from different sources?
A: We check the characteristics, so it is not an issue.

Q: Do the spammers have access to high bandwidth links?
A: I know about spam servers in South Korea which have high bandwidth available.

Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks
Ramakrishna Gummadi and Hari Balakrishnan, MIT CSAIL; Petros Maniatis and Sylvia Ratnasamy, Intel Research Berkeley

———————

If you mistakenly are flagged as spam, then you are in a big trouble.

How to distinguish bots from humans?

Assume:
- Untrusted Operating System
- Verifiable TPM boot up

Requirements:
- Automatic
- Fast
- Small TCP
- Privacy & Anonymity

TPM:
- small physically sealed chip
- Two relevant protocols
- direct anonymous attestation
- sealed storage

Not-a-Bot (NAB):
Goals:
- Attest all human requests
- Reduce attested bot requests

Attestation:
- non-transferable
- bound to request content
- single usage

The main questions:
- When to attest?
- What to attest?

Evaluation:
- Xen VMM
- 500 lines in kernel
- 10ms on 2GHz CPU
- NAB reduced inbox spam by 90%

BotGraph: Large Scale Spamming Botnet Detection
Yao Zhao, Northwestern University and Microsoft Research Silicon Valley; Yinglian Xie, Fang Yu, Qifa Ke, and Yuan Yu, Microsoft Research Silicon Valley; Yan Chen, Northwestern University; Eliot Gillum, Microsoft Corporation

———————

The problem with Hotmail:
- Zombie machine gets a free email
- Then gives it to spam servers

BotGraph:
- A graph-based approach
- Efficient implementation in Drayad
1) detect aggressive sign ups
2) graph-based algorithm

On user-user graph
- edge: number of ASes that shared the IP address

Random graph theory: if d > 1 then most node are in a single connected subgraph.

Validation:
- Manual check
- Comparision with known spmming users

Q: There was a work at 2000 named by SybilAttack. What is the relationship of this work to that?
A: -

Q: 50% false positive is very high!
A: Yes, it is.