Whispers & Screams
And Other Things

OSPF DR and BDR Election

Participating routers in an OSPF network have varying roles to play in ensuring that the processes which route the data around the network maintain a true and accurate picture of the network topology. The two primary roles in this structure are the Designated Router (DR) and the Backup Designated Router (BDR). Their roles, whilst primarily aimed at maintaining network function from a routing perspective, are equally focused on ensuring that network bandwidth used to accomplish this is used judiciously.

An Election


Consider a multi-access environment (such as LAN or MAN), where three or more routers are connected together. If all the routers in the OSPF network had to form adjacencies with every other OSPF router present, forming a fully meshed OSPF adjacency network, the resultant conceptualised routing mesh would be overly chatty flooding Link State Advertisements (LSAs) with each and every other OSPF router. As a direct result, router CPU load and network bandwidth would be consumed wastefully. OSPF is designed to be far more efficient in its use of these resources, and, in order to prevent this from happening, OSPF holds an election process to determine and fill roles named Designated Router (DR) and a Backup Designated Router (BDR) so that the workload of propagating routing information around the network is more effectively managed. Election for the DR and BDR is determined primarily on the Router Priority (which by default is 1) and the Router ID. If the value of the router interface priority is changed to 0, it prevents that router from becoming the DR or the BDR.

Router priority can be adjusted on Cisco routers on a per interface basis. The Router ID however is a 32-bit number that uniquely identifies the router in the Autonomous System. One algorithm for Router ID assignment is to choose the largest or smallest IP address assigned to the router. If a router's OSPF Router ID is changed, the router's OSPF software should be restarted before the new Router ID takes effect. Before restarting in order to change its Router ID, the router should flush its self-originated LSAs from the routing domain or they will persist for up to MaxAge minutes. Cisco uses a method that some other vendors choose to follow, but it is not a requirement. If you have a loopback interface, since that's the most stable interface on your router, that will be used. If there is no loopback interface, the highest IP address on the router is used. If there is more than one loopback then the highest of them is used. In many elections in OSPF, the higher RID wins. this is the logic for choosing higher over lower. It should be noted however that you can manually specify an RID that isn't even a valid ip address such as 224.1.1.1.

Drothers


The DR is the router which receives LSAs and other updates when there is a change in the inter-neighbor communications. These LSAs are sent out by the DROTHERS routers (all non-DR/BDR routers), and consequently, any further updates are propagated by the DR to the rest of the DROTHERS routers. The show ip ospf neighbor command, when executed, indicates the non-DR/BDR routers as DROTHERS. Every network segment in OSPF has a DR and a BDR.

The Process


What actually happens is that whenever there is a change in network routing status, instead of flooding each and every path with LSAs advertising new information about network topology, the update is only sent to the DR. The DR then takes on this job and floods the routers in its network segment with the update. If the DR fails or is not functioning, the BDR takes over. When this happens, the BDR replaces the existing DR as the new Designated Router, and a new BDR is elected.

Continue reading
389 Hits
0 Comments

The EIGRP (Enhanced Interior Gateway Routing Protocol) metric

EIGRP (Enhanced Interior Gateway Routing Protocol) is a network protocol that lets routers exchange information more efficiently than was the case with older routing protocols. EIGRP which is a proprietary protocol evolved from IGRP (Interior Gateway Routing Protocol) and routers using either EIGRP and IGRP can interoperate because the metric (criteria used for selecting a route) used with one protocol can be translated into the metrics of the other protocol. It is this metric which we will examine in more detail.

Using EIGRP, a router keeps a copy of its neighbour’s routing tables. If it can’t find a route to a destination in one of these tables, it queries its neighbours for a route and they in turn query their neighbours until a route is found. When a routing table entry changes in one of the routers, it notifies its neighbours of the change. To keep all routers aware of the state of neighbours, each router sends out a periodic “hello” packet. A router from which no “hello” packet has been received in a certain period of time is assumed to be inoperative.

EIGRP uses the Diffusing-Update Algorithm (DUAL) to determine the most efficient (least cost) route to a destination. A DUAL finite state machine contains decision information used by the algorithm to determine the least-cost route (which considers distance and whether a destination path is loop-free).

Figure 1




