3.2 Router Operation Overview
As you know, every IP host in a network is normally configured with not only its own IP address and mask but also the IP address of the default gateway (see Figure 3-1). If the host needs to send an IP packet to a destination address that does not belong to a subnet the host is directly attached to, the host passes the packet to the default gateway (router).
Figure 3-1. Use of default gateway
A common misunderstanding is how the address of the default gateway is used. People tend to incorrectly think that when a packet is sent to the default router, the host sets the destination address in the IP packet to the configured default router address. However, the router would then consider the packet addressed to itself and would not forward it any further. Why configure the default gateway's IP address, then? The answer is that the host uses the Address Resolution Protocol (ARP) to find the Media Access Control (MAC) address of the specified router. Having acquired the router's MAC address, the host sends the packets directly to it as data link unicast submissions.
What happens when a router receives a packet on one of its interfaces? The first thing to remember is that normally, routers do not check the source IP address of the packet when it is received. It seems obvious. However, people are sometimes very surprised when they see, for example, packets coming from an interface attached to subnet 22.214.171.124 with the source address set to, say, 126.96.36.199.
As we will see in Chapter 5, however, Cisco routers can be explicitly configured to perform so-called unicast Reverse-Path Forwarding (RPF) check, whereby the router does verify the source address in the packets to prevent denial-of-service attacks.
Routers never change the source and the destination addresses in IP packets, except for Network Address Translation (NAT), which is not considered in this book. Routers send packets to each other by setting correct data link layer addressesfor example, MAC addresses for Ethernet or Data Link Connection Identifier (DLCI) for Frame Relayin the data link frames or just pushing them through point-to-point links, using associated encapsulation mechanisms. If they changed the source and destination IP addresses, routers would lose information about where the packets were coming from and going to. In our example, a packet with a source address of 188.8.131.52 could be originated by a host outside the network and forwarded by another router on subnet 184.108.40.206. The intermediate routers won't change the packet's IP addresses but instead just pass the packet to the next closest neighbor toward the destination address.
When a packet is received, the router checks its validity and determines whether the packet must be delivered locallyit is addressed to the router itselfor forwarded further. If the packet must be forwarded, the router makes the routing decision and determines the outbound interface and the IP address of the router that should be the next hop in the path, if the destination network is not directly attached.
Consider a simple example. Suppose that a router is connected to two networks10.0.0.0 and 220.127.116.11as illustrated in Figure 3-2. Host A on the first segment sends an IP packet to host B on the second segment. Host A passes the packet to the router by specifying the router's MAC address as the destination address in the Ethernet frame. (The destination IP address is the IP address of B.)
Figure 3-2. Two segments connected by a router
When it receives the frame, R1 examines the IP packet and uses its routing table to decide where to forward the packet. The table contains information in the form "to reach hosts on network N, use interface X and next hop Y." Such a combination of routing parameters is called a route. How does the router know where the networks are, though?
Part of every router's configuration task is assignment of IP addresses to the router's interfaces. A router therefore functions like a normal IP host on each network to which it is connected. Even if it never originated IP packets itself, a router would still need this information to answer the ARP requests sent by end nodes while trying to find the MAC address of the default router or by neighboring routers looking for the MAC address of the next hop.
Because a router's interfaces are configured with IP addresses and corresponding address masks, the router can derive information about the networks connected to its interfaces by applying address masks to the associated addresses. That is the way routers obtain their startup information about directly connected networks and put this information into the routing tables. In our example, the routing table of R1 would look like the following:
Network 10.0.0.0 is directly connected to interface Ethernet 0 Network 18.104.22.168 is directly connected to interface Ethernet 1
This table contains enough information to route the packet from host A to host B. The router just takes the destination address from the IP packet header and looks through the table. Having found the information about network 22.214.171.124, the router understands that the packet destined for a host on this network should be delivered on interface Ethernet 1. The decision is made. Now the router has to encapsulate the IP packet into an Ethernet frame and send it to host B. If this is the first time the router is sending a packet to this host, the router sends an ARP request, asking for B's MAC address. Otherwise, the router uses its ARP cache. This example is quite simple, as both networks are directly connected.
Now look at a network constructed of several routers (Figure 3-3). Every router in the network has information only about directly attached networks:
Figure 3-3. More complex routed network
Network 10.0.0.0 is directly connected to the interface Ethernet 0 Network 126.96.36.199 is directly connected to the interface Ethernet 1
Network 188.8.131.52 is directly connected to the interface Ethernet 0 Network 184.108.40.206 is directly connected to the interface Ethernet 1
Network 220.127.116.11 is directly connected to the interface Ethernet 0 Network 18.104.22.168 is directly connected to the interface Ethernet 1
Now host A from network 10.0.0.0 sends an IP packet to host C on network 22.214.171.124. When it receives the packet, R1 cannot make the forwarding decision, because it has no information about destination network 126.96.36.199. R1 will drop the packet and send an ICMP "Destination Unreachable" message to host A. What information would R1 need in its routing table to successfully route the packet to host C? There should obviously be a line saying that network 188.8.131.52 is reachable via router R2. The routing table of R1 would have to look like the following.
Network 10.0.0.0 is directly connected to the interface Ethernet 0 Network 184.108.40.206 is directly connected to the interface Ethernet 1 Network 220.127.116.11 is accessible via 18.104.22.168
With this information, the router would make its forwarding decision as follows.
The packet is destined to host 22.214.171.124 (host C).
Look through the routing table for information about address 126.96.36.199.
Address 188.8.131.52 belongs to network 184.108.40.206 that is accessible via host 220.127.116.11.
Look through the routing table for information about address 18.104.22.168.
Network 22.214.171.124 belongs to network 126.96.36.199 that is directly connected to interface Ethernet 1.
Send the packet through the Ethernet 1 interface, using R2's MAC address as the destination MAC address.
As you see, the router performs recursive table lookup, trying to find a route to the next-hop address, specified in the last route in the table. If there were another router, R4, on network 188.8.131.52 and connected to network 184.108.40.206, router R1 would have the following routing table:
Network 10.0.0.0 is directly connected to the interface Ethernet 0 Network 220.127.116.11 is directly connected to the interface Ethernet 1 Network 18.104.22.168 is accessible via 22.214.171.124 Network 126.96.36.199 is accessible via 188.8.131.52 (router R4's IP address)
The steps taken by the router in this case would be the same: "Find information about the destination network; if it goes through another network, find information about that one, too." The router would continue looking through the table recursively until it found a reference to a router's address that belonged to a directly connected network or it realized that there was no route for the address.
Following are some rules of thumb about routing in datagram networks. (IP networks belong to the datagram network group.) Knowing these basic principles is required for network maintenance and troubleshooting.
Every router makes its decision alone, based on the information it has in its own routing table. When making the routing decision, a router can use only information in its own routing table. There is no way for a router to check whether its neighbors are going to make a consistent decision. Routers route packets according to the information they have in the routing tables at a particular instance. When it forwards a packet to the next router, a router assumes that the next router will do the same: make its decision according to the information in its own routing table. Only consistent routing information can guarantee a consistent forwarding decision throughout the network.
The fact that one router has certain information in its routing table does not mean that other routers have the same information. Even if the first-hop routerthe router nearest to the sourcehas required information about a remote network, other routers on the way to the destination may have no information about it. Therefore, even if the first-hop router forwards a packet successfully, the next router may drop the packet if it doesn't have enough routing information to forward it.
Routing information about a path from one network to another does not provide routing information about the reverse, or return, path. Even though all routers along the way to a destination have information about the destination network, the remote routers may have no information about how to route packets coming back. In the example, if host C on network 184.108.40.206 sent a reply to host A on network 10.0.0.0, router R2 would need additional information about how to reach network 10.0.0.0. If it had no information about this network, R2 would have to drop the packet.
According to these rules, the administrator needs to make sure that all routers in a network have adequate and consistent information about every network that might be involved in the communication process.
Lack of routing information about a destination network is not the only reason for a router to drop a packet. A router can also drop packets because of output queue overflow or because of a lack of CPU time needed for the router to take packets out of the input queues. A packet is also dropped when the value of its Time-to-Live (TTL) field reaches 0; each router decrements it by1. This is a protective measure introduced to make sure that even in the presence of temporary or permanent routing loops, the network does not accumulateforward endlesslypackets destined for the networks for which the loops are experienced. Another reason for a packet drop is inability to fragment an IP packet while trying to send it through one of the router's interfaces.
Normally, every router's interface is assigned a value that specifies the maximum size of a data block that can be sent over it. This value is called maximum transmission unit (MTU) and is usually specific for a given media type. For example, the default MTU for Ethernet and serial interfaces in Cisco routers is 1,500 bytes; for the 16Mbps Token Ring, it is 8,136 bytes. When it is about to send an IP packet over an interface, a router checks whether the packet fits into the interface MTU. If the packet is bigger than the MTU, the router breaks the packet into pieces that fit into it and sends them as separate IP packets. This process is called IP packet fragmentation. Routers can fragment an IP packet if necessary unless it has the do not fragment (DF) bit set in the header. When this bit is set and a router sees that the packet must be fragmented, the router drops the packet and sends an ICMP "Destination Unreachable" message with the code field set to "Fragmentation needed and DF set" to the originator.
The difference between an IP packet and an IP datagram is that hosts always send datagrams, which can be fragmented into several IP packets. Therefore, any IP packet can be either a whole IP datagram or a fragment of it. IP packets can be further fragmented if they need to be sent over a link with even smaller MTUs.
If a datagram is fragmented while going through the network, the receiving host performs IP datagram reassembly. Routers do not reassemble IP datagrams from IP packets not destined for themselves, for several reasons. First, it would add extra delays in routing: A router would have to wait until all fragments of a given datagram came to it. Second, the router would need to store all fragments of all datagrams before reassembly. (Imagine an Internet core router doing this.) Third, and maybe most important, because routers perform load sharingsend packets to the same destination along parallel pathsand because IP packets are sometimes dropped on their way through the network, a router may never receive all fragments of a datagram.