Charles M. Kozierok The TCP-IP Guide

Подождите немного. Документ загружается.

In this example, Router A and Router D are internal routers. Router B and Router C are

area border routers, and comprise the backbone (Area 0) of the internetwork. Routers A, B

and C will maintain an LSDB describing Area 1, while Routers B, C and D will maintain an

LSDB describing Area 2. Routers B and C maintain a separate LSDB for the backbone.

There is no backbone router other than the area border routers B and C. However, suppose

we had a router E that had only direct connections to RB and RC. This would be a

backbone router only.

You have probably already discovered the chief drawback to hierarchical topology:

complexity. For large autonomous systems, however, it has significant advantages over

making every router a peer. At the same time, the conceptual complexity is made worse by

the need for very careful design, especially of the backbone. If the hierarchy is not set up

properly, a single failure of a link between routers could disrupt the backbone and isolate

one or more of the areas (including all the devices on all networks within the area!)

OSPF Route Determination Using SPF Trees

The key data structure maintained by each router in an OSPF autonomous system (AS) is

the link-state database (LSDB). The LSDB contains a representation of the topology of

either the entire AS (in basic topology) or a single area (in hierarchical topology). As we

have seen earlier in this section, each router in the AS or area has the same LSDB, so it

represents a neutral view of the connections between routers and networks.

Of course, each router needs to participate in keeping the LSDB up to date, but it also has

its own “selfish” concerns. It needs to be able to determine what routes it should use for

datagrams it receives from its connected networks—this is, after all, the entire point of a

routing protocol.

The SPF Tree

To find the best route from any router, it must determine the shortest path between itself and

each router or network in the AS or area. For this, it needs not a neutral view of the inter-

network but a view of it from its own perspective.

The router creates this perspective by taking the information in the LSDB and transforming

it into a shortest path first tree or SPF tree. The term “tree” refers to a data structure with a

root that has branches coming out that go to other nodes, which in turn have branches. The

structure as a whole looks like an upside-down tree. In this case, the SPF tree shows the

topology information of the AS or area with the router constructing the tree at the top. Each

directly-connected router or network is one step down in the tree; each router or network

connected to these first-level routers or networks is then connected, and so on, until the

entire AS or area has been represented.

Again, the router doesn't really make the tree; it is just an algorithmic calculation performed

by the computer within the router. Once this is done, however, this logical construct can be

used to calculate the cost for that router to reach any router or network in the AS (or area).

In some cases, there may be more than one way to reach a router or network, so the tree is

constructed to show only the shortest (lowest-cost) path to the network.

Of course, each router is only responsible for sending a datagram on the next leg of its

journey, and not for what happens to the journey as a whole. After the SPF tree is done, the

router will create a routing table with an entry for each network, showing the cost to reach it,

and also the next hop router to use to reach it.

The SPF tree is created dynamically based on the current state of the LSDB. If the LSDB

ever changes, the SPF tree and the routing information are recalculated.

Key Concept: To determine what routes it should use to reach networks in its auton-

omous system, a router generates a shortest path first tree (SPF tree) from its link-

state database. This tree contains the same basic information as the LSDB but

presents it from the point of view of the router doing the calculation so that router can see

the costs of various paths to different networks.

OSPF Route Determination Example

I can almost see your eyes glazing over, so let's go back again to the example we have

been using in this section. I am going to assume we are looking at the whole AS as a whole

in basic topology, for simplicity. In Table 125, I have repeated the LSDB for this AS, and I

have taken the liberty of replacing the “☯“s with cost metrics; these are shown in Figure 181

as well. Again, remember there is no cost to reach a router from a network, so those links

have a non-zero cost only going from the router to the network.

Now, let's construct the SPF tree for RC. We can do this in iterations, as follows (this is

shown graphically in Figure 182 as well for your convenience):

First Level

To construct the first level of the tree, we look for all devices that RC can reach directly. We

find:

Table 125: Example OSPF Link State Database (LSDB) With Costs

To Router /

Network

From Router From Network

RA RB RC RD N1 N2 N3 N4

