dcdev mailing list

ADC has made it to v0.4, it's available at http://dcplusplus.sf.net/ADC.htm
for the interested...an implementation will soon follow...

/J

Ok, protocol seems chosen, no prob...but just one question:
How hub can know what client use what protocol version? (because it seems
new client don't send any protocol version information to hub)

-----Message d'origine-----
De : dcdev-bounces@dcportal.net [mailto:dcdev-bounces@dcportal.net] De la
part de Jacek Sieka
Envoyé : samedi 17 janvier 2004 20:59
À : 'Direct Connect developers'
Objet : [dcdev] adc

ADC has made it to v0.4, it's available at http://dcplusplus.sf.net/ADC.htm
for the interested...an implementation will soon follow...

/J

The hub doesn't know and doesn't care, but the client does because all valid
adc hub addresses start with adc://
If a hub wants to support both protocols (which, at least for now, seems
doable), it'll have to do it on two different ports.

/J

-----Original Message-----
From: dcdev-bounces@dcportal.net [mailto:dcdev-bounces@dcportal.net] On Behalf Of Nouanda
Sent: Sunday, January 18, 2004 10:56 PM
To: 'Direct Connect developers'
Subject: RE: [dcdev] adc

Ok, protocol seems chosen, no prob...but just one question:
How hub can know what client use what protocol version? (because it seems
new client don't send any protocol version information to hub)

-----Message d'origine-----
De : dcdev-bounces@dcportal.net [mailto:dcdev-bounces@dcportal.net] De la
part de Jacek Sieka
Envoyé : samedi 17 janvier 2004 20:59
À : 'Direct Connect developers'
Objet : [dcdev] adc

ADC has made it to v0.4, it's available at http://dcplusplus.sf.net/ADC.htm
for the interested...an implementation will soon follow...

/J

ADC has made it to v0.4

Using an error code in ERR is a good idea however but the code you gave is rather ... illogical. They seems to be grouped by program sending them (client, hub, ...) but I think it is more logic to group them by kind of results (ok, recoveral, not recoverable, fatal) and then by program (or program and then kind). IMHO, Nick invalid cannot be in the same category as nick busy. Nick busy is recoverable but nick invalid is not recoveral, same goes for perm/temp ban (not recoverable/recoverable).
Eric

ADC has made it to v0.4

Using an error code in ERR is a good idea however but the code you gave is rather ... illogical. They seems to be grouped by program sending them (client, hub, ...) but I think it is more logic to group them by kind of results (ok, recoveral, not recoverable, fatal) and then by program (or program and then kind). IMHO, Nick invalid cannot be in the same category as nick busy. Nick busy is recoverable but nick invalid is not recoveral, same goes for perm/temp ban (not recoverable/recoverable).
Eric

eric wrote:

Using an error code in ERR is a good idea however but the code you gave is rather ... illogical. They seems to be grouped by program sending them (client, hub, ...) but I think it is more logic to group them by kind of results (ok, recoveral, not recoverable, fatal) and then by program (or program and then kind).

Good point, Eric.  I think Arne expanded error codes based on a couple pieces of feedback.  The feedback may not have been all coherent though.  I think I prefer SMTP[1] style codes over HTTP[2] style ones.  I'm not sure how well they map to error conditions in the current or next protocols, but...

From RFC0812:

1yz   Positive Preliminary reply
2yz   Positive Completion reply
3yz   Positive Intermediate reply
4yz   Transient Negative Completion reply
5yz   Permanent Negative Completion reply

It has a nice mirroring of the fourcc code in ADC... but it might not be too applicable.

- Todd

[1] = http://www.w3.org/Protocols/rfc2616/rfc2616-sec6.html#sec6.1.1
[2] = http://www.ietf.org/rfc/rfc0821.txt

Hello

Why is there no regexp search? It could use the signal RX and it could limit the search
after the other three types are complete.

/Erik

New to this list, building a client-server dc client in java.

On Sat, 17 Jan 2004 20:59:24 +0100
"Jacek Sieka" <j_s@telia.com> wrote:

ADC has made it to v0.4, it's available at http://dcplusplus.sf.net/ADC.htm
for the interested...an implementation will soon follow...

/J

A) because the vast majority of users don't have the slightest idea of what
a regular expression is
B) because it would require a 3rd party library (or very much work) to
create a BASE compilant client on the biggest target platform, i e it's not
part of the C standard library
C) because they are slower (indexed searches become tricky for instance)
D) because if there's demand for it, it's very, very easy to add to the
protocol and mandate by the hub (using sup)
E) I can go on...

/J

-----Original Message-----
From: dcdev-bounces@dcportal.net [mailto:dcdev-bounces@dcportal.net] On Behalf Of Erik Ekman
Sent: Tuesday, January 20, 2004 7:09 PM
To: Direct Connect developers
Subject: Re: [dcdev] adc

Hello

Why is there no regexp search? It could use the signal RX and it could limit the search
after the other three types are complete.

/Erik

New to this list, building a client-server dc client in java.

On Sat, 17 Jan 2004 20:59:24 +0100
"Jacek Sieka" <j_s@telia.com> wrote:

> ADC has made it to v0.4, it's available at http://dcplusplus.sf.net/ADC.htm
> for the interested...an implementation will soon follow...
> > /J
> > -- >

Yes, this probably makes more sense, although has the possible downside of
tying down to protocol level what is recoverable and what is not...unless
they're completely separated, code and severity...hm...

/J

-----Original Message-----
From: dcdev-bounces@dcportal.net [mailto:dcdev-bounces@dcportal.net] On Behalf Of eric
Sent: Monday, January 19, 2004 6:54 PM
To: Direct Connect developers
Subject: Re: [dcdev] adc
> ADC has made it to v0.4

Using an error code in ERR is a good idea however but the code you gave is rather ... illogical. They seems to be grouped by program sending them (client, hub, ...) but I think it is more logic to group them by kind of results (ok, recoveral, not recoverable, fatal) and then by program (or program and then kind). IMHO, Nick invalid cannot be in the same category as nick busy. Nick busy is recoverable but nick invalid is not recoveral, same goes for perm/temp ban (not recoverable/recoverable).
Eric

On Tuesday 20 January 2004 20:00, Jacek Sieka wrote:

A) because the vast majority of users don't have the slightest idea of what
a regular expression is

but the majority does not mean everybody. The majority of people have feet but this does not have prevented automobile creation ;-)

B) because it would require a 3rd party library (or very much work) to
create a BASE compilant client on the biggest target platform, i e it's not
part of the C standard library

I am not sure about this. When I do a "man regex", it is classified in man(3) and it is in POSIX.2. Moreover, there is no libregex anymore since ... a long time :)

C) because they are slower (indexed searches become tricky for instance)

It is not slower (see earlier mails in the mailing list for test results) and indexed searches are mainly a matter of index organization.

D) because if there's demand for it, it's very, very easy to add to the
protocol and mandate by the hub (using sup)

then why not add it immediatly if it is so easy :)

Eric

david vargas (nny) wrote:

so i recommend using a port above 1024... not like its difficult to say
which port to use, but might as well mention it at the start...

I don't think ADC should have *any* default port - ie. each hub address should be fully qualified like: adc://hubname.domain.tld:port   It should be left up to _implementations_ to pick a random port when a hub is first configured/created (and then registered to a public list - something ADC doesn't touch on yet), and to make sure that port isn't likely firewalled (like the backorifice [or other trojan] ports).  Of course, if you want to make it easy to block the new protocol, we could go back to a forced client and server listening port.

If we randomize ports, Packeteer's Packetshaper will probably keep up anyway, but port-based firewalling systems will be defeated.

- Todd

i say use a port above 1024... so on *nix machines you can run a
server, and reboot it remotely, in the event it hangs or the server
crashes or whatever..., so the app doesnt have to run as root on
startup... so you dont have any security issues... since opendchub tends to
crash at times... my roomate has been using it for some time now... so i dont
know if it crashes as much, but he has a script making sure it continues
running, and starts it up again, in the event it goes down... but theres
still the security risk, in the event someone discovers an exploit...

so i recommend using a port above 1024... not like its difficult to say
which port to use, but might as well mention it at the start...

-nny

On Sun, 18 Jan 2004, Jacek Sieka wrote:

Date: Sun, 18 Jan 2004 23:19:42 +0100
From: Jacek Sieka <j_s@telia.com>
Reply-To: Direct Connect developers <dcdev@dcportal.net>
To: 'Direct Connect developers' <dcdev@dcportal.net>
Subject: RE: [dcdev] adc

The hub doesn't know and doesn't care, but the client does because all valid
adc hub addresses start with adc://
If a hub wants to support both protocols (which, at least for now, seems
doable), it'll have to do it on two different ports.

