Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can

Session 7.2: Scheduling and resource management: 2

Title: Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can

Authors: Virajith Jalaparti (University of Illinois, Urbana-Champaign), Peter Bodik (Microsoft Research), Ishai Menache (Microsoft Research), Sriram Rao (Microsoft), Konstantin Makarychev (Microsoft Research), Matthew Caesar (University of Illinois, Urbana-Champaign)

Paper: http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p407.pdf
Public review: http://conferences.sigcomm.org/sigcomm/2015/pdf/reviews/241pr.pdf
Large compute clusters have become quite common. The jobs on this network are often constrained by the network. Network scheduling is important for data-parallel jobs, because they include Network intensive stages (e.g., shuffle, join).
Several techniques proposed. Consider a simple map-reduce job, where you have a bunch of maps and reduces. You have inputs that are sent to the maps. The focus is on placing tasks, e.g., Tetris and Quincy. There is a focus on scheduling network flows, e.g., Baraat and Varys. The limitation of existing techniques is that the map input data is spread randomly. The maps produce data which is sent to the reducers. When the reducers start running the reduce input is spread randomly.
The authors propose placing data input in a few racks. Map input data is placed in one rack. This then means the reduce input is in the same rack. Furthermore, all the transfers stay within the rack leading to rack locality. The benefit of this proposal include high bandwidth between tasks and reduced contention across jobs. This placement of data is feasible, and it is useful in cases where there are recurring jobs known ahead of time and separate storage and compute clusters.
The challenge of this approach is how many racks to assign a job. The presenter showed a figure that showed that one rack may be sufficient for 75—95% of jobs. However there is a long tail, and we may need more than one rack for 5—25% of jobs. Offline planning using job properties can be used to address this problem.
The authors propose a system called Corral. Corral consists of an offline planner and a cluster scheduler. The planner takes future job estimates and determines which racks are to be used. Corral essentially solves an offline planning problem. For data placement: One data replica is constrained to Racks(i), while other replicas are placed randomly for redundancy.
The planning problem is formulated as follows: Given a set of jobs and their arrival time, find a schedule which meets their goals. There are two scenarios: Batch or online. With the former you minimize the makespan, while the latter minimizes the average job time. This presentation focusses on the batch approach.
Corral was implemented on Yarn with a modified HDFS and Resource manager. The cluster had 210 machines in 7 racks. Three different MapReduce workloads were tested. Corral reduces makespan by 10—33%. Corral improved the network locality. There is reduced contention across the cluster.
Q: Do you consider that different jobs may share data?
A: No we don’t take it into account. That is deferred to future work.

Session 6: Practical, Real-time Centralized Control for CDN-based Live Video Delivery

Authors: Matthew K. Mukerjee (Carnegie Mellon University), David Naylor (Carnegie Mellon University), Junchen Jiang (Carnegie Mellon University), Dongsu Han (KAIST), Srinivasan Seshan (Carnegie Mellon University), Hui Zhang (Carnegie Mellon University, Conviva Inc.)

Presenter: Matthew Mukerjee

Link to the paper
Link to the public review

This presentation outlines the design of a hybrid VDN (Video Distribution Network) which combines the global state view of a centralized controller with the scalability of a distributed control system. 

Content delivery exists as an optimization to maximize service quality which minimizing cost. Due the large demand of Internet video traffic, and its significant traffic volumes, the problem of delivering video content should be optimized on a per request basis. Much of the challenge of centralized optimization in this context is the ability to scale up to thousands of servers with the minimal response needed for live video distribution. The authors present three potential solutions to this problem: a completely centralized approach, a distributed approach and the eventual hybrid approach. 

In the centralized approach, at each level of the distribution tree, the central controller is queried to inform where to next route each request. The controller would run an integer linear program for each request to determine the optimal next hop. The large amount of overhead, and considerable per request computation, all directed toward a single controller resulted in adverse performance in video start time for users. The authors next evaluated a decentralized control mechanism, distributing control using “distance-to-video” tables (similar to distance-vector) distributed at each server. While this approach provided much more scalability, it produced suboptimal decisions due to a lack of a global state. Also provided a much larger variance in performance due to a lack of coordination between requests.

The hybrid approach described in the paper combines the two approaches by using the same distance-to-video tables in the completely decentralized approach but which are updated and maintained by a centralized controller. 

Presenter Questions:

Q1. Why did you not decompose the optimization problem (e.g. NUM)

A. Due to the per request information used for optimization, the authors needed a global view of state which can only be accomplished through centralized control.

Q2. Do you take advantage of caching?

A.     Since the system focuses on live video, caching is less of an issue. For example user interactive videos like Twitch have a delay tolerance which is too low for a cache delay, therefore the system is designed to not utilize caching.

Q3. Did you look at reducing the TTLs? Did you look at lowering the bitrate for improving client performance?

A.     Reducing the TTL to 1 second from 30 seconds produced a nominal improvement, and was not worth the cost of the increase in DNS server traffic.

Q4. Did you consider adapting client bitrates in your study?

A. Client bitrate adaptation is a well studied problem, and was out of the scope of the paper.

Silo: Predictable Message Latency in the Cloud

Authors: Keon Jang (Intel Labs), Justine Sherry (UC Berkeley), Hitesh Ballani (Microsoft Research), Toby Moncaster (University of Cambridge)

Presenter: Keon Jang

The author started his presentation by stating how shared network effect tenant performance, and motivate this statement by showing simple experiment with memcached, a popular in-memory key-value store by running memcached against netperf. The found out that request latency increases significantly due to network contention. Thus, important aspects such as bandwidth, packet latency, and burst allowances cannot be guaranteed for tenants.

The author introduced Silo, a system that offers these guarantees in multi-tenant datacenters. Silo leverages the tight coupling between bandwidth and delay. In other words, controlling tenant bandwidth leads to deterministic bounds on network queuing delay. The author showed how Silo performs in comparison to existing solutions such as TCP, DCTCP, Okto, Okto+

The authors evaluate Silo across three platforms: testbed experiments with memcached, through ns2 simulations, and through flow-level simulations. The evaluation showed how Silo ensures predictability for message latency and provides simple design where VM placement satisfy both latency and bandwidth requirement

Q: How much bandwidth and latency real applications need?
A: There are other works that specify these needs and tenant can specify these requirements as well.
Q: Did you figure out how to use determinist network calculs to do the modeling of batched packets?
Yes

