Archive for the 'Al Friebe' Category

« Previous Entries
Next Entries »

OSPF, Part 2

Published November 6, 2009 Al Friebe , Routing & Switching Leave a Comment
Tags:

In this installment, we’ll continue our look at OSPF (Open Shortest Path First). As we’ve seen, each router originates a Link State Advertisement (LSA), which is flooded throughout the internetwork. The LSA contains prefix and metric information for each link to which that router is directly connected. Each router maintains a Link State Database (LSDB) which contains copies of all LSAs the router has learned. Thus, the LSDB represents the detailed topology of the internetwork. Using Dijkstra’s SPF algorithm, each router independently uses its copy of the LSDB to develop its routing table.

So that all routers know which router originated which LSA, each LSA is uniquely identified by the originating router’s OSPF router ID. Like an IP address, an OSPF router ID is a 32-bit binary value that is commonly represented in dotted-decimal format. An OSPF router ID is assigned or selected as follows:

  • If a “router-id” command appears under the OSPF process, that’s it.
  • If not, it’s the highest IP address amongst the active loopback interfaces.
  • If there are no active loopbacks, it’s the highest IP address amongst the active physical interfaces.

By active we mean not Administratively Down. In other words, a physical interface that’s Up/Down or Down/Down is still a candidate for OSPF router ID.

Note that although an OSPF router ID looks like an IP address, and may have been derived from an IP address, it is not an IP address. Instead, the router ID is used to uniquely identify the originator of a particular LSA within the LSDBs.

Key point: If you’re setting the OSPF router IDs manually using either router-id commands or loopbacks, they had better be unique! If not, corruption of the LSDBs and of the resulting routing tables can occur.

Two OSPF neighbors-to-be begin in the Down state. Once one of the potential neighbors has sent a hello, the neighbors move to Init state. To go further, the routers must agree on the following items with regard to the link which connects them:

  • The subnet of the link
  • The OSPF Hello and Dead intervals for the link
  • The OSPF area within which the link resides
  • Whether or not that area is an OSPF “stub” area
  • Authentication type and keystring (if configured)

Assuming that the conditions are met, the neighbors proceed to Two-Way, which means that the neighbor relationship has been confirmed.

In the case of a point-to-point link (such as a serial link running HDLC or PPP), once the routers are Two-Way, they immediately proceed through Exstart, Exchange, and Loading, to Full state. Once they’ve reached Full state, their LSDBs are synchronized.

Next time, we’ll see how we handle LSDB synchronization on multi-access media, such as Ethernet LANs and Frame Relay WANs.

Author: Al Friebe

OSPF, Part 1

Published November 2, 2009 Al Friebe , Routing & Switching Leave a Comment
Tags: ,

Having discussed the big picture when it comes to Link-State protocols, let’s now take a more detailed look. With IP there are two Link-State protocols in use:

  • OSPF: Open Shortest Path First
  • IS-IS: Intermediate System to Intermediate System

Both work in pretty much the same way, but because it’s more commonly used, for now we’ll focus on OSPF.

In an OSPF router, the topology database is referred to as the Link State Database (LSDB). The LSDB contains the detailed information that a router has regarding the topology of the internetwork. Each entry in the LSDB is called a Link State Advertisement (LSA). In OSPF, there are five packet types used:

  • Hello: Used to build and maintain neighbor relationships.
  • DBD: Database Description, a summary of the LSDB.
  • LSR: Link State Request, used to request one or more missing LSAs.
  • LSU: Link State Update, used to send one or more LSAs.
  • LSAck: Link State Acknowledgement, used to acknowledge receipt of a LSU.

When a new neighbor is found, an OSPF router’s goal is to synchronize its LSDB with that of the neighbor. By “synchronize” we mean make the LSDBs consistent, so that they contain the same LSAs. To accomplish this, the routers compare LSDBs (“You show me yours, and I’ll show you mine!”) and any LSA that a router is missing it requests from the neighbor. During this process, the neighbors proceed through the following OSPF states:

  • Down: The start of the neighbor process.
  • Init: The neighbor relationship is being initialized.
  • Two-Way: The neighbor relationship has been confirmed.
  • Exstart: The routers negotiate which sends its DBD first.
  • Exchange: The DBDs are being exchanged.
  • Loading: The LSRs and LSUs are being exchanged.
  • Full: The LSDBs are synchronized.

Once the LSDB is complete, a router runs the Shortest Path First (SPF) algorithm, generating its routing table. In OSPF the metric is cost, and SPF finds the lowest cost path to each destination prefix. Note that SPF is where OSPF gets its name: it’s an “Open” (non-proprietary) protocol that uses SPF. The SPF algorithm is commonly referred to as “Dijkstra’s Algorithm”, after Edsger Dijkstra (pronounced Dike-stra), the computer scientist who developed it.