RA 00

RB 5 0 0

RC 500

RD 0 0

N1 2

N2 3 4 3

N3 561

N4 4

☯ RB, with a cost of 5.

☯ N2, with a cost of 3.

☯ N3, with a cost of 6.

Second Level

To construct the second level, we look for all devices that the devices on the first level can

reach directly. We then add the cost to reach each device on the first level to the cost of

each device at the second level:

☯ RB: RB has a cost of 5 and can reach:

☯ RC, with a cost of 5, total cost of 10.

☯ N2, with a cost of 4, total cost of 9.

☯ N3, with a cost of 5, total cost of 10.

☯ N2: N2 has a cost of 3 and can reach:

☯ RA, with a cost of 0, total cost of 3.

☯ RB, with a cost of 0, total cost of 3.

☯ RC, with a cost of 0, total cost of 3.

☯ N3: N3 has a cost of 6 and can reach:

☯ RB, with a cost of 0, total cost of 6.

☯ RC, with a cost of 0, total cost of 6.

☯ RD, with a cost of 0, total cost of 6.

You probably can see immediately that we ended up with a number of different paths to the

same devices or networks, some of which make no sense. For example, we don't really

care about any path that goes to RC, since we are RC! Similarly, we can weed out certain

paths immediately because we already have a shorter path to them; taking a path through

RB to N3 with a cost of 10 makes no sense when we can go directly at the first level for a

cost of 6. So, after separating out the chaff, we end up with the following “wheat” at the

second level:

Figure 181: Example OSPF Autonomous System With Costs

This is the same sample AS that is shown in Figure 179, but with costs assigned to each of the links between

routers and networks. Costs between routers and networks are applied only in the direction from the router to

the network.

Network 1

Network 2 Network 3 Network 4

☯ N2 to RA, with a cost of 3.

☯ N3 to RD, with a cost of 6.

Third Level

We continue the process by looking for devices that connect to the “weeded-out” devices

we found on the second level (this time I am only showing the meaningful ones):

☯ RA: RA connects to N1, with a cost of 2, total cost of 5.

☯ RD: RD connects to N4, with a cost of 4, total cost of 10.

Figure 182: OSPF Route Determination Using The Shortest Path First Algorithm

This diagram shows graphically how a router, in this case RC, determines the best path to various networks.

The arrows here represent not the transfer of data but rather the examination of various links from a router to

other routers or networks. In panel #1, RC examines its LSDB and determines the cost for each of its directly-

linked devices. In #2, the second level of the SPF tree is constructed by adding to those numbers the costs of

all routers/networks that connect to the routers/networks found in panel #1. (The red arrows represent “looking

back” in the direction we came from in the prior step, which we don’t pursue.) In #3 the process continues,

resulting in the determination of a cost of 5 for RC to reach N1 and 10 to reach N4.

N2 N3 N4

3+0

6+0+4

3+0+2

6+0

N2 N3 N4RC

5+4

5+5

3+0

6+0

Shortest Path Tree and Route Calculation Results

In this simple example, we only need three levels to construct the tree for RC (we would

need more for RA or RD, however.) The final results would be the tree in Figure 183, and

the routing information for RC to the four networks that is shown in Table 126.

This of course is what you would expect in this very simple example. Note that there are no

specific entries for other routers, since they are the “means to the end” of reaching

networks. However, if one of the other routers were a boundary router that connected the

AS to the outside world, there would be entries for the networks to which the boundary

router connected, so RC knew to send traffic for those networks to that boundary router.

OSPF General Operation and Message Types

As a routing protocol, the main job of OSPF is to facilitate the exchange of routing infor-

mation between routers. Each router in an OSPF autonomous system that runs OSPF

software that is responsible for various tasks, such as setting timers to control certain activ-

ities that must occur on a regular basis, and the maintenance of important data structures,

Figure 183: OSPF Calculated Shortest Path First Tree

This is a graphical representation of the SPF tree calculated in Figure 182, showing only the final results of the

calculation process.

Table 126: Example Calculated OSPF Routes

Destination

