Rudiments of Routing

Moving bits from the source to the destination is a major function of computer
networking. On the current Internet, the Network layer is responsible for achieving this.

AS 2

AS 1

Inter-domain routing
OSPF and RIP
Inter-domain routing
OSPF and RIP

Intra-domain routing
BGP

In general, most routing within Autonomous Systems use Routing Information Protocol
(RIP), or its enhanced version Open Shortest Path First (OSPF). The current de facto
Intra-domain routing standard is Border Gateway Protocol(BGP),Version 4 (RFC 4271) .
You need to concern yourself with these protocols if you are dealing with routers inside
or between Autonomous Systems.

Most currently implemented routing protocols between routers use either the Link-State
algorithm, which is based on the famous Dijkstra's algorithm in Graph Theory, or the
Distance-Vector algorithm, based on the Bellman-Ford equation.

At the host level, however, most likely you need only a static routing table. This is a
table of routes that the OS kernel keeps. It is possible to add to and delete from routes in
the kernel routing table relatively easily. We discuss routing tables based on RIP
(RFC2453).
The routing tables are operating-system dependent. On linux-based systems, the netstat
command with a -r flag will give the routing table. On Windows machines, route print on
a command prompt will show the routing table. Below are two linux-OS outing tables
and a Windows 10 routing table.
When looking at routing tables, remember that most Unix-like operating systems use
mnemonic names for their interfaces. In the first two images of routing tables above, the
Iface column has names enp0s25 and eth0 respectively. These are the mnemonic names of
the network interfaces attached to the hosts.

You can see all the configured interfaces on a linux host using the ifconfig command
which is usually found in /sbin/ directory (but not always). On Windows machines, you
can run the "ipconfig /all" command in a command terminal to see all the configured
interfaces (plus other information). On both Linux and Windows (I think!), you can see
the routing table with “netstat -r” command.

The output from /sbin/ifconfig command on a linux machine below shows that there are
four configured interfaces, one an Ethernet (enp6s0), another for a docker
instance(docker0) and a VPN tunnel (cscotun0) interface, and the loopback interface (lo).

The real physical interface in the above figure is the ethernet interface – the others are
conceptual devices that use the ethernet. We have already seen the loopback interface
before.
In the following, we generally omit loopback interfaces for convenience.

Let us look at the routing table on a linux host carefully:

Destination Gateway Genmask Flags MSS Window irtt Iface

[Link] [Link] [Link] U 0 0 0 virbr0
[Link] [Link] [Link] U 0 0 0 eth0
[Link] [Link] [Link] U 0 0 0 eth0
[Link] [Link] [Link] UG 0 0 0 eth0

The first line says that the network [Link]/24 can be reached by directly sending
to virb0 interface - this is how we reach virtual machines on this host. The second line
says that [Link]/23 can be reached directly sending to eth0 interface. The flag U
here means that the interface is “UP”. We know the netmask is 23 because of the
[Link] entry under Genmask.

The third line, [Link]/16 is a special class of IP link-local addresses

using the draft Zeroconf standard. Zeroconf is better known in its incarnation as Apple's
Rendezvous. Routes like this one are stop-gap responses that allow Linux to somewhat
participate in Zeroconf/Rendezvous networks. For more information, look at
[Link].

The fourth line is the catch-all route. It says that if the above three lines fail to give a
route, send the packet to [Link]. This is called the default route and the gateway
machine is called the default router. The UG flags mean that the route is UP and that the
destination is a network not directly connected to this interface. Note that from the first
line we already know how to get to [Link] – simply send to eth0 interface.
[Link] must be directly on the wire.

Routing table flags.

Usually, in most simple host routing tables on linux/Unix hosts, one sees three sets of
flags - U, G and H. U means route is up, G means the destination is a network not directly
connected to us, and H means the destination is a host IP. So for example, a routing table
entry with flags UGH means the the destination in the entry is a host IP on a network not
directly attached to us. UH flags mean that the destination is a host IP directly attached to
us.
Routing table – another example

Consider another example:

Kernel Routing Table