Hopper: Decentralized Speculation-aware Cluster Scheduling at Scale

Authors: Xiaoqi Ren (Caltech), Ganesh Ananthanarayanan (MSR), Adam Wierman (Caltech), Minlan Yu (USC)
Presenter: Xiaoqi Ren 

The author started by introducing hopper which is a speculation-aware job scheduler, and implements both decentralized and centralized prototypes. She began by showing limitation of current designs of schedulares’s literature (both centralized and decentralized) where it ignores an important aspect of clusters: straggler mitigation via speculation.
The authors asks central question in the design of a speculation aware job scheduler which is how to dynamically (online) balance the slots used by speculative and original copies of tasks across jobs.
 The authors shows the key insight behind Hopper which is that a scheduler must anticipate the speculation requirements of jobs and dynamically allocate capacity depending on the marginal value (in terms of performance) of extra slots which are likely used for speculation. The presentation later showed the three demonstration prototypes of Hopper where they augment the centralized scheduling frameworks Hadoop (for batch jobs) and Spark for interactive jobs), and the decentralized framework Sparrow.

Beside the compatibility of Hopper with all current speculation algorithms, Hopper’s job speed ups of 66% in decentralized settings and 50% in centralized settings compared to current state-of-the-art schedulers.

Q: The optimization systems depeneds on these data paerematers that you learn. Giving the ability of these learning parmementers, do you see repteaibility across jobs you need to maintain state of previously ran jobed in order to learn data correctly and how sensitive these results to accuracy in all stragleer compitions 
A: Our evaluation we don’t artififually add any propbabilty distriatiob to manualy create struggles, we just use workload and try to use completion time of the task to fit in the distribution to gues the beta. We also show in the paper that if user can show the probs based on their charictariztions of how likely struggler will occur we can get more efficient results.

Session 5 Paper 2: SpotFi: Decimeter Level Localization Using WiFi

Authors: Manikanta Kotaru (Stanford), Kiran Joshi (Stanford), Dinesh Bharadia (Stanford), Sachin Katti (Stanford)

Presenter: Manikanta Kotaru

Link to the paper
Link to the public review

This talk presents the design and implementation of an indoor WiFi localization system - SpotFi. The presenter first illustrates several indoor applications that can benefit from accurate indoor localization. A good solution should consider both the deployment, universal, and accuracy. The key idea of this paper is also to exploit the angle-of-arrival (AoA) of signals, together with the time-of-flight signals. Compared to other existing works on indoor WiFi localization, this work does not need to modify the AP firmware. SpotFi only needs information that is already exposed by commodity WiFi devices.

As presented in the talk, this work has two major contributions:

1) Different from previous work that needs half dozen antennas at the AP, SpotFi is able to compute the angle of arrival of multipath signals accurately with only three antennas. This will be very useful in practice because most of the existing APs in use by people only have three or less antennas.

2)  Furthermore, advanced estimation and filtering techniques are adopted to identify the angle-of-arrival of the path between AP and targeted object. Existing works only consider the angle-of-arrival. The technique proposed in this paper also consider the time-of-flight. The analytical model includes both signals at the antenna as well as signals from different subcarrier, to compensate the few antennas it uses.

The proposed SpotFi has been implemented using the off-the-shelf Intel 5300 WiFi NICs. Experiments are carried out in 55 different positions of a building. Experimental results show that with only three antennas at the AP, the SpotFi can achieve median localization error of 0.4 m, which is similar to those famous existing work ArrayTrack  and Ubicarse.

Q: The median localization error is 0.5m, and the maximal is up to 5m. Is this practical?
A: Yes, the median value is 0.4m. About 80% of the localization error is below 1.5m.

Q: It is a nice work. Have you considered the impact of light of sight? In reality, the target object can move and may stay in an environment of dense APs. Can you comment on this?
A: The system can still work in dense layout of APs.
Q: The localization is in a passive way and may cause privacy problems to the targeted devices.
A: We can allow users to decide. Users can enable/disable to use this technique. 

Session 5 Paper 1: Laissez-Faire: Fully asymmetric backscatter communication

Authors: Pan Hu (University of Massachusetts Amherst), Pengyu Zhang (University of Massachusetts Amherst), Deepak Ganesan (University of Massachusetts Amherst)

Presenter: Pan Hu

Link to the paper

Link to the public review

This talk presents the design of an asymmetric backscatter system, the Laissez-Faire (LF-Backscatter). Existing backscatter systems usually suffer from the tradeoff between energy-efficient and available data rate. The presented LF-Backscatter in this talk introduces a protocol that can enable nodes to blindly transmit data when they sense. The proposed system targets at both achieving the high energy-efficient and high data rate. The system adopts a extremely power-efficient backscatter radio. The backscatter RX only needs one transistor. Nodes can transmit at the same time and can transmit whenever they want to.

One difficulty in designing the system is the decoding multiple concurrent transmissions at the readers. To solve this problem, this work introduces method to separate interleaved signals in the time domain, and separate the collisions of transmissions in the frequency domain. The edges of the received signals from the tags can be detected at the reader, where the reader adopts a high sampling frequency.


The proposed system is implemented and evaluated. Experimental results show that LF-backscatter can improve the data rate by 15 times compared to TDMA. Furthermore, LF-backscatter can also improve the energy efficiency by 20 times when compared with TDMA and Buzz. One drawback of this system is that it requires a high SNR, typically 4dB higher than the other two techniques.


Q: The capacity of the system?
A: Can even achieve 100kbps with several dozens of nodes.

Q: You claim at the beginning that the tags can work at bitrate and at any time. Is that ture?
A: The current bottleneck is the transmission from the Reader to the Tags, not from Tags to the Readers. A requirement of 4dB higher SNR is not bad.

Session 5 (Wireless) Paper 4: Caraoke: An E-Toll Transponder Network for Smart Cities

Authors: Omid Abari, Deepak Vasisht, Dina Katabi and Anantha Chandrakasan
from MIT

