Charles M. Kozierok The TCP-IP Guide

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

Flags 1

DD Sequence

Number

DD Sequence Number: Used to number a sequence of Database

Description messages so they are kept in order.

LSA Headers Variable

LSA Headers: Contains link-state advertisement headers, which carry

information about the LSDB. See near the end of the topic for more infor-

mation on LSAs.

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

Field Name

Size

(bytes)

Description

ags:

pec

ags use

orma

on a

e exc

ange o

Database Description messages:

Subfield

Name

Size

(bytes)

Description

Reserved

5/8

(5 bits)

Reserved: Sent and received as zero.

1/8

(1 bit)

I-Bit: Set to 1 to indicate that this is the first

(“initial”) in a sequence of Database Description

messages.

1/8

(1 bit)

M-Bit: Set to 1 to indicate that “more” Database

Description messages follow this one.

1/8

(1 bit)

MS-Bit: Set to 1 if the router sending this message

is the master in the communication, or 0 if it is the

slave.

Link State Request Message Format

These messages have a Type value of 3 in the header. Following the header comes one or

more sets of three fields that each identify a link state advertisement (LSA) for which the

router is requesting an update, as shown in Figure 187. Each LSA identification has the

format described in Table 130.

Figure 186: OSPF Database Description Message Format

Table 130: OSPF Link State Request Message Format

Field Name

Size

(bytes)

Description

LS Type 4 Link State Type: The type of link state advertisement (LSA) being sought.

Link State ID 4

Link State ID: The identifier of the LSA, usually the IP address of either the

router or network linked.

Advertising

Router

Advertising Router: The ID of the router that created the LSA whose

update is being sought.

Interface MTU Options Flags

DD Sequence Number

4 8 12 16 20 24 28 320

...

LSA Header #1

480

Reserved

Initial

Bit

(I)

Mor e

Bit

(M)

Mas ter /

Slave

Bit

(MS)

LSA Header #N

Link State Update Message Format

These messages have a Type value of 4 in the header, and the fields illustrated in Table

131 and Figure 188.

Figure 187: OSPF Link State Request Message Format

Table 131: OSPF Link State Update Message Format

Field Name

Size

(bytes)

Description

# LSAs 4

Number of LSAs: The number of link-state advertisements included in this

message.

LSAs Variable LSAs: One or more link-state advertisements. See below for more details.

Link State Type

Link State ID

Advertising Router

4 8 12 16 20 24 28 320

...

Link State Type / Link State ID / Advertising Router #2

LSA Identification #1

Link State Type / Link State ID / Advertising Router #N

Link State Acknowledgment Message Format

These messages have a Type value of 5 in the header. They then contain a list of LSA

headers corresponding to the LSAs being acknowledged, as shown in Table 132 and Figure

189.

Figure 188: OSPF Link State Update Message Format

Table 132: OSPF Link State Acknowledgment Message Format

Field Name

Size

(bytes)

Description

LSA Headers Variable

LSA Headers: Contains link-state advertisement headers, to identify the

LSAs acknowledged.

Figure 189: OSPF Link State Acknowledgment Message Format

Number of Link State Advertisements

Link State Advertisement #1

Link State Advertisement #N

4 8 12 16 20 24 28 320

...

4 8 12 16 20 24 28 320

...

LSA Header #1

LSA Header #N

Link State Advertisements (LSAs) and the LSA Header Format

As we saw above, several of the message types include link state advertisements (LSAs),

which are the fields that actually carry topological information about the LSDB. There are

several types of LSAs, which are used to convey information about different types of links.

Like the OSPF messages themselves, each LSA has a common header with 20 bytes, and

then a number of additional fields that describe the link.

LSA Header

The LSA header contains sufficient information to identify the link. It uses the subfield

structure in Table 133 and Figure 190.

Table 133: OSPF Link State Advertisement Header Format

Subfield Name

Size

(bytes)

Description

LS Age 2 LS Age: The number of seconds elapsed since the LSA was created.

Options 1

Options: Indicates which of several optional OSPF capabilities the router

supports.

LS Type 1

Link State ID 4

Link State ID: Identifies the link. This usually is the IP address of either the

router or the network the link represents.

Advertising

Router

4 Advertising Router: The ID of the router originating the LSA.

LS Sequence

Number

LS Sequence Number: A sequence number used to detect old or

duplicate LSAs.

LS Checksum 2 LS Checksum: A checksum of the LSA, for data corruption protection.

Length 2 Length: The length of the LSA, including the 20 bytes of the header.

LS Type: Indicates the type of link this LSA describes:

Value Link Type Description

1 Router-LSA Link to a router

2 Network-LSA Link to a network

Summary-LSA (IP

Network)

When areas are used, summary infor-

mation generated about a network.

Summary-LSA

(ASBR)

When areas are used, summary infor-

mation about a link to an AS boundary

router.

5 AS-External-LSA