/J

> -----Original Message-----
> From: dcdev-bounces@dcportal.net
> [mailto:dcdev-bounces@dcportal.net] On Behalf Of Nouanda
> Sent: Sunday, January 18, 2004 10:56 PM
> To: 'Direct Connect developers'
> Subject: RE: [dcdev] adc
>
> Ok, protocol seems chosen, no prob...but just one question:
> How hub can know what client use what protocol version?
> (because it seems
> new client don't send any protocol version information to hub)
>
> -----Message d'origine-----
> De : dcdev-bounces@dcportal.net
> [mailto:dcdev-bounces@dcportal.net] De la
> part de Jacek Sieka
> Envoyé : samedi 17 janvier 2004 20:59
> À : 'Direct Connect developers'
> Objet : [dcdev] adc
>
> ADC has made it to v0.4, it's available at
> http://dcplusplus.sf.net/ADC.htm
> for the interested...an implementation will soon follow...
>
> /J
>
> --
>

On Tuesday 20 January 2004 20:00, Jacek Sieka wrote:
> A) because the vast majority of users don't have the slightest idea of what
> a regular expression is

but the majority does not mean everybody. The majority of people have feet but this does not have prevented automobile creation ;-)

The majority of people do know how to drive though (in the western part of
the world where the majority has a car anyway)...and as sandos noted; all
the regex searchs you provided in your tests were archivable with substring
search as well...

> B) because it would require a 3rd party library (or very much work) to
> create a BASE compilant client on the biggest target platform, i e it's not
> part of the C standard library

I am not sure about this. When I do a "man regex", it is classified in man(3) and it is in POSIX.2. Moreover, there is no libregex anymore since ... a long time :)

Being in posix.2 means, among other things, that it's not covered by the
standard c library...it also means that it's not available on windows, and
although you might think that linux is the answer to everything, I doubt
that your client comes even close to the >1000000 downloads that dc++ had in
it's second latest version (and that being from sf only, not counting the
countless mirrors and freeware cd's its being distributed through)...hence,
the major dc platform does not support regexes without library support...

> C) because they are slower (indexed searches become tricky for instance)

It is not slower (see earlier mails in the mailing list for test results) and indexed searches are mainly a matter of index organization.

It is. Even some of your simple searches took ~0.1s, imagine what a more
complex one would do that actually uses the enhanced expressiveness of
regexes (start by introducing a few | and you'll see...), and if it takes
0.1s it means that the highes search throughput will be 10searches/s with
100% cpu, which is not very impressive, not in my eyes anyway...

> D) because if there's demand for it, it's very, very easy to add to the
> protocol and mandate by the hub (using sup)

then why not add it immediatly if it is so easy :)

Because it adds complexity to a BASE client...if anything should be added,
it's hashes...

/J

On Wednesday, January 21, 2004, 6:03:55, david vargas (nny) wrote:

so i recommend using a port above 1024... not like its difficult to say
which port to use, but might as well mention it at the start...

It's not hard to drop root privileges right after the port has been bound,
and if you're really paranoid, you could always run the server in chroot
jail.

-- 
begin  .sig
< Jernej Simoncic >< http://deepthought.ena.si/ >

There ain't no such thing as a free lunch. ("tanstaafl")
      -- Crane's Law (Friedman's Reiteration)
end

On Wednesday, January 21, 2004, 14:40:26, Todd Pederzani wrote:

If we randomize ports, Packeteer's Packetshaper will probably keep up anyway, but port-based firewalling systems will be defeated.

Add encryption (even simple XOR-based will do), and then threaten under the
DMCA anybody who attempts to detect the protocol by decrypting the stream :)

-- 
begin  .sig
< Jernej Simoncic >< http://deepthought.ena.si/ >

Smile, tomorrow will be worse.
      -- The Murphy Philosophy
end

Jacek Sieka:
You're missing the point. With this scheme, a client can create a new
command and have it sent to other clients correctly without any updates to
the hub software at all (if nmdch supported this, we wouldn't need a new
protocol at all, because creating a new search or myinfo command would have
been doable without having to update and rewrite all the hubs out
there...)...

This mean hub must trust all client's commands, and just forward to
client(s) depending to the first char?

/Fabrice

Jacek Sieka writes:
> > On Tuesday 20 January 2004 20:00, Jacek Sieka wrote:
> > > A) because the vast majority of users don't have the > > slightest idea of what
> > > a regular expression is
> > > > but the majority does not mean everybody. The majority of > > people have feet but > > this does not have prevented automobile creation ;-)
> The majority of people do know how to drive though (in the western part of
> the world where the majority has a car anyway)...and as sandos noted; all
> the regex searchs you provided in your tests were archivable with substring
> search as well...

I use regexes very frequently to filter search results, and I do that
because I can achieve things that I cannot achieve with substring
searches. I think it would be great to have regex searching in the
client, because then fewer relevant search results would be dropped
because of UDP packets being discarded by my modem when my bandwidth
is breached.

I don't understand why it matters whether the majority of users will
be able to use regexes or not. Since regexes allow a set of achievable
search criteria that is a strict superset of that which substring
searches allows for, without sacrificing almost any speed (see below),
it is, quite simply, very, very good.

> > > > > B) because it would require a 3rd party library (or very > > much work) to
> > > create a BASE compilant client on the biggest target > > platform, i e it's not
> > > part of the C standard library
> > > > I am not sure about this. When I do a "man regex", it is > > classified in man(3) > > and it is in POSIX.2. Moreover, there is no libregex anymore > > since ... a long > > time :)
> Being in posix.2 means, among other things, that it's not covered by the
> standard c library...it also means that it's not available on windows, and
> although you might think that linux is the answer to everything, I doubt
> that your client comes even close to the >1000000 downloads that dc++ had in
> it's second latest version (and that being from sf only, not counting the
> countless mirrors and freeware cd's its being distributed through)...hence,
> the major dc platform does not support regexes without library support...

As someone mentioned earlier on this list, regexes _are_ available for
Windows from http://gnuwin32.sf.net/. I don't use Windows, so I can't
give any specifics, but I guess that it's a library that can be
directly included in the source code for a program, just like, for
example, bzip2 has been included in DC++.

> > > C) because they are slower (indexed searches become tricky > > for instance)
> > > > It is not slower (see earlier mails in the mailing list for > > test results) and > > indexed searches are mainly a matter of index organization.
> It is. Even some of your simple searches took ~0.1s, imagine what a more
> complex one would do that actually uses the enhanced expressiveness of
> regexes (start by introducing a few | and you'll see...), and if it takes
> 0.1s it means that the highes search throughput will be 10searches/s with
> 100% cpu, which is not very impressive, not in my eyes anyway...

First of all, that was 0.01 seconds, and it was also on a file list
that was around 150000 lines, which is _far_ more than the avarage
user that you seem so fond of.

As for more complex regexes, I egrepped through 400000 lines of the
Linux networking code, and even using backrefs, without a doubt the
most CPU-intensive part of regexes, I simply couldn't manage to push
it beyond 0.25 seconds, and that was on very many lines. It is also
very important to note that nothing prevents a client implementation
from dropping a search once it has reached a certain time threshold
of, for example, 0.05 seconds, which prevents people from submitting
complex expressions just for the DoS fun of it. Since regex substring
searches are as fast (or almost as fast) as ordinary substring
searches, normal users, who don't use regexes, won't even be impaired
by such behavior.

> > > > > D) because if there's demand for it, it's very, very easy > > to add to the
> > > protocol and mandate by the hub (using sup)
> > > > then why not add it immediatly if it is so easy :)
> Because it adds complexity to a BASE client...if anything should be added,
> it's hashes...

Considering how regexes are available as a seperate library and all, I
don't see how using regexec() instead of strstr() makes it so much
more complex. In that case, I'd say that eg. filelist compression adds
much more complexity, wouldn't you agree? It is nonetheless very
useful, just like regex searches are.

Also, may I ask why you want such an over-simplified base
implementation?

Fredrik Tolf

Nouanda writes:
> Jacek Sieka:
> You're missing the point. With this scheme, a client can create a new
> command and have it sent to other clients correctly without any updates to
> the hub software at all (if nmdch supported this, we wouldn't need a new
> protocol at all, because creating a new search or myinfo command would have
> been doable without having to update and rewrite all the hubs out
> there...)...
> > This mean hub must trust all client's commands, and just forward to
> client(s) depending to the first char?

Indeed; I was thinking the same. That could easily drain a hub's
bandwidth. Since it's rather clearly defined anyway which commands
will ever need a similar "upgrade", I'd say that it's better in that
case to make those commands generic enough to be upgraded easily.

Fredrik

At 03:17 AM 1/22/2004 +0100, you wrote:

