Charles M. Kozierok The TCP-IP Guide

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

metric is a measure of “cost” that is used to assess the efficiency of a particular route. Since

internetworks can be quite complex, the algorithms and metrics of a protocol are very

important, and can be the determining factor in deciding that one protocol is superior to

another.

There are two routing protocol algorithms that are most commonly encountered: distance-

vector and link-state. There are also protocols that use a combination of these methods, or

others.

Distance-Vector (Bellman-Ford) Routing Protocol Algorithm

A distance vector routing algorithm, also called a Bellman-Ford algorithm after two of its

inventors, is one where routes are selected based on the distance between networks. The

distance metric is something simple—usually the number of “hops”, or routers between

them.

Routers using this type of protocol maintain information about the distance to all known

networks in a table. They regularly send that table to each router they immediately connect

with (their neighbors or peers). These routers then update their tables and send to their

neighbors. This causes distance information to propagate across the internetwork, so that

eventually each router obtains distance information about all networks on the internet.

Distance-vector routing protocols are somewhat limited in their ability to choose the best

route. They also are subject to certain problems in their operation that must be worked

around through the addition of special heuristics and features. Their chief advantages are

simplicity and history (they have been used for a long time).

Link-State (Shortest Path First) Routing Protocol Algorithm:

A link-state algorithm selects routes based on a dynamic assessment of the shortest path

between any two networks, and is for that reason also called a shortest-path first method.

Each router maintains a map describing the current topology of the internetwork. This map

is updated regularly by testing reachability of different parts of the internet, and by

exchanging link-state information with other routers. The determination of the best route

(“shortest path”) can be made based on a variety of metrics that indicate the true cost of

sending a datagram over a particular route.

Link-state algorithms are much more powerful than distance-vector algorithms. They adapt

dynamically to changing internetwork conditions, and also allow routes to be selected

based on more realistic metrics of cost than simply the number of hops between networks.

However, they are more complicated to set up and use more computer processing

resources than distance-vector algorithms, and aren't as well-established.

Hybrid Routing Protocol Algorithms

There are also hybrid protocols that combine features from both types of algorithms, and

other protocols that use completely different algorithms. For example, the Border Gateway

Protocol (BGP) is a path-vector algorithm, which is somewhat similar to the distance-vector

algorithm, but communicates much more detailed route information. It includes some of the

attributes of distance-vector and link-state protocols, but is more than just a combination of

the two.

Static and Dynamic Routing Protocols

You may also occasionally see routing protocols categorized by type as static and dynamic,

so this is the last concept I want to discuss in this overview. This terminology is somewhat

misleading. The term “static routing” simply refers to a situation where the routing tables are

manually set up, so they remain static. In contrast, “dynamic routing” is the subject of this

entire section: the use of routing protocols to dynamically update routing tables. Thus, all

routing protocols are “dynamic”. There is no such thing as a “static routing protocol” unless

you consider a network administrator editing a routing table a “protocol”.

TCP/IP Interior Routing Protocols (RIP, OSPF, GGP, HELLO, IGRP,

EIGRP)

Modern TCP/IP routing architecture groups routers into autonomous systems (ASes) that

are independently controlled by different organizations and companies. The routing

protocols used to facilitate the exchange of routing information between routers within an

AS are called interior routing protocols (or historically, interior gateway protocols). Since

most network administrators are responsible for routers within a particular organization,

these are the routing protocols you are most likely to deal with unless you become a major

Internet big-shot. ☺

One of the benefits of autonomous systems architecture is that the details of what happens

within an AS are hidden from the rest of the internetwork. This means that there is no need

for universal agreement on a single “language” for an internet as is the case for exterior

routing protocols. As a network administrator for an AS, you are free to choose whatever

interior routing protocol best suits your networks. The result of this is that there is no

agreement on the use of a single TCP/IP interior routing protocol. There are several

common ones in use today, though as is usually the case, some are more popular than

others.

In this section I provide a description of six different protocols used for routing within auton-

omous systems in TCP/IP. The first two sections provide comprehensive descriptions of two

of the most popular TCP/IP interior routing protocols: the Routing Information Protocol

(RIP) and Open Shortest Path First (OSPF). The third section provides a more brief

discussion of two historical interior routing protocols and two proprietary ones developed by

networking leader Cisco Systems.

TCP/IP Routing Information Protocol (RIP, RIP-2 and RIPng)

The most popular of the TCP/IP interior routing protocols is the Routing Information

Protocol (RIP). The simplicity of the name matches the simplicity of the protocol—RIP is

