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

         Inter-Domain Policy Routing Protocol Specification: Version 1

    Status of this Memo

       This RFC specifies an IAB standards track protocol for the Internet
       community, and requests discussion and suggestions for improvements.
       Please refer to the current edition of the "IAB Official Protocol
       Standards" for the standardization state and status of this protocol.
       Distribution of this memo is unlimited.

    Abstract

       We present the set of protocols and procedures that constitute
       Inter-Domain Policy Routing (IDPR).  IDPR includes the virtual
       gateway protocol, the flooding protocol, the route server query
       protocol, the route generation procedure, the path control protocol,
       and the data message forwarding procedure.

    Contributors

       The following people have contributed to the protocols and procedures
       described in this document: Helen Bowns, Lee Breslau, Ken Carlberg,
       Isidro Castineyra, Deborah Estrin, Tony Li, Mike Little, Katia
       Obraczka, Sam Resheff, Martha Steenstrup, Gene Tsudik, and Robert
       Woodburn.

    Table of Contents

       1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3
       1.1. Domain Elements . . . . . . . . . . . . . . . . . . . . . . . 3
       1.2. Policy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
       1.3. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . . 5
       1.3.1. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . 6
       1.4. Policy Semantics. . . . . . . . . . . . . . . . . . . . . . . 7
       1.4.1. Source Policies . . . . . . . . . . . . . . . . . . . . . . 7
       1.4.2. Transit Policies. . . . . . . . . . . . . . . . . . . . . . 8
       1.5. IDPR Message Encapsulation. . . . . . . . . . . . . . . . . . 9
       1.5.1. IDPR Data Message Format. . . . . . . . . . . . . . . . . .11
       1.6. Security. . . . . . . . . . . . . . . . . . . . . . . . . . .12
       1.7. Timestamps and Clock Synchronization. . . . . . . . . . . . .13
       1.8. Network Management. . . . . . . . . . . . . . . . . . . . . .14
       1.8.1. Policy Gateway Configuration. . . . . . . . . . . . . . . .17
       1.8.2. Route Server Configuration. . . . . . . . . . . . . . . . .18

    Steenstrup                                                      [Page 1]

    RFC 1479                     IDPR Protocol                     July 1993

       2. Control Message Transport Protocol. . . . . . . . . . . . . . .18
       2.1. Message Transmission. . . . . . . . . . . . . . . . . . . . .20
       2.2. Message Reception . . . . . . . . . . . . . . . . . . . . . .22
       2.3. Message Validation. . . . . . . . . . . . . . . . . . . . . .23
       2.4. CMTP Message Formats. . . . . . . . . . . . . . . . . . . . .24
       3. Virtual Gateway Protocol. . . . . . . . . . . . . . . . . . . .27
       3.1. Message Scope . . . . . . . . . . . . . . . . . . . . . . . .28
       3.1.1. Pair-PG Messages. . . . . . . . . . . . . . . . . . . . . .28
       3.1.2. Intra-VG Messages . . . . . . . . . . . . . . . . . . . . .29
       3.1.3. Inter-VG Messages . . . . . . . . . . . . . . . . . . . . .29
       3.1.4. VG Representatives. . . . . . . . . . . . . . . . . . . . .31
       3.2. Up/Down Protocol. . . . . . . . . . . . . . . . . . . . . . .31
       3.3. Implementation. . . . . . . . . . . . . . . . . . . . . . . .33
       3.4. Policy Gateway Connectivity . . . . . . . . . . . . . . . . .35
       3.4.1. Within a Virtual Gateway. . . . . . . . . . . . . . . . . .35
       3.4.2. Between Virtual Gateways. . . . . . . . . . . . . . . . . .37
       3.4.3. Communication Complexity. . . . . . . . . . . . . . . . . .40
       3.5. VGP Message Formats . . . . . . . . . . . . . . . . . . . . .41
       3.5.1. UP/DOWN . . . . . . . . . . . . . . . . . . . . . . . . . .41
       3.5.2. PG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .42
       3.5.3. PG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .43
       3.5.4. VG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .44
       3.5.5. VG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .45
       3.5.6. Negative Acknowledgements . . . . . . . . . . . . . . . . .46
       4. Routing Information Distribution. . . . . . . . . . . . . . . .47
       4.1. AD Representatives. . . . . . . . . . . . . . . . . . . . . .48
       4.2. Flooding Protocol . . . . . . . . . . . . . . . . . . . . . .48
       4.2.1. Message Generation. . . . . . . . . . . . . . . . . . . . .50
       4.2.2. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . .52
       4.2.3. Message Acceptance. . . . . . . . . . . . . . . . . . . . .52
       4.2.4. Message Incorporation . . . . . . . . . . . . . . . . . . .54
       4.2.5. Routing Information Database. . . . . . . . . . . . . . . .56
       4.3. Routing Information Message Formats . . . . . . . . . . . . .57
       4.3.1. CONFIGURATION . . . . . . . . . . . . . . . . . . . . . . .57
       4.3.2. DYNAMIC . . . . . . . . . . . . . . . . . . . . . . . . . .62
       4.3.3. Negative Acknowledgements . . . . . . . . . . . . . . . . .63
       5. Route Server Query Protocol . . . . . . . . . . . . . . . . . .64
       5.1. Message Exchange. . . . . . . . . . . . . . . . . . . . . . .64
       5.2. Remote Route Server Communication . . . . . . . . . . . . . .65
       5.3. Routing Information . . . . . . . . . . . . . . . . . . . . .66
       5.4. Routes. . . . . . . . . . . . . . . . . . . . . . . . . . . .67
       5.5. Route Server Message Formats. . . . . . . . . . . . . . . . .67
       5.5.1. ROUTING INFORMATION REQUEST . . . . . . . . . . . . . . . .67
       5.5.2. ROUTE REQUEST . . . . . . . . . . . . . . . . . . . . . . .68
       5.5.3. ROUTE RESPONSE. . . . . . . . . . . . . . . . . . . . . . .71
       5.5.4. Negative Acknowledgements . . . . . . . . . . . . . . . . .72
       6. Route Generation. . . . . . . . . . . . . . . . . . . . . . . .73
       6.1. Searching . . . . . . . . . . . . . . . . . . . . . . . . . .74

    Steenstrup                                                      [Page 2]

    RFC 1479                     IDPR Protocol                     July 1993

       6.1.1. Implementation. . . . . . . . . . . . . . . . . . . . . . .75
       6.2. Route Directionality. . . . . . . . . . . . . . . . . . . . .78
       6.3. Route Database. . . . . . . . . . . . . . . . . . . . . . . .79
       6.3.1. Cache Maintenance . . . . . . . . . . . . . . . . . . . . .80
       7. Path Control Protocol and Data Message Forwarding Procedure . .80
       7.1. An Example of Path Setup. . . . . . . . . . . . . . . . . . .81
       7.2. Path Identifiers. . . . . . . . . . . . . . . . . . . . . . .84
       7.3. Path Control Messages . . . . . . . . . . . . . . . . . . . .85
       7.4. Setting Up and Tearing Down a Path. . . . . . . . . . . . . .87
       7.4.1. Validating Path Identifiers . . . . . . . . . . . . . . . .89
       7.4.2. Path Consistency with Configured Transit Policies . . . . .89
       7.4.3. Path Consistency with Virtual Gateway Reachability. . . . .91
       7.4.4. Obtaining Resources . . . . . . . . . . . . . . . . . . . .92
       7.4.5. Target Response . . . . . . . . . . . . . . . . . . . . . .93
       7.4.6. Originator Response . . . . . . . . . . . . . . . . . . . .93
       7.4.7. Path Life . . . . . . . . . . . . . . . . . . . . . . . .  94
       7.5. Path Failure and Recovery . . . . . . . . . . . . . . . . .  95
       7.5.1. Handling Implicit Path Failures . . . . . . . . . . . . .  96
       7.5.2. Local Path Repair . . . . . . . . . . . . . . . . . . . .  97
       7.5.3. Repairing a Path. . . . . . . . . . . . . . . . . . . . .  98
       7.6. Path Control Message Formats. . . . . . . . . . . . . . . . 100
       7.6.1. SETUP . . . . . . . . . . . . . . . . . . . . . . . . . . 101
       7.6.2. ACCEPT. . . . . . . . . . . . . . . . . . . . . . . . . . 103
       7.6.3. REFUSE. . . . . . . . . . . . . . . . . . . . . . . . . . 103
       7.6.4. TEARDOWN. . . . . . . . . . . . . . . . . . . . . . . . . 104
       7.6.5. ERROR . . . . . . . . . . . . . . . . . . . . . . . . . . 105
       7.6.6. REPAIR. . . . . . . . . . . . . . . . . . . . . . . . . . 106
       7.6.7. Negative Acknowledgements . . . . . . . . . . . . . . . . 106
       8. Security Considerations . . . . . . . . . . . . . . . . . . . 106
       9. Authors's Address . . . . . . . . . . . . . . . . . . . . . . 107
       References . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

    1.  Introduction

       In this document, we specify the protocols and procedures that
       compose Inter-Domain Policy Routing (IDPR).  The objective of IDPR is
       to construct and maintain routes between source and destination
       administrative domains, that provide user traffic with the services
       requested within the constraints stipulated for the domains
       transited.  IDPR supports link state routing information distribution
       and route generation in conjunction with source specified message
       forwarding.  Refer to [5] for a detailed justification of our
       approach to inter-domain policy routing.

    1.1.  Domain Elements

       The IDPR architecture has been designed to accommodate an
       internetwork with tens of thousands of administrative domains

    Steenstrup                                                      [Page 3]

    RFC 1479                     IDPR Protocol                     July 1993

       collectively containing hundreds of thousands of local networks.
       Inter-domain policy routes are constructed using information about
       the services offered by, and the connectivity between, administrative
       domains.  The intra-domain details - gateways, networks, and links
       traversed - of an inter-domain policy route are the responsibility of
       intra-domain routing and are thus outside the scope of IDPR.

       An "administrative domain" (AD) is a collection of contiguous hosts,
       gateways, networks, and links managed by a single administrative
       authority.  The domain administrator defines service restrictions for
       transit traffic and service requirements for locally-generated
       traffic, and selects the addressing schemes and routing procedures
       that apply within the domain.  Within the Internet, each domain has a
       unique numeric identifier assigned by the Internet Assigned Numbers
       Authority (IANA).

       "Virtual gateways" (VGs) are the only IDPR-recognized connecting
       points between adjacent domains.  Each virtual gateway is a
       collection of directly-connected "policy gateways" (see below) in two
       adjoining domains, whose existence has been sanctioned by the
       administrators of both domains.  The domain administrators may agree
       to establish more than one virtual gateway between the two domains.
       For each such virtual gateway, the two administrators together assign
       a local numeric identifier, unique within the set of virtual gateways
       connecting the two domains.  To produce a virtual gateway identifier
       unique within its domain, a domain administrator concatenates the
       mutually assigned local virtual gateway identifier together with the
       adjacent domain's identifier.

       Policy gateways (PGs) are the physical gateways within a virtual
       gateway.  Each policy gateway enforces service restrictions on IDPR
       transit traffic, as stipulated by the domain administrator, and
       forwards the traffic accordingly.  Within a domain, two policy
       gateways are "neighbors" if they are in different virtual gateways.
       A single policy gateway may belong to multiple virtual gateways.
       Within a virtual gateway, two policy gateways are "peers" if they are
       in the same domain and are "adjacent" if they are in different
       domains.  Adjacent policy gateways are "directly connected" if the
       only Internet-addressable entities attached to the connecting medium
       are policy gateways in the virtual gateways.  Note that this
       definition implies that not only point-to-point links but also
       networks may serve as direct connections between adjacent policy
       gateways.  The domain administrator assigns to each of its policy
       gateways a numeric identifier, unique within that domain.

       A "domain component" is a subset of a domain's entities such that all
       entities within the subset are mutually reachable via intra-domain
       routes, but no entities outside the subset are reachable via intra-

    Steenstrup                                                      [Page 4]

    RFC 1479                     IDPR Protocol                     July 1993

       domain routes from entities within the subset.  Normally, a domain
       consists of a single component, namely itself; however, when
       partitioned, a domain consists of multiple components.  Each domain
       component has an identifier, unique within the Internet, composed of
       the domain identifier together with the identifier of the lowest-
       numbered operational policy gateway within the component.  All
       operational policy gateways within a domain component can discover
       mutual reachability through intra-domain routing information.  Hence,
       all such policy gateways can consistently determine, without explicit
       negotiation, which of them has the lowest number.

    1.2.  Policy

       With IDPR, each domain administrator sets "transit policies" that
       dictate how and by whom the resources in its domain should be used.
       Transit policies are usually public, and they specify offered
       services comprising:

       -   Access restrictions: e.g., applied to traffic to or from certain
           domains or classes of users.

       -   Quality: e.g., delay, throughput, or error characteristics.

       -   Monetary cost: e.g., charge per byte, message, or unit time.

       Each domain administrator also sets "source policies" for traffic
       originating in its domain.  Source policies are usually private, and
       they specify requested services comprising:

       -   Access restrictions: e.g., domains to favor or avoid in routes.

       -   Quality: e.g., acceptable delay, throughput, and reliability.

       -   Monetary cost: e.g., acceptable session cost.

    1.3.  IDPR Functions

       IDPR comprises the following functions:

       -   Collecting and distributing routing information including domain
           transit policies and inter-domain connectivity.

       -   Generating and selecting policy routes based on the routing
           information distributed and on the source policies configured or
           requested.

       -   Setting up paths across the Internet using the policy routes
           generated.

    Steenstrup                                                      [Page 5]

    RFC 1479                     IDPR Protocol                     July 1993

       -   Forwarding messages across and between domains along the
           established paths.

       -   Maintaining databases of routing information, inter-domain policy
           routes, forwarding information, and configuration information.

    1.3.1.  IDPR Entities

       Several different entities are responsible for performing the IDPR
       functions.

       Policy gateways, the only IDPR-recognized connecting points between
       adjacent domains, collect and distribute routing information,
       participate in path setup, forward data messages along established
       paths, and maintain forwarding information databases.

       "Path agents", resident within policy gateways and within "route
       servers" (see below), act on behalf of hosts to select policy routes,
       to set up and manage paths, and to maintain forwarding information
       databases.  Any Internet host can reap the benefits of IDPR, as long
       as there exists a path agent configured to act on its behalf and a
       means by which the host's messages can reach the path agent.
       Specifically, a path agent in one domain may be configured to act on
       behalf of hosts in another domain.  In this case, the path agent's
       domain is an IDPR "proxy" for the hosts' domain.

       Route servers maintain both the routing information database and the
       route database, and they generate policy routes using the routing
       information collected and the source policies requested by the path
       agents.  A route server may reside within a policy gateway, or it may
       exist as an autonomous entity.  Separating the route server functions
       from the policy gateways frees the policy gateways from both the
       memory intensive task of database (routing information and route)
       maintenance and the computationally intensive task of route
       generation.  Route servers, like policy gateways, each have a unique
       numeric identifier within their domain, assigned by the domain
       administrator.

       Given the size of the current Internet, each policy gateway can
       perform the route server functions, in addition to its message
       forwarding functions, with little or no degradation in message
       forwarding performance.  Aggregating the routing functions into
       policy gateways simplifies implementation; one need only install IDPR
       protocols in policy gateways.  Moreover, it simplifies communication
       between routing functions, as all functions reside within each policy
       gateway.  As the Internet grows, the memory and processing required
       to perform the route server functions may become a burden for the
       policy gateways.  When this happens, each domain administrator should

    Steenstrup                                                      [Page 6]

    RFC 1479                     IDPR Protocol                     July 1993

       separate the route server functions from the policy gateways in its
       domain.

       "Mapping servers" maintain the database of mappings that resolve
       Internet names and addresses to domain identifiers.  Each host is
       contained within a domain and is associated with a proxy domain which
       may be identical with the host's domain.  The mapping server function
       will be integrated into the existing DNS name service (see [6]) and
       will provide mappings between a host and its local and proxy domains.

       "Configuration servers" maintain the databases of configured
       information that apply to IDPR entities within their domains.
       Configuration information for a given domain includes transit
       policies (i.e., service offerings and restrictions), source policies
       (i.e., service requirements), and mappings between local IDPR
       entities and their names and addresses.  The configuration server
       function will be integrated into a domain's existing network
       management system (see [7]-[8]).

    1.4.  Policy Semantics

       The source and transit policies supported by IDPR are intended to
       accommodate a wide range of services available throughout the
       Internet.  We describe the semantics of these policies, concentrating
       on the access restriction aspects.  To express these policies in this
       document, we have chosen to use a syntactic variant of Clark's policy
       term notation [1].  However, we provide a more succinct syntax (see
       [7]) for actually configuring source and transit policies.

    1.4.1.  Source Policies

       Each source policy takes the form of a collection of sets as follows:

       Applicable Sources and Destinations:
          {((H(1,1),s(1,1)),...,(H(1,f1),s(1,f1))),...,((H(n,1),s(n,1)),...,
          (H(n,fn),s(n,fn)))}: The set of groups of source/destination
          traffic flows to which the source policy applies.  Each traffic
          flow group ((H(i,1),s(i,1)),...,(H(i,fi),s(i,fi))) contains a set
          of source hosts and corresponding destination hosts.  Here, H(i,j)
          represents a host, and s(i,j), an element of {SOURCE,
          DESTINATION}, represents an indicator of whether H(i,j) is to be
          considered as a source or as a destination.

       Domain Preferences: {(AD(1),x(1)),...,(AD(m),x(m))}: The set of
          transit domains that the traffic flows should favor, avoid, or
          exclude.  Here, AD(i) represents a domain, and x(i), an element of
          {FAVOR, AVOID, EXCLUDE}, represents an indicator of whether routes
          including AD(i) are to be favored, avoided if possible, or

    Steenstrup                                                      [Page 7]

    RFC 1479                     IDPR Protocol                     July 1993

          unconditionally excluded.

       UCI: The source user class for the traffic flows listed.

       RequestedServices: The set of requested services not related to
          access restrictions, i.e., service quality and monetary cost.

       When selecting a route for a traffic flow from a source host H(i,j)
       to a destination host H(i,k), where 1 < or = i < or = n and 1 < or =
       j, k < or = fi, the path agent (see section 1.3.1) must honor the
       source policy such that:

       - For each domain, AD(p), contained in the route, AD(p) is not equal
         to any AD(k), such that 1 < or = k < or = m and x(k) = EXCLUDE.

       - The route provides the services listed in the set Requested
         Services.

    1.4.2.  Transit Policies

       Each transit policy takes the form of a collection of sets as
       follows:

       Source/Destination Access Restrictions:
          {((H(1,1),AD(1,1),s(1,1)),...,(H(1,f1),AD(1,f1),s(1,f1))),...,
          ((H(n,1),AD(n,1),s(n,1)),...,(H(n,fn),AD(n,fn),s(n,fn)))}: The set
          of groups of source and destination hosts and domains to which the
          transit policy applies.  Each domain group
          ((H(i,1),AD(i,1),s(i,1)),...,(H(i,fi),AD(i,fi),s(i,fi))) contains
          a set of source and destination hosts and domains such that this
          transit domain will carry traffic from each source listed to each
          destination listed.  Here, H(i,j) represents a set of hosts,
          AD(i,j) represents a domain containing H(i,j), and s(i,j), a
          subset of {SOURCE, DESTINATION}, represents an indicator of
          whether (H(i,j),AD(i,j)) is to be considered as a set of sources,
          destinations, or both.

       Temporal Access Restrictions: The set of time intervals during which
          the transit policy applies.

       User Class Access Restrictions: The set of user classes to which the
          transit policy applies.

       Offered Services: The set of offered services not related to access
          restrictions, i.e., service quality and monetary cost.

    Steenstrup                                                      [Page 8]

    RFC 1479                     IDPR Protocol                     July 1993

       Virtual Gateway Access Restrictions:
          {((VG(1,1),e(1,1)),...,(VG(1,g1),e(1,g1))),...,((VG(m,1),e(m,1)),
          gateways to which the transit policy applies.  Each virtual
          gateway group ((VG(i,1),e(i,1)),...,(VG(i,gi),e(i,gi))) contains a
          set of domain entry and exit points such that each entry virtual
          gateway can reach (barring an intra-domain routing failure) each
          exit virtual gateway via an intra-domain route supporting the
          transit policy.  Here, VG(i,j) represents a virtual gateway, and
          e(i,j), a subset of {ENTRY, EXIT}, represents an indicator of
          whether VG(i,j) is to be considered as a domain entry point, exit
          point, or both.

       The domain advertising such a transit policy will carry traffic from
       any host in the set H(i,j) in AD(i,j) to any host in the set H(i,k)
       in AD(i,k), where 1 < or = i < or = n and 1 < or = j, k < or = fi,
       provided that:

       - SOURCE is an element of s(i,j).

       - DESTINATION is an element of s(i,k).

       - Traffic from H(i,j) enters the domain during one of the intervals
         in the set Temporal Access Restrictions.

       - Traffic from H(i,j) carries one of the user class identifiers in
         the set User Class Access Restrictions.

       - Traffic from H(i,j) enters via any VG(u,v) such that ENTRY is an
         element of e(u,v), where 1 < or = u < or = m and 1 < or = v < or =
         gu.

       - Traffic to H(i,k) leaves via any VG(u,w) such that EXIT is an
         element of e(u,w), where 1 < or = w < or = gu.

    1.5.  IDPR Message Encapsulation

       There are two kinds of IDPR messages:

       - "Data messages" containing user data generated by hosts.

       - "Control messages" containing IDPR protocol-related control
         information generated by policy gateways and route servers.

       Within an internetwork, only policy gateways and route servers are
       able to generate, recognize, and process IDPR messages.  The
       existence of IDPR is invisible to all other gateways and hosts,
       including mapping servers and configuration servers.  Mapping servers
       and configuration servers perform necessary but ancillary functions

    Steenstrup                                                      [Page 9]

    RFC 1479                     IDPR Protocol                     July 1993

       for IDPR, and thus they are not required to handle IDPR messages.

       An IDPR entity places IDPR-specific information in each IDPR control
       message it originates; this information is significant only to
       recipient IDPR entities.  Using "encapsulation" across each domain,
       an IDPR message tunnels from source to destination across an
       internetwork through domains that may employ disparate intra-domain
       addressing schemes and routing procedures.

       As an alternative to encapsulation, we had considered embedding IDPR
       in IP, as a set of IP options.  However, this approach has the
       following disadvantages:

       - Only domains that support IP would be able to participate in IDPR;
         domains that do not support IP would be excluded.

       - Each gateway, policy or other, in a participating domain would at
         least have to recognize the IDPR option, even if it did not execute
         the IDPR protocols.  However, most commercial routers are not
         optimized for IP options processing, and so IDPR message handling
         might require significant processing at each gateway.

       - For some IDPR protocols, in particular path control, the size
         restrictions on IP options would preclude inclusion of all of the
         necessary protocol-related information.

       For these reasons, we decided against the IP option approach and in
       favor of encapsulation.

       An IDPR message travels from source to destination between
       consecutive policy gateways.  Each policy gateway encapsulates the
       IDPR message with information, for example an IP header, that will
       enable the message to reach the next policy gateway.  Note that the
       encapsulating header and the IDPR-specific information may increase
       the message size beyond the MTU of the given domain.  However,
       message fragmentation and reassembly is the responsibility of the
       protocol, for example IP, that encapsulates IDPR messages for
       transport between successive policy gateways; it is not currently the
       responsibility of IDPR itself.

       A policy gateway, when forwarding an IDPR message to a peer or a
       neighbor policy gateway, encapsulates the message in accordance with
       the addressing scheme and routing procedure of the given domain and
       indicates in the protocol field of the encapsulating header that the
       message is indeed an IDPR message.  Intermediate gateways between the
       two policy gateways forward the IDPR message as they would any other
       message, using the information in the encapsulating header.  Only the
       recipient policy gateway interprets the protocol field, strips off

    Steenstrup                                                     [Page 10]

    RFC 1479                     IDPR Protocol                     July 1993

       the encapsulating header, and processes the IDPR message.

       A policy gateway, when forwarding an IDPR message to a directly-
       connected adjacent policy gateway, encapsulates the message in
       accordance with the addressing scheme of the entities within the
       virtual gateway and indicates in the protocol field of the
       encapsulating header that the message is indeed an IDPR message.  The
       recipient policy gateway strips off the encapsulating header and
       processes the IDPR message.  We recommend that the recipient policy
       gateway perform the following validation check of the encapsulating
       header, prior to stripping it off.  Specifically, the recipient
       policy gateway should verify that the source address and the
       destination address in the encapsulating header match the adjacent
       policy gateway's address and its own address, respectively.
       Moreover, the recipient policy gateway should verify that the message
       arrived on the interface designated for the direct connection to the
       adjacent policy gateway.  These checks help to ensure that IDPR
       traffic that crosses domain boundaries does so only over direct
       connections between adjacent policy gateways.

       Policy gateways forward IDPR data messages according to a forwarding
       information database which maps "path identifiers", carried in the
       data messages, into next policy gateways.  Policy gateways forward
       IDPR control messages according to next policy gateways selected by
       the particular IDPR control protocols associated with the messages.
       Distinguishing IDPR data messages and IDPR control messages at the
       encapsulating protocol level, instead of at the IDPR protocol level,
       eliminates an extra level of dispatching and hence makes IDPR message
       forwarding more efficient.  When encapsulated within IP messages,
       IDPR data messages and IDPR control messages carry the IP protocol
       numbers 35 and 38, respectively.

    1.5.1.  IDPR Data Message Format

       The path agents at a source domain determine which data messages
       generated by local hosts are to be handled by IDPR.  To each data
       message selected for IDPR handling, a source path agent prepends the
       following header:

    Steenstrup                                                     [Page 11]

    RFC 1479                     IDPR Protocol                     July 1993

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    VERSION    |     PROTO     |            LENGTH             |
       +---------------+---------------+-------------------------------+
       |                            PATH ID                            |
       |                                                               |
       +---------------------------------------------------------------+
       |                           TIMESTAMP                           |
       +---------------------------------------------------------------+
       |                            INT/AUTH                           |
       |                                                               |
       +---------------------------------------------------------------+

       VERSION (8 bits) Version number for IDPR data messages, currently
       equal to 1.

       PROTO (8 bits) Numeric identifier for the protocol with which to
       process the contents of the IDPR data message.  Only the path agent
       at the destination interprets and acts upon the contents of the PROTO
       field.

       LENGTH (16 bits) Length of the entire IDPR data message in bytes.

       PATH ID (64 bits) Path identifier assigned by the source's path agent
       and consisting of the numeric identifier for the path agent's domain
       (16 bits), the numeric identifier for the path agent's policy gateway
       (16 bits), and the path agent's local path identifier (32 bits) (see
       section 7.2).

       TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970
       0:00 GMT.

       INT/AUTH (variable) Computed integrity/authentication value,
       dependent on the type of integrity/authentication requested during
       path setup.

       We describe the IDPR control message header in section 2.4.

    1.6.  Security

       IDPR contains mechanisms for verifying message integrity and source
       authenticity and for protecting against certain types of denial of
       service attacks.  It is particularly important to keep IDPR control
       messages intact, because they carry control information critical to
       the construction and use of viable policy routes between domains.

       All IDPR messages carry a single piece of information, referred to as

    Steenstrup                                                     [Page 12]

    RFC 1479                     IDPR Protocol                     July 1993

       the "integrity/authentication value", which may be used not only to
       detect message corruption but also to verify the authenticity of the
       message source.  In the Internet, the IANA will sanction the set of
       valid algorithms which may be used to compute the
       integrity/authentication values.  This set may include algorithms
       that perform only message integrity checks such as n-bit cyclic
       redundancy checksums (CRCs), as well as algorithms that perform both
       message integrity and source authentication checks such as signed
       hash functions of message contents.

       Each domain administrator is free to select any
       integrity/authentication algorithm, from the set specified by the
       IANA, for computing the integrity/authentication values contained in
       its domain's messages.  However, we recommend that IDPR entities in
       each domain be capable of executing all of the valid algorithms so
       that an IDPR control message originating at an entity in one domain
       can be properly checked by an entity in another domain.

       Each IDPR control message must carry a non-null
       integrity/authentication value.  We recommend that control message
       integrity/authentication be based on a digital signature algorithm
       applied to a one-way hash function, such as RSA applied to MD5 [17],
       which simultaneously verifies message integrity and source
       authenticity.  The digital signature may be based on either public-
       key or private-key cryptography.  Our approach to digital signature
       use in IDPR is based on the privacy-enhanced Internet electronic mail
       service [13]-[15], already available in the Internet.

       We do not require that IDPR data messages carry a non-null
       integrity/authentication value.  In fact, we recommend that a higher
       layer (end-to-end) procedure, and not IDPR, assume responsibility for
       checking the integrity and authenticity of data messages, because of
       the amount of computation involved.

    1.7.  Timestamps and Clock Synchronization

       Each IDPR message carries a timestamp (expressed in seconds elapsed
       since 1 January 1970 0:00 GMT, following the UNIX precedent) supplied
       by the source IDPR entity, which serves to indicate the age of the
       message.  IDPR entities use the absolute value of the timestamp to
       confirm that a message is current and use the relative difference
       between timestamps to determine which message contains the more
       recent information.

       All IDPR entities must possess internal clocks that are synchronized
       to some degree, in order for the absolute value of a message
       timestamp to be meaningful.  The synchronization granularity required
       by IDPR is on the order of minutes and can be achieved manually.

    Steenstrup                                                     [Page 13]

    RFC 1479                     IDPR Protocol                     July 1993

       Thus, a clock synchronization protocol operating among all IDPR
       entities in all domains, while useful, is not necessary.

       An IDPR entity can determine whether to accept or reject a message
       based on the discrepancy between the message's timestamp and the
       entity's own internal clock time.  Any IDPR message whose timestamp
       lies outside of the acceptable range may contain stale or corrupted
       information or may have been issued by a source whose internal clock
       has lost synchronization with the message recipient's internal clock.
       Timestamp checks are required for control messages because of the
       consequences of propagating and acting upon incorrect control
       information.  However, timestamp checks are discretionary for data
       messages but may be invoked during problem diagnosis, for example,
       when checking for suspected message replays.

       We note that none of the IDPR protocols contain explicit provisions
       for dealing with an exhausted timestamp space.  As timestamp space
       exhaustion will not occur until well into the next century, we expect
       timestamp space viability to outlast the IDPR protocols.

    1.8.  Network Management

       In this document, we do not describe how to configure and manage
       IDPR.  However, in this section, we do provide a list of the types of
       IDPR configuration information required.  Also, in later sections
       describing the IDPR protocols, we briefly note the types of
       exceptional events that must be logged for network management.
       Complete descriptions of IDPR entity configuration and IDPR managed
       objects appear in [7] and [8] respectively.

       To participate in inter-domain policy routing, policy gateways and
       route servers within a domain each require configuration information.
       Some of the configuration information is specifically defined within
       the given domain, while some of the configuration information is
       universally defined throughout an internetwork.  A domain
       administrator determines domain-specific information, and in the
       Internet, the IANA determines globally significant information.

       To produce valid domain configurations, the domain administrators
       must receive the following global information from the IANA:

       - For each integrity/authentication type, the numeric
         identifier, syntax, and semantics.  Available integrity and
         authentication types include but are not limited to:

           o    public-key based signatures;

           o    private-key based signatures;

    Steenstrup                                                     [Page 14]

    RFC 1479                     IDPR Protocol                     July 1993

           o    cyclic redundancy checksums;

           o    no integrity/authentication.

       - For each user class, the numeric identifier, syntax, and
         semantics.  Available user classes include but are not limited to:

           o    federal (and if necessary, agency-specific such as NSF, DOD,
                DOE, etc.);

           o    research;

           o    commercial;

           o    support.

       - For each offered service that may be advertised in transit
         policies, the numeric identifier, syntax, and semantics.  Available
         offered services include but are not limited to:

           o    average message delay;

           o    message delay variation;

           o    average bandwidth available;

           o    available bandwidth variation;

           o    maximum transfer unit (MTU);

           o    charge per byte;

           o    charge per message;

           o    charge per unit time.

       - For each access restriction that may be advertised in transit
         policies, the numeric identifier, syntax, and semantics.  Available
         access restrictions include but are not limited to:

           o    Source and destination domains and host sets.

           o    User classes.

           o    Entry and exit virtual gateways.

           o    Time of day.

    Steenstrup                                                     [Page 15]

    RFC 1479                     IDPR Protocol                     July 1993

       - For each requested service that may appear within a path setup
         message, the numeric identifier, syntax, and semantics.  Available
         requested services include but are not limited to:

           o    maximum path life in minutes, messages, or bytes;

           o    integrity/authentication algorithms to be used on data
                messages sent over the path;

           o    upper bound on path delay;

           o    minimum delay path;

           o    upper bound on path delay variation;

           o    minimum delay variation path;

           o    lower bound on path bandwidth;

           o    maximum bandwidth path;

           o    upper bound on monetary cost;

           o    minimum monetary cost path.

       In an internetwork-wide implementation of IDPR, the set of global
       configuration parameters and their syntax and semantics must be
       consistent across all participating domains.  The IANA, responsible
       for establishing the full set of global configuration parameters in
       the Internet, relies on the cooperation of the administrators of all
       participating domains to ensure that the global parameters are
       consistent with the desired transit policies and user service
       requirements of each domain.  Moreover, as the syntax and semantics
       of the global parameters affects the syntax and semantics of the
       corresponding IDPR software, the IANA must carefully define each
       global parameter so that it is unlikely to require future
       modification.

       The IANA provides configured global information to configuration
       servers in all domains participating in IDPR.  Each domain
       administrator uses the configured global information maintained by
       its configuration servers to develop configurations for each IDPR
       entity within its domain.  Each configuration server retains a copy
       of the configuration for each local IDPR entity and also distributes
       the configuration to that entity using, for example, SNMP.

    Steenstrup                                                     [Page 16]

    RFC 1479                     IDPR Protocol                     July 1993

    1.8.1.  Policy Gateway Configuration

       Each policy gateway must contain sufficient configuration information
       to perform its IDPR functions, which subsume those of the path agent.
       These include: validating IDPR control messages; generating and
       distributing virtual gateway connectivity and routing information
       messages to peer, neighbor, and adjacent policy gateways;
       distributing routing information messages to route servers in its
       domain; resolving destination addresses; requesting policy routes
       from route servers; selecting policy routes and initiating path
       setup; ensuring consistency of a path with its domain's transit
       policies; establishing path forwarding information; and forwarding
       IDPR data messages along existing paths.  The necessary configuration
       information includes the following:

       - For each integrity/authentication type, the numeric identifier,
         syntax, and semantics.

       - For each policy gateway and route server in the given domain, the
         numeric identifier and set of addresses or names.

       - For each virtual gateway connected to the given domain, the numeric
         identifier, the numeric identifiers for the constituent peer policy
         gateways, and the numeric identifier for the adjacent domain.

       - For each virtual gateway of which the given policy gateway is a
         member, the numeric identifiers and set of addresses for the
         constituent adjacent policy gateways.

       - For each policy gateway directly-connected and adjacent to the
         given policy gateway, the local connecting interface.

       - For each local route server to which the given policy gateway
         distributes routing information, the numeric identifier.

       - For each source policy applicable to hosts within the given domain,
         the syntax and semantics.

       - For each transit policy applicable to the domain, the numeric
         identifier, syntax, and semantics.

       - For each requested service that may appear within a path setup
         message, the numeric identifier, syntax, and semantics.

       - For each source user class, the numeric identifier, syntax, and
         semantics.

    Steenstrup                                                     [Page 17]

    RFC 1479                     IDPR Protocol                     July 1993

    1.8.2.  Route Server Configuration

       Each route server must contain sufficient configuration information
       to perform its IDPR functions, which subsume those of the path agent.
       These include: validating IDPR control messages; deciphering and
       storing the contents of routing information messages; exchanging
       routing information with other route servers and policy gateways;
       generating policy routes that respect transit policy restrictions and
       source service requirements; distributing policy routes to path
       agents in policy gateways; resolving destination addresses; selecting
       policy routes and initiating path setup; establishing path forwarding
       information; and forwarding IDPR data messages along existing paths.
       The necessary configuration information includes the following:

       - For each integrity/authentication type, the numeric identifier,
         syntax, and semantics.

       - For each policy gateway and route server in the given domain, the
         numeric identifier and set of addresses or names.

       - For each source policy applicable to hosts within the given domain,
         the syntax and semantics.

       - For access restriction that may be advertised in transit
         policies, the numeric identifier, syntax, and semantics.

       - For each offered service that may be advertised in transit policies,
         the numeric identifier, syntax, and semantics.

       - For each requested service that may appear within a path setup
         message, the numeric identifier, syntax, and semantics.

       - For each source user class, the numeric identifier, syntax, and
         semantics.

    2.  Control Message Transport Protocol

       IDPR control messages convey routing-related information that
       directly affects the policy routes generated and the paths set up
       across the Internet.  Errors in IDPR control messages can have
       widespread, deleterious effects on inter-domain policy routing, and
       so the IDPR protocols have been designed to minimize loss and
       corruption of control messages.  For every control message it
       transmits, each IDPR protocol expects to receive notification as to
       whether the control message successfully reached the intended IDPR
       recipient.  Moreover, the IDPR recipient of a control message first
       verifies that the message appears to be well-formed, before acting on
       its contents.

    Steenstrup                                                     [Page 18]

    RFC 1479                     IDPR Protocol                     July 1993

       All IDPR protocols use the Control Message Transport Protocol (CMTP),
       a connectionless, transaction-based transport layer protocol, for
       communication with intended recipients of control messages.  CMTP
       retransmits unacknowledged control messages and applies integrity and
       authenticity checks to received control messages.

       There are three types of CMTP messages:

       DATAGRAM:
            Contains IDPR control messages.

       ACK: Positive acknowledgement in response to a DATAGRAM message.

       NAK: Negative acknowledgement in response to a DATAGRAM message.

       Each CMTP message contains several pieces of information supplied by
       the sender that allow the recipient to test the integrity and
       authenticity of the message.  The set of integrity and authenticity
       checks performed after CMTP message reception are collectively
       referred to as "validation checks" and are described in section 2.3.

       When we first designed the IDPR protocols, CMTP as a distinct
       protocol did not exist.  Instead, CMTP-equivalent functionality was
       embedded in each IDPR protocol.  To provide a cleaner implementation,
       we later decided to provide a single transport protocol that could be
       used by all IDPR protocols.  We originally considered using an
       existing transport protocol, but rejected this approach for the
       following reasons:

       - The existing reliable transport protocols do not provide all of the
         validation checks, in particular the timestamp and authenticity
         checks, required by the IDPR protocols.  Hence, if we were to use
         one of these protocols, we would still have to provide a separate
         protocol on top of the transport protocol to force retransmission of
         IDPR messages that failed to pass the required validation checks.

       - Many of the existing reliable transport protocols are window-based
         and hence can result in increased message delay and resource use
         when, as is the case with IDPR, multiple independent messages use
         the same transport connection.  A single message experiencing
         transmission problems and requiring retransmission can prevent the
         window from advancing, forcing all subsequent messages to queue
         behind it.  Moreover, many of the window-based protocols do not
         support selective retransmission of failed messages but instead
         require retransmission of not only the failed message but also all
         preceding messages within the window.

       For these reasons, we decided against using an existing transport

    Steenstrup                                                     [Page 19]

    RFC 1479                     IDPR Protocol                     July 1993

       protocol and in favor of developing CMTP.

    2.1.  Message Transmission

       At the transmitting entity, when an IDPR protocol is ready to issue a
       control message, it passes a copy of the message to CMTP; it also
       passes a set of parameters to CMTP for inclusion in the CMTP header
       and for proper CMTP message handling.  In turn, CMTP converts the
       control message and associated parameters into a DATAGRAM by
       prepending the appropriate header to the control message.  The CMTP
       header contains several pieces of information to aid the message
       recipient in detecting errors (see section 2.4).  Each IDPR protocol
       can specify all of the following CMTP parameters applicable to its
       control message:

       -   IDPR protocol and message type.

       -   Destination.

       -   Integrity/authentication scheme.

       -   Timestamp.

       -   Maximum number of transmissions allotted.

       -   Retransmission interval in microseconds.

       One of these parameters, the timestamp, can be specified directly by
       CMTP as the internal clock time at which the message is transmitted.
       However, two of the IDPR protocols, namely flooding and path control,
       themselves require message generation timestamps for proper protocol
       operation.  Thus, instead of requiring CMTP to pass back a timestamp
       to an IDPR protocol, we simplify the service interface between CMTP
       and the IDPR protocols by allowing an IDPR protocol to specify the
       timestamp in the first place.

       Using the control message and accompanying parameters supplied by the
       IDPR protocol, CMTP constructs a DATAGRAM, adding to the header
       CMTP-specific parameters.  In particular, CMTP assigns a "transaction
       identifier" to each DATAGRAM generated, which it uses to associate
       acknowledgements with DATAGRAM messages.  Each DATAGRAM recipient
       includes the received transaction identifier in its returned ACK or
       NAK, and each DATAGRAM sender uses the transaction identifier to
       match the received ACK or NAK with the original DATAGRAM.

       A single DATAGRAM, for example a routing information message or a
       path control message, may be handled by CMTP at many different policy
       gateways.  Within a pair of consecutive IDPR entities, the DATAGRAM

    Steenstrup                                                     [Page 20]

    RFC 1479                     IDPR Protocol                     July 1993

       sender expects to receive an acknowledgement from the DATAGRAM
       recipient.  However, only the IDPR entity that actually generated the
       original CMTP DATAGRAM has control over the transaction identifier,
       because that entity may supply a digital signature that covers the
       entire DATAGRAM.  The intermediate policy gateways that transmit the
       DATAGRAM do not change the transaction identifier.  Nevertheless, at
       each DATAGRAM recipient, the transaction identifier must uniquely
       distinguish the DATAGRAM so that only one acknowledgement from the
       next DATAGRAM recipient matches the original DATAGRAM.  Therefore,
       the transaction identifier must be globally unique.

       The transaction identifier consists of the numeric identifiers for
       the domain and IDPR entity (policy gateway or route server) issuing
       the original DATAGRAM, together with a 32-bit local identifier
       assigned by CMTP operating within that IDPR entity.  We recommend
       implementing the 32-bit local identifier either as a simple counter
       incremented for each DATAGRAM generated or as a fine granularity
       clock.  The former always guarantees uniqueness of transaction
       identifiers; the latter guarantees uniqueness of transaction
       identifiers, provided the clock granularity is finer than the minimum
       possible interval between DATAGRAM generations and the clock wrapping
       period is longer than the maximum round-trip delay to and from any
       internetwork destination.

       Before transmitting a DATAGRAM, CMTP computes the length of the
       entire message, taking into account the prescribed
       integrity/authentication scheme, and then computes the
       integrity/authentication value over the whole message.  CMTP includes
       both of these quantities, which are crucial for checking message
       integrity and authenticity at the recipient, in the DATAGRAM header.
       After sending a DATAGRAM, CMTP saves a copy and sets an associated
       retransmission timer, as directed by the IDPR protocol parameters.
       If the retransmission timer fires and CMTP has received neither an
       ACK nor a NAK for the DATAGRAM, CMTP then retransmits the DATAGRAM,
       provided this retransmission does not exceed the transmission
       allotment.  Whenever a DATAGRAM exhausts its transmission allotment,
       CMTP discards the DATAGRAM, informs the IDPR protocol that the
       control message transmission was not successful, and logs the event
       for network management.  In this case, the IDPR protocol may either
       resubmit its control message to CMTP, specifying an alternate
       destination, or discard the control message altogether.

    Steenstrup                                                     [Page 21]

    RFC 1479                     IDPR Protocol                     July 1993

    2.2.  Message Reception

       At the receiving entity, when CMTP obtains a DATAGRAM, it takes one
       of the following actions, depending upon the outcome of the message
       validation checks:

       - The DATAGRAM passes the CMTP validation checks.  CMTP then delivers
         the DATAGRAM with enclosed IDPR control message, to the appropriate
         IDPR protocol, which in turn applies its own integrity checks to
         the control message before acting on the contents.  The recipient
         IDPR protocol, except in one case, directs CMTP to generate an ACK
         and return the ACK to the sender.  That exception is the up/down
         protocol (see section 3.2) which determines reachability of
         adjacent policy gateways and does not use CMTP ACK messages to
         notify the sender of message reception.  Instead, the up/down
         protocol messages themselves carry implicit information about
         message reception at the adjacent policy gateway.  In the cases
         where the recipient IDPR protocol directs CMTP to generate an ACK,
         it may pass control information to CMTP for inclusion in the ACK,
         depending on the contents of the original IDPR control message.
         For example, a route server unable to fill a request for routing
         information may inform the requesting IDPR entity, through an ACK
         for the initial request, to place its request elsewhere.

       - The DATAGRAM fails at least one of the CMTP validation checks.
         CMTP then generates a NAK, returns the NAK to the sender, and
         discards the DATAGRAM, regardless of the type of IDPR control
         message contained in the DATAGRAM.  The NAK indicates the nature of
         the validation failure and serves to help the sender establish
         communication with the recipient.  In particular, the CMTP NAK
         provides a mechanism for negotiation of IDPR version and
         integrity/authentication scheme, two parameters crucial for
         establishing communication between IDPR entities.

       Upon receiving an ACK or a NAK, CMTP immediately discards the message
       if at least one of the validation checks fails or if it is unable to
       locate the associated DATAGRAM.  CMTP logs the latter event for
       network management.  Otherwise, if all of the validation checks pass
       and if it is able to locate the associated DATAGRAM, CMTP clears the
       associated retransmission timer and then takes one of the following
       actions, depending upon the message type:

       - The message is an ACK.  CMTP discards the associated DATAGRAM and
         delivers the ACK, which may contain IDPR control information, to
         the appropriate IDPR protocol.

       - The message is a NAK.  If the associated DATAGRAM has exhausted its
         transmission allotment, CMTP discards the DATAGRAM, informs the

    Steenstrup                                                     [Page 22]

    RFC 1479                     IDPR Protocol                     July 1993

         appropriate IDPR protocol that the control message transmission was
         not successful, and logs the event for network management.
         Otherwise, if the associated DATAGRAM has not yet exhausted its
         transmission allotment, CMTP first checks its copy of the DATAGRAM
         against the failure indication contained in the NAK.  If its
         DATAGRAM copy appears to be intact, CMTP retransmits the DATAGRAM
         and sets the associated retransmission timer.  However, if its
         DATAGRAM copy appears to be corrupted, CMTP discards the DATAGRAM,
         informs the IDPR protocol that the control message transmission was
         not successful, and logs the event for network management.

    2.3.  Message Validation

       On every CMTP message received, CMTP performs a set of validation
       checks to test message integrity and authenticity.  The order in
       which these tests are executed is important.  CMTP must first
       determine if it can parse enough of the message to compute the
       integrity/authentication value.  (Refer to section 2.4 for a
       description of CMTP message formats.)  Then, CMTP must immediately
       compute the integrity/authentication value before checking other
       header information.  An incorrect integrity/authentication value
       means that the message is corrupted, and so it is likely that CMTP
       header information is incorrect.  Checking specific header fields
       before computing the integrity/authentication value not only may
       waste time and resources, but also may lead to incorrect diagnoses of
       a validation failure.

       The CMTP validation checks are as follows:

       - CMTP verifies that it can recognize both the control message
         version type contained in the header.  Failure to recognize either
         one of these values means that CMTP cannot continue to parse the
         message.

       - CMTP verifies that it can recognize and accept the
         integrity/authentication type contained in the header; no
         integrity/authentication is not an acceptable type for CMTP.

       - CMTP computes the integrity/authentication value and verifies that
         it equals the integrity/authentication value contained in the
         header.  For key-based integrity/authentication schemes, CMTP may
         use the source domain identifier contained in the CMTP header to
         index the correct key.  Failure to index a key means that CMTP
         cannot compute the integrity/authentication value.

       - CMTP computes the message length in bytes and verifies that it
         equals the length value contained in the header.

    Steenstrup                                                     [Page 23]

    RFC 1479                     IDPR Protocol                     July 1993

       - CMTP verifies that the message timestamp is in the acceptable
         range.  The message should be no more recent than cmtp_new (300)
         seconds ahead of the entity's current internal clock time.  In this
         document, when we present an IDPR system configuration parameter,
         such as cmtp_new, we usually follow it with a recommended value in
         parentheses.  The cmtp_new value allows some clock drift between
         IDPR entities.  Moreover, each IDPR protocol has its own limit on
         the maximum age of its control messages.  The message should be no
         less recent than a prescribed number of seconds behind the
         recipient entity's current internal clock time.  Hence, each IDPR
         protocol performs its own message timestamp check in addition to
         that performed by CMTP.

       - CMTP verifies that it can recognize the IDPR protocol designated
         for the enclosed control message.

       Whenever CMTP encounters a failure while performing any of these
       validation checks, it logs the event for network management.  If the
       failure occurs on a DATAGRAM, CMTP immediately generates a NAK
       containing the reason for the failure, returns the NAK to the sender,
       and discards the DATAGRAM message.  If the failure occurs on an ACK
       or a NAK, CMTP discards the ACK or NAK message.

    2.4.  CMTP Message Formats

       In designing the format of IDPR control messages, we have attempted
       to strike a balance between efficiency of link bandwidth usage and
       efficiency of message processing.  In general, we have chosen compact
       representations for IDPR information in order to minimize the link
       bandwidth consumed by IDPR-specific information.  However, we have
       also organized IDPR information in order to speed message processing,
       which does not always result in minimum link bandwidth usage.

       To limit link bandwidth usage, we currently use fixed-length
       identifier fields in IDPR messages; domains, virtual gateways, policy
       gateways, and route servers are all represented by fixed-length
       identifiers.  To simplify message processing, we currently align
       fields containing an even number of bytes on even-byte boundaries
       within a message.  In the future, if the Internet adopts the use of
       super domains, we will offer hierarchical, variable-length identifier
       fields in an updated version of IDPR.

       The header of each CMTP message contains the following information:

    Steenstrup                                                     [Page 24]

    RFC 1479                     IDPR Protocol                     July 1993

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    VERSION    |  PRT  |  MSG  |  DPR  |  DMS  |    I/A TYP    |
       +---------------+-------+-------+-------+-------+---------------+
       |           SOURCE AD           |           SOURCE ENT          |
       +-------------------------------+-------------------------------+
       |                           TRANS ID                            |
       +---------------------------------------------------------------+
       |                           TIMESTAMP                           |
       +-------------------------------+-------------------------------+
       |            LENGTH             |       message specific        |
       +-------------------------------+-------------------------------+
       |         DATAGRAM AD           |         DATAGRAM ENT          |
       +-------------------------------+-------------------------------+
       |                             INFORM                            |
       +---------------------------------------------------------------+
       |                            INT/AUTH                           |
       |                                                               |
       +---------------------------------------------------------------+

       VERSION
            (8 bits) Version number for IDPR control messages, currently
            equal to 1.

       PRT (4 bits) Numeric identifier for the control message transport
            protocol, equal to 0 for CMTP.

       MSG (4 bits) Numeric identifier for the CMTP message type,equal to 0
            for a DATAGRAM, 1 for an ACK, and 2 for a NAK.

       DPR (4 bits) Numeric identifier for the original DATAGRAM's IDPR
            protocol type.

       DMS (4 bits) Numeric identifier for the original DATAGRAM's IDPR
            message type.

       I/A TYP (8 bits) Numeric identifier for the integrity/authentication
            scheme used.  CMTP requires the use of an
            integrity/authentication scheme; this value must not be set
            equal to 0, indicating no integrity/authentication in use.

       SOURCE AD (16 bits) Numeric identifier for the domain containing the
            IDPR entity that generated the message.

       SOURCE ENT (16 bits) Numeric identifier for the IDPR entity that
            generated the message.

    Steenstrup                                                     [Page 25]

    RFC 1479                     IDPR Protocol                     July 1993

       TRANSACTION ID (32 bits) Local transaction identifier assigned by the
            IDPR entity that generated the original DATAGRAM.

       TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970
            0:00 GMT.

       LENGTH (16 bits) Length of the entire IDPR control message, including
            the CMTP header, in bytes.

       message specific (16 bits) Dependent upon CMTP message type.

            For DATAGRAM and ACK messages:

                 RESERVED
                      (16 bits) Reserved for future use and currently set
                      equal to 0.

            For NAK messages:

                 ERR TYP (8 bits) Numeric identifier for the type of CMTP
                      validation failure encountered.  Validation failures
                      include the following types:

                      1.   Unrecognized IDPR control message version number.

                      2.   Unrecognized CMTP message type.

                      3.   Unrecognized integrity/authentication scheme.

                      4.   Unacceptable integrity/authentication scheme.

                      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

       Distribution of intra-VG messages among peers often triggers
       generation and distribution of inter-VG messages among virtual
       gateways.  Usually, the lowest-numbered operational policy gateway in
       a virtual gateway generates and distributes an inter-VG message
       immediately after detecting a change in virtual gateway connectivity,
       through receipt or generation of an intra-VG message.  However, if
       this policy gateway is also waiting for an intra-VG message from a
       newly reachable peer, it does not immediately generate and distribute
       the inter-VG message.

       Waiting for intra-VG messages enables the lowest-numbered operational
       policy gateway in a virtual gateway to gather the most recent
       connectivity information for inclusion in the inter-VG message.
       However, under unusual circumstances, the policy gateway may fail to
       receive an intra-VG message from a newly reachable peer, even after
       actively requesting such a message.  To accommodate this case, VGP
       uses an upper bound of four times the configured retransmission
       interval, vgp_int microseconds, on the amount of time to wait before
       generating and distributing an inter-VG message, when receipt of an
       intra-VG message is pending.

    3.1.4.  VG Representatives

       When distributing an inter-VG message, the issuing policy gateway
       selects as recipients one neighbor, the VG Representative, from each
       virtual gateway in the domain.  To be selected as a VG
       representative, a policy gateway must be reachable from the issuing
       policy gateway via intra-domain routing.  The issuing policy gateway
       gives preference to neighbors that are members of more than one
       virtual gateway.  Such a neighbor acts as a VG representative for all
       virtual gateways of which it is a member and restricts inter-VG
       message distribution as follows: any policy gateway that is a peer in
       more than one of the represented virtual gateways receives at most
       one copy of the inter-VG message.  This message distribution strategy
       minimizes the number of message copies required for disseminating
       inter-VG information.

    3.2.  Up/Down Protocol

       Directly-connected adjacent policy gateways execute the Up/Down
       Protocol to determine mutual reachability.  Pairs of peer or neighbor
       policy gateways can determine mutual reachability through information
       provided by the intra-domain routing procedure or through execution
       of the up/down protocol.  In general, we do not recommend
       implementing the up/down protocol between each pair of policy
       gateways in a domain, as it results in O(n**2) (where n is the number
       of policy gateways within the domain) communications complexity.
       However, if the intra-domain routing procedure is slow to detect

    Steenstrup                                                     [Page 31]

    RFC 1479                     IDPR Protocol                     July 1993

       connectivity changes or is unable to report reachability at the IDPR
       entity level, the reachability information obtained through the
       up/down protocol may well be worth the extra communications cost.  In
       the remainder of this section, we decribe the up/down protocol from
       the perspective of adjacent policy gateways, but we note that the
       identical protocol can be applied to peer and neighbor policy
       gateways as well.

       The up/down protocol determines whether the direct connection between
       adjacent policy gateways is acceptable for data traffic transport.  A
       direct connection is presumed to be "down" (unacceptable for data
       traffic transport) until the up/down protocol declares it to be "up"
       (acceptable for data traffic transport).  We say that a virtual
       gateway is "up" if there exists at least one pair of adjacent policy
       gateways whose direct connection is acceptable for data traffic
       transport, and that a virtual gateway is "down" if there exists no
       such pair of adjacent policy gateways.

       When executing the up/down protocol, policy gateways exchange UP/DOWN
       messages every ud_per (1) second.  All policy gateways use the same
       default period of ud_per initially and then negotiate a preferred
       period through exchange of UP/DOWN messages.  A policy gateway
       reports its desired value for ud_per within its UP/DOWN messages.  It
       then chooses the larger of its desired value and that of the adjacent
       policy gateway as the period for exchanging subsequent UP/DOWN
       messages.  Policy gateways also exchange, in UP/DOWN messages,
       information about the identity of their respective domain components.
       This information assists the policy gateways in selecting routes
       across virtual gateways to partitioned domains.

       Each UP/DOWN message is transported using CMTP and hence is covered
       by the CMTP validation checks.  However, unlike other IDPR control
       messages, UP/DOWN messages do not require reliable transport.
       Specifically, the up/down protocol requires only a single
       transmission per UP/DOWN message and never directs CMTP to return an
       ACK.  As pair-PG messages, UP/DOWN messages are acceptable under the
       conditions described in section 3.1.1.

       Each policy gateway assesses the state of its direct connection, to
       the adjacent policy gateway, by counting the number of acceptable
       UP/DOWN messages received within a set of consecutive periods.  A
       policy gateway communicates its perception of the state of the direct
       connection through its UP/DOWN messages.  Initially, a policy gateway
       indicates the down state in each of its UP/DOWN messages.  Only when
       the direct connection appears to be up from its perspective does a
       policy gateway indicate the up state in its UP/DOWN messages.

       A policy gateway can begin to transport data traffic over a direct

    Steenstrup                                                     [Page 32]

    RFC 1479                     IDPR Protocol                     July 1993

       connection only if both of the following conditions are true:

       - The policy gateway receives from the adjacent policy gateway at
         least j acceptable UP/DOWN messages within the last m consecutive
         periods.  From the recipient policy gateway's perspective, this
         event up.  Hence, the recipient policy gateway indicates the up
         state in its subsequent UP/DOWN messages.

       - The UP/DOWN message most recently received from the adjacent policy
         gateway indicates the up state, signifying that the adjacent policy
         gateway considers the direct connection to be up.

       A policy gateway must cease to transport data traffic over a direct
       connection whenever either of the following conditions is true:

       - The policy gateway receives from the adjacent policy gateway at
         most acceptable UP/DOWN messages within the last n consecutive
         periods.

       - The UP/DOWN message most recently received from the adjacent policy
         gateway indicates the down state, signifying that the adjacent
         policy gateway considers the direct connection to be down.

       From the recipient policy gateway's perspective, either of these
       events constitutes a state transition of the direct connection from
       up to down.  Hence, the policy gateway indicates the down state in
       its subsequent UP/DOWN messages.

    3.3.  Implementation

       We recommend implementing the up/down protocol using a sliding
       window.  Each window slot indicates the UP/DOWN message activity
       during a given period, containing either a "hit" for receipt of an
       acceptable UP/DOWN message or a "miss" for failure to receive an
       acceptable UP/DOWN message.  In addition to the sliding window, the
       implementation should include a tally of hits recorded during the
       current period and a tally of misses recorded over the current
       window.

       When the direct connection moves to the down state, the initial
       values of the up/down protocol parameters must be set as follows:

       -   The sliding window size is equal to m.

       -   Each window slot contains a miss.

       -   The current period hit tally is equal to 0.

    Steenstrup                                                     [Page 33]

    RFC 1479                     IDPR Protocol                     July 1993

       -   The current window miss tally is equal to m.

       When the direct connection moves to the up state, the initial values
       of the up/down protocol parameters must be set as follows:

       -   The sliding window size is equal to n.

       -   Each window slot contains a hit.

       -   The current period hit tally is equal to 0.

       -   The current window miss tally is equal to 0.

       At the conclusion of each period, a policy gateway computes the miss
       tally and determines whether there has been a state transition of the
       direct connection to the adjacent policy gateway.  In the down state,
       a miss tally of no more than m - j signals a transition to the up
       state.  In the up state, a miss tally of no less than n - k signals a
       transition to the down state.

       Computing the correct miss tally involves several steps.  First, the
       policy gateway prepares to slide the window by one slot so that the
       oldest slot disappears, making room for the newest slot.  However,
       before sliding the window, the policy gateway checks the contents of
       the oldest window slot.  If this slot contains a miss, the policy
       gateway decrements the miss tally by 1, as this slot is no longer
       part of the current window.

       After sliding the window, the policy gateway determines the proper
       contents.  If the hit tally for the current period equals 0, the
       policy gateway records a miss for the newest slot and increments the
       miss tally by 1.  Otherwise, if the hit tally for the current period
       is greater than 0, the policy gateway records a hit for the newest
       slot and decrements the hit tally by 1.  Moreover, the policy gateway
       applies any remaining hits to slots containing misses, beginning with
       the newest and progressing to the oldest such slot.  For each such
       slot containing a miss, the policy gateway records a hit in that slot
       and decrements both the hit and miss tallies by 1, as the hit cancels
       out a miss.  The policy gateway continues to apply each remaining hit
       tallied to any slot containing a miss, until either all such hits are
       exhausted or all such slots are accounted for.  Before beginning the
       next up/down period, the policy gateway resets the hit tally to 0.

       Although we expect the hit tally, within any given period, to be no
       greater than 1, we do anticipate the occasional period in which a
       policy gateway receives more than one UP/DOWN message from an
       adjacent policy gateway.  The most common reasons for this occurrence
       are message delay and clock drift.  When an UP/DOWN message is

    Steenstrup                                                     [Page 34]

    RFC 1479                     IDPR Protocol                     July 1993

       delayed, the receiving policy gateway observes a miss in one period
       followed by two hits in the next period, one of which cancels the
       previous miss.  However, excess hits remaining in the tally after
       miss cancellation indicate a problem, such as clock drift.  Thus,
       whenever a policy gateway accumulates excess hits, it logs the event
       for network management.

       When clock drift occurs between two adjacent policy gateways, it
       causes the period of one policy gateway to grow with respect to the
       period of the other policy gateway.  Let p(X) be the period for PG X,
       let p(Y) be the period for PG Y, and let g and h be the smallest
       positive integers such that g * p(X) = h * p(Y).  Suppose that p(Y) >
       p(X) because of clock drift.  In this case, PG X observes g - h
       misses in g consecutive periods, while PG Y observes g - h surplus
       hits in h consecutive periods.  As long as (g - h)/g < (n - k)/n and
       (g - h)/g < or = (m - j)/m, the clock drift itself will not cause the
       direct connection to enter or remain in the down state.

    3.4.  Policy Gateway Connectivity

       Policy gateways collect connectivity information through the intra-
       domain routing procedure and through VGP, and they distribute
       connectivity changes through VGP in both intra-VG messages to peers
       and inter-VG messages to neighbors.  Locally, this connectivity
       information assists policy gateways in selecting routes, not only
       across a virtual gateway to an adjacent domain but also across a
       domain between two virtual gateways.  Moreover, changes in
       connectivity between domains are distributed, in routing information
       messages, to route servers throughout an internetwork.

    3.4.1.  Within a Virtual Gateway

       Each policy gateway within a virtual gateway constantly monitors its
       connectivity to all adjacent and to all peer policy gateways.  To
       determine the state of its direct connection to an adjacent policy
       gateway, a policy gateway uses reachability information supplied by
       the up/down protocol.  To determine the state of its intra-domain
       routes to a peer policy gateway, a policy gateway uses reachability
       information supplied by either the intra-domain routing procedure or
       the up/down protocol.

       A policy gateway generates a PG CONNECT message whenever either of
       the following conditions is true:

       -   The policy gateway detects a change, in state or in adjacent
           domain component, associated with its direct connection to an
           adjacent policy gateway.  In this case, the policy gateway
           distributes a copy of the message to each peer reachable via

    Steenstrup                                                     [Page 35]

    RFC 1479                     IDPR Protocol                     July 1993

           intra-domain routing.

       -   The policy gateway detects that a previously unreachable peer is
           now reachable.  In this case, the policy gateway distributes a
           copy of the message to the newly reachable peer.

       A PG CONNECT message is an intra-VG message that includes information
       about each adjacent policy gateway directly connected to the issuing
       policy gateway.  Specifically, the PG CONNECT message contains the
       adjacent policy gateway's identifier, status (reachable or
       unreachable), and domain component identifier.  If a PG CONNECT
       message contains a "request", each peer that receives the message
       responds to the sender with its own PG CONNECT message.

       All mutually reachable peers monitor policy gateway connectivity
       within their virtual gateway, through the up/down protocol, the
       intra-domain routing procedure, and the exchange of PG CONNECT
       messages.  Within a given virtual gateway, each constituent policy
       gateway maintains the following information about each configured
       adjacent policy gateway:

       - The identifier for the adjacent policy gateway.

       - The status of the adjacent policy gateway: reachable/unreachable,
         directly connected/not directly connected.

       - The local exit interfaces used to reach the adjacent policy
         gateway, provided it is reachable.

       - The identifier for the adjacent policy gateway's domain component.

       - The set of peers to which the adjacent policy gateway is
         directly-connected.

       Hence, all mutually reachable peers can detect changes in
       connectivity across the virtual gateway to adjacent domain
       components.

       When the lowest-numbered operational peer policy gateway within a
       virtual gateway detects a change in the set of adjacent domain
       components reachable through direct connections across the given
       virtual gateway, it generates a VGCONNECT message and distributes a
       copy to a VG representative in all other virtual gateways connected
       to its domain.  A VG CONNECT message is an inter-VG message that
       includes information about each peer's connectivity across the given
       virtual gateway.  Specifically, the VG CONNECT message contains, for
       each peer, its identifier and the identifiers of the domain
       components reachable through its direct connections to adjacent

    Steenstrup                                                     [Page 36]

    RFC 1479                     IDPR Protocol                     July 1993

       policy gateways.  Moreover, the VG CONNECT message gives each
       recipient enough information to determine the state, up or down, of
       the issuing virtual gateway.

       The issuing policy gateway, namely the lowest-numbered operational
       peer, may have to wait up to four times vgp_int microseconds after
       detecting the connectivity change, before generating and distributing
       the VGCONNECT message, as described in section 3.1.3.  Each recipient
       VG representative in turn distributes a copy of the VG CONNECT
       message to each of its peers reachable via intra-domain routing.  If
       a VG CONNECT message contains a "request", then in each recipient
       virtual gateway, the lowest-numbered operational peer that receives
       the message responds to the original sender with its own VGCONNECT
       message.

    3.4.2.  Between Virtual Gateways

       At present, we expect transit policies to be uniform over all intra-
       domain routes between any pair of policy gateways within a domain.
       However, when tariffed qualities of service become prevalent
       offerings for intra-domain routing, we can no longer expect
       uniformity of transit policies throughout a domain.  To monitor the
       transit policies supported on intra-domain routes between virtual
       gateways requires both a policy-sensitive intra-domain routing
       procedure and a VGP exchange of policy information between neighbor
       policy gateways.

       Each policy gateway within a domain constantly monitors its
       connectivity to all peer and neighbor policy gateways, including the
       transit policies supported on intra-domain routes to these policy
       gateways.  To determine the state of its intra-domain connection to a
       peer or neighbor policy gateway, a policy gateway uses reachability
       information supplied by either the intra-domain routing procedure or
       the up/down protocol.  To determine the transit policies supported on
       intra-domain routes to a peer or neighbor policy gateway, a policy
       gateway uses policy-sensitive reachability information supplied by
       the intra-domain routing procedure.  We note that when transit
       policies are uniform over a domain, reachability and policy-sensitive
       reachability are equivalent.

       Within a virtual gateway, each constituent policy gateway maintains
       the following information about each configured peer and neighbor
       policy gateway:

       - The identifier for the peer or neighbor policy gateway.

       - The identifiers corresponding to the transit policies configured to
         be supported by intra-domain routes to the peer or neighbor policy

    Steenstrup                                                     [Page 37]

    RFC 1479                     IDPR Protocol                     July 1993

         gateway.

       - According to each transit policy, the status of the peer or
         neighbor policy gateway: reachable/unreachable.

       - For each transit policy, the local exit interfaces used to reach
         the peer or neighbor policy gateway, provided it is reachable.

       - The identifiers for the adjacent domain components reachable
         through direct connections from the peer or neighbor policy
         gateway, obtained through VG CONNECT messages.

       Using this information, a policy gateway can detect changes in its
       connectivity to an adjoining domain component, with respect to a
       given transit policy and through a given neighbor.  Moreover,
       combining the information obtained for all neighbors within a given
       virtual gateway, the policy gateway can detect changes in its
       connectivity, with respect to a given transit policy, to that virtual
       gateway and to adjoining domain components reachable through that
       virtual gateway.

       All policy gateways mutually reachable via intra-domain routes
       supporting a configured transit policy need not exchange information
       about perceived changes in connectivity, with respect to the given
       transit policy.  In this case, each policy gateway can infer
       another's policy-sensitive reachability to a third, through mutual
       intra-domain reachability information provided by the intra-domain
       routing procedure.  However, whenever two or more policy gateways are
       no longer mutually reachable with respect to a given transit policy,
       these policy gateways can no longer infer each other's reachability
       to other policy gateways, with respect to that transit policy.  In
       this case, these policy gateways must exchange explicit information
       about changes in connectivity to other policy gateways, with respect
       to that transit policy.

       A policy gateway generates a PG POLICY message whenever either of the
       following conditions is true:

       - The policy gateway detects a change in its connectivity to another
         virtual gateway, with respect to a configured transit policy, or to
         an adjoining domain component reachable through that virtual
         gateway.  In this case, the policy gateway distributes a copy of
         the message to each peer reachable via intra-domain routing but not
         currently reachable via any intra-domain routes of the given
         transit policy.

       - The policy gateway detects that a previously unreachable peer is
         reachable.  In this case, the policy gateway distributes a copy of

    Steenstrup                                                     [Page 38]

    RFC 1479                     IDPR Protocol                     July 1993

         the message to the newly reachable peer.

       A PG POLICY message is an intra-VG message that includes information
       about each configured transit policy and each virtual gateway
       configured to be reachable from the issuing policy gateway via
       intra-domain routes of the given transit policy.  Specifically, the
       PGPOLICY message contains, for each configured transit policy:

       - The identifier for the transit policy.

       - The identifiers for the virtual gateways associated with the given
         transit policy and currently reachable, with respect to that
         transit policy, from the issuing policy gateway.

       - The identifiers for the domain components reachable from and
         adjacent to the members of the given virtual gateways.

       If a PG POLICY message contains a "request", each peer that receives
       the message responds to the original sender with its own PG POLICY
       message.

       In addition to connectivity between itself and its neighbors, each
       policy gateway also monitors the connectivity, between domain
       components adjacent to its virtual gateway and domain components
       adjacent to other virtual gateways, through its domain and with
       respect to the configured transit policies.  For each member of each
       of its virtual gateways, a policy gateway monitors:

       -  The set of  adjacent domain components  currently reachable
         through direct connections across the given virtual gateway.  The
         policy gateway obtains this information through PG CONNECT messages
         from reachable peers and through UP/DOWN messages from adjacent
         policy gateways.

       - For each configured transit policy, the set of virtual gateways
         currently reachable from the given virtual gateway with respect to
         that transit policy and the set of adjoining domain components
         currently reachable through direct connections across those virtual
         gateways.  The policy gateway obtains this information through PG
         POLICY messages from peers, VG CONNECT messages from neighbors, and
         the intra-domain routing procedure.  Using this information, a
         policy gateway can detect connectivity changes, through its domain
         and with respect to a given transit policy, between adjoining
         domain components.

       When the lowest-numbered operational policy gateway within a virtual
       gateway detects a change in the connectivity between a domain
       component adjacent to its virtual gateway and a domain component

    Steenstrup                                                     [Page 39]

    RFC 1479                     IDPR Protocol                     July 1993

       adjacent to another virtual gateway in its domain, with respect to a
       configured transit policy, it generates a VG POLICY message and
       distributes a copy to a VG representative in selected virtual
       gateways connected to its domain.  In particular, the lowest-numbered
       operational policy gateway distributes a VG POLICY message to a VG
       representative in every other virtual gateway containing a member
       reachable via intra-domain routing but not currently reachable via
       any routes of the given transit policy.  A VG POLICY message is an
       inter-VG message that includes information about the connectivity
       between domain components adjacent to the issuing virtual gateway and
       domain components adjacent to the other virtual gateways in the
       domain, with respect to configured transit policies.  Specifically,
       the VG POLICY message contains, for each transit policy:

       - The identifier for the transit policy.

       - The identifiers for the virtual gateways associated with the given
         transit policy and currently reachable, with respect to that
         transit policy, from the issuing virtual gateway.

       - The identifiers for the domain components reachable from and
         adjacent to the members of the given virtual gateways.

       The issuing policy gateway, namely the lowest-numbered operational
       peer, may have to wait up to four times vgp_int microseconds after
       detecting the connectivity change, before generating and distributing
       the VG POLICY message, as described in section 3.1.3.  Each recipient
       VG representative in turn distributes a copy of the VG POLICY message
       to each of its peers reachable via intra-domain routing.  If a VG
       POLICY message contains a "request", then in each recipient virtual
       gateway, the lowest-numbered operational peer that receives the
       message responds to the original sender with its own VG POLICY
       message.

    3.4.3.  Communication Complexity

       We offer an example, to provide an estimate of the number of VGP
       messages exchanged within a domain, AD X, after a detected change in
       policy gateway connectivity.  Suppose that an adjacent domain, AD Y,
       partitions such that the partition is detectable through the exchange
       of UP/DOWN messages across a virtual gateway connecting AD X and AD
       Y.  Let V be the number of virtual gateways in AD X.  Suppose each
       virtual gateway contains P peer policy gateways, and no policy
       gateway is a member of multiple virtual gateways.  Then, within AD X,
       the detected partition will result in the following VGP message
       exchanges:

       - P policy gateways each receive at most P-1 PG CONNECT messages.

    Steenstrup                                                     [Page 40]

    RFC 1479                     IDPR Protocol                     July 1993

         Each policy gateway detecting the adjacent domain partition
         generates a PG CONNECT message and distributes it to each reachable
         peer in the virtual gateway.

       - P * (V-1) policy gateways each receive at most one VG CONNECT
         message.  The lowest-numbered operational policy gateway in the
         virtual gateway detecting the partition of the adjacent domain
         generates a VG CONNECT message and distributes it to a VG
         representative in all other virtual gateways connected to the
         domain.  In turn, each VG representative distributes the VG CONNECT
         message to each reachable peer within its virtual gateway.

       - P * (V-1) policy gateways each receive at most P-1 PG POLICY
         messages, and only if the domain has more than a single uniform
         transit policy.  Each policy gateway in each virtual gateway
         generates a PG POLICY message and distributes it to all reachable
         peers not currently reachable with respect to the given transit
         policy.

       - P * V policy gateways each receive at most V-1 VG POLICY messages,
         only if the domain has more than a single uniform transit policy.
         The lowest-numbered operational policy gateway in each virtual
         gateway generates a VG POLICY message and distributes it to a VG
         representative in all other virtual gateways containing at least
         one reachable member not currently reachable with respect to the
         given transit policy.  In turn, each VG representative distributes
         a VG POLICY message to each peer within its virtual gateway.

    3.5.  VGP Message Formats

       The virtual gateway protocol number is equal to 0.  We describe the
       contents of each type of VGP message below.

    3.5.1.  UP/DOWN

       The UP/DOWN message type is equal to 0.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            SRC CMP            |            DST AD             |
       +-------------------------------+---------------+---------------+
       |            DST PG             |    PERIOD     |     STATE     |
       +-------------------------------+---------------+---------------+

       SRC CMP
            (16 bits) Numeric identifier for the domain component containing
            the issuing policy gateway.

    Steenstrup                                                     [Page 41]

    RFC 1479                     IDPR Protocol                     July 1993

       DST AD (16 bits) Numeric identifier for the destination domain.

       DST PG (16 bits) Numeric identifier for the destination policy
            gateway.

       PERIOD (8 bits) Length of the UP/DOWN message generation period, in
            seconds.

       STATE (8 bits) Perceived state (1 up, 0 down) of the direct
            connection from the perspective of the issuing policy gateway,
            contained in the right-most bit.

    3.5.2.  PG CONNECT

       The PG CONNECT message type is equal to 1.  PG CONNECT messages are
       not required for any virtual gateway containing exactly two policy
       gateways.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            ADJ AD             |      VG       |     RQST      |
       +-------------------------------+---------------+---------------+
       |            NUM RCH            |           NUM UNRCH           |
       +-------------------------------+-------------------------------+
       For each reachable adjacent policy gateway:
       +-------------------------------+-------------------------------+
       |            ADJ PG             |            ADJ CMP            |
       +-------------------------------+-------------------------------+
       For each unreachable adjacent policy gateway:
       +-------------------------------+
       |            ADJ PG             |
       +-------------------------------+

       ADJ AD
            (16 bits) Numeric identifier for the adjacent domain.

       VG (8 bits) Numeric identifier for the virtual gateway.

       RQST (8 bits) Request for a PG CONNECT message (1 request, 0 no
            request) from each recipient peer, contained in the right-most
            bit.

       NUM RCH (16 bits) Number of adjacent policy gateways within the
            virtual gateway, which are directly-connected to and currently
            reachable from the issuing policy gateway.

       NUM UNRCH (16 bits) Number of adjacent policy gateways within the

    Steenstrup                                                     [Page 42]

    RFC 1479                     IDPR Protocol                     July 1993

            virtual gateway, which are directly-connected to but not
            currently reachable from the issuing policy gateway.

       ADJ PG (16 bits) Numeric identifier for a directly-connected adjacent
            policy gateway.

       ADJ CMP (16 bits) Numeric identifier for the domain component
            containing the reachable, directly-connected adjacent policy
            gateway.

    3.5.3.  PG POLICY

       The PG POLICY message type is equal to 2.  PG POLICY messages are not
       required for any virtual gateway containing exactly two policy
       gateways or for any domain with a single uniform transit policy.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            ADJ AD             |      VG       |     RQST      |
       +-------------------------------+---------------+---------------+
       |            NUM TP             |
       +-------------------------------+
       For each transit policy associated with the virtual gateway:
       +-------------------------------+-------------------------------+
       |              TP               |            NUM VG             |
       +-------------------------------+-------------------------------+
       For each virtual gateway reachable via the transit policy:
       +-------------------------------+---------------+---------------+
       |            ADJ AD             |      VG       |    UNUSED     |
       +-------------------------------+---------------+---------------+
       |            NUM CMP            |            ADJ CMP            |
       +-------------------------------+-------------------------------+

       ADJ AD
            (16 bits) Numeric identifier for the adjacent domain.

       VG (8 bits) Numeric identifier for the virtual gateway.

       RQST (8 bits) Request for a PG POLICY message (1 request, 0 no
            request) from each recipient peer, contained in the right-most
            bit.

       NUM TP (8 bits) Number of transit policies configured to include the
            virtual gateway.

       TP (16 bits) Numeric identifier for a transit policy associated with
            the virtual gateway.

    Steenstrup                                                     [Page 43]

    RFC 1479                     IDPR Protocol                     July 1993

       NUM VG (16 bits) Number of virtual gateways reachable from the
            issuing policy gateway, via intra-domain routes supporting the
            transit policy.

       UNUSED (8 bits) Not currently used; must be set equal to 0.

       NUM CMP (16 bits) Number of adjacent domain components reachable via
            direct connections through the virtual gateway.

       ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
            component.

    3.5.4.  VG CONNECT

       The VG CONNECT 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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            ADJ AD             |      VG       |     RQST      |
       +-------------------------------+---------------+---------------+
       |            NUM PG             |
       +-------------------------------+
       For each reach policy gateway in the virtual gateway:
       +-------------------------------+-------------------------------+
       |              PG               |            NUM CMP            |
       +-------------------------------+-------------------------------+
       |            ADJ CMP            |
       +-------------------------------+

       ADJ AD
            (16 bits) Numeric identifier for the adjacent domain.

       VG (8 bits) Numeric identifier for the virtual gateway.

       RQST (8 bits) Request for a VG CONNECT message (1 request, 0 no
            request) from a recipient in each virtual gateway, contained in
            the right-most bit.

       NUM PG (16 bits) Number of mutually-reachable peer policy gateways in
            the virtual gateway.

       PG (16 bits) Numeric identifier for a peer policy gateway.

       NUM CMP (16 bits) Number of components of the adjacent domain
            reachable via direct connections from the policy gateway.

    Steenstrup                                                     [Page 44]

    RFC 1479                     IDPR Protocol                     July 1993

       ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
            component.

    3.5.5.  VG POLICY

       The VG POLICY message type is equal to 4.  VG POLICY messages are not
       required for any domain with a single uniform transit policy.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            ADJ AD             |      VG       |     RQST      |
       +-------------------------------+---------------+---------------+
       |            NUM TP             |
       +-------------------------------+
       For each transit policy associated with the virtual gateway:
       +-------------------------------+-------------------------------+
       |              TP               |            NUM GRP            |
       +-------------------------------+-------------------------------+
       For each virtual gateway group reachable via the transit policy:
       +-------------------------------+-------------------------------+
       |            NUM VG             |            ADJ AD             |
       +---------------+---------------+-------------------------------+
       |     VG        |    UNUSED     |            NUM CMP            |
       +---------------+---------------+-------------------------------+
       |            ADJ CMP            |
       +-------------------------------+

       ADJ AD
            (16 bits) Numeric identifier for the adjacent domain.

       VG (8 bits) Numeric identifier for the virtual gateway.

       RQST (8 bits) Request for a VG POLICY message (1 request, 0 no
            request) from a recipient in each virtual gateway, contained in
            the right-most bit.

       NUM TP (16 bits) Number of transit policies configured to include the
            virtual gateway.

       TP (16 bits) Numeric identifier for a transit policy associated with
            the virtual gateway.

       NUM GRP (16 bits) Number of groups of virtual gateways, such that all
            members in a group are reachable from the issuing virtual
            gateway via intra-domain routes supporting the given transit
            policy.

    Steenstrup                                                     [Page 45]

    RFC 1479                     IDPR Protocol                     July 1993

       NUM VG (16 bits) Number of virtual gateways in a virtual gateway
            group.

       UNUSED (8 bits) Not currently used; must be set equal to 0.

       NUM CMP (16 bits) Number of adjacent domain components reachable via
            direct connections through the virtual gateway.

       ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
            component.

       Normally, each VG POLICY message will contain a single virtual
       gateway group.  However, if the issuing virtual gateway becomes
       partitioned such that peers are mutually reachable with respect to
       some transit policies but not others, virtual gateway groups may be
       necessary.  For example, let PG X and PG Y be two peers in VG A which
       configured to support transit policies 1 and 2.  Suppose that PG X
       and PG Y are reachable with respect to transit policy 1 but not with
       respect to transit policy 2.  Furthermore, suppose that PG X can
       reach members of VG B via intra-domain routes of transit policy 2 and
       that PG Y can reach members of VG C via intra-domain routes of
       transit policy 2.  Then the entry in the VG POLICY message issued by
       VG A will include, for transit policy 2, two groups of virtual
       gateways, one containing VG B and one containing VG C.

    3.5.6.  Negative Acknowledgements

       When a policy gateway receives an unacceptable VGP message that
       passes the CMTP validation checks, it includes, in its CMTP ACK, an
       appropriate VGP 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 VGP negative
       acknowledgement is contained in the left-most 8 bits of the INFORM
       field.  Negative acknowledgements associated with VGP include the
       following types:

       1.  Unrecognized VGP message type.  Numeric identifier for the
           unrecognized message type (8 bits).

       2.  Out-of-date VGP message.

       3.  Unrecognized virtual gateway source.  Numeric identifier for the
           unrecognized virtual gateway including the adjacent domain
           identifier (16 bits) and the local identifier (8 bits).

    Steenstrup                                                     [Page 46]

    RFC 1479                     IDPR Protocol                     July 1993

    4.  Routing Information Distribution

       Each domain participating in IDPR generates and distributes its
       routing information messages to route servers throughout an
       internetwork.  IDPR routing information messages contain information
       about the transit policies in effect across the given domain and the
       virtual gateway connectivity to adjacent domains.  Route servers in
       turn use IDPR routing information to generate policy routes between
       source and destination domains.

       There are three different procedures for distributing IDPR routing
       information:

       - The flooding protocol.  In this case, a representative policy
         gateway in each domain floods its routing information messages to
         route servers in all other domains.

       - Remote route server communication.  In this case, a route server
         distributes its domain's routing information messages to route
         servers in specific destination domains, by encapsulating these
         messages within IDPR data messages.  Thus, a domain administrator
         may control the distribution of the domain's routing information by
         restricting routing information exchange with remote route servers.
         Currently, routing information distribution restrictions are not
         included in IDPR configuration information.

       - The route server query protocol.  In this case, a policy gateway or
         route server requests routing information from another route
         server, which in turn responds with routing information from its
         database.  The route server query protocol may be used for quickly
         updating the routing information maintained by a policy gateway
         or route server that has just been connected or reconnected to an
         internetwork.  It may also be used to retrieve routing information
         from domains that restrict distribution of their routing
         information.

       In this section, we describe the flooding protocol only.  In section
       5, we describe the route server query protocol, and in section 5.2,
       we describe communication between route servers in separate domains.

       Policy gateways and route servers use CMTP for reliable transport of
       IDPR routing information messages flooded between peer, neighbor, and
       adjacent policy gateways and between those policy gateways and route
       servers.  The issuing policy gateway must communicate to CMTP the
       maximum number of transmissions per routing information message,
       flood_ret, and the interval between routing information message
       retransmissions, flood_int microseconds.  The recipient policy
       gateway or route server must determine routing information message

    Steenstrup                                                     [Page 47]

    RFC 1479                     IDPR Protocol                     July 1993

       acceptability, as we describe in section 4.2.3 below.

    4.1.  AD Representatives

       We designate a single policy gateway, the "AD representative", for
       generating and distributing IDPR routing information about its
       domain, to ensure that the routing information distributed is
       consistent and unambiguous and to minimize the communication required
       for routing information distribution.  There is usually only a single
       AD representative per domain, namely the lowest-numbered operational
       policy gateway in the domain.  Within a domain, policy gateways need
       no explicit election procedure to determine the AD representative.
       Instead, all members of a set of policy gateways mutually reachable
       via intra-domain routes can agree on set membership and therefore on
       which member has the lowest number.

       A partitioned domain has as many AD representatives as it does domain
       components.  In fact, the numeric identifier for an AD representative
       is identical to the numeric identifier for a domain component.  One
       cannot normally predict when and where a domain partition will occur,
       and thus any policy gateway within a domain may become an AD
       representative at any time.  To prepare for the role of AD
       representative in the event of a domain partition, every policy
       gateway must continually monitor its domain's IDPR routing
       information, through VGP and through the intra-domain routing
       procedure.

    4.2.  Flooding Protocol

       An AD representative policy gateway uses unrestricted flooding among
       all domains to distribute its domain's IDPR routing information
       messages to route servers in an internetwork.  There are two kinds of
       IDPR routing information messages issued by each AD representative:
       CONFIGURATION and DYNAMIC messages.  Each CONFIGURATION message
       contains the transit policy information configured by the domain
       administrator, including for each transit policy, its identifier, its
       specification, and the sets of virtual gateways configured as
       mutually reachable via intra-domain routes supporting the given
       transit policy.  Each DYNAMIC message contains information about
       current virtual gateway connectivity to adjacent domains and about
       the sets of virtual gateways currently mutually reachable via intra-
       domain routes supporting the configured transit policies.

       The IDPR Flooding Protocol is similar to the flooding procedures
       described in [9]-[11].  Through flooding, the AD representative
       distributes its routing information messages to route servers in its
       own domain and in adjacent domains.  After generating a routing
       information message, the AD representative distributes a copy to each

    Steenstrup                                                     [Page 48]

    RFC 1479                     IDPR Protocol                     July 1993

       of its peers and to a selected VG representative (see section 3.1.4)
       in all other virtual gateways connected to the domain.  Each VG
       representative in turn distributes a copy of the routing information
       message to each of its peers.  We note that distribution of routing
       information messages among virtual gateways and among peers within a
       virtual gateway is identical to distribution of inter-VG messages in
       VGP, as described in section 3.1.3.

       Within a virtual gateway, each policy gateway distributes a copy of
       the routing information message:

       - To each route server in its configured set of route servers.  A
         domain administrator should ensure that each route server not
         contained within a policy gateway appears in the set of configured
         route servers for at least two distinct policy gateways.  Hence,
         such a route server will continue to receive routing information
         messages, even when one of the policy gateways becomes unreachable.
         However, the route server will normally receive duplicate copies of
         a routing information message.

       - To certain directly-connected adjacent policy gateways.  A policy
         gateway distributes a routing information message to a
         directly-connected adjacent policy gateway in an adjacent domain
         component, only when it is the lowest-numbered operational peer
         with a direct connection to the given domain component.  We note
         that each policy gateway knows, through information provided by
         VGP, which peers have direct connections to which components of
         the adjacent domain.  If the policy gateway has direct connections
         to more than one adjacent policy gateway in that domain component,
         it selects the routing information message recipient according to
         the order in which the adjacent policy gateways appear in its
         database, choosing the first one encountered.  This selection
         procedure ensures that a copy of the routing information message
         reaches each component of the adjacent domain, while limiting the
         number of copies distributed.

       Once a routing information message reaches an adjacent policy
       gateway, that policy gateway distributes copies of the message
       throughout its domain.  The adjacent policy gateway, acting as the
       first recipient of the routing information message in its domain,
       follows the same message distribution procedure as the AD
       representative in the source domain, as described above.  The
       flooding procedure terminates when all reachable route servers in an
       internetwork receive a copy of the routing information message.

       Neighbor policy gateways may receive copies of the same routing
       information message from different adjoining domains.  If two
       neighbor policy gateways receive the message copies simultaneously,

    Steenstrup                                                     [Page 49]

    RFC 1479                     IDPR Protocol                     July 1993

       they will distribute them to VG representatives in other virtual
       gateways within their domain, resulting in duplicate message
       distribution.  However, each policy gateway stops the spread of
       duplicate routing information messages as soon as it detects them, as
       described in section 4.2.3 below.  In the Internet, we expect
       simultaneous message receptions to be the exception rather than the
       rule, given the hierarchical structure of the current topology.

    4.2.1.  Message Generation

       An AD representative generates and distributes a CONFIGURATION
       message whenever there is a configuration change in a transit policy
       or virtual gateway associated with its domain.  This ensures that
       route servers maintain an up-to-date view of a domain's configured
       transit policies and adjacencies.  An AD representative may also
       distribute a CONFIGURATION message at a configurable period of
       conf_per (500) hours.  A CONFIGURATION message contains, for each
       configured transit policy, the identifier assigned by the domain
       administrator, the specification, and the set of associated "virtual
       gateway groups".  Each virtual gateway group comprises virtual
       gateways configured to be mutually reachable via intra-domain routes
       of the given transit policy.  Accompanying each virtual gateway
       listed is an indication of whether the virtual gateway is configured
       to be a domain entry point, a domain exit point, or both according to
       the given transit policy.  The CONFIGURATION message also contains
       the set of local route servers that the domain administrator has
       configured to be available to IDPR clients in other domains.

       An AD representative generates and distributes a DYNAMIC message
       whenever there is a change in currently supported transit policies or
       in current virtual gateway connectivity associated with its domain.
       This ensures that route servers maintain an up-to-date view of a
       domain's supported transit policies and existing adjacencies and how
       they differ from those configured for the domain.  Specifically, an
       AD representative generates a DYNAMIC message whenever there is a
       change in the connectivity, through the given domain and with respect
       to a configured transit policy, between two components of adjoining
       domains.  An AD representative may also distribute a DYNAMIC message
       at a configurable period of dyn_per (24) hours.  A DYNAMIC message
       contains, for each configured transit policy, its identifier,
       associated virtual gateway groups, and domain components reachable
       through virtual gateways in each group.  Each DYNAMIC message also
       contains the set of currently "unavailable", either down or
       unreachable, virtual gateways in the domain.

       We note that each virtual gateway group expressed in a DYNAMIC
       message may be a proper subset of one of the corresponding virtual
       gateway groups expressed in a CONFIGURATION message.  For example,

    Steenstrup                                                     [Page 50]

    RFC 1479                     IDPR Protocol                     July 1993

       suppose that, for a given domain, the virtual gateway group (VG
       A,...,VG E) were configured for a transit policy such that each
       virtual gateway was both a domain entry and exit point.  Thus, all
       virtual gateways in this group are configured to be mutually
       reachable via intra-domain routes of the given transit policy.  Now
       suppose that VG E becomes unreachable because of a power failure and
       furthermore that the remaining virtual gateways form two distinct
       groups, (VG A,VG B) and (VG C,VG D), such that although virtual
       gateways in both groups are still mutually reachable via some intra-
       domain routes they are no longer mutually reachable via any intra-
       domain routes of the given transit policy.  In this case, the virtual
       gateway groups for the given transit policy now become (VG A,VG B)
       and (VG C,VG D); VG E is listed as an unavailable virtual gateway.

       A route server uses information about the set of unavailable virtual
       gateways to determine which of its routes are no longer viable, and
       it subsequently removes such routes from its route database.
       Although route servers could determine the set of unavailable virtual
       gateways using information about configured virtual gateways and
       currently reachable virtual gateways, the associated processing cost
       is high.  In particular, a route server would have to examine all
       virtual gateway groups listed in a DYNAMIC message to determine
       whether there are any unavailable virtual gateways in the given
       domain.  To reduce the message processing at each route server, we
       have chosen to include the set of unavailable virtual gateways in
       each DYNAMIC message.

       In order to construct a DYNAMIC message, an AD representative
       assembles information gathered from intra-domain routing and from
       VGP.  Specifically, the AD representative uses the following
       information:

       - VG CONNECT and UP/DOWN messages to determine the state, up or down,
         of each of its domain's virtual gateways and the adjacent domain
         components reachable through a given virtual gateway.

       - Intra-domain routing information to determine, for each of its
         domain's transit policies, whether a given virtual gateway in the
         domain is reachable with respect to that transit policy.

       - VG POLICY messages to determine the connectivity of adjoining
         domain components, across the given domain and with respect to a
         configured transit policy, such that these components are adjacent
         to virtual gateways not currently reachable from the AD
         representative's virtual gateway according to the given transit
         policy.

    Steenstrup                                                     [Page 51]

    RFC 1479                     IDPR Protocol                     July 1993

    4.2.2.  Sequence Numbers

       Each IDPR routing information message carries a sequence number
       which, when used in conjunction with the timestamp carried in the
       CMTP message header, determines the recency of the message.  An AD
       representative assigns a sequence number to each routing information
       message it generates, depending upon its internal clock time:

       - The AD representative sets the sequence number to 0, if its
         internal clock time is greater than the timestamp in its previously
         generated routing information message.

       - The AD representative sets the sequence number to 1 greater than
         the sequence number in its previously generated routing information
         message, if its internal clock time equals the timestamp for its
         previously generated routing information message and if the
         previous sequence number is less than the maximum value
         (currently 2**16 - 1).  If the previous sequence number equals the
         maximum value, the AD representative waits until its internal clock
         time exceeds the timestamp in its previously generated routing
         information message and then sets the sequence number to 0.

       In general, we do not expect generation of multiple distinct IDPR
       routing information messages carrying identical timestamps, and so
       the sequence number may seem superfluous.  However, the sequence
       number may become necessary during synchronization of an AD
       representative's internal clock.  In particular, the AD
       representative may need to freeze the clock value during
       synchronization, and thus distinct sequence numbers serve to
       distinguish routing information messages generated during the clock
       synchronization interval.

    4.2.3.  Message Acceptance

       Prior to a policy gateway forwarding a routing information message or
       a route server incorporating routing information into its routing
       information database, the policy gateway or route server assesses
       routing information message acceptability.  An IDPR routing
       information message is "acceptable" if:

       - It passes the CMTP validation checks.

       - Its timestamp is less than conf_old (530) hours behind the
         recipient's internal clock time for CONFIGURATION messages and less
         than dyn_old (25) hours behind the recipient's internal clock time
         for DYNAMIC messages.

       - Its timestamp and sequence number indicate that it is more recent

    Steenstrup                                                     [Page 52]

    RFC 1479                     IDPR Protocol                     July 1993

         than the currently-stored routing information from the given
         domain.  If there is no routing information currently stored from
         the given domain, then the routing information message contains, by
         default, the more recent information.

       Policy gateways acknowledge and forward acceptable IDPR routing
       information messages, according to the flooding protocol described in
       section 4.2 above.  Moreover, each policy gateway retains the
       timestamp and sequence number for the most recently accepted routing
       information message from each domain and uses these values to
       determine acceptability of routing information messages received in
       the future.  Route servers acknowledge the receipt of acceptable
       routing information messages and incorporate the contents of these
       messages into their routing information databases, contingent upon
       criteria discussed in section 4.2.4 below; however, they do not
       participate in the flooding protocol.  We note that when a policy
       gateway or route server first returns to service, it immediately
       updates its routing information database with routing information
       obtained from another route server, using the route server query
       protocol described in section 5.

       An AD representative takes special action upon receiving an
       acceptable routing information message, supposedly generated by
       itself but originally obtained from a policy gateway or route server
       other than itself.  There are at least three possible reasons for the
       occurrence of this event:

       - The routing information message has been corrupted in a way that is
         not detectable by the integrity/authentication value.

       - The AD representative has experienced a memory error.

       - Some other entity is generating routing information messages on
         behalf of the AD representative.

       In any case, the AD representative logs the event for network
       management.  Moreover, the AD representative must reestablish its own
       routing information messages as the most recent for its domain.  To
       do so, the AD representative waits until its internal clock time
       exceeds the value of the timestamp in the received routing
       information message and then generates a new routing information
       message using the currently-stored domain routing information
       supplied by VGP and by the intra-domain routing procedure.  Note that
       the length of time the AD representative must wait to generate the
       new message is at most cmtp_new (300) seconds, the maximum CMTP-
       tolerated difference between the received message's timestamp and the
       AD representative's internal clock time.

    Steenstrup                                                     [Page 53]

    RFC 1479                     IDPR Protocol                     July 1993

       IDPR routing information messages that pass the CMTP validity checks
       but appear less recent than stored routing information are
       unacceptable.  Policy gateways do not forward unacceptable routing
       information messages, and route servers do not incorporate the
       contents of unacceptable routing information messages into their
       routing information databases.  Instead, the recipient of an
       unacceptable routing information message acknowledges the message in
       one of two ways:

       - If the routing information message timestamp and sequence number
         equal to the timestamp and sequence number associated with the
         stored routing information for the given domain, the recipient
         assumes that the routing information message is a duplicate and
         acknowledges the message.

       - If the routing information message timestamp and sequence number
         indicate that the message is less recent than the stored routing
         information for the domain, the recipient acknowledges the message
         with an indication that the routing information it contains is
         out-of-date.  Such a negative acknowledgement is a signal to the
         sender of the routing information message to request more up-to-
         date routing information from a route server, using the route
         server query protocol.  Furthermore, if the recipient of the out-
         of-date routing information message is a route server, it
         regenerates a routing information message from its own routing
         information database and forwards the message to the sender.  The
         sender may in turn propagate this more recent routing information
         message to other policy gateways and route servers.

    4.2.4.  Message Incorporation

       A route server usually stores the entire contents of an acceptable
       IDPR routing information message in its routing information database,
       so that it has access to all advertised transit policies when
       generating a route and so that it can regenerate routing information
       messages at a later point in time if requested to do so by another
       route server or policy gateway.  However, a route server may elect
       not to store all routing information message contents.  In
       particular, the route server need not store any transit policy that
       excludes the route server's domain as a source or any routing
       information from a domain that the route server's domain's source
       policies exclude for transit.  Selective storing of routing
       information message contents simplifies the route generation
       procedure since it reduces the search space of possible routes, and
       it limits the amount of route server memory devoted to routing
       information.  However, selective storing of routing information also
       means that the route server cannot always regenerate the original
       routing information message, if requested to do so by another route

    Steenstrup                                                     [Page 54]

    RFC 1479                     IDPR Protocol                     July 1993

       server or policy gateway.

       An acceptable IDPR routing information message may contain transit
       policy information that is not well-defined according to the route
       server's perception.  A CONFIGURATION message may contain an
       unrecognized domain, virtual gateway, or transit policy attribute,
       such as user class access restrictions or offered service.  In this
       case, "unrecognized" means that the value in the routing information
       message is not listed in the route server's configuration database,
       as described previously in section 1.8.2.  A DYNAMIC message may
       contain an unrecognized transit policy or virtual gateway.  In this
       case, "unrecognized" means that the transit policy or virtual gateway
       was not listed in the most recent CONFIGURATION message for the given
       domain.

       Each route server can always parse an acceptable routing information
       messsage, even if some of the information is not well-defined, and
       thus can always use the information that it does recognize.
       Therefore, a route server can store the contents of acceptable
       routing information messages from domains in which it is interested,
       regardless of whether all contents appear to be well-defined at
       present.  If a routing message contains unrecognized information, the
       route server may attempt to obtain the additional information it
       needs to decipher the unrecognized information.  For a CONFIGURATION
       message, the route server logs the event for network management; for
       a DYNAMIC message, the route server requests, from another route
       server, the most recent CONFIGURATION message for the domain in
       question.

       When a domain is partitioned, each domain component has its own AD
       representative, which generates routing information messages on
       behalf of that component.  Discovery of a domain partition prompts
       the AD representative for each domain component to generate and
       distribute a DYNAMIC message.  In this case, a route server receives
       and stores more than one routing information message at a time for
       the given domain, namely one for each domain component.

       When the partition heals, the AD representative for the entire domain
       generates and distributes a DYNAMIC message.  In each route server's
       routing information database, the new DYNAMIC message does not
       automatically replace all of the currently-stored DYNAMIC messages
       for the given domain.  Instead, the new message only replaces that
       message whose AD representative matches the AD representative for the
       new message.  The other DYNAMIC messages, generated during the period
       over which the partition occurred, remain in the routing information
       database until they attain their maximum lifetime, as described in
       section 4.2.5 below.  Such stale information may lead to the
       generation of routes that result in path setup failures and hence the

    Steenstrup                                                     [Page 55]

    RFC 1479                     IDPR Protocol                     July 1993

       selection of alternative routes.  To reduce the chances of path setup
       failures, we will investigate, for a future version of IDPR,
       mechanisms for removing partition-related DYNAMIC messages
       immediately after a partition disappears.

    4.2.5.  Routing Information Database

       We expect that most of the IDPR routing information stored in a
       routing information database will remain viable for long periods of
       time, perhaps until a domain reconfiguration occurs.  By "viable", we
       mean that the information reflects the current state of the domain
       and hence may be used successfully for generating policy routes.  To
       reduce the probability of retaining stale routing information, a
       route server imposes a maximum lifetime on each database entry,
       initialized when it incorporates an accepted entry into its routing
       information database.  The maximum lifetime should be longer than the
       corresponding message generation period, so that the database entry
       is likely to be refreshed before it attains its maximum lifetime.

       Each CONFIGURATION message stored in the routing information database
       has a maximum lifetime of conf_old (530) hours; each DYNAMIC message
       stored in the routing information database has a maximum lifetime of
       dyn_old (25) hours.  Periodic generation of routing information
       messages makes it unlikely that any routing information message will
       remain in a routing information database for its full lifetime.
       However, a routing information message may attain its maximum
       lifetime in a route server that is separated from a internetwork for
       a long period of time.

       When an IDPR routing information message attains its maximum lifetime
       in a routing information database, the route server removes the
       message contents from its database, so that it will not generate new
       routes with the outdated routing information nor distribute old
       routing information in response to requests from other route servers
       or policy gateways.  Nevertheless, the route server continues to
       dispense routes previously generated with the old routing
       information, as long as path setup (see section 7) for these routes
       succeeds.

       The route server treats routing information message lifetime
       expiration differently, depending on the type of routing information
       message.  When a CONFIGURATION message expires, the route server
       requests, from another route server, the most recent CONFIGURATION
       message issued for the given domain.  When a DYNAMIC message expires,
       the route server does not initially attempt to obtain more recent
       routing information.  Instead, if route generation is necessary, the
       route server uses the routing information contained in the
       corresponding CONFIGURATION message for the given domain.  Only if

    Steenstrup                                                     [Page 56]

    RFC 1479                     IDPR Protocol                     July 1993

       there is a path setup failure (see section 7.4) involving the given
       domain does the route server request, from another route server, the
       most recent DYNAMIC message issued for the given domain.

    4.3.  Routing Information Message Formats

       The flooding protocol number is equal to 1.  We describe the contents
       of each type of routing information message below.

    4.3.1.  CONFIGURATION

       The CONFIGURATION message type is equal to 0.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            AD CMP             |              SEQ              |
       +-------------------------------+-------------------------------+
       |            NUM TP             |            NUM RS             |
       +-------------------------------+-------------------------------+
       |              RS               |
       +-------------------------------+
       For each transit policy configured for the domain:
       +-------------------------------+-------------------------------+
       |              TP               |            NUM ATR            |
       +-------------------------------+-------------------------------+
       For each attribute of the transit policy:
       +-------------------------------+-------------------------------+
       |            ATR TYP            |            ATR LEN            |
       +-------------------------------+-------------------------------+
       For the source/destination access restrictions attribute:
       +-------------------------------+
       |          NUM AD GRP           |
       +-------------------------------+
       For each domain group in the source/destination access restrictions:
       +-------------------------------+-------------------------------+
       |            NUM AD             |              AD               |
       +---------------+---------------+-------------------------------+
       |    AD FLGS    |    NUM HST    |            HST SET            |
       +---------------+---------------+-------------------------------+
       For the temporal access restrictions attribute:
       +-------------------------------+
       |            NUM TIM            |
       +-------------------------------+

    Steenstrup                                                     [Page 57]

    RFC 1479                     IDPR Protocol                     July 1993

       For each set of times in the temporal access restrictions:
       +---------------+-----------------------------------------------+
       |   TIM FLGS    |                   DURATION                    |
       +---------------+-----------------------------------------------+
       |                             START                             |
       +-------------------------------+-------------------------------+
       |            PERIOD             |            ACTIVE             |
       +-------------------------------+-------------------------------+
       For the user class access restrictions attribute:
       +-------------------------------+
       |            NUM UCI            |
       +-------------------------------+
       For each UCI in the user class access restrictions:
       +---------------+
       |      UCI      |
       +---------------+
       For each offered service attribute:
       +---------------------------------------------------------------+
       |                            OFR SRV                            |
       +---------------------------------------------------------------+
       For the virtual gateway access restrictions attribute:
       +-------------------------------+
       |           NUM VG GRP          |
       +-------------------------------+
       For each virtual gateway group in the virtual gateway access
       restrictions:
       +-------------------------------+-------------------------------+
       |            NUM VG             |            ADJ AD             |
       +---------------+---------------+-------------------------------+
       |      VG       |    VG FLGS    |
       +---------------+---------------+

       AD CMP
            (16 bits) Numeric identifier for the domain component containing
            the AD representative policy gateway.

       SEQ (16 bits) Routing information message sequence number.

       NUM TP (16 bits) Number of transit policy specifications contained in
            the routing information message.

       NUM RS (16 bits) Number of route servers advertised to serve clients
            outside of the domain.

       RS (16 bits) Numeric identifier for a route server.

       TP (16 bits) Numeric identifier for a transit policy specification.

    Steenstrup                                                     [Page 58]

    RFC 1479                     IDPR Protocol                     July 1993

       NUM ATR (16 bits) Number of attributes associated with the transit
            policy.

       ATR TYP (16 bits) Numeric identifier for a type of attribute.  Valid
            attributes include the following types:

       - Set of  virtual  gateway access restrictions   (see  section 1.4.2)
         associated with the transit policy (variable).  This attribute must
         be included.

       - Set of source/destination access restrictions (see section 1.4.2)
         associated with the transit policy (variable).  This attribute may
         be omitted.  Absence of this attribute implies that traffic from
         any source to any destination is acceptable.

       - Set of temporal access restrictions (see section 1.4.2) associated
         with the transit policy (variable).  This attribute may be omitted.
         Absence of this attribute implies that the transit policy applies
         at all times.

       - Set of user class access restrictions (see section 1.4.2)
         associated with the transit policy (variable).  This attribute may
         be omitted.  Absence of this attribute implies that traffic from
         any user class is acceptable.

       - Average delay in milliseconds (16 bits).  This attribute may be
         omitted.

       - Delay variation in milliseconds (16 bits).  This attribute may be
         omitted.

       - Average available bandwidth in bits per second (48 bits).  This
         attribute may be omitted.

       - Available bandwidth variation in bits per second (48 bits).  This
         attribute may be omitted.

       - MTU in bytes (16 bits).  This attribute may be omitted.

       - Charge per byte in thousandths of a cent (16 bits). This attribute
         may be omitted.

       - Charge per message in thousandths of a cent (16 bits).  This
         attribute may be omitted.

       - Charge for session time in thousandths of a cent per second (16
         bits).  This attribute may be omitted.  Absence of any charge
         attribute implies that the domain provides free transit service.

    Steenstrup                                                     [Page 59]

    RFC 1479                     IDPR Protocol                     July 1993

       ATR LEN (16 bits) Length of an attribute in bytes, beginning with the
       subsequent field.

       NUM AD GRP (16 bits) Number of source/destination domain groups (see
       section 1.4.2) associated with the source/destination access
       restrictions.

       NUM AD (16 bits) Number of domains or sets of domains in a domain
       group.

       AD (16 bits) Numeric identifier for a domain or domain set.

       AD FLGS (8 bits) Set of five flags indicating how to interpret the AD
       field, contained in the right-most bits.  Proceeding left to right,
       the first flag indicates whether the transit policy applies to all
       domains or to specific domains (1 all, 0 specific), and when set to
       1, causes the second and third flags to be ignored.  The second flag
       indicates whether the domain identifier signifies a single domain or
       a domain set (1 single, 0 set).  The third flag indicates whether the
       transit policy applies to the given domain or domain set (1 applies,
       0 does not apply) and is used for representing complements of sets of
       domains.  The fourth flag indicates whether the domain is a source (1
       source, 0 not source).  The fifth flag indicates whether the domain
       is a destination (1 destination, 0 not destination).  At least one of
       the fourth and fifth flags must be set to 1.

       NUM HST (8 bits) Number of "host sets" (see section 1.4.2) associated
       with a particular domain or domain set.  The value 0 indicates that
       all hosts in the given domain or domain set are acceptable sources or
       destinations, as specified by the fourth and fifth AD flags.

       HST SET (16 bits) Numeric identifier for a host set.

       NUM TIM (16 bits) Number of time specifications associated with the
       temporal access restrictions.  Each time specification is split into
       a set of continguous identical periods, as we describe below.

       TIM FLGS (8 bits) Set of two flags indicating how to combine the time
       specifications, contained in the right-most bits.  Proceeding left to
       right, the first flag indicates whether the transit policy applies
       during the periods specified in the time specification (1 applies, 0
       does not apply) and is used for representing complements of policy
       applicability intervals.  The second flag indicates whether the time
       specification takes precedence over the previous time specifications
       listed (1 precedence, 0 no precedence).  Precedence is equivalent to
       the boolean OR and AND operators, in the following sense.  At any
       given instant, a transit policy either applies or does not apply,
       according to a given time specification, and we can assign a boolean

    Steenstrup                                                     [Page 60]

    RFC 1479                     IDPR Protocol                     July 1993

       value to the state of policy applicability according to a given time
       specification.  If the second flag assumes the value 1 for a given
       time specification, that indicates the boolean operator OR should be
       applied to the values of policy applicability, according to the given
       time specification and to all previously listed time specifications.
       If the second flag assumes the value 0 for a given time
       specification, that indicates the boolean operator AND should be
       applied to the values of policy applicability, according to the given
       time specification and to all previously listed time specifications.

       DURATION (24 bits) Length of the time specification duration, in
       minutes.  A value of 0 indicates an infinite duration.

       START (32 bits) Time at which the time specification first takes
       effect, in seconds elapsed since 1 January 1970 0:00 GMT.

       PERIOD (16 bits) Length of each time period within the time
       specification, in minutes.

       ACTIVE (16 bits) Length of the policy applicable interval during each
       time period, in minutes from the beginning of the time period.

       NUM UCI (16 bits) Number of user classes associated with the user
       class access restrictions.

       UCI (8 bits) Numeric identifier for a user class.

       NUM VG GRP (16 bits) Number of virtual gateway groups (see section
       1.4.2) associated with the virtual gateway access restrictions.

       NUM VG (16 bits) Number of virtual gateways in a virtual gateway
       group.

       ADJ AD (16 bits) Numeric identifier for the adjacent domain to which
       a virtual gateway connects.

       VG (8 bits) Numeric identifier for a virtual gateway.

       VG FLGS (8 bits) Set of two flags indicating how to interpret the VG
       field, contained in the right-most bits.  Proceeding left to right,
       the first flag indicates whether the virtual gateway is a domain
       entry point (1 entry, 0 not entry).  The second flag indicates
       whether the virtual gateway is a domain exit point (1 exit, 0 not
       exit).  At least one of the first and second flags must be set to 1.

    Steenstrup                                                     [Page 61]

    RFC 1479                     IDPR Protocol                     July 1993

    4.3.2.  DYNAMIC

       The DYNAMIC 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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            AD CMP             |              SEQ              |
       +-------------------------------+-------------------------------+
       |           UNAVL VG            |            NUM PS             |
       +-------------------------------+-------------------------------+
       For each unavailable virtual gateway in the domain:
       +-------------------------------+---------------+---------------+
       |            ADJ AD             |      VG       |    UNUSED     |
       +-------------------------------+---------------+---------------+
       For each set of transit policies for the domain:
       +-------------------------------+-------------------------------+
       |            NUM TP             |          NUM VG GRP           |
       +-------------------------------+-------------------------------+
       |              TP               |
       +-------------------------------+
       For each virtual gateway group associated with the transit policy
       set:
       +-------------------------------+-------------------------------+
       |            NUM VG             |            ADJ AD             |
       +---------------+---------------+-------------------------------+
       |      VG       |    VG FLGS    |            NUM CMP            |
       +---------------+---------------+-------------------------------+
       |            ADJ CMP            |
       +-------------------------------+

       AD CMP
            (16 bits) Numeric identifier for the domain component containing
            the AD representative policy gateway.

       SEQ (16 bits) Routing information message sequence number.

       UNAVL VG (16 bits) Number of virtual gateways in the domain component
            that are currently unavailable via any intra-domain routes.

       NUM PS (16 bits) Number of sets of transit policies listed.  Transit
            policy sets provide a mechanism for reducing the size of DYNAMIC
            messages.  A single set of virtual gateway groups applies to all
            transit policies in a given set.

       ADJ AD (16 bits) Numeric identifier for the adjacent domain to which
            a virtual gateway connects.

    Steenstrup                                                     [Page 62]

    RFC 1479                     IDPR Protocol                     July 1993

       VG (8 bits) Numeric identifier for a virtual gateway.

       UNUSED (8 bits) Not currently used; must be set equal to 0.

       NUM TP (16 bits) Number of transit policies in a set.

       NUM VGGRP (16 bits) Number of virtual gateway groups currently
            associated with the transit policy set.

       TP (16 bits) Numeric identifier for a transit policy.

       NUM VG (16 bits) Number of virtual gateways in a virtual gateway
            group.

       VG FLGS (8 bits) Set of two flags indicating how to interpret the VG
            field, contained in the right-most bits.  Proceeding left to
            right, the first flag indicates whether the virtual gateway is a
            domain entry point (1 entry, 0 not entry).  The second flag
            indicates whether the virtual gateway is a domain exit point (1
            exit, 0 not exit).  At least one of the first and second flags
            must be set to 1.

       NUM CMP (16 bits) Number of adjacent domain components reachable via
            direct connections through the virtual gateway.

       ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
            component.

    4.3.3.  Negative Acknowledgements

       When a policy gateway or route server receives an unacceptable IDPR
       routing information 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 routing information message negative
       acknowledgement is contained in the left-most 8 bits of the INFORM
       field.  Negative acknowledgements associated with routing information
       messages include the following types:

       1.  Unrecognized IDPR routing information message type.  Numeric
           identifier for the unrecognized message type (8 bits).

       2.  Out-of-date IDPR routing information message.  This is a signal
           to the sender that it may not have the most recent routing
           information for the given domain.

    Steenstrup                                                     [Page 63]

    RFC 1479                     IDPR Protocol                     July 1993

    5.  Route Server Query Protocol

       Each route server is responsible for maintaining both the routing
       information database and the route database and for responding to
       database information requests from policy gateways and other route
       servers.  These requests and their responses are the messages
       exchanged via the Route Server Query Protocol (RSQP).

       Policy gateways and route servers normally invoke RSQP to replace
       absent, outdated, or corrupted information in their own routing
       information or route databases.  In section 4, we discussed some of
       the situations in which RSQP may be invoked; in this section and in
       section 7, we discuss other such situations.

    5.1.  Message Exchange

       Policy gateways and route servers use CMTP for reliable transport of
       route server requests and responses.  RSQP must communicate to CMTP
       the maximum number of transmissions per request/response message,
       rsqp_ret, and the interval between request/response message
       retransmissions, rsqp_int microseconds.  A route server
       request/response message is "acceptable" if:

       - It passes the CMTP validation checks.

       - Its timestamp is less than rsqp_old (300) seconds behind the
         recipient's internal clock time.

       With RSQP, a requesting entity expects to receive an acknowledgement
       from the queried route server indicating whether the route server can
       accommodate the request.  The route server may fail to fill a given
       request for either of the following reasons:

       - Its corresponding database contains no entry or only a partial
         entry for the requested information.

       - It is governed by special message distribution rules, imposed by
         the domain administrator, that preclude it from releasing the
         requested information.  Currently, such distribution rules are not
         included in IDPR configuration information.

       For all requests that it cannot fill, the route server responds with
       a negative acknowledgement message carried in a CMTP acknowledgement,
       indicating the set of unfulfilled requests (see section 5.5.4).

       If the requesting entity either receives a negative acknowledgement
       or does not receive any acknowledgement after rsqp_ret attempts
       directed at the same route server, it queries a different route

    Steenstrup                                                     [Page 64]

    RFC 1479                     IDPR Protocol                     July 1993

       server, as long as the number of attempted requests to different
       route servers does not exceed rsqp_try (3).  Specifically, the
       requesting entity proceeds in round-robin order through its list of
       addressable route servers.  However, if the requesting entity is
       unsuccessful after rsqp_try attempts, it abandons the request
       altogether and logs the event for network management.

       A policy gateway or a route server can request information from any
       route server that it can address.  Addresses for local route servers
       within a domain are part of the configuration for each IDPR entity
       within a domain; addresses for remote route servers in other domains
       are obtained through flooded CONFIGURATION messages, as described
       previously in section 4.2.1.  However, requesting entities always
       query local route servers before remote route servers, in order to
       contain the costs associated with the query and response.  If the
       requesting entity and the queried route server are in the same
       domain, they can communicate over intra-domain routes, whereas if the
       requesting entity and the queried route server are in different
       domains, they must obtain a policy route and establish a path before
       they can communicate, as we describe below.

    5.2.  Remote Route Server Communication

       RSQP communication involving a remote route server requires a policy
       route and accompanying path setup (see section 7) between the
       requesting and queried entities, as these entities reside in
       different domains.  After generating a request message, the
       requesting entity hands to CMTP its request message along with the
       remote route server's entity and domain identifiers.  CMTP encloses
       the request in a DATAGRAM and hands the DATAGRAM and remote route
       server information to the path agent.  Using the remote route server
       information, the path agent obtains, and if necessary sets up, a path
       to the remote route server.  Once the path to the remote route server
       has been successfully established, the path agent encapsulates the
       DATAGRAM within an IDPR data message and forwards the data message
       along the designated path.

       When the path agent in the remote route server receives the IDPR data
       message, it extracts the DATAGRAM and hands it to CMTP.  In addition,
       the path agent, using the requesting entity and domain identifiers
       contained in the path identifier, obtains, and if necessary sets up,
       a path back to the requesting entity.

       If the DATAGRAM fails any of the CMTP validation checks, CMTP returns
       a NAK to the requesting entity.  If the DATAGRAM passes all of the
       CMTP validation checks, the remote route server assesses the
       acceptability of the request message.  Provided the request message
       is acceptable, the remote route server determines whether it can

    Steenstrup                                                     [Page 65]

    RFC 1479                     IDPR Protocol                     July 1993

       fulfill the request and directs CMTP to return an ACK to the
       requesting entity.  The ACK may contain a negative acknowledgement if
       the entire request cannot be fulfilled.

       The remote route server generates responses for all requests that it
       can fulfill and returns the responses to the requesting entity.
       Specifically, the remote route server hands to CMTP its response and
       the requesting entity information.  CMTP in turn encloses the
       response in a DATAGRAM.

       When returning an ACK, a NAK, or a response to the requesting entity,
       the remote route server hands the corresponding CMTP message and
       requesting entity information to the path agent.  Using the
       requesting entity information, the path agent retrieves the path to
       the requesting entity, encapsulates the CMTP message within an IDPR
       data message, and forwards the data message along the designated
       path.

       When the path agent in the requesting entity receives the IDPR data
       message, it extracts the ACK, NAK, or response to its request and
       performs the CMTP validation checks for that message.  In the case of
       a response messsage, the requesting entity also assesses message
       acceptability before incorporating the contents into the appropriate
       database.

    5.3  Routing Information

       Policy gateways and route servers request routing information from
       route servers, in order to update their routing information
       databases.  To obtain routing information from a route server, the
       requesting entity issues a ROUTING INFORMATION REQUEST message
       containing the type of routing information requested - CONFIGURATION
       messages, DYNAMIC messages, or both - and the set of domains from
       which the routing information is requested.

       Upon receiving a ROUTING INFORMATION REQUEST message, a route server
       first assesses message acceptability before proceeding to act on the
       contents.  If the ROUTING INFORMATION REQUEST message is deemed
       acceptable, the route server determines how much of the request it
       can fulfill and then instructs CMTP to generate an acknowledgement,
       indicating its ability to fulfill the request.  The route server
       proceeds to fulfill as much of the request as possible by
       reconstructing individual routing information messages, one per
       requested message type and domain, from its routing information
       database.  We note that only a regenerated routing information
       message whose entire contents match that of the original routing
       information message may pass the CMTP integrity/authentication
       checks.

    Steenstrup                                                     [Page 66]

    RFC 1479                     IDPR Protocol                     July 1993

    5.4.  Routes

       Path agents request routes from route servers when they require
       policy routes for path setup.  To obtain routes from a route server,
       the requesting path agent issues a ROUTE REQUEST message containing
       the destination domain and applicable service requirements, the
       maximum number of routes requested, a directive indicating whether to
       generate the routes or retrieve them from the route database, and a
       directive indicating whether to refresh the routing information
       database with the most recent CONFIGURATION or DYNAMIC message from a
       given domain, before generating the routes.  To refresh its routing
       information database, a route server must obtain routing information
       from another route server.  The path agent usually issues routing
       information database refresh directives in response to a failed path
       setup.  We discuss the application of these directives in more detail
       in section 7.4.

       Upon receiving a ROUTE REQUEST message, a route server first assesses
       message acceptability before proceeding to act on the contents.  If
       the ROUTE REQUEST message is deemed acceptable, the route server
       determines whether it can fulfill the request and then instructs CMTP
       to generate an acknowledgement, indicating its ability to fulfill the
       request.  The route server proceeds to fulfill the request with
       policy routes, either retrieved from its route database or generated
       from its routing information database if necessary, and returns these
       routes in a ROUTE RESPONSE message.

    5.5.  Route Server Message Formats

       The route server query protocol number is equal to 2.  We describe
       the contents of each type of RSQP message below.

    5.5.1.  ROUTING INFORMATION REQUEST

       The ROUTING INFORMATION REQUEST message type is equal to 0.

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            QRY AD             |            QRY RS             |
       +-------------------------------+-------------------------------+
       |            NUM AD             |              AD               |
       +---------------+---------------+-------------------------------+
       |   RIM FLGS    |    UNUSED     |
       +---------------+---------------+

       QRY AD
            (16 bits) Numeric identifier for the domain containing the

    Steenstrup                                                     [Page 67]

    RFC 1479                     IDPR Protocol                     July 1993

            queried route server.

       QRY RS (16 bits) Numeric identifier for the queried route server.

       NUM AD (16 bits) Number of domains about which routing information is
            requested.  The value 0 indicates a request for routing
            information from all domains.

       AD (16 bits) Numeric identifier for a domain.  This field is absent
            when NUM AD equals 0.

       RIM FLGS (8 bits) Set of two flags indicating the type of routing
            information messages requested, contained in the right-most
            bits.  Proceeding left to right, the first flag indicates
            whether the request is for a CONFIGURATION message (1
            CONFIGURATION, 0 no CONFIGURATION).  The second flag indicates
            whether the request is for a DYNAMIC message (1 DYNAMIC, 0 no
            DYNAMIC).  At least one of the first and second flags must be
            set to 1.

       UNUSED (8 bits) Not currently used; must be set equal to 0.

    5.5.2.  ROUTE REQUEST

            The ROUTE REQUEST 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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            QRY AD             |            QRY RS             |
       +-------------------------------+-------------------------------+
       |            SRC AD             |            HST SET            |
       +---------------+---------------+-------------------------------+
       |      UCI      |    UNUSED     |            NUM RQS            |
       +---------------+---------------+-------------------------------+
       |            DST AD             |            PRX AD             |
       +---------------+---------------+-------------------------------+
       |    NUM RTS    |   GEN FLGS    |            RFS AD             |
       +---------------+---------------+-------------------------------+
       |            NUM AD             |
       +-------------------------------+
       For each domain to be favored, avoided, or excluded:
       +-------------------------------+---------------+---------------+
       |              AD               |    AD FLGS    |    UNUSED     |
       +-------------------------------+---------------+---------------+

    Steenstrup                                                     [Page 68]

    RFC 1479                     IDPR Protocol                     July 1993

       For each requested service:
       +-------------------------------+-------------------------------+
       |            RQS TYP            |            RQS LEN            |
       +-------------------------------+-------------------------------+
       |                            RQS SRV                            |
       +---------------------------------------------------------------+

       QRY AD
            (16 bits) Numeric identifier for the domain containing the
            queried route server.

       QRY RS (16 bits) Numeric identifier for the queried route server.

       SRC AD (16 bits) Numeric identifier for the route's source domain.

       HST SET (16 bits) Numeric identifier for the source's host set.

       UCI (8 bits) Numeric identifier for the source user class. The value
            0 indicates that there is no particular source user class.

       UNUSED (8 bits) Not currently used; must be set equal to 0.

       NUM RQS (16 bits) Number of requested services.  The value 0
            indicates that the source requests no special services.

       DST AD (16 bits) Numeric identifier for the route's destination
            domain.

       PRX AD (16 bits) Numeric identifier for the destination domain's
            proxy (see section 1.3.1).  If the destination domain provides
            the path agent function for its hosts, then the destination and
            proxy domains are identical.  A route server constructs routes
            between the source domain's proxy and the destination domain's
            proxy.  We note that the source domain's proxy is identical to
            the domain issuing the CMTP message containing the ROUTE REQUEST
            message, and hence available in the CMTP header.

       NUM RTS (8 bits) Number of policy routes requested.

       GEN FLGS (8 bits) Set of three flags indicating how to obtain the
            requested routes, contained in the right-most bits.  Proceeding
            left to right, the first flag indicates whether the route server
            should retrieve existing routes from its route database or
            generate new routes (1 retrieve, 0 generate).  The second flag
            indicates whether the route server should refresh its routing
            information database before generating the requested routes (1
            refresh, 0 no refresh) and when set to 1, causes the third flag
            and the RFS AD field to become significant.  The third flag

    Steenstrup                                                     [Page 69]

    RFC 1479                     IDPR Protocol                     July 1993

            indicates whether the routing information database refresh
            should include CONFIGURATION messages or DYNAMIC messages (1
            configuration, 0 dynamic).

       RFS AD (16 bits) Numeric identifier for the domain for which routing
            information should be refreshed.  This field is meaningful only
            if the second flag in the GEN FLGS field is set to 1.

       NUM AD (16 bits) Number of transit domains that are to be favored,
            avoided, or excluded during route selection (see section 1.4.1).

       AD (16 bits) Numeric identifier for a transit domain to be favored,
            avoided, or excluded.

       AD FLGS (8 bits) Three flags indicating how to interpret the AD
            field, contained in the right-most bits.  Proceeding left to
            right, the first flag indicates whether the domain should be
            favored (1 favored, 0 not favored).  The second flag indicates
            whether the domain should be avoided (1 avoided, 0 not avoided).
            The third flag indicates whether the domain should be excluded
            (1 excluded, 0 not excluded).  No more than one of the first,
            second, and third flags must set to 1.

       RQS TYP (16 bits) Numeric identifier for a type of requested service.
            Valid requested services include the following types:

       1.  Upper bound on delay, in milliseconds (16 bits).  This attribute
           may be omitted.

       2.  Minimum delay route.  This attribute may be omitted.

       3.  Upper bound on delay variation, in milliseconds (16 bits).  This
           attribute may be omitted.

       4.  Minimum delay variation route.  This attribute may be omitted.

       5.  Lower bound on bandwidth, in bits per second (48 bits).  This
           attribute may be omitted.

       6.  Maximum bandwidth route.  This attribute may be omitted.

       7.  Upper bound on monetary cost, in cents (32 bits).  This attribute
           may be omitted.

       8.  Minimum monetary cost route.  This attribute may be omitted.

       9.  Path lifetime in minutes (16 bits). This attribute may be omitted
           but must be present if types 7 or 8 are present. Route servers

    Steenstrup                                                     [Page 70]

    RFC 1479                     IDPR Protocol                     July 1993

           use path lifetime information together with domain charging
           method to compute expected session monetary cost over a given
           domain.

       10. Path lifetime in messages (16 bits).  This attribute may be
           omitted but must be present if types 7 or 8 are present.

       11. Path lifetime in bytes (48 bits).  This attribute may be omitted
           but must be present if types 7 or 8 are present.

       RQS LEN
            (16 bits) Length of the requested service, in bytes, beginning
            with the next field.

       RQS SRV
            (variable) Description of the requested service.

    5.5.3.  ROUTE RESPONSE

       The ROUTE RESPONSE 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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    NUM RTS    |
       +---------------+
       For each route provided:
       +---------------+---------------+
       |    NUM AD     |   RTE FLGS    |
       +---------------+---------------+
       For each domain in the route:
       +---------------+---------------+-------------------------------+
       |    AD LEN     |      VG       |            ADJ AD             |
       +---------------+---------------+-------------------------------+
       |            ADJ CMP            |            NUM TP             |
       +-------------------------------+-------------------------------+
       |              TP               |
       +-------------------------------+

       NUM RTS
            (16 bits) Number of policy routes provided.

       RTE FLGS (8 bits) Set of two flags indicating the directions in which
            a route can be used, contained in the right-most bits.  Refer to
            sections 6.2, 7, and 7.2 for detailed discussions of path
            directionality.  Proceeding left to right, the first flag
            indicates whether the route can be used from source to
            destination (1 from source, 0 not from source).  The second flag

    Steenstrup                                                     [Page 71]

    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

            domain which the adjacent domain's transit policies permit the
            requested traffic flow and which are currently reachable from
            the entry virtual gateway.

       Next Node:

            These steps are performed for all exit virtual gateways in the
            above set.

          - If there are no exit virtual gateways in the set, go to Remove
            Next Node.

          - Compute the characteristics for the route to the exit virtual
            gateway, and check that all of the route characteristics are
            within the requested service limits.  If any of the route
            characteristics are outside of these limits, go to Next Node.

          - Compare these route characteristics with those already
            associated with the exit virtual gateway (there may be none, if
            this is the first time the exit virtual gateway has been visited
            in the search), according to the primary optimal service.

          - Select the route with the optimal value of the primary optimal
            service, resolve ties by considering optimality according to any
            other optimal requested services in the order in which they are
            listed in the ROUTE REQUEST message, and associate the selected
            route and its characteristics with the exit virtual gateway.

          - Add the virtual gateway to the next-node structure:

                 BF:  Add to the end of the fifo queue.

                 SPF: Add to the heap.

                 and go to Next Node.

       Exit:
            Return a response to the route request, consisting of either a
            set of candidate policy routes or an indication that the route
            request cannot be fulfilled.

       Policy Consistency: Check policy consistency for the given domain.

          - Check that the given domain is not specified as an excluded
            domain in the route request.

          - Check that the given domain's transit policies do not preclude
            traffic generated by members of the source host set with the

    Steenstrup                                                     [Page 77]

    RFC 1479                     IDPR Protocol                     July 1993

            specified user class and requested services, from flowing to the
            destination domain.

       During the computation of the requested routes, a route server also
       caches what it considers to be all feasible routes to intermediate
       destination domains, thus increasing the chances of being able to
       respond to a future route request without having to generate a new
       route.  The route server does perform some policy consistency checks
       on the routes, as they are generated, to intermediate destinations.
       However, these routes may not in fact be feasible; the transit
       domains contained on the routes may not permit traffic between the
       source and the given intermediate destinations.  Hence, before
       dispensing such a route in response to a route request, a route
       server must check that the transit policies of the constituent
       domains are consistent with the source and destination of the traffic
       flow.

    6.2.  Route Directionality

       A path agent may wish to set up a bidirectional path using a route
       supplied by a route server.  (Refer to sections 7.2 and 7.4 for
       detailed discussions of path directionality.)  However, a route
       server can only guarantee that the routes it supplies are feasible if
       used in the direction from source to destination.  The reason is that
       the route server, which resides in the source or source proxy domain,
       does not have access to, and thus cannot account for, the source
       policies of the destination domain.  Nevertheless, the route server
       can provide the path agent with an indication of its assessment of
       route feasibility in the direction from destination to source.

       A necessary but insufficient condition for a route to be feasible in
       the direction from destination to source is as follows.  The route
       must be consistent, in the direction from destination to source, with
       the transit policies of the domains that compose the route.  The
       transit policy consistency checks performed by the route server
       during route generation account for the direction from source to
       destination but not for the direction from destination to source.
       Only after a route server generates a feasible route from source to
       destination does it perform the transit policy consistency checks for
       the route in the direction from destination to source.  Following
       these checks, the route server includes in its ROUTE RESPONSE message
       to the path agent an indication of its assessment of route
       feasibility in each direction.

    Steenstrup                                                     [Page 78]

    RFC 1479                     IDPR Protocol                     July 1993

    6.3.  Route Database

       A policy route, as originally specified by a route server, is an
       ordered list of virtual gateways, domains, and transit policies: VG 1
       - AD 1 - TP 1 - ... - VG n - AD n - TP n. where VG i is the virtual
       gateway that serves as exit from AD i-1 and entry to AD i, and TP i
       is the set of transit policies associated with AD i and relevant to
       the particular route.  Each route is indexed by source and
       destination domain.  Route servers and paths agents store policy
       routes in route databases maintained as caches whose entries must be
       periodically flushed to avoid retention of stale policy routes.  A
       route server's route database is the set of all routes it has
       generated on behalf of its domain as source or source proxy;
       associated with each route in the database are its route
       characteristics.  A path agent's route database is the set of all
       routes it has requested and received from route servers on behalf of
       hosts for which it is configured to act.

       When attempting to locate a feasible route for a traffic flow, a path
       agent first consults its own route database before querying a route
       server.  If the path agent's route database contains one or more
       routes between the given source and destination domains and
       accommodating the given host set and UCI, then the path agent checks
       each such route against the set of excluded domains listed in the
       source policy.  The path agent either selects the first route
       encountered that does not include the excluded domains, or, if no
       such route exists in its route database, requests a route from a
       route server.

       A path agent must query a route server for routes when it is unable
       to fulfill a route request from its own route database.  Moreover, we
       recommend that a path agent automatically forward to a route server,
       all route requests with non-null requested services.  The reason is
       that the path agent retains no route characteristics in its route
       database.  Hence, the path agent cannot determine whether an entry in
       its route database satisfies the requested services.

       When responding to a path agent's request for a policy route, a route
       server first consults its route database, unless the ROUTE REQUEST
       message contains an explicit directive to generate a new route.  If
       its route database contains one or more routes between the given
       source and destination domains and accommodating the given host set
       and UCI, the route server checks each such route against the set of
       excluded domains listed in the ROUTE REQUEST message.  The route
       server either selects all routes encountered that do not include the
       excluded domains, or, if no such route exists in its route database,
       attempts to generate such a route.  Once the route server selects a
       set of routes, it then checks each such route against the services

    Steenstrup                                                     [Page 79]

    RFC 1479                     IDPR Protocol                     July 1993

       requested by the path agent and the services offered by the domains
       composing the route.  To obtain the offered services information, the
       route server consults its routing information database.  The route
       server either selects the first route encountered that is consistent
       with both the requested and offered services, or, if no such route
       exists in its route database, attempts to generate such a route.

    6.3.1.  Cache Maintenance

       Each route stored in a route database has a maximum cache lifetime
       equal to rdb_rs minutes for a route server and rdb_ps minutes for a
       path agent.  Route servers and path agents reclaim cache space by
       flushing entries that have attained their maximum lifetimes.
       Moreover, paths agents reclaim cache space for routes whose paths
       have failed to be set up successfully or have been torn down (see
       section 7.4).

       Nevertheless, cache space may become scarce, even with reclamation of
       entries.  If a cache fills, the route server or path agent logs the
       event for network management.  To obtain space in the cache when the
       cache is full, the route server or path agent deletes from the cache
       the oldest entry.

    7.  Path Control Protocol and Data Message Forwarding Procedure

       Two entities in different domains may exchange IDPR data messages,
       only if there exists an IDPR path set up between the two domains.
       Path setup requires cooperation among path agents and intermediate
       policy gateways.  Path agents locate policy routes, initiate the Path
       Control Protocol (PCP), and manage existing paths between
       administrative domains.  Intermediate policy gateways verify that a
       given policy route is consistent with their domains' transit
       policies, establish the forwarding information, and forward messages
       along existing paths.

       Each policy gateway and each route server contains a path agent.  The
       path agent that initiates path setup in the source or source proxy
       domain is the "originator", and the path agent that handles the
       originator's path setup message in the destination or destination
       proxy domain is the "target".  Every path has two possible directions
       of traffic flow: from originator to target and from target to
       originator.  Path control messages are free to travel in either
       direction, but data messages may be restricted to only one direction.

       Once a path for a policy route is set up, its physical realization is
       a set of consecutive policy gateways, with policy gateways or route
       servers forming the endpoints.  Two successive entities in this set
       belong to either the same domain or the same virtual gateway.  A

    Steenstrup                                                     [Page 80]

    RFC 1479                     IDPR Protocol                     July 1993

       policy gateway or route server may, at any time, recover the
       resources dedicated to a path that goes through it by tearing down
       that path.  For example, a policy gateway may decide to tear down a
       path that has not been used for some period of time.

       PCP may build multiple paths between source and destination domains,
       but it is not responsible for managing such paths as a group or for
       eliminating redundant paths.

    7.1.  An Example of Path Setup

       We illustrate how path setup works by stepping through an example.
       Suppose host Hx in domain AD X wants to communicate with host Hy in
       domain AD Y and that both AD X and AD Y support IDPR.  Hx need not
       know the identity of its own domain or of Hy's domain in order to
       send messages to Hy.  Instead, Hx simply forwards a message bound for
       Hy to one of the gateways on its local network, according to its
       local forwarding information only.  If the recipient gateway is a
       policy gateway, the resident path agent determines how to forward the
       message outside of the domain.  Otherwise, the recipient gateway
       forwards the message to another gateway in AD X, according to its
       local forwading information.  Eventually, the message will arrive at
       a policy gateway in AD X, as policy gateways are the only egress
       points to other domains, in domains that support IDPR.

       The path agent resident in the recipient policy gateway uses the
       message header, including source and destination addresses and any
       requested service information (for example, type of service), in
       order to determine whether it is an intra-domain or inter-domain
       message, and if inter-domain, whether it requires an IDPR policy
       route.  Specifically, the path agent attempts to locate a forwarding
       information database entry for the given traffic flow, from the
       information contained in the message header.  In the future, for IP
       messages, the relevant header information may also include special
       service-specific IP options or even information from higher layer
       protocols.

       Forwarding database entries exist for all of the following:

       - All intra-domain traffic flows.  Intra-domain forwarding
         information is integrated into the forwarding information database
         as soon as it is received.

       - Inter-domain traffic flows that do not require IDPR policy routes.
         Non-IDPR forwarding information is integrated into the forwarding
         database as soon as it is received.

       - IDPR inter-domain traffic flows for which a path has already been

    Steenstrup                                                     [Page 81]

    RFC 1479                     IDPR Protocol                     July 1993

         set up.  IDPR forwarding information is integrated into the
         forwarding database only during path setup.

       The path agent uses the message header contents to guide the search
       for a forwarding information database entry for a given traffic flow.
       We recommend a radix search to locate such an entry.  When the search
       terminates, it produces either an entry, or, in the case of a new
       IDPR traffic flow, a directive to generate an entry.  If the search
       terminates in an existing forwarding information database entry, the
       path agent forwards the message according to that entry.

       Suppose that the search terminates indicating that the traffic flow
       from Hx to Hy requires an IDPR policy route and that no entry in the
       forwarding information database yet exists for that traffic flow.  In
       this case, the path agent first determines the source and destination
       domains associated with the message's source and destination
       addresses, before attempting to obtain a policy route.  The path
       agent relies on the mapping servers to supply the domain information,
       but it caches all mapping server responses locally to limit the
       number of future queries.  When attempting to resolve an address to a
       domain, the path agent always checks its local cache before
       contacting a mapping server.

       After obtaining the domain information, the path agent attempts to
       obtain a policy route to carry the traffic from Hx to Hy.  The path
       agent relies on route servers to supply policy routes, but it caches
       all route server responses locally to limit the number of future
       queries.  When attempting to locate a suitable policy route, the path
       agent usually consults its local cache before contacting a route
       server, as described previously in section 6.3.

       If no suitable cache entry exists, the path agent queries the route
       server, providing it with the source and destination domains together
       with source policy information carried in the host message or
       specified through configuration.  Upon receiving a policy route
       query, a route server consults its route database.  If it cannot
       locate a suitable route in its route database, the route server
       attempts to generate at least one route to AD Y, consistent with the
       requested services for Hx.

       The route server always returns a response to the path agent,
       regardless of whether it is successful in locating a suitable policy
       route.  The response to a successful route query consists of a set of
       candidate routes, from which the path agent makes its selection.  We
       expect that a path agent will normally choose a single route from a
       candidate set.  Nevertheless, IDPR does not preclude a path agent
       from selecting multiple routes from the candidate set.  A path agent
       may desire multiple routes to support features such as fault

    Steenstrup                                                     [Page 82]

    RFC 1479                     IDPR Protocol                     July 1993

       tolerance or load balancing; however, IDPR does not currently specify
       how the path agent should use multiple routes.

       If the policy route is a new route provided by the route server,
       there will be no existing path for the route, and thus the path agent
       must set up such a path.  However, if the policy route is an existing
       route extracted from the path agent's cache, there may well be an
       existing path for the route, set up to accommodate a host traffic
       flow.  IDPR permits multiple traffic flows to use the same path,
       provided that all traffic flows sharing the path travel between the
       same endpoint domains and have the same service requirements.
       Nevertheless, IDPR does not preclude a path agent from setting up
       distinct paths along the same policy route to preserve the
       distinction between host traffic flows.

       The path agent associates an identifier with the path, which is
       included in each message that travels down the path and is used by
       the policy gateways along the path in order to determine how to
       forward the message.  If the path already exists, the path agent uses
       the preexisting identifier.  However, for new paths, the path agent
       chooses a path identifier that is different from those of all other
       paths that it manages.  The path agent also updates its forwarding
       information database to reference the path identifier and modifies
       its search procedure to yield the correct entry in the forwarding
       information database given the data message header.

       For new paths, the path agent initiates path setup, communicating the
       policy route, in terms of requested services, constituent domains,
       relevant transit policies, and the connecting virtual gateways, to
       policy gateways in intermediate domains.  Using this information, an
       intermediate policy gateway determines whether to accept or refuse
       the path and to which next policy gateway to forward the path setup
       information.  The path setup procedure allows policy gateways to set
       up a path in both directions simultaneously.  Each intermediate
       policy gateway, after path acceptance, updates its forwarding
       information database to include an entry that associates the path
       identifier with the appropriate previous and next hop policy
       gateways.

       When a policy gateway in AD Y accepts a path, it notifies the source
       path agent in AD X.  We expect that the source path agent will
       normally wait until a path has been successfully established before
       using it to transport data traffic.  However, PCP does not preclude a
       path agent from forwarding messages along a path prior to
       confirmation of successful path establishment.  Paths remain in place
       until they are torn down because of failure, expiration, or when
       resources are scarce, preemption in favor of other paths.

    Steenstrup                                                     [Page 83]

    RFC 1479                     IDPR Protocol                     July 1993

       We note that data communication between Hx and Hy may occur over two
       separate IDPR paths: one from AD X to AD Y and one from AD Y to AD X.
       The reasons are that within a domain, hosts know nothing about path
       agents nor IDPR paths, and path agents know nothing about other path
       agents' existing IDPR paths.  Thus, in AD Y, the path agent that
       terminates the path from AD X may not be the same as the path agent
       that receives traffic from Hy destined for Hx.  In this case, receipt
       of traffic from Hy forces the second path agent to set up an
       independent path from AD Y to AD X.

    7.2.  Path Identifiers

       Each path has an associated path identifier, unique throughout an
       internetwork.  Every IDPR data message travelling along that path
       includes the path identifier, used for message forwarding.  The path
       identifier is the concatenation of three items: the identifier of the
       originator's domain, the identifier of the originator's policy
       gateway or route server, and a 32-bit local path identifier specified
       by the originator.  The path identifier and the CMTP transaction
       identifier have analogous syntax and play analogous roles in their
       respective protocols.

       When issuing a new path identifier, the originator always assigns a
       local path identifier that is different from that of any other active
       or recently torn-down path originally set up by that path agent.
       This helps to distinguish new paths from replays.  Hence, the
       originator must keep a record of each extinct path for long enough
       that all policy gateways on the path will have eliminated any
       reference to it from their memories.  The right-most 30 bits of the
       local identifier are the same for each path direction, as they are
       assigned by the originator.  The left-most 2 bits of the local
       identifier indicate the path direction.

       At path setup time, the originator specifies which of the path
       directions to enable contingent upon the information received from
       the route server in the ROUTE RESPONSE message.  By "enable", we mean
       that each path agent and each intermediate policy gateway establishes
       an association between the path identifier and the previous and next
       policy gateways on the path, which it uses for forwarding data
       messages along that path.  IDPR data messages may travel in the
       enabled path directions only, but path control messages are always
       free to travel in either path direction.  The originator may enable
       neither path direction, if the entire data transaction can be carried
       in the path setup message itself.  In this case, the path agents and
       the intermediate policy gateways do not establish forwarding
       associations for the path, but they do verify consistency of the
       policy information contained in the path setup message, with their
       own transit policies, before forwarding the setup message on to the

    Steenstrup                                                     [Page 84]

    RFC 1479                     IDPR Protocol                     July 1993

       next policy gateway.

       The path direction portion of the local path identifier has different
       interpretations, depending upon message type.  In an IDPR path setup
       message, the path direction indicates the directions in which the
       path should be enabled: the value 01 denotes originator to target,
       the value 10 denotes target to originator, the value 11 denotes both
       directions, and the value 00 denotes neither direction.  Each policy
       gateway along the path interprets the path direction in the setup
       message and sets up the forwarding information as directed.  In an
       IDPR data message, the path direction indicates the current direction
       of traffic flow: either 01 for originator to target or 10 for target
       to originator.  Thus, if for example, an originator sets up a path
       enabling only the direction from target to originator, the target
       sends data messages containing the path identifier selected by the
       originator together with the path direction set equal to 10.

       Instead of using path identifiers that are unique throughout an
       internetwork, we could have used path identifiers that are unique
       only between a pair of consecutive policy gateways and that change
       from one policy gateway pair to the next.  The advantage of locally
       unique path identifiers is that they may be much shorter than
       globally unique identifiers and hence consume less transmission
       bandwidth.  However, the disadvantage is that the path identifier
       carried in each IDPR data message must be modified at each policy
       gateway, and hence if the integrity/authentication information covers
       the path identifier, it must be recomputed at each policy gateway.
       For security reasons, we have chosen to include the path identifier
       in the set of information covered by the integrity/authentication
       value, and moreover, we advocate public-key based signatures for
       authentication.  Thus, it is not possible for intermediate policy
       gateways to modify the path identifier and then recompute the correct
       integrity/authentication value.  Therefore, we have decided in favor
       of path identifiers that do not change from hop to hop and hence must
       be globally unique.  To speed forwarding of IDPR data messages with
       long path identifiers, policy gateways should hash the path
       identifiers in order to index IDPR forwarding information.

    7.3.  Path Control Messages

       Messages exchanged by the path control protocol are classified into
       "requests": SETUP, TEARDOWN, REPAIR; and "responses": ACCEPT, REFUSE,
       ERROR.  These messages have significance for intermediate policy
       gateways as well as for path agents.

       SETUP:
            Establishes a path by linking together pairs of policy gateways.
            The SETUP message is generated by the originator and propagates

    Steenstrup                                                     [Page 85]

    RFC 1479                     IDPR Protocol                     July 1993

            to the target.  In response to a SETUP message, the originator
            expects to receive an ACCEPT, REFUSE, or ERROR message.  The
            SETUP message carries all information necessary to set up the
            path including path identifier, requested services, transit
            policy information relating to each domain traversed, and
            optionally, expedited data.

       ACCEPT: Signals successful path establishment.  The ACCEPT message is
            generated by the target, in response to a SETUP message, and
            propagates back to the originator.  Reception of an ACCEPT
            message by the originator indicates that the originator can now
            safely proceed to send data along the path.  The ACCEPT message
            contains the path identifier and an optional reason for
            conditional acceptance.

       REFUSE: Signals that the path could not be successfully established,
            either because resources were not available or because there was
            an inconsistency between the services requested by the source
            and the services offered by a transit domain along the path.
            The REFUSE message is generated by the target or by any
            intermediate policy gateway, in response to a SETUP message, and
            propagates back to the originator.  All recipients of a REFUSE
            message recover the resources dedicated to the given path.  The
            REFUSE message contains the path identifier and the reason for
            path refusal.

       TEARDOWN: Tears down a path, typically when a non-recoverable failure
            is detected.  The TEARDOWN message may be generated by any path
            agent or policy gateway in the path and usually propagates in
            both path directions.  All recipients of a TEARDOWN message
            recover the resources dedicated to the given path.  The TEARDOWN
            message contains the path identifier and the reason for path
            teardown.

       REPAIR: Establishes a repaired path by linking together pairs of
            policy gateways.  The REPAIR message is generated by a policy
            gateway after detecting that the next policy gateway on one of
            its existing paths is unreachable.  A policy gateway that
            generates a REPAIR message propagates the message forward at
            most one virtual gateway.  In response to a REPAIR message, the
            policy gateway expects to receive an ACCEPT, REFUSE, TEARDOWN,
            or ERROR message.  The REPAIR message carries the original SETUP
            message.

       ERROR: Transports information about a path error back to the
            originator, when a PCP message contains unrecognized
            information.  The ERROR message may be generated by the target
            or by any intermediate policy gateway and propagates back to the

    Steenstrup                                                     [Page 86]

    RFC 1479                     IDPR Protocol                     July 1993

            originator.  Most, but not all, ERROR messages are generated in
            response to errors encountered during path setup.  The ERROR
            message includes the path identifier and an explanation of the
            error detected.

       Policy gateways use CMTP for reliable transport of PCP messages,
       between path agents and policy gateways and between consecutive
       policy gateways on a path.  PCP must communicate to CMTP the maximum
       number of transmissions per path control message, pcp_ret, and the
       interval between path contol message retransmissions, pcp_int
       microseconds.  All path control messages, except ERROR messages, may
       be transmitted up to pcp_ret times; ERROR messages are never
       retransmitted.  A path control message is "acceptable" if:

       - It passes the CMTP validation checks.

       - Its timestamp is less than pcp_old (300) seconds behind the
         recipient's internal clock time.

       - It carries a recognized path identifier, provided it is not a SETUP
         message.

       An intermediate policy gateway on a path forwards acceptable PCP
       messages.  As we describe in section 7.4 below, SETUP messages must
       undergo additional tests at each intermediate policy gateway prior to
       forwarding.  Moreover, receipt of an acceptable ACCEPT, REFUSE,
       TEARDOWN, or ERROR message at either path agent or at any
       intermediate policy gateway indirectly cancels any active local CMTP
       retransmissions of the original SETUP message.  When a path agent or
       intermediate policy gateway receives an unacceptable path control
       message, it discards the message and logs the event for network
       management.  The path control message age limit reduces the
       likelihood of denial of service attacks based on message replay.

    7.4.  Setting Up and Tearing Down a Path

       Path setup begins when the originator generates a SETUP message
       containing:

       - The path identifier, including path directions to enable.

       - An indication of whether the message includes expedited data.

       -   The source user class identifier.

       - The requested services (see section 5.5.2) and source-specific
         information (see section 7.6.1) for the path.

    Steenstrup                                                     [Page 87]

    RFC 1479                     IDPR Protocol                     July 1993

       - For each domain on the path, the domain component, applicable
         transit policies, and entry and exit virtual gateways.

       The only mandatory requested service is the maximum path lifetime,
       pth_lif, and the only mandatory source-specific information is the
       data message integrity/authentication type.  If these are not
       specified in the path setup message, each recipient policy gateway
       assigns them default values, (60) minutes for pth_lif and no
       authentication for integrity/authentication type.  Each path agent
       and intermediate policy gateway tears down a path when the path
       lifetime is exceeded.  Hence, no single source can indefinitely
       monopolize policy gateway resources or still functioning parts of
       partially broken paths.

       After generating the SETUP message and establishing the proper local
       forwarding information, the originator selects the next policy
       gateway on the path and forwards the SETUP message to the selected
       policy gateway.  The next policy gateway selection procedure,
       described below, applies when either the originator or an
       intermediate policy gateway is making the selection.  We have elected
       to describe the procedure from the perspective of a selecting
       intermediate policy gateway.

       The policy gateway selects the next policy gateway on a path, in
       round-robin order from its list of policy gateways contained in the
       present or next virtual gateway, as explained below.  In selecting
       the next policy gateway, the policy gateway uses information
       contained in the SETUP message and information provided by VGP and by
       the intra-domain routing procedure.

       If the selecting policy gateway is a domain entry point, the next
       policy gateway must be:

       - A member of the next virtual gateway listed in the SETUP message.

       - Reachable according to intra-domain routes supporting the transit
         policies listed in the SETUP message.

       - Able to reach, according to VGP, the next domain component listed
         in the SETUP message.

       In addition, the selecting policy gateway may use quality of service
       information supplied by intra-domain routing to resolve ties between
       otherwise equivalent next policy gateways in the same domain.  In
       particular, the selecting policy gateway may select the next policy
       gateway whose connecting intra-domain route is optimal according to
       the requested services listed in the SETUP message.

    Steenstrup                                                     [Page 88]

    RFC 1479                     IDPR Protocol                     July 1993

       If the selecting policy gateway is a domain exit point, the next
       policy gateway must be:

       - A member of the current virtual gateway listed in the SETUP message
         (which is also the selecting policy gateway's virtual gateway).

       - Reachable according to VGP.

       - A member of the next domain component listed in the SETUP message.

       Once the originator or intermediate policy gateway selects a next
       policy gateway, it forwards the SETUP message to the selected policy
       gateway.  Each recipient (policy gateway or target) of an acceptable
       SETUP message performs several checks on the contents of the message,
       in order to determine whether to establish or reject the path.  We
       describe these checks in detail below from the perspective of a
       policy gateway as SETUP message recipient.

    7.4.1.  Validating Path Identifiers

       The recipient of a SETUP message first checks the path identifier, to
       make sure that it does not correspond to that of an already existing
       or recently extinct path.  To detect replays, malicious or otherwise,
       path agents and policy gateways maintain a record of each path that
       they establish, for max{pth_lif, pcp_old} seconds.  If the path
       identifier and timestamp carried in the SETUP message match a stored
       path identifier and timestamp, the policy gateway considers the
       message to be a retransmission and does not forward the message.  If
       the path identifier carried in the SETUP message matches a stored
       path identifier but the two timestamps do not agree, the policy
       gateway abandons path setup, logs the event for network management,
       and returns an ERROR message to the originator via the previous
       policy gateway.

    7.4.2.  Path Consistency with Configured Transit Policies

       Provided the path identifier in the SETUP message appears to be new,
       the policy gateway proceeds to determine whether the information
       contained within the SETUP message is consistent with the transit
       policies configured for its domain.  The policy gateway must locate
       the source and destination domains, the source host set and user
       class identifier, and the domain-specific information for its own
       domain, within the SETUP message, in order to evaluate path
       consistency.  If the policy gateway fails to recognize the source
       user class (or one or more of the requested services), it logs the
       event for network management but continues with path setup.  If the
       policy gateway fails to locate its domain within the SETUP message,
       it abandons path setup, logs the event for network management, and

    Steenstrup                                                     [Page 89]

    RFC 1479                     IDPR Protocol                     July 1993

       returns an ERROR message to the originator via the previous policy
       gateway.  The originator responds by tearing down the path and
       subsequently removing the route from its cache.

       Once the policy gateway locates its domain-specific portion of the
       SETUP message, it may encounter the following problems with the
       contents:

       - The domain-specific portion lists a transit policy not configured
         for the domain.

       - The domain-specific portion lists a virtual gateway not configured
         for the domain.

       In each case, the policy gateway abandons path setup, logs the event
       for network management, and returns an ERROR message to the
       originator via the previous policy gateway.  These types of ERROR
       messages indicate to the originator that the route may have been
       generated using information from an out-of-date CONFIGURATION
       message.

       The originator reacts to the receipt of such an ERROR message as
       follows.  First, it tears down the path and removes the route from
       its cache.  Then, it issues to a route server a ROUTE REQUEST message
       containing a directive to refresh the routing information database,
       with the most recent CONFIGURATION message from the domain that
       issued the ERROR message, before generating a new route.

       Once it verifies that its domain-specific information in the SETUP
       message is recognizable, the policy gateway then checks that the
       information contained within the SETUP message is consistent with the
       transit policies configured for its domain.  A policy gateway at the
       entry to a domain checks path consistency in the direction from
       originator to target, if the enabled path directions include
       originator to target.  A policy gateway at the exit to a domain
       checks path consistency in the direction from target to originator,
       if the enabled path directions include target to originator.

       When evaluating the consistency of the path with the transit policies
       configured for the domain, the policy gateway may encounter any of
       the following problems with SETUP message contents:

       - A transit policy does not apply in the given direction between the
         virtual gateways listed in the SETUP message.

       - A transit policy denies access to traffic from the given host set
         between the source and destination domains listed in the SETUP
         message.

    Steenstrup                                                     [Page 90]

    RFC 1479                     IDPR Protocol                     July 1993

       - A transit policy denies access to traffic from the source user
         class listed in the SETUP message.

       - A transit policy denies access to traffic at the current time.

       In each case, the policy gateway abandons path setup, logs the event
       for network management, and returns a REFUSE message to the
       originator via the previous policy gateway.  These types of REFUSE
       messages indicate to the originator that the route may have been
       generated using information from an out-of-date CONFIGURATION
       message.  The REFUSE message also serves to teardown the path.

       The originator reacts to the receipt of such a REFUSE message as
       follows. First, it removes the route from its cache.  Then, it issues
       to a route server a ROUTE REQUEST message containing a directive to
       refresh the routing information database, with the most recent
       CONFIGURATION message from the domain that issued the REFUSE message,
       before generating a new route.

    7.4.3.  Path Consistency with Virtual Gateway Reachability

       Provided the information contained in the SETUP message is consistent
       with the transit policies configured for its domain, the policy
       gateway proceeds to determine whether the path is consistent with the
       reachability of the virtual gateway containing the potential next
       hop.  To determine virtual gateway reachability, the policy gateway
       uses information provided by VGP and by the intra-domain routing
       procedure.

       When evaluating the consistency of the path with virtual gateway
       reachability, the policy gateway may encounter any of the following
       problems:

       - The virtual gateway containing the potential next hop is down.

       - The virtual gateway containing the potential next hop is not
         reachable via any intra-domain routes supporting the transit
         policies listed in the SETUP message.

       - The next domain component listed in the SETUP message is not
         reachable.

       Each of these determinations is made from the perspective of a single
       policy gateway and may not reflect actual reachability.  In each
       case, the policy gateway encountering such a problem returns a REFUSE
       message to the previous policy gateway which then selects a different
       next policy gateway, in round-robin order, as described in
       previously.  If the policy gateway receives the same response from

    Steenstrup                                                     [Page 91]

    RFC 1479                     IDPR Protocol                     July 1993

       all next policy gateways selected, it abandons path setup, logs the
       event for network management, and returns the REFUSE message to the
       originator via the previous policy gateway.  These types of REFUSE
       messages indicate to the originator that the route may have been
       generated using information from an out-of-date DYNAMIC message.  The
       REFUSE message also serves to teardown the path.

       The originator reacts to the receipt of such a REFUSE message as
       follows.  First, it removes the route from its cache.  Then, it
       issues to a route server a ROUTE REQUEST message containing a
       directive to refresh the routing information database, with the most
       recent DYNAMIC message from the domain that issued the REFUSE
       message, before generating a new route.

    7.4.4.  Obtaining Resources

       Once the policy gateway determines that the SETUP message contents
       are consistent with the transit policies and virtual gateway
       reachability of its domain, it attempts to gain resources for the new
       path.  For this version of IDPR, path resources consist of memory in
       the local forwarding information database.  However, in the future,
       path resources may also include reserved link bandwidth.

       If the policy gateway does not have sufficient resources to establish
       the new path, it uses the following algorithm to determine whether to
       generate a REFUSE message for the new path or a TEARDOWN message for
       an existing path in favor of the new path.  There are two cases:

       - No paths have been idle for more than pcp_idle (300) seconds.  In
         this case, the policy gateway returns a REFUSE message to the
         previous policy gateway.  This policy gateway then tries to select
         a different next policy gateway, as described previously, provided
         the policy gateway that issued the REFUSE message was not the
         target. If the REFUSE message was issued by the target or if there
         is no available next policy gateway, the policy gateway returns
         the REFUSE message to the originator via the previous policy
         gateway and logs the event for network management.  The REFUSE
         message serves to tear down the path.

       - At least one path has been idle for more than pcp_idle seconds.  In
         this case, the policy gateway tears down an older path in order to
         accommodate the newer path and logs the event for network
         management.  Specifically, the policy gateway tears down the least
         recently used path among those that have been idle for longer than
         pcp_idle seconds, resolving ties by choosing the oldest such path.

       If the policy gateway has sufficient resources to establish the path,

    Steenstrup                                                     [Page 92]

    RFC 1479                     IDPR Protocol                     July 1993

       it attempts to update its local forwarding information database with
       information about the path identifier, previous and next policy
       gateways on the path, and directions in which the path should be
       enabled for data traffic transport.

    7.4.5  Target Response

       When an acceptable SETUP message successfully reaches an entry policy
       gateway in the destination or destination proxy domain, this policy
       gateway performs all of the SETUP message checks described in the
       above sections.  The policy gateway's path agent then becomes the
       target, provided no checks fail, unless there is an explicit target
       specified in the SETUP message.  For example, remote route servers
       act as originator and target during RSQP message exchanges (see
       section 5.2).  If the recipient policy gateway is not the target, it
       attempts to forward the SETUP message to the target along an intra-
       domain route.  However, if the target is not reachable via intra-
       domain routing, the policy gateway abandons path setup, logs the
       event for network management, and returns a REFUSE message to the
       originator via the previous policy gateway.  The REFUSE message
       serves to tear down the path.

       Once the SETUP message reaches the target, the target determines
       whether it has sufficient path resources.  The target generates an
       ACCEPT message, provided it has sufficient resources to establish the
       path.  Otherwise, it generates a REFUSE message.

       The target may choose to use the reverse path to transport data
       traffic to the source domain, if the enabled path directions include
       10 or 11.  However, the target must first verify the consistency of
       the reverse path with its own domain's configured transit policies,
       before sending data traffic over that path.

    7.4.6.  Originator Response

       The originator expects to receive an ACCEPT, REFUSE, or ERROR message
       in response to a SETUP message and reacts as follows:

       - The originator receives an ACCEPT message, confirming successful
         path establishment.  To expedite data delivery, the originator may
         forward data messages along the path prior to receiving an ACCEPT
         message, with the understanding that there is no guarantee that the
         path actually exists.

       - The originator receives a REFUSE message or an ERROR message,
         implying that the path could not be successfully established.  In
         response, the originator attempts to set up a different path to the
         same destination, as long as the number of selected different paths

    Steenstrup                                                     [Page 93]

    RFC 1479                     IDPR Protocol                     July 1993

         does not exceed setup_try (3).  If the originator is unsuccessful
         after setup_try attempts, it abandons path setup and logs the event
         for network management.

       - The originator fails to receive any response to the SETUP message
         within setup_int microseconds after transmission.  In this case,
         the originator attempts path setup using the same policy route and
         a new path identifier, as long as the number of path setup attempts
         using the same route does not exceed setup_ret (2).  If the
         originator fails to receive a response to a SETUP message after
         setup_ret attempts, it logs the event for network management and
         then proceeds as though it received a negative response, namely a
         REFUSE or an ERROR, to the SETUP message.  Specifically, it
         attempts to set up a different path to the same destination, or it
         abandons path setup altogether, depending on the value of
         setup_try.

    7.4.7.  Path Life

       Once set up, a path does not live forever.  A path agent or policy
       gateway may tear down an existing path, provided any of the following
       conditions are true:

       - The maximum path lifetime (in minutes, bytes, or messages) has been
         exceeded at the originator, the target, or an intermediate policy
         gateway.  In each case, the IDPR entity detecting path expiration
         logs the event for network management and generates a TEARDOWN
         message as follows:

          o The originator path agent generates a TEARDOWN message for
            propagation toward the target.

          o The target path agent generates a TEARDOWN message for
            propagation toward the originator.

          o An intermediate policy gateway generates two TEARDOWN messages,
            one for propagation toward the originator and one for
            propagation toward the target.

       - The previous or next policy gateway becomes unreachable, across a
         virtual gateway or across a domain according to a given transit
         policy, and the path is not reparable.  In either case, the policy
         gateway detecting the reachability problem logs the event for
         network management and generates a TEARDOWN message as follows:

          o If the previous policy gateway is unreachable, an intermediate
            policy gateway generates a TEARDOWN message for propagation to
            the target.

    Steenstrup                                                     [Page 94]

    RFC 1479                     IDPR Protocol                     July 1993

          o If the next policy gateway is unreachable, an intermediate
            policy gateway generates a TEARDOWN message for propagation to
            the originator.

       - All of the policy gateway's path resources are in use at the
         originator, the target, or an intermediate policy gateway, a new
         path requires resources, and the given existing path is expendable,
         according to the least recently used criterion discussed in section
         7.4.4 above.  In each case, the IDPR entity initiating path
         preemption logs the event for network management and generates a
         TEARDOWN message as follows:

          o The originator path agent generates a TEARDOWN message for
            propagation toward the originator.

          o The target path agent generates a TEARDOWN message for
            propagation toward the originator.

          o An intermediate policy gateway generates two TEARDOWN messages,
            one for propagation toward the originator and one for
            propagation toward the target.

       Path teardown at a path agent or policy gateway, whether initiated by
       one of the above events, by receipt of a TEARDOWN message, or by
       receipt of a REFUSE message during path setup (as discussed in the
       previous sections), results in the path agent or policy gateway
       releasing all resources devoted to both directions of the path.

    7.5.  Path Failure and Recovery

       When a policy gateway fails, it may not be able to save information
       pertaining to its established paths.  Thus, when the policy gateway
       returns to service, it may have no recollection of the paths set up
       through it and hence may no longer be able to forward data messages
       along these paths.  We expect that when a policy gateway fails, it
       will usually be out of service for long enough that the up/down
       protocol and the intra-domain routing procedure can detect that the
       particular policy gateway is no longer reachable.  In this case,
       adjacent or neighbor policy gateways that have set up paths through
       the failed policy gateway and that have detected the failure, attempt
       local path repair (see section 7.5.2 below), and if unsuccessful,
       issue TEARDOWN messages for all affected paths.

    Steenstrup                                                     [Page 95]

    RFC 1479                     IDPR Protocol                     July 1993

    7.5.1.  Handling Implicit Path Failures

       Nevertheless, policy gateways along a path must be able to handle the
       case in which a policy gateway fails and subsequently returns to
       service without either the up/down protocol or the intra-domain
       routing procedure detecting the failure; we do not expect this event
       to occur often.  If the policy gateway, prior to failure, contained
       forwarding information for several established paths, it may now
       receive many IDPR data messages containing unrecognized path
       identifiers.  The policy gateway should alert the data sources that
       their paths through it are no longer viable.

       Policy gateways that receive IDPR data messages with unrecognized
       path identifiers take one of the following two actions, depending
       upon their past failure record:

       - The policy gateway has not failed in the past pg_up (24) hour
         period.  In this case, there are at least four possible reasons for
         the unrecognized path identifier in the data message:

          o The data message path identifier has been corrupted in a way
            that is not detectable by the integrity/authentication value, if
            one is present.

          o The policy gateway has experienced a memory error.

          o The policy gateway failed sometime during the life of the path
            and source sent no data on the path for a period of pg_up hours
            following the failure.  Although paths may persist for more than
            pg_up hours, we expect that they will also be used more
            frequently than once every pg_up hours.

          o The path was not successfully established, and the originator
            sent data messages down the path prior to receiving a response
            to its SETUP message.

          In all cases, the policy gateway discards the data message and
          logs the event for network management.

       - The policy gateway has failed at least once in the past pg_up hour
         period.  Thus, the policy gateway assumes that the unrecognized
         path identifier in the data message may be attributed to its
         failure.  In response to the data message, the policy gateway
         generates an ERROR message containing the unrecognized path
         identifier.  The policy gateway then sends the ERROR message back
         to the entity from which it received the data message, which should
         be equivalent to the previous policy gateway on the path.

    Steenstrup                                                     [Page 96]

    RFC 1479                     IDPR Protocol                     July 1993

       When the previous policy gateway receives such an ERROR message, it
       decides whether the message is acceptable.  If the policy gateway
       does not recognize the path identifier contained in the ERROR
       message, it does not find the ERROR message acceptable and
       subsequently discards the message.  However, if the policy gateway
       does find the ERROR message acceptable, it then determines whether it
       has already received an ACCEPT message for the given path.  If the
       policy gateway has not received an ACCEPT message for that path, it
       discards the ERROR message and takes no further action.

       If the policy gateway has received an ACCEPT message for that path,
       it then attempts path repair, as described in section 7.5.2 below.
       Only if path repair is unsuccessful does the previous policy gateway
       generate a TEARDOWN message for the path and return it to the
       originator.  The TEARDOWN message includes the domain and virtual
       gateway containing the policy gateway that failed, which aids the
       originator in selecting a new path that does not include the domain
       containing the failed policy gateway.  This mechanism ensures that
       path agents quickly discover and recover from disrupted paths, while
       guarding against unwarranted path teardown.

    7.5.2.  Local Path Repair

       Failure of one of more entities on a given path may render the path
       unusable.  If the failure is within a domain, IDPR relies on the
       intra-domain routing procedure to find an alternate route across the
       domain, which leaves the path unaffected.  If the failure is in a
       virtual gateway, policy gateways must bear the responsibility of
       repairing the path.  Policy gateways nearest to the failure are the
       first to recognize its existence and hence can react most quickly to
       repair the path.

       Relinquishing control over path repair to policy gateways in other
       domains may be unacceptable to some domain administrators.  The
       reason is that these policy gateways cannot guarantee construction of
       a path that satisfies the source policies of the source domain, as
       they have no knowledge of other domains' source policies.

       Nevertheless, limited local path repair is feasible, without
       distributing either source policy information throughout an
       internetwork or detailed path information among policy gateways in
       the same domain or in the same virtual gateway.  We say that a path
       is "locally reparable" if there exists an alternate route between two
       policy gateways, separated by at most one virtual gateway, on the
       path.  This definition covers path repair in the presence of failed
       routes between consecutive policy gateways as well as failed policy
       gateways themselves.

    Steenstrup                                                     [Page 97]

    RFC 1479                     IDPR Protocol                     July 1993

       An IDPR entity attempts local repair of an established path, in the
       direction from originator to target, immediately after detecting that
       the next policy gateway on the path is no longer reachable.  To
       prevent multiple path repairs in response to the same failure, we
       have stipulated that path repair can only be initiated in the
       direction from originator to target.  The IDPR entity initiating
       local path repair attempts to find an alternate path to the policy
       gateway immediately following the unreachable policy gateway on the
       path.

       Local path repair minimizes the disruption of data traffic flow
       caused by certain types of failures along an established path.
       Specifically, local path repair can accommodate an individual failed
       policy gateway or failed direct connection between two adjacent
       policy gateways.  However, it can only be attempted through virtual
       gateways containing multiple peer policy gateways.  Local path repair
       is not designed to repair paths traversing failed virtual gateways or
       domain partitions.  Whenever local path repair is impossible, the
       failing path must be torn down.

    7.5.3.  Repairing a Path

       When an IDPR entity detects through an ERROR message that the next
       policy gateway has no knowledge of a given path, it generates a
       REPAIR message and forwards it to the next policy gateway.  This
       REPAIR message will reestablish the path through the next policy
       gateway.

       When an entity detects that the next policy gateway on a path is no
       longer reachable, it takes one of the following actions, depending
       upon whether the entity is a member of the next policy gateway's
       virtual gateway.

       - If the entity is not a member of the next policy gateway's virtual
         gateway, then one of the following two conditions must be true:

          o The next policy gateway has a peer that is reachable via an
            intra-domain route consistent with the requested services.  In
            this case, the entity generates a REPAIR message containing the
            original SETUP message and forwards it to the next policy
            gateway's peer.

          o The next policy gateway has no peers that are reachable via
            intra-domain routes consistent with the requested services.  In
            this case, the entity tears down the path back to the
            originator.

       - If the entity is a member of the next policy gateway's virtual

    Steenstrup                                                     [Page 98]

    RFC 1479                     IDPR Protocol                     July 1993

       gateway, then one of the following four conditions must be true:

          o The next policy gateway has a peer that belongs to the same
            domain component and is directly-connected to and reachable from
            the entity.  In this case, the entity generates a REPAIR message
            and forwards it to the next policy gateway's peer.

          o The next policy gateway has a peer that belongs to the same
            domain component, is not directly-connected to the entity, but
            is directly-connected to and reachable from one of the entity's
            peers, which in turn is reachable from the entity via an intra-
            domain route consistent with the requested services.  In this
            case, the entity generates a REPAIR message and forwards it to
            its peer.

          o The next policy gateway has no operational peers within its
            domain component, but is directly-connected to and reachable
            from one of the entity's peers, which in turn is reachable from
            the entity via an intra-domain route consistent with the
            requested services.  In this case, the entity generates a REPAIR
            message and forwards it to its peer.

          o The next policy gateway has no operational peers within its
            domain component, and the entity has no operational peers which
            are both reachable via intra-domain routes consistent with the
            requested services and directly-connected to and reachable from
            the next policy gateway.  In this case, the entity tears down
            the path back to the originator.

       A recipient of a REPAIR message takes the following steps, depending
       upon its relationship to the entity that issued the REPAIR message.

       - The recipient and the issuing entity are in the same domain or in
         same virtual gateway.  In this case, the recipient extracts the
         SETUP message contained within the REPAIR message and treats the
         message as it would any other SETUP message.  Specifically, the
         recipient checks consistency of the path with its domain's transit
         policies and virtual gateway reachability.  If there are
         unrecognized portions of the SETUP message, the recipient generates
         an ERROR message, and if there are path inconsistencies, the
         recipient generates a REFUSE message.  In either case, the
         recipient returns the corresponding message to the policy gateway
         from which it received the REPAIR message.  Otherwise, if the
         recipient accepts the REPAIR message, it updates its local
         forwarding information database accordingly and forwards the REPAIR
         message to a potential next policy gateway, according to the
         information contained in the enclosed SETUP message.

    Steenstrup                                                     [Page 99]

    RFC 1479                     IDPR Protocol                     July 1993

       - The recipient and the issuing entity are in different domains and
         different virtual gateways.  In this case, the recipient extracts
         the SETUP message from the REPAIR message and determines whether
         the associated path matches any of its established paths.  If the
         path does not match an established path, the recipient generates a
         REFUSE message and returns it to the policy gateway from which it
         received the REPAIR message.  In response to the receipt of a
         REFUSE message, the policy gateway tries a different next policy
         gateway.

       The path is reparable, if a path match is discovered.  In this case,
       the recipient updates the path entry in the local forwarding
       information database and issues an ACCEPT message to the policy
       gateway from which it received the REPAIR message, which in turn
       returns the message to the entity that issued the REPAIR message.
       The path is irreparable if all potential next policy gateways have
       been exhausted and a path match has yet to be discovered.  In this
       case, the policy gateway that fails to locate a next policy gateway
       issues a TEARDOWN message to return to the originator.

       An IDPR entity expects to receive an ACCEPT, TEARDOWN, REFUSE, or
       ERROR message in response to a REPAIR message and reacts to these
       responses differently as follows:

       - The entity always returns a TEARDOWN message to the originator via
         previous policy gateway.

       - The entity does not return an ACCEPT message to the originator, but
         receipt of such a message indicates that the path has been
         successfully repaired.

       - The entity infers that the path is irreparable and subsequently
         tears down the path and logs the event for network management, upon
         receipt of a REFUSE or ERROR message or when no response to the
         REPAIR message arrives within setup_int microseconds.

       When an entity detects that the previous policy gateway on a path
       becomes unreachable, it expects to receive a REPAIR message within
       setup_wait microseconds.  If the entity does not receive a REPAIR
       message for the path within that time, it infers that the path is
       irreparable and subsequently tears down the path and logs the event
       for network management.

    7.6.  Path Control Message Formats

       The path control protocol number is equal to 3.  We describe the
       contents of each type of PCP message below.

    Steenstrup                                                    [Page 100]

    RFC 1479                     IDPR Protocol                     July 1993

    7.6.1.  SETUP

       The SETUP message type is equal to 0.

        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                            |
       |                                                               |
       +-------------------------------+-------------------------------+
       |            SRC AD             |            HST SET            |
       +---------------+---------------+-------------------------------+
       |      UCI      |    UNUSED     |            NUM RQS            |
       +---------------+---------------+-------------------------------+
       |            DST AD             |            TGT ENT            |
       +-------------------------------+-------------------------------+
       |            AD PTR             |
       +-------------------------------+
       For each requested service for the path:
       +-------------------------------+-------------------------------+
       |            RQS TYP            |            RQS LEN            |
       +-------------------------------+-------------------------------+
       |                            RQS SRV                            |
       +---------------------------------------------------------------+
       For each domain contained in the path:
       +---------------+---------------+-------------------------------+
       |    AD LEN     |      VG       |            ADJ AD             |
       +---------------+---------------+-------------------------------+
       |            ADJ CMP            |            NUM TP             |
       +-------------------------------+-------------------------------+
       |              TP               |
       +-------------------------------+

       PATH ID
            (64 bits) Path identifier consisting of the numeric identifier
            for the originator's domain (16 bits), the numeric identifier
            for the originator policy gateway or route server (16 bits), the
            path direction (2 bits), and the local path identifier (30
            bits).

       SRC AD (16 bits) Numeric identifier for the source domain, which may
            be different from the originator domain if the originator domain
            is a proxy for the source.

       HST SET (16 bits) Numeric identifier for the source's host set.

       UCI (8 bits) Numeric identifier for the source user class.  The value
            0 indicates that there is no particular source user class.

    Steenstrup                                                    [Page 101]

    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.

    Steenstrup                                                    [Page 108]