Indeed; I was thinking the same. That could easily drain a hub's
bandwidth. Since it's rather clearly defined anyway which commands
will ever need a similar "upgrade", I'd say that it's better in that
case to make those commands generic enough to be upgraded easily.

The hub need not trust the commands, for it's not hurt by them no matter how malicious the intent. It should merely relay them to clients, the responsibility of which to protect themselves becomes ever clearer under this proposal.

Regarding bandwidth, a hub should indeed prevent a user from consuming too much of its upload bandwidth, but it should do this by treating B commands equally. If a client wishes to waste its prescribed allotment on BGBG garbage commands of which the hub has no knowledge, it should be free to do so; this simply means it should not then be able to send searches and chat messages.

-cologic

At 11:09 PM 1/21/2004 +0100, you wrote:

Add encryption (even simple XOR-based will do), and then threaten under the
DMCA anybody who attempts to detect the protocol by decrypting the stream :)

While cute, relying on the effectiveness of this system strikes me as foolish. There's plenty of real encryption available; use it.

-cologic

The majority of people do know how to drive though (in the western part of
the world where the majority has a car anyway)...and as sandos noted; all
the regex searchs you provided in your tests were archivable with substring
search as well...

it was just to be able to compare speed between substring search and regex.

Being in posix.2 means, among other things, that it's not covered by the
standard c library...it also means that it's not available on windows, and
although you might think that linux is the answer to everything, I doubt
that your client comes even close to the >1000000 downloads that dc++ had
in it's second latest version (and that being from sf only, not counting
the countless mirrors and freeware cd's its being distributed
through)...hence, the major dc platform does not support regexes without
library support...

IMHO, it is a bad explanation. The only reason your client is downloaded so many time is probably because it is better than the standard nmdc client and because both are available on windoz. It has nothing to do with the capabilities of the system. If we should have waited for a good network protocol from windoz, we still would run netbeui, not TCP/IP. If a feature must be added, a possible missing function is a bad reason, just add it.

It is. Even some of your simple searches took ~0.1s, imagine what a more
complex one would do that actually uses the enhanced expressiveness of
regexes (start by introducing a few | and you'll see...), and if it takes
0.1s it means that the highes search throughput will be 10searches/s with
100% cpu, which is not very impressive, not in my eyes anyway...

but not everyone share as many files as the test share file. Moreover, currently, the problem is not the CPU speed, it is the bandwidth (especially upstream). If performing 40 searches per second use all your upload bandwidth then I think we will just have something like ed2k (good to find something, awful to obtain it).

Eric

On Wednesday 21 January 2004 23:14, Nouanda wrote:

Jacek Sieka:
You're missing the point. With this scheme, a client can create a new
command and have it sent to other clients correctly without any updates to
the hub software at all (if nmdch supported this, we wouldn't need a new
protocol at all, because creating a new search or myinfo command would have
been doable without having to update and rewrite all the hubs out
there...)...

This mean hub must trust all client's commands, and just forward to
client(s) depending to the first char?

I have not seen this while reading but you are right. This is great, it will be the first protocol to have a built-in DoS feature. DoS is good for you :)

Eric
Note: well, in fact, it is the 2nd, the first is DC protocol :)

On Thursday 22 January 2004 00:20, Fredrik Tolf wrote:

Jernej Simon?i? writes:
 > On Wednesday, January 21, 2004, 6:03:55, david vargas (nny) wrote:
 > > so i recommend using a port above 1024... not like its difficult to
 > > say which port to use, but might as well mention it at the start...
 >
 > It's not hard to drop root privileges right after the port has been
 > bound, and if you're really paranoid, you could always run the server in
 > chroot jail.

Yeah, but it might be nice for a user to be able to start it without
requiring the binary to be suid...

I agree, there should be no default port. Default ports exist for daemon running under inetd, not stand-alone daemon. We should not even suggest a default port.

Eric

I use regexes very frequently to filter search results, and I do that
because I can achieve things that I cannot achieve with substring
searches. I think it would be great to have regex searching in the
client, because then fewer relevant search results would be dropped
because of UDP packets being discarded by my modem when my bandwidth
is breached.

I don't understand why it matters whether the majority of users will
be able to use regexes or not. Since regexes allow a set of achievable
search criteria that is a strict superset of that which substring
searches allows for, without sacrificing almost any speed (see below),
it is, quite simply, very, very good.

I agree. That's clearly what defines a power user. Not everyone has the same usage, why do you want to limit the "power" given to users ?

As someone mentioned earlier on this list, regexes _are_ available for
Windows from http://gnuwin32.sf.net/. I don't use Windows, so I can't
give any specifics, but I guess that it's a library that can be
directly included in the source code for a program, just like, for
example, bzip2 has been included in DC++.

that's a very good reason (and the regex processor should probably be a single file with a ridiculously small size).

Considering how regexes are available as a seperate library and all, I
don't see how using regexec() instead of strstr() makes it so much
more complex. In that case, I'd say that eg. filelist compression adds
much more complexity, wouldn't you agree? It is nonetheless very
useful, just like regex searches are.

Moreover, it won't be strstr because windoz loo^H^H^Husers won't understand why if they search for "toto", they don't receive files like "Toto", "tOto" or any other possible case sensitive changes.

Eric

Indeed; I was thinking the same. That could easily drain a hub's
bandwidth. Since it's rather clearly defined anyway which commands
will ever need a similar "upgrade", I'd say that it's better in that
case to make those commands generic enough to be upgraded easily.

I have a better choice. Let's define only one command (*) having various parameters (in random order) and let the hub randomly chooses the action to do with this command. It is the perfect protocol: no out of order problem, low bandwidth usage for both hub and client, and finally, random results (like any P2P protocol)... oh, I have forgotten how it will be easy to program because due to the fact everything is random, you can program the code you want :)

Eric

On Thursday 22 January 2004 06:15, blackclaw@parsoma.net wrote:

At 11:09 PM 1/21/2004 +0100, you wrote:
>Add encryption (even simple XOR-based will do), and then threaten under
> the DMCA anybody who attempts to detect the protocol by decrypting the
> stream :)

While cute, relying on the effectiveness of this system strikes me as
foolish. There's plenty of real encryption available; use it.

and with standard library,even on windoz.

Eric

At 01:01 AM 1/22/2004 +0100, you wrote:

I don't understand why it matters whether the majority of users will
be able to use regexes or not. Since regexes allow a set of achievable
search criteria that is a strict superset of that which substring
searches allows for, without sacrificing almost any speed (see below),
it is, quite simply, very, very good.

Whilst regexes are strictly more powerful than the multiple substring searches DC++ uses, unless one has a & operator (rare) or Perl5's positive lookahead, one cannot implement them without an increase in length proportional to the permutations of the terms in the query:

Multiple substring: a b c d

Extended POSIX-style: a.*b.*c.*d | a.*b.*d.*c | a.*c.*b.*d | a.*c.*d.*b | a.*d.*b.*c | a.*d.*c.*b | b.*a.*c.*d | b.*a.*d.*c | b.*c.*a.*d | b.*c.*d.*a | b.*d.*a.*c | b.*d.*c.*a | c.*a.*b.*d | c.*a.*d.*b | c.*b.*a.*d | c.*b.*d.*a | c.*d.*a.*b | c.*d.*b.*a | d.*a.*b.*c | d.*a.*c.*b | d.*b.*a.*c | d.*b.*c.*a | d.*c.*a.*b | d.*c.*b.*a

Perl5-compatible regex: (?=a)(?=b)(?=c)(?=d)

All of the above are untested.

As for more complex regexes, I egrepped through 400000 lines of the
Linux networking code, and even using backrefs, without a doubt the
most CPU-intensive part of regexes, I simply couldn't manage to push
it beyond 0.25 seconds, and that was on very many lines. It is also
very important to note that nothing prevents a client implementation
from dropping a search once it has reached a certain time threshold
of, for example, 0.05 seconds, which prevents people from submitting
complex expressions just for the DoS fun of it.

Such protection would be necessary, as http://www.cs.rice.edu/~scrosby/hash/slides/USENIX-RegexpWIP.2.ppt shows that even removing backrefs entirely doesn't immunize a RE engine from attack. 400,000 lines requiring 0.25 seconds would suggest that, for example, 100,000 lines requires 0.0625 seconds, which allows only 16 searches per second before one reaches 100% CPU usage. Even your example of 0.05 seconds allows only 20/second. I don't want a DC client I run monopolizing near that much CPU time.

Another factor you haven't mentioned is your CPU: what is it?

Since regex substring
searches are as fast (or almost as fast) as ordinary substring
searches, normal users, who don't use regexes, won't even be impaired
by such behavior.

