APPENDIX E Additional Next-Hop Selection Algorithms

   Section [5.2.4.3] specifies an algorithm that routers ought to use
   when selecting a next-hop for a packet.

   This appendix provides historical perspective for the next-hop
   selection problem.  It also presents several additional pruning rules
   and next-hop selection algorithms that might be found in the
   Internet.

   This appendix presents material drawn from an earlier, unpublished,
   work by Philip Almquist; Ruminations on the Next Hop.

   This Appendix does not specify any standards or requirements.

E.1. Some Historical Perspective

   It is useful to briefly review the history of the topic, beginning
   with what is sometimes called the "classic model" of how a router
   makes routing decisions.  This model predates IP.  In this model, a
   router speaks some single routing protocol such as RIP.  The protocol
   completely determines the contents of the router's Forwarding
   Information Base (FIB).  The route lookup algorithm is trivial: the
   router looks in the FIB for a route whose destination attribute
   exactly matches the network prefix portion of the destination address
   in the packet.  If one is found, it is used; if none is found, the
   destination is unreachable.  Because the routing protocol keeps at
   most one route to each destination, the problem of what to do when
   there are multiple routes that match the same destination cannot
   arise.

   Over the years, this classic model has been augmented in small ways.
   With the deployment of default routes, subnets, and host routes, it
   became possible to have more than one routing table entry which in
   some sense matched the destination.  This was easily resolved by a
   consensus that there was a hierarchy of routes: host routes should be
   preferred over subnet routes, subnet routes over net routes, and net
   routes over default routes.

   With the deployment of technologies supporting variable length subnet
   masks (variable length network prefixes), the general approach
   remained the same although its description became a little more
   complicated; network prefixes were introduced as a conscious
   simplification and regularization of the architecture.  We now say
   that each route to a network prefix route has a prefix length
   associated with it.  This prefix length indicates the number of bits
   in the prefix.  This may also be represented using the classical
   subnet mask.  A route cannot be used to route a packet unless each
   significant bit in the route's network prefix matches the
   corresponding bit in the packet's destination address.  Routes with
   more bits set in their masks are preferred over routes that have
   fewer bits set in their masks.  This is simply a generalization of
   the hierarchy of routes described above, and will be referred to for
   the rest of this memo as choosing a route by preferring longest
   match.

   Another way the classic model has been augmented is through a small
   amount of relaxation of the notion that a routing protocol has
   complete control over the contents of the routing table.  First,
   static routes were introduced.  For the first time, it was possible
   to simultaneously have two routes (one dynamic and one static) to the
   same destination.  When this happened, a router had to have a policy
   (in some cases configurable, and in other cases chosen by the author
   of the router's software) which determined whether the static route
   or the dynamic route was preferred.  However, this policy was only
   used as a tie-breaker when longest match didn't uniquely determine
   which route to use.  Thus, for example, a static default route would
   never be preferred over a dynamic net route even if the policy
   preferred static routes over dynamic routes.

   The classic model had to be further augmented when inter-domain
   routing protocols were invented.  Traditional routing protocols came
   to be called "interior gateway protocols" (IGPs), and at each
   Internet site there was a strange new beast called an "exterior
   gateway", a router that spoke EGP to several "BBN Core Gateways" (the
   routers that made up the Internet backbone at the time) at the same
   time as it spoke its IGP to the other routers at its site.  Both
   protocols wanted to determine the contents of the router's routing
   table.  Theoretically, this could result in a router having three

   routes (EGP, IGP, and static) to the same destination.  Because of
   the Internet topology at the time, it was resolved with little debate
   that routers would be best served by a policy of preferring IGP
   routes over EGP routes.  However, the sanctity of longest match
   remained unquestioned: a default route learned from the IGP would
   never be preferred over a net route from learned EGP.

   Although the Internet topology, and consequently routing in the
   Internet, have evolved considerably since then, this slightly
   augmented version of the classic model has survived intact to this
   day in the Internet (except that BGP has replaced EGP).  Conceptually
   (and often in implementation) each router has a routing table and one
   or more routing protocol processes.  Each of these processes can add
   any entry that it pleases, and can delete or modify any entry that it
   has created.  When routing a packet, the router picks the best route
   using longest match, augmented with a policy mechanism to break ties.
   Although this augmented classic model has served us well, it has a
   number of shortcomings:

   o It ignores (although it could be augmented to consider) path
      characteristics such as quality of service and MTU.

   o It doesn't support routing protocols (such as OSPF and Integrated
      IS-IS) that require route lookup algorithms different than pure
      longest match.

   o There has not been a firm consensus on what the tie-breaking
      mechanism ought to be.  Tie-breaking mechanisms have often been
      found to be difficult if not impossible to configure in such a way
      that the router will always pick what the network manger considers
      to be the "correct" route.