After the routing tables have been generated, the network is converged. The goal is to maintain full state (LSDB synchronization) with the neighbors. Let’s say that router R1 senses a topology change, such as gaining or losing a link. It will then update the R1 LSA in its LSDB, flood a copy of the revised R1 LSA to its neighbors, and run SPF to regenerate its routing table. R1’s neighbors will acknowledge receipt of R1’s revised LSA, replace the old R1 LSA in their LSDBs with the new R1 LSA, flood the new R1 LSA to their neighbors, and run SPF. In this manner, the new R1 LSA propagates throughout the internetwork, and as it does it updates the LSDB, triggers SPF, and regenerates the routing table of each router. Once this process is complete (and it typically takes only seconds) routing is again converged.

LSUs are sent only when changes occur (that is, they’re triggered updates), so in between LSUs a router sends periodic Hellos to reassure its neighbors of its continued presence. Since Hellos are small, they don’t take much bandwidth or CPU power to process, and can be sent relatively frequently (every few seconds is typical). Because changes are only being advertised when they occur, the result is that Link-State protocols such as OSPF scale better than Distance-Vector protocols like RIP, which periodically flood the entire routing table even in the absence of any changes.

Next time, we’ll look at some additional details and enhancements regarding OSPF.

Author: Al Friebe

Routing Protocols, Part 6

Published October 26, 2009 Al Friebe , Routing & Switching Leave a Comment
Tags:

We’ve discussed several techniques to improve the performance of Distance-Vector (D-V) protocols. With that accomplished, the next thing to do is to examine their scalability. With the D-V protocols, as the size of an internetwork grows, the number of prefixes to be advertised and stored grows, requiring greater bandwidth and RAM. Also, as the number of routing updates increases, more CPU power is required to send and receive the updates.

Around 1990, based on the projected growth of internetworks, it became apparent that the scalability of the D-V protocols would present a problem. To deal with this, an entirely new category of routing protocols was developed: the “Link-State” protocols.

Each Link-State router builds a topology database that contains everything that router knows about the topology of the internetwork. This information includes which IP prefixes are directly connected to which routers, and the metric information for each prefix. It’s referred to as a “Link-State” protocol because each router knows the detailed prefix (link) and metric (state) information…in other words, the state of the links.

It’s like a jigsaw puzzle, where each router contributes a piece of the puzzle (the prefixes to which it is directly connected). The goal is to collect all of the pieces, and then assemble the puzzle.

Each router begins by placing an entry for itself in its topology database. Next, the router uses a “hello” protocol to discover its directly connected neighbors. The neighbors then exchange topology information. When an update containing new topology information is received, the router adds that piece to its topology database, and then floods that piece. Each neighbor does the same. When this process is complete, all routers will have detailed information about the entire topology, and each router can then determine the best path from itself to each destination prefix.

Think of the internetwork as being like a shopping mall. There’s a map near each door that shows where all the stores are. Because it’s all one mall the maps are identical, except for one thing: the “You Are Here” marker. We can use the nearest map to find the best route from where we are to each of the stores that we’d like to visit. Similarly, each router has a topology database. Because all of the routers are part of one internetwork, all of the topology databases are identical. Using its copy of the topology database, each router individually calculates the best next hop for each known destination prefix, and places this information in its routing table. At this point, routing has converged.

There are, however, a few differences between a real Link-State protocol and our shopping mall analogy. First, the maps in the mall are diagrams, while routers keep the topology databases in table form. Second, while most shoppers are interested in visiting only a few stores within the mall (there may be exceptions), routers calculate the best next hop for all known prefixes.

Key Point: With a Link-State protocol, what’s being advertised from one router to another is raw topology information, not routing table entries. As a result, each Link-State router knows the entire topology of the internetwork. Since the topology updates are acknowledged (making the protocol reliable), there is no need for frequent periodic updates. Instead, updates need only be sent when a topology change occurs. In between changes, the hello protocol is used to verify the continued availability of neighbors.

Next time, we’ll look at Link-State protocols in more detail, including some real-world examples.

Author: Al Friebe

NAT and PAT – Part 4 (A New Perspective)

Published October 19, 2009 Al Friebe , Routing & Switching 1 Comment
Tags:

Many people are confused by Cisco’s NAT/PAT naming conventions, such as “inside local”, etc. Since a picture is worth a kiloword, I thought that perhaps a few diagrams might help.

