The DUAL Finite State Machine

When an EIGRP router is performing no diffusing computations, each route is in the passive state. Referring to any of the topology tables in the previous section, a key to the left of each route indicates a passive state.

A router will reassess its list of feasible successors for a route, as described in the last section, any time an input event occurs. An input event can be:

• A change in the cost of a directly connected link

• A change in the state (up or down) of a directly connected link

• The reception of an update packet

• The reception of a query packet

• The reception of a reply packet

The first step in its reassessment is a local computation in which the distance to the destination is recalculated for all feasible successors. The possible results are:

• If the feasible successor with the lowest distance is different from the existing successor, the feasible successor will become the successor.

• If the new distance is lower than the FD, the FD will be updated.

• If the new distance is different from the existing distance, updates will be sent to all neighbors.

While the router is performing a local computation, the route remains in the passive state. If a feasible successor is found, an update is sent to all neighbors and no state change occurs.

If a feasible successor cannot be found in the topology table, the router will begin a diffusing computation and the route will change to the active state.Until the diffusing computation is completed and the route transitions back to the passive state, the router cannot:

• Change the route's successor

• Change the distance it is advertising for the route

• Begin another diffusing computation for the route

A router begins a diffusing computation by sending queries to all of its neighbors (Figure 8.10). The query will contain the new locally calculated distance to the destination. Each neighbor, upon receipt of the query, will perform its own local computation:

Figure 8.10. A diffusing computation grows as queries are sent and shrinks as replies are received.

Figure 8.10. A diffusing computation grows as queries are sent and shrinks as replies are received.

• If the neighbor has one or more feasible successors for the destination, it will send a reply to the originating router. The reply will contain that neighbor's minimum locally calculated distance to the destination.

• If the neighbor does not have a feasible successor, it too will change the route to the active state and will begin a diffusing computation.

For each neighbor to which a query is sent, the router will set a reply status flag(r) to keep track of all outstanding queries. The diffusing computation is complete when the router has received a reply to every query sent to every neighbor.

In some cases, a router does not receive a reply to every query sent. For example, this may happen in large networks with many low-bandwidth or low-quality links. At the beginning of the diffusing computation, an Active timer is set for 3 minutes.191 If all expected replies are not received before the Active time expires, the route is declared stuck-in-active(SIA). The neighbor or neighbors that did not reply will be removed from the neighbor table, and the diffusing computation will consider the neighbor to have responded with an infinite metric.

191 The default Active timer is 1 minute in some earlier IOS versions.

The default 3-minute Active time can be changed or disabled with the command timers active-time. The deletion of a neighbor because of a lost query obviously can have disruptive results, and SIAs should never occur in a stable, well-designed internetwork. The troubleshooting section of this chapter discusses SIAs in more detail.

At the completion of the diffusing computation, the originating router will set FD to infinity to ensure that any neighbor replying with a finite distance to the destination will meet the FC and become a feasible successor. For each of these replies, a metric is calculated based on the distance advertised in the reply plus the cost of the link to the neighbor who sent the reply. A successor is selected based on the lowest metric, and FD is set to this metric. Any feasible successors that do not satisfy the FC for this new FD will be removed from the topology table. Note that a successor is not chosen until all replies have been received.

Since there are multiple types of input events that can cause a route to change state, some of which may occur while a route is active, DUAL defines multiple active states. A query origin flag (O) is used to indicate the current state. Figure 8.11 and Table 8.1 show the complete DUAL finite state machine.

Figure 8.11. The DUALfinite state machine. The query origin flag(o) marks the current state of the diffusing calculation. See table 8.1 for a description of each input event(IE).

Figure 8.11. The DUALfinite state machine. The query origin flag(o) marks the current state of the diffusing calculation. See table 8.1 for a description of each input event(IE).

Table 8.1. Input events for the DUAL finite state machine.

Input Event

Description

IE1

Any input event for which FC is satisfied or the destination is unreachable

IE2

Query received from the successor; FC not satisfied

IE3

Input event other than a query from the successor; FC not satisfied

IE4

Input event other than last reply or a query from the successor

IE5

Input event other than last reply, a query from the successor, or an increase in distance to destination

IE6

Input event other than last reply

IE7

Input event other than last reply or increase in distance to destination

IE8

Increase in distance to destination

IE9

Last reply received; FC not met with current FD

IE10

Query received from the successor

IE11

Last reply received; FC met with current FD

IE12

Last reply received; set FD to infinity

Two examples will help clarify the DUAL process. Figure 8.12 shows the example network, focusing only on each router's path to subnet 10.1.7.0; refer to Figure 8.3 for specific addresses. On the data links, an arrow indicates the successor each router is using to reach 10.1.7.0. In parentheses are each router's locally calculated distance to the subnet, the router's FD, the reply status flag (r), and the query origin flag (O), respectively. Active routers are indicated with a circle.

Figure 8.12. All routes to subnet 10.1.7.0 are in the passive state, indicated by r = 0 and O = 1.

Ultenlhal Csyley

Figure 8.12. All routes to subnet 10.1.7.0 are in the passive state, indicated by r = 0 and O = 1.

Ultenlhal Csyley

0 0

Post a comment