?

Log in

No account? Create an account
January 22nd, 2008 - Adventures in Engineering — LiveJournal
The wanderings of a modern ronin.

Ben Cantrick
  Date: 2008-01-22 02:10
  Subject:   Binary radix tries for fast CIDR sorting.
Public
  Mood:der uber-nerd
  Tags:  reddit


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.
Post A Comment | | Link



Ben Cantrick
  Date: 2008-01-22 10:49
  Subject:   The occupation of Iraq is sucking the US economy dry.
Public
  Mood:so very not worth saving...
  Music:America, Fuck Yeah! - Team America OST
  Tags:  politics, reddit, usa not worth saving

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!
22 Comments | Post A Comment | | Link






browse
May 2015