Understanding How Forwarding Decisions Are Made
IP routing is normally done on a next hop basis. For example, in Figure 1-7, RouterA may have told RouterB about subnet 168.71.5.0. RouterB doesn't really care whether RouterA is actually attached to 168.71.5.0. If RouterA says it can reach 168.71.5.0, that is sufficient for RouterB to make a forwarding decision to send packets destined for network address 168.71.5.0 to RouterA.
Performing Longest Match Lookups
Routers take an incoming IP packet and compare it to entries in their routing tables by performing a longest match lookup. Remember that IP addresses are really 32-bit binary numbers split between a network section and a host section. Only the network portion is stored in a routing table.
Performing a longest match lookup in a routing table is the same as saying the following: "Find the network address in the routing table with the most bits in common before a mismatch occurs with the destination network address of the packet being routed. Do this by reading each entry in the routing table from left to right, comparing each bit in sequence with the bits in the destination network address of the packet being routed. Stop the comparison process at the bit before the first bit that doesn't match in the routing table entry being compared."
Figure 1-7. An example of a simple routing table for Router B.
Longest Match Lookup—A Simple Example
Start with the binary number 11111100. Compare it to the following binary numbers: (a) 11111000, (b) 11110000, and (c) 11100000. Which is the longest match?
The answer is (a). The original binary number starts with a string of six 1s, followed by two 0s. (a) starts with five 1s, followed by three 0s, so it has the longest matching number of bits before a mismatch.
Routers typically store entries in their tables in descending order. In this example, the numbers would be stored in the order: (a), (b), (c).
If a router were comparing these numbers, it would have started with (a) and stored in memory how closely (a) matched the number being compared (11111100) before a mismatched bit occurred.
The router would then proceed to do the same comparison for (b). The router would have realized that (a) was a better match than (b) because (a) had five bits in common before a mismatch, whereas (b) had only four.
The router would never have gotten around to checking (c) because it would know that numbers are stored in descending order and that (c) had to be a smaller number than (b) and therefore could not be a better match.
See the section on longest match lookups using VLSM in Chapter 3, "Discontiguous Networks, Summarization, and Subnet 0." VLSM is also explained in Chapter 3.
Entries in a routing table are the network addresses that the router knows about. It is common practice to refer to an entry in a routing table as a route. Therefore, saying that RouterB has a network entry in its routing table for network 168.71.5.0 is synonymous with saying "RouterB has a route to 168.71.5.0." This book uses both methods when discussing the contents of a router's routing table.
Routers ignore the host section of the destination address. They use only the network section when performing a longest match lookup. Routers know how addresses should be broken down because they store the subnet mask associated with each route in its routing table.
Note
Routing tables normally include the subnet masks associated with the network addresses, as well as the network addresses themselves. Subnet masks are not given in the routing table in Figure 1-8 so that it is easier to view. For reference, the mask for these routes is 255.255.255.0.
If a router finds a suitable match in its table for the network address of a packet it is trying to forward, it has what is sometimes referred to as an explicit match. In other words, the information in the routing table indicates explicitly where to send the packet.
If no explicit route is available, the router may choose to forward the packet to a gateway of last resort. This is covered in more detail in Chapter 4 in the section on gateways. In Figure 1-7, RouterB received a packet destined for 168.71.5.1.
The longest match in the routing table indicates that 168.71.5.0 is known via serial 0, with a next hop of 168.71.6.1. In this case, the next hop address is redundant because the serial link is point to point. There is only one router to forward this packet to. Remember that the actual destination IP address in the packet does not change. It remains 168.71.5.1.
Forwarding Decisions for Multipoint Interfaces
Figure 1-8 shows how the next hop interface of serial 0 is not sufficient for forwarding the packet to 168.71.5.1 accurately. The further distinction of a next hop IP address eliminates the ambiguity of only pointing to the serial interface. In this case, RouterB knows that the next hop is out serial 0 to the next hop address of 168.71.6.1. RouterB will have a Frame Relay map entry on serial 0 that indicates the appropriate DLCI (100) to send the packet to.
Figure 1-8. How forwarding decision are made for multipoint interfaces.
For Frame Relay, the DLCI address performs the same function as a MAC address on an Ethernet network. Frame Relay is a layer two protocol. Therefore, when a Frame Relay switch forwards an IP datagram encapsulated in a Frame Relay layer two frame, it does so by reading the layer two destination DLCI address contained in the frame.
The Frame Relay network switches the frame through the network and finally delivers it to RouterA. RouterA can then forward the datagram on to the ultimate host. See Frame Relay Principles and Applications by Philip Smith, published by Addison-Wesley (ISBN 0-201-62400-1), for more information on Frame Relay.
The Frame Relay map entry for IP address 168.71.6.1 to DLCI 100 is essentially an ARP entry for the layer two and layer three protocol addresses. It is similar to an Ethernet MAC address to IP address ARP entry:
RouterB#show frame-relay map
Serial0 (up): ip 168.71.6.1 dlci 100(0x64,0x1840), static,
broadcast,
CISCO
RouterB#
The Address Resolution Protocol (ARP) is used to resolve layer three (network) addresses to layer two (MAC) addresses so that frames can be forwarded to a particular host directly. If end systems were not able to store entries that mapped these two addresses, all frames would have to be broadcast at the MAC level. In addition, each end system would have to open every frame and de-encapsulate it to the network layer to see whether the frame's network layer address matched its own network layer address.
End Systems Sending Packets to Other Subnets
Before a router can even become involved in forwarding a packet from an end station, the end station must figure out how to get the packet to the router in the first place.
When an end system wants to send an IP packet to another end system, it compares the destination IP address with its own address. If the destination network address is within the same subnet (on the same local cable), the originating end station will ARP for the destination end system.
If the originating end system determines that the destination end system is on a different cable because it has a different subnet (network) address, it will send the packet to the MAC (cable address) of its gateway and the IP address of the destination end system.
In Figure 1-9, end system A wants to send a PING to end system B. End system A determines that end system B is on a different cable segment because the destination IP address is on a different subnet of 168.71.0.0. End system A is on subnet 168.71.5.0, and end system B is on subnet 168.71.8.0.
End system A has 168.71.5.2 configured as its gateway address. End system A will ARP for the MAC address of 168.71.5.2 so that it can use this address as the MAC address for delivering packets to 168.71.8.1. The layer two (MAC) addresses are specific to the link to which they are attached. The layer three (IP addresses) are end to end. The layer two addresses for the serial links have been omitted for clarity.
Figure 1-9. End system A sends a PING to end system B.
The IP address 168.71.5.2 and the MAC address 0000.0c01.8793 both belong to RouterA's Ethernet 0 interface. The IP address 168.71.8.2 and the MAC address 0000.0f00.8684 both belong to RouterB's Token Ring 0 interface. Gateways are covered in more detail in Chapter 5.
HINT
If you have a PC running TCP/IP, you may be able to see this for yourself. At a DOS prompt, type C:> arp -a.
You should see the IP address and MAC address of your IP gateway. You will probably not see entries for systems that are not on your subnet because your PC is sending these datagrams in frames that have the MAC address of your IP gateway.
Entries for systems on your own subnet will have their own MAC addresses associated with their IP addresses. If you do not see any entries for systems on your subnet, try the following command at a DOS prompt: C:>ping 255.255.255.255. This is the IP broadcast address. Then try C:> arp -a again. If other IP hosts are on your subnet, they may show up in your ARP table.