home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 1100s / rfc1105.txt < prev    next >
Text File  |  1989-06-18  |  37KB  |  955 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                        K. Lougheed
  8. Request for Comments:  1105                                cisco Systems
  9.                                                               Y. Rekhter
  10.                                   T.J. Watson Research Center, IBM Corp.
  11.                                                                June 1989
  12.  
  13.                     A Border Gateway Protocol (BGP)
  14.  
  15. Status of this Memo
  16.  
  17.    This RFC outlines a specific approach for the exchange of network
  18.    reachability information between Autonomous Systems.
  19.  
  20.    At the time of this writing, the Border Gateway Protocol
  21.    implementations exist for cisco routers as well as for the NSFNET
  22.    Nodal Switching Systems.  A public domain version for "gated" is
  23.    currently being implemented.
  24.  
  25.    Distribution of this memo is unlimited.
  26.  
  27. 1. Introduction
  28.  
  29.    The Border Gateway Protocol (BGP) is an inter-autonomous system
  30.    routing protocol.  It is built on experience gained with EGP as
  31.    defined in RFC 904 [1] and EGP usage in the NSFNET Backbone as
  32.    described in RFC 1092 [2] and RFC 1093 [3].
  33.  
  34.    The primary function of a BGP speaking system is to exchange network
  35.    reachability information with other BGP systems.  This network
  36.    reachability information includes information on the autonomous
  37.    systems (AS's) that traffic must transit to reach these networks.
  38.    This information is sufficient to construct a graph of AS
  39.    connectivity from which routing loops may be pruned and policy
  40.    decisions at an AS level may be enforced.
  41.  
  42.    BGP runs over a reliable transport level protocol.  This eliminates
  43.    the need to implement explicit update fragmentation, retransmission,
  44.    acknowledgement, and sequencing.  Any authentication scheme used by
  45.    the transport protocol may be used in addition to BGP's own
  46.    authentication mechanisms.
  47.  
  48.    The initial BGP implementation is based on TCP [4], however any
  49.    reliable transport may be used.  A message passing protocol such as
  50.    VMTP [5] might be more natural for BGP.  TCP will be used, however,
  51.    since it is present in virtually all commercial routers and hosts.
  52.    In the following descriptions the phrase "transport protocol
  53.    connection" can be understood to refer to a TCP connection.  BGP uses
  54.    TCP port 179 for establishing its connections.
  55.  
  56.  
  57.  
  58. Lougheed & Rekhter                                              [Page 1]
  59.  
  60. RFC 1105                          BGP                          June 1989
  61.  
  62.  
  63. 2. Summary of Operation
  64.  
  65.    Two hosts form a transport protocol connection between one another.
  66.    They exchange messages to open and confirm the connection parameters.
  67.    The initial data flow is the entire BGP routing table.  Incremental
  68.    updates are sent as the routing tables change.  Keepalive messages
  69.    are sent periodically to ensure the liveness of the connection.
  70.    Notification messages are sent in response to errors or special
  71.    conditions.  If a connection encounters an error condition, a
  72.    notification message is sent and the connection is optionally closed.
  73.  
  74.    The hosts executing the Border Gateway Protocol need not be routers.
  75.    A non-routing host could exchange routing information with routers
  76.    via EGP or even an interior routing protocol.  That non-routing host
  77.    could then use BGP to exchange routing information with a border
  78.    gateway in another autonomous system.  The implications and
  79.    applications of this architecture are for further study.
  80.  
  81.    If a particular AS has more than one BGP gateway, then all these
  82.    gateways should have a consistent view of routing.  A consistent view
  83.    of the interior routes of the autonomous system is provided by the
  84.    intra-AS routing protocol.  A consistent view of the routes exterior
  85.    to the AS may be provided in a variety of ways.  One way is to use
  86.    the BGP protocol to exchange routing information between the BGP
  87.    gateways within a single AS.  In this case, in order to maintain
  88.    consist routing information, these gateways MUST have direct BGP
  89.    sessions with each other (the BGP sessions should form a complete
  90.    graph).  Note that this requirement does not imply that all BGP
  91.    gateways within a single AS must have direct links to each other;
  92.    other methods may be used to ensure consistent routing information.
  93.  
  94. 3. Message Formats
  95.  
  96.    This section describes message formats and actions to be taken when
  97.    errors are detected while processing these messages.
  98.  
  99.    Messages are sent over a reliable transport protocol connection.  A
  100.    message is processed after it is entirely received.  The maximum
  101.    message size is 1024 bytes.  All implementations are required to
  102.    support this maximum message size.  The smallest message that may be
  103.    sent consists of a BGP header without a data portion, or 8 bytes.
  104.  
  105.    The phrase "the BGP connection is closed" means that the transport
  106.    protocol connection has been closed and that all resources for that
  107.    BGP connection have been deallocated.  Routing table entries
  108.    associated with the remote peer are marked as invalid.  This
  109.    information is passed to other BGP peers before being deleted from
  110.    the system.
  111.  
  112.  
  113.  
  114. Lougheed & Rekhter                                              [Page 2]
  115.  
  116. RFC 1105                          BGP                          June 1989
  117.  
  118.  
  119. 3.1 Message Header Format
  120.  
  121.    Each message has a fixed size header.  There may or may not be a data
  122.    portion following the header, depending on the message type.  The
  123.    layout of these fields is shown below.
  124.  
  125.     0                   1                   2                   3
  126.     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
  127.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  128.    |        Marker                |          Length                |
  129.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  130.    |    Version   |     Type      |        Hold Time               |
  131.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  132.  
  133.    Marker: 16 bits
  134.  
  135.       The Marker field is 16 bits of all ones.  This field is used to
  136.       mark the start of a message.  If the first two bytes of a message
  137.       are not all ones then we have a synchronization error and the BGP
  138.       connection should be closed after sending a notification message
  139.       with opcode 5 (connection not synchronized).  No notification data
  140.       is sent.
  141.  
  142.    Length: 16 bits
  143.  
  144.       The Length field is 16 bits.  It is the total length of the
  145.       message, incluluding header, in bytes.  If an illegal length is
  146.       encountered (more than 1024 bytes or less than 8 bytes), a
  147.       notification message with opcode 6 (bad message length) and two
  148.       data bytes of the bad length should be sent and the BGP connection
  149.       closed.
  150.  
  151.    Version: 8 bits
  152.  
  153.       The Version field is 8 bits of protocol version number.  The
  154.       current BGP version number is 1.  If a bad version number is
  155.       found, a notification message with opcode 8 (bad version number)
  156.       should be sent and the BGP connection closed.  The bad version
  157.       number should be included in one byte of notification data.
  158.  
  159.    Type: 8 bits
  160.  
  161.       The Type field is 8 bits of message type code.  The following type
  162.       codes are defined:
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Lougheed & Rekhter                                              [Page 3]
  171.  
  172. RFC 1105                          BGP                          June 1989
  173.  
  174.  
  175.                     1 - OPEN
  176.                     2 - UPDATE
  177.                     3 - NOTIFICATION
  178.                     4 - KEEPALIVE
  179.                     5 - OPEN CONFIRM
  180.  
  181.       If an unrecognized type value is found, a notification message
  182.       with opcode 7 (bad type code) and data consisting of the byte of
  183.       type field in question should be sent and the BGP connection
  184.       closed.
  185.  
  186.    Hold Timer: 16 bits.
  187.  
  188.       This field contains the number of seconds that may elapse since
  189.       receiving a BGP KEEPALIVE or BGP UPDATE message from our BGP peer
  190.       before we declare an error and close the BGP connection.
  191.  
  192. 3.2  OPEN Message Format
  193.  
  194.    After a transport protocol connection is established, the first
  195.    message sent by either side is an OPEN message.  If the OPEN message
  196.    is acceptable, an OPEN CONFIRM message confirming the OPEN is sent
  197.    back.  Once the OPEN is confirmed, UPDATE, KEEPALIVE, and
  198.    NOTIFICATION messages may be exchanged.
  199.  
  200.    In addition to the fixed size BGP header, the OPEN message contains
  201.    the following fields.
  202.  
  203.     0                   1                   2                   3
  204.     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
  205.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  206.    |    My Autonomous System      |   Link Type   |  Auth. Code    |
  207.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  208.    |                                                               |
  209.    |                 Authentication Data                           |
  210.    |                                                               |
  211.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  212.  
  213.    My Autonomous System: 16 bits
  214.  
  215.       This field is our 16 bit autonomous system number.  If there is a
  216.       problem with this field, a notification message with opcode 9
  217.       (invalid AS field) should be sent and the BGP connection closed.
  218.       No notification data is sent.
  219.  
  220.    Link Type: 8 bits
  221.  
  222.       The Link Type field is a single octet containing one of the
  223.  
  224.  
  225.  
  226. Lougheed & Rekhter                                              [Page 4]
  227.  
  228. RFC 1105                          BGP                          June 1989
  229.  
  230.  
  231.       following codes defining our position in the AS graph relative to
  232.       our peer.
  233.  
  234.                        0  - INTERNAL
  235.                        1  - UP
  236.                        2  - DOWN
  237.                        3  - H-LINK
  238.  
  239.       UP indicates the peer is higher in the AS hierarchy, DOWN
  240.       indicates lower, and H-LINK indicates at the same level.  INTERNAL
  241.       indicates that the peer is another BGP speaking host in our
  242.       autonomous system.  INTERNAL links are used to keep AS routing
  243.       information consistent with an AS with multiple border gateways.
  244.       If the Link Type field is unacceptable, a notification message
  245.       with opcode 1 (link type error in open) and data consisting of the
  246.       expected link type should be sent and the BGP connection closed.
  247.       The acceptable values for the Link Type fields of two BGP peers
  248.       are discussed below.
  249.  
  250.    Authentication Code: 8 bits
  251.  
  252.       The Authentication Code field is an octet whose value describes
  253.       the authentication mechanism being used.  A value of zero
  254.       indicates no BGP authentication.  Note that a separate
  255.       authentication mechanism may be used in establishing the transport
  256.       level connection.  If the authentication code is not recognized, a
  257.       notification message with opcode 2 (unknown authentication code)
  258.       and no data is sent and the BGP connection is closed.
  259.  
  260.    Authentication Data: variable length
  261.  
  262.       The Authentication Data field is a variable length field
  263.       containing authentication data.  If the value of Authentication
  264.       Code field is zero, the Authentication Data field has zero length.
  265.       If authentication fails, a notification message with opcode 3
  266.       (authentication failure) and no data is sent and the BGP
  267.       connection is closed.
  268.  
  269. 3.3 OPEN CONFIRM Message Format
  270.  
  271.    An OPEN CONFIRM message is sent after receiving an OPEN message.
  272.    This completes the BGP connection setup.  UPDATE, NOTIFICATION, and
  273.    KEEPALIVE messages may now be exchanged.
  274.  
  275.    An OPEN CONFIRM message consists of a BGP header with an OPEN CONFIRM
  276.    type code.  There is no data in an OPEN CONFIRM message.
  277.  
  278.  
  279.  
  280.  
  281.  
  282. Lougheed & Rekhter                                              [Page 5]
  283.  
  284. RFC 1105                          BGP                          June 1989
  285.  
  286.  
  287. 3.4 UPDATE Message Format
  288.  
  289.    UPDATE messages are used to transfer routing information between BGP
  290.    peers.  The information in the UPDATE packet can be used to construct
  291.    a graph describing the relationships of the various autonomous
  292.    systems.  By applying rules to be discussed, routing information
  293.    loops and some other anomalies may be detected and removed from the
  294.    inter-AS routing.
  295.  
  296.    Whenever an error in a UPDATE message is detected, a notification
  297.    message is sent with opcode 4 (bad update), a two byte subcode
  298.    describing the nature of the problem, and a data field consisting of
  299.    as much of the UPDATE message data portion as possible.  UPDATE
  300.    messages have the following format:
  301.  
  302.     0                   1                   2                   3
  303.     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
  304.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  305.    |                         Gateway                               |
  306.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  307.    |   AS count    | Direction     |         AS Number             |
  308.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  309.    |     repeat (Direction, AS Number) pairs AS count times        |
  310.    /                                                               /
  311.    /                                                               /
  312.    |                                                               |
  313.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  314.    |      Net Count                |
  315.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  316.    |                        Network                                |
  317.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  318.    |      Metric                   |                               |
  319.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
  320.    |       repeat (Network, Metric) pairs Net Count times          |
  321.    /                                                               /
  322.    /                                                               /
  323.    |                                                               |
  324.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  325.  
  326.    Gateway: 32 bits.
  327.  
  328.       The Gateway field is the address of a gateway that has routes to
  329.       the Internet networks listed in the rest of the UPDATE message.
  330.       This gateway MUST belong to the same AS as the BGP peer who
  331.       advertises it.  If there is a problem with the gateway field, a
  332.       notification message with subcode 6 (invalid gateway field) is
  333.       sent.
  334.  
  335.  
  336.  
  337.  
  338. Lougheed & Rekhter                                              [Page 6]
  339.  
  340. RFC 1105                          BGP                          June 1989
  341.  
  342.  
  343.    AS count: 8 bits.
  344.  
  345.       This field is the count of Direction and AS Number pairs in this
  346.       UPDATE message.  If an incorrect AS count field is detected,
  347.       subcode 1 (invalid AS count) is specified in the notification
  348.       message.
  349.  
  350.    Direction: 8 bits
  351.  
  352.       The Direction field is an octet containing the direction taken by
  353.       the routing information when exiting the AS defined by the
  354.       succeeding AS Number field.  The following values are defined.
  355.  
  356.             1  - UP            (went up a link in the graph)
  357.             2  - DOWN          (went down a link in the graph)
  358.             3  - H_LINK        (horizontal link in the graph)
  359.             4  - EGP_LINK      (EGP derived information)
  360.             5  - INCOMPLETE    (incomplete information)
  361.  
  362.       There is a special provision to pass exterior learned (non-BGP)
  363.       routes over BGP.  If an EGP learned route is passed over BGP, then
  364.       the Direction field is set to EGP-LINK and the AS Number field is
  365.       set to the AS number of the EGP peer that advertised this route.
  366.       All other exterior-learned routes (non-BGP and non-EGP) may be
  367.       passed by setting AS Number field to zero and Direction field to
  368.       INCOMPLETE.  If the direction code is not recognized, a
  369.       notification message with subcode 2 (invalid direction code) is
  370.       sent.
  371.  
  372.    AS Number: 16 bits
  373.  
  374.       This field is the AS number that transmitted the routing
  375.       information.  If there is a problem with this AS number, a
  376.       notification message with subcode 3 (invalid autonomous system) is
  377.       sent.
  378.  
  379.    Net Count: 16 bits.
  380.  
  381.       The Net Count field is the number of Metric and Network field
  382.       pairs which follow this field.  If there is a problem with this
  383.       field, a notification with subcode 7 (invalid net count field) is
  384.       sent.
  385.  
  386.    Network: 32 bits
  387.  
  388.       The Network field is four bytes of Internet network number.  If
  389.       there is a problem with the network field, a notification message
  390.       with subcode 8 (invalid network field) is sent.
  391.  
  392.  
  393.  
  394. Lougheed & Rekhter                                              [Page 7]
  395.  
  396. RFC 1105                          BGP                          June 1989
  397.  
  398.  
  399.    Metric: 16 bits
  400.  
  401.       The Metric field is 16 bits of an unspecified metric.  BGP metrics
  402.       are comparable ONLY if routes have exactly the same AS path.  A
  403.       metric of all ones indicates the network is unreachable.  In all
  404.       other cases the metric field is MEANINGLESS and MUST BE IGNORED.
  405.       There are no illegal metric values.
  406.  
  407. 3.5  NOTIFICATION Message Format
  408.  
  409.    NOTIFICATION messages are sent when an error condition is detected.
  410.    The BGP connection is closed shortly after sending the notification
  411.    message.
  412.  
  413.     0                   1                   2                   3
  414.     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
  415.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  416.    |          Opcode               |           Data                |
  417.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
  418.    |                                                               |
  419.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  420.  
  421.    Opcode: 16 bits
  422.  
  423.       The Opcode field describes the type of NOTIFICATION.  The
  424.       following opcodes have been defined.
  425.  
  426.             1 (*) - link type error in open.  Data is one byte of proper
  427.                     link type.
  428.             2 (*) - unknown authentication code.  No data.
  429.             3 (*) - authentication failure.  No data.
  430.             4     - update error.  See below for data description.
  431.             5 (*) - connection out of sync.  No data.
  432.             6 (*) - invalid message length.  Data is two bytes of
  433.                     bad length.
  434.             7 (*) - invalid message type.  Data is one byte of bad
  435.                     message type.
  436.             8 (*) - invalid version number.  Data is one byte of
  437.                     bad version.
  438.             9 (*) - invalid AS field in OPEN.  No data.
  439.            10 (*) - BGP Cease.  No data.
  440.  
  441.       The starred opcodes in the list above are considered fatal errors
  442.       and cause transport connection termination.
  443.  
  444.       The update error (opcode 4) has as data 16 bits of subcode
  445.       followed by the last UPDATE message in question.  After the
  446.       subcode comes as much of the data portion of the UPDATE in
  447.  
  448.  
  449.  
  450. Lougheed & Rekhter                                              [Page 8]
  451.  
  452. RFC 1105                          BGP                          June 1989
  453.  
  454.  
  455.       question as possible.  The following subcodes are defined:
  456.  
  457.                1 - invalid AS count
  458.                2 - invalid direction code
  459.                3 - invalid autonomous system
  460.                4 - EGP_LINK or INCOMPLETE_LINK link type at other than
  461.                    the end of the AS path list
  462.                5 - routing loop
  463.                6 - invalid gateway field
  464.                7 - invalid Net Count field
  465.                8 - invalid network field
  466.  
  467.    Data: variable
  468.  
  469.       The Data field contains zero or more bytes of data to be used in
  470.       diagnosing the reason for the NOTIFICATION.  The contents of the
  471.       Data field depend upon the opcode.  See the opcode descriptions
  472.       above for more details.
  473.  
  474. 3.6 KEEPALIVE Message Format
  475.  
  476.    BGP does not use any transport protocol based keepalive mechanism to
  477.    determine if peers are reachable.  Instead KEEPALIVE messages are
  478.    exchanged between peers often enough as not to cause the hold time
  479.    (as advertised in the BGP header) to expire.  A reasonable minimum
  480.    frequency of KEEPALIVE exchange would be one third of the Hold Time
  481.    interval.
  482.  
  483.    As soon as the Hold Time associated with BGP peer has expired, the
  484.    BGP connection is closed and BGP deallocates all resources associated
  485.    with this peer.
  486.  
  487.    The KEEPALIVE message is a BGP header without any data.
  488.  
  489. 4. BGP Finite State machine.
  490.  
  491.    This section specifies BGP operation in terms of a Finite State
  492.    Machine (FSM).  Following is a brief summary and overview of BGP
  493.    operations by state as determined by this FSM.  A condensed version
  494.    of the BGP FSM is found in Appendix 1.
  495.  
  496.    Initially BGP is in the BGP_Idle state.
  497.  
  498.    BGP_Idle state:
  499.  
  500.       In this state BGP refuses all incoming BGP connections.  No
  501.       resources are allocated to the BGP neighbor.  In response to the
  502.       Start event (initiated by either system or operator) the local
  503.  
  504.  
  505.  
  506. Lougheed & Rekhter                                              [Page 9]
  507.  
  508. RFC 1105                          BGP                          June 1989
  509.  
  510.  
  511.       system initializes all BGP resources and changes its state to
  512.       BGP_Active.
  513.  
  514.    BGP_Active state:
  515.  
  516.       In this state BGP is trying to acquire a BGP neighbor by opening a
  517.       transport protocol connection.  If the transport protocol open
  518.       fails (for example, retransmission timeout),  BGP stays in the
  519.       BGP_Active state.
  520.  
  521.       Otherwise,  the local system sends an OPEN message to its peer,
  522.       and changes its state to BGP_OpenSent.  Since the hold time of the
  523.       peer is still undetermined, the hold time is initialized to some
  524.       large value.
  525.  
  526.       In response to the Stop event (initiated by either system or
  527.       operator) the local system releases all BGP resources and changes
  528.       its state to BGP_Idle.
  529.  
  530.    BGP_OpenSent state:
  531.  
  532.       In this state BGP waits for an OPEN message from its peer.  When
  533.       an OPEN message is received, all fields are checked for
  534.       correctness.  If the initial BGP header checking detects an error,
  535.       BGP deallocates all resources associated with this peer and
  536.       returns to the BGP_Active state.  Otherwise, the Link Type,
  537.       Authentication Code, and Authentication Data fields are checked
  538.       for correctness.
  539.  
  540.       If the link type is incorrect, a NOTIFICATION message with opcode
  541.       1 (link type error in open) is sent.  The following combination of
  542.       link type fields are correct; all other combinations are invalid.
  543.  
  544.                       Our view         Peer view
  545.                       UP                DOWN
  546.                       DOWN              UP
  547.                       INTERNAL          INTERNAL
  548.                       H-LINK            H-LINK
  549.  
  550.       If the link between two peers is INTERNAL, then AS number of both
  551.       peers must be the same.  Otherwise, a NOTIFICATION message with
  552.       opcode 1 (link type error in open) is sent.
  553.  
  554.       If both peers have the same AS number and the link type between
  555.       these peers is not INTERNAL, then a NOTIFICATION message with
  556.       opcode 1 (link type error in open) is sent.
  557.  
  558.       If the value of the Authentication Code field is zero, any
  559.  
  560.  
  561.  
  562. Lougheed & Rekhter                                             [Page 10]
  563.  
  564. RFC 1105                          BGP                          June 1989
  565.  
  566.  
  567.       information in the Authentication Data field (if present) is
  568.       ignored.  If the Authentication Code field is non-zero it is
  569.       checked for known authentication codes.  If authentication code is
  570.       unknown, then the BGP NOTIFICATION message with opcode 2 (unknown
  571.       authentication code) is sent.
  572.  
  573.       If the Authentication Code value is non-zero, then the
  574.       corresponding authentication procedure is invoked.  The default
  575.       values are a zero Authentication Code and no Authentication Data.
  576.  
  577.       If any of the above tests detect an error, the local system closes
  578.       the BGP connection and changes its state to BGP_Idle.
  579.  
  580.       If there are no errors in the BGP OPEN message, BGP sends an OPEN
  581.       CONFIRM message and goes into the BGP_OpenConfirm state.  At this
  582.       point the hold timer which was originally set to some arbitrary
  583.       large value (see above) is replaced with the value indicated in
  584.       the OPEN message.
  585.  
  586.       If disconnect notification is received from the underlying
  587.       transport protocol or if the hold time expires, the local system
  588.       closes the BGP connection and changes its state to BGP_Idle.
  589.  
  590.    BGP_OpenConfirm state:
  591.  
  592.       In this state BGP waits for an OPEN CONFIRM message.  As soon as
  593.       this message is received, BGP changes its state to
  594.       BGP_Established.  If the hold timer expires before an OPEN CONFIRM
  595.       message is received, the local system closes the BGP connection
  596.       and changes its state to BGP_Idle.
  597.  
  598.    BGP_Established state:
  599.  
  600.       In the BGP_Established state BGP can exchange UPDATE,
  601.       NOTIFICATION, and KEEPALIVE messages with its peer.
  602.  
  603.       If disconnect notification is received from the underlying
  604.       transport protocol or if the hold time expires, the local system
  605.       closes the BGP connection and changes its state to BGP_Idle.
  606.  
  607.       In response to the Stop event initiated by either the system or
  608.       operator, the local system sends a NOTIFICATION message with
  609.       opcode 10 (BGP Cease), closes the BGP connection, and changes its
  610.       state to BGP_Idle.
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618. Lougheed & Rekhter                                             [Page 11]
  619.  
  620. RFC 1105                          BGP                          June 1989
  621.  
  622.  
  623. 5. UPDATE Message Handling
  624.  
  625.    A BGP UPDATE message may be received only in the BGP_Established
  626.    state.  When a BGP UPDATE message is received, each field is checked
  627.    for validity.  When a NOTIFICATION message is sent regarding an
  628.    UPDATE, the opcode is always 4 (update error), the subcode depends on
  629.    the type of error, and the rest of the data field is as much as
  630.    possible of the data portion of the UPDATE that caused the error.
  631.  
  632.    If the Gateway field is incorrect, a BGP NOTIFICATION message is sent
  633.    with subcode 6 (invalid gateway field).  All information in this
  634.    UPDATE message is discarded.
  635.  
  636.    If the AS Count field is less than or equal to zero, a BGP
  637.    NOTIFICATION is sent with subcode 1 (invalid AS count).  Otherwise,
  638.    the complete AS path is extracted and checked as described below.
  639.  
  640.    If one of the Direction fields in the AS route list is not defined, a
  641.    BGP NOTIFICATION message is with subcode 2 (invalid direction code).
  642.  
  643.    If one of the AS Number fields in the AS route list is incorrect, a
  644.    BGP NOTIFICATION message is sent with subcode 3 (invalid autonomous
  645.    system).
  646.  
  647.    If either a EGP_LINK or a INCOMPLETE_LINK link type occurs at other
  648.    than the end of the AS path, a BGP NOTIFICATION message is sent with
  649.    subcode 4 (EGP_LINK or INCOMPLETE_LINK link type at other than the
  650.    end of the AS path list).
  651.  
  652.    If none of the above tests failed, the full AS route is checked for
  653.    AS loops.
  654.  
  655.    AS loop detection is done by scanning the full AS route and checking
  656.    that each AS in this route occurs only once.  If an AS loop is
  657.    detected, a BGP NOTIFICATION message is sent with subcode 5 (routing
  658.    loop).
  659.  
  660.    If any of the above errors are detected, no further processing is
  661.    done.  Otherwise, the complete AS path is correct and the rest of the
  662.    UPDATE message is processed.
  663.  
  664.    If the Net Count field is incorrect, a BGP NOTIFICATION message is
  665.    sent with subcode 7 (invalid Net Count field).
  666.  
  667.    Each network and metric pair listed in the BGP UPDATE message is
  668.    checked for a valid network number.  If the Network field is
  669.    incorrect, a BGP Notification message is sent with subcode 8 (invalid
  670.    network field).  No checking is done on the metric field.  It is up
  671.  
  672.  
  673.  
  674. Lougheed & Rekhter                                             [Page 12]
  675.  
  676. RFC 1105                          BGP                          June 1989
  677.  
  678.  
  679.    to a particular implementation to decide whether to continue
  680.    processing or terminate it upon the first incorrect network.
  681.  
  682.    If the network, its complete AS path, and the gateway are correct,
  683.    then the route is compared with other routes to the same network.  If
  684.    the new route is better than the current one, then it is flooded to
  685.    other BGP peers as follows:
  686.  
  687.     - If the BGP UPDATE was received over the INTERNAL link, it is not
  688.       propagated over any other INTERNAL link.  This restriction is
  689.       due to the fact that all BGP gateways within a single AS
  690.       form a completely connected graph (see above).
  691.  
  692.     - Before sending a BGP UPDATE message over the non-INTERNAL links,
  693.       check the AS path to insure that doing so would not cause a
  694.       routing loop.  The BGP UPDATE message is then propagated (subject
  695.       to the local policy restrictions) over any of the non-INTERNAL
  696.       link of a routing loop would not result.
  697.  
  698.     - If the BGP UPDATE message is propagated over a non-INTERNAL link,
  699.       then the current AS number and link type of the link over which
  700.       it is going to be propagated is prepended to the full AS path
  701.       and the AS count field is incremented by 1.  If the BGP UPDATE
  702.       message is propagated over an INTERNAL link, then the full AS
  703.       path passed unmodified and the AS count stays the same.  The
  704.       Gateway field is replaced with the sender's own address.
  705.  
  706. 6. Acknowledgements
  707.  
  708.    We would like to express our thanks to Len Bosack (cisco Systems),
  709.    Jeff Honig (Cornell University) and all members of the IWG task force
  710.    for their contributions to this document.
  711.  
  712.  
  713.  
  714.  
  715.  
  716.  
  717.  
  718.  
  719.  
  720.  
  721.  
  722.  
  723.  
  724.  
  725.  
  726.  
  727.  
  728.  
  729.  
  730. Lougheed & Rekhter                                             [Page 13]
  731.  
  732. RFC 1105                          BGP                          June 1989
  733.  
  734.  
  735.                                 Appendix 1
  736.  
  737. BGP FSM State Transitions and Actions.
  738.  
  739.    This Appendix discusses the transitions between states in the BGP FSM
  740.    in response to BGP events.  The following is the list of these states
  741.    and events.
  742.  
  743.        BGP States:
  744.  
  745.             1 - BGP_Idle
  746.             2 - BGP_Active
  747.             3 - BGP_OpenSent
  748.             4 - BGP_OpenConfirm
  749.             5 - BGP_Established
  750.  
  751.        BGP Events:
  752.  
  753.             1 - BGP Start
  754.             2 - BGP Transport connection open
  755.             3 - BGP Transport connection closed
  756.             4 - BGP Transport connection open failed
  757.             5 - Receive OPEN message
  758.             6 - Receive OPEN CONFIRM message
  759.             7 - Receive KEEPALIVE message
  760.             8 - Receive UPDATE messages
  761.             9 - Receive NOTIFICATION message
  762.            10 - Holdtime timer expired
  763.            11 - KeepAlive timer expired
  764.            12 - Receive CEASE message
  765.            13 - BGP Stop
  766.  
  767.    The following table describes the state transitions of the BGP FSM
  768.    and the actions triggered by these transitions.
  769.  
  770.  
  771.  
  772.  
  773.  
  774.  
  775.  
  776.  
  777.  
  778.  
  779.  
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786. Lougheed & Rekhter                                             [Page 14]
  787.  
  788. RFC 1105                          BGP                          June 1989
  789.  
  790.  
  791.    Event                Actions               Message Sent   Next State
  792.    --------------------------------------------------------------------
  793.    BGP_Idle (1)
  794.      1            Initialize resources           none             2
  795.    BGP_Active (2)
  796.      2           Initialize resources            OPEN             3
  797.      4                   none                    none             2
  798.     13           Release resources               none             1
  799.  
  800.    BGP_OpenSent(3)
  801.     3                    none                    none             1
  802.     5            Process OPEN is OK            OPEN CONFIRM       4
  803.                  Process OPEN Message failed   NOTIFICATION       1
  804.    11            Restart KeepAlive timer       KEEPALIVE          3
  805.    13            Release resources               none             1
  806.  
  807.    BGP_OpenConfirm (4)
  808.     6            Complete initialization         none             5
  809.     3                   none                     none             1
  810.    10            Close transport connection      none             1
  811.    11            Restart KeepAlive timer       KEEPALIVE          4
  812.    13            Release resources               none             1
  813.  
  814.    BGP_Established (5)
  815.     7            Process KEEPALIVE               none             5
  816.     8            Process UPDATE is OK          UPDATE             5
  817.                  Process UPDATE failed         NOTIFICATION       5
  818.     9            Process NOTIFICATION            none             5
  819.    10            Close transport connection      none             1
  820.    11            Restart KeepAlive timer       KEEPALIVE          5
  821.    12            Close transport connection    NOTIFICATION       1
  822.    13            Release resources               none             1
  823.    --------------------------------------------------------------------
  824.  
  825.    All other state-event combinations are considered fatal errors and
  826.    cause the termination of the BGP transport connection (if necessary)
  827.    and a transition to the BGP_Idle state.
  828.  
  829.  
  830.  
  831.  
  832.  
  833.  
  834.  
  835.  
  836.  
  837.  
  838.  
  839.  
  840.  
  841.  
  842. Lougheed & Rekhter                                             [Page 15]
  843.  
  844. RFC 1105                          BGP                          June 1989
  845.  
  846.  
  847.    The following is a condensed version of the above state transition
  848.    table.
  849.  
  850.    Events|BGP_Idle BGP_Active BGP_OpenSent BGP_OpenConfirm BGP_Estab
  851.          |  (1)   |    (2)   |     (3)    |      (4)      |      (5)
  852.          |-------------------------------------------------------------
  853.     1    |   2    |          |            |               |
  854.          |        |          |            |               |
  855.     2    |        |     3    |            |               |
  856.          |        |          |            |               |
  857.     3    |        |          |      1     |       1       |
  858.          |        |          |            |               |
  859.     4    |        |     2    |            |               |
  860.          |        |          |            |               |
  861.     5    |        |          |    4 or 1  |               |
  862.          |        |          |            |               |
  863.     6    |        |          |            |       5       |
  864.          |        |          |            |               |
  865.     7    |        |          |            |               |       5
  866.          |        |          |            |               |
  867.     8    |        |          |            |               |       5
  868.          |        |          |            |               |
  869.     9    |        |          |            |               |       5
  870.          |        |          |            |               |
  871.    10    |        |          |            |       1       |       1
  872.          |        |          |            |               |
  873.    11    |        |          |      3     |       4       |       5
  874.          |        |          |            |               |
  875.    12    |        |          |            |               |       1
  876.          |        |          |            |               |
  877.    13    |        |     1    |      1     |       1       |       1
  878.          |        |          |            |               |
  879.          --------------------------------------------------------------
  880.  
  881.  
  882.  
  883.  
  884.  
  885.  
  886.  
  887.  
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898. Lougheed & Rekhter                                             [Page 16]
  899.  
  900. RFC 1105                          BGP                          June 1989
  901.  
  902.  
  903. References
  904.  
  905.   [1]  Mills, D., "Exterior Gateway Protocol Formal Specification", RFC
  906.        904, BBN, April 1984.
  907.  
  908.   [2]  Rekhter, Y., "EGP and Policy Based Routing in the New NSFNET
  909.        Backbone", RFC 1092, T. J. Watson Research Center, February 1989.
  910.  
  911.   [3]  Braun, H-W., "The NSFNET Routing Architecture", RFC 1093,
  912.        MERIT/NSFNET Project, February 1989.
  913.  
  914.   [4]  Postel, J., "Transmission Control Protocol - DARPA Internet
  915.        Program Protocol Specification", RFC 793, DARPA, September 1981.
  916.  
  917.   [5]  Cheriton, D., "VMTP: Versatile Message Transaction Protocol", RFC
  918.        1045, Stanford University, February 1988.
  919.  
  920. Authors' Addresses
  921.  
  922.    Kirk Lougheed
  923.    cisco Systems, Inc.
  924.    1360 Willow Road, Suite 201
  925.    Menlo Park, CA 94025
  926.  
  927.    Phone: (415) 326-1941
  928.  
  929.    Email: LOUGHEED@MATHOM.CISCO.COM
  930.  
  931.  
  932.    Jacob Rekhter
  933.    T.J. Watson Research Center
  934.    IBM Corporation
  935.    P.O. Box 218
  936.    Yorktown Heights, NY 10598
  937.  
  938.    Phone: (914) 945-3896
  939.  
  940.    Email: YAKOV@IBM.COM
  941.  
  942.  
  943.  
  944.  
  945.  
  946.  
  947.  
  948.  
  949.  
  950.  
  951.  
  952.  
  953.  
  954. Lougheed & Rekhter                                             [Page 17]
  955.