14-07-2012, 01:10 PM
Maximizable Routing Metrics
Maximizable Routing Metrics.pdf (Size: 80.97 KB / Downloads: 26)
Introduction
The primary task of a routing protocol is to generate
and maintain a tree with the appropriate desirable properties
(e.g., shortest path, maximum bandwidth, etc.). As the
topology and available resources of a network change over
time, this may necessitate that the tree be updated or rebuilt
so that the resulting tree is maximal with respect to a
given routing metric. Within the Internet, the common basis
for IP routing is the shortest path tree. Conventional routing
protocols such as OSPF and RIP utilize link-state and
distance-vector routing in order to build a shortest path tree
that minimizes the latency encounteredwhen routing a datagram
from one location to another. The explosion of traffic
in the Internet due to the World Wide Web, along with the
demand for multimedia applications such as real-time audio
and videoconferencing, is necessitating its rearchitecture so
as to provide more flexible quality of service types that take
into account bandwidth and other network properties in addition
to latency.
In recent years several authors have investigated alternative
routing metrics based on bandwidth and other measures
besides distance. For instance [GS94, GS95, Sch97]
introduced the notion of maximum flow trees and provided
a stabilizing distance-vector based protocol for their construction.
Define the flow of a path as the minimum capacity
of an edge along that path. A maximum flow tree in a
network is a rooted spanning tree of the network wherein
the path from any node to the root is a maximum flow path.
Maximum flow trees were also independently introduced
and studied by [WC95] in the context of the distance-vector
paradigm. See also [CD94] wherein a metric is provided for
depth first search tree construction.
Routing Metrics
A network is an undirected graph where each node represents
a computer, and each undirected edge between two
nodes represents a communication channel between the two
computers represented by the nodes.
To simplify our discussion of routing data messages in a
networkN, we assume that all datamessages that are generated
in all the nodes of N are to be routed to a distinct node
in N. This node is called the root of N. It is straightforward
to extend our discussion to the case where data messages are
routed to arbitrary nodes.
Let N be a network and r be the root of N. In order
to route the data messages generated at all the nodes of N
to node r, a spanning tree rooted at node r, is maintained
in N. When a node generates (or receives from one of its
neighbors) a data message, the node forwards the data message
to its parent in the spanning tree. Each data message
is forwarded from any node to the node’s parent in the tree
until the data message reaches the root of the tree, node r.
Properties of Maximizable Routing Metrics
In this section we identify two important properties of
routing metrics, namely boundedness and monotonicity. It
turns out that these two properties are both necessary and
sufficient for constructing a maximal tree with respect to
any routing metric. For detailed the proofs of the theorems
in this section see [Sch97].
Analysis of IGRP
Both the Inter-Gateway Routing Protocol (or IGRP for
short) and the Enhanced Inter-Gateway Routing Protocol
(EIGRP for short) use an interesting composite routingmetric;
see [Hed91] and [Far93] respectively as well as [Hui95].
In this section we discuss how the IGRP/EIGRP routing
metric is composed and show that it is bounded but not
monotonic.
IGRP was designed with a number of goals in mind.
These included cycle free routing, fast response with low
overhead, multipath routing and the ability to provide multiple
types of service. In IGRP instead of a simple single
metric, a set of path functions is maintained and this set is
used to produced a composite metric. The composite metric
is based upon four path functions and five constants. The
four path functions are as follows:
Concluding Remarks
We developed a theory for deciding, for any routingmetric
and any network, whether the messages in this network
can be routed along paths whose metric values are maximum.
In order for the messages in a network to be routed
along paths whose metric values are maximum, the network
needs to have a rooted spanning tree that is maximal with
respect to the routing metric. We identified two important
properties of routing metrics: boundedness and monotonicity,
and showed that these two properties are both necessary
and sufficient to ensure that any network has a maximal tree
with respect to any (bounded and monotonic) metric.
In related work [Sch97] we have shown that the distancevector
paradigm may be extended to arbitrary bounded and
monotonic metrics such that a maximal tree will always be
built. Furthermore, the presented protocol will still build a
tree for any bounded and nonmonotonic metric such as the
one used in IGRP.