Internet Draft Ross Callon DEC October 1992 Addressing and End Point Identification, For Use with TUBA Status of the Memo This document is an Internet Draft. 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 working 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''. Distribution of this memo is unlimited. Abstract Addressing is critically tied into routing and scaling in very large Internets. This draft paper discusses how NSAP addresses can be used to allow scaling in a huge Internet, and to allow the flexibility necessary to deal with multiple different dimensions of Internet growth. This document is a personal contribution of the author as an input to the IETF TUBA working group. 1 Summary The Internet is approaching a situation in which the current IP address space is no longer adequate for global addressing and routing. There is an urgent need to develop and deploy an approach to addressing and routing which solves these problems and allows scaling to several orders of magnitude larger than the existing Internet [1]. A companion paper [2] describes a simple proposal which provides a long-term solution to Internet addressing, routing, and scaling based on gradual migration from the current Internet Suite (which is based on Internet applications, running over TCP or UDP, running over IP) to an updated suite (based on the same Internet applications, running over TCP or UDP, running over CLNP [2]). This approach is known as "TUBA" (TCP & UDP with Bigger Addresses). This paper describes a proposal for how addressing and end point Expires 5/10/93 [Page 1] Internet Draft Addressing and EID for Use with TUBA Oct 1992 identification may be done with TUBA. This allows the ability to scale, as well as the flexibility to deal with multiple different dimensions of Internet growth. For example, the Internet may grow by creation of more backbones and regional networks along the current Internet model, by use of IP and/or CLNP service by large public carriers, and/or by provision of Internet services to a very large number of homes and/or small businesses over telephone networks or similar services. The main motivation of TUBA is to allow the Internet to scale to a size many orders of magnitude larger than the current Internet. In fact, it is important to be able to scale to as large an Internet as we can conceive may exist (for example, there may someday be a network and hundreds of hosts in every home in the world -- any proposed solution to Internet routing, addressing, and scaling should be capable of easily scaling to this size). The addressing proposal described in this paper makes use of the general scaling concepts described in NSAP Guidelines [reference], with flexibility for other address techniques also built in. Annex B provides a very rough description of how this proposal allows scaling beyond the largest anticipated size of the worldwide Internet. 2 Overview of OSI NSAPs - very flexible (some would say too flexible); binary string of variable length up to 20 byte maximum length; - NSAP is split into "Part which conforms to international standards" (IDP) and "rest" (DSP) - AFIs; first byte is AFI, indicates format for the part which conforms to international standards. A variety of AFIs are defined (more could easily be defined if anyone could think of a use for a new format). OSI standards allows for binary and decimal addresses. However, the decimal encodings are obsolete/useless and can be ignored. In practice, only binary representations make sense (and associated external representations, such as writing addresses in hexadecimal with or without separators for human readibility). Old version of standard places variable length restrictions based on AFI. However, this is based on obsolete requirement that addresses be capable of being represented in 40 decimal digits. Given that the decimal representation is obsolete, these length restrictions can be ignored, and have been removed from current versions of the standard. Thus only length restriction is that address has maximum size of 20 bytes (regardless of AFI). Expires 5/10/93 [Page 2] Internet Draft Addressing and EID for Use with TUBA Oct 1992 It is important to clarify what hosts can assume about addresses, what routers can assume, and how addresses are actually to be used. (see section xxx below). Addresses will need to have a lot of structure, but most of the structure will be used to allow address summarization (along boundaries which need to be configured) and administration. Thus most of structure is not visible to hosts and router implementations. There are multiple NSAP formats in use. However, routers need to think of NSAP addresses as a string of bits (or a string of nibbles -- half bytes), where forwarding is based on prefixes. Thus, routers don't know anything about any of the various formats, except perhaps for the configuration code, and knowledge of the size of the ID. Similarly, I would expect aggregation to require substantial manual configuration, such as manually configured summary addresses (surely a router is not going to *automatically* determine that it should aggregate, based on knowledge of the gosips). Thus, adding another format does not impact the router, except perhaps by causing more entries to get added to (or deleted from) the forwarding table. 3 Technical Considerations / Constraints 3.1 End Point Identification An address performs two functions: It identifies the system, and it specifies the location where the system is. The identification of source and destination systems may, for example, be used to demultiplex various network communications. The location of a system may be used as one input to the routing function (to determine how to get a packet delivered to the system). There are some situations in which it is preferable to perform these two functions independently: For example, if a system moves, then the identification of the system may stay the same, while the location of the system may change. Similarly, if the location of the system is specified hierarchically based on network topology (or based on the geographic location of a private network's attachment to a public service), then a change in network topology (or a change in where the public connection is made) may result in a change in the specification of the location of the system, even though the identity remains constant. Traditionally (for example, in the 32-bit IP address space) the functions of identification and location are intermingled, so that it is difficult or impossible to change one without changing the other. The current Internet protocol suite generally does not take advantage of the possibility of separating these two functions (ie, enhanced features of the Internet suite, such as mobile host support, had to be developed without consideration of Expires 5/10/93 [Page 3] Internet Draft Addressing and EID for Use with TUBA Oct 1992 the possibility of separating location and identification information). For this reason it is difficult to accurately predict precisely how valueable this separation will turn out to be. However, specification of the location and the identity of a host system are architecturally separate functions, and therefore it is felt that separation of these functions will turn out to be valuable. 3.2 NSAP Address Standard and Address Structure TUBA makes use of NSAP addresses which correspond to ISO standards. This includes the requirements of the NSAP address standard [reference], and routing protocols [reference ES-IS and IS-IS]. However, in order to allow the host identification to be separated from the location, the requirement (from IS-IS) that the ID be unique within the area is strengthened, to require that the ID must be globally unique. In order to emphasize that the ID globally identifies the end-point (ie, the conceptual virtual host which is the recipient of a CLNP packet), the globally unique ID will be referred to as the End-point IDentifier (EID). Also note that (in accordance with IS-IS) the last byte of the NSAP address is refered to as the Selector (SEL) and is used to demultiplex users of the CLNP service within a host. This therefore provides the same function as the Protocol field in the IP header. For TUBA, we will use values corresponding to the assigned Protocol values from assigned numbers for the Selector. This results in an address structure as follows: Tuba +-------------------+--------------------+----------+ Terms | Location | End-Point Id (EID) | Protocol | +-------------------+--------------------+----------+ variable length 6 bytes 1 byte <------------Network Entity Title--------> OSI <----Area Address---><--------ID---------><---SEL---> Terms <--IDP--><--HO-DSP--> Figure 1 - Basic Structure of TUBA Addresses The basic structure of TUBA addresses, and the correspondance between TUBA addresses and OSI addresses, is illustrated in figure 1. TUBA splits the addresses into Location, EIDs, and Protocol. Here the location identifies where a system is. The EID identifies the system. Finally the Protocol specifies what user protocol is operating above CLNP (i.e., specifies the protocol whose packets are included in the CLNP Data field). The OSI term "Network Entity Title" (NET) refers to the entire Expires 5/10/93 [Page 4] Internet Draft Addressing and EID for Use with TUBA Oct 1992 address, except for the Protocol field. The NET therefore performs the same function as a 32-bit IP address (except longer with more flexibility). The NET is therefore the entity which is returned by DNS name-to-address lookups (in much the same manner than IP DNS lookups return a 32-bit IP address). IS-IS uses the low order 7 bytes of the address as the identifier and selector. The rest of the address (all of the address except for the last 7 bytes) is known as the "area address", and specifies which area the system is in. Once the destination area is reached, IS-IS then routes directly to the destination host. The IS-IS term "area address" is therefore analoguous to the TUBA term "location", and specifies where the system is. [NOTE: TUBA requires use of CLNP and ES-IS. Other CLNP-related network layer protocols such as IS-IS are assumed to be used, but are not actually required. If, hypothetically, we were to define a new intra-domain protocol then the TUBA format will remain constant in the sense that the low-order 7 bytes will specify EID and Protocol, and the remaining high-order part of the address would specify the location. However, in this hypothetical case the location might not necessarily correspond to area (for example, if a new protocol routed to subnets, then the "location" field from the TUBA addresses may correspond to "subnet address" from a new routing protocol specification). This allows a graceful transition from IS-IS to a future intra-domain routing protocol, in the hypothetical case that this was required at some point in the future]. NSAP addresses used with TUBA must be valid OSI NSAP addresses. This implies that the first byte of the Location must be an AFI (authority and format identifier), which specifies the format of the remainder of the IDP (ie, for the high-order part of the location). Depending upon the value of the AFI, the location part of the address may vary from a minimum of one byte (containing only an AFI) to a maximum of 13 bytes. Thus the overall TUBA address may vary from a minimum of 8 bytes (which would contain only an AFI, EID, and Protocol field), to a maximum of 20 bytes. The TCP connection is identified by the EID and Protocol (as well as information carried in the transport level header). Thus the location part of the address is not required for unique identification of the host. However, a complete valid address is required in all packets. Thus, packet forwarding is based on the entire NSAP address, and in general is not based on solely the location nor on solely the EID. [Note: For normal operation with IS-IS and IDRP, the packet is forwarded based on location until the packet arrives at the destination area, and then forwarded based on EID to the destination host]. Future documentation will specify how a host (if it knows a priori the EID portion of its address) can autoconfigure the Expires 5/10/93 [Page 5] Internet Draft Addressing and EID for Use with TUBA Oct 1992 location part of the address. The same mechanism is also useful for updating the addresses assigned to a particular area or routing domain, by allowing auto-re-configuration of the location part of the address. This is important to allow addresses to be changed when necessary (in the current Internet architecture changing addresses is just too hard). Note, these mechanisms will be based on the address autoconfiguration work done for CLNP, with additional TUBA-specific features (for example, to deal with mobile hosts, to allow TCP connections to remain in operation undisturbed through address changes, etc), The TUBA-specific mechanisms are straightforward, but have not yet been written down in detail due to time constraints. It is necessary to be able to map from EID to name. This is analoguous to the mapping from 32-bit IP address to name in the current Internet architecture. EIDs therefore must be administered in a manner which facilitates this mapping. In addition, EID assignments must be global, and must conform to Internet requirements (TBD). Initial proposal is described in Annex A. 3.3 Addressing and Scaling The primary motivation for TUBA is to allow scaling of the Internet architecture to a truely enormous worldwide ubiquitous Internet. This requires that addresses used with TUBA be assigned in a manner which facilitates scaling. The current IP addressing scheme assigns one or more "network numbers" to each customer. There are two immediate problems with this approach: a)The Internet is running out of some types of addresses (particularly, class B network numbers). b)Internet routing tables (and routing protocols) require a separate entry for every customer (ie, for each network number). As the internet grows, this implies that the growth in routing tables and routing protocol information grows at least linearly with the number of customers. The first of these problems is largely a matter of ensuring that the address space (including any hierarchical subdivision of the address space) is large enough so that you don't run out of addresses to assign. This implies that one needs to be very careful when subdividing and address space, but does not appear to be a significant problem for the NSAP address space due to the large number of addresses available. Expires 5/10/93 [Page 6] Internet Draft Addressing and EID for Use with TUBA Oct 1992 The second of these problems require much more care. There are several proposals for how to deal with growth of addressing information: a)Massive Resources This approach attempts to deal directly with one or more separate routes for each Internet customer. In the future this potentially will require massive routing tables, massive CPU and memory in routers, and some (unspecified) management tools to make management of the associated information feasible. b)Provider Based Addresses This approach makes use of addresses for customer networks which are based on prefixes assigned by provider. Thus, any one particular public service provider would obtain a large block of the address space based on a single prefix from a national or international address authority. Each provider would then allocate a part of this address space (based on a longer prefix) to each customer. This is the approach recommended by RFC 1347. c)Provider-Subnet Addresses This approach is not intended for general use by all networks, but rather is intended to deal with one important special case. In particular, in some situations it is necessary to deal with very large numbers of individual systems or small sites connected via telephone networks, public data networks, ISDN, or other public service. For example, such situations may occur in retail sales and home applications. In general, telephone networks, public data networks, and similar networks have their own globally significant address space. In these cases, it will be necessary to map from the global internet address space to the subnet address space used by the provider. This is facilitated with TUBA by allowing such "provider-subnet" addresses to be embedded as part of the "location" field in the TUBA NSAP address. Provider-subnet addresses are considered important enough that they are discussed separately in section 3.4 below. d)Geographic Addresses This approach assigns addresses to customer networks based on the geographic area of their attachment to a public service provider. This approach requires considerable cooperation between public service providers. In particular, it requires that a metro-area be fully connected, (i.e., either once a packet is delivered to any point in a metro area, it can reach any other point in the same metro without leaving the metro, or special mechanisms such as encapsulation are used to allow Expires 5/10/93 [Page 7] Internet Draft Addressing and EID for Use with TUBA Oct 1992 the packet to be delivered between different providers in the same metro area via intermediate networks). The topology constraint associated with geographic addressing is just a specific case of the general requirement/assumption of any hierarchical routing scheme: that each region, sub-region, sub-sub-region, etc. be fully connected. There is an analogous case with provider-based addressing: A provider's facilities must be fully connected if they are to be identified by a single prefix. (Note, this is not an absolute requirement -- you can use tricks like tunneling to link together the pieces of a partitioned region. IS-IS can do that to heal partitioned Level 1 Areas, and the various mobile IP schemes do something similar to allow members of a subnet to roam to arbitrary places in the graph.) Provider-based addressing and geographic addressing are not necessarily mutually exclusive. Suppose that some providers rely on provider-based addresses (implying that customers of this provider are required to take addresses from that provider's space), and other providers make use of geographic addressing. In this case, those providers which use geographic addressing are required to cooperate and exchange traffic between them, but will have the offsetting advantage that they can advertise "open" addressing (ie, addressing which does not lock the customer into a single provider). TUBA does not require any particular solution to the hierarchical routing issue. Any combination of Provider based addressing, Geographic addressing, and Provider-Subnet addressing is permitted with TUBA. 3.4 Provider-Subnet Addressing to Homes and Small Sites Imagine a situation in which the financial services department of XYZ corporation has placed point-of-sale terminals in 100,000 small retail stores (we might presume that the stores are independently-owned, and that XYZ corporation has contracted to provide a service to the stores). Alternatively, imagine a situation in which XYZ entertainment corporation has placed entertainment devices in 100,000 homes. In either cases, let's suppose that access from the central offices of XYZ corporation to the 100,000 individual sites is done over the public telephone network, and that the applications running from XYZ to the sites is done using Internet applications running over TUBA. In this case, it will be necessary to assign Expires 5/10/93 [Page 8] Internet Draft Addressing and EID for Use with TUBA Oct 1992 NSAP addresses to each of the individual sites, and to facilitate routing between XYZ corporation and the individual sites. With the existing IP architecture, this problem is very hard to solve. It becomes necessary to map from the 32-bit IP address space to the "subnet point of attachment (SNPA) addresses" (ie, phone numbers) used in each customer site. With IP, this requires a very large mapping table, which is either difficult or impossible to manage. With TUBA, this problem is solved by embedding the SNPA address in the location part of the NSAP address. This is facilitated by defining a separate AFI for each commonly used type of SNPA address. For example, in the telephone case the NSAP/TUBA address would be as follows: In this case the AFI is 1 byte long, the telephone number is variable length (padded to a constant length of xx bytes, corresponding to the maximum length of worldwide telephone numbers), the EID is 6 bytes long, and the protocol is 1 byte long. Note that with this approach, rather than requiring a mapping table with 100,000 entries, only a single entry is needed in routing tables. This entry would route packets destined to the appropriate type of address to one or more routers with interfaces on the public telephone network. The routers attached to the telephone network would then be able to obtain the correct subnet address (ie, telephone number) by extracting it from the NSAP address. If a finer grained control was required (for example, routing traffic separately based on country, or based on area code), then this would be easy to do by using prefixes applied to the telephone number. This is facilitated since the telephone number space is globally meaningful, and is assigned in a manner which corresponds to the global topology of the telephone network. A similar approach can be used for public networks using other common address formats. AFI values have been assigned for telex numbers, telephone numbers, X.121 addresses, and E.164 addresses (used by ISDN and some other public networks). 3.5 Compatibility with Current CLNP deployment TUBA is based on the use of CLNP as a scalable network layer for use with existing Internet applications. However, it must be realized that CLNP will also be used for other purposes. For example, some OSI applications have been deployed which make use of the services provided by CLNP. Similarly, some proprietary applications have also been deployed which make use of CLNP. Expires 5/10/93 [Page 9] Internet Draft Addressing and EID for Use with TUBA Oct 1992 It is therefore desireable (although not absolutely necessary) to allow a common address format be used for TUBA, and for other uses of CLNP. The use of a common address format will simplify network configuration, management, and operation. The identifiers used with TUBA must be compatible with the identifiers used with other CLNP applications, in the sense that the same ID cannot be assigned for one host for use with TUBA and to another host in the same area for use with OSI applications. Use of common identifiers is also somewhat useful but is not as important. For example, if TUBA makes use of one format for identifiers, and OSI applications make use of a different format, then multi-protocol hosts will have to have two different identifiers assigned to them. However, the requirement that the identifiers used with TUBA must be capable of being used as the index for a DNS identifier-to-name lookup constrains the form of identifier used with TUBA. Generally, current CLNP applications (including OSI and proprietary applications) make use of two common methods for assigning IDs: Some systems use IEEE 48-bit globally administered unicast IDs, Some use manual configuration of IDs. The latter are not a problem (locally administered IDs for use with OSI applications can be chosen for compatibility with TUBA). However, given that some systems are already using IEEE IDs, we have two choices: (i) Use globally administered unicast IEEE IDs; or (ii) Avoid the 25% of the 48 bit ID space which happens to correspond to the IEEE globally administered unicast IDs. Given our desire to make ID to name lookups easy, we propose to use the latter approach: All IDs assigned for use with TUBA will use a prefix which avoids collision with the IEEE globally administered space. The current practice in assignment of NSAP addresses is somewhat more complex (ie, different formats are being used in different situations, and some customer networks are uncertain as to which NSAP format would be the best to use). However there is a strong trend towards use of NSAP addresses which are chosen to allow scaling. In particular, the current trend is towards use of provider-based addresses assigned more-or-less in conformance with RFC 1237. Also, existing NSAP allocations make use of a variety of address lengths, but use a consistent 6 byte ID. The current practice is therefore compatible with TUBA addressing requirements specified in this document. Expires 5/10/93 [Page 10] Internet Draft Addressing and EID for Use with TUBA Oct 1992 4 Proposed Address Solution 4.1 What Hosts can Assume about Addresses - The NSAP address is split into Location (variable length), EID (6 bytes), Protocol (1 byte) - Location should be treated as flat variable length binary string (in fact will have structure, but structure is not visible to host) - EID is six byte globally unique identifier. TUBA host can assume that this will always be globally unique, and will identify the other system. DNS will be able to look up name based on EID. However, host cannot make any assumptions about the internal contents of the ID. - A single host can have multiple values for the location part of the address. It is possible that some future specifications might allow what constitutes a correct location part of the address for any one host to vary over time. - Logically a host only has one correct value for the EID. Thus, if a real physical host has multiple EIDs assigned to it, it is treated as if it were multiple logical hosts. If the EID changes, then logically you have a different host. - Protocol field uses same values as IP. Host uses value in destination address. The value in source address MUST be ignored. 4.2 What Routers can Assume about TUBA Addresses - The NSAP address is split into Location (variable length), EID (6 bytes), Protocol (1 byte) - Routing is in accordance with other standards - For initial use, using existing CLNP-associated routing protocols such as ES-IS, IS-IS and IDRP - These use prefixes on location part, on "nibble" boundaries, plus ID in destination area - For forwarding loop: Router SHOULD NOT be aware of internal structure of location part of address, except for matching prefixes to location part of address - Note: During transition period EID will contain IP address. This could potentially be used for router-visible transition methods such as packet translation details outside of the scope of this document. - Router ignores Protocol (as required by IS-IS and IDRP) - Expires 5/10/93 [Page 11] Internet Draft Addressing and EID for Use with TUBA Oct 1992 4.3 Configuration of NSAP Addresses Hosts, routers, name servers, and other TUBA systems MUST allow configuration of NSAPs as a simple hexadecimal string without consideration of internal structure. Systems MAY also allow configuration in other ways (e.g., systems may allow the option of checking to see if a valid AFI is provided, and/or allow the IDP to be entered in a format which is AFI dependent). However, in order to conform with the TUBA proposal it MUST be possible to override this and enter NSAPs as simple hexadecimal strings. NSAPs may be input as simple hexadecimal strings. Different sub-fields in the NSAP may be separated by dots, but the dots are optionally included only for ease of writing down the NSAP, and do not have semantic meaning (i.e., the dots are ignored by address parsers). The user can put them wherever he/she wants in a configuration file (and they can be inserted in any position on output). For example the following NSAP Addresses are all equivalent: 47000580FFEC00000000000010000080F1005100 47.0005.80FF.EC00.0000.0000.0010.0000.80F1.0051.00 47.0005.80.FFEC00.0000.0000.0010.000080F10051.00 The latter grouping uses the location of dots to group bytes according to administrative fields. In either case, the placement of the dots has no significance other than readability. 4.4 What Address Solution Will be Used Currently multiple things in use, will converge over time Depends upon situation, can use combination of provider based, geographic, or provider-subnet address based. For geographic base, use different DFI, split rest differently For subnet-provider-address-based, use X.121 (or...) format 5 References [1] Overview of ROAD problem (ROAD report or IESG report) Expires 5/10/93 [Page 12] Internet Draft Addressing and EID for Use with TUBA Oct 1992 [2] RFC 1347, "TCU and UDP with Bigger Addresses (TUBA), a Proposal for... [3] RFC 1348, and/or its replacement [4] NSAP Guidelines [5] Dave Piscitello's TUBA CLNP Profile [6] "Protocol for Providing the Connectionless-Mode Network Service", ISO 8473, 1988. [7] "Supernetting: An Address Assignment and Aggregation Strategy", V.Fuller, T.Li, J.Yu, and K.Varadhan, Mar 1992. [8] IP Address Guidelines paper [9] Steve Deering's Geographic paper [10] "Extending the IP Internet Through Address Reuse", Paul Tsuchiya, December 1991. 6 Security Considerations Security issues are not discussed in this memo. 7 Author's Address Ross Callon Digital Equipment Corporation 550 King Street, LKG 1-2/A19 Littleton, MA 01460-1289 Phone: 508-486-5009 Email: Callon@bigfut.lkg.dec.com Annex A A Draft Proposal for EID Assignments A.1 Constraints A.2 Proposal For initial use: - Fixed 16-bit prefix prepended to IP address - Prefix chosen to not collide with IDs selected from IEEE Expires 5/10/93 [Page 13] Internet Draft Addressing and EID for Use with TUBA Oct 1992 globally administered space For future use: - Administered by IANA - Details for further study Annex B A Rough Analysis of NSAP Scaling We know that the Internet will grow a lot, but we don't know how the Internet will grow. In particular, we don't know what the topology will look like. For example, if the Internet reaches every home in North America and Europe, how will this public Internet service be provided? Will there be one large public service provider per country, or many smaller providers? If there are many public service providers in each country, how will the providers interconnect? How many providers will there be worldwide and how large will they be? Will the bulk of systems connected to the Internet use "public service provider specific" addresses such as X.121, E.164, or telephone numbers? This uncertainty about the manner in which the Internet topology will grow leads to a resulting difficulty in determining what future Internet addressing should look like, and in accurately predicting how any particular addressing plan will scale. Fortunately, the NSAP address scheme used with TUBA provides a great deal of flexibility in how addresses are structured. Also, as discussed in section 4, TUBA-capable hosts are required to make no assumption about the substructure of the location field of the NSAP addresses, and routers similarly should make only very limited assumptions about the location field. This implies that the substructure can be changed (or different structures for the location field used in different parts of the Internet) without effecting existing equipment. Given this flexibility in NSAP address structure and uncertainly in network topology design, it is difficult to accurately predict precisely how addresses will scale. However, we can give rough "back of the envelope" calculations for several different scenarios. B.1 Scaling of Provider-Based Addressing It is proposed that provider based addresses basically look like: * NOTE: By "country", we really mean country or geographic area. For example, multi-country continental networks (such as a European wide backbone) would specify continent in this field, rather than country. Expires 5/10/93 [Page 14] Internet Draft Addressing and EID for Use with TUBA Oct 1992 ** NOTE: The "substructure" field is needed because eventually we will either end up with too many providers in order to route on a flat provider space (in one country), or, more likely, end up with too many customers of a single provider in a single country. For example, given more than 10,000,000 companies in the USA, and roughly 100,000,000 homes in the USA, it is likely that eventually there will be one or more providers in the USA which have enough customers to require hierarchical routing between customers of the same provider. This "substructure" field is referred to as "reserved" in the US GOSIP and ANSI address spaces, since initially (so long as the number of providers within a country, and the number of customers of any one provider is small), the "substructure" field does not need to be used. Note that the some of these subfields in the Provider-based addressing will actually be further subdivided into several sub-sub-fields. For example, the country will be specified using the combination of an AFI (authority and format identifier -- the first byte of the NSAP giving the format of the next field) and DCC (data country code) or ICD (international code designator). Some NSAP format provide a single byte after the country to indicate the type of the rest of the address (for example, this byte will specify whether the address is provider-based or geographic-based). For example, with US GOSIP based addressing, the approximate mapping is as follows: My Term GOSIP Field (for rough analysis) term size Country AFI and ICD 3 bytes (not mentioned) DFI 1 byte Provider AA 3 bytes substructure reserved 2 bytes customer RD 2 bytes area area 2 bytes EID ID 6 bytes (not mentioned) Protocol/SEL 1 byte Note that the DFI (DSP Format Identifier) in the GOSIP space can be used to identify different address formats, such as the provider based format (as illustrated above) versus a geographic format. The selector/Protocol field is provided by the GOSIP format (and required for TUBA addressing), but is not considered for purposed of analysis of scaling because the Protocol/Selector Expires 5/10/93 [Page 15] Internet Draft Addressing and EID for Use with TUBA Oct 1992 field is only used for demultiplexing within a host, and is therefore not useful for scaling to a large number of hosts. Initially, we can probably treat the country and provider as a flat field which specifies the provider. Assuming that dynamic routing in a flat address space allows for roughly up to 10,000 entries at one level (noting that the phone system seems to manage with this size, and that the Internet also is managing routing in a flat space with several thousand network numbers). Our guess is that this may be sufficient indefinitely (there may never be more than 10,000 providers). If this guess is wrong and the number of providers gets large enough that it is not possible to route amongst providers on a flat basis, then we will need to route hierarchically amongst providers. However, provider identifiers are in fact being handed out geographically, based on country (or at least continent, in the case of multinational nets). Thus, if we needed to, we could first route on country, then on provider, without changing the current address assignments. In practice, if the number of public service providers worldwide gets to be substantially larger than roughly 10,000, then most likely there will be some "major" providers, which will continue to be advertised globally in routing advertisement and tables, as well as some "minor" providers, which can be routed on a per-country basis (i.e., routes to the minor providers will only be maintained within their country of operation). The RD field allows up to about 10,000 customers per provider (again, routed on a flat basis; if fact, more than 10,000 entries are possible, but we are assuming that 10,000 is a reasonable "order of magnitude" estimate of the comfortable maximum size of a routing table). Let's suppose that we end up with something like 100 providers in the US (it might be larger, but this number is a sort of "today's guess"). Given that there are millions of companies in the US (most very small), it would appear inevitable that if we assign value for "customer" to each company (even small ones), then we are eventually going to get more than 10,000 customers for a single provider. Thus there is the substruture field sitting there waiting in just the right spot to allow a single provider to hierarchically subdivide the addresses under it. The Area, and EID fields are used for routing within a company / campus. For a large company we might have a few hundred areas. If we needed to, we could have a few thousand (the routing algorithms could handle this, but it is dubious that there will be many companies large enough to need it). Each area could have up to a few thousand end systems. A rough upper bound of the size that can be handled by this scheme can be obtained by multipling together the maximum size at Expires 5/10/93 [Page 16] Internet Draft Addressing and EID for Use with TUBA Oct 1992 each level. Without using the substructure (reserved) field, and assuming that we would prefer to use flat routing of providers worldwide, we get 10,000 providers (worldwide) with 10,000 customers each with 100 areas per customer with 1000 hosts per area. This implies about 10**8 customers with about 10**13 hosts. If we ignore homes, then this is about the anticipated maximum size of the Internet. However, note that we will probably never actually be able to reach the "upper bound" size, since it is nearly impossible to completely fill in every level of a hierarchical address without having some parts of the address space become exhausted (ie, we will probably end up having to use the reserved field). If some companies have more than 100 areas that is fine (we could easily go much larger). If we end up with more than 10,000 providers then again this is fine, since there is the option of routing by country/continent first, or of subdividing the providers within a country by using the "sustructure" field. If we end up with fewer providers and more customers per provider, then we will need to use the reserved field to allow hierarchical subdivision of the customers of a provider, this would potentially allow several million customers of each provider, each customer able to have well over 100,000 hosts (again, each customer could have up to several thousand areas and several thousand hosts per area). We can similarly put together an upper bound with use of the reserved field. We might assume that we are unlikely to get more than 10,000 major providers worldwide. Thus, although the NSAP address scheme allows for more than this number, it is not likely to actually be used (except perhaps for a number of smaller providers). If we assume 10,000 providers worldwide, with 10,000,000 customers (router hierarchically within each provider using the "substructure" field, and noteing that the NSAP structure could actually handle more than this -- we just don't expect any one provider to require more than this), then we come up with a rough upper bound of 10**11 customers, each with up to several thousand areas, and several thousand hosts per area. Note however that this bound is much larger than the number of potential sites which exist which could want to attach to the Internet, unless we consider individual homes. B.2 Provider/Geographic Based Addresses to Individual Homes Routing to individual homes is also well handled. Given that each home is located in a small geographic location, each provider would probably arrange its provider network geographically, use the RD field (or perhaps the reserved field) geographically, and then assign a single area to each house in a geographic area (assuming that we have no more than a few thousand hosts within a single house). This would allow 10,000 geographic areas per provider (using the RD field) and 10,000 houses per geographic Expires 5/10/93 [Page 17] Internet Draft Addressing and EID for Use with TUBA Oct 1992 area (using the area field), or a maximum of about 100,000,000 houses per provider. If there is a single provider serving a country which has more than 100,000 houses (perhaps the Chinese monopoly PTT), then they will to use the reserved field and arrange the Chinese PTT itself in a hierarchical way, allowing 10,000 top-level things (using the Reverved field), 10,000 next level things (using the RD field), and 10,000 houses per thing (using area field). Thus the Chinese PTT, if it really needed to, could hand out 10**12 addresses to 10**12 houses within China, with each house having a thousand computers in it. Note, in this example, it is possible that the Chinese PTT might not choose to route CLNP directly, but rather might offer simple telephone service or ISDN service to each home. In this case, provider-subnet addresses would be used, as was discussed earlier in section 3.4. B.3 Scaling of Geographic Addressing B.4 Summary It is hard to anticipate exactly how much fan-out will exist at each level of the hierarchy because we still don't know exactly what providers will exist and how many customers each will have. However, the NSAP address space with the ANSI/GOSIP address structure allows plenty of room and flexibility and scales well beyond the current size of the world. Expires 5/10/93 [Page 18]