the O(N^2) problem

Edward B. DREGER eddy+public+spam at noc.everquick.net
Mon Apr 14 00:36:07 UTC 2008


Bottom line first:

We need OOB metadata ("trust/distrust") information exchange that scales
better than the current O(N^2) nonsense, yet is not PKI.

And now, the details... which ended up longer reading than I intended.
My apologies.  As Mark Twain said, "I didn't have time to write a short
letter, so I wrote a long one instead." :-)

When it comes to establishing trust:

* The current SMTP model is O(N^2);

* I posit that the current IP networking model is sub-O(N);

* PKI models are pretty much O(1).

Polynomial-order just doesn't scale well.  It's mathematical fact, and
particularly painful when the independent variable is still increasing
quickly.

Many operators seem to reject PKI as "power in too few hands".  I'll not
disagree with that.

Conclusion:  What we need is something that scales better than O(N^2),
but that is not as "few trusted keepers of the world" as PKI.

Let's look to one of the current hot tickets: social networking.  Who is
whose friend, who is in whose network, blah blah blah.  (The junior high
students seem to grok the concept of trust being semi-transitive!)

Let's also draw upon operational lessons from a couple old-timers.  I
recall using a critter known as "NNTP".  And once upon a time, before my
days on the Internet, lived a funny little beast called "UUCP".

We track email quality from all mailservers that hit us.  I can whip up
a list of MXes/organizations that I'm willing to "trust" -- and let's
leave that term imprecisely-defined for now.

Here's what I propose:

Establish a "distrust protocol".  Let path weight be "distrust".  The
"trust path" is of secondary importance to "path weight", although not
completely irrelevant.  SMTP endpoint not in graph?  Fine; have some
default behavior.

Let _trust_ be semi-transitive, a la BGP -- a technology that we know,
understand, and at least sort of trust to run this crazy, giant network
that dwarfs even a 50M-user provider.

Let actual _content_ still be end-to-end, so that we do not simply
reincarnate NNTP or UUCP.

Alternatively:

I'm open to other suggestions.

Or, there's plan "C":

We continue to argue, banter, carp, fuss, grumble, moan, swear, whine,
et cetera (I decided against running the alphabet) over the problem.
Hey, it's worked/working great so far, right?


Eddy
--
Everquick Internet - http://www.everquick.net/
A division of Brotsman & Dreger, Inc. - http://www.brotsman.com/
Bandwidth, consulting, e-commerce, hosting, and network building
Phone: +1 785 865 5885 Lawrence and [inter]national
Phone: +1 316 794 8922 Wichita
________________________________________________________________________
DO NOT send mail to the following addresses:
davidc at brics.com -*- jfconmaapaq at intc.net -*- sam at everquick.net
Sending mail to spambait addresses is a great way to get blocked.
Ditto for broken OOO autoresponders and foolish AV software backscatter.



More information about the NANOG mailing list