Diffusing update algorithm

From Hill2dot0
Jump to: navigation, search

The diffusing update algorithm (DUAL) finite state machine within Cisco's Enhanced Interior Gateway Routing Protocol, embodies the decision process for all route computations. It tracks all routes advertised by all neighbors. The distance information, known as a metric, is used by DUAL to select efficient, loop-free paths. DUAL selects routes to be inserted into a routing table based on feasible successors. A successor is a neighboring router used for packet forwarding that has a least cost path to a destination that is guaranteed not to be part of a routing loop. When there are no feasible successors but there are neighbors advertising the destination, a recomputation of a new successor must occur. The amount of time it takes to recompute the successor affects the convergence time. Even though the recomputation is not processor-intensive, it is advantageous to avoid recomputation if it is not necessary. When a topology change occurs, DUAL tests for feasible successors. If a feasible successor exists, recomputation is avoided.

DUAL Examples

Operational network

Operational Network

To understand the operation of the diffusing update algorithm, let’s examine how it operates in a simple network.

The arrows and numbers indicate the direction and cost to reach network a from routers 3, 4, and 5. Router 3 goes through router 2, router 5 goes through router 4, and router 4 goes through router 2.

Let’s first examine router 4’s and router 5’s successors and feasible successors. From router 4’s perspective its successor is router 2 (the router it goes through to reach network A). It has no feasible successor, which means no other router has a path to network A that is equal to or lower than its cost of 3. From router 5’s perspective its successor is router 4. It has one feasible successor, router 3 (i.e., router 3’s cost to network A is 3—lower than router 4’s cost of 4).

Network failure

Network failure

Let’s examine the operation of the diffusing update algorithm after a failure on the link between router 2 and router 4.

From router 4’s perspective it loses the connection to router 2. Let’s look at what this means for router 4 to reach network A. For network a router 4 has no feasible successors; hence it will send a multicast Query to its neighbors and put network A in what’s called an “active state” (i.e., it’s currently resolving a route to that network). Other networks would also be put in the active state but we will consider network A only. The only neighbor of router 4—router 5—receives the Query.

Router 5 has a feasible successor for network A—router 3—so it changes its successor from router 4 to router 3 and sends a unicast Reply to router 4 indicating that it can reach network A with a cost of 4 (i.e., the sum of the interface costs from router 5 to network A). Router 4 receives the Reply, puts network A in its routing table with a cost of 5, and takes network A out of the active state.

In this example routers 1, 2, and 3 were not involved in the route computation. Router 5 determined a new route to network A without learning the route from its downstream neighbors.

Please note that only a portion of the routing activity in this network has been described. For example, router 2 will do a route computation to reach the network between routers 2 and 4; hence it will also send out a Query to its neighbors.