RFC1478 - An Architecture for Inter-Domain Policy Routing

Network Working Group M. Steenstrup
Request for Comments: 1478 BBN Systems and Technologies
June 1993
An Architecture for Inter-Domain Policy Routing
Status of this Memo
This RFCspecifies an IAB standards track protocol for the Internet
community, and requests discussion and suggestions for improvements.
Please refer to the current edition of the "IAB Official Protocol
Standards" for the standardization state and status of this protocol.
Distribution of this memo is unlimited.
Abstract
We present an architecture for inter-domain policy routing (IDPR).
The objective of IDPR is to constrUCt and maintain routes, between
source and destination administrative domains, that provide user
traffic with the requested services within the constraints stipulated
for the domains transited. The IDPR architecture is designed to
accommodate an internetwork containing tens of thousands of
administrative domains with heterogeneous service requirements and
restrictions.
Contributors
The following people have contributed to the IDPR architecture: Bob
Braden, Lee Breslau, Ross Callon, Noel Chiappa, Dave Clark, Pat
Clark, Deborah Estrin, Marianne Lepp, Mike Little, Martha Steenstrup,
Zaw-Sing Su, Paul Tsuchiya, and Gene Tsudik. Yakov Rekhter supplied
many useful comments on a previous draft of this document.
Table of Contents
1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. The Internet Environment. . . . . . . . . . . . . . . . . . . 4
2. Approaches to Policy Routing. . . . . . . . . . . . . . . . . . 5
2.1. Policy Route Generation . . . . . . . . . . . . . . . . . . . 5
2.1.1. Distance Vector Approach. . . . . . . . . . . . . . . . . . 5
2.1.2. Link State Approach . . . . . . . . . . . . . . . . . . . . 7
2.2. Routing Information Distribution. . . . . . . . . . . . . . . 8
2.2.1. Distance Vector Approach. . . . . . . . . . . . . . . . . . 8
2.2.2. Link State Approach . . . . . . . . . . . . . . . . . . . .10
2.3. Message Forwarding along Policy Routes. . . . . . . . . . . .10
2.3.1. Hop-by-Hop Approach . . . . . . . . . . . . . . . . . . . .11
2.3.1.1. A Clarification . . . . . . . . . . . . . . . . . . . . .11
2.3.2. Source Specified Approach . . . . . . . . . . . . . . . . .12
3. The IDPR Architecture . . . . . . . . . . . . . . . . . . . . .13
3.1. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . .13
3.2. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . .13
3.2.1. Path Agents . . . . . . . . . . . . . . . . . . . . . . . .16
3.2.2. IDPR Servers. . . . . . . . . . . . . . . . . . . . . . . .17
3.2.3. Entity Identifiers. . . . . . . . . . . . . . . . . . . . .19
3.3. Security and Reliability. . . . . . . . . . . . . . . . . . .20
3.3.1. Retransmissions and Acknowledgements. . . . . . . . . . . .20
3.3.2. Integrity Checks. . . . . . . . . . . . . . . . . . . . . .21
3.3.3. Source Authentication . . . . . . . . . . . . . . . . . . .21
3.3.4. Timestamps. . . . . . . . . . . . . . . . . . . . . . . . .21
3.4. An Example of IDPR Operation. . . . . . . . . . . . . . . . .22
4. Accommodating a Large, Heterogeneous Internet . . . . . . . . .25
4.1. Domain Level Routing. . . . . . . . . . . . . . . . . . . . .25
4.2. Route Generation. . . . . . . . . . . . . . . . . . . . . . .27
4.3. Super Domains . . . . . . . . . . . . . . . . . . . . . . . .29
4.4. Domain Communities. . . . . . . . . . . . . . . . . . . . . .30
4.5. Robustness in the Presence of Failures. . . . . . . . . . . .31
4.5.1. Path Repair . . . . . . . . . . . . . . . . . . . . . . . .31
4.5.2. Partitions. . . . . . . . . . . . . . . . . . . . . . . . .33
5. References. . . . . . . . . . . . . . . . . . . . . . . . . . .XX
5. Security Considerations . . . . . . . . . . . . . . . . . . . .34
6. Author"s Address . . . . . . . . . . . . . . . . . . . . . . .34
1. Introduction
As data communications technologies evolve and user populations grow,
the demand for internetworking increases. Internetworks usually
proliferate through interconnection of autonomous, heterogeneous
networks administered by separate authorities. We use the term
"administrative domain" (AD) to refer to any collection of contiguous
networks, gateways, links, and hosts governed by a single
administrative authority who selects the intra-domain routing
procedures and addressing schemes, specifies service restrictions for
transit traffic, and defines service requirements for locally-
generated traffic.
Interconnection of administrative domains can broaden the range of
services available in an internetwork. Hence, traffic with special
service requirements is more likely to receive the service requested.
However, administrators of domains offering special transit services
are more likely to establish stringent Access restrictions, in order
to maintain control over the use of their domains" resources.
An internetwork composed of many domains with diverse service
requirements and restrictions requires "policy routing" to transport
traffic between source and destination. Policy routing constitutes
route generation and message forwarding procedures for producing and
using routes that simultaneously satisfy user service requirements
and respect transit domain service restrictions.
With policy routing, each domain administrator sets "transit
policies" that dictate how and by whom the resources within its
domain should be used. Transit policies are usually public, and they
specify offered services comprising:
- Access restrictions: e.g., applied to traffic to or from certain
domains or classes of users.
- Quality: e.g., delay, throughput, or error characteristics.
- Monetary cost: e.g., charge per byte, message, or unit time.
Each domain administrator also sets "source policies" for traffic
originating within its domain. Source policies are usually private,
and they specify requested services comprising:
- Access restrictions: e.g., domains to favor or avoid in routes.
- Quality: e.g., acceptable delay, throughput, or reliability.
- Monetary cost: e.g., acceptable session cost.
In this document, we describe an architecture for inter-domain policy
routing (IDPR), and we provide a set of functions which can form the
basis for a suite of IDPR protocols and procedures.
1.1. The Internet Environment
The Internet currently comprises over 7000 operational networks and
over 10,000 registered networks. In fact, for the last several
years, the number of constituent networks has approximately doubled
annually. Although we do not eXPect the Internet to sustain this
growth rate, we must provide an architecture for IDPR that can
accommodate the Internet five to ten years in the future. According
to the functional requirements for inter-autonomous system (i.e.,
inter-domain) routing set forth in [6], the IDPR architecture and
protocols must be able to handle O(100,000) networks distributed over
O(10,000) domains.
Internet connectivity has increased along with the number of
component networks. In the early 1980s, the Internet was purely
hierarchical, with the ARPANET as the single backbone. The current
Internet possesses a semblance of a hierarchy in the collection of
backbone, regional, metropolitan, and campus domains that compose it.
However, technological, economical, and political incentives have
prompted the introduction of inter-domain links outside of those in
the strict hierarchy. Hence, the Internet has the properties of both
hierarchical and mesh connectivity.
We expect that the Internet will evolve in the following way. Over
the next five years, the Internet will grow to contain O(10) backbone
domains, most providing connectivity between many source and
destination domains and offering a wide range of qualities of
service, for a fee. Most domains will connect directly or indirectly
to at least one Internet backbone domain, in order to communicate
with other domains. In addition, some domains may install direct
links to their most favored destinations. Domains at the lower
levels of the hierarchy will provide some transit service, limited to
traffic between selected sources and destinations. However, the
majority of Internet domains will be "stubs", that is, domains that
do not provide any transit service for other domains.
The bulk of Internet traffic will be generated by hosts in these stub
domains, and thus, the applications running in these hosts will
determine the traffic service requirements. We expect application
diversity encompassing electronic mail, desktop videoconferencing,
scientific visualization, and distributed simulation, to list a few.
Many of these applications have strict requirements on loss, delay,
and throughput.
Ensuring that Internet traffic traverses routes that provide the
required services without violating domain usage restrictions will be
the task of policy routing in the Internet in the next several years.
Refer to [1]-[10] for more information on the role of policy routing
in the Internet.
2. Approaches to Policy Routing
In this section, we provide an assessment of candidate approaches to
policy routing, concentrating on the "distance vector" and "link
state" alternatives for routing information distribution and route
generation and on the "hop-by-hop" and "source specified"
alternatives for data message forwarding. The IDPR architecture
supports link state routing information distribution and route
generation in conjunction with source specified message forwarding.
We justify these choices for IDPR below.
2.1. Policy Route Generation
We present policy route generation from the distance vector
perspective and from the link state perspective.
2.1.1. Distance Vector Approach
Distance vector route generation distributes the computation of a
single route among multiple routing entities along the route. Hence,
distance vector route generation is potentially susceptible to the
problems of routing loop formation and slow adaptation to changes in
an internetwork. However, there exist several techniques that can be
applied during distance vector route generation to reduce the
severity of, or even eliminate, these problems. For information on a
loop-free, quickly adapting distance vector routing procedure,
consult [13] and [14].
During policy route generation, each recipient of a distance vector
message assesses the acceptability of the associated route and
determines the set of neighboring domains to which the message should
be propagated. In the context of policy routing, both of the
following conditions are necessary for route acceptability:
- The route is consistent with at least one transit policy for each
domain, not including the current routing entity"s domain, contained
in the route. To enable each recipient of a distance vector message
to verify consistency of the associated route with the transit
policies of all constituent domains, each routing entity should
include its domain"s identity and transit policies in each
acceptable distance vector message it propagates.
- The route is consistent with at least one source policy for at least
one domain in the Internet. To enable each recipient of a distance
vector message to verify consistency of the associated route with
the source policies of particular domains, each domain must provide
other domains with access to its source policies.
In addition, at least one of the following conditions is necessary
for route acceptability:
- The route is consistent with at least one of the transit policies
for the current routing entity"s domain. In this case, the routing
entity accepts the distance vector message and then proceeds to
compare the associated route with its other routes to the
destinations listed in the message. If the routing entity decides
that the new route is preferable, it updates the distance vector
message with its domain"s identity and transit policies and then
propagates the message to the appropriate neighboring domains. We
discuss distance vector message distribution in more detail in
section 2.2.1.
The route is consistent with at least one of the source policies for
the current routing entity"s domain. In this case, the routing
entity need not propagate the distance vector message but does retain
the associated route for use by traffic from local hosts, bound for
the destinations listed in the message.
The routing entity discards any distance vector message that does not
meet these necessary conditions.
With distance vector policy route generation, a routing entity may
select and store multiple routes of different characteristics, such
as qualities of service, to a single destination. A routing entity
uses the quality of service information, provided in the transit
policies contained in accepted distance vector messages, to
discriminate between routes based on quality of service. Moreover, a
routing entity may select routes that are specific to certain source
domains, provided that the routing entity has access to the source
policies of those domains.
In the distance vector context, the flexibility of policy route
generation afforded by accounting for other domains" transit and
source policies in route selection has the following disadvantages:
- Each recipient of a distance vector message must bear the cost of
verifying the consistency of the associated route with the
constituent domains" transit policies.
- Source policies must be made public. Thus, a domain must divulge
potentially private information.
- Each recipient of a distance vector message must bear the
potentially high costs of selecting routes for arbitrary source
domains. In particular, a routing entity must store the source
policies of other domains, account for these source policies during
route selection, and maintain source-specific forwarding
information. Moreover, there must be a mechanism for distributing
source policy information among domains. Depending on the mechanism
selected, distribution of source policies may add to the costs paid
by each routing entity in supporting source-specific routing.
We note, however, that failure to distribute source policies to all
domains may have unfortunate consequences. In the worst case, a
domain may not learn of any acceptable routes to a given destination,
even though acceptable routes do exist. For example, suppose that AD
V is connected to AD W and that AD W can reach AD Z through either AD
X or AD Y. Suppose also that AD~W, as a recipient of distance vector
messages originating in AD Z, prefers the route through AD Y to the
route through AD X. Furthermore, suppose that AD W has no knowledge
of AD V"s source policy precluding traffic from traversing AD Y.
Hence, AD W distributes to AD V the distance vector message
containing the route WYZ but not the distance vector message
containing the route WXZ. AD V is thus left with no known route to
AD Z, although a viable route traversing AD W and AD X does exist.
2.1.2. Link State Approach
Link state route generation permits concentration of the computation
of a single route within a single routing entity at the source of the
route. In the policy routing context, entities within a domain
generate link state messages containing information about the
originating domain, including the set of transit policies that apply
and the connectivity to adjacent domains, and they distribute these
messages to neighboring domains. Each recipient of a link state
message stores the routing information for anticipated policy route
generation and also distributes it to neighboring domains. Based on
the set of link state messages collected from other domains and on
its domain"s source and transit policies, a routing entity constructs
and selects policy routes from its domain to other domains in the
Internet.
We have selected link state policy route generation for IDPR for the
following reasons:
- Each domain has complete control over policy route generation from
the perspective of itself as source.
- The cost of computing a route is completely contained within the
source domain. Hence, routing entities in other domains need not
bear the cost of generating policy routes that their domains" local
hosts may never use.
- Source policies may be kept private and hence need not be
distributed. Thus, there are no memory, processing, or transmission
bandwidth costs incurred for distributing and storing source
policies.
2.2. Routing Information Distribution
A domain"s routing information and the set of domains to which that
routing information is distributed each influence the set of generable
policy routes that include the given domain. In particular, a domain
administrator may promote the generation of routes that obey its
domain"s transit policies by ensuring that its domain"s routing
information:
- Includes resource access restrictions.
- Is distributed only to those domains that are permitted to use these
resources.
Both of these mechanisms, distributing restrictions with and
restricting distribution of a domain"s routing information, can be
applied in both the distance vector and link state contexts.
2.2.1. Distance Vector Approach
A routing entity may distribute its domain"s resource access
restrictions by including the appropriate transit policy information
in each distance vector it accepts and propagates. Also, the routing
entity may restrict distribution of an accepted distance vector
message by limiting the set of neighboring domains to which it
propagates the message. In fact, restricting distribution of routing
information is inherent in the distance vector approach, as a routing
entity propagates only the preferred routes among all the distance
vector messages that it accepts.
Although restricting distribution of distance vector messages is
easy, coordinating restricted distribution among domains requires
each domain to know other domains" distribution restrictions. Each
domain may have a set of distribution restrictions that apply to all
distance vector messages generated by that domain as well as sets of
distribution restrictions that apply to distance vector messages
generated by other domains.
As a distance vector message propagates among domains, each routing
entity should exercise the distribution restrictions associated with
each domain constituting the route thus far constructed. In
particular, a routing entity should send an accepted distance vector
message to a given neighbor, only if distribution of that message to
that neighbor is not precluded by any domain contained in the route.
To enable a routing entity to exercise these distribution
restrictions, each domain must permit other domains access to its
routing information distribution restrictions. However, we expect
that domains may prefer to keep distribution restrictions, like
source policies, private. There are at least two ways to make a
domain"s routing information distribution restrictions generally
available to other domains:
- Prior to propagation of an accepted distance vector message, a
routing entity includes in the message its domain"s distribution
restrictions (all or only those to that apply to the given message).
This method requires no additional protocol for disseminating the
distribution restrictions, but it may significantly increase the
size of each distance vector message.
- Each domain independently disseminates its distribution restrictions
to all other domains, so that each domain will be able to exercise
all other domains" distribution restrictions. This method requires
an additional protocol for disseminating the distribution
restrictions, and it may require a significant amount of memory at
each routing entity for storing all domains" distribution
restrictions.
We note that a domain administrator may describe the optimal
distribution pattern of distance vector messages originating in its
domain, as a directed graph rooted at its domain. Furthermore, if
all domains in the directed graph honor the directionality and if the
graph is also acyclic, no routing loops may form, because no two
domains are able to exchange distance vector messages pertaining to
the same destination. However, an acyclic graph also means that some
domains may be unable to discover alternate paths when connectivity
between adjacent domains fails, as we show below.
We reconsider the example from section 2.1.1. Suppose that the
distance vector distribution graph for AD Z is such that all distance
vectors originating in AD Z flow toward AD V. In particular,
distance vectors from AD Z enter AD W from AD X and AD Y and leave AD
W for AD V. Now, suppose that the link between the AD Z and AD X
breaks. AD X no longer has knowledge of any viable route to AD Z,
although such a route exists through AD W. To ensure discovery of
alternate routes to AD Z during connectivity failures, the distance
vector distribution graph for AD Z must contain bidirectional links
between AD W and AD X and between AD W and AD Y.
2.2.2. Link State Approach
With link state routing information distribution, all recipients of a
domain"s link state message gain knowledge of that domain"s transit
policies and hence service restrictions. For reasons of efficiency
or privacy, a domain may also restrict the set of domains to which
its link state messages should be distributed. Thus, a domain has
complete control over distributing restrictions with and restricting
distribution of its routing information.
A domain"s link state messages automatically travel to all other
domains if no distribution restrictions are imposed. Moreover, to
ensure that distribution restrictions, when imposed, are applied, the
domain may use source specified forwarding of its link state
messages, such that the messages are distributed and interpreted only
by the destination domains for which they were intended. Thus, only
those domains receive the given domain"s link state messages and
hence gain knowledge of that domain"s service offerings.
We have selected link state routing information distribution for IDPR
for the following reasons:
- A domain has complete control over the distribution of its own
routing information.
- Routing information distribution restrictions may be kept private
and hence need not be distributed. Thus, there are no memory,
processing, or transmission bandwidth costs incurred for
distributing and storing distribution restrictions.
2.3. Message Forwarding along Policy Routes
To transport data messages along a selected policy route, a routing
entity may use either hop-by-hop or source specified message
forwarding.
2.3.1. Hop-by-Hop Approach
With hop-by-hop message forwarding, each routing entity makes an
independent forwarding decision based on a message"s source,
destination, and requested services and on information contained in
the entity"s forwarding information database. Hop-by-hop message
forwarding follows a source-selected policy route only if all routing
entities along the route have consistent routing information and make
consistent use of this information when generating and selecting
policy routes and when establishing forwarding information. In
particular, all domains along the route must have consistent
information about the source domain"s source policies and consistent,
but not necessarily complete, information about transit policies and
domain adjacencies within the Internet. In general, this implies
that each domain should have knowledge of all other domains" source
policies, transit policies, and domain adjacencies.
When hop-by-hop message forwarding is applied in the presence of
inconsistent routing information, the actual route traversed by data
messages not only may differ from the route selected by the source
but also may contain loops. In the policy routing context, private
source policies and restricted distribution of routing information
are two potential causes of routing information inconsistencies among
domains. Moreover, we expect routing information inconsistencies
among domains in a large Internet, independent of whether the
Internet supports policy routing, as some domains may not want or may
not be able to store routing information from the entire Internet.
2.3.1.1. A Clarification
In a previous draft, we presented the following example which results
in persistent routing loops, when hop-by-hop message forwarding is
used in conjunction with distance vector routing information
distribution and route selection. Consider the sequence of events:
- AD X receives a distance vector message containing a route to AD Z,
which does not include AD Y. AD X selects and distributes this route
as its primary route to AD Z.
- AD Y receives a distance vector message containing a route to AD Z,
which does not include AD X. AD Y selects and distributes this route
as its primary route to AD Z.
- AD X eventually receives the distance vector message containing the
route to AD Z, which includes AD Y but not AD X. AD X prefers this
route over its previous route to AD Z and selects this new route as
its primary route to AD Z.
- AD Y eventually receives the distance vector message containing the
route to AD Z, which includes AD X but not AD Y. AD Y prefers this
route over its previous route to AD Z and selects this new route as
its primary route to AD Z.
Thus, AD X selects a route to AD Z that includes AD Y, and AD Y
selects a route to AD Z that includes AD X.
Suppose that all domains along the route selected by AD X, except for
AD Y, make forwarding decisions consistent with AD X"s route, and
that all domains along the route selected by AD Y, except for AD X,
make forwarding decisions consistent with AD Y"s route. Neither AD
X"s selected route nor AD Y"s selected route contains a loop.
Nevertheless, data messages destined for AD Z and forwarded to either
AD X or AD Y will continue to circulate between AD X and AD Y, until
there is a route change. The reason is that AD X and AD Y have
conflicting notions of the route to AD Z, with each domain existing
as a hop on the other"s route.
We note that while BGP-3 [8] is susceptible to such routing loops,
BGP-4 [9] is not. We thank Tony Li and Yakov Rekhter for their help
in clarifying this difference between BGP-3 and BGP-4.
2.3.2. Source Specified Approach
With source specified message forwarding, the source domain dictates
the data message forwarding decisions to the routing entities in each
intermediate domain, which then forward data messages according to
the source specification. Thus, the source domain ensures that any
data message originating within it follows its selected routes.
For source specified message forwarding, each data message must carry
either an entire source specified route or a path identifier.
Including the complete route in each data message incurs a per
message transmission and processing cost for transporting and
interpreting the source route. Using path identifiers does not incur
these costs. However, to use path identifiers, the source domain
must initiate, prior to data message forwarding, a path setup
procedure that forms an association between the path identifier and
the next hop in the routing entities in each domain along the path.
Thus, path setup may impose an initial delay before data message
forwarding can begin.
We have selected source specified message forwarding for IDPR data
messages for the following reasons:
- Source specified message forwarding respects the source policies of
the source domain, regardless of whether intermediate domains along
the route have knowledge of these source policies.
- Source specified message forwarding is loop-free, regardless of
whether the all domains along the route maintain consistent routing
information.
Also, we have chosen path identifiers over complete routes, to affect
source specified message forwarding, because of the reduced
transmission and processing cost per data message.
3. The IDPR Architecture
We now present the architecture for IDPR, including a description of
the IDPR functions, the entities that perform these functions, and
the features of IDPR that aid in accommodating Internet growth.
3.1. IDPR Functions
Inter-domain policy routing comprises the following functions:
- Collecting and distributing routing information including domain
transit policies and inter-domain connectivity.
- Generating and selecting policy routes based on the routing
information distributed and on the source policies configured or
requested.
- Setting up paths across the Internet using the policy routes
generated.
- Forwarding messages across and between domains along the established
paths.
- Maintaining databases of routing information, inter-domain policy
routes, forwarding information, and configuration information.
3.2. IDPR Entities
From the perspective of IDPR, the Internet comprises administrative
domains connected by "virtual gateways" (see below), which are in
turn connected by intra-domain routes supporting the transit policies
configured by the domain administrators. Each domain administrator
defines the set of transit policies that apply across its domain and
the virtual gateways between which each transit policy applies.
Several different transit policies may be configured for the intra-
domain routes connecting a pair of virtual gateways. Moreover, a
transit policy between two virtual gateways may be directional. That
is, the transit policy may apply to traffic flowing in one direction,
between the virtual gateways, but not in the other direction.
Virtual gateways (VGs) are the only connecting points recognized by
IDPR between adjacent administrative domains. Each virtual gateway
is actually a collection of directly-connected "policy gateways" (see
below) in two adjacent domains, whose existence has been sanctioned
by the administrators of both domains. Domain administrators may
agree to establish more than one virtual gateway between their
domains. For example, if two domains are to be connected at two
geographically distant locations, the domain administrators may wish
to preserve these connecting points as distinct at the inter-domain
level, by establishing two distinct virtual gateways.
Policy gateways (PGs) are the physical gateways within a virtual
gateway. Each policy gateway forwards transit traffic according to
the service restrictions stipulated by its domain"s transit policies
applicable to its virtual gateway. A single policy gateway may
belong to multiple virtual gateways. Within a domain, two policy
gateways are "neighbors" if they are in different virtual gateways.
Within a virtual gateway, two policy gateways are "peers" if they are
in the same domain and are "adjacent" if they are in different
domains. Peer policy gateways must be able to communicate over
intra-domain routes that support the transit policies that apply to
their virtual gateways. Adjacent policy gateways are "directly
connected" if they are the only Internet addressable entities
attached to the connecting medium. Note that this definition implies
that not only point-to-point links but also multiaccess networks may
serve as direct connections between adjacent policy gateways.
Combining multiple policy gateways into a single virtual gateway
affords three advantages:
- A reduction in the amount of IDPR routing information that must be
distributed and maintained throughout the Internet.
- An increase in the reliability of IDPR routes through redundancy of
physical connections between domains.
- An opportunity for load sharing of IDPR traffic among policy
gateways.
Several different entities are responsible for performing the IDPR
functions:
- Policy gateways collect and distribute routing information,
participate in path setup, forward data messages along established
paths, and maintain forwarding information databases.
- "Path agents" act on behalf of hosts to select policy routes, to set
up and manage paths, and to maintain forwarding information
databases.
- Special-purpose servers maintain all other IDPR databases as
follows:
o Each "route server" is responsible for both its database of
routing information, including domain connectivity and transit
policy information, and its database of policy routes. Also,
each route server generates policy routes on behalf of its
domain, using entries from its routing information database
and source policy information supplied through configuration
or oBTained directly from the path agents.
o Each "mapping server" is responsible for its database of
mappings that resolve Internet names and addresses to
administrative domains.
o Each "configuration server" is responsible for its database of
configured information that applies to policy gateways, path
agents, and route servers in the given administrative domain.
The configuration information for a given domain includes
source and transit policies and mappings between local IDPR
entities and their Internet addresses.
To maximize IDPR"s manageability, one should embed all of IDPR"s
required functionality within the IDPR protocols and procedures.
However, to minimize duplication of implementation effort, one should
take advantage of required functionality already provided by
mechanisms external to IDPR. Two such cases are the mapping server
functionality and the configuration server functionality. The
functions of the mapping server can be integrated into an existing
name service such as the DNS, and the functions of the configuration
server can be integrated into the domain"s existing network
management system.
Within the Internet, only policy gateways, path agents, and route
servers must be able to generate, recognize, and process IDPR
messages. The existence of IDPR is invisible to all other gateways
and hosts. Mapping servers and configuration servers perform
necessary but ancillary functions for IDPR, and they are not required
to execute the IDPR protocols.
3.2.1. Path Agents
Any Internet host can reap the benefits of IDPR, as long as there
exists a path agent configured to act on its behalf and a means by
which the host"s messages can reach that path agent. Path agents
select and set up policy routes for hosts, accounting for service
requirements. To obtain a host"s service requirements, a path agent
may either consult its configured IDPR source policy information or
extract service requirements directly from the host"s data messages,
provided such information is available in these data messages.
Separating the path agent functions from the hosts means that host
software need not be modified to support IDPR. Moreover, it means
that a path agent can aggregate onto a single policy route traffic
from several different hosts, as long as the source domains,
destination domains, and service requirements are the same for all of
these host traffic flows. Policy gateways are the natural choice for
the entities that perform the path agent functions on behalf of
hosts, as policy gateways are the only inter-domain connecting points
recognized by IDPR.
Each domain administrator determines the set of hosts that its
domain"s path agents will handle. We expect that a domain
administrator will normally configure path agents in its domain to
act on behalf of its domain"s hosts only. However, a path agent can
be configured to act on behalf of any Internet host. This
flexibility permits one domain to act as an IDPR "proxy" for another
domain. For example, a small stub domain may wish to have policy
routing available to a few of its hosts but may not want to set up
its domain to support all of the IDPR functionality. The
administrator of the stub domain can negotiate the proxy function
with the administrator of another domain, who agrees that its domain
will provide policy routes on behalf of the stub domain"s hosts.
If a source domain supports IDPR and limits all domain egress points
to policy gateways, then each message generated by a host in that
source domain and destined for a host in another domain must pass
through at least one policy gateway, and hence path agent, in the
source domain. A host need not know how to reach any policy gateways
in its domain; it need only know how to reach a gateway on its own
local network. Gateways within the source domain direct inter-domain
host traffic toward policy gateways, using default routes or routes
derived from other inter-domain routing procedures.
If a source domain does not support IDPR and requires an IDPR proxy
domain to provide its hosts with policy routing, the administrator of
that source domain must carefully choose the proxy domain. All
intervening gateways between hosts in the source domain and path
agents in the proxy domain forward traffic according to default
routes or routes derived from other inter-domain routing procedures.
In order for traffic from hosts in the source domain to reach the
proxy domain with no special intervention, the proxy domain must lie
on an existing non-IDPR inter-domain route from the source to the
destination domain. Hence, to minimize the knowledge a domain
administrator must have about inter-domain routes when selecting a
proxy domain, we recommend that a domain administrator select its
proxy domain from the set of adjacent domains.
In either case, the first policy gateway to receive messages from an
inter-domain traffic flow originating at the source domain acts as
the path agent for the host generating that flow.
3.2.2. IDPR Servers
IDPR servers are the entities that manage the IDPR databases and that
respond to queries for information from policy gateways or other
servers. Each IDPR server may be a dedicated device, physically
separate from the policy gateway, or it may be part of the
functionality of the policy gateway itself. Separating the server
functions from the policy gateways reduces the processing and memory
requirements for and increases the data traffic carrying capacity of
the policy gateways.
The following IDPR databases: routing information, route, mapping,
and configuration, may be distributed hierarchically, with partial
redundancy throughout the Internet. This arrangement implies a
hierarchy of the associated servers, where a server"s position in the
hierarchy determines the extent of its database. At the bottom of
the hierarchy are the "local servers" that maintain information
pertinent to a single domain; at the top of the hierarchy are the
"global servers" that maintain information pertinent to all domains
in the Internet. There may be zero or more levels in between the
local and global levels.
Hierarchical database organization relieves most IDPR servers of the
burden of maintaining information about large portions of the
Internet, most of which their clients will never request.
Distributed database organization, with redundancy, allows clients to
spread queries among IDPR servers, thus reducing the load on any one
server. Furthermore, failure to communicate with a given IDPR server
does not mean the loss of the entire service, as a client may obtain
the information from another server. We note that some IDPR
databases, such as the mapping database, may grow so large that it is
not feasible to store the entire database at any single server.
IDPR routing information databases need not be completely consistent
for proper policy route generation and use, because message
forwarding along policy routes is completely specified by the source
path agent. The absence of a requirement for consistency among IDPR
routing information databases implies that there is no requirement
for strict synchronization of these databases. Such synchronization
is costly in terms of the message processing and transmission
bandwidth required. Nevertheless, each IDPR route server should have
a query/response mechanism for making its routing information
database consistent with that of another route server, if necessary.
A route server uses this mechanism to update its routing information
database following detection of a gap or potential error in database
contents, for example, when the route server returns to service after
disconnection from the Internet.
A route server in one domain wishing to communicate with a route
server in another domain must establish a policy route to the other
route server"s domain. To generate and establish a policy route, the
route server must know the other route server"s domain, and it must
have sufficient routing information to construct a route to that
domain. As route servers may often intercommunicate in order to
obtain routing information, one might assume an ensuing deadlock in
which a route server requires routing information from another route
server but does not have sufficient mapping and routing information
to establish a policy route to that route server. However, such a
deadlock should seldom persist, if the following IDPR functionality
is in place:
- A mechanism that allows a route server to gain access, during route
server initialization, to the identities of the other route servers
within its domain. Using this information, the route server need not
establish policy routes in order to query these route servers for
routing information.
- A mechanism that allows a route server to gain access, during route
server initialization, to its domain"s adjacencies. Using this
information, the route server may establish policy routes to the
adjacent domains in order to query their route servers for routing
information when none is available within its own domain.
- Once operational, a route server should collect (memory capacity
permitting) all the routing information to which it has access. A
domain usually does not restrict distribution of its routing
information but instead distributes its routing information to all
other Internet domains. Hence, a route server in a given domain is
likely to receive routing information from most Internet domains.
- A mechanism that allows an operational route server to obtain the
identities of external route servers from which it can obtain routing
information and of the domains containing these route servers.
Furthermore, this mechanism should not require mapping server queries.
Rather, each domain should distribute in its routing information
messages the identities of all route servers, within its domain, that
may be queried by clients outside of its domain.
When a host in one domain wishes to communicate with a host in
another domain, the path agent in the source domain must establish a
policy route to a path agent in the destination domain. However, the
source path agent must first query a mapping server, to determine the
identity of the destination domain. The queried mapping server may
in turn contact other mapping servers to obtain a reply. As with
route server communication, one might assume an ensuing deadlock in
which a mapping server requires mapping information from an external
mapping server but the path agent handling the traffic does not have
sufficient mapping information to determine the domain of, and hence
establish a policy route to, that mapping server.
We have previously described how to minimize the potential for
deadlock in obtaining routing information. To minimize the potential
for deadlock in obtaining mapping information, there should be a
mechanism that allows a mapping server to gain access, during mapping
server initialization, to the identities of other mapping servers and
the domains in which they reside. Thus, when a mapping server needs
to query an external mapping server, it knows the identity of that
mapping server and sends a message. The path agent handling this
traffic queries a local mapping server to resolve the identity of the
external mapping server to the proper domain and then proceeds to
establish a policy route to that domain.
3.2.3. Entity Identifiers
Each domain has a unique identifier within the Internet, specifically
an ordinal number in the enumeration of Internet domains, determined
by the Internet Assigned Numbers Authority (IANA) who is responsible
for maintaining such information.
Each virtual gateway has a unique local identifier within a domain,
derived from the adjacent domain"s identifier together with the
virtual gateway"s ordinal number within an enumeration of the virtual
gateways connecting the two domains. The administrators of both
domains mutually agree upon the enumeration of the virtual gateways
within their shared set of virtual gateways; selecting a single
virtual gateway enumeration that applies in both domains eliminates
the need to maintain a mapping between separate virtual gateway
ordinal numbers in each domain.
Each policy gateway and route server has a unique local identifier
within its domain, specifically an ordinal number in the domain
administrator"s enumeration of IDPR entities within its domain. This
local identifier, when combined with the domain identifier, produces
a unique identifier within the Internet for the policy gateway or
route server.
3.3. Security and Reliability
The correctness of control information, and in particular routing-
related information, distributed throughout the Internet is a
critical factor affecting the Internet"s ability to transport data.
As the number and heterogeneity of Internet domains increases, so too
does the potential for both information corruption and denial of
service attacks. Thus, we have imbued the IDPR architecture with a
variety of mechanisms to:
- Promote timely delivery of control information.
- Minimize acceptance and distribution of corrupted control
information.
- Verify authenticity of a source of control information.
- Reduce the chances for certain types of denial of service attacks.
Consult [11] for a general security architecture for routing and [12]
for a security architecture for inter-domain routing.
3.3.1. Retransmissions and Acknowledgements
All IDPR entities must make an effort to accept and distribute only
correct IDPR control messages. Each IDPR entity that transmits an
IDPR control message expects an acknowledgement from the recipient
and must retransmit the message up to a maximum number of times when
an acknowledgement is not forthcoming. An IDPR entity that receives
an IDPR control message must verify message content integrity and
source authenticity before accepting, acknowledging, and possibly
redistributing the message.
3.3.2. Integrity Checks
Integrity checks on message contents promote the detection of
corrupted information. Each IDPR entity that receives an IDPR
control message must perform several integrity checks on the
contents. Individual IDPR protocols may apply more stringent
integrity checks than those listed below. The required checks
include confirmation of:
- Recognized message version.
- Consistent message length.
- Valid message checksum.
Each IDPR entity may also apply these integrity checks to IDPR data
messages. Although the IDPR architecture only requires data message
integrity checks at the last IDPR entity on a path, it does not
preclude intermediate policy gateways from performing these checks as
well.
3.3.3. Source Authentication
Authentication of a message"s source promotes the detection of a
rogue entity masquerading as another legitimate entity. Each IDPR
entity that receives an IDPR control message must verify the
authenticity of the message source. We recommend that the source of
the message supply a digital signature for authentication by message
recipients. The digital signature should cover the entire message
contents (or a hash function thereof), so that it can serve as the
message checksum as well as the source authentication information.
Each IDPR entity may also authenticate the source of IDPR data
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