nanog mailing list archives
Re: Why doesn't BGP... -Reply
From: Neal Castagnoli <Neal_Castagnoli () novell com>
Date: Mon, 11 Nov 1996 17:26:13 -0800
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 () 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 - - - - - - - - - - - - - - - - -
Current thread:
- Re: Why doesn't BGP..., (continued)
- Re: Why doesn't BGP... alex (Nov 12)
- Re: Why doesn't BGP... Tine Hutchison (Nov 11)
- Re: Why doesn't BGP... Dorian R. Kim (Nov 11)
- Re: Why doesn't BGP... Vadim Antonov (Nov 12)
- Re: Why doesn't BGP... -Reply Avi Freedman (Nov 12)
- Re: Why doesn't BGP... -Reply Jon Zeeff (Nov 12)
- Re: Why doesn't BGP... -Reply Alex.Bligh (Nov 12)
- Re: Why doesn't BGP... -Reply Larry J. Plato (Nov 16)
- Re: Why doesn't BGP... -Reply Allan Chong (Nov 17)
- Re: Why doesn't BGP... -Reply dave o'leary (Nov 18)
- Re: Why doesn't BGP... -Reply Alex.Bligh (Nov 17)
- Re: Why doesn't BGP... -Reply Curtis Villamizar (Nov 20)
- Re: Why doesn't BGP... -Reply Alex.Bligh (Nov 20)