home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc1863 < prev    next >
Text File  |  1995-10-20  |  37KB  |  900 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                          D. Haskin
  8. Request For Comments: 1863                                   Intel Corp.
  9. Category: Experimental                                      October 1995
  10.  
  11.  
  12.        A BGP/IDRP Route Server alternative to a full mesh routing
  13.  
  14. Status of this Memo
  15.  
  16.    This memo defines an Experimental Protocol for the Internet
  17.    community.  This memo does not specify an Internet standard of any
  18.    kind.  Discussion and suggestions for improvement are requested.
  19.    Distribution of this memo is unlimited.
  20.  
  21. Abstract
  22.  
  23.    This document describes the use and detailed design of Route Servers
  24.    for dissemination of routing information among BGP/IDRP speaking
  25.    routers.
  26.  
  27.    The intention of the proposed technique is to reduce overhead and
  28.    management complexity of maintaining numerous direct BGP/IDRP
  29.    sessions which otherwise might be required or desired among routers
  30.    within a single routing domain as well as among routers in different
  31.    domains that are connected to a common switched fabric (e.g. an ATM
  32.    cloud).
  33.  
  34. 1. Overview
  35.  
  36.    Current deployments of Exterior Routing protocols, such as the Border
  37.    Gateway Protocol [BGP4] and the adaptation of the ISO Inter-Domain
  38.    Routing Protocol [IDRP], require that all BGP/IDRP routers, which
  39.    participate in inter-domain routing (border routers) and belong to
  40.    the same routing domain, establish a full mesh connectivity with each
  41.    other for purpose of exchanging routing information acquired from
  42.    other routing domains. In large routing domains the number of intra-
  43.    domain connections that needs to be maintained by each border route
  44.    can be significant.
  45.  
  46.    In addition, it may be desired for a border router to establish
  47.    routing sessions with all border routers in other domains which are
  48.    reachable via a shared communication media. We refer to routers that
  49.    are directly reachable via a shared media as adjacent routers.  Such
  50.    direct peering allows a router to acquire "first hand" information
  51.    about destinations which are directly reachable through adjacent
  52.    routers and select the optimum direct paths to these destinations.
  53.    Establishment of BGP/IDRP sessions among all adjacent border routers
  54.    would result in a full mesh routing connectivity.  Unfortunately for
  55.  
  56.  
  57.  
  58. Haskin                        Experimental                      [Page 1]
  59.  
  60. RFC 1863                A BGP/IDRP Route Server             October 1995
  61.  
  62.  
  63.    a switched media as ATM, SMDS or Frame Relay network which may
  64.    inter-connect a large number of routers,  due to the number of
  65.    connections that would be needed to maintain a full mesh direct
  66.    peering between the routers,  makes this approach impractical.
  67.  
  68.    In order to alleviate the "full mesh" problem, this paper proposes to
  69.    use IDRP/BGP Route Servers which would relay external routes with all
  70.    of their attributes between client routers. The clients would
  71.    maintain IDRP/BGP sessions only with the assigned route servers
  72.    (sessions with more than one server would be needed if redundancy is
  73.    desired).  All routes that are received from a client router would be
  74.    propagated to other clients by the Route Server.  Since all external
  75.    routes and their attributes are relayed unmodified between the client
  76.    routers, the client routers would acquire the same routing
  77.    information as they would via direct peering.  We refer to such
  78.    arrangement as virtual peering.  Virtual peering allows client
  79.    routers independently apply selection criteria to the acquired
  80.    external routes according to their local policies as they would if a
  81.    direct peering were established.
  82.  
  83.    The routing approach described in this paper assumes that border
  84.    routers possess a mechanism to resolve the media access address of
  85.    the next hop router for any route acquired from a virtual peer.
  86.  
  87.    It is fair to note that the approach presented in this paper only
  88.    reduces the number of routing connection each border router needs to
  89.    maintain. It does not reduce the volume of routing information that
  90.    needs to maintained at each border router.
  91.  
  92.    Besides addressing the "full mesh" problems,  the proposal attempts
  93.    to achieve the following goals:
  94.  
  95.    - to minimize BGP/IDRP changes that need to be implemented in client
  96.      routers in order to inter-operate with route servers;
  97.  
  98.    - to provide for redundancy of distribution of routing information to
  99.      route server clients;
  100.  
  101.    - to minimize the amount of routing updates that have to be sent to
  102.      route server clients;
  103.  
  104.    - to provide load distribution between route servers;
  105.  
  106.    - to avoid an excessive complexity of the interactions between Route
  107.      Servers themselves.
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114. Haskin                        Experimental                      [Page 2]
  115.  
  116. RFC 1863                A BGP/IDRP Route Server             October 1995
  117.  
  118.  
  119. 2. Terms And Acronyms
  120.  
  121.    The following terms and acronyms are used in this paper:
  122.  
  123.   Routing Domain     -  a collection of routers with the same set of
  124.                         routing policies.  For IPv4 it can be identified
  125.                         with an Autonomous System Number, for IPv6
  126.                         it can be identified with a Routing Domain
  127.                         Identifier.
  128.  
  129.   Border Router (BR) -  a router that acquires external routes, i.e.
  130.                         routes to internet points outside its routing
  131.                         domain.
  132.  
  133.   Route Server (RS)  -  a process that collects routing information
  134.                         from border routers and distributes this
  135.                         information to 'client routers'.
  136.  
  137.   RS Client (RC)     -  a router than peers with an RS in order to
  138.                         acquire routing information.  A server's client
  139.                         can be a router or another route server.
  140.  
  141.   RS Cluster (RSC)   -  two or more of route servers that share the same
  142.                         subset of clients.  A RS Cluster provides
  143.                         redundancy of routing information to its
  144.                         clients,  i.e. routing information is provided
  145.                         to all RS Cluster clients as long as there is
  146.                         at least one functional route server in the RS
  147.                         Cluster.
  148.  
  149.   RCID             -    Cluster ID
  150.  
  151. 3. RS Model
  152.  
  153.    In the proposed scheme a Route Server (RS) does not apply any
  154.    selection criteria to the routes received from border routers for the
  155.    purpose of distributing these routes to its clients.  All routes
  156.    acquired from border routers or other Route Servers are relayed to
  157.    the client border routers.
  158.  
  159.    There can be two classes of Route Servers: Route Servers that relay
  160.    external routes between routers in a single routing domain and Route
  161.    Servers that relay external routes between border routers in
  162.    different routing domains.  The former are Intra-Domain Route Servers
  163.    and the latter are Inter-Domain Route Servers.
  164.  
  165.    In the RS model proposed in this document there is no routing
  166.    exchange between Intra-Domain Route Servers and Inter-Domain Route
  167.  
  168.  
  169.  
  170. Haskin                        Experimental                      [Page 3]
  171.  
  172. RFC 1863                A BGP/IDRP Route Server             October 1995
  173.  
  174.  
  175.    Servers.  Routes that cross a domain boundary must always pass
  176.    through a border router of such a domain which may apply
  177.    administrative filters to such routes.
  178.  
  179.    Operations of Intra-Domain Route Servers and Inter-Domain Route
  180.    Servers are identical.
  181.  
  182.    One or more Route Servers form an RS Cluster (RSC).  For redundancy's
  183.    sake two or more RSs can be configured to operate in an RS Cluster.
  184.    All route servers in an RSC share the same clients,  i.e. cluster
  185.    clients establish connections to all route servers in such an RSC for
  186.    the purpose of exchanging routing information. Each cluster is
  187.    assigned an unique RSC Identifier (RCID) represented by a 2-octet
  188.    unsigned integer.
  189.  
  190.    Clusters which provide virtual connectivity between their clients
  191.    would be normally exchanging routing information among themselves so
  192.    that all external routes are propagated to all participating clients.
  193.  
  194.    Though a Route Server Client (RC) can be associated with multiple
  195.    RSC, it seems that there is no real advantage of doing so except for
  196.    a short transition period to provide a graceful re-assignment from
  197.    one RSC to another or, if for some reason, there are multiple RS
  198.    groups that don't exchange routing information with each other.
  199.  
  200.    The inter-cluster route exchange can be accomplished by forming a
  201.    full mesh routing adjacency between clusters.  In this approach,
  202.    illustrated in the diagram below,  each RS in each RSC would maintain
  203.    a routing connection with every RS in other RS clusters.  Only routes
  204.    that are acquired from border routers are propagated to RSs in other
  205.    RS clusters.
  206.  
  207.          BR11   BR12   BR1n     BR21  BR22  BR2n
  208.            |     |  ... |        |     | ...  |
  209.           -----------------     ------------------
  210.           !  RS11  RS12   ! --- !  RS21    RS22  !
  211.           -----------------     ------------------
  212.                <RSC#1>  \           /    <RSC#2>
  213.                          \         /
  214.                        -----------------
  215.                        !  RS31  RS32   !   <RSC#3>
  216.                        -----------------
  217.                          |     | ... |
  218.                         BR31  BR32  BR3n
  219.  
  220.    Another way to propagate routing information between clusters would
  221.    be to form a cluster hierarchy in which an RS in one cluster
  222.    maintains sessions only with RSs in designated clusters.  In this
  223.  
  224.  
  225.  
  226. Haskin                        Experimental                      [Page 4]
  227.  
  228. RFC 1863                A BGP/IDRP Route Server             October 1995
  229.  
  230.  
  231.    approach an RS must advertise all acquired routes to an RS in another
  232.    cluster except the routes that are acquired from that cluster.
  233.    Nevertheless,  it allows for minimizing the number of routing
  234.    sessions which can be highly desirable in some network.  It is
  235.    important for the hierarchical scheme that the inter-cluster route
  236.    exchange links form a tree, i.e. there is only one route propagation
  237.    path between any two clusters, otherwise routing loops may result.
  238.    For detection and pruning of routing loops in a hierarchical cluster
  239.    topology, it is advisable to include the "RCID Path" attribute (see
  240.    4.3.4) in all routing updates sent between route servers. This
  241.    attribute lists IDs of all clusters in the route propagation path.
  242.    When a duplicate ID is detected in this attribute an offending route
  243.    needs to be discarded.
  244.  
  245.    The diagram below which illustrates the hierarchical approach is
  246.    created from the diagram above by removing the route exchange link
  247.    between clusters 2 and 3.
  248.  
  249.          BR11   BR12   BR1n     BR21  BR22  BR2n
  250.            |     |  ... |        |     | ...  |
  251.           -----------------     ------------------
  252.           !  RS11  RS12   ! --- !  RS21    RS22  !
  253.           -----------------     ------------------
  254.                <RSC#1>  \                <RSC#2>
  255.                          \
  256.                        -----------------
  257.                        !  RS31  RS32   !   <RSC#3>
  258.                        -----------------
  259.                          |     | ... |
  260.                         BR31  BR32  BR3n
  261.  
  262.    It seems that the only disadvantage of the hierarchical model, is the
  263.    management headache of avoiding routing loops and redundant
  264.    information flow by insuring that inter-cluster links always form a
  265.    tree.  But more study is needed to fully evaluate the comparative
  266.    merits of the full-mesh and hierarchical models.
  267.  
  268.    Since RSs in the same cluster maintain routing sessions with the same
  269.    set of clients, it may seem that there is no need to exchange routing
  270.    information between RSs in the same cluster. Nevertheless, such a
  271.    route exchange may help to maintain identical routing databases in
  272.    the servers during client acquisition periods and when a partial
  273.    failure may affect some routing sessions.
  274.  
  275.    Route servers in the same RS cluster exchange control messages in
  276.    attempt to subdivide the responsibilities of providing routing
  277.    information to their clients.  In order to simplify the RS design,
  278.    the RS messaging is implemented on top of exterior protocol which is
  279.  
  280.  
  281.  
  282. Haskin                        Experimental                      [Page 5]
  283.  
  284. RFC 1863                A BGP/IDRP Route Server             October 1995
  285.  
  286.  
  287.    used by route servers for the routing information exchange.
  288.  
  289. 4. Operation
  290.  
  291. 4.1 ADVERTISER Path Attribute
  292.  
  293.    Route servers act as concentrators for routes acquired by border
  294.    routers so that the border routers need to maintain routing
  295.    connections with only one or two designated route servers.  Route
  296.    Servers distribute routing information that is provided to them by
  297.    the border routers to all their client.
  298.  
  299.    If routing information were relayed to RS clients in UPDATE messages
  300.    with only those path attribute that are currently defined in the
  301.    BGP-4/IDRP specification, the RS clients would not be able to
  302.    associate external routes they receive with the border routers which
  303.    submitted that routes to route servers. Such an association is
  304.    necessary for making a correct route selection decision. Therefore,
  305.    the new path attribute, ADVERTISER, is defined.
  306.  
  307.    The ADVERTISER is an optional non-transitive attribute that defines
  308.    the identifying address of the border router which originally
  309.    submitted the route to a router server in order for it to be relayed
  310.    to other RS clients. Type Code of the ADVERTISER attribute is 255.
  311.    This attribute must be included in every UPDATE message that is
  312.    relayed by route servers and must be recognized by RS clients.
  313.  
  314. 4.2 Route Client Operation
  315.  
  316.    An RS client establishes an BGP/IDRP connection to every route server
  317.    in the RS cluster to which the route client is assigned.
  318.  
  319.    RS clients must be able to recognize the ADVERTISER path attribute
  320.    that is included in all UPDATE messages received from route servers.
  321.    Routes received in UPDATE messages from route servers are processed
  322.    as if they were received directly from the border routers specified
  323.    in the ADVERTISER attributes of the respective updates.
  324.  
  325.    If an RS client receives a route from a Intra-Domain Route Server, is
  326.    assumed that the border router identified in the ADVERTISER attribute
  327.    is located in the receiving client's own routing domain.
  328.  
  329.    If an RS client receives a route from a Inter-Domain Route Server,
  330.    the locality of the border router identified in the ADVERTISER
  331.    attribute can be determined from the BGP's AS_PATH attribute or
  332.    IDRP's RD_PATH attribute respectively.
  333.  
  334.  
  335.  
  336.  
  337.  
  338. Haskin                        Experimental                      [Page 6]
  339.  
  340. RFC 1863                A BGP/IDRP Route Server             October 1995
  341.  
  342.  
  343.    If no ADVERTISER attribute was included in an UPDATE message from a
  344.    route server it is assumed that the route server itself is the
  345.    advertiser of the corresponding route.
  346.  
  347.    If the NEXT_HOP path attribute of an UPDATE message lists an address
  348.    of the receiving router itself, the route that is carried in such an
  349.    update message must be declared unreachable.
  350.  
  351.    In addition, it is highly desirable, albeit not required,  to
  352.    slightly modify the "standard" BGP/IDRP operation when acquiring
  353.    routes from RSs:
  354.  
  355.     when a route is received from an RS and a route with the completely
  356.     identical attributes has been previously acquired from another RS
  357.     in the same cluster,  the previously acquired route should be
  358.     replaced with the newly acquired route.  Such a route replacement
  359.     should not trigger any route advertisement action on behalf of the
  360.     route.
  361.  
  362.    RSs are designed to operate in such a way that eliminates the need to
  363.    keep multiple copies of the same route by RS clients and minimizes
  364.    the possibility of a route flap when the BGP/IDRP connection to one
  365.    of the redundant route servers is lost.
  366.  
  367.    It is attempted to subdivide the route dissemination load between
  368.    route servers such that only one RS provides routing updates to a
  369.    given client.  But since, for avoiding an excessive complexity, the
  370.    reconciliation algorithm does not eliminate completely the
  371.    possibility of races, it is still possible that a client may receive
  372.    updates from more than one route server.  Therefore, the client's
  373.    ability to discard duplicate routes may reduce the need for a bigger
  374.    routing database.
  375.  
  376. 4.3 Route Server Operation
  377.  
  378.    A Route Server maintains BGP-4/IDRP sessions with its clients
  379.    according to the respective BGP-4/IDRP specification with exception
  380.    of protocol modifications outlined in this document.
  381.  
  382.    UPDATE messages sent by route servers have the same format and
  383.    semantics as it respective BGP-4/IDRP counterparts but also carry the
  384.    ADVERTISER path attribute which specifies the BGP Identifier of the
  385.    border router that submitted the route advertised in the UPDATE
  386.    message. In addition, if the hierarchical model is deployed to
  387.    interconnect Route Server clusters, it is advisable to include the
  388.    "RCID Path" attribute in all routing updates sent between route
  389.    servers as described in 4.3.4.
  390.  
  391.  
  392.  
  393.  
  394. Haskin                        Experimental                      [Page 7]
  395.  
  396. RFC 1863                A BGP/IDRP Route Server             October 1995
  397.  
  398.  
  399.    When route servers exchange OPEN messages they include the Route
  400.    Server protocol version (current version is 1) as well as Cluster IDs
  401.    of their respective clusters in an Optional Parameter of the OPEN
  402.    message. The value of Parameter Type for this parameter is 255. The
  403.    length of the parameter data is 3 octets. The format of parameter
  404.    data is shown below:
  405.  
  406.     +-----------------------+------------------------------------+
  407.     | Version = 1 (1 octet) |      Cluster ID (2 octets)         |
  408.     +-----------------------+------------------------------------+
  409.  
  410.    Also, route servers that belong to the same cluster send to each
  411.    other LIST messages with lists of clients to which they're providing
  412.    routing information.  In the LIST message an RS specifies the Router
  413.    Identifier of each client to which that RS is providing routing
  414.    updates. Since LIST messages are relatively small there is no need to
  415.    add a processing complexity of generating incremental updates when a
  416.    list changes; instead the complete list is sent when RSs need to be
  417.    informed of the changes.  The format of the LIST message is presented
  418.    in 4.3.1.
  419.  
  420. 4.3.1 LIST Message Format
  421.  
  422.    The LIST message contains the fixed BGP/IDRP header that is followed
  423.    with the fields shown below.  The type code in the fixed header of
  424.    the LIST message is 255.
  425.  
  426.      +----------+----------+----------+----------+
  427.      |        Client Identifying Address         | Repeated for each
  428.      +-------------------------------------------+ informed client
  429.    The number of Client Identifying Address" fields is not encoded
  430.    explicitly,  but can be calculated as:
  431.  
  432.      (<LIST message Length> - <Header Length>) / <Address Length>,
  433.  
  434.    where <LIST message Length> is the value encoded in the fixed
  435.    BGP/IDRP header, <Header Length> is the length of that header, and
  436.    <Address Length> is 4 for IPv4 and 16 for IPv6.
  437.  
  438. 4.3.2 External Route Acquisition And Advertisement
  439.  
  440.    A route server acquires external routes from RS clients that are also
  441.    border routers.  A RS also may acquire external routes from other
  442.    RSs.  Route servers relay all acquired routes unaltered to their
  443.    clients.  No route selection is performed for purpose of route re-
  444.    advertisement to RS clients.
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Haskin                        Experimental                      [Page 8]
  451.  
  452. RFC 1863                A BGP/IDRP Route Server             October 1995
  453.  
  454.  
  455.    While route servers receive and store routing data from all their
  456.    client,  Routing Servers in the same cluster coordinate their route
  457.    advertisement in the attempt to ensure that only one RS provides
  458.    routing updates to a given client.  If an RS fails,  other Route
  459.    Servers in the cluster take over the responsibility of providing
  460.    routing updates to the clients that were previously served by the
  461.    failed RS.  A route flap that can result from such switch-over can be
  462.    eliminated by the configuring client's "Hold Time" of their BGP-
  463.    4/IDRP sessions with the route servers to be larger than the switch-
  464.    over time.  The switch-over time is determined by the Hold Time of
  465.    BGP-4/IDRP sessions between the route servers in the cluster and the
  466.    period that is needed for that route servers to reconcile their route
  467.    advertisement responsibilities.  The reconciliation protocol is
  468.    described in 4.3.3.
  469.  
  470.    The BGP-4/IDRP operations of route servers differs from the
  471.    "standard" operation in the following ways:
  472.  
  473.    -    when receiving routes from another RS, the RS Client mode of
  474.         operation is assumed, i.e., when a route with completely
  475.         identical attributes has been previously acquired from an RS
  476.         belonging to the same cluster as the RS that advertises the new
  477.         route, the previously acquired route should be discarded and
  478.         the newly acquired route should be accepted.  Such a route
  479.         replacement should not trigger any route advertisement action
  480.         on behalf of the route.
  481.  
  482.    -    all acquired routes are advertised to a client router except
  483.         routes which were acquired from that client (no route echoing);
  484.  
  485.    -    if the hierarchical model of inter-cluster route exchange is
  486.         used,  all acquired routes are advertised to an RS in another
  487.         RSC except routes that are acquired from that RSC.  In the
  488.         full-mesh model, only routes which are acquired from border
  489.         routers are advertised to route servers in other clusters;
  490.  
  491.    -    if route servers in the same RS cluster are configured to
  492.         exchange routing information,  only external routes that are
  493.         acquired from border routers are advertised to route servers in
  494.         the local cluster;
  495.  
  496.    -    the ADVERTISER path attribute is included in every UPDATE
  497.         messages that is generated by RS.  This attribute must
  498.         specify the identifying address of the border router from which
  499.         information provided in UPDATE has been acquired.  All other
  500.         routing attributes should be relayed to RS's peers unaltered.
  501.  
  502.  
  503.  
  504.  
  505.  
  506. Haskin                        Experimental                      [Page 9]
  507.  
  508. RFC 1863                A BGP/IDRP Route Server             October 1995
  509.  
  510.  
  511.    -    when a route advertised by to an RS by a client becomes
  512.         unreachable such a route needs to be declared unreachable to
  513.         all other clients.  In order to withdraw a route,  the route
  514.         server sends an UPDATE for that route to each client (except
  515.         the client that this route was originally acquired) with the
  516.         NEXT_HOP path attribute set to the address of the client to
  517.         which this UPDATE is sent to.  The the ADVERTISER path attribute
  518.         with the identifying address of the border router that
  519.         originally advertised the withdrawn route must be also included
  520.         in such an update message.
  521.  
  522.    -    if the hierarchical model is deployed to interconnect Route
  523.         Server clusters,  it is advisable to include the RCID_PATH
  524.         attribute in all routing updates sent between route servers as
  525.         described in 4.3.4.  The RCID_PATH attribute is never included
  526.         in UPDATE messages sent to border routers.
  527.  
  528. 4.3.3 Intra-Cluster Coordination
  529.  
  530.    In order to coordinate route advertisement activities,  route servers
  531.    which are members of the same RS cluster establish and maintain
  532.    BGP/IDRP connections between themselves forming a full-mesh
  533.    connectivity.  Normally, there is no need for more than two-three
  534.    route servers in one cluster.
  535.  
  536.    Route servers belonging to the same cluster send to each other LIST
  537.    messages with lists of clients to which they're providing routing
  538.    information;  let's call such clients "informed clients".
  539.  
  540.    Each RS maintains a separate "informed client" list for each RS in
  541.    the local cluster including itself.  All such lists are linked in an
  542.    ascending order that is determined by the number of clients in each
  543.    list; the order among the lists with the same number of clients is
  544.    determined by comparing the identifying addresses of the
  545.    corresponding RSs -- an RS in such a "same number of clients" subset
  546.    is positioned after all RSs with the lower address.
  547.  
  548.    An RS can be in one of two RS coordination states: 'Initiation' and
  549.    'Active'.
  550.  
  551. 4.3.3.1 Initiation State
  552.  
  553.    This is the initial state of route server that is entered upon RS
  554.    startup.  When the Initiation state is entered the 'InitiationTimer'
  555.    is started.  The Initiation state transits to the Active state upon
  556.    expiration of the 'InitiationTimer' or as soon as all configured
  557.    BGP/IDRP connections to other route servers in the local RS Cluster
  558.    are established and LIST messages from that route servers are
  559.  
  560.  
  561.  
  562. Haskin                        Experimental                     [Page 10]
  563.  
  564. RFC 1863                A BGP/IDRP Route Server             October 1995
  565.  
  566.  
  567.    received.
  568.  
  569.    In the Initiation state an RS:
  570.  
  571.     o   tries to establish connections with other RSs in the local and
  572.         remote clusters.
  573.  
  574.     o   accepts BGP/IDRP connections from client routers.
  575.  
  576.     o   receives and process BGP/IDRP updates but doesn't send any
  577.         routing updates.
  578.  
  579.     o   stores "informed client" lists received from other RSs in the
  580.         local cluster - a newly received list replaces the existing list
  581.         for the same RS. If a LIST message is received from the route
  582.         server in another RS cluster, it should be silently ignored.
  583.  
  584.     o   initializes an empty "informed client" list for its own clients.
  585.     o   as soon as a BGP/IDRP connection to an RS in the same RS Cluster
  586.         is established, transmits an empty LIST message to such an RS.
  587.  
  588. 4.3.3.2 Active State
  589.  
  590. This state is entered upon expiration of the 'InitiationTimer' or as
  591. soon as all configured BGP/IDRP connections to other route servers in
  592. the local RS Cluster are established and LIST messages from that route
  593. servers are received.
  594.  
  595. In the Active state an RS:
  596.  
  597.     o   continues attempts to establish connections with other route
  598.         servers in the local and remote clusters;
  599.  
  600.     o   accepts new BGP/IDRP connections;
  601.  
  602.     o   transmits a LIST message to an RS in the local cluster as soon
  603.         as an BGP/IDRP session with the RS is established and then
  604.         whenever the local "informed client" list changes;
  605.  
  606.     o   receives and process BGP/IDRP updates;
  607.  
  608.     o   receives and processes "informed client" lists as described
  609.         below:
  610.  
  611.         a) If a LIST message is received from the route server in
  612.            another RS cluster, it should be silently ignored.
  613.  
  614.  
  615.  
  616.  
  617.  
  618. Haskin                        Experimental                     [Page 11]
  619.  
  620. RFC 1863                A BGP/IDRP Route Server             October 1995
  621.  
  622.  
  623.         b) If a LIST message is received from a route server that
  624.            belongs to the same RS Cluster,  the differences between
  625.            the old and the new list are determined and the old "informed
  626.            client" list for that RS is replaced by the list from the new
  627.            message.  For each client that was in the old list but not in
  628.            the new list it is checked whether the server has
  629.            an established BGP/IDRP connection to that client and
  630.            the client is not in any of the other "informed client"
  631.            lists.  If both conditions are met,  the processing described
  632.            for a new client takes place (see 4.3.3.3).
  633.  
  634.     o   for each new BGP/IDRP client (including connections established
  635.         in Initiation state),  decides if that client should become an
  636.         "informed client", i.e. whether routing updates are to be sent
  637.         to the client or that client has been already taken care by
  638.         another RS in the local cluster.  The decision process is
  639.         described in the next section.
  640.  
  641. 4.3.3.3 New Client Processing
  642.  
  643.    Whenever an RS acquires a new BGP/IDRP peer it scans through all
  644.    "informed client" lists in order to determine if this peer has
  645.    already been receiving routing updates from another RS in the local
  646.    RS cluster.  If the identifying address of the peer is found in one
  647.    of the list,  no routing updates are sent to that peer.
  648.  
  649.    If the peer's Router Id is not found,  the route server initiates a
  650.    'DelayTimer' timer for that peer and the decision is postponed until
  651.    that timer expires.  The delay value is calculated as followed:
  652.  
  653.       the RS determines the relative position of its own "informed
  654.       client" list in the linked list of all "informed client" lists.
  655.       If such position is expressed with a number, say N,  in the 1 to
  656.       "maximum number of lists" range, then the delay value is set to
  657.       (N-1)*<DelayGranularity>.
  658.  
  659.    Upon expiration of the DelayTimer,  the "informed client" lists are
  660.    scanned once again to see if the corresponding peer has already been
  661.    receiving routing updates from another RS in the local RS cluster.
  662.    If the Router Id of the peer is found in one of the lists as a result
  663.    of receiving a new LIST message, no routing updates are sent to that
  664.    peer.  Otherwise,  the peer's Router ID is entered in the "informed
  665.    client" list that belongs to the RS,  the transmission of the updated
  666.    LIST message is immediately scheduled, and routing updates are sent
  667.    to the client.
  668.  
  669.    The rational for the delay is to minimize races in the decision as
  670.    which RS among route servers in the same RSC is going to provide
  671.  
  672.  
  673.  
  674. Haskin                        Experimental                     [Page 12]
  675.  
  676. RFC 1863                A BGP/IDRP Route Server             October 1995
  677.  
  678.  
  679.    routing information to a given client.  The RS with least number of
  680.    "informed clients" would have a shortest delay and is the most
  681.    probable to win the race.  This helps to equalize the number of
  682.    "informed clients" between RSc in a cluster.
  683.  
  684.    After an BGP/IDRP peer is placed in the "informed client" list, it is
  685.    only removed from the list when the BGP/IDRP connection to this peer
  686.    is lost.  While an RS client is in the list it is accurately updated
  687.    with all routing changes.
  688.  
  689. 4.3.3.5 Inter-RS Connection Failure
  690.  
  691.    If a route server loses a routing session with a route server in the
  692.    same cluster,  it must consider taking the responsibilities of route
  693.    advertisement to the clients that are in the "informed client" list
  694.    of the remote route server of the failed session.
  695.  
  696.    For each such client it is checked whether the server has an
  697.    established BGP/IDRP connection to that client and the client is not
  698.    in any of the "informed client" lists of active RS.  If both
  699.    conditions are true,  the processing described for a new client takes
  700.    place (see 4.3.3.3).
  701.  
  702.    After advertisement responsibilities are reconciled the "informed
  703.    client" list associated with the failed session should be discarded.
  704.  
  705. 4.3.4 RCID_PATH Attribute
  706.  
  707.    The RCID_PATH is an optional non-transitive attribute that is
  708.    composed of a sequence of RS Cluster Identifiers (RCID) that
  709.    identifies the RS Cluster through which routing information carried
  710.    in the UPDATE message has passed.  Type Code of the RCID_PATH
  711.    attribute is 254.  The attribute value field contains one or more RS
  712.    Cluster Identifiers, each encoded as a 2-octets long field.
  713.  
  714.    When a route server propagates a route which has been learned from
  715.    nother Route Server's UPDATE message, the following is performed with
  716.    respect to the the RCID_PATH attribute:
  717.  
  718.   -     if the destination of the route is not a route server, the
  719.         RCID_PATH Attribute is excluded from the UPDATE message sent to
  720.         that client.
  721.  
  722.   -     if the destination of the route is another route server that is
  723.         located in the advertising server's own RS cluster,  the
  724.         RCID_PATH attribute is sent unmodified.
  725.  
  726.  
  727.  
  728.  
  729.  
  730. Haskin                        Experimental                     [Page 13]
  731.  
  732. RFC 1863                A BGP/IDRP Route Server             October 1995
  733.  
  734.  
  735.   -     if the destination of the route is a route server in a different
  736.         RS cluster,  the advertising route server shall verify that the
  737.         RCID of the destination speaker's cluster is not present in
  738.         the RCID_PATH attribute associated with route.  If it does,
  739.         the route shall not be advertised and an event indicating
  740.         that a route loop was detected should be logged, otherwise
  741.         the advertising router shall prepend its own RCID to the RCID
  742.         sequence in the RCID_PATH attribute (put it in the leftmost
  743.         position).
  744.  
  745.    When a route server propagates a route which has been learned from a
  746.    border router to another route server then:
  747.  
  748.   -     if the destination of the route is a route server that is
  749.         located in the advertising router's own RS cluster,  an empty
  750.         RCID_PATH attribute shall be included in the UPDATE message
  751.         (an empty RCID_PATH attribute is one whose length field contains
  752.         the value zero).
  753.  
  754.   -     if the destination of the route is a route server in a different
  755.         RS cluster,  the advertising route server shall include its own
  756.         RCID in the RCID_PATH attribute.  In this case, the RCID of
  757.         advertising route server will be the only entry in the RCID_PATH
  758.         attribute.
  759.  
  760. 4.3.5 NOTIFICATION Error Codes
  761.  
  762.    In addition to the error codes defined in the BGP-4/IDRP
  763.    specification, the following error can be indicated in a NOTIFICATION
  764.    message that is sent by a route server:
  765.  
  766.      255  LIST Message Error
  767.  
  768.    The following error subcodes can be associated with the LIST Message
  769.    Error:
  770.  
  771.      1  - Bad Address.  This subcode indicates that a Client Identifying
  772.           Address in the received LIST message does not represent
  773.           a valid network layer address of a router interface.
  774.  
  775.    The following additional UPDATE error subcodes are also defined:
  776.  
  777.      255 - Invalid ADVERTISER Attribute.  This subcode indicates that
  778.            a value of the ADVERTISER Attribute does not represent
  779.            a valid network layer address of a router interface.
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786. Haskin                        Experimental                     [Page 14]
  787.  
  788. RFC 1863                A BGP/IDRP Route Server             October 1995
  789.  
  790.  
  791. 4.3.7 Timers
  792.  
  793.    The InitiationTimer value of 5 minutes is suggested.
  794.  
  795.    In order to avoid route flaps during an RS switch-over, a value of
  796.    DelayGranularity should be such so the maximum possible value of the
  797.    DelayTimer (see 4.3.3.3) combined with the Hold Time of inter-RS
  798.    connections would be shorter than two-third of the smallest Hold Time
  799.    interval of all BGP/IDRP connections between the route servers and
  800.    their clients (including RSs in other clusters).  So in a cluster
  801.    with three RSs and the respective Hold Times of 30 and 90 seconds the
  802.    DelayGranularity of 15 seconds would be a recommended value.
  803.  
  804.    For the same reason it is recommended that the Hold Time of BGP/IDRP
  805.    connections between route servers in the same cluster is set to one-
  806.    third of the smallest Hold Time of all BGP/IDRP connections between
  807.    the route servers and their clients (including RSs in other
  808.    clusters).  So, if the smallest Hold Time of BGP/IDRP sessions with
  809.    clients is 90 seconds,  the recommended  value of the Hold Time of
  810.    BGP/IDRP connections between route servers in that cluster would be
  811.    30 seconds.
  812.  
  813. 5. Route Server Discovery
  814.  
  815.    This document does not propose any mechanism for the dynamic RS
  816.    discovery by RS clients or/and by other route servers.  It is assumed
  817.    that at minimum a manual configuration will be provided in
  818.    participating routers to achieve the needed connectivity.
  819.  
  820. 7. Security Considerations
  821.  
  822.    Security issues are not discussed in this document.
  823.  
  824. 8. Acknowledgment
  825.  
  826.    Some design concepts presented in this paper benefited from
  827.    discussions with Tony Li (cisco Systems).
  828.  
  829.    Author likes to thank John Krawczyk (Bay Networks) and Susan Harris
  830.    (Merit) for their review and valuable comments.
  831.  
  832.    Also, author would like to thank Yakov Rekhter (IBM) for the review
  833.    of the earlier version of this document and constructive comments.
  834.  
  835.    Special thanks to Ray Chang (Bay Networks) whose experience in
  836.    implementing the concepts presented in this document helped to refine
  837.    the route server design.
  838.  
  839.  
  840.  
  841.  
  842. Haskin                        Experimental                     [Page 15]
  843.  
  844. RFC 1863                A BGP/IDRP Route Server             October 1995
  845.  
  846.  
  847. 9. References
  848.  
  849.    [BGP4] Rekhter, Y., and T. Li, "A Border Gateway Protocol 4
  850.           (BGP-4)", RFC 1771, T.J. Watson Research Center, IBM Corp.,
  851.           cisco Systems, March 1995.
  852.  
  853.    [IDRP] Rekhter, Y., and P. Traina, "IDRP for IPv6", Work In Progress.
  854.  
  855. 10. Author's Address
  856.  
  857.    Dimitry Haskin
  858.    Bay Networks, Inc.
  859.    2 Federal Street
  860.    Billerica, MA 01821
  861.  
  862.    EMail: dhaskin@baynetworks.com
  863.  
  864.  
  865.  
  866.  
  867.  
  868.  
  869.  
  870.  
  871.  
  872.  
  873.  
  874.  
  875.  
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882.  
  883.  
  884.  
  885.  
  886.  
  887.  
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898. Haskin                        Experimental                     [Page 16]
  899.  
  900.