Events Add an event Speakers Talks Collections
 
SIGCOMM 2020
August 11, 2020, Online, New York, NY, USA
SIGCOMM 2020
Request Q&A
SIGCOMM 2020
From the conference
SIGCOMM 2020
Request Q&A
Video
Probabilistic Verification of Network Configurations
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Add to favorites
199
I like 0
I dislike 0
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
  • Description
  • Transcript
  • Discussion

About the talk

Not all important network properties need to be enforced all the time. Often, what matters instead is the fraction of time / probability these properties hold. Computing the probability of a property in a network relying on complex inter-dependent routing protocols is challenging and requires determining all failure scenarios for which the property is violated. Doing so at scale and accurately goes beyond the capabilities of current network analyzers.
In this paper, we introduce NetDice, the first scalable and accurate probabilistic network configuration analyzer supporting BGP, OSPF, ECMP, and static routes. Our key contribution is an inference algorithm to efficiently explore the space of failure scenarios. More specifically, given a network configuration and a property φ, our algorithm automatically identifies a set of links whose failure is provably guaranteed not to change whether φ holds. By pruning these failure scenarios, NetDice manages to accurately approximate P(φ). NetDice supports practical properties and expressive failure models including correlated link failures.
We implement NetDice and evaluate it on realistic configurations. NetDice is practical: it can precisely verify probabilistic properties in few minutes, even in large networks.

About speaker

Samuel Steffen
PhD student at ETH Zurich

Samuel Steffen is a PhD Student at ETH Zürich in the Secure, Reliable, and Intelligent Systems Lab. His research interests lie in the intersection of networks and probabilistic analysis.

View the profile
Share

Hi, I'm sad. And I'm presenting this going to work with T-Mobile. Petirrojo and Martin from eghc rig, Traditionally, lithographic Nations concerned with checking properties such as which ability and often also takes failures into account. And there is a long line of a few stories about such properties. And you can, for instance, check the property for a specific scenario or check whether the property holds for all scenarios in Sunset. And because in those cages, the property either. Or does not hold for the completed set of scenarios,

we call these properties heart properties. In reality, the failures within a network or public police sticks, downloads engines, failed randomly. So we can list the question about property satisfaction through this probabilistic settings and ask, what is the probability that the property holds the question? So, consider service level agreement specifying that which ability is guaranteed 99.99% of time or with probability 99.99, ultimate properties, who's for ballistic analysis? It interesting, for instance, consider a network operator that wants to have load balancing

but maybe not on the percent of the time because it would be too expensive, but 80% of the time would be okay. And ask these properties are allowed to be violated for some fractions time because all these properties soft properties. Analyzing these high position is usually required. For instance, to verify ds419slim. You will have to obtain an imposition below Poinciana 1%. So what can we do to compute the probability of the property? It eventually boils down to exploring the famous

place. In Rome, seems to attempt to explore the order of likelihood. So you would start with the scenario, very have no failures. Then check the property and then explore. All scenarios is exactly why. In the net profit on the 91 links and some realistic Fela probabilities, the number of scenarios to be visited in order to achieve a 4/9 position is more than this is clearly too expensive, right? Running an existing verify for each of those scenarios.

Alternatively, you can perform probability estimation using sent this to. You just repeatedly sample from the sale of the property. Don't you think concentration bound set a 30-minute quality? You can show that you need at least seven hundred millions of this year in order to achieve before ninth position and this is Gary So in this talk, I'm introducing neckties which reduces the number of scenarios to explore to a bit more than 2,800 which is around the Times with Dachshund compared to mix ratio.

Neckties is a probabilistic network. Configuration, analyzer supporting pgp night. EP high accuracy sufficient to verify 490 Celeste and, which is scalable. Also Netflix, how does Mike Tyson work as it takes a network? Configuration of Ralph, Teresa supporting bgp to ospf Ethiopian static route, Mixed it takes a powerful fail emotions that can model dependent lymph nodes and solt failures. It also takes the property. This property holes in the network, on the ticket and send

them all. Let's have a look at the property supported by neckties traffic, arriving at Ingress. A destination shown here is forwarded And if that is interested in checking properties solely based on this Photograph and you can check my beans, you can also take a fling for the reporting requirement. And all those properties are called single floor property because the only depend on the forwarding resources in Oslo. Of course, you can extend this and reason about multiple flows that has isolation in what we call multi-flow properties. Letters. Target's fuel flow properties

with a set of laws. Under consideration this month, you can analyze any such property using neckties as long as there is insufficient check of the property based on the forward and crafts. How does neckties prune the space of failures? Consider this network here with you to sort of poverty, we're all links have weight one except the link in the center traffic from A to B, is forwarded, the longest part. Of course, if this link here fails, then the shores of a change in traffic will be forwarded us from here. However, on the detailers here, the shortest

person not change. It is a very important observation that any failure outside. So we captured these ideas in the notion of cold edges. The cause excess excess who's favored organ teeth. Not to change the forward and graph examples of outside the shortest, Paul. They're actually 32 weeks reason and sailor sing. I receive the same folding craft any combination of failures of the cold. The key technical contribution of neckties without identify called and just work on writing protocols. Let's introduce estatic router show here. Now traffic will be deflected

by the static route as shown in the figure. What are the coldest year? Of course, if any of the green Lynx fails, then the forwarding graph to change. But there are also other failures that would change the forwarding crafts. For instance, if this link fails, when the shortest path from A to B will change and Ava not forward traffic to the right in the first place, but we'll use the following forwarding. So, how do we find the gold Hsu actually reasons? Which is