As I demonstrated above, not without special support from the RE engine; that 24-way or'd expression is going to be noticeably slower than the semantically equivalent multiple substring search. The Perl5 method should be similar in speed, but requires an NFA RE implementation exhibiting unbounded-time behaviour and thus potentially vulnerable to the attacks described above.

Finally, using regular expressions inhibits one from applying many potential search optimizations, such as Bloom filters (used in Gnutella as the QRP, or Query Routing Protocol) and suffix array-assisted searches. A histogram of the speed results of the latter is at http://opennavel.dnsalias.org/~fusbar/cologic/bmratio2.png ; the y axis represents how many searches (out of approximately 20,000 total) were faster or slower under that scheme than DC++'s default search by the (inverse of natural log of) the x-axis value.

-cologic

Such protection would be necessary, as
http://www.cs.rice.edu/~scrosby/hash/slides/USENIX-RegexpWIP.2.ppt shows
that even removing backrefs entirely doesn't immunize a RE engine from
attack. 400,000 lines requiring 0.25 seconds would suggest that, for
example, 100,000 lines requires 0.0625 seconds, which allows only 16
searches per second before one reaches 100% CPU usage. Even your example of
0.05 seconds allows only 20/second. I don't want a DC client I run
monopolizing near that much CPU time.

Another factor you haven't mentioned is your CPU: what is it?

a simple blacklist on users sending queries taking too much time is enough, no ?

As I demonstrated above, not without special support from the RE engine;
that 24-way or'd expression is going to be noticeably slower than the
semantically equivalent multiple substring search. The Perl5 method should
be similar in speed, but requires an NFA RE implementation exhibiting
unbounded-time behaviour and thus potentially vulnerable to the attacks
described above.

There is a little flaw in your demonstration. You have assumed when a client searches for "a b c d", this means "a" & "b" & "c" & "d" but it is wrong. Speaking about probability, a.*b.*c.*d is probably what the user wants the most. For example, if a user searches for an album, he won't spend time to write the album title in the reverse order. That's why most of the time, "a b c d" means "a.*b.*c.*d" (when it is not exactly "a b c d"). Any user having enough experience in any search engine (even google) knows he should not use some simple words like "a", "the", "is" and to search for "heaven is a place on earth", he will search "heaven place earth" (and it is even shorter to write :) ).

Finally, using regular expressions inhibits one from applying many
potential search optimizations, such as Bloom filters (used in Gnutella as
the QRP, or Query Routing Protocol) and suffix array-assisted searches. A
histogram of the speed results of the latter is at
http://opennavel.dnsalias.org/~fusbar/cologic/bmratio2.png ; the y axis
represents how many searches (out of approximately 20,000 total) were
faster or slower under that scheme than DC++'s default search by the
(inverse of natural log of) the x-axis value.

optimizing something is good but optimizing something which is limited is IMHO just a waste of time. Moreover, finding something is good, being able to send it to the client requesting it in a reasonable period of time is better. Not everybody has access to a 100Mb connection, most of the users have ADSL or cable connections and if they take 5-10 minutes to send/receive their reply, I think they won't use this P2P network.

Eric

As I demonstrated above, not without special support from the RE engine;
that 24-way or'd expression is going to be noticeably slower than the
semantically equivalent multiple substring search. The Perl5 method should
be similar in speed, but requires an NFA RE implementation exhibiting
unbounded-time behaviour and thus potentially vulnerable to the attacks
described above.

There is a little flaw in your demonstration. You have assumed when a client searches for "a b c d", this means "a" & "b" & "c" & "d" but it is wrong. Speaking about probability, a.*b.*c.*d is probably what the user wants the most. For example, if a user searches for an album, he won't spend time to write the album title in the reverse order. That's why most of the time, "a b c d" means "a.*b.*c.*d" (when it is not exactly "a b c d"). Any user having enough experience in any search engine (even google) knows he should not use some simple words like "a", "the", "is" and to search for "heaven is a place on earth", he will search "heaven place earth" (and it is even shorter to write :) ).

Moreover, both substring and regex searches can be supported. Why arguing? It's not a question wether to use regex or substring, but if to support regex at all.
Like I said in my early mail, simply add a / (0x2F) on both sides of the regex. Reason? It's a magic char used in filesystems. UNIX uses it, windows supports it. So you can't use in a filename pattern. And if you do, the client simply escapes it before sending. And if you want to search for directories, tell it by using filetype/category.

Regex is good for advanced searches; substring is enough for the basic user. Both can be supported. Support it! :p

And for resource limitations (resources = bandwidth,cpu,memory.. whatever), the client would simply refuse to perform the search if it gets too heavy (decided on factors that the client are to decide, not part of the actual protocol). And I belive that everyone agrees that a client refusing to perform the search due to resource limits is a fully acceptable reason.

/Carl-Adam

You didnt understood what he said, did you. He never said that XOR encryption will be used, just that something that simple is enought for a trivial encryption.
_READ_ what has been written :P

blackclaw@parsoma.net wrote:

At 11:09 PM 1/21/2004 +0100, you wrote:

Add encryption (even simple XOR-based will do), and then threaten under the
DMCA anybody who attempts to detect the protocol by decrypting the stream :)

While cute, relying on the effectiveness of this system strikes me as foolish. There's plenty of real encryption available; use it.

-cologic

On Thursday, January 22, 2004, 8:13:20, Carl-Adam Brengesjö wrote:

You didnt understood what he said, did you. He never said that XOR encryption will be used, just that something that simple is enought for a trivial encryption.

Actually, I was joking, but anyway, if you put an encryption (any
encryption, even if it's ROT-13), you have the right (under the DMCA) to sue
anybody who tries to work around your encryption, for whatever reason (there
are numerous similarly stupid examples in the real world).

-- 
begin  .sig
< Jernej Simoncic >< http://deepthought.ena.si/ >

A good place to start from is where you are.
      -- Wolf's Law of Planning
end

At 08:13 AM 1/22/2004 +0100, you wrote:

You didnt understood what he said, did you. He never said that XOR encryption will be used, just that something that simple is enought for a trivial encryption.
_READ_ what has been written :P

Well, sure; I recall no statements assertive enough to claim that something "will be used", with the possible exception of arnetheduck's messagres regarding ADC.

As a response the claim that "something that simple is enough for trivial encryption", my original response holds.

-cologic

And for resource limitations (resources = bandwidth,cpu,memory.. whatever), the client would simply refuse to perform the search if it gets too heavy (decided on factors that the client are to decide, not part of the actual protocol). And I belive that everyone agrees that a client refusing to perform the search due to resource limits is a fully acceptable reason.

This is something we want to avoid I believe...if the system as a whole
starts skipping too many searches, users will learn that they get different
results if they search more times, and that's bad...it's more or less like
the old multitasking systems that gave priority to processes where keyboard
input was being done to improve their responsiveness...it worked until the
users found out that their calculations went faster if they kept pressing a
button while doing it...

/J

> This mean hub must trust all client's commands, and just forward to
> client(s) depending to the first char?

What's there to trust/not trust?

I have not seen this while reading but you are right. This is great, it will be the first protocol to have a built-in DoS feature. DoS is good for you :)

It doesn't take a degree in computer science to make this a configuration
option in the hub, for instance "allow these commands"...
Besides, flooding with known commands seems more efficient since they have
resource-taking side effects while an unknown one will simply be discarded
by all clients...

/J

I agree, there should be no default port. Default ports exist for daemon running under inetd, not stand-alone daemon. We should not even suggest a default port.

Did anyone suggest it?

/J

Jernej Simon?i? writes:
> On Wednesday, January 21, 2004, 6:03:55, david vargas (nny) wrote:
> > > so i recommend using a port above 1024... not like its difficult to say
> > which port to use, but might as well mention it at the start...
> > It's not hard to drop root privileges right after the port has been bound,
> and if you're really paranoid, you could always run the server in chroot
> jail.

Yeah, but it might be nice for a user to be able to start it without
requiring the binary to be suid...

Fredrik

eric wrote:

and with standard library,even on windoz.

Does Linus 2.6 have standard libraries?

- Todd

eric wrote:

There is a little flaw in your demonstration. You have assumed when a client searches for "a b c d", this means "a" & "b" & "c" & "d" but it is wrong.  

Matching all of the substrings is the way Jon Hess coded the original client, how can that somehow be an incorrect assumption?

Speaking about probability, a.*b.*c.*d is probably what the user wants the most. For example, if a user searches for an album, he won't spend time to write the album title in the reverse order. That's why most of the time, "a b  

What's wrong with supporting out of order matching of search strings?  Some users do use it - I'm one.

optimizing something is good but optimizing something which is limited is IMHO just a waste of time.

Using Gnutella's QRP model will limit the number of users that a hub has to broadcast to.  Hub bandwidth, not CPU power, is the limiting factor, so I don't think that you should have dismissed cologic's suggested optimizations that easily.

