INTERNET DRAFT draft-ietf-sip-routing-addr-01.txt S. Deering (Xerox PARC) P. Francis (NTT) R. Govindan (Bellcore) February 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. Changes From Last Version Actually, this was intended to be the first version of the ROAD spec, but the previous version was sent to the Internet Drafts secretariat before it was completely reviewed, and in the confusion was mistak- enly posted in the Internet Drafts repository. The previous version is dated January 1994. This version contains numerous minor changes not mentioned here. The major changes in this version are: 1. Routers are no longer required to recognize prefixes they ini- tiate in routing algorithms as identifying themselves. SIPP WG, Expires Sept. 1, 1994 [Page 1] draft-ietf-sip-routing-addr-01.txt February 1994 2. The Flow ID/Source Identifying Address pair no longer needs to be unique for a given route header. The Flow ID is not set unless an explicit flow has been established. 3. The X and S bits in the Local-Use address have been repositioned to reflect where they actually lay according to canonical for- mat. 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. New terms are defined as follows: address: A 64-bit SIPP layer identifier for a node or set of nodes. An address can be used for both routing and identification purposes. (This definition is an augmentation of that given in the SIPP Specification.) 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. SIPP WG, Expires Sept. 1, 1994 [Page 2] draft-ietf-sip-routing-addr-01.txt February 1994 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). extended address: The use of an address sequence to extend the SIPP address space beyond 64 bits. 2. SIPP ADDRESSING SIPP addresses are 64-bit identifiers for nodes and sets of nodes. There are two types of addresses: Unicast: Causes a packet to be sent to a single node. Multicast: Identifies a set of nodes, and causes the packet to be sent to all of those nodes. There are no broadcast addresses in SIPP, their function being super- seded by multicast addresses. 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. 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 Eth- ernets) 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 SIPP WG, Expires Sept. 1, 1994 [Page 3] draft-ietf-sip-routing-addr-01.txt February 1994 prefix 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 IP, a node may be so configured. However, SIPP's relaxation of IP'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 IP 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 IP were originally designed to map one-to-one with links, de facto usage of IP 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 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 IP 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 SIPP WG, Expires Sept. 1, 1994 [Page 4] draft-ietf-sip-routing-addr-01.txt February 1994 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 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 hexade- cimal values of the four 16-bit pieces of the address. Exam- ples: FEDC:BA98:7654:3210 40D7:0:D01:4403 2. an alternative form that is sometimes more convenient when deal- ing with a mixed environment of IP 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 IP representation). Examples: SIPP WG, Expires Sept. 1, 1994 [Page 5] draft-ietf-sip-routing-addr-01.txt February 1994 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. 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 IP-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]. SIPP WG, Expires Sept. 1, 1994 [Page 6] draft-ietf-sip-routing-addr-01.txt February 1994 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: | 64 bits | +-----------------------------------------------------------------+ | node address | +-----------------------------------------------------------------+ A slightly sophisticated host (but still rather simple) may addition- ally be aware of link or subnet prefix(es) for the link(s) it is attached to, where different addresses may have different values for n: | n bits | 64-n bits | +---------------------------------------------------+-------------+ | link or subnet prefix | node ID | +---------------------------------------------------+-------------+ The link prefix allows the host to deduce that another host with the same link prefix is on the same link. (Note that there can be multi- ple link prefixes per link.) The host acquires this information through manual configuration or the operation of routing or confi- guration protocols. Still more sophisticated hosts may be aware of other hierarchical boundaries in the unicast address, primarily in the form of cluster SIPP WG, Expires Sept. 1, 1994 [Page 7] draft-ietf-sip-routing-addr-01.txt February 1994 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: | 4 | |bits| 12 bits | 48 bits | +----+---------------+--------------------------------------------+ |0110| subnet ID | node ID | +----+---------------+--------+-+-+-------------------------------+ | 6 bits |S|X| 40 bits | The seventh and eighth bits of the 48-bit node ID are the S and X flag respectively. The S flag is 0 if the node ID has global unique- ness 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. With one exception, the X flag must always be 0. (This bit of the IEEE-802 address indicates whether the address is group or indivi- dual. A group address as the node-ID in the local-use unicast address is illegal.) That exception is the node ID value of 01-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. SIPP WG, Expires Sept. 1, 1994 [Page 8] draft-ietf-sip-routing-addr-01.txt February 1994 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 local-use address has only local uniqueness scope, then it must assign new addresses that have global uniqueness scope. If the local-use address has global uniqueness scope, then it either assign new addresses, or extend the existing local-use address using an address sequence. 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 by listening to Router Advertisement 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 are described elsewhere [7]. 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 SIPP WG, Expires Sept. 1, 1994 [Page 9] draft-ietf-sip-routing-addr-01.txt February 1994 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| +---------------------------------------+-------------------------+ 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. Note that when an extended address is used, the cluster prefix may completely fill a single (64-bit) address. (Subsequent addresses in the cluster address sequence are, conceptually, all zeros. Such all-zero addresses, however, would not actually appear in a packet header.) SIPP WG, Expires Sept. 1, 1994 [Page 10] draft-ietf-sip-routing-addr-01.txt February 1994 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 IP-Only Nodes SIPP unicast addresses are assigned to IP-only hosts as part of the IPAE [IPAE] scheme for transition from IP to SIPP. Such addresses have the following form: |1| 31 bits | 32 bits | +-+------------------------------+--------------------------------+ |1| higher-order SIPP prefix | IP address | +-+------------------------------+--------------------------------+ The highest-order bit of a SIPP address is called the IP compatibil- ity bit or the C bit. A C bit value of 1 identifies an address as belonging to an IP-only node. The IP node's 32-bit IP 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: SIPP WG, Expires Sept. 1, 1994 [Page 11] draft-ietf-sip-routing-addr-01.txt February 1994 |1| 7 | 4 | 4 | 48 bits | +-+-------+----+----+---------------------------------------------+ |C|1111111|flgs|scop| group ID | +-+-------+----+----+---------------------------------------------+ where: C = IP 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. 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 SIPP WG, Expires Sept. 1, 1994 [Page 12] draft-ietf-sip-routing-addr-01.txt February 1994 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 des- tination 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 SIPP WG, Expires Sept. 1, 1994 [Page 13] draft-ietf-sip-routing-addr-01.txt February 1994 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 the multicast addresses of any other groups 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. 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: SIPP WG, Expires Sept. 1, 1994 [Page 14] draft-ietf-sip-routing-addr-01.txt February 1994 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 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. Each such address sequence is 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. SIPP WG, Expires Sept. 1, 1994 [Page 15] draft-ietf-sip-routing-addr-01.txt February 1994 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, the address of the router serving as a host's 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 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 (such as a TCP 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. SIPP WG, Expires Sept. 1, 1994 [Page 16] draft-ietf-sip-routing-addr-01.txt February 1994 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 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 process.) The best match is the one where the largest number of addresses in the tail of the received route sequence match the corresponding addresses in the node's own address sequence. For instance, assume the node has an address sequence of . The best match is the one with the highest x for which S0 = Rn, S1 = Rn- 1,..., Sx = Rn-x. Note that it is not necessary for the node's com- plete address sequence to match the tail of the received route sequence. For instance, the case where S0 = Rn and S1 = Rn-1 but Si != Rn-i is still considered a match. At a minimum, the node's Iden- tifying 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 best 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. SIPP WG, Expires Sept. 1, 1994 [Page 17] draft-ietf-sip-routing-addr-01.txt February 1994 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. 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 (for instance, [8]). This is true even when extended addresses are in use. This is possible because a SIPP unicast forwarding table lookup is made by looking at only a single (64-bit) address. The result of such a forwarding table lookup may be to advance the route header, causing the router to look at the subsequent address. The routing table lookup on this subsequent address, however, is made without consideration of the previous lookup. In other words, every "atomic" forwarding table access for unicast routing requires only a single address. Because the forwarding table lookup only involves a single address, the routing algorithm only need carry a single address. If extended addresses are used, however, care must be taken in the distribution of routing information. (For this reason, when extended addresses are used, it may be desirable, though not necessary, that routing algorithms carry extended addresses. Routing algorithms can be thus enhanced in the future if desired.) In particular, routing informa- tion cannot be leaked across routing hierarchy boundaries that coin- cide with the boundary between two SIPP addresses in an extended address. For instance, consider the case where the subscriber prefix is encoded in the upper address of an extended address, and the subnet and host ID is encoded in the lower address of an extended address. The boundary between the upper and lower address coincides with the SIPP WG, Expires Sept. 1, 1994 [Page 18] draft-ietf-sip-routing-addr-01.txt February 1994 boundary between the subscriber network and the provider network (or, with the subscriber network and another subscriber network). Because subnet IDs are not by themselves globally unique, if the lower address were advertised outside of the subscriber network, it could overlap with subnet numbers in the outside network, and routing would fail. The only mechanism required to make extended addresses work with single-address routing algorithms is that routers recognize addresses that identify themselves (see Section 2.4), and advance the route header upon receiving such an address. 4.0.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 just examined, if any, and examines the address in the source address field otherwise. 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 Mechanisms", Internet Draft. SIPP WG, Expires Sept. 1, 1994 [Page 19] draft-ietf-sip-routing-addr-01.txt February 1994 [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. [7] S. Thomson, "Automatic Host Address Assignment in SIPP", Internet Draft in preparation. [8] P. Francis, "OSPF for SIPP", Internet Draft. Author's Addresses Steve Deering, deering@parc.xerox.com Paul Francis, francis@cactus.ntt.jp Ramesh Govindan, rxg@thumper.bellcore.com SIPP WG, Expires Sept. 1, 1994 [Page 20] draft-ietf-sip-routing-addr-01.txt February 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. Subscriber domain D con- tains node H. Subscriber 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 SIPP WG, Expires Sept. 1, 1994 [Page 21] draft-ietf-sip-routing-addr-01.txt February 1994 provider P. When the first router in provider P receives this 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 double 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 Sept. 1, 1994 [Page 22] draft-ietf-sip-routing-addr-01.txt February 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 Sept. 1, 1994 [Page 23] draft-ietf-sip-routing-addr-01.txt February 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 Mobile Host. A CH may itself be mobile. Foreign Agent The SIPP router to which the MH is attached after it moves. Home Agent 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 a 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 Sept. 1, 1994 [Page 24] draft-ietf-sip-routing-addr-01.txt February 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 Foreign Agent with an address D.d. MH discovers D.d through SIPP "I-Am-Here" advertise- ments. These are multicast by the Foreign Agent to the SIPP All Nodes address (similar to an IS hello advertisement in ES-IS). MH also periodically multicast SIPP "I-Am-Here" advertisements to the SIPP All Routers multicast address (similar to the ES hello adver- tisement in ES-IS). This latter advertisement contains the MH's identifying address. Through a mechanism beyond the scope of this document, the MH informs the Home Agent of its new base station. Packets carrying the old route sequence from the CH are intercepted by the Home Agent. The Home Agent tunnels them to the Foreign Agent, 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 Foreign Agent is within I's Iden- tifying 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 Foreign Agent at D.d, producing the desired behavior. SIPP WG, Expires Sept. 1, 1994 [Page 25] draft-ietf-sip-routing-addr-01.txt February 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 Sept. 1, 1994 [Page 26]