
Video

Table of contents

Video
 Description
 Transcript
 Discussion
About the talk
Standard vectoring protocols, such as EIGRP, BGP, DSDV, or Babel, only route on optimal paths when the total order on path attributes that substantiates optimality is consistent with the extension operation that calculates path attributes from link attributes, leaving out many optimality criteria of practical interest. We present a solution to this problem and, more generally, to the problem of routing on multiple optimality criteria. A key idea is the derivation of a partial order on path attributes that is consistent with the extension operation and respects every optimality criterion of a designated collection of such criteria. We design new vectoring protocols that compute on partial orders, with every node capable of electing multiple attributes per destination rather than a single attribute as in standard vectoring protocols. Our evaluation over publicly available network topologies and attributes shows that the proposed protocols converge fast and enable optimal path routing concurrently for many optimality criteria with only a few elected attributes at each node per destination. We further show how predicating computations on partial orders allows incorporation of service chain constraints on optimal path routing.
About speaker
Hello. We need three things from Portugal. My name is supposed to be in this short talk, I will go with you Maya. Miguel Paredes, listen to work enough. Suppose we want to deliver file Crossing at work as quickly as possible supposedly want to see in the video Crossing At Work Week. Minimum July at specified, are two rights in both cases, the result of compromises between General, current boxing protocol router only if the relative valuation of fat Matrix that is
consistent with the operation that computer back metrics from League matches. We were able to devise a procedure and protocol that allows Optima belt routing for an eye. We didn't realize that the procedure we do price to pave, the way for optimal path routing, concurrently for multiple of humility criteria, since the lots of problems of the former excuse, the title of the paper. Returning to our opening example, our protocols enable simultaneous routing delivery
across the network, on their respective, optimal apps. Open, do bats related, algorithms and protocols can be treated with General at him. The routing algebra algebra consist of a Saturn SUV, represent a performance metrics for that. She picked up a set and the optimal that's he gets from source to destination. In the network, is the optimal answer you tomorrow. The binary operation allows calculation of fat that switched from Lincoln Village. Routing, protocols, internet
extension, and the election operations on at CVS 1 week at a time. When there was a time, I will focus on that swing both goals, which instantiate a separate invitation process per destination forgiven. This nation has continually extend as advertised by out neighbors into Kansas. It is well known that veteran. Protocols do not route at the back of Sonakshi of fats in general. The key property, underlying optimal capitation size of tenacity, implies that the extension of equal is preferred
to the east extension of a woodsy. An equivalent characterization of citystates, that extension operation over the election of operation. Breaking protocol real fast. If I go to the city holds, if I do not Sprout animal fats in general, the problem is that many brackets do not satisfy. So what can we do? And idea is to reduce the total order such that I certainly city is satisfied in the reduced order, we using an order means declaring incomparable,
some pairs of acids due at the boots are incomparable. If neither of the two weeks before it's the other Rigorously and isotonic, production is a partial order continue. The foothill order for which is fine. It's a partial or the meaning of that incomparable. The largest Apostle Lords of the better in terms of route. It can be shown that every total order contains a large slice of Honey production. So now we have partial or this, how do we deal with partial orders?
Where to find suitable, path problems, and design appropriate routing. Protocols, in a partial order, the concept of dominant at CVS The dominant attributes from a source with destination. The network is a dominant activity. The set of dominant daddy with some sort of this nation is a set of paralyzing comprable acid. I know we were able to design partial or the battery in Portugal's also perform interactions of extension, but not better than Barcelona.
Importantly, it's a partial order is a reduction of some original Total order. Then you Regional Optima latitude is found among the dominant activities. So, if it were possible with the vaccine protocol, that's routes and Diamond path, we are able to find the optimal fast. We are one step away from being able to run concurrently on multiple optimity criteria. And what we do is just performed intersection He's getting two sections with his father's ethnicity. We are done. If it does not satisfy isotonicity, we take the largest production
that is contained in multiple orders. Now, can use a partial or the vaccine protocol, find the dominant. That's if the dominant fat and the original optimal. That's the main ideas of the paper. Miniature reviews of the paper from to collect certifications. If you were referred to the problems we have in the paper Motel turkey, breast problems are special case in these problems. Each term Associated extension operation and total order is the product of the elementary extension operations and chapels are partially order buy the product or their own Elementary total orders
extension of Corrections. Not necessarily the product of Elementary extension operations and the largest production and intersection of total orders did not necessarily lead to product orders. In fact, the paper but that's the quickest part or we just order on which is such that, its largest production is different from the profit, or their own Paris weekly Another reviewer off. Why don't use links a protocol instead? I guess there's something on the line pieces of this question. Is that Computing? Optimal passes somewhat
easier in ringsted protocol because every known as knowledge of the topology of the network, Lisa protocol is dijkstra's algorithm to compute, bats promissory note in Indianapolis. The concept of largest isotonic. Production at the intersection of total orders are as relevant as they are. One of the reasons for our preference for venturing protocols is because this protocol is complete athletes from the destination towards the sources, allowing simultaneous installation of
Ford information, to guide us to destination and this is not the case. I will leave this a short overview with the breakdown of the contributions we presented to problems optimal fast routing for an Optimum tax relief for multiple Rocky. Mountain Credit Union in the process of developing solutions to these problems, which is used to New Concepts, to routing largest total order or partial orders. Both concerts at least two partial orders centrepiece of our work was the design of partial or the between particles that route on
dominant path bus enable routing on multiple. Thank you for listening. Your feedback is welcome. Please get in touch with you. Thank you for listening. Please get in touch with you. Great talk, really impressive work at some wonderful questions coming in through slack. So let's start up. Sunday route from Purdue asks a question but I think a lot of folks of really benefit from hearing from you which is could you provide an example where I should send this to be
satisfied and one more Okay, thank you. That's a great person to to start because it's when people my other question. So I just need to be satisfied for instance in the shortest path routing. So I thought means that I woke up decision. Based I make I make for everybody is global as well. So, what I like is what my neighbor will like it as well, I can discard already passed that. The designer will not be good for anybody. So an example of an example, but it does not hold could be short. The slightest possibility. We are you trying to out on the shore of the widest pets.
So you're the first Criterion is why does and then you have the shortest month or more generally if you want to deliver a file the the back pasture, the liver of file is a combination of Eli on the universe bandwidth on this thing does not satisfy. I wrote that sufficiently clear. I'd be happy to continue on the number of routes generated and he give it to follow up with some routers today. So, if you want to speak in general to the complexity of both sites,
the next one question again, no. You said you have to go back to let them know. That may be the worst guys, exponential. So for instance, if you have to and belted length, you can contrive a very contrived matter if he's really about where the number 6. No, it's one of the the the components that make up the accident is for instance, with the number of wits in a napkin limited and so we can be a polynomial time on the size of the network. And we did you realize that you really measure is much simpler than the worstcase down on the qualities and the metric system,
which is one of the protocol is in particular. Are we starting protocol in the paper, and allows you to choose between optionality and complexity? So you can say I accept a maximum of three rounds. Each note for a given destination. A loose parts of the analogy of it. Perhaps do better than I like in just one. So what this thing is is that the way that breaks over from our prison of having a routing protocol selecting only one route I'm not listing, sorry. Oops, I said something to somebody. I don't know. I apologize
to follow up. So so timid episode Apollo question. You just initial K quickest shortest pass does each driver have to use the same value of K and W? No by no means so you can see the election. I'll drop him off bathroom two steps, the network as a whole computes dominance pass. So what you can see the other way, which is that I could get ahold of Scots path, that certainly will not be open for anybody and then you just settle down a minute that you use for every sort of the destination. And then the source, the open will pass among those have to be there. So
you just make the population of the quickest for the value of K that you want and you choose, which is the brokest one. Fantastic. Thank you so much. Okay, thank you. If you want for that interesting and presentation. Hello. Miguel. So, could you give an example for our listeners? That's maybe haven't looked at the paper yet. Can you give me an example of a isotonic order and an anion isotonic order. Just so people have an idea what we're talking about
an order, which satisfies the shortstop's old is just a less than equal. So Satisfied by the spot where the shortest route shortest way to stop farting. So mean that refers to choose the. Why the staff and then the shortest amount to what among the whitest there's no status. I guess for another example of a more or less people when we can think of is the order of the underlined a time to propagate a salad. I say, okay, thank you. I have another question. So, you know, when we think about policy, Rich, protocols, like bgp, right? It
seems to me that, you know, this difference between local Optima. That's a kind of a Nash equilibrium. You get the best thing, given, what your neighbors, give you versus global optimality? It seems to me that with a protocol like btp is that, actually, the local Optima is exactly what we want because we don't necessarily the notion of global optimality doesn't even make sense necessarily in that case. And in that case, your largest, what do you call it? The largest isotonic? Yeah, it's going to be something trivial like the equality
relation, right? So can you talk about that a little bit? So in the context of what we are interested in are the IMDb. And yes, I I just said, okay, yes, okay and also the property satisfy other algebra is are slightly more relaxed, but I guess you could also if you could, you could still be fine at the largest maybe with some other clothes from in, and go on from there. Since you could think of all that Computing or producing large sections of this policy reach
out to reason about Okay. So we aren't getting any questions on the slack channel. So viewers, please send questions but so I'll ask another one. Yeah, I noticed that you can get extra or you can get certified Lexus unexpected routes in your, in your Solutions. So can you have a bond on the number of routes that could be produced to expects destination? Yes, so so I can't. I guess that's for so far send me since is a very special, the number of dominance attributes of the number of Rob's competed in that exponential in
the side of the network examples and a width and the length of the number of this number is is only because well because because you are a minimum at work. But as for the more we starting our evaluation that infects, the the the actual number for real, for real. He's very much below. This is fresh oil and butter. The opthamology okara scheme for the, for the state that is kept on the, on the complexity of the storage that picture.
Buy this talk
Ticket
Interested in topic “IT & Technology”?
You might be interested in videos from this event
Similar talks
Buy this video
Conference Cast
With ConferenceCast.tv, you get access to our library of the world's best conference talks.