- Todd

Fredrik Tolf wrote:

Nah, I'm not sure about that. What if the user accidently presses
enter like 10 times (has happened to me from time to time when I'm so
tired that I think I let the button up completely, but in fact, it's
still down and autotyping)? Then all of a sudden the user must wait
for like 2 minutes two search again.

Even better: 10 duplicate searches?  Send only one.

I think that it's better to make the hub warn, and then if the user
wants delayed searches, that can be implemented in the client instead.

Or... it could be implemented in both places.

- Todd

At 06:40 PM 1/22/2004 +0100, you wrote:

I agree. That's clearly what defines a power user. Not everyone has the same
usage, why do you want to limit the "power" given to users ?

Because it increases the potential to DoS clients.

Moreover, it won't be strstr because windoz loo^H^H^Husers won't understand
why if they search for "toto", they don't receive files like "Toto", "tOto"
or any other possible case sensitive changes.

Wouldn't most Lindows loo^H^H^Husers encounter a similar difficulty?

-Dusitn

At 06:30 PM 1/22/2004 +0100, you wrote:

I have not seen this while reading but you are right. This is great, it will
be the first protocol to have a built-in DoS feature. DoS is good for you :)

Yes, because the hub broadcasting messages as it's been optimized for represents such an utterly catastrophic DoS channel. What, can't eunuchs clients handle a few unknown commands?

-cologic

Fredrik Tolf wrote:

I'm sorry, but I can't seem to find anything about that in either my
mailbox or in the archives (even if I search through the raw archive
mbox, I can't find anything that looks like it). Was that on this
list?

It was message ID <401093D9.8030001@verizon.net> =)

In case you missed the 'windoz' references:

~/Maildir/.Lists.DCDev$ mboxgrep -i windoz -m maildir . | grep "From:"
From: eric <eric@ac2i.tzo.com>
From: Fredrik Tolf <fredrik@dolda2000.com>
From: eric <eric@ac2i.tzo.com>
From: eric <eric@ac2i.tzo.com>
From: eric <eric@a2ml.ath.cx>
From: eric <eric@a2ml.ath.cx>
From: Fredrik Tolf <fredrik@dolda2000.com>
From: Jan Vidar Krey <janvidar@extatic.org>
From: eric <eric@a2ml.ath.cx>
From: Todd Pederzani <todd.pederzani@verizon.net>

DJ_Offset: it isn't bashing.  I attempted to echo Eric's comments right back at him.  Cologic did similarly a short while later.

It's practically inspired as many mails as encoding schemes, so it's gone way too far. =)

- Todd

(There's no way this can be considered on topic.)

On Thursday 22 January 2004 21:27, Jacek Sieka wrote:

> And for resource limitations (resources = bandwidth,cpu,memory..
> whatever), the client would simply refuse to perform the search if it
> gets too heavy (decided on factors that the client are to decide, not
> part of the actual protocol). And I belive that everyone
> agrees that a
> client refusing to perform the search due to resource limits
> is a fully
> acceptable reason.

This is something we want to avoid I believe...if the system as a whole
starts skipping too many searches, users will learn that they get different
results if they search more times, and that's bad...it's more or less like
the old multitasking systems that gave priority to processes where keyboard
input was being done to improve their responsiveness...it worked until the
users found out that their calculations went faster if they kept pressing a
button while doing it...

but it is inevitable because you have to deal with too many parameters:
1) the size of share in number of files
2) the CPU power (I think some users still use a good old pentium 200 (or less)).
3) the system load (which is more or less directly linked to the CPU power and (real) ram size)).

Eric

Todd Pederzani writes:
> Fredrik Tolf wrote:
> > >Nah, I'm not sure about that. What if the user accidently presses
> >enter like 10 times (has happened to me from time to time when I'm so
> >tired that I think I let the button up completely, but in fact, it's
> >still down and autotyping)? Then all of a sudden the user must wait
> >for like 2 minutes two search again.
>
> Even better: 10 duplicate searches?  Send only one.

Well, like I said, it was accidental. It can also happen for other
reasons. Say that a hub connection is really laggy, so the user
presses the search button, but nothing happens, so he/she thinks that
it was registered for any reason, so the user presses again, and
again. By the time the hub has relayed the first search, there are 1
or 2 others in transit, that will remain queued, taking up unnecessary
time.

> >I think that it's better to make the hub warn, and then if the user
> >wants delayed searches, that can be implemented in the client instead.
> Or... it could be implemented in both places.

Why? The thing is that if you implement it in the hub, the user
_cannot_ cancel delayed searches, unless you add yet another command
precisely for cancelling delayed searches. If it is only implemented
in the client, it gives the user greater control. It's not like it
gives any advantages to have the hub queue delayed searches if the
client can do it instead.

Fredrik Tolf

That was what I was referring to. And I don't think anyone said that
the current protocol was perfect.

That's even why it is called a draft :)

In any case, I don't really know why I even followed up on the DoS
matter. The thing that I really don't agree with about ADC is the fact
that such a command division isn't actually necessary. I believe that
all commands should be clearly defined, and those that are broadcasted
should be specified in such a way that allows for easy future
extension of those commands.

And even to ease hub/client developper work. If you should read more than 2 times a protocol specification to hope you have understand well it (not in detail but the concept), it is bad, especially if something looks badly definite, it is the best way to have client/hub incompatibility.

Eric

Todd Pederzani writes:
> Fredrik Tolf wrote:
> > >In any case, I don't really know why I even followed up on the DoS
> >matter. The thing that I really don't agree with about ADC is the fact
> >that such a command division isn't actually necessary. I believe that
> >all commands should be clearly defined, and those that are broadcasted
> >should be specified in such a way that allows for easy future
> >extension of those commands.
> > True, this is a better argument than a half-hearted > DC-client-as-ddos-tool argument (but that should be a topic of > discussion at some point - how to handle "evilness" in the network).

Yeah, I think that should be the subject of a later
discussion. Possibly not at all on this list, since it's probably not
a protocol matter.

> For me, ADC makes sense: The simplicity of, more or less, being
> able to write a hub that consists of a switch statement is
> appealing.  So is the ability add arbitrary broadcast and directed
> commands.  Users want a lot of things, and all of them won't be
> covered by any single protocol we accept.  If a new directed
> command is needed (say, for client to client cctp), making its
> function dependent upon what (adc or dolda-connect compliant)
> hubsoft the clients are attached to is just plain unacceptable -
> it's the same situation we have now.

I do agree with you in a way, in that it does seem appealing in terms
of simplicity. However, I don't think that kind of simplicity is going
to hold, since the broadcast commands still often require some
individual intelligent processing by the hub. For example, the only
two commands in ADC that truly benefit from broadcasting are, as far
as I can see, the SCH and INF commands. These already differ in my
mind, in that if the hub receives to SCH commands too close in time to
each other, it should reject the second one with an error. However, if
it requires two INF commands within one "allowed broadcast period", if
you see what I mean, it shouldn't deny the second one. It should wait
until the broadcast timer expires, and accumulate all succeeding INF
commands and then re-broadcast the final data once the client is
allowed the broadcast bandwidth again, right?

Do you see what I mean, or were I too unclear?

Fredrik Tolf

>  > For me, ADC makes sense: The simplicity of, more or less, being
>  > able to write a hub that consists of a switch statement is
>  > appealing.  So is the ability add arbitrary broadcast and directed
>  > commands.  Users want a lot of things, and all of them won't be
>  > covered by any single protocol we accept.  If a new directed
>  > command is needed (say, for client to client cctp), making its
>  > function dependent upon what (adc or dolda-connect compliant)
>  > hubsoft the clients are attached to is just plain unacceptable -
>  > it's the same situation we have now.
> > I do agree with you in a way, in that it does seem appealing in terms
> of simplicity. However, I don't think that kind of simplicity is going
> to hold, since the broadcast commands still often require some
> [...]

I forgot to mention, that given the very narrow namespace in ADC -
three characters per command, you're pretty much doomed to have
namespace clashes when people start extending it too much. And then,
broadcasting commands that have different meanings for different
clients isn't really a good thing, IMHO.

Fredrik Tolf

Todd Pederzani writes:
> eric wrote:
> > >and with standard library,even on windoz.
> >  > >
> Does Linus 2.6 have standard libraries?

Hmmm... Have you understood how Linux works? Remember, Linux is just
the kernel, only the kernel. Why the whole system has come to be
called Linux is, to this very day, a mystery. As Richard Stallman has
correctly noted, it should be called GNU/Linux.

Thus, running the 2.4 or 2.6 kernel isn't even related to the
libraries. Upgrading to the 2.6 kernel doesn't change your libraries,
which will remain as standard as they have always been.

