Layer 3 – IPv4 Routing Part I

While Switches help to transfer packets inside a layer 2 Broadcast Domain, Routers switch the packets between Broadcast Domains. For this the Router uses also a table like the Switches called the Routing Table. Routing is the process of determining where to send data that are destined for devices outside the Broadcast Domain.

Routers are the devices which function at layer 3 of the OSI model, which are responsible for finding the optimum path to a network thereby forming a logical path between 2 hosts. The Routers use a database called the Routing Table or Routing Information Base (RIB) to determine which path to take for a given destination network.

Functions of Router:

The two basic functions of a Router are:

o Packet forwarding
o Path determination

Packet switching:

Routers use the Routing Table to determine, which the exit interface for an outgoing packet is. The Routing Table or Routing Information Base (RIB) is the database where a network is mapped to the exit interface or IP address of another router (Next Hop). The Routing Table consists of network entries with their network or subnet masks. The router reads through the RIB to find the best match to reach the destination IP address.

After finding the next hop IP address, the router changes the layer 2 source and destination addresses, then switch the frame out of the corresponding interface. If the receiving device is a Router, it does the same routing Table lookup to find where to forward the Packet. This packet forwarding function of the router is controlled by the Data Plane.

Path determination:

When a packet arrives at a Router which is destined for a remote network, it must be able to route the packet necessarily. To route a packet, the router must be able to read the destination IP address from the IP header and know how it can reach the destination network. For this it must have an entry for the destination network in its Routing Table.

An entry can be added manually or dynamically to the Routing Table. Routing Table are dynamically populated by using different routing protocols like OSPF, RIP, EIGRP, BGP etc. These protocols exchange Networks information with other routers in the network. Statically populating the Routing Table does not scale and leads to problems like routing of packets to black hole, which could increase the convergence time. The routing protocols which dynamically make the router to route belong to the Control Plane of the router.

How does a Router operate?

When a packet arrives at the Router, it reads the destination address of the packet. If the destination network is not connected to the router, it has to forward the packet to another router. For this it does a routing table lookup. Once a match is found, the packet is encapsulated in the layer 2 data link frame for that outgoing interface.

Eventually the packet reaches a router that is part of a network that matches the destination IP address of the packet. To reach a destination network, all routers in the path must have a routing table entry. If any one of the routers does not have a route to a given destination, it will send a destination unreachable ICMP message to the host which generated the packet (sender).

Routing Table:

A Router uses its Routing table or Routing Information Base (RIB) to switch packets between Broadcast Domains. Routing Table is a data file in RAM that is used to store route information about directly connected and remote networks. The RIB consists of networks to “next hop” mappings. These mappings tell a router that a particular destination can be optimally reached by sending the packet to a specific router that represents the ‘next hop’ on the way to the final destination. An interface can also be specified as ‘next hop’; in this case it is called the exit interface for the destination network.

The RIB consists of network IDs. A network ID is used to represent a network. A network could be either directly connected to the router or remote network. A directly connected network is a network that is directly attached to one of the routers interface. When a router interface is configured with an IP address and network mask, this interface becomes a host on that attached network. The network ID and network mask of the interface, along with the interface type and number, are entered into the routing table as a directly connected network.

A remote network is a network that is not directly connected to the router. A remote network is a network that is only reachable by sending the packet to another router. Remote networks are added to the routing table using either a dynamic routing protocol or by configuring static routes. Technically speaking all IP configured devices does have a routing table.

Basic Network Layer terms:

Before getting into the details of how a router does the packet forwarding process in a network, we need to understand some basic terms of the network layer.

IP address: The IP address is the addressing scheme in the Layer 3 of the OSI. Each host in the network must have a unique IP address. The IP address is 32 bits long and is grouped in 4 blocks. Each block consists of 8 bits (1 octet) and is separated with a dot. An IP address is divided into 2 parts, the network part and the host part. The network mask determines where the network part ends and the host part begins. An IP address can be used to represent a Host ID, Network ID or a Broadcast ID.

Network ID: An IP address which is used to identify an entire network is the Network ID. The IP address is divided into 2 parts, the network part and the host part. The network ID is the first possible IP address from a given network. By definition the Network ID will have its entire host bits set to ‘0’. The use of network IDs is mostly found in the routing table. The router just cares for the network ID when it has to switch packets between Broadcast Domains.

