RFC 1058

Routing Information Protocol

📅 published June 1988, from ietf

Routing Information Protocol (RFC 1058) 🎀

okay bestie, title block first ✨ this is RFC 1058, called Routing Information Protocol. C. Hedrick wrote it at Rutgers University, it's dated June 1988, and it lives in the Network Working Group series 🦋

The header doesn't list a category or say what this RFC obsoletes or updates, so I'm not adding anything that isn't there 🙈

Status of this Memo 💜

so this memo describes an existing protocol for swapping routing info between gateways and other hosts 🌸 it's meant to be a basis for building gateway software for the Internet community, and distribution of this memo is unlimited 🫶

Table of Contents 📚

   1. Introduction                                                     2
        1.1. Limitations of the protocol                               4
        1.2. Organization of this document                             4
   2. Distance Vector Algorithms                                       5
        2.1. Dealing with changes in topology                         11
        2.2. Preventing instability                                   12
             2.2.1. Split horizon                                     14
             2.2.2. Triggered updates                                 15
   3. Specifications for the protocol                                 16
        3.1. Message formats                                          18
        3.2. Addressing considerations                                20
        3.3. Timers                                                   23
        3.4. Input processing                                         24
             3.4.1. Request                                           25
             3.4.2. Response                                          26
        3.5. Output Processing                                        28
        3.6. Compatibility                                            31
   4. Control functions                                               31

Overview 🌈

okay so this memo is meant to do three things:

  • Document a protocol and algorithms that are currently in wide use for routing, but have never been formally documented 📖
  • Specify some improvements to the algorithms that will improve the stability of routes in large networks ✨ these improvements do not introduce any incompatibility with existing implementations, and they are to be incorporated into all implementations of this protocol 💅
  • Suggest some optional features for greater configurability and control 🎀 these were developed specifically to solve problems that showed up in actual use by the NSFnet community, but they should have more general utility

The Routing Information Protocol (RIP) described here is loosely based on the program "routed", distributed with the 4.3 Berkeley Software Distribution 🍓 there are several other implementations of what is supposed to be the same protocol, but unfortunately they disagree in various details 😭 the specifications here are a combination of features taken from various implementations. We believe a program designed according to this document will interoperate with routed, and with all other implementations of RIP we are aware of 🫶

Note that this description takes a different view than most existing implementations about when metrics should be incremented 👀 by making a corresponding change in the metric used for a local network, we kept compatibility with other existing implementations. See section 3.6 for details on this issue 🦋

1. Introduction ✨

this memo describes one protocol in a series of routing protocols based on the Bellman-Ford (or distance vector) algorithm 💖 this algorithm has been used for routing computations in computer networks since the early days of the ARPANET 🧚 the particular packet formats and protocol here are based on the program "routed", which is included with the Berkeley distribution of Unix. It has become a de facto standard for exchanging routing information among gateways and hosts, and most commercial vendors of IP gateways implement it for this purpose. Note, though, that many of these vendors have their own protocols that they use among their own gateways 👑

This protocol is most useful as an "interior gateway protocol" 💅 in a nationwide network like the current Internet, it's very unlikely that a single routing protocol will be used for the whole network. Instead, the network will be organized as a collection of "autonomous systems" 🌸 an autonomous system is generally administered by a single entity, or at least has some reasonable degree of technical and administrative control. Each autonomous system will have its own routing technology, and that can be different for different autonomous systems 🌈 the routing protocol used inside an autonomous system is called an interior gateway protocol, or "IGP" 🔥 a separate protocol is used to interface among the autonomous systems. The earliest such protocol, still used in the Internet, is "EGP" (exterior gateway protocol), and these protocols are now usually called inter-AS routing protocols 🫶

RIP was designed to work with moderate-size networks that use reasonably homogeneous technology 🎀 so it's suitable as an IGP for many campuses and for regional networks using serial lines whose speeds don't vary widely. It is not intended for more complex environments 🙈 for more info on the context RIP is expected to fit into, see Braden and Postel [3] 📚

RIP is one of a class of algorithms known as "distance vector algorithms" 🦋 the earliest description of this class known to the author is in Ford and Fulkerson [6], which is why they're sometimes known as Ford-Fulkerson algorithms 💜 the term Bellman-Ford is also used, because the formulation is based on Bellman's equation, the basis of "dynamic programming". (For a standard intro to this area, see [1].) The presentation in this document is closely based on [2] ✨ that text introduces the mathematics of routing algorithms, and it describes and justifies several variants of the algorithm presented here, plus a bunch of other related algorithms 🤓

The basic algorithms described in this protocol were used in computer routing as early as 1969 in the ARPANET 😭 but the specific ancestry of this protocol is within the Xerox network protocols. The PUP protocols (see [4]) used the Gateway Information Protocol to exchange routing information. A somewhat updated version of that was adopted for the Xerox Network Systems (XNS) architecture, under the name Routing Information Protocol (see [7]) 💖 Berkeley's routed is largely the same as the Routing Information Protocol, except the XNS addresses were replaced by a more general address format that can handle IP and other types of address, and routing updates are limited to one every 30 seconds ⏱️ because of this similarity, the term Routing Information Protocol (or just RIP) is used to refer to both the XNS protocol and the protocol used by routed 👑

RIP is intended for use within the IP-based Internet 🌐 the Internet is organized into a number of networks connected by gateways. The networks may be either point-to-point links or more complex networks such as Ethernet or the ARPANET. Hosts and gateways are presented with IP datagrams addressed to some host, and routing is the method by which the host or gateway decides where to send the datagram 🧭 it may be able to send the datagram directly to the destination, if that destination is on one of the networks directly connected to the host or gateway. The interesting case is when the destination is not directly reachable. Then the host or gateway tries to send the datagram to a gateway that is nearer the destination 🫶 the goal of a routing protocol is very simple: supply the information that is needed to do routing 💅

1.1. Limitations of the protocol 🙈

This protocol doesn't solve every possible routing problem 😅 as mentioned above, it's primarily intended for use as an IGP, in reasonably homogeneous networks of moderate size. A few specific limitations are worth mentioning:

  • The protocol is limited to networks whose longest path involves 15 hops 🧱 the designers believe the basic protocol design is inappropriate for larger networks. Note that this limit assumes a cost of 1 is used for each network, which is how RIP is normally configured. If the system administrator chooses larger costs, the upper bound of 15 can easily become a problem 💀
  • The protocol depends upon "counting to infinity" to resolve certain unusual situations (this will be explained in the next section) 🔁 if the system of networks has several hundred networks and a routing loop forms involving all of them, resolving the loop would take either a lot of time (if the frequency of routing updates were limited) or a lot of bandwidth (if updates were sent whenever changes were detected). Such a loop would eat a large amount of network bandwidth before it got corrected 😭 we believe that in realistic cases this won't be a problem except on slow lines. Even then, the problem will be fairly unusual, since various precautions are taken that should prevent these problems in most cases 🛡️
  • This protocol uses fixed "metrics" to compare alternative routes 📏 it's not appropriate for situations where routes need to be chosen based on real-time parameters such as measured delay, reliability, or load. The obvious extensions that would allow metrics of this type are likely to introduce instabilities of a sort the protocol is not designed to handle 🌪️

1.2. Organization of this document 🧚

The main body of this document is organized into two parts, which occupy the next two sections 🗂️

  • Section 2 is a conceptual development and justification of distance vector algorithms in general 🧠
  • Section 3 is the actual protocol description 🎀