The Diffusing Update Algorithm (DUAL) is a modification of the way distance-vector routing typically works that allows the router to identify loop free failover paths.  This concept is easier to grasp if you imagine it geographically. Consider the map of the UK midlands shown in Figure1. The numbers show approximate travel distance, in miles. Imagine that you live in Glasgow. From Glasgow, you need to determine the best path to Hull. Imagine that each of Glasgow’s neighbours advertises a path to Hull. Each neighbour advertises its cost (travel distance) to get to Hull. The cost from the neighbour to the destination is called the advertised distance. The cost from Glasgow itself is called the feasible distance.
In this example, Newcastle reports that if Glasgow routed to Hull through Newcastle, the total cost (feasible distance) is 302 miles, and that the remaining cost once the traffic gets to Newcastle is only 141 miles. Table1 shows distances reported from Glasgow to Hull going through each of Glasgow’s neighbours.

Table 1




Glasgow will select the route with the lowest feasible distance which is the path through Newcastle.

If the Glasgow-Newcastle road were to be closed, Glasgow knows it may fail over to Carlisle without creating a loop. Notice that the distance from Carlisle to Hull (211 miles) is less than the distance from Glasgow to Hull (302 miles). Because Carlisle is closer to Hull, routing through Hull does not involve driving to Carlisle and then driving back to Glasgow (as it would for Ayr). Carlisle is a guaranteed loop free path.

The idea that a path through a neighbour is loop free if the neighbour is closer is called the feasibility requirement and can be restated as "using a path where the neighbour's advertised distance is less than our feasible distance will not result in a loop."

The neighbour with the best path is referred to as the successor. Neighbours that meet the feasibility requirement are called feasible successors. In emergencies, EIGRP understands that using feasible successors will not cause a routing loop and instantly switches to the backup paths.

Notice that Ayr is not a feasible successor. Ayr's AD (337) is higher than Newcastle's FD (302). For all we know, driving to Hull through Ayr involves driving from Glasgow to Ayr, then turning around and driving back to Glasgow before continuing on to Hull (in fact, it does). Ayr will still be queried if the best path is lost and no feasible successors are available because potentially there could be a path that way; however, paths that do not
meet the feasibility requirement will not be inserted into the routing table without careful consideration.

EIGRP uses a sophisticated metric that considers bandwidth, load, reliability and delay. That metric is:




[latex]256, *, left(K_1, *, bandwidth ,+, dfrac {K_2 ,*, bandwidth}{256 - load}, +, K_3 ,*, delayright), *,dfrac {K_5}{reliability ,+, K_4}[/latex]


Although this equation looks intimidating, a little work will help you understand the maths and the impact the metric has on route selection.

You first need to understand that EIGRP selects path based on the fastest path. To do that it uses K-values to balance bandwidth and delay. The K-values are constants that are used to adjust the relative contribution of the various parameters to the total metric. In other words, if you wanted delay to be much more relatively important than bandwidth, you might set K3 to a much larger number.

You next need to understand the variables:

    • Bandwidth—Bandwidth is defined as (100 000 000 / slowest link in the path) kbps. Because routing protocols select the lowest metric, inverting the bandwidth (using it as the divisor) makes faster paths have lower costs.

 

    • Load and reliability—Load and reliability are 8-bit calculated values based on the performance of the link. Both are multiplied by a zero K-value, so neither is used.

 

    • Delay—Delay is a constant value on every interface type, and is stored in terms of microseconds. For example, serial links have a delay of 20,000 microseconds and Ethernet lines have a delay of 1000 microseconds. EIGRP uses the sum of all delays along the path, in tens of microseconds.



By default, K1=K3=1 and K2=K4=K5=0. Those who followed the maths will note that when K5=0 the metric is always zero. Because this is not useful, EIGRP simply ignores everything outside the parentheses. Therefore, given the default K-values the equation becomes:




[latex]256, *, left(1, *, bandwidth ,+, dfrac {0 ,*, bandwidth}{256 - load}, +, 1 ,*, delayright), *,dfrac {0}{reliability ,+, 0}[/latex]


Substituting the earlier description of variables, the equation becomes 100,000,000 divided by the chokepoint bandwidth plus the sum of the delays:




[latex]256, *, left(dfrac {10^7}{min(bandwidth)}, +,sum,dfrac {delays}{10}right)[/latex]


As a final note, it is important to remember that routers running EIGRP will not become neighbours unless they share K-values. That said however you really should not change the K-values from the default without a compelling reason.

Continue reading
367 Hits
0 Comments