E.2. Additional Pruning Rules

      Section [5.2.4.3] defined several pruning rules to use to select
      routes from the FIB.  There are other rules that could also be
      used.

      o OSPF Route Class
         Routing protocols that have areas or make a distinction between
         internal and external routes divide their routes into classes
         by the type of information used to calculate the route.  A
         route is always chosen from the most preferred class unless
         none is available, in which case one is chosen from the second
         most preferred class, and so on.  In OSPF, the classes (in
         order from most preferred to least preferred) are intra-area,
         inter-area, type 1 external (external routes with internal
         metrics), and type 2 external.  As an additional wrinkle, a

         router is configured to know what addresses ought to be
         accessible using intra-area routes, and will not use inter-
         area or external routes to reach these destinations even when
         no intra-area route is available.

         More precisely, we assume that each route has a class
         attribute, called route.class, which is assigned by the routing
         protocol.  The set of candidate routes is examined to determine
         if it contains any for which route.class = intra-area.  If so,
         all routes except those for which route.class = intra-area are
         discarded.  Otherwise, router checks whether the packet's
         destination falls within the address ranges configured for the
         local area.  If so, the entire set of candidate routes is
         deleted.  Otherwise, the set of candidate routes is examined to
         determine if it contains any for which route.class = inter-
         area.  If so, all routes except those for which route.class =
         inter-area are discarded.  Otherwise, the set of candidate
         routes is examined to determine if it contains any for which
         route.class = type 1 external.  If so, all routes except those
         for which route.class = type 1 external are discarded.

      o IS-IS Route Class
         IS-IS route classes work identically to OSPF's.  However, the
         set of classes defined by Integrated IS-IS is different, such
         that there isn't a one-to-one mapping between IS-IS route
         classes and OSPF route classes.  The route classes used by
         Integrated IS-IS are (in order from most preferred to least
         preferred) intra-area, inter-area, and external.

         The Integrated IS-IS internal class is equivalent to the OSPF
         internal class.  Likewise, the Integrated IS-IS external class
         is equivalent to OSPF's type 2 external class.  However,
         Integrated IS-IS does not make a distinction between inter-area
         routes and external routes with internal metrics - both are
         considered to be inter-area routes.  Thus, OSPF prefers true
         inter-area routes over external routes with internal metrics,
         whereas Integrated IS-IS gives the two types of routes equal
         preference.

      o IDPR Policy
         A specific case of Policy.  The IETF's Inter-domain Policy
         Routing Working Group is devising a routing protocol called
         Inter-Domain Policy Routing (IDPR) to support true policy-based
         routing in the Internet.  Packets with certain combinations of
         header attributes (such as specific combinations of source and
         destination addresses or special IDPR source route options) are
         required to use routes provided by the IDPR protocol.  Thus,
         unlike other Policy pruning rules, IDPR Policy would have to be

         applied before any other pruning rules except Basic Match.

         Specifically, IDPR Policy examines the packet being forwarded
         to ascertain if its attributes require that it be forwarded
         using policy-based routes.  If so, IDPR Policy deletes all
         routes not provided by the IDPR protocol.

E.3 Some Route Lookup Algorithms

      This section examines several route lookup algorithms that are in
      use or have been proposed.  Each is described by giving the
      sequence of pruning rules it uses.  The strengths and weaknesses
      of each algorithm are presented