Link to the public review

 What we can do today with the current e-toll transponders is limited. This is because only one transponder at a time can be read by an RFID reader since the transponders do not have any MAC protocol. If we can overcome this barrier, a lot of applications can come out. Cities can deploy readers at traffic lights to spot cars that pass at red light, estimate the crowdedness of intersections and the speeds of the cars (to detect violations). To achieve this, the authors proposed a networked system of e-toll transponders and readers, where the RFID readers are enabled to work with collisions, without modifying the design of existing transponders.

 The presenter explained that they exploit the carrier frequency offset (CFO) of the transponders. He explained that they looked at the collision in the frequency domain and observed spikes corresponding to the CFOs of the colliding transponders. He also explained that they can get the number of transponders by counting the number of spikes. They also can localize cars into their parking spots by exploiting the differences in CFOs and apply RF-based localization.

The presenter explained that decoding of IDs is also possible by combining multiple collisions in a way that boosts up the SNR of a target transponder above the others. The presenter showed that Karaoke counts cars accurately with an average error of 2% and can localize cars into their parking spots with an error of only 4 degrees. Number of car ids being correctly decoded increases as the number of cars increase.

Q: Do you expect millions of queries to the transponders? How long does the battery last?
A: Power consumption is really low and the number of queries do not matter.

Q: What if people take the transponders out, if they cheat or jam?
A: Vision is that the transponders will be mandatory. And these will be illegal actions.

Q: Is it not easy to spoof the system? Someone builds a system that creates spikes and makes the system think there are a lot of cars in a region?
A: This will be illegal.

Session 5 (Wireless) Paper 3: BackFi: High Throughput WiFi Backscatter

Authors: Dinesh Bharadia, Kiran Joshi, Manikanta Kotaru, Sachin Katti
from Stanford University

Link to the public review

According to the authors, for the Internet of Things (IoT) to become a reality, the IoT devices need to satisfy three requirements: sufficient range & throughput, low power design, and reuse of ambient signals. In order to achieve these goals, the authors propose a backscattering-based approach where the IoT devices piggyback their data on the ambient signals.


The presenter explained that this is done by modulating the data on the received downlink signals from Wi-Fi APs to clients and then backscattering the signal to the APs. The authors designed an AP that can receive backscatter signals even when transmitting data. In order to achieve this, they rely on recently-proposed self-interference cancellation techniques for full-duplex radios and modify them so that the backscatter itself signal does not get canceled.

The presenter showed that BackFi provides low energy consumption for the IoT devices, and delivers 1Mbps of throughput for 5m range and 1Mbps for 1m range. BackFi also improves spectral efficiency.


Q: What happens when all the IoT devices respond at the same time since there is no MAC protocol? How do you handle that?
A: We are working on a protocol to actually do it.

Q: Since there are multiple APs and many clients, a lot of them will trigger the backscatter signals. How do the sensors know when to reply and to which AP they’re associated with?
A: The AP sends a CTS message and then the sensors know that the next message will be backscattered to this AP.

Session 4 (Middleboxes) -- Paper 2: BlindBox: Deep Packet Inspection over Encrypted Traffic

Authors: Justine Sherry (UC Berkeley), Chang Lan (UC Berkeley), Raluca Ada Popa (ETH and UC Berkeley), Sylvia Ratnasamy (UC Berkeley)
Presenter: Justine Sherry 

Paper: http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p213.pdf

Public Review: http://conferences.sigcomm.org/sigcomm/2015/pdf/reviews/332pr.pdf

Middleboxes are used to do deep packet inspection, and scan and filter traffic. However, today many of network communications are encrypted, which means middleboxes won't be able to do their normal DPI. This work presents BlindBox which achieves DPI for encrypted traffic.

The speaker pointed out that they are mostly focused on intrusion prevention systems, and motivated the problem by pointing out that such systems are responsible for monitoring connections and deciding which ones should be blocked, which is an important functionality for both clients and networks, but conflicting with encryption. So the goal is to get the combination of privacy (encryption) and functionality (middleboxes): DPI without decryption.

The speaker then discusses the thread model and explains that one solution is for vendors to basically release their detection lists, but that's not something they are willing to do because that basically their secret sauce and what makes them better than their competitors.

An overview of BlindBox HTTPS is then presented, starting with the handshake and how it's basically base on known techniques. Encrypted data goes through BlindBox and the middlebox learns encrypted keywords. One downside of this is the threat of middlebox doing frequency analysis attacks. To overcome this, they use the literature on searchable encryption approaches. The speakers talks about how randomized searchable detections can help with this problem, but it comes at the cost of lower speed as opposed to deterministic approaches. To get the best of the two worlds, every token is encrypted and then used as the salt for next encryption.

The speaker mentions that the talk focused on exact matches and encourages the audience to read the paper for details on more complex matching such as regular expressions.

The talk was concluded with evaluation results on two vectors: functionality and performance. In terms of functionality the can support 100% of things that middleboxes do for exact matching. Fo more complex matchings such as regex, they have to use a weaker security model if they wish to achieve that 100%. In terms of performance it's comparable with current IDSs employments, but there is a setup time that it's reasonable if connections are long-lived and persistent.

Q: I don’t believe IDSs work! And also usually what they do is not just substring matches. What we really care about malware. How do you apply this in an environment where malware in polymorphic and encrypts itself? I am not convince this is going to work! 
A: I actually don't agree with that. IDSs are used all the time
Q: Yes, but they don't work! it's like 99% FP! (Let me take a look at the paper)

Q: Having the marker at different locations in the tree doesn't really prevent  frequency attack?

A: Yeah, once there is actually a match, we want the middlebox to learn that! So of course you can do frequency analysis over match data. But not over innocent data

Q: If alice is attacker, why would she talk with the middlebox?

A: Bob is going to determine what his security level is.

Q: About the performance: ~190Mbits per second. That’s actually orders of magnitudes slower than commercial boxes

A: thats single core

Q: Oh ok. So what’s the bottleneck in the performance?

A: The hand shake! That’s what killing us and needs to be revisited and improved.

Q: What o you do about behavioral IDSs?

A: usually IDSs do exact matches and if there is a match, they do regex and more. Once you have an exact match, you have the ability (probable cause) to decrypt

Q: What prevents middleboxes to add more keywords to do freq. attack?

A: Those keywords should be signed by trusted parties (e.g. McAfee)

Q: followup on behavioural IDS. not clear how your system works with them.

A: actually much of those are about connection analysis and .. which is unencrypted !

Q: Your approach seems very english centric. How does it work if you're in china?

A: I would actually just use a VPN instead of HTTPS ;) we can tokenize binary

