Why doesn't BGP... -Reply

Tue Nov 12 13:21:18 UTC 1996

> Routing does not use an exponential NP-Complete algorithm (like the
> travelling salesman).  The travelling salesman problem tries to solve the
> cheapest way in which a salesman can visit every one of a set of cities.
>  In fact, routing can be done in order (n) with a bounded metric and
> bounded distance, since it really is only trying to find the cheapest way
> to get to a single destination.
> 
> What I don't know, is why is it that SS7, the telephone routing protocol,
> can do some of the things that are required, like load sharing across
> unequal paths, for example.  Does anyone have any insight into this?
> 
>   --Neal

Quick comment:  You're looking at the computing of routes wrt one router.
I'm suggesting that perhaps we should consider the set of all routers since
we're concerned about spreading load due to the quick communication from
one router to many of every best external-path changing.

But no, I'm not familiar with SS7, and I've not even been thinking deeply
about other routing algorithm possibilities.  I was just suggesting that
people are encouraged to do so...

Avi