routing
Click on the red underlined text to get to the source
... domain. In order to support each domain's
autonomy and heterogeneity, routing consists of two distinct
components: intra-domain (interior) routing ...
... routing consists of two distinct
components: intra-domain (interior) routing, and inter-domain
(exterior) routing ...
... routing, and inter-domain
(exterior) routing. Intra-domain routing provides support for data
...
... (exterior) routing. Intra-domain routing provides support for data
communication between hosts where data traverses transmission and
...
... 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
...
... are called border routers (BRs). The entities responsible for
exchanging inter-domain routing information are called route servers
(RSs ...
... As the global internet grows, both in size and in the diversity of
routing requirements, providing inter-domain routing that can
...
... routing requirements, providing inter-domain routing that can
accommodate both of these factors becomes more and more crucial. The
number and diversity of routing ...
... 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 ...
... different criteria weighs heavily on the mechanisms provided by
conventional hop-by-hop routing architectures ([ISIS10589, OSPF ...
...
Current work on inter-domain routing within the Internet community
has diverged in two directions: one is best represented by the Border
Gateway Protocol ...
... Honig90, IDRP91]), and another is best
represented by the Inter-Domain Policy Routing (IDPR) architecture
...
... services. While the number and
variety of routes provided by hop-by-hop routing architectures with
type of service ...
... 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:
...
... 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 ...
... 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 ...
... IDPR) architecture uses
these techniques.]. However, a source-demand routing architecture,
used as the only means of inter-domain routing ...
... 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 ...
... 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 ...
... 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 ...
... inter-domain routing, based on
hop-by-hop routing and a distributed route-computation algorithm
...
... datagram networks, it does not provide support for specialized
routing requirements as flexibly and efficiently as IDPR-style
...
... route is not needed. Therefore, our scalable inter-
domain routing architecture consists of two major components:
...
... architecture consists of two major components:
source-demand routing (SDR), and node routing (NR ...
... 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
...
...
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 ...
... 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
...
... 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.
...
... 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 ...
... 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 ...
... 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 ...
... 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.
...
... 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.].
...
...
In order to justify our design choices for a scalable inter-domain
routing architecture, we must articulate our evaluation criteria and
priorities ...
...
Inter-domain routing complexity must be evaluated on the basis of the
following performance metrics: (1) storage overhead ...
... The storage overhead of an entity that participates in inter-domain
routing comes from two sources: Routing Information Base (RIB), and
...
... overhead of an entity that participates in inter-domain
routing comes from two sources: Routing Information Base (RIB), and
Forwarding Information Base ...
... overhead. The RIB contains the
routing information that entities exchange via the inter-domain
routing protocol; the RIB is the input to the route ...
... RIB contains the
routing information that entities exchange via the inter-domain
routing protocol; the RIB is the input to the route computation. 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 ...
... 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 ...
... 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.
...
... 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 ...
... 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 ...
...
The bandwidth consumed by routing information distribution should be
limited. However, the possible use of data compression techniques
...
... overhead may
be further contained by using incremental (rather than complete)
exchange of routing information.
...
...
Aggregation and abstraction of routing and forwarding information
provides a very powerful mechanism for satisfying storage,
computational, and bandwidth constraints ...
... 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
...
... 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
...
... transit constraint. Aggregation of routing information should
provide a reduction of all three components. Aggregation of
...
... registration authorities, and the way routing domains and routing
domain confederations are organized (see Section 2.6).
...
... Routing Policies ...
...
Routing policies that the architecture must support may be broadly
classified into transit policies and route selection ...
... dissimilar route selection policies is one of the key factors that
distinguish inter-domain routing from intra-domain routing ([ECMA89 ...
... Routing Information Hiding ...
... 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-
...
...
In this and previous papers we have argued that a global inter-domain
routing architecture should support a wide range of policies. In
...
... think such policy types are either very expensive in terms of
overhead, or may lead to routing instabilities.
...
... 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
...
... type of service
(TOS) routing. There is a great deal of research and development
activity currently underway to explore network architectures ...
...
In this context, it is the job of routing protocols to locate routes
that can potentially support the particular TOS requested. It is
...
... 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 ...
... Commonality between Routing Components ...
... address structure, except that this structure should facilitate
information aggregation, without forcing rigid hierarchical routing.
...
... destination. Moreover, NR is best suited to provide
routing for inter-domain data traffic that is either steady enough to
...
... 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 ...
... route computation. Route computation is driven by
changes in either operational status of routing facilities or policy
constraints. The NR ...
...
Moreover, the exchange of routing information necessary for the SDR
component depends on facilities provided by the NR component; i.e.,
...
...
The potential reduction of routing and forwarding information depends
very heavily on the way addresses are assigned and how domains ...
... 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 ...
... 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 ...
... information will be possible. Therefore, given the nature of inter-
domain routing in general, and the NR component in particular,
scalability ...
... 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 ...
... 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
...
... 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
...
... 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
...
... 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 ...
... distance vector protocols. However, simple distance vector
protocols (i.e., Routing Information Protocol [Hedrick88]), do not
scale because of convergence ...
... 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 ...
... BGP91]) and the Inter Domain
Routing Protocol (IDRP) (see [IDRP91]) are examples of path vector ...
... vector
(PV) protocols [Footnote: BGP is an inter-autonomous system routing
protocol for TCP/IP internets. IDRP is an OSI ...
... TCP/IP internets. IDRP is an OSI inter-domain routing
protocol that is being progressed toward standardization within ISO.
...
...
The routing algorithm employed by PV bears a certain resemblance to
the traditional Bellman-Ford routing algorithm in the sense that each
...
... 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 ...
... 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
...
... domains (or confederations) traversed so far, is carried in a
special path attribute which records the sequence of routing domains
through which the reachability ...
... 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 ...
...
Because PV does not require all routing domains to have homogeneous
criteria (policies) for route selection ...
... route selection, route selection policies
used by one routing domain are not necessarily known to other routing
...
... used by one routing domain are not necessarily known to other routing
domains. To maintain the maximum degree of autonomy and independence
...
... domains. To maintain the maximum degree of autonomy and independence
between routing domains, each domain which participates in PV may
...
...
Without any aggregation of routing information, and ignoring storage
overhead associated with transit constraints ...
... TOS ranges between
O(N) and O(Nlog(N)), where N is the total number of routing domains
([Rekhter91 ...
... Rekhter91]). The LS RIB, with no aggregation of routing
information, no transit constraints, a single homogeneous route
selection policy across all the domains ...
... 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
...
... 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 ...
... 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 ...
... the PV routing algorithm, where route computation precedes routing
information dissemination, and only routing information associated
with the routes selected by a domain ...
... 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 ...
... 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.].
...
... 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
...
... 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 ...
... 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 ...
... to all destinations, with LS hop-by-hop routing and heterogeneous
route selection policies. In contrast, PV allows each domain ...
...
PV routing updates include fully-expanded information. A complete
route for each supported TOS ...
... link state information is
flooded to all domains, while with PV, routing updates are
distributed only to the domains that actually use them. Therefore,
...
... 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 ...
... route server, since
route computation precedes routing information dissemination.
Consequently, PV confederations can be nested, disjoint, or
overlapping. A domain ...
... 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 ...
... 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
...
... 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.
...
... However, there are several reasons why NR and SDR would not use
exactly the same routing information, even if they did use the same
algorithm. Moreover, there are several opportunities for unifying
...
... algorithm. Moreover, there are several opportunities for unifying
the management (distribution and storage) of routing and forwarding
information, even if dissimilar algorithms are used.
...
...
1. Routing information and distribution protocol: LS for SDR is
quite different from the LS in NR. For example, SDR LS need
...
... Given the performance complexity issues associated with global
routing, aggregation of routing information is essential; at the same
...
... routing, aggregation of routing information is essential; at the same
time we have argued that such aggregation must be flexible. Given
...
... aggregation must be flexible. Given
the difficulties of supporting LS hop-by-hop routing in the presence
of (a) flexible aggregation, (b) heterogeneous route selection ...
... aggregation, (b) heterogeneous route selection
policies, and (c) incomplete or inconsistent routing information, we
see no alternative but to employ PV for the NR component of our
...
... [Footnote: Packet forwarding along routes produced by the NR
component can be accomplished by either source routing or hop-by-hop
routing ...
... routing or hop-by-hop
routing. The latter is the primary choice because it reduces the
amount of state in routers ...
... layer packets. However,
the architecture does not preclude the use of source routing (or
route setup) along the routes computed, but not installed, by the NR ...
... route (e.g., the list of domains or routing domain confederations
that the routing information ...
... routing domain confederations
that the routing information has traversed so far). The path
attributes that are carried along with a route express a variety of
...
... path
attributes that are carried along with a route express a variety of
routing policies, and make explicit the entire route to the
destination ...
... Source-demand routing (SDR) ...
... Inter-domain routers participating in the SDR component forward
packets according to routing information computed and installed by
the domain that originates the traffic ...
... It is important to realize that requiring route installation by the
source routing domain is not a matter of choice, but rather a
necessity. If a particular route ...
...
In general, information that is used by source routing domains for
computing source-demand routes reflects administrative (but not
...
... domains for
computing source-demand routes reflects administrative (but not
operational) status of the routing facilities (i.e., configured
topology and policy) [Footnote: If SDR uses NR ...
... operational status could be considered in some route selection.].
Consequently, it is possible for a source routing domain to compute a
route ...
... route
installation is attempted. Similarly, the SDR component provides
mechanisms for the source routing domain to be notified of failures
along previously-installed active ...
... along previously-installed active routes. In other words, the SDR
component performs routing that is adaptive to topological changes;
however, the adaptability is achieved as a consequence of the route
...
... incorporated by nodes as soon as possible. Therefore, to allow
faster adaptation to changes in the operational status of routing
facilities, the SDR component allows the source domain to switch ...
... domain
map if portions of the world are never traversed or communicated
with. As a result of the looser routing structure, SDR does not
guarantee that a participating source routing domain ...
... with. As a result of the looser routing structure, SDR does not
guarantee that a participating source routing domain will always have
sufficient information to compute a route ...
... to compute desired routes [Footnote: The primary goal of policy or
TOS routing is to compute a route that satisfies a set of specialized
requirements ...
... requirements, and these requirements take precedence over optimality.
In other words, even if a routing domain that participates in SDR or
NR ...
... internet forms a small fraction of the total number of source-demand
routes that can potentially be installed by all the routing domains.
It is an assumption of the architecture ...
... architecture that the number of routes
installed in a BR by the SDR component should be on the order of log
N (where N is the total number of routing domains in the Internet),
...
... method
of route computation along with source routing. One could imagine,
for instance, a protocol like BGP in which the source uses the full
...
... BGP in which the source uses the full
AD path information it receives in routing updates to create a source
route. Such a protocol could address ...
... against further discussion of such a protocol because there is less
to gain by using source routing without also using a link state
scheme. The power of source routing ...
... routing without also using a link state
scheme. The power of source routing, in the context of inter-AD
...
... context of inter-AD
policy routing, is in giving the source control over the entire
route. This goal cannot be realized fully when intermediate nodes ...
... Distribution of Routing Information ...
... hop-by-hop NR component based on PV to complement the
source-routing SDR component, we have alleviated the pressure to
aggregate SDR forwarding information; the large percentage of inter-
domain ...
... topology map. In this section
we describe promising opportunities for improving the scaling
properties of SDR routing information distribution, storage, and
computation.
...
... domains may require different methods of abstracting
the same routing information. For example, if we aggregate routing
information of domains that do not share the same policy and TOS ...
... methods of abstracting
the same routing information. For example, if we aggregate routing
information of domains that do not share the same policy and TOS
...
... inter-domain connections.
If source routing exhibits route locality, the source is more likely
to use other routes going through the node ...
... NR component, or in parallel with it. SDR forwarding will be
supported via two techniques: loose source-routing and route setup.
...
...
The first technique, loose source-routing, would allow the originator
of a packet to specify a sequence of domains that the packet should
...
... domains within a confederation,
would be left to intra-domain routing. This avoids per-connection
state ...
... 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 ...
... accept message is propagated back hop by hop, and each BR en route
activates its routing information. Subsequent data packets traveling
along the same path to the destination ...
... network numbers to domain numbers; the latter
is needed to make the routing decision. We should consider
obtaining the network reachability and domain ...
... types of services, the capability of the
architecture to support routing in the presence of a large number of
different types of service is largely academic. That is, not all
...
... network layer is going to
have its own inter-domain routing protocol, or a single inter-domain
routing protocol will be able to cover multiple network layers
...
... layer is going to
have its own inter-domain routing protocol, or a single inter-domain
routing protocol will be able to cover multiple network layers
[Footnote: Similar issue already arose with respect to the intra-
...
... [Footnote: Similar issue already arose with respect to the intra-
domain routing protocol, which generated sufficient amount of
controversy within the Internet community. It is our opinion, that
...
... Internet community. It is our opinion, that
the issue of single versus multiple protocols is more complex for the
inter-domain routing than for the intra-domain routing.]. That is,
...
... inter-domain routing than for the intra-domain routing.]. That is,
the proposed architecture can be realized either by a single inter-
...
... architecture can be realized either by a single inter-
domain routing protocol covering multiple network layers, or by
multiple inter-domain routing ...
... routing protocol covering multiple network layers, or by
multiple inter-domain routing protocols (with the same architecture)
tailored to a specific network ...
... replacing existing EGP-2 routing with BGP routing. Once the NR
component is in place, it can be augmented by the facilities provided
...
... route installation and packet forwarding in the routers
that support SDR. Participation as a transit routing domain requires
that the domain ...
... that which it is best suited: NR uses PV and multiple, flexible,
levels of confederations to support efficient routing of generic
packets over generic routes; SDR uses LS computation over a database
...
... parallel. Together these two approaches will flexibly and
efficiently support TOS and policy routing in very large global
internets.
...
... "Intermediate System to Intermediate System Intra- Domain Routing Exchange Protocol", ANSI X3S3.3/87-150R. ...
... Breslau, L., and D. Estrin, "Design and Evaluation of Inter-Domain Policy Routing Protocols", To appear in Journal of Internetworking Research and Experience, 1991. (Earlier version appeared in ACM Sigcomm 1990.) ...
... Clark, D., "Policy Routing in Internetworks", Journal of Internetworking Research and Experience, Vol. 1, pp. 35-52, 1990. ...
... "Inter-Domain Intermediate Systems Routing", Draft Technical Report ECMA TR/ISR, ECMA/TC32-TG 10/89/56, May 1989. ...
... Estrin, D., "Policy Requirements for Inter Administrative Domain Routing", RFC 1125, USC Computer Science Department, November 1989. ...
... Estrin, D., Breslau, L., and L. Zhang, "Protocol Mechanisms for Adaptive Routing in Global Multimedia Internets", University of Southern California, Computer Science Department Technical Report, CS-SYS-91-04, November 1991. ...
... Hedrick, C., "Routing Information Protocol", RFC 1058hist, Rutgers University, June 1988. ...
... Steenstrup, M., "Inter-Domain Policy Routing Protocol Specification and Usage: Version 1", Work in Progress, February 1991. ...
... Information Exchange between Systems - Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol for use in Conjunction with the protocol for providing the Connectionless-mode Network Service (ISO ...
... Jaffee, J., and F. Moss, "A Responsive Distributed Routing Algorithm for Computer Networks", IEEE Transactions ...
... Little, M., "Goals and Functional Requirements for Inter-Autonomous System Routing", RFC 1126, SAIC, October 1989. ...
... Shin, K., and M. Chen, "Performance Analysis of Distributed Routing Strategies Free of Ping-Pong-Type Looping", IEEE Transactions ...
... Zaumen, W., and J. Garcia-Luna-Aceves, "Dynamics of Link State and Loop-free Distance-Vector Routing Algorithms", ACM Sigcomm '91, Zurich, Switzerland, September 1991. ...