Section 4.4. Designated Routers


4.4. Designated Routers

Broadcast network media such as Ethernet presents interesting problems for link state protocols, both in terms of database synchronization and SPF calculations. Think of six routers sharing a broadcast link, as in Figure 4.22. If each of the six routers forms an adjacency with each of its neighbors in the link, there will be a total of 15 adjacencies, as shown in the illustration. In fact the number of adjacencies that will be formed under such a scenario, given some number of routers n, is .5(n2n). What this formula tells you is that as the number of routers sharing a broadcast link increases, the number of adjacencies increases exponentially.

Figure 4.22. Under the procedures described so far, all routers sharing a broadcast network will form adjacencies with each other.


The number of adjacencies is usually not a problem by itself. In any sane network design, a large number of routers are not likely to share a single link, and modern routers can maintain a reasonably large number of adjacencies. The real problem is inefficiency. For each adjacency shown in Figure 4.22, the routers at each end must synchronize their databases. You already know that the information must be the same in every link state database within an area, so a single router on the network could provide the database information to all the other routers, as depicted in Figure 4.23. If all routers on the link were to form an adjacency to this one router, the number of synchronizing adjacencies can be reduced from an exponential .5(n2n) to a linear n1.

Figure 4.23. Exchange of redundant information across the broadcast network is reduced if one router is the database synchronization neighbor for all the other routers.


The other problem with the network in Figure 4.22 is how it is represented in SPF calculations, where the shortest path from every node to every other node is determined. If each of the routers (nodes) in Figure 4.22 advertises itself and each of its five adjacencies to the larger network (routers not connected to the broadcast network), a large amount of redundant information is flooded and the SPF calculation becomes unnecessarily complicated.

Instead, the network can be represented as a pseudonode,[4] as shown in Figure 4.24. Rather than each router advertising the attached broadcast network and its adjacent neighbors on the link, a single advertisement can be flooded that specifies the link and lists the nodes attached to the link. The attached routers then advertise just an adjacency to the pseudonode rather than adjacencies to the other attached routers.

[4] Pseudonode is an IS-IS term, and does not appear in OSPF RFCs. But the term is useful and descriptive, so I use it when talking about both IS-IS and OSPF.

Figure 4.24. A pseudonode allows the SPF process to view a broadcast link and its attached nodes as a single node.


Figure 4.25 shows how the pseudonode figures into the SPF calculation. Each of the routers connected to the broadcast network on the left (routers B, C, D, E, F, and G) send their normal link state advertisements, and in these advertisements they show their normal interface cost to the broadcast link. But a link state advertisement is also generated by one router for the pseudonode itself. This link state advertisement has its own ID, which in the example of Figure 4.25 is H. "Node" H indicates that routers B, C, D, E, F, and G are directly connected neighbors, at a cost of 0. The SPF process in all routers then sees H as just another node, and calculates the tree shown in the right side of the illustration.

Figure 4.25. A pseudonode allows the SPF process to view a broadcast link as a node on the SPF tree.


You can see from Figure 4.25 how a pseudonode simplifies the SPF tree. However, although the pseudonode is seen as a node on the tree, it should not be seen as an extra router hopthat is why the pseudonode's link state advertisement shows a cost of 0 to the node's directly connected neighbors. Suppose all routers in Figure 4.25 advertise an interface cost of 1. The route from A to I, then, would be a cost of 3: 1 from A to B, 1 from B to H, 0 from H to F, and 1 from F to I. H is seen as a node but does not effect the physical route costs.

Key to making both the simplified database synchronization and the pseudonode possible is the selection of a designated router. The designated router is one of the routers on the broadcast link to which all other routers on the link synchronize their databases, and the designated router is responsible for originating the link state advertisement that represents the pseudonode. OSPF and IS-IS both use designated routers, although their implementations of the concept vary in significant ways. The remainder of this section examines how the two protocols select and use designated routers.

4.4.1. OSPF Designated Routers