Q: You said IDS operators don’t want to reveal their secrets so you need them in-network. Is that really true?

A: There are many reasons why you still need that in-network analysis even if you could run it on your computer (e.g. what if your machine is compromised, the in-network can still save you)

Session 4 (Middleboxes) -- Paper 1: Multi-Context TLS (mcTLS): Enabling Secure In-Network Functionality in TLS

Authors: David Naylor (Carnegie Mellon University), Kyle Schomp (Case Western Reserve University), Matteo Varvello (Telefónica Research), Ilias Leontiadis (Telefónica Research), Jeremy Blackburn (Telefónica Research), Diego Lopez (Telefónica Research), Konstantina Papagiannaki (Telefónica Research), Pablo Rodriguez Rodriguez (Telefónica Research), Peter Steenkiste (Carnegie Mellon University)

Presenter: David Naylor from CMU

Paper: http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p199.pdf

Public Review: http://conferences.sigcomm.org/sigcomm/2015/pdf/reviews/193pr.pdf

The speaker motivated the pointing out two observations:

1. Encryption is increasing (more traffic is moving towards HTTPS)
2. In network optimization is important (e.g. DPI for intrusion detection)

But the issue is that in-network middleboxes cannot inspect encrypted traffic, and users are not willing (rightfully) to compromise privacy and security. One solution is to let the middleboxes perform MITM attack and decrypt the traffic, inspect it, and the re-encrypted. But this is not ideal as it gives middleboxes unrestricted access to all users' traffic. The speaker argued that such unrestricted access is not necessary and middleboxes can actually perform their functionalities with limited view into user's traffic. 

The speaker then talked briefly about TLS and what provides (authentication, secrecy, and integrity) and how TLS + middleboxes is problematic as there is no mechanism to verify middleboxes, no secrecy guarantees past the middlebox, and how middleboxes have unrestricted read/write access.

He then carried on to explain the high level design of mcTLS. mcTLS has two extra requirements on top of TLS: 1)visibility and control, 2)least privilege. mcTLS introduces the notion of "context", which the speaker said they can be seen as tags and showed an example of contexts for HTTP and how most parts of it don't need r/w access:

The speaker emphasized that mcTLS does not support transparent middleboxes, as in both end points are aware of the middlebox and the middlebox ONLY received a key for a context if both ends agree on that.

Finally, the speaker talks about mcTLS's performance and its overhead in terms of data, cpu, and time. mcTLS has a few Kb of data overhead and might hurt when getting small objects. In terms of time, it has the same number of round trips as TLS.

Q: Does mcTLS require clients to have public keys?

A: No

Q: So what do you require the client to have? It's providing something

A: This is actually same as TLS

Q: How do you authenticate clients then?

A: You don't need that for mcTLS. If you need to authenticate clients for example for a paid service, that should be done at the application layer

Q: You made a distinction between authorized and unauthorized middleboxes. Now who gets to decide what's authorized? You're building a system where you can draw that line hard, as oppose to soft. This could be dangerous

A: We decided to leave that to the end point. They have to both decide if they want that middlebox there.

Q: This seems to work well in theory, but it requires all parties to be updated!

A: yeah, all parties need to be updated, but you can always fall back into TLS

Q: but updating apps can be hard

A: yeah but you can build this into a library

Q: Middleboxes will never adopt this! I don’t see what’s the financial win?

A: Some of these mbs are helpful to clients and costumers might want this!

Q: there is 2012 IETF proposals, (?), didn’t really progress behind the draft. Have you seen it? how does it compare to your solution?

A: not very familiar.

Q: is there a solution for client or server to say I want to middle box to interfere with my traffic?

A: absolutely, both end points can deny access to the middle boxes

Session 1, Paper 1: "BwE: Flexible, Hierarchical Bandwidth Allocation for WAN Distributed Computing"

Authors: Alok Kumar (Google), Sushant Jain (Google), Uday Naik (Google), Anand Raghuraman (Premise Data Corp), Nikhil Kasinadhuni (Google), Enrique Cauich Zermeno (Google), C. Stephen Gunn (Google), Jing Ai (Google), Björn Carlin (Google), Mihai Amarandei-Stavila (Google), Mathieu Robin (Google), Aspi Siganporia (Google), Stephen Stuart (Google), Amin Vahdat (Google)

Presented by: Alok Kumar from Google

Paper: http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p1.pdf

Public Review: http://conferences.sigcomm.org/sigcomm/2015/pdf/reviews/175pr.pdf


The BwE system has been deployed inside Google for the last 5 years.
Google's internal network traffic is enormous: If Google would be considered an ISP, it would be the 2nd biggest one in the world!
B4 is Google's internals WAN. It spans multiple continents (North America, Europe, Asia)

Such a giant-scale network has many inefficiencies in bandwith allocation.
The goal of the project: a centralized bandwith allocation algorithm at the scale of Google's WAN
(allowing for flexible allocation polcies; enforcement at hosts), to minimize inefficiencies.

System before BwE: Thousands of competing users classified in few classes; no differentiation

Search vs Gmail, instead of user by user.
No good solution for non-critical application such as backups, where latency is irrelevant, but high throughput necessary.

What problem does it solve?
Visibility into users
Sharing of WAN bandwith based on configured policies -> users can specify/buy requirements

System Architecture: Global enforcer (takes policies and network model as input), computes allocation -> send to several cluster enforcers -> send to multiple job enforcers -> send to host enforcers

Policies have the following form:
Guranteed Bandwith (with weight) + Best Effort (with weight)
For example: Gmail: 10 Gbps guranteed + 20 Gbps best effort with w=2 and 50 Gbps with w=1


Algorithm: path selection (traffic engineering) & bandwith allocation are optimized independently, rather than doing joint optimization. This is suboptimal, but scales better.

Phases:
(1) Traffic Engineering (TE): run less frequently (so things scale): determines paths -> input to MPFA
(2) MultiPath Fair Allocation (MPFA): Can handle arbitrarily complex networks, flowgroups can take multiple paths, network can have bottlenecks

Failure Handling: Redundancy at each layer

Future Work: Deadline based scheduling, Joint BwE-TE optimization

Conclusion: BwE
* is single place for specifying bandwith polices
* enables efficient use of network resources


Questions/Answers:
[Unfortunately very incomplete due to acoustic problems]

