Introduction
Routing is the process of finding the route to a destination, and routing protocols determine how a router updates its route information. A router is attached to two or more networks, and its primary function is receiving IP packets through one network interface and forwarding them through another. The packets can travel through a number of routers before arriving at their final destination. Each router-to-router transmission is called a hop.
Routing is moving information across an internetwork from source to destination. Along the way, at least one intermediate node is typically encountered. Routing is often contrasted with bridging which seems to accomplish precisely the same thing. The primary difference between the two is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, while routing occurs at Layer 3 (the network layer). This distinction provides routing and bridging with different information to use in the process of moving information from source to destination. As a result, routing and bridging accomplish their tasks in different ways and, in fact, there are several different kinds of routing and bridging.
In the Internet context there are three major aspects of routing
- Physical Address Determination
- Selection of inter-network gateways
- Symbolic and Numeric Addresses
The first of these is necessary when an IP datagram is to be transmitted from a computer. It is necessary to encapsulate the IP datagram within whatever frame format is in use on the local network or networks to which the computer is attached. This encapsulation clearly requires the inclusion of a local network address or physical address within the frame.
The second of these is necessary because the Internet consists of a number of local networks interconnected by one or more gateways. Such gateways, generally known as routers, sometimes have physical connections or ports onto many networks. The determination of the appropriate gateway and port for a particular IP datagram is called routing and also involves gateways interchanging information in standard ways.
The third aspect which involves address translation from a reasonably human friendly form to numeric IP addresses is performed by a system known as the Domain Name System or DNS for short. It is not considered further at this stage.
The topic of routing has been covered in computer science literature for over two decades, but routing only achieved commercial popularity in the mid-1980s. The primary reason for this time lag is the nature of networks in the 1970s. During this time, networks were fairly simple, homogeneous environments. Only recently has large-scale internetworking become popular.
Routing Components
Routing involves two basic activities: determination of optimal routing paths and the transport of information groups (typically called packets) through an internetwork. Path determination, on the other hand, can be very complex.
Path Determination
A metric is a standard of measurement—for example, path length—that is used by routing algorithms to determine the optimal path to a destination. To aid the process of path determination, routing algorithms initialize and maintain routing tables, which contain route information. Route information varies depending on the routing algorithm used.
Routing algorithms fill routing tables with a variety of information. Destination/next hop associations tell a router that a particular destination can be gained optimally by sending the packet to a particular router representing the “next hop” on the way to the final destination. When a router receives an incoming packet, it checks the destination address and attempts to associate this address with a next hop.
Routing tables can also contain other information, such as information about the desirability of a path. Routers compare metrics to determine optimal routes. Metrics differ depending on the design of the routing algorithm being used.
Routers communicate with one another (and maintain their routing tables) through the transmission of a variety of messages. The routing update message is one such message. Routing updates generally consist of all or a portion of a routing table. By analyzing routing updates from all routers, a router can build a detailed picture of network topology. A link-state advertisement is another example of a message sent between routers. Link-state advertisements inform other routers of the state of the sender’s links. Link information can also be used to build a complete picture of network topology. Once the network topology is understood, routers can determine optimal routes to network destinations.
If a computer wishes to transmit an IP datagram it needs to encapsulate in a frame appropriate to the physical medium of the network it is attached to. For the successful transmission of such a frame it is necessary to determine the physical address of the destination computer. This can be achieved fairly simply using a table that will map IP addresses to physical addresses, such a table may include addresses for IP nets and a default address as well as the physical addresses corresponding to the IP addresses of locally connected computers.
Such a table could be configured into a file and read into memory at boot up time. However it is normal practice for a computer to use a protocol known as ARP (Address Resolution Protocol) and defined by RFC 826. This operates dynamically to maintain the translation table known as the ARP cache. A computer determines its own physical address at boot up by examining the hardware and its own IP address by reading a configuration file at boot up time but it is necessary to fill the ARP cache. This is done by the computer making ARP request broadcasts whenever it encounters an IP address that cannot be mapped to a physical address by consulting the cache.
The format of an ARP request on an Ethernet is;
| General | Use | Size in Bytes | Typical Values |
| Ethernet Header | Ethernet Destination Address | 6 | A broadcast address |
| Ethernet Source Address | 6 | Identifies the computer making the request | |
| Frame Type | 2 | Set to 0x0806 for ARP request and 0x8035 for an ARP reply | |
| ARP request/reply | Hardware Type | 2 | Set to 1 for an Ethernet |
| Protocol Type | 2 | Set to 0x0800 for IP Addresses | |
| Hardware Address Size in bytes | 1 | Set to 6 for Ethernet | |
| Protocol Address Size in bytes | 1 | Set to 4 for IP | |
| Operation | 2 | 1 for request, 2 for reply | |
| Sender Ethernet Address | 6 | – | |
| Sender IP Address | 4 | – | |
| Destination Ethernet Address | 6 | Not filled in on ARP Request | |
| Destination IP Address | 4 | – |
ARP request table format on Ethernet
By making such requests a host can fill up the ARP cache. ARP cache entries will eventually time-out and a new query will have to be made. This allows a computer to respond to changing topology. Typical timeouts are about 20 minutes. An ARP request to a non-existent computer may be repeated after a few seconds up to a modest maximum number of times.
If a computer is connected to more than one network via separate ports then a separate ARP cache will be maintained for each interface. Alternatively there will be a further entry in the ARP cache associating an entry with a particular interface.
It may be thought that ARP requests will be made for every Internet computer a computer wishes to contact. This is not true, a reference to an IP address not on a local or directly connected network will be re-directed to an IP router computer with an IP address that is on a local directly connected network.
Since ARP requests are broadcast any computer maintaining an ARP cache can monitor all such broadcasts and extract the sending computer’s physical and IP address and update its own ARP cache as necessary. When a computer boots up it can send an ARP request as a means of announcing its presence on the local network. It is possible to associate more than one IP address with a single physical address.
Switching
Switching algorithms are relatively simple and are basically the same for most routing protocols. In most cases, a host determines that it must send a packet to another host. Having acquired a router’s address by some means, the source host sends a packet addressed specifically to a router’s physical (Media Access Control [MAC]-layer) address, but with the protocol (network-layer) address of the destination host.
On examining the packet’s destination protocol address, the router determines that it either knows or does not know how to forward the packet to the next hop. If the router does not know how to forward the packet, it typically drops the packet. If the router knows how to forward the packet, it changes the destination physical address to that of the next hop and transmits the packet.
The next hop may or may not be the ultimate destination host. If not, the next hop is usually another router, which executes the same switching decision process. As the packet moves through the internetwork, its physical address changes but its protocol address remains constant.
The International Organization for Standardization (ISO) has developed a hierarchical terminology that is useful in describing this process. Using this terminology, network devices without the ability to forward packets between subnetworks are called end systems (ESs), while network devices with these capabilities are referred to as intermediate systems (ISs). ISs are further divided into those that can communicate within routing domains (intradomain ISs) and those that communicate both within and between routing domains (interdomain ISs). A routing domain is generally considered to be a portion of an internetwork under common administrative authority, regulated by a particular set of administrative guidelines. Routing domains are also called autonomous systems. With certain protocols, routing domains can also be divided into routing areas, but intradomain routing protocols are still used for switching both within and between areas.
Routing Protocols
Border Gateway Protocol
One protocol that addresses the task of path determination in today’s networks is the Border Gateway Protocol (BGP). BGP performs interdomain routing in Transmission-Control Protocol/Internet Protocol (TCP/IP) networks. BGP is an exterior gateway protocol (EGP), which means that it performs routing between multiple autonomous systems or domains and exchanges routing and reachability information with other BGP systems.
BGP is specified in several Request For Comments (RFCs):
- RFC 1771 —Describes BGP4, the current version of BGP
- RFC 1654—Describes the first BGP4 specification
- RFC 1105, RFC 1163, and RFC 1267—Describes versions of BGP prior to BGP4
BGP Operation
BGP performs three types of routing: interautonomous system routing, intra-autonomous system routing, and pass-through autonomous system routing.
Interautonomous system routing occurs between two or more BGP routers in different autonomous systems. Peer routers in these systems use BGP to maintain a consistent view of the internetwork topology. BGP neighbors communicating between autonomous systems must reside on the same physical network. The Internet serves as an example of an entity that uses this type of routing because it is comprised of autonomous systems or administrative domains. Many of these domains represent the various institutions, corporations, and entities that make up the Internet. BGP is frequently used to provide path determination to provide optimal routing within the Internet.
Intra-autonomous system routing occurs between two or more BGP routers located within the same autonomous system. Peer routers within the same autonomous system use BGP to maintain a consistent view of the system topology. BGP also is used to determine which router will serve as the connection point for specific external autonomous systems. Once again, the Internet provides an example of interautonomous system routing. An organization, such as a university, could make use of BGP to provide optimal routing within its own administrative domain or autonomous system. The BGP protocol can provide both inter- and intra-autonomous system routing services.
Pass-through autonomous system routing occurs between two or more BGP peer routers that exchange traffic across an autonomous system that does not run BGP. In a pass-through autonomous system environment, the BGP traffic did not originate within the autonomous system in question and is not destined for a node in the autonomous system. BGP must interact with whatever intra-autonomous system routing protocol is being used to successfully transport BGP traffic through that autonomous system.
OSPF
The Open Shortest Path First (OSPF) routing protocol is designed for a hierarchical network structure. The community of routers, usually owned and managed by a single group is called an autonomous system (AS). OSPF divides the world into two domains—within the autonomous system and external to the autonomous system. The autonomous system itself is divided into a central, or backbone area
(area 0) to which all other areas are connected, and other (nonzero) numbered areas.
Areas
Each OSPF area has one or more network address/netmask pairs and is identified by a 32-bit area number. An area is a contiguous set of routers sharing network segments between them. An area must be one of the following types, depending upon the routing information that it uses:
- Transit area – An area where routing information for a default route, static routes, intra-area routes, interarea routes, and autonomous system external routes is kept in the area database. The backbone area falls into this category.
- Stub area – An area where all autonomous system external routes are summarized by a per-area default route in the area database, which also contains intra-area and interarea routes. Summarization reduces the database size and memory requirements for a stub area’s internal routers. A stub area frequently has only one area border router (ABR).
- Not-so-stubby area (NSSA) – Similar to a stub area, but it can export limited autonomous system external route information to the backbone. The NSSA is useful for areas that do not need to retain all the autonomous system external route information flooded into the area, but do need to export some limited external route information not permitted from standard OSPF stub areas.
RIP
The Routing Information Protocol (RIP) is an interior routing protocol that uses a distance-vector algorithm to optimize routing. It is widely used by routers in TCP/IP networks and Novell IPX networks.
The distance-vector algorithm used by RIP for making routing decisions is based on the number of hops to a destination. The route with the least number of hops is considered to have the lowest cost. The number of hops is referred to as the route metric; a route with a metric greater than 15 is considered to be unreachable.
Routing table entries for RIP are aged as follows:
- Updates are expected every 30 seconds.
- After 120 seconds, if information for another route to a given destination is observed the new route is used for the destination.
- After 180 seconds without an update, a route is considered unreachable. RIP makes the route obsolete by setting the route metric to 16.
- The routing timer is suspended if an on-demand interface is suspended.
- Routes are valid only for active interfaces.
- If an interface becomes unreachable, all routes that go through that interface are examined. If the specified gateway is available through another interface, the route is moved to the active interface. Otherwise, the routing table entry is marked as obsolete.
Types of Routing
Static Routing
Static routes contain route information that does not respond to changes in network topology or condition. In spite of this inability to respond to change, static routes can be useful for stable networks or segments of networks that are not expected to change frequently.
Other possible uses for static routing are
- For operations that use or connect to routers that do not support the routing protocols supported by the Lucent ComOS
- For operations over WAN links where costs are determined by connect time or number of packets sent, and the use of routing protocols adds to the cost Static routing tables are constructed manually by the network administrator, who must update them periodically to reflect any network changes.
Dynamic Routing
If a network has more than one possible route to a destination, or if the network is large or complex, or experiences frequent changes, dynamic or learned routing through the use of routing protocols is necessary. Routing protocols collect routing information, broadcast it dynamically, and update routing tables automatically to reflect network changes.
Dynamic routing adds a high degree of flexibility to the routing process by
- Permitting the selection of routes based on cost or congestion criteria
- Allowing redundant routes to compensate for downed lines
- Selecting the best route to a destination when multiple routes exist
- Providing fast response to network changes
Variable-Length Subnet Masks
The commonly used Routing Information Protocol (RIP) requires that a single netmask be used across the entire subnet. This limitation has a major impact on the routing of traffic among many networks. Regardless of the actual need for addresses, each subnet of the network must be assigned the same number of IP addresses. The use of more than one subnet mask in a subnetted network is described in RFC 1812. A network using this method of subnetting is referred to as a network with variable-length subnet masks (VLSMs) because the network prefixes have different lengths. VLSM support allows more efficient use of TCP/IP addresses by allowing network designers greater freedom in assigning addresses.
Classless Interdomain Routing (CIDR)
Variable-length subnet masking uses classless interdomain routing (CIDR) addressing. Table 1-1 lists the variable-length netmasks from 16 to 32, the CIDR representation form (/xx), and the hexadecimal and decimal equivalents. Refer to RFC 1878 for more information.
| IP addresses | Bits | Prefix | Subnet Mask |
| 1 | 0 | /32 | 255.255.255.255 |
| 2 | 1 | /31 | 255.255.255.254 |
| 4 | 2 | /30 | 255.255.255.252 |
| 8 | 3 | /29 | 255.255.255.248 |
| 16 | 4 | /28 | 255.255.255,240 |
| 32 | 5/ | /27 | 255.255.255.224 |
| 64 | 6 | /26 | 255.255.255.192 |
| 128 | 7 | /25 | 255.255.255.128 |
| 256 | 8 | /24 | 255.255.255.0 |
| 512 | 9 | /23 | 255.255.254.0 |
| 1 k | 10 | /22 | 255.255.252.0 |
| 2 k | 11 | /21 | 255.255.248.0 |
| 4 k | 12 | /20 | 255.255.240.0 |
| 8 k | 13 | /19 | 255.255.224.0 |
| 16 k | 14 | /18 | 255.255.192.0 |
| 32 k | 15/ | /17 | 255.255.128.0 |
| 64 k | 16 | /16 | 255.255.0.0 |