tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 7868

Informational
Pages: 80
Top     in Index     Prev     Next
in Group Index     Prev in Group     No Next: Highest Number in Group     Group: ~cisco

Cisco's Enhanced Interior Gateway Routing Protocol (EIGRP)

Part 1 of 4, p. 1 to 20
None       Next RFC Part

 


Top       ToC       Page 1 
Independent Submission                                         D. Savage
Request for Comments: 7868                                         J. Ng
Category: Informational                                         S. Moore
ISSN: 2070-1721                                            Cisco Systems
                                                                D. Slice
                                                        Cumulus Networks
                                                               P. Paluch
                                                    University of Zilina
                                                                R. White
                                                                LinkedIn
                                                                May 2016


       Cisco's Enhanced Interior Gateway Routing Protocol (EIGRP)

Abstract

   This document describes the protocol design and architecture for
   Enhanced Interior Gateway Routing Protocol (EIGRP).  EIGRP is a
   routing protocol based on Distance Vector technology.  The specific
   algorithm used is called "DUAL", a Diffusing Update Algorithm as
   referenced in "Loop-Free Routing Using Diffusing Computations"
   (Garcia-Luna-Aceves 1993).  The algorithm and procedures were
   researched, developed, and simulated by SRI International.

Status of This Memo

   This document is not an Internet Standards Track specification; it is
   published for informational purposes.

   This is a contribution to the RFC Series, independently of any other
   RFC stream.  The RFC Editor has chosen to publish this document at
   its discretion and makes no statement about its value for
   implementation or deployment.  Documents approved for publication by
   the RFC Editor are not a candidate for any level of Internet
   Standard; see Section 2 of RFC 5741.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at
   http://www.rfc-editor.org/info/rfc7868.

Page 2 
Copyright Notice

   Copyright (c) 2016 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.

   This document may not be modified, and derivative works of it may not
   be created, except to format it for publication as an RFC or to
   translate it into languages other than English.

Table of Contents

   1. Introduction ....................................................5
   2. Conventions .....................................................5
      2.1. Requirements Language ......................................5
      2.2. Terminology ................................................5
   3. The Diffusing Update Algorithm (DUAL) ...........................9
      3.1. Algorithm Description ......................................9
      3.2. Route States ..............................................10
      3.3. Feasibility Condition .....................................11
      3.4. DUAL Message Types ........................................13
      3.5. DUAL Finite State Machine (FSM) ...........................13
      3.6. DUAL Operation -- Example Topology ........................18
   4. EIGRP Packets ..................................................20
      4.1. UPDATE Packets ............................................21
      4.2. QUERY Packets .............................................21
      4.3. REPLY Packets .............................................22
      4.4. Exception Handling ........................................22
           4.4.1. Active Duration (SIA) ..............................22
                  4.4.1.1. SIA-QUERY .................................23
                  4.4.1.2. SIA-REPLY .................................24
   5. EIGRP Operation ................................................25
      5.1. Finite State Machine ......................................25
      5.2. Reliable Transport Protocol ...............................25
           5.2.1. Bandwidth on Low-Speed Links .......................32
      5.3. Neighbor Discovery/Recovery ...............................32
           5.3.1. Neighbor Hold Time .................................32
           5.3.2. HELLO Packets ......................................33
           5.3.3. UPDATE Packets .....................................33
           5.3.4. Initialization Sequence ............................34
           5.3.5. Neighbor Formation .................................35
           5.3.6. QUERY Packets during Neighbor Formation ............35