Q1: Do applications need to specify requirements?
A: [had problems to understand acoustically] We have both; services buy bandwith

Q2: Do you over subscribe to get good utilization?
A: On certain levels

Q3: ...
A: Smooth polices over time (5 minutes)

Q4: Assumption that all hosts offer roughly the same amount of traffic; how much inbalance is there in practice?
A: ...

Q5: What about delay? Do you take it into account?
A: TE does somewhat (tries to assign shortest paths)

Session 1, Paper 3: PGA: Using graphs to express and automatically reconcile network policies

Authors: Chaithan Prakash (University of Wisconsin-Madison), Jeongkeun Lee (HP Labs), Yoshio Turner (Banyan), Joon-Myung Kang (HP Labs), Aditya Akella (University of Wisconsin-Madison), Sujata Banerjee (HP Labs), Charles Clark (HP Labs), Yadi Ma (HP Labs), Puneet Sharma (HP Labs), Ying Zhang (HP Labs)

Presenter: Chaithan Prakash from HB Labs

Paper: http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p29.pdf

Public Review: http://conferences.sigcomm.org/sigcomm/2015/pdf/reviews/346pr.pdf

PGA stands for Policy Graph Abstraction
It aims at providing an intuitive & simple API in which network operators can express and combine network policies. PGA is close to the kind of graph-based representations network operators would draw on a white board.

Network policy management is a challenge:
Different types of policies by different stakeholders have to be combined into a single coherent, well-formed policy that satisfies the constraints imposed by the individual policies.
In practice, this "intent-composition" is usually performed manually by network operators.
-> not scalable, error prone, low-level

High level languages such as Pyretic, NetKAT, ... provide composition operators; but they are not sufficient (?) to compose high-level policies.

PGA aims to provide:
* Simple, inutuitive abstractions
* portable policies (decoupled from network specifics)
* automatic policy composition

Model:
Nodes represent groups of end-points (EPG) that satisfy a certain membership predicate
Directed edges represent allowed communication
Edge attributes: classifiers/service chains/network functions, for example what port, byte counting, through load balancer
Labels: capture endpoint attributes: tenant, location, security status (logical labels)
Several graphs are composed into single graph by composition algorithm.

The authors have implemented a prototype in Python. It provides a GUI to input graphs, and uses one of the following two backends to deploy the resulting policies:
  * Pox controller in reactive mode -> OpenFlow
  * OpenStack Neutron

The runtime overhead (for executing policies) is in the sub-ms area.
Compilation scales:
  (a) <10 min, < 1.2 GB for a graph with 1 million edges, but no network functions
  (b) <14mins, < 20 GB when randomly inserting network functions into the graph.

There will be a live demo of the prototype tomorrow.



Questions (incomplete & paraphrased)
Q1: Complex policies combination, how do you know it's right?
A: Intuitive framework; no absolute guarantees. System raises flag if well-formed composition is impossible.

Session 3.2, Paper 3 [Experience Track 2]: Jupiter Rising: A Decade of Clos Topologies and Centralized Control in Google’s Datacenter Network

Authors: Arjun Singh (Google), Joon Ong (Google), Amit Agarwal (Google), Glen Anderson (Google), Ashby Armistead (Google), Roy Bannon (Google), Seb Boving (Google), Gaurav Desai (Google), Bob Felderman (Google), Paulie Germano (Google), Anand Kanagala (Google), Jeff Provost (Google), Jason Simmons (Google), Eiichi Tanda (Google), Jim Wanderer (Google), Urs Hoelzle (Google), Stephen Stuart (Google), Amin Vahdat (Google)

Presenter: Arjun Singh

Link to the Public Review by Ming Zhang

Summary:

Large-scale datacenters operated by companies like Google, Facebook, and Amazon support hundreds of thousands of servers in a single facility. It is often useful to ask: How did they address the key challenges of scalability, manageability, cost, and evolvability as their datacenter networks grew over time. This paper studies the evolution of Google’s datacenter network during the last decade.

Arjun highlighted the three common themes across the five generations of evolution of Google’s datacenter networks. They are 1) the use of Clos topologies for achieving scalable performance and failure resilience, 2) use of centralized protocols for managing operational complexity, and 3) use of cheap off-the-shelf commodity devices.

Arjun showed how Google started with firehose 1.0 that provided few Tbps of aggregate capacity in 2004 to Jupiter that supports up to 1.3 Pbps of capacity. He walked through how they used the three key themes in Google's datacenter design that enabled them to achieve high performance, high availability, and ease of network management at relatively low costs. Finally, he talked about managing small on-chip buffers by leveraging ECN and DCTCP and providing high reliability using redundancy and diversity.

Q/A (Paraphrased):

Q. You used DCTCP. What did you do for virtualized environments where you didn't have control over the end-host stack

A. I'm not too sure but I can't provide more details.

Q. It seems we are relearning what we learnt 30 years ago. Is it that earlier we focussed on "within" the switch Clos-type interconnections and now we are considering these distributed datacenters structured as Clos networks with centralized software for managing them

A. Yes

Q. What gains did DCTCP bring to your datacenter?

A. I don't know the precise numbers but the gains were quite significant.

Q. We in academia do not have access to a lot of things that companies like Google have. Would you like to comment on that?

A. Well, that is a good question. We also struggled with large-scale evaluation. As a result, we had to rely on virtualized testbed environments for testing new protocols and systems.

Q.  Do you still have congestion hotspots? Is there more thirst for intra-datacenter bandwidth?

A. Even though we removed most of the congestion hotspots over time, the need for bandwidth is constantly growing.

Session 3.2, Paper 2 [Experience Track 2]: End-User Mapping: Next Generation Request Routing for Content Delivery

Authors: Fangfei Chen (Akamai Technologies), Ramesh K. Sitaraman (UMass, Amherst & Akamai Technologies), Marcelo Torres (Akamai Technologies)

Presenter: Fangfei Chen

Link to Public Review by Ethan Katz-Bassett

Summary:

A key component in a content delivery network (CDN) is the mapping system that routes a client’s request to a server. Traditionally, the mapping systems have used the local recursive domain name servers (LDNS) as a proxy for determining clients' path conditions (called NS-based mapping approach). However, in several cases the network conditions of the LDNS and the client may be different. This paper provides the first large-scale study of the limitations of NS-based mapping and the experience of deploying EDNS0 (client-subnet extension to the DNS protocol); a solution that uses the client’s prefix to infer information about the client (their resulting system is called end-user mapping).

