draft-ietf-idr-bgp4-22.txt

BCAST Implementation for NS2

   IGP
      Interior Gateway Protocol - a routing protocol used to exchange
      routing information among routers within a single Autonomous Sys-
      tem.

   Loc-RIB
      The Loc-RIB contains the routes that have been selected by the
      local BGP speaker's Decision Process.

   NLRI
      Network Layer Reachability Information.

   Route
      A unit of information that pairs a set of destinations with the



Expiration Date April 2004                                      [Page 6]





RFC DRAFT                                                   October 2003


      attributes of a path to those destinations. The set of destina-
      tions are systems whose IP addresses are contained in one IP
      address prefix carried in the Network Layer Reachability Informa-
      tion (NLRI) field of an UPDATE message. The path is the informa-
      tion reported in the path attributes field of the same UPDATE mes-
      sage.

   RIB
      Routing Information Base.

   Unfeasible route
      A previously advertised feasible route that is no longer available
      for use.


2. Acknowledgments

   This document was originally published as RFC 1267 in October 1991,
   jointly authored by Kirk Lougheed and Yakov Rekhter.

   We would like to express our thanks to Guy Almes, Len Bosack, and
   Jeffrey C. Honig for their contributions to the earlier version
   (BGP-1) of this document.

   We would like to specially acknowledge numerous contributions by Den-
   nis Ferguson to the earlier version of this document.

   We like to explicitly thank Bob Braden for the review of the earlier
   version (BGP-2) of this document as well as his constructive and
   valuable comments.

   We would also like to thank Bob Hinden, Director for Routing of the
   Internet Engineering Steering Group, and the team of reviewers he
   assembled to review the earlier version (BGP-2) of this document.
   This team, consisting of Deborah Estrin, Milo Medin, John Moy, Radia
   Perlman, Martha Steenstrup, Mike St. Johns, and Paul Tsuchiya, acted
   with a strong combination of toughness, professionalism, and cour-
   tesy.

   Certain sections of the document borrowed heavily from IDRP
   [IS10747], which is the OSI counterpart of BGP. For this credit
   should be given to the ANSI X3S3.3 group chaired by Lyman Chapin and
   to Charles Kunzinger who was the IDRP editor within that group.

   We would also like to thank Benjamin Abarbanel, Enke Chen, Edward
   Crabbe, Mike Craren, Vincent Gillet, Eric Gray, Jeffrey Haas, Dimitry
   Haskin, John Krawczyk, David LeRoy, Dan Massey, Jonathan Natale, Dan
   Pei, Mathew Richardson, John Scudder, John Stewart III, Dave Thaler,



Expiration Date April 2004                                      [Page 7]





RFC DRAFT                                                   October 2003


   Paul Traina, Russ White, Curtis Villamizar, and Alex Zinin for their
   comments.

   We would like to specially acknowledge Andrew Lange for his help in
   preparing the final version of this document.

   Finally, we would like to thank all the members of the IDR Working
   Group for their ideas and support they have given to this document.


Specification of Requirements


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



3. Summary of Operation

   The Border Gateway Protocol (BGP) is an inter-Autonomous System rout-
   ing protocol. It is built on experience gained with EGP as defined in
   [RFC904] and EGP usage in the NSFNET Backbone as described in
   [RFC1092] and [RFC1093].

   The primary function of a BGP speaking system is to exchange network
   reachability information with other BGP systems. This network reacha-
   bility information includes information on the list of Autonomous
   Systems (ASs) that reachability information traverses.  This informa-
   tion is sufficient to construct a graph of AS connectivity from which
   routing loops may be pruned and some policy decisions at the AS level
   may be enforced.

   In the context of this document we assume that a BGP speaker adver-
   tises to its peers only those routes that it itself uses (in this
   context a BGP speaker is said to "use" a BGP route if it is the most
   preferred BGP route and is used in forwarding). All other cases are
   outside the scope of this document.

   In the context of this document the term "IP address" refers to an IP
   Version 4 address [RFC791].

   Routing information exchanged via BGP supports only the destination-
   based forwarding paradigm, which assumes that a router forwards a
   packet based solely on the destination address carried in the IP
   header of the packet. This, in turn, reflects the set of policy deci-
   sions that can (and can not) be enforced using BGP. Note that some



Expiration Date April 2004                                      [Page 8]