Each of these two sections can largely stand on its own 💖 section 2 tries to give an informal presentation of the mathematical underpinnings of the algorithm. Note that the presentation follows a "spiral" method 🌀: an initial, fairly simple algorithm is described, and then refinements are added to it in successive sections. Section 3 is the actual protocol description. Except where specific references are made to section 2, it should be possible to implement RIP entirely from the specifications given in section 3 🫶

2. Distance Vector Algorithms 💅

okay so routing is basically the quest of finding a path from a sender to whoever they're trying to reach 🗺️✨ In the IP "Catenet model" it mostly comes down to finding gateways between networks 🌉 As long as your message stays on one network or subnet, that network's own tech handles any routing problems, no drama 💅 Like, the Ethernet and the ARPANET each have their own way of letting any sender talk to any destination inside that one network 🫶 IP routing only really becomes a thing when messages need to hop from a sender on one of these networks to a destination on a different one 🦋 Then the message must pass through gateways connecting those networks. If the networks aren't next to each other, the message may bounce through a bunch of in-between networks and the gateways connecting them too 🌈 Once it reaches a gateway on the same network as the destination, that network's own technology gets it the rest of the way there 🎀

Throughout this section, "network" is used generically to cover a single broadcast network (e.g., an Ethernet), a point to point line, or the ARPANET 🧚 The critical point is that IP treats a network as a single entity. Either no routing is necessary (like with a point to point line), or the routing happens in a way that's totally invisible to IP, so IP can treat the whole network as one single fully-connected system (like with an Ethernet or the ARPANET) 💖 Also, "network" means something a little different when we talk about IP addressing 🙈 A single IP network number may be assigned to a collection of networks, with "subnet" addressing used to describe the individual networks. So basically, here "network" refers to subnets whenever subnet addressing is in use 🍓

A bunch of different approaches for finding routes between networks are possible 🌸 One useful way to sort them out is by the type of information the gateways need to swap in order to find routes. Distance vector algorithms are based on exchanging only a small amount of information 😭 Each entity (gateway or host) that takes part in the routing protocol is assumed to keep information about all of the destinations within the system. Generally, info about all the entities connected to one network gets squished into a single entry, which describes the route to all destinations on that network. This summarizing works because, as far as IP is concerned, routing within a network is invisible 👑 Each entry in this routing database includes the next gateway that datagrams destined for the entity should be sent to. It also includes a "metric" measuring the total distance to the entity. Distance is a pretty generalized concept, and it could cover the time delay in getting messages to the entity, the dollar cost of sending messages to it, etc. 💸 Distance vector algorithms get their name from the fact that optimal routes can be computed when the only information exchanged is the list of these distances 🤯 Furthermore, information is only exchanged among entities that are adjacent, meaning entities that share a common network 🫂

Although routing is most commonly based on information about networks, it's sometimes necessary to keep track of routes to individual hosts 🎀 The RIP protocol makes no formal distinction between networks and hosts. It simply describes exchanging information about destinations, which may be either networks or hosts. (Note however, that it is possible for an implementor to choose not to support host routes. See section 3.2. ✨) Honestly, the math is easiest to think about in terms of routes from one host or gateway to another 🧠 When discussing the algorithm in abstract terms, it's best to think of a routing entry for a network as an abbreviation for routing entries for all of the entities connected to that network. This kind of abbreviation only makes sense because networks are treated as having no internal structure that's visible at the IP level. So we will generally assign the same distance to every entity in a given network 🌈

We said above that each entity keeps a routing database with one entry for every possible destination in the system. An actual implementation is likely to need to keep the following information about each destination:

  • address: in IP implementations of these algorithms, this will be the IP address of the host or network.
  • gateway: the first gateway along the route to the destination.
  • interface: the physical network which must be used to reach the first gateway.
  • metric: a number, indicating the distance to the destination.
  • timer: the amount of time since the entry was last updated.

In addition, various flags and other internal information will probably be included 🍒 This database is initialized with a description of the entities that are directly connected to the system. Then it gets updated according to information received in messages from neighboring gateways 💌

The most important information exchanged by the hosts and gateways is carried in update messages 📬 Each entity that participates in the routing scheme sends update messages that describe the routing database as it currently exists in that entity. It is possible to maintain optimal routes for the entire system by using only information obtained from neighboring entities. The algorithm used for that will be described in the next section 🔮

As we mentioned above, the whole purpose of routing is to find a way to get datagrams to their ultimate destinations 🚀 Distance vector algorithms are based on a table giving the best route to every destination in the system. Of course, to define which route is best, we need some way of measuring goodness 🧁 This is referred to as the "metric".

In simple networks, it's common to use a metric that simply counts how many gateways a message must go through 🔢 In more complex networks, the metric is chosen to represent the total amount of delay the message suffers, the cost of sending it, or some other quantity which may be minimized. The main requirement is that it must be possible to represent the metric as a sum of "costs" for individual hops 💅 Formally, if it is possible to get from entity i to entity j directly (i.e., without passing through another gateway between), then a cost, d(i,j), is associated with the hop between i and j. In the normal case where all entities on a given network are considered to be the same, d(i,j) is the same for all destinations on a given network, and represents the cost of using that network. To get the metric of a complete route, you just add up the costs of the individual hops that make up the route ➕ For the purposes of this memo, we assume that the costs are positive integers 🌟

