okay, BGP is the border Gateway protocol, and it’s, it’s a routing protocol that evolved in the internet and It’s, you can think of it as kind of the the top of the food chain in terms of routing in the internet It’s the it’s the protocol that’s used to connect the Service providers let’s say primarily in the internet, so how does AT&T exchange reachability information with bt with France telecom with you know and they have to exchange This kind of reach ability information, so that we can glue that these Autonomous Networks together Because there is no one there is no centralized control in the internet you know so bt Controls its equipment And it’s part of the internet But AT&T controls its part of its own part of the internet and they have to interoperate somehow they have to be able to Exchange information about the IP addresses associated with their customers and Etc So the border Gateway protocol BGP is this protocol that has evolved to handle that job, right, to exchange information between Autonomous networks okay, so without any centralized control.
There are many interesting engineering problems, [they’re] interesting research problems in terms of scalability and robustness ETC And but I’m going to talk about it in really sort of elementary terms and I want to I want to be I want to talk about a simple graph problem as a reachability problem in graphs in simple combinatorial graphs with where we have nodes and Arcs And we want to get from one place to another. You send a packet to your service provider It has to look in a table and figure out where to send that next and that packet may end up on the other side of the globe in a completely different network and and so it’s that level you know it’s it’s How to get from here to there, so it’s the foundations of the internet It’s the basic global foundation of the internet.
Different protocols are used within these autonomous networks And I think more talked about that in a previous computer file, and you know for example You might use some kind of shortest path based thing within a network, but between networks what’s interesting about this is that You know we want this inter domains or you know regional Autonomous networks we want this routing to interoperate to work even when The service providers don’t have common agreement about what is the best route for example? You know your best route might not look like my best route because we have different contracts With with different companies in the internet, and so we have different we will have different ideas about what is best Okay.
So that might be a commercial thing it might be our you know I don’t want you to send too much traffic through me because it’s going to cost me money to look that’s right right and basically the idea is that when you’re doing shortest path routing you want you know you want everybody to be connected with everybody and along the shortest path and in the internet you want you don’t want traffic to be crossing your network unless somebody’s paying you for that either the source of the traffic or the destination or a combination right somehow and so in other words the the protocol is more about limiting the Connectivity rather than You know being generous about it and giving it to everyone It’s kind of let’s restrict this connectivity to those that are paying for it somehow.
That’s basically the idea but What I want what I want to think about is well, How does this fit into our notion of finding paths in a graph? because in the undergraduate Computer science one of the things we teach in algorithms courses is you know a lot of shortest path algorithms.
So we we define a graph let’s say that is nodes and Arcs And you have a weight on these arcs and then you try to find the best paths between every pair of Arcs Let’s say and we typically teach this and we teach lots of algorithms for doing this like Dijkstra’s algorithm Bellman-Ford Warshall’s Algorithm so can we abstract away from the complexities of BGP and think about it in those terms? The thing is it doesn’t quite fit in our models very well and and and I’ll try to explain Informally why not -Well what doesn’t fit the BGP or what doesn’t fit? Okay? So we normally think about shortest paths in terms of numeric values Okay.
So and we typically add those values as we go along a path Right, so maybe maybe each Arc has a weight one and we essentially count the number of hops that we’re going Through a path and then we would prefer Let’s say a shorter path one with fewer hops than a longer one so we’re what we’re using there are two operations plus and Maybe an operation let’s call it min Okay, so we have these operations min and plus so min for minimum Yeah, plus for adding up those hops yeah, right, and so what people notice that about 40 years ago Is that a lot of these algorithms that we have for shortest paths Dijkstra’s algorithm bellman-Ford can be generalized to a large class of Algebraic structures called Semi rings. I’m gonna show you.
What is a really stupid question I’m sure okay semi ring I’m not familiar with a semi ring, okay? So a semi ring is a algebraic structure that looks like a ring So what is a ring a ring is something like the real numbers, so we have domain the real numbers and we have a plus and a times they are plus and times the the Standard operations and A Linear Algebra is built on Rings where actually we take Matrices we multiply matrices we solve Matrix equations things like that That’s all linear Algebra.
Well it turns out that semi rings and routing is also. It’s kind It’s kind of like a generalization of that where we we weaken the properties that the the plus and the times have to have Right so for example a ring That plus has inverses we have negative numbers.
So there’s always a For every a there’s a not there’s a negative a that when you add them together you get zero Okay, and the semi ring is like a ring except it doesn’t have that inverse property you don’t necessarily have inverses what people did back In the 60s and 70s is they looked at algorithms like Dijkstra’s algorithm like Bellman-Ford, and then they said wait a minute. Let’s work backwards let’s look at these we see min and plus in the algorithms, but let’s replace them by abstract operators and Let’s see what algebraic properties. We need to make this algorithm work still suppose.
We want to pick paths that have the highest capacity Okay, so we might instead of using plus. We might go along a path Using min the weight of a path will be the minimum capacity Link And then instead of using min to compare paths we might want to use max so that would give us the highest capacity path Okay, so people noticed.
Oh wait a minute. You know this min plus and this max min They have certain algebraic properties that are true, and we can we can take Dijkstra’s algorithm, and we can replace the plus With min and replace the min with max and now we have an algorithm that does it works perfectly fine now it Now it finds the highest capacity paths in the graph, and then we can build other things for example suppose I wanted to find paths that were shortest, but if I had two paths that were equally short Maybe I want to break ties with capacity ok so then now I could have a path with two metrics.
You know distance Capacity right and then I could essentially You know a use shortest paths on that first component and then break ties with capacity Okay That to that that that turns out you can make a semi ring out of this and then guess what you can use Dijkstra’s algorithm Bellman-Ford to compute with these as well if you compare things you know first distance then capacity kind of its kind of A Lexicographic comparison there you can build a semi ring out of that and then and so these these algorithms are really Generic you can just plug in You can plug in You know just an unbounded number Of different algebraic structures to get what you want and use the same algorithms Bellman-Ford or Dijkstra ETC, so this might seem like oh now.
We have this open-ended world Maybe we can model something like BGP in this world turns out we can’t okay and let me give you an example of That’s easy easier to understand than BGP. Okay. I told you we could do We could we could look at distance first then break ties with bandwidth suppose. We or capacity let’s suppose We did it the other way around. I want the highest capacity path and if I have two best paths With high capacity I want to break ties then on the distance So I first look at the at the capacity component, then I break ties on distance That’s not a semi ring anymore Why is that? Oh? It’s not obvious that you know if you use some of these generic Best path algorithms, it’s something’s going to break.
Maybe why is that? not obvious, but it turns out that one of the rules of that needs to be followed by a semi ring is something called just Distributivity this is an algebraic property what it really means is that you know It doesn’t really matter if I make a decision about the best path seeing all my past or you my neighbor You make the decisions, and you tell me what your best path is it kind of doesn’t really matter Because we’ll come to the same We’ll come to the same conclusion right, so that’s what distributivity is all about and This this thing I told you about you know shortest path then capacity that has that property still But when I turn it around when I do capacity first and then shortest paths it breaks that property Okay, and let me just give you an example of why suppose.
I have a neighbor That sees two paths: one’s very high Bandwidth But also a very long path right and it sees another one with very low bandwidth or capacity But it has a short path And then I am talking to my neighbor over a very low capacity link so my neighbor picks that high capacity long Path, but I see two. Paths and I say wait a minute. This is kind of like a bottleneck link Is sort of wipes out the the capacity you know it’s the the capacity of both paths is now the capacity of this really lousy link as far as I’m concerned both of those paths that my neighbor is giving me have the same capacity because I have this bottleneck link with very low capacity.
So I’m going to break ties on the length And I’m going to break ties I’m going to want that shortest path, but my neighbor picked the longer path because it had a higher capacity But I don’t see that you see so we’re going to be disagreeing about this, okay so a similar thing happens in the internet for example If I’m a paying customer of a route of a path, let’s say, I’m paying Upstream, I’m paying for this route, but my neighbor is a service provider One of those paths it’s not paying for because it’s a it’s their customer another path It’s paying for you know. It’s up It has an upstream provider so that that that Path could be my neighbor would like the longer path because it’s a from a paying customer From an economic point of view they like that longer path but I I see the two routes as well.
They’re both Provider paths, they’re both equally bad in that sense, so I’ll pick the shorter one, so we don’t agree There’s one thing I should say about internet routing that I was I’ve been sort of taking for granted without Really making it explicit and that is 99% of internet Routing Protocols only They they they’re their traffic insensitive? Okay, that is they’re perfectly willing to route all the traffic along the most congested link in the internet Okay, in other words.
They don’t route around congestion So this is the traffic difference between right yeah, and so telco Protocols routed around things like congestion, but internet protocols have tradition. There are a few exceptions but generally Protocols like BGP OSPF is is and and RIP do not route around congestion That’s considered sort of a network that’s at done that network management timescales So a network manager will see oh, we have congestion over there.
Let’s adjust the link weights So that the traffic will be more or divergent the protocol doesn’t do that the protocol just Blindly follows those link weights those statically configured link weights it’s not sensitive to traffic characteristics, and this is because in the internet those characteristics tend to change a lot and oscillate a lot and they tend to often oscillate in a At a faster rate than the control plane can keep up with and so you you when you try to adapt dynamically to congestion you tend to introduce a lot of instability in the Routing plane and So these things are you know completely insensitive to to traffic conditions like congestion It’s up to the network managers to set those statically configured link weights to Avoid congestion So this is more like the road size.
They tell you where those things go. Yes, they don’t change yes I think internet forwarding is a lot like those signs that just point you in that direction You know paris is in that direction. Go if you’re heading towards Paris Go that way a complicated thing of course is that when we have now these regions that are divided up into Autonomous regions that have very different goals But they’re forced to interact all right BT is forced to exchange routes with AT&T because they’re selling The service of Global internet Connectivity, so they’re forced to interact with their competitors They they’d like to control the entire internet. I’m sure but they can’t There’s a balance you want to Allow each network to tailor its let’s call them routing policies or routing policies Sorry, I’ve been in the uk for 12 years, so I’m saying routing now