Broadcast ID: This is the IP address, which is used to send a Broadcast on a network. When a host wants to communicate with all the hosts in the broadcast domain, it can use this IP address as the destination address. By definition the Broadcast ID will have its entire host bits set to ‘1’. When a host sends a layer 3 broadcast, it will be encapsulated in a frame and destined to the layer 2 broadcast address.

IP address classes: IP addresses are organized into classes. The address class determines the potential size of the network. The classes specify which of the bits are used to identify the Network or which of the bits are used to identify the Host. There are five classes of IP addresses, classes A through E.

Table 4.1 IP Address Classes

Class		IP Address Range	Leftmost Bits	Network Mask	Slash notation
	A	0.0.0.0-127.255.255.255	0XXXXXXX	255.0.0.0	/8
	B	128.0.0.0-191.255.255.255	10XXXXXX	255.255.0.0	/16
	C	192.0.0.0-223.255.255.255	110XXXXX	255.255.255.0	/24
	D	224.0.0.0-239.255.255.255	1110XXXX
	E	240.0.0.0-255.255.255.255	1111XXXX

Class A: Class A addresses are used in networks which have very large number of hosts. The first bit or the leftmost bit from the first byte (octet) is always set to ‘0’. Thus Class A has a total of 128 (2^{^7}) networks by using the rest 7 bits from the first octet for the Network IDs. The 24 bits in the remaining 3 octets represent the Host ID which allows 2^{^24} IPs per network. The Network ID and the Broadcast ID cannot be assigned for the hosts.

Class B: Class B addresses are used in medium to large sized networks. The first 2 bits or the leftmost bits from the first byte are always set to ‘10’. Thus Class B has a total of 16,384 (2^{^14}) networks by using the rest 14 bits from the first 2 octets for the Network IDs. The remaining 16 bits in the third and fourth octet represent Host ID which allows 65536 (2^{^16}) IPs per network.

Class C: Class C addresses are used in small sized networks. The first 3 bits or the leftmost bits from the first byte are always set to ‘110’. Thus Class C has a total of 2097152 (2^{^21}) networks by using the rest 21 bits from the first 3 octets for the Network IDs. The remaining 8 bits in the fourth octet represent Host ID which allows 256 (2^{^8}) IPs per network.

Figure 4.1 IP Address Classes

Network Mask: The Network Mask is used to identify the network part and the host part from the IP address. An IP address is always specified along with its Network mask. This helps to identify to which network the IP address belongs to. For example a Class A IP address has its first 8 bits for the Network ID and the rest 24 bits for the Host ID. Therefore the Class A has a network mask of 255.0.0.0 or it can be also written as /8 (slash notation).

Classful Network: In a Classful Network all the IP addresses that are available are divided into the five classes A, B, C, D and E, in which class A, B and C address classes are used for IP address assignment. The main disadvantage of Classful addressing is that it limited the flexibility and scalability for IP address assignment. Let us look at the following example.

An organization which is having a network consisting of 1000 hosts cannot use a single class C IP address, because it can have only 254 IP addresses assigned to hosts. A class B network would be helpful, but there is a waste of 64534 IP addresses. The scarcity of the IP addresses required for the need of a new network addressing scheme called Classless Networks.

Classless Networks: In a Classless Network the idea of classes does not exist. This is achieved by dividing a Classful Network. From the above example where the organization demands 1000 IPs for hosts, a class B network can be divided into smaller network which accommodates only the required number of IP addresses. The process of dividing a Classful network is called as Subnetting.

Subnetwork: A Subnetwork is a portion of the Classful network. A Subnetwork is created by borrowing the host bits to the network bits. When a class B network which has 16 bits for the host part borrows 8 bits to the network part, it is called Subnetting. The new network which can have a maximum of 254 hosts is called a Subnetwork. Let us look at the following example.

An organization which requires 1000 IP addresses could be assigned a Subnetwork from the main network class B. This means we need 10 bits for the hosts which yields 1024 IP addresses and 1022 usable host IPs. Thus the class B network can be subnetted in the 3^rd Octet by borrowing 6 bits from the host part to the network part. The network 150.150.0.0/16 can be subnetted to 150.150.0.0/22 and can be assigned to the organization.

