tech-invite   World Map
3GPP     Specs     Glossaries     UICC       IETF     RFCs     Groups     SIP     ABNFs       T+       Search     Home

RFC 1479

 
 
 

Inter-Domain Policy Routing Protocol Specification: Version 1

Part 4 of 4, p. 73 to 108
Prev RFC Part

 


prevText      Top      Up      ToC       Page 73 
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

Top      Up      ToC       Page 74 
    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.

Top      Up      ToC       Page 75 
    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.

Top      Up      ToC       Page 76 
        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

Top      Up      ToC       Page 77 
        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

Top      Up      ToC       Page 78 
        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.

Top      Up      ToC       Page 79 
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

Top      Up      ToC       Page 80 
   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

Top      Up      ToC       Page 81 
   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

Top      Up      ToC       Page 82 
     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

Top      Up      ToC       Page 83 
   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.

Top      Up      ToC       Page 84 
   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

Top      Up      ToC       Page 85 
   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

Top      Up      ToC       Page 86 
        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

Top      Up      ToC       Page 87 
        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.

Top      Up      ToC       Page 88 
   - 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.

Top      Up      ToC       Page 89 
   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

Top      Up      ToC       Page 90 
   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.

Top      Up      ToC       Page 91 
   - 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

Top      Up      ToC       Page 92 
   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,

Top      Up      ToC       Page 93 
   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

Top      Up      ToC       Page 94 
     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.

Top      Up      ToC       Page 95 
      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.

Top      Up      ToC       Page 96 
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.

Top      Up      ToC       Page 97 
   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.

Top      Up      ToC       Page 98 
   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

Top      Up      ToC       Page 99 
   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.

Top      Up      ToC       Page 100 
   - 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.

Top      Up      ToC       Page 101 
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.

Top      Up      ToC       Page 102 
   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.

Top      Up      ToC       Page 103 
   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

Top      Up      ToC       Page 104 
        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                     |
   +---------------+-----------------------------------------------+

Top      Up      ToC       Page 105 
   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.

Top      Up      ToC       Page 106 
   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.

Top      Up      ToC       Page 107 
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.

Top      Up      ToC       Page 108 
   [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.