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
the management (distribution and storage) of routing and forwarding
information, even if dissimilar algorithms are used.
In considering the differences between NR and SDR we must address
several areas:
1. Routing information and distribution protocol: LS for SDR is
quite different from the LS in NR. For example, SDR LS need
not aggregate domains; to the contrary SDR LS requires detailed
information to generate special routes.
In addition, consistency requirements (essential for NR) are
unnecessary for the SDR component. Therefore LS information for
the SDR component can be retrieved on-demand, while the NR
component must use flooding of topology information.
2. Route computation algorithm: It is not clear whether route
computation algorithm(s) can be shared between the SDR and NR
components, given the difficulty of supporting heterogeneous
route selection policies in NR.
3. Forwarding information: The use of dissimilar route computation
algorithms does not preclude common handling of packet
forwarding. Even if LS were used for NR, the requirement would
be the same, i.e., that the forwarding agent can determine
whether to use a NR precomputed route or an SDR installed route
to forward a particular data packet.
In conclusion, using similar algorithms and mechanisms for SDR and NR
components would have benefits. However, these benefits do not
dominate the other factors as discussed before.
3.8 Summary
Given the performance complexity issues associated with global
routing, aggregation of routing information is essential; at the same
time we have argued that such 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
policies, and (c) incomplete or inconsistent routing information, we
see no alternative but to employ PV for the NR component of our
architecture.
Based on the above tradeoffs, our NR component employs a PV
architecture, where route computation and installation is done in a
distributed fashion by the routers participating in the NR component
[Footnote: Packet forwarding along routes produced by the NR
component can be accomplished by either source routing or hop-by-hop
routing. The latter is the primary choice because it reduces the
amount of state in routers (if route setup is employed), or avoids
encoding an explicit source route in network 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
component.].
The distributed algorithm combines some of the features of link state
with those of distance vector algorithms; in addition to next hop
information, the NR component maintains path attributes for each
route (e.g., the list of domains or 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
routing policies, and make explicit the entire route to the
destination. With aggregation, this is a superset of the domains
that form the path to the destination.
4.0 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 (source routing domain).
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 is used by a small number of
domains (perhaps only one) then it is more appropriate to have the
source compute and install the special route instead of burdening the
intermediate nodes with the task of looking for and selecting a route
with the specialized requirements. In addition, if the demand for
the route is unpredictable, and thus can be determined only by the
source, it should be up to the source to install the route.
In general, information that is used by source routing 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 information then
operational status could be considered in some route selection.].
Consequently, it is possible for a source routing domain to compute a
route that is not operational at route installation time. The SDR
component attempts to notify the source domain of failures when route
installation is attempted. Similarly, the SDR component provides
mechanisms for the source routing domain to be notified of failures
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
installation and route management mechanisms. This is different from
the NR component, where status changes are propagated and
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 to a
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 NR
route.
The NR component will group domains into confederations to achieve
its scaling goals (see [IDRP91]). In contrast, SDR will allow an
AD-level route to be used by an individual domain without allowing
use by the entire confederation to which the domain belongs.
Similarly, a single transit domain may support a policy or special
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 of
NR. In compensation, SDR does not require a complete, global 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 will always have
sufficient information to compute a route to a destination. In
addition, if the domain does have sufficient information, it is
possible that the quantity may be large enough to preclude storage
and/or route computation in a timely fashion. However, despite the
lack of guarantees, it is a goal of the architecture to provide
efficient methods whereby sources can obtain the information needed
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, and these requirements take precedence over optimality.
In other words, even if a routing domain that participates in SDR or
NR has sufficient information to compute a route, given a particular
set of requirements, the architecture does not guarantee that the
computed route is optimal.].
Essential to SDR is the assumption that the routes installed on
demand will be used sparingly. The architecture assumes that at any
given moment the set of all source-demand routes installed in an
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 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),
so that the scaling properties of the SDR component are comparable
with the scaling properties of the NR component. The NR component
achieves this property as a result of hierarchy.
Note that the above requirement does not imply that only a few
domains can participate in SDR, or that routes installed by the SDR
component must have short life times. What the requirement does
imply, is that the product of the number of routes specified by
domains that participate in SDR, times the average SDR-route life
time, is bounded. For example, the architecture allows either a
small number of SDR routes with relatively long average life times,
or a large number of SDR routes with relatively short average life
times. But the architecture clearly prohibits a large number of SDR
routes with relatively long average life times. The number of SDR
routes is a function of the number of domains using SDR routes and
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 justify
computation and maintenance by the NR component, and (2) whose
duration is significantly longer than the time it takes to perform
the route installation procedure.
The architecture does not require all domains in the Internet to
participate in SDR. Therefore, issues of scalability (with respect
to the size of the Internet) become less crucial (though still
important) to the SDR component. Instead, the primary focus of the
SDR component is shifted towards the ability to compute routes that
satisfy specialized requirements, where we assume that the total
number of domains requiring special routes simultaneously through the
same part of the network is small relative to the total population.
4.1 Path Vector vs. Link State for SDR
It is feasible to use either a distance vector or link state method
of route computation along with source routing. One could imagine,
for instance, a protocol like 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 some of the deficiencies
identified with distance vector, hop-by-hop designs. However, we opt
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, in the 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
control which legal routes are advertised to neighbors, and therefore
to a source.
In other words, intermediate nodes should be able to preclude the use
of a route by expressing a transit policy, but if a route is not
precluded (i.e., is legal according to all ADs in the route), the
route should be made available to the source independent of an
intermediate domain's preferences for how its own traffic flows.
Therefore, the SDR component employs an IDPR-like architecture in
which link-state style updates are distributed with explicit policy
terms included in each update along with the advertising node's
connectivity.
4.2 Distribution of Routing Information
By using a 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 traffic carried, simultaneously, by any particular border
router will be forwarded using aggregated NR forwarding information.
However, the use of NR does not address the other major scaling
problem associated with SDR: that of distributing, storing, and
computing over a complete domain-level topology map. In this section
we describe promising opportunities for improving the scaling
properties of SDR routing information distribution, storage, and
computation.
Note that we do not propose to solve this problem in the same way
that we solve it for NR. A priori abstraction will not be employed
since different 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
characteristics (i.e., services), then outside of the aggregate, only
those services that are offered by all domains in the aggregate will
be advertised. In order to locate special routes, SDR only uses
aggregates when the component domains (and in turn the aggregate)
advertise the required TOS and policy descriptions. When the
required TOS or policy characteristics are not offered by an
aggregate, full information about the component domains is used to
construct a route through those domains that do support the
particular characteristics. Consequently, we need some other, more
flexible, means of reducing the amount of information distributed and
held. We address two issues in turn: distribution of configured
topology and policy information, and distribution of dynamic status
information.
4.2.1 Configured Information
Information about the existence of inter-domain links, and policies
maintained by domains, changes slowly over time. This is referred to
as configured information. In the current IDPR specification
complete, global, configuration information is kept by a route server
in each domain. Route servers (RS) are the entities that compute
source routes. On startup a RS can download the connectivity
database from a neighbor RS; as domains, inter-domain links, or
policies change, the changes are flooded to a RS in each domain.
We have not yet specified the exact mechanisms for distributing
configured connectivity information for SDR. However, unlike the
current IDPR specification, the SDR component will not flood all
configured information globally. Several alternate methods for
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 information
could be posted in several well-known locations for retrieval, e.g.,
via FTP. Between these "major" updates, aggregated collections of
changes may be flooded globally. Moreover, limited flooding (e.g.,
by hop-count) could be used as appropriate to the "importance" of the
change; while a policy change in a major backbone may still be
flooded globally, a new inter-regional link may be flooded only
within those regions, and information about an additional link to a
non-transit domain may not be available until the next regularly-
scheduled "major" distribution.
Changes that are not distributed as they occur will not necessarily
be discovered. However, a route server may learn pertinent
information by direct query of remote servers, or through error
messages resulting from traffic sent along failed routes. Complete
global flooding may be avoided by using some combination of these
mechanisms.
Even if an initial implementation uses a simple global flood, we must
study the problem of structuring connectivity information such that
it can be retrieved or distributed in a more selective manner, while
still allowing sources to discover desired routes. For example, we
imagine RSs requesting filtered information from each other. How the
RSs should define filters that will get enough information to find
special routes, while also effectively limiting the information, is
an open question. Again, the question is how to effectively
anticipate and describe what information is needed in advance of
computing the route.
The essential dilemma is that networks are not organized in a nicely
geographical or topologically consistent manner (e.g., it is not
effective to ask for all networks going east-west that are within a
certain north-south region of the target), hence a source domain does
not know what information it needs (or should ask for) until it
searches for, and discovers, the actual path. Even with a central
database, techniques are needed to structure configuration
information so that the potential paths that are most likely to be
useful are explored first, thereby reducing the time required for
route computation.
One promising approach organizes information using route fragments
(partial paths) [Footnote: Route fragments were first suggested by
Dave Clark and Noel Chiappa.]. Although the number of route
fragments grows faster than the number of domains (at least O(N^2)),
we can selectively choose those that will be useful to compute
routes. In particular, for each stub domain, fragments would be
constructed to several well-known backbones [Footnote: Route
fragments may be computed by a destination's route server and either
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 a
manner useful for computing source-routes, and provides an index,
namely the destination, which facilitates on-demand reference and
retrieval of information pertinent to a particular route computation.
At this point, it is not clear how route fragments will affect SDR's
ability to discover non-hierarchical routes.
4.2.2 Dynamic Status Information
Assuming a technique for global or partial distribution of configured
information, a second issue is whether, and how, to distribute
dynamic status information (i.e., whether an inter-domain connection
is up or down).
In the current version of IDPR, dynamic status information is flooded
globally in addition to configuration information. We propose to
distribute status information based strictly on locality. First,
dynamic information will be advertised within a small hop-count
radius. This simple and low-overhead mechanism exploits topological
locality. In addition to flooding status updates to nearby nodes, we
also want to provide more accurate route information for long
distance communications that entails more than a few network hops.
Reverse path update (RPU) is a mechanism for sending dynamic status
information to nodes that are outside the k-hop radius used for
updates, but that nevertheless would obtain better service (fewer
failed setups) by having access to the dynamic information [Estrin-
etal91].
RPU uses the existing active routes (represented by installed setup
state or by a cache of the most recent source routes sent via the
node in question) as a hint for distribution of event notifications.
Instead of reporting only the status of the route being used, RPU
reports the status of the domain's other inter-domain connections.
If source routing exhibits route locality, the source is more likely
to use other routes going through the node in question; in any case
the overhead of the information about other links will be minimal.
In this way, sources will receive status information from regions of
the network through which they maintain active routes, even if those
regions are more than k hops away. Using such a scheme, k could be
small to maximize efficiency, and RPU could be used to reduce the
incidence of failed routes resulting from inaccurate status
information. This will be useful if long-path communication exhibits
route locality with respect to regions that are closer to the
destination (and therefore outside the k hop radius of flooded
information). In such situations, flooding information to the source
of the long route would be inefficient because k would have to be
equal to the length of the route, and in almost all cases, the
percentage of nodes that would use the information decreases
significantly with larger k.
4.3 Source-Demand Route Management
SDR may be built either on top of the network layer supported by the
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
traverse on its path to a destination. Forwarding such a packet
within a domain, or even between domains within a confederation,
would be left to intra-domain routing. This avoids per-connection
state and supports transaction traffic.
The second technique, route setup, will be based on mechanisms
developed for IDPR and described in [IDPR90]. It is well suited to
conversations that persist significantly longer than a round-trip-
time. The setup protocol defines packet formats and the processing
of route installation request packets (i.e, setup packets). When a
source generates a setup packet, the first border router along the
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-related
information the particular domain requires. The setup packet is
passed on to the next BR in the domain-level source route, and the
same procedure is carried out [Footnote: The setup packet may be
forwarded optimistically, i.e., before checks are completed, to
reduce latency.]. When the setup packet reaches the destination, an
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 include a path ID in the
packet. That path ID is used to locate the appropriate next-hop
information for each packet.
Border routers that support both the NR and the SDR components, must
be able to determine what forwarding mechanism to use. That is, when
presented with a network layer PDU, such a BR should be able to make
an unambiguous decision about whether forwarding of that PDU should
be handled by the NR or the SDR component. Discrimination mechanisms
are dependent on whether the new network layer introduced by the SDR
component is built on top of, or in parallel with, the network layers
supported by the NR component. Once the discrimination is made,
packets that have to be forwarded via routes installed by the SDR
component are forwarded to the exit port associated with the
particular Path ID in the packet header. Packets that have to be
forwarded via routes installed by the NR component are forwarded to
the exit port associated with the particular destination and Type of
Service parameters (if present) in their packet headers.
Next, we describe the primary differences between the IDPR setup
procedure previously specified, and the procedure we propose to
develop for this hybrid architecture.
During route installation, if a BR on the path finds that the
remainder of the indicated route from the BR to the destination is
identical to the NR route from the BR to the destination, then the BR
can turn off the SDR route at that point and map it onto the NR
route. For this to occur, the specifications of the SDR route must
completely match those of the NR route. In addition, the entire
forward route must be equivalent (i.e., the remaining hops to the
destination).
Moreover, if the NR route changes during the course of an active SDR
route, and the new NR route does not match the SDR route, then the
SDR route must be installed for the remainder of the way to the
destination. Consequently, when an SDR route is mapped onto an NR
route, the original setup packet must be saved. A packet traveling
from a source to destination may therefore traverse both an SDR and
an NR route segment; however, a packet will not traverse another SDR
segment after traveling over an NR segment. However, during
transient periods packets could traverse the wrong route and
therefore this must be an optional and controllable feature.
A source can also request notification if a previously-down link or
node returns to operation some time after a requested route setup
fails. If a BR on the route discovers that the requested next-hop BR
is not available, the BR can add the source to a notification list
and when the next-hop BR becomes reachable, a notification can be
sent back to the source. This provides a means of flushing out bad
news when it is no longer true. For example, a domain might decide
to route through a secondary route when its preferred route fails;
the notification mechanism would inform the source in a timely manner
when its preferred route is available again.
A third option addresses adaptation after route installation. During
packet forwarding along an active SDR route, if a BR finds that the
SDR route has failed, it may redirect the traffic along an existing
NR route to the destination. This adaptation is allowed only if use
of the NR route does not violate policy; for example, it may provide
a less desirable type of service. This is done only if the source
selects the option at route setup time. It is also up to the source
whether it is to be notified of such actions.
When a SDR route does fail, the detecting BR sends notification to
the source(s) of the active routes that are affected. Optionally,
the detecting BR may include additional information about the state
of other BRs in the same domain. In particular, the BR can include
its domain's most recent "update" indicating that domain's inter-
domain links and policy. This can be helpful to the extent there is
communication locality; i.e., if alternative routes might be used
that traverse the domain in question, but avoid the failed BR.
In summary, when a route is first installed, the source has several
options (which are represented by flags in the route setup packet):
1. If an NR route is available that satisfies all local policy
and TOS, then use it. Otherwise...
2. Indicate whether the source wants to allow the setup to
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 resource
re-availability.
6. Allow data packets to be rerouted to a NR route when failure
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 notice
when the route is active.
9. Request addition to a notification list if an active route
fails.
5.0 The Unified Architecture
In addition to further evaluation and implementation of the proposed
architecture, future research must investigate opportunities for
increased unification of the two components of our architecture. We
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 labeled
with flags (on the nodes or links) corresponding to the
generic transit constraints. SDR requires that this graph
be augmented by links with non-generic policies that have
been discovered and maintained for computing special routes;
in addition, special policy flags may be added to links
already maintained by the NR component.
2. Information Distribution:
The NR path vectors could include address(es) of repositories
for SDR-update information for each AD (or confederation) to
assist the SDR component in retrieving selective information
on demand. For domains with minimal policies, where the space
required for policy information is smaller than the space
required for a repository address (e.g., if the policies for
the domain listed are all wildcard), the NR path vectors could
include a flag to that effect.
3. Packet Forwarding:
We should consider replacing the current IDPR-style network
layer (which contains a global path identifier used in
forwarding data packets to the next policy gateway on an
IDPR route) with a standard header (e.g., IP or CLNP),
augmented with some option fields. This would unify the
packet header parsing and forwarding functions for SDR and NR,
and possibly eliminate some encapsulation overhead.
4. Reachability Information:
Currently IDRP distributes network reachability information
within updates, whereas IDPR only distributes domain
reachability information. IDPR uses a domain name service
function to map network numbers to domain numbers; the latter
is needed to make the routing decision. We should consider
obtaining the network reachability and domain information in
a unified manner.
5.1 Applicability to Various Network Layer Protocols
The proposed architecture is designed to accommodate such existing
network layer protocols as IP ([Postel81]), CLNP ([ISO-473-88]), and
ST-II ([ST2-90]). In addition, we intend for this architecture to
support future network layer mechanisms, e.g., Clark and Jacobson's
proposal or Braden and Casner's Integrated Services IP. However on
principal we can not make sweeping guarantees in advance of the
mechanisms themselves. In any case, not all of the mentioned
protocols will be able to utilize all of the capabilities provided by
the architecture. For instance, unless the increase in the number of
different types of services offered is matched by the ability of a
particular network layer protocol to unambiguously express requests
for such different 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
components of the architecture will have equal importance for
different network layer protocols. On the other hand, this
architecture is designed to serve the future global internetworking
environment. The extensive research and development currently
underway to implement and evaluate network mechanisms for different
types of service suggests that future networks will offer such
services.
One of the fundamental issues in the proposed architecture is the
issue of single versus multiple protocols. The architecture does not
make any assumptions about whether each 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
[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
the issue of single versus multiple protocols is more complex for the
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 by
multiple inter-domain routing protocols (with the same architecture)
tailored to a specific network layer [Footnote: If the single
protocol strategy is adopted, then it is likely that IDRP will be
used as a base for the NR component. Since presently IDRP is
targeted towards CLNP, further work is needed to augment it to
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 NR
component for IP, and IDRP will be used as a base for the NR
component for CLNP. Further work is needed to specify protocol in
support for the NR component for ST-II. Additional work may be
needed to specify new features that may be added to BGP.].
5.2 Transition
The proposed architecture is not intended for full deployment in the
short term future. We are proposing this architecture as a goal
towards which we can begin guiding our operational and research
investment over the next 5 years.
At the same time, the architecture does not require wholesale
overhaul of the existing Internet. The NR component may be phased in
gradually. For example, the NR component for IP may be phased in by
replacing existing EGP-2 routing with BGP routing. Once the NR
component is in place, it can be augmented by the facilities provided
by the SDR component.
The most critical components of the architecture needed to support
SDR include route installation and packet forwarding in the routers
that support SDR. Participation as a transit routing domain requires
that the domain can distribute local configuration information (LCI)
and that some of its routers implement the route installation and
route management protocols. Participation as a source requires that
the domain have access to a RS to compute routes, and that the source
domain has a router that implements the route installation and route
management protocols. In addition, a network management entity must
describe local configuration information and send it to the central
repository(ies). A collection and distribution mechanism must be put
in place, even if it is centralized.
6.0 Conclusions and Future Work
In summary, the proposed architecture combines hop-by-hop path-
vector, and source-routed link-state, protocols, and uses each for
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
of configured and dynamic information to route special traffic over
special routes. In the past, the community has viewed these two as
mutually exclusive; to the contrary, they are quite complementary and
it is fortunate that we, as a community, have pursued both paths in
parallel. Together these two approaches will flexibly and
efficiently support TOS and policy routing in very large global
internets.
It is now time to consider the issues associated with combining and
integrating the two. We must go back and look at both architectures
and their constituent protocols, eliminate redundancies, fill in new
holes, and provide seamless integration.
7.0 Acknowledgments
We would like to thank Hans-Werner Braun (San Diego Supercomputer
Center), Lee Breslau (USC), Scott Brim (Cornell University), Tony Li
(cisco Systems), Doug Montgomery (NIST), Tassos Nakassis (NIST),
Martha Steenstrup (BBN), and Daniel Zappala (USC) for their comments
on a previous draft.
8.0 References
[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)", RFC1267, cisco Systems, T.J. Watson Research Center, IBM
Corp., October 1991.
[Breslau-Estrin 91] 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 90] Clark, D., "Policy Routing in Internetworks", Journal of
Internetworking Research and Experience, Vol. 1, pp. 35-52, 1990.
[Dijkstra 59] Dijkstra, E., "A Note on Two Problems in Connection
with Graphs", Numer. Math., Vol. 1, 1959, pp. 269-271.
[ECMA89] "Inter-Domain Intermediate Systems Routing", Draft
Technical Report ECMA TR/ISR, ECMA/TC32-TG 10/89/56, May 1989.
[EGP] Rosen, E., "Exterior Gateway Protocol (EGP)", RFC827, BBN,
October 1982.
[Estrin 89] Estrin, D., "Policy Requirements for Inter
Administrative Domain Routing", RFC1125, USC Computer Science
Department, November 1989.
[Estrin-etal91] 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 88] Hedrick, C., "Routing Information Protocol", RFC1058,
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", RFC
1164, Cornell Univ. Theory Center, Merit/NSFNET, Pittsburgh
Supercomputing Center, T.J. Watson Research Center, IBM Corp., June
1990.
[IDPR90] Steenstrup, M., "Inter-Domain Policy Routing Protocol
Specification and Usage: Version 1", Work in Progress, February 1991.
[IDRP91] "Intermediate System to Intermediate System Inter-domain
Routeing Exchange Protocol", ISO/IEC/ JTC1/SC6 CD10747.
[ISIS10589] "Information Processing Systems - Telecommunications and
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 8473)", ISO/IEC 10589.
[ISO-473 88] "Protocol for providing the connectionless-mode network
service", ISO 8473, 1988.
[Jaffee 82] Jaffee, J., and F. Moss, "A Responsive Distributed
Routing Algorithm for Computer Networks", IEEE Transactions on
Communications, July 1982.
[Little 89] Little, M., "Goals and Functional Requirements for
Inter-Autonomous System Routing", RFC1126, SAIC, October 1989.
[Oran 89] Oran, D., "Expert's Paper: The Relationship between
Addressing and Routeing", ISO/JTC1/SC6/WG2, 1989.
[OSPF] Moy, J., "The Open Shortest Path First (OSPF) Specification",
RFC1131, Proteon, October 1989.
[Postel 81] Postel, J., "Internet Protocol", RFC791, DARPA,
September 1981.
[Rekhter 91] Rekhter, Y., "IDRP protocol analysis: storage
complexity", IBM Research Report RC17298(#76515), October 1991.
[Shin87] Shin, K., and M. Chen, "Performance Analysis of Distributed
Routing Strategies Free of Ping-Pong-Type Looping", IEEE Transactions
on Computers, February 1987.
[ST2-90] Topolcic, C., "Experimental Internet Stream Protocol,
version 2 (ST II)", RFC1190, CIP Working Group, October 1990.
[Zaumen 91] 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.
[Zhang 91] Zhang, L., "Virtual Clock: A New Traffic Control Algorithm
for Packet Switching Networks".
Security Considerations
Security issues are not discussed in this memo.
Authors' Addresses
Deborah Estrin
University of Southern California
Computer Science Department, MC 0782
Los Angeles, California 90089-0782
Phone: (310) 740-4524
EMail: estrin@usc.edu
Yakov Rekhter
IBM T.J. Watson Research Center
P.O. Box 218
Yorktown Heights, New York 10598
Phone: (914) 945-3896
EMail: yakov@ibm.com
Steven Hotz
University of Southern California
Computer Science Department, MC 0782
Los Angeles, California 90089-0782
Phone: (310) 822-1511
EMail: hotz@usc.edu