one of the easiest to configure and least resource-demanding of all the routing protocols. Its

popularity is due both to this simplicity and its long history. In fact, support for RIP has been

built into operating systems for as long as TCP/IP itself has existed.

In this section I describe the characteristics and operation of the TCP/IP Routing Infor-

mation Protocol (RIP). There are three versions of RIP: RIP versions 1 and 2 for IP version

4 and RIPng (next generation) for IP version 6. The basic operation of the protocol is mostly

the same for all three versions, but there are also some notable differences between them,

especially in terms of the format of messages sent.

For this reason, I have divided my description of RIP into two subsections. In the first, I

describe the fundamental attributes of RIP and its operation in general terms for all three

versions. In the second, I take a closer look at each version, showing the message format

used for each and discussing version-specific features as well.

RIP Fundamentals and General Operation

The Routing Information Protocol (RIP) was one of the first interior routing protocols used in

TCP/IP. Over 20 years later, it continues to be widely used. Even though RIP has important

limitations that have caused some to malign it and in fact led to the development of newer

routing protocols that are technically superior to it, RIP continues to have an important

place in TCP/IP routing to this day. Evidence that RIP has a future can be seen in the

creation of an IPv6 version of the protocol: RIPng.

In this section, I provide an overall description of the characteristics of RIP and how it works

in general terms. I begin with an overview and history of the protocol, including a brief

discussion of its different versions and the standards that define them. I describe the

method that RIP uses to determine routes and the metric used to assess route cost. I

describe the general operation of the protocol including message types and when they are

sent. I then describe the most important limitations and issues with RIP, and the special

features that have been added to the protocol to resolve several problems with the basic

RIP algorithm.

RIP Overview, History, Standards and Versions

The Routing Information Protocol (RIP) has been the most popular interior routing protocol

in the TCP/IP suite for many years. The history of the protocol and how it came to achieve

prominence is a rather interesting one. Unlike many of the other important protocols in the

TCP/IP suite, RIP was not first developed formally using the RFC standardization process.

Rather, it evolved as a de facto industry standard and only became an Internet standard

later on.

Early History of RIP

The history of RIP shares some commonality with that of another networking heavyweight:

Ethernet. Like the formidable LAN technology, RIP's roots go back to that computing

pioneer, Xerox's Palo Alto Research Center (PARC). At the same time that Ethernet was

being developed for tying together local area networks, PARC created a higher layer

protocol to run on Ethernet called the Xerox PARC Universal Protocol (PUP). PUP required

a routing protocol, so Xerox created a protocol called the Gateway Information Protocol

(GWINFO). This was later renamed the Routing Information Protocol and used as part of

the Xerox Network System (XNS) protocol suite.

RIP entered the mainstream when developers at the University of California at Berkeley

adapted it for use in the Berkeley Standard Distribution (BSD) of the UNIX operating

system. RIP first appeared in BSD version 4.2 in 1982, where it was implemented as the

UNIX program routed (pronounced “route-dee”, not “rout-ed”—the “d” stands for daemon, a

common UNIX term for a server process.)

BSD was (and still is) a very popular operating system, especially for machines connected

to the early Internet. As a result, RIP was widely deployed and became the industry

standard for internal routing protocols. It was used both for TCP/IP and also other protocol

suites. In fact, a number of other routing protocols, such as the RTP protocol in the

AppleTalk suite, were based on this early version of RIP.

RIP Standardization

For a while, the BSD implementation of routed was actually considered the standard for the

protocol itself. However, this was not a formally defined standard, and this meant there was

no formal definition of how exactly it functioned. This lead to slight differences in various

implementations of the protocol over time. To resolve potential interoperability issues

between implementations, the IETF formally specified RIP in the Internet standard RFC

1058, Routing Information Protocol, published in June 1988. This RFC was based directly

on the BSD routed program. This original version of RIP is now also sometimes called RIP

version 1 or RIP-1 to differentiate it from later versions.

RIP's popularity was due in large part to its inclusion in BSD; this was in turn a result of the

relative simplicity of the protocol. RIP uses the distance-vector algorithm (also called the

Bellman-Ford algorithm after two of its inventors) to determine routes. Each router

maintains a routing table containing entries for various networks or hosts in the inter-

network. Each entry contains two primary pieces of information: the address of the network

or host, and the distance to it, measured in hops, which is simply the number of routers that

a datagram must pass through to get to its destination.

RIP Operational Overview, Advantages and Limitations

On a regular basis, each router in the internetwork sends out its routing table in a special

