Case Study Developing the Link State Database

Earlier in this chapter, you learned how LSAs were used to send information about the links between OSPF routers. These LSAs are stored in the router in a database with each LSA as a record in that database.

Figure 2-16 shows the OSPF network topology for this case study.

Figure 2-16 OSPF Network Topology for Link-State Database Case Study

OSPF Area 30 30.30.30.X/24

.102

192.168.254.X/24

fa0/0

.100

fa0/0

fa0/1

OSPF Area 10 10.10.10.x/24

OSPF Area 20 20.20.20.X/24

Example 2-6 shows entries generated by the show ip ospf database command from the router HAL9000.

Example 2-6 Viewing the LSA Database for the HAL9000 Router

HAL9000#show ip

ospf database

OSPF

Router with ID (192.168.254.

253)

(Process ID 100)

Router Link-states (Area

0)

Link ID

ADV Router Age

Seq#

Checksum

Link count

192.168.

254

100

192.168.254.100 649

0x80000003

0x75C

1

192.168.

254

101

192.168.254.101 651

0x80000003

0x55B

1

192.168.

254

102

192.168.254.102 582

0x8000000A

0xF461

1

192.168.

254

253

192.168.254.253 1486 Net Link-states (Area 0)

0x80000051

0xD669

1

Link ID

ADV Router Age

Seq#

Checksum

192.168.

254

253

192.168.254.253 1346

0x80000006

0x355B

Summary Net Link-states

(Area 0)

Link ID

ADV Router Age

Seq#

Checksum

10.10.10

.0

192.168.254.102 648

0x80000002

0xBC91

20.20.20.0

192.168.254.100 1312

0x80000001

0x61D1

30.30.30.0

192.168.254.101 651

0x80000002

0xEF23

HAL9000#

Notice how the output here shows no information on the other areas in Figure 2-16. This is because the HAL9000 router is a backbone router and has no other interfaces in areas other than area 0. Contrast the output in Example 2-6 for the HAL9000 router with the output generated from the same command on the Tokyo router in Example 2-7.

90 Chapter 2: Introduction to OSPF

Example 2-7 Viewing the LSA Database for the Tokyo Router

Tokyo#show ip ospf database

OSPF

Router with ID