Top      ToC       Page 3 
      5.4. Topology Table ............................................36
           5.4.1. Route Management ...................................36
                  5.4.1.1. Internal Routes ...........................37
                  5.4.1.2. External Routes ...........................37
           5.4.2. Split Horizon and Poison Reverse ...................38
                  5.4.2.1. Startup Mode ..............................38
                  5.4.2.2. Advertising Topology Table Change .........39
                  5.4.2.3. Sending a QUERY/UPDATE ....................39
      5.5. EIGRP Metric Coefficients .................................39
           5.5.1. Coefficients K1 and K2 .............................40
           5.5.2. Coefficient K3 .....................................40
           5.5.3. Coefficients K4 and K5 .............................40
           5.5.4. Coefficient K6 .....................................41
                  5.5.4.1. Jitter ....................................41
                  5.5.4.2. Energy ....................................41
      5.6. EIGRP Metric Calculations .................................41
           5.6.1. Classic Metrics ....................................41
                  5.6.1.1. Classic Composite Formulation .............42
                  5.6.1.2. Cisco Interface Delay Compatibility .......43
           5.6.2. Wide Metrics .......................................43
                  5.6.2.1. Wide Metric Vectors .......................44
                  5.6.2.2. Wide Metric Conversion Constants ..........45
                  5.6.2.3. Throughput Calculation ....................45
                  5.6.2.4. Latency Calculation .......................46
                  5.6.2.5. Composite Calculation .....................46
   6. EIGRP Packet Formats ...........................................46
      6.1. Protocol Number ...........................................46
      6.2. Protocol Assignment Encoding ..............................47
      6.3. Destination Assignment Encoding ...........................47
      6.4. EIGRP Communities Attribute ...............................48
      6.5. EIGRP Packet Header .......................................49
      6.6. EIGRP TLV Encoding Format .................................51
           6.6.1. Type Field Encoding ................................52
           6.6.2. Length Field Encoding ..............................52
           6.6.3. Value Field Encoding ...............................52
      6.7. EIGRP Generic TLV Definitions .............................52
           6.7.1. 0x0001 - PARAMETER_TYPE ............................53
           6.7.2. 0x0002 - AUTHENTICATION_TYPE .......................53
                  6.7.2.1. 0x02 - MD5 Authentication Type ............54
                  6.7.2.2. 0x03 - SHA2 Authentication Type ...........54
           6.7.3. 0x0003 - SEQUENCE_TYPE .............................54
           6.7.4. 0x0004 - SOFTWARE_VERSION_TYPE .....................55
           6.7.5. 0x0005 - MULTICAST_SEQUENCE_TYPE ...................55
           6.7.6. 0x0006 - PEER_INFORMATION_TYPE .....................55
           6.7.7. 0x0007 - PEER_ TERMINATION_TYPE ....................56
           6.7.8. 0x0008 - TID_LIST_TYPE .............................56
      6.8. Classic Route Information TLV Types .......................57
           6.8.1. Classic Flag Field Encoding ........................57

Top      ToC       Page 4 
           6.8.2. Classic Metric Encoding ............................57
           6.8.3. Classic Exterior Encoding ..........................58
           6.8.4. Classic Destination Encoding .......................59
           6.8.5. IPv4-Specific TLVs .................................59
                  6.8.5.1. IPv4 INTERNAL_TYPE ........................60
                  6.8.5.2. IPv4 EXTERNAL_TYPE ........................60
                  6.8.5.3. IPv4 COMMUNITY_TYPE .......................62
           6.8.6. IPv6-Specific TLVs .................................62
                  6.8.6.1. IPv6 INTERNAL_TYPE ........................63
                  6.8.6.2. IPv6 EXTERNAL_TYPE ........................63
                  6.8.6.3. IPv6 COMMUNITY_TYPE .......................65
      6.9. Multiprotocol Route Information TLV Types .................66
           6.9.1. TLV Header Encoding ................................66
           6.9.2. Wide Metric Encoding ...............................67
           6.9.3. Extended Metrics ...................................68
                  6.9.3.1. 0x00 - NoOp ...............................69
                  6.9.3.2. 0x01 - Scaled Metric ......................70
                  6.9.3.3. 0x02 - Administrator Tag ..................70
                  6.9.3.4. 0x03 - Community List .....................71
                  6.9.3.5. 0x04 - Jitter .............................71
                  6.9.3.6. 0x05 - Quiescent Energy ...................71
                  6.9.3.7. 0x06 - Energy .............................72
                  6.9.3.8. 0x07 - AddPath ............................72
                           6.9.3.8.1. AddPath with IPv4 Next Hop .....73
                           6.9.3.8.2. AddPath with IPv6 Next Hop .....74
           6.9.4. Exterior Encoding ..................................75
           6.9.5. Destination Encoding ...............................76
           6.9.6. Route Information ..................................76
                  6.9.6.1. INTERNAL TYPE .............................76
                  6.9.6.2. EXTERNAL TYPE .............................76
   7. Security Considerations ........................................77
   8. IANA Considerations ............................................77
   9. References .....................................................77
      9.1. Normative References ......................................77
      9.2. Informative References ....................................78
   Acknowledgments ...................................................79
   Authors' Addresses ................................................80

Top      ToC       Page 5 
1.  Introduction

   This document describes the Enhanced Interior Gateway Routing
   Protocol (EIGRP), a routing protocol designed and developed by Cisco
   Systems, Inc.  DUAL, the algorithm used to converge the control plane
   to a single set of loop-free paths is based on research conducted at
   SRI International [3].  The Diffusing Update Algorithm (DUAL) is the
   algorithm used to obtain loop freedom at every instant throughout a
   route computation [2].  This allows all routers involved in a
   topology change to synchronize at the same time; the routers not
   affected by topology changes are not involved in the recalculation.
   This document describes the protocol that implements these functions.

