Authors: Arne Ludwig, Matthias Rost, Damien Foucard (TU Berlin), Stefan Schmid (TU Berlin and T-Labs, Germany)
Presenter: Arne Ludwig
Arne notes that networks are becoming more and more dynamic, partly an effect of SDN. And network updates happen for a variety of reasons, for example, due to changing policies. How do network updates impact security? For example, we don't want path changes to allow bad packets to bypass network firewalls. That leads into the motivating example of waypoint enforcement, where we want all packets of a flow to pass through a network box (say a firewall). It is easy to build scenarios (like the example in the talk) where the paths before and after the network update pass through the network box, and there are no loops in either configuration, but when changing from using one path to another both these problems can occur.
Arne notes that we can simplify the model under consideration to involve only nodes in the intersection of the old and new paths because other nodes can be updated without issue. Of primary concern in this work, are the properties of waypoint enforcement (WPE) and loop-freedom (LF).
At the core of the problem is that we cannot update network configurations "simultaneously"? This is not possible in practice; and the time between an update being issued and it taking effect varies a lot (as past work has shown). But can we plan a sequence of updates such that at each step we have WPE and LF? This is the question this work addresses.
The overall idea is to organize the update process in a series of rounds, such that within a round of updates, the order of updates will not break WPE and LF, and then figuring out how to order the rounds, still while preserving WPE and LF. The goal then, is to minimize the number of rounds (to cut the time during which the network is transient, and thus prevent negative effects on traffic.) The paper shows that a greedy approach which attempts to maximize the number of updated links within a round is both incorrect (sometimes fails to find a solution, even when one exists) and inefficient.
More broadly, this work shows that WPE and LF are in conflict, and in general, a solution while enforcing both at each step does not always exist. To guarantee the discovery of a solution when one exists, the authors frame the problem as a Mixed-Integer program with the objective of minimizing the number of rounds, the constraints building in the LF and WPE properties. The MIP either yields an optimal solution, or reveals that an instance is not solvable. The MIP's complexity is large though, leaving scenarios where the MIP leaves the instance unclassified. Arne discussed their analysis of how often the MIP find a solution when the greedy approach fails, and how often the MIP leaves an instance unresolved due to time complexity. The greedy approach finds the solution in ~80% of the instances offered. The MIP solves a few percent additional cases. As the number of switches increases, the number of unclassified cases increases (due to increasing complexity).
The overall conclusion of this work is that update sequences guaranteeing WPE and LF simultaneously are hard to find (and sometimes do not exist) and sometimes, "maybe we should just concentrate on the security part" (presumably, tolerating transient loops).
Q: What happens if we have more than one waypoint?
A: We're currently working on this; it's not an easy problem.
Q: As the number of switches increases, the MIP doesn't seem to work. Should we just use greedy?
A: The MIP does find a solution in many scenarios where greedy doesn't work.
Q: Did you look at the union of when MIP and greedy find solution?
A: All scenarios solvable with greedy were also solvable by MIP, except due to problem size.
Q: (Andrew Ferguson) Does the structure of the network have an impact on whether you can find a solution?
A: We don't consider the full topology; our model allows us to look only at the switches on the paths under consideration.
Q: Have you compared your algorithms with techniques based on dependency graphs?
A: Dependencies between updates? We haven't looked into that for the MIP, but finding a better / faster algorithm based on these dependencies is something we're looking into.
Q: Can you go through additional nodes to solve the unsolvable instances?
A: The current MIP wouldn't handle that, but if we had knowledge of the topology and the other paths available, we could look into this.
Presenter: Arne Ludwig
Arne notes that networks are becoming more and more dynamic, partly an effect of SDN. And network updates happen for a variety of reasons, for example, due to changing policies. How do network updates impact security? For example, we don't want path changes to allow bad packets to bypass network firewalls. That leads into the motivating example of waypoint enforcement, where we want all packets of a flow to pass through a network box (say a firewall). It is easy to build scenarios (like the example in the talk) where the paths before and after the network update pass through the network box, and there are no loops in either configuration, but when changing from using one path to another both these problems can occur.
Arne notes that we can simplify the model under consideration to involve only nodes in the intersection of the old and new paths because other nodes can be updated without issue. Of primary concern in this work, are the properties of waypoint enforcement (WPE) and loop-freedom (LF).
At the core of the problem is that we cannot update network configurations "simultaneously"? This is not possible in practice; and the time between an update being issued and it taking effect varies a lot (as past work has shown). But can we plan a sequence of updates such that at each step we have WPE and LF? This is the question this work addresses.
The overall idea is to organize the update process in a series of rounds, such that within a round of updates, the order of updates will not break WPE and LF, and then figuring out how to order the rounds, still while preserving WPE and LF. The goal then, is to minimize the number of rounds (to cut the time during which the network is transient, and thus prevent negative effects on traffic.) The paper shows that a greedy approach which attempts to maximize the number of updated links within a round is both incorrect (sometimes fails to find a solution, even when one exists) and inefficient.
More broadly, this work shows that WPE and LF are in conflict, and in general, a solution while enforcing both at each step does not always exist. To guarantee the discovery of a solution when one exists, the authors frame the problem as a Mixed-Integer program with the objective of minimizing the number of rounds, the constraints building in the LF and WPE properties. The MIP either yields an optimal solution, or reveals that an instance is not solvable. The MIP's complexity is large though, leaving scenarios where the MIP leaves the instance unclassified. Arne discussed their analysis of how often the MIP find a solution when the greedy approach fails, and how often the MIP leaves an instance unresolved due to time complexity. The greedy approach finds the solution in ~80% of the instances offered. The MIP solves a few percent additional cases. As the number of switches increases, the number of unclassified cases increases (due to increasing complexity).
The overall conclusion of this work is that update sequences guaranteeing WPE and LF simultaneously are hard to find (and sometimes do not exist) and sometimes, "maybe we should just concentrate on the security part" (presumably, tolerating transient loops).
Q: What happens if we have more than one waypoint?
A: We're currently working on this; it's not an easy problem.
Q: As the number of switches increases, the MIP doesn't seem to work. Should we just use greedy?
A: The MIP does find a solution in many scenarios where greedy doesn't work.
Q: Did you look at the union of when MIP and greedy find solution?
A: All scenarios solvable with greedy were also solvable by MIP, except due to problem size.
Q: (Andrew Ferguson) Does the structure of the network have an impact on whether you can find a solution?
A: We don't consider the full topology; our model allows us to look only at the switches on the paths under consideration.
Q: Have you compared your algorithms with techniques based on dependency graphs?
A: Dependencies between updates? We haven't looked into that for the MIP, but finding a better / faster algorithm based on these dependencies is something we're looking into.
Q: Can you go through additional nodes to solve the unsolvable instances?
A: The current MIP wouldn't handle that, but if we had knowledge of the topology and the other paths available, we could look into this.
No comments:
Post a Comment