Hi Tony,
Some idle thoughts on the routing quality section..
Is it worth removing the "maximum" from the stretch definition, given
that stretch can be defined for various cases, such as maximum and
average? E.g.:
"The stretch of a routing scheme is a proportional measure of the
increase in path length inherent to that scheme, relative to the
length of the shortest path, for a pair of nodes in a network.
Stretch often is expressed as the maximal, worst-case ratio a scheme
will produce, have over all networks. However other measures of
stretch may be interesting, such as the average case."
References, as per previous email from Stephen and myself: see
Kleinrock, Kamoun, "Hierarchical Routing for Large Networks", '77
(which looks at the average case); and Peleg & Upfal, "A trade-off
between space and efficiency for routing tables", '89, might be
weightier.
Also, this goal:
"A solution is strongly desired to provide routing quality equivalent
to what is available today or better."
simply may not be achievable if the stretch of BGP on the internet
today is as close to 1 as can be gotten - which is not an
unreasonable thing to think (??). In that case, according to the
results of the Peleg paper, then any new routing scheme that
decreases the size of the per-node routing table must inevitably also
increase the stretch factor.
Perhaps therefore it should be slightly weaker, e.g.:
"A solution is strongly desired to provide routing quality
equivalent to what is available today, or as close as possible,
if not better."
?
e.g. to get a 40% to 60% reduction in table sizes would imply a
stretch in the region of 2 to 3 (for foreseeable sizes of the
internet).
regards,
--
Paul Jakma [email protected] Key ID: 64A2FF6A
Fortune:
One of the worst of my many faults is that I'm too critical of myself.
_______________________________________________
rrg mailing list
[email protected]
http://www.irtf.org/mailman/listinfo/rrg