2.  Conventions

2.1.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [1].

2.2.  Terminology

   The following is a list of abbreviations and terms used throughout
   this document:

   ACTIVE State:
      The local state of a route on a router triggered by any event that
      causes all neighbors providing the current least-cost path to fail
      the Feasibility Condition check.  A route in Active state is
      considered unusable.  During Active state, the router is actively
      attempting to compute the least-cost loop-free path by explicit
      coordination with its neighbors using Query and Reply messages.

   Address Family Identifier (AFI):
      Identity of the network-layer protocol reachability information
      being advertised [12].

   Autonomous System (AS):
      A collection of routers exchanging routes under the control of one
      or more network administrators on behalf of a single
      administrative entity.

Top      ToC       Page 6 
   Base Topology:
      A routing domain representing a physical (non-virtual) view of the
      network topology consisting of attached devices and network
      segments EIGRP uses to form neighbor relationships.  Destinations
      exchanged within the Base Topology are identified with a Topology
      Identifier value of zero (0).

   Computed Distance (CD):
      Total distance (metric) along a path from the current router to a
      destination network through a particular neighbor computed using
      that neighbor's Reported Distance (RD) and the cost of the link
      between the two routers.  Exactly one CD is computed and
      maintained per the [Destination, Advertising Neighbor] pair.

   CR-Mode
      Conditionally Received Mode

   Diffusing Computation:
      A distributed computation in which a single starting node
      commences the computation by delegating subtasks of the
      computation to its neighbors that may, in turn, recursively
      delegate sub-subtasks further, including a signaling scheme
      allowing the starting node to detect that the computation has
      finished while avoiding false terminations.  In DUAL, the task of
      coordinated updates of routing tables and resulting best path
      computation is performed as a diffusing computation.

   Diffusing Update Algorithm (DUAL):
      A loop-free routing algorithm used with distance vectors or link
      states that provides a diffused computation of a routing table.
      It works very well in the presence of multiple topology changes
      with low overhead.  The technology was researched and developed at
      SRI International [3].

   Downstream Router:
      A router that is one or more hops away from the router in question
      in the direction of the destination.

   EIGRP:
      Enhanced Interior Gateway Routing Protocol.

   Feasibility Condition:
      The Feasibility Condition is a sufficient condition used by a
      router to verify whether a neighboring router provides a loop-free
      path to a destination.  EIGRP uses the Source Node Condition
      stating that a neighboring router meets the Feasibility Condition
      if the neighbor's RD is less than this router's Feasible Distance.

Top      ToC       Page 7 
   Feasible Distance (FD):
      Defined as the least-known total metric to a destination from the
      current router since the last transition from ACTIVE to PASSIVE
      state.  Being effectively a record of the smallest known metric
      since the last time the network entered the PASSIVE state, the FD
      is not necessarily a metric of the current best path.  Exactly one
      FD is computed per destination network.

   Feasible Successor:
      A neighboring router that meets the Feasibility Condition for a
      particular destination, hence, providing a guaranteed loop-free
      path.

   Neighbor/Peer:
      For a particular router, another router toward which an EIGRP
      session, also known as an "adjacency", is established.  The
      ability of two routers to become neighbors depends on their mutual
      connectivity and compatibility of selected EIGRP configuration
      parameters.  Two neighbors with interfaces connected to a common
      subnet are known as adjacent neighbors.  Two neighbors that are
      multiple hops apart are known as remote neighbors.

   PASSIVE state:
      The local state of a route in which at least one neighbor
      providing the current least-cost path passes the Feasibility
      Condition check.  A route in PASSIVE state is considered usable
      and not in need of a coordinated re-computation.

   Network Layer Reachability Information (NLRI):
      Information a router uses to calculate the global routing table to
      make routing and forwarding decisions.

   Reported Distance (RD):
      For a particular destination, the value representing the router's
      distance to the destination as advertised in all messages carrying
      routing information.  RD is not equivalent to the current distance
      of the router to the destination and may be different from it
      during the process of path re-computation.  Exactly one RD is
      computed and maintained per destination network.

   Sub-Topology:
      For a given Base Topology, a sub-topology is characterized by an
      independent set of routers and links in a network for which EIGRP
      performs an independent path calculation.  This allows each sub-
      topology to implement class-specific topologies to carry class-
      specific traffic.

