From: Kevin Wampler (wampler@cs.washington.edu)
Date: Sun Oct 31 2004 - 22:32:18 PST
In "The Revised ARPANET Routing Metric" The authors describe an adjustment
to the previous metric used in dynamic routing to minimize the delay of
packets in a network. This change is motivated by the observation that
the D-SPF algorithm become unstable under congested network conditions.
In this paper I particularly enjoyed that the authors tied the local
routing changed they made to the large scale network dynamics they
induced. This seems to be a particularly effective way to attempt to gain
an understanding of and limit equilibrium states in a network. In this
case it seems to work well, as HN-SPF offers substantial improvements over
D-SPF in high congestion cases. It strikes me, however, that the better
direction to go in the other way, to start at a model of desirable
dynamics and to model a routing metric to achieve it (perhaps this is what
was done and the paper just presents the metric first however).
There are some parts of this paper that are certainly showing their age.
In particular, the authors state that each router has complete knowledge
of the topology of the network and used this information to make routing
adjustments. Today I would imagine that this is prohibitively expensive
for large networks. Given this, it is necessary to attempt to attempt to
optimize routing with only local information. I would guess that
heuristics such as ant-colony optimization might be useful here (I'm
unaware of how it's currently handled).
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 22:32:19 PST