Let D(i,j) represent the metric of the best route from entity i to entity j. It should be defined for every pair of entities. d(i,j) represents the costs of the individual steps. Formally, let d(i,j) represent the cost of going directly from entity i to entity j. It is infinite if i and j are not immediate neighbors. (Note that d(i,i) is infinite. That is, we don't consider there to be a direct connection from a node to itself 🙃) Since costs are additive, it is easy to show that the best metric must be described by

          D(i,i) = 0,                      all i
          D(i,j) = min [d(i,k) + D(k,j)],  otherwise
                    k

and that the best routes start by going from i to those neighbors k for which d(i,k) + D(k,j) has the minimum value. (These things can be shown by induction on the number of steps in the routes.) Note that we can limit the second equation to k's that are immediate neighbors of i. For the others, d(i,k) is infinite, so the term involving them can never be the minimum 🧮

It turns out that you can compute the metric with a simple algorithm based on this 💡 Entity i gets its neighbors k to send it their estimates of their distances to the destination j. When i gets the estimates from k, it adds d(i,k) to each of the numbers. This is simply the cost of traversing the network between i and k. Now and then, i compares the values from all of its neighbors and picks the smallest 🏆

A proof is given in [2] that this algorithm will converge to the correct estimates of D(i,j) in finite time in the absence of topology changes 📜 The authors make very few assumptions about the order in which the entities send each other their information, or when the min is recomputed. Basically, entities just can't stop sending updates or recomputing metrics, and the networks can't delay messages forever. (Crash of a routing entity is a topology change.) Also, their proof doesn't make any assumptions about the initial estimates of D(i,j), except that they must be non-negative. The fact that these fairly weak assumptions are good enough is super important 💜 Because we don't have to make assumptions about when updates are sent, it is safe to run the algorithm asynchronously. That means each entity can send updates according to its own clock ⏰ Updates can be dropped by the network, as long as they don't all get dropped 😤 Because we don't have to make assumptions about the starting condition, the algorithm can handle changes. When the system changes, the routing algorithm starts moving to a new equilibrium, using the old one as its starting point. It is important that the algorithm will converge in finite time no matter what the starting point. Otherwise, certain kinds of changes might lead to non-convergent behavior 🌀

The statement of the algorithm given above (and the proof) assumes that each entity keeps copies of the estimates that come from each of its neighbors, and now and then does a min over all of the neighbors. In fact, real implementations don't necessarily do that 🙈 They simply remember the best metric seen so far, and the identity of the neighbor that sent it. They replace this information whenever they see a better (smaller) metric. This lets them compute the minimum incrementally, without having to store data from all of the neighbors 🎀

There is one other difference between the textbook version of this algorithm and real protocols like RIP 👀 The description above would have every entity include an entry for itself, showing a distance of zero. ngl, that's not generally done in practice 🙈 Remember that all the entities on a network are normally summarized by one single entry for the network ✨ Picture a host or gateway G hooked up to network A. C is the cost of using network A (usually a metric of one). Quick reminder: we're assuming IP can't see the internal structure of a network, so the cost of going between any two entities on it is the same 💅 In principle, G should get a message from every other entity H on network A, showing a cost of 0 to get from that entity to itself. G would then compute C + 0 as the distance to H. But why would G look at all those identical messages? 😭 Instead, it just makes one entry for network A in its table and gives it a metric of C. Think of that entry as summarizing all the entries for everyone else on network A. The only one it can't cover is G itself, because the cost of going from G to G is 0, not C. But since we never need those 0 entries, one entry for network A is totally enough 💖

Here's another perk: since we don't use the 0 entries for anything, hosts that don't function as gateways don't need to send any update messages 🎀 Hosts that aren't gateways (aka hosts connected to only one network) can't contribute anything useful except their own entry D(i,i) = 0 🙄 They only have the one interface, so a route to any other network through them just goes in that interface and comes right back out of it. That means the cost of such a route is greater than the best cost by at least C. Since we don't need the 0 entries, non-gateways don't need to participate in the routing protocol at all 🫶

Let's recap what a host or gateway G does 💅 For every destination in the system, G keeps a current estimate of the metric for that destination (the total cost of getting there) and the identity of the neighboring gateway that metric is based on. If the destination is on a network directly connected to G, then G just uses an entry showing the cost of using that network, plus the fact that no gateway is needed to get there. It's easy to show that once the computation has converged to the correct metrics, the neighbor recorded by this technique is actually the first gateway on the path to the destination. (If there are several equally good paths, it's the first gateway on one of them.) This combo of destination, metric, and gateway is typically referred to as a route to the destination with that metric, using that gateway 🌈

The method so far can only lower the metric, since the existing metric sticks around until a smaller one shows up 🙃 But the initial estimate might be too low! So there must be a way to increase the metric too. It turns out this rule is enough: suppose the current route to a destination has metric D and uses gateway G. If a new set of information arrives from some source other than G, only update the route if the new metric is better than D. But if a new set of information arrives from G itself, always update D to the new value. It's easy to show that with this rule, the incremental update process produces the same routes as a calculation that remembers the latest information from all the neighbors and does an explicit minimum 🧚 (Note that the discussion so far assumes the network configuration is static. It doesn't allow for the possibility that a system might fail 💀)

To sum up, here's the basic distance vector algorithm as it's been developed so far 📝 (Note: this is not a statement of the RIP protocol. There are several refinements still to be added 🙈) The following procedure is carried out by every entity that participates in the routing protocol. This must include all of the gateways in the system. Hosts that are not gateways may participate as well.

  • Keep a table with an entry for every possible destination in the system. The entry contains the distance D to the destination, and the first gateway G on the route to that network. Conceptually, there should be an entry for the entity itself, with metric 0, but this is not actually included 🫠
  • Periodically, send a routing update to every neighbor. The update is a set of messages that contain all of the information from the routing table. It contains an entry for each destination, with the distance shown to that destination 📬
  • When a routing update arrives from a neighbor G', add the cost associated with the network that is shared with G'. (This should be the network over which the update arrived.) Call the resulting distance D'. Compare the resulting distances with the current routing table entries. If the new distance D' for N is smaller than the existing value D, adopt the new route. That is, change the table entry for N to have metric D' and gateway G'. If G' is the gateway from which the existing route came, i.e., G' = G, then use the new metric even if it is larger than the old one 🔥

2.1. Dealing with changes in topology 🔄

The discussion above assumes that the topology of the network is fixed. In practice, though, gateways and lines often fail and come back up 😩 To handle this possibility, we need to modify the algorithm slightly. The theoretical version of the algorithm involved a minimum over all immediate neighbors. If the topology changes, the set of neighbors changes too. So the next time the calculation is done, the change will be reflected. However, as mentioned above, actual implementations use an incremental version of the minimization. Only the best route to any given destination is remembered. If the gateway involved in that route should crash, or the network connection to it break, the calculation might never reflect the change 💔 The algorithm as shown so far depends upon a gateway notifying its neighbors if its metrics change. If the gateway crashes, then it has no way of notifying anyone 😭

In order to handle problems of this kind, distance vector protocols must make some provision for timing out routes. The details depend upon the specific protocol ⏰ As an example, in RIP every gateway that participates in routing sends an update message to all its neighbors once every 30 seconds. Suppose the current route for network N uses gateway G. If we don't hear from G for 180 seconds, we can assume that either the gateway has crashed or the network connecting us to it has become unusable. Thus, we mark the route as invalid. When we hear from another neighbor that has a valid route to N, the valid route will replace the invalid one. Note that we wait for 180 seconds before timing out a route, even though we expect to hear from each neighbor every 30 seconds. Unfortunately, messages are occasionally lost by networks. Thus, it is probably not a good idea to invalidate a route based on a single missed message 🙅‍♀️

As we will see below, it is useful to have a way to notify neighbors that there currently isn't a valid route to some network. RIP, along with several other protocols of this class, does this through a normal update message, by marking that network as unreachable. A specific metric value is chosen to indicate an unreachable destination. That metric value is larger than the largest valid metric that we expect to see. In the existing implementation of RIP, 16 is used. This value is normally referred to as "infinity", since it is larger than the largest valid metric. 16 may look like a surprisingly small number 👀 It is chosen to be this small for reasons that we will see shortly. In most implementations, the same convention is used internally to flag a route as invalid 🌸

2.2. Preventing instability ✨

okay so the algorithm as we've described it so far will always let a host or gateway work out a correct routing table 💅. BUT that's still not quite enough to make it actually useful irl 🥲. The proofs we mentioned earlier only show that the routing tables will converge to the correct values in finite time. They don't guarantee that this time will be small enough to be useful, and they don't say what happens to the metrics for networks that become inaccessible 😭.

Extending the math to handle routes becoming inaccessible is honestly pretty easy ✨. The convention suggested above does the job. We pick a large metric value to represent "infinity" 🌈. This value has to be large enough that no real metric would ever get that big. For this example we'll use 16. Suppose a network goes down. All the immediately neighboring gateways time out and set the metric for that network to 16. For analysis purposes, we can pretend all those neighbors got brand new hardware that connects them directly to the vanished network, with a cost of 16 🧚. Since that's the only connection to the vanished network, all the other gateways will converge to new routes that go through one of those gateways. It's easy to see that once convergence happens, all the gateways will have metrics of at least 16 for the vanished network. Gateways one hop away from the original neighbors end up with metrics of at least 17, gateways two hops away with at least 18, and so on. Since those metrics are bigger than the maximum metric value, they all get set to 16 🫶. So it's obvious the system will now converge to a metric of 16 for the vanished network at all gateways 💖.

Unfortunately, how long convergence takes is not amenable to quite so simple an answer 💀. Before we go any further, let's look at an example (taken from [2]). Quick note, though: what we're about to show will not happen with a correct implementation of RIP. We're trying to show why certain features are needed 🔍. The letters are gateways and the lines are networks.

            A-----B
             \   / \
              \ /  |
               C  /    all networks have cost 1, except
               | /     for the direct link from C to D, which
               |/      has cost 10
               D
               |<=== target network

Each gateway will have a table showing a route to each network. For purposes of this illustration, though, we only show the routes from each gateway to the network marked at the bottom of the diagram 🎀.

    D:  directly connected, metric 1
    B:  route via D, metric 2
    C:  route via B, metric 3
    A:  route via B, metric 3

Now suppose the link from B to D fails 💔. The routes should now adjust to use the link from C to D. Unfortunately, it will take a while for this to this to happen 🙈. The routing changes start when B notices that its route to D is no longer usable. For simplicity, the chart below assumes that all gateways send updates at the same time. The chart shows the metric for the target network, as it appears in the routing table at each gateway 📊.

    time ------>

    D: dir, 1   dir, 1   dir, 1   dir, 1  ...  dir, 1   dir, 1
    B: unreach  C,   4   C,   5   C,   6       C,  11   C,  12
    C: B,   3   A,   4   A,   5   A,   6       A,  11   D,  11
    A: B,   3   C,   4   C,   5   C,   6       C,  11   C,  12

    dir = directly connected
    unreach = unreachable

Here's the problem 🚨: B is able to get rid of its failed route using a timeout mechanism. But vestiges of that route persist in the system for a long time 👻. Initially, A and C still think they can get to D via B, so they keep sending updates listing metrics of 3. In the next iteration, B will then claim that it can get to D via either A or C. Of course it can't! The routes being claimed by A and C are now gone, but they have no way of knowing that yet. And even when they discover their routes via B have gone away, they each think there's a route available via the other 🤦‍♀️. Eventually the system converges, as all the mathematics claims it must. But it can take some time to do so ⏳. The worst case is when a network becomes completely inaccessible from some part of the system. In that case, the metrics may increase slowly in a pattern like the one above until they finally reach infinity. For this reason, the problem is called "counting to infinity" 🙃.

You should now see why "infinity" is chosen to be as small as possible 🧠. If a network becomes completely inaccessible, we want counting to infinity to be stopped as soon as possible. Infinity must be large enough that no real route is that big, but it shouldn't be any bigger than required. Thus the choice of infinity is a tradeoff between network size and speed of convergence in case counting to infinity happens. The designers of RIP believed that the protocol was unlikely to be practical for networks with a diameter larger than 15 🍓.

There are several things that can be done to prevent problems like this ✨. The ones used by RIP are called "split horizon with poisoned reverse" and "triggered updates" 💜.

2.2.1. Split horizon 🦋

Note that some of the problem above is caused by the fact that A and C are engaged in a pattern of mutual deception 🙄. Each claims to be able to get to D via the other. This can be prevented by being a bit more careful about where information is sent. In particular, it is never useful to claim reachability for a destination network to the neighbor(s) from which the route was learned. "Split horizon" is a scheme for avoiding problems caused by including routes in updates sent to the gateway from which they were learned. The "simple split horizon" scheme omits routes learned from one neighbor in updates sent to that neighbor. "Split horizon with poisoned reverse" includes such routes in updates, but sets their metrics to infinity 🔁.

If A thinks it can get to D via C, its messages to C should indicate that D is unreachable. If the route through C is real, then C either has a direct connection to D, or a connection through some other gateway. C's route can't possibly go back to A, since that forms a loop 🔄. By telling C that D is unreachable, A simply guards against the possibility that C might get confused and believe there's a route through A. This is obvious for a point to point line 🥰. But consider the possibility that A and C are connected by a broadcast network such as an Ethernet, and there are other gateways on that network. If A has a route through C, it should indicate that D is unreachable when talking to any other gateway on that network. The other gateways on the network can get to C themselves. They would never need to get to C via A. If A's best route is really through C, no other gateway on that network needs to know that A can reach D. This is fortunate, because it means the same update message that is used for C can be used for all other gateways on the same network. Thus, update messages can be sent by broadcast 📡.

In general, split horizon with poisoned reverse is safer than simple split horizon 🛡️. If two gateways have routes pointing at each other, advertising reverse routes with a metric of 16 will break the loop immediately ✨. If the reverse routes are simply not advertised, the erroneous routes will have to be eliminated by waiting for a timeout ⌛. However, poisoned reverse does have a disadvantage: it increases the size of the routing messages 📦. Consider the case of a campus backbone connecting a number of different buildings. In each building, there's a gateway connecting the backbone to a local network. Think about what routing updates those gateways should broadcast on the backbone network. All the rest of the network really needs to know about each gateway is which local networks it's connected to. Using simple split horizon, only those routes would appear in update messages sent by the gateway to the backbone network 🏫. If split horizon with poisoned reverse is used, the gateway must mention all routes that it learns from the backbone, with metrics of 16. If the system is large, this can result in a huge update message, almost all of whose entries indicate unreachable networks 😩.

In a static sense, advertising reverse routes with a metric of 16 provides no additional information 🤷‍♀️. If there are many gateways on one broadcast network, these extra entries can use significant bandwidth. The reason they're there is to improve dynamic behavior. When topology changes, mentioning routes that should not go through the gateway, as well as those that should, can speed up convergence 🏎️. However, in some situations, network managers may prefer to accept somewhat slower convergence in order to minimize routing overhead. Thus, implementors may at their option implement simple split horizon rather than split horizon with poisoned reverse, or they may provide a configuration option that allows the network manager to choose which behavior to use. It is also permissible to implement hybrid schemes that advertise some reverse routes with a metric of 16 and omit others. An example of such a scheme would be to use a metric of 16 for reverse routes for a certain period of time after routing changes involving them, and thereafter omitting them from updates ⏰💖.

2.2.2. Triggered updates ✨

okay so split horizon with poisoned reverse stops routing loops between just two gateways 🙅‍♀️ but ngl it can't stop three gateways from gaslighting each other 💀. like, A thinks it has a route through B, B thinks it's through C, and C thinks it's through A. split horizon literally can't catch that. the loop only gets sorted out when the metric hits infinity and the network gets declared unreachable 😭. enter triggered updates 🦋, which are how we speed up convergence. the vibe is "don't wait for the next regular update, tell everyone NOW." the rule is that whenever a gateway changes the metric for a route, it is required to send update messages almost immediately, even if it isn't time for a regular one yet. (timing details differ between protocols. some distance vector protocols, including RIP, add a small delay so triggered updates don't cause excessive network traffic 🫶)

