S. Deering (Xerox PARC) P. Francis (NTT) R. Govindan (Bellcore) January 1994 Simple Internet Protocol Plus (SIPP): Routing and Addressing 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. 1. INTRODUCTION This specification defines the routing and addressing architecture of SIPP. It describes the address formats for SIPP, and the rules for handling address sequences for both hosts and routers. The authors would like to acknowledge the contributions of Jim Bound (DEC), Bob Gilligan (Sun), Bob Hinden (Sun), Christian Huitema (INRIA), and Erik Nordmark (Sun), and Sue Thomson (Bellcore). 1.1. Terminology The terminology defined in the SIPP Specification [4] applies to this document. The first three terms below are copied from [4] for clar- ity. The following additional terminology is defined below that: address: A 64-bit SIPP layer identifier for a node or set of nodes. SIPP WG, Expires Aug 1, 1994 [Page 1] SIPP Routing and Addressing January 1994 An address can be used for both routing and identification purposes. uniqueness scope: The topologically defined region over which an address may be assigned to no more than one node or set of nodes. routing scope: The topologically defined region over which hosts and routers have sufficient routing information to forward a packet toward the node(s) identified by that address. route sequence: The sequence of addresses consisting of the source address, the destination address, and the addresses encoded in the optional Routing Header of the SIPP packet. address sequence: A sequence of addresses that forms part of the route sequence. The address sequence is used for the purpose of routing to a node in the case where a single (64-bit) address has insufficient routing scope. identifying address: The low-order address in an address sequence. Of the addresses in an address sequence, only the identifying address is used to identify the source and destination of a packet (for instance, by the transport protocol). 2. SIPP ADDRESSING SIPP addresses are 64-bit identifiers for nodes and sets of nodes. There are two types of address: Unicast: Causes a single packet to be sent to a single node (bar- ring unintentional loss or duplication). Usually uniquely identifies a single node (meaning that no other node shares that identifier). Sometimes uniquely identifies a group of nodes, for instance a cluster address. Sometimes non-uniquely identifies a single node, for instance a local-use address or SIPP address for IPv4-only nodes. Multicast: Uniquely identifies a set of nodes, and causes the packet to be sent to all of those nodes (barring unintentional loss or duplication). There are no broadcast addresses in SIPP, their function being super- seded by multicast addresses. SIPP WG, Expires Aug 1, 1994 [Page 2] SIPP Routing and Addressing January 1994 Nodes may have multiple unicast addresses and multiple multicast addresses. Each of a node's addresses is said to be "bound" to zero or more of that node's interfaces, including possibly zero. Whether or not an address may be bound to an interface depends on the routing environment in which the node is situated. As one example, consider a host (i.e., a non-router) with three interfaces, connected to two links (e.g., two Ethernets) as illustrated here: ================================== Link X | | i1| |i2 +----------+ | Host | +----------+ i3| | ================================== Link Y Assume the host has been allocated a unicast address with subnet pre- fix S. That address may be bound to EITHER or BOTH interfaces i1 and i2 only if at least one router attached to link X is advertising pre- fix S on that link (using ICMP Router Advertisement messages, as specified in [6]). The same address may be bound to interface i3 only if at least one router on link Y is advertising prefix S. If the prefix S is being advertised on both link X and link Y, the same address may be bound to any or all of the three interfaces. Even though an address MAY be bound to an interface, it is not REQUIRED to be bound to that interface. If it is desired that a dif- ferent address be bound to each each interface, as with IPv4, a node may be so configured. However, SIPP's relaxation of IPv4's strict one-address-per-interface model provides greater flexibility in con- figuring and managing addresses and subnets, allows conservation of addresses (as is sometimes accomplished in IPv4 routers, through the use of "unnumbered" or "not separately numbered" interfaces), and supports some new capabilities such as singly-addressed, multiply- attached servers and dynamic changing of address bindings to dif- ferent links by mobile hosts. From the addressing example above, it can also be noted that SIPP supports the use of the same subnet prefix across more than one link. Although subnets in IPv4 were originally designed to map one-to-one with links, de facto usage of IPv4 has frequently violated that model, allowing one subnet to span multiple links (e.g., using proxy ARP) and more than one subnet to be assigned to the same link. SIPP SIPP WG, Expires Aug 1, 1994 [Page 3] SIPP Routing and Addressing January 1994 adopts the less stringent model: subnets in SIPP are a logical con- struct -- the lowest-level (i.e., finest-grain) aggregation of addresses under a common address prefix -- independent of the physi- cal topology of links. A network administrator is free to assign one subnet per link if desired, but that is not a requirement of the pro- tocol. One further relaxation of the IPv4 addressing model is that two SIPP nodes attached to the same link need not belong to the same subnet in order to communicate directly, i.e., they are not forced to communi- cate via an intermediate router on the common link. A SIPP address serves two purposes. One is to uniquely identify the node (or set of nodes) to which the address belongs. The other is to specify the location of the addressed node(s) in the internet topol- ogy, to facilitate routing. A SIPP address is said to have a certain "routing scope", which is the topological region over which nodes have sufficient routing information to deliver a packet to the node(s) identified by that address. Most SIPP addresses have global routing scope, meaning they are routable from anywhere in the internet. However, some addresses have less than global routing scope. For example, during bootstrap- ping a SIPP node may use an address derived from its link-level address (e.g., an Ethernet address) that is only locally routable. Every SIPP packet contains two Identifying Addresses, identifying the source and destination nodes of the packet. The transport-layer pseudo-header checksum for the packet is calculated using the two Identifying Addresses. The two Identifying Addresses may or may not contain sufficient loca- tion information to route the packet to its destination(s) (or to route an error message back to its source). When they are insuffi- cient, an optional SIPP Routing Header is included in the packet to carry the additional addressing information required for routing. These additional addresses may be viewed as high-order extensions of the Identifying Addresses. The additional addresses and the Identi- fying Address, taken together, are called an address sequence. For instance, an address sequence can be used for a mobile node that is attached to a place in the internet other than the location speci- fied by its Identifying Address. Or, an address sequence can be used if the routing scope of the Identifying Address is not sufficient (as may happen if the internet grows too large to assign globally- routable addresses to all nodes). This way, the address sequence can be used to achieve the effect of a variable length address. Even when the address sequence is used to extend the address length beyond SIPP WG, Expires Aug 1, 1994 [Page 4] SIPP Routing and Addressing January 1994 64 bits, however, the identification function uses only the "low order" 64 bits (the Identifying Address). 2.1. Text Representation of Addresses There are two conventional forms for representing SIPP addresses as text strings: 1. the preferred form is x:x:x:x, where the 'x's are the hexadecimal values of the four 16-bit pieces of the address. Examples: FEDC:BA98:7654:3210 40D7:0:D01:4403 2. an alternative form that is sometimes more convenient when dealing with a mixed environment of IPv4 and SIPP nodes is x:x:d.d.d.d, where the 'x's are the hexadecimal values of the two high-order 16-bit pieces of the address, and the 'd's are the decimal values of the four low-order 8-bit pieces of the address (standard IPv4 representation). Examples: FEDC:BA98:118.84.50.16 40D7:0:13.1.68.3 If a multi-part address sequence is used, the multiple addresses are separated by double colons. Examples: 0123:4567:89AB:CDEF::FEDC:BA98:7654:3210 0123:4567:89AB:CDEF::FEDC:BA98:118.84.50.16 2.2. Unicast Addresses Unicast addresses are distinguished from multicast addresses by the value of the high-order octet of the addresses: a value of 7F (01111111) or FF (11111111) identifies an address as a multicast address; any other value identifies an address as a unicast address. The SIPP unicast address is contiguous bit-wise maskable, similar to IP addresses under CIDR [1]. The SIPP address sequence is also con- tiguous bit-wise maskable, with the exception that a "field" (for instance, one level of a hierarchical address) within the extended address cannot straddle individual SIPP addresses. SIPP WG, Expires Aug 1, 1994 [Page 5] SIPP Routing and Addressing January 1994 There are several forms of unicast address assignment in SIPP, including the global hierarchical unicast address, the cluster address, the local-use address, and the IPv4-only host address. 2.2.1. Global Hierarchical Unicast Addresses The global unicast address is initially assigned as follows [5]: |1| n bits | m bits | p bits | 63-n-m-p| +-+-------------------+---------------------+-----------+---------+ |C| provider ID | subscriber ID | subnet ID | node ID | +-+-------------------+---------------------+-----------+---------+ The first bit is the IP compatibility bit, or C-bit [3]. It indi- cates if the node represented by the address is IP-only or SIPP [4]. SIPP addresses are provider-oriented [5]. That is, the high-order part of the address is assigned to providers, which then assign por- tions of the address space to subscribers, etc. The term "provider prefix" refers to the high-order part of the address up to and including the provider ID. This is similar to assignment of IP addresses under the CIDR scheme [1]. The subscriber ID distinguishes among multiple subscribers attached to the provider identified by the provider ID. The term "subscriber prefix" refers to the high-order part of the address up to and including the subscriber ID. The subnet ID identifies a topologically connected group of nodes within the subscriber network identified by the subscriber prefix. The group of nodes identified by the subnet ID may all be attached to the same link, or may be spread among multiple links. The term "sub- net prefix" refers to the high-order part of the address up to and including the subnet ID. The term "link prefix" can be used in place of the term subnet prefix in the case where the group of nodes iden- tified by the subnet ID are attached to the same link. The node ID identifies a single node among the group of nodes identi- fied by the subnet prefix. Different SIPP nodes have greater or lesser knowledge of the internal structure of the SIPP address, depending on the role the node plays (for instance, host versus router). At a minimum, a node may con- sider that unicast addresses (including its own) have no internal structure: SIPP WG, Expires Aug 1, 1994 [Page 6] SIPP Routing and Addressing January 1994 | 64 bits | +-----------------------------------------------------------------+ | node address | +-----------------------------------------------------------------+ A slightly sophisticated host (but still rather simple) may addition- ally be aware of the link prefix for the link(s) it is attached to, where different addresses may have different values for n: | n bits | 64-n bits | +---------------------------------------------------+-------------+ | link prefix | node ID | +---------------------------------------------------+-------------+ This allows the host to deduce that another host is on the same link. The host acquires this information through manual configuration or the operation of routing or configuration protocols. Still more sophisticated hosts may be aware of other hierarchical boundaries in the unicast, primarily in the form of cluster addresses. These include but are not limited to mobility-scope clus- ter addresses, subscriber cluster addresses, and provider cluster addresses, and are discussed later. Though a very simple router may have no knowledge of the internal structure of SIPP unicast addresses, routers will more generally have knowledge of one or more of the hierarchical boundaries for the operation of routing protocols. The known boundaries will differ from router to router, depending on what positions the router holds in the hierarchy. 2.2.2. Local-use SIPP Unicast Address A local-use address is a unicast address that has only local routa- bility scope (within the subnet or within a subscriber network), and may have local or global uniqueness scope. Local-use addresses with local uniqueness scope can be reused in other domains. Local-use address have the following format: SIPP WG, Expires Aug 1, 1994 [Page 7] SIPP Routing and Addressing January 1994 | 4 | |bits| 12 bits | 48 bits | +----+---------------+--------------------------------------------+ |0110| subnet ID | node ID | +----+---------------+-+-+----------------------------------------+ |X|S| The first two bits of the 48-bit node ID are the X and S flag respec- tively. The S flag is 0 if the node ID has global uniqueness scope, and is 1 if it has only local uniqueness scope. If the S flag is 0, then the node ID is a "universally administered" IEEE-802 address, of length 48 bits. (This bit of the IEEE-802 address is always 0 for "universally administered" IEEE-802 addresses.) If the S flag is 1, then the node ID can be any value, including a "locally administered" IEEE-802 address. Except for one exception, the X flag must always be 0. (This bit of the IEEE-802 address indicates whether the address is group or indi- vidual. A group address as the node-ID in the local-use unicast address is illegal.) That exception is the node ID value of 80-00- 00-00-00-00. This value is reserved to mean "unassigned". It can be used to indicate that the system in question has not been assigned (or assigned itself) a local-use address. It must not be used in the Destination Address field or in the Routing Header. The local-use address does not have global routing scope because the address does not indicate which subscriber network the node is in. The 12 bit subnet ID can be used to indicate which subnet, within the local subscriber network, the node is in. When an IEEE-802 address is used as the node ID, it can come from an actual IEEE-802 interface, or from some other IEEE-802 address, for instance one given to the CPU card of the node. In any event, it must not be assumed that the IEEE-802 address in the node ID field matches the IEEE-802 address of the node's IEEE-802 interface, should the node have one at all. In general, it is preferable that the IEEE-802 address used to form the local-use unicast address be as permanent as possible. Thus, the use of an IEEE-802 address from the CPU card is preferable to one used from an IEEE-802 interface. Local-use addresses have two primary benefits. First, for sites or organizations that are not (yet) connected to the global Internet, there is no need to request or "steal" an address prefix from the global Internet address space -- local-use addresses can be used instead. If the organization connects to the global Internet, it must then form addresses with global routability scope. If the SIPP WG, Expires Aug 1, 1994 [Page 8] SIPP Routing and Addressing January 1994 local-use address has only local uniqueness scope, then it must assign new addresses that have global routability and global unique- ness scope. If the local-use address has global uniqueness scope, then it can either assign new addresses, or prepend the subnet clus- ter address to the local-use address. The resulting address sequence has global routing scope and can be used for global communications. The second benefit of local-use addresses is that they can hold much larger node IDs, which makes possible a very simple form of auto- configuration of addresses. In particular, a node may discover a subnet ID and length by listening to Router Advertisment messages on its attached link(s), and then fabricating a SIPP address for itself by using its link-level address as the node ID on that subnet (if the link-level address can fit in the node ID field). An auto-configured local-use address may be used by a node as its own identification for communication within the local domain, possibly including communication with a local address server to obtain a glo- bal SIPP address. The details of host auto-configuration will be described elsewhere. 2.2.3. Cluster Addresses Cluster addresses are unicast addresses that may be used to reach the "nearest" one (according to unicast routing's notion of nearest) of the set of boundary routers of a cluster of nodes identified by a common prefix in the SIPP unicast routing hierarchy. A boundary router of cluster C has at least one address with prefix C and at least one link to a node with a prefix other than C. Cluster addresses have the general form: | n bits | 64-n bits | +---------------------------------+-------------------------------+ | cluster prefix |0000000000000000000000000000000| +---------------------------------+-------------------------------+ For example, to reach the nearest boundary router for the routing domain identified by subscriber prefix S, a packet may be sent to the following cluster address: | m bits | 64-m bits | +---------------------------------------+-------------------------+ | subscriber prefix = S |0000000000000000000000000| +---------------------------------------+-------------------------+ SIPP WG, Expires Aug 1, 1994 [Page 9] SIPP Routing and Addressing January 1994 and to reach the nearest boundary router for subnet T of subscriber S, a packet may be sent to the following cluster address: | m bits | p bits |64-m-p bits| +---------------------------------------+-------------+-----------+ | subscriber prefix = S |subnet ID = T|00000000000| +---------------------------------------+-------------+-----------+ Cluster boundary routers are required to know that they are boundary routers and to accept packets addressed to the corresponding cluster address as being addressed to themselves. Cluster addresses are most commonly used as intermediate addresses in a SIPP Routing Header, to cause a packet to be routed to one or more specific clusters on the way to its final destination. The value zero is reserved at each level of the unicast address hierarchy for use in formulating cluster addresses. Cluster addresses may not be used as source addresses in SIPP pack- ets. 2.2.4. The Loopback Address The unicast address 0:0:0:1 is called the loopback address. It may be used by a node to send a SIPP packet to itself. It may never be bound to any interface. The loopback address may not be used as the source address in SIPP packets that are sent outside of a single node. 2.2.5. The Unspecified Address The address 0:0:0:0 is called the unspecified address. It shall never be assigned to any node. It may be used anywhere an address appears, to indicate the absence of an address. One example of its use is in the Source Address field of any SIPP packets sent by an initializing host before it has learned its own address. The unspecified address may not be used as the destination address of SIPP packets or in SIPP Routing Headers. 2.2.6. SIPP Addresses for IPv4-Only Nodes SIPP unicast addresses are assigned to IPv4-only hosts as part of the IPAE [IPAE] scheme for transition from IPv4 to SIPP. Such addresses SIPP WG, Expires Aug 1, 1994 [Page 10] SIPP Routing and Addressing January 1994 have the following form: |1| 31 bits | 32 bits | +-+------------------------------+--------------------------------+ |1| higher-order SIPP prefix | IPv4 address | +-+------------------------------+--------------------------------+ The highest-order bit of a SIPP address is called the IPv4 compati- bility bit or the C bit. A C bit value of 1 identifies an address as belonging to an IPv4-only node. The IPv4 node's 32-bit IPv4 address is carried in the low-order 32 bits of the SIPP address. The remaining 31 bits are used to carry higher-order SIPP prefixes, such as a service-provider ID. 2.3. Multicast Addresses A SIPP multicast address is an identifier for a group of nodes. A node may belong to any number of multicast groups. Multicast addresses have the following format: |1| 7 | 4 | 4 | 48 bits | +-+-------+----+----+---------------------------------------------+ |C|1111111|flgs|scop| group ID | +-+-------+----+----+---------------------------------------------+ where: C = IPv4 compatibility bit; see [IPAE]. 1111111 in the rest of the first octet identifies the address as being a multicast address. +-+-+-+-+ flgs is a set of 4 flags: |0|0|0|T| +-+-+-+-+ the high-order 3 flags are reserved, and must be initialized to 0. T = 0 indicates a permanently-assigned ("well-known") multicast address, assigned by the global internet numbering authority. T = 1 indicates a non-permanently-assigned ("transient") multi- cast address. SIPP WG, Expires Aug 1, 1994 [Page 11] SIPP Routing and Addressing January 1994 scop is a 4-bit multicast scope value: 0 reserved 1 intra-node scope 2 intra-link scope 3 (unassigned) 4 (unassigned) 5 intra-site scope 6 (unassigned) 7 (unassigned) 8 intra-organization scope 9 (unassigned) A (unassigned) B intra-community scope C (unassigned) D (unassigned) E global scope F reserved group ID identifies the multicast group, either permanent or transient, within the given scope. The "meaning" of a permanently-assigned multicast address is indepen- dent of the scope value. For example, if the "NTP servers group" is assigned a permanent multicast address with a group ID of 43 (hex), then: 7F01:0:0:43 means all NTP servers on the same node as the sender. 7F02:0:0:43 means all NTP servers on the same link as the sender. 7F05:0:0:43 means all NTP servers at the same site as the sender. 7F0E:0:0:43 means all NTP servers in the internet. Non-permanently-assigned multicast addresses are meaningful only within a given scope. For example, a group identified by the non- permanent, intra-site multicast address 7F15:0:0:43 at one site bears no relationship to a group using the same address at a different site, nor to a non-permanent group using the same group ID with dif- ferent scope, nor to a permanent group with the same group ID. Multicast addresses must not be used as source addresses in SIPP packets. A given route sequence must have zero or one multicast address in it, but no more. The active address in a route sequence must never be advanced beyond a multicast address. In other words, if a SIPP node receives a packet with a multicast address in the SIPP WG, Expires Aug 1, 1994 [Page 12] SIPP Routing and Addressing January 1994 destination address field, the node must not advance the routing header, even if the node is a member of that multicast group and the route sequence has not yet been exhausted. 2.3.1. Pre-Defined Multicast Addresses The following well-known multicast addresses are pre-defined: The Reserved Multicast Addresses: 7F0s:0:0:0 These multicast addresses (with any scope value, s) are reserved, and shall never be assigned to any multicast group. The All Nodes Addresses: 7F01:0:0:1 7F02:0:0:1 These multicast addresses identify the group of all SIPP nodes, within scope 1 (intra-node) or 2 (intra-link). The All Hosts Addresses: 7F01:0:0:2 7F02:0:0:2 These multicast addresses identify the group of all SIPP hosts, within scope 1 (intra-node) or 2 (intra-link). The All Routers Addresses: 7F01:0:0:3 7F02:0:0:3 These multicast addresses identify the group of all SIPP routers, within scope 1 (intra-node) or 2 (intra-link). 2.4. A Node's Required Addresses A host is required to recognize the following addresses as identify- ing itself: its own unicast addresses, the loopback address, the All Nodes and All Hosts multicast addresses, and any other multicast addresses to which the host belongs. A router is required to recognize the following addresses as identi- fying itself: its own unicast addresses, the cluster addresses of all clusters for which the router is a boundary router, the loopback address, the All Nodes and All Routers multicast addresses, and any other multicast addresses to which the router belongs. The router is also required to recognize as identifying itself any address that it initiated in a routing protocol. If this address is the higher level address of an extended address, then the resulting behaviour will be that the router advances the Routing Header and routes on the next address. SIPP WG, Expires Aug 1, 1994 [Page 13] SIPP Routing and Addressing January 1994 Nodes must also know their own address sequences, primarily for the purpose of inserting them in packets that they transmit. 3. ADDRESS SEQUENCE HANDLING BY NODES For address sequences to be an effective means of extending SIPP addresses or enriching SIPP routing semantics for use in provider selection, mobility, auto-readdressing, etc., nodes must be able to manipulate address sequences appropriately. A node must be able to recognize that its own addresses and other nodes' addresses may be represented as address sequences, for instance in transmitted and received packets and in DNS. A node must also be able to reverse address sequences for sending return packets. 3.1. Address Sequence Notation The SIPP mechanism for encoding address sequences is the optional Routing Header. With this mechanism, the active address of the optional Routing Header is in the destination address field of the SIPP header, and the remaining addresses in the address sequence (those that were previously active and those that will be active) are in the Routing Header. Thus, the fields of the Routing Header rotate through the destination address field as each becomes active. Notated literally, the mechanism would look like this: source address dest address Routing Header -------------- ------------ ------------ initial S A >B D next S B A >D final S D A B > This shows a packet from S, routed through A and B on its way to D. The '>' symbol indicates which field is next in the Routing Header (i.e., the field pointed to by the Next Addr field of the Routing Header). While this notation accurately depicts what happens in the packet header, it is unwieldy, so the following equivalent notation is used instead: initial S,*A, B, D next S, A,*B, D final S, A, B,*D In this notation, the first element is in the source address field of the SIPP header. The '*' denotes the active element of the Routing Header, which is in the destination address field. The remaining elements are in the Routing Header, with the Next Addr field pointing SIPP WG, Expires Aug 1, 1994 [Page 14] SIPP Routing and Addressing January 1994 to the element after the active one. 3.2. Node Formation of Address Sequences This section describes a simple set of rules for the handling of address sequences. These rules allow nodes to form and transmit SIPP packets with traditional IP address semantics. More importantly, they allow nodes to receive and "reverse" SIPP packets with advanced routing and addressing semantics, such as policy routing. Thus nodes that do not understand advanced routing semantics can still operate appropriately when receiving packets from a node that does. Every node has a set of address sequences that it considers its own. These address sequences are a series of 64-bit addresses of the form , where S0 is the low-order address and also the Identifying Address, and Si is the high-order address. Note that the terms low-order and high-order do not necessarily indicate that the high-order terms are hierarchically above the low-order terms. Rather, the implication is that the high-order terms must come first in an address sequence. All nodes must be capable of handling an address sequence of at least three addresses. A node may be able to handle longer address sequences if desired. An address sequence of a node constitutes the sum total of informa- tion needed in the packet header to route the packet to that node. Only the low-order address is required to identify the node. Some of a node's address sequences are source-capable and others are not. A source-capable address sequence is one that can validly be used as a "source address" in a transmitted packet. For instance, unicast address sequences are source-capable and multicast address sequences are not, though both can be considered by the node to be its own address sequences. A route sequence may contain a number of components, such as a source address sequence, a destination address sequence, a policy route, a mobile host base station, or a multicast tree core address. From the perspective of a "simple" node, however, a route sequence contains only two parts, the source address sequence and the destination address sequence: For a transmitted packet, the source address sequence is one of the node's own source-capable address sequences, and the destination address sequence is everything else. For a received packet, the des- tination address sequence is (or at least should be) any of the SIPP WG, Expires Aug 1, 1994 [Page 15] SIPP Routing and Addressing January 1994 node's own address sequences, and the source address sequence is everything else. In an address sequence, the addresses of the source address sequence are ordered with the "low order" parts first, while the addresses of the destination address sequence are ordered in the opposite direc- tion, with the "high-order" parts first. Thus the first and last addresses are always the identifying addresses--the "low order" parts of the source and destination address sequences. In the common case with a single-component source and destination address, the complete route sequence simply has the form: . Such packets contain no Routing Header. When a node has an "association" with another node (that is, a tran- sport connection or an application "connection" running over UDP), it must maintain the following information with respect to the correspondent node (the node with which it has the association): 1. The source and destination Identifying Addresses for the entire association. 2. The source and destination address sequences currently in use. The low-order parts of the source and destination address sequences must match the Identifying Addresses. When a node initiates an association, it will normally learn the des- tination address sequence through DNS or from local means (for instance, the user typing it in). It extracts the destination Iden- tifying Address for the association from the low-order part of the destination address sequence. It chooses from among its source- capable address sequences for the source address sequence, and forms the header as indicated above. When a node is not the initiator of an association, it must extract the appropriate information from the received packet. This occurs in two cases, where a node is the destination of the packet, and where the node is a router that has encountered an error in processing a packet and must return an ICMP error message. 3.2.1. Destination Node Reversal of Route Sequence Let the route sequence in the received packet be . The receiving node compares its own source address sequences against the tail of the received route sequence, looking for the best match. (Note that the multicast groups that the node belongs to are included in its list of address sequences for this comparison SIPP WG, Expires Aug 1, 1994 [Page 16] SIPP Routing and Addressing January 1994 process.) A best match is one where, given a source address sequence of , S0 = Rn, S1 = Rn-1, etc., for the larg- est number of addresses. At a minimum, however, the node's Identify- ing Address, S0, must match the destination Identifying Address from the received route sequence, Rn. The node then strips from the route sequence the addresses that matched its source address sequence, resulting in , where j < n. The resulting sequence is reversed, giving . This sequence is then prepended with one of the node's source-capable address sequences, preferably the one that matched the tail of the incoming route sequence, resulting in . If the destination Identifying Address of the incoming route sequence, Rn, is source-capable, then the source Iden- tifying Address of the reversed route sequence, S0, must be equal to Rn. Finally, the active address (that is, the address to which the Next Addr field of the Routing Header points) is set to be Rj, the first address after the node's address sequence. Every node must implement these reversal rules. Even if a node has no notion of, say, provider selection, it will successfully return packets to a node that does if it implements these rules. 3.2.2. Intermediate Node Reversal of Route Sequence Let the route sequence in the invoking packet be , where R0 is the source's Identifying Address and Rn the destination's Identifying Address. Let Rj be the active element in the route sequence. Note that j is always >= 1. The route sequence in the ICMP error message MUST be , where is any source- capable address sequence for the router generating the ICMP error message. The active element in this route sequence is Rj-1. Intui- tively, the "consumed" portion of the invoking packet's route sequence is used to route the error message back to the source. 3.2.3. Using the SIPP Flow Label to Tag Route Sequences SIPP packets originating from the same sender and carrying the same SIPP flow label constitute a "flow". Mechanically, a packet's flow label (together with the source identifying address) is a convenient key with which a router can associate the sum total of its actions on the packet; such actions include special-purpose or real-time han- dling as well as packet forwarding. For good hash function SIPP WG, Expires Aug 1, 1994 [Page 17] SIPP Routing and Addressing January 1994 performance, senders assign pseudo-random values to the flow label. If an outgoing packet carries a non-zero flow label, a SIPP host must generate a different non-zero flow label value when the route sequence changes. There are only two instances where a sender must generate a new flow label: when the sending application adds or deletes SIPP addresses from a destination address sequence, and when the sender's source address sequence changes, e.g. if its location changes. This explicit use of the flow label to "tag" route sequences has two advantages. First, hosts need not apply the reversal rules on every incoming packet. When a receiver reverses an incoming route sequence, it can associate the result of the reversal with the sender's identifying address and the flow label in the incoming packet. Route sequences in subsequent packets from the same sender with the same flow label need not be reversed. Second, the source identifying address and the flow label uniquely determines the next hop router and outgoing interface at each router on the path of the packet. Routers can cache this mapping to speed up packet forwarding. This is particularly useful for route sequences in which routers need to "peek-behind" into the routing header to make forwarding decisions (e.g. traditional multicast with extended addresses or traditional multicast from a mobile host). The caches at routers and hosts represent "soft" state; loss of this state does not affect the correctness of packet forwarding or route sequence reversal. Furthermore, this correctness is not affected if the same route sequence is assigned different flow labels. This may happen, for instance, when an application wants all packets to a des- tination to follow the same path but some packets be "handled" dif- ferently in routers along the path. Our use of the flow label places a restriction on the choice of the flow label: when the route sequence changes, the flow label must change. We believe this is not a significant restriction. When a route sequence changes, flow setup will be required along the new path. Even if the new path is intersects the old significantly, set- ting up the same state in the common routers under a new flowID might not be that much more expensive. A sender may assign a flow label of zero to an outgoing route sequence. Receiving hosts and intermediate routers do not cache route lookups on packets with zero-valued flow labels. This feature SIPP WG, Expires Aug 1, 1994 [Page 18] SIPP Routing and Addressing January 1994 is useful for minimal SIPP implementations that may not need to sup- port flow-based applications. 4. ROUTING ALGORITHMS SIPP routing algorithms are identical to those used with the CIDR version of IP, except that the address used is 64 bits rather than 32. This is true even when extended addresses are in use. This having been said, when extended addresses are used, some care must be taken in the routing protocol configuration, that is, which routers initiate the advertisement of addresses, and which routers halt the advertisement of addresses. Further, routers must know when to advance the route header during the parsing of an extended address. 4.1. Background In order to specify this, some background is required. Consider a hierarchical address with hierarchical components , where H0 is the low level component and Hn is the high level component. Assume that this hierarchical address belongs to Host A. Host A advertises the complete address in its hello packets (or, by virtue of responding to an ARP request). The router adjacent to host A, router A1, hears the advertisement, and creates a routing table entry for the complete address (or, an ARP table entry). Router A1, however, may not advertise Host A's complete address to its neighbor. Instead, router A1 may advertise all but the last hierarchical component, , for instance because the link of Host A has a subnet ID associated with it. In this case, Host A is said to initiate the advertisement , and Router A1 is said to halt the advertisement of . Router A1 initiates the advertisement of , which will travel to the router A2 at the border of whatever cluster is defined by the prefix , where it will be halted. Router A2 will initiate the advertisement , and so on up the hierarchy. Thus, the operation of a hierarchical routing algorithm involves configuring routers to know when to initiate and when to halt address prefixes. Consider the following topology: SIPP WG, Expires Aug 1, 1994 [Page 19] SIPP Routing and Addressing January 1994 Ra Routing +------------------+ Table: | C0 | ---------- | | To Next L1 | +----+ +----+ | C0.Cc L2 ---Ra----+--| Ca |--| Cb | | C0 L1 | | +----+ +----+ | |L2 | | | | | +----+ | | +----+--| Cc |----+ | | +----+ | +------------------+ Router Ra can reach cluster C0 via two links, L1 and L2. Ra's rout- ing table indicates that the prefix for cluster C0 is via link L1. Ra's routing table, however, has an entry for cluster Cc inside clus- ter C0, via link L2. If Ra receives a packet for a host in cluster Ca, the destination address will have a prefix of C0.Ca. Ra will parse the C0 component of the address, and determine that it must look deeper into the address to determine if the address is for some- thing in cluster Cc. Since in this case it is not, Ra will forward the packet to cluster C0 over link L1. If this scenario occurred using SIPP, and the prefix C0.Ca were in the same SIPP address, then it would work as described above. If, however, the C0 component and the Ca component are in different addresses, then the above scenario would not work. This is because router Ra would look at the C0 component, determine that it should look deeper in the address, and advance the route header. It would then access the routing table with prefix Ca, for which it has no routing information. This constrained behaviour results from the way that SIPP nodes advance the routing header. That is, they advance it when they per- ceive that a given address identifies themselves, and when there are more addresses in the route header. Put another way, SIPP routers do not have the ability to "peek ahead" into the next address of the routing header without advancing the routing header. Once advanced, however, the router, and subsequent routers in the path, must have enough routing information to route the packet based solely on the new address. 4.2. Router Rules for Handling Unicast Destination Addresses This leads to the following rules that must be followed by all routers: SIPP WG, Expires Aug 1, 1994 [Page 20] SIPP Routing and Addressing January 1994 1. A router only advances the route header when the address in the route header identifies itself. 2. The addresses that identify a router are given above. One of these addresses is any address that a router initiates in a routing advertisement. 3. A router must only initiate an address in a routing advertise- ment with a given mask when a) the address identifies an indivi- dual node, or b) the router has full knowledge of the destina- tions reachable at the hierarchical level below the one adver- tised. For example, in the above network, if C0 and Ca were positioned in different addresses, the Ra must either: 1. have no routing information about the internals of C0, in which case it would not initiate an advertisement for C0, or 2. have full information about the internals (that is, have routing table entries for Ca and Cb as well as Cc), in which case it would initiate an advertisement for C0 (as though it were inside C0). 4.2.1. Handling Address Sequences in Source Addresses For certain types of multicast routing--namely those based on build- ing multicast trees from the source--it is necessary for a router to examine the source address as well as the destination (multicast) address when forwarding a packet. Since the source address in SIPP may also be extended, the router must also know how to examine it in order of high order address to low order address. All of the addresses of the extended source address except for the identifying address are in the routing header. To examine the source address, the router starts at the address immediately preceding the active address (in terms of the address sequence notation). In terms of packet header format, this is the address in the routing header immediately preceding the address indicated by the Next Addr field, if any, and the address in the source address field otherwise. If, upon examining an address in the source address sequence, the router finds that it must examine the next lower-order address in the sequence, the router examines the address in the route header immedi- ately preceding the address it is just examined, if any, and examines the address in the source address field otherwise. SIPP WG, Expires Aug 1, 1994 [Page 21] SIPP Routing and Addressing January 1994 References [1] V. Fuller, T. Li, K. Varadhan, J. Yu, "Supernetting: an Address Assignment and Aggregation Strategy", RFC 1338. [2] S. Deering, "Host Extensions for IP multicasting", RFC 1112. [3] R. Gilligan et al, "SIPP Transition Mechinisms", Internet Draft,. [4] S. Deering, "Simple Internet Protocol Plus (SIPP) Specification", Internet Draft, work in progress. [5] P. Francis, "SIPP Address Assignment", Internet Draft. [6] R. Govindan and S. Deering, "ICMP and IGMP for the Simple Internet Protocol Plus", Internet-Draft in preparation. Author's Addresses Steve Deering, deering@parc.xerox.com Paul Francis, francis@cactus.ntt.jp Ramesh Govindan, rxg@thumper.bellcore.com SIPP WG, Expires Aug 1, 1994 [Page 22] SIPP Routing and Addressing January 1994 APPENDIX A: EXAMPLES 5. UNICAST EXAMPLES In this section, we give several typical unicast examples that demon- strate the use of the Routing Header mechanism for provider selection and address extension. Later sections give typical examples for mobility, multicast, and auto-configuration. The examples assume the following topology. Domain D contains node H. Domain E contains node I. Domain D is attached to providers P and Q. Domain E is attached to providers Q and R. 5.1. Simple (Non-Extended) Addresses Assume that the addresses of node H are P.D.H and Q.D.H, and the addresses of node I are Q.E.I and R.E.I, where the notation "a.b.c" represents a 64-bit SIPP address. (Note that the 'D' of P.D.H and Q.D.H are subscriber numbers assigned by P and Q respectively, and are therefore in general not the same value.) H initiates an associa- tion with I by querying DNS and learning the two addresses for I. Assume that H chooses Q.E.I, since it has the best "match" with its own addresses. H forms the following packet: Route sequence at sender H: Q.D.H, *Q.E.I I receives this packet, reverses the (in this case simple) route sequence, and returns: Reversed route sequence at receiver I: Q.E.I, *Q.D.H 5.2. Simple Addresses with Provider Selection The previous example is in fact a form of provider selection, but it is simple in that both ends have the same provider, so nothing expli- cit has to be done. Assume in this case, however, that H wishes to send its packet through provider P. Since I is not attached to pro- vider P, H must explicitly indicate that it wants its packet to go through provider P, and therefore forms the following packet: Route sequence at sender H: P.D.H, *P.0, Q.E.I The active element of the route sequence is the cluster address of provider P. This causes routers in domain D to route the packet to provider P. When the first router in provider P receives this SIPP WG, Expires Aug 1, 1994 [Page 23] SIPP Routing and Addressing January 1994 packet, it recognizes the packet as being for "itself", and advances the Routing Header, producing: Advanced route sequence at provider P router: P.D.H, P.0, *Q.E.I which causes the packet to be routed to I. Upon receiving this packet, I uses the reversing rules stated above, producing the fol- lowing packet: Reversed route sequence at receiver I: Q.E.I, *P.0, P.D.H This packet has a couple of noteworthy characteristics. First, the packet may exit domain E via either provider Q or R, depending on what routing considers the best path to provider P. Second, the P.0 element is redundant, since the destination address P.D.H will also cause the packet to be routed to P. However, without knowing the provider mask of P, I has know way of knowing that P.0 is redundant with P.D.H, and so includes both elements. In the future, it may be possible for I to learn H's cluster address and optimize the header accordingly. To continue this example, assume that I does care which exit provider is used to reach H, and further that I chooses provider Q. In this case, I would insert the following "policy route" (actually, one address) to force the packet to go through Q outgoing: Alternative reversed route sequence: Q.E.I, *Q.0, P.0, P.D.H Note that this example describes a node that is more sophisticated than the simple one described previously. In particular, the node in this example understands three components of the source route (the source and destination addresses and a provider) rather than just two (the source and destination addresses). The node further understands that when it inserts the provider selector in the route sequence, it sets the active element to be that of the provider selector on transmitted packets. 5.3. Extended Address (Address Sequence) Now assume that at some point 64 bits become inadequate and addresses are extended to an address sequence of two 64-bit addresses. In this case, H's address sequences are P.D:S.H and Q.D:S.H, where the colon ':' indicates a 64-bit boundary, and S represents a subnet inside domain D. I's address sequences are Q.E:S.I and R.E:S.I. For H to send a packet to I, it could form: SIPP WG, Expires Aug 1, 1994 [Page 24] SIPP Routing and Addressing January 1994 Route sequence at sender H: S.H, Q.D, *Q.E, S.I The active element Q.E would cause the packet to be routed to domain E, where the Routing Header would be advanced to: Advanced route sequence at router in Domain E: S.H, Q.D, Q.E, *S.I and delivered to I. The above reversing rules executed by I would produce: Reversed route sequence at receiver I: S.I, Q.E, *Q.D, S.H thus returning the packet to I. 6. MULTICASTING IN SIPP This section describes how traditional multicast [2] works using SIPP route sequences. As with unicast, SIPP multicast address sequences are described using a series of 64-bit address elements. Thus, the node's notion of multicast addressing is extended such that a "multi- cast address" is seen as an address sequence rather than a single multicast address as is the case with IP. The final element of the multicast address sequence is the group ID. When a node joins a multicast group, it considers the multicast address sequence to be one of its own address sequences for the sake of packet reception and reversal. The multicast address sequence is not source-capable. In traditional multicast (also known as Deering multicast or source- based multicast), a packet from a sender to a multicast group is sent on the shortest-path delivery tree (rooted at the sender) to members of the group. The traditional SIPP multicast address sequence con- tains only one address--the group ID. This section describes the Routing Header that is formed by the sender, the reversed Routing Header formed by the receiver and the necessary extensions to the multicast forwarding algorithm. 6.0.1. Example Assume the same scenario as described above (with nodes H and I), further assuming that H and I have extended addresses as described above. (We do an extended address example here because the simple address example is the same as with current IP.) Assume further that H is transmitting a traditional multicast with multicast address M, and that I is a member of group M. H forms the following header: SIPP WG, Expires Aug 1, 1994 [Page 25] SIPP Routing and Addressing January 1994 Route sequence at sender H: S.H, Q.D, *M The route sequence is received unchanged at each of the receivers. If I wishes to respond unicast to H, it executes the reversing rules described above in the following way. First, it isolates its own address from the route sequence. Since this is multicast, and since I is a member of the multicast group M, I considers M to be one of its "own" addresses, and strips it. Reversing what remains produces . Since a multicast address cannot be used as a source address, I knows to prepend its own unicast address sequence to the route sequence, producing: Reversed route sequence at receiver I: S.I, Q.E, *Q.D, S.H 7. MOBILITY IN SIPP This section shows how SIPP source routing and SIPP route sequences might be used for mobile communication. Note that the Mobile IP group of IETF is deliberating on various solutions for mobility, and may choose a different approach than the one outlined here. At the same time, more approaches are possible with SIPP than with IP, so the Mobile IP group may choose a different solution for use with SIPP. First, we introduce some terminology. Mobile Host (MH) A node that is able to maintain its network connections even after being physically moved. Correspondent Host (CH) A node that has a network connection open to an MH. A CH may itself be mobile. Base Station (BS) The SIPP router to which the MH is attached after it moves. Home Station (HS) A SIPP node that is aware of the MH's current location. Each MH has a preconfigured home station. 7.1. Mobility Example Assume that H is an MH and that I is the CH, both with the (extended) address sequences from above. Initially, a packet from the CH to the MH carries the following route sequence as in the above example: SIPP WG, Expires Aug 1, 1994 [Page 26] SIPP Routing and Addressing January 1994 Route sequence from CH to MH: S.I, Q.E, *Q.D, S.H Now suppose the MH moves to the vicinity of a BS with an address D.d. MH discovers D.d through SIPP "I-Am-Here" advertisements. These are multicast by the BS to the SIPP All Nodes address (similar to an IS hello advertisement in ES-IS). MHs also periodically multicast SIPP "I-Am-Here" advertisements to the SIPP All Routers multicast address (similar to the ES hello advertisement in ES-IS). This latter adver- tisement contains the MH's identifying address. Through a mechanism beyond the scope of this document, the MH informs the HS of its new base station. Packets carrying the old route sequence from the CH are intercepted by the HS. The HS tunnels them to the BS, which forwards it to the MH. After the MH has discovered D.d, all subsequent packets to the CH carry the following route sequence: Route sequence from MH to CH after move: S.H, D.d, *Q.E, S.I It is sufficient to include only MH's identifying address in the route sequence; we assume that the BS is within I's Identifying Addresses (S.I) routing scope. When the CH reverses the incoming route sequence from the MH, it created the following route sequence: Reversed route sequence from CH to MH after move: S.I, Q.E, *D.d, S.H This causes packet to the MH to be routed through the BS at D.d, pro- ducing the desired behavior. SIPP WG, Expires Aug 1, 1994 [Page 27] SIPP Routing and Addressing January 1994 APPENDIX B: SIPP Service Interface and Address Sequences Because SIPP has larger addresses and a different packet format from IP, the service interface it provides to the transport layer is dif- ferent from that provided by IP [4]. Existing transport-layer proto- cols that use IP must be modified to operate over SIPP's service interface. In this section, we discuss only the changes to the SIPP service interface that arise from the use of address sequences to represent the location of SIPP nodes. When sending a packet, the transport layer must specify the complete address sequences of the source and destination. The lowest-order address in each address sequence must correspond to the identifying addresses used to form the transport-layer pseudo-header checksum. The destination address sequence can include "policy-route" addresses that an application may have prepended to the destination's address. As discussed before, a node's address sequences may change over time (e.g. because it is mobile). The node's SIPP layer must track such changes; we do not require that the transport layer also track changes in the node's address sequences. Thus, the source address sequence specified in a send operation may be incorrect or insuffi- cient. In such a case, the send operation fails, and the SIPP layer returns a correct source address sequence that may be used in the outgoing packet. (Basically, the SIPP layer returns a source-capable address sequence with a matching identifying address. If the transport layer passed the SIPP Unspecified Address, the SIPP layer returns some source-capable address). The transport layer may then retry the send operation with this source address sequence. After processing a received packet, the SIPP layer passes up to the transport layer the source and destination address sequences in the incoming packet. To do this, the SIPP layer first applies the rever- sal rules. The packet's destination address sequence is that address sequence that best matches the tail of the incoming route sequence. The unmatched part of the incoming route sequence, reversed, is the packet's source address sequence. SIPP WG, Expires Aug 1, 1994 [Page 28]