message on each of the networks to which it is connected, using UDP. Other routers

receive these tables and use them to update their own tables. This is done by taking each

of the routes they receive and adding an extra hop. For example, if router A receives an

indication from router B that network N1 is 4 hops away, then since router A and router B

are adjacent, the distance from router A to N1 is 5. After a router updates its tables, it in turn

sends out this information to other routers on its local networks. Over time, routing distance

information for all networks propagates over the entire internetwork.

RIP is straight-forward in operation, easy to implement, and undemanding of router

processing power, which makes it attractive especially in smaller autonomous systems.

There are, however, some important limitations that arise due to the simplicity of the

protocol. For starters, hops are often not the best metric to use in selecting routes. There

are also a number of problems that arise with the algorithm itself. These include slow

convergence (delays in having all routers agree on the same routing information) and

problems dealing with network link failures.

RIP includes several special features to resolve some of these issues, but others are

inherent limitations of the protocol. For example, RIP only supports a maximum of 15 hops

between destinations, making it unsuitable for very large autonomous systems, and this

cannot be changed.

Key Concept: The Routing Information Protocol (RIP) is one of the oldest and most

popular interior routing protocols. It uses a distance-vector algorithm with each router

maintaining a table indicating how to reach various networks in the autonomous

system and the distance to it in hops. RIP is popular because it is well-established and

simple, but has a number of important limitations.

Development of RIP Version 2 (RIP-2) and RIPng for IPv6

Some other issues with RIP were a result of its having been developed in the early 1980s

when TCP/IP was still in its infancy. Over time, as the use of TCP/IP protocols changed,

RIP became outdated. In response, RIP Version 2, or RIP-2 was created in the early 1990s.

RIP-2 defines a new message format for RIP and includes a number of new features,

including support for classless addressing, authentication, and the use of multicasting

instead of broadcasting to improve network performance. It was first defined in RFC 1388,

RIP Version 2 Carrying Additional Information, published in January 1993. This RFC was

revised in RFC 1723, and finalized in RFC 2453, RIP Version 2, November 1998.

Over two decades after it was first created, RIP continues to be a popular interior routing

protocol. Its limitations have led to many internetworking experts hoping that the protocol

would eventually “go away”, in favor of newer protocols like OSPF that are superior on a

strictly technical basis. Some have gone so far as to sarcastically suggest that maybe it

would be best if RIP would “R. I. P.” (“rest in peace”.) ☺ Once a protocol becomes popular,

however, it's hard to resist momentum, and RIP is likely to continue to be used for many

years to come.

In order to ensure that RIP can work with TCP/IP in the future, it was necessary to define a

version that would work with the new Internet Protocol version 6 (IPv6). In 1997, RFC 2080

was published, titled RIPng for IPv6. The ng stands for next generation—recall that IPv6 is

also sometimes called IPng. RIPng is not just a new version of RIP, like RIP-2, but is

defined as a new standalone protocol. It is, however, based closely on the original RIP and

RIP-2 standards. A distinct protocol (as opposed to a revision of the original) was needed

due to the changes made between IPv4 and IPv6, though RIP and RIPng work in the same

basic way. RIPng is sometimes also called RIPv6.

Key Concept: The original version of RIP has the fewest features and is now called

RIP-1. RIP-2 was created to add support for classless addressing and other capabil-

ities. RIPng is the version created for compatibility with IPv6.

RIP Route Determination Algorithm and Metric

As I mentioned in the overview topic on TCP/IP routing protocols, one of the defining

characteristics of any routing protocol is the algorithm it uses for determining routes. RIP

falls into the class of protocols that use a distance-vector or Bellman-Ford routing algorithm.

To help you better understand exactly how RIP determines routes, I will now discuss the

specific implementation of the algorithm for RIP and provide an example so you can see

exactly how RIP determines routes and propagates information across a network.

RIP Routing Information and Route Distance Metric

The job of RIP, like any routing protocol, is to provide a mechanism for exchanging infor-

mation about routes so routers can keep their routing tables up to date. Each router in an

RIP internetwork keeps track in its routing table of all networks (and possibly individual

hosts) in the internetwork. For each network or host, the device includes a variety of infor-

mation, of which the following are the most important:

☯ The address of the network or host.

☯ The distance from that router to the network or host.

☯ The first hop for the route: the device to which datagrams must first be sent to

eventually get to the network or host.

In theory, the distance metric can be any assessment of cost, but in RIP, distance is

