Graphs at Work. At school. And in other places, too.

Switching gear and getting lower in the IP stack, I introduced graphs as used in IP networking in general, and in OSPF in particular. With the advent of namespacing in the Linux kernel, it is possible to operate a large number of independent routing tables in a single host, therefore making it easy to simulate relatively complex network behavior. I borrowed the very good work from Edwin Cordeiro and fixed it for recent versions of Ubuntu (18.04 LTS) and Mininet.

OSPF Network

A single VM can simulate a decent network with several hosts (h010_*) and routers (r010_*), with a very limited memory and CPU footprint. For a limited investment, we can enter the brave world of Link State Advertisement and Shortest Path First (as known as Dijkstra).

We can connect to the Zebra daemon in random routers, and start by investigating how routing works for directly-connected hosts.

$ sudo nsenter -n -t $(cat /tmp/zebra-r010_1.pid) telnet localhost zebra
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
Hello, this is Quagga (version 1.2.4).
Copyright 1996-2005 Kunihiro Ishiguro, et al.
User Access Verification
Password:
r010_1> enable
Password:
r010_1# show ip route connected
Codes: K - kernel route, C - connected, S - static, R - RIP,
O - OSPF, I - IS-IS, B - BGP, P - PIM, A - Babel, N - NHRP,
> - selected route, * - FIB route
C>* 10.0.0.0/30 is directly connected, r010_1-eth4
C>* 10.0.0.4/30 is directly connected, r010_1-eth5
C>* 10.1.0.0/24 is directly connected, r010_1-eth3
C>* 10.10.0.1/32 is directly connected, lo
C>* 10.255.0.0/30 is directly connected, r010_1-eth1
C>* 10.255.0.16/30 is directly connected, r010_1-eth2
C>* 127.0.0.0/8 is directly connected, lo
r010_1#

What OSPF allows is for each router to know how to reach each of the networks advertised, i.e. to compute the next router that should be used to reach a remote network. In the example below, r010_1 learned from OSPF that it should send packets destined to 10.2.0.0/24 (a network behind r010_2) via its neighbor 10.255.0.2 through its eth1 interface.

r010_1# show ip route ospf
Codes: K - kernel route, C - connected, S - static, R - RIP,
O - OSPF, I - IS-IS, B - BGP, P - PIM, A - Babel, N - NHRP,
> - selected route, * - FIB route
O>* 10.2.0.0/24 [110/20] via 10.255.0.2, r010_1-eth1, 00:44:36
O>* 10.3.0.0/24 [110/20] via 10.255.0.2, r010_1-eth1, 00:44:36
O>* 10.4.0.0/24 [110/20] via 10.255.0.17, r010_1-eth2, 00:44:36
O>* 10.5.0.0/24 [110/20] via 10.255.0.17, r010_1-eth2, 00:44:41
O 10.10.0.1/32 [110/0] is directly connected, lo, 00:45:27
O>* 10.10.0.2/32 [110/10] via 10.255.0.2, r010_1-eth1, 00:44:37
O>* 10.10.0.3/32 [110/20] via 10.255.0.2, r010_1-eth1, 00:44:37
O>* 10.10.0.4/32 [110/20] via 10.255.0.17, r010_1-eth2, 00:44:37
O>* 10.10.0.5/32 [110/10] via 10.255.0.17, r010_1-eth2, 00:44:42
O 10.255.0.0/30 [110/10] is directly connected, r010_1-eth1, 00:44:47
O>* 10.255.0.4/30 [110/20] via 10.255.0.2, r010_1-eth1, 00:44:37
O>* 10.255.0.8/30 [110/30] via 10.255.0.2, r010_1-eth1, 00:44:37
* via 10.255.0.17, r010_1-eth2, 00:44:37
O>* 10.255.0.12/30 [110/20] via 10.255.0.17, r010_1-eth2, 00:44:42
O 10.255.0.16/30 [110/10] is directly connected, r010_1-eth2, 00:44:42

We end up with end-to-end connectivity, a key property of IP networks that is never overvalued. Yes, IPv4 NAT, I am targeting you. We can then examine end-to-end paths across the network:

mininet> h010_51 traceroute h010_31
traceroute to 10.3.0.2 (10.3.0.2), 30 hops max, 60 byte packets
1 10.5.0.1 (10.5.0.1) 0.060 ms 0.005 ms 0.004 ms
2 10.255.0.13 (10.255.0.13) 0.015 ms 0.005 ms 0.005 ms
3 10.255.0.9 (10.255.0.9) 0.017 ms 0.007 ms 0.006 ms
4 10.3.0.2 (10.3.0.2) 0.024 ms 0.008 ms 0.007 ms

Welcome in the magic of distributed systems, where nodes eventually reach a consensus on how they should behave individually so that the overall system performs the desired end-to-end routing function.

read original article here