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).
6. Route Generation
Route generation is the most computationally complex part of IDPR,
because of the number of domains and the number and heterogeneity of
policies that it must accommodate. Route servers must generate
policy routes that satisfy the requested services of the source
domains and respect the offered services of the transit domains.
We distinguish requested qualities of service and route generation
with respect to them as follows:
- Requested service limits include upper bounds on route delay, route
delay variation, and session monetary cost and lower bounds on
available route bandwidth. Generating a route that must satisfy
more than one quality of service constraint, for example route delay
of no more than X seconds and available route bandwidth of no less
than Y bits per second, is an NP-complete problem.
- Optimal requested services include minimum route delay, minimum
route delay variation, minimum session monetary cost, and maximum
available route bandwidth. In the worst case, the computational
complexity of generating a route that is optimal with respect to a
given requested service is O((N + L) log N) for Dijkstra's shortest
path first (SPF) search and O(N + (L * L)) for breadth-first (BF)
search, where N is the number of nodes and L is the number of links
in the search graph. Multi-criteria optimization, for example
finding a route with minimal delay variation and minimal session
monetary cost, may be defined in several ways. One approach to
multi-criteria optimization is to assign each link a single value
equal to a weighted sum of the values of the individual offered
qualities of service and generate a route that is optimal with
respect to this new criterion. However, selecting the weights that
yield the desired route generation behavior is itself an
optimization procedure and hence not trivial.
To help contain the combinatorial explosion of processing and memory
costs associated with route generation, we supply the following
guidelines for generation of suitable policy routes:
- Each route server should only generate policy routes from the
perspective of its own domain as source; it need not generate policy
routes for arbitrary source/destination domain pairs. Thus, we can
distribute the computational burden over all route servers.
- Route servers should precompute routes for which they anticipate
requests and should generate routes on demand only in order to
satisfy unanticipated route requests. Hence, a single route server
can distribute its computational burden over time.
- Route servers should cache the results of route generation, in order
to minimize the computation associated with responding to future
route requests.
- To handle requested service limits, a route server should always
select the first route generated that satisfies all of the requested
service limits.
- To handle multi-criteria optimization in route selection, a route
server should generate routes that are optimal with respect to the
first optimal requested service listed in the ROUTE REQUEST message.
The route server should resolve ties between otherwise equivalent
routes by evaluating these routes according to the other optimal
requested services contained in the ROUTE REQUEST message, in the
order in which they are listed. With respect to the route server's
routing information database, the selected route is optimal
according to the first optimal requested service listed in the ROUTE
REQUEST message but is not necessarily optimal according to any
other optimal requested service listed in the ROUTE REQUEST message.
ti 2 - To handle a mixture of requested service limits and optimal
requested services, a route server should generate routes that
satisfy all of the requested service limits. The route server
should resolve ties between otherwise equivalent routes by
evaluating these routes as described in the multi-criteria
optimization case above.
ti 2 - All else being equal, a route server should always prefer
minimum-hop routes, because they minimize the amount of network
resources consumed by the routes.
ti 2 - A route server should generate at least one route to each
component of a partitioned destination domain, because it may not
know in which domain component the destination host resides. Hence,
a route server can maximize the chances of providing a feasible
route to a destination within a partitioned domain.
6.1 Searching
All domains need not execute the identical route generation
procedure. Each domain administrator is free to specify the IDPR
route generation procedure for route servers in its own domain,
making the procedure as simple or as complex as desired.
We offer an IDPR route generation procedure as a model. With slight
modification, this procedure can be made to search in either BF or
SPF order. The procedure can be used either to generate a single
policy route from the source to a specified destination domain or to
generate a set of policy routes from the source domain to all
destination domains. If the source or destination domain has a
proxy, then the source or destination endpoint of the policy route
is a proxy domain and not the actual source or destination domain.
For high-bandwidth traffic flows, BF search is the recommended
search technique, because it produces minimum-hop routes. For low-
bandwidth traffic flows, the route server may use either BF search
or SPF search. The computational complexity of BF search is O(N +
L) and hence it is the search procedure of choice, except when
generating routes with optimal requested services. We recommend
using SPF search only for optimal requested services and never in
response to a request for a maximum bandwidth route.
6.1.1. Implementation
Data Structures:
The routing information database contains the graph of an
internetwork, in which virtual gateways are the nodes and intra-
domain routes between virtual gateways are the links. During route
generation, each route is represented as a sequence of virtual
gateways, domains, and relevant transit policies, together with a
list of route characteristics, stored in a temporary array and
indexed by destination domain.
- Execute the Policy Consistency routine, first with the source
domain the given domain and second with the destination domain as
the given domain. If any policy inconsistency precludes the
requested traffic flow, go to Exit.
- For each domain, initialize a null route, set the route bandwidth
to and set the following route characteristics to infinity: route
delay, route delay variation, session monetary cost, and route
length in hops.
- With each operational virtual gateway in the source or source proxy
domain, associate the initial route characteristics.
- Initialize a next-node data structure which will contain, for each
route in progress, the virtual gateway at the current endpoint of
the route together with the associated route characteristics. The
next-node data structure determines the order in which routes get
expanded.
BF: A fifo queue.
SPF: A heap, ordered according to the first optimal requested
service listed in the ROUTE REQUEST message.
Remove Next Node: These steps are performed for each virtual gateway
in the next-node data structure.
- If there are no more virtual gateways in the next-node data
structure, go to Exit.
- Extract a virtual gateway and its associated route
characteristics from the next-node data structure, obtain the
adjacent domain, and:
SPF: Remake the heap.
- If there is a specific destination domain and if for the primary
optimal service:
BF: Route length in hops.
SPF: First optimal requested service listed in the ROUTE
REQUEST message.
the extracted virtual gateway's associated route characteristic
is no better than that of the destination domain, go to Remove
Next Node.
- Execute the Policy Consistency routine with the adjacent domain
as given domain. If any policy inconsistency precludes the
requested traffic flow, go to Remove Next Node.
- Check that the source domain's transit policies do not preclude
traffic generated by members of the source host set with the
specified user class and requested services, from flowing to the
adjacent domain as destination. This check is necessary because
the route server caches what it considers to be all feasible
routes, to intermediate destination domains, generated during
the computation of the requested route. If there are no policy
inconsistencies, associate the route and its characteristics
with the adjacent domain as destination.
- If there is a specific destination domain and if the adjacent
domain is the destination or destination proxy domain, go to
Remove Next Node.
- Record the set of all exit virtual gateways in the adjacent
domain which the adjacent domain's transit policies permit the
requested traffic flow and which are currently reachable from
the entry virtual gateway.
Next Node:
These steps are performed for all exit virtual gateways in the
above set.
- If there are no exit virtual gateways in the set, go to Remove
Next Node.
- Compute the characteristics for the route to the exit virtual
gateway, and check that all of the route characteristics are
within the requested service limits. If any of the route
characteristics are outside of these limits, go to Next Node.
- Compare these route characteristics with those already
associated with the exit virtual gateway (there may be none, if
this is the first time the exit virtual gateway has been visited
in the search), according to the primary optimal service.
- Select the route with the optimal value of the primary optimal
service, resolve ties by considering optimality according to any
other optimal requested services in the order in which they are
listed in the ROUTE REQUEST message, and associate the selected
route and its characteristics with the exit virtual gateway.
- Add the virtual gateway to the next-node structure:
BF: Add to the end of the fifo queue.
SPF: Add to the heap.
and go to Next Node.
Exit:
Return a response to the route request, consisting of either a
set of candidate policy routes or an indication that the route
request cannot be fulfilled.
Policy Consistency: Check policy consistency for the given domain.
- Check that the given domain is not specified as an excluded
domain in the route request.
- Check that the given domain's transit policies do not preclude
traffic generated by members of the source host set with the
specified user class and requested services, from flowing to the
destination domain.
During the computation of the requested routes, a route server also
caches what it considers to be all feasible routes to intermediate
destination domains, thus increasing the chances of being able to
respond to a future route request without having to generate a new
route. The route server does perform some policy consistency checks
on the routes, as they are generated, to intermediate destinations.
However, these routes may not in fact be feasible; the transit
domains contained on the routes may not permit traffic between the
source and the given intermediate destinations. Hence, before
dispensing such a route in response to a route request, a route
server must check that the transit policies of the constituent
domains are consistent with the source and destination of the traffic
flow.
6.2. Route Directionality
A path agent may wish to set up a bidirectional path using a route
supplied by a route server. (Refer to sections 7.2 and 7.4 for
detailed discussions of path directionality.) However, a route
server can only guarantee that the routes it supplies are feasible if
used in the direction from source to destination. The reason is that
the route server, which resides in the source or source proxy domain,
does not have access to, and thus cannot account for, the source
policies of the destination domain. Nevertheless, the route server
can provide the path agent with an indication of its assessment of
route feasibility in the direction from destination to source.
A necessary but insufficient condition for a route to be feasible in
the direction from destination to source is as follows. The route
must be consistent, in the direction from destination to source, with
the transit policies of the domains that compose the route. The
transit policy consistency checks performed by the route server
during route generation account for the direction from source to
destination but not for the direction from destination to source.
Only after a route server generates a feasible route from source to
destination does it perform the transit policy consistency checks for
the route in the direction from destination to source. Following
these checks, the route server includes in its ROUTE RESPONSE message
to the path agent an indication of its assessment of route
feasibility in each direction.
6.3. Route Database
A policy route, as originally specified by a route server, is an
ordered list of virtual gateways, domains, and transit policies: VG 1
- AD 1 - TP 1 - ... - VG n - AD n - TP n. where VG i is the virtual
gateway that serves as exit from AD i-1 and entry to AD i, and TP i
is the set of transit policies associated with AD i and relevant to
the particular route. Each route is indexed by source and
destination domain. Route servers and paths agents store policy
routes in route databases maintained as caches whose entries must be
periodically flushed to avoid retention of stale policy routes. A
route server's route database is the set of all routes it has
generated on behalf of its domain as source or source proxy;
associated with each route in the database are its route
characteristics. A path agent's route database is the set of all
routes it has requested and received from route servers on behalf of
hosts for which it is configured to act.
When attempting to locate a feasible route for a traffic flow, a path
agent first consults its own route database before querying a route
server. If the path agent's route database contains one or more
routes between the given source and destination domains and
accommodating the given host set and UCI, then the path agent checks
each such route against the set of excluded domains listed in the
source policy. The path agent either selects the first route
encountered that does not include the excluded domains, or, if no
such route exists in its route database, requests a route from a
route server.
A path agent must query a route server for routes when it is unable
to fulfill a route request from its own route database. Moreover, we
recommend that a path agent automatically forward to a route server,
all route requests with non-null requested services. The reason is
that the path agent retains no route characteristics in its route
database. Hence, the path agent cannot determine whether an entry in
its route database satisfies the requested services.
When responding to a path agent's request for a policy route, a route
server first consults its route database, unless the ROUTE REQUEST
message contains an explicit directive to generate a new route. If
its route database contains one or more routes between the given
source and destination domains and accommodating the given host set
and UCI, the route server checks each such route against the set of
excluded domains listed in the ROUTE REQUEST message. The route
server either selects all routes encountered that do not include the
excluded domains, or, if no such route exists in its route database,
attempts to generate such a route. Once the route server selects a
set of routes, it then checks each such route against the services
requested by the path agent and the services offered by the domains
composing the route. To obtain the offered services information, the
route server consults its routing information database. The route
server either selects the first route encountered that is consistent
with both the requested and offered services, or, if no such route
exists in its route database, attempts to generate such a route.
6.3.1. Cache Maintenance
Each route stored in a route database has a maximum cache lifetime
equal to rdb_rs minutes for a route server and rdb_ps minutes for a
path agent. Route servers and path agents reclaim cache space by
flushing entries that have attained their maximum lifetimes.
Moreover, paths agents reclaim cache space for routes whose paths
have failed to be set up successfully or have been torn down (see
section 7.4).
Nevertheless, cache space may become scarce, even with reclamation of
entries. If a cache fills, the route server or path agent logs the
event for network management. To obtain space in the cache when the
cache is full, the route server or path agent deletes from the cache
the oldest entry.
7. Path Control Protocol and Data Message Forwarding Procedure
Two entities in different domains may exchange IDPR data messages,
only if there exists an IDPR path set up between the two domains.
Path setup requires cooperation among path agents and intermediate
policy gateways. Path agents locate policy routes, initiate the Path
Control Protocol (PCP), and manage existing paths between
administrative domains. Intermediate policy gateways verify that a
given policy route is consistent with their domains' transit
policies, establish the forwarding information, and forward messages
along existing paths.
Each policy gateway and each route server contains a path agent. The
path agent that initiates path setup in the source or source proxy
domain is the "originator", and the path agent that handles the
originator's path setup message in the destination or destination
proxy domain is the "target". Every path has two possible directions
of traffic flow: from originator to target and from target to
originator. Path control messages are free to travel in either
direction, but data messages may be restricted to only one direction.
Once a path for a policy route is set up, its physical realization is
a set of consecutive policy gateways, with policy gateways or route
servers forming the endpoints. Two successive entities in this set
belong to either the same domain or the same virtual gateway. A
policy gateway or route server may, at any time, recover the
resources dedicated to a path that goes through it by tearing down
that path. For example, a policy gateway may decide to tear down a
path that has not been used for some period of time.
PCP may build multiple paths between source and destination domains,
but it is not responsible for managing such paths as a group or for
eliminating redundant paths.
7.1. An Example of Path Setup
We illustrate how path setup works by stepping through an example.
Suppose host Hx in domain AD X wants to communicate with host Hy in
domain AD Y and that both AD X and AD Y support IDPR. Hx need not
know the identity of its own domain or of Hy's domain in order to
send messages to Hy. Instead, Hx simply forwards a message bound for
Hy to one of the gateways on its local network, according to its
local forwarding information only. If the recipient gateway is a
policy gateway, the resident path agent determines how to forward the
message outside of the domain. Otherwise, the recipient gateway
forwards the message to another gateway in AD X, according to its
local forwading information. Eventually, the message will arrive at
a policy gateway in AD X, as policy gateways are the only egress
points to other domains, in domains that support IDPR.
The path agent resident in the recipient policy gateway uses the
message header, including source and destination addresses and any
requested service information (for example, type of service), in
order to determine whether it is an intra-domain or inter-domain
message, and if inter-domain, whether it requires an IDPR policy
route. Specifically, the path agent attempts to locate a forwarding
information database entry for the given traffic flow, from the
information contained in the message header. In the future, for IP
messages, the relevant header information may also include special
service-specific IP options or even information from higher layer
protocols.
Forwarding database entries exist for all of the following:
- All intra-domain traffic flows. Intra-domain forwarding
information is integrated into the forwarding information database
as soon as it is received.
- Inter-domain traffic flows that do not require IDPR policy routes.
Non-IDPR forwarding information is integrated into the forwarding
database as soon as it is received.
- IDPR inter-domain traffic flows for which a path has already been
set up. IDPR forwarding information is integrated into the
forwarding database only during path setup.
The path agent uses the message header contents to guide the search
for a forwarding information database entry for a given traffic flow.
We recommend a radix search to locate such an entry. When the search
terminates, it produces either an entry, or, in the case of a new
IDPR traffic flow, a directive to generate an entry. If the search
terminates in an existing forwarding information database entry, the
path agent forwards the message according to that entry.
Suppose that the search terminates indicating that the traffic flow
from Hx to Hy requires an IDPR policy route and that no entry in the
forwarding information database yet exists for that traffic flow. In
this case, the path agent first determines the source and destination
domains associated with the message's source and destination
addresses, before attempting to obtain a policy route. The path
agent relies on the mapping servers to supply the domain information,
but it caches all mapping server responses locally to limit the
number of future queries. When attempting to resolve an address to a
domain, the path agent always checks its local cache before
contacting a mapping server.
After obtaining the domain information, the path agent attempts to
obtain a policy route to carry the traffic from Hx to Hy. The path
agent relies on route servers to supply policy routes, but it caches
all route server responses locally to limit the number of future
queries. When attempting to locate a suitable policy route, the path
agent usually consults its local cache before contacting a route
server, as described previously in section 6.3.
If no suitable cache entry exists, the path agent queries the route
server, providing it with the source and destination domains together
with source policy information carried in the host message or
specified through configuration. Upon receiving a policy route
query, a route server consults its route database. If it cannot
locate a suitable route in its route database, the route server
attempts to generate at least one route to AD Y, consistent with the
requested services for Hx.
The route server always returns a response to the path agent,
regardless of whether it is successful in locating a suitable policy
route. The response to a successful route query consists of a set of
candidate routes, from which the path agent makes its selection. We
expect that a path agent will normally choose a single route from a
candidate set. Nevertheless, IDPR does not preclude a path agent
from selecting multiple routes from the candidate set. A path agent
may desire multiple routes to support features such as fault
tolerance or load balancing; however, IDPR does not currently specify
how the path agent should use multiple routes.
If the policy route is a new route provided by the route server,
there will be no existing path for the route, and thus the path agent
must set up such a path. However, if the policy route is an existing
route extracted from the path agent's cache, there may well be an
existing path for the route, set up to accommodate a host traffic
flow. IDPR permits multiple traffic flows to use the same path,
provided that all traffic flows sharing the path travel between the
same endpoint domains and have the same service requirements.
Nevertheless, IDPR does not preclude a path agent from setting up
distinct paths along the same policy route to preserve the
distinction between host traffic flows.
The path agent associates an identifier with the path, which is
included in each message that travels down the path and is used by
the policy gateways along the path in order to determine how to
forward the message. If the path already exists, the path agent uses
the preexisting identifier. However, for new paths, the path agent
chooses a path identifier that is different from those of all other
paths that it manages. The path agent also updates its forwarding
information database to reference the path identifier and modifies
its search procedure to yield the correct entry in the forwarding
information database given the data message header.
For new paths, the path agent initiates path setup, communicating the
policy route, in terms of requested services, constituent domains,
relevant transit policies, and the connecting virtual gateways, to
policy gateways in intermediate domains. Using this information, an
intermediate policy gateway determines whether to accept or refuse
the path and to which next policy gateway to forward the path setup
information. The path setup procedure allows policy gateways to set
up a path in both directions simultaneously. Each intermediate
policy gateway, after path acceptance, updates its forwarding
information database to include an entry that associates the path
identifier with the appropriate previous and next hop policy
gateways.
When a policy gateway in AD Y accepts a path, it notifies the source
path agent in AD X. We expect that the source path agent will
normally wait until a path has been successfully established before
using it to transport data traffic. However, PCP does not preclude a
path agent from forwarding messages along a path prior to
confirmation of successful path establishment. Paths remain in place
until they are torn down because of failure, expiration, or when
resources are scarce, preemption in favor of other paths.
We note that data communication between Hx and Hy may occur over two
separate IDPR paths: one from AD X to AD Y and one from AD Y to AD X.
The reasons are that within a domain, hosts know nothing about path
agents nor IDPR paths, and path agents know nothing about other path
agents' existing IDPR paths. Thus, in AD Y, the path agent that
terminates the path from AD X may not be the same as the path agent
that receives traffic from Hy destined for Hx. In this case, receipt
of traffic from Hy forces the second path agent to set up an
independent path from AD Y to AD X.
7.2. Path Identifiers
Each path has an associated path identifier, unique throughout an
internetwork. Every IDPR data message travelling along that path
includes the path identifier, used for message forwarding. The path
identifier is the concatenation of three items: the identifier of the
originator's domain, the identifier of the originator's policy
gateway or route server, and a 32-bit local path identifier specified
by the originator. The path identifier and the CMTP transaction
identifier have analogous syntax and play analogous roles in their
respective protocols.
When issuing a new path identifier, the originator always assigns a
local path identifier that is different from that of any other active
or recently torn-down path originally set up by that path agent.
This helps to distinguish new paths from replays. Hence, the
originator must keep a record of each extinct path for long enough
that all policy gateways on the path will have eliminated any
reference to it from their memories. The right-most 30 bits of the
local identifier are the same for each path direction, as they are
assigned by the originator. The left-most 2 bits of the local
identifier indicate the path direction.
At path setup time, the originator specifies which of the path
directions to enable contingent upon the information received from
the route server in the ROUTE RESPONSE message. By "enable", we mean
that each path agent and each intermediate policy gateway establishes
an association between the path identifier and the previous and next
policy gateways on the path, which it uses for forwarding data
messages along that path. IDPR data messages may travel in the
enabled path directions only, but path control messages are always
free to travel in either path direction. The originator may enable
neither path direction, if the entire data transaction can be carried
in the path setup message itself. In this case, the path agents and
the intermediate policy gateways do not establish forwarding
associations for the path, but they do verify consistency of the
policy information contained in the path setup message, with their
own transit policies, before forwarding the setup message on to the
next policy gateway.
The path direction portion of the local path identifier has different
interpretations, depending upon message type. In an IDPR path setup
message, the path direction indicates the directions in which the
path should be enabled: the value 01 denotes originator to target,
the value 10 denotes target to originator, the value 11 denotes both
directions, and the value 00 denotes neither direction. Each policy
gateway along the path interprets the path direction in the setup
message and sets up the forwarding information as directed. In an
IDPR data message, the path direction indicates the current direction
of traffic flow: either 01 for originator to target or 10 for target
to originator. Thus, if for example, an originator sets up a path
enabling only the direction from target to originator, the target
sends data messages containing the path identifier selected by the
originator together with the path direction set equal to 10.
Instead of using path identifiers that are unique throughout an
internetwork, we could have used path identifiers that are unique
only between a pair of consecutive policy gateways and that change
from one policy gateway pair to the next. The advantage of locally
unique path identifiers is that they may be much shorter than
globally unique identifiers and hence consume less transmission
bandwidth. However, the disadvantage is that the path identifier
carried in each IDPR data message must be modified at each policy
gateway, and hence if the integrity/authentication information covers
the path identifier, it must be recomputed at each policy gateway.