Network Working Group M. Steenstrup Request for Comments: 1479 BBN Systems and Technologies July 1993 Inter-Domain Policy Routing Protocol Specification: Version 1 Status of this Memo This RFC specifies an IAB standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "IAB Official Protocol Standards" for the standardization state and status of this protocol. Distribution of this memo is unlimited. Abstract We present the set of protocols and procedures that constitute Inter-Domain Policy Routing (IDPR). IDPR includes the virtual gateway protocol, the flooding protocol, the route server query protocol, the route generation procedure, the path control protocol, and the data message forwarding procedure. Contributors The following people have contributed to the protocols and procedures described in this document: Helen Bowns, Lee Breslau, Ken Carlberg, Isidro Castineyra, Deborah Estrin, Tony Li, Mike Little, Katia Obraczka, Sam Resheff, Martha Steenstrup, Gene Tsudik, and Robert Woodburn. Table of Contents 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Domain Elements . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Policy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . 6 1.4. Policy Semantics. . . . . . . . . . . . . . . . . . . . . . . 7 1.4.1. Source Policies . . . . . . . . . . . . . . . . . . . . . . 7 1.4.2. Transit Policies. . . . . . . . . . . . . . . . . . . . . . 8 1.5. IDPR Message Encapsulation. . . . . . . . . . . . . . . . . . 9 1.5.1. IDPR Data Message Format. . . . . . . . . . . . . . . . . .11 1.6. Security. . . . . . . . . . . . . . . . . . . . . . . . . . .12 1.7. Timestamps and Clock Synchronization. . . . . . . . . . . . .13 1.8. Network Management. . . . . . . . . . . . . . . . . . . . . .14 1.8.1. Policy Gateway Configuration. . . . . . . . . . . . . . . .17 1.8.2. Route Server Configuration. . . . . . . . . . . . . . . . .18 Steenstrup [Page 1] RFC 1479 IDPR Protocol July 1993 2. Control Message Transport Protocol. . . . . . . . . . . . . . .18 2.1. Message Transmission. . . . . . . . . . . . . . . . . . . . .20 2.2. Message Reception . . . . . . . . . . . . . . . . . . . . . .22 2.3. Message Validation. . . . . . . . . . . . . . . . . . . . . .23 2.4. CMTP Message Formats. . . . . . . . . . . . . . . . . . . . .24 3. Virtual Gateway Protocol. . . . . . . . . . . . . . . . . . . .27 3.1. Message Scope . . . . . . . . . . . . . . . . . . . . . . . .28 3.1.1. Pair-PG Messages. . . . . . . . . . . . . . . . . . . . . .28 3.1.2. Intra-VG Messages . . . . . . . . . . . . . . . . . . . . .29 3.1.3. Inter-VG Messages . . . . . . . . . . . . . . . . . . . . .29 3.1.4. VG Representatives. . . . . . . . . . . . . . . . . . . . .31 3.2. Up/Down Protocol. . . . . . . . . . . . . . . . . . . . . . .31 3.3. Implementation. . . . . . . . . . . . . . . . . . . . . . . .33 3.4. Policy Gateway Connectivity . . . . . . . . . . . . . . . . .35 3.4.1. Within a Virtual Gateway. . . . . . . . . . . . . . . . . .35 3.4.2. Between Virtual Gateways. . . . . . . . . . . . . . . . . .37 3.4.3. Communication Complexity. . . . . . . . . . . . . . . . . .40 3.5. VGP Message Formats . . . . . . . . . . . . . . . . . . . . .41 3.5.1. UP/DOWN . . . . . . . . . . . . . . . . . . . . . . . . . .41 3.5.2. PG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .42 3.5.3. PG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .43 3.5.4. VG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .44 3.5.5. VG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .45 3.5.6. Negative Acknowledgements . . . . . . . . . . . . . . . . .46 4. Routing Information Distribution. . . . . . . . . . . . . . . .47 4.1. AD Representatives. . . . . . . . . . . . . . . . . . . . . .48 4.2. Flooding Protocol . . . . . . . . . . . . . . . . . . . . . .48 4.2.1. Message Generation. . . . . . . . . . . . . . . . . . . . .50 4.2.2. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . .52 4.2.3. Message Acceptance. . . . . . . . . . . . . . . . . . . . .52 4.2.4. Message Incorporation . . . . . . . . . . . . . . . . . . .54 4.2.5. Routing Information Database. . . . . . . . . . . . . . . .56 4.3. Routing Information Message Formats . . . . . . . . . . . . .57 4.3.1. CONFIGURATION . . . . . . . . . . . . . . . . . . . . . . .57 4.3.2. DYNAMIC . . . . . . . . . . . . . . . . . . . . . . . . . .62 4.3.3. Negative Acknowledgements . . . . . . . . . . . . . . . . .63 5. Route Server Query Protocol . . . . . . . . . . . . . . . . . .64 5.1. Message Exchange. . . . . . . . . . . . . . . . . . . . . . .64 5.2. Remote Route Server Communication . . . . . . . . . . . . . .65 5.3. Routing Information . . . . . . . . . . . . . . . . . . . . .66 5.4. Routes. . . . . . . . . . . . . . . . . . . . . . . . . . . .67 5.5. Route Server Message Formats. . . . . . . . . . . . . . . . .67 5.5.1. ROUTING INFORMATION REQUEST . . . . . . . . . . . . . . . .67 5.5.2. ROUTE REQUEST . . . . . . . . . . . . . . . . . . . . . . .68 5.5.3. ROUTE RESPONSE. . . . . . . . . . . . . . . . . . . . . . .71 5.5.4. Negative Acknowledgements . . . . . . . . . . . . . . . . .72 6. Route Generation. . . . . . . . . . . . . . . . . . . . . . . .73 6.1. Searching . . . . . . . . . . . . . . . . . . . . . . . . . .74 Steenstrup [Page 2] RFC 1479 IDPR Protocol July 1993 6.1.1. Implementation. . . . . . . . . . . . . . . . . . . . . . .75 6.2. Route Directionality. . . . . . . . . . . . . . . . . . . . .78 6.3. Route Database. . . . . . . . . . . . . . . . . . . . . . . .79 6.3.1. Cache Maintenance . . . . . . . . . . . . . . . . . . . . .80 7. Path Control Protocol and Data Message Forwarding Procedure . .80 7.1. An Example of Path Setup. . . . . . . . . . . . . . . . . . .81 7.2. Path Identifiers. . . . . . . . . . . . . . . . . . . . . . .84 7.3. Path Control Messages . . . . . . . . . . . . . . . . . . . .85 7.4. Setting Up and Tearing Down a Path. . . . . . . . . . . . . .87 7.4.1. Validating Path Identifiers . . . . . . . . . . . . . . . .89 7.4.2. Path Consistency with Configured Transit Policies . . . . .89 7.4.3. Path Consistency with Virtual Gateway Reachability. . . . .91 7.4.4. Obtaining Resources . . . . . . . . . . . . . . . . . . . .92 7.4.5. Target Response . . . . . . . . . . . . . . . . . . . . . .93 7.4.6. Originator Response . . . . . . . . . . . . . . . . . . . .93 7.4.7. Path Life . . . . . . . . . . . . . . . . . . . . . . . . 94 7.5. Path Failure and Recovery . . . . . . . . . . . . . . . . . 95 7.5.1. Handling Implicit Path Failures . . . . . . . . . . . . . 96 7.5.2. Local Path Repair . . . . . . . . . . . . . . . . . . . . 97 7.5.3. Repairing a Path. . . . . . . . . . . . . . . . . . . . . 98 7.6. Path Control Message Formats. . . . . . . . . . . . . . . . 100 7.6.1. SETUP . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.6.2. ACCEPT. . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.6.3. REFUSE. . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.6.4. TEARDOWN. . . . . . . . . . . . . . . . . . . . . . . . . 104 7.6.5. ERROR . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.6.6. REPAIR. . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.6.7. Negative Acknowledgements . . . . . . . . . . . . . . . . 106 8. Security Considerations . . . . . . . . . . . . . . . . . . . 106 9. Authors's Address . . . . . . . . . . . . . . . . . . . . . . 107 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 1. Introduction In this document, we specify the protocols and procedures that compose Inter-Domain Policy Routing (IDPR). The objective of IDPR is to construct and maintain routes between source and destination administrative domains, that provide user traffic with the services requested within the constraints stipulated for the domains transited. IDPR supports link state routing information distribution and route generation in conjunction with source specified message forwarding. Refer to [5] for a detailed justification of our approach to inter-domain policy routing. 1.1. Domain Elements The IDPR architecture has been designed to accommodate an internetwork with tens of thousands of administrative domains Steenstrup [Page 3] RFC 1479 IDPR Protocol July 1993 collectively containing hundreds of thousands of local networks. Inter-domain policy routes are constructed using information about the services offered by, and the connectivity between, administrative domains. The intra-domain details - gateways, networks, and links traversed - of an inter-domain policy route are the responsibility of intra-domain routing and are thus outside the scope of IDPR. An "administrative domain" (AD) is a collection of contiguous hosts, gateways, networks, and links managed by a single administrative authority. The domain administrator defines service restrictions for transit traffic and service requirements for locally-generated traffic, and selects the addressing schemes and routing procedures that apply within the domain. Within the Internet, each domain has a unique numeric identifier assigned by the Internet Assigned Numbers Authority (IANA). "Virtual gateways" (VGs) are the only IDPR-recognized connecting points between adjacent domains. Each virtual gateway is a collection of directly-connected "policy gateways" (see below) in two adjoining domains, whose existence has been sanctioned by the administrators of both domains. The domain administrators may agree to establish more than one virtual gateway between the two domains. For each such virtual gateway, the two administrators together assign a local numeric identifier, unique within the set of virtual gateways connecting the two domains. To produce a virtual gateway identifier unique within its domain, a domain administrator concatenates the mutually assigned local virtual gateway identifier together with the adjacent domain's identifier. Policy gateways (PGs) are the physical gateways within a virtual gateway. Each policy gateway enforces service restrictions on IDPR transit traffic, as stipulated by the domain administrator, and forwards the traffic accordingly. Within a domain, two policy gateways are "neighbors" if they are in different virtual gateways. A single policy gateway may belong to multiple virtual gateways. Within a virtual gateway, two policy gateways are "peers" if they are in the same domain and are "adjacent" if they are in different domains. Adjacent policy gateways are "directly connected" if the only Internet-addressable entities attached to the connecting medium are policy gateways in the virtual gateways. Note that this definition implies that not only point-to-point links but also networks may serve as direct connections between adjacent policy gateways. The domain administrator assigns to each of its policy gateways a numeric identifier, unique within that domain. A "domain component" is a subset of a domain's entities such that all entities within the subset are mutually reachable via intra-domain routes, but no entities outside the subset are reachable via intra- Steenstrup [Page 4] RFC 1479 IDPR Protocol July 1993 domain routes from entities within the subset. Normally, a domain consists of a single component, namely itself; however, when partitioned, a domain consists of multiple components. Each domain component has an identifier, unique within the Internet, composed of the domain identifier together with the identifier of the lowest- numbered operational policy gateway within the component. All operational policy gateways within a domain component can discover mutual reachability through intra-domain routing information. Hence, all such policy gateways can consistently determine, without explicit negotiation, which of them has the lowest number. 1.2. Policy With IDPR, each domain administrator sets "transit policies" that dictate how and by whom the resources in its domain should be used. Transit policies are usually public, and they specify offered services comprising: - Access restrictions: e.g., applied to traffic to or from certain domains or classes of users. - Quality: e.g., delay, throughput, or error characteristics. - Monetary cost: e.g., charge per byte, message, or unit time. Each domain administrator also sets "source policies" for traffic originating in its domain. Source policies are usually private, and they specify requested services comprising: - Access restrictions: e.g., domains to favor or avoid in routes. - Quality: e.g., acceptable delay, throughput, and reliability. - Monetary cost: e.g., acceptable session cost. 1.3. IDPR Functions IDPR comprises the following functions: - Collecting and distributing routing information including domain transit policies and inter-domain connectivity. - Generating and selecting policy routes based on the routing information distributed and on the source policies configured or requested. - Setting up paths across the Internet using the policy routes generated. Steenstrup [Page 5] RFC 1479 IDPR Protocol July 1993 - Forwarding messages across and between domains along the established paths. - Maintaining databases of routing information, inter-domain policy routes, forwarding information, and configuration information. 1.3.1. IDPR Entities Several different entities are responsible for performing the IDPR functions. Policy gateways, the only IDPR-recognized connecting points between adjacent domains, collect and distribute routing information, participate in path setup, forward data messages along established paths, and maintain forwarding information databases. "Path agents", resident within policy gateways and within "route servers" (see below), act on behalf of hosts to select policy routes, to set up and manage paths, and to maintain forwarding information databases. Any Internet host can reap the benefits of IDPR, as long as there exists a path agent configured to act on its behalf and a means by which the host's messages can reach the path agent. Specifically, a path agent in one domain may be configured to act on behalf of hosts in another domain. In this case, the path agent's domain is an IDPR "proxy" for the hosts' domain. Route servers maintain both the routing information database and the route database, and they generate policy routes using the routing information collected and the source policies requested by the path agents. A route server may reside within a policy gateway, or it may exist as an autonomous entity. Separating the route server functions from the policy gateways frees the policy gateways from both the memory intensive task of database (routing information and route) maintenance and the computationally intensive task of route generation. Route servers, like policy gateways, each have a unique numeric identifier within their domain, assigned by the domain administrator. Given the size of the current Internet, each policy gateway can perform the route server functions, in addition to its message forwarding functions, with little or no degradation in message forwarding performance. Aggregating the routing functions into policy gateways simplifies implementation; one need only install IDPR protocols in policy gateways. Moreover, it simplifies communication between routing functions, as all functions reside within each policy gateway. As the Internet grows, the memory and processing required to perform the route server functions may become a burden for the policy gateways. When this happens, each domain administrator should Steenstrup [Page 6] RFC 1479 IDPR Protocol July 1993 separate the route server functions from the policy gateways in its domain. "Mapping servers" maintain the database of mappings that resolve Internet names and addresses to domain identifiers. Each host is contained within a domain and is associated with a proxy domain which may be identical with the host's domain. The mapping server function will be integrated into the existing DNS name service (see [6]) and will provide mappings between a host and its local and proxy domains. "Configuration servers" maintain the databases of configured information that apply to IDPR entities within their domains. Configuration information for a given domain includes transit policies (i.e., service offerings and restrictions), source policies (i.e., service requirements), and mappings between local IDPR entities and their names and addresses. The configuration server function will be integrated into a domain's existing network management system (see [7]-[8]). 1.4. Policy Semantics The source and transit policies supported by IDPR are intended to accommodate a wide range of services available throughout the Internet. We describe the semantics of these policies, concentrating on the access restriction aspects. To express these policies in this document, we have chosen to use a syntactic variant of Clark's policy term notation [1]. However, we provide a more succinct syntax (see [7]) for actually configuring source and transit policies. 1.4.1. Source Policies Each source policy takes the form of a collection of sets as follows: Applicable Sources and Destinations: {((H(1,1),s(1,1)),...,(H(1,f1),s(1,f1))),...,((H(n,1),s(n,1)),..., (H(n,fn),s(n,fn)))}: The set of groups of source/destination traffic flows to which the source policy applies. Each traffic flow group ((H(i,1),s(i,1)),...,(H(i,fi),s(i,fi))) contains a set of source hosts and corresponding destination hosts. Here, H(i,j) represents a host, and s(i,j), an element of {SOURCE, DESTINATION}, represents an indicator of whether H(i,j) is to be considered as a source or as a destination. Domain Preferences: {(AD(1),x(1)),...,(AD(m),x(m))}: The set of transit domains that the traffic flows should favor, avoid, or exclude. Here, AD(i) represents a domain, and x(i), an element of {FAVOR, AVOID, EXCLUDE}, represents an indicator of whether routes including AD(i) are to be favored, avoided if possible, or Steenstrup [Page 7] RFC 1479 IDPR Protocol July 1993 unconditionally excluded. UCI: The source user class for the traffic flows listed. RequestedServices: The set of requested services not related to access restrictions, i.e., service quality and monetary cost. When selecting a route for a traffic flow from a source host H(i,j) to a destination host H(i,k), where 1 < or = i < or = n and 1 < or = j, k < or = fi, the path agent (see section 1.3.1) must honor the source policy such that: - For each domain, AD(p), contained in the route, AD(p) is not equal to any AD(k), such that 1 < or = k < or = m and x(k) = EXCLUDE. - The route provides the services listed in the set Requested Services. 1.4.2. Transit Policies Each transit policy takes the form of a collection of sets as follows: Source/Destination Access Restrictions: {((H(1,1),AD(1,1),s(1,1)),...,(H(1,f1),AD(1,f1),s(1,f1))),..., ((H(n,1),AD(n,1),s(n,1)),...,(H(n,fn),AD(n,fn),s(n,fn)))}: The set of groups of source and destination hosts and domains to which the transit policy applies. Each domain group ((H(i,1),AD(i,1),s(i,1)),...,(H(i,fi),AD(i,fi),s(i,fi))) contains a set of source and destination hosts and domains such that this transit domain will carry traffic from each source listed to each destination listed. Here, H(i,j) represents a set of hosts, AD(i,j) represents a domain containing H(i,j), and s(i,j), a subset of {SOURCE, DESTINATION}, represents an indicator of whether (H(i,j),AD(i,j)) is to be considered as a set of sources, destinations, or both. Temporal Access Restrictions: The set of time intervals during which the transit policy applies. User Class Access Restrictions: The set of user classes to which the transit policy applies. Offered Services: The set of offered services not related to access restrictions, i.e., service quality and monetary cost. Steenstrup [Page 8] RFC 1479 IDPR Protocol July 1993 Virtual Gateway Access Restrictions: {((VG(1,1),e(1,1)),...,(VG(1,g1),e(1,g1))),...,((VG(m,1),e(m,1)), gateways to which the transit policy applies. Each virtual gateway group ((VG(i,1),e(i,1)),...,(VG(i,gi),e(i,gi))) contains a set of domain entry and exit points such that each entry virtual gateway can reach (barring an intra-domain routing failure) each exit virtual gateway via an intra-domain route supporting the transit policy. Here, VG(i,j) represents a virtual gateway, and e(i,j), a subset of {ENTRY, EXIT}, represents an indicator of whether VG(i,j) is to be considered as a domain entry point, exit point, or both. The domain advertising such a transit policy will carry traffic from any host in the set H(i,j) in AD(i,j) to any host in the set H(i,k) in AD(i,k), where 1 < or = i < or = n and 1 < or = j, k < or = fi, provided that: - SOURCE is an element of s(i,j). - DESTINATION is an element of s(i,k). - Traffic from H(i,j) enters the domain during one of the intervals in the set Temporal Access Restrictions. - Traffic from H(i,j) carries one of the user class identifiers in the set User Class Access Restrictions. - Traffic from H(i,j) enters via any VG(u,v) such that ENTRY is an element of e(u,v), where 1 < or = u < or = m and 1 < or = v < or = gu. - Traffic to H(i,k) leaves via any VG(u,w) such that EXIT is an element of e(u,w), where 1 < or = w < or = gu. 1.5. IDPR Message Encapsulation There are two kinds of IDPR messages: - "Data messages" containing user data generated by hosts. - "Control messages" containing IDPR protocol-related control information generated by policy gateways and route servers. Within an internetwork, only policy gateways and route servers are able to generate, recognize, and process IDPR messages. The existence of IDPR is invisible to all other gateways and hosts, including mapping servers and configuration servers. Mapping servers and configuration servers perform necessary but ancillary functions Steenstrup [Page 9] RFC 1479 IDPR Protocol July 1993 for IDPR, and thus they are not required to handle IDPR messages. An IDPR entity places IDPR-specific information in each IDPR control message it originates; this information is significant only to recipient IDPR entities. Using "encapsulation" across each domain, an IDPR message tunnels from source to destination across an internetwork through domains that may employ disparate intra-domain addressing schemes and routing procedures. As an alternative to encapsulation, we had considered embedding IDPR in IP, as a set of IP options. However, this approach has the following disadvantages: - Only domains that support IP would be able to participate in IDPR; domains that do not support IP would be excluded. - Each gateway, policy or other, in a participating domain would at least have to recognize the IDPR option, even if it did not execute the IDPR protocols. However, most commercial routers are not optimized for IP options processing, and so IDPR message handling might require significant processing at each gateway. - For some IDPR protocols, in particular path control, the size restrictions on IP options would preclude inclusion of all of the necessary protocol-related information. For these reasons, we decided against the IP option approach and in favor of encapsulation. An IDPR message travels from source to destination between consecutive policy gateways. Each policy gateway encapsulates the IDPR message with information, for example an IP header, that will enable the message to reach the next policy gateway. Note that the encapsulating header and the IDPR-specific information may increase the message size beyond the MTU of the given domain. However, message fragmentation and reassembly is the responsibility of the protocol, for example IP, that encapsulates IDPR messages for transport between successive policy gateways; it is not currently the responsibility of IDPR itself. A policy gateway, when forwarding an IDPR message to a peer or a neighbor policy gateway, encapsulates the message in accordance with the addressing scheme and routing procedure of the given domain and indicates in the protocol field of the encapsulating header that the message is indeed an IDPR message. Intermediate gateways between the two policy gateways forward the IDPR message as they would any other message, using the information in the encapsulating header. Only the recipient policy gateway interprets the protocol field, strips off Steenstrup [Page 10] RFC 1479 IDPR Protocol July 1993 the encapsulating header, and processes the IDPR message. A policy gateway, when forwarding an IDPR message to a directly- connected adjacent policy gateway, encapsulates the message in accordance with the addressing scheme of the entities within the virtual gateway and indicates in the protocol field of the encapsulating header that the message is indeed an IDPR message. The recipient policy gateway strips off the encapsulating header and processes the IDPR message. We recommend that the recipient policy gateway perform the following validation check of the encapsulating header, prior to stripping it off. Specifically, the recipient policy gateway should verify that the source address and the destination address in the encapsulating header match the adjacent policy gateway's address and its own address, respectively. Moreover, the recipient policy gateway should verify that the message arrived on the interface designated for the direct connection to the adjacent policy gateway. These checks help to ensure that IDPR traffic that crosses domain boundaries does so only over direct connections between adjacent policy gateways. Policy gateways forward IDPR data messages according to a forwarding information database which maps "path identifiers", carried in the data messages, into next policy gateways. Policy gateways forward IDPR control messages according to next policy gateways selected by the particular IDPR control protocols associated with the messages. Distinguishing IDPR data messages and IDPR control messages at the encapsulating protocol level, instead of at the IDPR protocol level, eliminates an extra level of dispatching and hence makes IDPR message forwarding more efficient. When encapsulated within IP messages, IDPR data messages and IDPR control messages carry the IP protocol numbers 35 and 38, respectively. 1.5.1. IDPR Data Message Format The path agents at a source domain determine which data messages generated by local hosts are to be handled by IDPR. To each data message selected for IDPR handling, a source path agent prepends the following header: Steenstrup [Page 11] RFC 1479 IDPR Protocol July 1993 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VERSION | PROTO | LENGTH | +---------------+---------------+-------------------------------+ | PATH ID | | | +---------------------------------------------------------------+ | TIMESTAMP | +---------------------------------------------------------------+ | INT/AUTH | | | +---------------------------------------------------------------+ VERSION (8 bits) Version number for IDPR data messages, currently equal to 1. PROTO (8 bits) Numeric identifier for the protocol with which to process the contents of the IDPR data message. Only the path agent at the destination interprets and acts upon the contents of the PROTO field. LENGTH (16 bits) Length of the entire IDPR data message in bytes. PATH ID (64 bits) Path identifier assigned by the source's path agent and consisting of the numeric identifier for the path agent's domain (16 bits), the numeric identifier for the path agent's policy gateway (16 bits), and the path agent's local path identifier (32 bits) (see section 7.2). TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970 0:00 GMT. INT/AUTH (variable) Computed integrity/authentication value, dependent on the type of integrity/authentication requested during path setup. We describe the IDPR control message header in section 2.4. 1.6. Security IDPR contains mechanisms for verifying message integrity and source authenticity and for protecting against certain types of denial of service attacks. It is particularly important to keep IDPR control messages intact, because they carry control information critical to the construction and use of viable policy routes between domains. All IDPR messages carry a single piece of information, referred to as Steenstrup [Page 12] RFC 1479 IDPR Protocol July 1993 the "integrity/authentication value", which may be used not only to detect message corruption but also to verify the authenticity of the message source. In the Internet, the IANA will sanction the set of valid algorithms which may be used to compute the integrity/authentication values. This set may include algorithms that perform only message integrity checks such as n-bit cyclic redundancy checksums (CRCs), as well as algorithms that perform both message integrity and source authentication checks such as signed hash functions of message contents. Each domain administrator is free to select any integrity/authentication algorithm, from the set specified by the IANA, for computing the integrity/authentication values contained in its domain's messages. However, we recommend that IDPR entities in each domain be capable of executing all of the valid algorithms so that an IDPR control message originating at an entity in one domain can be properly checked by an entity in another domain. Each IDPR control message must carry a non-null integrity/authentication value. We recommend that control message integrity/authentication be based on a digital signature algorithm applied to a one-way hash function, such as RSA applied to MD5 [17], which simultaneously verifies message integrity and source authenticity. The digital signature may be based on either public- key or private-key cryptography. Our approach to digital signature use in IDPR is based on the privacy-enhanced Internet electronic mail service [13]-[15], already available in the Internet. We do not require that IDPR data messages carry a non-null integrity/authentication value. In fact, we recommend that a higher layer (end-to-end) procedure, and not IDPR, assume responsibility for checking the integrity and authenticity of data messages, because of the amount of computation involved. 1.7. Timestamps and Clock Synchronization Each IDPR message carries a timestamp (expressed in seconds elapsed since 1 January 1970 0:00 GMT, following the UNIX precedent) supplied by the source IDPR entity, which serves to indicate the age of the message. IDPR entities use the absolute value of the timestamp to confirm that a message is current and use the relative difference between timestamps to determine which message contains the more recent information. All IDPR entities must possess internal clocks that are synchronized to some degree, in order for the absolute value of a message timestamp to be meaningful. The synchronization granularity required by IDPR is on the order of minutes and can be achieved manually. Steenstrup [Page 13] RFC 1479 IDPR Protocol July 1993 Thus, a clock synchronization protocol operating among all IDPR entities in all domains, while useful, is not necessary. An IDPR entity can determine whether to accept or reject a message based on the discrepancy between the message's timestamp and the entity's own internal clock time. Any IDPR message whose timestamp lies outside of the acceptable range may contain stale or corrupted information or may have been issued by a source whose internal clock has lost synchronization with the message recipient's internal clock. Timestamp checks are required for control messages because of the consequences of propagating and acting upon incorrect control information. However, timestamp checks are discretionary for data messages but may be invoked during problem diagnosis, for example, when checking for suspected message replays. We note that none of the IDPR protocols contain explicit provisions for dealing with an exhausted timestamp space. As timestamp space exhaustion will not occur until well into the next century, we expect timestamp space viability to outlast the IDPR protocols. 1.8. Network Management In this document, we do not describe how to configure and manage IDPR. However, in this section, we do provide a list of the types of IDPR configuration information required. Also, in later sections describing the IDPR protocols, we briefly note the types of exceptional events that must be logged for network management. Complete descriptions of IDPR entity configuration and IDPR managed objects appear in [7] and [8] respectively. To participate in inter-domain policy routing, policy gateways and route servers within a domain each require configuration information. Some of the configuration information is specifically defined within the given domain, while some of the configuration information is universally defined throughout an internetwork. A domain administrator determines domain-specific information, and in the Internet, the IANA determines globally significant information. To produce valid domain configurations, the domain administrators must receive the following global information from the IANA: - For each integrity/authentication type, the numeric identifier, syntax, and semantics. Available integrity and authentication types include but are not limited to: o public-key based signatures; o private-key based signatures; Steenstrup [Page 14] RFC 1479 IDPR Protocol July 1993 o cyclic redundancy checksums; o no integrity/authentication. - For each user class, the numeric identifier, syntax, and semantics. Available user classes include but are not limited to: o federal (and if necessary, agency-specific such as NSF, DOD, DOE, etc.); o research; o commercial; o support. - For each offered service that may be advertised in transit policies, the numeric identifier, syntax, and semantics. Available offered services include but are not limited to: o average message delay; o message delay variation; o average bandwidth available; o available bandwidth variation; o maximum transfer unit (MTU); o charge per byte; o charge per message; o charge per unit time. - For each access restriction that may be advertised in transit policies, the numeric identifier, syntax, and semantics. Available access restrictions include but are not limited to: o Source and destination domains and host sets. o User classes. o Entry and exit virtual gateways. o Time of day. Steenstrup [Page 15] RFC 1479 IDPR Protocol July 1993 - For each requested service that may appear within a path setup message, the numeric identifier, syntax, and semantics. Available requested services include but are not limited to: o maximum path life in minutes, messages, or bytes; o integrity/authentication algorithms to be used on data messages sent over the path; o upper bound on path delay; o minimum delay path; o upper bound on path delay variation; o minimum delay variation path; o lower bound on path bandwidth; o maximum bandwidth path; o upper bound on monetary cost; o minimum monetary cost path. In an internetwork-wide implementation of IDPR, the set of global configuration parameters and their syntax and semantics must be consistent across all participating domains. The IANA, responsible for establishing the full set of global configuration parameters in the Internet, relies on the cooperation of the administrators of all participating domains to ensure that the global parameters are consistent with the desired transit policies and user service requirements of each domain. Moreover, as the syntax and semantics of the global parameters affects the syntax and semantics of the corresponding IDPR software, the IANA must carefully define each global parameter so that it is unlikely to require future modification. The IANA provides configured global information to configuration servers in all domains participating in IDPR. Each domain administrator uses the configured global information maintained by its configuration servers to develop configurations for each IDPR entity within its domain. Each configuration server retains a copy of the configuration for each local IDPR entity and also distributes the configuration to that entity using, for example, SNMP. Steenstrup [Page 16] RFC 1479 IDPR Protocol July 1993 1.8.1. Policy Gateway Configuration Each policy gateway must contain sufficient configuration information to perform its IDPR functions, which subsume those of the path agent. These include: validating IDPR control messages; generating and distributing virtual gateway connectivity and routing information messages to peer, neighbor, and adjacent policy gateways; distributing routing information messages to route servers in its domain; resolving destination addresses; requesting policy routes from route servers; selecting policy routes and initiating path setup; ensuring consistency of a path with its domain's transit policies; establishing path forwarding information; and forwarding IDPR data messages along existing paths. The necessary configuration information includes the following: - For each integrity/authentication type, the numeric identifier, syntax, and semantics. - For each policy gateway and route server in the given domain, the numeric identifier and set of addresses or names. - For each virtual gateway connected to the given domain, the numeric identifier, the numeric identifiers for the constituent peer policy gateways, and the numeric identifier for the adjacent domain. - For each virtual gateway of which the given policy gateway is a member, the numeric identifiers and set of addresses for the constituent adjacent policy gateways. - For each policy gateway directly-connected and adjacent to the given policy gateway, the local connecting interface. - For each local route server to which the given policy gateway distributes routing information, the numeric identifier. - For each source policy applicable to hosts within the given domain, the syntax and semantics. - For each transit policy applicable to the domain, the numeric identifier, syntax, and semantics. - For each requested service that may appear within a path setup message, the numeric identifier, syntax, and semantics. - For each source user class, the numeric identifier, syntax, and semantics. Steenstrup [Page 17] RFC 1479 IDPR Protocol July 1993 1.8.2. Route Server Configuration Each route server must contain sufficient configuration information to perform its IDPR functions, which subsume those of the path agent. These include: validating IDPR control messages; deciphering and storing the contents of routing information messages; exchanging routing information with other route servers and policy gateways; generating policy routes that respect transit policy restrictions and source service requirements; distributing policy routes to path agents in policy gateways; resolving destination addresses; selecting policy routes and initiating path setup; establishing path forwarding information; and forwarding IDPR data messages along existing paths. The necessary configuration information includes the following: - For each integrity/authentication type, the numeric identifier, syntax, and semantics. - For each policy gateway and route server in the given domain, the numeric identifier and set of addresses or names. - For each source policy applicable to hosts within the given domain, the syntax and semantics. - For access restriction that may be advertised in transit policies, the numeric identifier, syntax, and semantics. - For each offered service that may be advertised in transit policies, the numeric identifier, syntax, and semantics. - For each requested service that may appear within a path setup message, the numeric identifier, syntax, and semantics. - For each source user class, the numeric identifier, syntax, and semantics. 2. Control Message Transport Protocol IDPR control messages convey routing-related information that directly affects the policy routes generated and the paths set up across the Internet. Errors in IDPR control messages can have widespread, deleterious effects on inter-domain policy routing, and so the IDPR protocols have been designed to minimize loss and corruption of control messages. For every control message it transmits, each IDPR protocol expects to receive notification as to whether the control message successfully reached the intended IDPR recipient. Moreover, the IDPR recipient of a control message first verifies that the message appears to be well-formed, before acting on its contents. Steenstrup [Page 18] RFC 1479 IDPR Protocol July 1993 All IDPR protocols use the Control Message Transport Protocol (CMTP), a connectionless, transaction-based transport layer protocol, for communication with intended recipients of control messages. CMTP retransmits unacknowledged control messages and applies integrity and authenticity checks to received control messages. There are three types of CMTP messages: DATAGRAM: Contains IDPR control messages. ACK: Positive acknowledgement in response to a DATAGRAM message. NAK: Negative acknowledgement in response to a DATAGRAM message. Each CMTP message contains several pieces of information supplied by the sender that allow the recipient to test the integrity and authenticity of the message. The set of integrity and authenticity checks performed after CMTP message reception are collectively referred to as "validation checks" and are described in section 2.3. When we first designed the IDPR protocols, CMTP as a distinct protocol did not exist. Instead, CMTP-equivalent functionality was embedded in each IDPR protocol. To provide a cleaner implementation, we later decided to provide a single transport protocol that could be used by all IDPR protocols. We originally considered using an existing transport protocol, but rejected this approach for the following reasons: - The existing reliable transport protocols do not provide all of the validation checks, in particular the timestamp and authenticity checks, required by the IDPR protocols. Hence, if we were to use one of these protocols, we would still have to provide a separate protocol on top of the transport protocol to force retransmission of IDPR messages that failed to pass the required validation checks. - Many of the existing reliable transport protocols are window-based and hence can result in increased message delay and resource use when, as is the case with IDPR, multiple independent messages use the same transport connection. A single message experiencing transmission problems and requiring retransmission can prevent the window from advancing, forcing all subsequent messages to queue behind it. Moreover, many of the window-based protocols do not support selective retransmission of failed messages but instead require retransmission of not only the failed message but also all preceding messages within the window. For these reasons, we decided against using an existing transport Steenstrup [Page 19] RFC 1479 IDPR Protocol July 1993 protocol and in favor of developing CMTP. 2.1. Message Transmission At the transmitting entity, when an IDPR protocol is ready to issue a control message, it passes a copy of the message to CMTP; it also passes a set of parameters to CMTP for inclusion in the CMTP header and for proper CMTP message handling. In turn, CMTP converts the control message and associated parameters into a DATAGRAM by prepending the appropriate header to the control message. The CMTP header contains several pieces of information to aid the message recipient in detecting errors (see section 2.4). Each IDPR protocol can specify all of the following CMTP parameters applicable to its control message: - IDPR protocol and message type. - Destination. - Integrity/authentication scheme. - Timestamp. - Maximum number of transmissions allotted. - Retransmission interval in microseconds. One of these parameters, the timestamp, can be specified directly by CMTP as the internal clock time at which the message is transmitted. However, two of the IDPR protocols, namely flooding and path control, themselves require message generation timestamps for proper protocol operation. Thus, instead of requiring CMTP to pass back a timestamp to an IDPR protocol, we simplify the service interface between CMTP and the IDPR protocols by allowing an IDPR protocol to specify the timestamp in the first place. Using the control message and accompanying parameters supplied by the IDPR protocol, CMTP constructs a DATAGRAM, adding to the header CMTP-specific parameters. In particular, CMTP assigns a "transaction identifier" to each DATAGRAM generated, which it uses to associate acknowledgements with DATAGRAM messages. Each DATAGRAM recipient includes the received transaction identifier in its returned ACK or NAK, and each DATAGRAM sender uses the transaction identifier to match the received ACK or NAK with the original DATAGRAM. A single DATAGRAM, for example a routing information message or a path control message, may be handled by CMTP at many different policy gateways. Within a pair of consecutive IDPR entities, the DATAGRAM Steenstrup [Page 20] RFC 1479 IDPR Protocol July 1993 sender expects to receive an acknowledgement from the DATAGRAM recipient. However, only the IDPR entity that actually generated the original CMTP DATAGRAM has control over the transaction identifier, because that entity may supply a digital signature that covers the entire DATAGRAM. The intermediate policy gateways that transmit the DATAGRAM do not change the transaction identifier. Nevertheless, at each DATAGRAM recipient, the transaction identifier must uniquely distinguish the DATAGRAM so that only one acknowledgement from the next DATAGRAM recipient matches the original DATAGRAM. Therefore, the transaction identifier must be globally unique. The transaction identifier consists of the numeric identifiers for the domain and IDPR entity (policy gateway or route server) issuing the original DATAGRAM, together with a 32-bit local identifier assigned by CMTP operating within that IDPR entity. We recommend implementing the 32-bit local identifier either as a simple counter incremented for each DATAGRAM generated or as a fine granularity clock. The former always guarantees uniqueness of transaction identifiers; the latter guarantees uniqueness of transaction identifiers, provided the clock granularity is finer than the minimum possible interval between DATAGRAM generations and the clock wrapping period is longer than the maximum round-trip delay to and from any internetwork destination. Before transmitting a DATAGRAM, CMTP computes the length of the entire message, taking into account the prescribed integrity/authentication scheme, and then computes the integrity/authentication value over the whole message. CMTP includes both of these quantities, which are crucial for checking message integrity and authenticity at the recipient, in the DATAGRAM header. After sending a DATAGRAM, CMTP saves a copy and sets an associated retransmission timer, as directed by the IDPR protocol parameters. If the retransmission timer fires and CMTP has received neither an ACK nor a NAK for the DATAGRAM, CMTP then retransmits the DATAGRAM, provided this retransmission does not exceed the transmission allotment. Whenever a DATAGRAM exhausts its transmission allotment, CMTP discards the DATAGRAM, informs the IDPR protocol that the control message transmission was not successful, and logs the event for network management. In this case, the IDPR protocol may either resubmit its control message to CMTP, specifying an alternate destination, or discard the control message altogether. Steenstrup [Page 21] RFC 1479 IDPR Protocol July 1993 2.2. Message Reception At the receiving entity, when CMTP obtains a DATAGRAM, it takes one of the following actions, depending upon the outcome of the message validation checks: - The DATAGRAM passes the CMTP validation checks. CMTP then delivers the DATAGRAM with enclosed IDPR control message, to the appropriate IDPR protocol, which in turn applies its own integrity checks to the control message before acting on the contents. The recipient IDPR protocol, except in one case, directs CMTP to generate an ACK and return the ACK to the sender. That exception is the up/down protocol (see section 3.2) which determines reachability of adjacent policy gateways and does not use CMTP ACK messages to notify the sender of message reception. Instead, the up/down protocol messages themselves carry implicit information about message reception at the adjacent policy gateway. In the cases where the recipient IDPR protocol directs CMTP to generate an ACK, it may pass control information to CMTP for inclusion in the ACK, depending on the contents of the original IDPR control message. For example, a route server unable to fill a request for routing information may inform the requesting IDPR entity, through an ACK for the initial request, to place its request elsewhere. - The DATAGRAM fails at least one of the CMTP validation checks. CMTP then generates a NAK, returns the NAK to the sender, and discards the DATAGRAM, regardless of the type of IDPR control message contained in the DATAGRAM. The NAK indicates the nature of the validation failure and serves to help the sender establish communication with the recipient. In particular, the CMTP NAK provides a mechanism for negotiation of IDPR version and integrity/authentication scheme, two parameters crucial for establishing communication between IDPR entities. Upon receiving an ACK or a NAK, CMTP immediately discards the message if at least one of the validation checks fails or if it is unable to locate the associated DATAGRAM. CMTP logs the latter event for network management. Otherwise, if all of the validation checks pass and if it is able to locate the associated DATAGRAM, CMTP clears the associated retransmission timer and then takes one of the following actions, depending upon the message type: - The message is an ACK. CMTP discards the associated DATAGRAM and delivers the ACK, which may contain IDPR control information, to the appropriate IDPR protocol. - The message is a NAK. If the associated DATAGRAM has exhausted its transmission allotment, CMTP discards the DATAGRAM, informs the Steenstrup [Page 22] RFC 1479 IDPR Protocol July 1993 appropriate IDPR protocol that the control message transmission was not successful, and logs the event for network management. Otherwise, if the associated DATAGRAM has not yet exhausted its transmission allotment, CMTP first checks its copy of the DATAGRAM against the failure indication contained in the NAK. If its DATAGRAM copy appears to be intact, CMTP retransmits the DATAGRAM and sets the associated retransmission timer. However, if its DATAGRAM copy appears to be corrupted, CMTP discards the DATAGRAM, informs the IDPR protocol that the control message transmission was not successful, and logs the event for network management. 2.3. Message Validation On every CMTP message received, CMTP performs a set of validation checks to test message integrity and authenticity. The order in which these tests are executed is important. CMTP must first determine if it can parse enough of the message to compute the integrity/authentication value. (Refer to section 2.4 for a description of CMTP message formats.) Then, CMTP must immediately compute the integrity/authentication value before checking other header information. An incorrect integrity/authentication value means that the message is corrupted, and so it is likely that CMTP header information is incorrect. Checking specific header fields before computing the integrity/authentication value not only may waste time and resources, but also may lead to incorrect diagnoses of a validation failure. The CMTP validation checks are as follows: - CMTP verifies that it can recognize both the control message version type contained in the header. Failure to recognize either one of these values means that CMTP cannot continue to parse the message. - CMTP verifies that it can recognize and accept the integrity/authentication type contained in the header; no integrity/authentication is not an acceptable type for CMTP. - CMTP computes the integrity/authentication value and verifies that it equals the integrity/authentication value contained in the header. For key-based integrity/authentication schemes, CMTP may use the source domain identifier contained in the CMTP header to index the correct key. Failure to index a key means that CMTP cannot compute the integrity/authentication value. - CMTP computes the message length in bytes and verifies that it equals the length value contained in the header. Steenstrup [Page 23] RFC 1479 IDPR Protocol July 1993 - CMTP verifies that the message timestamp is in the acceptable range. The message should be no more recent than cmtp_new (300) seconds ahead of the entity's current internal clock time. In this document, when we present an IDPR system configuration parameter, such as cmtp_new, we usually follow it with a recommended value in parentheses. The cmtp_new value allows some clock drift between IDPR entities. Moreover, each IDPR protocol has its own limit on the maximum age of its control messages. The message should be no less recent than a prescribed number of seconds behind the recipient entity's current internal clock time. Hence, each IDPR protocol performs its own message timestamp check in addition to that performed by CMTP. - CMTP verifies that it can recognize the IDPR protocol designated for the enclosed control message. Whenever CMTP encounters a failure while performing any of these validation checks, it logs the event for network management. If the failure occurs on a DATAGRAM, CMTP immediately generates a NAK containing the reason for the failure, returns the NAK to the sender, and discards the DATAGRAM message. If the failure occurs on an ACK or a NAK, CMTP discards the ACK or NAK message. 2.4. CMTP Message Formats In designing the format of IDPR control messages, we have attempted to strike a balance between efficiency of link bandwidth usage and efficiency of message processing. In general, we have chosen compact representations for IDPR information in order to minimize the link bandwidth consumed by IDPR-specific information. However, we have also organized IDPR information in order to speed message processing, which does not always result in minimum link bandwidth usage. To limit link bandwidth usage, we currently use fixed-length identifier fields in IDPR messages; domains, virtual gateways, policy gateways, and route servers are all represented by fixed-length identifiers. To simplify message processing, we currently align fields containing an even number of bytes on even-byte boundaries within a message. In the future, if the Internet adopts the use of super domains, we will offer hierarchical, variable-length identifier fields in an updated version of IDPR. The header of each CMTP message contains the following information: Steenstrup [Page 24] RFC 1479 IDPR Protocol July 1993 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VERSION | PRT | MSG | DPR | DMS | I/A TYP | +---------------+-------+-------+-------+-------+---------------+ | SOURCE AD | SOURCE ENT | +-------------------------------+-------------------------------+ | TRANS ID | +---------------------------------------------------------------+ | TIMESTAMP | +-------------------------------+-------------------------------+ | LENGTH | message specific | +-------------------------------+-------------------------------+ | DATAGRAM AD | DATAGRAM ENT | +-------------------------------+-------------------------------+ | INFORM | +---------------------------------------------------------------+ | INT/AUTH | | | +---------------------------------------------------------------+ VERSION (8 bits) Version number for IDPR control messages, currently equal to 1. PRT (4 bits) Numeric identifier for the control message transport protocol, equal to 0 for CMTP. MSG (4 bits) Numeric identifier for the CMTP message type,equal to 0 for a DATAGRAM, 1 for an ACK, and 2 for a NAK. DPR (4 bits) Numeric identifier for the original DATAGRAM's IDPR protocol type. DMS (4 bits) Numeric identifier for the original DATAGRAM's IDPR message type. I/A TYP (8 bits) Numeric identifier for the integrity/authentication scheme used. CMTP requires the use of an integrity/authentication scheme; this value must not be set equal to 0, indicating no integrity/authentication in use. SOURCE AD (16 bits) Numeric identifier for the domain containing the IDPR entity that generated the message. SOURCE ENT (16 bits) Numeric identifier for the IDPR entity that generated the message. Steenstrup [Page 25] RFC 1479 IDPR Protocol July 1993 TRANSACTION ID (32 bits) Local transaction identifier assigned by the IDPR entity that generated the original DATAGRAM. TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970 0:00 GMT. LENGTH (16 bits) Length of the entire IDPR control message, including the CMTP header, in bytes. message specific (16 bits) Dependent upon CMTP message type. For DATAGRAM and ACK messages: RESERVED (16 bits) Reserved for future use and currently set equal to 0. For NAK messages: ERR TYP (8 bits) Numeric identifier for the type of CMTP validation failure encountered. Validation failures include the following types: 1. Unrecognized IDPR control message version number. 2. Unrecognized CMTP message type. 3. Unrecognized integrity/authentication scheme. 4. Unacceptable integrity/authentication scheme.