IP Routing: From Basic Principles to Link State Protocols

This chapter is from the book

IP Routing Primer Plus

Learn More Buy

This chapter is from the book

This chapter is from the book 

IP Routing Primer Plus

Learn More Buy

Basic Routing Concepts

Routing involves the delivery of datagrams between end systems located on different networks. Without routers and routing protocols, end host communication would be limited to only those systems on the same physical segment (see Figure 3.1).

Figure 3.1 All hosts are attached to the same segment. There is no need for routers and routing protocols for these hosts to communicate with each other.

Routers provide the physical connection between networks. Routers must be configured with some type of routing mechanism to enable communication between hosts beyond their local segments (see figure 3.2).

Figure 3.2 Routers connect multiple subnets together allowing remote hosts to communicate. The router forwards traffic between hosts on subnets 1 and 2.

These routing mechanisms are either static or dynamic in nature. Static means manual configuration is necessary. Dynamic mechanisms involve routing protocols that facilitate the exchange of information, allowing routers to learn and adapt to changes in a network's topology. Static and dynamic routing protocols will be discussed later in this chapter.

Whether a router is configured statically or dynamically or a combination of both the objective is the same, to facilitate communication between remote hosts. For hosts to communicate with other hosts located on different networks, end systems must be configured with the IP address of at least one local router (also referred to as the default router). Hosts may be statically configured or dynamically discover their local router's or router's IP address(see Figure 3.3).

Figure 3.3 Host A is configured with the IP address (131.107.1.1) of the Default router located on its subnet.

The local router (131.107.1.1) in figure 3.3 is the exit and/or entry point connecting the network and its local hosts to the outside world. Whenever Host A wants to communicate with a host or hosts not connected to its local segment, it must send the datagram to the local router for forwarding. Specific configuration of end hosts is not discussed in this book.

The reference to the "outside world" does not necessarily mean the Internet. Remember that hosts are limited to communicating with hosts connected to the same network unless a router is present. The outside world could simply be a single network on the other side of this router or it could be a series of networks connected through multiple routers leading out to the Internet (see Figure 3.4). The point is that whenever a host wants to go outside of its local segment, it must send datagrams to a local router for delivery.

Figure 3.4 A typical network with multiple internal subnets may contain a router providing a connection to the Internet. The router providing access to the Internet has one interface connected to the inside network and one connected to the outside world.

Let's relate routing to the postal service analogy used in Chapter 2, "IP and IP Addressing," which discussed a network as a "city" and subnetworks as "streets" within a city. The city represents the major classful address (class A, B, or C). The street represents the subnetworks within the major network used to organize and divide the houses within the city. Now let's consider the U.S. postal service as the routing entity that makes delivery of mail within and between cities possible.

First consider a single street without postal service. If you want to send a note to a neighbor who lives on the same street you do, you would probably save yourself the cost of a stamp and deliver the mail yourself, without involving the postal service. In this case you would address the letter as follows: Your name and return address complete with city, street, and house number. You would also indicate the destination address of the intended recipient.

However, if you wanted to send a note to a friend who lives on a different street within your city or in some other city or state, you would most certainly rely on the postal service for the delivery of this message. The U.S. Postal service provides a delivery infrastructure for mail throughout the entire U.S. and interfaces with other delivery services outside the U.S. to facilitate the delivery of mail throughout the world. Standard delivery of mail is best effort, which means there is no guarantee other than trust in the service that your mail will actually get to its final destination.

Now consider yourself the end host on a single segment. And just like an end host you must be able to identify the entry or exit point (router) to use to delivery mail outside of your local street. In this case your mailbox (router) would be considered your entry and exit point outside your local street(see Figure 3.5).

Figure 3.5 A host's entry and exit point (mailbox) in and out of its subnet is its local router.

Somehow when you were young you were taught the basics about mail. Perhaps you learned how to address a letter and what to do with it when you want the postal service to handle delivery outside your local street. Placing a letter in your mailbox is second nature.

However, what happens to your mail once it gets picked up by the mailman is not. That is the mysterious magic of routers and routing protocols. We will discuss how routers and routing protocols handle the delivery of mail in a moment, but for now let's continue with our analogy.

Your letter is in the mailbox; now what? For your letter to arrive at its destination it must travel through the massive delivery infrastructure developed by the postal service. This infrastructure consists of postmen, postal offices, trucks, planes, and so on that through coordinated efforts receive, sort, and deliver the mail.

The first point of contact with your mail is your local postal carrier, who knows to check your mailbox (router) for outgoing mail and take it to the local post office. At that point all mail received at this office is examined. This process involves identifying the address of the destination (end system) or recipient.

