[103771] in North American Network Operators' Group
Re: the O(N^2) problem
daemon@ATHENA.MIT.EDU (Owen DeLong)
Mon Apr 14 01:20:22 2008
Cc: nanog@merit.edu
From: Owen DeLong <owen@delong.com>
To: "Edward B. DREGER" <eddy+public+spam@noc.everquick.net>
In-Reply-To: <Pine.LNX.4.62.0804140002490.16365@pop.ict1.everquick.net>
Date: Sun, 13 Apr 2008 22:04:45 -0700
Errors-To: owner-nanog@merit.edu
--Apple-Mail-54-61535649
Content-Type: text/plain;
charset=US-ASCII;
format=flowed;
delsp=yes
Content-Transfer-Encoding: 7bit
On Apr 13, 2008, at 5:36 PM, Edward B. DREGER wrote:
>
> 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.
>
Not sure why PKI should be excluded, but, so far, this is too abstract
to know what the question is...
> 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 don't see SMTP as even a "trust" model since there's pretty much
nothing trustworthy in SMTP.
> * I posit that the current IP networking model is sub-O(N);
>
Again, I'm not seeing IP as a trust model, but, YMMV.
> * 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.
>
Sure.
> Many operators seem to reject PKI as "power in too few hands". I'll
> not
> disagree with that.
>
Depends on the PKI. For example, the PGP/GPG Web of Trust concept
pretty much lets each individual build their own trust model to whatever
O(x) they choose where greater values of x require more effort and also
provide greater security/trust granularity and lower values of x involve
greater trust of others that you claim you can trust and less direct
effort
on your part.
>
> 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".
>
I remember UUCP. It was pretty much O(n^2).
> 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.
>
Uh, OK. Starting to understand what the question might be aiming
towards.
> 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.
>
Now I'm lost again. You've mixed so many different metaphors from
interdomain routing to distance-vector computaton to store-and-forward
that I simply don't understand what you are proposing or how one
could begin to approach implementing it or what problem you seem
to think it solves (although it sort of seems like you're wanting to
attack
the trustworthiness of email to battle SPAM through some mechanism
that depends only on the level of trust for the (source, arrival path)
tuple from whence it came.
What am I missing?
Owen
--Apple-Mail-54-61535649
Content-Type: text/html;
charset=US-ASCII
Content-Transfer-Encoding: quoted-printable
<html><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =
-webkit-line-break: after-white-space; "><br><div><html>On Apr 13, 2008, =
at 5:36 PM, Edward B. DREGER wrote:</html><br =
class=3D"Apple-interchange-newline"><blockquote =
type=3D"cite"><div><br>Bottom line first:<br><br>We need OOB metadata =
("trust/distrust") information exchange that scales<br>better than the =
current O(N^2) nonsense, yet is not PKI.<br><br></div></blockquote>Not =
sure why PKI should be excluded, but, so far, this is too =
abstract</div><div>to know what the question =
is...</div><div><br><blockquote type=3D"cite"><div>And now, the =
details... which ended up longer reading than I intended.<br>My =
apologies. As Mark Twain said, "I didn't have time to write a =
short<br>letter, so I wrote a long one instead." :-)<br><br>When it =
comes to establishing trust:<br><br>* The current SMTP model is =
O(N^2);<br><br></div></blockquote>I don't see SMTP as even a "trust" =
model since there's pretty much</div><div>nothing trustworthy in =
SMTP.</div><div><br><blockquote type=3D"cite"><div>* I posit that the =
current IP networking model is =
sub-O(N);<br><br></div></blockquote>Again, I'm not seeing IP as a trust =
model, but, YMMV.</div><div><br><blockquote type=3D"cite"><div>* PKI =
models are pretty much O(1).<br><br>Polynomial-order just doesn't scale =
well. It's mathematical fact, and<br>particularly painful when the =
independent variable is still =
increasing<br>quickly.<br><br></div></blockquote>Sure.</div><div><br><bloc=
kquote type=3D"cite"><div>Many operators seem to reject PKI as "power in =
too few hands". I'll not<br>disagree with =
that.<br><br></div></blockquote>Depends on the PKI. For example, =
the PGP/GPG Web of Trust concept</div><div>pretty much lets each =
individual build their own trust model to whatever</div><div>O(x) they =
choose where greater values of x require more effort and =
also</div><div>provide greater security/trust granularity and lower =
values of x involve</div><div>greater trust of others that you claim you =
can trust and less direct effort</div><div>on your =
part.</div><div><blockquote type=3D"cite"><div><font =
class=3D"Apple-style-span" color=3D"#000000"><br></font></div><div>Let's =
also draw upon operational lessons from a couple old-timers. =
I<br>recall using a critter known as "NNTP". And once upon a =
time, before my<br>days on the Internet, lived a funny little beast =
called "UUCP".<br><br></div></blockquote>I remember UUCP. It was =
pretty much O(n^2).</div><div><br></div><div><blockquote =
type=3D"cite"><div>We track email quality from all mailservers that hit =
us. I can whip up<br>a list of MXes/organizations that I'm willing =
to "trust" -- and let's<br>leave that term imprecisely-defined for =
now.<br><br></div></blockquote>Uh, OK. Starting to understand what =
the question might be =
aiming</div><div>towards.</div><div><br></div><div><blockquote =
type=3D"cite"><div>Here's what I propose:<br><br>Establish a "distrust =
protocol". Let path weight be "distrust". The<br>"trust =
path" is of secondary importance to "path weight", although =
not<br>completely irrelevant. SMTP endpoint not in graph? =
Fine; have some<br>default behavior.<br><br>Let _trust_ be =
semi-transitive, a la BGP -- a technology that we know,<br>understand, =
and at least sort of trust to run this crazy, giant network<br>that =
dwarfs even a 50M-user provider.<br><br>Let actual _content_ still be =
end-to-end, so that we do not simply<br>reincarnate NNTP or =
UUCP.<br><br></div></blockquote>Now I'm lost again. You've mixed =
so many different metaphors from</div><div>interdomain routing to =
distance-vector computaton to store-and-forward</div><div>that I simply =
don't understand what you are proposing or how one</div><div>could begin =
to approach implementing it or what problem you seem</div><div>to think =
it solves (although it sort of seems like you're wanting to =
attack</div><div>the trustworthiness of email to battle SPAM through =
some mechanism</div><div>that depends only on the level of trust for the =
(source, arrival path)</div><div>tuple from whence it =
came.</div><div><br></div><div>What am I =
missing?</div><div><br></div><div>Owen</div><div><br></div></body></html>=
--Apple-Mail-54-61535649--
