Internal Gateway Protocols share information with one another such that every router has a complete make of the network they’re a part of. This way, each router can make autonomous routing decisions given an IP address. No matter where it’s going, the router can always forward the packet in the right direction.
IGPs like Open Shortest Path First (OSPF) use Dijkstra’s Algorithm to find the shortest path along a weighted graph.
In this project, we’re going to simulate that routing. Were going to implement Dijkstra’s Algorithm to print out the shortest path from one IP to another IP, showing the IPs of all the routers in between.
We won’t be using a real network for this. Rather, your program will read in a JSON file that contains the network description and then compute the route from that.
Graphs are made of vertices and edges. Sometimes vertices are called “vertexes” or “verts” or “nodes”. Edges are connections from one node to another.
Any node on the graph can be connected to any number of other nodes, even zero. A node can be connected to every single other node. It could even connect to itself.
An edge can have a weight which generally means the cost of traversing that edge when you’re walking a path through the graph.
For example, imagine a highway map that shows cities and highways between the cities. And each highway is labeled with its length. In this example, the cities would be vertices, the highways would be edges, and the highway length would be the edge weight.
When traversing a graph, the goal is to minimize the total of all the edge waits that you encounter along the way. On our map, the goal would be to choose edges from our starting city through all the intermediate cities to our destination city that had us driving the minimum total distance.
Edsger Dijkstra (DIKE-struh) was a famous computer scientist who came up with a lot of things, but one of them was so influential it came to be known by only his name: Dijkstra’s Algorithm.
Protip: The secret to spelling “Dijkstra” is remembering that “ijk” appears in order.
If you want to find the shortest path between nodes in an unweighted graph, you merely need to perform a breadth-first traversal until you find what you’re looking for. Distances are only measured in “hops”.
But if you add weights to the edges between the nodes, BFT can’t help you differentiate them. Maybe some paths are very desirable, and others are very undesirable.
Dijkstra’s can differentiate. It’s a BFT with a twist.
The gist of the algorithm is this: explore outward from the starting point, pursuing only the path with the shortest total length so far.
Each path’s total weight is the sum of the weights of all its edges.
In a well-connected graph, there will be a lot of potential paths from the start to the destination. But since we only pursue the shortest known path so far, we’ll never pursue one that takes us a million miles out of the way, assuming we know of a path that is shorter than a million miles.
Dijkstra’s builds a tree structure on top of a graph. When you find the shortest path from any node back toward the start, that node records the prior node in its path as its parent.
If another shorter path comes to be found later, the parent is switched to the new shorter path’s node.
Wikipedia has some great diagrams that show it in action11.
Now how do make it work?
Dijkstra’s itself only builds the tree representing the shortest paths back to the start. We’ll follow that shortest path tree later to find a particular path.
to_visit set. This is the set of all nodes we still need to visit.distance dictionary. For any given node (as a key), it will hold the distance from that node to the starting nodeparent dictionary. For any given node (as a key), it lists the key for the node that leads back to the starting node (along the shortest path).parent to None.distance to infinity. (Python has infinity in math.inf, but you could also use just a very large number, e.g. 4 billion.)to_visit set.0.to_visit isn’t empty:
to_visit with the smallest distance. Call this the “current node”.to_visit set.to_visit:
distance:
distance to the computed distance.parent to the current node.Wikipedia offers this pseudocode, if that’s easier to digest:
1 function Dijkstra(Graph, source):
2
3 for each vertex v in Graph.Vertices:
4 dist[v] ← INFINITY
5 prev[v] ← UNDEFINED
6 add v to Q
7 dist[source] ← 0
8
9 while Q is not empty:
10 u ← vertex in Q with min dist[u]
11 remove u from Q
12
13 for each neighbor v of u still in Q:
14 alt ← dist[u] + Graph.Edges(u, v)
15 if alt < dist[v]:
16 dist[v] ← alt
17 prev[v] ← u
18
19 return dist[], prev[]At this point, we have constructed our tree made up of all the parent pointers.
To find the shortest path from one point back to the start (at the root of the tree), you need to just follow the parent pointers from that point back up the tree.
path to be an empty array.path.parent of current nodeOf course, this will build the path in reverse order. It has to, since the parent pointers all point back to the starting node at the root of the tree. Either reverse it at the end, or run the main Dijkstra’s algorithm passing the destination in for the source.
Part of the algorithm is to find the node with the minimum distance that is still in the to_visit set.
For this project, you can just do a O(n) linear search to find the node with the shortest distance so far.
In real life, this is too expensive–O(n²) performance over the number of vertices. So implementations will use a min heap which will effectively get us the minimum in far-superior O(log n) time. This gets us to O(n log n) over the number of verts.
If you wish the additional challenge, use a min heap.
[All IP addresses in this project are IPv4 addresses.]
Download the skeleton code ZIP here12.
OK, so that was a lot of general stuff.
So what does that correspond to in the project?
You have to implement this function:
def dijkstras_shortest_path(routers, src_ip, dest_ip):The function inputs are:
routers: A dictionary representing the graph.src_ip: A source IP address as a dots-and-numbers string.dest_ip: A destination IP address as a dots-and-numbers string.The function output is:
Code to drive your function is already included in the skeleton code above. It will output to the console lines like this showing the source, destination, and all routers in between:
10.34.46.25 -> 10.34.166.228 ['10.34.46.1', '10.34.98.1', '10.34.166.1']The graph dictionary in routers looks like this excerpt:
{
"10.34.98.1": {
"connections": {
"10.34.166.1": {
"netmask": "/24",
"interface": "en0",
"ad": 70
},
"10.34.194.1": {
"netmask": "/24",
"interface": "en1",
"ad": 93
},
"10.34.46.1": {
"netmask": "/24",
"interface": "en2",
"ad": 64
}
},
"netmask": "/24",
"if_count": 3,
"if_prefix": "en"
},
# ... etc. ...The top-level keys (e.g. "10.34.98.1") are the router IPs. These are the vertices of the graph.
For each of those, you have a list of "connections" which are the edges of the graph.
In each connection, you have a field "ad" which is the edge weight.
“AD” is short for Administrative Distance. This is a weight set manually or automatically (or a mix of both) that defines how expensive a particular segment of the route is. The default value is 110. Higher numbers are more expensive.
The metric encompasses a number of ideas about the route, including how much bandwidth it provides, how congested it is, how much the administrators want it used (or not), and so on.
The netmask for the router IP is in the "netmask" field, and there are additional "netmask" fields for all the connection routers, as well.
The "interface" says which network device on the router is used to reach a neighboring router. It is unused in this project.
"if_count" and "if_prefix" are also unused in this project.
The skeleton archive includes an example input file (example1.json) and expected output for that file (example1_output.json).