home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc1654 < prev    next >
Text File  |  1994-07-20  |  130KB  |  3,140 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                         Y. Rekhter
  8. Request for Comments: 1654        T.J. Watson Research Center, IBM Corp.
  9. Category: Standards Track                                          T. Li
  10.                                                            cisco Systems
  11.                                                                  Editors
  12.                                                                July 1994
  13.  
  14.  
  15.                   A Border Gateway Protocol 4 (BGP-4)
  16.  
  17. Status of this Memo
  18.  
  19.    This document specifies an Internet standards track protocol for the
  20.    Internet community, and requests discussion and suggestions for
  21.    improvements.  Please refer to the current edition of the "Internet
  22.    Official Protocol Standards" (STD 1) for the standardization state
  23.    and status of this protocol.  Distribution of this memo is unlimited.
  24.  
  25. 1. Acknowledgements
  26.  
  27.    This document was originally published as RFC 1267 in October 1991,
  28.    jointly authored by Kirk Lougheed (cisco Systems) and Yakov Rekhter
  29.    (IBM).
  30.  
  31.    We would like to express our thanks to Guy Almes (Rice University),
  32.    Len Bosack (cisco Systems), and Jeffrey C. Honig (Cornell University)
  33.    for their contributions to the earlier version of this document.
  34.  
  35.    We like to explicitly thank Bob Braden (ISI) for the review of the
  36.    earlier version of this document as well as his constructive and
  37.    valuable comments.
  38.  
  39.    We would also like to thank Bob Hinden, Director for Routing of the
  40.    Internet Engineering Steering Group, and the team of reviewers he
  41.    assembled to review the previous version (BGP-2) of this document.
  42.    This team, consisting of Deborah Estrin, Milo Medin, John Moy, Radia
  43.    Perlman, Martha Steenstrup, Mike St. Johns, and Paul Tsuchiya, acted
  44.    with a strong combination of toughness, professionalism, and
  45.    courtesy.
  46.  
  47.    This updated version of the document is the product of the IETF BGP
  48.    Working Group with Yakov Rekhter and Tony Li as editors. Certain
  49.    sections of the document borrowed heavily from IDRP [7], which is the
  50.    OSI counterpart of BGP. For this credit should be given to the ANSI
  51.    X3S3.3 group chaired by Lyman Chapin (BBN) and to Charles Kunzinger
  52.    (IBM Corp.) who was the IDRP editor within that group.  We would also
  53.    like to thank Mike Craren (Proteon, Inc.), Dimitry Haskin
  54.    (Wellfleet), John Krawczyk (Wellfleet), and Paul Traina (cisco) for
  55.  
  56.  
  57.  
  58. Rekhter & Li                                                    [Page 1]
  59.  
  60. RFC 1654                         BGP-4                         July 1994
  61.  
  62.  
  63.    their insightful comments.
  64.  
  65.    We would like to specially acknowledge numerous contributions by
  66.    Dennis Ferguson (ANS).
  67.  
  68. 2.  Introduction
  69.  
  70.    The Border Gateway Protocol (BGP) is an inter-Autonomous System
  71.    routing protocol.  It is built on experience gained with EGP as
  72.    defined in RFC 904 [1] and EGP usage in the NSFNET Backbone as
  73.    described in RFC 1092 [2] and RFC 1093 [3].
  74.  
  75.    The primary function of a BGP speaking system is to exchange network
  76.    reachability information with other BGP systems.  This network
  77.    reachability information includes information on the list of
  78.    Autonomous Systems (ASs) that reachability information traverses.
  79.    This information is sufficient to construct a graph of AS
  80.    connectivity from which routing loops may be pruned and some policy
  81.    decisions at the AS level may be enforced.
  82.  
  83.    BGP-4 provides a new set of mechanisms for supporting classless
  84.    interdomain routing.  These mechanisms include support for
  85.    advertising an IP prefix and eliminates the concept of network
  86.    "class" within BGP.  BGP-4 also introduces mechanisms which allow
  87.    aggregation of routes, including aggregation of AS paths.  These
  88.    changes provide support for the proposed supernetting scheme [8, 9].
  89.  
  90.    To characterize the set of policy decisions that can be enforced
  91.    using BGP, one must focus on the rule that a BGP speaker advertise to
  92.    its peers (other BGP speakers which it communicates with) in
  93.    neighboring ASs only those routes that it itself uses.  This rule
  94.    reflects the "hop-by-hop" routing paradigm generally used throughout
  95.    the current Internet.  Note that some policies cannot be supported by
  96.    the "hop-by-hop" routing paradigm and thus require techniques such as
  97.    source routing to enforce.  For example, BGP does not enable one AS
  98.    to send traffic to a neighboring AS intending that the traffic take a
  99.    different route from that taken by traffic originating in the
  100.    neighboring AS.  On the other hand, BGP can support any policy
  101.    conforming to the "hop-by-hop" routing paradigm.  Since the current
  102.    Internet uses only the "hop-by-hop" routing paradigm and since BGP
  103.    can support any policy that conforms to that paradigm, BGP is highly
  104.    applicable as an inter-AS routing protocol for the current Internet.
  105.  
  106.    A more complete discussion of what policies can and cannot be
  107.    enforced with BGP is outside the scope of this document (but refer to
  108.    the companion document discussing BGP usage [5]).
  109.  
  110.  
  111.  
  112.  
  113.  
  114. Rekhter & Li                                                    [Page 2]
  115.  
  116. RFC 1654                         BGP-4                         July 1994
  117.  
  118.  
  119.    BGP runs over a reliable transport protocol.  This eliminates the
  120.    need to implement explicit update fragmentation, retransmission,
  121.    acknowledgement, and sequencing.  Any authentication scheme used by
  122.    the transport protocol may be used in addition to BGP's own
  123.    authentication mechanisms.  The error notification mechanism used in
  124.    BGP assumes that the transport protocol supports a "graceful" close,
  125.    i.e., that all outstanding data will be delivered before the
  126.    connection is closed.
  127.  
  128.    BGP uses TCP [4] as its transport protocol.  TCP meets BGP's
  129.    transport requirements and is present in virtually all commercial
  130.    routers and hosts.  In the following descriptions the phrase
  131.    "transport protocol connection" can be understood to refer to a TCP
  132.    connection.  BGP uses TCP port 179 for establishing its connections.
  133.  
  134.    This memo uses the term `Autonomous System' (AS) throughout.  The
  135.    classic definition of an Autonomous System is a set of routers under
  136.    a single technical administration, using an interior gateway protocol
  137.    and common metrics to route packets within the AS, and using an
  138.    exterior gateway protocol to route packets to other ASs.  Since this
  139.    classic definition was developed, it has become common for a single
  140.    AS to use several interior gateway protocols and sometimes several
  141.    sets of metrics within an AS.  The use of the term Autonomous System
  142.    here stresses the fact that, even when multiple IGPs and metrics are
  143.    used, the administration of an AS appears to other ASs to have a
  144.    single coherent interior routing plan and presents a consistent
  145.    picture of what networks are reachable through it.
  146.  
  147.    The planned use of BGP in the Internet environment, including such
  148.    issues as topology, the interaction between BGP and IGPs, and the
  149.    enforcement of routing policy rules is presented in a companion
  150.    document [5].  This document is the first of a series of documents
  151.    planned to explore various aspects of BGP application.  Please send
  152.    comments to the BGP mailing list (iwg@ans.net).
  153.  
  154. 3.  Summary of Operation
  155.  
  156.    Two systems form a transport protocol connection between one another.
  157.    They exchange messages to open and confirm the connection parameters.
  158.    The initial data flow is the entire BGP routing table.  Incremental
  159.    updates are sent as the routing tables change.  BGP does not require
  160.    periodic refresh of the entire BGP routing table.  Therefore, a BGP
  161.    speaker must retain the current version of the entire BGP routing
  162.    tables of all of its peers for the duration of the connection.
  163.    KeepAlive messages are sent periodically to ensure the liveness of
  164.    the connection.  Notification messages are sent in response to errors
  165.    or special conditions.  If a connection encounters an error
  166.    condition, a notification message is sent and the connection is
  167.  
  168.  
  169.  
  170. Rekhter & Li                                                    [Page 3]
  171.  
  172. RFC 1654                         BGP-4                         July 1994
  173.  
  174.  
  175.    closed.
  176.  
  177.    The hosts executing the Border Gateway Protocol need not be routers.
  178.    A non-routing host could exchange routing information with routers
  179.    via EGP or even an interior routing protocol.  That non-routing host
  180.    could then use BGP to exchange routing information with a border
  181.    router in another Autonomous System.  The implications and
  182.    applications of this architecture are for further study.
  183.  
  184.    If a particular AS has multiple BGP speakers and is providing transit
  185.    service for other ASs, then care must be taken to ensure a consistent
  186.    view of routing within the AS.  A consistent view of the interior
  187.    routes of the AS is provided by the interior routing protocol.  A
  188.    consistent view of the routes exterior to the AS can be provided by
  189.    having all BGP speakers within the AS maintain direct BGP connections
  190.    with each other.  Using a common set of policies, the BGP speakers
  191.    arrive at an agreement as to which border routers will serve as
  192.    exit/entry points for particular networks outside the AS.  This
  193.    information is communicated to the AS's internal routers, possibly
  194.    via the interior routing protocol.  Care must be taken to ensure that
  195.    the interior routers have all been updated with transit information
  196.    before the BGP speakers announce to other ASs that transit service is
  197.    being provided.
  198.  
  199.    Connections between BGP speakers of different ASs are referred to as
  200.    "external" links.  BGP connections between BGP speakers within the
  201.    same AS are referred to as "internal" links.  Similarly, a peer in a
  202.    different AS is referred to as an external peer, while a peer in the
  203.    same AS may be described as an internal peer.
  204.  
  205. 3.1 Routes: Advertisement and Storage
  206.  
  207.    For purposes of this protocol a route is defined as a unit of
  208.    information that pairs a destination with the attributes of a path to
  209.    that destination:
  210.  
  211.       - Routes are advertised between a pair of BGP speakers in UPDATE
  212.       messages: the destination is the systems whose IP addresses are
  213.       reported in the Network Layer Reachability Information (NLRI)
  214.       field, and the the path is the information reported in the path
  215.       attributes fields of the same UPDATE message.
  216.  
  217.       - Routes are stored in the Routing Information Bases (RIBs):
  218.       namely, the Adj-RIBs-In, the Loc-RIB, and the Adj-RIBs-Out. Routes
  219.       that will be advertised to other BGP speakers must be present in
  220.       the Adj-RIB-Out; routes that will be used by the local BGP speaker
  221.       must be present in the Loc-RIB, and the next hop for each of these
  222.       routes must be present in the local BGP speaker's forwarding
  223.  
  224.  
  225.  
  226. Rekhter & Li                                                    [Page 4]
  227.  
  228. RFC 1654                         BGP-4                         July 1994
  229.  
  230.  
  231.       information base; and routes that are received from other BGP
  232.       speakers are present in the Adj-RIBs-In.
  233.  
  234.    If a BGP speaker chooses to advertise the route, it may add to or
  235.    modify the path attributes of the route before advertising it to a
  236.    peer.
  237.  
  238.    BGP provides mechanisms by which a BGP speaker can inform its peer
  239.    that a previously advertised route is no longer available for use.
  240.    There are three methods by which a given BGP speaker can indicate
  241.    that a route has been withdrawn from service:
  242.  
  243.       a) the IP prefix that expresses destinations for a previously
  244.       advertised route can be advertised in the WITHDRAWN ROUTES field
  245.       in the UPDATE message, thus marking the associated route as being
  246.       no longer available for use
  247.  
  248.       b) a replacement route with the same Network Layer Reachability
  249.       Information can be advertised, or
  250.  
  251.       c) the BGP speaker - BGP speaker connection can be closed, which
  252.       implicitly removes from service all routes which the pair of
  253.       speakers had advertised to each other.
  254.  
  255. 3.2 Routing Information Bases
  256.  
  257.    The Routing Information Base (RIB) within a BGP speaker consists of
  258.    three distinct parts:
  259.  
  260.       a) Adj-RIBs-In: The Adj-RIBs-In store routing information that has
  261.       been learned from inbound UPDATE messages. Their contents
  262.       represent routes that are available as an input to the Decision
  263.       Process.
  264.  
  265.       b) Loc-RIB: The Loc-RIB contains the local routing information
  266.       that the BGP speaker has selected by applying its local policies
  267.       to the routing information contained in its Adj-RIBs-In.
  268.  
  269.       c) Adj-RIBs-Out: The Adj-RIBs-Out store the information that the
  270.       local BGP speaker has selected for advertisement to its peers. The
  271.       routing information stored in the Adj-RIBs-Out will be carried in
  272.       the local BGP speaker's UPDATE messages and advertised to its
  273.       peers.
  274.  
  275.    In summary, the Adj-RIBs-In contain unprocessed routing information
  276.    that has been advertised to the local BGP speaker by its peers; the
  277.    Loc-RIB contains the routes that have been selected by the local BGP
  278.    speaker's Decision Process; and the Adj-RIBs-Out organize the routes
  279.  
  280.  
  281.  
  282. Rekhter & Li                                                    [Page 5]
  283.  
  284. RFC 1654                         BGP-4                         July 1994
  285.  
  286.  
  287.    for advertisement to specific peers by means of the local speaker's
  288.    UPDATE messages.
  289.  
  290.    Although the conceptual model distinguishes between Adj-RIBs-In,
  291.    Loc-RIB, and Adj-RIBs-Out, this neither implies nor requires that an
  292.    implementation must maintain three separate copies of the routing
  293.    information. The choice of implementation (for example, 3 copies of
  294.    the information vs 1 copy with pointers) is not constrained by the
  295.    protocol.
  296.  
  297. 4.  Message Formats
  298.  
  299.    This section describes message formats used by BGP.
  300.  
  301.    Messages are sent over a reliable transport protocol connection.  A
  302.    message is processed only after it is entirely received.  The maximum
  303.    message size is 4096 octets.  All implementations are required to
  304.    support this maximum message size.  The smallest message that may be
  305.    sent consists of a BGP header without a data portion, or 19 octets.
  306.  
  307. 4.1 Message Header Format
  308.  
  309.    Each message has a fixed-size header.  There may or may not be a data
  310.    portion following the header, depending on the message type.  The
  311.    layout of these fields is shown below:
  312.  
  313.        0                   1                   2                   3
  314.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  315.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  316.       |                                                               |
  317.       +                                                               +
  318.       |                                                               |
  319.       +                                                               +
  320.       |                           Marker                              |
  321.       +                                                               +
  322.       |                                                               |
  323.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  324.       |          Length               |      Type     |
  325.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  326.  
  327.       Marker:
  328.  
  329.          This 16-octet field contains a value that the receiver of the
  330.          message can predict.  If the Type of the message is OPEN, or if
  331.          the Authentication Code used in the OPEN message of the
  332.          connection is zero, then the Marker must be all ones.
  333.          Otherwise, the value of the marker can be predicted by some a
  334.          computation specified as part of the authentication mechanism
  335.  
  336.  
  337.  
  338. Rekhter & Li                                                    [Page 6]
  339.  
  340. RFC 1654                         BGP-4                         July 1994
  341.  
  342.  
  343.          used.  The Marker can be used to detect loss of synchronization
  344.          between a pair of BGP peers, and to authenticate incoming BGP
  345.          messages.
  346.  
  347.       Length:
  348.  
  349.          This 2-octet unsigned integer indicates the total length of the
  350.          message, including the header, in octets.  Thus, e.g., it
  351.          allows one to locate in the transport-level stream the (Marker
  352.          field of the) next message.  The value of the Length field must
  353.          always be at least 19 and no greater than 4096, and may be
  354.          further constrained, depending on the message type.  No
  355.          "padding" of extra data after the message is allowed, so the
  356.          Length field must have the smallest value required given the
  357.          rest of the message.
  358.  
  359.       Type:
  360.  
  361.          This 1-octet unsigned integer indicates the type code of the
  362.          message.  The following type codes are defined:
  363.  
  364.                                     1 - OPEN
  365.                                     2 - UPDATE
  366.                                     3 - NOTIFICATION
  367.                                     4 - KEEPALIVE
  368.  
  369. 4.2 OPEN Message Format
  370.  
  371.    After a transport protocol connection is established, the first
  372.    message sent by each side is an OPEN message.  If the OPEN message is
  373.    acceptable, a KEEPALIVE message confirming the OPEN is sent back.
  374.    Once the OPEN is confirmed, UPDATE, KEEPALIVE, and NOTIFICATION
  375.    messages may be exchanged.
  376.  
  377.    In addition to the fixed-size BGP header, the OPEN message contains
  378.    the following fields:
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394. Rekhter & Li                                                    [Page 7]
  395.  
  396. RFC 1654                         BGP-4                         July 1994
  397.  
  398.  
  399.         0                   1                   2                   3
  400.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  401.        +-+-+-+-+-+-+-+-+
  402.        |    Version    |
  403.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  404.        |     My Autonomous System      |
  405.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  406.        |           Hold Time           |
  407.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  408.        |                         BGP Identifier                        |
  409.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  410.        |  Auth. Code   |
  411.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  412.        |                                                               |
  413.        |                       Authentication Data                     |
  414.        |                                                               |
  415.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  416.  
  417.       Version:
  418.  
  419.          This 1-octet unsigned integer indicates the protocol version
  420.          number of the message.  The current BGP version number is 4.
  421.  
  422.       My Autonomous System:
  423.  
  424.          This 2-octet unsigned integer indicates the Autonomous System
  425.          number of the sender.
  426.  
  427.       Hold Time:
  428.  
  429.          This 2-octet unsigned integer indicates the number of seconds
  430.          that the sender proposes for the value of the Hold Timer.  Upon
  431.          receipt of an OPEN message, a BGP speaker MUST calculate the
  432.          value of the Hold Timer by using the smaller of its configured
  433.          Hold Time and the Hold Time received in the OPEN message.  The
  434.          Hold Time MUST be either zero or at least three seconds.  An
  435.          implementation may reject connections on the basis of the Hold
  436.          Time.  The calculated value indicates the maximum number of
  437.          seconds that may elapse between the receipt of successive
  438.          KEEPALIVE, and/or UPDATE messages by the sender.
  439.  
  440.       BGP Identifier:
  441.  
  442.          This 4-octet unsigned integer indicates the BGP Identifier of
  443.          the sender. A given BGP speaker sets the value of its BGP
  444.          Identifier to an IP address assigned to that BGP speaker.  The
  445.          value of the BGP Identifier is determined on startup and is the
  446.          same for every local interface and every BGP peer.
  447.  
  448.  
  449.  
  450. Rekhter & Li                                                    [Page 8]
  451.  
  452. RFC 1654                         BGP-4                         July 1994
  453.  
  454.  
  455.       Authentication Code:
  456.  
  457.          This 1-octet unsigned integer indicates the authentication
  458.          mechanism being used.  Whenever an authentication mechanism is
  459.          specified for use within BGP, three things must be included in
  460.          the specification:
  461.  
  462.          - the value of the Authentication Code which indicates use of
  463.            the mechanism,
  464.          - the form and meaning of the Authentication Data, and
  465.          - the algorithm for computing values of Marker fields.  Only
  466.            one authentication mechanism is specified as part of this
  467.            memo:
  468.          - its Authentication Code is zero,
  469.          - its Authentication Data must be empty (of zero length), and
  470.          - the Marker fields of all messages must be all ones.  The
  471.            semantics of non-zero Authentication Codes lies outside the
  472.            scope of this memo.
  473.  
  474.          Note that a separate authentication mechanism may be used in
  475.          establishing the transport level connection.
  476.  
  477.       Authentication Data:
  478.  
  479.          The form and meaning of this field is a variable-length field
  480.          depend on the Authentication Code.  If the value of
  481.          Authentication Code field is zero, the Authentication Data
  482.          field must have zero length.  The semantics of the non-zero
  483.          length Authentication Data field is outside the scope of this
  484.          memo.
  485.  
  486.          Note that the length of the Authentication Data field can be
  487.          determined from the message Length field by the formula:
  488.  
  489.             Message Length = 29 + Authentication Data Length
  490.  
  491.          The minimum length of the OPEN message is 29 octets (including
  492.          message header).
  493.  
  494. 4.3 UPDATE Message Format
  495.  
  496.    UPDATE messages are used to transfer routing information between BGP
  497.    peers.  The information in the UPDATE packet can be used to construct
  498.    a graph describing the relationships of the various Autonomous
  499.    Systems.  By applying rules to be discussed, routing information
  500.    loops and some other anomalies may be detected and removed from
  501.    inter-AS routing.
  502.  
  503.  
  504.  
  505.  
  506. Rekhter & Li                                                    [Page 9]
  507.  
  508. RFC 1654                         BGP-4                         July 1994
  509.  
  510.  
  511.    An UPDATE message is used to advertise a single feasible route to a
  512.    peer, or to withdraw multiple unfeasible routes from service (see
  513.    3.1). An UPDATE message may simultaneously advertise a feasible route
  514.    and withdraw multiple unfeasible routes from service.  The UPDATE
  515.    message always includes the fixed-size BGP header, and can optionally
  516.    include the other fields as shown below:
  517.  
  518.       +-----------------------------------------------------+
  519.       |   Unfeasible Routes Length (2 octets)               |
  520.       +-----------------------------------------------------+
  521.       |  Withdrawn Routes (variable)                        |
  522.       +-----------------------------------------------------+
  523.       |   Total Path Attribute Length (2 octets)            |
  524.       +-----------------------------------------------------+
  525.       |    Path Attributes (variable)                       |
  526.       +-----------------------------------------------------+
  527.       |   Network Layer Reachability Information (variable) |
  528.       +-----------------------------------------------------+
  529.  
  530.       Unfeasible Routes Length:
  531.  
  532.          This 2-octets unsigned integer indicates the total length of
  533.          the Withdrawn Routes field in octets.  Its value must allow the
  534.          length of the Network Layer Reachability Information field to
  535.          be determined as specified below.
  536.  
  537.          A value of 0 indicates that no routes are being withdrawn from
  538.          service, and that the WITHDRAWN ROUTES field is not present in
  539.          this UPDATE message.
  540.  
  541.       Withdrawn Routes:
  542.  
  543.  
  544.          This is a variable length field that contains a list of IP
  545.          address prefixes for the routes that are being withdrawn from
  546.          service.  Each IP address prefix is encoded as a 2-tuple of the
  547.          form <length, prefix>, whose fields are described below:
  548.  
  549.                   +---------------------------+
  550.                   |   Length (1 octet)        |
  551.                   +---------------------------+
  552.                   |   Prefix (variable)       |
  553.                   +---------------------------+
  554.  
  555.  
  556.  
  557.  
  558.  
  559.  
  560.  
  561.  
  562. Rekhter & Li                                                   [Page 10]
  563.  
  564. RFC 1654                         BGP-4                         July 1994
  565.  
  566.  
  567.          The use and the meaning of these fields are as follows:
  568.  
  569.          a) Length:
  570.  
  571.             The Length field indicates the length in bits of the IP
  572.             address prefix. A length of zero indicates a prefix that
  573.             matches all IP addresses (with prefix, itself, of zero
  574.             octets).
  575.  
  576.          b) Prefix:
  577.  
  578.             The Prefix field contains IP address prefixes followed by
  579.             enough trailing bits to make the end of the field fall on an
  580.             octet boundary. Note that the value of trailing bits is
  581.             irrelevant.
  582.  
  583.       Total Path Attribute Length:
  584.  
  585.          This 2-octet unsigned integer indicates the total length of the
  586.          Path Attributes field in octets.  Its value must allow the
  587.          length of the Network Layer Reachability field to be determined
  588.          as specified below.
  589.  
  590.          A value of 0 indicates that no Network Layer Reachability
  591.          Information field is present in this UPDATE message.
  592.  
  593.       Path Attributes:
  594.  
  595.          A variable length sequence of path attributes is present in
  596.          every UPDATE.  Each path attribute is a triple <attribute type,
  597.          attribute length, attribute value> of variable length.
  598.  
  599.          Attribute Type is a two-octet field that consists of the
  600.          Attribute Flags octet followed by the Attribute Type Code
  601.          octet.
  602.  
  603.                 0                   1
  604.                 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  605.                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  606.                |  Attr. Flags  |Attr. Type Code|
  607.                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  608.  
  609.          The high-order bit (bit 0) of the Attribute Flags octet is the
  610.          Optional bit.  It defines whether the attribute is optional (if
  611.          set to 1) or well-known (if set to 0).
  612.  
  613.          The second high-order bit (bit 1) of the Attribute Flags octet
  614.          is the Transitive bit.  It defines whether an optional
  615.  
  616.  
  617.  
  618. Rekhter & Li                                                   [Page 11]
  619.  
  620. RFC 1654                         BGP-4                         July 1994
  621.  
  622.  
  623.          attribute is transitive (if set to 1) or non-transitive (if set
  624.          to 0).  For well-known attributes, the Transitive bit must be
  625.          set to 1.  (See Section 5 for a discussion of transitive
  626.          attributes.)
  627.  
  628.          The third high-order bit (bit 2) of the Attribute Flags octet
  629.          is the Partial bit.  It defines whether the information
  630.          contained in the optional transitive attribute is partial (if
  631.          set to 1) or complete (if set to 0).  For well-known attributes
  632.          and for optional non-transitive attributes the Partial bit must
  633.          be set to 0.
  634.  
  635.          The fourth high-order bit (bit 3) of the Attribute Flags octet
  636.          is the Extended Length bit.  It defines whether the Attribute
  637.          Length is one octet (if set to 0) or two octets (if set to 1).
  638.          Extended Length may be used only if the length of the attribute
  639.          value is greater than 255 octets.
  640.  
  641.          The lower-order four bits of the Attribute Flags octet are .
  642.          unused. They must be zero (and must be ignored when received).
  643.  
  644.          The Attribute Type Code octet contains the Attribute Type Code.
  645.          Currently defined Attribute Type Codes are discussed in Section
  646.          5.
  647.  
  648.          If the Extended Length bit of the Attribute Flags octet is set
  649.          to 0, the third octet of the Path Attribute contains the length
  650.          of the attribute data in octets.
  651.  
  652.          If the Extended Length bit of the Attribute Flags octet is set
  653.          to 1, then the third and the fourth octets of the path
  654.          attribute contain the length of the attribute data in octets.
  655.  
  656.          The remaining octets of the Path Attribute represent the
  657.          attribute value and are interpreted according to the Attribute
  658.          Flags and the Attribute Type Code. The supported Attribute Type
  659.          Codes, their attribute values and uses are the following:
  660.  
  661.          a)   ORIGIN (Type Code 1):
  662.  
  663.             ORIGIN is a well-known mandatory attribute that defines the
  664.             origin of the path information.   The data octet can assume
  665.             the following values:
  666.  
  667.  
  668.  
  669.  
  670.  
  671.  
  672.  
  673.  
  674. Rekhter & Li                                                   [Page 12]
  675.  
  676. RFC 1654                         BGP-4                         July 1994
  677.  
  678.  
  679.                   Value      Meaning
  680.  
  681.                   0         IGP - Network Layer Reachability Information
  682.                                is interior to the originating AS
  683.  
  684.                   1         EGP - Network Layer Reachability Information
  685.                                learned via EGP
  686.  
  687.                   2         INCOMPLETE - Network Layer Reachability
  688.                                Information learned by some other means
  689.  
  690.             Its usage is defined in 5.1.1
  691.  
  692.          b) AS_PATH (Type Code 2):
  693.  
  694.             AS_PATH is a well-known mandatory attribute that is composed
  695.             of a sequence of AS path segments. Each AS path segment is
  696.             represented by a triple <path segment type, path segment
  697.             length, path segment value>.
  698.  
  699.             The path segment type is a 1-octet long field with the
  700.             following values defined:
  701.  
  702.                   Value      Segment Type
  703.  
  704.                   1         AS_SET: unordered set of ASs a route in the
  705.                                UPDATE message has traversed
  706.  
  707.                   2         AS_SEQUENCE: ordered set of ASs a route in
  708.                                the UPDATE message has traversed
  709.  
  710.             The path segment length is a 1-octet long field containing
  711.             the number of ASs in the path segment value field.
  712.  
  713.             The path segment value field contains one or more AS
  714.             numbers, each encoded as a 2-octets long field.
  715.  
  716.             Usage of this attribute is defined in 5.1.2.
  717.  
  718.          c)   NEXT_HOP (Type Code 3):
  719.  
  720.             This is a well-known mandatory attribute that defines the IP
  721.             address of the border router that should be used as the next
  722.             hop to the destinations listed in the Network Layer
  723.             Reachability field of the UPDATE message.
  724.  
  725.             Usage of this attribute is defined in 5.1.3.
  726.  
  727.  
  728.  
  729.  
  730. Rekhter & Li                                                   [Page 13]
  731.  
  732. RFC 1654                         BGP-4                         July 1994
  733.  
  734.  
  735.          d) MULTI_EXIT_DISC (Type Code 4):
  736.  
  737.             This is an optional non-transitive attribute that is a four
  738.             octet non-negative integer. The value of this attribute may
  739.             be used by a BGP speaker's decision process to discriminate
  740.             among multiple exit points to a neighboring autonomous
  741.             system.
  742.  
  743.             Its usage is defined in 5.1.4.
  744.  
  745.          e) LOCAL_PREF (Type Code 5):
  746.  
  747.             LOCAL_PREF is a well-known discretionary attribute that is a
  748.             four octet non-negative integer. It is used by a BGP speaker
  749.             to inform other BGP speakers in its own autonomous system of
  750.             the originating speaker's degree of preference for an
  751.             advertised route. Usage of this attribute is described in
  752.             5.1.5.
  753.  
  754.          f) ATOMIC_AGGREGATE (Type Code 6)
  755.  
  756.             ATOMIC_AGGREGATE is a well-known discretionary attribute of
  757.             length 0. It is used by a BGP speaker to inform other BGP
  758.             speakers that the local system selected a less specific
  759.             route without selecting a more specific route which is
  760.             included in it. Usage of this attribute is described in
  761.             5.1.6.
  762.  
  763.          g) AGGREGATOR (Type Code 7)
  764.  
  765.             AGGREGATOR is an optional transitive attribute of length 6.
  766.             The attribute contains the last AS number that formed the
  767.             aggregate route (encoded as 2 octets), followed by the IP
  768.             address of the BGP speaker that formed the aggregate route
  769.             (encoded as 4 octets).  Usage of this attribute is described
  770.             in 5.1.7
  771.  
  772.       Network Layer Reachability Information:
  773.  
  774.          This variable length field contains a list of IP address
  775.          prefixes.  The length in octets of the Network Layer
  776.          Reachability Information is not encoded explicitly, but can be
  777.          calculated as:
  778.  
  779.             UPDATE message Length - 23 - Total Path Attributes Length -
  780.             Unfeasible Routes Length
  781.  
  782.          where UPDATE message Length is the value encoded in the fixed-
  783.  
  784.  
  785.  
  786. Rekhter & Li                                                   [Page 14]
  787.  
  788. RFC 1654                         BGP-4                         July 1994
  789.  
  790.  
  791.          size BGP header, Total Path Attribute Length and Unfeasible
  792.          Routes Length  are the values encoded in the variable part of
  793.          the UPDATE message, and 23 is a combined length of the fixed-
  794.          size BGP header, the Total Path Attribute Length field and the
  795.          Unfeasible Routes Length field.
  796.  
  797.          Reachability information is encoded as one or more 2-tuples of
  798.          the form <length, prefix>, whose fields are described below:
  799.  
  800.                   +---------------------------+
  801.                   |   Length (1 octet)        |
  802.                   +---------------------------+
  803.                   |   Prefix (variable)       |
  804.                   +---------------------------+
  805.  
  806.          The use and the meaning of these fields are as follows:
  807.  
  808.          a) Length:
  809.  
  810.             The Length field indicates the length in bits of the IP
  811.             address prefix. A length of zero indicates a prefix that
  812.             matches all IP addresses (with prefix, itself, of zero
  813.             octets).
  814.  
  815.          b) Prefix:
  816.  
  817.             The Prefix field contains IP address prefixes followed by
  818.             enough trailing bits to make the end of the field fall on an
  819.             octet boundary. Note that the value of the trailing bits is
  820.             irrelevant.
  821.  
  822.    The minimum length of the UPDATE message is 23 octets -- 19 octets
  823.    for the fixed header + 2 octets for the Unfeasible Routes Length + 2
  824.    octets for the Total Path Attribute Length (the value of Unfeasible
  825.    Routes Length is 0  and the value of Total Path Attribute Length is
  826.    0).
  827.  
  828.    An UPDATE message can advertise at most one route, which may be
  829.    described by several path attributes. All path attributes contained
  830.    in a given UPDATE messages apply to the destinations carried in the
  831.    Network Layer Reachability Information field of the UPDATE message.
  832.  
  833.    An UPDATE message can list multiple routes to be withdrawn from
  834.    service.  Each such route is identified by its destination (expressed
  835.    as an IP prefix), which unambiguously identifies the route in the
  836.    context of the BGP speaker - BGP speaker connection to which it has
  837.    been previously been advertised.
  838.  
  839.  
  840.  
  841.  
  842. Rekhter & Li                                                   [Page 15]
  843.  
  844. RFC 1654                         BGP-4                         July 1994
  845.  
  846.  
  847.    An UPDATE message may advertise only routes to be withdrawn from
  848.    service, in which case it will not include path attributes or Network
  849.    Layer Reachability Information. Conversely, it may advertise only a
  850.    feasible route, in which case the WITHDRAWN ROUTES field need not be
  851.    present.
  852.  
  853. 4.4 KEEPALIVE Message Format
  854.  
  855.    BGP does not use any transport protocol-based keep-alive mechanism to
  856.    determine if peers are reachable.  Instead, KEEPALIVE messages are
  857.    exchanged between peers often enough as not to cause the Hold Timer
  858.    to expire.  A reasonable maximum time between KEEPALIVE messages
  859.    would be one third of the Hold Time interval.  KEEPALIVE messages
  860.    MUST NOT be sent more frequently than one per second.  An
  861.    implementation MAY adjust the rate at which it sends KEEPALIVE
  862.    messages as a function of the Hold Time interval.
  863.  
  864.    If the negotiated Hold Time interval is zero, then periodic KEEPALIVE
  865.    messages MUST NOT be sent.
  866.  
  867.    KEEPALIVE message consists of only message header and has a length of
  868.    19 octets.
  869.  
  870. 4.5 NOTIFICATION Message Format
  871.  
  872.    A NOTIFICATION message is sent when an error condition is detected.
  873.    The BGP connection is closed immediately after sending it.
  874.  
  875.    In addition to the fixed-size BGP header, the NOTIFICATION message
  876.    contains the following fields:
  877.  
  878.         0                   1                   2                   3
  879.         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  880.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  881.        | Error code    | Error subcode |           Data                |
  882.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
  883.        |                                                               |
  884.        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  885.  
  886.       Error Code:
  887.  
  888.          This 1-octet unsigned integer indicates the type of
  889.          NOTIFICATION.  The following Error Codes have been defined:
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898. Rekhter & Li                                                   [Page 16]
  899.  
  900. RFC 1654                         BGP-4                         July 1994
  901.  
  902.  
  903.             Error Code       Symbolic Name               Reference
  904.  
  905.               1         Message Header Error             Section 6.1
  906.  
  907.               2         OPEN Message Error               Section 6.2
  908.  
  909.               3         UPDATE Message Error             Section 6.3
  910.  
  911.               4         Hold Timer Expired               Section 6.5
  912.  
  913.               5         Finite State Machine Error       Section 6.6
  914.  
  915.               6         Cease                            Section 6.7
  916.  
  917.  
  918.       Error subcode:
  919.  
  920.          This 1-octet unsigned integer provides more specific
  921.          information about the nature of the reported error.  Each Error
  922.          Code may have one or more Error Subcodes associated with it.
  923.          If no appropriate Error Subcode is defined, then a zero
  924.          (Unspecific) value is used for the Error Subcode field.
  925.  
  926.          Message Header Error subcodes:
  927.  
  928.                                1  - Connection Not Synchronized.
  929.                                2  - Bad Message Length.
  930.                                3  - Bad Message Type.
  931.  
  932.          OPEN Message Error subcodes:
  933.  
  934.                                1  - Unsupported Version Number.
  935.                                2  - Bad Peer AS.
  936.                                3  - Bad BGP Identifier.
  937.                                4  - Unsupported Authentication Code.
  938.                                5  - Authentication Failure.
  939.                                6  - Unacceptable Hold Time.
  940.  
  941.          UPDATE Message Error subcodes:
  942.  
  943.                                1 - Malformed Attribute List.
  944.                                2 - Unrecognized Well-known Attribute.
  945.                                3 - Missing Well-known Attribute.
  946.                                4 - Attribute Flags Error.
  947.                                5 - Attribute Length Error.
  948.                                6 - Invalid ORIGIN Attribute
  949.                                7 - AS Routing Loop.
  950.                                8 - Invalid NEXT_HOP Attribute.
  951.  
  952.  
  953.  
  954. Rekhter & Li                                                   [Page 17]
  955.  
  956. RFC 1654                         BGP-4                         July 1994
  957.  
  958.  
  959.                                9 - Optional Attribute Error.
  960.                               10 - Invalid Network Field.
  961.                               11 - Malformed AS_PATH.
  962.  
  963.       Data:
  964.  
  965.          This variable-length field is used to diagnose the reason for
  966.          the NOTIFICATION.  The contents of the Data field depend upon
  967.          the Error Code and Error Subcode.  See Section 6 below for more
  968.          details.
  969.  
  970.          Note that the length of the Data field can be determined from
  971.          the message Length field by the formula:
  972.  
  973.                   Message Length = 21 + Data Length
  974.  
  975.    The minimum length of the NOTIFICATION message is 21 octets
  976.    (including message header).
  977.  
  978. 5.  Path Attributes
  979.  
  980.    This section discusses the path attributes of the UPDATE message.
  981.  
  982.    Path attributes fall into four separate categories:
  983.  
  984.                1. Well-known mandatory.
  985.                2. Well-known discretionary.
  986.                3. Optional transitive.
  987.                4. Optional non-transitive.
  988.  
  989.    Well-known attributes must be recognized by all BGP implementations.
  990.    Some of these attributes are mandatory and must be included in every
  991.    UPDATE message.  Others are discretionary and may or may not be sent
  992.    in a particular UPDATE message.
  993.  
  994.    All well-known attributes must be passed along (after proper
  995.    updating, if necessary) to other BGP peers.
  996.  
  997.    In addition to well-known attributes, each path may contain one or
  998.    more optional attributes.  It is not required or expected that all
  999.    BGP implementations support all optional attributes.  The handling of
  1000.    an unrecognized optional attribute is determined by the setting of
  1001.    the Transitive bit in the attribute flags octet.  Paths with
  1002.    unrecognized transitive optional attributes should be accepted. If a
  1003.    path with unrecognized transitive optional attribute is accepted and
  1004.    passed along to other BGP peers, then the unrecognized transitive
  1005.    optional attribute of that path must be passed along with the path to
  1006.    other BGP peers with the Partial bit in the Attribute Flags octet set
  1007.  
  1008.  
  1009.  
  1010. Rekhter & Li                                                   [Page 18]
  1011.  
  1012. RFC 1654                         BGP-4                         July 1994
  1013.  
  1014.  
  1015.    to 1. If a path with recognized transitive optional attribute is
  1016.    accepted and passed along to other BGP peers and the Partial bit in
  1017.    the Attribute Flags octet is set to 1 by some previous AS, it is not
  1018.    set back to 0 by the current AS. Unrecognized non-transitive optional
  1019.    attributes must be quietly ignored and not passed along to other BGP
  1020.    peers.
  1021.  
  1022.    New transitive optional attributes may be attached to the path by the
  1023.    originator or by any other AS in the path.  If they are not attached
  1024.    by the originator, the Partial bit in the Attribute Flags octet is
  1025.    set to 1.  The rules for attaching new non-transitive optional
  1026.    attributes will depend on the nature of the specific attribute.  The
  1027.    documentation of each new non-transitive optional attribute will be
  1028.    expected to include such rules.  (The description of the
  1029.    MULTI_EXIT_DISC attribute gives an example.)  All optional attributes
  1030.    (both transitive and non-transitive) may be updated (if appropriate)
  1031.    by ASs in the path.
  1032.  
  1033.    The sender of an UPDATE message should order path attributes within
  1034.    the UPDATE message in ascending order of attribute type.  The
  1035.    receiver of an UPDATE message must be prepared to handle path
  1036.    attributes within the UPDATE message that are out of order.
  1037.  
  1038.    The same attribute cannot appear more than once within the Path
  1039.    Attributes field of a particular UPDATE message.
  1040.  
  1041. 5.1 Path Attribute Usage
  1042.  
  1043.    The usage of each BGP path attributes is described in the following
  1044.    clauses.
  1045.  
  1046. 5.1.1 ORIGIN
  1047.  
  1048.    ORIGIN is a well-known mandatory attribute.  The ORIGIN attribute
  1049.    shall be generated by the autonomous system that originates the
  1050.    associated routing information. It shall be included in the UPDATE
  1051.    messages of all BGP speakers that choose to propagate this
  1052.    information to other BGP speakers.
  1053.  
  1054. 5.1.2  AS_PATH
  1055.  
  1056.    AS_PATH is a well-known mandatory attribute. This attribute
  1057.    identifies the autonomous systems through which routing information
  1058.    carried in this UPDATE message has passed. The components of this
  1059.    list can be AS_SETs or AS_SEQUENCEs.
  1060.  
  1061.    When a BGP speaker propagates a route which it has learned from
  1062.    another BGP speaker's UPDATE message, it shall modify the route's
  1063.  
  1064.  
  1065.  
  1066. Rekhter & Li                                                   [Page 19]
  1067.  
  1068. RFC 1654                         BGP-4                         July 1994
  1069.  
  1070.  
  1071.    AS_PATH attribute based on the location of the BGP speaker to which
  1072.    the route will be sent:
  1073.  
  1074.       a) When a given BGP speaker advertises the route to another BGP
  1075.       speaker located in its own autonomous system, the advertising
  1076.       speaker shall not modify the AS_PATH attribute associated with the
  1077.       route.
  1078.  
  1079.       b) When a given BGP speaker advertises the route to a BGP speaker
  1080.       located in a neighboring autonomous system, then the advertising
  1081.       speaker shall update the AS_PATH attribute as follows:
  1082.  
  1083.          1) if the first path segment of the AS_PATH is of type
  1084.          AS_SEQUENCE, the local system shall prepend its own AS number
  1085.          as the last element of the sequence (put it in the leftmost
  1086.          position).
  1087.  
  1088.          2) if the first path segment of the AS_PATH is of type AS_SET,
  1089.          the local system shall prepend a new path segment of type
  1090.          AS_SEQUENCE to the AS_PATH, including its own AS number in that
  1091.          segment.
  1092.  
  1093.       When a BGP speaker originates a route then:
  1094.  
  1095.          a) the originating speaker shall include its own AS number in
  1096.          the AS_PATH attribute of all UPDATE messages sent to BGP
  1097.          speakers located in neighboring autonomous systems. (In this
  1098.          case, the AS number of the originating speaker's autonomous
  1099.          system will be the only entry in the AS_PATH attribute).
  1100.  
  1101.          b) the originating speaker shall include an empty AS_PATH
  1102.          attribute in all UPDATE messages sent to BGP speakers located
  1103.          in its own autonomous system. (An empty AS_PATH attribute is
  1104.          one whose length field contains the value zero).
  1105.  
  1106. 5.1.3 NEXT_HOP
  1107.  
  1108.    The NEXT_HOP path attribute defines the IP address of the border
  1109.    router that should be used as the next hop to the networks listed in
  1110.    the UPDATE message.  If a border router belongs to the same AS as its
  1111.    peer, then the peer is an internal border router. Otherwise, it is an
  1112.    external border router.  A BGP speaker can advertise any internal
  1113.    border router as the next hop provided that the interface associated
  1114.    with the IP address of this border router (as specified in the
  1115.    NEXT_HOP path attribute) shares a common subnet with both the local
  1116.    and remote BGP speakers. A BGP speaker can advertise any external
  1117.    border router as the next hop, provided that the IP address of this
  1118.    border router was learned from one of the BGP speaker's peers, and
  1119.  
  1120.  
  1121.  
  1122. Rekhter & Li                                                   [Page 20]
  1123.  
  1124. RFC 1654                         BGP-4                         July 1994
  1125.  
  1126.  
  1127.    the interface associated with the IP address of this border router
  1128.    (as specified in the NEXT_HOP path attribute) shares a common subnet
  1129.    with the local and remote BGP speakers.  A BGP speaker needs to be
  1130.    able to support disabling advertisement of external border routers.
  1131.  
  1132.    A BGP speaker must never advertise an address of a peer to that peer
  1133.    as a NEXT_HOP, for a route that the speaker is originating.  A BGP
  1134.    speaker must never install a route with itself as the next hop.
  1135.  
  1136.    When a BGP speaker advertises the route to a BGP speaker located in
  1137.    its own autonomous system, the advertising speaker shall not modify
  1138.    the NEXT_HOP attribute associated with the route.  When a BGP speaker
  1139.    receives the route via an internal link, it may forward packets to
  1140.    the NEXT_HOP address if the address contained in the attribute is on
  1141.    a common subnet with the local and remote BGP speakers.
  1142.  
  1143. 5.1.4   MULTI_EXIT_DISC
  1144.  
  1145.    The MULTI_EXIT_DISC attribute may be used on external (inter-AS)
  1146.    links to discriminate among multiple exit or entry points to the same
  1147.    neighboring AS.  The value of the MULTI_EXIT_DISC attribute is a four
  1148.    octet unsigned number which is called a metric.  All other factors
  1149.    being equal, the exit or entry point with lower metric should be
  1150.    preferred.  If received over external links, the MULTI_EXIT_DISC
  1151.    attribute may be propagated over internal links to other BGP speakers
  1152.    within the same AS.  The MULTI_EXIT_DISC attribute is never
  1153.    propagated to other BGP speakers in neighboring AS's.
  1154.  
  1155. 5.1.5   LOCAL_PREF
  1156.  
  1157.    LOCAL_PREF is a well-known discretionary attribute that shall be
  1158.    included in all UPDATE messages that a given BGP speaker sends to the
  1159.    other BGP speakers located in its own autonomous system. A BGP
  1160.    speaker shall calculate the degree of preference for each external
  1161.    route and include the degree of preference when advertising a route
  1162.    to its internal peers. The higher degree of preference should be
  1163.    preferred. A BGP speaker shall use the degree of preference learned
  1164.    via LOCAL_PREF in its decision process (see section 9.1.1).
  1165.  
  1166.    A BGP speaker shall not include this attribute in UPDATE messages
  1167.    that it sends to BGP speakers located in a neighboring autonomous
  1168.    system. If it is contained in an UPDATE message that is received from
  1169.    a BGP speaker which is not located in the same autonomous system as
  1170.    the receiving speaker, then this attribute shall be ignored by the
  1171.    receiving speaker.
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177.  
  1178. Rekhter & Li                                                   [Page 21]
  1179.  
  1180. RFC 1654                         BGP-4                         July 1994
  1181.  
  1182.  
  1183. 5.1.6   ATOMIC_AGGREGATE
  1184.  
  1185.    ATOMIC_AGGREGATE is a well-known discretionary attribute.  If a BGP
  1186.    speaker, when presented with a set of overlapping routes from one of
  1187.    its peers (see 9.1.4), selects the less specific route without
  1188.    selecting the more specific one, then the local system shall attach
  1189.    the ATOMIC_AGGREGATE attribute to the route when propagating it to
  1190.    other BGP speakers (if that attribute is not already present in the
  1191.    received less specific route). A BGP speaker that receives a route
  1192.    with the ATOMIC_AGGREGATE attribute shall not remove the attribute
  1193.    from the route when propagating it to other speakers. A BGP speaker
  1194.    that receives a route with the ATOMIC_AGGREGATE attribute shall not
  1195.    make any NLRI of that route more specific (as defined in 9.1.4) when
  1196.    advertising this route to other BGP speakers.  A BGP speaker that
  1197.    receives a route with the ATOMIC_AGGREGATE attribute needs to be
  1198.    cognizant of the fact that the actual path to destinations, as
  1199.    specified in the NLRI of the route, while having the loop-free
  1200.    property, may traverse ASs that are not listed in the AS_PATH
  1201.    attribute.
  1202.  
  1203. 5.1.7   AGGREGATOR
  1204.  
  1205.    AGGREGATOR is an optional transitive attribute which may be included
  1206.    in updates which are formed by aggregation (see Section 9.2.4.2).  A
  1207.    BGP speaker which performs route aggregation may add the AGGREGATOR
  1208.    attribute which shall contain its own AS number and IP address.
  1209.  
  1210. 6.  BGP Error Handling.
  1211.  
  1212.    This section describes actions to be taken when errors are detected
  1213.    while processing BGP messages.
  1214.  
  1215.    When any of the conditions described here are detected, a
  1216.    NOTIFICATION message with the indicated Error Code, Error Subcode,
  1217.    and Data fields is sent, and the BGP connection is closed.  If no
  1218.    Error Subcode is specified, then a zero must be used.
  1219.  
  1220.    The phrase "the BGP connection is closed" means that the transport
  1221.    protocol connection has been closed and that all resources for that
  1222.    BGP connection have been deallocated.  Routing table entries
  1223.    associated with the remote peer are marked as invalid.  The fact that
  1224.    the routes have become invalid is passed to other BGP peers before
  1225.    the routes are deleted from the system.
  1226.  
  1227.    Unless specified explicitly, the Data field of the NOTIFICATION
  1228.    message that is sent to indicate an error is empty.
  1229.  
  1230.  
  1231.  
  1232.  
  1233.  
  1234. Rekhter & Li                                                   [Page 22]
  1235.  
  1236. RFC 1654                         BGP-4                         July 1994
  1237.  
  1238.  
  1239. 6.1 Message Header error handling.
  1240.  
  1241.    All errors detected while processing the Message Header are indicated
  1242.    by sending the NOTIFICATION message with Error Code Message Header
  1243.    Error.  The Error Subcode elaborates on the specific nature of the
  1244.    error.
  1245.  
  1246.    The expected value of the Marker field of the message header is all
  1247.    ones if the message type is OPEN.  The expected value of the Marker
  1248.    field for all other types of BGP messages determined based on the
  1249.    Authentication Code in the BGP OPEN message and the actual
  1250.    authentication mechanism (if the Authentication Code in the BGP OPEN
  1251.    message is non-zero). If the Marker field of the message header is
  1252.    not the expected one, then a synchronization error has occurred and
  1253.    the Error Subcode is set to Connection Not Synchronized.
  1254.  
  1255.    If the Length field of the message header is less than 19 or greater
  1256.    than 4096, or if the Length field of an OPEN message is less  than
  1257.    the minimum length of the OPEN message, or if the Length field of an
  1258.    UPDATE message is less than the minimum length of the UPDATE message,
  1259.    or if the Length field of a KEEPALIVE message is not equal to 19, or
  1260.    if the Length field of a NOTIFICATION message is less than the
  1261.    minimum length of the NOTIFICATION message, then the Error Subcode is
  1262.    set to Bad Message Length.  The Data field contains the erroneous
  1263.    Length field.
  1264.  
  1265.    If the Type field of the message header is not recognized, then the
  1266.    Error Subcode is set to Bad Message Type.  The Data field contains
  1267.    the erroneous Type field.
  1268.  
  1269. 6.2 OPEN message error handling.
  1270.  
  1271.    All errors detected while processing the OPEN message are indicated
  1272.    by sending the NOTIFICATION message with Error Code OPEN Message
  1273.    Error.  The Error Subcode elaborates on the specific nature of the
  1274.    error.
  1275.  
  1276.    If the version number contained in the Version field of the received
  1277.    OPEN message is not supported, then the Error Subcode is set to
  1278.    Unsupported Version Number.  The Data field is a 2-octet unsigned
  1279.    integer, which indicates the largest locally supported version number
  1280.    less than the version the remote BGP peer bid (as indicated in the
  1281.    received OPEN message).
  1282.  
  1283.    If the Autonomous System field of the OPEN message is unacceptable,
  1284.    then the Error Subcode is set to Bad Peer AS.  The determination of
  1285.    acceptable Autonomous System numbers is outside the scope of this
  1286.    protocol.
  1287.  
  1288.  
  1289.  
  1290. Rekhter & Li                                                   [Page 23]
  1291.  
  1292. RFC 1654                         BGP-4                         July 1994
  1293.  
  1294.  
  1295.    If the Hold Time field of the OPEN message is unacceptable, then the
  1296.    Error Subcode MUST be set to Unacceptable Hold Time.  An
  1297.    implementation MUST reject Hold Time values of one or two seconds.
  1298.    An implementation MAY reject any proposed Hold Time.  An
  1299.    implementation which accepts a Hold Time MUST use the negotiated
  1300.    value for the Hold Time.
  1301.  
  1302.    If the BGP Identifier field of the OPEN message is syntactically
  1303.    incorrect, then the Error Subcode is set to Bad BGP Identifier.
  1304.    Syntactic correctness means that the BGP Identifier field represents
  1305.    a valid IP host address.
  1306.  
  1307.    If the Authentication Code of the OPEN message is not recognized,
  1308.    then the Error Subcode is set to Unsupported Authentication Code.  If
  1309.    the Authentication Code is zero, then the Authentication Data must be
  1310.    of zero length.  Otherwise, the Error Subcode is set to
  1311.    Authentication Failure.
  1312.  
  1313.    If the Authentication Code is non-zero, then the corresponding
  1314.    authentication procedure is invoked.  If the authentication procedure
  1315.    (based on Authentication Code and Authentication Data) fails, then
  1316.    the Error Subcode is set to Authentication Failure.
  1317.  
  1318. 6.3 UPDATE message error handling.
  1319.  
  1320.    All errors detected while processing the UPDATE message are indicated
  1321.    by sending the NOTIFICATION message with Error Code UPDATE Message
  1322.    Error.  The error subcode elaborates on the specific nature of the
  1323.    error.
  1324.  
  1325.    Error checking of an UPDATE message begins by examining the path
  1326.    attributes.  If the Unfeasible Routes Length or Total Attribute
  1327.    Length is too large (i.e., if Unfeasible Routes Length + Total
  1328.    Attribute Length + 23 exceeds the message Length), then the Error
  1329.    Subcode is set to Malformed Attribute List.
  1330.  
  1331.    If any recognized attribute has Attribute Flags that conflict with
  1332.    the Attribute Type Code, then the Error Subcode is set to Attribute
  1333.    Flags Error.  The Data field contains the erroneous attribute (type,
  1334.    length and value).
  1335.  
  1336.    If any recognized attribute has Attribute Length that conflicts with
  1337.    the expected length (based on the attribute type code), then the
  1338.    Error Subcode is set to Attribute Length Error.  The Data field
  1339.    contains the erroneous attribute (type, length and value).
  1340.  
  1341.    If any of the mandatory well-known attributes are not present, then
  1342.    the Error Subcode is set to Missing Well-known Attribute.  The Data
  1343.  
  1344.  
  1345.  
  1346. Rekhter & Li                                                   [Page 24]
  1347.  
  1348. RFC 1654                         BGP-4                         July 1994
  1349.  
  1350.  
  1351.    field contains the Attribute Type Code of the missing well-known
  1352.    attribute.
  1353.  
  1354.    If any of the mandatory well-known attributes are not recognized,
  1355.    then the Error Subcode is set to Unrecognized Well-known Attribute.
  1356.    The Data field contains the unrecognized attribute (type, length and
  1357.    value).
  1358.  
  1359.    If the ORIGIN attribute has an undefined value, then the Error
  1360.    Subcode is set to Invalid Origin Attribute.  The Data field contains
  1361.    the unrecognized attribute (type, length and value).
  1362.  
  1363.    If the NEXT_HOP attribute field is syntactically incorrect, then the
  1364.    Error Subcode is set to Invalid NEXT_HOP Attribute.  The Data field
  1365.    contains the incorrect attribute (type, length and value).  Syntactic
  1366.    correctness means that the NEXT_HOP attribute represents a valid IP
  1367.    host address.  Semantic correctness applies only to the external BGP
  1368.    links. It means that the interface associated with the IP address, as
  1369.    specified in the NEXT_HOP attribute, shares a common subnet with the
  1370.    receiving BGP speaker and is not the IP address of the receiving BGP
  1371.    speaker.  If the NEXT_HOP attribute is semantically incorrect, the
  1372.    error should be logged, and the the route should be ignored.  In this
  1373.    case, no NOTIFICATION message should be sent.
  1374.  
  1375.    The AS_PATH attribute is checked for syntactic correctness.  If the
  1376.    path is syntactically incorrect, then the Error Subcode is set to
  1377.    Malformed AS_PATH.
  1378.  
  1379.    If an optional attribute is recognized, then the value of this
  1380.    attribute is checked.  If an error is detected, the attribute is
  1381.    discarded, and the Error Subcode is set to Optional Attribute Error.
  1382.  
  1383.    The Data field contains the attribute (type, length and value).
  1384.  
  1385.    If any attribute appears more than once in the UPDATE message, then
  1386.    the Error Subcode is set to Malformed Attribute List.
  1387.  
  1388.    The NLRI field in the UPDATE message is checked for syntactic
  1389.    validity.  If the field is syntactically incorrect, then the Error
  1390.    Subcode is set to Invalid Network Field.
  1391.  
  1392. 6.4 NOTIFICATION message error handling.
  1393.  
  1394.    If a peer sends a NOTIFICATION message, and there is an error in that
  1395.    message, there is unfortunately no means of reporting this error via
  1396.    a subsequent NOTIFICATION message.  Any such error, such as an
  1397.    unrecognized Error Code or Error Subcode, should be noticed, logged
  1398.    locally, and brought to the attention of the administration of the
  1399.  
  1400.  
  1401.  
  1402. Rekhter & Li                                                   [Page 25]
  1403.  
  1404. RFC 1654                         BGP-4                         July 1994
  1405.  
  1406.  
  1407.    peer.  The means to do this, however, lies outside the scope of this
  1408.    document.
  1409.  
  1410. 6.5 Hold Timer Expired error handling.
  1411.  
  1412.    If a system does not receive successive KEEPALIVE and/or UPDATE
  1413.    and/or NOTIFICATION messages within the period specified in the Hold
  1414.    Time field of the OPEN message, then the NOTIFICATION message with
  1415.    Hold Timer Expired Error Code must be sent and the BGP connection
  1416.    closed.
  1417.  
  1418. 6.6 Finite State Machine error handling.
  1419.  
  1420.    Any error detected by the BGP Finite State Machine (e.g., receipt of
  1421.    an unexpected event) is indicated by sending the NOTIFICATION message
  1422.    with Error Code Finite State Machine Error.
  1423.  
  1424. 6.7 Cease.
  1425.  
  1426.    In absence of any fatal errors (that are indicated in this section),
  1427.    a BGP peer may choose at any given time to close its BGP connection
  1428.    by sending the NOTIFICATION message with Error Code Cease.  However,
  1429.    the Cease NOTIFICATION message must not be used when a fatal error
  1430.    indicated by this section does exist.
  1431.  
  1432. 6.8 Connection collision detection.
  1433.  
  1434.    If a pair of BGP speakers try simultaneously to establish a TCP
  1435.    connection to each other, then two parallel connections between this
  1436.    pair of speakers might well be formed.  We refer to this situation as
  1437.    connection collision.  Clearly, one of these connections must be
  1438.    closed.
  1439.  
  1440.    Based on the value of the BGP Identifier a convention is established
  1441.    for detecting which BGP connection is to be preserved when a
  1442.    collision does occur. The convention is to compare the BGP
  1443.    Identifiers of the peers involved in the collision and to retain only
  1444.    the connection initiated by the BGP speaker with the higher-valued
  1445.    BGP Identifier.
  1446.  
  1447.    Upon receipt of an OPEN message, the local system must examine all of
  1448.    its connections that are in the OpenConfirm state.  A BGP speaker may
  1449.    also examine connections in an OpenSent state if it knows the BGP
  1450.    Identifier of the peer by means outside of the protocol.  If among
  1451.    these connections there is a connection to a remote BGP speaker whose
  1452.    BGP Identifier equals the one in the OPEN message, then the local
  1453.    system performs the following collision resolution procedure:
  1454.  
  1455.  
  1456.  
  1457.  
  1458. Rekhter & Li                                                   [Page 26]
  1459.  
  1460. RFC 1654                         BGP-4                         July 1994
  1461.  
  1462.  
  1463.       1. The BGP Identifier of the local system is compared to the BGP
  1464.       Identifier of the remote system (as specified in the OPEN
  1465.       message).
  1466.  
  1467.       2. If the value of the local BGP Identifier is less than the
  1468.       remote one, the local system closes BGP connection that already
  1469.       exists (the one that is already in the OpenConfirm state), and
  1470.       accepts BGP connection initiated by the remote system.
  1471.  
  1472.       3. Otherwise, the local system closes newly created BGP connection
  1473.       (the one associated with the newly received OPEN message), and
  1474.       continues to use the existing one (the one that is already in the
  1475.       OpenConfirm state).
  1476.  
  1477.       Comparing BGP Identifiers is done by treating them as (4-octet
  1478.       long) unsigned integers.
  1479.  
  1480.       A connection collision with an existing BGP connection that is in
  1481.       Established states causes unconditional closing of the newly
  1482.       created connection. Note that a connection collision cannot be
  1483.       detected with connections that are in Idle, or Connect, or Active
  1484.       states.
  1485.  
  1486.       Closing the BGP connection (that results from the collision
  1487.       resolution procedure) is accomplished by sending the NOTIFICATION
  1488.       message with the Error Code Cease.
  1489.  
  1490. 7.  BGP Version Negotiation.
  1491.  
  1492.    BGP speakers may negotiate the version of the protocol by making
  1493.    multiple attempts to open a BGP connection, starting with the highest
  1494.    version number each supports.  If an open attempt fails with an Error
  1495.    Code OPEN Message Error, and an Error Subcode Unsupported Version
  1496.    Number, then the BGP speaker has available the version number it
  1497.    tried, the version number its peer tried, the version number passed
  1498.    by its peer in the NOTIFICATION message, and the version numbers that
  1499.    it supports.  If the two peers do support one or more common
  1500.    versions, then this will allow them to rapidly determine the highest
  1501.    common version. In order to support BGP version negotiation, future
  1502.    versions of BGP must retain the format of the OPEN and NOTIFICATION
  1503.    messages.
  1504.  
  1505. 8.  BGP Finite State machine.
  1506.  
  1507.    This section specifies BGP operation in terms of a Finite State
  1508.    Machine (FSM).  Following is a brief summary and overview of BGP
  1509.    operations by state as determined by this FSM.  A condensed version
  1510.    of the BGP FSM is found in Appendix 1.
  1511.  
  1512.  
  1513.  
  1514. Rekhter & Li                                                   [Page 27]
  1515.  
  1516. RFC 1654                         BGP-4                         July 1994
  1517.  
  1518.  
  1519.       Initially BGP is in the Idle state.
  1520.  
  1521.       Idle state:
  1522.  
  1523.          In this state BGP refuses all incoming BGP connections.  No
  1524.          resources are allocated to the peer.  In response to the Start
  1525.          event (initiated by either system or operator) the local system
  1526.          initializes all BGP resources, starts the ConnectRetry timer,
  1527.          initiates a transport connection to other BGP peer, while
  1528.          listening for connection that may be initiated by the remote
  1529.          BGP peer, and changes its state to Connect.  The exact value of
  1530.          the ConnectRetry timer is a local matter, but should be
  1531.          sufficiently large to allow TCP initialization.
  1532.  
  1533.          If a BGP speaker detects an error, it shuts down the connection
  1534.          and changes its state to Idle. Getting out of the Idle state
  1535.          requires generation of the Start event.  If such an event is
  1536.          generated automatically, then persistent BGP errors may result
  1537.          in persistent flapping of the speaker.  To avoid such a
  1538.          condition it is recommended that Start events should not be
  1539.          generated immediately for a peer that was previously
  1540.          transitioned to Idle due to an error. For a peer that was
  1541.          previously transitioned to Idle due to an error, the time
  1542.          between consecutive generation of Start events, if such events
  1543.          are generated automatically, shall exponentially increase. The
  1544.          value of the initial timer shall be 60 seconds. The time shall
  1545.          be doubled for each consecutive retry.
  1546.  
  1547.          Any other event received in the Idle state is ignored.
  1548.  
  1549.       Connect state:
  1550.  
  1551.          In this state BGP is waiting for the transport protocol
  1552.          connection to be completed.
  1553.  
  1554.          If the transport protocol connection succeeds, the local system
  1555.          clears the ConnectRetry timer, completes initialization, sends
  1556.          an OPEN message to its peer, and changes its state to OpenSent.
  1557.  
  1558.          If the transport protocol connect fails (e.g., retransmission
  1559.          timeout), the local system restarts the ConnectRetry timer,
  1560.          continues to listen for a connection that may be initiated by
  1561.          the remote BGP peer, and changes its state to Active state.
  1562.  
  1563.          In response to the ConnectRetry timer expired event, the local
  1564.          system restarts the ConnectRetry timer, initiates a transport
  1565.          connection to other BGP peer, continues to listen for a
  1566.          connection that may be initiated by the remote BGP peer, and
  1567.  
  1568.  
  1569.  
  1570. Rekhter & Li                                                   [Page 28]
  1571.  
  1572. RFC 1654                         BGP-4                         July 1994
  1573.  
  1574.  
  1575.          stays in the Connect state.
  1576.  
  1577.          Start event is ignored in the Active state.
  1578.  
  1579.          In response to any other event (initiated by either system or
  1580.          operator), the local system releases all BGP resources
  1581.          associated with this connection and changes its state to Idle.
  1582.  
  1583.       Active state:
  1584.  
  1585.          In this state BGP is trying to acquire a peer by initiating a
  1586.          transport protocol connection.
  1587.  
  1588.          If the transport protocol connection succeeds, the local system
  1589.          clears the ConnectRetry timer, completes initialization, sends
  1590.          an OPEN message to its peer, sets its Hold Timer to a large
  1591.          value, and changes its state to OpenSent.  A Hold Timer value
  1592.          of 4 minutes is suggested.
  1593.  
  1594.          In response to the ConnectRetry timer expired event, the local
  1595.          system restarts the ConnectRetry timer, initiates a transport
  1596.          connection to other BGP peer, continues to listen for a
  1597.          connection that may be initiated by the remote BGP peer, and
  1598.          changes its state to Connect.
  1599.  
  1600.          If the local system detects that a remote peer is trying to
  1601.          establish BGP connection to it, and the IP address of the
  1602.          remote peer is not an expected one, the local system restarts
  1603.          the ConnectRetry timer, rejects the attempted connection,
  1604.          continues to listen for a connection that may be initiated by
  1605.          the remote BGP peer, and stays in the Active state.
  1606.  
  1607.          Start event is ignored in the Active state.
  1608.  
  1609.          In response to any other event (initiated by either system or
  1610.          operator), the local system releases all BGP resources
  1611.          associated with this connection and changes its state to Idle.
  1612.  
  1613.       OpenSent state:
  1614.  
  1615.          In this state BGP waits for an OPEN message from its peer.
  1616.          When an OPEN message is received, all fields are checked for
  1617.          correctness.  If the BGP message header checking or OPEN
  1618.          message checking detects an error (see Section 6.2), or a
  1619.          connection collision (see Section 6.8) the local system sends a
  1620.          NOTIFICATION message and changes its state to Idle.
  1621.  
  1622.  
  1623.  
  1624.  
  1625.  
  1626. Rekhter & Li                                                   [Page 29]
  1627.  
  1628. RFC 1654                         BGP-4                         July 1994
  1629.  
  1630.  
  1631.          If there are no errors in the OPEN message, BGP sends a
  1632.          KEEPALIVE message and sets a KeepAlive timer.  The Hold Timer,
  1633.          which was originally set to a large value (see above), is
  1634.          replaced with the negotiated Hold Time value (see section 4.2).
  1635.          If the negotiated Hold Time value is zero, then the Hold Time
  1636.          timer and KeepAlive timers are not started.  If the value of
  1637.          the Autonomous System field is the same as the local Autonomous
  1638.          System number, then the connection is an "internal" connection;
  1639.          otherwise, it is "external".  (This will effect UPDATE
  1640.          processing as described below.) Finally, the state is changed
  1641.          to OpenConfirm.
  1642.  
  1643.          If a disconnect notification is received from the underlying
  1644.          transport protocol, the local system closes the BGP connection,
  1645.          restarts the ConnectRetry timer, while continue listening for
  1646.          connection that may be initiated by the remote BGP peer, and
  1647.          goes into the Active state.
  1648.  
  1649.          If the Hold Timer expires, the local system sends NOTIFICATION
  1650.          message with error code Hold Timer Expired and changes its
  1651.          state to Idle.
  1652.  
  1653.          In response to the Stop event (initiated by either system or
  1654.          operator) the local system sends NOTIFICATION message with
  1655.          Error Code Cease and changes its state to Idle.
  1656.  
  1657.          Start event is ignored in the OpenSent state.
  1658.  
  1659.          In response to any other event the local system sends
  1660.          NOTIFICATION message with Error Code Finite State Machine Error
  1661.          and changes its state to Idle.
  1662.  
  1663.          Whenever BGP changes its state from OpenSent to Idle, it closes
  1664.          the BGP (and transport-level) connection and releases all
  1665.          resources associated with that connection.
  1666.  
  1667.       OpenConfirm state:
  1668.  
  1669.          In this state BGP waits for a KEEPALIVE or NOTIFICATION
  1670.          message.
  1671.  
  1672.          If the local system receives a KEEPALIVE message, it changes
  1673.          its state to Established.
  1674.  
  1675.          If the Hold Timer expires before a KEEPALIVE message is
  1676.          received, the local system sends NOTIFICATION message with
  1677.          error code Hold Timer Expired and changes its state to Idle.
  1678.  
  1679.  
  1680.  
  1681.  
  1682. Rekhter & Li                                                   [Page 30]
  1683.  
  1684. RFC 1654                         BGP-4                         July 1994
  1685.  
  1686.  
  1687.          If the local system receives a NOTIFICATION message, it changes
  1688.          its state to Idle.
  1689.  
  1690.          If the KeepAlive timer expires, the local system sends a
  1691.          KEEPALIVE message and restarts its KeepAlive timer.
  1692.  
  1693.          If a disconnect notification is received from the underlying
  1694.          transport protocol, the local system changes its state to Idle.
  1695.  
  1696.          In response to the Stop event (initiated by either system or
  1697.          operator) the local system sends NOTIFICATION message with
  1698.          Error Code Cease and changes its state to Idle.
  1699.  
  1700.          Start event is ignored in the OpenConfirm state.
  1701.  
  1702.          In response to any other event the local system sends
  1703.          NOTIFICATION message with Error Code Finite State Machine Error
  1704.          and changes its state to Idle.
  1705.  
  1706.          Whenever BGP changes its state from OpenConfirm to Idle, it
  1707.          closes the BGP (and transport-level) connection and releases
  1708.          all resources associated with that connection.
  1709.  
  1710.       Established state:
  1711.  
  1712.          In the Established state BGP can exchange UPDATE, NOTIFICATION,
  1713.          and KEEPALIVE messages with its peer.
  1714.  
  1715.          If the local system receives an UPDATE or KEEPALIVE message, it
  1716.          restarts its Hold Timer, if the negotiated Hold Time value is
  1717.          non-zero.
  1718.  
  1719.          If the local system receives a NOTIFICATION message, it changes
  1720.          its state to Idle.
  1721.  
  1722.          If the local system receives an UPDATE message and the UPDATE
  1723.          message error handling procedure (see Section 6.3) detects an
  1724.          error, the local system sends a NOTIFICATION message and
  1725.          changes its state to Idle.
  1726.  
  1727.          If a disconnect notification is received from the underlying
  1728.          transport protocol, the local system changes its state to Idle.
  1729.  
  1730.          If the Hold Timer expires, the local system sends a
  1731.          NOTIFICATION message with Error Code Hold Timer Expired and
  1732.          changes its state to Idle.
  1733.  
  1734.  
  1735.  
  1736.  
  1737.  
  1738. Rekhter & Li                                                   [Page 31]
  1739.  
  1740. RFC 1654                         BGP-4                         July 1994
  1741.  
  1742.  
  1743.          If the KeepAlive timer expires, the local system sends a
  1744.          KEEPALIVE message and restarts its KeepAlive timer.
  1745.  
  1746.          Each time the local system sends a KEEPALIVE or UPDATE message,
  1747.          it restarts its KeepAlive timer, unless the negotiated Hold
  1748.          Time value is zero.
  1749.  
  1750.          In response to the Stop event (initiated by either system or
  1751.          operator), the local system sends a NOTIFICATION message with
  1752.          Error Code Cease and changes its state to Idle.
  1753.  
  1754.          Start event is ignored in the Established state.
  1755.  
  1756.          In response to any other event, the local system sends
  1757.          NOTIFICATION message with Error Code Finite State Machine Error
  1758.          and changes its state to Idle.
  1759.  
  1760.          Whenever BGP changes its state from Established to Idle, it
  1761.          closes the BGP (and transport-level) connection, releases all
  1762.          resources associated with that connection, and deletes all
  1763.          routes derived from that connection.
  1764.  
  1765. 9.  UPDATE Message Handling
  1766.  
  1767.    An UPDATE message may be received only in the Established state.
  1768.    When an UPDATE message is received, each field is checked for
  1769.    validity as specified in Section 6.3.
  1770.  
  1771.    If an optional non-transitive attribute is unrecognized, it is
  1772.    quietly ignored.  If an optional transitive attribute is
  1773.    unrecognized, the Partial bit (the third high-order bit) in the
  1774.    attribute flags octet is set to 1, and the attribute is retained for
  1775.    propagation to other BGP speakers.
  1776.  
  1777.    If an optional attribute is recognized, and has a valid value, then,
  1778.    depending on the type of the optional attribute, it is processed
  1779.    locally, retained, and updated, if necessary, for possible
  1780.    propagation to other BGP speakers.
  1781.  
  1782.    If the UPDATE message contains a non-empty WITHDRAWN ROUTES field,
  1783.    the previously advertised routes whose destinations (expressed as IP
  1784.    prefixes) contained in this field shall be removed from the Adj-RIB-
  1785.    In.  This BGP speaker shall run its Decision Process since the
  1786.    previously advertised route is not longer available for use.
  1787.  
  1788.    If the UPDATE message contains a feasible route, it shall be placed
  1789.    in the appropriate Adj-RIB-In, and the following additional actions
  1790.    shall be taken:
  1791.  
  1792.  
  1793.  
  1794. Rekhter & Li                                                   [Page 32]
  1795.  
  1796. RFC 1654                         BGP-4                         July 1994
  1797.  
  1798.  
  1799.    i) If its Network Layer Reachability Information (NLRI) is identical
  1800.    to the one of a route currently stored in the Adj-RIB-In, then the
  1801.    new route shall replace the older route in the Adj-RIB-In, thus
  1802.    implicitly withdrawing the older route from service. The BGP speaker
  1803.    shall run its Decision Process since the older route is no longer
  1804.    available for use.
  1805.  
  1806.    ii) If the new route is an overlapping route that is included (see
  1807.    9.1.4) in an earlier route contained in the Adj-RIB-In, the BGP
  1808.    speaker shall run its Decision Process since the more specific route
  1809.    has implicitly made a portion of the less specific route unavailable
  1810.    for use.
  1811.  
  1812.    iii) If the new route has identical path attributes to an earlier
  1813.    route contained in the Adj-RIB-In, and is more specific (see 9.1.4)
  1814.    than the earlier route, no further actions are necessary.
  1815.  
  1816.    iv) If the new route has NLRI that is not present in any of the
  1817.    routes currently stored in the Adj-RIB-In, then the new route shall
  1818.    be placed in the Adj-RIB-In. The BGP speaker shall run its Decision
  1819.    Process.
  1820.  
  1821.    v) If the new route is an overlapping route that is less specific
  1822.    (see 9.1.4) than an earlier route contained in the Adj-RIB-In, the
  1823.    BGP speaker shall run its Decision Process on the set of destinations
  1824.    described only by the less specific route.
  1825.  
  1826. 9.1 Decision Process
  1827.  
  1828.    The Decision Process selects routes for subsequent advertisement by
  1829.    applying the policies in the local Policy Information Base (PIB) to
  1830.    the routes stored in its Adj-RIB-In. The output of the Decision
  1831.    Process is the set of routes that will be advertised to all peers;
  1832.    the selected routes will be stored in the local speaker's Adj-RIB-
  1833.    Out.
  1834.  
  1835.    The selection process is formalized by defining a function that takes
  1836.    the attribute of a given route as an argument and returns a non-
  1837.    negative integer denoting the degree of preference for the route.
  1838.    The function that calculates the degree of preference for a given
  1839.    route shall not use as its inputs any of the following: the existence
  1840.    of other routes, the non-existence of other routes, or the path
  1841.    attributes of other routes. Route selection then consists of
  1842.    individual application of the degree of preference function to each
  1843.    feasible route, followed by the choice of the one with the highest
  1844.    degree of preference.
  1845.  
  1846.  
  1847.  
  1848.  
  1849.  
  1850. Rekhter & Li                                                   [Page 33]
  1851.  
  1852. RFC 1654                         BGP-4                         July 1994
  1853.  
  1854.  
  1855.    The Decision Process operates on routes contained in each Adj-RIB-In,
  1856.    and is responsible for:
  1857.  
  1858.       - selection of routes to be advertised to BGP speakers located in
  1859.         the local speaker's autonomous system
  1860.  
  1861.       - selection of routes to be advertised to BGP speakers located in
  1862.         neighboring autonomous systems
  1863.  
  1864.       - route aggregation and route information reduction
  1865.  
  1866.    The Decision Process takes place in three distinct phases, each
  1867.    triggered by a different event:
  1868.  
  1869.       a) Phase 1 is responsible for calculating the degree of preference
  1870.       for each route received from a BGP speaker located in a
  1871.       neighboring autonomous system, and for advertising to the other
  1872.       BGP speakers in the local autonomous system the routes that have
  1873.       the highest degree of preference for each distinct destination.
  1874.  
  1875.       b) Phase 2 is invoked on completion of phase 1. It is responsible
  1876.       for choosing the best route out of all those available for each
  1877.       distinct destination, and for installing each chosen route into
  1878.       the appropriate Loc-RIB.
  1879.  
  1880.       c) Phase 3 is invoked after the Loc-RIB has been modified. It is
  1881.       responsible for disseminating routes in the Loc-RIB to each peer
  1882.       located in a neighboring autonomous system, according to the
  1883.       policies contained in the PIB. Route aggregation and information
  1884.       reduction can optionally be performed within this phase.
  1885.  
  1886. 9.1.1 Phase 1: Calculation of Degree of Preference
  1887.  
  1888.    The Phase 1 decision function shall be invoked whenever the local BGP
  1889.    speaker receives an UPDATE message from a peer located in a
  1890.    neighboring autonomous system that advertises a new route, a
  1891.    replacement route, or a withdrawn route.
  1892.  
  1893.    The Phase 1 decision function is a separate process which completes
  1894.    when it has no further work to do.
  1895.  
  1896.    The Phase 1 decision function shall lock an Adj-RIB-In prior to
  1897.    operating on any route contained within it, and shall unlock it after
  1898.    operating on all new or unfeasible routes contained within it.
  1899.  
  1900.    For each newly received or replacement feasible route, the local BGP
  1901.    speaker shall determine a degree of preference. If the route is
  1902.    learned from a BGP speaker in the local autonomous system, either the
  1903.  
  1904.  
  1905.  
  1906. Rekhter & Li                                                   [Page 34]
  1907.  
  1908. RFC 1654                         BGP-4                         July 1994
  1909.  
  1910.  
  1911.    value of the LOCAL_PREF attribute shall be taken as the degree of
  1912.    preference, or the local system shall compute the degree of
  1913.    preference of the route based on preconfigured policy information. If
  1914.    the route is learned from a BGP speaker in a neighboring autonomous
  1915.    system, then the degree of preference shall be computed based on
  1916.    preconfigured policy information.  The exact nature of this policy
  1917.    information and the computation involved is a local matter.  The
  1918.    local speaker shall then run the internal update process of 9.2.1 to
  1919.    select and advertise the most preferable route.
  1920.  
  1921. 9.1.2 Phase 2: Route Selection
  1922.  
  1923.    The Phase 2 decision function shall be invoked on completion of Phase
  1924.    1.  The Phase 2 function is a separate process which completes when
  1925.    it has no further work to do. The Phase 2 process shall consider all
  1926.    routes that are present in the Adj-RIBs-In, including those received
  1927.    from BGP speakers located in its own autonomous system and those
  1928.    received from BGP speakers located in neighboring autonomous systems.
  1929.  
  1930.    The Phase 2 decision function shall be blocked from running while the
  1931.    Phase 3 decision function is in process. The Phase 2 function shall
  1932.    lock all Adj-RIBs-In prior to commencing its function, and shall
  1933.    unlock them on completion.
  1934.  
  1935.    If the NEXT_HOP attribute of a BGP route depicts an address to which
  1936.    the local BGP speaker doesn't have a route in its Loc-RIB, the BGP
  1937.    route SHOULD be excluded from the Phase 2 decision function.
  1938.  
  1939.    For each set of destinations for which a feasible route exists in the
  1940.    Adj-RIBs-In, the local BGP speaker shall identify the route that has:
  1941.  
  1942.       a) the highest degree of preference of any route to the same set
  1943.          of destinations, or
  1944.  
  1945.       b) is the only route to that destination, or
  1946.  
  1947.       c) is selected as a result of the Phase 2 tie breaking rules
  1948.          specified in 9.1.2.1.
  1949.  
  1950.    The local speaker SHALL then install that route in the Loc-RIB,
  1951.    replacing any route to the same destination that is currently being
  1952.    held in the Loc-RIB. The local speaker MUST determine the immediate
  1953.    next hop to the address depicted by the NEXT_HOP attribute of the
  1954.    selected route by performing a lookup in the IGP and selecting one of
  1955.    the possible paths in the IGP.  This immediate next hop MUST be used
  1956.    when installing the selected route in the Loc-RIB.  If the route to
  1957.    the address depicted by the NEXT_HOP attribute changes such that the
  1958.    immediate next hop changes, route selection should be recalculated as
  1959.  
  1960.  
  1961.  
  1962. Rekhter & Li                                                   [Page 35]
  1963.  
  1964. RFC 1654                         BGP-4                         July 1994
  1965.  
  1966.  
  1967.    specified above.
  1968.  
  1969.    Unfeasible routes shall be removed from the Loc-RIB, and
  1970.    corresponding unfeasible routes shall then be removed from the Adj-
  1971.    RIBs-In.
  1972.  
  1973. 9.1.2.1 Breaking Ties (Phase 2)
  1974.  
  1975.    In its Adj-RIBs-In a BGP speaker may have several routes to the same
  1976.    destination that have the same degree of preference. The local
  1977.    speaker can select only one of these routes for inclusion in the
  1978.    associated Loc-RIB. The local speaker considers all equally
  1979.    preferable routes, both those received from BGP speakers located in
  1980.    neighboring autonomous systems, and those received from other BGP
  1981.    speakers located in the local speaker's autonomous system.
  1982.  
  1983.    The following tie-breaking procedure assumes that for each candidate
  1984.    route all the BGP speakers within an autonomous system can ascertain
  1985.    the cost of a path (interior distance) to the address depicted by the
  1986.    NEXT_HOP attribute of the route.  Ties shall be broken according to
  1987.    the following algorithm:
  1988.  
  1989.       a) If the local system is configured to take into account
  1990.          MULTI_EXIT_DISC, and the candidate routes differ in their
  1991.          MULTI_EXIT_DISC attribute, select the route that has the
  1992.          lowest value of the MULTI_EXIT_DISC attribute.
  1993.  
  1994.       b) Otherwise, select the route that has the lowest cost
  1995.          (interior distance) to the entity depicted by the NEXT_HOP
  1996.          attribute of the route.  If there are several routes with the
  1997.          same cost, then the tie-breaking shall be broken as follows:
  1998.  
  1999.          - if at least one of the candidate routes was advertised by
  2000.            the BGP speaker in a neighboring autonomous system, select
  2001.            the route that was advertised by the BGP speaker in a
  2002.            neighboring autonomous system whose BGP Identifier has the
  2003.            lowest value among all other BGP speakers in neighboring
  2004.            autonomous systems;
  2005.  
  2006.          - otherwise, select the route that was advertised by the BGP
  2007.            speaker whose BGP Identifier has the lowest value.
  2008.  
  2009.  
  2010.  
  2011.  
  2012.  
  2013.  
  2014.  
  2015.  
  2016.  
  2017.  
  2018. Rekhter & Li                                                   [Page 36]
  2019.  
  2020. RFC 1654                         BGP-4                         July 1994
  2021.  
  2022.  
  2023. 9.1.3 Phase 3: Route Dissemination
  2024.  
  2025.    The Phase 3 decision function shall be invoked on completion of Phase
  2026.    2, or when any of the following events occur:
  2027.  
  2028.       a) when routes in a Loc-RIB to local destinations have changed
  2029.  
  2030.       b) when locally generated routes learned by means outside of BGP
  2031.          have changed
  2032.  
  2033.       c) when a new BGP speaker - BGP speaker connection has been
  2034.          established
  2035.  
  2036.    The Phase 3 function is a separate process which completes when it
  2037.    has no further work to do. The Phase 3 Routing Decision function
  2038.    shall be blocked from running while the Phase 2 decision function is
  2039.    in process.
  2040.  
  2041.    All routes in the Loc-RIB shall be processed into a corresponding
  2042.    entry in the associated Adj-RIBs-Out. Route aggregation and
  2043.    information reduction techniques (see 9.2.4.1) may optionally be
  2044.    applied.
  2045.  
  2046.    For the benefit of future support of inter-AS multicast capabilities,
  2047.    a BGP speaker that participates in inter-AS multicast routing shall
  2048.    advertise a route it receives from one of its external peers and if
  2049.    it installs it in its Loc-RIB, it shall advertise it back to the peer
  2050.    from which the route was received. For a BGP speaker that does not
  2051.    participate in inter-AS multicast routing such an advertisement is
  2052.    optional. When doing such an advertisement, the NEXT_HOP attribute
  2053.    should be set to the address of the peer. An implementation may also
  2054.    optimize such an advertisement by truncating information in the
  2055.    AS_PATH attribute to include only its own AS number and that of the
  2056.    peer that advertised the route (such truncation requires the ORIGIN
  2057.    attribute to be set to INCOMPLETE).  In addition an implementation is
  2058.    not required to pass optional or discretionary path attributes with
  2059.    such an advertisement.
  2060.  
  2061.    When the updating of the Adj-RIBs-Out and the Forwarding Information
  2062.    Base (FIB) is complete, the local BGP speaker shall run the external
  2063.    update process of 9.2.2.
  2064.  
  2065. 9.1.4 Overlapping Routes
  2066.  
  2067.    A BGP speaker may transmit routes with overlapping Network Layer
  2068.    Reachability Information (NLRI) to another BGP speaker. NLRI overlap
  2069.    occurs when a set of destinations are identified in non-matching
  2070.    multiple routes. Since BGP encodes NLRI using IP prefixes, overlap
  2071.  
  2072.  
  2073.  
  2074. Rekhter & Li                                                   [Page 37]
  2075.  
  2076. RFC 1654                         BGP-4                         July 1994
  2077.  
  2078.  
  2079.    will always exhibit subset relationships.  A route describing a
  2080.    smaller set of destinations (a longer prefix) is said to be more
  2081.    specific than a route describing a larger set of destinations (a
  2082.    shorted prefix); similarly, a route describing a larger set of
  2083.    destinations (a shorter prefix) is said to be less specific than a
  2084.    route describing a smaller set of destinations (a longer prefix).
  2085.  
  2086.    The precedence relationship effectively decomposes less specific
  2087.    routes into two parts:
  2088.  
  2089.       -  a set of destinations described only by the less specific
  2090.          route, and
  2091.  
  2092.       -  a set of destinations described by the overlap of the less
  2093.          specific and the more specific routes
  2094.  
  2095.    When overlapping routes are present in the same Adj-RIB-In, the more
  2096.    specific route shall take precedence, in order from more specific to
  2097.    least specific.
  2098.  
  2099.    The set of destinations described by the overlap represents a portion
  2100.    of the less specific route that is feasible, but is not currently in
  2101.    use.  If a more specific route is later withdrawn, the set of
  2102.    destinations described by the overlap will still be reachable using
  2103.    the less specific route.
  2104.  
  2105.    If a BGP speaker receives overlapping routes, the Decision Process
  2106.    shall take into account the semantics of the overlapping routes. In
  2107.    particular, if a BGP speaker accepts the less specific route while
  2108.    rejecting the more specific route from the same peer, then the
  2109.    destinations represented by the overlap may not forward along the ASs
  2110.    listed in the AS_PATH attribute of that route. Therefore, a BGP
  2111.    speaker has the following choices:
  2112.  
  2113.       a)   Install both the less and the more specific routes
  2114.  
  2115.       b)   Install the more specific route only
  2116.  
  2117.       c)   Install the non-overlapping part of the less specific
  2118.            route only (that implies de-aggregation)
  2119.  
  2120.       d)   Aggregate the two routes and install the aggregated route
  2121.  
  2122.       e)   Install the less specific route only
  2123.  
  2124.       f)   Install neither route
  2125.  
  2126.  
  2127.  
  2128.  
  2129.  
  2130. Rekhter & Li                                                   [Page 38]
  2131.  
  2132. RFC 1654                         BGP-4                         July 1994
  2133.  
  2134.  
  2135.    If a BGP speaker chooses e), then it should add ATOMIC_AGGREGATE
  2136.    attribute to the route. A route that carries ATOMIC_AGGREGATE
  2137.    attribute can not be de-aggregated. That is, the NLRI of this route
  2138.    can not be made more specific.  Forwarding along such a route does
  2139.    not guarantee that IP packets will actually traverse only ASs listed
  2140.    in the AS_PATH attribute of the route.  If a BGP speaker chooses a),
  2141.    it must not advertise the more general route without the more
  2142.    specific route.
  2143.  
  2144. 9.2 Update-Send Process
  2145.  
  2146.    The Update-Send process is responsible for advertising UPDATE
  2147.    messages to all peers. For example, it distributes the routes chosen
  2148.    by the Decision Process to other BGP speakers which may be located in
  2149.    either the same autonomous system or a neighboring autonomous system.
  2150.    Rules for information exchange between BGP speakers located in
  2151.    different autonomous systems are given in 9.2.2; rules for
  2152.    information exchange between BGP speakers located in the same
  2153.    autonomous system are given in 9.2.1.
  2154.  
  2155.    Distribution of routing information between a set of BGP speakers,
  2156.    all of which are located in the same autonomous system, is referred
  2157.    to as internal distribution.
  2158.  
  2159. 9.2.1 Internal Updates
  2160.  
  2161.    The Internal update process is concerned with the distribution of
  2162.    routing information to BGP speakers located in the local speaker's
  2163.    autonomous system.
  2164.  
  2165.    When a BGP speaker receives an UPDATE message from another BGP
  2166.    speaker located in its own autonomous system, the receiving BGP
  2167.    speaker shall not re-distribute the routing information contained in
  2168.    that UPDATE message to other BGP speakers located in its own
  2169.    autonomous system.
  2170.  
  2171.    When a BGP speaker receives a new route from a BGP speaker in a
  2172.    neighboring autonomous system, it shall advertise that route to all
  2173.    other BGP speakers in its autonomous system by means of an UPDATE
  2174.    message if any of the following conditions occur:
  2175.  
  2176.       1) the degree of preference assigned to the newly received route
  2177.       by the local BGP speaker is higher than the degree of preference
  2178.       that the local speaker has assigned to other routes that have been
  2179.       received from BGP speakers in neighboring autonomous systems, or
  2180.  
  2181.       2) there are no other routes that have been received from BGP
  2182.       speakers in neighboring autonomous systems, or
  2183.  
  2184.  
  2185.  
  2186. Rekhter & Li                                                   [Page 39]
  2187.  
  2188. RFC 1654                         BGP-4                         July 1994
  2189.  
  2190.  
  2191.       3) the newly received route is selected as a result of breaking a
  2192.       tie between several routes which have the highest degree of
  2193.       preference, and the same destination (the tie-breaking procedure
  2194.       is specified in 9.2.1.1).
  2195.  
  2196.    When a BGP speaker receives an UPDATE message with a non-empty
  2197.    WITHDRAWN ROUTES field, it shall remove from its Adj-RIB-In all
  2198.    routes whose destinations was carried in this field (as IP prefixes).
  2199.    The speaker shall take the following additional steps:
  2200.  
  2201.       1) if the corresponding feasible route had not been previously
  2202.       advertised, then no further action is necessary
  2203.  
  2204.       2) if the corresponding feasible route had been previously
  2205.       advertised, then:
  2206.  
  2207.          i) if a new route is selected for advertisement that has the
  2208.          same Network Layer Reachability Information as the unfeasible
  2209.          routes, then the local BGP speaker shall advertise the
  2210.          replacement route
  2211.  
  2212.          ii) if a replacement route is not available for advertisement,
  2213.          then the BGP speaker shall include the destinations  of the
  2214.          unfeasible route (in form of IP prefixes) in the WITHDRAWN
  2215.          ROUTES field of an UPDATE message, and shall send this message
  2216.          to each peer to whom it had previously advertised the
  2217.          corresponding feasible route.
  2218.  
  2219.    All feasible routes which are advertised shall be placed in the
  2220.    appropriate Adj-RIBs-Out, and all unfeasible routes which are
  2221.    advertised shall be removed from the Adj-RIBs-Out.
  2222.  
  2223. 9.2.1.1 Breaking Ties (Internal Updates)
  2224.  
  2225.    If a local BGP speaker has connections to several BGP speakers in
  2226.    neighboring autonomous systems, there will be multiple Adj-RIBs-In
  2227.    associated with these peers. These Adj-RIBs-In might contain several
  2228.    equally preferable routes to the same destination, all of which were
  2229.    advertised by BGP speakers located in neighboring autonomous systems.
  2230.    The local BGP speaker shall select one of these routes according to
  2231.    the following rules:
  2232.  
  2233.       a) If the candidate route differ only in their NEXT_HOP and
  2234.       MULTI_EXIT_DISC attributes, and the local system is configured to
  2235.       take into account MULTI_EXIT_DISC attribute, select the routes
  2236.       that has the lowest value of the MULTI_EXIT_DISC attribute.
  2237.  
  2238.  
  2239.  
  2240.  
  2241.  
  2242. Rekhter & Li                                                   [Page 40]
  2243.  
  2244. RFC 1654                         BGP-4                         July 1994
  2245.  
  2246.  
  2247.       b) If the local system can ascertain the cost of a path to the
  2248.       entity depicted by the NEXT_HOP attribute of the candidate route,
  2249.       select the route with the lowest cost.
  2250.  
  2251.       c) In all other cases, select the route that was advertised by the
  2252.       BGP speaker whose BGP Identifier has the lowest value.
  2253.  
  2254. 9.2.2 External Updates
  2255.  
  2256.    The external update process is concerned with the distribution of
  2257.    routing information to BGP speakers located in neighboring autonomous
  2258.    systems. As part of Phase 3 route selection process, the BGP speaker
  2259.    has updated its Adj-RIBs-Out and its Forwarding Table. All newly
  2260.    installed routes and all newly unfeasible routes for which there is
  2261.    no replacement route shall be advertised to BGP speakers located in
  2262.    neighboring autonomous systems by means of UPDATE message.
  2263.  
  2264.    Any routes in the Loc-RIB marked as unfeasible shall be removed.
  2265.    Changes to the reachable destinations within its own autonomous
  2266.    system shall also be advertised in an UPDATE message.
  2267.  
  2268. 9.2.3 Controlling Routing Traffic Overhead
  2269.  
  2270.    The BGP protocol constrains the amount of routing traffic (that is,
  2271.    UPDATE messages) in order to limit both the link bandwidth needed to
  2272.    advertise UPDATE messages and the processing power needed by the
  2273.    Decision Process to digest the information contained in the UPDATE
  2274.    messages.
  2275.  
  2276. 9.2.3.1 Frequency of Route Advertisement
  2277.  
  2278.    The parameter MinRouteAdvertisementInterval determines the minimum
  2279.    amount of time that must elapse between advertisement of routes to a
  2280.    particular destination from a single BGP speaker. This rate limiting
  2281.    procedure applies on a per-destination basis, although the value of
  2282.    MinRouteAdvertisementInterval is set on a per BGP peer basis.
  2283.  
  2284.    Two UPDATE messages sent from a single BGP speaker that advertise
  2285.    feasible routes to some common set of destinations received from BGP
  2286.    speakers in neighboring autonomous systems must be separated by at
  2287.    least MinRouteAdvertisementInterval. Clearly, this can only be
  2288.    achieved precisely by keeping a separate timer for each common set of
  2289.    destinations. This would be unwarranted overhead. Any technique which
  2290.    ensures that the interval between two UPDATE messages sent from a
  2291.    single BGP speaker that advertise feasible routes to some common set
  2292.    of destinations received from BGP speakers in neighboring autonomous
  2293.    systems will be at least MinRouteAdvertisementInterval, and will also
  2294.    ensure a constant upper bound on the interval is acceptable.
  2295.  
  2296.  
  2297.  
  2298. Rekhter & Li                                                   [Page 41]
  2299.  
  2300. RFC 1654                         BGP-4                         July 1994
  2301.  
  2302.  
  2303.    Since fast convergence is needed within an autonomous system, this
  2304.    procedure does not apply for routes receives from other BGP speakers
  2305.    in the same autonomous system. To avoid long-lived black holes, the
  2306.    procedure does not apply to the explicit withdrawal of unfeasible
  2307.    routes (that is, routes whose destinations (expressed as IP prefixes)
  2308.    are listed in the WITHDRAWN ROUTES field of an UPDATE message).
  2309.  
  2310.    This procedure does not limit the rate of route selection, but only
  2311.    the rate of route advertisement. If new routes are selected multiple
  2312.    times while awaiting the expiration of MinRouteAdvertisementInterval,
  2313.    the last route selected shall be advertised at the end of
  2314.    MinRouteAdvertisementInterval.
  2315.  
  2316. 9.2.3.2 Frequency of Route Origination
  2317.  
  2318.    The parameter MinASOriginationInterval determines the minimum amount
  2319.    of time that must elapse between successive advertisements of UPDATE
  2320.    messages that report changes within the advertising BGP speaker's own
  2321.    autonomous systems.
  2322.  
  2323. 9.2.3.3 Jitter
  2324.  
  2325.    To minimize the likelihood that the distribution of BGP messages by a
  2326.    given BGP speaker will contain peaks, jitter should be applied to the
  2327.    timers associated with MinASOriginationInterval, Keepalive, and
  2328.    MinRouteAdvertisementInterval. A given BGP speaker shall apply the
  2329.    same jitter to each of these quantities regardless of the
  2330.    destinations to which the updates are being sent; that is, jitter
  2331.    will not be applied on a "per peer" basis.
  2332.  
  2333.    The amount of jitter to be introduced shall be determined by
  2334.    multiplying the base value of the appropriate timer by a random
  2335.    factor which is uniformly distributed in the range from 0.75 to 1.0.
  2336.  
  2337. 9.2.4 Efficient Organization of Routing Information
  2338.  
  2339.    Having selected the routing information which it will advertise, a
  2340.    BGP speaker may avail itself of several methods to organize this
  2341.    information in an efficient manner.
  2342.  
  2343. 9.2.4.1 Information Reduction
  2344.  
  2345.    Information reduction may imply a reduction in granularity of policy
  2346.    control - after information is collapsed, the same policies will
  2347.    apply to all destinations and paths in the equivalence class.
  2348.  
  2349.    The Decision Process may optionally reduce the amount of information
  2350.    that it will place in the Adj-RIBs-Out by any of the following
  2351.  
  2352.  
  2353.  
  2354. Rekhter & Li                                                   [Page 42]
  2355.  
  2356. RFC 1654                         BGP-4                         July 1994
  2357.  
  2358.  
  2359.    methods:
  2360.  
  2361.       a)   Network Layer Reachability Information (NLRI):
  2362.  
  2363.       Destination IP addresses can be represented as IP address
  2364.       prefixes.  In cases where there is a correspondence between the
  2365.       address structure and the systems under control of an autonomous
  2366.       system administrator, it will be possible to reduce the size of
  2367.       the NLRI carried in the UPDATE messages.
  2368.  
  2369.       b)   AS_PATHs:
  2370.  
  2371.       AS path information can be represented as ordered AS_SEQUENCEs or
  2372.       unordered AS_SETs. AS_SETs are used in the route aggregation
  2373.       algorithm described in 9.2.4.2. They reduce the size of the
  2374.       AS_PATH information by listing each AS number only once,
  2375.       regardless of how many times it may have appeared in multiple
  2376.       AS_PATHs that were aggregated.
  2377.  
  2378.       An AS_SET implies that the destinations listed in the NLRI can be
  2379.       reached through paths that traverse at least some of the
  2380.       constituent autonomous systems. AS_SETs provide sufficient
  2381.       information to avoid routing information looping; however their
  2382.       use may prune potentially feasible paths, since such paths are no
  2383.       longer listed individually as in the form of AS_SEQUENCEs.  In
  2384.       practice this is not likely to be a problem, since once an IP
  2385.       packet arrives at the edge of a group of autonomous systems, the
  2386.       BGP speaker at that point is likely to have more detailed path
  2387.       information and can distinguish individual paths to destinations.
  2388.  
  2389. 9.2.4.2 Aggregating Routing Information
  2390.  
  2391.    Aggregation is the process of combining the characteristics of
  2392.    several different routes in such a way that a single route can be
  2393.    advertised.  Aggregation can occur as part of the decision  process
  2394.    to reduce the amount of routing information that will be placed in
  2395.    the Adj-RIBs-Out.
  2396.  
  2397.    Aggregation reduces the amount of information that a BGP speaker must
  2398.    store and exchange with other BGP speakers. Routes can be aggregated
  2399.    by applying the following procedure separately to path attributes of
  2400.    like type and to the Network Layer Reachability Information.
  2401.  
  2402.    Routes that have the following attributes shall not be aggregated
  2403.    unless the corresponding attributes of each route are identical:
  2404.    MULTI_EXIT_DISC, NEXT_HOP.
  2405.  
  2406.  
  2407.  
  2408.  
  2409.  
  2410. Rekhter & Li                                                   [Page 43]
  2411.  
  2412. RFC 1654                         BGP-4                         July 1994
  2413.  
  2414.  
  2415.    Path attributes that have different type codes can not be aggregated
  2416.    together. Path of the same type code may be aggregated, according to
  2417.    the following rules:
  2418.  
  2419.       ORIGIN attribute: If at least one route among routes that are
  2420.       aggregated has ORIGIN with the value INCOMPLETE, then the
  2421.       aggregated route must have the ORIGIN attribute with the value
  2422.       INCOMPLETE. Otherwise, if at least one route among routes that are
  2423.       aggregated has ORIGIN with the value EGP, then the aggregated
  2424.       route must have the origin attribute with the value EGP. In all
  2425.       other case the value of the ORIGIN attribute of the aggregated
  2426.       route is INTERNAL.
  2427.  
  2428.       AS_PATH attribute: If routes to be aggregated have identical
  2429.       AS_PATH attributes, then the aggregated route has the same AS_PATH
  2430.       attribute as each individual route.
  2431.  
  2432.       For the purpose of aggregating AS_PATH attributes we model each AS
  2433.       within the AS_PATH attribute as a tuple <type, value>, where
  2434.       "type" identifies a type of the path segment the AS belongs to
  2435.       (e.g., AS_SEQUENCE, AS_SET), and "value" is the AS number.  If the
  2436.       routes to be aggregated have different AS_PATH attributes, then
  2437.       the aggregated AS_PATH attribute shall satisfy all of the
  2438.       following conditions:
  2439.  
  2440.          - all tuples of the type AS_SEQUENCE in the aggregated AS_PATH
  2441.          shall appear in all of the AS_PATH in the initial set of routes
  2442.          to be aggregated.
  2443.  
  2444.          - all tuples of the type AS_SET in the aggregated AS_PATH shall
  2445.          appear in at least one of the AS_PATH in the initial set (they
  2446.          may appear as either AS_SET or AS_SEQUENCE types).
  2447.  
  2448.          - for any tuple X of the type AS_SEQUENCE in the aggregated
  2449.          AS_PATH which precedes tuple Y in the aggregated AS_PATH, X
  2450.          precedes Y in each AS_PATH in the initial set which contains Y,
  2451.          regardless of the type of Y.
  2452.  
  2453.          - No tuple with the same value shall appear more than once in
  2454.          the aggregated AS_PATH, regardless of the tuple's type.
  2455.  
  2456.       An implementation may choose any algorithm which conforms to these
  2457.       rules.  At a minimum a conformant implementation shall be able to
  2458.       perform the following algorithm that meets all of the above
  2459.       conditions:
  2460.  
  2461.          - determine the longest leading sequence of tuples (as defined
  2462.          above) common to all the AS_PATH attributes of the routes to be
  2463.  
  2464.  
  2465.  
  2466. Rekhter & Li                                                   [Page 44]
  2467.  
  2468. RFC 1654                         BGP-4                         July 1994
  2469.  
  2470.  
  2471.          aggregated. Make this sequence the leading sequence of the
  2472.          aggregated AS_PATH attribute.
  2473.  
  2474.          - set the type of the rest of the tuples from the AS_PATH
  2475.          attributes of the routes to be aggregated to AS_SET, and append
  2476.          them to the aggregated AS_PATH attribute.
  2477.  
  2478.          - if the aggregated AS_PATH has more than one tuple with the
  2479.          same value (regardless of tuple's type), eliminate all, but one
  2480.          such tuple by deleting tuples of the type AS_SET from the
  2481.          aggregated AS_PATH attribute.
  2482.  
  2483.       Appendix 6, section 6.8 presents another algorithm that satisfies
  2484.       the conditions and  allows for more complex policy configurations.
  2485.  
  2486.       ATOMIC_AGGREGATE: If at least one of the routes to be aggregated
  2487.       has ATOMIC_AGGREGATE path attribute, then the aggregated route
  2488.       shall have this attribute as well.
  2489.  
  2490.       AGGREGATOR: All AGGREGATOR attributes of all routes to be
  2491.       aggregated should be ignored.
  2492.  
  2493. 9.3   Route Selection Criteria
  2494.  
  2495.    Generally speaking, additional rules for comparing routes among
  2496.    several alternatives are outside the scope of this document.  There
  2497.    are two exceptions:
  2498.  
  2499.       - If the local AS appears in the AS path of the new route being
  2500.       considered, then that new route cannot be viewed as better than
  2501.       any other route.  If such a route were ever used, a routing loop
  2502.       would result.
  2503.  
  2504.       - In order to achieve successful distributed operation, only
  2505.       routes with a likelihood of stability can be chosen.  Thus, an AS
  2506.       must avoid using unstable routes, and it must not make rapid
  2507.       spontaneous changes to its choice of route.  Quantifying the terms
  2508.       "unstable" and "rapid" in the previous sentence will require
  2509.       experience, but the principle is clear.
  2510.  
  2511. 9.4   Originating BGP routes
  2512.  
  2513.    A BGP speaker may originate BGP routes by injecting routing
  2514.    information acquired by some other means (e.g., via an IGP) into BGP.
  2515.    A BGP speaker that originates BGP routes shall assign the degree of
  2516.    preference to these routes by passing them through the Decision
  2517.    Process (see Section 9.1).  These routes may also be distributed to
  2518.    other BGP speakers within the local AS as part of the Internal update
  2519.  
  2520.  
  2521.  
  2522. Rekhter & Li                                                   [Page 45]
  2523.  
  2524. RFC 1654                         BGP-4                         July 1994
  2525.  
  2526.  
  2527.    process (see Section 9.2.1). The decision whether to distribute non-
  2528.    BGP acquired routes within an AS via BGP or not depends on the
  2529.    environment within the AS (e.g., type of IGP) and should be
  2530.    controlled via configuration.
  2531.  
  2532.  
  2533.  
  2534.  
  2535.  
  2536.  
  2537.  
  2538.  
  2539.  
  2540.  
  2541.  
  2542.  
  2543.  
  2544.  
  2545.  
  2546.  
  2547.  
  2548.  
  2549.  
  2550.  
  2551.  
  2552.  
  2553.  
  2554.  
  2555.  
  2556.  
  2557.  
  2558.  
  2559.  
  2560.  
  2561.  
  2562.  
  2563.  
  2564.  
  2565.  
  2566.  
  2567.  
  2568.  
  2569.  
  2570.  
  2571.  
  2572.  
  2573.  
  2574.  
  2575.  
  2576.  
  2577.  
  2578. Rekhter & Li                                                   [Page 46]
  2579.  
  2580. RFC 1654                         BGP-4                         July 1994
  2581.  
  2582.  
  2583. Appendix 1.  BGP FSM State Transitions and Actions.
  2584.  
  2585.    This Appendix discusses the transitions between states in the BGP FSM
  2586.    in response to BGP events.  The following is the list of these states
  2587.    and events when the negotiated Hold Time value is non-zero.
  2588.  
  2589.        BGP States:
  2590.  
  2591.                 1 - Idle
  2592.                 2 - Connect
  2593.                 3 - Active
  2594.                 4 - OpenSent
  2595.                 5 - OpenConfirm
  2596.                 6 - Established
  2597.  
  2598.  
  2599.        BGP Events:
  2600.  
  2601.                 1 - BGP Start
  2602.                 2 - BGP Stop
  2603.                 3 - BGP Transport connection open
  2604.                 4 - BGP Transport connection closed
  2605.                 5 - BGP Transport connection open failed
  2606.                 6 - BGP Transport fatal error
  2607.                 7 - ConnectRetry timer expired
  2608.                 8 - Hold Timer expired
  2609.                 9 - KeepAlive timer expired
  2610.                10 - Receive OPEN message
  2611.                11 - Receive KEEPALIVE message
  2612.                12 - Receive UPDATE messages
  2613.                13 - Receive NOTIFICATION message
  2614.  
  2615.  
  2616.  
  2617.  
  2618.  
  2619.  
  2620.  
  2621.  
  2622.  
  2623.  
  2624.  
  2625.  
  2626.  
  2627.  
  2628.  
  2629.  
  2630.  
  2631.  
  2632.  
  2633.  
  2634. Rekhter & Li                                                   [Page 47]
  2635.  
  2636. RFC 1654                         BGP-4                         July 1994
  2637.  
  2638.  
  2639.    The following table describes the state transitions of the BGP FSM
  2640.    and the actions triggered by these transitions.
  2641.  
  2642.     Event                Actions               Message Sent   Next State
  2643.     --------------------------------------------------------------------
  2644.     Idle (1)
  2645.      1            Initialize resources            none             2
  2646.                   Start ConnectRetry timer
  2647.                   Initiate a transport connection
  2648.      others               none                    none             1
  2649.  
  2650.     Connect(2)
  2651.      1                    none                    none             2
  2652.      3            Complete initialization         OPEN             4
  2653.                   Clear ConnectRetry timer
  2654.      5            Restart ConnectRetry timer      none             3
  2655.      7            Restart ConnectRetry timer      none             2
  2656.                   Initiate a transport connection
  2657.      others       Release resources               none             1
  2658.  
  2659.     Active (3)
  2660.      1                    none                    none             3
  2661.      3            Complete initialization         OPEN             4
  2662.                   Clear ConnectRetry timer
  2663.      5            Close connection                                 3
  2664.                   Restart ConnectRetry timer
  2665.      7            Restart ConnectRetry timer      none             2
  2666.                   Initiate a transport connection
  2667.      others       Release resources               none             1
  2668.  
  2669.     OpenSent(4)
  2670.      1                    none                    none             4
  2671.      4            Close transport connection      none             3
  2672.                   Restart ConnectRetry timer
  2673.      6            Release resources               none             1
  2674.     10            Process OPEN is OK            KEEPALIVE          5
  2675.                   Process OPEN failed           NOTIFICATION       1
  2676.     others        Close transport connection    NOTIFICATION       1
  2677.                   Release resources
  2678.  
  2679.  
  2680.  
  2681.  
  2682.  
  2683.  
  2684.  
  2685.  
  2686.  
  2687.  
  2688.  
  2689.  
  2690. Rekhter & Li                                                   [Page 48]
  2691.  
  2692. RFC 1654                         BGP-4                         July 1994
  2693.  
  2694.  
  2695.     OpenConfirm (5)
  2696.      1                   none                     none             5
  2697.      4            Release resources               none             1
  2698.      6            Release resources               none             1
  2699.      9            Restart KeepAlive timer       KEEPALIVE          5
  2700.     11            Complete initialization         none             6
  2701.                   Restart Hold Timer
  2702.     13            Close transport connection                       1
  2703.                   Release resources
  2704.     others        Close transport connection    NOTIFICATION       1
  2705.                   Release resources
  2706.  
  2707.  
  2708.  
  2709.  
  2710.     Established (6)
  2711.      1                   none                     none             6
  2712.      4            Release resources               none             1
  2713.      6            Release resources               none             1
  2714.      9            Restart KeepAlive timer       KEEPALIVE          6
  2715.     11            Restart Hold Timer            KEEPALIVE          6
  2716.     12            Process UPDATE is OK          UPDATE             6
  2717.                   Process UPDATE failed         NOTIFICATION       1
  2718.     13            Close transport connection                       1
  2719.                   Release resources
  2720.     others        Close transport connection    NOTIFICATION       1
  2721.                   Release resources
  2722.    ---------------------------------------------------------------------
  2723.  
  2724.  
  2725.  
  2726.  
  2727.  
  2728.  
  2729.  
  2730.  
  2731.  
  2732.  
  2733.  
  2734.  
  2735.  
  2736.  
  2737.  
  2738.  
  2739.  
  2740.  
  2741.  
  2742.  
  2743.  
  2744.  
  2745.  
  2746. Rekhter & Li                                                   [Page 49]
  2747.  
  2748. RFC 1654                         BGP-4                         July 1994
  2749.  
  2750.  
  2751.       The following is a condensed version of the above state transition
  2752.       table.
  2753.  
  2754.  
  2755.    Events| Idle | Connect | Active | OpenSent | OpenConfirm | Estab
  2756.          | (1)  |   (2)   |  (3)   |    (4)   |     (5)     |   (6)
  2757.          |---------------------------------------------------------------
  2758.     1    |  2   |    2    |   3    |     4    |      5      |    6
  2759.          |      |         |        |          |             |
  2760.     2    |  1   |    1    |   1    |     1    |      1      |    1
  2761.          |      |         |        |          |             |
  2762.     3    |  1   |    4    |   4    |     1    |      1      |    1
  2763.          |      |         |        |          |             |
  2764.     4    |  1   |    1    |   1    |     3    |      1      |    1
  2765.          |      |         |        |          |             |
  2766.     5    |  1   |    3    |   3    |     1    |      1      |    1
  2767.          |      |         |        |          |             |
  2768.     6    |  1   |    1    |   1    |     1    |      1      |    1
  2769.          |      |         |        |          |             |
  2770.     7    |  1   |    2    |   2    |     1    |      1      |    1
  2771.          |      |         |        |          |             |
  2772.     8    |  1   |    1    |   1    |     1    |      1      |    1
  2773.          |      |         |        |          |             |
  2774.     9    |  1   |    1    |   1    |     1    |      5      |    6
  2775.          |      |         |        |          |             |
  2776.    10    |  1   |    1    |   1    |  1 or 5  |      1      |    1
  2777.          |      |         |        |          |             |
  2778.    11    |  1   |    1    |   1    |     1    |      6      |    6
  2779.          |      |         |        |          |             |
  2780.    12    |  1   |    1    |   1    |     1    |      1      | 1 or 6
  2781.          |      |         |        |          |             |
  2782.    13    |  1   |    1    |   1    |     1    |      1      |    1
  2783.          |      |         |        |          |             |
  2784.          ---------------------------------------------------------------
  2785.  
  2786.  
  2787.  
  2788.  
  2789.  
  2790.  
  2791.  
  2792.  
  2793.  
  2794.  
  2795.  
  2796.  
  2797.  
  2798.  
  2799.  
  2800.  
  2801.  
  2802. Rekhter & Li                                                   [Page 50]
  2803.  
  2804. RFC 1654                         BGP-4                         July 1994
  2805.  
  2806.  
  2807. Appendix 2. Comparison with RFC 1267
  2808.  
  2809.    BGP-4 is capable of operating in an environment where a set of
  2810.    reachable destinations may be expressed via a single IP prefix.  The
  2811.    concept of network classes, or subnetting is foreign to BGP-4.  To
  2812.    accommodate these capabilities BGP-4 changes semantics and encoding
  2813.    associated with the AS_PATH attribute. New text has been added to
  2814.    define semantics associated with IP prefixes.  These abilities allow
  2815.    BGP-4 to support the proposed supernetting scheme [9].
  2816.  
  2817.    To simplify configuration this version introduces a new attribute,
  2818.    LOCAL_PREF, that facilitates route selection procedures.
  2819.  
  2820.    The INTER_AS_METRIC attribute has been renamed to be MULTI_EXIT_DISC.
  2821.    A new attribute, ATOMIC_AGGREGATE, has been introduced to insure that
  2822.    certain aggregates are not de-aggregated.  Another new attribute,
  2823.    AGGREGATOR, can be added to aggregate routes in order to advertise
  2824.    which AS and which BGP speaker within that AS caused the aggregation.
  2825.  
  2826.    To insure that Hold Timers are symmetric, the Hold Time is now
  2827.    negotiated on a per-connection basis.  Hold Times of zero are now
  2828.    supported.
  2829.  
  2830. Appendix 3.  Comparison with RFC 1163
  2831.  
  2832.    All of the changes listed in Appendix 2, plus the following.
  2833.  
  2834.    To detect and recover from BGP connection collision, a new field (BGP
  2835.    Identifier) has been added to the OPEN message. New text (Section
  2836.    6.8) has been added to specify the procedure for detecting and
  2837.    recovering from collision.
  2838.  
  2839.    The new document no longer restricts the border router that is passed
  2840.    in the NEXT_HOP path attribute to be part of the same Autonomous
  2841.    System as the BGP Speaker.
  2842.  
  2843.    New document optimizes and simplifies the exchange of the information
  2844.    about previously reachable routes.
  2845.  
  2846. Appendix 4.  Comparison with RFC 1105
  2847.  
  2848.    All of the changes listed in Appendices 2 and 3, plus the following.
  2849.  
  2850.    Minor changes to the RFC1105 Finite State Machine were necessary to
  2851.    accommodate the TCP user interface provided by 4.3 BSD.
  2852.  
  2853.    The notion of Up/Down/Horizontal relations present in RFC1105 has
  2854.    been removed from the protocol.
  2855.  
  2856.  
  2857.  
  2858. Rekhter & Li                                                   [Page 51]
  2859.  
  2860. RFC 1654                         BGP-4                         July 1994
  2861.  
  2862.  
  2863.    The changes in the message format from RFC1105 are as follows:
  2864.  
  2865.       1.  The Hold Time field has been removed from the BGP header and
  2866.       added to the OPEN message.
  2867.  
  2868.       2.  The version field has been removed from the BGP header and
  2869.       added to the OPEN message.
  2870.  
  2871.       3.  The Link Type field has been removed from the OPEN message.
  2872.  
  2873.       4.  The OPEN CONFIRM message has been eliminated and replaced with
  2874.       implicit confirmation provided by the KEEPALIVE message.
  2875.  
  2876.       5.  The format of the UPDATE message has been changed
  2877.       significantly.  New fields were added to the UPDATE message to
  2878.       support multiple path attributes.
  2879.  
  2880.       6.  The Marker field has been expanded and its role broadened to
  2881.       support authentication.
  2882.  
  2883.       Note that quite often BGP, as specified in RFC 1105, is referred
  2884.       to as BGP-1, BGP, as specified in RFC 1163, is referred to as
  2885.       BGP-2, BGP, as specified in RFC1267 is referred to as BGP-3, and
  2886.       BGP, as specified in this document is referred to as BGP-4.
  2887.  
  2888. Appendix 5.  TCP options that may be used with BGP
  2889.  
  2890.    If a local system TCP user interface supports TCP PUSH function, then
  2891.    each BGP message should be transmitted with PUSH flag set.  Setting
  2892.    PUSH flag forces BGP messages to be transmitted promptly to the
  2893.    receiver.
  2894.  
  2895.    If a local system TCP user interface supports setting precedence for
  2896.    TCP connection, then the BGP transport connection should be opened
  2897.    with precedence set to Internetwork Control (110) value (see also
  2898.    [6]).
  2899.  
  2900. Appendix 6.  Implementation Recommendations
  2901.  
  2902.    This section presents some implementation recommendations.
  2903.  
  2904. 6.1 Multiple Networks Per Message
  2905.  
  2906.    The BGP protocol allows for multiple networks with the same AS path
  2907.    and next-hop gateway to be specified in one message. Making use of
  2908.    this capability is highly recommended. With one network per message
  2909.    there is a substantial increase in overhead in the receiver. Not only
  2910.    does the system overhead increase due to the reception of multiple
  2911.  
  2912.  
  2913.  
  2914. Rekhter & Li                                                   [Page 52]
  2915.  
  2916. RFC 1654                         BGP-4                         July 1994
  2917.  
  2918.  
  2919.    messages, but the overhead of scanning the routing table for updates
  2920.    to BGP peers and other routing protocols (and sending the associated
  2921.    messages) is incurred multiple times as well. One method of building
  2922.    messages containing many networks per AS path and gateway from a
  2923.    routing table that is not organized per AS path is to build many
  2924.    messages as the routing table is scanned. As each network is
  2925.    processed, a message for the associated AS path and gateway is
  2926.    allocated, if it does not exist, and the new network is added to it.
  2927.    If such a message exists, the new network is just appended to it. If
  2928.    the message lacks the space to hold the new network, it is
  2929.    transmitted, a new message is allocated, and the new network is
  2930.    inserted into the new message. When the entire routing table has been
  2931.    scanned, all allocated messages are sent and their resources
  2932.    released.  Maximum compression is achieved when all networks share a
  2933.    gateway and common path attributes, making it possible to send many
  2934.    networks in one 4096-byte message.
  2935.  
  2936.    When peering with a BGP implementation that does not compress
  2937.    multiple networks into one message, it may be necessary to take steps
  2938.    to reduce the overhead from the flood of data received when a peer is
  2939.    acquired or a significant network topology change occurs. One method
  2940.    of doing this is to limit the rate of updates. This will eliminate
  2941.    the redundant scanning of the routing table to provide flash updates
  2942.    for BGP peers and other routing protocols. A disadvantage of this
  2943.    approach is that it increases the propagation latency of routing
  2944.    information.  By choosing a minimum flash update interval that is not
  2945.    much greater than the time it takes to process the multiple messages
  2946.    this latency should be minimized. A better method would be to read
  2947.    all received messages before sending updates.
  2948.  
  2949. 6.2  Processing Messages on a Stream Protocol
  2950.  
  2951.    BGP uses TCP as a transport mechanism.  Due to the stream nature of
  2952.    TCP, all the data for received messages does not necessarily arrive
  2953.    at the same time. This can make it difficult to process the data as
  2954.    messages, especially on systems such as BSD Unix where it is not
  2955.    possible to determine how much data has been received but not yet
  2956.    processed.
  2957.  
  2958.    One method that can be used in this situation is to first try to read
  2959.    just the message header. For the KEEPALIVE message type, this is a
  2960.    complete message; for other message types, the header should first be
  2961.    verified, in particular the total length. If all checks are
  2962.    successful, the specified length, minus the size of the message
  2963.    header is the amount of data left to read. An implementation that
  2964.    would "hang" the routing information process while trying to read
  2965.    from a peer could set up a message buffer (4096 bytes) per peer and
  2966.    fill it with data as available until a complete message has been
  2967.  
  2968.  
  2969.  
  2970. Rekhter & Li                                                   [Page 53]
  2971.  
  2972. RFC 1654                         BGP-4                         July 1994
  2973.  
  2974.  
  2975.    received.
  2976.  
  2977. 6.3 Reducing route flapping
  2978.  
  2979.    To avoid excessive route flapping a BGP speaker which needs to
  2980.    withdraw a destination and send an update about a more specific or
  2981.    less specific route shall combine them into the same UPDATE message.
  2982.  
  2983. 6.4 BGP Timers
  2984.  
  2985.    BGP employs five timers: ConnectRetry, Hold Time, KeepAlive,
  2986.    MinASOriginationInterval, and MinRouteAdvertisementInterval The
  2987.    suggested value for the ConnectRetry timer is 120 seconds.  The
  2988.    suggested value for the Hold Time is 90 seconds.  The suggested value
  2989.    for the KeepAlive timer is 30 seconds.  The suggested value for the
  2990.    MinASOriginationInterval is 15 seconds.  The suggested value for the
  2991.    MinRouteAdvertisementInterval is 30 seconds.
  2992.  
  2993.    An implementation of BGP MUST allow these timers to be configurable.
  2994.  
  2995. 6.5 Path attribute ordering
  2996.  
  2997.    Implementations which combine update messages as described above in
  2998.    6.1 may prefer to see all path attributes presented in a known order.
  2999.    This permits them to quickly identify sets of attributes from
  3000.    different update messages which are semantically identical.  To
  3001.    facilitate this, it is a useful optimization to order the path
  3002.    attributes according to type code.  This optimization is entirely
  3003.    optional.
  3004.  
  3005. 6.6 AS_SET sorting
  3006.  
  3007.    Another useful optimization that can be done to simplify this
  3008.    situation is to sort the AS numbers found in an AS_SET.  This
  3009.    optimization is entirely optional.
  3010.  
  3011. 6.7 Control over version negotiation
  3012.  
  3013.    Since BGP-4 is capable of carrying aggregated routes which cannot be
  3014.    properly represented in BGP-3, an implementation which supports BGP-4
  3015.    and another BGP version should provide the capability to only speak
  3016.    BGP-4 on a per-peer basis.
  3017.  
  3018. 6.8 Complex AS_PATH aggregation
  3019.  
  3020.    An implementation which chooses to provide a path aggregation
  3021.    algorithm which retains significant amounts of path information may
  3022.    wish to use the following procedure:
  3023.  
  3024.  
  3025.  
  3026. Rekhter & Li                                                   [Page 54]
  3027.  
  3028. RFC 1654                         BGP-4                         July 1994
  3029.  
  3030.  
  3031.       For the purpose of aggregating AS_PATH attributes of two routes,
  3032.       we model each AS as a tuple <type, value>, where "type" identifies
  3033.       a type of the path segment the AS belongs to (e.g., AS_SEQUENCE,
  3034.       AS_SET), and "value" is the AS number.  Two ASs are said to be the
  3035.       same if their corresponding <type, value> tuples are the same.
  3036.  
  3037.       The algorithm to aggregate two AS_PATH attributes works as
  3038.       follows:
  3039.  
  3040.          a) Identify the same ASs (as defined above) within each AS_PATH
  3041.          attribute that are in the same relative order within both
  3042.          AS_PATH attributes.  Two ASs, X and Y, are said to be in the
  3043.          same order if either:
  3044.             - X precedes Y in both AS_PATH attributes, or - Y precedes X
  3045.             in both AS_PATH attributes.
  3046.  
  3047.          b) The aggregated AS_PATH attribute consists of ASs identified
  3048.          in (a) in exactly the same order as they appear in the AS_PATH
  3049.          attributes to be aggregated. If two consecutive ASs identified
  3050.          in (a) do not immediately follow each other in both of the
  3051.          AS_PATH attributes to be aggregated, then the intervening ASs
  3052.          (ASs that are between the two consecutive ASs that are the
  3053.          same) in both attributes are combined into an AS_SET path
  3054.          segment that consists of the intervening ASs from both AS_PATH
  3055.          attributes; this segment is then placed in between the two
  3056.          consecutive ASs identified in (a) of the aggregated attribute.
  3057.          If two consecutive ASs identified in (a) immediately follow
  3058.          each other in one attribute, but do not follow in another, then
  3059.          the intervening ASs of the latter are combined into an AS_SET
  3060.          path segment; this segment is then placed in between the two
  3061.          consecutive ASs identified in (a) of the aggregated attribute.
  3062.  
  3063.       If as a result of the above procedure a given AS number appears
  3064.       more than once within the aggregated AS_PATH attribute, all, but
  3065.       the last instance (rightmost occurrence) of that AS number should
  3066.       be removed from the aggregated AS_PATH attribute.
  3067.  
  3068. References
  3069.  
  3070.    [1] Mills, D., "Exterior Gateway Protocol Formal Specification", STD
  3071.        18, RFC 904, BBN, April 1984.
  3072.  
  3073.    [2] Rekhter, Y., "EGP and Policy Based Routing in the New NSFNET
  3074.        Backbone", RFC 1092, T.J. Watson Research Center, February 1989.
  3075.  
  3076.    [3] Braun, H-W., "The NSFNET Routing Architecture", RFC 1093,
  3077.        MERIT/NSFNET Project, February 1989.
  3078.  
  3079.  
  3080.  
  3081.  
  3082. Rekhter & Li                                                   [Page 55]
  3083.  
  3084. RFC 1654                         BGP-4                         July 1994
  3085.  
  3086.  
  3087.    [4] Postel, J., "Transmission Control Protocol - DARPA Internet
  3088.        Program Protocol Specification", RFC 793, DARPA, September 1981.
  3089.  
  3090.    [5] Rekhter, Y., and P. Gross, "Application of the Border Gateway
  3091.        Protocol in the Internet", T.J. Watson Research Center, IBM
  3092.        Corp., ANS, RFC 1655, T.J. Watson Research Center, MCI, July
  3093.        1994.
  3094.  
  3095.    [6] Postel, J., "Internet Protocol - DARPA Internet Program Protocol
  3096.        Specification", STD 5, RFC 791, DARPA, September 1981.
  3097.  
  3098.    [7] "Information Processing Systems - Telecommunications and
  3099.        Information Exchange between Systems - Protocol for Exchange of
  3100.        Inter-domain Routeing Information among Intermediate Systems to
  3101.        Support Forwarding of ISO 8473 PDUs", ISO/IEC IS10747, 1993
  3102.  
  3103.    [8] Fuller, V., Li, T., Yu, J., and K. Varadhan, "Classless Inter-
  3104.        Domain Routing (CIDR): an Address Assignment and Aggregation
  3105.        Strategy", RFC 1519, BARRNet, cisco, MERIT, OARnet, September
  3106.        1993.
  3107.  
  3108.    [9] Rekhter, Y., and T. Li, "An Architecture for IP Address
  3109.        Allocation with CIDR", RFC 1518, T.J. Watson Research Center,
  3110.        cisco, September 1993.
  3111.  
  3112. Security Considerations
  3113.  
  3114.    Security issues are not discussed in this memo.
  3115.  
  3116. Editors' Addresses
  3117.  
  3118.    Yakov Rekhter
  3119.    T.J. Watson Research Center IBM Corporation
  3120.    P.O. Box 218
  3121.    Yorktown Heights, NY 10598
  3122.  
  3123.    Phone:  (914) 945-3896
  3124.    EMail:  yakov@watson.ibm.com
  3125.  
  3126.  
  3127.    Tony Li
  3128.    cisco Systems, Inc.
  3129.    1525 O'Brien Drive
  3130.    Menlo Park, CA 94025
  3131.  
  3132.    EMail: tli@cisco.com
  3133.  
  3134.  
  3135.  
  3136.  
  3137.  
  3138. Rekhter & Li                                                   [Page 56]
  3139.  
  3140.