Map-Distribution/Explicit Routing Architectures

For QoS Routing and Traffic Engineering

J. Noel Chiappa


This talk covers:

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.


Other Objects

Some other objects which are not intrinsic to a discussion of routing architectures:


Routing Fundamentals


Maps are representations of the fundamental underlying connectivity topology with which routing has to deal. In one simple model, the terminology of graph theory is used, and maps consist of:

More About Maps

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:

Sample Topology

one could decide to use the following set of abstraction boundaries:

Sample Abstraction Boundaries

One can now represent the relationship between those abstractions with the following abstraction hierarchy:

Sample Abstraction Hierarchy

Note that:


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: Each node also has some ``inherent'' attributes, i.e. ones which each node must have:

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: 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 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:

Examples and Non-Examples of Routing Architectures

Routing protocols: Routing architectures:

Routing Architecture Fundamentals

Classes of Routing Architectures - Path Selection

In one of the two fundamental divisions of routing architectures, paths can be selected either: These two form the ends of a spectrum, in between which are a large number of more complex alternatives, such as:

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:

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:

Advantages and Disadvantages of Various Path Selection Mechanisms

Hop-by-hop architectures have the following disadvantages: Explicit architectures have the following advantages:

Advantages and Disadvantages of Various Data Exchanges

DV architectures have the following advantages: MD architectures have the following advantages:

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: QoS routing cannot be done with DV architectures: 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: 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:

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.

Current Routing Work

The Current Internet Routing Architecture

The current Internet routing architecture has the following key characteristics: 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:

Problems With The Current Routing Architecture

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: 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