Network

Cost Next Hop

N1 5RA

N2 3 (local)

N3 6 (local)

N4 10 RD

RA RD

N2 N3

N1 N4

3+0+2 6+0+4

such as the link-state database (LSDB). Most importantly, each OSPF router must both

generate and respond to OSPF messages. It is this messaging system that allows

important routing information to be shared within an AS or area, which makes it crucial to

understanding how OSPF works. So, it's worth taking a look at the message types and how

they are used.

OSPF Message Types

Unlike RIP, OSPF does not send its information using the User Datagram Protocol (UDP).

Instead, OSPF forms IP datagrams directly, packaging them using protocol number 89 for

the IP Protocol field. OSPF defines five different message types, for various types of

communication:

1. Hello: As the name suggests, these messages are used as a form of greeting, to allow

a router to discover other adjacent routers on its local links and networks. The

messages establish relationships between neighboring devices (called adjacencies)

and communicate key parameters about how OSPF is to be used in the autonomous

system or area.

2. Database Description: These messages contain descriptions of the topology of the

AS or area. That is, they convey the contents of the link-state database for the auton-

omous system or area from one router to another. Communicating a large LSDB may

require several messages to be sent; this is done by having the sending device desig-

nated as a master device and sending messages in sequence, with the slave

(recipient of the LSDB information) responding with acknowledgements.

3. Link State Request: These messages are used by one router to request updated

information about a portion of the LSDB from another router. The message specifies

exactly which link(s) about which the requesting device wants more current

information.

4. Link State Update: These messages contain updated information about the state of

certain links on the LSDB. They are sent in response to a Link State Request

message, and also broadcast or multicast by routers on a regular basis. Their contents

are used to update the information in the LSDBs of routers that receive them.

5. Link State Acknowledgment: These messages provide reliability to the link-state

exchange process, by explicitly acknowledging receipt of a Link State Update

message.

OSPF Messaging and General Operation

The use of these messages is approximately as follows. When a router first starts up it will

send a Hello message out to see if any neighboring routers are around running OSPF, and

it will also send them out periodically to discover any new neighbors that may show up.

When an adjacency is set up with a new router, Database Description messages will then

be sent to initialize the router's LSDB.

Routers that have been initialized enter a steady state mode. They will each routinely

“flood” their local networks with Link State Update messages, advertising the state of their

links. They will also send out updates when they detect a change in topology that needs to

be communicated. They will of course receive Link State Update messages sent by other

devices, and respond with Link State Acknowledgments accordingly. Routers may also

request updates using Link State Request messages.

Key Concept: The operation of OSPF involves five message types. Hello messages

are used to establish contact between routers, and Database Description messages

to initialize a router’s link-state database. Routine LSDB updates are sent using Link

State Update messages, which are acknowledged using Link State Acknowledgments. A

device may also request a specific update using a Link State Request.

When hierarchical topology is used, internal routers maintain a single LSDB and perform

messaging only within an area. Area border routers have multiple LSDBs and perform

messaging in more than one area. They, along with any other OSPF backbone routers, also

exchange messaging information on the backbone, including summarized link-state infor-

mation for the areas they border.

Again, all of this is highly simplified; the OSPF standard contains pages and pages of

detailed rules and procedures governing the exact timing for sending and receiving

messages.

OSPF Message Authentication

The OSPF standard specifies that all OSPF messages are authenticated for security. This

is a bit misleading, however, since one of the authentication “methods” supported is “null

authentication”—meaning no authentication is used. More security is provided by using the

optional simple password authentication method, and the most security through the use of

cryptographic authentication. These methods are described in Appendix D of RFC 2328.

Note: The Hello messages used in OSPF are also sometimes called the Hello

Protocol. This is especially poor terminology because there is an actual routing

protocol, described in the next section, called the HELLO Protocol. The two

protocols are not related. However, I suspect that the OSPF Hello messages may have

been so named because they serve a similar purpose to the messages used in the

independent HELLO protocol.

OSPF Message Formats

OSPF uses five different types of messages to communicate both link-state and general

