Internet Draft                                         Ramesh Govindan
Expires  April 28, 1997                                        USC/ISI
draft-ietf-idr-rdc-config-01.txt                      October 28, 1996

                   Configuring IDRP Confederations

Status of this Memo

This document is an Internet Draft, and can be found as
draft-ietf-idr-rdc-config-00.txt in any standard internet drafts
repository.  Internet Drafts are working documents of the Internet
Engineering Task Force (IETF), its Areas, and its Working Groups.
Note that other groups may also distribute working documents as
Internet Drafts.

Internet Drafts are draft documents valid for a maximum of six months.
Internet Drafts may be updated, replaced, or obsoleted by other
documents at any time.  It is not appropriate to use Internet Drafts
as reference material, or to cite them other than as a ``working
draft'' or ``work in progress.''

Please check the I-D abstract listing contained in each Internet Draft
directory to learn the current status of this or any other Internet


     In the Inter-Domain Routing Protocol (IDRP), all border
    routers (border intermediate systems (BISs) in ISO
    terminology) of a routing domain confederation (RDC) must be
    configured with the identity of all RDCs that overlap or
    enclose that RDC. This draft describes some minor
    modifications to IDRP specification that removes this

1 The Inter-Domain Routing Protocol

In the Inter-Domain Routing Protocol (IDRP, [1]), border intermediate
systems (BISs) of routing domains (RDs) exchange route updates.  A

Internet Draft     Configuring IDRP Confederations    October 28, 1996

route update advertises reachability to one or more address prefixes
(Network Layer Reachability Information, or NLRI, in ISO terminology).
Each IDRP route update also contains an RD_PATH attribute; the RD_PATH
is a list of Routing Domain Identifiers (RDIs) of RDs traversed by a
route update.  The RD_PATH is used to detect routing loops.

In a large internet, a routing update's RD_PATH may contain a large
number of RDIs.  To allow shorter RD_PATHs, two or more topologically
adjacent RDs may be combined into a single IDRP Routing Domain
Confederation (RDC). In turn, two or more topologically adjacent RDCs
may be combined into a single, larger, RDC. RDCs may also overlap.  An
RD outside an RDC A sees only the A's RDI in RD_PATHs of route updates
from A; that is, RDIs of RDs completely enclosed by A are not visible
outside A.

2 RDC Configuration

Section 7.13.2 of [1] specifies that a border router (or Border
Intermediate System (BIS)) that participates in one or more RDCs must:

    be aware of the RDIs of all confederations of which it is a
    member, and it must know the partial order which prevails
    between these confederations:  that is, it must know the
    nesting and overlap relationships between all confederations
    to which it belongs.

Such configuration is undesirable because changing an RDC's boundaries
may require significant coordination between that RDC and all other
RDCs that it contains or overlaps.

To understand the need for such configuration, we briefly describe
RD_PATH formation in IDRP (the interested reader is referred to
Section 7.12.3 of [1] for details).  When a routing update message
enters an RDC, the RDC's BIS inserts an ``entry'' marker in the
RD_PATH. Thus, the RD_PATH of a route update that has entered three
RDCs A, B and C looks like this:


The ellipses indicate RDIs of other RDs or RDCs traversed by the

When this route exits RDC B, B's BIS removes its ``entry'' marker and
updates the RD_PATH according to the rules described in Section 7.12.3

Ramesh Govindan            Expires  April 28, 1997            [Page 2]

Internet Draft     Configuring IDRP Confederations    October 28, 1996

                         B          *
                       *            *          *
                       *            *          *
                       * Enter B    * Enter C  * Exit B
                       *            *          *

Figure 1:  Suppose a route's  RD_PATH contains an ``entry''  marker for
RD B followed by an  ``entry'' marker for RD  C. If the route exits  B
before exiting C, C must overlap B.

