As per Relevance of the word policies, we have this rfc below:
Network Working Group D.
Request for Comments: 1322
Y.
S.
May 1992
A Unified Approach to Inter-Domain
Status of this
This memo provides information for the Internet community. It
not specify an Internet standard. Distribution of this memo
unlimited
This memo is an informational RFC which outlines one
approach for inter-domain routing in future global internets.
focus is on scalability to very large networks and functionality,
well as scalability, to support routing in an environment
heterogeneous services, requirements, and route selection criteria
Note: The work of D. Estrin and S. Hotz was supported by the
Science Foundation under contract number NCR-9011279, with
funds from GTE Laboratories. The work of Y. Rekhter was supported
the Defense Advanced Research Projects Agency, under
DABT63-91-C-0019. Views and conclusions expressed in this paper
not necessarily those of the Defense Advanced Research
Agency and National Science Foundation
1.0
The global internet can be modeled as a collection of
interconnected via transmission and switching facilities.
over the collection of hosts and the transmission and
facilities that compose the networking resources of the
internet is not homogeneous, but is distributed among
administrative authorities. Resources under control of a
administration form a domain. In order to support each domain'
autonomy and heterogeneity, routing consists of two
components: intra-domain (interior) routing, and inter-
(exterior) routing. Intra-domain routing provides support for
communication between hosts where data traverses transmission
switching facilities within a single domain. Inter-domain
provides support for data communication between hosts where
Estrin, Rekhter & Hotz [Page 1]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
traverses transmission and switching facilities spanning
domains. The entities that forward packets across domain
are called border routers (BRs). The entities responsible
exchanging inter-domain routing information are called route
(RSs). RSs and BRs may be colocated
As the global internet grows, both in size and in the diversity
routing requirements, providing inter-domain routing that
accommodate both of these factors becomes more and more crucial.
number and diversity of routing requirements is increasing due to
(a) transit restrictions imposed by source, destination, and
networks, (b) different types of services offered and required,
(c) the presence of multiple carriers with different
schemes. The combinatorial explosion of mixing and matching
different criteria weighs heavily on the mechanisms provided
conventional hop-by-hop routing architectures ([ISIS10589, OSPF
Hedrick88, EGP]).
Current work on inter-domain routing within the Internet
has diverged in two directions: one is best represented by the
Gateway Protocol (BGP)/Inter-Domain Routeing Protocol (IDRP
architectures ([BGP91, Honig90, IDRP91]), and another is
represented by the Inter-Domain Policy Routing (IDPR)
([IDPR90, Clark90]). In this paper we suggest that the
architectures are quite complementary and should not be
mutually exclusive
We expect that over the next 5 to 10 years, the types of
available will continue to evolve and that specialized
will be employed to provide new services. While the number
variety of routes provided by hop-by-hop routing architectures
type of service (TOS) support (i.e., multiple, tagged routes) may
sufficient for a large percentage of traffic, it is important
mechanisms be in place to support efficient routing of
traffic types via special routes. Examples of special routes are
(1) a route that travels through one or more transit domains
discriminate according to the source domain, (2) a route that
through transit domains that support a service that is not widely
regularly used. We refer to all other routes as generic
Our desire to support special routes efficiently led us
investigate the dynamic installation of routes ([Breslau-Estrin91,
Clark90, IDPR90]). In a previous paper ([Breslau-Estrin91]),
evaluated the algorithmic design choices for inter-domain
routing with specific attention to accommodating source-specific
other "special" routes. The conclusion was that special routes
best supported with source-routing and extended link-
algorithms; we refer to this approach as source-demand
Estrin, Rekhter & Hotz [Page 2]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
[Footnote: The Inter-Domain Policy Routing (IDPR) architecture
these techniques.]. However, a source-demand routing architecture
used as the only means of inter-domain routing, has scaling
because it does not lend itself to general hierarchical
and aggregation of routing and forwarding information. For example
even if a particular route from an intermediate transit domain X,
a destination domain Y is shared by 1,000 source-domains,
requires that state for each of the 1,000 routes be setup
maintained in the transit border routers between X and Y.
contrast, an alternative approach to inter-domain routing, based
hop-by-hop routing and a distributed route-computation
(described later), provides extensive support for aggregation
abstraction of reachability, topology, and forwarding information
The Border Gateway Protocol (BGP) and Inter-Domain Routeing
(IDRP) use these techniques ([BGP91, IDRP91]). While the BGP/
architecture is capable of accommodating very large numbers
datagram networks, it does not provide support for
routing requirements as flexibly and efficiently as IDPR-
routing
1.1 Overview of the Unified
We want to support special routes and we want to exploit
when a special route is not needed. Therefore, our scalable inter
domain routing architecture consists of two major components
source-demand routing (SDR), and node routing (NR). The NR
computes and installs routes that are shared by a significant
of sources. These generic routes are commonly used and warrant
propagation, consequently, aggregation of routing information
critical. The SDR component computes and installs specialized
that are not shared by enough sources to justify computation by
[Footnote: Routes that are only needed sporadically (i.e., the
for them is not continuous or otherwise predictable) are
candidates for SDR.]. The potentially large number of
specialized routes, combined with their sparse utilization, make
too costly to support with the NR mechanism
A useful analogy to this approach is the manufacturing of
products. When predictable patterns of demand exist, firms
objects and sell them as "off the shelf" consumer goods. In
architecture NR provides off-the-shelf routes. If demand is
predictable, then firms accept special orders and produce what
demanded at the time it is needed. In addition, if a part is
specialized that only a single or small number of consumers need it
the consumer may repeatedly special order the part, even if it
needed in a predictable manner, because the consumer does
represent a big enough market for the producer to bother managing
item as part of its regular production. SDR provides such
Estrin, Rekhter & Hotz [Page 3]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
order, on-demand routes
By combining NR and SDR routing we propose to support inter-
routing in internets of practically-unlimited size, while at the
time providing efficient support for specialized
requirements
The development of this architecture does assume that
requirements will be diverse and that special routes will be needed
On the other hand, the architecture does not depend on
about the particular types of routes demanded or on the
of that demand. Routing will adapt naturally over time to
traffic patterns and new services by shifting computation
installation of particular types of routes between the two
of the hybrid architecture [Footnote: Before continuing with
explanation of this architecture, we wish to state up front
supporting highly specialized routes for all source-destination
in an internet, or even anything close to that number, is
feasible in any routing architecture that we can foresee. In
words, we do not believe that any foreseeable routing
can support unconstrained proliferation of user requirements
network services. At the same time, this is not necessarily
problem. The capabilities of the architecture may in fact exceed
requirements of the users. Moreover, some of the requirements
we regard as infeasible from the inter-domain routing point of view
may be supported by means completely outside of routing
Nevertheless, the caveat is stated here to preempt
expectations.].
While the packet forwarding functions of the NR and SDR
have little or no coupling with each other, the
information exchange mechanism of the SDR component relies
services provided by the NR component
1.2
The remainder of this report is organized as follows. Section 2
outlines the requirements and priorities that guide the design of
NR and SDR components. Sections 3 and 4 describe the NR and
design choices, respectively, in light of these requirements
Section 5 describes protocol support for the unified architecture
briefly discusses transition issues. We conclude with a
summary
Estrin, Rekhter & Hotz [Page 4]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
2.0 Architectural Requirements and
In order to justify our design choices for a scalable inter-
routing architecture, we must articulate our evaluation criteria
priorities. This section defines complexity, abstraction, policy
and type of service requirements
2.1
Inter-domain routing complexity must be evaluated on the basis of
following performance metrics: (1) storage overhead, (2)
computational overhead, and (3) message overhead. This evaluation
essential to determining the scalability of any architecture
2.1.1 Storage
The storage overhead of an entity that participates in inter-
routing comes from two sources: Routing Information Base (RIB),
Forwarding Information Base (FIB) overhead. The RIB contains
routing information that entities exchange via the inter-
routing protocol; the RIB is the input to the route computation.
FIB contains the information that the entities use to forward
inter-domain traffic; the FIB is the output of the route computation
For an acceptable level of storage overhead, the amount
information in both FIBs and RIBs should grow significantly
than linearly (e.g., close to logarithmically) with the total
of domains in an internet. To satisfy this requirement with
to the RIB, the architecture must provide mechanisms for
aggregation and abstraction of routing and forwarding information,
retrieval of a subset of this information on demand. To satisfy
requirement with respect to the FIB, the architecture must
mechanisms for either aggregation of the forwarding information (
the NR computed routes), or dynamic installation/tear down of
information (for the SDR computed routes).
Besides being an intrinsically important evaluation metric,
overhead has a direct impact on computational and
complexity. Unless the computational complexity is fixed (
independent of the total number of domains), the storage overhead
direct impact on the computational complexity of the
since the routing information is used as an input to
computation. Moreover, unless the architecture employs
updates, where only changes to the routing information
propagated, the storage overhead has direct impact on the
overhead of the architecture since the exchange of
information constitutes most of the bandwidth overhead
Estrin, Rekhter & Hotz [Page 5]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
2.1.2 Computational
The NR component will rely primarily on precomputation of routes.
inter-domain routing is ubiquitous, then the precomputed
include all reachable destinations. Even if policy constraints
fully ubiquitous routing impossible, the precomputed routes
likely to cover a very large percentage of all
destinations. Therefore the complexity of this computation must
as small as possible. Specifically, it is highly desirable that
architecture would employ some form of partial computation,
changes in topology would require less than complete recomputation
Even if complete recomputation is necessary, its complexity should
less than linear with the total number of domains
The SDR component will use on-demand computation and caching
Therefore the complexity of this computation can be somewhat higher
Another reason for relaxed complexity requirements for SDR is
SDR is expected to compute routes to a smaller number of
than is NR (although SDR route computation may be invoked
frequently).
Under no circumstances is computational complexity allowed to
exponential (for either the NR or SDR component).
2.1.3 Bandwidth
The bandwidth consumed by routing information distribution should
limited. However, the possible use of data compression
and the increasing speed of network links make this less
than route computation and storage overhead. Bandwidth overhead
be further contained by using incremental (rather than complete
exchange of routing information
While storage and bandwidth overhead may be interrelated,
incremental updates are used then bandwidth overhead is negligible
the steady state (no changes in topology), and is independent of
storage overhead. In other words, use of incremental
constrains the bandwidth overhead to the dynamics of the internet
Therefore, improvements in stability of the physical links,
with techniques to dampen the effect of topological instabilities
will make the bandwidth overhead even less important
2.2
Aggregation and abstraction of routing and forwarding
provides a very powerful mechanism for satisfying storage
computational, and bandwidth constraints. The ability to aggregate
and subsequently abstract, routing and forwarding information
Estrin, Rekhter & Hotz [Page 6]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
essential to the scaling of the architecture [Footnote: While we
not prove that there are no other ways to achieve scaling, we are
aware of any mechanism other than clustering that allows
aggregation/abstraction. Therefore, the rest of the paper
that clustering is used for information aggregation/abstraction.].
This is especially true with respect to the NR component, since
NR component must be capable of providing routes to all or almost
reachable destinations
At the same time, since preserving each domain's independence
autonomy is one of the crucial requirements of inter-domain routing
the architecture must strive for the maximum flexibility of
aggregation scheme, i.e., impose as few preconditions, and as
global coordination, as possible on the participating domains
The Routing Information Base (RIB) carries three types
information: (1) topology (i.e., the interconnections between
or groups of domains), (2) network layer reachability, and (3)
transit constraint. Aggregation of routing information
provide a reduction of all three components. Aggregation
forwarding information will follow from reachability
aggregation
Clustering (by forming routing domain confederations) serves
following aggregation functions: (1) to hide parts of the
physical topology, thus abstracting topological information, (2)
combine a set of reachable destination entities into a single
and reduce storage overhead, and (3) to express transit
in terms of clusters, rather than individual domains
As argued in [Breslau-Estrin91], the architecture must
confederations to be formed and changed without
configuration and coordination; in particular, forming
confederation should not require global coordination (such as
required in ECMA ([ECMA89]). In addition, aggregation should
require explicit designation of the relative placement of each
relative to another; i.e., domains or confederations of
should not be required to agree on a partial ordering (i.e., who
above whom, etc.).
Estrin, Rekhter & Hotz [Page 7]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
The architecture should allow different domains to use
methods of aggregation and abstraction. For example, a
collaborator at IBM might route to USC as a domain-level entity
order to take advantage of some special TOS connectivity to, or
through, USC. Whereas, someone else at Digital Equipment
might see information at the level of the California
Institutions Confederation, and know only that USC is a member
Alternatively, USC might see part of the internal structure
the IBM Confederation (at the domain's level), whereas UCLA may
based on the confederation of IBM domains as a whole
Support for confederations should be flexible. Specifically,
architecture should allow confederations to overlap without
nested, i.e., a single domain, or a group of domains may be part
more than one confederation. For example, USC may be part of
California Educational Institutions Confederation and part of the
R&D Institutions Confederation; one is not a subset of the other
Another example: T.J. Watson Research Center might be part
NYSERNET Confederation and part of IBM-R&D-US Confederation.
the above examples describe cases where overlap consists of a
domain, there may be other cases where multiple domains overlap.
an example consider the set of domains that form the
Confederation, and another set of domains that form the
Confederation. Within IBM there is a domain IBM-Research,
similarly within DEC there is a domain DEC-Research. Both of
domains could be involved in some collaborative effort, and thus
established direct links. The architecture should allow
use of these direct links, so that other domains within the
Confederation would not be able to use it to talk to other
within the DEC Confederation. A similar example exists when
multinational corporation forms a confederation, and the
branches within each country also belong to their respective
confederations. The corporation may need to protect itself
being used as an inter-country transit domain (due to internal,
international, policy). All of the above examples illustrate
situation where confederations overlap, and it is necessary
control the traffic traversing the overlapping resources
While flexible aggregation should be accommodated in any inter-
architecture, the extent to which this feature is exploited will
direct a effect on the scalability associated with aggregation.
the same time, the exploitation of this feature depends on the
addresses are assigned. Specifically, scaling associated
forwarding information depends heavily on the assumption that
will be general correspondence between the hierarchy of
registration authorities, and the way routing domains and
domain confederations are organized (see Section 2.6).
Estrin, Rekhter & Hotz [Page 8]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
2.3 Routing
Routing policies that the architecture must support may be
classified into transit policies and route selection
[Breslau-Estrin 91, Estrin89].
Restrictions imposed via transit policies may be based on a
of factors. The architecture should be able to support
based on the source, destination, type of services (TOS), user
identification (UCI), charging, and path [Estrin89 , Little89].
architecture must allow expression of transit policies on all routes
both NR and SDR. Even if NR routes are widely used and have
source or destination restrictions, NR routes may have some
qualifiers (e.g., TOS, charging, or user-class restriction). If
most widely-usable route to a destination has policy qualifiers,
should be advertiseable by NR and the transit constraints should
explicit
Route selection policies enable each domain to select a
route among multiple routes to the same destination. To
maximum autonomy and independence between domains, the
must support heterogeneous route selection policies, where
domain can establish its own criteria for selecting routes.
argument was made earlier with respect to source route
([IDPR90, Clark90, Breslau-Estrin91]). In addition,
intermediate transit domain must have the flexibility to apply
own selection criteria to the routes made available to it by
neighbors. This is really just a corollary to the above; i.e., if
allow route selection policy to be expressed for NR routes, we
not assume all domains will apply the same policy. The support
dissimilar route selection policies is one of the key factors
distinguish inter-domain routing from intra-domain routing ([ECMA89,
Estrin89]). However, it is a non-goal of the architecture to
all possible route selection policies. For more on unsupported
selection policies see Section 2.3.2 below
2.3.1 Routing Information
The architecture should not require all domains within an internet
reveal their connectivity and transit constraints to each other
Domains should be able to enforce their transit policies
limiting the advertisement of their policy and
information as much as possible; such advertisement will be driven
a "need to know" criteria. Moreover, advertising a transit policy
domains that can not use this policy will increase the amount
routing information that must be stored, processed, and propagated
Not only may it be impractical for a router to maintain full inter
domain topology and policy information, it may not be permitted
Estrin, Rekhter & Hotz [Page 9]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
obtain this information
2.3.2 Policies Not
In this and previous papers we have argued that a global inter-
routing architecture should support a wide range of policies.
this section we identify several types of policy that we
do not propose to support. In general our reasoning is pragmatic;
think such policy types are either very expensive in terms
overhead, or may lead to routing instabilities
1. Route selection policies contingent on external behavior
The route selection process may be modeled by a function
assigns a non-negative integer to a route, denoting the
of preference. Route selection applies this function to
feasible routes to a given destination, and selects the
with the highest value. To provide a stable environment,
preference function should not use as an input the status
attributes of other routes (either to the same or to
different destination).
2. Transit policies contingent on external behavior
To provide a stable environment, the domain's transit
can not be automatically affected by any information
to the domain. Specifically, these policies can not be modified
automatically, in response to information about other domains
transit policies, or routes selected by local or other domains
Similarly, transit policies can not be automatically
in response to information about performance characteristics
either local or external domains
3. Policies contingent on external state (e.g., load).
It is a non-goal of the architecture to support load-
routing for generic routes. However, it is possible that
types of service may employ load information to select
alternate SDR routes
4. Very large number of simultaneous SDR routes
It is a non-goal of the architecture to support a very
number of simultaneous SDR routes through any single router
Specifically, the FIB storage overhead associated with
routes must be comparable with that of NR routes, and
always be bound by the complexity requirements outlined
[Foonote: As discussed earlier, theoretically the state
could grow O(N^2) with the number of domains in an internet
However, there is no evidence or intuition to suggest
this will be a limiting factor on the wide utilization of SDR
provided that NR is available to handle generic routes.].
Estrin, Rekhter & Hotz [Page 10]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
2.4 Support for TOS
Throughout this document we refer to support for type of
(TOS) routing. There is a great deal of research and
activity currently underway to explore network architectures
protocols for high-bandwidth, multimedia traffic. Some of
traffic is delay sensitive, while some requires high throughput.
is unrealistic to assume that a single communication fabric will
deployed homogeneously across the internet (including
metropolitan, regional, and backbone networks) that will support
types of traffic uniformly. To support diverse traffic
in a heterogeneous environment, various resource
mechanisms will be used in different parts of the global
(e.g., resource reservation of various kinds) [ST2-90, Zhang91].
In this context, it is the job of routing protocols to locate
that can potentially support the particular TOS requested. It
explicitly not the job of the general routing protocols to
routes that are guaranteed to have resources available at
particular time of the route request. In other words, it is
practical to assume that instantaneous resource availability will
known at all remote points in the global internet. Rather, once
TOS route has been identified, an application requiring
service guarantees will attempt to use the route (e.g., using
explicit setup message if so required by the underlying networks).
In Section 4 we describe additional services that may be provided
support more adaptive route selection for special TOS [Footnote
Adaptive route selection implies adaptability only during the
selection process. Once a route is selected, it is not going to be
subject to any adaptations, except when it becomes infeasible.].
2.5 Commonality between Routing
While it is acceptable for the NR and SDR components to
dissimilar, we do recognize that such a solution is less desirable --
all other things being equal. In theory, there are advantages
having the NR and SDR components use similar algorithms
mechanisms. Code and databases could be shared and the
would be more manageable and comprehensible. On the other hand
there may be some benefit (e.g., robustness) if the two parts of
architecture are heterogeneous, and not completely inter-dependent
In Section 5 we list several areas in which opportunities
increased commonality (unification) will be exploited
2.6 Interaction with
The proposed architecture should be applicable to various
schemes. There are no specific assumptions about a
Estrin, Rekhter & Hotz [Page 11]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
address structure, except that this structure should
information aggregation, without forcing rigid hierarchical routing
Beyond this requirement, most of the proposals for extending the
address space, for example, can be used in conjunction with
architecture. But our architecture itself does not provide (
impose) a particular solution to the addressing problem
Estrin, Rekhter & Hotz [Page 12]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
3.0 Design Choices for Node Routing (NR
This section addresses the design choices made for the NR
in light of the above architectural requirements and priorities.
of our discussion of NR assumes hop-by-hop routing. Source
is subject to different constraints and is used for the
SDR component
3.1 Overview of
The NR component is designed and optimized for an environment where
large percentage of packets will travel over routes that can
shared by multiple sources and that have predictable
patterns. The efficiency of the NR component improves when a
of source domains share a particular route from some
point to a destination. Moreover, NR is best suited to
routing for inter-domain data traffic that is either steady enough
justify the existence of a route, or predictable, so that a route
be installed when needed (based on the prediction, rather than on
actual traffic). Such routes lend themselves to distributed
computation and installation procedures
Routes that are installed in routers, and information that was
by the routers to compute these routes, reflect the known
state of the routing facilities (as well as the policy constraints
at the time of route computation. Route computation is driven
changes in either operational status of routing facilities or
constraints. The NR component supports route computation that
dynamically adaptable to both changes in topology and policy. The
component allows time-dependent selection or deletion of routes
However, time dependency must be predictable (e.g., advertising
certain route only after business hours) and routes should be
widely enough to warrant inclusion in NR
The proposed architecture assumes that most of the inter-
conversations will be forwarded via routes computed and installed
the NR component
Moreover, the exchange of routing information necessary for the
component depends on facilities provided by the NR component; i.e.,
NR policies must allow SDR reachability information to travel
Therefore, the architecture requires that all domains in an
implement and participate in NR. Since scalability (with respect
the size of the internet) is one of the fundamental requirements
the NR component, it must provide multiple mechanisms with
degrees of sophistication for information aggregation
abstraction
Estrin, Rekhter & Hotz [Page 13]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
The potential reduction of routing and forwarding information
very heavily on the way addresses are assigned and how domains
their confederations are structured. "If there is no
between the address registration hierarchy and the organisation
routeing domains, then ... each and every routeing domain in the
would need a table entry potentially at every boundary IS of
other routeing domain" ([Oran89]). Indeed, scaling in the
component is almost entirely predicated on the assumption that
will be general correspondence between the hierarchy of
assignment authorities and the way routing domains are organised,
that the efficient and frequent aggregation of routing and
information will be possible. Therefore, given the nature of inter
domain routing in general, and the NR component in particular
scalability of the architecture depends very heavily on
flexibility of the scheme for information aggregation
abstraction, and on the preconditions that such a scheme imposes
Moreover, given a flexible architecture, the operational
(scalability) of the global internet, or portions thereof,
depend on tradeoffs made between flexibility and aggregation
While the NR component is optimized to satisfy the common
routing requirements for an extremely large population of users,
does not imply that routes produced by the NR component would not
used for different types of service (TOS). To the contrary, if a
becomes sufficiently widely used (i.e., by multiple domains
predictably over time), then it may warrant being computed by the
component
To summarize, the NR component is best suited to provide routes
are used by more than a single domain. That is, the efficiency
the NR component improves when a number of source domains share
particular route from some intermediate point to a destination
Moreover, NR is best suited to provide routing for inter-domain
traffic that is either steady enough to justify the existence of
route, or predictable, so that a route may be installed when needed
(based on the prediction, rather than on the actual traffic).
3.2 Routing Algorithm Choices for
Given that a NR component based on hop-by-hop routing is needed
provide scalable, efficient inter-domain routing, the remainder
this section considers the fundamental design choices for the
routing algorithm
Typically the debate surrounding routing algorithms focuses on
state and distance vector protocols. However, simple distance
protocols (i.e., Routing Information Protocol [Hedrick88]), do
scale because of convergence problems. Improved distance
Estrin, Rekhter & Hotz [Page 14]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
protocols, such as those discussed in [Jaffee82, Zaumen91, Shin87],
have been developed to address this issue using
mechanisms or additional path information. In the case of inter
domain routing, having additional path information is essential
supporting policy. Therefore, the algorithms we consider for NR
link state and one we call path vector (PV). Whereas
characteristics of link state algorithms are generally
(for example, [Zaumen 91]), we must digress from our
discussion to describe briefly the newer concept of the PV
[Footnote: We assume that some form of SPF algorithm will be used
compute paths over the topology database when LS algorithms are
[Dijkstra59, OSPF]].
3.2.1 Path Vector Protocol
The Border Gateway Protocol (BGP) (see [BGP91]) and the Inter
Routing Protocol (IDRP) (see [IDRP91]) are examples of path
(PV) protocols [Footnote: BGP is an inter-autonomous system
protocol for TCP/IP internets. IDRP is an OSI inter-domain
protocol that is being progressed toward standardization within ISO
Since in terms of functionality BGP represents a proper subset
IDRP, for the rest of the paper we will only consider IDRP.].
The routing algorithm employed by PV bears a certain resemblance
the traditional Bellman-Ford routing algorithm in the sense that
border router advertises the destinations it can reach to
neighboring BRs. However,the PV routing algorithm augments
advertisement of reachable destinations with information
describes various properties of the paths to these destinations
This information is expressed in terms of path attributes.
emphasize the tight coupling between the reachable destinations
properties of the paths to these destinations, PV defines a route
a pairing between a destination and the attributes of the path
that destination. Thus the name, path-vector protocol, where a
receives from its neighboring BR a vector that contains paths to
set of destinations [Footnote: The term "path-vector protocol"
an intentional similarity to the term "distance-vector protocol",
where a BR receives from each of its neighbors a vector that
distances to a set of destinations.]. The path, expressed in
of the domains (or confederations) traversed so far, is carried in
special path attribute which records the sequence of routing
through which the reachability information has passed.
of routing loops is implemented via this special path attribute,
contrast to LS and distance vector which use a globally-
monotonically-increasing metric for route selection [Shin87].
Because PV does not require all routing domains to have
Estrin, Rekhter & Hotz [Page 15]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
criteria (policies) for route selection, route selection
used by one routing domain are not necessarily known to other
domains. To maintain the maximum degree of autonomy and
between routing domains, each domain which participates in PV
have its own view of what constitutes an optimal route. This view
based solely on local route selection policies and the
carried in the path attributes of a route. PV standardizes only
results of the route selection procedure, while allowing
selection policies that affect the route selection to be non-
[Footnote: This succinct observation is attributed to Ross
(Digital Equipment Corporation).].
3.3
Given the above description of PV algorithms, we can compare them
LS algorithms in terms of the three complexity parameters
earlier
3.3.1 Storage
Without any aggregation of routing information, and ignoring
overhead associated with transit constraints, it is possible to
that under some rather general assumptions the average case
storage overhead of the PV scheme for a single TOS ranges
O(N) and O(Nlog(N)), where N is the total number of routing
([Rekhter91]). The LS RIB, with no aggregation of
information, no transit constraints, a single homogeneous
selection policy across all the domains, and a single TOS, requires
complete domain-level topology map whose size is O(N).
Supporting heterogeneous route selection and transit policies
hop-by-hop forwarding and LS requires each domain to know all
domains route selection and transit policies. This may
increase the amount of routing information that must be stored
each domain. If the number of policies advertised grows with
number of domains, then the storage could become unsupportable.
contrast, support for heterogeneous route selection policies has
effect on the storage complexity of the PV scheme (aside from
storing the local policy information). The presence of
constraints in PV results in a restricted distribution of
information, thus further reducing storage overhead. In contrast
with LS no such reduction is possible since each domain must
every other domain's transit policies. Finally, some of the
constraints (e.g., path sensitive constraints) can be expressed in
more concise form in PV (see aggregation discussion below).
The ability to further restrict storage overhead is facilitated
the PV routing algorithm, where route computation precedes
Estrin, Rekhter & Hotz [Page 16]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
information dissemination, and only routing information
with the routes selected by a domain is distributed to
domains. In contrast, route selection with LS is decoupled from
distribution of routing information, and has no effect on
distribution
While theoretically routing information aggregation can be used
reduce storage complexity in both LS and PV, only aggregation
topological information would yield the same gain for both
Aggregating transit constraints with LS may result in either
connectivity or less information reduction, as compared with PV
Aggregating heterogeneous route selection policies in LS is
problematic, at best. In PV, route selection policies are
distributed, thus making aggregation of route selection policies
non-issue [Footnote: Although a domain's selection policies are
explicitly distributed, they have an impact on the routes
to other domains. A route that may be preferred by a
domain, and not prohibited by transit restrictions, may still
unavailable due to the selection policies of some
domain. The ability to compute and install alternative routes
may be lost using hop-by-hop routing (either LS of PV) is
critical functionality provided by SDR.].
Support for multiple TOSs has the same impact on storage overhead
both LS and for PV
Potentially the LS FIB may be smaller if routes are computed at
node on demand. However, the gain of such a scheme depends
on the traffic patterns, memory size, and caching strategy. If
is not a high degree of locality, severely degraded performance
result due to excessive overall computation time and
computation delay when forwarding packets to a new destination.
demand driven route computation is not used for LS, then the size
the FIB would be the same for both LS and PV
Estrin, Rekhter & Hotz [Page 17]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
3.3.2 Route Computation
Even if all domains employ exactly the same route selection policy
computational complexity of PV is smaller than that of LS. The
computation consists of evaluating a newly arrived route
comparing it with the existing one [Footnote: Some additional
are required when an update is received to insure that a routing
has not been created.]. Whereas, conventional LS
requires execution of an SPF algorithm such as Dijkstra's
With PV, topology changes only result in the recomputation of
affected by these changes, which is more efficient than
recomputation. However, because of the inclusion of full
information with each distance vector, the effect of a
change may propagate farther than in traditional distance
algorithms. On the other hand, the number of affected domains
still be smaller with PV than with conventional LS hop-by-
routing. With PV, only those domains whose routes are affected
the changes have to recompute, while with conventional LS hop-by-
routing all domains must recompute. While it is also possible
employ partial recomputation with LS (i.e., when topology changes
only the affected routes are recomputed), "studies suggest that
a very small number of link changes (perhaps 2) the
computational complexity of the incremental update exceeds
complete recalculation" ([ANSI87-150R]). However these checks
much simpler than executing a full SPF algorithm
Support for heterogeneous route selection policies has
implications for the computational complexity. The major
with supporting heterogeneous route selection policies with LS is
computational complexity of the route selection itself
Specifically, we are not aware of any algorithm with less
exponential time complexity that would be capable of computing
to all destinations, with LS hop-by-hop routing and
route selection policies. In contrast, PV allows each domain to
its route selection autonomously, based only on local policies
Therefore support for dissimilar route selection policies has
negative implications for the complexity of route computation in PV
Similarly, providing support for path-sensitive transit policies
LS implies exponential computation, while in PV such support has
impact on the complexity of route computation
In summary, because NR will rely primarily on precomputation
routes, aggregation is essential to the long-term scalability of
architecture. To the extent aggregation is facilitated with PV,
is reduced computational complexity. While similar arguments may
made for LS, the aggregation capabilities that can be achieved
LS are more problematic because of LS' reliance on
Estrin, Rekhter & Hotz [Page 18]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
topology maps at each node. It is also not clear what
computational complexity will be associated with aggregation
transit constraints and heterogeneous route selection policies in LS
3.3.3 Bandwidth
PV routing updates include fully-expanded information. A
route for each supported TOS is advertised. In LS, TOS
contributes a factor increase per link advertised, which is much
than the number of complete routes. Although TOSs may be
more efficiently with LS than with PV, link state information
flooded to all domains, while with PV, routing updates
distributed only to the domains that actually use them. Therefore
it is difficult to make a general statement about which
imposes more bandwidth overhead, all other factors being equal
Moreover, this is perhaps really not an important difference,
we are more concerned with the number of messages than with
number of bits (because of compression and greater link bandwidth,
well as the increased physical stability of links).
3.4
Forming confederations of domains, for the purpose of consistent
hop-by-hop, LS route computation, requires that domains within
confederation have consistent policies. In addition,
confederation requires that any lower level entity be a member
only one higher level entity. In general, no intra-
information can be made visible outside of a confederation, or
routing loops may occur as a result of using an inconsistent map
the network at different domains. Therefore, the use
confederations with hop-by-hop LS is limited because each domain (
confederation) can only be a part of one higher level
and only export policies consistent with that confederation (
examples in Section 2.2). These restrictions are likely to
the scaling capabilities of the architecture quite severely
In comparison, PV can accommodate different confederation
because looping is avoided by the use of full path information
Consistent network maps are not needed at each route server,
route computation precedes routing information dissemination
Consequently, PV confederations can be nested, disjoint,
overlapping. A domain (or confederation) can export
policies or TOS as part of different confederations, thus
the extreme flexibility that is crucial for the overall scaling
extensibility of the architecture
In summary, aggregation is essential to achieve acceptable
Estrin, Rekhter & Hotz [Page 19]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
bounds, and flexibility is essential to achieve
aggregation across the global, decentralized internet. PV'
strongest advantage stems from its flexibility
3.5
The need to allow expression of transit policy constraints on
route (i.e., NR routes as well as SDR routes), by itself, can
supported by either LS or PV. However, the associated
of supporting transit policy constraints are noticeably higher for
than for PV. This is due to the need to flood all transit
with LS, where with PV transit policies are controlled via
distribution of routing information. The latter always imposes
overhead than flooding
While all of the transit constraints that can be supported with
can be supported with PV, the reverse is not true. In other words
there are certain transit constraints (e.g., path-sensitive
constraints) that are easily supported with PV, and are
expensive (in terms of complexity) to support in LS. For example,
is not clear how NR with LS could support something like ECMA-
policies that are based on hierarchical relations between domains
while support for such policies is straightforward with PV
As indicated above, support for heterogeneous route
policies, in view of its computational and storage complexity,
impractical with LS hop-by-hop routing. In contrast, PV
accommodate heterogeneous route selection with little
overhead
3.6 Information
PV has a clear advantage with respect to selective
hiding. LS with hop-by-hop routing hinges on the ability of
domains to have exactly the same information; this
contradicts the notion of selective information hiding. That is,
requirement to perform selective information hiding is
with LS hop-by-hop routing
3.7 Commonality between NR and SDR
In [Breslau-Estrin91] we argued for the use of LS in conjunction
SDR. Therefore there is some preference for using LS with NR
However, there are several reasons why NR and SDR would not
exactly the same routing information, even if they did use the
algorithm. Moreover, there are several opportunities for
the management (distribution and storage) of routing and
information, even if dissimilar algorithms are used
Estrin, Rekhter & Hotz [Page 20]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
In considering the differences between NR and SDR we must
several areas
1. Routing information and distribution protocol: LS for SDR
quite different from the LS in NR. For example, SDR LS
not aggregate domains; to the contrary SDR LS requires
information to generate special routes
In addition, consistency requirements (essential for NR)
unnecessary for the SDR component. Therefore LS information
the SDR component can be retrieved on-demand, while the
component must use flooding of topology information
2. Route computation algorithm: It is not clear whether
computation algorithm(s) can be shared between the SDR and
components, given the difficulty of supporting
route selection policies in NR
3. Forwarding information: The use of dissimilar route
algorithms does not preclude common handling of
forwarding. Even if LS were used for NR, the requirement
be the same, i.e., that the forwarding agent can
whether to use a NR precomputed route or an SDR installed
to forward a particular data packet
In conclusion, using similar algorithms and mechanisms for SDR and
components would have benefits. However, these benefits do
dominate the other factors as discussed before
Estrin, Rekhter & Hotz [Page 21]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
3.8
Given the performance complexity issues associated with
routing, aggregation of routing information is essential; at the
time we have argued that such aggregation must be flexible.
the difficulties of supporting LS hop-by-hop routing in the
of (a) flexible aggregation, (b) heterogeneous route
policies, and (c) incomplete or inconsistent routing information,
see no alternative but to employ PV for the NR component of
architecture
Based on the above tradeoffs, our NR component employs a
architecture, where route computation and installation is done in
distributed fashion by the routers participating in the NR
[Footnote: Packet forwarding along routes produced by the
component can be accomplished by either source routing or hop-by-
routing. The latter is the primary choice because it reduces
amount of state in routers (if route setup is employed), or
encoding an explicit source route in network layer packets. However
the architecture does not preclude the use of source routing (
route setup) along the routes computed, but not installed, by the
component.].
The distributed algorithm combines some of the features of link
with those of distance vector algorithms; in addition to next
information, the NR component maintains path attributes for
route (e.g., the list of domains or routing domain
that the routing information has traversed so far). The
attributes that are carried along with a route express a variety
routing policies, and make explicit the entire route to
destination. With aggregation, this is a superset of the
that form the path to the destination
Estrin, Rekhter & Hotz [Page 22]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
4.0 Source-demand routing (SDR
Inter-domain routers participating in the SDR component
packets according to routing information computed and installed
the domain that originates the traffic (source routing domain).
It is important to realize that requiring route installation by
source routing domain is not a matter of choice, but rather
necessity. If a particular route is used by a small number
domains (perhaps only one) then it is more appropriate to have
source compute and install the special route instead of burdening
intermediate nodes with the task of looking for and selecting a
with the specialized requirements. In addition, if the demand
the route is unpredictable, and thus can be determined only by
source, it should be up to the source to install the route
In general, information that is used by source routing domains
computing source-demand routes reflects administrative (but
operational) status of the routing facilities (i.e.,
topology and policy) [Footnote: If SDR uses NR information
operational status could be considered in some route selection.].
Consequently, it is possible for a source routing domain to compute
route that is not operational at route installation time. The
component attempts to notify the source domain of failures when
installation is attempted. Similarly, the SDR component
mechanisms for the source routing domain to be notified of
along previously-installed active routes. In other words, the
component performs routing that is adaptive to topological changes
however, the adaptability is achieved as a consequence of the
installation and route management mechanisms. This is different
the NR component, where status changes are propagated
incorporated by nodes as soon as possible. Therefore, to
faster adaptation to changes in the operational status of
facilities, the SDR component allows the source domain to switch to
route computed by the NR component, if failure along the source
demand route is detected (either during the route installation phase
or after the route is installed), and if policy permits use of the
route
The NR component will group domains into confederations to
its scaling goals (see [IDRP91]). In contrast, SDR will allow
AD-level route to be used by an individual domain without
use by the entire confederation to which the domain belongs
Similarly, a single transit domain may support a policy or
TOS that is not supported by other domains in its confederation(s).
In other words, the architecture uses SDR to support non
hierarchical, non-aggregated policies where and when needed
Consequently, SDR by itself does not have the scaling properties
Estrin, Rekhter & Hotz [Page 23]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
NR. In compensation, SDR does not require a complete, global
map if portions of the world are never traversed or
with. As a result of the looser routing structure, SDR does
guarantee that a participating source routing domain will always
sufficient information to compute a route to a destination.
addition, if the domain does have sufficient information, it
possible that the quantity may be large enough to preclude
and/or route computation in a timely fashion. However, despite
lack of guarantees, it is a goal of the architecture to
efficient methods whereby sources can obtain the information
to compute desired routes [Footnote: The primary goal of policy
TOS routing is to compute a route that satisfies a set of
requirements, and these requirements take precedence over optimality
In other words, even if a routing domain that participates in SDR
NR has sufficient information to compute a route, given a
set of requirements, the architecture does not guarantee that
computed route is optimal.].
Essential to SDR is the assumption that the routes installed
demand will be used sparingly. The architecture assumes that at
given moment the set of all source-demand routes installed in
internet forms a small fraction of the total number of source-
routes that can potentially be installed by all the routing domains
It is an assumption of the architecture that the number of
installed in a BR by the SDR component should be on the order of
N (where N is the total number of routing domains in the Internet),
so that the scaling properties of the SDR component are
with the scaling properties of the NR component. The NR
achieves this property as a result of hierarchy
Note that the above requirement does not imply that only a
domains can participate in SDR, or that routes installed by the
component must have short life times. What the requirement
imply, is that the product of the number of routes specified
domains that participate in SDR, times the average SDR-route
time, is bounded. For example, the architecture allows either
small number of SDR routes with relatively long average life times
or a large number of SDR routes with relatively short average
times. But the architecture clearly prohibits a large number of
routes with relatively long average life times. The number of
routes is a function of the number of domains using SDR routes
the number of routes used per source domain
In summary, SDR is well suited for traffic that (1) is not widely
used enough (or is not sufficiently predictable or steady) to
computation and maintenance by the NR component, and (2)
duration is significantly longer than the time it takes to
the route installation procedure
Estrin, Rekhter & Hotz [Page 24]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
The architecture does not require all domains in the Internet
participate in SDR. Therefore, issues of scalability (with
to the size of the Internet) become less crucial (though
important) to the SDR component. Instead, the primary focus of
SDR component is shifted towards the ability to compute routes
satisfy specialized requirements, where we assume that the
number of domains requiring special routes simultaneously through
same part of the network is small relative to the total population
4.1 Path Vector vs. Link State for
It is feasible to use either a distance vector or link state
of route computation along with source routing. One could imagine
for instance, a protocol like BGP in which the source uses the
AD path information it receives in routing updates to create a
route. Such a protocol could address some of the
identified with distance vector, hop-by-hop designs. However, we
against further discussion of such a protocol because there is
to gain by using source routing without also using a link
scheme. The power of source routing, in the context of inter-
policy routing, is in giving the source control over the
route. This goal cannot be realized fully when intermediate
control which legal routes are advertised to neighbors, and
to a source
In other words, intermediate nodes should be able to preclude the
of a route by expressing a transit policy, but if a route is
precluded (i.e., is legal according to all ADs in the route),
route should be made available to the source independent of
intermediate domain's preferences for how its own traffic flows
Therefore, the SDR component employs an IDPR-like architecture
which link-state style updates are distributed with explicit
terms included in each update along with the advertising node'
connectivity
4.2 Distribution of Routing
By using a hop-by-hop NR component based on PV to complement
source-routing SDR component, we have alleviated the pressure
aggregate SDR forwarding information; the large percentage of inter
domain traffic carried, simultaneously, by any particular
router will be forwarded using aggregated NR forwarding information
However, the use of NR does not address the other major
problem associated with SDR: that of distributing, storing,
computing over a complete domain-level topology map. In this
we describe promising opportunities for improving the
properties of SDR routing information distribution, storage,
Estrin, Rekhter & Hotz [Page 25]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
computation
Note that we do not propose to solve this problem in the same
that we solve it for NR. A priori abstraction will not be
since different domains may require different methods of
the same routing information. For example, if we aggregate
information of domains that do not share the same policy and
characteristics (i.e., services), then outside of the aggregate,
those services that are offered by all domains in the aggregate
be advertised. In order to locate special routes, SDR only
aggregates when the component domains (and in turn the aggregate
advertise the required TOS and policy descriptions. When
required TOS or policy characteristics are not offered by
aggregate, full information about the component domains is used
construct a route through those domains that do support
particular characteristics. Consequently, we need some other,
flexible, means of reducing the amount of information distributed
held. We address two issues in turn: distribution of
topology and policy information, and distribution of dynamic
information
4.2.1 Configured
Information about the existence of inter-domain links, and
maintained by domains, changes slowly over time. This is referred
as configured information. In the current IDPR
complete, global, configuration information is kept by a route
in each domain. Route servers (RS) are the entities that
source routes. On startup a RS can download the
database from a neighbor RS; as domains, inter-domain links,
policies change, the changes are flooded to a RS in each domain
We have not yet specified the exact mechanisms for
configured connectivity information for SDR. However, unlike
current IDPR specification, the SDR component will not flood
configured information globally. Several alternate methods
organizing and distributing information are under investigation
Configured information may be regularly distributed via an out-of
band channel, e.g., CD/ROM. In a similar vein, this
could be posted in several well-known locations for retrieval, e.g.,
via FTP. Between these "major" updates, aggregated collections
changes may be flooded globally. Moreover, limited flooding (e.g.,
by hop-count) could be used as appropriate to the "importance" of
change; while a policy change in a major backbone may still
flooded globally, a new inter-regional link may be flooded
within those regions, and information about an additional link to
non-transit domain may not be available until the next regularly
Estrin, Rekhter & Hotz [Page 26]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
scheduled "major" distribution
Changes that are not distributed as they occur will not
be discovered. However, a route server may learn
information by direct query of remote servers, or through
messages resulting from traffic sent along failed routes.
global flooding may be avoided by using some combination of
mechanisms
Even if an initial implementation uses a simple global flood, we
study the problem of structuring connectivity information such
it can be retrieved or distributed in a more selective manner,
still allowing sources to discover desired routes. For example,
imagine RSs requesting filtered information from each other. How
RSs should define filters that will get enough information to
special routes, while also effectively limiting the information,
an open question. Again, the question is how to
anticipate and describe what information is needed in advance
computing the route
The essential dilemma is that networks are not organized in a
geographical or topologically consistent manner (e.g., it is
effective to ask for all networks going east-west that are within
certain north-south region of the target), hence a source domain
not know what information it needs (or should ask for) until
searches for, and discovers, the actual path. Even with a
database, techniques are needed to structure
information so that the potential paths that are most likely to
useful are explored first, thereby reducing the time required
route computation
One promising approach organizes information using route
(partial paths) [Footnote: Route fragments were first suggested
Dave Clark and Noel Chiappa.]. Although the number of
fragments grows faster than the number of domains (at least O(N^2)),
we can selectively choose those that will be useful to
routes. In particular, for each stub domain, fragments would
constructed to several well-known backbones [Footnote:
fragments may be computed by a destination's route server and
made available via information service queries or global flooding
In addition, NR computed routes may be used as SDR route fragments.].
Among its benefits, this approach aggregates domain information in
manner useful for computing source-routes, and provides an index
namely the destination, which facilitates on-demand reference
retrieval of information pertinent to a particular route computation
At this point, it is not clear how route fragments will affect SDR'
ability to discover non-hierarchical routes
Estrin, Rekhter & Hotz [Page 27]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
4.2.2 Dynamic Status
Assuming a technique for global or partial distribution of
information, a second issue is whether, and how, to
dynamic status information (i.e., whether an inter-domain
is up or down).
In the current version of IDPR, dynamic status information is
globally in addition to configuration information. We propose
distribute status information based strictly on locality. First
dynamic information will be advertised within a small hop-
radius. This simple and low-overhead mechanism exploits
locality. In addition to flooding status updates to nearby nodes,
also want to provide more accurate route information for
distance communications that entails more than a few network hops
Reverse path update (RPU) is a mechanism for sending dynamic
information to nodes that are outside the k-hop radius used
updates, but that nevertheless would obtain better service (
failed setups) by having access to the dynamic information [Estrin
etal91].
RPU uses the existing active routes (represented by installed
state or by a cache of the most recent source routes sent via
node in question) as a hint for distribution of event notifications
Instead of reporting only the status of the route being used,
reports the status of the domain's other inter-domain connections
If source routing exhibits route locality, the source is more
to use other routes going through the node in question; in any
the overhead of the information about other links will be minimal
In this way, sources will receive status information from regions
the network through which they maintain active routes, even if
regions are more than k hops away. Using such a scheme, k could
small to maximize efficiency, and RPU could be used to reduce
incidence of failed routes resulting from inaccurate
information. This will be useful if long-path communication
route locality with respect to regions that are closer to
destination (and therefore outside the k hop radius of
information). In such situations, flooding information to the
of the long route would be inefficient because k would have to
equal to the length of the route, and in almost all cases,
percentage of nodes that would use the information
significantly with larger k
4.3 Source-Demand Route
SDR may be built either on top of the network layer supported by
NR component, or in parallel with it. SDR forwarding will
Estrin, Rekhter & Hotz [Page 28]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
supported via two techniques: loose source-routing and route setup
The first technique, loose source-routing, would allow the
of a packet to specify a sequence of domains that the packet
traverse on its path to a destination. Forwarding such a
within a domain, or even between domains within a confederation
would be left to intra-domain routing. This avoids per-
state and supports transaction traffic
The second technique, route setup, will be based on
developed for IDPR and described in [IDPR90]. It is well suited
conversations that persist significantly longer than a round-trip
time. The setup protocol defines packet formats and the
of route installation request packets (i.e, setup packets). When
source generates a setup packet, the first border router along
specified source route checks the setup request, and if accepted
installs routing information; this information includes a path ID
the previous and next hops, and whatever other accounting-
information the particular domain requires. The setup packet
passed on to the next BR in the domain-level source route, and
same procedure is carried out [Footnote: The setup packet may
forwarded optimistically, i.e., before checks are completed,
reduce latency.]. When the setup packet reaches the destination,
accept message is propagated back hop by hop, and each BR en
activates its routing information. Subsequent data packets
along the same path to the destination include a path ID in
packet. That path ID is used to locate the appropriate next-
information for each packet
Border routers that support both the NR and the SDR components,
be able to determine what forwarding mechanism to use. That is,
presented with a network layer PDU, such a BR should be able to
an unambiguous decision about whether forwarding of that PDU
be handled by the NR or the SDR component. Discrimination
are dependent on whether the new network layer introduced by the
component is built on top of, or in parallel with, the network
supported by the NR component. Once the discrimination is made
packets that have to be forwarded via routes installed by the
component are forwarded to the exit port associated with
particular Path ID in the packet header. Packets that have to
forwarded via routes installed by the NR component are forwarded
the exit port associated with the particular destination and Type
Service parameters (if present) in their packet headers
Next, we describe the primary differences between the IDPR
procedure previously specified, and the procedure we propose
develop for this hybrid architecture
Estrin, Rekhter & Hotz [Page 29]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
During route installation, if a BR on the path finds that
remainder of the indicated route from the BR to the destination
identical to the NR route from the BR to the destination, then the
can turn off the SDR route at that point and map it onto the
route. For this to occur, the specifications of the SDR route
completely match those of the NR route. In addition, the
forward route must be equivalent (i.e., the remaining hops to
destination).
Moreover, if the NR route changes during the course of an active
route, and the new NR route does not match the SDR route, then
SDR route must be installed for the remainder of the way to
destination. Consequently, when an SDR route is mapped onto an
route, the original setup packet must be saved. A packet
from a source to destination may therefore traverse both an SDR
an NR route segment; however, a packet will not traverse another
segment after traveling over an NR segment. However,
transient periods packets could traverse the wrong route
therefore this must be an optional and controllable feature
A source can also request notification if a previously-down link
node returns to operation some time after a requested route
fails. If a BR on the route discovers that the requested next-hop
is not available, the BR can add the source to a notification
and when the next-hop BR becomes reachable, a notification can
sent back to the source. This provides a means of flushing out
news when it is no longer true. For example, a domain might
to route through a secondary route when its preferred route fails
the notification mechanism would inform the source in a timely
when its preferred route is available again
A third option addresses adaptation after route installation.
packet forwarding along an active SDR route, if a BR finds that
SDR route has failed, it may redirect the traffic along an
NR route to the destination. This adaptation is allowed only if
of the NR route does not violate policy; for example, it may
a less desirable type of service. This is done only if the
selects the option at route setup time. It is also up to the
whether it is to be notified of such actions
When a SDR route does fail, the detecting BR sends notification
the source(s) of the active routes that are affected. Optionally
the detecting BR may include additional information about the
of other BRs in the same domain. In particular, the BR can
its domain's most recent "update" indicating that domain's inter
domain links and policy. This can be helpful to the extent there
communication locality; i.e., if alternative routes might be
that traverse the domain in question, but avoid the failed BR
Estrin, Rekhter & Hotz [Page 30]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
In summary, when a route is first installed, the source has
options (which are represented by flags in the route setup packet):
1. If an NR route is available that satisfies all local
and TOS, then use it. Otherwise...
2. Indicate whether the source wants to allow the setup
default to a NR route if the SDR route setup fails
3. Request notification of mapping to a NR route
4. Request additional configured information on failure
5. Request addition to a notification list for
re-availability
6. Allow data packets to be rerouted to a NR route when
happens after setup (so long as no policy is violated).
7. Request notification of a reroute of data packets
8. Request additional configured information on failure
when the route is active
9. Request addition to a notification list if an active
fails
Estrin, Rekhter & Hotz [Page 31]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
5.0 The Unified
In addition to further evaluation and implementation of the
architecture, future research must investigate opportunities
increased unification of the two components of our architecture.
are investigating several opportunities for additional commonality
1. Routing Information Base
Perhaps a single RIB could be shared by both NR and SDR
NR routes can be represented as a directed graph
with flags (on the nodes or links) corresponding to
generic transit constraints. SDR requires that this
be augmented by links with non-generic policies that
been discovered and maintained for computing special routes
in addition, special policy flags may be added to
already maintained by the NR component
2. Information Distribution
The NR path vectors could include address(es) of
for SDR-update information for each AD (or confederation)
assist the SDR component in retrieving selective
on demand. For domains with minimal policies, where the
required for policy information is smaller than the
required for a repository address (e.g., if the policies
the domain listed are all wildcard), the NR path vectors
include a flag to that effect
3. Packet Forwarding
We should consider replacing the current IDPR-style
layer (which contains a global path identifier used
forwarding data packets to the next policy gateway on
IDPR route) with a standard header (e.g., IP or CLNP),
augmented with some option fields. This would unify
packet header parsing and forwarding functions for SDR and NR
and possibly eliminate some encapsulation overhead
4. Reachability Information
Currently IDRP distributes network reachability
within updates, whereas IDPR only distributes
reachability information. IDPR uses a domain name
function to map network numbers to domain numbers; the
is needed to make the routing decision. We should
obtaining the network reachability and domain information
a unified manner
Estrin, Rekhter & Hotz [Page 32]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
5.1 Applicability to Various Network Layer
The proposed architecture is designed to accommodate such
network layer protocols as IP ([Postel81]), CLNP ([ISO-473-88]),
ST-II ([ST2-90]). In addition, we intend for this architecture
support future network layer mechanisms, e.g., Clark and Jacobson'
proposal or Braden and Casner's Integrated Services IP. However
principal we can not make sweeping guarantees in advance of
mechanisms themselves. In any case, not all of the
protocols will be able to utilize all of the capabilities provided
the architecture. For instance, unless the increase in the number
different types of services offered is matched by the ability of
particular network layer protocol to unambiguously express
for such different types of services, the capability of
architecture to support routing in the presence of a large number
different types of service is largely academic. That is, not
components of the architecture will have equal importance
different network layer protocols. On the other hand,
architecture is designed to serve the future global
environment. The extensive research and development
underway to implement and evaluate network mechanisms for
types of service suggests that future networks will offer
services
One of the fundamental issues in the proposed architecture is
issue of single versus multiple protocols. The architecture does
make any assumptions about whether each network layer is going
have its own inter-domain routing protocol, or a single inter-
routing protocol will be able to cover multiple network
[Footnote: Similar issue already arose with respect to the intra
domain routing protocol, which generated sufficient amount
controversy within the Internet community. It is our opinion,
the issue of single versus multiple protocols is more complex for
inter-domain routing than for the intra-domain routing.]. That is
the proposed architecture can be realized either by a single inter
domain routing protocol covering multiple network layers, or
multiple inter-domain routing protocols (with the same architecture
tailored to a specific network layer [Footnote: If the
protocol strategy is adopted, then it is likely that IDRP will
used as a base for the NR component. Since presently IDRP
targeted towards CLNP, further work is needed to augment it
support IP and ST-II. If the multiple protocol strategy is adopted
then it is likely that BGP will be used as a base for the
component for IP, and IDRP will be used as a base for the
component for CLNP. Further work is needed to specify protocol
support for the NR component for ST-II. Additional work may
needed to specify new features that may be added to BGP.].
Estrin, Rekhter & Hotz [Page 33]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
5.2
The proposed architecture is not intended for full deployment in
short term future. We are proposing this architecture as a
towards which we can begin guiding our operational and
investment over the next 5 years
At the same time, the architecture does not require
overhaul of the existing Internet. The NR component may be phased
gradually. For example, the NR component for IP may be phased in
replacing existing EGP-2 routing with BGP routing. Once the
component is in place, it can be augmented by the facilities
by the SDR component
The most critical components of the architecture needed to
SDR include route installation and packet forwarding in the
that support SDR. Participation as a transit routing domain
that the domain can distribute local configuration information (LCI
and that some of its routers implement the route installation
route management protocols. Participation as a source requires
the domain have access to a RS to compute routes, and that the
domain has a router that implements the route installation and
management protocols. In addition, a network management entity
describe local configuration information and send it to the
repository(ies). A collection and distribution mechanism must be
in place, even if it is centralized
Estrin, Rekhter & Hotz [Page 34]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
6.0 Conclusions and Future
In summary, the proposed architecture combines hop-by-hop path
vector, and source-routed link-state, protocols, and uses each
that which it is best suited: NR uses PV and multiple, flexible
levels of confederations to support efficient routing of
packets over generic routes; SDR uses LS computation over a
of configured and dynamic information to route special traffic
special routes. In the past, the community has viewed these two
mutually exclusive; to the contrary, they are quite complementary
it is fortunate that we, as a community, have pursued both paths
parallel. Together these two approaches will flexibly
efficiently support TOS and policy routing in very large
internets
It is now time to consider the issues associated with combining
integrating the two. We must go back and look at both
and their constituent protocols, eliminate redundancies, fill in
holes, and provide seamless integration
7.0
We would like to thank Hans-Werner Braun (San Diego
Center), Lee Breslau (USC), Scott Brim (Cornell University), Tony
(cisco Systems), Doug Montgomery (NIST), Tassos Nakassis (NIST),
Martha Steenstrup (BBN), and Daniel Zappala (USC) for their
on a previous draft
Estrin, Rekhter & Hotz [Page 35]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
8.0
[ANSI 87-150R] "Intermediate System to Intermediate System Intra
Domain Routing Exchange Protocol", ANSI X3S3.3/87-150R
[BGP 91] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3
(BGP-3)", RFC 1267, cisco Systems, T.J. Watson Research Center,
Corp., October 1991.
[Breslau-Estrin 91] Breslau, L., and D. Estrin, "Design
Evaluation of Inter-Domain Policy Routing Protocols", To appear
Journal of Internetworking Research and Experience, 1991. (
version appeared in ACM Sigcomm 1990.)
[Clark 90] Clark, D., "Policy Routing in Internetworks", Journal
Internetworking Research and Experience, Vol. 1, pp. 35-52, 1990.
[Dijkstra 59] Dijkstra, E., "A Note on Two Problems in
with Graphs", Numer. Math., Vol. 1, 1959, pp. 269-271.
[ECMA89] "Inter-Domain Intermediate Systems Routing",
Technical Report ECMA TR/ISR, ECMA/TC32-TG 10/89/56, May 1989.
[EGP] Rosen, E., "Exterior Gateway Protocol (EGP)", RFC 827, BBN
October 1982.
[Estrin 89] Estrin, D., "Policy Requirements for
Administrative Domain Routing", RFC 1125, USC Computer
Department, November 1989.
[Estrin-etal91] Estrin, D., Breslau, L., and L. Zhang, "
Mechanisms for Adaptive Routing in Global Multimedia Internets",
University of Southern California, Computer Science
Technical Report, CS-SYS-91-04, November 1991.
[Hedrick 88] Hedrick, C., "Routing Information Protocol", RFC 1058,
Rutgers University, June 1988.
[Honig 90] Honig, J., Katz, D., Mathis, M., Rekhter, Y., and J. Yu
"Application of the Border Gateway Protocol in the Internet",
1164, Cornell Univ. Theory Center, Merit/NSFNET,
Supercomputing Center, T.J. Watson Research Center, IBM Corp.,
1990.
[IDPR90] Steenstrup, M., "Inter-Domain Policy Routing
Specification and Usage: Version 1", Work in Progress, February 1991.
Estrin, Rekhter & Hotz [Page 36]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
[IDRP91] "Intermediate System to Intermediate System Inter-
Routeing Exchange Protocol", ISO/IEC/ JTC1/SC6 CD10747.
[ISIS10589] "Information Processing Systems - Telecommunications
Information Exchange between Systems - Intermediate System
Intermediate System Intra-Domain Routing Exchange Protocol for use
Conjunction with the protocol for providing the Connectionless-
Network Service (ISO 8473)", ISO/IEC 10589.
[ISO-473 88] "Protocol for providing the connectionless-mode
service", ISO 8473, 1988.
[Jaffee 82] Jaffee, J., and F. Moss, "A Responsive
Routing Algorithm for Computer Networks", IEEE Transactions
Communications, July 1982.
[Little 89] Little, M., "Goals and Functional Requirements
Inter-Autonomous System Routing", RFC 1126, SAIC, October 1989.
[Oran 89] Oran, D., "Expert's Paper: The Relationship
Addressing and Routeing", ISO/JTC1/SC6/WG2, 1989.
[OSPF] Moy, J., "The Open Shortest Path First (OSPF) Specification",
RFC 1131, Proteon, October 1989.
[Postel 81] Postel, J., "Internet Protocol", RFC 791, DARPA
September 1981.
[Rekhter 91] Rekhter, Y., "IDRP protocol analysis:
complexity", IBM Research Report RC17298(#76515), October 1991.
[Shin87] Shin, K., and M. Chen, "Performance Analysis of
Routing Strategies Free of Ping-Pong-Type Looping", IEEE
on Computers, February 1987.
[ST2-90] Topolcic, C., "Experimental Internet Stream Protocol
version 2 (ST II)", RFC 1190, CIP Working Group, October 1990.
[Zaumen 91] Zaumen, W., and J. Garcia-Luna-Aceves, "Dynamics of
State and Loop-free Distance-Vector Routing Algorithms", ACM
'91, Zurich, Switzerland, September 1991.
[Zhang 91] Zhang, L., "Virtual Clock: A New Traffic Control
for Packet Switching Networks".
Estrin, Rekhter & Hotz [Page 37]
RFC 1322 A Unified Approach to Inter-Domain Routing May 1992
Security
Security issues are not discussed in this memo
Authors'
Deborah
University of Southern
Computer Science Department, MC 0782
Los Angeles, California 90089-0782
Phone: (310) 740-4524
EMail: estrin@usc.
Yakov
IBM T.J. Watson Research
P.O. Box 218
Yorktown Heights, New York 10598
Phone: (914) 945-3896
EMail: yakov@ibm.
Steven
University of Southern
Computer Science Department, MC 0782
Los Angeles, California 90089-0782
Phone: (310) 822-1511
EMail: hotz@usc.
Estrin, Rekhter & Hotz [Page 38]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