Top      ToC       Page 8 
   Successor:
      For a particular destination, a neighboring router that meets the
      Feasibility Condition and, at the same time, provides the least-
      cost path.

   Stuck In Active (SIA):
      A destination that has remained in the ACTIVE State in excess of a
      predefined time period at the local router (Cisco implements this
      as 3 minutes).

   Successor-Directed Acyclic Graph (SDAG):
      For a particular destination, a graph defined by routing table
      contents of individual routers in the topology, such that nodes of
      this graph are the routers themselves and a directed edge from
      router X to router Y exists if and only if router Y is router X's
      successor.  After the network has converged, in the absence of
      topological changes, SDAG is a tree.

   Topology Change / Topology-Change Event:
      Any event that causes the CD for a destination through a neighbor
      to be added, modified, or removed.  As an example, detecting a
      link-cost change, receiving any EIGRP message from a neighbor
      advertising an updated neighbor's RD.

   Topology Identifier (TID):
      A number that is used to mark prefixes as belonging to a specific
      sub-topology.

   Topology Table:
      A data structure used by EIGRP to store information about every
      known destination including, but not limited to, network prefix /
      prefix length, FD, RD of each neighbor advertising the
      destination, CD over the corresponding neighbor, and route state.

   Type, Length, Value (TLV):
      An encoding format for information elements used in EIGRP messages
      to exchange information.  Each TLV-formatted information element
      consists of three generic fields: Type identifying the nature of
      information carried in this element, Length describing the length
      of the entire TLV triplet, and Value carrying the actual
      information.  The Value field may, itself, be internally
      structured; this depends on the actual type of the information
      element.  This format allows for extensibility and backward
      compatibility.

   Upstream Router:
      A router that is one or more hops away from the router in
      question, in the direction of the source of the information.

Top      ToC       Page 9 
   VID:
      VLAN Identifier

   Virtual Routing and Forwarding (VRF):
      Independent Virtual Private Network (VPN) routing/forwarding
      tables that coexist within the same router at the same time.

3.  The Diffusing Update Algorithm (DUAL)

   The Diffusing Update Algorithm (DUAL) constructs least-cost paths to
   all reachable destinations in a network consisting of nodes and edges
   (routers and links).  DUAL guarantees that each constructed path is
   loop free at every instant including periods of topology changes and
   network reconvergence.  This is accomplished by all routers, which
   are affected by a topology change, computing the new best path in a
   coordinated (diffusing) way and using the Feasibility Condition to
   verify prospective paths for loop freedom.  Routers that are not
   affected by topology changes are not involved in the recalculation.
   The convergence time with DUAL rivals that of any other existing
   routing protocol.

3.1.  Algorithm Description

   DUAL is used by EIGRP to achieve fast loop-free convergence with
   little overhead, allowing EIGRP to provide convergence rates
   comparable, and in some cases better than, most common link state
   protocols [10].  Only nodes that are affected by a topology change
   need to propagate and act on information about the topology change,
   allowing EIGRP to have good scaling properties, reduced overhead, and
   lower complexity than many other interior gateway protocols.

   Distributed routing algorithms are required to propagate information
   as well as coordinate information among all nodes in the network.
   Unlike basic Bellman-Ford distance vector protocols that rely on
   uncoordinated updates when a topology change occurs, DUAL uses a
   coordinated procedure to involve the affected part of the network
   into computing a new least-cost path, known as a "diffusing
   computation".  A diffusing computation grows by querying additional
   routers for their current RD to the affected destination, and it
   shrinks by receiving replies from them.  Unaffected routers send
   replies immediately, terminating the growth of the diffusing
   computation over them.  These intrinsic properties cause the
   diffusing computation to self-adjust in scope and terminate as soon
   as possible.

   One attribute of DUAL is its ability to control the point at which
   the diffusion of a route calculation terminates by managing the
   distribution of reachability information through the network.

Top      ToC       Page 10 
   Controlling the scope of the diffusing process is accomplished by
   hiding reachability information through aggregation (summarization),
   filtering, or other means.  This provides the ability to create
   effective failure domains within a single AS, and allows the network
   administrator to manage the convergence and processing
   characteristics of the network.

