RFCs in HTML Format


RFC 1479

Network Working Group                                     M. Steenstrup
Request for Comments: 1479                 BBN Systems and Technologies
                                                              July 1993


     Inter-Domain Policy Routing Protocol Specification: Version 1

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. 5. Unable to locate key using source domain. 6. Incorrect integrity/authentication value. 7. Incorrect message length. 8. Message timestamp out of range. 9. Unrecognized IDPR protocol designated for the enclosed control message. Steenstrup [Page 26]
RFC 1479 IDPR Protocol July 1993 ERR INFO (8 bits) CMTP supplies the following additional information for the designated types of validation failures: Type 1: Acceptable IDPR control message version number. Types 3 and 4: Acceptable integrity/authentication type. DATAGRAM AD (16 bits) Numeric identifier for the domain containing the IDPR entity that generated the original DATAGRAM. Present only in ACK and NAK messages. DATAGRAM ENT (16 bits) Numeric identifier for the IDPR entity that generated the original DATAGRAM. Present only in ACK and NAK messages. INFORM (optional,variable) Information to be interpreted by the IDPR protocol that issued the original DATAGRAM. Present only in ACK messages and dependent on the original DATAGRAM's IDPR protocol type. INT/AUTH (variable) Computed integrity/authentication value, dependent on the type of integrity/authentication scheme used. 3. Virtual Gateway Protocol Every policy gateway within a domain participates in gathering information about connectivity within and between virtual gateways of which it is a member and in distributing this information to other virtual gateways in its domain. We refer to these functions collectively as the Virtual Gateway Protocol (VGP). The information collected through VGP has both local and global significance for IDPR. Virtual gateway connectivity information, distributed to policy gateways within a single domain, aids those policy gateways in selecting routes across and between virtual gateways connecting their domain to adjacent domains. Inter-domain connectivity information, distributed throughout an internetwork in routing information messages, aids route servers in constructing feasible policy routes. Provided that a domain contains simple virtual gateway and transit policy configurations, one need only implement a small subset of the VGP functions. The connectivity among policy gateways within a virtual gateway and the heterogeneity of transit policies within a Steenstrup [Page 27]
RFC 1479 IDPR Protocol July 1993 domain determine which VGP functions must be implemented, as we explain toward the end of this section. 3.1. Message Scope Policy gateways generate VGP messages containing information about perceived changes in virtual gateway connectivity and distribute these messages to other policy gateways within the same domain and within the same virtual gateway. We classify VGP messages into three distinct categories: "pair-PG", "intra-VG", and "inter-VG", depending upon the scope of message distribution. Policy gateways use CMTP for reliable transport of VGP messages. The issuing policy gateway must communicate to CMTP the maximum number of transmissions per VGP message, vgp_ret, and the interval between VGP message retransmissions, vgp_int microseconds. The recipient policy gateway must determine VGP message acceptability; conditions of acceptability depend on the type of VGP message, as we describe below. Policy gateways store, act upon, and in the case of inter-VG messages, forward the information contained in acceptable VGP messages. VGP messages that pass the CMTP validation checks but fail a specific VGP message acceptability check are considered to be unacceptable and are hence discarded by recipient policy gateways. A policy gateway that receives an unacceptable VGP message also logs the event for network management. 3.1.1. Pair-PG Messages Pair-PG message communication occurs between the two members of a pair of adjacent, peer, or neighbor policy gateways. With IDPR, the only pair-PG messages are those periodically generated by the up/down protocol and used to monitor mutual reachability between policy gateways. A pair-PG message is "acceptable" if: - It passes the CMTP validation checks. - Its timestamp is less than vgp_old (300) seconds behind the recipient's internal clock time. - Its destination policy gateway identifier coincides with the identifier of the recipient policy gateway. - Its source policy gateway identifier coincides with the identifier of a policy gateway configured for the recipient's domain or Steenstrup [Page 28]
RFC 1479 IDPR Protocol July 1993 associated virtual gateway. 3.1.2. Intra-VG Messages Intra-VG message communication occurs between one policy gateway and all of its peers. Whenever a policy gateway discovers that its connectivity to an adjacent or neighbor policy gateway has changed, it issues an intra-VG message indicating the connectivity change to all of its reachable peers. Whenever a policy gateway detects that a previously unreachable peer is now reachable, it issues, to that peer, intra-VG messages indicating connectivity to adjacent and neighbor policy gateways. If the issuing policy gateway fails to receive an analogous intra-VG message from the newly reachable peer within twice the configured VGP retransmission interval, vgp_int microseconds, it actively requests the intra-VG message from that peer. These message exchanges ensure that peers maintain a consistent view of each others' connectivity to adjacent and neighbor policy gateways. An intra-VG message is "acceptable" if: - It passes the CMTP validation checks. - Its timestamp is less than vgp_old (300) seconds behind the recipient's internal clock time. - Its virtual gateway identifier coincides with that of a virtual gateway configured for the recipient's domain. 3.1.3. Inter-VG Messages Inter-VG message communication occurs between one policy gateway and all of its neighbors. Whenever the lowest-numbered operational policy gateway in a set of mutually reachable peers discovers that its virtual gateway's connectivity to the adjacent domain or to another virtual gateway has changed, it issues an inter-VG message indicating the connectivity change to all of its neighbors. Specifically, the policy gateway distributes an inter-VG message to a "VG representative" policy gateway (see section 3.1.4 below) in each virtual gateway in the domain. Each VG representative in turn propagates the inter-VG message to each of its peers. Whenever the lowest-numbered operational policy gateway in a set of mutually peers detects that one or more previously unreachable peers are now reachable, it issues, to the lowest-numbered operational policy gateway in all other virtual gateways, requests for inter-VG information indicating connectivity to adjacent domains and to other virtual gateways. The recipient policy gateways return the requested Steenstrup [Page 29]
RFC 1479 IDPR Protocol July 1993 inter-VG messages to the issuing policy gateway, which in turn distributes the messages to the newly reachable peers. These message exchanges ensure that virtual gateways maintain a consistent view of each others' connectivity, while consuming minimal domain resources in distributing connectivity information. An inter-VG message contains information about the entire virtual gateway, not just about the issuing policy gateway. Thus, when virtual gateway connectivity changes happen in rapid succession, recipients of the resultant inter-VG messages should be able to determine the most recent message and that message must contain the current virtual gateway connectivity information. To ensure that the connectivity information distributed is consistent and unambiguous, we designate a single policy gateway, namely the lowest-numbered operational peer, for generating and distributing inter-VG messages. It is a simple procedure for a set of mutually reachable peers to determine the lowest-numbered member, as we describe in section 3.2 below. To understand why a single member of a virtual gateway must issue inter-VG messages, consider the following example. Suppose that two peers in a virtual gateway each detect a different connectivity change and generate separate inter-VG messages. Recipients of these messages may not be able to determine which message is more recent if policy gateway internal clocks are not perfectly synchronized. Moreover, even if the clocks were perfectly synchronized, and hence message recency could be consistently determined, it is possible for each peer to issue its inter-VG message before receiving current information from the other. As a result, neither inter-VG message contains the correct connectivity from the perspective of the virtual gateway. However, these problems are eliminated if all inter-VG messages are generated by a single peer within a virtual gateway, in particular the lowest-numbered operational policy gateway. An inter-VG message is "acceptable" if: - It passes the CMTP validation checks. - Its timestamp is less than vgp_old (300) seconds behind the recipient's internal clock time. - Its virtual gateway identifier coincides with that of a virtual gateway configured for the recipient's domain. - Its source policy gateway identifier represents the lowest numbered operational member of the issuing virtual gateway, reachable from the recipient. Steenstrup [Page 30]
RFC 1479 IDPR Protocol July 1993
RFC 1479 IDPR Protocol July 1993 indicates whether the route can be used from destination to source (1 from destination, 0 not from destination). At least one of the first and second flags must be set to 1, if NUM RTS is greater than 0. NUM AD (8 bits) Number of domains in the policy route, not including the first domain on the route. AD LEN (8 bits) Length of the information associated with a particular domain, in bytes, beginning with the next field. VG (8 bits) Numeric identifier for an exit virtual gateway. ADJ AD (16 bits) Numeric identifier for the adjacent domain connected to the virtual gateway. ADJ CMP (16 bits) Numeric identifier for the adjacent domain component. Used by policy gateways to select a route across a virtual gateway connecting to a partitioned domain. NUM TP (16 bits) Number of transit policies that apply to the section of the route traversing the domain component. TP (16 bits) Numeric identifier for a transit policy. 5.5.4. Negative Acknowledgements When a policy gateway receives an unacceptable RSQP message that passes the CMTP validation checks, it includes, in its CMTP ACK, an appropriate negative acknowledgement. This information is placed in the INFORM field of the CMTP ACK (described previously in section 2.4); the numeric identifier for each type of RSQP negative acknowledgement is contained in the left-most 8 bits of the INFORM field. Negative acknowledgements associated with RSQP include the following types: 1. Unrecognized RSQP message type. Numeric identifier for the unrecognized message type (8 bits). 2. Out-of-date RSQP message. 3. Unable to fill requests for routing information from the following domains. Number of domains for which requests cannot be filled (16 bits); a value of 0 indicates that the route server cannot fill any of the requests. Numeric identifier for each domain for which a request cannot be filled (16 bits). Steenstrup [Page 72]
RFC 1479 IDPR Protocol July 1993 4. Unable to fill requests for routes to the following destination domain. Numeric identifier for the destination domain (16 bits). 6. Route Generation Route generation is the most computationally complex part of IDPR, because of the number of domains and the number and heterogeneity of policies that it must accommodate. Route servers must generate policy routes that satisfy the requested services of the source domains and respect the offered services of the transit domains. We distinguish requested qualities of service and route generation with respect to them as follows: - Requested service limits include upper bounds on route delay, route delay variation, and session monetary cost and lower bounds on available route bandwidth. Generating a route that must satisfy more than one quality of service constraint, for example route delay of no more than X seconds and available route bandwidth of no less than Y bits per second, is an NP-complete problem. - Optimal requested services include minimum route delay, minimum route delay variation, minimum session monetary cost, and maximum available route bandwidth. In the worst case, the computational complexity of generating a route that is optimal with respect to a given requested service is O((N + L) log N) for Dijkstra's shortest path first (SPF) search and O(N + (L * L)) for breadth-first (BF) search, where N is the number of nodes and L is the number of links in the search graph. Multi-criteria optimization, for example finding a route with minimal delay variation and minimal session monetary cost, may be defined in several ways. One approach to multi-criteria optimization is to assign each link a single value equal to a weighted sum of the values of the individual offered qualities of service and generate a route that is optimal with respect to this new criterion. However, selecting the weights that yield the desired route generation behavior is itself an optimization procedure and hence not trivial. To help contain the combinatorial explosion of processing and memory costs associated with route generation, we supply the following guidelines for generation of suitable policy routes: - Each route server should only generate policy routes from the perspective of its own domain as source; it need not generate policy routes for arbitrary source/destination domain pairs. Thus, we can distribute the computational burden over all route servers. - Route servers should precompute routes for which they anticipate Steenstrup [Page 73]
RFC 1479 IDPR Protocol July 1993 requests and should generate routes on demand only in order to satisfy unanticipated route requests. Hence, a single route server can distribute its computational burden over time. - Route servers should cache the results of route generation, in order to minimize the computation associated with responding to future route requests. - To handle requested service limits, a route server should always select the first route generated that satisfies all of the requested service limits. - To handle multi-criteria optimization in route selection, a route server should generate routes that are optimal with respect to the first optimal requested service listed in the ROUTE REQUEST message. The route server should resolve ties between otherwise equivalent routes by evaluating these routes according to the other optimal requested services contained in the ROUTE REQUEST message, in the order in which they are listed. With respect to the route server's routing information database, the selected route is optimal according to the first optimal requested service listed in the ROUTE REQUEST message but is not necessarily optimal according to any other optimal requested service listed in the ROUTE REQUEST message. ti 2 - To handle a mixture of requested service limits and optimal requested services, a route server should generate routes that satisfy all of the requested service limits. The route server should resolve ties between otherwise equivalent routes by evaluating these routes as described in the multi-criteria optimization case above. ti 2 - All else being equal, a route server should always prefer minimum-hop routes, because they minimize the amount of network resources consumed by the routes. ti 2 - A route server should generate at least one route to each component of a partitioned destination domain, because it may not know in which domain component the destination host resides. Hence, a route server can maximize the chances of providing a feasible route to a destination within a partitioned domain. 6.1 Searching All domains need not execute the identical route generation procedure. Each domain administrator is free to specify the IDPR route generation procedure for route servers in its own domain, making the procedure as simple or as complex as desired. Steenstrup [Page 74]
RFC 1479 IDPR Protocol July 1993 We offer an IDPR route generation procedure as a model. With slight modification, this procedure can be made to search in either BF or SPF order. The procedure can be used either to generate a single policy route from the source to a specified destination domain or to generate a set of policy routes from the source domain to all destination domains. If the source or destination domain has a proxy, then the source or destination endpoint of the policy route is a proxy domain and not the actual source or destination domain. For high-bandwidth traffic flows, BF search is the recommended search technique, because it produces minimum-hop routes. For low- bandwidth traffic flows, the route server may use either BF search or SPF search. The computational complexity of BF search is O(N + L) and hence it is the search procedure of choice, except when generating routes with optimal requested services. We recommend using SPF search only for optimal requested services and never in response to a request for a maximum bandwidth route. 6.1.1. Implementation Data Structures: The routing information database contains the graph of an internetwork, in which virtual gateways are the nodes and intra- domain routes between virtual gateways are the links. During route generation, each route is represented as a sequence of virtual gateways, domains, and relevant transit policies, together with a list of route characteristics, stored in a temporary array and indexed by destination domain. - Execute the Policy Consistency routine, first with the source domain the given domain and second with the destination domain as the given domain. If any policy inconsistency precludes the requested traffic flow, go to Exit. - For each domain, initialize a null route, set the route bandwidth to and set the following route characteristics to infinity: route delay, route delay variation, session monetary cost, and route length in hops. - With each operational virtual gateway in the source or source proxy domain, associate the initial route characteristics. - Initialize a next-node data structure which will contain, for each route in progress, the virtual gateway at the current endpoint of the route together with the associated route characteristics. The next-node data structure determines the order in which routes get expanded. Steenstrup [Page 75]
RFC 1479 IDPR Protocol July 1993 BF: A fifo queue. SPF: A heap, ordered according to the first optimal requested service listed in the ROUTE REQUEST message. Remove Next Node: These steps are performed for each virtual gateway in the next-node data structure. - If there are no more virtual gateways in the next-node data structure, go to Exit. - Extract a virtual gateway and its associated route characteristics from the next-node data structure, obtain the adjacent domain, and: SPF: Remake the heap. - If there is a specific destination domain and if for the primary optimal service: BF: Route length in hops. SPF: First optimal requested service listed in the ROUTE REQUEST message. the extracted virtual gateway's associated route characteristic is no better than that of the destination domain, go to Remove Next Node. - Execute the Policy Consistency routine with the adjacent domain as given domain. If any policy inconsistency precludes the requested traffic flow, go to Remove Next Node. - Check that the source domain's transit policies do not preclude traffic generated by members of the source host set with the specified user class and requested services, from flowing to the adjacent domain as destination. This check is necessary because the route server caches what it considers to be all feasible routes, to intermediate destination domains, generated during the computation of the requested route. If there are no policy inconsistencies, associate the route and its characteristics with the adjacent domain as destination. - If there is a specific destination domain and if the adjacent domain is the destination or destination proxy domain, go to Remove Next Node. - Record the set of all exit virtual gateways in the adjacent Steenstrup [Page 76]
RFC 1479 IDPR Protocol July 1993
RFC 1479 IDPR Protocol July 1993 UNUSED (8 bits) Not currently used; must be set equal to 0. NUM RQS (16 bits) Number of requested services. DST AD (16 bits) Numeric identifier for the destination domain, which may be different from the target domain if the target domain is a proxy for the destination. TGT ENT (16 bits) Numeric identifier for the target entity. A value of 0 indicates that there is no specific target entity. AD PTR (16 bits) Byte offset from the beginning of the message indicating the location of the beginning of the domain-specific information, contained in the right-most 15 bits. The left-most bit indicates whether the message includes expedited data (1 expedited data, 0 no expedited data). RQS TYP (16 bits) Numeric identifier for a type of requested service or source-specific information. Valid requested services are described in section 5.5.2. Valid source source-specific information includes the following types: 12. MD4/RSA data message authentication (see [16]). 13. MD5/RSA data message authentication (see [17]). 14. Billing address (variable). 15. Charge number (variable). RQS LEN (16 bits) Length of the requested service or source-specific information, in bytes, beginning with the next field. RQS SRV (variable) Description of the requested service or source- specific information. AD LEN (8 bits) Length of the information associated with a particular domain on the route, in bytes, beginning with the next field. VG (8 bits) Numeric identifier for an exit virtual gateway. ADJ AD (16 bits) Numeric identifier for an adjacent domain. ADJ CMP (16 bits) Numeric identifier for a component of the adjacent domain. Used to aid a policy gateway in routing across a virtual gateway connected to a partitioned domain. Steenstrup [Page 102]
RFC 1479 IDPR Protocol July 1993 NUM TP (16 bits) Number of transit policies that apply to the section of the path traversing the given domain component. TP (16 bits) Numeric identifier for a transit policy. 7.6.2. ACCEPT The ACCEPT message type is equal to 1. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PATH ID | | | +---------------+-----------------------------------------------+ | RSN TYP | REASON | +---------------+-----------------------------------------------+ PATH ID (64 bits) Path identifier contained in the original SETUP message. RSN TYP (optional, 8 bits) Numeric identifier for the reason for conditional path acceptance. REASON (optional, variable) Description of the reason for conditional path acceptance. Currently, no reasons have been defined. 7.6.3 REFUSE The REFUSE message type is equal to 2. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PATH ID | | | +---------------+-----------------------------------------------+ | RSN TYP | REASON | +---------------+-----------------------------------------------+ PATH ID (64 bits) Path identifier contained in the original SETUP message. RSN TYP (8 bits) Numeric identifier for the reason for path refusal. REASON (variable) Description of the reason for path refusal. Valid Steenstrup [Page 103]
RFC 1479 IDPR Protocol July 1993 reasons include the following types: 1. Transit policy does not apply between the virtual gateways in a given direction. Numeric identifier for the transit policy (16 bits). 2. Transit policy denies access to traffic from the host set between the source and destination domains. Numeric identifier for the transit policy (16 bits). 3. Transit policy denies access to traffic from the source user class. Numeric identifier for the transit policy (16 bits). 4. Transit policy denies access to traffic at the current time. Numeric identifier for the transit policy (16 bits). 5. Virtual gateway is down. Numeric identifier for the virtual gateway (8 bits) and associated adjacent domain (16 bits). 6. Virtual gateway is not reachable according to the given transit policy. Numeric identifier for the virtual gateway (8 bits), associated adjacent domain (16 bits), and transit policy (16 bits). 7. Domain component is not reachable. Numeric identifier for the domain (16 bits) and the component (16 bits). 8. Insufficient resources to establish the path. 9. Target is not reachable via intra-domain routing. 10. No existing path with the given path identifier, in response to a REPAIR message only. 7.6.4. TEARDOWN The TEARDOWN message type is equal to 3. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PATH ID | | | +---------------+-----------------------------------------------+ | RSN TYP | REASON | +---------------+-----------------------------------------------+ Steenstrup [Page 104]
RFC 1479 IDPR Protocol July 1993 PATH ID (64 bits) Path identifier contained in the original SETUP message. RSN TYP (8 bits) Numeric identifier for the reason for path teardown. REASON (variable) Description of the reason for path teardown. Valid reasons include the following types: 1. Virtual gateway is down. Numeric identifier for the virtual gateway (8 bits) and associated adjacent domain (16 bits). 2. Virtual gateway is not reachable according to the given transit policy. Numeric identifier for the virtual gateway (8 bits), associated adjacent domain (16 bits), and transit policy (16 bits). 3. Domain component is not reachable. Numeric identifier for the domain (16 bits) and the component (16 bits). 4. Maximum path lifetime exceeded. 5. Preempted path. 6. Unable to repair path. 7.6.5. ERROR The ERROR message type is equal to 4. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PATH ID | | | +---------------+---------------+-------------------------------+ | MSG | RSN TYP | REASON | +---------------+---------------+-------------------------------+ PATH ID (64 bits) Path identifier contained in the path control or data message in error. MSG (8 bits) Numeric identifier for the type of path control message in error. This field is ignored for error type 5. RSN TYP (8 bits) Numeric identifier for the reason for the PCP message error. Steenstrup [Page 105]
RFC 1479 IDPR Protocol July 1993 REASON (variable) Description of the reason for the PCP message error. Valid reasons include the following types: 1. Path identifier is already currently active. 2. Domain does not appear in the SETUP message. 3. Transit policy is not configured for the domain. Numeric identifer for the transit policy (16 bits). 4. Virtual gateway not configured for the domain. Numeric identifier for the virtual gateway (8 bits) and associated adjacent domain (16 bits). 5. Unrecognized path identifier in an IDPR data message. 7.6.6. REPAIR The REPAIR message type is equal to 5. A REPAIR message contains the original SETUP message only. 7.6.7. Negative Acknowledgements When a policy gateway receives an unacceptable PCP message that passes the CMTP validation checks, it includes, in its CMTP ACK, an appropriate negative acknowledgement. This information is placed in the INFORM field of the CMTP ACK (described previously in section 2.4); the numeric identifier for each type of PCP negative acknowledgement is contained in the left-most 8 bits of the INFORM field. Negative acknowledgements associated with PCP include the following types: 1. Unrecognized PCP message type. Numeric identifier for the unrecognized message type (8 bits). 2. Out-of-date PCP message. 3. Unrecognized path identifier (for all PCP messages except SETUP). Numeric identifier for the unrecognized path (64 bits). 8. Security Considerations Refer to sections 1.6, 1.7, and 2.3 for details on security in IDPR. Steenstrup [Page 106]
RFC 1479 IDPR Protocol July 1993 9. Author's Address Martha Steenstrup BBN Systems and Technologies 10 Moulton Street Cambridge, MA 02138 Phone: (617) 873-3192 Email: msteenst@bbn.com References [1] Clark, D., "Policy Routing in Internet Protocols", RFC 1102, May 1989 [2] Estrin, D., "Requirements for Policy Based Routing in the Research Internet", RFC 1125, November 1989. [3] Little, M., "Goals and Functional Requirements for Inter- Autonomous System Routing", RFC 1126, July 1989. [4] Breslau, L. and Estrin, D., "Design of Inter-Administrative Domain Routing Protocols", Proceedings of the ACM SIGCOMM '90 Symposium, September 1990. [5] Steenstrup, M., "An Architecture for Inter-Domain Policy Rout- ing", RFC 1478, July 1993. [6] Austein, R., "DNS Support for IDPR", Work in Progress, March 1993 [7] Bowns, H. and Steenstrup, M., "Inter-Domain Policy Routing Con- figuration and Usage", Work in Progress, July 1991. [8] Woodburn, R., "Definitions of Managed Objects for Inter-Domain Policy Routing (Version 1)", Work in Progress, March 1993. [9] McQuillan, J., Richer, I., Rosen, E., and Bertsekas, D., "ARPANET Routing Algorithm Improvements: Second Semiannual Technical Report", BBN Report No. 3940, October 1978. [10] Moy, J., "The OSPF Specification", RFC 1131, October 1989. [11] Oran, D. (editor), "Intermediate System to Intermediate System Routeing Exchange Protocol for Use in Conjunction with the Pro- tocol for Providing the Connectionless-mode Network Service (ISO 8473)", ISO/IEC JTC1/SC6/WG2, October 1989. Steenstrup [Page 107]
RFC 1479 IDPR Protocol July 1993 [12] Estrin, D., and Tsudik, G., "Secure Control of Transit Internet- work Traffic, TR-89-15, Computer Science Department, University of Southern California. [13] Linn, J., "Privacy Enhancement for Internet Electronic Mail: Part I - Message Encipherment and Authentication Procedures", RFC 1113, August 1989. [14] Kent, S., and Linn, J., "Privacy Enhancement for Internet Elec- tronic Mail: Part II - Certificate-based Key Management", RFC 1114, August 1989. [15] Linn, J., "Privacy Enhancement for Internet Electronic Mail: Part III - Algorithms, Modes, and Identifiers", RFC 1115, August 1989 [16] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320, April 1992 [17] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992



Back to RFC index

 

 



Sponsered-Sites:

Register domain name and transfer | Cheap webhosting service | Domain name registration

 

 

""