messages; however, the IDPR architecture does not require source
authentication of data messages. Instead, we recommend that higher
level (end-to-end) protocols, not IDPR, assume the responsibility for
data message source authentication, because of the amount of
computation involved in verifying a digital signature.
3.3.4. Timestamps
Message timestamps promote the detection of out-of-date messages as
well as message replays. Each IDPR control message must carry a
timestamp supplied by the source, which serves to indicate the age of
the message. IDPR entities use the absolute value of a timestamp to
confirm that the message is current and use the relative difference
between timestamps to determine which message contains the most
recent information. Hence, all IDPR entities must possess internal
clocks that are synchronized to some degree, in order for the
absolute value of a message timestamp to be meaningful. The
synchronization granularity required by the IDPR architecture is on
the order of minutes and can be achieved manually.
Each IDPR entity that receives an IDPR control message must check
that the message is timely. Any IDPR control message whose timestamp
lies outside of the acceptable range may contain stale or corrupted
information or may have been issued by a source whose internal clock
has lost synchronization with the message recipient's internal clock.
IDPR data messages also carry timestamps; however, the IDPR
architecture does not require timestamp acceptability checks on IDPR
data messages. Instead, we recommend that IDPR entities only check
IDPR data message timestamps during problem diagnosis, for example,
when checking for suspected message replays.
3.4. An Example of IDPR Operation
We illustrate how IDPR works by stepping through an example. In this
example, we assume that all domains support IDPR and that all domain
egress points are policy gateways.
Suppose host Hx in domain AD X wants to communicate with host Hy in
domain AD Y. 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. 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 forwarding information.
Eventually, the message will arrive at a policy gateway in AD X, as
described previously in section 3.2.1.
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. The
forwarding information database will already contain entries for all
of the following:
- All intra-domain traffic flows. Intra-domain forwarding information
is integrated into the forwarding database as soon as it is received.
- Inter-domain traffic flows that do not require IDPR policy routes.
Non-IDPR inter-domain 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 traffic flow; we
suggest a radix search to locate a database entry. When the search
terminates, it either produces a forwarding information database
entry or a directive to generate such an entry for an IDPR traffic
flow. If the search terminates in an existing database entry, the
path agent forwards the message according to that entry.
Suppose that the search terminates indicating that the traffic flow
between Hx and Hy requires an IDPR route and that no forwarding
information database entry yet exists for this 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 source and destination domain information, the
path agent attempts to obtain a policy route to carry the traffic
from Hx to Hy. The path agent relies on the 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 consults its local cache before
contacting a route server. A policy route contained in the cache is
suitable provided that its associated source domain is AD X, its
associated destination domain is AD Y, and it satisfies the service
requirements specified in the data message or through source policy
configuration.
If no suitable cache entry exists, the path agent queries the route
server, providing it with the source and destination domains together
with the requested services. 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 domain AD Y, consistent with the
requested services for Hx.
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, the IDPR architecture 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, the IDPR architecture
does not specify how the path agent should use multiple routes. In
any case, a route server always returns a response to a path agent's
query, even if it is not successful in locating a suitable policy
route.
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 different host
traffic flow. The IDPR architecture permits multiple host traffic
flows to use the same path, provided that all flows sharing the path
travel between the same endpoint domains and have the same service
requirements. Nevertheless, the IDPR architecture 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 will be
included in each message that travels down the path and will be 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 forwarding information
database entry 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 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. Paths remain in place until they are torn down because of
failure, expiration, or when resources are scarce, preemption in
favor of other paths.
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, the IDPR architecture
does not preclude a path agent from forwarding data messages along a
path prior to confirmation of successful path establishment. In this
case, the source path agent transmits data messages along the path
with full knowledge that the path may not yet have been successfully
established at all intermediate policy gateways and thus that these
data messages will be immediately discarded by any policy gateway not
yet able to recognize the path identifier.
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 a new path
from AD Y to AD X.
4. Accommodating a Large, Heterogeneous Internet
The IDPR architecture must be able to accommodate an Internet
containing O(10,000) domains, supporting diverse source and transit
policies. Thus, we have endowed the IDPR architecture with many
features that allow it to function effectively in such an
environment.
4.1. Domain Level Routing
The IDPR architecture provides policy routing among administrative
domains. In order to construct policy routes, route servers require
routing information at the domain level only; no intra-domain details
need be included in IDPR routing information. The size of the
routing information database maintained by a route server depends not
on the number of Internet gateways, networks, and links, but on how
these gateways, networks, and links are grouped into domains and on
what services they offer. Therefore, the number of entries in an
IDPR routing information database depends on the number of domains
and the number and size of the transit policies supported by these
domains.
Policy gateways distribute IDPR routing information only when
detectable inter-domain changes occur and may also elect to
distribute routing information periodically (for example, on the
order of once per day) as a backup. We expect that a pair of policy
gateways within a domain will normally be connected such that when
the primary intra-domain route between them fails, the intra-domain
routing procedure will be able to construct an alternate route.
Thus, an intra-domain failure is unlikely to be visible at the
inter-domain level and hence unlikely to force an inter-domain
routing change. Therefore, we expect that policy gateways will not
often generate and distribute IDPR routing information messages.
IDPR entities rely on intra-domain routing procedures operating
within domains to transport inter-domain messages across domains.
Hence, IDPR messages must appear well-formed according to the intra-
domain routing and addressing procedures in each domain traversed.
Recall that source authentication information (refer to section 3.3.3
above) may cover the entire IDPR message. Thus, the IDPR portion of
such a message cannot be modified at intermediate domains along the
path without causing source authenticity checks to fail. Therefore,
at domain boundaries, IDPR messages require encapsulation and
decapsulation according to the routing procedures and addressing
schemes operating with the given domain. Only policy gateways and
route servers must be capable of handling IDPR-specific messages;
other gateways and hosts simply treat the encapsulated IDPR messages
like any other message. Thus, for the Internet to support IDPR, only
a small proportion of Internet entities require special IDPR
software.
With domain level routes, many different traffic flows may use not
only the same policy route but also the same path, as long as their
source domains, destination domains, and service requirements are
compatible. The size of the forwarding information database
maintained by a policy gateway depends not on the number of Internet
hosts but on how these hosts are grouped into domains, which hosts
intercommunicate, and on how much distinction a source domain wishes
to preserve among its traffic flows. Therefore, the number of
entries in an IDPR forwarding information database depends on the
number of domains and the number of source policies supported by
those domains. Moreover, memory associated with failed, expired, or
disused paths can be reclaimed for new paths, and thus forwarding
information for many paths can be accommodated in a policy gateway's
forwarding information database.
4.2. 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 monetary cost for the session 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 monetary cost for the session, 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 monetary cost for the session, 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,
it may not always be possible to achieve the desired route
generation behavior using such a linear combination of qualities of
service.
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 specified optimal requested service listed in the source
policy. The route server should resolve ties between otherwise
equivalent routes by evaluating these routes according to the other
optimal requested services, in the order in which they are
specified. With respect to the route server's routing information
database, the selected route is optimal according to the first
optimal requested service but is not necessarily optimal according
to any other optimal requested service.
- 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 those routes as described in the multi-criteria
optimization case above.
- 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.
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.
4.3. SuperDomains
A "super domain" is itself an administrative domain, comprising a set
of contiguous domains with similar transit policies and formed
through consensus of the administrators of the constituent domains.
Super domains provide a mechanism for reducing the amount of IDPR
routing information distributed throughout the Internet. Given a set
of n contiguous domains with consistent transit policies, the amount
of routing information associated with the set is approximately n
times smaller when the set is considered as a single super domain
than when it is considered as n individual domains.
When forming a super domain from constituent domains whose transit
policies do not form a consistent set, one must determine which
transit policies to distribute in the routing information for the
super domain. The range of possibilities is bounded by the following
two alternatives, each of which reduces the amount of routing
information associated with the set of constituent domains:
- The transit policies supported by the super domain are derived from
the union of the access restrictions and the intersection of the
qualities of service, over all constituent domains. In this case,
the formation of the super domain reduces the number of services
offered by the constituent domains, but guarantees that none of
these domains' access restrictions are violated.
- The transit policies supported by the super domain are derived from
the intersection of the access restrictions and the union of the
qualities of service. In this case, the formation of the super
domain increases the number of services offered by the constituent
domains, but forces relaxation of these domains' access
restrictions.
Thus, we recommend that domain administrators refrain from
arbitrarily grouping domains into super domains, unless they fully
understand the consequences.
The existence of super domains imposes a hierarchy on domains within
the Internet. For model consistency, we assume that there is a
single super domain at the top of the hierarchy, which contains the
set of all high-level domains. A domain's identity is defined
relative to the domain hierarchy. Specifically, a domain's identity
may be defined in terms of the domains containing it, the domains it
contains, or both.
For any domain AD X, the universe of distribution for its routing
information usually extends only to those domains contained in AD X's
immediate super domain and at the same level of the hierarchy as AD
X. However, the IDPR architecture does not preclude AD X from
distributing its routing information to domains at arbitrarily high
levels in the hierarchy, as long as the immediate super domain of
these domains is also a super domain of AD X. For example, the
administrator of an individual domain within a super domain may wish
to have one of its transit policies advertised outside of the
immediate super domain, so that other domains can take advantage of a
quality of service not offered by the super domain itself. In this
case, the super domain and the consituent domain may distribute
routing information at the same level in the domain hierarchy, even
though one domain actually contains the other.
We note that the existence of super domains may restrict the number
of routes available to source domains with access restrictions. For
example, suppose that a source domain AD X has source policies that
preclude its traffic from traversing a domain AD Y and that AD Y is
contained in a super domain AD Z. If domains within AD Z do not
advertise routing information separately, then route servers within
AD X do not have enough routing information to construct routes that
traverse AD Z but that avoid AD Y. Hence, route servers in AD X must
generate routes that avoid AD Z altogether.
4.4. Domain Communities
A "domain community" is a group of domains to which a given domain
distributes routing information, and hence domain communities may be
used to limit routing information distribution. Domain communities
not only reduce the costs associated with distributing and storing
routing information but also allow concealment of routing information
from domains outside of the community. Unlike a super domain, a
domain community is not necessarily an administrative domain.
However, formation of a domain community may or may not involve the
consent of the administrators of the member domains, and the
definition of the community may be implicit or explicit.
Each domain administrator determines the extent of distribution of
its domain's routing information and hence unilaterally defines a
domain community. By default, this community encompasses all
Internet domains. However, the domain administrator may restrict
community membership by describing the community as a neighborhood
(defined, for example, in terms of domain hops) or as a list of
member domains.
A group of domain administrators may mutually agree on distribution
of their domains' routing information among their domains and hence
multilaterally define a domain community. By default, this community
encompasses all Internet domains. However, the domain administrators
may restrict community membership by describing the community as a
list of member domains. In fact, this domain community may serve as
a multicast group for routing information distribution.
4.5. Robustness in the Presence of Failures
The IDPR architecture possesses the following features that make it
resistent to failures in the Internet:
- Multiple connections between adjacent policy gateways in a virtual
gateway and between peer and neighbor policy gateways across an
administrative domain minimize the number of single component
failures that are visible at the inter-domain level.
- Policy gateways distribute IDPR routing information immediately
after detecting a connectivity failure at the inter-domain level,
and route servers immediately incorporate this information into
their routing information databases. This ensures that new policy
routes will not include those domains involved in the connectivity
failure.
- The routing information database query/response mechanism ensures
rapid updating of the routing information database for a previously
failed route server following the route server's reconnection to the
Internet.
- To minimize user service disruption following a
failure in the primary path, policy gateways attempt local path
repair immediately after detecting a connectivity failure.
Moreover, path agents may maintain standby alternate paths that can
become the primary path if necessary.
- Policy gateways within a domain continuously monitor domain
connectivity and hence can detect and identify domain partitions.
Moreover, IDPR can continue to operate properly in the presence of
partitioned domains.
4.5.1. Path Repair
Failure of one or more entities on a given policy route may render
the route unusable. If the failure is within a domain, IDPR relies
on the intra-domain routing procedure to find an alternate route
across the domain, which leaves the path unaffected. If the failure
is in a virtual gateway, policy gateways must bear the responsibility
of repairing the path. Policy gateways nearest to the failure are
the first to recognize its existence and hence can react most quickly
to repair the path.
Relinquishing control over path repair to policy gateways in other
domains may be unacceptable to some domain administrators. The
reason is that these policy gateways cannot guarantee construction of
a path that satisfies the source policies of the source domain, as
they have no knowledge of other domains' source policies.
Nevertheless, limited local path repair is feasible, without
distributing either source policy information throughout the Internet
or detailed path information among policy gateways in a domain or in
a virtual gateway. We say that a path is "locally repairable" if
there exists an alternate route between two policy gateways,
separated by at most one policy gateway, on the path. This
definition covers path repair in the presence of failed routes
between consecutive policy gateways as well as failed policy gateways
themselves.
A policy gateway attempts local path repair, proceeding in the
forward direction of the path, upon detecting that the next policy
gateway on a path is no longer reachable. The policy gateway must
retain enough of the original path setup information to repair the
path locally. Using the path setup information, the policy gateway
attempts to locate a route around the unreachable policy gateway.
Specifically, the policy gateway attempts to establish contact with
either:
- A peer of the unreachable policy gateway. In this case, the
contacted policy gateway attempts to locate the next policy gateway
following the unreachable policy gateway, on the original path.
- A peer of itself, if the unreachable policy gateway is an adjacent
policy gateway and if the given policy gateway no longer has direct
connections to any adjacent policy gateways. In this case, the
contacted policy gateway attempts to locate a peer of the
unreachable policy gateway, which in turn attempts to locate the
next policy gateway following the unreachable policy gateway, on the
original path.
If it successfully reaches the next policy gateway, the contacted
policy gateway informs the requesting policy gateway. In this case,
the requesting, contacted, and next policy gateways update their
forwarding information databases to conform to the new part of the
path. If it does not successfully reach the next policy gateway, the
contacted policy gateway initiates teardown of the original path; in
this case, the source path agent is responsible for finding a new
route to the destination.
4.5.2. Partitions
A "domain partition" exists whenever there are at least two entities
within the domain that can no longer communicate over any intra-
domain route. Domain partitions not only disrupt intra-domain
communication but also may interfere with inter-domain communication,
particularly when the partitioned domain is a transit domain.
Therefore, we have designed the IDPR architecture to permit effective
use of partitioned domains and hence maximize Internet connectivity
in the presence of domain partitions.
When a domain is partitioned, it becomes a set of multiple distinct
"components". A domain component is a subset of the domain's
entities such that all entities within the subset are mutually
reachable via intra-domain routes, but no entities in the complement
of the subset are reachable via intra-domain routes from entities
within the subset. Each domain component has a unique identifier,
namely the identifier of the domain together with the ordinal number
of the lowest-numbered operational policy gateway within the domain
component. No negotiation among policy gateways is necessary to
determine the domain component's lowest-numbered operational policy
gateway. Instead, within each domain component, all policy gateway
members discover mutual reachability through intra-domain
reachability information. Therefore, all members have a consistent
view of which is the lowest-numbered operational policy gateway in
the component.
IDPR entities can detect and compensate for all domain partitions
that isolate at least two groups of policy gateways from each other.
They cannot, however, detect any domain partition that isolates
groups of hosts only. Note that a domain partition may segregate
portions of a virtual gateway, such that peer policy gateways lie in
separate domain components. Although itself partitioned, the virtual
gateway does not assume any additional identities. However, from the
perspective of the adjacent domain, the virtual gateway now connects
to two separate domain components.
Policy gateways use partition information to select routes across
virtual gateways to the correct domain components. They also
distribute partition information to route servers as part of the IDPR
routing information. Thus, route servers know which domains are
partitioned. However, route servers do not know which hosts reside
in which components of a partitioned domain; tracking this
information would require extensive computation and communication.
Instead, when a route server discovers that the destination of a
requested route is a partitioned domain, it attempts to generate a
suitable policy route to each component of the destination domain.
Generation of multiple routes, on detection of a partitioned
destination domain, maximizes the chances of obtaining at least one
policy route that can be used for communication between the source
and destination hosts.
5. References
[1] Rekhter, Y., "EGP and Policy Based Routing in the New NSFNET
Backbone", RFC1092, February 1989.
[2] Clark, D., "Policy Routing in Internet Protocols", RFC1102, May
1989.
[3] Braun, H-W., "Models of Policy Based Routing", RFC1104, June
1989.
[4] Leiner, B., "Policy Issues in Interconnecting Networks", RFC
1124, September 1989.
[5] Estrin, D., "Requirements for Policy Based Routing in the
Research Internet", RFC1125, November 1989.
[6] Little, M., "Goals and Functional Requirements for Inter-
Autonomous System Routing", RFC1126, July 1989.
[7] Honig, J., Katz, D., Mathis, M., Rekhter, Y., and Yu, J.,
"Application of the Border Gateway Protocol in the Internet",
RFC1164, June 1990.
[8] Lougheed, K. and Rekhter, Y., "A Border Gateway Protocol 3
(BGP-3)", RFC1267, October 1991.
[9] Rekhter, Y. and Li, T. Editors, "A Border Gateway Protocol 4
(BGP-4)", Work in Progress, September 1992.
[10] ISO, "Information Processing Systems - Telecommunications and
Information Exchange between Systems - Protocol for Exchange of
Inter-domain Routeing Information among Intermediate Systems to
Support Forwarding of ISO 8473 PDUs", ISO/IEC DIS 10747, August
1992.
[11] Perlman, R., "Network Layer Protocols with Byzantine Robust-
ness", Ph.D. Thesis, Department of Electrical Engineering and
Computer Science, MIT, August 1988.
[12] Estrin, D. and Tsudik, G., "Secure Control of Transit Internet-
work Traffic", TR-89-15, Computer Science Department, University
of Southern California.
[13] Garcia-Luna-Aceves, J.J., "A Unified Approach for Loop-Free
Routing using Link States or Distance Vectors", ACM Computer
Communication Review, Vol. 19, No. 4, SIGCOMM 1989, pp. 212-223.
[14] Zaumen, W.T. and Garcia-Luna-Aceves, J.J., "Dynamics of Distri-
buted Shortest-Path Routing Algorithms", ACM Computer Communica-
tion Review, Vol. 21, No. 4, SIGCOMM 1991, pp. 31-42.
6. Security Considerations
Refer to section 3.3 for details on security in IDPR.
7. Author's Address
Martha Steenstrup
BBN Systems and Technologies
10 Moulton Street
Cambridge, MA 02138
Phone: (617) 873-3192
Email: msteenst@bbn.com