Routing

You are currently browsing articles tagged Routing.

Ran into something interesting the other day and the response I got from TAC was even more interesting.  We had a 6500 that had multiple equal cost paths out of a few different interfaces.  The switch was basically being used as a distribution switch with multiple WAN routers plugged into it.  Many of the prefixes were equal cost from the switches perspective so I expected CEF to do the default of per destination (really source/destination) load balancing.  The switch appeared to do that correctly, but not in the manner that I expected it would…

Here’s what the lab topology looks like that I was using…

image

Let’s assume that each of the 4 routers has a equal cost path to get to 4.2.2.2.  The 6500 sees equal cost routes for that /32 through each of the four routers…

image

At this point, let’s say that I want to determine the particular path that a packet would take towards 4.2.2.2.  How would I do that?  Easy, all CEF enabled devices (all that I can think of anyways) have the command…

show ip cef exact-route <source IP> <destination IP>

If you are doing per destination CEF load sharing, than this command should tell you the exact next hop and interface that the switch will use to forward the packet.  Let’s do an example to see…

image

Here you can see that I’m checking the path that a packet will take from the client (10.0.0.21) to the destination of 4.2.2.2.  CEF says that the packet will take the path out of interface Gig2/3 to the next hop of 10.0.0.9. 

Pretty slick huh?  Let’s send some packets from the client and see what happens…

image

After pinging 4.2.2.2 for 30 second the statistics on the Gig2/3 interface only show a single packet being output while the client is receiving valid echo-replies to the pings.  How can this be?

I opened a TAC case and while I didn’t get a documented answer on what I was seeing, it appears that I was using the wrong command.  I should have been using the…

show mls cef exact-route <source IP> <destination IP>

When that command is run, I get this output…

image

And sure enough, if I look at the Gig2/4 interface I see my pings…

image

The answer I got from Cisco was that the ‘show ip’ version of the command looks at the control plane or MSFC for the lookup.  The ‘show cef’ version of the command looks at the hardware forwarding table or PFC for the lookup. 

This makes it pretty clear that the control plane of the switch has different forwarding logic than the data plane which I find sort of scary.  Apparently one of the forwarding tables uses an additional piece of information to determine the path.  This extra piece of information is called the UID.  Here’s what Cisco has to say about the UID…

Cisco IOS introduced a concept called unique-ID/universal-ID which helps avoid CEF polarization. This algorithm, called the universal algorithm (the default in current Cisco IOS versions), adds a 32-bit router-specific value to the hash function (called the universal ID – this is a randomly generated value at the time of the switch boot up that can can be manually controlled). This seeds the hash function on each router with a unique ID, which ensures that the same source/destination pair hash into a different value on different routers along the path. This process provides a better network-wide load-sharing and circumvents the polarization issue. This unique -ID concept does not work for an even number of equal-cost paths due to a hardware limitation, but it works perfectly for an odd number of equal-cost paths. In order to overcome this problem, Cisco IOS adds one link to the hardware adjacency table when there is an even number of equal-cost paths in order to make the system believe that there is an odd number of equal-cost links.

So apparently that UID is what’s causing the what I’m seeing but it’s unclear which forwarding table is using it.  I’m betting that it’s being used on the hardware forwarding side of things but that’s only a guess.  Since the control plane should be programming the data plane the whole concept of them being different seems odd to me. 

Just something to keep in mind.  If you want to see how the packet would be forwarded by the SUP (in software) use the ‘show ip’ version of the command.  If you want to see how it would be forwarded in hardware use the ‘show mls’ version of the command.

Tags: ,

EIGRP – Part 1

EIGRP is my favorite IGP (don’t hate me just yet, I have a good reason).  I’ll elaborate more on that comment later, but for now, let’s jump right into a topology so we can start playing with EIGRP…

image

In my lab, I’m using 1841 routers and since they only have two Ethernet interfaces, I’m going to be utilizing sub interfaces in this example.  The initial config involves configuring the interfaces on each router and ends with each router being able to ping it’s directly connected neighbor. I’m not going to run through that config since it’s pretty straight forward.

The bottom router (Router5) has a 10.64.32.0 /24 network behind it which we want to be reachable by all the routers.  The top switch (Switch1) has the 0’s route behind it which we also want to be reachable by all of the routers.  Let’s put a base configuration on each router to get EIGRP up and running and see what it does.  The base configuration will look like this…

