From: Chandrika Jayant (cjayant@cs.washington.edu)
Date: Mon Nov 01 2004 - 07:59:51 PST
"The Revised ARPANET Routing Metric"
Written by Atul Khanna and John Zinky
Reviewed by Chandrika Jayant
This paper proposes a new routing metric, Hop-Normalized SPF
(HN-SPF).
The old routing metrics performed well under light network loads but
were unstable and inefficient under heavily loaded networks. D-SPF
resulted in routing oscillations because it was assumed that the packet
delay on a link predicted the link delay on all nodes re-routing based
on that. This works decently under light loads because queing delay is
negligible, and with moderate traffic as well. Under heavy traffic
loads, queuing delay becomes a big factor in link delay, so this
algorithm fails and routing oscillations follow.
A new link cost metric normalizes the link cost in terms of hops.
Greediness is fine when a PSN chooses its path, but with higher traffic
these routes could interfere- therefore the average route should have a
good path instead of best path to every route. It is impressive how such
a "small" change to the old algorithm produced such drastic
improvements. However, maybe the authors shouldn't have stopped with
this and tried to, or mentioned, different ways the underlying structure
of the algorithm could be changed for better results. Otherwise, they
could have defended it more.
I wish that the authors had discussed more of the limits of HN-SPF. They
mention that it will be most effective when the network consists of
several small node-to-node flows. They should have discussed the
implementation of multi-path routing. They also assume that each router
has complete topological knowledge of the network. Is this realistic
today?
This paper is relevant because without good and efficient routing, the
Internet is useless. The paper is coming from the perspective of
ARPANET, but the authors note that the metric is applicable to any
network and has been deployed in others. I think the next step would be
to defend the underlying algorithm that the authors built over, instead
of just making smaller steps in improvement.
This archive was generated by hypermail 2.1.6 : Mon Nov 01 2004 - 08:00:08 PST