| Note |
|
| Note |
|
Routing Protocol Features
There are many ways to characterize routing protocols, including the following:
The following sections discuss these methods in detail.
Static Versus Dynamic Routing
Whereas static routes are typically configured manually, routing protocols generate dynamic routes. Each method has advantages and disadvantages in specific network scenarios, as discussed in the following sections.
Static Routing
The term static routing denotes the use of manually configured or injected static routes for traffic forwarding purposes. Using a static route might be appropriate in the following circumstances:
- When it is undesirable to have dynamic routing updates forwarded across slow bandwidth links, such as a dialup link
- When the administrator needs total control over the routes used by the router
- When a backup to a dynamically learned route is necessary
- When it is necessary to reach a network that is accessible by only one path (a stub network)
Configuring and maintaining static routes is time-consuming. Properly implementing static routes requires complete knowledge of the entire network.
Figure 7-1 illustrates a stub network scenario in which the use of static routes is favored over a dynamic routing protocol. The right side of Figure 7-1 shows a stub network with a single entry/ exit point over the S0 interface of Router A. On the stub network router (Router A), a static default route is configured so that the S0 link forwards all traffic toward destinations outside the stub network. On Router B, a static route is installed toward the stub network and then is redistributed into the routing protocol so that reachability information for the stub network is available throughout the rest of the network.
| Note |
|
By using static and default static routes in this scenario, no traffic from a dynamic routing protocol is present on the serial link or in the stub network. In addition, the processor and memory requirements for both routers are lower; in the stub network, a low-end router would suffice. Static routes are therefore appropriate in situations such as with stub networks, hub-and-spoke connections (also called star connections), and dialup environments.
Dynamic Routing
Dynamic routing allows the network to adjust to changes in the topology automatically, without administrator involvement. A static route cannot dynamically respond to changes in the network. If a link fails, the static route is no longer valid if it is configured to use that failed link, so a new static route must be configured. If a new router or new link is added, that information must also be configured on every router in the network. In a very large or unstable network, these changes can lead to considerable work for network administrators. It can also take a long time for every router in the network to receive the correct information. In situations such as these, it might be better to have the routers receive information about networks and links from each other using a dynamic routing protocol. Dynamic routing protocols must do the following:
- Find sources from which routing information can be received (usually neighboring routers)
- Select the best paths toward all reachable destinations, based on received information
- Maintain this routing information
- Have a means of verifying routing information (periodic updates or refreshes)
When using a dynamic routing protocol, the administrator configures the routing protocol on each router. The routers then exchange information about the reachable networks and the state of each network. Routers exchange information only with other routers running the same routing protocol. When the network topology changes, the new information is dynamically propagated throughout the network, and each router updates its routing table to reflect the changes.
Interior Versus Exterior Routing Protocols
An autonomous system (AS), also known as a domain, is a collection of routers that are under a common administration, such as a company’s internal network or an Internet service provider’s (ISP’s) network.
Because the Internet is based on the AS concept, two types of routing protocols are required:
- Interior gateway protocols (IGP) are intra-AS (inside an AS) routing protocols. Examples of IGPs include Routing Information Protocol (RIP) version 1 (RIPv1), RIP version 2 (RIPv2), Open Shortest Path First (OSPF), Integrated Intermediate System-to-Intermediate System (IS-IS), and Enhanced Interior Gateway Routing Protocol (EIGRP).
- Exterior gateway protocols (EGP) are inter-AS (between autonomous systems) routing protocols. Border Gateway Protocol (BGP) is the only widely used EGP protocol on the Internet. BGP version 4 (BGP-4) is considered the acceptable version of BGP on the Internet. It is discussed in the “Border Gateway Protocol” section.
Different types of protocols are required for the following reasons:
- Inter-AS connections require more options for manual selection of routing characteristics. EGPs should be able to implement various policies.
- The speed of convergence (distribution of routing information) and finding the best path to the destination are crucial for intra-AS routing protocols.
Therefore, EGP routing protocol metrics (used to measure paths to a destination) include more parameters to allow the administrator to influence the selection of certain routing paths. EGPs are slower to converge and more complex to configure. IGPs use less-complicated metrics to ease configuration and speed up the decisions about best routing paths for faster convergence. The “Routing Protocol Metrics” section later in this chapter defines and explains routing protocol metrics.
IGP and EGP Example
Figure 7-2 shows three interconnected autonomous systems (domains). Each AS uses an IGP for intra-AS (intra-domain) routing.
Figure 7-2: Interior Protocols Are Used Inside and Exterior Protocols Are Used Between Autonomous Systems The autonomous systems require some form of interdomain routing to communicate with each other. Static routes are used in simple cases; typically, an EGP is used.
BGP-4 is the dominant EGP currently in use; BGP-4 and its extensions are the only acceptable version of BGP available for use on the public Internet.
Multihoming is when an AS has more than one connection to the Internet (for redundancy or to increase performance). BGP is particularly useful when an AS multihomes to the Internet via multiple ISPs, as illustrated in Figure 7-2. To comply with the contractual requirements from specific ISPs, an administrator uses BGP to apply specific policies—for example, to define traffic exit points, return traffic paths, and levels of quality of service (QoS).
Distance Vector Versus Link-State Versus Hybrid Protocols
There are two main types of routing protocols:
- Distance vector protocol: In a distance vector protocol, routing decisions are made on a hop-by-hop basis. Each router relies on its neighbor routers to make the correct routing decisions. The router passes only the results of this decision (its routing table) to its neighbors. Distance vector protocols are typically slower to converge and do not scale well; however, they are easy to implement and maintain. Examples of distance vector protocols include RIPv1, RIPv2, and Interior Gateway Routing Protocol (IGRP).
Note Although they are all distance vector protocols, RIPv1 uses broadcast packets to advertise routes, whereas RIPv2 uses multicast packets.Note Note A network is converged when routing tables on all routers in the network are synchronized and contain a route to all destination networks. Convergence is discussed in detail in the “Routing Protocol Convergence” section later in this chapter. - Link-state protocol: Each router floods information about itself (its link states) either to all other routers in the network or to a part of the network (area). Each router makes its own routing decision based on all received information and using the shortest path first (SPF) algorithm (also called the Dijkstra algorithm), which calculates the shortest path to any destination. Link-state protocols are fast to converge, have less routing traffic overhead, and scale well. However, because of their complexity, link-state protocols are more difficult to implement and maintain. The IP link-state protocols are OSPF and Integrated IS-IS.
| Note |
|
A third type of protocol also exists: the hybrid interior gateway protocol, which is the Cisco EIGRP. EIGRP has characteristics of both distance vector and link-state protocols; it combines distance vector behavior with some link-state characteristics and some proprietary features. EIGRP is a fast-converging and scalable routing protocol.
| Note |
|
Routers running link-state and hybrid protocols use multicast packets to communicate with each other.
When a network is using a distance vector routing protocol, all the routers periodically send their routing tables, or a portion of their tables, to only their neighboring routers.
In contrast, when a network is using a link-state routing protocol, each of the routers sends the state of its own interfaces (its links) to all other routers, or to all routers in a part of the network known as an area, only when there is a change.
Routers running a hybrid protocol send changed information only when there is a change (similar to link-state protocols), but only to neighboring routers (similar to distance vector protocols).
Table 7-1 summarizes the IP routing protocol types.
|
|
|
|---|---|
|
|
|
|
|
|
|
|
|
Open table as spreadsheetDistance Vector Example
A distance vector router’s understanding of the network is based on its neighbor’s perspective of the topology; consequently, the distance vector approach is sometimes referred to as routing by rumor. Routers running traditional distance vector protocols periodically send their complete routing tables to all connected neighbors. Convergence might be slow because triggered updates are not typically used (RIPv2 is an exception) and loop detection timers are long. In large networks, running a distance vector protocol might cause routing tables to become enormous and result in a lot of traffic on the links.
| Note |
|
| Note |
|
Figure 7-3 shows a sample network that runs a distance vector protocol. In this network, the routing updates are periodic and include the entire routing table.
RIPv2, which is a standardized protocol developed from the RIPv1 protocol, is an example of a distance vector protocol. The characteristics of RIPv2 include the following:
- The hop count is used as the metric for path selection.
- The maximum allowable hop count is 15.
- By default, routing updates are sent every 30 seconds (RIPv1 uses broadcast, and RIPv2 uses multicast).
- RIPv2 supports variable-length subnet masking (VLSM); RIPv1 does not. Chapter 6, “Designing IP Addressing in the Network,” describes VLSM.
Link-State Example
Both OSPF and Integrated IS-IS use the Hello protocol for establishing neighbor relationships. Those relationships are stored in a neighbor table (also called an adjacencies database). Each router learns a complete network topology from information shared through these neighbor relationships. That topology is stored in the router’s link-state database (LSDB), also called the topology table or topology database. Each router uses this topology and the SPF algorithm to create a shortest-path tree for all reachable destinations. Each router selects the best routes from its SPF tree and places them in its routing table (also called the forwarding database).
You can think of the LSDB as being like a map in a shopping mall. Every map in the mall is the same, just as the LSDB is the same in all routers within an area. The one difference between all the maps in a shopping mall is the “you are here” dot. By looking at this dot, you can determine the best way to get to every store from your current location; the best path to a specific store is different from each location in the mall. Link-state routers function similarly: They each calculate the best way to every network within the area, from their own perspective, using the LSDB.
Figure 7-4 shows a network that uses a link-state protocol. Triggered updates, which include data on the state of only links that have changed, are sent in this network.
In link-state protocols, the information about connected links (including the subnets on those links) on all routers is flooded throughout the network or to a specific area of the network. Therefore, all routers in the network have detailed knowledge of the entire network. In contrast, routers running a distance vector routing protocol receive knowledge about only the best routes from their neighbors.
After the initial exchange of all link states and on reaching the full (converged) state of operation, almost no periodic updates are sent through the network. (In OSPF, periodic updates are sent every 30 minutes for each specific route, but not at the same time for all routes, reducing the routing traffic volume.) Triggered updates are flooded through the network only when a change in a link state occurs (the link goes down, comes up, or link parameters that affect routing—such as bandwidth—are changed). Only periodic hello messages are sent between neighbors to maintain and verify neighbor relationships.
Most of the control packets used in link-state operations are sent as multicast packets, which might cause problems when deploying link-state protocols in nonbroadcast multiaccess (NBMA) networks, such as with Frame Relay or ATM topologies.
Routing Protocol Metrics
This section introduces routing protocol metrics and compares the metrics used by different routing protocols.
What Is a Routing Metric?
A metric is a value (such as path length) that routing protocols use to measure paths to a destination.
Different routing protocols base their metric on different measurements, including hop count, interface speed, or more-complex metrics. Most routing protocols maintain databases containing all the networks that the routing protocol recognizes and all the paths to each network. If a routing protocol recognizes more than one way to reach a network, it compares the metric for each different path and chooses the path with the lowest metric. If multiple paths have the same metric, a maximum of 16 can be installed in the routing table, and the router can perform load balancing among them. EIGRP can also perform load balancing between unequal-cost paths.
| Note |
|
Figure 7-5 shows network 172.16.1.0, which is connected to Router A. The parameters for route metric calculation are forwarded in routing protocol updates.
In this case, the EIGRP method of route metric parameters is used, and the minimum bandwidth and cumulative delay influence best path selection (the path with the highest minimum bandwidth and lowest delay is preferred). Figure 7-5 shows the following steps:
|
|
|
|
|
|
|
|
|
Metrics Used by Routing Protocols
Different routing protocols calculate their routing metrics from different parameters and with different formulas. Some use simple metrics (such as RIPv1 and RIPv2), and some use complex metrics (such as EIGRP).
RIPv1 and RIPv2 use only the hop count to determine the best path (the path with the smallest hop count is preferred). Because they do not consider bandwidth, RIPv1 and RIPv2 are not suitable for networks that have significantly different transmission speeds on redundant paths. For networks that use diverse media on redundant paths, routing protocols must account for bandwidth and possibly the delay of the links.
By default EIGRP uses the minimum bandwidth and accumulated delay of the path toward the destination network in its metric calculation. Other parameters (reliability and load) can also be used, but they should be configured only if the consequences are fully understood. If misconfigured, they might affect convergence and cause routing loops.
| Note |
|
EIGRP’s minimum bandwidth is the minimum (slowest) bandwidth along the path. An interface’s bandwidth is either the default value of the interface or as specified by the bandwidth command—this command is usually used on serial interfaces.
| Note |
|
EIGRP calculates the metric by adding weighted values of different link characteristics to a destination network. The formula used is as follows:
|
|
If K5 does not equal 0, an additional operation is performed:
|
|
The K values in the previous formulas are constants with default values of K1 = K3 = 1 and K2 = K4 = K5 = 0. Therefore, by default, the formula is the following:
|
|
The bandwidth used in this formula is calculated using the smallest (slowest) bandwidth along the path between the source and the destination, in kilobits per second (kbps). 107 is divided by that value, and the result is multiplied by 256.
The delay used in this formula is the sum of the delays in the path from the source to the destination, in tens of microseconds, multiplied by 256. Figure 7-6 presents a sample network to illustrate the EIGRP metric calculation.
In Figure 7-6, Router B advertises network 10.1.1.0 to Router A. The metric that Router B advertises for 10.1.1.0 is calculated as follows:
- Bandwidth = (10,000,000/1,544) * 256 = 6476 * 256 = 1,658,031
- Delay = (20,000/10) * 256 = 2000 * 256 = 512,000
- Metric = Bandwidth + Delay = 2,170,031
Router A calculates the metric it puts in its routing table for 10.1.1.0 as follows:
- Bandwidth = (10,000,000/128) * 256 = 20,000,000 (using the minimum bandwidth in the path—in this case, 128 kbps)
- Delay = ((20,000 + 20,000)/10) * 256 = 1,024,000
- Metric = Bandwidth + Delay = 21,024,000
The IGRP metric is the EIGRP metric divided by 256 because the metric for EIGRP is a 32-bit number versus the IGRP 24-bit metric; accordingly, EIGRP has additional granularity for route selection.
In the case of link-state protocols (OSPF and IS-IS), a cumulative cost or metric is used (the lowest cost or metric path is selected). OSPF uses cost for path calculation, usually reflecting the link’s bandwidth. As a result, the highest accumulated bandwidth (lowest cost) is used to select the best path. The IS-IS interface metric defaults to 10 on Cisco routers; this value can be changed, to reflect different bandwidths, for example.
| Note |
|
BGP uses the AS-path attribute as part of its metric. The length of this attribute is the number of autonomous systems that must be traversed to reach a destination and is usually a factor that influences the path selection. BGP incorporates additional path attributes that can influence routing decisions; these can be manually configured.
Routing Protocol Convergence
Whenever a change occurs in a network’s topology, all the routers in that network must learn the new topology. This process is both collaborative and independent; the routers share information with each other, but they must calculate the impact of the topology change independently. Because they must mutually develop an independent agreement on the new topology, they are said to converge on this consensus.
Convergence properties include the speed of propagation of routing information and the calculation of optimal paths. The quicker the convergence, the more optimal the routing protocol is said to be.
Recall that a network is converged when all routing tables are synchronized and each contains a usable route to each destination network.
Convergence time is the time it takes for all routers in a network to agree on the current topology. The size of the network, the routing protocol in use, the network design, and numerous configurable timers can affect convergence time. For example, the use of hierarchical addressing and summarization helps localize topology changes, which speeds convergence.
Network convergence must occur whenever a new routing protocol starts and whenever a change takes place in the network. It occurs in both new networks and those that are already operational. Convergence is also important when changes occur in the network.
A network is not completely operable until it has converged. Therefore, short convergence times are required for routing protocols.
RIPv2 Convergence Example
RIPv2 is a distance vector protocol that periodically propagates its routing information. Distance vector protocols use the principle of hold-down to prevent routing loops. Putting a route in hold-down after the route has failed (perhaps due to a link failure) means that if a routing update arrives with the same or a worse metric, the new route is not installed until the hold-down timer expires. Even though the destination might no longer be reachable, a route in hold-down is still used to forward traffic during the entire hold-down period.
Figure 7-7 shows a network running RIPv2; the Ethernet link (Network N) between Routers A and C has failed. The following are the RIPv2 convergence steps:
Therefore, the convergence time at Router E is the hold-down time plus one or two update intervals.
| Note |
|
Comparison of Routing Protocol Convergence
As shown in Figure 7-8, different routing protocols need different amounts of time to converge in a given network. Although the convergence depends on the network’s topology and structure, pure distance vector protocols are slower to converge than link-state protocols. The use of periodic updates and the hold-down mechanism are the main reasons for slow convergence. As a result, the fast-converging protocols should be used when the network’s convergence time is crucial.
Link-state protocols usually converge much more quickly because they instantly propagate routing updates. Whenever a change occurs in a link’s state, a link-state update is flooded through the entire network. There is no need to wait for the hold-down timer to expire or for the next periodic update, as with distance vector protocols.
EIGRP is a special case because it incorporates the distance vector principle of metric propagation (it sends only the best routes to the neighbors). However, it does not have periodic updates, nor does it implement the principle of hold-downs. The most distinct feature of EIGRP is that it stores all feasible backup routes in its topology table. When a backup route exists for a lost destination, the switchover to the best backup route is almost immediate and involves no action from other routers. Therefore, very fast convergence can be achieved with proper EIGRP deployment.
Flat Versus Hierarchical Routing Protocols
Flat routing protocols propagate all routing information throughout the network, whereas hierarchical routing protocols divide large networks into smaller areas.
This section discusses these two types of routing protocols.
Flat Routing Protocols
Flat routing protocols have no means of limiting route propagation in a major network (within a Class A, B, or C network) environment. These protocols are typically classful distance vector protocols.
Recall from Chapter 6 that classful means that routing updates do not include subnet masks and that the protocol performs automatic route summarization on major network (class) boundaries. Summarization cannot be done within a major network. These protocols support only fixed-length subnet masking (FLSM); they do not support VLSM.
Recall also that distance vector protocols periodically send entire routing tables to neighbors. Distance vector protocols do not scale well because, in a large network, they produce significant volumes of routing information that consume too many network resources (CPU, bandwidth, memory). These resources should be available to the routed traffic (application data and user traffic) instead.
Two examples of flat routing protocols are RIPv1 and RIPv2. Note, however, that RIPv2 is a classless protocol. Figure 7-9 illustrates a flat network and a hierarchical network.
Hierarchical Routing Protocols
To solve the problems associated with flat routing protocols, additional features are implemented in hierarchical routing protocols to support large networks—for example, some support an area-based design.
Hierarchical routing protocols are typically classless link-state protocols. Recall from Chapter 6 that classless means that routing updates include subnet masks in their routing updates; therefore, the routing protocol supports VLSM.
Hierarchy is part of the implementation of link-state protocols with the concept of backbone and nonbackbone areas. With link-state protocols such as OSPF and IS-IS, large networks are divided into multiple areas.
Route summarization can be performed manually in hierarchical protocols and is required in most cases. With the help of route summarization, smaller routing updates propagate among areas, resulting in higher scalability. Instabilities in one part of the network are isolated, and convergence is greatly improved. Summarization can be performed on an arbitrary bit boundary within an IP address. Note, however, that OSPF supports summarization on only specific routers called area border routers and autonomous system boundary routers.
Although it is a classless hybrid protocol, EIGRP is considered a flat routing protocol because it is not area-based. Because EIGRP also supports manual summarization, EIGRP can be used in a hierarchical network design by dividing the network into areas. A hierarchical design is not necessary in EIGRP, but one is recommended for large networks.
| Note |
|
0 comments
Post a Comment