Fredrik Tolf

I forgot to mention, that given the very narrow namespace in ADC -
three characters per command, you're pretty much doomed to have
namespace clashes when people start extending it too much. And then,
broadcasting commands that have different meanings for different
clients isn't really a good thing, IMHO.

And we will see the current mess where we should test the client "type" to understand what its command meant.

Eric

I do agree with you in a way, in that it does seem appealing in terms
of simplicity. However, I don't think that kind of simplicity is going
to hold, since the broadcast commands still often require some
individual intelligent processing by the hub. For example, the only
two commands in ADC that truly benefit from broadcasting are, as far
as I can see, the SCH and INF commands. These already differ in my
mind, in that if the hub receives to SCH commands too close in time to
each other, it should reject the second one with an error. However, if
it requires two INF commands within one "allowed broadcast period", if
you see what I mean, it shouldn't deny the second one. It should wait
until the broadcast timer expires, and accumulate all succeeding INF
commands and then re-broadcast the final data once the client is
allowed the broadcast bandwidth again, right?

As a bit of background, the idea comes originally from irc client-to-client
copy, and it's been used there with success afaik...on flooding, again irc
has a good model with their sliding timer - in fact, that's what dch++ uses
for the moment as flood protection, and it seems to be working ok...(if(now

flood_timer) flood_timer = now; now += 2; if(flood_timer - now > limit)

kick();) that is...which works regardless of command, and allows for a
number of commands coming one directly after the other...

Further, hub processing on commands needs to be done mainly for limiting
purposes - shares, slots, etc. Clients should do their own sanity checking
on messages that arrive, and should never trust what they get from the hub
anyway, so -specially for new commands- it is mainly up to the client to
decide whether to trust a command or not...
Besides, a simple allow list in the hub config brings us back where no
bandwidth is lost on funny commands...but the hub owner can easily allow a
new one should one emerge...and it's not like the commands themselves are
unspecified...

/J

In a filesharing client? None of Gnutella, Kazaa, Napster, nor the current
DC have trained them to expect such case-sensitivity, nor do the top few
web search engines implement it.

but maybe we should be able to tell on-the-fly if the query is case-sensitive or not (a good example of why: you probably know a movie named xXx :) ).

Eric

blackclaw@parsoma.net writes:
> At 06:40 PM 1/22/2004 +0100, you wrote:
> >I agree. That's clearly what defines a power user. Not everyone
> >has the same usage, why do you want to limit the "power" given to
> >users ?
> > Because it increases the potential to DoS clients.

In just what way would that be? If you are referring to the fact that
a specially crafted regex can take time to execute, then that issue
has already been covered in previous mails.

> >Moreover, it won't be strstr because windoz loo^H^H^Husers won't
> >understand why if they search for "toto", they don't receive files
> >like "Toto", "tOto" or any other possible case sensitive changes.
> > Wouldn't most Lindows loo^H^H^Husers encounter a similar difficulty?

I think not, since Lindows, and other GNU/Linux distributions, are
case-sensitive, and thus their users will already often be accustomed
to such behavior.

In any case, though, that was a bad example to begin with, since noone
wants DC searches to be case-sensitive, whatever O/S they come from.

Fredrik Tolf

blackclaw@parsoma.net writes:
> At 06:30 PM 1/22/2004 +0100, you wrote:
> >I have not seen this while reading but you are right. This is
> >great, it will be the first protocol to have a built-in DoS
> >feature. DoS is good for you :)
> > Yes, because the hub broadcasting messages as it's been optimized
> for represents such an utterly catastrophic DoS channel. What,
> can't eunuchs clients handle a few unknown commands?

I really don't think that was the heart of the matter. The thing was
that with unknown broadcasted commands, you could potentially give a
command that would force compliant clients to send lots of data to an
unrelated IP address, thereby making DDoS attacks easy.

Oh, by the way, great pun there with "eunuchs". I almost smiled.

Fredrik Tolf

The hub's problem is bandwidth. The client's problem is CPU time. Those "40
searches per second" are client CPU problems with regexes, not bandwidth
problems that would affect one's ability to share files (rendering your odd
ed2k comment utterly irrelevant).

I don't 100% agree. The problem of clients are both CPU time and bandwidth and probably more bandwidth than CPU, I explain. From the point of view of a single user, I agree with you but from the point of view of the network, it is better to have a client dropping some queries than having a client having a share speed (upstream) very low. In any case, if the network connection of a user "stalls", your queries/replies will be silently dropped thanks to UDP.

Eric

At 04:04 AM 1/23/2004 +0100, you wrote:

In just what way would that be? If you are referring to the fact that
a specially crafted regex can take time to execute, then that issue
has already been covered in previous mails.

Inadequately; nondeterministic search behaviour is ultimately counterproductive.

I think not, since Lindows, and other GNU/Linux distributions, are
case-sensitive, and thus their users will already often be accustomed
to such behavior.

In a filesharing client? None of Gnutella, Kazaa, Napster, nor the current DC have trained them to expect such case-sensitivity, nor do the top few web search engines implement it.

-cologic

At 06:26 PM 1/22/2004 +0100, you wrote:

If we should have waited for a good network protocol from windoz, we still would run netbeui, not TCP/IP. If a feature must be added, a possible missing function is a bad reason, just add it.

I know, Finux has only superior protocols such as NFS, and invented TCP/IP.

Moreover, currently, the problem is not the CPU speed, it is the bandwidth (especially upstream). If performing 40 searches per second use all your upload bandwidth then I think we will just have something like ed2k (good to find something, awful to obtain it).

Did Slashdot's Lunix groupthink remove your ability to compose a coherent, rational thought?

The hub's problem is bandwidth. The client's problem is CPU time. Those "40 searches per second" are client CPU problems with regexes, not bandwidth problems that would affect one's ability to share files (rendering your odd ed2k comment utterly irrelevant).

-cologic

blackclaw@parsoma.net writes:
> At 04:04 AM 1/23/2004 +0100, you wrote:
> >In just what way would that be? If you are referring to the fact that
> >a specially crafted regex can take time to execute, then that issue
> >has already been covered in previous mails.
> > Inadequately; nondeterministic search behaviour is ultimately > counterproductive.

What exactly do you think the flaw is?

> >I think not, since Lindows, and other GNU/Linux distributions, are
> >case-sensitive, and thus their users will already often be accustomed
> >to such behavior.
> > In a filesharing client? None of Gnutella, Kazaa, Napster, nor the current > DC have trained them to expect such case-sensitivity, nor do the top few > web search engines implement it.

Quote myself in that very same reply:

In any case, though, that was a bad example to begin with, since
noone wants DC searches to be case-sensitive, whatever O/S they come
from.

Fredrik Tolf

blackclaw@parsoma.net writes:
> At 06:26 PM 1/22/2004 +0100, you wrote:
> >If we should have waited for a good network protocol from windoz, we still > >would run netbeui, not TCP/IP. If a feature must be added, a possible > >missing function is a bad reason, just add it.
> > I know, Finux has only superior protocols such as NFS, and invented TCP/IP.

If you would care to excuse me, gentlemen, I think it would be
constructive for the relevant correspondence to stop bashing at each
others operating systems, and instead focus on the task at hand...

> >Moreover, currently, the problem is not the CPU speed, it is the bandwidth > >(especially upstream). If performing 40 searches per second use all your > >upload bandwidth then I think we will just have something like ed2k (good > >to find something, awful to obtain it).
> > Did Slashdot's Lunix groupthink remove your ability to compose a coherent, > rational thought?
> > The hub's problem is bandwidth. The client's problem is CPU time. Those "40 > searches per second" are client CPU problems with regexes, not bandwidth > problems that would affect one's ability to share files (rendering your odd > ed2k comment utterly irrelevant).

Now for the fourth time, "those 40 searches per second" scenario will
never happen, for previously given reasons.

Btw., you seem to be inventing different name puns on Linux in every
mail that you write. While, as I stated, I think that it would be
constructive to stop bashing at each others operating systems, I can't
help being a bit curious as to what grudge it is that you hold against
an excellent operating system. Would you mind mailing me your reasons
in a private mail?

Fredrik Tolf

Fredrik Tolf wrote:

Todd Pederzani writes:
> eric wrote:
> > >and with standard library,even on windoz.
> >  > >
> Does Linus 2.6 have standard libraries?

Hmmm... Have you understood how Linux works? Remember, Linux is just
the kernel, only the kernel. Why the whole system has come to be
called Linux is, to this very day, a mystery. As Richard Stallman has
correctly noted, it should be called GNU/Linux.

Thus, running the 2.4 or 2.6 kernel isn't even related to the
libraries. Upgrading to the 2.6 kernel doesn't change your libraries,
which will remain as standard as they have always been.