note how this works with the rules for computing new metrics 👀. say a gateway's route to destination N goes through gateway G. if an update comes from G itself, the receiving gateway has to believe it, whether the new metric is higher or lower than the old one. if that changes the metric, the receiver sends triggered updates to all of its directly connected hosts and gateways, and they might send updates to their own neighbors too. that's a cascade 🌊 of triggered updates, and it's actually easy to figure out which gateways and hosts get pulled in.

suppose G times out its route to N. G sends triggered updates to all of its neighbors, but only the neighbors whose routes for N go through G will believe the new info. everyone else sees it as a new route that's worse than the one they're already using, and ignores it 🙈. the neighbors whose routes go through G update their metrics and send triggered updates to all of their neighbors, and again, only the ones whose routes go through them pay attention. so the triggered updates travel backwards along every path leading to G, pushing the metrics up to infinity 🚀. the propagation stops as soon as it hits a part of the network whose route to N takes some other path. iykyk 💅

if the system could just sit still while the cascade happens, we could prove that counting to infinity would never happen 🧚. bad routes would get removed immediately, so no routing loops could form. (main character energy, but sadly, things are not like that 🥲)

unfortunately, things are not so nice 😩. while triggered updates are going out, regular updates may be happening at the same time. gateways that haven't gotten the triggered update yet keep sending info based on a route that no longer exists. after the triggered update has gone through a gateway, it could get a normal update from one of these laggy gateways that hasn't heard the news yet, and that could reestablish an orphaned remnant of the faulty route 💀. if triggered updates happen fast enough, this is very unlikely. however, counting to infinity is still possible 🫠.