E.3.1 The Revised Classic Algorithm

      The Revised Classic Algorithm is the form of the traditional
      algorithm that was discussed in Section [E.1].  The steps of this
      algorithm are:

      1.  Basic match
      2.  Longest match
      3.  Best metric
      4.  Policy

      Some implementations omit the Policy step, since it is needed only
      when routes may have metrics that are not comparable (because they
      were learned from different routing domains).

      The advantages of this algorithm are:

      (1) It is widely implemented.

      (2) Except for the Policy step (which an implementor can choose to
           make arbitrarily complex) the algorithm is simple both to
           understand and to implement.

      Its disadvantages are:

      (1) It does not handle IS-IS or OSPF route classes, and therefore
           cannot be used for Integrated IS-IS or OSPF.

      (2) It does not handle TOS or other path attributes.

      (3) The policy mechanisms are not standardized in any way, and are
           therefore are often implementation-specific.  This causes
           extra work for implementors (who must invent appropriate
           policy mechanisms) and for users (who must learn how to use

           the mechanisms. This lack of a standardized mechanism also
           makes it difficult to build consistent configurations for
           routers from different vendors. This presents a significant
           practical deterrent to multi-vendor interoperability.

      (4) The proprietary policy mechanisms currently provided by
           vendors are often inadequate in complex parts of the
           Internet.

      (5) The algorithm has not been written down in any generally
           available document or standard.  It is, in effect, a part of
           the Internet Folklore.

E.3.2 The Variant Router Requirements Algorithm

      Some Router Requirements Working Group members have proposed a
      slight variant of the algorithm described in the Section
      [5.2.4.3].  In this variant, matching the type of service
      requested is considered to be more important, rather than less
      important, than matching as much of the destination address as
      possible.  For example, this algorithm would prefer a default
      route that had the correct type of service over a network route
      that had the default type of service, whereas the algorithm in
      [5.2.4.3] would make the opposite choice.

      The steps of the algorithm are:

      1.  Basic match
      2.  Weak TOS
      3.  Longest match
      4.  Best metric
      5.  Policy

      Debate between the proponents of this algorithm and the regular
      Router Requirements Algorithm suggests that each side can show
      cases where its algorithm leads to simpler, more intuitive routing
      than the other's algorithm does.  This variant has the same set of
      advantages and disadvantages that the algorithm specified in
      [5.2.4.3] does, except that pruning on Weak TOS before pruning on
      Longest Match makes this algorithm less compatible with OSPF and
      Integrated IS-IS than the standard Router Requirements Algorithm.

E.3.3 The OSPF Algorithm

      OSPF uses an algorithm that is virtually identical to the Router
      Requirements Algorithm except for one crucial difference: OSPF
      considers OSPF route classes.

      The algorithm is:

      1.  Basic match
      2.  OSPF route class
      3.  Longest match
      4.  Weak TOS
      5.  Best metric
      6.  Policy

      Type of service support is not always present.  If it is not
      present then, of course, the fourth step would be omitted

      This algorithm has some advantages over the Revised Classic
      Algorithm:

      (1) It supports type of service routing.

      (2) Its rules are written down, rather than merely being a part of
           the Internet folklore.

      (3) It (obviously) works with OSPF.

      However, this algorithm also retains some of the disadvantages of
      the Revised Classic Algorithm:

      (1) Path properties other than type of service (e.g., MTU) are
           ignored.

      (2) As in the Revised Classic Algorithm, the details (or even the
           existence) of the Policy step are left to the discretion of
           the implementor.

      The OSPF Algorithm also has a further disadvantage (which is not
      shared by the Revised Classic Algorithm).  OSPF internal (intra-
      area or inter-area) routes are always considered to be superior to
      routes learned from other routing protocols, even in cases where
      the OSPF route matches fewer bits of the destination address.
      This is a policy decision that is inappropriate in some networks.

      Finally, it is worth noting that the OSPF Algorithm's TOS support
      suffers from a deficiency in that routing protocols that support
      TOS are implicitly preferred when forwarding packets that have
      non-zero TOS values.  This may not be appropriate in some cases.

E.3.4 The Integrated IS-IS Algorithm

   Integrated IS-IS uses an algorithm that is similar to but not quite
   identical to the OSPF Algorithm.  Integrated IS-IS uses a different
   set of route classes, and differs slightly in its handling of type of
   service.  The algorithm is:

   1.  Basic Match
   2.  IS-IS Route Classes
   3.  Longest Match
   4.  Weak TOS
   5.  Best Metric
   6.  Policy

   Although Integrated IS-IS uses Weak TOS, the protocol is only capable
   of carrying routes for a small specific subset of the possible values
   for the TOS field in the IP header.  Packets containing other values
   in the TOS field are routed using the default TOS.

   Type of service support is optional; if disabled, the fourth step
   would be omitted.  As in OSPF, the specification does not include the
   Policy step.

   This algorithm has some advantages over the Revised Classic
   Algorithm:

   (1) It supports type of service routing.
   (2) Its rules are written down, rather than merely being a part of
        the Internet folklore.
   (3) It (obviously) works with Integrated IS-IS.

   However, this algorithm also retains some of the disadvantages of the
   Revised Classic Algorithm:

   (1) Path properties other than type of service (e.g., MTU) are
        ignored.
   (2) As in the Revised Classic Algorithm, the details (or even the
        existence) of the Policy step are left to the discretion of the
        implementor.
   (3) It doesn't work with OSPF because of the differences between IS-
        IS route classes and OSPF route classes.  Also, because IS-IS
        supports only a subset of the possible TOS values, some obvious
        implementations of the Integrated IS-IS algorithm would not
        support OSPF's interpretation of TOS.

   The Integrated IS-IS Algorithm also has a further disadvantage (which
   is not shared by the Revised Classic Algorithm): IS-IS internal
   (intra-area or inter-area) routes are always considered to be

   superior to routes learned from other routing protocols, even in
   cases where the IS-IS route matches fewer bits of the destination
   address and doesn't provide the requested type of service.  This is a
   policy decision that may not be appropriate in all cases.

   Finally, it is worth noting that the Integrated IS-IS Algorithm's TOS
   support suffers from the same deficiency noted for the OSPF
   Algorithm.

Security Considerations

   Although the focus of this document is interoperability rather than
   security, there are obviously many sections of this document that
   have some ramifications on network security.

   Security means different things to different people.  Security from a
   router's point of view is anything that helps to keep its own
   networks operational and in addition helps to keep the Internet as a
   whole healthy.  For the purposes of this document, the security
   services we are concerned with are denial of service, integrity, and
   authentication as it applies to the first two.  Privacy as a security
   service is important, but only peripherally a concern of a router -
   at least as of the date of this document.

   In several places in this document there are sections entitled ...
   Security Considerations.  These sections discuss specific
   considerations that apply to the general topic under discussion.

   Rarely does this document say do this and your router/network will be
   secure.  More likely, it says this is a good idea and if you do it,
   it *may* improve the security of the Internet and your local system
   in general.

   Unfortunately, this is the state-of-the-art AT THIS TIME.  Few if any
   of the network protocols a router is concerned with have reasonable,
   built-in security features.  Industry and the protocol designers have
   been and are continuing to struggle with these issues.  There is
   progress, but only small baby steps such as the peer-to-peer
   authentication available in the BGP and OSPF routing protocols.

   In particular, this document notes the current research into
   developing and enhancing network security.  Specific areas of
   research, development, and engineering that are underway as of this
   writing (December 1993) are in IP Security, SNMP Security, and common
   authentication technologies.

   Notwithstanding all the above, there are things both vendors and
   users can do to improve the security of their router.  Vendors should

   get a copy of Trusted Computer System Interpretation [INTRO:8].  Even
   if a vendor decides not to submit their device for formal
   verification under these guidelines, the publication provides
   excellent guidance on general security design and practices for
   computing devices.

APPENDIX F: HISTORICAL ROUTING PROTOCOLS

   Certain routing protocols are common in the Internet, but the authors
   of this document cannot in good conscience recommend their use.  This
   is not because they do not work correctly, but because the
   characteristics of the Internet assumed in their design (simple
   routing, no policy, a single "core router" network under common
   administration, limited complexity, or limited network diameter) are
   not attributes of today's Internet.  Those parts of the Internet that
   still use them are generally limited "fringe" domains with limited
   complexity.

   As a matter of good faith, collected wisdom concerning their
   implementation is recorded in this section.

F.1 EXTERIOR GATEWAY PROTOCOL - EGP

F.1.1 Introduction

   The Exterior Gateway Protocol (EGP) specifies an EGP that is used to
   exchange reachability information between routers of the same or
   differing autonomous systems.  EGP is not considered a routing
   protocol since there is no standard interpretation (i.e. metric) for
   the distance fields in the EGP update message, so distances are
   comparable only among routers of the same AS.  It is however designed
   to provide high-quality reachability information, both about neighbor
   routers and about routes to non-neighbor routers.

   EGP is defined by [ROUTE:6].  An implementor almost certainly wants
   to read [ROUTE:7] and [ROUTE:8] as well, for they contain useful
   explanations and background material.

   DISCUSSION
      The present EGP specification has serious limitations, most
      importantly a restriction that limits routers to advertising only
      those networks that are reachable from within the router's
      autonomous system.  This restriction against propagating third
      party EGP information is to prevent long-lived routing loops.
      This effectively limits EGP to a two-level hierarchy.

      RFC-975 is not a part of the EGP specification, and should be
      ignored.

F.1.2 Protocol Walk-through

      Indirect Neighbors: RFC-888, page 26

         An implementation of EGP MUST include indirect neighbor
         support.

      Polling Intervals: RFC-904, page 10

         The interval between Hello command retransmissions and the
         interval between Poll retransmissions SHOULD be configurable
         but there MUST be a minimum value defined.

         The interval at which an implementation will respond to Hello
         commands and Poll commands SHOULD be configurable but there
         MUST be a minimum value defined.

      Network Reachability: RFC-904, page 15

   An implementation MUST default to not providing the external list of
   routers in other autonomous systems; only the internal list of
   routers together with the nets that are reachable through those
   routers should be included in an Update Response/Indication packet.
   However, an implementation MAY elect to provide a configuration
   option enabling the external list to be provided.  An implementation
   MUST NOT include in the external list routers that were learned
   through the external list provided by a router in another autonomous
   system.  An implementation MUST NOT send a network back to the
   autonomous system from which it is learned, i.e.  it MUST do split-
   horizon on an autonomous system level.

   If more than 255 internal or 255 external routers need to be
   specified in a Network Reachability update, the networks reachable
   from routers that can not be listed MUST be merged into the list for
   one of the listed routers.  Which of the listed routers is chosen for
   this purpose SHOULD be user configurable, but SHOULD default to the
   source address of the EGP update being generated.

   An EGP update contains a series of blocks of network numbers, where
   each block contains a list of network numbers reachable at a
   particular distance through a particular router.  If more than 255
   networks are reachable at a particular distance through a particular
   router, they are split into multiple blocks (all of which have the
   same distance).  Similarly, if more than 255 blocks are required to
   list the networks reachable through a particular router, the router's
   address is listed as many times as necessary to include all the
   blocks in the update.

Unsolicited Updates: RFC-904, page 16

   If a network is shared with the peer, an implementation MUST send an
   unsolicited update upon entry to the Up state if the source network
   is the shared network.

Neighbor Reachability: RFC-904, page 6, 13-15

   The table on page 6 that describes the values of j and k (the
   neighbor up and down thresholds) is incorrect.  It is reproduced
   correctly here:

      Name    Active  Passive Description
      -----------------------------------------------
       j         3       1    neighbor-up threshold
       k         1       0    neighbor-down threshold

   The value for k in passive mode also specified incorrectly in RFC-
   904, page 14 The values in parenthesis should read:

      (j = 1, k = 0, and T3/T1 = 4)

   As an optimization, an implementation can refrain from sending a
   Hello command when a Poll is due.  If an implementation does so, it
   SHOULD provide a user configurable option to disable this
   optimization.

Abort timer: RFC-904, pages 6, 12, 13

   An EGP implementation MUST include support for the abort timer (as
   documented in section 4.1.4 of RFC-904).  An implementation SHOULD
   use the abort timer in the Idle state to automatically issue a Start
   event to restart the protocol machine.  Recommended values are P4 for
   a critical error (Administratively prohibited, Protocol Violation and
   Parameter Problem) and P5 for all others.  The abort timer SHOULD NOT
   be started when a Stop event was manually initiated (such as through
   a network management protocol).

Cease command received in Idle state: RFC-904, page 13

   When the EGP state machine is in the Idle state, it MUST reply to
   Cease commands with a Cease-ack response.

Hello Polling Mode: RFC-904, page 11

   An EGP implementation MUST include support for both active and
   passive polling modes.

Neighbor Acquisition Messages: RFC-904, page 18

   As noted the Hello and Poll Intervals should only be present in
   Request and Confirm messages.  Therefore the length of an EGP
   Neighbor Acquisition Message is 14 bytes for a Request or Confirm
   message and 10 bytes for a Refuse, Cease or Cease-ack message.
   Implementations MUST NOT send 14 bytes for Refuse, Cease or Cease-ack
   messages but MUST allow for implementations that send 14 bytes for
   these messages.

Sequence Numbers: RFC-904, page 10

   Response or indication packets received with a sequence number not
   equal to S MUST be discarded.  The send sequence number S MUST be
   incremented just before the time a Poll command is sent and at no
   other times.

F.2 ROUTING INFORMATION PROTOCOL - RIP

F.2.1 Introduction

   RIP is specified in [ROUTE:3].  Although RIP is still quite important
   in the Internet, it is being replaced in sophisticated applications
   by more modern IGPs such as the ones described above.  A router
   implementing RIP SHOULD implement RIP Version 2 [ROUTE:?], as it
   supports CIDR routes.  If occasional access networking is in use, a
   router implementing RIP SHOULD implement Demand RIP [ROUTE:?].

   Another common use for RIP is as a router discovery protocol.
   Section [4.3.3.10] briefly touches upon this subject.

F.2.2 Protocol Walk-Through

   Dealing with changes in topology: [ROUTE:3], page 11

        An implementation of RIP MUST provide a means for timing out
        routes.  Since messages are occasionally lost, implementations
        MUST NOT invalidate a route based on a single missed update.

        Implementations MUST by default wait six times the update
        interval before invalidating a route.  A router MAY have
        configuration options to alter this value.

   DISCUSSION
      It is important to routing stability that all routers in a RIP
      autonomous system use similar timeout value for invalidating
      routes, and therefore it is important that an implementation
      default to the timeout value specified in the RIP specification.

      However, that timeout value is too conservative in environments
      where packet loss is reasonably rare.  In such an environment, a
      network manager may wish to be able to decrease the timeout period
      to promote faster recovery from failures.

   IMPLEMENTATION
      There is a very simple mechanism that a router may use to meet the
      requirement to invalidate routes promptly after they time out.
      Whenever the router scans the routing table to see if any routes
      have timed out, it also notes the age of the least recently
      updated route that has not yet timed out.  Subtracting this age
      from the timeout period gives the amount of time until the router
      again needs to scan the table for timed out routes.

Split Horizon: [ROUTE:3], page 14-15

   An implementation of RIP MUST implement split horizon, a scheme used
   for avoiding problems caused by including routes in updates sent to
   the router from which they were learned.

   An implementation of RIP SHOULD implement Split horizon with poisoned
   reverse, a variant of split horizon that includes routes learned from
   a router sent to that router, but sets their metric to infinity.
   Because of the routing overhead that may be incurred by implementing
   split horizon with poisoned reverse, implementations MAY include an
   option to select whether poisoned reverse is in effect.  An
   implementation SHOULD limit the time in which it sends reverse routes
   at an infinite metric.

   IMPLEMENTATION
      Each of the following algorithms can be used to limit the time for
      which poisoned reverse is applied to a route.  The first algorithm
      is more complex but does a more thorough job of limiting poisoned
      reverse to only those cases where it is necessary.

      The goal of both algorithms is to ensure that poison reverse is
      done for any destination whose route has changed in the last Route
      Lifetime (typically 180 seconds), unless it can be sure that the
      previous route used the same output interface.  The Route Lifetime
      is used because that is the amount of time RIP will keep around an
      old route before declaring it stale.

      The time intervals (and derived variables) used in the following
      algorithms are as follows:

      Tu The Update Timer; the number of seconds between RIP updates.
           This typically defaults to 30 seconds.

      Rl The Route Lifetime, in seconds.  This is the amount of time
           that a route is presumed to be good, without requiring an
           update.  This typically defaults to 180 seconds.

      Ul The Update Loss; the number of consecutive updates that have to
           be lost or fail to mention a route before RIP deletes the
           route.  Ul is calculated to be (Rl/Tu)+1.  The +1 is to
           account for the fact that the first time the ifcounter is
           decremented will be less than Tu seconds after it is
           initialized.  Typically, Ul will be 7: (180/30)+1.


      In The value to set ifcounter to when a destination is newly
           learned.  This value is Ul-4, where the 4 is RIP's garbage
           collection timer/30

      The first algorithm is:

      - Associated with each destination is a counter, called the
         ifcounter below.  Poison reverse is done for any route whose
         destination's ifcounter is greater than zero.

      - After a regular (not triggered or in response to a request)
         update is sent, all the non-zero ifcounters are decremented by
         one.

      - When a route to a destination is created, its ifcounter is set
         as follows:

         - If the new route is superseding a valid route, and the old
            route used a different (logical) output interface, then the
            ifcounter is set to Ul.

         - If the new route is superseding a stale route, and the old
            route used a different (logical) output interface, then the
            ifcounter is set to MAX(0, Ul - INT(seconds that the route
            has been stale/Ut).

         - If there was no previous route to the destination, the
            ifcounter is set to In.

         - Otherwise, the ifcounter is set to zero

      - RIP also maintains a timer, called the resettimer below.  Poison
         reverse is done on all routes whenever resettimer has not
         expired (regardless of the ifcounter values).

      - When RIP is started, restarted, reset, or otherwise has its
         routing table cleared, it sets the resettimer to go off in Rl
         seconds.

      The second algorithm is identical to the first except that:

      - The rules which set the ifcounter to non-zero values are changed
         to always set it to Rl/Tu, and

      - The resettimer is eliminated.

 Triggered updates: [ROUTE:3], page 15-16; page 29

      Triggered updates (also called flash updates) are a mechanism for
      immediately notifying a router's neighbors when the router adds or
      deletes routes or changes their metrics.  A router MUST send a
      triggered update when routes are deleted or their metrics are
      increased.  A router MAY send a triggered update when routes are
      added or their metrics decreased.

      Since triggered updates can cause excessive routing overhead,
      implementations MUST use the following mechanism to limit the
      frequency of triggered updates:

      (1) When a router sends a triggered update, it sets a timer to a
           random time between one and five seconds in the future.  The
           router must not generate additional triggered updates before
           this timer expires.

      (2) If the router would generate a triggered update during this
           interval it sets a flag indicating that a triggered update is
           desired.  The router also logs the desired triggered update.

      (3) When the triggered update timer expires, the router checks the
           triggered update flag.  If the flag is set then the router
           sends a single triggered update which includes all the
           changes that were logged.  The router then clears the flag
           and, since a triggered update was sent, restarts this
           algorithm.

      (4) The flag is also cleared whenever a regular update is sent.

      Triggered updates SHOULD include all routes that have changed
      since the most recent regular (non-triggered) update.  Triggered
      updates MUST NOT include routes that have not changed since the
      most recent regular update.

   DISCUSSION
      Sending all routes, whether they have changed recently or not, is
      unacceptable in triggered updates because the tremendous size of
      many Internet routing tables could otherwise result in
      considerable bandwidth being wasted on triggered updates.

Use of UDP: [ROUTE:3], page 18-19.

   RIP packets sent to an IP broadcast address SHOULD have their initial
   TTL set to one.

   Note that to comply with Section [6.1] of this memo, a router SHOULD
   use UDP checksums in RIP packets that it originates, MUST discard RIP
   packets received with invalid UDP checksums, but MUST NOT discard
   received RIP packets simply because they do not contain UDP
   checksums.

Addressing Considerations: [ROUTE:3], page 22

   A RIP implementation SHOULD support host routes.  If it does not, it
   MUST (as described on page 27 of [ROUTE:3]) ignore host routes in
   received updates.  A router MAY log ignored hosts routes.

   The special address 0.0.0.0 is used to describe a default route.  A
   default route is used as the route of last resort (i.e., when a route
   to the specific net does not exist in the routing table).  The router
   MUST be able to create a RIP entry for the address 0.0.0.0.

Input Processing - Response: [ROUTE:3], page 26

   When processing an update, the following validity checks MUST be
   performed:

   o The response MUST be from UDP port 520.

   o The source address MUST be on a directly connected subnet (or on a
      directly connected, non-subnetted network) to be considered valid.

   o The source address MUST NOT be one of the router's addresses.

   DISCUSSION
      Some networks, media, and interfaces allow a sending node to
      receive packets that it broadcasts.  A router must not accept its
      own packets as valid routing updates and process them.  The last
      requirement prevents a router from accepting its own routing
      updates and processing them (on the assumption that they were sent
      by some other router on the network).

   An implementation MUST NOT replace an existing route if the metric
   received is equal to the existing metric except in accordance with
   the following heuristic.

   An implementation MAY choose to implement the following heuristic to
   deal with the above situation.  Normally, it is useless to change the
   route to a network from one router to another if both are advertised
   at the same metric.  However, the route being advertised by one of
   the routers may be in the process of timing out.  Instead of waiting
   for the route to timeout, the new route can be used after a specified
   amount of time has elapsed.  If this heuristic is implemented, it
   MUST wait at least halfway to the expiration point before the new
   route is installed.

F.2.3 Specific Issues


RIP Shutdown

     An implementation of RIP SHOULD provide for a graceful shutdown
     using the following steps:

     (1) Input processing is terminated,

     (2) Four updates are generated at random intervals of between two
          and four seconds, These updates contain all routes that were
          previously announced, but with some metric changes.  Routes
          that were being announced at a metric of infinity should
          continue to use this metric.  Routes that had been announced
          with a non-infinite metric should be announced with a metric
          of 15 (infinity - 1).

   DISCUSSION
      The metric used for the above really ought to be 16 (infinity);
      setting it to 15 is a kludge to avoid breaking certain old hosts
      that wiretap the RIP protocol.  Such a host will (erroneously)
      abort a TCP connection if it tries to send a datagram on the
      connection while the host has no route to the destination (even if
      the period when the host has no route lasts only a few seconds
      while RIP chooses an alternate path to the destination).

RIP Split Horizon and Static Routes

   Split horizon SHOULD be applied to static routes by default.  An
   implementation SHOULD provide a way to specify, per static route,
   that split horizon should not be applied to this route.

F.3 GATEWAY TO GATEWAY PROTOCOL - GGP

   The Gateway to Gateway protocol is considered obsolete and SHOULD NOT
   be implemented.

Acknowledgments

   O that we now had here
   But one ten thousand of those men in England
   That do no work to-day!

   What's he that wishes so?
   My cousin Westmoreland? No, my fair cousin:
   If we are mark'd to die, we are enow
   To do our country loss; and if to live,
   The fewer men, the greater share of honour.
   God's will! I pray thee, wish not one man more.
   By Jove, I am not covetous for gold,
   Nor care I who doth feed upon my cost;
   It yearns me not if men my garments wear;
   Such outward things dwell not in my desires:
   But if it be a sin to covet honour,
   I am the most offending soul alive.
   No, faith, my coz, wish not a man from England:
   God's peace! I would not lose so great an honour
   As one man more, methinks, would share from me
   For the best hope I have. O, do not wish one more!
   Rather proclaim it, Westmoreland, through my host,
   That he which hath no stomach to this fight,
   Let him depart; his passport shall be made
   And crowns for convoy put into his purse:
   We would not die in that man's company
   That fears his fellowship to die with us.
   This day is called the feast of Crispian:
   He that outlives this day, and comes safe home,
   Will stand a tip-toe when the day is named,
   And rouse him at the name of Crispian.
   He that shall live this day, and see old age,
   Will yearly on the vigil feast his neighbours,
   And say 'To-morrow is Saint Crispian:'
   Then will he strip his sleeve and show his scars.
   And say 'These wounds I had on Crispin's day.'
   Old men forget: yet all shall be forgot,
   But he'll remember with advantages
   What feats he did that day: then shall our names.
   Familiar in his mouth as household words
   Harry the king, Bedford and Exeter,
   Warwick and Talbot, Salisbury and Gloucester,

   Be in their flowing cups freshly remember'd.
   This story shall the good man teach his son;
   And Crispin Crispian shall ne'er go by,
   From this day to the ending of the world,
   But we in it shall be remember'd;
   We few, we happy few, we band of brothers;
   For he to-day that sheds his blood with me
   Shall be my brother; be he ne'er so vile,
   This day shall gentle his condition:
   And gentlemen in England now a-bed
   Shall think themselves accursed they were not here,
   And hold their manhoods cheap whiles any speaks
   That fought with us upon Saint Crispin's day.

                                   -- William Shakespeare

   This memo is a product of the IETF's Router Requirements Working
   Group.  A memo such as this one is of necessity the work of many more
   people than could be listed here.  A wide variety of vendors, network
   managers, and other experts from the Internet community graciously
   contributed their time and wisdom to improve the quality of this
   memo.  The editor wishes to extend sincere thanks to all of them.

   The current editor also wishes to single out and extend his heartfelt
   gratitude and appreciation to the original editor of this document;
   Philip Almquist.  Without Philip's work, both as the original editor
   and as the Chair of the working group, this document would not have
   been produced.  He also wishes to express deep and heartfelt
   gratitude to the previous editor, Frank Kastenholz.  Frank changed
   the original document from a collection of information to a useful
   description of IP technology - in his words, a "snapshot" of the
   technology in 1991.  One can only hope that this snapshot, of the
   technology in 1994, is as clear.

   Philip Almquist, Jeffrey Burgan, Frank Kastenholz, and Cathy
   Wittbrodt each wrote major chapters of this memo.  Others who made
   major contributions to the document included Bill Barns, Steve
   Deering, Kent England, Jim Forster, Martin Gross, Jeff Honig, Steve
   Knowles, Yoni Malachi, Michael Reilly, and Walt Wimer.

   Additional text came from Andy Malis, Paul Traina, Art Berggreen,
   John Cavanaugh, Ross Callon, John Lekashman, Brian Lloyd, Gary
   Malkin, Milo Medin, John Moy, Craig Partridge, Stephanie Price, Yakov
   Rekhter, Steve Senum, Richard Smith, Frank Solensky, Rich Woundy, and
   others who have been inadvertently overlooked.

   Some of the text in this memo has been (shamelessly) plagiarized from
   earlier documents, most notably RFC-1122 by Bob Braden and the Host

   Requirements Working Group, and RFC-1009 by Bob Braden and Jon
   Postel.  The work of these earlier authors is gratefully
   acknowledged.

   Jim Forster was a co-chair of the Router Requirements Working Group
   during its early meetings, and was instrumental in getting the group
   off to a good start.  Jon Postel, Bob Braden, and Walt Prue also
   contributed to the success by providing a wealth of good advice
   before the group's first meeting.  Later on, Phill Gross, Vint Cerf,
   and Noel Chiappa all provided valuable advice and support.

   Mike St.  Johns coordinated the Working Group's interactions with the
   security community, and Frank Kastenholz coordinated the Working
   Group's interactions with the network management area.  Allison
   Mankin and K.K.  Ramakrishnan provided expertise on the issues of
   congestion control and resource allocation.

   Many more people than could possibly be listed or credited here
   participated in the deliberations of the Router Requirements Working
   Group, either through electronic mail or by attending meetings.
   However, the efforts of Ross Callon and Vince Fuller in sorting out
   the difficult issues of route choice and route leaking are especially
   acknowledged.

   The editor thanks his employer, Cisco Systems, for allowing him to
   spend the time necessary to produce the 1994 snapshot.

Editor's Address

   The address of the current editor of this document is

      Fred Baker
      Cisco Systems
      519 Lado Drive
      Santa Barbara, California 93111
      USA

      Phone:+1 805-681-0115

      EMail: fred@cisco.com