Network Working GrouP P. Tsuchiya INTERNET-DRAFT Bellcore March 1993 On the Assignment of Provider Rooted Addresses Status of this 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 draft documents valid for a maximum of six months. Internet Drafts may be Updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress." Please check the I-D abstract listing contained in each Internet Draft directory to learn the current status of this or any other Internet Draft. Abstract There is an ongoing debate in the IETF about the pros and cons of provider versus geographically assigned addresses. This paper describes the characteristics of provider-rooted address assignment, and compares it with geographical address assignment. 1. Some Background The assignment of addresses in the internet follows a tree of Address Assignment Authorities. At the root of the tree is the top-level (or 0-level) AAA. This AAA assigns blocks of numbers to the next level down (1-level) AAA, which assigns blocks of numbers from the block it owns to 2-level AAAs and so on. If a traditional left-to-right bit- wise significant address is used, these blocks of numbers are low- order-bits-maskable binary numbers. If Pip Addresses are used, these blocks are derived from a hierarchical series of numbers. For the Pip WG, Expires Sept. 1, 1993 [Page 1] INTERNET-DRAFT Provider-based Addressing March 1993 sake of discussion, we refer to assigning a block of numbers as sim- ply assigning a number. The issue at debate is how to assign these numbers so that 1) routing scales well, 2) good paths are found, 3) constraints on the physical topology are minimized, and 4) reconfiguration of systems is minim- ized. If one creates a graph where the vertical axis is scaling (bottom is perfect scaling in top is bad scaling) and the horizontal axis is path quality (left is perfect paths and right is bad paths), then the optimal operating point on the graph is the lower left corner. In general the "physics" of networking forces operating points on this graph to be at the upper left or lower right. Depend- ing on the type of address assignment scheme used, however, it is possible to move somewhat towards the lower left (good solutions) or the upper right (bad solutions). Moving to the lower left, however, may increase topology constraints or reconfiguration requirements. Central to the evaluation of any address assignment scheme are answers to the questions 1) what constitutes good scaling, 2) what constitutes a good path, 3) what constitutes unacceptable or costly topology constraints, and 4) what constitutes unacceptable or costly reconfiguration. I suspect that the community has or will come to reasonable agreement on what the characteristics of each address assignment scheme are. Except for possibly the first question, I also suspect that the community will not agree on the answers to the questions, partly because the cost of each aspect is borne by dif- ferent parties, and partly because we lack experience. The argument for provider-rooted addressing assumes, among other things, that 1) provider selection is an important component of a good path, and 2) reassignment of address prefixes to large numbers of systems will be low cost with IPv7. I won't spend any time argu- ing for these two assumptions, except to say the following. First, provider selection is part of telephone operation in the USA. I believe that provider selection will be more important in the inter- net because of the wider variation of services. Second, the Pip Near-term Architecture document [1] outlines an approach to prefix assignment that I believe to be tenable. 2. Description of Provider-rooted Addressing The basic approach to provider-rooted addresses is as follows. The top-level AAA assigns numbers directly to providers. This includes Pip WG, Expires Sept. 1, 1993 [Page 2] INTERNET-DRAFT Provider-based Addressing March 1993 both internet protocol service providers and lower-layer (for instance, ATM) protocol service providers. Depending on the size of the provider, it can either assign numbers internally, or assign numbers directly to its subscribers. The internal numbers would be for clustering groups of subscribers under a single prefix for the sake of internal scaling. Thus, the addresses would be: provider.subscriber or provider.subProvider.subscriber From the perspective of routing among providers, provider-rooted addresses mean that a provider-router routing table will have one entry for each other provider. From the perspective of subscribers, they will be given an address prefix from each provider through which they derive service. Each host in the subscriber network would then have one address for each provider through which the subscriber net- work can be reached. When the subscriber subscribes to a new pro- vider, or unsubscribes from an existing provider, it must change the address set for all of its hosts and routers. The purpose of assigning numbers to providers is two-fold. First, it helps scaling. Rather than keep a routing table entry for roughly every subscriber network (as with IP), one entry per provider is required. Second, it gives the subscriber a means of selecting the provider, both on the source side and on the destination side. With regards to provider selection, it is not necessarily the case that the subscriber wants to choose a directly attached provider. This would be the case for instance where the directly attached pro- vider is a "local access" provider. That is, the provider operates in a small region, and for all destinations outside that region, the local access provider forwards traffic to a "long distance" pro- vider. The subscriber may want to choose one of multiple long dis- tance providers that provide service to the local access provider. In this case, the long distance provider would appear at the top of the address, and the local access provider would appear below that. LDprovider.LAprovider.subscriber The local access provider could appear as a top-level number or as a number hierarchically under the long-distance provider. The former Pip WG, Expires Sept. 1, 1993 [Page 3] INTERNET-DRAFT Provider-based Addressing March 1993 is generally preferable, as it allows all providers to have a top- level number whether or not they appear at the top of an address. This allows the local access provider to, among other things, appear at the top of the hierarchy for certain subscribers but not others. Note that if a local access provider does not appear at the top of the hierarchy for any of its subscribers, then it does not have to be advertised globally in routing updates. Note that with Pip Addressing, it is straightforward to give each provider, including local access providers, a top level number. With SIP addressing, doing this is somewhat problematic, since the address size is constrained and giving top level numbers to the first two levels requires more bits. 3. Other Aspects of Provider-rooted Addressing 3.1. Scaling at the top level With provider-rooted addresses, the growth in routing tables at the top level of the hierarchy grows as the number of providers that wish to be globally advertised. It is possible at some future date that this number will be too large for top-level routing. I believe that the need for this will be unlikely. None-the-less, it is a possibil- ity. The solution is to add another level of hierarchy above the provider level. providerCluster.provider.subscriber This of course requires that, over time, all addresses will have to be changed. I believe this to be perfectly feasible. Large scale address prefix assignment for private networks is necessary in a provider-rooted scheme because private networks will get new prefixes every time they change providers. Adding a new level of hierarchy at the top will be no different to a private network than getting a new prefix because of a provider change. In addition, adding a new level of hierarchy at the top is likely to be a rare event compared to changing providers. Furthermore, such prefix changes are invisible to most users, since most users deal with domain names rather than addresses. It is not appropriate to try to determine now what the nature of the Pip WG, Expires Sept. 1, 1993 [Page 4] INTERNET-DRAFT Provider-based Addressing March 1993 new top level should be. In general, the clustering of providers should be according to how providers would most commonly intercon- nect. It is not necessarily true that providers will most commonly interconnect at national or metro boundaries. IP providers currently exist that have international connections but are not connected to all other IP providers in their country. It seems feasible that, in the future, a provider will be as likely to connect to a provider of similar type as it is to connect to a provider in its own country. For instance, it may make more sense for an ATM provider in the USA to connect to an ATM provider in Europe than to connect to an IP provider in the USA. One advantage to clustering providers according to service provided rather than geographical locale is that the top level can still be used as a meaningful policy routing hook. In any event, it is premature to speculate on how providers might be clustered, given that it is unlikely to happen anyway, and if it does the decision can best be made then. 3.2. Routing between providers If two providers are interconnected in multiple places, then there are multiple ways to route from one provider to the other. In some cases, it is desirable to be able to control which route is used. For instance, consider two providers, X and Y, connected with each other on the right coast and the left coast. Assume that X has pack- ets for Y. If X's policy is that it should always route the packet to Y at the nearest interconnect, then provider-root addressing works just fine. Each of X's routing tables simply point to the nearest interconnect. If, on the other hand, X's policy is to route the packet internally until it reaches the interconnect closest to the destination, then additional information is needed. X must have routing information about the internal structure of Y. That is, X must know which of Y's subscribers are nearest to the left coast interconnect, and which are nearest to the right coast interconnect. If Y clusters internally (that is, has an internal layer of hierarchy above the subscriber level but below the top level), then X need only know about the clus- ters in Y, not the individual subscribers. Still, this could be a substantial amount of information. (Note that with geographical addressing, the opposite effect occurs. Pip WG, Expires Sept. 1, 1993 [Page 5] INTERNET-DRAFT Provider-based Addressing March 1993 If X's policy is to route internally until getting close to the des- tination, then geographical works fine, because X's internal routing will get the packet close to the destination's geographic locale, and then local routing will determine which provider to use. If, on the other hand, X's policy is to route to the nearest interconnect, then X would need to know which of the various subscribers in each geo- graphic locale were subscribers of Y.) 4. Comparison with Geographical Addressing Our working definition of geographical addressing is where the top- level is assigned to geographical regions, such as countries or metros. Thus, a geographical address could be: country.metro.subscriber With provider-rooted addressing, packets are initially routed to the provider indicated at the top of the address, which then routes to the entity at the next lower part of the address (subProvider or sub- scriber) and so on. With geographical, the packet is routed to the geographical entity at the top (say, country), then to the next geo- graphical entity (metro), and finally to subscriber. With any hierarchical routing, the implication is that, once a "clus- ter" is reached, the packet can be routed internal to the cluster. With provider-rooted addressing, this rule follows naturally since a provider is naturally internally connected. With geographical addressing, it does not naturally follow that a country or metro will be internally connected. Instead, it is neces- sary to insure that they are connected, either by making physical connections or by tunneling through other parts of the hierarchy. Note that being "internally connected" doesn't mean that everything in a cluster has a direct connection with everything else (n^2 con- nectivity). It is adequate for two "network elements" in a cluster to reach each other through transit network elements. I assume that providers will overlap geographically. In this case, once a packet reaches a geographic locale in one provider, a decision must be made as to which other provider to forward the packet to. To make this decision, the router must know which subscriber numbers are connected to which providers in the locale. Pip WG, Expires Sept. 1, 1993 [Page 6] INTERNET-DRAFT Provider-based Addressing March 1993 4.1. Some comments on scaling Consider a routing hierarchy with N levels of hierarchy, with level N as the top level and level 1 as the bottom level. In general, the information in a routing table for a router operating at hierarchy level n consists of: 1. One entry for each "cluster" immediately below the router in the hierarchy (i.e., level n-1). 2. One entry for each cluster at levels x = n through N-1 that shares a parent with the router at level x+1. 3. One entry for every cluster at level N. Of course, there are exceptions to this rule, for instance with default routing. Routing table size is minimized, for a given number of hierarchy lev- els, when the number of elements at each level is the same. Thus, to keep routing tables relatively small, growth should, to the extent possible, be absorbed equally at all hierarchy levels. If routing tables approach unacceptable size, then it is necessary to add levels of hierarchy. Both geographical and provider-rooted addresses allow growth in the number of elements at each level. With geographical addresses, addi- tional numbers can be added to each geographical locale. For instance, if the top of the hierarchy is assigned to countries, and growth dictates that the top level should be bigger, it is possible to assign additional numbers to each country. Thus, a given country would have multiple top level numbers instead of only one. Note that assigning additional numbers does not require existing addresses to change. Addresses rooted at the new number could be assigned to new growth. With provider-rooted addresses, the hierarchical numbering within each provider is determined by the provider. It is safe to say, how- ever, that additional numbers could be assigned similarly to the way described in the previous paragraph for geographical addresses. If at the top level, the number of providers is smaller than the desired number of elements at the top level, then additional numbers can be assigned to each provider. If, on the other hand, the number of pro- viders is larger than an acceptable number of elements at the top level, it is not possible to reduce the number of elements. In this Pip WG, Expires Sept. 1, 1993 [Page 7] INTERNET-DRAFT Provider-based Addressing March 1993 case, a level of hierarchy must be added above that of provider, as discussed previously. Thus, geographical addressing provides slightly more flexibility with regards to routing talbe sizing. 5. Conclusion The primary difference between provider-rooted and geographical addresses is that provider-rooted addresses allows for provider- selection policy routing where-as geographical addressing does not. The "cost" of this extra functionality is that subscribers must periodically undergo address prefix changes. In defense of prefix changes, I make the following observations. First, I believe that, even with geographical addresses, prefix changes will occur from time to time, for instance because at some point a new level of hierarchy will be needed. Second, I believe that automatic prefix changes, at least for hosts but also for inter- nal routers, is straightforward algorithmically. It should be possi- ble for large scale prefix changes to occur as a matter of course. Third, I think it is impossible to pick the correct address assign- ment technique for all time, and so the ability to have automatic prefix changes allows us to be flexible with regard to addressing in the future. Thus, I argue that we should and can have easy automatic address pre- fix assignment. Given this, I see little reason not to use provider-rooted addresses. References [1] Pip Near-Term Architecture, Internet-Draft Pip WG, Expires Sept. 1, 1993 [Page 8]