Why doesn't BGP... -Reply

Tue Nov 12 01:26:13 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

>>> Avi Freedman <freedman at netaxs.com> 11/09/96 05:31am >>>

I understand that IOS 12.0 will solve the travelling salesman problem
for arbitrary number of cities.  Seems they had to find a way to solve
NP-complete problems in sub-exponential time in order to give us better
algorithms for guaranteed-optimal routing.

Anyway, sorry to be snide - any suggestions you have about algorithms
for exchanging routing data between (or inside of) providers that also
takes into account link size and perhaps hop-count, as opposed to
just AS-PATH, are welcome at the next IETF meeting.

Avi