Request for Comments: 1322 USC
Y. Rekhter
IBM
S. Hotz
USC
May 1992
A Unified Approach to Inter-Domain Routing
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard. Distribution of this memo is
unlimited.
Abstract
This memo is an informational RFCwhich outlines one potential
approach for inter-domain routing in future global internets. The
focus is on scalability to very large networks and functionality, as
well as scalability, to support routing in an environment of
heterogeneous services, requirements, and route selection criteria.
Note: The work of D. Estrin and S. Hotz was supported by the National
Science Foundation under contract number NCR-9011279, with matching
funds from GTE Laboratories. The work of Y. Rekhter was supported by
the Defense Advanced Research Projects Agency, under contract
DABT63-91-C-0019. Views and conclusions expressed in this paper are
not necessarily those of the Defense Advanced Research Projects
Agency and National Science Foundation.
1.0 Motivation
The global internet can be modeled as a collection of hosts
interconnected via transmission and switching facilities. Control
over the collection of hosts and the transmission and switching
facilities that compose the networking resources of the global
internet is not homogeneous, but is distributed among multiple
administrative authorities. Resources under control of a single
administration form a domain. In order to support each domain's
autonomy and heterogeneity, routing consists of two distinct
components: intra-domain (interior) routing, and inter-domain
(exterior) routing. Intra-domain routing provides support for data
communication between hosts where data traverses transmission and
switching facilities within a single domain. Inter-domain routing
provides support for data communication between hosts where data
traverses transmission and switching facilities spanning multiple
domains. The entities that forward packets across domain boundaries
are called border routers (BRs). The entities responsible for
exchanging inter-domain routing information are called route servers
(RSs). RSs and BRs may be colocated.
As the global internet grows, both in size and in the diversity of
routing requirements, providing inter-domain routing that can
accommodate both of these factors becomes more and more crucial. The
number and diversity of routing requirements is increasing due to:
(a) transit restrictions imposed by source, destination, and transit
networks, (b) different types of services offered and required, and
(c) the presence of multiple carriers with different charging
schemes. The combinatorial explosion of mixing and matching these
different criteria weighs heavily on the mechanisms provided by
conventional hop-by-hop routing architectures ([ISIS10589, OSPF,
Hedrick88, EGP]).
Current work on inter-domain routing within the Internet community
has diverged in two directions: one is best represented by the Border
Gateway Protocol (BGP)/Inter-Domain Routeing Protocol (IDRP)
architectures ([BGP91, Honig90, IDRP91]), and another is best
represented by the Inter-Domain Policy Routing (IDPR) architecture
([IDPR90, Clark90]). In this paper we suggest that the two
architectures are quite complementary and should not be considered
mutually exclusive.
We expect that over the next 5 to 10 years, the types of services
available will continue to evolve and that specialized facilities
will be employed to provide new services. While the number and
variety of routes provided by hop-by-hop routing architectures with
type of service (TOS) support (i.e., multiple, tagged routes) may be
sufficient for a large percentage of traffic, it is important that
mechanisms be in place to support efficient routing of specialized
traffic types via special routes. Examples of special routes are:
(1) a route that travels through one or more transit domains that
discriminate according to the source domain, (2) a route that travels
through transit domains that support a service that is not widely or
regularly used. We refer to all other routes as generic.
Our desire to support special routes efficiently led us to
investigate the dynamic installation of routes ([Breslau-Estrin91,
Clark90, IDPR90]). In a previous paper ([Breslau-Estrin91]), we
evaluated the algorithmic design choices for inter-domain policy
routing with specific attention to accommodating source-specific and
other "special" routes. The conclusion was that special routes are
best supported with source-routing and extended link-state
algorithms; we refer to this approach as source-demand routing
[Footnote: The Inter-Domain Policy Routing (IDPR) architecture uses
these techniques.]. However, a source-demand routing architecture,
used as the only means of inter-domain routing, has scaling problems
because it does not lend itself to general hierarchical clustering
and aggregation of routing and forwarding information. For example,
even if a particular route from an intermediate transit domain X, to
a destination domain Y is shared by 1,000 source-domains, IDPR
requires that state for each of the 1,000 routes be setup and
maintained in the transit border routers between X and Y. In
contrast, an alternative approach to inter-domain routing, based on
hop-by-hop routing and a distributed route-computation algorithm
(described later), provides extensive support for aggregation and
abstraction of reachability, topology, and forwarding information.
The Border Gateway Protocol (BGP) and Inter-Domain Routeing Protocol
(IDRP) use these techniques ([BGP91, IDRP91]). While the BGP/IDRP
architecture is capable of accommodating very large numbers of
datagram networks, it does not provide support for specialized
routing requirements as flexibly and efficiently as IDPR-style
routing.
1.1 Overview of the Unified Architecture
We want to support special routes and we want to exploit aggregation
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 component
computes and installs routes that are shared by a significant number
of sources. These generic routes are commonly used and warrant wide
propagation, consequently, aggregation of routing information is
critical. The SDR component computes and installs specialized routes
that are not shared by enough sources to justify computation by NR
[Footnote: Routes that are only needed sporadically (i.e., the demand
for them is not continuous or otherwise predictable) are also
candidates for SDR.]. The potentially large number of different
specialized routes, combined with their sparse utilization, make them
too costly to support with the NR mechanism.
A useful analogy to this approach is the manufacturing of consumer
products. When predictable patterns of demand exist, firms produce
objects and sell them as "off the shelf" consumer goods. In our
architecture NR provides off-the-shelf routes. If demand is not
predictable, then firms accept special orders and produce what is
demanded at the time it is needed. In addition, if a part is so
specialized that only a single or small number of consumers need it,
the consumer may repeatedly special order the part, even if it is
needed in a predictable manner, because the consumer does not
represent a big enough market for the producer to bother managing the
item as part of its regular production. SDR provides such special
order, on-demand routes.
By combining NR and SDR routing we propose to support inter-domain
routing in internets of practically-unlimited size, while at the same
time providing efficient support for specialized routing
requirements.
The development of this architecture does assume that routing
requirements will be diverse and that special routes will be needed.
On the other hand, the architecture does not depend on assumptions
about the particular types of routes demanded or on the distribution
of that demand. Routing will adapt naturally over time to changing
traffic patterns and new services by shifting computation and
installation of particular types of routes between the two components
of the hybrid architecture [Footnote: Before continuing with our
explanation of this architecture, we wish to state up front that
supporting highly specialized routes for all source-destination pairs
in an internet, or even anything close to that number, is not
feasible in any routing architecture that we can foresee. In other
words, we do not believe that any foreseeable routing architecture
can support unconstrained proliferation of user requirements and
network services. At the same time, this is not necessarily a
problem. The capabilities of the architecture may in fact exceed the
requirements of the users. Moreover, some of the requirements that
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 unrealistic
expectations.].
While the packet forwarding functions of the NR and SDR components
have little or no coupling with each other, the connectivity
information exchange mechanism of the SDR component relies on
services provided by the NR component.
1.2 Outline
The remainder of this report is organized as follows. Section 2
outlines the requirements and priorities that guide the design of the
NR and SDR components. Sections 3 and 4 describe the NR and SDR
design choices, respectively, in light of these requirements.
Section 5 describes protocol support for the unified architecture and
briefly discusses transition issues. We conclude with a brief
summary.
2.0 Architectural Requirements and Priorities
In order to justify our design choices for a scalable inter-domain
routing architecture, we must articulate our evaluation criteria and
priorities. This section defines complexity, abstraction, policy,
and type of service requirements.
2.1 Complexity
Inter-domain routing complexity must be evaluated on the basis of the
following performance metrics: (1) storage overhead, (2)
computational overhead, and (3) message overhead. This evaluation is
essential to determining the scalability of any architecture.
2.1.1 Storage Overhead
The storage overhead of an entity that participates in inter-domain
routing comes from two sources: Routing Information Base (RIB), and
Forwarding Information Base (FIB) overhead. The RIB contains the
routing information that entities exchange via the inter-domain
routing protocol; the RIB is the input to the route computation. The
FIB contains the information that the entities use to forward the
inter-domain traffic; the FIB is the output of the route computation.
For an acceptable level of storage overhead, the amount of
information in both FIBs and RIBs should grow significantly slower
than linearly (e.g., close to logarithmically) with the total number
of domains in an internet. To satisfy this requirement with respect
to the RIB, the architecture must provide mechanisms for either
aggregation and abstraction of routing and forwarding information, or
retrieval of a subset of this information on demand. To satisfy this
requirement with respect to the FIB, the architecture must provide
mechanisms for either aggregation of the forwarding information (for
the NR computed routes), or dynamic installation/tear down of this
information (for the SDR computed routes).
Besides being an intrinsically important evaluation metric, storage
overhead has a direct impact on computational and bandwidth
complexity. Unless the computational complexity is fixed (and
independent of the total number of domains), the storage overhead has
direct impact on the computational complexity of the architecture
since the routing information is used as an input to route
computation. Moreover, unless the architecture employs incremental
updates, where only changes to the routing information are
propagated, the storage overhead has direct impact on the bandwidth
overhead of the architecture since the exchange of routing
information constitutes most of the bandwidth overhead.
2.1.2 Computational Overhead
The NR component will rely primarily on precomputation of routes. If
inter-domain routing is ubiquitous, then the precomputed routes
include all reachable destinations. Even if policy constraints make
fully ubiquitous routing impossible, the precomputed routes are
likely to cover a very large percentage of all reachable
destinations. Therefore the complexity of this computation must be
as small as possible. Specifically, it is highly desirable that the
architecture would employ some form of partial computation, where
changes in topology would require less than complete recomputation.
Even if complete recomputation is necessary, its complexity should be
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 that
SDR is expected to compute routes to a smaller number of destinations
than is NR (although SDR route computation may be invoked more
frequently).
Under no circumstances is computational complexity allowed to become
exponential (for either the NR or SDR component).
2.1.3 Bandwidth Overhead
The bandwidth consumed by routing information distribution should be
limited. However, the possible use of data compression techniques
and the increasing speed of network links make this less important
than route computation and storage overhead. Bandwidth overhead may
be further contained by using incremental (rather than complete)
exchange of routing information.
While storage and bandwidth overhead may be interrelated, if
incremental updates are used then bandwidth overhead is negligible in
the steady state (no changes in topology), and is independent of the
storage overhead. In other words, use of incremental updates
constrains the bandwidth overhead to the dynamics of the internet.
Therefore, improvements in stability of the physical links, combined
with techniques to dampen the effect of topological instabilities,
will make the bandwidth overhead even less important.
2.2 Aggregation
Aggregation and abstraction of routing and forwarding information
provides a very powerful mechanism for satisfying storage,
computational, and bandwidth constraints. The ability to aggregate,
and subsequently abstract, routing and forwarding information is
essential to the scaling of the architecture [Footnote: While we can
not prove that there are no other ways to achieve scaling, we are not
aware of any mechanism other than clustering that allows information
aggregation/abstraction. Therefore, the rest of the paper assumes
that clustering is used for information aggregation/abstraction.].
This is especially true with respect to the NR component, since the
NR component must be capable of providing routes to all or almost all
reachable destinations.
At the same time, since preserving each domain's independence and
autonomy is one of the crucial requirements of inter-domain routing,
the architecture must strive for the maximum flexibility of its
aggregation scheme, i.e., impose as few preconditions, and as little
global coordination, as possible on the participating domains.
The Routing Information Base (RIB) carries three types of
information: (1) topology (i.e., the interconnections between domains
or groups of domains), (2) network layer reachability, and (3)
transit constraint. Aggregation of routing information should
provide a reduction of all three components. Aggregation of
forwarding information will follow from reachability information
aggregation.
Clustering (by forming routing domain confederations) serves the
following aggregation functions: (1) to hide parts of the actual
physical topology, thus abstracting topological information, (2) to
combine a set of reachable destination entities into a single entity
and reduce storage overhead, and (3) to express transit constraints
in terms of clusters, rather than individual domains.
As argued in [Breslau-Estrin91], the architecture must allow
confederations to be formed and changed without extensive
configuration and coordination; in particular, forming a
confederation should not require global coordination (such as that
required in ECMA ([ECMA89]). In addition, aggregation should not
require explicit designation of the relative placement of each domain
relative to another; i.e., domains or confederations of domains
should not be required to agree on a partial ordering (i.e., who is
above whom, etc.).
The architecture should allow different domains to use different
methods of aggregation and abstraction. For example, a research
collaborator at IBM might route to USC as a domain-level entity in
order to take advantage of some special TOS connectivity to, or even
through, USC. Whereas, someone else at Digital Equipment Corporation
might see information at the level of the California Educational
Institutions Confederation, and know only that USC is a member.
Alternatively, USC might see part of the internal structure within
the IBM Confederation (at the domain's level), whereas UCLA may route
based on the confederation of IBM domains as a whole.
Support for confederations should be flexible. Specifically, the
architecture should allow confederations to overlap without being
nested, i.e., a single domain, or a group of domains may be part of
more than one confederation. For example, USC may be part of the
California Educational Institutions Confederation and part of the US
R&D Institutions Confederation; one is not a subset of the other.
Another example: T.J. Watson Research Center might be part of
NYSERNET Confederation and part of IBM-R&D-US Confederation. While
the above examples describe cases where overlap consists of a single
domain, there may be other cases where multiple domains overlap. As
an example consider the set of domains that form the IBM
Confederation, and another set of domains that form the DEC
Confederation. Within IBM there is a domain IBM-Research, and
similarly within DEC there is a domain DEC-Research. Both of these
domains could be involved in some collaborative effort, and thus have
established direct links. The architecture should allow restricted
use of these direct links, so that other domains within the IBM
Confederation would not be able to use it to talk to other domains
within the DEC Confederation. A similar example exists when a
multinational corporation forms a confederation, and the individual
branches within each country also belong to their respective country
confederations. The corporation may need to protect itself from
being used as an inter-country transit domain (due to internal, or
international, policy). All of the above examples illustrate a
situation where confederations overlap, and it is necessary to
control the traffic traversing the overlapping resources.
While flexible aggregation should be accommodated in any inter-domain
architecture, the extent to which this feature is exploited will have
direct a effect on the scalability associated with aggregation. At
the same time, the exploitation of this feature depends on the way
addresses are assigned. Specifically, scaling associated with
forwarding information depends heavily on the assumption that there
will be general correspondence between the hierarchy of address
registration authorities, and the way routing domains and routing
domain confederations are organized (see Section 2.6).
2.3 Routing Policies
Routing policies that the architecture must support may be broadly
classified into transit policies and route selection policies
[Breslau-Estrin 91, Estrin89].
Restrictions imposed via transit policies may be based on a variety
of factors. The architecture should be able to support restrictions
based on the source, destination, type of services (TOS), user class
identification (UCI), charging, and path [Estrin89 , Little89]. The
architecture must allow expression of transit policies on all routes,
both NR and SDR. Even if NR routes are widely used and have fewer
source or destination restrictions, NR routes may have some transit
qualifiers (e.g., TOS, charging, or user-class restriction). If the
most widely-usable route to a destination has policy qualifiers, it
should be advertiseable by NR and the transit constraints should be
explicit.
Route selection policies enable each domain to select a particular
route among multiple routes to the same destination. To maintain
maximum autonomy and independence between domains, the architecture
must support heterogeneous route selection policies, where each
domain can establish its own criteria for selecting routes. This
argument was made earlier with respect to source route selection
([IDPR90, Clark90, Breslau-Estrin91]). In addition, each
intermediate transit domain must have the flexibility to apply its
own selection criteria to the routes made available to it by its
neighbors. This is really just a corollary to the above; i.e., if we
allow route selection policy to be expressed for NR routes, we can
not assume all domains will apply the same policy. The support for
dissimilar route selection policies is one of the key factors that
distinguish inter-domain routing from intra-domain routing ([ECMA89,
Estrin89]). However, it is a non-goal of the architecture to support
all possible route selection policies. For more on unsupported route
selection policies see Section 2.3.2 below.
2.3.1 Routing Information Hiding
The architecture should not require all domains within an internet to
reveal their connectivity and transit constraints to each other.
Domains should be able to enforce their transit policies while
limiting the advertisement of their policy and connectivity
information as much as possible; such advertisement will be driven by
a "need to know" criteria. Moreover, advertising a transit policy to
domains that can not use this policy will increase the amount of
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 to
obtain this information.
2.3.2 Policies Not Supported
In this and previous papers we have argued that a global inter-domain
routing architecture should support a wide range of policies. In
this section we identify several types of policy that we explicitly
do not propose to support. In general our reasoning is pragmatic; we
think such policy types are either very expensive in terms of
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 that
assigns a non-negative integer to a route, denoting the degree
of preference. Route selection applies this function to all
feasible routes to a given destination, and selects the route
with the highest value. To provide a stable environment, the
preference function should not use as an input the status and
attributes of other routes (either to the same or to a
different destination).
2. Transit policies contingent on external behavior.
To provide a stable environment, the domain's transit policies
can not be automatically affected by any information external
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 modified
in response to information about performance characteristics of
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-sensitive
routing for generic routes. However, it is possible that some
types of service may employ load information to select among
alternate SDR routes.
4. Very large number of simultaneous SDR routes.
It is a non-goal of the architecture to support a very large
number of simultaneous SDR routes through any single router.
Specifically, the FIB storage overhead associated with SDR
routes must be comparable with that of NR routes, and should
always be bound by the complexity requirements outlined earlier
[Foonote: As discussed earlier, theoretically the state overhead
could grow O(N^2) with the number of domains in an internet.
However, there is no evidence or intuition to suggest that
this will be a limiting factor on the wide utilization of SDR,
provided that NR is available to handle generic routes.].
2.4 Support for TOS Routing
Throughout this document we refer to support for type of service
(TOS) routing. There is a great deal of research and development
activity currently underway to explore network architectures and
protocols for high-bandwidth, multimedia traffic. Some of this
traffic is delay sensitive, while some requires high throughput. It
is unrealistic to assume that a single communication fabric will be
deployed homogeneously across the internet (including all
metropolitan, regional, and backbone networks) that will support all
types of traffic uniformly. To support diverse traffic requirements
in a heterogeneous environment, various resource management
mechanisms will be used in different parts of the global internet
(e.g., resource reservation of various kinds) [ST2-90, Zhang91].
In this context, it is the job of routing protocols to locate routes
that can potentially support the particular TOS requested. It is
explicitly not the job of the general routing protocols to locate
routes that are guaranteed to have resources available at the
particular time of the route request. In other words, it is not
practical to assume that instantaneous resource availability will be
known at all remote points in the global internet. Rather, once a
TOS route has been identified, an application requiring particular
service guarantees will attempt to use the route (e.g., using an
explicit setup message if so required by the underlying networks).
In Section 4 we describe additional services that may be provided to
support more adaptive route selection for special TOS [Footnote:
Adaptive route selection implies adaptability only during the route
selection process. Once a route is selected, it is not going to be a
subject to any adaptations, except when it becomes infeasible.].
2.5 Commonality between Routing Components
While it is acceptable for the NR and SDR components to be
dissimilar, we do recognize that such a solution is less desirable --
all other things being equal. In theory, there are advantages in
having the NR and SDR components use similar algorithms and
mechanisms. Code and databases could be shared and the architecture
would be more manageable and comprehensible. On the other hand,
there may be some benefit (e.g., robustness) if the two parts of the
architecture are heterogeneous, and not completely inter-dependent.
In Section 5 we list several areas in which opportunities for
increased commonality (unification) will be exploited.
2.6 Interaction with Addressing
The proposed architecture should be applicable to various addressing
schemes. There are no specific assumptions about a particular
address structure, except that this structure should facilitate
information aggregation, without forcing rigid hierarchical routing.
Beyond this requirement, most of the proposals for extending the IP
address space, for example, can be used in conjunction with our
architecture. But our architecture itself does not provide (or
impose) a particular solution to the addressing problem.
3.0 Design Choices for Node Routing (NR)
This section addresses the design choices made for the NR component
in light of the above architectural requirements and priorities. All
of our discussion of NR assumes hop-by-hop routing. Source routing
is subject to different constraints and is used for the complementary
SDR component.
3.1 Overview of NR
The NR component is designed and optimized for an environment where a
large percentage of packets will travel over routes that can be
shared by multiple sources and that have predictable traffic
patterns. The efficiency of the NR component improves when a number
of source domains share a particular route from some intermediate
point to a destination. Moreover, NR is best suited to provide
routing for inter-domain data traffic that is either steady enough to
justify the existence of a route, or predictable, so that a route may
be installed when needed (based on the prediction, rather than on the
actual traffic). Such routes lend themselves to distributed route
computation and installation procedures.
Routes that are installed in routers, and information that was used
by the routers to compute these routes, reflect the known operational
state of the routing facilities (as well as the policy constraints)
at the time of route computation. Route computation is driven by
changes in either operational status of routing facilities or policy
constraints. The NR component supports route computation that is
dynamically adaptable to both changes in topology and policy. The NR
component allows time-dependent selection or deletion of routes.
However, time dependency must be predictable (e.g., advertising a
certain route only after business hours) and routes should be used
widely enough to warrant inclusion in NR.
The proposed architecture assumes that most of the inter-domain
conversations will be forwarded via routes computed and installed by
the NR component.
Moreover, the exchange of routing information necessary for the SDR
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 internet
implement and participate in NR. Since scalability (with respect to
the size of the internet) is one of the fundamental requirements for
the NR component, it must provide multiple mechanisms with various
degrees of sophistication for information aggregation and
abstraction.
The potential reduction of routing and forwarding information depends
very heavily on the way addresses are assigned and how domains and
their confederations are structured. "If there is no correspondence
between the address registration hierarchy and the organisation of
routeing domains, then ... each and every routeing domain in the OSIE
would need a table entry potentially at every boundary IS of every
other routeing domain" ([Oran89]). Indeed, scaling in the NR
component is almost entirely predicated on the assumption that there
will be general correspondence between the hierarchy of address
assignment authorities and the way routing domains are organised, so
that the efficient and frequent aggregation of routing and forwarding
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 the
flexibility of the scheme for information aggregation and
abstraction, and on the preconditions that such a scheme imposes.
Moreover, given a flexible architecture, the operational efficiency
(scalability) of the global internet, or portions thereof, will
depend on tradeoffs made between flexibility and aggregation.
While the NR component is optimized to satisfy the common case
routing requirements for an extremely large population of users, this
does not imply that routes produced by the NR component would not be
used for different types of service (TOS). To the contrary, if a TOS
becomes sufficiently widely used (i.e., by multiple domains and
predictably over time), then it may warrant being computed by the NR
component.
To summarize, the NR component is best suited to provide routes that
are used by more than a single domain. That is, the efficiency of
the NR component improves when a number of source domains share a
particular route from some intermediate point to a destination.
Moreover, NR is best suited to provide routing for inter-domain data
traffic that is either steady enough to justify the existence of a
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 NR
Given that a NR component based on hop-by-hop routing is needed to
provide scalable, efficient inter-domain routing, the remainder of
this section considers the fundamental design choices for the NR
routing algorithm.
Typically the debate surrounding routing algorithms focuses on link
state and distance vector protocols. However, simple distance vector
protocols (i.e., Routing Information Protocol [Hedrick88]), do not
scale because of convergence problems. Improved distance vector
protocols, such as those discussed in [Jaffee82, Zaumen91, Shin87],
have been developed to address this issue using synchronization
mechanisms or additional path information. In the case of inter-
domain routing, having additional path information is essential to
supporting policy. Therefore, the algorithms we consider for NR are
link state and one we call path vector (PV). Whereas the
characteristics of link state algorithms are generally understood
(for example, [Zaumen 91]), we must digress from our evaluation
discussion to describe briefly the newer concept of the PV algorithm
[Footnote: We assume that some form of SPF algorithm will be used to
compute paths over the topology database when LS algorithms are used
[Dijkstra59, OSPF]].
3.2.1 Path Vector Protocol Overview
The Border Gateway Protocol (BGP) (see [BGP91]) and the Inter Domain
Routing Protocol (IDRP) (see [IDRP91]) are examples of path vector
(PV) protocols [Footnote: BGP is an inter-autonomous system routing
protocol for TCP/IP internets. IDRP is an OSI inter-domain routing
protocol that is being progressed toward standardization within ISO.
Since in terms of functionality BGP represents a proper subset of
IDRP, for the rest of the paper we will only consider IDRP.].
The routing algorithm employed by PV bears a certain resemblance to
the traditional Bellman-Ford routing algorithm in the sense that each
border router advertises the destinations it can reach to its
neighboring BRs. However,the PV routing algorithm augments the
advertisement of reachable destinations with information that
describes various properties of the paths to these destinations.
This information is expressed in terms of path attributes. To
emphasize the tight coupling between the reachable destinations and
properties of the paths to these destinations, PV defines a route as
a pairing between a destination and the attributes of the path to
that destination. Thus the name, path-vector protocol, where a BR
receives from its neighboring BR a vector that contains paths to a
set of destinations [Footnote: The term "path-vector protocol" bears
an intentional similarity to the term "distance-vector protocol",
where a BR receives from each of its neighbors a vector that contains
distances to a set of destinations.]. The path, expressed in terms
of the domains (or confederations) traversed so far, is carried in a
special path attribute which records the sequence of routing domains
through which the reachability information has passed. Suppression
of routing loops is implemented via this special path attribute, in
contrast to LS and distance vector which use a globally-defined
monotonically-increasing metric for route selection [Shin87].
Because PV does not require all routing domains to have homogeneous
criteria (policies) for route selection, route selection policies
used by one routing domain are not necessarily known to other routing
domains. To maintain the maximum degree of autonomy and independence
between routing domains, each domain which participates in PV may
have its own view of what constitutes an optimal route. This view is
based solely on local route selection policies and the information
carried in the path attributes of a route. PV standardizes only the
results of the route selection procedure, while allowing the
selection policies that affect the route selection to be non-standard
[Footnote: This succinct observation is attributed to Ross Callon
(Digital Equipment Corporation).].
3.3 Complexity
Given the above description of PV algorithms, we can compare them to
LS algorithms in terms of the three complexity parameters defined
earlier.
3.3.1 Storage Overhead
Without any aggregation of routing information, and ignoring storage
overhead associated with transit constraints, it is possible to show
that under some rather general assumptions the average case RIB
storage overhead of the PV scheme for a single TOS ranges between
O(N) and O(Nlog(N)), where N is the total number of routing domains
([Rekhter91]). The LS RIB, with no aggregation of routing
information, no transit constraints, a single homogeneous route
selection policy across all the domains, and a single TOS, requires a
complete domain-level topology map whose size is O(N).
Supporting heterogeneous route selection and transit policies with
hop-by-hop forwarding and LS requires each domain to know all other
domains route selection and transit policies. This may significantly
increase the amount of routing information that must be stored by
each domain. If the number of policies advertised grows with the
number of domains, then the storage could become unsupportable. In
contrast, support for heterogeneous route selection policies has no
effect on the storage complexity of the PV scheme (aside from simply
storing the local policy information). The presence of transit
constraints in PV results in a restricted distribution of routing
information, thus further reducing storage overhead. In contrast,
with LS no such reduction is possible since each domain must know
every other domain's transit policies. Finally, some of the transit
constraints (e.g., path sensitive constraints) can be expressed in a
more concise form in PV (see aggregation discussion below).
The ability to further restrict storage overhead is facilitated by
the PV routing algorithm, where route computation precedes routing
information dissemination, and only routing information associated
with the routes selected by a domain is distributed to adjacent
domains. In contrast, route selection with LS is decoupled from the
distribution of routing information, and has no effect on such
distribution.
While theoretically routing information aggregation can be used to
reduce storage complexity in both LS and PV, only aggregation of
topological information would yield the same gain for both.
Aggregating transit constraints with LS may result in either reduced
connectivity or less information reduction, as compared with PV.
Aggregating heterogeneous route selection policies in LS is highly
problematic, at best. In PV, route selection policies are not
distributed, thus making aggregation of route selection policies a
non-issue [Footnote: Although a domain's selection policies are not
explicitly distributed, they have an impact on the routes available
to other domains. A route that may be preferred by a particular
domain, and not prohibited by transit restrictions, may still be
unavailable due to the selection policies of some intermediate
domain. The ability to compute and install alternative routes that
may be lost using hop-by-hop routing (either LS of PV) is the
critical functionality provided by SDR.].
Support for multiple TOSs has the same impact on storage overhead for
both LS and for PV.
Potentially the LS FIB may be smaller if routes are computed at each
node on demand. However, the gain of such a scheme depends heavily
on the traffic patterns, memory size, and caching strategy. If there
is not a high degree of locality, severely degraded performance can
result due to excessive overall computation time and excessive
computation delay when forwarding packets to a new destination. If
demand driven route computation is not used for LS, then the size of
the FIB would be the same for both LS and PV.
3.3.2 Route Computation Complexity
Even if all domains employ exactly the same route selection policy,
computational complexity of PV is smaller than that of LS. The PV
computation consists of evaluating a newly arrived route and
comparing it with the existing one [Footnote: Some additional checks
are required when an update is received to insure that a routing loop
has not been created.]. Whereas, conventional LS computation
requires execution of an SPF algorithm such as Dijkstra's.
With PV, topology changes only result in the recomputation of routes
affected by these changes, which is more efficient than complete
recomputation. However, because of the inclusion of full path
information with each distance vector, the effect of a topology
change may propagate farther than in traditional distance vector
algorithms. On the other hand, the number of affected domains will
still be smaller with PV than with conventional LS hop-by-hop
routing. With PV, only those domains whose routes are affected by
the changes have to recompute, while with conventional LS hop-by-hop
routing all domains must recompute. While it is also possible to
employ partial recomputation with LS (i.e., when topology changes,
only the affected routes are recomputed), "studies suggest that with
a very small number of link changes (perhaps 2) the expected
computational complexity of the incremental update exceeds the
complete recalculation" ([ANSI87-150R]). However these checks are
much simpler than executing a full SPF algorithm.
Support for heterogeneous route selection policies has serious
implications for the computational complexity. The major problem
with supporting heterogeneous route selection policies with LS is the
computational complexity of the route selection itself.
Specifically, we are not aware of any algorithm with less than
exponential time complexity that would be capable of computing routes
to all destinations, with LS hop-by-hop routing and heterogeneous
route selection policies. In contrast, PV allows each domain to make
its route selection autonomously, based only on local policies.
Therefore support for dissimilar route selection policies has no
negative implications for the complexity of route computation in PV.
Similarly, providing support for path-sensitive transit policies in
LS implies exponential computation, while in PV such support has no
impact on the complexity of route computation.
In summary, because NR will rely primarily on precomputation of
routes, aggregation is essential to the long-term scalability of the
architecture. To the extent aggregation is facilitated with PV, so
is reduced computational complexity. While similar arguments may be
made for LS, the aggregation capabilities that can be achieved with
LS are more problematic because of LS' reliance on consistent
topology maps at each node. It is also not clear what additional
computational complexity will be associated with aggregation of
transit constraints and heterogeneous route selection policies in LS.
3.3.3 Bandwidth Overhead
PV routing updates include fully-expanded information. A complete
route for each supported TOS is advertised. In LS, TOS only
contributes a factor increase per link advertised, which is much less
than the number of complete routes. Although TOSs may be encoded
more efficiently with LS than with PV, link state information is
flooded to all domains, while with PV, routing updates are
distributed only to the domains that actually use them. Therefore,
it is difficult to make a general statement about which scheme
imposes more bandwidth overhead, all other factors being equal.
Moreover, this is perhaps really not an important difference, since
we are more concerned with the number of messages than with the
number of bits (because of compression and greater link bandwidth, as
well as the increased physical stability of links).
3.4 Aggregation
Forming confederations of domains, for the purpose of consistent,
hop-by-hop, LS route computation, requires that domains within a
confederation have consistent policies. In addition, LS
confederation requires that any lower level entity be a member of
only one higher level entity. In general, no intra-confederation
information can be made visible outside of a confederation, or else
routing loops may occur as a result of using an inconsistent map of
the network at different domains. Therefore, the use of
confederations with hop-by-hop LS is limited because each domain (or
confederation) can only be a part of one higher level confederation
and only export policies consistent with that confederation (see
examples in Section 2.2). These restrictions are likely to impact
the scaling capabilities of the architecture quite severely.
In comparison, PV can accommodate different confederation definitions
because looping is avoided by the use of full path information.
Consistent network maps are not needed at each route server, since
route computation precedes routing information dissemination.
Consequently, PV confederations can be nested, disjoint, or
overlapping. A domain (or confederation) can export different
policies or TOS as part of different confederations, thus providing
the extreme flexibility that is crucial for the overall scaling and
extensibility of the architecture.
In summary, aggregation is essential to achieve acceptable complexity
bounds, and flexibility is essential to achieve acceptable
aggregation across the global, decentralized internet. PV's
strongest advantage stems from its flexibility.
3.5 Policy
The need to allow expression of transit policy constraints on any
route (i.e., NR routes as well as SDR routes), by itself, can be
supported by either LS or PV. However, the associated complexities
of supporting transit policy constraints are noticeably higher for LS
than for PV. This is due to the need to flood all transit policies
with LS, where with PV transit policies are controlled via restricted
distribution of routing information. The latter always imposes less
overhead than flooding.
While all of the transit constraints that can be supported with LS
can be supported with PV, the reverse is not true. In other words,
there are certain transit constraints (e.g., path-sensitive transit
constraints) that are easily supported with PV, and are prohibitively
expensive (in terms of complexity) to support in LS. For example, it
is not clear how NR with LS could support something like ECMA-style
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 selection
policies, in view of its computational and storage complexity, is
impractical with LS hop-by-hop routing. In contrast, PV can
accommodate heterogeneous route selection with little additional
overhead.
3.6 Information Hiding
PV has a clear advantage with respect to selective information
hiding. LS with hop-by-hop routing hinges on the ability of all
domains to have exactly the same information; this clearly
contradicts the notion of selective information hiding. That is, the
requirement to perform selective information hiding is unsatisfiable
with LS hop-by-hop routing.
3.7 Commonality between NR and SDR Components
In [Breslau-Estrin91] we argued for the use of LS in conjunction with
SDR. Therefore there is some preference for using LS with NR.