Charles M. Kozierok The TCP-IP Guide

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

internetwork so that all routers are eventually updated. For example, suppose a connection

were added from Router C to Network 1. If Router D previously had the entry {N1,RB,3}, it

would eventually change this to {N1,RC,2}, since it could now reach N1 more quickly by

going through Router C.

Default Routes

In some cases it is not convenient for every network or host in a large internetwork to be

fully specified with its own routing entry. In this case it may be advantageous to specify a

default route for the network to use in reaching hosts or networks for which they have no

information. The most common example of this is when an autonomous system connects to

the public Internet through a single router. Except for that router, the rest of the local

network doesn't need to know how to access the Internet.

In RIP, information about a default route is communicated by having routers intended to

handle such traffic send information about a “dummy” network with the address 0.0.0.0.

This is treated as if it were a regular network when information about routes is propagated

on the internetwork using RIP messages, but other devices recognize this special address

and understand it means a default route.

Note: The algorithm description in this topic is the basic one used by RIP. This is

modified in certain ways to address some of the problems that can occur in special

circumstances due to how the algorithm works. Topics later in this chapter

describe these problems and the special features RIP includes to address them.

Key Concept: Routing information is propagated between routers in RIP using a

simple algorithm. On a regular basis, each router sends out RIP messages that

specify what networks it can reach, and how many hops to reach them. Other routers

directly connected to that one know that they can then reach those networks through that

router at a cost of one additional hop. So if router A sends a message saying it can reach

network X for a cost of N hops, each other router that connects directly to A can reach

network X for a cost of N+1 hops. It will put that information into its routing table, unless it

knows of an alternate route through another router that has a lower cost.

RIP General Operation, Messaging and Timers

RIP is a protocol for exchanging routing information, so its operation can best be described

in terms of the messages used to exchange this information, and the rules for when

messages are sent. The RIP software in each router sends messages and takes other

actions both in reaction to certain events and in response to triggers set off by timers.

Timers are also used to determine when routing information should be discarded if not

updated.

RIP Messages and Basic Message Types

Communication between RIP software elements in routers on an internetwork is accom-

plished through the use of RIP messages. These messages are sent using the User

Datagram Protocol (UDP), with reserved UDP port number 520 for RIP-1 and RIP-2, and

521 for RIPng. Thus, even though RIP is considered part of layer three like other routing

protocols, it behaves more like an application in terms of how it sends messages. The exact

format of the message is version-dependent, and all three formats (for RIP, RIP-2 and

RIPng) are described in detail in their own section. RIP messages can be either sent to a

specific device, or can be sent out for multiple devices to receive. If directed to one device

they are sent unicast; otherwise, they are either broadcast (in RIP) or multicast (RIP-2 and

RIPng).

There are only two basic message types for all three versions of RIP:

☯ RIP Request: A message sent by a router to another router asking it to send back all

or part of its routing table.

☯ RIP Response: A message sent by a router containing all or part of its routing table.

Note that despite the name, this message is not sent just in response to an RIP

Request message, as we will see. So it's not really that great a name… oh well.

Note: The original RIP also defined a few other message types: Traceon, Traceoff

and a special message type reserved for use by Sun Microsystems. These are

obsolete and no longer used, and were removed from the RIP-2 and RIPng

standards.

RIP Update Messaging and the 30-Second Timer

RIP Request messages are sent under special circumstances, when a router requires that it

be provided with immediate routing information. The most common example of this is when

a router is first powered on. After initializing, the router will typically send an RIP Request on

its attached networks to ask for the latest information about routes from any neighboring

routers. It is also possible for RIP Request messages to be used for diagnostic purposes.

A router receiving an RIP Request will process it and send an RIP Response containing

either all of its routing table, or just the entries the Request asked for, as appropriate. Under

normal circumstances, however, routers do not usually send RIP Request messages asking

specifically for routing information. Instead, a special timer is used on each RIP router that

goes off every 30 seconds. (This timer is not given a specific name in the RIP standards; it

is just “the 30 second timer”).

Each time the timer expires, an unsolicited (unrequested) broadcast/multicast is made of an