3.2.  Route States

   A route to a destination can be in one of two states: PASSIVE or
   ACTIVE.  These states describe whether the route is guaranteed to be
   both loop free and the shortest available (the PASSIVE state) or
   whether such a guarantee cannot be given (the ACTIVE state).
   Consequently, in PASSIVE state, the router does not perform any route
   recalculation in coordination with its neighbors because no such
   recalculation is needed.

   In ACTIVE state, the router is actively involved in re-computing the
   least-cost loop-free path in coordination with its neighbors.  The
   state is reevaluated and possibly changed every time a topology
   change is detected.  A topology change is any event that causes the
   CD to the destination over any neighbor to be added, changed, or
   removed from EIGRP's topology table.

   More exactly, the two states are defined as follows:

   o Passive

      A route is considered to be in the Passive state when at least one
      neighbor that provides the current least-total-cost path passes
      the Feasibility Condition check that guarantees loop freedom.  A
      route in the PASSIVE state is usable and its next hop is perceived
      to be a downstream router.

   o Active

      A route is considered to be in the ACTIVE state if neighbors that
      do not pass the Feasibility Condition check provide lowest-cost
      path, and therefore the path cannot be guaranteed loop free.  A
      route in the ACTIVE state is considered unusable and this router
      must coordinate with its neighbors in the search for the new loop-
      free least-total-cost path.

   In other words, for a route to be in PASSIVE state, at least one
   neighbor that provides the least-total-cost path must be a Feasible
   Successor.  Feasible Successors providing the least-total-cost path
   are also called "successors".  For a route to be in PASSIVE state, at
   least one successor must exist.

Top      ToC       Page 11 
   Conversely, if the path with the least total cost is provided by
   routers that are not Feasible Successors (and thus not successors),
   the route is in the ACTIVE state, requiring re-computation.

   Notably, for the definition of PASSIVE and ACTIVE states, it does not
   matter if there are Feasible Successors providing a worse-than-least-
   total-cost path.  While these neighbors are guaranteed to provide a
   loop-free path, that path is potentially not the shortest available.

   The fact that the least-total-cost path can be provided by a neighbor
   that fails the Feasibility Condition check may not be intuitive.
   However, such a situation can occur during topology changes when the
   current least-total-cost path fails and the next-least-total-cost
   path traverses a neighbor that is not a Feasible Successor.

   While a router has a route in the ACTIVE state, it must not change
   its successor (i.e., modify the current SDAG) nor modify its own
   Feasible Distance or RD until the route enters the PASSIVE state
   again.  Any updated information about this route received during
   ACTIVE state is reflected only in CDs.  Any updates to the successor,
   FD, and RD are postponed until the route returns to PASSIVE state.
   The state transitions from PASSIVE to ACTIVE and from ACTIVE to
   PASSIVE are controlled by the DUAL FSM and are described in detail in
   Section 3.5.

3.3.  Feasibility Condition

   The Feasibility Condition is a criterion used to verify loop freedom
   of a particular path.  The Feasibility Condition is a sufficient but
   not a necessary condition, meaning that every path meeting the
   Feasibility Condition is guaranteed to be loop free; however, not all
   loop-free paths meet the Feasibility Condition.

   The Feasibility Condition is used as an integral part of DUAL
   operation: every path selection in DUAL is subject to the Feasibility
   Condition check.  Based on the result of the Feasibility Condition
   check after a topology change is detected, the route may either
   remain PASSIVE (if, after the topology change, the neighbor providing
   the least cost path meets the Feasibility Condition) or it needs to
   enter the ACTIVE state (if the topology change resulted in none of
   the neighbors providing the least cost path to meet the Feasibility
   Condition).

   The Feasibility Condition is a part of DUAL that allows the diffused
   computation to terminate as early as possible.  Nodes that are not
   affected by the topology change are not required to perform a DUAL
   computation and may not be aware a topology change occurred.  This
   can occur in two cases:

Top      ToC       Page 12 
   First, if informed about a topology change, a router may keep a route
   in PASSIVE state if it is aware of other paths that are downstream
   towards the destination (routes meeting the Feasibility Condition).
   A route that meets the Feasibility Condition is determined to be loop
   free and downstream along the path between the router and the
   destination.

   Second, if informed about a topology change for which it does not
   currently have reachability information, a router is not required to
   enter into the ACTIVE state, nor is it required to participate in the
   DUAL process.

   In order to facilitate describing the Feasibility Condition, a few
   definitions are in order.

   o  A successor for a given route is the next hop used to forward data
      traffic for a destination.  Typically, the successor is chosen
      based on the least-cost path to reach the destination.

   o  A Feasible Successor is a neighbor that meets the Feasibility
      Condition.  A Feasible Successor is regarded as a downstream
      neighbor towards the destination, but it may not be the least-cost
      path but could still be used for forwarding data packets in the
      event equal or unequal cost load sharing was active.  A Feasible
      Successor can become a successor when the current successor
      becomes unreachable.

   o  The Feasibility Condition is met when a neighbor's advertised
      cost, (RD) to a destination is less than the FD for that
      destination, or in other words, the Feasibility Condition is met
      when the neighbor is closer to the destination than the router
      itself has ever been since the destination has entered the PASSIVE
      state for the last time.

   o  The FD is the lowest distance to the destination since the last
      time the route went from ACTIVE to PASSIVE state.  It should be
      noted it is not necessarily the current best distance; rather, it
      is a historical record of the best distance known since the last
      diffusing computation for the destination has finished.  Thus, the
      value of the FD can either be the same as the current best
      distance, or it can be lower.

   A neighbor that advertises a route with a cost that does not meet the
   Feasibility Condition may be upstream and thus cannot be guaranteed
   to be the next hop for a loop-free path.  Routes advertised by
   upstream neighbors are not recorded in the routing table but saved in
   the topology table.