Let’s say that our host H1 has IP address 10.1.1.1/24, an RFC 1918 private address. We want to cross the Internet to access host H2, which has the public IP address 198.133.219.25, as shown in Figure 1:

Slide1

Because we can’t advertise RFC 1918 addresses to the public Internet, in order to make this work we’re going to perform PAT (overloading) on R1, our edge router. Let’s assume that our internal LAN, with address space 10.1.1.0/24, is connected to R1’s Ethernet 0 interface. We’ll be overloading on Serial 0, which has the IP address 64.82.100.67, in public space. To accomplish the translation, the commands would be:

  • R1(config)#access-list 1 permit 10.1.1.0 0.0.0.255
  • R1(config)#ip nat inside source list 1interface serial 0 overload
  • R1(config)#int e0
  • R1(config-if)#ip nat inside
  • R1(config-if)#int s0
  • R1(config-if)#ip nat outside

Figure 2 summarizes the situation at this point:

Slide2

Inside and Outside: These refer to the physical location of the device whose address is being referenced. The physical locations were unambiguously defined by configuring the appropriate router interfaces with these commands:

  • ip nat inside
  • ip nat outside

In our example, R1 is doing the translation, with the “inside” interface attached to our LAN, and the “outside” interface on the WAN link to our service provider.

Key point: Because of the way we have configured R1’s interfaces, “inside” is defined to mean “located on our side of R1”, and “outside” means “located on the far side of R1”.

Local and Global: These refer to the perspective (viewpoint) from which the address is being observed, not where the device is located.

Key point: In our example, “local” is defined to mean “looking at it from our side of R1”, and “global” means “looking at it from the far side of R1”.

Yeah, yeah…but what about “inside local”? The key to the jargon is to realize that it describes what we’re looking at, and from where in that order. It’s location-perspective. In other words, “inside local” means that we’re looking at the address of an “inside” device (on our side of our router), from our “local” perspective (from our side of our router). Given the two locations (inside and outside), and the two perspectives (local and global), there are four possibilities:

  • Inside Local
  • Inside Global
  • Outside Local
  • Outside Global

We’ll discuss each of these in turn. Since humans can’t actually see the packets as they traverse the media, by “looking” we mean what we would “see” if we were to install protocol analyzers “locally” and “globally”, and examine the addresses within the packets’ IP headers. Since I can’t draw a protocol analyzer, in the diagrams I’ll use an “X-ray eyeball” that’s able to see the packet headers.

Inside Local: Viewing an “inside” device from the “local” perspective, as shown in Figure 3. This is how we see the IP address of H1 from our side of R1. In our example, the “inside local” address is 10.1.1.1, which is the actual address of H1.

Slide3

Inside Global: Viewing an “inside” device from the “global” perspective, as shown in Figure 4. This is how the Internet sees the IP address of H1. In our example, the “inside global” address is 64.82.100.67, the translated address of H1.

Slide4

Outside Local: Viewing an “outside” device from the “local” perspective, as shown in Figure 5. This is how H1 sees the IP address of H2. In our example, the “outside local” address is 198.133.219.25, which is not being translated.

Slide5

Outside Global: Viewing an “outside” device from the “global” perspective, as shown in Figure 6. This is how the Internet sees the IP address of H2. In our example, the “outside global” address is 198.133.219.25, which is H2’s actual address.

Slide6

Since in our example we’re not translating the destination address on the way out (nor the source address on the way back), the “outside local” and “outside global” addresses are identical. Figure 7 shows our current situation, including the four combinations of location and perspective, along with the corresponding addresses.

Slide7

Key point: It’s possible that NAT/PAT is also being done on H2’s side, but there is no way we can tell that from our side. If so, they would have their own versions of inside/ outside and local/global that have nothing whatsoever to do with ours.

No matter what terms Cisco chose to use, it would boil down to the same location-perspective issue.  So it is what it is, and that’s “what we’re looking at, and from where”.

And, yes, I still often put my fingers on the diagram and talk to myself when figuring this stuff out. “Inside global…so we’re talking about the inside stuff” while my left hand is pointing to the LAN…“from the global perspective” …my right hand is pointing to the Internet, and sliding from right to left to show the direction I’m looking.

By the way, although we used PAT (overloading) in our example, the “location-perspective” terms work the same way for static and dynamic NAT.

Author: Al Friebe

Routing Protocols – Part 5

Published October 14, 2009 Al Friebe , Routing & Switching 1 Comment
Tags:

Continuing on with our discussion of improvements to Distance-Vector protocols, we were about to discuss hold down timers. Here’s our topology:
Routing_Part5_Fig1

