home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_ietf_i / draft-ietf-idr-rdc-config-01.txt < prev    next >
Text File  |  1996-10-29  |  9KB  |  285 lines
  1.  
  2.  
  3. Internet Draft                                         Ramesh Govindan
  4. Expires  April 28, 1997                                        USC/ISI
  5. draft-ietf-idr-rdc-config-01.txt                      October 28, 1996
  6.  
  7.  
  8.                    Configuring IDRP Confederations
  9.  
  10.  
  11.  
  12.  
  13.  
  14. Status of this Memo
  15.  
  16.  
  17. This document is an Internet Draft, and can be found as
  18. draft-ietf-idr-rdc-config-00.txt in any standard internet drafts
  19. repository.  Internet Drafts are working documents of the Internet
  20. Engineering Task Force (IETF), its Areas, and its Working Groups.
  21. Note that other groups may also distribute working documents as
  22. Internet Drafts.
  23.  
  24. Internet Drafts are draft documents valid for a maximum of six months.
  25. Internet Drafts may be updated, replaced, or obsoleted by other
  26. documents at any time.  It is not appropriate to use Internet Drafts
  27. as reference material, or to cite them other than as a ``working
  28. draft'' or ``work in progress.''
  29.  
  30. Please check the I-D abstract listing contained in each Internet Draft
  31. directory to learn the current status of this or any other Internet
  32. Draft.
  33.  
  34.  
  35.                                Abstract
  36.  
  37.  
  38.      In the Inter-Domain Routing Protocol (IDRP), all border
  39.     routers (border intermediate systems (BISs) in ISO
  40.     terminology) of a routing domain confederation (RDC) must be
  41.     configured with the identity of all RDCs that overlap or
  42.     enclose that RDC. This draft describes some minor
  43.     modifications to IDRP specification that removes this
  44.     requirement.
  45.  
  46.  
  47. 1 The Inter-Domain Routing Protocol
  48.  
  49.  
  50. In the Inter-Domain Routing Protocol (IDRP, [1]), border intermediate
  51. systems (BISs) of routing domains (RDs) exchange route updates.  A
  52.  
  53.  
  54. Internet Draft     Configuring IDRP Confederations    October 28, 1996
  55.  
  56. route update advertises reachability to one or more address prefixes
  57. (Network Layer Reachability Information, or NLRI, in ISO terminology).
  58. Each IDRP route update also contains an RD_PATH attribute; the RD_PATH
  59. is a list of Routing Domain Identifiers (RDIs) of RDs traversed by a
  60. route update.  The RD_PATH is used to detect routing loops.
  61.  
  62. In a large internet, a routing update's RD_PATH may contain a large
  63. number of RDIs.  To allow shorter RD_PATHs, two or more topologically
  64. adjacent RDs may be combined into a single IDRP Routing Domain
  65. Confederation (RDC). In turn, two or more topologically adjacent RDCs
  66. may be combined into a single, larger, RDC. RDCs may also overlap.  An
  67. RD outside an RDC A sees only the A's RDI in RD_PATHs of route updates
  68. from A; that is, RDIs of RDs completely enclosed by A are not visible
  69. outside A.
  70.  
  71.  
  72.  
  73. 2 RDC Configuration
  74.  
  75.  
  76. Section 7.13.2 of [1] specifies that a border router (or Border
  77. Intermediate System (BIS)) that participates in one or more RDCs must:
  78.  
  79.  
  80.     be aware of the RDIs of all confederations of which it is a
  81.     member, and it must know the partial order which prevails
  82.     between these confederations:  that is, it must know the
  83.     nesting and overlap relationships between all confederations
  84.     to which it belongs.
  85.  
  86.  
  87. Such configuration is undesirable because changing an RDC's boundaries
  88. may require significant coordination between that RDC and all other
  89. RDCs that it contains or overlaps.
  90.  
  91. To understand the need for such configuration, we briefly describe
  92. RD_PATH formation in IDRP (the interested reader is referred to
  93. Section 7.12.3 of [1] for details).  When a routing update message
  94. enters an RDC, the RDC's BIS inserts an ``entry'' marker in the
  95. RD_PATH. Thus, the RD_PATH of a route update that has entered three
  96. RDCs A, B and C looks like this:
  97.  
  98.  
  99.     ...Enter(A)....Enter(B)....Enter(C)....
  100.  
  101.  
  102. The ellipses indicate RDIs of other RDs or RDCs traversed by the
  103. route.
  104.  
  105. When this route exits RDC B, B's BIS removes its ``entry'' marker and
  106. updates the RD_PATH according to the rules described in Section 7.12.3
  107.  
  108.  
  109. Ramesh Govindan            Expires  April 28, 1997            [Page 2]
  110.  
  111.  
  112. Internet Draft     Configuring IDRP Confederations    October 28, 1996
  113.  
  114.  
  115.                                      C
  116.                                     *********
  117.                          B          *
  118.                        *************************
  119.                        *            *          *
  120.                        *            *          *
  121.                     ---*------------*----------*--------->
  122.                        * Enter B    * Enter C  * Exit B
  123.                        *            *          *
  124.                        *************************
  125.                                     *
  126.                                     *********
  127.  
  128.  
  129.  
  130. Figure 1:  Suppose a route's  RD_PATH contains an ``entry''  marker for
  131. RD B followed by an  ``entry'' marker for RD  C. If the route exits  B
  132. before exiting C, C must overlap B.
  133.  
  134.  
  135. of [1].  These rules depend on the nesting or overlap relationship
  136. between B and all RDCs whose ``entry'' markers are listed in the
  137. RD_PATH. As we show below, B cannot determine these relatioships from
  138. the RD_PATH alone.  For this reason, [1] specifies the configuration
  139. rule described above.
  140.  
  141. By simple examination of the RD_PATH, B's BIS can unambiguously assert
  142. that RDC C overlaps RDC B. Indeed, all ``entry'' markers in the
  143. RD_PATH to the ``right'' of B's ``entry'' marker correspond to RDCs
  144. that overlap with B (Figure 1).
  145.  
  146. However, without configured information, B's BIS cannot unambiguously
  147. determine whether RDC A overlaps or contains RDC B. Indeed, any
  148. ``entry'' marker in the RD_PATH to the ``left'' of B's ``entry''
  149. marker may correspond to an RDC that either overlaps with, or
  150. completely contains, B (Figure 2).
  151.  
  152.  
  153.  
  154. 3 Solution
  155.  
  156.  
  157. With the following modification to the RD_PATH formation rules of
  158. Section 7.12.3 ([1]), the configuration rule of the previous section
  159. is no longer necessary:
  160.  
  161.  
  162.     In the absence of configured information, a BIS for an RDC B
  163.     (say) shall assume that B is nested within RDCs whose
  164.     ENTRY_SEQs and ENTRY_SETs appear to the ``left'' of B's
  165.     ENTRY_SEQ or ENTRY_SET.
  166.  
  167. Ramesh Govindan            Expires  April 28, 1997            [Page 3]
  168.  
  169.  
  170. Internet Draft     Configuring IDRP Confederations    October 28, 1996
  171.  
  172.  
  173.       A                                         B
  174.     ************************                  ***********
  175.     *      B               *              A   *         *
  176.     *    ************      *             **********************
  177. ----*----*----------*------*--->      ---*----*---------*-----*--->
  178.     *    *          *      *             *    *         *     *
  179.     *    ************      *             *    ***********     *
  180.     *                      *             *                    *
  181.     ************************             **********************
  182.               (i)                                 (ii)
  183.  
  184.  
  185.  
  186. Figure 2:  Suppose a route's  RD_PATH contains an ``entry''  marker for
  187. RD A followed  by an  ``entry'' marker for  RD B.  If the route  exits
  188. B before exiting  A, (i)  A may completely  enclose B,  or (ii) B  may
  189. overlap A.
  190.  
  191.  
  192. Instead, Section 7.13.2 now requires the following configuration
  193. information:
  194.  
  195.  
  196.     Each BIS must be aware of the RDCs entered by UPDATE PDUs
  197.     received from each of its neighbors.  Each BIS must also be
  198.     aware of the RDCs exited by UPDATE PDUs sent from the BIS to
  199.     each of its neighbors.
  200.  
  201.  
  202. That is, a BIS need know only about RDCs which it borders, not all the
  203. RDCs in which it participates.  Two related modifications to [1] are
  204. necessary.  Section 7.13.3 is now redundant; in our proposed solution,
  205. confederation boundaries are configured.  For the same reason, the
  206. OPEN PDU (Section 6.2) need no longer carry RDC IDs.
  207.  
  208. This solution has one important consequence.  Consider the case when A
  209. overlaps with B in the RD_PATH shown in the previous section
  210. (Figure 2(ii)).  If B's BIS were configured with this information,
  211. both A and B's RDIs would appear in the route's RD_PATH, when seen at
  212. any RD outside A. With our proposed solution, only A's RDI would
  213. appear in the RD_PATH, when seen at any RD outside A. This is because
  214. our solution treats B as if it were nested within A. Thus, the fact
  215. that the route traverses RDC B is not visible outside RDC A. This does
  216. not violate loop detection.  If, for policy reasons, it is desirable
  217. to have B's RDI appear in the RD_PATH, B's network administrator can
  218. configure nesting and overlap relationships according to the
  219. configuration rule of Section 2.
  220.  
  221. Finally, an equally correct solution would have been to always assume
  222. that A overlaps B. This solution provides no reduction, however, in
  223.  
  224.  
  225. Ramesh Govindan            Expires  April 28, 1997            [Page 4]
  226.  
  227.  
  228. Internet Draft     Configuring IDRP Confederations    October 28, 1996
  229.  
  230. the length of RD_PATHs, a primary motivation for introducing RDCs.
  231.  
  232.  
  233.  
  234. Acknowledgements
  235.  
  236.  
  237. Yakov Rekhter motivated the study of this problem and provided
  238. valuable feedback on earlier versions of the draft.  Cengiz
  239. Alaettinoglu, Rusty Eddy, Deborah Estrin, and Kannan Varadhan also
  240. influenced the contents of this draft.
  241.  
  242.  
  243. References
  244.  
  245.  
  246. [1] Protocol for exchange of inter-domain routeing information among
  247.     intermediate systems to support forwarding of iso 8473 pdus.
  248.     ISO/IEC 10747:  Information Processing Systems
  249.     Telecommunications and Information Exchange between Systems,
  250.     October 1993.
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282.  
  283. Ramesh Govindan            Expires  April 28, 1997            [Page 5]
  284.  
  285.