North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: Why doesn't BGP... -Reply

  • From: Vadim Antonov
  • Date: Wed Nov 13 19:12:39 1996

Neal Castagnoli <[email protected]> wrote:

>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.

The routing mentioned was optimal routing of virtual circuits.
It thought of as NP-complete.

There's quite a lot of science (commodity flows, and such) essentially
investigating efficient ways to find quasi-optimal solutions for the

>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?

They simply precompute routing for different scenarios and then just load
it.  Precomputation can take days at pretty big machines.  SS7 is
no magic -- just a protocol.

- - - - - - - - - - - - - - - - -