They collected data from over 3.76 million IP blocks. They found that more than 50% of the clients were within 100miles of their LDNS. However, there was a lot of diversity across countries. For instance, the average distance between clients and LDNS in India and Brazil was large. The author conjectured that this was because there weren't many (or perhaps no) public DNS servers within these countries.

Fangfei then talked about the performance benefits of using end-user mapping as observed by Akamai. In particular, they found that the download times improved by approximately 100ms. This is significant because better download times for the end-users are correlated with revenue. However, a major challenge they ran into was scalability. As there are more clients than LDNS servers generally, using EDNS0 meant that there was increase in DNS query traffic. It is a significant problem which requires more attention.

Q/A (Paraphrased):

Q. Why did you report results in terms of miles as opposed to RTTs

A. It was tricky to report them in terms of RTTs. Reporting them in miles was more direct and also helped in geo-locating the IP addresses

Q. Did you look at the costs at the ISP side of scalability concerns

A. We didn't look at the costs but such an analysis could be carried out with our data.

Q. Did you measure EDNS0 adoption?

A. No but we are encouraging ISPs to adopt it.

Q. Was there a rollout of new cache servers while conducting this study?

A. We did not specifically restrict the rollout of new cache servers.

Session 3.2, Paper 1 [Experience Track 2]: Large-scale measurements of wireless network behavior

Authors: Sanjit Biswas (Cisco Meraki), John Bicket (Cisco Meraki), Edmund Wong (Cisco Meraki), Raluca Musaloiu-E (Cisco Meraki), Apurv Bhartia (Cisco Meraki), Dan Aguayo (Cisco Meraki)

Presenter: Sanjit Biswas

Link to the Public Review by Kyle Jamieson

Summary:

How big of an issue is interference in deployed WiFi networks? Which applications are most popular? How fast is the uptake of newer WiFi standards (e.g., 802.11n and 802.11ac)? How utilized are the WiFi frequency bands and how is this changing over time? These are some of the exciting questions that this paper attempts to answer by analyzing an extremely large-scale measurement dataset from Meraki’s deployed WiFi networks.

Using Meraki's centralized management platform, they collected time-series data of applications, clients, and device statistics. This data was collected from over 20,000 networks and about 5.58M clients across a variety of deployment types.

Sanjit highlighted some interesting insights during his talk. These included:

• YouTube, NetFlix, and iTunes combined (i.e, video/music) dominated the traffic and over a period of one year, all these applications observed at least 60% growth in their traffic
• Most data was downloaded by users using the Windows/MS OSes and smartphone traffic witnessed one of the largest growth in terms of traffic as well as number of devices.
• While overwhelming majority of clients used 802.11n capable devices, most only used the single stream mode (these were largely smartphones equipped with single antennas). In addition, 802.11ac was observed to be gaining traction.
• They found most interference to be from 802.11 traffic. In addition, they found that majority of the wireless links exhibited a wide range of delivery ratios. On average, they observed ~55 networks/AP

In the end, Sanjit mentioned about one AP that had 10,000 nearby networks as well as about cable problems they frequently ran into. It is great that they have made their data publically available.

Q/A (Paraphrased):

Q. Most of Meraki's clients are enterprises. Do you expect the Netflix traffic to dominate for home networks or dorms?
A. Yes

Q. What was the latency between the radios and the collection server?
A. This was in the order of milliseconds.

Q. Why was the channel utilization so low?
A. We actually think, it is fairly high.

[Session 3.1, Experience track1] Pingmesh: A Large-Scale System for Data Center Network Latency Measurement and Analysis

Pingmesh: A Large-Scale System for Data Center Network Latency Measurement and Analysis

Authors: Chuanxiong Guo, Lihua Yuan, Dong Xiang, Yingnong Dang, Ray Huang, Dave Maltz, Zhaoyi Liu, Vin Wang, Bin Pang, Hua Chen, Zhi-Wei Lin, Varugis Kurien*
Microsoft, *Midfin systems

Presenter: Chuanxiong Guo

Link to the paper

Link to the public review

This work focuses on network measurement and analysis. It considers the data center network (DCN), and tries to tackle challenges in DCN operation, such as the source of incidents (network or not), tracking SLA etc. The work suggests that using latency measurements between any two servers these challenges can be addressed.

The system, dubbed Pingmesh, uses Pingmesh agents installed on each server. The agents are controlled by a Pingmesh controller, which defines and manages the measurements.  The system is built on top of existing infrastructure (Autopilot, Cosmos/SCOPE). The storage and analysis is done on a scale that ranges from 10 minutes to a day.

The rest of the talk focused on the results collected and the lessons learned.
It started by exploring latency measurements, while comparing two data centers.
A following packet drop rate study has shown packet drops at the NIC and the ToR, and compared it between different data centers, showing that they differ (for intra and inter rack drop), and that a typical drop rate is in the order of 10^-4 to 10^-5.
Using Pingmesh, it was possible to detect black holes (deterministic packet drops)  and silent random packet drops.

Pingmesh is not without limitations. Pingmesh can not tell which spine switch is dropping packets. Also, Pingmesh uses single packets for the measurements, which is not good for detecting network reachability and packet-level latency issues.

Pingmesh provides an always-on service that provides a full coverage. It provides scalability, leaving space for evolvability. As such, it is an interesting tool for tracking problems in the network, which is one of the hard problem today. Plus, it is running on a production system and for a long time (4 years), which is its main advantage. 


Q&A:

Q: What are the thresholds beyond which the overhead of measurements is too high?
A: Pingmesh has a lot of overheads, that relate to processing, but in terms on networking pingmesh uses just Kbps, vs. Gbps available on the servers, so it is negligible. 

Q: In the past, works like Planerlab used similar measurement techniques to predict how systems will behave. Will you be able to do what/if based on the huge amounts of data you collected?
A: We are currently focused on using the system for trouble shooting.

Q: Do you really need 2M probes to find that a server went down?
A: You can not predict what will happen next, so we try to make the measurements as comprehensible as possible, so we can catch failures quickly.

Session 3.1 - Paper 1: Inside the Social Network's (Datacenter) Network