Fredrik Tolf

Please do not respond to trolls that aren't targeting you. =)

'windoz' - a name-calling of Windows
'linus' - an ignorant name for the linux kernel (which ignores the gnu portion/contribution to linux kernel based distributions)

Thanks for trying to be helpful, but you entirely missed the point.

- Todd

Todd Pederzani writes:
> Please do not respond to trolls that aren't targeting you. =)
> > 'windoz' - a name-calling of Windows
> 'linus' - an ignorant name for the linux kernel (which ignores the gnu > portion/contribution to linux kernel based distributions)
> > Thanks for trying to be helpful, but you entirely missed the point.

Oh, I'm sorry. I just thought that you had misspelled it by
accident. I hadn't seen that name pun before.

Fredrik Tolf

At 04:17 AM 1/23/2004 +0100, you wrote:

blackclaw@parsoma.net writes:
 > Inadequately; nondeterministic search behaviour is ultimately
 > counterproductive.

What exactly do you think the flaw is?

In arne's words: "This is something we want to avoid I believe...if the system as a whole starts skipping too many searches, users will learn that they get different
results if they search more times, and that's bad..."

-cologic

>Speaking about probability, a.*b.*c.*d is probably what the user wants the
>most. For example, if a user searches for an album, he won't spend time to
>write the album title in the reverse order. That's why most of the time,
> "a b

What's wrong with supporting out of order matching of search strings?
Some users do use it - I'm one.

There is nothing wrong but you are arguing against yourself. Currently, the main reason to reject regex is because most people won't use it. What I just see is when people search for an album/a movie, most of them simply write it then why don't we just use a simple strcasecmp() because it is what the majority wants.

Using Gnutella's QRP model will limit the number of users that a hub has
to broadcast to.  Hub bandwidth, not CPU power, is the limiting factor,
so I don't think that you should have dismissed cologic's suggested
optimizations that easily.

But you should admit gnutella was not the most widely used protocol and there is perhaps a reason. If it was that good, it should be more used than others especially because it is available for now several years. What I just want to say is we should not choose something because it is easy to optimize, we should choose something for its features, optimizations will come later.

Eric

blackclaw@parsoma.net writes:
> At 04:17 AM 1/23/2004 +0100, you wrote:
> >blackclaw@parsoma.net writes:
> >  > Inadequately; nondeterministic search behaviour is ultimately
> >  > counterproductive.
> >
> >What exactly do you think the flaw is?
> > In arne's words: "This is something we want to avoid I believe...if
> the system as a whole starts skipping too many searches, users will
> learn that they get different results if they search more times,
> and that's bad..."

Well, two things:

1. Since the regex searches will take almost exactly the same time
  anyway (and therefore will be aborted at almost exactly the same
  point), the users will most likely not get different results, or at
  least not that very different results.
2. Since hubs will restrict the search frequency anyway, isn't up to
  the user if he wants to search for the same thing again the next
  time he can, instead of searching for something else?

Fredrik Tolf

Further, hub processing on commands needs to be done mainly for limiting
purposes - shares, slots, etc. Clients should do their own sanity checking
on messages that arrive, and should never trust what they get from the hub
anyway, so -specially for new commands- it is mainly up to the client to
decide whether to trust a command or not...

But speaking about hub bandwidth, hub should also be able to sanity checks on command it receives else it is the best way to waste hub bandwidth (see DC history to find cases of buggy clients sending invalid commands which where relayed by hubs because they were unable to verify the commands).

Eric

At 04:23 AM 1/23/2004 +0100, you wrote:

Now for the fourth time, "those 40 searches per second" scenario will
never happen, for previously given reasons.

I reached 22 searches/second pretty easily whilst on 5 hubs. Why, again, won't 40 searches/second ever happen?

Btw., you seem to be inventing different name puns on Linux in every
mail that you write. While, as I stated, I think that it would be
constructive to stop bashing at each others operating systems, I can't
help being a bit curious as to what grudge it is that you hold against
an excellent operating system. Would you mind mailing me your reasons
in a private mail?

See Gargoyle's and my mails regarding 'windoz'.

-cologic

Fredrik Tolf wrote:

I really don't think that was the heart of the matter. The thing was
that with unknown broadcasted commands, you could potentially give a
command that would force compliant clients to send lots of data to an
unrelated IP address, thereby making DDoS attacks easy.

I'm not sure I follow.  Certainly, you could (if the hub doesn't enforce proper IPs) send a connection message to clients making them all try to connect to a remote IP.  Or you could similarly fake an IP in the search string (causing a bit of udp traffic to the remote IP).  Both are possible with the current protocol.  If you're suggesting that there's a buffer overflow in one of the yet-to-be-coded clients... sure.  Having the hub screen unknown commands (beyond some common-sense rate and bandwidth limiting) is the wrong approach to protecting users in my opinion.  Such a buggy client should get eliminated (or fixed) through the software equivalent of natural selection - bad clients and hubs deserve to die and be replaced with better ones.

I'd rather not be guessing blindly at what you mean, so please clarify why your opposed to hubs broadcasting (or routing) unknown commands.

- Todd

blackclaw@parsoma.net writes:
> At 04:23 AM 1/23/2004 +0100, you wrote:
> >Now for the fourth time, "those 40 searches per second" scenario will
> >never happen, for previously given reasons.
> > I reached 22 searches/second pretty easily whilst on 5 hubs. Why, again, > won't 40 searches/second ever happen?

I'm sorry, I didn't mean it like that. I meant that the maximum search
frequency never will be bottlenecked that low.

Fredrik Tolf

Fredrik Tolf wrote:

Oh, I'm sorry. I just thought that you had misspelled it by
accident. I hadn't seen that name pun before.

I'll try to be a bit less oblique next time.  Anyone planning a GNU/HURD hub/client? ;)

- Todd

Todd Pederzani writes:
> Fredrik Tolf wrote:
> > >I really don't think that was the heart of the matter. The thing was
> >that with unknown broadcasted commands, you could potentially give a
> >command that would force compliant clients to send lots of data to an
> >unrelated IP address, thereby making DDoS attacks easy.
> >  > >
> I'm not sure I follow.  Certainly, you could (if the hub doesn't enforce > proper IPs) send a connection message to clients making them all try to > connect to a remote IP.  Or you could similarly fake an IP in the search > string (causing a bit of udp traffic to the remote IP).  Both are > possible with the current protocol.

That was what I was referring to. And I don't think anyone said that
the current protocol was perfect.

In any case, I don't really know why I even followed up on the DoS
matter. The thing that I really don't agree with about ADC is the fact
that such a command division isn't actually necessary. I believe that
all commands should be clearly defined, and those that are broadcasted
should be specified in such a way that allows for easy future
extension of those commands.

Fredrik Tolf

Todd Pederzani writes:
> Fredrik Tolf wrote:
> > >Oh, I'm sorry. I just thought that you had misspelled it by
> >accident. I hadn't seen that name pun before.
> >  > >
> > I'll try to be a bit less oblique next time.  Anyone planning a GNU/HURD > hub/client? ;)

Yeah, I am, as soon as the Hurd becomes operational in... 10 years? Or
is the current schedule maybe aiming for 2030? =)

Seriously, I _love_ the Hurd concept, but... I'd just love if it
actually seemed to be getting anywhere. It's a real petty that it
doesn't.

Fredrik Tolf

>There is a little flaw in your demonstration. You have assumed when a
> client searches for "a b c d", this means "a" & "b" & "c" & "d" but it is
> wrong. Speaking about probability, a.*b.*c.*d is probably what the user
> wants the most. For example, if a user searches for an album, he won't
> spend time to write the album title in the reverse order. That's why most
> of the time, "a b c d" means "a.*b.*c.*d" (when it is not exactly "a b c
> d"). Any user having enough experience in any search engine (even google)
> knows he should not use some simple words like "a", "the", "is" and to
> search for "heaven is a place on earth", he will search "heaven place
> earth" (and it is even shorter to write :) ).

I can with equal validity state that "a b c d is probably what the user
wants the
most": the more exacting the default searches are, the more different
searches an average/median user must use to attempt to find what he wants.

I don't have any evidence to back this claim up, but you didn't present any
either.

I agree, I just based what I said on what I have seen from the usage made by friends who have no computer science knowledge, whom we simply call "basic user".

>optimizing something is good but optimizing something which is limited is
>IMHO
>just a waste of time.

Regular expressions are limited too, just differently.

Yes, their limits just are less close.

>Moreover, finding something is good, being able to send
>it to the client requesting it in a reasonable period of time is better.
> Not everybody has access to a 100Mb connection, most of the users have
> ADSL or cable connections and if they take 5-10 minutes to send/receive
> their reply, I think they won't use this P2P network.

To what is this a response? Has anyone disagreed that "finding something is
good"?

it is not a response to anything, it is just a simple reflexion on our reality (or everyday life).

Eric

At 04:34 PM 1/23/2004 +0100, you wrote:

But you should admit gnutella was not the most widely used protocol and there
is perhaps a reason. If it was that good, it should be more used than others
especially because it is available for now several years. What I just want to
say is we should not choose something because it is easy to optimize, we
should choose something for its features, optimizations will come later.

Would it make you feel better if I called them "bloom filters"? That's their more correct name anyway.

Of course Gnutella isn't the most widely used protocol, but as you've pointed out, popularity doesn't necessarily correlate with virtue. Would you call for DC to adopt the FastTrack protocol? It is probably the most popular, due to its usage in Kazaa.

Further, this isn't adopting all of Gnutella, this is adopting one good idea of theirs... Argue against the idea, not "Gnutella suxx0rs [debatable point anyway], so everything within it must too".

-cologic

A client with insufficient bandwidth to handle the hubs connections with
complete and utter ease is one I don't care about downloading from anyway.

except if it is the only one having the file you want :)