Top      ToC       Page 13 
3.4.  DUAL Message Types

   DUAL operates with three basic message types: QUERY, UPDATE, and
   REPLY.

   o  UPDATE - sent to indicate a change in metric or an addition of a
      destination.

   o  QUERY - sent when the Feasibility Condition fails, which can
      happen for reasons like a destination becoming unreachable or the
      metric increasing to a value greater than its current FD.

   o REPLY - sent in response to a QUERY or SIA-QUERY

   In addition to these three basic types, two additional sub-types have
   been added to EIGRP:

   o  SIA-QUERY - sent when a REPLY has not been received within one-
      half of the SIA interval (90 seconds as implemented by Cisco).

   o  SIA-REPLY - sent in response to an SIA-QUERY indicating the route
      is still in ACTIVE state.  This response does not stratify the
      original QUERY; it is only used to indicate that the sending
      neighbor is still in the ACTIVE state for the given destination.

   When in the PASSIVE state, a received QUERY may be propagated if
   there is no Feasible Successor found.  If a Feasible Successor is
   found, the QUERY is not propagated and a REPLY is sent for the
   destination with a metric equal to the current routing table metric.
   When a QUERY is received from a non-successor in ACTIVE state, a
   REPLY is sent and the QUERY is not propagated.  The REPLY for the
   destination contains a metric equal to the current routing table
   metric.

3.5.  DUAL Finite State Machine (FSM)

   The DUAL FSM embodies the decision process for all route
   computations.  It tracks all routes advertised by all neighbors.  The
   distance information, known as a metric, is used by DUAL to select
   efficient loop-free paths.  DUAL selects routes to be inserted into a
   routing table based on Feasible Successors.  A successor is a
   neighboring router used for packet forwarding that has a least-cost
   path to a destination that is guaranteed not to be part of a routing
   loop.

   When there are no Feasible Successors but there are neighbors
   advertising the destination, a recalculation must occur to determine
   a new successor.

Top      ToC       Page 14 
   The amount of time it takes to calculate the route impacts the
   convergence time.  Even though the recalculation is not processor
   intensive, it is advantageous to avoid recalculation if it is not
   necessary.  When a topology change occurs, DUAL will test for
   Feasible Successors.  If there are Feasible Successors, it will use
   any it finds in order to avoid any unnecessary recalculation.

   The FSM, which applies per destination in the topology table,
   operates independently for each destination.  It is true that if a
   single link goes down, multiple routes may go into ACTIVE state.
   However, a separate SDAG is computed for each destination, so loop-
   free topologies can be maintained for each reachable destination.

Top      ToC       Page 15 
              +------------+                +-----------+
              |             \              /            |
              |              \            /             |
              |   +=================================+   |
              |   |                                 |   |
              |(1)|             Passive             |(2)|
              +-->|                                 |<--+
                  +=================================+
                      ^     |    ^    ^    ^    |
                  (14)|     |(15)|    |(13)|    |
                      |  (4)|    |(16)|    | (3)|
                      |     |    |    |    |    +------------+
                      |     |    |    |    |                  \
             +-------+      +    +    |    +-------------+     \
            /              /    /     |                   \     \
           /              /    /      +----+               \     \
          |               |   |            |                |     |
          |               v   |            |                |     v
      +==========+(11) +==========+     +==========+(12) +==========+
      |  Active  |---->|  Active  |(5)  |  Active  |---->|  Active  |
      |          |  (9)|          |---->|          | (10)|          |
      |  oij=0   |<----|  oij=1   |     |  oij=2   |<----|  oij=3   |
   +--|          |  +--|          |  +--|          |  +--|          |
   |  +==========+  |  +==========+  |  +==========+  |  +==========+
   |      ^   |(5)  |      ^         |    ^    ^      |         ^
   |      |   +-----|------|---------|----+    |      |         |
   +------+         +------+         +---------+      +---------+
   (6,7,8)          (6,7,8)            (6,7,8)          (6,7,8)

                      Figure 1: DUAL Finite State Machine

   Legend:

    i   Node that is computing route
    j   Destination node or network
    k   Any neighbor of node i
    oij QUERY origin flag
      0 = metric increase during ACTIVE state
      1 = node i originated
      2 = QUERY from, or link increase to, successor during ACTIVE state
      3 = QUERY originated from successor
    rijk REPLY status flag for each neighbor k for destination j
      1 = awaiting REPLY
      0 = received REPLY
    lik = the link connecting node i to neighbor k