Destination Gateway Genmask Flags Metric Ref Use Iface
[Link] [Link] [Link] UGH 1 0 180 eth1
[Link] [Link] [Link] UGH 1 0 187 eth1
[Link] [Link] [Link] U 0 0 63311 eth1
[Link] [Link] [Link] U 0 0 753430 eth0
[Link] [Link] [Link] UG 1 0 47543 eth1
[Link] [Link] [Link] UG 1 0 89011 eth1
[Link] [Link] [Link] U 0 0 564 lo
[Link] [Link] [Link] UG 1 0 183436 eth1

Let's interpret the line highlighted in blue. It says that if the destination of a datagram is
[Link]/18, then send it to [Link]. In other words, if the first 18 bits of a
destination IP matches that of [Link] (that is: 11000000 10101000 01), then send it
to [Link]. For instance, if this host wants to send a datagram to [Link],
the datagram should be routed to [Link], because the first 18 bits of
[Link] matches this rule.

Notice how genmask (or netmask) is used in the above interpretation. Look at the line
highlighted in yellow. This rule says that if all 32 bits match those of [Link], send
to [Link] - in other words, if you want to send a datagram to the IP [Link],
send to [Link].

As an exercise, try to construct the network topology attached to the router whose routing
table is given above.
 Another example.

Consider a scenario as follows. You have a machine R with two Ethernet network cards
eth0 and eth1; one is hooked up to your cable modem as shown, and the other interface is
connected to a hub to which hosts A, B and C also connect.
[Link] A

[Link]/22
HUB
eth0 eth1
[Link] B R Cable modem

[Link] C
[Link]/24

This is a set up you can use if you do not have a commercial Cable/DSL router. In fact,
home routers are simple machines like R in the figure above, running linux and a web
server for system administration.

What will be the routing table on R? It should specify that all packets to [Link]/24
should be sent to eth0 interface. All packets to [Link]/22 network should be sent to
eth1 interface (explain this!). Everything else should be sent to a default gateway that
your ISP specifies, say [Link]. The routing table looks somewhat like this:
Destination Gateway Genmask Flags MSS Window irtt Iface
[Link] [Link] 255.255.255.0U 0 0 0 eth0
[Link] [Link] 255.255.252.0U 0 0 0 Eth1
[Link] [Link] [Link] UG 0 0 0 Eth1

The IP, netmask, default gateway, as well as domain name servers are specified by your
ISP, mostly through DHCP (Dynamic Host Control) protocol.

What would the routing table of a host like A look like? It's quite simple:

Destination Gateway Genmask Flags MSS Window irtt Iface

[Link] [Link] 255.255.255.0U 0 0 0 eth0
[Link] [Link] [Link] UG 0 0 0 eth0

This says that to send to [Link]/24 network, just send to the eth0 interface, send
everything else to [Link] (which we know how to get to from the previous line).

Within R, eth0 and eth1 interfaces should be configured to forward packages to each
other.
If A in the above diagram needs to send a datagram to [Link], A's IP will look
up the routing table, and see that the datagram should b sent to its default gateway,
[Link]. Note that this does not mean that the destination IP in the IP header will
be [Link] – that will still be [Link]. That the immediate next hop is
[Link] is relevant only to the link layer, as we will see soon.

Bringing up an interface (the following applies only to linux/unix hosts).

On most Unix/Linux machines, the ifconfig command can be used to bring up and
shutdown network interfaces. For example, the following command brings up the eth1
interface and assigns it an IP:

root>/sbin/ifconfig eth1 [Link] netmask [Link] up

Similarly you can shutdown an interface by

root>/sbin/ifconfig eth1 down

Manually building and deleting routing table entries

The route command is used to do both of these operations.

For example, to add a default gateway manually, do

root> route add default gw [Link] netmask [Link]

To delete the default route, do

root>route del default

The man pages for route and ifconfig commands give a number of command line options
you can use with these commands.
Exercise: In the following network scenario, construct routing tables for R1, R2, A and
D. Packets from every host should be able to reach [Link]/24 and [Link]/24
networks, as well as the outside Internet through a default gateway [Link].

[Link]/24
B eth0
[Link] R1
Internet
Hub
[Link]/24
eth1
[Link]
A

[Link](eth0) C
[Link]
R2
[Link]
Hub D
[Link]/24(eth1)

Additional material on Linux IP layer routing can be found at

[Link]