Maximizable routing metrics

We present a simple theory for maximizable routing metrics. First, we give a formal definition of routing metrics and identify two important properties: boundedness and monotonicity. We show that these two properties are both necessary and sufficient for a routing metric to be maximizable in any net...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2003-08, Vol.11 (4), p.663-675
Main Authors: Gouda, M.G., Schneider, M.
Format: Article
Language:English
Subjects:
Bandwidth
Communication system signaling
Computer networks
Delay
Distributed algorithms
Explosions
Laboratories
Network topology
Networks
Routing (telecommunications)
Routing protocols
Shortest-path problems
Studies
Tree graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a simple theory for maximizable routing metrics. First, we give a formal definition of routing metrics and identify two important properties: boundedness and monotonicity. We show that these two properties are both necessary and sufficient for a routing metric to be maximizable in any network. We show how to combine two (or more) routing metrics into a single composite metric such that if the original metrics are both bounded and monotonic (and, hence, maximizable), then the composite metric is also bounded and monotonic (and, hence, maximizable). We present several applications of our theory. We show that the composite routing metric used in the inter-gateway routing protocol (IGRP) is not maximizable and we show that enhanced IGRP (EIGRP) does not behave as expected for nonmonotonic metrics. We also show that a technique for scalable link-state routing does not work correctly when applied to composite metrics. A common theme throughout the paper is that the intuitions generated by using distance metrics to produce shortest paths do not carry over to other routing metrics.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2003.815294