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