Let’s go back to the initial conditions, where the 10.1.0.0/16 subnet was reachable. At that point, we had:

  • R1 sees 10.1.0.0/16 as directly connected (zero hops)
  • R2 sees 10.1.0.0/16 as reachable via R1 (one hop)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Since R2 and R3 consider R1 to be their best next hop to reach 10.1.0.0/16, per the split-horizon rule neither R2 nor R3 is advertising 10.1.0.0/16 to R1, but they are advertising it to each other. Let’s assume that R1 loses its connection to the 10.1.0.0/16 subnet, we then have:

  • R1 sees 10.1.0.0/16 as unreachable
  • R2 sees 10.1.0.0/16 as reachable via R1 (one hop)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Notice that R2 and R3 are currently mistaken as to the state of 10.1.0.0/16. At this time, R1 sends flash updates to R2 and R3, poisoning the route to 10.1.0.0/16. Let’s imagine that R2 processes the flash update prior to R3. Upon receipt of a poisoned update, a router will place the prefix into “hold down”, meaning that it will:

  • Start a hold down timer for that prefix
  • Mark the prefix as “possibly down”
  • Flood poison updates for the prefix
  • Continue routing packets for that prefix as before
  • Ignore updates for the prefix, unless the metric is better than before

The route stays in hold down until either the hold down timer expires, or a route for that prefix with a better metric is learned.

When a route is in hold down, packets for the prefix are routed as before, in case the route has come back up. The situation at this moment is:

  • R1 sees 10.1.0.0/16 as unreachable
  • R2 sees 10.1.0.0/16 as “possibly down” via R1 (one hop)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Notice R2 now has 10.1.0.0/16 in hold down, and that R3 is currently mistaken. Let’s imagine that just before processing the flash update it received from R1, R3’s periodic update timer expires, and R3 sends its routing table to R2. Since 10.1.0.0/16 is in hold down on R2, the update from R3 (with a metric of two hops, worse than R2’s previous best metric of one hop) is ignored. Thus, the situation remains:

  • R1 sees 10.1.0.0/16 as unreachable
  • R2 sees 10.1.0.0/16 as “possibly down” via R1 (one hop)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Shortly thereafter, R3 processes the triggered update it received from R1, and also places 10.1.0.0/16 in hold down. The situation is now:

  • R1 sees 10.1.0.0/16 as unreachable
  • R2 sees 10.1.0.0/16 as “possibly down” via R1 (one hop)
  • R3 sees 10.1.0.0/16 as “possibly down” via R1 (one hop)

In accordance with the hold down rules, any packets received by either R2 or R3 that are bound for 10.1.0.0/16 will still be forwarded to R1, which will drop them or forward them depending on the actual state of that prefix. Obviously, no routing loop exists, but since neither R2 nor R3 is sure of the topology, the network is not yet converged.

Eventually the hold down timers on R2 and R3 will expire. At that point, either 10.1.0.0/16 is reachable, or it is not. If it’s reachable, R1 will be periodically advertising it to R2 and R3, which will restore it to their routing tables as a normal route. If it’s not reachable, both R2 and R3 will remove it from their routing tables when their flush timers expire. Either way, shortly after the hold down timers expire, the network will be converged.

We’ve looked at six techniques for improving the performance of Distance-Vector routing protocols, including:

  • Defining a Maximum
  • Split Horizon
  • Route Poisoning
  • Poison Reverse
  • Triggered Updates
  • Hold Down Timers

In Cisco’s implementation of RIP, which uses all six techniques, the default values of the timers are:

  • Update – 30 seconds
  • Invalid – 180 seconds
  • Hold Down – 180 seconds
  • Flush – 240 seconds

The timers can be viewed with the show ip protocols command, and changed under the RIP routing process with the timers basic command.

Author: Al Friebe

Routing Protocols – Part 4

Published October 5, 2009 Al Friebe , Routing & Switching Leave a Comment
Tags:

Continuing our discussion of techniques for improving the performance of Distance-Vector routing protocols, imagine that we have a topology route_image2consisting of three routers (R1, R2 and R3) in a triangle, with each router directly connected to the other two (a full mesh). R1 also has a directly connected stub route, 10.1.0.0/16, for a total of four subnets.