You have already seen that the excess along the shortest path from A to B, have to be hoped because any of those mean failing will change the photograph by taking to compliment Meg, Cyrus arrives at the state of covid. you know, paper Journal couldn't identify the cold exercise for pgp Des algorithm takes into account Network petition to semantics of reflection in the dependency between PCP and ITP. You can have a look at the paper Drury. Also provides a correctness proof.

Don't, let's see how night at explore space afraid, there's in starts with a c. R o, the scenario without any failures and then come forward and glass and checks the property. Now is a different device to set of cold. Hsnt idea is to implicity cover any failures of toes at once without exploring these scenarios, to descend, you compute the probability of all equivalent scenarios, which are the scenarios that have called H failures. And this probability Mouse is much higher than the probability of two. No favors.

Now it's simply recursively. Introduces failures of the norm called access. So we don't let this at 12 and then apply this a technique recursively, it has to take care of, exploring States twice. Summit ice explores the tree or fail, scenarios and simple songs of the probabilities of, those are the property holds, the efficiency of our exploration depends on the number of called actress neckties is very efficient in practice. Implemented neckties and you can find its implementation supporting some common properties on keto.

For senior flow properties, such as Rich ability only uses few minutes in Netflix of hundreds of links to reach the four lines position. for 80% of the scenarios more than half of the links are called, For multi flow properties, neckties performance De Grace gracefully as in summary, has a precise and efficient probabilistic network configuration. Analyzer Great. Thank you for the nice talk. So send me was online now and please feel free to ask any questions while we have many questions

on me. So the first session from Aaron is, how does determination of hot and cold edges? Interact with interact with equivalent classes? So this is the famous by identifying call. Dad wants to know. I just called then the times of flavor combinations in class identify a whole extremists class by looking at the set of cold at just. So it's basically the same Into the next question from a d. Yes. So in terms of failure to support a very expressive model so you can also more no failures or a shared Riesling through playlist. That's not an issue.

We have a strong muscles are both in terms of realistic event. For instance, a realistic BHP announcements, for example neckties can currently not hands. And is focused on Matrix component Taylors. One last question, you're any good opportunity to steal his eyes from Marty flow properties. I'm not sure, I understand the question. So in terms of multiple properties, sanitize starts to the great writer. For instance, if you check all the flaws in your network, like in square,

because there won't be any contact with your focus on something, like, I may have to have it slows or two flaws. That must be isolated for reasons of security, then you can use my ties to analyze. That sounds kind of properties. Write, thank you very much. Congrats on being. You wouldn't work and there are a lot more questions, and I neglected to mention the beginning. This is also going to see what papers said, congratulations on the best eating paper word and also paper that received all of the artifact evaluation badges which again, is great to see books. Releasing open

source artifacts that can be used by others. I'm so full of questions, please. Either type into the Q&A or, or on the stock. I see some pencils writing on the side. I quickly ask, I'm curious if you've had me Springs talking to network operators, and why are they thought? So I'm just going to probably take an Allosaurus Currently model or anything. Currently doing, is just a practice or to some kind of simulation Great questions from the slack. From a ritual, he says isolation smells like a hard property because it's security-related. Is that the right

intuition? Wendy's Reese is correct, but it's not about the security here to finish. When you start include more flows, then you will have more exercise, right? So if you only look at your floor stain, you basically the same reasoning applies as you have seen in the talk, but they need to union to become slower and slower simply because it's very hard to find any record of an email respect for property. another question about the performance, is there performance impact due to realistic bgp policies question here is

Without where the examples you considered somehow Representatives, or or were they simplified in some way? Yes, it's so for the policies actually smell the scaling. Me. She was all. So, if you could wear policy at the net to catch for using EBT. Maps, it's not an issue for Maryland. Pre-processing step of you doing crazy around in change to Portrait to, to have some for maternity section. For this going on Cason TV, looking for the future. I'm sorry, one more question. So this printing based on

cold Edge's theme seems really nice and a very important optimization for making this to scale this to us. I'm in loss of fits well, with the kinds of protocols. You're looking at, which I must be triggered by you. No changes on inches. Have you considered infertile publishing houses tools? Whether this kind of optimization make sense. I'm so, you know, finding some dimensional problem where when the the weight of something to put it on that aspect, you know, Falls below a threshold. Then you decide to no expert. I'm doing this technique is is generally

applicable. And I'm also running about like, datapoint analysis or other other kinds of her calls. And besides the one you met all this, if it would always be edges or might be something else that causes you to prune trees. So, the idea still applies. It's about identifying, which aspects will actually impact what is going on in this trailer spotted clearlink sales during inspiration. But I can imagine that you can apply similar reasoning with other things that can be pruned and like this

writing for the same ride. So we should have some elements which are subject to any changes. The properties of course you have to sit down and can't afford any fire first, what kind of elements that you want to prune and second you need to find an efficient way to identify

Cackle comments for the website

Buy this talk

Access to the talk “Probabilistic Verification of Network Configurations”
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free

Ticket

Get access to all videos “SIGCOMM 2020”
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Ticket

Interested in topic “IT & Technology”?

You might be interested in videos from this event

November 9 - 17, 2020
Online
50
94
future of ux, behavioral science, design engineering, design systems, design thinking process, new product, partnership, product design, the global experience summit 2020, ux research

Similar talks

Joao Luis Sobrinho
Professor at Instituto Superior Técnico
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Tong LI
PhD Candidate at Huawei
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Fangdan Ye
Student at Tsinghua University
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free

Buy this video

Video
Access to the talk “Probabilistic Verification of Network Configurations”
Available
In cart
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free
Free

Conference Cast

With ConferenceCast.tv, you get access to our library of the world's best conference talks.

Conference Cast
949 conferences
37757 speakers
14408 hours of content