Inside the Social Network's (Datacenter) Network

Authors: Arjun Roy (University of California, San Diego), Hongyi Zeng (Facebook), Jasmeet Bagga (Facebook), George M. Porter (University of California, San Diego), Alex C. Snoeren (University of California, San Diego)

Presenter: Arjun Roy

Link to the paper

Link to the public review

Summary:

This paper presents the production traffic workload characteristics of the Facebook datacenters and how the workload differs from the existing literature. Existing workload observations are mainly based on web search services, which does not capture all types of cloud services. Literature of datacenter traffic shows that: traffic is rack local and predictable over small timescales. The ability to design efficient deployments in datacenters by means of traffic workload knowledge motivates this work. Facebook datacenter architecture consists of multiple site, multiple datacenter within site and a fat tree topology consisting of clusters of servers connected together by top-of-rack switch, in turn connected to cluster switches, which are connected by Fat Cats aggregation switches. Servers have exclusive roles: cache, web, Hadoop and MultiFeed servers; rack typically contains same type of servers. Workloads are collected using Facebook-wide monitoring system using Fbflow(long term traffic storage, but of low resolution) and per-host packet-header traces using Port mirroring(short term traffic of higher resolution). 

Following are the observations from traffic analysis:

1. Although Hadoop deployments traffic is consistent with literature, other traffic is neither rack-local nor all-to-all(sparse rack locality and heavy inter-rack traffic observed in Front-end clusters).
2. Despite this inter-rack traffic, most of the links are loaded with less than 10% traffic. Heavy hitters are generally instantaneous and are not persistent. Sub-second traffic is unpredictable and ephemeral.
3. Traffic is bipartite due to colocation of servers of same type. 
4. Traffic is stable across all cache servers over long timescales(1-second timescale). Traffic distributions exhibit even spread across different levels(cluster, dataceenter, rack levels and so on). Hence traffic is stable over time and per destination.

These observations provide a chance to reduce inter-rack bandwidth.

Q&A:

Q: Any insights on why the heavy hitters didn't last for long, is it due congestion or some application the end hosts are doing?

A: Heavy hitters are ephemeral due to effect of load balancing. If heavy hitters are persistent, then that means the load balancer is not doing its job. Load balancer ensures that the cache center(which got heavy hit) does not get further requests for a significant amount of time to balance load properly.

Q: Was coordination between same type of service exhibiting locality similar to intra-rack locality?

A: We did look at locality. Since services are colocated at rack level, looking at rack level is exactly same as looking at type of service. 

Q: Instead of blind colocation of servers of same type, why not mix servers together?

A: Locality patterns wouldn't work out well by doing colocation of different servers.

Q: Are aggregation and core switches as volatile with respect to heavy hitters as end hosts are?

A: This study did not cover this.

Q: Are incast traffic issues observed in the FB datacenters similar to observations in DCTCP?

A: Incast traffic require micro-second scale observations, which weren't part of this study.

Session 1, Paper 4: Central Control Over Distributed Routing

Authors: Stefano Vissicchio (UCLouvain), Olivier Tilmans (UCLouvain), Laurent Vanbever (ETH Zürich), Jennifer Rexford (Princeton University)

Presenter: Stefano Vissicchio

Link to the paper

Link to the public review

Link to Fibbing website

This paper presents Fibbing, an architecture that achieves both flexibility and robustness through central control over distributed routing. Fibbing relies on traditional link-state protocol like OSPF and IS-IS, and by introducing fake nodes and links, Fibbing is able to control forwarding information base (FIB) directly.

The most exciting thing about this paper is, as mentioned in the public review, “The paper reminds us that SDN is not architecturally about a particular wire protocol but about decoupling

the control and data plane, and how in fact there are multiple ways, with varying trade-offs, to achieve it.”

System Design is clearly described in the graph below borrowed from the paper:

A Fibbing prototype is evaluated over three dimensions, 

• low CPU and memory overhead and no impact on convergence time introduced by Fibbing on existing routers, 
• the efficiency of Fibbing’s augmentation algorithm in terms of speed and size of topology
• a case study on a real network consisting of 4 Cisco routers showing how Fibbing alleviate congestion.

There is a Q&A section in paper which is worthwhile to take a look.

Q&A:

Q: Do you ever get to trouble if working with different switches from different vendors?
A: No, we use standard IGP, and there is no fancy specific features used.

Q: Given the complexity of network dynamics, I can't tell if this is a bad idea or a brilliant idea. How do you debug Fibbing when things go wrong?
A: It's true that Fibbing is hard to roll-back. But Fibbing controller could automate the roll-back. Controller can push some information to improve debugging ability. IGP has a shared view of topology, and it will sync up. We don't think debugging ability is a problem.
- Follow-up Q: If the controller crashes, will router fall-back to standard?
- Follow-up A: Yes.

Q: OSPF is hard to enforce high-level policy. Will things be easy if use BGP high-level policy routing?
A: We can apply a modified version of Fibbing to BGP. Different protocols have values in different settings.

Q: How does Fibbing work with OSPF hierarchy?
A: We need one controller per zone, and coordination is needed. Maybe in future work.

Q: Does Fibbing complicate debugging?
A: To me, Fibbing is not degrading debugging too much. You just need to understand why the fake nodes are there.

Q: We can apply either segment routing or Fibbing to do policy routing. Which to choose?
A: In some cases, they are complimentary. The solution of Fibbing is simpler, because it needs less information from the hardware. If just used for optimizing traffic, Fibbing might be better.

Q: SDN also gives you fine-grained control, but I don't see it in Fibbing.
A: It's true. Fibbing is not very sweet for fine-grained control, but it still provides you some level fine-grained control, such as middle-box. One possibility is to deploy Fibbing in the core instead of edge.

Q: How is implementation complexity in practice?
A: There is one special field in OSPF message, which is leveraged to enable Fibbing. And it works with real Cisco and Juniper routers.

How to Bid the Cloud

Authors: Liang Zheng, Carlee Joe-Wong (Princeton University), Chee Wei Tan (City University of Hong Kong & National University of Singapore), Mung Chiang (Princeton University), Xinyu Wang (City University of Hong Kong)

Paper (pdf)
Public review (pdf)