OSPF elects a designated router (DR) on all multi-access links: broadcast and NBMA. The DR forms an adjacency with all other OSPF routers on the network, and the other routers synchronize their LS databases only with the DR. The DR represents the network to the rest of the OSPF area by producing a special LSA called a Network LSA, which is described in detail in Chapter 5 along with the other basic OSPF LSA types.

When routers are synchronizing their databases with the DR over a broadcast link, it would be a waste of bandwidth and interface resources for the DR to produce duplicate Update packets for each and every adjacency. To avoid this inefficiency, multicast addresses are used. The DR sends packets to the other routers on the network using a destination address of 224.0.0.5 (called AllSPFRouters); the other routers communicate with the DR by sending packets to the multicast address 224.0.0.6 (called AllDRouters). By definition, NBMA networks do not support broadcasting and multicasting, so on these networks the DR and its adjacent routers must communicate using unicast on every adjacency. (This sounds like a worse problem than it actually is. In reality, the DR election happens very fast.)

The broadcast or NBMA network represented by the DR is seen by the SPF process and the graph of nodes it derives as a single nodea pseudonode, as described in the previous section. The OSPF pseudonode is represented by the address of the DR's interface attached to the network. This means that if the DR fails, a new DR must be elected, the other routers must synchronize their LS databases to this new DR, and the new DR must advertise its own Network LSA indicating that the pseudonode is now represented by its own interface address. The problem is that until a new DR is elected, adjacencies formed with it and databases resynchronized, and until a new Network LSA is advertised, the network might appear as unreachable to the rest of the OSPF domain.

To minimize the impact of a failed DR, OSPF elects a backup designated router (BDR) in addition to the DR. Routers that are neither the DR nor the BDR (called DROthers in OSPF parlance) form adjacencies with both the DR and the BDR. The DR and BDR are also adjacent, and the BDR synchronizes with the DR just like the DROthers. Figure 4.26 illustrates this relationship. The BDR also listens to the ALLDRouters multicast address on broadcast links. Beyond that, the job of the BDR is like that of a vice president: to read the obituaries. That is, it quietly monitors the DR and if it detects that the DR has failed, it immediately takes over the job. The DROthers are already adjacent with the BDR, and because the BDR has synchronized to the DR just as the DROthers have, everyone should have the same LS databaseresynchronization is not necessary. As a result, recovery from a DR failure should be faster.

Figure 4.26. Both the DR and the BDR have adjacencies to all other routers on a multi-access network, but the routers only synchronize with the DR.


Looking back at the Hello packet in Figure 4.9, notice the Router Priority, Designated Router, and Backup Designated Router fields. These are the specific fields used for the election of DRs and BDRs. Every broadcast and NBMA interface is assigned a priority value, which can be any number between 0 and 255. The value of the priority can be manually specified, and if it is not specified most routers will use some predetermined default value. However, RFC 2328 does not specify what the default should be, so it might vary from implementation to implementation. The default priority of Cisco Systems routers, for example, is 1, whereas the default for Juniper Networks routers is 128. If an interface has an assigned priority value of 0, the router is ineligible to be a DR or BDR on the connected network. The Designated Router and Backup Designated Router fields carry the IP address of the DR and BDR, if they are known. If the addresses of either or both of these routers are not known, the corresponding field is set to 0.0.0.0.

The steps preceding the OSPF DR election process are as follows:

1.

When an OSPF router interface becomes active on a multi-access network, it sets the DR and BDR values in the interface data structure to 0.0.0.0 to indicate that the DR and BDR are unknown. It also starts a wait timer with the value of the interface router dead interval.

2.

The router begins the neighbor-discovery process. It sends Hellos with the DR and BDR fields set to 0.0.0.0.

3.

If the received Hellos indicate an existing DR and BDR, the wait timer is stopped and the DR/BDR advertised in the Hellos is accepted.

4.