Once the network has converged, the situation will be:

  • R1 sees 10.1.0.0/16 as directly connected (zero hops)
  • R2 sees 10.1.0.0/16 as reachable via R1 (one hop)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Since R2 and R3 consider R1 to be their best next hop to reach 10.1.0.0/16, per the split-horizon rule neither R2 nor R3 is advertising 10.1.0.0/16 to R1, but they are advertising it to each other. Let’s assume that R1 loses its connection to the 10.1.0.0/16 subnet, and thus from the routers’ perspectives we now have:

  • R1 sees 10.1.0.0/16 as unreachable
  • R2 sees 10.1.0.0/16 as reachable via R1 (one hop)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Notice that R2 and R3 are currently mistaken as to the state of 10.1.0.0/16. At this time, R1 sends flash updates to R2 and R3, poisoning the route to 10.1.0.0/16. Let’s imagine that R2 processes the flash update prior to R3. The situation at this moment is:

  • R1 sees 10.1.0.0/16 as unreachable
  • R2 sees 10.1.0.0/16 as unreachable
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Notice that R3 is currently mistaken. Let’s imagine that just before processing the flash update it received from R1, R3’s periodic update timer expires, so R3 sends its routing table to R2. The current situation is:

  • R1 sees 10.1.0.0/16 as unreachable
  • R2 sees 10.1.0.0/16 as reachable via R3 (two hops)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Now R2 and R3 are both mistaken. Since R2 did not receive its best (and only) route for 10.1.0.0/16 from R1, it’s free to advertise the route to R1 via a flash update, which it does, resulting in:

  • R1 sees 10.1.0.0/16 as reachable via R2 (three hops)
  • R2 sees 10.1.0.0/16 as reachable via R3 (two hops)
  • R3 sees 10.1.0.0/16 as reachable via R1 (one hop)

Now all three routers are mistaken. Since R1 learned the best route to 10.1.0.0/16 from R2, it will not advertise it to R2, but it will advertise it to R3, giving us:

  • R1 sees 10.1.0.0/16 as reachable via R2 (three hops)
  • R2 sees 10.1.0.0/16 as reachable via R3 (two hops)
  • R3 sees 10.1.0.0/16 as reachable via R1 (four hops)

At this point, we have a routing loop, in which R1 advertises 10.1.0.0/16 to R3, R3 advertises it to R2, R2 advertises it to R1, etc. The result of this will be that data packets bound for 10.1.0.0/16 (which is actually unreachable by any router) will loop in the direction opposite to that taken by the routing updates.

As discussed before, each individual packet that becomes caught in the loop will be discarded when its TTL reaches zero, and the routing loop itself will end when the metrics count up to the maximum value. What it comes down to is that split horizon does not prevent routing loops in topologies that include three or more routers connected in a physical loop. To solve this problem, the “Hold Down” timer was introduced, which we’ll discuss in the next installment.

Author: Al Friebe

Routing Protocols – Part 3

Published September 28, 2009 Al Friebe , Routing & Switching Leave a Comment
Tags:

In this installment, we’ll look at some techniques for improving the performance of Distance-Vector (D-V) routing protocols.

As previously discussed, if a routing loop occurs between two routers, the routing updates will bounce between those routers. This is sometimes referred to as “routing feedback”. The metric for the prefix will count up to the maximum (as determined by the number of bits used to track the metric), roll over to zero, and then start counting upwards again (the “count to infinity”). This process, and thus the loop, will continue forever, and any data packet caught in the loop will ricochet between the routers until its IP TTL reaches zero, at which time it is discarded. This is a waste of bandwidth in the routers’ backplanes, and on the link connecting them.

Defining a Maximum
One thing we can do to break the loop is to enforce a rule that if a metric exceeds a specified maximum, that route is considered unreachable and removed from the routing table. Once the metric exceeds the max, the route will be removed from the routing table, and it will no longer be advertised to any neighbors. Eventually the route times out of the neighbors’ routing tables as well, and the network is converged. For IP RIP, for example, a metric of 16 or more hops is considered “infinity”. With an update timer of 30 seconds and a flush timer of 4 minutes, convergence for RIP should occur within 12 minutes.

Split Horizon
As we have seen, defining a maximum stops a routing loop from existing forever, but it could still last quite a while. What we’d like to do is prevent the loop from forming between the two routers in the first place. This can be accomplished by enforcing what is known as the “split horizon” rule. The split horizon rule says that

“It is never useful to advertise information back in the direction from which it came”

What this means is, if a router learns a route on one interface, and decides that’s the best way to reach that destination, it won’t advertise that route back out on that same interface. It will, however, advertise the route on the other interfaces. Thus, instead of just simple-mindedly sending its routing table out on every interface, the router actually filters the table in accordance with the split horizon rule, on a per-interface basis. This process of sending information out on all interfaces other than the one on which it is received is called “flooding”.

