Presente: Ryan Hand
Today's security systems have very limited programability. They can work individually to detect and response to attacks, but are not able to actively collect information, attribute attacks and adjust the configuration based on the observations to prevent future attacks.
We propose an active security architecture. It has a programmable control interface to automate the task of attack detection, data collection, attach attribution and system reconfiguration to react to attacks. The new architecture has four major components: 1) protection: a security infrastructure that can monitor and react to common attacks. 2) sensing: collecting alerts from an variety of sensors such as intrusion detection system or individual firewalls; 2) data collection: in case of a potential attack collecting different data from the whole system, e.g. routers, firewalls, individual devices in the network for the attribution of the attack. 3) adjust: a programmable interface to reconfigure the network to
react to the attack, and monitor future attacks.
Comment:
Q: You said existing systems often leads to a step behind the attacks, but it seems you architecture is also based on the those hard work done by others.
A: Some work has been done on dynamic malware analysis. If it can be done in almost real-time, we can do better job.
Q: What kind of data do you need to do this active security? speculate the datasets that could be useful
A: Probably not this time. Ongoing work..Couldn't comment on that fully right now
Q: Why would a victim host would trust some one to pull the memory?
A: Trust needs to be built between the supervisor and the host
Sunday, November 24, 2013
HotNets' 13: On the Risk of Misbehaving RPKI Authorities
Presenter: Danny Cooper
RPKI is a new security architecture for BGP that can prevent malicious parties from originating routes of IP prefixes that don't belong to them, which are also called prefix and subprefix hijacks. The idea is to build a trusted mapping between the ASes and their IP prefixes.
However serious risks could exist if the RPKI authorities are misconfigured or compromised. This paper explores such possible risks in different aspects, and show that the new architecture gives the authorities (such as the owner of the superset of IP prefixes) arbitrary power to reclaim the IP prefixes unilaterally, while leaving the targeted ASes little power to protect themselves. This problem is even severe if the authority and targeted AS cross international borders.
In conclusion, this study shows that the new architecture brings in a completely new set of problems, which are worth noting by the researchers in this area.
Q: What would happen if not allowing multiple trees while only allow a single root of authority?
A: It doesn't change much as someone can manipulate you in the upper layer
Q: What happen if you have two valid certificate claiming the same segment?
A: Currently it does't provide mechanisms to deal with conflict
Q: Who will be the entities that do the monitoring work?
A: Anyone can run our current monitor tools, universities, institutes.
Saturday, November 23, 2013
Routing/Management Panel discussion
Routing/Management Panel discussion:
Q: John Wroclawski pointed to the main themes in the session: reconfigurability (Merlin), adaptability (RC3), and resilience (Plink) and wondered if any of the three systems could benefit from any of the other themes.
Brent Stephens and Robert Soule both agreed that their systems could benefit from reconfigurability and resilience respectively.
Q John Wroclawski: Would incremental recompilation benefit Merlin?
Robert Soule: That is definitely something we want to look at. If we look at subset of modified networks and policies, maybe we can more quickly adapt to changes in network configuration.
Q: John Wroclawski pointed to the main themes in the session: reconfigurability (Merlin), adaptability (RC3), and resilience (Plink) and wondered if any of the three systems could benefit from any of the other themes.
Brent Stephens and Robert Soule both agreed that their systems could benefit from reconfigurability and resilience respectively.
Q John Wroclawski: Would incremental recompilation benefit Merlin?
Robert Soule: That is definitely something we want to look at. If we look at subset of modified networks and policies, maybe we can more quickly adapt to changes in network configuration.
HotNets' 13: How to Improve Your Network Performance by Asking Your Provider for Worse Service
Presented by: Radhika Mittal, UC Berkeley
This paper makes two main observations to motivate its designs. First, network providers typically over-provision their networks (for resiliency). Second TCP's congestion control is cautious and ramps up slowly in Slow Start. These two behaviors interact adversely, and in an Internet where most flows do not leave slow start, waste capacity.
To address this, the authors step back and look at the goals of congestion control: To fill the pipe for high throughput, and to do no harm to other flows. Traditionally, a single mechanism achieves these two conflicting goals. Their system (RC'3)'s key insight is decoupling the two: Run regular TCP at high priority, and fill up the pipe at a lower priority. They call this worse quality of service (WQoS) and claim that the already-present priority queuing mechanisms in switches can be re-purposed for this task, by providing several layers of worse quality of service.
Next, they develop an idealized mathematical model to analyze the performance gains of RC3 relative to vanilla TCP as a function of flow size. Broadly, for flow sizes less than the initial window, RC3 gives no gains. For flow sizes between the initial window and the bandwidth-delay product, RC3's gains increase monotonically and then start falling off beyond the bandwidth-delay product. They also observe that the maximum possible gain increases with increasing bandwidth-delay product, making it future-proof.
RC3's design has two control loops: the standard TCP control loop, and RC3's own control loop. RC3 tries to minimize overlap between packets sent by the two control loops by transmitting the flow's packets in reverse order for RC3's control loop, and in the standard forward order for TCP's control loop. To make this scheme feasible with a fixed number of priority levels, RC3 transmits (say) 4 packets at priority level 1, 40 at priority level 2, 400 at level 3, and so on, until it crosses over into the standard loop's transmissions. Furthermore, to ensure flow-level fairness, every flow gets to transmit exactly the same number of packets at each priority level, ensuring that long flows can't squeeze out the shorter ones. They leave loss recovery to TCP's loss recovery mechanism, but require SACK to selectively acknowledge packets that are received through RC3's control loop.
Their evaluations show that their performance gains track their theoretical model well. The authors also compare RC3 with increasing the Initial Window, RCP, and traditional QoS and see that it improves flow completion times in all cases.
Q&A
1. How is this different from pFabric?
Ans: They focused their design largely on the data-center context. Our gains, on the other hand, are much more pronounced in wide-area settings with high bandwidth-delay products, and much lesser
in the data-center context due to smaller bandwidth-delay products.
2. Does the application set priorities for the packets?
Ans: No, the OS does this in the kernel. It happens automatically and it ensures that the longer flows do not starve the shorter ones.
3. Floyd and Allman proposed a similar mechanism a while back. They had trouble implementing this using the scheduler mechanisms in Linux.
Ans: We implemented it in Linux and it worked fine for us.
4. What about per-packet delay? Since RC3 sends the initial window + 4 + 40 + ... packets in one burst, doesn't it lead to large per-packet delays for other flows that are not interested in flow completion times, but individual per-packet delays?
Ans: The flows interested in per-packet delay would be sent at the same priority as standard TCP. Hence their packets would pre-empt packets that are sent at the lower priority levels by RC3, and would only compete with packets sent by the standard TCP control loop, just like they would today.
5. Did you explore any congestion control for the RC3 loop itself? Instead of sending all the packets at any priority level all at once?
Ans: No. We stuck with this idea because it was simple and worked.
6. Let's say two users want to start a connection simultaneously. Does RC3 give any gains to either user over standard TCP?
Ans: RC3 doesn't do any worse than TCP in the worst case. But if there is enough spare capacity for both users to fill the pipe quickly, RC3 will allow both flows to complete faster than standard TCP.
This paper makes two main observations to motivate its designs. First, network providers typically over-provision their networks (for resiliency). Second TCP's congestion control is cautious and ramps up slowly in Slow Start. These two behaviors interact adversely, and in an Internet where most flows do not leave slow start, waste capacity.
To address this, the authors step back and look at the goals of congestion control: To fill the pipe for high throughput, and to do no harm to other flows. Traditionally, a single mechanism achieves these two conflicting goals. Their system (RC'3)'s key insight is decoupling the two: Run regular TCP at high priority, and fill up the pipe at a lower priority. They call this worse quality of service (WQoS) and claim that the already-present priority queuing mechanisms in switches can be re-purposed for this task, by providing several layers of worse quality of service.
Next, they develop an idealized mathematical model to analyze the performance gains of RC3 relative to vanilla TCP as a function of flow size. Broadly, for flow sizes less than the initial window, RC3 gives no gains. For flow sizes between the initial window and the bandwidth-delay product, RC3's gains increase monotonically and then start falling off beyond the bandwidth-delay product. They also observe that the maximum possible gain increases with increasing bandwidth-delay product, making it future-proof.
RC3's design has two control loops: the standard TCP control loop, and RC3's own control loop. RC3 tries to minimize overlap between packets sent by the two control loops by transmitting the flow's packets in reverse order for RC3's control loop, and in the standard forward order for TCP's control loop. To make this scheme feasible with a fixed number of priority levels, RC3 transmits (say) 4 packets at priority level 1, 40 at priority level 2, 400 at level 3, and so on, until it crosses over into the standard loop's transmissions. Furthermore, to ensure flow-level fairness, every flow gets to transmit exactly the same number of packets at each priority level, ensuring that long flows can't squeeze out the shorter ones. They leave loss recovery to TCP's loss recovery mechanism, but require SACK to selectively acknowledge packets that are received through RC3's control loop.
Their evaluations show that their performance gains track their theoretical model well. The authors also compare RC3 with increasing the Initial Window, RCP, and traditional QoS and see that it improves flow completion times in all cases.
Q&A
1. How is this different from pFabric?
Ans: They focused their design largely on the data-center context. Our gains, on the other hand, are much more pronounced in wide-area settings with high bandwidth-delay products, and much lesser
in the data-center context due to smaller bandwidth-delay products.
2. Does the application set priorities for the packets?
Ans: No, the OS does this in the kernel. It happens automatically and it ensures that the longer flows do not starve the shorter ones.
3. Floyd and Allman proposed a similar mechanism a while back. They had trouble implementing this using the scheduler mechanisms in Linux.
Ans: We implemented it in Linux and it worked fine for us.
4. What about per-packet delay? Since RC3 sends the initial window + 4 + 40 + ... packets in one burst, doesn't it lead to large per-packet delays for other flows that are not interested in flow completion times, but individual per-packet delays?
Ans: The flows interested in per-packet delay would be sent at the same priority as standard TCP. Hence their packets would pre-empt packets that are sent at the lower priority levels by RC3, and would only compete with packets sent by the standard TCP control loop, just like they would today.
5. Did you explore any congestion control for the RC3 loop itself? Instead of sending all the packets at any priority level all at once?
Ans: No. We stuck with this idea because it was simple and worked.
6. Let's say two users want to start a connection simultaneously. Does RC3 give any gains to either user over standard TCP?
Ans: RC3 doesn't do any worse than TCP in the worst case. But if there is enough spare capacity for both users to fill the pipe quickly, RC3 will allow both flows to complete faster than standard TCP.
Hotnets '13: Plinko: Building Provably Resilient Forwarding Tables
Authors: Brent Stephens, Alan L. Cox, Scott Rixner (Rice University)
The Internet is designed to be robust with redundant paths between nodes so that data can be delivered in spite of failures. However, most networks today drop data, at least for some time, when a link fails. This paper introduces a new forwarding model, Plinko, which can tolerate up to t failures with no packet drops.
Plinko's algorithm initially chooses a set of default routes for all source/destination pairs. Once these routes are chosen, the algorithm iteratively increases resilience by installing new alternate routes to protect the paths built in the previous round. The main challenge with this approach is that the backup routes can end up forming loops. Plinko solves this problem by performing matching on the reverse path of a packet, which is accumulated in the packet's header.
In order to reduce the amount of state that needs to be stored, Plinko also utilizes compression, by grouping together rules with the same output path. A good feature of Plinko's compression is that the compression ratios achieved are much higher for larger numbers of nodes and increased resiliency requirements, where the state would also be correspondingly higher. This makes Plinko pretty scalable; it can be utilized to build a 4-resilient network for topologies with up to about ten thousand hosts.
Q) In the presence of failures, we may want to prioritize some paths over others. How will this affect you?
A) Perhaps we can use a reservation or bandwidth aware version of Plinko. Typically, in datacenters, you only need best-effort.
The Internet is designed to be robust with redundant paths between nodes so that data can be delivered in spite of failures. However, most networks today drop data, at least for some time, when a link fails. This paper introduces a new forwarding model, Plinko, which can tolerate up to t failures with no packet drops.
Plinko's algorithm initially chooses a set of default routes for all source/destination pairs. Once these routes are chosen, the algorithm iteratively increases resilience by installing new alternate routes to protect the paths built in the previous round. The main challenge with this approach is that the backup routes can end up forming loops. Plinko solves this problem by performing matching on the reverse path of a packet, which is accumulated in the packet's header.
In order to reduce the amount of state that needs to be stored, Plinko also utilizes compression, by grouping together rules with the same output path. A good feature of Plinko's compression is that the compression ratios achieved are much higher for larger numbers of nodes and increased resiliency requirements, where the state would also be correspondingly higher. This makes Plinko pretty scalable; it can be utilized to build a 4-resilient network for topologies with up to about ten thousand hosts.
Q) In the presence of failures, we may want to prioritize some paths over others. How will this affect you?
A) Perhaps we can use a reservation or bandwidth aware version of Plinko. Typically, in datacenters, you only need best-effort.
Friday, November 22, 2013
Hotnets '13: Managing the Network with Merlin
Authors: Robert Soulé, Shrutarshi Basu, Robert Kleinberg, Emin Gün Sirer, Nate Foster (Cornell University)
Presented by: Robert Soulé
Enforcing network management policies is complicated using current techniques. A lot of different diverse machines have to be configured in multiple ways to enforce even relatively simple policies. When these rules need to be modified, it is even harder to reason about the effect of these changed rules upon the different devices and upon the network as a whole. Further, current techniques assume that networks belong to single administrative authorities and do not allow delegation of authority.
The paper addresses the above challenges. First, in order to make policies easier to express and easier to implement, the paper offers an abstraction for global networking policies using a high-level declarative language, which is then mapped to a constraint problem. Second, the paper introduces a framework where authority can be delegated to "tenants". To make sure that tenants are actually obeying their constraints, the paper also introduces a technique for verification.
Policies are expressed using a combination of logical predicates, regular expressions and bandwidth constraints, which can allow the administrator to specify the intended behavior of the network at a high level of abstraction. A compiler then evaluates these policies and generates the code. The problem is then mapped into a constraint problem using NFA, which is solved using linear programming.
To evaluate Merlin, the authors ran a TCP trace and a UDP trace in two network configurations - one with Merlin and another without. They noted that the TCP trace performed much better in the configuration with Merlin (which was configured to grant higher priority to TCP). The authors also evaluated Merlin on a testbed with 140 nodes to check how well the system scales. They noted that it took 6 seconds to generate and run the linear programming model, which they think is fairly low.
Q) What happens when there are failures?
A) One possible approach is to model the failures as input to the constraint problem.
Q) How scalable is Merlin? Constraint solving may not scale well with a higher number of devices and with different types of devices?
A) We looked at networks with 140 nodes. We think it's fairly good to look at numbers of this scale. Google B4 was doing the same, but they used only a dozen classes of traffic, whereas we handle about a hundred classes of traffic on 140 different nodes. Scaling to even larger sizes may be possible by coming up with engineering approaches to further reduce the time to solve the linear programming problem. Alternately, perhaps we can adopt appoximation solutions which could result in much faster run times at a small accuracy tradeoff
Q) What does the NFA abstraction buy you?
A) We are language researchers and want to program in abstractions. We are getting powerful abstractions such as verification of policies that are farmed out to tenants, something that nobody has done before.
Presented by: Robert Soulé
Enforcing network management policies is complicated using current techniques. A lot of different diverse machines have to be configured in multiple ways to enforce even relatively simple policies. When these rules need to be modified, it is even harder to reason about the effect of these changed rules upon the different devices and upon the network as a whole. Further, current techniques assume that networks belong to single administrative authorities and do not allow delegation of authority.
The paper addresses the above challenges. First, in order to make policies easier to express and easier to implement, the paper offers an abstraction for global networking policies using a high-level declarative language, which is then mapped to a constraint problem. Second, the paper introduces a framework where authority can be delegated to "tenants". To make sure that tenants are actually obeying their constraints, the paper also introduces a technique for verification.
Policies are expressed using a combination of logical predicates, regular expressions and bandwidth constraints, which can allow the administrator to specify the intended behavior of the network at a high level of abstraction. A compiler then evaluates these policies and generates the code. The problem is then mapped into a constraint problem using NFA, which is solved using linear programming.
To evaluate Merlin, the authors ran a TCP trace and a UDP trace in two network configurations - one with Merlin and another without. They noted that the TCP trace performed much better in the configuration with Merlin (which was configured to grant higher priority to TCP). The authors also evaluated Merlin on a testbed with 140 nodes to check how well the system scales. They noted that it took 6 seconds to generate and run the linear programming model, which they think is fairly low.
Q) What happens when there are failures?
A) One possible approach is to model the failures as input to the constraint problem.
Q) How scalable is Merlin? Constraint solving may not scale well with a higher number of devices and with different types of devices?
A) We looked at networks with 140 nodes. We think it's fairly good to look at numbers of this scale. Google B4 was doing the same, but they used only a dozen classes of traffic, whereas we handle about a hundred classes of traffic on 140 different nodes. Scaling to even larger sizes may be possible by coming up with engineering approaches to further reduce the time to solve the linear programming problem. Alternately, perhaps we can adopt appoximation solutions which could result in much faster run times at a small accuracy tradeoff
Q) What does the NFA abstraction buy you?
A) We are language researchers and want to program in abstractions. We are getting powerful abstractions such as verification of policies that are farmed out to tenants, something that nobody has done before.
HotNets '13: Cross-Path Inference Attacks on Multipath TCP
Authors: Zubair Shafiq (Michigan State University), Franck Le, Mudhakar Srivatsa (IBM Research), Alex X. Liu (Michigan State University).
Multipath TCP (MPTCP) is an optimization that allows traffic between two endpoints to take advantage of multiple paths, thus increasing the utilization of overall bandwidth available. The three design objectives of MPTCP are threefold:
1. Increase throughput
2. ‘Do no harm’ by not degrading the performance of single-path path flows sharing the network
3. Balance congestion by moving traffic off congested paths
This paper presents an attack, not on any of these design objectives, but on another implicit design goal, which is that the routing strategy shouldn’t otherwise compromise the privacy of the user or the network operator. In short, this paper presents an attack on MPTCP that allows one ISP to probe the precise performance characteristics of other competing ISPs on the network. This information may be considered proprietary. Although a similar attack is already possible with ordinary single-path TCP, the attack can only be launched from nodes lying on the routed path, whereas with MPTCP the attack can be launched by nodes off the path.
The attack presented in this paper was demonstrated on a small four-node network of hosts running a Linux kernel patched with an existing MPTCP implementation. The attack allows one node on the network to directly infer the throughput of a single-path TCP flow spanning the other three nodes, with approximately 90% accuracy.
HotNets '13: CryptoBook
[PDF] CryptoBook: An Architecture for Privacy Preserving Online Identities
Authors: John Maheswaran, David Isaac Wolinsky, Bryan Ford (Yale University).
CryptoBook attempts to provide cross-site authentication in a privacy preserving way. Cross-site authentication is increasingly widespread: users can use OAuth and their Facebook accounts to log in to Pinterest, StackOverflow, etc. The reasons why users prefer this form of authentication are clear: they only have to maintain one account (their Facebook account), and don't have to sign up or create passwords at every other site.
The problem is that every thing a user does on a third party site can now be associated with their Facebook count, which is often not what the user wants.
CryptoBook acts as an intermediate login service. It is presented as a second login option, next to "Log In with Facebook" for example. Facebook issues an OAuth token to the intermediate CryptoBook service, rather than to the visited site (e.g., Wikipedia). The CryptoBook service vouches that the user's identity *does* correspond to *a* Facebook account, without revealing which one. In fact, the user provides a list of other Facebook accounts to act as the anonymity set - the website does not learn which of these users is signing in.
CryptoBook's backend consists of a collection of federated servers, of which only one (not necessarily a majority) needs to follow the protocol in order to maintain security and privacy. Standard ring signatures are used so that the token is provably signed by one user among this set, but it could be any of them.
Q. Why go through the effort of using crypto? Why not have the user's browser simply sign up, automatically, on their behalf, to various websites?
A. Part of the function of cross-site authentication is to protect the website against anonymous user accounts. In other words, the website may not want to accept anonymous signups, but instead only accepts legitimate Facebook accounts.
Comment: It was suggested that this work may duplicate existing work, as many state governments are busy implementing very similar things.
Q. What happens when a Facebook account is deactivated?
A. The token can be revoked. This could conceivably introduce a correlation attack.
Authors: John Maheswaran, David Isaac Wolinsky, Bryan Ford (Yale University).
CryptoBook attempts to provide cross-site authentication in a privacy preserving way. Cross-site authentication is increasingly widespread: users can use OAuth and their Facebook accounts to log in to Pinterest, StackOverflow, etc. The reasons why users prefer this form of authentication are clear: they only have to maintain one account (their Facebook account), and don't have to sign up or create passwords at every other site.
The problem is that every thing a user does on a third party site can now be associated with their Facebook count, which is often not what the user wants.
CryptoBook acts as an intermediate login service. It is presented as a second login option, next to "Log In with Facebook" for example. Facebook issues an OAuth token to the intermediate CryptoBook service, rather than to the visited site (e.g., Wikipedia). The CryptoBook service vouches that the user's identity *does* correspond to *a* Facebook account, without revealing which one. In fact, the user provides a list of other Facebook accounts to act as the anonymity set - the website does not learn which of these users is signing in.
CryptoBook's backend consists of a collection of federated servers, of which only one (not necessarily a majority) needs to follow the protocol in order to maintain security and privacy. Standard ring signatures are used so that the token is provably signed by one user among this set, but it could be any of them.
Q. Why go through the effort of using crypto? Why not have the user's browser simply sign up, automatically, on their behalf, to various websites?
A. Part of the function of cross-site authentication is to protect the website against anonymous user accounts. In other words, the website may not want to accept anonymous signups, but instead only accepts legitimate Facebook accounts.
Comment: It was suggested that this work may duplicate existing work, as many state governments are busy implementing very similar things.
Q. What happens when a Facebook account is deactivated?
A. The token can be revoked. This could conceivably introduce a correlation attack.
HotNets'13: Patch Panels in the Sky: A Case for Free-Space Optics in Data Centers.
Navid Hamed Azimi, Himanshu Gupta, Vyas Sekar, Samir Das (Stony Brook University).
Paper: http://conferences.sigcomm.org/hotnets/2013/papers/hotnets-final129.pdf
Presenter: Navid Hamed Azimi
The authors propose that all data center networking (between ToR switches) must be free-space optical (FSO) links, which has advantages in that it can potentially be low-cost and high-performance, but it comes with its own challenges. Today's FSO devices are expensive, but it's because they are designed for outdoor environments. One main challenge is that the laser from FSO diverges, but the authors engineered a way around it (see paper for more details). Another challenge is line-of-sight requirement for FSO, which is problematic for all-to-all network connectivity. The authors use a mirror on the ceiling of the data centre to overcome this limitation.
What's cool is that they actually built a small prototype of this in their lab and verified they were able to sustain communication between two hosts at 1Gb/s.
Q: I like the idea, but what happens if I scale to 10Gb/s and 40Gb/s? Will I run into alignment issues?
A: We consulted an optics person who said there shouldn't be any issue.
Q: Why can't I just put them on the server NICs instead of putting FSO on the ToR switches?
A: There will be line-of-sight issues.
Q: I worry about vibration issues due to the mirror. Can you talk about fault-tolerance?
A: We don't know exactly but we think it shouldn't be an issue.
Q: Dynamic links require mechanics to turn mirrors and a feedback control system, right?
A: Yes.
Q: If you only have three choices for mirror alignment, this isn't that flexible, is it?
A: You can add as many mirrors as there is space on the ToR switch.
Q: What is the pass-through loss?
A: 2--3%.
Panel:
Q: Now we cannot have lights in our data center?
[Laughter]
Q: MCP and fountain codes are two competing solutions to incast. Can each of you argue why your solution is the best? Isn't incast the main problem you are trying to solve?
A:
Trevis author: Incast isn't the only problem. There are other problems which I can argue qualitatively.
MCP author: MCP flow rates are deadline driven, so there could be bandwidth headroom for new flows (incast-like).
Comment from Trevis author to MCP author: Do consider what happens during barrier-synchronized workloads, which is the worst-case scenario for incast.
Q: Do you have a combinatorial explosion on the number of mirrors if you have lot of racks?
A: Fanout multiplies with the number of mirrors.
Q: What is the frequency of the link?
A: Single-mode 1300nm wavelength.
Comment on DC research from [anonymous]: We can have lot of coding mechanisms in a data center, particularly layer 1 and layer 2. Can we do CDMA? Are we doing too much SDN?
Q: Yesterday we had someone talk about blowing up a DC into individual pieces. If we take a coding perspective, we might have a different architecture. What is the cost of a particular design point?
A: I don't know what the best design is, but I see the opportunity.
A: We have preconception about computers (as mainframes, DC, PC, etc.) but what we really have is information flows, interacting with each other and generating new information. I think we should go deep in that direction too.
Q: We have low-latency as a requirement, but there are fundamental latency limits. For instance, we cannot steer mirrors fast compared to DC RTTs. Congestion control is also mostly reactive. Can you comment on the limits of your approaches?
A: For large flows, milliseconds is fine.
A: Depends on the application. If you care about consistency, latency probably doesn't matter, but we will need to explore.
HotNets'13: Trevi: Watering Down Storage Hotspots with Cool Fountain Codes.
George Parisis, Toby Moncaster, Anil Madhavapeddy, Jon Crowcroft (Computer Laboratory, University of Cambridge).
Presented by George Parisis.
Paper: http://conferences.sigcomm.org/hotnets/2013/papers/hotnets-final48.pdf
Commodity storage applications still use TCP, which has its own problems: Incast, lack of multicast support, no multipath support. The paper introduces a system called Trevis, a transport protocol specially designed for storage applications that uses fountain codes to get around TCP's limitations. In Trevis, (fountain coded) symbols are first-class citizens of transmission. The key features of Trevis are: (a) receiver-based flow control, (b) fountain-coded symbols, (c) support for multicasting, and (d) multi-sourcing to fetch data from multiple replicas.
What is interesting about this paper is that it got me thinking along the lines of designing a transport with application intent (fetching content) in mind, instead of metrics we usually associate with application performance (flow completion times).
Q: Fountain codes have some limitations (e.g. it can encode only limited message length) before it has serious overheads. What do you do about this?
A: The messages are typically small in size -- limited by the storage system's blob size, which is typically bounded (~4MB) and configurable.
Q: You are combining error recovery with congestion control. Is this the right thing to do?
A: I don't know, and I don't have numbers to show (yet).
Q: Our benchmarks show Reed-Solomon codes takes 5--10s.
A: This isn't Reed-Solomon. Fountain codes are "online" so you can do it on the fly.
HotNets'13: Towards Minimal-Delay Deadline-Driven Data Center TCP
Li Chen, Shuihai Hu, Kai Chen (HKUST), Haitao Wu (Microsoft Research Asia), Danny H.K. Tsang (HKUST).
Paper: http://conferences.sigcomm.org/hotnets/2013/papers/hotnets-final92.pdf
The key idea in the paper is formulating the problem explicitly as a stochastic network optimization problem and derived an end-to-end scheme using a standard technique called "drift plus penalty method." See paper for more details.
What I think is interesting about the paper is that the authors formulated the problem explicitly and derived the end-to-end window update algorithm to achieve the optimal rates needed to meet as many flow deadlines as possible.
Q: You are adapting rate over time and starting rate. Have you quantified the benefit of each modification's? How much of the benefit is just due to the right starting rate?
A: It has to start at expected rate, or dynamics would take a long time to converge. If flows just stick to starting rate, the network will be unstable.
Q: Is the objective to maximize the number of deadlines met?
A: No, it is to minimize per-packet delays.
Q: Recent works look at flow-level metrics (mean FCT, etc.). What impact do these metrics have on application performance (e.g. MapReduce)?
A: Most work in this area is on flow-level performance, so we used the same. For specific applications, I think there is room for improvement.
Q: In your graphs, what is "optimal"? Why is it different from the line labeled "throughput"?
A: Optimal is computed centrally using per-hop information. It is hard for a stochastic program to always operate at the optimal point -- we just proved convergence to optimality in the stochastic sense.
Paper: http://conferences.sigcomm.org/hotnets/2013/papers/hotnets-final92.pdf
Data center workloads have flows with diverse deadlines as recognized by earlier work such as D3, D2TCP, PDQ, and pFabric. Some of these approaches are ad-hoc: For instance, DCTCP maintains shallow queues which indirectly affects flow completion times; while others require intrusive hardware changes (e.g. D3 and pFabric). This paper presents MCP, which is an end-to-end congestion control algorithm to determine the "right" rates to meet flow deadlines, while being readily deployable.
The key idea in the paper is formulating the problem explicitly as a stochastic network optimization problem and derived an end-to-end scheme using a standard technique called "drift plus penalty method." See paper for more details.
What I think is interesting about the paper is that the authors formulated the problem explicitly and derived the end-to-end window update algorithm to achieve the optimal rates needed to meet as many flow deadlines as possible.
Q: You are adapting rate over time and starting rate. Have you quantified the benefit of each modification's? How much of the benefit is just due to the right starting rate?
A: It has to start at expected rate, or dynamics would take a long time to converge. If flows just stick to starting rate, the network will be unstable.
Q: Is the objective to maximize the number of deadlines met?
A: No, it is to minimize per-packet delays.
Q: Recent works look at flow-level metrics (mean FCT, etc.). What impact do these metrics have on application performance (e.g. MapReduce)?
A: Most work in this area is on flow-level performance, so we used the same. For specific applications, I think there is room for improvement.
Q: In your graphs, what is "optimal"? Why is it different from the line labeled "throughput"?
A: Optimal is computed centrally using per-hop information. It is hard for a stochastic program to always operate at the optimal point -- we just proved convergence to optimality in the stochastic sense.
Hotnets '13: On Consistent Updates in Software-defined Networks.
Authors: Ratul Mahajan (Microsoft Research), Roger Wattenhofer (ETH).
They argue that a problem with SDN may be in the area of transitions between current states and future states during rule changes. When the SDN controller wants to change some rules and sends some updates into the network, which is asynchronous, the state does not change atomically and may result in things like network loops during the transition.
One approach is to try to make the state transition atomic by propagating version numbers and don't tell the nodes to start using a version until all nodes have received it. This slows down updates when some nodes don't aren't affected by the rule change. The way of assuming all nodes rules are dependent on one another gives stronger packet coherence, but if we instead targeted only the nodes that have dependencies on one another we can try to achieve minimal SDN updates.
It is possible to find a minimal set of nodes that need to be involved for a given set of properties for various kinds of consistency, but the difficulty is not just how to compute new rules, but how to get from the current configuration to the new configuration gracefully.
Suppose you have a set of new rules and run it through an update plan generator that creates an update DAG that defines when and where various rule updates need to be applied. If the graph is cyclic the cycle has to be broken and then an optimizer can reduce the graph into a smaller set of operations. At this point, the executor can then apply the updates.
Q: There have been a couple of papers looking at program synthesis. You can view these as instantiations of your update planner. Can you say more about what is in the planner and how it works?
A: We only have it for some kind of properties. In this paper we only look at loop freedom. It doesn't work in general for any property that you define. For us we want to look at specific properties and understand them better.
Q: Work has been done in this area for distributed networks (pre-SDN). Is there a formal version of how to map the distributed approaches to the central approach.
A: We don't know yet. At the surface they look different because you can exactly control which node you are sending an update to, which isn't true in the distributed case. It is possible those algorithms can be used in some p
Q: Is there a small set of properties that are broadly useful enough or do you have to fall back to something like version numbers for the general case?
A: I wouldn't characterize the version numbers as a general solution, because they don't work universally. I would choose the fastest thing you can do that has the correctness property.
Observation (from audience): Depending on the application people go with different data consistently problems. Maybe all you care about is looping.
They argue that a problem with SDN may be in the area of transitions between current states and future states during rule changes. When the SDN controller wants to change some rules and sends some updates into the network, which is asynchronous, the state does not change atomically and may result in things like network loops during the transition.
One approach is to try to make the state transition atomic by propagating version numbers and don't tell the nodes to start using a version until all nodes have received it. This slows down updates when some nodes don't aren't affected by the rule change. The way of assuming all nodes rules are dependent on one another gives stronger packet coherence, but if we instead targeted only the nodes that have dependencies on one another we can try to achieve minimal SDN updates.
It is possible to find a minimal set of nodes that need to be involved for a given set of properties for various kinds of consistency, but the difficulty is not just how to compute new rules, but how to get from the current configuration to the new configuration gracefully.
Suppose you have a set of new rules and run it through an update plan generator that creates an update DAG that defines when and where various rule updates need to be applied. If the graph is cyclic the cycle has to be broken and then an optimizer can reduce the graph into a smaller set of operations. At this point, the executor can then apply the updates.
Q: There have been a couple of papers looking at program synthesis. You can view these as instantiations of your update planner. Can you say more about what is in the planner and how it works?
A: We only have it for some kind of properties. In this paper we only look at loop freedom. It doesn't work in general for any property that you define. For us we want to look at specific properties and understand them better.
Q: Work has been done in this area for distributed networks (pre-SDN). Is there a formal version of how to map the distributed approaches to the central approach.
A: We don't know yet. At the surface they look different because you can exactly control which node you are sending an update to, which isn't true in the distributed case. It is possible those algorithms can be used in some p
Q: Is there a small set of properties that are broadly useful enough or do you have to fall back to something like version numbers for the general case?
A: I wouldn't characterize the version numbers as a general solution, because they don't work universally. I would choose the fastest thing you can do that has the correctness property.
Observation (from audience): Depending on the application people go with different data consistently problems. Maybe all you care about is looping.
Hotnets '13: Software Defined Networking II: Panel Discussion
Q: Is there really a need to support every single queuing mechanism in SDN? Seems to rich? What is the minimal instruction set, current solution seems to complicated.
Anirudh: Several queue management schemes have non-trivial logic, most of these share little logic. It is a better approach to optimize control flow for all of them independently. Not sure which instruction set we will end up with.
Q: Can you also verify queue management and processing steps?
Mihai: Not looked into it yet, but why not.
Q: Not so much the instruction set is the main cost factor but rather the hardware gadgets. Other costs come with managing the flexibility at all (someone has to make sure program is verified). Maybe it should be the next step to articulate and quantify these costs. What do you think is expensive and what not?
Anirudh: Yes there is a need to quantify this. No idea on strong incentives for deployment yet.
Q: Have you thought about underlying hardware primitives that are needed for implementing or is general purpose hardware enough?
Ratul: Support from switches could help (e.g. if the switch tells neighbors when done after update).
Q: Instead of unrolling loops could you just look at the loop invariant? The programmer does what they want in the loop but just states the invariants. Have you seen code that is simple enough to do this?
Mihai: It depends in the invariant and the loop, but there is not a lot of algorithms in the data plane yet so this is still ongoing research.
Anirudh: Several queue management schemes have non-trivial logic, most of these share little logic. It is a better approach to optimize control flow for all of them independently. Not sure which instruction set we will end up with.
Q: Can you also verify queue management and processing steps?
Mihai: Not looked into it yet, but why not.
Q: Not so much the instruction set is the main cost factor but rather the hardware gadgets. Other costs come with managing the flexibility at all (someone has to make sure program is verified). Maybe it should be the next step to articulate and quantify these costs. What do you think is expensive and what not?
Anirudh: Yes there is a need to quantify this. No idea on strong incentives for deployment yet.
Q: Have you thought about underlying hardware primitives that are needed for implementing or is general purpose hardware enough?
Ratul: Support from switches could help (e.g. if the switch tells neighbors when done after update).
Q: Instead of unrolling loops could you just look at the loop invariant? The programmer does what they want in the loop but just states the invariants. Have you seen code that is simple enough to do this?
Mihai: It depends in the invariant and the loop, but there is not a lot of algorithms in the data plane yet so this is still ongoing research.
Hotnets '13: No Silver Bullet: Extending SDN to the Data Plane
Anirudh Sivaraman, Keith Winstein, Suvinay Subramanian, Hari Balakrishnan (MIT CSAIL)
Speaker: Anirudh Sivaraman
In the past, several queue-management and scheduling algorithms for different scenarios have been proposed. Among these are RED, and more recently XCP, RCP, and PDQ. All of these optimize for different objectives and are effective and suitable for their specifc field. The idea of this work is to apply principles of SDN to the data plane in order to find a more flexible and general solution instead of implementing even more different scheduling and queueing schemes. This would allow one to optimize for different networks and different objectives like low latency, high bandwidth or low loss independently of the actual application and the operating system in a more dynamic manner.
The paper works on quantifying the non-universality of existing in-network methods. In particular, the authors look at three different queuing and scheduling schemes, namingly CoDel+FCFS, CoDel+FQ, Bufferbloat+FQ which again all are well applicable for different distinct objectives. Additonally, three different traffic types are taken into consideration: bulk transfers, web traffic (optimize for completion time), and interactive communication. In essence, since the selection of the right schemes, highly depends on various factors, mainly the underlying network and the application, there is no silverbullet solution in terms of a single good network queueing and scheduling configuration.
To overcome this problem, it is proposed to architect the data plane itself for flexibility and extendability in order use different schemes dynamically. This means that network operators should be able to dynamically, based on rules, specify the scheduling and queuing logic by getting an interface to the data plane of the switch exposing the head and tail of the queue. This approach relies on hardware adaption, customized I/O interfaces, state maintenance and a domain-specific instruction set. The hardware side is implemented using a FPGA attached to the switch. The instruction set is put in place to express control flow and implement functionality that is not available in the hardware directly. In conclusion the work proposes an open interface for queuing and scheduling that is portable across vendors, which is a significant step moving towards a programmable data plane.
Q: The methodology of proving seems odd. They don’t seem to prove the non existence of a silver bullet.
A: We tried 3 schemes that are typical. Yes, there could be other ones that we did not work on. We believe these schemes are representative.
Q: Thinking about Click (being one way of doing sdn) … can’t all this be done in Click?
A: Click is purely a software router. Nobody uses it in production. We wanted to work with actual hardware for performance and deployability in real networks.
Q: Instead of specifying all the logic, why don’t you use existing schemes in hardware and parameterize them?
A: Believe, the better approach is to expose API and programmability instead of parameterizing existing.
Q: Could you compare this to FCP (flexible control plane - specifies set of operations on the forwarding plane)?
A: Not aware of this work.
Q: What is the usage scenario for this approach? Just programmable dataplane? Adapt scheduling and queuing based on time (based on workload)? Every single packet possibly treated differently?
A: Our system can support either of these due to its minimal interface.
Q: There have been approaches doing this at the network edge (e.g. Fabric). What is the motivation to have two different architectures? Isn’t processing at the edge more the silver bullet?
A: No, if there are bottlenecks in the network core; if at the edge then possibly.
Q: If a bottleneck is in the core, can the edge identify and transfer control to the core?
A: Possibly.
Speaker: Anirudh Sivaraman
In the past, several queue-management and scheduling algorithms for different scenarios have been proposed. Among these are RED, and more recently XCP, RCP, and PDQ. All of these optimize for different objectives and are effective and suitable for their specifc field. The idea of this work is to apply principles of SDN to the data plane in order to find a more flexible and general solution instead of implementing even more different scheduling and queueing schemes. This would allow one to optimize for different networks and different objectives like low latency, high bandwidth or low loss independently of the actual application and the operating system in a more dynamic manner.
The paper works on quantifying the non-universality of existing in-network methods. In particular, the authors look at three different queuing and scheduling schemes, namingly CoDel+FCFS, CoDel+FQ, Bufferbloat+FQ which again all are well applicable for different distinct objectives. Additonally, three different traffic types are taken into consideration: bulk transfers, web traffic (optimize for completion time), and interactive communication. In essence, since the selection of the right schemes, highly depends on various factors, mainly the underlying network and the application, there is no silverbullet solution in terms of a single good network queueing and scheduling configuration.
To overcome this problem, it is proposed to architect the data plane itself for flexibility and extendability in order use different schemes dynamically. This means that network operators should be able to dynamically, based on rules, specify the scheduling and queuing logic by getting an interface to the data plane of the switch exposing the head and tail of the queue. This approach relies on hardware adaption, customized I/O interfaces, state maintenance and a domain-specific instruction set. The hardware side is implemented using a FPGA attached to the switch. The instruction set is put in place to express control flow and implement functionality that is not available in the hardware directly. In conclusion the work proposes an open interface for queuing and scheduling that is portable across vendors, which is a significant step moving towards a programmable data plane.
Q: The methodology of proving seems odd. They don’t seem to prove the non existence of a silver bullet.
A: We tried 3 schemes that are typical. Yes, there could be other ones that we did not work on. We believe these schemes are representative.
Q: Thinking about Click (being one way of doing sdn) … can’t all this be done in Click?
A: Click is purely a software router. Nobody uses it in production. We wanted to work with actual hardware for performance and deployability in real networks.
Q: Instead of specifying all the logic, why don’t you use existing schemes in hardware and parameterize them?
A: Believe, the better approach is to expose API and programmability instead of parameterizing existing.
Q: Could you compare this to FCP (flexible control plane - specifies set of operations on the forwarding plane)?
A: Not aware of this work.
Q: What is the usage scenario for this approach? Just programmable dataplane? Adapt scheduling and queuing based on time (based on workload)? Every single packet possibly treated differently?
A: Our system can support either of these due to its minimal interface.
Q: There have been approaches doing this at the network edge (e.g. Fabric). What is the motivation to have two different architectures? Isn’t processing at the edge more the silver bullet?
A: No, if there are bottlenecks in the network core; if at the edge then possibly.
Q: If a bottleneck is in the core, can the edge identify and transfer control to the core?
A: Possibly.
Hotnets '13: Toward a Verifiable Software Dataplane
Authors: Mihai Dobrescu and Katerina Argyraki (EPFL).
Software dataplanes give operators more flexibility, allowing more rapid deployment of changes. Recent advances have increased their performance to tens of Gbps, making them more practical. However, hardware manufacturers have been reluctant to allow network operators to install software into the data plane because of fear of bugs and performance effects.
The goal of this paper is to work toward verifiable software dataplanes. Properties that are taken for granted, like crash freedom, bounded per-packet latency, and network reachability are all goals of this verification system.
A tool that can verify these properties would reduce testing time, speed time to market, and allow a market to develop for dataplane software that is verifiable.
Unfortunately proving properties of general purpose software is a difficult due to shared state and the difficulty of reasoning about code behavior due to factors like path explosion. Sacrificing flexibility or performance has made this problem easier in the general software case. The software demands of the data plane have specific needs that mitigate the need for these sacrifices, making verification feasible.
In dataplane software, the input to an element is a packet. The output to an element is a modified packet. By considering dataplane software elements as a collection of pipelines of independent packet processing components with well defined, narrow interfaces and no shared state, verification time can be reduced.
Verification consists of two main steps. First, verify each element in isolation and identify suspect paths against the property one is trying to prove. Then verify the target property by composing these possible paths. The assumption is that individual elements are verifiable. Ocassionally this can be challenging, for instance when an element loops through the packet and modifies it depending on various options. This causes an internal path explosion. Decomposing the loop and conceiving as each step in the loop as a separate element simplifies reasoning and reduces path explusion.
Another difficulty is dealing with mutable state. Use of verified data structures can help ameliorate this problem. For more details see the paper.
They built a prototype based on S2E, a symbolic execution engine. They proved properties, such as crash-freedom and a bounded number of instructions on Click pipelines in 10s of minutes.
Q: Do you assume it is single-threaded
A: You can parallelize across multiple cores but they don't share data.
Q: Can you compare to other verification efforts, like seL4.
A: That was mostly a manual effort. We are trying to develop an automatic approach. We try to bring together the advancements from the verification community and combine it with the needs of the networking community. For example, the pipeline programming model affords us opportunities that aren't available for general programs.
Q: My impression is the formal verification community has made a lot of progress in the past few years. That leads me to the question of whether you would advocate for stylized programming methodology even if verification tools could do these transforms for you.
A: If there is a tool that can do this, sure, but I'm not aware of anything for C or C++. Our tool needs minor modifications to your code to provide hints for the tool. You write it in a structured way and it allows the tool to do the job.
Q: How do you train the programmers to use the tool?
A: The tool lets you know. It says you can verify something or you can't, and here's why. We take more of an interactive approach and try to create guidelines around the common needs.
Q: When you talk about performance do you make assumptions about graph properties of the pipelines? The network of these modules can be highly non-trivial. It depends on how you schedule individual packets. Do you restrict topology?
A: We analyze the performance of an individual element, and then compose the results to analyze the entire pipeline. We've experimented with simple pipelines, but I think you can have an arbitrary path.
Q: Including loops?
A: As long as you put a bound on how many times you feed it back in.
Q: Is Click the right kind of abstraction for pipeline modules or do we need something more finely grained?
A: For the evaluation we used Click, so we think it's sufficient. We think its granularity is good.
Q: I question the possibility of saying there isn't shared state between modules. For instance you can implement NAT in Click, which is stateful.
A: We looked into NAT, so basically you're right, but you can look into why you need this state. You can do static allocation of the ports available and then you don't need to share state. There are imbalances, but this is feasible.
Thursday, November 21, 2013
Hotnets ‘13: On the Validity of Geosocial Mobility Traces
Authors : Zengbin Zhang, Lin Zhou, Xiaohan Zhao, GangWang, Yu Su, Miriam Metzger, Haitao Zheng, and Ben Y. Zhao
There has been significant effort to understanding human mobility; a number of applications such as infrastructure deployment and AdHoc vehicular design can be enhanced significantly with knowledge of user mobility. However, obtaining large-scale, accurate and detailed traces of human movement has proven to be hard. Social networks such as Foursquare offer new ways of obtaining human mobility traces. The goal of this paper is to examine the quality and representativeness of this data, and based upon the quality, possibly clean up the data and perhaps extrapolate from it.
The paper evaluates the quality of the data from social networks by comparing it with GPS traces of “ground truth” data. The authors wrote an app which can be deployed on users’ phones which records users’ locations using GPS (and whatever other localization techniques are availables). This location data is then compared with the “Check-in” data that users provide on Social networking websites.
The authors found that a majority of data logged by the social networks is spurious. Several companies offer discounts and other incentives to “Check-in” frequently. This leads to a number of spurious check-ins by users. Also, users do not “Check in” if they are going to ‘routing’ places like their home, workplace, or grocery stores. Thus, down-sampling occurs a lot too.
In spite of these flaws in the data, it may still be of use. Extraneous check-ins can be removed by comparing them with ground-truth data. Further, it may be possible to remove missing locations by up-sampling observed checkins based on statistical models of real user mobility.
Q) What’s the accuracy of GPS coordinates? People turn off GPS all the time, and perhaps the locations in the study are not accurate?
A) In general, we force GPS to be on as much as possible. If it’s not on, use everything else that we can. For most of data, we had fairly reliable GPS. There is a 5% error region that we are not accounting for; perhaps these are caused by location errors.
Q) Doesn’t Foursquare validate when check-ins come in?
They do not.
Q) Do companies like FourSquare allow spurious check-ins to give users the flexibility to login from indoors? If users don’t have this flexibility, perhaps they can only login from outdoors, and this would result in bad user experience ...
A) Yes, it’s a part of it. They don’t want to ban spurious check-ins. Someimtes the location itself is the problem with things like foodtrucks, which are mobile and move around a lot. That’s why the threshold in our study is really large.
Foursquare’s own test shows that GPS isn’t highly reliable unless everything else that could be used for location-sensing was turned on. So we were not focussed on saving power, we just turned on everything too.
Q) Twitter has GPS info also. Is there incentive to show location?
A) My guess is Extraneous check-ins will disappear for most part if GPS coordinates are provided. But there will still be downsampling. Pruning the data is easy, but extrapolating is the real challenge.Hotnets '13: Towards Comprehensive Social Sharing of Recommendations: Augmenting Push with Pull
Authors: Harsha V. Madhyastha (UC Riverside), Megha Maiya
Speaker: Harsha V. Madhyastha
In spite of the widespread use of social networks, the authors contend that obtaining opinions from other people remains hard, particularly from friends and family whose opinions may matter more. The primary goal of this paper is to improve how people internetwork with other people and specifically, to make it easier for people to ask for and give recommendations to each other.
The authors note that users have a number of options to recommend things that they like, since many websites provide “Likes” and “+1”s. And it should be possible for a user to ask a question of his friends and find answers quickly. However, in practice, this is much harder. The authors note that people often do not share their likes and dislikes on the Internet. In the current Push-based paradigm, one can query for recommendations and obtain them with low delay, but the recommendations may not be very complete because of low user participation. On the other hand, people may be much more open to sharing their recommendations with specific people, although this could incur higher delay.
This paper aims to examine the tradeoff between delay and completeness by asking the following question: What if the Push-based paradigm is augmented by a Pull-based paradigm? Users often do not take part in the Push-based paradigm, because it involves effort and also involves privacy concerns. Thus, reducing the effort involved to share information and reducing accidental information leakage should incentivize users to share more information.
In order to achieve this goals, the paper suggests the use of a personal repository, which is a complete log of the users’ actions on the Internet. Subsequently, when a user has a query, a search is performed upon the repositories of all the users’ friends. If any of the friends has relevant information, they can choose if they want to share it. In this way, users can share more with lower effort and also exercise a greater degree of control over their privacy.
Q) Pull style may not be appropriate everywhere since it may introduce other sorts of privacy concerns. Maybe Pull is not always the best option?
A) Yes, you are right; the Pull model is not always the best model since consumers are revealing their questions. But since there is the notion of circles in several social networking sites, perhaps we can leverage circles to provide some extra anonymity. The social network could pass on queries from a Circle, and not from a specific user.
Q) The system uses increased logging. What kind of threat models are there if you log even more?
A) Great question, this is preliminary work. One can imagine encrypting all the data with their own key, but even then, there is no doubt that information leakage, if it occurs, will be much bigger. Another question that comes up is if we are we aiding law enforcement significantly, since we may be providing them much more information about ourselves by signing up for the comprehensive personal repository. However, at this point, the aim of the paper is more to bridge the gap between what is being shared and what is not being shared, and the question of threat models will be addressed more carefully in the future.
Session 4 Discussion: Social
Q: how should we view privacy? From today's session, on one hand you have privacy preservation, then on the other, you have logging, and Ben is saying how nobody is telling the truth.
A: [Ben] I'm agnostic. My work doesn't say anything about privacy, and since the truth isn't out there, it's almost irrelevant.
A: [Anmol] It's difficult to enforce privacy, so our approach is to provide transparency as a "different" approach to privacy preservation.
Q: [to Anmol] is your chrome extension going to be available?
A: [Anmol] Yes, maybe next week.
A: [Ben] We can all take proactive approaches to preserving privacy. For example, if I was FourSquare user, I'd add a script to obfuscate my own data.
A: [Anmol] most tools to help anonymize things today are point solutions. There is a SIGCOMM paper that talks about unifying these tools across the "user profile" stack (this type of work) that might help.
A: [Karen] there is some work about payment schemes were users (those targeted) can monetize the ads themselves.
Q: observation that the pull model might actually help simplify privacy, where you can just ask for, say, any 1000 samples of something, without attributing those samples.
A: [Harsha] Good though, but latency might be a concern (see his talk)
Q: As computer scientists, we already understand some of these things, but the average user might not be as sophisticated. We might want to be careful about giving these users another tool who may mistakenly reveal something private.
A: [Harsha] Overall, we are targeting users who are currently sharing nothing, and the pull model may help with this. But the proof will be in the pudding (upon deployment).
A: [Ben] Where should responsibility lie: users or providers? For the former, you're assuming sophistication, and for the latter, you're assuming the right incentives, etc. It's unclear if one answer will work.
A: [Ben] I'm agnostic. My work doesn't say anything about privacy, and since the truth isn't out there, it's almost irrelevant.
A: [Anmol] It's difficult to enforce privacy, so our approach is to provide transparency as a "different" approach to privacy preservation.
Q: [to Anmol] is your chrome extension going to be available?
A: [Anmol] Yes, maybe next week.
A: [Ben] We can all take proactive approaches to preserving privacy. For example, if I was FourSquare user, I'd add a script to obfuscate my own data.
A: [Anmol] most tools to help anonymize things today are point solutions. There is a SIGCOMM paper that talks about unifying these tools across the "user profile" stack (this type of work) that might help.
A: [Karen] there is some work about payment schemes were users (those targeted) can monetize the ads themselves.
Q: observation that the pull model might actually help simplify privacy, where you can just ask for, say, any 1000 samples of something, without attributing those samples.
A: [Harsha] Good though, but latency might be a concern (see his talk)
Q: As computer scientists, we already understand some of these things, but the average user might not be as sophisticated. We might want to be careful about giving these users another tool who may mistakenly reveal something private.
A: [Harsha] Overall, we are targeting users who are currently sharing nothing, and the pull model may help with this. But the proof will be in the pudding (upon deployment).
A: [Ben] Where should responsibility lie: users or providers? For the former, you're assuming sophistication, and for the latter, you're assuming the right incentives, etc. It's unclear if one answer will work.
HotNets '13: Network Stack Specialisation for Performance
Bonus: Panel discussion for Session 3 at the end!
Speaker: Ilias Marinos
Authors: Ilias Marinos, Robert N. M. Watson (University of Cambridge), Mark Handley (University College London).
Traditionally, servers and OSes have been built to be general purpose. However now we have a high degree of specialization. In fact, in a big web service, you might have thousands of machines dedicated to one function. Therefore, there's scope for specialization. This paper looks at a specific opportunity in that space. Network stacks today are good for high throughput with large transfers, but not small files (which are common in web browsing). For example one of their experiments showed with 8KB files, ~85% CPU load for just ~50% throughput (5 Gbps).
The goal of this paper is to design a specialized network stack that addresses that problem, by reducing system overhead and providing free flow of memory between the NIC and applications. The paper introduces a zero copy web server called Sandstorm which accomplishes that.
Key design decisions include putting apps and the network stack in the same address space; static content pre-segmented into packets; batching of data; and bufferless operation. In performance evaluation, the most impressive improvements are in flow completion time when there are a small number of connections, and CPU load reduction of about 5x. When moving to 6x10GbE NICs, the thoughput improvement also becomes impressive: about 3.5x higher throughput than FreeBSD+nginx and even bigger improvement over Linux+nginx. Overall, the paper's contribution is a new programmign model that tightly couples the application with the network stack, reaching 55 Gbps at 72% load.
Q&A
Q: Was this with interrupt coalescing on the NIC turned on?
A: Yes.
Q: Would it be possible to turn it off?
A: We can poll.
Q: Does this stack optimization perhaps suggest changes in TCP -- things like, say, selective ACKs, which we maybe thought was a good idea, but is just too complex?
A: Not so far. The real problem is the system stack not the protocols themselves.
Q: At what level do you demultiplex, if you have two different stacks, legacy and Sandstorm?
A: Could share stack if you are careful, or use two queues and put apps on different stacks.
Q: But current NICs generally don't have enough demultiplexing flexibility to send certain traffic types to different stacks.
A: There are a few NICs that can do that.
Q: Could you fix the stack overhead with presegmentation?
A: Presegmentation is only one part of the problem.
Q: It would be interesting to see a graph showing how much benefit comes from each of these specializations.
Panel discussion for all papers in this session
Q: How does big data affect these works on the data plane?
A: Facebook wouldn't be supporting Open Compute Project if it thought it didn't matter.
Q (for the Disaggregation paper [Han et al.]): The RAMCloud project also had tight latency constraints, but they're trying to treat servers as a pool of memory (not full disaggregation). How do the approaches the compare? Why isn't RAMCloud the solution?
A: RAMCloud doesn't allow you to change the CPU/Memory ratio. (Additional discussion not recorded. .
Q: Why not push functionality near to the storage device?
Q: Does it make sense to combine the visions, using an approach like tiny packet programs to get functionality closer to the network?
Q: There are several reasons you have hierarchies of latency. One is because we just don't know how to build really low latency memory. But also there are others, e.g. fast memory is more expensive. The cross-cutting vision of these papers seems to be removing implementation barriers, which then allows you to create a more optimized hierarchy (based on fundamental cost tradeoffs rather than implementation). Is this how you think about this?
A: May depend on workload.
HotNets '13: AdReveal: Improving Transparency Into Online Targeted Advertising
Authors: Bin Liu (USC), Anmol Sheth, Udi Weinsberg, Jaideep Chandrashekar (Technicolor), Ramesh Govindan (USC).
Speaker: Anmol Sheth
This work is motivated by two observations: the ad ecosystem is becoming increasingly fine-grained with respect to per-user tracking, and advertisers are willing to pay (up to 2.6x higher) for targeted ads vs non-targeted ads. The goal of this work is to provide users with transparency to how these (targeted) ads are chosen.
As an example, a person browsing a Web site sees a particular ad might want to know why this particular ad was shown to him/her. This might be useful, for example, to allow users to play an explicit role in controlling ads, for example, to separate home persona and work persona, or to not advertise my personal interests, like health, finance, or online dating.
There are three primary targeting mechanisms used today: (1) contextual (ignores user profile, but uses context, say Web page content), (2) behavioral (user profile explicitly used), (3) re-marketing (target users who have shown explicit -- perhaps previous -- interest in advertiser's product). This talk discusses how to identify whether an ad is likely to display the first or second category; more about the third in the paper.
The authors built a Chrome extension called AdReveal. It is based upon an ML model (logistic regression classifier) that is used to calculate probability of the ad using contextual or behavioral targeting. The results show that up to 65% of ad categories are behavioral. Most contextual ads are from pages about politics and government, whereas ads on pages about insurance/real estate/travel/tourism were higher.
The authors are surprised by how high this result is for behavioral targeting.
The hope is that transparency will enable new ad control mechanisms, and promote more measurement studies. The authors also had a demo that shows the extension in action: it displays what targeting mechanism are likely used for each ad, and the breakdown of a user's ad categories.
Q: can you use the framework to see if a user model is shared across different ad companies?
A: you mean like re-selling? not yet, but we're exploring it.
Q: we have different personas, say, across devices. These profiles may look different. Are there efforts to unify these profiles (presumably by marketers)?
A: Google seems to be trying to do this, say in android devices. Another approach is to correlate something like browsing patterns to be able to use this.
Q: how can you ensure that browsing history was consistent in experiments?
A: we used a fresh browser profile (deleted cookies, etc). we also ran experiments at different times of the day and with different IP addresses using PlanetLab.
Q: I like this work, but this seems like a passive tool; what can users to do with this information?
A: This may help users learn how to more carefully obfuscate their profile. We might be able to selectively delete profile, cookies, etc, so you don't lose the benefit of this tracking while eliminating some of the tracking.
Q: Google seems to offer this type of breakdown. Have you compared your tool to what Google reports?
A: not yet, but it sounds like a good idea.
HotNets '13: Pharos: Enable Physical Analytics through Visible Light based Indoor Localization
Authors: Pan Hu (University of Massachusetts Amherst), Liqun Li (Microsoft Research Asia), Chunyi Peng (University of California, Los Angeles), Guobin Shen, Feng Zhao (Microsoft Research Asia)
GPS-like indoor localization is important, with current techniques determining the position by using distances or angles of arrival based on access points. In addition, fingerprinting techniques allow position estimation based on information (e.g., signal power) collected at discrete positions aggregated in a centralized database. However, there is additional improvement to be made in terms of localization accuracy.
Given the wide-spread adoption of LED lighting, it is possible to exploit the visible spectrum to determine current location. Since LEDs have very quick rising and falling transition edges between on and off, it is possible to transmit information over this optical medium by modulating the LED. If each LED light broadcasts its location information, user devices can perform multilateration to estimate their own location based on the received location information, along with estimated distances according to received power from each light. In order to support many uncoordinated LEDs within some environment, frequency-division multiplexing is used along with frequency hopping to avoid interference (an approach that is similar to Bluetooth).
This system was implemented in hardware, designing control boards to connect to the LEDs and light sensor boards to attach to cellphones (via the audio port for communication). In practice, within both a conference room and cubicle area environment, the accuracy is shown to be within 0.4 to 0.7 meters (better than representative WiFi based approaches).
Q: What changes are necessary to existing lights?
A: Each light must be attached to a control board, which supports the transmission of the necessary location information beacons as part of the multilateration protocol.
Q: In the evaluation, there are very open environments and without many people moving around. Do you have plans for evaluations in more dense environments?
Q: What happens if there is a room with outside sources of light?
A: If the cellphone can detect the natural light, it should be able to actually use GPS in this case (as it has a LOS to the sky). However, stable sources of light will not affect this method due to detecting the power at certain frequencies (10 kHz to 19 kHz).
HotNets '13: Give in to Procrastination and Stop Prefetching
Authors: Lenin Ravindranath, Sharad Agarwal, Jitendra
Padhye, Chris Riederer
Many applications such as shopping, socializing improve
their performance by prefetching. They do not care about data usage. It
consumes 600KB to simply checking the temperature in a weather application. It
downloaded 30 objects in this process include very large radar image. The
applications do so because the cellular network is slow.
However, the author point out that there is a need to stop
prefetching due to limited data plan or roaming to other networks. So they
presented Procrastinator that could decide when to fetch each network
object.
The Procrastinator makes decision by taking several factors
into account, include whether the user is on WiFi or cellular network, how many
bytes are remaining in the user’s data plan and whether the object is needed at
the present time.
The procrastinator does not need to have the source code for
the applications. It could achieve its
goal by trap system calls and inject custom codes. In addition, it does not
require OS changes.
The author carried on an experiment on 9 cellphones for 6
weeks. The result of the experiment is significant. The system could achieve up
to 4 times saving in bytes transferred.
The paper revealed an interesting and common problem on
cellphone users. The authors regard the system as a significant improvement to
current cellphones by providing a useful function with little overhead.
Q: There may have side effects on the server such as more
http requests.
A: It won’t pose too much pressure on the server. Just
process the request as usual.
Q: Do you think it can be applied in other useful cases such
as taken other people into consideration while sharing the same network?
A: Yes.
Q: Do you think it will impair the user experience? Did you
carried out any user study on this?
A: For WiFi networks the impairment is very small.
Q: Do you process any post requests or TCP connection?
A: Yes.
Q: Hacking my binary does not make me feel good.
A: It won’t cause bad things for you.
Q: why not provide prefetching API in the system? It could
also provided a bounded delay for the software.
A: That requires too much effort. Actually we’ve developing an IDE which can
warn the developer of improper prefetching.
HotNets '13: Network Support for Resource Disaggregation in Next-Generation Data Centers.
Authors: Sangjin Han (U.C.Berkeley), Norbert Egi (Huawei Corp.), Aurojit Panda, Sylvia Ratnasamy (U.C.Berkeley), Guangyu Shi (Huawei Corp.), Scott Shenker (U.C.Berkeley and ICSI).
Traditionally data centers have segregated their computing resources into a collection of individual servers. There has been an ongoing trend with systems such as HP MoonShot and AMD SeaMicro, both of which disaggregate some resources. This paper looks at what data centers would look like in the future if this trend continues.
As this trend continues all resources would be accessible as standalone blades connected by a unified interconnect. This development would increase resource modularity dramatically. This would allow operators to update or replace hardware in tune with its upgrade cycle with less difficulty. It would also allow operators to expand capabilities in a more granular way. In this scenario, operators could purchase only the resource they need in aggregate.
While this is a significant conceptual change, hardware and software changes can be done incrementally. In the case of hardware the fundamentals would not need to be changed. The chief accommodation would be the addition of a network controller. For individual software applications, no changes would need to be made, but some minor changes would have to be made in the VM.
These modified virtual machines would then be able to achieve higher efficiency than in the traditional data center because of the increase in resource acquisition flexibility and fewer resources would be left unused on individual servers.
On a larger scale, instead of being connected on an internal bus, resources would be connected to a unified network. While a unified interconnect may seem radically different than a traditional internal interconnect, comparing PCIe to Ethernet shows them to be similar requirements.
A significant difference though is communication latency, which is particularly a factor with memory. By expanding the memory hierarchy to add a layer of local memory next to the CPU to act as a cache the cost of this could be mitigated. In an experiment they found that 10-40 Gbps network link is sufficient, with an average link utilization of between 1-5 Gbps. Latency of less than 10 microseconds kept overhead to less than 20%. Keeping latency low is a key ingredient to a performant disaggregated data center.
Q: This reminds me a lot of multiprocessor systems from the past used in mainframes.
A: They are similar in that they try to act as a big computer, but the main difference is how tightly coupled the resources are. A primary goal of a disaggregated data center is a decoupling of these resources. Previous systems coupled resources tightly to achieve higher performance.
Q: Instead of a proprietary bus you want to use a more open protocol?
A: Yes
Q: 20 years ago desk area network and some others had the idea that you can push the network very far in the device and very low latency interconnects was necessary. Are their common models or lessons?
A: Data centers are very big now and can achieve high economies of scale. This changes the economics of this approach, which was a problem with the earlier approach.
Q: What is the relationship between disaggregation and high performance computing. It seems like approach starts with commodity components. What if you started from supercomputing?
A: Modularity is everything. Vendor-lock-in increases costs.
Q: What is the overhead in hardware cost?
A: Network controllers at scale are very cheap.
Traditionally data centers have segregated their computing resources into a collection of individual servers. There has been an ongoing trend with systems such as HP MoonShot and AMD SeaMicro, both of which disaggregate some resources. This paper looks at what data centers would look like in the future if this trend continues.
As this trend continues all resources would be accessible as standalone blades connected by a unified interconnect. This development would increase resource modularity dramatically. This would allow operators to update or replace hardware in tune with its upgrade cycle with less difficulty. It would also allow operators to expand capabilities in a more granular way. In this scenario, operators could purchase only the resource they need in aggregate.
While this is a significant conceptual change, hardware and software changes can be done incrementally. In the case of hardware the fundamentals would not need to be changed. The chief accommodation would be the addition of a network controller. For individual software applications, no changes would need to be made, but some minor changes would have to be made in the VM.
These modified virtual machines would then be able to achieve higher efficiency than in the traditional data center because of the increase in resource acquisition flexibility and fewer resources would be left unused on individual servers.
On a larger scale, instead of being connected on an internal bus, resources would be connected to a unified network. While a unified interconnect may seem radically different than a traditional internal interconnect, comparing PCIe to Ethernet shows them to be similar requirements.
A significant difference though is communication latency, which is particularly a factor with memory. By expanding the memory hierarchy to add a layer of local memory next to the CPU to act as a cache the cost of this could be mitigated. In an experiment they found that 10-40 Gbps network link is sufficient, with an average link utilization of between 1-5 Gbps. Latency of less than 10 microseconds kept overhead to less than 20%. Keeping latency low is a key ingredient to a performant disaggregated data center.
Q: This reminds me a lot of multiprocessor systems from the past used in mainframes.
A: They are similar in that they try to act as a big computer, but the main difference is how tightly coupled the resources are. A primary goal of a disaggregated data center is a decoupling of these resources. Previous systems coupled resources tightly to achieve higher performance.
Q: Instead of a proprietary bus you want to use a more open protocol?
A: Yes
Q: 20 years ago desk area network and some others had the idea that you can push the network very far in the device and very low latency interconnects was necessary. Are their common models or lessons?
A: Data centers are very big now and can achieve high economies of scale. This changes the economics of this approach, which was a problem with the earlier approach.
Q: What is the relationship between disaggregation and high performance computing. It seems like approach starts with commodity components. What if you started from supercomputing?
A: Modularity is everything. Vendor-lock-in increases costs.
Q: What is the overhead in hardware cost?
A: Network controllers at scale are very cheap.
HotNets '13: Inaccurate Spectrum Databases? Public Transit to its Rescue
Author: Tan Zhang, Suman Banerjee
TV white spaces could provide us with precious spectrum
resource. It could enable many interesting applications. We need to look up
databases before using the channel to avoid interference according to FCC rules.
However, the current commercial databases are not that
accurate. According to their experiments, the databases have low under
protection rate that is usually less than 1%, but it has wasted a lot of
resource to protect TV and wireless microphones. 42% of the spectrum is wasted according
to their measurement.
The authors proposed a system to fix the database using
opportunistic measurements. The challenge of detecting primary signal comes
from the very weak signal. The FCC rules indicates that the channel is
unoccupied if the primary signal is weaker than -114dBm. This is hard to detect even on the most
advanced spectrum analyzer.
To solve these problems, the author proposed the V-Scope
system.
It includes a zoom-in pilot-tracking algorithm that could
measure the power of TV signals up to -120dbm. At the same time, the author
also proposed a model refinement procedure to augment the existing propagation
model with their measurement.
To evaluate the V-Scope system the author carried out
experiments in a 100 square-km area with over 1 million result collected. The experiment shows that opportunistic
wardriving is useful. Users could reclaim at most 33% of the measured
locations.
The paper pointed out the problem of current TV Whitespace
database and provided a practical system to fix that. Experimental results
indicate a significant improvement over the state of the art database.
Q: Wireless microphones may not transmit all the time.
Opportunistic sensing may miss the signal.
A: Sampling at the same place for multiple times could solve
this problem. Public transit will pass by the same place for many times per
day.
Q: Why there are commercial databases?
A: FCC specified the standards, and the commercial databases
make profit from providing services to CR devices.
Q: Is it legal to do so? Does FCC force these rules?
A: Sure.
Q: Does FCC force these models?
A: Yes, the models are specified in the standards.
Q: Why do you use this model?
A: Many models are trying to predict the channel availability.
Log based model is generally hold, so we
need to tune the parameters only.
Q: Which databases did you studied?
A: Google and SpectrumBridge.
Subscribe to:
Posts (Atom)