Supernet: A Supernet is a network that is formed from the combination of two or more networks or subnetworks. The process of combining two or more networks or subnetworks is called Supernetting, route aggregation or route summarization. This helps to reduce the size of the routing table. This helps to reduce the time for routers to perform routing table lookup and also decreases the impact on CPU resources, memory and bandwidth consumption. This also helps for the dynamic routing protocols to perform route advertisements because they just have to send the aggregated address. We can look at the following example where Supernetting is used.

The router R1 has 4 networks, 10.0.0/24 to 10.0.3/24 in its routing table. R1 is connected to R2. R1 in this case could send a summery address or an aggregated address of 10.0.0/22 to R2 other than all of the individual subnets. This reduces the routing table size of R2 and also increases overall performance. The practice of summarizing networks whenever possible is highly advisable for scalability. To properly implement route aggregation the networks must be contiguous.

Topology Interpretation:

Figure 4.2 Hosts communicating across Broadcast Domains

In the figure 4.2 we have 3 Broadcast Domains. There are 2 routers and 2 hosts attached to them. There could also be a switch between the host and the router which is normally the case, I did not add them to make it simple. The Network IDs are marked in red, Host IDs in blue and interface name and numbers in black.

The Router R1 has 2 interfaces. The interface F0/0 is in the network which has an ID of 1.0.0.0. This can be told from ‘1/8’, as ‘1/8’ means 1.0.0.0/8 or 1.0.0.0 255.0.0.0. 1 in the first octet means that this network belongs to Class A. In the same way the interface F1/0 is in the network which has an ID of 12.0.0.0. The interface F0/0 has an IP address of .1 from the network 1.0.0.0. The interface F1/0 has an IP address of .1 from the network 12/8. The H1 has 1.0.0.1 and H2 has 2.0.0.2 as their gateways configured.

Table 4.2 Topology details

Device	IP Address	Interface	Network	Slash notation	Mask
R1	1.0.0.1	F0/0	1.0.0.0	/8	255.0.0.0
R1	12.0.0.1	F1/0	12.0.0.0	/8	255.0.0.0
H1	1.0.0.10	–	1.0.0.0	/8	255.0.0.0
R2	2.0.0.2	F0/0	2.0.0.0	/8	255.0.0.0
R2	12.0.0.2	F1/0	12.0.0.0	/8	255.0.0.0
H2	2.0.0.10	–	2.0.0.0	/8	255.0.0.0

How does a Router Operate?

Let us take the scenario from figure 4.2 where H1 wants to ping H2. The routers in the middle know of all networks in the topology. The following steps happen:

1.      H1 encapsulates the ICMP packet in an L2 frame destined to interface F0/0 of R1.
2.      R1 checks the destination IP address and then does a RIB lookup for the network 2/8.
3.      R1 finds that the destination remote network is reachable through the next hop of 12.0.0.2 (R2).
4.      R1 changes the layer 2 source and destination appropriately that it can switch the packet out of F1/0.
5.      R2 looks at the arrived packet for the destination IP address and then does a RIB lookup.
6.      R2 finds that the destination IP is directly attached to it.
7.      R2 delivers the packet to H2 after changing the layer 2 source and destination address.
8.      When H2 replies the ICMP request the same things happen to the packet.

CON output 4.1 Verifying Routing Table.

R1#sh ip route
Codes: C - connected, S - static, R - RIP, M - mobile, B - BGP
       D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
       N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
       E1 - OSPF external type 1, E2 - OSPF external type 2
       i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2
       ia - IS-IS inter area, * - candidate default, U - per-user static route
       o - ODR, P - periodic downloaded static route

Gateway of last resort is not set

C    1.0.0.0/8 is directly connected, FastEthernet0/0
S    2.0.0.0/8 [1/0] via 12.0.0.2
C    12.0.0.0/8 is directly connected, FastEthernet1/0

The output 3.1 shows the routing table from R1. You can see that R1 is directly connected to 2 networks. The network 1/8 is connected via F0/0 and 12/8 is connected via F1/0. There is also a manually configured route to the 2/8 network. This is denoted with the keyword ‘S’ which stands for Static Route.

Routing Table Lookup:

The very important key point for the RIB lookup is that a destination IP will only be matched to the best match from the given set of entries. This is also called as the longest match.

Entry #	Network	Mask	Next-hop IP/Exit interface
1	10.0.0.0	255.0.0.0	F0/0
2	10.0.0.0	255.255.0.0	192.168.1.1
3	10.0.1.0	255.255.255.0	192.168.10.1
4	10.0.1.1	255.255.255.255	192.168.10.10

Table 4.3 Routing table lookup

Consider the table 4.3 and let us check what the router does with the packets destined to various destinations.

Example 1: Packet destined for the IP 1.1.1.1
When this packet arrives at the router, it does a RIB lookup and finds that it does not have any matching entry for the IP 1.1.1.1. Thus it drops the packet and sends a destination unreachable to the sender.

Example 2: Packet destined for the IP 10.2.0.1
When this packet arrives at the router, it does a RIB lookup and finds that it can be sent out of interface F0/0 as per the entry numbered 1.

Example 3: Packet destined for the IP 10.0.2.1
When this packet arrives at the router, it does a RIB lookup and switches the packet to the next hop router at 192.168.1.1 as per the entry numbered 2.

Example 4: Packet destined for the IP 10.0.1.2
When this packet arrives at the router, it does a RIB lookup and switches the packet to the next hop router at 192.168.10.1 as per the entry numbered 3.

Example 5: Packet destined for the IP 10.0.1.1
When this packet arrives at the router, it does a RIB lookup and switches the packet to the next hop router at 192.168.10.10 as per the entry numbered 4.

Building the Routing Information Base:

The RIB, which is a database containing network entry mapped to next hops or exit interfaces stored in the Router memory. If a network is directly connected, then the router already knows how to send a packet to it. If a network is remote, the router must learn how to get to it. The Router learns about remote networks from neighbor routers or from an administrator. The router then builds a routing table that describes how to find the remote networks.

The key point here is that, each Layer 3 device in the path MUST know a path to reach the destination as stated in the destination IP field of the packet.

The Router learns about the remote network in the following ways:

o Static routing
o Dynamic routing

Static Routing:

Static routing is the simplest way to set up routing. The Router learns about the network when the administrator types in the appropriate command. They do not have to run routing protocols and thereby reducing CPU utilization. When a change occurs in the network topology the administrator has to apply the change on all the routers. Thereby the administrative overhead to maintain the network is very high.

Static routes can be implemented as backup solutions using Floating static routes. The stub Routers which are usually connected to 2 networks use a default static route to route packets to all destinations. Static routes can be configured as follows.

CON output 4.2 configuring and Verifying static route.

R1#conf t
R1(config)#ip route 2.0.0.0 255.0.0.0 12.0.0.2
R1(config)#end
R1#sh ip route static !shows only static routes
S    2.0.0.0/8 [1/0] via 12.0.0.2

Dynamic Routing:

The router learns a route dynamically using a protocol after the routing protocol is activated by the administrator. When a routing protocol is activated on a router, it is responsible for making the routing table changes as there is a network topology change. All routers participating in dynamic routing exchange update messages which are necessary to maintain the RIB.

The dynamic routing protocols can be used to route inside the autonomous system or to route between autonomous systems. An autonomous system is a group of networks under the same administrative overhead which share the same routing policies. Thus according to where they operate, the routing protocols are classified into two. They are:

Interior Gateway Protocols (IGP): IGPs are routing protocols which are used to exchange routing information inside an autonomous system. Open Shortest Path First (OSPF), Intermediate System-Intermediate System (IS-IS), Routing Information Protocol (RIP), Enhanced Interior Gateway Routing Protocol (EIGRP), are examples of IGPs.

Exterior Gateway Protocols (EGP): EGPs are routing protocols which are used to exchange routing information between autonomous systems. BGP is the only protocol which is used in the Internet is the one and only EGP.

The dynamic routing protocols can be classified into two according to their methods of operation. They are:

o Distance Vector routing protocols
o Link State routing protocols

Distance Vector routing:

In distance vector routing the protocol sends out a copy of its routing table to its neighbors. This kind of routing is also known as “routing by rumor”, because the router learns about the available routes to other networks through the information passed along to it by neighboring routers. Thus the protocol helps for the router to know two characteristics about how to reach a network. They are:
Which direction to take for reaching a remote network? The interface on which the neighboring router is connected or neighboring routers IP address itself will be used as the direction (Vector).

