doc: Add RFC documents

1 files changed, 6051 insertions, 0 deletions

diff --git a/doc/rfc/rfc1479.txt b/doc/rfc/rfc1479.txt
new file mode 100644
index 0000000..6aaeae5
--- /dev/null
+++ b/doc/rfc/rfc1479.txt
@@ -0,0 +1,6051 @@
+
+
+
+
+
+
+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]
+
\ No newline at end of file