This paper studies the auction-based spot pricing of Amazon's Elastic Compute Cloud. Users can place bids (above a price set by Amazon) to have computation performed on EC2; jobs that are currently running can be outbid and interrupted. Hence, EC2 spots are ideal for jobs that can be suspended and the results of which are not needed immediately. The goal of this paper was twofold, to understand how the cloud provider sets their prices and to determine which prices users should bid.

The authors present two different types of bidding strategies, one-time bids and persistent bids. One-time bids are submitted once and then exit the system once they fall below the current spot price. The risk with one-time bids is that they be interrupted without completing. Persistent bids are resubmitted in each time period until the job finishes or is manually terminated by the user. This results in longer waiting and completion times. In contrast, one-time bids provide better control over bid completion times. The authors test these strategies to bid for MapReduce jobs. They propose placing a single one-time bid for the Master node, which prevents interruptions and using persistent bidding requests for slave nodes.

Q&A

Q: You talk about both a cloud provider price model and user price model. What if you cannot control the provider's price model? What if you have no knowledge about how Amazon prices? Will your model work?
A: We tried to model how the cloud provider sets a price to get more precise prediction of the spot price. If we do not have any knowledge of how Amazon, then we can still use probability distribution of spot price offered by Amazon to predict future prices. As a result, maybe it will not be as accurate, but it is still doable.

Q: Two questions. Do you provide any estimation or prediction models to the user that is currently bidding? In other words, apart from the current minimum bid, what other information is publicly available? Also in your map reduce model you can reduce your cost by taking some slaves online, but isn't this cost offset by the increased need for storage when the host goes offline?
A: To answer your second questions, for map reduce jobs, if some slave node goes offline, I think the slave nodes will upload some result to the master node. But when they jump off then there may be some results they haven't uploaded to the master node. This will be included in the recovery time. If another slave node takes over for the slave node that fails, then we implement this as a recovery/overhead time in our work. The other slave node will need more time to complete. Can you repeat your first question?

Q: Say I am a bidder, and I want to bid for some containers. I do know the current minimum bid price, but what other information is available to me? Is there an estimation model? For example, what is the probability my job is killed at some time for a given bid? Do you provide information on what the probability of a job being killed is if you bid some price. Say, if I bid 500 dollars I have 60% probability of being killed, if I bid 800 dollars I have 30% of my job being killed.
A: Yes, this information can be calculated by our model. The public information that is provided to users is spot instance prices of the past two months. From this, we can calculate the PDF of the spot price. Then we can calculate the probability by considering the total running time of the job.

Q: There's an assumption that the computation results don't vary in value. For example, the computation results are not going to be useful if the conference is already over. Do you have any thoughts on what affect the value of computation over time would have on the model? Often, the busiest times to bid are more expensive because the results of the computation are more valuable at that time. A real life bidding strategy would have to take that into account the effects of running the job later during the off hours. Do you have any thoughts on how that would affect the bidding strategy?
A: Actually we did not find any correlation between the time and the spot price, because people from all over the world can bid at any time. But we do think that if a lot of people use our bidding strategies then this would affect the spot price. It should make the market efficient. We want to improve this in future work.

Q: How will things change if you consider competitors? That if customers had the choice to select between different providers?
A: This is a good question which we never considered. If we have multiple cloud providers, then the user can have more choices to choose from by comparing the price they offered and the spot price distribution may be more variable. This will complicated model. I think that is an interesting point to study in the future.

Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup

Authors: Hirochika Asai (The University of Tokyo), Yasuhiro Ohara (NTT Communications Corporation)

Paper (pdf)
Public review (pdf)

With the rapidly increasing size of routing tables, we need an efficient approach for IP routing table lookups. In this paper, the authors Poptrie, an IP routing lookup algorithm. The name was chosen because of how their algorithm leverages the popcount instruction and their use of the multiway trie. The authors were able to achieve a lookup rate of 148.8 Mlps (about 6.7 ns per lookup).

Poptrie uses a number of extensions to improve performance and reduce the memory footprint, such as compressing the leaf bit-vector, route aggregation,  and direct pointing (like DXR). Using the leafvec extension, they were able to reduce the memory footprint to less than 1/3. Adding the route aggregation reduces the tree depth. Direct pointing extracts the nodes that corresponds to the most significant s bits, which specifies how many bits should be used as the index to the lookup array.

The authors tested Poptrie on both random and real traffic and compared against other algorithms. In their tests, D18R performed well on random traffic, but did poorly on on real traffic. Conversely, SAIL did poorly on random traffic, but performs well on real traffic. In contrast to both, Poptrie performed well on both random and real traffic patterns. The authors also pointed out that Poptrie is well suited for the future as the number of IPv6 prefixes increases, since it does well on datasets with longer prefixes.

Q&A

Q: Compared to work in the past, the most impressive thing here seems to be that you managed to compress the intermediate nodes and pointers. It seems like the big win is the deletion of all the duplicate space. Yes?
A: Yes. The direct pointing is significant for this. We couldn't see any big differences at shorter prefixes, but we could see very big differences at the deeper prefixes.

Q: Are there any other places such as firewall rules or encryption lookups that would also benefit that would benefit from these kind techniques for deletion of duplication.
A: Yes, I think so. Right now, we are focusing on IP routing table, but could extend this in future work to apply to access control lists, firewalls or string matching.

Q: You're using the pop count instruction in a general purpose processor, it's a standard instruction. You're benefiting a lot from that instruction. Normally, if you need high speed lookups you'd probably use ASICs or FPGAs perhaps. So, couldn't you put more things in the hardware?
A: Yes, this can implemented in hardware, but we focus on the software. Because with the advancement of hypervisors and virtual machine technologies, routing is often implemented in a hypervisor. In that case, we are not using dedicated hardware. This mechanism could be implemented in hardware but our focus is on software.

Q: I wonder if you had tried using memory prefetching to reduce the number of cycles for lookups? It should be able to reduce the number of cycles that are caused by cache misses.
A: The cache misses are the main factor that affects performance. Comparing 5th and 95th percentiles, we can see there are big fluctuations. It's very fast if there are no cache misses, but if there are cache misses we see bad performance. We looked into trying to quantify the number of CPU cache misses, but the kind of CPU we used does not report that. We want to look into that in the future. So instead we focused on measuring CPU cycles. We did try prefetching, but it doesn't help. We only have 6-7 nanoseconds. Since the prefetching requires more CPU cycles and time, it does not work well.