Identifying the destination and the path to that destination is key to proper delivery. The postal service has many different options for delivering mail: air, sea, land, and so on. To determine what delivery paths are available and to select the "best path," information about the physical postal infrastructure is either known or needs to be learned (for a router, this function is performed by static or dynamic routing protocols). The postal service's delivery options and best paths to destinations may be in the form of a map or table, similar to the local route table stored by a router. This information is most likely posted at the local post office for all postal workers to use when determining the best path to deliver the mail to its destination.

After identifying the destination address and potential delivery paths by consulting the postal infrastructure map (route table), the most efficient path is chosen. The mail is then sent to the next post office (router) along this path closest to the destination where similar procedures are performed. This continues until it reaches the post office (router) responsible for delivering mail for the destination city (network) and street (subnet) (see Figure 3.6).

Figure 3.6 An example of the delivery of mail from one city to another. Routers serve as the entry, exit, and intermediate delivery points between and across cities (networks) facilitating the delivery of mail (datagrams) between houses (end systems).

The mail is then given to a postman (router) who knows the exact location of the street and house. The postal service (any router involved with delivery) is not concerned with the sender's address or name, unless the destination (end system) is unreachable for some reason. In this case the postal service may return mail marked Undeliverable to the sender.

The delivery and decisions based on the delivery of mail center around the destination address. At no time does the postal service (any router) change the address of the sender or recipient. However, routing markers are added as mail transits from one postal office to another. These markers are used as indicators throughout the postal infrastructure to identify the distribution centers mail has passed through. These markers can be likened to Data Link addresses in that they specifically identify each entity that handled the mail along the path end to end. These markings are not significant outside of the postal delivery system.

Routers represent the physical delivery system of the postal service. Router interfaces connect cities (networks) and streets (subnets) and serve as the entry (mail box), exit (mail box) for end systems (houses) within these cities and streets. Static or dynamic routing protocols build and maintain local route tables. These route tables represent the physical network infrastructure (similar to the postal infrastructure) identifying paths to networks and subnets. Routers after identifying the destination address, use these route tables to determine the best path between source and destination. Route tables are discussed next.

Route Table

All routers must have a local route table. Routers use different routing mechanisms to build and maintain a table known as a route table (also referred to as a forwarding database). Several routing mechanisms exist (directly connected, static, default and dynamic). These mechanisms serve as route table input sources providing a router with network and subnet information necessary to build and maintain the route table. Routing methods and mechanisms are discussed in more detail later in this chapter. Similar to the postal service infrastructure map, these tables are used by routers to determine the best path between source and destination when forwarding datagrams. Route tables include a list of all cities (networks) and streets (subnets) known to a router and the address of the post office (the IP address of the next hop router) used to reach that city or street, among other things.

Route tables are built through several input sources, such as directly connected networks, static, default, and dynamic routes. No matter what the source the end result is the same, the router builds a table that identifies known cities (networks) and streets (subnets).

When a router receives a datagram, the destination address is determined and then compared to each route within the route table until an exact or best route match is found. If an exact match is found within the route table, the router readdresses the datagram using its MAC address as the source and the next hop routers address as the destination. It does not change the logical network layer addresses within the datagram. It then sends the datagram out the local interface connected to the link leading to the next hop router.

When the routers does not find a specific match within its route table, the default route (if one exists) is used or the datagram is discarded and an ICMP error is sent to the originator. ICMP is covered in Chapter 2 of this book.

If multiple paths exist to a destination, more than one route may be included in the route table. Typically, when more than one path to a destination exists, one path needs to be selected (as the best path) by the routing protocol and placed in the route table. This would be the primary (active) path the router would use to forward the traffic to that destination. However, some routing protocols support load balancing across multiple paths. Both paths would become active for the destination and placed in the route table. Both active paths could then be alternately used by routers to forward, balancing the traffic load across these paths.

Once a router has built its route table, it must accurately maintain the information. Maintenance might include manual configuration of routes by an administrator or learned route information through the use of dynamic routing protocols. Whatever the method, accuracy is key to a router's capability to successfully forward traffic. The contents of the route table are only as good as the information entered into the route table. Successful communication between remote systems depends on the maintenance of this information. Bad information leads to bad forwarding decisions. Good information leads to good path selection.

Datagram Forwarding

Datagram forwarding begins when an IP host wants to communicate with another system. Routers and routing protocols provide the delivery infrastructure when source and destination systems are not on the same segment. To send a datagram to another host, the sender must first identify whether the destination host is local or remote. To do so it compares its local mask to the destination hosts IP address to determine whether they are on the same or different subnets (streets). If both hosts reside on the same (local) street, there is no need to involve a router. If not, the source host must route the datagram by sending it to its local router for delivery. The addressing of such a datagram includes the network layer IP addresses of the source and destination hosts. However at the Data Link layer MAC addresses are of the source host and the local router (or mailbox) that will be used to deliver the datagram.

