The Dijkstra Algorithm

Before you continue, you should review the Dijkstra algorithm. Figure 10-3 shows the network setup for which SPF is to be executed. Also, study the following network tables to understand how the router calculates the shortest path to the destination. All the associated costs for the interfaces are listed. Costs for exiting the interface are always considered.

Figure 10-3. Network Setup for which SPF Is to Be Executed

To begin the process, each router considers three lists:

When the process is initiated or a new LSP is introduced

• Tentative list

The LSP being considered for inclusion into the path list

The LSP for which the best path to the destination is computed

Assume, for example, that router A is the source point. Calculate its shortest path to each destination within the network; at the beginning of the process, each router is in the unknown list. Router A places itself on the tentative list.

Router and its neighbors list: A, B, C, D, E, F, G, H

Route stands for router

Router A

Router B

Router C

Router D

B

4

A

4

A

3

B

2

C

3

D

2

D

2

C

3

H

2

F

3

Router E

Router F

Router G

Router H

C

1

E

2

F

5

G

3

F

2

G

1

H

3

F

1

H

1

D

2

The SPF computation is an iterative process. There is one iteration per node in the network. Each iteration involves following these steps:

Examine the tentative list. Move the node with the shortest path from the tentative list to the path list.

Locate that node's LSP in the link-state database, and then search it at the node's neighbors. Move those neighbors from the unknown list to the tentative list. If those nodes are already on the path list, skip them. If those nodes are already on the tentative list, see if the cost of the new path is better than the previous one.

The cost for the new node on the tentative list is the cost to reach the parent, which is the node we just moved to the path list, in addition to the cost from the parent to the new node on the tentative list. We can locate the cost in the LSP. If the new node on the tentative list is only one hop away from the source, search for the outgoing interface in the adjacency table. If the new node is further away from the source, copy the first-hop information from the parent.

When there are no more nodes on the tentative list, the computation is finished.

The information to retain for each node is the routerID/systemID of the node, the cost of reaching it, and the outgoing interfaces to reach it.

Then, you are ready to perform the computation. Router A is the only node on the tentative list. It moves itself from the tentative list to the path list. Router A moves B and C to the tentative list. Router B has a cost of 4 (0 + 4) and Router C has a cost of 3 (0 + 3). Study the adjacency table to determine the outgoing interfaces. That concludes the first iteration. When you begin the second iteration, look in the tentative list for the node with the shortest path (Router C). Router C is placed on the path list first because it is at a shorter distance. Router A places the neighbors of Router C (Routers D and E) on the tentative list. The cost to Router D is 5 (3 + 2). The cost to E is 5 (3 + 1). The first-hop interface is the same as the outgoing interface to reach Router C.

Current path list for router A: B , C

Router A

B

4

Now, with routers B and C moving to the path list, routers D and E can move to the tentative list:

Distance from B to D is 2 Distance from C to D is 2

Routers B and C are of equal cost, but the distance to C via A is smaller. Similarly, router E is not known via B, but it is known via C at a distance of 1. Router A now installs router E and router D in the path list and their neighbors in the tentative list, so H and F are now in the tentative list.

New table for A with E and D in path list

Router A

B

4

C

3

D

5

E

4

The cost from D to F is 3, the cost from D to H is 2, and the cost from E to F is 2. According to the table, D is already at a cost of 5 and is giving a higher cost to F. Router E is at a cost of 4 and is advertising a lower cost of 2. H is learned only via D.

Now F and H are moved from the tentative list to the path list:

Router A

B

4

C

3

D

5

E

4

F

6

H

7

Now with F moving into the path list, the distance from F to H is smaller than via D. The cost to H is 7. With both F and H in the path list, G is placed in the tentative list. The cost is calculated from both H and F to G. Finally, all the destinations are resolved and the final table will resemble the following:

Router A

B

4

C

3

D

5

E

4

F

6

H

7

G

10

After all the destinations are computed, the router installs routes in the table if the route has passed all the required conditions. According to the 10589 requirement, when a router receives a new LSP, it waits five seconds before running SPF; it waits 10 seconds before running two consecutive SPFs within the same area. For this reason, if the router is both a level 1 and a level 2 router, it must run to multiple SPFs.

After the SPF runs, the best route is installed in the table. An internal list of backup routes is saved, in case a prefix is lost to a destination. If this happens, the router reviews the backup list, and runs a partial SPF to find the next best optimal path to the destination. A complete SPF algorithm is executed only if an LSP with a different neighbor list is received.

Using IS-IS Pseudonode

Instead of treating a broadcast network as a fully connected topology, IS-IS treats a broadcast network as a pseudonode with links to each attached system.

NOTE

To reduce the number of full mesh adjacencies between nodes, multiaccess links are modeled as pseudonodes. As the name implies, this is a virtual node. One of the ISs on the link is designated to be the pseudonode; this node is called the designated intermediate system (DIS). All routers on the broadcast link, including the one elected to be DIS, form adjacencies with the pseudonode instead of forming n (n-1) adjacencies with each other in a full mesh.

The DIS is responsible for generating pseudonode link-state packets, for reporting links to all systems on the broadcast subnetwork, and for carrying out flooding over the LAN. A separate DIS is elected for level 1 and level 2 routing.

All routers attached to the broadcast network must report their links to the pseudonode. Each pseudonode has a DIS. Figure 10-4 shows the physical and logical views of the pseudonode.

Figure 10-4. The Physical and Logical Views of the Pseudonode iW fH

Was this article helpful?

0 0

Post a comment