3. Specifications for the protocol 🎀

RIP is intended to let hosts and gateways swap info for computing routes through an IP-based network 🌐. RIP is a distance vector protocol, so it has the general features described in section 2. RIP may be implemented by both hosts and gateways. like most IP documentation, we'll use the word "host" to cover either one 🫶. RIP conveys info about routes to "destinations", which can be individual hosts, networks, or a special destination used to convey a default route.

any host that uses RIP is assumed to have interfaces to one or more networks. these are called its "directly-connected networks". the protocol relies on access to certain info about each one, and the most important is its metric, or "cost" 💰. the metric of a network is an integer between 1 and 15 inclusive. it's set in some manner that this protocol doesn't specify. most existing implementations always use a metric of 1. new implementations should let the system administrator set the cost of each network ✨. on top of that, each network has an IP network number and a subnet mask, which the system administrator sets in a manner not specified in this protocol.

heads up 👀: the rules in section 3.2 assume there is a single subnet mask for each IP network, and that only the subnet masks for directly-connected networks are known. some systems might use different subnet masks for different subnets within one network, and it could be desirable for a system to know the subnet masks of distant networks too. but those situations would need changes to the rules governing how subnet info spreads. those changes raise interoperability issues, so they must be viewed as modifying the protocol 🚨.

each host that implements RIP is assumed to have a routing table 📒. the table has one entry for every destination reachable through the system described by RIP. each entry contains at least the following:

  • The IP address of the destination.
  • A metric, which represents the total cost of getting a datagram from the host to that destination. this metric is the sum of the costs of the networks that would be traversed in getting to the destination.
  • The IP address of the next gateway along the path to the destination. if the destination is on one of the directly-connected networks, this isn't needed.
  • A flag to indicate that information about the route has changed recently. this is the "route change flag." 🚩
  • Various timers associated with the route. see section 3.3 for more details on them ⏰.

the entries for the directly-connected networks are set up by the host, using info gathered by means not specified in this protocol. the metric for a directly-connected network is set to the cost of that network. in existing RIP implementations, 1 is always used for the cost, which means the RIP metric reduces to a simple hop-count 🦘. more complex metrics may be used when it's desirable to show preference for some networks over others, for example because of differences in bandwidth or reliability 🌈.

implementors may also choose to let the system administrator enter additional routes. these would most likely be routes to hosts or networks outside the scope of the routing system 🧭.

entries for destinations other than these initial ones are added and updated by the algorithms described in the following sections 🍓.

in order for the protocol to provide complete information on routing, every gateway in the system must participate in it. hosts that aren't gateways need not participate, but many implementations make provisions for them to listen to routing info so they can maintain their routing tables 👂.

3.1. Message formats 🎀

okay bestie, so RIP runs on top of UDP 🦋 Every host that uses RIP has a routing process that sends and receives datagrams on UDP port number 520. Anything aimed at another host's RIP processor goes to port 520, and all routing update messages go out from port 520 too. Unsolicited updates have both the source and destination port set to 520 💖 Replies to a request go back to whichever port the request came from. Specific queries and debugging requests can come from other ports, but they still get sent to port 520 on the target machine 🧚

okay now the silent mode is so cute 🙈 A silent RIP process normally doesn't send out any messages, but it still listens to what everyone else is saying 👂 This is useful for hosts that aren't acting as gateways but still want to listen to routing updates so they can keep an eye on local gateways and keep their routing tables current. (See [5] for a discussion of various ways that hosts can keep track of network topology.) A gateway that has lost contact with all but one of its networks might choose to go silent, since it's effectively not a gateway anymore 😌

ngl this one is a trap though: don't go silent if there's any chance the neighboring gateways are depending on its messages to figure out that the failed network is back up 🚨 (The 4BSD routed program uses routing packets to monitor the operation of point-to-point links.)

Here's the packet format, and it's giving very organized 📦

      Format of datagrams containing network information.  Field sizes
      are given in octets.  Unless otherwise specified, fields contain
      binary integers, in normal Internet order with the most-significant
      octet first.  Each tick mark represents one bit.

       0                   1                   2                   3 3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | command (1)   | version (1)   |      must be zero (2)         |
      +---------------+---------------+-------------------------------+
      | address family identifier (2) |      must be zero (2)         |
      +-------------------------------+-------------------------------+
      |                         IP address (4)                        |
      +---------------------------------------------------------------+
      |                        must be zero (4)                       |
      +---------------------------------------------------------------+
      |                        must be zero (4)                       |
      +---------------------------------------------------------------+
      |                          metric (4)                           |
      +---------------------------------------------------------------+
                                      .
                                      .
                                      .
      The portion of the datagram from address family identifier through
      metric may appear up to 25 times.  IP address is the usual 4-octet
      Internet address, in network order.

                          Figure 1.   Packet format

Every datagram has a command, a version number, and possibly some arguments 💅 This document describes version 1 of the protocol. Details on how to process the version number are in section 3.4. The command field tells you what the datagram is for. Here's the summary of the commands implemented in version 1, straight from the source ✨

   1 - request     A request for the responding system to send all or
                   part of its routing table.

   2 - response    A message containing all or part of the sender's
                   routing table.  This message may be sent in response
                   to a request or poll, or it may be an update message
                   generated by the sender.

   3 - traceon     Obsolete.  Messages containing this command are to be
                   ignored.

   4 - traceoff    Obsolete.  Messages containing this command are to be
                   ignored.

   5 - reserved    This value is used by Sun Microsystems for its own
                   purposes.  If new commands are added in any
                   succeeding version, they should begin with 6.
                   Messages containing this command may safely be
                   ignored by implementations that do not choose to
                   respond to it.

For request and response, the rest of the datagram is a list of destinations, with info about each one 📋 Each entry has a destination network or host and the metric for it. The packet format is meant to carry routing info for several different protocols, so each entry has an address family identifier that says what kind of address it holds 🌈 This document only covers routing for Internet networks, and the address family identifier for IP is 2. None of the RIP implementations available to the author implement any other type of address. But to make room for future development, implementations are required to skip entries that specify address families they don't support 🫶 (These entries are the same size as an entry specifying an IP address.) Processing carries on normally after any unsupported entries are skipped. The IP address is the usual Internet address, stored as 4 octets in network order. The metric field must contain a value between 1 and 15 inclusive, giving the current metric for the destination, or the value 16, which means the destination is not reachable 💀 Each route sent by a gateway supersedes any previous route to the same destination from that same gateway.

The maximum datagram size is 512 octets 📏 That only counts the portions of the datagram described above, not the IP or UDP headers. The commands that involve network information let information be split across several datagrams. No special provisions are needed for continuations, since you still get correct results if the datagrams are processed one at a time ✨

3.2. Addressing considerations 🗺️

Okay so, like we saw in section 2, distance vector routing can describe routes to individual hosts or to whole networks 🦋. RIP lets you do either one. The destinations in request and response messages can be networks, hosts, or a special code that means a default address. Which kind you actually end up using depends on the routing strategy of that particular network 💅.