The split horizon rule has two effects. First, since a router can no longer advertise a “best” route back to the router from which it learned it, no loop can form between two routers. Second, the routers are not wasting each others’ time and bandwidth with redundant advertisements (why tell them what they told just you?). Note that it’s not a violation of split horizon for a router to advertise a better route to a prefix from neighbors from which it has learned an inferior route. In fact, it’s required! For IP RIP, which has a 4 minute flush timer and a 30 second update timer, the split horizon rule should reduce the convergence interval to less than 5 minutes.

Route Poisoning
Another refinement is what’s called “route poisoning”. The idea is that when a router learns that a route is unreachable, instead of just removing it from the routing table and no longer advertising it, it advertises the route with the maximum metric (which the routers treat as “infinity”), and then removes it. The effect of this is that routers are now able to explicitly inform their neighbors that they can no longer get packets to a prefix. Thus, instead of waiting for the flush timer to remove the route from the routing tables, it would be removed at the next update. For IP RIP, this would be within 30 seconds.

Poison Reverse
An enhancement to route poisoning goes by the name “poison reverse”. What this means is that when a router poisons a route (advertises it as unreachable), a neighbor that now has no route to that destination will echo the poisoning back. This makes sure that both routers know that the route is unreachable, and there is no way that a loop between those two routers could form. Note that poison reverse overrides the split horizon rule, but because the routers are advertising “bad news”, it’s allowed.

Triggered Updates
Continuing on in the spirit of shortening the convergence time, we could also have the routers advertise changes that occur when they occur. In other words, rather than waiting until the next update interval to inform their neighbors that the status of a route has changed, tell them right now using what is referred to as a “triggered” update (also known as a “triggered incremental” or “flash” update). A triggered update contains information only about the route for which the status has changed. This change could be that the route has become unreachable (route poisoning), that it has become reachable, or that its metric has changed. Flash updates occur in addition to the periodic flooding of the routing tables, and can reduce the convergence time to nearly zero.

Next time, we’ll continue our discussion of enhancements to Distance-Vector protocols.

Author: Al Friebe

Routing Protocols – Part 2

Published September 22, 2009 Al Friebe , Routing & Switching 1 Comment
Tags:

The Distance-Vector (D-V) protocols such as RIP work, but they’re not perfect. Let’s imagine that we have two routers (R1 and R2) and three subnets (10.1.0.0/16, 10.2.0.0/16 and 10.3.0.0/16), connected in a string, like this:

  • 10.1.0.0/16 – R1 – 10.2.0.0/16 – R2 – 10.3.0.0/16

Once the network has converged, both routers will know the best path to each of the three subnets. Looking specifically at the 10.3.0.0/16 subnet:

  • R2 sees 10.3.0.0/16 as directly connected  (zero hops)
  • R1 sees 10.3.0.0/16 as reachable via R2 (one hop)

Imagine now that the 10.3.0.0/16 subnet becomes unreachable, and R2 removes it from its routing table. Since we’re running RIP, a D-V protocol, each router is periodically flooding its routing table. At this moment R1, which is not yet aware of the change, sends its table to R2. As a result, R2, which can no longer reach 10.3.0.0/16 directly, now thinks that it can reach that subnet via R1, and that it is two hops away:

  • R2 sees 10.3.0.0/16 as reachable via R1 (two hops)
  • R1 sees 10.3.0.0/16 as reachable via R2 (one hop)

When R2 next floods its routing table, R1 will see that 10.3.0.0/16 is now reachable via R2, and that it’s three hops away:

  • R2 sees 10.3.0.0/16 as reachable via R1 (two hops)
  • R1 sees 10.3.0.0/16 as reachable via R2 (three hops)

When R1 next floods its routing table, we’ll have:

  • R2 sees 10.3.0.0/16 as reachable via R1 (four hops)
  • R1 sees 10.3.0.0/16 as reachable via R2 (three hops)

And after R2’s next update:

  • R2 sees 10.3.0.0/16 as reachable via R1 (four hops)
  • R1 sees 10.3.0.0/16 as reachable via R2 (five hops)

There are two things to note about the current situation. First, R1 thinks that it can reach 10.3.0.0/16 via R2, and R2 thinks that it can reach it via R1. The truth is that neither router can reach that subnet. The effect of this is that any packet destined for 10.3.0.0/16 will be caught in a routing loop between R1 and R2. This is bad because as R1 and R2 ping-pong the packet it’s wasting their time, as well as wasting bandwidth on the link between them. Fortunately the packet will not loop forever, because eventually the TTL of the packet will hit zero, at which time the packet will be discarded (see RFC 1812 for details).