An external link outside the autonomous

system.

LSA Body

Following the LSA header comes the body of the LSA, the specific fields of which depend

on the value of the LS Type field. It would take several more pages to describe all these

subfields, and I already probably went overboard in describing each message type, so I will

refer you to Appendix A of RFC 2328 if you want all the details. By way of quick summary:

☯ For normal links to a router, the LSA includes an identification of the router and the

metric to reach it, as well as details about the router such as whether it is a boundary

or area border router.

☯ LSAs for networks include a subnet mask and information about other routers on the

network.

☯ Summary LSAs include a metric and a summarized address, as well as a subnet

mask.

☯ External LSAs include a number of additional fields to allow the external router to be

communicated.

Figure 190: OSPF Link State Advertisement Header Format

LS Age Options LS Type

Link State ID

Advertising Router

LS Sequence Number

LS Checksum Length

4 8 12 16 20 24 28 320

Other Interior Routing Protocols

The Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) are the two

most well-known interior routing protocols used in the TCP/IP suite, and for this reason I

have described each in considerable detail. In addition to these, there are several other

TCP/IP interior routing protocols that fall into one of two categories. Some are either

protocols that are no longer used today but are interesting from a historical perspective, and

others are proprietary alternates to RIP and OSPF that you may encounter today in the

networking world but perhaps not as often.

In this section, I provide a brief description of four additional TCP/IP interior routing

protocols. I begin with a look at two obsolete protocols that played an important role in the

early Internet: the Gateway-to-Gateway Protocol (GGP) and the HELLO Protocol. I then

describe two interior routing protocols developed by Cisco Systems, which are sometimes

seen in the industry today as alternatives to RIP and OSPF: the Interior Gateway Routing

Protocol (IGRP) and the Enhanced Interior Gateway Routing Protocol (EIGRP).

Background Information: In some cases in this section, I make comparisons to

RIP and OSPF as appropriate, to show where these protocols are similar to or

differ from the “big two”. You may wish to have some familiarity with RIP and OSPF

before continuing here.

TCP/IP Gateway-to-Gateway Protocol (GGP)

In the overview topic on key routing protocol concepts, I described the evolution of TCP/IP

routing architectures. The modern Internet is based on the concept of independent auton-

omous systems (ASes) that run interior routing protocols within them, and exterior routing

protocols between them. The early Internet, however, was somewhat simpler; it consisted

of a relatively small number of core routers that carried detailed information about the

Internet as a whole, and non-core routers located around the core that knew only partial

information.

These core routers used a special routing protocol to communicate called the Gateway-To-

Gateway Protocol (GGP). GGP was originally developed in the early 1980s by Bolt,

Beranek and Newman (BBN) one of the pioneers of the Internet and TCP/IP. It was

documented in RFC 823, THE DARPA INTERNET GATEWAY

, published September 1982.

This protocol is now obsolete, but it played an important role in the early Internet, and also

introduced certain concepts that were used in routing protocols developed years later. This

makes knowing a little bit about it worthwhile.

Overview of Operation

GGP is similar in general operation to the Routing Information Protocol (RIP) in that it uses

a distance-vector algorithm to determine the best routes between devices. Like RIP, the

metric is a simple hop count, so GGP will select a route with the shortest number of hops.

While we have seen in our discussion of RIP that hop count is not always the best metric of

cost for a router, it was actually a pretty good method of route determination back then. This

is because the early Internet used both computers and links that would be considered

glacially slow by today's standards, making each hop fairly “expensive” compared to

modern routing.

A router using GGP initially starts out in a null state, assuming that all links to other routers

and local networks are down. It then tests the status of its local networks by seeing if it can

send and receive messages on the network. Every 15 seconds, the router sends a GGP

Echo message to each of its neighbors. If the neighbor receives the message, it responds

with a GGP Echo Reply message. The router sending the Echo messages considers the

neighbor up if it receives back replies to a certain percentage of messages, defaulting to

50%.

Note: These messages serve a similar function to ICMPv4 Echo and Echo Reply

messages, but are not the same.

Actual routing information is communicated by sending GGP Routing Update messages.

These are similar in nature to RIP Response messages used in RIP. Each Routing Update

message contains the information in the sending router's routing table, which specifies

which networks the router can reach and at what cost (in hops) for each.

Each router receiving a Routing Update message knows that since it can reach the router

that sent the update, it can also reach all of those router's reachable networks at the cost of

an additional hop. It uses the information to update its own internal tables of destinations

and metrics. It then sends out its own Routing Update on its own attached networks, to

propagate the information learned from other routers on its own networks. This process

continues until eventually, routes to all GGP routers spreads across the internetwork, just

as they do in RIP.

Propagation of Routing Table Information

One interesting difference between GGP and RIP is that in GGP, networks and costs aren't

sent in pairs. Instead, a GGP router sends its routing table in groups. If it has three networks

