9.4. Internet Routing Protocols
As mentioned earlier, Internet routing protocols can be classified into interdomain and intradomain routing protocols. Interdomain routing protocols are also referred to as Exterior Gateway Protocols or EGPs, based on early Internet terminology. BGP is the most popular example of an EGP. In fact, it is the only EGP that is in use in the Internet today. Intradomain routing protocols, on the other hand, are referred to as Interior Gateway Protocols or IGPs. Examples of IGPs include OSPF, IS-IS, and RIP. Figure 9-4 gives an overview of different routing protocols running in the Internet.
Figure 9-4. IGPs and EGP in the Internet
9.4.1. Intradomain Routing Protocols
9.4.1.1. RIP
RIP is an IGP based on the distance vector routing paradigm. It is also known by the name of its Unix implementation, routed (pronounced route-d), which was originally designed at University of California at Berkeley to provide consistent routing and reachability information among machines on a LAN. RIP's popularity is not necessarily based on its technical merits, but due to the fact that U.C. Berkeley distributed routed along with their popular BSD UNIX systems. Thus, many Internet sites adopted and installed routed without even considering its technical merits and limitations. Once installed and running, it became the basis for local routing.
Typical of a distance vector algorithm, RIP works fine for small, stable, high-speed networks. Routers running RIP broadcast their entire routing database periodically, typically every 30 seconds. This message lists each destination along with a “distance”to that destination, measured in number of router hops. Each router selects as next hop the neighbor whose distance is the shortest to a given destination, and advertises its own distance to all its neighbors.
Because every router is broadcasting its entire routing table, it takes a while for these tables to converge in times of network instability. Under RIP, there is no explicit protection from routing loops. Rather, a route is rejected when the associated distance (cost) reaches a maximum. Due to this, RIP suffers from slow convergence; when a loop occurs, the corresponding path cost tends to slowly increase, and the routing loop persists until the cost reaches the maximum value. In large networks or networks with slow links, some routers may still advertise a route that has ceased to exist.
9.4.1.2. OSPF
OSPF is a link state routing protocol. In contrast to a distance vector protocol, where a router “tells all neighbors about the world,” link state routers “tell the world about the neighbors.” OSPF LSAs allow routers to update each other about the LAN and WAN links to which they are connected. When a change is made to the network, LSAs are broadcast throughout the network. Five different types of LSAs are defined in OSPF. They are:
Summary LSA: For reasons of scalability, OSPF networks are often divided into multiple areas. Router and network LSAs pertaining to nodes and links in an area are contained within the area. Information about reachable destinations within an area is sent in summary LSAs to nodes outside the area. (Note: Summary LSAs may be used in optical networks with multiarea routing.)
Opaque LSA: Opaque LSAs provide a standard way to extend OSPF. We will see in Chapter 10 how opaque LSAs are used to extend OSPF for routing in optical networks.
OSPF routers receive LSAs and store them in a topology database, known as the Link State Database (LSDB). The typical LSDB contains a representation of every link and router in the network. The LSDB is used to calculate a forwarding table that lists the next hop to each destination. Each router uses an identical procedure, called Dijkstra's algorithm [Dijkstra59] (see Chapter 11), to compute consistent forwarding tables.
OSPF addresses all of the shortcomings of RIP and it is therefore better suited for routing in large, dynamic networks. For example, instead of sending its entire routing table to its neighbors every 30 seconds under RIP, a router broadcasts its local link state information every 30 minutes under OSPF. OSPF can get away with this large update interval, because OSPF routers also broadcast small update messages (typically less than 75 bytes) whenever they detect a change in the network (e.g., a failure or a new link). When routers exchange updates that reflect changes in the network, they converge to a new representation of the topology quickly and accurately.
Although it improves upon RIP, OSPF itself had to address the following issues. First, the number of LSAs that flow between routers can become an issue in large configurations. For instance, in a network with over a hundred routers, a single link change can precipitate a flood of LSAs that propagate across the entire network. Next, each time there is a change in the network, routers must recompute routes. In very large OSPF networks, topology convergence can be delayed while routers exchange link-state messages, update databases, and recalculate routes.
OSPF addresses these issues by incorporating the notion of areas (see Figure 9-5). OSPF areas are simply logical subdivisions of an OSPF network. Typically, an enterprise is divided into areas that correspond to buildings, campuses, regions, etc. An enterprise can have a large number of areas.
Figure 9-5. OSPF Areas and LSAs
OSPF routers within one area do not exchange detailed topology information with routers in other areas. When a LAN or WAN link is added to one area, topology updates flow only to routers within that area. This reduces the number of updates that flow through the network and the size of the topology databases in each router. In an enterprise with 500 routers, the creation of 10 areas of 50 routers means that each router only needs to store link information for 50 routers, and not for all 500. OSPF areas are connected to each other by means of a backbone area that is just another area by itself. A router that connects its area to the backbone area must maintain the topology databases for both areas. These special multiarea routers are called Area Border Routers (ABRs), and they serve as a filter for the routing information that moves between the other areas and the backbone. ABRs send summary LSAs that contain a summarization of the reachability information pertaining to their areas.
This technique of hierarchical routing reduces the complexity of an OSPF network, as a router need not know the internal details of all the areas. Each ABR sends out summary LSAs that advertise the IP address prefixes reachable within its area. Other ABRs store these summarization messages and use them to compute routes for the interarea traffic. While summarization of IP addresses as prefixes reduces the routing overhead, it does introduce an administrative overhead. Specifically, summarized prefixes must be administratively configured in ABRs. This task is similar to the configuration of router traffic filters or priorities.
A good example of the benefits of OSPF areas can be seen in a campus environment, where each building is defined as an area. Let us take a campus where each building has multiple floors and a router on each floor. Without OSPF areas, routers would have to exchange updates with every other router on the campus. When areas are configured, routers only exchange link state information with routers in the same building. An ABR in each building forms a link between the building and the campus backbone.
Another example of the application of OSPF areas is a national network that is divided into areas corresponding to different regions of the country. For example, all the routers in the New York area would have identical data bases that cover the New York region only, and the same would apply to other regions as well. In each area, an ABR is attached to the national backbone. This approach eliminates the need to propagate router update messages across the entire national network.
OSPF is the de facto industry standard protocol because of its robustness. It supports the requirements of larger networks such as special service requests and authentication of routing protocol messages. OSPF is an efficient protocol, supporting speedy recovery from topology changes. OSPF also minimizes overhead traffic by only sending updates on changes rather than the entire routing table.
9.4.1.3. IS-IS
IS-IS is also a link state routing protocol that offers similar services as OSPF. IS-IS, however, was developed by ISO as a part of the Open System Interconnection (OSI) network architecture [Tanenbaum02]. IS-IS was originally developed for routing within ISO Connectionless Network Protocol (CLNP) networks. It was later extended to support IP routing [Callon90].
In OSI terms, an end system (ES) refers to any network node that does not perform routing (e.g., a host) whereas an intermediate system (IS) is a router. Thus, the ES-IS protocol allows ESs and ISs to identify each other while IS-IS supports routing between ISs.
IS-IS periodically floods the network with link state information, allowing each router to maintain a complete picture of the network's topology. Optional path metrics available with IS-IS are based on delay, expense, and error. The delay metric represents the amount of delay on a particular link. Expense relates to the communications costs of using the link. The error metric represents the error rate of the link. The use of these metrics allows IS-IS to respond to the quality of service (QoS) field in the CLNP packet header. These mappings tell the IS-IS protocol to compute a path that best matches requested QoS.
IS-IS uses three basic packet types: Hello, Link State, and Sequence Number. For further details on IS-IS, refer to [Callon90, ISO90].
9.4.2. Interdomain Routing Protocols
The goal of interdomain routing is to exchange routing information across ASs. An AS is typically a collection of networks with the same routing policy and usually under single ownership, trust, and administrative control. An AS consists of one or more border routers, which exchange routes with border routers in other ASs. In addition, border routers may participate in intradomain routing within the AS.
9.4.2.1. BGP
BGP is the de facto standard interdomain routing protocol in the Internet. It was first specified in 1989. BGP version 4, the most recent version of BGP, was first specified in 1994 and updated in IETF RFC 1771 [Rekhter+95]. There also have been a number of other documented extensions to BGP.
The BGP protocol instance running in a border router establishes peer relationships with adjacent border routers, referred to as neighbors. Unlike OSPF and ISIS, which automatically discover the routing neighbors, BGP has to be configured with the peers' IP addresses and their AS Numbers (ASNs) over the appropriate interfaces. BGP peers send small keep-alive messages to each other. If a neighbor stops receiving keep-alive messages for a predefined hold time, it will update its routing table to reflect the loss of available routes through the corresponding peer. A router running BGP also sends incremental updates to its peers when routes become unavailable. Otherwise, the full routing tables are exchanged only when two routers first establish or reestablish a peering relationship.
BGP is a path vector protocol, which is similar to a distance vector protocol, but with a key difference. A distance vector protocol advertises only the cost of the path to a destination. A path vector protocol advertises both the cost of the path as well as the sequence of nodes in the path [Rajagopalan+91]. Under BGP, the path information is described at the level of ASs rather than individual nodes. A router running BGP chooses a route that traverses the least number of ASs to a destination. To enable this, a router that first advertises reachability to a destination includes its own AS number in the advertisement. Each router that receives this advertisement and propagates to other routers appends its AS number to the path information. By default, the path with the fewest ASs to a destination network is stored in the routing table. Since the path to a given destination can traverse multiple routers within an AS, the actual hop count may be higher than what the AS path indicates. The path information also helps in avoiding routing loops; a router that receives an external advertisement that includes its own AS number will reject the advertisement.
One of the advantages of BGP is its built-in flexibility to enhance the default behavior. For instance, it may be desirable to control the path taken by the traffic leaving a network. By default, BGP determines the optimal path by picking the route that has the fewest number of ASs. Because BGP does not take link speed or network load into consideration when computing paths, the shortest path may not be the optimal one. BGP's Local Preference attribute [Stewart99] allows some control over route selection. This attribute forces BGP to choose a particular route out of an AS when there are multiple choices. Another BGP attribute, Multi-Exit Discriminator (MED) [Rekhter+95], helps control the path taken by traffic coming into an AS.
BGP routing can be controlled through the Community attribute that identifies a group or community of routes. A BGP router takes a predefined action based on the value of the attribute. This value can be defined by the network administrator, but a well-known value corresponds to the predefined community, called No-Export. When a BGP router sees a route come in with the No-Export community, it will not advertise the route outside its own AS. This can be handy for balancing incoming traffic.