<DEVICE>#config t
Enter configuration commands, one per line.  End with CNTL/Z.
<DEVICE>(config)#
router eigrp 1
<DEVICE>(config-router)#network <Physical Interface IP> 0.0.0.0
REPEAT ABOVE COMMAND FOR EACH INTERFACE
<DEVICE>(config-router)#
end
<DEVICE>#

So for instance, the switch configuration would look like this…

image

Once, that’s done on all of the routers, let’s look at the routing table on router5…

image

You’ll note that we have two routes that have dual paths to the destination prefix.  Those are the 10.0.0.8/30 prefix as well as the 10.0.0.0/29 prefix.  Looking at the topology again, this makes sense since the paths to each of those prefixes from router 5 would truly be equal cost. 

No other real surprises here.  The rest of the /30’s are listed in the routing table as we would expect since all of the routers successfully joined EIGRP.  Let’s talk a quick second to talk about route selection.  As you know (or should know, read this if you don’t) EIGRP has an admin distance of 90.  Any route to the same destination with a higher admin distance will get squashed by the EIGRP route.  The admin distance of 90 is for what are called ‘internal’ EIGRP routes.  There are also ‘external’ EIGRP routes that have an admin distance of 170.  External EIGRP routes would be routes leaked into a EIGRP AS from a different EIGRP AS through route distribution.

However, what we don’t know is how EIGRP decides which route it is going to pick to get to each prefix.  For instance, we see above that to get to 10.0.0.8/30 router5 had two paths to the destination.  That’s because these two paths are equal cost so EIGRP can safely insert them both into the FIB and let CEF handle the load balancing between the two next hops.  However, since router5 is dual homed, it does have two paths to get to each and everyone of the other prefixes as well.  So where are those?

Before we go too far down the rabbit hole, let’s define some EIGRP terminology that should help us stay on track…

Adjacency
The goal of every EIGRP router is to form an adjacency with a neighboring EIGRP router.  Once this adjacency has been formed, the router will receives EIGRP updates from it’s peer router.  The updates can then be processed ,along with the metric to get to the peering router, to determine a distance to the prefix learned in the advertisement.

Feasible Distance (FD)
Of all of the paths learned to each given prefix, one will be picked as the ‘best’ path.  This metric associated with this best path is known as the ‘feasible distance’.  Basically, the router just picks the lowest cost path and makes that the FD. 

Advertised Distance (AD)
The advertised distance is the metric from the neighbor advertising the prefix, to the prefix.  That is, the feasible distance minus the cost to get to the neighbor you heard the advertisement from. 

Feasibility Condition (FC)
The feasibility condition states that a route may become a feasible successor route if the advertised distance is less than the feasible distance. 

Successor
A successor is the best route to a prefix

Feasible Successor
A feasible successor is a route that matches the feasibility condition and can be used as a backup route. 

Unfortunately, we need to go a little but further down the rabbit hole to fully understand EIGRP. To do that, we need to understand the metric that EIGRP uses. The metric itself is rather complicated, but if you assume the use of default values, one can size the formula down to this…

image

Let’s take a look at our example to clarify things.  So here is the output of the EIGRP topology table on router5…

image

Using that formula, let’s make sure we understand where the metric are coming from that EIGRP is reporting.  For instance, let’s examine the prefix 10.0.0.0 /29.  Note that the EIGRP topology table is showing 2 successors for the prefix, with two next hops that have matching metrics.  If the metrics weren’t a dead match for each other, we wouldn’t have 2 successors (in most cases, more on that later).  The topology table is reporting a feasible distance of 33280 and a advertised distance of 30720 for both paths to that prefix.  Let’s break down the math to see where that comes from.

Recall, we really only need to come up with two variables to solve the equation, the minimum bandwidth along the entire path and the sum of all interface delays.  Our lab topology currently uses fast Ethernet interfaces with the default delay and speed configuration, so the path looks something like this…

 image

The information on the delay as well as the interface speed can be shown using the ‘show interface <interface>’ command.  Here we see the speed and delay of an interface on router5…

image

Note: The delay can be statically set on an interface (we’ll do that later).  However, when you set the delay you are setting it in ‘tens of microseconds’ which are not the same as the usec metric.  If you set the delay to 50 on an interface, it will be 500 usec.  It’s good practice to verify what was set with the show interface command to make sure it’s what you think you configured. 