RIP Response message containing the router's entire routing table. The timer is then reset

and 30 seconds later goes off again, causing another routine RIP Response to be sent.

This process ensures that route information is regularly sent around the internet, so routers

are always kept up to date about routes.

Key Concept: RIP uses two basic message types, the RIP Request and RIP

Response, both of which are sent using the User Datagram Protocol (UDP). RIP

Response messages, despite their name, are used both for routine periodic routing

table updates as well as to reply to RIP Request messages. Requests are sent only in

special circumstances, such as when a router first joins a network.

Preventing Stale Information: The Timeout Timer

When a router receives routing information and enters it into its routing table, that infor-

mation cannot be considered valid indefinitely. In our example in the previous topic,

suppose that after Router B installs a route to Network 1 through Router A, the link to

between RA and N2 fails. Once this happens, N1 is no longer reachable from RB, but RB

has a route indicating it can reach Network 1.

To prevent this problem, routes are only kept in the routing table for a limited amount of

time. A special Timeout timer is started whenever a route is installed in the routing table.

Whenever the router receives another RIP Response with information about that route, the

route is considered “refreshed” and its Timeout timer is reset. As long as the route

continues to be refreshed, the timer will never expire.

If, however, RIP Responses containing that route stop arriving, the timer will eventually

expire. When this happens, the route is marked for deletion, by setting the distance for the

route to 16 (which you may recall is RIP infinity and indicates an unreachable network). The

default value for the Timeout timer is usually 180 seconds. This allows several periodic

updates of a route to be missed before a router will conclude that the route is no longer

reachable.

Removing Stale Information: The Garbage-Collection Timer

When a route is marked for deletion, a new Garbage-Collection timer is also started.

“Garbage collection” is a computer industry phrase for a task that looks for deleted or invalid

information and cleans it up. Thus, this is a timer that counts a number of seconds before

the newly invalid route will be actually removed from the table. The default value for this

timer is 120 seconds.

The reason for using this two-stage removal method is to give the router that declared the

route no longer reachable a chance to propagate this information to other routers. Until the

Garbage-Collection timer expires, the router will include that route, with the “unreachable”

metric of 16 hops, in its own RIP Responses, so other routers are informed of the problem

with that route. When the timer expires the route is deleted. If during the garbage collection

period a new RIP Response for the route is received, then as you might expect the deletion

process is aborted: the Garbage-Collection timer is cleared, the route is marked as valid

again, and a new Timeout timer starts.

Triggered Updates

In addition to the two situations already described where an RIP Response is sent—in reply

to an RIP Request and on expiration of the 30-second timer—an RIP Response is also sent

out when a route changes. This action, an enhancement to basic RIP operation called a

triggered update, is intended to ensure that information about route changes is propagated

as fast as possible across the internetwork, to help reduce the “slow convergence” problem

in RIP. For example, in the case we just saw where a route timed out and the Garbage-

Collection timer was started, a triggered update would be sent out about the now-invalid

route immediately. This is described in more detail in the topic on RIP special features.

RIP Protocol Limitations and Problems

The simplicity of the Routing Information Protocol is often given as the main reason for its

popularity; I certainly have mentioned this enough times in this section. Simplicity is great

most of the time, but an unfortunate “price” of simplicity in too many cases is that problems

crop up, usually in unusual cases or special situations. And so it is with RIP: the straight-

forward distance-vector algorithm and operation mechanism work well most of the time, but

they have some important weaknesses. We need to examine these problems to understand

both the limitations of RIP and some of the complexities that have been added to the

protocol to resolve them.

Problems With RIP’s Basic Algorithm and Implementation

The most important area where we find serious issues with RIP is with the basic function of

the distance-vector algorithm described earlier in this section, and the way that messages

are used to implement it. The are four main problems here: slow convergence, routing

loops, “counting to infinity” and “small infinity”.

Slow Convergence

The distance-vector algorithm is designed so that all routers share all their routing infor-

mation regularly. Over time then, all routers eventually end up with the same information

about the location of networks and which are the best routes to use to reach them. This is

called convergence. Unfortunately, the basic RIP algorithm is rather slow to achieve conver-