Second, you’ll notice that the metrics are increasing with every update cycle. This behavior is referred to as the “count to infinity”, and it is a symptom of a routing loop in a D-V protocol. When the metric hits the maximum as determined by the number of bits in the metric field, it will next go back to zero, and the cycle will repeat.

It’s important to note that for a particular data packet that’s caught in the loop, the TTL field in the packet’s IP header is counting down towards zero (at which point the packet is discarded), while the metric fields in the routing tables are counting up to the max (at which point the cycle repeats). While an individual packet does not loop forever, the loop does last forever.

One could make the case that since the 10.3.0.0/16 subnet is unreachable, the fact that traffic for that subnet loops is a non-issue. However, since the looping traffic gets in the way of other traffic, this is not the case. Thus, having routing loops for unreachable destinations is sub-optimal, and we want the entries for any unreachable subnets removed from all routing tables as quickly as possible.

Next time, we’ll look at some techniques used with Distance-Vector protocols to solve the looping problem, and to speed convergence.

Author: Al Friebe

Routing Protocols – Part 1

Published September 14, 2009 Al Friebe , Routing & Switching Leave a Comment
Tags:

In this series, we’ll discuss routing and routing protocols. First, let’s define what we mean by a “route”. In common usage, a “route” is an entry in the IP routing table. You can display the IP routing table (available routes) with the command show ip route.

Each entry in the routing table gives the best way for that router to reach a particular IP prefix. Remember that a “prefix” is a particular address/mask combination. Examples of prefixes are:

  • 10.0.0.0/8 (a classful network)
  • 172.168.100/24 (a subnet)
  • 192.168.1.32/29 (another subnet)
  • 200.100.200.3/32 (a host route)
  • 0.0.0.0/0 (the default route)

For each prefix displayed in the routing table, the entry will indicate how the route was learned, the next hop router’s address and/or outbound interface used to reach it, and other information. Although a routing table entry always represents the best known way to reach a particular prefix, the router may be aware of other possible paths to that prefix. If so, those additional paths would be tracked in other behind-the-scenes data structures separate from the routing table.

There are three ways that a router can learn about the existence of a route:

  • Directly connected (to an interface)
  • Static configured (by a person)
  • Dynamically learned (via a routing protocol)

Directly connected routes are those prefixes to which the router has a direct physical connection. Assuming that the interface is “up/up”, the router will calculate the prefix based on the address and mask configured on the interface, and place a “C” (Connected) route for that prefix in the routing table.

Static routes are those that are configured by an administrator with the ip route command, instructing the router to use a particular next hop or outbound interface to reach a particular prefix. Assuming that the interface in question is “up/up”, the router will place an “S” (Static) route for that prefix in the routing table.

Dynamic routes are those learned via a routing protocol. The mechanism by which the router learns the route varies by routing protocol, as does the letter representing the way the route was learned. Examples include “R” (RIP), “O” (OSPF) and “D” (EIGRP) routes.

Once all routers have learned their best paths to all available prefixes, the network is said to be “converged”. Note that after the network is converged, the routers do not have identical routing tables, but the tables are consistent and correct. When a change occurs, the time lag between the change and re-convergence is referred to as the “convergence interval” or “convergence time”, and is a function of the routing protocol(s) and the size of the network.

We can classify the dynamic protocols several ways. First there’s the method of operation, which can include:

  • Distance-Vector (D-V)
  • Link-State
  • Hybrid
  • Path-Vector

The basic idea of a D-V protocol such as RIP is that each router determines its directly-connected routes, and places them in its routing table. The router then sends advertisements on all participating interfaces to inform its neighbors about what it knows.

When a router receives an update, it checks its routing table to see if the update contains an advertised prefix that was previously unknown. If so, that prefix is added to the routing table, with the advertising router as the best next hop.

If a router receives an advertisement for a known prefix, the router checks to see if the advertised route has a better metric than the current route. If so, the router updates the routing table to use the advertising router as the next hop for that prefix. If not, the router ignores the advertisement.

When all information has been passed around and the routing tables have stabilized, the network is converged. So that all routers become aware of changes to the topology in a timely fashion, the routing tables are advertised periodically.

D-V protocols get their name from the fact that each update sent from router to router is a mathematical vector (a multi-valued variable) containing prefix and metric (distance) information. The metric varies by routing protocol, and include such things as hop count, cost, bandwidth, and delay. The vectors used with routing protocols are mathematical vectors, not navigational vectors (such as Northeast).

Author: Al Friebe

IOS Tips and Tricks – Part 4

Published September 8, 2009 Al Friebe , Routing & Switching Leave a Comment
Tags:

Here we go again with more IOS tips. Although the examples are shown on routers, they also work on IOS-based switches.

To get a router to begin using the new IOS after an upgrade, you either have to power-cycle it or execute the privileged mode “reload” (software restart) command:

  • Router#reload

Let’s imagine that we’ve established a Telnet (or SSH) session to a router for some remote-control configuration. What if we make a mistake that not only terminates our session, but also prevents us from reconnecting, such as a misconfigured access list? The result could be a CLE (Career-Limiting Event).

To prevent this, we connect to the router, instruct it to perform a reload in five or ten minutes, then make the changes to the config. Assuming that all goes well, we save the config, and cancel the reload. If, on the other hand, all does not go well (and we cut ourselves off), the scheduled reload will occur. After the router reboots, it will come up with the old config, allowing us to reconnect and try again.

You can schedule reloads for the future by using the in option. For example, to reload five minutes from now:

  • Router#reload in 5

You can also reload at a certain time and date with the at option. For example, to reload on August 31 at 1:00 am:

  • Router#reload at 1:00 31 august

To display a reload scheduled via the in or at options:

  • Router>show reload (“s rel”)

When there is one minute remaining before the scheduled shutdown, the system will display messages to all active lines (console, aux and vty). The system will also display a message just prior to the reload, but at that point it’s too late to stop the reload from occurring.

To cancel a scheduled reload:

  • Router#reload cancel (“rel can”)

You should see a message confirming that the shutdown was aborted. Make sure that you see this message, because if you mistyped the “cancel” command, the reload clock is still running. Note that you can view a scheduled reload from user mode, but you must be in privileged mode to schedule or cancel a reload.

I realize that every programmer thinks that his or her way of doing things is the best way, but I often wish that they would make a little more effort to be consistent. A case in point is the “Traceroute” command, which exploits the TTL field in the IP header to determine the routers traversed on the way to a specified destination. Like UNIX, the Cisco IOS implementation of “Traceroute” uses UDP with high port numbers, whereas Microsoft’s implementation uses ICMP Echo Requests (“Pings”). The result of this is that a trace from a Cisco machine may make it through firewalls and router access lists, while a trace from a Microsoft machine may not, or vice-versa.

Another difference is that Cisco’s command is traceroute (which can be shortcut as trace or even tr) and Microsoft’s command is tracert, which can’t be shortcut at all. What makes this really annoying is that Cisco’s traceroute (or trace or tr) and the like don’t work on a Microsoft machine, and Microsoft’s tracert doesn’t work on Cisco. This means that if you work in a mixed Cisco/Microsoft environment (as lots of us do), you have to think about which machine you’re on every time you do a trace.

Cisco has given us a way around this, though … the “alias”. What we can do is set up an alias on the Cisco, so that typing the Microsoft tracert command on a Cisco machine will invoke the Cisco traceroute. First, create the alias:

  • Router(config)#alias exec tracert traceroute

Now, whenever the router (or switch) sees the string tracert from an Exec prompt (that is, user or privileged mode), it substitutes the string traceroute in its place. You can now execute the tracert from user or privileged mode:

  • Router>tracert 1.2.3.4

From privileged mode you can also invoke the extended tracert, which like extended ping, will prompt you for additional information. Granted, we’ve just “dumbed-down” Cisco IOS to the Microsoft level with regard to trace, but at least now tracert will work on both platforms. The other option, as mentioned before, is to just use tra on a Cisco and tracert with Windows.

By the way, if you work in a Microsoft environment, don’t forget about the Windows pathping command which is similar to Cisco’s extended trace, but using ICMP echoes, of course. Try this on a Windows machine:

  • C:\WinXP>pathping /?

The alias feature of IOS can be used for other things. For example, if you make frequent use of the show ip ospf neighbor detail command, you might have discovered that you can shortcut it, like this:

  • Router#s ip o n de

Or, you could set up an alias, such as siond, from global config mode:

  • Router(config)#alias exec siond show ip ospf neighbor detail

Now you can use siond (or whatever you set up) in place of the full-blown command, including any options, such as:

  • Router#siond fa0/0

To display what a particular alias represents:

  • Router#siond? (with no space between the alias and the question mark)

To display all existing aliases:

  • Router#s alias

And, of course, to delete an alias, precede it with “no” in global config mode:

  • Router(config)#no alias exec siond show ip ospf neighbor detail

Author: Al Friebe

« Previous Page — Next Page »

Subscribe in a Reader

Subscribe by Email

Follow us on Twitter

Featured Courses

Archives

Cisco Live 2010