it can reach at a cost of 1 it sends those in a group with distance value 1, then if it has a few

at a cost of 2 it sends those in a group with distance value 2, and so on. Another difference

is that GGP Routing Update messages are acknowledged. Each Routing Update message

is sent with a sequence number, which is used to ensure that out-of-date information is not

propagated. If the Routing Update is received and has a new sequence number (indicating

that it is recent information), the router processing it sends back a GGP Acknowledgment

message back to the originator. If the sequence number indicates the message is stale, a

Negative Acknowledgment is sent instead and the message discarded.

As a distance-vector algorithm using hop count as a metric, GGP shared most of the same

pros and cons as RIP. It had simplicity on its side, but had various problems such as slow

convergence and issues such as the “counting to infinity” problem. GGP was a much more

rudimentary protocol than RIP, however, and did not include many of the features included

in RIP to handle such issues, such as split horizon. GGP was also limited to unsubnetted

classful networks, due to its age.

Current Role in TCP/IP

When Internet architecture moved to the use of autonomous systems, GGP was obsoleted.

While it was an important part of TCP/IP history, it is today not formally considered a part of

the TCP/IP protocol suite.

Key Concept: The Gateway-to-Gateway Protocol (GGP) was used to communicate

route information between core routers on the early Internet. It is a distance-vector

protocol that operates in a manner very similar to RIP. Each router periodically sends

out its routing table to neighboring routers, so each router can learn the cost, in hops, to

reach every network in the autonomous system. GGP is now considered a historical

protocol and is no longer part of TCP/IP.

The HELLO Protocol (HELLO)

The TCP/IP Internet as we know it today evolved over the course of decades. It began as

an experimental research project started by the United States Defense Advanced Research

Projects Agency (DARPA or ARPA), called the ARPAnet. The ARPAnet eventually grew

through the addition of other networks, such as the important NSFnet developed by the

National Science Foundation (NSF). The NSFnet backbone grew over the course of many

years and was instrumental to the eventual creation of the modern Internet.

The original NSFnet backbone consisted of six Digital Equipment Corporation (DEC,

absorbed by Compaq years ago) LSI-11 computers located across the United States.

These computers ran special software colloquially called “fuzzball” that enabled them to

function as routers. These “fuzzball routers” connected various networks to the NSFnet and

the ARPAnet.

The six NSFnet routers worked as an autonomous system (AS) and like any AS, used an

interior routing protocol to exchange routing information. The routing protocol used in these

early routers was called the HELLO protocol. It was developed in the early 1980s and

documented in RFC 891, DCN Local-Network Protocols

, published December 1983. The

name “HELLO” is capitalized, but is not an acronym; it simply refers to the word hello, since

the protocol uses messages that are sort of analogous to the routers talking to each other.

Note: The Open Shortest Path First (OSPF) routing protocol has a message type

called Hello. The use of these messages is sometimes referred to as “the Hello

Protocol”. OSPF is not directly related to the HELLO protocol described in this

section, other than both protocols being used for routing in an AS. It is possible OSPF

borrowed the name Hello from the HELLO protocol but I can't find anything definitive on that

subject.

Overview of Operation

The HELLO protocol uses a distance-vector algorithm, like the Routing Information Protocol

(RIP) and the Gateway-to-Gateway Protocol (GGP). What's interesting about it, however, is

that unlike RIP and GGP, HELLO does not use hop count as a metric. Instead, it attempts

to select the best route by assessing network delays and choosing the path with the

shortest delay.

One of the key jobs of routers using HELLO is to compute the time delay to send and

receive datagrams to and from its neighbors. On a regular basis, routers exchange HELLO

messages that contain clock and timestamp information. By comparing the clock value and

timestamp in the message to its own clock using a special algorithm, a receiving device can

compute an estimate for the amount of time it takes to send a datagram over the link.

Like RIP and GGP, HELLO messages also contain routing information in the form of a set of

destinations that the sending router is able to reach and a metric for each. However in this

case, the metric is an estimate of the round-trip delay cost for each destination. This infor-

mation is added to the computed round-trip delay time for the link over which the message

was received, and used to update the receiving router's own routing table.

This seems a bit confusing, but is really similar to the way a hop-count distance-vector

protocol like RIP works. Router A using RIP receiving an RIP Response message from

Router B knows it can reach every destination Router B can, but at a cost of one extra hop

(the hop to go from Router A to Router B). Similarly, router A receiving a HELLO message

from Router B knows it can reach every destination that Router B can, but at an additional

approximate cost of the computed delay for the link between Router A and Router B.

Issues with Using Delay as a Metric

In theory, using delay calculations should result in more efficient route selection than simply

using hop count, but at the cost of more complexity than a hop-count algorithm. This makes

HELLO very interesting indeed, especially for a protocol that is over 20 years old. However,

since the latency of a link is often unrelated to its bandwidth, using time delay as a link

metric may lead to spurious results.