gence. It takes a long time for all routers to get the same information, and in particular, it

takes a long time for information about topology changes to propagate.

Consider the worst-case situation of two networks separated by 15 routers. Since routers

normally send RIP Response messages only every 30 seconds, a change to one of this pair

of networks might not be seen by the router nearest the other one until many minutes have

elapsed—an eternity in networking terms.

The slow convergence problem is even more pronounced when it comes to the propagation

of route failures. Failure of a route is only detected through the expiration of the 180-second

Timeout timer, so that adds up to three minutes more delay before convergence can even

begin.

Routing Loops

A routing loop occurs when Router A has an entry telling it to send datagrams for Network 1

to Router B, and Router B has an entry saying that datagrams for Network 1 should be sent

to Router A. Larger loops can also exist: Router A says to send to B, which says to send to

C, which says to send to A.

While under normal circumstances these loops should not occur, they can happen in

special situations. RIP does not include any specific mechanism to detect or prevent routing

loops; the best it can do is try to avoid them.

“Counting To Infinity”

A special case of slow convergence can lead to a routing loop situation where one router

passes bad information to another router, which sends more bad information to another

router and so on. This causes a situation where the protocol is sometimes described as

unstable.; the problem is called counting to infinity for reasons we will soon see.

To understand how this happens, let's modify the example we looked at in the topic

describing the RIP algorithm (you may find it helpful to refer to Figure 174 as you follow this

discussion). Suppose that the internetwork is operating properly for a while. Router B has

an entry indicating it can reach Network 1 through Router A at a cost of 2. Now, say the link

from Network 1 to Router A fails. After the Timeout timer for Network 1 expires on Router A,

RA will change the metric for N1 to 16 to indicate that it is unreachable. In the absence of

any mechanism to force RA to immediately inform other routers of this failure, they will

remain “in the dark”. Router B will continue to think it can reach Network 1 through Router

Now, suppose RB's regular 30 second timer goes off before RA's next broadcast. RB will

send its normal routing table, which contains a route to Network 1 at a cost of 2. Router

A will see this and say “Hey, look, Router B has a route to Network 1 with a cost of 2! That

means I can get there with a cost of 3, which sure beats my current cost of 16; let's use

that!” So, Router A installs this route and cancels its Timeout timer. Of course, this is bogus

information—Router A doesn't realize that Router B's claim of being able to reach Network

1 was based on old information from Router A itself!

It only gets worse from there. When it is time for Router A's regular routing table update, it

will broadcast a route to Network 1 with a cost of 3. Now, Router B will then see this and say

“Hmm. Well, my route to Network 1 is through Router A. Router A was saying before that its

cost was 1, but now it says the cost is 3. That means I have to change my cost to 4”.

RB will later send back to RA, and back and forth they will go, each incrementing the cost

two at a time. This won't stop until the value of “infinity” (16) is hit—thus the name counting

to infinity. At this point both routers will finally agree that Network 1 is unreachable, but as

you can see, it takes a long time for it to happen.

Figure 174: The RIP “Counting To Infinity” Problem

