home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc1479 < prev    next >
Text File  |  1993-07-22  |  276KB  |  6,052 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                     M. Steenstrup
  8. Request for Comments: 1479                 BBN Systems and Technologies
  9.                                                               July 1993
  10.  
  11.  
  12.      Inter-Domain Policy Routing Protocol Specification: Version 1
  13.  
  14. Status of this Memo
  15.  
  16.    This RFC specifies an IAB standards track protocol for the Internet
  17.    community, and requests discussion and suggestions for improvements.
  18.    Please refer to the current edition of the "IAB Official Protocol
  19.    Standards" for the standardization state and status of this protocol.
  20.    Distribution of this memo is unlimited.
  21.  
  22. Abstract
  23.  
  24.    We present the set of protocols and procedures that constitute
  25.    Inter-Domain Policy Routing (IDPR).  IDPR includes the virtual
  26.    gateway protocol, the flooding protocol, the route server query
  27.    protocol, the route generation procedure, the path control protocol,
  28.    and the data message forwarding procedure.
  29.  
  30. Contributors
  31.  
  32.    The following people have contributed to the protocols and procedures
  33.    described in this document: Helen Bowns, Lee Breslau, Ken Carlberg,
  34.    Isidro Castineyra, Deborah Estrin, Tony Li, Mike Little, Katia
  35.    Obraczka, Sam Resheff, Martha Steenstrup, Gene Tsudik, and Robert
  36.    Woodburn.
  37.  
  38. Table of Contents
  39.  
  40.    1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3
  41.    1.1. Domain Elements . . . . . . . . . . . . . . . . . . . . . . . 3
  42.    1.2. Policy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
  43.    1.3. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . . 5
  44.    1.3.1. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . 6
  45.    1.4. Policy Semantics. . . . . . . . . . . . . . . . . . . . . . . 7
  46.    1.4.1. Source Policies . . . . . . . . . . . . . . . . . . . . . . 7
  47.    1.4.2. Transit Policies. . . . . . . . . . . . . . . . . . . . . . 8
  48.    1.5. IDPR Message Encapsulation. . . . . . . . . . . . . . . . . . 9
  49.    1.5.1. IDPR Data Message Format. . . . . . . . . . . . . . . . . .11
  50.    1.6. Security. . . . . . . . . . . . . . . . . . . . . . . . . . .12
  51.    1.7. Timestamps and Clock Synchronization. . . . . . . . . . . . .13
  52.    1.8. Network Management. . . . . . . . . . . . . . . . . . . . . .14
  53.    1.8.1. Policy Gateway Configuration. . . . . . . . . . . . . . . .17
  54.    1.8.2. Route Server Configuration. . . . . . . . . . . . . . . . .18
  55.  
  56.  
  57.  
  58. Steenstrup                                                      [Page 1]
  59.  
  60. RFC 1479                     IDPR Protocol                     July 1993
  61.  
  62.  
  63.    2. Control Message Transport Protocol. . . . . . . . . . . . . . .18
  64.    2.1. Message Transmission. . . . . . . . . . . . . . . . . . . . .20
  65.    2.2. Message Reception . . . . . . . . . . . . . . . . . . . . . .22
  66.    2.3. Message Validation. . . . . . . . . . . . . . . . . . . . . .23
  67.    2.4. CMTP Message Formats. . . . . . . . . . . . . . . . . . . . .24
  68.    3. Virtual Gateway Protocol. . . . . . . . . . . . . . . . . . . .27
  69.    3.1. Message Scope . . . . . . . . . . . . . . . . . . . . . . . .28
  70.    3.1.1. Pair-PG Messages. . . . . . . . . . . . . . . . . . . . . .28
  71.    3.1.2. Intra-VG Messages . . . . . . . . . . . . . . . . . . . . .29
  72.    3.1.3. Inter-VG Messages . . . . . . . . . . . . . . . . . . . . .29
  73.    3.1.4. VG Representatives. . . . . . . . . . . . . . . . . . . . .31
  74.    3.2. Up/Down Protocol. . . . . . . . . . . . . . . . . . . . . . .31
  75.    3.3. Implementation. . . . . . . . . . . . . . . . . . . . . . . .33
  76.    3.4. Policy Gateway Connectivity . . . . . . . . . . . . . . . . .35
  77.    3.4.1. Within a Virtual Gateway. . . . . . . . . . . . . . . . . .35
  78.    3.4.2. Between Virtual Gateways. . . . . . . . . . . . . . . . . .37
  79.    3.4.3. Communication Complexity. . . . . . . . . . . . . . . . . .40
  80.    3.5. VGP Message Formats . . . . . . . . . . . . . . . . . . . . .41
  81.    3.5.1. UP/DOWN . . . . . . . . . . . . . . . . . . . . . . . . . .41
  82.    3.5.2. PG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .42
  83.    3.5.3. PG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .43
  84.    3.5.4. VG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .44
  85.    3.5.5. VG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .45
  86.    3.5.6. Negative Acknowledgements . . . . . . . . . . . . . . . . .46
  87.    4. Routing Information Distribution. . . . . . . . . . . . . . . .47
  88.    4.1. AD Representatives. . . . . . . . . . . . . . . . . . . . . .48
  89.    4.2. Flooding Protocol . . . . . . . . . . . . . . . . . . . . . .48
  90.    4.2.1. Message Generation. . . . . . . . . . . . . . . . . . . . .50
  91.    4.2.2. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . .52
  92.    4.2.3. Message Acceptance. . . . . . . . . . . . . . . . . . . . .52
  93.    4.2.4. Message Incorporation . . . . . . . . . . . . . . . . . . .54
  94.    4.2.5. Routing Information Database. . . . . . . . . . . . . . . .56
  95.    4.3. Routing Information Message Formats . . . . . . . . . . . . .57
  96.    4.3.1. CONFIGURATION . . . . . . . . . . . . . . . . . . . . . . .57
  97.    4.3.2. DYNAMIC . . . . . . . . . . . . . . . . . . . . . . . . . .62
  98.    4.3.3. Negative Acknowledgements . . . . . . . . . . . . . . . . .63
  99.    5. Route Server Query Protocol . . . . . . . . . . . . . . . . . .64
  100.    5.1. Message Exchange. . . . . . . . . . . . . . . . . . . . . . .64
  101.    5.2. Remote Route Server Communication . . . . . . . . . . . . . .65
  102.    5.3. Routing Information . . . . . . . . . . . . . . . . . . . . .66
  103.    5.4. Routes. . . . . . . . . . . . . . . . . . . . . . . . . . . .67
  104.    5.5. Route Server Message Formats. . . . . . . . . . . . . . . . .67
  105.    5.5.1. ROUTING INFORMATION REQUEST . . . . . . . . . . . . . . . .67
  106.    5.5.2. ROUTE REQUEST . . . . . . . . . . . . . . . . . . . . . . .68
  107.    5.5.3. ROUTE RESPONSE. . . . . . . . . . . . . . . . . . . . . . .71
  108.    5.5.4. Negative Acknowledgements . . . . . . . . . . . . . . . . .72
  109.    6. Route Generation. . . . . . . . . . . . . . . . . . . . . . . .73
  110.    6.1. Searching . . . . . . . . . . . . . . . . . . . . . . . . . .74
  111.  
  112.  
  113.  
  114. Steenstrup                                                      [Page 2]
  115.  
  116. RFC 1479                     IDPR Protocol                     July 1993
  117.  
  118.  
  119.    6.1.1. Implementation. . . . . . . . . . . . . . . . . . . . . . .75
  120.    6.2. Route Directionality. . . . . . . . . . . . . . . . . . . . .78
  121.    6.3. Route Database. . . . . . . . . . . . . . . . . . . . . . . .79
  122.    6.3.1. Cache Maintenance . . . . . . . . . . . . . . . . . . . . .80
  123.    7. Path Control Protocol and Data Message Forwarding Procedure . .80
  124.    7.1. An Example of Path Setup. . . . . . . . . . . . . . . . . . .81
  125.    7.2. Path Identifiers. . . . . . . . . . . . . . . . . . . . . . .84
  126.    7.3. Path Control Messages . . . . . . . . . . . . . . . . . . . .85
  127.    7.4. Setting Up and Tearing Down a Path. . . . . . . . . . . . . .87
  128.    7.4.1. Validating Path Identifiers . . . . . . . . . . . . . . . .89
  129.    7.4.2. Path Consistency with Configured Transit Policies . . . . .89
  130.    7.4.3. Path Consistency with Virtual Gateway Reachability. . . . .91
  131.    7.4.4. Obtaining Resources . . . . . . . . . . . . . . . . . . . .92
  132.    7.4.5. Target Response . . . . . . . . . . . . . . . . . . . . . .93
  133.    7.4.6. Originator Response . . . . . . . . . . . . . . . . . . . .93
  134.    7.4.7. Path Life . . . . . . . . . . . . . . . . . . . . . . . .  94
  135.    7.5. Path Failure and Recovery . . . . . . . . . . . . . . . . .  95
  136.    7.5.1. Handling Implicit Path Failures . . . . . . . . . . . . .  96
  137.    7.5.2. Local Path Repair . . . . . . . . . . . . . . . . . . . .  97
  138.    7.5.3. Repairing a Path. . . . . . . . . . . . . . . . . . . . .  98
  139.    7.6. Path Control Message Formats. . . . . . . . . . . . . . . . 100
  140.    7.6.1. SETUP . . . . . . . . . . . . . . . . . . . . . . . . . . 101
  141.    7.6.2. ACCEPT. . . . . . . . . . . . . . . . . . . . . . . . . . 103
  142.    7.6.3. REFUSE. . . . . . . . . . . . . . . . . . . . . . . . . . 103
  143.    7.6.4. TEARDOWN. . . . . . . . . . . . . . . . . . . . . . . . . 104
  144.    7.6.5. ERROR . . . . . . . . . . . . . . . . . . . . . . . . . . 105
  145.    7.6.6. REPAIR. . . . . . . . . . . . . . . . . . . . . . . . . . 106
  146.    7.6.7. Negative Acknowledgements . . . . . . . . . . . . . . . . 106
  147.    8. Security Considerations . . . . . . . . . . . . . . . . . . . 106
  148.    9. Authors's Address . . . . . . . . . . . . . . . . . . . . . . 107
  149.    References . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
  150.  
  151. 1.  Introduction
  152.  
  153.    In this document, we specify the protocols and procedures that
  154.    compose Inter-Domain Policy Routing (IDPR).  The objective of IDPR is
  155.    to construct and maintain routes between source and destination
  156.    administrative domains, that provide user traffic with the services
  157.    requested within the constraints stipulated for the domains
  158.    transited.  IDPR supports link state routing information distribution
  159.    and route generation in conjunction with source specified message
  160.    forwarding.  Refer to [5] for a detailed justification of our
  161.    approach to inter-domain policy routing.
  162.  
  163. 1.1.  Domain Elements
  164.  
  165.    The IDPR architecture has been designed to accommodate an
  166.    internetwork with tens of thousands of administrative domains
  167.  
  168.  
  169.  
  170. Steenstrup                                                      [Page 3]
  171.  
  172. RFC 1479                     IDPR Protocol                     July 1993
  173.  
  174.  
  175.    collectively containing hundreds of thousands of local networks.
  176.    Inter-domain policy routes are constructed using information about
  177.    the services offered by, and the connectivity between, administrative
  178.    domains.  The intra-domain details - gateways, networks, and links
  179.    traversed - of an inter-domain policy route are the responsibility of
  180.    intra-domain routing and are thus outside the scope of IDPR.
  181.  
  182.    An "administrative domain" (AD) is a collection of contiguous hosts,
  183.    gateways, networks, and links managed by a single administrative
  184.    authority.  The domain administrator defines service restrictions for
  185.    transit traffic and service requirements for locally-generated
  186.    traffic, and selects the addressing schemes and routing procedures
  187.    that apply within the domain.  Within the Internet, each domain has a
  188.    unique numeric identifier assigned by the Internet Assigned Numbers
  189.    Authority (IANA).
  190.  
  191.    "Virtual gateways" (VGs) are the only IDPR-recognized connecting
  192.    points between adjacent domains.  Each virtual gateway is a
  193.    collection of directly-connected "policy gateways" (see below) in two
  194.    adjoining domains, whose existence has been sanctioned by the
  195.    administrators of both domains.  The domain administrators may agree
  196.    to establish more than one virtual gateway between the two domains.
  197.    For each such virtual gateway, the two administrators together assign
  198.    a local numeric identifier, unique within the set of virtual gateways
  199.    connecting the two domains.  To produce a virtual gateway identifier
  200.    unique within its domain, a domain administrator concatenates the
  201.    mutually assigned local virtual gateway identifier together with the
  202.    adjacent domain's identifier.
  203.  
  204.    Policy gateways (PGs) are the physical gateways within a virtual
  205.    gateway.  Each policy gateway enforces service restrictions on IDPR
  206.    transit traffic, as stipulated by the domain administrator, and
  207.    forwards the traffic accordingly.  Within a domain, two policy
  208.    gateways are "neighbors" if they are in different virtual gateways.
  209.    A single policy gateway may belong to multiple virtual gateways.
  210.    Within a virtual gateway, two policy gateways are "peers" if they are
  211.    in the same domain and are "adjacent" if they are in different
  212.    domains.  Adjacent policy gateways are "directly connected" if the
  213.    only Internet-addressable entities attached to the connecting medium
  214.    are policy gateways in the virtual gateways.  Note that this
  215.    definition implies that not only point-to-point links but also
  216.    networks may serve as direct connections between adjacent policy
  217.    gateways.  The domain administrator assigns to each of its policy
  218.    gateways a numeric identifier, unique within that domain.
  219.  
  220.    A "domain component" is a subset of a domain's entities such that all
  221.    entities within the subset are mutually reachable via intra-domain
  222.    routes, but no entities outside the subset are reachable via intra-
  223.  
  224.  
  225.  
  226. Steenstrup                                                      [Page 4]
  227.  
  228. RFC 1479                     IDPR Protocol                     July 1993
  229.  
  230.  
  231.    domain routes from entities within the subset.  Normally, a domain
  232.    consists of a single component, namely itself; however, when
  233.    partitioned, a domain consists of multiple components.  Each domain
  234.    component has an identifier, unique within the Internet, composed of
  235.    the domain identifier together with the identifier of the lowest-
  236.    numbered operational policy gateway within the component.  All
  237.    operational policy gateways within a domain component can discover
  238.    mutual reachability through intra-domain routing information.  Hence,
  239.    all such policy gateways can consistently determine, without explicit
  240.    negotiation, which of them has the lowest number.
  241.  
  242. 1.2.  Policy
  243.  
  244.    With IDPR, each domain administrator sets "transit policies" that
  245.    dictate how and by whom the resources in its domain should be used.
  246.    Transit policies are usually public, and they specify offered
  247.    services comprising:
  248.  
  249.    -   Access restrictions: e.g., applied to traffic to or from certain
  250.        domains or classes of users.
  251.  
  252.    -   Quality: e.g., delay, throughput, or error characteristics.
  253.  
  254.    -   Monetary cost: e.g., charge per byte, message, or unit time.
  255.  
  256.    Each domain administrator also sets "source policies" for traffic
  257.    originating in its domain.  Source policies are usually private, and
  258.    they specify requested services comprising:
  259.  
  260.    -   Access restrictions: e.g., domains to favor or avoid in routes.
  261.  
  262.    -   Quality: e.g., acceptable delay, throughput, and reliability.
  263.  
  264.    -   Monetary cost: e.g., acceptable session cost.
  265.  
  266. 1.3.  IDPR Functions
  267.  
  268.    IDPR comprises the following functions:
  269.  
  270.    -   Collecting and distributing routing information including domain
  271.        transit policies and inter-domain connectivity.
  272.  
  273.    -   Generating and selecting policy routes based on the routing
  274.        information distributed and on the source policies configured or
  275.        requested.
  276.  
  277.    -   Setting up paths across the Internet using the policy routes
  278.        generated.
  279.  
  280.  
  281.  
  282. Steenstrup                                                      [Page 5]
  283.  
  284. RFC 1479                     IDPR Protocol                     July 1993
  285.  
  286.  
  287.    -   Forwarding messages across and between domains along the
  288.        established paths.
  289.  
  290.    -   Maintaining databases of routing information, inter-domain policy
  291.        routes, forwarding information, and configuration information.
  292.  
  293. 1.3.1.  IDPR Entities
  294.  
  295.    Several different entities are responsible for performing the IDPR
  296.    functions.
  297.  
  298.    Policy gateways, the only IDPR-recognized connecting points between
  299.    adjacent domains, collect and distribute routing information,
  300.    participate in path setup, forward data messages along established
  301.    paths, and maintain forwarding information databases.
  302.  
  303.    "Path agents", resident within policy gateways and within "route
  304.    servers" (see below), act on behalf of hosts to select policy routes,
  305.    to set up and manage paths, and to maintain forwarding information
  306.    databases.  Any Internet host can reap the benefits of IDPR, as long
  307.    as there exists a path agent configured to act on its behalf and a
  308.    means by which the host's messages can reach the path agent.
  309.    Specifically, a path agent in one domain may be configured to act on
  310.    behalf of hosts in another domain.  In this case, the path agent's
  311.    domain is an IDPR "proxy" for the hosts' domain.
  312.  
  313.    Route servers maintain both the routing information database and the
  314.    route database, and they generate policy routes using the routing
  315.    information collected and the source policies requested by the path
  316.    agents.  A route server may reside within a policy gateway, or it may
  317.    exist as an autonomous entity.  Separating the route server functions
  318.    from the policy gateways frees the policy gateways from both the
  319.    memory intensive task of database (routing information and route)
  320.    maintenance and the computationally intensive task of route
  321.    generation.  Route servers, like policy gateways, each have a unique
  322.    numeric identifier within their domain, assigned by the domain
  323.    administrator.
  324.  
  325.    Given the size of the current Internet, each policy gateway can
  326.    perform the route server functions, in addition to its message
  327.    forwarding functions, with little or no degradation in message
  328.    forwarding performance.  Aggregating the routing functions into
  329.    policy gateways simplifies implementation; one need only install IDPR
  330.    protocols in policy gateways.  Moreover, it simplifies communication
  331.    between routing functions, as all functions reside within each policy
  332.    gateway.  As the Internet grows, the memory and processing required
  333.    to perform the route server functions may become a burden for the
  334.    policy gateways.  When this happens, each domain administrator should
  335.  
  336.  
  337.  
  338. Steenstrup                                                      [Page 6]
  339.  
  340. RFC 1479                     IDPR Protocol                     July 1993
  341.  
  342.  
  343.    separate the route server functions from the policy gateways in its
  344.    domain.
  345.  
  346.    "Mapping servers" maintain the database of mappings that resolve
  347.    Internet names and addresses to domain identifiers.  Each host is
  348.    contained within a domain and is associated with a proxy domain which
  349.    may be identical with the host's domain.  The mapping server function
  350.    will be integrated into the existing DNS name service (see [6]) and
  351.    will provide mappings between a host and its local and proxy domains.
  352.  
  353.    "Configuration servers" maintain the databases of configured
  354.    information that apply to IDPR entities within their domains.
  355.    Configuration information for a given domain includes transit
  356.    policies (i.e., service offerings and restrictions), source policies
  357.    (i.e., service requirements), and mappings between local IDPR
  358.    entities and their names and addresses.  The configuration server
  359.    function will be integrated into a domain's existing network
  360.    management system (see [7]-[8]).
  361.  
  362. 1.4.  Policy Semantics
  363.  
  364.    The source and transit policies supported by IDPR are intended to
  365.    accommodate a wide range of services available throughout the
  366.    Internet.  We describe the semantics of these policies, concentrating
  367.    on the access restriction aspects.  To express these policies in this
  368.    document, we have chosen to use a syntactic variant of Clark's policy
  369.    term notation [1].  However, we provide a more succinct syntax (see
  370.    [7]) for actually configuring source and transit policies.
  371.  
  372. 1.4.1.  Source Policies
  373.  
  374.    Each source policy takes the form of a collection of sets as follows:
  375.  
  376.    Applicable Sources and Destinations:
  377.       {((H(1,1),s(1,1)),...,(H(1,f1),s(1,f1))),...,((H(n,1),s(n,1)),...,
  378.       (H(n,fn),s(n,fn)))}: The set of groups of source/destination
  379.       traffic flows to which the source policy applies.  Each traffic
  380.       flow group ((H(i,1),s(i,1)),...,(H(i,fi),s(i,fi))) contains a set
  381.       of source hosts and corresponding destination hosts.  Here, H(i,j)
  382.       represents a host, and s(i,j), an element of {SOURCE,
  383.       DESTINATION}, represents an indicator of whether H(i,j) is to be
  384.       considered as a source or as a destination.
  385.  
  386.    Domain Preferences: {(AD(1),x(1)),...,(AD(m),x(m))}: The set of
  387.       transit domains that the traffic flows should favor, avoid, or
  388.       exclude.  Here, AD(i) represents a domain, and x(i), an element of
  389.       {FAVOR, AVOID, EXCLUDE}, represents an indicator of whether routes
  390.       including AD(i) are to be favored, avoided if possible, or
  391.  
  392.  
  393.  
  394. Steenstrup                                                      [Page 7]
  395.  
  396. RFC 1479                     IDPR Protocol                     July 1993
  397.  
  398.  
  399.       unconditionally excluded.
  400.  
  401.    UCI: The source user class for the traffic flows listed.
  402.  
  403.    RequestedServices: The set of requested services not related to
  404.       access restrictions, i.e., service quality and monetary cost.
  405.  
  406.    When selecting a route for a traffic flow from a source host H(i,j)
  407.    to a destination host H(i,k), where 1 < or = i < or = n and 1 < or =
  408.    j, k < or = fi, the path agent (see section 1.3.1) must honor the
  409.    source policy such that:
  410.  
  411.    - For each domain, AD(p), contained in the route, AD(p) is not equal
  412.      to any AD(k), such that 1 < or = k < or = m and x(k) = EXCLUDE.
  413.  
  414.    - The route provides the services listed in the set Requested
  415.      Services.
  416.  
  417. 1.4.2.  Transit Policies
  418.  
  419.    Each transit policy takes the form of a collection of sets as
  420.    follows:
  421.  
  422.    Source/Destination Access Restrictions:
  423.       {((H(1,1),AD(1,1),s(1,1)),...,(H(1,f1),AD(1,f1),s(1,f1))),...,
  424.       ((H(n,1),AD(n,1),s(n,1)),...,(H(n,fn),AD(n,fn),s(n,fn)))}: The set
  425.       of groups of source and destination hosts and domains to which the
  426.       transit policy applies.  Each domain group
  427.       ((H(i,1),AD(i,1),s(i,1)),...,(H(i,fi),AD(i,fi),s(i,fi))) contains
  428.       a set of source and destination hosts and domains such that this
  429.       transit domain will carry traffic from each source listed to each
  430.       destination listed.  Here, H(i,j) represents a set of hosts,
  431.       AD(i,j) represents a domain containing H(i,j), and s(i,j), a
  432.       subset of {SOURCE, DESTINATION}, represents an indicator of
  433.       whether (H(i,j),AD(i,j)) is to be considered as a set of sources,
  434.       destinations, or both.
  435.  
  436.    Temporal Access Restrictions: The set of time intervals during which
  437.       the transit policy applies.
  438.  
  439.    User Class Access Restrictions: The set of user classes to which the
  440.       transit policy applies.
  441.  
  442.    Offered Services: The set of offered services not related to access
  443.       restrictions, i.e., service quality and monetary cost.
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Steenstrup                                                      [Page 8]
  451.  
  452. RFC 1479                     IDPR Protocol                     July 1993
  453.  
  454.  
  455.    Virtual Gateway Access Restrictions:
  456.       {((VG(1,1),e(1,1)),...,(VG(1,g1),e(1,g1))),...,((VG(m,1),e(m,1)),
  457.       gateways to which the transit policy applies.  Each virtual
  458.       gateway group ((VG(i,1),e(i,1)),...,(VG(i,gi),e(i,gi))) contains a
  459.       set of domain entry and exit points such that each entry virtual
  460.       gateway can reach (barring an intra-domain routing failure) each
  461.       exit virtual gateway via an intra-domain route supporting the
  462.       transit policy.  Here, VG(i,j) represents a virtual gateway, and
  463.       e(i,j), a subset of {ENTRY, EXIT}, represents an indicator of
  464.       whether VG(i,j) is to be considered as a domain entry point, exit
  465.       point, or both.
  466.  
  467.    The domain advertising such a transit policy will carry traffic from
  468.    any host in the set H(i,j) in AD(i,j) to any host in the set H(i,k)
  469.    in AD(i,k), where 1 < or = i < or = n and 1 < or = j, k < or = fi,
  470.    provided that:
  471.  
  472.    - SOURCE is an element of s(i,j).
  473.  
  474.    - DESTINATION is an element of s(i,k).
  475.  
  476.    - Traffic from H(i,j) enters the domain during one of the intervals
  477.      in the set Temporal Access Restrictions.
  478.  
  479.    - Traffic from H(i,j) carries one of the user class identifiers in
  480.      the set User Class Access Restrictions.
  481.  
  482.    - Traffic from H(i,j) enters via any VG(u,v) such that ENTRY is an
  483.      element of e(u,v), where 1 < or = u < or = m and 1 < or = v < or =
  484.      gu.
  485.  
  486.    - Traffic to H(i,k) leaves via any VG(u,w) such that EXIT is an
  487.      element of e(u,w), where 1 < or = w < or = gu.
  488.  
  489. 1.5.  IDPR Message Encapsulation
  490.  
  491.    There are two kinds of IDPR messages:
  492.  
  493.    - "Data messages" containing user data generated by hosts.
  494.  
  495.    - "Control messages" containing IDPR protocol-related control
  496.      information generated by policy gateways and route servers.
  497.  
  498.    Within an internetwork, only policy gateways and route servers are
  499.    able to generate, recognize, and process IDPR messages.  The
  500.    existence of IDPR is invisible to all other gateways and hosts,
  501.    including mapping servers and configuration servers.  Mapping servers
  502.    and configuration servers perform necessary but ancillary functions
  503.  
  504.  
  505.  
  506. Steenstrup                                                      [Page 9]
  507.  
  508. RFC 1479                     IDPR Protocol                     July 1993
  509.  
  510.  
  511.    for IDPR, and thus they are not required to handle IDPR messages.
  512.  
  513.    An IDPR entity places IDPR-specific information in each IDPR control
  514.    message it originates; this information is significant only to
  515.    recipient IDPR entities.  Using "encapsulation" across each domain,
  516.    an IDPR message tunnels from source to destination across an
  517.    internetwork through domains that may employ disparate intra-domain
  518.    addressing schemes and routing procedures.
  519.  
  520.    As an alternative to encapsulation, we had considered embedding IDPR
  521.    in IP, as a set of IP options.  However, this approach has the
  522.    following disadvantages:
  523.  
  524.    - Only domains that support IP would be able to participate in IDPR;
  525.      domains that do not support IP would be excluded.
  526.  
  527.    - Each gateway, policy or other, in a participating domain would at
  528.      least have to recognize the IDPR option, even if it did not execute
  529.      the IDPR protocols.  However, most commercial routers are not
  530.      optimized for IP options processing, and so IDPR message handling
  531.      might require significant processing at each gateway.
  532.  
  533.    - For some IDPR protocols, in particular path control, the size
  534.      restrictions on IP options would preclude inclusion of all of the
  535.      necessary protocol-related information.
  536.  
  537.    For these reasons, we decided against the IP option approach and in
  538.    favor of encapsulation.
  539.  
  540.    An IDPR message travels from source to destination between
  541.    consecutive policy gateways.  Each policy gateway encapsulates the
  542.    IDPR message with information, for example an IP header, that will
  543.    enable the message to reach the next policy gateway.  Note that the
  544.    encapsulating header and the IDPR-specific information may increase
  545.    the message size beyond the MTU of the given domain.  However,
  546.    message fragmentation and reassembly is the responsibility of the
  547.    protocol, for example IP, that encapsulates IDPR messages for
  548.    transport between successive policy gateways; it is not currently the
  549.    responsibility of IDPR itself.
  550.  
  551.    A policy gateway, when forwarding an IDPR message to a peer or a
  552.    neighbor policy gateway, encapsulates the message in accordance with
  553.    the addressing scheme and routing procedure of the given domain and
  554.    indicates in the protocol field of the encapsulating header that the
  555.    message is indeed an IDPR message.  Intermediate gateways between the
  556.    two policy gateways forward the IDPR message as they would any other
  557.    message, using the information in the encapsulating header.  Only the
  558.    recipient policy gateway interprets the protocol field, strips off
  559.  
  560.  
  561.  
  562. Steenstrup                                                     [Page 10]
  563.  
  564. RFC 1479                     IDPR Protocol                     July 1993
  565.  
  566.  
  567.    the encapsulating header, and processes the IDPR message.
  568.  
  569.    A policy gateway, when forwarding an IDPR message to a directly-
  570.    connected adjacent policy gateway, encapsulates the message in
  571.    accordance with the addressing scheme of the entities within the
  572.    virtual gateway and indicates in the protocol field of the
  573.    encapsulating header that the message is indeed an IDPR message.  The
  574.    recipient policy gateway strips off the encapsulating header and
  575.    processes the IDPR message.  We recommend that the recipient policy
  576.    gateway perform the following validation check of the encapsulating
  577.    header, prior to stripping it off.  Specifically, the recipient
  578.    policy gateway should verify that the source address and the
  579.    destination address in the encapsulating header match the adjacent
  580.    policy gateway's address and its own address, respectively.
  581.    Moreover, the recipient policy gateway should verify that the message
  582.    arrived on the interface designated for the direct connection to the
  583.    adjacent policy gateway.  These checks help to ensure that IDPR
  584.    traffic that crosses domain boundaries does so only over direct
  585.    connections between adjacent policy gateways.
  586.  
  587.    Policy gateways forward IDPR data messages according to a forwarding
  588.    information database which maps "path identifiers", carried in the
  589.    data messages, into next policy gateways.  Policy gateways forward
  590.    IDPR control messages according to next policy gateways selected by
  591.    the particular IDPR control protocols associated with the messages.
  592.    Distinguishing IDPR data messages and IDPR control messages at the
  593.    encapsulating protocol level, instead of at the IDPR protocol level,
  594.    eliminates an extra level of dispatching and hence makes IDPR message
  595.    forwarding more efficient.  When encapsulated within IP messages,
  596.    IDPR data messages and IDPR control messages carry the IP protocol
  597.    numbers 35 and 38, respectively.
  598.  
  599. 1.5.1.  IDPR Data Message Format
  600.  
  601.    The path agents at a source domain determine which data messages
  602.    generated by local hosts are to be handled by IDPR.  To each data
  603.    message selected for IDPR handling, a source path agent prepends the
  604.    following header:
  605.  
  606.  
  607.  
  608.  
  609.  
  610.  
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618. Steenstrup                                                     [Page 11]
  619.  
  620. RFC 1479                     IDPR Protocol                     July 1993
  621.  
  622.  
  623.     0                   1                   2                   3
  624.     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
  625.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  626.    |    VERSION    |     PROTO     |            LENGTH             |
  627.    +---------------+---------------+-------------------------------+
  628.    |                            PATH ID                            |
  629.    |                                                               |
  630.    +---------------------------------------------------------------+
  631.    |                           TIMESTAMP                           |
  632.    +---------------------------------------------------------------+
  633.    |                            INT/AUTH                           |
  634.    |                                                               |
  635.    +---------------------------------------------------------------+
  636.  
  637.    VERSION (8 bits) Version number for IDPR data messages, currently
  638.    equal to 1.
  639.  
  640.    PROTO (8 bits) Numeric identifier for the protocol with which to
  641.    process the contents of the IDPR data message.  Only the path agent
  642.    at the destination interprets and acts upon the contents of the PROTO
  643.    field.
  644.  
  645.    LENGTH (16 bits) Length of the entire IDPR data message in bytes.
  646.  
  647.    PATH ID (64 bits) Path identifier assigned by the source's path agent
  648.    and consisting of the numeric identifier for the path agent's domain
  649.    (16 bits), the numeric identifier for the path agent's policy gateway
  650.    (16 bits), and the path agent's local path identifier (32 bits) (see
  651.    section 7.2).
  652.  
  653.    TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970
  654.    0:00 GMT.
  655.  
  656.    INT/AUTH (variable) Computed integrity/authentication value,
  657.    dependent on the type of integrity/authentication requested during
  658.    path setup.
  659.  
  660.    We describe the IDPR control message header in section 2.4.
  661.  
  662. 1.6.  Security
  663.  
  664.    IDPR contains mechanisms for verifying message integrity and source
  665.    authenticity and for protecting against certain types of denial of
  666.    service attacks.  It is particularly important to keep IDPR control
  667.    messages intact, because they carry control information critical to
  668.    the construction and use of viable policy routes between domains.
  669.  
  670.    All IDPR messages carry a single piece of information, referred to as
  671.  
  672.  
  673.  
  674. Steenstrup                                                     [Page 12]
  675.  
  676. RFC 1479                     IDPR Protocol                     July 1993
  677.  
  678.  
  679.    the "integrity/authentication value", which may be used not only to
  680.    detect message corruption but also to verify the authenticity of the
  681.    message source.  In the Internet, the IANA will sanction the set of
  682.    valid algorithms which may be used to compute the
  683.    integrity/authentication values.  This set may include algorithms
  684.    that perform only message integrity checks such as n-bit cyclic
  685.    redundancy checksums (CRCs), as well as algorithms that perform both
  686.    message integrity and source authentication checks such as signed
  687.    hash functions of message contents.
  688.  
  689.    Each domain administrator is free to select any
  690.    integrity/authentication algorithm, from the set specified by the
  691.    IANA, for computing the integrity/authentication values contained in
  692.    its domain's messages.  However, we recommend that IDPR entities in
  693.    each domain be capable of executing all of the valid algorithms so
  694.    that an IDPR control message originating at an entity in one domain
  695.    can be properly checked by an entity in another domain.
  696.  
  697.    Each IDPR control message must carry a non-null
  698.    integrity/authentication value.  We recommend that control message
  699.    integrity/authentication be based on a digital signature algorithm
  700.    applied to a one-way hash function, such as RSA applied to MD5 [17],
  701.    which simultaneously verifies message integrity and source
  702.    authenticity.  The digital signature may be based on either public-
  703.    key or private-key cryptography.  Our approach to digital signature
  704.    use in IDPR is based on the privacy-enhanced Internet electronic mail
  705.    service [13]-[15], already available in the Internet.
  706.  
  707.    We do not require that IDPR data messages carry a non-null
  708.    integrity/authentication value.  In fact, we recommend that a higher
  709.    layer (end-to-end) procedure, and not IDPR, assume responsibility for
  710.    checking the integrity and authenticity of data messages, because of
  711.    the amount of computation involved.
  712.  
  713. 1.7.  Timestamps and Clock Synchronization
  714.  
  715.    Each IDPR message carries a timestamp (expressed in seconds elapsed
  716.    since 1 January 1970 0:00 GMT, following the UNIX precedent) supplied
  717.    by the source IDPR entity, which serves to indicate the age of the
  718.    message.  IDPR entities use the absolute value of the timestamp to
  719.    confirm that a message is current and use the relative difference
  720.    between timestamps to determine which message contains the more
  721.    recent information.
  722.  
  723.    All IDPR entities must possess internal clocks that are synchronized
  724.    to some degree, in order for the absolute value of a message
  725.    timestamp to be meaningful.  The synchronization granularity required
  726.    by IDPR is on the order of minutes and can be achieved manually.
  727.  
  728.  
  729.  
  730. Steenstrup                                                     [Page 13]
  731.  
  732. RFC 1479                     IDPR Protocol                     July 1993
  733.  
  734.  
  735.    Thus, a clock synchronization protocol operating among all IDPR
  736.    entities in all domains, while useful, is not necessary.
  737.  
  738.    An IDPR entity can determine whether to accept or reject a message
  739.    based on the discrepancy between the message's timestamp and the
  740.    entity's own internal clock time.  Any IDPR message whose timestamp
  741.    lies outside of the acceptable range may contain stale or corrupted
  742.    information or may have been issued by a source whose internal clock
  743.    has lost synchronization with the message recipient's internal clock.
  744.    Timestamp checks are required for control messages because of the
  745.    consequences of propagating and acting upon incorrect control
  746.    information.  However, timestamp checks are discretionary for data
  747.    messages but may be invoked during problem diagnosis, for example,
  748.    when checking for suspected message replays.
  749.  
  750.    We note that none of the IDPR protocols contain explicit provisions
  751.    for dealing with an exhausted timestamp space.  As timestamp space
  752.    exhaustion will not occur until well into the next century, we expect
  753.    timestamp space viability to outlast the IDPR protocols.
  754.  
  755. 1.8.  Network Management
  756.  
  757.    In this document, we do not describe how to configure and manage
  758.    IDPR.  However, in this section, we do provide a list of the types of
  759.    IDPR configuration information required.  Also, in later sections
  760.    describing the IDPR protocols, we briefly note the types of
  761.    exceptional events that must be logged for network management.
  762.    Complete descriptions of IDPR entity configuration and IDPR managed
  763.    objects appear in [7] and [8] respectively.
  764.  
  765.    To participate in inter-domain policy routing, policy gateways and
  766.    route servers within a domain each require configuration information.
  767.    Some of the configuration information is specifically defined within
  768.    the given domain, while some of the configuration information is
  769.    universally defined throughout an internetwork.  A domain
  770.    administrator determines domain-specific information, and in the
  771.    Internet, the IANA determines globally significant information.
  772.  
  773.    To produce valid domain configurations, the domain administrators
  774.    must receive the following global information from the IANA:
  775.  
  776.    - For each integrity/authentication type, the numeric
  777.      identifier, syntax, and semantics.  Available integrity and
  778.      authentication types include but are not limited to:
  779.  
  780.        o    public-key based signatures;
  781.  
  782.        o    private-key based signatures;
  783.  
  784.  
  785.  
  786. Steenstrup                                                     [Page 14]
  787.  
  788. RFC 1479                     IDPR Protocol                     July 1993
  789.  
  790.  
  791.  
  792.        o    cyclic redundancy checksums;
  793.  
  794.        o    no integrity/authentication.
  795.  
  796.    - For each user class, the numeric identifier, syntax, and
  797.      semantics.  Available user classes include but are not limited to:
  798.  
  799.        o    federal (and if necessary, agency-specific such as NSF, DOD,
  800.             DOE, etc.);
  801.  
  802.        o    research;
  803.  
  804.        o    commercial;
  805.  
  806.        o    support.
  807.  
  808.    - For each offered service that may be advertised in transit
  809.      policies, the numeric identifier, syntax, and semantics.  Available
  810.      offered services include but are not limited to:
  811.  
  812.        o    average message delay;
  813.  
  814.        o    message delay variation;
  815.  
  816.        o    average bandwidth available;
  817.  
  818.        o    available bandwidth variation;
  819.  
  820.        o    maximum transfer unit (MTU);
  821.  
  822.        o    charge per byte;
  823.  
  824.        o    charge per message;
  825.  
  826.        o    charge per unit time.
  827.  
  828.    - For each access restriction that may be advertised in transit
  829.      policies, the numeric identifier, syntax, and semantics.  Available
  830.      access restrictions include but are not limited to:
  831.  
  832.        o    Source and destination domains and host sets.
  833.  
  834.        o    User classes.
  835.  
  836.        o    Entry and exit virtual gateways.
  837.  
  838.        o    Time of day.
  839.  
  840.  
  841.  
  842. Steenstrup                                                     [Page 15]
  843.  
  844. RFC 1479                     IDPR Protocol                     July 1993
  845.  
  846.  
  847.    - For each requested service that may appear within a path setup
  848.      message, the numeric identifier, syntax, and semantics.  Available
  849.      requested services include but are not limited to:
  850.  
  851.        o    maximum path life in minutes, messages, or bytes;
  852.  
  853.        o    integrity/authentication algorithms to be used on data
  854.             messages sent over the path;
  855.  
  856.        o    upper bound on path delay;
  857.  
  858.        o    minimum delay path;
  859.  
  860.        o    upper bound on path delay variation;
  861.  
  862.        o    minimum delay variation path;
  863.  
  864.        o    lower bound on path bandwidth;
  865.  
  866.        o    maximum bandwidth path;
  867.  
  868.        o    upper bound on monetary cost;
  869.  
  870.        o    minimum monetary cost path.
  871.  
  872.    In an internetwork-wide implementation of IDPR, the set of global
  873.    configuration parameters and their syntax and semantics must be
  874.    consistent across all participating domains.  The IANA, responsible
  875.    for establishing the full set of global configuration parameters in
  876.    the Internet, relies on the cooperation of the administrators of all
  877.    participating domains to ensure that the global parameters are
  878.    consistent with the desired transit policies and user service
  879.    requirements of each domain.  Moreover, as the syntax and semantics
  880.    of the global parameters affects the syntax and semantics of the
  881.    corresponding IDPR software, the IANA must carefully define each
  882.    global parameter so that it is unlikely to require future
  883.    modification.
  884.  
  885.    The IANA provides configured global information to configuration
  886.    servers in all domains participating in IDPR.  Each domain
  887.    administrator uses the configured global information maintained by
  888.    its configuration servers to develop configurations for each IDPR
  889.    entity within its domain.  Each configuration server retains a copy
  890.    of the configuration for each local IDPR entity and also distributes
  891.    the configuration to that entity using, for example, SNMP.
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898. Steenstrup                                                     [Page 16]
  899.  
  900. RFC 1479                     IDPR Protocol                     July 1993
  901.  
  902.  
  903. 1.8.1.  Policy Gateway Configuration
  904.  
  905.    Each policy gateway must contain sufficient configuration information
  906.    to perform its IDPR functions, which subsume those of the path agent.
  907.    These include: validating IDPR control messages; generating and
  908.    distributing virtual gateway connectivity and routing information
  909.    messages to peer, neighbor, and adjacent policy gateways;
  910.    distributing routing information messages to route servers in its
  911.    domain; resolving destination addresses; requesting policy routes
  912.    from route servers; selecting policy routes and initiating path
  913.    setup; ensuring consistency of a path with its domain's transit
  914.    policies; establishing path forwarding information; and forwarding
  915.    IDPR data messages along existing paths.  The necessary configuration
  916.    information includes the following:
  917.  
  918.    - For each integrity/authentication type, the numeric identifier,
  919.      syntax, and semantics.
  920.  
  921.    - For each policy gateway and route server in the given domain, the
  922.      numeric identifier and set of addresses or names.
  923.  
  924.    - For each virtual gateway connected to the given domain, the numeric
  925.      identifier, the numeric identifiers for the constituent peer policy
  926.      gateways, and the numeric identifier for the adjacent domain.
  927.  
  928.    - For each virtual gateway of which the given policy gateway is a
  929.      member, the numeric identifiers and set of addresses for the
  930.      constituent adjacent policy gateways.
  931.  
  932.    - For each policy gateway directly-connected and adjacent to the
  933.      given policy gateway, the local connecting interface.
  934.  
  935.    - For each local route server to which the given policy gateway
  936.      distributes routing information, the numeric identifier.
  937.  
  938.    - For each source policy applicable to hosts within the given domain,
  939.      the syntax and semantics.
  940.  
  941.    - For each transit policy applicable to the domain, the numeric
  942.      identifier, syntax, and semantics.
  943.  
  944.    - For each requested service that may appear within a path setup
  945.      message, the numeric identifier, syntax, and semantics.
  946.  
  947.    - For each source user class, the numeric identifier, syntax, and
  948.      semantics.
  949.  
  950.  
  951.  
  952.  
  953.  
  954. Steenstrup                                                     [Page 17]
  955.  
  956. RFC 1479                     IDPR Protocol                     July 1993
  957.  
  958.  
  959. 1.8.2.  Route Server Configuration
  960.  
  961.    Each route server must contain sufficient configuration information
  962.    to perform its IDPR functions, which subsume those of the path agent.
  963.    These include: validating IDPR control messages; deciphering and
  964.    storing the contents of routing information messages; exchanging
  965.    routing information with other route servers and policy gateways;
  966.    generating policy routes that respect transit policy restrictions and
  967.    source service requirements; distributing policy routes to path
  968.    agents in policy gateways; resolving destination addresses; selecting
  969.    policy routes and initiating path setup; establishing path forwarding
  970.    information; and forwarding IDPR data messages along existing paths.
  971.    The necessary configuration information includes the following:
  972.  
  973.    - For each integrity/authentication type, the numeric identifier,
  974.      syntax, and semantics.
  975.  
  976.    - For each policy gateway and route server in the given domain, the
  977.      numeric identifier and set of addresses or names.
  978.  
  979.    - For each source policy applicable to hosts within the given domain,
  980.      the syntax and semantics.
  981.  
  982.    - For access restriction that may be advertised in transit
  983.      policies, the numeric identifier, syntax, and semantics.
  984.  
  985.    - For each offered service that may be advertised in transit policies,
  986.      the numeric identifier, syntax, and semantics.
  987.  
  988.    - For each requested service that may appear within a path setup
  989.      message, the numeric identifier, syntax, and semantics.
  990.  
  991.    - For each source user class, the numeric identifier, syntax, and
  992.      semantics.
  993.  
  994. 2.  Control Message Transport Protocol
  995.  
  996.    IDPR control messages convey routing-related information that
  997.    directly affects the policy routes generated and the paths set up
  998.    across the Internet.  Errors in IDPR control messages can have
  999.    widespread, deleterious effects on inter-domain policy routing, and
  1000.    so the IDPR protocols have been designed to minimize loss and
  1001.    corruption of control messages.  For every control message it
  1002.    transmits, each IDPR protocol expects to receive notification as to
  1003.    whether the control message successfully reached the intended IDPR
  1004.    recipient.  Moreover, the IDPR recipient of a control message first
  1005.    verifies that the message appears to be well-formed, before acting on
  1006.    its contents.
  1007.  
  1008.  
  1009.  
  1010. Steenstrup                                                     [Page 18]
  1011.  
  1012. RFC 1479                     IDPR Protocol                     July 1993
  1013.  
  1014.  
  1015.    All IDPR protocols use the Control Message Transport Protocol (CMTP),
  1016.    a connectionless, transaction-based transport layer protocol, for
  1017.    communication with intended recipients of control messages.  CMTP
  1018.    retransmits unacknowledged control messages and applies integrity and
  1019.    authenticity checks to received control messages.
  1020.  
  1021.    There are three types of CMTP messages:
  1022.  
  1023.    DATAGRAM:
  1024.         Contains IDPR control messages.
  1025.  
  1026.    ACK: Positive acknowledgement in response to a DATAGRAM message.
  1027.  
  1028.    NAK: Negative acknowledgement in response to a DATAGRAM message.
  1029.  
  1030.    Each CMTP message contains several pieces of information supplied by
  1031.    the sender that allow the recipient to test the integrity and
  1032.    authenticity of the message.  The set of integrity and authenticity
  1033.    checks performed after CMTP message reception are collectively
  1034.    referred to as "validation checks" and are described in section 2.3.
  1035.  
  1036.    When we first designed the IDPR protocols, CMTP as a distinct
  1037.    protocol did not exist.  Instead, CMTP-equivalent functionality was
  1038.    embedded in each IDPR protocol.  To provide a cleaner implementation,
  1039.    we later decided to provide a single transport protocol that could be
  1040.    used by all IDPR protocols.  We originally considered using an
  1041.    existing transport protocol, but rejected this approach for the
  1042.    following reasons:
  1043.  
  1044.    - The existing reliable transport protocols do not provide all of the
  1045.      validation checks, in particular the timestamp and authenticity
  1046.      checks, required by the IDPR protocols.  Hence, if we were to use
  1047.      one of these protocols, we would still have to provide a separate
  1048.      protocol on top of the transport protocol to force retransmission of
  1049.      IDPR messages that failed to pass the required validation checks.
  1050.  
  1051.    - Many of the existing reliable transport protocols are window-based
  1052.      and hence can result in increased message delay and resource use
  1053.      when, as is the case with IDPR, multiple independent messages use
  1054.      the same transport connection.  A single message experiencing
  1055.      transmission problems and requiring retransmission can prevent the
  1056.      window from advancing, forcing all subsequent messages to queue
  1057.      behind it.  Moreover, many of the window-based protocols do not
  1058.      support selective retransmission of failed messages but instead
  1059.      require retransmission of not only the failed message but also all
  1060.      preceding messages within the window.
  1061.  
  1062.    For these reasons, we decided against using an existing transport
  1063.  
  1064.  
  1065.  
  1066. Steenstrup                                                     [Page 19]
  1067.  
  1068. RFC 1479                     IDPR Protocol                     July 1993
  1069.  
  1070.  
  1071.    protocol and in favor of developing CMTP.
  1072.  
  1073. 2.1.  Message Transmission
  1074.  
  1075.    At the transmitting entity, when an IDPR protocol is ready to issue a
  1076.    control message, it passes a copy of the message to CMTP; it also
  1077.    passes a set of parameters to CMTP for inclusion in the CMTP header
  1078.    and for proper CMTP message handling.  In turn, CMTP converts the
  1079.    control message and associated parameters into a DATAGRAM by
  1080.    prepending the appropriate header to the control message.  The CMTP
  1081.    header contains several pieces of information to aid the message
  1082.    recipient in detecting errors (see section 2.4).  Each IDPR protocol
  1083.    can specify all of the following CMTP parameters applicable to its
  1084.    control message:
  1085.  
  1086.    -   IDPR protocol and message type.
  1087.  
  1088.    -   Destination.
  1089.  
  1090.    -   Integrity/authentication scheme.
  1091.  
  1092.    -   Timestamp.
  1093.  
  1094.    -   Maximum number of transmissions allotted.
  1095.  
  1096.    -   Retransmission interval in microseconds.
  1097.  
  1098.    One of these parameters, the timestamp, can be specified directly by
  1099.    CMTP as the internal clock time at which the message is transmitted.
  1100.    However, two of the IDPR protocols, namely flooding and path control,
  1101.    themselves require message generation timestamps for proper protocol
  1102.    operation.  Thus, instead of requiring CMTP to pass back a timestamp
  1103.    to an IDPR protocol, we simplify the service interface between CMTP
  1104.    and the IDPR protocols by allowing an IDPR protocol to specify the
  1105.    timestamp in the first place.
  1106.  
  1107.    Using the control message and accompanying parameters supplied by the
  1108.    IDPR protocol, CMTP constructs a DATAGRAM, adding to the header
  1109.    CMTP-specific parameters.  In particular, CMTP assigns a "transaction
  1110.    identifier" to each DATAGRAM generated, which it uses to associate
  1111.    acknowledgements with DATAGRAM messages.  Each DATAGRAM recipient
  1112.    includes the received transaction identifier in its returned ACK or
  1113.    NAK, and each DATAGRAM sender uses the transaction identifier to
  1114.    match the received ACK or NAK with the original DATAGRAM.
  1115.  
  1116.    A single DATAGRAM, for example a routing information message or a
  1117.    path control message, may be handled by CMTP at many different policy
  1118.    gateways.  Within a pair of consecutive IDPR entities, the DATAGRAM
  1119.  
  1120.  
  1121.  
  1122. Steenstrup                                                     [Page 20]
  1123.  
  1124. RFC 1479                     IDPR Protocol                     July 1993
  1125.  
  1126.  
  1127.    sender expects to receive an acknowledgement from the DATAGRAM
  1128.    recipient.  However, only the IDPR entity that actually generated the
  1129.    original CMTP DATAGRAM has control over the transaction identifier,
  1130.    because that entity may supply a digital signature that covers the
  1131.    entire DATAGRAM.  The intermediate policy gateways that transmit the
  1132.    DATAGRAM do not change the transaction identifier.  Nevertheless, at
  1133.    each DATAGRAM recipient, the transaction identifier must uniquely
  1134.    distinguish the DATAGRAM so that only one acknowledgement from the
  1135.    next DATAGRAM recipient matches the original DATAGRAM.  Therefore,
  1136.    the transaction identifier must be globally unique.
  1137.  
  1138.    The transaction identifier consists of the numeric identifiers for
  1139.    the domain and IDPR entity (policy gateway or route server) issuing
  1140.    the original DATAGRAM, together with a 32-bit local identifier
  1141.    assigned by CMTP operating within that IDPR entity.  We recommend
  1142.    implementing the 32-bit local identifier either as a simple counter
  1143.    incremented for each DATAGRAM generated or as a fine granularity
  1144.    clock.  The former always guarantees uniqueness of transaction
  1145.    identifiers; the latter guarantees uniqueness of transaction
  1146.    identifiers, provided the clock granularity is finer than the minimum
  1147.    possible interval between DATAGRAM generations and the clock wrapping
  1148.    period is longer than the maximum round-trip delay to and from any
  1149.    internetwork destination.
  1150.  
  1151.    Before transmitting a DATAGRAM, CMTP computes the length of the
  1152.    entire message, taking into account the prescribed
  1153.    integrity/authentication scheme, and then computes the
  1154.    integrity/authentication value over the whole message.  CMTP includes
  1155.    both of these quantities, which are crucial for checking message
  1156.    integrity and authenticity at the recipient, in the DATAGRAM header.
  1157.    After sending a DATAGRAM, CMTP saves a copy and sets an associated
  1158.    retransmission timer, as directed by the IDPR protocol parameters.
  1159.    If the retransmission timer fires and CMTP has received neither an
  1160.    ACK nor a NAK for the DATAGRAM, CMTP then retransmits the DATAGRAM,
  1161.    provided this retransmission does not exceed the transmission
  1162.    allotment.  Whenever a DATAGRAM exhausts its transmission allotment,
  1163.    CMTP discards the DATAGRAM, informs the IDPR protocol that the
  1164.    control message transmission was not successful, and logs the event
  1165.    for network management.  In this case, the IDPR protocol may either
  1166.    resubmit its control message to CMTP, specifying an alternate
  1167.    destination, or discard the control message altogether.
  1168.  
  1169.  
  1170.  
  1171.  
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177.  
  1178. Steenstrup                                                     [Page 21]
  1179.  
  1180. RFC 1479                     IDPR Protocol                     July 1993
  1181.  
  1182.  
  1183. 2.2.  Message Reception
  1184.  
  1185.    At the receiving entity, when CMTP obtains a DATAGRAM, it takes one
  1186.    of the following actions, depending upon the outcome of the message
  1187.    validation checks:
  1188.  
  1189.    - The DATAGRAM passes the CMTP validation checks.  CMTP then delivers
  1190.      the DATAGRAM with enclosed IDPR control message, to the appropriate
  1191.      IDPR protocol, which in turn applies its own integrity checks to
  1192.      the control message before acting on the contents.  The recipient
  1193.      IDPR protocol, except in one case, directs CMTP to generate an ACK
  1194.      and return the ACK to the sender.  That exception is the up/down
  1195.      protocol (see section 3.2) which determines reachability of
  1196.      adjacent policy gateways and does not use CMTP ACK messages to
  1197.      notify the sender of message reception.  Instead, the up/down
  1198.      protocol messages themselves carry implicit information about
  1199.      message reception at the adjacent policy gateway.  In the cases
  1200.      where the recipient IDPR protocol directs CMTP to generate an ACK,
  1201.      it may pass control information to CMTP for inclusion in the ACK,
  1202.      depending on the contents of the original IDPR control message.
  1203.      For example, a route server unable to fill a request for routing
  1204.      information may inform the requesting IDPR entity, through an ACK
  1205.      for the initial request, to place its request elsewhere.
  1206.  
  1207.    - The DATAGRAM fails at least one of the CMTP validation checks.
  1208.      CMTP then generates a NAK, returns the NAK to the sender, and
  1209.      discards the DATAGRAM, regardless of the type of IDPR control
  1210.      message contained in the DATAGRAM.  The NAK indicates the nature of
  1211.      the validation failure and serves to help the sender establish
  1212.      communication with the recipient.  In particular, the CMTP NAK
  1213.      provides a mechanism for negotiation of IDPR version and
  1214.      integrity/authentication scheme, two parameters crucial for
  1215.      establishing communication between IDPR entities.
  1216.  
  1217.    Upon receiving an ACK or a NAK, CMTP immediately discards the message
  1218.    if at least one of the validation checks fails or if it is unable to
  1219.    locate the associated DATAGRAM.  CMTP logs the latter event for
  1220.    network management.  Otherwise, if all of the validation checks pass
  1221.    and if it is able to locate the associated DATAGRAM, CMTP clears the
  1222.    associated retransmission timer and then takes one of the following
  1223.    actions, depending upon the message type:
  1224.  
  1225.    - The message is an ACK.  CMTP discards the associated DATAGRAM and
  1226.      delivers the ACK, which may contain IDPR control information, to
  1227.      the appropriate IDPR protocol.
  1228.  
  1229.    - The message is a NAK.  If the associated DATAGRAM has exhausted its
  1230.      transmission allotment, CMTP discards the DATAGRAM, informs the
  1231.  
  1232.  
  1233.  
  1234. Steenstrup                                                     [Page 22]
  1235.  
  1236. RFC 1479                     IDPR Protocol                     July 1993
  1237.  
  1238.  
  1239.      appropriate IDPR protocol that the control message transmission was
  1240.      not successful, and logs the event for network management.
  1241.      Otherwise, if the associated DATAGRAM has not yet exhausted its
  1242.      transmission allotment, CMTP first checks its copy of the DATAGRAM
  1243.      against the failure indication contained in the NAK.  If its
  1244.      DATAGRAM copy appears to be intact, CMTP retransmits the DATAGRAM
  1245.      and sets the associated retransmission timer.  However, if its
  1246.      DATAGRAM copy appears to be corrupted, CMTP discards the DATAGRAM,
  1247.      informs the IDPR protocol that the control message transmission was
  1248.      not successful, and logs the event for network management.
  1249.  
  1250. 2.3.  Message Validation
  1251.  
  1252.    On every CMTP message received, CMTP performs a set of validation
  1253.    checks to test message integrity and authenticity.  The order in
  1254.    which these tests are executed is important.  CMTP must first
  1255.    determine if it can parse enough of the message to compute the
  1256.    integrity/authentication value.  (Refer to section 2.4 for a
  1257.    description of CMTP message formats.)  Then, CMTP must immediately
  1258.    compute the integrity/authentication value before checking other
  1259.    header information.  An incorrect integrity/authentication value
  1260.    means that the message is corrupted, and so it is likely that CMTP
  1261.    header information is incorrect.  Checking specific header fields
  1262.    before computing the integrity/authentication value not only may
  1263.    waste time and resources, but also may lead to incorrect diagnoses of
  1264.    a validation failure.
  1265.  
  1266.    The CMTP validation checks are as follows:
  1267.  
  1268.    - CMTP verifies that it can recognize both the control message
  1269.      version type contained in the header.  Failure to recognize either
  1270.      one of these values means that CMTP cannot continue to parse the
  1271.      message.
  1272.  
  1273.    - CMTP verifies that it can recognize and accept the
  1274.      integrity/authentication type contained in the header; no
  1275.      integrity/authentication is not an acceptable type for CMTP.
  1276.  
  1277.    - CMTP computes the integrity/authentication value and verifies that
  1278.      it equals the integrity/authentication value contained in the
  1279.      header.  For key-based integrity/authentication schemes, CMTP may
  1280.      use the source domain identifier contained in the CMTP header to
  1281.      index the correct key.  Failure to index a key means that CMTP
  1282.      cannot compute the integrity/authentication value.
  1283.  
  1284.    - CMTP computes the message length in bytes and verifies that it
  1285.      equals the length value contained in the header.
  1286.  
  1287.  
  1288.  
  1289.  
  1290. Steenstrup                                                     [Page 23]
  1291.  
  1292. RFC 1479                     IDPR Protocol                     July 1993
  1293.  
  1294.  
  1295.    - CMTP verifies that the message timestamp is in the acceptable
  1296.      range.  The message should be no more recent than cmtp_new (300)
  1297.      seconds ahead of the entity's current internal clock time.  In this
  1298.      document, when we present an IDPR system configuration parameter,
  1299.      such as cmtp_new, we usually follow it with a recommended value in
  1300.      parentheses.  The cmtp_new value allows some clock drift between
  1301.      IDPR entities.  Moreover, each IDPR protocol has its own limit on
  1302.      the maximum age of its control messages.  The message should be no
  1303.      less recent than a prescribed number of seconds behind the
  1304.      recipient entity's current internal clock time.  Hence, each IDPR
  1305.      protocol performs its own message timestamp check in addition to
  1306.      that performed by CMTP.
  1307.  
  1308.    - CMTP verifies that it can recognize the IDPR protocol designated
  1309.      for the enclosed control message.
  1310.  
  1311.    Whenever CMTP encounters a failure while performing any of these
  1312.    validation checks, it logs the event for network management.  If the
  1313.    failure occurs on a DATAGRAM, CMTP immediately generates a NAK
  1314.    containing the reason for the failure, returns the NAK to the sender,
  1315.    and discards the DATAGRAM message.  If the failure occurs on an ACK
  1316.    or a NAK, CMTP discards the ACK or NAK message.
  1317.  
  1318. 2.4.  CMTP Message Formats
  1319.  
  1320.    In designing the format of IDPR control messages, we have attempted
  1321.    to strike a balance between efficiency of link bandwidth usage and
  1322.    efficiency of message processing.  In general, we have chosen compact
  1323.    representations for IDPR information in order to minimize the link
  1324.    bandwidth consumed by IDPR-specific information.  However, we have
  1325.    also organized IDPR information in order to speed message processing,
  1326.    which does not always result in minimum link bandwidth usage.
  1327.  
  1328.    To limit link bandwidth usage, we currently use fixed-length
  1329.    identifier fields in IDPR messages; domains, virtual gateways, policy
  1330.    gateways, and route servers are all represented by fixed-length
  1331.    identifiers.  To simplify message processing, we currently align
  1332.    fields containing an even number of bytes on even-byte boundaries
  1333.    within a message.  In the future, if the Internet adopts the use of
  1334.    super domains, we will offer hierarchical, variable-length identifier
  1335.    fields in an updated version of IDPR.
  1336.  
  1337.    The header of each CMTP message contains the following information:
  1338.  
  1339.  
  1340.  
  1341.  
  1342.  
  1343.  
  1344.  
  1345.  
  1346. Steenstrup                                                     [Page 24]
  1347.  
  1348. RFC 1479                     IDPR Protocol                     July 1993
  1349.  
  1350.  
  1351.     0                   1                   2                   3
  1352.     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
  1353.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1354.    |    VERSION    |  PRT  |  MSG  |  DPR  |  DMS  |    I/A TYP    |
  1355.    +---------------+-------+-------+-------+-------+---------------+
  1356.    |           SOURCE AD           |           SOURCE ENT          |
  1357.    +-------------------------------+-------------------------------+
  1358.    |                           TRANS ID                            |
  1359.    +---------------------------------------------------------------+
  1360.    |                           TIMESTAMP                           |
  1361.    +-------------------------------+-------------------------------+
  1362.    |            LENGTH             |       message specific        |
  1363.    +-------------------------------+-------------------------------+
  1364.    |         DATAGRAM AD           |         DATAGRAM ENT          |
  1365.    +-------------------------------+-------------------------------+
  1366.    |                             INFORM                            |
  1367.    +---------------------------------------------------------------+
  1368.    |                            INT/AUTH                           |
  1369.    |                                                               |
  1370.    +---------------------------------------------------------------+
  1371.  
  1372.    VERSION
  1373.         (8 bits) Version number for IDPR control messages, currently
  1374.         equal to 1.
  1375.  
  1376.    PRT (4 bits) Numeric identifier for the control message transport
  1377.         protocol, equal to 0 for CMTP.
  1378.  
  1379.    MSG (4 bits) Numeric identifier for the CMTP message type,equal to 0
  1380.         for a DATAGRAM, 1 for an ACK, and 2 for a NAK.
  1381.  
  1382.    DPR (4 bits) Numeric identifier for the original DATAGRAM's IDPR
  1383.         protocol type.
  1384.  
  1385.    DMS (4 bits) Numeric identifier for the original DATAGRAM's IDPR
  1386.         message type.
  1387.  
  1388.    I/A TYP (8 bits) Numeric identifier for the integrity/authentication
  1389.         scheme used.  CMTP requires the use of an
  1390.         integrity/authentication scheme; this value must not be set
  1391.         equal to 0, indicating no integrity/authentication in use.
  1392.  
  1393.    SOURCE AD (16 bits) Numeric identifier for the domain containing the
  1394.         IDPR entity that generated the message.
  1395.  
  1396.    SOURCE ENT (16 bits) Numeric identifier for the IDPR entity that
  1397.         generated the message.
  1398.  
  1399.  
  1400.  
  1401.  
  1402. Steenstrup                                                     [Page 25]
  1403.  
  1404. RFC 1479                     IDPR Protocol                     July 1993
  1405.  
  1406.  
  1407.    TRANSACTION ID (32 bits) Local transaction identifier assigned by the
  1408.         IDPR entity that generated the original DATAGRAM.
  1409.  
  1410.    TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970
  1411.         0:00 GMT.
  1412.  
  1413.    LENGTH (16 bits) Length of the entire IDPR control message, including
  1414.         the CMTP header, in bytes.
  1415.  
  1416.    message specific (16 bits) Dependent upon CMTP message type.
  1417.  
  1418.         For DATAGRAM and ACK messages:
  1419.  
  1420.              RESERVED
  1421.                   (16 bits) Reserved for future use and currently set
  1422.                   equal to 0.
  1423.  
  1424.         For NAK messages:
  1425.  
  1426.              ERR TYP (8 bits) Numeric identifier for the type of CMTP
  1427.                   validation failure encountered.  Validation failures
  1428.                   include the following types:
  1429.  
  1430.                   1.   Unrecognized IDPR control message version number.
  1431.  
  1432.                   2.   Unrecognized CMTP message type.
  1433.  
  1434.                   3.   Unrecognized integrity/authentication scheme.
  1435.  
  1436.                   4.   Unacceptable integrity/authentication scheme.
  1437.  
  1438.                   5.   Unable to locate key using source domain.
  1439.  
  1440.                   6.   Incorrect integrity/authentication value.
  1441.  
  1442.                   7.   Incorrect message length.
  1443.  
  1444.                   8.   Message timestamp out of range.
  1445.  
  1446.                   9.   Unrecognized IDPR protocol designated for the
  1447.                   enclosed control message.
  1448.  
  1449.  
  1450.  
  1451.  
  1452.  
  1453.  
  1454.  
  1455.  
  1456.  
  1457.  
  1458. Steenstrup                                                     [Page 26]
  1459.  
  1460. RFC 1479                     IDPR Protocol                     July 1993
  1461.  
  1462.  
  1463.              ERR INFO (8 bits) CMTP supplies the following additional
  1464.                   information for the designated types of validation
  1465.                   failures:
  1466.  
  1467.                   Type 1:
  1468.                       Acceptable IDPR control message version number.
  1469.  
  1470.                   Types 3 and 4: Acceptable integrity/authentication
  1471.                       type.
  1472.  
  1473.    DATAGRAM AD
  1474.         (16 bits) Numeric identifier for the domain containing the IDPR
  1475.         entity that generated the original DATAGRAM.  Present only in
  1476.         ACK and NAK messages.
  1477.  
  1478.    DATAGRAM ENT (16 bits) Numeric identifier for the IDPR entity that
  1479.         generated the original DATAGRAM.  Present only in ACK and NAK
  1480.         messages.
  1481.  
  1482.    INFORM (optional,variable) Information to be interpreted by the IDPR
  1483.         protocol that issued the original DATAGRAM.  Present only in ACK
  1484.         messages and dependent on the original DATAGRAM's IDPR protocol
  1485.         type.
  1486.  
  1487.    INT/AUTH (variable) Computed integrity/authentication value,
  1488.         dependent on the type of integrity/authentication scheme used.
  1489.  
  1490. 3.  Virtual Gateway Protocol
  1491.  
  1492.    Every policy gateway within a domain participates in gathering
  1493.    information about connectivity within and between virtual gateways of
  1494.    which it is a member and in distributing this information to other
  1495.    virtual gateways in its domain.  We refer to these functions
  1496.    collectively as the Virtual Gateway Protocol (VGP).
  1497.  
  1498.    The information collected through VGP has both local and global
  1499.    significance for IDPR.  Virtual gateway connectivity information,
  1500.    distributed to policy gateways within a single domain, aids those
  1501.    policy gateways in selecting routes across and between virtual
  1502.    gateways connecting their domain to adjacent domains.  Inter-domain
  1503.    connectivity information, distributed throughout an internetwork in
  1504.    routing information messages, aids route servers in constructing
  1505.    feasible policy routes.
  1506.  
  1507.    Provided that a domain contains simple virtual gateway and transit
  1508.    policy configurations, one need only implement a small subset of the
  1509.    VGP functions.  The connectivity among policy gateways within a
  1510.    virtual gateway and the heterogeneity of transit policies within a
  1511.  
  1512.  
  1513.  
  1514. Steenstrup                                                     [Page 27]
  1515.  
  1516. RFC 1479                     IDPR Protocol                     July 1993
  1517.  
  1518.  
  1519.    domain determine which VGP functions must be implemented, as we
  1520.    explain toward the end of this section.
  1521.  
  1522. 3.1.  Message Scope
  1523.  
  1524.    Policy gateways generate VGP messages containing information about
  1525.    perceived changes in virtual gateway connectivity and distribute
  1526.    these messages to other policy gateways within the same domain and
  1527.    within the same virtual gateway.  We classify VGP messages into three
  1528.    distinct categories: "pair-PG", "intra-VG", and "inter-VG", depending
  1529.    upon the scope of message distribution.
  1530.  
  1531.    Policy gateways use CMTP for reliable transport of VGP messages.  The
  1532.    issuing policy gateway must communicate to CMTP the maximum number of
  1533.    transmissions per VGP message, vgp_ret, and the interval between VGP
  1534.    message retransmissions, vgp_int microseconds.  The recipient policy
  1535.    gateway must determine VGP message acceptability; conditions of
  1536.    acceptability depend on the type of VGP message, as we describe
  1537.    below.
  1538.  
  1539.    Policy gateways store, act upon, and in the case of inter-VG
  1540.    messages, forward the information contained in acceptable VGP
  1541.    messages.  VGP messages that pass the CMTP validation checks but fail
  1542.    a specific VGP message acceptability check are considered to be
  1543.    unacceptable and are hence discarded by recipient policy gateways.  A
  1544.    policy gateway that receives an unacceptable VGP message also logs
  1545.    the event for network management.
  1546.  
  1547. 3.1.1.  Pair-PG Messages
  1548.  
  1549.    Pair-PG message communication occurs between the two members of a
  1550.    pair of adjacent, peer, or neighbor policy gateways.  With IDPR, the
  1551.    only pair-PG messages are those periodically generated by the up/down
  1552.    protocol and used to monitor mutual reachability between policy
  1553.    gateways.
  1554.  
  1555.    A pair-PG message is "acceptable" if:
  1556.  
  1557.    - It passes the CMTP validation checks.
  1558.  
  1559.    - Its timestamp is less than vgp_old (300) seconds behind the
  1560.      recipient's internal clock time.
  1561.  
  1562.    - Its destination policy gateway identifier coincides with the
  1563.      identifier of the recipient policy gateway.
  1564.  
  1565.    - Its source policy gateway identifier coincides with the identifier
  1566.      of a policy gateway configured for the recipient's domain or
  1567.  
  1568.  
  1569.  
  1570. Steenstrup                                                     [Page 28]
  1571.  
  1572. RFC 1479                     IDPR Protocol                     July 1993
  1573.  
  1574.  
  1575.      associated virtual gateway.
  1576.  
  1577. 3.1.2.  Intra-VG Messages
  1578.  
  1579.    Intra-VG message communication occurs between one policy gateway and
  1580.    all of its peers.  Whenever a policy gateway discovers that its
  1581.    connectivity to an adjacent or neighbor policy gateway has changed,
  1582.    it issues an intra-VG message indicating the connectivity change to
  1583.    all of its reachable peers.  Whenever a policy gateway detects that a
  1584.    previously unreachable peer is now reachable, it issues, to that
  1585.    peer, intra-VG messages indicating connectivity to adjacent and
  1586.    neighbor policy gateways.  If the issuing policy gateway fails to
  1587.    receive an analogous intra-VG message from the newly reachable peer
  1588.    within twice the configured VGP retransmission interval, vgp_int
  1589.    microseconds, it actively requests the intra-VG message from that
  1590.    peer.  These message exchanges ensure that peers maintain a
  1591.    consistent view of each others' connectivity to adjacent and neighbor
  1592.    policy gateways.
  1593.  
  1594.    An intra-VG message is "acceptable" if:
  1595.  
  1596.    - It passes the CMTP validation checks.
  1597.  
  1598.    - Its timestamp is less than vgp_old (300) seconds behind the
  1599.      recipient's internal clock time.
  1600.  
  1601.    - Its virtual gateway identifier coincides with that of a virtual
  1602.      gateway configured for the recipient's domain.
  1603.  
  1604. 3.1.3.  Inter-VG Messages
  1605.  
  1606.    Inter-VG message communication occurs between one policy gateway and
  1607.    all of its neighbors.  Whenever the lowest-numbered operational
  1608.    policy gateway in a set of mutually reachable peers discovers that
  1609.    its virtual gateway's connectivity to the adjacent domain or to
  1610.    another virtual gateway has changed, it issues an inter-VG message
  1611.    indicating the connectivity change to all of its neighbors.
  1612.    Specifically, the policy gateway distributes an inter-VG message to a
  1613.    "VG representative" policy gateway (see section 3.1.4 below) in each
  1614.    virtual gateway in the domain.  Each VG representative in turn
  1615.    propagates the inter-VG message to each of its peers.
  1616.  
  1617.    Whenever the lowest-numbered operational policy gateway in a set of
  1618.    mutually peers detects that one or more previously unreachable peers
  1619.    are now reachable, it issues, to the lowest-numbered operational
  1620.    policy gateway in all other virtual gateways, requests for inter-VG
  1621.    information indicating connectivity to adjacent domains and to other
  1622.    virtual gateways.  The recipient policy gateways return the requested
  1623.  
  1624.  
  1625.  
  1626. Steenstrup                                                     [Page 29]
  1627.  
  1628. RFC 1479                     IDPR Protocol                     July 1993
  1629.  
  1630.  
  1631.    inter-VG messages to the issuing policy gateway, which in turn
  1632.    distributes the messages to the newly reachable peers.  These message
  1633.    exchanges ensure that virtual gateways maintain a consistent view of
  1634.    each others' connectivity, while consuming minimal domain resources
  1635.    in distributing connectivity information.
  1636.  
  1637.    An inter-VG message contains information about the entire virtual
  1638.    gateway, not just about the issuing policy gateway.  Thus, when
  1639.    virtual gateway connectivity changes happen in rapid succession,
  1640.    recipients of the resultant inter-VG messages should be able to
  1641.    determine the most recent message and that message must contain the
  1642.    current virtual gateway connectivity information.  To ensure that the
  1643.    connectivity information distributed is consistent and unambiguous,
  1644.    we designate a single policy gateway, namely the lowest-numbered
  1645.    operational peer, for generating and distributing inter-VG messages.
  1646.    It is a simple procedure for a set of mutually reachable peers to
  1647.    determine the lowest-numbered member, as we describe in section 3.2
  1648.    below.
  1649.  
  1650.    To understand why a single member of a virtual gateway must issue
  1651.    inter-VG messages, consider the following example.  Suppose that two
  1652.    peers in a virtual gateway each detect a different connectivity
  1653.    change and generate separate inter-VG messages.  Recipients of these
  1654.    messages may not be able to determine which message is more recent if
  1655.    policy gateway internal clocks are not perfectly synchronized.
  1656.    Moreover, even if the clocks were perfectly synchronized, and hence
  1657.    message recency could be consistently determined, it is possible for
  1658.    each peer to issue its inter-VG message before receiving current
  1659.    information from the other.  As a result, neither inter-VG message
  1660.    contains the correct connectivity from the perspective of the virtual
  1661.    gateway.  However, these problems are eliminated if all inter-VG
  1662.    messages are generated by a single peer within a virtual gateway, in
  1663.    particular the lowest-numbered operational policy gateway.
  1664.  
  1665.    An inter-VG message is "acceptable" if:
  1666.  
  1667.    - It passes the CMTP validation checks.
  1668.  
  1669.    - Its timestamp is less than vgp_old (300) seconds behind the
  1670.      recipient's internal clock time.
  1671.  
  1672.    - Its virtual gateway identifier coincides with that of a virtual
  1673.      gateway configured for the recipient's domain.
  1674.  
  1675.    - Its source policy gateway identifier represents the lowest numbered
  1676.      operational member of the issuing virtual gateway, reachable from
  1677.      the recipient.
  1678.  
  1679.  
  1680.  
  1681.  
  1682. Steenstrup                                                     [Page 30]
  1683.  
  1684. RFC 1479                     IDPR Protocol                     July 1993
  1685.  
  1686.  
  1687.    Distribution of intra-VG messages among peers often triggers
  1688.    generation and distribution of inter-VG messages among virtual
  1689.    gateways.  Usually, the lowest-numbered operational policy gateway in
  1690.    a virtual gateway generates and distributes an inter-VG message
  1691.    immediately after detecting a change in virtual gateway connectivity,
  1692.    through receipt or generation of an intra-VG message.  However, if
  1693.    this policy gateway is also waiting for an intra-VG message from a
  1694.    newly reachable peer, it does not immediately generate and distribute
  1695.    the inter-VG message.
  1696.  
  1697.    Waiting for intra-VG messages enables the lowest-numbered operational
  1698.    policy gateway in a virtual gateway to gather the most recent
  1699.    connectivity information for inclusion in the inter-VG message.
  1700.    However, under unusual circumstances, the policy gateway may fail to
  1701.    receive an intra-VG message from a newly reachable peer, even after
  1702.    actively requesting such a message.  To accommodate this case, VGP
  1703.    uses an upper bound of four times the configured retransmission
  1704.    interval, vgp_int microseconds, on the amount of time to wait before
  1705.    generating and distributing an inter-VG message, when receipt of an
  1706.    intra-VG message is pending.
  1707.  
  1708. 3.1.4.  VG Representatives
  1709.  
  1710.    When distributing an inter-VG message, the issuing policy gateway
  1711.    selects as recipients one neighbor, the VG Representative, from each
  1712.    virtual gateway in the domain.  To be selected as a VG
  1713.    representative, a policy gateway must be reachable from the issuing
  1714.    policy gateway via intra-domain routing.  The issuing policy gateway
  1715.    gives preference to neighbors that are members of more than one
  1716.    virtual gateway.  Such a neighbor acts as a VG representative for all
  1717.    virtual gateways of which it is a member and restricts inter-VG
  1718.    message distribution as follows: any policy gateway that is a peer in
  1719.    more than one of the represented virtual gateways receives at most
  1720.    one copy of the inter-VG message.  This message distribution strategy
  1721.    minimizes the number of message copies required for disseminating
  1722.    inter-VG information.
  1723.  
  1724. 3.2.  Up/Down Protocol
  1725.  
  1726.    Directly-connected adjacent policy gateways execute the Up/Down
  1727.    Protocol to determine mutual reachability.  Pairs of peer or neighbor
  1728.    policy gateways can determine mutual reachability through information
  1729.    provided by the intra-domain routing procedure or through execution
  1730.    of the up/down protocol.  In general, we do not recommend
  1731.    implementing the up/down protocol between each pair of policy
  1732.    gateways in a domain, as it results in O(n**2) (where n is the number
  1733.    of policy gateways within the domain) communications complexity.
  1734.    However, if the intra-domain routing procedure is slow to detect
  1735.  
  1736.  
  1737.  
  1738. Steenstrup                                                     [Page 31]
  1739.  
  1740. RFC 1479                     IDPR Protocol                     July 1993
  1741.  
  1742.  
  1743.    connectivity changes or is unable to report reachability at the IDPR
  1744.    entity level, the reachability information obtained through the
  1745.    up/down protocol may well be worth the extra communications cost.  In
  1746.    the remainder of this section, we decribe the up/down protocol from
  1747.    the perspective of adjacent policy gateways, but we note that the
  1748.    identical protocol can be applied to peer and neighbor policy
  1749.    gateways as well.
  1750.  
  1751.    The up/down protocol determines whether the direct connection between
  1752.    adjacent policy gateways is acceptable for data traffic transport.  A
  1753.    direct connection is presumed to be "down" (unacceptable for data
  1754.    traffic transport) until the up/down protocol declares it to be "up"
  1755.    (acceptable for data traffic transport).  We say that a virtual
  1756.    gateway is "up" if there exists at least one pair of adjacent policy
  1757.    gateways whose direct connection is acceptable for data traffic
  1758.    transport, and that a virtual gateway is "down" if there exists no
  1759.    such pair of adjacent policy gateways.
  1760.  
  1761.    When executing the up/down protocol, policy gateways exchange UP/DOWN
  1762.    messages every ud_per (1) second.  All policy gateways use the same
  1763.    default period of ud_per initially and then negotiate a preferred
  1764.    period through exchange of UP/DOWN messages.  A policy gateway
  1765.    reports its desired value for ud_per within its UP/DOWN messages.  It
  1766.    then chooses the larger of its desired value and that of the adjacent
  1767.    policy gateway as the period for exchanging subsequent UP/DOWN
  1768.    messages.  Policy gateways also exchange, in UP/DOWN messages,
  1769.    information about the identity of their respective domain components.
  1770.    This information assists the policy gateways in selecting routes
  1771.    across virtual gateways to partitioned domains.
  1772.  
  1773.    Each UP/DOWN message is transported using CMTP and hence is covered
  1774.    by the CMTP validation checks.  However, unlike other IDPR control
  1775.    messages, UP/DOWN messages do not require reliable transport.
  1776.    Specifically, the up/down protocol requires only a single
  1777.    transmission per UP/DOWN message and never directs CMTP to return an
  1778.    ACK.  As pair-PG messages, UP/DOWN messages are acceptable under the
  1779.    conditions described in section 3.1.1.
  1780.  
  1781.    Each policy gateway assesses the state of its direct connection, to
  1782.    the adjacent policy gateway, by counting the number of acceptable
  1783.    UP/DOWN messages received within a set of consecutive periods.  A
  1784.    policy gateway communicates its perception of the state of the direct
  1785.    connection through its UP/DOWN messages.  Initially, a policy gateway
  1786.    indicates the down state in each of its UP/DOWN messages.  Only when
  1787.    the direct connection appears to be up from its perspective does a
  1788.    policy gateway indicate the up state in its UP/DOWN messages.
  1789.  
  1790.    A policy gateway can begin to transport data traffic over a direct
  1791.  
  1792.  
  1793.  
  1794. Steenstrup                                                     [Page 32]
  1795.  
  1796. RFC 1479                     IDPR Protocol                     July 1993
  1797.  
  1798.  
  1799.    connection only if both of the following conditions are true:
  1800.  
  1801.    - The policy gateway receives from the adjacent policy gateway at
  1802.      least j acceptable UP/DOWN messages within the last m consecutive
  1803.      periods.  From the recipient policy gateway's perspective, this
  1804.      event up.  Hence, the recipient policy gateway indicates the up
  1805.      state in its subsequent UP/DOWN messages.
  1806.  
  1807.    - The UP/DOWN message most recently received from the adjacent policy
  1808.      gateway indicates the up state, signifying that the adjacent policy
  1809.      gateway considers the direct connection to be up.
  1810.  
  1811.    A policy gateway must cease to transport data traffic over a direct
  1812.    connection whenever either of the following conditions is true:
  1813.  
  1814.    - The policy gateway receives from the adjacent policy gateway at
  1815.      most acceptable UP/DOWN messages within the last n consecutive
  1816.      periods.
  1817.  
  1818.    - The UP/DOWN message most recently received from the adjacent policy
  1819.      gateway indicates the down state, signifying that the adjacent
  1820.      policy gateway considers the direct connection to be down.
  1821.  
  1822.    From the recipient policy gateway's perspective, either of these
  1823.    events constitutes a state transition of the direct connection from
  1824.    up to down.  Hence, the policy gateway indicates the down state in
  1825.    its subsequent UP/DOWN messages.
  1826.  
  1827. 3.3.  Implementation
  1828.  
  1829.    We recommend implementing the up/down protocol using a sliding
  1830.    window.  Each window slot indicates the UP/DOWN message activity
  1831.    during a given period, containing either a "hit" for receipt of an
  1832.    acceptable UP/DOWN message or a "miss" for failure to receive an
  1833.    acceptable UP/DOWN message.  In addition to the sliding window, the
  1834.    implementation should include a tally of hits recorded during the
  1835.    current period and a tally of misses recorded over the current
  1836.    window.
  1837.  
  1838.    When the direct connection moves to the down state, the initial
  1839.    values of the up/down protocol parameters must be set as follows:
  1840.  
  1841.    -   The sliding window size is equal to m.
  1842.  
  1843.    -   Each window slot contains a miss.
  1844.  
  1845.    -   The current period hit tally is equal to 0.
  1846.  
  1847.  
  1848.  
  1849.  
  1850. Steenstrup                                                     [Page 33]
  1851.  
  1852. RFC 1479                     IDPR Protocol                     July 1993
  1853.  
  1854.  
  1855.    -   The current window miss tally is equal to m.
  1856.  
  1857.    When the direct connection moves to the up state, the initial values
  1858.    of the up/down protocol parameters must be set as follows:
  1859.  
  1860.    -   The sliding window size is equal to n.
  1861.  
  1862.    -   Each window slot contains a hit.
  1863.  
  1864.    -   The current period hit tally is equal to 0.
  1865.  
  1866.    -   The current window miss tally is equal to 0.
  1867.  
  1868.    At the conclusion of each period, a policy gateway computes the miss
  1869.    tally and determines whether there has been a state transition of the
  1870.    direct connection to the adjacent policy gateway.  In the down state,
  1871.    a miss tally of no more than m - j signals a transition to the up
  1872.    state.  In the up state, a miss tally of no less than n - k signals a
  1873.    transition to the down state.
  1874.  
  1875.    Computing the correct miss tally involves several steps.  First, the
  1876.    policy gateway prepares to slide the window by one slot so that the
  1877.    oldest slot disappears, making room for the newest slot.  However,
  1878.    before sliding the window, the policy gateway checks the contents of
  1879.    the oldest window slot.  If this slot contains a miss, the policy
  1880.    gateway decrements the miss tally by 1, as this slot is no longer
  1881.    part of the current window.
  1882.  
  1883.    After sliding the window, the policy gateway determines the proper
  1884.    contents.  If the hit tally for the current period equals 0, the
  1885.    policy gateway records a miss for the newest slot and increments the
  1886.    miss tally by 1.  Otherwise, if the hit tally for the current period
  1887.    is greater than 0, the policy gateway records a hit for the newest
  1888.    slot and decrements the hit tally by 1.  Moreover, the policy gateway
  1889.    applies any remaining hits to slots containing misses, beginning with
  1890.    the newest and progressing to the oldest such slot.  For each such
  1891.    slot containing a miss, the policy gateway records a hit in that slot
  1892.    and decrements both the hit and miss tallies by 1, as the hit cancels
  1893.    out a miss.  The policy gateway continues to apply each remaining hit
  1894.    tallied to any slot containing a miss, until either all such hits are
  1895.    exhausted or all such slots are accounted for.  Before beginning the
  1896.    next up/down period, the policy gateway resets the hit tally to 0.
  1897.  
  1898.    Although we expect the hit tally, within any given period, to be no
  1899.    greater than 1, we do anticipate the occasional period in which a
  1900.    policy gateway receives more than one UP/DOWN message from an
  1901.    adjacent policy gateway.  The most common reasons for this occurrence
  1902.    are message delay and clock drift.  When an UP/DOWN message is
  1903.  
  1904.  
  1905.  
  1906. Steenstrup                                                     [Page 34]
  1907.  
  1908. RFC 1479                     IDPR Protocol                     July 1993
  1909.  
  1910.  
  1911.    delayed, the receiving policy gateway observes a miss in one period
  1912.    followed by two hits in the next period, one of which cancels the
  1913.    previous miss.  However, excess hits remaining in the tally after
  1914.    miss cancellation indicate a problem, such as clock drift.  Thus,
  1915.    whenever a policy gateway accumulates excess hits, it logs the event
  1916.    for network management.
  1917.  
  1918.    When clock drift occurs between two adjacent policy gateways, it
  1919.    causes the period of one policy gateway to grow with respect to the
  1920.    period of the other policy gateway.  Let p(X) be the period for PG X,
  1921.    let p(Y) be the period for PG Y, and let g and h be the smallest
  1922.    positive integers such that g * p(X) = h * p(Y).  Suppose that p(Y) >
  1923.    p(X) because of clock drift.  In this case, PG X observes g - h
  1924.    misses in g consecutive periods, while PG Y observes g - h surplus
  1925.    hits in h consecutive periods.  As long as (g - h)/g < (n - k)/n and
  1926.    (g - h)/g < or = (m - j)/m, the clock drift itself will not cause the
  1927.    direct connection to enter or remain in the down state.
  1928.  
  1929. 3.4.  Policy Gateway Connectivity
  1930.  
  1931.    Policy gateways collect connectivity information through the intra-
  1932.    domain routing procedure and through VGP, and they distribute
  1933.    connectivity changes through VGP in both intra-VG messages to peers
  1934.    and inter-VG messages to neighbors.  Locally, this connectivity
  1935.    information assists policy gateways in selecting routes, not only
  1936.    across a virtual gateway to an adjacent domain but also across a
  1937.    domain between two virtual gateways.  Moreover, changes in
  1938.    connectivity between domains are distributed, in routing information
  1939.    messages, to route servers throughout an internetwork.
  1940.  
  1941. 3.4.1.  Within a Virtual Gateway
  1942.  
  1943.    Each policy gateway within a virtual gateway constantly monitors its
  1944.    connectivity to all adjacent and to all peer policy gateways.  To
  1945.    determine the state of its direct connection to an adjacent policy
  1946.    gateway, a policy gateway uses reachability information supplied by
  1947.    the up/down protocol.  To determine the state of its intra-domain
  1948.    routes to a peer policy gateway, a policy gateway uses reachability
  1949.    information supplied by either the intra-domain routing procedure or
  1950.    the up/down protocol.
  1951.  
  1952.    A policy gateway generates a PG CONNECT message whenever either of
  1953.    the following conditions is true:
  1954.  
  1955.    -   The policy gateway detects a change, in state or in adjacent
  1956.        domain component, associated with its direct connection to an
  1957.        adjacent policy gateway.  In this case, the policy gateway
  1958.        distributes a copy of the message to each peer reachable via
  1959.  
  1960.  
  1961.  
  1962. Steenstrup                                                     [Page 35]
  1963.  
  1964. RFC 1479                     IDPR Protocol                     July 1993
  1965.  
  1966.  
  1967.        intra-domain routing.
  1968.  
  1969.    -   The policy gateway detects that a previously unreachable peer is
  1970.        now reachable.  In this case, the policy gateway distributes a
  1971.        copy of the message to the newly reachable peer.
  1972.  
  1973.    A PG CONNECT message is an intra-VG message that includes information
  1974.    about each adjacent policy gateway directly connected to the issuing
  1975.    policy gateway.  Specifically, the PG CONNECT message contains the
  1976.    adjacent policy gateway's identifier, status (reachable or
  1977.    unreachable), and domain component identifier.  If a PG CONNECT
  1978.    message contains a "request", each peer that receives the message
  1979.    responds to the sender with its own PG CONNECT message.
  1980.  
  1981.    All mutually reachable peers monitor policy gateway connectivity
  1982.    within their virtual gateway, through the up/down protocol, the
  1983.    intra-domain routing procedure, and the exchange of PG CONNECT
  1984.    messages.  Within a given virtual gateway, each constituent policy
  1985.    gateway maintains the following information about each configured
  1986.    adjacent policy gateway:
  1987.  
  1988.    - The identifier for the adjacent policy gateway.
  1989.  
  1990.    - The status of the adjacent policy gateway: reachable/unreachable,
  1991.      directly connected/not directly connected.
  1992.  
  1993.    - The local exit interfaces used to reach the adjacent policy
  1994.      gateway, provided it is reachable.
  1995.  
  1996.    - The identifier for the adjacent policy gateway's domain component.
  1997.  
  1998.    - The set of peers to which the adjacent policy gateway is
  1999.      directly-connected.
  2000.  
  2001.    Hence, all mutually reachable peers can detect changes in
  2002.    connectivity across the virtual gateway to adjacent domain
  2003.    components.
  2004.  
  2005.    When the lowest-numbered operational peer policy gateway within a
  2006.    virtual gateway detects a change in the set of adjacent domain
  2007.    components reachable through direct connections across the given
  2008.    virtual gateway, it generates a VGCONNECT message and distributes a
  2009.    copy to a VG representative in all other virtual gateways connected
  2010.    to its domain.  A VG CONNECT message is an inter-VG message that
  2011.    includes information about each peer's connectivity across the given
  2012.    virtual gateway.  Specifically, the VG CONNECT message contains, for
  2013.    each peer, its identifier and the identifiers of the domain
  2014.    components reachable through its direct connections to adjacent
  2015.  
  2016.  
  2017.  
  2018. Steenstrup                                                     [Page 36]
  2019.  
  2020. RFC 1479                     IDPR Protocol                     July 1993
  2021.  
  2022.  
  2023.    policy gateways.  Moreover, the VG CONNECT message gives each
  2024.    recipient enough information to determine the state, up or down, of
  2025.    the issuing virtual gateway.
  2026.  
  2027.    The issuing policy gateway, namely the lowest-numbered operational
  2028.    peer, may have to wait up to four times vgp_int microseconds after
  2029.    detecting the connectivity change, before generating and distributing
  2030.    the VGCONNECT message, as described in section 3.1.3.  Each recipient
  2031.    VG representative in turn distributes a copy of the VG CONNECT
  2032.    message to each of its peers reachable via intra-domain routing.  If
  2033.    a VG CONNECT message contains a "request", then in each recipient
  2034.    virtual gateway, the lowest-numbered operational peer that receives
  2035.    the message responds to the original sender with its own VGCONNECT
  2036.    message.
  2037.  
  2038. 3.4.2.  Between Virtual Gateways
  2039.  
  2040.    At present, we expect transit policies to be uniform over all intra-
  2041.    domain routes between any pair of policy gateways within a domain.
  2042.    However, when tariffed qualities of service become prevalent
  2043.    offerings for intra-domain routing, we can no longer expect
  2044.    uniformity of transit policies throughout a domain.  To monitor the
  2045.    transit policies supported on intra-domain routes between virtual
  2046.    gateways requires both a policy-sensitive intra-domain routing
  2047.    procedure and a VGP exchange of policy information between neighbor
  2048.    policy gateways.
  2049.  
  2050.    Each policy gateway within a domain constantly monitors its
  2051.    connectivity to all peer and neighbor policy gateways, including the
  2052.    transit policies supported on intra-domain routes to these policy
  2053.    gateways.  To determine the state of its intra-domain connection to a
  2054.    peer or neighbor policy gateway, a policy gateway uses reachability
  2055.    information supplied by either the intra-domain routing procedure or
  2056.    the up/down protocol.  To determine the transit policies supported on
  2057.    intra-domain routes to a peer or neighbor policy gateway, a policy
  2058.    gateway uses policy-sensitive reachability information supplied by
  2059.    the intra-domain routing procedure.  We note that when transit
  2060.    policies are uniform over a domain, reachability and policy-sensitive
  2061.    reachability are equivalent.
  2062.  
  2063.    Within a virtual gateway, each constituent policy gateway maintains
  2064.    the following information about each configured peer and neighbor
  2065.    policy gateway:
  2066.  
  2067.    - The identifier for the peer or neighbor policy gateway.
  2068.  
  2069.    - The identifiers corresponding to the transit policies configured to
  2070.      be supported by intra-domain routes to the peer or neighbor policy
  2071.  
  2072.  
  2073.  
  2074. Steenstrup                                                     [Page 37]
  2075.  
  2076. RFC 1479                     IDPR Protocol                     July 1993
  2077.  
  2078.  
  2079.      gateway.
  2080.  
  2081.    - According to each transit policy, the status of the peer or
  2082.      neighbor policy gateway: reachable/unreachable.
  2083.  
  2084.    - For each transit policy, the local exit interfaces used to reach
  2085.      the peer or neighbor policy gateway, provided it is reachable.
  2086.  
  2087.    - The identifiers for the adjacent domain components reachable
  2088.      through direct connections from the peer or neighbor policy
  2089.      gateway, obtained through VG CONNECT messages.
  2090.  
  2091.    Using this information, a policy gateway can detect changes in its
  2092.    connectivity to an adjoining domain component, with respect to a
  2093.    given transit policy and through a given neighbor.  Moreover,
  2094.    combining the information obtained for all neighbors within a given
  2095.    virtual gateway, the policy gateway can detect changes in its
  2096.    connectivity, with respect to a given transit policy, to that virtual
  2097.    gateway and to adjoining domain components reachable through that
  2098.    virtual gateway.
  2099.  
  2100.    All policy gateways mutually reachable via intra-domain routes
  2101.    supporting a configured transit policy need not exchange information
  2102.    about perceived changes in connectivity, with respect to the given
  2103.    transit policy.  In this case, each policy gateway can infer
  2104.    another's policy-sensitive reachability to a third, through mutual
  2105.    intra-domain reachability information provided by the intra-domain
  2106.    routing procedure.  However, whenever two or more policy gateways are
  2107.    no longer mutually reachable with respect to a given transit policy,
  2108.    these policy gateways can no longer infer each other's reachability
  2109.    to other policy gateways, with respect to that transit policy.  In
  2110.    this case, these policy gateways must exchange explicit information
  2111.    about changes in connectivity to other policy gateways, with respect
  2112.    to that transit policy.
  2113.  
  2114.    A policy gateway generates a PG POLICY message whenever either of the
  2115.    following conditions is true:
  2116.  
  2117.    - The policy gateway detects a change in its connectivity to another
  2118.      virtual gateway, with respect to a configured transit policy, or to
  2119.      an adjoining domain component reachable through that virtual
  2120.      gateway.  In this case, the policy gateway distributes a copy of
  2121.      the message to each peer reachable via intra-domain routing but not
  2122.      currently reachable via any intra-domain routes of the given
  2123.      transit policy.
  2124.  
  2125.    - The policy gateway detects that a previously unreachable peer is
  2126.      reachable.  In this case, the policy gateway distributes a copy of
  2127.  
  2128.  
  2129.  
  2130. Steenstrup                                                     [Page 38]
  2131.  
  2132. RFC 1479                     IDPR Protocol                     July 1993
  2133.  
  2134.  
  2135.      the message to the newly reachable peer.
  2136.  
  2137.    A PG POLICY message is an intra-VG message that includes information
  2138.    about each configured transit policy and each virtual gateway
  2139.    configured to be reachable from the issuing policy gateway via
  2140.    intra-domain routes of the given transit policy.  Specifically, the
  2141.    PGPOLICY message contains, for each configured transit policy:
  2142.  
  2143.    - The identifier for the transit policy.
  2144.  
  2145.    - The identifiers for the virtual gateways associated with the given
  2146.      transit policy and currently reachable, with respect to that
  2147.      transit policy, from the issuing policy gateway.
  2148.  
  2149.    - The identifiers for the domain components reachable from and
  2150.      adjacent to the members of the given virtual gateways.
  2151.  
  2152.    If a PG POLICY message contains a "request", each peer that receives
  2153.    the message responds to the original sender with its own PG POLICY
  2154.    message.
  2155.  
  2156.    In addition to connectivity between itself and its neighbors, each
  2157.    policy gateway also monitors the connectivity, between domain
  2158.    components adjacent to its virtual gateway and domain components
  2159.    adjacent to other virtual gateways, through its domain and with
  2160.    respect to the configured transit policies.  For each member of each
  2161.    of its virtual gateways, a policy gateway monitors:
  2162.  
  2163.    -  The set of  adjacent domain components  currently reachable
  2164.      through direct connections across the given virtual gateway.  The
  2165.      policy gateway obtains this information through PG CONNECT messages
  2166.      from reachable peers and through UP/DOWN messages from adjacent
  2167.      policy gateways.
  2168.  
  2169.    - For each configured transit policy, the set of virtual gateways
  2170.      currently reachable from the given virtual gateway with respect to
  2171.      that transit policy and the set of adjoining domain components
  2172.      currently reachable through direct connections across those virtual
  2173.      gateways.  The policy gateway obtains this information through PG
  2174.      POLICY messages from peers, VG CONNECT messages from neighbors, and
  2175.      the intra-domain routing procedure.  Using this information, a
  2176.      policy gateway can detect connectivity changes, through its domain
  2177.      and with respect to a given transit policy, between adjoining
  2178.      domain components.
  2179.  
  2180.    When the lowest-numbered operational policy gateway within a virtual
  2181.    gateway detects a change in the connectivity between a domain
  2182.    component adjacent to its virtual gateway and a domain component
  2183.  
  2184.  
  2185.  
  2186. Steenstrup                                                     [Page 39]
  2187.  
  2188. RFC 1479                     IDPR Protocol                     July 1993
  2189.  
  2190.  
  2191.    adjacent to another virtual gateway in its domain, with respect to a
  2192.    configured transit policy, it generates a VG POLICY message and
  2193.    distributes a copy to a VG representative in selected virtual
  2194.    gateways connected to its domain.  In particular, the lowest-numbered
  2195.    operational policy gateway distributes a VG POLICY message to a VG
  2196.    representative in every other virtual gateway containing a member
  2197.    reachable via intra-domain routing but not currently reachable via
  2198.    any routes of the given transit policy.  A VG POLICY message is an
  2199.    inter-VG message that includes information about the connectivity
  2200.    between domain components adjacent to the issuing virtual gateway and
  2201.    domain components adjacent to the other virtual gateways in the
  2202.    domain, with respect to configured transit policies.  Specifically,
  2203.    the VG POLICY message contains, for each transit policy:
  2204.  
  2205.    - The identifier for the transit policy.
  2206.  
  2207.    - The identifiers for the virtual gateways associated with the given
  2208.      transit policy and currently reachable, with respect to that
  2209.      transit policy, from the issuing virtual gateway.
  2210.  
  2211.    - The identifiers for the domain components reachable from and
  2212.      adjacent to the members of the given virtual gateways.
  2213.  
  2214.    The issuing policy gateway, namely the lowest-numbered operational
  2215.    peer, may have to wait up to four times vgp_int microseconds after
  2216.    detecting the connectivity change, before generating and distributing
  2217.    the VG POLICY message, as described in section 3.1.3.  Each recipient
  2218.    VG representative in turn distributes a copy of the VG POLICY message
  2219.    to each of its peers reachable via intra-domain routing.  If a VG
  2220.    POLICY message contains a "request", then in each recipient virtual
  2221.    gateway, the lowest-numbered operational peer that receives the
  2222.    message responds to the original sender with its own VG POLICY
  2223.    message.
  2224.  
  2225. 3.4.3.  Communication Complexity
  2226.  
  2227.    We offer an example, to provide an estimate of the number of VGP
  2228.    messages exchanged within a domain, AD X, after a detected change in
  2229.    policy gateway connectivity.  Suppose that an adjacent domain, AD Y,
  2230.    partitions such that the partition is detectable through the exchange
  2231.    of UP/DOWN messages across a virtual gateway connecting AD X and AD
  2232.    Y.  Let V be the number of virtual gateways in AD X.  Suppose each
  2233.    virtual gateway contains P peer policy gateways, and no policy
  2234.    gateway is a member of multiple virtual gateways.  Then, within AD X,
  2235.    the detected partition will result in the following VGP message
  2236.    exchanges:
  2237.  
  2238.    - P policy gateways each receive at most P-1 PG CONNECT messages.
  2239.  
  2240.  
  2241.  
  2242. Steenstrup                                                     [Page 40]
  2243.  
  2244. RFC 1479                     IDPR Protocol                     July 1993
  2245.  
  2246.  
  2247.      Each policy gateway detecting the adjacent domain partition
  2248.      generates a PG CONNECT message and distributes it to each reachable
  2249.      peer in the virtual gateway.
  2250.  
  2251.    - P * (V-1) policy gateways each receive at most one VG CONNECT
  2252.      message.  The lowest-numbered operational policy gateway in the
  2253.      virtual gateway detecting the partition of the adjacent domain
  2254.      generates a VG CONNECT message and distributes it to a VG
  2255.      representative in all other virtual gateways connected to the
  2256.      domain.  In turn, each VG representative distributes the VG CONNECT
  2257.      message to each reachable peer within its virtual gateway.
  2258.  
  2259.    - P * (V-1) policy gateways each receive at most P-1 PG POLICY
  2260.      messages, and only if the domain has more than a single uniform
  2261.      transit policy.  Each policy gateway in each virtual gateway
  2262.      generates a PG POLICY message and distributes it to all reachable
  2263.      peers not currently reachable with respect to the given transit
  2264.      policy.
  2265.  
  2266.    - P * V policy gateways each receive at most V-1 VG POLICY messages,
  2267.      only if the domain has more than a single uniform transit policy.
  2268.      The lowest-numbered operational policy gateway in each virtual
  2269.      gateway generates a VG POLICY message and distributes it to a VG
  2270.      representative in all other virtual gateways containing at least
  2271.      one reachable member not currently reachable with respect to the
  2272.      given transit policy.  In turn, each VG representative distributes
  2273.      a VG POLICY message to each peer within its virtual gateway.
  2274.  
  2275. 3.5.  VGP Message Formats
  2276.  
  2277.    The virtual gateway protocol number is equal to 0.  We describe the
  2278.    contents of each type of VGP message below.
  2279.  
  2280. 3.5.1.  UP/DOWN
  2281.  
  2282.    The UP/DOWN message type is equal to 0.
  2283.  
  2284.     0                   1                   2                   3
  2285.     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
  2286.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2287.    |            SRC CMP            |            DST AD             |
  2288.    +-------------------------------+---------------+---------------+
  2289.    |            DST PG             |    PERIOD     |     STATE     |
  2290.    +-------------------------------+---------------+---------------+
  2291.  
  2292.    SRC CMP
  2293.         (16 bits) Numeric identifier for the domain component containing
  2294.         the issuing policy gateway.
  2295.  
  2296.  
  2297.  
  2298. Steenstrup                                                     [Page 41]
  2299.  
  2300. RFC 1479                     IDPR Protocol                     July 1993
  2301.  
  2302.  
  2303.    DST AD (16 bits) Numeric identifier for the destination domain.
  2304.  
  2305.    DST PG (16 bits) Numeric identifier for the destination policy
  2306.         gateway.
  2307.  
  2308.    PERIOD (8 bits) Length of the UP/DOWN message generation period, in
  2309.         seconds.
  2310.  
  2311.    STATE (8 bits) Perceived state (1 up, 0 down) of the direct
  2312.         connection from the perspective of the issuing policy gateway,
  2313.         contained in the right-most bit.
  2314.  
  2315. 3.5.2.  PG CONNECT
  2316.  
  2317.    The PG CONNECT message type is equal to 1.  PG CONNECT messages are
  2318.    not required for any virtual gateway containing exactly two policy
  2319.    gateways.
  2320.  
  2321.     0                   1                   2                   3
  2322.     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
  2323.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2324.    |            ADJ AD             |      VG       |     RQST      |
  2325.    +-------------------------------+---------------+---------------+
  2326.    |            NUM RCH            |           NUM UNRCH           |
  2327.    +-------------------------------+-------------------------------+
  2328.    For each reachable adjacent policy gateway:
  2329.    +-------------------------------+-------------------------------+
  2330.    |            ADJ PG             |            ADJ CMP            |
  2331.    +-------------------------------+-------------------------------+
  2332.    For each unreachable adjacent policy gateway:
  2333.    +-------------------------------+
  2334.    |            ADJ PG             |
  2335.    +-------------------------------+
  2336.  
  2337.    ADJ AD
  2338.         (16 bits) Numeric identifier for the adjacent domain.
  2339.  
  2340.    VG (8 bits) Numeric identifier for the virtual gateway.
  2341.  
  2342.    RQST (8 bits) Request for a PG CONNECT message (1 request, 0 no
  2343.         request) from each recipient peer, contained in the right-most
  2344.         bit.
  2345.  
  2346.    NUM RCH (16 bits) Number of adjacent policy gateways within the
  2347.         virtual gateway, which are directly-connected to and currently
  2348.         reachable from the issuing policy gateway.
  2349.  
  2350.    NUM UNRCH (16 bits) Number of adjacent policy gateways within the
  2351.  
  2352.  
  2353.  
  2354. Steenstrup                                                     [Page 42]
  2355.  
  2356. RFC 1479                     IDPR Protocol                     July 1993
  2357.  
  2358.  
  2359.         virtual gateway, which are directly-connected to but not
  2360.         currently reachable from the issuing policy gateway.
  2361.  
  2362.    ADJ PG (16 bits) Numeric identifier for a directly-connected adjacent
  2363.         policy gateway.
  2364.  
  2365.    ADJ CMP (16 bits) Numeric identifier for the domain component
  2366.         containing the reachable, directly-connected adjacent policy
  2367.         gateway.
  2368.  
  2369. 3.5.3.  PG POLICY
  2370.  
  2371.    The PG POLICY message type is equal to 2.  PG POLICY messages are not
  2372.    required for any virtual gateway containing exactly two policy
  2373.    gateways or for any domain with a single uniform transit policy.
  2374.  
  2375.     0                   1                   2                   3
  2376.     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
  2377.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2378.    |            ADJ AD             |      VG       |     RQST      |
  2379.    +-------------------------------+---------------+---------------+
  2380.    |            NUM TP             |
  2381.    +-------------------------------+
  2382.    For each transit policy associated with the virtual gateway:
  2383.    +-------------------------------+-------------------------------+
  2384.    |              TP               |            NUM VG             |
  2385.    +-------------------------------+-------------------------------+
  2386.    For each virtual gateway reachable via the transit policy:
  2387.    +-------------------------------+---------------+---------------+
  2388.    |            ADJ AD             |      VG       |    UNUSED     |
  2389.    +-------------------------------+---------------+---------------+
  2390.    |            NUM CMP            |            ADJ CMP            |
  2391.    +-------------------------------+-------------------------------+
  2392.  
  2393.    ADJ AD
  2394.         (16 bits) Numeric identifier for the adjacent domain.
  2395.  
  2396.    VG (8 bits) Numeric identifier for the virtual gateway.
  2397.  
  2398.    RQST (8 bits) Request for a PG POLICY message (1 request, 0 no
  2399.         request) from each recipient peer, contained in the right-most
  2400.         bit.
  2401.  
  2402.    NUM TP (8 bits) Number of transit policies configured to include the
  2403.         virtual gateway.
  2404.  
  2405.    TP (16 bits) Numeric identifier for a transit policy associated with
  2406.         the virtual gateway.
  2407.  
  2408.  
  2409.  
  2410. Steenstrup                                                     [Page 43]
  2411.  
  2412. RFC 1479                     IDPR Protocol                     July 1993
  2413.  
  2414.  
  2415.    NUM VG (16 bits) Number of virtual gateways reachable from the
  2416.         issuing policy gateway, via intra-domain routes supporting the
  2417.         transit policy.
  2418.  
  2419.    UNUSED (8 bits) Not currently used; must be set equal to 0.
  2420.  
  2421.    NUM CMP (16 bits) Number of adjacent domain components reachable via
  2422.         direct connections through the virtual gateway.
  2423.  
  2424.    ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
  2425.         component.
  2426.  
  2427. 3.5.4.  VG CONNECT
  2428.  
  2429.    The VG CONNECT message type is equal to 3.
  2430.  
  2431.     0                   1                   2                   3
  2432.     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
  2433.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2434.    |            ADJ AD             |      VG       |     RQST      |
  2435.    +-------------------------------+---------------+---------------+
  2436.    |            NUM PG             |
  2437.    +-------------------------------+
  2438.    For each reach policy gateway in the virtual gateway:
  2439.    +-------------------------------+-------------------------------+
  2440.    |              PG               |            NUM CMP            |
  2441.    +-------------------------------+-------------------------------+
  2442.    |            ADJ CMP            |
  2443.    +-------------------------------+
  2444.  
  2445.    ADJ AD
  2446.         (16 bits) Numeric identifier for the adjacent domain.
  2447.  
  2448.    VG (8 bits) Numeric identifier for the virtual gateway.
  2449.  
  2450.    RQST (8 bits) Request for a VG CONNECT message (1 request, 0 no
  2451.         request) from a recipient in each virtual gateway, contained in
  2452.         the right-most bit.
  2453.  
  2454.    NUM PG (16 bits) Number of mutually-reachable peer policy gateways in
  2455.         the virtual gateway.
  2456.  
  2457.    PG (16 bits) Numeric identifier for a peer policy gateway.
  2458.  
  2459.    NUM CMP (16 bits) Number of components of the adjacent domain
  2460.         reachable via direct connections from the policy gateway.
  2461.  
  2462.  
  2463.  
  2464.  
  2465.  
  2466. Steenstrup                                                     [Page 44]
  2467.  
  2468. RFC 1479                     IDPR Protocol                     July 1993
  2469.  
  2470.  
  2471.    ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
  2472.         component.
  2473.  
  2474. 3.5.5.  VG POLICY
  2475.  
  2476.    The VG POLICY message type is equal to 4.  VG POLICY messages are not
  2477.    required for any domain with a single uniform transit policy.
  2478.  
  2479.     0                   1                   2                   3
  2480.     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
  2481.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2482.    |            ADJ AD             |      VG       |     RQST      |
  2483.    +-------------------------------+---------------+---------------+
  2484.    |            NUM TP             |
  2485.    +-------------------------------+
  2486.    For each transit policy associated with the virtual gateway:
  2487.    +-------------------------------+-------------------------------+
  2488.    |              TP               |            NUM GRP            |
  2489.    +-------------------------------+-------------------------------+
  2490.    For each virtual gateway group reachable via the transit policy:
  2491.    +-------------------------------+-------------------------------+
  2492.    |            NUM VG             |            ADJ AD             |
  2493.    +---------------+---------------+-------------------------------+
  2494.    |     VG        |    UNUSED     |            NUM CMP            |
  2495.    +---------------+---------------+-------------------------------+
  2496.    |            ADJ CMP            |
  2497.    +-------------------------------+
  2498.  
  2499.    ADJ AD
  2500.         (16 bits) Numeric identifier for the adjacent domain.
  2501.  
  2502.    VG (8 bits) Numeric identifier for the virtual gateway.
  2503.  
  2504.    RQST (8 bits) Request for a VG POLICY message (1 request, 0 no
  2505.         request) from a recipient in each virtual gateway, contained in
  2506.         the right-most bit.
  2507.  
  2508.    NUM TP (16 bits) Number of transit policies configured to include the
  2509.         virtual gateway.
  2510.  
  2511.    TP (16 bits) Numeric identifier for a transit policy associated with
  2512.         the virtual gateway.
  2513.  
  2514.    NUM GRP (16 bits) Number of groups of virtual gateways, such that all
  2515.         members in a group are reachable from the issuing virtual
  2516.         gateway via intra-domain routes supporting the given transit
  2517.         policy.
  2518.  
  2519.  
  2520.  
  2521.  
  2522. Steenstrup                                                     [Page 45]
  2523.  
  2524. RFC 1479                     IDPR Protocol                     July 1993
  2525.  
  2526.  
  2527.    NUM VG (16 bits) Number of virtual gateways in a virtual gateway
  2528.         group.
  2529.  
  2530.    UNUSED (8 bits) Not currently used; must be set equal to 0.
  2531.  
  2532.    NUM CMP (16 bits) Number of adjacent domain components reachable via
  2533.         direct connections through the virtual gateway.
  2534.  
  2535.    ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
  2536.         component.
  2537.  
  2538.    Normally, each VG POLICY message will contain a single virtual
  2539.    gateway group.  However, if the issuing virtual gateway becomes
  2540.    partitioned such that peers are mutually reachable with respect to
  2541.    some transit policies but not others, virtual gateway groups may be
  2542.    necessary.  For example, let PG X and PG Y be two peers in VG A which
  2543.    configured to support transit policies 1 and 2.  Suppose that PG X
  2544.    and PG Y are reachable with respect to transit policy 1 but not with
  2545.    respect to transit policy 2.  Furthermore, suppose that PG X can
  2546.    reach members of VG B via intra-domain routes of transit policy 2 and
  2547.    that PG Y can reach members of VG C via intra-domain routes of
  2548.    transit policy 2.  Then the entry in the VG POLICY message issued by
  2549.    VG A will include, for transit policy 2, two groups of virtual
  2550.    gateways, one containing VG B and one containing VG C.
  2551.  
  2552. 3.5.6.  Negative Acknowledgements
  2553.  
  2554.    When a policy gateway receives an unacceptable VGP message that
  2555.    passes the CMTP validation checks, it includes, in its CMTP ACK, an
  2556.    appropriate VGP negative acknowledgement.  This information is placed
  2557.    in the INFORM field of the CMTP ACK (described previously in section
  2558.    2.4); the numeric identifier for each type of VGP negative
  2559.    acknowledgement is contained in the left-most 8 bits of the INFORM
  2560.    field.  Negative acknowledgements associated with VGP include the
  2561.    following types:
  2562.  
  2563.    1.  Unrecognized VGP message type.  Numeric identifier for the
  2564.        unrecognized message type (8 bits).
  2565.  
  2566.    2.  Out-of-date VGP message.
  2567.  
  2568.    3.  Unrecognized virtual gateway source.  Numeric identifier for the
  2569.        unrecognized virtual gateway including the adjacent domain
  2570.        identifier (16 bits) and the local identifier (8 bits).
  2571.  
  2572.  
  2573.  
  2574.  
  2575.  
  2576.  
  2577.  
  2578. Steenstrup                                                     [Page 46]
  2579.  
  2580. RFC 1479                     IDPR Protocol                     July 1993
  2581.  
  2582.  
  2583. 4.  Routing Information Distribution
  2584.  
  2585.    Each domain participating in IDPR generates and distributes its
  2586.    routing information messages to route servers throughout an
  2587.    internetwork.  IDPR routing information messages contain information
  2588.    about the transit policies in effect across the given domain and the
  2589.    virtual gateway connectivity to adjacent domains.  Route servers in
  2590.    turn use IDPR routing information to generate policy routes between
  2591.    source and destination domains.
  2592.  
  2593.    There are three different procedures for distributing IDPR routing
  2594.    information:
  2595.  
  2596.    - The flooding protocol.  In this case, a representative policy
  2597.      gateway in each domain floods its routing information messages to
  2598.      route servers in all other domains.
  2599.  
  2600.    - Remote route server communication.  In this case, a route server
  2601.      distributes its domain's routing information messages to route
  2602.      servers in specific destination domains, by encapsulating these
  2603.      messages within IDPR data messages.  Thus, a domain administrator
  2604.      may control the distribution of the domain's routing information by
  2605.      restricting routing information exchange with remote route servers.
  2606.      Currently, routing information distribution restrictions are not
  2607.      included in IDPR configuration information.
  2608.  
  2609.    - The route server query protocol.  In this case, a policy gateway or
  2610.      route server requests routing information from another route
  2611.      server, which in turn responds with routing information from its
  2612.      database.  The route server query protocol may be used for quickly
  2613.      updating the routing information maintained by a policy gateway
  2614.      or route server that has just been connected or reconnected to an
  2615.      internetwork.  It may also be used to retrieve routing information
  2616.      from domains that restrict distribution of their routing
  2617.      information.
  2618.  
  2619.    In this section, we describe the flooding protocol only.  In section
  2620.    5, we describe the route server query protocol, and in section 5.2,
  2621.    we describe communication between route servers in separate domains.
  2622.  
  2623.    Policy gateways and route servers use CMTP for reliable transport of
  2624.    IDPR routing information messages flooded between peer, neighbor, and
  2625.    adjacent policy gateways and between those policy gateways and route
  2626.    servers.  The issuing policy gateway must communicate to CMTP the
  2627.    maximum number of transmissions per routing information message,
  2628.    flood_ret, and the interval between routing information message
  2629.    retransmissions, flood_int microseconds.  The recipient policy
  2630.    gateway or route server must determine routing information message
  2631.  
  2632.  
  2633.  
  2634. Steenstrup                                                     [Page 47]
  2635.  
  2636. RFC 1479                     IDPR Protocol                     July 1993
  2637.  
  2638.  
  2639.    acceptability, as we describe in section 4.2.3 below.
  2640.  
  2641. 4.1.  AD Representatives
  2642.  
  2643.    We designate a single policy gateway, the "AD representative", for
  2644.    generating and distributing IDPR routing information about its
  2645.    domain, to ensure that the routing information distributed is
  2646.    consistent and unambiguous and to minimize the communication required
  2647.    for routing information distribution.  There is usually only a single
  2648.    AD representative per domain, namely the lowest-numbered operational
  2649.    policy gateway in the domain.  Within a domain, policy gateways need
  2650.    no explicit election procedure to determine the AD representative.
  2651.    Instead, all members of a set of policy gateways mutually reachable
  2652.    via intra-domain routes can agree on set membership and therefore on
  2653.    which member has the lowest number.
  2654.  
  2655.    A partitioned domain has as many AD representatives as it does domain
  2656.    components.  In fact, the numeric identifier for an AD representative
  2657.    is identical to the numeric identifier for a domain component.  One
  2658.    cannot normally predict when and where a domain partition will occur,
  2659.    and thus any policy gateway within a domain may become an AD
  2660.    representative at any time.  To prepare for the role of AD
  2661.    representative in the event of a domain partition, every policy
  2662.    gateway must continually monitor its domain's IDPR routing
  2663.    information, through VGP and through the intra-domain routing
  2664.    procedure.
  2665.  
  2666. 4.2.  Flooding Protocol
  2667.  
  2668.    An AD representative policy gateway uses unrestricted flooding among
  2669.    all domains to distribute its domain's IDPR routing information
  2670.    messages to route servers in an internetwork.  There are two kinds of
  2671.    IDPR routing information messages issued by each AD representative:
  2672.    CONFIGURATION and DYNAMIC messages.  Each CONFIGURATION message
  2673.    contains the transit policy information configured by the domain
  2674.    administrator, including for each transit policy, its identifier, its
  2675.    specification, and the sets of virtual gateways configured as
  2676.    mutually reachable via intra-domain routes supporting the given
  2677.    transit policy.  Each DYNAMIC message contains information about
  2678.    current virtual gateway connectivity to adjacent domains and about
  2679.    the sets of virtual gateways currently mutually reachable via intra-
  2680.    domain routes supporting the configured transit policies.
  2681.  
  2682.    The IDPR Flooding Protocol is similar to the flooding procedures
  2683.    described in [9]-[11].  Through flooding, the AD representative
  2684.    distributes its routing information messages to route servers in its
  2685.    own domain and in adjacent domains.  After generating a routing
  2686.    information message, the AD representative distributes a copy to each
  2687.  
  2688.  
  2689.  
  2690. Steenstrup                                                     [Page 48]
  2691.  
  2692. RFC 1479                     IDPR Protocol                     July 1993
  2693.  
  2694.  
  2695.    of its peers and to a selected VG representative (see section 3.1.4)
  2696.    in all other virtual gateways connected to the domain.  Each VG
  2697.    representative in turn distributes a copy of the routing information
  2698.    message to each of its peers.  We note that distribution of routing
  2699.    information messages among virtual gateways and among peers within a
  2700.    virtual gateway is identical to distribution of inter-VG messages in
  2701.    VGP, as described in section 3.1.3.
  2702.  
  2703.    Within a virtual gateway, each policy gateway distributes a copy of
  2704.    the routing information message:
  2705.  
  2706.    - To each route server in its configured set of route servers.  A
  2707.      domain administrator should ensure that each route server not
  2708.      contained within a policy gateway appears in the set of configured
  2709.      route servers for at least two distinct policy gateways.  Hence,
  2710.      such a route server will continue to receive routing information
  2711.      messages, even when one of the policy gateways becomes unreachable.
  2712.      However, the route server will normally receive duplicate copies of
  2713.      a routing information message.
  2714.  
  2715.    - To certain directly-connected adjacent policy gateways.  A policy
  2716.      gateway distributes a routing information message to a
  2717.      directly-connected adjacent policy gateway in an adjacent domain
  2718.      component, only when it is the lowest-numbered operational peer
  2719.      with a direct connection to the given domain component.  We note
  2720.      that each policy gateway knows, through information provided by
  2721.      VGP, which peers have direct connections to which components of
  2722.      the adjacent domain.  If the policy gateway has direct connections
  2723.      to more than one adjacent policy gateway in that domain component,
  2724.      it selects the routing information message recipient according to
  2725.      the order in which the adjacent policy gateways appear in its
  2726.      database, choosing the first one encountered.  This selection
  2727.      procedure ensures that a copy of the routing information message
  2728.      reaches each component of the adjacent domain, while limiting the
  2729.      number of copies distributed.
  2730.  
  2731.    Once a routing information message reaches an adjacent policy
  2732.    gateway, that policy gateway distributes copies of the message
  2733.    throughout its domain.  The adjacent policy gateway, acting as the
  2734.    first recipient of the routing information message in its domain,
  2735.    follows the same message distribution procedure as the AD
  2736.    representative in the source domain, as described above.  The
  2737.    flooding procedure terminates when all reachable route servers in an
  2738.    internetwork receive a copy of the routing information message.
  2739.  
  2740.    Neighbor policy gateways may receive copies of the same routing
  2741.    information message from different adjoining domains.  If two
  2742.    neighbor policy gateways receive the message copies simultaneously,
  2743.  
  2744.  
  2745.  
  2746. Steenstrup                                                     [Page 49]
  2747.  
  2748. RFC 1479                     IDPR Protocol                     July 1993
  2749.  
  2750.  
  2751.    they will distribute them to VG representatives in other virtual
  2752.    gateways within their domain, resulting in duplicate message
  2753.    distribution.  However, each policy gateway stops the spread of
  2754.    duplicate routing information messages as soon as it detects them, as
  2755.    described in section 4.2.3 below.  In the Internet, we expect
  2756.    simultaneous message receptions to be the exception rather than the
  2757.    rule, given the hierarchical structure of the current topology.
  2758.  
  2759. 4.2.1.  Message Generation
  2760.  
  2761.    An AD representative generates and distributes a CONFIGURATION
  2762.    message whenever there is a configuration change in a transit policy
  2763.    or virtual gateway associated with its domain.  This ensures that
  2764.    route servers maintain an up-to-date view of a domain's configured
  2765.    transit policies and adjacencies.  An AD representative may also
  2766.    distribute a CONFIGURATION message at a configurable period of
  2767.    conf_per (500) hours.  A CONFIGURATION message contains, for each
  2768.    configured transit policy, the identifier assigned by the domain
  2769.    administrator, the specification, and the set of associated "virtual
  2770.    gateway groups".  Each virtual gateway group comprises virtual
  2771.    gateways configured to be mutually reachable via intra-domain routes
  2772.    of the given transit policy.  Accompanying each virtual gateway
  2773.    listed is an indication of whether the virtual gateway is configured
  2774.    to be a domain entry point, a domain exit point, or both according to
  2775.    the given transit policy.  The CONFIGURATION message also contains
  2776.    the set of local route servers that the domain administrator has
  2777.    configured to be available to IDPR clients in other domains.
  2778.  
  2779.    An AD representative generates and distributes a DYNAMIC message
  2780.    whenever there is a change in currently supported transit policies or
  2781.    in current virtual gateway connectivity associated with its domain.
  2782.    This ensures that route servers maintain an up-to-date view of a
  2783.    domain's supported transit policies and existing adjacencies and how
  2784.    they differ from those configured for the domain.  Specifically, an
  2785.    AD representative generates a DYNAMIC message whenever there is a
  2786.    change in the connectivity, through the given domain and with respect
  2787.    to a configured transit policy, between two components of adjoining
  2788.    domains.  An AD representative may also distribute a DYNAMIC message
  2789.    at a configurable period of dyn_per (24) hours.  A DYNAMIC message
  2790.    contains, for each configured transit policy, its identifier,
  2791.    associated virtual gateway groups, and domain components reachable
  2792.    through virtual gateways in each group.  Each DYNAMIC message also
  2793.    contains the set of currently "unavailable", either down or
  2794.    unreachable, virtual gateways in the domain.
  2795.  
  2796.    We note that each virtual gateway group expressed in a DYNAMIC
  2797.    message may be a proper subset of one of the corresponding virtual
  2798.    gateway groups expressed in a CONFIGURATION message.  For example,
  2799.  
  2800.  
  2801.  
  2802. Steenstrup                                                     [Page 50]
  2803.  
  2804. RFC 1479                     IDPR Protocol                     July 1993
  2805.  
  2806.  
  2807.    suppose that, for a given domain, the virtual gateway group (VG
  2808.    A,...,VG E) were configured for a transit policy such that each
  2809.    virtual gateway was both a domain entry and exit point.  Thus, all
  2810.    virtual gateways in this group are configured to be mutually
  2811.    reachable via intra-domain routes of the given transit policy.  Now
  2812.    suppose that VG E becomes unreachable because of a power failure and
  2813.    furthermore that the remaining virtual gateways form two distinct
  2814.    groups, (VG A,VG B) and (VG C,VG D), such that although virtual
  2815.    gateways in both groups are still mutually reachable via some intra-
  2816.    domain routes they are no longer mutually reachable via any intra-
  2817.    domain routes of the given transit policy.  In this case, the virtual
  2818.    gateway groups for the given transit policy now become (VG A,VG B)
  2819.    and (VG C,VG D); VG E is listed as an unavailable virtual gateway.
  2820.  
  2821.    A route server uses information about the set of unavailable virtual
  2822.    gateways to determine which of its routes are no longer viable, and
  2823.    it subsequently removes such routes from its route database.
  2824.    Although route servers could determine the set of unavailable virtual
  2825.    gateways using information about configured virtual gateways and
  2826.    currently reachable virtual gateways, the associated processing cost
  2827.    is high.  In particular, a route server would have to examine all
  2828.    virtual gateway groups listed in a DYNAMIC message to determine
  2829.    whether there are any unavailable virtual gateways in the given
  2830.    domain.  To reduce the message processing at each route server, we
  2831.    have chosen to include the set of unavailable virtual gateways in
  2832.    each DYNAMIC message.
  2833.  
  2834.    In order to construct a DYNAMIC message, an AD representative
  2835.    assembles information gathered from intra-domain routing and from
  2836.    VGP.  Specifically, the AD representative uses the following
  2837.    information:
  2838.  
  2839.    - VG CONNECT and UP/DOWN messages to determine the state, up or down,
  2840.      of each of its domain's virtual gateways and the adjacent domain
  2841.      components reachable through a given virtual gateway.
  2842.  
  2843.    - Intra-domain routing information to determine, for each of its
  2844.      domain's transit policies, whether a given virtual gateway in the
  2845.      domain is reachable with respect to that transit policy.
  2846.  
  2847.    - VG POLICY messages to determine the connectivity of adjoining
  2848.      domain components, across the given domain and with respect to a
  2849.      configured transit policy, such that these components are adjacent
  2850.      to virtual gateways not currently reachable from the AD
  2851.      representative's virtual gateway according to the given transit
  2852.      policy.
  2853.  
  2854.  
  2855.  
  2856.  
  2857.  
  2858. Steenstrup                                                     [Page 51]
  2859.  
  2860. RFC 1479                     IDPR Protocol                     July 1993
  2861.  
  2862.  
  2863. 4.2.2.  Sequence Numbers
  2864.  
  2865.    Each IDPR routing information message carries a sequence number
  2866.    which, when used in conjunction with the timestamp carried in the
  2867.    CMTP message header, determines the recency of the message.  An AD
  2868.    representative assigns a sequence number to each routing information
  2869.    message it generates, depending upon its internal clock time:
  2870.  
  2871.    - The AD representative sets the sequence number to 0, if its
  2872.      internal clock time is greater than the timestamp in its previously
  2873.      generated routing information message.
  2874.  
  2875.    - The AD representative sets the sequence number to 1 greater than
  2876.      the sequence number in its previously generated routing information
  2877.      message, if its internal clock time equals the timestamp for its
  2878.      previously generated routing information message and if the
  2879.      previous sequence number is less than the maximum value
  2880.      (currently 2**16 - 1).  If the previous sequence number equals the
  2881.      maximum value, the AD representative waits until its internal clock
  2882.      time exceeds the timestamp in its previously generated routing
  2883.      information message and then sets the sequence number to 0.
  2884.  
  2885.    In general, we do not expect generation of multiple distinct IDPR
  2886.    routing information messages carrying identical timestamps, and so
  2887.    the sequence number may seem superfluous.  However, the sequence
  2888.    number may become necessary during synchronization of an AD
  2889.    representative's internal clock.  In particular, the AD
  2890.    representative may need to freeze the clock value during
  2891.    synchronization, and thus distinct sequence numbers serve to
  2892.    distinguish routing information messages generated during the clock
  2893.    synchronization interval.
  2894.  
  2895. 4.2.3.  Message Acceptance
  2896.  
  2897.    Prior to a policy gateway forwarding a routing information message or
  2898.    a route server incorporating routing information into its routing
  2899.    information database, the policy gateway or route server assesses
  2900.    routing information message acceptability.  An IDPR routing
  2901.    information message is "acceptable" if:
  2902.  
  2903.    - It passes the CMTP validation checks.
  2904.  
  2905.    - Its timestamp is less than conf_old (530) hours behind the
  2906.      recipient's internal clock time for CONFIGURATION messages and less
  2907.      than dyn_old (25) hours behind the recipient's internal clock time
  2908.      for DYNAMIC messages.
  2909.  
  2910.    - Its timestamp and sequence number indicate that it is more recent
  2911.  
  2912.  
  2913.  
  2914. Steenstrup                                                     [Page 52]
  2915.  
  2916. RFC 1479                     IDPR Protocol                     July 1993
  2917.  
  2918.  
  2919.      than the currently-stored routing information from the given
  2920.      domain.  If there is no routing information currently stored from
  2921.      the given domain, then the routing information message contains, by
  2922.      default, the more recent information.
  2923.  
  2924.    Policy gateways acknowledge and forward acceptable IDPR routing
  2925.    information messages, according to the flooding protocol described in
  2926.    section 4.2 above.  Moreover, each policy gateway retains the
  2927.    timestamp and sequence number for the most recently accepted routing
  2928.    information message from each domain and uses these values to
  2929.    determine acceptability of routing information messages received in
  2930.    the future.  Route servers acknowledge the receipt of acceptable
  2931.    routing information messages and incorporate the contents of these
  2932.    messages into their routing information databases, contingent upon
  2933.    criteria discussed in section 4.2.4 below; however, they do not
  2934.    participate in the flooding protocol.  We note that when a policy
  2935.    gateway or route server first returns to service, it immediately
  2936.    updates its routing information database with routing information
  2937.    obtained from another route server, using the route server query
  2938.    protocol described in section 5.
  2939.  
  2940.    An AD representative takes special action upon receiving an
  2941.    acceptable routing information message, supposedly generated by
  2942.    itself but originally obtained from a policy gateway or route server
  2943.    other than itself.  There are at least three possible reasons for the
  2944.    occurrence of this event:
  2945.  
  2946.    - The routing information message has been corrupted in a way that is
  2947.      not detectable by the integrity/authentication value.
  2948.  
  2949.    - The AD representative has experienced a memory error.
  2950.  
  2951.    - Some other entity is generating routing information messages on
  2952.      behalf of the AD representative.
  2953.  
  2954.    In any case, the AD representative logs the event for network
  2955.    management.  Moreover, the AD representative must reestablish its own
  2956.    routing information messages as the most recent for its domain.  To
  2957.    do so, the AD representative waits until its internal clock time
  2958.    exceeds the value of the timestamp in the received routing
  2959.    information message and then generates a new routing information
  2960.    message using the currently-stored domain routing information
  2961.    supplied by VGP and by the intra-domain routing procedure.  Note that
  2962.    the length of time the AD representative must wait to generate the
  2963.    new message is at most cmtp_new (300) seconds, the maximum CMTP-
  2964.    tolerated difference between the received message's timestamp and the
  2965.    AD representative's internal clock time.
  2966.  
  2967.  
  2968.  
  2969.  
  2970. Steenstrup                                                     [Page 53]
  2971.  
  2972. RFC 1479                     IDPR Protocol                     July 1993
  2973.  
  2974.  
  2975.    IDPR routing information messages that pass the CMTP validity checks
  2976.    but appear less recent than stored routing information are
  2977.    unacceptable.  Policy gateways do not forward unacceptable routing
  2978.    information messages, and route servers do not incorporate the
  2979.    contents of unacceptable routing information messages into their
  2980.    routing information databases.  Instead, the recipient of an
  2981.    unacceptable routing information message acknowledges the message in
  2982.    one of two ways:
  2983.  
  2984.    - If the routing information message timestamp and sequence number
  2985.      equal to the timestamp and sequence number associated with the
  2986.      stored routing information for the given domain, the recipient
  2987.      assumes that the routing information message is a duplicate and
  2988.      acknowledges the message.
  2989.  
  2990.    - If the routing information message timestamp and sequence number
  2991.      indicate that the message is less recent than the stored routing
  2992.      information for the domain, the recipient acknowledges the message
  2993.      with an indication that the routing information it contains is
  2994.      out-of-date.  Such a negative acknowledgement is a signal to the
  2995.      sender of the routing information message to request more up-to-
  2996.      date routing information from a route server, using the route
  2997.      server query protocol.  Furthermore, if the recipient of the out-
  2998.      of-date routing information message is a route server, it
  2999.      regenerates a routing information message from its own routing
  3000.      information database and forwards the message to the sender.  The
  3001.      sender may in turn propagate this more recent routing information
  3002.      message to other policy gateways and route servers.
  3003.  
  3004. 4.2.4.  Message Incorporation
  3005.  
  3006.    A route server usually stores the entire contents of an acceptable
  3007.    IDPR routing information message in its routing information database,
  3008.    so that it has access to all advertised transit policies when
  3009.    generating a route and so that it can regenerate routing information
  3010.    messages at a later point in time if requested to do so by another
  3011.    route server or policy gateway.  However, a route server may elect
  3012.    not to store all routing information message contents.  In
  3013.    particular, the route server need not store any transit policy that
  3014.    excludes the route server's domain as a source or any routing
  3015.    information from a domain that the route server's domain's source
  3016.    policies exclude for transit.  Selective storing of routing
  3017.    information message contents simplifies the route generation
  3018.    procedure since it reduces the search space of possible routes, and
  3019.    it limits the amount of route server memory devoted to routing
  3020.    information.  However, selective storing of routing information also
  3021.    means that the route server cannot always regenerate the original
  3022.    routing information message, if requested to do so by another route
  3023.  
  3024.  
  3025.  
  3026. Steenstrup                                                     [Page 54]
  3027.  
  3028. RFC 1479                     IDPR Protocol                     July 1993
  3029.  
  3030.  
  3031.    server or policy gateway.
  3032.  
  3033.    An acceptable IDPR routing information message may contain transit
  3034.    policy information that is not well-defined according to the route
  3035.    server's perception.  A CONFIGURATION message may contain an
  3036.    unrecognized domain, virtual gateway, or transit policy attribute,
  3037.    such as user class access restrictions or offered service.  In this
  3038.    case, "unrecognized" means that the value in the routing information
  3039.    message is not listed in the route server's configuration database,
  3040.    as described previously in section 1.8.2.  A DYNAMIC message may
  3041.    contain an unrecognized transit policy or virtual gateway.  In this
  3042.    case, "unrecognized" means that the transit policy or virtual gateway
  3043.    was not listed in the most recent CONFIGURATION message for the given
  3044.    domain.
  3045.  
  3046.    Each route server can always parse an acceptable routing information
  3047.    messsage, even if some of the information is not well-defined, and
  3048.    thus can always use the information that it does recognize.
  3049.    Therefore, a route server can store the contents of acceptable
  3050.    routing information messages from domains in which it is interested,
  3051.    regardless of whether all contents appear to be well-defined at
  3052.    present.  If a routing message contains unrecognized information, the
  3053.    route server may attempt to obtain the additional information it
  3054.    needs to decipher the unrecognized information.  For a CONFIGURATION
  3055.    message, the route server logs the event for network management; for
  3056.    a DYNAMIC message, the route server requests, from another route
  3057.    server, the most recent CONFIGURATION message for the domain in
  3058.    question.
  3059.  
  3060.    When a domain is partitioned, each domain component has its own AD
  3061.    representative, which generates routing information messages on
  3062.    behalf of that component.  Discovery of a domain partition prompts
  3063.    the AD representative for each domain component to generate and
  3064.    distribute a DYNAMIC message.  In this case, a route server receives
  3065.    and stores more than one routing information message at a time for
  3066.    the given domain, namely one for each domain component.
  3067.  
  3068.    When the partition heals, the AD representative for the entire domain
  3069.    generates and distributes a DYNAMIC message.  In each route server's
  3070.    routing information database, the new DYNAMIC message does not
  3071.    automatically replace all of the currently-stored DYNAMIC messages
  3072.    for the given domain.  Instead, the new message only replaces that
  3073.    message whose AD representative matches the AD representative for the
  3074.    new message.  The other DYNAMIC messages, generated during the period
  3075.    over which the partition occurred, remain in the routing information
  3076.    database until they attain their maximum lifetime, as described in
  3077.    section 4.2.5 below.  Such stale information may lead to the
  3078.    generation of routes that result in path setup failures and hence the
  3079.  
  3080.  
  3081.  
  3082. Steenstrup                                                     [Page 55]
  3083.  
  3084. RFC 1479                     IDPR Protocol                     July 1993
  3085.  
  3086.  
  3087.    selection of alternative routes.  To reduce the chances of path setup
  3088.    failures, we will investigate, for a future version of IDPR,
  3089.    mechanisms for removing partition-related DYNAMIC messages
  3090.    immediately after a partition disappears.
  3091.  
  3092. 4.2.5.  Routing Information Database
  3093.  
  3094.    We expect that most of the IDPR routing information stored in a
  3095.    routing information database will remain viable for long periods of
  3096.    time, perhaps until a domain reconfiguration occurs.  By "viable", we
  3097.    mean that the information reflects the current state of the domain
  3098.    and hence may be used successfully for generating policy routes.  To
  3099.    reduce the probability of retaining stale routing information, a
  3100.    route server imposes a maximum lifetime on each database entry,
  3101.    initialized when it incorporates an accepted entry into its routing
  3102.    information database.  The maximum lifetime should be longer than the
  3103.    corresponding message generation period, so that the database entry
  3104.    is likely to be refreshed before it attains its maximum lifetime.
  3105.  
  3106.    Each CONFIGURATION message stored in the routing information database
  3107.    has a maximum lifetime of conf_old (530) hours; each DYNAMIC message
  3108.    stored in the routing information database has a maximum lifetime of
  3109.    dyn_old (25) hours.  Periodic generation of routing information
  3110.    messages makes it unlikely that any routing information message will
  3111.    remain in a routing information database for its full lifetime.
  3112.    However, a routing information message may attain its maximum
  3113.    lifetime in a route server that is separated from a internetwork for
  3114.    a long period of time.
  3115.  
  3116.    When an IDPR routing information message attains its maximum lifetime
  3117.    in a routing information database, the route server removes the
  3118.    message contents from its database, so that it will not generate new
  3119.    routes with the outdated routing information nor distribute old
  3120.    routing information in response to requests from other route servers
  3121.    or policy gateways.  Nevertheless, the route server continues to
  3122.    dispense routes previously generated with the old routing
  3123.    information, as long as path setup (see section 7) for these routes
  3124.    succeeds.
  3125.  
  3126.    The route server treats routing information message lifetime
  3127.    expiration differently, depending on the type of routing information
  3128.    message.  When a CONFIGURATION message expires, the route server
  3129.    requests, from another route server, the most recent CONFIGURATION
  3130.    message issued for the given domain.  When a DYNAMIC message expires,
  3131.    the route server does not initially attempt to obtain more recent
  3132.    routing information.  Instead, if route generation is necessary, the
  3133.    route server uses the routing information contained in the
  3134.    corresponding CONFIGURATION message for the given domain.  Only if
  3135.  
  3136.  
  3137.  
  3138. Steenstrup                                                     [Page 56]
  3139.  
  3140. RFC 1479                     IDPR Protocol                     July 1993
  3141.  
  3142.  
  3143.    there is a path setup failure (see section 7.4) involving the given
  3144.    domain does the route server request, from another route server, the
  3145.    most recent DYNAMIC message issued for the given domain.
  3146.  
  3147. 4.3.  Routing Information Message Formats
  3148.  
  3149.    The flooding protocol number is equal to 1.  We describe the contents
  3150.    of each type of routing information message below.
  3151.  
  3152. 4.3.1.  CONFIGURATION
  3153.  
  3154.    The CONFIGURATION message type is equal to 0.
  3155.  
  3156.     0                   1                   2                   3
  3157.     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
  3158.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3159.    |            AD CMP             |              SEQ              |
  3160.    +-------------------------------+-------------------------------+
  3161.    |            NUM TP             |            NUM RS             |
  3162.    +-------------------------------+-------------------------------+
  3163.    |              RS               |
  3164.    +-------------------------------+
  3165.    For each transit policy configured for the domain:
  3166.    +-------------------------------+-------------------------------+
  3167.    |              TP               |            NUM ATR            |
  3168.    +-------------------------------+-------------------------------+
  3169.    For each attribute of the transit policy:
  3170.    +-------------------------------+-------------------------------+
  3171.    |            ATR TYP            |            ATR LEN            |
  3172.    +-------------------------------+-------------------------------+
  3173.    For the source/destination access restrictions attribute:
  3174.    +-------------------------------+
  3175.    |          NUM AD GRP           |
  3176.    +-------------------------------+
  3177.    For each domain group in the source/destination access restrictions:
  3178.    +-------------------------------+-------------------------------+
  3179.    |            NUM AD             |              AD               |
  3180.    +---------------+---------------+-------------------------------+
  3181.    |    AD FLGS    |    NUM HST    |            HST SET            |
  3182.    +---------------+---------------+-------------------------------+
  3183.    For the temporal access restrictions attribute:
  3184.    +-------------------------------+
  3185.    |            NUM TIM            |
  3186.    +-------------------------------+
  3187.  
  3188.  
  3189.  
  3190.  
  3191.  
  3192.  
  3193.  
  3194. Steenstrup                                                     [Page 57]
  3195.  
  3196. RFC 1479                     IDPR Protocol                     July 1993
  3197.  
  3198.  
  3199.    For each set of times in the temporal access restrictions:
  3200.    +---------------+-----------------------------------------------+
  3201.    |   TIM FLGS    |                   DURATION                    |
  3202.    +---------------+-----------------------------------------------+
  3203.    |                             START                             |
  3204.    +-------------------------------+-------------------------------+
  3205.    |            PERIOD             |            ACTIVE             |
  3206.    +-------------------------------+-------------------------------+
  3207.    For the user class access restrictions attribute:
  3208.    +-------------------------------+
  3209.    |            NUM UCI            |
  3210.    +-------------------------------+
  3211.    For each UCI in the user class access restrictions:
  3212.    +---------------+
  3213.    |      UCI      |
  3214.    +---------------+
  3215.    For each offered service attribute:
  3216.    +---------------------------------------------------------------+
  3217.    |                            OFR SRV                            |
  3218.    +---------------------------------------------------------------+
  3219.    For the virtual gateway access restrictions attribute:
  3220.    +-------------------------------+
  3221.    |           NUM VG GRP          |
  3222.    +-------------------------------+
  3223.    For each virtual gateway group in the virtual gateway access
  3224.    restrictions:
  3225.    +-------------------------------+-------------------------------+
  3226.    |            NUM VG             |            ADJ AD             |
  3227.    +---------------+---------------+-------------------------------+
  3228.    |      VG       |    VG FLGS    |
  3229.    +---------------+---------------+
  3230.  
  3231.    AD CMP
  3232.         (16 bits) Numeric identifier for the domain component containing
  3233.         the AD representative policy gateway.
  3234.  
  3235.    SEQ (16 bits) Routing information message sequence number.
  3236.  
  3237.    NUM TP (16 bits) Number of transit policy specifications contained in
  3238.         the routing information message.
  3239.  
  3240.    NUM RS (16 bits) Number of route servers advertised to serve clients
  3241.         outside of the domain.
  3242.  
  3243.    RS (16 bits) Numeric identifier for a route server.
  3244.  
  3245.    TP (16 bits) Numeric identifier for a transit policy specification.
  3246.  
  3247.  
  3248.  
  3249.  
  3250. Steenstrup                                                     [Page 58]
  3251.  
  3252. RFC 1479                     IDPR Protocol                     July 1993
  3253.  
  3254.  
  3255.    NUM ATR (16 bits) Number of attributes associated with the transit
  3256.         policy.
  3257.  
  3258.    ATR TYP (16 bits) Numeric identifier for a type of attribute.  Valid
  3259.         attributes include the following types:
  3260.  
  3261.    - Set of  virtual  gateway access restrictions   (see  section 1.4.2)
  3262.      associated with the transit policy (variable).  This attribute must
  3263.      be included.
  3264.  
  3265.    - Set of source/destination access restrictions (see section 1.4.2)
  3266.      associated with the transit policy (variable).  This attribute may
  3267.      be omitted.  Absence of this attribute implies that traffic from
  3268.      any source to any destination is acceptable.
  3269.  
  3270.    - Set of temporal access restrictions (see section 1.4.2) associated
  3271.      with the transit policy (variable).  This attribute may be omitted.
  3272.      Absence of this attribute implies that the transit policy applies
  3273.      at all times.
  3274.  
  3275.    - Set of user class access restrictions (see section 1.4.2)
  3276.      associated with the transit policy (variable).  This attribute may
  3277.      be omitted.  Absence of this attribute implies that traffic from
  3278.      any user class is acceptable.
  3279.  
  3280.    - Average delay in milliseconds (16 bits).  This attribute may be
  3281.      omitted.
  3282.  
  3283.    - Delay variation in milliseconds (16 bits).  This attribute may be
  3284.      omitted.
  3285.  
  3286.    - Average available bandwidth in bits per second (48 bits).  This
  3287.      attribute may be omitted.
  3288.  
  3289.    - Available bandwidth variation in bits per second (48 bits).  This
  3290.      attribute may be omitted.
  3291.  
  3292.    - MTU in bytes (16 bits).  This attribute may be omitted.
  3293.  
  3294.    - Charge per byte in thousandths of a cent (16 bits). This attribute
  3295.      may be omitted.
  3296.  
  3297.    - Charge per message in thousandths of a cent (16 bits).  This
  3298.      attribute may be omitted.
  3299.  
  3300.    - Charge for session time in thousandths of a cent per second (16
  3301.      bits).  This attribute may be omitted.  Absence of any charge
  3302.      attribute implies that the domain provides free transit service.
  3303.  
  3304.  
  3305.  
  3306. Steenstrup                                                     [Page 59]
  3307.  
  3308. RFC 1479                     IDPR Protocol                     July 1993
  3309.  
  3310.  
  3311.    ATR LEN (16 bits) Length of an attribute in bytes, beginning with the
  3312.    subsequent field.
  3313.  
  3314.    NUM AD GRP (16 bits) Number of source/destination domain groups (see
  3315.    section 1.4.2) associated with the source/destination access
  3316.    restrictions.
  3317.  
  3318.    NUM AD (16 bits) Number of domains or sets of domains in a domain
  3319.    group.
  3320.  
  3321.    AD (16 bits) Numeric identifier for a domain or domain set.
  3322.  
  3323.    AD FLGS (8 bits) Set of five flags indicating how to interpret the AD
  3324.    field, contained in the right-most bits.  Proceeding left to right,
  3325.    the first flag indicates whether the transit policy applies to all
  3326.    domains or to specific domains (1 all, 0 specific), and when set to
  3327.    1, causes the second and third flags to be ignored.  The second flag
  3328.    indicates whether the domain identifier signifies a single domain or
  3329.    a domain set (1 single, 0 set).  The third flag indicates whether the
  3330.    transit policy applies to the given domain or domain set (1 applies,
  3331.    0 does not apply) and is used for representing complements of sets of
  3332.    domains.  The fourth flag indicates whether the domain is a source (1
  3333.    source, 0 not source).  The fifth flag indicates whether the domain
  3334.    is a destination (1 destination, 0 not destination).  At least one of
  3335.    the fourth and fifth flags must be set to 1.
  3336.  
  3337.    NUM HST (8 bits) Number of "host sets" (see section 1.4.2) associated
  3338.    with a particular domain or domain set.  The value 0 indicates that
  3339.    all hosts in the given domain or domain set are acceptable sources or
  3340.    destinations, as specified by the fourth and fifth AD flags.
  3341.  
  3342.    HST SET (16 bits) Numeric identifier for a host set.
  3343.  
  3344.    NUM TIM (16 bits) Number of time specifications associated with the
  3345.    temporal access restrictions.  Each time specification is split into
  3346.    a set of continguous identical periods, as we describe below.
  3347.  
  3348.    TIM FLGS (8 bits) Set of two flags indicating how to combine the time
  3349.    specifications, contained in the right-most bits.  Proceeding left to
  3350.    right, the first flag indicates whether the transit policy applies
  3351.    during the periods specified in the time specification (1 applies, 0
  3352.    does not apply) and is used for representing complements of policy
  3353.    applicability intervals.  The second flag indicates whether the time
  3354.    specification takes precedence over the previous time specifications
  3355.    listed (1 precedence, 0 no precedence).  Precedence is equivalent to
  3356.    the boolean OR and AND operators, in the following sense.  At any
  3357.    given instant, a transit policy either applies or does not apply,
  3358.    according to a given time specification, and we can assign a boolean
  3359.  
  3360.  
  3361.  
  3362. Steenstrup                                                     [Page 60]
  3363.  
  3364. RFC 1479                     IDPR Protocol                     July 1993
  3365.  
  3366.  
  3367.    value to the state of policy applicability according to a given time
  3368.    specification.  If the second flag assumes the value 1 for a given
  3369.    time specification, that indicates the boolean operator OR should be
  3370.    applied to the values of policy applicability, according to the given
  3371.    time specification and to all previously listed time specifications.
  3372.    If the second flag assumes the value 0 for a given time
  3373.    specification, that indicates the boolean operator AND should be
  3374.    applied to the values of policy applicability, according to the given
  3375.    time specification and to all previously listed time specifications.
  3376.  
  3377.    DURATION (24 bits) Length of the time specification duration, in
  3378.    minutes.  A value of 0 indicates an infinite duration.
  3379.  
  3380.    START (32 bits) Time at which the time specification first takes
  3381.    effect, in seconds elapsed since 1 January 1970 0:00 GMT.
  3382.  
  3383.    PERIOD (16 bits) Length of each time period within the time
  3384.    specification, in minutes.
  3385.  
  3386.    ACTIVE (16 bits) Length of the policy applicable interval during each
  3387.    time period, in minutes from the beginning of the time period.
  3388.  
  3389.    NUM UCI (16 bits) Number of user classes associated with the user
  3390.    class access restrictions.
  3391.  
  3392.    UCI (8 bits) Numeric identifier for a user class.
  3393.  
  3394.    NUM VG GRP (16 bits) Number of virtual gateway groups (see section
  3395.    1.4.2) associated with the virtual gateway access restrictions.
  3396.  
  3397.    NUM VG (16 bits) Number of virtual gateways in a virtual gateway
  3398.    group.
  3399.  
  3400.    ADJ AD (16 bits) Numeric identifier for the adjacent domain to which
  3401.    a virtual gateway connects.
  3402.  
  3403.    VG (8 bits) Numeric identifier for a virtual gateway.
  3404.  
  3405.    VG FLGS (8 bits) Set of two flags indicating how to interpret the VG
  3406.    field, contained in the right-most bits.  Proceeding left to right,
  3407.    the first flag indicates whether the virtual gateway is a domain
  3408.    entry point (1 entry, 0 not entry).  The second flag indicates
  3409.    whether the virtual gateway is a domain exit point (1 exit, 0 not
  3410.    exit).  At least one of the first and second flags must be set to 1.
  3411.  
  3412.  
  3413.  
  3414.  
  3415.  
  3416.  
  3417.  
  3418. Steenstrup                                                     [Page 61]
  3419.  
  3420. RFC 1479                     IDPR Protocol                     July 1993
  3421.  
  3422.  
  3423. 4.3.2.  DYNAMIC
  3424.  
  3425.    The DYNAMIC message type is equal to 1.
  3426.  
  3427.     0                   1                   2                   3
  3428.     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
  3429.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3430.    |            AD CMP             |              SEQ              |
  3431.    +-------------------------------+-------------------------------+
  3432.    |           UNAVL VG            |            NUM PS             |
  3433.    +-------------------------------+-------------------------------+
  3434.    For each unavailable virtual gateway in the domain:
  3435.    +-------------------------------+---------------+---------------+
  3436.    |            ADJ AD             |      VG       |    UNUSED     |
  3437.    +-------------------------------+---------------+---------------+
  3438.    For each set of transit policies for the domain:
  3439.    +-------------------------------+-------------------------------+
  3440.    |            NUM TP             |          NUM VG GRP           |
  3441.    +-------------------------------+-------------------------------+
  3442.    |              TP               |
  3443.    +-------------------------------+
  3444.    For each virtual gateway group associated with the transit policy
  3445.    set:
  3446.    +-------------------------------+-------------------------------+
  3447.    |            NUM VG             |            ADJ AD             |
  3448.    +---------------+---------------+-------------------------------+
  3449.    |      VG       |    VG FLGS    |            NUM CMP            |
  3450.    +---------------+---------------+-------------------------------+
  3451.    |            ADJ CMP            |
  3452.    +-------------------------------+
  3453.  
  3454.    AD CMP
  3455.         (16 bits) Numeric identifier for the domain component containing
  3456.         the AD representative policy gateway.
  3457.  
  3458.    SEQ (16 bits) Routing information message sequence number.
  3459.  
  3460.    UNAVL VG (16 bits) Number of virtual gateways in the domain component
  3461.         that are currently unavailable via any intra-domain routes.
  3462.  
  3463.    NUM PS (16 bits) Number of sets of transit policies listed.  Transit
  3464.         policy sets provide a mechanism for reducing the size of DYNAMIC
  3465.         messages.  A single set of virtual gateway groups applies to all
  3466.         transit policies in a given set.
  3467.  
  3468.    ADJ AD (16 bits) Numeric identifier for the adjacent domain to which
  3469.         a virtual gateway connects.
  3470.  
  3471.  
  3472.  
  3473.  
  3474. Steenstrup                                                     [Page 62]
  3475.  
  3476. RFC 1479                     IDPR Protocol                     July 1993
  3477.  
  3478.  
  3479.    VG (8 bits) Numeric identifier for a virtual gateway.
  3480.  
  3481.    UNUSED (8 bits) Not currently used; must be set equal to 0.
  3482.  
  3483.    NUM TP (16 bits) Number of transit policies in a set.
  3484.  
  3485.    NUM VGGRP (16 bits) Number of virtual gateway groups currently
  3486.         associated with the transit policy set.
  3487.  
  3488.    TP (16 bits) Numeric identifier for a transit policy.
  3489.  
  3490.    NUM VG (16 bits) Number of virtual gateways in a virtual gateway
  3491.         group.
  3492.  
  3493.    VG FLGS (8 bits) Set of two flags indicating how to interpret the VG
  3494.         field, contained in the right-most bits.  Proceeding left to
  3495.         right, the first flag indicates whether the virtual gateway is a
  3496.         domain entry point (1 entry, 0 not entry).  The second flag
  3497.         indicates whether the virtual gateway is a domain exit point (1
  3498.         exit, 0 not exit).  At least one of the first and second flags
  3499.         must be set to 1.
  3500.  
  3501.    NUM CMP (16 bits) Number of adjacent domain components reachable via
  3502.         direct connections through the virtual gateway.
  3503.  
  3504.    ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
  3505.         component.
  3506.  
  3507. 4.3.3.  Negative Acknowledgements
  3508.  
  3509.    When a policy gateway or route server receives an unacceptable IDPR
  3510.    routing information message that passes the CMTP validation checks,
  3511.    it includes, in its CMTP ACK, an appropriate negative
  3512.    acknowledgement.  This information is placed in the INFORM field of
  3513.    the CMTP ACK (described previously in section 2.4); the numeric
  3514.    identifier for each type of routing information message negative
  3515.    acknowledgement is contained in the left-most 8 bits of the INFORM
  3516.    field.  Negative acknowledgements associated with routing information
  3517.    messages include the following types:
  3518.  
  3519.    1.  Unrecognized IDPR routing information message type.  Numeric
  3520.        identifier for the unrecognized message type (8 bits).
  3521.  
  3522.    2.  Out-of-date IDPR routing information message.  This is a signal
  3523.        to the sender that it may not have the most recent routing
  3524.        information for the given domain.
  3525.  
  3526.  
  3527.  
  3528.  
  3529.  
  3530. Steenstrup                                                     [Page 63]
  3531.  
  3532. RFC 1479                     IDPR Protocol                     July 1993
  3533.  
  3534.  
  3535. 5.  Route Server Query Protocol
  3536.  
  3537.    Each route server is responsible for maintaining both the routing
  3538.    information database and the route database and for responding to
  3539.    database information requests from policy gateways and other route
  3540.    servers.  These requests and their responses are the messages
  3541.    exchanged via the Route Server Query Protocol (RSQP).
  3542.  
  3543.    Policy gateways and route servers normally invoke RSQP to replace
  3544.    absent, outdated, or corrupted information in their own routing
  3545.    information or route databases.  In section 4, we discussed some of
  3546.    the situations in which RSQP may be invoked; in this section and in
  3547.    section 7, we discuss other such situations.
  3548.  
  3549. 5.1.  Message Exchange
  3550.  
  3551.    Policy gateways and route servers use CMTP for reliable transport of
  3552.    route server requests and responses.  RSQP must communicate to CMTP
  3553.    the maximum number of transmissions per request/response message,
  3554.    rsqp_ret, and the interval between request/response message
  3555.    retransmissions, rsqp_int microseconds.  A route server
  3556.    request/response message is "acceptable" if:
  3557.  
  3558.    - It passes the CMTP validation checks.
  3559.  
  3560.    - Its timestamp is less than rsqp_old (300) seconds behind the
  3561.      recipient's internal clock time.
  3562.  
  3563.    With RSQP, a requesting entity expects to receive an acknowledgement
  3564.    from the queried route server indicating whether the route server can
  3565.    accommodate the request.  The route server may fail to fill a given
  3566.    request for either of the following reasons:
  3567.  
  3568.    - Its corresponding database contains no entry or only a partial
  3569.      entry for the requested information.
  3570.  
  3571.    - It is governed by special message distribution rules, imposed by
  3572.      the domain administrator, that preclude it from releasing the
  3573.      requested information.  Currently, such distribution rules are not
  3574.      included in IDPR configuration information.
  3575.  
  3576.    For all requests that it cannot fill, the route server responds with
  3577.    a negative acknowledgement message carried in a CMTP acknowledgement,
  3578.    indicating the set of unfulfilled requests (see section 5.5.4).
  3579.  
  3580.    If the requesting entity either receives a negative acknowledgement
  3581.    or does not receive any acknowledgement after rsqp_ret attempts
  3582.    directed at the same route server, it queries a different route
  3583.  
  3584.  
  3585.  
  3586. Steenstrup                                                     [Page 64]
  3587.  
  3588. RFC 1479                     IDPR Protocol                     July 1993
  3589.  
  3590.  
  3591.    server, as long as the number of attempted requests to different
  3592.    route servers does not exceed rsqp_try (3).  Specifically, the
  3593.    requesting entity proceeds in round-robin order through its list of
  3594.    addressable route servers.  However, if the requesting entity is
  3595.    unsuccessful after rsqp_try attempts, it abandons the request
  3596.    altogether and logs the event for network management.
  3597.  
  3598.    A policy gateway or a route server can request information from any
  3599.    route server that it can address.  Addresses for local route servers
  3600.    within a domain are part of the configuration for each IDPR entity
  3601.    within a domain; addresses for remote route servers in other domains
  3602.    are obtained through flooded CONFIGURATION messages, as described
  3603.    previously in section 4.2.1.  However, requesting entities always
  3604.    query local route servers before remote route servers, in order to
  3605.    contain the costs associated with the query and response.  If the
  3606.    requesting entity and the queried route server are in the same
  3607.    domain, they can communicate over intra-domain routes, whereas if the
  3608.    requesting entity and the queried route server are in different
  3609.    domains, they must obtain a policy route and establish a path before
  3610.    they can communicate, as we describe below.
  3611.  
  3612. 5.2.  Remote Route Server Communication
  3613.  
  3614.    RSQP communication involving a remote route server requires a policy
  3615.    route and accompanying path setup (see section 7) between the
  3616.    requesting and queried entities, as these entities reside in
  3617.    different domains.  After generating a request message, the
  3618.    requesting entity hands to CMTP its request message along with the
  3619.    remote route server's entity and domain identifiers.  CMTP encloses
  3620.    the request in a DATAGRAM and hands the DATAGRAM and remote route
  3621.    server information to the path agent.  Using the remote route server
  3622.    information, the path agent obtains, and if necessary sets up, a path
  3623.    to the remote route server.  Once the path to the remote route server
  3624.    has been successfully established, the path agent encapsulates the
  3625.    DATAGRAM within an IDPR data message and forwards the data message
  3626.    along the designated path.
  3627.  
  3628.    When the path agent in the remote route server receives the IDPR data
  3629.    message, it extracts the DATAGRAM and hands it to CMTP.  In addition,
  3630.    the path agent, using the requesting entity and domain identifiers
  3631.    contained in the path identifier, obtains, and if necessary sets up,
  3632.    a path back to the requesting entity.
  3633.  
  3634.    If the DATAGRAM fails any of the CMTP validation checks, CMTP returns
  3635.    a NAK to the requesting entity.  If the DATAGRAM passes all of the
  3636.    CMTP validation checks, the remote route server assesses the
  3637.    acceptability of the request message.  Provided the request message
  3638.    is acceptable, the remote route server determines whether it can
  3639.  
  3640.  
  3641.  
  3642. Steenstrup                                                     [Page 65]
  3643.  
  3644. RFC 1479                     IDPR Protocol                     July 1993
  3645.  
  3646.  
  3647.    fulfill the request and directs CMTP to return an ACK to the
  3648.    requesting entity.  The ACK may contain a negative acknowledgement if
  3649.    the entire request cannot be fulfilled.
  3650.  
  3651.    The remote route server generates responses for all requests that it
  3652.    can fulfill and returns the responses to the requesting entity.
  3653.    Specifically, the remote route server hands to CMTP its response and
  3654.    the requesting entity information.  CMTP in turn encloses the
  3655.    response in a DATAGRAM.
  3656.  
  3657.    When returning an ACK, a NAK, or a response to the requesting entity,
  3658.    the remote route server hands the corresponding CMTP message and
  3659.    requesting entity information to the path agent.  Using the
  3660.    requesting entity information, the path agent retrieves the path to
  3661.    the requesting entity, encapsulates the CMTP message within an IDPR
  3662.    data message, and forwards the data message along the designated
  3663.    path.
  3664.  
  3665.    When the path agent in the requesting entity receives the IDPR data
  3666.    message, it extracts the ACK, NAK, or response to its request and
  3667.    performs the CMTP validation checks for that message.  In the case of
  3668.    a response messsage, the requesting entity also assesses message
  3669.    acceptability before incorporating the contents into the appropriate
  3670.    database.
  3671.  
  3672. 5.3  Routing Information
  3673.  
  3674.    Policy gateways and route servers request routing information from
  3675.    route servers, in order to update their routing information
  3676.    databases.  To obtain routing information from a route server, the
  3677.    requesting entity issues a ROUTING INFORMATION REQUEST message
  3678.    containing the type of routing information requested - CONFIGURATION
  3679.    messages, DYNAMIC messages, or both - and the set of domains from
  3680.    which the routing information is requested.
  3681.  
  3682.    Upon receiving a ROUTING INFORMATION REQUEST message, a route server
  3683.    first assesses message acceptability before proceeding to act on the
  3684.    contents.  If the ROUTING INFORMATION REQUEST message is deemed
  3685.    acceptable, the route server determines how much of the request it
  3686.    can fulfill and then instructs CMTP to generate an acknowledgement,
  3687.    indicating its ability to fulfill the request.  The route server
  3688.    proceeds to fulfill as much of the request as possible by
  3689.    reconstructing individual routing information messages, one per
  3690.    requested message type and domain, from its routing information
  3691.    database.  We note that only a regenerated routing information
  3692.    message whose entire contents match that of the original routing
  3693.    information message may pass the CMTP integrity/authentication
  3694.    checks.
  3695.  
  3696.  
  3697.  
  3698. Steenstrup                                                     [Page 66]
  3699.  
  3700. RFC 1479                     IDPR Protocol                     July 1993
  3701.  
  3702.  
  3703. 5.4.  Routes
  3704.  
  3705.    Path agents request routes from route servers when they require
  3706.    policy routes for path setup.  To obtain routes from a route server,
  3707.    the requesting path agent issues a ROUTE REQUEST message containing
  3708.    the destination domain and applicable service requirements, the
  3709.    maximum number of routes requested, a directive indicating whether to
  3710.    generate the routes or retrieve them from the route database, and a
  3711.    directive indicating whether to refresh the routing information
  3712.    database with the most recent CONFIGURATION or DYNAMIC message from a
  3713.    given domain, before generating the routes.  To refresh its routing
  3714.    information database, a route server must obtain routing information
  3715.    from another route server.  The path agent usually issues routing
  3716.    information database refresh directives in response to a failed path
  3717.    setup.  We discuss the application of these directives in more detail
  3718.    in section 7.4.
  3719.  
  3720.    Upon receiving a ROUTE REQUEST message, a route server first assesses
  3721.    message acceptability before proceeding to act on the contents.  If
  3722.    the ROUTE REQUEST message is deemed acceptable, the route server
  3723.    determines whether it can fulfill the request and then instructs CMTP
  3724.    to generate an acknowledgement, indicating its ability to fulfill the
  3725.    request.  The route server proceeds to fulfill the request with
  3726.    policy routes, either retrieved from its route database or generated
  3727.    from its routing information database if necessary, and returns these
  3728.    routes in a ROUTE RESPONSE message.
  3729.  
  3730. 5.5.  Route Server Message Formats
  3731.  
  3732.    The route server query protocol number is equal to 2.  We describe
  3733.    the contents of each type of RSQP message below.
  3734.  
  3735. 5.5.1.  ROUTING INFORMATION REQUEST
  3736.  
  3737.    The ROUTING INFORMATION REQUEST message type is equal to 0.
  3738.  
  3739.     0                   1                   2                   3
  3740.     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
  3741.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3742.    |            QRY AD             |            QRY RS             |
  3743.    +-------------------------------+-------------------------------+
  3744.    |            NUM AD             |              AD               |
  3745.    +---------------+---------------+-------------------------------+
  3746.    |   RIM FLGS    |    UNUSED     |
  3747.    +---------------+---------------+
  3748.  
  3749.    QRY AD
  3750.         (16 bits) Numeric identifier for the domain containing the
  3751.  
  3752.  
  3753.  
  3754. Steenstrup                                                     [Page 67]
  3755.  
  3756. RFC 1479                     IDPR Protocol                     July 1993
  3757.  
  3758.  
  3759.         queried route server.
  3760.  
  3761.    QRY RS (16 bits) Numeric identifier for the queried route server.
  3762.  
  3763.    NUM AD (16 bits) Number of domains about which routing information is
  3764.         requested.  The value 0 indicates a request for routing
  3765.         information from all domains.
  3766.  
  3767.    AD (16 bits) Numeric identifier for a domain.  This field is absent
  3768.         when NUM AD equals 0.
  3769.  
  3770.    RIM FLGS (8 bits) Set of two flags indicating the type of routing
  3771.         information messages requested, contained in the right-most
  3772.         bits.  Proceeding left to right, the first flag indicates
  3773.         whether the request is for a CONFIGURATION message (1
  3774.         CONFIGURATION, 0 no CONFIGURATION).  The second flag indicates
  3775.         whether the request is for a DYNAMIC message (1 DYNAMIC, 0 no
  3776.         DYNAMIC).  At least one of the first and second flags must be
  3777.         set to 1.
  3778.  
  3779.    UNUSED (8 bits) Not currently used; must be set equal to 0.
  3780.  
  3781. 5.5.2.  ROUTE REQUEST
  3782.  
  3783.         The ROUTE REQUEST message type is equal to 1.
  3784.  
  3785.     0                   1                   2                   3
  3786.     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
  3787.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3788.    |            QRY AD             |            QRY RS             |
  3789.    +-------------------------------+-------------------------------+
  3790.    |            SRC AD             |            HST SET            |
  3791.    +---------------+---------------+-------------------------------+
  3792.    |      UCI      |    UNUSED     |            NUM RQS            |
  3793.    +---------------+---------------+-------------------------------+
  3794.    |            DST AD             |            PRX AD             |
  3795.    +---------------+---------------+-------------------------------+
  3796.    |    NUM RTS    |   GEN FLGS    |            RFS AD             |
  3797.    +---------------+---------------+-------------------------------+
  3798.    |            NUM AD             |
  3799.    +-------------------------------+
  3800.    For each domain to be favored, avoided, or excluded:
  3801.    +-------------------------------+---------------+---------------+
  3802.    |              AD               |    AD FLGS    |    UNUSED     |
  3803.    +-------------------------------+---------------+---------------+
  3804.  
  3805.  
  3806.  
  3807.  
  3808.  
  3809.  
  3810. Steenstrup                                                     [Page 68]
  3811.  
  3812. RFC 1479                     IDPR Protocol                     July 1993
  3813.  
  3814.  
  3815.    For each requested service:
  3816.    +-------------------------------+-------------------------------+
  3817.    |            RQS TYP            |            RQS LEN            |
  3818.    +-------------------------------+-------------------------------+
  3819.    |                            RQS SRV                            |
  3820.    +---------------------------------------------------------------+
  3821.  
  3822.    QRY AD
  3823.         (16 bits) Numeric identifier for the domain containing the
  3824.         queried route server.
  3825.  
  3826.    QRY RS (16 bits) Numeric identifier for the queried route server.
  3827.  
  3828.    SRC AD (16 bits) Numeric identifier for the route's source domain.
  3829.  
  3830.    HST SET (16 bits) Numeric identifier for the source's host set.
  3831.  
  3832.    UCI (8 bits) Numeric identifier for the source user class. The value
  3833.         0 indicates that there is no particular source user class.
  3834.  
  3835.    UNUSED (8 bits) Not currently used; must be set equal to 0.
  3836.  
  3837.    NUM RQS (16 bits) Number of requested services.  The value 0
  3838.         indicates that the source requests no special services.
  3839.  
  3840.    DST AD (16 bits) Numeric identifier for the route's destination
  3841.         domain.
  3842.  
  3843.    PRX AD (16 bits) Numeric identifier for the destination domain's
  3844.         proxy (see section 1.3.1).  If the destination domain provides
  3845.         the path agent function for its hosts, then the destination and
  3846.         proxy domains are identical.  A route server constructs routes
  3847.         between the source domain's proxy and the destination domain's
  3848.         proxy.  We note that the source domain's proxy is identical to
  3849.         the domain issuing the CMTP message containing the ROUTE REQUEST
  3850.         message, and hence available in the CMTP header.
  3851.  
  3852.    NUM RTS (8 bits) Number of policy routes requested.
  3853.  
  3854.    GEN FLGS (8 bits) Set of three flags indicating how to obtain the
  3855.         requested routes, contained in the right-most bits.  Proceeding
  3856.         left to right, the first flag indicates whether the route server
  3857.         should retrieve existing routes from its route database or
  3858.         generate new routes (1 retrieve, 0 generate).  The second flag
  3859.         indicates whether the route server should refresh its routing
  3860.         information database before generating the requested routes (1
  3861.         refresh, 0 no refresh) and when set to 1, causes the third flag
  3862.         and the RFS AD field to become significant.  The third flag
  3863.  
  3864.  
  3865.  
  3866. Steenstrup                                                     [Page 69]
  3867.  
  3868. RFC 1479                     IDPR Protocol                     July 1993
  3869.  
  3870.  
  3871.         indicates whether the routing information database refresh
  3872.         should include CONFIGURATION messages or DYNAMIC messages (1
  3873.         configuration, 0 dynamic).
  3874.  
  3875.    RFS AD (16 bits) Numeric identifier for the domain for which routing
  3876.         information should be refreshed.  This field is meaningful only
  3877.         if the second flag in the GEN FLGS field is set to 1.
  3878.  
  3879.    NUM AD (16 bits) Number of transit domains that are to be favored,
  3880.         avoided, or excluded during route selection (see section 1.4.1).
  3881.  
  3882.    AD (16 bits) Numeric identifier for a transit domain to be favored,
  3883.         avoided, or excluded.
  3884.  
  3885.    AD FLGS (8 bits) Three flags indicating how to interpret the AD
  3886.         field, contained in the right-most bits.  Proceeding left to
  3887.         right, the first flag indicates whether the domain should be
  3888.         favored (1 favored, 0 not favored).  The second flag indicates
  3889.         whether the domain should be avoided (1 avoided, 0 not avoided).
  3890.         The third flag indicates whether the domain should be excluded
  3891.         (1 excluded, 0 not excluded).  No more than one of the first,
  3892.         second, and third flags must set to 1.
  3893.  
  3894.    RQS TYP (16 bits) Numeric identifier for a type of requested service.
  3895.         Valid requested services include the following types:
  3896.  
  3897.    1.  Upper bound on delay, in milliseconds (16 bits).  This attribute
  3898.        may be omitted.
  3899.  
  3900.    2.  Minimum delay route.  This attribute may be omitted.
  3901.  
  3902.    3.  Upper bound on delay variation, in milliseconds (16 bits).  This
  3903.        attribute may be omitted.
  3904.  
  3905.    4.  Minimum delay variation route.  This attribute may be omitted.
  3906.  
  3907.    5.  Lower bound on bandwidth, in bits per second (48 bits).  This
  3908.        attribute may be omitted.
  3909.  
  3910.    6.  Maximum bandwidth route.  This attribute may be omitted.
  3911.  
  3912.    7.  Upper bound on monetary cost, in cents (32 bits).  This attribute
  3913.        may be omitted.
  3914.  
  3915.    8.  Minimum monetary cost route.  This attribute may be omitted.
  3916.  
  3917.    9.  Path lifetime in minutes (16 bits). This attribute may be omitted
  3918.        but must be present if types 7 or 8 are present. Route servers
  3919.  
  3920.  
  3921.  
  3922. Steenstrup                                                     [Page 70]
  3923.  
  3924. RFC 1479                     IDPR Protocol                     July 1993
  3925.  
  3926.  
  3927.        use path lifetime information together with domain charging
  3928.        method to compute expected session monetary cost over a given
  3929.        domain.
  3930.  
  3931.    10. Path lifetime in messages (16 bits).  This attribute may be
  3932.        omitted but must be present if types 7 or 8 are present.
  3933.  
  3934.    11. Path lifetime in bytes (48 bits).  This attribute may be omitted
  3935.        but must be present if types 7 or 8 are present.
  3936.  
  3937.    RQS LEN
  3938.         (16 bits) Length of the requested service, in bytes, beginning
  3939.         with the next field.
  3940.  
  3941.    RQS SRV
  3942.         (variable) Description of the requested service.
  3943.  
  3944. 5.5.3.  ROUTE RESPONSE
  3945.  
  3946.    The ROUTE RESPONSE message type is equal to 2.
  3947.  
  3948.     0                   1                   2                   3
  3949.     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
  3950.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3951.    |    NUM RTS    |
  3952.    +---------------+
  3953.    For each route provided:
  3954.    +---------------+---------------+
  3955.    |    NUM AD     |   RTE FLGS    |
  3956.    +---------------+---------------+
  3957.    For each domain in the route:
  3958.    +---------------+---------------+-------------------------------+
  3959.    |    AD LEN     |      VG       |            ADJ AD             |
  3960.    +---------------+---------------+-------------------------------+
  3961.    |            ADJ CMP            |            NUM TP             |
  3962.    +-------------------------------+-------------------------------+
  3963.    |              TP               |
  3964.    +-------------------------------+
  3965.  
  3966.    NUM RTS
  3967.         (16 bits) Number of policy routes provided.
  3968.  
  3969.    RTE FLGS (8 bits) Set of two flags indicating the directions in which
  3970.         a route can be used, contained in the right-most bits.  Refer to
  3971.         sections 6.2, 7, and 7.2 for detailed discussions of path
  3972.         directionality.  Proceeding left to right, the first flag
  3973.         indicates whether the route can be used from source to
  3974.         destination (1 from source, 0 not from source).  The second flag
  3975.  
  3976.  
  3977.  
  3978. Steenstrup                                                     [Page 71]
  3979.  
  3980. RFC 1479                     IDPR Protocol                     July 1993
  3981.  
  3982.  
  3983.         indicates whether the route can be used from destination to
  3984.         source (1 from destination, 0 not from destination).  At least
  3985.         one of the first and second flags must be set to 1, if NUM RTS
  3986.         is greater than 0.
  3987.  
  3988.    NUM AD (8 bits) Number of domains in the policy route, not including
  3989.         the first domain on the route.
  3990.  
  3991.    AD LEN (8 bits) Length of the information associated with a
  3992.         particular domain, in bytes, beginning with the next field.
  3993.  
  3994.  
  3995.    VG (8 bits) Numeric identifier for an exit virtual gateway.
  3996.  
  3997.    ADJ AD (16 bits) Numeric identifier for the adjacent domain connected
  3998.         to the virtual gateway.
  3999.  
  4000.    ADJ CMP (16 bits) Numeric identifier for the adjacent domain
  4001.         component.  Used by policy gateways to select a route across a
  4002.         virtual gateway connecting to a partitioned domain.
  4003.  
  4004.    NUM TP (16 bits) Number of transit policies that apply to the section
  4005.         of the route traversing the domain component.
  4006.  
  4007.    TP (16 bits) Numeric identifier for a transit policy.
  4008.  
  4009. 5.5.4.  Negative Acknowledgements
  4010.  
  4011.    When a policy gateway receives an unacceptable RSQP message that
  4012.    passes the CMTP validation checks, it includes, in its CMTP ACK, an
  4013.    appropriate negative acknowledgement.  This information is placed in
  4014.    the INFORM field of the CMTP ACK (described previously in section
  4015.    2.4); the numeric identifier for each type of RSQP negative
  4016.    acknowledgement is contained in the left-most 8 bits of the INFORM
  4017.    field.  Negative acknowledgements associated with RSQP include the
  4018.    following types:
  4019.  
  4020.    1.  Unrecognized RSQP message type.  Numeric identifier for the
  4021.        unrecognized message type (8 bits).
  4022.  
  4023.    2.  Out-of-date RSQP message.
  4024.  
  4025.    3.  Unable to fill requests for routing information from the
  4026.        following domains.  Number of domains for which requests cannot
  4027.        be filled (16 bits); a value of 0 indicates that the route
  4028.        server cannot fill any of the requests.  Numeric identifier for
  4029.        each domain for which a request cannot be filled (16 bits).
  4030.  
  4031.  
  4032.  
  4033.  
  4034. Steenstrup                                                     [Page 72]
  4035.  
  4036. RFC 1479                     IDPR Protocol                     July 1993
  4037.  
  4038.  
  4039.    4.  Unable to fill requests for routes to the following destination
  4040.        domain.  Numeric identifier for the destination domain (16 bits).
  4041.  
  4042. 6.  Route Generation
  4043.  
  4044.    Route generation is the most computationally complex part of IDPR,
  4045.    because of the number of domains and the number and heterogeneity of
  4046.    policies that it must accommodate.  Route servers must generate
  4047.    policy routes that satisfy the requested services of the source
  4048.    domains and respect the offered services of the transit domains.
  4049.  
  4050.    We distinguish requested qualities of service and route generation
  4051.    with respect to them as follows:
  4052.  
  4053.   - Requested service limits include upper bounds on route delay, route
  4054.     delay variation, and session monetary cost and lower bounds on
  4055.     available route bandwidth.  Generating a route that must satisfy
  4056.     more than one quality of service constraint, for example route delay
  4057.     of no more than X seconds and available route bandwidth of no less
  4058.     than Y bits per second, is an NP-complete problem.
  4059.  
  4060.   - Optimal requested  services  include  minimum  route delay, minimum
  4061.     route delay variation, minimum session monetary cost, and maximum
  4062.     available route bandwidth.  In the worst case, the computational
  4063.     complexity of generating a route that is optimal with respect to a
  4064.     given requested service is O((N + L) log N) for Dijkstra's shortest
  4065.     path first (SPF) search and O(N + (L * L)) for breadth-first (BF)
  4066.     search, where N is the number of nodes and L is the number of links
  4067.     in the search graph.  Multi-criteria optimization, for example
  4068.     finding a route with minimal delay variation and minimal session
  4069.     monetary cost, may be defined in several ways.  One approach to
  4070.     multi-criteria optimization is to assign each link a single value
  4071.     equal to a weighted sum of the values of the individual offered
  4072.     qualities of service and generate a route that is optimal with
  4073.     respect to this new criterion.  However, selecting the weights that
  4074.     yield the desired route generation behavior is itself an
  4075.     optimization procedure and hence not trivial.
  4076.  
  4077. To help contain the combinatorial explosion of processing and memory
  4078. costs associated with route generation, we supply the following
  4079. guidelines for generation of suitable policy routes:
  4080.  
  4081.   - Each route server should only generate policy routes from the
  4082.     perspective of its own domain as source; it need not generate policy
  4083.     routes for arbitrary source/destination domain pairs.  Thus, we can
  4084.     distribute the computational burden over all route servers.
  4085.  
  4086.   - Route servers should precompute routes for which they anticipate
  4087.  
  4088.  
  4089.  
  4090. Steenstrup                                                     [Page 73]
  4091.  
  4092. RFC 1479                     IDPR Protocol                     July 1993
  4093.  
  4094.  
  4095.     requests and should generate routes on demand only in order to
  4096.     satisfy unanticipated route requests.  Hence, a single route server
  4097.     can distribute its computational burden over time.
  4098.  
  4099.   - Route servers should cache the results of route generation, in order
  4100.     to minimize the computation associated with responding to future
  4101.     route requests.
  4102.  
  4103.   - To handle requested service limits, a route server should always
  4104.     select the first route generated that satisfies all of the requested
  4105.     service limits.
  4106.  
  4107.   - To handle multi-criteria optimization in route selection, a route
  4108.     server should generate routes that are optimal with respect to the
  4109.     first optimal requested service listed in the ROUTE REQUEST message.
  4110.     The route server should resolve ties between otherwise equivalent
  4111.     routes by evaluating these routes according to the other optimal
  4112.     requested services contained in the ROUTE REQUEST message, in the
  4113.     order in which they are listed.  With respect to the route server's
  4114.     routing information database, the selected route is optimal
  4115.     according to the first optimal requested service listed in the ROUTE
  4116.     REQUEST message but is not necessarily optimal according to any
  4117.     other optimal requested service listed in the ROUTE REQUEST message.
  4118.  
  4119.     ti 2 - To handle a mixture of requested service limits and optimal
  4120.     requested services, a route server should generate routes that
  4121.     satisfy all of the requested service limits.  The route server
  4122.     should resolve ties between otherwise equivalent routes by
  4123.     evaluating these routes as described in the multi-criteria
  4124.     optimization case above.
  4125.  
  4126.     ti 2 - All else being equal, a route server should always prefer
  4127.     minimum-hop routes, because they minimize the amount of network
  4128.     resources consumed by the routes.
  4129.  
  4130.     ti 2 - A route server should generate at least one route to each
  4131.     component of a partitioned destination domain, because it may not
  4132.     know in which domain component the destination host resides.  Hence,
  4133.     a route server can maximize the chances of providing a feasible
  4134.     route to a destination within a partitioned domain.
  4135.  
  4136. 6.1  Searching
  4137.  
  4138.     All domains need not execute the identical route generation
  4139.     procedure.  Each domain administrator is free to specify the IDPR
  4140.     route generation procedure for route servers in its own domain,
  4141.     making the procedure as simple or as complex as desired.
  4142.  
  4143.  
  4144.  
  4145.  
  4146. Steenstrup                                                     [Page 74]
  4147.  
  4148. RFC 1479                     IDPR Protocol                     July 1993
  4149.  
  4150.  
  4151.     We offer an IDPR route generation procedure as a model.  With slight
  4152.     modification, this procedure can be made to search in either BF or
  4153.     SPF order.  The procedure can be used either to generate a single
  4154.     policy route from the source to a specified destination domain or to
  4155.     generate a set of policy routes from the source domain to all
  4156.     destination domains.  If the source or destination domain has a
  4157.     proxy, then the source or destination endpoint of the policy route
  4158.     is a proxy domain and not the actual source or destination domain.
  4159.  
  4160.     For high-bandwidth traffic flows, BF search is the recommended
  4161.     search technique, because it produces minimum-hop routes.  For low-
  4162.     bandwidth traffic flows, the route server may use either BF search
  4163.     or SPF search.  The computational complexity of BF search is O(N +
  4164.     L) and hence it is the search procedure of choice, except when
  4165.     generating routes with optimal requested services.  We recommend
  4166.     using SPF search only for optimal requested services and never in
  4167.     response to a request for a maximum bandwidth route.
  4168.  
  4169. 6.1.1.  Implementation
  4170.  
  4171.    Data Structures:
  4172.  
  4173.    The routing information database contains the graph of an
  4174.    internetwork, in which virtual gateways are the nodes and intra-
  4175.    domain routes between virtual gateways are the links.  During route
  4176.    generation, each route is represented as a sequence of virtual
  4177.    gateways, domains, and relevant transit policies, together with a
  4178.    list of route characteristics, stored in a temporary array and
  4179.    indexed by destination domain.
  4180.  
  4181.    - Execute the Policy Consistency routine, first with the source
  4182.      domain the given domain and second with the destination domain as
  4183.      the given domain.  If any policy inconsistency precludes the
  4184.      requested traffic flow, go to Exit.
  4185.  
  4186.    - For each domain, initialize a null route, set the route bandwidth
  4187.      to and set the following route characteristics to infinity: route
  4188.      delay, route delay variation, session monetary cost, and route
  4189.      length in hops.
  4190.  
  4191.    - With each operational virtual gateway in the source or source proxy
  4192.      domain, associate the initial route characteristics.
  4193.  
  4194.    - Initialize a next-node data structure which will contain, for each
  4195.      route in progress, the virtual gateway at the current endpoint of
  4196.      the route together with the associated route characteristics.  The
  4197.      next-node data structure determines the order in which routes get
  4198.      expanded.
  4199.  
  4200.  
  4201.  
  4202. Steenstrup                                                     [Page 75]
  4203.  
  4204. RFC 1479                     IDPR Protocol                     July 1993
  4205.  
  4206.  
  4207.         BF:  A fifo queue.
  4208.  
  4209.         SPF: A heap, ordered according to the first optimal requested
  4210.              service listed in the ROUTE REQUEST message.
  4211.  
  4212.    Remove Next Node: These steps are performed for each virtual gateway
  4213.         in the next-node data structure.
  4214.  
  4215.       - If there are no more virtual gateways in the next-node data
  4216.         structure, go to Exit.
  4217.  
  4218.       - Extract a virtual gateway and its associated route
  4219.         characteristics from the next-node data structure, obtain the
  4220.         adjacent domain, and:
  4221.  
  4222.              SPF: Remake the heap.
  4223.  
  4224.       - If there is a specific destination domain and if for the primary
  4225.         optimal service:
  4226.  
  4227.              BF:  Route length in hops.
  4228.  
  4229.              SPF: First optimal requested service listed in the ROUTE
  4230.              REQUEST message.
  4231.  
  4232.         the extracted virtual gateway's associated route characteristic
  4233.         is no better than that of the destination domain, go to Remove
  4234.         Next Node.
  4235.  
  4236.       - Execute the Policy Consistency routine with the adjacent domain
  4237.         as given domain.  If any policy inconsistency precludes the
  4238.         requested traffic flow, go to Remove Next Node.
  4239.  
  4240.       - Check that the source domain's transit policies do not preclude
  4241.         traffic generated by members of the source host set with the
  4242.         specified user class and requested services, from flowing to the
  4243.         adjacent domain as destination.  This check is necessary because
  4244.         the route server caches what it considers to be all feasible
  4245.         routes, to intermediate destination domains, generated during
  4246.         the computation of the requested route.  If there are no policy
  4247.         inconsistencies, associate the route and its characteristics
  4248.         with the adjacent domain as destination.
  4249.  
  4250.       - If there is a specific destination domain and if the adjacent
  4251.         domain is the destination or destination proxy domain, go to
  4252.         Remove Next Node.
  4253.  
  4254.       - Record the set of all exit virtual gateways in the adjacent
  4255.  
  4256.  
  4257.  
  4258. Steenstrup                                                     [Page 76]
  4259.  
  4260. RFC 1479                     IDPR Protocol                     July 1993
  4261.  
  4262.  
  4263.         domain which the adjacent domain's transit policies permit the
  4264.         requested traffic flow and which are currently reachable from
  4265.         the entry virtual gateway.
  4266.  
  4267.    Next Node:
  4268.  
  4269.         These steps are performed for all exit virtual gateways in the
  4270.         above set.
  4271.  
  4272.       - If there are no exit virtual gateways in the set, go to Remove
  4273.         Next Node.
  4274.  
  4275.       - Compute the characteristics for the route to the exit virtual
  4276.         gateway, and check that all of the route characteristics are
  4277.         within the requested service limits.  If any of the route
  4278.         characteristics are outside of these limits, go to Next Node.
  4279.  
  4280.       - Compare these route characteristics with those already
  4281.         associated with the exit virtual gateway (there may be none, if
  4282.         this is the first time the exit virtual gateway has been visited
  4283.         in the search), according to the primary optimal service.
  4284.  
  4285.       - Select the route with the optimal value of the primary optimal
  4286.         service, resolve ties by considering optimality according to any
  4287.         other optimal requested services in the order in which they are
  4288.         listed in the ROUTE REQUEST message, and associate the selected
  4289.         route and its characteristics with the exit virtual gateway.
  4290.  
  4291.       - Add the virtual gateway to the next-node structure:
  4292.  
  4293.              BF:  Add to the end of the fifo queue.
  4294.  
  4295.              SPF: Add to the heap.
  4296.  
  4297.              and go to Next Node.
  4298.  
  4299.    Exit:
  4300.         Return a response to the route request, consisting of either a
  4301.         set of candidate policy routes or an indication that the route
  4302.         request cannot be fulfilled.
  4303.  
  4304.    Policy Consistency: Check policy consistency for the given domain.
  4305.  
  4306.       - Check that the given domain is not specified as an excluded
  4307.         domain in the route request.
  4308.  
  4309.       - Check that the given domain's transit policies do not preclude
  4310.         traffic generated by members of the source host set with the
  4311.  
  4312.  
  4313.  
  4314. Steenstrup                                                     [Page 77]
  4315.  
  4316. RFC 1479                     IDPR Protocol                     July 1993
  4317.  
  4318.  
  4319.         specified user class and requested services, from flowing to the
  4320.         destination domain.
  4321.  
  4322.    During the computation of the requested routes, a route server also
  4323.    caches what it considers to be all feasible routes to intermediate
  4324.    destination domains, thus increasing the chances of being able to
  4325.    respond to a future route request without having to generate a new
  4326.    route.  The route server does perform some policy consistency checks
  4327.    on the routes, as they are generated, to intermediate destinations.
  4328.    However, these routes may not in fact be feasible; the transit
  4329.    domains contained on the routes may not permit traffic between the
  4330.    source and the given intermediate destinations.  Hence, before
  4331.    dispensing such a route in response to a route request, a route
  4332.    server must check that the transit policies of the constituent
  4333.    domains are consistent with the source and destination of the traffic
  4334.    flow.
  4335.  
  4336. 6.2.  Route Directionality
  4337.  
  4338.    A path agent may wish to set up a bidirectional path using a route
  4339.    supplied by a route server.  (Refer to sections 7.2 and 7.4 for
  4340.    detailed discussions of path directionality.)  However, a route
  4341.    server can only guarantee that the routes it supplies are feasible if
  4342.    used in the direction from source to destination.  The reason is that
  4343.    the route server, which resides in the source or source proxy domain,
  4344.    does not have access to, and thus cannot account for, the source
  4345.    policies of the destination domain.  Nevertheless, the route server
  4346.    can provide the path agent with an indication of its assessment of
  4347.    route feasibility in the direction from destination to source.
  4348.  
  4349.    A necessary but insufficient condition for a route to be feasible in
  4350.    the direction from destination to source is as follows.  The route
  4351.    must be consistent, in the direction from destination to source, with
  4352.    the transit policies of the domains that compose the route.  The
  4353.    transit policy consistency checks performed by the route server
  4354.    during route generation account for the direction from source to
  4355.    destination but not for the direction from destination to source.
  4356.    Only after a route server generates a feasible route from source to
  4357.    destination does it perform the transit policy consistency checks for
  4358.    the route in the direction from destination to source.  Following
  4359.    these checks, the route server includes in its ROUTE RESPONSE message
  4360.    to the path agent an indication of its assessment of route
  4361.    feasibility in each direction.
  4362.  
  4363.  
  4364.  
  4365.  
  4366.  
  4367.  
  4368.  
  4369.  
  4370. Steenstrup                                                     [Page 78]
  4371.  
  4372. RFC 1479                     IDPR Protocol                     July 1993
  4373.  
  4374.  
  4375. 6.3.  Route Database
  4376.  
  4377.    A policy route, as originally specified by a route server, is an
  4378.    ordered list of virtual gateways, domains, and transit policies: VG 1
  4379.    - AD 1 - TP 1 - ... - VG n - AD n - TP n. where VG i is the virtual
  4380.    gateway that serves as exit from AD i-1 and entry to AD i, and TP i
  4381.    is the set of transit policies associated with AD i and relevant to
  4382.    the particular route.  Each route is indexed by source and
  4383.    destination domain.  Route servers and paths agents store policy
  4384.    routes in route databases maintained as caches whose entries must be
  4385.    periodically flushed to avoid retention of stale policy routes.  A
  4386.    route server's route database is the set of all routes it has
  4387.    generated on behalf of its domain as source or source proxy;
  4388.    associated with each route in the database are its route
  4389.    characteristics.  A path agent's route database is the set of all
  4390.    routes it has requested and received from route servers on behalf of
  4391.    hosts for which it is configured to act.
  4392.  
  4393.    When attempting to locate a feasible route for a traffic flow, a path
  4394.    agent first consults its own route database before querying a route
  4395.    server.  If the path agent's route database contains one or more
  4396.    routes between the given source and destination domains and
  4397.    accommodating the given host set and UCI, then the path agent checks
  4398.    each such route against the set of excluded domains listed in the
  4399.    source policy.  The path agent either selects the first route
  4400.    encountered that does not include the excluded domains, or, if no
  4401.    such route exists in its route database, requests a route from a
  4402.    route server.
  4403.  
  4404.    A path agent must query a route server for routes when it is unable
  4405.    to fulfill a route request from its own route database.  Moreover, we
  4406.    recommend that a path agent automatically forward to a route server,
  4407.    all route requests with non-null requested services.  The reason is
  4408.    that the path agent retains no route characteristics in its route
  4409.    database.  Hence, the path agent cannot determine whether an entry in
  4410.    its route database satisfies the requested services.
  4411.  
  4412.    When responding to a path agent's request for a policy route, a route
  4413.    server first consults its route database, unless the ROUTE REQUEST
  4414.    message contains an explicit directive to generate a new route.  If
  4415.    its route database contains one or more routes between the given
  4416.    source and destination domains and accommodating the given host set
  4417.    and UCI, the route server checks each such route against the set of
  4418.    excluded domains listed in the ROUTE REQUEST message.  The route
  4419.    server either selects all routes encountered that do not include the
  4420.    excluded domains, or, if no such route exists in its route database,
  4421.    attempts to generate such a route.  Once the route server selects a
  4422.    set of routes, it then checks each such route against the services
  4423.  
  4424.  
  4425.  
  4426. Steenstrup                                                     [Page 79]
  4427.  
  4428. RFC 1479                     IDPR Protocol                     July 1993
  4429.  
  4430.  
  4431.    requested by the path agent and the services offered by the domains
  4432.    composing the route.  To obtain the offered services information, the
  4433.    route server consults its routing information database.  The route
  4434.    server either selects the first route encountered that is consistent
  4435.    with both the requested and offered services, or, if no such route
  4436.    exists in its route database, attempts to generate such a route.
  4437.  
  4438. 6.3.1.  Cache Maintenance
  4439.  
  4440.    Each route stored in a route database has a maximum cache lifetime
  4441.    equal to rdb_rs minutes for a route server and rdb_ps minutes for a
  4442.    path agent.  Route servers and path agents reclaim cache space by
  4443.    flushing entries that have attained their maximum lifetimes.
  4444.    Moreover, paths agents reclaim cache space for routes whose paths
  4445.    have failed to be set up successfully or have been torn down (see
  4446.    section 7.4).
  4447.  
  4448.    Nevertheless, cache space may become scarce, even with reclamation of
  4449.    entries.  If a cache fills, the route server or path agent logs the
  4450.    event for network management.  To obtain space in the cache when the
  4451.    cache is full, the route server or path agent deletes from the cache
  4452.    the oldest entry.
  4453.  
  4454. 7.  Path Control Protocol and Data Message Forwarding Procedure
  4455.  
  4456.    Two entities in different domains may exchange IDPR data messages,
  4457.    only if there exists an IDPR path set up between the two domains.
  4458.    Path setup requires cooperation among path agents and intermediate
  4459.    policy gateways.  Path agents locate policy routes, initiate the Path
  4460.    Control Protocol (PCP), and manage existing paths between
  4461.    administrative domains.  Intermediate policy gateways verify that a
  4462.    given policy route is consistent with their domains' transit
  4463.    policies, establish the forwarding information, and forward messages
  4464.    along existing paths.
  4465.  
  4466.    Each policy gateway and each route server contains a path agent.  The
  4467.    path agent that initiates path setup in the source or source proxy
  4468.    domain is the "originator", and the path agent that handles the
  4469.    originator's path setup message in the destination or destination
  4470.    proxy domain is the "target".  Every path has two possible directions
  4471.    of traffic flow: from originator to target and from target to
  4472.    originator.  Path control messages are free to travel in either
  4473.    direction, but data messages may be restricted to only one direction.
  4474.  
  4475.    Once a path for a policy route is set up, its physical realization is
  4476.    a set of consecutive policy gateways, with policy gateways or route
  4477.    servers forming the endpoints.  Two successive entities in this set
  4478.    belong to either the same domain or the same virtual gateway.  A
  4479.  
  4480.  
  4481.  
  4482. Steenstrup                                                     [Page 80]
  4483.  
  4484. RFC 1479                     IDPR Protocol                     July 1993
  4485.  
  4486.  
  4487.    policy gateway or route server may, at any time, recover the
  4488.    resources dedicated to a path that goes through it by tearing down
  4489.    that path.  For example, a policy gateway may decide to tear down a
  4490.    path that has not been used for some period of time.
  4491.  
  4492.    PCP may build multiple paths between source and destination domains,
  4493.    but it is not responsible for managing such paths as a group or for
  4494.    eliminating redundant paths.
  4495.  
  4496. 7.1.  An Example of Path Setup
  4497.  
  4498.    We illustrate how path setup works by stepping through an example.
  4499.    Suppose host Hx in domain AD X wants to communicate with host Hy in
  4500.    domain AD Y and that both AD X and AD Y support IDPR.  Hx need not
  4501.    know the identity of its own domain or of Hy's domain in order to
  4502.    send messages to Hy.  Instead, Hx simply forwards a message bound for
  4503.    Hy to one of the gateways on its local network, according to its
  4504.    local forwarding information only.  If the recipient gateway is a
  4505.    policy gateway, the resident path agent determines how to forward the
  4506.    message outside of the domain.  Otherwise, the recipient gateway
  4507.    forwards the message to another gateway in AD X, according to its
  4508.    local forwading information.  Eventually, the message will arrive at
  4509.    a policy gateway in AD X, as policy gateways are the only egress
  4510.    points to other domains, in domains that support IDPR.
  4511.  
  4512.    The path agent resident in the recipient policy gateway uses the
  4513.    message header, including source and destination addresses and any
  4514.    requested service information (for example, type of service), in
  4515.    order to determine whether it is an intra-domain or inter-domain
  4516.    message, and if inter-domain, whether it requires an IDPR policy
  4517.    route.  Specifically, the path agent attempts to locate a forwarding
  4518.    information database entry for the given traffic flow, from the
  4519.    information contained in the message header.  In the future, for IP
  4520.    messages, the relevant header information may also include special
  4521.    service-specific IP options or even information from higher layer
  4522.    protocols.
  4523.  
  4524.    Forwarding database entries exist for all of the following:
  4525.  
  4526.    - All intra-domain traffic flows.  Intra-domain forwarding
  4527.      information is integrated into the forwarding information database
  4528.      as soon as it is received.
  4529.  
  4530.    - Inter-domain traffic flows that do not require IDPR policy routes.
  4531.      Non-IDPR forwarding information is integrated into the forwarding
  4532.      database as soon as it is received.
  4533.  
  4534.    - IDPR inter-domain traffic flows for which a path has already been
  4535.  
  4536.  
  4537.  
  4538. Steenstrup                                                     [Page 81]
  4539.  
  4540. RFC 1479                     IDPR Protocol                     July 1993
  4541.  
  4542.  
  4543.      set up.  IDPR forwarding information is integrated into the
  4544.      forwarding database only during path setup.
  4545.  
  4546.    The path agent uses the message header contents to guide the search
  4547.    for a forwarding information database entry for a given traffic flow.
  4548.    We recommend a radix search to locate such an entry.  When the search
  4549.    terminates, it produces either an entry, or, in the case of a new
  4550.    IDPR traffic flow, a directive to generate an entry.  If the search
  4551.    terminates in an existing forwarding information database entry, the
  4552.    path agent forwards the message according to that entry.
  4553.  
  4554.    Suppose that the search terminates indicating that the traffic flow
  4555.    from Hx to Hy requires an IDPR policy route and that no entry in the
  4556.    forwarding information database yet exists for that traffic flow.  In
  4557.    this case, the path agent first determines the source and destination
  4558.    domains associated with the message's source and destination
  4559.    addresses, before attempting to obtain a policy route.  The path
  4560.    agent relies on the mapping servers to supply the domain information,
  4561.    but it caches all mapping server responses locally to limit the
  4562.    number of future queries.  When attempting to resolve an address to a
  4563.    domain, the path agent always checks its local cache before
  4564.    contacting a mapping server.
  4565.  
  4566.    After obtaining the domain information, the path agent attempts to
  4567.    obtain a policy route to carry the traffic from Hx to Hy.  The path
  4568.    agent relies on route servers to supply policy routes, but it caches
  4569.    all route server responses locally to limit the number of future
  4570.    queries.  When attempting to locate a suitable policy route, the path
  4571.    agent usually consults its local cache before contacting a route
  4572.    server, as described previously in section 6.3.
  4573.  
  4574.    If no suitable cache entry exists, the path agent queries the route
  4575.    server, providing it with the source and destination domains together
  4576.    with source policy information carried in the host message or
  4577.    specified through configuration.  Upon receiving a policy route
  4578.    query, a route server consults its route database.  If it cannot
  4579.    locate a suitable route in its route database, the route server
  4580.    attempts to generate at least one route to AD Y, consistent with the
  4581.    requested services for Hx.
  4582.  
  4583.    The route server always returns a response to the path agent,
  4584.    regardless of whether it is successful in locating a suitable policy
  4585.    route.  The response to a successful route query consists of a set of
  4586.    candidate routes, from which the path agent makes its selection.  We
  4587.    expect that a path agent will normally choose a single route from a
  4588.    candidate set.  Nevertheless, IDPR does not preclude a path agent
  4589.    from selecting multiple routes from the candidate set.  A path agent
  4590.    may desire multiple routes to support features such as fault
  4591.  
  4592.  
  4593.  
  4594. Steenstrup                                                     [Page 82]
  4595.  
  4596. RFC 1479                     IDPR Protocol                     July 1993
  4597.  
  4598.  
  4599.    tolerance or load balancing; however, IDPR does not currently specify
  4600.    how the path agent should use multiple routes.
  4601.  
  4602.    If the policy route is a new route provided by the route server,
  4603.    there will be no existing path for the route, and thus the path agent
  4604.    must set up such a path.  However, if the policy route is an existing
  4605.    route extracted from the path agent's cache, there may well be an
  4606.    existing path for the route, set up to accommodate a host traffic
  4607.    flow.  IDPR permits multiple traffic flows to use the same path,
  4608.    provided that all traffic flows sharing the path travel between the
  4609.    same endpoint domains and have the same service requirements.
  4610.    Nevertheless, IDPR does not preclude a path agent from setting up
  4611.    distinct paths along the same policy route to preserve the
  4612.    distinction between host traffic flows.
  4613.  
  4614.    The path agent associates an identifier with the path, which is
  4615.    included in each message that travels down the path and is used by
  4616.    the policy gateways along the path in order to determine how to
  4617.    forward the message.  If the path already exists, the path agent uses
  4618.    the preexisting identifier.  However, for new paths, the path agent
  4619.    chooses a path identifier that is different from those of all other
  4620.    paths that it manages.  The path agent also updates its forwarding
  4621.    information database to reference the path identifier and modifies
  4622.    its search procedure to yield the correct entry in the forwarding
  4623.    information database given the data message header.
  4624.  
  4625.    For new paths, the path agent initiates path setup, communicating the
  4626.    policy route, in terms of requested services, constituent domains,
  4627.    relevant transit policies, and the connecting virtual gateways, to
  4628.    policy gateways in intermediate domains.  Using this information, an
  4629.    intermediate policy gateway determines whether to accept or refuse
  4630.    the path and to which next policy gateway to forward the path setup
  4631.    information.  The path setup procedure allows policy gateways to set
  4632.    up a path in both directions simultaneously.  Each intermediate
  4633.    policy gateway, after path acceptance, updates its forwarding
  4634.    information database to include an entry that associates the path
  4635.    identifier with the appropriate previous and next hop policy
  4636.    gateways.
  4637.  
  4638.    When a policy gateway in AD Y accepts a path, it notifies the source
  4639.    path agent in AD X.  We expect that the source path agent will
  4640.    normally wait until a path has been successfully established before
  4641.    using it to transport data traffic.  However, PCP does not preclude a
  4642.    path agent from forwarding messages along a path prior to
  4643.    confirmation of successful path establishment.  Paths remain in place
  4644.    until they are torn down because of failure, expiration, or when
  4645.    resources are scarce, preemption in favor of other paths.
  4646.  
  4647.  
  4648.  
  4649.  
  4650. Steenstrup                                                     [Page 83]
  4651.  
  4652. RFC 1479                     IDPR Protocol                     July 1993
  4653.  
  4654.  
  4655.    We note that data communication between Hx and Hy may occur over two
  4656.    separate IDPR paths: one from AD X to AD Y and one from AD Y to AD X.
  4657.    The reasons are that within a domain, hosts know nothing about path
  4658.    agents nor IDPR paths, and path agents know nothing about other path
  4659.    agents' existing IDPR paths.  Thus, in AD Y, the path agent that
  4660.    terminates the path from AD X may not be the same as the path agent
  4661.    that receives traffic from Hy destined for Hx.  In this case, receipt
  4662.    of traffic from Hy forces the second path agent to set up an
  4663.    independent path from AD Y to AD X.
  4664.  
  4665. 7.2.  Path Identifiers
  4666.  
  4667.    Each path has an associated path identifier, unique throughout an
  4668.    internetwork.  Every IDPR data message travelling along that path
  4669.    includes the path identifier, used for message forwarding.  The path
  4670.    identifier is the concatenation of three items: the identifier of the
  4671.    originator's domain, the identifier of the originator's policy
  4672.    gateway or route server, and a 32-bit local path identifier specified
  4673.    by the originator.  The path identifier and the CMTP transaction
  4674.    identifier have analogous syntax and play analogous roles in their
  4675.    respective protocols.
  4676.  
  4677.    When issuing a new path identifier, the originator always assigns a
  4678.    local path identifier that is different from that of any other active
  4679.    or recently torn-down path originally set up by that path agent.
  4680.    This helps to distinguish new paths from replays.  Hence, the
  4681.    originator must keep a record of each extinct path for long enough
  4682.    that all policy gateways on the path will have eliminated any
  4683.    reference to it from their memories.  The right-most 30 bits of the
  4684.    local identifier are the same for each path direction, as they are
  4685.    assigned by the originator.  The left-most 2 bits of the local
  4686.    identifier indicate the path direction.
  4687.  
  4688.    At path setup time, the originator specifies which of the path
  4689.    directions to enable contingent upon the information received from
  4690.    the route server in the ROUTE RESPONSE message.  By "enable", we mean
  4691.    that each path agent and each intermediate policy gateway establishes
  4692.    an association between the path identifier and the previous and next
  4693.    policy gateways on the path, which it uses for forwarding data
  4694.    messages along that path.  IDPR data messages may travel in the
  4695.    enabled path directions only, but path control messages are always
  4696.    free to travel in either path direction.  The originator may enable
  4697.    neither path direction, if the entire data transaction can be carried
  4698.    in the path setup message itself.  In this case, the path agents and
  4699.    the intermediate policy gateways do not establish forwarding
  4700.    associations for the path, but they do verify consistency of the
  4701.    policy information contained in the path setup message, with their
  4702.    own transit policies, before forwarding the setup message on to the
  4703.  
  4704.  
  4705.  
  4706. Steenstrup                                                     [Page 84]
  4707.  
  4708. RFC 1479                     IDPR Protocol                     July 1993
  4709.  
  4710.  
  4711.    next policy gateway.
  4712.  
  4713.    The path direction portion of the local path identifier has different
  4714.    interpretations, depending upon message type.  In an IDPR path setup
  4715.    message, the path direction indicates the directions in which the
  4716.    path should be enabled: the value 01 denotes originator to target,
  4717.    the value 10 denotes target to originator, the value 11 denotes both
  4718.    directions, and the value 00 denotes neither direction.  Each policy
  4719.    gateway along the path interprets the path direction in the setup
  4720.    message and sets up the forwarding information as directed.  In an
  4721.    IDPR data message, the path direction indicates the current direction
  4722.    of traffic flow: either 01 for originator to target or 10 for target
  4723.    to originator.  Thus, if for example, an originator sets up a path
  4724.    enabling only the direction from target to originator, the target
  4725.    sends data messages containing the path identifier selected by the
  4726.    originator together with the path direction set equal to 10.
  4727.  
  4728.    Instead of using path identifiers that are unique throughout an
  4729.    internetwork, we could have used path identifiers that are unique
  4730.    only between a pair of consecutive policy gateways and that change
  4731.    from one policy gateway pair to the next.  The advantage of locally
  4732.    unique path identifiers is that they may be much shorter than
  4733.    globally unique identifiers and hence consume less transmission
  4734.    bandwidth.  However, the disadvantage is that the path identifier
  4735.    carried in each IDPR data message must be modified at each policy
  4736.    gateway, and hence if the integrity/authentication information covers
  4737.    the path identifier, it must be recomputed at each policy gateway.
  4738.    For security reasons, we have chosen to include the path identifier
  4739.    in the set of information covered by the integrity/authentication
  4740.    value, and moreover, we advocate public-key based signatures for
  4741.    authentication.  Thus, it is not possible for intermediate policy
  4742.    gateways to modify the path identifier and then recompute the correct
  4743.    integrity/authentication value.  Therefore, we have decided in favor
  4744.    of path identifiers that do not change from hop to hop and hence must
  4745.    be globally unique.  To speed forwarding of IDPR data messages with
  4746.    long path identifiers, policy gateways should hash the path
  4747.    identifiers in order to index IDPR forwarding information.
  4748.  
  4749. 7.3.  Path Control Messages
  4750.  
  4751.    Messages exchanged by the path control protocol are classified into
  4752.    "requests": SETUP, TEARDOWN, REPAIR; and "responses": ACCEPT, REFUSE,
  4753.    ERROR.  These messages have significance for intermediate policy
  4754.    gateways as well as for path agents.
  4755.  
  4756.    SETUP:
  4757.         Establishes a path by linking together pairs of policy gateways.
  4758.         The SETUP message is generated by the originator and propagates
  4759.  
  4760.  
  4761.  
  4762. Steenstrup                                                     [Page 85]
  4763.  
  4764. RFC 1479                     IDPR Protocol                     July 1993
  4765.  
  4766.  
  4767.         to the target.  In response to a SETUP message, the originator
  4768.         expects to receive an ACCEPT, REFUSE, or ERROR message.  The
  4769.         SETUP message carries all information necessary to set up the
  4770.         path including path identifier, requested services, transit
  4771.         policy information relating to each domain traversed, and
  4772.         optionally, expedited data.
  4773.  
  4774.    ACCEPT: Signals successful path establishment.  The ACCEPT message is
  4775.         generated by the target, in response to a SETUP message, and
  4776.         propagates back to the originator.  Reception of an ACCEPT
  4777.         message by the originator indicates that the originator can now
  4778.         safely proceed to send data along the path.  The ACCEPT message
  4779.         contains the path identifier and an optional reason for
  4780.         conditional acceptance.
  4781.  
  4782.    REFUSE: Signals that the path could not be successfully established,
  4783.         either because resources were not available or because there was
  4784.         an inconsistency between the services requested by the source
  4785.         and the services offered by a transit domain along the path.
  4786.         The REFUSE message is generated by the target or by any
  4787.         intermediate policy gateway, in response to a SETUP message, and
  4788.         propagates back to the originator.  All recipients of a REFUSE
  4789.         message recover the resources dedicated to the given path.  The
  4790.         REFUSE message contains the path identifier and the reason for
  4791.         path refusal.
  4792.  
  4793.    TEARDOWN: Tears down a path, typically when a non-recoverable failure
  4794.         is detected.  The TEARDOWN message may be generated by any path
  4795.         agent or policy gateway in the path and usually propagates in
  4796.         both path directions.  All recipients of a TEARDOWN message
  4797.         recover the resources dedicated to the given path.  The TEARDOWN
  4798.         message contains the path identifier and the reason for path
  4799.         teardown.
  4800.  
  4801.    REPAIR: Establishes a repaired path by linking together pairs of
  4802.         policy gateways.  The REPAIR message is generated by a policy
  4803.         gateway after detecting that the next policy gateway on one of
  4804.         its existing paths is unreachable.  A policy gateway that
  4805.         generates a REPAIR message propagates the message forward at
  4806.         most one virtual gateway.  In response to a REPAIR message, the
  4807.         policy gateway expects to receive an ACCEPT, REFUSE, TEARDOWN,
  4808.         or ERROR message.  The REPAIR message carries the original SETUP
  4809.         message.
  4810.  
  4811.    ERROR: Transports information about a path error back to the
  4812.         originator, when a PCP message contains unrecognized
  4813.         information.  The ERROR message may be generated by the target
  4814.         or by any intermediate policy gateway and propagates back to the
  4815.  
  4816.  
  4817.  
  4818. Steenstrup                                                     [Page 86]
  4819.  
  4820. RFC 1479                     IDPR Protocol                     July 1993
  4821.  
  4822.  
  4823.         originator.  Most, but not all, ERROR messages are generated in
  4824.         response to errors encountered during path setup.  The ERROR
  4825.         message includes the path identifier and an explanation of the
  4826.         error detected.
  4827.  
  4828.    Policy gateways use CMTP for reliable transport of PCP messages,
  4829.    between path agents and policy gateways and between consecutive
  4830.    policy gateways on a path.  PCP must communicate to CMTP the maximum
  4831.    number of transmissions per path control message, pcp_ret, and the
  4832.    interval between path contol message retransmissions, pcp_int
  4833.    microseconds.  All path control messages, except ERROR messages, may
  4834.    be transmitted up to pcp_ret times; ERROR messages are never
  4835.    retransmitted.  A path control message is "acceptable" if:
  4836.  
  4837.    - It passes the CMTP validation checks.
  4838.  
  4839.    - Its timestamp is less than pcp_old (300) seconds behind the
  4840.      recipient's internal clock time.
  4841.  
  4842.    - It carries a recognized path identifier, provided it is not a SETUP
  4843.      message.
  4844.  
  4845.    An intermediate policy gateway on a path forwards acceptable PCP
  4846.    messages.  As we describe in section 7.4 below, SETUP messages must
  4847.    undergo additional tests at each intermediate policy gateway prior to
  4848.    forwarding.  Moreover, receipt of an acceptable ACCEPT, REFUSE,
  4849.    TEARDOWN, or ERROR message at either path agent or at any
  4850.    intermediate policy gateway indirectly cancels any active local CMTP
  4851.    retransmissions of the original SETUP message.  When a path agent or
  4852.    intermediate policy gateway receives an unacceptable path control
  4853.    message, it discards the message and logs the event for network
  4854.    management.  The path control message age limit reduces the
  4855.    likelihood of denial of service attacks based on message replay.
  4856.  
  4857. 7.4.  Setting Up and Tearing Down a Path
  4858.  
  4859.    Path setup begins when the originator generates a SETUP message
  4860.    containing:
  4861.  
  4862.    - The path identifier, including path directions to enable.
  4863.  
  4864.    - An indication of whether the message includes expedited data.
  4865.  
  4866.    -   The source user class identifier.
  4867.  
  4868.    - The requested services (see section 5.5.2) and source-specific
  4869.      information (see section 7.6.1) for the path.
  4870.  
  4871.  
  4872.  
  4873.  
  4874. Steenstrup                                                     [Page 87]
  4875.  
  4876. RFC 1479                     IDPR Protocol                     July 1993
  4877.  
  4878.  
  4879.    - For each domain on the path, the domain component, applicable
  4880.      transit policies, and entry and exit virtual gateways.
  4881.  
  4882.    The only mandatory requested service is the maximum path lifetime,
  4883.    pth_lif, and the only mandatory source-specific information is the
  4884.    data message integrity/authentication type.  If these are not
  4885.    specified in the path setup message, each recipient policy gateway
  4886.    assigns them default values, (60) minutes for pth_lif and no
  4887.    authentication for integrity/authentication type.  Each path agent
  4888.    and intermediate policy gateway tears down a path when the path
  4889.    lifetime is exceeded.  Hence, no single source can indefinitely
  4890.    monopolize policy gateway resources or still functioning parts of
  4891.    partially broken paths.
  4892.  
  4893.    After generating the SETUP message and establishing the proper local
  4894.    forwarding information, the originator selects the next policy
  4895.    gateway on the path and forwards the SETUP message to the selected
  4896.    policy gateway.  The next policy gateway selection procedure,
  4897.    described below, applies when either the originator or an
  4898.    intermediate policy gateway is making the selection.  We have elected
  4899.    to describe the procedure from the perspective of a selecting
  4900.    intermediate policy gateway.
  4901.  
  4902.    The policy gateway selects the next policy gateway on a path, in
  4903.    round-robin order from its list of policy gateways contained in the
  4904.    present or next virtual gateway, as explained below.  In selecting
  4905.    the next policy gateway, the policy gateway uses information
  4906.    contained in the SETUP message and information provided by VGP and by
  4907.    the intra-domain routing procedure.
  4908.  
  4909.    If the selecting policy gateway is a domain entry point, the next
  4910.    policy gateway must be:
  4911.  
  4912.    - A member of the next virtual gateway listed in the SETUP message.
  4913.  
  4914.    - Reachable according to intra-domain routes supporting the transit
  4915.      policies listed in the SETUP message.
  4916.  
  4917.    - Able to reach, according to VGP, the next domain component listed
  4918.      in the SETUP message.
  4919.  
  4920.    In addition, the selecting policy gateway may use quality of service
  4921.    information supplied by intra-domain routing to resolve ties between
  4922.    otherwise equivalent next policy gateways in the same domain.  In
  4923.    particular, the selecting policy gateway may select the next policy
  4924.    gateway whose connecting intra-domain route is optimal according to
  4925.    the requested services listed in the SETUP message.
  4926.  
  4927.  
  4928.  
  4929.  
  4930. Steenstrup                                                     [Page 88]
  4931.  
  4932. RFC 1479                     IDPR Protocol                     July 1993
  4933.  
  4934.  
  4935.    If the selecting policy gateway is a domain exit point, the next
  4936.    policy gateway must be:
  4937.  
  4938.    - A member of the current virtual gateway listed in the SETUP message
  4939.      (which is also the selecting policy gateway's virtual gateway).
  4940.  
  4941.    - Reachable according to VGP.
  4942.  
  4943.    - A member of the next domain component listed in the SETUP message.
  4944.  
  4945.    Once the originator or intermediate policy gateway selects a next
  4946.    policy gateway, it forwards the SETUP message to the selected policy
  4947.    gateway.  Each recipient (policy gateway or target) of an acceptable
  4948.    SETUP message performs several checks on the contents of the message,
  4949.    in order to determine whether to establish or reject the path.  We
  4950.    describe these checks in detail below from the perspective of a
  4951.    policy gateway as SETUP message recipient.
  4952.  
  4953. 7.4.1.  Validating Path Identifiers
  4954.  
  4955.    The recipient of a SETUP message first checks the path identifier, to
  4956.    make sure that it does not correspond to that of an already existing
  4957.    or recently extinct path.  To detect replays, malicious or otherwise,
  4958.    path agents and policy gateways maintain a record of each path that
  4959.    they establish, for max{pth_lif, pcp_old} seconds.  If the path
  4960.    identifier and timestamp carried in the SETUP message match a stored
  4961.    path identifier and timestamp, the policy gateway considers the
  4962.    message to be a retransmission and does not forward the message.  If
  4963.    the path identifier carried in the SETUP message matches a stored
  4964.    path identifier but the two timestamps do not agree, the policy
  4965.    gateway abandons path setup, logs the event for network management,
  4966.    and returns an ERROR message to the originator via the previous
  4967.    policy gateway.
  4968.  
  4969. 7.4.2.  Path Consistency with Configured Transit Policies
  4970.  
  4971.    Provided the path identifier in the SETUP message appears to be new,
  4972.    the policy gateway proceeds to determine whether the information
  4973.    contained within the SETUP message is consistent with the transit
  4974.    policies configured for its domain.  The policy gateway must locate
  4975.    the source and destination domains, the source host set and user
  4976.    class identifier, and the domain-specific information for its own
  4977.    domain, within the SETUP message, in order to evaluate path
  4978.    consistency.  If the policy gateway fails to recognize the source
  4979.    user class (or one or more of the requested services), it logs the
  4980.    event for network management but continues with path setup.  If the
  4981.    policy gateway fails to locate its domain within the SETUP message,
  4982.    it abandons path setup, logs the event for network management, and
  4983.  
  4984.  
  4985.  
  4986. Steenstrup                                                     [Page 89]
  4987.  
  4988. RFC 1479                     IDPR Protocol                     July 1993
  4989.  
  4990.  
  4991.    returns an ERROR message to the originator via the previous policy
  4992.    gateway.  The originator responds by tearing down the path and
  4993.    subsequently removing the route from its cache.
  4994.  
  4995.    Once the policy gateway locates its domain-specific portion of the
  4996.    SETUP message, it may encounter the following problems with the
  4997.    contents:
  4998.  
  4999.    - The domain-specific portion lists a transit policy not configured
  5000.      for the domain.
  5001.  
  5002.    - The domain-specific portion lists a virtual gateway not configured
  5003.      for the domain.
  5004.  
  5005.    In each case, the policy gateway abandons path setup, logs the event
  5006.    for network management, and returns an ERROR message to the
  5007.    originator via the previous policy gateway.  These types of ERROR
  5008.    messages indicate to the originator that the route may have been
  5009.    generated using information from an out-of-date CONFIGURATION
  5010.    message.
  5011.  
  5012.    The originator reacts to the receipt of such an ERROR message as
  5013.    follows.  First, it tears down the path and removes the route from
  5014.    its cache.  Then, it issues to a route server a ROUTE REQUEST message
  5015.    containing a directive to refresh the routing information database,
  5016.    with the most recent CONFIGURATION message from the domain that
  5017.    issued the ERROR message, before generating a new route.
  5018.  
  5019.    Once it verifies that its domain-specific information in the SETUP
  5020.    message is recognizable, the policy gateway then checks that the
  5021.    information contained within the SETUP message is consistent with the
  5022.    transit policies configured for its domain.  A policy gateway at the
  5023.    entry to a domain checks path consistency in the direction from
  5024.    originator to target, if the enabled path directions include
  5025.    originator to target.  A policy gateway at the exit to a domain
  5026.    checks path consistency in the direction from target to originator,
  5027.    if the enabled path directions include target to originator.
  5028.  
  5029.    When evaluating the consistency of the path with the transit policies
  5030.    configured for the domain, the policy gateway may encounter any of
  5031.    the following problems with SETUP message contents:
  5032.  
  5033.    - A transit policy does not apply in the given direction between the
  5034.      virtual gateways listed in the SETUP message.
  5035.  
  5036.    - A transit policy denies access to traffic from the given host set
  5037.      between the source and destination domains listed in the SETUP
  5038.      message.
  5039.  
  5040.  
  5041.  
  5042. Steenstrup                                                     [Page 90]
  5043.  
  5044. RFC 1479                     IDPR Protocol                     July 1993
  5045.  
  5046.  
  5047.    - A transit policy denies access to traffic from the source user
  5048.      class listed in the SETUP message.
  5049.  
  5050.    - A transit policy denies access to traffic at the current time.
  5051.  
  5052.    In each case, the policy gateway abandons path setup, logs the event
  5053.    for network management, and returns a REFUSE message to the
  5054.    originator via the previous policy gateway.  These types of REFUSE
  5055.    messages indicate to the originator that the route may have been
  5056.    generated using information from an out-of-date CONFIGURATION
  5057.    message.  The REFUSE message also serves to teardown the path.
  5058.  
  5059.    The originator reacts to the receipt of such a REFUSE message as
  5060.    follows. First, it removes the route from its cache.  Then, it issues
  5061.    to a route server a ROUTE REQUEST message containing a directive to
  5062.    refresh the routing information database, with the most recent
  5063.    CONFIGURATION message from the domain that issued the REFUSE message,
  5064.    before generating a new route.
  5065.  
  5066. 7.4.3.  Path Consistency with Virtual Gateway Reachability
  5067.  
  5068.    Provided the information contained in the SETUP message is consistent
  5069.    with the transit policies configured for its domain, the policy
  5070.    gateway proceeds to determine whether the path is consistent with the
  5071.    reachability of the virtual gateway containing the potential next
  5072.    hop.  To determine virtual gateway reachability, the policy gateway
  5073.    uses information provided by VGP and by the intra-domain routing
  5074.    procedure.
  5075.  
  5076.    When evaluating the consistency of the path with virtual gateway
  5077.    reachability, the policy gateway may encounter any of the following
  5078.    problems:
  5079.  
  5080.    - The virtual gateway containing the potential next hop is down.
  5081.  
  5082.    - The virtual gateway containing the potential next hop is not
  5083.      reachable via any intra-domain routes supporting the transit
  5084.      policies listed in the SETUP message.
  5085.  
  5086.    - The next domain component listed in the SETUP message is not
  5087.      reachable.
  5088.  
  5089.    Each of these determinations is made from the perspective of a single
  5090.    policy gateway and may not reflect actual reachability.  In each
  5091.    case, the policy gateway encountering such a problem returns a REFUSE
  5092.    message to the previous policy gateway which then selects a different
  5093.    next policy gateway, in round-robin order, as described in
  5094.    previously.  If the policy gateway receives the same response from
  5095.  
  5096.  
  5097.  
  5098. Steenstrup                                                     [Page 91]
  5099.  
  5100. RFC 1479                     IDPR Protocol                     July 1993
  5101.  
  5102.  
  5103.    all next policy gateways selected, it abandons path setup, logs the
  5104.    event for network management, and returns the REFUSE message to the
  5105.    originator via the previous policy gateway.  These types of REFUSE
  5106.    messages indicate to the originator that the route may have been
  5107.    generated using information from an out-of-date DYNAMIC message.  The
  5108.    REFUSE message also serves to teardown the path.
  5109.  
  5110.    The originator reacts to the receipt of such a REFUSE message as
  5111.    follows.  First, it removes the route from its cache.  Then, it
  5112.    issues to a route server a ROUTE REQUEST message containing a
  5113.    directive to refresh the routing information database, with the most
  5114.    recent DYNAMIC message from the domain that issued the REFUSE
  5115.    message, before generating a new route.
  5116.  
  5117. 7.4.4.  Obtaining Resources
  5118.  
  5119.    Once the policy gateway determines that the SETUP message contents
  5120.    are consistent with the transit policies and virtual gateway
  5121.    reachability of its domain, it attempts to gain resources for the new
  5122.    path.  For this version of IDPR, path resources consist of memory in
  5123.    the local forwarding information database.  However, in the future,
  5124.    path resources may also include reserved link bandwidth.
  5125.  
  5126.    If the policy gateway does not have sufficient resources to establish
  5127.    the new path, it uses the following algorithm to determine whether to
  5128.    generate a REFUSE message for the new path or a TEARDOWN message for
  5129.    an existing path in favor of the new path.  There are two cases:
  5130.  
  5131.  
  5132.    - No paths have been idle for more than pcp_idle (300) seconds.  In
  5133.      this case, the policy gateway returns a REFUSE message to the
  5134.      previous policy gateway.  This policy gateway then tries to select
  5135.      a different next policy gateway, as described previously, provided
  5136.      the policy gateway that issued the REFUSE message was not the
  5137.      target. If the REFUSE message was issued by the target or if there
  5138.      is no available next policy gateway, the policy gateway returns
  5139.      the REFUSE message to the originator via the previous policy
  5140.      gateway and logs the event for network management.  The REFUSE
  5141.      message serves to tear down the path.
  5142.  
  5143.    - At least one path has been idle for more than pcp_idle seconds.  In
  5144.      this case, the policy gateway tears down an older path in order to
  5145.      accommodate the newer path and logs the event for network
  5146.      management.  Specifically, the policy gateway tears down the least
  5147.      recently used path among those that have been idle for longer than
  5148.      pcp_idle seconds, resolving ties by choosing the oldest such path.
  5149.  
  5150.    If the policy gateway has sufficient resources to establish the path,
  5151.  
  5152.  
  5153.  
  5154. Steenstrup                                                     [Page 92]
  5155.  
  5156. RFC 1479                     IDPR Protocol                     July 1993
  5157.  
  5158.  
  5159.    it attempts to update its local forwarding information database with
  5160.    information about the path identifier, previous and next policy
  5161.    gateways on the path, and directions in which the path should be
  5162.    enabled for data traffic transport.
  5163.  
  5164. 7.4.5  Target Response
  5165.  
  5166.    When an acceptable SETUP message successfully reaches an entry policy
  5167.    gateway in the destination or destination proxy domain, this policy
  5168.    gateway performs all of the SETUP message checks described in the
  5169.    above sections.  The policy gateway's path agent then becomes the
  5170.    target, provided no checks fail, unless there is an explicit target
  5171.    specified in the SETUP message.  For example, remote route servers
  5172.    act as originator and target during RSQP message exchanges (see
  5173.    section 5.2).  If the recipient policy gateway is not the target, it
  5174.    attempts to forward the SETUP message to the target along an intra-
  5175.    domain route.  However, if the target is not reachable via intra-
  5176.    domain routing, the policy gateway abandons path setup, logs the
  5177.    event for network management, and returns a REFUSE message to the
  5178.    originator via the previous policy gateway.  The REFUSE message
  5179.    serves to tear down the path.
  5180.  
  5181.    Once the SETUP message reaches the target, the target determines
  5182.    whether it has sufficient path resources.  The target generates an
  5183.    ACCEPT message, provided it has sufficient resources to establish the
  5184.    path.  Otherwise, it generates a REFUSE message.
  5185.  
  5186.    The target may choose to use the reverse path to transport data
  5187.    traffic to the source domain, if the enabled path directions include
  5188.    10 or 11.  However, the target must first verify the consistency of
  5189.    the reverse path with its own domain's configured transit policies,
  5190.    before sending data traffic over that path.
  5191.  
  5192. 7.4.6.  Originator Response
  5193.  
  5194.    The originator expects to receive an ACCEPT, REFUSE, or ERROR message
  5195.    in response to a SETUP message and reacts as follows:
  5196.  
  5197.    - The originator receives an ACCEPT message, confirming successful
  5198.      path establishment.  To expedite data delivery, the originator may
  5199.      forward data messages along the path prior to receiving an ACCEPT
  5200.      message, with the understanding that there is no guarantee that the
  5201.      path actually exists.
  5202.  
  5203.    - The originator receives a REFUSE message or an ERROR message,
  5204.      implying that the path could not be successfully established.  In
  5205.      response, the originator attempts to set up a different path to the
  5206.      same destination, as long as the number of selected different paths
  5207.  
  5208.  
  5209.  
  5210. Steenstrup                                                     [Page 93]
  5211.  
  5212. RFC 1479                     IDPR Protocol                     July 1993
  5213.  
  5214.  
  5215.      does not exceed setup_try (3).  If the originator is unsuccessful
  5216.      after setup_try attempts, it abandons path setup and logs the event
  5217.      for network management.
  5218.  
  5219.    - The originator fails to receive any response to the SETUP message
  5220.      within setup_int microseconds after transmission.  In this case,
  5221.      the originator attempts path setup using the same policy route and
  5222.      a new path identifier, as long as the number of path setup attempts
  5223.      using the same route does not exceed setup_ret (2).  If the
  5224.      originator fails to receive a response to a SETUP message after
  5225.      setup_ret attempts, it logs the event for network management and
  5226.      then proceeds as though it received a negative response, namely a
  5227.      REFUSE or an ERROR, to the SETUP message.  Specifically, it
  5228.      attempts to set up a different path to the same destination, or it
  5229.      abandons path setup altogether, depending on the value of
  5230.      setup_try.
  5231.  
  5232. 7.4.7.  Path Life
  5233.  
  5234.    Once set up, a path does not live forever.  A path agent or policy
  5235.    gateway may tear down an existing path, provided any of the following
  5236.    conditions are true:
  5237.  
  5238.    - The maximum path lifetime (in minutes, bytes, or messages) has been
  5239.      exceeded at the originator, the target, or an intermediate policy
  5240.      gateway.  In each case, the IDPR entity detecting path expiration
  5241.      logs the event for network management and generates a TEARDOWN
  5242.      message as follows:
  5243.  
  5244.       o The originator path agent generates a TEARDOWN message for
  5245.         propagation toward the target.
  5246.  
  5247.       o The target path agent generates a TEARDOWN message for
  5248.         propagation toward the originator.
  5249.  
  5250.       o An intermediate policy gateway generates two TEARDOWN messages,
  5251.         one for propagation toward the originator and one for
  5252.         propagation toward the target.
  5253.  
  5254.    - The previous or next policy gateway becomes unreachable, across a
  5255.      virtual gateway or across a domain according to a given transit
  5256.      policy, and the path is not reparable.  In either case, the policy
  5257.      gateway detecting the reachability problem logs the event for
  5258.      network management and generates a TEARDOWN message as follows:
  5259.  
  5260.       o If the previous policy gateway is unreachable, an intermediate
  5261.         policy gateway generates a TEARDOWN message for propagation to
  5262.         the target.
  5263.  
  5264.  
  5265.  
  5266. Steenstrup                                                     [Page 94]
  5267.  
  5268. RFC 1479                     IDPR Protocol                     July 1993
  5269.  
  5270.  
  5271.       o If the next policy gateway is unreachable, an intermediate
  5272.         policy gateway generates a TEARDOWN message for propagation to
  5273.         the originator.
  5274.  
  5275.    - All of the policy gateway's path resources are in use at the
  5276.      originator, the target, or an intermediate policy gateway, a new
  5277.      path requires resources, and the given existing path is expendable,
  5278.      according to the least recently used criterion discussed in section
  5279.      7.4.4 above.  In each case, the IDPR entity initiating path
  5280.      preemption logs the event for network management and generates a
  5281.      TEARDOWN message as follows:
  5282.  
  5283.       o The originator path agent generates a TEARDOWN message for
  5284.         propagation toward the originator.
  5285.  
  5286.       o The target path agent generates a TEARDOWN message for
  5287.         propagation toward the originator.
  5288.  
  5289.       o An intermediate policy gateway generates two TEARDOWN messages,
  5290.         one for propagation toward the originator and one for
  5291.         propagation toward the target.
  5292.  
  5293.    Path teardown at a path agent or policy gateway, whether initiated by
  5294.    one of the above events, by receipt of a TEARDOWN message, or by
  5295.    receipt of a REFUSE message during path setup (as discussed in the
  5296.    previous sections), results in the path agent or policy gateway
  5297.    releasing all resources devoted to both directions of the path.
  5298.  
  5299. 7.5.  Path Failure and Recovery
  5300.  
  5301.    When a policy gateway fails, it may not be able to save information
  5302.    pertaining to its established paths.  Thus, when the policy gateway
  5303.    returns to service, it may have no recollection of the paths set up
  5304.    through it and hence may no longer be able to forward data messages
  5305.    along these paths.  We expect that when a policy gateway fails, it
  5306.    will usually be out of service for long enough that the up/down
  5307.    protocol and the intra-domain routing procedure can detect that the
  5308.    particular policy gateway is no longer reachable.  In this case,
  5309.    adjacent or neighbor policy gateways that have set up paths through
  5310.    the failed policy gateway and that have detected the failure, attempt
  5311.    local path repair (see section 7.5.2 below), and if unsuccessful,
  5312.    issue TEARDOWN messages for all affected paths.
  5313.  
  5314.  
  5315.  
  5316.  
  5317.  
  5318.  
  5319.  
  5320.  
  5321.  
  5322. Steenstrup                                                     [Page 95]
  5323.  
  5324. RFC 1479                     IDPR Protocol                     July 1993
  5325.  
  5326.  
  5327. 7.5.1.  Handling Implicit Path Failures
  5328.  
  5329.    Nevertheless, policy gateways along a path must be able to handle the
  5330.    case in which a policy gateway fails and subsequently returns to
  5331.    service without either the up/down protocol or the intra-domain
  5332.    routing procedure detecting the failure; we do not expect this event
  5333.    to occur often.  If the policy gateway, prior to failure, contained
  5334.    forwarding information for several established paths, it may now
  5335.    receive many IDPR data messages containing unrecognized path
  5336.    identifiers.  The policy gateway should alert the data sources that
  5337.    their paths through it are no longer viable.
  5338.  
  5339.    Policy gateways that receive IDPR data messages with unrecognized
  5340.    path identifiers take one of the following two actions, depending
  5341.    upon their past failure record:
  5342.  
  5343.    - The policy gateway has not failed in the past pg_up (24) hour
  5344.      period.  In this case, there are at least four possible reasons for
  5345.      the unrecognized path identifier in the data message:
  5346.  
  5347.       o The data message path identifier has been corrupted in a way
  5348.         that is not detectable by the integrity/authentication value, if
  5349.         one is present.
  5350.  
  5351.       o The policy gateway has experienced a memory error.
  5352.  
  5353.       o The policy gateway failed sometime during the life of the path
  5354.         and source sent no data on the path for a period of pg_up hours
  5355.         following the failure.  Although paths may persist for more than
  5356.         pg_up hours, we expect that they will also be used more
  5357.         frequently than once every pg_up hours.
  5358.  
  5359.       o The path was not successfully established, and the originator
  5360.         sent data messages down the path prior to receiving a response
  5361.         to its SETUP message.
  5362.  
  5363.       In all cases, the policy gateway discards the data message and
  5364.       logs the event for network management.
  5365.  
  5366.    - The policy gateway has failed at least once in the past pg_up hour
  5367.      period.  Thus, the policy gateway assumes that the unrecognized
  5368.      path identifier in the data message may be attributed to its
  5369.      failure.  In response to the data message, the policy gateway
  5370.      generates an ERROR message containing the unrecognized path
  5371.      identifier.  The policy gateway then sends the ERROR message back
  5372.      to the entity from which it received the data message, which should
  5373.      be equivalent to the previous policy gateway on the path.
  5374.  
  5375.  
  5376.  
  5377.  
  5378. Steenstrup                                                     [Page 96]
  5379.  
  5380. RFC 1479                     IDPR Protocol                     July 1993
  5381.  
  5382.  
  5383.    When the previous policy gateway receives such an ERROR message, it
  5384.    decides whether the message is acceptable.  If the policy gateway
  5385.    does not recognize the path identifier contained in the ERROR
  5386.    message, it does not find the ERROR message acceptable and
  5387.    subsequently discards the message.  However, if the policy gateway
  5388.    does find the ERROR message acceptable, it then determines whether it
  5389.    has already received an ACCEPT message for the given path.  If the
  5390.    policy gateway has not received an ACCEPT message for that path, it
  5391.    discards the ERROR message and takes no further action.
  5392.  
  5393.    If the policy gateway has received an ACCEPT message for that path,
  5394.    it then attempts path repair, as described in section 7.5.2 below.
  5395.    Only if path repair is unsuccessful does the previous policy gateway
  5396.    generate a TEARDOWN message for the path and return it to the
  5397.    originator.  The TEARDOWN message includes the domain and virtual
  5398.    gateway containing the policy gateway that failed, which aids the
  5399.    originator in selecting a new path that does not include the domain
  5400.    containing the failed policy gateway.  This mechanism ensures that
  5401.    path agents quickly discover and recover from disrupted paths, while
  5402.    guarding against unwarranted path teardown.
  5403.  
  5404. 7.5.2.  Local Path Repair
  5405.  
  5406.    Failure of one of more entities on a given path may render the path
  5407.    unusable.  If the failure is within a domain, IDPR relies on the
  5408.    intra-domain routing procedure to find an alternate route across the
  5409.    domain, which leaves the path unaffected.  If the failure is in a
  5410.    virtual gateway, policy gateways must bear the responsibility of
  5411.    repairing the path.  Policy gateways nearest to the failure are the
  5412.    first to recognize its existence and hence can react most quickly to
  5413.    repair the path.
  5414.  
  5415.    Relinquishing control over path repair to policy gateways in other
  5416.    domains may be unacceptable to some domain administrators.  The
  5417.    reason is that these policy gateways cannot guarantee construction of
  5418.    a path that satisfies the source policies of the source domain, as
  5419.    they have no knowledge of other domains' source policies.
  5420.  
  5421.    Nevertheless, limited local path repair is feasible, without
  5422.    distributing either source policy information throughout an
  5423.    internetwork or detailed path information among policy gateways in
  5424.    the same domain or in the same virtual gateway.  We say that a path
  5425.    is "locally reparable" if there exists an alternate route between two
  5426.    policy gateways, separated by at most one virtual gateway, on the
  5427.    path.  This definition covers path repair in the presence of failed
  5428.    routes between consecutive policy gateways as well as failed policy
  5429.    gateways themselves.
  5430.  
  5431.  
  5432.  
  5433.  
  5434. Steenstrup                                                     [Page 97]
  5435.  
  5436. RFC 1479                     IDPR Protocol                     July 1993
  5437.  
  5438.  
  5439.    An IDPR entity attempts local repair of an established path, in the
  5440.    direction from originator to target, immediately after detecting that
  5441.    the next policy gateway on the path is no longer reachable.  To
  5442.    prevent multiple path repairs in response to the same failure, we
  5443.    have stipulated that path repair can only be initiated in the
  5444.    direction from originator to target.  The IDPR entity initiating
  5445.    local path repair attempts to find an alternate path to the policy
  5446.    gateway immediately following the unreachable policy gateway on the
  5447.    path.
  5448.  
  5449.    Local path repair minimizes the disruption of data traffic flow
  5450.    caused by certain types of failures along an established path.
  5451.    Specifically, local path repair can accommodate an individual failed
  5452.    policy gateway or failed direct connection between two adjacent
  5453.    policy gateways.  However, it can only be attempted through virtual
  5454.    gateways containing multiple peer policy gateways.  Local path repair
  5455.    is not designed to repair paths traversing failed virtual gateways or
  5456.    domain partitions.  Whenever local path repair is impossible, the
  5457.    failing path must be torn down.
  5458.  
  5459. 7.5.3.  Repairing a Path
  5460.  
  5461.    When an IDPR entity detects through an ERROR message that the next
  5462.    policy gateway has no knowledge of a given path, it generates a
  5463.    REPAIR message and forwards it to the next policy gateway.  This
  5464.    REPAIR message will reestablish the path through the next policy
  5465.    gateway.
  5466.  
  5467.    When an entity detects that the next policy gateway on a path is no
  5468.    longer reachable, it takes one of the following actions, depending
  5469.    upon whether the entity is a member of the next policy gateway's
  5470.    virtual gateway.
  5471.  
  5472.    - If the entity is not a member of the next policy gateway's virtual
  5473.      gateway, then one of the following two conditions must be true:
  5474.  
  5475.       o The next policy gateway has a peer that is reachable via an
  5476.         intra-domain route consistent with the requested services.  In
  5477.         this case, the entity generates a REPAIR message containing the
  5478.         original SETUP message and forwards it to the next policy
  5479.         gateway's peer.
  5480.  
  5481.       o The next policy gateway has no peers that are reachable via
  5482.         intra-domain routes consistent with the requested services.  In
  5483.         this case, the entity tears down the path back to the
  5484.         originator.
  5485.  
  5486.    - If the entity is a member of the next policy gateway's virtual
  5487.  
  5488.  
  5489.  
  5490. Steenstrup                                                     [Page 98]
  5491.  
  5492. RFC 1479                     IDPR Protocol                     July 1993
  5493.  
  5494.  
  5495.    gateway, then one of the following four conditions must be true:
  5496.  
  5497.       o The next policy gateway has a peer that belongs to the same
  5498.         domain component and is directly-connected to and reachable from
  5499.         the entity.  In this case, the entity generates a REPAIR message
  5500.         and forwards it to the next policy gateway's peer.
  5501.  
  5502.       o The next policy gateway has a peer that belongs to the same
  5503.         domain component, is not directly-connected to the entity, but
  5504.         is directly-connected to and reachable from one of the entity's
  5505.         peers, which in turn is reachable from the entity via an intra-
  5506.         domain route consistent with the requested services.  In this
  5507.         case, the entity generates a REPAIR message and forwards it to
  5508.         its peer.
  5509.  
  5510.       o The next policy gateway has no operational peers within its
  5511.         domain component, but is directly-connected to and reachable
  5512.         from one of the entity's peers, which in turn is reachable from
  5513.         the entity via an intra-domain route consistent with the
  5514.         requested services.  In this case, the entity generates a REPAIR
  5515.         message and forwards it to its peer.
  5516.  
  5517.       o The next policy gateway has no operational peers within its
  5518.         domain component, and the entity has no operational peers which
  5519.         are both reachable via intra-domain routes consistent with the
  5520.         requested services and directly-connected to and reachable from
  5521.         the next policy gateway.  In this case, the entity tears down
  5522.         the path back to the originator.
  5523.  
  5524.    A recipient of a REPAIR message takes the following steps, depending
  5525.    upon its relationship to the entity that issued the REPAIR message.
  5526.  
  5527.    - The recipient and the issuing entity are in the same domain or in
  5528.      same virtual gateway.  In this case, the recipient extracts the
  5529.      SETUP message contained within the REPAIR message and treats the
  5530.      message as it would any other SETUP message.  Specifically, the
  5531.      recipient checks consistency of the path with its domain's transit
  5532.      policies and virtual gateway reachability.  If there are
  5533.      unrecognized portions of the SETUP message, the recipient generates
  5534.      an ERROR message, and if there are path inconsistencies, the
  5535.      recipient generates a REFUSE message.  In either case, the
  5536.      recipient returns the corresponding message to the policy gateway
  5537.      from which it received the REPAIR message.  Otherwise, if the
  5538.      recipient accepts the REPAIR message, it updates its local
  5539.      forwarding information database accordingly and forwards the REPAIR
  5540.      message to a potential next policy gateway, according to the
  5541.      information contained in the enclosed SETUP message.
  5542.  
  5543.  
  5544.  
  5545.  
  5546. Steenstrup                                                     [Page 99]
  5547.  
  5548. RFC 1479                     IDPR Protocol                     July 1993
  5549.  
  5550.  
  5551.    - The recipient and the issuing entity are in different domains and
  5552.      different virtual gateways.  In this case, the recipient extracts
  5553.      the SETUP message from the REPAIR message and determines whether
  5554.      the associated path matches any of its established paths.  If the
  5555.      path does not match an established path, the recipient generates a
  5556.      REFUSE message and returns it to the policy gateway from which it
  5557.      received the REPAIR message.  In response to the receipt of a
  5558.      REFUSE message, the policy gateway tries a different next policy
  5559.      gateway.
  5560.  
  5561.    The path is reparable, if a path match is discovered.  In this case,
  5562.    the recipient updates the path entry in the local forwarding
  5563.    information database and issues an ACCEPT message to the policy
  5564.    gateway from which it received the REPAIR message, which in turn
  5565.    returns the message to the entity that issued the REPAIR message.
  5566.    The path is irreparable if all potential next policy gateways have
  5567.    been exhausted and a path match has yet to be discovered.  In this
  5568.    case, the policy gateway that fails to locate a next policy gateway
  5569.    issues a TEARDOWN message to return to the originator.
  5570.  
  5571.    An IDPR entity expects to receive an ACCEPT, TEARDOWN, REFUSE, or
  5572.    ERROR message in response to a REPAIR message and reacts to these
  5573.    responses differently as follows:
  5574.  
  5575.    - The entity always returns a TEARDOWN message to the originator via
  5576.      previous policy gateway.
  5577.  
  5578.    - The entity does not return an ACCEPT message to the originator, but
  5579.      receipt of such a message indicates that the path has been
  5580.      successfully repaired.
  5581.  
  5582.    - The entity infers that the path is irreparable and subsequently
  5583.      tears down the path and logs the event for network management, upon
  5584.      receipt of a REFUSE or ERROR message or when no response to the
  5585.      REPAIR message arrives within setup_int microseconds.
  5586.  
  5587.    When an entity detects that the previous policy gateway on a path
  5588.    becomes unreachable, it expects to receive a REPAIR message within
  5589.    setup_wait microseconds.  If the entity does not receive a REPAIR
  5590.    message for the path within that time, it infers that the path is
  5591.    irreparable and subsequently tears down the path and logs the event
  5592.    for network management.
  5593.  
  5594. 7.6.  Path Control Message Formats
  5595.  
  5596.    The path control protocol number is equal to 3.  We describe the
  5597.    contents of each type of PCP message below.
  5598.  
  5599.  
  5600.  
  5601.  
  5602. Steenstrup                                                    [Page 100]
  5603.  
  5604. RFC 1479                     IDPR Protocol                     July 1993
  5605.  
  5606.  
  5607. 7.6.1.  SETUP
  5608.  
  5609.    The SETUP message type is equal to 0.
  5610.  
  5611.     0                   1                   2                   3
  5612.     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
  5613.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  5614.    |                            PATH ID                            |
  5615.    |                                                               |
  5616.    +-------------------------------+-------------------------------+
  5617.    |            SRC AD             |            HST SET            |
  5618.    +---------------+---------------+-------------------------------+
  5619.    |      UCI      |    UNUSED     |            NUM RQS            |
  5620.    +---------------+---------------+-------------------------------+
  5621.    |            DST AD             |            TGT ENT            |
  5622.    +-------------------------------+-------------------------------+
  5623.    |            AD PTR             |
  5624.    +-------------------------------+
  5625.    For each requested service for the path:
  5626.    +-------------------------------+-------------------------------+
  5627.    |            RQS TYP            |            RQS LEN            |
  5628.    +-------------------------------+-------------------------------+
  5629.    |                            RQS SRV                            |
  5630.    +---------------------------------------------------------------+
  5631.    For each domain contained in the path:
  5632.    +---------------+---------------+-------------------------------+
  5633.    |    AD LEN     |      VG       |            ADJ AD             |
  5634.    +---------------+---------------+-------------------------------+
  5635.    |            ADJ CMP            |            NUM TP             |
  5636.    +-------------------------------+-------------------------------+
  5637.    |              TP               |
  5638.    +-------------------------------+
  5639.  
  5640.    PATH ID
  5641.         (64 bits) Path identifier consisting of the numeric identifier
  5642.         for the originator's domain (16 bits), the numeric identifier
  5643.         for the originator policy gateway or route server (16 bits), the
  5644.         path direction (2 bits), and the local path identifier (30
  5645.         bits).
  5646.  
  5647.    SRC AD (16 bits) Numeric identifier for the source domain, which may
  5648.         be different from the originator domain if the originator domain
  5649.         is a proxy for the source.
  5650.  
  5651.    HST SET (16 bits) Numeric identifier for the source's host set.
  5652.  
  5653.    UCI (8 bits) Numeric identifier for the source user class.  The value
  5654.         0 indicates that there is no particular source user class.
  5655.  
  5656.  
  5657.  
  5658. Steenstrup                                                    [Page 101]
  5659.  
  5660. RFC 1479                     IDPR Protocol                     July 1993
  5661.  
  5662.  
  5663.    UNUSED (8 bits) Not currently used; must be set equal to 0.
  5664.  
  5665.    NUM RQS (16 bits) Number of requested services.
  5666.  
  5667.    DST AD (16 bits) Numeric identifier for the destination domain, which
  5668.         may be different from the target domain if the target domain is
  5669.         a proxy for the destination.
  5670.  
  5671.    TGT ENT (16 bits) Numeric identifier for the target entity.  A value
  5672.         of 0 indicates that there is no specific target entity.
  5673.  
  5674.    AD PTR (16 bits) Byte offset from the beginning of the message
  5675.         indicating the location of the beginning of the domain-specific
  5676.         information, contained in the right-most 15 bits.  The left-most
  5677.         bit indicates whether the message includes expedited data (1
  5678.         expedited data, 0 no expedited data).
  5679.  
  5680.    RQS TYP (16 bits) Numeric identifier for a type of requested service
  5681.         or source-specific information.  Valid requested services are
  5682.         described in section 5.5.2.  Valid source source-specific
  5683.         information includes the following types:
  5684.  
  5685.         12.  MD4/RSA data message authentication (see [16]).
  5686.  
  5687.         13.  MD5/RSA data message authentication (see [17]).
  5688.  
  5689.         14.  Billing address (variable).
  5690.  
  5691.         15.  Charge number (variable).
  5692.  
  5693.    RQS LEN (16 bits) Length of the requested service or source-specific
  5694.         information, in bytes, beginning with the next field.
  5695.  
  5696.    RQS SRV (variable) Description of the requested service or source-
  5697.         specific information.
  5698.  
  5699.    AD LEN (8 bits) Length of the information associated with a
  5700.         particular domain on the route, in bytes, beginning with the
  5701.         next field.
  5702.  
  5703.    VG (8 bits) Numeric identifier for an exit virtual gateway.
  5704.  
  5705.    ADJ AD (16 bits) Numeric identifier for an adjacent domain.
  5706.  
  5707.    ADJ CMP (16 bits) Numeric identifier for a component of the adjacent
  5708.         domain.  Used to aid a policy gateway in routing across a
  5709.         virtual gateway connected to a partitioned domain.
  5710.  
  5711.  
  5712.  
  5713.  
  5714. Steenstrup                                                    [Page 102]
  5715.  
  5716. RFC 1479                     IDPR Protocol                     July 1993
  5717.  
  5718.  
  5719.    NUM TP (16 bits) Number of transit policies that apply to the section
  5720.         of the path traversing the given domain component.
  5721.  
  5722.    TP (16 bits) Numeric identifier for a transit policy.
  5723.  
  5724. 7.6.2.  ACCEPT
  5725.  
  5726.    The ACCEPT message type is equal to 1.
  5727.  
  5728.     0                   1                   2                   3
  5729.     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
  5730.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  5731.    |                            PATH ID                            |
  5732.    |                                                               |
  5733.    +---------------+-----------------------------------------------+
  5734.    |    RSN TYP    |                    REASON                     |
  5735.    +---------------+-----------------------------------------------+
  5736.  
  5737.    PATH ID
  5738.         (64 bits) Path identifier contained in the original SETUP
  5739.         message.
  5740.  
  5741.    RSN TYP (optional, 8 bits) Numeric identifier for the reason for
  5742.         conditional path acceptance.
  5743.  
  5744.    REASON (optional, variable) Description of the reason for conditional
  5745.         path acceptance.  Currently, no reasons have been defined.
  5746.  
  5747. 7.6.3  REFUSE
  5748.  
  5749.    The REFUSE message type is equal to 2.
  5750.  
  5751.     0                   1                   2                   3
  5752.     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
  5753.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  5754.    |                            PATH ID                            |
  5755.    |                                                               |
  5756.    +---------------+-----------------------------------------------+
  5757.    |    RSN TYP    |                    REASON                     |
  5758.    +---------------+-----------------------------------------------+
  5759.  
  5760.    PATH ID
  5761.         (64 bits) Path identifier contained in the original SETUP
  5762.         message.
  5763.  
  5764.    RSN TYP (8 bits) Numeric identifier for the reason for path refusal.
  5765.  
  5766.    REASON (variable) Description of the reason for path refusal.  Valid
  5767.  
  5768.  
  5769.  
  5770. Steenstrup                                                    [Page 103]
  5771.  
  5772. RFC 1479                     IDPR Protocol                     July 1993
  5773.  
  5774.  
  5775.         reasons include the following types:
  5776.  
  5777.  
  5778.         1.  Transit policy does not apply between the virtual gateways in a
  5779.             given direction.  Numeric identifier for the transit policy (16
  5780.             bits).
  5781.  
  5782.         2.  Transit policy denies access to traffic from the host set between
  5783.             the source and destination domains.  Numeric identifier for the
  5784.             transit policy (16 bits).
  5785.  
  5786.         3.  Transit policy denies access to traffic from the source user
  5787.             class.  Numeric identifier for the transit policy (16 bits).
  5788.  
  5789.         4.  Transit policy denies access to traffic at the current time.
  5790.             Numeric identifier for the transit policy (16 bits).
  5791.  
  5792.         5.  Virtual gateway is down.  Numeric identifier for the virtual
  5793.             gateway (8 bits) and associated adjacent domain (16 bits).
  5794.  
  5795.         6.  Virtual gateway is not reachable according to the given transit
  5796.             policy.  Numeric identifier for the virtual gateway (8 bits),
  5797.             associated adjacent domain (16 bits), and transit policy (16
  5798.             bits).
  5799.  
  5800.         7.  Domain component is not reachable.  Numeric identifier for the
  5801.             domain (16 bits) and the component (16 bits).
  5802.  
  5803.         8.  Insufficient resources to establish the path.
  5804.  
  5805.         9.  Target is not reachable via intra-domain routing.
  5806.  
  5807.         10. No existing path with the given path identifier, in response to
  5808.             a REPAIR message only.
  5809.  
  5810. 7.6.4.  TEARDOWN
  5811.  
  5812.    The TEARDOWN message type is equal to 3.
  5813.  
  5814.     0                   1                   2                   3
  5815.     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
  5816.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  5817.    |                            PATH ID                            |
  5818.    |                                                               |
  5819.    +---------------+-----------------------------------------------+
  5820.    |    RSN TYP    |                    REASON                     |
  5821.    +---------------+-----------------------------------------------+
  5822.  
  5823.  
  5824.  
  5825.  
  5826. Steenstrup                                                    [Page 104]
  5827.  
  5828. RFC 1479                     IDPR Protocol                     July 1993
  5829.  
  5830.  
  5831.    PATH ID
  5832.         (64 bits) Path identifier contained in the original SETUP
  5833.         message.
  5834.  
  5835.    RSN TYP (8 bits) Numeric identifier for the reason for path teardown.
  5836.  
  5837.    REASON (variable) Description of the reason for path teardown. Valid
  5838.         reasons include the following types:
  5839.  
  5840.    1.  Virtual gateway is down.  Numeric identifier for the virtual
  5841.        gateway (8 bits) and associated adjacent domain (16 bits).
  5842.  
  5843.    2.  Virtual gateway is not reachable according to the given transit
  5844.        policy.  Numeric identifier for the virtual gateway (8 bits),
  5845.        associated adjacent domain (16 bits), and transit policy (16
  5846.        bits).
  5847.  
  5848.    3.  Domain component is not reachable.  Numeric identifier for the
  5849.        domain (16 bits) and the component (16 bits).
  5850.  
  5851.    4.  Maximum path lifetime exceeded.
  5852.  
  5853.    5.  Preempted path.
  5854.  
  5855.    6.  Unable to repair path.
  5856.  
  5857. 7.6.5.  ERROR
  5858.  
  5859.    The ERROR message type is equal to 4.
  5860.  
  5861.     0                   1                   2                   3
  5862.     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
  5863.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  5864.    |                            PATH ID                            |
  5865.    |                                                               |
  5866.    +---------------+---------------+-------------------------------+
  5867.    |      MSG      |    RSN TYP    |            REASON             |
  5868.    +---------------+---------------+-------------------------------+
  5869.  
  5870.    PATH ID
  5871.         (64 bits) Path identifier contained in the path control or data
  5872.         message in error.
  5873.  
  5874.    MSG (8 bits) Numeric identifier for the type of path control message
  5875.         in error.  This field is ignored for error type 5.
  5876.  
  5877.    RSN TYP (8 bits) Numeric identifier for the reason for the PCP
  5878.         message error.
  5879.  
  5880.  
  5881.  
  5882. Steenstrup                                                    [Page 105]
  5883.  
  5884. RFC 1479                     IDPR Protocol                     July 1993
  5885.  
  5886.  
  5887.    REASON (variable) Description of the reason for the PCP message
  5888.         error.  Valid reasons include the following types:
  5889.  
  5890.    1.   Path identifier is already currently active.
  5891.  
  5892.    2.   Domain does not appear in the SETUP message.
  5893.  
  5894.    3.   Transit policy is not configured for the domain.  Numeric
  5895.    identifer for
  5896.         the transit policy (16 bits).
  5897.  
  5898.    4.   Virtual gateway not configured for the domain.  Numeric
  5899.    identifier
  5900.         for the virtual gateway (8 bits) and associated adjacent domain
  5901.    (16
  5902.         bits).
  5903.  
  5904.    5.   Unrecognized path identifier in an IDPR data message.
  5905.  
  5906. 7.6.6.  REPAIR
  5907.  
  5908.    The REPAIR message type is equal to 5.  A REPAIR message contains the
  5909.    original SETUP message only.
  5910.  
  5911. 7.6.7.  Negative Acknowledgements
  5912.  
  5913.    When a policy gateway receives an unacceptable PCP message that
  5914.    passes the CMTP validation checks, it includes, in its CMTP ACK, an
  5915.    appropriate negative acknowledgement.  This information is placed in
  5916.    the INFORM field of the CMTP ACK (described previously in section
  5917.    2.4); the numeric identifier for each type of PCP negative
  5918.    acknowledgement is contained in the left-most 8 bits of the INFORM
  5919.    field.  Negative acknowledgements associated with PCP include the
  5920.    following types:
  5921.  
  5922.    1.  Unrecognized PCP message type.  Numeric identifier for the
  5923.        unrecognized message type (8 bits).
  5924.  
  5925.    2.  Out-of-date PCP message.
  5926.  
  5927.    3.  Unrecognized path identifier (for all PCP messages except SETUP).
  5928.        Numeric identifier for the unrecognized path (64 bits).
  5929.  
  5930. 8.  Security Considerations
  5931.  
  5932.    Refer to sections 1.6, 1.7, and 2.3 for details on security in IDPR.
  5933.  
  5934.  
  5935.  
  5936.  
  5937.  
  5938. Steenstrup                                                    [Page 106]
  5939.  
  5940. RFC 1479                     IDPR Protocol                     July 1993
  5941.  
  5942.  
  5943. 9.  Author's Address
  5944.  
  5945.    Martha Steenstrup
  5946.    BBN Systems and Technologies
  5947.    10 Moulton Street
  5948.    Cambridge, MA 02138
  5949.  
  5950.    Phone: (617) 873-3192
  5951.    Email: msteenst@bbn.com
  5952.  
  5953. References
  5954.  
  5955.    [1]  Clark, D., "Policy Routing in Internet Protocols", RFC 1102, May
  5956.         1989.
  5957.  
  5958.    [2]  Estrin, D., "Requirements for Policy Based Routing in the
  5959.         Research Internet", RFC 1125, November 1989.
  5960.  
  5961.    [3]  Little, M., "Goals and Functional Requirements for Inter-
  5962.         Autonomous System Routing", RFC 1126, July 1989.
  5963.  
  5964.    [4]  Breslau, L. and Estrin, D., "Design of Inter-Administrative
  5965.         Domain Routing Protocols", Proceedings of the ACM SIGCOMM '90
  5966.         Symposium, September 1990.
  5967.  
  5968.    [5]  Steenstrup, M., "An Architecture for Inter-Domain Policy Rout-
  5969.         ing", RFC 1478, July 1993.
  5970.  
  5971.    [6]  Austein, R., "DNS Support for IDPR", Work in Progress, March
  5972.         1993.
  5973.  
  5974.    [7]  Bowns, H. and Steenstrup, M., "Inter-Domain Policy Routing Con-
  5975.         figuration and Usage", Work in Progress, July 1991.
  5976.  
  5977.    [8]  Woodburn, R., "Definitions of Managed Objects for Inter-Domain
  5978.         Policy Routing (Version 1)", Work in Progress, March 1993.
  5979.  
  5980.    [9]  McQuillan, J., Richer, I., Rosen, E., and Bertsekas, D.,
  5981.         "ARPANET Routing Algorithm Improvements: Second Semiannual
  5982.         Technical Report", BBN Report No. 3940, October 1978.
  5983.  
  5984.    [10] Moy, J., "The OSPF Specification", RFC 1131, October 1989.
  5985.  
  5986.    [11] Oran, D. (editor), "Intermediate System to Intermediate System
  5987.         Routeing Exchange Protocol for Use in Conjunction with the Pro-
  5988.         tocol for Providing the Connectionless-mode Network Service (ISO
  5989.         8473)", ISO/IEC JTC1/SC6/WG2, October 1989.
  5990.  
  5991.  
  5992.  
  5993.  
  5994. Steenstrup                                                    [Page 107]
  5995.  
  5996. RFC 1479                     IDPR Protocol                     July 1993
  5997.  
  5998.  
  5999.    [12] Estrin, D., and Tsudik, G., "Secure Control of Transit Internet-
  6000.         work Traffic, TR-89-15, Computer Science Department, University
  6001.         of Southern California.
  6002.  
  6003.    [13] Linn, J., "Privacy Enhancement for Internet Electronic Mail:
  6004.         Part I - Message Encipherment and Authentication Procedures",
  6005.         RFC 1113, August 1989.
  6006.  
  6007.    [14] Kent, S., and Linn, J., "Privacy Enhancement for Internet Elec-
  6008.         tronic Mail: Part II - Certificate-based Key Management", RFC
  6009.         1114, August 1989.
  6010.  
  6011.    [15] Linn, J., "Privacy Enhancement for Internet Electronic Mail:
  6012.         Part III - Algorithms, Modes, and Identifiers", RFC 1115, August
  6013.         1989.
  6014.  
  6015.    [16] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320, April
  6016.         1992.
  6017.  
  6018.    [17] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April
  6019.         1992.
  6020.  
  6021.  
  6022.  
  6023.  
  6024.  
  6025.  
  6026.  
  6027.  
  6028.  
  6029.  
  6030.  
  6031.  
  6032.  
  6033.  
  6034.  
  6035.  
  6036.  
  6037.  
  6038.  
  6039.  
  6040.  
  6041.  
  6042.  
  6043.  
  6044.  
  6045.  
  6046.  
  6047.  
  6048.  
  6049.  
  6050. Steenstrup                                                    [Page 108]
  6051.  
  6052.