* Iljitsch van Beijnum:
On 10-okt-04, at 19:46, Florian Weimer wrote:
A stateless longest-prefix matching algorithm which costs only a few
dozen cycles (or very few cache misses) per lookup (even for random
addresses), provides fast routing table inserts and reasonably
efficient deletes is not exactly trivial to come up with. A few
people have been looking for something that is reasonably fast and not
covered by patents yet, but I'm not aware of any interesting
Are you saying that the patricia tree / trie datastructures and/or
their search methods are patented?
No, their performance is just less than stellar (at least for the trie
algorithms that have been around since the mid-80s).
I was under the impression that this stuff came from the academic
world and as such would be unencumbered by patents.
Other routing algorithms come indeed from the academic community, but
are covered by patents nevertheless. I can't speak for the U.S., but
here in Germany, we are aggressively pushing for more patent output
from universities. A few years ago, law was even changed in a way
that supervising professors no longer can decide if they want to
patent a discovery (sorry, "invention") or not, it's now up to the
Ietf mailing list