This composite diagram shows part of the autonomous system illustrated in Figure 172. The top panel (#1)

shows the normal state of the network, with RB able to reach N1 through RA at a cost of 2. In #2, the link

between RA and N1 is broken. RA changes its cost to reach N1 to 16 (RIP infinity). In #3, Before RA can send

out this update to RB, it receives a routine RIP message from RB indicating that N1 can be reached for a cost

of 2. RA is then fooled into thinking it can use RB as an alternate route to N1, even though RB’s information

originally came from RA in the first place. In #4, RA then sends this bogus information out, which is received

by RB in #5. RB then increases its cost to 4, and on its next cycle will send this to RA, which will increase its

cost to 5, and so on. This cycle will continue, with both routers “counting to infinity” (16).

{N1,1}

{N1,RA,2}

{N1,16}

{N1,RA,2}

{N1,2} {N1,2}

{N1,RB,3}

{N1,RA,2}

{N1,2}

{N1,RB,3}

{N1,RA,2}

{N1,3}

{N1,RB,3}

{N1,RA,4}

{N1,3}

“Small Infinity”

The use of a relatively small value of “infinity” limits the slow convergence problem. Even in

a situation where we “count to infinity” as we just saw, the total amount of time elapsed is at

least manageable; imagine if “infinity” were defined as say, 1000! Unfortunately, the

drawback of this is that it limits the size of the internetwork that can be used for RIP.

Many people balk at the limit of a span of 15 routers in RIP, but to be honest I think it is

much ado about, well, if not nothing, then at least “nothing much”. The 15 value is not a limit

on the total number of routers you can use, just on the number of routers between any two

networks. Consider that most internetworks are set up hierarchically; even if you have a

rather complex four-level hierarchy you wouldn't be close to the 15-router limit. In fact, you

could create a huge autonomous system with thousands of routers without having more

than 15 routers between any two devices. So this is only a limitation for the very largest of

autonomous systems.

On the other hand, RIP’s need to send out its entire routing table many times each hour

makes it a potentially poor choice for a large internetwork regardless of the “infinity=16”

issue. In an internetwork with many routers, the amount of traffic RIP generates can

become excessive.

Key Concept: One of the most important problems with the operation of RIP is slow

convergence, which describes the fact that it can take a long time for information

about changes to a network to propagate between routers. One specific instance of

this problem is the counting to infinity problem, in which out-of-date information causes

many bogus RIP messages to be exchanged between routers about an unreachable

network.

To be fair, these problems are mostly general to distance-vector routing algorithms and not

RIP in particular. Some of them are corrected through the implementation of specific

changes to the algorithm or the rules under which RIP messages are sent, as described in

the next topic. According to RFC 2453, there was actually a proposal to increase RIP's

“infinity” to a number larger than 16, but this would have caused compatibility problems with

older devices (which would view any route with a metric of 16 or higher as unreachable) so

it was rejected.

Problems With RIP's Metric

In addition to these concerns with the algorithm itself, RIP is also often criticized because of

its choice of metric. There are two related issues here:

☯ Hop Count As A Distance Metric: Simply put, hop count is a poor metric of the cost

of sending a datagram between two networks. I believe the use of hop count as the

metric in RIP is partially due to the desire for simplicity (it's easy to make the protocol

work when hop count is all the routers need to consider) and partially an artifact of RIP

being a 20-plus-year-old protocol. Decades ago computers were slow, so each time a

datagram passed through a router there was probably a significant delay. Hop count

was not a perfect metric even then, but I think it had more correspondence with how

long it took to move a datagram across an internetwork than it does today.

Modern routers are lightning fast, making hop count a flawed way of measuring

network distance. The number of hops taken often has no correlation with the actual

amount of time it takes to move data across a route. To take an extreme case,

consider two networks that are connected by a direct dial-up telephone networking link

using 56K modems, and also connected by a sequence of three routers using high-

speed DS-3 lines. RIP would consider the 56K link a better route because it has fewer

hops, even though clearly it is much slower.

☯ Lack Of Support For Dynamic (Real-Time) Metrics: Even if RIP were to use a more

meaningful metric than hop count, the algorithm requires that the metric be fixed for

each link. There is no way to have RIP calculate the best route based on real-time

data about various links the way protocols like OSPF do.

These problems are built into RIP and cannot be resolved easily. Interestingly, some RIP

implementations apparently do let administrators “fudge” certain routes to compensate for

the limitations of the hop count metric. For example, the routers on either end of the 56K

link mentioned above could be configured so they considered the 56K link to have a hop

count of 10 instead of 1. This would cause any routes using the link to be more “expensive”

than the DS-3 path. This is clever, but hardly an elegant or general solution.

Note: In addition to the rather long list of problems above, there were also some

specific issues with the first version of RIP. Some of the more important of these

include lack of support for CIDR, lack of authentication, and the performance

reduction caused by the use of broadcasts for messaging. These were mostly addressed

through extensions in RIP-2.

RIP Special Features For Resolving RIP Algorithm Problems

The simplicity of the Routing Information Protocol is its most attractive quality, but also

leads to certain problems with how it operates. Most of these limitations are related to the

basic algorithm used for determining routes, and the method of message passing used to

implement the algorithm. In order for RIP to be a useful protocol, it was necessary that

some of these issues be addressed, in the form of changes to the basic RIP algorithm and

operational scheme we explored earlier in this section.

The solution to problems that arise due to RIP being too simple is to add complexity, in the

form of features that add more intelligence to the way that RIP operates. Let’s take a look at

four of these: split horizon, split horizon with poisoned reverse, triggered updates and hold-

down.

Split Horizon

The “counting to infinity” problem is one of the most serious issues with the basic RIP

algorithm. In the example in the previous topic, the cause of the problem is immediately

obvious: after Network 1 fails and Router A notices it go down, Router B “tricks” Router A

into thinking it has an alternate path to Network 1 by sending Router A a route adver-

tisement to N1.

If you think about it, it doesn't really make sense—under any circumstances—to have

Router B send an advertisement to Router A about a network that Router B can only access

through Router A in the first place. In the case where the route fails it causes this problem,

which is obviously a good reason not do it. But even when the route is operational, what is

the point of Router B telling Router A about it? Router A already has a shorter connection to

the network and will therefore never send traffic intended for Network 1 to Router B

anyway.

Clearly, the best solution is simply to have Router B not include any mention of the route to

Network 1 in any RIP Response messages it sends to Router A. We can generalize this by

adding a new rule to RIP operation: when a router sends out an RIP Response on any of

the networks to which it is connected, it omits any route information that was originally

learned from that network. This feature is called split horizon, since the router effectively

splits its view of the internetwork, sending different information on certain links than on

others.

With this new rule, let's consider the behavior of Router B. It has an interface on Network 2,

which it shares with Router A. It will therefore not include any information on routes it origi-

nally obtained from Router A when sending on N2. This will prevent the “counting to infinity”

loop we saw in the previous topic. Similarly, since Router D is on Network 3, Router B will

not send any information about routes it got from Router D when sending on Network 3.

Note, however, that split horizon may not always solve the “counting to infinity” problem,

especially in the case where multiple routers are connected indirectly. The classic example

would be three routers configured in a triangle. In this situation, problems may still result

due to data that is propagated in two directions between any two routers. In this case, the

“hold down” feature may be of assistance (see below).

Split Horizon With Poisoned Reverse

This is an enhancement of the basic split horizon feature. Instead of omitting routes learned

from a particular interface when sending RIP Response messages on that interface, we

include those routes but set their metric to “RIP infinity”, 16. So in the example above,

Router B would include the route to Network 1 in its transmissions on Network 2, but it

would say the cost to reach N1 was 16, instead of its real cost (which is 2).

The “poisoned reverse” refers to the fact that we are poisoning the routes that we want to

make sure routers on that interface don't use. Router A will see Router B advertise Network

1 but with a cost of 16, which serves as an explicit message to Router A: “there is

absolutely no way for you to get to Network 1 through Router B”. This provides more

insurance than the regular split horizon feature, because if the link from Router A to

Network 1 dies as we described in the previous topic, Router A will know for certain that it

can't try to get a new route through Router B. Figure 175 shows how split horizon with

poisoned reverse works.

This technique also works in normal circumstances (meaning, when there is no issue such

as a broken link to a network). In that case, Router A will receive updates from RB with a

cost of 16 on a periodic basis, but RA will never try to reach Network 1 through Router B

anyway, since it is directly connected to Network 1 (cost of 1).

Figure 175: RIP Problem Solving Using Split Horizon With Poisoned Reverse

The top panel in this diagram (#1) shows the same example as in Figure 174. In #2, as before, the link

between RA and N1 is broken, just as RB is ready to send out its routine update. However, the split horizon

with poisoned reverse feature means it sends different messages on its two links; on the network that

connects it to RA, it sends a route advertisement with a cost of 16. In #3, Router A receives this, which it will

discard, ensuring no counting to infinity problem occurs. On RA’s next cycle it will update RB to tell it that N1 is

no longer reachable.

{N1,1}

{N1,RA,2}

{N1,16}

{N1,RA,2}

{N1,16} {N1,2}

{N1,16}

{N1,RA,2}

{N1,16}