How far is the remote network? The number of routers in the path to reach the remote network which is the hop count (Distance)

Count to Infinity problem with Distance Vector Protocols:

Figure 4.3 Counting to Infinity condition

In the event of a network failure Distance Vector protocols generally have longer convergence time, because each router just knows of the network from the neighbor. Let us make an example from the figure 4.3. The network is fully converged. When in an event the Network X (nX) fails the re-convergence process occurs as follows.

1.      R3 does not send updates about nX to R2, because the network is down.
2.      R2 still knows nX with a distance of 1 and vector to R3.
3.      R2 sends update about nX to R3 and R1.
4.      R3 and R1 will now have a distance of 2 and vector to R2 for nX.
5.      R3 and R1 send update about nX to R2.
6.      R2 inserts the route from R3 with a distance of 3 because it had R3 as vector for nX.
7.      R2 sends update about nX to R3 and R1.
8.      R3 and R1 will now have a distance of 4 and vector to R2 for nX.
9.      R3 and R1 send update about nX to R2.
10. R2 inserts the route from R3 with a distance of 5 because it had R3 as vector for nX.

The steps 3-6 repeats and the distance increases to infinity. This condition is called Count to Infinity which results in a packet is destined for nX to be looped between R2 and R3. Thanks to the 8 bit Time-To-Live field in the Layer 3 header which ultimately stops the network loop.

Convergence Techniques of DV Protocols:

Each router on the path to a destination will reduce the Time-To-Live (TTL) value in the IP header. A router must reduce the TTL field by at least 1 each time it routes the packet. When the TTL value becomes 0, the receiving router discards that packet. However, this does not stop the router from continuing to attempt to send the packet to a network that is down. Before discussing more about Distance Vector Protocol Convergence speed up techniques, let us observe the following terms:

Maximum Metric: The problem with Count to Infinity occurs because there is not any limit for the Maximum Distance. If there is a predefined maximum Distance then the increments of Distance Count could be stopped at some point. Let us say that when the valid predefined Maximum Distance is 15, and this means if the counter gets to a value beyond 15, then the route will be considered invalid.

Maximum Metric is the maximum hop count value which is valid. If the counter value increases this limit, the route will be considered invalid. For example in the Routing Information Protocol (RIP) the Maximum Metric is 15.

Let us apply the Maximum Metric to the topology in figure 4.3. The Metric count on R2 is incremented each time when it gets the routing advertisement from R3. Due to the lack of Maximum Metric the Metric count increments without any limits. By defining the Maximum Metric count to 15 the R1 will ignore the update from R2. This happens because when R1 receives the update about nX with a hop count of 15, which is the maximum and so instead of incrementing the hop count it will discard the update. The concept of Maximum Metric is built into RIP which is 15

Split Horizon: The Network X is directly connected to R3, thus R2 learned about nX from R3 and R1 learned it from R2. So the fact is, in a case when the nX fails R2 and R1 will never have reachability to nX. From this point of view, it does not make sense when R2 advertises nX back to R3 and R1 advertises nX back to R2.

The rule of Split Horizon states nothing other than, that a route learned through an interface MUST not be advertised out of the same interface.

Let us apply the Split Horizon rule to the topology in figure 4.3. The route advertisement from R3 about the nX to R2 will never be advertised back to R3. So that means when nX fails R3 will not get an update about nX from R2 and thus eventually the information will be aged out from the routing table. Thus the loop is prevented.

Does it speed up convergence really?

The problem here is that R2 and R1 removes the route to nX because of the lack of updates. When the router R1 and R2 does not hear about the remote network for a certain amount of time, they will delete the network entry from their routing table. The convergence time could be decreased, when R3 propagates the message that the nX is failed to other routers.

Triggered Update: When R3 realizes the failure of nX, it sends an update with the information that nX failed. This is called a Triggered Update. A Triggered Update is generated when there is a topology change, which means when a network is down, when a new network is added to be advertised by the protocol.

