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