RFC 1621
Pip Near-term Architecture
Pages: 51
Historic
Historic
Part 1 of 2 – Pages 1 to 25
Network Working Group P. Francis Request for Comments: 1621 NTT Category: Informational May 1994 Pip Near-term Architecture Status of this Memo This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind. Distribution of this memo is unlimited. Preamble During 1992 and 1993, the Pip internet protocol, developed at Belclore, was one of the candidate replacments for IP. In mid 1993, Pip was merged with another candidate, the Simple Internet Protocol (SIP), creating SIPP (SIP Plus). While the major aspects of Pip-- particularly its distinction of identifier from address, and its use of the source route mechanism to achieve rich routing capabilities-- were preserved, many of the ideas in Pip were not. The purpose of this RFC and the companion RFC "Pip Header Processing" are to record the ideas (good and bad) of Pip. This document references a number of Pip draft memos that were in various stages of completion. The basic ideas of those memos are presented in this document, though many details are lost. The very interested reader can obtain those internet drafts by requesting them directly from me at <francis@cactus.ntt.jp>. The remainder of this document is taken verbatim from the Pip draft memo of the same title that existed when the Pip project ended. As such, any text that indicates that Pip is an intended replacement for IP should be ignored. Abstract Pip is an internet protocol intended as the replacement for IP version 4. Pip is a general purpose internet protocol, designed to evolve to all forseeable internet protocol requirements. This specification describes the routing and addressing architecture for near-term Pip deployment. We say near-term only because Pip is designed with evolution in mind, so other architectures are expected in the future. This document, however, makes no reference to such future architectures.
Table of Contents 1. Pip Architecture Overview ................................... 4 1.1 Pip Architecture Characteristics ........................... 4 1.2 Components of the Pip Architecture ......................... 5 2. A Simple Example ............................................ 6 3. Pip Overview ................................................ 7 4. Pip Addressing .............................................. 9 4.1 Hierarchical Pip Addressing ................................ 9 4.1.1 Assignment of (Hierarchical) Pip Addresses ............... 12 4.1.2 Host Addressing .......................................... 14 4.2 CBT Style Multicast Addresses .............................. 15 4.3 Class D Style Multicast Addresses .......................... 16 4.4 Anycast Addressing ......................................... 16 5. Pip IDs ..................................................... 17 6. Use of DNS .................................................. 18 6.1 Information Held by DNS .................................... 19 6.2 Authoritative Queries in DNS ............................... 20 7. Type-of-Service (TOS) (or lack thereof) ..................... 21 8. Routing on (Hierarchical) Pip Addresses ..................... 22 8.1 Exiting a Private Domain ................................... 23 8.2 Intra-domain Networking .................................... 24 9. Pip Header Server ........................................... 25 9.1 Forming Pip Headers ........................................ 25 9.2 Pip Header Protocol (PHP) .................................. 27 9.3 Application Interface ...................................... 27 10. Routing Algorithms in Pip .................................. 28 10.1 Routing Information Filtering ............................. 29 11. Transition ................................................. 30 11.1 Justification for Pip Transition Scheme ................... 31 11.2 Architecture for Pip Transition Scheme .................... 31 11.3 Translation between Pip and IP packets .................... 33 11.4 Translating between PCMP and ICMP ......................... 34 11.5 Translating between IP and Pip Routing Information ........ 34 11.6 Old TCP and Application Binaries in Pip Hosts ............. 34 11.7 Translating between Pip Capable and non-Pip Capable DNS Servers ................................................... 35
12. Pip Address and ID Auto-configuration ...................... 37 12.1 Pip Address Prefix Administration ......................... 37 12.2 Host Autoconfiguration .................................... 38 12.2.1 Host Initial Pip ID Creation ............................ 38 12.2.2 Host Pip Address Assignment ............................. 39 12.2.3 Pip ID and Domain Name Assignment ....................... 39 13. Pip Control Message Protocol (PCMP) ........................ 40 14. Host Mobility .............................................. 42 14.1 PCMP Mobile Host message .................................. 43 14.2 Spoofing Pip IDs .......................................... 44 15. Public Data Network (PDN) Address Discovery ................ 44 15.1 Notes on Carrying PDN Addresses in NSAPs .................. 46 16. Evolution with Pip ......................................... 46 16.1 Handling Directive (HD) and Routing Context (RC) Evolution. 49 16.1.1 Options Evolution ....................................... 50 References ..................................................... 51 Security Considerations ........................................ 51 Author's Address ............................................... 51
Introduction 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 describes the routing and addressing architecture for near-term Pip deployment. We say near-term only because Pip is designed with evolution in mind, so other architectures are expected in the future. This document, however, makes no reference to such future architectures (except in that it discusses Pip evolution in general). This document gives an overall picture of how Pip operates. It is provided primarily as a framework within which to understand the total set of documents that comprise Pip. 1. Pip Architecture Overview The Pip near-term architecture is an incremental step from IP. Like IP, near-term Pip is datagram. Pip runs under TCP and UDP. DNS is used in the same fashion it is now used to distribute name to Pip Address (and ID) mappings. Routing in the near-term Pip architecture is hop-by-hop, though it is possible for a host to create a domain- level source route (for policy reasons). Pip Addresses have more hierarchy than IP, thus improving scaling on one hand, but introducing additional addressing complexities, such as multiple addresses, on the other. Pip, however, uses hierarchical addresses to advantage by making them provider-based, and using them to make policy routing (in this case, provider selection) choices. Pip also provides mechanisms for automatically assigning provider prefixes to hosts and routers in domains. This is the main difference between the Pip near-term architecture and the IP architecture. (Note that in the remainder of this paper, unless otherwise stated, the phrase "Pip architecture" refers to the near- term Pip architecture described herein.) 1.1 Pip Architecture Characteristics The proposed architecture for near-term Pip has the following characteristics: 1. Provider-rooted hierarchical addresses. 2. Automatic domain-wide address prefix assignment. 3. Automatic host address and ID assignment.
4. Exit provider selection.
5. Multiple defaults routing (default routing, but to multiple exit
points).
6. Equivalent of IP Class D style addressing for multicast.
7. CBT style multicast.
8. "Anycast" addressing (route to one of a group, usually the
nearest).
9. Providers support forwarding on policy routes (but initially will
not provide the support for sources to calculate policy routes).
10. Mobile hosts.
11. Support for routing across large Public Data Networks (PDN).
12. Inter-operation with IP hosts (but, only within an IP-address
domain where IP addresses are unique). In particular, an IP
address can be explicitly carried in a Pip header.
13. Operation with existing transport and application binaries
(though if the application contains IP context, like FTP, it may
only work within a domain where IP addresses are unique).
14. Mechanisms for evolving Pip beyond the near-term architecture.
1.2 Components of the Pip Architecture
The Pip Architecture consists of the following five systems:
1. Host (source and sink of Pip packets)
2. Router (forwards Pip packets)
3. DNS
4. Pip/IP Translator
5. Pip Header Server (formats Pip headers)
The first three systems exist in the IP architecture, and require no
explanation here. The fourth system, the Pip/IP Translator, is
required solely for the purpose of inter-operating with current IP
systems. All Pip routers are also Pip/IP translators.
The fifth system, the Pip Header Server, is new. Its function is to format Pip headers on behalf of the source host (though initially hosts will be able to do this themselves). This use of the Pip Header Server will increase as policy routing becomes more sophisticated (moves beyond near-term Pip Architecture capabilities). To handle future evolution, a Pip Header Server can be used to "spoon-feed" Pip headers to old hosts that have not been updated to understand new uses of Pip. This way, the probability that the internet can evolve without changing all hosts is increased. 2. A Simple Example A typical Pip "exchange" is as follows: An application initiates an exchange with another host as identified by a domain name. A request for one or more Pip Headers, containing the domain name of the destination host, goes to the Pip Header Server. The Pip Header Server generates a DNS request, and receive back a Pip ID, multiple Pip Addresses, and possibly other information such as a mobile host server or a PDN address. Given this information, plus information about the source host (its Pip Addresses, for instance), plus optionally policy information, plus optionally topology information, the Pip Header Server formats an ordered list of valid Pip headers and give these to the host. (Note that if the Pip Header Server is co-resident with the host, as will be common initially, the host behavior is similar to that of an IP host in that a DNS request comes from the host, and the host forms a Pip header based on the answer from DNS.) The source host then begins to transmit Pip packets to the destination host. If the destination host is an IP host, then the Pip packet is translated into an IP packet along the way. Assuming that the destination host is a Pip host, however, the destination host uses the destination Pip ID alone to determine if the packet is destined for it. The destination host generates a return Pip header based either on information in the received Pip header, or the destination host uses the Pip ID of the source host to query the Pip Header Server/DNS itself. The latter case involves more overhead, but allows a more informed decision about how to return packets to the originating host. If either host is mobile, and moves to a new location, thus getting a new Pip Address, it informs the other host of its new address directly. Since host identification is based on the Pip ID and not the Pip Address, this doesn't cause transport level to fail. If both hosts are mobile and receive new Pip Addresses at the same time (and thus cannot exchange packets at all), then they can query each other's respective mobile host servers (learned from DNS). Note that
keeping track of host mobility is completely confined to hosts. Routers never get involved in tracking mobile hosts (though naturally they are involved in host discovery and automatic host address assignment). 3. Pip Overview Here, a brief overview of the Pip protocol is given. The reader is encouraged to read [2] for a complete description. The Pip header is divided into three parts: Initial Part Transit Part Options Part The Initial Part contains the following fields: Version Number Options Offset, OP Contents, Options Present (OP) Packet SubID Protocol Dest ID Source ID Payload Length Host Version Payload Offset Hop Count All of the fields in the Initial Part are of fixed length. The Initial Part is 8 32-bit words in length. The Version Number places Pip as a subsequent version of IP. The Options Offset, OP Contents, and Options Present (OP) fields tell how to process the options. The Options Offset tells where the options are The OP tells which of up to 8 options are in the options part, so that the Pip system can efficiently ignore options that don't pertain to it. The OP Contents is like a version number for the OP field. It allows for different sets of the (up to 8) options. The Packet SubID is used to relate a received PCMP message to a previously sent Pip packet. This is necessary because, since routers in Pip can tag packets, the packet returned to a host in a PCMP message may not be the same as the packet sent. The Payload Length and Protocol take the place of IP's Total Length and Protocol fields respectively. The Dest ID identifies the destination host, and is not used for routing, except for where the final router on a LAN uses ARP to find the physical address of the host identified by the dest
ID. The Source ID identifies the source of the packet. The Host
Version tells what control algorithms the host has implemented, so
that routers can respond to hosts appropriately. This is an
evolution mechanism. The Hop Count is similar to IP's Time-to-Live.
The Transit Part contains the following fields:
Transit Part Offset
HD Contents
Handling Directive (HD)
Active FTIF
RC Contents
Routing Context (RC)
FTIF Chain (FTIF = Forwarding Table Index Field)
Except for the FTIF Chain, which can have a variable number of 16-bit
FTIF fields, the fields in the Transit Part are of fixed length, and
are three 32-bit words in length.
The Transit Part Offset gives the length of the Transit Part. This
is used to determine the location of the subsequent Transit Part (in
the case of Transit Part encapsulation).
The Handling Directive (HD) is a set of subfields, each of which
indicates a specific handling action that must be executed on the
packet. Handling directives have no influence on routing. The HD
Contents field indicates what subfields are in the Handling
Directive. This allows the definition of the set of handling
directives to evolve over time. Example handling directives are
queueing priority, congestion experienced bit, drop priority, and so
on.
The remaining fields comprise the Routing Directive. This is where
the routing decision gets made. The basic algorithm is that the
router uses the Routing Context to choose one of multiple forwarding
tables. The Active FTIF indicates which of the FTIFs to retrieve,
which is then used as an index into the forwarding table, which
either instructs the router to look at the next FTIF, or returns the
forwarding information.
Examples of Routing Context uses are; to distinguish address families
(multicast vs. unicast), to indicate which level of the hierarchy a
packet is being routed at, and to indicate a Type of Service. In the
near-term architecture, the FTIF Chain is used to carry source and
destination hierarchical unicast addresses, policy route fragments,
multicast addresses (all-of-group), and anycast (one-of-group)
addresses. Like the OP Contents and HD Contents fields, the RC
Contents field indicates what subfields are in the Routing Context.
This allows the definition of the Routing Context to evolve over time. The Options Part contains the options. The options are preceded by an array of 8 fields that gives the offset of each of up to 8 options. Thus, a particular option can be found without a serial search of the list of options. 4. Pip Addressing Addressing is the core of any internet architecture. Pip Addresses are carried in the Routing Directive (RD) of the Pip header (except for the Pip ID, which in certain circumstances functions as part of the Pip Address). Pip Addresses are used only for routing packets. They do not identify the source and destination of a Pip packet. The Pip ID does this. Here we describe and justify the Pip Addressing types. There are four Pip Address types [11]. The hierarchical Pip Address (referred to simply as the Pip Address) is used for scalable unicast and for the unicast part of a CBT-style multicast and anycast. The multicast part of a CBT-style multicast is the second Pip address type. The third Pip address type is class-D style multicast. The fourth type of Pip address is the so-called "anycast" address. This address causes the packet to be forwarded to one of a class of destinations (such as, to the nearest DNS server). Bits 0 and 1 of the RC defined by RC Contents value of 1 (that is, for the near-term Pip architecture) indicate which of four address families the FTIFs and Dest ID apply to. The values are: Value Address Family ----- -------------- 00 Hierarchical Unicast Pip Address 01 Class D Style Multicast Address 10 CBT Style Multicast Address 11 Anycast Pip Address The remaining bits are defined differently for different address families, and are defined in the following sections. 4.1 Hierarchical Pip Addressing The primary purpose of a hierarchical address is to allow better scaling of routing information, though Pip also uses the "path" information latent in hierarchical addresses for making provider selection (policy routing) decisions.
The Pip Header encodes addresses as a series of separate numbers, one number for each level of hierarchy. This can be contrasted to traditional packet encodings of addresses, which places the entire address into one field. Because of Pip's encoding, it is not necessary to specify a format for a Pip Address as it is with traditional addresses (for instance, the SIP address is formatted such that the first so-many bits are the country/metro code, the next so-many bits are the site/subscriber, and so on). Pip's encoding also eliminates the "cornering in" effect of running out of space in one part of the hierarchy even though there is plenty of room in another. No "field sizing" decisions need be made at all with Pip Addresses. This makes address assignment easier and more flexible than with traditional addresses. Pip Addresses are carried in DNS as a series of numbers, usually with each number representing a layer of the hierarchy [1], but optionally with the initial number(s) representing a "route fragment" (the tail end of a policy route--a source route whose elements are providers). The route fragments would be used, for instance, when the destination network's directly attached (local access) provider is only giving access to other (long distance) providers, but the important provider-selection policy decision has to do the long distance providers. The RC for (hierarchical) Pip Addresses is defined as: bits meaning ---- ------- 0,1 Pip Address (= 00) 2,3 level 4,5 metalevel 6 exit routing type The level and metalevel subfields are used to indicate what level of the hierarchy the packet is currently at (see section 8). The exit routing type subfield is used to indicate whether host-driven (hosts decide exit provider) or router-driven (routers decide exit provider) exit routing is in effect (see section 8.1). Each FTIF in the FTIF Chain is 16 bits in length. The low-order part of each FTIF in a (hierarchical unicast) Pip Address indicates the relationship of the FTIF with the next FTIF. The three relators are Vertical, Horizontal, and Extension. The Vertical and Horizontal relators indicate if the subsequent FTIF is hierarchically above or below (Vertical) or hierarchically unrelated (Horizontal). The Extension relator is used to encode FTIF values longer than 16 bits.
FTIF values 0 - 31 are reserved for special purposes. That is, they cannot be assigned to normal hierarchical elements. FTIF value 1 is defined as a flag to indicate a switch from the unicast phase of packet forwarding to the anycast phase of packet forwarding. Note that Pip Addresses do not need to be seen by protocol layers above Pip (though layers above Pip can provide a Pip Address if desired). Transport and above use the Pip ID to identify the source and destination of a Pip packet. The Pip layer is able to map the Pip IDs (and other information received from the layer above, such as QOS) into Pip Addresses. The Pip ID can serve as the lowest level of a Pip Address. While this "bends the principal" of separating Pip Addressing from Pip Identification, it greatly simplifies dynamic host address assignment. The Pip ID also serves as a multicast ID. Unless otherwise stated, the term "Pip Address" refers to just the part in the Routing Directive (that is, excludes the Pip ID). Pip Addresses are provider-rooted (as opposed to geographical). That is, the top-level of a Pip Address indicates a network service provider (even when the service provided is not Pip). (A justification of using provider-rooted rather than geographical addresses is given in [12].) Thus, the basic form of a Pip address is: providerPart,subscriberPart where both the providerPart and subscriberPart can have multiple layers of hierarchy internally. A subscriber may be attached to multiple providers. In this case, a host can end up with multiple Pip Addresses by virtue of having multiple providerParts: providerPart1,subscriberPart providerPart2,subscriberPart providerPart3,subscriberPart This applies to the case where the subscriber network spans many different provider areas, for instance, a global corporate network. In this case, some hosts in the global corporate network will have certain providerParts, and other hosts will have others. The subscriberPart should be assigned such that routing can successfully take place without a providerPart in the destination Pip Address of the Pip Routing Directive (see section 8.2).
Note that, while there are three providerParts shown, there is only
one subscriberPart. Internal subscriber numbering should be
independent of the providerPart. Indeed, with the Pip architecture,
it is possible to address internal packets without including any of
the providerPart of the address.
Top-level Pip numbers can be assigned to subscriber networks as well
as to providers.
privatePart,subscriberPart
In this case, however, the top-level number (privatePart) would not
be advertised globally. The purpose of such an assignment is to give
a private network "ownership" of a globally unique Pip Address space.
Note that the privatePart is assigned as an extended FTIF (that is,
from numbers greater than 2^15). Because the privatePart is not
advertised globally, and because internal packets do not need the
prefix (above the subscriberPart), the privatePart actually never
appears in a Pip packet header.
Pip Addresses can be prepended with a route fragment. That is, one
or more Pip numbers that are all at the top of the hierarchy.
longDistanceProvider.localAccessProvider.subscriber
(top-level) (top-level) (next level)
This is useful, for instance, when the subscriber's directly attached
provider is a "local access" provider, and is not advertised
globally. In this case, the "long distance" provider is prepended to
the address even though the local access provider number is enough to
provide global uniqueness.
Note that no coordination is required between the long distance and
local access providers to form this address. The subscriber with a
prefix assigned to it by the local access provider can autonomously
form and use this address. It is only necessary that the long
distance provider know how to route to the local access provider.
4.1.1 Assignment of (Hierarchical) Pip Addresses
Administratively, Pip Addresses are assigned as follows [3]. There
is a root Pip Address assignment authority. Likely choices for this
are IANA or ISOC. The root authority assigns top-level Pip Address
numbers. (A "Pip Address number" is the number at a single level of
the Pip Address hierarchy. A Pip Address prefix is a series of
contiguous Pip Address numbers, starting at the top level but not
including the entire Pip Address. Thus, the top-level prefix is the
same thing as the top-level number.)
Though by-and-large, and most importantly, top-level assignments are made to providers, each country is given an assignment, each existing address space (such as E.164, X.121, IP, etc.) is given an assignment, and private networks can be given assignments. Thus, existing addresses can be grandfathered in. Even if the top-level Pip address number is an administrative rather than topological assignment, the routing algorithm still advertises providers at the top (provider) level of routing. That is, routing will advertise enough levels of hierarchy that providers know how to route to each other. There must be some means of validating top-level number requests from providers (basically, those numbers less than 2^15). That is, top- level assignments must be made only to true providers. While designing the best way to do this is outside the scope of this document, it seems off hand that a reasonable approach is to charge for the top-level prefixes. The charge should be enough to discourage non-serious requests for prefixes, but not so much that it becomes an inhibitor to entry in the market. The charge might include a yearly "rent", and top-level prefixes could be reclaimed when they are no longer used by the provider. Any profit made from this activity could be used to support the overall role of number assignment. Since roughly 32,000 top-level assignments can be made before having to increase the FTIF size in the Pip header from 16 bits to 32 bits, it is envisioned that top-level prefixes will not be viewed as a scarce resource. After a provider obtains a top-level prefix, it becomes an assignment authority with respect to that particular prefix. The provider has complete control over assignments at the next level down (the level below the top-level). The provider may either assign top-level minus one prefixes to subscribers, or preferably use that level to provide hierarchy within the provider's network (for instance, in the case where the provider has so many subscribers that keeping routing information on all of them creates a scaling problem). It is envisioned that the subscriber will have complete control over number assignments made at levels below that of the prefix assigned it by the provider. Assigning top level prefixes directly to providers leaves the number of top-level assignments open-ended, resulting in the possibility of scaling problems at the top level. While it is expected that the number of providers will remain relatively small (say less than 10000 globally), this can't be guaranteed. If there are more providers than top-level routing can handle, it is likely that many of these providers will be "local access" providers--providers whose role is to give a subscriber access to multiple "long-distance" providers. In this case, the local access providers need not appear at the top
level of routing, thus mitigating the scaling problem at that level. In the worst case, if there are too many top-level "long-distance" providers for top-level routing to handle, a layer of hierarchy above the top-level can be created. This layer should probably conform to some policy criteria (as opposed to a geographical criteria). For instance, backbones with similar access restrictions or type-of- service can be hierarchically clustered. Clustering according to policy criteria rather than geographical allows the choice of address to remain an effective policy routing mechanism. Of course, adding a layer of hierarchy to the top requires that all systems, over time, obtain a new providerPart prefix. Since Pip has automatic prefix assignment, and since DNS hides addresses from users, this is not a debilitating problem. 4.1.2 Host Addressing Hosts can have multiple Pip Addresses. Since Pip Addresses are topologically significant, a host has multiple Pip Addresses because it exists in multiple places topologically. For instance, a host can have multiple Pip addresses because it can be reached via multiple providers, or because it has multiple physical interfaces. The address used to reach the host influences the path to the host. Locally, Pip Addressing is similar to IP Addressing. That is, Pip prefixes are assigned to subnetworks (where the term subnetwork here is meant in the OSI sense. That is, it denotes a network operating at a lower layer than the Pip layer, for instance, a LAN). Thus, it is not necessary to advertise individual hosts in routing updates-- routers only need to advertise and store routes to subnetworks. Unlike IP, however, a single subnetwork can have multiple prefixes. (Strictly speaking, in IP a single subnetwork can have multiple prefixes, but a host may not be able to recognize that it can reach another host on the same subnetwork but with a different prefix without going through a router.) There are two styles of local Pip Addressing--one where the Pip Address denotes the host, and another where the Pip Address denotes only the destination subnetwork. The latter style is called ID- tailed Pip Addressing. With ID-tailed Pip Addresses, the Pip ID is used by the last router to forward the packet to the host. It is expected that ID-tailed Pip Addressing is the most common, because it greatly eases address administration. (Note that the Pip Routing Directive can be used to route a Pip packet internal to a host. For instance, the RD can be used to direct a packet to a device in a host, or even a certain memory
location. The use of the RD for this purpose is not part of this near-term Pip architecture. We note, however, that this use of the RD could be locally done without effecting any other Pip systems.) When a router receives a Pip packet and determines that the packet is destined for a host on one of its' attached subnetworks (by examining the appropriate FTIF), it then examines the destination Pip ID (which is in a fixed position) and forwards based on that. If it does not know the subnetwork address of the host, then it ARPs, using the Pip ID as the "address" in the ARP query. 4.2 CBT Style Multicast Addresses When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 10, the FTIF and Dest ID indicate CBT (Core Based Tree) style multicast. The remainder of the bits are defined as follows: bits meaning ---- ------- 0,1 CBT Multicast (= 10) 2,3 level 4,5 metalevel 6 exit routing type 7 on-tree bit 8,9 scoping With CBT (Core-based Tree) multicast, there is a single multicast tree connecting the members (recipients) of the multicast group (as opposed to Class-D style multicast, where there is a tree per source). The tree emanates from a single "core" router. To transmit to the group, a packet is routed to the core using unicast routing. Once the packet reaches a router on the tree, it is multicast using a group ID. Thus, the FTIF Chain for CBT multicast contains the (Unicast) Hierarchical Pip Address of the core router. The Dest ID field contains the group ID. A Pip CBT packet, then, has two phases of forwarding, a unicast phase and a multicast phase. The "on-tree" bit of the RC indicates which phase the packet is in. While in the unicast phase, the on-tree bit is set to 0, and the packet is forwarded similarly to Pip Addresses. During this phase, the scoping bits are ignored.
Once the packet reaches the multicast tree, it switches to multicast routing by changing the on-tree bit to 1 and using the Dest ID group address for forwarding. During this phase, bits 2-6 are ignored. 4.3 Class D Style Multicast Addresses When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 01, the FTIF and Dest ID indicate Class D style multicast. The remainder of the RC is defined as: bits meaning ---- ------- 0,1 Class D Style Multicast (= 01) 2-5 Scoping By "class D" style multicast, we mean multicast using the algorithms developed for use with Class D addresses in IP (class D addresses are not used per se). This style of routing uses both source and destination information to route the packet (source host address and destination multicast group). For Pip, the FTIF Chain holds the source Pip Address, in order of most significant hierarchy level first. The reason for putting the source Pip Address rather than the Source ID in the FTIF Chain is that use of the source Pip Address allows the multicast routing to take advantage of the hierarchical source address, as is being done with IP. The Dest ID field holds the multicast group. The Routing Context indicates Class-D style multicast. All routers must first look at the FTIF Chain and Dest ID field to route the packet on the tree. Bits 2 through 5 of the RC are the scoping bits. 4.4 Anycast Addressing When bits 1 and 0 of the RC defined by RC Contents = 1 are set to 11, the FTIF and Dest ID indicate Anycast addressing. The remainder of the RC is defined as:
bits meaning
---- -------
0,1 Anycast Address (= 11)
2,3 level
4,5 metalevel
6 exit routing type
7 anycast active
8,9 scoping
With anycast routing, the packet is unicast, but to the nearest of a
group of destinations. This type of routing is used by Pip for
autoconfiguration. Other applications, such as discovery protocols,
may also use anycast routing.
Like CBT, Pip anycast has two phases of operation, in this case the
unicast phase and the anycast phase. The unicast phase is for the
purpose of getting the packet into a certain vicinity. The anycast
phase is to forward the packet to the nearest of a group of
destinations in that vicinity.
Thus, the RC has both unicast and anycast information in it. During
the unicast phase, the anycast active bit is set to 0, and the packet
is forwarded according to the rules of Pip Addressing. The scoping
bits are ignored.
The switch from the unicast phase to the anycast phase is triggered
by the presence of an FTIF of value 1 in the FTIF Chain. When this
FTIF is reached, the anycast active bit is set to 1, the scoping bits
take effect, and bits 2 through 6 are ignored. When in the anycast
phase, forwarding is based on the Dest ID field.
5. Pip IDs
The Pip ID is 64-bits in length [4].
The basic role of the Pip ID is to identify the source and
destination host of a Pip Packet. (The other role of the Pip ID is
for allowing a router to find the destination host on the destination
subnetwork.)
This having been said, it is possible for the Pip ID to ultimately
identify something in addition to the host. For instance, the Pip ID
could identify a user or a process. For this to work, however, the
Pip ID has to be bound to the host, so that as far as the Pip layer
is concerned, the ID is that of the host. Any additional use of the
Pip ID is outside the scope of this Pip architecture.
The Pip ID is treated as flat. When a host receives a Pip packet, it compares the destination Pip ID in the Pip header with its' own. If there is a complete match, then the packet has reached the correct destination, and is sent to the higher layer protocol. If there is not a complete match, then the packet is discarded, and a PCMP Invalid Address packet is returned to the originator of the packet [7]. It is something of an open issue as to whether or not Pip IDs should contain significant organizational hierarchy information. Such information could be used for inverse DNS lookups and allowing a Pip packet to be associated with an organization. (Note that the use of the Pip ID alone for this purpose can be easily spoofed. By cross checking the Pip ID with the Pip Address prefix, spoofing is harder- -as hard as it is with IP--but still easy. Section 14.2 discusses methods for making spoofing harder still, without requiring encryption.) However, relying on organizational information in the Pip header generally complicates ID assignment. This complication has several ramifications. It makes host autoconfiguration of hosts harder, because hosts then have to obtain an assignment from some database somewhere (versus creating one locally from an IEEE 802 address, for instance). It means that a host has to get a new assignment if it changes organizations. It is not clear what the ramifications of this might be in the case of a mobile host moving through different organizations. Because of these difficulties, the use of flat Pip IDs is currently favored. Blocks of Pip ID numbers have been reserved for existing numbering spaces, such as IP, IEEE 802, and E.164. Pip ID numbers have been assigned for such special purposes such as "any host", "any router", "all hosts on a subnetwork", "all routers on a subnetwork", and so on. Finally, 32-bit blocks of Pip ID numbers have been reserved for each country, according to ISO 3166 country code assignments. 6. Use of DNS The Pip near-term architecture uses DNS in roughly the same style that it is currently used. In particular, the Pip architecture maintains the two fundamental DNS characteristics of 1) information stored in DNS does not change often, and 2) the information returned by DNS is independent of who requested it. While the fundamental use of DNS remains roughly the same, Pip's use of DNS differs from IP's use by degrees. First, Pip relies on DNS to
hold more types of information than IP [1]. Second, Pip Addresses in DNS are expected to change more often than IP addresses, due to reassignment of Pip Address prefixes (the providerPart). To still allow aggressive caching of DNS records in the face of more quickly changing addressing, Pip has a mechanism of indicating to hosts when an address is no longer assigned. This triggers an authoritative query, which overrides DNS caches. The mechanism consists of PCMP Packet Not Delivered messages that indicate explicitly that the Pip Address is invalid. In what follows, we first discuss the information contained in DNS, and then discuss authoritative queries. 6.1 Information Held by DNS The information contained in DNS for the Pip architecture is: 1. The Pip ID. 2. Multiple Pip Addresses 3. The destination's mobile host address servers. 4. The Public Data Network (PDN) addresses through which the destination can be reached. 5. The Pip/IP Translators through which the destination (if the destination is IP-only) can be reached. 6. Information about the providers represented by the destination's Pip addresses. This information includes provider name, the type of provider network (such as SMDS, ATM, or SIP), and access restrictions on the provider's network. The Pip ID and Addresses are the basic units of information required for carriage of a Pip packet. The mobile host address server tells where to send queries for the current address of a mobile Pip host. Note that usually the current address of the mobile host is conveyed by the mobile host itself, thus a mobile host server query is not usually required. The PDN address is used by the entry router of a PDN to learn the PDN address of the next hop router. The entry router obtains the PDN address via an option in the Pip packet. If there are multiple PDNs associated with a given Pip Address, then there can be multiple PDN addresses carried in the option. Note that the option is not sent on every packet, and that only the PDN entry router need examine the
option. The Pip/IP translator information is used to know how to translate an IP address into a Pip Address so that the packet can be carried across the Pip infrastructure. If the originating host is IP, then the first IP/Pip translator reached by the IP packet must query DNS for this information. The information about the destination's providers is used to help the "source" (either the source host or a Pip Header Server near the source host) format an appropriate Pip header with regards to choosing a Pip Address [14]. The choice of one of multiple Pip Addresses is essentially a policy routing choice. More detailed descriptions of the use of the information carried in DNS is contained in the relevant sections. 6.2 Authoritative Queries in DNS In general, Pip treats addresses as more dynamic entities than does IP. One example of this is how Pip Address prefixes change when a subscriber network attaches to a new provider. Pip also carries more information in DNS, any of which can change for various reasons. Thus, the information in DNS is more dynamic with Pip than with IP. Because of the increased reliance on DNS, there is a danger of increasing the load on DNS. This would be particularly true if the means of increasing DNS' dynamicity is by shortening the cache holding time by decreasing the DNS Time-to-Live (TTL). To counteract this trend, Pip provides explicit network layer (Pip layer) feedback on the correctness of address information. This allows Pip hosts to selectively over-ride cached DNS information by making an authoritative query. Through this mechanism, we actually hope to increase the cache holding time of DNS, thus improving DNS' scaling characteristics overall. The network layer feedback is in the form of a type of PCMP Packet Not Delivered (PDN) message that indicates that the address used is known to be out-of-date. Routers can be configured with this information, or it can be provided through the routing algorithm (when an address is decommissioned, the routing algorithm can indicate that this is the reason that it has become unreachable, as opposed to becoming "temporarily" unreachable through equipment failure). Pip hosts consider destination addresses to be in one of four states:
1. Unknown, but assumed to be valid. 2. Reachable (and therefore valid). 3. Unreachable and known to be invalid. 4. Unreachable, but weakly assumed to be valid. The first state exists before a host has attempted communication with another host. In this state, the host queries DNS as normal (that is, does not make an authoritative query). The second state is reached when a host has successfully communicated with another host. Once a host has reached this state, it can stay in it for an arbitrarily long time, including after the DNS TTL has expired. When in this state, there is no need to query DNS. A host enters the third state after a failed attempt at communicating with another host where the PCMP PND message indicates explicitly that the address is known to be invalid. In this case, the host makes an authoritative query to DNS whether or not the TTL has expired. It is this case that allows lengthy caching of DNS information while still allowing addresses to be reassigned frequently. A host enters the fourth state after a failed attempt at communicating with another host, but where the address is not explicitly known to be invalid. In this state, the host weakly assumes that the address of the destination is still valid, and so can requery DNS with a normal (non-authoritative) query. 7. Type-of-Service (TOS) (or lack thereof) One year ago it probably would have been adequate to define a handful (4 or 5) of priority levels to drive a simple priority FIFO queue. With the advent of real-time services over the Internet, however, this is no longer sufficient. Real-time traffic cannot be handled on the same footing as non-real-time. In particular, real-time traffic must be subject to access control so that excess real-time traffic does not swamp a link (to the detriment of other real-time and non- real-time traffic alike). Given that a consensus solution to real- and non-real-time traffic management in the internet does not exist, this version of the Pip near-term architecture does not specify any classes of service (and related queueing mechanisms). It is expected that Pip will define classes of service (primarily for use in the Handling Directive) as solutions become available.
8. Routing on (Hierarchical) Pip Addresses Pip forwarding in a single router is done based on one or a small number of FTIFs. What this means with respect to hierarchical Pip Addresses is that a Pip router is able to forward a packet based on examining only part of the Pip Address--often a single level. One advantage to encoding each level of the Pip Address separately is that it makes handling of addresses, for instance address assignment or managing multiple addresses, easier. Another advantage is address lookup speed--the entire address does not have to be examined to forward a packet (as is necessary, for instance, with traditional hierarchical address encoding). The cost of this, however, is additional complexity in keeping track of the active hierarchical level in the Pip header. Since Pip Addresses allow reuse of numbers at each level of the hierarchy, it is necessary for a Pip router to know which level of the hierarchy it is acting at when it retrieves an FTIF. This is done in part with a hierarchy level indicator in the Routing Context (RC) field. RC level is numbered from the top of the hierarchy down. Therefore, the top of the hierarchy is RC level = 0, the next level down is RC level = 1, and so on. The RC level alone, however, is not adequate to keep track of the appropriate level in all cases. This is because different parts of the hierarchy may have different numbers of levels, and elements of the hierarchy (such as a domain or an area) may exist in multiple parts of the hierarchy. Thus, a hierarchy element can be, say, level 3 under one of its parents and level 2 under another. To resolve this ambiguity, the topological hierarchy is superimposed with another set of levels--metalevels [11]. A metalevel boundary exists wherever a hierarchy element has multiple parents with different numbers of levels, or may with reasonable probability have multiple parents with different numbers of levels in the future. Thus, a metalevel boundary exists between a subscriber network and its provider. (Note that in general the metalevel represents a significant administrative boundary between two levels of the topological hierarchy. It is because of this administrative boundary that the child is likely to have multiple parents.) Lower metalevels may exist, but usually will not. The RC, then, contains a level and a metalevel indicator. The level indicates the number of levels from the top of the next higher metalevel. The top of the global hierarchy is metalevel 0, level 0. The next level down (for instance, the level that provides a level of
hierarchy within a provider) is metalevel 0, level 1. The first level of hierarchy under a provider is metalevel 1, level 0, and so on. To determine the RC level and RC metalevel in a transmitted Pip packet, a host (or Pip Header Server) must know where the metalevels are in its own Pip Addresses. The host compares its source Pip Address with the destination Pip Address. The highest Pip Address component that is different between the two addresses determines the level and metalevel. (No levels higher than this level need be encoded in the Routing Directive.) Neighbor routers are configured to know if there is a level or metalevel boundary between them, so that they can modify the RC level and RC metalevel in a transmitted packet appropriately. 8.1 Exiting a Private Domain The near-term Pip Architecture provides two methods of exit routing, that is, routing inter-domain Pip packets from a source host to a network service provider of a private domain [12,15]. 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. In either method, it is possible to prevent internal routers from having to carry external routing information. The exit routing bit of the RC indicates which type of exit routing is in effect. With host-driven exit routing, it is possible for the host to choose a provider through which the destination cannot be reached. In this case, the host receives the appropriate PCMP Packet Not Delivered message, and may either fallback on transit-driven exit routing or choose a different provider. When using transit-driven exit routing, there are two modes of operation. The first, called destination-oriented, is used when the routers internal to a domain have external routing information, and the host has only one provider prefix. The second, called provider- oriented, is used when the routers internal to a domain do not have any external routing information or when the host has multiple provider prefixes. (With IP, this case is called default routing. In the case of IP, however, default routing does not allow an intelligent choice of multiple exit points.) With provider-oriented exit routing, the host arbitrarily chooses a source Pip Address (and therefore, a provider). (Note that if the
Pip Header Server is tracking inter-domain routing, then it chooses the appropriate provider.) If the host chooses the wrong provider, then the border router will redirect the host to the correct provider with a PCMP Provider Redirect message. 8.2 Intra-domain Networking With intra-domain networking (where both source and destination are in the private network), there are two scenarios of concern. In the first, the destination address shares a providerPart with the source address, and so the destination is known to be intra-domain even before a packet is sent. In the second, the destination address does not share a providerPart with the source address, and so the source host doesn't know that the destination is reachable intra-domain. Note that the first case is the most common, because the private top-level number assignment acts as the common prefix even though it isn't advertised globally (see section 4.1). In the first case, the Pip Addresses in the Routing Directive need not contain the providerPart. Rather, it contains only the address part below the metalevel boundary. (A Pip Address in an FTIF Chain always starts at a metalevel boundary). For instance, if the source Pip Address is 1.2.3,4.5.6 and the destination Pip Address is 1.2.3,4.7.8, then only 4.7.8 need be included for the destination address in the Routing Directive. (The comma "," in the address indicates the metalevel boundary between providerPart and subscriberPart.) The metalevel and level are set accordingly. In the second case, it is desirable to use the Pip Header Server to determine if the destination is intra-domain or inter-domain. The Pip Header Server can do this by monitoring intra-domain routing. (This is done by having the Pip Header Server run the intra-domain routing algorithm, but not advertise any destinations.) Thus, the Pip Header Server can determine if the providerPart can be eliminated from the address, as described in the last paragraph, or cannot and must conform to the rules of exit routing as described in the previous section. If the Pip Header Server does not monitor intra-domain routing, however, then the following actions occur. In the case of host- driven exit routing, the packet will be routed to the stated provider, and an external path will be used to reach an internal destination. (The moral here is to not use host-driven exit routing unless the Pip Header Server is privy to routing information, both internal and external.)
In the case of transit-driven exit routing, the packet sent by the host will eventually reach a router that knows that the destination is intra-domain. This router will forward the packet towards the destination, and at the same time send a PCMP Reformat Transit Part message to the host. This message tells the host how much of the Pip Address is needed to route the packet.
(page 25 continued on part 2)