Route poisoning: When nX fails R3 sends a Triggered Update with this information. This update contains a Poisoned Route. This means that R3 will send an update for nX with a hop count (Distance) of 16, which means that nX is not reachable. The process of sending Poisoned route is Route poisoning.

Poison Reverse: In the event of Route Poisoning, those routers which receive the Poisoned Route will acknowledge the Poisoned Route update by sending the same update out of all interfaces where the protocol is activated. This rule of Poison Reverse acts against Split Horizon.

Whenever a router receives an update with a Poisoned Route, it will send the same update out of all interfaces where the protocol is activated, including that interface where the update came from. This process is called Poison Reverse.

Link State routing:

This type of routing requires a protocol which maintains an identical map of the network. The most important concept for link-state routing is that, all Routers have a map of how the network topology looks like. This map which is called the topology database must be identical on all participating routers. All the Link State routers exchange Link State information called Link State Updates, which helps them to build such a map.

A Link State update contains various attributes about the status of the Link (interface). The attributes could be Speed of the interface, configured Bandwidth, Network ID, Network mask, type of the Link etc. The collection of link states forms a link-state or a topology database. This database is used to calculate the best paths through the network. Link State routers find the best paths to a destination by applying Dr. Edsger Dijkstra’s Shortest Path First (SPF) algorithm against the Link State database to build the SPF tree. The best paths are then selected from the SPF tree and placed in the routing table.

This method or routing is more reliable, easier to debug and less bandwidth intensive than Distance Vector. But it is complex, processor and memory intensive. OSPF and IS-IS are link state routing protocols.

As opposed to Distance Vector routing protocols, Link State routing protocols never exchange their routing table. Thus they are not affected by situations like Count to Infinity. To reduce the convergence time Link State protocols send Triggered Updates only when a topology change occurs. The Link State routers maintain a neighbor relationship with other Link State speaking routers. Since all Link State speakers share the same topology database the convergence after a network failure is very fast, because there may be various paths to a destination network which will be reinserted into the RIB after a new SPF calculation.

Which Routes are insterted to the RIB?

We now have learned that the routing table can be populated either manually or dynamically. When a dynamic protocol is deployed to learn remote networks, it could learn many routes to a particular destination. There are also chances that a single routing protocol learning the same remote network from different sources.

In this case the Cisco IOS adds a route to the remote network in the routing table depending on the following conditions:

1. The reliability of the protocol which learned the route (Administrative Distance).
2. The cost for reaching a remote network (Metric).

Administrative distance:

Administrative distance (AD) defines the preference of a routing source. Each routing source including routing protocols, static routes, and directly connected networks are prioritized in order of most to least preferable using an Administrative Distance value. Cisco routers use the AD feature to select the best path when it learns about the same destination network from two or more different routing sources.

Figure 4.4 Path Selection

Administrative distance is an integer value from 0 to 255. The lower the value the more preferred the route source. An administrative distance of 0 is the most preferred. An administrative distance of 255 means the router will not believe the source of that route and it will not be installed in the routing table. The following table lists the default ADs.

Table 4.4 Default Administrative Distance.

Route Source	Administrative Distance
Directly Connected	0
Static Route	1
EIGRP	90
OSPF	110
RIP	120

Metric

A routing protocol may learn a remote network from more different sources. In this situation the protocol must be able to differentiate between the available paths. For this purpose, Metric is used. Metric is a value used by routing protocols to assign costs to reach a remote network.

Each routing protocol uses its own logic for the path cost calculation. For example, RIP uses hop count, EIGRP uses a combination of bandwidth and delay, and OSPF uses bandwidth. The metric used by one routing protocol is not comparable to the metric used by another routing protocol. Two different routing protocols might choose different paths to the same destination due to using different metrics. RIP would choose the path with the least amount of hops, whereas OSPF would choose the path with the highest bandwidth.

If RIP and OSPF were the protocols activated in the topology from figure 4.4, the path selection from router R2 to nX would be different. RIP which uses Hop count as Metric would choose the path over R3. OSPF which uses bandwidth as the Metric would choose path over R1-R3. Thus using the Metric value the protocol prioritizes the traffic flow to the remote network.

If there are multiple routes to a network the following occurs:

1. The route with the lowest AD will be preferred.
2. If the AD’s are same then the route with the lowest Metric.

Layer 3 Switching