Eric

At 05:01 AM 1/23/2004 +0100, you wrote:

Yeah, I am, as soon as the Hurd becomes operational in... 10 years? Or
is the current schedule maybe aiming for 2030? =)

Seriously, I _love_ the Hurd concept, but... I'd just love if it
actually seemed to be getting anywhere. It's a real petty that it
doesn't.

I thought it acquired an IDE driver or something recently?

-cologic

eric writes:
> > > In a filesharing client? None of Gnutella, Kazaa, Napster, nor
> > the current DC have trained them to expect such case-sensitivity,
> > nor do the top few web search engines implement it.
> > but maybe we should be able to tell on-the-fly if the query is
> case-sensitive or not (a good example of why: you probably know a
> movie named xXx :) ).

That's true! I haven't thought of that. I wonder if they chose the
name so that noone would be able to download it? =)

Fredrik Tolf

Fredrik Tolf wrote:

2. Since hubs will restrict the search frequency anyway, isn't up to
  the user if he wants to search for the same thing again the next
  time he can, instead of searching for something else?

Must this be the case?  I haven't understood why discarding searches (or discarding searches and warning the user) is a better approach than reordering of commands by the hub.  The cost is code complexity, but if you can delay searches, isn't that a more elegant solution?

- Todd

Quoting Todd Pederzani <todd.pederzani@verizon.net>:

Fredrik Tolf wrote:

>2. Since hubs will restrict the search frequency anyway, isn't up to
>   the user if he wants to search for the same thing again the next
>   time he can, instead of searching for something else?
>  >

Must this be the case?  I haven't understood why discarding searches (or discarding searches and warning the user) is a better approach than reordering of commands by the hub.  The cost is code complexity, but if you can delay searches, isn't that a more elegant solution?

 - Todd

At 04:41 AM 1/23/2004 +0100, you wrote:

1. Since the regex searches will take almost exactly the same time
   anyway (and therefore will be aborted at almost exactly the same
   point), the users will most likely not get different results, or at
   least not that very different results.
2. Since hubs will restrict the search frequency anyway, isn't up to
   the user if he wants to search for the same thing again the next
   time he can, instead of searching for something else?

The precise timing of a command may vary widely:

!!!$Lolita$College$Chick$Sucks$And$Fucks$Cucumber$In$Shaved$Hairless$Pussy$Xxx$Teen$Sex$Porno$1$$1$wtsoybno$mpg ranged from 6996 to 3291617 cycles, almost 3 orders of magnitude.

!!!best$cum$compilation$ever!.mpg ranged from 5711 to 25430 cycles.

!$pornstar$Sylvia$Saint$omg$what$an$ass,$takes$2$dicks,$lots$cum$and$rides$cock,$very$good$quality,$mgp$avi$: experimental took 18 ticks, current took 458768 ranged from 6184 to 458768 cycles.

!$teen$virgin$first$time$sex$OUCH$mpg ranged from 6799 to 219850 cycles.

!SNDSTOR$XM ranged from 895270 to 18641231 cycles.

!Trade$only!$Lolitas$Molly$babysitter$mpg$ ranged from 6595 to 259806 cycles.

"Hunter$X$Hunter" (quotation marks in original query) required from 5590 to 1455825 cycles to complete.

#1$$$Basics$$$Step$By$Step$mpg required from 5473 to 292763 clock cycles to complete.

While the RE search could behave differently, my point here is that even what should be fairly deterministic now isn't, and instead produces three-order of magnitude differences in query processing times. I therefore contest the validity of your first point.

Regarding your second point, sure, but if a user needs to find a certain file, and will after that stop searching, better to allow him to find the file he wants with fewer searches.

-cologic

Fredrik Tolf wrote:

That was what I was referring to. And I don't think anyone said that
the current protocol was perfect.

Oh, certainly not.  But hubs can protect against *some of it* - witness the hubs that need the NatUsers script (or other exemptions for people with legitimate wrong-ips in various protocol commands).

In any case, I don't really know why I even followed up on the DoS
matter. The thing that I really don't agree with about ADC is the fact
that such a command division isn't actually necessary. I believe that
all commands should be clearly defined, and those that are broadcasted
should be specified in such a way that allows for easy future
extension of those commands.

True, this is a better argument than a half-hearted DC-client-as-ddos-tool argument (but that should be a topic of discussion at some point - how to handle "evilness" in the network).

For me, ADC makes sense:   The simplicity of, more or less, being able to write a hub that consists of a switch statement is appealing.  So is the ability add arbitrary broadcast and directed commands.  Users want a lot of things, and all of them won't be covered by any single protocol we accept.  If a new directed command is needed (say, for client to client cctp), making its function dependent upon what (adc or dolda-connect compliant) hubsoft the clients are attached to is just plain unacceptable - it's the same situation we have now.

- Todd

Fredrik Tolf wrote:

Yeah, I am, as soon as the Hurd becomes operational in... 10 years? Or
is the current schedule maybe aiming for 2030? =)

I... don't keep up on it.  I see the Debian/Hurd page says Hurd "does not provide the performance and stability you would expect from a production system."  I'll try it after Debian releases a distro on it, which should only be a couple dozen months after Hurd itself is released.

Seriously, I _love_ the Hurd concept, but... I'd just love if it
actually seemed to be getting anywhere. It's a real petty that it
doesn't.

Hurd is a very bad poster boy for open source... especially when compared to Linux.  But we all know that competition is good.  Throwing Hurd in the mix with Linux and Free/Net/OpenBSD can't hurt.

- Todd

blackclaw@parsoma.net writes:
> >Btw., you seem to be inventing different name puns on Linux in every
> >mail that you write. While, as I stated, I think that it would be
> >constructive to stop bashing at each others operating systems, I can't
> >help being a bit curious as to what grudge it is that you hold against
> >an excellent operating system. Would you mind mailing me your reasons
> >in a private mail?
> > See Gargoyle's and my mails regarding 'windoz'.

I'm sorry, but I can't seem to find anything about that in either my
mailbox or in the archives (even if I search through the raw archive
mbox, I can't find anything that looks like it). Was that on this
list?

Fredrik Tolf

Todd Pederzani writes:
> Fredrik Tolf wrote:
> > >2. Since hubs will restrict the search frequency anyway, isn't up to
> >   the user if he wants to search for the same thing again the next
> >   time he can, instead of searching for something else?
> >  > >
> > Must this be the case?  I haven't understood why discarding searches (or > discarding searches and warning the user) is a better approach than > reordering of commands by the hub.  The cost is code complexity, but if > you can delay searches, isn't that a more elegant solution?

Nah, I'm not sure about that. What if the user accidently presses
enter like 10 times (has happened to me from time to time when I'm so
tired that I think I let the button up completely, but in fact, it's
still down and autotyping)? Then all of a sudden the user must wait
for like 2 minutes two search again.

I think that it's better to make the hub warn, and then if the user
wants delayed searches, that can be implemented in the client instead.

Fredrik Tolf

eric wrote:

But you should admit gnutella was not the most widely used protocol and there is perhaps a reason. If it was that good, it should be more used than others especially because it is available for now several years. What I just want to say is we should not choose something because it is easy to optimize, we should choose something for its features, optimizations will come later.

Gnutella is actively developed, whereas the DC protocol is not.  Sure, it *might* be worthless because few of its features have migrated to other P2P networks, but it's not.  Measuring by user count (or popularity in general) is also a poor indication of technical worthiness.

Oh, and for your information, Bloom filters (the concept behind QRP - name furnished by cologic) are in DC++'s CVS repository right now.  They cut CPU usage by about half.

- Todd