measured in hops. As you probably already know, in TCP/IP vernacular, a datagram makes

a hop when it passes through a router. Thus, the RIP distance between a router and a

network measures the number of routers that the datagram must pass through to get to the

network. If a router connects to a network directly, then the distance is 1 hop. If it goes

through a single router, the distance is 2 hops, and so on. In RIP, a maximum of 15 hops are

allowed for any network or host. The value 16 is defined as infinity, so an entry with 16 in it

means “this network or host is not reachable”.

RIP Route Determination Algorithm

On a regular basis, each router running RIP will send out its routing table entries to provide

information to other routers about the networks and hosts it knows how to reach. Any

routers on the same network as the one sending out this information will be able to update

their own tables based on the information they receive. Any router that receives a message

from another router on the same network saying it can reach network X at a cost of N,

knows it can reach network X at a cost of N+1 by sending to the router it received the

message from.

RIP Route Determination and Information Propagation Example

Let's take a specific example to help us understand better how routes are determined using

RIP. Consider a relatively simple internetwork with four individual networks, connected as

follows:

☯ Router A (RA) connects Network 1 (N1) to Network 2 (N2).

☯ Routers B (RB) and C (RC) connect Network 2 to Network 3 (N3).

☯ Router D (RD) connects Network 3 to Network 4 (N4).

This example autonomous system is illustrated in Figure 172.

Now, let's suppose that we just turned on router RA. It sees that it is directly connected to

N1 and N2, so it will have an entry in its routing table indicating that it can reach N1 at a cost

of 1, which we can represent as {N1,1}. Information about Network 1 will propagate from

Router RA across the internetwork in the following sequence of steps (which you can

observe graphically in Figure 173):

1. Router A sends out an RIP message containing the entry {N1,1} on each of the

networks to which it is connected. There are no other routers on N1, so nothing

happens there. But RB and RC are on N2 so they receive the information.

2. RB and RC will look in their routing tables to see if they already have entries for N1.

Assuming neither does, they will each create a routing table entry {N1,2} for Router A.

This means “I can reach Network 1 at a cost of 2 hops by sending to Router A”.

3. RB and RC will each send their own routing tables out over the networks to which they

are connected: N2 and N3. This will contain the entry {N1,2}. RA will receive that

message on N2 but will ignore it, since it knows it can reach N1 directly (cost of 1,

which is less than 2). But Router D will receive the message on N3.

4. RD will examine its routing table, and seeing no entry for N1 will add the entry {N1,3}

for RB or RC. Of course, either one will work, so which is chosen depends entirely on

whether RD received information about N1 first from RB or RC.

5. RD will send the entry {N1,3} on Network 4, but of course there are no other routers

there to hear it.

RIP is designed so that a routing entry is only replaced if information is received about a

shorter route; ties go to the incumbent, if you will. This means that once RD creates an

entry for N1 with a cost of 3 going through RB, if it receives information that it can reach N1

at the same cost of 3 through RC, it will ignore it. Similarly, if it gets RC's info first, it will

ignore the information from RB.

Naturally, this same propagation scheme will occur for all the other networks as well; I have

just shown only how information about N1 moves from router to router. For example, Router

A will eventually install an entry for N4 saying that it is reachable at a cost of 3 going

through either RB or RC: this will be either {N4,RB,3} or {N4,RC,3}.

This propagation of network routing information occurs on a regular basis, and also when

the structure of the network changes (due to either intentional changes in topography or

failure of links or routers). When this happens the change information will move through the

Figure 172: Example RIP Autonomous System

This is an example of a simple autonomous system that contains four physical networks and four routers.

Network 2 Network 3

Network 1

Network 4

Figure 173: Propagation of Network Routing Information Using RIP

This composite diagram illustrates the five steps in propagating route information about network N1 from RA

to the rest of the autonomous system. In Step #1 the information is sent from RA to both of its connected

networks. In Step #2 it reaches routers RB and RC, which then know they can reach N1 through RA at a cost

of one additional hop. In Step #3 these two routers send this information on their networks, and in Step #4 it

reaches RD. In Step #5 RD sends out the information, but no other routers are around to receive it.

{N1,1}

N2 N3 N4

{N1,RA,2}

{N1,1}

N2 N3 N4

{N1,RA,2}

{N1,RC,3}

{N1,3}

{N1,RA,2}

{N1,1}

N2 N3

{N1,RA,2}

{N1,2}

{N1,1}

N2 N3 N4

{N1,1}

N2 N3

{N1,RC,3}

{N1,2}

{N1,RA,2}