RFC DRAFT                                                   October 2003


   policies can not be supported by the destination-based forwarding
   paradigm, and thus require techniques such as source routing (aka
   explicit routing) to be enforced. Such policies can not be enforced
   using BGP either. For example, BGP does not enable one AS to send
   traffic to a neighboring AS for forwarding to some destination
   (reachable through but) beyond that neighboring AS intending that the
   traffic take a different route to that taken by the traffic originat-
   ing in the neighboring AS (for that same destination).  On the other
   hand, BGP can support any policy conforming to the destination-based
   forwarding paradigm.

   BGP-4 provides a new set of mechanisms for supporting Classless
   Inter-Domain Routing (CIDR) [RFC1518, RFC1519]. These mechanisms
   include support for advertising a set of destinations as an IP prefix
   and eliminating the concept of network "class" within BGP.  BGP-4
   also introduces mechanisms which allow aggregation of routes, includ-
   ing aggregation of AS paths.

   This document uses the term `Autonomous System' (AS) throughout.  The
   classic definition of an Autonomous System is a set of routers under
   a single technical administration, using an interior gateway protocol
   (IGP) and common metrics to determine how to route packets within the
   AS, and using an inter-AS routing protocol to determine how to route
   packets to other ASs. Since this classic definition was developed, it
   has become common for a single AS to use several IGPs and sometimes
   several sets of metrics within an AS. The use of the term Autonomous
   System here stresses the fact that, even when multiple IGPs and met-
   rics are used, the administration of an AS appears to other ASs to
   have a single coherent interior routing plan and presents a consis-
   tent picture of what destinations are reachable through it.

   BGP uses TCP [RFC793] as its transport protocol. This eliminates the
   need to implement explicit update fragmentation, retransmission,
   acknowledgment, and sequencing. BGP listens on TCP port 179.  The
   error notification mechanism used in BGP assumes that TCP supports a
   "graceful" close, i.e., that all outstanding data will be delivered
   before the connection is closed.

   Two systems form a TCP connection between one another. They exchange
   messages to open and confirm the connection parameters.

   The initial data flow is the portion of the BGP routing table that is
   allowed by the export policy, called the Adj-Ribs-Out (see 3.2).
   Incremental updates are sent as the routing tables change. BGP does
   not require periodic refresh of the routing table. To allow local
   policy changes to have the correct effect without resetting  any BGP
   connections, a BGP speaker SHOULD either (a) retain the current ver-
   sion of the routes advertised to it by all of its peers for the



Expiration Date April 2004                                      [Page 9]





RFC DRAFT                                                   October 2003


   duration of the connection, or (b) make use of the Route Refresh
   extension [RFC2918].

   KEEPALIVE messages may be sent periodically to ensure the liveness of
   the connection. NOTIFICATION messages are sent in response to errors
   or special conditions. If a connection encounters an error condition,
   a NOTIFICATION message is sent and the connection is closed.

   A peer in a different AS is referred to as an external peer, while a
   peer in the same AS is referred to as an internal peer. Internal BGP
   and external BGP are commonly abbreviated IBGP and EBGP.

   If a particular AS has multiple BGP speakers and is providing transit
   service for other ASs, then care must be taken to ensure a consistent
   view of routing within the AS. A consistent view of the interior
   routes of the AS is provided by the IGP used within the AS. For the
   purpose of this document, it is assumed that a consistent view of the
   routes exterior to the AS is provided by having all BGP speakers
   within the AS maintain IBGP with each other.

   This document specifies the base behavior of the BGP protocol. This
   behavior can and is modified by extension specifications.  When the
   protocol is extended the new behavior is fully documented in the
   extension specifications.


3.1 Routes: Advertisement and Storage

   For the purpose of this protocol, a route is defined as a unit of
   information that pairs a set of destinations with the attributes of a
   path to those destinations. The set of destinations are systems whose
   IP addresses are contained in one IP address prefix carried in the
   Network Layer Reachability Information (NLRI) field of an UPDATE mes-
   sage, and the path is the information reported in the path attributes
   field of the same UPDATE message.

   Routes are advertised between BGP speakers in UPDATE messages.  Mul-
   tiple routes that have the same path attributes can be advertised in
   a single UPDATE message by including multiple prefixes in the NLRI
   field of the UPDATE message.

   Routes are stored in the Routing Information Bases (RIBs): namely,
   the Adj-RIBs-In, the Loc-RIB, and the Adj-RIBs-Out, as described in
   Section 3.2.

   If a BGP speaker chooses to advertise a previously received route, it
   MAY add to or modify the path attributes of the route before adver-
   tising it to a peer.



Expiration Date April 2004                                     [Page 10]





RFC DRAFT                                                   October 2003


   BGP provides mechanisms by which a BGP speaker can inform its peer
   that a previously advertised route is no longer available for use.
   There are three methods by which a given BGP speaker can indicate
   that a route has been withdrawn from service:

      a) the IP prefix that expresses the destination for a previously
      advertised route can be advertised in the WITHDRAWN ROUTES field
      in the UPDATE message, thus marking the associated route as being
      no longer available for use

      b) a replacement route with the same NLRI can be advertised, or

      c) the BGP speaker - BGP speaker connection can be closed, which
      implicitly removes from service all routes which the pair of
      speakers had advertised to each other.

   Changing attribute(s) of a route is accomplished by advertising a
   replacement route. The replacement route carries new (changed)
   attributes and has the same address prefix as the original route.


3.2 Routing Information Base

   The Routing Information Base (RIB) within a BGP speaker consists of
   three distinct parts:

      a) Adj-RIBs-In: The Adj-RIBs-In store routing information that has
      been learned from inbound UPDATE messages received from other BGP
      speakers. Their contents represent routes that are available as an
      input to the Decision Process.

      b) Loc-RIB: The Loc-RIB contains the local routing information
      that the BGP speaker has selected by applying its local policies
      to the routing information contained in its Adj-RIBs-In. These are
      the routes that will be used by the local BGP speaker. The next
      hop for each of these routes MUST be resolvable via the local BGP
      speaker's Routing Table.

      c) Adj-RIBs-Out: The Adj-RIBs-Out store the information that the
      local BGP speaker has selected for advertisement to its peers. The
      routing information stored in the Adj-RIBs-Out will be carried in
      the local BGP speaker's UPDATE messages and advertised to its
      peers.

   In summary, the Adj-RIBs-In contain unprocessed routing information
   that has been advertised to the local BGP speaker by its peers; the
   Loc-RIB contains the routes that have been selected by the local BGP
   speaker's Decision Process; and the Adj-RIBs-Out organize the routes



Expiration Date April 2004                                     [Page 11]





RFC DRAFT                                                   October 2003


   for advertisement to specific peers by means of the local speaker's
   UPDATE messages.

   Although the conceptual model distinguishes between Adj-RIBs-In, Loc-
   RIB, and Adj-RIBs-Out, this neither implies nor requires that an
   implementation must maintain three separate copies of the routing
   information. The choice of implementation (for example, 3 copies of
   the information vs 1 copy with pointers) is not constrained by the
   protocol.

   Routing information that the BGP speaker uses to forward packets (or
   to construct the forwarding table that is used for packet forwarding)