January 22nd, 2008

ronin

Binary radix tries for fast CIDR sorting.



Instead of comparing greater-than/less-than at each node, you check to see if a bit is set, branching right if it’s set and left if it isn’t.

Let’s put this in context. Tries are a crucial data structure for Internet routing. The routing problem goes like this:

* You have a routing table with entries for "10.0.1.20/32 -> a" and "10.0.0.0/16 -> b".
* You need packets for 10.0.1.20 to go to "a"
* You need packets for 10.0.1.21 to to to "b"

This is a hard problem to solve with a basic binary tree, but with a radix trie, you’re just asking for "1010.0000.0000.0000.0000.0001.0100" (for 10.0.1.20) and "1010." (for 10.0.0.0). Lexicographic search gives you "best match" for routing. The correspondance between routing and radix tries is so strong that the most popular general-purpose radix trie library (the one from CPAN) is actually stolen out of gated.


http://www.matasano.com/log/1009/aguri-coolest-data-structure-youve-never-heard-of/

There's an even cleverer use for these radix tries, that basically makes it easy to take huge sets of individual IP addresses and reduce them down to approximate CIDR ranges. Which is the "aguri" algorithm mentioned in the URL.
  • Current Mood
    der uber-nerd
  • Tags
stupid

The occupation of Iraq is sucking the US economy dry.


Polls and media outlets constantly tell us that Americans are thinking about domestic issues, not foreign policy and Iraq, as though no connection exists between the strength of our economy and our misadventures overseas. But Americans are smart enough to see the source of our current economic downturn.

A Reddit headline says it all: "Bush, the goddamn idiot, is calling for $145B in goddamn tax relief in the middle of his goddamn war."


http://www.theseminal.com/2008/01/19/im-no-economist-but-some-things-are-obvious/


What's that you say? We should stop spending $9 billion per month to kill tons of people in a far-away land that's no threat to the USA and never was?

That's just crazy talk. The people want their war! SADDAM HAS WMD! BRING IT ON! MISSION ACCOMPLISHED! THE SURGE IS WORKING!