To understand how IP routing works, we must first begin with the structure of IPv4 addresses. As described in the last section, these are 32 bits in length. They are written in a dotted decimal notation in groups of 4 bytes (for example, 192.168.122.5). A given number of bits in that network prefix is used to identify the network where the packet should be delivered, and the rest of the bits identify the particular host. Thus, all hosts in the same network must have the same prefix. Conventionally, the prefix is described in the CIDR notation with the starting address and the number of bits in the network portion of the address separated by a slash (192.168.122.0/30). The number can then be used to find out how many addresses are available for hosts in the network (in this case, 2^(32-30) = 4). Given an IP address and a prefix, the network address can be extracted by bitwise-ANDing the address with a mask of all 1s in the network portion. Calculating the host address is just the reverse; we will need to AND with the network mask's logical negation (the host mask), which has all 0s in the network portion and all 1s in the host portion. Given an address and a prefix like 192.168.122.5/27, we will compute these as shown in the following figure. Thus, for the given CIDR, the network address is 192.168.122.0 and the host address is 0.0.0.5:
There are two broad classes of IP address; some blocks of addresses can be routed in the public internet, these are called public IP addresses. Some other blocks can only be used in private networks that do not directly interface with the internet, these are called private addresses. If a router on the internet receives a packet that is destined for a private IP address, it will have to drop that packet. Other than these two, IP addresses are also classified on various parameters: some are reserved for documentation only (192.0.2.0/24), some are reserved for point to point communication between two hosts (169.254.0.0/16), and so on. The Rust standard library has convenience methods to classify IP addresses according to their types.
All routers maintain a routing table which maps prefixes to the outgoing interface of the router (while a router administrator might decide to store individual addresses instead of prefixes, this will quickly lead to a large routing table in a busy router). An entry in the table basically says If a packet needs to go to this network, it should be sent on this interface. The next host that receives the packet might be another router or the destination host. How do routers figure out this table? Multiple routers run routing protocols between those which compute those tables. Some common examples are OSPF, RIP, and BGP. Given these primitives, the actual routing mechanism is fairly simple, as shown in the next diagram.
An interesting aspect of IP is the use of the Time To Live (TTL) field, this is also known as hop limit. The host sends out packets with a fixed value of TTL (usually 64). Each router the packet crossed decreases the TTL. When it reaches 0, the packet is discarded. This mechanism ensures that packets are not stuck in an infinite loop between routers:
Note that while trying to match the prefix to routes in the routing table, multiple routes might match. If that happens, the router must select the most specific match and use that for forwarding. Since the most specific routes will have the maximum number of leading 1s, and hence the largest prefix, this is called the longest prefix match. Say our router has the following routing table, as shown in the diagram. eth1, eth2, and eth3 are three network interfaces attached to our router, each having a different IP address in different networks:
At this point, if our device gets a packet that has a destination address set to 192.168.1.33, all three prefixes have this address but the last one is the largest of the three. So, the packet will go out through eth3.
A lot of what we described so far about IPv4 addresses does not change for IPv6, except, of course, it has a larger address space of 128 bits. In this case, the length of the network mask and the host mask depends on the address type.
One might be wondering, how do routers construct the routing table? As always, there are protocols to help with that. Routing protocols are of two major types: interior gateway protocols which are used for routing inside an autonomous system, and exterior gateway protocols which are used in routing between autonomous systems; an example of the latter is BGP. Interior gateway protocols can again be of two types, depending on how they look at the whole network. In link state routing, each router participating in the protocol maintains a view of the whole network topology. In distance vector routing, each router only knows about its one hop neighbors. An example of the former is the Routing Information Protocol (RIP) and of the latter is Open Shortest Path First (OSPF). Details about these are beyond the scope of this book. However, we can note that the common theme among all the routing protocols is that they work by exchanging information between routers. Thus, they have their own packet formats for encapsulating that information.