information between routers within an autonomous system or area. To help illustrate better

how the OSPF messages are used, it's worth taking a quick look at the format used for

each of these messages. Well, I guess I am being somewhat liberal in my use of the term

“quick” here. ☺

OSPF Common Header Format

Naturally, each type of OSPF message includes a slightly different set of information—

otherwise, they wouldn't be different message types! However, they all share a similar

message structure, beginning with a shared 24-byte header. This common header allows

certain standard information to be conveyed in a consistent manner, such as the number of

the version of OSPF that generated the message. It also allows a device receiving an

OSPF message to quickly determine which type of message it has received, so it knows

whether or not it needs to bother examining the rest of the message.Table 127 and Figure

184 show the common OSPF header format.

Table 127: OSPF Common Header Format

Field Name

Size

(bytes)

Description

Version # 1 Version Number: Set to 2 for OSPF version 2.

Type 1

Packet Length 2

Packet Length: The length of the message, in bytes, including the 24

bytes of this header.

Router ID 4

Router ID: The ID of the router that generated this message (generally its

IP address on the interface over which the message was sent).

Area ID 4

Area ID: An identification of the OSPF area to which this message

belongs, when areas are used.

Checksum 2

Checksum: A 16-bit checksum computed in a manner similar to a

standard IP checksum. The entire message is included in the calculation

except the Authentication field.

AuType 2

Authentication 8

Authentication: A 64-bit field used for authentication of the message, as

needed.

Type: Indicates the type of OSPF message:

Type Value OSPF Message Type

1 Hello

2 Database Description

3 Link State Request

4 Link State Update

5 Link State Acknowledgment

ype:

ype o

on use

thi

message:

Authentication Type

Value

OSPF Authentication Type

0 No Authentication

1 Simple Password Authentication

2 Cryptographic Authentication

Specific Message Formats

Following this header, the body of the message includes a variable number of fields is

included that depends on the message type. Each of the message formats is described in

detail in RFC 2328; since some are quite long I will describe their fields only briefly here.

Hello Message Format

These messages have a Type value of 1 in the header, and the field structure shown in

Table 128 and Figure 185 in the body of the message.

Figure 184: OSPF Common Header Format

Table 128: OSPF Hello Message Format (Page 1 of 2)

Field Name

Size

(bytes)

Description

Network Mask 4 Network Mask: The subnet mask of the network the router is sending to.

Hello Interval 2

Hello Interval: The number of seconds this router waits between sending

Hello messages.

Options 1 Options: Indicates which optional OSPF capabilities the router supports.

Rtr Pri 1

Router Priority: Indicates the router's priority, when electing a backup

designated router.

Router Dead

Interval

Router Dead Interval: The number of seconds a router can be “silent”

before it is considered to have failed.

Version Number = 2 Type Packet Length

Router ID

Area ID

Checksum Authentication Type

Authentication

Message Body

4 8 12 16 20 24 28 320

Database Description Message Format

These messages have a Type value of 2 in the header, and the body structure depicted in

Table 129 and Figure 186.

Designated

Router

Designated Router: The address of a router designated for certain special

functions on some networks. Set to zeroes if there is no designated router.

Backup Desig-

nated Router

Backup Designated Router: The address of a backup designated router.

Set to all zeroes if there is no backup designated router.

Neighbors

Multiple

of 4

Neighbors: The addresses of each router from which this router has

received Hello messages recently.

Figure 185: OSPF Hello Message Format

Table 129: OSPF Database Description Message Format (Page 1 of 2)

Field Name

Size

(bytes)

Description

Interface MTU 2

Interface MTU: The size of the largest IP message that can be sent on this

router's interface without fragmentation.

Options 1

Options: Indicates which of several optional OSPF capabilities the router

supports.

Table 128: OSPF Hello Message Format (Page 2 of 2)

Field Name

Size

(bytes)

Description

Network Mask

Hello Interval Options Router Priority

Router Dead Interval

Designated Router

Backup Designated Router

Neighbor #1

Neighbor #N

4 8 12 16 20 24 28 320

...