Network Working Group Paul Francis (formerly Paul Tsuchiya) INTERNET-DRAFT Bellcore June 1993 Pip Host Operation 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 Pip is an internet protocol intended as the replacement for IP version 4. Pip is a general purpose internet protocol, designed to handle all forseeable internet protocol requirements. This specification is one of a number of documents that specify the operation of Pip. This specification describes the operation of Pip hosts. In particular, it describes how a Pip host picks among multiple Pip Addresses, and how a Pip host responds to various PCMP Packet Not Delivered (PDN) messages. Conventions All functions in the main body of this specification are mandatory. The functions in the appendix are optional, but if they are not implemented, some function that provides the information expected by addressListCreate must be implemented.. Pip WG, Expires December, 1993 [Page 1] INTERNET-DRAFT Pip Host Operation May 1993 1. Overview This specification defines two host functions associated with the task of choosing the appropriate source and destination addresses for a given communications. The first function, called addressListCreate, creates an ordered list of source/destination Pip address pairs given certain locally configured information and infor- mation learned about the destination host from DNS or the destination host's mobile host server. The second function, called addressListUse, chooses among the ordered list based on information given to it by routers in response to packet transmissions. The partitioning of address choosing into these two functions allows for nice modularity in implementation. For instance, addressListUse could exist inside the kernel while addressListCreate could be out- side the kernel, or in another machine altogether, for instance the Pip Header Server. It also allows evolution of the addressListCreate function (for instance, in the Pip Header Server) while still allow- ing hosts to respond to PCMP messages. This document specifies the addressListUse function in the main body, but places the addressListCreate function in an appendix. The reason for this is because the addressListCreate function specified here is fairly naive, and is considered to be experimental. It is expected that significant evolution of the addressListCreate function will occur as the internet gains experience with commercialization and real-time services. 2. addressListUse: Host Selection of Source and Destination Pip Address Pairs Among an Ordered List Assume that the following information has been obtained from the function addressListCreate: 1. An ordered list of source and destination Pip address pairs to potentially use for the communications. Associated with each Pip address pair is a marking of strong or weak preference. All of the strong preference addresses are preferred over the weak preference addresses. The same source or destination Pip address may appear multiple times in the ordered list, but a given source address/destination address pair may appear only Pip WG, Expires December, 1993 [Page 2] INTERNET-DRAFT Pip Host Operation May 1993 once. 2. Information about the destination from DNS, including the fol- lowing: 2a. The Pip ID of the destination host. 2b. The names of any mobile host servers associated with the desti- nation host. 2c. The exit PDN addresses, if any, associated with each of the des- tination Pip addresses. 2d. The Time-to-Live of the DNS information. Given this list, the Pip layer chooses among the ordered list of source Pip addresses (and destination Pip addresses) to use in the transmitted Pip packets. There are a number of criteria that are considered when choosing. The basic rule is that, in general, Pip address pairs higher in the list are preferred over Pip address pairs lower in the list. Pip address pairs lower in the list can be used, however, when Pip address pairs higher in the list cannot be delivered or are overridden for one of several reasons. The following list of rules are used to choose the appropriate Pip address pair. 1. If a Pip address pair has strong preference, a lower-preference Pip address pair may be used only when the higher-preference Pip address pair is unreachable. Unreachability is indicated by PCMP Packet Not Delivered messages. All address pairs tagged as unreachable are retagged as reachable after a period of time. 2. Host-driven exit routing is always used with a strong-preference Pip address pair. 3. Transit-driven exit routing is always used with a weak- preference Pip address pair. 4. Consider a Pip address pair received from the destination host with an exit routing subfield bit set to 0 (host-driven). If the received Pip address pair matches a strong-preference entry from the list, then this entry is used in preference to a higher list entry. If the received Pip address pair matches a weak- preference entry from the list, then this entry is used in Pip WG, Expires December, 1993 [Page 3] INTERNET-DRAFT Pip Host Operation May 1993 preference to a higher weak-preference list entry, but is not used in preference to a strong-preference list entry. 5. All weak-preference address pairs are tagged as either good- route or bad-route. A weak-preference address pair is tagged as bad-route if a Border Redirect is received in response to a packet sent with the address pair. Otherwise, the address pair is tagged as good-route. All bad-route tags are changed to good-route after some period of time. An address pair tagged good-route is always preferred over one tagged bad-route. 2.1. Formatting a Pip Header for Exit Routing If the source and destination share a metalevel=0 cluster, then the format of the Active FTIF and RC depend on the type of exit routing [2]. There are two types of exit routing, that is, routing inter- domain Pip packets from a source host to a network service provider of a private domain. In the first method, called transit-driven exit routing, the source host leaves the choice of provider to the routers. In the second method, called host-driven exit routing, the source host explicitly chooses the provider. If host-driven exit routing is chosen, then the Active FTIF is set to point at the top (last FTIF) of the source Pip Address. The exit routing type subfield of the RC is set to 0, to indicate host-driven exit routing (and thus potentially "override" the routers' best path to the destination). The level and metalevel subfields of the RC are set to 0. When using transit-driven exit routing, there are two modes of opera- tion. The first, called destination-oriented, is used when the routers internal to a domain have external routing information. The second, called provider-oriented, is used when the routers internal to a domain do not have any external routing information. Hosts learn whether intra-domain routing is destination-oriented or provider-oriented as part of Pip Address auto-configuration. With provider-oriented (transit-driven) exit routing, the fields are set the same as with host-driven exit routing, except that the exit routing type subfield of the RC is set to 1. With destination-oriented (transit-driven) exit routing, if there are multiple source providers, then the fields are set the same as with Pip WG, Expires December, 1993 [Page 4] INTERNET-DRAFT Pip Host Operation May 1993 provider-oriented exit routing. If there is only one provider (and therefore only one address prefix above the metalevel=0 boundary), the Active FTIF is set to point at the first FTIF of the destination Pip Address, the exit routing type subfield of the RF is set to 1, and the level and metalevel subfields of the RC are set to 0. 2.2. Responding to PCMP Packet Not Delivered (PND) Messages In the course of transmitting packets to a destination, PCMP PND mes- sages may be received [1]. The reception of PCMP PND messages may result in 1) new source/destination address pairs being used, 2) the packet being reformatted but with the same source/destination address pair, 3) a new list of source/destination address pairs being gen- erated, or 4) no more attempts at packet delivery. This section describes which actions are taken for the various types of PCMP PND messages. The PCMP PND message types are shown in Table I. The actions taken as a result of a PCMP PND message fall into four broad categories: 1. Those where reformatting the packet, but keeping the same source/destination address pair, may result in successful delivery. In these cases, none of the source/destination address pairs need be marked as unreachable. Instead, the packet should be reformatted as appropriate according to the PCMP PND message received. PCMP PND types that may fall into this category are codes 1, 2, 11, 12, 13, 14, 15, and 19. 2. Those where nothing, including modifying the source/destination address pair, can result in successful delivery of the packet. This is often the case where the destination host can be reached using the given source/destination address pair, but refuses the packet for some reason. In this case, the application is simply informed of the inability to communicate. PCMP PND types that may fall into this category are codes 1, 2, 3, 4, 5, 6, 9, 12, 13, 14, and 15. 3. Those where none of the source/destination address pairs is ade- quate for successful packet delivery, but where new source/destination address pairs may be obtained, either from the mobile host server or from DNS. PCMP PND types that may fall into this category are codes 7, 8, 10, 16, 18, and 20. Pip WG, Expires December, 1993 [Page 5] INTERNET-DRAFT Pip Host Operation May 1993 Code Meaning ---- ------- 1 Options Contents Unknown 2 Individual Option Unknown 3 Protocol (doesn't exist) 4 Protocol (administratively prohibited) 5 Port (doesn't exist) 6 Port (administratively prohibited) 7 Dest ID (known not to exist) 8 Dest ID (known to have moved) 9 Dest ID (administratively prohibited) 10 Dest ID (otherwise) 11 Hop Count Expired 12 HD Contents Unknown 13 Individual HD Parameter Unknown 14 RC Contents Unknown 15 Individual RC Parameter Unknown 16 FTIF (known not to exist) 17 FTIF (administratively prohibited) 18 FTIF (otherwise) 19 MTU Exceeded 20 Exit PDN Address Unreachable Table I: PCMP Packet Not Delivered Message Types 4. Those where changing the source/destination address pair to another one in the given list is adequate for successful delivery of the packet. PCMP PND types that may fall into this category are codes 7, 10, 16, 17, 18, and 20. It is categories 3 and 4 that are of interest here because it is by changing the source/destination pair to be used that packet delivery might be achieved. When a PCMP PND message of type 10, 18, or 20 (particularly 18) is received, a host may continue to use the same address pair for a while, in the hope that the reason for non-delivery may be short- lived. In what follows, we assume that the reason for non-delivery is not short-lived, and that the host takes action with regards to the received PCMP PND message. The following list indicates how to respond to the above PCMP PND types. Pip WG, Expires December, 1993 [Page 6] INTERNET-DRAFT Pip Host Operation May 1993 1. Codes 7 and 16, Dest ID or FTIF known not to exist. When either of these messages are received, the source host re-queries DNS. This happens regardless of the stated of the DNS Time-to-Live information. (That is, even if the Time-to-Live indicates that the DNS information is still valid, DNS should be re-queried.) If the Time-to-Live indicates that the original DNS information has expired, then a non-authoritative query is made. If the Time-to-Live indicates that the original DNS information has not expired, then an authoritative query is made. If the DNS infor- mation returned from the non-authoritative query matches the original DNS information, then an authoritative query is made. If the DNS information returned from the authoritative query matches the original DNS information, and the PCMP message is Code 7, then the destination host cannot be reached and the application is informed as such. If the PCMP message is Code 16, then all entries with the bad destination address are marked unreachable, and other source/destination pairs are tried. It should be apparent that the purpose of Codes 7 and 16 are to give an on-demand indication of when DNS information for a host or a group of hosts has changed. In the case of Code 7, an individual host has obtained a new (permanent) set of Pip addresses, resulting in new DNS entries for that host. Code 7 is typically returned by the router attached to the subnet that the destination host was formerly attached to, or by a host that has the Pip address previously owned by the desired destination host. In the case of Code 16, the address prefix of a group of hosts has been de-assigned. This would be the case where a sub- scriber network disconnected from a particular provider, thus making the subscriber's prefix from that provider invalid. The provider may keep the prefix unassigned for a period of time long enough to allow DNS entries to time out. During this time, the provider's routers can be configured to return PCMP PND mes- sages with Code 16 for that particular prefix. 2. Code 8, Dest ID known to have moved. This PCMP PND message is delivered by a router attached to the subnet of the permanent location of the destination when the destination has 1) moved to a new location, and has 2) informed the router that it has moved. Note that it may inform the router before it moves. Upon reception of this PCMP PND message, the host queries the mobile host server learned from DNS. If there is no mobile host Pip WG, Expires December, 1993 [Page 7] INTERNET-DRAFT Pip Host Operation May 1993 server for the destination host, all source/destination pair entries whose low-order metalevel part matches that of the attempted destination address are marked as unreachable. (The low-order metalevel part is the sequence of FTIFs starting with the low-order FTIF and including all FTIFs below the lowest metalevel boundary. Normally, all of a host's addresses will have the same low-order metalevel part. The exception to this rule is when the host is attached to more than one subnet.) If all of the source/destination address pairs are marked unreachable, then the destination host cannot be reached and the application is informed as such. 3. Code 10, Dest ID, all circumstances other than Codes 7, 8, and 9. This PCMP PND message is sent when the router attached to the subnet indicated by the Pip address cannot reach the host, and the reason is unknown. In this case, the source host does not know if the destination host has moved temporarily, has a new permanent address, or has simply crashed, been powered down, or has a bad interface. (If the router has a bad interface, then it will return a Code 18, indicating the lowest level FTIF, that is, the subnet, as unreachable.) When this PCMP PND message is received, all source/destination pair entries whose low-order metalevel part matches that of the attempted destination address are marked as unreachable (same as with item 2 above). If this results in all source/destination pair entries being marked as unreachable, and the destination host has a mobile host server, then the mobile host server is queried to determine if the destination host has a new temporary address. If the destination host does not have a new temporary address, and the DNS Time-to-Live for that host has expired, then DNS is requeried (first with a non-authoritative query, followed by an authoritative query if new information is not obtained). If none of the above actions results in new destination addresses to try, then the destination host cannot be reached and the application is informed as such. 4. Codes 17 and 18, FTIF, either administratively prohibited or undeliverable for unknown reason. When one of these PCMP PND messages is received, any Pip WG, Expires December, 1993 [Page 8] INTERNET-DRAFT Pip Host Operation May 1993 source/destination address pair that contains the bad FTIF is marked as unreachable. In order to "contain" the bad FTIF, the chain of FTIFs from the FTIF indicated by the PCMP PND message up to the FTIF immediately below the next higher metalevel boun- dary must match. If all source/destination address pairs are marked unreachable, then the actions in item 3 above for the same circumstances are taken. 5. Code 20, Exit PDN Address Unreachable. This PCMP PND message is sent when the entry router to a Public Data network cannot com- municate with the exit router specified by the Exit PDN Address option. When this PCMP PND message is received, the Exit PDN Address information associated with the provider is marked as unreachable. If all of the Exit PDN Addresses for a given pro- vider are marked as unreachable, then then all source/destination address pairs with a destination address associated with the provider are marked as unreachable. If all source/destination address pairs are marked unreachable, then the actions in item 3 above for the same circumstances are taken. After a period of time, the Exit PDN Address information is marked as reachable. This may cause a previously unreachable source/destination address pair to become reachable. 3. Forming Exit PDN Address Options To be filled in. References [1] Francis, Govindan, "PCMP: Pip Control Message Protocol", Internet-Draft [2] Francis, "Pip Address Conventions", Internet-Draft Pip WG, Expires December, 1993 [Page 9] INTERNET-DRAFT Pip Host Operation May 1993 4. Appendix A: addressListCreate--Forming an Ordered List of Source and Destination Pip Address Pairs This appendix gives an experimental version of the addressListCreate function. It is expected that this function will evolve considerably as experience with commercialization and real-time service is gained. The following information is used by function addressListCreate: 1. The Pip addresses of the source host (obtained from local confi- guration). 2. The Pip addresses of the destination host (obtained from DNS and the destination host's mobile host server). 3. The user classes that the traffic falls under (such as research, corporate private). 4. The desired price/performance tradeoff--that is, one of 1) best price, 2) best performance, and 3) best price/performance. 5 The application type (for instance, telnet, ftp, vat, and so on). 6. Information about the destination from DNS, including the fol- lowing: 6a. The Pip ID of the destination host. 6b. The names of any mobile host servers associated with the desti- nation host. 6c. The exit PDN addresses, if any, associated with each of the des- tination Pip addresses. 6d. The Time-to-Live of the DNS information. 7. A provider preference given by the application (or user behind the application). 8. Other optional information, such as topology information or local policy and tariff information. Such information is not specified in this document. The following information is associated with the provider indicated Pip WG, Expires December, 1993 [Page 10] INTERNET-DRAFT Pip Host Operation May 1993 by the first FTIF of any Pip address (note that this is not neces- sarily the top-level of the Pip address, as there may be a route fragment associated with the Pip address [2]): 1. The provider name. 2. The service provider switching technology type (such as Pip, X.25, Frame Relay, and so on). 3. The user communities that the provider services. Given the above information, function addressListCreate executes the following steps (described in detail below). First, it determines if the source and destination are within the same cluster below metalevel boundary 0. If they are, then no provider decision need be made, and the creation of the source/destination address pair list is trivial. If the source and destination are not in the same metalevel cluster, then a provider decision must be made. This involves considering the actual providers, the service they provide versus the service required by the application, and any access restrictions on the part of either user or provider. This decision is entirely a local matter, and it is expected that this process will become more involved as experience is gained. This document proposes a simple but perhaps limited approach. First, the addresses associated with unacceptable providers (either source or destination) are eliminated. Note that a given provider can have multiple addresses--representing different services pro- vided. The remaining addresses, are then paired into all possible combinations. The address pairs are then ordered according to such criteria as commonality between source and destination, price, and other provider preference criteria. 4.1. First Step: Determine if Destination is in a Metalevel>0 Cluster The purpose of this step is to determine if the destination is within the private network (or possibly a portion of the private network, for lower metalevel clusters), or on the same LAN. If the destina- tion is within a metalevel>0 cluster, then no decisions have to be made about choice of address prefix--the higher order part of the address is pruned, and the packet is transmitted without regard to exit routing. Pip WG, Expires December, 1993 [Page 11] INTERNET-DRAFT Pip Host Operation May 1993 To determine if the destination is on the same LAN, the host compares each of its Pip Addresses with each of the destination's. If any of the Pip Addresses for the source completely match one of those for the destination, then the destination is assumed to be on the same LAN. If the destination is determined to be on the same LAN, then no FTIF Chain is necessary. The level and metalevel fields of the RC are set to be that of the LAN. The Active FTIF field is set to be 0. The Exit Routing Type bit of the RC is set to be 1. The packet is transmitted directly to the destination host (possibly after ARPing first). If, based on this comparison, the destination is determined not to be on the same LAN, the source's and destination's Pip addresses are compared to see if they are in the same metalevel cluster. Two hosts are in the same metalevel cluster if any of the destination's prefixes (the FTIFs from the top level to the FTIF above the metalevel boundary) match any of the source's prefixes. Two hosts are in the same metalevel=n cluster if this test holds true for metalevel=n and not metalevel=n+1. If the test holds true for metalevel=n, then it must also hold true for all metalevels less than n (where, again, n=0 is the highest metalevel). If the destination host is in the same metalevel>0 cluster, then it does not need any of the address prefix above the metalevel boundary in the Pip header. There is no exit provider selection in this case, so the exit routing type subfield of the RC is set to 1. The Active FTIF field is set to point at the highest FTIF of the destination address, which must be at level=0 and metalevel=n, where n is the metalevel cluster the source and destination have in common. The destination or source host may have multiple different low-order metalevel parts. If both source and destination have only one multi- ple low-order metalevel part, then only one source/destination address pair is generated. If either destination or source have mul- tiple low-order metalevel parts, then there will be multiple source/destination address pairs in the list generated. All entries in the list should have the same preference type (weak or strong). Since no exit routing takes place for internal traffic, the prefer- ence type does not matter. The list should contain all possible combinations of source/destination address pairs. However, source/destination Pip WG, Expires December, 1993 [Page 12] INTERNET-DRAFT Pip Host Operation May 1993 address pairs with more common high order FTIFs should have prefer- ence over those with fewer common high order FTIFs. Among different source/destination address pairs with the same number of common high order FTIFs, the order of preference in the list is a local decision. In general, a random selection will result in load balancing. The remaining steps are not necessary if the source and destination share a metalevel>0 cluster. 4.2. Second Step: Eliminate Unusable Addresses by Access Restriction The next step is to eliminate any individual source or destination addresses that do not meet requirements. This can be either because 1) the user (or this particular application) is restricted from using the provider, or 2) the user wishes not to use a certain provider. In the future, the service provided by the provider will increasing be used as an elimination criteria. 4.3. Third Step: Label Desirability of Source Address by Performance In this step, each source address is labeled according to its ability to satisfy the service requirements of the application. The avail- able performance levels are satisfactory (S), adequate (A), and inadequate (I). The information used to determine the labeling is 1) application type, 2) provider switching technology type, and 3) pro- vider name. It is a local matter how this labeling is determined. 4.4. Fourth Step: Label Desirability of Source Address by Price In this step, each source address is labeled according to its cost. The available cost categories are expensive (E), cheap (C), and free (F). It may be possible to rank order the individual addresses within each of these categories. It is expected that the source address will be the primary determining factor with respect to cost. Pip WG, Expires December, 1993 [Page 13] INTERNET-DRAFT Pip Host Operation May 1993 4.5. Fifth Step: Rank Order Source Addresses In this step, the source addresses are rank ordered according to desired price/performance. If price is preferred over performance, then the ranking is FS, FA, FU, CS, CA, ES, CU, EA, and EU, where the first letter indicates price, and the second letter indicates perfor- mance. If performance is preferred over price, then the ranking is FS, CS, ES, FA, CA, FU, EA, CU, and EU. If price and performance should be balanced, then the ranking is FS, CS, FA, CA, ES, EA, FU, CU, and EU. 4.6. Sixth Step: Match Destination Addresses with Source Addresses In this step, the source addresses ranked in the previous step are associated with destination addresses, thus producing a set of source/destination address pairs. Each pair is labeled according to the quality of match. A pair of addresses is considered a best match if the source and des- tination share the same provider (according to the provider name). Two addresses share the same provider is any of the providers in one address match any of the providers in another address. (An address has multiple providers if there is a route fragment in the address [2].) A pair of addresses is considered a good match if 1) it is not a best match, and 2) all of the source and destination providers are of the same switching technology type, or any of the source providers are of type IP (any version). A pair of addresses is considered a bad match otherwise. 4.7. Seventh Step: Rank Order and Label Address Pairs Finally, the source/destination address pairs are rank ordered and labeled according to strong and weak preference. The ordering fol- lows the following rules: 1. Pairs with best or good matching are ordered before pairs with bad matching. Pip WG, Expires December, 1993 [Page 14] INTERNET-DRAFT Pip Host Operation May 1993 2. Otherwise, pairs with higher ranked source addresses are ordered before pairs with lower ranked source addresses. 3. Otherwise, pairs with best matching are ordered before pairs with good matching. Address pairs are given a strong preference marking if it is desired that 1) the choice of source provider over-ride an alternative choice found by the routers, or 2) the address pair be used even if the des- tination host uses a different address pair in its packets. Address pairs are given a weak preference marking otherwise. Pip WG, Expires December, 1993 [Page 15]