If the wait timer expires without a DR being discovered, the DR election process begins.

The steps of the DR election are:

1.

Of all the neighbors on a link with which bidirectional communication has been established, list the neighbors that are eligible to become the DR or BDR (neighbors whose advertised priority is greater than 0). The router includes itself in this list unless its interface priority is 0.

2.

From this list, create a subset of routers that includes all routers except the ones listing their own address in the DR field of their Hellos (thus claiming to be the DR).

3.

Select from the subset all routers who claim to be the BDR by including their own address in the BDR field of their Hellos. From this subset, the router with the highest priority value becomes the BDR. If the priority values are equal, the router with the highest RID becomes the BDR.

4.

If no router in the list claims to be the BDR, the router on the list with the highest priority becomes the BDR. Again, if the priorities are equal, the router with the highest RID becomes the BDR.

5.

From the original list, select all routers claiming to be the DR. Using the same qualifications as are used for selecting the BDR (highest priority value with the highest RID used as a tie breaker), select the DR.

6.

If no router claims to be the DR, the newly elected BDR becomes the DR and Steps 2 through 4 are repeated to elect another BDR.

This procedure is used not only when the network first becomes active, but also when the DR fails. It provides for an orderly promotion from BDR to DR, and also takes into account the rare situation in which a misbehaving router claims to be the DR when it should not.

Most interesting, in light of the complexity of the procedure, is that it is unlikely to be invoked very often. When a new router becomes active on a multi-access link on which a DR and BDR already exist, no election process takes place even if the new router has a higher priority. In other words, existing DRs and BDRs are not preempted. This rule makes the multi-access link more stable by preventing an election process from taking place whenever a new router joins. On the other hand, it means that the OSPF DR election process has little meaning on a stable multi-access network: The first two DR-eligible routers to become active on the link will be the DR and BDR.[5]

[5] This assumes that two or more routers do not become active on a broadcast network within the same wait time. If multiple routers become active in the same wait time (as might happen after a network reboot or link restoration), the election process occurs as described.

4.4.2. IS-IS Designated Intermediate Systems

IS-IS designated routersor, in IS-IS parlance, designated intermediate systems (DIS)serve the same purpose as OSPF DRs. They are elected on all broadcast networks (IS-IS does not recognize NBMA network types), originate a pseudonode LSP to represent the pseudonode, and all other routers sharing the broadcast link synchronize their LS databases with that of the DIS. Although multicast is used for communication between the DIS and other routers on the broadcast network, there is not, as with OSPF, a special multicast address for the DIS. But underlying these functional similarities are some distinct differences in how the functions are performed.

IS-IS DISs differ from OSPF DRs in several significant ways:

  • There is no backup DIS.

  • An IS with a higher priority will preempt the existing DIS.

  • Setting a priority of 0 does not mean the router is ineligible to become the DIS.

  • A full mesh of adjacencies is established on a broadcast network, rather than just with the DIS.

  • On a given broadcast network, separate DISs can exist for L1 and L2 adjacencies.

As with OSPF, IS-IS broadcast interfaces are assigned a priority. You can see in the format of the IS-IS LAN Hello in Figure 4.11 that the Priority field is 7 bits, so the priority value can be any number between 0 and 127. (The default for both Cisco Systems and Juniper Networks routers is 64.) The priority value is set separately for level 1 and level 2, so it is possible for one router to be elected as the level 1 DIS and a different router on the same broadcast network to be elected as the level 2 DIS. If a router's interface is L1 only, then it participates only in the election of an L1 DIS, and likewise if the interface is L2 only, it participates only in the election of the L2 DIS. If the interface is L1/L2, the router participates in both election processes.

When a router runs an L1 DIS election, it includes all neighbors with which it has an L1 adjacency, plus itself. Likewise, when a router runs an L2 DIS election, it considers all neighbors with which it has an L2 adjacency, plus itself. Remember that IS-IS considers two neighbors to be adjacent as soon as bidirectional communication is confirmed, whereas OSPF does not consider neighbors to be fully adjacent until their databases have been synchronized. This accounts for the difference in the prerequisite neighbor states for DIS/DR election.

