Network Working Group R. Colella Request for Comments: 1629 NIST Obsoletes: 1237 R. Callon Category: Standards Track Wellfleet E. Gardner Mitre Y. Rekhter T.J. Watson Research Center, IBM Corp. May 1994 Guidelines for OSI NSAP Allocation in the Internet Status of this Memo This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited. Abstract CLNP is currently being deployed in the Internet. This is useful to support OSI and DECnet(tm) traffic. In addition, CLNP has been proposed as a possible IPng candidate, to provide a long-term solution to IP address exhaustion. Required as part of the CLNP infrastructure are guidelines for network service access point (NSAP) address assignment. This paper provides guidelines for allocating NSAP addresses in the Internet. The guidelines provided in this paper have been the basis for initial deployment of CLNP in the Internet, and have proven very valuable both as an aid to scaling of CLNP routing, and for address administration.
Table of Contents 1. Introduction ............................... 4 2. Scope ...................................... 5 3. Background ................................. 7 3.1 OSI Routing Standards ..................... 7 3.2 Overview of IS-IS (ISO/IEC 10589) ......... 8 3.3 Overview of IDRP (ISO/IEC 10747) .......... 12 3.3.1 Scaling Mechanisms in IDRP .............. 14 3.4 Requirements of IS-IS and IDRP on NSAPs ... 15 4. NSAPs and Routing .......................... 16 4.1 Routing Data Abstraction .................. 16 4.2 NSAP Administration and Efficiency ........ 19 5. NSAP Administration and Routing in the In- ternet ................................... 21 5.1 Administration at the Area ................ 23 5.2 Administration at the Subscriber Routing Domain ................................... 24 5.3 Administration at the Provider Routing Domain ................................... 24 5.3.1 Direct Service Providers ................ 25 5.3.2 Indirect Providers ...................... 26 5.4 Multi-homed Routing Domains ............... 26 5.5 Private Links ............................. 31 5.6 Zero-Homed Routing Domains ................ 33 5.7 Address Transition Issues ................. 33 6. Recommendations ............................ 36 6.1 Recommendations Specific to U.S. Parts of the Internet ............................. 37 6.2 Recommendations Specific to European Parts of the Internet .......................... 39 6.2.1 General NSAP Structure .................. 40 6.2.2 Structure of the Country Domain Part .... 40 6.2.3 Structure of the Country Domain Specific Part ............................ 41 6.3 Recommendations Specific to Other Parts of the Internet ............................. 41 6.4 Recommendations for Multi-Homed Routing Domains .................................. 41 6.5 Recommendations for RDI and RDCI assign- ment ..................................... 42 7. Security Considerations .................... 42 8. Authors' Addresses ......................... 43 9. Acknowledgments ............................ 43 10. References ................................ 44 A. Administration of NSAPs .................... 46 A.1 GOSIP Version 2 NSAPs .................... 47 A.1.1 Application for Administrative Authority
1. Introduction The Internet is moving towards a multi-protocol environment that includes CLNP. To support CLNP in the Internet, an OSI lower layers infrastructure is required. This infrastructure comprises the connectionless network protocol (CLNP)  and supporting routing protocols. Also required as part of this infrastructure are guidelines for network service access point (NSAP) address assignment. This paper provides guidelines for allocating NSAP addresses in the Internet (the terms NSAP and NSAP address are used interchangeably throughout this paper in referring to NSAP addresses). The guidelines presented in this document are quite similar to the guidelines that are proposed in the Internet for IP address allocation with CIDR (RFC 1519 ). The major difference between the two is the size of the addresses (4 octets for CIDR vs 20 octets for CLNP). The larger NSAP addresses allows considerably greater flexibility and scalability. The remainder of this paper is organized into five major sections and an appendix. Section 2 defines the boundaries of the problem addressed in this paper and Section 3 provides background information on OSI routing and the implications for NSAP addresses. Section 4 addresses the specific relationship between NSAP addresses and routing, especially with regard to hierarchical routing and data abstraction. This is followed in Section 5 with an application of these concepts to the Internet environment. Section 6 provides recommended guidelines for NSAP address allocation in the Internet. This includes recommendations for the U.S. and European parts of the Internet, as well as more general recommendations for any part of the Internet. The Appendix contains a compendium of useful information concerning NSAP structure and allocation authorities. The GOSIP Version 2 NSAP structure is discussed in detail and the structure for U.S.-based DCC (Data Country Code) NSAPs is described. Contact information for the registration authorities for GOSIP and DCC-based NSAPs in the U.S., the General Services Administration (GSA) and the American National Standards Institute (ANSI), respectively, is provided. This document obsoletes RFC 1237. The changes from RFC 1237 are minor, and primarily editorial in nature. The descriptions of OSI routing standards contained in Section 3 have been updated to reflect the current status of the relevant standards, and a description of the OSI Interdomain Routing Protocol (IDRP) has been added. Recommendations specific to the European part of the Internet have
been added in Section 6, along with recommendations for Routing Domain Identifiers and Routing Domain Confederation Identifiers needed for operation of IDRP. 2. Scope Control over the collection of hosts and the transmission and switching facilities that compose the networking resources of the global Internet is not homogeneous, but is distributed among multiple administrative authorities. For the purposes of this paper, the term network service provider (or just provider) is defined to be an organization that is in the business of providing datagram switching services to customers. Organizations that are *only* customers (i.e., that do not provide datagram services to other organizations) are called network service subscribers (or simply subscribers). In the current Internet, subscribers (e.g., campus and corporate site networks) attach to providers (e.g., regionals, commercial providers, and government backbones) in only one or a small number of carefully controlled access points. For discussion of OSI NSAP allocation in this paper, providers are treated as composing a mesh having no fixed hierarchy. Addressing solutions which require substantial changes or constraints on the current topology are not considered in this paper. There are two aspects of interest when discussing OSI NSAP allocation within the Internet. The first is the set of administrative requirements for obtaining and allocating NSAP addresses; the second is the technical aspect of such assignments, having largely to do with routing, both within a routing domain (intra-domain routing) and between routing domains (inter-domain routing). This paper focuses on the technical issues. The technical issues in NSAP allocation are mainly related to routing. This paper assumes that CLNP will be widely deployed in the Internet, and that the routing of CLNP traffic will normally be based on the OSI end-system to intermediate system routing protocol (ES-IS) , intra-domain IS-IS protocol , and inter-domain routing protocol (IDRP) . It is expected that in the future the OSI routing architecture will be enhanced to include support for multicast, resource reservation, and other advanced services. The requirements for addressing for these future services is outside of the scope of this document. The guidelines provided in this paper have been the basis for initial deployment of CLNP in the Internet, and have proven very valuable both as an aid to scaling of CLNP routing, and to address administration.
The guidelines in this paper are oriented primarily toward the large-scale division of NSAP address allocation in the Internet. Topics covered include: * Arrangement of parts of the NSAP for efficient operation of the IS-IS routing protocol; * Benefits of some topological information in NSAPs to reduce routing protocol overhead, and specifically the overhead on inter-domain routing (IDRP); * The anticipated need for additional levels of hierarchy in Internet addressing to support network growth and use of the Routing Domain Confederation mechanism of IDRP to provide support for additional levels of hierarchy; * The recommended mapping between Internet topological entities (i.e., service providers and service subscribers) and OSI addressing and routing components, such as areas, domains and confederations; * The recommended division of NSAP address assignment authority among service providers and service subscribers; * Background information on administrative procedures for registration of administrative authorities immediately below the national level (GOSIP administrative authorities and ANSI organization identifiers); and, * Choice of the high-order portion of the NSAP in subscriber routing domains that are connected to more than one service provider. It is noted that there are other aspects of NSAP allocation, both technical and administrative, that are not covered in this paper. Topics not covered or mentioned only superficially include: * Identification of specific administrative domains in the Internet; * Policy or mechanisms for making registered information known to third parties (such as the entity to which a specific NSAP or a portion of the NSAP address space has been allocated);
* How a routing domain (especially a site) should organize its internal topology of areas or allocate portions of its NSAP address space; the relationship between topology and addresses is discussed, but the method of deciding on a particular topology or internal addressing plan is not; and, * Procedures for assigning the System Identifier (ID) portion of the NSAP. A method for assignment of System IDs is presented in . 3. Background Some background information is provided in this section that is helpful in understanding the issues involved in NSAP allocation. A brief discussion of OSI routing is provided, followed by a review of the intra-domain and inter-domain protocols in sufficient detail to understand the issues involved in NSAP allocation. Finally, the specific constraints that the routing protocols place on NSAPs are listed. 3.1. OSI Routing Standards OSI partitions the routing problem into three parts: * routing exchanges between hosts (a.k.a., end systems or ESs) and routers (a.k.a., intermediate systems or ISs) (ES-IS); * routing exchanges between routers in the same routing domain (intra-domain IS-IS); and, * routing among routing domains (inter-domain IS-IS). ES-IS (international standard ISO 9542) advanced to international standard (IS) status within ISO in 1987. Intra-domain IS-IS advanced to IS status within ISO in 1992. Inter-Domain Routing Protocol (IDRP) advanced to IS status within ISO in October 1993. CLNP, ES- IS, and IS-IS are all widely available in vendor products, and have been deployed in the Internet for several years. IDRP is currently being implemented in vendor products. This paper examines the technical implications of NSAP assignment under the assumption that ES-IS, intra-domain IS-IS, and IDRP routing are deployed to support CLNP.
3.2. Overview of ISIS (ISO/IEC 10589) The IS-IS intra-domain routing protocol, ISO/IEC 10589, provides routing for OSI environments. In particular, IS-IS is designed to work in conjunction with CLNP, ES-IS, and IDRP. This section briefly describes the manner in which IS-IS operates. In IS-IS, the internetwork is partitioned into routing domains. A routing domain is a collection of ESs and ISs that operate common routing protocols and are under the control of a single administration (throughout this paper, "domain" and "routing domain" are used interchangeably). Typically, a routing domain may consist of a corporate network, a university campus network, a regional network, a backbone, or a similar contiguous network under control of a single administrative organization. The boundaries of routing domains are defined by network management by setting some links to be exterior, or inter-domain, links. If a link is marked as exterior, no intra-domain IS-IS routing messages are sent on that link. IS-IS routing makes use of two-level hierarchical routing. A routing domain is subdivided into areas (also known as level 1 subdomains). Level 1 routers know the topology in their area, including all routers and hosts. However, level 1 routers do not know the identity of routers or destinations outside of their area. Level 1 routers forward all traffic for destinations outside of their area to a level 2 router within their area. Similarly, level 2 routers know the level 2 topology and know which addresses are reachable via each level 2 router. The set of all level 2 routers in a routing domain are known as the level 2 subdomain, which can be thought of as a backbone for interconnecting the areas. Level 2 routers do not need to know the topology within any level 1 area, except to the extent that a level 2 router may also be a level 1 router within a single area. Only level 2 routers can exchange data packets or routing information directly with routers located outside of their routing domain. NSAP addresses provide a flexible, variable length addressing format, which allows for multi-level hierarchical address assignment. These addresses provide the flexibility needed to solve two critical problems simultaneously: (i) How to administer a worldwide address space; and (ii) How to assign addresses in a manner which makes routing scale well in a worldwide Internet. As illustrated in Figure 1, ISO addresses are subdivided into the Initial Domain Part (IDP) and the Domain Specific Part (DSP). The IDP is the part which is standardized by ISO, and specifies the format and authority responsible for assigning the rest of the
address. The DSP is assigned by whatever addressing authority is specified by the IDP (see Appendix A for more discussion on the top level NSAP addressing authorities). It is expected that the authority specified by the IDP may further sub-divide the DSP, and may assign sub-authorities responsible for parts of the DSP. For routing purposes, ISO addresses are subdivided by IS-IS into the area address, the system identifier (ID), and the NSAP selector (SEL). The area address identifies both the routing domain and the area within the routing domain. Generally, the area address corresponds to the IDP plus a high-order part of the DSP (HO-DSP). <----IDP---> <----------------------DSP----------------------------> <-----------HO-DSP------------> +-----+-----+-------------------------------+--------------+-------+ | AFI | IDI |Contents assigned by authority identified in IDI field| +-----+-----+-------------------------------+--------------+-------+ <----------------Area Address--------------> <-----ID-----> <-SEL-> IDP Initial Domain Part AFI Authority and Format Identifier IDI Initial Domain Identifier DSP Domain Specific Part HO-DSP High-order DSP ID System Identifier SEL NSAP Selector Figure 1: OSI Hierarchical Address Structure. The ID field may be from one to eight octets in length, but must have a single known length in any particular routing domain. Each router is configured to know what length is used in its domain. The SEL field is always one octet in length. Each router is therefore able to identify the ID and SEL fields as a known number of trailing octets of the NSAP address. The area address can be identified as the remainder of the address (after truncation of the ID and SEL fields). It is therefore not necessary for the area address to have any particular length -- the length of the area address could vary between different area addresses in a given routing domain. Usually, all nodes in an area have the same area address. However, sometimes an area might have multiple addresses. Motivations for allowing this are several:
* It might be desirable to change the address of an area. The most graceful way of changing an area address from A to B is to first allow it to have both addresses A and B, and then after all nodes in the area have been modified to recognize both addresses, one by one the nodes can be modified to forget address A. * It might be desirable to merge areas A and B into one area. The method for accomplishing this is to, one by one, add knowledge of address B into the A partition, and similarly add knowledge of address A into the B partition. * It might be desirable to partition an area C into two areas, A and B (where A might equal C, in which case this example becomes one of removing a portion of an area). This would be accomplished by first introducing knowledge of address A into the appropriate nodes (those destined to become area A), and knowledge of address B into the appropriate nodes, and then one by one removing knowledge of address C. Since the addressing explicitly identifies the area, it is very easy for level 1 routers to identify packets going to destinations outside of their area, which need to be forwarded to level 2 routers. Thus, in IS-IS routers perform as follows: * Level 1 intermediate systems route within an area based on the ID portion of the ISO address. Level 1 routers recognize, based on the destination address in a packet, whether the destination is within the area. If so, they route towards the destination. If not, they route to the nearest level 2 router. * Level 2 intermediate systems route based on address prefixes, preferring the longest matching prefix, and preferring internal routes over external routes. They route towards areas, without regard to the internal structure of an area; or towards level 2 routers on the routing domain boundary that have advertised external address prefixes into the level 2 subdomain. A level 2 router may also be operating as a level 1 router in one area. A level 1 router will have the area portion of its address manually configured. It will refuse to become a neighbor with a router whose area addresses do not overlap its own area addresses. However, if a level 1 router has area addresses A, B, and C, and a neighbor has area addresses B and D, then the level 1 IS will accept the other IS as a level 1 neighbor. A level 2 router will accept another level 2 router as a neighbor, regardless of area address. However, if the area addresses do not overlap, the link would be considered by both routers to be level 2
only, and only level 2 routing packets would flow on the link. External links (i.e., to other routing domains) must be between level 2 routers in different routing domains. IS-IS provides an optional partition repair function. If a level 1 area becomes partitioned, this function, if implemented, allows the partition to be repaired via use of level 2 routes. IS-IS requires that the set of level 2 routers be connected. Should the level 2 backbone become partitioned, there is no provision for use of level 1 links to repair a level 2 partition. Occasionally a single level 2 router may lose connectivity to the level 2 backbone. In this case the level 2 router will indicate in its level 1 routing packets that it is not "attached", thereby allowing level 1 routers in the area to route traffic for outside of the area to a different level 2 router. Level 1 routers therefore route traffic to destinations outside of their area only to level 2 routers which indicate in their level 1 routing packets that they are "attached". A host may autoconfigure the area portion of its address by extracting the area portion of a neighboring router's address. If this is the case, then a host will always accept a router as a neighbor. Since the standard does not specify that the host *must* autoconfigure its area address, a host may be pre-configured with an area address. Special treatment is necessary for broadcast subnetworks, such as LANs. This solves two sets of issues: (i) In the absence of special treatment, each router on the subnetwork would announce a link to every other router on the subnetwork, resulting in O(n-squared) links reported; (ii) Again, in the absence of special treatment, each router on the LAN would report the same identical list of end systems on the LAN, resulting in substantial duplication. These problems are avoided by use of a "pseudonode", which represents the LAN. Each router on the LAN reports that it has a link to the pseudonode (rather than reporting a link to every other router on the LAN). One of the routers on the LAN is elected "designated router". The designated router then sends out a Link State Packet (LSP) on behalf of the pseudonode, reporting links to all of the routers on the LAN. This reduces the potential n-squared links to n links. In addition, only the pseudonode LSP includes the list of end systems on the LAN, thereby eliminating the potential duplication.
The IS-IS provides for optional Quality of Service (QOS) routing, based on throughput (the default metric), delay, expense, or residual error probability. IS-IS has a provision for authentication information to be carried in all IS-IS PDUs. Currently the only form of authentication which is defined is a simple password. A password may be associated with each link, each area, and with the level 2 subdomain. A router not in possession of the appropriate password(s) is prohibited from participating in the corresponding function (i.e., may not initialize a link, be a member of the area, or a member of the level 2 subdomain, respectively). Procedures are provided to allow graceful migration of passwords without disrupting operation of the routing protocol. The authentication functions are extensible so that a stronger, cryptographically-based security scheme may be added in an upwardly compatible fashion at a future date. 3.3. Overview of IDRP (ISO/IEC 10747) The Inter-Domain Routing Protocol (IDRP, ISO/IEC 10747), developed in ISO, provides routing for OSI environments. In particular, IDRP is designed to work in conjuction with CLNP, ES-IS, and IS-IS. This section briefly describes the manner in which IDRP operates. Consistent with the OSI Routing Framework , in IDRP the internetwork is partitioned into routing domains. IDRP places no restrictions on the inter-domain topology. A router that participates in IDRP is called a Boundary Intermediate System (BIS). Routing domains that participate in IDRP are not allowed to overlap - a BIS may belong to only one domain. A pair of BISs are called external neighbors if these BISs belong to different domains but share a common subnetwork (i.e., a BIS can reach its external neighbor in a single network layer hop). Two domains are said to be adjacent if they have BISs that are external neighbors of each other. A pair of BISs are called internal neighbors if these BISs belong to the same domain. In contrast with external neighbors, internal neighbors don't have to share a common subnetwork -- IDRP assumes that a BIS should be able to exchange Network Protocol Date Units (NPDUs) with any of its internal neighbors by relying solely on intra-domain routing procedures. IDRP governs the exchange of routing information between a pair of neighbors, either external or internal. IDRP is self-contained with respect to the exchange of information between external neighbors. Exchange of information between internal neighbors relies on
additional support provided by intra-domain routing (unless internal neighbors share a common subnetwork). To facilitate routing information aggregation/abstraction, IDRP allows grouping of a set of connected domains into a Routing Domain Confederation (RDC). A given domain may belong to more than one RDC. There are no restrictions on how many RDCs a given domain may simultaneously belong to, and no preconditions on how RDCs should be formed -- RDCs may be either nested, or disjoint, or may overlap. One RDC is nested within another RDC if all members (RDs) of the former are also members of the latter, but not vice versa. Two RDCs overlap if they have members in common and also each has members that are not in the other. Two RDCs are disjoint if they have no members in common. Each domain participating in IDRP is assigned a unique Routing Domain Identifier (RDI). Syntactically an RDI is represented as an OSI network layer address. Each RDC is assigned a unique Routing Domain Confederation Identifier (RDCI). RDCIs are assigned out of the address space allocated for RDIs -- RDCIs and RDIs are syntactically indistinguishable. Procedures for assigning and managing RDIs and RDCIs are outside the scope of the protocol. However, since RDIs are syntactically nothing more than network layer addresses, and RDCIs are syntactically nothing more than RDIs, it is expected that RDI and RDCI assignment and management would be part of the network layer assignment and management procedures. Recommendations for RDI and RDCI assignment are provided in Section 6.5. IDRP requires a BIS to be preconfigured with the RDI of the domain to which the BIS belongs. If a BIS belongs to a domain that is a member of one or more RDCs, then the BIS has to be preconfigured with RDCIs of all the RDCs the domain is in, and the information about relations between the RDCs - nested or overlapped. IDRP doesn't assume or require any particular internal structure for the addresses. The protocol provides correct routing as long as the following guidelines are met: * End systems and intermediate systems may use any NSAP address or Network Entity Title (NET -- i.e., an NSAP address without the selector) that has been assigned under ISO 8348  guidelines; * An NSAP prefix carried in the Network Layer Reachability Information (NLRI) field for a route originated by a BIS in a given routing domain should be associated with only that routing domain; that is, no system identified by the prefix should reside in a different routing domain; ambiguous routing may result if several routing domains originate routes whose
NLRI field contain identical NSAP address prefixes, since this would imply that the same system(s) is simultaneously located in several routing domains; * Several different NSAP prefixes may be associated with a single routing domain which contains a mix of systems which use NSAP addresses assigned by several different addressing authorities. IDRP assumes that the above guidelines have been satisfied, but it contains no means to verify that this is so. Therefore, such verification is assumed to be the responsibility of the administrators of routing domains. IDRP provides mandatory support for data integrity and optional support for data origin authentication for all of its messages. Each message carries a 16-octet digital signature that is computed by applying the MD-4 algorithm (RFC 1320) to the context of the message itself. This signature provides support for data integrity. To support data origin authentication a BIS, when computing a digital signature of a message, may prepend and append additional information to the message. This information is not passed as part of the message but is known to the receiver. 3.3.1. Scaling Mechanisms in IDRP The ability to group domains in RDCs provides a simple, yet powerful mechanism for routing information aggregation and abstraction. It allows reduction of topological information by replacing a sequence of RDIs carried by the RD_PATH attribute with a single RDCI. It also allows reduction of the amount of information related to transit policies, since the policies can be expressed in terms of aggregates (RDCs), rather than individual components (RDs). It also allows simplification of route selection policies, since these policies can be expressed in terms of aggregates (RDCs) rather than individual components (RDs). Aggregation and abstraction of Network Layer Reachability Information (NLRI) is supported by the "route aggregation" mechanism of IDRP. This mechanism is complementary to the Routing Domain Confederations mechanism. Both mechanisms are intended to provide scalable routing via information reduction/abstraction. However, the two mechanisms are used for different purposes: route aggregation for aggregation and abstraction of routes (i.e., Network Layer Reachability Information), Routing Domain Confederations for aggregation and abstraction of topology and/or policy information. To provide maximum benefits, both mechanisms can be used together. This implies that address assignment that will facilitate route aggregation does not conflict with the ability to form RDCs, and vice versa; formation
of RDCs should be done in a manner consistent with the address assignment needed for route aggregation. 3.4. Requirements of IS-IS and IDRP on NSAPs The preferred NSAP format for IS-IS is shown in Figure 1. A number of points should be noted from IS-IS: * The IDP is as specified in ISO 8348, the OSI network layer service specification ; * The high-order portion of the DSP (HO-DSP) is that portion of the DSP whose assignment, structure, and meaning are not constrained by IS-IS; * The area address (i.e., the concatenation of the IDP and the HO-DSP) must be globally unique. If the area address of an NSAP matches one of the area addresses of a router, it is in the router's area and is routed to by level 1 routing; * Level 2 routing acts on address prefixes, using the longest address prefix that matches the destination address; * Level 1 routing acts on the ID field. The ID field must be unique within an area for ESs and level 1 ISs, and unique within the routing domain for level 2 ISs. The ID field is assumed to be flat. The method presented in RFC 1526  may optionally be used to assure globally unique IDs; * The one-octet NSAP Selector, SEL, determines the entity to receive the CLNP packet within the system identified by the rest of the NSAP (i.e., a transport entity) and is always the last octet of the NSAP; and, * A system shall be able to generate and forward data packets containing addresses in any of the formats specified by ISO 8348. However, within a routing domain that conforms to IS-IS, the lower-order octets of the NSAP should be structured as the ID and SEL fields shown in Figure 1 to take full advantage of IS-IS routing. End systems with addresses which do not conform may require additional manual configuration and be subject to inferior routing performance. For purposes of efficient operation of the IS-IS routing protocol, several observations may be made. First, although the IS-IS protocol specifies an algorithm for routing within a single routing domain, the routing algorithm must efficiently route both: (i) Packets whose final destination is in the domain (these must, of course, be routed
to the correct destination end system in the domain); and (ii) Packets whose final destination is outside of the domain (these must be routed to an appropriate "border" router, from which they will exit the domain). For those destinations which are in the domain, level 2 routing treats the entire area address (i.e., all of the NSAP address except the ID and SEL fields) as if it were a flat field. Thus, the efficiency of level 2 routing to destinations within the domain is affected only by the number of areas in the domain, and the number of area addresses assigned to each area. For those destinations which are outside of the domain, level 2 routing routes according to address prefixes. In this case, there is considerable potential advantage (in terms of reducing the amount of routing information that is required) if the number of address prefixes required to describe any particular set of external destinations can be minimized. Efficient routing with IDRP similarly also requires minimization of the number of address prefixes needed to describe specific destinations. In other words, addresses need to be assigned with topological significance. This requirement is described in more detail in the following sections. 4. NSAPs and Routing 4.1. Routing Data Abstraction When determining an administrative policy for NSAP assignment, it is important to understand the technical consequences. The objective behind the use of hierarchical routing is to achieve some level of routing data abstraction, or summarization, to reduce the processing time, memory requirements, and transmission bandwidth consumed in support of routing. This implies that address assignment must serve the needs of routing, in order for routing to scale to very large networks. While the notion of routing data abstraction may be applied to various types of routing information, this and the following sections primarily emphasize one particular type, namely reachability information. Reachability information describes the set of reachable destinations. Abstraction of reachability information dictates that NSAPs be assigned according to topological routing structures. However, administrative assignment falls along organizational or political boundaries. These may not be congruent to topological boundaries, and therefore the requirements of the two may collide. A balance between these two needs is necessary.
Routing data abstraction occurs at the boundary between hierarchically arranged topological routing structures. An element lower in the hierarchy reports summary routing information to its parent(s). Within the current OSI routing framework  and routing protocols, the lowest boundary at which this can occur is the boundary between an area and the level 2 subdomain within a IS-IS routing domain. Data abstraction is designed into IS-IS at this boundary, since level 1 ISs are constrained to reporting only area addresses. Level 2 routing is based upon address prefixes. Level 2 routers (ISs) distribute, throughout the level 2 subdomain, the area addresses of the level 1 areas to which they are attached (and any manually configured reachable address prefixes). Level 2 routers compute next-hop forwarding information to all advertised address prefixes. Level 2 routing is determined by the longest advertised address prefix that matches the destination address. At routing domain boundaries, address prefix information is exchanged with other routing domains via IDRP. If area addresses within a routing domain are all drawn from distinct NSAP assignment authorities (allowing no abstraction), then the boundary prefix information consists of an enumerated list of all area addresses. Alternatively, should the routing domain "own" an address prefix and assign area addresses based upon it, boundary routing information can be summarized into the single prefix. This can allow substantial data reduction and, therefore, will allow much better scaling (as compared to the uncoordinated area addresses discussed in the previous paragraph). If routing domains are interconnected in a more-or-less random (non- hierarchical) scheme, it is quite likely that no further abstraction of routing data can occur. Since routing domains would have no defined hierarchical relationship, administrators would not be able to assign area addresses out of some common prefix for the purpose of data abstraction. The result would be flat inter-domain routing; all routing domains would need explicit knowledge of all other routing domains that they route to. This can work well in small- and medium- sized internets, up to a size somewhat larger than the current IP Internet. However, this does not scale to very large internets. For example, we expect growth in the future to an international Internet which has tens or hundreds of thousands of routing domains in the U.S. alone. Even larger numbers of routing domains are possible when each home, or each small company, becomes its own routing domain. This requires a greater degree of data abstraction beyond that which can be achieved at the "routing domain" level.
In the Internet, however, it should be possible to exploit the existing hierarchical routing structure interconnections, as discussed in Section 5. Thus, there is the opportunity for a group of subscribers each to be assigned an address prefix from a shorter prefix assigned to their provider. Each subscriber now "owns" its (somewhat longer) prefix, from which it assigns its area addresses. The most straightforward case of this occurs when there is a set of subscribers whose routing domains are all attached only to a single service provider, and which use that provider for all external (inter-domain) traffic. A short address prefix may be assigned to the provider, which then assigns slightly longer prefixes (based on the provider's prefix) to each of the subscribers. This allows the provider, when informing other providers of the addresses that it can reach, to abbreviate the reachability information for a large number of routing domains as a single prefix. This approach therefore can allow a great deal of hierarchical abbreviation of routing information, and thereby can greatly improve the scalability of inter-domain routing. Clearly, this approach is recursive and can be carried through several iterations. Routing domains at any "level" in the hierarchy may use their prefix as the basis for subsequent suballocations, assuming that the NSAP addresses remain within the overall length and structure constraints. The flexibility of NSAP addresses facilitates this form of hierarchical address assignment and routing. As one example of how NSAPs may be used, the GOSIP Version 2 NSAP structure is discussed later in this section. At this point, we observe that the number of nodes at each lower level of a hierarchy tends to grow exponentially. Thus the greatest gains in data abstraction occur at the leaves and the gains drop significantly at each higher level. Therefore, the law of diminishing returns suggests that at some point data abstraction ceases to produce significant benefits. Determination of the point at which data abstraction ceases to be of benefit requires a careful consideration of the number of routing domains that are expected to occur at each level of the hierarchy (over a given period of time), compared to the number of routing domains and address prefixes that can conveniently and efficiently be handled via dynamic inter-domain routing protocols. As the Internet grows, further levels of hierarchy may become necessary. Again, this requires considerable flexibility in the addressing scheme, such as is provided by NSAP addresses.
4.2. NSAP Administration and Efficiency There is a balance that must be sought between the requirements on NSAPs for efficient routing and the need for decentralized NSAP administration. The NSAP structure from Version 2 of GOSIP (Figure 2) offers one example of how these two needs might be met. The AFI, IDI, DSP Format Identifier (DFI), and Administrative Authority (AA) fields provide for administrative decentralization. The AFI/IDI pair of values 47.0005 identify the U.S. Government as the authority responsible for defining the DSP structure and allocating values within it (see the Appendix for more information on NSAP structure). <----IDP---> +-----+-----+----------------------------------------+ | AFI | IDI |<----------------------DSP------------->| +-----+-----+----------------------------------------+ | 47 | 0005| DFI | AA | Rsvd | RD | Area | ID | SEL | +-----+-----+----------------------------------------+ octets | 1 | 2 | 1 | 3 | 2 | 2 | 2 | 6 | 1 | +-----+-----+----------------------------------------+ IDP Initial Domain Part AFI Authority and Format Identifier IDI Initial Domain Identifier DSP Domain Specific Part DFI DSP Format Identifier AA Administrative Authority Rsvd Reserved RD Routing Domain Identifier Area Area Identifier ID System Identifier SEL NSAP Selector Figure 2: GOSIP Version 2 NSAP structure. [Note: We are using U.S. GOSIP version 2 addresses only as an example. It is not necessary that NSAPs be allocated from the GOSIP Version 2 authority under 47.0005. The ANSI format under the Data Country Code for the U.S. (DCC=840) and formats assigned to other countries and ISO members or liaison organizations are also being used, and work equally well. For parts of the Internet outside of the U.S. there may in some cases be strong reasons to prefer a country- or area-specific format rather than the U.S. GOSIP format. However, GOSIP addresses are used in most cases in the examples in this paper because: * The DSP format has been defined and allows hierarchical allocation; and,
* An operational registration authority for suballocation of AA values under the GOSIP address space has already been established at GSA.] GOSIP Version 2 defines the DSP structure as shown (under DFI=80h) and provides for the allocation of AA values to administrations. Thus, the fields from the AFI to the AA, inclusive, represent a unique address prefix assigned to an administration. American National Standard X3.216-1992  specifies the structure of the DSP for NSAP addresses that use an Authority and Format Identifier (AFI) value of (decimal) 39, which identifies the "ISO- DCC" (data country code) format, in which the value of the Initial Domain Identifier (IDI) is (decimal) 840, which identifies the U.S. National Body (ANSI). This DSP structure is identical to the structure that is specified by GOSIP Version 2. The AA field is called "org" for organization identifier in the ANSI standard, and the ID field is called "system". The ANSI format, therefore, differs from the GOSIP format illustrated above only in that the AFI and IDI specify the "ISO-DCC" format rather than the "ISO 6523-ICD" format used by GOSIP, and the "AA" field is administered by an ANSI registration authority rather than by the GSA. Organization identifiers may be obtained from ANSI. The technical considerations applicable to NSAP administration are independent of whether a GOSIP Version 2 or an ANSI value is used for the NSAP assignment. Similarly, although other countries make use of different NSAP formats, the principles of NSAP assignment and use are the same. The NSAP formats recommended by RARE WG4 for use in Europe are discussed in Section 6.2. In the low-order part of the GOSIP Version 2 NSAP format, two fields are defined in addition to those required by IS-IS. These fields, RD and Area, are defined to allow allocation of NSAPs along topological boundaries in support of increased data abstraction. Administrations assign RD identifiers underneath their unique address prefix (the reserved field is left to accommodate future growth and to provide additional flexibility for inter-domain routing). Routing domains allocate Area identifiers from their unique prefix. The result is: * AFI+IDI+DFI+AA = administration prefix, * administration prefix(+Rsvd)+RD = routing domain prefix, and, * routing domain prefix+Area = area address.
This provides for summarization of all area addresses within a routing domain into one prefix. If the AA identifier is accorded topological significance (in addition to administrative significance), an additional level of data abstraction can be obtained, as is discussed in the next section. 5. NSAP Administration and Routing in the Internet Basic Internet routing components are service providers and service subscribers. A natural mapping from these components to OSI routing components is that each provider and subscriber operates as a routing domain. Alternatively, a subscriber may choose to operate as a part of a provider domain; that is, as an area within the provider's routing domain. However, in such a case the discussion in Section 5.1 applies. We assume that most subscribers will prefer to operate a routing domain separate from their provider's. Such subscribers can exchange routing information with their provider via interior routing protocol route leaking or via IDRP; for the purposes of this discussion, the choice is not significant. The subscriber is still allocated a prefix from the provider's address space, and the provider advertises its own prefix into inter-domain routing. Given such a mapping, where should address administration and allocation be performed to satisfy both administrative decentralization and data abstraction? Three possibilities are considered: 1. at the area, 2. at the subscriber routing domain, and, 3. at the provider routing domain. Subscriber routing domains correspond to end-user sites, where the primary purpose is to provide intra-domain routing services. Provider routing domains are deployed to carry transit (i.e., inter-domain) traffic. The greatest burden in transmitting and operating on routing information is at the top of the routing hierarchy, where routing information tends to accumulate. In the Internet, for example, each provider must manage the set of network numbers for all networks reachable through the provider.
For traffic destined for other networks, the provider will route based on inter-domain routing information obtained from other providers or, in some cases, to a default provider. In general, higher levels of the routing hierarchy will benefit the most from the abstraction of routing information at a lower level of the routing hierarchy. There is relatively little direct benefit to the administration that performs the abstraction, since it must maintain routing information individually on each attached topological routing structure. For example, suppose that a given subscriber is trying to decide whether to obtain an NSAP address prefix based on an AA value from GSA (implying that the first four octets of the address would be those assigned out of the GOSIP space), or based on an RD value from its provider (implying that the first seven octets of the address are those obtained by that provider). If considering only their own self-interest, the subscriber and its local provider have little reason to choose one approach or the other. The subscriber must use one prefix or another; the source of the prefix has little effect on routing efficiency within the subscriber's routing domain. The provider must maintain information about each attached subscriber in order to route, regardless of any commonality in the prefixes of its subscribers. However, there is a difference when the local provider distributes routing information to other providers. In the first case, the provider cannot aggregate the subscriber's address into its own prefix; the address must be explicitly listed in routing exchanges, resulting in an additional burden to other providers which must exchange and maintain this information. In the second case, each other provider sees a single address prefix for the local provider which encompasses the new subscriber. This avoids the exchange of additional routing information to identify the new subscriber's address prefix. Thus, the advantages primarily benefit other providers which maintain routing information about this provider (and its subscribers). Clearly, a symmetric application of these principles is in the interest of all providers, enabling them to more efficiently support CLNP routing to their customers. The guidelines discussed below describe reasonable ways of managing the OSI address space that benefit the entire community.
5.1. Administration at the Area If areas take their area addresses from a myriad of unrelated NSAP allocation authorities, there will be effectively no data abstraction beyond what is built into IS-IS. For example, assume that within a routing domain three areas take their area addresses, respectively, out of: * the GOSIP Version 2 authority assigned to the Department of Commerce, with an AA of nnn: AFI=47, IDI=0005, DFI=80h, AA=nnn, ... ; * the GOSIP Version 2 authority assigned to the Department of the Interior, with an AA of mmm: AFI=47, IDI=0005, DFI=80h, AA=mmm, ... ; and, * the ANSI authority under the U.S. Data Country Code (DCC) (Section A.2) for organization XYZ with ORG identifier = xxx: AFI=39, IDI=840, DFI=dd, ORG=xxx, .... As described in Section 3.3, from the point of view of any particular routing domain, there is no harm in having the different areas in the routing domain use addresses obtained from a wide variety of administrations. For routing within the domain, the area addresses are treated as a flat field. However, this does have a negative effect on inter-domain routing, particularly on those other domains which need to maintain routes to this domain. There is no common prefix that can be used to represent these NSAPs and therefore no summarization can take place at the routing domain boundary. When addresses are advertised by this routing domain to other routing domains, an enumerated list must be used consisting of the three area addresses. This situation is roughly analogous to the dissemination of routing information in the TCP/IP Internet prior to the introduction of CIDR. Areas correspond roughly to networks and area addresses to network numbers. The result of allowing areas within a routing domain to take their NSAPs from unrelated authorities is flat routing at the area address level. The number of address prefixes that subscriber routing domains would advertise is on the order of the number of attached areas; the number of prefixes a provider routing domain would advertise is approximately the number of areas attached to all
its subscriber routing domains. For "default-less" providers (i.e., those that don't use default routes) the size of the routing tables would be on the order of the number of area addresses globally. As the CLNP internet grows this would quickly become intractable. A greater degree of hierarchical information reduction is necessary to allow greater growth. 5.2. Administration at the Subscriber Routing Domain As mentioned previously, the greatest degree of data abstraction comes at the lowest levels of the hierarchy. Providing each subscriber routing domain (that is, site) with a unique prefix results in the biggest single increase in abstraction, with each subscriber domain assigning area addresses from its prefix. From outside the subscriber routing domain, the set of all addresses reachable in the domain can then be represented by a single prefix. As an example, assume a government agency has been assigned the AA value of zzz under ICD=0005. The agency then assigns a routing domain identifier to a routing domain under its administrative authority identifier, rrr. The resulting prefix for the routing domain is: AFI=47, IDI=0005, DFI=80h, AA=zzz, (Rsvd=0), RD=rrr. All areas within this routing domain would have area addresses comprising this prefix followed by an Area identifier. The prefix represents the summary of reachable addresses within the routing domain. There is a close relationship between areas and routing domains implicit in the fact that they operate a common routing protocol and are under the control of a single administration. The routing domain administration subdivides the domain into areas and structures a level 2 subdomain (i.e., a level 2 backbone) which provides connectivity among the areas. The routing domain represents the only path between an area and the rest of the internetwork. It is reasonable that this relationship also extend to include a common NSAP addressing authority. Thus, the areas within the subscriber RD should take their NSAPs from the prefix assigned to the subscriber RD.