Introduction to Routing
by David M. Piscitello, Bellcore and A.
Lyman Chapin, BBN
reprinted with permission from Connexions
Magazine (Volue 7, No. 9, September 1993), with permission.
Connexions is a Softbank Forums publication
[Ed.: This is an excerpt from Open Systems
Networking: TCP/IP and OSI,
Addison-Wesley Publishers, 1993.]
"Rö´ ting" is what fans
do at a football game, what pigs do for truffles under oak trees
in the Vaucluse, and what nurserymen intent on propagation do
to cuttings from plants. "Rou´ ting" is how one
creates a beveled edge on a table top, or sends a corps of infantrymen
into full-scale, disorganized retreat. Either pronunciation is
correct for "routing," which refers to the process of
discovering, selecting, and employing paths from one place to
another (or to many others) in a network.
The British prefer the spelling routeing,
presumably to distinguish what happens
in networks from what happened to the British in New Orleans in
1814. Since the Oxford English Dictionary is much heavier
than any dictionary of American English, British English generally
prevails in the documents produced by ISO and CCITT; wherefore,
most of the international standards for routing protocols use
the routeing spelling.
Since this spelling would be unfamiliar to many readers, we use
routing in
this article, with apologies to our friends in the British Standards
Institute.
A simple definition of routing is "learning
how to get from here to there." (This is an application of
the classic definition of a route by Shoch, tempered by the very
practical observation by Radia Perlman that routes are both source
and destination dependent;
i.e., that knowing how to get there
isn't enough, you have to know where you are starting from as
well.) In some cases, the term routing
is used in a very strict sense to refer
only to
the process of obtaining and distributing information ("learning"),
but not to the process of using that information to actually get
from one place to another (for which a different term, forwarding,
is reserved). Since it is difficult
to grasp the usefulness of information that is acquired but never
used, we employ the term routing
to refer in general to all the things
that are done to discover and advertise paths from here to there
and to actually move packets from here to there when necessary.
The distinction between routing and forwarding is preserved in
the formal discussion of the functions performed by OSI end systems
and intermediate systems, in which context the distinction is
meaningful.
Source Routing and "Hop-by-Hop"Routing"
The routing operations of finding out how
to get from here to there, and then actually getting from here
to there, can be done in two (very different) basic ways. In source
routing, all the information about how to get from here to
there is first collected at the source ("here"), which
puts it into the packets that it launches toward the destination
("there"). The job of the intervening network (with
its collection of links and intermediate systems) is simply to
read the routing information from the packets and act on it faithfully.
In hop-by-hop routing, the source is not expected to have
all the information about how to get from here to there; it is
sufficient for the source to know only how to get to the "next
hop" (perhaps an intermediate system to which it has a working
link), and for that system to know how to get to the next hop,
and so on until the destination is reached. The job of the intervening
network in this case is more complicated; it has only the address
of the destination (rather than a complete specification of the
route by the source) with which to figure out the best "next
hop" for each packet.
Example
Consider an example, in which "here" is your home in Hopkinton, MA, and "there" is Blueberry Hill Inn in Goshen, VT. If you sit down at home with a set of road maps and figure out exactly which roads and highways connect Hopkinton and Goshen, plotting the route you will follow along this road to that interchange to this junction (etc.), and then get in your car and actually drive along precisely that route to Blueberry Hill, you are performing source routing: if you were a packet, an ordered list of identifiers for links (roads) and intermediate systems (junctions and interchanges) would be encoded in your protocol header. If, on the other hand, you simply climb into your car and begin driving, stopping at every intersection to ask directions or examine the signposts, you are performing hop-by-hop routing: if you were a packet, the identification of your origin (Hopkinton) and final destination (Blueberry Hill) would be encoded in your protocol header. In the first case, your ability to actually get to Blueberry Hill depends on the accuracy of the maps you used and whether or not any of the roads you have selected are closed for repairs; in the second case, it depends on finding enough information at every intersection to enable you to pick the right road to follow to the next.
For the most part, routing in OSI and TCP/IP
networks today is hop-by-hop. Source routing has recently emerged
as an important component of a new set of routing capabilities
(for both OSI and TCP/IP networks) that support complex policies
governing the paths that packets are
permitted to take when more than one organization owns or administers
the equipment and facilities that intervene between "here"
and "there."
The principal criterion of successful routing is, of course, correctness (you do in fact want to get to Blueberry Hill, not Cranberry Bog), but it is not the only criterion. You might prefer to take the most direct route (the one that takes the least time and uses the least fuel), the most reliable route (the one that is not likely to be closed by a heavy snowfall), the most scenic route (the one that follows pleasant country roads rather than busy highways), the least expensive route (the one that follows freeways rather than toll roads), or the safest route (the one that avoids the army's missile testing range). In its most general form, optimal routing involves forwarding a packet from source to destination using the "best" path. What constitutes the "best" path can, of course, become quite a complicated question, as this example shows; networks, like the highway system, have variable costs, transit restrictions, delay characteristics, and residual error rates, and all of these can be more or less important in the determination of what "best" means for a particular source and destination or for a particular packet.
The principal objective of an open systems
routing architecture is not, therefore, to achieve "optimal"
routing-such a thing does not exist in the abstract. Such an architecture
must nevertheless be based on principles that account for what
is happening in the real open systems world of today and tomorrow,
in which computers are being connected to networks at a rate that
more than doubles the number of systems connected to the worldwide
(OSI and TCP/IP) Internet each year. These computers will be connected
using a variety of local, metropolitan, and wide area networking
technologies; the topology of interconnection will change as computers
and the links between them are added and deleted; the networks
will cross every conceivable national and international boundary;
and the computers and networks will be administered by different
organizations, both public and private, each of which may impose
rules (policies) governing (and safeguarding) their use.
Requirements
These observations suggest that an open systems
routing architecture should:
- Scale well
- Support many different subnetwork types and multiple qualities of service
- Adapt to topology changes quickly and efficiently (i.e., with minimum overhead and complexity)
- Provide controls that facilitate the "safe" connection of multiple organizations
It is not likely that the manual administration
of static routing tables (the earliest medium for the maintenance
of internetwork routes, in which a complete set of fixed routes
from each system to every other system was periodically-often
no more frequently than once a week -loaded into a file on each
system) will satisfy these objectives for a network connecting
more than a few hundred systems. A routing scheme for a large-scale
open systems network must be dynamic, adaptive, and decentralized;
be capable of supporting multiple paths offering different types
of service; and provide the means to establish trust, firewalls,
and security across multiple administrations (see ISO/IEC TR 9575,
the OSI Routing Framework).
The architecture of routing in OSI is basically
the same as the architecture of routing in other connectionless
(datagram) networks, including TCP/IP. As usual, however, the
conceptual framework and terminology of OSI are more highly elaborated
than those of its roughly equivalent peers, and thus, it is the
OSI routing architecture that gets the lion's share of attention
here. Keep in mind that most of what is said about the OSI routing
architecture applies to hop-by-hop connectionless open systems
routing in general.
The OSI routing scheme consists of:
- A set of routing protocols that allow end systems and intermediate systems to collect and distribute the information necessary to determine routes
- A routing information base containing this information, from which routes between end systems can be computed. (Like a directory information base, the routing information base is an abstraction; it doesn't exist as a single entity. The routing information base can be thought of as the collective (distributed) wisdom of an entire subsystem concerning the routing-relevant connectivity among the components of that subsystem.)
- A routing algorithm that uses the information contained in the routing information base to derive routes between end systems
End systems (ESs) and intermediate systems
(ISs) use routing protocols to distribute ("advertise")
some or all of the information stored in their locally maintained
routing information base. ESs and ISs send and receive these routing
updates, and use the information that they contain (and
information that may be available from the local environment,
such as information entered manually by an operator) to modify
their routing information base.
The routing information base consists of a table of entries that identify a destination (e.g., a network service access point address); the subnetwork over which packets should be forwarded to reach that destination (also known as the next hop, or "next hop subnetwork point of attachment address"); and some form of routing metric, which expresses one or more of the characteristics of the route (its delay properties, for example, or its expected error rate) in terms that can be used to evaluate the suitability of this route, compared to another route with different properties, for conveying a particular packet of class of packets. The routing information base may contain information about more than one "next hop" to the same destination if it is important to be able to send packets over different paths depending on the way in which the "quality of service" specified in the packet's header corresponds to different values of the routing metric(s).
The routing algorithm uses the information contained in the routing information base to compute the actual routes ("next hops"); these are collectively referred to as the forwarding information base. It is important to recognize that the routing information base is involved in computations that take place in the "background," independent of the data traffic flowing between sources and destinations at any given moment; but the forwarding information base is involved in the real-time selection of an outgoing link for every packet that arrives on an incoming link and must therefore be implemented in such a way that it does not become a performance-killing bottleneck in a real-world intermediate system (router).
Figure 1 illustrates the decomposition of
the OSI routing function as it is represented in ISO/IEC TR 9575,
the OSI Routing Framework.
Figure 1: Decomposition of the OSI Routing Function
No system-certainly not an end system, which
is supposed to be devoted primarily to tasks other than routing-can
maintain a routing information base containing all the information
necessary to specify routes from any "here" to any "there"
in the entire global Internet. Neither is it possible to design
a single routing protocol that operates well both in local environments
(in which it is important to account quickly for changes in the
local network topology) and in wide area environments (in which
it is important to limit the percentage of network bandwidth that
is consumed by "overhead" traffic such as routing updates).
Three Tiers
The OSI routing architecture is consequently hierarchical, and is divided into three functional tiers:
- End-system to intermediate-system routing (host-to-router), in which the principal routing functions are discovery and redirection.
- Intradomain intermediate-system to intermediate-system routing (router-to-router), in which "best" routes between ESs within a single administrative domain are computed. A single routing algorithm is used by all ISs within a domain.
- Interdomain intermediate-system to intermediate-system routing (router-to-router), in which routes are computed between administrative domains.
Figure 2: OSI Routing Architecture
In Figure 2, end systems discover and communicate
with the intermediate systems to which they are directly connected
(by dedicated or dial-up point-to-point links or by multiaccess
local or metropolitan area networks) in the outermost level of
the hierarchy; intermediate systems communicate with other intermediate
systems within a single routing domain in the levels of the hierarchy
next closest to the center; and in the center, intermediate systems
communicate with other intermediate systems across routing domain
boundaries.
The decomposition illustrated in Figure 2
is not arbitrary. At each level of the hierarchy, a different
set of imperatives governs the choices that are available for
routing algorithms and protocols. In the OSI routing architecture,
end systems are not involved in the distribution of routing information
and the computation of routes, and hence, the participation of
end systems in routing is limited to asking and answering the
question "Who's on this subnetwork with me?" (On broadcast
subnetworks such as most local area networks, this inquiry typically
begins with the more or less Cartesian assertion "I broadcast
[multicast], therefore I am . . .")
Mechanism
Within a single routing domain, the hegemony of a single administration (and a correspondingly consistent set of routing policies) argues in favor of using a single routing protocol, i.e., one which is based on a link-state algorithm, which provides every intermediate system with complete knowledge of the topology of the routing domain. Between routing domains that may be controlled by different (possibly even antagonistic) administrations, issues of security (including control over the extent to which information about the topology of one domain is propagated to other domains) outweigh most others, and the argument in favor of distributing complete topology information to all intermediate systems, so compelling when selecting an intradomain routing protocol, misfires for the very reason that concealing or withholding information is often as important as distributing it. It is important to recognize that the analysis that leads to one conclusion in the intradomain context does not necessarily hold when it is transplanted to the interdomain context.
Which is better?
Fortunately, with respect to routing, it has
not been difficult to refute the simplistic argument that if link-state
routing is the best choice for the intradomain level it must be
the best choice for the interdomain level. Ten years ago, however,
a similarly simplistic argument destroyed the opportunity for
OSI to standardize one of the best features of the TCP/IP internetwork
architecture-the combination of a connectionless (datagram) internetwork
protocol (which could be operated efficiently over any underlying
network technology, whether based on datagrams or virtual circuits)
with a connection-oriented end-to-end transport protocol. The
OSI position at that time was that a connection-oriented service
at the transport layer "naturally" mapped to a connection-oriented
service at the network layer, as if this were something inherent
in the very architecture of a layered model. The OSI community
wasted years dealing with this red herring, which was intended
to divert attention from the fact that a large segment of the
OSI community believed that the service provided by the network
layer was an end-to-end transport service. The TCP/IP community,
unencumbered by such nonsense, happily expanded to fill the resulting
vacuum.
ES-IS routing establishes connectivity and reachability among ESs and ISs attached to the same (single) subnetwork. Limiting the scope of routing in this manner allows an ES to play a simple role in the overall routing process and leaves most of the ES's resources available to support end-user applications (which is, presumably, the raison d'être of an ES). ESs are commonly attached to multiaccess subnetworks, such as IEEE 802 local area networks (LANs) and metropolitan area networks (MANs), creating topologies that are both highly connected and densely populated (with ESs); the protocols and algorithms that are appropriate for routing in this environment are very different from those that are appropriate for routing in the wide area environments served by intermediate system to intermediate system routing.
At this level of routing, the two critical
(closely related concerns are discovery (who is out there?) and
reachability (with whom is it possible to communicate?) Within
a single subnetwork, an ES is one "hop" away from any
ES or IS connected to the same subnetwork, so the only information
an ES needs in order to reach either destination ESs on the same
subnetwork or ISs that will forward packets to destination ESs
on other subnetworks is the "hardware interface" or
subnetwork point of attachment
(SNPA) addresses of the ESs and ISs
attached to the subnetwork.
Intradomain IS-IS routing establishes connectivity among intermediate systems within a single authority, the administrative domain. An administrative domain is composed of one or more routing domains. Each routing domain consists of a set of ISs and ESs; ISs within a routing domain use the same routing protocol, routing algorithm, and routing metrics.
At this level of routing, the critical concern
is the selection and maintenance of best paths among systems within
the administrative domain. ISs are concerned about route optimization
with respect to a variety of metrics and about the trade-off between
(1) the cost of distributing and maintaining routing information
(which increases as the granularity of the information approaches
"a separate route for every source/destination pair for every
value of the routing metric[s]") and (2) the cost of actually
sending data over a particular route (which increases if the available
routing information causes data to be sent over a "suboptimal"
route).
Interdomain IS-IS routing establishes communication
among different administrative domains, enabling them to control
the exchange of information "across borders." In most
circumstances, it is common to think of routing as something that
tries to make it "as easy as possible" for two systems
to communicate, regardless of what may lie between them. Interdomain
routing, on the other hand, plays the paradoxical role of facilitating
communication among open systems for which communication is a
(politically) sensitive activity, involving issues of cost, accountability,
transit authorization, and security that can produce highly counterintuitive
answers to what look like simple technical questions. (Within
the purview of a single network administration, it is considered
to be a very good and useful thing for the network to automatically
reconfigure itself to route traffic around a failed link onto
an alternate path. In an interdomain configuration involving mutually
suspicious network administrations, however, it may be the worst
possible thing for the network to switch traffic to an alternate
path "automatically" without first clearing the change
with the legal departments of both parties. This conundrum has
led one of the authors to claim that the only large-scale interdomain
routing protocol that is likely to be deployed in the near future
will be implemented as an army of lawyers on bicycles.)
At this level of routing the critical concern is the maintenance and enforcement of policies that govern, for example, the willingness of an administrative domain to (1) act as a transit domain for traffic originating from and destined for other administrative domains, (2) receive information from sources outside the administrative domain and deliver them to destinations within the administrative domain, and (3) forward information from within the administrative domain to destinations outside the administrative domain. Policies concerning 1, 2, and 3 can be derived on the basis of cost, access control, and regulatory concerns. The hierarchical relationship of the OSI routing protocols is depicted in Figure 3.
Within the OSI routing framework, it is possible
for different routing domains within a single administrative domain
to run different intradomain routing protocols, and it is also
possible to operate different ES-IS protocols within different
areas of the same routing domain. At present, however, OSI defines
only one standard routing protocol for each of the three levels
of the hierarchy.
Figure 3: Hierarchical Relationship of OSI
Routing Protocols
TCP/IP Routing Architecture
Through a process of evolution-in which some of the ideas that led to features of the OSI routing architecture originated with TCP/IP, developed into OSI standards, and returned to be adopted by the TCP/IP community-the TCP/IP routing architecture today is almost identical to the OSI architecture. The TCP/IP world began around a single network (which didn't require much in the way of routing), and grew into the "core"-based ARPANET, with individual networks connected to a single backbone (composed of "core gateways") as "stubs." Multiple organizations began offering IP transit services, and for a time, it was difficult to tell whether the Internet was a "mesh" of backbone networks or a hierarchy. A three-tier hierarchy was gradually introduced as the NSFNET grew and supplanted the ARPANET: the NSFNET served as a national backbone, and midlevel networks or "regionals" provided transit services to and from the IP networks whose directly connected hosts served as the sources and sinks of Internet traffic.
Today, the
TCP/IP routing architecture looks
very much like the OSI routing architecture. Hosts use a discovery
protocol to obtain the identification of gateways and other hosts
attached to the same network (subnetwork). Gateways within autonomous
systems (routing
domains) operate an interior gateway protocol
(intradomain routing protocol), and
between autonomous systems, they operate exterior
or border gateway protocols
(interdomain routing protocols. The details are different but
the principles are the same.
DAVID M. PISCITELLO
works on broadband data services-Frame Relay, SMDS, Cell Relay/ATM-and
network management at Bellcore. Involved in OSI-TCP/IP development
since 1979, he participated in OSI/Internet standards development
and has written several OSI and Internet standards including ISO
CLNP and RFC 1209. A member of the IESG, he is the Internet area
director for the IETF.
A. LYMAN CHAPIN
graduated from Cornell University in 1973 with a B.A. in Mathematics,
and spent the next two years writing COBOL applications for Systems
& Programs (NZ) Ltd. in Lower Hutt, New Zealand. He joined
the newly-formed Networking group at Data General Corporation
in 1977. He moved to Bolt Beranek and Newman in 1990 as the Chief
Network Architect in BBN's Communications Division. He is the
chairman of ANSI-accredited task group X3S3.3, responsible for
Network and Transport layer standards, since 1982; chairman of
ACM SIGCOMM since July of 1991; and area director for Internet
standards and procedures of the IESG.
________________________________________
Adapted from Open Systems Networking: TCP/IP
and OSI by
David M. Piscitello and A. Lyman Chapin. Copyright © 1993
by Addison-Wesley Publishing Co. Used with Permission. Call 1-800-238-9682
for more information on this book.