So what happens when a router receives a frame in one of its interfaces?

1. It strips off the Data Link header and trailer and passes the datagram to the upper layer routing process.

2. The router examines the logical destination address, conducting a BITwise ANDing comparison against its local mask to determine the destination network address (city and/or street).

3. The router checks its local cached route table to see if it has a specific route to the destination network, subnet, or end host and which local interface should be used to reach the destination.

• If the destination network address matches a directly attached network or subnet, the router uses a local interface in an attempt to locate the recipient (end system) on that subnet using the end host's IP address.

• If the router determines that the destination network is not local, the router identifies the local interface and IP address of the next hop router it will use to reach this destination.

• If however, a route to the specific destination network does not exist in the route table, the router looks to see if a default route is present. A default route is a route used as a last resort when no other route to a destination exists within the route table.

• If there is no default route specified, it sends a routing error in the form of an ICMP Destination Unreachable message to the originating host. ICMP was discussed in Chapter 2.

4. Once the IP address of either the destination end system or the next hop router has been identified, the router must resolve this address to a MAC address for delivery.

• The router accomplishes IP-to-MAC resolution by examining its local ARP (the Address Resolution Protocol is a broadcast-based protocol used to resolve IP addresses to MAC addresses) cache first to see if it has resolved the address recently for the destination host or next hop router. If an IP address to MAC address mapping resides in cache, the resolution is complete.

• If the IP address does not exist in the local ARP cache, the router broadcasts a local ARP request to resolve the network address to a physical address.

5. Once the IP address has been resolved, the router then uses this information to re-encapsulate the Data Link portion of the datagram. Re-encapsulation does not change the logical IP addresses of the source and destination hosts. The router does however add its own MAC address (of the outbound interface) and the destination host or next hop router's MAC address to the Data Link header. The router also calculates a new CRC, adding this to the end of the datagram as a trailer.

Note

Although routers do not modify the source and destination IP address information they do modify some parameters within the IP header. For instance, the TTL timer (previously mentioned in Chapter 2) is decremented by at least 1 second/hop by each forwarding router. Because changing the TTL value is a modification to the datagram the IP header checksum value must be recalculated.

6. After re-encapsulation, it sends the frame out the local interface either directly to the destination host or to the next hop router for forwarding.

7. The next hop router then performs the same process until the datagram reaches the final destination network.

Autonomous Systems and Routing Domains

Most routing occurs within logical boundaries referred to as Autonomous Systems (AS), or routing domains. Up until recently these terms were used interchangeably within the industry to describe a collection of related networks, subnets, and routers that use the same routing protocol and share information within the common area controlled by a single administrative entity. However, that is not necessarily the case these days, and most companies do not operate in this manner. Take an organization's network that spans a large geographic area. It might deploy several different routing protocols (for example, RIP and OSPF) within each geographic location. Each location might have a separate IT (Information Technology) department (administrative body) controlling it. In this example, RIP and OSPF would be considered separate routing domains. Each routing domain consists of the routing protocol (RIP or OSPF) and the networks, subnets, and routers within this domain. The organization's network as a whole, regardless of the number of routing protocols operating within it, is considered a single Autonomous System.

Presently it is more common to use the term routing domain when referring to routers and networks sharing a common routing protocol. Figure 3.7 shows a routing domain with a collection of networks and routers running a single routing protocol. The term AS is now used to describe a group of routing domains (see Figure 3.8). For example, an organization running two routing protocols, such as RIP and IGRP, would be considered to have two separate routing domains within a single Autonomous System (logically representing the organizational entity and the routing protocols within it as a whole).

Figure 3.7 An example of a RIP routing domain. A routing domain refers to a collection of networks and subnets associated with routers running the same routing protocol.

Figure 3.8 An autonomous system consists of multiple routing domains. In this example, there are three separate routing domains RIP, EIGRP, and IGRP.

The distinction between routing domain and AS is not always clear because the industry uses these terms sometimes interchangeably. In addition routing protocols, such as IGRP, EIGRP, and OSPF, refer to their routing domains as AS. The Internet community has adopted the term AS to describe major logical network boundaries (for example, ISP or organizations). Each of these AS' may implement any number of internal routing domains, each running a different routing protocol. Routing between and across these AS is handled by an Inter-AS routing protocol, known as BGP. Each of the above referenced protocols will be discussed later in the book.