Lots of networks don't need host routes at all. If every host on a given network or subnet is reachable through the same gateways, there's no reason to mention individual hosts in the routing tables 😌. BUT networks with point to point lines sometimes make gateways keep track of routes to certain hosts. Whether that's needed depends on the addressing and routing approach in the system, so some implementations may choose not to support host routes. If host routes aren't supported, they are to be dropped when they're received in response messages (see section 3.4.2) 🫶.

The RIP packet formats don't tell apart the different types of address. Fields that are labeled "address" can hold any of these:

  • host address
  • subnet number
  • network number
  • 0, indicating a default route

Entities that use RIP are assumed to use the most specific information available when routing a datagram 🎯. So when routing a datagram, its destination address gets checked against the list of host addresses first. Then it gets checked to see whether it matches any known subnet or network number. Finally, if none of those match, the default route is used.

When a host reads information it gets via RIP, how it interprets an address depends on whether it knows the subnet mask for that net 🧠. If it does, it can figure out what the address means. For example, take net 128.6, which has a subnet mask of 255.255.255.0. So 128.6.0.0 is a network number, 128.6.4.0 is a subnet number, and 128.6.4.1 is a host address. But if the host doesn't know the subnet mask, reading an address can be ambiguous 🙈. If there's a non-zero host part, there's no clear way to tell whether the address is a subnet number or a host address. A subnet number would be useless without the subnet mask, so in this situation addresses are assumed to represent hosts. To avoid this kind of mess, hosts must not send subnet routes to hosts that can't be expected to know the right subnet mask. Normally, hosts only know the subnet masks for directly-connected networks. So, unless special provisions have been made, routes to a subnet must not be sent outside the network that the subnet belongs to 🚫.

This filtering is done by the gateways on the "border" of the subnetted network 🚪. These are gateways that connect that network with some other network. Inside the subnetted network, each subnet is treated as its own individual network. RIP circulates routing entries for each subnet. However, border gateways send only a single entry for the network as a whole to hosts in other networks. That means a border gateway will send different information to different neighbors 👯. For neighbors connected to the subnetted network, it generates a list of all the subnets it's directly connected to, using the subnet number. For neighbors connected to other networks, it makes a single entry for the network as a whole, showing the metric for that network. (This metric would normally be the smallest metric for the subnets the gateway is attached to.)

Similarly, border gateways must not mention host routes for hosts within one of the directly-connected networks in messages to other networks. Those routes get subsumed by the single entry for the network as a whole ✨. We don't specify what to do with host routes for "distant" hosts (meaning hosts that aren't part of one of the directly-connected networks). Generally, these routes point at a host that's reachable through a route that doesn't support other hosts on the network that the host belongs to.

The special address 0.0.0.0 is used to describe a default route 🌈. A default route gets used when it's not convenient to list every possible network in the RIP updates, and when one or more closely-connected gateways in the system are ready to handle traffic to the networks that aren't listed explicitly. These gateways should create RIP entries for the address 0.0.0.0, just as if it were a network they're connected to. How gateways create entries for 0.0.0.0 is left up to the implementor 🛠️. Most commonly, the system administrator gets a way to specify which gateways should create entries for 0.0.0.0, but other mechanisms are possible. For example, an implementor might decide that any gateway that speaks EGP should be declared a default gateway. It may be useful to let the network administrator choose the metric used in these entries. If there's more than one default gateway, this makes it possible to express a preference for one over the other. The entries for 0.0.0.0 are handled by RIP in exactly the same way as if there were an actual network with this address. The difference is that the entry is used to route any datagram whose destination address doesn't match any other network in the table 🎀.

Implementations are not required to support this convention. However, it is strongly recommended. Implementations that don't support 0.0.0.0 must ignore entries with this address. In those cases, they must not pass the entry on in their own RIP updates. System administrators should take care to make sure routes to 0.0.0.0 don't propagate further than they're meant to 👀. Generally, each autonomous system has its own preferred default gateway. So routes involving 0.0.0.0 should generally not leave the boundary of an autonomous system. The mechanisms for enforcing this aren't specified in this document 🔒.

3.3. Timers ⏰

Okay, this section is all about the events that get triggered by timers. Let's go! 🚀

Every 30 seconds, the output process is told to generate a complete response to every neighboring gateway 📨. When there are lots of gateways on one network, they have a tendency to sync up with each other so they all send updates at the exact same time 😱. This can happen whenever the 30 second timer gets affected by the processing load on the system. It's undesirable for the update messages to become synchronized, because it can lead to unnecessary collisions on broadcast networks 💥. So, implementations are required to take one of two precautions:

  • The 30-second updates are triggered by a clock whose rate is not affected by system load or the time required to service the previous update timer.
  • The 30-second timer is offset by addition of a small random time each time it is set.

There are two timers associated with each route: a "timeout" and a "garbage-collection time" ⏳. When the timeout expires, the route is no longer valid. But it stays in the table for a short time, so neighbors can be told that the route has been dropped. When the garbage-collection timer expires, the route is finally removed from the tables 🗑️.

The timeout gets initialized when a route is established, and any time an update message is received for the route. If 180 seconds pass from the last time the timeout was initialized, the route is considered expired, and the deletion process (which we're about to describe) starts for it 😭.

Deletions can happen for one of two reasons: (1) the timeout expires, or (2) the metric is set to 16 because of an update received from the current gateway. (See section 3.4.2 for a discussion of processing updates from other gateways.) Either way, these things happen:

  • The garbage-collection timer is set for 120 seconds.
  • The metric for the route is set to 16 (infinity). This causes the route to be removed from service 🚮.
  • A flag is set noting that this entry has changed, and the output process is signalled to trigger a response.

Until the garbage-collection timer expires, the route is included in all updates sent by this host, with a metric of 16 (infinity). Once the garbage-collection timer expires, the route is deleted from the tables 💀.

Should a new route to this network get established while the garbage-collection timer is running, the new route will replace the one that's about to be deleted. In this case, the garbage-collection timer must be cleared 🧹.

See section 3.5 for a discussion of a delay that's required when carrying out triggered updates ⏱️. Implementing that delay does need a timer, but it makes more sense to talk about it in section 3.5 than here 💜.

3.4. Input processing 📥

This section describes how to handle datagrams received on UDP port 520 🎀. Before processing the datagrams in detail, certain general format checks must be made. These depend on the version number field in the datagram, like this:

  • 0: Datagrams whose version number is zero are to be ignored. They're from a previous version of the protocol, whose packet format was machine-specific 🤖.
  • 1: Datagrams whose version number is one are to be processed as described in the rest of this specification. All fields that are described above as "must be zero" are to be checked. If any of those fields contains a non-zero value, the entire message is to be ignored 🙅‍♀️.
  • >1: Datagrams whose version number is greater than one are to be processed as described in the rest of this specification. All fields that are described above as "must be zero" are to be ignored. Future versions of the protocol may put data into these fields. Version 1 implementations are to ignore this extra data and process only the fields specified in this document 🔮.

After checking the version number and doing any other preliminary checks, processing depends on the value in the command field 💖.

3.4.1. Request ✨

okay so a Request is basically the host going "bestie, what's in your routing table?" 🥺 It asks for a response containing all or part of the host's routing table. (Quick note: "host" here means either a host or a gateway. It'd be pretty unusual for a non-gateway host to send RIP messages 👀)