Top      ToC       Page 16 
   The following describes in detail the state/event/action transitions
   of the DUAL FSM.  For all steps, the topology table is updated with
   the new metric information from either QUERY, REPLY, or UPDATE
   received.

   (1)  A QUERY is received from a neighbor that is not the current
        successor.  The route is currently in PASSIVE state.  As the
        successor is not affected by the QUERY, and a Feasible Successor
        exists, the route remains in PASSIVE state.  Since a Feasible
        Successor exists, a REPLY MUST be sent back to the originator of
        the QUERY.  Any metric received in the QUERY from that neighbor
        is recorded in the topology table and the Feasibility Check (FC)
        is run to check for any change to current successor.

   (2)  A directly connected interface changes state (connects,
        disconnects, or changes metric), or similarly an UPDATE or QUERY
        has been received with a metric change for an existing
        destination, the route will stay in the PASSIVE state if the
        current successor is not affected by the change, or it is no
        longer reachable and there is a Feasible Successor.  In either
        case, an UPDATE is sent with the new metric information if it
        has changed.

   (3)  A QUERY was received from a neighbor who is the current
        successor and no Feasible Successors exist.  The route for the
        destination goes into ACTIVE state.  A QUERY is sent to all
        neighbors on all interfaces that are not split horizon.  Split
        horizon takes effect for a query or update from the successor it
        is using for the destination in the query.  The QUERY origin
        flag is set to indicate the QUERY originated from a neighbor
        marked as successor for route.  The REPLY status flag is set for
        all neighbors to indicate outstanding replies.

   (4)  A directly connected link has gone down or its cost has
        increased, or an UPDATE has been received with a metric
        increase.  The route to the destination goes to ACTIVE state if
        there are no Feasible Successors found.  A QUERY is sent to all
        neighbors on all interfaces.  The QUERY origin flag is to
        indicate that the router originated the QUERY.  The REPLY status
        flag is set to 1 for all neighbors to indicate outstanding
        replies.

Top      ToC       Page 17 
   (5)  While a route for a destination is in ACTIVE state, and a QUERY
        is received from the current successor, the route remains in
        ACTIVE state.  The QUERY origin flag is set to indicate that
        there was another topology change while in ACTIVE state.  This
        indication is used so new Feasible Successors are compared to
        the metric that made the route go to ACTIVE state with the
        current successor.

   (6)  While a route for a destination is in ACTIVE state and a QUERY
        is received from a neighbor that is not the current successor, a
        REPLY should be sent to the neighbor.  The metric received in
        the QUERY should be recorded.

   (7)  If a link cost changes, or an UPDATE with a metric change is
        received in ACTIVE state from a non-successor, the router stays
        in ACTIVE state for the destination.  The metric information in
        the UPDATE is recorded.  When a route is in the ACTIVE state,
        neither a QUERY nor UPDATE are ever sent.

   (8)  If a REPLY for a destination, in ACTIVE state, is received from
        a neighbor or the link between a router and the neighbor fails,
        the router records that the neighbor replied to the QUERY.  The
        REPLY status flag is set to 0 to indicate this.  The route stays
        in ACTIVE state if there are more replies pending because the
        router has not heard from all neighbors.

   (9)  If a route for a destination is in ACTIVE state, and a link
        fails or a cost increase occurred between a router and its
        successor, the router treats this case like it has received a
        REPLY from its successor.  When this occurs after the router
        originates a QUERY, it sets the QUERY origin flag to indicate
        that another topology change occurred in ACTIVE state.

   (10) If a route for a destination is in ACTIVE state, and a link
        fails or a cost increase occurred between a router and its
        successor, the router treats this case like it has received a
        REPLY from its successor.  When this occurs after a successor
        originated a QUERY, the router sets the QUERY origin flag to
        indicate that another topology change occurred in ACTIVE state.

   (11) If a route for a destination is in ACTIVE state, the cost of the
        link through which the successor increases, and the last REPLY
        was received from all neighbors, but there is no Feasible
        Successor, the route should stay in ACTIVE state.  A QUERY is
        sent to all neighbors.  The QUERY origin flag is set to 1.

