To: Lixia Zhang Cc: deering@parc.xerox.com Subject: Re: your geographic addressing paper In-reply-to: lixia's message of Sat, 21 Jan 95 17:30:12 -0800. Date: Sun, 22 Jan 1995 11:34:18 -0800 Sender: Steve Deering From: Steve Deering Message-Id: <95Jan22.113426pst.12174@skylark.parc.xerox.com> Lixia, Here's the draft geographical addressing paper I submitted to the ROAD group (back when I actually thought we were going to end up with NSAPs!), plus a follow-up messages to clarify a few things. Since then, my thinking has evolved on some of the details, and the terminology has been changed several times, but it captures the basic ideas. ----------- To: road@lanl.gov, peter@goshawk.lanl.gov, swb@nr-tech.cit.cornell.edu, lyman@bbn.com Subject: very rough paper on city code addressing and routing Date: Wed, 8 Jan 1992 04:14:19 -0800 From: Steve Deering Well, here is a start at trying to write up my idea for area code routing (now called "city codes", 'cuz IS-IS has usurped the word "area"). I hope someone sees this message and prints of a few copies for interested folks at the meeting today. I also hope expectations for this have not been too inflated -- I'm really not sure if it's applicable to any part of ROAD's mission, or even if it works. Sorry about the turgid prose; it's such a simple idea, but I have an awfully hard time expressing it in text (much easier standing at a whiteboard...)... City Codes: An Alternative Scheme for OSI NSAP Allocation in the Internet Stephen Deering Xerox Palo Alto Research Center January 7, 1992 INCOMPLETE, WORKING DRAFT -- PLEASE DO NOT DISTRIBUTE. [Author's notes to himself are enclosed in square brackets.] 1 Introduction We propose a scheme for allocating OSI NSAP addresses (``NSAPs'', for short) for use in the Internet, as an alternative to the scheme recommended in RFC-1237 [Colella et al.]. The essence of our scheme is that the NSAPs allocated to a particular ``leaf'' routing domain, such as a campus, a corporate site, or a personal residence, have a prefix which identifies the country and city in or near which the leaf domain attaches to a transit routing domain, such as a regional or wide-area network. Such NSAPs are similar to plain old telephone numbers, which start with country and city codes (or ``area codes'' in North America; we forgo the ``area'' terminology to avoid confusion with the previous use of that word in OSI routing protocols). Unlike the current practice in the telephone system, however, we allow more than one ``carrier'' to offer transit delivery service into, out of, and within the geographic scope of a single city code. NSAPs based on city codes identify where leaf domains obtain their transit service; they do not identify the carriers providing the service. The city code scheme achieves the same goal as RFC-1237: it eliminates the need for wide-area routing domains, such as national and international backbones, to maintain and distribute routing information about large numbers of leaf domains. Wide-area routing is based simply on country and city codes. The main advantage of the city code scheme over RFC-1237 is that a leaf domain may be switched from one transit provider to another, or may be attached to a transit provider for the first time, without changing its NSAPs---provided that the new attachment point is within the geographic scope of the same city code. This is not true of the RFC-1237 scheme, since it requires that most leaf domains acquire their NSAPs out of a block belonging to currently-attached transit provider. Thus, using city codes, a leaf domain is not ``locked-in'' to its current transit provider; it can be switched to whichever provider offers the most desirable service without the burden of reconfiguring all internal hosts and routers (only part of which might yield to automated procedures) and without a lengthy transition period during which two providers may have to be paid. City codes also handle some ``multi-homed'' leaf domains, that is, leaf domains attached to more than one public transit service, more gracefully than the RFC-1237 approach. 2 Proposed NSAP Structure We propose that NSAPs for a leaf domain be structured as follows: where: is a numeric code identifying the country in which the leaf domain attaches to a transit service. It is not strictly necessary that country codes be one-to-one with countries. A single code may identify a contiguous set of countries (perhaps arising from the break-up of a larger country, like the U.S.S.R. or Canada). A single country may also have more than one country code (perhaps arising from the merger of several independent countries, like East and West Germany, or the wider European Community). And a country code may be assigned to a non-country, like Antarctica or the Moon. is a numeric code identifying the geographical region within a country, typically centered on a major metropolitan area (unless it happens to be Antarctica or the Moon!), in which the leaf domain attaches to a transit service. A country would not be expected to have more than a couple hundred city codes. Unlike telephone area codes, a single large city would not be partitioned into multiple, non-overlapping city codes, although it would be permissible for two city codes to overlap, geographically. is a numeric code identifying the particular leaf domain within the city of the attachment point. Every leaf domain in a city has a unique domain ID, independent of the transit provider. Strategies for allocating domain IDs are discussed below. is the part of the NSAP upon which the leaf domain performs its internal routing. In the case of a leaf domain using DIS10589 (the IS-IS intra-domain routing protocol), the intra-domain part would consist of the Area ID, System ID, and NSAP Selector subfields. There are a variety of ways of encoding this structure within an NSAP. A simple encoding scheme, similar to the ANSI proposal described in RFC-1237, would be as follows: 1 octet AFI = 39 2 octet Country Code (ISO DCC) 1 octet DFI = 2 (to identify this particular format) 1 octet Reserved (for possible growth of the city code field) 1 octet City Code (allows up to 256 cities per country) 2 octet Reserved (for possible growth of the domain ID field) 3 octet Domain ID (allows up to 16 million leaf domains per city) 2 octet Area ID 6 octet System ID 1 octet NSAP Selector -- 20 octets total [I wonder if there any possibility of shoehorning a version of this scheme, with more carefully-crafted subfields, into the IP Class A address space, to extend the useful life of IP?] 3 Routing through Transit Domains We first consider the case of ``public'' transit routing domains that offer to deliver packets anywhere in the ``global internet''. Such routing domains do not themselves reach everywhere---they may span only a single metropolitan area or multiple cities, in one country or in multiple countries---but through bilateral and multilateral agreements with other transit domains (such as national and international backbones and various regional and metropolitan networks), they are able to offer universal delivery service. It is this set of interconnected, public transit domains that may be said to define the ``global internet''. Under the city code scheme, each router in such a transit domain must maintain routing table entries to enable it to reach any city in the global internet. Those entries may consist of interior routes to cities or countries directly reachable within the domain, obtained through the operation of a conventional intra-domain routing protocol, and exterior routes to specific cities, to specific countries (with the city unspecified), and to ``default'' countries, injected at the domain's boundary routers by static configuration or an inter-domain routing protocol. The number of such inter-city route entries in any one router is expected to be manageably small. For a single-city regional, it may be just a single ``default'' entry, pointing to a wide-area backbone. For a larger regional, there will be entries for each of the cities served by that regional, plus zero or more country routes, plus a default. National backbones will probably have routes to all cities within one country, and international backbones will probably have routes to all countries. If by nothing else, the number of such entries is bounded by the total number of cities in the world. [I wonder how many there are?] A packet is routed towards its destination city via the inter-city route entries, using the conventional ``longest-match'' algorithm to choose a city-specific route over a country-only route. Once the packet reaches a router in the destination city, further routing is done using the domain ID field. The router at which the packet arrives in the destination city may or may not belong to a transit domain that is directly serving the destination leaf domain. If it does, it will have a internal route for the given domain ID. If it does not, the router must have some other information that will allow it to forward the packet to a transit domain that does directly serve the destination. [Here's comes the interesting bit, at last. Hope it makes sense.] In order for a packet to get shuttled to the right transit domain in the destination city, all of the domains serving a single city must be connected to each other, either directly or indirectly (through some other transit service), and they must exchange information about which transit domains serve which leaf domains. The simplest way to exchange that information is simply to have each transit domain export all of its leaf domain routes to all of the other transitdomains serving the same city; that should suffice for cities with only a few hundred leaf domains. However, we may expect the number of leaf domains in a city eventually to grow into the millions (when, someday, every telephone is replaced by a router). For large numbers of leaf domains, more efficient information exchange is possible: once a day, say, each transit domain could simply send a list of all of the leaf domain IDs it serves to each of its neighboring domains. The routers would then concatenate the lists from all of the domains, and use the resulting list as an indirection table for routing packets within the city: the domain ID of a packet's destination would first be looked up in the indirection table to find out who serves that ID, and then the routing table would be consulted to determine how to reach the serving domain. If the memory cost of storing the indirection table becomes prohibitive, it could reasonably be stored on disk, with only the recently-referenced domain IDs being cached in memory. (The once a day exchange rate implies that it would take at most one day for a leaf domain to start receiving service from a new transit domain.) The storage required for the list of domain IDs could be further reduced by imposing some sub-structure on domain IDs, assuming that most leaf domains will not, in fact, ever switch from their initial transit domain to some other transit domain. If that should be the case, then it would be reasonable to hand out blocks of domain IDs to each transit domain serving a city, structured as follows: where identifies the transit domain within the city, and is simply incremented each time a new leaf domain ID is to be assigned by that transit domain. A leaf domain would obtain a domain ID of that form from the first transit domain to which it connected. If the leaf domain later switched to another transit, it would still keep the same domain ID, but it would report that ID to its new transit domain. Then, each transit domain would only have to inform its neighbors of these ``exceptions'' (i.e., leaf domains whose domain ID's field did not match their current transit provider), rather than complete lists of all served leaf domains. For ``semi-private'' transit domains, such as wide-area networks constrained to serving a limited clientele, routing could be performed on full prefixes, treating them as a flat field. Alternatively, a semi-private domain could take advantage of the city code structure to achieve the same scalability benefits as the public transit domains. The only difference would be that, in the semi-private case, if a packet arrives in its destination city and the router there does not have an interior route to the destination leaf domain, the router would simply drop the packet, it being addressed to an unauthorized destination. 4 Routing in Leaf Domains Within a leaf domain, routing is normally performed using the NSAP fields that follow the domain ID. If a leaf domain attaches to more than one transit domain in the same city, it need not obtain multiple NSAP allocations; packets with the same destination NSAP may arrive via any of the attached transit domains. (The leaf domain may control which transit domain it uses for outgoing traffic, based on the source and destination addresses of the traffic, quality-of-service fields, time-of-day, or any other information at hand, similar to the way modern office PBX systems select carriers for off-site calls. The choice of transit domain for incoming traffic, however, is under the control of the source leaf domain and all of the intermediate transit domains. [Should I mention the possibility of explicitly allocating multiple NSAP blocks with different domain IDs for a multi-home domain, in order to control incoming traffic via the addresses that are handed out to communicants?]). A leaf domain may itself span multiple cities, or multiple countries. An example is a large private corporate internet interconnecting many branch offices. If such a domain attached to the ``public'' internet in only one place, the NSAPs for all of the company's systems (or at least all systems with external access privileges) would contain the city code for the attachment point, regardless of where the systems themselves were located. If the corporate domain were attached to the public internet in more than one place, it would be reasonable for the systems inside the corporation to take their NSAPs from their nearest point of attachment, as discussed in RFC-1237. This would mean the use of multiple NSAP prefixes (country, city, and domain IDs) within the single corporate domain. The intra-domain routing protocol could be configured to know about the specific prefixes belonging to the company, in order to keep intra-company traffic inside the corporate internet. The country and city structure of those NSAPs could be exploited for their scalability benefits by the corporate routers. Alternatively, the company could use an entirely separate NSAP address space for its systems, in addition to the NSAPs obtained from any public attachment points, similar to the way telephones in some large corporations may be ``addressed'' by both a normal, public phone number, and a number belonging to the corporation's own private phone system. One advantage of assigning both interior and exterior addresses to the company's systems might to allow the exterior addresses and public connectivity to be used for intra-company communication if the corporate internet should partition. 5 When NSAPs Change Under the city code scheme, there are still occasions when it is necessary for a leaf domain to change some or all of its NSAPs. For example, if a small company moves to a new city and attaches its routing domain there, that domain will have to use new NSAPs. However, such moves also entail changes of phone numbers, fax numbers, postal addresses, etc., so the change of NSAPs would not be unexpected or unreasonable. If a company with a wide-area private internet adds a new attachment point to the public internet, it is necessary to assign new NSAPs to some of the company's systems if it is desired that those systems receive packets via the new attachment point. However, the new addresses may be introduced gradually, and use of the old addresses may be allowed to continue for an indefinite transition period. Finally, if the country or city code of an attachment point should happen to change, say, by annexation of the city by a hostile neighboring country, leaf domain NSAPs would have to change. That would probably be the least of the worries. [Should add some discussion of ``800 numbers'', mobile hosts, and multicast. Nothing surprising.] References [Colella et al.] Colella R., Gardner E., and Callon, R. Guidelines for OSI NSAP Allocation in the Internet. RFC-1237, Network Working Group, July 1991. -------------- To: road@lanl.gov Subject: City Codes Date: Fri, 10 Jan 1992 17:51:33 -0800 From: Steve Deering Roadies, I talked to Scott this morning, and he said you didn't get a chance to discuss my proposal for city code addressing/routing. He did, however, mention a few comments people had made concerning my proposal (but he did not attribute the comments to particular individuals). This is a response to those comments, second-hand though they were and strawmen though they may be. (I know there are far more pressing issues than this on the road agenda, so feel free to ignore it if it's getting in the way of the real work.) Comment: This is nothing new. Response: Absolutely right. The Phone Company has been doing city-code routing forever. But for some reason it has never been adopted in the Internet. In one or two IETF NSAP working group meetings, and in several email exchanges regarding address allocation for scalable routing, I have made a nuisance of myself by saying, "Obviously, you should assign addresses geographically!", in response to which someone (usually Ross Callon) would rightly ask, "What do you mean when you say geographically?", and I would fail to follow through, leaving people to think (if they cared at all) that I was talking about cartesian routing or something. So the draft paper I sent was my first attempt to explain in writing what I meant. I claim no originality -- it just seems like the obvious way to do global address allocation, if you want scalable global routing, and it seems like it would work pretty well. Comment: This is just another way to allocate NSAPs. Response: Exactly. But as Noel keeps reminding us, address allocation should not be done in a vacuum, without consideration of its impact on routing, management, etc. I contend that the NSAP allocation method recommended in RFC-1237 has negative consequences in the managment area that can easily be avoided, in particular, the address management cost to the leaf domains of subscribing to a new transit service provider. My scheme requires a bit more coordination between providers operating in the same city, but that seems a small price to pay to save the customers >From a lot of hassle and to ensure unhindered competition in the transit service business. Sprint, MCI, and the like may never have gotten off the ground if it had been necessary to change one's phone number to receive calls via those carriers. Comment: This scheme requires all transit service providers in a city to connect to the same POP, and they will never agree to that! Response: That's not the case. All they need is an Internet path to each other, and they must already have such a path if they are purporting to offer public internet service. After all, a provider is not going to get very many customers if it cannot provide delivery to and from the customers of other providers in the same city. Given that the providers have some way to inter-communicate, my scheme requires that they exchange information among themselves. It is in their customers' interest that the providers advertise to each other their lists of attached leaf domains, because that allows the those leaf domains to receive packets, regardless of where the packets originate. A couple more observations on the city code scheme: - The memory cost, per router, of supporting a million leaf domains in the router's city is just a megabyte or so (an array, indexed by domain ID, identifying which of the city's transit domains serves each leaf domain), which is a $30 item, these days. It'll be a number of years before any city has more than a million IS-IS routing domains, by which time memory will be even cheaper. - The exponential growth is going to occur in the number of leaf domains per city; I wouldn't expect significant growth in the number of city codes or country codes. In my scheme, the overhead incurred by the growth at the leaves is limited to the routers within the scope of a city code, so, for example, the tracking of increasing number of leaves does not consume expensive long-distance bandwidth. Steve