Requests are normally sent as broadcasts, from a UDP source port of 520. When that happens, silent processes do not respond to the request. Silent processes are, by definition, the ones we normally don't want seeing routing info 🙈 But gateway monitoring can make it useful to look at the routing table even for a silent process, so in that case the request should be sent from a UDP port number other than 520. If a request comes from port 520, silent processes do not respond. If the request comes from any other port, processes must respond even if they are silent. 🫣

The request is processed entry by entry. If there are no entries, no response is given. There's one special case though 💅 If there is exactly one entry in the request, with an address family identifier of 0 (meaning unspecified) and a metric of infinity (i.e., 16 for current implementations), that's a request to send the entire routing table. In that case, a call is made to the output process to send the routing table to the requesting port. It's giving "send me everything" energy 🧚

Except for this special case, processing is quite simple. Go down the list of entries in the request one by one. For each entry, look up the destination in the host's routing database. If there is a route, put that route's metric in the metric field in the datagram. If there isn't a route to the specified destination, put infinity (i.e., 16) in the metric field in the datagram. Once all the entries have been filled in, set the command to response and send the datagram back to the port it came from. ✨

Now here's the important bit 👑 There's a difference in handling depending on whether the request is for a specified set of destinations or for a complete routing table. If the request is for a complete host table, normal output processing is done. This includes split horizon (see section 2.2.1) and subnet hiding (section 3.2), so certain entries from the routing table will not be shown. If the request is for specific entries, they are looked up in the host table and the information is returned. No split horizon processing is done, and subnets are returned if requested. The authors expected these two kinds of requests to be used for different purposes, and they were right 🙌

When a host first comes up, it broadcasts requests on every connected network asking for a complete routing table. In general, complete routing tables are likely to be used to update another host's routing table, so for this reason, split horizon and all other filtering must be used. 🛡️ Requests for specific networks are only made by diagnostic software and are not used for routing. In that case the requester wants to know the exact contents of the routing database and would not want any information hidden 🔍

3.4.2. Response 💌

Responses can be received for several different reasons:

  • response to a specific query
  • regular updates
  • triggered updates triggered by a metric change

Processing is the same no matter how responses were generated. Iconic ✨

Because processing a response may update the host's routing table, the response must be checked carefully for validity 🧐 The response must be ignored if it is not from port 520. The IP source address should be checked to see whether the datagram is from a valid neighbor. The source of the datagram must be on a directly-connected network. It's also worth checking whether the response is from one of the host's own addresses. Interfaces on broadcast networks may receive copies of their own broadcasts immediately 😭 If a host processes its own output as new input, confusion is likely, so such datagrams must be ignored (except as discussed in the next paragraph).

Before actually processing a response, it may be useful to use its presence as input to a process for keeping track of interface status. As mentioned above, we time out a route when we haven't heard from its gateway for a certain amount of time. This works fine for routes that come from another gateway. It's also desirable to know when one of our own directly-connected networks has failed. This document does not specify any particular method for doing this, because such methods depend on the characteristics of the network and the hardware interface to it. However, such methods often involve listening for datagrams arriving on the interface, and arriving datagrams can be used as an indication that the interface is working. 🔌 Still, some caution must be used, because it is possible for interfaces to fail in such a way that input datagrams are received but output datagrams are never sent successfully. Lowkey scary 💀

Now that the datagram as a whole has been validated, process the entries in it one by one. Again, start by doing validation. If the metric is greater than infinity, ignore the entry. (This should be impossible, if the other host is working correctly. Incorrect metrics and other format errors should probably cause alerts or be logged.) Then look at the destination address and check the address family identifier. If it is not a value which is expected (e.g., 2 for Internet addresses), ignore the entry. Now check the address itself for various kinds of inappropriate addresses. Ignore the entry if the address is class D or E, if it is on net 0 (except for 0.0.0.0, if we accept default routes), or if it is on net 127 (the loopback network). Also, test for a broadcast address, i.e., anything whose host part is all ones on a network that supports broadcast, and ignore any such entry. If the implementor has chosen not to support host routes (see section 3.2), check whether the host portion of the address is non-zero; if so, ignore the entry. 🚫

Recall that the address field contains a number of unused octets. If the version number of the datagram is 1, they must also be checked. If any of them is nonzero, the entry is to be ignored. (Many of these cases indicate that the host the message came from isn't working correctly, so some form of error logging or alert should be triggered 🚨)

Update the metric by adding the cost of the network on which the message arrived. If the result is greater than 16, use 16. That is:

metric = MIN (metric + cost, 16)

Now look up the address to see whether there's already a route for it. In general, if there isn't one, we want to add one. However, there are various exceptions 🎀 If the metric is infinite, don't add an entry. (We would update an existing one, but we don't add new entries with infinite metric.) We also want to avoid adding routes to hosts if the host is part of a net or subnet for which we have at least as good a route. If neither of these exceptions applies, add a new entry to the routing database. This includes the following actions:

  • Set the destination and metric to those from the datagram.
  • Set the gateway to be the host from which the datagram came.
  • Initialize the timeout for the route. If the garbage-collection timer is running for this route, stop it. (See section 3.3 for a discussion of the timers.)
  • Set the route change flag, and signal the output process to trigger an update (see 3.5).

If there is an existing route, first compare gateways. If this datagram is from the same gateway as the existing route, reinitialize the timeout. Next compare metrics. If the datagram is from the same gateway as the existing route and the new metric is different from the old one, or if the new metric is lower than the old one, do the following actions:

  • Adopt the route from the datagram. That is, put the new metric in, and set the gateway to be the host from which the datagram came.
  • Initialize the timeout for the route.
  • Set the route change flag, and signal the output process to trigger an update (see 3.5).
  • If the new metric is 16 (infinity), the deletion process is started.