(192.168.254.

101

(Process ID 100)

Router Link

-states (Area

0)

Link ID

ADV

Router

Age

Seq#

Checksum

Link

count

192.168.

254

100

192

168.254

100 903

0x80000003

0x75C

1

192.168.

254

101

192

168.254

101 903

0x80000003

0x55B

1

192.168.

254

102

192

168.254

102 836

0x8000000A

0xF461

1

192.168.

254

253

192

168.254

253 1740

0x80000051

0xD669

1

Net

Link-states (Area 0)

Link ID

ADV

Router

Age

Seq#

Checksum

192.168.

254

253

192

168.254

253 1601

0x80000006

0x355B

Summary Net

Link-states

(Area 0)

Link ID

ADV

Router

Age

Seq#

Checksum

10.10.1C

.0

192

168.254

102 902

0x80000002

0xBC91

20.20.20.0

192

168.254

100 1567

0x80000001

0x61D1

30.30.30.0

192

168.254

101 904

0x80000002

0xEF23

Router Link

-states (Area

30)

Link ID

ADV

Router

Age

Seq#

Checksum

Link

count

192.168.

254

101

192

168.254

101 904

0x80000002

0xCC6D

1

Summary Net

Link-states

(Area 30)

Link ID

ADV

Router

Age

Seq#

Checksum

10.10.10

.0

192

168.254

101 826

0x80000005

0xC684

20.20.20.0

192

168.254

101 1566

0x80000001

0x65CB

192.168.

254

0

192

168.254

101 1421

0x80000007

0x7B84

Tokyo#

In many cases, people use the term topological database to describe the link-state database. That is technically incorrect because RFC 2328 on OSPF v2 refers to the table as the linkstate database.

Each of these entries in Example 2-7 has a meaning in the LSA as defined in the following list:

• Heading and introduction—Cisco routers present you with a good bit of information about what you are viewing prior to giving you the LSA entries. The first part tells you what the RID is for, what router you have executed the command on, and what OSPF routing process this database is for. Cisco routers can run multiple and separate instances of OSPF.

• Area information—If you recall, a router like an ABR maintains a separate link-state database (LSDB) for each OSPF area. This part of the example reveals the type of LSA and for which OSPF area the LSDB relates:

• ADV router—Identifies the advertising router by its RID that originated the LSA.

• Seq#—Sequence number of the LSA and is included within the LSA and the database to prevent old or duplicate information.

• Checksum—Ensures that the LSA checks out.

• Link count—Number of interfaces that OSPF is running on for the router that transmitted the LSA. This field is present only in a Type 1 router LSA.

Figure 2-17 shows a network with eight routers, all running OSPF and with several of the interfaces associated with different costs (indicated by thicker lines for easy reference).

Figure 2-17 Sample OSPF Network

OSPF Area 0

= 10-Mbps Links = 100-Mbps Links

When viewing this network, note that cost is placed on a link per outgoing interface. For example, for RtrA, it would cost 4 to go directly to RtrE in the center of the network. However, if you were in RtrE, it would cost 5 to go directly to RtrA. Therefore, cost is considered to be interface-based and is applied in an outgoing direction.

With the given network, OSPF develops a link-state database based on the topology shown in Figure 2-17. In this network, it is assumed that all the routers belong to a single OSPF area, so each router has an identical copy of the database and no other. This example uses area 0.

NOTE To make the table more legible, the names of the routers in Figure 2-17 have been abbreviated as RA for RtrA, RB for RtrB, and so on.

92 Chapter 2: Introduction to OSPF

Table 2-4 shows the link-state database for each router in the OSPF network in Figure 2-17. This table consists of several parts, each of which represents the contents of the link-state database for each of the routers in Figure 2-17. The Router ID column identifies each of the routers. The layout of the link-state database is a result of OSPF building the link-state database with itself as the root of the tree. The next column, Neighbor, contains all the other routers to which the root router is directly connected (that is, its neighbors). The third and final column indicates the cost for the root router to reach its neighbor.

For example, consider Router A (RA). It has three neighbors: B, D, and E. The cost to reach B is 2, the cost to reach E is 4, and so on.

Table 2-4 Link-State Database by Router for the OSPF Network

Router ID

Neighbor

Cost

RA

RB

2

RA

RD

4

RA

RE

4

RB

RA

2

RB

RC

1

RB

RE

10

RC

RB

5

RC

RF

2

RD

RA

4

RD

RE

3

RD

RG

5

RE

RA

5

RE

RB

2

RE

RD

3

RE

RF

2

RE

RG

1

RE

RH

8

RF

RC

2

RF

RE

2

RF

RH

4

RG

RE

1

RH

RE

8

RH

RF

6

At this point, the network is not nearly converged. The next step is to go through that entire process. Dijkstra's algorithm was adapted for use when routers are running the SPF algorithm. This process starts with the router having already created a link-state database, as shown in Table 2-4. The process is described in the following steps:

1 A router begins the process of creating the SPF tree database by adding itself as the root of the SPF tree (recall Figure 2-6). When the router starts as the root, it enters itself as its own neighbor, with a cost of 0.

2 All entries in the link-state database that describe links to the root router's neighbors are added to the candidate database.

NOTE A candidate database is a working database that OSPF creates during this process to expedite the calculation of the SPF tree entries from which the router derives the routing table.

The cost from the root router to each link in the candidate database is calculated. The link in the candidate database with the lowest cost is moved to the tree database. If two or more links are an equally low cost from the root, choose one.

NOTE The tree database is the output of the root router running the SPF algorithm on the candidate database. When the algorithm is completed, the tree database contains the shortest path.

4 The neighbor RID of the link that was just added to the tree database is examined. With the exception of any entries whose neighbor ID is already in the tree database, information in the link-state database describing that router's neighbors is added to the candidate database.

5 If entries remain in the candidate database, return to Step 3. If the candidate database is empty, the SPF algorithm is stopped. The SPF calculations are finished and successful when a single neighbor ID entry is in the tree database that represents every router in the OSPF area.

Table 2-5 summarizes the process and results of applying Dijkstra's algorithm to build a shortest-path tree for the network in Figure 2-17.

In Table 2-5, the columns each represent various processes on how the network converges. The first column represents the potential candidate entries into the link-state database; after the calculations, these entries are entered into the tree database. The Description column explains the events that are occurring.

94 Chapter 2: Introduction to OSPF

Table 2-5 SPF Algorithm Applied to the Database of Table 2-4

Candidate Entries

Database

Description

-

-

RA,RA,0

RA adds itself to the SPF tree as root.

RA,RB,2 RA,RD,4 RARE,4

2 4 4

RA,RA,0

The links and their costs to all of RA's neighbors are added to the candidate list.

RA,RD,4 RA,RE,4 RB,RC,1 RB,RE,10 RD, RE, 7

4 4 3

RA,RA,0 RA,RB,2

(RA,RB,2) is the lowest-cost link on the candidate list, so it is added to the tree. All of RB's neighbors, except those already in the tree, are added to the candidate list. Note that there are three paths to RE. (RA,RE,4) is a lower-cost link to RE than (RB,RE,10) or (RD,RE,7), so the last two links are dropped from the candidate list.

RA,RD,4 RA,RE,4 RC,RF,2

4 4 5

RA,RA,0 RA,RB,2 RB,RC,1

(RB,RC,1) is the lowest-cost link on the candidate list, so it is added to the tree. All of RC's neighbors, except those already on the tree, become candidates.

RA,RE,4 RC,RF,2 RD,RE,3 RD,RG,5

4 5 7 9

RA,RA,0 RA,RB,2 RB,RC,1 RA,RD,4

(RA,RD,4) and (RA,RE,4) are both a cost of 4 from RA; (RC,RF,2) is a cost of 5. (RA,RD,4) is added to the tree, and its neighbors become candidates. Two paths to RE are on the candidate list; (RD,RE,3) is a higher cost from RA and is dropped.

RC,RF,2

RD,RG,5

RE,RF,2

RE,RG,1

RE,RH,8

5 9 6 5 12

RA,RA,0 RA,RB,2 RB,RC,1 RA,RD,4 RA,RE,4

(RF,RE,1) is added to the tree. All of RE's neighbors not already on the tree are added to the candidate list. The higher-cost link to RG is dropped.

RE,RF,2 RE,RG,1 RE,RH,8 RF,RH,4

6 5 12 9

RA,RA,0 RA,RB,2 RB,RC,1 RA,RD,4 RA,RE,4 RC,RF,2

(RC,RF,2) is added to the tree, and its neighbors are added to the candidate list. (RE,RG,1) could have been selected instead because it has the same cost (5) from RA. The higher-cost path to RH is dropped.

RF,RH,4

RA,RA,0 RA,RB,2 RB,RC,1 RA,RD,4 RA,RE,4 RC,RF,2 RE,RG,1

(RE,RG,1) is added to the tree. RG has no neighbors that are not already on the tree, so nothing is added to the candidate list.

RA,RA,0 RA,RB,2 RB,RC,1 RA,RD,4 RA,RE,4 RC,RF,2 RE,RG,1 RF,RH,4

(RF,RH,4) is the lowest-cost link on the candidate list, so it is added to the tree. No candidates remain on the list, so the algorithm is terminated. The shortest-path tree is complete when RA has a complete tree with all the shortest links to all other routers in the network.

RtrA from Figure 2-17 is running the SPF algorithm, using the link-state database of Table 2-5. Figure 2-18 shows the shortest-path tree constructed for RtrA by this algorithm. After each router calculates its own tree, it can examine the other routers' network link information and add the stub networks to the tree fairly easily. From this information, entries can be made into the routing table.

Figure 2-18 SPF Results

Was this article helpful?

0 0

Post a comment