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