Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!sunybcs!sbcs!stealth!brnstnd
From: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.protocols.tcp-ip
Subject: Re: Traffic Sensitive SPF Routing is NOT too hard!
Message-ID: <4171@sbcs.sunysb.edu>
Date: 6 Dec 89 04:51:47 GMT
References: <4118@sbcs.sunysb.edu> <6251@cbnewsh.ATT.COM>
Sender: news@sbcs.sunysb.edu
Reply-To: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Distribution: usa
Organization: IR
Lines: 35

In article <6251@cbnewsh.ATT.COM> tds@cbnewsh.ATT.COM (antonio.desimone) writes:
> From article <4118@sbcs.sunysb.edu>, by brnstnd@stealth.acf.nyu.edu (Dan Bernstein):
> > There's absolutely no reason not to use a Bayesian or maximum-entropy
>                      ^^^^^^^^^ including being able to calculate routes
>                                in a human lifetime?

Yup.

> > calculation of the minimal-cost distribution of paths for a given
> > distribution of load. Maximum-entropy routing yields the efficiency of
> > dynamic routing without the instability of dynamic routing. If you're
> > paranoid, recalculate paths every week instead of every month.
> This is a little too heavy on the jargon for me.  Are you suggesting
> a single optimal route?  Or some kind of table-driven routing with
> tables calculated in advance?

You want as little calculation time as possible? Okay: See where the
heaviest amount of your traffic is going. Figure out two routes for it.
Figure out the delay time on each route; use maximum entropy to find the
proper distribution between routes. Remove that destination from your
calculation---and make sure to figure a higher delay on the two
calculated routes. Repeat until you've built a table covering 99% of
your destinations. All of this can be done with a minimal amount of
effort every once in a while. (None of this was my idea.)

The point is not to do a gigantic calculation of the best routes; the
point is to make routing a reasonably stable decision of ``90% of our
traffic here, 10% of our traffic there, all the time,'' rather than an
instable flip-flop between ``128.122 loves me... 128.122 loves me not...
128.122 just crashed... 128.122 loves me...'' Maximum entropy is just a
statistically sound way of keeping any desired variable---say, delay
times, where the current Internet fails so miserably---completely under
control.

---Dan