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

   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

   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

   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-

   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.

   -   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

   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

      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.

   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

   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

   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:

    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

   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.

   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;

       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.

   - 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.

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.

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.