HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 06:18:55 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Wed, 09 Dec 1992 04:36:00 GMT ETag: "3dde11-8379-2b2577b0" Accept-Ranges: bytes Content-Length: 33657 Connection: close Content-Type: text/plain Network Working Group P. Tsuchiya INTERNET-DRAFT Bellcore November 1992 Pip Header Processing 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 defines the Pip header processing for Routers and Hosts. Acknowledgements I want to individually acknowledge Rob Coltun, Steve Deering, Joel Halpern, John Ioannidis, Chris Petrilli, Bob Smart, and Zheng Wang. I want also to acknowledge the many people from the Pip working group who have participated in developing Pip. Conventions All functions in this specification are mandatory. Pip WG, Expires May. 1, 1993 [Page 1] INTERNET-DRAFT Pip Header November 1992 1. Introduction Pip is an internet protocol intended as the replacement for IP ver- sion 4. Pip is a general purpose internet protocol, designed to han- dle all forseeable internet protocol requirements. This specifica- tion defines the Pip header processing for Routers and Hosts. The design of Pip is fundamentally different from that of previous internetwork protocols. Pip is designed to be as general as possi- ble, but without significantly compromising performance. Because of Pip's generality, it can handle forseeable routing and addressing requirements. It is hoped that it will be able to handle most if not all future routing and addressing requirements. There are many detailed aspects of Pip that provide this generality that are not discussed here. It is useful, however, to mention one general aspect. That is, Pip strives to remove as much "functional semantics" from the base specification as possible. Pip defines a packet header and forwarding rules that can include many different functional semantics (that is, routing, addressing, and flow para- digms). Therefore, the reader may often find him or herself asking "But how do you do foo with Pip?" The answer to this sort of question belongs in companion documents to the basic Pip spec. Pip can be thought of as a mechanism for triggering actions in hosts and routers, just as a machine language can be thought of as a mechanism for triggering actions in CPUs. The machine language has no functional semantics outside of the specific actions it triggers (move this register, write that memory location, etc.). But, the machine language is a very powerful tool upon which functional seman- tics are built. Likewise, Pip is a powerful tool upon which routing, addressing, and flow functions can be built. 2. Definitions Pip system: A Pip-capable host or router. Routing Directive: That part of the Pip header starting with the Routing Context field and ending with the first Router Option (or Host Part, if there are no Router Options). Pip WG, Expires May. 1, 1993 [Page 2] INTERNET-DRAFT Pip Header November 1992 Target system: The Pip system for which the Pip header is intended. This definition is used in conjunction with tunneling, where an encapsulated Pip header is "targeted" for a Pip system more than one internet hop away. In the case where no tunneling is used, the receiving host is the target system (excepting the case where the Pip header is in error). High and Low (in the context of Tunneling): When Routing Parts are recursively encapsulated, the "lower" Router Part encapsulates the "higher" Router Part. 3. Pip Specification The Pip header is partitioned into five parts, the Misc Part, the Router Part, the Router Options, the Host Part, and the Host Options: +===========================+ | Misc Part | +===========================+ | Router Part | +===========================+ | Router Options | +===========================+ | Host Part | +===========================+ | Host Options | +===========================+ | | | Payload | | | Each part falls on a 32-bit boundary (as indicated by the double lines shown). When a router receives a Pip packet, it does not need to look at Host Part or Host Options for the purposes of normal (no Router Options) packet forwarding and flow handling. Depending on the Router Option, a router may need to look at the host parts of the Pip header (for instance, for fragmentation). Routers may, however, wish to look at the Host parts or even higher layers for the purpose of filtering, billing, or whatever. When a host receives a Pip packet, it must look at all parts. The Pip header is designed to make forwarding and flow handling by routers efficient, but not Pip WG, Expires May. 1, 1993 [Page 3] INTERNET-DRAFT Pip Header November 1992 looking at "higher layer" information (including the host parts, even though the host parts are not strictly higher layer in terms of a protocol identifier and such). The concept of tunneling in an integral part of Pip. Pip achieves tunneling by encapsulating the Router Part of the Pip header in another Router Part. Therefore, when tunneling, there is one Router Part for each (nested) tunnel: +===========================+ | Misc Part | +===========================+ | Router Part | +===========================+ | Router Part | +===========================+ . . . +===========================+ | Router Part | +===========================+ | Router Options | +===========================+ | Host Part | +===========================+ | Host Options | +===========================+ Because each Router Part has only what is necessary for router for- warding and handling, this method of tunneling is reasonably effi- cient in terms of packet size. 3.1. Misc Part The Misc Part is formatted as below: Pip WG, Expires May. 1, 1993 [Page 4] INTERNET-DRAFT Pip Header November 1992 length, in bits +===========================+ | 7 | 4 +---------------------------+ | Sub-Version | 4 +---------------------------+ | Options Present | 1 +---------------------------+ | Options/Host Part Offset | 11 +---------------------------+ | Hop Count | 12 +===========================+ An explanation of each field follows. 3.1.1. Version Numbers The first octet is divided into two 4-bit fields, the Version and the Sub-Version. The Version field is set to be 7, and is meant to be version 7 of IP. Thus, all encapsulation schemes defined for IP can work for Pip as well. The Sub-Version field is set to the value 0 for the version of Pip defined in this specification. 3.1.2. Options Present When the Options Present bit is set to 0, there are no Router Options present. When the Options Present bit is set to 1, there are Router Options present. 3.1.3. Options/Host Part Offset The Options/Host Part Offset indicates the position of the first non-Router Part word. The unit of measure of the Options/Host Part Offset is 32-bit words, counting the first word containing an FTIF as word 0. That is, if the Options/Host Part Offset is 0, then there is only one Router Part, and that Router Part has no FTIFs. If the Options Present bit is 1, then the Options/Host Part Offset indicates the position of the first Router Option. If the Options Present bit Pip WG, Expires May. 1, 1993 [Page 5] INTERNET-DRAFT Pip Header November 1992 is 0, then the Options/Host Part Offset indicates the position of the Host Part. Note that if Router Options are present, then the first Router Option will indicate the position of the Host Part. If a Pip system encapsulates a Pip Router Part in another Pip Router Part, then the Options/Host Part Offset in the new Router Part must be increased by the length of the new Router Part. This allows sub- sequent routers to find the position of the Router Options easily. 3.1.4. Hop Count The Hop Count is decremented by every router that forwards the Pip packet. If a system receives a Pip header with a Hop Count equal to 0, and is not the recipient of the packet, then the packet is dis- carded and a PCMP Destination Unreachable is routed to the system indicated by the Routing Directive. (In other words, a host can legally receive a Router Part with a Hop Count of 0.) 3.2. Router Part The Router Part is formatted as shown in Figure 1. An explanation of each field follows. 3.2.1. HD/RC Epoch This field is used to verify that the Pip system that sent the packet correctly understood the mapping of the receiving system's Handling Directive and Routing Context. When a Pip system redifines its Han- dling Directive and Routing Context mapping, it may not be able to tell all other systems that are still holding the old mapping. By incrementing the HD/RC Epoch field when a new mapping is defined, a Pip system can recognize when the received packet is using the wrong mapping. Before a Pip system processes the Handling Directive and Routing Directive, it compares the HD/RC Epoch field with the current HD/RC Epoch. If they do not match, then a PCMP HD/RC Epoch Mismatch is Pip WG, Expires May. 1, 1993 [Page 6] INTERNET-DRAFT Pip Header November 1992 length, in bits +===========================+ | HD/RC Epoch | 16 +---------------------------+ | Routing Context (RC) | 16 +===========================+ | FTIF Length | 2 +---------------------------+ | FTIF Offset | 6 +---------------------------+ | Handling Directive (HD) | 24 +===========================+ | FTIF 1 | Variable +---------------------------+ | FTIF 2 | Variable +---------------------------+ . . . +---------------------------+ | FTIF N | Variable +---------------------------+ | Padding | Variable +===========================+ Figure 1: Router Part transmitted to the sending Pip system. 3.2.2. Handling Directive (HD) The HD is a general purpose field used for the purpose of triggering special packet handling by a Pip system. The HD field does not influence a Pip router's next hop choice for a Pip packet, nor does it influence a Pip host's determination as to whether the Pip packet is destined for it. Examples of special packet handling would be "low priority queueing", or "high priority discard", etc. Both hosts and routers use the HD field. (Hosts may make use of the HD field for packet handling for both incoming and outgoing packets.) Pip WG, Expires May. 1, 1993 [Page 7] INTERNET-DRAFT Pip Header November 1992 The HD field makes a complete distinction between the syntax and the semantics of the HD field. (This can be contrasted with, for instance, IP, which couples the semantics and syntax of the TOS bits. That is, the IP specification itself determines, to a first degree, how the TOS bits should be interpreted.) Indeed, each Pip system has its own interpretation of the HD field, and one Pip system must modify the HD field to match the next hop Pip system's interpreta- tion. In addition, each Pip system can modify the semantic meaning of the HD, for instance, by increasing or decreasing the queueing priority of a packet. From an abstract modeling perspective, the HD is handled as follows: 1. Extract the semantic meaning(s) (the handling instructions) from the HD. Transmitting Pip hosts must determine the semantic meaning from another source, such as the upper layer protocol. If the receiving system decapsulates multiple Pip headers, then the HD semantics are extracted from the lowest Pip header for which it is not the target (see example on tunneling below). 2. Handle the Pip packet according to those instructions. 3. Modify the semantic meaning if necessary. 4. Map the (potentially new) semantic meaning into the HD syntax expected by the next hop Pip systems (receiving Pip hosts skip this step). Note that if the Pip header is to be encapsulated in another Pip header for the purposes of tunneling, then there are two (or more, if multiple encapsulations) next hop systems- -one at the end of the tunnel (the target system for the encap- sulating Pip header), and the true next hop. The HD semantics are mapped into the HD syntax of the appropriate system. Note also that if the Pip packet is replicated for multicast, the HD must be individually mapped for each next hop. 3.2.3. Tunneling Consider two Pip systems, X and Y, separated by one or more inter- mediate Pip systems. X wishes to tunnel a Router Part to Y. Y is therefore the target system of the tunnel. A Router Part He arrives at X. In order to forward the Router Part to Y, X encapsulates He in another Router Part, Hy. Y is the target system for Router Part Hy. Pip WG, Expires May. 1, 1993 [Page 8] INTERNET-DRAFT Pip Header November 1992 X sets the HD of He to what it would have been if Y was directly con- nected to X (that is, there were no intermediate Pip systems between X and Y). Further, it is intended that Y will derive its HD seman- tics from the HD of Router Part He, not Router Part Hy. ----0-----o-----o-----o-----o-----0---- X I J K L Y Now consider the operation of Pip system L (the previous hop system to Y). When L forwards the packet to Y, it may either decapsulate the packet (in the knowledge that Y is the target for Hy), or not decapsulate the packet. Either way, L derives its HD semantics from the HD of Router Part He. If L does not decapsulate the Router Part, then it is as though I, J, K, and L are a "subnetwork" (albeit a Pip subnetwork), and Y is stripping the "subnetwork" header (Hy) off before processing the true Router Part (He). If L does decapsulate the Router Part, then, from Y's perspective, it is essentially as though Y were directly con- nected to X. 3.2.4. Routing Directive (RD) The RD consists of the Routing Context (RC), the FTIF Length, the FTIF Offset, and a series of zero or more FTIFs (Forwarding Table Index Fields). This series of FTIFs is called the FTIF Chain. The RC is used to either 1) determine how to forward the Pip packet, or 2) determine the context within which the FTIF should be evaluated. In the latter role, the RC can be thought of as selecting one of multiple forwarding tables, into which the active FTIF is then used as an index. The RC is interpreted according to the interface over which the Pip packet was received. The RC is handled similarly to the HD. That is, the syntax and semantics of the RC are separated. Each Pip system determines its own syntax for the RC, and knows the syntax for neighbor Pip systems so that it can translate the RC appropriately upon transmission. Pip WG, Expires May. 1, 1993 [Page 9] INTERNET-DRAFT Pip Header November 1992 The FTIF Length field indicates the length of each FTIF in the FTIF Chain (all FTIFs are the same length). FITFs can be one of three lengths, 8 bits, 16 bits, and 32 bits. The FTIF Length field is encoded as follows: FTIF Length value Actual FTIF length ----------------- ------------------ 0 8 bits 1 16 bits 2 32 bits The FTIF Offset field indicates which FTIF is active. The active FTIF is the one that is used to index the forwarding table indicated by the RC. An FTIF Offset value of 0 means that the first FTIF is active, an FTIF Offset value of 1 means that the second FTIF is active, and so on. If there are no FTIFs, then the FTIF Length and FTIF Offset have no meaning, and can be any value. In this case, the RC field itself will indicate how to forward the packet. Note that the FTIF Length concatenated with the FTIF Offset forms a 8-bit value that indicates the exact location of the active FTIF. Therefore, this 8-bit value can be used as an index into an array that gives information about the specific location of the active FTIF. The FTIF Chain is padded out to a 32-bit boundary. Note that there can be more than 32 bits of padding (for instance, if it is desirable to pad out to a 64-bit boundary). The padding is ignored upon receipt, and can be transmitted as any value (that is, it does not have to be any specific pattern of 0's or 1's). This formatting of FTIFs means that no FTIF less than or equal to 32-bits in length straddles a 32-bit boundary. As such, an FTIF of 32-bits or less can always be retrieved by accessing only one 32-bit word. 3.2.5. Router RD Forwarding Algorithm This section describes the forwarding algorithm for a Pip router. 1. Using the value of the RC field as an index, retrieve one or more of the following instructions (steps 2 - 4) from the Pip WG, Expires May. 1, 1993 [Page 10] INTERNET-DRAFT Pip Header November 1992 rcTable associated with the incoming interface. (The reason that more than one instruction might be retrieved is for the case where the packet is to be multicast.) 2. If one of the instructions is decapsulate, then decapsulate the Pip header and re-execute step 1 using the new header. 3. If one of the instructions is forward, then (possibly addition- ally) retrieve the associated Forwarding Information Block (FIB), and go to step 10. 4. If one of the instructions is to examine the FTIF Chain, then (possibly additionally) retrieve the forwardingTable indicated by the rcTable entry, and continue on to step 5. 5. Using the value of the FTIF indicated by the FTIF Offset as an index, retrieve one or more of the following instructions (steps 6 - 8) from the forwardingTable identified in step 4 or step 8. 6. If one of the instructions is decapsulate, then decapsulate the Pip header and re-execute step 1 using the new header (this is the same as step 2). 7. If one of the instructions is forward, then (possibly addition- ally) retrieve the associated Forwarding Information Block (FIB), and go to step 10 (this is the same as step 3). 8. If one of the instructions is to examine the next FTIF, then, according to the information in the current forwardingTable entry, modify the current FTIF and choose a new forwardingTable. 9. Increment the FTIF Offset and go to step 5. 10. The FIB contains a set of potential recipient for the Pip packet, including next hop Pip systems (both directly connected and at the end of Pip tunnels) and the Host Part processing of the local system. Taking into consideration the previous hop Pip system (as determined by the lower-layer source address and incoming interface) and potentially other local information (such as congestion on outgoing queues), prune the set of poten- tial next hops. (This may result in no pruning having taken place or in every potential next hop having been pruned.) 11. For each remaining next hop, format a Pip header by modifying a) the RC, b) the current FTIF, c) the FTIF Offset (either with a Pip WG, Expires May. 1, 1993 [Page 11] INTERNET-DRAFT Pip Header November 1992 completely new value or an addition or subtraction on the current value) and d) any Pip header encapsulations, according to the information in the FIB, and transmit the packet to the recipient (either next hop or Host Part processing). 3.3. Router Options The Router Options are formatted as shown in Figure 2. +===========================+ | Router Options Length | 32 +===========================+ | Option 2 | Variable +===========================+ | Option 3 | Variable +===========================+ . . . +===========================+ | Option N | Variable +===========================+ | Router Options Checksum | 32 +===========================+ Figure 2: Router Options Every Option is at least one 32-bit word in length, and ends on a 32-bit word boundary. Each option is formatted as follows: length, in bits +===========================+ | Router Option Type | 8 +---------------------------+ | Option Length | 6 +---------------------------+ | Action if Unrecognized | 2 +---------------------------+ | Option Data | Variable +===========================+ Pip WG, Expires May. 1, 1993 [Page 12] INTERNET-DRAFT Pip Header November 1992 The Option Type field indicates the type of Option. The Option Length field gives the length of the option in 32-bit words. The Action if Unrecognized (AU) determines what the Pip system should do if it does not recognize the Option, according to the following values: AU value Action -------- ------ 0 Ignore Option and continue processing 1 Silently discard packet 2 Discard Packet with Notification Defined Options The following Options are defined. 3.3.1. Router Options Length The Options Length option gives the number of 32-bit words comprised by all Router Options. It has Router Option Type = 1 and Option Length = 1. The AU is of type 1 (Silently discard packet). The Option Data is a single 16 bit value, and contains the length, in 32-bit words, of the combined Router Options (including the Options Length and Options Checksum options). The Options Length option is always the first option. If any Router Options are included, the Options Length option must be included. 3.3.2. Router Options Checksum The Options Checksum option has Router Option Type = 2 and Option Length = 1. The AU is of type 1 (Silently discard packet). The Option Data is a single 16 bit value, and contains the checksum value. The checksum algorithm is the same as that of IP. That is, the checksum field is the 16 bit one's complement of the one's complement Pip WG, Expires May. 1, 1993 [Page 13] INTERNET-DRAFT Pip Header November 1992 sum of all 16 bit words in the header. For purposes of computing the checksum, the value of the checksum field is zero. The Options Checksum option is always the last option. If any Router Options are included, the Options Checksum option must be included. 3.3.3. Fragmentation The Fragmentation Option has Router Option Type = 3 and Option Length = 2. The AU is of type 2. The Option Data is formatted as follows: length, in bits +---------------------------+ | | +=== Identification ===+ 26 +---------------------------+ | Send Max PDU Size | 1 +---------------------------+ | More Fragments | 1 +---------------------------+ | Fragment Offset | 20 +===========================+ The Identification, More Fragments, and Fragment Offset are used exactly as with IP, with the exception that the Fragment Offset is in units of 32 bits (not 64 bits, as with IP). That is, the Identifica- tion field identifies which packet this fragment belongs to. The More Fragments bit is 1 if there are more fragments, and 0 if it is the last fragment. The first fragment has offset 0. The Send Max PDU Size bit is 1 if the fragmenting router should return a Max PDU Size PCMP packet to the originating host, and 0 if the fragmenting router should not. If the Router Options does not contain a Fragmentation Option, then the packet cannot be fragmented. If fragmentation is necessary to forward the packet, then the packet is discarded rather than frag- mented, and a notification is sent to the orginating system. When a host creates a Fragmentation Option, it sets the Identifica- tion field to a value that must be unique for the combination of Source ID, Dest ID, and Protocol (these fields are all in the Host Part of the Pip header) for the lifetime of the packet. Each frag- ment of a fragmented Pip packet must modify the Payload Length field Pip WG, Expires May. 1, 1993 [Page 14] INTERNET-DRAFT Pip Header November 1992 to accurately indicate the length of the new payload. Each fragment of a fragmented Pip packet must contain the entire Pip header of the original (unfragmented) Pip header. 3.4. Host Part The Host Part is formatted as shown in Figure 3. length, in bits +===========================+ | Payload Length | 24 +---------------------------+ | Protocol | 8 +===========================+ | Dest ID | 64 +===========================+ | Source ID | 64 +===========================+ | Packet SubID | 8 +---------------------------+ | Host Version | 8 +---------------------------+ | Host Part Checksum | 16 +===========================+ Figure 3: Host Part The fields of the Host Part are defined as follows: 3.4.1. Payload Length The Payload Length gives the length of the Pip packet payload in units of 8 bits. The Payload Length does not include the length of the Pip header. 3.4.2. Protocol Indicates the protocol header found in the payload. The values for Pip WG, Expires May. 1, 1993 [Page 15] INTERNET-DRAFT Pip Header November 1992 this field are the same as those used for IPv4. 3.4.3. Dest and Source ID These are the identifiers of the source and destination of the packet. When a Pip system determines at forwarding time that a packet is destined for itself (based on the RD), it checks the Dest ID to verify if that packet is destined for it. If the complete Dest ID matches its own ID, then the packet is for it, and is passed to the layer indicated by the Protocol field. (The Pip system may of course wish to check a security option before passing a packet to an upper layer.) If the complete Dest ID field does not match its own ID, then an ID/RD Mismatch PCMP message is sent to the source of the packet. The purpose of this message is to flush the ID to RD binding in the source Pip host. The Source ID indicates the source of a packet. It is passed to upper layers for the purposes of identifying the context for the packet. The structure of the ID fields are defined in [ref]. For the purposes of running ARP, the ID fields are used as the proto- col addresses. Reserved The Reserved octet must be transmitted as all 0's and ignored upon receipt. 3.4.4. Packet SubID This field is used by Pip hosts to correctly associate received PCMP messages with local control blocks. This is necessary because the semantics of the Router Part can change while a packet is in transit. Therefore, a router sending a PCMP message cannot necessarily provide all of the information needed by the Pip host to correctly identify the context of the received message (that is, which "packet flow" it should be identified with). Pip WG, Expires May. 1, 1993 [Page 16] INTERNET-DRAFT Pip Header November 1992 A PCMP message uses the Protocol, Source ID, Dest ID, and Packet SubID to define the PCMP messages context. It is not sufficient to use just Protocol, Source ID, and Dest ID, because two hosts running the same protocol between them may have multiple "flows", for instance, a data flow, a video flow, and an audio flow in the case of multi-media. Each flow may have a different Router Part, and take different paths. Therefore, the Packet SubID field is needed to further differentiate. 3.4.5. Host Version The Host Version field indicates what "version" of Pip software the sending host has implemented. This is to allow a host to inform a router which ancillary protocols/messages the host is able to accept. It is envisioned that over time, new host functions will be developed. Different hosts will install these new functions at dif- ferent times. This field allows routers to know what functions the host can and cannot handle. 3.4.6. Host Options The Host Options are formatted exactly as the Router Options. The type field for the Host Options is called the Host Option Type. It contains different types from the Router Option Type field (that is, they are separate number spaces). As with the Router Options, the Options Length and Options Checksum options have Host Option Types 1 and 2 respectively. These options are used in the Host Options exactly as they are defined for the Router Options. Other host options needed.....Signature Option (for verifying sender of packet),....., timestamp, ..... Pip WG, Expires May. 1, 1993 [Page 17]