If the new metric is 16 (infinity), this starts the process for deleting the route. The route is no longer used for routing packets, and the deletion timer is started (see section 3.3). Note that a deletion is started only when the metric is first set to 16. If the metric was already 16, then a new deletion is not started. (Starting a deletion sets a timer. The concern is that we don't want to reset the timer every 30 seconds, as new messages arrive with an infinite metric. ⏰)

If the new metric is the same as the old one, it's simplest to do nothing further (beyond reinitializing the timeout, as specified above). However, the 4BSD routed uses an additional heuristic here 🧠 Normally, it is senseless to change to a route with the same metric as the existing route but a different gateway. If the existing route is showing signs of timing out, though, it may be better to switch to an equally-good alternative route immediately, rather than waiting for the timeout to happen. (See section 3.3 for a discussion of timeouts.) So, if the new metric is the same as the old one, routed looks at the timeout for the existing route. If it is at least halfway to the expiration point, routed switches to the new route. That is, the gateway is changed to the source of the current message. This heuristic is optional. 🦋

Any entry that fails these tests is ignored, as it is no better than the current route. Not me ignoring the bad ones 💖

3.5. Output Processing ✨

Okay bestie, this is where the router actually builds its replies 💌 Output processing makes response messages that carry all or part of the routing table, and it can kick off in any of these three ways:

  • by input processing when a request is seen. Here the resulting message goes to only one destination 🎯
  • by the regular routing update. Every 30 seconds, a response with the whole routing table goes to every neighboring gateway. (See section 3.3.) ⏰
  • by triggered updates. Whenever the metric for a route changes, an update gets triggered. (The update MAY be delayed; see below.) ⚡

Before we get into how each message is built for each directly-connected network, we need to talk about how the destinations get picked for the last two cases 🗺️ Normally, when a response is going to all destinations (so either the regular update or a triggered update is being prepared), it goes to the host at the other end of each connected point-to-point link, and it gets broadcast on every connected network that supports broadcasting. So you get one response prepared for each directly-connected network, sent to the matching destination or broadcast address. In most cases, that reaches all the neighboring gateways 🫶 But there are some cases where that's not good enough. This might involve a network that doesn't support broadcast (the ARPANET is the example), or a situation with dumb gateways. In those cases, it may be necessary to specify an actual list of neighboring hosts and gateways, and send a datagram to each one explicitly. It's up to the implementor to decide whether that mechanism is needed, and to define how the list gets specified 🤷‍♀️

Triggered updates need special handling for two reasons 💅 First, experience shows that triggered updates can put excessive load on networks with limited capacity or with lots of gateways on them 😭 So the protocol requires that implementors include provisions to limit how often triggered updates happen. After a triggered update is sent, a timer SHOULD be set for a random time between 1 and 5 seconds. If other changes that would trigger updates happen before the timer goes off, a single update is triggered when the timer expires, and then the timer gets set to another random value between 1 and 5 seconds. Triggered updates MAY be suppressed if a regular update is due by the time the triggered update would be sent 🌸

Second, triggered updates don't have to include the entire routing table. In principle, only the routes that changed need to be in there ✨ So messages generated as part of a triggered update MUST include at least those routes that have their route change flag set. They MAY include additional routes, or all routes, at the implementor's discretion. However, when full routing updates need multiple packets, sending all routes is strongly discouraged 🙈 When a triggered update is processed, messages SHOULD be generated for every directly-connected network. Split horizon processing happens when generating triggered updates as well as normal updates (see below) 🦋

If, after split horizon processing, a changed route would look identical on a network as it did before, the route doesn't need to be sent. And if, as a result, no routes need to be sent at all, the update MAY be omitted on that network 💀 (If a route only had a metric change, or it uses a new gateway that's on the same network as the old gateway, the route will be sent to the old gateway's network with a metric of infinity both before and after the change.) Once all of the triggered updates have been generated, the route change flags SHOULD be cleared 🧹

If input processing is allowed while output is being generated, appropriate interlocking MUST be done 🔐 The route change flags SHOULD NOT be changed as a result of processing input while a triggered update message is being generated 🚫

The only difference between a triggered update and any other update message is that routes which haven't changed might get left out. The rest of the mechanisms we're about to describe MUST all apply to triggered updates too 👑

Here's how a response datagram gets generated for a particular directly-connected network:

The IP source address MUST be the sending host's address on that network. This matters a LOT, because the source address gets put into routing tables in other hosts. If an incorrect source address is used, other hosts may be unable to route datagrams 😬 Sometimes gateways are set up with multiple IP addresses on one physical interface. Normally, that means several logical IP networks are being carried over one physical medium. In those cases, a separate update message MUST be sent for each address, with that address as the IP source address 🎀

Set the version number to the current version of RIP. (The version described in this document is 1.) Set the command to response. Set the bytes labeled "must be zero" to zero. Now start filling in entries 📝

To fill in the entries, go down all the routes in the internal routing table. Remember that the maximum datagram size is 512 bytes 📏 When there's no more space in the datagram, send the current message and start a new one. If a triggered update is being generated, only entries whose route change flags are set need to be included 💖

See the description in Section 3.2 for a discussion of the problems subnet and host routes can cause 🧐 Routes to subnets won't mean anything outside the network, so they MUST be omitted if the destination isn't on the same subnetted network. They SHOULD be replaced with a single route to the network that the subnets are part of. Similarly, routes to hosts MUST be eliminated if they're subsumed by a network route, as discussed in Section 3.2 🌈

If the route passes these tests, then the destination and metric go into the entry in the output datagram. Routes MUST be included in the datagram even if their metrics are infinite ♾️ If the gateway for the route is on the network the datagram is being prepared for, then the metric in the entry is set to 16, or the entire entry is omitted. Omitting the entry is simple split horizon. Including an entry with metric 16 is split horizon with poisoned reverse 🍓 See Section 2.2 for a more complete discussion of these alternatives 🧚

3.6. Compatibility 🌷

The protocol in this document is meant to interoperate with routed and other existing RIP implementations 🤝 But there's a different viewpoint on when to increment the metric than most earlier implementations used. In the previous perspective, the internal routing table has a metric of 0 for all directly-connected networks, and the cost (which is always 1) gets added to the metric when the route is sent in an update message. In this document, directly-connected networks appear in the internal routing table with metrics equal to their costs, and those metrics are not necessarily 1 📈 Here, the cost gets added to the metrics when routes are received in update messages. Metrics from the routing table are sent in update messages without change (unless split horizon modifies them) 💜

These two viewpoints result in identical update messages being sent 🥰 The metrics in the routing table differ by a constant one between the two descriptions, so there's no difference in effect. The change was made because the new description makes it way easier to handle situations where different metrics are used on directly-attached networks 🧠

Implementations that only support network costs of one don't need to change to match the new style of presentation. However, they MUST follow the description given in this document in all other ways 🫶

4. Control functions 🎛️

This section is about administrative controls. They aren't part of the protocol per se 🙃 Still, experience with existing networks suggests they matter a lot. Because they're not a necessary part of the protocol, they are considered OPTIONAL. However, we strongly recommend that at least some of them get included in every implementation 💅

These controls exist mainly so RIP can be connected to networks whose routing might be unstable or prone to errors ⚠️ Here are some examples:

It's sometimes desirable to limit the hosts and gateways that information gets accepted from. Every once in a while, hosts get misconfigured in a way that makes them start sending inappropriate information 😭

A bunch of sites limit the set of networks they allow in update messages. Say Organization A has a connection to Organization B that they use for direct communication. For security or performance reasons, A may not be willing to give other organizations access to that connection. In those cases, A SHOULD NOT include B's networks in the updates A sends to third parties 🔒

Here are some typical controls. Heads up though: the RIP protocol does not require these or any other controls 🙈

  • a neighbor list - the network administrator SHOULD be able to define a list of neighbors for each host. A host would accept response messages only from hosts on its list of neighbors 👯‍♀️
  • allowing or disallowing specific destinations - the network administrator SHOULD be able to specify a list of destination addresses to allow or disallow. The list would be associated with a particular interface in the incoming or outgoing direction. Only allowed networks would be mentioned in response messages going out, or processed in response messages coming in. If a list of allowed addresses is specified, all other addresses are disallowed. If a list of disallowed addresses is specified, all other addresses are allowed 🚦

REFERENCES and BIBLIOGRAPHY 📚✨

  • [1] Bellman, R. E., "Dynamic Programming", Princeton University Press, Princeton, N.J., 1957.
  • [2] Bertsekas, D. P., and Gallaher, R. G., "Data Networks", Prentice-Hall, Englewood Cliffs, N.J., 1987.
  • [3] Braden, R., and Postel, J., "Requirements for Internet Gateways", USC/Information Sciences Institute, RFC-1009, June 1987.
  • [4] Boggs, D. R., Shoch, J. F., Taft, E. A., and Metcalfe, R. M., "Pup: An Internetwork Architecture", IEEE Transactions on Communications, April 1980.
  • [5] Clark, D. D., "Fault Isolation and Recovery," MIT-LCS, RFC-816, July 1982.
  • [6] Ford, L. R. Jr., and Fulkerson, D. R., "Flows in Networks", Princeton University Press, Princeton, N.J., 1962.
  • [7] Xerox Corp., "Internet Transport Protocols", Xerox System Integration Standard XSIS 028112, December 1981.
📦 where this page comes from