Map-Distribution/Explicit Routing Architectures
For QoS Routing and Traffic Engineering
J. Noel Chiappa
Introduction
This talk covers:
- An overview of the fundamentals of routing, specifically a
review of the various basic classes of routing architectures.
- The advantages and disadvantages of each class of routing architecture.
- Why the current prevalent functional goals for routing (such as the
ability to provide paths that meet QoS constraints, or allocate paths for
traffic aggregates in a way that optimizes use of network resources) are
really only capable of being provided by an approach which is fundamentally
different from most familiar current routing technologies (e.g. RIP, BGP).
Architectural Discussion Fundamentals
Terminology and Concepts
I am far from thinking that nomenclature is a remedy for every defect in art
or science: still I cannot but feel that confusion of terms generally springs
from, and always leads to, confusion of ideas.
-- John Louis Petit, Architectural Studies in France, 1854
Names and Objects
We must also separate out the name for a thing from the
object, the thing itself, to which those names refer.
We must also separate out the form of the name for a thing from
the generic concept of a name for the thing.
One or more possible names or types of names (i.e. namespaces) can
exist for each object; sometimes, a single namespace is used to refer to two
different types of object. Different namespaces may or may not have
structure; the structure is there to help something else do its job.
Objects
- Network:
- A collection of interfaces which have some useful relationship:
- Any interface can send directly to any other without going
through a router;
- A topology aggregate (to help routing scale).
- Route or Path:
- A path from one place in the network to another;
- The term route may also mean a routing table entry.
- To prevent confusion, the term path is preferred here.
- Node:
- A host or router;
- In routing technical terminology, an element of a map (which
is represented as a graph, with nodes and arcs).
- Interface:
- A place to which a producer or consumer of packets connects to
the network; a ``network attachment point''.
- The place towards which the system of routers directs packets.
Other Objects
Some other objects which are not intrinsic to a discussion of routing
architectures:
- Host:
- An actual machine which is the source or destination of traffic,
through some interface.
- Router:
- A device which interconnects various elements of the network,
and forwards traffic based on the internetwork header.
- Switch:
- A device which interconnects various elements of the network, and
forwards traffic based on something other than the internetwork
header. Switches may be either:
- Per-packet: the switch examines each packet and forwards it to any one
of a number of output ports based on the packet header.
- Bit-stream: the switch passes an entire bit stream from one interface to
another without examining the individual packets within the stream.
Names
- Address:
- A structured name for either a network interface or topology
aggregate:
- One namespace is used to name two different kinds of
object - always a source of potential confusion!
- The structure is used by the routing to help it scale:
- Topologically related items have to be given related addresses.
- Allows the number of destinations tracked by the routing.
to be minimized
- Allows quick location of the named interface on a map.
- DNS names:
- A structured human usable name for a host, etc.
- The structure is used to facilitate the distribution and lookup.
Routing Fundamentals
Maps
Maps are representations of the fundamental underlying connectivity topology
with which routing has to deal.
- In other words, if there is no link between nodes A and B, the routing
system cannot send traffic directly from A to B.
In one simple model, the terminology of graph theory is used, and
maps consist of:
- Nodes (which have an open-ended list of attributes);
- Arcs (which are uni-directional links which connect nodes, and
cannot have attributes; they simply indicate connectivity).
More About Maps
- In this model, a node in a map can represent some part of the physical
network. It may be as large or as small as desired: a node can represent an
entire ISP, or a single interface.
- A contiguous portion of the graph which represents the entire physical
network may be represented by either a single node, or a set of nodes,
either of which is an abstraction for that part of the network.
- In other words, abstractions can be recursive.
Abstraction Hierarchies
An abstraction hierarchy is the name for the naming structure which
creates a nested set of abstractions for parts of a network. These
abstractions consist of naming boundaries around (generally contiguous) parts
of the network.
This set of abstractions is what lies beneath the familiar hierarchical
addressing structure for a given topology, which is used to create hierchical
addresses for both interfaces (i.e. places where things are connected to the
network), as well as topological aggregates of parts of the network.
For example, given the following physical network topology:
one could decide to use the following set of abstraction boundaries:
One can now represent the relationship between those abstractions
with the following abstraction hierarchy:
Note that:
- For a single actual topololgy, one can create a number of different
abstraction hierarchies, depending on where one draw the abstraction
boundaries.
- The topology, and an abstraction hierarch for it, are very different
things! Much confusion has been engendered by trying to draw both things
in one picture!
Attributes
The nodes in the map may be characterized by an open-ended
list of attributes, which can include many different kinds
of information. Attributes might include:
- Bandwidth
- Delay
- Delay variance
- Error rate
- Cost
- Allowed users (e.g. government only)
Each node also has some ``inherent'' attributes, i.e. ones which each node
must have:
- The connectivity of the node
Routing Tables
A routing table is a database (usually in a router or per-packet switch)
which is used to make decisions about where to send traffic. It takes the
form of a linear array, indexed by destination address, which provides a
number of pieces of information:
- The outbound interface to send the packet over;
- The next entity to send the packet to (if the next hop is not the
final destination);
- Other information used to calculate paths.
Here's a sample routing table, for node A.1 from the previous sample
topology:
Destination |
Next Hop |
Outbound Interface |
Other |
A.2 |
1 |
A.2 |
|
A.3 |
2 |
A.3 |
|
B |
1 |
A.2 |
|
Routing and Addressing Architectures
What is a ``Routing and Addressing Architecture''?
An addressing architecture includes:
- A system of naming networks, interfaces, topology aggregates, etc.
A routing architecture is not simply a protocol (i.e. a
set of packet formats, and instructions on how to process them). Rather, it
considers the entire question of how the network organizes the handling of
user traffic.
A routing architecture includes:
- A way of exchanging information as to where these named things are;
- A way of computing and selecting paths between sets of communicating
entities;
- A way of causing traffic to take these paths.
Examples and Non-Examples of Routing Architectures
Routing protocols:
Routing architectures:
- The entire current collection of BGP and all the IGP's, along with the
specifications for how they interact, is a routing architecture (albeit a
rather ad-hoc one, not to mention one without many desirable capabilities)
- Nimrod is a routing architecture
Routing Architecture Fundamentals
Classes of Routing Architectures - Path Selection
In one of the two fundamental divisions of routing architectures, paths
can be selected either:
- Fully distributed: each node along the path makes a completely
independent decision as to which node user traffic will go through next;
this is sometimes called hop-by-hop (HbH) path selection.
- Explicit: one node selects the entire path.
- Sometimes the entity which makes the selection is the source of the
traffic (in which case the term source routing is used).
- For the general case, the term explicit (E) is to be preferred to
source routing, as this is often taken to have the limited meaning
that the host sending the packet must compute the entire route, which is then
included in every packet.
These two form the ends of a spectrum, in between which are a large number
of more complex alternatives, such as:
- Hierarchical explicit: i.e. one node picks the entire path, but in
terms of high-level abstractions; paths across those abstractions are
selected by other entities.
- Hierarchical distributed: this is exit-router based routing; i.e.
at any given level of abstraction, no node has a more significant
responsibility in selecting the path than any other node, but a node at a
lower level cannot override the higher layer's choice of the next high-level
abstraction to transit.
Classes of Routing Architectures - Data Types
Along another axis, there are two broad classes of routing architectures,
depending on what kind of data is being passed between the nodes:
- Destination Vector (DV) architectures, where nodes pass sets of
(destination, information) n-tuples (i.e. basically, a routing table) to
immediate neighbours, and this information is used directly to construct
routing tables. They are characterized by:
- The selection of the path from a given source to a given destination
is usually evenly distributed; i.e. at any given level of
abstraction, no node has a more significant responsibility in
selecting the path.
- In the course of running the algorithm to select the path,
intermediate results in that computation are passed between independent
nodes.
- Map Distribution (MD) architectures, where nodes distribute
information about their immediate surroundings through the network; this
information is used to construct topology maps. They are characterized
by:
- The selection of the path can be either localized or hop-by-hop, but
in either case the actual computation is not fully distributed.
- Thus, no intermediate results are passed around between nodes.
- The routing computation may easily be delayed until the path is
needed.
- A path-selection algorithm can inspect the map directly to select
a path.
- Alternatively, from the topology map, another algorithm can construct a
classical routing table.
Combining the Two
These two orthagonal axes define a 4-way classification of routing
architectures, one which is not, however, fully populated. The three main
classes of routing architecture (along with examples of each), are:
- DV-HbH - the classic initial routing architecture; used in:
- the original ARPAnet dynamic routing
- RIP
- IGRP
- BGP
- etc.
- MD-HbH - a newer routing architecture, used in:
- first instance - the ``new'' ARPAnet dynamic routing
- IS-IS
- OSPF
- MD-E - the direction of recent research in routing, and the likely
future direction of routing work. Some examples include:
- IDPR (RFC-1478, 1993)
- The first MD-E routing architecture, mostly for Inter-AS (EGP)
applications.
- Nimrod (RFC-1992, 1996)
- A follow-on to IDPR.
- Enhanced to take over both the EGP and IGP functionality, and with better
tools for doing and managing abstraction.
- PNNI
Advantages and Disadvantages of Various Path Selection Mechanisms
Hop-by-hop architectures have the following disadvantages:
- They effectively require global consistency in
the routing databases to prevent routing loops.
Explicit architectures have the following advantages:
- They trivially allow the testing and deployment of new path-selection
algorithms.
- They can allow the users much more control over the path of
their traffic.
- They are more naturally immune to loops.
- They can be made much more robust.
- They can be secured against almost all attacks.
- Some optimization problems cannot be solved by local optimization
algorithms, which means no HbH architecture can handle them.
Advantages and Disadvantages of Various Data Exchanges
DV architectures have the following advantages:
- They require less computing and storage overhead than MD architectures.
MD architectures have the following advantages:
- They are much more practical to secure against many attacks.
- They can react more quickly to changes (in topology, etc.).
- Their stabilization time is not only shorter on average, but
also much more bounded.
- They require less bandwidth to react to significant changes in
network topology.
- They allow the incremental deployment of new attributes.
- Constraint-based routing (which includes most QOS routing) is only
practical with MD architectures.
- Highly secure routing is only practical with MD architectures.
QoS Routing and Traffic Engineering
What are QoS Routing and Traffic Engineering?
QoS Routing means selecting paths on multiple constraints, using
constraints related to service levels (e.g. bandwidth, delay), not just
on a single simple metric like the number of hops.
Traffic Engineering means allocating paths for traffic
aggregates in such a way that an optimal use is made of network
resources.
Routing Architectures for QoS
QoS routing cannot be done with classic HbH architectures:
- Some constraints (e.g. overall delay) cannot be calculated in a
hop-by-hop fashion.
- Unless path selection decisions are tightly coordinated (i.e. no
partially-deployed attributes), loops can result.
QoS routing cannot be done with DV architectures:
- Each combinations of constraints requires a separate routing table,
leading to combinatorial explosion.
MD-E architectures are the only ones suitable for QoS.
Load-Based Routing
QoS can also imply load-based routing, where traffic patterns change
in response to offered load. The increased dynamicity of LBR make it more
susceptible to oscillatory behaviour:
- Distributed computations of DV architectures are harder to stabilize.
- Generally, with Explicit architectures, paths are fixed, again
increasing resistance to oscillatory behaviour.
Overall, MD-E architectures are more suitable for LBR.
Routing Architectures for TE
TE is an optimization process, and getting good optimization with
local traffic placing algorithms can be difficult; global algorithms
can do better.
There are several different aspects of local:
- Local knowledge only (i.e. routing tables, as opposed to a
complete map).
- Local control only (i.e. the ability to select the next hop only,
not the complete path).
MD-E architectures, which are capable of being more global along both axes,
are thus much better suited to TE.
Also, simply routing each aggregate independently may not produce a pattern
of traffic flows which the available network resources can support.
- For such cases, a centralized allocation algorithm, not a distributed
one, is needed.
- Such a centralized algorithm must have both complete knowledge (i.e.
MD) and complete control (i.e. Explicit).
Current Routing Work
The Current Internet Routing Architecture
The current Internet routing architecture has the following key
characteristics:
- Destination Vector type
- Hop-by-hop path selection
Do not be misled by the deployment of IGP's which use MD architectures,
such as OSPF and IS-IS, in limited areas of the network. The
overall operation of the current Internet routing architecture is DV:
- The data passed between AS's consists of routing tables, not maps.
- The path across a number of AS's is selected piecemeal, not in a
unitary fashion. (I.e. if downstream ISP Y has two paths to destination
site D, upstream ISP X can't select which of those two it wants to use; all
it can do is give the traffic to Y, which picks which one it will use.)
Problems With The Current Routing Architecture
- The overall DV-HbH model does not allow a lot of desirable features:
- User control of paths
- QoS Routing
- Load-Based Routing
- Traffic Engineering
- Not very robust.
- Secured only by extensive configuration, which limits the flexibility,
especially in response to failure.
- Poor tools for doing abstraction, and controlling it.
- The simplistic EGP/IGP split.
Recent Routing Work
As mentioned, the Internet engineering community has been experimenting with
MD/E architectures for some time. They have not gotten wide-spread
deployment, for two likely reasons:
- They are very different from existing routing protocols, particularly
the DV-based system which people are most familiar with, and with the
incredible pressure to provide service, it was easier to stay with what
was familiar, and known to work.
- The MD/E systems which were done are more complex, because they provide
greater capabilities, but there was apparently not enough need for the
capabilities they provide.
Recently, work in the MPLS community has started to explore MD/E
architectures (e.g. QOSPF together with an LSP setup protocol). However, the
work (as with most work in the MPLS area) is poorly integrated with the
internetwork layer (due in large part to ossification in the community
responsible for the internetwork layer as a whole).
Back to JNC's home page