of [1].  These rules depend on the nesting or overlap relationship
between B and all RDCs whose ``entry'' markers are listed in the
RD_PATH. As we show below, B cannot determine these relatioships from
the RD_PATH alone.  For this reason, [1] specifies the configuration
rule described above.

By simple examination of the RD_PATH, B's BIS can unambiguously assert
that RDC C overlaps RDC B. Indeed, all ``entry'' markers in the
RD_PATH to the ``right'' of B's ``entry'' marker correspond to RDCs
that overlap with B (Figure 1).

However, without configured information, B's BIS cannot unambiguously
determine whether RDC A overlaps or contains RDC B. Indeed, any
``entry'' marker in the RD_PATH to the ``left'' of B's ``entry''
marker may correspond to an RDC that either overlaps with, or
completely contains, B (Figure 2).

3 Solution

With the following modification to the RD_PATH formation rules of
Section 7.12.3 ([1]), the configuration rule of the previous section
is no longer necessary:

    In the absence of configured information, a BIS for an RDC B
    (say) shall assume that B is nested within RDCs whose
    ENTRY_SEQs and ENTRY_SETs appear to the ``left'' of B's

Ramesh Govindan            Expires  April 28, 1997            [Page 3]

Internet Draft     Configuring IDRP Confederations    October 28, 1996

      A                                         B
    ************************                  ***********
    *      B               *              A   *         *
    *    ************      *             **********************
----*----*----------*------*--->      ---*----*---------*-----*--->
    *    *          *      *             *    *         *     *
    *    ************      *             *    ***********     *
    *                      *             *                    *
    ************************             **********************
              (i)                                 (ii)

Figure 2:  Suppose a route's  RD_PATH contains an ``entry''  marker for
RD A followed  by an  ``entry'' marker for  RD B.  If the route  exits
B before exiting  A, (i)  A may completely  enclose B,  or (ii) B  may
overlap A.

Instead, Section 7.13.2 now requires the following configuration

    Each BIS must be aware of the RDCs entered by UPDATE PDUs
    received from each of its neighbors.  Each BIS must also be
    aware of the RDCs exited by UPDATE PDUs sent from the BIS to
    each of its neighbors.

That is, a BIS need know only about RDCs which it borders, not all the
RDCs in which it participates.  Two related modifications to [1] are
necessary.  Section 7.13.3 is now redundant; in our proposed solution,
confederation boundaries are configured.  For the same reason, the
OPEN PDU (Section 6.2) need no longer carry RDC IDs.

This solution has one important consequence.  Consider the case when A
overlaps with B in the RD_PATH shown in the previous section
(Figure 2(ii)).  If B's BIS were configured with this information,
both A and B's RDIs would appear in the route's RD_PATH, when seen at
any RD outside A. With our proposed solution, only A's RDI would
appear in the RD_PATH, when seen at any RD outside A. This is because
our solution treats B as if it were nested within A. Thus, the fact
that the route traverses RDC B is not visible outside RDC A. This does
not violate loop detection.  If, for policy reasons, it is desirable
to have B's RDI appear in the RD_PATH, B's network administrator can
configure nesting and overlap relationships according to the
configuration rule of Section 2.

Finally, an equally correct solution would have been to always assume
that A overlaps B. This solution provides no reduction, however, in

Ramesh Govindan            Expires  April 28, 1997            [Page 4]

Internet Draft     Configuring IDRP Confederations    October 28, 1996

the length of RD_PATHs, a primary motivation for introducing RDCs.


Yakov Rekhter motivated the study of this problem and provided
valuable feedback on earlier versions of the draft.  Cengiz
Alaettinoglu, Rusty Eddy, Deborah Estrin, and Kannan Varadhan also
influenced the contents of this draft.


[1] Protocol for exchange of inter-domain routeing information among
    intermediate systems to support forwarding of iso 8473 pdus.
    ISO/IEC 10747:  Information Processing Systems
    Telecommunications and Information Exchange between Systems,
    October 1993.

Ramesh Govindan            Expires  April 28, 1997            [Page 5]