So, we can see here the the minimum bandwidth is 100 meg (100000 Kb) on any of the given links.  So there is out first variable, our second variable is the sum of the interface delays which we can see would equal 300 usecs.  Plug those into the formula…

image 

and we get a metric of 33280.  So that’s our feasible distance, how about our advertised distance?  Recall that the advertised distance is the metric a router hears advertised by it’s neighbor not including the cost to get to the neighbor.  In this case, that would mean that we’d just remove the delay of router5’s interface and run the equation again…

image

Which gives us an advertised distance of 30720 like we saw in the output above. 

Now, let’s look at a prefix that only has one entry in the topology table.  For instance, let’s look at the prefix 10.0.0.12 /30.  The EIGRP topology table shows only one path to that prefix…

image

And why is that? The answer is simple, all other paths must fail the feasibility condition.  Let’s look at the other paths to prove this…

image 
The path highlighted in orange is obviously the shortest path to the prefix, but let’s look at the purple path to prove why it can’t be a feasible successor.   The metric for the orange path is 30720 which is the prefixes feasible distance.  Let’s compute the metric for the purple path.  The minimum bandwidth on that path is 100000 Kbps but the delay is 400 usec.  That would gives us a metric of 35840 for the purple path.  The feasibility condition states that a route may become a feasible successor route if the advertised distance is less than the feasible distance. Since 35840 is not less than 30720, the route is not a feasible successor to the existing successor.  Let’s shut down the link between router3 and router5 to prove that our metric calculation was valid…

image

I show the use of a very handy command here.  The ‘show ip eigrp topology <prefix>’ command is very handy in determining the metric and the means in which it was calculated.  As you can see, we started wit the FD of 30720 (orange path) and after shutting down the interface, we came up with a FD of 35480 (purple path). 

Hopefully, at this point, EIGRP is starting to make a little more sense to you.  To mix things up a bit (and show us some other features) let’s manipulate some of the interfaces to change things up a little bit…

image 
Notice that we’ve manipulated the delay on the links between router1, router3, and router5.  A look at the topology table on router5 now shows us…

 image

2 prefixes to the 10.0.0.12 /30 subnet.  Let’s do the math on each of these to figure out how this happened. 

The Orange Path Feasible Distance
image 

The Purple Path Feasible Distance
image 

The winner in this case turns out to be the purple path since it has a lower metric.  However, the advertised distance of the orange path turns out to be 281600 which happens to be less than the feasible distance of the purple path.  When this happens the route becomes a feasible successor.  The output of the topology table confirms this for us…

image

Taking a close look at the topology table, we can tell that we are dealing with a feasible successor…

image

Note that the table says it has 1 successor, but there are two entries.  Only the first entry will show up in the forwarding table of the router…

image

Since there is a second entry, we know that EIGRP is using the second route as a feasible successor.  If EIGRP is going to insert both routes into the routers routing table, it will tell you that you have 2 successors as we saw above with the 10.0.0.0 /29 prefix…

Topology Table
 image

Router’s routing Table
image

I think that’s enough for now.  There are a few more aspects of EIGRP I’d like to cover in my next post but I think this is enough to get started.  Look for post 2 coming up next!

Tags: , , ,

The logical next step from static routing is dynamic routing.  When we talk about dynamic routing, we classify the routing protocols into two main groups. 

Distance Vector
The distance vector protocols are said to advertise ‘vectors’ of information.  That is, a distance and direction.  In IP terms, that would be a metric and an interface.  The distance vector protocols (relevant for the CCIE) include RIP and EIGRP.  Distance vector protocols are often considered to be ‘routing by rumor’.  A neighboring router sends a router some information and says “You can get here by coming to me and it’s this far away”.

Link State
Link state protocols are a little bit different than distance vector.  Link state protocols hear updates for all router’s participating in the same routing protocol instance.  That is, each router generates it’s updates as well as forwards updates that it hears from other routers.  In this manner, each router knows about the entire routing topology rather than only what it hears from it’s directly connected neighbors.  Routers running a link state protocol are able to map the entire network, then run their own calculations to determine the best path to each network.  Examples of link state protocols include OSPF and IS-IS. 

There are more nuances to each type of routing protocol but I think it’s best to flush those out as we examine each.  The major differences between distance vector protocols and link state protocol are important to remember. 

Tags: ,

« Older entries