If a router is attached to a broadcast network but does not find any adjacent neighbors, it does not consider itself the DIS. This eliminates the possibility of a router that can transmit packets but cannot receive themeither because of a network component defect or some network configurationfrom erroneously declaring itself the DIS.

The election process is simple: Select the router within the L1 or L2 set with the highest priority to be the DIS. If the priority values are all the same, select the router whose interface connecting to the network has the numerically highest SNPA (MAC address). Unlike OSPF, a priority of 0 does not eliminate a router from the election process; it only means that the router will not be the DIS as long as another router has a higher priority. It also means that unlike OSPF you cannot accidentally create a situation in which no router on the link is eligible to become DIS.

Another dissimilarity from OSPF is that there is no wait timer and no association with neighbor state changes. An IS-IS router runs this election process every time a LAN Hello is received from an adjacent neighbor and every time it transmits its own LAN Hello as long as there is at least one adjacent neighbor. The need to ensure an orderly transition from the BDR to DR contributes to much of the complexity of the OSPF DR election process. The absence of any sort of "backup" DIS is a major factor in the simplicity of the IS-IS DIS election process, and is a reasonable tradeoff: The election process happens so fast that the benefit of a backup is negligible.

Running the election process whenever a LAN Hello is received means that whenever a Hello is received that has a higher priority than the existing DIS (or higher MAC address if the priority is equal to the DIS priority) the originator of the Hello becomes the DIS. Whenever the DIS is preempted (or resigns by lowering its priority to below that of another router on the link) the new DIS purges the pseudonode LSP generated by the old DIS and originates its own, and all other routers synchronize to the new DIS's LS database. At first look, this might seem to be a source of network instabilitysomething good network engineers constantly strive to minimize. But you can answer that concern yourself. How often is a router likely to be added or removed from a broadcast network shared with other routers? The answer is "once in a while, at the most." Even during transition projects, DIS preemption is not going to have a noticeable impact on network stability.

Point-to-Point Adjacencies over Ethernet

Ethernet interfaces, whether 10M, 100M, 1G, or 10G, are consistently cheaper than other interfaces of equivalent speed. Accordingly, Ethernet is often used as a point-to-point connection between devices in the same equipment room, building, campus, or metro area. When used to connect only two devices, a DR or DIS serves no purpose. Yet because OSPF and IS-IS classify Ethernet interfaces as broadcast by default, one of the two devices is going to be elected as a DR or DIS.

Conscientious network engineers like to keep their networks as simple, efficient, and uncluttered as possible. To us, allowing unnecessary DRs or DISs means unnecessary network traffic, unnecessary information in the link state databases, and unnecessary nodes on the SPF tree. If nothing else, it offends our sense of network aesthetics. Although some might argue that this is fastidiousness run amok, when you manage a very large network you find yourself constantly on the lookout for inefficiencies. And some large networks can have hundreds or even thousands of point-to-point Ethernet links. To add to the complexity, some Ethernet links carry Virtual LAN (VLAN) logical links. If OSPF or IS-IS is run over these links, DR/DIS functions can again contribute to undesirable complexity.

Some router vendors provide you with the option of changing the Ethernet interface network type for OSPF or IS-IS or both from its default broadcast to point-to-point. In addition to making the overall network simple and hence more manageable, configuring point-to-point Ethernet links to the OSPF or IS-IS point-to-point network type enables the use of IP unnumbered for address conservation.





OSPF and IS-IS(c) Choosing an IGP for Large-Scale Networks
OSPF and IS-IS: Choosing an IGP for Large-Scale Networks: Choosing an IGP for Large-Scale Networks
ISBN: 0321168798
EAN: 2147483647
Year: 2006
Pages: 111
Authors: Jeff Doyle

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net