RFC 1479
Inter-Domain Policy Routing Protocol Specification: Version 1
Pages: 108
Historic
Historic
Part 3 of 4 – Pages 47 to 73
4. Routing Information Distribution Each domain participating in IDPR generates and distributes its routing information messages to route servers throughout an internetwork. IDPR routing information messages contain information about the transit policies in effect across the given domain and the virtual gateway connectivity to adjacent domains. Route servers in turn use IDPR routing information to generate policy routes between source and destination domains. There are three different procedures for distributing IDPR routing information: - The flooding protocol. In this case, a representative policy gateway in each domain floods its routing information messages to route servers in all other domains. - Remote route server communication. In this case, a route server distributes its domain's routing information messages to route servers in specific destination domains, by encapsulating these messages within IDPR data messages. Thus, a domain administrator may control the distribution of the domain's routing information by restricting routing information exchange with remote route servers. Currently, routing information distribution restrictions are not included in IDPR configuration information. - The route server query protocol. In this case, a policy gateway or route server requests routing information from another route server, which in turn responds with routing information from its database. The route server query protocol may be used for quickly updating the routing information maintained by a policy gateway or route server that has just been connected or reconnected to an internetwork. It may also be used to retrieve routing information from domains that restrict distribution of their routing information. In this section, we describe the flooding protocol only. In section 5, we describe the route server query protocol, and in section 5.2, we describe communication between route servers in separate domains. Policy gateways and route servers use CMTP for reliable transport of IDPR routing information messages flooded between peer, neighbor, and adjacent policy gateways and between those policy gateways and route servers. The issuing policy gateway must communicate to CMTP the maximum number of transmissions per routing information message, flood_ret, and the interval between routing information message retransmissions, flood_int microseconds. The recipient policy gateway or route server must determine routing information message
acceptability, as we describe in section 4.2.3 below. 4.1. AD Representatives We designate a single policy gateway, the "AD representative", for generating and distributing IDPR routing information about its domain, to ensure that the routing information distributed is consistent and unambiguous and to minimize the communication required for routing information distribution. There is usually only a single AD representative per domain, namely the lowest-numbered operational policy gateway in the domain. Within a domain, policy gateways need no explicit election procedure to determine the AD representative. Instead, all members of a set of policy gateways mutually reachable via intra-domain routes can agree on set membership and therefore on which member has the lowest number. A partitioned domain has as many AD representatives as it does domain components. In fact, the numeric identifier for an AD representative is identical to the numeric identifier for a domain component. One cannot normally predict when and where a domain partition will occur, and thus any policy gateway within a domain may become an AD representative at any time. To prepare for the role of AD representative in the event of a domain partition, every policy gateway must continually monitor its domain's IDPR routing information, through VGP and through the intra-domain routing procedure. 4.2. Flooding Protocol An AD representative policy gateway uses unrestricted flooding among all domains to distribute its domain's IDPR routing information messages to route servers in an internetwork. There are two kinds of IDPR routing information messages issued by each AD representative: CONFIGURATION and DYNAMIC messages. Each CONFIGURATION message contains the transit policy information configured by the domain administrator, including for each transit policy, its identifier, its specification, and the sets of virtual gateways configured as mutually reachable via intra-domain routes supporting the given transit policy. Each DYNAMIC message contains information about current virtual gateway connectivity to adjacent domains and about the sets of virtual gateways currently mutually reachable via intra- domain routes supporting the configured transit policies. The IDPR Flooding Protocol is similar to the flooding procedures described in [9]-[11]. Through flooding, the AD representative distributes its routing information messages to route servers in its own domain and in adjacent domains. After generating a routing information message, the AD representative distributes a copy to each
of its peers and to a selected VG representative (see section 3.1.4) in all other virtual gateways connected to the domain. Each VG representative in turn distributes a copy of the routing information message to each of its peers. We note that distribution of routing information messages among virtual gateways and among peers within a virtual gateway is identical to distribution of inter-VG messages in VGP, as described in section 3.1.3. Within a virtual gateway, each policy gateway distributes a copy of the routing information message: - To each route server in its configured set of route servers. A domain administrator should ensure that each route server not contained within a policy gateway appears in the set of configured route servers for at least two distinct policy gateways. Hence, such a route server will continue to receive routing information messages, even when one of the policy gateways becomes unreachable. However, the route server will normally receive duplicate copies of a routing information message. - To certain directly-connected adjacent policy gateways. A policy gateway distributes a routing information message to a directly-connected adjacent policy gateway in an adjacent domain component, only when it is the lowest-numbered operational peer with a direct connection to the given domain component. We note that each policy gateway knows, through information provided by VGP, which peers have direct connections to which components of the adjacent domain. If the policy gateway has direct connections to more than one adjacent policy gateway in that domain component, it selects the routing information message recipient according to the order in which the adjacent policy gateways appear in its database, choosing the first one encountered. This selection procedure ensures that a copy of the routing information message reaches each component of the adjacent domain, while limiting the number of copies distributed. Once a routing information message reaches an adjacent policy gateway, that policy gateway distributes copies of the message throughout its domain. The adjacent policy gateway, acting as the first recipient of the routing information message in its domain, follows the same message distribution procedure as the AD representative in the source domain, as described above. The flooding procedure terminates when all reachable route servers in an internetwork receive a copy of the routing information message. Neighbor policy gateways may receive copies of the same routing information message from different adjoining domains. If two neighbor policy gateways receive the message copies simultaneously,
they will distribute them to VG representatives in other virtual gateways within their domain, resulting in duplicate message distribution. However, each policy gateway stops the spread of duplicate routing information messages as soon as it detects them, as described in section 4.2.3 below. In the Internet, we expect simultaneous message receptions to be the exception rather than the rule, given the hierarchical structure of the current topology. 4.2.1. Message Generation An AD representative generates and distributes a CONFIGURATION message whenever there is a configuration change in a transit policy or virtual gateway associated with its domain. This ensures that route servers maintain an up-to-date view of a domain's configured transit policies and adjacencies. An AD representative may also distribute a CONFIGURATION message at a configurable period of conf_per (500) hours. A CONFIGURATION message contains, for each configured transit policy, the identifier assigned by the domain administrator, the specification, and the set of associated "virtual gateway groups". Each virtual gateway group comprises virtual gateways configured to be mutually reachable via intra-domain routes of the given transit policy. Accompanying each virtual gateway listed is an indication of whether the virtual gateway is configured to be a domain entry point, a domain exit point, or both according to the given transit policy. The CONFIGURATION message also contains the set of local route servers that the domain administrator has configured to be available to IDPR clients in other domains. An AD representative generates and distributes a DYNAMIC message whenever there is a change in currently supported transit policies or in current virtual gateway connectivity associated with its domain. This ensures that route servers maintain an up-to-date view of a domain's supported transit policies and existing adjacencies and how they differ from those configured for the domain. Specifically, an AD representative generates a DYNAMIC message whenever there is a change in the connectivity, through the given domain and with respect to a configured transit policy, between two components of adjoining domains. An AD representative may also distribute a DYNAMIC message at a configurable period of dyn_per (24) hours. A DYNAMIC message contains, for each configured transit policy, its identifier, associated virtual gateway groups, and domain components reachable through virtual gateways in each group. Each DYNAMIC message also contains the set of currently "unavailable", either down or unreachable, virtual gateways in the domain. We note that each virtual gateway group expressed in a DYNAMIC message may be a proper subset of one of the corresponding virtual gateway groups expressed in a CONFIGURATION message. For example,
suppose that, for a given domain, the virtual gateway group (VG
A,...,VG E) were configured for a transit policy such that each
virtual gateway was both a domain entry and exit point. Thus, all
virtual gateways in this group are configured to be mutually
reachable via intra-domain routes of the given transit policy. Now
suppose that VG E becomes unreachable because of a power failure and
furthermore that the remaining virtual gateways form two distinct
groups, (VG A,VG B) and (VG C,VG D), such that although virtual
gateways in both groups are still mutually reachable via some intra-
domain routes they are no longer mutually reachable via any intra-
domain routes of the given transit policy. In this case, the virtual
gateway groups for the given transit policy now become (VG A,VG B)
and (VG C,VG D); VG E is listed as an unavailable virtual gateway.
A route server uses information about the set of unavailable virtual
gateways to determine which of its routes are no longer viable, and
it subsequently removes such routes from its route database.
Although route servers could determine the set of unavailable virtual
gateways using information about configured virtual gateways and
currently reachable virtual gateways, the associated processing cost
is high. In particular, a route server would have to examine all
virtual gateway groups listed in a DYNAMIC message to determine
whether there are any unavailable virtual gateways in the given
domain. To reduce the message processing at each route server, we
have chosen to include the set of unavailable virtual gateways in
each DYNAMIC message.
In order to construct a DYNAMIC message, an AD representative
assembles information gathered from intra-domain routing and from
VGP. Specifically, the AD representative uses the following
information:
- VG CONNECT and UP/DOWN messages to determine the state, up or down,
of each of its domain's virtual gateways and the adjacent domain
components reachable through a given virtual gateway.
- Intra-domain routing information to determine, for each of its
domain's transit policies, whether a given virtual gateway in the
domain is reachable with respect to that transit policy.
- VG POLICY messages to determine the connectivity of adjoining
domain components, across the given domain and with respect to a
configured transit policy, such that these components are adjacent
to virtual gateways not currently reachable from the AD
representative's virtual gateway according to the given transit
policy.
4.2.2. Sequence Numbers Each IDPR routing information message carries a sequence number which, when used in conjunction with the timestamp carried in the CMTP message header, determines the recency of the message. An AD representative assigns a sequence number to each routing information message it generates, depending upon its internal clock time: - The AD representative sets the sequence number to 0, if its internal clock time is greater than the timestamp in its previously generated routing information message. - The AD representative sets the sequence number to 1 greater than the sequence number in its previously generated routing information message, if its internal clock time equals the timestamp for its previously generated routing information message and if the previous sequence number is less than the maximum value (currently 2**16 - 1). If the previous sequence number equals the maximum value, the AD representative waits until its internal clock time exceeds the timestamp in its previously generated routing information message and then sets the sequence number to 0. In general, we do not expect generation of multiple distinct IDPR routing information messages carrying identical timestamps, and so the sequence number may seem superfluous. However, the sequence number may become necessary during synchronization of an AD representative's internal clock. In particular, the AD representative may need to freeze the clock value during synchronization, and thus distinct sequence numbers serve to distinguish routing information messages generated during the clock synchronization interval. 4.2.3. Message Acceptance Prior to a policy gateway forwarding a routing information message or a route server incorporating routing information into its routing information database, the policy gateway or route server assesses routing information message acceptability. An IDPR routing information message is "acceptable" if: - It passes the CMTP validation checks. - Its timestamp is less than conf_old (530) hours behind the recipient's internal clock time for CONFIGURATION messages and less than dyn_old (25) hours behind the recipient's internal clock time for DYNAMIC messages. - Its timestamp and sequence number indicate that it is more recent
than the currently-stored routing information from the given
domain. If there is no routing information currently stored from
the given domain, then the routing information message contains, by
default, the more recent information.
Policy gateways acknowledge and forward acceptable IDPR routing
information messages, according to the flooding protocol described in
section 4.2 above. Moreover, each policy gateway retains the
timestamp and sequence number for the most recently accepted routing
information message from each domain and uses these values to
determine acceptability of routing information messages received in
the future. Route servers acknowledge the receipt of acceptable
routing information messages and incorporate the contents of these
messages into their routing information databases, contingent upon
criteria discussed in section 4.2.4 below; however, they do not
participate in the flooding protocol. We note that when a policy
gateway or route server first returns to service, it immediately
updates its routing information database with routing information
obtained from another route server, using the route server query
protocol described in section 5.
An AD representative takes special action upon receiving an
acceptable routing information message, supposedly generated by
itself but originally obtained from a policy gateway or route server
other than itself. There are at least three possible reasons for the
occurrence of this event:
- The routing information message has been corrupted in a way that is
not detectable by the integrity/authentication value.
- The AD representative has experienced a memory error.
- Some other entity is generating routing information messages on
behalf of the AD representative.
In any case, the AD representative logs the event for network
management. Moreover, the AD representative must reestablish its own
routing information messages as the most recent for its domain. To
do so, the AD representative waits until its internal clock time
exceeds the value of the timestamp in the received routing
information message and then generates a new routing information
message using the currently-stored domain routing information
supplied by VGP and by the intra-domain routing procedure. Note that
the length of time the AD representative must wait to generate the
new message is at most cmtp_new (300) seconds, the maximum CMTP-
tolerated difference between the received message's timestamp and the
AD representative's internal clock time.
IDPR routing information messages that pass the CMTP validity checks
but appear less recent than stored routing information are
unacceptable. Policy gateways do not forward unacceptable routing
information messages, and route servers do not incorporate the
contents of unacceptable routing information messages into their
routing information databases. Instead, the recipient of an
unacceptable routing information message acknowledges the message in
one of two ways:
- If the routing information message timestamp and sequence number
equal to the timestamp and sequence number associated with the
stored routing information for the given domain, the recipient
assumes that the routing information message is a duplicate and
acknowledges the message.
- If the routing information message timestamp and sequence number
indicate that the message is less recent than the stored routing
information for the domain, the recipient acknowledges the message
with an indication that the routing information it contains is
out-of-date. Such a negative acknowledgement is a signal to the
sender of the routing information message to request more up-to-
date routing information from a route server, using the route
server query protocol. Furthermore, if the recipient of the out-
of-date routing information message is a route server, it
regenerates a routing information message from its own routing
information database and forwards the message to the sender. The
sender may in turn propagate this more recent routing information
message to other policy gateways and route servers.
4.2.4. Message Incorporation
A route server usually stores the entire contents of an acceptable
IDPR routing information message in its routing information database,
so that it has access to all advertised transit policies when
generating a route and so that it can regenerate routing information
messages at a later point in time if requested to do so by another
route server or policy gateway. However, a route server may elect
not to store all routing information message contents. In
particular, the route server need not store any transit policy that
excludes the route server's domain as a source or any routing
information from a domain that the route server's domain's source
policies exclude for transit. Selective storing of routing
information message contents simplifies the route generation
procedure since it reduces the search space of possible routes, and
it limits the amount of route server memory devoted to routing
information. However, selective storing of routing information also
means that the route server cannot always regenerate the original
routing information message, if requested to do so by another route
server or policy gateway. An acceptable IDPR routing information message may contain transit policy information that is not well-defined according to the route server's perception. A CONFIGURATION message may contain an unrecognized domain, virtual gateway, or transit policy attribute, such as user class access restrictions or offered service. In this case, "unrecognized" means that the value in the routing information message is not listed in the route server's configuration database, as described previously in section 1.8.2. A DYNAMIC message may contain an unrecognized transit policy or virtual gateway. In this case, "unrecognized" means that the transit policy or virtual gateway was not listed in the most recent CONFIGURATION message for the given domain. Each route server can always parse an acceptable routing information messsage, even if some of the information is not well-defined, and thus can always use the information that it does recognize. Therefore, a route server can store the contents of acceptable routing information messages from domains in which it is interested, regardless of whether all contents appear to be well-defined at present. If a routing message contains unrecognized information, the route server may attempt to obtain the additional information it needs to decipher the unrecognized information. For a CONFIGURATION message, the route server logs the event for network management; for a DYNAMIC message, the route server requests, from another route server, the most recent CONFIGURATION message for the domain in question. When a domain is partitioned, each domain component has its own AD representative, which generates routing information messages on behalf of that component. Discovery of a domain partition prompts the AD representative for each domain component to generate and distribute a DYNAMIC message. In this case, a route server receives and stores more than one routing information message at a time for the given domain, namely one for each domain component. When the partition heals, the AD representative for the entire domain generates and distributes a DYNAMIC message. In each route server's routing information database, the new DYNAMIC message does not automatically replace all of the currently-stored DYNAMIC messages for the given domain. Instead, the new message only replaces that message whose AD representative matches the AD representative for the new message. The other DYNAMIC messages, generated during the period over which the partition occurred, remain in the routing information database until they attain their maximum lifetime, as described in section 4.2.5 below. Such stale information may lead to the generation of routes that result in path setup failures and hence the
selection of alternative routes. To reduce the chances of path setup failures, we will investigate, for a future version of IDPR, mechanisms for removing partition-related DYNAMIC messages immediately after a partition disappears. 4.2.5. Routing Information Database We expect that most of the IDPR routing information stored in a routing information database will remain viable for long periods of time, perhaps until a domain reconfiguration occurs. By "viable", we mean that the information reflects the current state of the domain and hence may be used successfully for generating policy routes. To reduce the probability of retaining stale routing information, a route server imposes a maximum lifetime on each database entry, initialized when it incorporates an accepted entry into its routing information database. The maximum lifetime should be longer than the corresponding message generation period, so that the database entry is likely to be refreshed before it attains its maximum lifetime. Each CONFIGURATION message stored in the routing information database has a maximum lifetime of conf_old (530) hours; each DYNAMIC message stored in the routing information database has a maximum lifetime of dyn_old (25) hours. Periodic generation of routing information messages makes it unlikely that any routing information message will remain in a routing information database for its full lifetime. However, a routing information message may attain its maximum lifetime in a route server that is separated from a internetwork for a long period of time. When an IDPR routing information message attains its maximum lifetime in a routing information database, the route server removes the message contents from its database, so that it will not generate new routes with the outdated routing information nor distribute old routing information in response to requests from other route servers or policy gateways. Nevertheless, the route server continues to dispense routes previously generated with the old routing information, as long as path setup (see section 7) for these routes succeeds. The route server treats routing information message lifetime expiration differently, depending on the type of routing information message. When a CONFIGURATION message expires, the route server requests, from another route server, the most recent CONFIGURATION message issued for the given domain. When a DYNAMIC message expires, the route server does not initially attempt to obtain more recent routing information. Instead, if route generation is necessary, the route server uses the routing information contained in the corresponding CONFIGURATION message for the given domain. Only if
there is a path setup failure (see section 7.4) involving the given domain does the route server request, from another route server, the most recent DYNAMIC message issued for the given domain. 4.3. Routing Information Message Formats The flooding protocol number is equal to 1. We describe the contents of each type of routing information message below. 4.3.1. CONFIGURATION The CONFIGURATION message type is equal to 0. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AD CMP | SEQ | +-------------------------------+-------------------------------+ | NUM TP | NUM RS | +-------------------------------+-------------------------------+ | RS | +-------------------------------+ For each transit policy configured for the domain: +-------------------------------+-------------------------------+ | TP | NUM ATR | +-------------------------------+-------------------------------+ For each attribute of the transit policy: +-------------------------------+-------------------------------+ | ATR TYP | ATR LEN | +-------------------------------+-------------------------------+ For the source/destination access restrictions attribute: +-------------------------------+ | NUM AD GRP | +-------------------------------+ For each domain group in the source/destination access restrictions: +-------------------------------+-------------------------------+ | NUM AD | AD | +---------------+---------------+-------------------------------+ | AD FLGS | NUM HST | HST SET | +---------------+---------------+-------------------------------+ For the temporal access restrictions attribute: +-------------------------------+ | NUM TIM | +-------------------------------+
For each set of times in the temporal access restrictions:
+---------------+-----------------------------------------------+
| TIM FLGS | DURATION |
+---------------+-----------------------------------------------+
| START |
+-------------------------------+-------------------------------+
| PERIOD | ACTIVE |
+-------------------------------+-------------------------------+
For the user class access restrictions attribute:
+-------------------------------+
| NUM UCI |
+-------------------------------+
For each UCI in the user class access restrictions:
+---------------+
| UCI |
+---------------+
For each offered service attribute:
+---------------------------------------------------------------+
| OFR SRV |
+---------------------------------------------------------------+
For the virtual gateway access restrictions attribute:
+-------------------------------+
| NUM VG GRP |
+-------------------------------+
For each virtual gateway group in the virtual gateway access
restrictions:
+-------------------------------+-------------------------------+
| NUM VG | ADJ AD |
+---------------+---------------+-------------------------------+
| VG | VG FLGS |
+---------------+---------------+
AD CMP
(16 bits) Numeric identifier for the domain component containing
the AD representative policy gateway.
SEQ (16 bits) Routing information message sequence number.
NUM TP (16 bits) Number of transit policy specifications contained in
the routing information message.
NUM RS (16 bits) Number of route servers advertised to serve clients
outside of the domain.
RS (16 bits) Numeric identifier for a route server.
TP (16 bits) Numeric identifier for a transit policy specification.
NUM ATR (16 bits) Number of attributes associated with the transit
policy.
ATR TYP (16 bits) Numeric identifier for a type of attribute. Valid
attributes include the following types:
- Set of virtual gateway access restrictions (see section 1.4.2)
associated with the transit policy (variable). This attribute must
be included.
- Set of source/destination access restrictions (see section 1.4.2)
associated with the transit policy (variable). This attribute may
be omitted. Absence of this attribute implies that traffic from
any source to any destination is acceptable.
- Set of temporal access restrictions (see section 1.4.2) associated
with the transit policy (variable). This attribute may be omitted.
Absence of this attribute implies that the transit policy applies
at all times.
- Set of user class access restrictions (see section 1.4.2)
associated with the transit policy (variable). This attribute may
be omitted. Absence of this attribute implies that traffic from
any user class is acceptable.
- Average delay in milliseconds (16 bits). This attribute may be
omitted.
- Delay variation in milliseconds (16 bits). This attribute may be
omitted.
- Average available bandwidth in bits per second (48 bits). This
attribute may be omitted.
- Available bandwidth variation in bits per second (48 bits). This
attribute may be omitted.
- MTU in bytes (16 bits). This attribute may be omitted.
- Charge per byte in thousandths of a cent (16 bits). This attribute
may be omitted.
- Charge per message in thousandths of a cent (16 bits). This
attribute may be omitted.
- Charge for session time in thousandths of a cent per second (16
bits). This attribute may be omitted. Absence of any charge
attribute implies that the domain provides free transit service.
ATR LEN (16 bits) Length of an attribute in bytes, beginning with the subsequent field. NUM AD GRP (16 bits) Number of source/destination domain groups (see section 1.4.2) associated with the source/destination access restrictions. NUM AD (16 bits) Number of domains or sets of domains in a domain group. AD (16 bits) Numeric identifier for a domain or domain set. AD FLGS (8 bits) Set of five flags indicating how to interpret the AD field, contained in the right-most bits. Proceeding left to right, the first flag indicates whether the transit policy applies to all domains or to specific domains (1 all, 0 specific), and when set to 1, causes the second and third flags to be ignored. The second flag indicates whether the domain identifier signifies a single domain or a domain set (1 single, 0 set). The third flag indicates whether the transit policy applies to the given domain or domain set (1 applies, 0 does not apply) and is used for representing complements of sets of domains. The fourth flag indicates whether the domain is a source (1 source, 0 not source). The fifth flag indicates whether the domain is a destination (1 destination, 0 not destination). At least one of the fourth and fifth flags must be set to 1. NUM HST (8 bits) Number of "host sets" (see section 1.4.2) associated with a particular domain or domain set. The value 0 indicates that all hosts in the given domain or domain set are acceptable sources or destinations, as specified by the fourth and fifth AD flags. HST SET (16 bits) Numeric identifier for a host set. NUM TIM (16 bits) Number of time specifications associated with the temporal access restrictions. Each time specification is split into a set of continguous identical periods, as we describe below. TIM FLGS (8 bits) Set of two flags indicating how to combine the time specifications, contained in the right-most bits. Proceeding left to right, the first flag indicates whether the transit policy applies during the periods specified in the time specification (1 applies, 0 does not apply) and is used for representing complements of policy applicability intervals. The second flag indicates whether the time specification takes precedence over the previous time specifications listed (1 precedence, 0 no precedence). Precedence is equivalent to the boolean OR and AND operators, in the following sense. At any given instant, a transit policy either applies or does not apply, according to a given time specification, and we can assign a boolean
value to the state of policy applicability according to a given time specification. If the second flag assumes the value 1 for a given time specification, that indicates the boolean operator OR should be applied to the values of policy applicability, according to the given time specification and to all previously listed time specifications. If the second flag assumes the value 0 for a given time specification, that indicates the boolean operator AND should be applied to the values of policy applicability, according to the given time specification and to all previously listed time specifications. DURATION (24 bits) Length of the time specification duration, in minutes. A value of 0 indicates an infinite duration. START (32 bits) Time at which the time specification first takes effect, in seconds elapsed since 1 January 1970 0:00 GMT. PERIOD (16 bits) Length of each time period within the time specification, in minutes. ACTIVE (16 bits) Length of the policy applicable interval during each time period, in minutes from the beginning of the time period. NUM UCI (16 bits) Number of user classes associated with the user class access restrictions. UCI (8 bits) Numeric identifier for a user class. NUM VG GRP (16 bits) Number of virtual gateway groups (see section 1.4.2) associated with the virtual gateway access restrictions. NUM VG (16 bits) Number of virtual gateways in a virtual gateway group. ADJ AD (16 bits) Numeric identifier for the adjacent domain to which a virtual gateway connects. VG (8 bits) Numeric identifier for a virtual gateway. VG FLGS (8 bits) Set of two flags indicating how to interpret the VG field, contained in the right-most bits. Proceeding left to right, the first flag indicates whether the virtual gateway is a domain entry point (1 entry, 0 not entry). The second flag indicates whether the virtual gateway is a domain exit point (1 exit, 0 not exit). At least one of the first and second flags must be set to 1.
4.3.2. DYNAMIC The DYNAMIC message type is equal to 1. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AD CMP | SEQ | +-------------------------------+-------------------------------+ | UNAVL VG | NUM PS | +-------------------------------+-------------------------------+ For each unavailable virtual gateway in the domain: +-------------------------------+---------------+---------------+ | ADJ AD | VG | UNUSED | +-------------------------------+---------------+---------------+ For each set of transit policies for the domain: +-------------------------------+-------------------------------+ | NUM TP | NUM VG GRP | +-------------------------------+-------------------------------+ | TP | +-------------------------------+ For each virtual gateway group associated with the transit policy set: +-------------------------------+-------------------------------+ | NUM VG | ADJ AD | +---------------+---------------+-------------------------------+ | VG | VG FLGS | NUM CMP | +---------------+---------------+-------------------------------+ | ADJ CMP | +-------------------------------+ AD CMP (16 bits) Numeric identifier for the domain component containing the AD representative policy gateway. SEQ (16 bits) Routing information message sequence number. UNAVL VG (16 bits) Number of virtual gateways in the domain component that are currently unavailable via any intra-domain routes. NUM PS (16 bits) Number of sets of transit policies listed. Transit policy sets provide a mechanism for reducing the size of DYNAMIC messages. A single set of virtual gateway groups applies to all transit policies in a given set. ADJ AD (16 bits) Numeric identifier for the adjacent domain to which a virtual gateway connects.
VG (8 bits) Numeric identifier for a virtual gateway.
UNUSED (8 bits) Not currently used; must be set equal to 0.
NUM TP (16 bits) Number of transit policies in a set.
NUM VGGRP (16 bits) Number of virtual gateway groups currently
associated with the transit policy set.
TP (16 bits) Numeric identifier for a transit policy.
NUM VG (16 bits) Number of virtual gateways in a virtual gateway
group.
VG FLGS (8 bits) Set of two flags indicating how to interpret the VG
field, contained in the right-most bits. Proceeding left to
right, the first flag indicates whether the virtual gateway is a
domain entry point (1 entry, 0 not entry). The second flag
indicates whether the virtual gateway is a domain exit point (1
exit, 0 not exit). At least one of the first and second flags
must be set to 1.
NUM CMP (16 bits) Number of adjacent domain components reachable via
direct connections through the virtual gateway.
ADJ CMP (16 bits) Numeric identifier for a reachable adjacent domain
component.
4.3.3. Negative Acknowledgements
When a policy gateway or route server receives an unacceptable IDPR
routing information message that passes the CMTP validation checks,
it includes, in its CMTP ACK, an appropriate negative
acknowledgement. This information is placed in the INFORM field of
the CMTP ACK (described previously in section 2.4); the numeric
identifier for each type of routing information message negative
acknowledgement is contained in the left-most 8 bits of the INFORM
field. Negative acknowledgements associated with routing information
messages include the following types:
1. Unrecognized IDPR routing information message type. Numeric
identifier for the unrecognized message type (8 bits).
2. Out-of-date IDPR routing information message. This is a signal
to the sender that it may not have the most recent routing
information for the given domain.
5. Route Server Query Protocol Each route server is responsible for maintaining both the routing information database and the route database and for responding to database information requests from policy gateways and other route servers. These requests and their responses are the messages exchanged via the Route Server Query Protocol (RSQP). Policy gateways and route servers normally invoke RSQP to replace absent, outdated, or corrupted information in their own routing information or route databases. In section 4, we discussed some of the situations in which RSQP may be invoked; in this section and in section 7, we discuss other such situations. 5.1. Message Exchange Policy gateways and route servers use CMTP for reliable transport of route server requests and responses. RSQP must communicate to CMTP the maximum number of transmissions per request/response message, rsqp_ret, and the interval between request/response message retransmissions, rsqp_int microseconds. A route server request/response message is "acceptable" if: - It passes the CMTP validation checks. - Its timestamp is less than rsqp_old (300) seconds behind the recipient's internal clock time. With RSQP, a requesting entity expects to receive an acknowledgement from the queried route server indicating whether the route server can accommodate the request. The route server may fail to fill a given request for either of the following reasons: - Its corresponding database contains no entry or only a partial entry for the requested information. - It is governed by special message distribution rules, imposed by the domain administrator, that preclude it from releasing the requested information. Currently, such distribution rules are not included in IDPR configuration information. For all requests that it cannot fill, the route server responds with a negative acknowledgement message carried in a CMTP acknowledgement, indicating the set of unfulfilled requests (see section 5.5.4). If the requesting entity either receives a negative acknowledgement or does not receive any acknowledgement after rsqp_ret attempts directed at the same route server, it queries a different route
server, as long as the number of attempted requests to different route servers does not exceed rsqp_try (3). Specifically, the requesting entity proceeds in round-robin order through its list of addressable route servers. However, if the requesting entity is unsuccessful after rsqp_try attempts, it abandons the request altogether and logs the event for network management. A policy gateway or a route server can request information from any route server that it can address. Addresses for local route servers within a domain are part of the configuration for each IDPR entity within a domain; addresses for remote route servers in other domains are obtained through flooded CONFIGURATION messages, as described previously in section 4.2.1. However, requesting entities always query local route servers before remote route servers, in order to contain the costs associated with the query and response. If the requesting entity and the queried route server are in the same domain, they can communicate over intra-domain routes, whereas if the requesting entity and the queried route server are in different domains, they must obtain a policy route and establish a path before they can communicate, as we describe below. 5.2. Remote Route Server Communication RSQP communication involving a remote route server requires a policy route and accompanying path setup (see section 7) between the requesting and queried entities, as these entities reside in different domains. After generating a request message, the requesting entity hands to CMTP its request message along with the remote route server's entity and domain identifiers. CMTP encloses the request in a DATAGRAM and hands the DATAGRAM and remote route server information to the path agent. Using the remote route server information, the path agent obtains, and if necessary sets up, a path to the remote route server. Once the path to the remote route server has been successfully established, the path agent encapsulates the DATAGRAM within an IDPR data message and forwards the data message along the designated path. When the path agent in the remote route server receives the IDPR data message, it extracts the DATAGRAM and hands it to CMTP. In addition, the path agent, using the requesting entity and domain identifiers contained in the path identifier, obtains, and if necessary sets up, a path back to the requesting entity. If the DATAGRAM fails any of the CMTP validation checks, CMTP returns a NAK to the requesting entity. If the DATAGRAM passes all of the CMTP validation checks, the remote route server assesses the acceptability of the request message. Provided the request message is acceptable, the remote route server determines whether it can
fulfill the request and directs CMTP to return an ACK to the requesting entity. The ACK may contain a negative acknowledgement if the entire request cannot be fulfilled. The remote route server generates responses for all requests that it can fulfill and returns the responses to the requesting entity. Specifically, the remote route server hands to CMTP its response and the requesting entity information. CMTP in turn encloses the response in a DATAGRAM. When returning an ACK, a NAK, or a response to the requesting entity, the remote route server hands the corresponding CMTP message and requesting entity information to the path agent. Using the requesting entity information, the path agent retrieves the path to the requesting entity, encapsulates the CMTP message within an IDPR data message, and forwards the data message along the designated path. When the path agent in the requesting entity receives the IDPR data message, it extracts the ACK, NAK, or response to its request and performs the CMTP validation checks for that message. In the case of a response messsage, the requesting entity also assesses message acceptability before incorporating the contents into the appropriate database. 5.3 Routing Information Policy gateways and route servers request routing information from route servers, in order to update their routing information databases. To obtain routing information from a route server, the requesting entity issues a ROUTING INFORMATION REQUEST message containing the type of routing information requested - CONFIGURATION messages, DYNAMIC messages, or both - and the set of domains from which the routing information is requested. Upon receiving a ROUTING INFORMATION REQUEST message, a route server first assesses message acceptability before proceeding to act on the contents. If the ROUTING INFORMATION REQUEST message is deemed acceptable, the route server determines how much of the request it can fulfill and then instructs CMTP to generate an acknowledgement, indicating its ability to fulfill the request. The route server proceeds to fulfill as much of the request as possible by reconstructing individual routing information messages, one per requested message type and domain, from its routing information database. We note that only a regenerated routing information message whose entire contents match that of the original routing information message may pass the CMTP integrity/authentication checks.
5.4. Routes Path agents request routes from route servers when they require policy routes for path setup. To obtain routes from a route server, the requesting path agent issues a ROUTE REQUEST message containing the destination domain and applicable service requirements, the maximum number of routes requested, a directive indicating whether to generate the routes or retrieve them from the route database, and a directive indicating whether to refresh the routing information database with the most recent CONFIGURATION or DYNAMIC message from a given domain, before generating the routes. To refresh its routing information database, a route server must obtain routing information from another route server. The path agent usually issues routing information database refresh directives in response to a failed path setup. We discuss the application of these directives in more detail in section 7.4. Upon receiving a ROUTE REQUEST message, a route server first assesses message acceptability before proceeding to act on the contents. If the ROUTE REQUEST message is deemed acceptable, the route server determines whether it can fulfill the request and then instructs CMTP to generate an acknowledgement, indicating its ability to fulfill the request. The route server proceeds to fulfill the request with policy routes, either retrieved from its route database or generated from its routing information database if necessary, and returns these routes in a ROUTE RESPONSE message. 5.5. Route Server Message Formats The route server query protocol number is equal to 2. We describe the contents of each type of RSQP message below. 5.5.1. ROUTING INFORMATION REQUEST The ROUTING INFORMATION REQUEST message type is equal to 0. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QRY AD | QRY RS | +-------------------------------+-------------------------------+ | NUM AD | AD | +---------------+---------------+-------------------------------+ | RIM FLGS | UNUSED | +---------------+---------------+ QRY AD (16 bits) Numeric identifier for the domain containing the
queried route server.
QRY RS (16 bits) Numeric identifier for the queried route server.
NUM AD (16 bits) Number of domains about which routing information is
requested. The value 0 indicates a request for routing
information from all domains.
AD (16 bits) Numeric identifier for a domain. This field is absent
when NUM AD equals 0.
RIM FLGS (8 bits) Set of two flags indicating the type of routing
information messages requested, contained in the right-most
bits. Proceeding left to right, the first flag indicates
whether the request is for a CONFIGURATION message (1
CONFIGURATION, 0 no CONFIGURATION). The second flag indicates
whether the request is for a DYNAMIC message (1 DYNAMIC, 0 no
DYNAMIC). At least one of the first and second flags must be
set to 1.
UNUSED (8 bits) Not currently used; must be set equal to 0.
5.5.2. ROUTE REQUEST
The ROUTE REQUEST message type is equal to 1.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| QRY AD | QRY RS |
+-------------------------------+-------------------------------+
| SRC AD | HST SET |
+---------------+---------------+-------------------------------+
| UCI | UNUSED | NUM RQS |
+---------------+---------------+-------------------------------+
| DST AD | PRX AD |
+---------------+---------------+-------------------------------+
| NUM RTS | GEN FLGS | RFS AD |
+---------------+---------------+-------------------------------+
| NUM AD |
+-------------------------------+
For each domain to be favored, avoided, or excluded:
+-------------------------------+---------------+---------------+
| AD | AD FLGS | UNUSED |
+-------------------------------+---------------+---------------+
For each requested service:
+-------------------------------+-------------------------------+
| RQS TYP | RQS LEN |
+-------------------------------+-------------------------------+
| RQS SRV |
+---------------------------------------------------------------+
QRY AD
(16 bits) Numeric identifier for the domain containing the
queried route server.
QRY RS (16 bits) Numeric identifier for the queried route server.
SRC AD (16 bits) Numeric identifier for the route's source domain.
HST SET (16 bits) Numeric identifier for the source's host set.
UCI (8 bits) Numeric identifier for the source user class. The value
0 indicates that there is no particular source user class.
UNUSED (8 bits) Not currently used; must be set equal to 0.
NUM RQS (16 bits) Number of requested services. The value 0
indicates that the source requests no special services.
DST AD (16 bits) Numeric identifier for the route's destination
domain.
PRX AD (16 bits) Numeric identifier for the destination domain's
proxy (see section 1.3.1). If the destination domain provides
the path agent function for its hosts, then the destination and
proxy domains are identical. A route server constructs routes
between the source domain's proxy and the destination domain's
proxy. We note that the source domain's proxy is identical to
the domain issuing the CMTP message containing the ROUTE REQUEST
message, and hence available in the CMTP header.
NUM RTS (8 bits) Number of policy routes requested.
GEN FLGS (8 bits) Set of three flags indicating how to obtain the
requested routes, contained in the right-most bits. Proceeding
left to right, the first flag indicates whether the route server
should retrieve existing routes from its route database or
generate new routes (1 retrieve, 0 generate). The second flag
indicates whether the route server should refresh its routing
information database before generating the requested routes (1
refresh, 0 no refresh) and when set to 1, causes the third flag
and the RFS AD field to become significant. The third flag
indicates whether the routing information database refresh
should include CONFIGURATION messages or DYNAMIC messages (1
configuration, 0 dynamic).
RFS AD (16 bits) Numeric identifier for the domain for which routing
information should be refreshed. This field is meaningful only
if the second flag in the GEN FLGS field is set to 1.
NUM AD (16 bits) Number of transit domains that are to be favored,
avoided, or excluded during route selection (see section 1.4.1).
AD (16 bits) Numeric identifier for a transit domain to be favored,
avoided, or excluded.
AD FLGS (8 bits) Three flags indicating how to interpret the AD
field, contained in the right-most bits. Proceeding left to
right, the first flag indicates whether the domain should be
favored (1 favored, 0 not favored). The second flag indicates
whether the domain should be avoided (1 avoided, 0 not avoided).
The third flag indicates whether the domain should be excluded
(1 excluded, 0 not excluded). No more than one of the first,
second, and third flags must set to 1.
RQS TYP (16 bits) Numeric identifier for a type of requested service.
Valid requested services include the following types:
1. Upper bound on delay, in milliseconds (16 bits). This attribute
may be omitted.
2. Minimum delay route. This attribute may be omitted.
3. Upper bound on delay variation, in milliseconds (16 bits). This
attribute may be omitted.
4. Minimum delay variation route. This attribute may be omitted.
5. Lower bound on bandwidth, in bits per second (48 bits). This
attribute may be omitted.
6. Maximum bandwidth route. This attribute may be omitted.
7. Upper bound on monetary cost, in cents (32 bits). This attribute
may be omitted.
8. Minimum monetary cost route. This attribute may be omitted.
9. Path lifetime in minutes (16 bits). This attribute may be omitted
but must be present if types 7 or 8 are present. Route servers
use path lifetime information together with domain charging
method to compute expected session monetary cost over a given
domain.
10. Path lifetime in messages (16 bits). This attribute may be
omitted but must be present if types 7 or 8 are present.
11. Path lifetime in bytes (48 bits). This attribute may be omitted
but must be present if types 7 or 8 are present.
RQS LEN
(16 bits) Length of the requested service, in bytes, beginning
with the next field.
RQS SRV
(variable) Description of the requested service.
5.5.3. ROUTE RESPONSE
The ROUTE RESPONSE message type is equal to 2.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NUM RTS |
+---------------+
For each route provided:
+---------------+---------------+
| NUM AD | RTE FLGS |
+---------------+---------------+
For each domain in the route:
+---------------+---------------+-------------------------------+
| AD LEN | VG | ADJ AD |
+---------------+---------------+-------------------------------+
| ADJ CMP | NUM TP |
+-------------------------------+-------------------------------+
| TP |
+-------------------------------+
NUM RTS
(16 bits) Number of policy routes provided.
RTE FLGS (8 bits) Set of two flags indicating the directions in which
a route can be used, contained in the right-most bits. Refer to
sections 6.2, 7, and 7.2 for detailed discussions of path
directionality. Proceeding left to right, the first flag
indicates whether the route can be used from source to
destination (1 from source, 0 not from source). The second flag
indicates whether the route can be used from destination to
source (1 from destination, 0 not from destination). At least
one of the first and second flags must be set to 1, if NUM RTS
is greater than 0.
NUM AD (8 bits) Number of domains in the policy route, not including
the first domain on the route.
AD LEN (8 bits) Length of the information associated with a
particular domain, in bytes, beginning with the next field.
VG (8 bits) Numeric identifier for an exit virtual gateway.
ADJ AD (16 bits) Numeric identifier for the adjacent domain connected
to the virtual gateway.
ADJ CMP (16 bits) Numeric identifier for the adjacent domain
component. Used by policy gateways to select a route across a
virtual gateway connecting to a partitioned domain.
NUM TP (16 bits) Number of transit policies that apply to the section
of the route traversing the domain component.
TP (16 bits) Numeric identifier for a transit policy.
5.5.4. Negative Acknowledgements
When a policy gateway receives an unacceptable RSQP message that
passes the CMTP validation checks, it includes, in its CMTP ACK, an
appropriate negative acknowledgement. This information is placed in
the INFORM field of the CMTP ACK (described previously in section
2.4); the numeric identifier for each type of RSQP negative
acknowledgement is contained in the left-most 8 bits of the INFORM
field. Negative acknowledgements associated with RSQP include the
following types:
1. Unrecognized RSQP message type. Numeric identifier for the
unrecognized message type (8 bits).
2. Out-of-date RSQP message.
3. Unable to fill requests for routing information from the
following domains. Number of domains for which requests cannot
be filled (16 bits); a value of 0 indicates that the route
server cannot fill any of the requests. Numeric identifier for
each domain for which a request cannot be filled (16 bits).
4. Unable to fill requests for routes to the following destination
domain. Numeric identifier for the destination domain (16 bits).
(page 73 continued on part 4)