Top      ToC       Page 18 
   (12) If a route for a destination is in ACTIVE state because of a
        QUERY received from the current successor, and the last REPLY
        was received from all neighbors, but there is no Feasible
        Successor, the route should stay in ACTIVE state.  A QUERY is
        sent to all neighbors.  The QUERY origin flag is set to 3.

   (13) Received replies from all neighbors.  Since the QUERY origin
        flag indicates the successor originated the QUERY, it
        transitions to PASSIVE state and sends a REPLY to the old
        successor.

   (14) Received replies from all neighbors.  Since the QUERY origin
        flag indicates a topology change to the successor while in
        ACTIVE state, it need not send a REPLY to the old successor.
        When the Feasibility Condition is met, the route state
        transitions to PASSIVE.

   (15) Received replies from all neighbors.  Since the QUERY origin
        flag indicates either the router itself originated the QUERY or
        FC was not satisfied with the replies received in ACTIVE state,
        FD is reset to infinite value and the minimum of all the
        reported metrics is chosen as FD and route transitions back to
        PASSIVE state.  A REPLY is sent to the old-successor if oij
        flags indicate that there was a QUERY from successor.

   (16) If a route for a destination is in ACTIVE state because of a
        QUERY received from the current successor or there was an
        increase in distance while in ACTIVE state, the last REPLY was
        received from all neighbors, and a Feasible Successor exists for
        the destination, the route can go into PASSIVE state and a REPLY
        is sent to the successor if oij indicates that QUERY was
        received from the successor.

3.6.  DUAL Operation -- Example Topology

   The following topology (Figure 2) will be used to provide an example
   of how DUAL is used to reroute after a link failure.  Each node is
   labeled with its costs to destination N.  The arrows indicate the
   successor (next hop) used to reach destination N.  The least-cost
   path is selected.

Top      ToC       Page 19 
                                N
                                |
                             (1)A ---<--- B(2)
                                |         |
                                ^         |
                                |         |
                             (2)D ---<--- C(3)

                        Figure 2: Stable Topology

   In the case where the link between A and D fails (Figure 3);

          N                                   N
          |                                   |
          A ---<--- B                         A ---<--- B
          |         |                         |          |
          X         |                         ^          |
          |         |                         |          |
          D ---<--- C                         D ---<--- C
            Q->                                      <-R

                             N
                             |
                          (1)A ---<--- B(2)
                                       |
                                       ^
                                       |
                          (4)D --->--- C(3)

                  Figure 3: Link between A and D Fails


      Only observing the destination provided by node N, D enters the
   ACTIVE state and sends a QUERY to all its neighbors, in this case
   node C.
      C determines that it has a Feasible Successor and replies
   immediately with metric 3.
      C changes its old successor of D to its new single successor B
   and the route to N stays in PASSIVE state.
      D receives the REPLY and can transition out of ACTIVE state
   since it received replies from all its neighbors.
      D now has a viable path to N through C.
      D selects C as its successor to reach node N with a cost of 4.

   Notice that nodes A and B were not involved in the recalculation
   since they were not affected by the change.

Top      ToC       Page 20 
   Let's consider the situation in Figure 4, where Feasible Successors
   may not exist.  If the link between node A and B fails, B goes into
   ACTIVE state for destination N since it has no Feasible Successors.
   Node B sends a QUERY to node C.  C has no Feasible Successors, so it
   goes active for destination N; and since C has no neighbors, it
   replies to the QUERY, deletes the destination, and returns to the
   PASSIVE state for the unreachable route.  As C removes the (now
   unreachable) destination from its table, C sends REPLY to its old
   successor.  B receives this REPLY from C, and determines this is the
   last REPLY it is waiting on before determining what the new state of
   the route should be; on receiving this REPLY, B deletes the route to
   N from its routing table.

   Since B was the originator of the initial QUERY, it does not have to
   send a REPLY to its old successor (it would not be able to any ways,
   because the link to its old successor is down).  Note that nodes A
   and D were not involved in the recalculation since their successors
   were not affected.

          N                                N
          |                                |
       (1)A ---<--- B(2)                   A ------- B   Q
          |         |                      |         |   |^      ^
          ^         ^                      ^         |   v|      |
          |         |                      |         |      |    |
       (2)D         C(3)                   D         C     ACK   R


        Figure 4: No Feasible Successors When Link between A and B Fails



(page 20 continued on part 2)

Next RFC Part